限流这里总结了四个算法分别是 计数器固定窗口算法、计数器滑动窗口算法、漏斗算法、令牌桶算法
1. 计数器固定窗口算法
计数器固定窗口算法是最基础也是最简单的一种限流算法。原理就是对一段固定时间窗口内的请求进行计数，如果请求数超过了阈值，则舍弃该请求；
如果没有达到设定的阈值，则接受该请求，且计数加1。当时间窗口结束时，重置计数器为0。
优点：实现简单容易理解
缺点： 流量曲线可能不够平滑，有"突刺现象"
-
一段时间内(不超过时间窗口)系统服务不可用
比如窗口大小为1s，限流大小为100，然后恰好在某个窗口的第1ms来了100个请求，然后第2ms-999ms的请求就都会被拒绝，这段时间用户会感觉系统服务不可用。
-
窗口切换时可能会产生两倍于阈值流量的请求
比如窗口大小为1s，限流大小为100，然后恰好在某个窗口的第999ms来了100个请求，窗口前期没有请求，所以这100个请求都会通过。
再恰好，下一个窗口的第1ms有来了100个请求，也全部通过了，那也就是在2ms之内通过了200个请求，而我们设定的阈值是100，通过的请求达到了阈值的两倍。
package com.example.demo.util;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @ClassName CounterLimiter
* @Description 计数器固定窗口算法
* @Date 2021/8/11 3:46 下午
* @Created by liyanyan
*/
public class CounterLimiter {
private int windowSize; //窗口大小，毫秒单位
private int limit; //窗口内限流大小
private AtomicInteger count; //当前窗口的计数器
private CounterLimiter() {
}
public CounterLimiter(int windowSize, int limit) {
this.limit = limit;
this.windowSize = windowSize;
count = new AtomicInteger(0);
//开启一个线程，达到窗口结束时清空count
new Thread(new Runnable() {
@Override
public void run() {
while (true) {
count.set(0);
try {
Thread.sleep(windowSize);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
}
//请求到达后先调用本方法，若返回true，则请求通过，否则限流
public boolean tryAcquire() {
int newCount = count.addAndGet(1);
if (newCount > limit) {
return false;
} else {
return true;
}
}
//测试 Client
public static void main(String[] args) throws InterruptedException {
//每秒20个请求
CounterLimiter counterLimiter = new CounterLimiter(1000, 20);
int count = 0;
//模拟50次请求，看多少能通过
for (int i = 0; i < 50; i++) {
if (counterLimiter.tryAcquire()) {
count++;
}
}
System.out.println("第一波50个请求中通过: " + count + "，限流: " + (50 - count));
//过一秒再请求
Thread.sleep(1000);
count = 0;
//模拟50次请求，看多少能通过
for (int i = 0; i < 50; i++) {
if (counterLimiter.tryAcquire()) {
count++;
}
}
System.out.println("第二波50个请求中通过: " + count + "，限流: " + (50 - count));
}
}
2. 计数器滑动窗口算法
计数器滑动窗口算法是计数器固定窗口算法的改进，解决了固定窗口切换时可能会产生两倍于阈值流量请求的缺点
滑动窗口算法在固定窗口的基础上，将一个计时窗口分成了若干个小窗口，然后每个小窗口维护一个独立的计数器，当请求的时间大于当前窗口的最大时间时，则将计时窗口向前平移一个小窗口。
平移时，将第一个小窗口的数据丢弃，然后将第二个小窗口设置为第一个小窗口，同时在最后新增一个小窗口，将新的请求放在新增的小窗口中。同时要保证整个窗口中所有小窗口的请求数目之后不能超过设定的阈值。
滑动窗口其实就是固定窗口的升级版。将计时窗口划分成一个小窗口，滑动窗口算法就退化成了固定窗口算法。而滑动窗口算法其实就是对请求数进行了更细粒度的限流。
窗口划分的越多，则限流越精准
package com.example.demo.util;
/**
* @ClassName CounterSlideWindowLimiter
* @Description 计数器滑动窗口算法
* @Date 2021/8/11 5:41 下午
* @Created by liyanyan
*/
public class CounterSlideWindowLimiter {
private int windowSize; //窗口大小，毫秒为单位
private int limit; //窗口内限流大小
private int splitNum; //切分小窗口的数目大小
private int[] counters; //当前小窗口的计数数组
private int index; //当前小窗口计数器的索引
private long startTime; //窗口开始时间
private CounterSlideWindowLimiter() {
}
public CounterSlideWindowLimiter(int windowSize, int limit, int splitNum) {
this.windowSize = windowSize;
this.splitNum = splitNum;
this.limit = limit;
counters = new int[splitNum];
index = 0;
startTime = System.currentTimeMillis();
}
//请求达到后先调用本方法，若返回true，则请求通过，否则限流
public synchronized boolean tryAcquire() {
long curTime = System.currentTimeMillis();
long windowsNum = Math.max(curTime - windowSize - startTime, 0) / (windowSize / splitNum); //计算滑动小窗口的数量
slideWindow(windowsNum); //滑动窗口
int count = 0;
for (int i = 0; i < splitNum; i++) {
count += counters[i];
}
if (count >= limit) {
return false;
} else {
counters[index]++;
return true;
}
}
private synchronized void slideWindow(long windowsNum) {
if (windowsNum == 0) {
return;
}
long slideNum = Math.min(windowsNum, splitNum);
for (int i = 0; i < slideNum; i++) {
index = (index + 1) % splitNum;
counters[index] = 0;
}
startTime = startTime + windowsNum * (windowSize / splitNum); //更新滑动窗口时间
}
/**
* 测试 Client
* 测试时，取滑动窗口大小为 1000/10=100ms。然后模拟100 组间隔150ms的50次请求，计数器滑动窗口算法与计数器固定窗口算法进行对别
*
* 固定窗口算法在窗口切换时产生了两倍于阈值流量的请求的问题，而滑动你个窗口算法避免了这个问题
* 和漏斗算法相比，心来的请求也能够被处理到，避免了漏斗算法的饥饿问题。
*
* @param args
* @throws InterruptedException
*/
public static void main(String[] args) throws InterruptedException {
//每秒20个
int limit = 20;
CounterSlideWindowLimiter counterSlideWindowLimiter = new CounterSlideWindowLimiter(1000, limit, 20);
int count = 0;
// Thread.sleep(3000);
//计数器滑动窗口算法模拟100组间隔30ms的50次请求
System.out.println("计数器滑动窗口算法测试开始...");
System.out.println("开始模拟100组间隔150ms的50次请求...");
int failCount = 0;
for (int j = 0; j < 100; j++) {
count = 0;
for (int i = 0; i < 50; i++) {
if (counterSlideWindowLimiter.tryAcquire()) {
count++;
}
}
Thread.sleep(150);
//模拟50次请求，看多少能通过
for (int i = 0; i < 50; i++) {
if (counterSlideWindowLimiter.tryAcquire()) {
count++;
}
}
if (count > limit) {
System.out.println("时间窗口内放过的请求超过阈值，放过的请求数" + count + ",限流：" + limit);
failCount++;
}
Thread.sleep((int) (Math.random() * 100));
}
System.out.println("计数器滑动窗口算法测试结束，100组间隔150ms的50次请求模拟完成，限流失败组数： " + failCount);
System.out.println("==========================================================================");
//计数器固定窗口算法模拟100组间隔30ms的50次请求
System.out.println("计数器固定窗口算法测试开始...");
//模拟100组间隔30ms的50次请求
CounterLimiter counterLimiter = new CounterLimiter(1000, 20);
System.out.println("开始模拟100组间隔150ms的50次请求...");
failCount = 0;
for (int j = 0; j < 100; j++) {
count = 0;
for (int i = 0; i < 50; i++) {
if (counterLimiter.tryAcquire()) {
count++;
}
}
Thread.sleep(150);
//模拟50次请求，看多少能通过
for (int i = 0; i < 50; i++) {
if (counterLimiter.tryAcquire()) {
count++;
}
}
if (count > limit) {
System.out.println("时间窗口内放过的请求超过阈值，放过的请求数" + count + ",限流：" + limit);
failCount++;
}
Thread.sleep((int) (Math.random() * 100));
}
System.out.println("计数器固定窗口算法测试结束，100组间隔150ms的50次请求模拟完成，限流失败组数：" + failCount);
}
}
3. 漏斗算法
请求来了之后会首先进到漏斗里，然后漏斗以恒定的速率将请求流出进行处理，从而起到平滑流量的作用。当请求的流量过大时，漏斗达到最大容量时会溢出，此时请求被丢弃。
从系统的角度来看，我们不知道什么时候会有请求来，也不知道请求会以多大的速率来，这就给系统的安全性埋下隐患。但是如果加了一层漏斗算法限流之后，就能够保证请求以恒定的速率流出。
在系统看来，请求永远是以平滑的传输速率过来，从而起到来保护系统的作用。
漏斗特点：
- 漏斗的漏出速率是固定的，可以起到整流的作用。即虽然请求的流量可能具有随机性，忽大忽小。但是经过漏斗算法之后，变成来固有速率的稳定流量，从而对下游的系统起到保护作用。
- 不能解决流量突发的问题。测试例子里 我们设定的漏斗速率是2个/秒 然后突然来了10个请求，受限于漏斗的容量，只有5个请求被接受，另外5个被拒绝。
漏斗速率是2个/秒，然后瞬间接受了5个请求。但是没有马上处理这5个请求，处理的速度仍然是我们设定的2个/秒 令牌桶算法能够在一定程度上解决流量突发的问题
package com.example.demo.util;
import java.util.Date;
import java.util.LinkedList;
/**
* @ClassName LeakyBucketLimiter
* @Description 漏斗算法
* @Date 2021/8/12 8:00 下午
* @Created by liyanyan
*/
public class LeakyBucketLimiter {
private int capacity; //漏斗容量
private int rate; //漏斗速率
private int left; //剩余容量
private LinkedList<Request> requestList;
private LeakyBucketLimiter(){}
public LeakyBucketLimiter(int capacity, int rate) {
this.capacity = capacity;
this.rate = rate;
this.left = capacity;
requestList = new LinkedList<>();
//开启一个定时线程，以固定的速率将漏斗中的请求流出，进行处理
new Thread(new Runnable() {
@Override
public void run() {
while(true) {
if(!requestList.isEmpty()) {
Request request = requestList.removeFirst();
handleRequest(request);
}
try {
Thread.sleep(1000 / rate); //睡眠
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
}
/**
* 处理请求
* @param request
*/
private void handleRequest(Request request) {
request.setHandleTime(new Date());
System.out.println(request.getCode() + "号请求被处理，请求发起时间: "
+ request.getLaunchTime() + ",请求处理时间: " + request.getHandleTime() + ",处理耗时: "
+ (request.getHandleTime().getTime() - request.getLaunchTime().getTime() + "ms"));
}
private synchronized boolean tryAcquire(Request request) {
if(left <= 0) {
return false;
}else {
left--;
requestList.addLast(request);
return true;
}
}
/**
* 请求类，属性包含编号字符串，请求达到时间和请求处理时间
*/
static class Request {
private int code;
private Date launchTime;
private Date handleTime;
private Request(){}
public Request(int code, Date launchTime) {
this.launchTime = launchTime;
this.code = code;
}
public int getCode() {
return code;
}
public void setCode(int code) {
this.code = code;
}
public Date getLaunchTime() {
return launchTime;
}
public void setLaunchTime(Date launchTime) {
this.launchTime = launchTime;
}
public Date getHandleTime() {
return handleTime;
}
public void setHandleTime(Date handleTime) {
this.handleTime = handleTime;
}
}
public static void main(String[] args) {
LeakyBucketLimiter leakyBucketLimiter = new LeakyBucketLimiter(5, 2);
for(int i=1; i<=10; i++) {
Request request = new Request(i, new Date());
if(leakyBucketLimiter.tryAcquire(request)) {
System.out.println(i + "号请求被接受");
}else {
System.out.println(i + "号请求被拒绝");
}
}
}
}
4. 令牌桶算法
令牌桶算法是对漏桶算法的一种改进，除了能够在限制调用的平均速率的同时还允许一定程度的流量突发。
package com.example.demo.util;
import java.util.Date;
/**
* @ClassName TokenBucketLimiter
* @Description 令牌桶算法
* @Date 2021/8/12 8:55 下午
* @Created by liyanyan
*/
public class TokenBucketLimiter {
private int capacity; //令牌桶容量
private int rate; //令牌产生速率
private int tokenAmount; //令牌数量
public TokenBucketLimiter(int capacity, int rate) {
this.capacity = capacity;
this.rate = rate;
tokenAmount = capacity;
new Thread(new Runnable() {
@Override
public void run() {
//以恒定的速率放令牌
while (true) {
synchronized (this) {
tokenAmount++;
if (tokenAmount > capacity) {
tokenAmount = capacity;
}
}
try {
Thread.sleep(1000 / rate);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
}
public synchronized boolean tryAcquire(Request request) {
if (tokenAmount > 0) {
tokenAmount--;
handleRequest(request);
return true;
} else {
return false;
}
}
/**
* 处理请求
*
* @param request
*/
private void handleRequest(Request request) {
request.setHandleTime(new Date());
System.out.println(request.getCode() + "号请求被处理，请求发起时间: "
+ request.getLaunchTime() + ",请求处理时间: " + request.getHandleTime() + ",处理耗时: "
+ (request.getHandleTime().getTime() - request.getLaunchTime().getTime() + "ms"));
}
/**
* 请求类，属性包含编号字符串，请求达到时间和请求处理时间
*/
static class Request {
private int code;
private Date launchTime;
private Date handleTime;
private Request() {
}
public Request(int code, Date launchTime) {
this.launchTime = launchTime;
this.code = code;
}
public int getCode() {
return code;
}
public void setCode(int code) {
this.code = code;
}
public Date getLaunchTime() {
return launchTime;
}
public void setLaunchTime(Date launchTime) {
this.launchTime = launchTime;
}
public Date getHandleTime() {
return handleTime;
}
public void setHandleTime(Date handleTime) {
this.handleTime = handleTime;
}
}
public static void main(String[] args) {
TokenBucketLimiter tokenBucketLimiter = new TokenBucketLimiter(5, 2);
for (int i = 1; i <= 10; i++) {
Request request = new Request(i, new Date());
if (tokenBucketLimiter.tryAcquire(request)) {
System.out.println(i + "号请求被接受");
}else {
System.out.println(i + "号请求被拒绝");
}
}
}
}
小结：
计数器固定窗口算法实现简单，容易理解。和漏斗算法相比，新来的请求也能够被马上处理到。但是流量曲线可能不够平滑，有"突刺现象"，在窗口切换时可能会产生两倍于阈值流量的请求。
而计数器滑动窗口算法作为计数器固定窗口算法的一种改进，有效解决了窗口切换时可能会产生两倍于阈值流量请求的问题
漏斗算法能够对流量起到整流的作用，让随机不稳定的流量以固定的速率流出，但是不能解决流量突发的问题。
令牌桶算法作为漏斗算法的一种改进，除了能够起到平滑流量的作用，还允许一定程度的流量突发。
没有最好的算法，只有最合适的算法
比如令牌桶算法一般用于保护自身的系统，对调用者进行限流，保护自身的系统不被突发的流量打垮。如果自身的系统实际的处理能里强于配置的流量限制时，可以允许一定程度的流量突发，使得实际的处理速率，充分利用系统资源。
而漏斗算法一般用于保护第三方的系统，比如自身的系统需要调用第三方的接口，为了保护第三方的系统不被自身的调用打垮，便可以通过漏斗算法进行限流，保证自身的流量平稳的达到第三方的接口上。
算法是死的，场景是活的。没有最好的，只有最合适的。
