一種提高N-Code可擴(kuò)展性的數(shù)據(jù)重組方案

劉靖宇,李蕭言,李浩鵬,李 娟,武優(yōu)西

(河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院，天津 300401)

1 引 言

獨(dú)立磁盤(pán)冗余陣列(Redundant Arrays of Independent Disks,RAID)將多個(gè)磁盤(pán)組合[1],形成統(tǒng)一的邏輯存儲(chǔ)設(shè)備,實(shí)現(xiàn)并行工作以提高存儲(chǔ)系統(tǒng)的性能、容量和可靠性[2].隨著大數(shù)據(jù)時(shí)代的深入[3],數(shù)據(jù)指數(shù)型增長(zhǎng)對(duì)RAID的存儲(chǔ)能力和I/O帶寬提出更高的要求和挑戰(zhàn),提高RAID的可擴(kuò)展性成為存儲(chǔ)系統(tǒng)迫切需要解決的重要問(wèn)題[4].對(duì)于RAID系統(tǒng)的擴(kuò)展有替換和擴(kuò)容兩種基本策略,替換策略是用新的容量更大的磁盤(pán)陣列整體代替舊陣列,數(shù)據(jù)遷移量大,遷移時(shí)間長(zhǎng),無(wú)法為用戶提供高質(zhì)量服務(wù)響應(yīng),且舊磁盤(pán)陣列沒(méi)有充分利用.鑒于這種策略的種種不足,通常選擇使用擴(kuò)容策略,即在現(xiàn)有RAID陣列中增加新磁盤(pán),從而形成具有更大容量和I/O帶寬的新磁盤(pán)陣列[5].

RAID存儲(chǔ)技術(shù)經(jīng)過(guò)多年的發(fā)展,形成了RAID0,RAID1,RAID4,RAID5等擴(kuò)容策略應(yīng)用良好的存儲(chǔ)系統(tǒng).然而在大規(guī)模存儲(chǔ)系統(tǒng)中,多個(gè)磁盤(pán)發(fā)生故障的可能性更高.RAID1采用的鏡像技術(shù)具有高數(shù)據(jù)可靠性但是空間利用率僅有50%,RAID0,RAID4和RAID5無(wú)法在多個(gè)磁盤(pán)失效的情況下提供數(shù)據(jù)保護(hù).而RAID6采用的雙奇偶校驗(yàn)使磁盤(pán)陣列在充分利用存儲(chǔ)空間的基礎(chǔ)上,提高了存儲(chǔ)系統(tǒng)的容錯(cuò)能力,被廣泛部署在現(xiàn)代存儲(chǔ)集群和數(shù)據(jù)中心,其中以基于最大距離可分碼(Maximum Distance Separated,MDS)實(shí)現(xiàn)的RAID6最為典型[6].不同于布局相對(duì)統(tǒng)一的低層級(jí)RAID,基于MDS編碼實(shí)現(xiàn)的RAID6具有多樣性和復(fù)雜性,擴(kuò)容過(guò)程中數(shù)據(jù)布局變化大,使擴(kuò)容方案的研究面臨極大的挑戰(zhàn).

RAID6系統(tǒng)擴(kuò)容時(shí),為了使新磁盤(pán)陣列負(fù)載均衡需要遷移部分?jǐn)?shù)據(jù)到新磁盤(pán)[7].數(shù)據(jù)遷移會(huì)造成額外的磁盤(pán)I/O來(lái)維持RAID6的雙奇偶校驗(yàn)布局,保證存儲(chǔ)系統(tǒng)的高可靠性.高效的RAID6擴(kuò)容方案應(yīng)在短時(shí)間內(nèi)完成數(shù)據(jù)重組,且具備數(shù)據(jù)遷移量少,擴(kuò)容開(kāi)銷(xiāo)低等特點(diǎn)[8].

目前提出了多種RAID6 MDS陣列碼,為RAID0,RAID4和RAID5設(shè)計(jì)的擴(kuò)容方案不能適用于這些復(fù)雜多樣的RAID6編碼,因此需要根據(jù)各RAID6編碼的特點(diǎn),設(shè)計(jì)具有針對(duì)性的有效擴(kuò)容方案.N-Code[9]是一種具有最佳存儲(chǔ)效率,編解碼計(jì)算復(fù)雜度和更新復(fù)雜度的MDS RAID6編碼,本文主要解決N-Code RAID6擴(kuò)容問(wèn)題.

本文提出一種提高N-Code RAID6可擴(kuò)展性的新型數(shù)據(jù)重組方案Cross-Scale.不同于現(xiàn)有研究中的單一擴(kuò)容方案,該方案根據(jù)磁盤(pán)陣列剩余空間動(dòng)態(tài)選擇擴(kuò)容方法.本文的主要貢獻(xiàn)有:1)定義了擴(kuò)容閾值,將每個(gè)磁盤(pán)的剩余空間與擴(kuò)容閾值作比較選擇不同的策略,以適應(yīng)任意磁盤(pán)陣列狀態(tài);2)根據(jù)N-Code的編碼特點(diǎn)提出了陣列標(biāo)準(zhǔn)化策略,使擴(kuò)容后陣列維持原編碼布局;3)提出了快速數(shù)據(jù)遷移策略來(lái)減少奇偶校驗(yàn)更新的開(kāi)銷(xiāo),提高擴(kuò)容效率.

2 相關(guān)工作

2.1 現(xiàn)有擴(kuò)容方案

傳統(tǒng)的基于輪詢?cè)L問(wèn)的RR[10]是最簡(jiǎn)單且應(yīng)用范圍最廣的擴(kuò)容方案,但是重新分布所有數(shù)據(jù)導(dǎo)致其有接近100%的數(shù)據(jù)遷移率.Goel Ashish等人提出的SCADDAR[11]利用偽隨機(jī)函數(shù)將計(jì)算出的遷移后地址為新磁盤(pán)的數(shù)據(jù)塊移動(dòng),解決了RR方案中遷移開(kāi)銷(xiāo)高的問(wèn)題,但是連續(xù)多次擴(kuò)容不能保證數(shù)據(jù)均勻分布,降低了擴(kuò)容后的訪問(wèn)性能.Zheng等人提出的FastScale[12]針對(duì)RAID0提出將劃定的平行四邊形區(qū)域中的數(shù)據(jù)遷移到新磁盤(pán),不再要求擴(kuò)容后的數(shù)據(jù)滿足輪詢?cè)L問(wèn),為之后的擴(kuò)容方案設(shè)計(jì)提供了新思路.此外,研究者針對(duì)具有相對(duì)統(tǒng)一布局的RAID4和RAID5系統(tǒng)提出了多種擴(kuò)容方案,例如USR4和ISM[13],這些方案在布局簡(jiǎn)單的低層級(jí)RAID上應(yīng)用良好,但直接應(yīng)用于復(fù)雜多樣的RAID6系統(tǒng)時(shí),會(huì)帶來(lái)巨大的擴(kuò)容開(kāi)銷(xiāo).

Wang等人提出的SDM[14]針對(duì)RAID6提出了一種條帶級(jí)擴(kuò)容方案,它將磁盤(pán)陣列劃分為條帶集,其中各條帶分別采用了不同的數(shù)據(jù)遷移方法,根據(jù)擴(kuò)容后的編碼布局決定數(shù)據(jù)移動(dòng)的位置.近年來(lái)根據(jù)不同RAID6編碼的特點(diǎn)提出了具有針對(duì)性的擴(kuò)容方案.其中Zhang等人提出的RS6是基于橫向編碼RDP提出的擴(kuò)容方案[15],RS6為了維持RAID6的編碼布局提出了陣列標(biāo)準(zhǔn)化方法,根據(jù)最佳遷移參數(shù)確定新盤(pán)增加的位置和數(shù)據(jù)遷移區(qū)域.數(shù)據(jù)移動(dòng)時(shí)要充分利用原校驗(yàn)鏈,采用PiggyBack技術(shù)[16]更新校驗(yàn)值,使校驗(yàn)值更新的開(kāi)銷(xiāo)最小.HCS[17]和HS6[18]都是基于H-Code提出的擴(kuò)容方案,其中Xia等人提出的HCS通過(guò)對(duì)比擴(kuò)容前后的陣列選擇需要調(diào)整位置的對(duì)角數(shù)據(jù)塊遷移到相應(yīng)位置,在擴(kuò)容過(guò)程中不需要更新校驗(yàn)值.Yuan等人提出的HS6體現(xiàn)了最少數(shù)據(jù)遷移量和快速擴(kuò)容等特性,最大程度保留了原有的校驗(yàn)數(shù)據(jù).Zhang等人提出的Xscale和Jin等人提出的DEC分別基于縱式編碼X-Code和D-Code設(shè)計(jì)了擴(kuò)容方案,二者劃定遷移區(qū)域,將其中的數(shù)據(jù)只遷移到新磁盤(pán),最小化數(shù)據(jù)遷移量[19,20].

2.2 N-Code編碼布局

N-Code是一種RAID6 MDS陣列碼,其編碼陣列滿足(p-1)×(p+1)的布局,p為大于2的質(zhì)數(shù),水平校驗(yàn)塊和對(duì)角校驗(yàn)塊組成形如字母N的簡(jiǎn)單幾何結(jié)構(gòu),使布局具有中心對(duì)稱的特點(diǎn).校驗(yàn)塊分為兩個(gè)類(lèi)型:水平校驗(yàn)塊放置在中間的p-1個(gè)磁盤(pán),對(duì)角校驗(yàn)塊均勻分布在第一個(gè)和最后一個(gè)磁盤(pán),數(shù)據(jù)塊分散在所有的邏輯磁盤(pán)中.圖1為p=5時(shí)的一個(gè)N-Code編碼陣列,相同字母標(biāo)記的塊屬于同一校驗(yàn)鏈,圖1(a)所示為水平校驗(yàn)鏈,圖1(b)所示為對(duì)角校驗(yàn)鏈.

圖1 p=5時(shí)一個(gè)N-Code編碼陣列Fig.1 Layout and construction rules of N-Code with p=5

2.3 研究動(dòng)機(jī)

通過(guò)分析現(xiàn)有的RAID6擴(kuò)容方案,擴(kuò)容方案的設(shè)計(jì)存在兩個(gè)方面的問(wèn)題:

1)RAID6擴(kuò)容方案通常通過(guò)條帶拼接來(lái)維持原編碼陣列,邏輯拼接空白條帶的方法,校驗(yàn)值更新少,可以大幅度減少擴(kuò)容的開(kāi)銷(xiāo),但需要磁盤(pán)具有一定的冗余空間[21];多條帶之間邏輯拼接的方法沒(méi)有磁盤(pán)冗余空間的限制,但增加了方案設(shè)計(jì)的難度且擴(kuò)容開(kāi)銷(xiāo)大.現(xiàn)有方案應(yīng)用單一的條帶拼接方法,缺乏對(duì)磁盤(pán)剩余空間的定量分析,適用的磁盤(pán)陣列狀態(tài)受到限制.

2)現(xiàn)有的擴(kuò)容方案中,校驗(yàn)塊部署在特定條帶或者特定磁盤(pán)中,數(shù)據(jù)遷移時(shí)僅考慮數(shù)據(jù)塊的移動(dòng)即可.而N-Code的校驗(yàn)塊分布在所有磁盤(pán)上,沒(méi)有專(zhuān)用的校驗(yàn)盤(pán),擴(kuò)容時(shí)還需考慮校驗(yàn)塊的部署,特殊的布局還導(dǎo)致磁盤(pán)間緊密耦合,給擴(kuò)容方案的設(shè)計(jì)帶來(lái)困難.

為解決以上問(wèn)題,本文提出一種基于N-Code編碼的快速擴(kuò)容方案Cross-Scale,提高擴(kuò)容效率的同時(shí)保持了N-Code原編碼布局.

3 Cross-Scale方案

Cross-Scale方案中提出了擴(kuò)容閾值的定義,根據(jù)擴(kuò)容閾值與各磁盤(pán)陣列剩余空間的關(guān)系選擇不同的擴(kuò)容策略.下面詳細(xì)介紹Cross-Scale方案的工作原理.

3.1 擴(kuò)容閾值

為了確定磁盤(pán)在何種狀態(tài)下可以采用拼接空白條帶的方式來(lái)減少擴(kuò)容開(kāi)銷(xiāo),提出了擴(kuò)容閾值的概念.在磁盤(pán)陣列中,每個(gè)磁盤(pán)劃分為大小相同的D個(gè)磁盤(pán)塊,簡(jiǎn)稱塊.定義擴(kuò)容閾值CT(Capacity Threshold)為一個(gè)磁盤(pán)塊數(shù)(D)與第t次擴(kuò)容后一個(gè)編碼陣列增加的條帶數(shù)(Sad)占第t次擴(kuò)容時(shí)一個(gè)編碼陣列條帶總數(shù)(St)的比值的乘積,如公式(1)所示:

(1)

若磁盤(pán)陣列從6塊盤(pán)(p=5)增加到8塊盤(pán)(p=7),每個(gè)編碼陣列中的條帶數(shù)由4條增加到6條,Sad=2,St=6,那么擴(kuò)容閾值CT=D×2/6=1/3D.

擴(kuò)容前將檢查舊磁盤(pán)陣列中每個(gè)磁盤(pán)中的空白塊數(shù)量,第i個(gè)磁盤(pán)中的空白塊數(shù)量記為T(mén)i,存儲(chǔ)在一個(gè)數(shù)組中,通過(guò)遍歷數(shù)組,找到陣列中空白塊剩余最少的磁盤(pán)dmin,磁盤(pán)dmin的空白塊數(shù)為T(mén)min.若Tmin超過(guò)閾值CT,則說(shuō)明整個(gè)磁盤(pán)陣列有超過(guò)CT條空白條帶,即可以采用拼接空白條帶的方法.Cross-Scale方案在0≤Tmin

3.2 陣列標(biāo)準(zhǔn)化

RAID6擴(kuò)容時(shí),隨著參數(shù)p的改變,編碼陣列中的磁盤(pán)數(shù)與條帶數(shù)均會(huì)改變,擴(kuò)容前需要確定新磁盤(pán)增加的位置和新增條帶的位置,這個(gè)過(guò)程稱為陣列標(biāo)準(zhǔn)化.

在一個(gè)(p-1)×(p+1)的N-Code編碼陣列中,共有p×(p+2)種組合方式.N-Code的編碼陣列具有中心對(duì)稱的特點(diǎn),則共有p×((p+1)/2+1)個(gè)不重復(fù)的組合方式.由于N-Code沒(méi)有專(zhuān)門(mén)存放校驗(yàn)塊的磁盤(pán),因此擴(kuò)容時(shí)不僅要對(duì)數(shù)據(jù)塊進(jìn)行處理,還要考慮校驗(yàn)塊是否滿足編碼布局.現(xiàn)有的可以應(yīng)用于N-Code的擴(kuò)容方案有一大部分?jǐn)U容開(kāi)銷(xiāo)來(lái)源于維持N-Code原編碼布局,為了減少這部分?jǐn)U容開(kāi)銷(xiāo),Cross-Scale在各種組合方式中選擇與擴(kuò)容后編碼布局最相近的組合,即在增加磁盤(pán)和條帶后選擇符合擴(kuò)容后編碼規(guī)則最多塊數(shù)的組合方式.

表1 不同組合方式下符合編碼規(guī)則的塊數(shù)Table 1 Number of blocks conforming to coding rules in different combinations

通過(guò)取不同p值進(jìn)行分析,N-Code在其磁盤(pán)陣列1/2處增加磁盤(pán)且在各編碼陣列1/2處增加條帶時(shí)可以有效減少擴(kuò)容開(kāi)銷(xiāo).

對(duì)于磁盤(pán)的增加,若原磁盤(pán)陣列中共有m個(gè)磁盤(pán),其中第i個(gè)磁盤(pán)的磁盤(pán)號(hào)為di(0≤i≤m-1).增加的新磁盤(pán)數(shù)為n,編碼第t次擴(kuò)容時(shí)的參數(shù)p為pt,則n為pt與pt-1的差.這n個(gè)新磁盤(pán)的原始數(shù)據(jù)在加入磁盤(pán)陣列前將被清零,這個(gè)清零操作不會(huì)占用擴(kuò)容時(shí)間.新磁盤(pán)增加后則根據(jù)公式(2)和公式(3)為磁盤(pán)陣列重新調(diào)整磁盤(pán)編號(hào).

第j(0≤j≤n-1)塊新磁盤(pán)的盤(pán)號(hào)dj,則:

(2)

(3)

如圖2左圖所示,原磁盤(pán)陣列有6塊磁盤(pán),增加2塊新磁盤(pán).此時(shí)pt-1=5,若舊磁盤(pán)盤(pán)號(hào)小于3則盤(pán)號(hào)不變,其它舊磁盤(pán)盤(pán)號(hào)分別增加2,新磁盤(pán)盤(pán)號(hào)經(jīng)計(jì)算分別為3和4.

圖2 0≤Tmin

對(duì)于編碼陣列中的條帶,目前已知條帶增加的位置,下面介紹增加哪些條帶以及如何增加條帶.

Cross-Scale通過(guò)條帶拼接的方式來(lái)維持N-Code的編碼布局,在磁盤(pán)的邏輯視圖操作,實(shí)際上并不會(huì)產(chǎn)生數(shù)據(jù)遷移.磁盤(pán)陣列中,所有磁盤(pán)上具有相同塊號(hào)的塊構(gòu)成一個(gè)條帶(Stripe),一個(gè)編碼陣列中包含了p-1個(gè)Stripes,這部分Stripes的集合稱為Set.條帶拼接時(shí)將部分Stripes邏輯拼接到其它Set中,這部分Stripes稱為拼接條帶.

情況1.當(dāng)0≤Tmin

通過(guò)舊編碼陣列的邏輯條帶號(hào)Vt-1計(jì)算擴(kuò)容所需的參數(shù),其中L為St-1和St的最小公倍數(shù),一個(gè)Region中包含L個(gè)Stripes,Region是該條件下擴(kuò)容的基本單位,各Region中的條帶拼接方法是相同的.r為各Region的編號(hào),lr是一個(gè)Region中的邏輯條帶號(hào),s是一個(gè)Region中的Set編號(hào),ls是一個(gè)Set中的邏輯條帶號(hào).擴(kuò)容前每個(gè)Region中有L/St-1個(gè)Sets,擴(kuò)容后每個(gè)Region中有L/(St-1+Sad)個(gè)Sets,前L/(St-1+Sad)個(gè)Sets保留,調(diào)整保留Sets中條帶的邏輯條帶號(hào)為拼接條帶的加入提供位置,其余(L/St-1-L/(St-1+Sad))個(gè)Sets中Stripes為拼接條帶,首先調(diào)用Grouping算法將拼接條帶分組,再邏輯拼接到保留Set中,最后獲得擴(kuò)容后新陣列的邏輯條帶號(hào)Vt.SplicingS算法表述如算法1所示.

算法1.SplicingS

輸入:擴(kuò)容次數(shù)t,第t-1次擴(kuò)容的邏輯條帶號(hào)Vt-1,編碼陣列條帶數(shù)St-1,擴(kuò)容增加的條帶數(shù)Sad

輸出:陣列標(biāo)準(zhǔn)化后的邏輯條帶號(hào)Vt

1.L←lcm(St-1,St-1+Sad);

2.r←Vt-1/L;

3.lr←Vt-1modL;

4.s←lr/St-1;

5.ls←lrmodSt-1;

6. IF(s

7. 掃描被保留的Set;

8. IF(ls

9.Vt←r×L+lr+Sad×s;

10. ELSE

11.Vt←r×L+lr+Sad×(s+1);

12. END IF

13.ELSE

14.Grouping()

15.將條帶拼接到保留Set中;

16.END IF

17.RETURNVt;

SplicingS算法中調(diào)用的條帶組合算法Grouping將拼接條帶分組,該算法使拼接條帶具有中心對(duì)稱的布局,使陣列標(biāo)準(zhǔn)化后對(duì)角校驗(yàn)塊分布的位置滿足編碼布局,具體內(nèi)容如下:

首先獲取一個(gè)Region中全部拼接條帶,一方面自上而下遍歷拼接條帶盤(pán)號(hào)為0的塊,每找到n/2個(gè)存儲(chǔ)對(duì)角校驗(yàn)值的塊,則將這些塊所在的條帶分為一小組.另一方面自下而上遍歷拼接條帶中盤(pán)號(hào)為m+n-1的塊,操作與前者相同.最后將組號(hào)相同的小組合并成一個(gè)組.分組后第一塊和最后一塊盤(pán)中的對(duì)角校驗(yàn)塊均勻分配,每組拼接條帶中各有n/2個(gè)條帶中的對(duì)角校驗(yàn)塊來(lái)自第一塊和最后一塊磁盤(pán).Grouping算法表述如算法2所示.

算法2.Grouping

輸入:拼接條帶集Setsp,編碼陣列條帶數(shù)St-1,擴(kuò)容增加的條帶數(shù)Sad,原磁盤(pán)數(shù)m,增加磁盤(pán)數(shù)n

輸出:條帶分組G

1. 將一個(gè)Region中所有拼接條帶集Setsp合并為Setsum;

2.i←0;j←0;k←0;

3. 自上而下掃描Setsum中盤(pán)號(hào)為0的塊;

4. WHILE(d0==P)DO

5. 將其所在的條帶每Sad/2個(gè)分為一組,g1[i]←lr;

6. END WHILE

7. 自下而上掃描Setsum中盤(pán)號(hào)為m+n-1的塊;

9. 將其所在的條帶每Sad/2個(gè)分為一組,g2[j]←lr;

10. END WHILE

11.G[k]←g1[i]∪g2[j];

12.RETUENG;

如圖2所示,在0≤Tmin

情況2.當(dāng)CT≤Tmin≤D時(shí),條帶拼接在空白條帶與原條帶之間進(jìn)行,通過(guò)算法SplicingB實(shí)現(xiàn),算法中拼接條帶增加到保留Set中的位置與SplicingS算法相同,區(qū)別在于拼接條帶是否包含數(shù)據(jù).具體內(nèi)容如下:

通過(guò)舊編碼陣列的邏輯條帶號(hào)Vt-1計(jì)算擴(kuò)容所需的參數(shù),其中s為擴(kuò)容前各Set的編號(hào),ls是一個(gè)Set中的邏輯條帶號(hào).將dmin中第一個(gè)空白塊所在的水平條帶記為lmin,lmin之前的條帶根據(jù)算法調(diào)整邏輯條帶號(hào),為拼接條帶的加入提供位置,lmin之后的條帶每n條按順序分為一組,組號(hào)為g,邏輯拼接到與其組號(hào)g具有相同Set編號(hào)s的保留Set中.如圖3所示,調(diào)整保留Set中原條帶的邏輯條帶號(hào),為每組2個(gè)拼接條帶提供加入的位置,若此時(shí)d1為空白塊最少的磁盤(pán)dmin,從d1第1個(gè)空白塊所在的stripe開(kāi)始,每2個(gè)stripes順序分為一組,依次拼接到保留Set中.SplicingB算法表述如算法3所示.

圖3 CT≤Tmin≤D時(shí)陣列標(biāo)準(zhǔn)化Fig.3 Normalizing operation when CT≤Tmin≤D

算法3.SplicingB

輸入:擴(kuò)容次數(shù)t,第t-1次擴(kuò)容的邏輯視圖Vt-1,編碼陣列條帶數(shù)St-1,增加條帶數(shù)Sad

輸出:條帶拼接后的邏輯視圖Vt

1.s←Vt-1/St-1;

2.ls←Vt-1modSt-1;

3. 從dmin中找到第一個(gè)空白塊,其行號(hào)記作lmin,將lmin后的條帶每n條分為一組,組號(hào)為g從0至lmin/St-1-1;

4.WHILEVt-1!=DO

5. IF(Vt-1

6. IF(ls

7.Vt←Vt-1+Sad×s;

8. ELSE

9.Vt←Vt-1+Sad×(s+1);

10. END IF

11. ELSE

12. 根據(jù)組號(hào)g將條帶拼接到保留Set中;

13. END IF

14.END WHILE

15.RETURNVt;

3.3 數(shù)據(jù)遷移

數(shù)據(jù)遷移分為校驗(yàn)塊遷移和數(shù)據(jù)塊遷移.陣列標(biāo)準(zhǔn)化之后各Set中數(shù)據(jù)遷移方式是相同的.下面以一個(gè)Set為例介紹數(shù)據(jù)遷移方式.

校驗(yàn)塊遷移只發(fā)生在0≤Tmin

圖4 從p=5到p=7的數(shù)據(jù)遷移示意圖Fig.4 Data migration during scaling from p=5 to p=7

算法4.MovingP

輸入:陣列標(biāo)準(zhǔn)化后邏輯行號(hào)Vt,擴(kuò)容前數(shù)據(jù)磁盤(pán)號(hào)db

1. IF(lr∈G)THEN

2. IF(P &&lr∈gu)THEN

3. 水平校驗(yàn)塊盤(pán)號(hào)db循環(huán)調(diào)整為{m/2,(m+n)/2-1};

4. END IF

5. IF(P &&lr∈gd)THEN

6. 水平校驗(yàn)塊盤(pán)號(hào)db循環(huán)調(diào)整為{(m+n)/2,m/2+n-1};

7. END IF

8. END IF

對(duì)于數(shù)據(jù)塊,Cross-Scale方案中根據(jù)算法MovingD將數(shù)據(jù)塊遷移.數(shù)據(jù)塊遷移按照兩個(gè)基本規(guī)則進(jìn)行,以減少檢驗(yàn)值的更新:1)數(shù)據(jù)塊遷移始終保持在同一行中進(jìn)行;2)盡可能多的將數(shù)據(jù)塊移動(dòng)到原來(lái)的對(duì)角校驗(yàn)鏈中.

為方便描述,在一個(gè)Set中以拼接條帶為橫坐標(biāo)帶,新增加的磁盤(pán)為縱坐標(biāo)帶,將Set視為4個(gè)象限.權(quán)衡保留校驗(yàn)鏈數(shù)量和數(shù)據(jù)遷移量,0≤Tmin

算法5.MovingD

輸入:陣列標(biāo)準(zhǔn)化后的邏輯行號(hào)Vt,擴(kuò)容前數(shù)據(jù)的磁盤(pán)號(hào)db,數(shù)據(jù)遷移區(qū)域邊長(zhǎng)e

1. 掃描編碼陣列,根據(jù)數(shù)據(jù)遷移區(qū)域找到需要遷移的塊;

2. IF(數(shù)據(jù)塊位于第3象限)THEN

3.db′ ←(db+n)mod(m+n);

4. END IF

5. IF(數(shù)據(jù)塊位于第1象限)THEN

6.db′ ←(db-n)mod(m+n);

7. END IF

4 實(shí)驗(yàn)與分析

本節(jié)對(duì)Cross-Scale方案的性能進(jìn)行分析,并在1.60GHz CPU和2GB RAM的Ubuntu14.0 32位系統(tǒng)上采用磁盤(pán)模擬器Disksim進(jìn)行仿真實(shí)驗(yàn).所模擬的單個(gè)磁盤(pán)容量為128GB,條帶內(nèi)數(shù)據(jù)塊的大小為64KB,整個(gè)仿真過(guò)程處于離線模式下.實(shí)驗(yàn)中將6塊盤(pán)組成的RAID6 N-Code在不同數(shù)據(jù)量的條件下擴(kuò)容5次,從影響擴(kuò)容效率的各項(xiàng)因素論證Cross-Scale方案的性能優(yōu)于目前可以應(yīng)用于N-Code的擴(kuò)容方案RR,SCADDAR和SDM.實(shí)驗(yàn)圖中以整數(shù)元組(m,n)表示原始磁盤(pán)數(shù)量和增加磁盤(pán)數(shù)量,①表示數(shù)據(jù)量為D-2CT,②表示數(shù)據(jù)量為D-CT,③表示數(shù)據(jù)量為D.

4.1 數(shù)據(jù)遷移率

數(shù)據(jù)遷移率的定義為:

(4)

RR將所有數(shù)據(jù)重新布局,產(chǎn)生了巨大的遷移成本.SCADDAR和SDM的大部分?jǐn)?shù)據(jù)僅在原磁盤(pán)和新磁盤(pán)之間遷移,所以數(shù)據(jù)遷移率低于RR,但由于N-Code的校驗(yàn)塊分布在所有磁盤(pán)上,沒(méi)有專(zhuān)用的校驗(yàn)盤(pán),因此需額外遷移數(shù)據(jù)來(lái)維持校驗(yàn)快的布局.不同擴(kuò)容方案在多次擴(kuò)容過(guò)程中的數(shù)據(jù)遷移率如圖5所示.

圖5表明,Cross-Scale方案在不同程度上降低了擴(kuò)容時(shí)的數(shù)據(jù)遷移率.在寫(xiě)入磁盤(pán)的數(shù)據(jù)量為D時(shí),與其它3種方案相比降低了30.43%～97.40%的數(shù)據(jù)遷移率,因?yàn)橹恍鑼澏ǖ倪w移區(qū)域中的數(shù)據(jù)塊和校驗(yàn)塊遷移,而且數(shù)據(jù)只在原磁盤(pán)和新磁盤(pán)之間遷移.若寫(xiě)入磁盤(pán)的數(shù)據(jù)量為D-2CT和D-CT,此時(shí)CT≤Tmin≤D,進(jìn)一步分析發(fā)現(xiàn),當(dāng)n≥(m-2)/2時(shí),數(shù)據(jù)遷移只發(fā)生在原磁盤(pán)和新磁盤(pán)之間,因此數(shù)據(jù)遷移率明顯低于其它3種方案.而當(dāng)n<(m-2)/2時(shí),部分?jǐn)?shù)據(jù)在原磁盤(pán)之間遷移,因此Cross-Scale的數(shù)據(jù)遷移率存在接近SCADDAR和SDM的情況,但是由劃定的遷移區(qū)域可知,當(dāng)CT≤Tmin≤D時(shí)一個(gè)編碼陣列中需遷移((m-2)/2)2+(m-2)/2個(gè)數(shù)據(jù)塊,由公式(4)可得其數(shù)據(jù)遷移率RdCT≤Tmin≤D,如公式(5)所示.由公式(5)可知數(shù)據(jù)遷移率隨著m的增大而減小,即隨著磁盤(pán)陣列增大,其數(shù)據(jù)遷移率在不斷降低.另外,降低數(shù)據(jù)遷移率可以減少數(shù)據(jù)移動(dòng)產(chǎn)生的I/O,但整個(gè)擴(kuò)容過(guò)程的開(kāi)銷(xiāo)由多個(gè)因素影響,Cross-Scale方案在最終結(jié)果中呈現(xiàn)最優(yōu).

圖5 數(shù)據(jù)遷移率比較Fig.5 Comparison of data migration ratio

(5)

4.2 擴(kuò)容開(kāi)銷(xiāo)

擴(kuò)容開(kāi)銷(xiāo)分為I/O操作和XOR操作兩部分.在I/O操作方面,擴(kuò)容過(guò)程中的I/O操作來(lái)自數(shù)據(jù)遷移和更新校驗(yàn)值帶來(lái)的數(shù)據(jù)讀寫(xiě),不同擴(kuò)容方案下的I/O操作數(shù)如圖6所示.

圖6 磁盤(pán)I/O操作數(shù)比較Fig.6 Comparison of the number of disk I/Os

圖6表明,Cross-Scale方案在不同擴(kuò)容情況下其I/O操作數(shù)均小于其它3種方案,減少了6.74%～73.37%的I/O操作數(shù).原因在于,RR需要遷移所有的數(shù)據(jù)塊,隨著磁盤(pán)陣列的擴(kuò)大,相應(yīng)需要遷移的數(shù)據(jù)塊增多,I/O操作數(shù)明顯增長(zhǎng).SCADDAR和SDM雖然降低了數(shù)據(jù)遷移率,但在更新校驗(yàn)值時(shí)需要額外讀出其它數(shù)據(jù)塊.而Cross-Scale方案在寫(xiě)入磁盤(pán)的數(shù)據(jù)量為D-2CT和D-CT時(shí),保留了全部原校驗(yàn)鏈,沒(méi)有奇偶校驗(yàn)更新,只有數(shù)據(jù)塊遷移,不需要額外讀出遷移區(qū)域外的數(shù)據(jù)塊,因此減少了I/O操作.當(dāng)寫(xiě)入磁盤(pán)的數(shù)據(jù)量為D時(shí),每個(gè)編碼陣列中有2e條校驗(yàn)鏈采用PiggyBack技術(shù),通過(guò)減少更新校驗(yàn)值時(shí)額外讀出的數(shù)據(jù)而減少I(mǎi)/O操作次數(shù).

(6)

一個(gè)校驗(yàn)鏈中若有bk個(gè)有效數(shù)據(jù),生成一個(gè)校驗(yàn)值則需要bk-1次XOR操作.那么兩種擴(kuò)容方案生成單校驗(yàn)值需要的XOR操作為NXOR1和NXOR2:

(7)

(8)

因此,若Ns1NXOR2,即擴(kuò)容過(guò)程中有效數(shù)據(jù)總量不變,若校驗(yàn)鏈數(shù)減少,則XOR操作增加.通過(guò)分析校驗(yàn)值修改率和校驗(yàn)鏈數(shù)量,得到不同擴(kuò)容方案在多次擴(kuò)容過(guò)程中的XOR操作數(shù),如圖7所示.

圖7 XOR操作數(shù)比較Fig.7 Comparison of the number of XOR operations calculation

圖7表明,當(dāng)寫(xiě)入磁盤(pán)的數(shù)據(jù)量為D-2CT和D-CT,Cross-Scale消除了XOR操作;當(dāng)寫(xiě)入磁盤(pán)的數(shù)據(jù)量為D,與其它3種擴(kuò)容方案相比Cross-Scale減少了6.13%～85.11%的XOR操作數(shù).原因在于,RR和SCADDAR在數(shù)據(jù)遷移率時(shí)未考慮保留原校驗(yàn)鏈,均需更新全部校驗(yàn)值,且RR校驗(yàn)鏈數(shù)少于SCADDAR,因此具有RR更多的XOR操作.SDM在擴(kuò)容過(guò)程中校驗(yàn)鏈的數(shù)量保持不變且根據(jù)水平校驗(yàn)鏈遷移數(shù)據(jù)塊,但是犧牲了一部分條帶來(lái)維持負(fù)載均衡,增加了對(duì)角校驗(yàn)值的修改率.而對(duì)于Cross-Scale,當(dāng)CT≤Tmin≤D時(shí),由于拼接的是空白條帶,沒(méi)有來(lái)自其它編碼陣列的數(shù)據(jù),因此經(jīng)數(shù)據(jù)遷移之后所有的校驗(yàn)鏈保持原鏈,避免了XOR操作;當(dāng)0≤Tmin

4.3 擴(kuò)容時(shí)間

擴(kuò)容時(shí)間受XOR操作數(shù)和I/O操作數(shù)影響,其中一個(gè)磁盤(pán)I/O耗時(shí)在毫秒級(jí),相比微秒級(jí)的XOR操作對(duì)擴(kuò)容時(shí)間的影響更明顯.與其它擴(kuò)容方案相比,Cross-Scale在每次擴(kuò)容過(guò)程中都具有良好的性能,與RR,SCADDAR,SDM相比減少了6.81%～73.39%的擴(kuò)容時(shí)間.不同擴(kuò)容方案下的擴(kuò)容時(shí)間如圖8所示.

圖8 擴(kuò)容總時(shí)間比較Fig.8 Comparison of total scaling time

在寫(xiě)入的數(shù)據(jù)量低于擴(kuò)容閾值時(shí),0≤Tmin

5 結(jié) 論

本文提出一種針對(duì)N-Code的擴(kuò)容方案Cross-Scale.方案中定義了擴(kuò)容閾值,根據(jù)擴(kuò)容閾值與磁盤(pán)陣列剩余空間的關(guān)系,選擇不同陣列標(biāo)準(zhǔn)化策略和快速數(shù)據(jù)遷移策略來(lái)維持原編碼布局,減少奇偶校驗(yàn)更新的開(kāi)銷(xiāo),提高擴(kuò)容效率.通過(guò)數(shù)學(xué)分析和仿真實(shí)驗(yàn)證明與現(xiàn)有的輪詢遷移方案相比,減少了擴(kuò)容過(guò)程中的數(shù)據(jù)遷移率、XOR操作和I/O操作數(shù),最終縮短了擴(kuò)容時(shí)間,并進(jìn)一步證明了在磁盤(pán)剩余容量充足的情況下選擇最佳擴(kuò)容方案的必要性和有效性.