基于ＡＲＩＭＡ的存儲(chǔ)優(yōu)化算法設(shè)計(jì)與實(shí)現(xiàn)

摘要：分析了SAN（storage area network）共享存儲(chǔ)體系中I/O訪問路徑上可能存在的性能瓶頸，提出了采用ARIMA時(shí)間序列分析方法建立基于前饋的預(yù)測式控制機(jī)制，預(yù)測瓶頸發(fā)生趨勢；通過改變存儲(chǔ)子系統(tǒng)內(nèi)的塊映射關(guān)系來實(shí)現(xiàn)數(shù)據(jù)的遷移，減少I/O訪問路徑上發(fā)生性能瓶頸的可能性，有效提高了SAN的可靠性和可用性。

關(guān)鍵詞：性能瓶頸；自回歸求和滑動(dòng)平均模型；性能預(yù)測

中圖分類號：TP302文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)11-3385-03



Design and implementation of storage performance optimization based on ARIMA



ZENG Lei-jie，ZHANG Yan-yuan，LI Zhan-huai，ZHAO Xiao-nan

（School of Computer， Northwestern Polytechnical University， Xi’an 710072， China）

Abstract:This paper analyzed the possible causes of the performance bottleneck in I/O access path in SAN storage architecture and proposed a predictive approach based on feedforward to optimize the I/O performance of SAN effectively， which was using a time series analysis method based on ARIMA to build the predictive and monitoring model of the performance. By this approach， the SAN can improve its availability and reliability effectively due to avoiding the appearance of performance bottleneck in I/O access path. 

Key words:performance bottleneck；ARIMA（autoregressive integrated moving average）；performance prediction

為了提高存儲(chǔ)局域網(wǎng)的可靠性和可用性，RAID技術(shù)得到了廣泛的運(yùn)用。按照不同的RAID級別把物理磁盤(physical disk，PD)組成Pool，然后從中構(gòu)筑出不同容量的邏輯磁盤(logical disk，LD)，實(shí)現(xiàn)單點(diǎn)PD故障能夠繼續(xù)進(jìn)行數(shù)據(jù)訪問(RAID7可實(shí)現(xiàn)兩點(diǎn)PD故障能夠繼續(xù)數(shù)據(jù)訪問)，提高了數(shù)據(jù)的可用性和可靠性。不過，在SAN的共享存儲(chǔ)體系中，多個(gè)業(yè)務(wù)服務(wù)器共享多個(gè)LD的數(shù)據(jù)，可能會(huì)使得個(gè)別PD上的I/O非常集中，形成瓶頸，從而使得I/O的響應(yīng)速度急劇降低，因此很有必要進(jìn)行性能的監(jiān)視，預(yù)測性能的趨勢，提前進(jìn)行數(shù)據(jù)的遷移，減少瓶頸發(fā)生的可能性。

解決該問題的方法主要有短期調(diào)節(jié)和長期修正兩種。短期調(diào)節(jié)一般是在存儲(chǔ)子系統(tǒng)發(fā)生擁塞現(xiàn)象時(shí)，采用見效快的臨時(shí)性措施，解決系統(tǒng)當(dāng)前表現(xiàn)為性能瓶頸的問題，但并不能徹底解決，只是暫時(shí)的；長期修正是依據(jù)對存儲(chǔ)系統(tǒng)存儲(chǔ)行為歷史的觀測進(jìn)行分析，然后推測系統(tǒng)將來會(huì)發(fā)生瓶頸的對象，預(yù)先采取必要的措施來加以回避。目前的存儲(chǔ)產(chǎn)品主要還是依賴人為的干預(yù)來實(shí)現(xiàn)這兩種方法，而且多數(shù)是在性能瓶頸出現(xiàn)后進(jìn)行事后調(diào)節(jié)，這勢必影響存儲(chǔ)設(shè)備性能的充分發(fā)揮。因此，如何根據(jù)所采集的數(shù)據(jù)，預(yù)測可能發(fā)生瓶頸的對象，自動(dòng)地按照某種策略提前進(jìn)行數(shù)據(jù)的重新調(diào)整，正常地響應(yīng)業(yè)務(wù)請求變得尤為重要。

現(xiàn)有的方法主要是借鑒人工智能和數(shù)據(jù)挖掘等技術(shù)，結(jié)合存儲(chǔ)系統(tǒng)的性能研究技術(shù)進(jìn)行展開的。例如，IBM Almaden研究中心的存儲(chǔ)管理項(xiàng)目SMART（storage management analytics and reasoning technology）、HP公司的AutoRAID^[1]等。它們主要是采用基于規(guī)則的、基于模型的或基于反饋的方法來實(shí)現(xiàn)存儲(chǔ)系統(tǒng)的決策和自動(dòng)化^[2，3]。本文提出了針對SAN中I/O性能監(jiān)視的數(shù)據(jù)來建立時(shí)間序列預(yù)測模型，實(shí)現(xiàn)基于前饋式的控制機(jī)制，對磁盤陣列的I/O進(jìn)行預(yù)測性監(jiān)控，避免瓶頸的發(fā)生，從而實(shí)現(xiàn)整體性能的優(yōu)化。

1性能瓶頸分析及數(shù)據(jù)采集方法

要實(shí)現(xiàn)對存儲(chǔ)系統(tǒng)的工作性能的預(yù)測、優(yōu)化，前提是必須能夠有效地對當(dāng)前工作狀態(tài)下的可能成為瓶頸的各個(gè)因素進(jìn)行監(jiān)視，然后根據(jù)所采集的數(shù)據(jù)信息進(jìn)行具體分析。

在進(jìn)行性能瓶頸的分析之前，首先分析存儲(chǔ)系統(tǒng)中I/O路徑的構(gòu)成情況，找準(zhǔn)進(jìn)行監(jiān)視的對象。如圖1所示，SAN存儲(chǔ)系統(tǒng)大致可以劃分為物理層、邏輯層和應(yīng)用層三個(gè)層次。物理層主要指的是多個(gè)PD按照RAID所構(gòu)成的Pool。邏輯層主要指從Pool中所構(gòu)筑的各種容量的LD。應(yīng)用層主要指寫入到LD中的各種文件，對LD的訪問是通過LD Mount到對應(yīng)的目錄下，然后進(jìn)行格式化，從而應(yīng)用服務(wù)器就可通過文件→LD→Pool→PD的多層映射來實(shí)現(xiàn)數(shù)據(jù)的I/O訪問。由上面的分析可知，I/O擁塞可能出現(xiàn)在I/O路徑上的每一個(gè)訪問環(huán)節(jié)：a）文件系統(tǒng)級的訪問；b)存儲(chǔ)設(shè)備所提供服務(wù)的外部端口；c)存儲(chǔ)子系統(tǒng)中的cache；d)LD；e)Pool或PD。

對于文件級的I/O瓶頸問題，可以借助操作系統(tǒng)或文件的重組來解決。不過，這種方法需要暫時(shí)停止業(yè)務(wù)的執(zhí)行，因?yàn)樗豢紤]或者很少考慮到存儲(chǔ)介質(zhì)的構(gòu)成情況，調(diào)節(jié)效果不佳。若存儲(chǔ)設(shè)備外部端口成為瓶頸，需要通過改變端口到應(yīng)用服務(wù)器的映射來緩解，這也需要停止業(yè)務(wù)。對于磁盤陣列而言cache相對低價(jià)，容量可以足夠大，基本上不會(huì)成為I/O的瓶頸，因此本文不把它作為監(jiān)視對象。若直接針對LD來解決I/O瓶頸問題，需要考慮的因素很多且很復(fù)雜。PD是構(gòu)成存儲(chǔ)子系統(tǒng)最基本的單位，當(dāng)某特定PD的I/O過于集中時(shí)，可以通過改變LD/PD的映射關(guān)系來解決，也就是可以將該P(yáng)ool中讀寫訪問頻繁的LD映射到其他不繁忙或者不用的Pool中，從而降低PD的訪問頻度，提高系統(tǒng)的整體性能。

本文主要把LD、Pool和PD作為監(jiān)視的對象，然后對存儲(chǔ)子系統(tǒng)的性能進(jìn)行數(shù)據(jù)的采集和分析，主要參數(shù)如表1所示。

表1性能參數(shù)及原始數(shù)據(jù)對應(yīng)一覽

參數(shù)名稱參數(shù)構(gòu)成對象對應(yīng)的原始數(shù)據(jù)

繁忙率PD/LD/Pool繁忙時(shí)間；監(jiān)視時(shí)間讀/寫應(yīng)答時(shí)間（對LD）

依據(jù)表1，可以明確在對磁盤陣列子系統(tǒng)進(jìn)行性能監(jiān)視時(shí)，需要監(jiān)測的對象有LD、PD和Pool等，以及需要收集數(shù)據(jù)的原始參數(shù)。

2性能預(yù)測模型的設(shè)計(jì)和實(shí)現(xiàn)

一般情況下，對磁盤陣列的訪問是隨機(jī)的，而數(shù)據(jù)的I/O有時(shí)會(huì)表現(xiàn)出一定的規(guī)律性，甚至是周期性的變化。例如數(shù)據(jù)的吞吐量白天和夜晚存在差異，周末和平時(shí)會(huì)存在差異等。針對這樣的特點(diǎn)分析磁盤陣列的I/O數(shù)據(jù)，估計(jì)歷史采樣值對下一個(gè)采樣值的影響，用線性回歸的方法來建立模型。事實(shí)證明對I/O變化的特點(diǎn)和趨勢進(jìn)行擬合預(yù)測也是可行的。而經(jīng)典的時(shí)間序列分析模型，自回歸求和滑動(dòng)平均模型（ARIMA）正具有這樣的特性。Box-Jenkins的ARIMA模型可以對各種復(fù)雜的時(shí)間序列進(jìn)行分析，包括平穩(wěn)的、非平穩(wěn)的、周期性模式。廣泛地運(yùn)用于各個(gè)領(lǐng)域時(shí)間序列的分析和預(yù)測，如網(wǎng)絡(luò)性能預(yù)測和數(shù)據(jù)預(yù)取等方面都有應(yīng)用^[4，5]。

ARIMA（p，d，q）是ARMA(p，q)模型的擴(kuò)展；ARMA(p，q)是由自回歸模型AR（p）和移動(dòng)平均模型MA（q）發(fā)展而來的。假定時(shí)間序列用z1，z2，…，zt表示，則一個(gè)純粹的AR(p)模型是將變量的一個(gè)觀測值表示成其以前的p個(gè)觀測值的線性組合加隨機(jī)誤差at項(xiàng)的形式：

Z^

t=1Z^t-1+2Z^t-2+…+pZ^t-p+at(1) 

一個(gè)純粹的MA(q)模型將變量的一個(gè)觀測值表示成由目前的和先前的q個(gè)隨機(jī)誤差線性組合的形式：

Z^t=at+θ1at-1+θ2at-2+…+θqat-q(2) 

自回歸—滑動(dòng)平均混合模型（ARMA）可寫成：

Z^t=1Z^t-1+2Z^t-2+…+pZ^t-p+at-θ1at-1+θ2at-2-…-θqat-q(3) 

由式（3）可知，在ARMA模型中，有p+q個(gè)參數(shù)需要估計(jì)。ARMA(p，q)模型要求序列均值不隨時(shí)間增加或減少，序列的方差不隨時(shí)間變化，而且序列本身相關(guān)的模式不改變^[6]。但現(xiàn)實(shí)中的時(shí)間序列很難滿足該條件，故需采用差分的方法將實(shí)際樣本序列進(jìn)行預(yù)處理，從而得到平穩(wěn)的ARMA模型。其中d表示差分次數(shù)。關(guān)于ARIMA模型作如下描述：

后移算子B：BZt=Zt-1，從而有BmZt=Zt-m

向后差分算子：ΔZt=Zt-Zt-1=(1-B)Zt

定義設(shè)d是非負(fù)整數(shù)，稱{Zt}是ARIMA(p，d，q)序列，形式如下：

Φ(B)ΔdZ^t=Θ(B)at(4)

其中:Φ(B)和Θ(B)是兩個(gè)次數(shù)分別為p和q的特征多項(xiàng)式；p和q都是正整數(shù)，表達(dá)式分別為

其中：B是后移算子；Δd為d階差分算子；at為高斯白噪聲序列，服從(0，σ2)的正態(tài)分布。

在運(yùn)用預(yù)測模型時(shí)，如果原始數(shù)據(jù)不是平穩(wěn)序列，需要先根據(jù)一定的差分步長（即選擇d值），對數(shù)據(jù)作預(yù)處理，再對平穩(wěn)序列建立ARMA模型，估計(jì)參數(shù)；之后根據(jù)d值反向求和還原原始序列值，就得到了真正的時(shí)間序列的預(yù)測值。利用ARIMA模型可以預(yù)測出現(xiàn)性能瓶頸的時(shí)機(jī)，找出繁忙率很高的LD，然后將繁忙率較低的Pool中的LD進(jìn)行數(shù)據(jù)遷移和映射關(guān)系的重新設(shè)定，就可以實(shí)現(xiàn)負(fù)載的重新分配，從而提高磁盤陣列的整體性能。

3實(shí)驗(yàn)結(jié)果及性能分析

本文采用NEC S2900的兩個(gè)物理磁盤(15 GB)按RAID1配置成的Pool，然后構(gòu)筑出多個(gè)容量為2 GB的邏輯磁盤LD作為監(jiān)測對象。實(shí)驗(yàn)中的工作負(fù)荷是由Iometer產(chǎn)生，訪問模式是64 KB大小的純隨機(jī)訪問(67%的讀操作，33%的寫操作)。在Iometer中，設(shè)置LD等待訪問請求的最大數(shù)目為5，并用參數(shù)delay time(相鄰兩個(gè)反問請求的間隔時(shí)間)來調(diào)節(jié)存儲(chǔ)負(fù)荷的強(qiáng)度。所采用的操作系統(tǒng)是Windows 2003，Intel Pentium 4 28 GHz，1 GB RAM，監(jiān)測對象LD格式化成NTFS。性能數(shù)據(jù)每15 min收集一次數(shù)據(jù)(采集間隔太短會(huì)導(dǎo)致正常I/O的響應(yīng)速度降低，因此本文采用15 min采集一次)，并對其I/O數(shù)據(jù)進(jìn)行具體的預(yù)測分析，以簡單驗(yàn)證預(yù)測模型的效果。

31數(shù)據(jù)的預(yù)處理

根據(jù)ACF（自相關(guān)）和PACF（偏自相關(guān)）函數(shù)的性質(zhì)，如果ACF和PACF函數(shù)中至少一個(gè)不是以指數(shù)形式或正弦形式衰減，則說明該序列不是平穩(wěn)的，必須進(jìn)行差分變換平穩(wěn)化之后，再利用ARMA(p，q)模型進(jìn)行估計(jì)。分析Pool繁忙率的ACF和PACF函數(shù)發(fā)現(xiàn)，其ACF函數(shù)不是指數(shù)或正弦形式的衰減，故對數(shù)據(jù)進(jìn)行差分預(yù)處理。對比圖2、3的一階、二階差分圖像可知，一階差分的結(jié)果已經(jīng)平穩(wěn)，因此選定一階差分的結(jié)果，即d取1。

32預(yù)測模型的建立

圖4、5是數(shù)據(jù)經(jīng)過一階差分處理后的ACF函數(shù)和PACF函數(shù)圖像，根據(jù)其明顯的下降趨勢，認(rèn)為序列平穩(wěn)。因此，可以對此預(yù)處理后的數(shù)據(jù)建立ARMA(p，q)模型。自回歸模型的階數(shù)可以根據(jù)ACF來確定。由于圖形持續(xù)衰減且正負(fù)相間，視p＝2；當(dāng)然，該圖形也可以視為第5個(gè)值以后截尾，因此，p＝5也可以。類似地，可以得出q的值也能取2和5兩種情況。綜合各值，初步選定ARMA(2，5)和ARMA(5，2)兩個(gè)模型。相應(yīng)的AIC值分別為-221.999和-225.531。根據(jù)AIC信息準(zhǔn)則，最終選擇模型ARMA(5，2)。用最大似然估計(jì)選定模型的估計(jì)參數(shù)，得到如下模型：

Y^t=0.252Y^t-1+0.157Y^t-2+0.076Y^t-3+0.076Y^t-4+0.376Y^t-5-0.042 at-1-0.895 at-2+0.11

該模型參數(shù)估計(jì)值的殘差序列的ACF和PACF圖像沒有任何模式（圖略），而且數(shù)值接近0，說明該殘差序列是白噪聲。

33模型的預(yù)測

根據(jù)上述步驟得出的模型ARIMA(5，1，2)對Pool的繁忙率進(jìn)行預(yù)測。圖6為ARIMA模型對Pool繁忙率的擬合曲線。通過擬合的結(jié)果可以看到，該模型對Pool繁忙率的曲線可以進(jìn)行很好的擬合。這樣就可以根據(jù)這個(gè)模型對Pool繁忙率將來的變化趨勢進(jìn)行預(yù)測了。根據(jù)預(yù)測的變化趨勢以及預(yù)先設(shè)定的baseline值，可以預(yù)先判斷出該P(yáng)ool在未來某個(gè)時(shí)刻是否會(huì)出現(xiàn)I/O瓶頸的現(xiàn)象。

4瓶頸點(diǎn)預(yù)測后的磁盤性能優(yōu)化方法

由PD、Pool與LD之間的映射關(guān)系可知，在實(shí)際監(jiān)視操作中，當(dāng)通過ARIMA模型預(yù)測出某個(gè)PD有I/O頻繁發(fā)生的趨勢時(shí)，需要對該P(yáng)D所在的Pool中所映射的各個(gè)LD進(jìn)行進(jìn)一步的負(fù)載分析，找出可能導(dǎo)致這個(gè)瓶頸發(fā)生的、對該P(yáng)ool的繁忙率有最大貢獻(xiàn)的LD，然后將該LD遷移到其他讀寫頻率較低的Pool去。下面是相應(yīng)的性能參數(shù)的計(jì)算公式。

公式1PD繁忙率（監(jiān)視時(shí)間內(nèi)PD實(shí)際I/O時(shí)間的比例）：pd_busyrate=pd_busytime/mon_time。

由公式1、3可知，若某個(gè)Pool中LD的讀寫操作頻繁，則其讀寫時(shí)間就會(huì)比較長，而構(gòu)成它的各個(gè)PD的繁忙率也就會(huì)比較長。因此，對成為性能瓶頸的LD進(jìn)行映射遷移，便可以消除PD產(chǎn)生的性能瓶頸的目的。

選擇遷移目的對象有如下原則： a)移入的LD應(yīng)為目標(biāo)Pool中繁忙率最低的LD；b)移入和移出的LD容量必須相同；c)移入和移出的LD必須位于不同的Pool；d)源、目標(biāo)Pool的RAID類型相同。

如圖7所示，當(dāng)預(yù)測出Pool 1中的PD出現(xiàn)I/O瓶頸的趨勢時(shí)，就對Pool 1中的各個(gè)LD進(jìn)行數(shù)據(jù)分析，計(jì)算所對應(yīng)的LD繁忙率，找出LD繁忙率最大的LD，然后將該LD的數(shù)據(jù)遷移到與Pool 1有相同RAID構(gòu)成、Pool繁忙率較低的Pool 2中容量相同的但LD繁忙率低的LD中，修改相應(yīng)的LD-Pool-PD映射關(guān)系。這樣，就可以減輕Pool1的繁忙率。

具體的實(shí)現(xiàn)采用事務(wù)處理的思想進(jìn)行在線更新方式，按照如下的步驟來實(shí)現(xiàn)。首先，在數(shù)據(jù)遷移開始時(shí)，維持源LD塊遷移的位圖信息，全部初始化為0，每個(gè)塊的位圖信息有兩個(gè)值（0代表該塊的數(shù)據(jù)還沒有遷移到目的LD中；1代表該塊的數(shù)據(jù)已經(jīng)遷移到目的LD對應(yīng)的塊上了）；然后，在數(shù)據(jù)遷移過程中根據(jù)數(shù)據(jù)塊的次序進(jìn)行數(shù)據(jù)拷貝，若在遷移的過程中出現(xiàn)了I/O寫請求，其具體的算法如下：

a)查看指定塊的遷移位圖信息，若為0，則說明該塊的數(shù)據(jù)還沒有進(jìn)行遷移，只要直接寫入對象LD中即可。

b)若指定塊的遷移位圖信息為1，就說明該塊的數(shù)據(jù)已經(jīng)遷移到目的LD中，那么，把該塊的數(shù)據(jù)分別寫入到目的LD和源LD；如果兩個(gè)寫操作都成功，就表示整個(gè)寫操作的成功，否則寫操作就失敗。若寫操作失敗，也就表示LD遷移處于LD移動(dòng)故障狀態(tài)，也就沒有繼續(xù)遷移的必要了。

若在遷移的過程中出現(xiàn)了I/O讀請求，按照正常的數(shù)據(jù)訪問即可。

5結(jié)束語

通過預(yù)測模型，使性能監(jiān)視更智能化，更具先見性和主動(dòng)性，降低了存儲(chǔ)系統(tǒng)性能下降的概率，從而達(dá)到提高存儲(chǔ)服務(wù)的質(zhì)量、優(yōu)化存儲(chǔ)性能的目的。不過，本文提出的預(yù)測方法仍有一些局限性。由于閾值是預(yù)先進(jìn)行設(shè)定的，未能根據(jù)最新的監(jiān)測數(shù)據(jù)進(jìn)行調(diào)整，會(huì)導(dǎo)致15%左右、可能成為瓶頸點(diǎn)的不能被發(fā)現(xiàn)，針對這個(gè)現(xiàn)象，還需要進(jìn)一步討論和解決。

參考文獻(xiàn)：

[1]舒繼武，薛魏，付長冬.網(wǎng)絡(luò)存儲(chǔ)系統(tǒng)與技術(shù)的現(xiàn)狀及發(fā)展趨勢[C]//2004年中國計(jì)算機(jī)科學(xué)技術(shù)發(fā)展報(bào)告.北京：清華大學(xué)出版社，2005:143-160.

[2]WANG Meng-zhi，KINMAN A U，AILAMAKI A，et al.Storage device performance prediction with CART models[C]//Proc of the 12th MASCOTS.Washington DC:IEEE Computer Society，2004:588-595. 

[3]LI Yin，UTTAMCHANDANI S，PALMER J，et al.AutoLoop: automated action selection in the observe-analyze-act loop of storage systems[C]//Proc of the 6th IEEE International Workshop on Policies for Distributed Systems and Networks (POLICY’05).Washington DC:IEEE Computer Society，2005:129-138.

[4]MILOUCHEVA I，ANZALONI A，MULLER E.A practical approach to forecast quality of service parameters considering outliers[C]//Proc of the 1st International Workshop on Inter-domain Performance and Simulation.Salzburg:[s.n.]，2003:163-172.

[5]TRAN N，REED D A.ARIMA time series modeling and forecasting for adaptive I/O prefetching[C]//Proc of ACM Int’l Conference on Supercomputing.New York:ACM Press，2001:473-485.

[6]張樹京，齊立心.時(shí)間序列分析簡明教程[M].北京：清華大學(xué)出版社，2003.

［7］Total cost of storage ownership:a user oriented approach[R].[S.l.]:Gartner Group，2000.

[8]UTTAMCHANDANI S，VORUGANTI K，SRINIVASAN S，et al.Polus: growing storage QoS management beyond a 4-year old kid[C]//Proc ofthe 3rd File and Storage Technologies(FAST).Berkeley CA:USENIX Association，2004:31-44.

[9] BEARDEN M，GARG S，LEE W J.Integrating goal specification in policy-based management[C]//Proc ofInt’l Workshop on Policies for Distributed Systems and Networks.London:Springer-Verlag，2001:153-170.

[10]QIAO Lin，IYER B R，AGRAWAL D，et al.PulStore: automated storage management with QoS guarantee in large-scale virtualized storage systems[C]//Proc of IEEE International Conference on Autono-mic Computing (ICAC).2005.

[11]KARLSSON M，KARAMANOLIS C，ZHU X.Triage:performance isolation and differentiation for storage systems[C]//Proc of the 12th Int’l Workshop on Quality of Service.New York:[s.n.]，2004.

[12]ZHANG Jian-yong，SIVASUBRAMANIAM A，WANG Qian，et al.Sto-rage performance virtualization via throughput and latency control[C]//Proc of the 3rd IEEE Internadional Symposium on Modeling， Analysis and Simulation of Computer and Telecommunication Systems.2005:135-142.