摘要：令牌桶算法漏桶算法漏桶漏桶的出水速度是恒定的，那么意味著如果瞬時(shí)大流量的話，將有大部分請求被丟棄掉也就是所謂的溢出。

工作中對外提供的API 接口設(shè)計(jì)都要考慮限流，如果不考慮限流，會(huì)成系統(tǒng)的連鎖反應(yīng)，輕者響應(yīng)緩慢，重者系統(tǒng)宕機(jī)，整個(gè)業(yè)務(wù)線崩潰，如何應(yīng)對這種情況呢，我們可以對請求進(jìn)行引流或者直接拒絕等操作，保持系統(tǒng)的可用性和穩(wěn)定性，防止因流量暴增而導(dǎo)致的系統(tǒng)運(yùn)行緩慢或宕機(jī)。

在開發(fā)高并發(fā)系統(tǒng)時(shí)有三把利器用來保護(hù)系統(tǒng)：緩存、降級和限流

緩存：緩存的目的是提升系統(tǒng)訪問速度和增大系統(tǒng)處理容量
降級：降級是當(dāng)服務(wù)器壓力劇增的情況下，根據(jù)當(dāng)前業(yè)務(wù)情況及流量對一些服務(wù)和頁面有策略的降級，以此釋放服務(wù)器資源以保證核心任務(wù)的正常運(yùn)行
限流：限流的目的是通過對并發(fā)訪問/請求進(jìn)行限速，或者對一個(gè)時(shí)間窗口內(nèi)的請求進(jìn)行限速來保護(hù)系統(tǒng)，一旦達(dá)到限制速率則可以拒絕服務(wù)、排隊(duì)或等待、降級等處理

常用的限流算法有令牌桶和和漏桶，而Google開源項(xiàng)目Guava中的RateLimiter使用的就是令牌桶控制算法。

把請求比作是水，水來了都先放進(jìn)桶里，并以限定的速度出水，當(dāng)水來得過猛而出水不夠快時(shí)就會(huì)導(dǎo)致水直接溢出，即拒絕服務(wù)。

漏斗有一個(gè)進(jìn)水口 和 一個(gè)出水口，出水口以一定速率出水，并且有一個(gè)最大出水速率：

在漏斗中沒有水的時(shí)候，

如果進(jìn)水速率小于等于最大出水速率，那么，出水速率等于進(jìn)水速率，此時(shí)，不會(huì)積水

如果進(jìn)水速率大于最大出水速率，那么，漏斗以最大速率出水，此時(shí)，多余的水會(huì)積在漏斗中

在漏斗中有水的時(shí)候

出水口以最大速率出水

如果漏斗未滿，且有進(jìn)水的話，那么這些水會(huì)積在漏斗中

如果漏斗已滿，且有進(jìn)水的話，那么這些水會(huì)溢出到漏斗之外

對于很多應(yīng)用場景來說，除了要求能夠限制數(shù)據(jù)的平均傳輸速率外，還要求允許某種程度的突發(fā)傳輸。這時(shí)候漏桶算法可能就不合適了，令牌桶算法更為適合。

令牌桶算法的原理是系統(tǒng)以恒定的速率產(chǎn)生令牌，然后把令牌放到令牌桶中，令牌桶有一個(gè)容量，當(dāng)令牌桶滿了的時(shí)候，再向其中放令牌，那么多余的令牌會(huì)被丟棄；當(dāng)想要處理一個(gè)請求的時(shí)候，需要從令牌桶中取出一個(gè)令牌，如果此時(shí)令牌桶中沒有令牌，那么則拒絕該請求。

https://github.com/google/guava

添加依賴

  com.google.guava
  guava
  26.0-jre
  
  26.0-android

public class Test {

    public static void main(String[] args) {
        ListeningExecutorService executorService = MoreExecutors.listeningDecorator(Executors.newFixedThreadPool(100));
        // 指定每秒放1個(gè)令牌
  RateLimiter limiter = RateLimiter.create(1);
        for (int i = 1; i < 50; i++) {
            // 請求RateLimiter, 超過permits會(huì)被阻塞
  //acquire(int permits)函數(shù)主要用于獲取permits個(gè)令牌，并計(jì)算需要等待多長時(shí)間，進(jìn)而掛起等待，并將該值返回
  Double acquire = null;
            if (i == 1) {
                acquire = limiter.acquire(1);
            } else if (i == 2) {
                acquire = limiter.acquire(10);
            } else if (i == 3) {
                acquire = limiter.acquire(2);
            } else if (i == 4) {
                acquire = limiter.acquire(20);
            } else {
                acquire = limiter.acquire(2);
            }
            executorService.submit(new Task("獲取令牌成功，獲取耗：" + acquire + " 第 " + i + " 個(gè)任務(wù)執(zhí)行"));
        }
    }
}
class Task implements Runnable {
    String str;
    public Task(String str) {
        this.str = str;
    }
    @Override
  public void run() {
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        System.out.println(sdf.format(new Date()) + " | " + Thread.currentThread().getName() + str);
    }
}

響應(yīng)

2018-08-11 00:26:22.953 | pool-1-thread-1獲取令牌成功，獲取耗：0.0 第 1 個(gè)任務(wù)執(zhí)行
2018-08-11 00:26:23.923 | pool-1-thread-2獲取令牌成功，獲取耗：0.98925 第 2 個(gè)任務(wù)執(zhí)行
2018-08-11 00:26:33.920 | pool-1-thread-3獲取令牌成功，獲取耗：9.996993 第 3 個(gè)任務(wù)執(zhí)行
2018-08-11 00:26:35.920 | pool-1-thread-4獲取令牌成功，獲取耗：1.999051 第 4 個(gè)任務(wù)執(zhí)行
2018-08-11 00:26:55.920 | pool-1-thread-5獲取令牌成功，獲取耗：19.999726 第 5 個(gè)任務(wù)執(zhí)行
2018-08-11 00:26:57.920 | pool-1-thread-6獲取令牌成功，獲取耗：1.999139 第 6 個(gè)任務(wù)執(zhí)行
2018-08-11 00:26:59.920 | pool-1-thread-7獲取令牌成功，獲取耗：1.999806 第 7 個(gè)任務(wù)執(zhí)行
2018-08-11 00:27:01.919 | pool-1-thread-8獲取令牌成功，獲取耗：1.999433 第 8 個(gè)任務(wù)執(zhí)行

acquire函數(shù)主要用于獲取permits個(gè)令牌，并計(jì)算需要等待多長時(shí)間，進(jìn)而掛起等待，并將該值返回

一個(gè)RateLimiter主要定義了發(fā)放permits的速率。如果沒有額外的配置，permits將以固定的速度分配，單位是每秒多少permits。默認(rèn)情況下，Permits將會(huì)被穩(wěn)定的平緩的發(fā)放。

從輸出結(jié)果可以看出，指定每秒放1個(gè)令牌，RateLimiter具有預(yù)消費(fèi)的能力：

acquire 1 時(shí)，并沒有任何等待 0.0 秒 直接預(yù)消費(fèi)了1個(gè)令牌
acquire 10時(shí)，由于之前預(yù)消費(fèi)了 1 個(gè)令牌，故而等待了1秒，之后又預(yù)消費(fèi)了10個(gè)令牌
acquire 2 時(shí)，由于之前預(yù)消費(fèi)了 10 個(gè)令牌，故而等待了10秒，之后又預(yù)消費(fèi)了2個(gè)令牌
acquire 20 時(shí)，由于之前預(yù)消費(fèi)了 2 個(gè)令牌，故而等待了2秒，之后又預(yù)消費(fèi)了20個(gè)令牌
acquire 2 時(shí)，由于之前預(yù)消費(fèi)了 20 個(gè)令牌，故而等待了20秒，之后又預(yù)消費(fèi)了2個(gè)令牌
acquire 2 時(shí)，由于之前預(yù)消費(fèi)了 2 個(gè)令牌，故而等待了2秒，之后又預(yù)消費(fèi)了2個(gè)令牌
acquire 2 時(shí) .....

通俗的講「前人_挖坑_后人跳」,也就說上一次請求獲取的permit數(shù)越多，那么下一次再獲取授權(quán)時(shí)更待的時(shí)候會(huì)更長，反之，如果上一次獲取的少，那么時(shí)間向后推移的就少，下一次獲得許可的時(shí)間更短?？梢?，都是有代價(jià)的。正所謂：要浪漫就要付出代價(jià)。馬上就七夕了，浪漫的代價(jià)可能要花錢啊，單身狗們。

漏桶

漏桶的出水速度是恒定的，那么意味著如果瞬時(shí)大流量的話，將有大部分請求被丟棄掉（也就是所謂的溢出）。

令牌桶

生成令牌的速度是恒定的，而請求去拿令牌是沒有速度限制的。這意味，面對瞬時(shí)大流量，該算法可以在短時(shí)間內(nèi)請求拿到大量令牌，而且拿令牌的過程并不是消耗很大的事情。

不論是對于令牌桶拿不到令牌被拒絕，還是漏桶的水滿了溢出，都是為了保證大部分流量的正常使用，而犧牲掉了少部分流量，這是合理的，如果因?yàn)闃O少部分流量需要保證的話，那么就可能導(dǎo)致系統(tǒng)達(dá)到極限而掛掉，得不償失。

本文講的單機(jī)的限流，是JVM級別的的限流，所有的令牌生成都是在內(nèi)存中，在分布式環(huán)境下不能直接這么用，可用使redis限流。

作者：鵬磊

出處：http://www.ymq.io/2018/08/011/RateLimiter

版權(quán)歸作者所有，轉(zhuǎn)載請注明出處

Wechat：關(guān)注公眾號，搜云庫，專注于開發(fā)技術(shù)的研究與知識分享