#

普通哈希算法

要了解一致性哈希，首先我们必须了解传统的哈希及其在大规模分布式系统中的局限性。简单地说，哈希就是一个键值对存储，在给定键的情况下，可以非常高效地找到所关联的值。假设我们要根据其邮政编码查找城市中的街道名称。一种最简单的实现方式是将此信息以哈希字典的形式进行存储 <Zip Code，Street Name>。

当数据太大而无法存储在一个节点或机器上时，问题变得更加有趣，系统中需要多个这样的节点或机器来存储它。比如，使用多个 Web 缓存中间件的系统。那如何确定哪个 key 存储在哪个节点上？针对该问题，最简单的解决方案是使用哈希取模来确定。 给定一个 key，先对 key 进行哈希运算，将其除以系统中的节点数，然后将该 key 放入该节点。同样，在获取 key 时，对 key 进行哈希运算，再除以节点数，然后转到该节点并获取值。上述过程对应的哈希算法定义如下：

node_number = hash(key) % N # 其中 N 为节点数。

下图描绘了多节点系统中的传统的哈希取模算法，基于该算法可以实现简单的负载均衡。

缺点很明显，如果某一台master发生了宕机，那么此时会导致Redis中所有的缓存失效。为什么是所有的？假设之前有3个master，那么之前的算法应该是 hash % 3，但是如果其中一台master宕机了，则算法就会变成 hash % 2，会影响到之前存储的所有的key。而这对缓存后面保护的DB来说，是致命的打击。

一致性哈希

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

哈希算法特性

一致性哈希算法是在哈希算法基础上提出的，在动态变化的分布式环境中，哈希算法应该满足的几个条件：平衡性、单调性和分散性。

• 平衡性(Balance)：是指 hash 的结果应该平均分配到各个节点，这样从算法上解决了负载均衡问题。
• 单调性(Monotonicity)：是指在新增或者删减节点时，不影响系统正常运行。
• 分散性(Spread)：是指数据应该分散地存放在分布式集群中的各个节点（节点自己可以有备份），不必每个节点都存储所有的数据。
• 负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

理解一致性哈希

一致性哈希算法的基本实现原理是将机器节点和 key 值都按照一样的 hash 算法映射到一个 $2^{32}-1$ 的圆环上。当有一个写入缓存的请求到来时，计算 Key 值 k 对应的哈希值 Hash(k)，如果该值正好对应之前某个机器节点的Hash值，则直接写入该机器节点，如果没有对应的机器节点，则顺时针查找下一个节点，进行写入，如果超过$2^{32}$还没找到对应节点，则从0开始查找(因为是环状结构)。如图所示

图中Key K的哈希值在A与B之间，于是K就由节点B来处理。

经过一致性哈希算法散列之后，当有新的机器加入时，将只影响一台机器的存储情况，例如新加入的节点H的散列在B与C之间，则原先由C处理的一些数据可能将移至H处理，而其他所有节点的处理情况都将保持不变，因此表现出很好的单调性。而如果删除一台机器，例如删除C节点，此时原来由C处理的数据将移至D节点，而其它节点的处理情况仍然不变。而由于在机器节点散列和缓冲内容散列时都采用了同一种散列算法，因此也很好得降低了分散性和负载。

虚拟节点

我们的 key 有可能计算出的哈希值都在一定范围，而这个范围都是一个节点存储，导致 key 分布不均匀。所以引入了虚拟节点的概念，我们在这个范围平均分配节点的虚拟节点，最终由虚拟节点再去映射真正的机器，这样就可以保证 hash 出的 key 与范围无关，均衡分布了，满足了哈希算法的平衡性。

如下图，A1 A2 C1 C2 四个虚拟节点，平分了哈希范围，让哈希出的 key 到每个节点的概率一样。

与普通哈希区别

因为普通哈希需要对机器数取模，在机器和减机器后 mod 值变了，导致 key 分布全乱了，导致多个机器上的 key 失效，这样是不便于迁移的。

一致性哈希不需要取模，所以机器变化后，计算出的 hash 值不会变, 如果节点下线就找下一个，所以只是单机 key 失效，也便于迁移。

Java 实现

仿照了 Jedis 的 一致性哈希的实现。

package com.unclezs.redis.algorithm;

import lombok.AllArgsConstructor;
import lombok.Data;

import java.util.*;

/**
 * 一致性哈希算法实现
 *
 * @author blog.unclezs.com
 * @since 2022/7/28 3:17 PM
 */
public class ConsistentHashing {
  private final TreeMap<Integer, ServerInfo> nodes = new TreeMap<>();
  private final Map<String, ServerInfo> resources = new HashMap<>();

  /**
   * 每个节点的虚拟节点数量
   */
  private static final int NODE_VIRTUAL_NODES_NUM = 160;

  public ConsistentHashing(List<ServerInfo> serverInfos) {
    initialize(serverInfos);
  }

  /**
   * 初始化
   *
   * @param shards 分片
   */
  private void initialize(List<ServerInfo> shards) {
    for (int i = 0; i < shards.size(); i++) {
      ServerInfo shard = shards.get(i);
      for (int n = 0; n < NODE_VIRTUAL_NODES_NUM; n++) {
        int hash = hash("SHARD-" + i + "-NODE-" + n);
        nodes.put(hash, shard);
        addNodeIfNotExist(shard);
      }
    }
  }

  /**
   * 如果不存在添加节点
   *
   * @param node 节点
   */
  private void addNodeIfNotExist(ServerInfo node) {
    String key = node.toString();
    ServerInfo serverInfo = resources.get(key);
    if (serverInfo != null) {
      return;
    }
    resources.put(key, node);
  }

  /**
   * 使用 FNV1_32_HASH 算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
   *
   * @param str str
   * @return int
   */
  private int hash(String str) {
    final int p = 16777619;
    int hash = (int) 2166136261L;
    for (int i = 0; i < str.length(); i++) {
      hash = (hash ^ str.charAt(i)) * p;
    }
    hash += hash << 13;
    hash ^= hash >> 7;
    hash += hash << 3;
    hash ^= hash >> 17;
    hash += hash << 5;

    // 如果算出来的值为负数则取其绝对值
    if (hash < 0) {
      hash = Math.abs(hash);
    }
    return hash;
  }

  /**
   * 得到应当路由到的结点
   *
   * @param key 键
   * @return {@link String}
   */
  private ServerInfo getServer(String key) {
    int hash = hash(key);
    SortedMap<Integer, ServerInfo> tail = nodes.tailMap(hash);
    if (tail.isEmpty()) {
      return nodes.get(nodes.firstKey());
    }
    return tail.get(tail.firstKey());
  }

  public static void main(String[] args) {
    List<ServerInfo> shards = new ArrayList<>();
    shards.add(new ServerInfo("127.0.0.1", 7001));
    shards.add(new ServerInfo("127.0.0.1", 7002));
    shards.add(new ServerInfo("127.0.0.1", 7003));
    shards.add(new ServerInfo("127.0.0.1", 7004));
    shards.add(new ServerInfo("127.0.0.1", 7005));
    shards.add(new ServerInfo("127.0.0.1", 7006));

    ConsistentHashing hashing = new ConsistentHashing(shards);

    String[] keys = {"太阳", "月亮", "星星"};
    for (String key : keys) {
      System.out.println("[" + key + "]的 hash 值为" + hashing.hash(key) + ", 被路由到结点[" + hashing.getServer(key) + "]");
    }
  }

  @Data
  @AllArgsConstructor
  static class ServerInfo {
    private String host;
    private int port;

    @Override
    public String toString() {
      return host + ":" + port;
    }
  }
}

---------------------------------
[太阳]的 hash 值为1977106057, 被路由到结点[127.0.0.1:7004]
[月亮]的 hash 值为1132637661, 被路由到结点[127.0.0.1:7003]
[星星]的 hash 值为880019273, 被路由到结点[127.0.0.1:7005]