一致性hash基础知识(二)

背景

在上一篇文章《一致性hash基础知识》中记录了自己负责的缓存服务需要搞成分布式, 然后研究了一致性hash的理论知识.
后来讨论, 发现还有很多问题, 这里就一点一点的看看遇到的问题以及解决方案吧.

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

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

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

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

固定路由

其实上篇提到的机器取模问题, 解决方案并不是只有一致性hash一个.
现在我们再来看看这个问题.

原型: 请求的key hash到一个数字, 然后这个数字直接对机器数取模来决定路由到某台机器上.
问题: 机器减少或增多, key与机器的关系会重映射, 瞬间命中率很低.

上篇的解决方案是对机器也进行hash, 这样key和机器都是一系列数字, 然后我们定义一个规则:每个请求的key属于环上顺时针方向的第一个机器, 也就是第一个大于key的机器.

再深入的看一致性hash这个方案, 其本质是它不是不取模了, 而是取模固定了, 比如是整数最大值.
当取模因子固定后, 再定一个策略把机器与key关联上即可.

看到这里, 很容易得出结论: 解决这个问题的本质在于减少key与机器的重映射, 最常见的方案是取模因子固定.

PS: 当然, 如果取模因子变化了, 但是能保证key和机器的映射变化不大的话, 也是可以的. google有个算法就可以做到,这里就不深入讲解了.

既然这样, 我们取一个相当大的取模因子即可, 比如一个很大的质数 10007.
然后定义一个区间来和机器关联上.

这样我们也可以得到一个key与机器的映射关系, 而且某个区间负载比较高了,我们调整这个区间与机器的关系即可.

现在我们再来看看删除机器与增加机器的影响.

增加机器时, 拆分某个区间, 拆除的新区间分给新机器. 只影响两个区间.
删除机器时, 直接把这个区间挂在其他机器下接口. 也是只影响两个区间.

静态路由唯一的缺点就是key与机器的关系是人工配置的, 维护成本高.

业务面临的问题

不管是一致性hash, 还是静态路由, 我们都是直接把key映射到机器上.
但是我这个业务比较特殊: 请求有N个key, 经过映射请求将会扩散N倍, 流量也会翻一倍, 很多其他操作也被放大N倍, 好恐怖.

背景中介绍了, 加上这个功能不能从根本上提高命中率, 所以命中率不变的, 这样再已扩散, 下层也撑不住了.
所以面临一个问题: 一个机器不能简单的当做一个节点了, 一个节点应该是一组机器, 然后我们需要固定的节点数, 即对机器分组.

这个时候就需要维护N个节点与机器的关系了, 成本好高, 但是面对扩散问题, 只好选择维护成本高的固定节点这个方案了.

容灾问题

讨论一致性hash和静态路由的时候一直在说发现机器故障时, 把机器摘除; 机器灰度后, 把机器加进来.
那么我们如何知道机器故障了呢? 又是如何知道机器恢复了呢?

其实这是一个很常见的容灾问题, 大部分公司应该都有非常成熟的容灾解决方案, 大概都是做一个下面这样的组件:

有一个探测程序, 将探测业务机器的状况, 并将探测的结果统一上报到决策服务.
决策服务根据探测结果判断某台机器是否可用, 然后将机器的判断结果下发到业务机器中.
当然, 决策服务也可以是探测服务, 也可能就在业务机器中, 我们暂时不考虑这些细节, 只需要关心大的功能点.

组件的大致架构大概如下:

这个组件可以理解为服务与服务之间加的中间层, 用于解决服务间的耦合问题.
被调的服务挂了, 调用方无需感知的, 组件自动剔除故障机器; 机器恢复, 组件自动加入机器. 当然, 这样的组件实现方式和架构千差万别, 但是目的是一样的, 就是解决容灾问题: 机器挂了对业务无影响, IDC挂了对业务无影响, 当然稍微复杂的还会根据机器的负载和流量还自动调度.

这个一个组件自己短期内实现一个, 不容易保证高可用性, 所以自己的业务只能利用上已有的组件, 不能自己来实现这样的功能(即使实现了能够使用的阻力也很大吧).

有人可能会问:以前的服务你们是怎么容灾的.
答案是使用公司已经的负载均衡组件, 大家可以google tencent l5 了解组件细节.

我们在业务面临的问题中提到, 我们不能简单的建立key和机器的映射, 而需要建立key和分组节点的映射, 刚好我们每一个分组节点都可以单独来容灾. 可谓是分组和容灾完美结合了.

这个时候总体来看看我们的解决方案:

1. 对机器进行节点分组, 每个节点自身保证容灾问题.
2. 使用静态路由表对分组节点建立映射
3. 请求的key hash 取模后, 可以根据路由表找到分组节点

这样对现有业务的影响也不少:

1. 上了分布式功能(N节点), 每个节点只需要处理1/N的数据, 可以显著提高本地命中率, 减少远程cache的访问
2. 对于N节点系统来说, 请求被放大了N倍, 流量会增加N倍, CPU也会适当增加.
3. 由于总体命中率并没有提高, 但是请求扩散, 所以对下层的访问也会扩大N倍.
4. 由于节点内为了容灾, 往往会加入不同IDC的机器, 这样一个请求路由到多个节点后, 可能面临流量在不同IDC之间传输可能会增大服务平均延时的问题.

好吧, 短期内上线这个功能的弊大于利, 因为现在系统的瓶颈在CPU, 增加这个功能消耗更多的CPU了, 所以还是先增加个开关先关闭这个功能吧.