歡迎光臨
每天分享高質量文章

大型網站限流演算法的實現和改造

(點擊上方公號,快速關註我們)


來源:石玉軍

最近寫了一個限流的插件,所以避免不了的接觸到了一些限流演算法。本篇文章就來分析一下這幾種常見的限流演算法

分析之前

  1. 依我個人的理解來說限流的話應該靈活到可以針對每一個接口來做。比如說一個類裡面有5個接口,那麼我的限流插件就應該能針對每一個接口就行不同的限流方案。所以呢,既然針對的每個接口所以就需要一個可以唯一標示這個接口的key(我取的是類名+方法名+入參)。

  2. 分佈式限流強烈推薦使用redis+lua或者nginx+lua來實現。

  3. 這裡用2個限流條件來做示例講一下常見的限流演算法:


    1. 接口1它10秒鐘最大允許訪問100次

    2. 接口2它10秒鐘最大允許每個人訪問100次。

    計數器演算法

    這個演算法可以說是限流演算法中最簡單的一種演算法了。

    核心思想

    計數器演算法的意思呢就是當接口在一個時間單位中被訪問時,我就記下來訪問次數,直到它訪問的次數到達上限。

    涉及變數

    1. 接口(key)

    2. 時間單位(expire)

    3. 允許訪問多少次(limit)

    4. 訪問次數(value)

    條件一

    當一個請求過來時,我們就會得到這個key。

    if(存在key){

       value++;

       if(value>=limit){

       不能訪問

       }

       }else{

       添加keyvalue1

           設置key過期時間為expire

       }

    條件二

    既然條件一已經實現了,那條件二會複雜麽 ?

    相比於條件一來說就是同一個key對應了多個用戶。那麼我們只需要把key加上用戶的信息就可以了。比如說 key_用戶1、key_用戶2。

    漏桶演算法

    核心思想

    漏桶演算法的意思呢就是一個接口在一個時間單位中允許被訪問次數是動態變化的(假如一分鐘允許訪問60次,那麼從開始計時時不管有沒有被訪問第59秒只允許訪問59次,30秒只允許30次)。為什麼這樣呢,因為有另外一個執行緒在進行遞減操作

    涉及變數

    1. 接口(key)

    2. 時間單位(expire)

    3. 允許訪問多少次(limit)

    4. 遞減間隔時間(interval)

    5. 遞減步長(step)

    6. 剩餘可訪問次數(value)

    7. key的訪問時間(lastUpdateTime)

    8. 當前時間(nowTime)(註意nowTime的取值應為應用取得的時間而不是redis或者nginx取得的時間)

    條件一

    執行緒一:

    if(存在key){

       value

       if(value<=0){

       不能訪問

       }

       }else{

       添加key,設置valuelimit

       }

    執行緒二:

    while(過去interval時間){

       所有keyvaluestep

       }

    條件二

    參考計數器演算法條件二實現。

    演算法升級

    可以看到實現漏桶演算法的話需要每隔interval時間都要另外一條執行緒去遍歷所key的value去做遞減操作,那麼有沒有什麼辦法可以省略這一步呢。答案是肯定有。

    if(存在key){

       value

       if((nowTimelastUpdateTime>interval{

       value=valuenowTimelastUpdateTime/interval*step;

           lastUpdateTime=nowTime;

       }

       if(value<=0){

       不能訪問

       }

       }else{

       添加key,設置valuelimit

           lastUpdateTime=nowTime

       }

    令牌桶演算法

    核心思想

    令牌桶演算法呢,恰恰是和漏桶演算法相反的一個演算法,不過還是推薦你使用這個。這個演算法的原理我不講,我覺得聰明的你看了偽代碼就明白了。

    涉及變數

    1. 接口(key)

    2. 時間單位(expire)

    3. 允許訪問多少次(limit)

    4. 遞增間隔時間(interval)

    5. 遞增步長(step)

    6. 當前可訪問次數(value)

    7. key的訪問時間(lastUpdateTime)

    8. 當前時間(nowTime)(參照漏桶演算法需要註意的點)

    條件一

    執行緒一:

    if(存在key){

       value++

       if(value>=limit){

       不能訪問

       }

       }else{

       添加key,設置valuelimit

       }

    執行緒二:

    while(過去interval時間){

       所有keyvalue+step

       }

    條件二

    參考計算器演算法條件二實現。

    演算法升級

    參考漏桶演算法升級實現。

    代碼

    代碼實現請參考我的限流框架https://github.com/2388386839/syj-ratelimit

    【關於投稿】


    如果大家有原創好文投稿,請直接給公號發送留言。


    ① 留言格式:
    【投稿】+《 文章標題》+ 文章鏈接

    ② 示例:
    【投稿】
    《不要自稱是程式員,我十多年的 IT 職場總結》:

    http://blog.jobbole.com/94148/


    ③ 最後請附上您的個人簡介哈~



    覺得本文有幫助?請分享給更多人

    關註「演算法愛好者」,修煉編程內功

赞(0)

分享創造快樂