【修真院Java小课堂】什么是一致性哈希

开场语：

大家好，我是IT修真院北京分院第32期的学员廖友，一枚正直纯洁善良的Java程序员，今天给大家分享一下，修真院官网Java任务五，深度思考中的知识点——什么是一致性哈希

一、背景介绍：

一致性哈希算法在1997年由麻省理工学院提出(参见扩展阅读[1])，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用。

二、知识剖析：

1、一致性哈希算法原理

研究过memcached缓存数据库的人都知道，memcached服务器端本身不提供分布式cache的一致性，而是由客户端来提供，具体在计算一致性hash时采用如下步骤： 

（1）首先求出memcached服务器（节点）的哈希值，并将其配置到0～2‘32的圆（continuum）上。 

（2）然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。 

（3）然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器，就会保存到第一台memcached服务器上。 

 3、一致性哈希算法特性之平衡性 

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。 

 4、 一致性哈希算法特性之单调性 

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x = (ax + b) mod (P)，在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。

 5、一致性哈希算法特性之分散性

在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

 6、 一致性哈希算法特性之负载 

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。  

三、常见问题：

xmemcached本身不具备分布式功能，那它是如何实现分布式应用的呢？

四、解决方案：

xmemcached的分布式实现是由客户端实现的，客户端采用了一致性哈希算法，从而能够计算出每条记录的存储位置。

五、编码实战

六、拓展思考：

解决数据分布的常用映射方式 Hash映射：

通过哈希算法将key映射到有限值上，例如crc16(key)%16384 范围映射：对key的值空间划分范围，根据数据ID缓存到对应区域 Hash与范围结合：典型算法为一致性哈希算法，统一对key进行哈希运算求得哈希值，通过对整个哈希空间划分范围，划分的节点为用来存储数据的缓存节点，然后将数据存储到对应的存储空间中。

七、参考文献：

[1]http://www.zsythink.net/archives/1182/

[2]《深入分布式缓存》 

[3]https://www.cnblogs.com/lpfuture/p/5796398.html

八、更多讨论：

Q1：为什么需要一致性哈希

A1：在解决数据分布的问题上，若采用简单的哈希取模方式，由于模是与缓存服务器数据量绑定的，当对缓存服务器进行增减时，模也要变化，这会导致以前的数据全部失效；若采用一致性哈希算法，由于模固定，所以对服务器进行增减时不会导致全部数据失效，受影响的部分只是一小部分。

Q2：一致性哈希运用场景有哪些

A2：xmemcached的客户端是使用一致性哈希算法来解决数据分布问题的，redis默认采用crc16(key)%16384解决数据分布问题，但我们也可以将一致性哈希应用在redis的数据分布上，具体怎么选择看应用场景 。

Q3：使用虚拟节点技术解决平衡性问题，那么数据一定是均匀分布在各个服务器上吗？

A3：这个不一定，使用虚拟节点技术只能说能够尽量使节点均匀分布在哈希环上，但不能绝对均匀，若想提高平衡性，可以多虚拟出几个节点。

九、结束语：

今天的分享就到这里啦，欢迎大家点赞、转发、留言、拍砖~