副本策略和糾刪碼是存儲領(lǐng)域常見的兩種數(shù)據(jù)冗余技術(shù)。相比于副本策略苛吱，糾刪碼具有更高的磁盤利用率刚陡。 Reed-Solomon碼是一種常見的糾刪碼陆盘。
Erasure Code是一種編碼技術(shù)舷蟀，它可以將n份原始數(shù)據(jù)恤磷，增加m份數(shù)據(jù)，并能通過n+m份中的任意n份數(shù)據(jù)雪侥，還原為原始數(shù)據(jù)碗殷。即如果有任意小于等于m份的數(shù)據(jù)失效，仍然能通過剩下的數(shù)據(jù)還原出來速缨。 糾刪碼技術(shù)在分布式存儲 系統(tǒng)中的應(yīng)用主要有三類，陣列糾刪碼（Array Code: RAID5代乃、RAID6等）旬牲、RS(Reed-Solomon)里德-所羅門類糾刪碼和LDPC(LowDensity Parity Check Code)低密度奇偶校驗糾刪碼。 LDPC碼目前主要用于通信搁吓、視頻和音頻編碼等領(lǐng)域原茅。
多副本策略即將數(shù)據(jù)存儲多個副本（一般是三副本，比如HDFS）堕仔，當某個副本丟失時擂橘，可以通過其他副本復制回來。三副本的磁盤利用率為1/3摩骨。
糾刪碼技術(shù)主要是通過糾刪碼算法將原始的數(shù)據(jù)進行編碼得到冗余通贞，并將數(shù)據(jù)和冗余一并存儲起來朗若，以達到容錯的目的。其基本思想是將n塊原始的數(shù)據(jù)元素通過一定的計算昌罩，得到m塊冗余元素（校驗塊）哭懈。對于這n+m塊的元素，當其中任意的m塊元素出錯（包括原始數(shù)據(jù)和冗余數(shù)據(jù)）時茎用，均可以通過對應(yīng)的重構(gòu)算法恢復出原來的n塊數(shù)據(jù)遣总。生成校驗的過程被成為編碼（encoding），恢復丟失數(shù)據(jù)塊的過程被稱為解碼（decoding）轨功。磁盤利用率為n/(n+m)旭斥。基于糾刪碼的方法與多副本方法相比具有冗余度低古涧、磁盤利用率高等優(yōu)點垂券。
兩種冗余技術(shù)對比如下表：
| 兩種技術(shù) | 磁盤利用率 | 計算開銷 | 網(wǎng)絡(luò)消耗 | 恢復效率 |
|---|---|---|---|---|
| 多副本(3副本) | 1/3 | 幾乎沒有 | 較低 | 較高 |
| 糾刪碼(n+m) | n/(n+m) | 高 | 較高 | 較低 |
Reed-Solomon(RS)碼
Reed-Solomon（RS）碼是存儲系統(tǒng)較為常用的一種糾刪碼，它有兩個參數(shù)n和m蒿褂，記為RS(n,m)圆米。n代表原始數(shù)據(jù)塊個數(shù)。m代表校驗塊個數(shù)啄栓。接下來介紹RS碼的原理娄帖。
RS碼原理
以n=5，m=3為例昙楚。即5個原始數(shù)據(jù)塊近速，乘上一個(n+m)n的矩陣，然后得出一個(n+m)1的矩陣堪旧。根據(jù)矩陣特點可以得知結(jié)果矩陣中前面5個值與原來的5個數(shù)據(jù)塊的值相等削葱，而最后3個則是計算出來的校驗塊。
以上過程為編碼過程淳梦。D是原始數(shù)據(jù)塊析砸，得到的C為校驗塊。
假設(shè)丟失了m塊數(shù)據(jù)爆袍。如下：
那我們?nèi)绾螐氖Ｓ嗟膎個數(shù)據(jù)塊（注意首繁，這里剩余的n塊可能包含幾個原始數(shù)據(jù)塊+幾個校驗塊）恢復出來原始的n個數(shù)據(jù)塊呢，就需要通過下面的decoding（解碼）過程來實現(xiàn)陨囊。
第一步：從編碼矩陣中刪去丟失數(shù)據(jù)塊和丟失編碼塊對應(yīng)行弦疮。 將刪掉m個塊的(n+m)1個矩陣變形為n1矩陣，同時B矩陣也需要刪掉對應(yīng)的m個行得出一個B'的變形矩陣蜘醋，這個B'就是n*n矩陣胁塞。如下：假設(shè)D1、D4、C2丟失啸罢，我們得到如下B’矩陣及等式编检。
第二步：求出B’的逆矩陣。
第三步：等式兩邊分別乘上B’的逆矩陣伺糠。
B’和它的逆矩陣相乘得到單位矩陣I蒙谓，如下：
左邊只剩下原始數(shù)據(jù)矩陣D：
至此完成解碼過程。
注：圖中黃色部分為范德蒙矩陣训桶。至于如何生成B矩陣累驮，以及如何求B’的逆矩陣，請查看其他相關(guān)文獻舵揭，這里不再贅述谤专。
RS的特點
- 低冗余度，高磁盤利用率午绳。
- 數(shù)據(jù)恢復代價高置侍。 丟失數(shù)據(jù)塊或者編碼塊時， RS需要讀取n個數(shù)據(jù)塊和校驗塊才能恢復數(shù)據(jù)拦焚， 數(shù)據(jù)恢復效率也在一定程度上制約了RS的可靠性蜡坊。
- 數(shù)據(jù)更新代價高。 數(shù)據(jù)更新相當于重新編碼赎败， 代價很高秕衙， 因此常常針對只讀數(shù)據(jù)，或者冷數(shù)據(jù)僵刮。
工程實踐中据忘，一般對于熱數(shù)據(jù)還是會使用多副本策略來冗余，冷數(shù)據(jù)使用糾刪碼搞糕。
糾刪碼引擎
ISA-L
糾刪碼作為 ISA-L 庫所提供的功能之一勇吊，其性能應(yīng)該是目前業(yè)界最佳。需要注意的是 Intel 采用的性能測試方法與學術(shù)界常用的方式略有出路窍仰，其將數(shù)據(jù)塊與冗余塊的尺寸之和除以耗時作為速度汉规，而一般的方法是不包含冗余塊的。另外驹吮，ISA-L 未對 vandermonde 矩陣做特殊處理鲫忍，而是直接拼接單位矩陣作為其編碼矩陣，因此在某些參數(shù)下會出現(xiàn)編碼矩陣線性相關(guān)的問題钥屈。好在 ISA-L 提供了cauchy 矩陣作為第二方案。
ISA-L 之所以速度快坝辫，一方面是由于 Intel 諳熟匯編優(yōu)化之道篷就，其次是因為它將整體矩陣運算搬遷到匯編中進行。但這導致了匯編代碼的急劇膨脹近忙，令人望而生畏竭业。
Jerasure2.0
不同于 ISA-L 直接使用匯編代碼智润，Jerasure2.0 使用 C 語言封裝后的指令，這樣代碼更加的友好未辆。另外 Jerasure2.0 不僅僅支持 GF(2^8) 有限域的計算，其還可以進行 GF(2^4) - GF(2^128) 之間的有限域。并且除了 RS 碼网棍，還提供了 Cauchy Reed-Solomon code （CRS 碼）等其他編碼方法的支持通孽。它在工業(yè)應(yīng)用之外，其學術(shù)價值也非常高拙友。目前其是使用最為廣泛的編碼庫之一为狸。目前 Jerasure2.0 并不支持 AVX 加速，盡管如此遗契，不過在僅使用 SSE 的情況下辐棒，Jerasure2.0 依然提供了非常高的性能表現(xiàn)。不過主要作者之一 James S. Plank 教授轉(zhuǎn)了研究方向牍蜂，另外一位作者 Greenan 博士早已加入工業(yè)界漾根。因此后續(xù)的維護將是個比較大的問題。
klauspost 的 ReedSolomon
klauspost 利用 Golang 的匯編支持鲫竞，友好地使用了 SIMD 技術(shù)辐怕，此款引擎的 SIMD 加速部分是目前我看到的實現(xiàn)中最為簡潔的，矩陣運算的部分邏輯被移到了外層高級語言中贡茅，加上 Golang 自帶的匯編支持秘蛇，使得匯編代碼閱讀起來更佳的友好。不過 Go 并沒有集成所有指令顶考，部分指令不得不利用 YASM 等匯編編譯器將指令編譯成字節(jié)序列寫入?yún)R編文件中赁还。一方面導致了指令的完全不可讀，另外一方面這部分代碼的語法風格是 Intel 而非 Golang 匯編的 AT&T 風格驹沿，平添了迷惑艘策。這款引擎比較明顯的缺陷有兩點：1.對于較大的數(shù)據(jù)塊，編碼速度會有巨大的下滑渊季；2.修復速度明顯慢于編碼速度朋蔫。
Hadoop 3.0 開始支持 糾刪碼(EC)存儲。
Swift現(xiàn)在支持糾刪碼(EC)存儲策略類型却汉。
這樣部署人員驯妄、以極少的RAW容量達到極高的可用性，如同在副本存儲中一樣合砂。然而青扔，EC需要更多的CPU和網(wǎng)絡(luò)資源，所以并不適合所有應(yīng)用場景。EC非常適合在一個獨立的區(qū)域內(nèi)極少訪問的微猖、大容量數(shù)據(jù)谈息。
Swift糾刪碼的實現(xiàn)對于用戶是透明的。對于副本存儲和糾刪碼存儲的類型凛剥，在API上沒有任何區(qū)別侠仇。
為了支持糾刪碼，Swift現(xiàn)在需要依賴PyECLib和liberasurecode犁珠。liberasurecode是一個可插件式的庫逻炊，允許在你選擇的庫中實現(xiàn)EC算法。
糾刪碼優(yōu)/劣勢
優(yōu)勢
糾刪碼技術(shù)作為一門數(shù)據(jù)保護技術(shù)盲憎，自然有許多的優(yōu)勢嗅骄，首先可以解決的就是目前分布式系統(tǒng)，云計算中采用副本來防止數(shù)據(jù)的丟失饼疙。副本機制確實可以解決數(shù)據(jù)丟失的問題溺森，但是翻倍的數(shù)據(jù)存儲空間也必然要被消耗，這一點卻是非常致命的窑眯。EC技術(shù)的運用就可以直接解決這個問題屏积。
劣勢
EC技術(shù)的優(yōu)勢確實明顯，但是他的使用也是需要一些代價的磅甩，一旦數(shù)據(jù)需要恢復炊林，他會造成2大資源的消耗:
1、網(wǎng)絡(luò)帶寬的消耗卷要，因為數(shù)據(jù)恢復需要去讀其他的數(shù)據(jù)塊和校驗塊
2渣聚、進行編碼，解碼計算需要消耗CPU資源
就是既耗網(wǎng)絡(luò)又耗CPU
總結(jié)
最好的選擇是用于冷數(shù)據(jù)集群僧叉，有下面2點原因可以支持這種選擇
1奕枝、冷數(shù)據(jù)集群往往有大量的長期沒有被訪問的數(shù)據(jù)，體量確實很大瓶堕，采用EC技術(shù)隘道，可以大大減少副本數(shù)
2、冷數(shù)據(jù)集群基本穩(wěn)定郎笆，耗資源量少谭梗，所以一旦進行數(shù)據(jù)恢復，將不會對集群造成大的影響
出于上述2種原因宛蚓，冷數(shù)據(jù)集群無非是一個很好的選擇激捏。
擴展閱讀：
HDFS EC：將糾刪碼技術(shù)融入HDFS
Erasure Code - EC糾刪碼原理
原文鏈接：
糾刪碼（Erasure Code）淺析
https://blog.csdn.net/runningtortoises/article/details/51567417
