近年来, 随着云计算和大数据等概念的出现, 分布式系统已经获得了普及和相关性.

其中一种系统， 分布式缓存 这为许多高流量动态网站和web应用程序提供了动力, 通常由分布式散列的特定情况组成. 它们利用了一种算法 一致性哈希.

什么是一致性哈希? 它背后的动机是什么，为什么你应该关心?

在本文中, 我将首先回顾散列的一般概念及其目的, 然后是分布式哈希的描述和它所带来的问题. 然后，这将引导我们进入标题主题.

什么是哈希?

“哈希”是关于什么的? 梅里亚姆-韦伯斯特 定义名词 哈希 就像“切碎的肉和土豆混在一起，变成褐色。,动词为“把(如肉和土豆)切成小块”.” So, 撇开烹饪细节不谈, Hash的大致意思是“切碎和混合”——这正是这个专业术语的来源.

散列函数是映射一段数据的函数，通常描述某种对象, 通常是任意大小的另一段数据, 通常是整数, 被称为 散列码，或者简单地说 哈希.

例如，一些散列函数设计为散列字符串，输出范围为 0 .. 100，可以映射字符串 你好 比方说，号码 57, 再见，宝贝 到数字 33，并将任何其他可能的字符串转换为该范围内的某个数字. 因为可能的输入比输出多得多, 任何给定的数字都会有许多不同的字符串映射到它, 这种现象被称为 碰撞. 好的散列函数应该以某种方式“切碎和混合”输入数据(因此有了这个术语)，这样不同输入值的输出在输出范围内尽可能均匀地分布.

哈希函数有很多用途，每种用途可能需要不同的属性. 有一种哈希函数叫做 密码哈希函数, 哪些必须满足一组限制性属性并用于安全目的(包括密码保护等应用程序), 消息的完整性检查和指纹, 数据损坏检测, 等, 但这些都超出了本文的讨论范围.

非加密散列函数也有几种用途，最常见的是在 哈希表，这是我们关心的问题，我们将更详细地探讨.

介绍哈希表(哈希映射)

假设我们需要保存某个俱乐部所有成员的列表，同时能够搜索任何特定成员. 我们可以通过将列表保存在数组(或链表)中来处理它, 执行搜索, 迭代元素，直到找到所需的元素(我们可能根据它们的名称进行搜索), 例如). 在最坏的情况下, 这意味着要检查所有成员(如果我们要搜索的成员是最后一个的话), 或者根本不在场), 或者平均一半. 在复杂性理论中，搜索将具有复杂性 O(n), 对于一个小列表来说，这是相当快的, 但它会变得越来越慢，与成员数量成正比.

怎样才能改善呢? 假设所有这些俱乐部成员都有一个成员 ID，这恰好是一个连续的数字，反映了他们加入俱乐部的顺序.

假设通过 ID 如果可以接受，我们可以将所有成员放在一个数组中，它们的索引与它们的 IDS(例如，具有的成员 ID=10 会在索引处吗 10 在数组中). 这将允许我们直接访问每个成员，根本不需要搜索. 这将是非常有效的, 事实上, 尽可能的高效, 对应于尽可能低的复杂性, O(1)也被称为 常数时间.

但是，不可否认，我们的俱乐部成员 ID 这个场景有点做作. 如果 IDS是大的、非顺序的或随机的数字? 或者，如果搜索by ID 是不可接受的，我们需要按名称(或其他字段)搜索吗? 保持我们的快速直接访问(或接近)，同时能够处理任意数据集和较少限制的搜索条件，这当然是有用的.

这里是散列函数的救星. 可以使用合适的哈希函数将任意数据块映射为整数, 哪一个将扮演与我们的社员相似的角色 ID，尽管有一些重要的区别.

第一个, 一个好的散列函数通常具有较宽的输出范围(通常为, 32位或64位整数的整个范围), 因此，为所有可能的索引构建一个数组要么不切实际，要么根本不可能, 这是对记忆的巨大浪费. 为了克服这一点, 我们可以有一个合理大小的数组(比如, 只是我们期望存储的元素数量的两倍)并执行a 模 对散列进行操作以获得数组索引. 所以，指标是 index = 哈希(object) mod N,在那里 N 是数组的大小吗.

第二个, 对象哈希值不会是唯一的(除非我们使用固定的数据集和自定义的 完全哈希函数(但我们不会在这里讨论). 会有 碰撞 (通过取模操作进一步增加)，因此简单的直接索引访问将不起作用. 有几种方法可以处理此问题，但典型的方法是附加一个列表，通常称为 桶，以保存共享给定索引的所有对象.

我们有一个数组的大小 N，每个条目都指向一个对象桶. 要添加一个新对象，我们需要计算其 哈希模N，并检查结果索引处的桶，如果对象不存在，则添加该对象. 搜索一个对象, 我们也一样, 只是看看桶里的东西是否在那里. 这样的结构叫做a 哈希表, 尽管桶内的搜索是线性的, 一个适当大小的哈希表应该在每个桶中包含相当少的对象, 导致 几乎 常数时间访问(平均复杂度为 O (N / k),在那里 k 是桶的数量).

对于复杂对象，哈希函数通常不会应用于整个对象，而是应用于a 关键 而不是. 在我们俱乐部成员的例子中, 每个对象可能包含几个字段(如name, 年龄, address, 电子邮件, 电话), 但是我们可以选择, 说, 将电子邮件作为密钥，这样哈希函数将仅应用于电子邮件. 事实上, the 关键 need 不 be part of the object; it is common to store 关键/value pairs, 这里的键通常是相对较短的字符串, 这个值可以是任意的数据. 在这种情况下，哈希表或哈希映射被用作 字典，这是一些高级语言实现对象或关联数组的方式.

向外扩展:分布式哈希

既然我们已经讨论了散列，我们准备看看 分布式哈希.

在某些情况下, 将哈希表拆分为几个部分可能是必要的或可取的, 由不同的服务器托管. 这样做的主要动机之一是绕过使用单台计算机的内存限制, 允许构建任意大的哈希表(给定足够的服务器).

在这种场景中，对象(及其键)是 分布式 在多个服务器之间，因此得名.

一个典型的用例是实现内存缓存，例如 Memcached.

这种设置由一个缓存服务器池组成，缓存服务器托管许多键/值对，并用于提供对最初存储(或计算)在其他地方的数据的快速访问. 例如, 减少数据库服务器的负载，同时提高性能, 可以将应用程序设计为首先从缓存服务器获取数据, 只有在它不存在的情况下——这种情况被称为 缓存错过-求助于数据库, 运行相关查询并使用适当的键缓存结果, 这样下次需要的时候就能找到.

那么，分配是如何进行的呢? 使用什么标准来确定在哪些服务器上托管哪些密钥?

最简单的方法是取散列 模 服务器的数量. 也就是说, server = 哈希(关键) mod N,在那里 N 游泳池的大小是多少. 为了存储或检索密钥，客户端首先计算散列，应用 模N 操作, 并使用生成的索引联系相应的服务器(可能通过使用IP地址查找表). 请注意，用于密钥分发的散列函数必须在所有客户机上是相同的, 但是它不一定是缓存服务器内部使用的那个.

让我们看一个例子. 假设我们有三台服务器， A, B 和 C，我们有一些带哈希值的字符串键:

客户端想要检索关键的值 约翰. 它的。 哈希模3 is 2，因此必须与服务器联系 C. 在那里找不到键，因此客户机从源获取数据并添加它. 池子是这样的:

接下来，另一个客户端(或同一个客户端)希望检索关键的值 比尔. 它的。 哈希模3 is 0，因此必须与服务器联系 A. 在那里找不到键，因此客户机从源获取数据并添加它. 池子现在是这样的:

添加了剩余的键后，池看起来是这样的:

重复问题

这种分发方案简单、直观，而且运行良好. 也就是说，直到服务器数量发生变化. 如果其中一个服务器崩溃或不可用会发生什么? 当然，需要重新分发密钥以弥补丢失的服务器. 如果将一个或多个新服务器添加到池中，则同样适用;需要重新分发密钥以包含新服务器. 这对于任何分配方案都是正确的, 但是我们的简单模分布的问题是，当服务器数量发生变化时, 大多数 哈希对N取模 是否会更改，所以大多数密钥需要移动到不同的服务器. So, 即使删除或添加了单个服务器, 所有密钥都可能需要重新散列到不同的服务器中.

从前面的示例中，如果我们删除server C，我们需要重新散列所有的密钥 哈希模2 而不是 哈希模3，钥匙的新位置将变成:

注意，所有的键位置都改变了，而不仅仅是来自服务器的键位置 C.

在我们之前提到的典型用例中(缓存), 这就意味着, 突然之间, 密钥不会被找到，因为它们还没有出现在新位置.

So, 大多数查询将导致错误, 并且原始数据可能需要再次从源中检索并重新散列, 因此，在原始服务器(通常是数据库)上放置了沉重的负载。. 这可能会严重降低性能，并可能导致源服务器崩溃.

解决方案:一致哈希

那么，如何解决这个问题呢? 我们需要一个能做到这一点的分配方案 不 直接依赖于服务器的数量, 如此......以至于......。, 添加或删除服务器时, 需要重新定位的键的数量被最小化. 一个这样的方案——一个聪明而又出奇简单的方案——叫做 一致性哈希，最早被描述为 Karger等人. 麻省理工学院 在1997年的一篇学术论文中(根据维基百科).

一致性哈希是一种分布式哈希方案，它独立于分布式服务器或对象的数量运行 哈希表 在一个抽象的圆上给它们指定一个位置，或者 散列环. 这允许服务器和对象在不影响整个系统的情况下进行扩展.

假设我们将哈希输出范围映射到一个圆的边缘. 这意味着最小可能的哈希值, 零, 对应的角度是0吗, 可能的最大值(我们称之为 INT_MAX)对应的角度为2𝝅弧度(或360度), 所有其他哈希值都线性地适合于这两者之间的某个地方. 所以，我们可以取一个键，计算它的哈希值，然后找出它在圆边缘上的位置. 假设一个 INT_MAX of 10¹⁰ (举个例子)，我们上一个例子中的键看起来像这样:

现在想象一下，我们也把服务器放在圆的边缘, 通过伪随机分配它们的角度. 这应该以可重复的方式完成(或者至少以所有客户端在服务器角度上达成一致的方式)。. 一种方便的方法是对服务器名称(或IP地址)进行散列, 或者某个ID)——就像我们对任何其他钥匙所做的那样——来得出它的角度.

在我们的例子中，事情可能是这样的:

因为我们在同一个圆圈上有对象和服务器的密钥, 我们可以定义一个简单的规则将前者与后者关联起来:每个对象键都属于键最接近的服务器, 逆时针方向(或顺时针方向, 取决于使用的约定). 换句话说, 查找向哪个服务器请求给定的密钥, 我们需要在圆圈上找到钥匙然后沿着上升的角度移动直到我们找到服务器.

在我们的例子中:

从编程的角度来看, 我们要做的是保存一个排序的服务器值列表(可以是任何实际间隔内的角度或数字), 遍历该列表(或使用二分查找)以查找值大于的第一个服务器, 或者等于, 所需要的键. 如果没有找到这样的值，则需要绕行，从列表中取出第一个值.

确保对象键在服务器之间均匀分布, 我们需要应用一个简单的技巧:不分配一个, 但是每个服务器都有很多标签(角度). 所以不用标签 A, B 和 C，我们可以说， A0 .. A9, B0 .. B9 和 C0 .. C9，都散布在圆圈上. 增加标签(服务器密钥)数量的因子，称为 重量, 根据具体情况(甚至每个服务器可能不同)来调整每个服务器上的密钥的概率. 例如，if server B 是其他人的两倍吗, 它可以被分配两倍的标签, 结果就是, 它最终会容纳两倍的对象(平均).

在我们的示例中，我们假设所有三台服务器的权重为10(这对于三台服务器很适用), 适用于10到50台服务器, 重量在100到500之间会更好, 更大的池可能需要更高的权重):

那么，这种循环方法的好处是什么呢? 想象一下服务器 C 删除. 为了解释这一点，我们必须去掉标签 C0 .. C9 从圆圈开始. 这将导致以前与已删除标签相邻的对象键现在被随机标记 Ax 和 Bx，将它们重新分配给服务器 A 和 B.

但其他对象键呢，那些原本属于 A 和 B? 没有什么! 这就是它的美妙之处:没有 Cx 标签不会以任何方式影响这些键. So, 删除服务器将导致其对象键被随机重新分配给其他服务器, 其他钥匙都不动:

如果不是删除服务器，而是添加服务器，也会发生类似的情况. 如果我们想添加服务器 D 以我们的例子(比如说，作为 C)，我们需要添加标签 D0 .. D9. 结果将是大约三分之一的现有密钥(都属于 A or B)将被重新分配至 D其余的都保持不变:

这就是一致性哈希解决重新哈希问题的方式.

一般来说，只有 k/N 键需要重新映射 k 键的个数是和吗 N 是服务器的数量(更具体地说，是初始和最终服务器数量的最大值).

什么下一个?

我们在使用分布式缓存优化性能时观察到这一点, 缓存服务器的数量可能会发生变化(其原因可能是服务器崩溃), 或者需要添加或删除服务器以增加或减少总体容量). 通过使用一致散列在服务器之间分发密钥, 如果发生这种情况，我们可以放心, 被重新散列的键的数量——因此, 对原始服务器的影响将被最小化, 防止潜在的停机时间或性能问题.

有几个系统的客户端, 比如Memcached和Redis, 这包括对开箱即用的一致散列的支持.

另外, 你可以自己实现这个算法, 用你选择的语言, 一旦理解了这个概念，这应该是相对容易的.

如果你对数据科学感兴趣，Toptal有一些关于这个主题的最好的文章 博客