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

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

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

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

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