[發明專利]一種基于糾刪碼的文件追加方法

有效

• 申請號: 201410331144.5
• 申請日: 2014-07-13
• 公開（公告）號: CN104102558B
• 公開（公告）日: 2017-01-25
• 發明（設計）人: 王意潔;裴曉強;許方亮;符永銓;孫偉東;程力;李小勇;馬行空;王媛;趙越;林軒;熊澤宇
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F11/14
• 分類號: G06F11/14
• 代理公司: 國防科技大學專利服務中心43202
• 代理人: 郭敏

技術領域

本發明涉及分布存儲系統的數據容錯技術，尤其是基于糾刪碼的文件追加方法。

背景技術

數據容錯是海量數據分布存儲的關鍵技術之一，數據容錯對于提高系統的可用性和可靠性至關重要。目前，數據容錯技術主要包括基于復制的容錯技術和基于糾刪碼的容錯技術。

基于復制的容錯技術簡單直觀，易于實現和部署，需要為每個數據文件創建若干同樣大小的副本，存儲空間開銷較大。基于糾刪碼的容錯技術通過將數據文件分割為多個數據塊，通過利用糾刪碼算法對原始的數據塊進行編碼得到冗余的數據塊，把多個數據塊的信息融合到較少的冗余信息中，有效節省存儲空間。與基于復制的容錯技術相比，基于糾刪碼的容錯技術具有冗余度低、存儲空間利用率高等優點，已經逐步成為大數據時代數據容錯的主流技術。

在基于糾刪碼的容錯技術中，對數據的讀寫操作需要進行編解碼，產生一定的計算開銷。基于糾刪碼的容錯技術的基本思想是：(1)首先，將數據文件DO分割為K個原始數據塊，并按照每組k(k<K)個原始數據塊進行分組，若最后一組不足k個原始數據塊，則用全零數據塊補齊；(2)然后，對每組中的k個原始數據塊進行編碼計算得到m個冗余數據塊；(3)對于每組的k個原始數據塊及其m個冗余數據塊，只需這k+m個數據塊中的任意k個數據塊，就可通過解碼計算恢復得到原始的k個數據塊。

對于每組數據塊而言，每個冗余數據塊C_j(j＝1,2,…,m)都是k個原始數據塊D_i(i＝1,2,…,k)的線性組合，編碼計算可表示為公式(1)，其中，G_ji(j＝1,2,…,m，i＝1,2,…,k)是數據塊編碼系數。也就是說，對于冗余數據塊C_j(j＝1,2,…,m)而言，首先，編碼系數G_ji(i＝1,2,…,k)與數據塊D_i(i＝1,2,…,k)進行逐位相乘，得到k個新數據塊T_ji＝G_ji×D_i(i＝1,2,…,k)；然后，k個新數據塊T_ji(i＝1,2,…,k)進行逐位相加，得到冗余數據塊

G_j1×D₁+…+G_ji×D_i+…+G_jk×D_k＝C_j????????????????????(1)

每個原始數據塊D_i(i＝1,2,…,k)都是其它任意k個可用數據塊E_j(j＝1,2,…,k)(原始數據塊或者冗余數據塊)的線性組合，解碼計算可表示為公式(2)，其中，H_ij(i＝1,2,…,k，j＝1,2,…,k)是數據塊解碼系數。也就是說，對于原始數據塊D_i(i＝1,2,…,k)而言，首先，解碼系數H_ij(j＝1,2,…,k)與可用數據塊E_j(j＝1,2,…,k)進行逐位相乘，得到k個新數據塊S_ij＝H_ij×E_j(j＝1,2,…,k)；然后，k個新數據塊S_ij(j＝1,2,…,k)進行逐位相加，得到原始數據塊

Hi_1×E₁+…+H_ij×E_j+…+H_ik×E_k＝D_i????????????????????????????(2)

隨著海量數據規模的不斷增大，文件追加逐漸成為數據更新的主要方法之一。所謂文件追加是指不覆蓋數據文件中原來的數據塊，而是在數據文件末端追加新的數據塊。在基于糾刪碼的容錯技術中，現有的文件追加方法都是將追加后的文件作為新文件，將追加之前的老文件的冗余數據塊全部刪除，對整個新文件進行重新編碼。文件追加的編碼計算開銷和網絡傳輸開銷取決于文件的數據塊數目。隨著數據文件的不斷增大，文件的數據塊數目呈現出逐漸增長的趨勢，從而使得文件追加的編碼計算開銷和網絡傳輸開銷越來越大，對文件追加效率產生影響。

因此，如何針對文件追加的編碼計算開銷問題和網絡傳輸開銷問題，設計基于糾刪碼的文件追加方法，有效降低文件追加的編碼計算開銷和網絡傳輸開銷，有效保證文件追加效率，已經成為分布存儲領域的熱點研究問題。

發明內容