Rate Limiter

1. OverView

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

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

2. Leaky Bucket 与 Token Bucket 算法

2.1 算法描述

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

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

double rate;               // leak rate in calls/s
double burst;              // bucket size in calls

long refreshTime;          // time for last water refresh
double water;              // water count at refreshTime

refreshWater() {
  long  now = getTimeOfDay();
  water = max(0, water- (now - refreshTime)*rate); // 水随着时间流逝，不断流走，最多就流干到0.
  refreshTime = 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添加间隔(即上例那个10ms)，初始token数量 = burst，有算法保证系统总是相对平滑。
• Bursty， burst = rate或另外的参数设置，初始token数量 = 0 ，当系统冷了一段时间，支持突发到burst。

Guava以micros为时间单位，计算token的变化。

4. 多个滑动的Buckets

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

5. 两种算法比较

Leaky Bucket只维持一个桶内水量，每个请求过来时，一是水量加一，二是根据过去的时间减少水量。
滑动Buckets 维持多个桶，每个请求过来时，一是计算出当前桶，当前桶水量加一，二是获得前面多个bucket的水量合计，三是可能需要滚动桶。

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

个人比较倾向Leaky Bucket。

6. 集群而非单机的Rate Limiter

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