未完待续

一、引出

假设有 100W 的数据，100 个存储节点，如何分配呢？
通常的方法是哈希，数据存储到第 个节点上。
可是，当新增或删除节点时，需要对所有的数据重新映射，可能发生大规模的数据迁移。这对于分布式系统而言，是一个很严重的问题。

一致性哈希算法就是为了解决这个问题产生的，即『当slot数发生变化时，能够尽量少的移动数据』

维基百科：一致哈希是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对 K/n个关键字重新映射，其中K是关键字的数量， n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

二、实现

基本实现

实现原理：
1）将 0~最大正整数形成一个环
2）计算每个节点的哈希值，即 hash(node)，并落入环上某个位置
3）计算数据的哈希值，即 hash(key)，并落入环上某个位置。
4）数据在环上的位置顺时针找离它最近的节点，作为该数据的存储节点

可理解成：每个节点负责某个范围内的哈希值的数据。比如，当哈希值在 [hash(node1), hash(node2)] 内的数据，落入 node2。

当节点变化，仅影响该节点顺时针方向的下一个节点，具体情况如下：

• 当删除一个节点时，该节点上的数据迁移到该节点顺时针方向的下一节点上
• 当新增一个节点时，该节点顺时针方向的下一节点部分数据迁移到该节点上。

改进一：加入虚拟节点

目的：为了使得每个节点的负载尽量均衡

参考文献

[1] 一致性Hash原理_憧憬的专栏-CSDN博客
[2] 一致性哈希算法的理解与实践 | Yikun
[3] 一致性hash算法及java实现Java青鱼入云的博客-CSDN博客