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

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

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

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

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

圖1 糾刪碼基本原理圖

編碼原理

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

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

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

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

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

解碼原理

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

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

圖3 丟失m塊

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

圖4 vandermode矩陣

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

圖5 B’逆矩陣

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

圖6 兩邊乘上B’逆矩陣

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

圖7 單位矩陣

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

圖8 解碼完成

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

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

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

糾刪池

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

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

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

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

fqj