前言

本文不是一個(gè)RateLimiter的詳細(xì)分析，僅僅是概要分析。

令牌桶算法

一說(shuō)到RateLimiter，必然要是說(shuō)的令牌桶，它的大致邏輯如下：

按圖實(shí)現(xiàn)

令牌桶的圖，網(wǎng)上到處可見，按圖實(shí)現(xiàn)也非常簡(jiǎn)單，無(wú)非是定時(shí)添加令牌桶，并提供一個(gè)獲取令牌的函數(shù)，博主實(shí)現(xiàn)了一遍代碼如下： 

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("第幾次執(zhí)行i:" + i + ",執(zhí)行時(shí)間為：" + System.currentTimeMillis());  
        }  
    }  
   /**  
    * 定時(shí)添加令牌  
    */  
    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){};  
    }  
} 

測(cè)試結(jié)果如下,基本滿足要求

RateLimiter概要實(shí)現(xiàn)

我一開始是按照自己實(shí)現(xiàn)的邏輯，去查看Guava的RateLimiter的源碼的，結(jié)果發(fā)現(xiàn)RateLimiter根本沒有集合充當(dāng)桶，核心是記錄了下一令牌產(chǎn)生的時(shí)間與現(xiàn)存令牌數(shù)，并動(dòng)態(tài)更新它們。

概要邏輯圖如下：

按照這個(gè)圖看核心代碼就比較容易了，摘錄核心代碼如下： 

@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;  
 // 現(xiàn)存令牌可以提供的令牌數(shù)  
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);  
 //需要刷新的令牌數(shù)  
    double freshPermits = requiredPermits - storedPermitsToSpend;  
 //等待時(shí)間=需要刷新的令牌數(shù)*固定間隔+存儲(chǔ)許可等待時(shí)間  
    long waitMicros =  
        storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)  
            + (long) (freshPermits * stableIntervalMicros); 
  //下次令牌生產(chǎn)時(shí)間=本次令牌生產(chǎn)時(shí)間+等待時(shí)間  
    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);  
    this.storedPermits -= storedPermitsToSpend;  
    return returnValue;  
} 

總結(jié)：RateLimiter根本沒有集合充當(dāng)桶，核心是記錄了下一令牌產(chǎn)生的時(shí)間與現(xiàn)存令牌數(shù)，并動(dòng)態(tài)更新它們。最后，關(guān)注公眾號(hào)Java技術(shù)棧，在后臺(tái)回復(fù)：面試，可以獲取我整理的 Java 系列面試題和答案，非常齊全。