面试基础-高并发高可用架构深度实践限流算法令牌桶-vs-漏桶设计与实现
目录
面试基础—高并发高可用架构深度实践：限流算法（令牌桶 vs 漏桶）设计与实现
高并发高可用架构深度实践：限流算法（令牌桶 vs 漏桶）设计与实现
引言：从双十一洪峰看限流的重要性
在2023年阿里双十一购物节中，核心交易系统成功支撑了每秒58.3万笔的订单创建峰值。在这背后，限流算法作为系统稳定的最后一道防线，发挥了关键作用。本文将深入探讨令牌桶与漏桶算法，结合Sentinel源码解析，揭示高并发场景下的限流实现细节。
一、限流算法核心原理
1.1 令牌桶算法
1.1.1 算法原理
- 以恒定速率向桶中添加令牌
- 请求到达时消耗令牌
- 无令牌时拒绝请求
令牌生产者
令牌桶
请求消费者
添加令牌
loop
[恒定速率]
请求令牌
允许通过
拒绝请求
alt
[有可用令牌]
[无可用令牌]
令牌生产者
令牌桶
请求消费者
1.1.2 生产级实现
public class TokenBucket {
private final AtomicLong tokens;
private final long capacity;
private final long refillRate; // 令牌/秒
private volatile long lastRefillTime;
public boolean tryAcquire(int permits) {
refillTokens();
long currentTokens = tokens.get();
if (currentTokens < permits) {
return false;
}
return tokens.compareAndSet(currentTokens, currentTokens - permits);
}
private void refillTokens() {
long now = System.nanoTime();
long duration = now - lastRefillTime;
long newTokens = duration * refillRate / 1_000_000_000;
if (newTokens > 0) {
lastRefillTime = now;
tokens.updateAndGet(current -> Math.min(capacity, current + newTokens));
}
}
}1.2 漏桶算法
1.2.1 算法原理
- 请求以任意速率进入漏桶
- 以恒定速率处理请求
- 桶满时拒绝请求
请求生产者
漏桶
请求处理器
提交请求
接受请求
拒绝请求
alt
[桶未满]
[桶已满]
处理请求
loop
[恒定速率]
请求生产者
漏桶
请求处理器
1.2.2 生产级实现
public class LeakyBucket {
private final BlockingQueue<Request> queue;
private final int capacity;
private final long processRate; // 请求/秒
public boolean tryEnqueue(Request request) {
return queue.offer(request);
}
@SuppressWarnings("InfiniteLoopStatement")
public void startProcessing() {
ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(1);
scheduler.scheduleAtFixedRate(() -> {
Request request = queue.poll();
if (request != null) {
process(request);
}
}, 0, 1_000_000_000 / processRate, TimeUnit.NANOSECONDS);
}
}二、生产环境应用实践
2.1 淘宝交易系统限流方案
挑战 ：
- 瞬时峰值流量可能超过系统容量10倍
- 需要区分核心业务和非核心业务
解决方案 ：
- 采用分层限流架构
- 网关层：漏桶算法控制全局流量
- 服务层：令牌桶算法保护核心业务
- 动态限流策略
- 基于CPU、RT等指标动态调整限流阈值
- 核心业务预留20%冗余容量
漏桶限流
令牌桶限流
令牌桶限流
用户请求
API网关
交易服务
库存服务
支付服务
2.2 Sentinel源码解析
以Sentinel的
FlowSlot
为例：
public class FlowSlot extends AbstractLinkedProcessorSlot<DefaultNode> {
@Override
public void entry(Context context, ResourceWrapper resourceWrapper, DefaultNode node,
int count, boolean prioritized, Object... args) throws Throwable {
// 执行限流检查
if (!flowRuleChecker.checkFlow(resourceWrapper, context, node, count, prioritized)) {
throw new FlowException(resourceWrapper.getName(), "flow limited");
}
// 调用后续处理器
fireEntry(context, resourceWrapper, node, count, prioritized, args);
}
}三、算法对比与选型指南
| 维度 | 令牌桶算法 | 漏桶算法 |
|---|---|---|
| 流量特性 | 允许突发流量 | 平滑输出流量 |
| 实现复杂度 | 中等 | 简单 |
| 适用场景 | 需要应对突发流量的场景 | 需要严格控制处理速率的场景 |
| 典型应用 | API网关、服务接口限流 | 消息队列消费速率控制 |
选型建议 ：
- 网关层优先选择漏桶算法
- 服务层优先选择令牌桶算法
- 混合使用实现分层限流
四、大厂面试深度追问
4.1 基础问题
- 令牌桶和漏桶算法的核心区别是什么？
- 如何实现分布式限流？
- 限流算法的时间复杂度是多少？
4.2 进阶问题
- 如何设计支持动态调整速率的限流算法？
- 限流算法在微服务架构中如何应用？
- 如何评估限流算法对系统性能的影响？
4.3 实战问题
- 在双十一场景下，如何设计限流策略？
- 如何处理限流导致的请求失败？
- 如何监控和优化限流效果？
五、未来演进方向
- AI驱动限流 ：基于机器学习预测流量模式
- 边缘计算限流 ：在CDN边缘节点实现限流
- 自适应限流 ：根据系统负载动态调整限流策略
- 跨云限流 ：支持多云环境统一限流策略
通过持续优化，我们正在构建支撑千万级TPS、EB级数据量的新一代限流体系，为阿里云和字节跳动的全球化业务提供坚实保障。