張勝利，陳莉君

(西安郵電大學 計算機學院，陜西 西安710061)

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

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

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

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

1 文件預測模型

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

1.1 LS文件預測模型

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

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

1.2 DLS文件預測模型

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

圖1 DLS文件預測模型

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

1.3 LS和DLS兩種文件預測模型對比

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

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

表1 DLS與LS對比1

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

表2 DLS與LS對比2

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

2 DLSDCM設計原理

2.1 緩存模型理論基礎

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

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

2.2 DLSDCM的架構

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

圖2 DLSDCM緩存模型

3 DLSDCM的實現(xiàn)

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

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

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

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

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

3.2 DLSDCM服務器端的實現(xiàn)

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

圖3 客戶端結構

圖4 客戶端讀請求流程圖

(1)收到預讀請求信號：將預讀請求文件加入預讀請求隊列，并標記兩個預讀請求文件在傳輸時占據的帶寬比例，隊列中兩個文件占用一個節(jié)點，在被調度時根據比例傳輸兩個文件數(shù)據。

(2)收到預讀請求轉讀請求信號：將對應文件加入I/O請求隊列；將文件所在的預讀請求隊列節(jié)點刪除。

(3)收到預讀終止信號：終止數(shù)據傳輸，將預讀文件所在節(jié)點從預讀隊列中刪除。

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

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

[1]鄧見光，潘曉衡，袁華強.云存儲及其分布式文件系統(tǒng)研究[J].東莞理工學院學報，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]秦秀磊，張文博，魏峻，等.云計算環(huán)境下分布式緩存技術的現(xiàn)狀與挑戰(zhàn)[J].軟件學報.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文件預測模型[J].計算機工程與應用，2007，43(29)：14-17.

[8]吳峰光，奚宏生，徐陳鋒.一種支持并發(fā)訪問流的文件預取算法[J].軟件學報，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]姚念民，鞠九濱.過載服務器的性能研究[J].軟件學報，2003，14(10)：1781-1786.

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