滑動窗口演算法

Ⅰ 滑動窗口技術工作原理

滑動窗口針對圖像的演算法的一般描述是:在規模為 W×H 的圖像中，按一定規律移動 w×h 的窗口(W>>w， H>>h)，對窗口內像素點的像素值進行一系列運算，運算結束後窗口向右或向下移動一步，直到完成對整幅圖像的處理。

如果問的是滑動窗口協議的話，網路隨便搜索下，N多回答。

Ⅱ 演算法總結之滑動窗口

滑動窗口類問題是面試當中的高頻題，問題本身其實並不復雜，但是實現起來細節思考非常的多，想著想著可能因為變數變化，指針移動等等問題，導致程序反復刪來改去，有思路，但是程序寫不出是這類問題最大的障礙。
本文會將 LeetCode 裡面的大部分滑動窗口問題分析、總結、分類，並提供一個可以參考的模版

滑動窗口這類問題一般需要用到 雙指針 來進行求解，另外一類比較特殊則是需要用到特定的數據結構，如 Map，隊列等。

題目問法大致有這幾種

1 . 給兩個字元串，一長一短，問其中短的是否在長的中滿足一定的條件存在

2 . 給一個字元串或者數組，問這個字元串的子串或者子數組是否滿足一定的條件

除此之外，還有一些其他的問法，但是不變的是，這類題目脫離不開主串（主數組）和子串（子數組）的關系，要求的時間復雜度往往是 O ( N ) O(N) O(N) ，空間復雜度往往是 O ( 1 ) O(1) O(1) 的。

根據前面的描述，滑動窗口就是這類題目的重點，換句話說， 窗口的移動 就是重點！我們要控制前後指針的移動來控制窗口，這樣的移動是有條件的，也就是要想清楚在什麼情況下移動，在什麼情況下保持不變。
思路是保證右指針每次往前移動一格，每次移動都會有新的一個元素進入窗口，這時條件可能就會發生改變，然後根據當前條件來決定左指針是否移動，以及移動多少格。

無重復字元的最長子串

給定一個字元串，請你找出其中不含有重復字元的最長子串的長度。

示例

解題思路

輸入只有一個字元串，要求子串裡面不能夠有重復的元素，這里 count 都不需要定義，直接判斷哈希散列裡面的元素是不是在窗口內即可，是的話得移動左指針去重。
建立一個 128 位大小的整型數組，用來建立字元和其出現位置之間的映射。維護一個滑動窗口，窗口內的都是沒有重復的字元，去盡可能的擴大窗口的大小，窗口不停的向右滑動。

替換後的最長重復字元

給你一個僅由大寫英文字母組成的字元串，你可以將任意位置上的字元替換成另外的字元，總共可最多替換 k 次。在執行上述操作後，找到包含重復字母的最長子串的長度。

示例

解題思路

最簡單的方法就是把哈希散列遍歷一邊找到最大的字元數量，但是仔細想想如果我們每次新進元素都更新這個最大數量，且只更新一次，我們保存的是當前遍歷過的全局的最大值，它肯定是比實際的最大值大的，我們左指針移動的條件是 right - left + 1 - count > k，保存的結果是 result = Math.max(result, right - left + 1)； 這里 count 比實際偏大的話，雖然導致左指針不能移動，但是不會記錄當前的結果，所以最後的答案並不會受影響。

長度為 K 的無重復字元子串

給你一個字元串 S，找出所有長度為 K 且不含重復字元的子串，請你返回全部滿足要求的子串的數目。

示例

解題思路

根據題意我們發現相當於窗口大小固定為K，同時在窗口內必須沒有重復的字元。我們用左右指針可以計算出當前窗口的大小right - left + 1，同時再利用一個count對字元種類進行計數（也可以直接用一個boolean值即可），那麼很容易可以得出當right - left + 1 > K 或者 count > 0時需要移動左指針了。剩下的部分就是愉快地套用模板啦。

至多包含兩個不同字元的最長子串

給定一個字元串 s ，找出至多包含兩個不同字元的最長子串 t 。

示例

解題思路

類似於上一題，不過我們用count來記錄當前窗口內字元的種類數量，當出現新字元以及滑動左指針時，做相應的判斷來改變count，窗口大小始終保持在滿足條件至多兩個不同字元的情況下。

至多包含 K 個不同字元的最長子串

給定一個字元串 s ，找出 至多 包含 k 個不同字元的最長子串 T。

示例

解題思路

和上一題完全一樣的思路，只需要把判斷窗口條件的地方改成 count > k ，又一題困難被我們直接秒殺。

下面來看看兩個字元串的情況

最小覆蓋子串

給你一個字元串 S、一個字元串 T，請在字元串 S 裡面找出：包含 T 所有字母的最小子串。

示例

解題思路

同樣是兩個字元串之間的關系問題，因為題目求的最小子串，也就是窗口的最小長度，說明這里的窗口大小是可變的，這里移動左指針的條件變成，只要左指針指向不需要的字元，就進行移動。

字元串的排列

給定兩個字元串 s1 和 s2，寫一個函數來判斷 s2 是否包含 s1 的排列。

示例

解題思路

首先窗口是固定的，窗口長度就是s1的長度，也就是說，右指針移動到某個位置後，左指針必須跟著一同移動，且每次移動都是一格，count 用來記錄窗口內滿足條件的元素，直到 count 和窗口長度相等即可。

找到字元串中所有字母異位詞

給定一個字元串 s 和一個非空字元串 p，找到 s 中所有是 p 的字母異位詞的子串，返回這些子串的起始索引。字元串只包含小寫英文字母，並且字元串 s 和 p 的長度都不超過 20100。

示例

解題思路

和上一題完全一致的思路，窗口固定為p串的長度。

最後來看看數組類型的題吧
最大連續1的個數 III

給定一個由若干 0 和 1 組成的數組 A，我們最多可以將 K 個值從 0 變成 1 。返回僅包含 1 的最長（連續）子數組的長度。

示例

解題思路

這題有點像上面的 替換後的最長重復字元，只不過把字元串換成了數組，由於只有兩種數字 0 和 1，並且只求連續 1 的長度，我們可以連 hash 映射都不需要了，直接計算遍歷到的 0 的個數即可。

K 個不同整數的子數組

給定一個正整數數組 A，如果 A 的某個子數組中不同整數的個數恰好為 K，則稱 A 的這個連續、不一定獨立的子數組為好子數組。

示例

解題思路

這題比較 tricky 的一個地方在於，這里不是求最小值最大值，而是要你計數。
但是如果每次僅僅加 1 的話又不太對，例如 A = [1,2,1,2,3], K = 2 這個例子，假如右指針移到 index 為 3 的位置，如果按之前的思路左指針根據 count 來移動，當前窗口是 [1,2,1,2]，但是怎麼把 [2,1] 給考慮進去呢？
可以從數組和子數組的關系來思考！
假如 [1,2,1,2] 是符合條件的數組，如果要計數的話，[1,2,1,2] 要求的結果是否和 [1,2,1] 的結果存在聯系？這兩個數組的區別在於多了一個新進來的元素，之前子數組計數沒考慮到這個元素，假如把這個元素放到之前符合條件的子數組中組成的新數組也是符合條件的，我們看看這個例子中所有滿足條件的窗口以及對應的滿足條件的子數組情況：

你可以看到對於一段連續的數組，新的元素進來，窗口增加 1，每次的增量都會在前一次增量的基礎上加 1。當新的元素進來打破當前條件會使這個增量從新回到 1，這樣我們左指針移動條件就是只要是移動不會改變條件，就移動，不然就停止。

至此，本文用同一個框架解決了多道滑動窗口的題目，這類問題思維復雜度並不高，但是出錯點往往在細節。記憶常用的解題模版還是很有必要的，特別是對於這種變數名多，容易混淆的題型。有了這個框架，思考的點就轉化為 「什麼條件下移動左指針」，無關信息少了，思考加實現自然不是問題。

Ⅲ [OpenJudge 3866] 滑動窗口〔單調隊列〕

這是一篇題解筆記，這貌似被認為是一個經典題。題目鏈接： OpenJudge - 7:滑動窗口

總時間限制: 12000ms內存限制: 65536kB
描述
給定一個長度為n（n<=10^6）的數組。有一個大小為k的滑動窗口銷遲從數組的最左端移動到胡斗態最右端。你可以看到窗口中的k個數字。窗口每次向右滑動一個數字的距離。
下面是一個例子：
數組是 [1 3 -1 -3 5 3 6 7]， k = 3。

你的任務是得到滑動窗口在每個位置時的最大值和最小值。

輸入
輸入包括兩行。
第一行包括n和k，分別表示數組的長度和窗口的大小。
第二行包括n個數字。
輸出
輸出包括兩行。
第一行包括窗口從左至右移動的每個位置的最小值。
第二行包括窗口從左至右移動的每個位置的最大值。
樣例輸入

樣例輸出

開始接觸STL後，發現 set 和 map 真是強大好用，對這個題直接暴力用 multiset 模擬滑動窗口：

由於 set / multiset 底層是用紅黑樹實現，雖然是暴力，在OpenJudge上仍然能900ms通過。但是提交到 洛谷 上就有一個case超過1s報TLE，那就來研究一下此題「正確」的數據結構吧！

暴力做法使用的 set ，每次插入新的元素必須同時刪除一個舊元素，舊元素在集合中的位置又必須通過再次查找得知，這當中查找、刪除兩步都在重復使用之前的時間戳確定的窗內其它元素的大小信息。我們不希望重復使用這些信息，畢竟整個過程中，我們關注的只是窗口內的最值。
應該採用更加簡明的數據結構來存儲這些數值，且它應該保存以下兩個方面的信息：(1) 元素在數集內的 出現順序 ，這方面較適合這里的情況的就是 隊列 ；(2) 數集內的一種 層次大小結構 ，或者說單調結構，能夠借其確保每次最大/最小值的詢問都可以快速返回。這兩條信息對應窗口的兩個行為，一是元素的 進出 ，二是 最值 的詢問。
有了這些前提，就可以動手設計這道題使用的數據結構（單調隊列）了，其精巧地滿足了我們的需求。在這個問題里，使用的是一個雙端隊列。

在窗口建立（從讀入第一個數到讀入第 size （窗口的大小）個數）和滑動的過程中，我們維護一個隊列 ，它的行為和正常的隊列一致，但是會自動淘汰那些不可能作為最小/大值詢問結果的元素。以最小值為例，如果一個數 出現在數 的後邊，但是比 和 都要小，那麼在 插入以後，這兩個數 就永遠 沒有機會 作為窗口的最小值輸出。
要實現這一點，每當新元素要進入 ，我們都比較它與 前一個進入的元素（當前的 back ）的大小。如果新元素更小，則當前的 back 被淘汰，將它彈出，讓下一個 back 與新元素比較；如果新元素更大或一路到達了 的頭部，由於此後這元素可能成為最小值，將它先存儲在隊列的末尾。
我們只需再實現窗口左側元素的彈出功能。好的情況下，讓 彈出現存的第一個元素（ front ）即可；然而窗口左側元素可能已經被淘汰， front 未必是它。不要緊，我們換成存儲元素的下標，這樣就能監測 的 front 是否該彈出了。
在整個演算法中，我們做的比較幾乎都是剛好必要的。每進入一個新元素，都至多需要 size 次比較，然而真正要這么多次比較的頻率會很低（如果某次進入新元素需要 size 次比較，則說明窗口完全遞增且新元素最小，而加入下一個元素要麼會破壞這種遞增，褲源要麼會花費很少的比較次數，即不會總要比較 size 次），因此這個演算法的性能應當是很好的。（2022/7/6 Edit：實際上直接可以看出均攤的時間復雜度為 。）

實際情況也是如此。採用單調隊列後（用 std::list 實現），在OpenJudge上300ms通過：

Ⅳ 滑動窗口演算法

在滑動窗口類型的問題中都會有兩個指針，一個用於 延伸 現有窗口的 right 指針，和一個用於 收縮 窗口的 left 指針。在任意時刻，哪悄胡只有一個指針運動，而另一個保持靜止。滑動窗口演算法的時間復雜度為 ，因為 right 和 left 兩個指針都只移動了 n 次。
該演算法的大致邏輯如下：

接下來還是看幾道典型的 leetcode 題目。

題目描述：

題目分析：
首先想到暴力解法，循環每個子區間，找到滿足和大於等於 s 的子區間，更新最小長度。

此時時間復雜度 ，題目提示復雜度應為 ，那需要在常數次遍歷中找到答案。在暴力解法中，我們先固定 i ，然後增加 j ，一次結束後，我們將 i 加 1 ，然後再循環 j ，重復的計算主要在這里。那是不是可以保持 j 在上一次循環結束的地方不動呢？我們知道上一次循環結束後 i 和 j 之間的子數組的和大於等於 s ，如果此時 j 不動，然後 i 加 1 ，那我們求得的和就需要減掉 nums[i] ，如果此時的子數組的和滿足條件，那最小長度比開始更小了，那我們需要更新最小長度；如果此時子數組的和不滿足條件，那我們繼續增加 j ，來擴大子數組的長度。這也就是我們的滑動窗口思路。

題目描述：

聯系滑動窗口演算法，首先我們增大窗口，當條件滿足時，縮小窗口。考慮到 t 中可能有重復字元，所以我們的判斷條件還需要考慮每個字元的數量一致。

題目描述：

題目分析：
這道題需要關注的窗口為固定長度。我們先不考慮這個點，看看普通的滑動窗口解法：

這個李攔解法中，我們是等到子字元串滿足條件了再來縮減窗口。由於題目所述為固定的窗口大小，那我們縮減窗口的條件可以改成如下形式：

題目描述：

和上一題類似，我們還是套運咐用滑動窗口模板：

題目描述：

題目分析：
題目的條件是無重復字元，那我們滑動窗口的條件便是：沒有重復字元時，我們增大窗口，出現重復字元時我們縮小滑動窗口。需要注意的是我們更新結果再增加窗口的步驟中。

Ⅳ 四種限流演算法原理

限流這里總結了四個演算法分別是 計數器固定窗口演算法、計數器滑動窗口演算法、漏斗演算法、令牌桶演算法

計數器固定窗口演算法是最基礎也是最簡單的一種限流演算法。原理就是對一段固定時間窗口內的請求進行計數，如果請求數超過了閾值，則舍棄該請求；

如果沒有達到設定的閾值，則接受該請求，且計數加1。當時間窗口結束時，重置計數器為0。

優點：實現簡單容易理解

缺點： 流量曲線可能不夠平滑，有"突刺現象"

計數器滑動窗口演算法是計數器固定窗口演算法的改進，解決了固定窗口切換時可能會產生兩倍於閾值流量請求的缺點

滑動窗口演算法在固定窗口的基礎上，將一個計時窗口分成了若干個小窗口，然後每個小窗口維護一個獨立的計數器，當請求的時間大於當前窗口的最大時間時，則將計時窗口向前平移一個小窗口。

平移時，將第一個小窗口的數據丟棄，然後將第二個小窗口設置為第一個小窗口，同時在最後新增一個小窗口，將新的請求放在新增的小窗口中。同時要保肢鎮證整個窗口中所有小窗口的請求數目之後不能超過設定的閾值。

滑動窗口其實就是固定窗口的升級版。將計時窗口劃分成一個小窗口，滑動窗口演算法就退化成了固定窗口演算法。而滑動窗口演算法其實就是對請求數進行了更細粒度的限流。

窗口劃分的越多，則限流越精準

請求來了之後會首先進到漏斗里，然後漏斗以恆定的速率將請求流出進行處理，從而起到平滑流量的作用。當請求的流量過大時，漏斗達到最大容量時會溢出，此時請求被丟棄。

從系統的角度來看，我們不知道什麼時候會有請求來，也不知道請求會以多大的速率來，這就給系統的安全性埋下隱患。但是如果加了一層漏斗演算法限流之後，就能晌陵夠保證請求以恆定的速宴飢戚率流出。

在系統看來，請求永遠是以平滑的傳輸速率過來，從而起到來保護系統的作用。

漏斗特點：

令牌桶演算法是對漏桶演算法的一種改進，除了能夠在限制調用的平均速率的同時還允許一定程度的流量突發。

計數器固定窗口演算法實現簡單，容易理解。和漏斗演算法相比，新來的請求也能夠被馬上處理到。但是流量曲線可能不夠平滑，有"突刺現象"，在窗口切換時可能會產生兩倍於閾值流量的請求。

而計數器滑動窗口演算法作為計數器固定窗口演算法的一種改進，有效解決了窗口切換時可能會產生兩倍於閾值流量請求的問題

漏斗演算法能夠對流量起到整流的作用，讓隨機不穩定的流量以固定的速率流出，但是不能解決流量突發的問題。

令牌桶演算法作為漏斗演算法的一種改進，除了能夠起到平滑流量的作用，還允許一定程度的流量突發。

沒有最好的演算法，只有最合適的演算法

比如令牌桶演算法一般用於保護自身的系統，對調用者進行限流，保護自身的系統不被突發的流量打垮。如果自身的系統實際的處理能里強於配置的流量限制時，可以允許一定程度的流量突發，使得實際的處理速率，充分利用系統資源。

而漏斗演算法一般用於保護第三方的系統，比如自身的系統需要調用第三方的介面，為了保護第三方的系統不被自身的調用打垮，便可以通過漏斗演算法進行限流，保證自身的流量平穩的達到第三方的介面上。

演算法是死的，場景是活的。沒有最好的，只有最合適的。

Ⅵ 什麼是滑窗迭代演算法

TCP的首部中有一個很重要的欄位就是16位長的窗口大小，它出現在每一個TCP數據報中，配合32位的確認序號，用於向對端通告本地socket的接收窗口大小。也就是說，如果本地socket發送一個TCP數據，其32位確認序號是5,窗口大小是5840，則用於告訴對端，對端已經發出的4個位元組的數據已經收到並確認，接下來，本地socket最多能夠接收從第5個位元組開始的5840個位元組長度的數據。這是由接收方進行的一種流量控制，接收方通過告訴發送方自己所能夠接收數據的大小，達到控制發送方發送速度的目的。
結構體struct tcp_sock中有很多成員數據跟滑動窗口協議相關，需要注意的是這里講的滑動窗口都是指本地socket的接收窗口。
成員window_clamp表示滑動窗口的最大值，滑動窗口的大小在變化的過程中不能超出這個值。它在TCP連接建立的時候被初始化，被置為最大的16位整數左移窗口的擴大因子，因為滑動窗口在TCP首部中以16位表示，window_clamp太大會導致滑動窗口不能在TCP首部中表示。
成員rx_opt是一個struct tcp_options_received結構體，它有兩個成員snd_wscale和rcv_wscale，分別表示來自對端通告的滑動窗口擴大因子(本地發送數據報時需要遵守)，和本地接收滑動窗口的擴大因子。snd_wscale從來自對端的第一個SYN中獲取。rcv_wscale在本地socket建立連接時初始化，它賦值的原則是使16位整數的最大值左移rcv_wscale後，至少可以達到整個接收緩存的最大值。接收緩存最大值在協議棧中由全局變數mysysctl_rmem_max表示，它是256*(256+sizeof(struct sk_buff))後的值，為107520，但sysctl_tcp_rmem[3]所表示的接收緩存的上限更大，為174760，所以，取後者，這樣的話，rcv_wscale的值幾乎可以說是固定的，為2。所以window_clamp的值就是 65535 << 2 = 262140。可見，window_clamp的值超出了接收緩存的最大值，但這沒有關系，因為在滑動窗口增長的時候，會考慮接收緩存的大小這個因素的。
rcv_wnd表示當前的接收窗口的大小，這個值在接收到來自對端的數據後，會變動的。它的初始值取接收緩存大小的3/4跟MAX_TCP_WINDOW之間的最小值，MAX_TCP_WINDOW在系統中的定義為32767U。然後，還要根據mss的值作一個調整，調整邏輯是：如果mss大於3*1460，則如果當前的rcv_wnd大於兩倍的mss，就取兩倍的mss作為rcv_wnd的值；如果mss大於1460，則如果當前的rcv_wnd大於3倍的mss，就取3倍的mss作為rcv_wnd的新值；否則，如果rcv_wnd大於4倍的mss,就取4倍的mss作為rcv_wnd的新值，我們的實驗環境的mss值為1448(因為tcp首部有12位元組的時間戳選項)，所以rcv_wnd最後被調整為1448*4=5792。

Ⅶ 請問如何用python編寫滑動窗口演算法

用ActionChains這個模塊裡面的drag_and_drop 元素或者drag_and_drop_by_offset坐標

Ⅷ 熔斷限流

限流： 原理是監控應用流量的QPS或並發線程數等指標，當達到指定閾值時對流量進行控制，避免液則系統被瞬時的流量高峰沖垮，保障應用高可用性。保護自身系統防止被外部調垮。

熔斷： 調用遠程服務，後端服務不可避免的會產生調用失敗（超時或者異常），防止應用程序不斷地嘗試可能超時和失敗的服務，能達到應用程序執行而不必等待下游服務修正錯誤服務。

降級： 是指犧牲非核心的業務功能，保證核心功能的穩定運行。在後台通過開關控制，降級部分非主流程的業務功能，減輕系統依賴和性能損耗，從而提升集群的整體吞吐率。

 Hystrix 的關注點在於以隔離和 熔斷 為主的容錯機制，超時或被熔斷的調用將會快速失敗，並可以提供 fallback 機制。Hystrix 提供兩種隔離策略： 線程池隔離（Bulkhead Pattern） 和 信號量隔離。

線程池隔離： 針對不同的資源分別創建不同的線程池，不同服務調用都發生在不同的線程池中，在線程池排隊、超時等阻塞情況時可以快速失敗，並可以提供 fallback 機制。好處是隔離度比較高，單獨處理某個資源；代價就是線程上下文切換的 overhead 比較大，會讓機器資源碎片化，特別是對低延時的調用有比較大的影響。

信號量隔離： 限制對某個資源調用的並發數，更為輕量，開銷更小。但缺點是無法對慢調用自動進行降級，只能等待客戶端自己超時，因此仍然可能會出現級聯阻塞的情況。

Sentinel 和 Hystrix 的熔斷降級功能本質上都是基於熔斷器模式（Circuit Breaker Pattern）。Sentinel 與 Hystrix 都支持基於 失敗比率（異常比率） 的熔斷降級， 在調用達到一定量級並且失敗比率達到設定的閾值時自動進行熔斷 ，此時所有對該資源的調用都會被 block，直到過了指定的時間窗口後才啟發性地恢復。 Sentinel 還支持基於平均響應時間的熔斷降級，可以在服務響應時間持續飆高的時候自動熔斷 ，拒絕掉更多的請求，直到一段時間後才恢復。這樣可以防止調用非常慢造成級聯阻塞的情況。

Hystrix 和 Sentinel 的實時指標數據統計實現都是基於滑動窗口的。

Sentinel：輕量級和高性能， 可以針對不同的調用關系，以 不同的運行指標（如 QPS、並發調用數、系統負載等） 為基準，對資源調用進行流量控制，將隨機的請求調整成合適的形狀。

熔斷策略： 平均響應時間 (DEGRADE_GRADE_RT)：時間窗口內介面調用RT超過一定時巧碰間，下一時間窗口自動熔斷； 異常比例 (DEGRADE_GRADE_EXCEPTION_RATIO) ：每秒調用時間異常比例超過一定閾值，自動熔斷； 異常數 (DEGRADE_GRADE_EXCEPTION_COUNT)：當資源近 1 分鍾的異常數目超過閾值之後會進行熔斷。

流量控制(Flow Control)，原理是監控應用流量的QPS或並發線程數等指標，當達到指定閾值時對流量進行控制，避免系統被瞬時的流量高峰沖垮，保障應用高可用性。

流量整形策略： 直接拒絕模式 ：即超出的請求直接拒絕。

慢啟動預熱模式 ：當流量激增的時候，控制流量通過的速率，讓通過的流量緩慢增加，在一定時間內逐漸增加到閾值上限，給冷系統一個預熱的時間，避免冷系統被壓垮。

勻速器模式： 利用 Leaky Bucket 演算法實現的勻速模式，嚴格控制了請求通過的時間間隔，同時堆積的請求將會排隊，超過超時時長的請求直接被拒絕。

常用限流演算法：

①計數器限流演算法

通過一個計數器，限制每一秒鍾能夠接收的請求數。周期內，超過閾值後的請求就會被全部拒絕。

②滑動窗口演算法（sentinel使用）

滑動窗口演算法是將時間周期分為N個小周期（窗口），分別記錄每個小周期內訪問次鬧寬棚數，然後根據時間將窗口往前滑動，統計時間窗口內調用次數。

③漏桶限流演算法

實現一個容器，容量固定，訪問請求到達時直接放入漏桶，如當前容量已達到上限（限流值），則進行丟棄（觸發限流策略）。漏桶以固定的速率進行釋放訪問請求（即請求通過），直到漏桶為空。實際上消息中間件就使用了漏桶限流的思想，不管生產者的請求量有多大， 消息的處理能力取決於消費者。

④令牌桶限流演算法

令牌桶是網路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種演算法。對於每一個請求，都需要從令牌桶中獲得一個令牌，如果沒有獲得令牌，則需要觸發限流策略。

Ⅸ perl中的滑動窗口是怎麼回事啊

滑動窗口是一種特別的數據結構和演算法吧，搭神歲打個比方，有一個1，2，3，4，5，6，7，8，9，10的序列，滑動窗口大小知睜為3，窗口從最左邊進入序列，那麼，窗口內的數據就應該是，
【1，2，3】，4，5，6，……這樣，【】表示窗口，
當窗口向右移動，就成了瞎槐1，【2，3，4】，5，6，……這樣，
你可以利用這個結構，很快的找到從第幾位開始，接下來的窗口大小內的數據是什麼，在研究DNA鹼基序列中可以很方便，你只需從窗口中取出鹼基序列就可以做相應的事情，如果不行，可以將窗口向前移動繼續查找。

Ⅹ Redis 限制頻繁請求攔截處理

項目運維人員發現NGINX日誌中短時間內有同一IP、同一用戶、同一設備發出的大量請求，比用戶正常行為產生的請求頻率要高出很多，所以有對單位時間內訪問頻次限制的需求。

一般就會在伺服器端將用戶信息和訪問信息做下關聯，以此來實現訪問頻次限制。通常大家都會選擇 Redis 來作為此中間件的存儲介質。

幾種最常用的限流演算法：

固定窗口計數器演算法概念如下：

固定窗口計數器是最為簡單的演算法，但這個演算法有時會讓通過請求量允許為限制的兩倍。考慮如下情況：限制 1 秒內最多通過 5 個請求，在第一個窗口的最後半秒內通過了 5 個請求，第二個窗口的前半秒內又通過了 5 個請求。這樣看來就是在 1 秒內通過了 10 個請求。

滑動窗口計數器演算法概念如下：

滑動窗口計數器是通過將窗口再細分，並且按照時間"滑動"，這種演算法避免了固定窗口計數器帶來的雙倍突發請求，但時間區間的精度越春廳高，演算法所需的空間容量就越大。

漏桶演算法概念如下：

漏桶演算法多使用 隊列 實現，服務的請求會存到隊列中，服務的提供方則按照固定的速率從隊列中取出請求並執行，過多的請求則放在隊列中排隊或直接拒絕。

漏桶演算法的缺陷也很明顯，當短時間內有大量的突發請求時，即便此時伺服器沒有任何負載，每個請求也都得在隊列中等待一段時間才能被響應。

令牌桶演算法概念如下：

令牌桶演算法既能夠將所有的請求平均分布到時間區間內，又能接受伺服器能夠純凱承受范圍內的突發請求，因此是目前使扒褲隱用較為廣泛的一種限流演算法。

業務對此要求不高，所以用了簡單的固定窗口計數器演算法。