1. 限流器

1.1 限流器

常见限流算法：

计数器算法
计数器算法是一种简单的限流方法，通过对请求进行计数，当请求达到一定的阈值时，进行限制。这种方法适用于简单场景，但不够灵活。容易出现临界时间点限流失效问题。
滑动窗口算法
滑动窗口算法维护一个时间窗口内的请求数量，通过动态调整窗口大小，可以更灵活地适应流量的变化。其实就是计数器算法的优化版本，将计数器算法中的单位时间切割成了多块，但也没有完全解决临界时间点限流失效问题。
漏桶算法（Leaky Bucket）
漏桶算法与令牌桶算法类似，但是它是按照固定速率漏水，而不是放入令牌。请求被处理的速度是固定的，当请求到来时，如果漏桶未满，则请求被处理，否则被丢弃或等待。
令牌桶算法（Token Bucket）
令牌桶算法是漏桶算法的优化版，支持突发流量。在令牌桶中，令牌以固定的速率被放入到桶中，而请求要想通过，必须获取到一个令牌。如果桶中没有足够的令牌，请求就会被限制。

1.2 Guava实现原理

Guava就是令牌桶算法的实现。

需要实现的功能点：

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

很容易想到令牌桶的一个实现是：工作线程执行操作前去申请令牌，后台再开启一个子线程定时地添加令牌。但是Guava的RateLimiter限流器并不是这个原理。

RateLimiter的实现是：通过计算下个令牌颁发时间点，并让申请线程休眠对应时长。

假设每次只申请1个令牌（实际上可以申请n个），主要流程如下图所示。

线程执行调用acquire()方法请求令牌，acquire()会调用同步reserve(long time)方法计算下个令牌颁发时间点并返回，线程计算休眠时长后，调用sleep()方法直接休眠对应时长。

1.3 简易限流器代码实现

class RateLimiter {
    // 单个令牌颁发间隔时长,单位纳秒
    private final long INTERVAL = 1000_000_000;
    // 最大令牌数，额外的突发量
    private final long maxPermits;
    // 当前令牌数
    private long storePermits;
    // 下个令牌颁发时间点
    private long next;

    /**
     * @param initPermits 初始令牌数
     * @param maxPermits 最大令牌数
     */
    public RateLimiter(long initPermits, long maxPermits) {
        // 省略合法性检查
        this.storePermits = initPermits;
        this.maxPermits = maxPermits;
    }

    /**
     * 获取令牌，没有令牌则等待
     */
    @SneakyThrows
    public void acquire() {
        // 获取当前时间
        long now = System.nanoTime();
        // 预占令牌，计算可执行时间点
        long timePoint = reverse(now);
        // 计算等待时长, 避免异常负数最小置为0
        long wait = Math.max(timePoint - now, 0);
        // 如果wait大于0，则休眠对应时长
        if (wait > 0) {
            TimeUnit.NANOSECONDS.sleep(wait);
        }
    }

    /**
     * 预占令牌，并返回线程可执行时间点
     * 加锁为了保护共享变量storePermits及next
     *
     * @param now 线程申请令牌时间点
     * @return 可执行时间点
     */
    synchronized private long reverse(long now) {
        // 更新令牌数及下个令牌颁发时间点
        resync(now);
        // 获取下一个令牌颁发时间
        long timePoint = next;
        // 判断是否有令牌
        if (storePermits > 0) {
            // 有令牌，令牌数-1
            storePermits--;
        } else {
            // 没有令牌，下一个令牌颁发时间需要增加一个间隔时长
            next += INTERVAL;
        }
        return timePoint;
    }

    /**
     * 更新令牌数及下个令牌颁发时间点
     * @param now 线程申请令牌时间点
     */
    private void resync(long now) {
        // 如果线程申请令牌时间点比下个令牌颁发时间点还早，那么不需要新增令牌数及更新下个令牌颁发时间点
        if (now <= next) {
            return;
        }
        // 计算新增令牌数, 实际上Guava限流器实现用double更精准
        long newPermits = (now - next) / INTERVAL;
        // 更新令牌数
        storePermits = Math.min(storePermits + newPermits, maxPermits);
        // 更新下次颁发令牌时间点
        next = now;
    }

}

@Slf4j
public class Test {
    @SneakyThrows
    public static void main(String[] args) {
        // 创建固定6个线程的线程池
        ExecutorService executor = Executors.newFixedThreadPool(6);
        // 创建一个初始令牌3个，最大令牌数为3的限流器
        RateLimiter simpleLimiter = new RateLimiter(3, 3);
        // 丢9个数字打印观察
        for (int i = 1; i <= 9; i++) {
            int finalI = i;
            executor.submit(() -> {
                simpleLimiter.acquire();
                log.info(String.valueOf(finalI));
            });
        }
        executor.shutdown();
    }
}

打印如下。由于设置了初始令牌数为3，可以看到刚开始4个线程并发打印。后续则每秒只有1个线程打印。

21:43:31.319 [pool-1-thread-2] INFO com.huaxiaogou.MDog.myguava.Test - 2
21:43:31.319 [pool-1-thread-3] INFO com.huaxiaogou.MDog.myguava.Test - 3
21:43:31.319 [pool-1-thread-4] INFO com.huaxiaogou.MDog.myguava.Test - 4
21:43:31.319 [pool-1-thread-1] INFO com.huaxiaogou.MDog.myguava.Test - 1
21:43:32.323 [pool-1-thread-5] INFO com.huaxiaogou.MDog.myguava.Test - 5
21:43:33.323 [pool-1-thread-6] INFO com.huaxiaogou.MDog.myguava.Test - 6
21:43:34.323 [pool-1-thread-2] INFO com.huaxiaogou.MDog.myguava.Test - 7
21:43:35.323 [pool-1-thread-4] INFO com.huaxiaogou.MDog.myguava.Test - 8
21:43:36.323 [pool-1-thread-3] INFO com.huaxiaogou.MDog.myguava.Test - 9