一种特殊的一致性哈希算法的研究

一致性哈希简单介绍

     Consistent Hashing 算法早在 1997 年就在论文《Consistent hashing and random trees》中被提出，提出了在动态变化的Cache环境中，哈希算法应该满足的4个适应条件：

    平衡性(Balance)
    单调性(Monotonicity)
    分散性(Spread)
    负载(Load)

一致性哈希原理

一致性哈希将key用hash函数进行映射，映射出来的所有点能够分布到一个圆环内，实际上consistent hashing 是一种 hash 算法, 在改变映射内容的大小时，而不需要改变hash算法，且能够尽可能小的改变已存在 key 映射关系，尽可能的满足单调性的要求。。这里我要讲述一种特殊的一致性哈希——分布式一致性哈希(Distributed Consistent Hashing)：
普通的一致性哈希

    分布式一致性哈希(DCH)满足节点的对称分布，普通的一致性哈希表现如图1：




    3个节点平均分布在圆环上，每个节点之间的角度为120°，此时，只要hash函数够均匀，那么每个节点所命中的概率则都是一样的。

    如果再增加一个节点，普通的一致性哈希认为无论在那个节点之间增加新的节点，那么与新的节点非相邻的节点尽量保持不变，这样保证一致性哈希的单调性，如图 2：



    新的节点4（n4）自由分配到节点2（n2）和节点3（n3）之间，那么原来的key的映射范围k3变成了新的k3和k4，插入时，新的k3将着落在节点 4（n4）上；新的k4将着落在节点3上（n3）。为了节点的老数据不丢失，我们还需要将节点3上的属于k3范围的数据迁移到新的节点4（n4）上，并定期删除节点3（n3）的冗余数据（一致性哈希的分散性），这样在查询时，不会有命中不到的情况。虽然保证了一致性哈希的单调性，但是这样的方式不能保证节点的负载均衡，毕竟大部分的查询会着落在节点1（n1）和节点2（n2）上。

    如果减少节点，普通的一致性哈希情况如图3：



    节点3（n3）因为某种原因不能进行映射，那么圆环上只剩下2个节点（n1、n2），这样原来k1和k3合并成新的k1，即所有的负载全部着落在节点 1（n1）上，同新增加节点一样，虽然保证了单调性，但是明显不能保证负载均衡。

分布式一致性哈希

    分布式一致性哈希（DCH）只是在普通的的一致性哈希算法进行的一点改进。同样DCH是将key映射到一个圆环中，与普通一致性哈希不同的是，节点增加了虚拟的节点；包括实节点对之对应的虚节点不是按照连续的弧度范围进行划分，而是定义一个最小的弧度单位（最好能够被圆整分），在这个最小的弧度单位里面均匀放置所有的节点，如图4：



    上图实线部分表示实节点，虚线部分表示虚节点。

    当增加新节点或删除节点的时候，保证最小弧度单位不变化，每个节点分别控制插入和数据迁移的大小，如图5所示：



    当新增加节点时

    最小弧度中数据迁移大小=最小弧度/节点数
    总共数据迁移量=最小弧度中数据迁移大小*360/最小弧度=360/节点数

    与传统一致性哈希比较，迁移数据从1点节点开始增加，那么迁移的数据弧度比例分别为：

    传统一致性哈希（2分法）：1/2+1/4+1/4+1/8+1/8+1/8+1/8+...
    DCH：1/2+1/3+1/4+1/5+1/6+1/7+1/8...

    很明显，传统一致性哈希迁移数据量少，但是负载集中在某几个节点上；而DCH则主要体现在迁移数据会利用各个节点的资源达到均衡，查询时也会比传统一致性哈希更均匀些。

    当删除节点时，并无数据迁移；

总结

    对于在分布式的环境中来说，数据的访问负载均衡更加重要，所以采用DCH的类似架构可能比数据迁移更加重要，比如memcache当中就采用了虚拟节点方式去达到负载均衡的目的。

    对于数据迁移来说，普通的一致性哈希针对的是某两个节点的数据迁移，而DCH针对的是一个分布式的环境，在数据量特别大的时候，DCH方式将数据迁移的压力分散到各个节点，而不是集中在某些节点上。