摘要：涉及變量接口時(shí)間單位允許訪問多少次遞增間隔時(shí)間遞增步長當(dāng)前可訪問次數(shù)的訪問時(shí)間當(dāng)前時(shí)間參照漏桶算法需要注意的點(diǎn)條件一線程一存在不能訪問添加，設(shè)置為線程二過去時(shí)間所有的條件二參考計(jì)算器算法條件二實(shí)現(xiàn)。算法升級(jí)參考漏桶算法升級(jí)實(shí)現(xiàn)。

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

依我個(gè)人的理解來說限流的話應(yīng)該靈活到可以針對(duì)每一個(gè)接口來做。比如說一個(gè)類里面有5個(gè)接口，那么我的限流插件就應(yīng)該能針對(duì)每一個(gè)接口就行不同的限流方案。所以呢，既然針對(duì)的每個(gè)接口所以就需要一個(gè)可以唯一標(biāo)示這個(gè)接口的key（我取的是類名+方法名+入?yún)ⅲ?。分布式限流?qiáng)烈推薦使用redis+lua或者nginx+lua來實(shí)現(xiàn)。

這里用2個(gè)限流條件來做示例講一下常見的限流算法：
   1.  接口1它10秒鐘最大允許訪問100次
   2.  接口2它10秒鐘最大允許每個(gè)人訪問100次。

這個(gè)算法可以說是限流算法中最簡單的一種算法了。

計(jì)數(shù)器算法的意思呢就是當(dāng)接口在一個(gè)時(shí)間單位中被訪問時(shí)，我就記下來訪問次數(shù)，直到它訪問的次數(shù)到達(dá)上限。
涉及變量

1.接口（key）
2.時(shí)間單位（expire）
3.允許訪問多少次（limit）
4.訪問次數(shù)（value）

當(dāng)一個(gè)請(qǐng)求過來時(shí)，我們就會(huì)得到這個(gè)key。

if(存在key){
   value++;
   if(value>=limit){
           不能訪問
       }
   }else{
       添加key，value為1
       設(shè)置key過期時(shí)間為expire
   }

既然條件一已經(jīng)實(shí)現(xiàn)了，那條件二會(huì)復(fù)雜么 ？

相比于條件一來說就是同一個(gè)key對(duì)應(yīng)了多個(gè)用戶。那么我們只需要把key加上用戶的信息就可以了。比如說 key_用戶1、key_用戶2。

漏桶算法的意思呢就是一個(gè)接口在一個(gè)時(shí)間單位中允許被訪問次數(shù)是動(dòng)態(tài)變化的（假如一分鐘允許訪問60次，那么從開始計(jì)時(shí)時(shí)不管有沒有被訪問第59秒只允許訪問59次，30秒只允許30次）。為什么這樣呢，因?yàn)橛辛硗庖粋€(gè)線程在進(jìn)行遞減操作

1.接口（key）
2.時(shí)間單位（expire）
3.允許訪問多少次（limit）
4.遞減間隔時(shí)間（interval）
5.遞減步長（step）
6.剩余可訪問次數(shù)（value）
7.key的訪問時(shí)間（lastUpdateTime）
8.當(dāng)前時(shí)間（nowTime）（注意nowTime的取值應(yīng)為應(yīng)用取得的時(shí)間而不是redis或者nginx取得的時(shí)間）

1

if(存在key){
   value--；
   if(value<=0){
           不能訪問
       }
   }else{
       添加key，設(shè)置value為limit
   }

while(過去interval時(shí)間){
   所有key的value-step
   }

參考計(jì)數(shù)器算法條件二實(shí)現(xiàn)。

可以看到實(shí)現(xiàn)漏桶算法的話需要每隔interval時(shí)間都要另外一條線程去遍歷所key的value去做遞減操作，那么有沒有什么辦法可以省略這一步呢。答案是肯定有。

if(存在key){
   value--；
   if（（nowTime-lastUpdateTime）>interval）{
       value=value-（nowTime-lastUpdateTime）/interval*step;
       lastUpdateTime=nowTime;
   }
   if(value<=0){
           不能訪問
       }
   }else{
       添加key，設(shè)置value為limit；
       lastUpdateTime=nowTime；
   }

令牌桶算法呢，恰恰是和漏桶算法相反的一個(gè)算法，不過還是推薦你使用這個(gè)。這個(gè)算法的原理我不講，我覺得聰明的你看了偽代碼就明白了。
涉及變量

1.接口（key）
2.時(shí)間單位（expire）
3.允許訪問多少次（limit）
4.遞增間隔時(shí)間（interval）
5.遞增步長（step）
6.當(dāng)前可訪問次數(shù)（value）
7.key的訪問時(shí)間（lastUpdateTime）
8.當(dāng)前時(shí)間（nowTime）（參照漏桶算法需要注意的點(diǎn)）

if(存在key){
   value++；
   if(value>=limit){
           不能訪問
       }
   }else{
       添加key，設(shè)置value為limit
   }

while(過去interval時(shí)間){
   所有key的value+step
   }

參考計(jì)算器算法條件二實(shí)現(xiàn)。

參考漏桶算法升級(jí)實(shí)現(xiàn)。

代碼實(shí)現(xiàn)請(qǐng)參考我的限流組件 https://github.com/2388386839...

本文出自http://zhixiang.org.cn,轉(zhuǎn)載請(qǐng)保留。