一致性哈希 Consistent Hash

概述

一致性哈希是由传统的哈希算法改进而来的一种算法. 为了解决传统哈希算法对于哈希表长度发生变化导致大量数据对象需要重哈希的问题.

前言

当我们去车站买票的时候, 经常看到这样一个现象. 车站只开了一个窗口, 窗口前排着长长的队伍.突然, 旁边的售票窗口打开了, 然后后面排队的人们轰的一下就会跑到另外一个窗口去. 或者是有某个窗口突然被关闭, 人们就得排到还打开的窗口去.

然后再来回顾一下传统的哈希表, 计算方法我们就采用简单又常见的取余法

我们将 {3, 4, 7, 8, 12} 五个数字对这个哈希表长n = 8取余, 能得到上面图片中的哈希表.

我们将哈希表长减到n = 5, 依旧是存储上面的5个数字, 此时哈希表就变成了下面这样

基本上所有的元素都改变了在表中的位置, 也就是说如果哈希表的长度发生改变, 大部分元素都要重哈希来定位自己在新表中的位置.

做个变化的比较

if __name__ == '__main__':
    Node = {"0": [], "1": [], "2": [], "3": [], "4": [], "5": [], "6": [], "7": []}
    new_Node = {"0": [], "1": [], "2": [], "3": [], "4": []}
    for i in range(10000):
        hash_number = 8
        tmp = i % hash_number
        Node[str(tmp)].append(i)
        hash_number = 5
        tmp = i % hash_number
        new_Node[str(tmp)].append(i)
    sum = 0
    for x in Node['0']:
        for k in new_Node['0']:
            if x == k:
                sum += 1
    print((len(new_Node['0'])-sum)/len(new_Node['0']))

# 最后得出的结果是 0.875

也就是说, 对于表中的一个节点会有大量的数据会被重新哈希定位新的位置

在大部分程序语言中, 哈希表会指定一个默认长度 (Python的dict默认长度为8), 但并不推荐使用使用这个默认值, 因为这个值并不能满足大部分的使用需求, 如果使用了这个默认值通常需要进行调整长度.

如果哈希表长度经常发生变化的话, 数据要经常重新定位. 这工作量十分巨大.

为什么动一个节点就要殃及池鱼呢? 有没有什么很好的办法能够使得每次的调整造成的影响减小或者说只影响于调整的位置?

申请长度足够的哈希表, 这样少量的增减不会对整体的数据产生影响
- 就像我们在车站开放100万个窗口, 增减几个窗口对大部分用户不会有什么影响, 毕竟哪个车站会有这么多人呢
如果只是短时调整, 可以让数据在原地等待节点恢复原状
- 车站的售票员临时去上了个厕所, 就让用户在原地等待一会

第一个方案似乎会更好一些, 可是申请大量的空间不使用也是很浪费的, 所以在此基础上再次进行优化, 于是就有了一致性哈希算法.

性质

平衡性(Balance)
单调性(Monotonicity)
分散性(Spread)
负载(Load)
平滑性(Smoothness)

算法原理

这里应用简单的哈希计算方法 (取余法)

我们还是要去买票

这次车站想了一个新的办法来管理车站的售票窗口, 去买票的人需要先去取个号码.

车站打开了A, B, C 三个售票窗口, 并且规定领到号码的人要按照号码顺序在圆形大厅中顺时针去排队买票

此时车站来了一万个人, 并且领取了号码准备买票

根据车站的管理规则, 他们应该去到对应的窗口买票, 500号选手顺序应当到A售票窗口买票

扩展和移除

新增

不少的人觉得, 排队买票的时间太久了, 强烈要求车站增开售票窗口.

如下图, 要在B窗口和C窗口之间新增一个X窗口, 此时5500的用户就不需要去到C窗口买票了, 直接去到X窗口买票

此时受到影响的也只是B窗口和X窗口之间的用户, 位于X窗口和B窗口之间的请求会从C窗口上转移至X窗口上.

其他用户还是去对应的窗口买票, 这样对整体的影响将大大减小.

移除

当移除掉一个售票窗口, 受到影响的用户又有多少呢?

同理可得. 如下图, 我们想要移除B窗口的话, 此时A窗口和B窗口之间的请求将顺着哈希环全部转移至C窗口, 其他位置的用户并不会收到影响.

由上可见, 如果有N个售票窗口, 并且这N个窗口均匀分布, 那么新增或移除K个窗口只会对 $\frac KN$ 的用户造成影响. 这远远小于传统哈希算法改变表长带来的影响

分配倾斜

城市下个星期要开展一个盛大的活动, 来往的人也变得多了起来, 人们照常去售票大厅购票, 于是排队的场面就变成了这样

A窗口的售票员操劳过度, 大量的人排在了A窗口前.

这是由于窗口的数量对于日常的人流分配是均匀的, 但是人数突然激增或者减少, 这个平衡就会被打破.

对于这个情况, 在不改变窗口数量的情况下, 有没有办法让人数在分配时更加的均匀呢?

我们需要把同一个时段的人能够更均匀的分配到每一个窗口, 就需要再将窗口分配得更密集一点, 可是窗口只有那么多个怎么办呢?

我们可以建造一些购票机器使人流更分散均匀.

我们使用虚拟节点 (购票机器) 来完成这个优化, 将真实的售票窗口虚拟出很多的窗口并更均匀的分配到大厅中, 实际上在虚拟节点购票的用户实际上是在真实的窗口出票的.

实践

微软提交社区的一致性哈希算法, 具体数据结构使用了排序的Map, 查找效率较无序Map大大提升.

忽略锁的部分

/**
 * Consistent hash ring to distribute items across nodes (locations). If we add
 * or remove nodes, it minimizes the item migration.
 * 一致性哈希环，分散化实体项的节点位置选择，减少因为节点的变更导致的其上所属实体项的迁移。
 */
public class ConsistentHashRing {
  private static final String SEPERATOR = "/";
  private static final String VIRTUAL_NODE_FORMAT = "%s" + SEPERATOR + "%d";

  /** Hash ring 哈希环. */
  private SortedMap<String, String> ring = new TreeMap<String, String>();
  /** 虚拟节点信息 -> 节点数 映射信息 */
  /** Entry -> num virtual nodes on ring. */
  private Map<String, Integer> entryToVirtualNodes =
      new HashMap<String, Integer>();

  /** Synchronization 锁同步. */
  private final ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
  private final Lock readLock = readWriteLock.readLock();
  private final Lock writeLock = readWriteLock.writeLock();

  public ConsistentHashRing(Set<String> locations) {
    for (String location : locations) {
      // 在环内添加位置信息
      addLocation(location);
    }
  }

  /**
   * Add entry to consistent hash ring.
   * 添加实体项到哈希环内
   * @param location Node to add to the ring.
   */
  public void addLocation(String location) {
    // 虚拟出100个节点插入
    addLocation(location, 100);
  }

  /**
   * Add entry to consistent hash ring.
   * 添加具体项到哈希环内
   * @param location 需要添加的节点.
   * @param numVirtualNodes 需要添加的虚拟节点数。
   */
  public void addLocation(String location, int numVirtualNodes) {
    writeLock.lock();
    try {
      // 更新虚拟节点列表信息
      entryToVirtualNodes.put(location, numVirtualNodes);
      for (int i = 0; i < numVirtualNodes; i++) {
        // 得到虚拟节点名
        String key = String.format(VIRTUAL_NODE_FORMAT, location, i);
        // 取其哈希值
        String hash = getHash(key);
        // 加入到哈希环内
        ring.put(hash, key);
      }
    } finally {
      writeLock.unlock();
    }
  }

  /**
   * Remove specified entry from hash ring.
   * 从哈希环内移除实体项
   * @param location Node to remove from the ring.
   */
  public void removeLocation(String location) {
    writeLock.lock();
    try {
      // 移除给定节点位置，并获取其对应的虚拟节点数
      Integer numVirtualNodes = entryToVirtualNodes.remove(location);
      for (int i = 0; i < numVirtualNodes; i++) {
        // 得到虚拟节点key，并从哈希环内移除
        String key = String.format(VIRTUAL_NODE_FORMAT, location, i);
        String hash = getHash(key);
        ring.remove(hash);
      }
    } finally {
      writeLock.unlock();
    }
  }

  /**
   * Return location (owner) of specified item. Owner is the next
   * entry on the hash ring (with a hash value > hash value of item).
   * 从哈希环内去得其最近的节点位置
   * @param item Item to look for.
   * @return The location of the item.
   */
  public String getLocation(String item) {
    readLock.lock();
    try {
      if (ring.isEmpty()) {
        return null;
      }
      // 计算输入路径的哈希值
      String hash = getHash(item);
      // 如果哈希环内不恰好包含此节点
      if (!ring.containsKey(hash)) {
        // 将哈希环定位到大于此key的首个位置
        SortedMap<String, String> tailMap = ring.tailMap(hash);
        // 并得到第一个大于此key的项目的key,也就是距离最近的key
        hash = tailMap.isEmpty() ? ring.firstKey() : tailMap.firstKey();
      }
      // 根据此key得到对应的虚拟节点信息
      String virtualNode = ring.get(hash);
      // 然后从虚拟节点信息中得到实际位置信息
      int index = virtualNode.lastIndexOf(SEPERATOR);
      if (index >= 0) {
        return virtualNode.substring(0, index);
      } else {
        return virtualNode;
      }
    } finally {
      readLock.unlock();
    }
  }

  public String getHash(String key) {
    return MD5Hash.digest(key).toString();
  }

  /**
   * Get the locations in the ring.
   * @return Set of locations in the ring.
   */
  public Set<String> getLocations() {
    return entryToVirtualNodes.keySet();
  }
}

应用

一致性哈希被应用于分布式系统中, 在分布式数据库和分布式缓存中被广泛使用.

Data partitioning in Azure Cosmos DB
服务器负载均衡
MemCache分布式内存对象缓存系统

比较

传统哈希表因为表长改变需要对极大部分数据进行重哈希, 产生大量的工作量.

而一致性哈希使数据几乎不会产生冲突的分布在整数环上, 然后再对整数环切分处理, 在可用节点发生改变的时候, 只会对改变节点至上一个节点中的对象造成影响

对于N个节点 (或槽), K个关键字的渐近时间复杂度

	传统哈希表	一致性哈希
增加一个节点	$O(K)$	$O(\frac KN + \log N)$
移除一个节点	$O(K)$	$O(\frac KN + \log N)$
增加一个关键字	$O(1)$	$O(\log N)$
移除一个关键字	$O(1)$	$O(\log N)$