国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

使用Guava RateLimiter限流以及源碼解析

simpleapples / 3218人閱讀

摘要:令牌桶算法對于很多應用場景來說,除了要求能夠限制數據的平均傳輸速率外,還要求允許某種程度的突發傳輸。使用以及源碼解析開源工具包提供了限流工具類,該類基于令牌桶算法實現流量限制,使用十分方便,而且十分高效。

前言

在開發高并發系統時有三把利器用來保護系統:緩存、降級和限流

緩存 緩存的目的是提升系統訪問速度和增大系統處理容量

降級 降級是當服務出現問題或者影響到核心流程時,需要暫時屏蔽掉,待高峰或者問題解決后再打開

限流 限流的目的是通過對并發訪問/請求進行限速,或者對一個時間窗口內的請求進行限速來保護系統,一旦達到限制速率則可以拒絕服務、排隊或等待、降級等處理

常用的限流算法 漏桶算法
漏桶算法思路很簡單,水(請求)先進入到漏桶里,漏桶以一定的速度出水,當水流入速度過大會直接溢出,可以看出漏桶算法能強行限制數據的傳輸速率。

令牌桶算法
對于很多應用場景來說,除了要求能夠限制數據的平均傳輸速率外,還要求允許某種程度的突發傳輸。這時候漏桶算法可能就不合適了,令牌桶算法更為適合。如圖所示,令牌桶算法的原理是系統會以一個恒定的速度往桶里放入令牌,而如果請求需要被處理,則需要先從桶里獲取一個令牌,當桶里沒有令牌可取時,則拒絕服務。

RateLimiter使用以及源碼解析
Google開源工具包Guava提供了限流工具類RateLimiter,該類基于令牌桶算法實現流量限制,使用十分方便,而且十分高效。
RateLimiter使用

首先簡單介紹下RateLimiter的使用,

public void testAcquire() {
      RateLimiter limiter = RateLimiter.create(1);

      for(int i = 1; i < 10; i = i + 2 ) {
          double waitTime = limiter.acquire(i);
          System.out.println("cutTime=" + System.currentTimeMillis() + " acq:" + i + " waitTime:" + waitTime);
      }
  }

輸出結果:

cutTime=1535439657427 acq:1 waitTime:0.0
cutTime=1535439658431 acq:3 waitTime:0.997045
cutTime=1535439661429 acq:5 waitTime:2.993028
cutTime=1535439666426 acq:7 waitTime:4.995625
cutTime=1535439673426 acq:9 waitTime:6.999223

首先通過RateLimiter.create(1);創建一個限流器,參數代表每秒生成的令牌數,通過limiter.acquire(i);來以阻塞的方式獲取令牌,當然也可以通過tryAcquire(int permits, long timeout, TimeUnit unit)來設置等待超時時間的方式獲取令牌,如果超timeout為0,則代表非阻塞,獲取不到立即返回。

從輸出來看,RateLimiter支持預消費,比如在acquire(5)時,等待時間是3秒,是上一個獲取令牌時預消費了3個兩排,固需要等待3*1秒,然后又預消費了5個令牌,以此類推

RateLimiter通過限制后面請求的等待時間,來支持一定程度的突發請求(預消費),在使用過程中需要注意這一點,具體實現原理后面再分析。

RateLimiter實現原理
Guava有兩種限流模式,一種為穩定模式(SmoothBursty:令牌生成速度恒定),一種為漸進模式(SmoothWarmingUp:令牌生成速度緩慢提升直到維持在一個穩定值) 兩種模式實現思路類似,主要區別在等待時間的計算上,本篇重點介紹SmoothBursty
RateLimiter的創建

通過調用RateLimiter的create接口來創建實例,實際是調用的SmoothBuisty穩定模式創建的實例。

public static RateLimiter create(double permitsPerSecond) {
    return create(permitsPerSecond, SleepingStopwatch.createFromSystemTimer());
  }

  static RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {
    RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
    rateLimiter.setRate(permitsPerSecond);
    return rateLimiter;
  }

SmoothBursty中的兩個構造參數含義:

SleepingStopwatch:guava中的一個時鐘類實例,會通過這個來計算時間及令牌

maxBurstSeconds:官方解釋,在ReteLimiter未使用時,最多保存幾秒的令牌,默認是1

在解析SmoothBursty原理前,重點解釋下SmoothBursty中幾個屬性的含義

/**
 * The work (permits) of how many seconds can be saved up if this RateLimiter is unused?
 * 在RateLimiter未使用時,最多存儲幾秒的令牌
 * */
 final double maxBurstSeconds;
 

/**
 * The currently stored permits.
 * 當前存儲令牌數
 */
double storedPermits;

/**
 * The maximum number of stored permits.
 * 最大存儲令牌數 = maxBurstSeconds * stableIntervalMicros(見下文)
 */
double maxPermits;

/**
 * The interval between two unit requests, at our stable rate. E.g., a stable rate of 5 permits
 * per second has a stable interval of 200ms.
 * 添加令牌時間間隔 = SECONDS.toMicros(1L) / permitsPerSecond;(1秒/每秒的令牌數)
 */
double stableIntervalMicros;

/**
 * The time when the next request (no matter its size) will be granted. After granting a request,
 * this is pushed further in the future. Large requests push this further than small requests.
 * 下一次請求可以獲取令牌的起始時間
 * 由于RateLimiter允許預消費,上次請求預消費令牌后
 * 下次請求需要等待相應的時間到nextFreeTicketMicros時刻才可以獲取令牌
 */
private long nextFreeTicketMicros = 0L; // could be either in the past or future

接下來介紹幾個關鍵函數

setRate

public final void setRate(double permitsPerSecond) {
  checkArgument(
      permitsPerSecond > 0.0 && !Double.isNaN(permitsPerSecond), "rate must be positive");
  synchronized (mutex()) {
    doSetRate(permitsPerSecond, stopwatch.readMicros());
  }
}

通過這個接口設置令牌通每秒生成令牌的數量,內部時間通過調用SmoothRateLimiterdoSetRate來實現

doSetRate

@Override
  final void doSetRate(double permitsPerSecond, long nowMicros) {
    resync(nowMicros);
    double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond;
    this.stableIntervalMicros = stableIntervalMicros;
    doSetRate(permitsPerSecond, stableIntervalMicros);
  }

這里先通過調用resync生成令牌以及更新下一期令牌生成時間,然后更新stableIntervalMicros,最后又調用了SmoothBurstydoSetRate

resync

/**
 * Updates {@code storedPermits} and {@code nextFreeTicketMicros} based on the current time.
 * 基于當前時間,更新下一次請求令牌的時間,以及當前存儲的令牌(可以理解為生成令牌)
 */
void resync(long nowMicros) {
    // if nextFreeTicket is in the past, resync to now
    if (nowMicros > nextFreeTicketMicros) {
      double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
      storedPermits = min(maxPermits, storedPermits + newPermits);
      nextFreeTicketMicros = nowMicros;
    }
}

根據令牌桶算法,桶中的令牌是持續生成存放的,有請求時需要先從桶中拿到令牌才能開始執行,誰來持續生成令牌存放呢?

一種解法是,開啟一個定時任務,由定時任務持續生成令牌。這樣的問題在于會極大的消耗系統資源,如,某接口需要分別對每個用戶做訪問頻率限制,假設系統中存在6W用戶,則至多需要開啟6W個定時任務來維持每個桶中的令牌數,這樣的開銷是巨大的。

另一種解法則是延遲計算,如上resync函數。該函數會在每次獲取令牌之前調用,其實現思路為,若當前時間晚于nextFreeTicketMicros,則計算該段時間內可以生成多少令牌,將生成的令牌加入令牌桶中并更新數據。這樣一來,只需要在獲取令牌時計算一次即可。

SmoothBursty的doSetRate

@Override
void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
  double oldMaxPermits = this.maxPermits;
  maxPermits = maxBurstSeconds * permitsPerSecond;
  if (oldMaxPermits == Double.POSITIVE_INFINITY) {
    // if we don"t special-case this, we would get storedPermits == NaN, below
    // Double.POSITIVE_INFINITY 代表無窮啊
    storedPermits = maxPermits;
  } else {
    storedPermits =
        (oldMaxPermits == 0.0)
            ? 0.0 // initial state
            : storedPermits * maxPermits / oldMaxPermits;
  }
}

桶中可存放的最大令牌數由maxBurstSeconds計算而來,其含義為最大存儲maxBurstSeconds秒生成的令牌。
該參數的作用在于,可以更為靈活地控制流量。如,某些接口限制為300次/20秒,某些接口限制為50次/45秒等。也就是流量不局限于qps

RateLimiter幾個常用接口分析

在了解以上概念后,就非常容易理解RateLimiter暴露出來的接口

@CanIgnoreReturnValue
public double acquire() {
  return acquire(1);
}

/**
* 獲取令牌,返回阻塞的時間
**/
@CanIgnoreReturnValue
public double acquire(int permits) {
  long microsToWait = reserve(permits);
  stopwatch.sleepMicrosUninterruptibly(microsToWait);
  return 1.0 * microsToWait / SECONDS.toMicros(1L);
}

final long reserve(int permits) {
  checkPermits(permits);
  synchronized (mutex()) {
    return reserveAndGetWaitLength(permits, stopwatch.readMicros());
  }
}

acquire函數主要用于獲取permits個令牌,并計算需要等待多長時間,進而掛起等待,并將該值返回,主要通過reserve返回需要等待的時間,reserve中通過調用reserveAndGetWaitLength獲取等待時間

/**
 * Reserves next ticket and returns the wait time that the caller must wait for.
 *
 * @return the required wait time, never negative
 */
final long reserveAndGetWaitLength(int permits, long nowMicros) {
  long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
  return max(momentAvailable - nowMicros, 0);
}

最后調用了reserveEarliestAvailable

@Override
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;
}
首先通過resync生成令牌以及同步nextFreeTicketMicros時間戳,freshPermits從令牌桶中獲取令牌后還需要的令牌數量,通過storedPermitsToWaitTime計算出獲取freshPermits還需要等待的時間,在穩定模式中,這里就是(long) (freshPermits * stableIntervalMicros) ,然后更新nextFreeTicketMicros以及storedPermits,這次獲取令牌需要的等待到的時間點, reserveAndGetWaitLength返回需要等待的時間間隔。

從`reserveEarliestAvailable`可以看出RateLimiter的預消費原理,以及獲取令牌的等待時間時間原理(可以解釋示例結果),再獲取令牌不足時,并沒有等待到令牌全部生成,而是更新了下次獲取令牌時的nextFreeTicketMicros,從而影響的是下次獲取令牌的等待時間。



 `reserve`這里返回等待時間后,`acquire`通過調用`stopwatch.sleepMicrosUninterruptibly(microsToWait);`進行sleep操作,這里不同于Thread.sleep(), 這個函數的sleep是uninterruptibly的,內部實現:
public static void sleepUninterruptibly(long sleepFor, TimeUnit unit) {
    //sleep 阻塞線程 內部通過Thread.sleep()
  boolean interrupted = false;
  try {
    long remainingNanos = unit.toNanos(sleepFor);
    long end = System.nanoTime() + remainingNanos;
    while (true) {
      try {
        // TimeUnit.sleep() treats negative timeouts just like zero.
        NANOSECONDS.sleep(remainingNanos);
        return;
      } catch (InterruptedException e) {
        interrupted = true;
        remainingNanos = end - System.nanoTime();
        //如果被interrupt可以繼續,更新sleep時間,循環繼續sleep
      }
    }
  } finally {
    if (interrupted) {
      Thread.currentThread().interrupt();
      //如果被打斷過,sleep過后再真正中斷線程
    }
  }
}
 sleep之后,`acquire`返回sleep的時間,阻塞結束,獲取到令牌。


public boolean tryAcquire(int permits) {
  return tryAcquire(permits, 0, MICROSECONDS);
}

public boolean tryAcquire() {
  return tryAcquire(1, 0, MICROSECONDS);
}

public boolean tryAcquire(int permits, long timeout, TimeUnit unit) {
  long timeoutMicros = max(unit.toMicros(timeout), 0);
  checkPermits(permits);
  long microsToWait;
  synchronized (mutex()) {
    long nowMicros = stopwatch.readMicros();
    if (!canAcquire(nowMicros, timeoutMicros)) {
      return false;
    } else {
      microsToWait = reserveAndGetWaitLength(permits, nowMicros);
    }
  }
  stopwatch.sleepMicrosUninterruptibly(microsToWait);
  return true;
}

private boolean canAcquire(long nowMicros, long timeoutMicros) {
  return queryEarliestAvailable(nowMicros) - timeoutMicros <= nowMicros;
}

@Override
final long queryEarliestAvailable(long nowMicros) {
  return nextFreeTicketMicros;
}

tryAcquire函數可以嘗試在timeout時間內獲取令牌,如果可以則掛起等待相應時間并返回true,否則立即返回false
canAcquire用于判斷timeout時間內是否可以獲取令牌,通過判斷當前時間+超時時間是否大于nextFreeTicketMicros 來決定是否能夠拿到足夠的令牌數,如果可以獲取到,則過程同acquire,線程sleep等待,如果通過canAcquire在此超時時間內不能回去到令牌,則可以快速返回,不需要等待timeout后才知道能否獲取到令牌。

因為SmoothBursty允許一定程度的突發,會有人擔心如果允許這種突發,假設突然間來了很大的流量,那么系統很可能扛不住這種突發。因此需要一種平滑速率的限流工具,從而系統冷啟動后慢慢的趨于平均固定速率(即剛開始速率小一些,然后慢慢趨于我們設置的固定速率)。Guava也提供了SmoothWarmingUp來實現這種需求,其可以認為是漏桶算法,但是在某些特殊場景又不太一樣。

SmoothWarmingUp創建方式:

public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) {
  checkArgument(warmupPeriod >= 0, "warmupPeriod must not be negative: %s", warmupPeriod);
  return create(
      permitsPerSecond, warmupPeriod, unit, 3.0, SleepingStopwatch.createFromSystemTimer());
}

permitsPerSecond表示每秒新增的令牌數,warmupPeriod表示在從冷啟動速率過渡到平均速率的時間間隔,大致原理是類似的,這里就先不分析了。

到此,Guava RateLimiter穩定模式的實現原理基本已經清楚,如發現文中錯誤的地方,勞煩指正!

上述分析主要參考了:https://segmentfault.com/a/11...,再此基礎上做了些筆記補充

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/76899.html

相關文章

  • 限流器及Guava實現分析

    摘要:計數限流算法無論固定窗口還是滑動窗口核心均是對請求進行計數,區別僅僅在于對于計數時間區間的處理。令牌桶限流實現原理令牌桶限流的實現原理在有詳細說明。因此由此為入口進行分析。目前可返回的實現子類包括及兩種,具體不同下文詳細分析。 限流 限流一詞常用于計算機網絡之中,定義如下: In computer networks, rate limiting is used to control t...

    xcc3641 評論0 收藏0
  • 服務限流(自定義注解令牌桶算法)

    摘要:自定義注解實現基于接口限流仔細看會發現上面的簡單實現會造成我每個接口都要寫一次限流方法代碼很冗余所以采用來使用自定義注解來實現。 服務限流 -- 自定義注解基于RateLimiter實現接口限流 令牌桶限流算法showImg(https://segmentfault.com/img/bVbgTi6?w=2420&h=1547);圖片來自網上 令牌桶會以一個恒定的速率向固定容量大小桶...

    microcosm1994 評論0 收藏0
  • 接口限流算法:漏桶算法&令牌桶算法

    摘要:令牌桶算法漏桶算法漏桶漏桶的出水速度是恒定的,那么意味著如果瞬時大流量的話,將有大部分請求被丟棄掉也就是所謂的溢出。 工作中對外提供的API 接口設計都要考慮限流,如果不考慮限流,會成系統的連鎖反應,輕者響應緩慢,重者系統宕機,整個業務線崩潰,如何應對這種情況呢,我們可以對請求進行引流或者直接拒絕等操作,保持系統的可用性和穩定性,防止因流量暴增而導致的系統運行緩慢或宕機。 在開發高并發...

    dendoink 評論0 收藏0
  • RateLimter源碼解析

    摘要:允許突發流量的平滑限流器的實現。實例執行結果方法返回結果代表獲取所等待的時間。先看下示例代碼運行效果為了預防突然暴增的流量將系統壓垮,很貼心的增加了預熱。 RateLimiter 類圖 showImg(https://segmentfault.com/img/bVbflrs?w=1598&h=1076); RateLimiter:作為抽象類提供一個限流器的基本的抽象方法。SmoothR...

    RaoMeng 評論0 收藏0

發表評論

0條評論

simpleapples

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<