这是用户在 2024-5-27 13:54 为 https://smudge.ai/blog/ratelimit-algorithms 保存的双语快照页面，由 沉浸式翻译 提供双语支持。了解如何保存？

Visualizing algorithms for rate limiting
可视化速率限制算法

Why rate limit? 为什么要限制速率？

Imagine a Twitch chat with many active participants and just one spammer. Without rate limiting, the sole spammer can easily dominate the entire conversation. With rate limiting, each user has a fair chance to participate.
想象一下，在一场 Twitch 聊天中，有许多活跃参与者，但只有一个垃圾邮件发送者。如果没有速率限制，唯一的垃圾邮件发送者就可以轻松主导整个对话。通过速率限制，每个用户都有公平的参与机会。

cr4sh_b0t
200IQ play cr4sh_b0t200IQ 播放
primedriftking205
😱  prime 漂流王205😱
primeluckyducky7
I always learn so much from these streams
prime luckyducky7我总是从这些流中学到很多东西
pixelpirate
that's actually not that hard to do
Pixelpirate这实际上并不难做到
0xCookie
yeah.. 0xCookie 是的..
cr4sh_b0t
F
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
pixie_dust91
it happens. pixie_dust91它发生了。
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
moderatorqu1cksc0p3
I should probably get some sleep. peace!
moderator qu1cksc0p3我也许应该睡一会儿。和平！
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
primedriftking205
I guess so! never thought about that tbh
prime driftking205我想是的！从来没有想过这个问题
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
primeluckyducky7
gigachad
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
primeshadow_sn1per  prime shadow_sn1per
F
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
primetournado
❤️❤️❤️  prime 巡回赛❤️❤️❤️
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
pixie_dust91
wait just ban him?
pixie_dust91等等就禁止他吗？
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
turboMinWalker
absolute legend
turbo MinWalker绝对传奇
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
primeluckyducky7
🐐🐐🐐 goated 🐐🐐🐐
prime luckyducky7🐐🐐🐐山羊🐐🐐🐐
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
moderatorverifiedQuantumLeap42
💀💀💀
moderator verified QuantumLeap42💀💀💀
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
turboMinWalker
alright alright we deserved that one
turbo MinWalkeralright 好吧，我们应得的
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
primedriftking205
💀 CALLED OUT LMAO
prime driftking205💀喊出LMAO
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
sk8erboi22
lolololololol sk8erboi22lololololol 洛洛洛洛洛尔
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件 垃圾邮件
w4nderlust_x
GAMER MOMENT w4nderlust_xGAMER 时刻
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
0xCookie
kekw
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM SPAM SPAM
😈垃圾邮件发送者😈垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM
😈 垃圾邮件发送者 😈 垃圾邮件 垃圾邮件 垃圾邮件
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
😈 SPAMMER 😈
SPAM SPAM SPAM SPAM SPAM
Allowed requests:
101
Blocked requests: 0 被阻止的请求：0
😈 SPAMMER 😈 😈 垃圾邮件发送者 😈
you
pixie_dust91 小精灵_dust91
tournado 图尔纳多
qu1cksc0p3
luckyducky7 幸运鸭7
pixelpirate 像素海盗
cr4sh_b0t
fallenstar89 堕落之星89
w4nderlust_x
driftking205 漂流王205
QuantumLeap42 量子跃迁42
raidboss24 袭击老板24
shadow_sn1per 影子_sn1per
0xCookie
MinWalker 明沃克
sk8erboi22

A rate limiter lets you control the rate of traffic that your service processes by blocking requests that exceed a set limit during a period of time. This is useful beyond just throttling spam in a chat. For instance, rate limiting a login form can deter brute force attacks while still allowing a small burst of incorrect guesses.
速率限制器可让您通过阻止一段时间内超出设定限制的请求来控制服务处理的流量速率。这不仅仅限于限制聊天中的垃圾邮件。例如，限制登录表单的速率可以阻止暴力攻击，同时仍然允许少量的错误猜测。

API endpoints are also frequently rate-limited to prevent any single user from monopolizing resources. Imagine that you want users to only be able to hit an expensive endpoint 100 times per minute. You could track hits with a counter that resets every minute. Any request after the 100th within that minute gets blocked. This is one of the simplest rate-limiting algorithms, called a fixed window limiter, and is a common way to control traffic to a service.
API 端点也经常受到速率限制，以防止任何单个用户独占资源。想象一下，您希望用户每分钟只能访问昂贵的端点 100 次。您可以使用每分钟重置的计数器来跟踪点击次数。该分钟内第 100 个之后的任何请求都会被阻止。这是最简单的速率限制算法之一，称为固定窗口限制器，是控制服务流量的常用方法。

But it’s not always that simple.
但事情并不总是那么简单。

When does each one-minute window begin and end? If I begin a burst of requests near the end of a window, can I exceed the limit? Is a window’s capacity restored one request at a time, or all at once?
每个一分钟窗口何时开始和结束？如果我在窗口即将结束时开始突发请求，是否可以超出限制？窗口的容量是一次恢复一个请求，还是一次全部恢复？

In this post, we’ll explore the three most common algorithms to answer each of these questions.
在这篇文章中，我们将探讨三种最常见的算法来回答这些问题。

  1. Fixed windows 固定窗
  2. Sliding windows  推拉窗
  3. Token buckets 令牌桶

Fixed windows 固定窗

A set number of requests can be made within a predefined time window. Requests increment a counter that’s reset to zero at the start of each window.
可以在预定义的时间窗口内发出一定数量的请求。请求会增加一个计数器，该计数器在每个窗口开始时重置为零。

Allow 6 requests per day (24-hour windows)
每天允许 6 个请求（24 小时窗口）
Each green dot 
 represents an allowed request while 
 is a request blocked by the rate limiter. You can add more requests with the Hit button, which pauses the automatic stream.
每个绿点代表允许的请求，而代表被速率限制器阻止的请求。您可以使用 Hit 按钮添加更多请求，这会暂停自动流。
  • Pros 优点
    • Simple to implement and understand
      易于实施和理解
    • Predictable for users 用户可预测
  • Cons 缺点
    • Allows bursts up to 2x the limit when requests begin near the end of a window
      当请求在窗口末尾附近开始时，允许突发高达 limit 的 2 倍
  • Real-world example 现实世界的例子
    • GitHub’s API uses a fixed window rate limiter with limit = 5000, windowDuration = 1h, and windowStart set to the start of each wall clock hour, allowing users 5,000 requests per hour.
      GitHub 的 API 使用固定窗口速率限制器，将 limit = 5000 、 windowDuration = 1h 和 windowStart 设置为每个时钟小时的开始，允许用户每小时 5,000 个请求。
A brief tangent on 24-hour fixed windows
24小时固定窗口的简短切线

There is a subtle issue with the 24-hour limiter above. Its windows reset every day at midnight—but midnight according to what time zone? A standard fixed window might reset its counter according to your server’s midnight or a standard timezone offset such as UTC. A user in a different timezone who just ran out of requests might retry just after midnight and be surprised if the limit hasn’t been lifted—since to them, it is a new calendar day.
上面的 24 小时限制有一个微妙的问题。它的窗户每天都会在午夜重置——但是午夜是根据哪个时区来重置的呢？标准固定窗口可能会根据服务器的午夜或标准时区偏移（例如 UTC）重置其计数器。位于不同时区的刚刚用完请求的用户可能会在午夜后重试，如果限制尚未解除，他们会感到惊讶 - 因为对他们来说，这是一个新的日历日。

For these applications, you need to offset your window starts according to the user’s time zone, which has some potential for abuse as users can manually adjust their timezone once they’ve run out of requests to gain up to 1 full window of additional requests. Worse yet, users traveling West to East might incorrectly have more requests limited while those traveling East to West might incorrectly have more requests allowed as they effectively extend their day. If a rate limit resets based on local midnight and a user moves to an earlier time zone, they encounter earlier local midnights. This can effectively allow them to reset their request count sooner by being in a new “day” earlier than expected, thus potentially increasing their total allowable requests within a 24-hour period as measured by real time. Yikes. And we still haven’t dealt with DST.
对于这些应用程序，您需要根据用户的时区来偏移窗口启动，这可能会被滥用，因为用户可以在用完请求后手动调整其时区，以获得最多 1 个完整窗口的额外请求。更糟糕的是，从西向东旅行的用户可能会错误地限制更多请求，而从东向西旅行的用户可能会错误地允许更多请求，因为他们实际上延长了一天的时间。如果速率限制根据当地午夜重置并且用户移动到较早的时区，他们会遇到较早的当地午夜。这可以有效地允许他们通过早于预期进入新的“一天”来更快地重置请求计数，从而有可能增加实时测量的 24 小时内允许的请求总数。哎呀。我们还没有处理夏令时。

This use case is already a bit of a tangent, so for now I’ll leave it at this: handling time zones correctly, accounting for users relocating as well as daylight savings, is difficult to get right—so if you’re considering going down that painful path, I’ll just point you to these resources instead. If you can sidestep this problem by using any other approach at all, you should!

Fixed window with user-defined start
具有用户定义开始的固定窗口

Instead of fixing the start times to a set interval, each window can be created at the time of the user’s first request within that window.
每个窗口都可以在用户在该窗口内发出第一个请求时创建，而不是将开始时间固定为设定的时间间隔。

With this approach, it’s especially important to show users the time remaining until the next window once they’re limited since there’s no set time that aligns each window.
通过这种方法，一旦用户受到限制，向用户显示直到下一个窗口的剩余时间就显得尤为重要，因为没有固定的时间来对齐每个窗口。

Sliding windows 推拉窗

Instead of refreshing the capacity all at once, sliding windows refill one request at a time.
滑动窗口不是一次性刷新所有容量，而是一次填充一个请求。

  • Pros 优点
    • Smooths the distribution of request traffic
      平滑请求流量的分配
    • Well-suited for high loads
      非常适合高负载
  • Cons 缺点
    • Less predictable for users than fixed windows
      与固定窗口相比，用户的可预测性较差
    • Storing timestamps for each request is resource-intensive
      存储每个请求的时间戳是资源密集型的

Because sliding windows tend to be most useful in high-traffic scenarios, the fact that the naive algorithm is resource-intensive is counterproductive. Shouldn’t a high-traffic rate limiter use an efficient algorithm? For this reason, most real-world sliding window rate limiters, such as those provided by Upstash or Cloudflare, use an approximation, often called a floating window. Using this approximation, we have all the same pros but can remove the “resource-intensive” point from the cons. Here’s how it works:
由于滑动窗口往往在高流量场景中最有用，因此朴素算法占用资源这一事实会适得其反。高流量限速器不应该使用高效的算法吗？因此，大多数现实世界的滑动窗口速率限制器（例如 Upstash 或 Cloudflare 提供的那些）都使用近似值，通常称为浮动窗口。使用这个近似值，我们拥有所有相同的优点，但可以消除缺点中的“资源密集型”点。它的工作原理如下：

  1. Count the number of allowed requests in the previous fixed window.
    统计上一个固定窗口内允许的请求数。
  2. Count the number of allowed requests in the current fixed window.
    统计当前固定窗口内允许的请求数。
  3. Weight the previous window’s allowed requests proportional to that window’s overlap with a floating window ending at the current time.
    前一个窗口允许的请求权重与该窗口与当前时间结束的浮动窗口的重叠部分成比例。
  4. Add the weighted requests from (3) to the unweighted requests from (2).
    将 (3) 中的加权请求添加到 (2) 中的未加权请求中。

In other words, this is the computation:
换句话说，这是计算：

approximation = (prevWindowCount * prevWindowWeight) + currentWindowCount

In practice, this approximation limits requests at roughly the same proportion but is far more efficient than tracking all the requests’ timestamps. See for yourself how it compares:
实际上，这种近似以大致相同的比例限制请求，但比跟踪所有请求的时间戳要有效得多。亲自看看如何比较：

Precise window: limited 0
精确窗口：有限 0
Approximated: limited 0 估计：有限 0
  • Real-world example 现实世界的例子
    • Cloudflare’s configurable rate limiter uses an approximated sliding window.
      Cloudflare 的可配置速率限制器使用近似滑动窗口。

Token buckets 令牌桶

Instead of thinking in terms of windows with durations, picture a bucket that fills up with “tokens” at a constant rate. Each request withdraws one token from this bucket, and when the bucket is empty the next request will be blocked. This token bucket approach has some useful properties.
不要考虑具有持续时间的窗口，而是想象一个以恒定速率填充“令牌”的桶。每个请求都会从该桶中提取一个令牌，当桶为空时，下一个请求将被阻止。这种令牌桶方法有一些有用的属性。

  1. The capacity of the bucket is the maximum number of requests that a burst can support (not counting tokens that are replenished mid-burst).
    桶的容量是一次突发可以支持的最大请求数（不包括突发中补充的令牌）。
  2. The refill interval represents the long-term average allowed request interval.
    重新填充间隔代表长期平均允许的请求间隔。

Having distinct burst and average capacities without the need for multiple rate limiters is one of the main benefits to this algorithm.
该算法的主要优点之一是具有不同的突发容量和平均容量，而无需多个速率限制器。

  • Pros 优点

    • Allows bursts of high traffic, but enforces a long-term average rate of requests
      允许突发高流量，但强制执行长期平均请求率
    • More flexible for users, allowing for traffic spikes within an acceptable range
      对用户来说更加灵活，允许流量峰值在可接受的范围内

  • Cons 缺点

    • More difficult to convey limits and refill times to users than with fixed windows
      与固定窗口相比，向用户传达限制和补充时间更困难

  • Real-world examples 现实世界的例子

    • Stripe uses a token bucket in which each user gets a bucket with limit = 500, refillInterval = 0.01s, allowing for sustained activity of 100 requests per second, but bursts of up to 500 requests. (Implementation details.)
      Stripe 使用令牌桶，其中每个用户都会获得一个带有 limit = 500 、 refillInterval = 0.01s 的桶，允许每秒 100 个请求的持续活动，但最多可突发 500 个请求。 （实施细节。）
    • OpenAI’s free tier for GPT-3.5 is limited to 200 requests per day using a token bucket with limit = 200 and refillInterval = 86400s / 200, replenishing the bucket such that at the end of a day (86,400 seconds) an empty bucket will be 100% filled. They refill the bucket one token at a time.
      OpenAI 的 GPT-3.5 免费套餐每天使用带有 limit = 200 和 refillInterval = 86400s / 200 的令牌桶限制为 200 个请求，补充桶，以便在一天结束时（86,400 秒）空桶将 100% 填满。他们一次给桶装满一个令牌。

    The Twitch chat demo above is rate-limited using a token bucket with a bucket size of 3, allowing bursts of up to 3 requests, and a refill interval of 4 seconds, which creates a long-term average allowed rate of 1 message every 4 seconds.
    上面的 Twitch 聊天演示使用桶大小为 3 的令牌桶进行速率限制，允许最多 3 个请求的突发，以及 4 秒的重新填充间隔，这创建了每 4 条消息的长期平均允许速率秒。

    Thanks to their flexibility, token buckets can also mimic the properties of some of the other algorithms. For example, set the refillRate equal to the limit and you have an equivalent to a fixed window rate limiter with a user-defined start.
    由于其灵活性，令牌桶还可以模仿其他一些算法的属性。例如，将 refillRate 设置为等于 limit ，您就拥有了一个相当于具有用户定义启动的固定窗口速率限制器。

Other considerations 其他考虑因素

If you decide to add rate limiting to your application or endpoint, in addition to selecting an appropriate algorithm there are a few other things you should keep in mind.
如果您决定向应用程序或端点添加速率限制，除了选择适当的算法之外，您还应该记住其他一些事情。

  • Create a persisted store for the rate limiter. If you ever intend to horizontally scale your server (or even just restart it) your rate limiter data store can’t be in-memory. A popular option is to save rate limiting data to a key-value store like Redis, which has built-in functions for expiring keys, on a separate machine from your application. You can, however, use an ephemeral in-memory cache to block requests without hitting Redis while the limiter is hot.
    为速率限制器创建持久存储。如果您打算水平扩展服务器（甚至只是重新启动服务器），则速率限制器数据存储不能位于内存中。一种流行的选择是将速率限制数据保存到 Redis 等键值存储中，Redis 具有用于过期键的内置功能，位于与应用程序不同的计算机上。但是，您可以使用临时内存缓存来阻止请求，而无需在限制器很热时访问 Redis。
  • Fail open. If your server’s connection to the persisted store fails, make sure to allow all requests rather than blocking access to your service altogether.
    打开失败。如果服务器与持久存储的连接失败，请确保允许所有请求，而不是完全阻止对服务的访问。
  • Optionally throttle bursts. Throttling can be used in combination with rate limiting to reduce the impact of burst traffic.
    可选择油门爆发。节流可以与速率限制结合使用，以减少突发流量的影响。
  • Choose sensible keys. In general, rate limiting is done on a per-user level. For most apps, this means keying on the user ID. For APIs, key on an API key. To rate limit unauthenticated users, the options aren’t great, but popular methods include using the request’s IP address, a device fingerprint, a unique installation ID, or just a shared limiter.
    选择合理的按键。一般来说，速率限制是在每个用户级别上完成的。对于大多数应用程序来说，这意味着键入用户 ID。对于 API，请输入 API 密钥。要对未经身份验证的用户进行速率限制，选项并不好，但流行的方法包括使用请求的 IP 地址、设备指纹、唯一的安装 ID 或只是共享限制器。
  • Surface useful rate limiting errors. Let users know how long they have to wait for their next request. For APIs, use the 429 HTTP status code when a request is blocked and include the relevant x-ratelimit-* response headers. GitHub has good examples of the headers for their fixed-window limiter and OpenAI has some for their token-bucket limiter.
    表面有用的速率限制错误。让用户知道他们需要等待下一个请求多长时间。对于 API，当请求被阻止时使用 429 HTTP 状态代码并包含相关的 x-ratelimit-* 响应标头。 GitHub 有固定窗口限制器的标头示例，OpenAI 有一些令牌桶限制器的标头示例。

Wrapping up 包起来

  • If you need a simple rate limiter or predictable window start times, use a fixed window.
    如果您需要简单的速率限制器或可预测的窗口开始时间，请使用固定窗口。
  • If you need traffic smoothing for a high volume of requests, consider using an approximated sliding window.
    如果您需要对大量请求进行流量平滑，请考虑使用近似滑动窗口。
  • If you need to support bursts of traffic while enforcing a lower average long-term rate for requests, use a token bucket.
    如果您需要支持流量突发，同时对请求强制执行较低的平均长期速率，请使用令牌桶。

Playground 操场

Fixed window 固定窗
Fixed window with user-defined start
具有用户定义开始的固定窗口
Sliding window 滑动窗口
Sliding window approximated
滑动窗口近似
Token bucket 令牌桶

This post was inspired by the amazing load balancing visualizations at samwho.dev. Also, a huge thank you to @onsclom for pairing with me on the canvas visualizations. Lastly, shoutout to Upstash for their docs and implementation scripts, which served as an excellent reference for each algorithm.
这篇文章的灵感来自 samwho.dev 上令人惊叹的负载平衡可视化。另外，非常感谢 @onsclom 与我一起进行画布可视化。最后，感谢 Upstash 的文档和实现脚本，它们为每个算法提供了很好的参考。

There’s a discussion about this post on Hacker News as well.
黑客新闻上也有关于这篇文章的讨论。

Feel free to send corrections, ideas, and feedback my way at feedback@smudge.ai!
请随时通过我的方式发送更正、想法和反馈：feedback@smudge.ai！

This post is the second in a series where I document some of the things I’ve learned while building smudge.ai. If you’re new here, smudge.ai is a Chrome extension that lets you save custom ChatGPT commands into your right-click menu. It’s a (mostly) solo project and an extension I rely on almost every day. If you think it could be a useful tool for you, too, then you can always try smudge.ai for free with no account using the rate-limited free tier, which happens to have been implemented as a fixed window with a user-defined start. Cheers!
这篇文章是系列文章中的第二篇，我记录了我在构建 smudge.ai 时学到的一些东西。如果您是新来的，smudge.ai 是一个 Chrome 扩展程序，可让您将自定义 ChatGPT 命令保存到右键菜单中。这是一个（大部分）独立项目，也是我几乎每天都依赖的扩展。如果您认为它对您来说也是一个有用的工具，那么您可以随时免费尝试 smudge.ai，无需使用速率限制的免费套餐，该免费套餐恰好已实现为具有用户定义的固定窗口开始。干杯!
rate limiter – smudge.ai blog