分布式存儲(chǔ)中基于糾刪碼的數(shù)據(jù)容錯(cuò)技術(shù)研究.pdf

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

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

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

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

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

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

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

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

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

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

11、地把提供節(jié)點(diǎn)集合互不相交的失效節(jié)點(diǎn)加入到分組中，直到分組中節(jié)點(diǎn)的數(shù)量達(dá)到最大；(2)為分組中的每個(gè)節(jié)點(diǎn)構(gòu)建修復(fù)拓?fù)?。為了降低分組中每個(gè)失效節(jié)點(diǎn)的修復(fù)開銷，提出了一種基于生成樹的自適應(yīng)修復(fù)拓?fù)錁?gòu)建算法ARTC。ARTC算法把盡可能多的提供節(jié)點(diǎn)包含到修復(fù)拓?fù)渲幸詼p小數(shù)據(jù)傳輸總量；(3)對(duì)分組中的所有失效節(jié)點(diǎn)并行地執(zhí)行修復(fù)。修復(fù)時(shí)采用再生碼技術(shù)，讓修復(fù)需要的數(shù)據(jù)沿著樹型結(jié)構(gòu)的修復(fù)拓?fù)鋸娜~節(jié)點(diǎn)向根節(jié)點(diǎn)傳輸，并在中間節(jié)點(diǎn)進(jìn)行編碼合并以減小網(wǎng)絡(luò)開銷