一致性Hash算法入门及代码实现

最近在看关于分布式相关的知识,很多地方都有提到使用一致性hash算法来实现相关功能。自己度娘了相关知识,特此总结下。

在分布式缓存中,有多台缓存服务器,那么一个缓存set或get操作是在哪个服务器中执行的,这个服务器是怎么确定的?这个问题就牵扯到了hash算法。

计算余数法。就是用取余数的方式来选择服务器节点。具体步骤如下:

1、根据键名计算出键名的整数哈希值,用该哈希值对节点数取余

2、根据余数在节点数组中取出节点。

假设在一个集群中有n个服务器节点,对这些节点编号为0,1,2,…,n-1 。然后,将一条数据(key,value)存储到服务器中。这时我们该如何来选择服务器节点呢?根据上面的步骤我们需要对key计算hash值,然后再对n(节点个数)取余数。最后得到的值就是我们所要的节点。用一个公式来表示:num = hash(key) % n。

一切都运行正常,再考虑如下的两种情况;

1、 一个服务器节点坏掉了(在实际应用中必须要考虑这种情况),这样所有映射到这个服务器节点的缓存都会失效,怎么办,需要把这个服务器节点从集群中移除,这时候服务器集群是 n-1 台,映射公式变成了 hash(key)%(n-1) ;

2、 由于访问加重,需要添加节点 ,这时候服务器是 n+1 台,映射公式变成了 hash(key)%(n+1) ;

1 和 2 意味着什么?这意味着突然之间几乎所有的 cache 都失效了(节点选择进行了重新计算)。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向数据服务器,导致数据服务器压力倍增。

根据以上场景,我们考虑,有没有在增加或删除节点的时候尽可能的减少Cache的失效(完全不影响是不可能的),这个时候一致性hash算法就来了。

一致性Hash算法。考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环,如下面图 1 所示:

一致性哈希算法实现,有以下几个步骤。

1、将对象放置到Hash环

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

hash(o1) = m1

hash(o2) = m2

hash(o3) = m3

hash(o4) = m4

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

2、将机器放置到Hash环

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

hash(c1) = t1

hash(c2) = t2

hash(c3) = t3

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

3、为对象选择机器

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

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

4、处理机器增减的情况

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

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

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

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

5、虚拟节点

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

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

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

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

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

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

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

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

代码实现(Golang版本):

import(

"hash/crc32"

"strconv"

"sort"

)

// 一致性哈希算法,主要用在分布式服务上

// 返回选中的服务器ip

funcconsistentHash(keystring)string{

servers:= []string{

"10.192.15.28",

"10.192.15.29",

"10.192.15.39",

"10.192.15.40",

"10.192.15.41",

"10.192.15.43",

"10.192.15.45",

"10.192.15.54",

}

// 增加虚拟节点,使key分布更均匀

// 定义虚拟节点个数

nums:=32

newServers:=make(map[string]string)

fors:=; s

v:= servers[s]

fori:=1; i

k:= (v +"#"+ strconv.Itoa(i))

newServers[k] = v

}

}

// 对节点进行hash计算

sm:=make(map[int]string)

varcodes[]int

codes=make([]int,)

fork,v:=rangenewServers{

hashCode:=hash(k)

sm[hashCode] = v

codes=append(codes, hashCode)

}

// 对节点hashcode进行排序

sort.Ints(codes)

// 计算key的哈希值

keyHashCode:=hash(key)

length:=len(codes)

fori:=; i

// 顺时针找寻服务器节点

ifcodes[i] > keyHashCode{

returnsm[codes[i]]

}

}

// 如果没有服务器节点被选中,那就返回环中第一个服务器节点

returnsm[codes[]]

}

// hash函数,返回int类型的hash值

funchash(keystring)int{

hash:= crc32.NewIEEE()

hash.Write([]byte(key))

i:= hash.Sum32()

returnint(i)

}

总结

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

参考文章链接:

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180703G0WDGI00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券