一致性哈希指南

作者: Juan Pablo Carzolio

译者: java达人

来源: https://www.toptal.com/big-data/consistent-hashing

近年来，随着云计算、大数据等概念的出现，分布式系统得到了普及和应用。

其中一种类型的系统是分布式缓存，它支持许多高流量动态网站和web应用程序，通常由一种特定的分布式哈希实现，一种一致性哈希算法。

什么是一致性哈希?它背后的动机是什么?你为什么要关注它?

在本文中，我将首先回顾哈希的一般概念及其用途，然后描述分布式哈希及其所涉及的问题，引出了我们的主题。

什么是哈希

哈希是什么意思?韦氏词典将“hash”一词定义为“肉丁和土豆混在一起烧成棕色”，而动词则是“将东西(如肉和土豆)切成碎片”。所以，撇开烹饪细节不谈，hash大致的意思是“切碎和混合”—这正是这个技术术语的来源。

哈希函数是将一段数据(常是描述某种类型的对象，通常是任意大小的)映射到另一段数据(通常是一个整数，称为哈希码，或者简称哈希)。

例如，一些哈希函数设计用于哈希字符串，输出范围为0 .. 100的数、可以将字符串 Hello 映射到数字57, Hasta la vista, baby映射到数字 33，将其他任何可能的字符串映射到该范围内的某个数字。由于可能的输入比输出多得多，任何给定的数字都会有许多不同的字符串映射到它，这就是所谓的碰撞现象。好的哈希函数应该以某种方式“切碎并混合”输入的数据，以便不同输入值的输出尽可能均匀地分布在输出值范围内。

哈希函数有许多用途，对于每种用途，可能需要不同的属性。有一种叫加密哈希函数,它必须严格满足一组属性，用于安全目的,如密码保护、消息的完整性检查和指纹识别,数据损坏检测等,这些超出了本文讨论范围。

非加密哈希函数也有几种用途，最常见的是它们在哈希表中的使用，这是我们关心的问题，我们将更详细地进行探讨。

介绍Hash Table(Hash Map)

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

如何改进呢?假设所有这些俱乐部成员都有一个成员ID，它恰好是一个反映其加入俱乐部顺序序列号。

假设可以接受按 ID进行搜索，我们可以将所有成员放入一个数组中，其索引与ID匹配(例如，ID=10的成员位于数组索引10处)。这将允许我们直接访问每个成员，根本不需要搜索。这将是非常高效的，事实上，越是高效，对应于越小的复杂度，O(1)也被称为常数时间。

但是，必须承认，俱乐部成员ID场景是有些人为的。如果id很大、非顺序的或是随机数，或者如果不能接受按ID进行搜索，而需要按名称(或其他字段)进行搜索，怎么办?需要保持我们的快速直接访问(或其他类似的访问)，同时能够处理任意数据集和较少限制的搜索条件。

这就是哈希函数发挥作用的地方。一个合适的哈希函数可以将任意的数据映射到一个整数，这个整数将扮演类似于我们的俱乐部成员ID的角色，尽管有一些重要的区别。

首先，一个好的哈希函数通常有一个宽泛的输出范围(通常是32位或64位integer范围)，所以为所有可能的索引构建一个数组要么不切实际，要么根本不可能，而且会浪费大量内存。为了克服这个问题，我们可以有一个合理大小的数组(比方说，只需要两倍于我们预期存储的元素的数量)，并执行Hash取模操作来获得数组索引。索引为index = hash(object) mod N，其中N是数组的大小。

其次，对象哈希不是唯一的(除非我们使用固定的数据集和自定义的完美哈希函数，但我们不会在这里讨论这个)。它们会有冲突(取模操作进一步增加冲突)，因此简单用索引直接访问将无法工作。有几种方法可以解决这个问题，一种典型的方法是将一个列表(通常称为bucket)附加到每个数组索引，以保存共享同一个索引的所有对象。

因此，我们有一个大小为N的数组，每个条目都指向一个对象桶。要添加一个新对象，我们需要计算它的hash modulo N，并检查结果索引处的bucket，如果还没有对象，则添加该对象。要搜索一个对象，我们也要做同样的事情，即查看桶中是否有对象。这样的结构称为哈希表，尽管桶内的搜索是线性的，但是哈希表大小适当的话每个桶应该有相当少的对象，从而产生几乎是常数时间的访问(平均复杂度为O(N/k，其中k是桶的数量)。

对于复杂对象，哈希函数通常不计算整个对象，而是对键进行计算。在我们的club成员示例中，每个对象可能包含几个字段(比如姓名、年龄、地址、email、电话)，但是我们可以选择email作为键，这样哈希函数只应用于email。事实上，键不需要是对象的一部分;通常存储键/值对时，键是相对较短的字符串，而值可以是任意数据块。在这种情况下，哈希表或hash map作为字典使用，这也是一些高级语言创建对象或关联数组的方式。

扩展：分布式哈希

既然我们已经讨论了哈希，现在我们准备研究分布式哈希。

在某些情况下，可能必须或者希望将哈希表拆分为由不同服务器承载的多个部分。这样做的主要动机之一是绕过只使用单台计算机的内存限制，允许构造任意大的哈希表(给定足够的服务器)。

在这种情况下，对象(及其key)分布在多个服务器中，因此称为分布式哈希。

这方面的一个典型用例是内存缓存(如Memcached)的实现。

这种配置由一个缓存服务器池组成，这些缓存服务器托管许多键/值对，用于提供对原来在其他地方存储(或计算)的数据的快速访问。例如,为了减少对数据库服务器的负载,同时提高性能,应用程序可以设计先从缓存服务器中获取数据,只有当数据不存在时—这种情况称为缓存未命中—才请求数据库，运行相关查询并使用适当的键缓存结果，以便下次需要时可以找到它。

那么，分布式是如何实现的呢?使用什么标准来确定要在哪些服务器上驻留哪些key?

最简单的方法根据服务器数量哈希取模。即 server = hash(key) mod N，其中 N是池的大小。要存储或检索密钥，客户机首先计算哈希，使用modulo N操作，并使用生成的索引与合适的服务器关联(可能通过使用IP地址查找表)。注意，用于key分发的哈希函数在所有客户端上必须都是相同的，但是缓存服务器内部使用的哈希函数不一定相同。

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

客户端想要检索key为 john的值。它 hash modulo 3是2，所以它必须与服务器C关联。key不存在，所以客户端从数据源获取数据并添加。服务器池结果如下:

接下来，另一个客户端(或同一客户端)希望检索key 为bill的值。它hash modulo 3结果是0，所以它必须与服务器A关联。key未找到，所以客户端从数据源获取数据并添加。服务器池结果如下:

在添加了其余的key之后，服务器池结果如下:

Rehash问题

这种分配方案简单、直观、工作良好,但是如果服务器的数量发生变化就不行了。如果其中一个服务器崩溃或变得不可用，会发生什么?当然需要重新分发key来弥补损失的服务器。如果将一台或多台新服务器添加到池中，情况也是如此;需要重新分发key以包含新服务器。任何分发方案都会有这种问题，但是我们这种简单的取模分发方案的问题是，当服务器的数量发生变化时，大多数hashes modulo N 结果将发生变化，因此大多数key将需要移动到不同的服务器。因此，即使删除或添加了单个服务器，也可能需要将所有key rehash到不同的服务器中。

从我们之前的例子中，如果我们删除了服务器C，我们将不得不根据 hash modulo 2而不是hash modulo 3对所有key进行rehash，key的新位置如下:

注意，所有key位置都发生了变化，不仅仅是在服务器 C的key的位置。

在我们前面提到的典型用例(缓存)中，这意味着，key突然都找不到了，因为它们还没有被存放在新的位置。

因此，大多数查询将不会命中，并且可能需要重新从数据源检索原始数据来rehash，进而给源服务器(通常是数据库)带来沉重的负载。这可能会严重降低性能，导致源服务器崩溃。

解决方案：一致性哈希

那么，如何解决这个问题呢?我们需要一个不直接依赖于服务器数量的分发方案，这样，在添加或删除服务器时，需要重新定位的key的数量就可以最小化。有一个这样的方案—一个聪明的，却非常简单的方案—被称为一致性哈希，它首次由麻省理工学院的Karger等人在1997年的一篇学术论文中提出(根据维基百科)。

一致性哈希是一种分布式哈希方案，它在一个抽象的圆或哈希环上为服务器或对象分配一个位置，它的操作不依赖于分布式哈希表中服务器或对象的数量。这允许服务器和对象在不影响整个系统的情况下进行伸缩。

假设我们将哈希输出范围映射到圆环的边缘。这意味着最小散列值零将对应于零角，其最大可能值(我们称为INT_MAX的大整数)对应于2?(或360度)的角,所有其他的哈希值线性地介于两者之间。我们可以取出一个key值，计算它的哈希值，然后找出它在圆环的位置。假设 INT_MAX 为1010(举例子)，我们前面的例子中的key应该是这样的:

现在假设我们将服务器也放置在圆环，通过伪随机方式分配它们所在的角度。这应该以一种可重复的方式完成(或者至少让所有客户端都在服务器的角度问题上达成一致)。一种方便的方法是根据服务器名称取哈希(或IP地址，或某些ID)—就像我们对任意其他key所做的操作那样—来找出它的角度。

在我们的例子中，也许是这样的:

因为我们的对象和服务器都有key放在在同一个环,我们可以定义一个简单的规则将前者与后者关联:每个对象key将归属于在逆时针方向上(或顺时针,取决于约定)key最接近的服务器。换句话说，要找到向哪台服务器获取key，我们需要在环上定位key，并沿着角度升序方向移动，直到找到那台服务器为止。

示例如下：

从编程的角度来看,我们要做的是保持服务器值的排序列表(可以是任何真正间隔的角度或数字),遍历这个列表(或使用二分搜索)，找到大于或等于key的第一个服务器值。如果没有找到这样的值，我们需要从列表中提取第一个值。

为了确保对象key在服务器之间均匀分布，我们需要应用一个简单的技巧:为每个服务器分配多个标签(角度)，而不是一个。所以我们不用标签 A, B，C，我们可以用A0 .. A9, B0 .. B9和C0 .. C9, 所有的都沿着圆环散布。增加的标签(服务器key)数量，称为权重，它根据具体情况(甚至可能对每个服务器来说是不同的)来调整每台服务器上key结束的概率。例如，如果服务器B的性能是其他服务器的两倍，那么它可以被分配两倍的标签，这样它将持有两倍的对象(平均而言)。

在我们的例子中，我们假设所有3个服务器的权值都是10(这对于3个服务器很有效，10到50个服务器时，权值在100到500之间会更好，更大的池可能需要更高的权值):

那么，这种使用环的方法有什么好处呢?假设服务器C被删除。为了说明这一点，我们必须删除环上标签C0 .. C9。这将导致先前与被删除标签相邻的对象key，现在被随机标记为Ax 和 Bx，并被重新分配到服务器 A和 B。

但是那些原本属于 A和B的key怎么办呢?没有什么变化!这就是它的美妙之处:没有Cx标签，并不影响这些key。因此，删除一个服务器会导致它的对象key被随机地重新分配给其他服务器，而其他key则保持不变。

如果不删除服务器，而是添加一个服务器，也会发生类似的情况。如果我们想将服务器D添加到我们的示例中(例如，作为对C的替换)，我们需要添加标签D0 .. D9。其结果是，大约三分之一的现有key(都属于A或B)将被重新分配给D，其余的key将保持不变:

这就是一致性哈希解决rehash问题的方法。

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

后续

我们注意到，当使用分布式缓存优化性能时，缓存服务器的数量可能会发生变化(原因可能是服务器崩溃，或者需要添加或删除服务器来增加或减少总体容量)。通过使用一致性哈希来在服务器之间分发key，我们可以对此放心，如果发生这种情况，rehash的key数量(同时对数据源服务器的影响)将被最小化，从而防止可能的停机或性能问题。

几个像Memcached和Redis系统的客户端，包含对一致性哈希开箱即用的支持。

或者，您可以使用您选择的语言自己实现算法，一旦概念被理解，这应该是比较容易的。

如果你对数据科学感兴趣，Toptal博客上有一些关于这方面主题的最好的文章(https://www.toptal.com/developers/blog/data-science-and-databases)

java达人

ID：drjava

（长按或扫码识别）