在服务器流量波动的情况下，我们需要根据下游服务器容量、业务要求等等对系统进行策略性的保护。保护策略有很多种，包括：

限流（Rate limit）：限制系统输入输出以达到维持服务稳定的目的；
熔断（Circuit break）：在系统受到过多failing response的时候，拒绝系统输出；
减载（Load shedding）：在系统输入请求响应时间过长的时候，拒绝系统输入。

一旦系统处理速度小于系统每秒接收的请求数量（processing speed < QPS），内存队列中的请求将逐渐累积，当请求不断增加没有及时释放，系统会遇到延迟增高，阻塞，内存溢出等等问题。因此系统可以建立一种机制，在响应时间变长时拒绝接收请求防止系统过载。

Facebook 有一篇非常有名的paper ^[1]提供了集中策略来设计系统减载方案（loadshedding）。主要里用到的技术包含Control Delay（CoDel）和Adaptive LIFO。

Control Delay

一般来说服务器会有内存或者资源池数量的限制，并将没有来得及处理的请求放在缓冲区。一旦处理请求的速度跟不上到来的请求，队列将会越来越大并且最终超过使用闲置。Facebook根据CoDel的启发设计了一套算法：

当内存缓冲队列在过去的N毫秒内没有被清空，则queue中请求的timeout则被设置为M毫秒（一般为10-30ms）；
(Optional) 当内存缓冲队列在过去的N毫秒内被清空，则queue中请求的timeout被设置成N毫秒。

伪代码如下：

def onNewRequest(req, queue):

  if (queue.lastEmptyTime() < (now - N seconds)) {
     timeout = M ms
  } else {
     timeout = N seconds;
  }
  queue.enqueue(req, timeout)

Adaptive LIFO

大部分系统处理请求遵循FIFO (First In Last Out) 原则。在峰值流量太大时，后来的请求可能会因为先来请求的阻塞而导致请求耗时更长。对此Facebook提出的方案是adaptive LIFO (Last In First Out) ，当系统出现队列请求积压的时候，将队列模式自动切换为LIFO，后到的请求首先执行，最大限度上增加了请求成功的可能性。

Adaptive LIFO与CoDel能够非常好的兼容，如下图所示。CoDel设置较短timeout，防止队列积压过多请求，adaptive LIFO将后入的请求率先处理，最大限度增加请求成功的概率。Facebook的PHP runtime virtual machine ^[2]以及thrift ^[3] framework都用到了这种算法。

Reference

[1] https://queue.acm.org/detail.cfm?id=2839461 “Fail at Scale”
[2] https://github.com/facebook/hhvm/blob/43c20856239cedf842b2560fd768038f52b501db/hphp/util/job-queue.h#L75 “A virtual machine for executing programs written in Hack”
[3] https://github.com/facebook/fbthrift “Facebook Thrift”