速率限制算法：固定窗口与滑动窗口

在生产环境中，我们经常需要通过一定的办法方案来保护我们的系统（比如 API）免受无意的或恶意的过度使用。在极端情况下，我们还需要对系统进行适度的降级，以确保系统的可用性。速率限制（rate limit）有助于自动化该过程（有时候也会称为流量控制）。

这里我们主要介绍固定窗口计数算法和滑动窗口计数算法。

固定窗口 Fixed Window

固定窗口算法比较好理解，大致的概念如下：

  1. 时间被切分成固定大小的窗口，比如 60 秒或 5 分钟等；
  2. 每个时间窗口允许通过的请求阈值固定，假定为 N；
  3. 每一次请求进来，对当前时间窗口的计数器加 1， 假设为 n；
  4. 当当前时间窗口的请求计数超过阈值时（n>N），丢弃当前时间窗口进来的所有请求；

整体的理解可以参考下述图例 1（固定时间窗口 1 秒，每秒钟允许通过 3 个请求）：

image-20220328142057442

图 1. 固定窗口算法图例

看起来好像没有什么毛病，在允许的时间窗口内只允许通过预设的请求。为什么还会需要滑动窗口算法，我们看一下固定窗口算法的问题：

  1. 以上图为例，假定 14:00:02 秒的 3 个请求是在后 500ms 到达，14:00:03 分的 3 个请求是在前 500ms 到达，实际上一秒内可能通过了超过预设的 3 个请求，系统被击穿（参考下图 2）；
  2. 如果这是一个高并发系统，那么有可能存在大量请求等待时间窗口重置的情况，还是以上图为例，一切换新的时间窗口，系统可能马上在短时间内被击穿不可用（踩踏）；

图2

图 2. 固定窗口算法问题

滑动窗口 Sliding Window

为了解决固定窗口在时间窗口切换边界的流量尖峰问题，引入了滑动窗口计数算法。该算法在固定窗口的基础上，将固定窗口进行更细粒度的切分：

  1. 将时间划分为多个固定区间，如 200ms；
  2. 在每个区间内每有一次请求则计数加 1，并维持固定的时间窗口，如固定时间窗口为 1 秒，则占用 5 个时间区间；
  3. 每经过一个区间的时间，抛弃最早的区间，并纳入最新的时间区间；
  4. 如果当前时间窗口的请求数量超过了预设限制，则本时间窗口内的后续请求都会被丢弃；

基本算法通过下图 3 概要说明，可以直观发现滑动窗口计算方法可以有效避免窗口切换的边界流量尖峰及踩踏问题。并且在我们需要提高流控精度的时候，可以通过划分更细的时间区间来实现。

image-20220328154213560

图 3. 滑动窗口算法图例

注：算法可以进一步简化，假设当前时间窗口已经过去 25%，目前的请求数为CurrentN，上一次时间窗口共接受 PreN 次请求（权重为 100%-25%=75%），如果 (PreN * 0.75 + CurrentN) > 预设请求阈值 则丢弃本次请求，反之放行本次请求。

参考文档

  1. [How to Design a Scalable Rate Limiting Algorithm with Kong API

您可能还喜欢以下文章


关于我

热爱开源、分享。目前主要从事混合云、数据库 SaaS 等运维开发及相关团队管理工作。