对一致性哈希的理解

前提准备

什么是哈希算法？

       以我自己的理解，哈希算法就是运用哈希函数（即反映变量关系的数学公式）来解决事物之间对应关系的方法。

 

哈希算法产生的背景原因？

         举个例子来说。想象一下我们现在有100亿本书（分别标记为book0~book10^10-1），却只有1亿个柜子(分别标记为cupboard0~cupboard10^8-1)。现在要将这些书摆放到这些柜子上，很显然的是，如果每个柜子上只放一本书的话，就会有剩下的99亿本书还没摆放。因此，必然有一些柜子上摆放的书超过了一本，即一个柜子上有多本书，这就产生了在哈希算法中称为“冲突”的现象。显然，在这种书多柜少的情况下，冲突是不可避免的。我们要做的就是，将这些书合理的分配到各个柜子上，即规划好书本和柜子的对应关系（哪本书对应哪个柜子）。而这种规划就是所谓的哈希算法，找出书本和柜子的对应关系（用哈希函数来表示）。在这个例子中，我们比较容易想到的哈希算法就是：每个柜子放100本书，将book0~book99放到cupboard0中，将book100~book199放到cupboard1中，依次类推，刚好这100亿本书可以放到这1亿个柜子中。而这种对应关系用哈希函数来表示就是：柜子序号=书本序号/100 （求整运算），运用这种关系，我们很容易就能知道哪本书放在哪个柜子中，方便快速。

 

评价哈希算法的好坏

       当然上面这个例子的哈希函数看起来还是挺不错的，因为书本能比较均衡地放在各个柜子上。但将这个哈希函数改为：柜子序号=书本序号/10000,这样的话1个柜子上就摆放了10000本书，这样就只需要10^6个柜子就够了，还有10^8-10^6个柜子没有用到（相当于只用到了柜子资源的10^6/10^8=1%），这大大的浪费了柜子资源，使得书本资源过于集中在少数柜子资源上，增加了单个柜子的负载。因此一个良好的哈希函数要做到负载均衡。

 

一致性哈希

      经过上面的准备，下面就可以进入正题了。

什么是一致性哈希？

      其实也就是一种哈希算法，只是它着重考虑到了容错性和扩展性的一些问题。下面从它产生的背景来分析就会容易理解了。

 

一致性哈希产生的背景原因？

     就如上面举的关于书本和柜子的例子。互联网世界也存在类似的现象。只需将书本换为客户端（可以看作是我们的电脑或手机打开的网页浏览器），将柜子换为服务器（可以看作是web服务器）。数量和上面的例子一样，客户端是100亿，服务器端是1亿。实际上，客户端和服务器也是有标记的，那就是带有唯一性的IP号（类似于我们的身份证号码）。同样的，由于客户端多、服务器少，有的单个服务器肯定要服务于多个客户端。那么我们就需要一个哈希函数来分配他们之间的对应关系（哪个客户端去访问哪个服务器）。如果按照像上面例子一样的哈希函数（当然IPV4协议的IP号是由4个字节组成的，最多表示2^32个IP地址，对IP地址的使用也有相应的限制，不同于上面的例子，但这里只是用来帮助理解，所以也无妨），IP号为0的服务器对应于IP号为0~99的客户端，IP号为1的服务器对应于IP号为100~199的客户端，依次类推。

    现在容错性的问题来了。那么多服务器，总会有部分服务器由于各种原因崩溃掉，假设崩溃的是IP号为1的服务器，那么IP号为100~199的客户端将无法访问该服务器。更何况一亿台服务器，挂掉的肯定不止这么一两个，那么将会有许多用户将不能通过客户端访问到服务器。因此，怎样处理这些挂掉的服务器，怎样让这些不能连接上服务器的客户端能重新连上服务器就成了要解决的问题。这也就一致性哈希所强调的单调性。网上很多资料提到同一种方法，我也就简单的介绍一下这种方法。通过将客户端的IP号和服务器的IP号映射到同一个环形hash空间中，然后顺时针将客户端对应到相邻的服务器，如图所示：

                                      

                                 

客户端5将连接到顺时针与其相邻的服务器0，客户端155连接到服务器1，客户端370,350连接到服务器4。如果此时服务器0挂掉了，那么客户端将连接到下一个存活的服务器1。这样保证了整个系统的容错性。

     同样的，为了减轻单个服务器的负载或为了服务更多的客户端，需要添加服务器，假如添加一个服务器X，那么如图所示：

 

 

由于服务器的key值在服务器1和服务器4的key值之间，因此客户端350将连接到服务器X，其他的连接将保持不变。这保证了系统的扩展性。

推荐几个链接，写得图文并茂，容易理解：

http://blog.csdn.net/sparkliang/article/details/5279393

http://hi.baidu.com/ysuhy/item/84d095f198b06508d99e72cb