一致性hash算法

PHPor 的Blog 2009-11-20 21:01:37 浏览 4,105 次

标签 hash 一致性

一致性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();

一致性hash算法

建议继续学习