限流器（rate limiter）用于控制网络流量，比如限制客户在一定时间内能够发起的请求数量，如果超过了该数量，那么接下来的请示都会被阻挡，以下是一些限流的需求示例：

  • 用户每秒最多只能发起两次请示
  • 每个IP一天最多只能创建10个用户
  • 每个设备每周最多只能奖励5次

限流的用处包括但不局限于：

  • 防止由拒绝服务攻击引起的资源耗尽
  • 降低成本
  • 防止服务器过载

Step 1 - 明确需求

沟通并确定设计需求，以下是一些可供讨论的点：

1. 哪端限流？客户端限流or服务端API限流？

2. 限流策略？基于IP限流 or 基于用户ID限流 or 其它？

3. 系统规模？

4. 分布式？

5. 限流器作为一个单独的服务还是集成到代码中？

6. 需要通知被限流的用户吗？


以下是一个需求示例：

1. 精确限制超额访问流量

2. 低延迟，不能降低HTTP响应速度

3. 尽可能少得使用内存

4. 分布式，可跨服务器提供限流服务

5. 异常处理，为限流用户提供异常报警

6. 高容错率，当限流器异常时，不能影响整个系统的使用

Step 2 - 概要设计

在哪里限流

1. 在客户端限流，一般不靠谱

2. 在服务端限流

3. 在中间件中限流，比如API网关

限流算法

令牌桶

维护一个固定容量的令牌桶，系统以稳定的速率向桶内添加令牌，当令牌数量超过容量时多余的令牌会被抛弃。

每次用户请求都会消耗一个令牌，当桶内没有令牌时，限流生效，用户请求被阻挡。

令牌桶算法依赖两个参数：

  • 桶容量
  • 重填速率

设计这两项参数需要根据实际情况来确定，比如下面是一些实际场景：

  1. 不同的API一般需要不同的限流速率，则每个API都需要一个令牌桶
  2. 如果根据IP地址进行限流，则每个IP地址都需要一个令牌桶
  3. 如果系统每秒最多只能访问10000次，则所有的请求需要共享一个令牌桶

优点：

  1. 算法简单
  2. 内存效率高
  3. 允许短时间内的突发访问

缺点：

  1. 桶容量和重填速率两项参数可能不容易调整到合适值

漏桶

所有的请求先存放在一个固定容量的漏桶里，系统以恒定的速率从漏桶里取出请求进行处理。如果漏桶满了，则后续的请求会被丢弃。

漏桶与令牌桶的区别是漏桶对请求的处理速率是固定的。

漏桶算法依赖两项参数：

  • 桶容量
  • 取出速率

优点：

  1. 内存效率高
  2. 可保证处理请求的速率是固定的，不会出现突发访问的情况

缺点：

  1. 不能处理突发访问的情况，出现突发访问时，旧的请求被积压，导致新的请求被丢弃
  2. 算法的两个参数不容易调到合适值

固定窗口计数器

将时间线划分成一个一个的固定窗口，在每个窗口内维护一个计数器，每次用户访问时计数器加一，到达阈值后新的访问被丢弃。

固定窗口计数器的预期目标是限制每个时间段内的流量，但如果流量峰值出现在时间段的开头和结尾处，则仍会出现时间段内的流量超时限定值的情况，如下：

上面的固定窗口是1分钟，流量上限是5，从2:00:00~2:01:00和2:01:00~2:02:00这两个时间段来看，流量都没有超出限定值，但是从2:00:30~2:01:30这个时间段来看，流量是10，超出了限定值。

优点：

  1. 内存效率高，容量理解
  2. 可以做到在每个时间窗结束时调整流量，这在某些场景下有用

缺点：

  • 峰值流量出现在时间窗的开始或结束位置时，实际流量超标

滑动窗口日志

用于解决固定窗口计数器中流量峰值出现在边缘位置时实际流量超标的问题，实际操作如下：

  1. 每次有请求到达时，记录该请求的时间戳。
  2. 当新的请求到达时，移除所有过时的时间戳，比如时间窗口是1分钟，则移除1分钟以前的请求。
  3. 记录新请求的时间戳。
  4. 判断记录的时间戳数量是否超过设定值，是则丢弃该请求。

优点：

  1. 流控精准，在任何时间窗口内，流量都不会超标

缺点：

  1. 内存消耗大，即使一个请求被丢弃，也要记录其时间戳

滑动窗口计数器

固定窗口计算器算法和滑动窗口日志算法的结合，以下面的流控举例：

假设每分钟允许的最大流量是7，前一分钟有5次请求，当前分钟有3次请求。在当前分钟的30%位置有新请求到来，那么当前窗口的请求数量按下面的公式计算：

当前窗口的请求数 + 前一个窗口的请求数 * 滑动窗口中前一个窗口的占比

按公式计算当前滑动窗口的请求数量是 3 + 5 * 70% = 6.5，根据实际情况可以向上或向下取整。以向下取整为例，滑动窗口有6个请求，所以新的请求会被接受。

优点：

  • 内存效率高
  • 有效抑制流量峰值，保证任意窗口内的流量都不会超标

缺点：

  • 非严格流控，存在误判概率，因为它假设了前一个窗口的流量是平均分布的。

概要设计

要点：

1. 使用内存缓存数据库Redis记录同一用户的请求次数，在中间件做流量控制。

2. 每次有请求到达时，从Redis中取出该用户的请求次数，判断是否超出限制。如果超出，则丢弃这次请求，否则将请求传递给API服务器，并且对Redis记录的请求次数加1。

Step 3 - 详细设计

流控规则

这里举两个示例：

domain: messaging
descriptors:
 - key: message_type
   Value: marketing
   rate_limit:
    unit: day
    requests_per_unit: 5

这个示例描述的是每天最多有5条推广消息。

domain: auth
descriptors:
 - key: auth_type
   Value: login
   rate_limit:
    unit: minute
    requests_per_unit: 5

这个示例描述的是每分钟最多登录5次。

受限请求处理

当请求被流控限制时，一般会在HTTP响应中回复代码429（too many requests）。根据实际场景，我们可以直接丢弃本次请求，或是先放入消息队列，等待后续处理。

可以在HTTP响应头中加入以下字段以通知客户端流控详情：

X-Ratelimit-Remaining: 当前窗口剩余的请求数
X-Ratelimit-Limit: 每个窗口允许的请求数
X-Ratelimit-Retry-After: 至下次请求合法时应等待的秒数

详细设计

重点：

  • 流控规则存储在磁盘上，工作集群定期从磁盘加载流控配置并存储在缓存中。
  • 客户的请求首先经过流控中间件。
  • 流控中间件从缓存中加载配置，并使用Redis来存储每个客户的访问计数，当请求到达时，从Redis中取出访问计数和时间戳，并判断是否对本次请求进行控制：
    • 如果本次请求不被流控，则转发给API服务器
    • 如果要执行流控，则返回429代码给客户端，并根据实际需求决定是否将本次请求丢弃或是缓存到消息队列以便后续处理

分布式流控

分布式环境下，主要要考虑两个问题：

  • 竞态条件
  • 同步问题

竞态条件

发生在读-判断-写回过程，两个独立的读-判断-写回语句可能发生重叠，导致最终结果不正确，如下：

互斥锁可以用于处理竞态条件，但是会显著降低性能，除此外还有两个常见的处理办法：Lua脚本和Redis排序集合。

同步问题

分布式环境下可能有不止一个流控服务器，当有多个流控服务器时如何进行数据同步是一个问题，一般可以使用一个集中的数据存储服务器来做同步，如下：

性能优化

  1. 使用多数据中心设计，用户请求被导向最近的服务器，以降低延时。
  2. 使用最终一致性模型进行数据同步。

状态监控

通过监控下面两项来优化限流器的运行效果：

  1. 流控算法的有效性
  2. 流控参数有有效性

如果流控太严格导致大量请求被限制，则可以适当放松流控规则。如果突发情况下流控失效，则需要调整流控算法，比如使用令牌桶算法。

Step 4 - 总结

流控算法：

  • 令牌桶
  • 漏桶
  • 固定窗计数器
  • 固定窗日志
  • 滑动窗计数器

硬控 vs 软控：

  • 硬控：严格控制流量不能超出限制
  • 软控：允许短时间流量超出限制

其他层的流控：

  • 基于IP地址进行流控，比如在OSI模型的第三层用iptables进行流控

客户端改良：

  • 使用客户端缓存
  • 指数回退，避免频繁发送API请求
  • 优雅处理被流控时客户端的响应