高　帥　梁　杰　吳　思　許胤龍

(中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　安徽 合肥 230027) (安徽省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室　安徽 合肥 230027)

?

基于輪轉(zhuǎn)部署的RAID6分布式存儲(chǔ)系統(tǒng)擴(kuò)容方案

高帥梁杰吳思許胤龍

(中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院安徽 合肥 230027) (安徽省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室安徽 合肥 230027)

隨著用戶數(shù)據(jù)和新型應(yīng)用的爆炸式增長(zhǎng)，存儲(chǔ)系統(tǒng)需要更大的存儲(chǔ)空間和更好的I/O性能，導(dǎo)致對(duì)原有存儲(chǔ)系統(tǒng)進(jìn)行擴(kuò)容。研究基于RDP編碼的存儲(chǔ)系統(tǒng)的擴(kuò)容問題。已有的擴(kuò)容方案RS6、SDM等沒有考慮到校驗(yàn)塊的輪轉(zhuǎn)部署與負(fù)載均衡等因素，導(dǎo)致擴(kuò)容后的系統(tǒng)中各磁盤的負(fù)載不平衡。在基于校驗(yàn)塊輪轉(zhuǎn)部署的基礎(chǔ)上，提出一種新型RDP擴(kuò)容方案RSR?；赗SR的擴(kuò)容方案，擴(kuò)容后的系統(tǒng)中各磁盤上的數(shù)據(jù)塊與校驗(yàn)塊的分布都是均衡的。通過在Disksim上的一系列模擬實(shí)驗(yàn)證明，RSR的數(shù)據(jù)塊和校驗(yàn)塊遷移量上達(dá)到了最優(yōu)，并且在擴(kuò)容后的系統(tǒng)訪問性能也接近于最優(yōu)。

RDP編碼擴(kuò)容輪轉(zhuǎn)部署

0　引　言

當(dāng)前，用戶信息和數(shù)據(jù)呈現(xiàn)爆炸式增長(zhǎng)，單磁盤已經(jīng)很難提供高效、可靠的服務(wù)。因此，RAID[1-3]編碼被廣泛應(yīng)用于各種存儲(chǔ)系統(tǒng)中。一個(gè)RAID存儲(chǔ)系統(tǒng)由多個(gè)獨(dú)立的物理磁盤組成，具有存儲(chǔ)容量大、高并行I/O帶寬、冗余容錯(cuò)等特點(diǎn)。根據(jù)容錯(cuò)能力的不同，RAID有不同的類型。RAID6編碼可以容2個(gè)磁盤的出錯(cuò)。

隨著數(shù)據(jù)量和用戶請(qǐng)求的增長(zhǎng)，原有的RAID存儲(chǔ)系統(tǒng)會(huì)日益無法滿足需求，因此需要對(duì)原有分布式系統(tǒng)進(jìn)行擴(kuò)容。通常采用增加磁盤數(shù)量的方式進(jìn)行擴(kuò)容，并在增加磁盤過后將一部分原有數(shù)據(jù)遷移到新盤上以均衡I/O負(fù)載。由于許多應(yīng)用要求提供24小時(shí)無間斷服務(wù)，系統(tǒng)要求進(jìn)行在線擴(kuò)容，這將嚴(yán)重影響系統(tǒng)訪問性能。為了提高擴(kuò)容速度，提升擴(kuò)容后系統(tǒng)的訪問性能，需要最小化擴(kuò)容過程中的數(shù)據(jù)遷移量，均衡擴(kuò)容后的數(shù)據(jù)分布等[5]。

已有RAID6擴(kuò)容算法包括SDM[6]、RS6[7]和MDSFrame[8]。SDM算法通過多條帶之間進(jìn)行均衡的方式實(shí)現(xiàn)了數(shù)據(jù)均衡和最小化數(shù)據(jù)遷移，但是該方法要求擴(kuò)容前每個(gè)磁盤擁有一定的冗余存儲(chǔ)空間。MDSFrame則是通過不同編碼方案之間進(jìn)行轉(zhuǎn)換的方式實(shí)現(xiàn)了系統(tǒng)的擴(kuò)容。RS6克服了SDM方法的不足，并使用了Piggyback[2]技術(shù)減小了校驗(yàn)塊更新所帶來的開銷。但是以上方法假定校驗(yàn)塊部署于2個(gè)特定的磁盤中，并且只考慮了數(shù)據(jù)塊的遷移，這將導(dǎo)致擴(kuò)容后系統(tǒng)中的校驗(yàn)塊分布不均勻。

在一個(gè)RAID6存儲(chǔ)系統(tǒng)中，如果所有的校驗(yàn)塊都部署在2個(gè)特定的磁盤中，校驗(yàn)塊的更新負(fù)載將會(huì)成為整個(gè)系統(tǒng)的瓶頸。因此實(shí)際應(yīng)用中通常采用另一種方案，將不同條帶內(nèi)的校驗(yàn)塊以輪轉(zhuǎn)的方式部署在每塊磁盤上，達(dá)到校驗(yàn)塊的分布均衡與負(fù)載均衡。

本文研究基于RDP編碼的RAID6存儲(chǔ)系統(tǒng)的擴(kuò)容問題。假定不同條帶內(nèi)的校驗(yàn)塊按輪轉(zhuǎn)的方式部署在所有磁盤中，提出一種新的擴(kuò)容方案RSR，使得擴(kuò)容后系統(tǒng)中校驗(yàn)塊和數(shù)據(jù)塊能夠均衡地分布在所有磁盤中。RSR最小化了數(shù)據(jù)遷移量，并以Piggyback技術(shù)減少了校驗(yàn)盤更新所帶來的開銷。

1　RDP碼的編碼方案與擴(kuò)容方案

1.1RDP編碼

圖1表示的是一個(gè)基于p=5的RDP編碼陣列。其中i代表磁盤塊在磁盤中的編號(hào)，j代表磁盤塊所在的磁盤號(hào)，di,j代表第j個(gè)磁盤上的第i塊。D0到D3存儲(chǔ)數(shù)據(jù)塊，D4和D5分別用來存儲(chǔ)行校驗(yàn)塊和斜校驗(yàn)塊。

圖1　p=5的RDP陣列

1.2RDP碼的擴(kuò)容方案

(1) 基于滿足RoundRobin性質(zhì)的傳統(tǒng)擴(kuò)容方案

對(duì)于用RDP碼進(jìn)行編碼的分布式存儲(chǔ)系統(tǒng)，當(dāng)需要進(jìn)行擴(kuò)容操作時(shí)，傳統(tǒng)的擴(kuò)容方案是基于滿足RoundRobin[9]性質(zhì)對(duì)原有系統(tǒng)進(jìn)行擴(kuò)容。即對(duì)校驗(yàn)塊和數(shù)據(jù)塊在擴(kuò)容后系統(tǒng)中的磁盤分布按RoundRobin規(guī)則重新部署，并在此之后重新計(jì)算校驗(yàn)塊。

傳統(tǒng)擴(kuò)容方案的優(yōu)點(diǎn)在于擴(kuò)容后的數(shù)據(jù)讀寫性能最優(yōu)，缺點(diǎn)是沒有滿足最小數(shù)據(jù)遷移量的要求。額外的數(shù)據(jù)遷移量將會(huì)增加系統(tǒng)內(nèi)網(wǎng)絡(luò)帶寬的開銷和磁盤間的數(shù)據(jù)流動(dòng)，而這最終會(huì)導(dǎo)致系統(tǒng)訪問性能的降低。

(2) 基于滿足最小數(shù)據(jù)遷移量的擴(kuò)容方案

文獻(xiàn)[6]提出了通過邏輯拼接空閑磁盤塊的方式來進(jìn)行擴(kuò)容。由于RAID6碼是對(duì)系統(tǒng)內(nèi)條帶(陣列)進(jìn)行編碼，因此在擴(kuò)容過程中不僅要考慮到增加條帶的列數(shù)(磁盤數(shù))，也要考慮到增加條帶的行數(shù)。該方法通過邏輯拼接磁盤內(nèi)空閑塊到原條帶的方式來進(jìn)行行方向上的擴(kuò)充。相對(duì)傳統(tǒng)的擴(kuò)容方案，在擴(kuò)容過程中最小化了數(shù)據(jù)遷移量。

文獻(xiàn)[7]提出了多條帶之間邏輯拼接來進(jìn)行擴(kuò)容的方法。相比于邏輯拼接空閑塊的方法，在擴(kuò)容過程中對(duì)原系統(tǒng)磁盤中的空閑區(qū)域大小沒有要求。并且使用了Piggyback技術(shù)，減少了由于更新校驗(yàn)塊所帶來的數(shù)據(jù)塊的讀取。

但是，文獻(xiàn)[6]與文獻(xiàn)[7]中的方案假定校驗(yàn)塊部署在2個(gè)特定磁盤中，所以都沒有考慮到校驗(yàn)塊的遷移，也就沒有考慮到校驗(yàn)塊的均衡。在實(shí)際部署中，為了均衡校驗(yàn)塊更新負(fù)載，通常將校驗(yàn)塊以條帶為單位用輪轉(zhuǎn)的方式部署在系統(tǒng)中。圖2為一個(gè)輪轉(zhuǎn)部署的示意圖，其中，每行表示1個(gè)條帶，R、D分別代表相應(yīng)的條帶中存儲(chǔ)行校驗(yàn)塊和斜校驗(yàn)塊的磁盤。如圖2所示，在1個(gè)輪轉(zhuǎn)內(nèi)各磁盤間的數(shù)據(jù)塊和校驗(yàn)塊都是均衡的。為了實(shí)現(xiàn)擴(kuò)容后數(shù)據(jù)塊和校驗(yàn)塊的均衡，我們需同時(shí)進(jìn)行數(shù)據(jù)塊和校驗(yàn)塊的遷移。

圖2　RDP的基于輪轉(zhuǎn)的部署方案

2　基于輪轉(zhuǎn)部署的RDP擴(kuò)容方案

在RDP碼輪轉(zhuǎn)部署的基礎(chǔ)上，相較于RS6等擴(kuò)容方法，RSR不僅考慮了擴(kuò)容后數(shù)據(jù)塊的均衡，也考慮了校驗(yàn)塊的均衡。相對(duì)于傳統(tǒng)的擴(kuò)容方案來說，RSR最小化了數(shù)據(jù)遷移量。為了進(jìn)一步減小更新校驗(yàn)塊所帶來的開銷，RSR使用了Piggyback技術(shù)來減少校驗(yàn)塊更新帶來的數(shù)據(jù)塊讀取量。

2.1擴(kuò)容算法引例

(1) 條帶間的拼接與均衡

將一個(gè)基于RDP編碼的存儲(chǔ)系統(tǒng)從6個(gè)磁盤擴(kuò)容到8個(gè)磁盤，需要對(duì)原有的編碼條帶增加2列和2行。如圖3左上角所示，有3個(gè)類似圖2中的輪轉(zhuǎn)。為了更好地減小更新校驗(yàn)塊所帶來的開銷，我們將第3個(gè)輪轉(zhuǎn)中的每個(gè)條帶拆分，然后拼接到第1、2輪轉(zhuǎn)的對(duì)應(yīng)條帶上，以實(shí)現(xiàn)擴(kuò)容在每個(gè)條帶內(nèi)行數(shù)上的增加，形成如圖3下半部分的兩個(gè)6×6的陣列。在對(duì)以上3個(gè)輪轉(zhuǎn)進(jìn)行分拆和拼接之后會(huì)形成類似圖2中的2個(gè)新的輪轉(zhuǎn)。不同于圖3左上角舊的輪轉(zhuǎn)，新的輪轉(zhuǎn)中的每1行是一個(gè)6×6的陣列，我們把擴(kuò)容前系統(tǒng)中的條帶經(jīng)過拆分與拼接后得到的輪轉(zhuǎn)稱為新輪轉(zhuǎn)。

為了實(shí)現(xiàn)校驗(yàn)塊的均衡，我們需要將若干個(gè)新輪轉(zhuǎn)中的校驗(yàn)塊全部遷移到新盤中。在本例中，我們將每4個(gè)新輪轉(zhuǎn)中的最后1個(gè)作為遷移校驗(yàn)塊的新輪轉(zhuǎn)，并將其校驗(yàn)塊全部遷移到新盤中。由于新輪轉(zhuǎn)條帶間的分布與舊輪轉(zhuǎn)相似，所以我們還用圖3來介紹如何實(shí)現(xiàn)校驗(yàn)盤的均衡。如圖3所示，3個(gè)新輪轉(zhuǎn)中每個(gè)舊磁盤有3個(gè)R和3個(gè)D，每個(gè)R或D在新輪轉(zhuǎn)中代表6塊校驗(yàn)塊，即每個(gè)舊磁盤有3×6塊行校驗(yàn)塊和斜校驗(yàn)塊。通過將最后1個(gè)新輪轉(zhuǎn)中的校驗(yàn)塊遷移到新盤中，即一共有6×6塊行校驗(yàn)塊和斜校驗(yàn)塊被遷移到新盤中。平均每個(gè)新盤中有3×6塊行校驗(yàn)塊和斜校驗(yàn)塊，所以如果將新盤中的校驗(yàn)塊也按輪轉(zhuǎn)均勻放置，那么無論新盤舊盤每個(gè)磁盤都有3×6塊校驗(yàn)塊，從而就實(shí)現(xiàn)了校驗(yàn)塊的均衡。

圖3　RDP的p=5到p=7的擴(kuò)容過程中的拼接過程

我們以4個(gè)新輪轉(zhuǎn)作為一個(gè)單元，作為擴(kuò)容的基本單位，在擴(kuò)容后的系統(tǒng)中實(shí)現(xiàn)數(shù)據(jù)塊的均衡與校驗(yàn)塊的均衡。在4個(gè)新輪轉(zhuǎn)中，有一個(gè)遷移校驗(yàn)塊，另外3個(gè)不遷移校驗(yàn)塊。為了實(shí)現(xiàn)數(shù)據(jù)塊的均衡，我們從不遷移校驗(yàn)塊的3個(gè)新輪轉(zhuǎn)中，每個(gè)條帶遷移8塊數(shù)據(jù)塊到新盤中，從遷移校驗(yàn)塊的1個(gè)新輪轉(zhuǎn)中不遷移數(shù)據(jù)塊到新盤中。遷移數(shù)據(jù)塊前，每4個(gè)新輪轉(zhuǎn)在每個(gè)舊盤中有4×4×6=96塊數(shù)據(jù)塊。由于我們把每4個(gè)新輪轉(zhuǎn)中的前3個(gè)輪轉(zhuǎn)的每個(gè)條帶遷移8塊數(shù)據(jù)塊到新盤中，故每4個(gè)新輪轉(zhuǎn)中遷移了3×6×8=144塊數(shù)據(jù)塊到新盤中。平均每個(gè)舊盤減少了144÷6=24塊數(shù)據(jù)塊，即平均每個(gè)舊盤還剩下96-24=72塊數(shù)據(jù)塊。而平均每個(gè)新盤中遷移進(jìn)了144÷2=72塊數(shù)據(jù)塊。因?yàn)閿?shù)據(jù)盤塊輪轉(zhuǎn)部署的特性，舊盤中的數(shù)據(jù)塊是均衡分布的。而新盤中，我們也是以輪轉(zhuǎn)的方式部署盤塊，所以無論新盤舊盤都有72塊數(shù)據(jù)塊，從而實(shí)現(xiàn)了數(shù)據(jù)塊的均勻。

(2) 條帶內(nèi)的數(shù)據(jù)遷移方案

4個(gè)新輪轉(zhuǎn)作為一個(gè)單元，1個(gè)新輪轉(zhuǎn)中遷移校驗(yàn)塊，3個(gè)新輪轉(zhuǎn)中不遷移校驗(yàn)塊。根據(jù)是否遷移校驗(yàn)塊，條帶內(nèi)的數(shù)據(jù)塊遷移方案分為了2種。若條帶中不遷移校驗(yàn)塊，如圖4左邊所示，新加入盤D6和D7插入到如圖3所示的拼接后的6×6條帶內(nèi)，形成6×8(p=7)的條帶。

圖4　在p=7的條帶中，校驗(yàn)盤從老盤遷移到新盤

在這種不遷移校驗(yàn)塊的條帶中，我們可以使用文獻(xiàn)[7]中的方法來進(jìn)行數(shù)據(jù)遷移，在此不在贅述。若條帶中遷移校驗(yàn)塊，則我們既需要遷移數(shù)據(jù)塊也需要遷移校驗(yàn)塊。如圖4右邊所示，在圖4左邊插入新盤D6和D7的基礎(chǔ)上，所有的校驗(yàn)塊都被遷移到了新盤中去。由于本例中的新盤全被遷移后的校驗(yàn)塊占用，無需再往新盤遷移任何數(shù)據(jù)塊，故本例只能展示條帶間的拼接過程。下面我們通過一個(gè)2×4(p=3)擴(kuò)容到6×8(p=7)的例子來展示遷移校驗(yàn)盤之后如何遷移數(shù)據(jù)塊。

圖5　從p=3擴(kuò)容到p=7遷移塊條帶的數(shù)據(jù)遷移過程

2.2算法的形式化介紹

在基于RDP編碼的RAID6存儲(chǔ)系統(tǒng)中，假設(shè)從m=p+1個(gè)磁盤塊擴(kuò)容到n=q+1個(gè)磁盤塊，其中p和q為大于2的素?cái)?shù)。首先通過將r1個(gè)舊輪轉(zhuǎn)拼接成新輪轉(zhuǎn)，實(shí)現(xiàn)了輪轉(zhuǎn)內(nèi)的條帶從m-2行擴(kuò)展到n-2行。為了讓整數(shù)個(gè)m-2行的舊條帶能夠拼接成整數(shù)個(gè)n-2行的新條帶，r1×(m-2)需要能夠被n-2整除。然后將r2個(gè)新輪轉(zhuǎn)作為一個(gè)整體來進(jìn)行數(shù)據(jù)和校驗(yàn)盤的遷移與均衡。因?yàn)橐獙2個(gè)新輪轉(zhuǎn)中的最后r2×(n-m)/n個(gè)進(jìn)行校驗(yàn)塊的遷移以實(shí)現(xiàn)整體校驗(yàn)盤的均衡，所以r2要滿足r2×(n-m)可以被n整除。也就是說如果條帶在0到r2×m/n-1新輪轉(zhuǎn)中只遷移數(shù)據(jù)塊，條帶在r2×m/n到r2-1新輪轉(zhuǎn)中遷移校驗(yàn)塊和數(shù)據(jù)塊。這就將條帶的遷移方案分為了兩種：遷移校驗(yàn)塊的和不遷移校驗(yàn)塊的。如上所述，我們通過文獻(xiàn)[7]中的方法去遷移第1種條帶內(nèi)的數(shù)據(jù)塊，下面我們介紹同時(shí)遷移數(shù)據(jù)塊和校驗(yàn)塊的條帶內(nèi)遷移方案。

在這類條帶中，我們首先將校驗(yàn)塊遷移到新盤中，然后再遷移數(shù)據(jù)塊。在本遷移方案中，有3個(gè)因素可以影響到遷移后更新校驗(yàn)塊所帶來的開銷：① 未遷移進(jìn)校驗(yàn)塊的新盤在條帶中插入的邏輯位置；② 校驗(yàn)塊遷移后所留下的空盤在條帶中的邏輯位置；③ 哪些數(shù)據(jù)塊會(huì)被遷移。

下面介紹遷移方案的決策過程：

如圖5左邊所示，在遷移數(shù)據(jù)塊之前，校驗(yàn)塊由D2到D3被遷移到了新盤D6到D7中。然后我們確定未遷移進(jìn)校驗(yàn)塊的空盤在條帶中的位置，我們用ld表示第一個(gè)空盤在條帶中的邏輯位置，其中0≤ld≤n-2，在本例中l(wèi)d=2。其次我們用ls表示校驗(yàn)塊遷移后所留下的空盤在條帶中的邏輯位置，其中 ld≤ls≤ld+2，在本例中l(wèi)s=2。最后用dis表示moving parallelogram的左上角與條帶中全體數(shù)據(jù)塊右上角之間的距離，其中0≤dis≤m-3，在本例中dis=1。通過將圖5右邊中的moving parallelogram中數(shù)據(jù)塊全部遷移到新盤中以實(shí)現(xiàn)數(shù)據(jù)塊的遷移，而moving parallelogram是高為n-2寬為n-m的平行四邊形，如圖5所示。在本例中從moving parallelogram中遷移d3,1、d4,0、d4,1、d5,0塊到新盤中。

每一組確定的ld、ls和dis值都對(duì)應(yīng)一個(gè)更新校驗(yàn)盤所帶來的開銷。所以通過枚舉所有的ld、ls和dis值，我們從中選取開銷最小的方案作為我們的遷移方案。

2.3算法的理論分析

對(duì)于基于RDP編碼的存儲(chǔ)系統(tǒng)擴(kuò)容過程，RSR在擴(kuò)容后使得校驗(yàn)塊和數(shù)據(jù)塊均勻部署在所有磁盤中，并在擴(kuò)容過程中最小化了數(shù)據(jù)塊與校驗(yàn)塊的數(shù)據(jù)遷移量。下面我們給出理論分析，并說明RSR較其他方法的優(yōu)勢(shì)。

假設(shè)從m個(gè)磁盤擴(kuò)容到n個(gè)磁盤，并將r2個(gè)新輪轉(zhuǎn)做為一個(gè)整體進(jìn)行數(shù)據(jù)和校驗(yàn)塊的均衡和遷移。為了實(shí)現(xiàn)校驗(yàn)塊的均衡，我們將序號(hào)從r2×m/n到r2-1的新輪轉(zhuǎn)中所有的校驗(yàn)塊遷移到新盤中。這也就意味著我們將所有校驗(yàn)塊的(n-m)/n遷移到了新盤中，滿足校驗(yàn)塊的最小遷移量。由于有n-m個(gè)新磁盤，所以每個(gè)新磁盤在遷移后平均有1/n的校驗(yàn)塊。同理，老盤中有m個(gè)磁盤，而遷移后還剩下m/n的校驗(yàn)塊，所以老盤中平均每個(gè)磁盤有1/n的校驗(yàn)塊。也就是說只要校驗(yàn)塊能均衡地部署在每塊磁盤中，就實(shí)現(xiàn)了校驗(yàn)塊的均衡部署。如圖3所示，老盤中校驗(yàn)塊是以輪轉(zhuǎn)的方式進(jìn)行部署，所以老盤中校驗(yàn)塊是均衡的。而新盤中，我們也采同樣的方式將校驗(yàn)塊均衡的部署在新盤中。所以從整體上，校驗(yàn)塊在遷移中滿足最小遷移量，在遷移后實(shí)現(xiàn)了均衡部署。

在新輪轉(zhuǎn)中每個(gè)條帶有m×(n-2)個(gè)數(shù)據(jù)塊，而一個(gè)新輪轉(zhuǎn)有m個(gè)條帶，所以r2個(gè)新輪轉(zhuǎn)中有r2×m2×(n-2)個(gè)數(shù)據(jù)塊。為了滿足最小化數(shù)據(jù)塊遷移量，我們需要遷移(n-m)/n的數(shù)據(jù)塊到新盤中，即r2×m2×(n-2) ×(n-m)/n個(gè)數(shù)據(jù)塊。

條帶內(nèi)的數(shù)據(jù)塊遷移方案被分為了兩種：不遷移校驗(yàn)塊的條帶和遷移校驗(yàn)塊的條帶。在不遷移校驗(yàn)塊的條帶中，我們遷移(n-m)/(n-2)的數(shù)據(jù)塊到新盤中，也就是m×(n-m)個(gè)數(shù)據(jù)塊。在遷移校驗(yàn)塊的條帶中，我們遷移(n-m-2)/(n-2)的數(shù)據(jù)塊到新盤中，也就是m×(n-m-2)個(gè)數(shù)據(jù)塊。由于條帶在前r2×m/n個(gè)新輪轉(zhuǎn)中采取第一種數(shù)據(jù)塊遷移方案，所以有r2×m3×(n-m) /n個(gè)數(shù)據(jù)塊被遷移到新盤中。而在后r2×(n-m)/n個(gè)新輪轉(zhuǎn)中采取第二種數(shù)據(jù)塊遷移方案，所以有r2×m2×(n-m-2)×(n-m)/n個(gè)數(shù)據(jù)塊被遷移到了新盤中。而上述兩種遷移量的和剛好等于r2×m2×(n-2) ×(n-m)/n，所以數(shù)據(jù)塊滿足最小遷移量。由于數(shù)據(jù)塊的均衡與校驗(yàn)塊類似，在此不再贅述。

對(duì)比RS6與 SDM擴(kuò)容方法，由于這兩種方法的遷移方案并沒有考慮到校驗(yàn)塊的遷移，所以校驗(yàn)塊仍然集中在m個(gè)老盤中。基于RDP編碼的存儲(chǔ)系統(tǒng)在寫操作時(shí)需要進(jìn)行2到3次的校驗(yàn)塊更新過程，所以校驗(yàn)塊的更新往往成為整個(gè)系統(tǒng)的瓶頸。如果系統(tǒng)進(jìn)行了多次擴(kuò)容，這種校驗(yàn)塊負(fù)載不均衡的現(xiàn)象會(huì)更加明顯。而對(duì)于RSR來說，由于校驗(yàn)塊均衡地分布在所有磁盤中，擴(kuò)容后的校驗(yàn)塊負(fù)載是均衡的，所以在系統(tǒng)訪問性能上要優(yōu)于RS6與SDM。對(duì)比傳統(tǒng)基于輪轉(zhuǎn)調(diào)度的擴(kuò)容方法，由于RSR只需要遷移(n-m)/n的數(shù)據(jù)，相對(duì)于傳統(tǒng)擴(kuò)容方案需要整體遷移數(shù)據(jù)節(jié)省了m/n的數(shù)據(jù)遷移量，所以在數(shù)據(jù)遷移量上要優(yōu)于傳統(tǒng)擴(kuò)容方案。

3　模擬實(shí)驗(yàn)與評(píng)估

為了評(píng)估RSR的性能，我們通過兩組實(shí)驗(yàn)來比較RSR、RS6、RR4和RR5的擴(kuò)容時(shí)間和擴(kuò)容后的訪問性能。RR4是基于校驗(yàn)塊部署在2個(gè)特定磁盤上的RoundRobin擴(kuò)容方法，而RR5是基于校驗(yàn)塊輪轉(zhuǎn)部署的RoundRobin擴(kuò)容方法。

3.1評(píng)估方法

在廣泛使用的磁盤模擬器DiskSim[11]上進(jìn)行模擬實(shí)驗(yàn)，采用SEAGATE_ST3146855FC_3LN02D4A企業(yè)級(jí)磁盤作為被模擬的磁盤。

為了評(píng)估在不同磁盤數(shù)量下的擴(kuò)容性能，從6個(gè)磁盤開始一直擴(kuò)容到18個(gè)磁盤，分4次分別增加2、4、2、4個(gè)磁盤。因?yàn)樵诓煌疟P容量下各個(gè)方法相對(duì)的性能比較差距不大，因此將單個(gè)磁盤容量設(shè)置為4 GB，并將盤塊的大小設(shè)置為64 KB。

為了評(píng)估不同算法下擴(kuò)容后的訪問性能，我們使用真實(shí)系統(tǒng)中的3個(gè)磁盤I/O訪問記錄來進(jìn)行模擬實(shí)驗(yàn)。3個(gè)訪問記錄選自于Storage Performance Council(SPC)[10]，基于讀寫比例的不同來選取。因?yàn)檫@3個(gè)訪問記錄中的塊大小為4 KB，所以我們?cè)O(shè)置盤塊大小為4 KB來進(jìn)行訪問性能實(shí)驗(yàn)。這3個(gè)訪問記錄的特點(diǎn)如下：

1) Financial1[10]收集于一個(gè)OLTP應(yīng)用，這個(gè)應(yīng)用在兩個(gè)大型的金融機(jī)構(gòu)內(nèi)運(yùn)行。是3個(gè)訪問記錄中寫操作比例最高的，達(dá)到76.8%。

2) Financial2[10]同樣來自于一個(gè)OLTP應(yīng)用，唯一的不同是Financial2的寫操作比例要低一些，為17.7%。

3) WebSearch2[10]來自一個(gè)流行的搜索引擎。它主要的特點(diǎn)是基本上都是讀操作，讀操作比例高達(dá)99.9%。

基于以上3個(gè)訪問記錄，我們對(duì)總體擴(kuò)容時(shí)間和擴(kuò)容后平均響應(yīng)時(shí)間進(jìn)行比較，從而評(píng)估各個(gè)算法的性能。

3.2擴(kuò)容時(shí)間評(píng)估

為了評(píng)估擴(kuò)容性能，收集RSR、RS6、RR4和RR5的總體擴(kuò)容時(shí)間來進(jìn)行對(duì)比。圖6中展示了在不同磁盤數(shù)下的總體擴(kuò)容時(shí)間對(duì)比。相較于其他算法，RSR在擴(kuò)容時(shí)間上比RR4和RR5有較大優(yōu)勢(shì)，并且基本與RS6持平。本算法在總體擴(kuò)容時(shí)間上比RR4和RR5減少了53.45%～76.75%，而相較于RS6減少了-0.74%～6.89%。

圖6　總體擴(kuò)容時(shí)間對(duì)比

相較于RR4和RR5來說，RSR在擴(kuò)容時(shí)間上有顯著的減少，其原因在于RSR最小化了數(shù)據(jù)塊和校驗(yàn)塊的遷移量。而相較于RS6的只需要遷移數(shù)據(jù)塊，雖然RSR既需要遷移數(shù)據(jù)塊也需要遷移校驗(yàn)塊，但是由于并行性更好等原因，平均來說，在擴(kuò)容時(shí)間上還是比RS6略好。

3.3訪問性能評(píng)估

在對(duì)于基于輪轉(zhuǎn)部署的RDP編碼存儲(chǔ)系統(tǒng)來說，如果使用RSR進(jìn)行擴(kuò)容，在擴(kuò)容后將會(huì)保持系統(tǒng)內(nèi)校驗(yàn)塊和數(shù)據(jù)塊的均衡分布。但是對(duì)于同樣一個(gè)存儲(chǔ)系統(tǒng)來說，因?yàn)镽S6僅僅遷移數(shù)據(jù)塊，卻做不到校驗(yàn)塊均衡。但是RSR和RS6在擴(kuò)容后的系統(tǒng)中都沒有像RR5一樣嚴(yán)格地滿足RoundRobin性質(zhì)。所以在本節(jié)旨在對(duì)比RSR是否能在擴(kuò)容時(shí)間比RR5有較大減少的基礎(chǔ)上，擴(kuò)容后訪問性能接近RR5并優(yōu)于RR4和RS6方法。

在一個(gè)基于RDP編碼的存儲(chǔ)系統(tǒng)中進(jìn)行一個(gè)寫操作時(shí)，需要同步進(jìn)行2到3次的校驗(yàn)塊更新，而這將帶來4到6次的I/O操作。因此對(duì)于寫操作占主要的環(huán)境中，校驗(yàn)塊的均衡會(huì)對(duì)訪問性能起決定性作用。為了模擬現(xiàn)實(shí)中不同比例寫操作環(huán)境下的系統(tǒng)訪問性能，我們分別使用Financial1、Financial2和Websearch2訪問記錄來進(jìn)行實(shí)驗(yàn)。我們比較各個(gè)擴(kuò)容算法后平均I/O響應(yīng)時(shí)間，并以此為依據(jù)對(duì)各個(gè)算法的擴(kuò)容后訪問性能進(jìn)行評(píng)估。在磁盤數(shù)量上，我們采用與擴(kuò)容時(shí)間的實(shí)驗(yàn)相同的配置。圖7中只給出了本算法和RR5的比較，因?yàn)镕inancial1有一個(gè)相當(dāng)高的寫操作比例，對(duì)于RR4和RR6這樣的方法來說，不能得出一個(gè)有效的平均響應(yīng)時(shí)間(響應(yīng)時(shí)間過長(zhǎng))。而對(duì)于RSR和RR5來說，由于校驗(yàn)塊均衡部署在各個(gè)磁盤上，所以在均衡負(fù)載的基礎(chǔ)上可以給得一個(gè)有效的訪問時(shí)間。

圖7　基于Financial1的擴(kuò)容后訪問性能對(duì)比

如圖7所示，RSR在Financial1訪問記錄下相較于RR5平均訪問時(shí)間多了0.76%～15.92%。如圖8所示，RSR在Financial2訪問記錄下相較于RS6平均訪問時(shí)間少了11.11%～16.92%，相較于RR4少了5.54%～14.67%，相較于RR5多了0.42%～5.57%。如圖9所示，RSR在WebSearch2訪問記錄下相較于RS6平均訪問時(shí)間少了0%到1.88%，相較于RR4平均訪問時(shí)間少了-4.12%～4.96%，相較于RR5多了-4.98%～0.74%。

圖8　基于Financial2的擴(kuò)容后訪問性能對(duì)比

圖9　基于Websearch2的擴(kuò)容后訪問性能對(duì)比

從實(shí)驗(yàn)結(jié)果可以看出，在擴(kuò)容時(shí)間上，RSR明顯優(yōu)于RR4和RR5，與RS6基本持平。但是在擴(kuò)容后訪問性能上，RSR在寫主導(dǎo)的訪問記錄下明顯優(yōu)于RR4和RS6，與RR5基本持平。在讀主導(dǎo)的訪問記錄下各算法，擴(kuò)容后系統(tǒng)的訪問性能基本相同。所以，RSR在擴(kuò)容時(shí)間和擴(kuò)容后系統(tǒng)訪問方面均有較好的性能。

4　結(jié)　語

基于輪轉(zhuǎn)部署RDP碼的存儲(chǔ)系統(tǒng)，本文提出了一種新型的擴(kuò)容算法RSR。傳統(tǒng)的擴(kuò)容算法雖然保持了RoundRobin性質(zhì)，但擴(kuò)容時(shí)的開銷過大，無法適應(yīng)如今系統(tǒng)所需求的24小時(shí)無間斷服務(wù)。RS6、SDM等新型擴(kuò)容算法雖然相較于傳統(tǒng)算法擴(kuò)容在擴(kuò)容時(shí)間上有較大改進(jìn)，但是在擴(kuò)容后的訪問性能上有較大的差距，并且不符合現(xiàn)實(shí)系統(tǒng)的編碼部署方案。通過對(duì)各個(gè)算法進(jìn)行一系列的模擬評(píng)估，證實(shí)了RSR在擴(kuò)容時(shí)間和訪問性能上均有很好的表現(xiàn)，可以更好地適應(yīng)現(xiàn)實(shí)系統(tǒng)下的擴(kuò)容需求。

[1] Chen P M,Lee E K,Gibson G A,et al.RAID:High-performance,reliable secondary storage[J].ACM Computing Surveys (CSUR),1994,26(2):145-185.

[2] Patterson D A,Gibson G,Katz R H.A case for redundant arrays of inexpensive disks (RAID)[M].ACM,1988.

[3] Si Wu,Yinlong Xu,Yongkun Li,et al.Enhancing Scalability in Distributed Storage Systems with Cauchy Reed-Solomon Codes[C]//IEEE International Conference on Parallel and Distributed Systems (ICPADS 2014),2014.

[4] Corbett P,English B,Goel A,et al.Row-diagonal parity for double disk failure correction[C]//Proceedings of the 3rd USENIX Conference on File and Storage Technologies,2004:1-14.

[5] Zheng W,Zhang G.FastScale:Accelerate RAID Scaling by Minimizing Data Migration[J].FAST,2011,64(1):149-161.

[6] Wu C,He X,Han J,et al.Sdm:A stripe-based data migration scheme to improve the scalability of raid-6[C]//Cluster Computing (CLUSTER),2012 IEEE International Conference on. IEEE,2012:284-292.

[7] Zhang G,Li K,Wang J,et al.Accelerate rdp raid-6 scaling by reducing disk i/os and xor operations[J].IEEE Transactions on Computers,2013:32-44.

[8] Wu C,He X.A flexible framework to enhance raid-6 scalability via exploiting the similarities among mds codes[C]//Parallel Processing (ICPP),2013 42nd International Conference on.IEEE,2013:542-551.

[9] Ghandeharizadeh S,Kim D.On-line reorganization of data in scalable continuous media servers[C]//Database and Expert Systems Applications. Springer Berlin Heidelberg,1996:751-768.

[10] OLTP Application I/O and Search Engine I/O.UMass Trace Repository[EB/OL].http://traces.cs.umass.edu/index.php/Storage/Storage.June,2007.

[11] Bucy J S,Schindler J,Schlosser S W,et al.The disksim simulation environment version 4.0 reference manual[EB/OL].ParallelData Laboratory,2008:26.

A ROTATED DEPLOYMENT-BASED EXPANSION SCHEME FOR RAID6 DISTRIBUTED STORAGE SYSTEM

Gao ShuaiLiang JieWu SiXu Yinlong

(SchoolofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,Hefei230027,Anhui,China) (KeyLaboratoryofHighPerformanceComputing,AnhuiProvince,Hefei230027,Anhui,China)

With the explosive growth of user data and new applications, storage system requires bigger storage space and better I/O performance, which leads to the expansion of original system. In the paper we study the RDP code-based storage system expansion. Existing expansion schemes of RS6 and SDM, etc. do not take into account the rotation-based deployment and load balance of the parity blocks, this result in the unbalance of the load in each disk after the expansion of system. We propose a new RDP expansion approach called RSR based on the rotation-based deployment of parity blocks. The system expanded by RSR will have a balanced distribution of data and parity blocks in each disk. After a series of simulation experiments on Disksim, we prove that the RSR minimises the migration of the data and parity blocks. Furthermore, the expanded system has a near optimal performance on access performance.

RDP codeExpansionRotation-based distribution

2015-01-26。高帥，碩士生，主研領(lǐng)域：分布式系統(tǒng)擴(kuò)容。梁杰，博士生。吳思，博士生。許胤龍，教授。

TP3

A

10.3969/j.issn.1000-386x.2016.08.027