令牌桶算法
- 令牌桶是一种常用的流量控制技术。令牌桶本身没有丢弃和优先级策略。
- 令牌以一定的速率放入桶中。
- 每个令牌允许源发送一定数量的比特。
- 发送一个包,流量调节器就要从桶中删除与包大小相等的令牌数。
- 如果没有足够的令牌发送包,这个包就会等待直到有足够的令牌(在整形器的情况下)或者包被丢弃,也有可能被标记更低的DSCP(在策略者的情况下)。
桶有特定的容量,如果桶已经满了,新加入的令牌就会被丢弃。因此,在任何时候,源发送到网络上的最大突发数据量与桶的大小成比例。令牌桶允许突发,但是不能超过限制。
环境介绍
- Ubuntu 16.04.7 LTS Release:16.04 Codename:xenial 使用
sudo lsb_release -a
查看 - php7.4.27 使用
php -v
查看 - swoole4.8.5 使用
php --ri swoole
查看 swoole官方文档 - redis扩展 使用
php --ri redis
查看 redis编译包 redis服务我这里使用docker搭建redis了服务,具体命令如下:
# 命令来查看可用版本 docker search redis # 拉取官方的最新版本的镜像 docker pull redis:latest # 查看是否已安装了 redis docker images #运行redis容器 #–-requirepass 设置密码 #–-appendonly 开启redis 持久化 docker run -itd --name myredis -p 6379:6379 redis --requirepass "123456" --appendonly yes #查看容器的运行 docker ps
虚拟机IP
192.168.56.2
开放端口8080
php使用swoole搭建一个简单的HTTP服务做测试
创建test.php文件
<?php $http = new Swoole\Http\Server('0.0.0.0', 8080); $http->on('Request', function ($request, $response) { if ($request->server['path_info'] == '/favicon.ico' || $request->server['request_uri'] == '/favicon.ico') { $response->end(); return; } $lua = file_get_contents('limiter.lua'); $redis = new Redis(); $redis->connect('192.168.56.2'); $redis->auth(123456); $key = 'lingpai'; if (isset($request->get['method'])) { //初始化令牌 $message = '初始化令牌失败!'; if ($redis->eval($lua,[$key, 'initTokenBucket',100, 1],1)) { $message = '初始化令牌成功!'; } $response->end($message); return; } //请求时间 $curr_mill_second = $redis->eval($lua,['currentTimeMillis'],0); //获取令牌 $result = $redis->eval($lua,[$key, 'acquire',1, $curr_mill_second],1); $response->end($result); }); $http->start();
# 命令行执行开启服务 php test.php
limiter.lua文件
--- @param key 令牌的唯一标识
--- @param permits 请求令牌数量
--- @param curr_mill_second 当前时间
--- 0 没有令牌桶配置;-1 表示取令牌失败,也就是桶里没有令牌;1 表示取令牌成功
local function acquire(key, permits, curr_mill_second)
local local_key = key --- 令牌桶key ,使用 .. 进行字符串连接
if tonumber(redis.pcall("EXISTS", local_key)) < 1 then --- 未配置令牌桶
return 0
end
--- 令牌桶内数据:
--- last_mill_second 最后一次放入令牌时间
--- curr_permits 当前桶内令牌
--- max_permits 桶内令牌最大数量
--- rate 令牌放置速度
local rate_limit_info = redis.pcall("HMGET", local_key, "last_mill_second", "curr_permits", "max_permits", "rate")
local last_mill_second = rate_limit_info[1]
local curr_permits = tonumber(rate_limit_info[2])
local max_permits = tonumber(rate_limit_info[3])
local rate = rate_limit_info[4]
--- 标识没有配置令牌桶
if type(max_permits) == 'boolean' or max_permits == nil then
return 0
end
--- 若令牌桶参数没有配置,则返回0
if type(rate) == 'boolean' or rate == nil then
return 0
end
local local_curr_permits = max_permits;
--- 令牌桶刚刚创建,上一次获取令牌的毫秒数为空
--- 根据和上一次向桶里添加令牌的时间和当前时间差,触发式往桶里添加令牌,并且更新上一次向桶里添加令牌的时间
--- 如果向桶里添加的令牌数不足一个,则不更新上一次向桶里添加令牌的时间
--- ~=号在Lua脚本的含义就是不等于!=
if (type(last_mill_second) ~= 'boolean' and last_mill_second ~= nil) then
if(curr_mill_second - last_mill_second < 0) then
return -1
end
--- 生成令牌操作
local reverse_permits = math.floor(((curr_mill_second - last_mill_second) / 1000) * rate) --- 最关键代码:根据时间差计算令牌数量并匀速的放入令牌
local expect_curr_permits = reverse_permits + curr_permits;
local_curr_permits = math.min(expect_curr_permits, max_permits); --- 如果期望令牌数大于桶容量,则设为桶容量
--- 大于0表示这段时间产生令牌,则更新最新令牌放入时间
if (reverse_permits > 0) then
redis.pcall("HSET", local_key, "last_mill_second", curr_mill_second)
end
else
redis.pcall("HSET", local_key, "last_mill_second", curr_mill_second)
end
--- 取出令牌操作
local result = -1
if (local_curr_permits - permits >= 0) then
result = 1
redis.pcall("HSET", local_key, "curr_permits", local_curr_permits - permits)
else
redis.pcall("HSET", local_key, "curr_permits", local_curr_permits)
end
return result
end
--- 初始化令牌桶
--- @param key 令牌的唯一标识
--- @param max_permits最大令牌数
--- param rate令牌放置速度
local function initTokenBucket(key, max_permits, rate)
if(key == nil or string.len(key) < 1) then
return 0
end
local local_max_permits = 100
if(tonumber(max_permits) > 0) then
local_max_permits = max_permits
end
local local_rate = 100
if(tonumber(rate) > 0) then
local_rate = rate
end
redis.pcall("HMSET", key, "max_permits", local_max_permits, "rate", local_rate)
return 1;
end
--- 获取当前时间,单节点获取,避免集群模式下(无论业务系统集群,还是redis集群)获取的时间不同,导致桶不匀速
local function currentTimeMillis()
local times = redis.pcall("TIME")
return tonumber(times[1]) * 1000 + tonumber(times[2]) / 1000
end
--- key,即redis中的key。
local key = KEYS[1]
--- args第一个参数即要调用的方法名。
local method = ARGV[1]
--- 请求令牌
if method == 'acquire' then
return acquire(key, ARGV[2], ARGV[3])
--- 请求时间
elseif method == 'currentTimeMillis' then
return currentTimeMillis()
--- 初始化令牌桶
elseif method == 'initTokenBucket' then
return initTokenBucket(key, ARGV[2], ARGV[3])
end
check.php 获取当前令牌数量
<?php
while (true) {
$redis = new Redis();
$redis->connect('192.168.56.2');
$redis->auth(123456);
$data = $redis->hMget('lingpai',['max_permits','curr_permits','rate']);
echo "最大的令牌数:{$data['max_permits']}---------每秒生成令牌数:{$data['rate']}----------当前令牌数:{$data['curr_permits']}\r\n";
sleep(3);
}
# 命令行执行
php check.php
浏览器多次连续模拟API接口请求,根据check.php查看结果
测试
说明
- 我们初始化设置令牌最大数量为100个
- 生成速率为每秒1个令牌/s
初始化令牌
http://192.168.56.2:8080/?method #初始化令牌成功!
获取令牌
http://192.168.56.2:8080/ #返回1则获取到令牌 返回-1则获取失败