流控算法

漏桶算法

令牌桶算法

一年一度的「雙 11」又要到了，阿里的碼農(nóng)們進(jìn)入了一年中最辛苦的時(shí)光。各種容量評(píng)估、壓測(cè)、擴(kuò)容讓我們忙得不可開交。洛陽親友如相問，就說我搞雙十一。

如何讓系統(tǒng)在洶涌澎湃的流量面前談笑風(fēng)生？我們的策略是不要讓系統(tǒng)超負(fù)荷工作。如果現(xiàn)有的系統(tǒng)扛不住業(yè)務(wù)目標(biāo)怎么辦？加機(jī)器！機(jī)器不夠怎么辦？業(yè)務(wù)降級(jí)，系統(tǒng)限流！

正所謂「他強(qiáng)任他強(qiáng)，清風(fēng)拂山崗；他橫任他橫，明月照大江」，降級(jí)和限流是大促保障中必不可少的神兵利器，丟卒保車，以暫停邊緣業(yè)務(wù)為代價(jià)保障核心業(yè)務(wù)的資源，以系統(tǒng)不被突發(fā)流量壓掛為第一要?jiǎng)?wù)。

集團(tuán)的中間件有一個(gè)不錯(cuò)的單機(jī)限流框架，支持兩種限流模式：控制速率和控制并發(fā)。限流這種東西，應(yīng)該是來源于網(wǎng)絡(luò)里面的「流量整型」，通過控制數(shù)據(jù)包的傳輸速率和時(shí)機(jī)，來實(shí)現(xiàn)一些性能、服務(wù)質(zhì)量方面的東西。令牌桶是一種常見的流控算法，屬于控制速率類型的?？刂撇l(fā)則相對(duì)要常見的多，比如操作系統(tǒng)里的「信號(hào)量」就是一種控制并發(fā)的方式。

在 Wikipedia 上，令牌桶算法是這么描述的：

1. 每秒會(huì)有 r 個(gè)令牌放入桶中，或者說，每過 1/r 秒桶中增加一個(gè)令牌

2. 桶中最多存放 b 個(gè)令牌，如果桶滿了，新放入的令牌會(huì)被丟棄

3. 當(dāng)一個(gè) n 字節(jié)的數(shù)據(jù)包到達(dá)時(shí)，消耗 n 個(gè)令牌，然后發(fā)送該數(shù)據(jù)包

4. 如果桶中可用令牌小于 n，則該數(shù)據(jù)包將被緩存或丟棄

令牌桶控制的是一個(gè)時(shí)間窗口內(nèi)的通過的數(shù)據(jù)量，在 API 層面我們常說的 QPS、TPS，正好是一個(gè)時(shí)間窗口內(nèi)的請(qǐng)求量或者事務(wù)量，只不過時(shí)間窗口限定在 1s 罷了。

現(xiàn)實(shí)世界的網(wǎng)絡(luò)工程中使用的令牌桶，比概念圖中的自然是復(fù)雜了許多，「令牌桶」的數(shù)量也不是一個(gè)而是兩個(gè)，簡單的算法描述可用參考中興的期刊[1]或者 RFC。

假如項(xiàng)目使用 Java 語言，我們可以輕松地借助 Guava 的 RateLimiter 來實(shí)現(xiàn)基于令牌桶的流控。RateLimiter 令牌桶算法的單桶實(shí)現(xiàn)，也許是因?yàn)樵?Web 應(yīng)用層面單桶實(shí)現(xiàn)就夠用了，雙筒實(shí)現(xiàn)就屬于過度設(shè)計(jì)。

RateLimiter 對(duì)簡單的令牌桶算法做了一些工程上的優(yōu)化，具體的實(shí)現(xiàn)是 SmoothBursty。需要注意的是，RateLimiter 的另一個(gè)實(shí)現(xiàn) SmoothWarmingUp，就不是令牌桶了，而是漏桶算法。也許是出于簡單起見，RateLimiter 中的時(shí)間窗口能且僅能為 1s，如果想搞其他時(shí)間單位的限流，只能另外造輪子。

SmoothBursty 積極響應(yīng)×××總理的號(hào)召，上個(gè)月的流量沒用完，可以挪到下個(gè)月用。其實(shí)就是 SmoothBursty 有一個(gè)可以放 N 個(gè)時(shí)間窗口產(chǎn)生的令牌的桶，系統(tǒng)空閑的時(shí)候令牌就一直攢著，最好情況下可以扛 N 倍于限流值的高峰而不影響后續(xù)請(qǐng)求。如果不想像三峽大壩一樣能扛千年一遇的洪水，可以把 N 設(shè)置為 1，這樣就只屯一個(gè)時(shí)間窗口的令牌。

RateLimiter 有一個(gè)有趣的特性是「前人挖坑后人跳」，也就是說 RateLimiter 允許某次請(qǐng)求拿走超出剩余令牌數(shù)的令牌，但是下一次請(qǐng)求將為此付出代價(jià)，一直等到令牌虧空補(bǔ)上，并且桶中有足夠本次請(qǐng)求使用的令牌為止[2]。這里面就涉及到一個(gè)權(quán)衡，是讓前一次請(qǐng)求干等到令牌夠用才走掉呢，還是讓它先走掉后面的請(qǐng)求等一等呢？Guava 的設(shè)計(jì)者選擇的是后者，先把眼前的活干了，后面的事后面再說。

當(dāng)我們要實(shí)現(xiàn)一個(gè)基于速率的單機(jī)流控框架的時(shí)候，RateLimiter 是一個(gè)完善的核心組件，就仿佛 Linux 內(nèi)核對(duì) GNU 操作系統(tǒng)那樣重要。但是我們還需要其他的一些東西才能把一個(gè)流控框架跑起來，比如一個(gè)通用的 API，一個(gè)攔截器，一個(gè)在線配置流控閾值的后臺(tái)等等。

下面隨便寫了一個(gè)簡單的流控框架 API，至于攔截器和后臺(tái)就懶得寫了，有時(shí)間再自己造一套中間件的輪子吧~

public class TrafficShaper {    public static class RateLimitException extends Exception {        private static final long serialVersionUID = 1L;        private String resource;        public String getResource() {            return resource;
        }        public RateLimitException(String resource) {            super(resource + " should not be visited so frequently");            this.resource = resource;
        }        @Override        public synchronized Throwable fillInStackTrace() {            return this;
        }
    }    private static final ConcurrentMap<String, RateLimiter>
            resourceLimiterMap = Maps.newConcurrentMap();    public static void updateResourceQps(String resource, double qps) {
        RateLimiter limiter = resourceLimiterMap.get(resource);        if (limiter == null) {
            limiter = RateLimiter.create(qps);
            RateLimiter putByOtherThread
                    = resourceLimiterMap.putIfAbsent(resource, limiter);            if (putByOtherThread != null) {
                limiter = putByOtherThread;
            }
        }
        limiter.setRate(qps);
    }    public static void removeResource(String resource) {
        resourceLimiterMap.remove(resource);
    }    public static void enter(String resource) throws RateLimitException {
        RateLimiter limiter = resourceLimiterMap.get(resource);        if (limiter == null) {            return;
        }        if (!limiter.tryAcquire()) {            throw new RateLimitException(resource);
        }
    }    public static void exit(String resource) {        //do nothing when use RateLimiter
    }
}