本文中，我们将通过实例来解释一致性哈希和 rendezvous 散列之间的区别。通过本文，您将更好地了解两者之间的细微差别，并做出更明智的选择。
大家好，我的名字是米哈伊尔·亚历克谢维奇，我在MY.GAMES担任Java后端开发者。优化性能的实现是我热衷的事情之一，我对分布式系统也十分感兴趣——但我更喜欢这种情况，将数学融入到性能目标和理念之中。
为此，在本文中，我将探讨在服务器上哈希数据时一致哈希和 rendezvous 哈希算法之间的区别。我还将提供我们在处理这些问题时遇到的一些实例。在 MY.GAMES，我们总是寻找新的方法来优化游戏的后端，并不断尝试新技术，分享我们的经验。
文章快结束时我会谈到的一个 Skeleton 变体的例子。
关于一致哈希的特点我来举个例子：我们有一个很酷的键值存储系统，因为负载增大了，所以我们决定扩展一下这个系统。假设客户想在键值24存点数据。
左边是客户，右边是节点们
客户端怎么挑出负责这个键的节点？（我们不会考虑可能效果不佳的奇怪选项，例如使用轮流选择的方式选择节点，然后将选择的节点分发给其他客户端。）
我建议简单地用24除以节点的数量——节点有四个。然后只需取这个除法的余数。
我们得到了某个索引值。所以，如果我们索引0有一个蓝色节点，索引1有一个红色节点，依此类推，因此可以得出这样的结论：蓝色节点负责键24。我们将键的值发送给它，它现在保存着这个值。对于全世界的任何客户端来说，这个划分的结果对于这个键都是正确的。
同样，如果我们用41除以4，余数是1，然后发送到红色，同样地给橙色15，给绿色34。
如果我们想要获取键41的值，我们就用4去除它，余数为1，然后到红色节点并取该值。
上述方法本质上就是一个大家熟悉的普通HashMap，一切运行得还不错，直到橙色的那个节点挂了。
现在，当我们想要得到41这个值时，我们除以3而非4，余数是2。所以我们去绿色节点要数据，但它什么也给不了我们，因为映射已经坏了。同样，如果有新的节点加入集群，也会出现类似的情况。
这完全不是我们想要的。问题是，当集群结构发生变化时，数组也随之变化——它会变小或变大。最好是让数组保持原样，但某个节点宕机了（或者新增了一个节点），所以得做点什么。一致性哈希环可以帮到忙。
这是它的运作方式：我们以100为例，现在我们有一个包含我们所有可能哈希值的范围：[0; 100)。我们将这个范围按照节点的数量来划分，这样我们就得到了4个范围，每个范围正好有25个元素。然后，每个范围都映射到一个节点。但我们不只是简单地映射它们——我们将这些范围像环一样连接起来。所以现在，如果某个节点宕机了，它的范围会被下一个节点接手。
我们将为每个区间分配一个标记；这个标记是该区间第一个元素，即（0, 25, 50, 75）之一。为了确定哪个节点负责特定键，我们取键除以100的余数作为参考，然后通过二分查找找到最接近该余数的标记；找到的标记对应的节点将负责此键。
如你所知，二分搜索的时间复杂度是对数级别的，这很好，但是之前可以将一个节点定义为常量。我也会提及一种可能的优化方案，通过牺牲内存来优化算法复杂度：你可以创建一个包含100个元素的数组，并根据它们的区间将节点分解到这个数组中（例如：[0; 24]、[25; 49]等）。计算键的哈希值后，然后你可以通过索引从数组中提取节点，从而实现常数时间查找。
现在，让我们回到我们的例子：客户决定将键值设为124。所以，当除以100时，余数是24，这便是蓝色节点，数据因此被发送到该节点。同样，对于下面的键：141、251、378也会发生类似的事情。
当橙色节点崩溃时，客户端尝试从键251获取值，但没有变化。我们再除以100，得到的余数是51，然后去红色节点获取值。那么键378又如何呢？和其他橙色节点处理的键一样，它现在在环形中的下一个节点上处理，即蓝色节点。
如果向集群中添加新的节点，我们并不完全清楚应该怎么做。我们需要从另一个节点分配一部分数据——但实际上，这倒不是最关键的问题。
主要问题是橙色节点崩溃了。为什么会发生这种情况？如果是因为负载过高，那么整个负载将会转移到蓝色节点上——它也可能崩溃。最终，绿色和红色节点也可能跟着崩溃。我们不能让这种情况继续下去，所以我们得想个别的办法。
我们的范围结果变得不灵活和不方便。如果把每个范围拆分成几个更小的部分，并分配到其他节点上，会好得多。但是问题是，我们以4为单位进行划分的原因是我们正好有四个物理节点。那我们现在该怎么分配这些范围呢？
答案其实很简单：我们可以把每个范围映射到虚拟节点上，再把这些虚拟节点映射到物理节点上。
实践中就是这样：我们将一个大的区间分成了16个大约相等的虚拟节点，并将每个虚拟节点映射到一个物理节点上。
gif中的虚拟节点更少了，不过想法还是差不多
这一切都遵循之前的逻辑。我们将124除以100，余数为24。我们要找的是负责这个键的虚拟节点，即蓝色节点22到27。因此，我们将键发送过去，以此类推。
所以，如果这个橙色节点崩溃了，我们不会把全部的负载都转移到蓝色节点上，而是平均分给其他节点——每个服务器分到一个虚拟节点，并且剩下的那一个虚拟节点的四分之一也平均分配给其他节点。这样一来，因为负载已经被均匀分配，集群中的其他节点就不会再崩溃。
(Note: "rendezvous hashing" is a technical term, usually left untranslated or clarified with its technical term in the target language. Here, I've kept it untranslated as is common practice in technical contexts.)
然而，实际上，所有这些带有虚拟节点的环都并非那么容易实现，因此相比之下，相对于广泛接受的（但复杂的）一致性哈希，你可以选择使用 rendezvous哈希算法。虽然它没有那么好的算法特性，但它确实让键在节点间的分布变得更简单，并且在理论上大大降低了开销。
使用 rendezvous hashing，客户端不仅为键 364 计算哈希，还会为键 364 和节点 1、键 364 和节点 2 这对组合计算哈希。所以我们这么操作，会这样做。我们计算这些哈希。比如我们得到的值是这样的。
我们收到了一系列哈希；我们可以从中挑选出最大值，这个节点负责处理这个键：364会被发到节点1。
让我指出，来自键364和节点编号1的最大哈希值将是所有客户端中的最大值。同样，如果我们取键215，再次计算哈希，排序后我们会得到最大值并将其发送到节点编号2。我们也会用同样的方法处理107和124。
现在，当我们想要获取一个值时，计算哈希数，排序后，挑出最大值，然后再从第二个节点取。即便节点4宕机了，也不会有任何改变——最大哈希值依然是由215与2这一对得到的。
现在谁来负责密钥124？为了回答这个问题，我们计算哈希，排序数组，排除节点，然后从剩下的列表中选择下一个。
结果发现，在我们的算法中，节点之间的键重分配是免费实现的，而且这很可能会相对公平，相比之下，一致哈希就未必如此。不能保证在节点4之后的键一定会指向节点1；可能是节点2、3或其他节点。如果有更多节点，也可能是其他节点。
还有不少好处。如果我们决定将此列表中的第一个节点作为主节点，其余的作为备份节点，那么当它收到键时，就可以把值复制给接下来的两个节点；换句话说，主节点还能算出这些哈希。
此外，客户端可以同时向三个节点发送值，并只需等待任意两个节点的确认，也就是说，它可以采用多数表决的方式进行写入。
但是有一个问题就是：如果添加了一个新的节点，其中一些键的哈希值可能会变成列表中的最大值，这种情况会发生什么呢？
我们需要以某种方式来“让节点预热”。（并且我们也需要以某种方式在一致性哈希中实现这一点。）为了理解如何让节点预热，我们需要了解我们系统的特性：如果这是一个分布式缓存，那么它通常会有一个关联的数据库，并且可以通过数据库预热节点。
如果系统自身是持久且分布的，那么我们就能找到前一个节点，并能从它那里预热新节点。
之前我们只计算一个哈希，但现在我们要计算N个哈希。对于小型集群来说这不成问题，但对于大型集群来说，我们则可以采用对数方式，通过调整骨架来实现。
所以，我们有24个节点，这是一个相当具体的N值。假设它们是这样分组的：
我们将它们合并成一个虚拟的骨架，就像一棵树一样。
当我们想对键124做某事时，我们可以直接在树上递归应用 rendezvous 哈希算法。换句话说，虚拟节点0有两个孩子节点：1和2。我们计算、排序并选择两个哈希值中的最大值。
键124分配给虚拟节点2。
接下来，我们从节点2的子节点中统计哈希值，排序后选择最大的那个。
但是我们不只是从1、2和3开始计数，而是从最高位为当前节点编号，最低位为子节点编号的数字开始计数。这是因为在之前的步骤中，当我们处于节点0并计算哈希值时，最大值是2；而在计数时，我们肯定不会选择1，而是选择2或3中的一个。对于所有最终落在虚拟节点2上的键来说，这句话都是正确的。有些节点根本没有使用，这不太好，所以我们可以用一个小技巧来使分布更随机并能访问所有内容；124则被分配到了虚拟节点1。
在这里我们用同样的方法计算哈希，选择最大值。
因此，数字124在节点4上被处理了。这里使用了九个哈希值，而不是24个。
如果第四个节点崩溃了，我们知道该怎么做。我们就把它划掉，然后选下一个。
如果整个集群崩溃，我们只需向上一级转移，然后选择列表里的下一个。对于虚拟节点 2 中的四个节点，我们也会做同样的操作。因此，124 将被移到第二个节点。
此时，一致性哈希还有最后一个优势——虚拟节点在物理服务器上的自由分布特性。是的，我们可以通过某种权重函数，给性能强的服务器分配更多的虚拟节点。但是，rendezvous 哈希也有它的解决方案：一种加权版本的 rendezvous 算法。不过，这种方法也有一个缺点：使用一致性哈希时，我们可以手动迁移虚拟节点，但在使用 rendezvous 时则不行。
尽管一致性和会面这两种方法解决相同问题的成本大致相当，但它们的差异在实践中尤为显著，这一点在实际操作中尤为突出。
保持一致的：
- O(log n) O(1)
- 实现负载均衡的可能性
约会：
- O(n) O(log n)
- 无需额外努力即可实现均匀分布
- 简单的复制操作
在最基本的版本中，一致性哈希的算法复杂度是一个更好的方法，对于大型集群来说，我们很可能会采用这种方法。尽管在rendezvous方面我们还需要做一些调整。当数值趋向于无穷大时，对数不会远离常数，因此为了其他优点，这种小的牺牲往往是值得的。一致性哈希还支持手动调整负载平衡。
这就是rendezvous带给我们的：在集群结构变化时，算法会均匀地分布，同时进行简单的自然复制过程。
我希望这篇帖子能解释一致哈希和 rendezvous 哈希之间的细微差别，让你能更加明智地选择你的哈希策略！