Redis 实现限流

常见的限流算法有:计数器,漏桶、令牌桶。

计数器(时间窗口)

原理:记录每个请求,判断在设定的限流时间窗口内请求数是否大于限制数。限流要注意避免边界问题,滑动时间窗口的方法能很好解决这个问题。

利用 Redis 有序集合实现,并用管道加速

思路:假设 $period 秒内,一个用户只能访问 $maxCount 次。用户ID作为 key,毫秒时间戳作为 score 和 value。
一个请求进入,

  1. 加入有序集合——zadd
  2. 移除时间窗口之前的行为记录,剩下的都是时间窗口内的——zremrangebyscore
  3. 更新过期时间——expire
  4. 获取窗口内的元素数量——zcard
  5. 判断窗口内元素数量是否大于最大请求限制数(maxCount),若大于等于则拒绝请求,若小于则接受请求。
function isActionAllowed($userId, $action, $period, $maxCount) 
{
    $redis = new Redis();
    $redis->connect('127.0.0.1', 6379);
    $key = sprintf('hist:%s:%s', $userId, $action);
    $now = msectime();   # 毫秒时间戳

    $pipe=$redis->multi(Redis::PIPELINE); //使用管道提升性能
    $pipe->zadd($key, $now, $now); //value 和 score 都使用毫秒时间戳
    $pipe->zremrangebyscore($key, 0, $now - $period * 1000); //移除时间窗口之前的行为记录,剩下的都是时间窗口内的
    $pipe->zcard($key);  //获取窗口内的行为数量
    $pipe->expire($key, $period  + 1);  //多加一秒过期时间
    $replies = $pipe->exec();
    return $replies[2] <= $maxCount;
}

// 执行
for ($i=0; $i<20; $i++){
    var_dump(isActionAllowed("110", "reply", 60, 5)); //执行可以发现只有前5次是通过的
}

//返回当前的毫秒时间戳
function msectime() {
    list($msec, $sec) = explode(' ', microtime());
    $msectime = (float)sprintf('%.0f', (floatval($msec) + floatval($sec)) * 1000);
    return $msectime;
 }

漏斗算法

原理:漏桶 (Leaky Bucket) 算法思路很简单,水 (请求) 先进入到漏桶里,漏桶以一定的速度出水 (接口有响应速率), 当水流入速度过大会直接溢出 (访问频率超过接口响应速率), 然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率。

利用 Redis-Cell 模块实现

Redis 4.0 提供了一个限流 Redis 模块,名称为 redis-cell,该模块提供漏斗算法,并提供原子的限流指令。

该模块只有一条指令 cl.throttle,下面看一下其参数和返回值

> cl.throttle tom:reply 14 30 60 1
1) (integer) 0    # 0表示允许,1表示拒绝
2) (integer) 15    # 漏斗容量capacity
3) (integer) 14    # 漏斗剩余空间left_quota
4) (integer) -1    # 如果拒绝了,需要多长时间后再重试,单位秒
5) (integer) 2    # 多长时间后,漏斗完全空出来,单位秒

令牌桶算法

原理:令牌桶算法 (Token Bucket) 和 Leaky Bucket 效果一样但方向相反的算法,更加容易理解。随着时间流逝,系统会按恒定 1/QPS 时间间隔 (如果 QPS=100, 则间隔是 10ms) 往桶里加入 Token (想象和漏洞漏水相反,有个水龙头在不断的加水), 如果桶已经满了就不再加了。新请求来临时,会各自拿走一个 Token, 如果没有 Token 可拿了就阻塞或者拒绝服务。

利用 Redis String + 定时任务实现

利用定时任务不断增加令牌数,Redis->incr(),自增一,令牌桶满则不再增加;
来一个请求消耗一个令牌,Redis->decr(),自减一,当没有令牌时则拒绝请求。
一旦需要提高速率,则按需提高放入桶中的令牌的速率即可。

参考 https://learnku.com/articles/30822