一致性哈希的设计理念

首先看一个最简单的hash函数

#define HASH_RANGE  5
int simple_hash(int key)
{
     return key%HASH_RANGE
}

通过调用simple_hash对5、8、9三个值进行哈希，结果如下：

simple_hash(5) = 0
simple_hash(8) = 3
simple_hash(9) = 4

在实际应用中，HASH_RANGE是代表着一定的实际意义的，比如机器的台数，本文就以机器台数为例。当HASH_RANGE=5的时候，机器节点编号为0 ~ 4，simple_hash(5) = 0 表示key为5的数据将被放置到0号机器节点中。查询的时候，只需要将key 5进行hash得到节点号0，则可以找到节点，从而读出数据。

就这样，系统运行了一段时间，数据来来去去，天下太平。

有一天，系统中增加了一台新机器，这个时候HASH_RANGE = 6，我们会发现，5、8、9三个值的哈希值已经改变了！这意味着什么呢？在新的函数看来，原来5、8、9三个值被分配到了错误的机器上。如果有人用key=5来查询，则返回的节点此时变成了5，而不是0，显然，这次查询会失败。因为数据还在0号节点上呢！

// HASH_FACTOR = 6
simple_hash(5) = 5 
simple_hash(8) = 2 
simple_hash(9) = 3

在教科书上，HASH_RANGE被称作哈希因子。

如何才能保证机器台数的增加的情况下还等读到正确的数据呢？最简单的方法是不用机器台数作为哈希因子 ，而是选取一些不变量为哈希因子。Consistency Hash就是在这种指导思想下产生的。

先通过下图看看一致性哈希的基本思想：

机器数（node）不再作为哈希因子，而是通过一个通用的hash函数哈希到[0, 2^32)的范围上，所有的key也被哈希到这个范围上，然后顺着数轴环“往前”找node，首先找到的那个就是key要存放到的机器。

Consistency Hash并不完美。当系统中有新机器加入的时候，部分key还是需要重新分布，如下图。但是，通用的hash函数还是用原来那个。从效果上看，Consistency Hash比普通hash的影响要小得多。

更多一致性哈希的内容，感兴趣的朋友可以到维基百科上阅读 。

在普通hash函数中，哈希和存储是紧耦合的，而在Consistency Hash中，哈希和存储被分离，首先通过hash来确定大致范围，再通过向前寻址的方式找到最近的节点以存储。

Hash函数存在的本质问题并没有解决，Consistency Hash只是弱化了Hash函数在算法中的地位，引入一些新思路来解决问题而已。

Remarks：

1. 文中图片截自：Memcached全面剖析 p28

2. 为了避免数据都hash到很近的地方，Consistency Hash还使用了虚拟节点的概念。即一个物理节点可能被虚拟成200个虚拟节点，并且均匀分布在环上。这种思路也很巧妙，值得学习。