基于范德蒙矩陣的Erasure code技術詳解
責編：admin ｜2015-02-04 14:35:59在傳統存儲領域，隨著磁盤容量的不斷增大，RAID數據重構時間將會是一個非常嚴重的問題。大家知道，過長的數據重構時間意味著數據可靠性下降。所以，在RAID設計的過程中，一定要考慮數據重構的時間，并且盡可能的將“無數據保護狀態”的時間降到最小。在不改變傳統RAID架構前提下，只能通過增加數據冗余度來緩解大容量磁盤引入的超長數據重構時間的問題。這種思路就好比幾年前，當RAID5無法滿足過長數據重構時間時，只能被迫采用RAID6算法，通過RAID6能夠提供兩塊盤的冗余度來緩解長時間數據重構的問題。隨著時間的推移，目前，在很多應用中，RAID6也無法滿足應用需求了。為了達到更高的數據冗余度，一個比較不錯的選擇是采用冗余度更大的編解碼方式：Erasure Code。很多公司將基于這種編碼方式的RAID稱之為RAID7。
在互聯網領域，通常采用Server SAN的存儲架構方式。也就是將廉價的Server通過集群軟件的方式組建一套分布式的存儲系統。Google首先倡導了這種方式，架構了GFS系統，將很多非格式化的數據（例如網頁）存儲到這種分布式系統中。通常，這種廉價的Server是不具備RAID功能的，那么數據可靠性如何保證呢？在這種Server SAN中，通常會將數據復制多份存儲到不同的節點上，一旦一個節點失效，數據可以從其它節點上獲取。數據多節點復制的方式可以很好的提高數據可靠性，并且可以將讀寫數據流很好的分離。但是，帶來的問題是存儲利用率大為降低。對于一般的數據，通常會存儲三份，對于非常重要的數據，會存儲六份。如何平衡存儲空間和數據可靠性成了分布式存儲需要考慮的重要問題。Erasure Code可以平衡這兩者關系，在提高存儲空間利用率的前提下，不會影響數據可靠性。采用Erasure Code對數據進行編碼冗余的方式和“網絡RAID（RAIN）”的概念是很相像的。當互聯網領域引入Erasure Code之后，需要考慮的問題是如何降低編解碼的運算復雜度問題。
事實已經證明，Erasure Code作為一種數據編解碼技術在大數據環境下有了十分迫切的需求。不僅傳統的RAID需要這種技術，而且分布式存儲也需要這種技術去提升存儲資源利用率。
常用的Erasure code是基于范德蒙（Vandermonde）矩陣的RS算法。其基本思想很簡單，采用范德蒙矩陣作為生成矩陣，得到校驗數據。現假設輸入數據為D1~Dn，生成的校驗數據為C1~Cm，那么輸入數據和校驗數據之間的關系可以描述為：
其中，
為范德蒙矩陣，該矩陣為編碼矩陣。所以，為了得到校驗數據，主要的任務是將輸入數據和編碼矩陣相乘，得到的輸出結果就是編碼值。為了能夠更好的表示磁盤上存儲的數據，通常將編碼矩陣方程表示如下：
可以發現這個生成矩陣（A）就是單元矩陣和范德蒙矩陣的組合。輸入數據（D）和生成矩陣（A）的乘積就是編碼之后的存儲數據（E）。采用傳統RAID的思路去理解，編碼之后的結果就是一個條帶需要存儲的所有數據。
編碼過程我們已經很清楚了，生成矩陣的格式很規整。那么，問題是如何進行解碼操作呢？當存儲的數據d1~dn，c1~cm中有些數據無法讀取時，如何進行數據恢復呢？從數學的原理來看，只要將讀取的有效數據和生成矩陣的逆矩陣相乘就可以恢復丟失的數據。假設m個數據塊丟失，則可以將m個數據塊對應的矩陣A和E中的行刪掉，得到新的n*n階生成矩陣A2和1*n階結果矩陣E2。由于生成矩陣是有范德蒙矩陣和單元矩陣的組合，所以，矩陣A的任意n行子集都可以保證線性無關。因此，需要恢復的數據可以通過A2和E2 的逆矩陣乘積得到，即D=逆（A2）*逆（E2）。
從數學的角度來看，我們現在常用的RAID5和RAID6算法只是范德蒙矩陣算法的一個子集而已。當冗余數據只有一個的時候，就退化成了RAID5算法，在實數域只需要將輸入數據累加就可以得到校驗碼了。為了簡化計算復雜度，編解碼運算放到了迦羅話域，加法運算變成了XOR邏輯運算。當冗余數據有兩個的時候，范德蒙矩陣退化成了RAID6算法，也可以在迦羅華域通過查表、XOR的方法完成運算。具體可以參考文章《一個IO的傳奇一生（12）– 磁盤陣列1》。
從這個角度來看，基于范德蒙矩陣的Erasure Code方法是傳統RAID5/RAID6算法的擴展。在實現過程中，同樣可以在迦羅華域中完成乘、除和加減法運算。為了實現快速算法，需要構建兩張對數表和反對數表，然后通過查表和XOR運算快速實現編解碼。
基于范德蒙矩陣的Erasure Code編解碼原理比較簡單，可以說是在RAID5/RAID6算法基礎上的一種延伸。采用這種方法的算法復雜度還是比較高的，編碼復雜度為O（mn），其中m為校驗數據個數，n為輸入數據個數。解碼復雜度為O（n^3），解碼具有較高的計算復雜度。
下一篇：H3C交換機常用配置命令