在评估离线应用的性能时，我们通常关心吞吐和平均延时。但在交互/在线应用中，延时长尾对用户体验同样有着非常大的影响。这些应用涉及的机器数越多，数据规模越大，延时长尾越严重，tail-tolerant越重要，就像fault-tolerant一样。
本文介绍了大型系统中常见的几种产生延时长尾的因素，以及如何消除它们。这些方法通常可以借助已有技术，不会增加多少开销。
我在Tablestore做性能优化时，非常明显地感觉到了延时长尾对整体性能/用户体验的影响。这篇文章主要讲的是如何解决准交互（亚秒级）分析的延时长尾，但并没有太多涉及我最关心的Batch写入长尾问题。无论如何，这篇文章都很有意义。
为什么存在抖动
可能的因素：
- 不同应用会去争抢相同机器的CPU/缓存/内存带宽/网络带宽等资源，相同应用的请求间也会有争抢。
- daemon进程通常资源受限，容易被影响。
- 不同应用也会争抢网关/分布式文件系统等全局资源。
- 一些背景活动（如分布式文件系统的数据重建/BigTable等系统中的compaction/语言runtime的gc等）也会造成周期性的延时尖峰。
- 各种地方的排队。
以及一些硬件因素：
- 功率限制，CPU只能短暂高于其功率限制运行，可能会对长时间运行的任务限流以降低功耗。
- SSD的GC会导致一次写操作的延时达到正常的100倍。
- 节能模式的开关也会导致延时上升。
通过冗余可以减少抖动，但很难彻底消除抖动，重要的是如何做好顶层设计，单一底层模块的抖动尽量少地传播到上层。尽管如此，知道造成抖动的因素，也有助于我们在设计系统时有意识地规避这些因素，如：使用什么语言、是否允许混部（不一定是可选的）、如何做负载均衡等。从这个角度讲，C++是很好的语言，无GC，可精准控制资源使用等，理论上C++实现的系统的抖动会更小，但实际工程中我们往往用不好。
组件级别的抖动随规模增大而放大
大规模在线应用一种常见的降延时的做法是把一个大请求分成若干个小请求分发给多台机器并行执行，再汇总一起返回给用户。它引起的问题是，我们需要等所有子请求返回，而子请求越多，抖动的影响越大。
想像每个子请求正常延时为10ms，但有1%的请求达到1秒。如果只有一个子请求，只有1%的请求延时达到1s；如果同时有100个子请求，整个请求的延时会受到最慢的子请求制约，有63%（1 - 0.99^100）的请求会达到1s。
我之前遇到的就是这个问题，一个Batch请求涉及了100个分区，平均延时就居高不下。当时的解决方案有三种：
- 增加数据聚合度，即减少子请求数量，从而降低抖动的放大，但这么做要么容易产生热点（数据分布不均匀），要么用户难以实现（一张表有非常多分区时，用户本身很难保证数据足够聚合）。
- 降低组件级别的抖动，可行，但说起来容易做起来难，我在这方面做了一些组件内部的工作，但不太彻底。
- 放弃实时响应，因此不需要考虑平均延时。这个方案就是要改变产品形态了，理论上很有诱惑，实际上用户不太可能认可（比如用户很难能知道哪些数据写入失败）。
降低组件的抖动
通过以下手段保证组件及时响应：
- 区分不同服务类别，尽量在上层服务中排队。区分服务类别是为了让在线请求优先于离线请求调度。下层服务保持短的队列能让上层策略更快生效。如分布式文件系统中尽量不要让请求在OS的队列中排队，而是在应用的队列中排队。
越下层的服务，知道的用户细节越少，越难针对性服务。排队和调度是非常依赖上下文的，因此尽量往上移。
- 减少队首阻塞。把长请求拆成多个短请求依次入队，与其它短请求交替执行，避免一个长请求阻塞一大堆。
牺牲个别长请求来保证占大多数的短请求的执行时间。如果长请求本身可以接受部分结果，则它自己也能保证响应时间。另外，令队列中的每个任务有着差不多的执行时间，可以显著降低调度的复杂度，效率更高（个人经验）。
- 管理背景活动，使用同步中断。对于背景活动：合并重复活动、限流、拆分长任务、低负载时执行。有些高扇出的系统如果在机器间同步背景活动（相同时间执行），可能要比异步（机器独立执行）更好，因为同步执行只会影响这个时间窗口的请求，而异步执行下，每时每刻都可能有机器在执行背景任务，会影响更多请求。
这里没讨论cache，因为它通常不直接影响延时长尾。
适应抖动
抖动不可能完全消除掉，总有开发者没办法控制的共享资源引入抖动。更重要的是适应抖动。这里讨论两类方法，一类是请求内的，几十ms内就生效的，一类是跨请求的，几十秒以上才生效的。
请求内的短时适应方法
很多web服务将数据保存为多个replica，读远多于写，且对一致性要求不高。比如拼写纠正服务。此时我们可以利用分布式文件系统中每个replica都可读的特性来降低单个请求的抖动。
对冲请求（Hedged requests）
向多个replica发送相同的请求，返回最快的那个。client先往最佳的replica发送请求，等一段时间没响应的话再给第二个发请求，其中一个响应后，client再给另一个replica发送cancel请求。等待时间合理的话对冲开销不会太大。比如我们可以把等待时间设定为期望的95%延时，这样只会有5%的额外请求。
这种方法的前提是延时的抖动通常与请求本身无关，而是来源于其它因素。
Google的一个例子是BigTable中查询100个server，等待10ms后发送第二个请求，只多了2%的请求，就将99.9%延时从1800ms降到了74ms。如果将第二个请求标记为低优先级，则额外开销还能更低。
我们之前也用到了这种方法，但并没有量化标准（95%），而是拍脑袋决定的。风险是当整个集群有问题时，这种方法的额外请求会大大增加，导致问题恶化。
绑定请求（Tied requests）
Hedged requests有时太保守了，我们可以更激进一些。我们每次向多个replica发送相同请求，每个replica都知道彼此，先执行的replica会向其它replica发送cancel请求。
这种方法的前提是抖动的主要因素就是排队，一旦从队列出来，抖动率就大大降低了。
为了降低多个replica同时执行的概率，client发送请求间可以加一些随机delay（如1ms）。Google的例子是BigTable请求分布式文件系统，效果还不错。
变种
client在应用以上两种方法时，可以先探测replica的队列长度。有用，但用处有限：
- 探测和实际发送间队列长度会变。
- 受其它因素影响，很难通过队列长度来估计响应时间。
- client的探测本身可能产生热点。
另一种变种是第一个server自己在发现数据不在cache的时候把请求转发给另一个server，两个server同时执行，再加上cancel机制。
实际上除了多replica系统，其它的可以通过不同机器执行相同请求的系统也可以应用上述方法。如很多带编码的系统，我们可以先请求原始数据，超过一定时间后再通过其它数据计算得到结果。
跨请求的长时适应方法
这些方法主要用于降低因更粗粒度现象导致的抖动（如负载不均衡）。对于分partition的系统，静态partition分布很难满足实际需求：
- 底层机器的性能既不均衡，也不稳定。
- partition可能有热点。
涉及到负载均衡了，我在2017年到2018年之间做了点这方面的事情。在线系统的负载均衡是很难做的，尤其是均衡动作本身对系统也会产生影响。决策速度与采集时间窗口大小似乎是矛盾的。
微型partition
每台机器服务多个partition，这样调度粒度更精细，均衡时间更短，机器故障的恢复速度也更快。
但partition分得越细，前面说的组件抖动的放大效应越强，同时用户操作受到的限制也可能越大（partition内的操作要比partition间的操作更丰富）。
有选择的replication
检测甚至预测产生不均衡的数据，并对这些数据创建额外的replica。这样不需要移动partition就可以分散压力（每个replica都可以承担部分压力）。Google的search就会对热的doc创建额外replica，还会在partition划分时有侧重。
延时引发的缓刑
一些抖动是因为机器的临时问题，中间的server可以把慢机器放到缓刑列表中，暂时将其踢出去。等机器延时降下来了，再将其从列表中移除。
大型信息检索系统
这类系统中及时返回足够好的结果，要比返回最好的结果，但慢，更重要。有两种技术：
- 足够好。不要等所有子请求返回，只要已经返回的子请求包含了足够好的结果，就返回给用户。某一台server上存在最好结果的可能性是非常低的。我们还可以把最重要的数据分布到多台server上。更general的说法是，不重要的响应慢的子系统都是可以跳过的。
- 金丝雀请求（Canary requests）。高扇出系统的另一个问题是，一个请求会发给非常多的机器，如果这个请求触发了bug，可能同时非常多的机器都会受影响。因此我们可以先把请求发给一两台server，没问题了再发给其它所有机器。canary阶段通常时间可控，因为涉及的机器少，抖动也小。
修改操作
上述技术主要针对不进行关键修改的操作。通常涉及修改的操作抖动更好控制，因为这样的操作不会涉及非常多的机器。另外很多修改操作不在用户请求的主路径上，很多系统也被设计为可容忍不一致的状态。对于需要一致状态的系统，我们通常会使用基于quorum的算法（如Paxos），这些算法只需要多数成功，本身就能容忍延时长尾。
硬件趋势与效应
更激进的功率优化，工艺导致的设备间差异，会使未来硬件产生更高的抖动。再加上机器规模的扩大，使得软件层面的tail-tolerate更为重要。幸运的是一些硬件趋势会提升这些tolerate技术的效果。如更高的双向网络带宽，更低的消息延时（如RDMA）。
结论
以上这些技术有个好处，就是可以不需要那么多冗余资源就能保证尾延时可控，这样我们可以显著提升系统使用率，降低成本，而不用牺牲响应速度。
这些技术中很多都可以封装为库，不同应用不需要重复实现。同时这些技术也能令上层应用的设计更简单。