[發明專利]基于RS糾刪碼的數據存儲方法

無效

• 申請號: 201010171777.6
• 申請日: 2010-05-13
• 公開（公告）號: CN101840377A
• 公開（公告）日: 2010-09-22
• 發明（設計）人: 鄭燕飛;沈林峰;曹羽中;程正杰;陳克非
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F12/06
• 分類號: G06F12/06;G06F11/14;G11C29/42
• 代理公司: 上海交達專利事務所 31201
• 代理人: 王錫麟;王桂忠

1.一種基于RS糾刪碼的數據存儲方法，其特征在于，包括以下步驟：

第一步，對待存儲文件進行分塊處理，從而得到N個大小相同的原始數據塊，并對這些原始數據塊進行分組處理，得到M個數據組；

第二步，將每個數據組中的原始數據塊逐塊的從用戶端傳送到數據節點，當第i個數據組傳輸完畢后，接收到該數據組數據的數據節點將接收到的數據傳送給管理節點指定的一個數據節點，該數據節點得到該組數據塊的所有原始數據塊信息，1≤i≤M；

第三步，得到第i組數據塊的所有原始數據塊信息的數據節點對該數據組進行RS編碼，使第i個數據組從K_i個原始數據塊變為K_i個原始數據塊和R_i個冗余數據塊，K_i是編碼前第i個數據組中原始數據塊的數目；

第四步，將編碼后的同一數據組中的數據塊存儲的若干個機架上，且同一機架上中同一數據組的數據塊不超過R_i個；

第五步，當存儲文件中有數據塊損壞時，采用RS糾刪碼恢復數據塊，得到恢復后的數據塊。

2.根據權利要求1所述的基于RS糾刪碼的數據存儲方法，其特征是，第一步中所述的分塊處理，是：將待存儲文件按照固定大小T分為N個原始數據塊，當最后一塊原始數據塊小于T時，對最后一塊原始數據塊填充冗余，使其大小正好是T。

3.根據權利要求1所述的基于RS糾刪碼的數據存儲方法，其特征是，第一步中所述的分組處理，是：將K個原始數據塊作為一組，從而將N個原始數據塊分為M組，其中最后一個原始數據組的原始數據塊的個數小于或者等于K。

4.根據權利要求1所述的基于RS糾刪碼的數據存儲方法，其特征是，第三步中所述的RS編碼是依次對每個原始數據塊中w比特的數據按照下面的公式進行處理，得到對應該K_i個w比特原始數據的R_i個w比特的冗余數據，將第j冗余數據的所有w比特的冗余數據按順序進行組合得到第j冗余數據塊，1≤j≤R_i，具體公式是：

FD＝C，

其中：F是R_i×K_i的范得蒙德矩陣，D是第i個數據組中K_i個w比特原始數據組成的K_i×1的矩陣，C是編碼后第i個數據組中R_i個w比特的冗余數據組成的R_i×1的矩陣。

5.根據權利要求1所述的基于RS糾刪碼的數據存儲方法，其特征是，第五步中所述的恢復數據塊，是指：

1)當損壞的數據塊的數目小于或等于R_i時，通過下面的公式分別得到w比特的原始數據塊，進而組合得到損壞的原始數據塊或者是通過RS編碼得到損壞的冗余數據塊；

A′D＝E′，

其中：I是K_i×K_i的單位矩陣，F是R_i×K_i的范得蒙德矩陣，D是第i個數據組中K_i個w比特原始數據塊組成的K_i×1的矩陣，C是編碼后第i個數據組中R_i個w比特冗余數據塊組成的R_i×1的矩陣，A′是從A中去除損壞數據塊所對應的行后的新矩陣，E′是從E中去除損壞數據塊所對應的行后的新矩陣；

2)當損壞的數據塊的數目大于R_i時，損壞的數據塊無法恢復。