亚洲日本免费-啊轻点灬太粗太长了三男一女-麻豆av电影在线观看-日韩一级片毛片|www.grbbt.com

在傳統(tǒng)存儲領(lǐng)域，隨著磁盤容量的不斷增大，RAID數(shù)據(jù)重構(gòu)時間將會是一個非常嚴重的問題。大家知道，過長的數(shù)據(jù)重構(gòu)時間意味著數(shù)據(jù)可靠性下降。所以，在RAID設(shè)計的過程中，一定要考慮數(shù)據(jù)重構(gòu)的時間，并且盡可能的將“無數(shù)據(jù)保護狀態(tài)”的時間降到最小。在不改變傳統(tǒng)RAID架構(gòu)前提下，只能通過增加數(shù)據(jù)冗余度來緩解大容量磁盤引入的超長數(shù)據(jù)重構(gòu)時間的問題。這種思路就好比幾年前，當(dāng)RAID5無法滿足過長數(shù)據(jù)重構(gòu)時間時，只能被迫采用RAID6算法，通過RAID6能夠提供兩塊盤的冗余度來緩解長時間數(shù)據(jù)重構(gòu)的問題。隨著時間的推移，目前，在很多應(yīng)用中，RAID6也無法滿足應(yīng)用需求了。為了達到更高的數(shù)據(jù)冗余度，一個比較不錯的選擇是采用冗余度更大的編解碼方式：Erasure Code。很多公司將基于這種編碼方式的RAID稱之為RAID7。

在互聯(lián)網(wǎng)領(lǐng)域，通常采用Server SAN的存儲架構(gòu)方式。也就是將廉價的Server通過集群軟件的方式組建一套分布式的存儲系統(tǒng)。Google首先倡導(dǎo)了這種方式，架構(gòu)了GFS系統(tǒng)，將很多非格式化的數(shù)據(jù)（例如網(wǎng)頁）存儲到這種分布式系統(tǒng)中。通常，這種廉價的Server是不具備RAID功能的，那么數(shù)據(jù)可靠性如何保證呢？在這種Server SAN中，通常會將數(shù)據(jù)復(fù)制多份存儲到不同的節(jié)點上，一旦一個節(jié)點失效，數(shù)據(jù)可以從其它節(jié)點上獲取。數(shù)據(jù)多節(jié)點復(fù)制的方式可以很好的提高數(shù)據(jù)可靠性，并且可以將讀寫數(shù)據(jù)流很好的分離。但是，帶來的問題是存儲利用率大為降低。對于一般的數(shù)據(jù)，通常會存儲三份，對于非常重要的數(shù)據(jù)，會存儲六份。如何平衡存儲空間和數(shù)據(jù)可靠性成了分布式存儲需要考慮的重要問題。Erasure Code可以平衡這兩者關(guān)系，在提高存儲空間利用率的前提下，不會影響數(shù)據(jù)可靠性。采用Erasure Code對數(shù)據(jù)進行編碼冗余的方式和“網(wǎng)絡(luò)RAID（RAIN）”的概念是很相像的。當(dāng)互聯(lián)網(wǎng)領(lǐng)域引入Erasure Code之后，需要考慮的問題是如何降低編解碼的運算復(fù)雜度問題。

事實已經(jīng)證明，Erasure Code作為一種數(shù)據(jù)編解碼技術(shù)在大數(shù)據(jù)環(huán)境下有了十分迫切的需求。不僅傳統(tǒng)的RAID需要這種技術(shù)，而且分布式存儲也需要這種技術(shù)去提升存儲資源利用率。

常用的Erasure code是基于范德蒙（Vandermonde）矩陣的RS算法。其基本思想很簡單，采用范德蒙矩陣作為生成矩陣，得到校驗數(shù)據(jù)。現(xiàn)假設(shè)輸入數(shù)據(jù)為D1~Dn，生成的校驗數(shù)據(jù)為C1~Cm，那么輸入數(shù)據(jù)和校驗數(shù)據(jù)之間的關(guān)系可以描述為：

其中，

為范德蒙矩陣，該矩陣為編碼矩陣。所以，為了得到校驗數(shù)據(jù)，主要的任務(wù)是將輸入數(shù)據(jù)和編碼矩陣相乘，得到的輸出結(jié)果就是編碼值。為了能夠更好的表示磁盤上存儲的數(shù)據(jù)，通常將編碼矩陣方程表示如下：

可以發(fā)現(xiàn)這個生成矩陣（A）就是單元矩陣和范德蒙矩陣的組合。輸入數(shù)據(jù)（D）和生成矩陣（A）的乘積就是編碼之后的存儲數(shù)據(jù)（E）。采用傳統(tǒng)RAID的思路去理解，編碼之后的結(jié)果就是一個條帶需要存儲的所有數(shù)據(jù)。

編碼過程我們已經(jīng)很清楚了，生成矩陣的格式很規(guī)整。那么，問題是如何進行解碼操作呢？當(dāng)存儲的數(shù)據(jù)d1~dn，c1~cm中有些數(shù)據(jù)無法讀取時，如何進行數(shù)據(jù)恢復(fù)呢？從數(shù)學(xué)的原理來看，只要將讀取的有效數(shù)據(jù)和生成矩陣的逆矩陣相乘就可以恢復(fù)丟失的數(shù)據(jù)。假設(shè)m個數(shù)據(jù)塊丟失，則可以將m個數(shù)據(jù)塊對應(yīng)的矩陣A和E中的行刪掉，得到新的n*n階生成矩陣A2和1*n階結(jié)果矩陣E2。由于生成矩陣是有范德蒙矩陣和單元矩陣的組合，所以，矩陣A的任意n行子集都可以保證線性無關(guān)。因此，需要恢復(fù)的數(shù)據(jù)可以通過A2和E2 的逆矩陣乘積得到，即D=逆（A2）*逆（E2）。

從數(shù)學(xué)的角度來看，我們現(xiàn)在常用的RAID5和RAID6算法只是范德蒙矩陣算法的一個子集而已。當(dāng)冗余數(shù)據(jù)只有一個的時候，就退化成了RAID5算法，在實數(shù)域只需要將輸入數(shù)據(jù)累加就可以得到校驗碼了。為了簡化計算復(fù)雜度，編解碼運算放到了迦羅話域，加法運算變成了XOR邏輯運算。當(dāng)冗余數(shù)據(jù)有兩個的時候，范德蒙矩陣退化成了RAID6算法，也可以在迦羅華域通過查表、XOR的方法完成運算。具體可以參考文章《一個IO的傳奇一生（12）– 磁盤陣列1》。

從這個角度來看，基于范德蒙矩陣的Erasure Code方法是傳統(tǒng)RAID5/RAID6算法的擴展。在實現(xiàn)過程中，同樣可以在迦羅華域中完成乘、除和加減法運算。為了實現(xiàn)快速算法，需要構(gòu)建兩張對數(shù)表和反對數(shù)表，然后通過查表和XOR運算快速實現(xiàn)編解碼。

基于范德蒙矩陣的Erasure Code編解碼原理比較簡單，可以說是在RAID5/RAID6算法基礎(chǔ)上的一種延伸。采用這種方法的算法復(fù)雜度還是比較高的，編碼復(fù)雜度為O（mn），其中m為校驗數(shù)據(jù)個數(shù)，n為輸入數(shù)據(jù)個數(shù)。解碼復(fù)雜度為O（n^3），解碼具有較高的計算復(fù)雜度。