一致性hash基础知识

背景

有一个数据统一输出服务，由于超时率原来越高，要我增加了一层cache。 但是由于底层数据量比较大(千万级别)，每个数据的资料也很多（几百个），每个数据的资料大小也很大(几字节到几十k不等)，请求的数据又是两级放大的，请求还比较分散，导致单机cache命中率不是很理想。 于是准备改造成一致性hash,提高单机命中率。 这里简单的记录一下一致性hash的基础知识。

这个服务是一个支持批量查询的资料系统。 用户请求的时候会带上N个资料的key以及M个资料的字段名，服务会返回N*M的资料信息。　

这里有三个维度的命中率：字段命中率，key命中率，请求命中率。 当然，其他人只关心请求命中率的。

假设请求有100个key和100个field,只要任意一个key的任意一个字段在cache中过期或未找到，请求命中率中就算未命中。 所以这里的请求命中率很低只有70~80%, 而key的命中率是80~90%, 字段的命中率是90~99.9%.

当然命中率低的根本原因并不是这个，所以这个功能并不能实质性解决命中率问题，不过加了这个肯定可以提供命中率，所以还是加上吧。

理论知识

一致性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
• 一致性哈希算法
• 一致性哈希算法及其在分布式系统中的应用