陳付 張淑萍

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

關鍵詞關鍵詞：云存儲；分布式塊存儲；糾刪碼；重構效率

DOIDOI：10.11907/rjdk.161381

中圖分類號：TP301文獻標識碼：A文章編號文章編號：16727800（2016）007003303

0引言

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

1相關技術

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

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

1.2糾刪碼容錯技術

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

2方案設計

2.1臨時故障與永久故障

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

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

2.2臨時故障解決方案

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

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

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

2.3永久故障解決方案

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

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

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

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

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

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

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

3方案評估

3.1評估方案

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

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

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

對3種方案進行了比較，包括：三副本、CRS（15，10）和采用高效重構的NRS（15，10）。

。

4結語

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

參考文獻：

[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]劉磊.分布式塊存儲系統(tǒng)節(jié)能技術研究[D].武漢：華中科技大學，2013.

[6]羅象宏，舒繼武.存儲系統(tǒng)中的糾刪碼研究綜述[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]鄭清吉.安全存儲系統(tǒng)中糾刪碼技術研究[D].上海：上海交通大學，2009.

[11]朱云鋒.分布式存儲系統(tǒng)中基于糾刪碼的容錯技術研究[D].長沙：國防科學技術大學，2014.