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

淡淡的烟草味﹌ 2022-01-13 06:25 114阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

阅读前提：

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

# 一致性Hash的描述 #

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

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

hash值。

一致性hash算法

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

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

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

![163920\_HDoK\_1791874.png][163920_HDoK_1791874.png]

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

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

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

![164602\_ev56\_1791874.png][164602_ev56_1791874.png]

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

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

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

![165243\_ev1e\_1791874.png][165243_ev1e_1791874.png]

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

![165336\_a2nT\_1791874.png][165336_a2nT_1791874.png]igz

#     #

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

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

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

![170002\_N5X7\_1791874.png][170002_N5X7_1791874.png]

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

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

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

![171331\_I0qv\_1791874.png][171331_I0qv_1791874.png]

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

转载于:https://my.oschina.net/infiniteSpace/blog/337825

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220113/932392379a524214aa0fa60d9a72f057.png
[163920_HDoK_1791874.png]: /images/20220113/eb36ac72287449768a6ad474469c3959.png
[164602_ev56_1791874.png]: /images/20220113/78d32bf0dce3460fbf92dbacab0e5aae.png
[165243_ev1e_1791874.png]: /images/20220113/23cec46e82454f42803f7579fc67b3ea.png
[165336_a2nT_1791874.png]: /images/20220113/4511d33290d047cbbf04c2cc482bdc92.png
[170002_N5X7_1791874.png]: /images/20220113/30965b8efc4d43b99107fa164f7ce836.png
[171331_I0qv_1791874.png]: /images/20220113/a7f61c036e814d3e9565172a1de2a9c8.png