redis, 工作

接口请求速率(接口防刷)限制方案

1.场景

当前业务中接口防刷的场景有:

  • 1.短信/邮件接口。这个接口不做好防刷策略,损失是很大的。
  • 2.涉及到安全问题的接口调用。比如注册接口,登录接口等等。过于频繁的请求可能代表着用户的批量注册,用户密码的暴力破解(需要考虑到可能是用户忘记密码了)等等。

2.要求

  • 1.与当前业务系统解耦合
  • 2.可以很方便的对不同的接口设置不同的请求频率限制
  • 3.具有较好的性能。在大并发的情况下,需要有正确的结果

3.方案提出

3.1 token bucket(令牌桶)

token bucket算法的如下图:

token_bucket

描述如下:

1.假设有一个桶,不断的向桶中投放token,并且我们也可以从桶中取出token。
2.投放token的速率是恒定的r1,桶满了token数量则不会再增长。
3.取出的速率是随机的r2。如果桶是空的,则无法取出token。
4.所有的请求都必须从桶中取出token才是有效的。否则该请求会被拒绝。

举个例子,假设桶的容量是10,每秒放2个token进去。

  • 如果现在每秒2个请求,那么所有这样的请求都是没有问题的,都会拿到token。
  • 如果现在每秒4个请求,10 + 2x = 4x。也就是x=5秒后请求就没法及时拿到token,被丢弃。

总结出以下特点:
– 如果请求速率过快,到一段时间后会受到限制
– 允许突发请求

3.2 redis数据库

使用redis数据库完全是因为方便以及速度。只要注意这其中存在的CAS问题即可

4.具体实现

首先,为了解决redis中检查和存储数据存在的CAS问题,我们需要使用lua脚本。因此,对于token bucket的主要实现是用lua脚本实现,然后通过php调用。

local function mysplit(inputstr, sep)
    if sep == nil then
            sep = "%s"
    end
    local t={} ; 
    local i=1
    for str in string.gmatch(inputstr, "([^"..sep.."]+)") do
            t[i] = str
            i = i + 1
    end
    return t
end

local res = redis.pcall('get',KEYS[1])

if (res == false) then
    -- bucket不存在,初始化为capacity - 1
    local str = string.format("%d %d",ARGV[1] - 1,ARGV[2])  
    return redis.pcall('set',KEYS[1],str)
end

local arr_str = mysplit(res, " ")

local num = arr_str[1]
local timestamp = arr_str[2]

-- 根据时间戳来计算num,这里一秒2个令牌
num = num + (ARGV[2] - timestamp) * ARGV[3]
-- 不超过10个令牌
if num > 10 then
    num = 10
end

if (tonumber(num) > 0) then
    -- 拿到token并减一
    local str = string.format("%d %d",num - 1,ARGV[2])
    return redis.pcall('set', KEYS[1], str)
else 
    -- 没有拿到token
    return false
end
<?php

$sha = '2ff7ad2d1b49da8430e5adc8675e';

/**
 * 初始化lua脚本
 */
function initScript($redis) {
    global $sha;
    //不存在脚本,load进去
    $script = file_get_contents('check_and_set.lua');
    $sha = $redis->script('load', $script);
    if($redis->getLastError() !== NULL){
        echo "出错了:".$redis->getLastError().'\n';
    }
    echo "初始化的脚本sha:".$sha.PHP_EOL;
}

function getTokenFromBucket($redis, $bucket) {
    global $sha;
    $capacity = 10;
    $time = time();
    $inputRate = 2;     //一秒2个token
    $params = array($bucket, $capacity, $time, $inputRate);
    $result = $redis->evalSha($sha, $params, 1);
    if($redis->getLastError() !== NULL){
        echo "出错了:".$redis->getLastError().'\n';
    }
    return $result;
}

$redis = new Redis();
$redis->pconnect("127.0.0.1");

initScript($redis);

$start = microtime(true) * 1000;

while(true) {
    $result =  getTokenFromBucket($redis, 'bucket1');
    if (!$result) {
        break;
    } else {
        echo time()."--拿到令牌".PHP_EOL;
        usleep(250000);    //每秒请求4次,10 + 2x = 4x, x = 5。5秒左右无法拿到令牌
    }
}

$end = microtime(true) * 1000;

echo "共耗时:".($end - $start)."毫秒".PHP_EOL.PHP_EOL;

$start = microtime(true) * 1000;

while(true) {
    $result =  getTokenFromBucket($redis, 'bucket2');
    if (!$result) {
        break;
    } else {
        echo "拿到令牌".PHP_EOL;
        usleep(500000);    //每秒请求2次,永远可以拿到令牌
    }
}

$end = microtime(true) * 1000;

echo "共耗时:".($end - $start)."毫秒".PHP_EOL.PHP_EOL;

代码中主要部分概括如下:

  • 检查redis中是否存在桶bucket1
  • 如果不存在,那么默认的容量是10,将bucket1设为9 timestamp(timestamp为当前的时间戳)。返回true
  • 如果存在,则获取该bucket1的值,解析出实际token数量为num,以及上一次存储时时间戳为pre。如果rate为token的生成速率,那么现在的token数量应该是:num = num + (time() – pre) * rate。num最大为默认容量10。如果num大于0,则减一后重新设置,返回true。否则返回false。

代码的运行结果如下:

运行结果演示

5.扩展知识

与token bucket相似的算法还有leaky bucket(漏桶)。leaky bucket 就像是 token bucket的镜像一样。leaky bucket 一般用于Traffic shaping和Traffic policing等问题,与下面的两张图对应。

leaky bucket

leaky bucket

可以描述如下:

  • 1.有一个桶,其上方水龙头以变化的速率r1向里面滴水,桶底的水龙头则以恒定的速率向下漏水
  • 2.水桶装满后,上方水龙头的滴水就会溢出
  • 3.水桶空后,下方水龙头则不会滴水

这里举一个异步任务处理(任务队列的容量是有限的)的例子。

  • 上方水龙头相当于任务投递系统,下方水龙头相当于任务处理系统。
  • 任务投递的速率是变化的,因为不同时间段的系统负载可能不同。
  • 任务处理系统的速率是恒定的,因为机器的处理能力是恒定的。
  • 当任务投递的速率大于处理速率,填充满任务队列后,后面的任务都会被丢弃。

可以看出leaky bucket可以将不规则的抖动的请求序列变成规则的平滑的请求序列。leaky bucket通常有两个版本:作为一个评判的仪器(meter)或者是生成一个合法请求队列(queue)。

虽然在使用中leaky bucket和token bucket是不同的,但实际上他们是同一种思路。leaky bucket的变化的输入相当于token bucket的变化的输出,leaky bucket的恒定的输出相当于token bucket的恒定的输出。

参考文献

token bucket
leaky bucket

2 comments

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注