在服务器流量波动的情况下，我们需要根据下游服务器容量、业务要求等等对系统进行策略性的保护。保护策略有很多种，包括：
- 限流（Rate limit）：限制系统输入输出以达到维持服务稳定的目的；
- 熔断（Circuit break）：在系统收到过多failing response的时候，拒绝系统输出；
- 减载（Load shedding）：在系统输入请求响应时间过长的时候，拒绝系统输入。
一般来说，常见的限流算法有三种：滑动窗口（sliding window），漏桶（leaky bucket）以及令牌桶（token bucket）算法。
滑动窗口（Sliding Window）
滑动窗口算法比较简单粗暴。比方说我们需要100 qps的限流，我们将1s分为十个100ms的格子，格子之间通过链表（linkedlist）的方式连接。然后我们设置一个1s的窗口，每100ms在链表尾部新加一个格子，然后删掉队头的格子，保证1s的窗口内始终有十个格子。
每个格子内会记录到底的请求，请求到来的时候会首先查看当前1s内总访问量，如果超过100s则进入缓存等待或者丢弃，否则队尾格子进行计数。
滑动窗口算法的优势在于实现简单，内存友好。存在的问题是精度由格子的粒度决定。格子细粒度越高，窗口滑动越平滑，限流统计就越精确。
漏桶（Leaky Bucket）
漏桶算法[1]的核心逻辑为以下几点：
- 实现了一个固定容量的桶；
- 桶的输出速率保证恒定，一旦桶内请求为空则停止输出；
- 一旦桶溢出，则溢出流量会被丢弃。
漏桶的实现在单机上可以利用队列（queue）完成，分布式环境可以使用Redis或者其他消息中间件。
令牌桶（Token Bucket）
令牌桶[1]根据令牌的数量来控制请求速率。每秒钟会平均往桶内放n个令牌，每次请求到达会消耗掉桶内X个令牌，一旦桶内剩余令牌≤X则请求放入缓存区等待或者丢弃。
](/images/token_bucket.gif "Token Bucket 原理图")
令牌桶对于不同突发状况有比较好的处理能力，以Google的Java开源项目Guava[4]为例，针对RateLimiter提供了两个实用的子类：平滑突发限流（SmoothBusrty）和平滑预热限流（SmoothWarmingUp）。
SmoothBursty能够很好地应对突发流量。当流量突然变大的时候，会立刻消耗掉桶内令牌，之后流量输出取决于令牌自增速率，达到一个平缓的输出速率；当流量突然变小的时候，流量会立即消耗掉桶内令牌。输出流量会呈现一个逼近恒定速率的趋势，但是具体速率由实时系统流量和令牌自增速率共同动态决定。
SmoothWarmingUp适用于下游服务需要预热的场景。创建限流器的时候可以设定参数如下：
1 | // 令牌自增速率为2个/秒，缓冲时间为3s |
在这样的设置下，在前3s令牌不会每0.5s发放一次，而是会形成平缓线性下降的坡度。比方说1.5s发放第一个，0.9s发放第二个，0.6s发放第三个。在3s之后，发放速率会恢复设定的速率。
漏桶 vs 令牌桶
- 漏桶输出速率恒定，令牌桶输出速率由令牌自增速率与输入流量决定。增加令牌自增速率能够提高限流器上限。有突发流量（burst）时令牌桶输出速率可以动态提高
- 当漏桶满了之后，输入流量会被丢弃。当令牌桶满了之后，输入可以被缓存或者丢弃；
一般来说漏桶被用在traffic policing的场景中，即network需要满足某一个contract，一旦超过contract，traffic shaping就会拒绝多余的流量请求，保证传输带宽；令牌桶多用在rate limit的场景中，更加灵活和动态。Uber的批处理系统中对限流的处理就运用到了这种令牌桶的设计原理。
Reference
- [1] https://www.quora.com/What-is-the-difference-between-token-bucket-and-leaky-bucket-algorithms “What is the difference between token bucket and leaky bucket algorithms?”
- [2] https://www.figma.com/blog/an-alternative-approach-to-rate-limiting/ “An alternative approach to rate limiting”
- [3] https://mp.weixin.qq.com/s/b4yqLSqNz7_vcGLRmhG0rw “高并发系统中的限流应该如何做？”
- [4] https://github.com/google/guava “google/guava”
