[發明專利]用于對存儲數據進行編碼的方法以及裝置

有效

• 申請號: 201580084349.0
• 申請日: 2015-11-10
• 公開（公告）號: CN108352845B
• 公開（公告）日: 2021-02-23
• 發明（設計）人: 彼得·弗拉基米羅維奇·特里夫諾夫;王元鋼;楊思曉
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H03M13/37
• 分類號: H03M13/37
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 熊永強;李稷芳

本發明提供用于對n個存儲設備中的存儲數據進行編碼的方法，使得所述數據在多達r個存儲設備的一次故障以及多達s次塊故障之后是可恢復的，其中所述方法涉及對數據進行外編碼以及內編碼以獲得編碼后數據。本發明亦提供用于從部分擦除的編碼后數據恢復數據的方法。

技術領域

本發明涉及用于對n個存儲設備中的存儲數據進行編碼的方法以及裝置，使得數據在多達r個存儲設備的一次故障以及多達s次塊故障之后是可恢復的。本發明亦涉及用于恢復部分擦除的編碼后數據的裝置。

本發明亦涉及存儲程序代碼的計算機可讀存儲介質，程序代碼包括用于執行用于對數據進行編碼的或用于恢復部分擦除的編碼后數據的方法的指令。

背景技術

考慮包括n個存儲設備(例如磁盤，NVRAM芯片，等等)的存儲系統。此等設備中的任一個可能完全或部分出現故障，亦即，存儲設備的一些數據塊(磁盤扇區，內存頁，等等)可能變得永不可用。擦除編碼技術一般用于保護數據免受這樣的故障。被稱為獨立磁盤冗余陣列(redundant array of independent disks，RAID)的架構通過分配用于存儲奇偶校驗數據的r個存儲設備來解決此問題，使得至多可以恢復r個設備中的任意故障。然而，塊故障比設備故障更為頻繁地多，并且，倘若使用邏輯塊至物理塊的適當映射，相同分條中的許多塊同時出現故障的可能性極小。因此，這些方案的冗余似乎過高。

通過運用部分MDS以及扇區-磁盤(sector-disk，SD)陣列碼可以解決設備故障以及塊故障存在時的數據保護的問題。它們的碼字表示為ν×n個陣列。一個陣列中的每一列對應一個存儲設備，以及一列中的各行對應不同塊。部分MDS碼定義為GF(q)上的(νn，ν(n-r)-s)碼，其能夠校正對應一個碼字的一個陣列的每一行i_j中的多達s_j+r次擦除，條件是0≤i₁i₂...i_t≤ν-1，并且扇區-磁盤(sector-disk，SD)碼是(νn，ν(n-r)-s)碼，其能夠校正多達r次列擦除，以及多達s次塊擦除的另外任一配置。對于r≤3以及s≤3，使用計算機搜索獲得SD碼，盡管對于r＝s＝3，由于復雜性限制，僅驗證部分SD屬性。對于r＝1，s≥1以及r≥1，s＝1的，給出部分MDS碼的構造。提議給出對于r≥1，s＝2的情況下的SD碼的明確構造。此等構造皆要求νnq。給出類SD碼的簡化構造，其要求max(ν，n)q并且可以恢復1次磁盤故障以及多達2次塊故障的一些組合。提議了此方法的替代選擇，其中二維編碼方案是基于MDS碼。然而，此等方法都沒有提議用于通過對應碼對數據進行編碼的快速算法。

一些現有技術公開案沒有提供有效編碼以及擦除恢復算法，并且對可實現的碼參數施加了嚴格限制。

發明內容

本發明的目的在于提供用于對存儲設備中的存儲數據進行編碼的裝置以及方法，其中所述裝置以及所述方法克服現有技術的上述的問題中的一個或多個問題。特定言之，本發明的目的可以包括提供用于遭受設備故障以及塊故障的存儲系統在計算上有效的擦除編碼技術。

本發明的第一方面提供用于對n個存儲設備中的存儲數據進行編碼的方法，使得所述數據在多達r個存儲設備的一次故障以及多達s次塊故障之后是可恢復的，其中所述方法包括步驟：

用一個或多個外碼對所述數據進行外編碼以獲得外編碼后數據，其中所述外碼為GF(2^m)上的C_i(ν，K_i，ν-K_i+1)碼，ν≤2^m，其中0≤i＜n，

其中

并且(ν-K_j+1)(j-r)＞s；以及

用一個或多個內碼對所述外編碼后數據進行編碼以獲得編碼后數據，其中所述內碼為GF(2^m)上的嵌套碼。