有时候我们会对接一个弱鸡后端服务，只能支持很低的并发量。为了防止世界被破坏，我们需要对用户请求做限流，避免后端服务被打垮。

限流器有多种算法，比较常用的如令牌桶、漏桶、滑动窗口等。本文讲的是滑动窗口算法。

滑动窗口算法限流最适合的需求场景，就是X秒内，最多允许Y个请求。用漏桶和令牌桶算法我还没想出来应该咋能精确实现这一需求。

滑动窗口的原理网上一搜一大堆，这里就不描述了。我们直接来讲：

实现方法

如何定义限流规则呢？

有以下参数决定一个限流规则：

private $window; // int 窗口大小，单位为秒
private $count; // int 在窗口时间内最多允许多少个请求
private $precision; // int 滑动窗口精度。根据窗口大小适当调整，窗口小（比如60以下），则为1，
                    // 窗口越大，此值可以适当调大，以降低存储的请求数信息大小
private $resourceIdentity; // 需要限流保护的资源标识，在本例中就是这个后端接口

如何描述请求数信息呢？

首先，我们搞个字典，以unix时间（秒）为key来统计请求数。如果窗口太大，达到几百几千秒，则可以适当降低精度，以若干秒为单位来统计请求数。那么请求数信息就会是这样：

// 当前时间为 1598268380，统计精度为1秒
$rateLimitInfo = [
    ...
    1598268377 => 3, // 2020-08-24 19:26:17 (CST) 有三个请求
    1598268378 => 1, // 猜猜看啥意思
    1598268379 => 2,
    1598268380 => 1,
];
// 或者统计精度为3秒
$rateLimitInfo = [
    ...
    1598268375 => 3, // 1598268377\1598268376\1598268375 这三秒都归到此处
    1598268378 => 4, // 1598268380\1598268379\1598268378 这三秒都归到此处
]

如何存储请求数信息呢？

我们将这字典的key作为缓存服务的key（当然，需要根据限流规则标识、限流对象标识等内容，加上前缀标记），value作为缓存服务的value，存入缓存服务，每次请求过来时，根据设置的滑动窗口大小，生成所有位于窗口内的key值，并调用缓存服务的getMulti方法获得所有的key对应的value，就得到了当前窗口内的所有时间的请求数了。

// 计算当前时间（根据精度归一化后的时间）
$currentTime = floor((int)time() / $this->precision) * $this->precision; 

// 生成时间窗口内所有的key
$cacheKeyTime = $currentTime;
$earliestTime = $currentTime - $this->window;
$cacheKeyList = [];
while ($cacheKeyTime > $earliestTime) {
    $cacheKeyList[] = $this->generateCacheKey($cacheKeyTime, $callerIdentity);
    $cacheKeyTime -= $this->precision;
}

// 调用缓存服务的getMulti方法获取
$rateLimitInfo = $this->memcached->getMulti($cacheKeyList);
if (array_sum($rateLimitInfo) >= $this->count) {
    // 请求数超限啦，滚犊子吧
}

如果上面请求数校验通过了，则需要累加请求数。Memcached有increment方法，可以原子地增加缓存中的值，如果缓存值不存在，则设置一个初始值。

$this->memcached->increment(
    $this->generateCacheKey($currentTime, $callerIdentity), // 缓存的key，和时间相关
    1, // 自增多少，当然是自增1
    1, // 如果没有此key，初始值为多少，当然是1
    $this->window // 过期时间
);

这里有个关键的地方，就是缓存过期时间，只有在没有此key需要新增记录的时候，这个参数才有用。也就是说，如果已存在key，调用increment方法时并不会延长过期时间。

那么我们将过期时间设置为窗口大小，就很好理解了，我们获取已有请求数时，并不会看当前时间窗口之外的数据，那么它们过期了，也无所谓。

以上的检查+自增，就构成了限流器的acquire方法。此方法还需要接受一个参数，即请求对象标识。这个标识可以是用户IP、或者业务上的用户ID。甚至可以是一个固定字符串，使其成为全局的限流。

完整代码为：

public function __construct(
    string $resourceIdentity,
    int $window,
    int $count,
    int $precision = 1) {
    $this->window = $window < 0 ? 0 : $window;
    $this->count = $count;
    $this->resourceIdentity = $resourceIdentity;
    $this->precision = $precision;
    $this->memcached = new Memcached( .... );
}

public function acquire(string $callerIdentity) : bool {
    // 计算当前时间（根据精度归一化后的时间）
    $currentTime = floor((int)time() / $this->precision) * $this->precision; 

    // 生成时间窗口内所有的key
    $cacheKeyTime = $currentTime;
    $earliestTime = $currentTime - $this->window;
    $cacheKeyList = [];
    while ($cacheKeyTime > $earliestTime) {
        $cacheKeyList[] = $this->generateCacheKey($cacheKeyTime, $callerIdentity);
        $cacheKeyTime -= $this->precision;
    }

    // 调用缓存服务的getMulti方法获取
    $rateLimitInfo = $this->memcached->getMulti($cacheKeyList);
    if (array_sum($rateLimitInfo) >= $this->count) {
        // 请求数超限
        return false;
    }
    $this->memcached->increment(
    $this->generateCacheKey($currentTime, $callerIdentity), // 缓存的key，和时间相关
        1, // 自增多少，当然是自增1
        1, // 如果没有此key，初始值为多少，当然是1
        $this->window // 过期时间
    );
    return true;
}

private function generateCacheKey(int $currentTime, string $callerIdentity) : string {
    return __CLASS__ . $this->resourceIdentity . '_' . $callerIdentity . '_' . $currentTime;
}

标签: none

添加新评论

captcha
请输入验证码