接口限流算法：漏桶算法&令牌桶算法

dendoink 發布于2019-08-19 10:55 / 958人閱讀

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

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

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

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

限流算法

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

漏桶算法

把請求比作是水，水來了都先放進桶里，并以限定的速度出水，當水來得過猛而出水不夠快時就會導致水直接溢出，即拒絕服務。

漏斗有一個進水口和一個出水口，出水口以一定速率出水，并且有一個最大出水速率：

在漏斗中沒有水的時候，

如果進水速率小于等于最大出水速率，那么，出水速率等于進水速率，此時，不會積水

如果進水速率大于最大出水速率，那么，漏斗以最大速率出水，此時，多余的水會積在漏斗中

在漏斗中有水的時候

出水口以最大速率出水

如果漏斗未滿，且有進水的話，那么這些水會積在漏斗中

如果漏斗已滿，且有進水的話，那么這些水會溢出到漏斗之外

令牌桶算法

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

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

RateLimiter 用法

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個令牌
  RateLimiter limiter = RateLimiter.create(1);
        for (int i = 1; i < 50; i++) {
            // 請求RateLimiter, 超過permits會被阻塞
  //acquire(int permits)函數主要用于獲取permits個令牌，并計算需要等待多長時間，進而掛起等待，并將該值返回
  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 + " 個任務執行"));
        }
    }
}
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);
    }
}

響應

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

acquire函數主要用于獲取permits個令牌，并計算需要等待多長時間，進而掛起等待，并將該值返回

一個RateLimiter主要定義了發放permits的速率。如果沒有額外的配置，permits將以固定的速度分配，單位是每秒多少permits。默認情況下，Permits將會被穩定的平緩的發放。

預消費能力

從輸出結果可以看出，指定每秒放1個令牌，RateLimiter具有預消費的能力：

acquire 1 時，并沒有任何等待 0.0 秒直接預消費了1個令牌
acquire 10時，由于之前預消費了 1 個令牌，故而等待了1秒，之后又預消費了10個令牌
acquire 2 時，由于之前預消費了 10 個令牌，故而等待了10秒，之后又預消費了2個令牌
acquire 20 時，由于之前預消費了 2 個令牌，故而等待了2秒，之后又預消費了20個令牌
acquire 2 時，由于之前預消費了 20 個令牌，故而等待了20秒，之后又預消費了2個令牌
acquire 2 時，由于之前預消費了 2 個令牌，故而等待了2秒，之后又預消費了2個令牌
acquire 2 時 .....

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

令牌桶算法VS漏桶算法

漏桶

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

令牌桶

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

最后

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

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

Contact

作者：鵬磊

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

版權歸作者所有，轉載請注明出處

Wechat：關注公眾號，搜云庫，專注于開發技術的研究與知識分享

GPU云服務器云服務器 webrtc漏桶算法桶排序算法 java算法符號&lt 令牌桶

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

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

Redis + Lua 接口限流最佳實踐策略

摘要：算法簡介和示例說明業界比較流行的限流算法有漏桶算法和令牌桶算法。判斷接口是否限流其實就是看能不能從令牌桶中取出令牌，方法如下判斷接口是否被限流更新令牌桶狀態到了這里，相信讀者已經對令牌桶算法有了一個比較清晰的認識了。 1.應用場景我們開發的接口服務系統很多都具有抗高并發，保證高可用的特性。現實條件下，隨著流量的不斷增加，在經費、硬件和資源受限的情況下，我們就需要為我們的系統服務制定有...

Julylovin 2019-07-01 14:03 評論0 收藏0
接口限流的常用算法匯總

摘要：接口限流的常用算法計數器法計數器法是限流算法里最簡單也是最容易實現的一種算法。由此可見，當滑動窗口的格子劃分的越多，那么滑動窗口的滾動就越平滑，限流的統計就會越精確。漏桶算法漏桶算法，又稱。接口限流什么是接口限流那么什么是限流呢？顧名思義，限流就是限制流量，包括并發的流量和一定時間內的總流量，就像你寬帶包了1個G的流量，用完了就沒了，所以控制你的使用頻率和單次使用的總消耗。通過限...

gyl_coder 2019-06-27 15:37 評論0 收藏0
8分鐘視頻看懂限流算法

摘要：視頻介紹限流算法，分析漏桶算法和令牌算法的應用場景，算法原理和算法實現方法視頻在這里分鐘看懂限流算法你好，我是好剛，這一講我們來了解限流算法。這里限流的常用算法有漏桶算法和令牌桶算法。所以令牌桶算法的特點是允許突發流量。視頻介紹限流算法，分析漏桶算法和令牌算法的應用場景，算法原理和算法實現方法【視頻在這里】 8分鐘看懂限流算法你好，我是好剛，這一講我們來了解限流算法 (Rate ...

MAX_zuo 2019-07-01 10:16 評論0 收藏0
限流器及Guava實現分析

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

xcc3641 2019-08-19 11:05 評論0 收藏0
幾種限流技術

摘要：下面是幾種常見的限流技術一限流算法常用的限流算法有令牌桶，漏桶令牌桶令牌桶算法是網絡流量整形和速率限制中最常使用的一種算法。就秒殺接口來說，當訪問頻率或者并發請求超過其承受范圍的時候，這時候我們就要考慮限流來保證接口的可用性，以防止非預期的請求對系統壓力過大而引起的系統癱瘓。通常的策略就是拒絕多余的訪問，或者讓多余的訪問排隊等待服務。下面是幾種常見的限流技術一、限流算法常用的限流算...

Warren 2019-08-16 17:30 評論0 收藏0