限流原理与实践：固定窗口、滑动窗口、漏桶与令牌桶解析

方案一、固定窗口限流算法

这里我们通过一个 demo 来介绍固定窗口限流算法。

创建一个 FixWindowRateLimiterService 类。

@Service
public class FixWindowRateLimiterService {
    @Resource
    private StringRedisTemplate stringRedisTemplate;

    private static final DefaultRedisScript<Long> LIMIT_SCRIPT;


    /**
     * 是否运行请求通过
     *
     * @param key     Redis key
     * @param max     允许请求通过的最大数
     * @param timeout 一个窗口的时间
     * @return true:通过 false:限流
     */
    public boolean isAllowed(String key, Long max, Long timeout) {
        Long signal = stringRedisTemplate.execute(
                LIMIT_SCRIPT,
                Collections.singletonList(key),
                String.valueOf(max),
                String.valueOf(timeout)
        );

        if (Objects.isNull(signal)) {
            return false;
        }

        //返回 0，则说明就是限流
        return signal != 0;
    }

    static {
        LIMIT_SCRIPT = new DefaultRedisScript<>();
        LIMIT_SCRIPT.setLocation(new ClassPathResource("RateLimiterLua.lua"));
        LIMIT_SCRIPT.setResultType(Long.class);
    }
}

写一个 lua 脚本（保证线程安全），lua 脚本要放在 resources 的根目录下

local key = KEYS[1]
local max = tonumber(ARGV[1])
local timeout = tonumber(ARGV[2])
local current = tonumber(redis.call('get', key) or "0")
if current + 1 > max then
    return 0
else
    redis.call("INCRBY", key, 1)
    redis.call("EXPIRE", key, timeout)
    return current + 1
end

测试

注意，固定窗口算法存在边界问题，下图介绍了窗口问题。

方案二、滑动窗口限流算法

滑动窗口限流算法相对固定窗口限流算法更复杂一些，但更为精确。下面是一个基于 Redis 的 zset 结构实现的简单滑动窗口限流的例子。

@RestController
public class RateLimitController {
    private static final String KEY = "rate:limit";
    private static final int MAX_VISIT = 1;

    @Resource
    private RedisTemplate redisTemplate;

    @ResponseBody
    @GetMapping("/visit")
    public String visit() {
        //1970-01-01T00:00:00Z 到现在的秒数
        long now = Instant.now().getEpochSecond();
        //移除现在这个时刻往前推 60s 的访问统计数
        redisTemplate.opsForZSet().removeRangeByScore(KEY, 0, now - 60);
        //获取当前的访问统计数
        Long currentVisits = redisTemplate.opsForZSet().zCard(KEY);

        if (currentVisits >= MAX_VISIT) {
            return "请稍后再试~";
        } else {
            redisTemplate.opsForZSet().add(KEY, String.valueOf(now), now);
            return "访问成功~";
        }
    }
}

方案三、漏桶限流算法

这个算法的基本思想就像有一个漏洞的桶一样。漏桶以一定的速度出水，当水流入过大的时候溢出。通过这个思想来进行流量的控制。

在程序实现中，漏桶通常以一个队列的形式存在，在有新的请求先进入队列中。队列以一定的速率处理请求，当队列满了以后，新进入的请求就会被拒绝。

下面是一个漏桶算法的 demo。在这个例子中，我们创建了一个容量为 10 的桶，每秒可以漏水两个（也就是系统每秒可以处理两个请求）。每当有新请求到来时，我们先计算桶里还剩多少水，如果没满则把请求加进去，满了就拒绝请求。

public class LeakyBucketDemo {
    /**
     * 桶的容量
     */
    private final long capacity = 10L;

    /**
     * 水流出的速度
     */
    private final long rate = 2L;

    /**
     * 当前水量（实际上就是请求书）
     */
    private long water = 0L;

    /**
     * 上次漏水时间
     */
    private long lastTime = System.currentTimeMillis();

    public boolean tryConsume() {
        long now = System.currentTimeMillis();
        //计算当前水量
        water = Math.max(0, water - (now - lastTime) * rate);
        lastTime = now;
        //判断剩余空间是否足够
        if ((water + 1) < capacity) {
            water++;
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        LeakyBucketDemo leakyBucketDemo = new LeakyBucketDemo();
        for (int i = 0; i < 11; i++) {
            System.out.println(leakyBucketDemo.tryConsume() ? "请求通过" : "请求被限流");
        }
    }
}

方案四、令牌桶限流算法

这个算法的思想是在一个常量固定速率下，把令牌放到令牌桶中。当请求来临的时候，令牌桶中有令牌则请求成功，没有令牌则请求失败。每请求成功一次，就会桶令牌丢到一个令牌。

下面是一个使用 Google 开源的 Guava 库来做限流算法的 demo。

public class TokenBucketDemo {
    private final RateLimiter rateLimiter = RateLimiter.create(10);

    public void doRequest() {
        if (rateLimiter.tryAcquire()) {
            System.out.println("正常处理请求");
        } else {
            System.out.println("限流");
        }
    }

    public static void main(String[] args) throws InterruptedException {
        TokenBucketDemo tokenBucketDemo = new TokenBucketDemo();
        for (int i = 0; i < 20; i++) {
            Thread.sleep(1000);
            tokenBucketDemo.doRequest();
        }
    }
}

总结

四种限流算法各有优缺点，需要根据自己的业务场景选择使用。推荐项目比较复杂的时候使用成熟的框架，比如sentinel。

固定窗口限流算法：适用于对精度要求不高，对性能要求比较高的场景。
滑动窗口限流算法：适用于对限流精度比较高的场景。
漏桶限流算法：适用于访问速率绝对稳定的场景。
令牌桶限流算法：适用于访问速率相对比较稳定的场景，但也可以应对一定的突发流量的场景。（对于使用 Guava 实现的方案，如果自己的项目是分布式的，那么此方案不适用 --Guava 是单机的）