一致性哈希与分布式系统

一致性哈希的应用

负载均衡算法

加权轮询：把外界的请求轮流发给内部计算节点，如果内部节点的硬件配置不同，可以分配不同的权重。要求每个节点都可计算。

但是对于 分布式系统 来说， 轮询就起不到作用了。因为每个机器存储的数据不同。

传统 hash 算法

使用取模运算：hash = key % n 来寻找对应机器。

但是对于 扩容 来说，就有些灾难了。
比如：原来有三个机器：n = 3，现在增加一个机器 n = 4，导致计算的 hash 值与真是对应机器编号不一致。例如： key = 6，原来计算的 hash 值为 0，现在计算 hash 值为 2，导致需要将大量的数据进行迁移。

一致性 hash

通过 hash 环实现，起点为0，终点为2^32 - 1。

1. 先映射数据。
2. 映射服务器。
3. 将数据缓存到顺时针查找距离最近的服务器上。

但是由于数据分布不均衡，导致大量的数据缓存在同一台服务器上，如果该服务器失效，将所有的数据缓存到下一台服务器上，会导致雪崩效应。

虚拟节点

将每台服务器虚拟为一组服务器，均匀放置到 hash 环上，节点变多，分布就相对均匀。
需要两层映射，先映射虚拟服务器，再映射到实际服务器上。