一致性哈希算法

   在上次去YY面试中还遇到过一个问题，就是一致性哈希算法。网上有篇文章解释得非常清楚(戳我)， 综合阅读分析后，总结一下我的理解。

   历史

   一致性哈希算法是1997年由MIT提出的一种分布式哈希(DHT)实现算法，设计目标是为了解决因特网中的热点(Hot Spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得分布式哈希(DHT)可以在P2P环境中真正得到应用。

   应用场景

   假设我们有一个网站，最近流量增加，服务器压力增大，之前直接读写数据库的方式无法满足需求，于是我们想引入Memcached作为缓存机制。现在我们假设一共有三台机器可以作为Memcached服务器，如下图：

很显然，很简单的策略是将Memcached请求随机发送到一台Memcached服务器，但是这种策略可能会带来两个问题：一是同一份数据可能被存在不同的机器上而造成数据冗余，二是有可能某数据已经被缓存但是访问没有命中，因为无法保证对相同key的所有访问都被发送到相同的服务器。因此，随机策略无论是时间效率还是空间效率都不是非常好。

要解决上述问题只需要做到如下一点：保证对相同key的访问会被发送到相同的服务器。最常用的方法是计算哈希。例如对于每次访问，可以按如下算法计算其哈希值：

          h = Hash(key) % 3

其中Hash是一个从字符串到正整数的哈希映射函数。这样，如果我们将Memcached Server分别编号为0，1，2，那就可以根据上式和key计算出服务器编号h,然后去访问。

这个方法虽然解决了上面提到的两个问题，但是存在一些其他的问题。如果将上述方法抽象，可以认为通过：

         h = Hash(key) % N

这个公式计算每个key的请求应该被发送到哪台服务器，其中N为服务器的台数，并且服务器按照0 ～(N-1)编号。

这个算法的问题在于容错性和扩展性不好。所谓容错性是指当系统中某一个或几个服务器变得不可用时，整个系统是否可以正确高效运行；而扩展性是指当加入新的服务器后，这个系统是否可以正确高效运行。

现假设有一台服务器宕机了，那么为了填补空缺，要将宕机的服务器从编号列表中移除，后面的服务器按顺序前移一位并将其编号值减一，此时每个key就要按h = Hash(key) % (N-1)重新计算；同样，如果新增加一台服务器，虽然原有服务器编号不用改变，但是要按h = Hash(key) % (N+1)重新计算哈希值。因此系统中一旦有服务器变更，大量的key会被重新定位到不同的服务器从而造成大量缓存不命中。而这种情况在分布式系统中是非常糟糕的。 这个时候就需要用一致性哈希算法了。

算法简述

一致性哈希算法(Consistent Hashing)最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说，一致性哈希将整个哈希值空间组这成一个虚拟的圆环，如假设某哈希函数H的值空间为0 ~ 2^32 - 1(即哈希值是一个32位无符号整形)，整个哈希空间环如下：

整个空间按顺时针方向组织，0和2^32-1在零点中方向重合。

下一步将各个服务器使用H进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中三台服务器使用ip地址哈希后在环空间的位置如下：

接下来使用如下算法定位数据访问到相应服务器：将数据key使用相同的函数H计算出哈希值H,根据h确定此数据在环中的位置，从此位置沿环顺时针行走，第一台遇到的服务器就是其应该定位到的服务器。

假如我们有A,B,C,D四个数据对象，经过哈希计算后，在环空间的位置如下：

根据一致性哈希算法，数据A会被定位到Server1上，D会被定位到Server3上，而B,C则会被定位到Server2上。

容错性与可扩展性分析

容错性

     现假设Server3宕机了：

   可以看到此时A,C,B不会受到影响，只有D节点被重定位到Server2。

扩展性

  如果我们在系统中增加一台服务器Memcached Server4:

此时A,D,C不受影响，只有B需要重新定位到新的Server4.

综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

目前一致性哈希基本成为分布式系统组件的标准配置，例如Memcached的各种客户端都提供内置的一致性哈希支持。