一致性hash基础知识
作者: tiankonguse | 更新日期:
做一个缓存服务，随着数据量增大，命中率越来越低，于是准备增加一致性hash。这里简单记录一下基础知识。
背景
自己负责一个数据统一输出服务，由于访问量很大，增加了一层cache。
但是由于数据量比较大，每个数据的内容大小也很大，单机cache命中率不是很理想。
于是准备改造成一致性hash,提高单机命中率。
这里简单的记录一下一致性hash的基础知识。
理论知识
一致性hash的思想早在1997年就由MIT的Karger及其合作者提出来了,目标是解决互联网中热点问题(缓存问题)。
当时还有一篇论文，叫做 Web Caching with Consistent Hashing , 大家可以看看（下面参考文献有链接）。
一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：
- 平衡性(Balance)：哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。
- 单调性(Monotonicity)：如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。
哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。 - 分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。
当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。
这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。
分散性的定义就是上述情况发生的严重程度。
好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。 - 负载(Load)：负载问题实际上是从另一个角度看待分散性问题。
既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。
与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
基本hash的问题
基本的hash是对请求的 key 映射到一个数字，然后对机器数取模。这样就知道该请求去那台机器加载数据了。
假设机器数量不变的话，这种做法勉强还可以接受。虽然取模时请求分布可能不均匀，取决与机器数量。
但是当我们增加或减少机器数量时， 面临一个问题：取模因子变化了。
影响很严重，key映射的机器会全部变化。结果是这个时间大部分请求会不能cache住数据，透传率会突然增高，下层可能被压死。
拓展基本hash
看到上面的问题，我们第一个能想到的是不能直接取模了。
我们改变机器时，要尽可能的不变更机器与key的对应关系。
此时我们要做的是中间加一层映射。
增加一层－环
这个环也不需要取模了，直接是 0~(2^32)-1 即可。
key映射到环上
我们把请求的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
增加虚拟阶段后， 映射大概如下
由于机器虚拟节点多了， 环上就把区间划分为更小的片段了， 这样就大大降低了区间热点的概率了。
参考资料
- 维基百科：一致哈希
- 论文：Web Caching with Consistent Hashing
- Consistent hashing
- 一致性哈希算法
- 一致性哈希算法及其在分布式系统中的应用
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
