一致性hash算法 -- 算法 -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> 算法 --> 一致性hash算法

一致性hash算法

浏览:3466次出处信息

一致性hash算法（consitent Hash）用于解决动态cache问题 http://baike.baidu.com/view/1588037.html

memcach中一个具体实现算法：

初始化：

已有server m个和各自权重，构建 40*server个数*4个bucket，每个bucket实际上就是一个long值，按照权重分配给各个server，所有的bucket会分布在2的32次方的空间中，用一个TreeMap来存储。

以下是代码片段：
    double factor = Math .floor(((double) (40 * this.servers.length * thisWeight)) / (double) this.totalWeight);
             for (long j = 0; j < factor; j++)
             {
      //md5结果为16个字节，每4个一组，转成一个long值（在0到2的32次方间）
                 byte[] d = md5.digest((servers[i] + "-" + j).getBytes());
                 for (int h = 0; h < 4; h++)
                 {
                     Long k = ((long) (d[3 + h * 4] & 0xFF) << 24)
                             | ((long) (d[2 + h * 4] & 0xFF) << 16)
                             | ((long) (d[1 + h * 4] & 0xFF) << 8)
                             | ((long) (d[0 + h * 4] & 0xFF));
                     consistentBuckets.put(k, servers[i]);

                 }
             }

根据key来查找来分配server:

计算key的hash code,从TreeMap中查找大于它的节点，如果有则取第一个，没有则取TreeMap的第一个（相当于一个圆环）

以下是代码片段：
         SortedMap tmap = this.consistentBuckets.tailMap(hv);
         return (tmap.isEmpty()) ? this.consistentBuckets.firstKey() : tmap
                 .firstKey();

建议继续学习：

QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习

<< 前一篇：C/C++循环获取文件中的每行数据（别以为很简单！）

后一篇：最近几个容易错的地方总结(hash_map迭代删除,localtime(),线程状态) >>

文章信息

作者：phpor 来源： PHPor 的Blog
标签： hash 一致性
发布时间：2009-11-20 21:01:37

建议继续学习

近3天十大热文