一致性 hashing

随着云计算，大数据的发展，分布式系统获得了越来越多的关注。其中一种叫分布式缓存的系统为高并发的Web应用提供了性能上的支撑，它就是采用了一种叫做一致性哈希 (consistent hashing) 的算法。

那什么是一致性哈希呢？他产生的背后有什么原因呢？为什么我们需要了解它呢？

在这篇文章里面，我会首先简单讲一下哈希的概念和作用。然后延伸到分布式哈希和它所面临的问题，最后在回到我们的主题，一致性 hashing。

What is Hashing?

哈希是将一个对象到一个整数的映射，这个整数我们通常称之为哈希码 (hash code)

比如一些哈希函数将任意字符串映射到某一个范围内的整数 1-100，"hello" 映射成 38， "hello world" 映射成 10，因为输入的字符串可以有任意多个，而数1-100却只有100个，是有限的，那么就会出现不同的字符串hash code相同的情况，这种情况我们称为 "collision"。一个好的hash函数应该是能够将输入均匀的分配到所有的hash值里面去。

哈希一个比较常见的地方就是hash table,下面就简单介绍一下hash table。

Hash Table 简介

加入我们有这样的一个需求，我们要保存一个俱乐部里面所有的成员，然后能通过名字找到这些成员，一种方法就是我们把这些成员对象放到一个list里面，然后通过遍历整个list,找到对应的成员，显然，这种算法的复杂度是 O(n). 数据量小的时候没有问题，但是一旦数据量大了以后，效率会非常差。

假设成员的ID是一个整数，那我们维护一个大的数组，那我们可以将ID作为数组的index 来存放数据。此时算法的复杂度就变成了 O(1). 

但是，如果ID是一个非连续的数呢，是随机数了，是一个非常大的数呢？甚至不是一个数呢？我们该怎么办？不用担心，Hash 来拯救我们来了！一个合适的hash函数可以将任意对象转换成一个范围内的整数，就想我们将ID映射到数组的index一样，只是有一点点不同而已。

首先，一个好的hash函数会有一个比较大的整数范围，通常是32或者 64bit的整数，想要创建一个这么大的数组几乎是不可能或者不必要的，因为浪费内存呀。那么怎么办呢？讲hash值模上一个整数N就好了，这个整数N就是我们数组的大小。

第二，因为对象的hash值会重复，这个时候就会产生collision, 产生hash冲突有很多种解决办法，最常见的做法就是在数组里面维护一个链表，通常叫做桶 （buket）。想要找到相应的对象就先算hash定位到链表，然后再在链表里面找。

分布式Hash

前面我们讲到了Hash,下面谈谈分布式哈希(distributed hash)

在数据非常大的情况下，单机内存不够，我们怎么办呢，那此时我们需要将一个hash table分成多个部分，让数据分散在多个server上。一个典型的应用就是分布式缓存系统 memcache.

那我们如何决定哪些server 存储哪些key呢？

最简单的做法就是将hash值与server的数量取模，server = hash(key) mod N。

举个栗子

假如我们有三台服务器 A, B, C,以及一些以字符串作为key的数据:

假如要获得“john”为key的数据，那我们先算hash,然后mod 3,得到值为2，对应的是server C.那我们就可以去server C 上面找我们的数据，如果server C上面没有的话，就去原始数据库找到相应的数据，在存放到 server C 上面。

Rehashing的问题

前面的分布式策略简单，又符合直觉，也能满足我们的需求，然而，一段我们的server的数量发生变化，或者某些server出现故障，之前定位到出现故障的server的key就需要被重新hash到别的能工作的server上，当我们新增server的时候，也需要进行重新hash.

前面的例子中，如果我们去掉 server C, 那么我们需要重新计算 hash mode 2, key映射到不同的server上。

注意，这个时候所有的key对应的server都发生了改变。

这个改变意味着什么呢？一断我们系统里面的某个server发生故障，之前的缓存都变得无效。系统需要重新从数据库里面load所有的数据。数据库的压力陡然上升，甚至会使得整个系统瘫痪。

解决办法 一致性Hash

我们怎么办呢？我们需要一个分布算法，不依赖于服务器的数量，当我们增加或者减少服务器时，需要被重新reload的key的数量就会变小. MIT 的一个人在1997年提出了一个叫做一致性Hash的算法。

Consistent Hashing is a distributed hashing scheme that operates independently of the number of servers or objects in a distributed hash table by assigning them a position on an abstract circle, or hash ring. This allows servers and objects to scale without affecting the overall system.

当我们把hash值映射到一个环上去的话，此时最小值就是0，最大值就是 360 (角度). 我们把之前的例子映射到环上：

现在我们把 server也放到环上，我们可以给server随机分配一个位置. 也可以通过server的ip或者名称计算一个hash值，然后对应到环上的某个位置。然后就变成了这个样子:

因为object的key和 server都在这个环上面，那么我们可以定义一个简单的规则将两者联系起来，比如每个key属于离他最近的逆时针方向的那个server .换句话说，我们想要知道key在哪个server上面，我们只需要沿着逆时针的方向找，直到我们找到一个server为止。就是下面这个样子:

从编程的角度来讲，我们只需要维护一个排序的server的值 (angle) 的list, 然后遍历这个list,找到比key对应的angle值大的那个server. 如果找不到的话，就去list的第一个即可.

为了保证key在server间均匀分布，有一个小小的技巧，我们为每个server分布多个label(angle). 现在我们不只是 A, B, C了，我们有 A0 .. A9, B0 .. B9 和 C0 .. C9. 他们穿插在环中，至于每个server多少个label这个取决于不同情况，比如 如果B的处理能力是A的两倍的话，那么可以为B分布两倍于A的label.那么B就会理论上拥有两倍于A的key.

这样做的好处是什么呢？如果我们把C去掉了，那么我们需要去掉 c0-c9。所有映射到 c的key这时候会被映射到Ax和Bx，但是然来映射到Ax和Bx的key不会发生任何变化。

同样的，当我们加入一个server D 的时候，也只有一部分的key 被映射到D 上，大部分的key并不会变化.

这就是一致性Hash如何解决rehashing的问题的。通常来讲，只有 k/N 数量的key需要被重新定位。k是key的数量，N是服务器的数量。

开源分布式缓存memcache和redis都使用了这种算法。