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

一致性哈希简单介绍

  •  Consistent Hashing 算法早在 1997 年就在论文《Consistent hashing and random trees》中被提出,提出了在动态变化的Cache环境中,哈希算法应该满足的4个适应条件:
  1. 平衡性(Balance)
  2. 单调性(Monotonicity)
  3. 分散性(Spread)
  4. 负载(Load)

一致性哈希原理

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

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

1.png



  • 3个节点平均分布在圆环上,每个节点之间的角度为120°,此时,只要hash函数够均匀,那么每个节点所命中的概率则都是一样的。
  • 如果再增加一个节点,普通的一致性哈希认为无论在那个节点之间增加新的节点,那么与新的节点非相邻的节点尽量保持不变,这样保证一致性哈希的单调性,如图 2:
2.png
  • 新的节点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.png
  • 节点3(n3)因为某种原因不能进行映射,那么圆环上只剩下2个节点(n1、n2),这样原来k1和k3合并成新的k1,即所有的负载全部着落在节点 1(n1)上,同新增加节点一样,虽然保证了单调性,但是明显不能保证负载均衡。

分布式一致性哈希

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

4.png

  • 上图实线部分表示实节点,虚线部分表示虚节点。
  • 当增加新节点或删除节点的时候,保证最小弧度单位不变化,每个节点分别控制插入和数据迁移的大小,如图5所示:

5.png

  • 当新增加节点时

最小弧度中数据迁移大小=最小弧度/节点数
总共数据迁移量=最小弧度中数据迁移大小*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方式将数据迁移的压力分散到各个节点,而不是集中在某些节点上。

Monthly Archives

Pages

Powered by Movable Type 7.7.2

About this Entry

This page contains a single entry by Cnangel published on June 8, 2010 6:58 PM.

如何去除rpm的公钥 was the previous entry in this blog.

distcc 介绍 is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.