Rate Limiting
Table of Contents
1. 定义
In computer networks, rate limiting is used to control the rate of requests sent or received by a network interface controller. It can be used to prevent DoS attacks and limit web scraping.
rate limiting，通常叫做“速率限制”，“流量限制”。用于控制到达服务端的请求量，避免出现爆发式的增长，导致服务不可用。把“异常” 的请求丢掉（比如 DDos 攻击，爆破登录），“正常”的用户请求得到处理。另外，在“正常”流量也比较高的情况下，控制请求的速率（延迟）， 让服务端可以在自己的承受范围内把请求平滑的处理掉。
在哪里做限流？
一般会放在客户端，代理层（gateway/proxy），服务器三块。
- 客户端：在请求时做流量控制，这样实现最简单。但前提假设是认为这些都是“正常”的流量。 自己的服务一般不会用这种方法，第三方的 APIs，为了避免出现被 block，可以在调用时做限流；
- 代理层：比如入口（公司/集群） nginx；waf 也是常见的流量控制（从安全层面）器；当然更常见的是微服务网关，限流熔断基本是 微服务网关的标配。通常限流会放在代理层实现，好处是下游的服务们不需要关心限流的事情（否则每个服务都自己实现一遍成本太高）；
- 服务层：服务自身当然也可以实现限流，灵活性很高。但通常适用于与业务逻辑强相关的事情，通用的比如 IP，API 的限制放在代理层更好；
2. 限流算法
有 5 种限流算法，各有优劣势。
2.1. 令牌桶（Token bucket）
Rate limiting using the Token Bucket algorithm 这篇文章讲的比较清晰，我直接搬过来了。
Figure 1: image via https://dev.to/satrobit/rate-limiting-using-the-token-bucket-algorithm-3cjh
上图中包含一个桶，桶中放着令牌（token），令牌就是请求的运行资格。
- 上方以稳定的速率向桶中放入令牌
- 当有流量进入时，判断桶中是否有足够的令牌
- 如果有剩余令牌，流量通过，自动扣除
- 如果没有令牌，则把流量丢掉（注意：流量是否丢掉，还是阻塞等待新的令牌生成，视具体的业务场景而定）
2.2. 漏桶法（Leaky bucket）
Figure 2: image via https://betterprogramming.pub/4-rate-limit-algorithms-every-developer-should-know-7472cb482f48
想象有一个桶，桶中放着所有要处理的请求。水滴的速度用来控制请求什么时候被处理。
- 桶可以类比成一个 FIFO 的队列
- 新的流量进来之后，先入队
- 以固定的“流速”来控制出队
2.3. 固定窗口（Fixed Window）
Rate limiting using the Fixed Window algorithm 这篇文章讲的比较清晰，我直接搬过来了。
Figure 3: image via https://dev.to/satrobit/rate-limiting-using-the-fixed-window-algorithm-2hgm
固定窗口是指将时间改成固定宽度的段（比如 1 分钟），对每一段中的流量进行计数，超过 limit 则丢弃或者等待下一个时间段。
2.4. 滑动日志（Sliding log）
Figure 4: image via https://www.quinbay.com/blog/rate-limiter-implementation-sliding-log-algorithm
滑动日志将以日志的方式记录每一个请求的时间戳。通过历史的请求日志量来判断当前请求是否放行，超过阈值则丢弃。
2.5. 滑动窗口（Sliding Window）
Figure 5: image via https://dev.to/satrobit/rate-limiting-using-the-sliding-window-algorithm-5fjn
滑动窗口是固定窗口的一种改进，为了解决固定窗口在窗口边缘突发流量是无法检测的问题。
解决的思路是如果没到达当前窗口的结束，则按照差的比例，从前一个窗口的加权补充到当前窗口。讲起来有点绕，但其实很好理解。
如上图，假设一分钟消耗为 50，当前时间为 01:20 ，已经计数了 20 。
- 当前时间未到达
2:00占了当前 2 分钟窗口的20/60 = 1/3； - 从前一分钟补偿
2/3的时间，凑够 1 分钟。也就是50 * (2/3)； - 滑动窗口的总计数为
50 * (2/3) + 20结果是小于 50 的，所以放行。
3. 算法的开源实现
主要选取基于 go 的实现：
- 令牌桶：go 的官方标准库中 time 封装了一个 rate limiter，核心算法就是 token bucket
- 漏桶：uber 开源的 ratelimit
- 滑动窗口：https://github.com/RussellLuo/slidingwindow
- 固定窗口和滑动日志用的比较少，知名的开源实现也少
4. 我自己的实现
https://github.com/zhangjie2012/yo-ratelimit
分别实现了 token-bucket 和 sliding-window 两种算法。我的场景是需要针对单个 IP 或者用户请求进行限流，
所以额外加了一个 RateLimitPool 的实现。
5. 总评
- 漏桶的好处是任何时候流量都是非常均匀的，问题是无法处理流量不均匀或者突发（burst）情况（会被阻塞），特定场景才会使用；
- 令牌桶解决了漏桶无法处理突发流量的问题，能够处理上游的不均匀流量；
- 固定窗口在窗口边界的前后赶上流量高峰是没办法的检测到的，误差较大，所以一般不用于生产；
- 滑动日志解决了固定窗口的问题，当流量大时，缺点也很明显：无论是存储空间，还是计算成本都比较昂贵，一般也不会使用；
- 滑动窗口方法是固定窗口的改进，可以处理流量突发场景。
以上 5 种算法实现都不复杂，各有优劣。令牌桶和滑动窗口都可以处理流量不够均匀的情况，建议使用。不过这几种算法都是针对单机的实现，不适合分布式场景下。