令牌桶与漏桶算法实战解析

最近发现不少小伙伴都对文章很感兴趣，所以今天继续给大家介绍文章相关的知识，本文《PHP限流算法：令牌桶与漏桶实战应用》主要内容涉及到等等知识点，希望能帮到你！当然如果阅读本文时存在不同想法，可以在评论中表达，但是请勿使用过激的措辞~

在PHP应用中实现请求限流需采用令牌桶或漏桶算法，1. 令牌桶通过维护令牌数量和生成速率控制请求，允许突发流量；2. 漏桶通过固定漏水速率平滑请求处理，防止突发冲击；3. 两者均需借助Redis的原子操作（如Lua脚本）确保并发一致性；4. 限流维度可基于用户、IP或接口，通过唯一键标识；5. 核心目标是保障系统稳定性，防止过载，确保服务可用性，最终通过返回布尔值明确是否放行请求。

请求限流在PHP应用中，特别是对于API接口的保护，通常会采用令牌桶（Token Bucket）或漏桶（Leaky Bucket）这两种经典算法。它们的核心思想都是控制单位时间内允许处理的请求数量，避免系统过载，保障服务的稳定性与可用性。在PHP中实现它们，关键在于如何高效地管理“令牌”或“水滴”，并利用共享存储（如Redis）来维护状态，确保并发环境下的数据一致性。

解决方案

实现请求限流，我们首先要明确限流的目标：是限制某个用户、某个IP，还是整个接口的访问频率？这决定了我们存储状态的维度。通常，基于Redis的实现是首选，因为它提供了原子操作和高并发读写能力。

令牌桶算法（Token Bucket）

想象一个固定容量的桶，系统会以恒定的速率往桶里放入令牌。每个请求到来时，都需要从桶里取走一个令牌才能被处理。如果桶里没有令牌，请求就会被拒绝或排队。

• 实现思路：

  • 定义桶的容量（bucket_capacity）和令牌生成速率（token_rate，每秒生成多少个）。
  • 在Redis中存储一个键，表示当前桶中令牌的数量（current_tokens）以及上次更新令牌的时间戳（last_fill_time）。
  • 每次请求到达时，通过Redis的Lua脚本来原子性地执行以下逻辑：
    1. 计算自上次填充以来新增的令牌数量：new_tokens = (current_timestamp - last_fill_time) * token_rate。
    2. 更新桶中令牌数：current_tokens = min(bucket_capacity, current_tokens + new_tokens)。
    3. 更新last_fill_time = current_timestamp。
    4. 如果current_tokens >= 1，则允许请求，并current_tokens--。
    5. 否则，拒绝请求。

• PHP伪代码示例 (使用Redis)：

  <?php
  // 假设已经通过 composer require predis/predis 或者 php-redis 扩展连接了 Redis
  // 这里使用一个简单的 Redis 客户端模拟，实际生产环境请使用成熟的库
  
  class RateLimiter
  {
      private $redis;
  
      public function __construct(Redis $redis)
      {
          $this->redis = $redis;
      }
  
      /**
       * 令牌桶算法限流
       * @param string $key 限流的唯一标识，例如 'user:123' 或 'api:product_list'
       * @param int $capacity 桶的容量，即最大允许的突发请求数
       * @param float $rate 令牌生成速率，每秒生成的令牌数
       * @return bool 是否允许请求通过
       */
      public function tokenBucket($key, $capacity, $rate): bool
      {
          $currentTokensKey = "rate_limit:token_bucket:{$key}:tokens";
          $lastFillTimeKey = "rate_limit:token_bucket:{$key}:last_fill_time";
  
          $currentTime = microtime(true); // 使用微秒时间戳，更精确
  
          // Lua脚本保证原子性操作
          $script = <<<LUA
              local currentTokens = tonumber(redis.call('get', KEYS[1])) or 0
              local lastFillTime = tonumber(redis.call('get', KEYS[2])) or ARGV[1] -- ARGV[1] is currentTime if not set
  
              local newTokens = (ARGV[1] - lastFillTime) * tonumber(ARGV[2])
              currentTokens = math.min(tonumber(ARGV[3]), currentTokens + newTokens)
  
              if currentTokens >= 1 then
                  redis.call('set', KEYS[1], currentTokens - 1)
                  redis.call('set', KEYS[2], ARGV[1])
                  return 1 -- 允许
              else
                  redis.call('set', KEYS[1], currentTokens) -- 即使不通过也要更新
                  redis.call('set', KEYS[2], ARGV[1])
                  return 0 -- 拒绝
              end
          LUA;
  
          // eval($script, $keys, $args, $numKeys)
          // KEYS[1]: currentTokensKey, KEYS[2]: lastFillTimeKey
          // ARGV[1]: currentTime, ARGV[2]: rate, ARGV[3]: capacity
          $result = $this->redis->eval($script, [$currentTokensKey, $lastFillTimeKey], [$currentTime, $rate, $capacity], 2);
  
          return (bool)$result;
      }
  
      /**
       * 漏桶算法限流
       * @param string $key 限流的唯一标识
       * @param int $capacity 桶的容量，即最大允许的缓冲请求数
       * @param float $rate 漏水速率，每秒处理的请求数
       * @return bool 是否允许请求通过
       */
      public function leakyBucket($key, $capacity, $rate): bool
      {
          $currentWaterKey = "rate_limit:leaky_bucket:{$key}:water";
          $lastLeakTimeKey = "rate_limit:leaky_bucket:{$key}:last_leak_time";
  
          $currentTime = microtime(true);
  
          $script = <<<LUA
              local currentWater = tonumber(redis.call('get', KEYS[1])) or 0
              local lastLeakTime = tonumber(redis.call('get', KEYS[2])) or ARGV[1]
  
              local leakedWater = (ARGV[1] - lastLeakTime) * tonumber(ARGV[2])
              currentWater = math.max(0, currentWater - leakedWater)
  
              if currentWater < tonumber(ARGV[3]) then
                  redis.call('set', KEYS[1], currentWater + 1)
                  redis.call('set', KEYS[2], ARGV[1])
                  return 1 -- 允许
              else
                  redis.call('set', KEYS[1], currentWater)
                  redis.call('set', KEYS[2], ARGV[1])
                  return 0 -- 拒绝
              end
          LUA;
  
          $result = $this->redis->eval($script, [$currentWaterKey, $lastLeakTimeKey], [$currentTime, $rate, $capacity], 2);
  
          return (bool)$result;
      }
  }
  
  // 示例用法：
  // $redis = new Redis();
  // $redis->connect('127.0.0.1', 6379);
  // $limiter = new RateLimiter($redis);
  
  // 令牌桶：允许每秒2个请求，桶容量5个（允许短时突发5个请求）
  // if ($limiter->tokenBucket('user:123', 5, 2)) {
  //     echo "令牌桶：请求通过\n";
  // } else {
  //     echo "令牌桶：请求被限流\n";
  // }
  
  // 漏桶：允许每秒处理2个请求，桶容量5个（最多缓冲5个请求）
  // if ($limiter->leakyBucket('api:endpoint', 5, 2)) {
  //     echo "漏桶：请求通过\n";
  // } else {
  //     echo "漏桶：请求被限流\n";
  // }
  ?>

这里用Lua脚本是为了保证get、set、计算的原子性，避免并发问题。

漏桶算法（Leaky Bucket）

想象一个底部有固定漏水速率的桶，水（请求）以不规则的速率流入。如果流入速度快于漏出速度，桶就会满，溢出的水（请求）就会被丢弃。

• 实现思路：
  • 定义桶的容量（bucket_capacity）和漏水速率（leak_rate，每秒漏出多少个请求）。
  • 在Redis中存储当前桶中的水量（current_water）以及上次漏水的时间戳（last_leak_time）。
  • 每次请求到达时，同样通过Redis的Lua脚本原子性地执行：
    1. 计算自上次漏水以来漏出的水量：leaked_water = (current_timestamp - last_leak_time) * leak_rate。
    2. 更新桶中水量：current_water = max(0, current_water - leaked_water)。
    3. 更新last_leak_time = current_timestamp。
    4. 如果current_water < bucket_capacity，则允许请求，并current_water++。
    5. 否则，拒绝请求。

Lua脚本在这里同样至关重要，它确保了读写操作的原子性，避免了竞态条件。

为什么在PHP应用中需要

以上就是《令牌桶与漏桶算法实战解析》的详细内容，更多关于php,redis,请求限流,令牌桶,漏桶的资料请关注golang学习网公众号！