您现在的位置是：首页 >技术教程 >限流算法浅析网站首页技术教程
限流算法浅析
简介限流算法浅析
前言
在前文接口请求安全措施中，简单提到过接口限流，那里是通过Guava工具类的RateLimiter实现的，它实际上是令牌桶限流的具体实现，那么下面分别介绍几种限流算法，做一个更详细的了解。
固定窗口限流
1、核心思想
在单位时间（固定时间窗口）内限制请求的数量，即将时间分为固定的窗口，限制每个窗口的请求数量，如下图所示
2、具体实现
假设单位时间是1s，限流阈值为5，在单位时间内，每来一次请求，计数器count +1，若count>5，后续请求全部拒绝，等到1s结束，count清零
package com.example.test.limit.fixedWindow;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @author zy
* @version 1.0.0
* @ClassName fixedWindow.java
* @Description 固定窗口限流算法
* 核心思想：在单位时间（固定时间窗口）内限制请求的数量，即将时间分为固定的窗口，限制每个窗口的请求数量。
* 具体实现：假设单位时间是1s，限流阈值为5，在单位时间内，每来一次请求，计数器count +1，若count>5，后续请求全部拒绝，等到1s结束，count清零
* 优点：易于理解和实现
* 缺点：存在临界问题，例如0-1和1-2是两个时间窗口，若在0.8-1s内有5个请求，在1-1.2s内有5个请求，虽然在各自的窗口上没有超限，但是在0.8-1.2s这个时间范围内
* 实际上也是一个窗口的，这样就超限了
* @createTime 2023/4/19
*/
public class fixedWindow {
//计数器
public static AtomicInteger count = new AtomicInteger(0);
//时间窗口，单位s
public static final Long window = 1000L;
//窗口阈值
public static final int threshold = 5;
//上次请求时间
public static long lastAcquireTime = 0L;
public static synchronized boolean fixedWindowTryAcquire(){
//当前系统时间
long currentTime = System.currentTimeMillis();
//看看本次请求是否在窗口内
if(currentTime - lastAcquireTime > window){
//重置计数器和上次请求时间
count.set(0);
lastAcquireTime = currentTime;
}
//检查计数器是否超过阈值，注意这里getAndIncrement和incrementAndGet的区别
if(count.incrementAndGet() <= threshold){
return true;
}
return false;
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
try {
Thread.sleep(150);
System.out.println(Thread.currentThread().getName()+"--------------->"+fixedWindowTryAcquire());
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
3、优缺点
- 优点：易于理解和实现
- 缺点：存在临界问题，例如0-1和1-2是两个时间窗口，若在0.8-1s内有5个请求，在1-1.2s内有5个请求，虽然在各自的窗口上没有超限，但是在0.8-1.2s这个时间范围内，实际上也是一个窗口的，这样就超限了，如下图
滑动窗口限流
1、核心思想
在固定窗口中，存在跨越两个小窗口（指的是一个单位窗口内我们自行理解的划分）的临界问题，那么，如果我们让这个小窗口动起来，不断去删除已经过去的时间，这样，动态的判断是否超限，如下图所示
2、具体实现
假设单位时间是100s（单位窗口），限流阈值为5，我们将单位窗口分为10个小窗口（每个小窗口为10s），然后不断的更新每个小窗口的请求和小窗口的起始时间，这样就是动起来了
package com.example.test.limit.slideWindow;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
/**
* @author zy
* @version 1.0.0
* @ClassName slideWindow.java
* @Description 滑动窗口限流算法
* 核心思想：在固定窗口中，存在跨越两个小窗口（指的是一个单位窗口内我们自行理解的划分）的临界问题，那么，如果我们让这个小窗口动起来，不断去删除已经过去的时间，这样，动态的判断是否超限
* 具体实现：假设单位时间是100s（单位窗口），限流阈值为5，我们将单位窗口分为10个小窗口（每个小窗口为10s），然后不断的更新每个小窗口的请求和小窗口的起始时间，这样就是动起来了
* 优点：精度高，对比固定窗口算法，减少了临界状态下的失真
* 缺点：无法应对突发流量（短时间大量请求），许多请求会被直接拒绝
* @createTime 2023/4/20
*/
public class slideWindow {
//时间窗口，单位s
public static final Long window = 100L;
//窗口阈值
public static final int threshold = 5;
//小窗口个数
public static final int windowCount = 10;
//存储每个小窗口开始时间及其流量
public static Map<Long, Integer>windowCounters = new HashMap<>();
public static synchronized boolean tryAcquire(){
//取当前时间，做了取整操作，保证在同一个小窗口内的时间落到同一个起点，将时间戳取秒计算，方便理解
long currentTime = System.currentTimeMillis()/1000 / windowCount * windowCount;
int currentCount = calculate(currentTime);
if(currentCount > threshold){
return false;
}
windowCounters.put(currentTime - windowCount* (window/windowCount-1),currentCount);
return true;
}
private static int calculate(long currentTime) {
//计算小窗口开始时间
//这里可以理解为 currentTime - entry.key > window/windowCount
long startTime = currentTime - windowCount* (window/windowCount-1);
System.out.println(startTime);
int count = 1;
//遍历计数器
Iterator<Map.Entry<Long,Integer>> iterator = windowCounters.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry<Long,Integer>entry = iterator.next();
//删除无效过期的子窗口
if(entry.getKey() < startTime){
iterator.remove();
System.out.println("移除了");
}else{
//累加请求
count = entry.getValue()+1;
}
}
return count;
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
try {
Thread.sleep(1000);
System.out.println(Thread.currentThread().getName()+"--------------->"+tryAcquire());
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
3、优缺点
- 优点：精度高，对比固定窗口算法，减少了临界状态下的失真
- 缺点：无法应对突发流量（短时间大量请求），许多请求会被直接拒绝
漏桶算法
1、核心思想
对于每个请求，检查漏桶是否有容量，没有直接拒绝；有的话放入漏桶，漏桶以一定速率处理桶内的请求，生产者-消费者模型，请求作为生产者，系统作为消费者，如下所示
2、具体实现
假设漏桶容量为5，速率为1个/s，那么我们还需要有一个当前的水量和当前时间分别用来判断是否可以存放请求和消耗请求
漏桶定义
package com.example.test.limit.leakBucket;
/**
* @author zy
* @version 1.0.0
* @ClassName leakBucket.java
* @Description 漏桶的定义
* @createTime 2023/4/21
*/
public class leakBucket {
//漏桶的容量
private long capacity;
//滴水（消耗请求）速率
private long rate;
//当前桶中的水（未消耗的请求）
private long water;
//上次滴水时间（用来计算现在要消耗多少个）
private long lastLeakTime;
public leakBucket(long capacity, long rate, long water, long lastLeakTime) {
this.capacity = capacity;
this.rate = rate;
this.water = water;
this.lastLeakTime = lastLeakTime;
}
public long getCapacity() {
return capacity;
}
public void setCapacity(long capacity) {
this.capacity = capacity;
}
public long getRate() {
return rate;
}
public void setRate(long rate) {
this.rate = rate;
}
public long getWater() {
return water;
}
public void setWater(long water) {
this.water = water;
}
public long getLastLeakTime() {
return lastLeakTime;
}
public void setLastLeakTime(long lastLeakTime) {
this.lastLeakTime = lastLeakTime;
}
}
实现
package com.example.test.limit.leakBucket;
/**
* @author zy
* @version 1.0.0
* @ClassName leakBucket.java
* @Description 漏桶算法
* 核心思想：对于每个请求，检查漏桶是否有容量，没有直接拒绝；有的话放入漏桶，漏桶以一定速率处理桶内的请求，生产者-消费者模型，请求作为生产者，系统作为消费者
* 具体实现：假设漏桶容量为5，速率为1个/s，那么我们还需要有一个当前的水量和当前时间分别用来判断是否可以存放请求和消耗请求
* 优点：漏桶算法还是很容易理解的，毕竟接近生活；可以平滑的处理请求，可以控制请求速度，避免过载或闲置
* 缺点：需要缓存请求，面对突发流量，处理不能及时响应
* @createTime 2023/4/21
*/
public class leakBucketAlgorithm {
//初始化漏桶
public static leakBucket leakBucket = new leakBucket(5,1,0,0);
public static synchronized boolean tryAcquire(){
leak();
//判断是否有空间，这里我设为每个请求都要判断，也可以直接传参多少个请求
if(leakBucket.getWater()+1 <leakBucket.getCapacity()){
leakBucket.setWater(leakBucket.getWater()+1);
return true;
}
return false;
}
//漏水方法
private static void leak() {
//当前时间，以秒操作
long currentTime = System.currentTimeMillis() / 1000;
//最后一次漏水到现在应该漏多少
long leakWater = (currentTime - leakBucket.getLastLeakTime()) * leakBucket.getRate();
if(leakWater > 0){
leakBucket.setWater(Math.max(0,leakBucket.getWater() - leakWater));
leakBucket.setLastLeakTime(currentTime);
}
}
public static void main(String[] args) throws InterruptedException {
for (int i = 0; i < 10; i++) {
Thread.sleep(200);
System.out.println(tryAcquire());
}
}
}
3、优缺点
- 优点：漏桶算法还是很容易理解的，毕竟接近生活；可以平滑的处理请求，可以控制请求速度，避免过载或闲置
- 缺点：需要缓存请求，面对突发流量，处理不能及时响应
令牌桶算法
1、核心思想
令牌桶算法相当于漏桶算法的翻版，之前说过，漏桶算法生产者是客户端，令牌桶是服务端作为生产者，以一定速率生成令牌放入桶中，桶满丢弃令牌，每次来一个请求消耗一个令牌，没有令牌就丢弃请求；相对于漏桶算法变化：生产者–>服务端，更符合限流的定义；消费者–>客户端，不需要另外的存储请求，如下图
2、具体实现
其实就是将漏桶的实现转变下思路
令牌桶定义
package com.example.test.limit.tokenBucket;
/**
* @author zy
* @version 1.0.0
* @ClassName tokenBucket.java
* @Description 令牌桶定义
* @createTime 2023/4/21
*/
public class tokenBucket {
//令牌桶的容量
private long capacity;
//生成令牌的速率
private long rate;
//当前桶中的令牌数
private long tokenNum;
//上次生成令牌的时间
private long lastMakeTime;
public tokenBucket(long capacity, long rate, long tokenNum, long lastMakeTime) {
this.capacity = capacity;
this.rate = rate;
this.tokenNum = tokenNum;
this.lastMakeTime = lastMakeTime;
}
public long getCapacity() {
return capacity;
}
public void setCapacity(long capacity) {
this.capacity = capacity;
}
public long getRate() {
return rate;
}
public void setRate(long rate) {
this.rate = rate;
}
public long getTokenNum() {
return tokenNum;
}
public void setTokenNum(long tokenNum) {
this.tokenNum = tokenNum;
}
public long getLastMakeTime() {
return lastMakeTime;
}
public void setLastMakeTime(long lastMakeTime) {
this.lastMakeTime = lastMakeTime;
}
}
实现
package com.example.test.limit.tokenBucket;
/**
* @author zy
* @version 1.0.0
* @ClassName tokenBucketAlgorithm.java
* @Description 令牌桶算法
* 核心思想：令牌桶算法相当于漏桶算法的翻版，之前说过，漏桶算法生产者是客户端，令牌桶是服务端作为生产者，以一定速率生成令牌放入桶中，桶满丢弃令牌，每次来一个
* 请求消耗一个令牌，没有令牌就丢弃请求
* 变化：生产者-->服务端，更符合限流的定义；消费者-->客户端，不需要另外的存储请求
* 优点：稳定性高，可以控制请求处理速度，使系统负载稳定；精度高，可以根据实际情况动态调整生成令牌的速率，可以实现较高精度的限流；可以处理突发流量，可以在短时间内提供更多的处理能力
* 以处理突发流量
* 缺点：令牌桶算法需要在固定的时间间隔内生成令牌，因此要求时间精度较高，如果系统时间不准确，可能会导致限流效果不理想
* @createTime 2023/4/21
*/
public class tokenBucketAlgorithm {
public static tokenBucket tokenBucket = new tokenBucket(5,1,5,0);
public static synchronized boolean tryAcquire(){
makeToken();
if(tokenBucket.getTokenNum() > 0){
tokenBucket.setTokenNum(tokenBucket.getTokenNum() - 1);
return true;
}
return false;
}
private static void makeToken() {
//当前时间，以秒计算
Long currentTime = System.currentTimeMillis() / 1000;
if(currentTime > tokenBucket.getLastMakeTime()){
//计算应该生成多少令牌
long makeNums = (currentTime - tokenBucket.getLastMakeTime()) * tokenBucket.getRate();
//放入令牌桶，多余容量的抛弃
tokenBucket.setTokenNum(Math.min(tokenBucket.getCapacity(),makeNums+tokenBucket.getTokenNum()));
//更新生成令牌时间
tokenBucket.setLastMakeTime(currentTime);
}
}
public static void main(String[] args) throws InterruptedException {
for (int i = 0; i < 10; i++) {
Thread.sleep(100);
System.out.println(tryAcquire());
}
}
}
3、优缺点
- 优点：稳定性高，可以控制请求处理速度，使系统负载稳定；精度高，可以根据实际情况动态调整生成令牌的速率，可以实现较高精度的限流；可以处理突发流量，可以在短时间内提供更多的处理能力以处理突发流量
- 缺点：令牌桶算法需要在固定的时间间隔内生成令牌，因此要求时间精度较高，如果系统时间不准确，可能会导致限流效果不理想
总结
虽然看上去限流算法很难，但是只要理解它们的核心思想，操作起来还是比较容易的，上述代码是完整可运行的，可以选择本地debug一下，看看具体怎么调用的。PS：滑动窗口算法那个开始时间的计算属实给我搞懵了，还好最后转过弯儿来了，最后，有轮子还是用轮子，但是我们要了解下轮子的原理。
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述