Rate Limiter

1. OverView

做限流(Rate Limit/Throttling)的时候，除了简单的控制并发如果要更准确的控制TPS，简单的做法是维护一个单位时间内的Counter，如判断单位时间已经过去，则将Counter置零。此做法被认为没有很好的处理单位时间的边界，比如可以在前一秒的最后一毫秒里和下一秒的第一毫秒触发最大的请求数，用另一个角度看，在2毫秒内发生了两倍的TPS。

因此更平滑的算法如Leaky Bucket--有漏洞的木桶算法，又或者将原来单位时间内单一的Counter拆分为单位时间内多个滑动的Buckets。

2. Leaky Bucket 与 Token Bucket 算法

2.1 算法描述

漏木桶算法简单的想象有一个木桶，有新请求就是不断的倒水进来，然后桶底下有个洞，按照固定的速率把水漏走，如果水进来的速度比漏走的快，桶可能就会满了，然后就拒绝请求。

可见这里有两个变量，一个是桶的大小，支持流量突发增多时可以存多少的水(burst)，另一个是水桶漏洞的大小(rate)，可以简单的让burst等于rate，也可以让burst更大接收更多突发请求，伪代码如下：

double rate;               // leak rate in calls/s given by the regulator
double burst;              // bucket size in calls (normally constant)

long long int refreshtime; // time for last water refresh
double water;              // water at refreshtime

refreshWater() {
  long long int now = gettimeofday();
  water = max(0, water- (now - time)*rate); // 水随着时间流逝，不断流走，最多就流干到0.
  time = now;
}

bool permissionGranted() {
  refreshWater();
  if (water < burst) { // 水桶还没满，继续加1
    water ++;
    return true;
  }
  else {
    return false;
  }
}

Token Bucket 是与 Leaky Bucket 效果一样但方向相反的算法，更加容易理解。随着时间流逝，系统会按速率 1/rate 的时间间隔(如果rate=100，则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反，有个水龙头在不断的加水)，如果桶已经满了就不再加了。新请求来临时，会各自拿走一个Token，如果没有Token可拿了就拒绝服务。

2.2 Guava RateLimiter

Google Guava中的RateLimiter，实际上就实现了Token Bucket的算法。Google搜索看到有些开源项目的issues，要把自己写的Limiter换成了它。

它支持两种获取permits接口，一种是如果拿不到立刻返回false，一种会阻塞等待一段时间看能不能拿到。

Leacky Bucket算法默认一开始水桶是空的，可以立即就接收最多burst的请求，而Token Bucket就要设置初始Token的数量。因此RateLimiter有两个子类，一个是WarmingUp，一个是Bursty。

• WarmingUp，burst = warmup时间/固定token添加间隔(即1s/rate)，初始token数量 = burst，但有一定的算法保证系统平滑。
• Bursty， burst = rate或另外的参数设置，初始token数量 = 0 。

4. 多个滑动的Buckets

不知道这种算法的业界命名是什么，原理也很简单，比如将原来的1秒划分为10个bucket。每个请求到来时，计算出当前时间属于哪个bucket，counter+1，然后计算当前bucket加上前9个bucket的值的总和看看是否达到TPS。

5. 两种算法比较

• 滑动Buckets比Leaky Bucket需要更多的Counter。
• Leaky Bucket支持当系统有一段时间清闲之后，能接收一个较大的burst值，当然，也可以把burst值调到和rate一样大来禁止它。
• 滑动Buckets需要实现滑动算法。

6. 集群而非单机的Rate Limiter

用上Redis或Memcached，哪种算法都不会很难。但首先，你要有个Redis。