基于排隊(duì)網(wǎng)絡(luò)RAID存儲(chǔ)系統(tǒng)的性能評(píng)價(jià)模型

張 燕, 胡英堅(jiān), 姜 濤

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

0 引 言

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

1 排隊(duì)網(wǎng)絡(luò)的基礎(chǔ)知識(shí)

排隊(duì)網(wǎng)絡(luò)屬于排隊(duì)論中的一個(gè)分支,利用排隊(duì)網(wǎng)絡(luò)模型,可以分析和評(píng)價(jià)系統(tǒng)的多種性能指標(biāo)。

1.1 排隊(duì)網(wǎng)絡(luò)的的概念

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

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

1.2 基本運(yùn)算定律

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

little定律:

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

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

R——系統(tǒng)對(duì)顧客的平均響應(yīng)時(shí)間。

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

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

服務(wù)規(guī)則為先來(lái)先服務(wù);

服務(wù)規(guī)則為后來(lái)先服務(wù),搶占式;

無(wú)限服務(wù)員節(jié)點(diǎn)或者延時(shí)節(jié)點(diǎn),為顧客立即提供服務(wù),服務(wù)時(shí)間服從一定分布。

2)服務(wù)節(jié)點(diǎn)的服務(wù)時(shí)間為以下幾種類型之一:

單服務(wù)員固定速率;

無(wú)限服務(wù)員,適用于上面提到的延時(shí)節(jié)點(diǎn)。

1.3 排隊(duì)網(wǎng)絡(luò)的分析方法

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

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

1)對(duì)于c類顧客,在節(jié)點(diǎn)k的平均響應(yīng)時(shí)間Rc,k等于顧客排隊(duì)時(shí)間和服務(wù)時(shí)間之和,對(duì)于單隊(duì)列節(jié)點(diǎn),表示為:

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

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

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

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

用上述方法對(duì)軟件RAID系統(tǒng)建立性能評(píng)價(jià)模型,利用評(píng)價(jià)模型對(duì)RAID系統(tǒng)進(jìn)行分析。

2.1 模型的建立

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

一個(gè)RAID系統(tǒng)實(shí)際上就是一個(gè)多類閉合排隊(duì)網(wǎng)絡(luò)。按照讀寫(xiě)請(qǐng)求的流程,軟件RAID的排隊(duì)網(wǎng)絡(luò)模型如圖1所示。

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

圖中,讀寫(xiě)請(qǐng)求由CPU節(jié)點(diǎn)發(fā)出,進(jìn)入緩存節(jié)點(diǎn),當(dāng)請(qǐng)求的數(shù)據(jù)在緩存中存在時(shí),讀寫(xiě)命中,請(qǐng)求直接返回;否則,要經(jīng)過(guò)RAID映射程序,將請(qǐng)求下發(fā)到對(duì)應(yīng)的磁盤(pán)節(jié)點(diǎn)上。

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

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

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

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

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

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

則緩存節(jié)點(diǎn)平均服務(wù)時(shí)間表示為:

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

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

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

Vdisk——磁盤(pán)的傳輸速率。

為了簡(jiǎn)化計(jì)算,我們忽略磁盤(pán)的定位時(shí)間,所以:

2.2 讀寫(xiě)請(qǐng)求服務(wù)的需求分析

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

2.2.1 讀和大數(shù)據(jù)寫(xiě)請(qǐng)求服務(wù)需求分析

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

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

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

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

式中:Sreq——請(qǐng)求大小;

Cstripe_len——RAID5條紋長(zhǎng)度。

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

CPU節(jié)點(diǎn)的服務(wù)需求表示為:

緩存節(jié)點(diǎn)的服務(wù)需求表示為:

注意,此時(shí)的Sreq為實(shí)際請(qǐng)求大小(對(duì)于寫(xiě)請(qǐng)求進(jìn)行相應(yīng)的轉(zhuǎn)換)。

磁盤(pán)節(jié)點(diǎn)的服務(wù)需求表示為:

式中:Ssub_req——每個(gè)磁盤(pán)的子請(qǐng)求的大小。

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

小數(shù)據(jù)寫(xiě)的過(guò)程是如果緩存中沒(méi)有請(qǐng)求的條紋就讀出整個(gè)條紋的數(shù)據(jù),然后改寫(xiě)需要更新的條紋單元并計(jì)算校驗(yàn)單元,再將改寫(xiě)后的數(shù)據(jù)和校驗(yàn)單元寫(xiě)回到磁盤(pán)上,所以與大數(shù)據(jù)寫(xiě)是不同的。

對(duì)于小數(shù)據(jù)寫(xiě)請(qǐng)求,回寫(xiě)磁盤(pán)包含校驗(yàn)單元和修改后的數(shù)據(jù)單元兩個(gè)數(shù)據(jù)塊,所以訪問(wèn)概率為2/Cstripe_len,因此小寫(xiě)方式下磁盤(pán)服務(wù)的需求為:

式中:Sstripe_unit——整個(gè)條紋單元的大小;

Cstripe_len——條紋長(zhǎng)度,也就是磁盤(pán)個(gè)數(shù)。

2.3 模型分析

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

整個(gè)系統(tǒng)的平均響應(yīng)時(shí)間為:

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

由little定律,各節(jié)點(diǎn)的隊(duì)列長(zhǎng)度可計(jì)算為:

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

3 實(shí) 驗(yàn)

通過(guò)實(shí)驗(yàn)比較模型的理論值和實(shí)際系統(tǒng)的測(cè)試值,實(shí)驗(yàn)參數(shù)見(jiàn)表1。

表1 實(shí)驗(yàn)參數(shù)表

測(cè)試對(duì)象為linux RAID5的磁盤(pán)陣列,實(shí)驗(yàn)數(shù)據(jù)分為3組,分別對(duì)應(yīng)了讀請(qǐng)求、大數(shù)據(jù)寫(xiě)請(qǐng)求和小數(shù)據(jù)寫(xiě)請(qǐng)求的理論值和實(shí)測(cè)值。

RAID5讀請(qǐng)求性能曲線如圖2所示。

圖2 RAID5讀請(qǐng)求性能曲線

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

圖3 RAID5大數(shù)據(jù)寫(xiě)請(qǐng)求性能曲線

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

圖4 RAID5小數(shù)據(jù)寫(xiě)請(qǐng)求性能曲線

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

4 結(jié) 語(yǔ)

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

[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ā)動(dòng)機(jī)溫度限制系統(tǒng)檢測(cè)儀的硬件設(shè)計(jì)[J].長(zhǎng)春工業(yè)大學(xué)報(bào):自然科學(xué)版,2010,31(2):171-175.