更多相关内容可查看

假设有一个场景：有三万张图片，有三台服务器S0，S1，S2

要求：将这三万张图片均匀的分摊到三台服务器上，这样可以减轻服务器压力

Hash算法

比如我用图片的名称作为缓存的key，我用服务器的数量（3）进行取模，假设算出对应的余数就是对应的服务器的编号，这样我就知道这个图片具体存在哪台服务器上了

计算公式：hash（图片名称）% 机器数（3） = 余数（服务器编号）

Hash算法的缺陷

如果图片过多，我将原来三台服务器升级到四台服务器，那我的计算公式就会发生改变，我的服务器数量变为4，最后的余数就会发生改变，上述说某个余数就是跟某台服务器映射过了，所以就会导致找不到对应的key，就会造成缓存雪崩，大面积的缓存失效，从而导致系统被压垮

计算公式：hash（图片名称）% 机器数（4） = 余数（服务器编号）

一致性Hash算法

一致性Hash算法是用了Hash环的思想，是一个2 ^ 32的大小的一个环，可以理解成，这个Hash环上有 2 ^ 32次方个点

比如有三台服务器A、B、C

计算公式：hash（A的服务器编号）% 2 ^ 32 = 余数（Hash环上的一个点 >> 0 ~ 2 ^ 32-1）

通过这个计算公式可以把三台服务器分别映射到Hash环上，如图

用相同的计算公式将三万张图片也可以映射到Hash环上

计算公式：hash（a.jpg）% 2 ^ 32 = 余数（Hash环上的一个点 >> 0 ~ 2 ^ 32-1）

一致性Hash存储规则

那这个图片a.jpg存在哪台服务器上呢？

思想：是从这个a.jpa映射的点顺时针找到第一台服务器就是他所存储的服务器，就是服务器B

上述图示就是a.jpg被缓存到服务器B，b.jpg被缓存到服务器C，c.jpg被缓存到服务器A

计算公式：hash（a.jpg）% 2 ^ 32 = 余数（Hash环上的一个点 >> 0 ~ 2 ^ 32-1）

因为hash（key）值不会变 所以在存储跟查询的时候 都使用同一种方式进行计算，就能找到对应的图片缓存的位置

一致性Hash解决Hash的缺陷问题

上文所说Hash的缺陷是服务器数量改变，导致最后的值发生了改变，从而导致缓存雪崩

按上述问题，我增加一个一台服务器D，我的计算公式会将服务器D映射到Hash环上的一个位置，那么我缓存失效的部分是服务器C到服务器D的那一小部分失效(如图)，剩余这个环的其他部分不会失效，这样就会避免大面积的缓存雪崩问题

计算公式：hash（a.jpg）% 2 ^ 32 = 余数（Hash环上的一个点 >> 0 ~ 2 ^ 32-1）

一致性Hash的偏斜问题

偏斜：就是我A、B、C三台服务器通过计算公式，映射到Hash环上的节点离的很近

计算公式：hash（a.jpg）% 2 ^ 32 = 余数（Hash环上的一个点 >> 0 ~ 2 ^ 32-1）

导致的问题：

• 三万张图片分布不均匀
• 在增加一台服务器D，可能会导致大面积的缓存失效

解决：

• 增加多个服务器，可以增加分布均匀的概率
• 增加虚拟节点：虚拟节点就是A服务器拆分为多个映射到Hash环上，相当于一个假服务器，找到虚拟节点再去找真实节点，再去进行读写操作，这样就能解决偏斜的问题

一致性哈希在实际中的应用

一致性哈希在许多分布式系统中得到了广泛应用，如分布式缓存系统（如 Memcached、Redis Cluster）、分布式文件系统（如 Ceph）等。

在分布式缓存系统中，一致性哈希确保了数据在各个缓存节点之间的均匀分布，提高了缓存的命中率和系统的性能。当缓存节点数量发生变化时，一致性哈希能够有效地减少数据的迁移量，保证系统的稳定性。

在分布式文件系统中，一致性哈希用于管理数据块的存储位置，实现数据的分布式存储和负载均衡。通过虚拟节点的机制，即使文件系统中的节点数量不断变化，也能保证数据的均匀分布和高效访问。

总结

一致性哈希算法通过将数据和服务器节点映射到一个固定的哈希空间，引入虚拟节点来解决数据分布不均匀的问题，并在服务器动态增减时能够有效地减少数据迁移的开销，实现了高效的负载均衡和系统的稳定性。它是分布式系统架构设计中一种非常重要的技术，为大规模数据的存储和处理提供了可靠的解决方案。随着分布式系统的不断发展和应用场景的不断拓展，一致性哈希算法将继续发挥其重要作用。