網(wǎng)易視頻云技術(shù)分享：ReedSolomon糾刪碼

《網(wǎng)易視頻云技術(shù)分享：ReedSolomon糾刪碼》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、網(wǎng)易視頻云技術(shù)分享：ReedSolomon糾刪碼網(wǎng)易視頻云是網(wǎng)易傾力打造的-款基于云計算的分布式多媒體處理集群和專業(yè)音視頻技術(shù)，為客戶提供穩(wěn)定流暢、低時延、高并發(fā)的視頻直播、錄制、存儲、轉(zhuǎn)碼及點播等音視頻的PASS服務(wù)。在線教育、遠程醫(yī)療、娛樂秀場、在線金融等各行業(yè)及企業(yè)用戶只需經(jīng)過簡單的開發(fā)即可打造在線音視頻平臺。現(xiàn)在，網(wǎng)易視頻云轉(zhuǎn)載相關(guān)文章，與大家分享一下ReedSolomon糾刪碼。糾刪碼是存儲領(lǐng)域常川的數(shù)據(jù)冗余技術(shù)，相比多副本復(fù)制而言，糾刪碼能夠以更小的數(shù)據(jù)冗余度獲得更高數(shù)據(jù)可靠性。ReedSolomonCoding是存儲領(lǐng)域常用的一種糾刪碼，它的棊本原理如

2、卜「：給定n個數(shù)據(jù)塊d1,d2,...,dn,n和一個正整數(shù)m,RS根據(jù)n個數(shù)據(jù)塊生成m個校驗塊，c1,cnrio對于任意的n和m,從n個原始數(shù)據(jù)塊和m個校驗塊中任取n塊就能解碼出原始數(shù)據(jù)，即RS最多容忍m個數(shù)據(jù)塊或者校驗塊同時丟失（糾刪碼貝能容忍數(shù)據(jù)丟失，無法容忍數(shù)據(jù)篡改，糾刪碼正是得名與此）。編碼原理RS編碼以word為編碼和解碼單位，大的數(shù)據(jù)塊拆分到字長為w的word（字長w取值一般為8或者16位），然后對word進行編解碼。所以數(shù)據(jù)塊的編碼原理與word編碼原理沒什么差別，為論述方便，后文中變量Di,Ci將代表一個wordo首先，把輸入數(shù)據(jù)視為向量D=（D1

3、,D2,Dn）,編碼后數(shù)據(jù)視為向量（D1,D2,...,Dn,C1,C2,..,Cm）,RS編碼可視為如圖1所示矩陣運算。下圖最左邊是編碼矩陣，矩陣上部是單位陣（n行n列），下邊是Vandermonde矩陣B（m行n列），vandermode炬陣如圖2所示，第i行，第j列的氐數(shù)值為j^（i-1）oZ所以采用Vandermonde矩陣的原因是，RS數(shù)據(jù)恢復(fù)算法要求編碼矩陣任意n*n子矩陣可逆。?圖1：RS糾刪碼編碼運算數(shù)據(jù)恢復(fù)原理RS最多能容忍m個刪除錯謀。數(shù)據(jù)恢復(fù)原理的過程如下：（1）從編碼矩陣屮刪去丟失數(shù)據(jù)塊和丟失編碼塊對應(yīng)行。假設(shè)D1、C2丟失，根據(jù)圖1所示RS

4、編碼運算等式，我們得到如FB'以及等式。T[DI00000DI000000DB”BnB”B刖B理B対B,Bjs?'S—T—T—T—1016一巧瓦-9『一zivllrv=s圖2：vandermode矩陣（2）由于B，是可逆的，兩邊乘上B'逆矩陣。oR"Survivors（3）得到如下原始數(shù)據(jù)D的計算公式（4）對D重新編碼，得到丟失的校驗碼矩陣求逆采川高斯消元法，需要進行實數(shù)加減乘除四則運算，無法作川丁-字長為w的二進制數(shù)據(jù)。為了解決這個問題，RS采用伽羅華群GF（2八w）中定義的四則運算法則。GF（2^w）域有"w個值，毎個值都對應(yīng)一個低于w次的多項式，這樣域上的四則

5、運算就轉(zhuǎn)換為多項式空間的運算［2］。GF（2八w）域中的加法就是XOR,乘法比較特殊,需要維護兩個大小為2^w-1的表格：log表gflog,反log表gfilog。乘法公式：a*b=gfilog(gflog(a)+fglog(b))%(2八w-1)CRS(CauchyReedSolomon)RS糾刪碼的計算代價較高，瓶頸在于乘除法,乘除法操作需要3次查衣操作，一?次加(減)法操作，—次條件判斷，一次取模操作(可優(yōu)化為一次條件判斷和一次減法操作)。CRS從兩個方而優(yōu)化RS性能(1)使用Cauchy編碼矩陣，Cauchy編碼矩陣的好處是求逆矩陣比較快(2)將GF(2^

6、w)+的運算全部轉(zhuǎn)換為XOR,其中的數(shù)學(xué)原理比較復(fù)雜，可參見文獻[3]小結(jié)RS的特點：(1)低冗余度，高可靠性。(2)數(shù)據(jù)恢復(fù)代價禹。丟失數(shù)據(jù)塊或者編碼塊時，RS需耍讀取n個數(shù)據(jù)塊和校驗塊才能恢復(fù)數(shù)據(jù)，數(shù)據(jù)恢復(fù)效率也在一定程度上制約了RS的可靠性。(3)數(shù)據(jù)更新代價高。數(shù)據(jù)更新和當?丁?重新編碼，代價很高，因此常常針對只讀數(shù)據(jù)，或者冷數(shù)據(jù)。(4)RS編碼依賴于兩張2^w-1大小的log表，通常只能采用16位或者8位字長，不能充分利用64位服務(wù)器的計算能力，具體實現(xiàn)上可能耍做一些優(yōu)化。參考文獻：[1]JamesS.Plank.ErasureCodesForStorag

7、eApplication.[2]JamesS.Plank.ATutorialonReed-SolomonCodingforFault-ToleraneeinRAID-likeSystems[3]JamesS.Plank.OptimizingCauchyReed-SolomonCodesforFault-TolerantStorageApplications