已發布·持續改進
速率限制 指南 · 4/6
本章目前僅提供英文版。
A rate limiter runs in front of every request, so the cost of one decision and the memory each key consumes translate directly into the cost of running your service. This chapter compares the five algorithms on time, space, accuracy and burst behavior. Below, L is the limit per window and K is the number of active keys.
O(1).O(1), although a single call may drop up to O(L) entries. Implemented with a Redis sorted set, adds and range deletes cost O(log n).O(1).O(1).O(1).| Algorithm | State per key | Space |
|---|---|---|
| Fixed window | window number, counter | O(1) |
| Sliding window log | timestamps of accepted requests | O(L) |
| Sliding window counter | window number, two counters | O(1) |
| Token bucket | token count, last update time | O(1) |
| Leaky bucket | queue of waiting requests | O(queue size) |
Multiply by K for the total. With a limit of 10,000 per hour and 100,000 active users, a sliding log may have to hold a billion timestamps in the worst case, while token buckets need just 200,000 numbers. That gap is why large services rarely use the log approach.
def worst_case_bytes(keys: int, limit: int, bytes_per_number: int = 8) -> dict[str, int]:
return {
"fixed_window": keys * 2 * bytes_per_number,
"sliding_log": keys * limit * bytes_per_number,
"sliding_counter": keys * 3 * bytes_per_number,
"token_bucket": keys * 2 * bytes_per_number,
}
for name, size in worst_case_bytes(keys=100_000, limit=10_000).items():
print(f"{name:16} {size / 2**20:10.1f} MiB")
# sliding_log needs about 7,629 MiB; the others need a few MiBReal usage is higher because of language and storage overhead, but the orders of magnitude hold.
| Algorithm |
|---|
| Most admitted in any window-length span |
|---|
| Burst |
|---|
| Character |
|---|
| Fixed window | up to 2L (at a boundary) | up to L at each window start | simplest |
| Sliding window log | exactly L | up to L | exact but heavy |
| Sliding window counter | about L (approximate) | around L | light and practical |
| Token bucket | capacity + rate × T over a span T | up to capacity | average rate plus bursts |
| Leaky bucket (queue) | rate × T (output side) | absorbed by the queue, output stays even | adds waiting time |
The token bucket bound is a simple formula: starting from a full bucket, at most capacity + rate × T requests pass during a span of length T. That is why it is configured with two numbers, such as "10 per second on average, bursts of up to 20".
def max_admitted(rate: float, capacity: float, seconds: float) -> int:
# Most requests that can pass in `seconds`, starting from a full bucket
return int(capacity + rate * seconds)
print(max_admitted(rate=10, capacity=20, seconds=1)) # 30
print(max_admitted(rate=10, capacity=20, seconds=60)) # 620This snippet sends requests just before and just after a boundary and counts how many each approach admits.
from collections import deque
def fixed_window(times, limit, window):
counts = {}
ok = 0
for t in times:
w = int(t // window)
counts[w] = counts.get(w, 0) + 1
ok += counts[w] <= limit
return ok
def sliding_log(times, limit, window):
log, ok = deque(), 0
for t in times:
while log and log[0] <= t - window:
log.popleft()
if len(log) < limit:
log.append(t)
ok += 1
return ok
burst = [59.5] * 5 + [60.5] * 5 # five on each side of the boundary
print(fixed_window(burst, 5, 60)) # 10
print(sliding_log(burst, 5, 60)) # 5When several servers share one limit, every decision needs a round trip to a shared store such as Redis. At that point the network round trip, typically hundreds of microseconds to a few milliseconds, dominates the algorithm's O(1). Bundling several commands into one Lua script keeps it to a single round trip. At very high volume, some systems keep a local bucket on each server and only sync with the shared store periodically, trading a little accuracy for lower latency.
O(1) in time and in space per key.O(L) memory per key, which hurts at scale.capacity + rate × T requests over a span T.
0 則留言
登入 · 登入後即可留言。
來留下第一則留言吧。