分布式存儲中基于糾刪碼的數據容錯技術研究.pdf

1、大規(guī)模分布式存儲為現(xiàn)代的商業(yè)計算、科學計算等應用提供底層的數據存取服務，已經成為現(xiàn)代社會的信息基礎設施。隨著數據規(guī)模的急劇膨脹，現(xiàn)代分布式存儲系統(tǒng)中節(jié)點的規(guī)模往往達到百萬級以上，數據的規(guī)模也達到PB級甚至EB級。數據失效已經成為大規(guī)模存儲系統(tǒng)常態(tài)化的行為，因此如何提高容錯能力已經成為分布式存儲系統(tǒng)所面臨的嚴峻挑戰(zhàn)。分布式存儲主要通過數據冗余提高數據的容錯能力。常用的容錯技術包括基于復制的容錯技術和基于糾刪碼的容錯技術?；趶椭频娜蒎e技術

2、通過為每個數據對象創(chuàng)建多個副本來提高容錯性，存儲開銷巨大，難以適應大數據時代的數據規(guī)模?；诩m刪碼的容錯技術能夠在保持相同容錯能力的基礎上，極大地降低存儲開銷，成為當前分布式存儲領域研究的熱點?；诩m刪碼的容錯技術面臨的主要挑戰(zhàn)在于：(1)現(xiàn)有的串行編解碼方法效率較低，極大的阻礙了糾刪碼在分布式存儲中的應用；(2)在有數據塊失效的情況下，數據的讀取效率急劇下降，難以滿足用戶的數據訪問請求；(3)修復失效數據塊時需要傳輸大量的數據，修復成

3、本高。本文圍繞上述挑戰(zhàn)，針對基于糾刪碼的容錯技術進行了深入研究。
　　目前已有的糾刪碼串行編解碼方法在單個CPU核上因伽羅瓦域上的計算開銷較大導致其編解碼效率較低，并行化技術是提高編解碼效率的一種重要方法。但是目前已有的并行編解碼方法則存在如下問題：(1)局限于特定的硬件平臺或者某種特殊的糾刪碼方法導致其適用范圍有限、通用性較差；(2)并行化時沒有深入分析糾刪碼的編解碼特點以及數據讀寫的I/O特性導致并行化的效率不高；(3)采用系

4、統(tǒng)默認的線程調度策略導致線程切換開銷較大。針對上述問題，提出了一種面向多核平臺的通用并行編解碼方法ParaErasure。在ParaErasure方法中，首先對并行編解碼過程進行分析建模，提出了一種能夠適用于所有糾刪碼的通用多線程并行編解碼模型MTPErasure；其次在MTPErasure的基礎上針對不同的I/O環(huán)境分別提出了兩種不同的并行編解碼算法。針對高速I/O環(huán)境下數據吞吐量大導致不同線程之間的數據同步開銷相對較大的特點，提出了

5、一種基于靜態(tài)數據劃分的并行編解碼算法sdaParallel。該算法采用靜態(tài)數據劃分的方法，將需要編解碼的數據對象靜態(tài)地劃分成若干更小的數據對象，再為每個小數據對象分配一個單獨的線程實現(xiàn)數據的讀取、編解碼以及寫入過程，以降低高速I/O環(huán)境下線程之間的數據同步開銷并提高編解碼效率；針對低速I/O環(huán)境下數據吞吐量小導致線程切換的開銷相對較大的特點，提出了一種基于動態(tài)數據劃分的并行編解碼算法ddaParallel。該算法采用動態(tài)數據劃分的方法，

6、將需要編解碼的數據對象按照編解碼的基本單位劃分成條，由兩個單獨的I/O線程分別執(zhí)行數據條的讀取和寫入，由多個編解碼線程動態(tài)地對讀寫就緒的數據條執(zhí)行編解碼過程，以降低線程切換開銷并提高編解碼效率。在ParaErasure方法中，提出了一個獨占式的線程調度算法使得編解碼線程可以在一個CPU核上運行盡可能多的時間從而降低線程切換開銷。實驗結果表明，與目前已有的串行編解碼方法相比，ParaErasure方法在低速I/O環(huán)境下的加速比達到1.3倍

7、以上，在高速I/O環(huán)境下的加速比達到5倍以上，顯著提升了糾刪碼的編解碼效率。
　　目前已有的數據分塊方法把原始數據對象簡單地分割成若干個大小相等的數據塊，因此地址連續(xù)的數據條被分配到同一個數據塊，導致在數據塊失效情況下執(zhí)行數據讀取操作時，需要從多個節(jié)點讀取大量的數據以解碼修復得到用戶請求的數據，帶來較大的網絡傳輸開銷和解碼計算開銷，影響數據讀取效率。針對已有分塊方法存在的上述開銷較大且效率較低的問題，提出了一種基于條映射的離散數據

8、分塊方法d-dividing。d-dividing方法按照編解碼的基本單位將數據對象分割成大量的數據條，然后依據映射的方式對數據條進行分組，以完成數據的分塊過程。d-dividing方法在對數據條進行映射時，為了最小化分塊以后數據讀取操作的網絡開銷和計算開銷，以降低數據塊失效情況下數據讀取時的數據傳輸總量和解碼計算量為目標，把在原始數據對象中位置連續(xù)的數據條離散地映射給不同的數據塊。在數據塊失效的情況下，d-dividing方法使得數據

9、讀取過程中每一次解碼計算均能夠獲得用戶請求的若干個地址連續(xù)的數據條，而在傳統(tǒng)分塊方法中每次解碼計算往往只能得到一個用戶請求的數據條。因此，d-dividing方法能夠降低數據讀取時的網絡傳輸開銷，同時減少解碼計算的次數，提高數據讀取的效率。實驗結果表明，與目前已有的數據分塊方法相比，當有超過2個數據塊失效時，d-dividing方法降低了50％的數據傳輸總量，減少了40%的解碼計算次數，提升了約1倍的數據讀取效率。
　　針對目前已

10、有的多節(jié)點并行修復方法因鏈路競爭導致成功修復概率和數據可用性均較低的問題，提出了一種基于分組迭代的多節(jié)點并行修復方法GIMPR。GIMPR方法把對多個失效節(jié)點的修復轉化成一個可以迭代執(zhí)行的循環(huán)過程，每一次迭代循環(huán)被分成三個步驟：(1)從所有失效節(jié)點中選擇部分失效節(jié)點組成一個可以并行修復的分組。為了提高分組內失效節(jié)點的數量以增加修復的并行度，提出了一種基于貪心策略的分組構建算法GSGC，該算法按照屬于不同數據對象的失效節(jié)點優(yōu)先的方式，不斷

11、地把提供節(jié)點集合互不相交的失效節(jié)點加入到分組中，直到分組中節(jié)點的數量達到最大；(2)為分組中的每個節(jié)點構建修復拓撲。為了降低分組中每個失效節(jié)點的修復開銷，提出了一種基于生成樹的自適應修復拓撲構建算法ARTC。ARTC算法把盡可能多的提供節(jié)點包含到修復拓撲中以減小數據傳輸總量；(3)對分組中的所有失效節(jié)點并行地執(zhí)行修復。修復時采用再生碼技術，讓修復需要的數據沿著樹型結構的修復拓撲從葉節(jié)點向根節(jié)點傳輸，并在中間節(jié)點進行編碼合并以減小網絡開銷