令牌桶算法

  • 令牌桶是一种常用的流量控制技术。令牌桶本身没有丢弃和优先级策略。
  • 令牌以一定的速率放入桶中。
  • 每个令牌允许源发送一定数量的比特。
  • 发送一个包，流量调节器就要从桶中删除与包大小相等的令牌数。
  • 如果没有足够的令牌发送包，这个包就会等待直到有足够的令牌（在整形器的情况下）或者包被丢弃，也有可能被标记更低的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则获取失败

    测试结果

Last modification：May 6, 2022
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏