最初是因为要配置nginx的限速所以想研究一下限速的方法,nginx里用到了Leaky Bucket算法,下面记一下漏桶(Leaky Bucket)和令牌桶(Token Bucket)算法的区别。

漏桶算法

漏桶算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。

这里有一个简单的golang的漏桶算法的实现:https://github.com/uber-go/ratelimit

漏桶算法的实现很简单,就是设置一个速率,然后记录一个上一次请求的时间,当一个请求来的时候,判断距离上一个请求的时间是否超过了1/rate,如果没有超过,那么就等够时间,然后再执行。

这样能够强行控制请求的速率,但是也有两个问题,就是太依赖与上一次请求的时间,当上一次执行的时间是很久以前时,那么如果立即执行请求,有两种情况需要考虑:

  1. 假如系统空转很久了,然后强制以一定的速率来处理是否合适,是否可以提高速度
  2. 假如系统太忙了,比如系统刚启动,是不是应该把速度降下来

就是可能会导致对系统利用不足或者过载。

令牌桶算法

令牌桶算法通过发放令牌,根据令牌的rate频率做请求频率限制,容量限制等。

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。

令牌桶算法的基本过程如下:

  1. 每秒会有 r 个令牌放入桶中,或者说,每过 1/r 秒桶中增加一个令牌;
  2. 桶中最多存放 b 个令牌,如果桶满了,新放入的令牌会被丢弃;
  3. 当一个 n 字节的数据包到达时,消耗 n 个令牌,然后发送该数据包;
  4. 如果桶中可用令牌小于 n,则该数据包将被缓存或丢弃。

令牌桶算法相对于漏桶算法,由于存有令牌,所以可以应对一定量的突发状况。

Guava Ratelimter的实现

https://github.com/google/guava/blob/v18.0/guava/src/com/google/common/util/concurrent/SmoothRateLimiter.java#L124:L130

RateLimter对于上面说的简单的漏桶算法加了一些优化。可以一定程度上解决对系统的利用不足和过载的问题。

RateLimter存了一个storedPermits,当请求过来的时候,可以从storedPermits里取。也就是说第一次请求会立即响应,下一次请求就得等了。有点今朝有酒今朝醉,明日愁来明日愁的感觉。

那么下一次请求要等多久呢,RateLimter考虑到了WarmUp的问题,当系统存了maxPermits,也就是系统很久没被使用了,就需要一个热身的时间,在开始的一些请求(1/2 * maxPermits)里,速率会比正常速率慢,当请求量超过了1/2 * maxPermits, 系统的速率就稳定下来。

细节可以参考代码。