一致性哈希

Distributed Hash Table（DHT） 是一种哈希分布方式，其目的是为了克服传统哈希分布在服务器节点数量变化时大量数据迁移的问题。

一致性 hash 算法解决了分布式环境下机器增加或者减少时，简单的取模运算无法获取较高命中率的问题。

通过虚拟节点的使用，一致性 hash 算法可以均匀分担机器的负载，使得这一算法更具现实的意义。

一致性 Hash(Consistent Hashing)原理剖析

1 基本思想

key 与 机器节点 都 hash 到环上。

1.1 取 0~2^32-1 的环

1.2 将对象放置到 Hash 环

使用 hash 函数计算这 4 个对象的 hash 值

1.3 将机器放置到 Hash 环

使用同样的 hash 函数，将机器也放置到 hash 环上。

1.4 为对象选择机器

将对象和机器都放置到同一个 hash 环后，在 hash 环上顺时针查找距离这个对象的 hash 值最近的机器，即是这个对象所属的机器。

1.5 处理机器增减的情况

增加机器 c4，只有机器 c3 与 c4 之间的对象需要重新分配新的机器。

机器 c1 下线，只有原有被分配到机器 c1 对象需要被重新分配到新的机器。

2 虚拟节点

一致性 hash 解决命中率问题，虚拟节点解决 key 的分布均匀问题（负载均衡）

1. 使用一般的 hash 运算，服务器的映射地点的分布非常不均匀；
2. 使用虚拟节点的思想，为每个物理节点（服务器）在圆上分配 100～200 个点。
3. 这样就能抑制分布不均匀，最大限度地减小服务器增减时的缓存重新分布。