一致性哈希算法的分析与实现

哈希函数，想必大家都不陌生。通过哈希函数我们可以将数据映射成一个数字（哈希值），然后可用于将数据打乱。例如，在HashMap中则是通过哈希函数使得每个桶中的数据尽量均匀。那一致性哈希又是什么？它是用于解决什么问题？本文将从普通的哈希函数说起，看看普通哈希函数存在的问题，然后再看一致性哈希是如何解决，一步步进行分析，并结合代码实现来讲解。

首先，设定这样一个场景，我们每天有1千万条业务数据，还有100个节点可用于存放数据。那我们希望能将数据尽量均匀地存放在这100个节点上，这时候哈希函数就能派上用场了，下面我们按一天的数据量来说明。

首先，准备下需要存放的数据，以及节点的地址。为了简单，这里的数据为随机整型数字，节点的地址为从“192.168.1.0”开始递增。

privatestaticintdataNum=10000000;privatestaticintnodeNum=100;privatestaticList<Integer>datas=initData(dataNum);privatestaticList<String>nodes=initNode(nodeNum);privatestaticList<Integer>initData(intn){List<Integer>datas=newArrayList<>();Randomrandom=newRandom();for(inti=0;i<n;i++){datas.add(random.nextInt());}returndatas;}privatestaticList<String>initNode(intn){List<String>nodes=newArrayList<>();for(inti=0;i<n;i++){nodes.add(String.format("192.168.1.%d",i));}returnnodes;}

接下来，我们看下通过“哈希+取模”得到数据相应的节点地址。这里的hash方法使用Guava提供的哈希方法来实现，后文也将继续使用该hash方法。

publicstaticStringnormalHash(Integerdata,List<String>nodes){inthash=hash(data);intnodeIndex=hash%nodes.size();returnnodes.get(nodeIndex);}privatestaticinthash(Objectobject){HashFunctionhashFunction=Hashing.murmur3_32();if(objectinstanceofInteger){returnMath.abs(hashFunction.hashInt((Integer)object).asInt());}elseif(objectinstanceofString){returnMath.abs(hashFunction.hashUnencodedChars((String)object).asInt());}return-1;}

最后，我们对数据的分布情况进行统计，观察分布是否均匀，这里通过标准差来观察。

publicstaticvoidnormalHashMain(){Map<String,Integer>nodeCount=newHashMap<>();for(Integerdata:datas){Stringnode=normalHash(data,nodes);if(nodeCount.containsKey(node)){nodeCount.put(node,nodeCount.get(node)+1);}else{nodeCount.put(node,1);}}analyze(nodeCount,dataNum,nodeNum);}publicstaticvoidanalyze(Map<String,Integer>nodeCount,intdataNum,intnodeNum){doubleaverage=(double)dataNum/nodeNum;IntSummaryStatisticss1=nodeCount.values().stream().mapToInt(Integer::intValue).summaryStatistics();intmax=s1.getMax();intmin=s1.getMin();intrange=max-min;doublestandardDeviation=nodeCount.values().stream().mapToDouble(n->Math.abs(n-average)).summaryStatistics().getAverage();System.out.println(String.format("平均值：%.2f",average));System.out.println(String.format("最大值：%d,（%.2f%%）",max,100.0*max/average));System.out.println(String.format("最小值：%d,（%.2f%%）",min,100.0*min/average));System.out.println(String.format("极差：%d,（%.2f%%）",range,100.0*range/average));System.out.println(String.format("标准差：%.2f,（%.2f%%）",standardDeviation,100.0*standardDeviation/average));}/**平均值：100000.00最大值：100818,（100.82%）最小值：99252,（99.25%）极差：1566,（1.57%）标准差：240.08,（0.24%）**/

其中标准差较小，说明分布较为均匀，那我们的需求达到了。

接着，随着业务的发展，你发现100个节点不够用了，我们希望再增加10个节点，来提高系统性能。而我们还将继续采用之前的方法来分布数据。这时候就出现了一个新的问题，我们是通过“哈希+取模”来决定数据的相应节点，原来数据的哈希值是不会改变的，可是取模的时候节点的数量发生了变化，这将导致的结果就是原来的数据存在A节点，现在可能需要迁移到B节点，也就是数据迁移问题。下面我们来看下有多少数据将发生迁移。

privatestaticintnewNodeNum=11;privatestaticList<String>newNodes=initNode(newNodeNum);publicstaticvoidnormalHashMigrateMain(){intmigrateCount=0;for(Integerdata:datas){Stringnode=normalHash(data,nodes);StringnewNode=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时，数据需要迁移的情况，如下所示：

publicstaticvoidconsistHashMigrateMain(){intmigrateCount=0;SortedMap<Integer,String>circle=newTreeMap<>();for(Stringnode:nodes){circle.put(hash(node),node);}SortedMap<Integer,String>newCircle=newTreeMap<>();for(Stringnode:newNodes){newCircle.put(hash(node),node);}for(Integerdata:datas){Stringnode=consistHash(data,circle);StringnewNode=consistHash(data,newCircle);if(!node.equals(newNode)){migrateCount++;}}System.out.println(String.format("数据迁移量：%d（%.2f%%）",migrateCount,migrateCount*100.0/datas.size()));}publicstaticStringconsistHash(Integerdata,SortedMap<Integer,String>circle){inthash=hash(data);//从环中取大于等于hash值的部分SortedMap<Integer,String>subCircle=circle.tailMap(hash);intindex;//如果在大于等于hash值的部分没有节点，则取环开始的第一个节点if(subCircle.isEmpty()){index=circle.firstKey();}else{index=subCircle.firstKey();}returncircle.get(index);}/**数据迁移量：817678（8.18%）**/

可见需要迁移的数据由90%降到了8%，效果十分可观。那我们再看下数据的分布情况，是否仍然均匀：

/**平均值：100000.00最大值：589675,（589.68%）最小值：227,（0.23%）极差：589448,（589.45%）标准差：77421.44,（77.42%）**/

77%的标准差，一个字，崩！这是为啥？我们原本设想的是节点映射到环上时，能将环均匀划分，所以当数据映射到环上时，也将被均匀分布到节点上。而实际情况，由于节点地址相似，映射到环上的位置也将相近，所以造成分布的不均匀，如下图所示：

分布不均

由于A、B、C的地址相似，例如：

A:192.168.1.0B:192.168.1.1C:192.168.1.2

所以映射的位置相近，那我们可以复制几份A、B、C，并且通过改变key，让节点能更均匀的划分环。比如我们在地址后面追加 “-index” 的序号，例如：

A0:192.168.1.0-0B0:192.168.1.1-0C0:192.168.1.2-0A1:192.168.1.0-1B1:192.168.1.1-1C1:192.168.1.2-1

虽然A0、B0、C0会相距较近，但是和A1、B1、C1的key具有差别，将能够成功分开，这也正是虚拟节点的作用。达到的效果如下：

虚拟节点

下面我们通过代码验证下实际效果：

privatestaticintvNodeNum=100;publicstaticvoidconsistHashVirtualNodeMain(){Map<String,Integer>nodeCount=newHashMap<>();SortedMap<Integer,String>circle=newTreeMap<>();for(Stringnode:nodes){for(inti=0;i<vNodeNum;i++){circle.put(hash(node+"-"+i),node);}}for(Integerdata:datas){Stringnode=consistHashVirtualNode(data,circle);if(nodeCount.containsKey(node)){nodeCount.put(node,nodeCount.get(node)+1);}else{nodeCount.put(node,1);}}analyze(nodeCount,dataNum,nodeNum);}/**平均值：100000.00最大值：122931,（122.93%）最小值：74434,（74.43%）极差：48497,（48.50%）标准差：7475.08,（7.48%）**/

可看到标准差已经由77%降到7%，效果显着。再多做几组实验，标准差随着虚拟节点数的变化如下：

虚拟节点数标准差1021661.04,（21.66%）1007475.08,（7.48%）10002498.36,（2.50%）10000858.96,（0.86%）100000363.98,（0.36%）

结果中，随着虚拟节点数的增加，标准差逐步下降。可见虚拟节点能达到均匀分布数据的效果。

一句话总结下：

一致性哈希可用于解决哈希函数在扩容时的数据迁移的问题，而一致性哈希的实现中需要借助虚拟节点来均匀分布数据。

最后，大家可以再思考两个问题：

虚拟节点越多越好吗？会不会有什么负面影响？Java中的HashMap在扩容时如何优化数据迁移问题？