5 设计一致哈希（HASHING）

要实现横向扩展，就必须在服务器之间高效、均匀地分配请求/数据。一致哈希是实现这一目标的常用技术。不过，首先让我们深入了解一下这个问题。

5.1 重散列（rehashing）问题

如果有n台缓存服务器，平衡负载的常用方法是使用下面的散列方法：

serverIndex = hash(key)%N，其中N是服务器池的大小。

当服务器池的大小固定且数据分布均匀时，这种方法效果很好。但是，当添加新服务器或移除现有服务器时，问题就会出现。例如，如果服务器1离线，服务器池的大小就会变成3。这意味着当服务器1离线时，大多数缓存客户端会连接到错误的服务器来获取数据。这将导致缓存丢失风暴。一致性散列是缓解这一问题的有效技术。

5.2 一致散列（Consistent hashing）

引自维基百科："一致散列是一种特殊的散列方式，当重新调整哈希表大小并使用一致散列时，平均只需重新映射 k/n 个键，其中k是键的个数，n是槽的个数。相比之下，在大多数传统哈希表中，数组槽数的变化会导致几乎所有的键都要重新映射"。

5.3 散列空间和散列环

既然我们已经理解了一致散列的定义，那就让我们来看看它是如何工作的。假设使用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.4 散列服务器

使用相同的哈希函数f，我们根据服务器IP或名称将服务器映射到哈希环上。

5.5 散列键

值得一提的是，这里使用的哈希函数与 "重洗问题 "中的哈希函数不同，没有模块化操作。

5.6 服务器查询

要确定密钥存储在哪个服务器上，我们要从密钥在哈希环上的位置开始顺时针查找，直到找到服务器为止。下图解释了这一过程。按顺时针方向，0存放在服务器0上；1存放在服务器1上；2存放在服务器2上；3存放在服务器3上。

5.7 添加服务器

使用上述逻辑，添加新服务器只需重新分配一部分密钥。

添加新服务器 4后，只需重新分配0，而 k1、k2 和 k3 仍保存在相同的服务器上。让我们仔细看看其中的逻辑。在服务器4添加之前，0保存在服务器0上。现在，密钥0将被保存在服务器4上，因为服务器4是它从密钥0在环上的位置顺时针旋转遇到的第一个服务器。其他Key不会根据一致的哈希算法重新分配。

5.8 移除服务器

移除服务器时，只有一小部分Key需要使用一致散列算法重新分配。下图中，当服务器1被移除时，只有key1必须重新映射到服务器2。其余的密钥不受影响。

5.9 基本方法中的两个问题

一致散列算法是由麻省理工学院的Karger等人提出的。基本步骤如下

• 使用均匀分布的散列函数将服务器和密钥映射到环上。

• 要找出密钥映射到哪个服务器上，就从密钥位置开始顺时针查找，直到找到环上的第一个服务器为止。

这种方法存在两个问题。首先，考虑到服务器可以添加或删除，环上所有服务器的分区大小不可能保持一致。分区是相邻服务器之间的散列空间。分配给每个服务器的环上分区的大小有可能非常小，也有可能相当大。下图如果删除 s1，s2 的分区（双向箭头突出显示）将是 s0 和 s3 分区的两倍。

其次，环上有可能出现密钥分布不均匀的情况。例如，如果将服务器映射到下图所列的位置，则大部分密钥都存储在服务器 2 上。然而，服务器 1 和服务器 3 却没有数据。

一种称为虚拟节点或副本的技术可用于解决这些问题。

参考资料

• 软件测试精品书籍文档下载持续更新 https://github.com/china-testing/python-testing-examples 请点赞，谢谢！
• 本文涉及的python测试开发库 谢谢点赞！ https://github.com/china-testing/python_cn_resouce
• python精品书籍下载 https://github.com/china-testing/python_cn_resouce/blob/main/python_good_books.md
• Linux精品书籍下载 https://www.cnblogs.com/testing-/p/17438558.html
• 一致散列：https://en.wikipedia.org/wiki/Consistent_hashing
• 一致散列：
  https://tom-e-white.com/2007/11/consistent-hashing.html
• Dynamo： 亚马逊的高可用键值存储：
  https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
• Cassandra - 一种分散的结构化存储系统：
  http://www.cs.cornell.edu/Projects/ladis2009/papers/Lakshman-ladis2009.PDF
• Discord 如何将 Elixir 扩展到 5,000,000 并发用户：
  https://blog.discord.com/scaling-elixir-f9b8e1e7c29b
• CS168： 现代算法工具箱讲座 #1：导论和一致性
  哈希算法：http://theory.stanford.edu/~tim/s16/l/l1.pdf
• Maglev: A Fast and Reliable Software Network Load Balancer：
  https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf

5.10 虚拟节点

虚拟节点指的是真实节点，每个服务器都由环上的多个虚拟节点表示。下图中，服务器 0 和服务器 1 都有 3 个虚拟节点。3 是任意选择的；而在实际系统中，虚拟节点的数量要大得多。我们不用 s0，而是用 s0_0、s0_1 和 s0_2 来表示环上的服务器 0。同样，s1_0、s1_1 和 s1_2 代表环上的服务器 1。通过虚拟节点，每个服务器负责多个分区。标签为 s0 的分区（边）由服务器 0 管理，而标签为 s1 的分区则由服务器 1 管理。

要查找密钥存储在哪台服务器上，我们可以从密钥所在位置出发，顺时针方向查找环上遇到的第一个虚拟节点。下图，要找出 k0 存放在哪个服务器上，我们从 k0 所在位置开始顺时针方向查找虚拟节点 s1_1，它指的是服务器 1。

随着虚拟节点数量的增加，密钥的分布也变得更加均衡。这是因为虚拟节点越多，标准偏差就越小，从而导致数据分布均衡。标准偏差衡量数据的分布情况。在线研究[2]的实验结果表明，在有一两百个虚拟节点的情况下，标准偏差介于平均值的 5%（200 个虚拟节点）和 10%（100 个虚拟节点）之间。当我们增加虚拟节点的数量时，标准偏差会更小。但是，需要更多空间来存储虚拟节点的数据。这是一个权衡问题，我们可以根据系统要求调整虚拟节点的数量。

5.11 找受影响的键

添加或删除服务器时，需要重新分配一部分数据。我们如何找到受影响的范围来重新分配密钥呢？

下图中，服务器 4 被添加到环上。受影响的范围从 s4（新添加的节点）开始，围绕环逆时针移动，直到找到一个服务器（s3）。因此，位于 s3 和 s4 之间的密钥需要重新分配到 s4。

下图当服务器（s1）被移除时，受影响的范围从 s1（被移除的节点）开始，围绕环路逆时针移动，直到找到服务器（s0）为止。因此，位于 s0 和 s1 之间的密钥必须重新分配到 s2。

5.12 总结

在本章中，我们深入讨论了一致散列，包括为什么需要一致散列以及一致散列的工作原理。一致散列的好处包括

• 当服务器添加或删除时，最小化的密钥会重新分配。
• 由于数据分布更均匀，因此易于横向扩展。
• 缓解热点密钥问题。对特定分片的过度访问可能会导致服务器过载。想象一下，凯蒂-佩里、贾斯汀-比伯和 Lady Gaga 的数据最终都在同一个分片上。一致散列法通过更均匀地分配数据，有助于缓解这一问题。

一致散列在现实世界的系统中得到了广泛应用，其中包括一些著名的系统：

• 亚马逊Dynamo数据库的分区组件。
• Apache Cassandra 中跨集群的数据分区。
• Discord 聊天应用程序
• Akamai 内容交付网络
• Maglev 网络负载平衡器