一致性Hash(Consistent Hashing)原理剖析

前面一篇文章通过生活化的场景为例，来描述RPC中的一些核心且常用的技术，(RPC是什么?为什么要学习RPC?)在负载均衡的时候，我们提到一个「一致性Hash」, 这个在RPC之外的许多场景也会使用到。

引入

在业务开发中，我们常把数据持久化到数据库中。如果需要读取这些数据，除了直接从数据库中读取外，为了减轻数据库的访问压力以及提高访问速度，我们更多地引入缓存来对数据进行存取。读取数据的过程一般为：

图1：加入缓存的数据读取过程

对于分布式缓存，不同机器上存储不同对象的数据。为了实现这些缓存机器的负载均衡，可以使用式子1来定位对象缓存的存储机器：

m = hash(o) mod n ——式子1 

其中，o为对象的名称，n为机器的数量，m为机器的编号，hash为一hash函数。图2中的负载均衡器(load balancer)正是使用式子1来将客户端对不同对象的请求分派到不同的机器上执行，例如，对于对象o，经过式子1的计算，得到m的值为3，那么所有对对象o的读取和存储的请求都被发往机器3执行。

图2：如何利用Hash取模实现负载均衡

式子1在大部分时候都可以工作得很好，然而，当机器需要扩容或者机器出现宕机的情况下，事情就比较棘手了。

当机器扩容，需要增加一台缓存机器时，负载均衡器使用的式子变成：

m = hash(o) mod (n + 1) ——式子2 

当机器宕机，机器数量减少一台时，负载均衡器使用的式子变成：

m = hash(o) mod (n - 1) ——式子3 

我们以机器扩容的情况为例，说明简单的取模方法会导致什么问题。假设机器由3台变成4台，对象o1由式子1计算得到的m值为2，由式子2计算得到的m值却可能为0，1，2，3(一个 3t + 2的整数对4取模，其值可能为0，1，2，3，读者可以自行验证)，大约有75%(3/4)的可能性出现缓存访问不命中的现象。随着机器集群规模的扩大，这个比例线性上升。当99台机器再加入1台机器时，不命中的概率是99%(99/100)。这样的结果显然是不能接受的，因为这会导致数据库访问的压力陡增，严重情况，还可能导致数据库宕机。

一致性hash算法正是为了解决此类问题的方法，它可以保证当机器增加或者减少时，对缓存访问命中的概率影响减至很小。下面我们来详细说一下一致性hash算法的具体过程。

一致性Hash环

一致性hash算法通过一个叫作一致性hash环的数据结构实现。这个环的起点是0，终点是2^32 - 1，并且起点与终点连接，环的中间的整数按逆时针分布，故这个环的整数分布范围是[0, 2^32-1]，如下图3所示：

图3：一致性Hash环

将对象放置到Hash环

假设现在我们有4个对象，分别为o1，o2，o3，o4，使用hash函数计算这4个对象的hash值(范围为0 ~ 2^32-1):

hash(o1) = m1  

hash(o2) = m2  

hash(o3) = m3  

hash(o4) = m4 

把m1，m2，m3，m4这4个值放置到hash环上，得到如下图4：

图4：放置了对象的一致性Hash环

将机器放置到Hash环

使用同样的hash函数，我们将机器也放置到hash环上。假设我们有三台缓存机器，分别为 c1，c2，c3，使用hash函数计算这3台机器的hash值：

hash(c1) = t1  

hash(c2) = t2  

hash(c3) = t3 

把t1，t2，t3 这3个值放置到hash环上，得到如下图5：

图5：放置了机器的一致性Hash环

为对象选择机器

将对象和机器都放置到同一个hash环后，在hash环上顺时针查找距离这个对象的hash值最近的机器，即是这个对象所属的机器。

例如，对于对象o2，顺序针找到最近的机器是c1，故机器c1会缓存对象o2。而机器c2则缓存o3，o4，机器c3则缓存对象o1。