8分鐘視頻看懂限流算法

MAX_zuo 發布于2019-07-01 10:16 / 1477人閱讀

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

視頻介紹限流算法，分析漏桶算法和令牌算法的應用場景，算法原理和算法實現方法

【視頻在這里】 8分鐘看懂限流算法

你好，我是好剛，這一講我們來了解限流算法 (Rate Limiting Throttling)。

1. 應用場景

首先我們看一個典型的應用場景，比如在商品搶購的場景里面，可能會有百萬級別的用戶請求我們的搶購接口。

這個時候如果不做任何保護措施，服務器就會承受很大的處理壓力，請求量很高，服務器負載也很高，并且當請求超過服務器承載極限的時候，系統就會崩潰，導致所有人都不能訪問。為了保證搶購服務的可用性，一個常用的辦法是對秒殺請求進行限流，攔截掉大部分請求，只允許一部分請求真正進入后端服務器，這樣就可以防止大量請求造成系統壓力過大導致的系統崩潰，從而保護服務正常可用。這里限流的常用算法有漏桶算法和令牌桶算法。

2. 漏桶算法

我們先來看漏桶算法（Leaky Bucket），先想象有一個木桶，新請求就像水滴一樣，不斷地滴進來，水滴進來的速度是不確定的，有時會快一點，有時會慢一點，同時桶底下有個洞，可以按照固定的速度把水漏走，如果水進來的速度比漏走的快，桶就會滿了，桶滿了水就會漫出來，對應的就是拒絕請求。

漏桶算法的主要特點是可以平滑網絡上的突發流量，請求可以被整形成穩定的流量。

算法偽代碼如下：

C               // 水桶總容量
r               // 漏水速度
at              // 上一個請求時間
w               // 當前桶里面的水量

when (b):
      bt = now();
      wb = (bt - at) * r  // 已經流出的水
     w = max(w - wb, 0)  // 桶里面的水量減去流走的水量等于當前水量，最多流干等于0

    if w < C:           // 水桶還沒滿，可以繼續添加
        w ++;
        return true
    else:
        return false

3. 令牌桶算法

我們再看下令牌桶算法（Token Bucket）。也是先有一個木桶，系統按照固定速度，往桶里加入Token，如果桶已經滿了就不再添加。當有請求到來時，會各自拿走一個Token，取到Token 才能繼續進行請求處理，沒有Token 就拒絕服務。

這里如果一段時間沒有請求時，桶內就會積累一些Token，下次一旦有突發流量，只要Token 足夠，也能一次處理。所以令牌桶算法的特點是允許突發流量。

我們看一個例子，看看令牌桶如何允許突發流量，假如令牌則按照每秒5 個的速度放入令牌桶，桶中最多存放20 個令牌，那系統可以支持兩種類型的請求流量，一種是允許持續的每秒處理5 個請求，第二種是每隔4 秒，等桶中20 個令牌攢滿后，就可以處理一次有20 個請求的突發情況。

算法偽代碼如下:

C   // 水桶總容量
r   // 添加令牌速度
at = // 上一個請求時間
w   // 當前令牌數

when (b):
    bt = now()
    wb = (bt - at) * r    // 兩次請求期間新增的Token
    w = min(w + wb, C)    // 上一個請求剩余的Token 數加上新增的剩余數不能超過木桶的總容量

    if (w > 1.0):
        w --              // 令牌足夠，可以處理請求并且將令牌數減一
        return true
    else:
        return false

4. 兩種算法比較

最后我們對比下漏桶算法和令牌桶算法。其實在實現上，兩種算法是效果一樣但方向相反的算法。

漏桶算法是請求流入的速度不確定，有時快有時慢，是存在突發情況的；但是請求流出的速度是固定的，它是流入會有突發情況，但是流出速度固定。

令牌桶算法就是固定的Token 流入速度，一個Token 代表一個請求可以被處理的機會；當系統有一段空閑時間之后，桶內有足夠的token，這樣可以處理突發的請求流量，它是流入速度固定，但是流出不固定。

總結下特點：漏桶算法因為流出速度固定，可以用來整流，無論你流入速率多大，我都按照固定的速度去處理。令牌桶算法的特點則是，支持突發情況，兩種算法在實際使用時，應該根據具體場景靈活選用。

限流算法就介紹到這，我是好剛，好剛用在刀刃上。如果講解對你有幫助，那就請你幫忙轉發吧。

5. 令牌通算法實現

PHP 實現

//速度 桶大小 / 時間段
$rate = $maxRequests / $period;

$t_key = $keyTime($id); //最后一次獲取令牌時間
$a_key = $keyAllow($id); //已有令牌數

//判斷是否有最后一次獲取令牌記錄
if ($cache->exists($t_key)) {
    $c_time = time();
    //計算上一次獲取令牌到現在過去的時間
    $time_passed = $c_time - $cache->get($t_key);
    $cache->set($t_key, $c_time, $ttl);

    //獲取桶中令牌數
    $allow = $cache->get($a_key);
    $allow += $time_passed * $rate; //加上最后一次消費令牌到現在期間增長的令牌數

    //令牌數不能超過最大數
    if ($allow > $maxRequests) {
        $allow = $maxRequests;
    }

    //使用的令牌數不能超過最大限制
    if ($allow < $use) {
        $cache->set($a_key, $allow, $ttl);
        return 0;
    } else {
        //消費令牌
        $cache->set($a_key, $allow - $use, $ttl);
        return (int) ceil($allow);
    }
} else {
    //記錄當前時間為最后一次處理時間，用于下次使用
    $cache->set($t_key, time(), $ttl);
    //沒有令牌時按照最大令牌數處理
    $cache->set($a_key, $maxRequests - $use, $ttl);
    return $maxRequests;
}

參考資料

Token bucket wiki

https://en.wikipedia.org/wiki/Leaky_bucket

PHP Rate Limiting Library With Token Bucket Algorithm

Rate Limiter

https://www.cnblogs.com/haoxinyue/p/6792309.html

https://github.com/yangwenmai/ratelimit

https://blog.52itstyle.com/ar...

云服務器 GPU云服務器微信發10分鐘以上視頻微信怎么發10分鐘視頻電話視頻通話多少錢一分鐘微信怎么發10分鐘視頻給好友

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

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

3分鐘視頻看懂令牌桶算法

摘要：視頻介紹令牌桶，分析令牌桶原理和代碼實現你好，我是好剛，這一講我們來了解令牌桶。總結下令牌桶算法的特點，令牌桶即可以控制進入系統的請求請求量，同時允許突發流量。視頻介紹令牌桶，分析令牌桶原理和代碼實現 https://www.bilibili.com/vide... 你好，我是好剛，這一講我們來了解令牌桶（Token Bucket）。先想象有一個木桶，系統按照固定速率，例如10ms...

novo 2019-07-01 10:17 評論0 收藏0
分布式系統關注點——想通關「限流」？只要這一篇

摘要：之前有了解到哥的一部分讀者們沒有充分搞清楚限流和熔斷的關系。后者表示系統在同一時刻能處理的最大請求數量，比如次的并發。后續限流策略需要設定的具體標準數值就是從這些指標中來的。限流閾值不繼續處理請求。如果這是第二次看到我的文章，歡迎掃描文末二維碼訂閱我喲~本文長度為2869字，建議閱讀8分鐘。可能你在網上看過不少「限流」相關的文章，但是z哥的這篇可能是最全面，最深入淺出的一篇了（容我...

CollinPeng 2019-08-16 13:57 評論0 收藏0
大型網站限流算法的實現和改造

摘要：涉及變量接口時間單位允許訪問多少次遞增間隔時間遞增步長當前可訪問次數的訪問時間當前時間參照漏桶算法需要注意的點條件一線程一存在不能訪問添加，設置為線程二過去時間所有的條件二參考計算器算法條件二實現。算法升級參考漏桶算法升級實現。最近寫了一個限流的插件，所以避免不了的接觸到了一些限流算法。本篇文章就來分析一下這幾種常見的限流算法分析之前依我個人的理解來說限流的話應該靈活到可以針對...

DC_er 2019-08-19 11:16 評論0 收藏0
接口限流的常用算法匯總

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

gyl_coder 2019-06-27 15:37 評論0 收藏0