令牌桶算法限流实现

令牌桶算法限流实现：程序员面试高频考点详解

📚 2025年Java面试宝典抢先领：
🔗 链接 提取码: 9b3g
（涵盖分布式系统、高并发设计等核心场景）

---

什么是令牌桶算法？

想象一个水桶：管理员以固定速率往桶里扔令牌（token），桶有最大容量。当请求到来时，只有拿到令牌才能放行，否则被限流。这种令牌桶算法能应对突发流量，是面试官最爱问的限流实现方案之一。

---

令牌桶算法的工作原理

1. 令牌生成
   系统以恒定速率（如每秒10个）向桶内添加令牌，直到达到桶容量上限。
   

2. 请求处理

   • 请求到达时，从桶中取出1个令牌 → 立即放行
   • 若桶中无令牌 → 触发限流（拒绝或排队）

3. 突发流量应对
   当桶中有积攒的令牌时，允许短时间内处理超过基准速率的请求，这是令牌桶算法相比固定窗口算法的核心优势。

---

令牌桶算法的应用场景

graph LR
A[网关层限流] --> B[微服务API调用]
C[秒杀系统库存扣减] --> D[数据库访问保护]

实际案例：某电商大促期间，商品详情页接口通过令牌桶算法将QPS控制在5000，避免下游服务雪崩。

---

实现令牌桶算法的关键步骤

1. 初始化参数

   • 桶容量 capacity
   • 令牌填充速率 rate（个/秒）
   • 当前令牌数 tokens
   • 上次填充时间 lastRefillTime

2. 请求处理逻辑

   def handle_request():
       refill_tokens()  # 先补充令牌
       if tokens > 0:
           tokens -= 1
           process_request()  # 处理请求
       else:
           reject_request()  # 触发限流
   

3. 令牌补充算法

   def refill_tokens():
       now = time.now()
       # 计算距离上次补充过了多少令牌
       new_tokens = (now - lastRefillTime) * rate  
       tokens = min(capacity, tokens + new_tokens)
       lastRefillTime = now
   

---

对比漏桶算法

| 特性 | 令牌桶算法 | 漏桶算法 | |--------------|--------------------------|-----------------------| | 流速控制 | 控制平均速率+允许突发 | 严格固定速率 | | 实现复杂度| 需定时补充令牌 | 简单队列 | | 适用场景 | 需要应对突发流量 | 需绝对平滑流量 |

---

面试实战技巧

当被问到“如何设计高并发系统的限流？”时，建议回答框架：

1. 先说明令牌桶算法适用场景（需允许合理突发）
2. 手绘桶模型并解释填充/消耗逻辑
3. 强调关键参数：rate和capacity的设定依据
4. 补充对比漏桶算法（加分项）
5. 提分布式场景下的实现方案（Redis + Lua脚本）

💡 面试福利：通过面试鸭返利网开通会员可返利25元！海量令牌桶算法真题解析和系统设计案例等你解锁。

---

延伸思考：当集群需要全局限流时，如何改造单机令牌桶算法？ 欢迎在面试鸭返利社区参与讨论～