預(yù)取Cache技術(shù)是解決Cache失效開銷的關(guān)鍵技術(shù)。由于多用戶產(chǎn)生的海量數(shù)據(jù)訪問往往耗時巨大，因此有必要根據(jù)多用戶存儲請求結(jié)構(gòu)設(shè)計特定的Cache預(yù)取優(yōu)化機制。通常采用的優(yōu)化策略可以分為兩類：

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

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

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

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