一致性hash算法 - consistent hashing

  1、   情景分析

前一篇博文分析了HashMap源码，HashMap在许多场景中作为存储数据的不二选择。

但是否使用HashMap就能解决所有在空间和时间的均衡问题？？

下面考虑使用HashMap的二个极端情景:

原来有 N 台Server，所有数据通过一种 hash 算法（以hash(key)%N为例）映射到 N 台Server 中。

情景一：其中的 M 台服务器失效，那么需要将服务器 M 移除；或者访问量锐减，撤除 M 台服务器

 ，此时服务器的数量为 (N-M)台，最后，映射公式变成了 hash(key)%(N-M)；

情景二：由于访问量加大，需要添加 M 台Server ，这时候 Server 是 (N+M) 台，映射公式变成了 hash(key)%(N+M)。

    这两种情景看似只是数学公式上的小差别，但是对于 Server 和 Internet 来说是一个巨大的灾难。

海量的数据重新重新计算hash然后定位到不同的 Server 中，整个过程对Internet的占用也很严重。

这种情况是非常糟糕的。

    用专业的说法来总结上述问题：以上hash算法的问题在于容错性和扩展性不好。

所谓容错性是指当系统中某一个或几个服务器变得不可用时，整个系统是否可以正确高效运行；

而扩展性是指当加入新的服务器后，整个系统是否可以正确高效运行。

   一个设计良好的分布式哈希方案应该具有良好的单调性，即服务节点的增减不会造成大量哈希重定位。一致性哈希算法就是这样一种哈希方案。

2、    一致性哈希算法算法简述

    一致性哈希算法（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在零点中方向重合。

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

    接下来使用如下算法定位数据访问到相应 Server：将数据key使用相同的函数 Hash 计算出哈希值h，通根据h确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。该解决方案有点像Hash的开放寻址中的线性探测法解决hash冲突的策略。 

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

根据一致性哈希算法，数据A会被定为到Server 1上，D被定为到Server 3上，而B、C分别被定为到Server 2上。

3、    一致性哈希算法的容错性与可扩展性分析

    3.1、下面分析一致性哈希算法的容错性：现假设Server 3挂了（专业一点就是宕机）：

    可以看到此时A、C、B不会受到影响，只有D节点被重定位到Server 2。一般的，在一致性哈希算法中，如果一台 Server 不可用，则受影响的数据仅仅是此 Server 到其环空间中前一台 Server（即顺着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

  3.2、分析可拓展性：如果我们在系统中增加一台服务器Memcached Server 4

此时A、D、C不受影响，只有B需要重定位到新的Server 4。一般的，在一致性哈希算法中，如果增加一台 Server ，则受影响的数据仅仅是新 Server 到其环空间中前一台Server （即顺着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

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

4、   虚拟节点

    一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如我们的系统中有两台 server，其环分布如下：

    此时必然造成大量数据集中到Server 1上，而只有极少量会定位到Server 2上。为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。

    具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，我们决定为每台服务器计算三个虚拟节点，于是可以分别计算“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”、“Memcached Server 2#1”、“Memcached Server 2#2”、“Memcached Server 2#3”的哈希值，于是形成六个虚拟节点：

    同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”三个虚拟节点的数据均定位到Server 1上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布，避免出现雪崩的情况。

5、  总结 

    在动态分布式缓存系统里哈希算法承担着系统架构上的关键点。 使用分布更合理的算法可以使得多个服务节点间的负载相对均衡，可以最大程度的避免资源的浪费以及服务器过载。 使用一致性哈希算法，可以最大程度的降低服务硬件环境变化带来的数据迁移代价和风险。 使用更合理的配置策略和算法可以使分布式缓存系统更加高效稳定。

简单的一致性哈希算法，可以使用MD5算法来作为hash算法, 对于各个hash算法的比较, 可以参考下面的讨论

http://www.iteye.com/topic/346682

参考资料地址：

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

http://en.wikipedia.org/wiki/Consistent_hashing

http://www.jiacheo.org/blog/174