[笔记]用ets实现了把一致性哈希中的最接近项查找

最近有些空，继续捣鼓consisten hash的简单实现。先前修改gb_trees，加入了lookup_nearest(Key, Tree) 函数，通过二叉查找和回朔，来查找最接近Key的项。昨天看了下xbaytable的DHT实现，发觉其实用ets会更快捷：

ets:prev(Table, Key) 和 ets:next(Table, Key) 函数，可以返回Table中Key的上一个或下一个存在的键，无论这个Key是否存在于Table中。再加上 ets:first/1、ets:last/1、ets:lookup/2，就可以实现了。

实践过程中发现了个问题，需要定义这个哈希范围的最大值，比如 0xFFFFFFFF （4294967295），才能正确比较环中最接近的一个点，比如环里面有两个Key：{4294960010，10}，对于 4294963657，最接近的是 4294960010，而对于4294963658，最接近的是10。原先使用二叉查找的实现忽略了这个问题，会导致查找4294960011会返回10。

ets是使用c代码实现，性能和内存占用比gb_trees好很多，构造429497个元素的ets，操作在几秒内完成，而gb_trees起码要几十秒，完全不在一个量级。不过查找最接近的值耗时就很接近，查找4294968次，gb_trees实现花了61875ms，ets实现花了65031ms，结果很接近。

此外还有一个问题，就是在使用next，prev过程中碰到了‘锁’的问题，毕竟ets是一种共享的存储结构。文档说明：

引用

Unless a table of type set, bag or duplicate_bag is protected using safe_fixtable/2, see below, a traversal may fail if concurrent updates are made to the table. If the table is of type ordered_set, the function returns the next key in order, even if the object does no longer exist.

对ets和dets的使用还是太少了，抽空再写写代码加深认识

===================
4.2修改：搞错单位了，应该是1ms内可以调用50多次。。。

评论

1 楼 mryufeng 2008-04-02  

ets肯定会比gb_tree快 毕竟是c实现的 推荐大量使。事实上erlang的标准库也是大量在用它。