俗話說(shuō)得好，緩存，限流和降級(jí)是系統(tǒng)的三把利劍。剛好項(xiàng)目中每天早上導(dǎo)出數(shù)據(jù)時(shí)因調(diào)訂單接口頻率過(guò)高，訂單系統(tǒng)擔(dān)心會(huì)對(duì)用戶(hù)側(cè)的使用造成影響，讓我們對(duì)調(diào)用限速一下，所以就正好用上了。 

常用的限流算法有2種：漏桶算法和令牌桶算法。

漏桶算法

漏桶算法：請(qǐng)求先進(jìn)入“桶”中，然后桶以一定的速率處理請(qǐng)求。如果請(qǐng)求的速率過(guò)快會(huì)導(dǎo)致桶溢出。根據(jù)描述可以知道，漏桶算法會(huì)強(qiáng)制限制請(qǐng)求處理的速度。任你請(qǐng)求的再快還是再慢，我都是以這種速率來(lái)處理。 

但是對(duì)于很多情況下，除了要求能夠限制平均處理速度外，還要求能允許一定程度的的突發(fā)情況。這樣的話，漏桶算法就不合適了，用令牌桶算法更合適。

令牌桶算法

令牌桶算法的原理是：系統(tǒng)以恒定的速率往桶里丟一定數(shù)量的令牌，請(qǐng)求只有拿到了令牌才能處理。當(dāng)桶里沒(méi)有令牌時(shí)便可拒絕服務(wù)。 

Guava中的Ratelimiter便是實(shí)現(xiàn)的令牌桶算法，同時(shí)能支持一定程度的突發(fā)請(qǐng)求。

private static RateLimiter one=RateLimiter.create(2);//每秒2個(gè)
  private static RateLimiter two=RateLimiter.create(2);//每秒2個(gè)
  private RateLimitUtil(){};
  public static void acquire(RateLimiter r,int num){
    double time =r.acquire(num);
    System.out.println("wait time="+time);
  }
  public static void main(String[] args) throws InterruptedException {
    acquire(one,1);
    acquire(one,1);
    acquire(one,1);
    System.out.println("-----");
    acquire(two,10);
    acquire(two,1);
  }

輸出結(jié)果：

wait time=0.0
wait time=0.499163
wait time=0.489308
-----
wait time=0.0
wait time=4.497819

可以看到，我們以每秒2個(gè)請(qǐng)求的速度生成令牌。對(duì)one來(lái)說(shuō)，當(dāng)?shù)?次和第3次獲取請(qǐng)求的時(shí)候，等待的時(shí)間加起來(lái)就差不多剛好是1秒。對(duì)two來(lái)說(shuō)，當(dāng)?shù)谝淮潍@取了10個(gè)令牌之后，第二次獲取1個(gè)請(qǐng)求，就差不多等待5S（10/2=5）?？梢钥吹?，guava通過(guò)限制后面請(qǐng)求的等待時(shí)間，來(lái)支持一定程度的突發(fā)請(qǐng)求。

接下來(lái)，就是通過(guò)源碼來(lái)解析它！ 

當(dāng)我第一次看到令牌桶的算法描述的時(shí)候，我還以為真是有一個(gè)線程每隔X秒往一個(gè)類(lèi)似計(jì)數(shù)器的地方加數(shù)字呢…. 

guava的限流算法有2種模式，一種是穩(wěn)定速度，還有一種是生成令牌的速度慢慢提升直到維持在一個(gè)穩(wěn)定的速度。2種模式原理類(lèi)似，只是在具體等待多久的時(shí)間計(jì)算上有區(qū)別。以下就專(zhuān)門(mén)指穩(wěn)定速度的模式。

先來(lái)看看它的acquire()方法：

public double acquire(int permits) {
  long microsToWait = reserve(permits);//先計(jì)算獲取這些請(qǐng)求需要讓線程等待多長(zhǎng)時(shí)間
  stopwatch.sleepMicrosUninterruptibly(microsToWait);//讓線程阻塞microTowait微秒長(zhǎng)的時(shí)間
  return 1.0 * microsToWait / SECONDS.toMicros(1L);//返回阻塞的時(shí)間
 }

主要分3步： 

1. 根據(jù)limiter創(chuàng)建時(shí)傳入的參數(shù)，計(jì)算出生成這些數(shù)量的令牌需要多長(zhǎng)的時(shí)間。 

2. 讓線程阻塞microTowait這么長(zhǎng)的時(shí)間（單位：微秒） 

3. 再返回阻塞了多久，單位：秒

具體它是怎么計(jì)算需要多長(zhǎng)時(shí)間的呢？讓我們來(lái)看看reserve(permits)方法。

final long reserve(int permits) {
  checkPermits(permits);//檢查參數(shù)是否合法
  synchronized (mutex()) {
   return reserveAndGetWaitLength(permits, stopwatch.readMicros());
  }
 }
    ↓
    ↓
    ↓
 final long reserveAndGetWaitLength(int permits, long nowMicros) {
  long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
  return max(momentAvailable - nowMicros, 0);
 }
    ↓
    ↓
    ↓
 final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
  resync(nowMicros);//here
  long returnValue = nextFreeTicketMicros;
  double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
  double freshPermits = requiredPermits - storedPermitsToSpend;
  long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
    + (long) (freshPermits * stableIntervalMicros);
  this.nextFreeTicketMicros = nextFreeTicketMicros + waitMicros;
  this.storedPermits -= storedPermitsToSpend;
  return returnValue;
 }

最終調(diào)用的是reserveEarliestAvailable方法。先看看resync(nowMicros)方法。

private void resync(long nowMicros) {
  // if nextFreeTicket is in the past, resync to now
  if (nowMicros > nextFreeTicketMicros) {
   storedPermits = min(maxPermits,
     storedPermits + (nowMicros - nextFreeTicketMicros) / stableIntervalMicros);
   nextFreeTicketMicros = nowMicros;
  }
 }

nextFreeTicketMicros的意思是：下次獲取的時(shí)候需要減去的時(shí)間。如果是第一次調(diào)用accquire()方法，那nowMicros - nextFreeTicketMicros 就是從初始化（初始化的時(shí)候會(huì)給nextFreeTicketMicros 賦值一次,具體可以看RateLimiter的構(gòu)造器）到第一次請(qǐng)求，這中間發(fā)生的時(shí)間。 

這個(gè)方法的意思，如果當(dāng)前時(shí)間比上一輪設(shè)置的下次獲取的時(shí)間大（因?yàn)榇嬖谔崆矮@取的情況，比如上次直接獲取了10個(gè)，那上輪設(shè)置的nextFreeTicketMicros就是上一輪的時(shí)間+5s。后面會(huì)提到），那就計(jì)算這個(gè)中間理論上能生成多少的令牌。比如這中間隔了1秒鐘，然后stableIntervalMicros=5000（穩(wěn)定生成速度的情況下）,那么，就這中間就可以生成2個(gè)令牌。再加上它原先存儲(chǔ)的storedPermits個(gè)，如果比maxPermits大，那最大也只能存maxPermits這么多。如果比maxPermits小，那就是storedPermits=原先存的+這中間生成的數(shù)量。同時(shí)記錄下下次獲取的時(shí)候需要減去的時(shí)間，也就是當(dāng)前時(shí)間 （nextFreeTicketMicros ）。 

接下來(lái)繼續(xù)看reserveEarliestAvailable方法：

final long reserveEarliestAvailable(int requiredPermits, long nowMicros) { //1
  resync(nowMicros);   //2
  long returnValue = nextFreeTicketMicros;//3
  double storedPermitsToSpend = min(requiredPermits, this.storedPermits);//4
  double freshPermits = requiredPermits - storedPermitsToSpend;//5
  long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
    + (long) (freshPermits * stableIntervalMicros);//6
  this.nextFreeTicketMicros = nextFreeTicketMicros + waitMicros;//7
  this.storedPermits -= storedPermitsToSpend;//8
  return returnValue;//9
 }

我們一行一行來(lái)看： 

第二行設(shè)置好之后。第3行中將下次獲取的時(shí)候需要減去的時(shí)間作為返回值（這點(diǎn)很重要）。 

這2句是什么意思呢？ 

其實(shí)這2句就是使得RateLimiter能一定程度的突發(fā)請(qǐng)求的原因。假設(shè)requiredPermits=10，而我們能存的storedPermits=2，那么freshPermits=8，也就是多取了8個(gè)。而第6行就是計(jì)算這多取的8個(gè)需要多長(zhǎng)時(shí)間才能生成？需要3秒。那么，就將這3秒鐘加到我們前面賦值的“下次獲取的時(shí)候需要減去的時(shí)間 ”。 

比如在05秒的時(shí)候一次性獲取了10個(gè)，那么，第7行的意思就是nextFreeTicketMicros=13S對(duì)應(yīng)的系統(tǒng)的毫秒數(shù)。然后storedPermits就是-8。當(dāng)過(guò)了1秒鐘，下一次請(qǐng)求來(lái)調(diào)用acquire(1)的時(shí)候，resync方法中由于nowMicros

final long reserveAndGetWaitLength(int permits, long nowMicros) {
  long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
  return max(momentAvailable - nowMicros, 0);//取較大的值
 }

也就是說(shuō)，reserveAndGetWaitLength會(huì)返回max(13-6,0)，也就是7。而該方法的返回值又是用于sleep線程的，也就是我們?cè)谝婚_(kāi)始看到的：

public double acquire(int permits) {
  long microsToWait = reserve(permits);
  stopwatch.sleepMicrosUninterruptibly(microsToWait);
  return 1.0 * microsToWait / SECONDS.toMicros(1L);
 }

總結(jié)起來(lái)，最主要的是nowMicros,nextFreeTicketMicros這2個(gè)值。nextFreeTicketMicros在一開(kāi)始構(gòu)造器執(zhí)行的時(shí)候會(huì)賦值一次為構(gòu)造器執(zhí)行的時(shí)間。當(dāng)?shù)谝淮握{(diào)用accquire()的時(shí)候，resync會(huì)被執(zhí)行，然后在accquire()中將nextFreeTicketMicros設(shè)置為當(dāng)前時(shí)間。但是，需要注意的是，在reserveEarliestAvailable中會(huì)根據(jù)請(qǐng)求的令牌數(shù)和當(dāng)前存儲(chǔ)的令牌數(shù)進(jìn)行比較。如果請(qǐng)求的令牌數(shù)很大，則會(huì)計(jì)算出生成這些多余的令牌需要的時(shí)間，并加在nextFreeTicketMicros上，從而保證下次調(diào)用accquire()的時(shí)候，根據(jù)nextFreeTicketMicros和當(dāng)時(shí)的nowMicros相減，若>0，則需要等到對(duì)應(yīng)的時(shí)間。也就能應(yīng)對(duì)流量的突增情況了。 

所以最重要的是nextFreeTicketMicros，它記錄了你這次獲取的時(shí)候，能夠開(kāi)始生成令牌的時(shí)間。比如當(dāng)前是05S，那若nextFreeTicketMicros=10，表示它要到10S才能開(kāi)始生成令牌，誰(shuí)叫前面的多拿了這么多呢。至于它這次是多拿了還是只是拿一個(gè)令牌，等待時(shí)間都是這么多。如果這次又多拿了，那下次就等待更久！

private static RateLimiter too=RateLimiter.create(2);//每秒2個(gè)
  private RateLimitUtil(){};
  public static void acquire(RateLimiter r,int num){
    double time =r.acquire(num);
    System.out.println("wait time="+time);
  }
  public static void main(String[] args) throws InterruptedException {
    acquire(too,1);
    acquire(too,10);//只等待了0.5秒就獲取了10個(gè)
    acquire(too,10);//等待了5秒就獲取了10個(gè)
    acquire(too,1);//雖然只獲取1個(gè)，也是等待5秒
  }

總結(jié)

以上就是本文關(guān)于RateLimiter 常用方法以及源碼分析的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以參閱：關(guān)于Openfire集群源碼的分析 、 Spring SpringMVC在啟動(dòng)完成后執(zhí)行方法源碼解析 、 Java查看本機(jī)端口是否被占用源碼等。感謝大家對(duì)腳本之家網(wǎng)站的支持！

最新評(píng)論