隨著計算機技術(shù)和存儲技術(shù)的發(fā)展，數(shù)據(jù)正以爆炸式的速度增長，海量數(shù)據(jù)對存儲系統(tǒng)提出了巨大的挑戰(zhàn)。為了保障存儲系統(tǒng)的CAP，Consistency（一致性）、 Availability（可用性）、Partition tolerance（分區(qū)容錯性），對于可用性來說常見的2種技術(shù)是多副本和糾刪碼，多副本就是把數(shù)據(jù)復(fù)制多份分別存儲到不同地方以實現(xiàn)冗余備份，這種方法容錯性能較好但存儲利用率低，比較典型的3副本磁盤利用率僅33.33%，當(dāng)系統(tǒng)數(shù)據(jù)量很大時，多副本帶來巨大的額外存儲空間消耗，導(dǎo)致TCO居高不下。糾刪碼技術(shù)以犧牲CPU計算量和網(wǎng)絡(luò)負(fù)載為代價，提高存儲空間利用率，同時提供近似副本的可靠性。

糾刪碼(Erasure Coding, EC)算法起源于1960年，最早應(yīng)用于通信系統(tǒng)領(lǐng)域。最著名的是范德蒙RS編碼Reed-Solomon。隨著時間的推移，出現(xiàn)了一些變種算法，例如柯西RS編碼等。目前，糾刪碼技術(shù)在分布式存儲系統(tǒng)中的應(yīng)用主要有三類，陣列糾刪碼（Array Code: RAID5、RAID6等）、RS(Reed-Solomon)里德-所羅門類糾刪碼和LDPC(LowDensity Parity Check Code)低密度奇偶校驗糾刪碼。糾刪碼首先對原始數(shù)據(jù)進行分片，然后基于分片編碼生成備份數(shù)據(jù)，最后將原始數(shù)據(jù)和備份數(shù)據(jù)分別寫入不同的存儲介質(zhì)。數(shù)據(jù)恢復(fù)是編碼的逆運算(為了能夠進行數(shù)據(jù)恢復(fù)，要求編碼采用的方法(函數(shù))一定可逆)，因此也稱為解碼。

目前一些主流的云存儲廠商都采用EC編碼方式。

Reed-Solomon實現(xiàn)原理

假設(shè)存儲系統(tǒng)由n塊磁盤組成，我們將它分為k個磁盤來保存數(shù)據(jù)，這樣m=n-k個磁盤保存編碼信息，分別對數(shù)據(jù)進行編碼，允許最多m個磁盤出現(xiàn)故障(可以是數(shù)據(jù)盤也可以是編碼盤)。編碼和解碼行為如圖1所示。通過編碼，k個數(shù)據(jù)盤的內(nèi)容被用來計算m個編碼盤的內(nèi)容。當(dāng)m個磁盤出現(xiàn)故障，利用現(xiàn)有的磁盤數(shù)據(jù)通過解碼算法可以還原得到所有丟失的數(shù)據(jù)內(nèi)容，從而實現(xiàn)恢復(fù)。

圖1 糾刪碼基本原理圖

編碼原理

RS編碼以word為編碼和解碼單位，大的數(shù)據(jù)塊拆分到字長為w（取值一般為8或者16位）的word，然后對word進行編解碼。數(shù)據(jù)塊的編碼原理與word編碼原理相同，后文中一word為例說明，變量Di, Ci將代表一個word。

把輸入數(shù)據(jù)視為向量D=(D1，D2，…, Dn）, 編碼后數(shù)據(jù)視為向量（D1, D2,…, Dn, C1, C2,…, Cm)，RS編碼可視為如下圖所示矩陣運算。

圖2 編碼數(shù)據(jù)

圖2最左邊是編碼矩陣（或稱為生成矩陣、分布矩陣，Distribution Matrix），編碼矩陣需要滿足任意n*n子矩陣可逆。

為方便數(shù)據(jù)存儲，編碼矩陣上部是單位陣（n行n列），下部是m行n列矩陣。下部矩陣可以選擇范德蒙德矩陣或柯西矩陣。

解碼原理

RS最多能容忍m個數(shù)據(jù)塊被刪除。數(shù)據(jù)恢復(fù)的過程如下：

(1)假設(shè)D1、D4、C2丟失，從編碼矩陣中刪掉丟失的數(shù)據(jù)塊/編碼塊對應(yīng)的行。

圖3 丟失m塊

根據(jù)圖2所示RS編碼運算等式，可以得到如下B’ 以及等式。

圖4 vandermode矩陣

(2)求出B’的逆矩陣。

圖5 B’逆矩陣

(3)由于B’ 是可逆的，記B’的逆矩陣為 (B’^-1)，則B’ * (B’^-1) = I 單位矩陣。兩邊左乘B’ 逆矩陣。

圖6 兩邊乘上B’逆矩陣

(4)得到如下原始數(shù)據(jù)D的計算公式

圖7 單位矩陣

即恢復(fù)原始數(shù)據(jù)D：

圖8 解碼完成

(5)對D重新編碼，可得到丟失的數(shù)據(jù)

以典型的讀寫過程來描述糾刪碼在ceph中的實現(xiàn)。假設(shè)使用RS(10,3)的方式，客戶端要寫入一個對象：副本池（3副本為例）：OSD會將數(shù)據(jù)復(fù)制3份分別存放到3塊不同的磁盤上（OSD1,OSD2,OSD3）糾刪池(RS(10,3)為例)將原始數(shù)據(jù)按照順序切分為若干相同大小的塊，示例切分為10塊；將對象基于糾刪碼算法進行編碼，得到編碼塊數(shù)據(jù)，示例得到3塊大小相同的數(shù)據(jù)；將編碼后的數(shù)據(jù)塊及編碼塊分別存放到13塊不同的磁盤上（OSD1-OSD13）。

客戶端要讀取一個對象：副本池，由于3副本存放的數(shù)據(jù)均相同，客戶端直接從主OSD讀取后返回。

糾刪池

如果數(shù)據(jù)塊未丟失，那么需要從存放了多個數(shù)據(jù)塊的不同磁盤上讀取并按照順序拼接，如果讀的過程中檢測到數(shù)據(jù)塊丟失，那么除了需要從那些幸存的OSD上讀取數(shù)據(jù)之外，還需要通過糾刪碼算法解碼還原，最后按照順序拼接后返回給客戶端。

糾刪碼在AWCloud中的應(yīng)用

在Ceph中糾刪碼相對于多副本而言，讀取數(shù)據(jù)需要同時訪問更多的磁盤，由算法本身帶來的額外網(wǎng)絡(luò)消耗，以及磁盤故障時額外CPU消耗，導(dǎo)致糾刪碼性能比多副本要差，因此僅適合于存儲大量對時延不敏感的冷數(shù)據(jù)（如備份數(shù)據(jù)）。

AWCloud利用FPGA高效的計算能力，將原本使用CPU計算的糾刪碼算法offload到FPGA硬件上，通過PCI-e方式完成數(shù)據(jù)在CPU和FPGA硬件之間的交換，最終達(dá)到降低CPU消耗的方式來提升集群性能，尋求成本與性能之間的平衡。

fqj