基于排隊網(wǎng)絡RAID存儲系統(tǒng)的性能評價模型

張 燕, 胡英堅, 姜 濤

(1.空軍航空大學基礎(chǔ)部,吉林長春 130022;2.長春工業(yè)大學機電工程學院,吉林長春 130012)

0 引 言

存儲系統(tǒng)是計算機系統(tǒng)的重要組成部分,如何準確地預測和評價存儲系統(tǒng)的性能,及時發(fā)現(xiàn)系統(tǒng)設計中的瓶頸和主要的性能影響因素,是提高存儲系統(tǒng)性能的先決條件。RAID技術(shù)是一種使用非常廣泛的存儲技術(shù),目前,對于這種存儲系統(tǒng)的性能評價模型大多數(shù)是基于硬件RAID的性能分析[1],與硬件RAID控制器相比,軟件RAID具有廉價、靈活性高等特點,是低端服務器存儲系統(tǒng)的最佳解決方案,但是對軟件RAID的定量分析工作很少[2]。文中針對磁盤陣列讀寫流程的特點,采用閉合排隊網(wǎng)絡的建模方法對軟件RAID的性能進行了評價,并通過實驗證明了該方法基本可以反映真實系統(tǒng)的性能狀況。

1 排隊網(wǎng)絡的基礎(chǔ)知識

排隊網(wǎng)絡屬于排隊論中的一個分支,利用排隊網(wǎng)絡模型,可以分析和評價系統(tǒng)的多種性能指標。

1.1 排隊網(wǎng)絡的的概念

一個排隊網(wǎng)絡是一個有向圖G=(V,E),由一組頂點V={1,2,…,M}和一組邊E?V×V組成,每個節(jié)點代表一個服務站(Service Center),服務站包括一個隊列和多個服務員,E是邊的集合,表示顧客流的可能通路。

一般采用節(jié)點的服務時間和節(jié)點之間的選道概率來刻畫工作負載,最簡單的排隊網(wǎng)絡是所有的顧客具有完全相同的性,稱為單一類別排隊網(wǎng)絡。同一網(wǎng)絡中如果存在多種不同類型的顧客,稱為多類排隊網(wǎng)絡,這種情況下,每類顧客具有不同的選道行為。如果網(wǎng)絡中的顧客數(shù)為常數(shù),所有顧客永遠循環(huán)流動,這樣的排隊網(wǎng)格稱為閉合排隊網(wǎng)絡。

1.2 基本運算定律

運算定律抽象出了計算機系統(tǒng)多種性能間的關(guān)系,忽略系統(tǒng)中性能因素的隨機行為,可以快速分析系統(tǒng)的平均性能。

little定律:

式中:N——隊列系統(tǒng)中的平均顧客數(shù);

X——系統(tǒng)的平均吞吐量;

R——系統(tǒng)對顧客的平均響應時間。

1)服務節(jié)點的類型為下列情況之一:

服務規(guī)則為處理器共享節(jié)點,服務由隊列中所有顧客平等分享;

服務規(guī)則為先來先服務;

服務規(guī)則為后來先服務,搶占式;

無限服務員節(jié)點或者延時節(jié)點,為顧客立即提供服務,服務時間服從一定分布。

2)服務節(jié)點的服務時間為以下幾種類型之一:

單服務員固定速率;

無限服務員,適用于上面提到的延時節(jié)點。

1.3 排隊網(wǎng)絡的分析方法

采用平均值法(MVA)對RAID系統(tǒng)進行分析,這種方法可以避免復雜的穩(wěn)定狀態(tài)概率。多類顧客閉合排隊網(wǎng)絡[3]的MVA分析方法如下:

假設一個閉合排隊網(wǎng)絡中有C類顧客,用向量M=(M1,M2,…,MC)表示,其中Mc代表第c(0＜c＜C)類顧客在網(wǎng)絡中的個數(shù),假設排隊網(wǎng)絡中有K個服務節(jié)點,對于每一個服務節(jié)點k,Vc,k代表第c類顧客對服務節(jié)點k的訪問概率。Sc,k代表服務節(jié)點k對c類顧客的平均服務時間,則節(jié)點k對c類顧客的服務需求為:Dc,k=Vc,k*Sc,k,用X表示吞吐量(Xc代表整個系統(tǒng)對c類顧客的吞吐量,Xk表示節(jié)點k的吞吐量,其它符號以此類推),R代表響應時間,Q代表隊列長度,則多類顧客閉合排隊網(wǎng)絡的MVA分析法基于以下3個基本公式[4-5]:

1)對于c類顧客,在節(jié)點k的平均響應時間Rc,k等于顧客排隊時間和服務時間之和,對于單隊列節(jié)點,表示為:

2)對于c類顧客在整個系統(tǒng)的吞吐量Xc(M)表示為:

3)對c類顧客,在節(jié)點k的排隊長度表示為Qc,k(M)=Xc(M)*Rc,k(M),于是節(jié)點k的總的隊列長度為:

式(1)～式(3)對網(wǎng)絡中任務數(shù)形成一種遞歸關(guān)系,每遞歸一次,系統(tǒng)中將減少一個顧客。因此,只要給出遞歸初始條件,該算法即可在有限步之內(nèi)計算出整個系統(tǒng)的吞吐量和平均響應時間。遞歸初始條件是顯然的,對第k個節(jié)點,在系統(tǒng)顧客數(shù)為0時:

2 軟件RAID系統(tǒng)的性能評價模型

用上述方法對軟件RAID系統(tǒng)建立性能評價模型,利用評價模型對RAID系統(tǒng)進行分析。

2.1 模型的建立

影響軟件RAID性能主要有3個部件:CPU、內(nèi)存以及磁盤驅(qū)動器。CPU節(jié)點處理請求的映射以及校驗計算,內(nèi)存緩沖條紋數(shù)據(jù),磁盤驅(qū)動器從內(nèi)存中接收讀寫請求,完成實際的I/O操作,這3個部件就為模型中的服務節(jié)點。對RAID系統(tǒng)的讀寫請求抽象為顧客。請求負載采用同步方式進行讀寫操作,也就是說在穩(wěn)定狀態(tài)下當一個請求結(jié)束后,CPU會馬上產(chǎn)生出一個類型和大小都相同的請求來代替,這樣,在一段時間內(nèi),系統(tǒng)中的請求數(shù)是一定的。

一個RAID系統(tǒng)實際上就是一個多類閉合排隊網(wǎng)絡。按照讀寫請求的流程,軟件RAID的排隊網(wǎng)絡模型如圖1所示。

圖1 軟件RAID系統(tǒng)的排隊網(wǎng)絡模型

圖中,讀寫請求由CPU節(jié)點發(fā)出,進入緩存節(jié)點,當請求的數(shù)據(jù)在緩存中存在時,讀寫命中,請求直接返回;否則,要經(jīng)過RAID映射程序,將請求下發(fā)到對應的磁盤節(jié)點上。

下面以實際的RAID5系統(tǒng)為例,討論其在不同負載條件下的性能。假設請求的大小為b(kB),各類節(jié)點的平均服務時間(用ST表示)的計算方式如下:

1)CPU節(jié)點:由于文中的系統(tǒng)完全是由軟件實現(xiàn)的,而且所進行的實驗對系統(tǒng)來說是一種壓力實驗,所以,將CPU抽象成為FCFS的排隊節(jié)點,其服務時間對所有任務是一個常數(shù)。

2)緩存節(jié)點:關(guān)鍵的問題是緩存命中率的問題,Linux RAID的調(diào)度機制存在著條紋預讀機制,緩存命中率和請求的順序程度有關(guān)。當對RAID5的某個條紋單元進行讀寫操作的時候,總是會將相關(guān)的整個條紋進行預讀,這樣對于順序的請求緩存命中率就比較高。文中討論的緩存命中僅指讀請求命中,對于寫請求,從系統(tǒng)的可靠性考慮,一般采用同步寫方式。預讀命中的概率可以采用如下方法計算:

一次實際磁盤操作讀取的數(shù)據(jù)大小Sdisk_read為請求大小Sread_req和預讀大小Sread_ahead之和,表示為:

定義一個順序度的概念,用Pseq表示。順序度表示順序請求在整個請求負載中所占的比率。如果請求負載是完全隨機的,則順序度為0;如果是完全順序的請求,則順序度為1。有了這一概念,那么一次實際的磁盤讀取操作能夠滿足的讀請求命中的個數(shù)為:

也就是說,經(jīng)歷Nreq_per_disk_read次讀請求就需要進行一次磁盤操作,也就是緩存不命中,于是緩存不命中的概率為1/Nreq_per_disk_read,所以預讀的緩存命中率為:

則緩存節(jié)點平均服務時間表示為:

3)磁盤節(jié)點:一次磁盤操作包括磁盤尋道時間、磁盤旋轉(zhuǎn)時間和數(shù)據(jù)傳輸時間,前兩者統(tǒng)稱為定位時間。磁盤定位時間是磁盤隊列長度的函數(shù),二者的關(guān)系為:

而磁盤傳輸時間為數(shù)據(jù)量的線性函數(shù)表示為:

式中:b——傳輸數(shù)據(jù)量大小;

Vdisk——磁盤的傳輸速率。

為了簡化計算,我們忽略磁盤的定位時間,所以:

2.2 讀寫請求服務的需求分析

對RAID系統(tǒng)的應用主要包括單用戶的大數(shù)據(jù)訪問和多用戶的隨機訪問,而RAID5對大數(shù)據(jù)寫和小數(shù)據(jù)寫的處理方式完全不同,所以將請求負載分為讀數(shù)據(jù)、大數(shù)據(jù)寫和小數(shù)據(jù)寫3類,它們對各節(jié)點的服務需求是不同的。

2.2.1 讀和大數(shù)據(jù)寫請求服務需求分析

大數(shù)據(jù)寫請求是指請求的數(shù)據(jù)遠遠大于RAID5條紋的長度,這樣在RAID層為完全條紋寫的方式。這種方式和讀請求的數(shù)據(jù)流程基本一致,只是有以下幾點不同:

1)討論的為同步方式,所以大數(shù)據(jù)寫的緩存命中率為0。

2)大數(shù)據(jù)寫增加了為計算校驗單元而進行異或運算的時間,所以,CPU節(jié)點的平均響應時間要高于讀操作。

3)由于RAID5的驅(qū)動程序需要生成新的校驗冗余信息,所以,大數(shù)據(jù)寫的實際寫的數(shù)據(jù)大小為:

式中:Sreq——請求大小;

Cstripe_len——RAID5條紋長度。

以上3點在計算服務需求時表現(xiàn)為輸入?yún)?shù)的不同,下面分別討論在讀(或大寫)請求下各個節(jié)點服務需求計算方法。

CPU節(jié)點的服務需求表示為:

緩存節(jié)點的服務需求表示為:

注意,此時的Sreq為實際請求大小(對于寫請求進行相應的轉(zhuǎn)換)。

磁盤節(jié)點的服務需求表示為:

式中:Ssub_req——每個磁盤的子請求的大小。

2.2.2 小數(shù)據(jù)寫的服務需求分析

小數(shù)據(jù)寫的過程是如果緩存中沒有請求的條紋就讀出整個條紋的數(shù)據(jù),然后改寫需要更新的條紋單元并計算校驗單元,再將改寫后的數(shù)據(jù)和校驗單元寫回到磁盤上,所以與大數(shù)據(jù)寫是不同的。

對于小數(shù)據(jù)寫請求,回寫磁盤包含校驗單元和修改后的數(shù)據(jù)單元兩個數(shù)據(jù)塊,所以訪問概率為2/Cstripe_len,因此小寫方式下磁盤服務的需求為:

式中:Sstripe_unit——整個條紋單元的大小;

Cstripe_len——條紋長度,也就是磁盤個數(shù)。

2.3 模型分析

前面給出了RAID5在不同負載條件下的服務需求,用MVA分析方法可以計算出RAID5的吞吐量和平均響應時間。除CPU節(jié)點外,磁盤節(jié)點和緩存節(jié)點在系統(tǒng)任務數(shù)為m時的平均響應時間表示為:

整個系統(tǒng)的平均響應時間為:

系統(tǒng)的吞吐量為:

由little定律,各節(jié)點的隊列長度可計算為:

以上公式構(gòu)成了遞歸關(guān)系,當m=1時,顯然Q*(m-1)=Q*(0)=0(*代表磁盤或者緩存節(jié)點),算法即可結(jié)束。

3 實 驗

通過實驗比較模型的理論值和實際系統(tǒng)的測試值,實驗參數(shù)見表1。

表1 實驗參數(shù)表

測試對象為linux RAID5的磁盤陣列,實驗數(shù)據(jù)分為3組,分別對應了讀請求、大數(shù)據(jù)寫請求和小數(shù)據(jù)寫請求的理論值和實測值。

RAID5讀請求性能曲線如圖2所示。

圖2 RAID5讀請求性能曲線

RAID5大數(shù)據(jù)寫請求性能曲線如圖3所示。

圖3 RAID5大數(shù)據(jù)寫請求性能曲線

RAID5小數(shù)據(jù)寫請求性能曲線如圖4所示。

圖4 RAID5小數(shù)據(jù)寫請求性能曲線

從以上3個曲線可以看出,系統(tǒng)的吞吐量在低負載時增加非常明顯,隨著負載的增加,系統(tǒng)中某些部件已經(jīng)飽和,也就是總有任務在該節(jié)點排隊等待,此時系統(tǒng)的吞吐量很難再增加。由于各個服務節(jié)點的服務需求是不同的,在系統(tǒng)負載達到極限時,整個系統(tǒng)的吞吐量取決于服務需求最低的那個節(jié)點,理論值同樣反映了這一趨勢,雖然二者有些差距,但表現(xiàn)是一樣的。

4 結(jié) 語

通過以上的分析和實驗得出,多類顧客閉合排隊網(wǎng)絡模型可以反映真實RAID系統(tǒng)的性能狀況,采用這種模型對系統(tǒng)進行評價,可以在多種可行性方案中選擇性價比高的設計方案;可以發(fā)現(xiàn)影響系統(tǒng)性能的瓶頸部件,提出改進方法(可以預測現(xiàn)有系統(tǒng)中那些部件的性能及提高的程度)。另外,它的工作量和費用比其它評價方法要小很多,因此,這種方法具有一定的實用性。

[1] M Uysal,G Alvarez A Merchant.A modular,analytical throughput model for modern disk arrays[C]//Proc.of the 9th Intl.Symp.on Modeling,Analysis and Simulation on Computer and Telecommunications Systems(MASCOTS),2001:183-192.

[2] Dan Feng,Hong Jiang,Yi-feng Zhu.I/O performance of an RAID10 style parallel file system[C]//Journal Computer.Sci.and Technology Nov,2004:965-972.

[3] Anand Kuratti,William H.Sanders performance analysis of RAID5 disk array[C]//Hawaii USA:Proceedings ofthe IEEE International Computer Performance and Dependability Symposium,1995:236-246.

[4] Shenze Chen,Don Towsley.A performance evalution of RAID Architectures[J].IEEE Transaction on Computers,1996,45(6):1116-1130.

[5] R Onvural.Survey of closed queueingnetworks with blocking[J].ACM Computing Surveys,1990,22(2):83-21.

[6] E Varki,A Merchant,J Xu,et al.Issues and challenges in the performance analysis of real disk arrays[J].IEEE Transactions on Parallel and Distributed Systems,2004,15(6):21-50.

[7] M Reiser,S S Lavenberg.Mean-value analysis of closed multichain queuing networks[J].Journal of the Association for Computing Machinery,1980,27(2):313-322.

[8] 謝斌,蔣寧,姜濤.某型航空發(fā)動機溫度限制系統(tǒng)檢測儀的硬件設計[J].長春工業(yè)大學報:自然科學版,2010,31(2):171-175.