接口限频算法：漏桶算法、令牌桶算法、滑动窗口算法

限频三大算法对比与选型建议

一、漏桶算法（Leaky Bucket Algorithm）

1.核心原理

漏桶算法的核心是恒定速率输出，无论输入流量如何波动，输出始终保持稳定。其工作机制可类比为一个底部有固定孔径的水桶：

• 输入：请求以任意速率流入桶中（如突发流量）。
• 输出：桶以固定速率（如100请求/秒）处理请求，超出桶容量的请求直接丢弃。

2.实现

• 实现：使用队列存储请求，通过定时任务以固定速率从队列中取出请求处理。若队列满则拒绝新请求。

在非单节点场景下，可使用消息队列中间件，或者Redis模拟队列，来实现这个算法。

3.为什么要限制漏桶容量

有容量限制 vs 无容量限制：对比分析

4.优缺点分析

• 优点：
  • 绝对平滑：严格控制输出速率，适合对稳定性要求极高的场景（如金融交易接口）。
  • 实现简单：只需维护队列和固定速率处理器，无需复杂逻辑。
• 缺点
  • 资源浪费：突发流量会被直接丢弃，无法利用系统空闲资源。
  • 灵活性差：无法区分请求优先级，所有超额请求同等处理。

二、令牌桶算法（Token Bucket Algorithm）

1.核心原理

令牌桶算法通过令牌生成与消耗实现限流，允许一定程度的突发流量：

• 令牌生成：系统以固定速率（如100令牌/秒）向桶中添加令牌，桶容量上限为burst_size（如200令牌）。
• 请求处理：每个请求需消耗一个令牌，无令牌则拒绝。若桶满，新生成的令牌会被丢弃。

2.实现

（1）单机实现

Guava的RateLimiter采用令牌桶算法，支持动态调整速率和突发容量。

RateLimiter rateLimiter = RateLimiter.create(100.0); // 每秒生成100令牌
if (rateLimiter.tryAcquire()) { // 尝试获取令牌
    // 处理请求
} else {
    // 限流
}

（2）分布式实现

在分布式系统中，可以利用 Redis 的原子操作和 Lua 脚本来实现一个线程安全的令牌桶。

• 使用 Redis 实现令牌桶的关键在于：
  • 使用原子操作保证令牌增减的线程安全
  • 实现令牌的自动生成逻辑
  • 高效地判断是否允许请求通过

3.优缺点分析

• 优点：
  • 支持突发流量：允许短时间内消耗桶内累积的令牌，提升资源利用率（如电商秒杀）。
  • 参数灵活：可通过调整rate（平均速率）和burst_size（突发容量）平衡平滑性与突发性。
• 缺点：
  • 实现复杂度较高：需维护令牌生成、存储和消耗逻辑。
  • 流量尖刺风险：突发流量可能瞬间耗尽令牌，导致后续请求被拒绝。

三、滑动窗口算法（Sliding Window Algorithm）

1.核心原理

滑动窗口算法通过时间窗口划分与计数实现限流，精度随窗口细分而提升：

• 窗口划分：将时间轴划分为多个固定长度的子窗口（如1秒划分为10个0.1秒的子窗口）。
• 计数与滑动：统计当前窗口内的请求数，当窗口滑动时，旧子窗口的计数逐渐过期。

2.实现

在分布式系统中，可以利用 Redis 的原子操作和 Lua 脚本来实现一个这个算法。

3.优缺点分析

• 优点：
  • 时间敏感性强：可精确控制时间维度的请求频率（如“每分钟最多100次”）。
  • 动态调整窗口：支持秒级、分钟级等不同粒度的限流规则。
• 缺点：
  • 临界问题：窗口切换时可能出现双倍请求（如0.9秒和1.1秒各发100次）。
  • 分布式同步成本：需依赖Redis等分布式缓存，引入额外延迟。