一致性 hash 环

概述

一致性hash算法由于均衡性、持久性的映射特点，被广泛应用于负载均衡领域，比如 nginx 、dubbo 、等等，内部都有一致性hash的实现 ，在分布式场景中，如果有多个实例，那么你可以通过一致性hash进行计算，然后分发到具体的某个实例上。

1.hash算法 在负载均衡中的问题

先来看看普通的hash算法的特点，普通的hash算法就是把一系列输入打散成随机的数据，负载均衡就是利用这一点特性，对于大量请求调用，通过一定的hash将它们均匀的散列，从而实现压力平均化。

问题：可以看出 当 N 节点数发生变化的时候，之前所有的 hash映射几乎全部失效，如果集群是无状态的服务倒是没什么事情，但是如果是分布式缓存这种，比如映射的key1原本是去node1上查询缓存的value1，但是当N节点变化后hash后的key1可能去了node2，这样就产生了致命问题。

2.一致性 hash 算法

一致性hash算法就是来解决上面的问题。

2.1 特点

下面说明 一致性hash算法的 2个 重要的特点

• 平衡性
  平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

• 单调性
  单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求

2.2 原理

一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形），就是所有的输入值都被映射到 0-2^32-1 之间，组成一个圆环，下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的ip或主机名或者其他唯一属性作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中四台服务器使用ip地址哈希后在环空间的位置如下：

定位数据存储的方法：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。可以为这些服务器维护一条二分查找树，定位服务器的过程就是在二分查找树中找刚好比其大的节点。

2.3 新增和删除节点

我们接下来讨论下， 当新增和删除槽位时， 哈希环的表现如何。

• 新增节点
  当往一个哈希环中新增一个槽位时，红色的 N4 是新增的槽位。 可以看到 k 从 N1 重新映射到了 N4 , 而 k1 的映射结果不变。 稍加分析可以知道， 只有被新增槽位拦下来的 k 的映射结果是变化了的。 新增槽位拦截了原本到下一节点的部分映射，其他槽位不受影响。 对于kv服务来说， 顺时针方向的下一个节点 N1 需要迁移部分数据到新节点 N4 上才可以正常服务， 其他节点不受影响。

• 删除节点
  当从一个哈希环中移除一个槽位时， 红色的 N1 是被删除的槽位。 可以看到 k 从 N1 重新映射到了 N3， 而 k1 的映射结果不变。 被删除槽位的映射会转交给下一槽位，其他槽位不受影响。 kv服务来说， 顺时针方向的原本映射到 N1 的请求会被 转交到顺时针方向的下一个节点 N3 处理， 所以需要迁移 N1 的数据到 N3 才可以正常服务。

2.4 一致性hash存在的问题

• 数据分布不均匀
  当节点Node很少的时候 比如2台机器，那么 必然造成大量数据集中在NodeA，少量在NodeB。

• 雪崩
  当某个节点宕机后，原本属于它的请求 都会被重新hash 映射到 下游节点，会突然造成下游节点压力过大 有可能也会造成 下游节点宕机，从而形成雪崩 这是致命的。

  为此，引入了虚拟节点来解决上面两个问题

3.带虚拟节点的一致性hash环

在哈希环上根据Node节点，生成很多的虚拟节点分布在圆环上，这样当某个节点挂了后，原本属于它的请求，会被均衡的分布到其他节点上，从而降低了产生雪崩的情况，也解决了节点数少导致请求分布不均的请求。
即对每一个服务节点计算多个哈希（可以用原节点key+”#xxx”作为每个虚拟节点的key，然后求hashcode），每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。

虚拟节点还解决了权重的问题，对于配置有高有低的服务器，可以根据权重给配置高的机器生成更多的虚拟节点来增加被选中的概率。

4.代码实现

以上就是一致性哈希环的讲解，接下来是它的代码实现：
github源码
代码用了golang的泛型，实现开箱即用，可设置虚拟节点数和权重，实现快速删除和添加节点，性能方面简单测的还算可以，欢迎提交更多的性能测试用例。

本作品采用《CC 协议》，转载必须注明作者和本文链接