论文部分内容阅读
摘要：分布式存储系统中为了实现高可用、高性能和高扩展性，系统内数据布局和负载均衡是关键的技术问题。一致性哈希算法是解决此类问题行之有效的方法。将对比研究几种一致性哈希算法，包括基本和带虚拟节点的一致性哈希，微信存储系统中应用的一致性哈希和谷歌跳跃一致性哈希。对微信存储应用的一致性哈希进行了改进。
关键词：一致性哈希;虚拟节点;跳跃一致性哈希
Abstract： In order to achieve high availability， high performance， and high scalability in distributed storage systems， data layout and load balancing in the system are key technical issues. The consistent hashing algorithm is an effective way to solve such problems. Several consistent hashing algorithms will be studied and compared， including basic consistent hashing， consistent hashing with virtual nodes， consistent hashing used in WeChat storage systems and Google jump consistent hashing. The consistent hashing used in WeChat is improved.
Keywords： Consistent hashing; Virtual node; Jump consistent hashing
分布式存储系统发展过程中，遇到了多个方面的挑战，其一是数据分散存储在系统中，当系统面对海量读写请求时，如何保障系统的负载均衡避免出现数据倾斜。第二为应对系统流量的增长和萎缩，集群系统需要能够动态添加和删除节点，在保持负载均衡的同时实现数据的最小化迁移。一致性哈希算法因为具有良好的均衡性和一致性，在分布式存储系统中受到广泛的应用。
基本一致性哈希算法在Kager于1997年论文[1]中提出并其后应用于Danamo和Switf等系统后，衍生了多种优化改进的算法，包括带虚拟节点的一致性哈希，微信核心业务存储系统使用的一致性哈希，谷歌跳跃一致性哈希，maglev一致性哈希，负载有界一致性哈希，以及其他改进的一致性哈希算法等。对上述的部分一致性哈希算法，论文将从均衡性和一致性两个方面进行对比研究，并对微信存储系统使用的一致性哈希进行了优化。其中均衡性是指数据经过哈希后能尽可能分散到所有服务器节点中，每个服务器处理的数据相当，均衡的算法能最大化系统利用率。一致性是指系统增加节点需要对数据key进行重新映射，数据key只能保留在原有节点或者移动到新节点上，不能移动到其他的节点上。
1算法对比
1.1基本一致性哈希和带虚拟节点的一致性哈希
基本的一致性哈希算法原理如图1，算法过程如下：
（1）设置一个地址空间范围为0～（232-1）的哈希环;
（2）使用节点的特征值（一般使用节点ip地址）计算哈希值，映射到哈希环上的一点。如图1所示节点S1，其ip地址经过哈希后落入哈希环上一点。对每个节点都使用同样的方法映射到哈希环上;
（3）对存取数据key使用相同的哈希函数计算哈希值映射到哈希环上，以此位置顺时针查找第一个落入到哈希环的节点。图1中key3经过哈希后顺时针找到了S2节点。
基本一致性哈希算法并不均衡[2]，在哈希环上复制虚拟节点的方法可以改善此算法的均衡度[3]，其思想是将一个节点（也称为实际节点或者实节点）在哈希环的不同位置上放置多个拷贝（称为虚拟节点），并调整上述算法的第二步，使用实节点对应虚拟节点的特征计算哈希值映射到哈希环（比如使用“192.168.1.100#1”作为192.168.1.100实节点编号为1的虚拟节点的特征），对每个实节点设置一定数量的虚拟节点映射到哈希环上，而要查找数据key对应的实节点，是先通过其哈希值顺时针找到虚拟节点再找到对应的实节点。
显然，新添加一个节点映射到哈希环上时，只有这个节点的哈希值（或者其对应虚拟节点的哈希值）与逆时针方向的前一个哈希值之间的数据key会被重新映射到新的节点，其他数据key继续保留在原有节点，两种算法都满足一致性的要求。
关于均衡性，从图1可以看到，落入节点的数据key的数量，与每个节点在哈希环中负责的地址空间密切相关，一致性哈希算法的均衡度，可由节点在哈希环负责的地址空间的差异来度量。在实际应用中，分布式系统一般是由相同配置的服务器节点构成，为了提高节点利用率和减少运营成本，要求选用均衡度较好的一致性哈希算法，另外按照木桶理论，分布式系统最大处理能力由最先进入过载的节点决定，也就是负载最高的节点决定了集群整体的性能，而在不考虑热点数据情况下，节点的负载与其负责的地址空间成正比例关系。因此论文用三个与地址空间有关的指标来衡量算法的均衡度：集群中最大地址空间与最小地址空间的比值R1，地址空间值与平均值相差10%、2%以内的节点数量在总节点数的比例R2和R3。
表1展示了使用md5 fnv1_32函數对节点或虚拟节点特征值进行哈希，通过程序统计得到两种算法在不同节点数配置下系统的R1和R2。ip地址和哈希函数的不同对统计结果会产生一些变化，但不会影响整体的结论。
基本一致性哈希算法的一般趋势是R1值随着节点数的增加而急速增加，此外R2值都比较低，意味着使用此算法的系统，其节点间的负载是非常不均衡的。比如30节点下，R1已超过了100，系统节点间会出现负载差异百倍的情况。带虚拟节点的一致性哈希算法均衡度得到了明显的改善，如30个实节点每个配置30个虚拟节点，R1已经降低到了2以下，远低于基本一致性哈希中的R1。此外在实节点数确定时，虚拟节点数的增加可以降低R1和提高R2，提高节点间均衡度;但虚拟节点数确定时，系统增加实节点时则会升高R1和降低R2，降低节点间均衡度。但考虑系统的复杂性，虚拟节点数并不会无限制的提高，实际应用中每个实节点配置100个虚拟节点是一个常用的配置。在此配置下，系统并非完全均衡，比如超过30个实节点的集群，R1超过了1.5，R2低于0.7，意味着系统会出现高负载是低负载1.5倍的情况，并且超过30%的机器负载偏离了平均负载的10%。 1.2微信PaxosStore一致性哈希算法
基本和带虚拟节点的一致性哈希算法，节点在哈希环的位置完全依赖于节点或虚拟节点特征的哈希值，哈希过程不可控，造成了两个算法的不完全均衡。如果能够人为控制这个哈希过程，让每个新加入的节点其管理的地址空间严格控制在平均值的一定范围内，那么算法的均衡将会提高。PaxosStore分布式存储系统采用了此思路的一致性哈希算法。
PaxosStore[4]分布式存储系统是腾讯2017年在github开源的项目，用于支持微信核心业务，此系统采用一致性哈希算法用于数据分片和负载均衡，算法与1.1带虚拟节点的一致性哈希算法相似，每个实节点有多个虚拟节点映射到哈希环上，但构建哈希环的过程有所不同，具体过程如下：
（1）设置一个地址空间范围为0～（232-1）的哈希环;
（2）对实节点编号：假设实节点数为n，将实节点顺序编号为0，1，...n-1;
（3）从预生成的哈希值字典中找到编号0对应的M个哈希值，作为此节点的M个虚拟节点的哈希值落入到哈希环上;采用同样的方法顺序将编号1，2...n-1在哈希值字典中找到对应哈希值，总共M*n个的哈希值放置到哈希环;
（4）对存取数据的键key使用哈希函数计算哈希值映射到哈希环上，以此位置顺时针查找到第一个虚拟节点，得到的实节点编号，进而找到实节点。
其中预生成的哈希值字典是一个关键的数据，通过程序搜索求解，具有以下特性：对任意的实节点数n，按照上述算法构建的哈希环，每个节点管理的地址空间与平均值差异小于等于ε。在开源项目中PaxosStore提供了一个静态的哈希值字典，最大的实节点数为901，ε为11%，M为100。
由于开源项目中只提供了静态的哈希值字典，并未提供此字典的搜索求解算法，本文重新设计实现了搜索哈希值字典的算法，达到了更低的ε，具体算法过程如下，设置虚拟节点数字为M=100：
（1）第一个实节点S1编号为0，通过一个ip地址加虚拟节点编号的方式获得100个不同的哈希值，保存到哈希值字典;
（2）从第二个节点开始，假设当前已经获得了n个实节点的哈希值字典，新添加一个实节点Sn 1，编号为n，其虚拟节点的位置（即哈希值）通过如下启发式算法获取：
（a）计算n 1个实节点时平均地址空间Lavg=232/（n 1）;新节点Sn 1需要获得Lavg长度的地址空间才能满足均衡性的要求，设置此节点剩余获取的地址空间为Ln 1=Lavg;
（b）计算前n个实节点每个节点管理的地址空间总数，从大到小排序;找到当前最大地址空间的实节点Smax，在其虚拟节点中找到管理地址空间最大的虚拟节点Vmax;
（c）对Vmax虚拟节点进行分裂得到V1和V2，其中V1的哈希值与Vmax一致继续作为Smax节点的虚拟节点，V2为Sn 1节点的虚拟节点，V2在满足如下原则下从Vmax中获得尽可能多的地址空间：V1、V2长度最小为1，V2长度不高于Ln 1，且Vmax失去V2地址空间后Smax节点总地址空间长度与Lavg的比值不低于R（n小于100时R为100%，n大于等于100时R为99.5%）;
（d）根据步骤c分裂得到的V2添加到哈希值字典作为Sn 1的虚拟节点，更新Smax管理的地址空间，更新Ln 1（小于等于0时，强制设置为1），重复b、c、d步骤直到Sn 1的虚拟节点数达到100;
（3）重复步骤2，直到n为901为止（即PaxosStore内置哈希值字典的最大节点数），将哈希值字典保存到文件。
通过上述搜索算法得到的哈希值字典部分数据如下表所示：
由上表看到，PaxosStore采用的一致性哈希算法，其R1一般情况下都低于1.16，节点地址空间与平均值的差异基本上都小于10%;与表1相比，此算法优于带虚拟节点的一致性哈希算法。而本文优化后求解的字典则更优于PaxosStore内置字典，R1低于1.02，并且所有节点的地址空间与平均值的差异控制在2%以内。
预生成哈希值字典的算法，是在添加一个实节点时优化虚拟节点的位置，所以在尾部添加和删除节点时能做到如表3的均衡度，但不保证在中间位置删除实节点时的均衡性。关于一致性，由于此算法与带虚拟节点的一致性哈希算法相似，采用哈希环的方式，也满足一致性的要求。
1.3谷歌跳跃一致性哈希算法
前述三种算法，都需要在内存中建立一个映射表，获取数据key访问的节点，首先需要对数据key计算哈希值，然后在映射表中查找，而查找的效率与映射表的大小密切相关。谷歌在论文[5]中提出了一个简单、快速无需依赖额外内存的一致性哈希算法。算法的核心在于将数据落在系统中每个节点的概率进行平均。假设要获得的一致性哈希算法的函数是ch（key， n），其中实节点数为n，此函数返回数据key落入的节点编号（从0开始到n-1）;要實现均衡性与一致性，函数应该具有以下的特性：
（1）当n等于1时，显然对任意key，ch（key， n）返回0;
（2）当n等于2时，需要将1/2的数据重新映射到编号为1的节点，节点间继续保持均衡;
（3）当节点数从n-1增长到n时，需要将1/n数据重映射到编号n-1的节点以继续保持均衡。
当系统增加一个节点，节点数从n-1增长到n时，数据key是否会迁移到新节点，可由概率决定，如可在函数调时产生一个随机数r（0～1之间），比较随机数r与1/n的大小，如果小于则将数据key迁入新节点，否则保留在原节点，从而满足递推公式的要求;但考虑到一致性要求，在节点数n确定时数据key必须稳定在某个节点上，对此问题论文[5]采用的方法是，在获得随机数之前使用key设置一次随机种子，随机数从而与key直接相关，进而确定了在增加节点时key是迁入新节点还是继续留在原节点，满足了一致性要求。以下的python代码展示了论文中ch（key，n）函数的实现： 算法采用遍历的方式获得数据key应落入的节点编号，算法时间复杂度为O（n）。实际上论文[5]还获得了时间复杂度是O（log（n））的算法，限于篇幅关系这里不做展开。关于算法的均衡性。由于算法没有管理地址空间的概念，本文采用随机1亿个18位字符的数据key，根据节点落入key的数量来统计R1、R2、R3（精度为小数点后三位）。
此结果与论文[5]的结果吻合，跳跃一致性哈希算法的均衡性与1.2改进的算法相当。不过此算法也存在一些弊端，僅支持在末尾添加和删除节点，不能删除中间的节点。
2总结
本文依次介绍了基本一致性哈希，带虚拟节点的一致性哈希，PaxosStore使用哈希值字典的一致性哈希以及谷歌跳跃一致性哈希。通过对比研究得出，基本一致性哈希算法存在严重的不均衡现象，通过引入虚拟节点的方式，带虚拟节点的一致性哈希均衡性有了大幅的提升;PaxosStore存储系统使用了搜索求解的哈希值字典提高了均衡度，而本文改进的搜索算法更进一步提升此算法的均衡度;谷歌跳跃一致性哈希算法使用概率模型的方法，快速且不需要额外的内存，算法在均衡度上与哈希值字典方法相当，但这两种算法也有一定的限制，只能在尾端添加和删除节点。
参考文献：
[1] Karger D，Lehman E，Leighton T，et al.Consistent Hashing and Random Trees： Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web[C]//Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing， El Paso， Texas， USA， May 4-6， 1997. ACM，1997.
[2] 聂晓文，卢显良，孟江涛，等.一类DHT算法中负载的概率分布[J].计算机应用研究，2009（10）：169-172.
[3] 杨彧剑，林波.分布式存储系统中一致性哈希算法的研究[J].电脑知识与技术，2011，7（22）：5295-5296.
[4] Zheng J，Qian L，Xu J，et al.PaxosStore： high-availability storage made practical in WeChat[J]. Proceedings of the VLDB Endowment，2017，10（12）：1730-1741.
[5] Lamping J，Veach E.A Fast，Minimal Memory，Consistent Hash Algorithm[J].Computer Science，2014.
【通联编辑：梁书】
关键词：一致性哈希;虚拟节点;跳跃一致性哈希
Abstract： In order to achieve high availability， high performance， and high scalability in distributed storage systems， data layout and load balancing in the system are key technical issues. The consistent hashing algorithm is an effective way to solve such problems. Several consistent hashing algorithms will be studied and compared， including basic consistent hashing， consistent hashing with virtual nodes， consistent hashing used in WeChat storage systems and Google jump consistent hashing. The consistent hashing used in WeChat is improved.
Keywords： Consistent hashing; Virtual node; Jump consistent hashing
分布式存储系统发展过程中，遇到了多个方面的挑战，其一是数据分散存储在系统中，当系统面对海量读写请求时，如何保障系统的负载均衡避免出现数据倾斜。第二为应对系统流量的增长和萎缩，集群系统需要能够动态添加和删除节点，在保持负载均衡的同时实现数据的最小化迁移。一致性哈希算法因为具有良好的均衡性和一致性，在分布式存储系统中受到广泛的应用。
基本一致性哈希算法在Kager于1997年论文[1]中提出并其后应用于Danamo和Switf等系统后，衍生了多种优化改进的算法，包括带虚拟节点的一致性哈希，微信核心业务存储系统使用的一致性哈希，谷歌跳跃一致性哈希，maglev一致性哈希，负载有界一致性哈希，以及其他改进的一致性哈希算法等。对上述的部分一致性哈希算法，论文将从均衡性和一致性两个方面进行对比研究，并对微信存储系统使用的一致性哈希进行了优化。其中均衡性是指数据经过哈希后能尽可能分散到所有服务器节点中，每个服务器处理的数据相当，均衡的算法能最大化系统利用率。一致性是指系统增加节点需要对数据key进行重新映射，数据key只能保留在原有节点或者移动到新节点上，不能移动到其他的节点上。
1算法对比
1.1基本一致性哈希和带虚拟节点的一致性哈希
基本的一致性哈希算法原理如图1，算法过程如下：
（1）设置一个地址空间范围为0～（232-1）的哈希环;
（2）使用节点的特征值（一般使用节点ip地址）计算哈希值，映射到哈希环上的一点。如图1所示节点S1，其ip地址经过哈希后落入哈希环上一点。对每个节点都使用同样的方法映射到哈希环上;
（3）对存取数据key使用相同的哈希函数计算哈希值映射到哈希环上，以此位置顺时针查找第一个落入到哈希环的节点。图1中key3经过哈希后顺时针找到了S2节点。
基本一致性哈希算法并不均衡[2]，在哈希环上复制虚拟节点的方法可以改善此算法的均衡度[3]，其思想是将一个节点（也称为实际节点或者实节点）在哈希环的不同位置上放置多个拷贝（称为虚拟节点），并调整上述算法的第二步，使用实节点对应虚拟节点的特征计算哈希值映射到哈希环（比如使用“192.168.1.100#1”作为192.168.1.100实节点编号为1的虚拟节点的特征），对每个实节点设置一定数量的虚拟节点映射到哈希环上，而要查找数据key对应的实节点，是先通过其哈希值顺时针找到虚拟节点再找到对应的实节点。
显然，新添加一个节点映射到哈希环上时，只有这个节点的哈希值（或者其对应虚拟节点的哈希值）与逆时针方向的前一个哈希值之间的数据key会被重新映射到新的节点，其他数据key继续保留在原有节点，两种算法都满足一致性的要求。
关于均衡性，从图1可以看到，落入节点的数据key的数量，与每个节点在哈希环中负责的地址空间密切相关，一致性哈希算法的均衡度，可由节点在哈希环负责的地址空间的差异来度量。在实际应用中，分布式系统一般是由相同配置的服务器节点构成，为了提高节点利用率和减少运营成本，要求选用均衡度较好的一致性哈希算法，另外按照木桶理论，分布式系统最大处理能力由最先进入过载的节点决定，也就是负载最高的节点决定了集群整体的性能，而在不考虑热点数据情况下，节点的负载与其负责的地址空间成正比例关系。因此论文用三个与地址空间有关的指标来衡量算法的均衡度：集群中最大地址空间与最小地址空间的比值R1，地址空间值与平均值相差10%、2%以内的节点数量在总节点数的比例R2和R3。
表1展示了使用md5 fnv1_32函數对节点或虚拟节点特征值进行哈希，通过程序统计得到两种算法在不同节点数配置下系统的R1和R2。ip地址和哈希函数的不同对统计结果会产生一些变化，但不会影响整体的结论。
基本一致性哈希算法的一般趋势是R1值随着节点数的增加而急速增加，此外R2值都比较低，意味着使用此算法的系统，其节点间的负载是非常不均衡的。比如30节点下，R1已超过了100，系统节点间会出现负载差异百倍的情况。带虚拟节点的一致性哈希算法均衡度得到了明显的改善，如30个实节点每个配置30个虚拟节点，R1已经降低到了2以下，远低于基本一致性哈希中的R1。此外在实节点数确定时，虚拟节点数的增加可以降低R1和提高R2，提高节点间均衡度;但虚拟节点数确定时，系统增加实节点时则会升高R1和降低R2，降低节点间均衡度。但考虑系统的复杂性，虚拟节点数并不会无限制的提高，实际应用中每个实节点配置100个虚拟节点是一个常用的配置。在此配置下，系统并非完全均衡，比如超过30个实节点的集群，R1超过了1.5，R2低于0.7，意味着系统会出现高负载是低负载1.5倍的情况，并且超过30%的机器负载偏离了平均负载的10%。 1.2微信PaxosStore一致性哈希算法
基本和带虚拟节点的一致性哈希算法，节点在哈希环的位置完全依赖于节点或虚拟节点特征的哈希值，哈希过程不可控，造成了两个算法的不完全均衡。如果能够人为控制这个哈希过程，让每个新加入的节点其管理的地址空间严格控制在平均值的一定范围内，那么算法的均衡将会提高。PaxosStore分布式存储系统采用了此思路的一致性哈希算法。
PaxosStore[4]分布式存储系统是腾讯2017年在github开源的项目，用于支持微信核心业务，此系统采用一致性哈希算法用于数据分片和负载均衡，算法与1.1带虚拟节点的一致性哈希算法相似，每个实节点有多个虚拟节点映射到哈希环上，但构建哈希环的过程有所不同，具体过程如下：
（1）设置一个地址空间范围为0～（232-1）的哈希环;
（2）对实节点编号：假设实节点数为n，将实节点顺序编号为0，1，...n-1;
（3）从预生成的哈希值字典中找到编号0对应的M个哈希值，作为此节点的M个虚拟节点的哈希值落入到哈希环上;采用同样的方法顺序将编号1，2...n-1在哈希值字典中找到对应哈希值，总共M*n个的哈希值放置到哈希环;
（4）对存取数据的键key使用哈希函数计算哈希值映射到哈希环上，以此位置顺时针查找到第一个虚拟节点，得到的实节点编号，进而找到实节点。
其中预生成的哈希值字典是一个关键的数据，通过程序搜索求解，具有以下特性：对任意的实节点数n，按照上述算法构建的哈希环，每个节点管理的地址空间与平均值差异小于等于ε。在开源项目中PaxosStore提供了一个静态的哈希值字典，最大的实节点数为901，ε为11%，M为100。
由于开源项目中只提供了静态的哈希值字典，并未提供此字典的搜索求解算法，本文重新设计实现了搜索哈希值字典的算法，达到了更低的ε，具体算法过程如下，设置虚拟节点数字为M=100：
（1）第一个实节点S1编号为0，通过一个ip地址加虚拟节点编号的方式获得100个不同的哈希值，保存到哈希值字典;
（2）从第二个节点开始，假设当前已经获得了n个实节点的哈希值字典，新添加一个实节点Sn 1，编号为n，其虚拟节点的位置（即哈希值）通过如下启发式算法获取：
（a）计算n 1个实节点时平均地址空间Lavg=232/（n 1）;新节点Sn 1需要获得Lavg长度的地址空间才能满足均衡性的要求，设置此节点剩余获取的地址空间为Ln 1=Lavg;
（b）计算前n个实节点每个节点管理的地址空间总数，从大到小排序;找到当前最大地址空间的实节点Smax，在其虚拟节点中找到管理地址空间最大的虚拟节点Vmax;
（c）对Vmax虚拟节点进行分裂得到V1和V2，其中V1的哈希值与Vmax一致继续作为Smax节点的虚拟节点，V2为Sn 1节点的虚拟节点，V2在满足如下原则下从Vmax中获得尽可能多的地址空间：V1、V2长度最小为1，V2长度不高于Ln 1，且Vmax失去V2地址空间后Smax节点总地址空间长度与Lavg的比值不低于R（n小于100时R为100%，n大于等于100时R为99.5%）;
（d）根据步骤c分裂得到的V2添加到哈希值字典作为Sn 1的虚拟节点，更新Smax管理的地址空间，更新Ln 1（小于等于0时，强制设置为1），重复b、c、d步骤直到Sn 1的虚拟节点数达到100;
（3）重复步骤2，直到n为901为止（即PaxosStore内置哈希值字典的最大节点数），将哈希值字典保存到文件。
通过上述搜索算法得到的哈希值字典部分数据如下表所示：
由上表看到，PaxosStore采用的一致性哈希算法，其R1一般情况下都低于1.16，节点地址空间与平均值的差异基本上都小于10%;与表1相比，此算法优于带虚拟节点的一致性哈希算法。而本文优化后求解的字典则更优于PaxosStore内置字典，R1低于1.02，并且所有节点的地址空间与平均值的差异控制在2%以内。
预生成哈希值字典的算法，是在添加一个实节点时优化虚拟节点的位置，所以在尾部添加和删除节点时能做到如表3的均衡度，但不保证在中间位置删除实节点时的均衡性。关于一致性，由于此算法与带虚拟节点的一致性哈希算法相似，采用哈希环的方式，也满足一致性的要求。
1.3谷歌跳跃一致性哈希算法
前述三种算法，都需要在内存中建立一个映射表，获取数据key访问的节点，首先需要对数据key计算哈希值，然后在映射表中查找，而查找的效率与映射表的大小密切相关。谷歌在论文[5]中提出了一个简单、快速无需依赖额外内存的一致性哈希算法。算法的核心在于将数据落在系统中每个节点的概率进行平均。假设要获得的一致性哈希算法的函数是ch（key， n），其中实节点数为n，此函数返回数据key落入的节点编号（从0开始到n-1）;要實现均衡性与一致性，函数应该具有以下的特性：
（1）当n等于1时，显然对任意key，ch（key， n）返回0;
（2）当n等于2时，需要将1/2的数据重新映射到编号为1的节点，节点间继续保持均衡;
（3）当节点数从n-1增长到n时，需要将1/n数据重映射到编号n-1的节点以继续保持均衡。
当系统增加一个节点，节点数从n-1增长到n时，数据key是否会迁移到新节点，可由概率决定，如可在函数调时产生一个随机数r（0～1之间），比较随机数r与1/n的大小，如果小于则将数据key迁入新节点，否则保留在原节点，从而满足递推公式的要求;但考虑到一致性要求，在节点数n确定时数据key必须稳定在某个节点上，对此问题论文[5]采用的方法是，在获得随机数之前使用key设置一次随机种子，随机数从而与key直接相关，进而确定了在增加节点时key是迁入新节点还是继续留在原节点，满足了一致性要求。以下的python代码展示了论文中ch（key，n）函数的实现： 算法采用遍历的方式获得数据key应落入的节点编号，算法时间复杂度为O（n）。实际上论文[5]还获得了时间复杂度是O（log（n））的算法，限于篇幅关系这里不做展开。关于算法的均衡性。由于算法没有管理地址空间的概念，本文采用随机1亿个18位字符的数据key，根据节点落入key的数量来统计R1、R2、R3（精度为小数点后三位）。
此结果与论文[5]的结果吻合，跳跃一致性哈希算法的均衡性与1.2改进的算法相当。不过此算法也存在一些弊端，僅支持在末尾添加和删除节点，不能删除中间的节点。
2总结
本文依次介绍了基本一致性哈希，带虚拟节点的一致性哈希，PaxosStore使用哈希值字典的一致性哈希以及谷歌跳跃一致性哈希。通过对比研究得出，基本一致性哈希算法存在严重的不均衡现象，通过引入虚拟节点的方式，带虚拟节点的一致性哈希均衡性有了大幅的提升;PaxosStore存储系统使用了搜索求解的哈希值字典提高了均衡度，而本文改进的搜索算法更进一步提升此算法的均衡度;谷歌跳跃一致性哈希算法使用概率模型的方法，快速且不需要额外的内存，算法在均衡度上与哈希值字典方法相当，但这两种算法也有一定的限制，只能在尾端添加和删除节点。
参考文献：
[1] Karger D，Lehman E，Leighton T，et al.Consistent Hashing and Random Trees： Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web[C]//Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing， El Paso， Texas， USA， May 4-6， 1997. ACM，1997.
[2] 聂晓文，卢显良，孟江涛，等.一类DHT算法中负载的概率分布[J].计算机应用研究，2009（10）：169-172.
[3] 杨彧剑，林波.分布式存储系统中一致性哈希算法的研究[J].电脑知识与技术，2011，7（22）：5295-5296.
[4] Zheng J，Qian L，Xu J，et al.PaxosStore： high-availability storage made practical in WeChat[J]. Proceedings of the VLDB Endowment，2017，10（12）：1730-1741.
[5] Lamping J，Veach E.A Fast，Minimal Memory，Consistent Hash Algorithm[J].Computer Science，2014.
【通联编辑：梁书】