資訊專欄INFORMATION COLUMN
摘要：理解數組實現的滑動窗口，看下邊這個圖就可以了。第秒，開始計數，此時數組內開始存入計數周期，保存在數組第個位置，表示這是當前滑動窗口內的第個計數周期。
在FireflySoft.RateLimit之前的版本中，進程內滑動窗口的實現是基于MemoryCache做的，雖然能夠正確的實現滑動窗口的算法邏輯，但是性能比較差，其吞吐量只有其它算法的1/4。性能為何如此之差呢？
我們先來看下滑動窗口的原理，這里給一張圖：
?
如上圖所示：
使用MemoryCache時，存儲結構如下：
每個計數周期都作為一個緩存項目添加到MemoryCache中，緩存Key為計數周期的絕對時間，緩存值為當前周期的計數值，緩存過期時間為一個大于滑動窗口時間跨度的相對過期時間，這樣不用自己編碼刪除過期的計數周期，而滑動窗口內的計數周期都能正常保留。
另外為了獲得滑動窗口內部每個計數周期對應的緩存項，這里還額外緩存了第一個計數周期的緩存Key（即對應的絕對時間），這樣就可以根據當前時間和計數周期的時間跨度計算出當前周期的緩存Key，從而可以再逐步向前推出4個計數周期的緩存Key。
如有興趣，具體實現可以點擊這里進入Github查看。
這個實現有兩個問題：
這應該就是這個算法實現性能比較差的主要原因。
為什么要使用數組來實現滑動窗口呢？首先當然是數組可以實現滑動窗口，其次它可以解決MemoryCache實現中的兩個問題，一是數組創建時就申請了固定大小的內存，后續計數都使用這塊內存，不用再新申請；二是計算滑動窗口內的計數值只要把數組中每個元素的值加起來就行了，不用再一個個的尋找它們。
學過操作系統的同學可能比較了解，在操作系統中很多地方使用了環形隊列，而環形隊列是用數組實現的；滑動窗口可以理解為環形隊列的一個特例，每次窗口滑動時，隊列彈出一個，然后再進入一個。
理解數組實現的滑動窗口，看下邊這個圖就可以了。
假設滑動窗口的時間跨度還是5s，計數周期的時間跨度是1秒。
首先我們初始化一個容量為5的空數組，此時還沒有開始計數，所以只是一個空數組。
然后隨著時間的前進，滑動窗口的處理就是循環第5秒至第9秒之間的處理邏輯。
再說計數的處理：
這里摘抄一些代碼，讓大家感受更深入一些：
// 幾個重要變量：保存計數周期的數組、代表滑動窗口的循環隊列的頭和尾SlidingWindowPeriod[] _queue;int _head = 0;int _tail = 0;// 省略很多代碼....// 創建一個計數周期，這里是一個結構體var newPeriod = new SlidingWindowPeriod(){ // 為了方便確定當前請求的計數周期，計數周期的Key是一個時間刻度， Key = lastPeriod.Key + _statPeriodMilliseconds * i, CountValue = 0};// 循環隊列尾加1// 如果超出了數組的索引范圍，則代表需要替換數組中第1個位置的計數周期，然后隊列尾來到數組中第1位_tail++;if (_tail == _length) _tail = 0;// 如果隊列尾在數組中的索引小于等于隊列頭的索引，則隊列頭需要彈出數據，隊列頭的位置向后移動1位if (_tail <= _head){ _head++; // 如果隊列頭的索引會超出索引范圍，則隊列頭歸位到數組中的第1位 if (_head == _length) _head = 0;}// 將新的計數周期寫入隊列尾所在的數組位置_queue[_tail] = newPeriod;
這里邊還會有一些特殊的處理，比如滑動窗口只包含一個小計數周期，再比如請求時間的前進是不均勻的（可能會跳過數個計數周期的時間跨度），都需要仔細考慮。
?
好了，以上就是本文的主要內容。
如果想了解完整的實現，查看全部代碼，請點擊進入GitHub。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/125674.html
摘要：你只可以看到在滑動窗口內的數字?；瑒哟翱诿看沃幌蛴乙苿右晃?。返回滑動窗口最大值。算法思路暴力破解法用兩個指針，分別指向窗口的起始位置和終止位置，然后遍歷窗口中的數據，求出最大值向前移動兩個指針，然后操作，直到遍歷數據完成位置。 Time：2019/4/16Title: Sliding Window MaximumDifficulty: DifficultyAuthor: 小鹿 題目...
摘要：代碼實現代碼實現接下來思考一個熔斷器如何實現。同時熔斷器的狀態也需要依靠指標統計來實現可觀測性，我們實現任何系統第一步需要考慮就是可觀測性，不然系統就是一個黑盒。可能是，熔斷器需要實時收集此數據。熔斷方法，自動上報執行結果自動擋。。。為什么需要熔斷微服務集群中，每個應用基本都會依賴一定數量的外部服務。有可能隨時都會遇到網絡連接緩慢，超時，依賴服務過載，服務不可用的情況,在高并發場景下如果此時...
摘要：你只可以看到在滑動窗口內的數字。滑動窗口每次只向右移動一位。返回滑動窗口最大值。 這篇文章我們來看一道題目求滑動窗口最大值問題(在leetcode上的地址：滑動窗口最大值) 題目描述 給定一個長度為N的數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口 k 內的數字?；瑒哟翱诿看沃幌蛴乙苿右晃?。返回滑動窗口最大值。 示例: 輸入: nu...
摘要：計數限流算法無論固定窗口還是滑動窗口核心均是對請求進行計數，區別僅僅在于對于計數時間區間的處理。令牌桶限流實現原理令牌桶限流的實現原理在有詳細說明。因此由此為入口進行分析。目前可返回的實現子類包括及兩種，具體不同下文詳細分析。 限流 限流一詞常用于計算機網絡之中，定義如下： In computer networks, rate limiting is used to control t...
摘要：之前有了解到哥的一部分讀者們沒有充分搞清楚限流和熔斷的關系。后者表示系統在同一時刻能處理的最大請求數量，比如次的并發。后續限流策略需要設定的具體標準數值就是從這些指標中來的。限流閾值不繼續處理請求。 如果這是第二次看到我的文章，歡迎掃描文末二維碼訂閱我喲~本文長度為2869字，建議閱讀8分鐘。 可能你在網上看過不少「限流」相關的文章，但是z哥的這篇可能是最全面，最深入淺出的一篇了（容我...
閱讀 3748·2023-01-11 11:02
閱讀 4254·2023-01-11 11:02
閱讀 3072·2023-01-11 11:02
閱讀 5189·2023-01-11 11:02
閱讀 4750·2023-01-11 11:02
閱讀 5561·2023-01-11 11:02
閱讀 5327·2023-01-11 11:02
閱讀 4023·2023-01-11 11:02
