一致性哈希算法

## 1 传统哈希算法

### 1.1 含义

1. 简单地说，哈希就是一个**键值对存储**，在给定键的情况下，可以非常高效地找到所关联的值，假如我们要根据邮政编码查找城市中的街道名称，一种最简单的实现方式是将此信息以哈希字典的形式进行存储 `<ZipCode, StreetName>`。
2. 当**数据太大而无法存储在一个节点或机器上**时，系统就会**需要多个这样的节点或机器来存储**他，比如，使用多个 Web 缓存中间件的系统，对于如何确定哪个 `key` 存储在哪个节点上，最简单的解决方案是使用**哈希取模**来决定：
   1. 给定一个 `key`，先对 `key` 进行哈希运算，将其除以系统中的节点数，然后将 `key` 放入该节点。
   2. 在获取 `key` 时，先对 `key` 进行哈希运算，将其除以系统中的节点数，然后转到该节点并获取值。
   3. 上述过程对应的哈希算法定义如下：
      
      ```python
      # 下面的 N 为节点数
      node_number = hash(key) % N
      ```
   4. 下图描绘了多节点系统中的**传统的哈希取模算法**，基于该算法可以实现**简单的负载均衡**。
      
      ![traditional-hashing.png](/media/202107/2021-07-07_1421000.9469852762339032.png)

### 1.2 局限性

假设初始时有如下对应关系：

![ch-three-nodes-hash.jpg](/media/202107/2021-07-07_1423490.6348292290452177.png)

#### 1.2.1 节点减少的场景

1. 在分布式多节点系统中，出现故障很常见，任何节点都可能在没有任何事先通知的情况下挂掉，针对这种情况，我们希望系统只是出现性能降低，正常的功能不会受到影响。
2. 对于原始示例，假设其中 1 个节点出现了故障，这时节点数发生了变化，节点个数从 3 减少为 2，此时表格中的状态发生了变化：![ch-two-nodes-hash.jpg](/media/202107/2021-07-07_1428060.3557011869260098.png)
3. 很明显**节点的减少会导致键与节点的映射关系发生变化**，这个变化**对于新的键来说并不会产生任何影响**，但**对于已有的键来说**，将**会导致节点映射错误**，以 `semlinker` 为例，变化前系统有 3 个节点，该键对应的节点编号为 1，当出现故障时，节点数减少为 2 个，此时该键对应的节点编号为 0。

#### 1.2.2 节点增加的场景

1. 在分布式多节点系统中，对于某些场景比如节日大促，就需要对服务节点进行扩容，以应对突发的流量。
2. 对于原始示例，假设进行扩容临时增加了 1 个节点，这时节点数发生了变化，节点个数从 3 增加到 4 个，此时表格的状态发生了变化：![ch-four-nodes-hash.jpg](/media/202107/2021-07-07_1434360.9232043057651353.png)
3. 很明显**节点的增加也会导致键与节点的映射关系发生变化**，这个变化**对于新的键来说并不会产生任何影响**，但**对于已有的键来说**，将**导致节点映射错误**，同样以 `semlinker` 为例，变化前系统有 3 个节点，该键对应的节点编号为 1，当增加节点时，节点数增加为 4 个，此时该键对应的节点编号为 2。

### 1.3 影响

1. 当**集群中节点的数量发生变化**时，**之前的映射规则就可能发生变化**，如果集群中每个机器提供的服务没有差别，这不会有什么影响，但对于分布式缓存这种的系统而言，**映射规则失效就意味着之前缓存的失效**，若**同一时刻出现大量的缓存失效**，则**可能会出现缓存雪崩**，这将**会造成灾难性的后果**。
2. 要解决此问题，我们必须**在其余节点上重新分配现在所有键**，这可能**是非常昂贵的操作**，并且可能**对正在运行的系统产生不利的影响**。
3. 当然除了重新分配所有现有键的方案之外，还有另一种更好的方案，即**使用一致性哈希算法**。

## 2 一致性哈希算法

### 2.1 含义

1. 一致性哈希算法在 1997 年由麻省理工学院提出，是一种特殊的哈希算法，在**移除或者添加一个服务器**时，能够**尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系**。
2. 一致性哈希算法**解决了简单哈希算法在分布式哈希表**（Distributed Hash Table, DHT）**中存在的动态伸缩等问题**。

### 2.2 原理

1. 一致性哈希算法通过一个叫做**一致性哈希环**的数据结构实现，这个环的**起点是 0**，**终点是 $ 2^{32}-1 $**，并且**起点与终点连接**，故这个环的**整数分布范围是 $[0, 2^{32}-1]$**，如下图所示：
   
   ![hash-ring.jpg](/media/202107/2021-07-07_1527080.4916393664284763.png)
2. 假设我们有 `semlinker`、`kakuqo`、`lolo`、`fer` 四个对象，分别简写为 $o_1$、$o_2$、$o_3$、$o_4$，然后使用哈希函数计算这个对象的哈希值，值的范围是 $[0,2^{32}-1]$。
   
   ```python
   hash(o1) = k1; 
   hash(o2) = k2;
   hash(o3) = k3; 
   hash(o4) = k4;
   ```
   
   ![hash-ring-hash-objects.jpg](/media/202107/2021-07-07_1532050.7649515222872495.png)
3. 接着使用同样的哈希函数，我们将服务器也放置到哈希环上，可以选择服务器的 IP 或主机名作为键进行哈希，这样每台服务器就能确定其在哈希环上的位置，假设我们有 3 台缓存服务器，分别为 $cs_1$、$cs_2$、$cs_3$：
   
   ```python
   # Cache Server
   hash(cs1) = t1;
   hash(cs2) = t2;
   hash(cs3) = t3;
   ```
   
   ![hash-ring-hash-servers.jpg](/media/202107/2021-07-07_1535270.7351723268765217.png)
4. 将对象和服务器都放置到同一个哈希环后，在哈希环上**顺时针查找距离这个对象的哈希值最近的机器**，**即是这个对象所属的机器**，以 $o_2$ 为例，顺时针找到最近的机器是 $cs_2$，故服务器 $cs_2$ 会缓存 $o_2$ 对象，而服务器 $cs_1$ 会缓存 $o_1$、$o_3$ 对象，服务器 $cs_3$ 则缓存 $cs_4$ 对象。
   
   ![hash-ring-objects-servers.jpg](/media/202107/2021-07-07_1539240.8742732784924294.png)
5. 假设由于业务需要，我们需要增加一台服务器 $cs_4$，经过同样的哈希运算，该服务器最终落于 $t_1$ 和 $t_2$ 服务器之间，具体如下图所示：
   
   ![hash-ring-add-server.jpg](/media/202107/2021-07-07_1541410.32191095883185805.png)
6. 对于上述的情况，只有 $t_1$ 和 $t_2$ 服务器之间的对象需要重新分配，在以上示例中只有 $o_3$ 对象需要重新分配，即他被重新分配到 $cs_4$ 服务器，在前面我们分析过，如果使用简单的取模方法，当新添加服务器时可能会导致大部分缓存失效，而使用一致性哈希算法后，这种情况得到了较大的改善，因为只有少部分对象需要重新分配。
7. 假如 $cs_3$ 服务器出现故障导致服务下线，这时原本存储于 $cs_3$ 服务器的对象 $o_4$，需要重新分配至 $cs_2$ 服务器，其他对象仍存储在原有的机器上。
   
   ![hash-ring-remove-server.jpg](/media/202107/2021-07-07_1547020.9424212599929602.png)

### 2.3 优缺点

#### 2.3.1 优点

1. 一致性哈希算法是**对普通哈希算法的改进**，有效的**解决了稳定性的问题**。
2. 当**服务器节点加入或退出**时，**只影响该节点在哈希环上顺时针相邻的后继节点**：
   1. 当**加入一个服务器节点**时，**原来分配到后继节点的一部分请求**，**重新分配给新加入的服务器节点**。
   2. 当**退出一个服务器节点**时，**原来分配到该节点的请求**，**全部重新分配到后继节点**。

#### 2.3.2 缺点

1. 一致性哈希算法解决了稳定性问题，但是又**产生了负载不均衡问题**，或者**热点问题**，当**某个服务器节点或者几个服务器节点存在热点资源**，**这几个服务器节点就会处理大量的用户请求**，**其他服务器只处理很少的用户请求**，这就**产生了负载不均衡问题**。
2. 另外，当**某个服务器节点崩溃退出**，就会**使该节点的后继节点负载增大**，如果**后继节点承受不住崩溃**，就会**传递给后继节点的后继节点**，**产生雪崩效应**。

### 2.4 解决方案

针对已执行哈希算法存在的问题，有以下两种解决方案：

1. **带有限负载的一致性哈希**。
2. **带虚拟节点的一致性哈希**。

#### 2.4.1 带有限负载的一致性哈希

1. **根据当前负载情况对每个服务器节点设置一个最大请求负载值**，在一致性哈希环中进行查找时将**跳过达到最大负载限制的服务器节点**，以此类推，这样就**把过载的请求转移到其他服务器节点上来解决热点和不均衡问题**。
2. 如下图所示，服务器节点 `Server3` 正在处理两个用户请求，已经达到了最大负载限制数，所以第四个用户请求到来时，直接跳过 `Server3`，分配 `Server4` 来处理请求。![](/media/202107/2021-07-07_1621130.7413548858604911.png)

#### 2.4.2 带有虚拟节点的一致性哈希

1. **对每个物理服务器节点计算多个哈希值**，**每个计算结果位置都放置在对应节点上**，这些节点称为**虚拟节点**，然后再**将这些虚拟节点映射到哈希环上**，由于这些虚拟节点**分散到哈希环上**，因此很大程度上**解决了负载不均衡的问题**。![](/media/202107/2021-07-07_1630280.9856118343143467.png)
2. 在查找时，如果**要确定对象的服务器**，需要**先确定对象的虚拟服务器**，**再由虚拟服务器确定物理服务器**。![](/media/202107/2021-07-07_1632040.35710670981861736.png)

### 2.5 算法实现

```java
/**
 * @author peng.wei
 * @version 1.0
 * @date 2021/8/29 15:36
 * @Description 一致性哈希算法
 */
public class ConsistentHash {
    /**
     * 虚拟节点的数量
     */
    private static final Integer V_NODE_SIZE = 10;
    /**
     * 虚拟节点的前缀
     */
    private static final String V_NODE_SUFFIX = "V_NODE_SUFFIX";

/**
     * 构造哈希环
     *
     * @param servers 服务器映射信息
     * @return 哈希环
     */
    public TreeMap<Integer, Node> buildConsistentHashRing(Map<String, Node> servers) {
        TreeMap<Integer, Node> hashRing = new TreeMap<>();
        for (Node node : servers.values()) {
            hashRing.put(getHashCode(node.getNodeAddress()), node);
        }
        return hashRing;
    }

/**
     * 构造带虚拟节点的哈希环
     *
     * @param servers 服务器映射信息
     * @return 哈希环
     */
    public TreeMap<Integer, Node> buildConsistentHashRingWithVirtualNode(Map<String, Node> servers) {
        TreeMap<Integer, Node> hashRing = new TreeMap<>();
        for (Node node : servers.values()) {
            for (Integer i = 0; i < V_NODE_SIZE; i++) {
                hashRing.put(getHashCode(String.format("%s%s%s", node.getNodeAddress(), V_NODE_SUFFIX, i)), node);
            }
        }
        return hashRing;
    }

/**
     * 根据请求 key 的哈希值在哈希环上寻找节点
     * @param servers   服务器映射信息
     * @param keyHashCode   节点哈希值
     * @return  目标节点
     */
    public Node locate(Map<String, Node> servers, int keyHashCode) {
        TreeMap<Integer, Node> hashRing = buildConsistentHashRingWithVirtualNode(servers);
        //  向右找到第一个 key
        Map.Entry<Integer, Node> locateEntry = hashRing.ceilingEntry(keyHashCode);
        if (locateEntry == null) {
            locateEntry = hashRing.firstEntry();
        }
        return locateEntry.getValue();
    }

/**
     * 根据服务器节点地址获取哈希值
     * @param nodeAddress   服务器节点地址
     * @return  服务器节点地址对应的哈希值
     */
    public Integer getHashCode(String nodeAddress) {
        return System.identityHashCode(nodeAddress);
    }
}
```

## 参考文献

1. [图解一致性哈希算法](https://segmentfault.com/a/1190000021199728)。
2. [分布式高可用-负载均衡-3 一致性哈希(有限负载、虚拟节点)](https://www.codenong.com/cs107077214)。
3. [5 分钟理解一致性哈希算法](https://juejin.cn/post/6844903750860013576)。
4. [一致性哈希 （Consistent Hashing）的前世今生](https://candicexiao.com/consistenthashing)。