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

視頻介紹限流算法，分析漏桶算法和令牌算法的應(yīng)用場景，算法原理和算法實(shí)現(xiàn)方法

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

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

首先我們看一個(gè)典型的應(yīng)用場景，比如在商品搶購的場景里面，可能會(huì)有百萬級(jí)別的用戶請(qǐng)求我們的搶購接口。

這個(gè)時(shí)候如果不做任何保護(hù)措施，服務(wù)器就會(huì)承受很大的處理壓力，請(qǐng)求量很高，服務(wù)器負(fù)載也很高，并且當(dāng)請(qǐng)求超過服務(wù)器承載極限的時(shí)候，系統(tǒng)就會(huì)崩潰，導(dǎo)致所有人都不能訪問。為了保證搶購服務(wù)的可用性，一個(gè)常用的辦法是對(duì)秒殺請(qǐng)求進(jìn)行限流，攔截掉大部分請(qǐng)求，只允許一部分請(qǐng)求真正進(jìn)入后端服務(wù)器，這樣就可以防止大量請(qǐng)求造成系統(tǒng)壓力過大導(dǎo)致的系統(tǒng)崩潰，從而保護(hù)服務(wù)正?？捎?。這里限流的常用算法有漏桶算法和令牌桶算法。

我們先來看漏桶算法（Leaky Bucket），先想象有一個(gè)木桶，新請(qǐng)求就像水滴一樣，不斷地滴進(jìn)來，水滴進(jìn)來的速度是不確定的，有時(shí)會(huì)快一點(diǎn)，有時(shí)會(huì)慢一點(diǎn)，同時(shí)桶底下有個(gè)洞，可以按照固定的速度把水漏走，如果水進(jìn)來的速度比漏走的快，桶就會(huì)滿了，桶滿了水就會(huì)漫出來，對(duì)應(yīng)的就是拒絕請(qǐng)求。

漏桶算法的主要特點(diǎn)是可以平滑網(wǎng)絡(luò)上的突發(fā)流量，請(qǐng)求可以被整形成穩(wěn)定的流量。

算法偽代碼如下：

C               // 水桶總?cè)萘?r               // 漏水速度
at              // 上一個(gè)請(qǐng)求時(shí)間
w               // 當(dāng)前桶里面的水量

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

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

我們?cè)倏聪铝钆仆八惴ǎ═oken Bucket）。也是先有一個(gè)木桶，系統(tǒng)按照固定速度，往桶里加入Token，如果桶已經(jīng)滿了就不再添加。當(dāng)有請(qǐng)求到來時(shí)，會(huì)各自拿走一個(gè)Token，取到Token 才能繼續(xù)進(jìn)行請(qǐng)求處理，沒有Token 就拒絕服務(wù)。

這里如果一段時(shí)間沒有請(qǐng)求時(shí)，桶內(nèi)就會(huì)積累一些Token，下次一旦有突發(fā)流量，只要Token 足夠，也能一次處理。所以令牌桶算法的特點(diǎn)是允許突發(fā)流量。

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

算法偽代碼如下:

C   // 水桶總?cè)萘?r   // 添加令牌速度
at = // 上一個(gè)請(qǐng)求時(shí)間
w   // 當(dāng)前令牌數(shù)

when (b):
    bt = now()
    wb = (bt - at) * r    // 兩次請(qǐng)求期間新增的Token
    w = min(w + wb, C)    // 上一個(gè)請(qǐng)求剩余的Token 數(shù)加上新增的剩余數(shù)不能超過木桶的總?cè)萘?
    if (w > 1.0):
        w --              // 令牌足夠，可以處理請(qǐng)求并且將令牌數(shù)減一
        return true
    else:
        return false

最后我們對(duì)比下漏桶算法和令牌桶算法。其實(shí)在實(shí)現(xiàn)上，兩種算法是效果一樣但方向相反的算法。

漏桶算法是請(qǐng)求流入的速度不確定，有時(shí)快有時(shí)慢，是存在突發(fā)情況的；但是請(qǐng)求流出的速度是固定的，它是流入會(huì)有突發(fā)情況，但是流出速度固定。

令牌桶算法就是固定的Token 流入速度，一個(gè)Token 代表一個(gè)請(qǐng)求可以被處理的機(jī)會(huì)；當(dāng)系統(tǒng)有一段空閑時(shí)間之后，桶內(nèi)有足夠的token，這樣可以處理突發(fā)的請(qǐng)求流量，它是流入速度固定，但是流出不固定。

總結(jié)下特點(diǎn)：漏桶算法因?yàn)榱鞒鏊俣裙潭ǎ梢杂脕碚?，無論你流入速率多大，我都按照固定的速度去處理。令牌桶算法的特點(diǎn)則是，支持突發(fā)情況，兩種算法在實(shí)際使用時(shí)，應(yīng)該根據(jù)具體場景靈活選用。

限流算法就介紹到這，我是好剛，好剛用在刀刃上。如果講解對(duì)你有幫助，那就請(qǐng)你幫忙轉(zhuǎn)發(fā)吧。

PHP 實(shí)現(xiàn)

//速度 桶大小 / 時(shí)間段
$rate = $maxRequests / $period;

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

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

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

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

    //使用的令牌數(shù)不能超過最大限制
    if ($allow < $use) {
        $cache->set($a_key, $allow, $ttl);
        return 0;
    } else {
        //消費(fèi)令牌
        $cache->set($a_key, $allow - $use, $ttl);
        return (int) ceil($allow);
    }
} else {
    //記錄當(dāng)前時(shí)間為最后一次處理時(shí)間，用于下次使用
    $cache->set($t_key, time(), $ttl);
    //沒有令牌時(shí)按照最大令牌數(shù)處理
    $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...