一致性Hash算法的随笔

常见的哈希算法

我们以往使用哈希算法，例如 JDK 1.8 中的HashMap，插入新的key需要确定哈希树桶中的索引位置，是先取key的hashCode，再高位运算，最后取模运算得到索引位。HashMap的深入了解

这样的算法在确定索引长度的情况下是没有问题的，但是如果索引树桶中有索引不能使用或者需要添加新的索引位置时，就要重新计算所有的key值。

一致性Hash算法

一致性Hash算法应用在分布式系统中，以Redis为例，当Redis中保存的数据到一定量时，需要对Redis进行分区，将数据按照一定规则，例如使用hash算法分布到不同的Redis中。但这种算法有个缺陷，如果有一台Redis故障需要移除，或者增加新的Redis实例，就需要重新计算hash并移动位置。为了解决这个问题，就产生了一致性Hash算法。

和哈希算法一样，一致性Hash算法也是取模运算，哈希算法是对固定长度进行取模，一致性Hash算法是对2^32 取模，此时哈希桶不再是一个固定长度的数组，而是一个哈希环，正上方为0，按照顺时针方向递增直到2^32-1。

Hash环

接下来就是对每个Redis所在的服务器IP或者主机名作为关键字进行hash运算，将得到的hash值作为哈希环上的位置。例如现在有3个Redis实例，他们经过hash运算在环上的位置如下：

Hash环2

最后对Redis中的key进行hash运算，得到在哈希环上的位置。从该位置沿环顺时针方向，遇到的第一个Redis实例就是所在的服务器。

Hash环3

一致性Hash算法的容错性和可扩展性

假设其中一台Redis不可用，受影响的仅仅是这台Redis前面的Redis，而对其他Redis没有影响；同理如果在系统中新增一台Redis，只有新增位置和其后面的Redis之间的数据会受影响，其他数据没有影响。

所以，一致性Hash算法对于节点的增减都只需要重定位哈希环中的一小部分数据，具有较好的容错性和可阔扎逆行。

Hash环数据倾斜的问题

一致性Hash算法在Redis节点太少时，容易因为节点分布不均匀造成数据倾斜。

Hash环4

为了解决数据倾斜问题，一致性Hash算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个Redis节点，称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。在实际应用中，虚拟节点通常为32或者更多，解决了节点过少产生的数据倾斜问题。