一致性哈希

一致性哈希

哈希算法。因为对同一个关键字进行哈希计算，每次计算都是相同的值，这样就可以将某个 key 确定到一个节点了，可以满足分布式系统的负载均衡需求。

哈希算法最简单的做法就是进行取模运算，比如分布式系统中有 3 个节点，基于 hash(key) % 3 公式对数据进行了映射。

当增加服务或者减少服务节点时，就会涉及迁移数据了

一致性哈希算法就很好地解决了分布式系统在扩容或者缩容时，发生过多的数据迁移的问题。

一致哈希算法也用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2^32 进行取模运算，是一个固定的值。

一致哈希算法是对 2^32 进行取模运算的结果值组织成一个圆环，就像钟表一样，钟表的圆可以理解成由 60 个点组成的圆，而此处我们把这个圆想象成由 2^32 个点组成的圆，这个圆环被称为哈希环

一致性哈希要进行两步哈希：

所以，一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上。

问题来了，对「数据」进行哈希映射得到一个结果要怎么找到存储该数据的节点呢？

答案是，映射的结果值往顺时针的方向的找到第一个节点，就是存储该数据的节点。

在一致哈希算法中，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。致性哈希算法并不保证节点能够在哈希环上分布均匀。

一致性哈希负载均衡算法就像是钟表，它的过程就有点儿像你的朋友约你吃火锅，说下一个整点到重庆火锅店集合。那么你看一下现在的时间，是下午三点四十五分，那么自然下一个整点就是下午四点了。

如果节点较少就会出现节点分布不均衡造成数据倾斜问题。

为了解决这种数据存储不平衡的问题，一致性哈希算法引入了虚拟节点机制，即对每个节点计算多个哈希值，每个计算结果位置都放置在对应节点中，这些节点称为虚拟节点。

对于数据定位的hash算法仍然不变，只是增加了虚拟节点到实际节点的映射。

Nginx 的一致性哈希算法，每个权重为 1 的真实节点就含有160 个虚拟节点。

另外，虚拟节点除了会提高节点的均衡度，还会提高系统的稳定性。当节点变化时，会有不同的节点共同分担系统的变化，因此稳定性更高。

带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景

数据定位：当需要存储或检索数据时，数据项会被计算出一个哈希值。然后在哈希环上找到顺时针方向的第一个虚拟节点，该虚拟节点对应的物理节点就是数据应该存储或检索的位置。

‣