常見限流演算法

来源:https://www.cnblogs.com/jtea/archive/2023/01/17/17057214.html
-Advertisement-
Play Games

簡介 限流顧名思義是對流量大小進行限制,防止請求數量超過系統的負載能力,導致系統崩潰,起到保護作用。 現實生活中限流也隨處可見,節假日出門旅行的人數會劇增,對於旅游景點來說往往會不堪重負,如果不進行人數控制,對整個景點的壓力會非常大,游客的體驗也會非常差,還容易出現安全事故等危險。 同樣的在一線城市 ...


簡介

限流顧名思義是對流量大小進行限制,防止請求數量超過系統的負載能力,導致系統崩潰,起到保護作用。
現實生活中限流也隨處可見,節假日出門旅行的人數會劇增,對於旅游景點來說往往會不堪重負,如果不進行人數控制,對整個景點的壓力會非常大,游客的體驗也會非常差,還容易出現安全事故等危險。
同樣的在一線城市地鐵限流也非常常見,早高峰為了控制乘車人數和有序進站,地鐵往往會在地鐵口進行攔截,一定時間內才放行一部分人進站乘車。

具體到程式,限流可以有以下幾種場景

  • 限制某個介面每秒最多訪問多少次
  • 限制某個ip每秒最多訪問多少次
  • 限制某個用戶或某個來源每秒最多訪問多少次
  • 限制某些用戶下載速度每秒最多多少kb
  • 禁止某些用戶或ip的訪問

限流起到了保護作用,那麼如何限呢?如果限制得太嚴,保護是保護到了,但是系統的處理能力下降了,體驗會很差;如果限制得太松,就會被一些突增流量衝擊到,或者被黑客利用進行安全攻擊。如何限流需要根據系統的負載來評估,系統的負載和處理能力是動態的,例如平時的qps是1000,雙11一般會進行擴容,也就是加服務節點,qps可能就是5000,這個時候系統處理能力變強的,限流策略也應該相應的調整。還有一種是出於安全的限流,例如同一個客戶端ip 1s內對系統發出上萬次請求,這種可以確定就是安全攻擊,很可能是有人惡意破壞,或者是一些爬蟲,這種可以限制請求數,超出的就直接拒絕。
如何限流是限流演算法要實現的,常見的限流演算法有“兩桶兩窗”,固定視窗、滑動視窗、漏桶與令牌桶,接下來介紹這四種演算法及應用。

固定視窗

固定視窗的思想和實現非常簡單,就是統計每個固定每個時間視窗的請求數,超過則拒絕。

如圖我們定義了視窗大小為1s,最大請求數100,視窗內超過100的請求數將被拒絕。實現上也非常簡單,利用redis的incr自增計數,當前時間秒作為緩存key,每次自增後判斷是否超過指定大小即可。
固定視窗的問題是容易出現“突刺現象”,例如在1s內,100個請求都是在前100ms過來的,那麼後面的900ms的請求都會被拒絕,而系統此時是空閑的。另外還有“臨界問題”,如果100個請求是在後100ms過來的,而下一個1s的100個請求在前100ms過來,此時系統在這200ms內就需要處理200個請求,跟我們想要的不符合。到這裡我們很容易想到,1s這個範圍太大了,縮小一些就更好了,這種把固定視窗拆成更多個小視窗的做法就是滑動視窗演算法了。

滑動視窗

滑動視窗的思想是將固定視窗拆成更多個小視窗,隨著時間的推移,視窗不斷的滑動,統計也在不斷的變化。視窗拆分的越多,滑動就會越平滑,統計就會越精確,所消耗的資源就會越多。滑動視窗如果只拆為1個視窗,就退化為固定視窗。
滑動視窗演算法可以解決上面固定視窗的問題,像hystrix和sentinel中都使用該演算法進行數據統計,用於限流熔斷等策略處理。如hystrix中圖所示,在一個視窗內拆分了10個桶(bucket),隨著時間的推移,會創建新的桶也會丟棄過期的桶,當然視窗的大小和拆分桶的數量都是可配置的。

漏桶

漏桶演算法的思想是將請求先放到一個桶中,然後像滴水一樣不斷的從中取出請求執行,桶滿則溢,後面的請求會被拒絕。

漏桶演算法的特點是流入速度不確定,但是流出速度是確定的,漏桶可以很平滑,均衡的處理請求,但是無法應對短暫的突發流量。

令牌桶

令牌桶演算法的思想是不斷的生成令牌放到一個桶中,請求到來時到桶中申請令牌,申請得到就執行,申請不到就拒絕。如果桶中的令牌滿了,新生成的令牌也會丟棄。

與漏桶不同的是,令牌桶是流入速度確定(生成令牌的速度),流出速度不確定,所以它不想漏桶一樣可以均衡的處理請求,但是由於有令牌桶這個緩衝,一旦有突增的流量,令牌桶里已有的令牌可以短暫的應對突發流量,由於流出速度是不限制的,此時桶中已有的令牌都可以被申請到,請求一下子就會到我們的服務,給系統帶來一定的壓力,所以桶的大小需要合適,不宜過大。舉個慄子:令牌桶的大小是1000,每秒放100個令牌,經過一段時間後,請求有空閑時,桶里的令牌就會積壓,最終保存了滿1000個令牌,由於某刻流量突增,有1000個請求到來,此時能申請到1000個令牌,所有請求都會放行,最終達到我們的系統,如果令牌桶過大,系統可能會承受不了這波請求。

應用

guava RateLimiter

guava限流實現的是桶演算法,通過RateLimiter.create創建,可以創建兩種類型的限流器,SmoothBursty和SmoothWarmingUp,前者定時生成令牌,後者有一個預熱的過程。
我們如下示例代碼,每秒會創建2個令牌,並且初始化的時候就是2。定時器每200ms會申請一次令牌,每秒申請5次,只有2次成功,所有運行程式每秒有3次success和2次fail。

        RateLimiter rateLimiter = RateLimiter.create(2);
		new Timer().schedule(new TimerTask() {
			@Override
			public void run() {
				if (rateLimiter.tryAcquire()) {
					System.out.println("success");
				} else {
					System.out.println("fail");
				}
			}
		}, 0, 200);

既然是桶,那麼桶的大小是多少呢?SmoothBursty里最大令牌數由maxPermits欄位表示,該欄位等於maxBurstSeconds * permitsPerSecond,permitsPerSecond是每秒要生成的令牌數,maxBurstSeconds預設是1。
另外還可以創建SmoothWarmingUp帶有預熱功能的限流器,預熱的作用是通過一個過程才達到permitsPerSecond,相當於讓系統有個熱身的時間。

		RateLimiter rateLimiter = RateLimiter.create(5, 10, TimeUnit.MILLISECONDS);
		new Timer().schedule(new TimerTask() {
			@Override
			public void run() {
				log.info("" + rateLimiter.acquire());			
			}
		}, 0, 200);

rateLimiter.acquire()返回的是獲取打令牌的時間,運行程式可以看到開始並不是每秒都能產生5個令牌,也就是不是能立刻獲取到令牌,獲取令牌需要的時間會越來越小,直到預熱期過後就能立馬獲取到令牌了。
guava的限流只能提供單機版的實現,對於集群就無能為力了,並且它通常作為一個工具存在,使用還需要自己封裝,集成到服務,並不能開箱即用。

bucket4j

bucket4j是一個java實現,基於令牌桶演算法的限流組件。它支持分散式限流,支持多種存儲,可以方便與各種框架和監控集成。github上start 1.2K,但是issues數量少,國內估計使用的人也不多,並且官方的實現存儲不支持最常用的redis,它專註於限流,如果是自研或者二次開發,是一個很好的參考。

Resilience4j

之前我們介紹過它的熔斷功能,Resilience4j也提供了限流的實現,可以參考這裡。相比guava,Resilience4j是框架級別的,可以很方便的使用。但Resilience4j也是單機版的實現,無法支持集群功能。
Resilience4j限流實現的是令牌桶,如下配置,每1s會生成10個令牌。

resilience4j.ratelimiter:
    instances:
        backendA:
            limitForPeriod: 10
            limitRefreshPeriod: 1s
            timeoutDuration: 0
            registerHealthIndicator: true
            eventConsumerBufferSize: 100

sentinel

流量控制是sentinel最重要的一個功能,sentinel屬於後起之秀,文檔齊全,支持的場景更加豐富。sentinel支持集群限流,也可以像guava一樣預熱,還可以基於調用鏈路進行限流。
sentinel還提供了控制台功能,支持多種數據源的持久化,使用spring cloud的話可以通過spring cloud alibaba引入sentinel。
開源版的sentinel有一些限制,並且使用起來並不是那麼方便,例如Resilience4j可以配置一個default針對所有的請求生效,但sentinel需要單個單個url去配置,顯得非常麻煩,包括熔斷feign介面的配置也是,這個給spring cloud alibaba提了feature,也許在下一個版本就會提供支持。

nginx

上面講到的都是應用級別的限流,nginx通常作為網路請求的入口,從運維的角度來說,在這裡做限流再合適不過,nginx本身也提供了限流的支持。
nginx比較適合對外的限流,但是我們內部不同系統間的調用一遍不經過nginx,會直接訪問到對方的網關,所以兩者並不矛盾。
nginx限流通過limit_req和limit_conn兩個模塊支持,分別對應請求限制和鏈接限制(一個鏈接可以有多個請求)。

http {  
    limit_req_zone zone=name:10m rate=100r/s;  
    server {  
        location /app/ {
            limit_req zone=name burst=500 nodelay;
        }
}

如上,定義了一個name zone,訪問速率最高是100個每秒,/app路徑應用了這個規則。busrt表示爆發的意思,是一個緩衝隊列,用於存儲突增的請求,這些請求會被緩存不會拒絕,如果超過了burst,nodelay表示不等待直接拒絕。
前面我們說到有些惡意攻擊可能每秒發送上萬個請求,導致服務崩潰,如果多個應用系統共用一個nginx,那麼可以統一在nginx配置處理,不需要每個系統自己去實現。

limit_conn_zone $binary_remote_addr zone=name:10m;

server {    
    limit_conn name 50;    
}

如上,定義了一個name zone,$binary_remote_addr表示遠端地址,也就是ip,10m表示存儲空間,10m大概可以存儲16w的ip地址,我們在server節點應用這個規則,50表示最多50個,超過就會拒絕。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1 簡介 DB2是IBM的一款優秀的關係型資料庫,簡單學習一下。 2 Docker安裝DB2 為了快速啟動,直接使用Docker來安裝DB2。先下載鏡像如下: docker pull ibmcom/db2:11.5.0.0 啟動資料庫如下: docker run -itd \ --name mydb ...
  • Spring管理Bean-IOC-02 2.基於XML配置bean 2.7通過util空間名稱創建list BookStore.java: package com.li.bean; import java.util.List; /** * @author 李 * @version 1.0 */ pu ...
  • Spring6 Spring項目的創建 打開IDEA,新建一個maven項目 在maven項目中引入spring的倉庫和依賴 <repositories> <repository> <id>repository.spring.milestone</id> <name>Spring Milestone ...
  • 2023-01-17 一、Spring中的註解 1、使用註解的原因 (1)使用註解將對象裝配到IOC容器中 (2)使用註解管理對象之間依賴關係(自動裝配) 2、Spring中裝配對象的註解 (1)@Component 標識一個受Spring IOC容器管理的普通組件 (2)@Repository 標 ...
  • 好久沒有更新文章了,高齡開發沒什麼技術,去了外包公司後沒怎麼更新文章了。今天分享下統一處理starter,相信開發web系統的時候都是會涉及到前後端的交互,而後端返回數據的時候一般都會統一封裝一個返回對象和統一處理異常,一般情況下都是在controller的每個方法中調用封裝的對象,把相應的數據塞到 ...
  • 2023-01-17 一、Spring管理druid步驟 (1)導入jar包 <!-- https://mvnrepository.com/artifact/com.alibaba/druid --> <dependency> <groupId>com.alibaba</groupId> <arti ...
  • 抽獎程式 ''' 抽獎程式 使用時可以修改嘉賓名單,然後單機‘開始’和‘停止’按鈕 來控制界面上名單的滾動實現抽獎功能,涉及的模塊主要 有多線程 ''' import itertools import random import threading import time import tkinte ...
  • 摘要:本文主要講解圖像局部直方圖均衡化和自動色彩均衡化處理。這些演算法可以廣泛應用於圖像增強、圖像去噪、圖像去霧等領域。 本文分享自華為雲社區《[Python從零到壹] 五十四.圖像增強及運算篇之局部直方圖均衡化和自動色彩均衡化處理》,作者: eastmount。 一.局部直方圖均衡化 前文通過調用O ...
一周排行
    -Advertisement-
    Play Games
  • 前言 當別人做大數據用Java、Python的時候,我使用.NET做大數據、數據挖掘,這確實是值得一說的事。 寫的並不全面,但都是實際工作中的內容。 .NET在大數據項目中,可以做什麼? 寫腳本(使用控制台程式+頂級語句) 寫工具(使用Winform) 寫介面、寫服務 使用C#寫代碼的優點是什麼? ...
  • 前言 本文寫給想學C#的朋友,目的是以儘快的速度入門 C#好學嗎? 對於這個問題,我以前的回答是:好學!但仔細想想,不是這麼回事,對於新手來說,C#沒有那麼好學。 反而學Java還要容易一些,學Java Web就行了,就是SpringBoot那一套。 但是C#方向比較多,你是學控制台程式、WebAP ...
  • 某一日晚上上線,測試同學在回歸項目黃金流程時,有一個工單項目介面報JSF序列化錯誤,馬上升級對應的client包版本,編譯部署後錯誤消失。 線上問題是解決了,但是作為程式員要瞭解問題發生的原因和本質。但這都是為什麼呢? ...
  • 本文介紹基於Python語言中TensorFlow的Keras介面,實現深度神經網路回歸的方法。 1 寫在前面 前期一篇文章Python TensorFlow深度學習回歸代碼:DNNRegressor詳細介紹了基於TensorFlow tf.estimator介面的深度學習網路;而在TensorFl ...
  • 前段時間因業務需要完成了一個工作流組件的編碼工作。藉著這個機會跟大家分享一下整個創作過程,希望大家喜歡,組件暫且命名為"easyFlowable"。 接下來的文章我將從什麼是工作流、為什麼要自研這個工作流組件、架構設計三個維度跟大家來做個整體介紹。 ...
  • 1 簡介 我們之前使用了dapr的本地托管模式,但在生產中我們一般使用Kubernetes托管,本文介紹如何在GKE(GCP Kubernetes)安裝dapr。 相關文章: dapr本地托管的服務調用體驗與Java SDK的Spring Boot整合 dapr入門與本地托管模式嘗試 2 安裝GKE ...
  • 摘要:在jvm中有很多的參數可以進行設置,這樣可以讓jvm在各種環境中都能夠高效的運行。絕大部分的參數保持預設即可。 本文分享自華為雲社區《為什麼需要對jvm進行優化,jvm運行參數之標準參數》,作者:共飲一杯無。 我們為什麼要對jvm做優化? 在本地開發環境中我們很少會遇到需要對jvm進行優化的需 ...
  • 背景 我們的業務共使用11台(阿裡雲)伺服器,使用SpringcloudAlibaba構建微服務集群,共計60個微服務,全部註冊在同一個Nacos集群 流量轉發路徑: nginx->spring-gateway->業務微服務 使用的版本如下: spring-boot.version:2.2.5.RE ...
  • 基於php+webuploader的大文件分片上傳,帶進度條,支持斷點續傳(刷新、關閉頁面、重新上傳、網路中斷等情況)。文件上傳前先檢測該文件是否已上傳,如果已上傳提示“文件已存在”,如果未上傳則直接上傳。視頻上傳時會根據設定的參數(分片大小、分片數量)進行上傳,上傳過程中會在目標文件夾中生成一個臨 ...
  • 基於php大文件分片上傳至七牛雲,使用的是七牛雲js-sdk V2版本,引入js文件,配置簡單,可以暫停,暫停後支持斷點續傳(刷新、關閉頁面、重新上傳、網路中斷等情況),可以配置分片大小和分片數量,官方文檔https://developer.qiniu.com/kodo/6889/javascrip ...