一致性哈希算法（Consistent Hashing）

terryecnu 2015-02-04

展开全文

应用场景

这里我先描述一个极其简单的业务场景：用4台Cache服务器缓存所有Object。

那么我将如何把一个Object映射至对应的Cache服务器呢？最简单的方法设置缓存规则：object.hashCode() % 4。

Cache 0：

object.hashCode() % 4 == 0

Cache 1:

object.hashCode() % 4 == 1

Cache 2:

object.hashCode() % 4 == 2

Cache 3:

object.hashCode() % 4 == 2

看起来一切正常，考虑下面两种情况：

一：由于Cache3硬件损坏，所有Cache3上的缓存都失效了，需要把Cache3移除。

二：由于负载已经无法承担业务增涨，决定添加一台Cache服务器。

一致性哈希算法简介

一致性哈希算法是在哈希算法基础上，提出的在动态变化的Cache环境中，哈希算法应该满足的4个适应条件。

平衡性(Balance)

平衡性是指Hash的结果能够尽可能分布均匀，充分利用所有缓存空间。

单调性(Monotonicity)

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

分散性(Spread)

分散性定义了分布式环境中，不同终端通过Hash过程将内容映射至缓存上时，因可见缓存不同，Hash结果不一致，相同的内容被映射至不同的缓冲区。

负载(Load)

负载是对分散性要求的另一个纬度。既然不同的终端可以将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。

使用一致性哈希算法解决上述问题

一致性哈希算法采用一种新的方式来解决问题，不再仅仅依赖object.hashCode()本身，而且将Cache的配置也进行哈希运算。具体步骤如下：

1. 首先求出每个Cache的哈希值，并将其配置到一个0~2^32的圆环区间上。

2. 使用同样的方法求出需要存储对象的哈希值，也将其配置到这个圆环上。

3. 从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个Cache节点上。如果超过2^32仍然找不到Cache节点，就会保存到第一个Cache节点上。

新增Cache服务器

　　假设在这个环形哈希空间中，Cache5被映射在Cache3和Cache4之间，那么受影响的将仅是沿Cache5逆时针遍历直到下一个Cache（Cache3）之间的对象（它们本来映射到Cache4上）。

移除Cache服务器

　　假设在这个环形哈希空间中，Cache3被移除，那么受影响的将仅是沿Cache3逆时针遍历直到下一个Cache（Cache2）之间的对象（它们本来映射到Cache3上）。

虚拟Cache服务器

考虑到哈希算法并不是保证绝对的平衡，尤其Cache较少的话，对象并不能被均匀的映射到 Cache上。为了解决这种情况，Consistent Hashing引入了“虚拟节点”的概念： “虚拟节点”是实际节点在环形空间的复制品，一个实际节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在哈希空间中以哈希值排列。

仍以4台Cache服务器为例，在下图中看到，引入虚拟节点，并设置“复制个数”为2后，共有8个“虚拟节点”分部在环形区域上，缓解了映射不均的情况。