流量控制演算法：Leaky Bucket 与 Token Bucket

在设计网路服务时，流量控制和资源管理是非常重要的课题。当系统面临大量 Requests 或突发流量时，无限制地接受 Request 可能导致资源耗尽或服务中断。为了解决这些问题，必须有机制来限制流量并平衡系统负载。Leaky Bucket 和 Token Bucket 是两种常见的演算法，能够有效地实现流量控制与资源管理，广泛应用于 Rate Limiting 和 Traffic Shaping。以下将介绍这两种演算法的目的、如何使用以及实作范例。

Leaky Bucket

目的

Leaky Bucket 演算法主要用于平滑网路流量，确保数据以稳定的速率处理。可以防止突发流量影响系统稳定性，并提供简单的 Rate Limiting 机制。在特定场景下，Leaky Bucket 的优势体现在其对稳定流量的控制能力，例如在处理需要均匀输出的批量任务时，这种方式可以避免系统瞬间超载。同时，Leaky Bucket 在实现和计算上相对简单，适合需要低效能开销的系统。

如何使用

范例程式（Pseudo Code）

Initialize bucket with capacity and leak_rate
Set current_water = 0
Set last_check_time to current time

Function add_request():
current_time = get current time
elapsed_time = current_time - last_check_time
last_check_time = current_time

Reduce current_water by elapsed_time * leak_rate
If current_water < 0:
Set current_water = 0

If current_water + 1 <= capacity:
Increase current_water by 1
Return True (request allowed)
Else:
Return False (request denied)

分散式系统情境

在分散式系统中，Leaky Bucket 可用于平滑多个节点的流量。例如，当多个使用者同时访问一个共享的资源时，Leaky Bucket 可确保每个节点以稳定的速率处理请求，避免突发流量导致系统过载。此外，它可以部署在 API Gateway 上，对进入系统的流量进行限制。

效能与空间影响

Leaky Bucket 的效能开销主要在于追踪水桶中当前水量以及处理流量的速率。由于只需追踪单一数值（当前水量）和基本的时间计算，空间需求极低，效能开销也相对较小，非常适合高併发的场景。在高併发场景中，可以将水量更新操作优化为基于时间间隔的批量更新，减少频繁的计算。此外，对于多执行绪或多节点环境，可以使用锁机制 (Lock) 或原子操作 (Atomic Operation) 来确保水桶中水量的正确性，同时避免併发问题。这些细节有助于降低实现中的额外开销并提升整体效能。

对应的 HTTP 状态码与 Retry-After

Leaky Bucket 并非专门设计用于计算重试时间，但可以根据剩余水量和漏出速率推算出下一次可接受请求的时间。如果要实现支援 Retry-After，则需返回基于剩余水量的等待时间。例如，若水量需要 2 秒才能降到可接受请求的水位，则返回 HTTP 状态码 429 Too Many Requests，并附带标头 Retry-After: 2。

HTTP Response 范例

HTTP/1.1 429 Too Many Requests
Retry-After: 2
Content-Type: application/json

{
"error": "Too many requests, please try again later."
}

此实作范例说明了如何在返回 Rate Limiting 的同时告知客户端应等待的时间，帮助其适当调整请求频率。

Token Bucket

目的

Token Bucket 演算法主要用于允许一定程度的突发流量，同时限制平均流量速率。常用于限流器 (Rate Limiter)，允许短时间内的高流量，但在过载时会逐渐减速。实际应用中，Token Bucket 广泛用于 API Gateway 和 CDN 系统。在 API Gateway 中，Token Bucket 用于对每个 API 使用者进行限流，根据使用者的需求允许短期高峰流量但控制长期平均速率；在 CDN 系统中，Token Bucket 被用来限制每个客户端的请求频率，确保流量不会压垮来源伺服器。同时，它还能应对突发的大量 Request，保持服务稳定。

如何使用

范例程式（Pseudo Code）

Initialize bucket with capacity and refill_rate
Set current_tokens = capacity
Set last_refill_time to current time

Function consume():
current_time = get current time
elapsed_time = current_time - last_refill_time
last_refill_time = current_time

Increase current_tokens by elapsed_time * refill_rate
If current_tokens > capacity:
Set current_tokens = capacity

If current_tokens >= 1:
Decrease current_tokens by 1
Return True (request allowed)
Else:
Return False (request denied)

分散式系统情境

在分散式系统中，Token Bucket 适合处理突发流量场景。例如，某些微服务可能会在短时间内收到大量请求，Token Bucket 允许这些突发流量通过，同时在长时间内限制总流量，避免影响其他服务。此外，Token Bucket 常被用于 API Gateway，为每个使用者或应用服务设定单独的流量限制，确保资源公平分配。

效能与空间影响

Token Bucket 的效能影响取决于 Token 的生成速率和水桶容量大小。由于需要频繁更新 Token 数量，会产生一定的计算开销。此外，储存 Token 数量与 Timestamp 的空间需求也较小，但比 Leaky Bucket 略高。在高併发场景中，能接受突发流量的使其非常实用，尽管效能开销稍高于 Leaky Bucket。

对应的 HTTP 状态码与 Retry-After

Token Bucket 更适合使用 Retry-After，因为 Token 是以固定速率补充的，可以直接计算下一个 Token 可用的时间。例如，若补充速率为每秒 2 个 Token，且当前无 Token ，则可返回 Retry-After: 0.5，提示客户端等待 0.5 秒再尝试。

比较

本篇文章也同步刊载在个人 Blog 上