API 限流算法详解：令牌桶、漏桶、滑动窗口

限流是保护 API 的重要手段。本文介绍三种限流算法。

1. 令牌桶

固定速率往桶里放令牌，请求需要消耗令牌。

public class TokenBucket {
    private final int capacity;
    private final int rate;
    private int tokens;
    private long lastRefillTime;
    
    public synchronized boolean tryAcquire() {
        refill();
        if (tokens > 0) {
            tokens--;
            return true;
        }
        return false;
    }
    
    private void refill() {
        long now = System.currentTimeMillis();
        int newTokens = (int) ((now - lastRefillTime) / 1000 * rate);
        tokens = Math.min(capacity, tokens + newTokens);
        lastRefillTime = now;
    }
}

2. 漏桶

请求进入漏桶，以固定速率流出。

public class LeakyBucket {
    private final int capacity;
    private final int rate;
    private int water;
    private long lastLeakTime;
    
    public synchronized boolean tryAcquire() {
        leak();
        if (water < capacity) {
            water++;
            return true;
        }
        return false;
    }
    
    private void leak() {
        long now = System.currentTimeMillis();
        int leaked = (int) ((now - lastLeakTime) / 1000 * rate);
        water = Math.max(0, water - leaked);
        lastLeakTime = now;
    }
}

3. 滑动窗口

在时间窗口内限制请求数量。

public class SlidingWindow {
    private final int limit;
    private final long windowSize;
    private final Queue<Long> timestamps = new LinkedList<>();
    
    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        
        // 移除过期的请求
        while (!timestamps.isEmpty() && timestamps.peek() < now - windowSize) {
            timestamps.poll();
        }
        
        if (timestamps.size() < limit) {
            timestamps.offer(now);
            return true;
        }
        return false;
    }
}

算法对比

Spring Boot 实现

@Component
public class RateLimitInterceptor implements HandlerInterceptor {
    private final TokenBucket bucket = new TokenBucket(100, 10);
    
    @Override
    public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler) {
        if (!bucket.tryAcquire()) {
            response.setStatus(429);
            return false;
        }
        return true;
    }
}

总结

限流是保护 API 的重要手段。根据场景选择合适的算法，防止服务被过载。