速率限制 (Rate Limit) 通过限制调用 API 的频率防止 API 过度使用，保护 API 免受意外或恶意的使用，在诸多业务场景中得到广泛应用。日前，又拍云系统开发工程师陈卓受邀在 Open Talk 公开课上作了题为《又拍云网关速率限制实践》的分享，详细解读当前常用的算法以及基于网关 nginx/openresty 的实现和配置细节。以下是直播分享内容整理，查看视频请点击阅读原文。
网关速率限制是一种防御服务性措施，公共服务需要借其保护自己免受过度使用，使用速率限制主要有三个好处：
提升用户体验：用户在使用公共服务时总会面临一些资源增强和共享的问题，例如 CPU，当一个用户不管是有意或无意地过度使用 API 时，势必会对其他的用户造成一些影响。
更加安全：我们的服务、CPU、内存其实都是有一定的限制，过度访问势必会影响到服务的稳定性。假如有四个服务，每个服务能承载 100 个请求，当其中一个服务超过 100 个请求时就可能会宕机，其它三个服务在接收到超过 100 个服务请求时，也会接着连续宕机，这会造成服务不可用。
减少开销：现在很多服务都是放到公有云上，内存、CPU 和流量都是有成本的，有一些按量计费，使用多少花多少钱，这种情况会产生一些不必要的开销。
RateLimit 的几种算法
首先介绍四种速率限制的算法，分别是漏桶（Leaky Bucket）、令牌桶（Token Bucket）、固定窗口（Fixed Windows）、滑动窗口（Sliding Windows），很多限制措施都是基于这些算法进行的。漏桶和令牌桶虽然直观理解看似不太一样，但是在底层实现中这两种算法非常相似，达到的效果差不多。固定窗口和滑动窗口属于另外一类，滑动窗口是基于固定窗口做的。
漏桶(Leaky Bucket)
如上图所示，用户请求都被放进桶里，当桶满了以后，请求会被拒绝掉。桶的底部有一个孔，请求会以一定的速率被放过，比如说现在是限制每分钟 10 个请求，意味着每隔 6 秒钟就会有一个请求通过。漏桶算法的特点在于其通过请求的速率是恒定的，可以将流量整形的非常均匀，即便同时有 100 个请求也不会一次性通过，而是按一定间隔慢慢放行，这对后端服务迎接突发流量非常友好。
令牌桶（Token Bucket）
令牌桶，顾名思义桶里放的是一些令牌，这些令牌会按一定的速率往桶里放，假如每分钟限制 10 个请求，那么每分钟就往桶里放 10 个令牌，请求进来的时候需要先在令牌桶里拿令牌，拿到令牌则请求被放行，桶为空拿不到则意味着该请求被拒绝掉。
需要说明的是，令牌的个数是按一定的速率投放的，每分钟放 10 个令牌，那么能通过的请求肯定也是每分钟 10 个。假如匀速放令牌， 6 秒钟放一个令牌，结果和每分钟放 10 个令牌是一样的。
漏桶（Leaky Bucket）算法实现
由于令牌桶跟漏桶的实现效果差不多，这里主要细讲漏桶的算法和实现。先假设速率限制是每分钟 3 个请求，即每 20 秒钟放行一个请求。如图所示，假设第 10 秒进来第一个请求，因为之前一直都没有请求进入，所以该请求被允许通过。记录下近期一次的访问时间，即为本次请求通过时间点。
现在第 20 秒又过来一个请求，20 秒相对于 10 秒钟经过了 10 秒钟，按照计算只允许被通过 0.5 个请求，那请求就被拒绝掉了。这个 last 值还是保持近期一次一个请求通过的时间。第 30 秒又来了一个请求：如果将 30 秒看作是近期一次更新时间，相当于是 30 秒减 10 秒，也就是经过了 20 秒，而我们的限制是每 20 秒允许 1 个请求，那么这个请求会被放过去，last 值现在已经变成了 30 秒。
通过上述分析可以发现，漏桶限制非常严格，即便请求是第 29 秒进来也不能被通过，因为必须要经过 20 秒才允许通过一个请求，这可能会给业务带来一个问题：例如现在每分钟允许通过 3 个请求，用户可能需要在前 10 秒钟把三个请求发完，这种需求在这种算法下不会被允许。因为从发掉第一个请求到发第二个请求必须要间隔 20 秒才可以，为了弥补这种缺陷，需要引用另外一个参数 burst（爆发），允许突然爆发的请求。如下图中所示，40 秒距离 30 秒实际上只经过了 10 秒钟，按照之前的算法计算只被允许访问 0.5 个请求，实际上应该被拒绝掉，但是我们允许它提前多访问一个请求（burst 为1），算下来就是 0.5+1=1.5 个请求。
需要注意的是，虽然我们当前时间是 40 秒，但我们需要更新请求时间到 50 秒，这是因为现在已经超量使用进入到下一个时间段了，相当于是提前放行一个请求，然后一个 last 时间是 30 秒，应该加 20 秒到 50 秒。这也是该算法实现的一个特点，很多算法也都有 burst 的功能，即允许提前访问。
45 秒又来了一个请求，尽管这个请求来时，我们也允许它提前访问。但由于上一次最后访问时间已经是 50 秒了，而且在通过计算得出不到一个请求时，这一个请求也就被拒绝掉了，时间戳 last 还是 50 秒。
漏桶算法核心的地方在于我们在实现的时候保存最后一次的通过时间，新请求来的时候，用当前的时候减去之前的时间，然后拿到可以允许通过的请求个数。如果能通过，就把最后一次请求时间改成当前的时间；不能通过，当前最后一次请求时间还是不变。如果我们要添加 burst 的功能，即提前允许它访问多少个请求的时候，last 时间可能不再是最后一次放过去的时间，而是相对于之前最后一次请求的时间，它增长了多少个请求的时间，而这个 last 时间可能会超过请求的时候，总的来看主要核心的变量就是 last 的时间戳和 burst。
漏桶/令牌桶算法开源库
漏桶跟令牌桶的开源库也是特别多，下列几个库非常经典，各个语言和各个包都有实现，再加上因为我从事的工作主要是对 lua 和 golang 比较熟悉，这里主要讲他们：
nginx
https://www.nginx.com/blog/rate-limiting-nginx/
openresty/lua-resty-limit-traffic (两个变量)
https://github.com/openresty/lua-resty-limit-traffic/blob/master/lib/resty/limit/req.lua
uber-go/ratelimit
https://github.com/uber-go/ratelimit
Nginx 使用漏桶实现的，这个大家有兴趣去看一看，我们稍后会讲 Nginx 如何配置限制。Openresty 是基于 Nginx 之上使用 lua 编写模块的一个框架，它的实现里主要有两个参数，第一个参数是刚刚说的 rate，即每秒允许多少个请求；另一个参数是 burst ，指的是允许提前范围多少个，比如说每秒钟允许请求 5 个，这里还可以允许它提前放过去 5 个请求。
Uber 是 Uber 公司内部用 go 语言实现的一个 rate 限制。与前面 lua 代码不加锁不同的是，这个算法加了一个自选锁。我认为在高并发场景中，自选锁是一个挺好的选择，因为这会有一个 get 和 set 的操作，为了保证准确肯定要加锁，大家也可以去看看。
Nginx 配置
Nginx 配置中先考虑限制维度。例如每个用户每分钟只被允许访问两次就是按照用户纬度来限制，或者按照 ip 和 host 来限制，还有就是按照一个 Server，比如一个 Sever 能承载每秒钟 10000 个，超过 10000 个可能要被弹掉了。
以上提到的这些限制维度在 Nginx 里都能实现，实现方式主要依赖于 Nginx 的两个模块：ngx_http_limit_req_module 和 ngx_http_limit_conn_module ，即限制请求数和限制连接数。
固定窗口（Fixed Windows）
固定窗口是比较好理解的一个算法，应用在分布式限制场景中非常容易实现，因为它不需要加锁。
如图是一个时间戳的窗口，我们现在规定每分钟 50 个请求。30 秒来了第 1 个请求，40 秒的时候来了 49 个请求，现在一分钟的时候来了 50 个请求，由于已经达到每秒 50 个限制，当 50 秒再来一个请求时会被直接弹掉。等到下一分钟时，即便一下子来了 50 个请求也会被放过，因为它已经到了下一分钟了。
通过分析，大家能看到固定窗口算法是真的非常简单，你的程序只需要存储着当前时间窗口内已经有了多少个请求。至于不加锁，则是因为我们直接原子操作增加变量，增加完了以后需要注意有没有超过 50，超过 50，请求被拒绝；没有超过 50，请求会被接收，所以这里不会出现 get 跟 set 的情况。
当然这个也有一个弊端，如上图所示的 00:30 到 01:30 ，也算是一个 60 秒的时间范围，但它有 100 个请求了，和我们限制的要求是不一样的，会出现流量高峰的问题。因而这种算法只能保证在一个固定窗口请求不会超过 50 个，如果是随机一个非固定窗口之内，它的请求就很有可能超过 50 个，针对这种情况又提出了滑动窗口的概念。
滑动窗口（Sliding Windows）
如图所示，每分钟有 50 个请求，滑动窗口的一分钟指的的是当前时间往前的一分钟有多少个请求，例如 01:15 之前相当于从 0:15 到 01:15 。
已知 01:00 到 01:15 有 18 个请求，但 00:15 到 01:00 这个时间段是多少个请求呢？我们现在知道的是 00:00 到 01:00 是有 42 个请求，而滑动窗口算法的特点在于按比例。可以将这一分钟分成两段时间，前 15 秒和 后 45 秒，它按这个比例计算 00:15 到 01:00 大约有多少个请求。按比例算不是很精准，因为它只记录了总数。通过计算
rate=42*((60-15)/60)+18=42 * 0.75 + 18=49.5 requests
算下来是 49.5 个请求，当前这个请求应该是被拒绝掉的。
通过上述操作可以发现滑动窗口通过比例来保证每个分钟内通过值和限制值相近。当然这种不准的情况可以通过减小窗口时间改进，例如现在窗口是 1 分钟，你可以减小到 10 秒钟，这样发生错误的概率就会降低，不过减小到 10 秒窗口带来的额外存储成本就会很高。虽然这个算法有一些缺点，但是也有不少的公司在用。
滑动窗口（Sliding Windows）是否准确的问题
Cloudflare 对来自 270000 个不同来源的 4 亿个请求的分析显示：
0.003% 的请求被错误地允许或限制了速率
实际利率与近似利率之间的平均差异为 6%
尽管产生了略高于阈值的流量(误报)，实际发生率比阈值率高出不到 15%
很多大公司也在使用滑动窗口算法，如果你的限制每分钟 50 个，你能容忍它每分钟 40 个或者 60个的话，这种算法方案也是可行的。
固定窗口/滑动窗口应用
刚刚我们已经讲到了滑动窗口限制算法不需要加锁，使用原子操作即可，所以实现也非常简单。
openresty/lua-resty-limit-traffic (atomic原子操作)
https://github.com/openresty/lua-resty-limit-traffic/blob/master/lib/resty/limit/count.lua
只有 100 的代码，这里用了一个 increment 的原子操作，不需要加锁，对多线程、多进程的实现比较友好，开销非常少。
kong
https://github.com/Kong/kong/tree/master/kong/plugins/rate-limiting
这是 Kong 实现的滑动窗口应用，不过代码比较多，大家有兴趣的看看，同样是 lua 的代码，这个滑动窗口的实现比较全。
分布式 Rate Limit
很多时候网关可能不止一台，有两台机器的时候就要执行同步操作，例如在漏桶算法中要同步 last 值。同步的策略可以使用 DB 库。不过 DB 库同步适合请求量比较小的场景。面对请求量特别大的时候，可以使用 redis 这种高速的内存库，同步比较快。当然以上两种都是限制比较精准的时候可以使用，如果不是特别精准，只需要防止服务不被冲垮，我觉得可以使用 local 限制。
local 的限制是什么呢？我们刚刚提到每分钟限制 50 个请求，如果你有两个 Node，可以平均分配每个 Node 25 个，这个方案是可行的。如果有权重是 10% 的流量往一边走，90% 的流量往另一边走，可以相对调大其中一个 Node 的权重，改成一个 Node 每分钟限制 45 个，另一个每分钟限制 5 个，这样可以避免再接入一些 DB 的中间件。
面对这种分布式的业务场景，APISIX 实现的还不错 （https://github.com/apache/incubator-apisix/blob/master/apisix/plugins/limit-count/limit-count-redis.lua），它是基于 openresty 做的一个库，直接使用了 redis 作为同步，通过固定窗口方法实现。另一个不错的是goredis（https://github.com/rwz/redis-gcra/blob/master/vendor/perform_gcra_ratelimit.lua），基于 golang 的库实现了漏桶算法。goredis 的成本稍微高一些，如果是分布式的话，用固定窗口和滑动窗口的成本会低很多。
分布式 Rate Limit 性能优化
前面提到每个请求过来时都要读取 redis 或者是 DB 类的数据，例如固定窗口读取 count 值，去redis 把 count 减 1 会增加延迟，这种情况下就带来一些多余的开销。为解决此问题，一些开源的企业级方案推崇不实时同步数值的做法。假如现在每分钟有两个请求，Node1 接到一个请求时，并不是马上执行去 redis 执行 last 减 1 的操作，而是等待一段时间，例如 1 秒钟同步一次，然后同步到 redis ，这样就减少了同步的次数。
但是这种操作也会带来一个新的问题。假如现在的限制是每秒允许 2 两个请求，Node1 和 Node2 在一秒内同时来了两个请求，因为还没有到一秒，只是在本地计数，所以这 4 个请求被放过。当到了 1 秒的时候，去 redis 减值的时候，才会发现已经有 4 个请求被放过。不过这种可以通过限制它下一秒一个请求都不能被通过来补偿。
当然这种情况要看你的容忍程度，这也算是一种解决方案，不过这种解决方案实现的还是比较少。Kong 算其中一个，它是基于 openresty 开发的一个网关产品，实现了我们讲的定时同步，不需要实时同步 count 值的功能。还有一个是 Cloudflare，也是用滑动窗口去解决性能的问题，不过它没有开源。
总结
漏桶跟令牌桶非常经典，大家可以找到自己熟悉的语言算法实现，限制比较准确。
固定窗口实现更简单，无锁，适于分布式，但是会有流量高峰的问题。在一些限制不需要那么平滑的的场景中可以使用，限制相对准确。
滑动窗口实现简单，也适用于分布式，且不会有高峰流量的问题，但是限制会有偏差，如果要使用需要容忍限制偏差的问题。
以上是陈卓在又拍云 Open Talk 公开课上的主要分享内容，演讲视频和 PPT 详见下方链接：
