系统设计：一致性哈希
原文：
towardsdatascience.com/system-design-consistent-hashing-43ddf48d2d32
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/25fd590876caa1d6c711fa521ea11f98.png
简介
我们生活在一个每天都会大量生成数据的世界上。在大公司中，实际上不可能将所有数据存储在单个服务器上。这就是为什么我们需要水平扩展，即每个数据部分都存储在单独的服务器上。
与我们可以在一个地方简单地存储所有数据的垂直扩展相反，在水平扩展中，组织存储以实现不同服务器上数据的快速访问至关重要。通过了解简单系统实现的性能劣势，我们将设计一个具有弹性的系统，以减轻提到的问题。
在系统设计中，我们将使用的原则被称为一致性哈希。
问题
假设我们有 n 个需要存储在 k 个不同服务器上的数据对象。服务器的配置可能会随时间变化：
任何服务器都可以关闭；
可以向系统中添加新的服务器。
考虑到这些潜在的配置更改，我们必须设计一个系统，该系统可以快速检索所需的数据块，并在配置更改的情况下在服务器之间传输数据。
简单实现
简单实现包括根据哈希函数在不同服务器之间分配数据。例如，当我们需要向我们的系统添加新的数据块时，我们将它的键插入到哈希函数中，该函数输出这个块将属于哪个服务器。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/7b3e567cc0c4844806ce974d4503ab76.png
基于哈希函数的数据分布。数据根据相应的哈希值存储在服务器上。
当我们需要从给定的键检索信息时，我们计算其哈希值以确定与该键关联的信息存储在哪个服务器上。在实现此类系统时，确保哈希函数均匀分布数据非常重要，以便每个服务器存储的数据量大致相同。
这个系统在对其进行更改之前运行良好。例如，想象一下上面的例子中服务器 S3 被关闭：我们无法访问其数据，并且将哈希到其桶中的新数据将不会被添加。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/da42dd1417c4552b89fa4ca31f933a09.png
每当任何服务器关闭时，其数据将不再可访问。
唯一可能的解决方案是将所有数据块重新分配到服务器上。由于我们现在有 k-1 个服务器，我们不应忘记在哈希函数中的余数必须减少 1。如果向系统中添加新服务器，也会发生类似的场景。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/662a75794fc3630bb1741b0d64cfd34b.png
在任何系统配置更改的情况下，所有数据都需要重新分配。
不幸的是，数据重新分配是一个资源消耗的操作。在大量数据和频繁配置更改的情况下，这种存储系统变得非常低效。
一致性哈希
一致性哈希是上述系统的优秀替代方案，在配置更改的情况下具有更高的容错性。
一致性哈希不仅对数据进行哈希，也对服务器进行哈希。数据键和服务器被哈希到同一组值[0, n]。为了更容易理解和可视化，让我们想象所有的哈希值都位于一个环（或时钟）上。每个服务器都有自己的哈希范围。
服务器哈希范围定义为哈希环上位于服务器哈希值之前和位于逆时针方向上另一个最近服务器哈希值之后的所有哈希值的区间。
要确定某个键属于哪个服务器，我们需要从键的哈希值开始，顺时针方向移动，直到我们达到对应于某个服务器的哈希值。该服务器将存储该键的数据。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/df45486af39d7eb0cdfc435956326d61.png
哈希环示例。服务器 S1 的哈希范围用蓝色表示。
服务器哈希值应存储在其他地方，并按升序排列，以便可以快速访问。使用二分搜索，这使我们能够在 O(log S)的时间内找到存储给定键的服务器（S 是服务器数量）。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/f946dffa0c1970a52ca62e51b49cdc8e.png
使用一致性哈希，可以以 O(log S)的时间复杂度找到与给定键关联的服务器编号，其中 S 是服务器总数。
关闭服务器
如果任何服务器关闭，我们只需简单地删除与该服务器关联的哈希值，并将该服务器上的数据仅**转移到顺时针方向的下一个服务器。与简单哈希相比，这是一致性哈希的一个巨大优势，因为我们不再需要像以前那样重新分配所有数据。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/53b29d6fca78fcb8c3ae364b76d5c6b1.png
从上面的例子中关闭服务器 S1 只需要转移之前存储在该服务器上的数据。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/fcda44a388c46ab6817a4101357490f7.png
关闭 S1 后，服务器 S2 扩展了其哈希范围。
添加新服务器
如果需要向系统中添加新服务器，那么我们只需要转移所有与位于新服务器哈希值和逆时针方向最近服务器哈希值之间哈希值相关联的数据。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/72dc699ce47dbb473d64c4c12c242d01.png
向系统中添加新服务器 S4。只有存储在 S0 上的一部分数据需要转移到 S4。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/99ae4a446f3fccb30e2ff82485975ecd.png
添加 S4 后，它占用了之前属于 S0 的一些相关哈希值。
不均匀分布
虽然一致性哈希似乎对各种配置更改具有弹性，但可能会出现数据在服务器之间不均匀分布的时刻。
- 首先，这可能是由于选择的哈希函数。实际上，我们无法保证它将均匀地为数据生成键。因此，这可能导致服务器具有非常不成比例的哈希范围长度。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/5eacfacf129e2543e74e21555ce40cc9.png
- 即使在某一时刻数据分布均匀，随着各种配置的改变，它可能会迅速变得不均匀。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/a4a61d500cfc8b33b4f391b07c491604.png
随着不均匀分布的增加，平均响应时间成比例变长。
缓解此问题的可能方法之一是在分布变得倾斜时，定期在系统中重新分配所有数据（可能使用另一个哈希函数）。虽然有时这可能是一个解决方案，但当有数百万或数十亿数据对象时，这仍然不是最佳方案。
虚拟节点
虚拟节点是构成哈希的扩展，它使得系统更能抵抗不均匀的数据分布。这个想法包括对每个服务器进行多次哈希（使用不同的哈希函数）。每个服务器的总哈希范围定义为与其所有键相关联的哈希范围的并集。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/ce9e2f688551960704a1e8387c78bd08.png
使用虚拟节点的一致性哈希。哈希环上的每种独特颜色对应一个服务器。
关闭服务器意味着删除与该服务器相关联的所有虚拟节点。该服务器上的所有数据都将转移到其他多个服务器。
当添加新服务器时，其虚拟节点的所有哈希值应通过之前用于其他服务器的哈希函数来计算。
在现实中，虚拟节点的数量通常比上面的例子中多得多。
一方面，随着虚拟节点数量的增加，哈希范围在平均上变得更加对齐。另一方面，执行与配置变化相关的标准操作需要更多的时间。此外，还需要存储关于虚拟节点的额外元数据。
在大多数情况下，根据给定问题、可用服务器数量和数据量来选择虚拟节点的数量是更好的。当难以估计一个合适的数字时，建议调整此参数以找到完美的权衡。
应用
一致性哈希具有广泛的应用范围。大多数情况下，它用于分布式应用程序，尤其是在存储大量数据的数据库中，这些数据分布在多个服务器上。一些最流行的例子包括：
Apache Cassandra– 分布式 NoSQL 列数据库；
Amazon Dynamo DB– 分布式 NoSQL 键值数据库；
Discord– 视频和聊天应用程序。
结论
随着分布式系统的兴起，一致性哈希开始迅速获得人气。通过能够抵抗频繁的配置变化，它提供了一个简单而有效的解决方案，用于跨不同集群划分数据。同时，虚拟节点数作为一个重要的参数，使得一致性哈希能够更好地适应大多数系统设置。
资源
- 一致性哈希 | 维基百科
除非另有说明，所有图像均为作者提供。