通過本文可以獲得如下知識：
① XOR碼茅坛、RS碼的基本原理和恢復(fù)過程實(shí)例。
② 圖解HDFS EC中block group（塊組）的概念弄喘、圖解striped layout（條帶布局）和連續(xù)布局玖喘，以及它們的優(yōu)缺點(diǎn)比較。用一個實(shí)例一步一步分析divideByteRangeIntoStripes方法生成的cells蘑志、ranges累奈、striped數(shù)組。
③ HDFS EC的核心源碼流程急但。
④ HDFS EC優(yōu)勢與劣勢费尽。
一、準(zhǔn)備工作
在存儲系統(tǒng)中羊始，糾刪碼技術(shù)主要是通過利用糾刪碼算法將原始的數(shù)據(jù)進(jìn)行編碼得到校驗(yàn)旱幼，并將數(shù)據(jù)和校驗(yàn)一并存儲起來，以達(dá)到容錯的目的突委。
1.1 幾個專業(yè)術(shù)語
Legacy coder: 遺留版本的Java RS碼柏卤，起源于Facebook的HDFS-RAID項(xiàng)目。
ISA-L: 實(shí)現(xiàn)RS算法的英特爾存儲加速庫匀油，為Intel指令集如SSE缘缚、AVX、AVX2和AVX-512提供性能優(yōu)化敌蚜。
ISA-L coder: 利用Intel ISA-L庫的本地（native）RS編碼器桥滨。
New Java coder: Reed-Solomon算法的純Java實(shí)現(xiàn)(適用于沒有所需CPU型號的系統(tǒng))。這個編碼器與ISA-L編碼器兼容弛车，還利用了JVM的自動向量化特性齐媒。
1.2 XOR碼（異或碼）
異或運(yùn)算：相同為0,不同為1。
滿足如下兩個運(yùn)算律：
交換律: B1⊕ B2 = B2⊕ B1
結(jié)合律: B1⊕ [B2⊕ B3] = [B1⊕ B2]⊕ B3
例如：
1 ⊕ 1 = 0;
0 ⊕ 0 = 0;
1 ⊕ 0 = 1;
0 ⊕ 1 = 1;
0 ⊕ 1 ⊕ 1 = 0;
現(xiàn)在我們假設(shè)下面式子中某一位丟失了纷跛。比如第一位0數(shù)據(jù)丟失了
0 ⊕ 1 ⊕ 1 = 0;
丟失后變成：
? ⊕ 1 ⊕ 1 = 0;
我們怎么恢復(fù)0這個數(shù)據(jù)呢喻括？這時候可以利用異或的結(jié)合律了。
? ⊕ 1 ⊕ 1 = ? ⊕ (1 ⊕ 1) = ? ⊕ 0 = 0
因此缺失的數(shù)據(jù)為0贫奠。
但是異或碼過于簡單了唬血，存在可容忍錯誤過少的問題望蜡。例如如果我們丟失了2位的數(shù)據(jù)，那就沒法恢復(fù)了拷恨。而在實(shí)際的場景下脖律，肯定會發(fā)生多個數(shù)據(jù)丟失的問題的，因此需要引入其他的糾刪碼來幫助我們解決這個問題腕侄。比如后面正文會介紹到的RS碼等小泉。
二、Reed Solomon Encoding（RS碼）
RS碼兜挨，中文名稱里德所羅門編碼。是EC編碼中一種眯分。本小節(jié)先介紹RS碼的基本思想拌汇，然后通過一個運(yùn)算實(shí)例幫助理解RS的工作原理。
RS碼是存儲系統(tǒng)較為常用的一種糾刪碼弊决，它有兩個參數(shù) k和 m噪舀，記為RS(k，m)飘诗。k代表的是data cell數(shù)據(jù)塊的數(shù)量,m代表的是parity cell塊的數(shù)量,parity cell可理解為校驗(yàn)塊,因?yàn)樗怯蓴?shù)據(jù)塊進(jìn)行編碼運(yùn)算后產(chǎn)生的与倡。
RS碼的基本思想：
- 將ｋ塊原始的數(shù)據(jù)元素通過一定的編碼計算，得到 ｍ 塊校驗(yàn)元素昆稿；
- 對于這ｋ+ｍ塊元素纺座，當(dāng)其中任意的ｍ塊元素出錯（包括數(shù)據(jù)和校驗(yàn)出錯），均可以通過對應(yīng)的重構(gòu)算法恢復(fù)出原來的ｋ塊數(shù)據(jù);
- 生成校驗(yàn)的過程被成為編碼（encoding）溉潭，恢復(fù)丟失數(shù)據(jù)塊的過程被稱為解碼（decoding）净响。
如上圖所示：
- k個數(shù)據(jù)塊組成一個向量被乘上一個生成矩陣（Generator Matrix）GT（G的轉(zhuǎn)置矩陣）從而得到一個碼字（codeword）向量，該向量由k個數(shù)據(jù)塊和m個校驗(yàn)塊構(gòu)成;
- 如果一個數(shù)據(jù)塊丟失喳瓣，可以用(GT)-1（G的轉(zhuǎn)置矩陣的逆矩陣馋贤，這個需要一些線性代數(shù)的知識。兩邊同時左乘這個逆矩陣畏陕，就能將GT消掉）乘以碼字向量來恢復(fù)出丟失的數(shù)據(jù)塊配乓；
- RS(k，m)最多可容忍m 個塊（包括數(shù)據(jù)塊和校驗(yàn)塊）丟失惠毁。
RS碼數(shù)據(jù)恢復(fù)實(shí)例：
我們以RS(5,3)為例來計算：
其中犹芹，1，5鞠绰，7羽莺，5，5為數(shù)據(jù)塊洞豁，23盐固，77荒给，289為范德蒙矩陣（可百度一下這個矩陣）生成的校驗(yàn)塊。現(xiàn)在我們來看下刁卜，23, 77, 289這三個校驗(yàn)塊到底能不能在丟失數(shù)據(jù)塊的時候?qū)?shù)據(jù)恢復(fù)出來志电。
假設(shè)在一個極端情況下，五個數(shù)據(jù)塊丟失了三個蛔趴，也就是可以容忍的最大數(shù)量挑辆，比如，丟失了數(shù)據(jù)塊的前三個數(shù)：1孝情，5鱼蝉，7。此時把丟失的數(shù)據(jù)塊和其對應(yīng)的生成矩陣的行去掉箫荡，然后用生成矩陣的逆矩陣乘以校驗(yàn)塊和剩余的數(shù)據(jù)塊組成的矩陣魁亦。
