一種基于websearch的緩存替換算法

一種基于websearch的緩存替換算法

1緩沖系統(tǒng)性能分析隨著信息總量的迅速增加，如何獲得有效信息已成為人們關(guān)注的問題。隨著大量搜索的出現(xiàn)，以適應(yīng)搜索系統(tǒng)的存儲系統(tǒng)也必須發(fā)揮更高的性能。存儲系統(tǒng)是有效加快系統(tǒng)性能的一般技術(shù)之一，對存儲系統(tǒng)的性能產(chǎn)生了重大影響。對于搜索系統(tǒng)的后段存儲系統(tǒng)來說，內(nèi)存作為存儲它通常被視為訪問頻繁訪問的內(nèi)容。然而，在研究中，對于web搜索負(fù)荷，經(jīng)典的存儲替換方法顯示了非常糟糕的適用性。如圖1所示，當(dāng)搜索結(jié)果的web輸入系統(tǒng)使用lru或lfu的命中率曲線時，這兩個算法顯示出非常差的性能。對于web搜索應(yīng)用程序，這兩個算法顯示出非常差的性能。當(dāng)容量小于1g時，這兩個算法的命中率僅為15%。顯然，低效存儲反應(yīng)計算法不能滿足搜索應(yīng)用對存儲系統(tǒng)的要求。在本文中，我們總結(jié)了負(fù)載訪問模式的特點，并在此基礎(chǔ)上設(shè)計了一種新的替換算法erd-lru。通過模擬和實踐驗證其有效性。2web確定方法在網(wǎng)絡(luò)改造中,同時進(jìn)行了改變信息的調(diào)整,節(jié)約政府?dāng)?shù)據(jù)的資源和服務(wù),提高了網(wǎng)絡(luò)服務(wù)質(zhì)量.大量文獻(xiàn)已廣泛研究了緩存替換算法,如LRU、LFU、MRU、2Q、ARC等.對于web應(yīng)用方面,Cao使用基于費用的貪心算法,為每一個緩存中的web文檔賦予一個H值,緩存中的每個文檔都和一個價位H關(guān)聯(lián);當(dāng)發(fā)生替換時,選擇H值最小的web文檔替換出去,并將所有的文檔的H值減去這個最小的H值.Williams利用了web靜態(tài)頁面的大小分布特性,即用戶傾向于訪問較小的web文檔,在替換發(fā)生時將最大的文檔替換出去.Rizzo通過考慮獲取文檔的代價、文檔的大小,并利用對web代理訪問日志的分析,計算文檔下一次或一段時間后被訪問的概率,并利用這個概率值作為替換的依據(jù).Wooster使用訪問web文檔的延遲作為替換的標(biāo)準(zhǔn),并兼顧了文檔的訪問頻率和大小.尤采用分塊緩存技術(shù)管理動態(tài)網(wǎng)頁,降低了緩存分配和替換的粒度,提高了數(shù)據(jù)的命中率.李通過在網(wǎng)絡(luò)節(jié)點上采用區(qū)分服務(wù)的方法,把服務(wù)分成有保證和無保證兩類,在發(fā)生數(shù)據(jù)替換時,首先替換無保證類服務(wù)的數(shù)據(jù),從而提高了網(wǎng)絡(luò)服務(wù)質(zhì)量.Konanki已經(jīng)指出單一的替換算法不能滿足各種不同應(yīng)用的需要;本文中,借鑒此結(jié)論,提出了適合websearch應(yīng)用的緩存替換算法.3訪問負(fù)荷的模式分析我們從時間局部性和訪問頻率兩個角度來分析應(yīng)用的訪問模式.表1給出了負(fù)載文件的參數(shù).3.1關(guān)聯(lián)訪問的分辨率使用重用距離(reuseddistance)來分析時間局部性.重用距離是指給定訪問序列中對同一塊的相鄰兩次訪問間距,訪問序列是指按訪問時間先后次序排列的請求隊列.例如,在訪問序列A1B2C3D4E5C6F7中,對塊C的兩次關(guān)聯(lián)訪問(C3和C6)的重用距離為2,這其中我們稱對同一塊的相鄰兩次訪問為關(guān)聯(lián)訪問.圖2給出了3種負(fù)載的重用距離分布,展示了重用距離相同的關(guān)聯(lián)訪問總量分布.從圖中我們可以看出,三種負(fù)載的重用距離分布表現(xiàn)為”小山形”.websearch1的關(guān)聯(lián)訪問的重用距離峰值出現(xiàn)在100K處左右;而另外兩種負(fù)載的峰值出現(xiàn)在16K處左右.據(jù)統(tǒng)計,有超過70%的關(guān)聯(lián)訪問出現(xiàn)在“小山形”區(qū)域.我們定義“小山形”的起始位置為最小距離(MinDist).由于大量的關(guān)聯(lián)訪問出現(xiàn)在了“小山形”區(qū)域內(nèi),理想替換算法應(yīng)該使得“小山形”區(qū)域內(nèi)的塊在緩存中至少駐留MinDist的虛擬緩存時間.對于LRU算法:當(dāng)容量小于MinDist時,絕大多數(shù)“小山形”區(qū)域內(nèi)的塊在緩存中駐留時間不足以等到其下一次被訪問,從而表現(xiàn)出很低的性能.3.2負(fù)載訪問頻率從訪問頻率角度來分析負(fù)載.塊的訪問頻率是在給定訪問序列中,對同一塊的總的訪問次數(shù).圖3顯示了3種負(fù)載的塊訪問頻率累積分布,其中x軸為塊訪問頻率,而y軸為具有相同頻率的塊總和.可以看出,負(fù)載中的數(shù)據(jù)塊訪問頻率普遍較低;且相同頻率的數(shù)據(jù)塊總和隨訪問頻率的增加而顯著下降.對于每種負(fù)載,通過統(tǒng)計我們發(fā)現(xiàn)超過80%的塊的訪問頻率小于10;而對這些塊的訪問占了總訪問的70%.這表明訪問頻率分布是比較均勻的.因此,由于訪問頻率不能有效區(qū)分熱塊和冷塊,LFU也不能提供很好的性能.此外,值得注意的是每種負(fù)載中約有30%的塊只被訪問過1次.定義重引用頻率(re-referencefrequency)為給定訪問序列中對同一塊的重復(fù)訪問次數(shù).研究重用距離與重引用頻率的關(guān)系.例如,對于序列A1C2B3A4C5A6D7C8,A4是對A的第1次重訪問,其重引用頻率是1,重用距離是2.A6是對A的第2次重訪問,其重引用頻率是2,重用距離是1.在重引用頻率固定條件下,計算平均重用距離(averagereuseddistance).例如,當(dāng)重引用頻率是1(A4和C5)時,其平均重用距離是2,即((2+2)/2).圖4顯示了平均重用距離和重引用頻率的關(guān)系.可知,隨重引用頻率的增長,平均重用距離迅速降低.這表明,重用頻率相對較高的訪問具有相對較小的重用距離.假設(shè)對A的第n次訪問的重用距離是distn,可以預(yù)測對A的第n+1次訪問的重用距離distn+1<distn.根據(jù)以上分析,總結(jié)負(fù)載訪問模式的特點:(1)關(guān)聯(lián)訪問的重用距離大;(2)塊的訪問頻率小,并存在大量只訪問1次的塊;(3)塊的訪問頻率呈均勻分布;(4)重用距離和重引用頻率之間具有反比關(guān)系.依據(jù)這4個特點設(shè)計一個更有效的替換算法.4傳統(tǒng)熱法布局式的布局特點基于負(fù)載的訪問模式,設(shè)計了一種新的替換算法——ERDP-LRU(LRUextendedwithreuseddistancebasedplacement).其基本思想如下:區(qū)分冷熱塊,并根據(jù)塊的冷熱采取不同的放置策略.具體說,緩存塊被組織為一個LRU隊列(標(biāo)記為Q)統(tǒng)一集中管理.當(dāng)一個塊被訪問時,根據(jù)重用距離來識別塊的冷熱,并采用不同的放置策略.該算法與LRU的替換策略相同,主要區(qū)別在于:它采用了基于重用距離的緩存放置策略,而不是傳統(tǒng)的按需訪問放置策略.圖5給出了算法的偽碼描述,其中G為虛緩存隊列(見下一節(jié)),K為預(yù)置虛緩存最大值.4.1確定失效訪問的類型對塊訪問的冷熱進(jìn)行定義.冷訪問:此前從未被訪問或重用距離超過實際緩存容量大小的訪問.熱訪問:重用距離小于實際緩存容量大小的訪問.為了有效的區(qū)分失效訪問類型,ERDP-LRU利用了虛擬緩存技術(shù)(ghostbuffer).將虛緩存標(biāo)記為G隊列,其記錄了最近被替換丟棄塊的相對訪問次序,其管理方式為FIFO.G隊列中的每個隊列元素僅記錄了塊的ID(存儲空間中的地址偏移量),并不存儲真實數(shù)據(jù).具體來說:(1)若失效訪問塊的ID在G中,則我們認(rèn)為該失效訪問為熱訪問,被訪問的失效塊為熱塊;(2)反之,則認(rèn)為該失效訪問為冷訪問,被訪問的失效塊為冷塊.4.2添加納入負(fù)載的冷塊當(dāng)一個塊被訪問,通過區(qū)分冷熱,采用不同的放置策略.具體如下:緩存預(yù)熱階段:失效塊被添至Q隊列的LRU端.緩存穩(wěn)定階段:失效塊被識別為熱塊,添至Q隊列MRU端;失效塊被識別為冷塊,添至Q隊列的LRU端.基于對訪問模式分析可知,算法的放置策略有以下兩個優(yōu)點:(1)通過把冷塊放置在隊列的LRU端,可以加快冷塊被替換的概率和速率;從而可避免大量一次訪問塊對有限緩存空間的污染(據(jù)特點(1)+(2));(2)通過區(qū)分負(fù)載訪問中的冷熱塊,并只允許熱塊加至隊列的MRU端,可以有效提高緩存空間利用率(據(jù)特點(1)+(4)).首先,負(fù)載中關(guān)聯(lián)訪問的重用距離較大,將下一次訪問重用距離超過緩存容量的塊添加至緩存將不會帶來命中;其次,對于同一塊的關(guān)聯(lián)訪問,其下一次訪問的重用距離通常小于其前一次.將識別出的熱塊加入緩存是有益的:若失效塊的重用距離小于緩存容量,可推測對此塊的下一次訪問間距很可能也小于緩存容量.除了不同的放置策略外,ERDP-LRU仍沿用LRU替換策略.其依據(jù)為:緩存進(jìn)入穩(wěn)定狀態(tài)后,冷塊聚集在隊列的LRU端附近,可以加速冷塊的替換;而熱塊聚集在隊列的MRU端附近,且重用距離很可能小于緩存容量,有利于減少熱塊被替換的概率.4.3負(fù)載的局部性來提高緩沖效率在實際系統(tǒng)中,替換算法通常與預(yù)取策略結(jié)合以優(yōu)化應(yīng)用的性能.前者利用負(fù)載的局部性來提高緩存效率;后者利用請求間隙來屏蔽慢速設(shè)備對性能的影響.這里并不關(guān)注具體的預(yù)取策略,而僅討論算法如何與預(yù)取策略有機結(jié)合.通過x.pref標(biāo)記塊x是否是預(yù)取塊,具體流程如圖6所示.5實驗評估5.1erdp-lru算法性能本節(jié)給出了ERDP-LRU和其它算法(LRU、MRU、LFU、2Q和ARC)的模擬結(jié)果.如圖7所示,ERDP-LRU在各種緩存容量下的性能均優(yōu)于其它算法,其命中率在測試范圍內(nèi)隨容量的增長而穩(wěn)步上升.5.2真實系統(tǒng)性能測試將ERDP-LRU集成到一個真實的緩存系統(tǒng)Flexi-Cache中,評價其在真實系統(tǒng)中的性能.首先,驗證ERDP-LRU的模擬結(jié)果,為了便于比較,也實現(xiàn)了LRU,2Q和ARC算法.其次,測試算法與預(yù)取結(jié)合的效果.5.2.1race文件測試配置見表2,2塊磁盤以RAID0方式向系統(tǒng)提供一個條帶卷1.使用的trace是從某門戶網(wǎng)絡(luò)搜索引擎的后端存儲系統(tǒng)中搜集得到,其格式遵循SPC-1標(biāo)準(zhǔn).其中每一條記錄指出了訪問偏移塊號、訪問長度、訪問模式(讀或?qū)?、訪問間隔時間等.使用回放工具——Kernio,進(jìn)行回放trace文件.5.2.2算法的有效性驗證以平均響應(yīng)時間為評價指標(biāo).如圖8所示,相對于其它算法,ERDP-LRU有效的減少了平均響應(yīng)時間.當(dāng)容量為1.25GB時,ERDP-LRU相對于LRU最大提高17%(websearch2),平均提高14%.根據(jù)模擬結(jié)果,隨著容量的增長,其它算法和ERDP-LRU的性能差距將增大.實驗結(jié)果驗證了算法在真實系統(tǒng)中的有效性.5.2.3預(yù)取窗口對比在Flexi-Cache中,采用自適應(yīng)線性預(yù)取策略.本節(jié)檢驗算法是否能有效地與預(yù)取策略相結(jié)合以進(jìn)一步提升性能.圖9給出了websearch2的結(jié)果(其它負(fù)載結(jié)果類似),其中圖9(a)對比了算法在有無預(yù)取兩種情形下的性能;在結(jié)合預(yù)取策略后,平均響應(yīng)延遲在各種容量下均得到降低,約為7.7%.圖9(b)給出了預(yù)取窗口隨時間變化分布,其大小在回放過程中穩(wěn)定在28～68KB左右(相當(dāng)于7～17個緩存塊);根據(jù)表1,負(fù)載的平均請求大小僅為15KB左右,由此可知,算法在結(jié)合預(yù)取策略后通過提前從磁盤中讀取已探測到的順序訪問序列,并利用請求間隙盡可能屏蔽慢速磁盤對負(fù)載回放性能的影響.結(jié)果表明,ERDP-LRU在與預(yù)取策略結(jié)合后可以進(jìn)一步提高