一致性Hash算法

在分布式数据分区时使用hash分区最容易的方案就是hash取模。

这样可以满足数据的均匀分配，但是这个算法的容错性和扩展性都比较差，比如删除一个节点过后，所有key都需要重新映射，显然这样成本太高。

所以我们需要一个算法用来解决：如何将数据均分分散到各个节点中，并且尽量的在加减节点时能受影响的数据最少。这就是下面要讲的一致性hash算法

一致性hash算法

一致性hash算法将所有的哈希值组织成一个抽象的圆环，这些输出值可以均匀的映射到哈希环上面。
假设hash()函数输出值在 [0, 11] 范围之间。则如图所示：

image.png

之后将分布式系统的各个节点放置到这个环上，假设系统有2个节点N1，N2，N3 则如下图所示：

image.png

将需要存储的key计算出hash值，再将其映射到hash环上，假设这里有3个key a，b，c 则计算出来的hash值分别为1、5、9，则数据映射到hash环上后如图所示：

image.png

那么数据具体分区到哪个节点上呢？在一致性hash算法中，数据存储按照顺时针方向遇到第一个节点上，如图所示：

image.png

接下来，假设我们向集群中添加一个节点会发生什么？假设，集群此时要添加一个N4，并添加到如图所示的位置，那么按照顺时针计算的方法，只需要将存储到N2上的a 转移到N4上。

image.png

可见，相比于普通的哈希分区算法在添加或删除节点时会导致大量的映射失效，一致性hash对于节点的增删只需要重新分配哈希环上一部分数据，对比起来，拥有更好的可扩展性和可管理性，但是一致性hash仍然有明显的缺点，那就是当系统节点太少时，容易产生数据分布不均匀的问题，以及当一个节点发生异常，需要下线时，该节点的数据会全部转移到下一个顺时针的方向的节点上，这回导致该节点负载增加，解决这个问题的办法是引入虚拟节点。

虚拟节点

虚拟节点并不是真实存在的物理服务器，一个物理节点并不再对应 hash 环上一个点，而是有可能对应多个节点。

image.png

引入虚拟节点后，数据分布就会越均匀。同时如果系统中有不同配置，不同性能的机器，那么虚拟节点也很有用，例如一台物理机器的性能是其他机器的2倍，那么可以让这台机器映射出2倍于其他机器的虚拟节点数。

代码实现

TODO

---

参考资料

1. 《深入理解分布式系统》
2. https://crossoverjie.top/2018/01/08/Consistent-Hash/
3. http://blog.chinaunix.net/uid-20498361-id-4303232.html