令牌桶限流算法的实现

宋正兵 on 2021-06-20

image.png

漏斗算法

漏斗算法顾名思义,就是请求像水一样的先进到漏斗里,它的规则如下:

  1. 请求来了放入桶中
  2. 桶内请求满了拒绝请求
  3. 服务定速从桶内拿请求处理

令牌桶算法

令牌桶算法是定速地往桶里塞入令牌,然后请求只有拿到了令牌才能通过,之后再被服务器处理。令牌桶算法在应对突发流量的时候有更好的表现,因为它桶内有库存的令牌可以被直接拿走。

  1. 初始化固定数量的令牌放入令牌桶中
  2. 初始化和开启一个定时的任务,定时往令牌桶添加令牌
  3. 提供一个获取令牌的方法,获取一个令牌,令牌桶中减一,如果令牌桶中为空,返回失败
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
public class TokenLimiter {
private ArrayBlockingQueue<String> blockingQueue;
private TimeUnit timeUnit;
private int period;

pulic TokenLimiter(int limit, int period, TimeUnit timeUnit) {
this.limit = limit;
this.semaphore = new Semaphore(limit);
this.period = period;
this.timeUnit = timeunit;
blockingQueue = new ArrayBlockingQueue<>(limit);
init();
start();
}
// 初始化令牌
private void init() {
for (int i = 0; i < limit; i++) {
blockingQueue.add("1");
}
}
// 获取令牌,如果令牌桶为空,返回 false
public boolean tryAcquire() {
return blockingQueue.poll() == null ? false : true;
}
private void addToken() {
blockingQueue.offer("1");
}
// 开启一个定时线程执行添加令牌
private void start() {
// 参数分别为 Runnable, 初始延迟,周期,时间单位
Executors.newScheduledThreadPool(1).scheduleAtFixedRate(() -> {
addToken();
}, 10, period, timeUnit);
}
}