限流算法详解：令牌桶、滑动窗口与实现

public class FixedWindowRateLimiter {
    private final int maxRequests;
    private final long windowSizeMs;
    private long windowStart;
    private int counter;

    public FixedWindowRateLimiter(int maxRequests, long windowSizeMs) {
        this.maxRequests = maxRequests;
        this.windowSizeMs = windowSizeMs;
        this.windowStart = System.currentTimeMillis();
        this.counter = 0;
    }

    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();

        // 进入新窗口，重置计数器
        if (now - windowStart >= windowSizeMs) {
            windowStart = now;
            counter = 0;
        }

        if (counter < maxRequests) {
            counter++;
            return true;
        }
        return false;
    }
}

public class SlidingWindowRateLimiter {
    private final int maxRequests;
    private final long windowSizeMs;
    private final int bucketCount;
    private final long bucketSizeMs;
    private final int[] buckets;
    private long lastBucketTime;
    private int lastBucketIndex;

    public SlidingWindowRateLimiter(int maxRequests, long windowSizeMs, int bucketCount) {
        this.maxRequests = maxRequests;
        this.windowSizeMs = windowSizeMs;
        this.bucketCount = bucketCount;
        this.bucketSizeMs = windowSizeMs / bucketCount;
        this.buckets = new int[bucketCount];
        this.lastBucketTime = System.currentTimeMillis();
        this.lastBucketIndex = 0;
    }

    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        advanceWindow(now);

        int totalCount = 0;
        for (int count : buckets) {
            totalCount += count;
        }

        if (totalCount < maxRequests) {
            buckets[lastBucketIndex]++;
            return true;
        }
        return false;
    }

    private void advanceWindow(long now) {
        long elapsed = now - lastBucketTime;
        int bucketsToAdvance = (int) (elapsed / bucketSizeMs);

        if (bucketsToAdvance > 0) {
            for (int i = 0; i < Math.min(bucketsToAdvance, bucketCount); i++) {
                lastBucketIndex = (lastBucketIndex + 1) % bucketCount;
                buckets[lastBucketIndex] = 0;
            }
            lastBucketTime += bucketsToAdvance * bucketSizeMs;
        }
    }
}

public class RedisSlidingWindowLimiter {
    private final RedisTemplate<String, String> redis;
    private final int maxRequests;
    private final long windowSizeMs;

    public boolean tryAcquire(String key) {
        long now = System.currentTimeMillis();
        String member = now + ":" + UUID.randomUUID();

        String redisKey = "rate_limit:" + key;

        // 使用 Lua 脚本保证原子性
        String luaScript = """
            -- 移除窗口外的旧请求
            redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, ARGV[1])
            -- 统计窗口内的请求数
            local count = redis.call('ZCARD', KEYS[1])
            if count < tonumber(ARGV[2]) then
                -- 未超限，添加新请求
                redis.call('ZADD', KEYS[1], ARGV[3], ARGV[4])
                redis.call('PEXPIRE', KEYS[1], ARGV[5])
                return 1
            end
            return 0
            """;

        Long result = redis.execute(
            new DefaultRedisScript<>(luaScript, Long.class),
            List.of(redisKey),
            String.valueOf(now - windowSizeMs),   // 窗口起始时间
            String.valueOf(maxRequests),           // 最大请求数
            String.valueOf(now),                   // 当前时间作为 score
            member,                                // 唯一成员
            String.valueOf(windowSizeMs)           // TTL
        );

        return result != null && result == 1;
    }
}

public class TokenBucketRateLimiter {
    private final double maxTokens;      // 桶容量
    private final double refillRate;     // 令牌填充速率(个/秒)
    private double currentTokens;        // 当前令牌数
    private long lastRefillTime;         // 上次填充时间

    public TokenBucketRateLimiter(double maxTokens, double refillRate) {
        this.maxTokens = maxTokens;
        this.refillRate = refillRate;
        this.currentTokens = maxTokens;
        this.lastRefillTime = System.nanoTime();
    }

    public synchronized boolean tryAcquire() {
        return tryAcquire(1);
    }

    public synchronized boolean tryAcquire(int tokens) {
        refill();
        if (currentTokens >= tokens) {
            currentTokens -= tokens;
            return true;
        }
        return false;
    }

    private void refill() {
        long now = System.nanoTime();
        double elapsed = (now - lastRefillTime) / 1_000_000_000.0;
        double tokensToAdd = elapsed * refillRate;
        currentTokens = Math.min(maxTokens, currentTokens + tokensToAdd);
        lastRefillTime = now;
    }
}

public class LeakyBucketRateLimiter {
    private final int capacity;      // 桶容量
    private final double leakRate;   // 漏出速率(个/秒)
    private double water;            // 当前水量
    private long lastLeakTime;       // 上次漏水时间

    public LeakyBucketRateLimiter(int capacity, double leakRate) {
        this.capacity = capacity;
        this.leakRate = leakRate;
        this.water = 0;
        this.lastLeakTime = System.nanoTime();
    }

    public synchronized boolean tryAcquire() {
        leak();

        if (water < capacity) {
            water++;
            return true;
        }
        return false; // 桶满，拒绝
    }

    private void leak() {
        long now = System.nanoTime();
        double elapsed = (now - lastLeakTime) / 1_000_000_000.0;
        double leaked = elapsed * leakRate;
        water = Math.max(0, water - leaked);
        lastLeakTime = now;
    }
}