你知道哈希算法，但你知道一致性哈希吗？

前言

假如让你为淘宝这种数据量非常大的公司的设计一个可扩展的数据存储系统，你该如何存储和管理数据呢？总不能放在单个服务器上吧，肯定放不下，必然需要水平扩展。那么这样就带来一个问题，这个数据要存储在哪个服务器上呢？这就引入了本文的主题一致性哈希算法，可能你没听过，那么本文就通过一个简单的例子带你一步一步认识它。

数据线性分布

假如我们现在有一组服务器，我们想提出一个在这组服务器之间进行数据存储和查找的策略。让我们从一个最最简单的方案开始。假设我们一个接一个地填满服务器，即仅当当前服务器已满时，我们才开始将数据写入下一个服务器。

在下图中，我们有一个简单的服务器，一次只能存储 4 条记录。当服务器变满时，我们添加一个新服务器并向其添加新数据。

好吧，这种方法在任何服务器上写入数据时都非常有效。当您被要求读取特定数据时会发生什么？您需要识别存储给定数据的服务器，然后获取它。你如何识别服务器？您会遍历所有服务器并线性扫描每个服务器吗？这会影响读取性能。

例如：在上面的例子中，如果你被要求查找“New York”，因为键和服务器之间没有直接映射，你将不得不线性扫描所有服务器并搜索这个键。

这样的效率是不是很糟糕，那么有没有更好的解决方案呢。

数据哈希分布

哈希算法想必大家都知道，Java中的HashMap就是采用的哈希算法。那么根据这个思路，我们提出了一个新的解决方案，数据根据哈希进行存储管理。

我们看到如果我们有 N 个服务器，则获取记录的时间复杂度将为O(N)。我们希望在O(1)中高效地读写数据。我们首先想到的是提供O(1)查找和写入的HashMap数据结构。

让我们看看 Hashing 是否可以解决我们的问题。假设我们有 N 个存储数据的服务器和一个具有分发数据策略的应用程序。该方法类似于HashMap使用的方法。首先，对键进行哈希处理，然后确定数据将存放的存储桶。应用程序将首先对密钥进行哈希处理，然后通过计算hash(data) % N来确定哪个服务器。

上述算法将给出写入数据的服务器编号。此外，在检索数据时，它将使用相同的逻辑，获取服务器编号并获取数据。读取和写入都在O(1)中完成。

让我们来看一个例子。假设我们有三个名为 S0、S1 和 S2 的服务器。我们的钥匙是世界城市名称。使用哈希，我们计算需要将密钥分配到的存储桶或服务器。

密钥的哈希和计算桶

密钥分配

但这在分布式系统中总是有效的吗？我们会遇到以下问题：

• 如果我们添加更多服务器，则hash(data) % N会有所不同。这意味着我们将不得不在添加新服务器时重新分配所有数据。
• 如果删除其中一台服务器，我们将遇到同样的问题。由于此处服务器的数量 N 是可变的，因此所有密钥都会受到影响。

以下是添加新服务器时发生的情况的说明。随着服务器数量从 3 台增长到 4 台，桶的计算逻辑将变为Hash % 4。

新旧密钥分配

在添加新服务器时，我们观察到三个键中的两个受到了影响。如果我们添加一个新服务器，键Madrid的桶将是 0 (S0) 而不是 1(S1)。我们必须将此密钥移动到服务器 S1 以确保我们的应用程序找到它。因此，我们必须重新散列所有现有密钥并将它们分配给不同的服务器。在最坏的情况下，这可能会影响系统中的所有密钥。

看来通过哈希算法将数据分发到不同服务器中还是不大行，那还有什么更好的办法呢？这边就要隆重介绍一致性哈希。

什么是一致性哈希？

当我们想要动态添加或删除服务器时，一致性哈希解决了我们的问题。在简单散列的情况下，添加或删除服务器将影响存储在系统中的所有 M 密钥。然而，一致性哈希确保只有 M/N 键受到影响，其中 N 是服务器的数量。

一致性哈希使密钥的分布与系统使用的服务器数量无关。因此，我们可以在不影响整个系统的情况下扩大或缩小规模。

从根本上说，一致性哈希使用哈希环。该算法将每个服务器映射到圆上的一个点。它首先使用服务器的 IP 地址，计算其散列值并为其分配圆上的一个点（角度）。以下是如何为 3 个服务器 S1、S2、S3 计算角度的简单说明：

将服务器分配给哈希环上的点

此外，每个密钥都使用相同的哈希算法进行哈希处理并在服务器上分配一个点。对于每个散列键，我们按顺时针方向移动并找到最近的服务器并分配给它。

将密钥分配给哈希环上的点

我们得到以上密钥集的以下分配：

将密钥分配给服务器

以下是上述密钥分配到哈希环上不同服务器的图形表示：

在哈希环上将密钥分配给服务器

从上图可以看出，我们从每个键顺时针方向移动，找到它的服务器。

扩展和添加新服务器

如前一节所述，我们首先计算服务器IP地址的哈希值并找到它在圆上的位置。例如：如果我们添加一个服务器S4，发现它位于圆上的S2和S0之间。此外，我们重新分配 S0 的键，其角度小于 S3，或者换句话说，在圆上出现在 S3 之前。

下图说明了此过程，其中添加了一个新服务器 S3，它位于 S2 和 S0 之间。最初，键Mumbai被分配给服务器 S0。在添加 S3 时，我们看到从键Mumbai顺时针方向遇到的第一个服务器是 S3，因此我们将此键分配给 S3。

添加新服务器 S3

从上面可以看出，添加新服务器不会影响所有密钥。只有散列环上两个服务器之间出现的密钥需要重新分配。

删除现有服务器

当删除现有服务器时，只需要重新分配属于该服务器的密钥。对于属于被移除服务器的key，按顺时针方向找到哈希环上的下一个服务器。此外，然后将密钥分配给新服务器。

下图说明了删除现有服务器的过程：

删除服务器 S1

在上图中，删除了服务器 S1。键New York被分配给服务器 S1。删除 S1 后，我们从键New York中找到第一个服务器并找到服务器 S2。因此，键New York被重新分配给服务器 S2。

与普通散列不同，删除服务器不需要重新散列所有密钥。只需重新分配已移除服务器的密钥。

虚拟节点

我们看到，当一个节点被移除时，分配给这个节点的所有键都会被移动到哈希环中的下一个节点。通常，在删除一个节点时，数据分布会变得不均匀，并且其中一个节点的负载会增加。

在上述情况下，如果我们从系统中删除 S0，则键London将映射到服务器 S2。最终，我们会发现 S2 处理三个密钥，而 S1 只管理一个密钥。因此，数据分布不均匀。

删除 S0 会给 S2 带来更多负载

在理想情况下，当有M个密钥和N个服务器时，每个服务器必须有接近 M/N 个密钥。因此，添加或删除节点会影响系统中的最大 M/N 键。为了确保接近理想的分布，我们在系统中引入了虚拟节点。每个物理节点在哈希环上都有多个虚拟节点。

我们使用多个哈希函数来查找虚拟节点在哈希环上的位置。每个服务器都用 Sij 表示，其中 i 表示实际服务器编号，j 代表其虚拟副本。例如：对于第一台服务器，虚拟副本将是 S00、S01、S02、S03 等。我们使用不同的哈希函数来计算每个虚拟副本的哈希值。

在上面的示例中，我们得到以下虚拟服务器分配：

哈希环上的虚拟服务器

从上图可以看出，服务器S1的虚拟副本是S10、S12和S13。这同样适用于服务器 S0。这导致节点之间的数据分布接近均匀。

对于给定的密钥，如果哈希环中的下一个服务器是 S12，则它将分配给第一个物理服务器。一般而言，分配给虚拟服务器 Sij 的密钥将存储在物理服务器 Si 上。

总结

本文带大家认识了一致性哈希算法，一致性哈希于 1997 年推出，它已经在许多分布式系统中的得到了应用。Amazon的Dynamo DB中使用它作分区组件。此外，Apache Cassandra和Voldermort等开源应用程序使用它进行数据分区。