简介

为了解决分布式 web 中的热点问题，David Karger 于 1997 年提出 一致性哈希(Consistent Hashing)，论文请见 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web(较难理解)。一致性哈希广泛的运用于多种分布式系统中，如 memcache/redis，gluster file system, zookooper 等。

本文主要介绍一致性哈希的原理。

原理

去中心与水平扩展

以 web 为例，cache 节点(如 Redis, Memcache)广泛用于 web 中，以提升性能。随着 web 规模扩大，单个节点无论是从性能上还是容量上都无法支撑大规模的业务，所以需要用多个节点以提升性能和容量。

在多个节点下，给定某个 object，客户端如何知道它存储在哪个节点呢？最简单的做法是选取某个节点做为元数据服务器，记录每个 object 存放的节点，每次访问该 object 时，客户端首先访问元数据服务器，获取其所存放的节点，最后从该节点获取 object。元数据服务器需要维护所有 object 的位置信息，并且每次访问 object 都需要先访问元数据服务器，如此，元数据服务器容易成为性能和容量的瓶颈，不利于大规模扩展。

          1. Fetch       +-----------------+
client  ------------->   | Metadata Server |   bottleneck
           Location      +-----------------+
       
          2. Access      +-----------------+
        ------------->   | Cache Server X  |
         Cache Server    +-----------------+

去中心化的系统最大优点之一就是易水平扩展，那是否有办法可以去除上述元数据服务器呢。答案是肯定的，比如计算 object 的 hash 值，然后均匀的分布到各个节点上。

hash(object) mod N        其中 N 为节点数目

但是如果某个节点宕机，剔除宕机节点后数目为 N - 1，此时映射关系变为：

hash(object) mod (N - 1)

另外，可能由于负载过高，需要新增一个节点，此时映射关系为：

hash(object) mod (N + 1)

无论是增加还是减少节点，都有可能会改变映射关系，造成大量请求的 miss。那是否能避免大量的 miss 呢？答案也是肯定的，一致性哈希解决了节点增减造成大量 hash 重定位的问题。

原理与增删节点

一致性哈希的原理如下：

  • 将每个节点(node)映射到数值空间 [0, 2^32 - 1]，映射的规则可为 IP、hostname 等。
  • 将每个 object 映射到数值空间 [0, 2^32 - 1]。
  • 对于某个 object，对于所有满足 hash(node) <= hash(object) 的节点，选择 hash(node) 最大的节点存放 object。如果没有满足上述条件的节点，选择 hash(node) 最小的节点存放该 object，如下图。

hash ring

当某个节点宕机时，仅有该节点的对象被重哈希到相邻节点上。

hash ring delete

与此类似，当新增一个节点时，仅有一个节点的部分 object 需要重哈希。

hash ring add

虚节点与平衡性

节点的位置是由自身哈希值决定的，它们的分布并非均匀，特别当节点数目很少时，容易造成 object 的分布不均匀，即平衡性低，例如：

unbalance

为了解决这个问题，我们引入虚拟节点，虚拟节点实际上是物理节点的复制品，一个物理节点包含多个虚拟节点，我们将这些虚拟节点映射到数值空间 [0, 2^32 - 1]，对于某个 object，我们根据上节步骤计算该 object 存放的虚拟节点，进而得出物理节点。如下图共有 2 个物理节点，每个物理节点有三个虚拟机节点。当虚拟节点越多，虚拟节点的位置分布越均匀，相应的，映射到物理节点的 object 数目也越均匀，提高了平衡性。

virtual node

总结

通过一致性哈希，客户端可以在本地计算 object 的存放位置，去除了中心节点，使得系统容易水平扩展，便于按需提升/降低整体的容量和性能，同时避免了每次增删节点造成大量哈希重定位的问题，最大化的减少了数据迁移。为使 object 能够尽可能均衡的分散在各个节点上，一致性哈希引入了虚节点，以提高平衡性。