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

　　前言
　　假如让你为淘宝这种数据量非常大的公司的设计一个可扩展的数据存储系统，你该如何存储和管理数据呢？总不能放在单个服务器上吧，肯定放不下，必然需要水平扩展。那么这样就带来一个问题，这个数据要存储在哪个服务器上呢？这就引入了本文的主题一致性哈希算法，可能你没听过，那么本文就通过一个简单的例子带你一步一步认识它。
　　欢迎关注个人公众号【JAVA旭阳】数据线性分布
　　假如我们现在有一组服务器，我们想提出一个在这组服务器之间进行数据存储和查找的策略。让我们从一个最最简单的方案开始。假设我们一个接一个地填满服务器，即仅当当前服务器已满时，我们才开始将数据写入下一个服务器。
　　在下图中，我们有一个简单的服务器，一次只能存储4条记录。当服务器变满时，我们添加一个新服务器并向其添加新数据。
　　好吧，这种方法在任何服务器上写入数据时都非常有效。当您被要求读取特定数据时会发生什么？您需要识别存储给定数据的服务器，然后获取它。你如何识别服务器？您会遍历所有服务器并线性扫描每个服务器吗？这会影响读取性能。
　　例如：在上面的例子中，如果你被要求查找NewYork，因为键和服务器之间没有直接映射，你将不得不线性扫描所有服务器并搜索这个键。
　　这样的效率是不是很糟糕，那么有没有更好的解决方案呢。数据哈希分布
　　哈希算法想必大家都知道，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台，桶的计算逻辑将变为Hash4。
　　新旧密钥分配
　　在添加新服务器时，我们观察到三个键中的两个受到了影响。如果我们添加一个新服务器，键Madrid的桶将是0（S0）而不是1（S1）。我们必须将此密钥移动到服务器S1以确保我们的应用程序找到它。因此，我们必须重新散列所有现有密钥并将它们分配给不同的服务器。在最坏的情况下，这可能会影响系统中的所有密钥。
　　看来通过哈希算法将数据分发到不同服务器中还是不大行，那还有什么更好的办法呢？这边就要隆重介绍一致性哈希。什么是一致性哈希？
　　当我们想要动态添加或删除服务器时，一致性哈希解决了我们的问题。在简单散列的情况下，添加或删除服务器将影响存储在系统中的所有M密钥。然而，一致性哈希确保只有MN键受到影响，其中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。键NewYork被分配给服务器S1。删除S1后，我们从键NewYork中找到第一个服务器并找到服务器S2。因此，键NewYork被重新分配给服务器S2。
　　与普通散列不同，删除服务器不需要重新散列所有密钥。只需重新分配已移除服务器的密钥。虚拟节点
　　我们看到，当一个节点被移除时，分配给这个节点的所有键都会被移动到哈希环中的下一个节点。通常，在删除一个节点时，数据分布会变得不均匀，并且其中一个节点的负载会增加。
　　在上述情况下，如果我们从系统中删除S0，则键London将映射到服务器S2。最终，我们会发现S2处理三个密钥，而S1只管理一个密钥。因此，数据分布不均匀。
　　删除S0会给S2带来更多负载
　　在理想情况下，当有M个密钥和N个服务器时，每个服务器必须有接近MN个密钥。因此，添加或删除节点会影响系统中的最大MN键。为了确保接近理想的分布，我们在系统中引入了虚拟节点。每个物理节点在哈希环上都有多个虚拟节点。
　　我们使用多个哈希函数来查找虚拟节点在哈希环上的位置。每个服务器都用Sij表示，其中i表示实际服务器编号，j代表其虚拟副本。例如：对于第一台服务器，虚拟副本将是S00、S01、S02、S03等。我们使用不同的哈希函数来计算每个虚拟副本的哈希值。
　　在上面的示例中，我们得到以下虚拟服务器分配：
　　哈希环上的虚拟服务器
　　从上图可以看出，服务器S1的虚拟副本是S10、S12和S13。这同样适用于服务器S0。这导致节点之间的数据分布接近均匀。
　　对于给定的密钥，如果哈希环中的下一个服务器是S12，则它将分配给第一个物理服务器。一般而言，分配给虚拟服务器Sij的密钥将存储在物理服务器Si上。总结
　　本文带大家认识了一致性哈希算法，一致性哈希于1997年推出，它已经在许多分布式系统中的得到了应用。Amazon的DynamoDB中使用它作分区组件。此外，ApacheCassandra和Voldermort等开源应用程序使用它进行数据分区。
　　欢迎关注个人公众号【JAVA旭阳】