速率限制定义了系统在指定时间段内可以处理的最大请求数量。
Image.png
速率限制是一种策略，我们在工作中常常使用，它定义了系统在设定的时间框架内可以处理的最大请求数量。
- 防御策略：这不仅仅是关于控制流量，而且还关于保护系统免受像DDoS攻击和潜在滥用等威胁。此外，不受限制的请求有时会成为攻击者利用漏洞的入口。
- 确保公平性：我可以确保系统为每个人都表现出色，确保每个用户都能公平分享系统的资源。
- 分层访问：对于高级用户，可以有更高的请求限制，而对于免费用户，则有一个标准限制。
在选择算法时，我遇到了几种不同的方法。
选择合适的方法至关重要，它应该与您的系统的特定需求以及您试图解决的挑战相一致。
1. 令牌桶
在速率限制方面，有一种方法我经常使用，这是由于它的简单性，对于本示例，我将在用户级别进行设置。
“那么‘在用户级别’到底是什么意思呢?”
实质上，它表示速率限制是为每个单独的用户定制的，确保为他们定制了独特的限制。想象一下，每个用户都被分配一个容量为5个令牌的桶，每当用户发出请求时，就会消耗1个令牌。在10分钟的时间内，系统被设计为能够在每个桶中重新填充3个令牌。如果用户的桶是空的，他们将无法再发出更多的请求，直到添加了一些令牌。以下是根据我的配置的详细说明：
- 桶限制：5个令牌。
- 请求使用：1个令牌。
- 重新填充速率：10分钟/3个令牌。
Image.png
(1) 优点
我观察到这种方法的一个关键优势是它相当节约资源。它在内存上占用较少的空间，不会对CPU造成太大的负担。
“您提到每10分钟进行一次重新填充。如果有1000万用户，这不是很占资源吗?”
与其为每个用户不断重新填充令牌，您可以采用一种“懒惰重新填充策略”。这意味着只有在用户实际提交请求时才会更新令牌计数。
此外，该方法相对较容易实施。
它旨在支持突发行为。在闲置期间，令牌会积累到其最大限制，使用户偶尔能够快速连续发出多个请求。
(2) 缺点
调整参数可能需要一些权衡，因此确定理想的桶大小、重新填充速率和请求使用可能需要一些试验。
尽管允许突发行为可能是有利的，但它也有其缺点。存在用户在短时间内发送大量请求的潜在风险。为了避免突发行为，我们可以应用“漏桶”策略以实现更一致的工作流。
2. 漏桶
而令牌桶会快速处理每个请求，漏桶采用了不同的方法。对于这种方法，每个请求都有一个固定的处理时间。
想象一下漏桶的运作方式，就像一个队列，如果队列达到其容量，任何进入的请求都会被拒绝。
Image.png
“但为什么要给它起名字‘漏桶’呢?这里哪里有漏洞呢?”
想象一下，桶底部有一个小孔，可以让水稳定滴出。如果您比桶内的水流得更快，会发生什么?确切地说，它会溢出，任何多余的水，就像我们的多余请求一样，都会被丢弃。
(1) 它是如何运作的?
我们从一个最多可以容纳10个单位的桶开始，每个请求需要1秒来处理。
- 时间0秒：桶是空的。
- 时间1秒：您向桶内倒入8个单位，现在它有了8个单位。
- 时间2秒：1个单位泄漏出去，剩下7个单位。
- 时间4秒：还有6个单位，我们尝试添加5个单位，但只有4个可以放下，导致1个溢出。现在桶满了，有10个单位。
(2) 优点
- 实施简单，在许多方面，它甚至比令牌桶更简单。
- 平滑突发行为，因此没有突发，客户可以急匆匆，但我们总是保持冷静。
(3) 缺点
- 不适合处理突发情况，比如特殊活动或假期期间。
- 太多被丢弃的请求可能会成为问题
“但如果一个读取请求只需要100毫秒，而我们的排水速度设置为1秒呢?”
请求仍然需要1秒处理。不过，可以调整设置：允许低于1秒的请求以其自然速度进行处理。然而，这样做可能会促使用户淹没系统，从而抵消了漏桶的优势，也许在这种情况下有更适合的方法。
“如果我们有一个较慢的请求，比如1秒，但桶的排水速率只有200毫秒呢?”
桶会继续释放该请求，但这可能是我们的排水速率设置得太低的一个指标，所以要小心。
3. 固定窗口计数器
移向基于时间的算法，让我们讨论一下固定窗口计数器。虽然听起来有所不同，但我们仍然可以使用我们熟悉的“桶”和“令牌”来解释这个概念。
每小时(这个时间很关键)，客户端都会得到一个空的请求桶。每次他们发出请求时，一个令牌就会被放入这个桶中。一旦桶满了，就不允许再发出更多的请求。
(您可以想象客户端从带有令牌的桶开始，每次请求都会拿走一个令牌，没有令牌意味着不能再发出更多请求。)
1*EdG-thC8YV5khwiWGo-X-Q.png
“但这与令牌桶方法有什么不同呢?”
我理解您的困惑，这两种方法似乎都在随时间分配令牌。固定窗口计数器在小时结束时不考虑以前的令牌使用情况，计数器在每个窗口结束时重置为0，与以前的活动无关。相反，令牌桶方法根据剩余的令牌重新填充：previous_tokens
+= refill_rate(但始终在其最大容量内)。
(11) 它是如何运作的?
我们正在使用一个1分钟的窗口，并且我们的计数器的上限设置为10
- 时间0秒：计数器为0，一个客户端发送了5个请求，将计数器提升到5。
- 时间10秒：又来了3个请求，将计数器推到8。
- 时间30秒：另外2个请求，我们的计数器达到了10，这就是这个窗口的限制。
- 时间40秒：一个客户端尝试另一个请求，但被拒绝了，限制已经达到。
- 时间60秒：一个新的窗口开始了，我们的计数器重置为0。
(2) 优点
- 这种方法易于实施和监控。
- 一旦时间窗口重新开始，客户端可以立刻发送一整组请求，允许突发行为。
(3) 缺点
- 存在一种突发请求在窗口边界的机会。
- 用户必须等待重置才能发出请求
例如，对于一个1小时的窗口和一个10个请求的限制，客户端可以在7:59:59和8:00:00之间的过渡时刻发送20个请求
4. 滑动日志
将滑动日志视为固定窗口的更好版本。它旨在处理窗口边缘的请求太多的问题。
与其坚持刚性的窗口，这个方法随着时间的推移而滑动。
对于每个传入的请求，我们的系统将迅速记下其时间戳。每个新的请求都会引发快速的回顾，以查看“过去N秒内有多少请求。
1*rGCamyRYi0ovqjvSozC0yQ.png
(1) 它是如何运作的?
想象一下，我们将时间窗口设置为10秒，并将其限制为3个请求，这意味着在任何给定的10
秒内只允许3个请求。
- 时间0秒：一个请求进来，我们做个标记 - [0]。
- 时间4秒、8秒：又来了两个请求 - [0, 4, 8]。
- 时间9秒：另一个请求尝试进来，但被拒绝，因为我们已经达到了限制。
- 时间11秒：首先，我们去掉了超过10秒的旧条目，留下了[4, 8]。由于还有空间，这个请求被允许 - [4, 8, 11]。
- 时间15秒：两个请求到达后，删除过时的条目后，我们的列表看起来像[8, 11]。但我们只能接受其中的一个，更新日志为 - [8, 11, 15]。
这个过程很清楚：删除旧日志，检查新请求，更新日志。
(2) 优点
- 有助于避免在窗口边缘太多的请求
- 客户端不需要等待完全重置，提供更均匀的请求流。
(3) 缺点
- 它需要更多的计算能力，因为我们必须为每个新请求清理旧条目。
- 由于需要跟踪时间戳，所以存储需求更大，如果我们的规模很大，这可能会成为一个问题。
5. 滑动窗口
对于滑动窗口，与滑动日志不同，我们略微简化了事情。我们关注的是最后一个窗口中的请求数量。
所以，如果你发现自己处于当前窗口的75%，你会权衡请求。25%来自上一个窗口，其余来自当前窗口：
权重 = (100 - 75)% * 上一个窗口的请求 + 当前窗口的请求
现在，当一个新请求试图加入这个过程时，你将这个权重加1(权重+1)。如果这个新的总数超过了我们设定的限制，我们必须拒绝这个请求。
1*js-77Ra-5xS-VVcVFlhdpw.png
它是如何运作的?
假设有一个每分钟10个请求的窗口。
让我们将这个过程分为两个阶段，窗口A为第一分钟，窗口B为第二分钟。
- 在0秒：我们收到一个初始请求，这意味着窗口A的计数器开始计时，现在为A_counter = 1。
- 在59秒：又来了7个请求，所以A_counter = 8。
- 在1分6秒：一个客户端决定发送另外3个请求。记住我们从窗口A的计数器中得到的8?因为我们已经进入窗口B，大约有10%消失，我们将使用90%的窗口A计数器值进行下一次计算。
current_weight = 90% * A_counter + 0 = 7.2
这允许大约再添加2个请求(因为7.2 + 2 < 10)。但第三个请求呢?
很遗憾，它被拒绝了，B_counter现在为2。
“但如果一个客户在59秒时发送8个突发请求，然后在1分钟6秒时偷偷再发送2个，他们仍然能够通过，对吗?”
正是如此，这就是与滑动日志相比的一个小权衡。我们选择更少的计算工作和存储空间来换取更高的准确性。使用方程式(1 - 百分比通过)* 上一个窗口 +
当前窗口，我们猜测上一个窗口的请求在时间上是均匀分布的，而不是一次性全部到来。这是一个战略性的选择，旨在寻求一种更高效的方法，即使这意味着在准确性上有所减少。考虑到您的资源、如何管理突发流量、准确性以及您愿意处理多少复杂性，选择适合您需求的正确速率限制器。
