认识达内从这里开始

我们在前几期的文章中给大家简单介绍了Java程序员需要掌握的一些编程算法等技术知识，而本文我们就再来学习一下，一致性哈希算法概念与应用分析。

当我们想要动态添加或删除服务器时，一致性哈希解决了我们的问题。在简单散列的情况下，添加或删除服务器将影响存储在系统中的所有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。键NewYork被分配给服务器S1。删除S1后，我们从键NewYork中找到一个服务器并找到服务器S2。因此，键NewYork被重新分配给服务器S2。

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

虚拟节点

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

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

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

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

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!请读者仅作参考。更多内容请加抖音达内三江区域学习了解。