特許ウォッチ

公開番号2025179595
公報種別公開特許公報(A)
公開日2025-12-10
出願番号2024086447
出願日2024-05-28
発明の名称データ復元システム
出願人個人
代理人個人
主分類G06F 11/16 20060101AFI20251203BHJP(計算;計数)
要約【課題】冗長データユニットを大量に作ることができ、その結果、元データを大量に復元できるようにすることで、記憶装置に生じた障害からの復旧を、高い確率で実現することができるデータ復元システムの提供。
【解決手段】元データから複数の元データユニットと複数の冗長データユニットの作成を行うと共に、障害を逃れた必要最小限の冗長データユニットを抽出し、抽出された冗長データユニットから、元データユニット及び冗長データユニットの復元を32ビットガロア体の行列を用いた計算をもって効率よく行う。
【選択図】図1

特許請求の範囲【請求項１】
Ｍ個（Ｍは２以上の自然数）の元データユニットＤ[０]～Ｄ[Ｍ－１]を復元するためのＲ個（Ｒは２以上の自然数）の冗長データユニットＱ[０]～Ｑ[Ｒ－１]を作成する冗長ユニット作成手段と、
前記元データユニットのうちのＬ（自然数）個が破損した時に破損していないＲ－Ｋ（自然数）個の冗長データユニットから破損したＬ個の元データユニットを復元する元ユニット復元手段とを備えるデータ復元システムにおいて、
前記冗長ユニット作成手段は、Ｍ個の元データユニットＤ[０]～Ｄ[Ｍ－１]から、数式（３）の演算処理を経てＲ個の冗長データユニットＱ[０]～Ｑ[Ｒ－１]を作成し、
前記元ユニット復元手段は、Ｌ≦Ｒ－Ｋの時に、元データユニットの復元に使用する破損していない冗長データユニットをＬ個抽出すると共に、抽出されたＬ個の冗長データユニットＱ[ａ[０]]，…，Ｑ[ａ[Ｌ－１]]と破損していないＭ－Ｌ個の元データユニットＤ[ｙ[０]]，…，Ｄ[ｙ[Ｍ－Ｌ－１]]から数式（４）の演算処理を経て元データユニットを復元することを特徴とするデータ復元システム。
TIFF
2025179595000078.tif
26
128
TIFF
2025179595000079.tif
96
159
続きを表示（約 4,500 文字）【請求項２】
元ユニット復元手段で元データユニットを復元した後に、復元された元データユニットを含むすべての元データユニット[０]，…，Ｄ[Ｍ－１]から破損した冗長データユニットＱ[ｂ[０]]，…，Ｑ[ｂ[Ｋ－１]]を数式（５）の演算処理を経て復元する冗長ユニット復元手段を備えることを特徴とする請求項１に記載のデータ復元システム。
TIFF
2025179595000080.tif
39
126
【請求項３】
前記演算処理において、Z/2Z係数の３２次多項式（数式（６））についてｆ
32
(x)=0の解をαとして、数式（７）となるαで生成された３２ビットガロア体の任意の要素ａ（数式（８））と要素ｂ（数式（９））との乗算処理を行い積ａｂ＝ｃを導く乗算手段を備え、
TIFF
2025179595000081.tif
6
123
TIFF
2025179595000082.tif
6
115
TIFF
2025179595000083.tif
7
132
TIFF
2025179595000084.tif
6
132
前記乗算手段は、
前記要素ａ及び要素ｂのαを変数ｘに置換したＡ（ｘ）（数式（１０））とＢ（ｘ）（数式（１１））との積である６２次多項式Ｃ（ｘ）（数式（１２））を得る演算手段と、
TIFF
2025179595000085.tif
6
115
TIFF
2025179595000086.tif
7
115
TIFF
2025179595000087.tif
7
123
前記Ｃ（ｘ）（数式（１２））のｘにαを代入して得たＣ（α）におけるαの累乗部分につき、α
k
の指数が32≦kの時に数式（１３）を利用して、多項式を３１次多項式に帰着させる係数e(k,j) (0≦k≦62,0≦j≦31)を用いた３１次多項式（数式（１４））に書き換える次数変換手段と、
TIFF
2025179595000088.tif
6
115
TIFF
2025179595000089.tif
7
132
前記乗算処理に用いられるα
k
の係数（e(k,31) e(k,30) …e(k,1) e(k,0)）を成分とする行列の値を保持するデータテーブルと、
前記演算手段から出力された積を前記Ｃ（ｘ）の各項の係数（c
62
… c
32
c
31
… c
1
c
0
）と前記データテーブルに保持された行列との成分同士の積の形で出力する整形手段とを備えることを特徴とする請求項１又は請求項２のいずれかに記載のデータ復元システム。
【請求項４】
前記演算処理において、Z/2Z係数の３２次多項式（数式（６））についてｆ
32
(x)=0の解をαとして、数式（７）となるαで生成された３２ビットガロア体の任意の要素ａ（数式（８））についてａ
ｎ
(0≦n≦2
32
-1)を導く累乗手段を備え、
TIFF
2025179595000090.tif
6
123
TIFF
2025179595000091.tif
6
115
TIFF
2025179595000092.tif
6
132
前記累乗手段は、
累乗対象ａの累乗回数ｎを、数式（３５）の形とする分解手段と、
TIFF
2025179595000093.tif
6
154
前記分解手段で得られた結果に基づき、前記累乗回数ｎの二進表記の係数ｎ
j
(0≦j≦31)のうちｎ
j
が「１」であるｊについて、数式（１５）の各項で、数式（１４）のα
31
からα
0
の係数に、k=31＊2
j
, k=30＊2
j
, …,k=1＊2
j
,k=0＊2
j
を当て嵌めたe(31＊2
j
,31)…e(31＊2
j
,0)…e(0＊2
j
,31)…e(0＊2
j
,0)を成分とする行列P
j
(0≦j≦31)の値を保持するデータテーブルと、
TIFF
2025179595000094.tif
7
157
TIFF
2025179595000095.tif
7
128
前記累乗回数ｎの二進表記の係数ｎ
j
(0≦j≦31)のうちｎ
j
が「１」であるすべてのａ^2
j
を累乗対象ａ（数式（１６））の各項の係数（a
31
…a
1
a
0
）と前記データテーブルに保持された値を成分とする行列P
j
との積（a
31
…a
1
a
0
）P
j
の形で出力する整形手段と、
TIFF
2025179595000096.tif
7
115
前記整形手段から出力されたすべてのａ^2
j
を掛け合わせて出力する乗算手段とを備えることを特徴とする請求項１又は請求項２のいずれかに記載のデータ復元システム。
【請求項５】
前記演算処理において、Z/2Z係数の３２次多項式（数式（６））についてｆ
32
(x)=0の解をαとして、数式（７）となるαで生成された３２ビットガロア体の任意の要素ａ（数式（８））と要素ｂ（数式（９））との乗算処理を行い積ａｂ＝ｃを導く乗算手段と、
前記演算処理において、Z/2Z係数の３２次多項式（数式（６））についてｆ
32
(x)=0の解をαとして、数式（７）となるαで生成された３２ビットガロア体の任意の要素ａ（数式（８））についてａ
ｎ
(0≦n≦2
32
-1)を導く累乗手段とを備え、
TIFF
2025179595000097.tif
6
123
TIFF
2025179595000098.tif
6
115
TIFF
2025179595000099.tif
7
132
TIFF
2025179595000100.tif
6
132
前記乗算手段は、
前記要素ａ及び要素ｂのαを変数ｘに置換したＡ（ｘ）（数式（１０））とＢ（ｘ）（数式（１１））との積である６２次多項式Ｃ（ｘ）（数式（１２））を得る演算手段と、
TIFF
2025179595000101.tif
6
115
TIFF
2025179595000102.tif
7
115
TIFF
2025179595000103.tif
7
123
前記Ｃ（ｘ）（数式（１２））のｘにαを代入して得たＣ（α）におけるαの累乗部分につき、α
k
の指数が32≦kの時に数式（１３）を利用して、多項式を３１次多項式に帰着させる係数e(k,j) (0≦k≦62,0≦j≦31)を用いた３１次多項式（数式（１４））に書き換える次数変換手段と、
TIFF
2025179595000104.tif
6
115
TIFF
2025179595000105.tif
7
132
前記乗算処理に用いられるα
k
の係数（e(k,31) e(k,30) …e(k,1) e(k,0)）を成分とする行列の値を保持するデータテーブルと、
前記演算手段から出力された積を前記Ｃ（ｘ）の各項の係数（c
62
… c
32
c
31
… c
1
c
0
）と前記データテーブルに保持された行列との成分同士の積の形で出力する整形手段とを備え、
前記累乗手段は、
累乗対象ａの累乗回数ｎを、数式（３５）の形とする分解手段と、
TIFF
2025179595000106.tif
6
154
前記分解手段で得られた結果に基づき、前記累乗回数ｎの二進表記の係数ｎ
j
(0≦j≦31)のうちｎ
j
が「１」であるｊについて、数式（１５）の各項で、数式（１４）のα
31
からα
0
の係数に、k=31＊2
j
, k=30＊2
j
, …,k=1＊2
j
,k=0＊2
j
を当て嵌めたe(31＊2
j
,31)…e(31＊2
j
,0)…e(0＊2
j
,31)…e(0＊2
j
,0)を成分とする行列P
j
(0≦j≦31)の値を保持するデータテーブルと、
TIFF
2025179595000107.tif
7
157
TIFF
2025179595000108.tif
6
132
前記累乗回数ｎの二進表記の係数ｎ
j
(0≦j≦31)のうちｎ
j
が「１」であるすべてのａ^2
j
を累乗対象ａ（数式（１６））の各項の係数（a
31
…a
1
a
0
）と前記データテーブルに保持された値を成分とする行列P
j
との積（a
31
…a
1
a
0

発明の詳細な説明【技術分野】
【０００１】
本発明は、本来在るべきデータ（以下、「元データ」と記す。）と、当該元データを修復する目的を帯びた冗長データを作成して記憶するように構成されたデータ復元システムに関する。
続きを表示（約 1,400 文字）【背景技術】
【０００２】
ＨＤＤ（Hard Disk Drive）などの物理ドライブを用いた記録再生装置は、モーターの劣化やディスクの劣化等に伴うＨＤＤの障害、バッテリー切れや意図しないデータの削除又は改変などに伴うノートパソコンの障害、停電や天変地異などに伴うストレージ装置のダウン、更には、無線通信障害によって、ＨＤＤに書き込まれているデータが損傷することが知られている。
【０００３】
その様な実態の下、物理ドライブを用いた記録再生装置の信頼性の向上、復旧性の向上及び高速化を実現する技術として、各種のデータを複数のディスクに分散し保存する冗長ディスクアレイ（ＲＡＩＤ：Redundant Arrays of Independent (Inexpensive) Disks：）が知られている。
【０００４】
ＲＡＩＤは、データディスクの他に、冗長性をもたせるためのパリティディスクを備え、データディスクに障害が発生した際には、当該障害による消失データを冗長性を持ったデータを用いて復元する。
【０００５】
データディスクに障害が生じた際には、当該障害による消失データをユニット単位の排他的論理和で復元する（下記特許文献１参照。）。
データーの復元は、例えば、以下のように元データＤを複数（ｎ個）の部分データに分割し、ガロア体と呼ばれる有限体からｋ個の線形独立なベクトルα
11
，α
21
，α
31
，……α
n1
を選択し、数式（１）を用いて、パリティーデータを作成する。
尚、元データＤ＝｛Ｄ
1
，Ｄ
2
，Ｄ
3
，…，Ｄ
n
｝、
送信データＤ′＝｛Ｃ
1
，Ｃ
2
，Ｃ
3
，…，Ｃ
m
｝、
パリティデータＣｋ＝α
11
・Ｄ
1
＋α
21
・Ｄ
2
＋…＋α
n1
・Ｄ
n
である。
【０００６】
元データＤを復元する際にはｎ個の部分データが取得できていれば、対応するｎ個のベクトルからｎ×ｎの行列Ａ＝（α
ij
），１≦ｉ≦ｎ，１≦ｊ≦ｎを構成し、取得した部分データにＡの逆行列をかければ元データが取得できる。つまり、数式（２）を用いて、元データを復元する。
【０００７】
TIFF
2025179595000002.tif
24
136
【０００８】
TIFF
2025179595000003.tif
23
136
【先行技術文献】
【特許文献】
【０００９】
特開２００８－１７２６１７号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、例えば、従来のＲＡＩＤ６では、パリティディスクが２個に固定されているため、元データディスクが３個以上破損すると、パリティディスクが全く破損しなかったとしても元データディスクの復元ができなくなる。
（【００１１】以降は省略されています）

関連特許