一致哈希算法理解(一致哈希学习笔记一)

发现维基百科上只有”一致哈希“这个概念,不知道”一致性哈希”是从哪来的,查看介绍一致性哈希的文章也都说”一致性哈希”是MIT的David Karger及合作者在1997年的学术论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》(论文要付费阅读和下载😓)上提出了的,由此可以推理”一致性哈希”和”一致哈希”是同一个算法。这里按照维基百科的说法称为一致哈希。

一致哈希算法要解决的问题

一致哈希是一种算法,特殊的哈希算法。特殊在什么地方,是为了解决什么问题呢?

考虑这样一个场景,在一个Web系统中,有N台缓存服务器(一般称Cache集群或Cache服务器池),缓存从后端DB拿到的数据,我们就要思考把一个key存到N台服务器中的那一台呢(其实是一个路由选择的问题)?传统的做法是通过负载均衡的方式,把key经一个普通哈希算法(比如余数哈希算法)计算出服务器的节点,然后进行存取操作。

余数哈希算法核心思想:
服务器节点编号 = hash(key) mod N

算法步骤:
0、通过一个hash函数,计算key对应的整数Z,比如PHP的crc32函数

1、用Z对N取模(Z % N)得到的数就是服务器节点编号。

上面这种方式的问题在于,当新增或删除一台服务器的时候,原来计算的服务器节点编号大部分会发生变化,也就是说大部分缓存都会失效,导致缓存服务器大量集中的从DB读取数据更新缓存,即缓存被穿透了,俗称”雪崩”。一致哈希算法可以有效解决这个问题。

一致哈希算法及实现

一致哈希算法步骤:
0、将每一个服务器节点按照ip或者server_name, 通过hash函数(eg: crc32)得到对应的一组hash整数值,这里称做hash_servers,并对得到的整数值按由小到大进行排序。
1、将key也通过上面同一个hash函数计算得到对应hash整数值, 这里称为hash_key。

2、遍历hash_servers,用hash_key与hash_servers中的数逐个比较,当hash_key最后小于hash_servers中的那个数存在时,这个数对应的节点就是这个key所存储的节点,否则存在第一个节点。

明白了算法,在参考实现,理解起来就相对容易。一致哈希算法的实现:
PHP的第一种实现: flexihash
PHP的第二种实现:《一致哈希PHP实现及应用(一致哈希学习笔记二)》

Golang的实现:Github地址
更多语言实现可见Implementations in various languages

一致哈希环

比较直观的理解方式是通过构建一个虚拟的圆环(Hash环)
0、构造一个长度为2^32的整数环

1、根据服务器节点的hash值将节点放在环上对应位置(下图中N1、N2、N3)。

2、根据key的hash值将key放在环上对应位置(下图中k1、k2)。

3、按顺时针方向,在环上查找离key最近的服务器节点,就是目标节点(下图中k1存在N1中,k2存N2中)。

4、新增服务器节点N4(下图中k2将存到N4中)。

5、删除服务器节点N1(下图中k1将存到N4中)。

6、数据倾斜性问题(服务器N2意外宕机,则存在N2上都全部瞬间转移到N3)

7、引入虚拟节点,解决平衡性(数据倾斜)问题(定位到多台虚拟节点上的key实际指向一台,可以做到相对均匀的分布,实际上做了两次key到节点的映射)。

一致哈希特点

冗余少/负载均衡/过渡平滑/存储均衡/关键词单调
具体含义参考:一致性Hash算法背景

应用实例

CouchBase
Memcached客户端实现分布式缓存

一致哈希算法在PHP Memcached扩展中的应用可以查看PHP Memcached扩展源码。源码分析可以参考:https://github.com/bingbo/blog/wiki/PHP的Memcached扩展源码分析

总结

一致哈希算法我们可能觉得很熟悉,但又不能很清楚的理解。我想的原因主要有两个:一是我们经常有意无意听到这个”一致哈希”这个词,比如我们经常听到Memcached客户端用的是一致哈希算法,我们很熟悉,但是并没有真正去学习、深入理解过;二是,很多介绍一致哈希的文章站在很高的起点,作者没有交代一些细节,导致我们理解很费劲。当然这篇文章也有很多没有说清楚,或者表述有误的地方,欢迎留言指正。一旦我们花点时间搞明白了,发现确实不难理解。

思考

有读者提到机器节点hash冲突的情况,应该顺位到下一个槽点(位置)?你怎么考虑,欢迎留言?

参考资料:
https://zh.wikipedia.org/wiki/一致哈希
https://en.wikipedia.org/wiki/Consistent_hashing
https://blog.csdn.net/jeffleo/article/details/68060506
http://afghl.github.io/2016/07/04/consistent-hashing.html
http://imhuchao.com/687.html

一致哈希算法理解(一致哈希学习笔记一)》上有2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注