标签：令牌 窗口 请求 算法 限流 速率 日志

Token bucket algorithm 令牌桶算法

该算法用具有预定义令牌容量的桶进行类比，这个桶会定期以恒定速率填充令牌。令牌可以被视为某种特定大小的数据包。

因此，每次我们收到请求时，算法都会检查存储桶中的令牌，每个请求应该至少有一个令牌才可以被转发以进一步处理。

令牌桶的算法流程如下：

假设我们预定义的速率限制为 R（/单位时间），桶的总容量为 C。

1. 该算法每隔 1/R 单位时间向存储桶添加一个新令牌
2. 当桶中的令牌数量等于桶的总容量 C 时，算法会丢弃新传入的令牌
3. 如果有 N 个请求传入，并且存储桶至少有 N 个令牌，则 N 个令牌将被消耗，并且请求将被转发以进一步处理。
4. 如果有 N 个传入请求并且存储桶中的令牌数量较少，则接受的请求数量等于存储桶中的可用令牌数量。

下图展示了令牌桶算法的工作原理。

下图演示了令牌消耗和速率限制逻辑的工作原理。在此示例中，桶的容量为三，并且以每分钟三个令牌的速率重新填充。

• 最初，桶中有三个令牌。请求在一分钟内到达并消耗存储桶中的令牌

• 同一分钟内又有两个请求到达并消耗剩余的两个令牌

• 同一分钟内又收到一个（第四个）请求。拒绝请求，因为桶是空的

• 一分钟后重新装满水桶

基本参数

• 桶容量 (C) ：桶中可以驻留的最大令牌数量。
• 速率限制 (R)：我们要限制每单位时间的请求数量。
• 重填速率（1/R）：每隔多长时间向存储桶添加一个新令牌。
• 请求计数 (N)：此参数跟踪传入请求的数量并将其与存储桶的容量进行比较。

优点

• 只要桶中有足够的令牌，该算法就可以造成流量的突发。
• 节省空间。由于状态有限，该算法所需的内存是标称的。

缺点

• 为基本参数选择最佳值比较困难

令牌桶算法除了允许突发流量之外，还可能超出限制的边缘吗？

是的，令牌桶算法有时可能会超出边缘的限制，如以下示例所示：

考虑一个场景，桶容量等于 3，每分钟允许的请求数也是 3。这会产生 0.33分钟的补充率，这意味着每 0.33 分钟就会有一个新令牌。第一分钟结束时已累积了三个令牌。与此同时，大量请求到达并消耗了所有三个令牌，使桶空了。在 1.33 分钟结束时（重新填充率为 0.33），新令牌将添加到存储桶中。同时，一个新请求到达并消耗了一个令牌。
但是，如果我们考虑从 0.66 到 1.33 分钟（共 0.66 小于一分钟）的持续时间，我们将看到总共消耗了 4 个令牌。这个例子说明了令牌桶可以超越边缘的限制。

 

The leaking bucket algorithm 漏桶算法

漏桶算法是令牌桶算法的一个变体，略有修改。漏桶算法不使用令牌，而是使用桶来包含传入请求并以恒定的传出速率处理它们。该算法使用以恒定速率泄漏的水桶进行类比。同样，在此算法中，请求以可变速率到达，而该算法按照先进先出 (FIFO) 的顺序以恒定传出速率处理这些请求。

下图展示了漏桶算法是如何工作的：

基本参数：

• 桶容量 (C)：这决定了桶的最大容量。当存储桶达到其最大限制 C 时，算法将丢弃传入请求。
• 流入率 (R_in)：该参数显示请求的流入率。这是一个变化的数量，取决于请求的应用和性质。
• 流出率 (R_^out​) ：这决定了单位时间处理的请求数量。

优点

• 由于流出速率恒定（R_out），因此它避免了请求的突发，这与令牌桶算法不同。
• 该算法还具有空间效率，因为它只需要三个状态：流入率 (R_in)、流出率 (R_out) 和存储桶容量 (C)。
• 由于请求以固定速率处理，因此适合流出速率稳定的应用。

缺点

• 突发的请求可能会填满存储桶，如果未在指定时间内处理，最近的请求可能会受到影响。
• 确定最佳的漏桶尺寸和流出率是一项挑战。

 

Fixed window counter algorithm 固定窗口计数器算法（也叫流量计数器）

该算法将时间划分为称为窗口的固定间隔，并为每个窗口分配一个计数器。当特定窗口收到请求时，计数器加一。一旦计数器达到其限制，新的请求将在该窗口中被丢弃。 如下图所示，虚线代表每个窗口的限制。如果计数器低于限制，则转发请求；否则，丢弃该请求。

该算法存在一个重大问题。在窗口边缘可能会出现大于允许请求的流量突发。下图中，系统每分钟最多允许 10 个请求。但01:30到02:30的一分钟窗口内请求数为20个，大于允许的请求数。

基本参数

• 窗口大小 (W)：表示时间窗口的大小。它可以是一分钟、一小时或任何其他合适的时间片。
• 速率限制 (R)：显示每个时间窗口允许的请求数量。
• 请求计数 (N)：该参数显示每个窗口传入请求的数量。如果 N 小于或等于R，则允许传入请求。

优点

• 由于请求率的限制，它还具有空间效率。
• ????与令牌桶式算法（如果没有足够的令牌则丢弃新请求）相比，该算法为新请求提供服务。

缺点

• 窗口边缘的持续流量突发（每个窗口允许的请求数的两倍）可能会导致性能潜在下降。

 

Sliding window log algorithm 滑动窗口日志算法

滑动窗口日志算法跟踪每个传入请求。当请求到达时，其到达时间存储在哈希映射中，通常称为日志。日志根据传入请求的时间戳进行排序。是否允许请求通过取决于日志的大小和到达时间。 与固定窗口计数器算法相比，该算法的主要优点是它不受边缘条件的影响。   让我们通过下图了解滑动窗口日志算法的工作原理。假设我们的最大速率限制为一分钟内两个请求。

• 新请求于 01:00 到达。它的到达时间将添加到日志中，并接受此请求。时间窗口标记为 01:00 至 02:00

•  另一个请求在 1:20 到达，它的时间戳被现在的日志大小小于最大限制，所以请求被允许通过

• 第三个请求在 1:45 到达，它的时间戳被添加到日志中，算法拒绝了这个请求，因为日志大小已经是 3 超过了最大限制。

• 02:25 收到新请求，这个时间戳超出了上一个时间窗口，所以我们从这里开始一个新窗口（最新超出窗口的请求倒推一分钟）。在日志中只保留最新窗口（从 01:25 到 02:25）。旧数据从日志中移除，大小相应减小

基本参数

• 日志大小 (L)：此参数类似于速率限制 (R)，因为它确定特定时间范围内允许的请求数量。
• 到达时间 (T)：此参数跟踪传入请求的时间戳并确定其计数。
• 时间范围 (T_r)：该参数确定时间范围。如果旧请求的时间戳不在此范围内，则将其删除。窗口的开始时间是根据第一个传入请求定义的，并在一分钟后到期。类似地，当到期时间之后另一个请求到达时，窗口范围也会相应更新。

优点

• 该算法不受固定窗口边界条件的影响。

缺点

• 它消耗额外的内存来存储附加信息，即传入请求的时间戳。即使请求被拒绝，它也会保留时间戳以提供动态窗口。

 

Sliding window counter algorithm 滑动窗口计数器算法

与之前的固定窗口算法不同，滑动窗口计数器算法不会基于固定时间单位来限制请求。该算法同时考虑了固定窗口计数器和滑动窗口日志算法，使请求的流程更加顺畅。 我们看一下下图的算法流程，其中绿色阴影区域表示1分钟的滑动窗口

 在上图中，前一个窗口中有 88 个请求，当前窗口有 12 个请求。我们将速率限制设置为每分钟 100 个请求。此外，滑动窗口与当前窗口重叠15秒。现在假设新请求于 02:15 到达。我们将使用数学公式来决定接受或拒绝哪个请求：

• R_p：上一个窗口的请求数。这里是 88
• R_c：当前窗口的请求数。这里是 13
• time frame：窗口的大小。这里是一分钟 60 秒
• overlap time：绿色的滑动窗口 与 当前窗口的重叠时间大小。这里是 15 秒

由于 78<100 （滑动窗口速率限制），所以允许请求传入

优点

• 由于状态有限，该算法还具有空间效率：当前窗口中的请求数量、前一个窗口中的请求数量、重叠百分比等。
• 它平滑突发的请求，并根据前一个窗口以近似平均速率处理它们。

缺点

• 该算法假设前一个窗口中的请求数量是均匀分布的，但这并不总是可能的。

 

限流算法比较

所有速率限制算法共有的两个主要因素是：

• 内存：此功能是指算法正常操作所需维护的状态数量。例如，如果一种算法比另一种算法需要更少的变量（状态），则它的空间效率更高。
• 突发：是指单位时间内流量的增加超过了定义的限制。

下表显示了描述的所有算法的空间效率和流量突发：

算法	节省空间	允许突发
令牌桶	Yes	Yes,它允许在最大限制内的流量突发（小于最大限制，但是突发）
漏桶	Yes	No
固定窗口（流量计数器）	Yes	Yes,它允许在窗口边缘出现流量突发，并且可以超出定义的限制
滑动窗口日志	No,维护日志需要额外的存储空间	No
滑动窗口计数器	Yes,但是它比其它节省空间的算法需要相对更多的存储空间	平滑突发

 

 

参考：

educative：Grokking Modern System Design Interview for Engineers & Managers

 

 

标签：令牌,窗口,请求,算法,限流,速率,日志
From： https://www.cnblogs.com/suBlog/p/17596902.html