在高并发系统中，限流（Rate Limiting）是保护服务稳定性的核心手段。它控制单位时间内请求的数量，防止系统过载。本文介绍两种常见但用途不同的限流策略：Count-Min Sketch（CMS） 和 Redis 令牌桶（Token Bucket）。
Count-Min Sketch（CMS）
是什么
Count-Min Sketch 是一种概率型数据结构，用于在数据流中估计元素的频率。它不是严格意义上的"限流算法"，而是限流系统中的频率统计组件——你用它来快速判断"某个 key 在过去一段时间内出现了多少次"。
核心原理
CMS 由一个 d × w 的二维数组（矩阵）和 d 个独立的哈希函数组成：
哈希函数 h1, h2, ..., hd
┌─────────────────────────┐
│ w 列 │
┌────┼─────────────────────────┤
│ h1 │ 0 3 0 1 0 2 │
d 行│ h2 │ 1 0 2 0 3 0 │
│ h3 │ 0 2 0 0 1 1 │
└────┼─────────────────────────┤
└─────────────────────────┘
写入：对一个元素 x，用每个哈希函数计算出一个列索引，将对应位置的计数器 +1。
查询：取所有哈希函数映射位置的计数值的最小值，作为 x 的频率估计。
// 伪代码
function estimate(key: string): number {
let min = Infinity;
for (let i = 0; i < d; i++) {
const col = hashFunctions[i](key) % w;
min = Math.min(min, counters[i][col]);
}
return min;
}
为什么用 CMS 做限流
在限流场景中，你需要回答一个问题："这个 IP / 用户 / API key 在最近 N 秒内请求了多少次？"
传统做法是用一个 Map<string, number> 维护精确计数，但当 key 空间非常大（百万级 IP）时，内存开销巨大。CMS 的优势在于：
- 固定内存：无论 key 多少，内存用量 =
d × w × 4 bytes - O(d) 查询：每次查询只需
d次哈希 +d次读取，通常d = 4~6 - 只高估不低估：CMS 的估计值 ≥ 真实值（单侧误差），用于限流时偏向"宁可多拦，不可漏放"
使用场景
- DDoS 防护：在网关层统计每个源 IP 的请求频率，快速识别异常流量
- API 限流：对 API key 进行频率估计，配合阈值决定是否拒绝
- 热 key 检测：在缓存层识别高频访问的 key，提前做降级或分片
Pros & Cons
| 优点 | 缺点 |
|---|---|
| 内存占用极低，适合大规模 key 空间 | 只能估计频率，无法精确计数 |
| 查询和更新都是 O(d)，速度极快 | 存在高估误差（false positive） |
| 支持并发写入，天然适合流式场景 | 无法做"滑动窗口"，需要配合时间分片 |
| 可以持久化到 Redis（RedisBloom 模块） | 不支持删除操作（Counting CMS 变体可以） |
实际使用
Redis 通过 RedisBloom 模块原生支持 CMS：
# 初始化：4 个哈希函数，宽度 1000
CMS.INITBYDIM rate_cms 1000 4
# 记录请求
CMS.INCRBY rate_cms "192.168.1.1" 1
# 查询频率
CMS.QUERY rate_cms "192.168.1.1"
Redis 令牌桶（Token Bucket）
是什么
令牌桶是一种流量整形算法，它允许一定程度的突发流量，同时维持长期的平均速率。这是它和固定窗口、滑动窗口计数器的核心区别。
核心原理
想象一个桶，以固定速率往里面放令牌：
┌──── 固定速率 r (tokens/sec) ────┐
│ │
▼ │
┌─────────┐ ┌────┴────┐
│ 令牌桶 │ ◄── 桶容量 C (burst) │ 请求到达 │
│ (C 个) │ └────┬────┘
└────┬────┘ │
│ │
▼ ▼
┌─────────┐ ┌─────────┐
│ 消耗令牌 │ ── 有令牌 → 放行 ──► │ 处理请求 │
│ 无令牌 │ ── 拒绝 ──────────► │ 返回 429│
└─────────┘ └─────────┘
- 桶容量 C（burst）：桶里最多能装多少令牌，决定了突发流量的上限
- 填充速率 r：每秒往桶里放多少令牌，决定了长期平均速率
- 请求消耗：每个请求消耗 1 个令牌；桶空则拒绝
算法实现（Lua 脚本）
在 Redis 中，令牌桶通常用 Lua 脚本保证原子性：
-- KEYS[1] = 令牌桶 key
-- ARGV[1] = 桶容量 (burst)
-- ARGV[2] = 填充速率 (tokens/sec)
-- ARGV[3] = 当前时间戳 (秒)
-- ARGV[4] = 请求消耗的令牌数
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])
-- 获取上次的状态
local last_time = tonumber(redis.call('HGET', key, 'last_time') or now)
local tokens = tonumber(redis.call('HGET', key, 'tokens') or capacity)
-- 计算时间差，填充令牌
local elapsed = now - last_time
local new_tokens = math.min(capacity, tokens + elapsed * rate)
-- 判断是否放行
if new_tokens >= requested then
new_tokens = new_tokens - requested
redis.call('HSET', key, 'tokens', new_tokens, 'last_time', now)
redis.call('EXPIRE', key, math.ceil(capacity / rate) * 2)
return 1 -- 允许
else
redis.call('HSET', key, 'tokens', new_tokens, 'last_time', now)
redis.call('EXPIRE', key, math.ceil(capacity / rate) * 2)
return 0 -- 拒绝
end
为什么用令牌桶
令牌桶的核心优势是允许突发。假设配置为 10 req/s，桶容量 20：
- 用户安静了 2 秒 → 桶里攒了 20 个令牌 → 瞬间可以发 20 个请求
- 用户持续高频率 → 维持在 10 req/s 的平均速率
这比固定窗口（窗口边界处可能允许 2x 突发）和滑动窗口（过于平滑，不允许任何突发）更符合真实业务场景。
使用场景
- API Gateway：对不同租户/套餐设置不同的速率和突发上限
- 用户行为限流：发帖、评论、登录等操作，允许偶尔快一点，但长期控制速率
- 微服务调用：下游服务限流，保护数据库或第三方 API
- 消息队列削峰：控制消费者速率，平滑流量
Pros & Cons
| 优点 | 缺点 |
|---|---|
| 允许突发流量，用户体验更好 | 需要维护状态（last_time + tokens），有存储开销 |
| 长期速率精确可控 | 单 key 的 Lua 脚本是串行的，超高并发下可能成为瓶颈 |
| Redis 原子脚本保证一致性 | 时间漂移问题：多实例时钟不一致可能导致误差 |
| 参数直观：速率 + 突发容量 | 不适合需要精确计数的场景（如按次计费） |
| 可以为不同用户设置不同参数 | 冷启动时桶是满的，可能瞬间放过大量请求 |
对比总结
| 维度 | Count-Min Sketch | Redis 令牌桶 |
|---|---|---|
| 本质 | 频率估算数据结构 | 流量整形算法 |
| 精度 | 概率估算，有误差 | 精确控制 |
| 内存 | 极低（固定矩阵） | 每 key 两个字段 |
| 突发处理 | 不涉及（只统计） | 天然支持 |
| 适用规模 | 百万级 key | 万级 key（受 Redis 内存限制） |
| 典型搭配 | CMS 统计 → 阈值判断 → 触发限流 | 直接作为限流决策器 |
| 分布式 | RedisBloom 模块 | Redis + Lua 脚本 |
如何选择
- 需要统计海量 key 的频率（如 IP 级别 DDoS 检测） → Count-Min Sketch
- 需要精确控制用户/租户的请求速率 → 令牌桶
- 两者结合：CMS 做第一层粗筛（快速识别异常），令牌桶做第二层精细控制
在实际系统中，它们经常一起出现：CMS 在网关层快速统计，判断是否超过阈值；令牌桶在业务层精细控制每个用户的请求节奏。理解各自的特点，才能在正确的场景用对工具。