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

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

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

Reed-Solomon實現原理

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

圖1 糾刪碼基本原理圖

編碼原理

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

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

圖2 編碼數據

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

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

解碼原理

RS最多能容忍m個數據塊被刪除。數據恢復的過程如下：

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

圖3 丟失m塊

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

圖4 vandermode矩陣

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

圖5 B’逆矩陣

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

圖6 兩邊乘上B’逆矩陣

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

圖7 單位矩陣

即恢復原始數據D：

圖8 解碼完成

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

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

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

糾刪池

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

糾刪碼在AWCloud中的應用

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

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

fqj