一致哈希指南

本文概述

• 什么是散列？
• 哈希表简介(哈希图)
• 向外扩展：分布式哈希
• 重新哈希问题
• 解决方案：一致的哈希
• 接下来是什么？

近年来, 随着诸如云计算和大数据之类的概念的出现, 分布式系统得到了普及和相关性。

一种此类系统, 为许多高流量动态网站和Web应用程序提供动力的分布式缓存通常由分布式哈希的一种特殊情况组成。这些利用称为一致性哈希的算法。

什么是一致性哈希？背后的动机是什么, 为什么要关心呢？

在本文中, 我将首先回顾散列的一般概念及其用途, 然后描述分布式散列及其带来的问题。反过来, 这将引导我们进入标题主题。

什么是散列？

“散列”到底是什么？ Merriam-Webster将名词哈希定义为”切碎的肉与土豆混合并烤成褐色”, 而将动词定义为”将(切成肉和土豆)切成小块”。因此, 除了烹饪细节外, 哈希大致意味着”剁碎和混合”, 而这恰恰是技术术语的来源。

哈希函数是一种功能, 可以将一段数据(通常描述某种对象, 通常具有任意大小)映射到另一段数据, 通常是一个整数(称为哈希码), 也可以简称为哈希。

例如, 某些散列函数设计为对字符串进行散列, 其输出范围为0 .. 100, 可以将字符串Hello映射到数字57, 例如Hasta la vista, baby映射到数字33, 并将任何其他可能的字符串映射到该范围内的一些数字。由于可能的输入比输出更多, 因此任何给定的数字都将映射许多不同的字符串, 这种现象称为冲突。良好的哈希函数应以某种方式”砍切并混合”(因此使用术语)输入数据, 以使不同输入值的输出在输出范围内尽可能均匀地分布。

哈希函数有许多用途, 对于每种用途, 可能需要不同的属性。有一种哈希函数称为加密哈希函数, 必须满足一组限制性属性并用于安全目的-包括密码保护, 完整性检查和消息指纹以及数据损坏检测等应用, 但是这些不在本文的讨论范围之内。

非加密哈希函数也有多种用途, 最常见的是在哈希表中的使用, 这是我们关心的一种, 我们将对此进行更详细的探讨。

哈希表简介(哈希图)

想象一下, 我们需要保留某个俱乐部的所有成员的列表, 同时能够搜索任何特定的成员。我们可以通过将列表保留在数组(或链接列表)中来进行处理, 然后执行搜索, 对元素进行迭代, 直到找到所需的元素为止(例如, 我们可能基于其名称进行搜索)。在最坏的情况下, 这意味着要检查所有成员(如果我们要搜索的成员是最后一个成员, 或者根本不存在), 或者平均检查一半。用复杂度理论的术语来说, 搜索将具有复杂度O(n), 并且对于一个较小的列表来说, 搜索速度会相当快, 但是与成员数成正比, 搜索速度会越来越慢。

如何改善呢？假设所有这些俱乐部会员都有一个会员ID, 该ID恰好是反映他们加入俱乐部顺序的序号。

假设按ID进行搜索是可以接受的, 我们可以将所有成员放置在数组中, 其索引与ID匹配(例如, ID = 10的成员将在数组的索引10处)。这将使我们可以直接访问每个成员, 而无需进行任何搜索。实际上, 这将是非常有效的, 它尽可能地高效, 对应于可能的最低复杂度O(1), 也称为恒定时间。

但是, 诚然, 我们的俱乐部会员编号方案有些人为设计。如果ID是大数, 非顺序数或随机数怎么办？或者, 如果不能按ID搜索, 而我们需要按名称(或其他字段)搜索？保持我们的快速直接访问(或接近的东西), 同时能够处理任意数据集和限制性较小的搜索条件, 无疑会很有用。

散列函数可助你一臂之力。可以使用适当的哈希函数将任意数据映射为整数, 尽管有一些重要区别, 但它将起到与俱乐部会员ID相似的作用。

首先, 良好的哈希函数通常具有较宽的输出范围(通常是32或64位整数的整个范围), 因此为所有可能的索引构建数组将是不切实际或根本不可能的, 并且会浪费大量内存。为了克服这个问题, 我们可以有一个合理大小的数组(例如, 只是我们希望存储的元素数量的两倍), 并对散列执行取模运算以获取数组索引。因此, 索引将是index = hash(object)mod N, 其中N是数组的大小。

其次, 对象的哈希值不会是唯一的(除非我们使用固定的数据集和定制的完美哈希函数, 但我们不在此讨论)。将会发生冲突(通过模运算会进一步增加冲突), 因此简单的直接索引访问将无法正常工作。有几种处理方法, 但是典型的方法是将一个列表(通常称为存储桶)附加到每个数组索引, 以保存共享给定索引的所有对象。

因此, 我们有一个大小为N的数组, 每个条目都指向一个对象存储桶。要添加新对象, 我们需要计算其哈希模N, 并在结果索引处检查存储桶, 如果尚不存在则添加该对象。要搜索对象, 我们做同样的事情, 只是查看存储桶中是否有对象。这种结构称为哈希表, 尽管存储桶中的搜索是线性的, 但适当大小的哈希表在每个存储桶中应具有相当少量的对象, 从而导致几乎恒定的时间访问(平均复杂度为O(N / k ), 其中k是存储桶数)。

对于复杂的对象, 哈希函数通常不应用于整个对象, 而是应用于键。在我们的俱乐部会员示例中, 每个对象可能包含多个字段(例如姓名, 年龄, 地址, 电子邮件, 电话), 但是我们可以选择说电子邮件作为密钥, 以便将哈希函数应用于电子邮件只要。实际上, 密钥不必是对象的一部分；它可以是对象的一部分。通常存储键/值对, 其中键通常是相对较短的字符串, 并且值可以是任意数据。在这种情况下, 哈希表或哈希图被用作字典, 这就是某些高级语言实现对象或关联数组的方式。

向外扩展：分布式哈希

既然我们已经讨论了哈希, 那么我们就可以研究分布式哈希了。

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

在这种情况下, 对象(及其键)分布在多个服务器之间, 因此也就是名称。

一个典型的用例是实现内存中的缓存, 例如Memcached。

这种设置由一个缓存服务器池组成, 这些池托管许多键/值对, 并用于快速访问最初在其他位置存储(或计算)的数据。例如, 为了减少数据库服务器上的负载并同时提高性能, 可以将应用程序设计为首先从缓存服务器中获取数据, 并且仅在不存在的情况下(这种情况称为缓存未命中)进行重新整理。数据库, 运行相关查询并使用适当的密钥缓存结果, 以便下次需要时可以找到它。

现在, 如何进行分配？使用什么标准来确定在哪些服务器上托管哪些密钥？

最简单的方法是对服务器数量进行哈希模运算。也就是说, server = hash(key)mod N, 其中N是池的大小。为了存储或检索密钥, 客户端首先计算哈希, 应用N模运算, 然后使用结果索引与适当的服务器联系(可能使用IP地址查找表)。请注意, 用于密钥分发的散列函数在所有客户端上必须相同, 但是不必与缓存服务器内部使用的散列函数相同。

让我们来看一个例子。假设我们有三个服务器, A, B和C, 并且我们有一些带有哈希值的字符串键：

客户端希望检索键john的值。它的哈希模3为2, 因此它必须与服务器C联系。在该服务器上找不到密钥, 因此客户端从源中获取数据并将其添加。池看起来像这样：

接下来, 另一个客户(或同一个客户)想要检索主要账单的值。它的哈希模3为0, 因此它必须与服务器A联系。在那里找不到密钥, 因此客户端从源获取数据并将其添加。泳池现在看起来像这样：

添加其余键后, 池如下所示：

重新哈希问题

这种分配方案简单, 直观且效果良好。也就是说, 直到服务器数量发生变化。如果其中一台服务器崩溃或不可用怎么办？当然, 需要重新分配密钥以解决缺少的服务器。如果将一个或多个新服务器添加到池中, 则同样适用；需要重新分配键以包括新服务器。对于任何分配方案来说都是如此, 但是我们简单的模分配的问题在于, 当服务器数量发生变化时, 大多数哈希模N将发生变化, 因此大多数密钥将需要移至其他服务器。因此, 即使删除或添加了单个服务器, 也可能需要将所有密钥重新映射到其他服务器中。

在上一个示例中, 如果删除了服务器C, 则必须使用哈希模2而不是哈希模3来重新哈希所有密钥, 并且密钥的新位置将变为：

请注意, 所有关键位置都发生了变化, 不仅是服务器C中的位置。

在我们前面提到的典型用例(缓存)中, 这意味着突然之间将找不到密钥, 因为它们尚未出现在新位置。

因此, 大多数查询都将导致未命中, 并且原始数据可能需要再次从源中检索以进行重新哈希处理, 从而对原始服务器(通常是数据库)造成沉重的负担。这可能会严重降低性能, 并可能导致原始服务器崩溃。

解决方案：一致的哈希

那么, 如何解决这个问题呢？我们需要一种不直接依赖于服务器数量的分发方案, 以便在添加或删除服务器时, 需要重定位的密钥数量最小化。一种这样的方案(一种聪明而又令人惊讶的简单方案)称为一致性哈希, 最早由Karger等人描述。麻省理工学院在1997年发表的学术论文中(根据Wikipedia)。

一致性哈希是一种分布式哈希方案, 通过为服务器或对象分配抽象圈或哈希环上的位置, 可以独立于服务器或对象的数量进行操作。这允许服务器和对象扩展而不影响整个系统。

假设我们将哈希输出范围映射到圆的边缘。这意味着最小可能的散列值零将对应于零角度, 最大可能值(一些大整数, 我们称为INT_MAX)将对应于2????弧度(或360度)角度, 而所有其他哈希值将线性地介于两者之间。因此, 我们可以选择一个密钥, 计算其哈希值, 然后找出它在圆的边缘上的位置。假设INT_MAX为1010(例如), 上例中的键如下所示：

现在想象一下, 我们也通过伪随机地分配服务器角度, 将服务器放置在圆的边缘。这应该以可重复的方式进行(或至少以所有客户端都同意服务器角度的方式进行)。一种简便的方法是对服务器名称(或IP地址或某些ID)进行哈希处理(就像我们对其他任何键所做的那样), 以得出其角度。

在我们的示例中, 事情可能看起来像这样：

由于我们在同一圆圈上拥有对象和服务器的密钥, 因此我们可以定义一个简单的规则来将前者与后者相关联：每个对象密钥将在逆时针方向上属于最接近其密钥的服务器(或顺时针, 取决于所使用的约定)。换句话说, 要找出哪个服务器要求给定密钥, 我们需要将密钥定位在圆上并沿上升角度方向移动, 直到找到服务器为止。

在我们的示例中：

从编程的角度来看, 我们要做的是保留服务器值的排序列表(可以是任何实际间隔中的角度或数字), 然后遍历该列表(或使用二进制搜索)以找到值更大的第一台服务器。大于或等于所需密钥的密钥。如果找不到这样的值, 则需要包装, 从列表中取出第一个。

为了确保对象密钥在服务器之间平均分配, 我们需要应用一个简单的技巧：为每个服务器分配一个标签而不是多个标签(角度)。因此, 不用标签A, B和C, 我们可以将A0 .. A9, B0 .. B9和C0 .. C9都沿着圆点散布。增加标签(服务器密钥)数量的因素(称为权重)取决于情况(对于每个服务器甚至可能有所不同), 以调整最终出现在每个服务器上的密钥的概率。例如, 如果服务器B的功能是其余功能的两倍, 则可以为其分配两倍的标签, 结果, 它最终将容纳两倍的对象(平均)。

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

那么, 所有这种循环方式的好处是什么？想象一下服务器C被删除了。为了解决这个问题, 我们必须从圆上删除标签C0 .. C9。这导致以前与已删除标签相邻的对象键现在被随机标记为Ax和Bx, 并将它们重新分配给服务器A和B。

但是其他对象键(最初属于A和B的对象键)会发生什么呢？没有！那就是它的美：没有Cx标签不会以任何方式影响这些键。因此, 删除服务器会导致其对象键被随机地重新分配给其余服务器, 而其他所有键则保持不变：

如果不是添加服务器, 而是添加服务器, 则会发生类似的情况。如果要将服务器D添加到示例中(例如, 作为C的替代), 则需要添加标签D0 .. D9。结果是, 大约三分之一的现有密钥(都属于A或B)将被重新分配给D, 其余的将保持不变：

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

通常, 当k是键的数量而N是服务器的数量(更具体地说, 是初始和最终服务器数量的最大值)时, 仅需要重新映射k / N个键。

接下来是什么？

我们观察到, 使用分布式缓存优化性能时, 缓存服务器的数量可能会发生变化(原因可能是服务器崩溃, 或者需要添加或删除服务器以增加或减少总容量)。通过使用一致的哈希在服务器之间分配密钥, 我们可以放心, 如果发生这种情况, 将最大程度地减少重新加密的密钥的数量(因此对原始服务器的影响), 从而避免潜在的停机时间或性能问题。

有一些系统的客户端, 例如Memcached和Redis, 它们都支持开箱即用的一致性哈希。

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

如果你对数据科学感兴趣, srcmini在博客上提供了有关该主题的一些最佳文章。