[.com原稿]在这篇文章中，我们将了解什么是一致性哈希，以及为什么它是可伸缩分布式系统架构中的必备工具。此外，我们将探索可用于大规模实施算法的数据结构。***，我们还将探索一个实际的例子。究竟什么是一致性哈希？还记得你在大学里学到的那种传统的朴素哈希方法吗？使用哈希函数，我们确保计算机程序所需的资源高效地存储在内存中，确保内存中的数据结构被均匀加载。我们还确保这种资源存储策略也使信息检索更加高效，从而使程序运行得更快。经典的散列方法使用散列函数生成伪随机数，然后除以内存空间的大小，将随机标识符转换为可用空间内的位置。结果如下所示：location=hash(key)modsize。图1那么，为什么我们不使用相同的方法来处理网络上的请求呢？在各种程序、计算机或用户向多个服务器节点请求某些资源的场景下，我们需要一种机制将请求平均映射到可用的服务器节点，以保证负载均衡并保持一致的性能。我们现在不妨退后一步，将服务器节点视为可以将一个或多个请求映射到的占位符。在经典的哈希方法中，我们总是假设内存位置的数量是已知的，并且这个数字永远不会改变。例如，我们通常会在一天内对集群进行扩容或缩容，同时还要应对突发故障。但是如果我们考虑上面的场景，并不能保证服务器节点的数量会保持不变。如果其中一个突然失败怎么办？使用简单的散列方法，我们最终需要重新计算每个键的散列值，因为新映射取决于节点数/内存位置，如下所示：图2：之前图3：刚刚重新计算分布之后哈希值系统的一个问题（移动每个键的位置）是状态存储在每个节点上。例如，集群大小的微小变化可能会导致大量工作重新缩放集群中的所有数据。随着集群规模的增长，这变得不可持续，因为每次哈希更改所需的工作量随集群规模线性增长。这时候一致性哈希的概念就派上用场了。究竟什么是一致性哈希？可以这样描述：它在一个虚拟的环状结构（命名为HashRing，HashRing）中代表资源请求者（我们在本文中简称为“请求”）和服务器节点。位置的数量不再固定，但环被认为具有最大数量的点，服务器节点可以放置在环上的随机位置。当然，可以使用哈希函数再次选择该随机数，但由于它不再是有限数，因此跳过了除以可用位置数的第二步。用户、计算机或无服务器程序的请求使用相同的哈希函数放置在同一个环上，类似于经典哈希中的键。图4那么，您如何决定哪个请求将由哪个服务器节点处理？如果我们假设环是有序的，使得环的顺时针遍历对应于位置地址的递增顺序，那么每个请求都可以由顺时针遍历中出现最多的服务器节点处理。即地址比请求地址高的第一个服务器节点负责处理请求。如果请求地址高于寻址最多的节点，则由地址最低的服务器节点处理，因为环遍历是以循环方式完成的。如下图所示：图5理论上，每个服务器节点“拥有”哈希环的一个区间，任何进入这个区间的请求都会被同一个服务器节点处理。现在，如果其中一个服务器节点（假设节点3）出现故障，下一个服务器节点的范围变宽，并且进入该范围的任何请求都转到新的服务器节点怎么办？然后只需要重新分配这个间隔（对应于发生故障的服务器节点），哈希环的其余部分和请求/节点分配不受影响。这与经典的哈希技术形成对比：哈希表大小的变化几乎会干扰所有映射。由于一致性哈希，只有一小部分请求（相对于环分配因子）会受到特定环更改的影响。（环发生变化是因为一些请求/节点映射因添加或删除节点而发生变化。）图6如何高效地实现一致性哈希算法？现在我们弄清楚了什么是哈希环，我们需要实现以下部分以使其工作：从我们的哈希空间到集群中节点的映射，允许我们找到负责请求的节点。解析为节点的集群请求的集合。稍后，这将使我们能够找出哪些哈希因添加或删除节点而受到影响。映射为了完成上面的第一部分，我们需要以下部分：给定一个请求标识符，计算环中位置的哈希函数。一种找出哪个节点对应于哈希请求的方法。为了找出某个请求对应于哪个节点，我们可以用一个简单的数据结构来表示，包括以下几个部分：环中节点对应的哈希数组。用于查找与特定请求对应的节点的图形（哈希表）。这实际上是有序图的原始表示。要在上述结构中找到负责某个散列的节点，我们需要：执行修改后的二分查找，找到数组中第一个等于或大于（≥）我们要查找的散列的节点/散列。在图中找到与找到的节点/哈希对应的节点。添加或删除节点正如我们在文章开头看到的，当添加一个新节点时，包含各种请求的哈希环的某些部分必须分配给该节点。相反，当一个节点被删除时，分配给该节点的请求需要由其他节点处理。我们如何找到那些受环变化影响的请求？一种解决方案是遍历分配给节点的所有请求。对于每一个请求，我们判断它是否属于已经发生的环变化范围内，如果有必要，将其移动到别处。但是，执行此操作所需的工作量会随着分配给节点的请求数量的增加而增加。随着节点数量的增加，发生环变化的次数往往会增加，这一事实使情况变得更糟。在最坏的情况下，由于环变化通常与局部故障相关，因此与环变化相关的瞬态负载也可能增加其他节点也受到影响的可能性，从而可能导致整个系统出现连锁反应问题。为了解决这个问题，我们希望请求的重定向尽可能高效。理想情况下，我们会将所有请求存储在一个数据结构中，该数据结构使我们能够在环上的任何位置找到受单个哈希更改影响的那些请求。高效查找受影响的哈希向集群添加节点或从集群中删除节点会改变请求在环的某些部分的分布，我们称之为受影响的范围。如果我们知道受影响范围的边界，我们就可以将请求移动到正确的位置。要找到受影响区间的边界，可以从添加或删除的节点的哈希值H开始，从H开始沿环向后移动（图中逆时针方向），直到找到另一个节点。我们将节点的哈希值称为S（起始值）。对该节点的逆时针请求将转到它，因此这些请求不会受到影响。请注意：这只是对所发生情况的简要描述；实际上，结构和算法更复杂，因为我们使用大于1的复制因子和专门的复制策略（只有一小部分节点可用于任何特定请求）。在找到的节点和添加（或删除）的节点之间的间隔中放置哈希的请求是需要移动的请求。高效查找受影响范围内的请求。一种方案是遍历一个节点对应的所有请求，更新hash值在范围内的请求。在JavaScript中，它可能看起来像这样：=upperBound
