一口气说出Redis实现5种限流算法，面试稳了

使用Redis实现限流是一种常见的做法，尤其是在分布式系统中。Redis的高性能和丰富的命令集使其非常适合于实现各种限流算法。下面介绍几种常见的限流算法及其在Redis中的实现：

1. 固定窗口限流

原理：

将时间分成固定长度的窗口，并在每个窗口内统计请求次数。如果请求次数超过限制，则进行限流。

实现：

假设我们限制每分钟最多10次请求，可以使用Redis的INCR命令和EXPIRE命令来实现。

import redis.clients.jedis.Jedis;

public class FixedWindowRateLimiter {
    private static final String REDIS_HOST = "localhost";
    private static final int REDIS_PORT = 6379;
    private static final int MAX_REQUESTS = 10;
    private static final int WINDOW_SIZE_IN_SECONDS = 60;

    private Jedis jedis;

    public FixedWindowRateLimiter() {
        this.jedis = new Jedis(REDIS_HOST, REDIS_PORT);
    }

    public boolean isAllowed(String userId) {
        String key = "rate:limiter:" + userId;
        long currentCount = jedis.incr(key);
        if (currentCount == 1) {
            // 第一次请求，需要设置过期时间
            jedis.expire(key, WINDOW_SIZE_IN_SECONDS);
        }
        return currentCount <= MAX_REQUESTS;
    }

    public static void main(String[] args) {
        FixedWindowRateLimiter rateLimiter = new FixedWindowRateLimiter();
        String userId = "user123";
        for (int i = 0; i < 12; i++) {
            boolean allowed = rateLimiter.isAllowed(userId);
            System.out.println("Request " + (i + 1) + ": " + (allowed ? "Allowed" : "Blocked"));
        }
    }
}

2. 滑动窗口限流

原理：

使用更细粒度的时间窗口来实现限流，更加精确地统计请求次数。

实现：

使用Redis的ZSET（有序集合）来存储请求的时间戳。

import redis.clients.jedis.Jedis;

public class SlidingWindowRateLimiter {
    private static final String REDIS_HOST = "localhost";
    private static final int REDIS_PORT = 6379;
    private static final int MAX_REQUESTS = 10;
    private static final int WINDOW_SIZE_IN_SECONDS = 60;

    private Jedis jedis;

    public SlidingWindowRateLimiter() {
        this.jedis = new Jedis(REDIS_HOST, REDIS_PORT);
    }

    public boolean isAllowed(String userId) {
        String key = "rate:limiter:" + userId;
        long currentTime = System.currentTimeMillis() / 1000;

        // 清理已过期的请求
        jedis.zremrangeByScore(key, 0, currentTime - WINDOW_SIZE_IN_SECONDS);

        // 添加当前请求
        jedis.zadd(key, currentTime, String.valueOf(currentTime));

        // 获取当前请求次数
        long currentCount = jedis.zcard(key);
        
        // 设置过期时间
        jedis.expire(key, WINDOW_SIZE_IN_SECONDS);

        return currentCount <= MAX_REQUESTS;
    }

    public static void main(String[] args) {
        SlidingWindowRateLimiter rateLimiter = new SlidingWindowRateLimiter();
        String userId = "user123";
        for (int i = 0; i < 12; i++) {
            boolean allowed = rateLimiter.isAllowed(userId);
            System.out.println("Request " + (i + 1) + ": " + (allowed ? "Allowed" : "Blocked"));
        }
    }
}

3. 令牌桶限流

原理：

使用一个令牌桶来控制请求速率。每当有请求时，从桶中取出一个令牌，如果桶中没有令牌，则进行限流。

实现：

使用Redis的INCRBY和DECR命令来管理令牌。

import redis.clients.jedis.Jedis;

public class TokenBucketRateLimiter {
    private static final String REDIS_HOST = "localhost";
    private static final int REDIS_PORT = 6379;
    private static final int MAX_TOKENS = 10;
    private static final int REFILL_INTERVAL_IN_SECONDS = 60;

    private Jedis jedis;

    public TokenBucketRateLimiter() {
        this.jedis = new Jedis(REDIS_HOST, REDIS_PORT);
    }

    public boolean isAllowed(String userId) {
        String key = "rate:limiter:token:" + userId;
        long currentTime = System.currentTimeMillis() / 1000;

        // 填满token
        jedis.setnx(key, String.valueOf(MAX_TOKENS));
        long lastRefillTime = Long.parseLong(jedis.get(key + ":time"));
        long tokensToAdd = (currentTime - lastRefillTime) * MAX_TOKENS / REFILL_INTERVAL_IN_SECONDS;
        if (tokensToAdd > 0) {
            jedis.incrBy(key, tokensToAdd);
            jedis.set(key + ":time", String.valueOf(currentTime));
        }

        // 获取token
        long currentTokens = Long.parseLong(jedis.get(key));
        if (currentTokens > 0) {
            jedis.decr(key);
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        TokenBucketRateLimiter rateLimiter = new TokenBucketRateLimiter();
        String userId = "user123";
        for (int i = 0; i < 12; i++) {
            boolean allowed = rateLimiter.isAllowed(userId);
            System.out.println("Request " + (i + 1) + ": " + (allowed ? "Allowed" : "Blocked"));
        }
    }
}

4. 漏桶限流

漏桶限流算法的实现步骤

1. 设置令牌桶的容量和漏出速率。
2. 每次请求时，计算令牌桶中的令牌数。
3. 如果令牌数足够，允许请求并减少令牌数。
4. 定期将新的令牌添加到桶中。

示例代码

import redis.clients.jedis.Jedis;

public class LeakyBucketRateLimiter {
    private static final String REDIS_HOST = "localhost";
    private static final int REDIS_PORT = 6379;

    private Jedis jedis;

    public LeakyBucketRateLimiter() {
        this.jedis = new Jedis(REDIS_HOST, REDIS_PORT);
    }

    public boolean isAllowed(String userId, int rate, int capacity) {
        String key = "rate:limiter:leaky:" + userId;
        long currentTime = System.currentTimeMillis() / 1000;

        // 获取桶的当前状态，如果桶为空，则初始化桶容量和上次漏出时间
        String[] bucket = jedis.hmget(key, "tokens", "last_time").toArray(new String[0]);
        int tokens = bucket[0] != null ? Integer.parseInt(bucket[0]) : capacity;
        long lastTime = bucket[1] != null ? Long.parseLong(bucket[1]) : 0;

        // 计算时间差，漏出令牌
        long elapsed = currentTime - lastTime;
        tokens = Math.min(capacity, tokens + (int) (elapsed * rate));
        lastTime = currentTime;

        // 判断是否可以通过请求
        boolean allowed = false;
        if (tokens >= 1) {
            tokens -= 1;
            allowed = true;
        }

        // 更新桶的状态
        jedis.hset(key, "tokens", String.valueOf(tokens));
        jedis.hset(key, "last_time", String.valueOf(lastTime));
        jedis.expire(key, capacity / rate);

        return allowed;
    }

    public static void main(String[] args) {
        LeakyBucketRateLimiter rateLimiter = new LeakyBucketRateLimiter();
        String userId = "user123";
        int rate = 1; // 每秒漏出1个请求
        int capacity = 5; // 桶的最大容量为5

        for (int i = 0; i < 12; i++) {
            boolean allowed = rateLimiter.isAllowed(userId, rate, capacity);
            System.out.println("Request " + (i + 1) + ": " + (allowed ? "Allowed" : "Blocked"));
            try {
                Thread.sleep(500); // 模拟每隔0.5秒发送一次请求
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }
}

5. Redis内置的限流功能

Redis 6.0 引入了新的命令 CL.THROTTLE，这是 Redis 内置的限流功能，可以用来实现令牌桶限流算法。通过 CL.THROTTLE，可以在 Redis 服务器端实现限流逻辑，从而避免了客户端与 Redis 之间的多次交互。

下面是一个示例，展示如何使用 CL.THROTTLE 实现限流：

令牌桶限流（Token Bucket Rate Limiting）

Redis 6.0 提供了一个模块 redis-cell，其中包含了 CL.THROTTLE 命令，可以用于实现令牌桶限流算法。

首先，需要确保 Redis 已加载 redis-cell 模块。可以在 Redis 启动时通过配置文件加载该模块：

loadmodule /path/to/redis-cell.so

或者在运行时通过 MODULE LOAD 命令加载：

MODULE LOAD /path/to/redis-cell.so

然后，可以使用 CL.THROTTLE 命令进行限流：

-- 限制某个操作每分钟最多允许10次请求
local key = "rate:limiter:user123"
local max_burst = 10
local tokens_per_period = 10
local period = 60 -- 60秒

local result = redis.call("CL.THROTTLE", key, max_burst, tokens_per_period, period)
local allowed = result[1] == 0

return allowed

示例代码

以下是一个完整的示例，展示如何在 Redis 中使用 CL.THROTTLE 命令实现令牌桶限流：

-- rate_limiter.lua
-- 参数：键名、最大突发次数、每个时间周期的令牌数、时间周期（秒）
local key = KEYS[1]
local max_burst = tonumber(ARGV[1])
local tokens_per_period = tonumber(ARGV[2])
local period = tonumber(ARGV[3])

-- 执行 CL.THROTTLE 命令
local result = redis.call("CL.THROTTLE", key, max_burst, tokens_per_period, period)
local allowed = result[1] == 0

return allowed

将上述 Lua 脚本保存为 rate_limiter.lua 文件，然后在客户端使用 EVAL 命令执行该脚本：

import redis.clients.jedis.Jedis;

public class RedisRateLimiter {
    private static final String REDIS_HOST = "localhost";
    private static final int REDIS_PORT = 6379;

    private Jedis jedis;

    public RedisRateLimiter() {
        this.jedis = new Jedis(REDIS_HOST, REDIS_PORT);
    }

    public boolean isAllowed(String userId) {
        String script = "local key = KEYS[1] " +
                        "local max_burst = tonumber(ARGV[1]) " +
                        "local tokens_per_period = tonumber(ARGV[2]) " +
                        "local period = tonumber(ARGV[3]) " +
                        "local result = redis.call('CL.THROTTLE', key, max_burst, tokens_per_period, period) " +
                        "local allowed = result[1] == 0 " +
                        "return allowed";

        String key = "rate:limiter:" + userId;
        int maxBurst = 10;
        int tokensPerPeriod = 10;
        int period = 60; // 60秒

        Object result = jedis.eval(script, 1, key, String.valueOf(maxBurst), String.valueOf(tokensPerPeriod), String.valueOf(period));
        return (boolean) result;
    }

    public static void main(String[] args) {
        RedisRateLimiter rateLimiter = new RedisRateLimiter();
        String userId = "user123";
        for (int i = 0; i < 12; i++) {
            boolean allowed = rateLimiter.isAllowed(userId);
            System.out.println("Request " + (i + 1) + ": " + (allowed ? "Allowed" : "Blocked"));
        }
    }
}