注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

小葫芦君(汉斯的博客)

博客迁移到新博客:https://blog.ssxingshou.com

 
 
 

日志

 
 
关于我

小小葫芦商城,为您提供高品质的商品,一流的产品,一流的包装服务,一流的物流服务,放心购买

网易考拉推荐

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

2012-06-04 10:17:53|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一致性哈希简单介绍

  •  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方式将数据迁移的压力分散到各个节点,而不是集中在某些节点上。
  评论这张
 
阅读(828)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017