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