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