分布式一致性Hash算法原理

一、一致性 Hash 算法

在我们常用的缓存，ES 搜索引擎，Hadoop 集群，分布式数据库等，都会用到一致性Hash算法。

也就是在分布式数据存储的场景下会用到，为什么？

以缓存为例：缓存的目的就是提升数据访问性能，缓解数据库压力。优先从缓存中获取。

但是大型互联网公司应对的是高并发，海量数据的场景，如上面图所示的单机缓存，就不能解决。高并发问题如何解决，那就用应用集群。

通过负载均衡将请求分发到集群服务器上，解决高并发带来的单个应用服务器的压力过大问题。

单机的缓存能扛得住高并发吗？

redis 的最大并发能到 10w，但是远远高于 10w怎么处理，做缓存集群。

做了缓存集群，怎么将海量的数据均匀的分发到每一个缓存节点上

1、 均匀分布方式一：hash（key）% 集群节点数。

举例：如上三个节点的集群，数据 aaa 假设 hash(aaa) = 200 ; 200%3 = 2 ；则数据放到服务器 2 上。

如果需要增加一个节点，增加一台服务器来提高性能，这个时候，有很大概率数据缓存命不中，应为 200%4 = 0 ，有多大概率命不中呢？

如图所示 0 - 11 号有 12个数字 取余数，有三个落在相同节点上，也就是缓存命中。

所以命中率为 3/12 = 1/4 也就是命不中概率 = 1 - 1/4 = 3/4；

公式为 1 - （原节点数 / 原节点数* 现节点数） = 1 - （1/现节点数）

也就是说从 99 个节点 到 100 个节点 99/100 * 100% = 99% ；

也就是基本上命不中了。

大量缓存命不中，就会去访问数据库，瞬间失去了缓存分压，数据库可能瞬间崩溃。

也就是缓存雪崩：数据库缓存导致的服务崩溃就缓存雪崩。

2、均衡分布方式二：一致性 hash 算法

a、将计算的 hash 值变为一个非负的整数，把非负的整数值做成一个圆环。

b、将节点的某一个属性 Hash 取值，根据 hash 值 将节点放到圆环上。

c、对数据的 key 求 hash 一样放到圆环上，按顺时针旋转，放到离它最近的节点上。

绿色是缓存节点。黄色是数据。

如图所示：a 数据就存放在 0 号节点上，b 就放在 1 号节点上。

新增节点会影响几何？

如图所示 ：新增节点 3 号节点，可能落在两节点中间，也可能落在节点上，落在 0 号后一点，几乎产生不了影响 ，但是落在节点 1 号前面一点，产生的影响有 1/3 ，取中值 1/6 。

也就是有 1/6 的概率命不中， 1 / （原节点数 * 2）。

新增节点能缓解其它节点的压力吗？答案是不能，只能缓解后一个节点的压力。

但是几点一定能均匀分布吗？答案是不能。如下图，这样的话，一号节点的压力远远大于其它节点。

如何能做到均衡分布，均衡缓解？

3、均衡分布方式二：一致性 hash 算法 + 虚拟节点

如图所示：给每个节点都分配一段虚拟节点，人后对节点求然后将节点均匀分布在环上，这样我们增加节点的时候，只需给新的节点分配一段虚拟节点，虚拟节店越多，分布越均衡。这样就能均匀分摊每个节点的压力。也会使得缓存不命中的概率大大降低。