一種基于文件預(yù)測(cè)的分布式緩存模型

張勝利，陳莉君

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安710061)

近年來，數(shù)據(jù)成爆炸式增長(zhǎng)，傳統(tǒng)存儲(chǔ)方式已無法滿足數(shù)據(jù)增長(zhǎng)速度的要求，在此現(xiàn)狀下，分布式存儲(chǔ)技術(shù)得到了快速發(fā)展。限于成本與科技等原因，多數(shù)分布式存儲(chǔ)都是利用大量廉價(jià)PC搭建而成[1]，與傳統(tǒng)的單機(jī)存儲(chǔ)一樣，在分布式存儲(chǔ)系統(tǒng)中I/O也是制約其整體性能的一個(gè)瓶頸，因此相繼提出了分布式緩存系統(tǒng)。

典型的分布式緩存系統(tǒng)如 Oracle coherence[2]、Memcached[3]、Terracotta[4]，在彈性資源供給、可用性與可靠性、敏捷性與自適應(yīng)性、多承租、數(shù)據(jù)管理、數(shù)據(jù)安全與隱私等方面已設(shè)計(jì)得較為完善，同時(shí)也有其不足之處：對(duì)數(shù)據(jù)的遷移是以容量均衡為目標(biāo)而缺少對(duì)熱點(diǎn)數(shù)據(jù)的處理；訪問頻率低的客戶端緩存數(shù)據(jù)被換出導(dǎo)致資源劫持等[5]。

熱點(diǎn)數(shù)據(jù)不均衡造成服務(wù)器之間接收到訪問請(qǐng)求的不均衡，而客戶的行為也有時(shí)間局域性，例如工作時(shí)間訪問工作相關(guān)數(shù)據(jù)多，非工作時(shí)間訪問娛樂數(shù)據(jù)多，這導(dǎo)致服務(wù)器收到的訪問請(qǐng)求在時(shí)間上分布不平坦。預(yù)取可改善系統(tǒng)I/O的兩個(gè)主要性能指標(biāo)[6]：利用異步預(yù)取在程序使用文件之前將文件準(zhǔn)備就緒，可對(duì)應(yīng)用程序隱藏磁盤I/O延時(shí)；在服務(wù)器空閑時(shí)間使用預(yù)取可以提升服務(wù)器的使用率。

數(shù)據(jù)的訪問請(qǐng)求并非完全隨機(jī)，它是由用戶或程序的行為驅(qū)動(dòng)，存在特定的訪問模式。當(dāng)用戶執(zhí)行程序訪問數(shù)據(jù)時(shí)，連續(xù)訪問的一系列數(shù)據(jù)之間必然存在一定的關(guān)聯(lián)[7]，因此在客戶端構(gòu)建文件預(yù)測(cè)模型對(duì)將要使用的文件進(jìn)行異步預(yù)取是可以實(shí)現(xiàn)的。為此提出了一種基于文件預(yù)測(cè)的分布式緩存模型DLSDCM(DLS based Distributed Cache Model)，在客戶端建立由經(jīng)典的文件預(yù)測(cè)模型LS(Last Successor)改進(jìn)而成的文件預(yù)測(cè)模型DLS(Double Last Successor)，并利用服務(wù)器的空閑時(shí)間進(jìn)行預(yù)測(cè)請(qǐng)求數(shù)據(jù)的傳輸。此模型建立在其他分布式緩存系統(tǒng)之上，完善其資源劫持、熱點(diǎn)數(shù)據(jù)分布不均衡等方面,同時(shí)也可作為單獨(dú)的緩存模型使用。

1 文件預(yù)測(cè)模型

數(shù)據(jù)的訪問請(qǐng)求并非完全隨機(jī)，它是由用戶或程序的行為驅(qū)動(dòng)，用戶執(zhí)行某種應(yīng)用程序去訪問數(shù)據(jù)，連續(xù)訪問的不同文件之間必然存在一定的關(guān)聯(lián)。可構(gòu)造出一種文件預(yù)測(cè)模型，通過對(duì)數(shù)據(jù)本體間的內(nèi)在聯(lián)系或者歷史訪問記錄進(jìn)行分析并構(gòu)造出預(yù)測(cè)數(shù)據(jù)庫，依據(jù)預(yù)測(cè)數(shù)據(jù)對(duì)預(yù)測(cè)文件進(jìn)行異步預(yù)讀并緩存。當(dāng)應(yīng)用程序使用這些數(shù)據(jù)時(shí)，便可大幅度減少數(shù)據(jù)的訪問延時(shí)，同時(shí)也減少了服務(wù)器空閑時(shí)間，提升了網(wǎng)絡(luò)使用率。本文主要研究LS預(yù)測(cè)模型。

1.1 LS文件預(yù)測(cè)模型

當(dāng)用戶訪問一系列數(shù)據(jù)時(shí)，或多或少會(huì)重復(fù)上一次的訪問順序，因此LS模型是最常用也是最簡(jiǎn)單的文件預(yù)測(cè)模型，被多數(shù)預(yù)測(cè)系統(tǒng)采用。Linux內(nèi)核采用的預(yù)取算法亦是根據(jù)上次及本次的讀請(qǐng)求進(jìn)行順序模式的匹配[8]。

但是LS文件預(yù)測(cè)模型在交替訪問文件時(shí)就會(huì)完全失效，例如第一次訪問順序?yàn)槲募?A、文件 B；第二次訪問順序?yàn)槲募嗀、文件I；第三次又重復(fù)第一次順序?yàn)槲募嗀、文件B。對(duì)于這樣的交替訪問，使用LS模型預(yù)測(cè)文件A的后繼則完全失效。若將預(yù)測(cè)的文件數(shù)擴(kuò)大為2個(gè)，即對(duì)于每個(gè)文件同時(shí)預(yù)讀其上一次訪問的后繼文件和上上一次訪問的后繼文件，則可避免交替訪問的預(yù)測(cè)失效，據(jù)此本文提出了DLS文件預(yù)測(cè)模型。

1.2 DLS文件預(yù)測(cè)模型

DLS文件預(yù)測(cè)模型一次可預(yù)測(cè)2個(gè)文件：上次訪問順序中的后繼和上上次訪問順序的后繼，預(yù)測(cè)命中的概率將會(huì)有很大提高。圖1所示為DLS模型對(duì)文件A后繼的預(yù)測(cè)，圖中文件 A、B、I、U、D代表獨(dú)立的文件，而非順序文件。

圖1 DLS文件預(yù)測(cè)模型

由于一次預(yù)測(cè)2個(gè)文件，因此數(shù)據(jù)傳輸時(shí)也會(huì)有2個(gè)文件同時(shí)傳輸，參考使用概率圖來預(yù)測(cè)未來文件訪問的文件預(yù)測(cè)模型[9]，分別記錄文件B和文件I的預(yù)測(cè)命中次數(shù)，并依命中次數(shù)來決定兩個(gè)文件傳輸時(shí)各自占用的帶寬比例，例如，記錄中文件B命中了40次，文件 I命中了60次，此時(shí)文件B占40%帶寬，文件I占60%的帶寬比例進(jìn)行傳輸。

1.3 LS和DLS兩種文件預(yù)測(cè)模型對(duì)比

文件預(yù)測(cè)模型很多，每種預(yù)測(cè)模型都有其最適用的環(huán)境。下面從理論上對(duì)比LS文件預(yù)測(cè)模型和DLS文件預(yù)測(cè)模型在DLSDCM中的適用性。以圖1為例對(duì)比LS文件預(yù)測(cè)模型和DLS文件預(yù)測(cè)模型的命中率和有效使用率：假設(shè)文件B和文件I命中率都是20%，文件B和文件I的大小均為1 MB。表1為服務(wù)器I/O空閑不大于傳輸1 MB數(shù)據(jù)所用時(shí)間的情況。

表1為使用LS文件預(yù)測(cè)模型和DLS文件預(yù)測(cè)模型的有效傳輸數(shù)據(jù)量相同，但是使用DLS文件預(yù)測(cè)模型卻有40%的概率傳輸有效數(shù)據(jù)，即在服務(wù)器I/O空閑小于等于傳輸1 MB數(shù)據(jù)時(shí)間的情況下，DLS文件預(yù)測(cè)模型與LS文件預(yù)測(cè)模型相比優(yōu)勢(shì)在于穩(wěn)定性高。表2為服務(wù)器I/O空閑可傳輸2 MB數(shù)據(jù)時(shí)的情況。

表1 DLS與LS對(duì)比1

表2為兩種模型的預(yù)測(cè)命中率不變，DLS文件預(yù)測(cè)模型總傳輸數(shù)據(jù)量和有效傳輸數(shù)據(jù)量均為L(zhǎng)S文件預(yù)測(cè)模型的2倍。由于DLSDCM是使用空閑網(wǎng)絡(luò)時(shí)間進(jìn)行數(shù)據(jù)的預(yù)傳輸，并不占用必要讀請(qǐng)求數(shù)據(jù)的傳輸時(shí)間，因此服務(wù)器I/O空閑大于空閑臨界值(傳輸LS預(yù)測(cè)文件全部數(shù)據(jù)的時(shí)間)時(shí)，DLS文件預(yù)測(cè)模型相對(duì)于LS文件預(yù)測(cè)模型有較大的優(yōu)勢(shì)。

表2 DLS與LS對(duì)比2

由此可見，在DLSDCM中DLS文件預(yù)測(cè)模型較之LS文件預(yù)測(cè)模型在服務(wù)器I/O空閑不大于空閑臨界值時(shí)，具有命中穩(wěn)定性高的優(yōu)勢(shì)；而當(dāng)在服務(wù)器I/O空閑大于空閑臨界值時(shí)，DLS文件預(yù)測(cè)模型優(yōu)勢(shì)就逐漸明顯，這個(gè)優(yōu)勢(shì)在服務(wù)器空閑時(shí)間足夠傳輸DLS文件預(yù)測(cè)模型所預(yù)測(cè)的兩個(gè)文件時(shí)達(dá)到最大。

2 DLSDCM設(shè)計(jì)原理

2.1 緩存模型理論基礎(chǔ)

緩存是傳輸速率相差較大的兩種實(shí)體(硬件或軟件)之間的存儲(chǔ)區(qū)域，用于存儲(chǔ)低速實(shí)體中的熱點(diǎn)數(shù)據(jù)或預(yù)讀數(shù)據(jù)，以提升系統(tǒng)的反應(yīng)速度[10]。

傳統(tǒng)的緩存模型是在程序請(qǐng)求訪問數(shù)據(jù)之后將數(shù)據(jù)緩存，基于數(shù)據(jù)使用的時(shí)間局域性，當(dāng)再次使用數(shù)據(jù)時(shí)便可降低訪問延時(shí)，這種策略屬于被動(dòng)式緩存。使用預(yù)取技術(shù)在程序請(qǐng)求訪問數(shù)據(jù)之前將其讀入，如果預(yù)測(cè)命中則將預(yù)讀數(shù)據(jù)交由系統(tǒng)緩存管理(以下“緩存”指DLSDCM預(yù)讀緩存，而“系統(tǒng)緩存”指支撐DLSDCM的分布式存儲(chǔ)系統(tǒng)緩存或分布式緩存系統(tǒng)緩存)，這屬于主動(dòng)式緩存。主動(dòng)式緩存填充了程序請(qǐng)求訪問數(shù)據(jù)之前的空白時(shí)間，對(duì)于服務(wù)器有空閑時(shí)間的情況，是一個(gè)提升服務(wù)器使用率的策略，對(duì)于客戶端來說可降低其請(qǐng)求數(shù)據(jù)的訪問延時(shí)。

2.2 DLSDCM的架構(gòu)

DLSDCM是基于客戶端數(shù)據(jù)訪問請(qǐng)求可以預(yù)測(cè)和服務(wù)器收到數(shù)據(jù)訪問請(qǐng)求在時(shí)間軸上非平坦分布這兩個(gè)前提來構(gòu)建的。在客戶端建立DLS預(yù)測(cè)模型，在服務(wù)器端增添一個(gè)預(yù)讀請(qǐng)求隊(duì)列并默認(rèn)調(diào)度優(yōu)先級(jí)低于I/O請(qǐng)求隊(duì)列，以達(dá)到預(yù)讀數(shù)據(jù)的傳輸在服務(wù)器I/O的空閑時(shí)間進(jìn)行，提升服務(wù)器使用效率[11]的目的（此處亦留下接口可手動(dòng)修改優(yōu)先權(quán)，調(diào)整特定客戶端優(yōu)先級(jí)）。DLSDCM建立在分布式存儲(chǔ)系統(tǒng)或分布式緩存系統(tǒng)之上，其緩存模型如圖2所示。

圖2 DLSDCM緩存模型

3 DLSDCM的實(shí)現(xiàn)

DLSDCM的實(shí)現(xiàn)分為客戶端的實(shí)現(xiàn)和服務(wù)器端的實(shí)現(xiàn)?？蛻舳私LS預(yù)測(cè)模型，使用DLS預(yù)測(cè)模型維護(hù)一份預(yù)測(cè)數(shù)據(jù)和一份高訪問頻率文件記錄，每次讀請(qǐng)求發(fā)生時(shí)，通過查詢預(yù)測(cè)數(shù)據(jù)對(duì)讀請(qǐng)求文件所對(duì)應(yīng)的預(yù)讀文件進(jìn)行異步預(yù)讀請(qǐng)求操作；高訪問頻率文件記錄作為預(yù)留接口為熱點(diǎn)數(shù)據(jù)遷移提供熱點(diǎn)數(shù)據(jù)信息[12]（此功能尚在開發(fā)中）；每個(gè)客戶端在本地維護(hù)一個(gè)預(yù)讀緩存，在本地磁盤維護(hù)一個(gè)緩存目錄。服務(wù)器端維護(hù)調(diào)度預(yù)讀請(qǐng)求隊(duì)列并默認(rèn)預(yù)讀請(qǐng)求隊(duì)列調(diào)度優(yōu)先級(jí)低于I/O請(qǐng)求隊(duì)列，響應(yīng)客戶端發(fā)送的預(yù)讀相關(guān)的請(qǐng)求信號(hào)。

3.1 DLSDCM客戶端的實(shí)現(xiàn)

DLSDCM客戶端在每次讀請(qǐng)求發(fā)生時(shí)，根據(jù)DLS文件預(yù)測(cè)模型所預(yù)測(cè)的數(shù)據(jù)向服務(wù)器發(fā)出預(yù)測(cè)文件的異步預(yù)讀請(qǐng)求，并將過大的預(yù)讀數(shù)據(jù)存儲(chǔ)于本地磁盤。參考Linux內(nèi)核的預(yù)取算法，其維護(hù)了兩種類型的狀態(tài)量：讀歷史和預(yù)讀歷史，在DLS預(yù)測(cè)模型中使用鏈表記錄文件讀歷史，而每個(gè)文件所對(duì)應(yīng)的節(jié)點(diǎn)又包含了節(jié)點(diǎn)文件所對(duì)應(yīng)的預(yù)讀文件和預(yù)讀命中次數(shù)；使用數(shù)組記錄高頻率訪問的文件及訪問次數(shù)，留作熱點(diǎn)數(shù)據(jù)遷移備用接口?？蛻舳私Y(jié)構(gòu)如圖3所示。

每次讀請(qǐng)求操作首先檢查DLS預(yù)測(cè)數(shù)據(jù)是否有對(duì)應(yīng)文件節(jié)點(diǎn)，再分別檢查緩存和系統(tǒng)緩存中是否有對(duì)應(yīng)文件，而后再次檢查緩存和系統(tǒng)緩存中是否有預(yù)讀文件，最后再將讀請(qǐng)求文件信息寫入DLS。一次讀請(qǐng)求的流程圖如圖4所示。

當(dāng)服務(wù)器空閑時(shí)間足夠、預(yù)讀文件大小超過預(yù)讀緩存容量時(shí)，執(zhí)行將預(yù)讀文件寫入本地磁盤緩存目錄的操作。緩存與磁盤緩存目錄文件保留至下一次預(yù)讀寫操作。

3.2 DLSDCM服務(wù)器端的實(shí)現(xiàn)

服務(wù)器端主要負(fù)責(zé)響應(yīng)客戶端的預(yù)讀請(qǐng)求信號(hào)和預(yù)讀請(qǐng)求隊(duì)列的調(diào)度。在調(diào)度方面，服務(wù)器視所有客戶端為平等優(yōu)先級(jí)(可修改特定客戶端的優(yōu)先級(jí))，按照傳統(tǒng)的先來先服務(wù)策略對(duì)預(yù)讀請(qǐng)求進(jìn)行調(diào)度[8]，只有在I/O請(qǐng)求隊(duì)列為空時(shí)才執(zhí)行預(yù)讀請(qǐng)求隊(duì)列調(diào)度。預(yù)讀請(qǐng)求隊(duì)列每個(gè)節(jié)點(diǎn)中包含兩個(gè)文件信息，在被調(diào)度傳輸時(shí)同時(shí)傳輸兩個(gè)文件，并根據(jù)相應(yīng)的比例來分配傳輸帶寬。響應(yīng)請(qǐng)求信號(hào)方面，主要響應(yīng)客戶端的3種請(qǐng)求信號(hào)是：預(yù)讀請(qǐng)求、預(yù)讀請(qǐng)求轉(zhuǎn)讀請(qǐng)求、預(yù)讀終止。對(duì)于這3種信號(hào)的處理如下：

圖3 客戶端結(jié)構(gòu)

圖4 客戶端讀請(qǐng)求流程圖

(1)收到預(yù)讀請(qǐng)求信號(hào)：將預(yù)讀請(qǐng)求文件加入預(yù)讀請(qǐng)求隊(duì)列，并標(biāo)記兩個(gè)預(yù)讀請(qǐng)求文件在傳輸時(shí)占據(jù)的帶寬比例，隊(duì)列中兩個(gè)文件占用一個(gè)節(jié)點(diǎn)，在被調(diào)度時(shí)根據(jù)比例傳輸兩個(gè)文件數(shù)據(jù)。

(2)收到預(yù)讀請(qǐng)求轉(zhuǎn)讀請(qǐng)求信號(hào)：將對(duì)應(yīng)文件加入I/O請(qǐng)求隊(duì)列；將文件所在的預(yù)讀請(qǐng)求隊(duì)列節(jié)點(diǎn)刪除。

(3)收到預(yù)讀終止信號(hào)：終止數(shù)據(jù)傳輸，將預(yù)讀文件所在節(jié)點(diǎn)從預(yù)讀隊(duì)列中刪除。

DLSDCM的優(yōu)點(diǎn)在于其可以建立在傳統(tǒng)分布式緩存系統(tǒng)之上，在程序使用數(shù)據(jù)之前異步預(yù)讀并將預(yù)讀命中數(shù)據(jù)傳給分布式緩存系統(tǒng)，填補(bǔ)了程序使用數(shù)據(jù)之前的空白時(shí)間；正在進(jìn)行中的熱點(diǎn)數(shù)據(jù)遷移工作可以填補(bǔ)緩存系統(tǒng)對(duì)熱點(diǎn)系統(tǒng)分配不均衡的不足，提高了傳統(tǒng)分布式緩存效率。

由于數(shù)據(jù)預(yù)讀發(fā)生在服務(wù)器空閑時(shí)間，DLSDCM的缺點(diǎn)是預(yù)讀的命中率問題提升了服務(wù)器的無效數(shù)據(jù)吞吐量，但此缺點(diǎn)并未影響整體分布式存儲(chǔ)的性能；DLSDCM對(duì)客戶端數(shù)據(jù)訪問隨機(jī)性強(qiáng)和更新速度快的場(chǎng)合適用性較差，對(duì)于服務(wù)器繁忙時(shí)提升效率較低。

[1]鄧見光，潘曉衡，袁華強(qiáng).云存儲(chǔ)及其分布式文件系統(tǒng)研究[J].東莞理工學(xué)院學(xué)報(bào)，2012，19(5)：41-46.

[2]Oracle white paper.Platform-as-a-Service pfivate cloude with oracle fusion middleware[EB/OL].(2009-10)[2013-03].http：//www.oracle.com/us/technologies/cloud/036500.pdf.

[3]Wikipedia.Memcached[EB/OL].(2013-03-12)[2013-04].http：//en.wikipedia.org/wiki/memcached.

[4]Terracotta.Terracotta DSO documentation[EB/OL].(2012-08)[2013-04].http：//www.terracotta.org/confluence/display/docs/Home.

[5]秦秀磊，張文博，魏峻，等.云計(jì)算環(huán)境下分布式緩存技術(shù)的現(xiàn)狀與挑戰(zhàn)[J].軟件學(xué)報(bào).2012，19(5)：1787-1803.

[6]SHRIVER E，SMALL C.Why does file system prefetching work?[C].Proceedings of 1999 USENIX Annual.Technical Conference，1999：71-84.

[7]劉愛貴，陳剛.一種基于用戶的 LNS文件預(yù)測(cè)模型[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(29)：14-17.

[8]吳峰光，奚宏生，徐陳鋒.一種支持并發(fā)訪問流的文件預(yù)取算法[J].軟件學(xué)報(bào)，2010，21(8)：1820-1833.

[9]GRIFFIOEN J，APPLETON R.Reducing file system latency using a predictive approach[C].Proceedings of USENIX Summer Technical Conference，1994：197-207.

[10]BRYANT R E，O′HALLARON D R.Computer systems a programmer′s perspective(英文版)[M].北京：電子工業(yè)出版社，2006.

[11]姚念民，鞠九濱.過載服務(wù)器的性能研究[J].軟件學(xué)報(bào)，2003，14(10)：1781-1786.

[12]徐非，楊廣文，鞠大鵬.基于peer-to-peer的分布式存儲(chǔ)系統(tǒng)的設(shè)計(jì)[J].軟件學(xué)報(bào)，2004，15(02)：268-277.