api网关安全与限流算法

Nginx限速模块初探 这篇文章解析得很清晰了。
记录一下几个关键点：

nginx使用的是漏桶算法

核心的代码是这一行

excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000; 

以固定的速率（ctx->rate）处理请求

nginx的限流统计是基于滑动窗口吗

答案：不是
nginx以固定速率处理请求，不管是怎样配置限速，它都是转换为多少毫秒取一个请求来处理。什么意思呢？举例：

limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;

配置了一秒钟2个请求，那就是每500ms处理一个请求。
也可以以分钟为单位配置，nginx官网文档提到，如果一秒内的请求少于一个，可以以分钟为单位配置：

The rate is specified in requests per second (r/s). If a rate of less than one request per second is desired, it is specified in request per minute (r/m). For example, half-request per second is 30r/m.

配置了30r/m，那就是30r/60000ms，每隔2000ms 处理一个请求。
假如说配置了200r/m，会出现跨2分钟统计导致限流不准确的情况吗？例如:
0s---190r---60s---190r---120s
30s---210r---90s
从固定窗口来看，每一分钟都是190个请求，没有超限；但是从滑动窗口来看，从第30s到90s这一分钟是210个请求，会导致限流不准确吗？
答案是不会。
因为nginx会以每300ms一个请求的速率，去处理请求，那么在30s-90s这一分钟，一定不会超过200r/m，所以不会出现30s-90s处理了210个请求这种情况。

分布式限流如何做

通常的做法是redis+lua。基于Redis的限流系统的设计这篇文章的限流算法是基于令牌桶的方式，而且它采取的是触发式的方式往桶里放令牌。关键代码如下：

local reverse_permits = math.floor(((curr_mill_second - last_mill_second) / 1000) * rate)
local expect_curr_permits = reverse_permits + curr_permits;
local_curr_permits = math.min(expect_curr_permits, max_permits);

计算上一次请求令牌的时间，与本次的时间差，然后再乘以速率，来决定要加多少令牌。如果两次请求的时间比较久，就相当于一次性补充了多个令牌。最后一行代码表示不能超过最大令牌数。

滑动窗口的近似算法

滑动窗口，一般的做法是记录明细，包括时间，然后从当前时间开始，往前框好时间窗口，再统计。这种做法，占用存储空间比较大。
How we built rate limiting capable of scaling to millions of domains 这篇文章提出了一种近似的算法，思路非常简单、直观。按作者的说法，还非常有效：

image.png

rate = 42 * ((60-15)/60) + 18
     = 42 * 0.75 + 18
     = 49.5 requests

它的算法是基于这么一个假设：上一时间窗口（固定时间窗口，例如10点05分这一分钟）的访问量是均匀的。所以它是按比例取上一时间窗口的统计值。