Hash一致性算法

2017/04/15

Hash一致性算法

介绍

我们知道一台reids机器最大内存是有上限的,现在随着业务的发展,现有一台redis内存不够用,这个时候我们使用n台服务器,那怎么做到key跟服务器的映射问题。

首先我们想到计算哈希

h = Hash(key) % n

这种方法可以解决这个问题,但是当一台宕机,当增加或减少一台缓存服务器时这种方式可能会改变所有资源对应的hash值,也就是所有的缓存都失效了,这会使得缓存服务器大量集中地向原始内容服务器更新缓存。下面一致性HASH算法。

一致性哈希算法

一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0 - 232-1(即哈希值是一个32位无符号整形),整个哈希空间环如下:

我们用每个缓存服务器ip作为关键字进行hash , 这样每台机器就能确定在这个圆环上的位置

当我们有一个key需要选择映射到那台服务器时我们将数据的key使用相同的函数算出hash值,定位到圆环上的位置然后沿着这个位置顺时针第一台遇到的缓存服务器就是这个key实际映射到的机器

虚拟节点

当我们的缓存服务器比较少的时候可能出现 缓存分布不均匀的问题,这个时候我们引入虚拟节点来解决这个问题

Post Directory