在开发项目中经常使用限流算法，这里将常用限流算法进行总结。
计数器限流
在一段时间间隔内，处理请求的最大数量固定，超过部分不做处理。
其原理是：通过维护一个单位时间内的计数值，每当一个请求通过时，就将计数值加1，当计数值超过预先设定的阈值时，就拒绝单位时间内的其他请求。如果单位时间已经结束，则将计数器清零，开启下一轮的计数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| import java.util.Random;
public class Counter {
private final int interval = 1000;
private final int limit = 5;
private long lastTime = System.currentTimeMillis();
private int counter = 0;
public boolean tryAcquire() {
if (System.currentTimeMillis() < lastTime + interval) {
counter++;
} else {
lastTime = System.currentTimeMillis();
counter = 1;
}
return counter <= limit;
}
public static void main(String[] args) throws InterruptedException {
Counter counter = new Counter();
while (true) {
if (counter.tryAcquire()) {
System.out.println("进行请求");
} else {
System.out.println("限流了。。。。");
}
Thread.sleep(100 * new Random().nextInt(5));
}
}
}
|
但是，计数器存在临界值的问题：
假设系统的限流规则设定为“1秒内最多允许100个请求”，如果用户在第一个时间窗口的最后几毫秒发送了 99 个请求，然后紧接着在下一个时间窗口的开始发送了 99 个请求，那么用户在短时间内（接近 1 秒）发送了 198 个请求，但由于这些请求跨越了两个不同的时间窗口，限流系统并不会阻止这种情况。
滑动时间窗口算法
滑动时间窗口算法就是为了解决上述固定时间窗口存在的临界值问题而诞生。要解决这种临界值问题，显然只用一个窗口是解决不了问题的。假设我们仍然设定1秒内允许通过的请求是200个，但是在这里我们需要把1秒的时间分成多格，假设分成5格（格数越多，流量过渡越平滑），每格窗口的时间大小是200毫秒，每过200毫秒，就将窗口向前移动一格。为了便于理解，可以看下图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| import java.util.LinkedList;
import java.util.Random;
public class MovingWindow {
private final int interval = 1000;
private final int limit = 5;
private int slotCount = 5;
private LinkedList<Node> slot = new LinkedList<Node>();
public MovingWindow() {
new Thread(() -> {
while (true) {
if (slot.size() == slotCount) {
slot.poll();
}
slot.offer(new Node(System.currentTimeMillis()));
try {
Thread.sleep(interval / slotCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
}
public boolean tryAcquire() {
Node currWindow = getCurrWindow();
currWindow.setCount(currWindow.getCount() + 1);
return getCounter() <= limit;
}
private int getCounter() {
return slot.stream().mapToInt(Node::getCount).sum();
}
private Node getCurrWindow() {
if (slot.isEmpty()) {
while (true) {
if (slot.isEmpty()) {
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
} else break;
}
}
return slot.getLast();
}
private class Node {
private int count;
private long time;
public Node(long time) {
this.time = time;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public long getTime() {
return time;
}
public void setTime(long time) {
this.time = time;
}
}
public static void main(String[] args) throws InterruptedException {
MovingWindow counter = new MovingWindow();
while (true) {
counter.slot.stream().forEach(node -> System.out.print(node.getTime() + ":" + node.getCount() + "|"));
if (counter.tryAcquire()) {
System.out.println("进行请求");
} else {
System.out.println("限流了。。。。");
}
Thread.sleep(100 * new Random().nextInt(5));
}
}
}
|
临界值问题
假设我们有一个 API 接口，限流规则是每分钟最多处理 100 个请求，并采用滑动时间窗口来进行限流控制。
- 滑动时间窗口：统计过去 60 秒内的请求数，允许每分钟最多处理 100 个请求。
- 时间窗口滑动频率：每秒滑动一次，实时监控过去 60 秒内的请求数量。
临界值问题的具体示例：
- 第 1 秒：用户发送了 100 个请求，这 100 个请求符合每分钟 100 个请求的限流规则。
- 第 59 秒：用户再次发送 100 个请求。由于滑动窗口统计的是过去 60 秒内的请求，因此这 100 个请求只会覆盖第 1 秒到第 59 秒内的请求。
- 第 60 秒：滑动窗口滑动，此时统计的是第 2 秒到第 60 秒的请求，因此用户可以再次发送 100 个请求。
临界点效应：
- 用户在第 1 秒和第 59 秒分别发送了 100 个请求，滑动时间窗口的总计是 200 个请求，但由于它们处于不同的统计时间窗口内，系统不会触发限流。
- 因此，尽管限流规则是每分钟 100 个请求，但在临界点的边界时刻（窗口的开头和结尾），用户可以在短短 2 秒钟内发送200 个请求。
在滑动窗口的边界时刻（第 59 秒和第 60 秒），短时间内可以发送 200 个请求，而不会违反限流规则。
漏桶限流
漏桶大小固定，处理速度固定，但请求进入速度不固定（在突发情况请求过多时，会丢弃过多的请求）。
原理
漏桶算法以一个常量限制了出口流量速率，因此漏桶算法可以平滑突发的流量。其中漏桶作为流量容器我们可以看做一个FIFO的队列，当入口流量速率大于出口流量速率时，因为流量容器是有限的，超出的流量会被丢弃。
下图比较形象的说明了漏桶算法的原理，其中水滴是入口流量，漏桶是流量容器，匀速流出的水是出口流量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| import java.util.Random;
import java.util.concurrent.ArrayBlockingQueue;
public class Funnel {
private int rate = 10;
private ArrayBlockingQueue bucket;
public Funnel(int rate, int capacity) {
this.rate = rate;
this.bucket = new ArrayBlockingQueue(capacity);
int speed = 1000 / this.rate;
new Thread(() -> {
while (true) {
bucket.poll();
try {
Thread.sleep(speed);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
}
public boolean tryAcquire() {
return bucket.offer(this);
}
public static void main(String[] args) throws InterruptedException {
Funnel funnel = new Funnel(10, 100);
while (true) {
if (funnel.tryAcquire()) {
System.out.println("进行请求");
} else {
System.out.println("限流了。。。。");
}
Thread.sleep(20 * new Random().nextInt(5));
}
}
}
|
因为漏桶算法的流出速率是固定的，所以漏桶算法不支持出现突发流出流量。但是在实际情况下，流量往往是突发的。
令牌桶限流
令牌桶的大小固定，令牌的产生速度固定，但是消耗令牌（即请求）速度不固定（可以应对一些某些时间请求过多的情况）；每个请求都会从令牌桶中取出令牌，如果没有令牌则丢弃该次请求。
原理：
令牌桶算法是如何支持突发流量的呢？最开始，令牌桶是空的，我们以恒定速率往令牌桶里加入令牌，令牌桶被装满时，多余的令牌会被丢弃。当请求到来时，会先尝试从令牌桶获取令牌（相当于从令牌桶移除一个令牌），获取成功则请求被放行，获取失败则阻塞或拒绝请求。那么当突发流量来临时，只要令牌桶有足够的令牌，就不会被限流。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class TokenBucketRateLimiter {
private final int capacity;
private final int rate;
private AtomicInteger tokens;
private long lastRefillTime;
private final Lock lock = new ReentrantLock();
public TokenBucketRateLimiter(int capacity, int rate) {
this.capacity = capacity;
this.rate = rate;
this.tokens = new AtomicInteger(capacity);
this.lastRefillTime = System.currentTimeMillis();
}
public boolean tryAcquire() {
lock.lock();
try {
refillTokens();
if (tokens.get() > 0) {
tokens.decrementAndGet();
return true;
} else {
return false;
}
} finally {
lock.unlock();
}
}
private void refillTokens() {
long currentTime = System.currentTimeMillis();
long elapsedTime = currentTime - lastRefillTime;
int newTokens = (int) (elapsedTime * rate / 1000);
if (newTokens > 0) {
tokens.set(Math.min(capacity, tokens.get() + newTokens));
lastRefillTime = currentTime;
}
}
public static void main(String[] args) {
TokenBucketRateLimiter rateLimiter = new TokenBucketRateLimiter(10, 5);
for (int i = 0; i < 20; i++) {
if (rateLimiter.tryAcquire()) {
System.out.println("Request " + (i + 1) + " allowed");
} else {
System.out.println("Request " + (i + 1) + " rejected");
}
try {
TimeUnit.MILLISECONDS.sleep(200);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
|
之前在校园论坛的项目中实现的。
总结
| 限流算法 |
原理 |
适用场景 |
优点 |
缺点 |
| 漏桶算法 |
请求进入漏桶，以固定速率流出，超出桶容量的请求被丢弃。 |
带宽管理、网络流量整形：保证流量平稳，防止短时间内的突发流量压垮系统。 |
处理流量平稳，防止突发流量造成系统过载。 |
可能导致请求被丢弃，无法灵活处理突发流量。 |
| 令牌桶算法 |
请求需要获取令牌才能处理，令牌按固定速率生成，超出令牌桶容量的请求被丢弃。 |
API 限流、请求限流：适用于允许突发流量的场景，如接口调用的限流。 |
支持突发流量，能够灵活处理短时间内的流量高峰。 |
令牌速率过低可能导致处理延迟，速率过高无法控制流量。 |
| 计数器算法 |
在固定时间窗口内记录请求数，超出限制的请求被拒绝。 |
简单 API 限流：如每日限额、每分钟限额等，适用于对流量限制较为简单的场景。 |
实现简单，逻辑清晰，适合短时间内的流量限制。 |
不能处理突发流量，流量可能集中在时间窗的边界。 |
| 滑动窗口计数 |
通过滑动时间窗口记录请求数，超出限制的请求被拒绝。 |
较灵活的限流：适用于需要平滑流量限制的场景，如需要更精细化的流量控制。 |
处理突发流量更加平滑，减少时间窗边界问题。 |
实现复杂度相对较高，计算量较大。 |
| 限速队列 |
通过将请求排队并延迟处理，控制请求的处理速率。 |
高并发系统：适用于需要控制请求速率的场景，如防止系统被瞬时高并发流量冲击。 |
易于实现，能够平滑处理请求，防止系统被瞬时流量压垮。 |
可能导致延迟过高，影响用户体验。 |
| 漏斗算法 |
通过设定定时“漏水”速率，限制单位时间内处理的请求数。 |
带宽控制、流量整形：用于防止流量瞬时过大冲击系统。 |
易于实现，能够平稳处理请求，避免系统过载。 |
可能导致请求延迟或丢弃，无法应对突发流量。 |
适用场景
- 漏桶算法：适合网络流量整形和带宽管理，可以平滑处理流量，防止突发流量对系统的冲击，常用于需要稳定流量的场景，如对某些服务的总带宽进行限制。
- 令牌桶算法：适合API 限流和允许突发流量的系统，如某些系统允许短时间内处理大量请求，但超过一定限制后开始拒绝请求。典型场景包括开放 API 接口、短信发送接口等。
- 计数器算法：适合简单的 API 限流，如每分钟、每天的请求限额。实现较为简单，适用于流量控制需求不复杂的场景，如每天只允许用户访问某接口 100 次。
- 滑动窗口计数：适合需要平滑控制流量的场景，能够减少时间窗口的边界效应，适用于需要更精准速率控制的系统，如交易系统中控制每秒最多处理多少笔交易。
- 限速队列：适合高并发场景下的请求排队，如商品秒杀活动，能够通过排队机制避免高并发请求直接冲击后端服务，防止系统崩溃。
- 漏斗算法：用于带宽控制和流量整形，适合需要对输入流量进行整形和调度的场景，如限制视频流的带宽，防止瞬时流量过大影响系统性能。
本文基于限流算法（计数器、滑动时间窗口、漏斗、令牌）原理以及代码实现
