一致性哈希的原理和历史

• 1997年，STOC 上一篇文章 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web 发表，一致性哈希首次被提出。这篇文章先前还被一个计算机科学的会议拒绝呢，因为他们觉得没法实现。
• 1998年，基于一致性哈希算法原理 Akamai 成立。然后1999年3月31日，《星球大战：魅影危机》的预告片发布，包括苹果在内几乎所有网站都挂了，那时候只有 Akamai 的缓存服务器上可以看到这个预告片，Akamai 一战成名。第二天，乔布斯电话 Akamai 的老板 Sagan 问问情况，Sagan 以为是个愚人节玩笑，电话直接给挂了。两年后的911，Akamai 的联合创始人 Danny Lewin 乘着撞向世贸中心双塔大厦的第一驾飞机，不幸遇难。
• 2001年，Chord 这篇文章把一致性哈希用在 P2P 网络中，这篇文章里，一致性哈希被称为 DHT (Distributed Hash Table)。
• 2006年，Amazon 实现了 Dynamo 系统，使用一致性哈希算法记录文件存在哪个服务器上。然后一致性哈希就传开了。

假设你提供一个缓存服务，用来保存 key-value 数据，数据量和请求量很大以至于单一服务器不能满足存储要求。所以你设立了 \( n \) 个缓存服务器，用来保存这些 key-value 数据。那么，如何从一个 \( key \) ，快速找到这个 \( key \) 存在哪个服务器上面呢？

显然 \( n \) 个服务器挨个去问不是个好办法。最简单的方法是取 \( key \) 的哈希值:

\[ serverIndex = hash(key) \mod n \]

例如，假设 \( n=4 \)，哈希函数 \( hash(key) = atoi(key[3])+100 \) ，那么

key	hash(key)	hash(key) mod 4
key0	100	0
key1	101	1
key2	102	2
key3	103	3
key4	104	0
key5	105	1
key6	106	2
key7	107	3

因此，服务器和 \( key \) 的分配如下：

现在一个服务器 (serverIndex=1) 要关掉，\( n=3 \) 了，得重新给服务器编号，重新计算每个 \( key \) 在哪个服务器上，然后再把它迁移过去。

key	hash(key)	hash(key) mod 3
key0	100	0
key1	101	1
key2	102	2
key3	103	0
key4	104	1
key5	105	2
key6	106	0
key7	107	1

可以看到，总共8个 \( key \) 就需要迁移7个，大部分都要迁移，很麻烦。一致性哈希就是要解决这个问题。

我们用 s0 表示 serverIndex=0 的服务器，s1 表示 severIndex=1 的服务器，以此类推。指定一个哈希函数，比如 SHA-1，它的值域是 \( \left\{x\in N, 0 \leq x \leq 2^{160}-1\right\} \) 。把 s0-s3 哈希后放上数轴上，大致就长这样子：

用 k0 表示 Key0，k1 表示 key1，以此类推，k0-k7 画在数轴上，大概是这样：

一致性哈希的原理，就是把 key 存储在数轴上下一个服务器节点中。例如上图， k1、k7 就保存到 s3，k0、k6 保存到 s0，k3、k4 保存到 s1。可以看到 k3 后面没服务器了，就从0开始往后找到 s1。

大多文章都把这个数轴画成环，就像下面这样：

如果要添加一个服务器 s4，那么如下图，只需要迁移 k0 这1个key。

如果要把一个服务器 s0 删掉，如下图，只需要迁移 k6 这 1 个 key。

一致性哈希就是这样，把服务器哈希值放到数轴环上，再把 key 的哈希值放上去，顺时针遇到的第一个服务器就是这个 key 的存储位置。

基本的一致性哈希有两个问题：

1. 服务器的哈希值在环上可能不会均匀分布
2. key 的哈希值可能集中在某个服务器周围

如图：

虚拟节点可以解决这个问题。简单地说，就是给服务器起别名，别名的哈希值也放到数轴上，但是这些别名节点，都代表一个服务器。这样，节点数量多，就可以把节点大致均匀分布在数轴环上了。

大多数分布式存储系统都要一份数据保存在多个服务器上，例如要保存在3个服务器上，那么，key 存储的节点，就要在数轴上继续向前走，首先遇到的三个代表不同真实服务器的节点就是要存储的位置。

一致性哈希可以解决 Key 重新分布的问题，更容易横向扩展或缩减。用了以后还是有很多需要解决的问题。如一致性如何保证，如何检测系统中服务器故障，如何检测某个服务器数据出错，服务器之间如何通信。要使用它，涉及到的知识依然很多，单也不是不能解决。有现成的计数可以参考：Amazon Dynamo， Redis， Cassandra，BitTable，Markle Tree，SSTable，Bloom filter。具体实现时，相信上述提及的软件和技术都能帮到你。