一致性哈希算法常用于负载均衡中要求资源被均匀的分布到所有节点上，并且对资源的请求能快速路由到对应的节点上。先从一个分布式缓存开始说起。

分布式缓存

      如上图展示了一个分布式系统架构，为了应对日益剧增的数据访问我们通常会使用Redis作为缓存，减轻底层数据库的压力。最简单的缓存策略即将热点数据保存到所有的Redis中，每次请求时则随机选择一个Redis节点获取数据，但是这种策略会引发以下问题;

• 数据冗余。
• 若某个数据在其中一个Redis节点中存在，但是在其他节点中不存在，由于是随机选择一个节点进行数据的获取，可能导致数据获取不到。

      为解决以上问题我们可以使用Hash算法：

1. 对每次的数据访问都求得Hash值；
2. Hash值%N（N: 节点的个数），求得此次访问请求哪个节点，即为index

      引入Hash算法在系统稳定的情况下解决了刚开始的问题，但是如果Redis集群一旦扩容或缩容，这将直接影响index的计算（N变化了）,大量的数据访问会重定向到其他服务器中，造成缓存命中率下降，大大影响性能。

一致性哈希算法

简单的一致性Hash算法

      先介绍一个简单版本的一致性Hash算法：

• 将Hash值不再模节点的个数，而是模360，即最多有360个位置；
• 将360分配给N个节点，每个节点将负责一段区间；
• 将区间分配信息记录在数据表上；
• 新增加一个节点时，通过数据表匀走相邻两台机器的一部分数据。

      若现在在添加一个节点Node3，采用均分则会涉及三个节点的数据迁移，所以选择两块相邻的且占比较大的区间(数据更多)进行三等分，如此只涉及了两个节点的数据迁移：

缺点

• 数据分布不均
• 对老节点迁移压力过大

一致性Hash算法

      简单的一致性Hash算法依旧有种种问题，那如何做到副作用更小呢？

虚拟节点

      首先，我们将复杂问题简单化，将3个节点分割整个环(360)的过程从Hash转换成一个【撒豆子问题】。emmm，这个名字自己取的。如果我们手中只有三个豆子随机的散在一个环上，将其三等分，我们有极大的概率得到一个不均匀的分配方式。

      通过顺时针查找的方式获取访问的节点：

      幸运的是，我们除了有三个豆子(红豆、绿豆和黄豆)，我们还有三种颜色的珠子各1000颗，我们将这些珠子(虚拟节点)作为一个中间层，各撒1000颗珠子，如此，将环均分的概率大多了。如下图所示为一次虚拟节点的分布，相同颜色的区间表示一个节点。

算法总结

• 将整个Hash区间看成一个环，大小为0~2^32-1；
• 将节点和数据都看作环上的一个点；
• 每个节点都对应1000个虚拟节点，每个虚拟节点对应Hash环上的一个点；
• 每新加入一台节点就在环上随机撒上1000个虚拟节点；

• 在计算某个Key所在的服务器时：

  • 首先计算该Key的Hash值，对应环上的一个点；
  • 顺时针找到第一个虚拟节点；
  • 该虚拟节点对应的机器就是该Key所在的真实数据节点。
• 新加入一台机器时，新添加的1000个虚拟节点各自向顺时针的下一台服务器索取逆时针的一段区间内的数据(不需要全部拿过来)

版权属于：带翅膀的猫

本文链接：https://www.chengpengper.cn/archives/165/

转载时须注明出处及本声明