一種基于文件預測的分布式緩存模型

張勝利，陳莉君

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

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

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

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

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

1 文件預測模型

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

1.1 LS文件預測模型

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

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

1.2 DLS文件預測模型

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

圖1 DLS文件預測模型

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

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

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

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

表1 DLS與LS對比1

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

表2 DLS與LS對比2

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

2 DLSDCM設計原理

2.1 緩存模型理論基礎

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

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

2.2 DLSDCM的架構

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

圖2 DLSDCM緩存模型

3 DLSDCM的實現

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

3.1 DLSDCM客戶端的實現

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

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

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

3.2 DLSDCM服務器端的實現

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

圖3 客戶端結構

圖4 客戶端讀請求流程圖

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

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

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

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

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

[1]鄧見光，潘曉衡，袁華強.云存儲及其分布式文件系統研究[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]秦秀磊，張文博，魏峻，等.云計算環境下分布式緩存技術的現狀與挑戰[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]吳峰光，奚宏生，徐陳鋒.一種支持并發訪問流的文件預取算法[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].北京：電子工業出版社，2006.

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

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