一致性 Hash 算法

一致性hash算法：

在高并发，高可用系统中，对技术的选型和设计也很重要。

背景：

哈希算法： 就是对一个对象进行哈希获得的散列值。其中，值越分散，哈希的碰撞率也就越低，性能也就越好。

一致性哈希算法在分布式高可用系统中场景的很多，比如分布式缓存存值问题，以redis为例，当拥有多台redis实例的时候可以利用redis自带的主从复制功能实现高可用（主写从读）。但是，一台服务器是有性能瓶颈的，当一台服务器存入的数据量大于该服务器性能瓶颈的时候，吞吐量会急剧下降，服务器会发生进程坏死的情况，所以这里使用多台作为例子，这里用下图方式进行分布：

这里的做法是用每台服务器的ip或者实例name作为key进行哈希取模

上图中，假设我们查找的是”a.png”，由于有4台服务器（排除从库），因此公式为hash(a.png) % 4 = 2 ，可知定位到了第2号服务器，这样的话就不会遍历所有的服务器，大大提升了性能！

Hash 取模

随机放置就不说了，会带来很多问题。通常最容易想到的方案就是 hash 取模了。我们可以将传入的 Key 按照 index = hash(key) % N 这样来计算出需要存放的节点。其中 hash 函数是一个将字符串转换为正整数的哈希映射方法，N 就是节点的数量。这样可以满足数据的均匀分配，但是这个算法的容错性和扩展性都较差。比如增加或删除了一个节点时，大量的请求会进入到数据库 可能会引发系统雪崩。

那么问题又来了，这个问题就比较严重了！ 动态的加机器会导致所有的key失效？

这里就引入了一致性哈希算法：

将所有的哈希值构成了一个环，其范围在 0 ~ 2^32-1。

之后将各个节点散列到这个环上，可以用节点的 IP、hostname 这样的唯一性字段作为 Key 进行 hash(key)，散列之后如下：

之后需要将数据定位到对应的节点上，使用同样的 hash 函数 将 Key 也映射到这个环上。

这样按照顺时针方向就可以把 k1 定位到 N1节点，k2 定位到 N3节点，k3 定位到 N2节点。

容错性

这时假设 N1 宕机了：

依然根据顺时针方向，k2 和 k3 保持不变，只有 k1 被重新映射到了 N3。

这样就很好的保证了容错性，当一个节点宕机时只会影响到少少部分的数据。

拓展性

当新增一个节点时:

在 N2 和 N3 之间新增了一个节点 N4 ，这时会发现受印象的数据只有 k3，其余数据也是保持不变，所以这样也很好的保证了拓展性。

虚拟节点

到目前为止该算法依然也有点问题:当节点较少时会出现数据分布不均匀的情况：

这样会导致大部分数据都在 N1 节点，只有少量的数据在 N2 节点。

为了解决这个问题，一致哈希算法引入了虚拟节点。将每一个节点都进行多次 hash，生成多个节点放置在环上称为虚拟节点:

计算时可以在 IP 后加上编号来生成哈希值。这样只需要在原有的基础上多一步由虚拟节点映射到实际节点的步骤即可让少量节点也能满足均匀性。

本文参考：https://www.jianshu.com/p/0bc075473eb5