系统设计：一致性哈希

原文towardsdatascience.com/system-design-consistent-hashing-43ddf48d2d32https://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– 视频和聊天应用程序。结论随着分布式系统的兴起一致性哈希开始迅速获得人气。通过能够抵抗频繁的配置变化它提供了一个简单而有效的解决方案用于跨不同集群划分数据。同时虚拟节点数作为一个重要的参数使得一致性哈希能够更好地适应大多数系统设置。资源一致性哈希 | 维基百科除非另有说明所有图像均为作者提供。