ᕕ( ᐛ )ᕗ Jimyag's Blog

分布式限流算法：令牌桶、漏桶与 Redis 实现

· 819 words · ~ 4 min read

单机限流并不难，难的是把限流状态放到多台应用实例之间共享，而且还要保证判断和更新是原子的。

这篇文章只讲两种最常见的限流算法：

  • 令牌桶 token bucket
  • 漏桶 leaky bucket

重点放在三件事：

  • 两种算法的流程
  • 它们在工程行为上的区别
  • 用 Redis 时适合选择哪些数据类型

多个应用实例共享 Redis 里的限流状态，请求是否放行取决于当前桶状态和一次原子更新的结果。

1. 先看两个算法的区别

令牌桶

令牌桶的核心规则可以直接看流程：

  flowchart TD
    A["请求到来"] --> B["读取桶状态<br/>tokens / last_refill"]
    B --> C["按时间补充令牌"]
    C --> D["令牌数是否超过 capacity"]
    D -->|是| E["截断到 capacity"]
    D -->|否| F["保留当前值"]
    E --> G{"tokens >= 1 ?"}
    F --> G
    G -->|是| H["扣减 1 个令牌"]
    H --> I["放行请求"]
    G -->|否| J["拒绝请求"]

它的行为特征是：

  • 令牌按恒定速率补充
  • 桶里可以积累额度，所以允许短时间突发
  • 长期平均速率仍然受控

例如 capacity = 100、refill = 10/s 时：

  • 最多积累 100 个令牌
  • 长期平均速率约 10 次/秒
  • 空闲一段时间后，可以一次性放过更多请求

这里还有一个实现细节经常会让人困惑：令牌到底从什么时候开始放。

工程实现里通常不会真的起一个后台线程持续往桶里塞令牌，而是用“懒补充”：

  • 桶初始化时记录一个时间基准，比如 last_refill = now
  • 后续每次请求到来时，用 now - last_refill 计算这段时间理论上该补多少令牌
  • 然后再更新 tokens 和 last_refill

初始化语义一般有两种：

  • 初始满桶：tokens = capacity，最常见，系统一开始允许一次 burst
  • 初始空桶：tokens = 0，少见，之后再按速率慢慢积累

很多 Redis 实现还会采用“首次访问时初始化”的方式：

  • 如果这个桶的 key 还不存在，就在第一次请求时把它视为新桶
  • 然后把 last_refill 设为当前时间
  • 是否满桶还是空桶，取决于你的策略选择

漏桶

漏桶的核心流程是：

  flowchart TD
    A["请求到来"] --> B{"桶是否已满"}
    B -->|否| C["请求进入桶"]
    C --> D["按固定速率出桶"]
    D --> E["下游处理"]
    B -->|是| F["拒绝请求<br/>或进入等待队列"]

它的行为特征是：

  • 入口流量可以有抖动
  • 桶负责吸收这部分抖动
  • 出口速率更平滑
  • 下游看到的是更稳定的流量

一句话对比

可以直接记：

  • 令牌桶：控制平均速率，允许突发，更像配额系统
  • 漏桶：平滑输出速率，不鼓励突发，更像排队整形

场景上通常是：

  • API 网关、登录、短信验证码，更适合先考虑令牌桶
  • 任务消费、消息投递、下游保护，更适合先考虑漏桶

2. Redis 里该用什么数据类型

Redis 里这几种数据结构在这里最常见的用法是：

  • String：简单值、计数器、单状态时间戳
  • Hash：一个 key 下保存多个状态字段
  • Sorted Set：成员有序，适合按时间维护请求集合
  • Stream：追加式事件流，适合排队和消费

先给结论：

  • 令牌桶通常用 Hash + Lua
  • 漏桶如果是同步拒绝式，通常优先 String/Hash + Lua
  • 漏桶如果需要显式维护积压集合，可以用 Sorted Set
  • 漏桶如果是异步排队式，通常用 Stream

令牌桶：优先用 Hash

最常见的令牌桶状态只有两个：

  • tokens
  • last_refill

为什么优先用 Hash，而不是多个独立 String：

  • 一个 key 下管理多个字段，状态更集中
  • 更适合在 Lua 里一次性原子更新
  • 多个 String 也能实现，但状态分散，更容易引入一致性问题

漏桶：常见有两种实现

漏桶在工程里常见分成两类：

1. 同步拒绝式

这种实现不真的排队处理请求，而是维护一个“计划出桶时间”或“当前桶内积压”。

更常见的做法是只维护一个标量状态，比如 next_allowed_time：

  flowchart TD
    A["请求到来"] --> B["读取 next_allowed_time"]
    B --> C{"是否已经到可服务时间"}
    C -->|是| D["更新 next_allowed_time = now + interval"]
    D --> E["放行"]
    C -->|否| F["拒绝或返回 wait_ms"]

这种做法的优点是：

  • 状态很小
  • Lua 原子更新直接
  • 更接近经典漏桶状态机

如果你希望显式维护“当前积压请求集合”，也可以用 Sorted Set：

  flowchart TD
    A["请求到来"] --> B["ZSET 中删除已漏出的旧请求"]
    B --> C["统计当前剩余成员数"]
    C --> D{"是否小于桶容量"}
    D -->|是| E["ZADD 新请求"]
    E --> F["放行"]
    D -->|否| G["拒绝"]

这里通常会把：

  • score 设计成时间戳
  • member 设计成请求 ID
  • 再按时间清理旧请求并统计当前积压量

这个做法是可行的工程建模，但它更像“按时间维护积压请求集合”，不是唯一的漏桶落地方式。

2. 真的要排队并匀速消费

这种实现更像一个平滑队列：

  • 请求先进入一个缓冲区
  • 后台 worker 按固定速率取走

这时候更适合：

  • 用 Stream
  • 或者更简单的 List

如果需要：

  • 保留事件顺序
  • 有多个消费者
  • 管理消费进度

那 Stream 比 List 更合适。

所以对漏桶，不要只记“Redis 用什么类型”，而要先问：

  • 你是想做“拒绝式限流”？
  • 还是想做“排队式整形”？

两者对应的数据结构不一样。

3. 用 Redis 实现令牌桶

Redis 官方已经给过一个标准思路：用 Lua 脚本实现 token bucket rate limiter。核心就是把状态放进 Hash，然后在脚本里原子完成整个计算过程。

状态设计

key 设计示例：

1

rate_limit:token_bucket:{user_id}

value 用 Hash：

1
2

tokens
last_refill

也就是一个 key 下的两个字段：

  • tokens
  • last_refill

核心流程

  flowchart TD
    A["请求到来"] --> B["HMGET tokens / last_refill"]
    B --> C["计算应补充的令牌数"]
    C --> D["按 capacity 截断"]
    D --> E{"tokens >= 1 ?"}
    E -->|是| F["扣减 1 个令牌"]
    F --> G["HMSET 写回新状态"]
    G --> H["放行"]
    E -->|否| I["HMSET 写回新状态"]
    I --> J["拒绝"]

为什么必须原子

  flowchart LR
    A["请求 1"] --> B["读到 tokens = 1"]
    C["请求 2"] --> D["也读到 tokens = 1"]
    B --> E["判断可放行"]
    D --> F["判断也可放行"]
    E --> G["结果：实际放过 2 个请求"]
    F --> G

所以分布式限流里，原子性不是优化项，而是正确性前提。

一个简化版 Lua 逻辑

下面这个脚本不是完整生产代码，但结构和 Redis 官方示例一致。

它特意省略了一些工程细节，只保留核心思路：

  • 默认每次请求只消费 1 个 token
  • 用离散步进的方式补充 token
  • 没处理 key 过期和状态清理
  • 没返回 retry_after 之类的等待信息
  • 所有时间参数统一使用毫秒
  • ARGV[2] 表示“每个补充周期补充多少 token”，不是“每秒补充多少”
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local tokens_per_interval = tonumber(ARGV[2])
local refill_interval_ms = tonumber(ARGV[3])
local now_ms = tonumber(ARGV[4])

local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(bucket[1])
local last_refill = tonumber(bucket[2])

if tokens == nil then
    tokens = capacity
    last_refill = now_ms
end

local time_passed_ms = now_ms - last_refill
local refills = math.floor(time_passed_ms / refill_interval_ms)

if refills > 0 then
    tokens = math.min(capacity, tokens + (refills * tokens_per_interval))
    last_refill = last_refill + (refills * refill_interval_ms)
end

local allowed = 0
if tokens >= 1 then
    tokens = tokens - 1
    allowed = 1
end

redis.call('HSET', key, 'tokens', tokens, 'last_refill', last_refill)
return {allowed, tokens}

令牌桶适合哪些 Redis 类型

令牌桶在 Redis 里通常是：

  • Hash：保存 tokens 和 last_refill
  • Lua 或 Redis Functions：保证读、算、写是原子的
  • String：只适合非常简单的状态设计

4. 用 Redis 实现漏桶

漏桶比令牌桶更容易写成两种完全不同的系统。

方案一：用单状态时间戳做“拒绝式漏桶”

如果目标是同步拒绝，不想真的排队，通常没必要把每个请求都单独存下来。

更直接的做法是维护一个“下次可服务时间”：

状态通常就是一个值：

  • next_allowed_time_ms

每次请求到来时：

  1. 读取当前 next_allowed_time
  2. 如果它早于 now，就把它拉到 now
  3. 如果当前请求要求“立即判断”，且 next_allowed_time > now，则拒绝
  4. 否则把 next_allowed_time 往后推进一个或多个 interval
  5. 返回是否放行，或者需要等待到什么时候

这个模型的特点是：

  • 优点：状态小，Lua 原子更新简单，更适合同步限流
  • 缺点：不直接保存请求明细，也不适合做真实排队

方案二：用 Sorted Set 做“积压集合模型”

如果你除了“能不能放行”之外，还想显式观察当前积压，或者要按时间管理一批待漏出的请求，可以用 Sorted Set。

状态通常是一个 Sorted Set：

  • score = 进入时间或计划出桶时间
  • member = 请求唯一 ID

每次请求到来时：

  1. 根据当前时间和漏出速率，计算理论上已经漏掉多少请求
  2. 删除已经漏掉的旧成员
  3. 看当前 ZSET 里还剩多少成员
  4. 如果剩余数量小于桶容量，就把当前请求加进去
  5. 否则拒绝

这个模型的特点是：

  • 优点：容易看出当前积压，方便按 score 清理旧元素，也能保留请求级别信息
  • 缺点：每个请求都要维护成员，内存成本更高，大流量下清理更重

方案三：用 Stream 做“排队式漏桶”

如果目标不是立刻拒绝，而是先接收、再匀速处理，那就更像一个真正的漏桶队列。

  flowchart LR
    A["请求到来"] --> B["XADD 到 Stream"]
    B --> C["Stream 中形成积压"]
    C --> D["Worker 按固定速率 XREADGROUP"]
    D --> E["匀速处理下游任务"]

这个方案的语义更接近真正的漏桶队列：

  • 天然保留顺序
  • 支持多个消费者
  • 可以管理消费进度
  • 但它也更像“流控 + 队列”

漏桶适合哪些 Redis 类型

可以直接记成：

  • 同步拒绝式：优先 String / Hash，保存 next_allowed_time，用 Lua 原子推进时间
  • 同步拒绝式但需要显式积压：可以用 Sorted Set
  • 异步排队式：优先 Stream
  • 只是简单队列：也可以用 List，但能力弱于 Stream

5. 该怎么选

如果只想做 Web API 限流，可以按这个思路判断：

  flowchart TD
    A["开始选型"] --> B{"是否允许一定突发"}
    B -->|是| C["令牌桶"]
    B -->|否| D{"是否需要排队整形"}
    D -->|是| E["漏桶"]
    D -->|否| F["也可以继续评估令牌桶或窗口类算法"]

选令牌桶

典型场景：

  • API 网关
  • 登录接口
  • 短信验证码
  • 允许一点突发的同步请求

落地方式通常是：

  • Hash 存状态
  • Lua 或 Redis Functions 做原子更新

选漏桶

典型场景：

  • 下游系统容量固定
  • 希望把流量打平
  • 请求可以排队或延迟处理

落地方式通常是：

  • 同步拒绝式：String / Hash
  • 需要显式积压时：Sorted Set
  • 异步排队式：Stream

工程上再补一句

很多系统嘴上说自己用“漏桶”，最后实现出来其实更像别的模型。判断时重点看这几件事：

  • 是否允许突发
  • 是直接拒绝还是排队
  • 状态保存的是剩余额度，还是积压请求

6. 一个实用的选型建议

默认方案

  • 对外同步 API 限流：令牌桶
  • Redis 类型：Hash
  • 并发正确性：EVAL 或 Redis Functions

如果你明确要“严格匀速，不允许突发”的同步限流，漏桶通常优先考虑：

  • String 或 Hash 保存 next_allowed_time
  • 用 Lua 原子判断和推进时间
  • 只有在你确实需要“显式积压集合”时，再考虑 Sorted Set

默认先选令牌桶，通常是因为：

  • 状态小
  • 逻辑直接
  • 允许合理突发
  • 实现和运维复杂度较低

什么时候用 Sorted Set

适合 Sorted Set 的情况：

  • 想按时间维护请求
  • 想显式知道当前积压
  • 更关注请求集合的时间序行为

什么时候用 Stream

适合 Stream 的情况：

  • 任务整形
  • 异步削峰
  • 顺序消费
  • 多 worker 平滑处理

7. 总结

可以直接记住这几条：

  • 令牌桶：控制平均速率，允许突发
  • 漏桶：平滑输出速率
  • 分布式限流的关键是原子更新
  • 令牌桶常见实现：Hash + Lua
  • 漏桶常见实现：String/Hash + Lua，或 Sorted Set / Stream
  • 默认优先从令牌桶开始

8. 参考

#Redis #限流 #分布式系统 #算法

Related posts

Table of Contents