“分布式哈希”和“一致性哈希”的概念与算法实现

标签: 搜索技术 | 发表时间:2011-01-24 12:34 | 作者:admin Wolf
出处:http://stblog.baidu-tech.com

  分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了。介绍的论文很多,这里做一个入门性质的介绍。

  分布式哈希(DHT)
  两个key point:每个节点只维护一部分路由;每个节点只存储一部分数据。从而实现整个网络中的寻址和存储。
DHT只是一个概念,提出了这样一种网络模型。并且说明它是对分布式存储很有好处的。但具体怎么实现,并不是DHT的范畴。

  一致性哈希:
  DHT的一种实现。本质还是一个哈希算法。回想平时我们做负载均衡,按querystring签名对后端节点取模是最简单也是最常用的算法,但节点的增删后所造成的问题显而易见,原有的请求几乎都落不到同一台机器上。优化一点的是carp算法(用机器ip和querystring一起做hash,选取hash值最小的一台),只让1/n的数据受到影响。
一致性哈希,似乎最早提出是在分布式cache里面的,让节点震荡的时候,影响最小,以提高分布式cache的命中率。不过现在更多的应用在分布式存储和p2p系统里面。

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

  1、balance:哈希结果尽可能的平均分散到各个节点上,使得每个节点都能得到充分利用。

  2、Monotonicity:上面也说了,如果是用签名取模算法,节点变更会使得整个网络的映射关系更改。如果是carp,会使得1/n的映射关系更改。一致性哈希的目标,是节点变更,不会改变网络的映射关系。

  3、spread:同一份数据,存储到不同的节点上,换言之就是系统冗余。一致性哈希致力于降低系统冗度。

  4、load:负载分散,和balance其实是差不多的意思,不过这里更多是指数据存储的均衡,balance是指访的均衡。

  Chord算法:
  一致性哈希有多种实现算法,最关键的问题在于如何定义数据分割策略和节点快速查询。

  chord算是最为经典的实现。cassandra中的DHT,基本是chord的简化版。

  网络中每个节点分配一个唯一id,可以通过机器的mac地址做sha1,是网络发现的基础。

  假设整个网络有N 个节点,并且网络是呈环状。两个节点间的距离定义为节点间下标差。每个节点会存储一张路由表(finger表),表内顺时针按照离本节点2、4、8、16、32.……2i的距离选定log2N个其他节点的ip信息来记录,主要是为了查询加速。

  存储:数据被按一定规则切割,每一份数据也有一个独立id(查询key),并且和节点id的值域是一样的。然后查找节点,如果存在和数据id一样的节点id,则将这份数据存在该节点上;如果不存在,则存储到离该数据id距离最近的节点上。同时,为了保证数 据的可靠性,会顺时针往下找K个冗余节点,存储这份数据。一般认为K=3是必须的。

  下图简单描述了一个chord网络的部署,绿色节点为机器,编码为hash值。N0节点的finger表可以看出N0节点的路由规则,其他节点也有类似的finger表。蓝色节点为数据,根据hash值找到最近的节点并存储。虚线所指是表示冗余存储。

  查询:先从自己的路由表中,找一个和数据id距离最近、并且存活在网络中的节点next。如果该节点的 id巧合和数据id相等,那么恭喜你。如果不相等,则到next进行递归查找。一般或需要经过多次查询才能找到数据所在的节点,而这个次数是可以被证明小于等于log2N的。

  在这个查询的过程中就体现了路由表的选取优势了,其实是实现了一个二分查找,从每个节点来观察网络,都是将网络分成了log2N块,最大一块里面有N/2个节点。路由表里面其实是记录了每一块的第一个节点。这样每一次查询,最少排除了一半的节点。保证在 log2N次内找到目标节点。

  下图简单展示了从N0节点查找N21节点的一个数据的过程,通过finger表经过2跳到达目的地。

  新增一个节点i:需要预先知道网络中已经存活的一个节点j,然后通过和节点j交互,更新自己和其他节点的路由表。并且,需要将离自己距离最近的节点中的数据copy过来,以提供数据服务。

  损失一个节点:路由算法会自动跳过这个节点,并且依靠数据的冗余来持续提供服务。

  KAD算法(Kademlia)
  kad算法其实是在chord上做的优化。主要是两个点:
  1、用二进制(32/64/128)表示一个节点的id,两节点的id异或运算得到节点间的距离。
  2、 每个节点保持的路由信息更丰富,同样是将整个网络按照划分成log2N份,在chord中,是保持log2N个路由节点,但在kad里面,是保存了 log2N个队列。每个队列长度为配置值K,记录网络中对应节点区域的多个节点,并且根据活跃时间对这些节点进行换入换出。
  第一点是方便进行网络划分,节点按照二进制中每一bit的0或1建成一棵二叉树。

  第二点是使得节点查询更迅速。从分割情况我们就可以得知,最坏情况不会差于chord,但保存更多的节点使得命中概率更高。另外队列中根据活跃时间进行换入换出,更有利于在p2p这种节点变更频繁的网络中快速找到有效的节点。

  关于kad的介绍,这篇文章讲的比较详细wenku.baidu.com/view/ee91580216fc700abb68fcae.html

By huanghaibin

相关 [分布 哈希 一致性] 推荐:

“分布式哈希”和“一致性哈希”的概念与算法实现

- Wolf - 搜索研发部官方博客
  分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了. 介绍的论文很多,这里做一个入门性质的介绍.   两个key point:每个节点只维护一部分路由;每个节点只存储一部分数据. 从而实现整个网络中的寻址和存储. DHT只是一个概念,提出了这样一种网络模型. 并且说明它是对分布式存储很有好处的.

一致性哈希算法及其在分布式系统中的应用

- BeerBubble - 博客园-EricZhang's Technology Blog
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用. 首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接下来会对这个算法进行相对详细的描述,并讨论一些如虚拟节点等与此算法应用相关的话题.

一致性哈希算法 - Consistent Hashing

- - CSDN博客云计算推荐文章
一、简单介绍一致性哈希算法.         分布式存储中,常常涉及到负载均衡问题,由于有多个数据存储服务器. 因此当一个对象被保存时候,它究竟应该存放到哪个数据存储服务器上面呢.         又例如:现在假设有一个网站,最近发现随着流量增加,服务器压力越来越大,之前直接读写数据库的方式已经不能满足用户的访问,于是想引入 Memcached 作为缓存机制.

一致性哈希算法(consistent hashing)

- - 互联网 - ITeye博客
consistent hashing由来. 在麻省理工学院用作分布式缓存,现在已经扩大到其他领域. 它被设计来解决hash的什么问题. 假设有m个对象需要被映射到n个node上,简单hash就求余映射hash(object)%n->node,就大致均匀的分布到n个node上了. 可是问题在于如果n发生变化(多了或者少了),就必须重新计算保存对象存放到node,这代价未免有点大.

一致性哈希算法与Java实现

- - Java - 编程语言 - ITeye博客
一致性哈希算法是分布式系统中常用的算法. 比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了,如果是持久化存储则要做数据迁移,如果是分布式缓存,则其他缓存就失效了.

利用一致性哈希水平拆分MySql单表

- - snoopyxdy的博客
Sharding(切片) 不是一门新技术,而是一个相对简朴的软件理念,就是当我们的数据库单机无法承受高强度的i/o时,我们就考虑利用 sharding 来把这种读写压力分散到各个主机上去. 所以Sharding 不是一个某个特定数据库软件附属的功能,而是在具体技术细节之上的抽象处理,是Horizontal Partitioning 水平扩展(或横向扩展)的解决方案,其主要目的是为突破单节点数据库服务器的 I/O 能力限制,注意这里是突破单点数据库服务器的“I/O”能力.

一个速度快内存占用小的一致性哈希算法

- - 鸟窝
这篇论文中提出在动态变化的Cache环境中,哈希算法应该满足的4个适应条件::Balance(均衡)、Monotonicity(单调性)、Spread(分散性)、Load(负载). 在分布式缓存系统中使用一致性哈希算法时,某个节点的添加和移除不会重新分配全部的缓存,而只会影响小部分的缓存系统,如果均衡性做的好的话,当添加一个节点时,会均匀地从其它节点移一部分缓存到新的节点上;当删除一个节点的时候,这个节点上的缓存会均匀地分配到其它活着的节点上.

_00013 一致性哈希算法 Consistent Hashing 探讨以及相应的新问题出现解决

- - CSDN博客云计算推荐文章
一般通常会想到的就是哈希取余了吧. 也就是 Hash(userid)% N (N=12),这样的话也能适当的减小很多压力了,但是这样的话又会产生一些新的问题,增加节点跟减少节点 :. 假如有一台Redis服务器挂掉了,那么是否这样 Hash(userid)% N (N=12) 哈希取余到该Redis的数据会全部丢失呢.

分布式系统的事务及一致性模型

- Roger - NoSQLFan
下面PPT出自10gen的产品和工程高级副总裁 Roger Bodamer ,参加过Mongo Beijing的人应该记得会上的大个子. 下面PPT 主要就分布式系统的事务及一致性模型进行了分析和讨论. 对分布式存储在CAP原理下的选择和实现进行了描述. Google Megastore系统事务机制.

分布式系统中的事务一致性问题

- - CSDN博客架构设计推荐文章
在分布式系统中,我们经常遇到多数据副本保持一致的问题,在我们所能找到的资料中该问题讲的很笼统,模模糊糊的,把多个问题或分类糅合在一起,难以理解. 在思考和翻阅资料后,通俗地把一致性的问题可分解为2个问题:. 1、任何一次修改保证数据一致性. 在弱一致性的算法,不要求每次修改的内容在修改后多副本的内容是一致的,对问题1的解决比较宽松,更多解决问题2,该类算法追求每次修改的高度并发性,减少多副本之间修改的关联性,以获得更好的并发性能.