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

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

分析之前

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{
    添加key，value為1
       設定key過期時間為expire
   }           

條件二

既然條件一已經實作了，那條件二會複雜麼 ？

相比于條件一來說就是同一個key對應了多個使用者。那麼我們隻需要把key加上使用者的資訊就可以了。比如說 key_使用者1、key_使用者2。

漏桶算法

漏桶算法的意思呢就是一個接口在一個時間機關中允許被通路次數是動态變化的（假如一分鐘允許通路60次，那麼從開始計時時不管有沒有被通路第59秒隻允許通路59次，30秒隻允許30次）。為什麼這樣呢，因為有另外一個線程在進行遞減操作

4. 遞減間隔時間（interval）
5. 遞減步長（step）
6. 剩餘可通路次數（value）
7. key的通路時間（lastUpdateTime）
8. 目前時間（nowTime）（注意nowTime的取值應為應用取得的時間而不是redis或者nginx取得的時間）

線程一：

if(存在key){
   value--；
   if(value<=0){
      不能通路
    }
   }else{
    添加key，設定value為limit
   }           

線程二：

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

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

算法更新

可以看到實作漏桶算法的話需要每隔interval時間都要另外一條線程去周遊所key的value去做遞減操作，那麼有沒有什麼辦法可以省略這一步呢。答案是肯定有。

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

令牌桶算法

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

4. 遞增間隔時間（interval）
5. 遞增步長（step）
6. 目前可通路次數（value）
8. 目前時間（nowTime）（參照漏桶算法需要注意的點）

if(存在key){
   value++；
   if(value>=limit){
      不能通路
    }
   }else{
    添加key，設定value為limit
   }           

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

參考電腦算法條件二實作。

參考漏桶算法更新實作。

代碼

代碼實作請參考我的限流架構

https://github.com/2388386839/syj-ratelimit