限流器的几种实现方案

整理常见的几种限流算法

• 令牌桶算法
  

  令牌桶算法的思路是，如果希望限制的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后，在节点再次申请的配额来到之前，请求的处理会被卡住。

相关的一些参考：

1. https://www.cyhone.com/articles/analisys-of-golang-rate/
2. https://chai2010.cn/advanced-go-programming-book/ch5-web/ch5-06-ratelimit.html
3. https://github.com/yangwenmai/ratelimit
4. https://pandaychen.github.io/2020/09/21/A-DISTRIBUTE-GOREDIS-RATELIMITER-ANALYSIS/