限流的三种算法
限流主要有三种算法：信号量、漏桶算法和令牌桶算法。
信号量限制的是并发、资源。令牌桶限制的是QPS。
信号量
Semaphore是一个计数信号量。常用于限制获取某资源的线程数量，可基于java的concurrent并发包实现。
通过acquire()方法获取许可，该方法会阻塞，直到获取许可为止。
通过release()方法释放许可。
基于java的concurrent的实现
@RestController
@RequestMapping("/semaphore")
public class SemaphoreController {
//初始化信号量=5，true-公平信号量FIFO。
private Semaphore semaphore = new Semaphore(5, true);
@RequestMapping("/acquire/{par1}")
public String acquire(@PathVariable String par1){
try {
semaphore.acquire(1);//获取一个许可
//do sth
return par1+"获取一个许可";
}catch (InterruptedException e){
e.printStackTrace();
return "获取许可失败";
}catch (Exception e1){
return "获取许可失败";
}finally {
semaphore.release(1);//处理完后，释放一个许可
}
}
}
漏桶算法
漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率.示意图如下:
漏桶.jpg
令牌桶算法
令牌桶算法(Token Bucket)和 Leaky Bucket 效果一样但方向相反的算法,更加容易理解.随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务
令牌桶.jpg
令牌桶算法比漏桶算法更加优雅，适合秒杀等场景。本示例主要描述基于google的guava令牌桶算法的实现。
pom坐标，建议使用16.0及以上版本
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>25.0-jre</version>
</dependency>
限流实现
@RestController
@RequestMapping("/ratelimiter")
public class RateLimiterController {
private RateLimiter rateLimiter = RateLimiter.create(0.5);//每秒发放0.5个令牌。注意:本初始化声明不要放在方法内
//非阻塞机制
@RequestMapping("/nonblock")
public String rateLimiterNonBlock() {
//如果令牌桶内有令牌，则直接发放；如果能在1000ms内能够获取一个令牌，则等待到时后发放；如果在1000ms内无法获取令牌，则直接返回false，无需等待。
if (rateLimiter.tryAcquire(1000, TimeUnit.MILLISECONDS)) {
//do sth
return "成功获取令牌";
} else {
// do other
return "获取失败";
}
}
//阻塞机制
@RequestMapping("/block")
public String reateLimiterBlock(){
//获取一个令牌，该方法会被阻塞知道获取令牌
double waitTime = rateLimiter.acquire();
//do sth
return "等待"+waitTime+"秒后，成功获取令牌";
}
}
建议使用非阻塞方式。
方法摘要
| 修饰符和类型 | 方法 | 描述 |
|---|---|---|
| double | acquire() | 从RateLimiter获取一个许可，该方法会被阻塞直到获取到请求 |
| double | acquire(int permits) | 从RateLimiter获取指定许可数，该方法会被阻塞直到获取到请求 |
| static RateLimiter | create(double permitsPerSecond) | 根据指定的稳定吞吐率创建RateLimiter，这里的吞吐率是指每秒多少许可数（通常是指QPS，每秒多少查询） |
| static RateLimiter | create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) | 根据指定的稳定吞吐率和预热期来创建RateLimiter，这里的吞吐率是指每秒多少许可数（通常是指QPS，每秒多少个请求量），在这段预热时间内，RateLimiter每秒分配的许可数会平稳地增长直到预热期结束时达到其最大速率。（只要存在足够请求数来使其饱和） |
| double | getRate() | 返回RateLimiter 配置中的稳定速率，该速率单位是每秒多少许可数 |
| void | setRate(double permitsPerSecond) | 更新RateLimite的稳定速率，参数permitsPerSecond 由构造RateLimiter的工厂方法提供。 |
| boolean | tryAcquire() | 从RateLimiter获取许可，如果该许可可以在无延迟下的情况下立即获取得到的话 |
| boolean | tryAcquire(int permits) | 从RateLimiter获取许可数，如果该许可数可以在无延迟下的情况下立即获取得到的话 |
| boolean | tryAcquire(int permits, long timeout, TimeUnit unit) | 从RateLimiter 获取指定许可数如果该许可数可以在不超过timeout的时间内获取得到的话，或者如果无法在timeout 过期之前获取得到许可数的话，那么立即返回false （无需等待） |
| boolean | tryAcquire(long timeout, TimeUnit unit) | 从RateLimiter 获取许可如果该许可可以在不超过timeout的时间内获取得到的话，或者如果无法在timeout 过期之前获取得到许可的话，那么立即返回false（无需等待） |
