Rate Limiter

Leacky Bucket 与 Token Bucket 算法

做限流的时候，可以简单的控制并发，如果要更准确的控制TPS，控制一秒之内发生的事情，则需要Leacky Bucket--有漏洞的木桶算法。

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

可见这里有两个变量，一个是桶的大小，代表流量最高的时候可以有多少水(burst)，另一个是水桶漏洞的大小(rate)，伪代码如下：

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

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

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

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

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

Guava RateLimiter

Google Guava中的RateLimiter，实际上就实现了Token Bucket的算法。Google看到有些开源项目，把自己自写写的ratelimiter换成google的。

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

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

• Bursty的默认初始token数量是0，burst=rate或自行特别设置。
• WarmingUp，burst = warmup时间/加水间隔， 初始token = burst。