RateLimiter 的底层实现是啥？

 前言

本文不是一个RateLimiter的详细分析，仅仅是概要分析。

令牌桶算法

一说到RateLimiter，必然要是说的令牌桶，它的大致逻辑如下：

按图实现

令牌桶的图，网上到处可见，按图实现也非常简单，无非是定时添加令牌桶，并提供一个获取令牌的函数，博主实现了一遍代码如下： 

 
 
 
 

  
  
  
  
import java.util.concurrent.*;  
  
  
  
  
public class MyRateLimiter {  
  
  
  
  
    //令牌桶  
  
  
  
  
    BlockingQueue<Integer>TOKEN_BUCKET=new LinkedBlockingDeque<>(5);  
  
  
  
  
    public static void main(String[] args) {  
  
  
  
  
        MyRateLimiter myRateLimiter=new MyRateLimiter();  
  
  
  
  
        myRateLimiter.addTokenFixedRate();  
  
  
  
  
       for(int i=0;i<10;i++){ 
  
  
  
  
                myRateLimiter.acqurie();  
  
  
  
  
                System.out.println("第几次执行i:" + i + ",执行时间为：" + System.currentTimeMillis());  
  
  
  
  
        }  
  
  
  
  
    }  
  
  
  
  
   /**  
  
  
  
  
    * 定时添加令牌  
  
  
  
  
    */  
  
  
  
  
    public void addTokenFixedRate(){  
  
  
  
  
        ScheduledExecutorService scheduledExecutorService= Executors.newSingleThreadScheduledExecutor();  
  
  
  
  
        scheduledExecutorService.scheduleAtFixedRate(()->{  
  
  
  
  
                    boolean suc=TOKEN_BUCKET.offer(1);  
  
  
  
  
                    if(!suc){  
  
  
  
  
                        System.out.println("令牌桶满了丢弃");  
  
  
  
  
                    }  
  
  
  
  
        },0,200,TimeUnit.MILLISECONDS);  
  
  
  
  
    }  
  
  
  
  
    public void acqurie(){  
  
  
  
  
        while (TOKEN_BUCKET.poll()==null){};  
  
  
  
  
    }  
  
  
  
  
} 
 
 
 
 

测试结果如下,基本满足要求

RateLimiter概要实现

我一开始是按照自己实现的逻辑，去查看Guava的RateLimiter的源码的，结果发现RateLimiter根本没有集合充当桶，核心是记录了下一令牌产生的时间与现存令牌数，并动态更新它们。

概要逻辑图如下：

按照这个图看核心代码就比较容易了，摘录核心代码如下： 

 
 
 
 

  
  
  
  
@CanIgnoreReturnValue  
  
  
  
  
public double acquire(int permits) {  
  
  
  
  
  long microsToWait = reserve(permits);  
  
  
  
  
  stopwatch.sleepMicrosUninterruptibly(microsToWait);  
  
  
  
  
  return 1.0 * microsToWait / SECONDS.toMicros(1L);  
  
  
  
  
}  
  
  
  
  
//Reserve 一路向下能查到如下代码  reserveEarliestAvailable  
  
  
  
  
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {  
  
  
  
  
    resync(nowMicros);  
  
  
  
  
    long returnValue = nextFreeTicketMicros;  
  
  
  
  
 // 现存令牌可以提供的令牌数  
  
  
  
  
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);  
  
  
  
  
 //需要刷新的令牌数  
  
  
  
  
    double freshPermits = requiredPermits - storedPermitsToSpend;  
  
  
  
  
 //等待时间=需要刷新的令牌数*固定间隔+存储许可等待时间  
  
  
  
  
    long waitMicros =  
  
  
  
  
        storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)  
  
  
  
  
            + (long) (freshPermits * stableIntervalMicros); 
  
  
  
  
  //下次令牌生产时间=本次令牌生产时间+等待时间  
  
  
  
  
    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);  
  
  
  
  
    this.storedPermits -= storedPermitsToSpend;  
  
  
  
  
    return returnValue;  
  
  
  
  
} 
 
 
 
 

总结：RateLimiter根本没有集合充当桶，核心是记录了下一令牌产生的时间与现存令牌数，并动态更新它们。最后，关注公众号Java技术栈，在后台回复：面试，可以获取我整理的 Java 系列面试题和答案，非常齐全。