大型網站限流算法的實現和改造-創(chuàng)新互聯

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

創(chuàng)新互聯是一家專注于網站建設、成都做網站與策劃設計,徽縣網站建設哪家好?創(chuàng)新互聯做網站,專注于網站建設十載,網設計領域的專業(yè)建站公司;建站業(yè)務涵蓋:徽縣等地區(qū)。徽縣做網站價格咨詢:18982081108

分析之前

  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。


1




2




3




4




5




6




7




8




9






if

(存在

key

){




   value++;




   

if

(value>=

limit

){




   		不能訪問




   	}




   }

else

{




   	添加

key

，value為

1





       設置

key

過期時間為expire




   }
條件二

既然條件一已經實現了，那條件二會復雜么 ？

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

漏桶算法

核心思想

漏桶算法的意思呢就是一個接口在一個時間單位中允許被訪問次數是動態(tài)變化的（假如一分鐘允許訪問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取得的時間）

條件一

線程一：


1




2




3




4




5




6




7




8






if

(存在key){




   

value

--；




   

if

(

value

<=


){




   		不能訪問




   	}




   }

else

{




   	添加key，設置

value

為limit




   }

線程二：


1




2




3






while

(過去interval時間){




   所有

key

的value-

step





   }
條件二

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

算法升級

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


1




2




3




4




5




6




7




8




9




10




11




12




13






if

(存在key){




   value--；




   

if

（（nowTime-lastUpdateTime）>interval）{




   	

value

=value-（nowTime-lastUpdateTime）/interval*step;




       

lastUpdateTime

=nowTime;




   }




   

if

(value<=0){




   		不能訪問




   	}




   }

else

{




   	添加key，設置value為limit；




       

lastUpdateTime

=nowTime；




   }

令牌桶算法

核心思想

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

涉及變量

  1. 接口（key）

  2. 時間單位（expire）

  3. 允許訪問多少次（limit）

  4. 遞增間隔時間（interval）

  5. 遞增步長（step）

  6. 當前可訪問次數（value）

  7. key的訪問時間（lastUpdateTime）

  8. 當前時間（nowTime）（參照漏桶算法需要注意的點）

條件一

線程一：


1




2




3




4




5




6




7




8






if

(存在

key

){




   value++；




   

if

(value>=

limit

){




   		不能訪問




   	}




   }

else

{




   	添加

key

，設置value為

limit





   }

線程二：


1




2




3






while

(過去interval時間){




   所有

key

的value+

step





   }
條件二

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

算法升級

參考漏桶算法升級實現。

代碼

代碼實現請參考我的限流框架 /tupian/20230522/syj-ratelimit

本文出自 http://zhixiang.org.cn ,轉載請保留。

名稱欄目：大型網站限流算法的實現和改造-創(chuàng)新互聯
網站網址：http://muchs.cn/article18/dhgcgp.html

成都網站建設公司_創(chuàng)新互聯，為您提供靜態(tài)網站、動態(tài)網站、小程序開發(fā)、手機網站建設、面包屑導航、網站設計

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯

搜索引擎優(yōu)化