高性能限流器GuavaRateLimiter

Guava是Google开源的Java类库，提供了一个工具类RateLimiter。

假设有一个线程池，它每秒只能处理两个任务，如果提交的任务过快，可能导致系统不稳定，这个时候就需要用到限流。

创建一个流速为2个请求/秒的限流器。每秒最多允许2个请求通过限流器。在Guava中，流速还有更深一层的意思：一种匀速的概念，2个请求/秒等价于1个请求/500毫秒。

//限流器流速：2个请求/秒
RateLimiter limiter = RateLimiter.create(2.0);
//执行任务的线程池
Executor es = Executors.newFixedThreadPool(1);
//记录上一次执行时间
long prev = System.nanoTime();
//测试执行20次
for(int i=0; i<20; i++) {
    //限流器限流
    limiter.acquire();
    //提交任务异步执行
    es.execute(()->{
        long cur = System.nanoTime();
        //打印时间间隔：毫秒
        System.out.println((cur - prev)/1000000);
        prev = cur;
    });
}

在向线程池提交任务之前，调用acquire()方法就能起到限流的作用，任务提交到线程池的时间间隔基本上稳定在500毫秒。

微服务接口鉴权限流

经典限流算法：令牌桶算法

Guava采用的是令牌桶算法，其核心是想要通过限流器，必须拿到令牌。只要能够限制发放令牌的速率，那么就能控制流速了。

令牌以固定的速率添加到令牌桶中，假设限流的速率是r/秒，则令牌每1/r秒会添加一个；
假设令牌桶的容量是b，如果令牌桶已满，则新的令牌会被丢弃；
请求能够通过限流器的前提是令牌桶中有令牌。

令牌桶的容量，是burst的简写，意义是限流器允许的最大突发流量。比如b=10，而且令牌桶中的令牌已满，此时限流器允许10个请求同时通过限流器。只是突发流量而已，这10个请求会带走10个令牌，后续的流量只能按照速率r通过限流器。

并发量不大的情况，令牌桶算法的实现，可以用生产者-消费者模式：一个生产者线程定时向阻塞队列中添加令牌，试图通过限流器的线程则作为消费者线程，只有从阻塞队列中获取到令牌，才允许通过限流器。

高并发场景，系统压力已经临近极限，生产者-消费者模式实现就有问题了。实际情况是使用限流的场景大部分都是高并发场景。在高并发场景下，当系统压力已经临近极限的时候，定时器的精度误差会非常大，同时定时器本身会创建调度线程，也会对系统的心梗产生影响。

Guava实现令牌桶算法

Guava的实现没用使用定时器。用了一个很简单的办法，关键就是记录并动态计算下一令牌发放的时间。

假设令牌桶的容量为b=1，限流速率r=1个请求/秒。

如果当前令牌桶中没有令牌，下一个令牌的发放时间是在第3秒，而在第2秒的时候有一个线程T1请求令牌。

对于这个请求令牌的线程T1而言，需要等待1秒，因为1秒以后(第3秒)它就能拿到令牌了。
下一个令牌的发放时间也要增加1秒，因为第3秒发放的令牌已经被线程T1预占了。

假设T1在预占了第3秒的令牌之后，马上又有一个线程T2请求令牌。

由于下一个令牌产生的而时间是第4秒，所以线程T2要等待2秒的时间，才能获取到令牌，同时由于T2预占了第4秒的令牌，所以下一令牌产生的时间还要增加1秒。

上面线程T1、T2都是在下一令牌产生时间之前请求令牌，如果线程在下一令牌产生时间之后请求令牌：在线程T1请求令牌之后的5秒，也就是第7秒，线程T3请求令牌。

由于在第5秒已经产生了一个令牌，所以此时线程T3可以直接拿到令牌，而无需等待。在第7秒，实际上限流器能够产生3个令牌，第5、6、7秒各产生一个令牌。由于假设了令牌桶的容量是1，所以第6、7秒产生的令牌就丢弃了(等价的也可以认为是保留的第7秒的令牌，丢弃的第5、6秒的令牌)，第7秒的令牌被线程T3占有了，于是下一令牌的产生时间应该是第8秒。

通过分析，只需要记录一个下一令牌产生的时间，并动态更新它，就能够轻松完成限流功能。

class SimpleLimiter {
    //下一令牌产生时间
    long next = System.nanoTime();
    //发放令牌间隔：纳秒
    long interval = 1000000000;
    //预占令牌，返回能够获取令牌的时间
    synchronized long reserve(long now) {
        //请求时间在下一令牌产生时间之后
        //重新计算下一令牌产生时间
        if(now > next) {
            //将下一令牌产生时间重置为当前时间
            next = now;
        }
        //能够获取令牌的时间
        long at = next;
        //设置下一令牌产生时间
        next += interval;
        //返回线程需要等待的时间
        return Math.max(at, 0L);
    }
    //申请令牌
    void acquire() {
        //申请临牌时的时间
        long now = System.nanoTime();
        //预占令牌
        long at = reserve(now);
        long waitTime = max(at - now, 0);
        //按照条件等待
        if(waitTime > 0) {
            try {
                TimeUnit.NANOSECONDS.sleep(waitTime);
            } catch(InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

假设令牌桶的容量是1。关键是reserve()方法，这个方法会为请求令牌的线程预分配令牌，同时返回该线程能够获取令牌的时间。
如果线程请求令牌的时间在下一令牌产生时间之后，那么该线程立刻就能获取令牌；反之，如果请求时间在下一令牌产生时间之前，那么该线程是在下一令牌产生的时间获取令牌。由于此时下一令牌已经被该线程预占，所以下一令牌产生的时间需要加上1秒。

class SimpleLimiter {
    //当前令牌桶中的令牌数量
    long storedPermits = 0;
    //令牌桶的容量
    long maxPermits = 3;
    //下一令牌产生时间
    long next = System.nanoTime();
    //发放令牌间隔：纳秒
    long interval = 1000000000;

    //请求时间在下一令牌产生时间之后，则
    //1.重新计算令牌桶中的令牌数
    //2.将下一令牌发放时间重置为当前时间
    void resync(long now) {
        if(now > next) {
            //新产生的令牌数
            long newPermits = (now - next)/interval;
            //新令牌增加到令牌桶
            storedPermits = min(maxPermits, storedPermits + newPermits);
            //将下一令牌发放时间重置为当前时间
            next = now;
        }
    }
    //预占令牌，返回能够获取令牌的时间
    synchronized long reserve(long now) {
        resync(now);
        //能够获取令牌的时间
        long at = next;
        //令牌桶中能提供的令牌
        long fb = min(1, storedPermits);
        //令牌净需求：首先减掉令牌桶中的令牌
        long nr = 1- fb;
        //重新计算下一令牌产生时间
        next = next + nr*interval;
        //重新计算令牌桶中的令牌
        this.storedPermits -= fb;
        return at;
    }
    //申请令牌
    void acquire() {
        //申请令牌时的时间
        long now = System.nanoTime();
        //预占令牌
        long at = reserve(now);
        long waitTime = max(at-now, 0);
        //按照条件等待
        if(waitTime > 0) {
            try {
                TimeUnit.NANOSECONDS.sleep(waitTime);
            } catch(InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

如果令牌桶的容量大于1。按照令牌桶算法，令牌要首先从令牌桶中出，所以需要按需计算令牌桶中的数量，当有线程请求令牌时，先从令牌桶中出。增加了一个resync()方法，在这个方法中，如果线程请求令牌的时间在下一令牌产生时间之后，会重新计算令牌桶中的令牌数，新产生的令牌的计算公式是：(now-next)/interval。reserve()方法中，则增加了先从令牌桶中出令牌的逻辑(如果令牌是从令牌桶中出的，那么next就无须增加一个interval()了)。

总结

经典的限流算法有两个，一个是令牌桶算法(Token Bucket)，另一个是漏桶算法(Leaky Bucket)。令牌桶算法是定时向令牌桶发送令牌，请求能够从令牌桶中拿到令牌，然后才能通过限流器；而漏桶算法里，请求就像水一样注入漏桶，漏桶会按照一定的速率自动将谁漏掉，只有漏桶里还能注入水的时候，请求才能通过限流。
令牌桶算法和漏桶算法很像一个硬币的正反面。