[發明專利]由整數索引的泰納圖構建扁平異或碼的方法

在審

• 申請號: 201580053343.7
• 申請日: 2015-09-29
• 公開（公告）號: CN107077401A
• 公開（公告）日: 2017-08-18
• 發明（設計）人: 金超;席蔚亞;揚啟良;陳世斌
• 申請（專利權）人: 新加坡科技研究局
• 主分類號: G06F11/10
• 分類號: G06F11/10;H03M13/05
• 代理公司: 北京派特恩知識產權代理有限公司11270
• 代理人: 胡春光,張穎玲

優先權聲明

本申請要求2014年10月3日提交的新加坡專利申請No.10201406332W的優先權。

技術領域

本發明涉及數據存儲系統。具體地，本發明涉及一種用于數據存儲系統的糾刪碼。

背景技術

糾刪可以由(n，k)參數的元組表征。碼字包含總數為n個的符號/列，其中，任何k個符號/列都可以用于恢復其他n-k個符號/列(如果其他n-k個符號/列丟失的話)。長期以來，在存儲系統中一直使用糾刪碼(例如，復制、RAID-5和Reed-Solomon碼等)以容忍磁盤/節點故障。為了在磁盤發生故障時啟用數據恢復，Reed-Solomon碼需要存儲最少量的冗余數據，其中保留精確的m個磁盤冗余數據以容忍任意m個磁盤故障。具有此屬性的代碼稱為最大距離可分離(MDS)碼。另一方面，復制需要數量大得多的冗余數據，和原始數據一樣大或比原始數據大幾倍。然而，復制具有非常短的恢復方程，這意味著它在磁盤發生故障時具有更高的恢復效率。

扁平異或(XOR)碼是介于復制和MDS碼之間的代碼類型。扁平XOR碼僅基于XOR算法構建。它們具有一維代碼結構，并且每個奇偶校驗符號是數據符號子集的異或和。扁平XOR碼不是MDS，因此它們不如MDS碼那樣具有空間效率。然而，扁平XOR碼具有短得多的恢復方程，并且其恢復效率遠高于MDS碼。與復制相比，扁平XOR碼的空間效率要高得多，雖然它們的恢復效率不是很好。因此，扁平XOR碼可以提供存儲效率和恢復效率之間的彈性權衡，從而在選擇設計參數時為存儲系統提供了更大的靈活性。

作為非MDS碼的其他類型，有犧牲一些存儲效率以提高恢復效率的金字塔碼、WEAVER碼和HOVER碼。金字塔碼建立在多級MDS代碼上，并且恢復是像聲稱的金字塔那樣逐級完成的。WEAVER和HOVER碼是非系統奇偶校驗矩陣XOR碼，其中所有或部分數據列包含奇偶校驗符號。然而，這些糾刪碼在存儲效率和重建性能方面存在不足。

對于扁平XOR碼來說，構建扁平XOR碼的方法非常少，并且扁平XOR碼的數量非常有限。此外，現有的扁平XOR碼僅能容忍至多3個故障。

因此，需要一種用于數據存儲系統的更穩健的、優化存儲效率和恢復效率之間的平衡的糾刪碼。此外，結合附圖和本公開的背景技術，通過隨后的詳細描述和所附的權利要求，其他期望的特征和特性將變得顯而易見。

發明內容

根據本公開的第一方面，提供了一種定義用于具有預定數量的數據磁盤的系統的糾刪碼的方法，所述方法包括選擇步驟、構建步驟、確定步驟和重復步驟。所述選擇步驟包括：為所述系統選擇預定的可接受數量的故障。所述構建步驟包括：為具有所述預定數量的數據磁盤的可接受兩個故障的系統構建第一泰納(Tanner)圖。所述確定步驟包括：通過將可接受的故障數量增加1，以及響應于增加的可接受數量的故障通過增加奇偶校驗節點的數量而構建另一個泰納圖，來重復構建步驟和確定步驟，直到達到該系統的預定數量的故障。

根據本公開的第二方面，提供了一種非暫時性計算機可讀介質，其包含用于使計算機執行定義用于具有預定數量的數據磁盤的系統的糾刪碼的方法的程序指令。所述方法包括選擇步驟、構建步驟、確定步驟和重復步驟。所述選擇步驟包括：為所述系統選擇預定的可接受數量的故障。所述構建步驟包括：為具有所述預定數量的數據磁盤的可接受兩個故障的系統構建第一泰納圖。所述確定步驟包括：通過將可接受的故障數量增加1，以及響應于增加的可接受數量的故障通過增加奇偶校驗節點的數量而構建另一個泰納圖，來重復構建步驟和確定步驟，直到達到該系統的預定數量的故障。

根據本公開的第三方面，提供了一種系統，所述系統具有預定數量的數據磁盤和執行用于定義糾刪碼的方法的計算機。所述方法包括選擇步驟、構建步驟、確定步驟和重復步驟。所述選擇步驟包括：為所述系統選擇預定的可接受數量的故障。所述構建步驟包括：為具有所述預定數量的數據磁盤的可接受兩個故障的系統構建第一泰納圖。所述確定步驟包括：通過將可接受的故障數量增加1，以及響應于增加的可接受數量的故障通過增加奇偶校驗節點的數量而構建另一個泰納圖，來重復構建步驟和確定步驟，直到達到該系統的預定數量的故障。

附圖說明

在附圖中，相同的附圖標記在各個分離的附圖中表示相同或功能相似的元件，并且附圖與下面的詳細描述一起并入說明書并且形成其一部分，附圖用于示出各種實施方式并根據本實施方式解釋各種原理和優點。

圖1示出了根據本公開的INT2-2碼的泰納圖結構的示例。

圖2示出了根據本公開的INT3-2碼的泰納圖結構的示例。