文章收录在网站:http://hardyfish.top/
文章收录在网站:http://hardyfish.top/
文章收录在网站:http://hardyfish.top/
文章收录在网站:http://hardyfish.top/
一致性Hash算法
假如有三台服务器编号node0
、node1
、node2
,现在有3000万个key
,希望可以将这些个key均匀的缓存到三台机器上?
可以使用取模算法
hash(key)% N
,对key进行hash运算后取模,N是机器的数量。但服务器数量N发生变化后
hash(key)% N
计算的结果也会随之变化。
一致性hash算法本质上也是一种取模算法,不过不同于上边按服务器数量取模,一致性hash是对固定值2^32
取模。
IPv4的地址是4组8位2进制数组成,所以用
2^32
可以保证每个IP地址会有唯一的映射。
将这2^32
个值抽象成一个圆环,圆环的正上方的点代表0,顺时针排列,以此类推,1、2、3、4、5、6……直到2^32-1
,而这个由2的32次方个点组成的圆环统称为hash环
。
服务器映射到hash环:
使用服务器IP地址进行hash计算,用哈希后的结果对
2^32
取模,结果一定是一个0到2^32-1
之间的整数,而这个整数映射在hash环上的位置代表了一个服务器,依次将node0
、node1
、node2
三个缓存服务器映射到hash环上。
一致性hash的优势:
假如业务量激增,系统需要进行扩容增加一台服务器
node-4
,刚好node-4
被映射到node-1
和node-2
之间,沿顺时针方向对象映射节点,发现原本缓存在node-2
上的对象key-4
、key-5
被重新映射到了node-4
上,而整个扩容过程中受影响的只有node-4
和node-1
节点之间的一小部分数据。假如
node-1
节点宕机,沿顺时针方向对象映射节点,缓存在node-1
上的对象key-1
被重新映射到了node-4
上,此时受影响的数据只有node-0
和node-1
之间的一小部分数据。
数据偏斜问题:
在服务器节点数量太少的情况下,很容易因为节点分布不均匀而造成数据倾斜问题,被缓存的对象大部分缓存在
node-4
服务器上,导致其他节点资源浪费,系统压力大部分集中在node-4
节点上,这样的集群是非常不健康的。
一致性Hash算法引入了一个虚拟节点机制,即对每个服务器节点计算出多个hash值,它们都会映射到hash环上,映射到这些虚拟节点的对象key,最终会缓存在真实的节点上。
一致性hash的应用场景:
一致性hash在分布式系统中应该是实现负载均衡的首选算法,比如日常使用较多的缓存中间件
memcached
和redis
集群都有用到它。