国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > 一致性Hash(Consistent Hashing)原理剖析

一致性Hash(Consistent Hashing)原理剖析

来源:程序员人生   发布时间:2017-02-22 08:10:34 阅读次数:3315次

     在业务开发中,我们常把数据持久化到数据库中。如果需要读取这些数据,除直接从数据库中读取外,为了减轻数据库的访问压力和提高访问速度,我们更多地引入缓存来对数据进行存取。读取数据的进程1般为:

一致性Hash(Consistent Hashing)原理剖析

图1:加入缓存的数据读取进程

对散布式缓存,不同机器上存储不同对象的数据。为了实现这些缓存机器的负载均衡,可使用式子1来定位对象缓存的存储机器:

m = hash(o) mod n ——式子1

其中,o为对象的名称,n为机器的数量,m为机器的编号,hash为1hash函数。图2中的负载均衡器(load balancer)正是使用式子1来将客户端对不同对象的要求分派到不同的机器上履行,例如,对对象o,经过式子1的计算,得到m的值为3,那末所有对对象o的读取和存储的要求都被发往机器3履行。

一致性Hash(Consistent Hashing)原理剖析

图2:如何利用Hash取模实现负载均衡

式子1在大部份时候都可以工作得很好,但是,当机器需要扩容或机器出现宕机的情况下,事情就比较辣手了。

当机器扩容,需要增加1台缓存机器时,负载均衡器使用的式子变成:

m = hash(o) mod (n + 1) ——式子2

当机器宕机,机器数量减少1台时,负载均衡器使用的式子变成:

m = hash(o) mod (n - 1) ——式子3

我们以机器扩容的情况为例,说明简单的取模方法会致使甚么问题。假定机器由3台变成4台,对象o1由式子1计算得到的m值为2,由式子2计算得到的m值却可能为0,1,2,3(1个 3t + 2的整数对4取模,其值可能为0,1,2,3,读者可以自行验证),大约有75%(3/4)的可能性出现缓存访问不命中的现象。随着机器集群范围的扩大,这个比例线性上升。当99台机器再加入1台机器时,不命中的几率是99%(99/100)。这样的结果明显是不能接受的,由于这会致使数据库访问的压力陡增,严重情况,还可能致使数据库宕机。

1致性hash算法正是为了解决此类问题的方法,它可以保证当机器增加或减少时,对缓存访问命中的几率影响减至很小。下面我们来详细说1下1致性hash算法的具体进程。

1致性Hash环

1致性hash算法通过1个叫作1致性hash环的数据结构实现。这个环的出发点是0,终点是2^32 - 1,并且出发点与终点连接,环的中间的整数按逆时针散布,故这个环的整数散布范围是[0, 2^32⑴],以下图3所示:

一致性Hash(Consistent Hashing)原理剖析

图3:1致性Hash环

将对象放置到Hash环

假定现在我们有4个对象,分别为o1,o2,o3,o4,使用hash函数计算这4个对象的hash值(范围为0 ~ 2^32⑴):

hash(o1) = m1

hash(o2) = m2

hash(o3) = m3

hash(o4) = m4

把m1,m2,m3,m4这4个值放置到hash环上,得到以下图4:

一致性Hash(Consistent Hashing)原理剖析

图4:放置了对象的1致性Hash环

将机器放置到Hash环

使用一样的hash函数,我们将机器也放置到hash环上。假定我们有3台缓存机器,分别为 c1,c2,c3,使用hash函数计算这3台机器的hash值:

hash(c1) = t1

hash(c2) = t2

hash(c3) = t3

把t1,t2,t3 这3个值放置到hash环上,得到以下图5:

一致性Hash(Consistent Hashing)原理剖析

图5:放置了机器的1致性Hash环

为对象选择机器

将对象和机器都放置到同1个hash环后,在hash环上顺时针查找距离这个对象的hash值最近的机器,即是这个对象所属的机器。

例如,对对象o2,顺序针找到最近的机器是c1,故机器c1会缓存对象o2。而机器c2则缓存o3,o4,机器c3则缓存对象o1。

一致性Hash(Consistent Hashing)原理剖析

图6:在1致性Hash环上为对象选择机器

处理机器增减的情况

对线上的业务,增加或减少1台机器的部署是常有的事情。

例如,增加机器c4的部署并将机器c4加入到hash环的机器c3与c2之间。这时候,只有机器c3与c4之间的对象需要重新分配新的机器。对我们的例子,只有对象o4被重新分配到了c4,其他对象仍在原有机器上。如图7所示:

一致性Hash(Consistent Hashing)原理剖析

图7:增加机器后的1致性Hash环的结构

如上文前面所述,使用简单的求模方法,当新添加机器后会致使大部份缓存失效的情况,使用1致性hash算法后这类情况则会得到大大的改良。前面提到3台机器变成4台机器后,缓存命中率只有25%(不命中率75%)。而使用1致性hash算法,理想情况下缓存命中率则有75%,而且,随着机器范围的增加,命中率会进1步提高,99台机器增加1台后,命中率到达99%,这大大减轻了增加缓存机器带来的数据库访问的压力。

再例如,将机器c1下线(固然,也有多是机器c1宕机),这时候,只有原有被分配到机器c1对象需要被重新分配到新的机器。对我们的例子,只有对象o2被重新分配到机器c3,其他对象仍在原有机器上。如图8所示:

一致性Hash(Consistent Hashing)原理剖析

图8:减少机器后的1致性Hash环的结构

虚拟节点

上面提到的进程基本上就是1致性hash的基本原理了,不过还有1个小小的问题。新加入的机器c4只分担了机器c2的负载,机器c1与c3的负载并没有由于机器c4的加入而减少负载压力。如果4台机器的性能是1样的,那末这类结果其实不是我们想要的。

为此,我们引入虚拟节点来解决负载不均衡的问题。

将每台物理机器虚拟为1组虚拟机器,将虚拟机器放置到hash环上,如果需要肯定对象的机器,先肯定对象的虚拟机器,再由虚拟机器肯定物理机器。

说得有点复杂,其实进程也很简单。

还是使用上面的例子,假设开始时存在缓存机器c1,c2,c3,对每一个缓存机器,都有3个虚拟节点对应,其1致性hash环结构如图9所示:

一致性Hash(Consistent Hashing)原理剖析

图9:机器c1,c2,c3的1致性Hash环结构

假定对对象o1,其对应的虚拟节点为c11,而虚拟节点c11对象缓存机器c1,故对象o1被分配到机器c1中。

新加入缓存机器c4,其对应的虚拟节点为c41,c42,c43,将这3个虚拟节点添加到hash环中,得到的hash环结构如图10所示:

一致性Hash(Consistent Hashing)原理剖析

图10:机器c1,c2,c3,c4的1致性Hash环结构

新加入的缓存机器c4对应1组虚拟节点c41,c42,c43,加入到hash环后,影响的虚拟节点包括c31,c22,c11(顺时针查找到第1个节点),而这3个虚拟节点分别对应机器c3,c2,c1。即新加入的1台机器,同时影响到原本的3台机器。理想情况下,新加入的机器同等地分担了原有机器的负载,这正是虚拟节点带来的好处。而且新加入机器c4后,只影响25%(1/4)对象分配,也就是说,命中率依然有75%,这跟没有使用虚拟节点的1致性hash算法得到的结果是相同的。

总结

1致性hash算法解决了散布式环境下机器增加或减少时,简单的取模运算没法获得较高命中率的问题。通过虚拟节点的使用,1致性hash算法可以均匀分担机器的负载,使得这1算法更具现实的意义。正因如此,1致性hash算法被广泛利用于散布式系统中。

参考资料

https://en.wikipedia.org/wiki/Consistent_hashing

https://www.codeproject.com/articles/56138/consistent-hashing

《大型网站技术架构——核心原理与安全分析》,李智慧著,电子工业出版社


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生