離線下載緩存替換算法.pdf

1、數(shù)據(jù)下載是人們獲取信息的一種重要方式;近年來新興的離線下載業(yè)務(wù)吸引了大量用戶。與傳統(tǒng)下載應(yīng)用不同，在離線下載系統(tǒng)中，用戶先向系統(tǒng)提交文件下載請(qǐng)求;然后，離線下載的服務(wù)器代替用戶從網(wǎng)絡(luò)中下載文件并存儲(chǔ)在離線下載系統(tǒng)的緩存中;最后，用戶再從緩存云中下載文件。這種設(shè)計(jì)，可以節(jié)省終端用戶的時(shí)間和資源，給用戶帶來更好的下載體驗(yàn)。
　　離線下載系統(tǒng)的核心部件是緩存服務(wù)器，緩存算法是決定緩存服務(wù)器性能的關(guān)鍵?，F(xiàn)有系統(tǒng)一般采用傳統(tǒng)的算法，如LRU

2、、LFU，這些算法并沒有考慮離線下載業(yè)務(wù)的特殊性;隨著離線下載日益普及和文件數(shù)量增長(zhǎng)，緩存和帶寬資源都面臨壓力。因此，需要尋找高效的緩存方法，充分利用有限的緩存空間，保障系統(tǒng)服務(wù)質(zhì)量。
　　離線下載系統(tǒng)中，用戶的請(qǐng)求時(shí)間和下載時(shí)間不同，二者往往存在時(shí)間間隔。我們稱這個(gè)間隔為預(yù)約時(shí)間。預(yù)約時(shí)間為我們提供了設(shè)計(jì)新的緩存算法的空間。由于下載是預(yù)約的，因此在每次緩存調(diào)度發(fā)生時(shí)，我們能夠獲知未來一段時(shí)間，還有哪些下載任務(wù)有待完成。因此，可以

3、將預(yù)約信息用于緩存設(shè)計(jì)，以提高緩存效率。
　　本文的主要工作是，針對(duì)離線下載的業(yè)務(wù)特征，尋找高效的緩存算法，減輕緩存的存儲(chǔ)壓力和帶寬開銷，提高系統(tǒng)性能。具體來說，本文的主要工作和貢獻(xiàn)如下:
　　(1)針對(duì)離線下載業(yè)務(wù)特征，提出了基于預(yù)約信息的緩存設(shè)計(jì)思想。該思想充分利用可用的預(yù)約信息和訪問歷史信息，提高字節(jié)命中率。在此基礎(chǔ)上，提出了兩種新的緩存算法，一種是基于文件預(yù)約信息和訪問歷史信息中的訪問頻率，一種是基于文件預(yù)約信息和訪

4、問歷史信息中的訪問時(shí)間間隔。分析了算法參數(shù)的設(shè)計(jì)依據(jù)并權(quán)衡了可能的取值范圍。
　　(2)基于真實(shí)的離線下載業(yè)務(wù)數(shù)據(jù)，進(jìn)行了不同緩存算法的比較和評(píng)估。結(jié)果顯示，相比傳統(tǒng)算法，本文提出的兩種緩存替換算法都可以提高字節(jié)命中率。尤其在緩存較小的時(shí)候，效果更明顯，字節(jié)命中率最高可以提高7.78％。
　　(3)最后，本文從理論上分析LRU算法的性能，建立了基于馬爾科夫鏈的數(shù)學(xué)模型。模型可以計(jì)算每個(gè)文件的命中率。模型的特色在于把單個(gè)文件在