令牌桶 vs 漏桶：深入解析流量控制的核心算法
鹿Sir约 4 分钟鹿Sir上线，见字如面。
在当今高并发的互联网环境中，流量控制是系统设计中不可或缺的一环。
本文将深入探讨两种经典的限流算法——令牌桶和漏桶，分析它们的核心原理、适用场景和实现方式，助你在系统设计中做出更明智的选择。
0x1. 核心概念对比
令牌桶算法
核心思想：系统维护一个固定容量的令牌桶，以固定速率向桶中添加令牌。当请求到达时，需要从桶中获取令牌才能被处理，若无可用令牌则请求被拒绝或等待。
类比理解：如同火车站售票系统，售票窗口定期放出固定数量的车票（令牌），乘客（请求）需要先购票才能进站乘车，票售罄时需等待下一批放票。
- ✅ 突发流量处理：桶内积累的令牌可应对短时流量高峰
- ✅ 实现简单：算法逻辑清晰，易于实现
- ✅ 内存高效：仅需维护令牌计数和最后更新时间
漏桶算法
核心思想：请求像水一样流入固定容量的漏桶中，桶以恒定速率"漏水"（处理请求），当桶满时新请求将被丢弃或排队。
类比理解：如同一个底部有固定大小孔洞的水桶，无论上方注水速度如何变化，出水速度始终保持恒定。
关键特性：
- ✅ 输出平滑：严格保证请求处理速率稳定
- ✅ 下游保护：有效防止下游系统过载
- ❌ 突发限制：无法利用系统空闲时的处理能力储备
- ❌ 潜在延迟：请求可能需要排队等待处理
0x2. 算法实现详解
令牌桶实现
public class TokenBucket {private final long capacity; // 桶容量private final long refillRate; // 令牌补充速率（个/秒）private AtomicLong tokens; // 当前令牌数private volatile long lastRefillTime; // 最后补充时间publicTokenBucket(long capacity, long refillRate) {this.capacity = capacity;this.refillRate = refillRate;this.tokens = new AtomicLong(capacity);this.lastRefillTime = System.currentTimeMillis();}public boolean tryAcquire() {refillTokens();long currentTokens = tokens.get();while (currentTokens > 0) {if (tokens.compareAndSet(currentTokens, currentTokens - 1)) {return true;}currentTokens = tokens.get();}return false;}privatevoidrefillTokens() {long now = System.currentTimeMillis();long elapsedTime = now - lastRefillTime;if (elapsedTime > 1000) {long newTokens = elapsedTime * refillRate/ 1000;if (newTokens > 0) {lastRefillTime = now;tokens.updateAndGet(current -> Math.min(capacity, current + newTokens));}}}}
漏桶实现
public class LeakyBucket {private final long capacity; // 桶容量private final long leakRate; // 漏水速率（个/秒）private AtomicLong waterLevel; // 当前水量private volatile long lastLeakTime; // 最后漏水时间public LeakyBucket(long capacity, long leakRate){this.capacity = capacity;this.leakRate = leakRate;this.waterLevel = new AtomicLong(0);this.lastLeakTime = System.currentTimeMillis();}public boolean tryConsume() {leakWater();long currentLevel = waterLevel.get();if (currentLevel >= capacity) {return false;}waterLevel.incrementAndGet();return true;}private void leakWater() {long now = System.currentTimeMillis();long elapsedTime = now - lastLeakTime;if (elapsedTime > 0) {long leaked = elapsedTime * leakRate / 1000;if (leaked > 0) {lastLeakTime = now;waterLevel.updateAndGet(current -> Math.max(0, current - leaked));}}}}
0x3. 应用场景
令牌桶适用场景：
- API限流保护：保护业务系统或敏感接口免受过载
- 突发流量应对：如秒杀系统的流量控制
- 防御恶意攻击：抵御DDoS等攻击行为
- 客户端限流：控制对第三方服务的调用频率
漏桶适用场景：
- 数据库保护：防止数据库连接被突发请求冲垮
- 消息队列消费：确保消费者处理速率稳定
- 支付系统：保证支付处理的稳定性和顺序性
- 数据导出：控制大数据量导出的处理速度
0x4. 面试深度问答
Q1：在微服务架构中，如何选择这两种算法？
A：需要考虑服务间的依赖关系。对于入口服务或面向用户的API，令牌桶更合适，因为它能更好地处理用户行为的突发性；对于下游关键服务（如支付核心），漏桶能提供更稳定的保护。
Q2：分布式环境下如何实现这些算法？
A：可采用Redis+Lua脚本实现分布式限流，保证原子性。也可考虑：
- 使用一致性哈希将请求路由到特定节点
- 采用中间件如Sentinel、Nginx限流模块
- 基于分布式协调服务（如Zookeeper）协调速率
Q3：如何动态调整桶参数？
A：可设计自适应限流策略：
- 监控系统负载（CPU、队列长度等）
- 根据健康指标动态调整rate和capacity
- 结合熔断机制（如Hystrix）实现多级保护
Q4：算法的时间复杂度如何？
A：两种算法的基本操作都是O(1)复杂度，因为主要涉及简单的原子操作和时间计算，这使得它们非常适合高性能场景。
0x5. 进阶思考
在实际生产环境中，我们往往需要结合两种算法的优势。例如：
- 分层限流：在API网关使用令牌桶控制整体流量，在服务内部使用漏桶保护关键资源
- 混合模式：实现可配置的算法切换，根据业务场景动态选择
- 机器学习：基于历史流量模式预测最佳参数，实现智能限流
鹿Sir提一杯：
令牌桶和漏桶算法各有千秋，没有绝对的"最优解"。
令牌桶更灵活，适合处理突发；漏桶更稳定，适合保护关键资源。理解它们的本质差异和适用场景，才能在实际系统设计中做出合理选择。
令牌桶像ATM机——有钱就能取；漏桶像水龙头——流速恒定不变。
根据业务需求选择合适的"管道"，才能构建出既稳健又高效的系统。
EOF
作者：鹿Sir「微信：Jensvn」
分享架构技术/IT资讯/牛马日常
高级架构师，多年SaaS/电商/AI产研经历
DDD极客/DDD4j开源框架作者
→关注公众号，撩小码鹿「已接入AI」
→加我备注“进群”，进技术大佬群学习