一致性哈希

技术宅 rainforest 8年前 (2012-09-13) 402次浏览 0个评论

之前参加了百度的一个技术沙龙,了解到了一致性哈希的概念,后来看人在微薄里面也有讨论。上次培训的时候,也有人提到了一致性哈希算法。但是由于时间原因,一直没对一致性哈希做深入的了解。

今天阅读了几篇博文,发现一致性哈希的概念其实是比较简单的。我们采用传统的方法做分流的时候,比如将流量分给多台服务器进行处理的时候,我们会对流量取模,然后分给对应的机器进行处理。但是这样有个问题,如果用于存储领域,在机器增加或减少的时候,会造成数据的大规模移动。

回想平时我们做负载均衡,按querystring签名对后端节点取模是最简单也是最常用的算法,但节点的增删后所造成的问题显而易见,原有的请求几乎都 落不到同一台机器上。优化一点的是carp算法(用机器ip和querystring一起做hash,选取hash值最小的一台),只让1/n的数据受到 影响。

一致性哈希就是来解决这个问题的,他把机器映射到一个环上(比如32位的空间),数据也映射到一个环上,然后把数据存储到离该数据最近的机器上,就能解决问题。这样机器的删减,只影响那些离删减机器比较近的数据。

一致性哈希也只是提出四个概念和原则,并没有提及具体实现:

  1. balance:哈希结果尽可能的平均分散到各个节点上,使得每个节点都能得到充分利用。
  2. Monotonicity:上面也说了,如果是用签名取模算法,节点变更会使得整个网络的映射关系更改。如果是carp,会使得1/n的映射关系更改。一致性哈希的目标,是节点变更,不会改变网络的映射关系。
  3. spread:同一份数据,存储到不同的节点上,换言之就是系统冗余。一致性哈希致力于降低系统冗度。
  4. load:负载分散,和balance其实是差不多的意思,不过这里更多是指数据存储的均衡,balance是指访的均衡。

具体可以参考以下文章:http://stblog.baidu-tech.com/?p=42


乐趣公园 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:一致性哈希
喜欢 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址