預取Cache技術是解決Cache失效開銷的關鍵技術。由于多用戶產生的海量數據訪問往往耗時巨大，因此有必要根據多用戶存儲請求結構設計特定的Cache預取優化機制。通常采用的優化策略可以分為兩類：

    (1)二級Cache結構預取[1]。該策略根據Cache結構設計，通過減小Cache訪問的延遲，提高二級Cache命中率[2]；適應面廣，可以應用在儲存優化系統中, 但是對于多用戶海量隨機訪問，預取效率很難有所提高。
    (2)自適應預取策略[3]。該策略考慮了預取的盲目性問題，通過調整預取長度提高預取效率。但是自適應預取只是在連續數據請求的情況下有效，在用戶請求地址完全不連續的情況下，預取數據基本失效。由于自適應預取算法將多用戶數據請求當成隨機數據請求，基本上不預取數據，因此預取性能受到限制。
　    通過構建一個智能動態預取策略的優化系統對多用戶訪問服務系統進行優化。其中預取的數據是優化系統能否發揮作用的一個重要因素。因此選擇動態調整Cache大小和調整預取長度相結合的方式。實現了多用戶數據存儲設備通過網絡為所有工作站的共享。
1 相關工作
    參考文獻[1]通過分析Cache失效行為特性,設計了一種步長自適應的二級Cache預取機制，該預取機制動態調整預測訪存模式及預測量。文中所選算法基于自適應算法，該算法僅對用戶數據保存在某一磁盤的連續地址有效,對多用戶訪問的非連續地址訪問對象預取失效。雖然多用戶的數據請求之間的邏輯存儲地址信息是不連續的，但對于每個用戶的數據請求的邏輯存儲地址的分布是連續的，可以把這種數據請求當作不完全的隨機請求，而且是有一定跨度的有規律請求，因此可以通過分解多用戶數據來獲得若干個順序數據請求。再利用自適應方式調整Cache,從而產生本文的多用戶Cache自適應動態預取算法。
    引入Cache結構之后， CPU的訪存時間由Cache命中時間、 Cache失效率[4]、 Cache失效開銷這三個因素共同決定，其決定關系如下：
    Cache訪存時間=Cache命中時間+Cache失效率×Cache失效開銷
    本文的主要設計工作包括：
    (1)分析多用戶請求信息特性，設計一種識別不同用戶數據、調度相應Cache的預取機制。
    (2)分析多用戶請求的Cache失效開銷，調整閾值參數，實時統計命中率。通過分析多用戶請求系統Cache開銷函數，選擇合適的Cache結構參數，最大可能地提高Cache性能[5]。
2 多用戶Cache自適應動態預取機制
2.1識別多用戶數據請求
    多用戶通過網絡服務器系統對存放在磁盤陣列中的數據發出請求，此時的數據請求序列特點是有規律的隨機數據請求,每個用戶的數據請求邏輯存儲地址的分布是連續的[3]。針對多用戶，引入每個用戶的唯一標識ID,由此產生分布式訪問各磁盤組的請求序列。磁盤陣列控制器在接收到主機發送過來的、包含邏輯地址數據信息的多個用戶讀請求命令后，將該命令進行預命令分解，并生成各物理盤的磁盤讀請求子命令。子命令信息包括邏輯首地址、數據長度、用戶ID號及訪問次數。只要將請求的邏輯首地址和數據長度與Cache組中記錄的值相比較，就可以快速查找出當前請求的數據是否在Cache組中。多用戶訪問預取的整個流程如圖1所示。
2.2 工作流程
     磁盤陣列包括N個磁盤Cache組,每個磁盤Cache組中有M個Cache區。Cache區數目則是根據磁盤陣列接收順序請求的數目和預取閾值H確定。本算法將每個順序請求定位調度給Cache組中相應的Cache區間。圖2中A、B、C緩存區間分別代表調度給A、B、C三個用戶的請求序列的Cache區間，這三個順序請求序列交錯組成一個磁盤組隨機請求序列。
   在多用戶查詢Cache組過程中， 無論是否命中Cache區間， 都要對Cache進行更新。Cache區間的具體更新過程如下：
    (1)若命中預取區間，則將命中項計數器Count值加1。然后將新命中數據塊放入Cache區地址單元的頭部。
    (2)若沒有命中Cache組中的任何一個有效項,則所有有效項的Count計數值減1， 同時在預取Cache組中分配一個新區間，并將該區間的Count值置1。在Cache組內淘汰Count值最小的Cache數據塊。
    動態Cache預取算法用來以優化自適應算法的另一措施是通過預取命中率實時統計來調整預取長度參數。通過設置一個窗口函數[5]，在窗口滑動之前，Cache命中次數為H，統計出滑動到某一位置時Cache命中次數Hs。這樣就可以得到Cache命中率p=H/Hs。下面定義命中率的函數f(p)。設當前窗口長度為Dcur,滑動后的長度

2.3 算法分析
　　多用戶系統存在多個用戶共享一臺服務器的情況。多用戶訪問采取M/ G/ 1排隊模型[6],兩個參數為λ1和λ2的poisson流請求同時進入服務器處理系統。用戶向共享服務器發出請求命令,服務器空閑時用戶能夠得到立即服務，否則排隊等待。
    多用戶訪問泊松輸入如圖3所示。服務器處理兩種請求：(1)常規請求,不能直接從本地磁盤上的預讀Cache中得到用戶請求響應；(2)預取請求，可以由Cache直接響應的請求。所有用戶發出的服務器請求具有相同的優先級，它們加入同一個隊列等待服務。假設用戶請求不調用磁盤數據傳輸時，則消耗的系統資源非常少，因此當用戶請求可從緩存Cache中滿足時，此次請求將不會產生系統代價。

3 測試及分析
    本文以視頻服務器為例對以上算法進行驗證。在視頻網絡服務器系統中模擬5個用戶訪問1 000個共享數據, 并讓用戶對服務器進行長時間的訪問。記錄用戶對磁盤陣列中數據不同訪問次數下的預取命中率，動態預取算法與自適應[6]預取的命中率對比如圖4所示，明顯看到動態Cache預取算法具有更好的預取效果。
    使用Iometer測試軟件模擬在多用戶數據請求條件下，分別測試自適應預取策略和動態預取算法性能。將磁盤陣列上的硬盤分為5個分區,模擬5個吧順序用戶請求,兩種算法測試性能對比如表1所示。

    動態Cache預取算法在達到2個用戶數時，體現出更大的優越性，此時常規自適應預取算法的I/O傳輸率下降了60%，而動態Cache預取算法的I/O傳輸率沒有任何下降。但是Cache組Cache區間的個數與多用戶請求序列數必須同比增加，否則算法的性能下降很大。原因是當順序請求序列數大于磁盤Cache組的Cache區間數時，導致Cache命中率下降。因此通過相應加大磁盤Cache組中Cache區間的數目來實現高效的磁盤預取性能。
    在單和多用戶系統中，固定式aIO/aT，系統容量越大，預取閾值就越高。然而，僅在多用戶系統中的預取閾值受系統負載f的影響。通過分析3個重要函數：代價函數C、預取率λ2的最佳值及預取閾值H，達到動態調整系統緩存負載f來獲得最小的預取閾值H，識別并分解多用戶個人信息，動態調度Cache區間，減小Cache負載，從而得到最高預取命中率，解決了多用戶訪問共享服務系統中預取失效率高的問題。
參考文獻
[1] 靳強, 郭陽, 魯建壯. 一種步長自適應二級Cache預取機制[J].計算機工程與應用,2011,47(29)：56-59.
[2] 徐煒遐, 李瓊, 蔣艷凰. 一種自適應負載的I/O調度算法[J].計算機工程與科學,2009,31(11)：1-29.
[3] 張敏.一種基于SAS技術的高性能硬件磁盤陣列的設計與實現[D].江西：南昌大學,2007.
[4] 張燕,胡英堅,姜濤. 基于排隊網絡RAID存儲系統的性能評價模型[J].長春工業大學報(自然科學版),2010,1(3):471-475.
[5] 姜國松,謝長生,丁紅,等.RAID控制器中I/O調度算法研究[J].小型微型計算機系統,2008，29(4)：773-776.
[6] 王培. 網格環境下基于滑動窗口的信任模型研究[D]. 秦皇島：燕山大學,2010.
[7] ALEXANDER T. Performance,reliability,and perform ability aspects of Hierarchical RAID[C]. Proceedings-6th IEEE International Conference on Networking, Architecture, and Storage, NAS2011.