Skip to content

Latest commit

 

History

History
46 lines (19 loc) · 3.85 KB

ConsistentHashing.md

File metadata and controls

46 lines (19 loc) · 3.85 KB

一致性哈希:变化世界中的负载平衡

Teradata在1986年发布的分布式数据库中使用了这种技术,但他没有提出这个术语。直到1997年,由David Karger等人在应用于分布式缓存问题中提出了 “一致性哈希” ,作为一种在不断变化的Web服务器集群中分配请求的方法。一致性哈希算法也是负载均衡算法中的一种。常用的负载均衡算法适用于集群,但不一定适用于分布式。

案例背景

在某大促活动中,我们需要将1亿用户数据缓存到1000个Redis实例中,每个Redis实例均摊10万用户数据。通常使用哈希算法(hash(K) mod N )来做映射,先计算用户id的哈希值,然后模运算计算出对应的服务器,最后把对应的数据缓存到对应的服务器即可。此种方法比较简单,但存在一个问题,它不适用于分布式下节点宕机、扩容和缩容的场景。

未命名1550461043.png

假如1号Redis服务宕机,对应10万用户将无法命中缓存。当然1号Redis服务可以做成高可用集群,但又不适用于分布式缓存下节点的扩容与缩容。试想,大促活动结束后,服务器的压力也会减少,没必要使用这么多服务器,可以将1000个Redis实例缩容为100个。随着节点的宕机、扩容和缩容,势必会带来数据的再哈希与重分配。如此海量的数据,将导致缓存服务不可用。

一致性哈希算法

为了解决上述问题,一致性哈希算法孕育而出

图1

首先将分配 2^32 个槽,也就是从 0 到 CodeCogsEqn (1).gif ,如上图,虚拟出环形。通过哈希算法 hash(ip, port) 计算出Redis实例对应的哈希值,然后对 2^32取模,得到映射到环上的值。对于请求来说,先计算出key的哈希值,同样对 2^32取模,得到映射到环上的值。沿着顺时针匹配第一个Redis服务节点。

当添加Redis节点时,也是通过哈希算法 hash(ip, port) 计算出Redis实例对应的哈希值,然后对 2^32 取模,得到映射到环上的值。假设如下图的X节点:

图2

在数据重分配上,仅仅需要将 B节点 和 C节点 之间的数据再哈希、重分配就可以了,B-X之间的数据映射到X节点,X-C之间的数据映射到C节点。这样就避免将全量的数据再哈希、重分配节点。

数据倾斜

图3

如果节点较少,就会造成节点分布不均衡(数据倾斜)的问题,如上图,B-A之间映射的请求远多于A-B之间。就会造成A节点压力增加,而B节点负载较轻。

虚拟节点

图4

为了解决上述的数据倾斜问题,在一致性哈希算法的基础上引入虚拟节点。其思想是,预先分配N个虚拟节点,然后这些虚拟节点再在映射实际节点,能保证虚拟节点映射的数据,不会过于倾斜。图4中,虚拟节点A1和A2对应的服务器为A、虚拟节点B1和B2对应的服务器为B,以此类推。假如A服务器宕机后,虚拟节点B1和B2则无法映射实际服务器,那么可以将数据按照瞬时间就近映射。D2-B1之间的数据映射到节点C1,实际映射的服务器是C;A1-B2之间的数据映射到节点A2,实际映射的服务器是A,这样就避免数据过度倾斜。