一致性 hash 原理及实现(python 版)
使用背景
用户的每一次动态数据的请求,都涉及数据库的访问。而一个系统中,数据库往往是最脆弱的缓解,为了缓解数据库的读压力,通常会将热点数据放入缓存。当用户进行数据请求时,先访问缓存,若有数据直接返回,没有,才进行数据库的查询,并将访问结果写回缓存。从而,挡住读访问的大部分流量。
缓存存储的数据量很大,所以,一般需要搭建缓存服务器集群,这样就需要把不同的数据放入不同的缓存服务器,当用户请求到来时,根据用户的请求的内容,从不同的缓存服务器获取数据。
从缓存中获取数据就涉及到缓存的路由选择。
一致性hash原理
最简单的路由方法就是对key取hash,并取余,通过余数,确定分发到哪一个缓存服务器。但是,这样,当增加或缓存服务时,会有大量的key,变换访问是缓存服务器。从而,导致缓存击穿、雪崩等一系列问题。
为了解决这一情况,提出了一致性hash。
将缓存服务器的哈希值映射到0~2^32的圆上。
当请求到来时,将请求也映射到0~2^32的圆。并开始顺时针查找,从找到的第一个缓存服务器上,获取数据。
基于虚拟节点的一致性hash算法
一致性hash解决了增加/下线 缓存服务器,可能引起的缓存击穿等问题。但是当缓存服务器数量较少时,出现数据倾斜等问题。
为了解决这个问题,产生了基于虚拟节点的一致性hash算法。即,一个缓存服务器映射到hash环上的多个地址。从而,减少数据倾斜的情况。
代码实现
一致性hash实现
基于虚拟节点的一致性hash实现
只需修改HashSeverMgr的add_server和del_server,每添加一个节点时,添加多个虚拟hash节点即可。get_server函数不用修改。
效果比较
为了验证基于虚拟节点的一致性hash,可以将数据更平均的分布在各个服务器上。 测试随机100KV在10节点服务器上分布的标准差。基于虚拟节点的一致性hash,将每个节点虚拟10个节点服务器。
某次运行结果:
consistent_hashing_simply's standard deviation: 86800.2052774
consistent_hashing_virtual's standard deviation: 33318.0594513
由于随机产生key,每次运行结果会有差异,但是,可以从结果看出,基于虚拟节点的一致性hash,可以使数据分布的更平均。
评论