(57)【要約】  データを複数のデータサブセットに分割することを含む、データを保護する方法と装置。複数のデータサブセットの内の各データサブセットと他のデータサブセットとに対しパリティデータを生成する。複数のデータサブセットの内の各データサブセットとさらに他のデータサブセットとに対しパリティデータを生成する。データを復元する方法と装置であって、１つ又は複数のデータサブセットを取得することを含む。１つのデータサブセットに対して生成された複数の異なるパリティデータを取得する。取得された１つ又は複数のデータサブセットと取得された複数のパリティデータセットとを使用して失われたデータサブセットを再生成する。復元データを形成するように、取得された１つ又は複数のデータサブセットと再生成された失われたデータサブセットとを組み合わせる。
2014525188.tif 000002
【特許請求の範囲】
【請求項１】
データを保護する方法であって、
前記データを複数のデータサブセットに分割するステップと、
前記複数のデータサブセットの内の各データサブセットと他のデータサブセットとに対しパリティデータを生成するステップと、
前記複数のデータサブセットの内の前記各データサブセットとさらに他のデータサブセットとに対しパリティデータを生成するステップと、
を含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、前記複数のデータサブセットと前記生成されたパリティデータとを保存するステップをさらに含むことを特徴とする方法。
【請求項３】
請求項１に記載の方法であって、前記複数のデータサブセットと前記生成されたパリティデータとを送信するステップをさらに含むことを特徴とする方法。
【請求項４】
請求項１〜３のいずれかに記載の方法であって、少なくとも２つのパリティデータセットが前記各データサブセットに対して生成されることを特徴とする方法。
【請求項５】
請求項１〜４のいずれかに記載の方法であって、前記各データサブセットは、２つの隣接するデータサブセットに対して生成されたパリティデータを有することを特徴とする方法。
【請求項６】
請求項１〜５のいずれかに記載の方法であって、パリティデータが最初のデータサブセットと最後のデータサブセットとに対して生成されることを特徴とする方法。
【請求項７】
請求項１〜６のいずれかに記載の方法であって、前記パリティデータは排他的論理和（ＸＯＲ）論理演算子を使用して生成されることを特徴とする方法。
【請求項８】
請求項１〜７のいずれかに記載の方法であって、前記データは奇数のデータサブセットに分割されることを特徴とする方法。
【請求項９】
請求項１〜８のいずれかに記載の方法であって、前記データは所定数のデータサブセットに分割されることを特徴とする方法。
【請求項１０】
データを復元する方法であって、
データサブセットを取得するステップと、
請求項１〜９のいずれかに従って生成されたパリティデータを取得するステップと、
前記取得されたデータサブセットと前記取得されたパリティデータとを使用して失われたデータサブセットを再生成するステップと、
復元データを形成するように、前記取得されたデータサブセットと前記再生成された失われたデータサブセットとを組み合わせるステップと、
を含むことを特徴とする方法。
【請求項１１】
データを復元する方法であって、
１つ又は複数のデータサブセットを取得するステップと、
前記１つのデータサブセットに対して生成された複数の異なるパリティデータセットを取得するステップと、
前記取得された１つ又は複数のデータサブセットと、前記取得された複数のパリティデータセットを使用して失われたデータサブセットを再生成するステップと、
復元データを形成するように、前記取得された１つ又は複数のデータサブセットと前記再生成された失われたデータサブセットとを組み合わせるステップと、
を含むことを特徴とする方法。
【請求項１２】
データを保護する装置であって、
前記データを複数のデータサブセットに分割することと、
前記複数のデータサブセットの内の各データサブセットと他のデータサブセットとに対しパリティデータを生成することと、
前記複数のデータサブセットの内の前記各データサブセットとさらに他のデータサブセットとに対しパリティデータを生成することと、
を実行するように構成されたプロセッサを含むことを特徴とする装置。
【請求項１３】
請求項１２に記載の装置であって、前記装置は、コンピュータ、携帯型コンピュータ、携帯電話、携帯機器、サーバ、送信器、ディスク、ドライブコントローラからなるグループから選択されることを特徴とする装置。
【請求項１４】
プログラム指令を有するコンピュータプログラムであって、前記プログラム指令はコンピュータ上で実行されると、請求項１〜１１のいずれかに記載の方法を前記コンピュータに実行させるコンピュータプログラム。
【請求項１５】
請求項１４に記載のコンピュータプログラムを実装することを特徴とするコンピュータ可読媒体。
【請求項１６】
請求項１〜１１のいずれかに記載の方法を実行するようにプログラムされることを特徴とするコンピュータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パリティデータを生成する方法と装置に関し、特に、誤り訂正とデータ再構築における利用に関する。
【背景技術】
【０００２】
パリティデータは、データを保存又は送信する際の冗長性の確保に使用される。パリティデータは、読み込まれたデータ又は受信されたデータが正しいか確認するため、又は例えばディスクドライブや通信チャネルの不具合によって失われたデータを再生成するために使用することができる。一般的にパリティデータは、複数のデータセット又はサブセットに適用される排他的論理和（ＸＯＲ）関数を使用して生成される。
【０００３】
そのような冗長性は、例えばＲＡＩＤ５等の特定のＲＡＩＤディスクアレイにおいて利用される。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ＲＡＩＤアレイで使用されるパリティ方式は、１つのキャビネットや１カ所のデータセンタ内の監視されたディスクドライブを使用する制御された環境下において必要な冗長性をもたらすためには十分であるかもしれないが、冗長性の程度は、隔離して設置された或いはネットワークを介して分散された記憶装置又はディスクドライブが組み込まれた分散機構又はアドホック記憶機構に対しては不十分である場合がある。さらに、多くのＲＡＩＤシステムは、単一ディスクの故障のような単一障害点に対してのみ、それに対応したりそこから復帰したりすることが可能である。ＲＡＩＤアレイにおいて複数の故障が同時に発生した場合には復帰不能である。
【０００５】
このため、これらの問題点を解決する方法と装置が必要である。
【課題を解決するための手段】
【０００６】
このような背景に対し、最初の態様において、データを保護する方法であって、前記データを複数のデータサブセットに分割するステップと、前記複数のデータサブセットの内の各データサブセットと他のデータサブセットとに対しパリティデータを生成するステップと、前記複数のデータサブセットの内の前記各データサブセットとさらに他のデータサブセットとに対しパリティデータを生成するステップと、を含む方法を提供する。本方法は、データの損失又は破損からデータを守り保護するようにデータを処理する。失われたデータサブセットは、生成されたパリティデータ及び残りのデータサブセットから復元可能である。本方法は、複数の同時に発生した不具合に対してもより強い回復力を与える。例えば、複数のディスクドライブが同時に故障した場合や複数の離れた保存場所が利用不可となったりアクセス不能となったりした場合である。
【０００７】
任意として本方法は、前記複数のデータサブセットと前記生成されたパリティデータとを保存するステップをさらに含んでもよい。これらはディスクドライブ、フラッシュドライブ、コンピュータ、サーバ、その他のデータ格納場所、又はそれらを組み合わせた装置に保存可能である。保存場所は相互にリモートであってもローカルであってもよく、例えばインタネット等のネットワークを介してアクセス可能であってもよい。
【０００８】
任意として本方法は、前記複数のデータサブセットと前記生成されたパリティデータとを送信するステップをさらに含んでもよい。送信は、イーサネット（登録商標）及び携帯情報通信を含むがそれに限らない無線又は有線の送信を利用してもよい。
【０００９】
好適には、少なくとも２つのパリティデータが前記各データサブセットに対して生成される。３つ以上のパリティデータセットを生成してもよい。
【００１０】
任意として前記各データサブセットは、２つの隣接するデータサブセットに対して生成されたパリティデータを有してもよい。順番に分割されたデータに対しては、隣接するデータも順番となる。
【００１１】
任意としてパリティデータは、最初のデータサブセットと最後のデータサブセットとに対して生成されてもよい。言い換えると、組み合わせは循環的に並べられる。
【００１２】
好適には、前記パリティデータは排他的論理和（ＸＯＲ）論理演算子を使用して生成してもよい。他の論理演算子を使用することもできる。
【００１３】
任意として前記データは、奇数のデータサブセットに分割してもよい。偶数でもよい。
【００１４】
好適には、前記データは所定数のデータサブセットに分割してもよい。
【００１５】
第２の態様によると、データを復元する方法であって、データサブセットを取得するステップと、上記のように生成されたパリティデータを取得するステップと、前記取得されたデータサブセットと前記取得されたパリティデータとを使用して失われたデータサブセットを再生成するステップと、復元データを形成するように前記取得されたデータサブセットと前記再生成された失われたデータサブセットとを組み合わせるステップと、を含む方法を提供する。
【００１６】
第３の態様によると、データを復元する方法であって、１つ又は複数のデータサブセットを取得するステップと、前記１つのデータサブセットに対して生成された複数の異なるパリティデータセットを取得するステップと、前記取得された１つ又は複数のデータサブセットと、前記取得された複数のパリティデータセットを使用して失われたデータサブセットを再生成するステップと、復元データを形成するように、前記取得された１つ又は複数のデータサブセットと前記再生成された失われたデータサブセットとを組み合わせるステップと、を含む方法を提供する。データサブセット及び／又はパリティデータセットは、保存機構又は保存場所から復元してもよく、又は例えば信号として受信してもよい。
【００１７】
第４の態様によると、パリティデータを生成する装置であって、前記データを複数のデータサブセットに分割することと、前記複数のデータサブセットの内の各データサブセットと他のデータサブセットとに対しパリティデータを生成することと、前記複数のデータサブセットの内の前記各データサブセットとさらに他のデータサブセットとに対しパリティデータを生成することと、を実行するように構成されたプロセッサを含む装置を提供する。
【００１８】
任意として前記装置は、コンピュータ、携帯型コンピュータ、携帯電話、携帯機器、サーバ、送信器、ディスク、ドライブコントローラからなるグループから選択してもよい。他の機器やプロセッサを使用してもよい。
【００１９】
上記の方法は、コンピュータを動作させるプログラム指令を含むコンピュータプログラムとして実装してもよい。コンピュータプログラムは、コンピュータ読み取り可能媒体上に保存可能である。
【００２０】
上記の特徴事項は、本発明のいかなる特定の態様や実施形態においても利用可能である。
【図面の簡単な説明】
【００２１】
本発明は、様々な方法で実施可能であって、ここで以下の添付の図を参照しながら実施形態を例としてのみ説明する。
【図１】パリティデータを生成する方法を例としてのみ示す概略図である。
【図２】図１に示す方法に従って生成されたパリティデータを使用して失われたデータを再構築する方法を例として示す概略図である。
【図３】図１に示す方法に従って生成されたパリティデータを使用して失われたデータを再構築する更なる方法を例として示す概略図である。
【図４】図１に示す方法に従ってパリティデータを生成するシステムを示す図である。
【００２２】
図面は簡潔にするために表され、必ずしも縮尺通りに描かれていないことに注意が必要である。
【発明を実施するための形態】
【００２３】
パリティデータは排他的（ＸＯＲ）関数を使用して生成される。例えば以下のようにである。
[数１]
（Ａ）０１００＾（Ｂ）００１０＝（Ｐ）０１１０
ここで＾はＸＯＲ関数を示す。
データセットＡ又はＢのどちらかが失われた場合、失われたデータは、同じＸＯＲ関数を使用して残りのデータとパリティデータ（Ｐ）から例えば次のように再構築できる。
[数２]
（Ａ）０１００＾（Ｐ）０１１０＝（Ｂ）００１０
【００２４】
特定のデータファイル又はデータセットを保護するように冗長データを生成するため、元データ（Ｆ）を均等のブロック又はサブセットに分割する。次のように表すことができる。
[数３]
Ｆ{１，２，３，．．．ｎ}
パリティデータは次のように生成できる。
[数４]
１＾２，３＾４，．．．（ｎ−１）＾ｎ
【００２５】
図１により信頼性の高いパリティデータを生成する方法１０を示す。この方法１０では、より多くのデータサブセット（及び／又はパリティデータ）が失われても復帰可能にする。実線で描かれた円１，２，３，．．．ｎは元データを分割して形成されたデータサブセットを表す。各データサブセットに対しパリティデータが２セット生成される。各データサブセットは別のデータサブセットとペアとなり、パリティデータが生成される。次にデータサブセットはさらに他のデータサブセットとペアとなり、もう１つのパリティデータのセットが生成される。言い換えると、各データサブセットは他の２つの異なるデータサブセットと関連付けられ、各ペアに対しパリティデータが生成される。例えば図１において、各データサブセットが両隣とペアとなることで示されている（例えば、２は１とペアであり、また２は３ともペアである）。最初（１）と最後（ｎ）のデータサブセットは隣が１つしかない（各々２とｎ−１）。このため、最初のデータサブセットは最後のデータサブセットとペアとなって、複数のパリティデータセットが両端のデータセットに関連付けられるようにする。ただし、各データサブセットが少なくとも２つのパリティデータセットと関連付けられるように、他の組み合わせや順列を使用することも可能である。表記法形式では次のように表される。
[数５]
Ｃ１｛１＾２，３＾４，．．．（ｎ−１）＾ｎ｝
Ｃ２｛２＾３，３＾４，．．．ｎ＾１｝
【００２６】
元データを５つのデータサブセットへ分割する例では、４つのデータサブセットが失われた場合でも、すべてのパリティデータセットが取得可能であれば、元データのすべてを再構築可能である。このような状況を図２に示し、失われたデータサブセットを再構築又は再生成する例としての方法１００を概略的に示す。
【００２７】
この例において、第３サブセットと５つのパリティデータセット（１＾２，２＾３，３＾４，４＾５，５＾１）が利用可能である。図２の囲み内に２つの選択肢が示され、各失われたデータサブセット１，２，４，５はＸＯＲ関数を使用して再構築可能である。
【００２８】
図３は更なる例としての状況を示し、元データから５つのデータサブセットが作成されたが、そのデータサブセットの内の２つとパリティデータセットの２つ（２＾３，３＾４）が失われている。この特定の再構築方法２００では、横の囲み内のＸＯＲ演算子を使用して２つの失われたデータサブセット２と４が復元される。
【００２９】
一般論として、ｎ−１個までのいかなる組み合わせのデータサブセットの紛失であっても、すべてのデータを復元可能である。
【００３０】
なお、図２及び３に示した特定の例は、データを復元させる多数の選択可能な組み合わせと方式の内の２つである。さらに、図１に示す各データサブセットに対して２つのパリティデータセットを生成する循環式手法は多数の選択肢の内の１つである。例えば、各データサブセットは、隣ではないサブセットとペアとなってパリティデータを形成してもよい。
【００３１】
データをデータサブセットに分割する際には、所定数のデータサブセットを選択する。この数は、使用される利用可能な又は必要な記憶場所（各データサブセット用及び各パリティデータセット用）の数、個別のデータチャネル数又はデータサブセットをある場所から別の場所へ移動させる送信手段の数に関連する。
【００３２】
図４は、図１〜３を参照しながら説明した方法を実装するシステム３００を示す。これは例としてのシステムであって、当業者であれば他のものを考案可能であろう。この特定の例では、サーバ３１０はデータをデータサブセットへ分割しパリティデータを生成するために使用される。これらのデータサブセットとパリティデータは次に個別の保存場所３３０に保存される。保存場所３３０は、例えば、分散型であってもよいし、ネットワークを介して相互に離れて設置しても１つのキャビネット内に一緒に設置してもよい。別のコンピュータ又はプロセッサ３４０は保存場所３３０（例えばディスクドライブ）からデータを取得する。コンピュータ３４０は、図２又は３に対応する例としての手法に基づいて失われたデータを再生成したり再構築したりできる。
【００３３】
各データサブセットに対して複数のパリティデータセットを生成する利点は、冗長性を高めて各データサブセットに関付けられた単数のパリティデータセットに頼るよりもより大きな割合のデータ紛失を許容できることである。
【００３４】
パリティデータを生成する上記の方法とシステムは、例えば、ディスクアレイ、分散型保存システム、クラウド保存システムと同様に、データの信頼性と安全性が必要な他の多くの状況において利用可能である。例えば、パリティを生成するこの手法は、有線ネットワーク、無線ネットワーク、携帯型ネットワーク上でのデータの送受信や、例えば光ディスク等の物理的な媒体へのデータの保存に利用可能である。
【００３５】
当業者であれば理解できることであるが、上記の実施形態の詳細は、添付の請求項によって定義される本発明の範囲から逸脱することなく変更可能である。
【００３６】
例えば、パリティデータを算出するためにＸＯＲ関数に替えて他の論理関数を使用してもよい。
【００３７】
各データサブセットに対して作成する個別のパリティデータセットの数は、２つに限らず、それ以上であってもよい。例えば、各データサブセットは他の最大すべてのデータサブセットとペアにできる。
【数６】
2014525188.tif 000003
上記の数のパリティセットが作成され、「ｎ」はデータサブセット数を示し、「ｋ」はパリティデータを作成するために比較されたデータサブセット数（ｋ≦ｎ）を示す。例えば、データサブセットのペア（ｋ＝２）によって４つのデータサブセット（ｎ＝４）を作成すると、６つの個別の保存場所に入れられる６つの個別のパリティデータセットが形成される。
【００３８】
個別の保存場所を多く必要とせずに元データをより多数のデータサブセット（例えば５１２バイトごと）に分割するには、各個別の保存場所が個別のデータサブセット及び／又はパリティデータセットを多数保存できるようにする。保存方式が明らかでありさえすれば、再構築を正常に実施できる。
【００３９】
上記の実施形態の特徴事項に対する多くの組み合わせ、改良、変更は当業者には容易に明らかであって、本発明の一部を形成するものとする。１つの実施形態又は例に特定して関連するように説明されたいずれの特徴事項も適切に変更することによって他の実施形態に利用可能である。
【図４】
2014525188.tif 000004
【図１】
2014525188.tif 000005
【図２】
2014525188.tif 000006
【図３】
2014525188.tif 000007
【手続補正書】
【提出日】平成26年8月1日(2014.8.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データを保護する方法であって、
（ａ）前記データを複数のデータサブセットに分割するステップと、
（ｂ）前記複数のデータサブセットの内の各データサブセットと他のデータサブセットとに対しパリティデータを生成するステップと、
（ｃ）前記複数のデータサブセットの内の前記各データサブセットとさらに他のデータサブセットとに対しパリティデータを生成するステップと、
（ｄ）前記複数のデータサブセットと前記生成されたパリティデータとを分散型保存システムに保存するステップと、
（ｅ）１または複数のデータサブセットを取得するステップと、
（ｆ）１つのデータサブセットに対して生成された２またはそれ以上の異なるパリティデータセットを取得するステップと、
（ｇ）前記取得された１または複数のデータサブセットと、前記取得された２またはそれ以上のパリティデータセットを使用して失われたデータサブセットを再生成するステップと、
（ｈ）復元データを形成するように、前記取得された１または複数のデータサブセットと前記再生成された失われたデータサブセットとを組み合わせるステップと、
を含み、
ステップ（ａ）から（ｄ）はプロセッサにより実行され、ステップ（ｅ）から（ｈ）は、前記プロセッサとは異なるプロセッサまたはコンピュータにより実行される、
ことを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、
少なくとも２つのパリティデータセットが前記各データサブセットに対して生成されることを特徴とする方法。
【請求項３】
請求項１に記載の方法であって、
前記各データサブセットは、２つの隣接するデータサブセットに対して生成されたパリティデータを有することを特徴とする方法。
【請求項４】
請求項１に記載の方法であって、
パリティデータが最初のデータサブセットと最後のデータサブセットとに対して生成されることを特徴とする方法。
【請求項５】
請求項１に記載の方法であって、前記パリティデータは排他的論理和（ＸＯＲ）論理演算子を使用して生成されることを特徴とする方法。
【請求項６】
請求項１に記載の方法であって、前記データは奇数のデータサブセットに分割されることを特徴とする方法。
【請求項７】
請求項１に記載の方法であって、前記データは所定数のデータサブセットに分割されることを特徴とする方法。
【請求項８】
データを保護するシステムであって、
前記データを複数のデータサブセットに分割することと、
前記複数のデータサブセットの内の各データサブセットと他のデータサブセットとに対しパリティデータを生成することと、
前記複数のデータサブセットの内の前記各データサブセットとさらに他のデータサブセットとに対しパリティデータを生成することと、
前記複数のデータサブセットと前記生成されたパリティデータとを分散型保存システムに保存することと、
を実行するように構成されたプロセッサと、
１または複数のデータサブセットを取得することと、
１つのデータサブセットに対して生成された２またはそれ以上の異なるパリティデータセットを取得することと、
前記取得された１または複数のデータサブセットと、前記取得された２またはそれ以上のパリティデータセットを使用して失われたデータサブセットを再生成することと、
復元データを形成するように、前記取得された１または複数のデータサブセットと前記再生成された失われたデータサブセットとを組み合わせること、
を実行するように構成された前記プロセッサとは異なるプロセッサまたはコンピュータと、
を含むことを特徴とするシステム。
【請求項９】
請求項８に記載のシステムであって、前記プロセッサは、コンピュータ、携帯型コンピュータ、携帯電話、携帯機器、サーバ、送信器、ディスク、ドライブコントローラのうちの１つに供給されることを特徴とするシステム。
【請求項１０】
プログラム指令を有するコンピュータプログラムであって、前記プログラム指令はコンピュータ上で実行されると、請求項１に記載の方法を前記コンピュータに実行させるコンピュータプログラム。
【請求項１１】
請求項１０に記載のコンピュータプログラムを実装することを特徴とするコンピュータ可読媒体。
【請求項１２】
請求項１に記載の方法を実行するようにプログラムされることを特徴とするコンピュータ。
【国際調査報告】
2014525188.tif 000008
2014525188.tif 000009