限流器的几种实现方案

2021-06-23 本文已影响0人 DayDayUpppppp

整理常见的几种限流算法

令牌桶算法

令牌桶算法的思路是，如果希望限制的QPS是1000。那么，就设置一个容量是1000的桶，每1/1000秒的恒定速率产生token放入桶中。每个请求达到之后，需要判断桶中是否有token。如果的话，处理请求；没有的话，拒绝服务或等待。
在实际的开发中，因为timer的精度或效率，不一定会直接使用每1/1000秒放一个token的这种策略，比如改为1/100秒放10个token这样的策略。
漏桶算法
存在一个桶（或者队列）把请求不断放入队列中，队列的出口以一个恒定的速度出队。

两个算法的区别是，无论流量多大，漏桶流出的速率都是固定的。但是令牌桶是可能会出现瞬发大量请求的，比如在令牌桶里面有1000个token，一瞬间来了999个请求，那这些请求是可以被瞬间放过的。令牌桶限流算法的伪代码：

int bucket_token_num = 0

// timer的timeout回调
void rate_limit_timeout()
{
    int add_token = get_add_token_by_cfg();
    bucket_token_num += add_token;
    return;
}

bool rate_limit_bucket_is_empty()
{
    if (bucket_token_num <= 0) {return true;}
    return false;
}

void rate_limit_dec_bucket_token()
{
    assert(!rate_limit_bucket_is_empty());
    bucket_token_num--;
}

// 处理消息的接口
int process_req()
{
    if (!rate_limit_bucket_is_empty())
    {
        rate_limit_dec_bucket_token();
        // do-something
    }
}

使用redis限流
额外引入一个节点做限流有一个好处是默认可以做到分布式限流。在redis上面维护一个key，作为已经请求处理请求的数量。
```
cur_num = tonumber(redis.call('get', key) or "0")
if (cur_num + 1 >= limit_num)
{
  return -1;  // 限流
}
else
{
  // 增加计数
  redis.call('INCRBY', key, 1)
  // 如果是0的话，说明当前是一个新的时间窗口，
  // 它的过期时间设置为窗口的过期时间
  if (cur_num == 0)
  {
     redis.call('EXPIRE', key, ttl)
  }
  return 0;  // 不限制
}
```
使用redis的方案做限流，这里用到的是一个同步接口。每个请求被判断是否限流之前，都需要被hold住，同步的查一下redis，拿到结果才知道能不能被处理。

还有一种方案，可以采用预分配的方案，有一个中央节点（qps=1000）假设有3个节点，给每个节点预分配50个，备用30个。请求来了之后，直接从预分配的池子中扣除，当请求开始使用备用池中的token时，节点开始向中央节点再次请求配额。

这种预分配的方案有点是效率比较高，会引入一个问题，如果一个节点上瞬间来了大量请求，消耗掉节点上的所有预分配token和备用token后，在节点再次申请的配额来到之前，请求的处理会被卡住。

限流器的几种实现方案

猜你喜欢

热点阅读