一背景

二 常用方法

令牌桶(Token Bucket)和漏桶(leaky bucket)是 最常用的两种限流的算法。

2.1 漏桶算法

漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率.示意图如下:

可见这里有两个变量,一个是桶的大小,支持流量突发增多时可以存多少的水(burst),另一个是水桶漏洞的大小(rate)，在某些情况下，漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的参数，所以，即使网络中不存在资源冲突（没有发生拥塞），漏桶算法也不能使某一个单独的流突发到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法可以结合起来为网络流量提供更大的控制。

2.2令牌桶算法

三 guava RateLimiter

3.1RateLimiter 简介

Google开源工具包Guava提供了限流工具类RateLimiter,该类基于令牌桶算法(Token Bucket)来完成限流,非常易于使用.RateLimiter经常用于限制对一些物理资源或者逻辑资源的访问速率.它支持两种获取permits接口,一种是如果拿不到立刻返回false,一种会阻塞等待一段时间看能不能拿到.

RateLimiter经常用于限制对一些物理资源或者逻辑资源的访问速率。与Semaphore 相比，Semaphore 限制了并发访问的数量而不是使用速率。（注意尽管并发性和速率是紧密相关的，比如参考通过设置许可证的速率来定义RateLimiter。在默认配置下，许可证会在固定的速率下被分配，速率单位是每秒多少个许可证。为了确保维护配置的速率，许可会被平稳地分配，许可之间的延迟会做调整。
可能存在配置一个拥有预热期的RateLimiter 的情况，在这段时间内，每秒分配的许可数会稳定地增长直到达到稳定的速率。

3.2 code

我们要实现一个基于速率的单机流控框架的时候，RateLimiter 是一个完善的核心组件，下面是demo

运行结果：

3.3 API接口

3.4.1SmoothBursty

[java] view plain copy

1. <span style="font-size:12px;"> static final class SmoothBursty extends SmoothRateLimiter {  
2.     /** The work (permits) of how many seconds can be saved up if this RateLimiter is unused? */  
3.     final double maxBurstSeconds;       
4.     SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds) {  
5.       super(stopwatch);  
6.       this.maxBurstSeconds = maxBurstSeconds;  
7.     }    
8.     @Override  
9.     void doSetRate(double permitsPerSecond, double stableIntervalMicros) {  
10.       double oldMaxPermits = this.maxPermits;  
11.       maxPermits = maxBurstSeconds * permitsPerSecond;  
12.       if (oldMaxPermits == Double.POSITIVE_INFINITY) {  
13.         // if we don't special-case this, we would get storedPermits == NaN, below  
14.         storedPermits = maxPermits;  
15.       } else {  
16.         storedPermits = (oldMaxPermits == 0.0)  
17.             ? 0.0 // initial state  
18.             : storedPermits * maxPermits / oldMaxPermits;  
19.       }  
20.     }    
21.     @Override  
22.     long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {  
23.       return 0L;  
24.     }  
25.   }</span>  

 RateLimiter 允许某次请求拿走超出剩余令牌数的令牌，但是下一次请求将为此付出代价，一直等到令牌亏空补上，并且桶中有足够本次请求使用的令牌为止2。这里面就涉及到一个权衡，是让前一次请求干等到令牌够用才走掉呢，还是让它先走掉后面的请求等一等呢？Guava 的设计者选择的是后者，先把眼前的活干了，后面的事后面再说。这里我看网上举了例子便于理解，以每秒qps=4，头两步消耗4个，剩余存储4个。在第三步的时候之前存储了4个，加上本次的共8个，但是本次请求了10个，所以透支了2个，第四次请求的时候，需要补上2个，等待0.5秒。

(1).t=0,这时候storedPermits=0，请求1个令牌，等待时间=0；

(2).t=1,这时候storedPermits=3，请求3个令牌，等待时间=0；

(3).t=2,这时候storedPermits=4，请求10个令牌，等待时间=0，超前使用了2个令牌；

     (4).t=3,这时候storedPermits=0，请求1个令牌，等待时间=0.5；

3.4.2SmoothWarmingUp

[java] view plain copy

1. static final class SmoothWarmingUp extends SmoothRateLimiter {  
2.     private final long warmupPeriodMicros;  
3.     /** 
4.      * The slope of the line from the stable interval (when permits == 0), to the cold interval 
5.      * (when permits == maxPermits) 
6.      */  
7.     private double slope;  
8.     private double halfPermits;  
9.     
10.     SmoothWarmingUp(SleepingStopwatch stopwatch, long warmupPeriod, TimeUnit timeUnit) {  
11.       super(stopwatch);  
12.       this.warmupPeriodMicros = timeUnit.toMicros(warmupPeriod);  
13.     }  
14.     
15.     @Override  
16.     void doSetRate(double permitsPerSecond, double stableIntervalMicros) {  
17.       double oldMaxPermits = maxPermits;  
18.       maxPermits = warmupPeriodMicros / stableIntervalMicros;  
19.       halfPermits = maxPermits / 2.0;  
20.       // Stable interval is x, cold is 3x, so on average it's 2x. Double the time -> halve the rate  
21.       double coldIntervalMicros = stableIntervalMicros * 3.0;  
22.       slope = (coldIntervalMicros - stableIntervalMicros) / halfPermits;  
23.       if (oldMaxPermits == Double.POSITIVE_INFINITY) {  
24.         // if we don't special-case this, we would get storedPermits == NaN, below  
25.         storedPermits = 0.0;  
26.       } else {  
27.         storedPermits = (oldMaxPermits == 0.0)  
28.             ? maxPermits // initial state is cold  
29.             : storedPermits * maxPermits / oldMaxPermits;  
30.       }  
31.     }  
32.     
33.     @Override  
34.     long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {  
35.       double availablePermitsAboveHalf = storedPermits - halfPermits;  
36.       long micros = 0;  
37.       // measuring the integral on the right part of the function (the climbing line)  
38.       if (availablePermitsAboveHalf > 0.0) {  
39.         double permitsAboveHalfToTake = min(availablePermitsAboveHalf, permitsToTake);  
40.         micros = (long) (permitsAboveHalfToTake * (permitsToTime(availablePermitsAboveHalf)  
41.             + permitsToTime(availablePermitsAboveHalf - permitsAboveHalfToTake)) / 2.0);  
42.         permitsToTake -= permitsAboveHalfToTake;  
43.       }  
44.       // measuring the integral on the left part of the function (the horizontal line)  
45.       micros += (stableIntervalMicros * permitsToTake);  
46.       return micros;  
47.     }  
48.     
49.     private double permitsToTime(double permits) {  
50.       return stableIntervalMicros + permits * slope;  
51.     }  
52.   }  

maxPermits等于热身(warmup)期间能产生的令牌数，比如QPS=4，warmup为2秒，则maxPermits=8.halfPermits为maxPermits的一半.

这个图还不是很理解，对比上一个实现方式，就是不能透支，需要的资源就等待。这里待测试验证。

四 其他常见实现方式

4.1Proxy 层的实现，针对部分 URL 或者 API 接口进行访问频率限制

limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;
server {
    location /search/ {
        limit_req zone=one burst=5;
    }