yao同学

常见限流算法

崧云悠揽月
April 26, 2024

本文将介绍以下四种常见的限流算法，并使用 Node.js + redis 实现：

固定窗口限流 ​

原理 ​

固定窗口限流就是对一段固定时间窗口内的请求进行计数。

  • 如果请求数超过了阈值，则拒绝该请求；
  • 如果请求数没超过阈值，则接受该请求，且计数加1。
  • 当时间窗口结束时，重置计数器为0。

代码实现 ​

ts
/**
 * 固定窗口限流
 * @param {string} key 缓存key
 * @param {number} max 最大访问量
 */
export function fixedWindow(key = 'fixedWindow', max = 5) {
    return async (ctx, next) => {
        const cacheKey = `${key}:${ctx.path}`;

        // 计数器
        const counter = await redis.incr(cacheKey);
        if (counter === 1) {
            await redis.expire(cacheKey, 5 * 60);
        }

        // 如果超过最大访问量，则拒绝访问
        if (counter > max) {
            ctx.status = 429;
            ctx.body = 'Too many request, try again later.';
        } else {
            await next();
        }
    }
}

测试一下 ​

ts
const Koa = require('koa');
const app = new Koa();

// 使用中间件
app.use(fixedWindow('fixedWindow', 5));

app.use((ctx) => ctx.body = 'Hello World');
app.listen(3000, () => {
    console.log('server is running at http://localhost:3000')
});
shell
ab -n 10 -c 10 -k -s 1200 "http://localhost:3000/"

缺点 ​

如图，临界值会出现两倍流量配置的情况。

滑动窗口限流 ​

滑动窗口限流解决固定窗口临界值的问题。它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期的小周期。

代码实现 ​

ts
/**
 * 滑动窗口限流
 * @param {string} key 缓存key
 * @param {number} max 最大访问量
 */
export function slidingWindow(key = 'slidingWindow', max = 5) {
    return async (ctx, next) => {
        const path = ctx.path;
        const cacheKey = `${key}:${path}`;
        const smallWindow = 200; // 200ms
        const now = Date.now();
        const uuid = `${Math.random().toString().slice(3)}-${now}`;
        const windowStart = calcWindowStart(5 * 60, smallWindow);
        const luaScript = `
      local key = KEYS[1]
      local now = tonumber(ARGV[1])
      local uuid = ARGV[2]
      local windowStart = tonumber(ARGV[3])
      local maxRequests = tonumber(ARGV[4])

      redis.call('ZREMRANGEBYSCORE', key, '-inf', windowStart)
      redis.call('ZADD', key, now, uuid)
      local requestCount = redis.call('ZCARD', key)

      if requestCount <= maxRequests then
        return "ALLOW"
      else
        return "DENY"
      end
    `;
        const result = await redis.eval(
            luaScript,
            1,
            cacheKey,
            now.toString(),
            uuid,
            windowStart.toString(),
            max
        );

        if (result !== 'ALLOW') {
            ctx.status = 429;
            ctx.body = 'Too many request, try again later.';
        } else {
            await next();
        }
    }
}

/**
 * 根据 滑动窗口长度、最小窗口长度和当前时间，计算滑动窗口开始时间
 * @param duration
 * @param smallWindow
 */
export function calcWindowStart(
    duration: number,
    smallWindow: number
): number {
    const now = Date.now();
    const lastWindowLen = now % smallWindow;
    const dur = duration * 1000;

    return now - dur + (smallWindow - lastWindowLen);
}

测试一下 ​

ts
const Koa = require('koa');
const app = new Koa();

// 使用中间件
app.use(slidingWindow('slidingWindow', 5));

app.use((ctx) => ctx.body = 'Hello World');
app.listen(3000, () => {
    console.log('server is running at http://localhost:3000')
});
shell
ab -n 10 -c 10 -k -s 1200 "http://localhost:3000/"

缺点 ​

滑动窗口算法虽然解决了固定窗口的临界问题，但是一旦到达限流后，请求都会直接被暴力被拒绝。酱紫我们会损失一部分请求，这其实对于产品来说，并不太友好。

漏桶算法 ​

漏桶算法面对限流，就更加的柔性，不存在直接的粗暴拒绝。

它的原理很简单，可以认为就是注水漏水的过程。往漏桶中以任意速率流入水，以固定的速率流出水。当水超过桶的容量时，会被溢出，也就是被丢弃。因为桶容量是不变的，保证了整体的速率。

代码实现 ​

原理：

  • 请求进来时，先计算当前请求滴出时间并将请求放入队列。
  • 根据滴出时间清除队列中已经滴出的请求。
  • 如果队列长度超过了桶的容量，则拒绝请求。

计算公式：请求滴出时间 = MAX(上次请求滴出时间 + 滴水间隔时间 ,当前时间)

举例

当前时间：2024-04-26 13:00:00(1714107600000), 滴水间隔时间：1个/200ms；桶容量：5个；同时有5个请求进来

  • 第1个请求滴出时间 = MAX(0 + 200, 1714107600000) = 1714107600200
  • 第2个请求滴出时间 = MAX(1714107600200 + 200, 1714107600200) = 1714107600400
  • 第3个请求滴出时间 = MAX(1714107600400 + 200, 1714107600400) = 1714107600600
  • 第4个请求滴出时间 = MAX(1714107600600 + 200, 1714107600600) = 1714107600800
  • 第5个请求滴出时间 = MAX(1714107600800 + 200, 1714107600800) = 1714107601000
ts
/**
 * 漏桶算法限流
 * @param {string} key 缓存key
 * @param {number} capacity 桶容量
 * @param {number} outRate 出水速率, 每秒出水量
 */
export function leakyBucket(
    key = 'leakyBucket',
    capacity = 5,
    outRate = 1
) {
    return async (ctx, next) => {
        const luaScript = `
      local redisKey = KEYS[1]
      local now = tonumber(ARGV[1])
      local capacity = tonumber(ARGV[2])
      local outRate = tonumber(ARGV[3])
      
      -- Step 1: 清除过期水滴，并获取当前水量
      redis.call('ZREMRANGEBYSCORE', redisKey, '-inf', now);
      local water = tonumber(redis.call('zcard', redisKey))
      
      -- Step 2：如果水量小于容量，则继续加水
      if water < capacity then
        local interval = math.floor(1000 / outRate)
        local max_score = redis.call('ZREVRANGE', redisKey, 0, 0)
        local lastOperateTime = max_score[0] or 0
        local currOperateTime = math.max(lastOperateTime + interval, now)
        redis.call('ZADD', redisKey, currOperateTime, currOperateTime)
        return currOperateTime
      else
        return -1
      end
    `;
        const now = Date.now();
        const currOperateTime = await redis.eval(
            luaScript,
            1,
            key,
            now.toString(),
            capacity.toString(),
            outRate.toString(),
        );

        if (currOperateTime && +currOperateTime < 0) {
            ctx.status = 429;
            ctx.body = 'Too many Requests. Try again later.';
        } else {
            await sleep(+currOperateTime - now);
            await next();
        }
    }
}

async function sleep(ms) {
    if (ms <= 0) return ;

    return new Promise(resolve => setTimeout(resolve, ms));
}

测试一下 ​

const Koa = require('koa');
const app = new Koa();

// 使用中间件
app.use(leakyBucket('fixedWindow', 5));

app.use((ctx) => ctx.body = 'Hello World');
app.listen(3000, () => {
    console.log('server is running at http://localhost:3000')
});

缺点 ​

在正常流量的时候，系统按照固定的速率处理请求，是我们想要的。但是面对突发流量的时候，漏桶算法还是循规蹈矩地处理请求，这就不是我们想看到的啦。流量变突发时，我们肯定希望系统尽量快点处理请求，提升用户体验嘛。

令牌桶算法 ​

面对突发流量的时候，我们可以使用令牌桶算法限流。

令牌桶算法原理：

  • 根据限流大小，定时往令牌桶里放令牌。
  • 如果令牌数量满了，超过令牌桶容量的限制，那就丢弃。
  • 系统在接受到一个用户请求时，都会先去令牌桶要一个令牌。如果拿到令牌，那么就处理这个请求的业务逻辑； 如果拿不到令牌，就直接拒绝这个请求。

代码实现 ​

ts
/**
 * 固定窗口限流
 * @param {string} key 缓存key
 * @param {number} capacity 令牌桶容量
 * @param {number} refillRate 令牌每秒添加速率,
 */
export function tokenBucket(
    key: string = 'tokenBucket',
    capacity: number = 5,
    refillRate: number = 1
) {
    return async (ctx, next) => {
        const luaScript = `
      local redisKey = KEYS[1]
      local now = tonumber(ARGV[1])
      local capacity = tonumber(ARGV[2])
      local refillRate = tonumber(ARGV[3])

      -- Get the current token count and last refill time
      -- Step 1: 获取当前令牌数量、最后添加令牌时间
      local lastRefillTime = tonumber(redis.call("HGET", redisKey, "lastRefillTime")) or now
      local currentTokens = tonumber(redis.call("HGET", redisKey, "tokens")) or capacity

      -- Calculate the elapsed time since the last refill
      -- Step 2: 计算当前需要添加多少令牌
      local elapsedSeconds = math.max(0, now - lastRefillTime)
      local tokensToAdd = math.floor(elapsedSeconds * refillRate)

      -- Update the token count and refill time
      -- Step 3: 更新令牌数量和最后添加令牌时间
      local newTokens = math.min(currentTokens + tokensToAdd, capacity)
      redis.call("HSET", redisKey, "lastRefillTime", now)
      redis.call("HSET", redisKey, "tokens", newTokens)

      -- Check if there are enough tokens for this request
      if newTokens >= 1 then
        redis.call("HSET", redisKey, "tokens", newTokens - 1)
        return "ALLOW"
      else
        return "DENY"
      end
    `;
        const now = Math.floor(Date.now() / 1000);
        const result = await redis.eval(
            luaScript,
            1,
            key,
            now.toString(),
            capacity.toString(),
            refillRate.toString(),
        );

        if (result !== 'ALLOW') {
            ctx.status = 429;
            ctx.body = 'Too many Requests. Try again later.';
        } else {
            await next();
        }
    }
}

测试一下 ​

ts
const Koa = require('koa');
const app = new Koa();

// 使用中间件
app.use(tokenBucket('tokenBucket', 5));

app.use((ctx) => ctx.body = 'Hello World');
app.listen(3000, () => {
    console.log('server is running at http://localhost:3000')
});

缺点 ​

如果令牌发放的策略正确，这个系统即不会被拖垮，也能提高机器的利用率。Google的Java开发工具包Guava中的RateLimiter类，就是基于令牌桶算法实现的。

拓展：Lua脚本是否可以用事务代替？ ​

可以，但Redis事务存在一些缺陷

  • 原子性的限制（如图）

  • 不支持条件操作：事务不支持条件操作，例如基于当前值来更新某个键的值。

  • 事务中的每条命令都会与redis服务器进行网络交互

总结 ​

算法优点缺点使用场景
固定窗口限流简单存在临界值问题--
滑动窗口限流解决了固定窗口的临界值问题达到限流后，对后续请求暴力拒绝--
漏桶算法面对限流更加柔和，不存在暴力拒绝面对突发流量，循规蹈矩--
令牌桶算法解决了突发流量的问题无明显缺点--

TIP

完整代码请点击这里。

粤ICP备2022123940号-1