令牌桶算法(Token Bucket)

令牌桶算法(Token Bucket)是一种用于流量控制和限流的经典算法。系统按恒定速率向一个容量固定的桶中投放令牌,每个请求在被处理前必须从桶中取走一个令牌;桶空时请求被限流或排队。它的特点是既能约束长期平均速率,又能容忍短时的突发流量。

概述

限流是保护后端服务不被过载的重要手段。令牌桶与漏桶是两种最常见的限流模型。漏桶以恒定速率流出,强制平滑流量;而令牌桶允许桶中积累令牌,当短时间来了一批请求时,可以一次性消耗积攒的令牌,从而支持突发,更贴合互联网流量忽高忽低的特性。

核心原理

• 桶有固定容量,系统以稳定速率往桶里添加令牌,桶满则多余令牌被丢弃。
• 每个到来的请求需要从桶中取出一定数量的令牌,取到则放行。
• 若桶中令牌不足,请求被拒绝、排队或降级处理。
• 令牌的积累使得桶中最多能积攒到桶容量个令牌,这决定了允许的最大突发量。

令牌桶的平均放行速率由令牌投放速率决定,而瞬时突发能力由桶容量决定,两者可独立配置,灵活性较高。

应用场景

• API 网关和微服务接口的调用频率限制。
• 网络设备的流量整形与带宽控制。
• 消息推送、短信发送等对速率有约束的业务。
• 限制单个用户或 IP 的访问速率,防止刷接口和恶意攻击。

常见问题

问:令牌桶和漏桶有什么区别?答:漏桶强制以固定速率处理请求,输出平滑但不允许突发;令牌桶允许令牌积累,可在短时间内放行一批请求,支持突发流量,同时保证长期平均速率不超限。

问:令牌桶如何在分布式环境中实现?答:单机可用内存计数实现,分布式场景常借助 Redis 存储令牌数量并用原子操作或 Lua 脚本保证并发安全,让多个服务实例共享同一份限流状态。