一致性哈希算法

一致性hash算法在分布式系统里面使用比较广，我也只是听说过这个概念，今天看到一个一致性hash开源库，随手写篇文章，记录下吧。

假如我们使用普通的哈希方式来处理负载均衡，到目标机器的映射使用的算法为：

hash(o) mod n (n表示机器的总数)

如果需要增加或减少一台机器的时候，算法就变为 hash(o) mod (n + 1) / hash(o) mod (n - 1)

不仅需要重新编写代码，当服务器做了大量变更，大量的o会重定向不同的服务器而导致了缓冲不被命中，所以此时，就提出了一致性hash算法。

一致性哈希算法

简单的说，哈希函数将o映射到 0 ~ 2^32 - 1的值区间，将这些数字头尾相连，然后将它们组织成一个闭合的圆环。如图一所示：

要实现一致性哈希算法，思路就是下面2个步骤：

将数据通过一定的hash算法映射到环上

hash(object1) = key1;
…
…
hash(object4) = key4;

将机器通过哈希算法映射到环上

假如有三台cache机器，A，B，C，一般情况下hash计算是采用机器的IP或者机器唯一的别名作为输入值。

hash(cache A) = key A;
…
…
hash(cache B) = key C;

然后顺时针方向计算，将所有object（数据）存储到离自己最近的机器上。
如上图所示：object1将存储到 cache A，object2和object3将会存储到 cache C，object4将会存储到 cache B。

添加或删除机器

假如B 机器被移走或者坏掉了，根据顺时针存储到最近的机器的特性，之前存储到B机器的objects（数据）将会转到C机器（因为顺时针离C最近），如下所示：

同样添加了新机器也是同理。

虚拟节点

一致性哈希算法在服务节点太少或不均匀时，容易造成数据倾斜问题，导致平衡性问题。hash算法不能保证平衡的，在一致性哈希算法中，为了尽可能的满足平衡性，引入了虚拟节点。

虚拟节点是实际节点（机器）在hash空间的复制品，一个实际节点对应了若干了虚拟节点，当我们增加一个机器时，我们在环里增加几个其虚拟节点，当我们移掉它时，我们把其虚拟节点从环中一块移除掉。实际上就是对一个机器节点计算多次哈希，每个计算结果位置都放置一个此服务节点，成为虚拟节点，具体做法可以在机器IP或主机名的后面添加编号来实现，如Node1-1，Node1-2。

例如，有两台机器A和C，引入了虚拟节点后，就会有4个节点，分布更均匀，如下图所示所示：