[發明專利]一種面向糾刪碼的數據放置方法

有效

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

技術領域

本發明涉及分布存儲系統的數據容錯技術，尤其是面向糾刪碼的數據放置方法。

背景技術

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

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

基于糾刪碼的容錯技術的基本思想是對k個原始數據塊進行編碼計算得到m個冗余數據塊；只需k+m個數據塊中的任意k個數據塊，就可通過解碼計算恢復得到原始的k個數據塊。

具體而言，每個冗余數據塊C_j(j＝1,2,…,m)都是k個原始數據塊Di(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)與數據塊Di(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)進行逐位相加，得到原始數據塊

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

盡管隨著技術的進步，各種軟硬件資源的可靠性得到了顯著提高，但是，隨著存儲資源規模的不斷擴大，資源的失效概率明顯上升。在大規模分布存儲系統中，資源失效是一種常態行為。在數據塊失效時，基于糾刪碼的容錯技術需要多個數據塊才能解碼恢復失效的原始數據塊，需要占用較多的網絡帶寬資源。

如何放置數據塊對分布存儲系統的數據訪問效率、數據可靠性和數據修復效率等系統性能都將產生重要影響。多存儲節點同時失效大多是由電源故障或網絡故障引起的，失效的多個存儲節點在拓撲上相距較近，如同一個機架中的存儲節點或連接于同一個交換機上的存儲節點。因此，數據放置越分散，數據的可靠性就會越高，但是，數據訪問效率就會越低，數據修復效率也會越低。但是，數據可靠性和數據訪問效率之間也不是完全矛盾的。如果數據訪問效率越高，那么，數據修復效率就會越高，在數據修復完成之前再次發生失效的概率就會越小，從而提高數據可靠性。