一致性hash

一致性Hash算法

概念：先构造一个长度为232的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 232-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 232-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。

        这种算法解决了普通余数Hash算法伸缩性差的问题，可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。

        当然，万事不可能十全十美，一致性Hash算法比普通的余数Hash算法更具有伸缩性，（普通的余数hash算法增加或者减少机器的时候容易造成大量缓存失效从而倒置雪崩）但是同时其算法实现也更为复杂，本文就来研究一下，如何利用Java代码实现一致性Hash算法。在开始之前，先对一致性Hash算法中的几个核心问题进行一些探究。

一致性hash算法的线上应用

 　　首先我们来看下String的hashCode()的方法计算出来的hash值代码如下：

        代码省略。

　　我们在做集群的时候，集群点的IP以这种连续的形式存在是很正常的。看一下运行结果为：

        运行结果省略。

hash值的区间基本大致是-2052839345--2012725363这样的区间，并且有负数的存在，当然我们可以通过取绝对值的方法规避负数。最重要的是一致性hash的区间是[0,232-1]中有4294967296个数字，我们的hashcode方法的hash值远远小于一致性hash区间这样会倒置数据严重的不匀均可能有的节点会存在百分之90的数据。综上，String重写的hashCode()方法在一致性Hash算法中没有任何实用价值，得找个算法重新计算HashCode。这种重新计算Hash值的算法有很多，比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等，其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法，用别的Hash算法也可以，比如FNV1_32_HASH算法的计算效率就会高一些。

一致性Hash算法实现版本1：不带虚拟节点

使用一致性Hash算法，尽管增强了系统的伸缩性，但是也有可能导致负载分布不均匀，解决办法就是使用虚拟节点代替真实节点，第一个代码版本，先来个简单的，不带虚拟节点。想象一下一个环上只有三点节点，很容就分布的不均匀。

下面来看一下不带虚拟节点的一致性Hash算法的Java代码实现：

运行结果如下：

       代码省略具体的代码实现在码云上。

　看到经过FNV1_32_HASH算法重新计算过后的Hash值，就比原来String的hashCode()方法好多了。从运行结果来看，也没有问题，三个点路由到的都是顺时针离他们Hash值最近的那台服务器上。最重要的是这样的一致性算法可以解决扩展性差的问题，但是这样的一致性算法是不能在生产环境使用的。因为这样的算法是负载不均匀的。

使用虚拟节点来改善一致性Hash算法

 　

比如说有Hash环上有A、B、C三个服务器节点，分别有100个请求会被路由到相应服务器上。现在在A与B之间增加了一个节点D，这导致了原来会路由到B上的部分节点被路由到了D上，这样A、C上被路由到的请求明显多于B、D上的，原来三个服务器节点上均衡的负载被打破了。某种程度上来说，这失去了负载均衡的意义，因为负载均衡的目的本身就是为了使得目标服务器均分所有的请求。

解决这个问题的办法是引入虚拟节点，其工作原理是：将一个物理节点拆分为多个虚拟节点，并且同一个物理节点的虚拟节点尽量均匀分布在Hash环上。采取这样的方式，就可以有效地解决增加或减少节点时候的负载不均衡的问题。

想象一下我们把一个节点虚拟化成200个节点使他更加的分散在hash环上这样我们就能解决负载不均衡的问题。

在理解了使用虚拟节点来改善一致性Hash算法的理论基础之后，就可以尝试开发代码了。编程方面需要考虑的问题是：

一个真实结点如何对应成为多个虚拟节点？

虚拟节点找到后如何还原为真实结点？

至于一个真实结点对应分成多少个虚拟结点的问题，经过大量的测试一般是150-200个虚拟结点会达到较好的效果，具体的实现还需要根据真实节点去测试。那么虚拟节点可以为真实节点+后缀名的方式实现那么还原也比较容易。

下面代码实现如下：

代码省略具体的代码实现在码云上。

运行代码可以查找到虚拟节点的hash值，求出来数据的key的hash值来找到对应的节点。这样我们就能解决了扩展差和负载差的问题。