作者: tiankonguse | 更新日期:
做一个缓存服务,随着数据量增大,命中率越来越低,于是准备增加一致性hash。这里简单记录一下基础知识。
自己负责一个数据统一输出服务,由于访问量很大,增加了一层cache。
但是由于数据量比较大,每个数据的内容大小也很大,单机cache命中率不是很理想。
于是准备改造成一致性hash,提高单机命中率。
这里简单的记录一下一致性hash的基础知识。
一致性hash的思想早在1997年就由MIT的Karger及其合作者提出来了,目标是解决互联网中热点问题(缓存问题)。
当时还有一篇论文,叫做 Web Caching with Consistent Hashing
, 大家可以看看(下面参考文献有链接)。
一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义:
基本的hash是对请求的 key
映射到一个数字,然后对机器数取模。这样就知道该请求去那台机器加载数据了。
假设机器数量不变的话,这种做法勉强还可以接受。虽然取模时请求分布可能不均匀,取决与机器数量。
但是当我们增加或减少机器数量时, 面临一个问题:取模因子变化了。
影响很严重,key映射的机器会全部变化。结果是这个时间大部分请求会不能cache住数据,透传率会突然增高,下层可能被压死。
看到上面的问题,我们第一个能想到的是不能直接取模了。
我们改变机器时,要尽可能的不变更机器与key的对应关系。
此时我们要做的是中间加一层映射。
这个环也不需要取模了,直接是 0~(2^32)-1
即可。
我们把请求的key映射到环上。
hashKey(object1) = key1; hashKey(object2) = key2; hashKey(object3) = key3; hashKey(object4) = key4;
我们把机器也全部映射到环上。
我们定义每个请求的key属于环上顺时针方向的第一个机器。
HashIp(cache A"192.168.1.2") = key A; HashIp(cache B"192.168.1.3") = key B; HashIp(cache C"192.168.1.4") = key C;
假设我们删除了机器 cache B
,那么 cache B
区间的key肯定会受影响的。
按照我们上面的定义, cache B
区间的key会属于顺时针方向第一个机器,即 cache C
.
此时其他区间的key都没有受到影响。
假设我们增加了机器 cache D
,且在 cache B
和 cache C
之间。
则 cache D
到 cache B
之间的key肯定会受影响。
按照我们上面的定义, 这个区间的key会属于 cache D
。
此时其他区间的key依旧都没有受到影响。
我们通过加一层来解决了单调性和负载均衡的问题,但是还有一个问题无法避免:缺少平衡性。
我们把整个区间划分为机器数相等的区间个数。
这样如果某个区间的key特别多的话,那个区间的机器压力就会很大。
这个是很常见的热key问题。
针对这个问题我们暂时没有办法完全避免,但是我们可以减小这个问题的概率:再增加一层虚拟节点
上面提到,只增加一层环存在热点问题,于是我们需要再增加一层虚拟节点来较少热点的概率。
虚拟节点的含义是一个机器不是划分一个大的区间,而是划分很多小的区间。
比如我们对hash的机器增加一个编号后缀。
HashIp(cache A"192.168.1.2?1"); => key A1 HashIp(cache A"192.168.1.2?2"); => key A2
增加虚拟阶段后, 映射大概如下
由于机器虚拟节点多了, 环上就把区间划分为更小的片段了, 这样就大大降低了区间热点的概率了。