假设你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache 。
hash(object) % N
一切都运行正常,那么考虑如下的两种情况:
hash(object)%(N-1)
;hash(object)%(N+1)
;1 和 2 意味着什么?这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向后台服务器。
再来考虑第三个问题,由于硬件能力越来越强,你可能想让后面添加的节点多做点活,显然上面的 hash 算法也做不到。
有什么方法可以改变这个状况呢,这就是 consistent hashing...
一致性哈希把哈希值想象成一个环,比如说在 0 ~ 2^32-1 这个范围内,然后将节点(名字、IP等)求哈希之后分布到环上。当有访问请求时,把请求信息求哈希之后,寻找小于该哈希值的下一个节点。
当有节点宕机的时候,请求会依次查找下一个节点,从而不让所有节点的缓存都失效。
当加入新节点的时候,只会影响一个区间内的请求,也不会影响其他区间。
如下图所示:
以上虽然解决了大部分问题,但是还有三个问题:
这时候可以引入虚拟节点。原始的一致性哈希中,每个节点通过哈希之后在环上占有一个位置,可以通过对每个节点多次计算哈希来获得多个虚拟节点。
比如说,本来我们通过节点的 IP 来计算哈希
hash('10.1.1.1') => n1
hash('10.1.1.2') => n2
hash('10.1.1.3') => n3
现在引入两倍的虚拟节点之后
hash('10.1.1.1-1') => n1-1
hash('10.1.1.1-2') => n1-2
hash('10.1.1.2-1') => n2-1
hash('10.1.1.2-2') => n2-2
hash('10.1.1.3-1') => n3-1
hash('10.1.1.3-2') => n3-2
如图所示:
引入虚拟节点之后:
最后,一致性哈希可以用跳表或者平衡二叉树来实现。
参考文档: