基于RAID-6的容量擴容布局研究

元 鑄，謝 平，耿生玲，張效娟

(青海師范大學 計算機學院，西寧 810008)

0 引 言

進入二十一世紀，數(shù)據(jù)的爆炸式增長，使社會進入了信息時代。數(shù)據(jù)的快速增長與現(xiàn)有存儲系統(tǒng)不匹配的問題，儼然成為了存儲系統(tǒng)的瓶頸。經(jīng)過科研人員的研究，提出了RAID[1](redundant arrays of independent disks)存儲技術。RAID存儲技術發(fā)展至今，形成了RAID-0，RAID-1，RAID-4[2-3]，RAID-5[4-5]等具有良好擴展性的存儲系統(tǒng)。RAID-1存儲系統(tǒng)的鏡像機制雖然提供了高數(shù)據(jù)可靠性但也導致存儲空間利用率偏低的問題；RAID-4和RAID-5存儲系統(tǒng)都允許單盤失效，但對存儲數(shù)據(jù)的可靠性還是存在一定的威脅。針對這些問題，學術界對具有更優(yōu)性能的RAID-6存儲系統(tǒng)的擴容算法展開研究，RAID-6[6-8]存儲系統(tǒng)與其他存儲方案相比，具有更高的數(shù)據(jù)冗余性能，可以允許2個數(shù)據(jù)盤同時失效也不會影響數(shù)據(jù)的使用。RAID-6存儲系統(tǒng)雙校驗盤機制，為數(shù)據(jù)提供了高可靠性和可恢復性，但在RAID-6擴容過程中其雙校驗機制也意味著校驗計算開銷較大，同時由于不同糾刪碼特殊布局結構的差異，使得對不同糾刪碼編碼的RAID-6存儲系統(tǒng)擴容算法的設計要求不同。H-Code[9]編碼是針對RAID-6存儲系統(tǒng)的一種編碼，該編碼具有水平校驗和斜校驗2條校驗鏈，保證了數(shù)據(jù)的安全性和可恢復性。RAID-6存儲系統(tǒng)因為2條校驗鏈的存在，采用Round-Robin[10]和Semi-RR[11]擴容算法進行擴容時會導致擴容時間長和計算開銷大的問題。所以，本文針對H-Code編碼的RAID-6存儲系統(tǒng)提出HS6擴容算法，該擴容算法只將一部分數(shù)據(jù)遷移到新磁盤，并不存在舊磁盤之間的數(shù)據(jù)遷移，減少了數(shù)據(jù)遷移量。同時，該擴容算法保證遷移數(shù)據(jù)只在同一校驗鏈中移動，最大程度保留了原有的校驗數(shù)據(jù)，極大地減少了XOR操作次數(shù)，降低了計算開銷。HS6擴容算法與Round-Robin擴容算法、Semi-RR擴容算法相比，擴容效率顯著提升，實現(xiàn)了快速高效的擴容。

1 傳統(tǒng)擴容算法

Round-Robin[10]擴容算法，也稱輪詢算法，該算法在擴容過程中，不僅需要在舊磁盤和新磁盤之間遷移數(shù)據(jù)，還需要在舊磁盤和舊磁盤之間遷移數(shù)據(jù)，該算法幾乎移動原來所有的數(shù)據(jù)塊，因此遷移數(shù)據(jù)量和計算開銷很大。第i次擴容過程fi(x)可形式化為

(1)

(1)式中：x為數(shù)據(jù)塊的邏輯塊號；Ni為第i次擴容后磁盤的個數(shù)；d為物理磁盤號；b為數(shù)據(jù)塊所在磁盤的物理塊號。

Semi-RR[11]擴容算法，只需要將一部分數(shù)據(jù)從舊磁盤遷移到新磁盤，因而具有較小的數(shù)據(jù)遷移量，但在多次擴容之后，其數(shù)據(jù)塊存在不均衡性布局的問題。第i次擴容過程gi(x)可形式化為

(2)

2 HS6擴容算法

采用H-Code編碼的RAID-6存儲系統(tǒng)具有水平和反對角線2條校驗鏈，增加了數(shù)據(jù)的安全性和可恢復性。H-Code編碼的RAID-6存儲系統(tǒng)只能為(p-1)×(p+1)布局，p為大于2的素數(shù)。當p為7，一個H-Code編碼RAID-6存儲系統(tǒng)為6×8的存儲條帶，如圖1。

圖1 H-Code編碼的RAID-6存儲系統(tǒng)Fig.1 H-Code encoded RAID-6 storage system

HS6是基于H-Code編碼技術針對RAID-6存儲系統(tǒng)提出的一種擴容算法。根據(jù)H-Code編碼具有2條校驗鏈的特性，HS6擴容算法充分考慮了最小數(shù)據(jù)遷移和最小化計算開銷的問題，并對其進行了實現(xiàn)。

實例1：如圖2，擴容前，當p=5時，RAID-6存儲系統(tǒng)為4×6的存儲條帶，擴容后，構成的存儲條帶必須滿足(p-1)×(p+1),p為素數(shù)的條件，所以加入2個新磁盤D5,D6構成6×8的存儲條帶(即p=7)，如圖3。

圖2 條帶為4*6的RAID-6存儲系統(tǒng)Fig.2 RAID-6 storage system with 4*6 stripes

圖3 向RAID-6存儲系統(tǒng)添加2個新磁盤Fig.3 Add two new disks to a RAID-6 storage system

加入新磁盤后，HS6擴容算法首先對存儲系統(tǒng)進行標準化，使存儲條帶滿足(p-1)×(p+1)，p為素數(shù)的條件，如圖4。在對存儲系統(tǒng)進行標準化時，為了最大程度地保留原來存儲條帶的結構，也為了減少數(shù)據(jù)遷移量和計算開銷。HS6擴容算法的標準化，采用將后面數(shù)據(jù)前調的做法。

圖4 RAID-6存儲系統(tǒng)的標準化Fig.4 Standardization of RAID-6 storage systems

在標準化之后，當p=7時，存儲系統(tǒng)中為6×8的存儲條帶，為了滿足所有斜校驗數(shù)據(jù)塊都處于反對角線上，對存儲系統(tǒng)中不在反對角線上的斜校驗塊進行遷移，如圖5。

圖5 將Q8、Q9、Q10、Q11斜校驗塊遷移到斜對角線上Fig.5 Move Q8, Q9, Q10, Q11 skew check blocks to diagonal diagonals

HS6擴容算法從舊磁盤遷移一定的數(shù)據(jù)到新磁盤，而且遷移數(shù)據(jù)只在同一校驗鏈移動，實現(xiàn)了水平校驗的計算開銷最小。同時，數(shù)據(jù)遷移到新磁盤后最大程度地保留了原來的斜校驗數(shù)據(jù)，使得斜校驗計算開銷也達到最小，即實現(xiàn)了計算開銷最小。

由圖2可知，未標準化之前Q0=1⊕6⊕11⊕12，Q1=2⊕7⊕8⊕13，Q2=3⊕4⊕9⊕14，Q3=0⊕5⊕10⊕15。加入2個新磁盤后，經(jīng)過標準化，變?yōu)?×8的存儲條帶。HS6擴容算法將一定的數(shù)據(jù)塊遷移到新磁盤，最大程度地保持原有斜校驗鏈的完整性，將數(shù)據(jù)遷移到新磁盤后，由于存儲條帶的擴大，斜校驗鏈發(fā)生了變化，如圖6，經(jīng)過標準化之后

Q0′=1⊕6⊕11⊕12⊕新數(shù)據(jù)⊕36，

所以Q0′=Q0⊕新數(shù)據(jù)⊕36；

Q1′=2⊕7⊕8⊕13⊕32⊕37，

所以Q1′=Q1⊕32⊕37；

Q2′,Q3′校驗塊所控制的校驗鏈，標準化后，全部為新數(shù)據(jù),校驗鏈需要重構；

Q8′=3⊕4⊕9⊕14⊕34⊕39，

所以Q8′=Q2⊕34⊕39；

Q9′=0⊕5⊕10⊕15⊕35⊕新數(shù)據(jù)，

所以Q9′=Q3⊕34⊕新數(shù)據(jù)。

圖6 遷移一定的數(shù)據(jù)到新磁盤，實現(xiàn)最小化計算開銷Fig.6 Migrate certain data to new disks for minimal computational overhead

由以上分析可知，HS6擴容算法最大化的利用了原有4條斜校驗鏈的校驗數(shù)據(jù)，將重構校驗鏈需要的5個XOR運算，減少為2個XOR運算，減少了計算開銷。

2.1 HS6擴容遷移算法

步驟1根據(jù)存儲磁盤的容量C和數(shù)據(jù)塊的大小B,確定存儲系統(tǒng)的總行數(shù)L=C/B；

步驟2M表示在擴容前，存儲系統(tǒng)含有的磁盤數(shù)；N表示向存儲系統(tǒng)添加的磁盤數(shù)。依據(jù)H-Code編碼(p-1)×(p+1)，p為素數(shù)的條件，根據(jù)M和N計算出p的值；

步驟3標準化后，判斷新加入到原有存儲條帶的數(shù)據(jù)中，斜校驗數(shù)據(jù)塊QN1和QN2是否在反對角線上。如果不在，將斜校驗數(shù)據(jù)塊遷移到反對角線上；

步驟4標準化后的存儲系統(tǒng)，每一個(M+N-2)×(M+N)的存儲條帶中，根據(jù)添加的磁盤N，將條帶中第一行的最后一個數(shù)據(jù)塊和左下角N×N的三角區(qū)域內的數(shù)據(jù)塊遷移到新磁盤的相應位置；

步驟5判斷所有條帶待遷移塊是否都已經(jīng)遷移到新磁盤的對應區(qū)域，若是，則遷移結束，執(zhí)行步驟6，否則執(zhí)行步驟4；

步驟6數(shù)據(jù)遷移過程結束。

3 性能分析

為了定量計算HS6擴容算法的優(yōu)勢，本文通過數(shù)字仿真實驗，比較了HS6算法與Round-Robin算法和Semi-RR算法的擴容性能。本文利用6個磁盤組成一個RAID-6存儲系統(tǒng)，其中，存儲系統(tǒng)中為4×6的存儲條帶。 由于擴容后的存儲條帶仍然需要滿足H-Code編碼的條件，所以本文RAID-6存儲系統(tǒng)5次擴容的過程，添加的新磁盤個數(shù)分別為2，4，2，4，2。其中，設定每個磁盤的大小為128 GByte，塊的大小為64 KByte，所以每個磁盤含有2×10242個數(shù)據(jù)塊。

3.1 數(shù)據(jù)遷移率比較

如圖7，不同的擴容算法在逐次擴容之后，與Round-Robin擴容算法數(shù)據(jù)遷移率的比較。經(jīng)過數(shù)字仿真實驗，對每一次擴容之后的遷移數(shù)據(jù)進行記錄，HS6算法的數(shù)據(jù)遷移率比Round-Robin擴容算法和Semi-RR擴容算法減少了73.2%～88.6%。圖中HS6擴容算法的數(shù)據(jù)遷移率隨著擴容次數(shù)的增加具有越來越小的趨勢。說明在進行多次擴容之后，HS6擴容算法與Round-Robin和Semi-RR擴容算法相比具有更小的遷移率，而且隨著擴容次數(shù)的增加，數(shù)據(jù)遷移率越來越小。

圖7 數(shù)據(jù)遷移率比較Fig.7 Data migration comparison

3.2 總I/O操作個數(shù)

圖8中，由于Round-Robin擴容算法每一次擴容都需要遷移幾乎所有的數(shù)據(jù)塊，所以隨著擴容次數(shù)的增加，總I/O操作數(shù)呈現(xiàn)上升的趨勢。Semi-RR擴容算法和HS6擴容算法第2，4次擴容時，由于為了滿足H-Code編碼的條件，添加4個新磁盤，數(shù)據(jù)遷移量的增加，導致了總I/O操作數(shù)在第2，4次擴容時有明顯的上升趨勢。

圖8 總I/O操作個數(shù)比較Fig.8 Comparison of total I/O operations

圖8，圖9中HS6的折線，雖然由于第2，4次擴容時，添加了4個新磁盤，折線呈現(xiàn)上升趨勢，但在第1，3，5次，同添加2個新磁盤的情況相比，HS6擴容算法隨著擴容次數(shù)的增加總I/O操作數(shù)和總擴容時間呈下降趨勢。相比于Round-Robin和Semi-RR擴容算法，HS6減少了30.6%～62.9%的總I/O操作數(shù)和總擴容時間。

圖9 總擴容時間比較Fig.9 Total expansion time comparison

3.3 計算開銷比較

圖10中，Round-Robin和Semi-RR 2種擴容算法，在每次擴容過程中，都需要重構全部的水平校驗鏈和斜校驗鏈，所以2種擴容算法總XOR操作數(shù)是一樣的。經(jīng)過仿真實驗的數(shù)據(jù)分析，HS6擴容算法的總XOR操作數(shù)相比于Round-Robin和Semi-RR擴容算法減少了43.9%～54.2%。

3.4 I/O性能比較

HS6擴容算法實現(xiàn)了最小數(shù)據(jù)遷移，減少了遷移I/O，擴容過程中對前臺用戶訪問造成的影響較小。RR算法數(shù)據(jù)遷移量大，遷移I/O多，對前臺用戶訪問造成的影響較大，降低了用戶訪問的性能。Semi-RR算法與RR相比，減少了一定的數(shù)據(jù)遷移量，但在多次擴容過程中存在負載不均衡的問題，對前臺用戶訪問影響較大，降低了用戶訪問性能。

圖10 總XOR操作個數(shù)比較Fig.10 Total XOR operation number comparison

4 總 結

本文對利用H-Code編碼的RAID-6存儲系統(tǒng)的擴容進行了研究，對于擴容過程中普遍面臨的最小化數(shù)據(jù)遷移和快速擴容的問題，提出了HS6擴容算法。HS6在擴容過程中，不僅保證了遷移數(shù)據(jù)只在舊磁盤與新磁盤之間移動，而且確保了遷移數(shù)據(jù)只在同一校驗鏈之間移動，同時最大程度地保留了原有的斜校驗數(shù)據(jù)，極大地減少了遷移數(shù)據(jù)量和計算開銷。經(jīng)過仿真實驗數(shù)據(jù)表明，與Round-Robin和Semi-RR擴容算法相比，HS6減少了73.2%～88.6%的數(shù)據(jù)遷移量，縮短了30.6%～62.9%的總擴容時間。HS6擴容算法具有最小數(shù)據(jù)遷移率和最小計算開銷，相較于傳統(tǒng)的擴容算法具有很大的優(yōu)勢。