引言：限流，对流量加以控制
限流算法
服务总有一个承载上限，如果不加以控制，很有可能导致服务过大，打爆服务。
本节介绍四种经典的限流算法（图片来自于博客）
固定窗口
固定窗口限流：固定时间处理阈值以内的流量，如果超过该时间的请求就丢弃
优缺点：
- 优点：实现简单
- 缺点：存在明显的临界问题，假设当前每秒限流10qps，第8s的最后100ms有8qps，第9s的前100ms有5qps，那么在这不到200ms的时间，流量有8+5=13qps，我们的限流失败了。
具体实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class FixedWindows implements RateLimiter {
public AtomicInteger counter = new AtomicInteger(0);
public long lastAcquireTime = System.currentTimeMillis();
public final Long windowUnit = 1000L ;
public final Integer threshold = 10;
@Override
public synchronized boolean allowReq() {
long currentTime = System.currentTimeMillis();
if (currentTime - lastAcquireTime > windowUnit) {
counter.set(0);
lastAcquireTime = currentTime;
}
if (counter.get() < threshold) {
counter.incrementAndGet();
return true;
}
return false;
}
}
|
滑动窗口
为了解决固定窗口的临界问题，引入了滑动窗口：
优缺点：
- 优点：简单，解决了临界问题
- 缺点：突发流量无法处理（意思是：达到阈值，后续请求都会被拒绝，而不是排队等待处理）
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
| public class SlideWindows implements RateLimiter {
private int SUB_CYCLE = 10;
private final int threshold = 10;
private final Map<Long, Integer> counters = new TreeMap<>();
@Override
public synchronized boolean allowReq() {
long epochSecond = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC);
long currentWindowTime = epochSecond / SUB_CYCLE * SUB_CYCLE;
int currentWindowNum = countCurrentWindow(currentWindowTime);
if (currentWindowNum >= threshold) {
return false;
}
counters.put(currentWindowTime, counters.getOrDefault(currentWindowTime, 0) + 1);
return true;
}
private int countCurrentWindow(long currentWindowTime) {
long startTime = currentWindowTime - SUB_CYCLE * (60 / SUB_CYCLE);
int count = 0;
Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Long, Integer> entry = iterator.next();
if (entry.getKey() < startTime) {
iterator.remove();
} else {
count += entry.getValue();
}
}
return count;
}
}
|
注意此处的计算窗口的开始位置：
1
2
|
long startTime = currentWindowTime - SUB_CYCLE * (60 / SUB_CYCLE);
|
(60 / SUB_CYCLE) 计算了一个分钟内有多少个小周期，我们设置的是10，因此一分钟有6个小周期
假设当前时间为 15:23:35，我们要计算的是在当前时间之前的窗口的起始时间戳。那么 currentWindowTime 就是当前时间的整十秒：currentWindowTime = 15:23:30
startTime 计算为：
1
2
3
4
5
| startTime = currentWindowTime - SUB_CYCLE * (60 / SUB_CYCLE)
= 15:23:30 - 10 * (60 / 10)
= 15:23:30 - 10 * 6
= 15:23:30 - 60
= 15:22:30
|
漏桶算法
所谓漏桶算法如图所示，有一定的处理量，而且有一定的储存量，但是如果超出储存，请求还是会被拒绝：
优点：可以应对突增流量（输入可以是随机速率（就像是现实中的流量），输出是恒定速率（方便服务匀速处理请求））
缺点：
- 桶存储请求，增大服务器消耗
- 桶的参数调整不能随时变化
- 不能遇强则强：无论当前流量如何，都会按固定速率处理
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
| public class LeakyBucket implements RateLimiter {
private final int capacity = 10;
private final long interval = 1000;
private int water;
private long lastLeakTime;
@Override
public synchronized boolean allowReq() {
long currentTime = System.currentTimeMillis();
int leakAmount = (int) ((currentTime - lastLeakTime) / interval);
lastLeakTime = currentTime;
water = Math.max(0, water - leakAmount);
if (water < capacity) {
water++;
return true;
}
return false;
}
}
|
令牌桶算法
该算法的模型是：
现在有一个存放了很多令牌的桶（所谓令牌就是，拿到令牌的请求可以执行），每秒会向桶中存放令牌，一个请求消耗一个令牌。
相较于漏桶算法，令牌桶算法主要的区别是：允许流量短时间内突增
但是这个特点也带来的一个问题：短时间内可能用完令牌，导致一段时间内的其他请求都无法响应。
因此如果我们的应用场景就是要求削峰填谷，那么使用漏桶反而是更好的选择。
如果是为了应对短时间内的流量突增，那么可以考虑使用令牌桶。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class TokenBucket implements RateLimiter {
private final int capacity = 10;
private final long interval = 100;
private final BlockingQueue<Object> tokenBucket = new ArrayBlockingQueue<>(capacity);
public TokenBucket() {
ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(1);
scheduler.scheduleAtFixedRate(() -> {
if (tokenBucket.size() < capacity) {
tokenBucket.offer(new Object());
}
}, 0, interval, TimeUnit.MILLISECONDS);
}
@Override
public boolean allowReq() {
return tokenBucket.poll() != null;
}
}
|