速率限制策略¶
如何选择策略¶
-
固定窗口（Fixed Window）： 当内存使用率低和高性能至关重要，且偶尔的突发流量可以接受或可以通过额外的细粒度限制来缓解时使用。
-
移动窗口（Moving Window）： 当需要精确的速率限制且额外的内存开销可以接受时使用。
-
滑动窗口计数器（Sliding Window Counter）： 当需要在内存效率和准确性之间取得平衡时使用。该策略以比完整移动窗口更少的开销平滑时间周期之间的过渡，尽管在桶边界附近可能会牺牲一些精度。
固定窗口（Fixed Window）¶
该策略是最内存高效的，因为它对每个资源和速率限制使用单个计数器。当第一个请求到达时，会启动一个固定时长的窗口（例如，对于每分钟10个请求的速率限制，窗口从第一个请求开始60秒后过期）。该窗口内的所有请求都会增加计数器，当窗口过期时，计数器重置。
绕过速率限制的突发流量可能出现在窗口边界处。
例如，对于每分钟10个请求的速率限制：
- 在 00:00:45，第一个请求到达，启动从 00:00:45 到 00:01:45 的窗口。
- 在 00:00:45 和 00:01:45 之间的所有请求都计入限制。
- 如果在该窗口内的任何时间发生10个请求，则在 00:01:45 之前的任何进一步请求都会被拒绝。
- 在 00:01:45，计数器重置，新窗口开始，允许10个请求直到 00:02:45。
Tip
为了减轻突发性（例如，窗口边缘的许多请求），将大窗口的限制与更细粒度的限制结合起来（例如，将每秒2个请求的限制与每分钟10个请求的限制结合起来）。
移动窗口（Moving Window）¶
该策略将每个请求的时间戳添加到日志中，如果第n个最旧的条目（其中n是限制）不存在或比窗口的时长更旧（例如，对于每分钟10个请求的速率限制，如果条目少于10个或第10个最旧的条目至少60秒旧）。在向日志添加新条目时，"过期"的条目会被截断。
例如，对于每分钟10个请求的速率限制：
- 在 00:00:10，客户端发送1个请求，被允许。
- 在 00:00:20，客户端发送2个请求，被允许。
- 在 00:00:30，客户端发送4个请求，被允许。
- 在 00:00:50，客户端发送3个请求，被允许（总计=10）。
- 在 00:01:11，客户端发送1个请求。策略检查第10个最旧条目的时间戳（00:00:10），该时间戳现在已61秒旧，因此已过期。请求被允许。
- 在 00:01:12，客户端发送1个请求。第10个最旧条目的时间戳是 00:00:20，该时间戳只有52秒旧。请求被拒绝。
滑动窗口计数器（Sliding Window Counter）¶
在版本4.1中添加。
该策略通过维护两个计数器来近似移动窗口，同时使用更少的内存：
- 当前桶（Current bucket）： 计算正在进行的时间段内的请求。
- 前一个桶（Previous bucket）： 计算紧接前一个时间段的请求。
基于当前桶中经过的时间计算这些计数器的加权和。加权计数定义为：
权重因子 \(w\) 计算如下：
其中：
- \(T_{\text{exp}}\) 是桶的持续时间。
- \(T_{\text{elapsed}}\) 是自桶切换以来经过的时间。
- \(C_{\text{prev}}\) 是前一个桶的计数。
- \(C_{\text{current}}\) 是当前桶的计数。
例如，对于 每分钟100个请求 的速率限制
假设：
- 当前桶有80次命中（\(C_{\text{current}}\)）
-
前一个桶有40次命中（\(C_{\text{prev}}\)）
-
如果桶在30秒前切换（\(T_{\text{elapsed}} = 30\)）。
由于有效计数等于限制，新请求被拒绝。
- 如果桶在40秒前切换（\(T_{\text{elapsed}} = 40\)）。
由于有效计数低于限制，新请求被允许。
Note
一些存储实现使用固定的桶边界（例如，将桶与时钟间隔对齐），而其他实现则基于第一次命中动态调整桶。这种差异可能允许攻击者在初始采样期间绕过限制。受影响的实现是 memcached 和 in-memory。