关于又拍云:又拍云网关速率限制实践

速率限度 (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/ra…

• openresty/lua-resty-limit-traffic (两个变量)

https://github.com/openresty/…

• uber-go/ratelimit

https://github.com/uber-go/ra…

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/…

只有 100 的代码，这里用了一个 increment 的原子操作，不须要加锁，对多线程、多过程的实现比拟敌对，开销非常少。

• kong

https://github.com/Kong/kong/…

这是 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/inc…），它是基于 openresty 做的一个库，间接应用了 redis 作为同步，通过固定窗口办法实现。另一个不错的是 goredis（https://github.com/rwz/redis-…），基于 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 详见下方链接：

Open Talk 公开课

举荐浏览

企业如何高效安稳实现数据迁徙

三分钟理解 Python3 的异步 Web 框架 FastAPI