分布式塊存儲(chǔ)系統(tǒng)中高效糾刪碼重構(gòu)技術(shù)研究

陳付 張淑萍

摘要：當(dāng)前的海量存儲(chǔ)壓力導(dǎo)致三副本存儲(chǔ)效率越來(lái)越難以滿足需求。糾刪碼可以提供和三副本存儲(chǔ)相同的可靠性，使用更少的存儲(chǔ)容量和網(wǎng)絡(luò)帶寬。提出一種針對(duì)分布式塊存儲(chǔ)訪問(wèn)特點(diǎn)的糾刪碼故障處理方案——一種糾刪碼和熱備副本相結(jié)合的方法，解決臨時(shí)故障導(dǎo)致的退化讀和退化更新問(wèn)題，同時(shí)精細(xì)地控制永久故障延遲重構(gòu)的時(shí)間點(diǎn)，減輕重構(gòu)操作造成的對(duì)網(wǎng)絡(luò)帶寬的壓力。實(shí)驗(yàn)結(jié)果表明，相對(duì)于傳統(tǒng)糾刪碼，該方案可節(jié)省3倍帶寬流量，存儲(chǔ)成本只有三副本的50%。

關(guān)鍵詞關(guān)鍵詞：云存儲(chǔ)；分布式塊存儲(chǔ)；糾刪碼；重構(gòu)效率

DOIDOI：10.11907/rjdk.161381

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2016）007003303

0引言

云存儲(chǔ)可提供不同接口類型的存儲(chǔ)服務(wù)，如文件存儲(chǔ)、對(duì)象存儲(chǔ)和塊存儲(chǔ)。其中，塊存儲(chǔ)接口可以為云計(jì)算中的云主機(jī)提供云硬盤(pán)服務(wù)。在大規(guī)模數(shù)據(jù)存儲(chǔ)系統(tǒng)中，設(shè)備故障越來(lái)越頻繁，使人們對(duì)于確保數(shù)據(jù)可靠性的需求十分迫切。通常采用數(shù)據(jù)冗余容錯(cuò)技術(shù)來(lái)保護(hù)數(shù)據(jù)，但隨著海量數(shù)據(jù)的存儲(chǔ)壓力與日俱增，分布式存儲(chǔ)系統(tǒng)中保障數(shù)據(jù)可靠性的三副本技術(shù)的存儲(chǔ)成本也越來(lái)越高[1]?，F(xiàn)有分布式存儲(chǔ)系統(tǒng)如微軟WAS[2]、Facebook的F4[3]、HDFS等開(kāi)始支持糾刪碼取代三副本技術(shù)，從而能夠在保持高可靠性的同時(shí)，減輕海量數(shù)據(jù)存儲(chǔ)壓力。糾刪碼的缺陷在于重構(gòu)效率低下，因此分布式塊存儲(chǔ)由于其高I/O密集和低訪問(wèn)延遲特性，必須要克服糾刪碼重構(gòu)成本高的弊端。

1相關(guān)技術(shù)

1.1分布式塊存儲(chǔ)系統(tǒng)

塊存儲(chǔ)提供塊存儲(chǔ)設(shè)備接口，用戶需要把塊存儲(chǔ)卷附加到虛擬機(jī)上之后才可以與其交互。面對(duì)極具彈性的存儲(chǔ)需求和性能需求，單機(jī)或獨(dú)立的SAN越來(lái)越難以滿足企業(yè)需求。塊存儲(chǔ)在Scale-up的瓶頸下面臨著Scale-out的需求，因此Scale-out的分布式塊存儲(chǔ)系統(tǒng)應(yīng)運(yùn)而生。企業(yè)級(jí)分布式塊存儲(chǔ)系統(tǒng)有Amazon EBS，開(kāi)源系統(tǒng)有Ceph RBD[4]和Sheepdog[5]。

1.2糾刪碼容錯(cuò)技術(shù)

考慮一個(gè)有M個(gè)服務(wù)器節(jié)點(diǎn)的糾刪碼編碼存儲(chǔ)集群，將數(shù)據(jù)分割成數(shù)據(jù)段，然后在每個(gè)段上獨(dú)立地使用糾刪碼進(jìn)行編碼。將一個(gè)糾刪碼方案表示為EC（n，k），EC（n，k）將一個(gè)數(shù)據(jù)段分割成了k個(gè)相同大小的未編碼塊，稱為數(shù)據(jù)塊，然后編碼生成n-k個(gè)編碼塊，稱為校驗(yàn)塊。假設(shè)n

2方案設(shè)計(jì)

2.1臨時(shí)故障與永久故障

存儲(chǔ)系統(tǒng)面臨著兩種類型的節(jié)點(diǎn)故障：臨時(shí)故障和永久故障。臨時(shí)故障包括機(jī)器重啟、軟件升級(jí)等，永久故障包括機(jī)器崩潰、磁盤(pán)損壞等[9]。如果一個(gè)存儲(chǔ)節(jié)點(diǎn)丟失數(shù)據(jù)，則發(fā)生了永久故障。為了維持系統(tǒng)的冗余級(jí)別，存儲(chǔ)系統(tǒng)需要執(zhí)行故障節(jié)點(diǎn)重構(gòu)，即將丟失的數(shù)據(jù)修復(fù)并寫(xiě)入另一個(gè)新的存儲(chǔ)節(jié)點(diǎn)。目前，很多研究是關(guān)于加快永久節(jié)點(diǎn)故障重構(gòu)。另一方面，如果一個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)并沒(méi)有丟失，僅是暫時(shí)無(wú)法直接訪問(wèn)，則發(fā)生了臨時(shí)故障。無(wú)永久數(shù)據(jù)丟失的臨時(shí)故障占數(shù)據(jù)中心所有故障事件的90%[10]。

區(qū)分臨時(shí)故障和永久故障，只對(duì)永久故障采用重構(gòu)操作，這樣既可以極大地減少存儲(chǔ)系統(tǒng)中的重構(gòu)次數(shù)，又避免了退化更新操作的高延遲。思路是當(dāng)節(jié)點(diǎn)出現(xiàn)不可用的情況時(shí)，初步界定為臨時(shí)故障，采用熱備副本方法進(jìn)行退化讀和退化更新操作，盡量延遲對(duì)永久故障的判定時(shí)間；當(dāng)確認(rèn)出現(xiàn)永久故障時(shí)，進(jìn)一步延遲重構(gòu)操作，直到一個(gè)數(shù)據(jù)條帶的幾個(gè)塊同時(shí)出現(xiàn)永久故障，或者臨時(shí)故障較多，可能影響到數(shù)據(jù)的可用性和可靠性時(shí)，才開(kāi)始進(jìn)行重構(gòu)操作。

2.2臨時(shí)故障解決方案

為訪問(wèn)暫時(shí)不可用的數(shù)據(jù)，存儲(chǔ)系統(tǒng)需要執(zhí)行退化讀操作，即從剩余存儲(chǔ)節(jié)點(diǎn)讀取數(shù)據(jù)并重建不可用的數(shù)據(jù)。同時(shí)，為了對(duì)無(wú)法直接訪問(wèn)的數(shù)據(jù)塊進(jìn)行更新，存儲(chǔ)系統(tǒng)需要進(jìn)行退化寫(xiě)操作。在更新操作對(duì)延遲不敏感的存儲(chǔ)系統(tǒng)中，將更新操作進(jìn)行阻塞直到能判斷存儲(chǔ)節(jié)點(diǎn)是永久故障還是臨時(shí)故障（等待15分鐘）。如果是永久故障則進(jìn)行重構(gòu)操作，并將更新數(shù)據(jù)寫(xiě)入到恢復(fù)后的節(jié)點(diǎn)；如果是臨時(shí)故障，在節(jié)點(diǎn)可以重新訪問(wèn)之后直接將更新數(shù)據(jù)寫(xiě)入數(shù)據(jù)塊節(jié)點(diǎn)[11]。但對(duì)于更新延遲比較敏感的分布式塊存儲(chǔ)系統(tǒng)，以前不重視的退化更新變得更為重要。

（1）退化讀。當(dāng)需要對(duì)不可用的數(shù)據(jù)塊進(jìn)行讀操作時(shí)，從剩余的n-1個(gè)數(shù)據(jù)塊和校驗(yàn)塊中選取k個(gè)可用的塊進(jìn)行解碼恢復(fù)操作，然后將恢復(fù)的數(shù)據(jù)塊返回客戶端。這些操作與標(biāo)準(zhǔn)的退化讀操作一致，但不同的是將恢復(fù)的數(shù)據(jù)塊保存到對(duì)應(yīng)數(shù)據(jù)塊節(jié)點(diǎn)的熱備節(jié)點(diǎn)中作為副本存儲(chǔ)。在該條帶出現(xiàn)臨時(shí)故障的節(jié)點(diǎn)一直不可用期間，將使用該副本替代原有節(jié)點(diǎn)的數(shù)據(jù)塊來(lái)完成各項(xiàng)更新和讀取操作。當(dāng)原臨時(shí)故障節(jié)點(diǎn)恢復(fù)正常可用時(shí)，如果數(shù)據(jù)塊已有更新，則將副本上更新的數(shù)據(jù)塊復(fù)制到原節(jié)點(diǎn)。接下來(lái)如果原節(jié)點(diǎn)的可用數(shù)據(jù)塊發(fā)生更新，則將副本設(shè)為無(wú)效。

（2）退化更新。退化更新操作分為對(duì)數(shù)據(jù)塊節(jié)點(diǎn)和校驗(yàn)塊節(jié)點(diǎn)兩種情況：①針對(duì)數(shù)據(jù)塊節(jié)點(diǎn)：先進(jìn)行退化讀操作，恢復(fù)原有數(shù)據(jù)塊，得到新數(shù)據(jù)塊并寫(xiě)入到熱備節(jié)點(diǎn)中形成副本，然后計(jì)算出新舊數(shù)據(jù)的更新差量，進(jìn)行常規(guī)的更新操作來(lái)更新所有校驗(yàn)塊；②針對(duì)校驗(yàn)塊節(jié)點(diǎn)：首先獲取校驗(yàn)塊狀態(tài)，如果處于可用狀態(tài)，則進(jìn)行常規(guī)更新操作，如果處于不可用狀態(tài)，則利用更新后的數(shù)據(jù)塊，計(jì)算相應(yīng)的新校驗(yàn)塊，并將新校驗(yàn)塊寫(xiě)入對(duì)應(yīng)的熱備節(jié)點(diǎn)中形成副本。

2.3永久故障解決方案

當(dāng)確定一個(gè)設(shè)備出現(xiàn)永久故障時(shí)，一般會(huì)立即觸發(fā)重構(gòu)操作。但由于糾刪碼有很強(qiáng)的可靠性，能夠容忍多節(jié)點(diǎn)同時(shí)故障，因而可采用一種延遲重構(gòu)的方法。延遲重構(gòu)方式的基本思想是降低重構(gòu)頻次，減少重構(gòu)消耗的網(wǎng)絡(luò)帶寬，同時(shí)不對(duì)可用性產(chǎn)生較大影響。可以采用的延遲方案有：

（1）對(duì)所有故障塊進(jìn)行延遲重構(gòu)。在網(wǎng)絡(luò)存儲(chǔ)環(huán)境中提出的一種解決方案是延遲故障塊的重構(gòu)，直到一個(gè)條帶的可用塊數(shù)目達(dá)到給定的恢復(fù)閾值r。例如，對(duì)于CRS（15，10），r=13，系統(tǒng)將等待出現(xiàn)一個(gè)條帶中有兩個(gè)塊出現(xiàn)故障時(shí)才觸發(fā)條帶的重構(gòu)。使用CRS（15，10）編碼延遲重構(gòu)的數(shù)據(jù)，永久丟失的概率大約等同于原始的CRS（14，10）進(jìn)行即時(shí)恢復(fù)的數(shù)據(jù)丟失概率，因?yàn)榛謴?fù)操作都是在僅有13個(gè)塊可用時(shí)進(jìn)行。

延遲重構(gòu)有兩個(gè)主要優(yōu)點(diǎn)：①恢復(fù)兩個(gè)塊的網(wǎng)絡(luò)成本和恢復(fù)一個(gè)塊成本相近，即恢復(fù)一個(gè)塊需要讀10個(gè)塊寫(xiě)入1個(gè)塊（總共11x帶寬），而恢復(fù)兩個(gè)塊需要讀10個(gè)塊寫(xiě)入2個(gè)塊（總共12x帶寬，或者平均每次恢復(fù)6x）；②如果一個(gè)塊由于臨時(shí)故障而不可用，如網(wǎng)絡(luò)消耗，延遲恢復(fù)可以使其有更多時(shí)間恢復(fù)到正?？捎脿顟B(tài)，從而避免了多余的修復(fù)。

系統(tǒng)模擬表明將重構(gòu)閾值減少1可能會(huì)極大地增大退化條帶的數(shù)目。例如，對(duì)于CRS（15，10），重構(gòu)閾值r=12，導(dǎo)致30%的存儲(chǔ)條帶處于退化狀態(tài)。另一方面，增加修復(fù)的閾值到r=13，能夠幫助減少退化條帶的數(shù)目，但會(huì)失去原來(lái)節(jié)省的網(wǎng)絡(luò)帶寬。

（2）結(jié)合臨時(shí)故障的精細(xì)延遲重構(gòu)。下面進(jìn)一步提出了與臨時(shí)故障處理相結(jié)合的更精細(xì)化的延遲重構(gòu)方案。將存儲(chǔ)系統(tǒng)中一個(gè)編碼條帶的故障程度表示為R，節(jié)點(diǎn)上出現(xiàn)臨時(shí)故障的編碼條帶比例為p%，有：R=∑ni=1r×（1-×p%）（1）這里的表示每個(gè)編碼條帶中已經(jīng)進(jìn)行退化讀或更新操作產(chǎn)生熱備副本的比例。公式（1）將編碼條帶組的臨時(shí)故障和永久故障情況進(jìn)行統(tǒng)一考慮，更加全面地對(duì)數(shù)據(jù)塊丟失概率和網(wǎng)絡(luò)恢復(fù)流量?jī)烧咧g進(jìn)行權(quán)衡。其中：γ=1節(jié)點(diǎn)處于永久故障狀態(tài)

p%節(jié)點(diǎn)處于臨時(shí)故障狀態(tài)（2）將閾值表示為limit，這里的limit可以動(dòng)態(tài)地自適應(yīng)調(diào)整，當(dāng)R≥limit時(shí)則開(kāi)始重構(gòu)操作：limitz + a = lim itZ + δ

lim itZ -（3）當(dāng)進(jìn)行了一次正常的重構(gòu)恢復(fù)操作時(shí)，即將limit值漸進(jìn)地增加δ（一個(gè)小增量）；當(dāng)出現(xiàn)由于延遲重構(gòu)而造成數(shù)據(jù)丟失的事件時(shí)，則懲罰性突變減少（一個(gè)大增量）。這里的初始閾值limit0是一個(gè)經(jīng)驗(yàn)初值，對(duì)于CRS（15，10）可配置為2或3。

3方案評(píng)估

3.1評(píng)估方案

評(píng)估一種重構(gòu)方案在減少修復(fù)帶寬、對(duì)系統(tǒng)可用性和可靠性影響等方面的作用是非常困難的，這里使用一個(gè)在GitHub開(kāi)源的分布式存儲(chǔ)系統(tǒng)模擬器DS-SIM來(lái)估計(jì)修復(fù)帶寬和系統(tǒng)可用性如何受故障事件、編碼方式和重構(gòu)方案等因素影響。

DS-SIM的輸入包括硬件配置規(guī)格說(shuō)明、存儲(chǔ)系統(tǒng)組件故障和重構(gòu)分布的統(tǒng)計(jì)性質(zhì)、編碼方案，模擬器返回穩(wěn)態(tài)和網(wǎng)絡(luò)帶寬利用的即刻值、退化條帶數(shù)目等。模擬參數(shù)如表1所示。

表1模擬系統(tǒng)參數(shù)參數(shù)數(shù)值總數(shù)據(jù)量4PB磁盤(pán)容量2T每個(gè)主機(jī)的磁盤(pán)數(shù)20每個(gè)機(jī)架的主機(jī)數(shù)20修復(fù)帶寬容量650TB/每天運(yùn)行周期10年迭代次數(shù)25，0003.2評(píng)估結(jié)果

對(duì)3種方案進(jìn)行了比較，包括：三副本、CRS（15，10）和采用高效重構(gòu)的NRS（15，10）。

。

4結(jié)語(yǔ)

針對(duì)分布式塊存儲(chǔ)系統(tǒng)的訪問(wèn)特點(diǎn)，本文設(shè)計(jì)了一種高效的糾刪碼重構(gòu)技術(shù)。對(duì)臨時(shí)故障和永久故障分別設(shè)計(jì)了相應(yīng)的解決方案，即對(duì)臨時(shí)故障采用一種糾刪碼和熱備副本相結(jié)合的故障處理方法，解決了臨時(shí)故障導(dǎo)致的退化讀/更新問(wèn)題，并從時(shí)間維度分散了永久故障的重構(gòu)成本，提升了重構(gòu)效率。同時(shí)精細(xì)地控制永久故障延遲重構(gòu)的時(shí)間點(diǎn)，在不影響讀寫(xiě)性能和數(shù)據(jù)可靠性的前提下，減少故障節(jié)點(diǎn)重構(gòu)次數(shù)，從而極大地減輕了重構(gòu)操作對(duì)網(wǎng)絡(luò)帶寬和磁盤(pán)造成的壓力。使用DS-SIM模擬器的評(píng)估結(jié)果表明，該重構(gòu)方案相對(duì)于原有的CRS方案減少了3倍的修復(fù)帶寬流量，同時(shí)對(duì)系統(tǒng)的可用性和可靠性影響很小；相對(duì)于三副本方案，該方案提高了系統(tǒng)的存儲(chǔ)效率與可靠性。

參考文獻(xiàn)：

[1]RASHMI K， NAKKIRAN P.Having your cake and eating It too：jointly optimal erasure codes for I/O，storage， and networkbandwidth[C]. USENIX Association，2015：8194.

[2]MURALIDHAR S， LLOYD W.f4：facebook's warm BLOB storage system[C].OSDI. USENIX Association，2014：383398.

[3]HUANG C， SIMITCI H，XU Y.Erasure coding in windows azure storage[C].ATC. USENIX Association，2012：2.

[4]WEIL S A， BRANDT S A.Ceph：a scalable，highperformance distributed file system[C].OSDI，2010：307320.

[5]劉磊.分布式塊存儲(chǔ)系統(tǒng)節(jié)能技術(shù)研究[D].武漢：華中科技大學(xué)，2013.

[6]羅象宏，舒繼武.存儲(chǔ)系統(tǒng)中的糾刪碼研究綜述[J].計(jì)算機(jī)研究與發(fā)展，2012， 49（1）：234240.

[7]LI X，ZHENG Q，QIAN H.Toward optimizing cauchy matrix for cauchy reedsolomon code[J].IEEE Communications Letters，2009：603605.

[8]PLANK J S， LUO J.A performance evaluation and examination of opensource erasure coding libraries for storage[C].CFST.2009：253265.

[9]RASHMI K V，SHAH N B.A hitchhiker's guide to fast and efficient data reconstruction in erasurecoded data centers[J].Acm SCCR，2014：331342.

[10]鄭清吉.安全存儲(chǔ)系統(tǒng)中糾刪碼技術(shù)研究[D].上海：上海交通大學(xué)，2009.

[11]朱云鋒.分布式存儲(chǔ)系統(tǒng)中基于糾刪碼的容錯(cuò)技術(shù)研究[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2014.