写在文章开头

这一篇我们来聊一个比较使用的限流工具RateLimiter，它是Google开源的Java类库guava中的一个工具类，本文将从使用和源码分析的角度介绍RateLimiter的设计与实现，希望对你有帮助。

Hi，我是 sharkChili ，是个不断在硬核技术上作死的 java coder ，是 CSDN的博客专家 ，也是开源项目 Java Guide 的维护者之一，熟悉 Java 也会一点 Go ，偶尔也会在 C源码 边缘徘徊。写过很多有意思的技术博客，也还在研究并输出技术的路上，希望我的文章对你有帮助，非常欢迎你关注我的公众号： 写代码的SharkChili 。

因为近期收到很多读者的私信，所以也专门创建了一个交流群，感兴趣的读者可以通过上方的公众号获取笔者的联系方式完成好友添加，点击备注 “加群” 即可和笔者和笔者的朋友们进行深入交流。

详解RateLimiter限流算法的实现

RateLimiter使用示例

假如我们希望每秒只处理一个请求，可以通过RateLimiter的create设置每秒的令牌数为1：

public static void main(String[] args) {
        //设置每秒处理1个请求
        RateLimiter rateLimiter = RateLimiter.create(1);
        //循环100次获取请求
        for (int i = 0; i < 100; i++) {
            rateLimiter.acquire(1);
            System.out.println(DateUtil.format(new Date(), "yyyy-MM-dd HH:mm:ss"));
        }
    }

从输出结果来看，确实是每秒处理1秒输出依次：

2024-07-30 13:11:48
2024-07-30 13:11:49
2024-07-30 13:11:50
2024-07-30 13:11:51
2024-07-30 13:11:52
2024-07-30 13:11:53

详解RateLimiter工作原理

RateLimiter本质上就是使用令牌桶算法完成限流的，这种思想本质是通过动态计算下一令牌发放时间，每当一个请求希望获取令牌，RateLimiter就会基于令牌发放的时间，告知当前线程需要等待的时间，由此避免高并发场景下传统方案中定时投递令牌导致的时延问题。

假设我们1秒发放一个令牌，而RateLimiter内部设置下一次令牌到期时间即nextFreeTicketMicros为3s，这个时间段，基于我们线程1的请求时间1s时，它就需要等待2s，然后更新下次令牌发放时间为4s：

假设第2s线程2也来获取令牌了，基于线程1的计算结果3s的令牌就被拿了，所以此时令牌桶的令牌为0，按照1s产生一个令牌的配置，线程2需要基于nextFreeTicketMicros即线程1令牌预发放时间的基础上加1s，得出线程2需要在4s时才能获取令牌，所以线程2需要等待2s，并更新下次发放时间为5s:

对此我们给出RateLimiter的源码，可以看到acquire方法逻辑就是调用reserve传入需要获取的令牌数得知当前线程要等待的时间，然后进行休眠等待，然后返回等待时长(单位秒)：

@CanIgnoreReturnValue
  public double acquire(int permits) {
  	//调用reserve获取当前线程要等待的时长
    long microsToWait = reserve(permits);
    //休眠等待
    stopwatch.sleepMicrosUninterruptibly(microsToWait);
    //返回等待的秒数
    return 1.0 * microsToWait / SECONDS.toMicros(1L);
  }

步入reserve可以看到它会先检查permits是否大于0，然后通过双重锁校验方式查看是否要初始化全局锁mutexDoNotUseDirectly，然后上锁调用reserveAndGetWaitLength获取令牌看看是否需要等待：

final long reserve(int permits) {
	//前置检查
    checkPermits(permits);
    //上锁
    synchronized (mutex()) {
    //尝试获取令牌，返回等待时长
      return reserveAndGetWaitLength(permits, stopwatch.readMicros());
    }
  }

//双重锁校验懒加载创建锁
private Object mutex() {
    Object mutex = mutexDoNotUseDirectly;
    if (mutex == null) {
      synchronized (this) {
        mutex = mutexDoNotUseDirectly;
        if (mutex == null) {
          mutexDoNotUseDirectly = mutex = new Object();
        }
      }
    }
    return mutex;
  }

步入reserveAndGetWaitLength即可看到它本质就是调用reserveEarliestAvailable获取令牌并得到等待时间，最后返回通过max获取要等待的时长，避免等待时间为负数：

final long reserveAndGetWaitLength(int permits, long nowMicros) {
	//返回令牌到期时间，通过减法计算得出等待时长
    long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
    return max(momentAvailable - nowMicros, 0);
  }

最终我们可以看到reserveEarliestAvailable的逻辑，为了便于读者理解，笔者结合上述讲解例子走一遍源码，首先线程1通过returnValue得知下一次令牌发放时间为3s，这个值最后会返回出去，让线程1基于这个时间计算自己需要等待多久才可以拿到这个令牌，可以看到通过令牌预发放的计算机制保证的时间的准确性，避免了采用生产者-消费者模式定时投放令牌方案的局限性。

后续的步骤则是比较requiredPermits和storedPermits最小值得出本次可以消费的令牌数0，然后计算还差的令牌数freshPermits为1 ，通过这个数得知等待时间为1*stableIntervalMicros(1秒)，stableIntervalMicros为0L，所以得出下次令牌发放时间需要等待时间waitMicros 为1秒。由此更新下一次令牌发放时间为4秒。

对应代码如下，读者可以按照笔者的表述结合代码感知一下这个流程：

@Override
  final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
    //......
    //获取下次发放令牌时间 
    long returnValue = nextFreeTicketMicros;
    //通过二者比较查看本次可以消费几个令牌
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
    //计算后续还需要产出多少个令牌
    double freshPermits = requiredPermits - storedPermitsToSpend;
    //基于freshPermits计算产出令牌的等待时间，storedPermitsToWaitTime为0L
    long waitMicros =
        storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
            + (long) (freshPermits * stableIntervalMicros);
	//基于waitMicros 更新下次可以令牌发放时间
    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
    //基于本次拿到的令牌数扣减库存令牌数storedPermits 
    this.storedPermits -= storedPermitsToSpend;
    return returnValue;
  }

同理线程2算法也是一样的，这里笔者就不多做赘述了。

结合两个流程我们小结一下：

1. 获取本次发放令牌时间nextFreeTicketMicros。
2. 通过min方法获取本次可以拿到的令牌数storedPermitsToSpend ，之所以使用min这个方法获取最小值的原因也很简单，如果我们获取的令牌数requiredPermits小，这就意味着本次只需要从令牌桶中拿小部分令牌即可。如果storedPermits小，则说明本次令牌桶只能发放这么多令牌，通过min运算可以保证本次拿的令牌尽可能小于且趋近于需要拿的令牌数。
3. 通过requiredPermits 减去本次拿到的令牌数storedPermitsToSpend得出还差多少个令牌。
4. 基于差值计算下次令牌发放的等待时长waitMicros 。
5. 基于等待时长waitMicros 得出下次拿到令牌的发放时间nextFreeTicketMicros 。
6. 扣减库存令牌storedPermits数值。

经过这些步骤后，就会返回本次令牌发放时间returnValue ，外部逻辑基于这个值结合当前时间得出当前请求的线程要等待的时间。

RateLimiter如何更新流逝时间需要补充的令牌

讲解完了每秒一个令牌这种基础的场景我们了解的令牌桶的算法的整体步骤了，接下来我们更进一步来了解实际场景中的1秒多个令牌是如何实现的，很简单，我们还是带入上述的代码，以一秒200个请求为例，这意味着0.005s可以处理一个请求，或者说0.005秒产生一个令牌。

每次调用acquire时，实际上代码都会走到resync方法，初始化情况下nextFreeTicketMicros为0，基于这个0结合我们上文计算得的令牌产生间隔0.005即coolDownIntervalMicros方法的返回值，就可以得出令牌数。 程序初次获取令牌时计算的newPermits按照这个差值除以coolDownIntervalMicros(预取令牌的冷却时间间隔)可以得到一个小数，以笔者调试时为例是1.0E-4即0.0001，按照resync逻辑初始化我们的令牌为0.0001个。

后续的取令牌逻辑和上文相同，因为还差0.9999个令牌，所以线程需要等待1*0.9999s：

这里我们也给出resync的代码，逻辑就如笔者所说，读者可参考注释阅读：

@Override
  final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
  	//令牌同步
    resync(nowMicros);
   	//上文所说的取令牌以及更新逻辑
  }


void resync(long nowMicros) {
    //初次步入程序，nowMicros 会大于nextFreeTicketMicros(值为0)
    if (nowMicros > nextFreeTicketMicros) {
    //以当前1s取200个令牌为例，计算得到的令牌是一个小数
      double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
      storedPermits = min(maxPermits, storedPermits + newPermits);
      //更新令牌发放时间为现在
      nextFreeTicketMicros = nowMicros;
    }
  }

后续的线程也会按照这个逻辑通过resync不断调整计算当前微妙得到的令牌数以及还需要等待的时长，由此保证的令牌算法的正常执行，这里就不多赘述。

最后我们给出完整的代码：

@Override
  final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
	//如果当前时间大于令牌发放时间，则通过resync计算这个间隔产生的令牌数，以保证请求者可以获得准确的取令牌时间
    resync(nowMicros);
    //获取下次发放令牌时间 
    long returnValue = nextFreeTicketMicros;
    //通过二者比较查看本次可以消费几个令牌
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
    //计算后续还需要产出多少个令牌
    double freshPermits = requiredPermits - storedPermitsToSpend;
    //基于freshPermits计算产出令牌的等待时间，storedPermitsToWaitTime为0L
    long waitMicros =
        storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
            + (long) (freshPermits * stableIntervalMicros);
	//基于waitMicros 更新下次可以令牌发放时间
    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
    //基于本次拿到的令牌数扣减库存令牌数storedPermits 
    this.storedPermits -= storedPermitsToSpend;
    return returnValue;
  }

小结

自此我们将RateLimiter的使用和基本实现源码分析完成，希望对你有帮助。

我是 sharkchili ，CSDN Java 领域博客专家，开源项目—JavaGuide contributor，我想写一些有意思的东西，希望对你有帮助，如果你想实时收到我写的硬核的文章也欢迎你关注我的公众号： 写代码的SharkChili 。 因为近期收到很多读者的私信，所以也专门创建了一个交流群，感兴趣的读者可以通过上方的公众号获取笔者的联系方式完成好友添加，点击备注 “加群” 即可和笔者和笔者的朋友们进行深入交流。

参考

限速神器RateLimiter源码解析:https://developer.jdcloud.com/article/2921 (opens new window)

guava--RateLimiter源码分析:https://www.cnblogs.com/duanxz/p/14659528.html (opens new window)