多用戶存儲中自適應(yīng)動態(tài)預(yù)取策略*

唐麗梅，邢素霞，陳天華

(北京工商大學(xué) 計算機與信息工程學(xué)院，北京 100048)

預(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ù)請求當成隨機數(shù)據(jù)請求，基本上不預(yù)取數(shù)據(jù)，因此預(yù)取性能受到限制。

通過構(gòu)建一個智能動態(tài)預(yù)取策略的優(yōu)化系統(tǒng)對多用戶訪問服務(wù)系統(tǒng)進行優(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)工作

[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ù)請求當作不完全的隨機請求，而且是有一定跨度的有規(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]。針對多用戶，引入每個用戶的唯一標識ID,由此產(chǎn)生分布式訪問各磁盤組的請求序列。磁盤陣列控制器在接收到主機發(fā)送過來的、包含邏輯地址數(shù)據(jù)信息的多個用戶讀請求命令后，將該命令進行預(yù)命令分解，并生成各物理盤的磁盤讀請求子命令。子命令信息包括邏輯首地址、數(shù)據(jù)長度、用戶ID號及訪問次數(shù)。只要將請求的邏輯首地址和數(shù)據(jù)長度與Cache組中記錄的值相比較，就可以快速查找出當前請求的數(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進行更新。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è)當前窗口長度為Dcur,滑動后的長度為 Dnext，則 Dnext=Dcurf(p)；其中 f(p)是 p的增函數(shù)，且當p＞0.5 時，f(p)＞1；當 p＜0.5 時，f(p)＜1。 這樣，當 Cache命中率較高時，窗口不斷增大，直到達到系統(tǒng)允許的最大值；當Cache命中率較低時，窗口不斷減小，直到預(yù)取值為0。

2.3 算法分析

多用戶系統(tǒng)存在多個用戶共享一臺服務(wù)器的情況。多用戶訪問采取M/G/1排隊模型[6],兩個參數(shù)為λ1和λ2的poisson流請求同時進入服務(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)資源非常少，因此當用戶請求可從緩存Cache中滿足時，此次請求將不會產(chǎn)生系統(tǒng)代價。

(1)代價函數(shù)C

對于一個給定的系統(tǒng)，用戶的數(shù)據(jù)請求到達率為λ。假設(shè)系統(tǒng)中的數(shù)據(jù)塊訪問率都為p(p＞0或p=0)，預(yù)取不影響用戶的關(guān)于訪問下一個數(shù)據(jù)塊的可能性p。在數(shù)據(jù)已經(jīng)被預(yù)取情況下，用戶仍然以相同的概率λ發(fā)出請求。常規(guī)請求到達率和預(yù)取請求到達率分別為λ1、λ2。因此，用戶能從本地Cache緩存中獲得請求響應(yīng)的概率為 λ-λ1，等價于 pλ2，因為在緩存 Cache中的所有數(shù)據(jù)塊被訪問的概率為p。即如式(1)，在泊松流請求系統(tǒng)中，x單位時間內(nèi)響應(yīng)數(shù)據(jù)請求的時間t為：

其中，s平均大小的為請求數(shù)據(jù)塊，b為網(wǎng)絡(luò)帶寬[7]，與當前的網(wǎng)絡(luò)負載有關(guān)。忽略在本地緩存中獲取數(shù)據(jù)的代價，f為系統(tǒng)的負載。在多用戶系統(tǒng)中，一個常規(guī)請求的代價是該系統(tǒng)的資源代價和響應(yīng)延遲代價[7]之和：

其中,aIO為將單位大小的數(shù)據(jù)從磁盤介質(zhì)上讀到內(nèi)存中(或?qū)?nèi)存中的數(shù)據(jù)寫到磁盤上)的代價因子，它與磁盤的讀寫速度、系統(tǒng)內(nèi)存等資源有關(guān)；aT為在單位時間內(nèi)通過網(wǎng)絡(luò)傳輸數(shù)據(jù)所需的代價因子。

多用戶的請求到達率為泊松流 λ,有 Pλ2的概率能從本地Cache緩存中得到響應(yīng)，有λ1以常規(guī)訪問送到服務(wù)器訪問磁盤。因此用戶請求得到響應(yīng)的的平均代價為：

其中,0＜λ2＜λ/p， 0＜p＜1。

(2)預(yù)取率 λ2的最佳值

假設(shè)p和 λ都已知,希望找到 λ2的預(yù)取值，從而最大限度地減少每個用戶請求的平均代價C。λ2的值一旦被確定，可以通過計算公式 λ1=λ-pλ2計算得到。

在 p=1，λ2=λ 時以及 P=0，λ2=0時均可得到最小代價C，此時所有請求數(shù)據(jù)都可以從Cache緩存中獲取?？紤] 0＜p＜1的情況，代價函數(shù) C對 λ2進行求導(dǎo),通過 2次求導(dǎo)可得到極值位置：

在穩(wěn)定系統(tǒng)中 b＞(λ+(1-p)λ2)s。 當 pb＞λs時， 代價函數(shù) C對 λ2的 2階導(dǎo)數(shù)一直小于 0，這表明在 dC/dλ2=0處代價函數(shù)C取得最大值。求解 dC/dλ2=0,得到 λ2′為：

代價函數(shù) C在λ2′=0處取得最大值，系統(tǒng)代價隨著λ2增加而減少。 給定 λ2、p、(aIO/aT)值，隨著 λ2在變化范圍 [0,(λ/p)]內(nèi)增加，更多的預(yù)取數(shù)據(jù)塊被概率p訪問到，同時系統(tǒng)代價函數(shù)C減小。因此預(yù)取所有概率p的數(shù)據(jù)塊將使訪問代價函數(shù)降低到最小值。pb＜λs的情況，對于所有 λ2，有 dC/dλ2＞0，即隨 λ2的增加代價函數(shù)C的值也同步增加，此時數(shù)據(jù)都不能被預(yù)取。

(3)預(yù)取閾值

在pb＞λs這樣的系統(tǒng)中找到一個預(yù)取的閾值 H，當p＞H，λ2′＜0時，所有用戶請求數(shù)據(jù)可以通過訪問概率 p從Cache緩存中得到，將預(yù)取閾值設(shè)置為H。當且僅當式 p＞H成立，系統(tǒng)的代價函數(shù) C在 λ2＜0獲得最小值,其中 f=(λs/b) 。

容易證明 H＞f,如果 p＞H，則 p＞f，得到 pb＞λS，λ2′＜0。p取決于負載f、帶寬b和固定的aIO/aT。當系統(tǒng)的負載f增加時，預(yù)取閾值有增大的傾向，即更少的數(shù)據(jù)塊需要預(yù)取。當(aIO/aT)比值很小時，則增加負載不與預(yù)取閾值同步增大。此時f負載較低時，預(yù)取不能節(jié)省大量時間；隨著負載的增加，它需要更長的時間來傳輸文件，預(yù)取可以節(jié)省更多的時間。因此，可通過減小閾值來增加預(yù)取數(shù)?？梢宰C明，當且僅當b＞(aIO/aT)以及固定的aIO/aT時，減小閾值隨負載f從0增加而減小。預(yù)取閾值H在負載時取得最小值。

3 測試及分析

本文以視頻服務(wù)器為例對以上算法進行驗證。在視頻網(wǎng)絡(luò)服務(wù)器系統(tǒng)中模擬5個用戶訪問1 000個共享數(shù)據(jù),并讓用戶對服務(wù)器進行長時間的訪問。記錄用戶對磁盤陣列中數(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所示。

表1 自適應(yīng)算法和動態(tài)Cache預(yù)取測試性能對比

動態(tài)Cache預(yù)取算法在達到2個用戶數(shù)時，體現(xiàn)出更大的優(yōu)越性，此時常規(guī)自適應(yīng)預(yù)取算法的I/O傳輸率下降了60%，而動態(tài)Cache預(yù)取算法的I/O傳輸率沒有任何下降。但是Cache組Cache區(qū)間的個數(shù)與多用戶請求序列數(shù)必須同比增加，否則算法的性能下降很大。原因是當順序請求序列數(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的影響。通過分析3個重要函數(shù)：代價函數(shù)C、預(yù)取率 λ2的最佳值及預(yù)取閾值 H，達到動態(tài)調(diào)整系統(tǒng)緩存負載f來獲得最小的預(yù)取閾值H，識別并分解多用戶個人信息，動態(tài)調(diào)度Cache區(qū)間，減小Cache負載，從而得到最高預(yù)取命中率，解決了多用戶訪問共享服務(wù)系統(tǒng)中預(yù)取失效率高的問題。

參考文獻

[1]靳強,郭陽,魯建壯.一種步長自適應(yīng)二級Cache預(yù)取機制[J].計算機工程與應(yīng)用,2011,47(29)：56-59.

[2]徐煒遐,李瓊,蔣艷凰.一種自適應(yīng)負載的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.