面试重要程度：⭐⭐⭐⭐⭐

常见提问方式： "设计API限流系统" "令牌桶vs漏桶算法" "分布式限流实现"

预计阅读时间：40分钟

🎯 限流算法基础

常见限流算法

限流是保护系统稳定性的重要手段，常见算法包括：

• 固定窗口计数器：简单但有突刺问题
• 滑动窗口计数器：平滑限流，内存开销大
• 令牌桶算法：允许突发流量，平滑限流
• 漏桶算法：强制限制输出速率

🪙 令牌桶算法

令牌桶实现

/**
 * 令牌桶限流算法
 */
public class TokenBucketRateLimiter {
    
    private final int capacity;           // 桶容量
    private final double refillRate;      // 令牌补充速率（个/秒）
    private final Map<String, TokenBucket> buckets;
    
    public TokenBucketRateLimiter(int capacity, double refillRate) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.buckets = new ConcurrentHashMap<>();
    }
    
    /**
     * 令牌桶
     */
    static class TokenBucket {
        private volatile double tokens;
        private volatile long lastRefillTime;
        private final int capacity;
        private final double refillRate;
        
        public TokenBucket(int capacity, double refillRate) {
            this.capacity = capacity;
            this.refillRate = refillRate;
            this.tokens = capacity;
            this.lastRefillTime = System.currentTimeMillis();
        }
        
        public synchronized boolean tryAcquire(int tokensRequested) {
            refill();
            
            if (tokens >= tokensRequested) {
                tokens -= tokensRequested;
                return true;
            }
            
            return false;
        }
        
        private void refill() {
            long currentTime = System.currentTimeMillis();
            double timePassed = (currentTime - lastRefillTime) / 1000.0;
            
            if (timePassed > 0) {
                double tokensToAdd = timePassed * refillRate;
                tokens = Math.min(capacity, tokens + tokensToAdd);
                lastRefillTime = currentTime;
            }
        }
        
        public double getAvailableTokens() {
            refill();
            return tokens;
        }
    }
    
    /**
     * 尝试获取许可
     */
    public boolean tryAcquire(String key) {
        return tryAcquire(key, 1);
    }
    
    /**
     * 尝试获取指定数量的许可
     */
    public boolean tryAcquire(String key, int permits) {
        TokenBucket bucket = buckets.computeIfAbsent(key, 
            k -> new TokenBucket(capacity, refillRate));
        
        return bucket.tryAcquire(permits);
    }
}

🌐 分布式限流

基于Redis的分布式限流

/**
 * 基于Redis的分布式限流器
 */
@Component
public class DistributedRateLimiter {
    
    private final RedisTemplate<String, Object> redisTemplate;
    private final String keyPrefix = "rate_limiter:";
    
    public DistributedRateLimiter(RedisTemplate<String, Object> redisTemplate) {
        this.redisTemplate = redisTemplate;
    }
    
    /**
     * 固定窗口限流
     */
    public boolean tryAcquireFixedWindow(String key, int maxRequests, long windowSizeInSeconds) {
        String redisKey = keyPrefix + "fixed:" + key;
        long currentWindow = System.currentTimeMillis() / (windowSizeInSeconds * 1000);
        String windowKey = redisKey + ":" + currentWindow;
        
        // 使用Lua脚本保证原子性
        String luaScript = 
            "local current = redis.call('GET', KEYS[1]) " +
            "if current == false then " +
            "  redis.call('SET', KEYS[1], 1) " +
            "  redis.call('EXPIRE', KEYS[1], ARGV[2]) " +
            "  return 1 " +
            "else " +
            "  if tonumber(current) < tonumber(ARGV[1]) then " +
            "    return redis.call('INCR', KEYS[1]) " +
            "  else " +
            "    return -1 " +
            "  end " +
            "end";
        
        DefaultRedisScript<Long> script = new DefaultRedisScript<>(luaScript, Long.class);
        Long result = redisTemplate.execute(script, 
            Collections.singletonList(windowKey), 
            maxRequests, windowSizeInSeconds);
        
        return result != null && result != -1;
    }
    
    /**
     * 令牌桶限流
     */
    public boolean tryAcquireTokenBucket(String key, int capacity, double refillRate) {
        String redisKey = keyPrefix + "token:" + key;
        long currentTime = System.currentTimeMillis();
        
        String luaScript = 
            "local bucket = redis.call('HMGET', KEYS[1], 'tokens', 'lastRefill') " +
            "local tokens = tonumber(bucket[1]) or tonumber(ARGV[1]) " +
            "local lastRefill = tonumber(bucket[2]) or tonumber(ARGV[4]) " +
            "local timePassed = (tonumber(ARGV[4]) - lastRefill) / 1000.0 " +
            "if timePassed > 0 then " +
            "  tokens = math.min(tonumber(ARGV[1]), tokens + timePassed * tonumber(ARGV[2])) " +
            "end " +
            "if tokens >= tonumber(ARGV[3]) then " +
            "  tokens = tokens - tonumber(ARGV[3]) " +
            "  redis.call('HMSET', KEYS[1], 'tokens', tokens, 'lastRefill', ARGV[4]) " +
            "  redis.call('EXPIRE', KEYS[1], 3600) " +
            "  return 1 " +
            "else " +
            "  redis.call('HMSET', KEYS[1], 'tokens', tokens, 'lastRefill', ARGV[4]) " +
            "  redis.call('EXPIRE', KEYS[1], 3600) " +
            "  return 0 " +
            "end";
        
        DefaultRedisScript<Long> script = new DefaultRedisS