乐趣区

关于后端:系统设计什么是一致性哈希一致性哈希是如何工作的如何设计一致性哈希

如果你有 n 个缓存服务器,一个常见的负载平衡形式是应用以下的哈希办法:

服务器索引 = 哈希(键) % N,其中 N 是服务器池的大小。

让咱们通过一个例子来阐明这是如何工作的。如表 5 - 1 所示,咱们有 4 台服务器和 8 个字符串键及其哈希值。

为了获取存储某个键的服务器,咱们执行模运算 f(键) % 4。例如,哈希(键 0) % 4 = 1 意味着客户端必须分割服务器 1 来获取缓存的数据。图 5 - 1 展现了基于表 5 - 1 的键的散布。

AI 不会取代你, 应用 AI 的人会。欢送关注我的公众号:更 AI。以程序员的视角来看 AI 能带给咱们什么~

当服务器池的大小固定且数据分布平均时,这种办法工作得很好。然而,当新的服务器被增加,或者现有的服务器被移除时,就会呈现问题。例如,如果服务器 1 离线,服务器池的大小就变成了 3。应用雷同的哈希函数,咱们失去的键的哈希值是雷同的。然而利用模运算会因为服务器数量缩小了 1 而失去不同的服务器索引。咱们利用 哈希 % 3 失去的后果如表 5 - 2 所示:

图 5 - 2 展现了基于表 5 - 2 的新键散布。

如图 5 - 2 所示,大多数键都被重新分配了,而不仅仅是那些最后存储在离线服务器(服务器 1)中的键。这意味着,当服务器 1 离线时,大多数缓存客户端将连贯到谬误的服务器来获取数据。这导致了一场缓存未命中的风暴。一致性哈希是一种无效的技术来缓解这个问题。

一致性哈希

援用自维基百科:” 一致性哈希是一种非凡的哈希,使得当哈希表大小扭转且应用一致性哈希时,均匀只有 k/n 个键须要被从新映射,其中 k 是键的数量,n 是槽位的数量。相比之下,在大多数传统哈希表中,数组槽位数量的变动导致简直所有的键都须要被从新映射[1]”。

哈希空间和哈希环

当初咱们了解了一致性哈希的定义,让咱们理解它是如何工作的。假如应用 SHA- 1 作为哈希函数 f,哈希函数的输入范畴是:x0, x1, x2, x3, …, xn。在密码学中,SHA- 1 的哈希空间从 0 到 2^160 – 1。也就是说,x0 对应 0,xn 对应 2^160 – 1,所有其余的哈希值都落在 0 和 2^160 – 1 之间。图 5 - 3 展现了哈希空间。

通过连贯两端,咱们失去一个如图 5 - 4 所示的哈希环:

哈希服务器

应用雷同的哈希函数 f,咱们依据服务器的 IP 或名字将服务器映射到环上。图 5 - 5 显示了 4 台服务器被映射到哈希环上。

哈希键

值得一提的是,这里应用的哈希函数与“重哈希问题”中的不同,并且没有模运算。如图 5 - 6 所示,4 个缓存键(key0,key1,key2 和 key3)被哈希到哈希环上。

服务器查找

为了确定一个键存储在哪个服务器上,咱们从环上的键地位顺时针方向进行寻找,直到找到一个服务器。图 5 - 7 解释了这个过程。顺时针方向,key 0 存储在 server 0上;key1 存储在 server 1 上;key2 存储在 server 2 上;key3 存储在 server 3 上。

增加服务器

应用上述逻辑,增加新服务器只须要重新分配一部分键。

在图 5 - 8 中,新增 server 4 后,只有 key0 须要被重新分配。k1, k2,k3 依然在雷同的服务器上。让咱们认真看看这个逻辑。在 server 4 增加之前,key0 存储在 server 0 上。当初,key0 将存储在 server 4 上,因为 server 4 是它从环上的 key0 地位顺时针方向遇到的第一个服务器。其余的键依据一致性哈希算法不须要重新分配。

移除服务器

当服务器被移除时,只有少部分的键须要通过一致性哈希进行重新分配。在图 5 - 9 中,当 server 1 被移除时,只有 key1 必须被映射到 server 2。其余的键不受影响。

根本办法中的两个问题

一致性哈希算法是由 MIT 的 Karger 等人提出的[1]。根本步骤如下:

  • 应用均匀分布的哈希函数将服务器和键映射到环上。
  • 要找出键映射到哪个服务器,从键地位开始顺时针方向找到环上的第一个服务器。

这种办法存在两个问题。首先,思考到服务器可能会被增加或移除,不可能在环上为所有服务器放弃雷同大小的分区。分区是相邻服务器之间的哈希空间。每个服务器被调配到的环上的分区大小可能十分小或者相当大。在图 5 -10 中,如果 s1 被移除,s2的分区(双向箭头高亮示意)就是 s0s3分区的两倍大。

第二,环上的键散布可能非平均。例如,如果服务器映射到图 5 -11 中列出的地位,大部分的键都存储在 server 2 上。然而,server 1server 3 没有任何数据。

一种被称为虚构节点或正本的技术被用来解决这些问题。

虚构节点

虚构节点是指理论节点,每个服务器在环上都由多个虚构节点示意。在图 5 -12 中,server 0server 1 都有 3 个虚构节点。这个 3 是随便抉择的;在理论零碎中,虚构节点的数量要多得多。咱们不再应用 s0,而是应用 s0_0, s0_1s0_2 来在环上示意 server 0。同样,s1_0, s1_1s1_2 在环上示意 server 1。有了虚构节点,每个服务器就负责多个分区。标签为 s0 的分区(边)由 server 0 治理。另一方面,标签为 s1 的分区由 server 1 治理。

要找出一个键存储在哪个服务器上,咱们从键的地位顺时针方向去找环上遇到的第一个虚构节点。在图 5 -13 中,要找出 k0 存储在哪个服务器上,咱们从 k0 的地位顺时针方向找到虚构节点s1_1,它指向server 1

随着虚构节点数量的减少,键的散布变得更加平衡。这是因为随着虚构节点数量的减少,标准差变得更小,导致数据分布平衡。标准差掂量了数据的扩散水平。在线钻研的一项试验后果 [2] 表明,当有一百或两百个虚构节点时,标准差在均值的 5%(200 个虚构节点)到 10%(100 个虚构节点)之间。当咱们减少虚构节点数量时,标准差会变小。然而,咱们须要更多的空间来存储虚构节点的数据。这是一个衡量,咱们能够调整虚构节点的数量以适应咱们的零碎需要。

找到受影响的键

当增加或移除一个服务器时,局部数据须要被从新散布。咱们如何找到受影响的范畴以重新分配键呢?

在图 5 -14 中,server 4被增加到环中。受影响的范畴从 s4(新增加的节点)开始,逆时针挪动到找到一个服务器(s3)。因而,位于s3s4之间的键须要被重新分配给s4

当一个服务器(s1)如图 5 -15 所示被移除时,受影响的范畴从 s1(被移除的节点)开始,逆时针绕环挪动到找到一个服务器(s0)。因而,位于s0s1之间的键必须被重新分配给s2

总结

在这一章,咱们深刻探讨了一致性哈希,包含为什么须要它以及它是如何工作的。一致性哈希的益处包含:

  • 当服务器被增加或移除时,最小化键的从新散布。
  • 因为数据更平均地散布,所以易于横向扩大。
  • 缓解热点键问题。适度拜访特定的分片可能导致服务器过载。设想一下,Katy Perry、Justin Bieber 和 Lady Gaga 的数据全副都在同一个分片上。一致性哈希通过更平均地散布数据来缓解这个问题。

一致性哈希在事实世界的零碎中被广泛应用,包含一些驰名的零碎:

  • Amazon 的 Dynamo 数据库的分区组件 [3]
  • Apache Cassandra 中跨集群的数据分区 [4]
  • Discord 聊天利用 [5]
  • Akamai 内容散发网络 [6]
  • Maglev 网络负载均衡器 [7]

祝贺你走到这一步!当初给本人一个赞。干得好!

AI 不会取代你, 应用 AI 的人会。欢送关注我的公众号:更 AI。以程序员的视角来看 AI 能带给咱们什么~

参考资料

[1] 一致性哈希:https://en.wikipedia.org/wiki/Consistent_hashing

[2] 一致性哈希:

https://tom-e-white.com/2007/11/consistent-hashing.html

[3] Dynamo:亚马逊的高可用键值存储:
https://www.allthingsdistributed.com/files/amazon-dynamo-sosp…

[4] Cassandra – 一个去中心化的结构化存储系统:

http://www.cs.cornell.edu/Projects/ladis2009/papers/Lakshman-…

[5] 如何将 Discord Elixir 扩大到 500 万并发用户:
https://blog.discord.com/scaling-elixir-f9b8e1e7c29b

[6] CS168:古代算法工具箱第一课:简介和一致性哈希:http://theory.stanford.edu/~tim/s16/l/l1.pdf

[7] Maglev:一个疾速牢靠的软件网络负载均衡器:
https://static.googleusercontent.com/media/research.google.co…

退出移动版