一、常见的限流算法
1.漏桶算法
漏桶算法的原理比较简单，请求进入到漏桶中，漏桶以一定的速率漏水。当请求过多时，水直接溢出。可以看出，漏桶算法可以强制限制数据的传输速度。
image
2.令牌桶算法
令牌桶算法的原理是系统以一定速率向桶中放入令牌，如果有请求时，请求会从桶中取出令牌，如果能取到令牌，则可以继续完成请求，否则等待或者拒绝服务。这种算法可以应对突发程度的请求，因此比漏桶算法好。
image
在 Wikipedia 上，令牌桶算法是这么描述的：
- 每秒会有 r 个令牌放入桶中，或者说，每过 1/r 秒桶中增加一个令牌
- 桶中最多存放 b 个令牌，如果桶满了，新放入的令牌会被丢弃
- 当一个 n 字节的数据包到达时，消耗 n 个令牌，然后发送该数据包
- 如果桶中可用令牌小于 n，则该数据包将被缓存或丢弃
二、RateLimiter
Guava中开源出来一个令牌桶算法的工具类RateLimiter，可以轻松实现限流的工作。RateLimiter 对简单的令牌桶算法做了一些工程上的优化，具体的实现是 SmoothBursty。需要注意的是，RateLimiter 的另一个实现 SmoothWarmingUp，就不是令牌桶了，而是漏桶算法。也许是出于简单起见，RateLimiter 中的时间窗口能且仅能为 1s，如果想搞其他时间单位的限流，只能另外造轮子。
RateLimiter 有一个有趣的特性是「前人挖坑后人跳」，也就是说 RateLimiter 允许某次请求拿走超出剩余令牌数的令牌，但是下一次请求将为此付出代价，一直等到令牌亏空补上，并且桶中有足够本次请求使用的令牌为止。这里面就涉及到一个权衡，是让前一次请求干等到令牌够用才走掉呢，还是让它先走掉后面的请求等一等呢？Guava 的设计者选择的是后者，先把眼前的活干了，后面的事后面再说。
测试代码：
public class RateLimiterMain {
public static void main(String[] args) {
RateLimiter rateLimiter = RateLimiter.create(2);
System.out.println(rateLimiter.acquire(5));
System.out.println(rateLimiter.acquire(2));
System.out.println(rateLimiter.acquire(1));
}
}
输出内容：
2.496889
0.992149
可以看出，令牌桶每秒只能产生2个令牌，我们可以第一次取出5个，但是第二个再去取令牌的时候，需要等2.5s，也就是第一次令牌取完后，需要等2.5s才能取到令牌。同样的，第三次取1个令牌的时候，也需要等待第二次的1s的时间。也就是，取的速率可以超过令牌产生的速率，但是下一次再次去取的时候，需要阻塞等待。
当然也可以使用tryAcquire来非阻塞的获取，可以实时返回结果。另外tryAcquire也可以传入参数，也就是等待的时间，超时直接返回false。这点等同于常见的lock，tryLock。
三、RateLimiter对API接口的限流实例
- pom文件代码
<!-- google guava -->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>16.0.1</version>
</dependency>
- java代码
package com.infinite.controller;
import java.util.concurrent.TimeUnit;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;
import com.google.common.util.concurrent.RateLimiter;
import com.infinite.controller.vo.ResultBean;
/**
*
* @ClassName: RateLimiterTestController
* @Description: RateLimiter限流（单应用，分布式考虑redis实现）
* @author chenliqiao
* @date 2018年5月11日 下午4:19:35
*
*/
@RestController
public class RateLimiterTestController {
/**令牌桶容量，一秒生成5个令牌**/
private static final double PERMITS=5;
RateLimiter rateLimiter=RateLimiter.create(PERMITS);
@RequestMapping(value="/rateLimiter/getOrderNO")
public ResultBean<String> getOrderNO(){
/**
* tryAcquire(long timeout, TimeUnit unit)
* 从RateLimiter 获取许可如果该许可可以在不超过timeout的时间内获取得到的话，
* 或者如果无法在timeout 过期之前获取得到许可的话，那么立即返回false（无需等待）
*/
if(!rateLimiter.tryAcquire(1000, TimeUnit.MILLISECONDS)){
System.out.println("获取失败!");
return new ResultBean<>("error!");
}
String orderNo="NO"+System.currentTimeMillis();
System.out.println("获取成功："+orderNo);
return new ResultBean<String>(orderNo);
}
}
网友评论