常見限流演算法

来源: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
  • 背景 在瀏覽器中訪問本地靜態資源html網頁時,可能會遇到跨域問題如圖。 是因為瀏覽器預設啟用了同源策略,即只允許載入與當前網頁具有相同源(協議、功能變數名稱和埠)的內容。 WebView2預設情況下啟用了瀏覽器的同源策略,即只允許載入與主機相同源的內容。所以如果我們把靜態資源發佈到iis或者通過node ...
  • 最近看幾個老項目的SQL條件中使用了1=1,想想自己也曾經這樣寫過,略有感觸,特別拿出來說道說道。編寫SQL語句就像炒菜,每一種調料的使用都會影響菜品的最終味道,每一個SQL條件的加入也會影響查詢的執行效率。那麼 1=1 存在什麼樣的問題呢?為什麼又會使用呢? ...
  • 好久不見,我又回來了。 給大家分享一個我最近使用c#代碼操作ftp伺服器的代碼示例: 1 public abstract class FtpOperation 2 { 3 /// <summary> 4 /// FTP伺服器地址 5 /// </summary> 6 private string f ...
  • 一:背景 1. 講故事 過年喝了不少酒,腦子不靈光了,停了將近一個月沒寫博客,今天就當新年開工寫一篇吧。 去年年初有位朋友找到我,說他們的系統會偶發性崩潰,在網上也發了不少帖子求助,沒找到自己滿意的答案,讓我看看有沒有什麼線索,看樣子這是一個牛皮蘚的問題,既然對方有了dump,那就分析起來吧。 二: ...
  • 自己製作的一個基於Entity Framework Core 的資料庫操作攔截器,可以列印資料庫執行sql,方便開發調試,代碼如下: /// <summary> /// EF Core 的資料庫操作攔截器,用於在資料庫操作過程中進行日誌記錄和監視。 /// </summary> /// <remar ...
  • 本文分享自華為雲社區《Go併發範式 流水線和優雅退出 Pipeline 與 Cancellation》,作者:張儉。 介紹 Go 的併發原語可以輕鬆構建流數據管道,從而高效利用 I/O 和多個 CPU。 本文展示了此類pipelines的示例,強調了操作失敗時出現的細微之處,並介紹了乾凈地處理失敗的 ...
  • 在上篇文章中,我們介紹到在多線程環境下,如果編程不當,可能會出現程式運行結果混亂的問題。出現這個原因主要是,JMM 中主記憶體和線程工作記憶體的數據不一致,以及多個線程執行時無序,共同導致的結果。 ...
  • 1、下載安裝包首先、進入官網下載安裝包網址:https://www.python.org/downloads/windows/下載步驟:進入下載地址,根據自己的電腦系統選擇相應的python版本 選擇適配64位操作系統的版本(查看自己的電腦操作系統版本), 點擊下載安裝包 也可以下載我百度雲分享的安 ...
  • 簡介 git-commit-id-maven-plugin 是一個maven 插件,用來在打包的時候將git-commit 信息打進jar中。 這樣做的好處是可以將發佈的某版本和對應的代碼關聯起來,方便查閱和線上項目的維護。至於它的作用,用官方說法,這個功能對於大型分散式項目來說是無價的。 功能 你 ...
  • 序言 在數字時代,圖像生成技術正日益成為人工智慧領域的熱點。 本討論將重點聚焦於兩個備受矚目的模型:DALL-E和其他主流AI繪圖方法。 我們將探討它們的優勢、局限性以及未來的發展方向。通過比較分析,我們期望能夠更全面地瞭解這些技術,為未來的研究和應用提供啟示。 Q: 介紹一下 dall-e Ope ...