一致性Hash

一致性Hash

1  简单介绍

Hash又称为哈希算法，哈希算法哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的。

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

2  一致性Hash的特性

一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个特性：均衡性、单调性、分散性、负载。

2.1  均衡性(Balance)

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

2.2  单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧缓冲集合中的其他缓冲区。

2.3  分散性(Spread)

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

2.4  负载(Load)

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

3  分布式Hash

在高并发的缓冲情况中，单台机器的已经无力负载这么高的缓存，必须引入分布式缓存机制，需要把缓存的内容分布到不同的实体机器上，如何把key映射到不同的机器？可以利用Hash算法，把实体机器当做是桶，采用和HashMap实现一样的思路，通过和实体机器的数量取模，映射到不同的实体机器。分布式缓存可以解决高并发的缓存情况。

3.1  分布式缓存存在的问题

1、如果一台实体机器挂了，数据将无法得到恢复。

2、新增一台实体机器，桶的数量将会改变，所有的Key将重新映射，导致原来缓存的无法通过key获取，这是对高并发是致命的，所有的请求将不再经过任何缓存，服务器面临崩溃。

3、新增一台实体机器，老的数据依然还存在旧的缓存中，并且不会被用到，浪费存储空间。

针对这些上面的这些问题，引入一致性Hash势在必行的。

3.2  分布式中的一致性Hash

一致性Hash是这样一种 hash算法，简单的说，在移除或添加一个节点（实体机器或者实体机器对应的IP）时，它能够尽可能小的改变已存在 key 映射关系，尽可能的满足均衡性、单调性、分散性、负载等要求。

3.3  一致性Hash算法映射

3.3.1  Hash环路空间

Hash算法来将对应的key哈希到一个具有2^32次方个桶的空间中，即0~(2^32)-1的数字空间中（数据量不够，2^64也行）。可以将这些数字头尾相连，想象成一个闭合的环形。

3.3.2  缓存数据映射到Hash环空间

假如有四个缓存数据需要映射，通过hash函数计算出的Hash值key 在环上的分布。

伪代码:

Hash(object1) = key1

Hash(object2) = key2

Hash(object3) = key3

Hash(object4) = key4

如下图：

3.3.3  缓存节点服务器映射到Hash环空间

假设我们有三台缓存服务器节点，命名为：Cache A、Cache B、Cache C通过Hash函数计算出的Hash值key 在环上的分布。

伪代码：

Hash(CacheA) = keyA

Hash(CacheB) = keyB

Hash(CacheC) = keyC

如下图：

 

3.3.4  缓存数据映射到缓存节点服务器

在这个Hash环形空间中，如果沿着顺时针方向从缓存对象的 key 值出发，直到遇见一个节点Cache，那么就将该对象存储在这个节点Cache上，因为缓存对象和节点Cache的 hash值是固定的，因此这个 缓存Cache必然是唯一和确定的。

映射关系：

1、object1将被存储到节点Cache A。

2、object2和object3将被存储到节点Cache C。

3、object4将被存储到节点Cache B。

如下图：

 

3.3.5  移除一个缓存节点

假设节点Cache B挂掉了，根据上面的映射方法，受影响的将仅是那些沿节点Cache B 逆时针遍历直到下一个Cache( Cache A)之间的对象，即是本来映射到Cache B上的那些对象。

改变映射关系：

1、仅需要变动对象object4 ，将其重新映射到Cache C。

如下图：

 

3.3.6  新增一个缓存节点

假设添加一台新的节点Cache D的情况，在这个环形hash空间中，节点Cache D被映射在对象object2 和object3之间。

改变映射关系：

1、  仅需要变动对象object2，将其重新映射到Cache D。

如下图：

3.3.7  均衡分配数据

在移除和增加缓存节点中，移除了节点Cache B，结果object4也转移到Cache C，这时节点Cache A只有object1，而节点CacheC有object2、object3、object4，服务器压力剧增，分布不平衡。为了解决这种情况， 一致性Hash引入了“虚拟节点”的概念。

虚拟节点(virtual node)是实际节点在Hash空间的复制品。一实际个节点对应了若干个虚拟节点，若干个对应的是复制个数，虚拟节点在Hash空间中以Hash值排列。

以部署节点Cache A和节点Cache C的情况为例，引入虚拟节点，并设置复制个数为2 ，这就意味着一共会存在4个虚拟节点。

假设理想情况：

1、  节点Cache A1、Cache A2代表了节点Cache A。

2、  节点Cache C1、Cache C2代表了节点Cache C。

如下图：

 

映射关系：

1、objec1 -> Cache A2。

2、objec2 -> Cache A1。

3、objec3 -> Cache C1。

4、objec4 -> Cache C2。

对象object1和object2都被映射到了节点 Cache A上，而object3和object4映射到了 节点Cache C 上，均衡性有了很大提高。

3.3.8  整体的映射关系

引入虚拟节点后，映射关系就从“对象 -> 节点”转换到了“对象 -> 虚拟节点”。

如下图：

虚拟节点的Hash计算可以采用对应节点的 IP 地址加数字后缀的方式。

例如：节点Cache A的IP地址值为10.1.53.1。

引入虚拟节点之前：

Cache A的Hash值：Hash(“10.1.53.1”)。

引入虚拟节点之前：

虚拟节点Cache A1值：Hash(“10.1.53.1@1”)。

虚拟节点Cache A2值：Hash(“10.1.53.1@2”)。

4  一致性Hash的局限性

4.1  集群单个节点出现故障时，该节点下的数据全部不可用

在移除一个缓存节点时，该节点的key是转移到了其它的节点，事实上数据已经丢失了。这个也不是该算法所能解决的范畴，只能通过主-从模式，对该主节点做从节点备份，一旦主节出现故障时，从节点能自动接替主节点，从而该节点下的数据不至于丢失。

4.2  增加节点的数据没有重新分配到其他节点

在增加一个缓存节点时，只有Key转移到新增节点上，这些转移的key对应的数据也丢失了。这个算法也解决不了，只能通过转移数据，最好能做到新增一个节点时，数据自动分配。
5  一致性Hash应用

一致性Hash，既可以在客户端实现，也可以在中间件上实现。

5.1  客户端应用

在客户端实现中，当客户端初始化的时候，需要初始化一张预备的节点的映射表这有一个缺点，假设有多个客户端，当映射表发生变化的时候，多个客户端需要同时拉取新的映射表。

5.2  中间件应用

中间件可以是代理（proxy），中间件的实现方法，在客户端和节点之间加多一个代理，代理经过哈希计算后将对应某个 key 的请求分发到对应的节点，一致性哈希算法就在中间件里面实现。

5.3  twemproxy-Redis应用案例

twemproxy 是 twitter 开源的一个轻量级的后端代理，兼容 redis/memcache 协议，可用以管理 redis/memcache 集群。

twemproxy 内部有实现一致性哈希算法，对于客户端而言，twemproxy 相当于是缓存数据库的入口，它无需知道后端的部署是怎样的。twemproxy 会检测与每个节点的连接是否健康，出现异常的节点会被剔除；待一段时间后，twemproxy 会再次尝试连接被剔除的节点。

 

通常，一个 Redis 节点池可以分由多个 twemproxy 管理，少数 twemproxy 负责写，多数负责读。twemproxy 可以实时获取节点池内的所有 Redis 节点的状态，但其对故障修复的支持还有待提高。解决的方法是可以借助 redis sentinel 来实现自动的主从切换，当主机 down 掉后，sentinel 会自动将从机配置为主机。而 twemproxy 可以定时向 redis sentinel 拉取信息，从而替换出现异常的节点。

5.4  Redis官方版本支持的集群

最新版本的Redis也开始支持集群特性了，再也不用靠着外援过日子了。基本的思想是，集群里的每个Redis都只存储一定的键值对，这个“一定”可以通过默认或自定义的哈希函数来决定，当一个Redis收到请求后，会首先查看此键值对是否该由自己来处理，是则继续往下执行；否则会产生一个类似于 http 3XX 的重定向，要求客户端去请求集群中的另一个 Redis。

Redis每一个实例都会通过遵守一定的协议来维护这个集群的可用性，稳定性。

 

 

 

 

 

参考链接：

http://www.cnblogs.com/color-my-life/p/5799903.html

http://www.cnblogs.com/coser/archive/2011/11/27/2265134.html