Rate Limiter

1. OverView

做限流的时候，可以简单的控制并发，如果要更准确的控制TPS，则需要Leaky Bucket--有漏洞的木桶算法 或者经典的Sliding Window算法。

Leaky Bucket 与 Sliding Windows的比较

2. Leaky Bucket 与 Token Bucket 算法

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

可见这里有两个变量，一个是桶的大小，代表流量最高的时候可以存多少水(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可拿了就拒绝服务。

3. 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. Sliding Windows