接口限流Part 3：令牌桶算法

本文基于开源项目api-rate-limiter编写

一、令牌桶算法原理

令牌桶算法是限流算法中最灵活的一种，它的核心思想是：
系统以固定速率生成令牌放入桶中，每次请求需要消耗令牌才能通过，桶满时不再添加令牌。

工作原理

令牌生成 ：系统按照固定速率（如每秒10个）向桶中添加令牌
容量限制 ：桶有最大容量，超过容量的令牌会被丢弃
令牌消费 ：每次请求消耗一个或多个令牌
流量控制 ：桶空时拒绝请求，桶满时允许突发流量

核心优势

突发流量支持 ：桶满时可以处理短时间的大量请求
平均速率控制 ：长期来看，请求速率不会超过令牌生成速率
灵活性高 ：可以根据业务需求调整令牌生成速率和桶容量

实际场景举例

假设设置：桶容量100个，生成速率10个/秒

正常情况：每秒最多处理10个请求
突发情况：可以瞬间处理100个请求，然后需要10秒恢复
长期效果：平均每秒不超过10个请求

二、Redis + Lua 实现方案

令牌桶算法需要维护每个用户的桶状态，包括当前令牌数和最后更新时间。这里采用Redis Hash + Lua脚本 的方案：

Hash结构 ：存储用户的令牌桶状态
Lua脚本 ：原子性执行令牌生成和消费
熔断机制 ：Redis不可用时降级处理

1. 核心Lua脚本

-- KEYS[1] = 用户限流key
-- ARGV[1] = 桶容量
-- ARGV[2] = 令牌生成速率（每秒）
-- ARGV[3] = 当前时间戳
-- ARGV[4] = 请求的令牌数

local user_key = KEYS[1]
local bucket_capacity = tonumber(ARGV[1])
local refill_rate_per_second = tonumber(ARGV[2])
local current_time = tonumber(ARGV[3])
local requested_tokens = tonumber(ARGV[4])

-- 步骤1：获取当前桶状态
local current_state = redis.call('HMGET', user_key, 'tokens', 'timestamp')
local last_tokens = tonumber(current_state[1])
local last_refill_time = tonumber(current_state[2])

-- 步骤2：初始化新用户桶状态
if last_tokens == nil then
    last_tokens = bucket_capacity
    last_refill_time = current_time
end

-- 步骤3：计算需要添加的令牌数量
local elapsed_time = math.max(0, current_time - last_refill_time)
local tokens_to_add = math.floor(elapsed_time * refill_rate_per_second)

-- 步骤4：更新令牌数量（不超过桶容量）
local new_tokens = math.min(last_tokens + tokens_to_add, bucket_capacity)
local new_refill_time = current_time

-- 步骤5：检查是否有足够令牌
local allowed = 0
if new_tokens >= requested_tokens then
    new_tokens = new_tokens - requested_tokens
    allowed = 1
end

-- 步骤6：保存更新后的状态
redis.call('HMSET', user_key, 'tokens', new_tokens, 'timestamp', new_refill_time)

-- 步骤7：设置过期时间（防止内存泄漏）
local expire_time = math.ceil(bucket_capacity / refill_rate_per_second) + 60
redis.call('EXPIRE', user_key, expire_time)

return allowed

脚本执行流程 ：

获取状态 ：读取当前令牌数和最后更新时间
初始化 ：新用户直接设置为满桶状态
计算增量 ：根据时间差计算需要添加的令牌数
更新令牌 ：添加令牌但不超过桶容量
消费令牌 ：检查并消费请求的令牌数
保存状态 ：更新Redis中的桶状态
设置过期 ：防止长期不活跃用户占用内存

2. Java服务层实现

@Service
@Slf4j
public class RedisRateLimiterService {

    private final RedisTemplate<String, String> redisTemplate;
    private final RedisScript<Long> redisScript;
    private final RateLimiterProperties rateLimiterProperties;

    /**
     * 检查是否允许请求
     * @param key 用户标识
     * @param requestedTokens 请求的令牌数
     * @return true-允许，false-拒绝
     */
    @CircuitBreaker(name = "redis", fallbackMethod = "fallbackIsAllowed")
    @Retry(name = "redis")
    public boolean isAllowed(String key, long requestedTokens) {
        String userKey = "rate:limiter:" + key;
        long currentTime = Instant.now().getEpochSecond();
        double refillRatePerSecond = rateLimiterProperties.getRefillRatePerMinute() / 60.0;

        Long result = redisTemplate.execute(
                redisScript,
                Collections.singletonList(userKey),
                String.valueOf(rateLimiterProperties.getBucketCapacity()),
                String.valueOf(refillRatePerSecond),
                String.valueOf(currentTime),
                String.valueOf(requestedTokens)
        );

        return result == 1L;
    }

    /**
     * 熔断器降级方法
     * Redis不可用时允许请求通过，避免服务雪崩
     */
    public boolean fallbackIsAllowed(String key, Throwable t) {
        log.error("Circuit breaker is open for key: {}. Fallback enabled due to: {}", key, t.getMessage());
        return true; // 降级时允许请求通过
    }
}

3. 配置类

@ConfigurationProperties(prefix = "rate-limiter")
@Data
public class RateLimiterProperties {
    /**
     * 桶容量
     */
    private int bucketCapacity = 100;
    
    /**
     * 令牌生成速率（每分钟）
     */
    private double refillRatePerMinute = 60.0;
    
    /**
     * 是否启用限流
     */
    private boolean enabled = true;
}

实现特点 ：

熔断保护 ：Redis不可用时自动降级
重试机制 ：网络抖动时自动重试
配置化 ：支持动态调整限流参数
监控友好 ：便于集成监控系统

三、令牌桶算法特点

核心优势

突发流量支持 ：桶满时可以处理短时间的大量请求
平均速率控制 ：长期来看，请求速率不会超过令牌生成速率
灵活性高 ：可以根据业务需求调整令牌生成速率和桶容量
平滑限流 ：避免了固定窗口的边界突刺问题

实际应用

令牌桶算法在以下场景中广泛使用：

Nginx ：limit_req 模块
Guava ：RateLimiter 类
Spring Cloud Gateway ：默认限流算法

最佳实践

参数调优 ：
- 桶容量 = 突发流量需求
- 生成速率 = 平均处理能力
- 过期时间 = 桶容量 / 生成速率 + 缓冲时间
监控指标 ：
- 限流触发频率
- 令牌消耗速率
- Redis连接状态
降级策略 ：
- Redis不可用时允许通过
- 监控告警及时处理
- 定期清理过期数据