江苏龙网

  1. 主页 > 生活百科 > >

一致性哈希算法的介绍与实现( 二 )

其中标准差较小 ， 说明分布较为均匀 ， 那我们的需求达到了 。
接着 ， 随着业务的发展 ， 你发现100个节点不够用了 ， 我们希望再增加10个节点 ， 来提高系统性能 。而我们还将继续采用之前的方法来分布数据 。这时候就出现了一个新的问题 ， 我们是通过“哈希+取模”来决定数据的相应节点 ， 原来数据的哈希值是不会改变的 ， 可是取模的时候节点的数量发生了变化 ， 这将导致的结果就是原来的数据存在A节点 ， 现在可能需要迁移到B节点 ， 也就是数据迁移问题 。下面我们来看下有多少数据将发生迁移 。
【一致性哈希算法的介绍与实现】private static int newNodeNum = 11;private static List<String> newNodes = initNode(newNodeNum);public static void normalHashMigrateMain() {    int migrateCount = 0;    for (Integer data : datas) {        String node = normalHash(data, nodes);        String newNode = normalHash(data, newNodes);        if (!node.equals(newNode)) {            migrateCount++;        }    }    System.out.println(String.format("数据迁移量：%d（%.2f%%）", migrateCount, migrateCount * 100.0 / datas.size()));}/**数据迁移量：9091127（90.91%）**/有90%多的数据都需要进行迁移 ， 这是几乎全部的量了 。普通哈希的问题暴露出来了 ， 当将节点由100扩展为110时 ， 会存在大量的迁移工作 。在1997年MIT提出了一致性哈希算法 ， 用于解决普通哈希的这一问题 。
我们再分析下 ， 假设hash值为10000 ， nodeNum为100 ， 那按照index = hash % nodeNum得到的结果是0 ， 而将100变为110时 ， 取模的结果将改变为100 。如果我们将取模的除数增大至大于hash值 ， 那hash值取模的结果将仍是其本身 。也就是说 ， 只要除数保证大于hash值 ， 那取模的结果将不会改变 。这里的hash值是int ， 4个字节 ， 那我们把除数固定为2^32-1 ， index = hash % (2^32-1) 。取模的结果也将固定在0到2^32-1中 ， 可将其构成一个环 ， 如下所示 。

一致性哈希算法的介绍与实现

文章插图
 
取模的结果范围
现在的除数是2^32-1 ， hash值为10000 ， 取模的结果为10000 ， 而我们有100个节点 ， 该映射到哪个节点上呢？我们可以先将节点通过哈希映射到环上 。为了绘图方便 ， 我们以3个节点为例 ， 如下图所示：
一致性哈希算法的介绍与实现

文章插图
 
一致性哈希环
10000落到环上后 ， 如果没有对应的节点 ， 则按顺时针方向找到下一个节点 ， 便为hash值对应的节点 。下面我们用JAVA的TreeMap来存节点的hash值 ， 利用TreeMap的tailMap寻找节点 。
我们使用和之前同样的方法 ， 测试下当节点由100变为110时 ， 数据需要迁移的情况 ， 如下所示：
public static void consistHashMigrateMain() {    int migrateCount = 0;    SortedMap<Integer, String> circle = new TreeMap<>();    for (String node : nodes) {        circle.put(hash(node), node);    }    SortedMap<Integer, String> newCircle = new TreeMap<>();    for (String node : newNodes) {        newCircle.put(hash(node), node);    }    for (Integer data : datas) {        String node = consistHash(data, circle);        String newNode = consistHash(data, newCircle);        if (!node.equals(newNode)) {            migrateCount++;        }    }    System.out.println(String.format("数据迁移量：%d（%.2f%%）", migrateCount, migrateCount * 100.0 / datas.size()));}public static String consistHash(Integer data, SortedMap<Integer, String> circle) {    int hash = hash(data);    // 从环中取大于等于hash值的部分    SortedMap<Integer, String> subCircle = circle.tailMap(hash);    int index;    // 如果在大于等于hash值的部分没有节点 ， 则取环开始的第一个节点    if (subCircle.isEmpty()) {        index = circle.firstKey();    } else {        index = subCircle.firstKey();    }    return circle.get(index);}/**数据迁移量：817678（8.18%）**/


推荐阅读


上一篇：禅意绿茶十二道,喝出时尚的禅意生活

下一篇：茶叶的原产地是中国吗,茶叶发源于中国