OPED 是 (我自己发起的) One Paper Each Day 挑战, 即每天读一篇 Paper, 领域不限.

这是 OPED 挑战的第四篇, 论文为 The Tail at Scale

这篇论文是由大神 Jeff Dean 写的. Jeff Dean 这尊大神想必不用我多介绍了, Google 三架马车有两篇是他写的. 之前在 Google 工作的时候也有幸能拜读他在内网的一些工作和回复. 网上有很多他的传说, 这里摘抄一句, 你们感受一下:

Jeff Dean wrote an O(n^2) algorithm once. It was for the Traveling Salesman Problem.

TSP, a.k.a Traveling Salesman Problem, 中文翻译为旅行商问题, NP-Complete, 感受一下.

Tail Latency

一个(直接或间接)面向用户的服务, 保证它的低延迟对于用户体验来说很重要. 这就和打游戏一样, ping 要是太高, 对方走到你脸上, 你的视野里可能还没看到对手. 那么我们怎么衡量一个服务的延迟呢? 对于一个略有经验的开发者来说, 他会很熟悉 Tail Latency, 95-Percentile Latency 这些名词. 它们描述了一个服务处理的所有请求中, 最慢的那一部分最少需要多久才能处理完成. 比如说, 一个服务, 对于大部分请求, 它可以在 10ms 内完成. 但是由于各种原因, 可能有 5% 的请求, 它耗费了 50ms 以上. 我们就会说它的 95-Percentile 延迟在 50ms 以上.

导致 Tail Latency 的原因

这个可能的原因实在是太多了, 比如说网络抖动; 比如这个服务运行在容器内, 但是宿主机上其他的进程突然占用了大量资源; 再比如一个 GC 语言 (e.g. Java) 编写的服务发生了 GC. 这些”不可控”因素, 我们暂且称它们为变数 (Variability). 上面说的这些, 都是单个组件的变数, 但是一个成熟的业务, 往往是由多个服务构成的. 很多面向终端用户的服务, 可能依赖了多个其他的内部服务, 这些服务的变数会叠加在这个服务上并放大. 如果你有一些概率论知识, 就可以很容易理解这一点. 比如一个服务 A 会调用某个服务 B 十次, 假设服务 B 的延迟超过 20ms 的概率是 p, 那么一次服务 A 的调用触发至少一次 tail latency 的概率就是 1 - (1-p)10. 如果 p = 0.01 的话, 那这个概率就是 0.65. 是不是很可怕.

如果缓解 Tail Latency

既然导致 Tail Latency 的原因时由于变数的存在, 我们只要减少甚至避免变数就好了. 虽然事情没有那么简单, 但是我们确实有一些可以减少变数的方法, 比如:

  1. 减少资源共享
  2. 规划后台任务的启动时间 等等.

但是这些方法的成本都比较高, 并且易出错．比如对于一个初创公司来说, 为了减少成本, 机器都要用在刀刃上, 减少资源共享必然导致成本上升. 再比如有 GC 特性的语言编写的服务, 要避免 Full GC 是很困难的. 参与开发的人员众多, 一个小小的改动可能就会前功尽弃.

所以大部分情况下, 变数是很难避免的, 我们要学会与它共存.

唯一不变的是变化.

单个请求级别的优化

刚刚我们使用概率论分析了变数放大的问题, 一个简单的思路就是, 对于同一个请求, 我们使用不同的机器执行多次, 当一个返回的时候我们就返回, 这样, 用户感受到 tail latency 的概率就会大大降低. 但是这个就会带来新的问题:

  1. 对于服务器的压力.
  2. 请求可能不是幂等的.

第二个问题和具体的业务有关, 这里我们不做太多的探讨. 对于第一个问题, 这篇论文提供了几种缓解的方式

  1. Hedged Request: 先发送一个请求, 如果这个请求超过了 95% 延迟还没会返回, 我们就再发送一个一样的. 显然, 这种方法只会带来 5% 的额外压力, 但是效果拔群. Benchmark 显示, 如果在 10ms 没有相应之后再发送一个请求, 那么 1000 个请求的总的 99.9% 延迟从 1800ms 降低到了 74ms.
  2. Tied Request: 我们发现大部分变数的来源是服务器的请求队列排队时间带来的, 一旦从队列出来, 之后的处理延时相对比较稳定. 这个方法就是基于这种观察, 每次发送多个请求, 一旦一个请求出队列, 就 cancel 其他的请求.

服务和基础设施设计上的优化

这部分的优化更加的根本, 门槛也更高, 主要有以下三种

  1. 使用更小(但数量更多)的 parittion. 这样可以方便 parition 的重分配, 让 hot 的 paritition 分配到空闲的机器上, 并且重分配更加快速.
  2. 有了更小的 partition, 我们可以用很小的开销对于 hot 的 partition 做更多的 replication. 这样可以方便 parition 的重分配, 让 hot 的 paritition 分配到空闲的机器上, 并且重分配更加快速.
  3. 如果我们发现某个 replica 的延迟特别高, 我们暂时禁用它知道它恢复.