Redis的6种限流算法
·
1. 固定窗口计数算法（Fixed Window Counter）
- 原理：将时间划分为固定的窗口，如 1 秒、1 分钟等。在每个时间窗口内，计数器记录请求次数。如果请求次数超过设定的阈值，则触发限流。
- 优点：实现简单，适合对短时间内的流量进行限制。
- 缺点：在时间窗口边界，可能会出现瞬时流量峰值。例如，一个窗口结束时有大量请求，紧接着下一个窗口开始时也有大量请求，导致短时间内的实际请求数量远超限制。
-
<?php class FixedWindowRateLimiter { private $redis; private $rateLimitKey; private $timeWindow; private $maxRequests; /** * 构造函数，初始化Redis连接和限流参数 * * @param string $host Redis服务器地址 * @param int $port Redis服务器端口 * @param int $timeWindow 时间窗口的长度（秒） * @param int $maxRequests 时间窗口内的最大请求数 */ public function __construct($host = '127.0.0.1', $port = 6379, $timeWindow = 60, $maxRequests = 100) { $this->redis = new Redis(); $this->redis->connect($host, $port); $this->timeWindow = $timeWindow; $this->maxRequests = $maxRequests; $this->rateLimitKey = 'rate_limit:' . date('Y-m-d H:i') . ':'; } /** * 检查请求是否允许通过限流 * * @param string $clientId 客户端唯一标识符 * @return bool 返回true表示请求被允许，false表示请求被拒绝 */ public function isRequestAllowed($clientId) { $currentWindowKey = $this->rateLimitKey . $clientId; // 获取当前窗口的请求次数 $requestCount = $this->redis->get($currentWindowKey); if ($requestCount === false) { // 初始化当前窗口的请求次数为1，并设置过期时间为timeWindow $this->redis->set($currentWindowKey, 1, $this->timeWindow); return true; } else { // 如果请求次数超过最大限制，拒绝请求 if ($requestCount >= $this->maxRequests) { return false; } // 增加当前窗口的请求次数 $this->redis->incr($currentWindowKey); return true; } } } // 示例用法 $rateLimiter = new FixedWindowRateLimiter('127.0.0.1', 6379, 60, 10); // 1分钟窗口，最多10次请求 $clientId = 'user_123'; // 这是一个唯一标识符，例如用户ID或IP地址 if ($rateLimiter->isRequestAllowed($clientId)) { echo "请求被允许。\n"; // 执行实际请求的操作 } else { echo "请求被拒绝。您已达到限流上限。\n"; // 返回错误响应，提示限流 }代码解析
-
构造函数：
- 初始化Redis连接。
- 设置时间窗口长度（例如60秒）和最大请求次数（例如10次）。
- 构建限流键（
rateLimitKey），用于存储请求计数。
-
isRequestAllowed方法：- 获取当前时间窗口的请求计数。
- 如果计数不存在（首次请求），初始化计数为1，并设置过期时间为时间窗口长度。
- 如果请求次数未达到最大请求数，增加计数并允许请求。
- 如果请求次数达到或超过最大请求数，拒绝请求。
-
2. 滑动窗口计数算法（Sliding Window Counter）
- 原理：与固定窗口计数不同，滑动窗口算法在时间上是滑动的，而不是固定的。它根据请求的时间戳动态调整窗口的起点和终点，只统计当前窗口内的请求数量。
- 优点：可以更平滑地统计请求，避免固定窗口边界效应引起的瞬时流量峰值。
- 缺点：实现相对复杂，需要更多的存储来维护请求的时间戳数据。
- 滑动窗口算法的实现需要在 Redis 中记录每个请求的时间戳，并通过这些时间戳计算当前窗口内的请求数量。为了实现这个算法，我们将使用 Redis 的
ZSET（有序集合）数据结构来存储请求时间戳。 -
<?php class SlidingWindowRateLimiter { private $redis; private $rateLimitKey; private $timeWindow; private $maxRequests; /** * 构造函数，初始化Redis连接和限流参数 * * @param string $host Redis服务器地址 * @param int $port Redis服务器端口 * @param int $timeWindow 时间窗口的长度（秒） * @param int $maxRequests 时间窗口内的最大请求数 */ public function __construct($host = '127.0.0.1', $port = 6379, $timeWindow = 60, $maxRequests = 100) { $this->redis = new Redis(); $this->redis->connect($host, $port); $this->timeWindow = $timeWindow; $this->maxRequests = $maxRequests; $this->rateLimitKey = 'sliding_window_rate_limit:'; } /** * 检查请求是否允许通过限流 * * @param string $clientId 客户端唯一标识符 * @return bool 返回true表示请求被允许，false表示请求被拒绝 */ public function isRequestAllowed($clientId) { $currentTime = microtime(true) * 1000; // 当前时间的毫秒数 $windowStart = $currentTime - ($this->timeWindow * 1000); // 计算当前滑动窗口的开始时间 $key = $this->rateLimitKey . $clientId; // 删除时间窗口之外的请求记录 $this->redis->zRemRangeByScore($key, 0, $windowStart); // 获取当前窗口内的请求数量 $currentRequestCount = $this->redis->zCard($key); if ($currentRequestCount < $this->maxRequests) { // 允许请求，将当前请求的时间戳添加到有序集合中 $this->redis->zAdd($key, $currentTime, $currentTime); // 设置过期时间以避免无用数据长期占用内存 $this->redis->expire($key, $this->timeWindow); return true; } else { // 请求被拒绝，因为请求数量超出限流阈值 return false; } } } // 示例用法 $rateLimiter = new SlidingWindowRateLimiter('127.0.0.1', 6379, 60, 10); // 1分钟窗口，最多10次请求 $clientId = 'user_123'; // 这是一个唯一标识符，例如用户ID或IP地址 if ($rateLimiter->isRequestAllowed($clientId)) { echo "请求被允许。\n"; // 执行实际请求的操作 } else { echo "请求被拒绝。您已达到限流上限。\n"; // 返回错误响应，提示限流 }代码解析
-
构造函数：
- 初始化 Redis 连接。
- 设置时间窗口的长度（例如 60 秒）和最大请求数（例如 10 次）。
- 构建限流键（
rateLimitKey），用于存储请求的时间戳。
-
isRequestAllowed方法：- 获取当前时间的毫秒数，并计算当前滑动窗口的开始时间。
- 使用 Redis 的
zRemRangeByScore方法，删除时间窗口之前的请求记录。 - 使用
zCard方法获取当前窗口内的请求数量。 - 如果请求数量小于最大限制，则允许请求，并将当前时间戳添加到有序集合中，设置过期时间以减少 Redis 内存占用。
- 如果请求数量超过最大限制，则拒绝请求。
-
3. 漏桶算法（Leaky Bucket Algorithm）
- 原理：漏桶算法将请求放入一个固定容量的桶中，请求以固定的速率从桶中流出。如果桶满了，新的请求就会被丢弃。
- 优点：输出速率稳定，适合控制数据流的平均传输速率。
- 缺点：突发流量在短时间内会被丢弃，无法适应突发流量。
<?php class LeakyBucketRateLimiter { private $redis; private $rateLimitKey; private $bucketCapacity; private $leakRate; // 单位时间内允许的请求数 private $lastLeakTime; // 上一次漏水的时间 /** * 构造函数，初始化Redis连接和限流参数 * * @param string $host Redis服务器地址 * @param int $port Redis服务器端口 * @param int $bucketCapacity 桶的容量（即允许的最大请求数） * @param int $leakRate 请求漏出的速率（每秒钟允许的请求数） */ public function __construct($host = '127.0.0.1', $port = 6379, $bucketCapacity = 100, $leakRate = 10) { $this->redis = new Redis(); $this->redis->connect($host, $port); $this->bucketCapacity = $bucketCapacity; $this->leakRate = $leakRate; $this->rateLimitKey = 'leaky_bucket:'; } /** * 检查请求是否允许通过限流 * * @param string $clientId 客户端唯一标识符 * @return bool 返回true表示请求被允许，false表示请求被拒绝 */ public function isRequestAllowed($clientId) { $currentTime = time(); $key = $this->rateLimitKey . $clientId; // 获取当前桶中的请求数和上次漏水的时间 $bucketInfo = $this->redis->hGetAll($key); $currentBucketSize = isset($bucketInfo['size']) ? (int)$bucketInfo['size'] : 0; $lastLeakTime = isset($bucketInfo['last_leak_time']) ? (int)$bucketInfo['last_leak_time'] : $currentTime; // 计算漏水量 $elapsedTime = $currentTime - $lastLeakTime; $leakedCount = (int)($elapsedTime * $this->leakRate); // 更新桶的大小 $newBucketSize = max(0, $currentBucketSize - $leakedCount); // 更新漏水时间 $this->redis->hSet($key, 'last_leak_time', $currentTime); if ($newBucketSize < $this->bucketCapacity) { // 如果桶未满，允许请求 $this->redis->hSet($key, 'size', $newBucketSize + 1); return true; } else { // 如果桶满了，拒绝请求 return false; } } } // 示例用法 $rateLimiter = new LeakyBucketRateLimiter('127.0.0.1', 6379, 10, 1); // 桶容量为10，每秒1个请求的速率 $clientId = 'user_123'; // 这是一个唯一标识符，例如用户ID或IP地址 if ($rateLimiter->isRequestAllowed($clientId)) { echo "请求被允许。\n"; // 执行实际请求的操作 } else { echo "请求被拒绝。您已达到限流上限。\n"; // 返回错误响应，提示限流 }代码解析
-
构造函数：
- 初始化 Redis 连接。
- 设置桶的容量（
bucketCapacity）和漏出的速率（leakRate）。 - 构建限流键（
rateLimitKey），用于存储桶的状态。
-
isRequestAllowed方法：- 获取当前时间戳。
- 计算自上次漏水后的时间间隔。
- 计算漏水量（即在时间间隔内漏出的请求数）。
- 更新桶的大小，移除已经漏出的请求。
- 如果桶未满，则允许新的请求进入桶，并增加桶的当前大小。
- 如果桶满了，则拒绝请求。
使用场景
这种实现可以用于需要平稳控制请求速率的场景，比如限制API请求的速率或限速下载。通过控制桶的容量和漏出的速率，可以实现不同的限流策略。
-
4. 令牌桶算法（Token Bucket Algorithm）
- 原理：令牌桶算法维持一个令牌桶，系统以固定的速率向桶中添加令牌。每个请求需要消耗一个令牌才能被处理。如果桶中没有足够的令牌，请求就会被限流或等待。
- 优点：允许一定的突发流量（当桶中有积累的令牌时），在控制请求速率的同时又能适应突发流量。
- 缺点：突发流量过大时，可能会快速消耗掉所有的令牌，导致后续请求被限流。
<?php class TokenBucketRateLimiter { private $redis; private $rateLimitKey; private $bucketCapacity; // 令牌桶的容量（最大令牌数） private $tokenRate; // 令牌生成速率（每秒生成的令牌数） /** * 构造函数，初始化Redis连接和限流参数 * * @param string $host Redis服务器地址 * @param int $port Redis服务器端口 * @param int $bucketCapacity 令牌桶的容量（最大令牌数） * @param int $tokenRate 令牌生成速率（每秒生成的令牌数） */ public function __construct($host = '127.0.0.1', $port = 6379, $bucketCapacity = 100, $tokenRate = 10) { $this->redis = new Redis(); $this->redis->connect($host, $port); $this->bucketCapacity = $bucketCapacity; $this->tokenRate = $tokenRate; $this->rateLimitKey = 'token_bucket:'; } /** * 检查请求是否允许通过限流 * * @param string $clientId 客户端唯一标识符 * @return bool 返回true表示请求被允许，false表示请求被拒绝 */ public function isRequestAllowed($clientId) { $currentTime = time(); $key = $this->rateLimitKey . $clientId; // 获取当前令牌数和上次令牌更新的时间 $bucketInfo = $this->redis->hGetAll($key); $currentTokenCount = isset($bucketInfo['tokens']) ? (int)$bucketInfo['tokens'] : $this->bucketCapacity; $lastTokenTime = isset($bucketInfo['last_token_time']) ? (int)$bucketInfo['last_token_time'] : $currentTime; // 计算自上次令牌添加后的时间差，计算应添加的令牌数量 $elapsedTime = $currentTime - $lastTokenTime; $newTokens = (int)($elapsedTime * $this->tokenRate); // 更新令牌数量 $newTokenCount = min($this->bucketCapacity, $currentTokenCount + $newTokens); // 更新最后一次添加令牌的时间 $this->redis->hSet($key, 'last_token_time', $currentTime); if ($newTokenCount > 0) { // 如果桶中有令牌，允许请求，并扣除一个令牌 $this->redis->hSet($key, 'tokens', $newTokenCount - 1); return true; } else { // 如果没有令牌，拒绝请求 return false; } } } // 示例用法 $rateLimiter = new TokenBucketRateLimiter('127.0.0.1', 6379, 10, 1); // 桶容量为10，每秒1个令牌 $clientId = 'user_123'; // 这是一个唯一标识符，例如用户ID或IP地址 if ($rateLimiter->isRequestAllowed($clientId)) { echo "请求被允许。\n"; // 执行实际请求的操作 } else { echo "请求被拒绝。您已达到限流上限。\n"; // 返回错误响应，提示限流 }代码解析
-
构造函数：
- 初始化 Redis 连接。
- 设置令牌桶的容量（
bucketCapacity）和令牌生成速率（tokenRate）。 - 构建限流键（
rateLimitKey），用于存储令牌桶的状态。
-
isRequestAllowed方法：- 获取当前时间戳。
- 从 Redis 获取当前令牌数和上次令牌更新的时间。
- 计算自上次更新后的时间差，并根据令牌生成速率计算新的令牌数。
- 更新令牌数和上次更新的时间。
- 如果桶中有令牌，允许请求并扣除一个令牌；否则拒绝请求。
使用场景
令牌桶算法适用于需要平稳流量控制但允许突发流量的场景，比如API速率限制、网络流量控制等。通过设置合理的桶容量和令牌生成速率，可以在流量控制和突发流量适应之间找到平衡。
-
5. 计数器（Counter）
- 原理：计数器是最简单的限流方式。它通过简单地计数一段时间内的请求数量来实现限流，比如在一分钟内只能允许100个请求。
- 优点：实现简单，适用于简单的限流需求。
- 缺点：对时间窗口边界的请求不敏感，容易出现流量突增的问题。
<?php class CounterRateLimiter { private $redis; private $rateLimitKey; private $timeWindow; // 时间窗口的大小（秒） private $maxRequests; // 时间窗口内允许的最大请求数 /** * 构造函数，初始化Redis连接和限流参数 * * @param string $host Redis服务器地址 * @param int $port Redis服务器端口 * @param int $timeWindow 时间窗口的大小（秒） * @param int $maxRequests 时间窗口内允许的最大请求数 */ public function __construct($host = '127.0.0.1', $port = 6379, $timeWindow = 60, $maxRequests = 100) { $this->redis = new Redis(); $this->redis->connect($host, $port); $this->timeWindow = $timeWindow; $this->maxRequests = $maxRequests; $this->rateLimitKey = 'counter_rate_limiter:'; } /** * 检查请求是否允许通过限流 * * @param string $clientId 客户端唯一标识符 * @return bool 返回true表示请求被允许，false表示请求被拒绝 */ public function isRequestAllowed($clientId) { $key = $this->rateLimitKey . $clientId; // 获取当前计数器值 $currentCount = $this->redis->get($key); if ($currentCount === false) { // 如果计数器不存在，初始化计数器和过期时间 $this->redis->set($key, 1, $this->timeWindow); return true; } if ($currentCount < $this->maxRequests) { // 增加计数器值 $this->redis->incr($key); return true; } else { // 达到请求上限，拒绝请求 return false; } } } // 示例用法 $rateLimiter = new CounterRateLimiter('127.0.0.1', 6379, 60, 100); // 一分钟内最多允许100个请求 $clientId = 'user_123'; // 这是一个唯一标识符，例如用户ID或IP地址 if ($rateLimiter->isRequestAllowed($clientId)) { echo "请求被允许。\n"; // 执行实际请求的操作 } else { echo "请求被拒绝。您已达到限流上限。\n"; // 返回错误响应，提示限流 } -
代码解析
-
构造函数:
- 初始化 Redis 连接。
- 设置时间窗口的大小（
timeWindow）和时间窗口内允许的最大请求数（maxRequests）。 - 构建限流键（
rateLimitKey），用于存储计数器的状态。
-
isRequestAllowed方法:- 从 Redis 获取当前计数器值。
- 如果计数器不存在（即当前时间窗口内没有请求），则初始化计数器为1并设置过期时间（等于时间窗口大小）。
- 如果当前计数器值小于最大请求数，增加计数器值并允许请求。
- 如果计数器值达到最大请求数，拒绝请求。
使用场景
计数器算法适用于一些简单的限流需求场景，例如防止用户短时间内的频繁操作。它的实现简单，适合不需要平滑流量控制的情况。尽管存在时间窗口边界效应，但在某些情况下可以忽略不计，或通过滑动窗口计数算法等更复杂的限流策略进行优化。
- 6. 滑动窗口日志算法（Sliding Window Log）
- 原理：维护一个请求时间戳的日志，每次请求到来时将其时间戳记录在日志中，并根据设定的时间窗口移除过期的时间戳。当前窗口内时间戳的数量即为请求数量。
- 优点：精确统计时间窗口内的请求数量，避免了固定窗口边界的问题。
- 缺点：需要存储所有请求的时间戳，内存开销大，不适合高频请求场景。
-
<?php class SlidingWindowLogRateLimiter { private $redis; private $rateLimitKey; private $timeWindow; // 时间窗口大小（秒） private $maxRequests; // 时间窗口内允许的最大请求数 /** * 构造函数，初始化Redis连接和限流参数 * * @param string $host Redis服务器地址 * @param int $port Redis服务器端口 * @param int $timeWindow 时间窗口大小（秒） * @param int $maxRequests 时间窗口内允许的最大请求数 */ public function __construct($host = '127.0.0.1', $port = 6379, $timeWindow = 60, $maxRequests = 100) { $this->redis = new Redis(); $this->redis->connect($host, $port); $this->timeWindow = $timeWindow; $this->maxRequests = $maxRequests; $this->rateLimitKey = 'sliding_window_log:'; } /** * 检查请求是否允许通过限流 * * @param string $clientId 客户端唯一标识符 * @return bool 返回true表示请求被允许，false表示请求被拒绝 */ public function isRequestAllowed($clientId) { $key = $this->rateLimitKey . $clientId; $now = microtime(true); // 当前时间的时间戳（秒级，带小数） // 开始 Redis 事务 $this->redis->multi(); // 移除时间窗口外的过期时间戳 $this->redis->zRemRangeByScore($key, 0, $now - $this->timeWindow); // 获取当前窗口内的请求数量 $requestCount = $this->redis->zCard($key); if ($requestCount < $this->maxRequests) { // 当前请求数未超过限制，允许请求，记录当前请求时间戳 $this->redis->zAdd($key, $now, $now); // 设置key的过期时间为时间窗口大小 $this->redis->expire($key, $this->timeWindow); // 执行事务 $this->redis->exec(); return true; } else { // 达到请求上限，拒绝请求 $this->redis->exec(); return false; } } } // 示例用法 $rateLimiter = new SlidingWindowLogRateLimiter('127.0.0.1', 6379, 60, 100); // 一分钟内最多允许100个请求 $clientId = 'user_123'; // 这是一个唯一标识符，例如用户ID或IP地址 if ($rateLimiter->isRequestAllowed($clientId)) { echo "请求被允许。\n"; // 执行实际请求的操作 } else { echo "请求被拒绝。您已达到限流上限。\n"; // 返回错误响应，提示限流 }代码解析
-
构造函数:
- 初始化 Redis 连接。
- 设置时间窗口的大小（
timeWindow）和时间窗口内允许的最大请求数（maxRequests）。 - 构建限流键（
rateLimitKey），用于存储请求日志的状态。
-
isRequestAllowed方法:- 获取当前时间的时间戳（
$now）。 - 使用 Redis 的事务（
multi和exec）来确保操作的原子性。 - 删除时间窗口外的过期时间戳，确保只统计当前窗口内的请求数量。
- 检查当前窗口内的请求数量是否小于最大请求数。
- 如果小于最大请求数，允许请求并记录当前请求的时间戳；否则，拒绝请求。
-
使用场景
滑动窗口日志算法适用于需要精确控制请求频率的场景，例如API请求限流、金融交易频率控制等。由于它能够精确统计时间窗口内的请求数量，可以有效防止因时间窗口切换导致的流量突增问题。不过，由于需要存储所有请求的时间戳，因此不适合高频请求的场景。在这些场景中，可以考虑使用滑动窗口计数算法或其他更高效的限流算法。
-
7. Redis Cell（漏桶算法的 Redis 实现）
- 原理：Redis Cell 是 Redis 提供的一种限流方式，基于漏桶算法实现。它通过 Redis 数据结构来模拟漏桶机制，具有高效性和持久性。
- 优点：性能高，易于在分布式环境下使用。
- 缺点：依赖 Redis，增加了外部系统的依赖。
-
实现原理
- 桶容量: 维护一个 Redis 键作为桶，记录当前桶中的水量（请求数）。
- 漏水速率: 使用 Redis 键的过期时间来模拟桶的漏水速率。
- 请求处理: 每当有请求到来时，检查桶是否有足够的容量。如果有足够的容量，则允许请求，并减少桶中的水量；如果没有足够的容量，则拒绝请求。
<?php class LeakyBucketRateLimiter { private $redis; private $bucketKey; private $bucketCapacity; // 桶的容量（请求数） private $leakRate; // 漏水速率（请求数/秒） /** * 构造函数，初始化Redis连接和限流参数 * * @param string $host Redis服务器地址 * @param int $port Redis服务器端口 * @param int $bucketCapacity 桶的容量（请求数） * @param float $leakRate 漏水速率（请求数/秒） */ public function __construct($host = '127.0.0.1', $port = 6379, $bucketCapacity = 100, $leakRate = 1) { $this->redis = new Redis(); $this->redis->connect($host, $port); $this->bucketCapacity = $bucketCapacity; $this->leakRate = $leakRate; $this->bucketKey = 'leaky_bucket:'; } /** * 检查请求是否允许通过限流 * * @param string $clientId 客户端唯一标识符 * @return bool 返回true表示请求被允许，false表示请求被拒绝 */ public function isRequestAllowed($clientId) { $key = $this->bucketKey . $clientId; $currentTime = microtime(true); // 开始 Redis 事务 $this->redis->multi(); // 获取当前桶的状态 $bucketData = $this->redis->hMGet($key, ['timestamp', 'water']); $lastTimestamp = isset($bucketData['timestamp']) ? $bucketData['timestamp'] : $currentTime; $currentWater = isset($bucketData['water']) ? $bucketData['water'] : 0; // 计算桶漏水后剩余的水量 $elapsedTime = $currentTime - $lastTimestamp; $leakedWater = $elapsedTime * $this->leakRate; $newWater = max(0, $currentWater - $leakedWater); if ($newWater < $this->bucketCapacity) { // 桶中有足够空间，允许请求 $newWater += 1; // 添加请求 $this->redis->hMSet($key, ['timestamp' => $currentTime, 'water' => $newWater]); $this->redis->expire($key, ceil($this->bucketCapacity / $this->leakRate)); $this->redis->exec(); return true; } else { // 桶满，拒绝请求 $this->redis->exec(); return false; } } } // 示例用法 $rateLimiter = new LeakyBucketRateLimiter('127.0.0.1', 6379, 100, 1); // 桶容量为100，漏水速率为1请求/秒 $clientId = 'user_123'; // 这是一个唯一标识符，例如用户ID或IP地址 if ($rateLimiter->isRequestAllowed($clientId)) { echo "请求被允许。\n"; // 执行实际请求的操作 } else { echo "请求被拒绝。桶已满。\n"; // 返回错误响应，提示限流 }代码解析
-
构造函数:
- 初始化 Redis 连接。
- 设置桶的容量（
bucketCapacity）和漏水速率（leakRate）。
-
isRequestAllowed方法:- 获取当前时间（
$currentTime）。 - 从 Redis 中获取桶的当前状态（时间戳和水量）。
- 计算自上次请求以来经过的时间，并根据漏水速率计算漏掉的水量。
- 更新桶中的水量，并检查是否有足够的容量来接受新请求。
- 如果桶中有足够的空间，允许请求并更新桶的状态；否则，拒绝请求。
使用场景
漏桶算法适用于需要控制请求的流量速率的场景，例如 API 请求限流、流量控制、带宽管理等。该实现可以有效控制请求的速率，适合需要高性能和简单实现的场景。然而，在高并发请求或极端负载下，Redis 的内存开销和性能开销可能成为瓶颈。
- 获取当前时间（
- 获取当前时间的时间戳（
更多推荐
37
0- 0
已为社区贡献1条内容
所有评论(0)