技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 一致性hash算法

一致性hash算法

浏览:3411次  出处信息
一致性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();

建议继续学习:

  1. HashMap解决hash冲突的方法    (阅读:11326)
  2. 关于memcache分布式一致性hash    (阅读:10714)
  3. 一致性哈希算法及其在分布式系统中的应用    (阅读:7994)
  4. 分布式哈希和一致性哈希    (阅读:7729)
  5. MinHash原理与应用    (阅读:5933)
  6. LVS hash size解决4096个并发的问题    (阅读:5443)
  7. 无锁HashMap的原理与实现    (阅读:5464)
  8. 如果用户在5分钟内重复上线,就给他发警告,问如何设计?    (阅读:4887)
  9. Ubuntu 下Hash校验和不符问题的解决    (阅读:4592)
  10. 分布式系统hash策略    (阅读:3777)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1