一锦募、背景

• 傳統(tǒng)各大互聯(lián)網(wǎng)公司在大規(guī)模數(shù)據(jù)存儲摆屯，包括私有云和公有云，技術(shù)選型上基本核心都是n-way replication糠亩，如典型的1主3備的架構(gòu)虐骑。
• n-way replication技術(shù)在帶來高可用性的同時准验，伴隨著巨大的冗余存儲成本，因此近年來各大公司都在用很多trick減少冗余備份的投入
• EC編碼的理論已經(jīng)有20多年的歷史了廷没，但知道最近幾年再P2P領(lǐng)域中發(fā)揮作用才被大家重視起來

二沟娱、EC技術(shù)

1、What

erasure code可以認(rèn)為是RAID的通式腕柜，任何RAID都可以轉(zhuǎn)換為特定的erasure code济似。在傳統(tǒng)的RAID中，僅支持少量的磁盤分布盏缤，當(dāng)系統(tǒng)中存在多個分發(fā)點和多節(jié)點時砰蠢，RAID將無法滿足需求。比如RAID5只支持一個盤失效唉铜，即使是RAID6也僅支持兩個盤失效台舱，所以支持多個盤失效的算法也就是erasure code是解決這一問題的辦法。(Erasure Code作為可有效提升存儲效率潭流、安全性和便捷性的新興存儲技術(shù))

定義：erasure code是一種技術(shù)竞惋，它可以將n份原始數(shù)據(jù)，增加m份數(shù)據(jù)(用來存儲erasure編碼)灰嫉，并能通過n+m份中的任意n份數(shù)據(jù)拆宛，還原為原始數(shù)據(jù)。定義中包含了encode和decode兩個過程讼撒，將原始的n份數(shù)據(jù)變?yōu)閚+m份是encode浑厚，之后這n+m份數(shù)據(jù)可存放在不同的device上，如果有任意小于m份的數(shù)據(jù)失效根盒，仍然能通過剩下的數(shù)據(jù)還原出來钳幅。也就是說，通常n+m的erasure編碼炎滞，能容m塊數(shù)據(jù)故障的場景敢艰，這時候的存儲成本是1+m/n，通常m<n册赛。因此钠导，通過erasure編碼，我們能夠把副本數(shù)降到1.x击奶。

Paste_Image.png

2辈双、Where

凡是需要通過冗余來進(jìn)行高可用的場景。但總體來說柜砾，主要運用于存儲和數(shù)字編碼領(lǐng)域。

• 陣列
  如果磁盤陣列需要使用高級特性换衬，比如需要能夠容錯兩個磁盤失效（RAID6）痰驱，那么可以用n+2的模式证芭；如果想容錯4個磁盤失效，則可使用n+4的模式担映。
• 云存儲
  erasure code是云存儲的核心技術(shù)废士，最初諸如hadoop, GFS，CEPH等都采用的是n-way replication來做冗余蝇完，但是這樣會帶來極大的成本開銷官硝，因此幾乎各大公司都在用erasure code替代n-way replication，之后我還會簡要介紹一下具體他們使用的模式短蜕。
• P2P領(lǐng)域
  erasure code 的理論起碼也有20年的歷史了氢架，但真正實踐可能也就最近幾年的時間，在P2P領(lǐng)域朋魔，動態(tài)的分布和智能的容錯岖研，特別是對短暫失效是非常關(guān)鍵的。以往的算法或多或少都有點山寨的感覺警检，而借助erasure code之后孙援，將會使P2P的算法更具有數(shù)學(xué)的嚴(yán)謹(jǐn)性。
• 數(shù)字編碼
  erasure code本身就是出自編碼理論扇雕，所以在這一塊具有先天的優(yōu)勢拓售。

3、How

最常見的Erasure Code是Reed Solomon算法镶奉，如圖邻辉，RS codes定義了一個(n + m) * n的分發(fā)矩陣(Distribution Matrix) 。

Paste_Image.png

1) Encode

對每一段的n份數(shù)據(jù)腮鞍，我們都可以通過B * D 得到得到對n份數(shù)據(jù)的Encode結(jié)果即n+m分?jǐn)?shù)據(jù)值骇。

Paste_Image.png

2) Decode

Decode的過程對應(yīng)著存在數(shù)據(jù)受損時，可以由任意n份數(shù)據(jù)恢復(fù)出其他受損數(shù)據(jù)移国。這個過程分成2個階段：恢復(fù)原始數(shù)據(jù)吱瘩、恢復(fù)編碼數(shù)據(jù)。

假設(shè)如上圖中的原始數(shù)據(jù)D1~5對應(yīng)的編碼后存儲數(shù)據(jù)中D1, D4, C2 失效

a) 恢復(fù)原始數(shù)據(jù)

Step1: 可以同時從矩陣B和B*D中迹缀，去掉相應(yīng)的行使碾，得到下面的等式：

Paste_Image.png

Step2: 用Survivors數(shù)據(jù)恢復(fù)原始數(shù)據(jù)D1~5，我們只需簡單的做矩陣乘法：

Paste_Image.png

因為(B')^-1 * B' = I 單位矩陣祝懂，所以我們就秋得了原始矩陣D：

Paste_Image.png

b) 恢復(fù)編碼數(shù)據(jù)

矩陣B是已知的票摇，原始數(shù)據(jù)D已經(jīng)完成恢復(fù)，只需要再做一次Encode的過程即可砚蓬。因為是矩陣乘法矢门，只取出受損數(shù)據(jù)對應(yīng)的行進(jìn)行矩陣乘即可。

參考文檔[http://blog.csdn.net/sinat_27186785/article/details/52034588]