一種改進(jìn)的2q算法在flexianche系統(tǒng)中的應(yīng)用

一種改進(jìn)的2q算法在flexianche系統(tǒng)中的應(yīng)用

1共享型大規(guī)模共享存儲(chǔ)模式的改進(jìn)設(shè)計(jì)隨著網(wǎng)絡(luò)和存儲(chǔ)技術(shù)的發(fā)展，集中存儲(chǔ)模式逐漸取代了傳統(tǒng)的地方直連式存儲(chǔ)模式。其中前者的優(yōu)點(diǎn)在于:它不僅能夠有效降低存儲(chǔ)管理成本,同時(shí)便于實(shí)現(xiàn)應(yīng)用間的數(shù)據(jù)共享、在線數(shù)據(jù)備份以及存儲(chǔ)虛擬化等高級(jí)存儲(chǔ)管理功能。在集中式存儲(chǔ)模式下,存儲(chǔ)系統(tǒng)作為一種共享資源通常需要同時(shí)服務(wù)于多種不同類型的應(yīng)用。緩存作為一種重用的性能優(yōu)化手段被廣泛應(yīng)用于各級(jí)存儲(chǔ)系統(tǒng)來提高應(yīng)用的I/O性能。傳統(tǒng)緩存系統(tǒng)在設(shè)計(jì)上采用基于全局替換方法,因而不能夠很好地適用于集中式存儲(chǔ)模式下的緩存管理,這是由于共享緩存的多種應(yīng)用往往具有不同類型的訪問模式,單一的緩存替換算法會(huì)導(dǎo)致緩存資源利用率的低下。為了解決該問題,我們?cè)谇捌诠ぷ髦刑岢隽艘环N基于動(dòng)態(tài)分區(qū)技術(shù)的緩存管理架構(gòu)-FlexiCache。在該架構(gòu)下,每個(gè)應(yīng)用具有相對(duì)獨(dú)立的緩存分區(qū)。根據(jù)具體應(yīng)用的負(fù)載訪問模式,每個(gè)緩存分區(qū)可以配置更適合的替換算法,從而有效地提高緩存資源利用率。稱該方法為基于替換算法的局部優(yōu)化。為了達(dá)成局部優(yōu)化效果,我們需要分析替換算法對(duì)于各種不同類型應(yīng)用負(fù)載的適用性。本文研究適用于郵件服務(wù)類負(fù)載的替換算法。已知一個(gè)優(yōu)秀的替換算法的重要標(biāo)志是能夠在中等緩存容量時(shí)取得相比于其他替換算法更好的性能?；诖?在對(duì)已有替換算法的模擬實(shí)驗(yàn)中發(fā)現(xiàn)2Q算法相比于其他算法更適合于郵件服務(wù)類負(fù)載。如圖2(a)所示,2Q算法對(duì)于郵件服務(wù)負(fù)載的命中曲線隨緩存容量增長穩(wěn)步提升且在中等緩存容量區(qū)間明顯優(yōu)于LRU算法。然而當(dāng)緩存容量足夠大時(shí),2Q算法的性能反略低于LRU算法。為了能夠在各種緩存容量配置下有效優(yōu)化郵件服務(wù)類應(yīng)用的物理I/O性能,本文有針對(duì)性地改進(jìn)了2Q算法。改進(jìn)后的2Q*算法不僅可以在中、小緩存容量時(shí)優(yōu)于其他替換算法,同時(shí)能夠有效改善經(jīng)典2Q算法在大緩存容量下的性能。為了驗(yàn)證2Q*算法在真實(shí)系統(tǒng)中的有效性,將該算法應(yīng)用于FlexiCache存儲(chǔ)緩存系統(tǒng)中并與目前主流的順序自適應(yīng)預(yù)取策略有機(jī)結(jié)合。實(shí)驗(yàn)結(jié)果表明,2Q*算法能夠有效地改善郵件服務(wù)類應(yīng)用的I/O性能。本文第2節(jié)分析了2Q算法對(duì)于郵件服務(wù)類負(fù)載所表現(xiàn)出的性能特點(diǎn);第3節(jié)針對(duì)郵件服務(wù)類應(yīng)用提出了改進(jìn)的算法2Q*并給出相應(yīng)的模擬實(shí)驗(yàn)結(jié)果;第4節(jié)討論如何將2Q*算法應(yīng)用于FexiCache系統(tǒng);第5節(jié)給出2Q*算法在真實(shí)系統(tǒng)中的性能評(píng)測(cè);最后總結(jié)全文。2q并行實(shí)驗(yàn)本節(jié)分析2Q算法對(duì)于郵件服務(wù)類負(fù)載所表現(xiàn)出的性能特點(diǎn)。分析的目的在于:1)指出2Q算法在中等緩存容量時(shí)的性能優(yōu)勢(shì);2)指出導(dǎo)致2Q算法在大緩存容量時(shí)性能劣勢(shì)的原因。為了便于分析,采用模擬實(shí)驗(yàn)方法并選擇LRU算法作為2Q算法的性能對(duì)比對(duì)象,其中LRU算法是目前實(shí)際存儲(chǔ)系統(tǒng)中普遍采用的一種替換算法,其最大的優(yōu)點(diǎn)在于簡單高效。本文實(shí)驗(yàn)中緩存塊的粒度均設(shè)為4kB,且使用的郵件服務(wù)類負(fù)載(負(fù)載統(tǒng)計(jì)信息參如表1所列)均采集于惠普公司郵件服務(wù)器的后端存儲(chǔ)系統(tǒng),其中郵件服務(wù)器的管理軟件版本為Openmail。在本節(jié)模擬實(shí)驗(yàn)中,選用第5號(hào)郵件服務(wù)器負(fù)載進(jìn)行分析。為了便于討論,依據(jù)郵件服務(wù)負(fù)載的數(shù)據(jù)集大小將緩存容量依次劃分為以下3個(gè)區(qū)間:小容量[32～256MB]、中容量[0.25～1.25GB]和大容量[1.25～2GB]。下面首先分析郵件服務(wù)類負(fù)載的特點(diǎn)。2.1相鄰訪問間距分布圖1(a)給出了郵件服務(wù)負(fù)載的重復(fù)訪問頻率分布,即在不同訪問頻度下數(shù)據(jù)塊再次被訪問的概率分布;圖1(b)給出了數(shù)據(jù)塊在不同訪問頻度下被再次訪問的平均相鄰訪問間距(IRGinter-referencegap)分布;圖1(c)則給出了郵件服務(wù)負(fù)載中數(shù)據(jù)訪問落在不同相鄰訪問間距內(nèi)的柱狀圖分布,圖中x軸的每一坐標(biāo)點(diǎn)xi代表IRG落在區(qū)間[xi,xi-1]內(nèi)的數(shù)據(jù)訪問總和。從中可以歸納出郵件服務(wù)負(fù)載的以下3個(gè)特點(diǎn):1)由圖1(a)可知,負(fù)載中存在相當(dāng)數(shù)量的非活躍數(shù)據(jù),據(jù)統(tǒng)計(jì)僅訪問1,2,3,4和5次的數(shù)據(jù)塊所占比例依次分別約為15%,21%,10%,13%和8%,而重復(fù)訪問超過5次的數(shù)據(jù)塊則僅占35%;2)隨著數(shù)據(jù)訪問頻度的增大,平均相鄰訪問間距隨之顯著下降,觀察圖1(a)可知絕大多數(shù)的數(shù)據(jù)塊在前5次訪問中的IRG較大,此后則相對(duì)較小;3)由圖1(c)所示,絕大多數(shù)的數(shù)據(jù)訪問IRG落在IRG分布區(qū)間兩端,僅有非常少量的數(shù)據(jù)訪問IRG處于IRG分布的中間區(qū)間。2.2基于傳遞的分辨率響應(yīng)特性基于郵件服務(wù)負(fù)載的上述3個(gè)特點(diǎn),在下一小節(jié)中對(duì)比分析2Q算法和LRU算法的性能差異。本文實(shí)驗(yàn)中2Q算法的q1.in隊(duì)列長度限制為緩存容量的1/10,而q1.out隊(duì)列大小則與真實(shí)緩存容量相當(dāng)。圖2(a)給出了郵件服務(wù)負(fù)載在兩種替換算法下的命中率變化曲線,其中測(cè)試的緩存容量從32MB變化至2GB。由圖可知,2Q算法在中小緩存容量范圍內(nèi)(32MB～1.25GB)的性能均優(yōu)于LRU算法,特別是在緩存容量介于256MB和1.25GB之間時(shí),2Q算法的性能優(yōu)勢(shì)非常明顯。當(dāng)緩存容量為0.5GB時(shí),2Q算法的緩存命中率比LRU算法高出10%。然而隨著緩存容量的進(jìn)一步增長,2Q算法的性能反而不如LRU算法。當(dāng)緩存容量為1.75GB時(shí),2Q算法命中率比LRU算法低了4%。下面將對(duì)上述兩種算法表現(xiàn)出的特點(diǎn)做進(jìn)一步分析,重點(diǎn)分析2Q算法在中等緩存容量時(shí)的性能優(yōu)勢(shì)及其在大緩存容量下相對(duì)性能下降的原因。2.2.1不同存儲(chǔ)頻率的活躍數(shù)據(jù)的算法結(jié)果2Q算法中q1隊(duì)列用于識(shí)別負(fù)載中的活躍數(shù)據(jù)。q1隊(duì)列是按照FIFO方式進(jìn)行管理的,一旦數(shù)據(jù)訪問在q1隊(duì)列中命中,則相應(yīng)將緩存數(shù)據(jù)遷移至qm隊(duì)列;qm隊(duì)列是以LRU的方式管理當(dāng)前負(fù)載中識(shí)別出的活躍數(shù)據(jù)。這里非活躍數(shù)據(jù)是指相鄰訪問間距較大或者僅訪問一次的數(shù)據(jù)塊,反之活躍數(shù)據(jù)是頻繁多次訪問且相鄰訪問間距相對(duì)較小的數(shù)據(jù)。由于q1隊(duì)列在功能上只是為了能夠快速區(qū)分出負(fù)載中的非活躍數(shù)據(jù),為了降低q1隊(duì)列所占緩存容量比例,q1隊(duì)列被劃分為q1.in和q1.out兩部分。其中前者在緩存中,而后者只是記錄數(shù)據(jù)塊ID而并不保存數(shù)據(jù)內(nèi)容本身。q1.in隊(duì)列長度限制(取決于K1in參數(shù))通常設(shè)為緩存總?cè)萘康暮苄∫徊糠?如1/10。此外,僅當(dāng)數(shù)據(jù)在q1.out隊(duì)列中命中時(shí)才被識(shí)別為活躍數(shù)據(jù)并遷移至qm隊(duì)列首。而當(dāng)數(shù)據(jù)在q1.in隊(duì)列中命中時(shí)算法并不做任何處理,其原因在于這樣可以避免將負(fù)載中僅在某一較短時(shí)段內(nèi)被連續(xù)多次關(guān)聯(lián)訪問(correlatedreferences)的數(shù)據(jù)塊識(shí)別為活躍數(shù)據(jù)。顯然,短時(shí)內(nèi)對(duì)同一數(shù)據(jù)塊的連續(xù)多次關(guān)聯(lián)訪問并不能客觀地反映數(shù)據(jù)當(dāng)前的訪問熱度。圖2(b)給出了數(shù)據(jù)訪問分別在q1.in,q1.out和qm3個(gè)隊(duì)列中的累積命中次數(shù)隨緩存總?cè)萘孔兓姆植?。在小緩存容量時(shí),由于數(shù)據(jù)塊的前幾次訪問的相鄰訪問間距較大(郵件服務(wù)負(fù)載特性2),因此數(shù)據(jù)塊在前幾次訪問時(shí)不僅被快速地從q1.in隊(duì)列中替換出去,同時(shí)很難在q1.out隊(duì)列中命中。然而隨著數(shù)據(jù)訪問頻度的增加,數(shù)據(jù)塊的相鄰訪問間距顯著下降(郵件服務(wù)負(fù)載特性2),因此數(shù)據(jù)塊在高頻訪問時(shí)在q1.in和q1.out隊(duì)列中命中的幾率相應(yīng)明顯增大。又由于負(fù)載中訪問頻度較高的數(shù)據(jù)塊所占比例非常小(郵件服務(wù)負(fù)載特性1),因此在小緩存容量時(shí)q1.out隊(duì)列中的命中次數(shù)也非常有限。然而,就是這些少量從q1.out隊(duì)列中識(shí)別出的活躍數(shù)據(jù)可以長期緩存在qm隊(duì)列中,從而在一定程度上提高了緩存命中率。這也正是2Q算法在小緩存容量時(shí)略優(yōu)于LRU算法的原因。在中等緩存容量區(qū)間時(shí),如圖2(b)所示,隨著緩存容量的增長,q1.out隊(duì)列的命中次數(shù)持續(xù)增長,相應(yīng)的qm隊(duì)列中的緩存命中次數(shù)也相應(yīng)增長,而q1.in隊(duì)列的命中次數(shù)則相反隨之下降。這是相當(dāng)數(shù)量的活躍數(shù)據(jù)在前幾次訪問時(shí)在q1.out隊(duì)列中命中而直接加入qm隊(duì)列所致。由圖可知,q1.in和qm兩隊(duì)列的累積命中次數(shù)總和則呈穩(wěn)步上升趨勢(shì)。在大緩存容量區(qū)間時(shí),一方面隨著緩存容量的增長,q1.in隊(duì)列的命中次數(shù)隨緩存容量的增長顯著提高,而q1.out隊(duì)列的命中次數(shù)反而呈急劇下降的趨勢(shì),這是當(dāng)緩存容量足夠大時(shí)初始數(shù)據(jù)訪問在q1.in隊(duì)列中的命中幾率顯著增大所致;另一方面,從q1.out隊(duì)列中識(shí)別出的活躍數(shù)據(jù)的減少直接導(dǎo)致了qm隊(duì)列命中次數(shù)的相應(yīng)下降。由郵件服務(wù)負(fù)載特性2)可知,后續(xù)數(shù)據(jù)訪問的IRG隨訪問頻度的增加而變得越來越小。而q1.in隊(duì)列的FIFO管理方式意味著任何數(shù)據(jù)為了能夠長期駐留于緩存中,必須在q1.out隊(duì)列中經(jīng)歷一次緩存失效,我們稱這種失效為強(qiáng)制識(shí)別失效(compulsoryidentificationmiss)。顯然,在大緩存容量區(qū)間仍對(duì)q1.in隊(duì)列采用FIFO管理方式是沒有必要的。此外,額外的強(qiáng)制識(shí)別失效開銷會(huì)帶來2Q算法緩存性能的相對(duì)下降。2.2.2存儲(chǔ)密度小的irg存儲(chǔ)增長快從圖2(a)可以看出,LRU緩存命中率曲線在中等緩存容量時(shí)的上升速率要明顯低于2Q算法。經(jīng)分析發(fā)現(xiàn),這是郵件負(fù)載特性3)所致,即數(shù)據(jù)訪問IRG集中在IRG分布的兩端,因而在處于中等緩存容量時(shí),相當(dāng)數(shù)量的數(shù)據(jù)訪問IRG始終高于當(dāng)前的緩存容量。這使得LRU算法無法有效利用負(fù)載中的訪問局部性,從而導(dǎo)致緩存命中率隨緩存容量增大其提升相對(duì)很小。相比之下,2Q算法能夠利用q1隊(duì)列快速有效地區(qū)分出當(dāng)前負(fù)載中活躍和非活躍數(shù)據(jù),并將識(shí)別出的活躍數(shù)據(jù)緩存在獨(dú)立于q1.in隊(duì)列的qm隊(duì)列中,從而有效提高后者的緩存空間利用率。正因如此,2Q算法的緩存命中率曲線可以在中等緩存容量區(qū)間時(shí)仍隨緩存容量的增長而穩(wěn)步增長。2.2.3不同存儲(chǔ)容量的sdra算法性能比較由以上分析,可以得出以下結(jié)論:①當(dāng)緩存容量相對(duì)有限時(shí)(中、小緩存容量區(qū)間),2Q算法通過區(qū)分負(fù)載中的活躍和非活躍數(shù)據(jù)來有效提高緩存空間利用率。相反,LRU算法由于郵件服務(wù)負(fù)載特性而不能夠高效地利用緩存資源,特別當(dāng)處于中等緩存容量時(shí),LRU算法的命中率曲線隨緩存容量的增大而上升得相對(duì)緩慢。②當(dāng)緩存容量相對(duì)充足時(shí)(大緩存容量區(qū)間),數(shù)據(jù)訪問在2Q算法中的q1.in隊(duì)列命中機(jī)率增大,因而其FIFO的管理方式不僅不能夠有效利用負(fù)載中局部性,反而會(huì)帶來了額外的強(qiáng)制識(shí)別失效開銷。這正是2Q算法的命中率曲線在大緩存容量區(qū)間時(shí)反被LRU算法曲線超出的原因。32q算法的改進(jìn)2q3.1q#算法在低負(fù)荷容量下的性能通過3.1節(jié)的分析可知2Q算法中q1.in隊(duì)列中的FIFO管理方式是直接導(dǎo)致其在大緩存容量時(shí)性能相對(duì)下降的原因。為了能夠有效降低2Q算法在大緩存容量時(shí)由于強(qiáng)制識(shí)別失效所帶來的不必要的性能損失,我們對(duì)2Q算法中的q1隊(duì)列管理方式進(jìn)行相應(yīng)的改進(jìn):采用LRU方式管理q1.in隊(duì)列,而沿用原先的FIFO方式管理q1.out隊(duì)列,我們稱改進(jìn)后的算法為2Q*。這樣改進(jìn)的依據(jù)在于:1)q1.in隊(duì)列管理方式在改為LRU方式后,2Q算法在大緩存容量下的行為與LRU算法相似。具體來說,在緩存預(yù)熱階段首次失效數(shù)據(jù)都是加入到q1.in隊(duì)列中。當(dāng)緩存容量足夠大時(shí),絕大多數(shù)的數(shù)據(jù)訪問都可在q1.in隊(duì)列中命中,且又因?yàn)閝1.in隊(duì)列是按照LRU方式管理的,因此在q1.in隊(duì)列中命中的緩存數(shù)據(jù)又被重新移入q1.in隊(duì)列頭,從而僅有很少量的數(shù)據(jù)訪問會(huì)在q1.in隊(duì)列中失效而在q1.out中命中。換言之,在大緩存容量下,2Q*算法會(huì)將絕大多數(shù)緩存容量分配給按照LRU方式管理的q1.in隊(duì)列。在3.3節(jié)中將通過模擬實(shí)驗(yàn)數(shù)據(jù)來驗(yàn)證這一點(diǎn)。已知當(dāng)緩存容量足夠大以至于和負(fù)載中活躍數(shù)據(jù)訪問集的大小相當(dāng)時(shí),LRU算法被公認(rèn)為是最有效的替換算法,因此改進(jìn)后的2Q*算法可以有效改善2Q算法在大緩存容量下的性能。2)通過嚴(yán)格限制q1.in隊(duì)列的長度(如在本文實(shí)驗(yàn)中K1in參數(shù)均設(shè)為1/10),改進(jìn)后的2Q*算法對(duì)于q1隊(duì)列的不同管理方式并不會(huì)影響其在緩存容量有限時(shí)對(duì)于負(fù)載中活躍數(shù)據(jù)識(shí)別的有效性,即能夠保證經(jīng)典2Q算法在中、小緩存容量時(shí)的性能優(yōu)勢(shì)。同樣在3.3節(jié)中將通過模擬實(shí)驗(yàn)數(shù)據(jù)來驗(yàn)證這一點(diǎn)。3.2算法描述圖3給出了2Q*算法的偽代碼描述。下面分別闡述該算法對(duì)于失效、命中和替換等3種不同緩存管理操作的處理流程:1模式2.1排塊塊中數(shù)據(jù)塊的總體功能1.in1-1)當(dāng)被訪問數(shù)據(jù)塊在q1.in隊(duì)列中命中,數(shù)據(jù)塊將被移至q1.in隊(duì)列首;1-2)當(dāng)被訪問數(shù)據(jù)塊在qm隊(duì)列中命中,數(shù)據(jù)將被移至qm隊(duì)列首。2被加入qm序列2-1)當(dāng)被訪問數(shù)據(jù)塊在q1.out隊(duì)列中命中,數(shù)據(jù)塊作為當(dāng)前識(shí)別出的活躍數(shù)據(jù)而被加入qm隊(duì)列首,該數(shù)據(jù)塊在q1.out隊(duì)列中的ID也將相應(yīng)被刪除;2-2)當(dāng)被訪問數(shù)據(jù)塊沒有在q1.out隊(duì)列中命中,數(shù)據(jù)塊作為當(dāng)前非活躍數(shù)據(jù)而被加入q1.in隊(duì)列首。3新失效數(shù)據(jù)塊的存儲(chǔ)3-1)當(dāng)前緩存處于預(yù)熱階段(即仍有空閑緩存塊),那么從空閑緩存中挑選出一塊來存儲(chǔ)新近失效數(shù)據(jù)塊內(nèi)容;3-2)當(dāng)前緩存處于飽和階段(即已無空閑緩存塊)且q1.in隊(duì)列的長度超過Klin參數(shù)限制,那么替換出當(dāng)前處于q1.in隊(duì)列尾部的數(shù)據(jù)塊來存儲(chǔ)新近失效數(shù)據(jù)塊內(nèi)容;3-3)當(dāng)前緩存處于飽和階段且q1.in隊(duì)列的長度不足Klin參數(shù)限制,那么替換出當(dāng)前處于qm隊(duì)列尾部的數(shù)據(jù)塊來存儲(chǔ)新近失效數(shù)據(jù)塊內(nèi)容。3.3q#算法性能差異本小節(jié)通過模擬實(shí)驗(yàn)對(duì)比改進(jìn)后的2Q*算法與已有替換算法的性能并重點(diǎn)分析導(dǎo)致2Q*算法與經(jīng)典2Q算法之間性能差異的原因。實(shí)驗(yàn)結(jié)果如圖4所示,改進(jìn)后的2Q*算法在中、小緩存容量區(qū)間內(nèi)的性能與2Q算法相當(dāng),優(yōu)于包括LRU,LFU,ARC和LIRS在內(nèi)的4種經(jīng)典替換算法。以第5號(hào)郵件服務(wù)器負(fù)載為例,2Q*算法在中等緩存容量下提升緩存命中率最高可達(dá)30%(相對(duì)于緩存容量為0.75GB時(shí)的LRU算法);而在大緩存容量時(shí),2Q*算法與LRU算法相當(dāng),略優(yōu)于包括經(jīng)典2Q算法在內(nèi)的其他4種替換算法。下面以第5號(hào)郵件服務(wù)器負(fù)載為例進(jìn)一步分析2Q*與2Q算法的性能差異緣由。圖5(a-c)分別給出了改進(jìn)前后的2Q算法中q1.in,q1.out以及qm等3隊(duì)列的累計(jì)命中次數(shù)隨緩存容量的分布對(duì)比。從圖中觀察可得以下幾點(diǎn):1)2Q*算法提高了數(shù)據(jù)訪問在q1.in隊(duì)列中的命中次數(shù),且隨著緩存容量的增長改進(jìn)前后兩種算法在q1.in隊(duì)列中的命中次數(shù)差距不斷被擴(kuò)大,顯然這是由于2Q*算法在采用LRU方式后使得在大緩存容量時(shí)更多的數(shù)據(jù)訪問在q1.in隊(duì)列中命中;2)2Q*算法使得失效數(shù)據(jù)訪問在q1.out隊(duì)列中的命中次數(shù)在大緩存容量時(shí)明顯降低,這是由于在大緩存容量時(shí),改進(jìn)后的2Q*算法使得更多的數(shù)據(jù)訪問在q1.in隊(duì)列中命中,從而也就相應(yīng)降低了失效數(shù)據(jù)訪問在q1.out隊(duì)列中的命中幾率;3)2Q算法中的qm隊(duì)列命中次數(shù)要明顯高于2Q*算法,且隨著緩存容量的增大兩者之間的差距在逐步加大,這是由于在2Q*算法中所識(shí)別出的活躍數(shù)據(jù)量相對(duì)于經(jīng)典2Q算法要少,顯然活躍數(shù)據(jù)量的減少必然帶來了qm隊(duì)列中數(shù)據(jù)訪問命中次數(shù)的下降。但是通過對(duì)比圖5(a)和圖5(c),可以發(fā)現(xiàn)2Q*算法對(duì)于q1.in隊(duì)列命中次數(shù)的提升在絕對(duì)值上要明顯高于其對(duì)于qm隊(duì)列命中次數(shù)的降低,此差異的原因正如在3.1節(jié)中所預(yù)期的那樣:2Q*算法將q1.in隊(duì)列的管理方式由原先的FIFO方式改變?yōu)長RU方式后不僅沒有影響該算法在中、小緩存容量時(shí)對(duì)于活躍數(shù)據(jù)識(shí)別的有效性,而且在大緩存容量時(shí)有效降低了由強(qiáng)制識(shí)別失效所帶來的緩存性能開銷。如圖4(b)所示,2Q*算法在緩存容量為1.75GB時(shí)較經(jīng)典2Q算法緩存命中率提升約5%。此外,由圖5(b)和圖5(c)可以推斷在大緩存容量時(shí),2Q*算法中的緩存數(shù)據(jù)大都聚集于q1.in隊(duì)列中。顯然,在緩存容量與負(fù)載活躍數(shù)據(jù)集大小相當(dāng)時(shí),LRU是達(dá)成緩存效率最高的工作方式。4分區(qū)存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)方法為了驗(yàn)證2Q*在真實(shí)系統(tǒng)中的有效性,我們將它實(shí)現(xiàn)于Flexicache系統(tǒng)中。FlexiCache是一種針對(duì)存儲(chǔ)服務(wù)器設(shè)計(jì)的動(dòng)態(tài)分區(qū)緩存管理系統(tǒng),如第1節(jié)所述,它以應(yīng)用為單位將緩存資源劃分為不同的分區(qū),根據(jù)具體應(yīng)用負(fù)載特征,不同的緩存分區(qū)可以配置不同的局部替換算法,以提高分區(qū)緩存資源利用率。為了便于在FlexiCache中集成各種不同的替換算法,該系統(tǒng)在機(jī)制上提供了一種標(biāo)準(zhǔn)化的通用分區(qū)緩存管理接口。這樣,為了在FlexiCache系統(tǒng)中實(shí)現(xiàn)新的替換算法,只需要實(shí)現(xiàn)分區(qū)緩存管理接口中定義的各種緩存管理方法。然而具體替換算法中所使用的各種獨(dú)特的實(shí)現(xiàn)機(jī)制(如緩存元數(shù)據(jù)管理等)對(duì)于FlexiCache中其他子系統(tǒng)模塊是完全透明的。這種模塊化的設(shè)計(jì)方法不僅簡化了替換算法在FlexiCache中的實(shí)現(xiàn),同時(shí)有助于提高FlexiCache系統(tǒng)代碼的可維護(hù)性和可擴(kuò)展性。4.1存儲(chǔ)型緩沖系統(tǒng)的局部替換算法目前FlexiCache系統(tǒng)中的分區(qū)緩存管理接口定義了3種核心緩存管理方法。下面簡要介紹這3種方法所實(shí)現(xiàn)的緩存管理功能:Cache_Insertion方法將失效數(shù)據(jù)塊加入到應(yīng)用緩存分區(qū)中;Cache_Renewal更新命中數(shù)據(jù)塊在應(yīng)用緩存分區(qū)中的狀態(tài);Cache_Eviction從應(yīng)用緩存分區(qū)中替換出指定數(shù)量的空閑緩存塊。上述3種核心緩存管理方法實(shí)際上也就定義了FlexiCache系統(tǒng)中應(yīng)用分區(qū)的緩存管理模型。具體來說,當(dāng)緩存失效時(shí),從系統(tǒng)預(yù)留的空閑緩存池中分配所需的緩存塊;而當(dāng)緩存池中的空閑緩存塊數(shù)低于一定閾值時(shí),系統(tǒng)則相應(yīng)地從各個(gè)應(yīng)用分區(qū)中分別回收一定數(shù)量的空閑緩存塊。各應(yīng)用分區(qū)中具體應(yīng)替換出哪些緩存塊,取決于負(fù)責(zé)管理該應(yīng)用分區(qū)的局部替換算法。由此可知,Cache_Insertion和Cache_Renewal兩方法都是在應(yīng)用I/O線程的上下文中調(diào)用并分別用于處理緩存失效和緩存命中兩種情形;而Cache_Eviction方法是在系統(tǒng)緩存資源回收線程的上下文中調(diào)用。FlexiCache中的緩存管理模型與傳統(tǒng)替換算法設(shè)計(jì)時(shí)所基于的緩存管理模型之區(qū)別在于以下兩點(diǎn):1)緩存替換操作與緩存失效處理的分離;2)應(yīng)用分區(qū)緩存容量的動(dòng)態(tài)變化。為了將2Q*算法集成于FlexiCache系統(tǒng)中,需要對(duì)算法本身的處理邏輯做一定的修改,并相應(yīng)實(shí)現(xiàn)上述3種核心緩存管理方法。圖6以偽碼形式概要性地給出了2Q*算法在FlexiCache系統(tǒng)中的實(shí)現(xiàn)(這里忽略了實(shí)際系統(tǒng)實(shí)現(xiàn)時(shí)所作的優(yōu)化,如回寫和緩存數(shù)據(jù)同步等),其基本處理流程如下(注:本小節(jié)暫不討論與預(yù)取策略相關(guān)的處理邏輯):在2Q*_Insertion方法中,2Q*算法將在q1.out隊(duì)列中命中的失效數(shù)據(jù)加入qm隊(duì)列中,并標(biāo)記為活躍數(shù)據(jù)塊,反之加入q1.in隊(duì)列中。如圖6所示,我們用x.hot標(biāo)記x塊為活躍數(shù)據(jù);在2Q*_Renewal方法中,2Q*算法將命中數(shù)據(jù)塊重新移至所在隊(duì)列首;而在2Q*_Eviction方法中,2Q*算法首先根據(jù)應(yīng)用分區(qū)在回收操作完成后的實(shí)際緩存容量(tgrtblk=curblk-count)和算法預(yù)先設(shè)置的Klin參數(shù)值來調(diào)整q1.in隊(duì)列長度限制(limitq1.in=tgrtblk*Klin),接著根據(jù)當(dāng)前q1.in和qm兩隊(duì)列長度選擇應(yīng)從哪個(gè)隊(duì)列進(jìn)行回收,最后從隊(duì)尾開始遍歷所選擇的回收隊(duì)列并從中回收指定數(shù)目的緩存塊。4.2自適應(yīng)線性預(yù)取策略在實(shí)際緩存系統(tǒng)中,替換算法通常與預(yù)取策略相結(jié)合,以優(yōu)化應(yīng)用的I/O性能。其中替換算法可以利用I/O負(fù)載中的局部性原理來提高緩存效率,而預(yù)取則可以通過利用I/O負(fù)載中的相鄰請(qǐng)求間隙或思考時(shí)間(thinktime)來屏蔽慢速磁盤I/O對(duì)應(yīng)用I/O性能的影響。在FlexiCache系統(tǒng)中,我們采用默認(rèn)的自適應(yīng)線性預(yù)取策略,該策略不僅能夠在線探測(cè)緩存負(fù)載中潛在的順序訪問模式,同時(shí)能夠自適應(yīng)地調(diào)節(jié)預(yù)取的粒度和預(yù)取的時(shí)間。關(guān)于該策略的介紹可參考文獻(xiàn),這里僅討論2Q*算法如何在FlexiCache系統(tǒng)中與預(yù)取策略有機(jī)結(jié)合以進(jìn)一步提高應(yīng)用的I/O性能。如圖6所示,在2Q*_Insertion方法中,2Q*算法將預(yù)取數(shù)據(jù)不加區(qū)分(不考慮其是否活躍數(shù)據(jù))地統(tǒng)一加入至q1.in隊(duì)列中,它通過增加x.pref標(biāo)記來記錄x塊當(dāng)前是否為預(yù)取數(shù)據(jù)。且此時(shí)應(yīng)用分區(qū)中存在兩類緩存數(shù)據(jù),其中一類是應(yīng)用同步訪問數(shù)據(jù),另一部分為預(yù)取策略異步預(yù)取數(shù)據(jù)。在2Q*_renewal方法中,如果當(dāng)前緩存命中數(shù)據(jù)塊x為預(yù)取數(shù)據(jù),那么2Q*算法需要判斷其是否為活躍數(shù)據(jù),即x.hot標(biāo)記是否為真。如果是,那么數(shù)據(jù)塊x將被移至qm隊(duì)列首,反之亦然。5q#算法與預(yù)取策略的結(jié)合本節(jié)對(duì)2Q*算法在FlexiCache中的實(shí)現(xiàn)進(jìn)行性能評(píng)測(cè)。其中5.1節(jié)對(duì)比2Q*算法和包括經(jīng)典2Q在內(nèi)的其他3種替換算法在真實(shí)存儲(chǔ)系統(tǒng)中的性能;5.2節(jié)通過對(duì)比配置預(yù)取策略前后2Q*算法的性能差異來驗(yàn)證2Q*算法是否與預(yù)取策略有機(jī)地結(jié)合,以進(jìn)一步提升應(yīng)用的I/O性能;5.3節(jié)通過對(duì)比2Q*算法和LRU算法以及LinuxVFS緩存在順序讀寫模式下的聚合帶寬差異,來檢驗(yàn)2Q*算法在實(shí)際系統(tǒng)中的運(yùn)行開銷。在討論上述3種性能評(píng)測(cè)結(jié)果之前,首先給出測(cè)試所基于的硬軟件實(shí)驗(yàn)環(huán)境。測(cè)試中使用的存儲(chǔ)服務(wù)器的硬軟件配置如表2所列,其中4塊西捷250GB的SATA磁盤通過3WareRAID控制器按每兩個(gè)一組以RAID0方式構(gòu)成兩個(gè)存儲(chǔ)卷。使用的測(cè)試工具包括xdd和kernio兩種,其中前者是一種運(yùn)行于用戶態(tài)的磁盤測(cè)試工具,后者為運(yùn)行于內(nèi)核空間的塊級(jí)I/O負(fù)載回放器,它能夠統(tǒng)計(jì)諸如平均響應(yīng)延遲、每秒操作數(shù)和磁盤負(fù)載等多種I/O性能參數(shù)指標(biāo)。5.1基于arc的傳遞特性測(cè)試本小節(jié)通過對(duì)比郵件服務(wù)負(fù)載在FlexiCache系統(tǒng)中的不同替換算法配置下實(shí)測(cè)得到的平均響應(yīng)延遲來驗(yàn)證2Q*算法在實(shí)際存儲(chǔ)系統(tǒng)中的有效性。作為比較,在FlexiCache系統(tǒng)中實(shí)現(xiàn)了LRU,2Q,ARC和2Q*等4種替換算法。測(cè)試中利用kernio工具通過FlexiCache緩存向物理存儲(chǔ)卷回放郵件服務(wù)負(fù)載并統(tǒng)計(jì)回放得到的平均響應(yīng)延遲。圖7給出了第5號(hào)郵件服務(wù)器的實(shí)驗(yàn)結(jié)果(注:其他負(fù)載的實(shí)驗(yàn)結(jié)果相似。此外由于受硬件資源所限,測(cè)試的最大緩存容量為1.25GB,但這并不影響性能分析的有效性)。如圖所示,2Q*算法在各種緩存容量下均優(yōu)于包括經(jīng)典2Q算法在內(nèi)的其他3種替換算法,該算法可降低負(fù)載平均響應(yīng)延遲最大約達(dá)20%(如1GB緩存容量時(shí)的ARC和2Q算法,0.75GB容量時(shí)的LRU算法)。實(shí)際系統(tǒng)中的實(shí)驗(yàn)結(jié)果進(jìn)一步驗(yàn)證了2Q*算法在模擬實(shí)驗(yàn)中對(duì)于郵件服務(wù)負(fù)載所表現(xiàn)出的良好性能。5.2預(yù)取策略下的性能比較本小節(jié)測(cè)試的目的在于檢驗(yàn)自適應(yīng)順序預(yù)取策略對(duì)于2Q*算法性能的影響,即2Q*算法是否能夠有效地與順序預(yù)取策略相結(jié)合以進(jìn)一步提升應(yīng)用的I/O性能。由于本文測(cè)試中使用的磁盤子系統(tǒng)性能低于負(fù)載采集系統(tǒng)中的磁盤子系統(tǒng)性能,因此我們將相鄰請(qǐng)求間的時(shí)隙擴(kuò)大原始負(fù)載中的4倍,這樣可有利于發(fā)揮預(yù)取策略對(duì)于慢速磁盤I/O延遲的屏蔽作用。圖8給出了第5號(hào)郵件服務(wù)器負(fù)載的實(shí)驗(yàn)結(jié)果(注:其他負(fù)載的實(shí)驗(yàn)結(jié)果類似)。其中圖8(a)對(duì)比了2Q*算法在有無預(yù)取兩種情形下的I/O性能。如圖所示,在結(jié)合預(yù)取策略后,負(fù)載平均響應(yīng)延遲在各種緩存容量下均得到了降低,約為5%左右。圖8(b)相應(yīng)給出了預(yù)取窗口大小隨時(shí)間變化的分布。由圖可知,在負(fù)載回放過程中預(yù)取窗口大小穩(wěn)定在32kB～64kB左右(相當(dāng)于8～16個(gè)緩存塊)。而由表1可知,郵