简介

为了办理漫衍式 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 重定位的问题。

道理与增删节点

一致性哈希的道理如下：

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

与此雷同，当新增一个节点时，仅有一个节点的部门 object 需要重哈希。

虚节点与均衡性

节点的位置是由自身哈希值抉择的，它们的漫衍并非匀称，出格当节点数目很少时，容易造成 object 的漫衍不匀称，即均衡性低，譬喻：