大数据体系【概念认知】系列-3:一致性hash算法

原创
2014/10/27 17:36
阅读数 249

阅读前提:

一致性hash算法设计的最初目标就是解决网络之中的热点问题

   

一致性Hash的描述

这里简单的对于Hash算法进行描述,之后,再对一致性Hash算法进行描述。


Hash算法是将任意长度的二进制的值,映射为较短的固定长度的二进制值,这个小的二进制值称为

hash值。


一致性hash算法

设计的目的是为了解决英特网之中的热点问题,和一致性hash算法相对应的是CARP的算法,前者是对后者的修正 。


简单的来说,一致性Hash是将整个Hash值空间组织成为一个虚拟的环,如假设某hash函数 H的值空间为 

0-2……23 -1 . 也就是指代一个32位的无符号的整类,整个Hash空间环如下 :


简要来看, 这是一个环,组成环的是每一个点,hash空间,按照顺时间方向来组织,0和2^32-1在时钟零点方向重合,之后,为了确定每台服务器在空间上的位置,通常而言,会将主机的Host名字,或者Ip地址对每一天服务器进行Hash寻址,

比如在空间之中有三台服务,进行Hash寻址,他在空间之中的位置分布如下所示:

    

三台机器,在进行Hash的处理以后。得到了一个地址,这个地址在Hsah环上对应的地址如下所示:


第一步解决好了,机器怎么存好解决了,那么数据该怎么存?

数据其实和机器一样,也就是需要使用一个Hash的算法来判断数据该访问哪一台机器,首先,将数据Key使用相同的函数H

来计算出hash值 h,依据 h这个值来确定我们在环上的位置,从此位置沿环 顺时钟的向下的去寻找,遇到的第一台服务器就是其应存储的服务器,数据存放在这台服务器上,比如 下图,我们有了四个数据,在进行Hash算法的取值以后,在空间上的位置如下:







一致性Hash映射的一个整体描述图如下所示:

igz


一致性Hash的容错性和可扩展性的分析

   传统的hash算法,存在着容错性和可扩展性的问题,尤其在增加服务器和减少服务器的时候,如果还要继续的工作,那么一定需要对算法进行修改。在这一节里,我们将会对一致性Hash算法的容错性和可扩展性进行介绍。假设Server3 突然停下来,那么就会出现如下的情况:


    机器Server3在集群之中消失了。那么整个topology 结构就改变了,如下所示:

    

 依据一致性的Hash算法, A依然是按照顺序时钟方向找到Server1,BCD这三个数据,将直接放置在Server2之上,先对于ServerB的消失,我们能确定的是,BC的位置依旧是机器3,改变的只是机器2之前的节点,


一致性Hash的算法在集群减少的时候,能将集群的数据变动减小到最小的值。

接下来的情况,我们试图在 当前的Hash 环的境况之下,添加一台新的,来看看hash环是如何变化的。




数据3依旧不变,而数据2将被分布到新添加的节点Server4 之上。

展开阅读全文
打赏
0
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部