唐麗梅，邢素霞，陳天華

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

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

(1)二級(jí) Cache結(jié)構(gòu)預(yù)取[1]。該策略根據(jù) Cache結(jié)構(gòu)設(shè)計(jì)，通過(guò)減小Cache訪問(wèn)的延遲，提高二級(jí)Cache命中率[2]；適應(yīng)面廣，可以應(yīng)用在儲(chǔ)存優(yōu)化系統(tǒng)中,但是對(duì)于多用戶海量隨機(jī)訪問(wèn)，預(yù)取效率很難有所提高。

(2)自適應(yīng)預(yù)取策略[3]。該策略考慮了預(yù)取的盲目性問(wèn)題，通過(guò)調(diào)整預(yù)取長(zhǎng)度提高預(yù)取效率。但是自適應(yīng)預(yù)取只是在連續(xù)數(shù)據(jù)請(qǐng)求的情況下有效，在用戶請(qǐng)求地址完全不連續(xù)的情況下，預(yù)取數(shù)據(jù)基本失效。由于自適應(yīng)預(yù)取算法將多用戶數(shù)據(jù)請(qǐng)求當(dāng)成隨機(jī)數(shù)據(jù)請(qǐng)求，基本上不預(yù)取數(shù)據(jù)，因此預(yù)取性能受到限制。

通過(guò)構(gòu)建一個(gè)智能動(dòng)態(tài)預(yù)取策略的優(yōu)化系統(tǒng)對(duì)多用戶訪問(wèn)服務(wù)系統(tǒng)進(jìn)行優(yōu)化。其中預(yù)取的數(shù)據(jù)是優(yōu)化系統(tǒng)能否發(fā)揮作用的一個(gè)重要因素。因此選擇動(dòng)態(tài)調(diào)整Cache大小和調(diào)整預(yù)取長(zhǎng)度相結(jié)合的方式。實(shí)現(xiàn)了多用戶數(shù)據(jù)存儲(chǔ)設(shè)備通過(guò)網(wǎng)絡(luò)為所有工作站的共享。

1 相關(guān)工作

[1]通過(guò)分析Cache失效行為特性,設(shè)計(jì)了一種步長(zhǎng)自適應(yīng)的二級(jí)Cache預(yù)取機(jī)制，該預(yù)取機(jī)制動(dòng)態(tài)調(diào)整預(yù)測(cè)訪存模式及預(yù)測(cè)量。文中所選算法基于自適應(yīng)算法，該算法僅對(duì)用戶數(shù)據(jù)保存在某一磁盤的連續(xù)地址有效,對(duì)多用戶訪問(wèn)的非連續(xù)地址訪問(wèn)對(duì)象預(yù)取失效。雖然多用戶的數(shù)據(jù)請(qǐng)求之間的邏輯存儲(chǔ)地址信息是不連續(xù)的，但對(duì)于每個(gè)用戶的數(shù)據(jù)請(qǐng)求的邏輯存儲(chǔ)地址的分布是連續(xù)的，可以把這種數(shù)據(jù)請(qǐng)求當(dāng)作不完全的隨機(jī)請(qǐng)求，而且是有一定跨度的有規(guī)律請(qǐng)求，因此可以通過(guò)分解多用戶數(shù)據(jù)來(lái)獲得若干個(gè)順序數(shù)據(jù)請(qǐng)求。再利用自適應(yīng)方式調(diào)整Cache,從而產(chǎn)生本文的多用戶Cache自適應(yīng)動(dòng)態(tài)預(yù)取算法。

引入Cache結(jié)構(gòu)之后，CPU的訪存時(shí)間由Cache命中時(shí)間、Cache失效率[4]、Cache失效開銷這三個(gè)因素共同決定，其決定關(guān)系如下：

Cache訪存時(shí)間=Cache命中時(shí)間+Cache失效率×Cache失效開銷

本文的主要設(shè)計(jì)工作包括：

(1)分析多用戶請(qǐng)求信息特性，設(shè)計(jì)一種識(shí)別不同用戶數(shù)據(jù)、調(diào)度相應(yīng)Cache的預(yù)取機(jī)制。

(2)分析多用戶請(qǐng)求的Cache失效開銷，調(diào)整閾值參數(shù)，實(shí)時(shí)統(tǒng)計(jì)命中率。通過(guò)分析多用戶請(qǐng)求系統(tǒng)Cache開銷函數(shù)，選擇合適的Cache結(jié)構(gòu)參數(shù)，最大可能地提高 Cache性能[5]。

2 多用戶Cache自適應(yīng)動(dòng)態(tài)預(yù)取機(jī)制

2.1 識(shí)別多用戶數(shù)據(jù)請(qǐng)求

多用戶通過(guò)網(wǎng)絡(luò)服務(wù)器系統(tǒng)對(duì)存放在磁盤陣列中的數(shù)據(jù)發(fā)出請(qǐng)求，此時(shí)的數(shù)據(jù)請(qǐng)求序列特點(diǎn)是有規(guī)律的隨機(jī)數(shù)據(jù)請(qǐng)求,每個(gè)用戶的數(shù)據(jù)請(qǐng)求邏輯存儲(chǔ)地址的分布是連續(xù)的[3]。針對(duì)多用戶，引入每個(gè)用戶的唯一標(biāo)識(shí)ID,由此產(chǎn)生分布式訪問(wèn)各磁盤組的請(qǐng)求序列。磁盤陣列控制器在接收到主機(jī)發(fā)送過(guò)來(lái)的、包含邏輯地址數(shù)據(jù)信息的多個(gè)用戶讀請(qǐng)求命令后，將該命令進(jìn)行預(yù)命令分解，并生成各物理盤的磁盤讀請(qǐng)求子命令。子命令信息包括邏輯首地址、數(shù)據(jù)長(zhǎng)度、用戶ID號(hào)及訪問(wèn)次數(shù)。只要將請(qǐng)求的邏輯首地址和數(shù)據(jù)長(zhǎng)度與Cache組中記錄的值相比較，就可以快速查找出當(dāng)前請(qǐng)求的數(shù)據(jù)是否在Cache組中。多用戶訪問(wèn)預(yù)取的整個(gè)流程如圖1所示。

2.2 工作流程

磁盤陣列包括N個(gè)磁盤Cache組,每個(gè)磁盤Cache組中有M個(gè)Cache區(qū)。Cache區(qū)數(shù)目則是根據(jù)磁盤陣列接收順序請(qǐng)求的數(shù)目和預(yù)取閾值H確定。本算法將每個(gè)順序請(qǐng)求定位調(diào)度給Cache組中相應(yīng)的Cache區(qū)間。圖2中A、B、C緩存區(qū)間分別代表調(diào)度給 A、B、C三個(gè)用戶的請(qǐng)求序列的Cache區(qū)間，這三個(gè)順序請(qǐng)求序列交錯(cuò)組成一個(gè)磁盤組隨機(jī)請(qǐng)求序列。

在多用戶查詢Cache組過(guò)程中，無(wú)論是否命中Cache區(qū)間，都要對(duì)Cache進(jìn)行更新。Cache區(qū)間的具體更新過(guò)程如下：

(1)若命中預(yù)取區(qū)間，則將命中項(xiàng)計(jì)數(shù)器Count值加1。然后將新命中數(shù)據(jù)塊放入Cache區(qū)地址單元的頭部。

(2)若沒(méi)有命中Cache組中的任何一個(gè)有效項(xiàng),則所有有效項(xiàng)的Count計(jì)數(shù)值減1，同時(shí)在預(yù)取Cache組中分配一個(gè)新區(qū)間，并將該區(qū)間的Count值置1。在Cache組內(nèi)淘汰Count值最小的Cache數(shù)據(jù)塊。

動(dòng)態(tài)Cache預(yù)取算法用來(lái)以優(yōu)化自適應(yīng)算法的另一措施是通過(guò)預(yù)取命中率實(shí)時(shí)統(tǒng)計(jì)來(lái)調(diào)整預(yù)取長(zhǎng)度參數(shù)。通過(guò)設(shè)置一個(gè)窗口函數(shù)[5]，在窗口滑動(dòng)之前，Cache命中次數(shù)為H，統(tǒng)計(jì)出滑動(dòng)到某一位置時(shí)Cache命中次數(shù)Hs。這樣就可以得到Cache命中率p=H/Hs。下面定義命中率的函數(shù)f(p)。設(shè)當(dāng)前窗口長(zhǎng)度為Dcur,滑動(dòng)后的長(zhǎng)度為 Dnext，則 Dnext=Dcurf(p)；其中 f(p)是 p的增函數(shù)，且當(dāng)p＞0.5 時(shí)，f(p)＞1；當(dāng) p＜0.5 時(shí)，f(p)＜1。 這樣，當(dāng) Cache命中率較高時(shí)，窗口不斷增大，直到達(dá)到系統(tǒng)允許的最大值；當(dāng)Cache命中率較低時(shí)，窗口不斷減小，直到預(yù)取值為0。

2.3 算法分析

多用戶系統(tǒng)存在多個(gè)用戶共享一臺(tái)服務(wù)器的情況。多用戶訪問(wèn)采取M/G/1排隊(duì)模型[6],兩個(gè)參數(shù)為λ1和λ2的poisson流請(qǐng)求同時(shí)進(jìn)入服務(wù)器處理系統(tǒng)。用戶向共享服務(wù)器發(fā)出請(qǐng)求命令,服務(wù)器空閑時(shí)用戶能夠得到立即服務(wù)，否則排隊(duì)等待。

多用戶訪問(wèn)泊松輸入如圖3所示。服務(wù)器處理兩種請(qǐng)求：(1)常規(guī)請(qǐng)求,不能直接從本地磁盤上的預(yù)讀Cache中得到用戶請(qǐng)求響應(yīng)；(2)預(yù)取請(qǐng)求，可以由Cache直接響應(yīng)的請(qǐng)求。所有用戶發(fā)出的服務(wù)器請(qǐng)求具有相同的優(yōu)先級(jí)，它們加入同一個(gè)隊(duì)列等待服務(wù)。假設(shè)用戶請(qǐng)求不調(diào)用磁盤數(shù)據(jù)傳輸時(shí)，則消耗的系統(tǒng)資源非常少，因此當(dāng)用戶請(qǐng)求可從緩存Cache中滿足時(shí)，此次請(qǐng)求將不會(huì)產(chǎn)生系統(tǒng)代價(jià)。

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

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

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

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

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

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

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

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

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

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

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

(3)預(yù)取閾值

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

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

3 測(cè)試及分析

本文以視頻服務(wù)器為例對(duì)以上算法進(jìn)行驗(yàn)證。在視頻網(wǎng)絡(luò)服務(wù)器系統(tǒng)中模擬5個(gè)用戶訪問(wèn)1 000個(gè)共享數(shù)據(jù),并讓用戶對(duì)服務(wù)器進(jìn)行長(zhǎng)時(shí)間的訪問(wèn)。記錄用戶對(duì)磁盤陣列中數(shù)據(jù)不同訪問(wèn)次數(shù)下的預(yù)取命中率，動(dòng)態(tài)預(yù)取算法與自適應(yīng)[6]預(yù)取的命中率對(duì)比如圖4所示，明顯看到動(dòng)態(tài)Cache預(yù)取算法具有更好的預(yù)取效果。

使用Iometer測(cè)試軟件模擬在多用戶數(shù)據(jù)請(qǐng)求條件下，分別測(cè)試自適應(yīng)預(yù)取策略和動(dòng)態(tài)預(yù)取算法性能。將磁盤陣列上的硬盤分為5個(gè)分區(qū),模擬5個(gè)吧順序用戶請(qǐng)求,兩種算法測(cè)試性能對(duì)比如表1所示。

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

動(dòng)態(tài)Cache預(yù)取算法在達(dá)到2個(gè)用戶數(shù)時(shí)，體現(xiàn)出更大的優(yōu)越性，此時(shí)常規(guī)自適應(yīng)預(yù)取算法的I/O傳輸率下降了60%，而動(dòng)態(tài)Cache預(yù)取算法的I/O傳輸率沒(méi)有任何下降。但是Cache組Cache區(qū)間的個(gè)數(shù)與多用戶請(qǐng)求序列數(shù)必須同比增加，否則算法的性能下降很大。原因是當(dāng)順序請(qǐng)求序列數(shù)大于磁盤Cache組的Cache區(qū)間數(shù)時(shí)，導(dǎo)致Cache命中率下降。因此通過(guò)相應(yīng)加大磁盤Cache組中Cache區(qū)間的數(shù)目來(lái)實(shí)現(xiàn)高效的磁盤預(yù)取性能。

在單和多用戶系統(tǒng)中，固定式aIO/aT，系統(tǒng)容量越大，預(yù)取閾值就越高。然而，僅在多用戶系統(tǒng)中的預(yù)取閾值受系統(tǒng)負(fù)載f的影響。通過(guò)分析3個(gè)重要函數(shù)：代價(jià)函數(shù)C、預(yù)取率 λ2的最佳值及預(yù)取閾值 H，達(dá)到動(dòng)態(tài)調(diào)整系統(tǒng)緩存負(fù)載f來(lái)獲得最小的預(yù)取閾值H，識(shí)別并分解多用戶個(gè)人信息，動(dòng)態(tài)調(diào)度Cache區(qū)間，減小Cache負(fù)載，從而得到最高預(yù)取命中率，解決了多用戶訪問(wèn)共享服務(wù)系統(tǒng)中預(yù)取失效率高的問(wèn)題。

參考文獻(xiàn)

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

[2]徐煒遐,李瓊,蔣艷凰.一種自適應(yīng)負(fù)載的I/O調(diào)度算法[J].計(jì)算機(jī)工程與科學(xué),2009,31(11)：1-29.

[3]張敏.一種基于SAS技術(shù)的高性能硬件磁盤陣列的設(shè)計(jì)與實(shí)現(xiàn)[D].江西：南昌大學(xué),2007.

[4]張燕,胡英堅(jiān),姜濤.基于排隊(duì)網(wǎng)絡(luò)RAID存儲(chǔ)系統(tǒng)的性能評(píng)價(jià)模型[J].長(zhǎng)春工業(yè)大學(xué)報(bào)(自然科學(xué)版),2010,1(3):471-475.

[5]姜國(guó)松,謝長(zhǎng)生,丁紅,等.RAID控制器中I/O調(diào)度算法研究[J].小型微型計(jì)算機(jī)系統(tǒng),2008，29(4)：773-776.

[6]王培.網(wǎng)格環(huán)境下基于滑動(dòng)窗口的信任模型研究[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.