Skip to content

Commit 813cdec

Browse files
niumooniumoo
committed
docs: 增加文章[5种限流算法，7种限流方式，挡住突发流量？](https://www.wdbyte.com/java/rate-limiter.html)
1 parent 0595a07 commit 813cdec

9 files changed

Lines changed: 417 additions & 0 deletions

File tree

‎core-java-rate-limiter/README.md‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
## core-java-rate-limiter
2+
当前模块包含限流相关代码
3+
4+
### 相关文章
5+
6+
- [5种限流算法，7种限流方式，挡住突发流量？](https://www.wdbyte.com/java/rate-limiter.html)

‎core-java-rate-limiter/pom.xml‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5+
<parent>
6+
<artifactId>parent-modules</artifactId>
7+
<groupId>com.wdbyte</groupId>
8+
<version>1.0.0-SNAPSHOT</version>
9+
</parent>
10+
<modelVersion>4.0.0</modelVersion>
11+
12+
<groupId>com.wdbyte.rate.limiter</groupId>
13+
<artifactId>core-java-rate-limiter</artifactId>
14+
15+
<properties>
16+
<maven.compiler.source>17</maven.compiler.source>
17+
<maven.compiler.target>17</maven.compiler.target>
18+
</properties>
19+
20+
</project>

‎core-java-rate-limiter/src/main/java/com/wdbyte/rate/limiter/RateLimiterGuava.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package com.wdbyte.rate.limiter;
2+
3+
import java.time.LocalDateTime;
4+
import java.time.format.DateTimeFormatter;
5+
6+
import com.google.common.util.concurrent.RateLimiter;
7+
8+
/**
9+
* @author https://www.wdbyte.com
10+
* @date 2022/02/25
11+
*/
12+
public class RateLimiterGuava {
13+
14+
public static void main(String[] args) throws InterruptedException {
15+
RateLimiter rateLimiter = RateLimiter.create(2);
16+
for (int i = 0; i < 10; i++) {
17+
String time = LocalDateTime.now().format(DateTimeFormatter.ISO_LOCAL_TIME);
18+
System.out.println(time + ":" + rateLimiter.tryAcquire(i+1));
19+
Thread.sleep(250);
20+
}
21+
}
22+
}

‎core-java-rate-limiter/src/main/java/com/wdbyte/rate/limiter/RateLimiterSildingLog.java‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package com.wdbyte.rate.limiter;
2+
3+
import java.time.LocalTime;
4+
import java.util.HashSet;
5+
import java.util.Set;
6+
import java.util.TreeMap;
7+
8+
/**
9+
* 滑动日志方式限流
10+
* 设置 QPS 为 2.
11+
*
12+
* @author https://www.wdbyte.com
13+
* @date 2022/02/23
14+
*/
15+
public class RateLimiterSildingLog {
16+
17+
/**
18+
* 阈值
19+
*/
20+
private Integer qps = 2;
21+
/**
22+
* 记录请求的时间戳,和数量
23+
*/
24+
private TreeMap<Long, Long> treeMap = new TreeMap<>();
25+
26+
/**
27+
* 清理请求记录间隔, 60 秒
28+
*/
29+
private long claerTime = 60 * 1000;
30+
31+
public RateLimiterSildingLog(Integer qps) {
32+
this.qps = qps;
33+
}
34+
35+
public synchronized boolean tryAcquire() {
36+
long now = System.currentTimeMillis();
37+
// 清理过期的数据老数据，最长60 秒清理一次
38+
if (!treeMap.isEmpty() && (treeMap.firstKey() - now) > claerTime) {
39+
Set<Long> keySet = new HashSet<>(treeMap.subMap(0L, now - 1000).keySet());
40+
for (Long key : keySet) {
41+
treeMap.remove(key);
42+
}
43+
}
44+
// 计算当前请求次数
45+
int sum = 0;
46+
for (Long value : treeMap.subMap(now - 1000, now).values()) {
47+
sum += value;
48+
}
49+
// 超过QPS限制，直接返回 false
50+
if (sum + 1 > qps) {
51+
return false;
52+
}
53+
// 记录本次请求
54+
if (treeMap.containsKey(now)) {
55+
treeMap.compute(now, (k, v) -> v + 1);
56+
} else {
57+
treeMap.put(now, 1L);
58+
}
59+
return sum <= qps;
60+
}
61+
62+
public static void main(String[] args) throws InterruptedException {
63+
RateLimiterSildingLog rateLimiterSildingLog = new RateLimiterSildingLog(3);
64+
for (int i = 0; i < 10; i++) {
65+
Thread.sleep(250);
66+
LocalTime now = LocalTime.now();
67+
if (rateLimiterSildingLog.tryAcquire()) {
68+
System.out.println(now + " 做点什么");
69+
} else {
70+
System.out.println(now + " 被限流");
71+
}
72+
}
73+
}
74+
}

‎core-java-rate-limiter/src/main/java/com/wdbyte/rate/limiter/RateLimiterSimpleWindow.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.wdbyte.rate.limiter;
2+
3+
import java.time.LocalTime;
4+
import java.util.concurrent.atomic.AtomicInteger;
5+
6+
/**
7+
* 固定窗口限流实现（不需要开单独线程）
8+
*
9+
* @author https://www.wdbyte.com
10+
* @date 2022/02/23
11+
*/
12+
public class RateLimiterSimpleWindow {
13+
14+
// 阈值
15+
private static Integer QPS = 2;
16+
// 时间窗口（毫秒）
17+
private static long TIME_WINDOWS = 1000;
18+
// 计数器
19+
private static AtomicInteger REQ_COUNT = new AtomicInteger();
20+
21+
private static long START_TIME = System.currentTimeMillis();
22+
23+
public synchronized static boolean tryAcquire() {
24+
long now = System.currentTimeMillis();
25+
if ((now - START_TIME) > TIME_WINDOWS) {
26+
START_TIME = now;
27+
REQ_COUNT.set(1);
28+
return true;
29+
}
30+
return REQ_COUNT.incrementAndGet() <= QPS;
31+
}
32+
33+
public static void main(String[] args) throws InterruptedException {
34+
//Thread.sleep(400);
35+
for (int i = 0; i < 10; i++) {
36+
Thread.sleep(250);
37+
LocalTime now = LocalTime.now();
38+
if (!tryAcquire()) {
39+
System.out.println(now + " 被限流");
40+
} else {
41+
System.out.println(now + " 做点什么");
42+
}
43+
}
44+
}
45+
}

‎core-java-rate-limiter/src/main/java/com/wdbyte/rate/limiter/RateLimiterSimpleWindow0.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package com.wdbyte.rate.limiter;
2+
3+
import java.util.concurrent.atomic.AtomicInteger;
4+
5+
/**
6+
* 固定窗口限流的简单实现
7+
* 需要开线程
8+
*
9+
* @author https://www.wdbyte.com
10+
* @date 2022/02/23
11+
*/
12+
public class RateLimiterSimpleWindow0 {
13+
14+
// 阈值
15+
private static Integer qps = 2;
16+
// 计数器
17+
private static AtomicInteger reqCount = new AtomicInteger();
18+
19+
static {
20+
new Thread(() -> {
21+
while (true) {
22+
try {
23+
Thread.sleep(1000);
24+
} catch (InterruptedException e) {
25+
e.printStackTrace();
26+
}
27+
reqCount.getAndSet(0);
28+
}
29+
}).start();
30+
}
31+
32+
public static void main(String[] args) throws InterruptedException {
33+
for (int i = 0; i < 10; i++) {
34+
Thread.sleep(250);
35+
if (reqCount.getAndAdd(1) > qps) {
36+
System.out.println("被限流");
37+
} else {
38+
reqCount.incrementAndGet();
39+
System.out.println("做点什么");
40+
}
41+
}
42+
}
43+
}

‎core-java-rate-limiter/src/main/java/com/wdbyte/rate/limiter/RateLimiterSlidingWindow.java‎

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
package com.wdbyte.rate.limiter;
2+
3+
import java.time.LocalTime;
4+
import java.util.concurrent.atomic.AtomicInteger;
5+
6+
/**
7+
* 滑动窗口限流工具类
8+
*
9+
* @author https://www.wdbyte.com
10+
* @date 2022/02/23
11+
*/
12+
public class RateLimiterSlidingWindow {
13+
/**
14+
* 阈值
15+
*/
16+
private int qps = 2;
17+
/**
18+
* 时间窗口总大小（毫秒）
19+
*/
20+
private long windowSize = 1000;
21+
/**
22+
* 多少个子窗口
23+
*/
24+
private Integer windowCount = 10;
25+
/**
26+
* 窗口列表
27+
*/
28+
private WindowInfo[] windowArray = new WindowInfo[windowCount];
29+
30+
public RateLimiterSlidingWindow(int qps) {
31+
this.qps = qps;
32+
long currentTimeMillis = System.currentTimeMillis();
33+
for (int i = 0; i < windowArray.length; i++) {
34+
windowArray[i] = new WindowInfo(currentTimeMillis, new AtomicInteger(0));
35+
}
36+
}
37+
38+
/**
39+
* 1. 计算当前时间窗口
40+
* 2. 更新当前窗口计数 & 重置过期窗口计数
41+
* 3. 当前 QPS 是否超过限制
42+
*
43+
* @return
44+
*/
45+
public synchronized boolean tryAcquire() {
46+
long currentTimeMillis = System.currentTimeMillis();
47+
// 1. 计算当前时间窗口
48+
int currentIndex = (int)(currentTimeMillis % windowSize / (windowSize / windowCount));
49+
// 2. 更新当前窗口计数 & 重置过期窗口计数
50+
int sum = 0;
51+
for (int i = 0; i < windowArray.length; i++) {
52+
WindowInfo windowInfo = windowArray[i];
53+
if ((currentTimeMillis - windowInfo.getTime()) > windowSize) {
54+
windowInfo.getNumber().set(0);
55+
windowInfo.setTime(currentTimeMillis);
56+
}
57+
if (currentIndex == i && windowInfo.getNumber().get() < qps) {
58+
windowInfo.getNumber().incrementAndGet();
59+
}
60+
sum = sum + windowInfo.getNumber().get();
61+
}
62+
// 3. 当前 QPS 是否超过限制
63+
return sum <= qps;
64+
}
65+
66+
private class WindowInfo {
67+
// 窗口开始时间
68+
private Long time;
69+
// 计数器
70+
private AtomicInteger number;
71+
72+
public WindowInfo(long time, AtomicInteger number) {
73+
this.time = time;
74+
this.number = number;
75+
}
76+
77+
public long getTime() {
78+
return time;
79+
}
80+
81+
public void setTime(long time) {
82+
this.time = time;
83+
}
84+
85+
public AtomicInteger getNumber() {
86+
return number;
87+
}
88+
}
89+
90+
public static void main(String[] args) throws InterruptedException {
91+
int qps = 2, count = 20, sleep = 300, success = count * sleep / 1000 * qps;
92+
System.out.println(String.format("当前QPS限制为:%d,当前测试次数:%d,间隔:%dms,预计成功次数:%d", qps, count, sleep, success));
93+
success = 0;
94+
RateLimiterSlidingWindow myRateLimiter = new RateLimiterSlidingWindow(qps);
95+
for (int i = 0; i < count; i++) {
96+
Thread.sleep(sleep);
97+
if (myRateLimiter.tryAcquire()) {
98+
success++;
99+
if (success % qps == 0) {
100+
System.out.println(LocalTime.now() + ": success, ");
101+
} else {
102+
System.out.print(LocalTime.now() + ": success, ");
103+
}
104+
} else {
105+
System.out.println(LocalTime.now() + ": fail");
106+
}
107+
}
108+
System.out.println();
109+
System.out.println("实际测试成功次数:" + success);
110+
}
111+
}
112+

‎core-java-rate-limiter/src/test/java/RedisLuaLimiterByIncr.java‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
//import java.io.IOException;
2+
//import java.time.LocalTime;
3+
//import java.util.Arrays;
4+
//
5+
//import org.junit.jupiter.api.Test;
6+
//import org.springframework.beans.factory.annotation.Autowired;
7+
//import org.springframework.boot.test.context.SpringBootTest;
8+
//import org.springframework.core.io.ClassPathResource;
9+
//import org.springframework.data.redis.core.StringRedisTemplate;
10+
//import org.springframework.data.redis.core.script.DefaultRedisScript;
11+
//import org.springframework.scripting.support.ResourceScriptSource;
12+
//
13+
//@SpringBootTest
14+
//class RedisLuaLimiterByIncr {
15+
// private static String KEY_PREFIX = "limiter_";
16+
// private static String QPS = "4";
17+
// private static String EXPIRE_TIME = "1";
18+
//
19+
// @Autowired
20+
// private StringRedisTemplate stringRedisTemplate;
21+
//
22+
// @Test
23+
// public void redisLuaLimiterTests() throws InterruptedException, IOException {
24+
// for (int i = 0; i < 15; i++) {
25+
// Thread.sleep(200);
26+
// System.out.println(LocalTime.now() + " " + acquire("user1"));
27+
// }
28+
// }
29+
//
30+
// /**
31+
// * 计数器限流
32+
// *
33+
// * @param key
34+
// * @return
35+
// */
36+
// public boolean acquire(String key) {
37+
// // 当前秒数作为 key
38+
// key = KEY_PREFIX + key + System.currentTimeMillis() / 1000;
39+
// DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
40+
// redisScript.setResultType(Long.class);
41+
// //lua文件存放在resources目录下
42+
// redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("limiter.lua")));
43+
// return stringRedisTemplate.execute(redisScript, Arrays.asList(key), QPS, EXPIRE_TIME) == 1;
44+
// }
45+
//
46+
//}

0 commit comments

Comments
 (0)