JAVA并发案例分析-Guava中的限流与高效令牌桶算法

Posted on | Edited on | In ,

令牌桶算法的作用

主要使用场景–限流。服务器在处理上游的请求时候为了防止资深被打垮往往需要限流这种保护机制，其中有一种算法是令牌桶算法。
即：在指定的时间内允许一定的请求通过。

实现方案

  • 方案1：生产者模式，消费者模式。用一个阻塞队列初始好令牌，请求来了从队列里消费，然后另外的线程按照一定速度往队列里增加令牌。缺点：在高并发场景下，线程调度的误差会变大，同时本身会创建线程调度会影响到线上的服务
  • 方案2：因为令牌是按照事件产生的，我们可以利用时间关系来创建”令牌“
    • 我们在桶中初始化令牌数，并且设置下一个产生令牌的时间next
    • 如果当前请求时间now大于next，则计算产生的令牌，同时更新next的值为now。
    • 取令牌，如果是令牌桶中取的不更新next，如果令牌桶没有了更新next时间
    • 计算现在时间和next的差值，进行限流策略（阻塞或者返回错误）

代码示例

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

public class SimpleLimit {

    private long next = System.currentTimeMillis();
    private long intrval = 1_000_000_000;
    private long permitSize = 0;

    public SimpleLimit(long permitSize) {
        this.permitSize = permitSize;
    }

    //计算产生了多少令牌
    private void rsync(long now) {
        if (now > next) {
            long permits = (now - next) / intrval;

            permitSize = Math.min(permitSize, permitSize + permits);

            next = now;
        }
    }


    private synchronized long reserve(long now) {
        rsync(now);

        long at = next;

        //如果从桶里取的next不更新，如果桶里没有了next更新
        long pf = Math.min(1, permitSize);
        long nr = 1 - pf;
        next = next + nr * intrval;

        permitSize -= pf;
        return at;
    }

    public void acquire() {
        long now = System.nanoTime();

        long at = reserve(now);

        //判断是否应该限流，因为桶没了next更新所以at>now这时候休眠
        long waitTime = Math.max(at - now, 0);
        if (waitTime > 0) {
            try {
                TimeUnit.NANOSECONDS.sleep(waitTime);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }

    }
}