(57)【要約】  ａ）データを複数のデータ要素に分離すること、ｂ）各データ要素の位置をデータ内での位置にしたがって記憶ロケーションとマッチングすること、ｃ）各データ要素を、マッチングされた記憶ロケーションに記憶すること、ｄ）グループ内のデータ要素のうち一つ以上がグループ内の残余データ要素とグループのパリティデータとから再作成されるようにデータ要素グループからパリティデータを生成すること、ｅ）ステップｄ）で使用されたのと同じデータ要素から異なる組み合わせで形成された追加データ要素グループから追加パリティデータを生成すること、およびｆ）パリティデータと追加パリティデータとを別々の記憶ロケーションに記憶することを包含する、データを記憶、検索、送信、および受信する装置および方法。
2013521555.tif 000002
【特許請求の範囲】
【請求項１】
データを記憶する方法であって、
ａ）前記データを複数のデータ要素に分離するステップと、
ｂ）各データ要素の位置を前記データ内での位置にしたがって記憶ロケーションとマッチングするステップと、
ｃ）各データ要素を、マッチングされた記憶ロケーションに記憶するステップと、
ｄ）グループ内の前記データ要素のうち一つ以上が前記グループ内の残余データ要素と前記グループのパリティデータとから再作成されるように、データ要素グループからパリティデータを生成するステップと、
ｅ）ステップｄ）で使用されたのと同じデータ要素から異なる組み合わせで形成された追加データ要素グループから、追加パリティデータを生成するステップと、
ｆ）前記パリティデータと追加パリティデータとを別々の記憶ロケーションに記憶するステップと、
を包含する方法。
【請求項２】
さらに、
ｅ）前記パリティデータの各要素を別々の記憶ロケーションに割り当てるステップと、
ｆ）各パリティデータ要素を別々の記憶ロケーションに記憶するステップと、
を包含する、請求項１に記載の方法。
【請求項３】
さらに、
ｇ）前記追加パリティデータの各要素を別々の記憶ロケーションに割り当てるステップと、
ｈ）追加パリティデータ要素の各々を別々の記憶ロケーションに記憶するステップと、
を包含する、請求項１または請求項２に記載の方法。
【請求項４】
前記マッチングが、データ要素位置および記憶ロケーションについてのルックアップテーブルに基づく、請求項１から請求項３のいずれか一項に記載の方法。
【請求項５】
ｉ）前記データ要素位置を２個以上の位置集合に順次分割することと、
ｉｉ）各集合の各データ要素位置を２個以上の記憶ロケーションに順次割り当てることと、
により前記ルックアップテーブルが形成される、請求項４に記載の方法。
【請求項６】
前記ルックアップテーブルがさらに、利用可能な追加記憶ロケーションが無くなるまでｉ）およびｉｉ）を反復することにより形成される、請求項５の方法。
【請求項７】
既存の記憶ロケーションを分割することにより追加記憶ロケーションを生成するステップをさらに包含する、請求項１から請求項６のいずれか一項に記載の方法。
【請求項８】
各データ要素がビットまたはビット集合である、請求項１から請求項７のいずれか一項に記載の方法。
【請求項９】
前記記憶ロケーションの各々が別々の物理デバイスである、請求項１から請求項８のいずれか一項に記載の方法。
【請求項１０】
前記データを暗号化するステップをさらに包含する、請求項１から請求項９のいずれか一項に記載の方法。
【請求項１１】
前記別々の記憶ロケーションが、ハードディスクドライブ、光ディスク、フラッシュＲＡＭ、ウェブサーバ、ＦＴＰサーバ、およびネットワークファイルサーバで構成されるグループから選択される、請求項１から請求項１０のいずれか一項に記載の方法。
【請求項１２】
前記データがウェブページである、請求項１から請求項１１のいずれか一項に記載の方法。
【請求項１３】
さらに、
一つ以上のデータ要素およびパリティデータに関数を適用して一つ以上の関連の認証コードを生成するステップ、
を包含する、請求項１から請求項１２のいずれか一項に記載の方法。
【請求項１４】
前記関数がハッシュ関数である、請求項１３の方法。
【請求項１５】
チェックサム、チェックディジット、フィンガープリント、ランダム化関数、エラー訂正コード、および暗号学的ハッシュ関数で構成されるグループから前記ハッシュ関数が選択される、請求項１４の方法。
【請求項１６】
前記別々の記憶ロケーションがネットワークを通してアクセス可能である、請求項１から請求項１５のいずれか一項に記載の方法。
【請求項１７】
各データ要素をマッチングおよび／または記憶する前記ステップが、パリティデータを生成および／または追加パリティデータを生成する前記ステップと同時に実施される、請求項１から請求項１６のいずれか一項に記載の方法。
【請求項１８】
記憶ロケーションに記憶されたデータを検索する方法であって、
ａ）オリジナルデータとパリティデータとを形成するデータ要素を前記記憶ロケーションから復元するステップと、
ｂ）復元された前記データ要素およびパリティデータから欠損データを再作成して再作成データ要素を形成するステップと、
ｃ）復元元であるか再作成先である前記記憶ロケーションに基づいて、復元および再作成された前記データ要素を前記オリジナルデータ内の位置にマッチングするステップと、
ｄ）マッチングされた位置にしたがって前記データ要素を組み合わせて前記オリジナルデータを形成するステップと、
を包含する方法。
【請求項１９】
前記マッチングが、データ要素位置および記憶ロケーションについてのルックアップテーブルに基づく、請求項１８に記載の方法。
【請求項２０】
ａ）データを複数のデータ要素に分離し、
ｂ）各データ要素の位置を前記データ内の位置にしたがって記憶ロケーションとマッチングし、
ｃ）各データ要素を、マッチングされた記憶ロケーションに記憶し、
ｄ）グループ内の前記データ要素のうち一つ以上が前記グループ内の残余データ要素と前記グループのパリティデータとから再作成されるように、データ要素グループからパリティデータを生成し、
ｅ）ステップｄ）で使用されたのと同じデータ要素から異なる組み合わせで形成された追加データ要素グループから、追加パリティデータを生成し、
ｆ）前記パリティデータと追加パリティデータとを別々の記憶ロケーションに記憶する、
ように構成されたプロセッサを具備する、データを記憶するための装置。
【請求項２１】
ａ）オリジナルデータとパリティデータとを形成するデータ要素を記憶ロケーションから復元し、
ｂ）復元された前記データ要素およびパリティデータから欠損データ要素を再作成して再作成データ要素を形成し、
ｃ）復元元であるか再作成先である前記記憶ロケーションに基づいて、復元および再作成されたデータ要素を前記オリジナルデータ内の位置にマッチングし、
ｄ）マッチングされた位置にしたがって前記データ要素を組み合わせて前記オリジナルデータを形成する、
ように構成されたプロセッサを具備する、記憶ロケーションに記憶されたデータを検索するための装置。
【請求項２２】
ａ）データを複数のデータ要素に分離するステップと、
ｂ）各データ要素の位置を前記データ内の位置にしたがって送信手段とマッチングするステップと、
ｃ）各データ要素を、マッチングされた送信手段で送信するステップと、
ｄ）グループ内の前記データ要素のうち一つ以上が前記グループ内の残余データ要素と前記グループの前記パリティデータとから再作成されるように、データ要素グループからパリティデータを生成するステップと、
ｅ）ステップｄ）で使用されたのと同じデータ要素から異なる組み合わせで形成された追加データ要素グループから追加パリティデータを生成するステップと、
ｆ）前記パリティデータと追加パリティデータとを別々の送信手段で送信するステップと、
を包含する、データを送信する方法。
【請求項２３】
各送信手段が異なるタイプの送信手段であるか異なる送信チャネルである、請求項２２の方法。
【請求項２４】
前記異なる送信手段が、電信電話網、電波、インターネットプロトコル、および移動体通信で構成されるグループから選択される一つ以上である、請求項２３の方法。
【請求項２５】
前記異なるチャネルが異なる無線周波数である、請求項２３の方法。
【請求項２６】
前記データ内の位置の奇偶状態にしたがって前記データがデータ要素に分離される、請求項１乃至１７、２２乃至２５のいずれか一項に記載の方法。
【請求項２７】
前記複数のデータ部分集合に論理関数を実施することにより前記パリティデータが生成される、請求項１乃至１７、２２乃至２６のいずれか一項に記載の方法。
【請求項２８】
前記論理関数が排他的論理和である、請求項２７の方法。
【請求項２９】
音声、携帯電話、パケットデータ、画像、リアルタイム二重データ、およびインターネットデータで構成されるグループから前記データが選択される、請求項２２乃至２８のいずれか一項に記載の方法。
【請求項３０】
ａ）データを複数のデータ要素に分離し、
ｂ）各データ要素の位置を前記データ内での位置にしたがって送信手段とマッチングし、
ｃ）各データ要素を、マッチングされた送信手段で送信し、
ｄ）グループ内の前記データ要素のうち一つ以上が前記グループ内の残余データ要素と前記グループのパリティデータとから再作成されるように、データ要素グループからパリティデータを生成し、
ｅ）ステップｄ）で使用されたのと同じデータ要素から異なる組み合わせで形成された追加データ要素グループから、追加パリティデータを生成し、
ｆ）前記パリティデータおよび追加パリティデータを別々の送信手段で送信する、
ように構成されたプロセッサを包含する、データを送信するための装置。
【請求項３１】
ａ）オリジナルデータとパリティデータとを形成するデータ要素を別々の送信手段から受信するステップと、
ｂ）受信された前記データ要素およびパリティデータから欠損データ要素を再作成して再作成データ要素を形成するステップと、
ｃ）受信元であるか再形成先である前記送信手段に基づいて、受信および再作成された前記データ要素を前記オリジナルデータ内の位置にマッチングするステップと、
ｄ）マッチングされた位置にしたがって前記データ要素を組み合わせて前記オリジナルデータを形成するステップと、
を包含する、データを受信する方法。
【請求項３２】
ａ）オリジナルデータとパリティデータとを形成するデータ要素を別々の送信手段から受信し、
ｂ）受信された前記データ要素およびパリティデータから欠損データ要素を再作成して再作成データ要素を形成し、
ｃ）受信元であるか再作成先である前記送信手段に基づいて、前記受信データと再作成データ要素とを前記オリジナルデータ内の位置にマッチングし、
ｄ）マッチングされた位置にしたがって前記データ要素を組み合わせて前記オリジナルデータを形成する、
ように構成されたプロセッサを具備する、データを受信するための装置。
【請求項３３】
請求項３０または請求項３２の装置を具備する携帯機器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを記憶および通信するための、特に、別々の記憶ロケーションにデータを記憶する、またデータを送信および受信するための方法およびシステムに関連する。
【背景技術】
【０００２】
データは、多様な技術を用いてコンピュータシステム内に記憶される。万一、デスクトップまたはラップトップコンピュータなど個々のコンピュータシステムが盗難されるか紛失した場合には、これに記憶されたデータも消失するという悲惨な結果となるかもしれない。別のドライブにデータをバックアップしてデータを維持してもよいが、それでも保護必要情報が消失して第三者に利用されることがある。システム全体の紛失または盗難ではない場合でも、個々のディスクドライブまたは他の記憶デバイスが故障してデータの消失につながり、同様の悲惨な結果が生じることがある。
【０００３】
ＲＡＩＤ（安価ドライブ冗長アレイ）のアレイは、様々な条件においてデータを記憶するように構成されるとよい。ＲＡＩＤアレイは、ディスクミラーリングおよび付加的な任意のパリティディスクを使用して、個々のディスクの故障に対する保護を行う。しかし、各々が所定の容量を有する一定数のディスクを備えるように、ＲＡＩＤアレイは予め構成されなければならない。ＲＡＩＤアレイの構成をアレイの再構築なしで動的に変更することは不可能であり、長いシステムダウン時間が生じる結果となる。例を挙げると、万一ＲＡＩＤアレイのスペースが不足しても、休止時間を延長せずにアレイの全体容量を増大させるように付加的なディスクを加えることは容易ではない。ＲＡＩＤアレイが２枚以上のディスクの故障に対処するのは容易ではなく、別々のＲＡＩＤアレイを組み合わせることも容易でない。
【０００４】
ＲＡＩＤアレイを形作るディスクがネットワークの様々な部分に配置されてもよいが、このように多数のディスクを設定することは困難で、ディスクを別々のロケーションに置くのは好都合でない。そのため、ＲＡＩＤアレイは一度や二度のディスク故障に対しては回復力を持つとしても、火災や洪水などの大惨事では、ディスクが通常は相互に近接して配置されているのでＲＡＩＤアレイのデータすべての破壊につながることがある。入れ子レベルのＲＡＩＤアレイは故障ディスクの回復力をさらに向上させるが、これらのシステムは複雑かつ高価であり、アレイを再構築せずに拡張するのは不可能である。
【０００５】
同様に、特に雑音または不安定チャネルでは、送信データの一部分が消失、破壊、または傍受されることがある。
【０００６】
さらに、現在のデータ記憶および／または送信の方法およびデバイスは、破壊およびデータ消失を被りやすい。わずかな程度の破壊でもデータ品質に影響しかねない。破壊は、再生中または受信メディアからの歪みおよび品質損失につながるので、高品質の視聴覚素材を記録するのにデータが使用される場合には特に、これが当てはまる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第５，３０１，２９７号明細書
【特許文献２】米国特許出願公開第２００４／０１７７２１８号明細書
【特許文献３】米国特許出願公開第２００２／０１２４１３９号明細書
【特許文献４】米国特許出願公開第２００９／０１７２２４４号明細書
【特許文献５】特許第８０１６３２８号公報
【特許文献６】米国特許出願公開第２００９／０２１０７４２号明細書
【特許文献７】米国特許第７，６３１，１４３号明細書
【非特許文献】
【０００８】
【非特許文献１】トマシアン  エイ（Ｔｈｏｍａｓｉａｎ  Ａ）；大規模ディスクアレイのためのマルチレベルＲＡＩＤ（Ｍｕｌｔｉ−ｌｅｖｅｌ  ＲＡＩＤ  ｆｏｒ  ｖｅｒｙ  ｌａｒｇｅ  ｄｉｓｋ  ａｒｒａｙｓ）パフォーマンス  エバリュエーション  レビュー（Ｐｅｒｆｏｒｍａｎｃｅ  Ｅｖａｌｕａｔｉｏｎ  Ｒｅｖｉｅｗ），２００６年３月
【発明の概要】
【発明が解決しようとする課題】
【０００９】
そのため、これらの問題を克服するデータのための記憶方法およびシステムが必要とされる。
【課題を解決するための手段】
【００１０】
第一の態様にしたがえば、
ａ）データを複数のデータ要素に分離するステップと、
ｂ）各データ要素の位置をデータ内での位置にしたがって記憶ロケーションとマッチングするステップと、
ｃ）各データ要素を、マッチングされた記憶ロケーションに記憶するステップと、
ｄ）グループ内の一つ以上のデータ要素がグループ内の残余データ要素とこのグループのパリティデータとから再作成されるように、データ要素グループからパリティデータを生成するステップと、
ｅ）ステップｄ）で使用されたのと同じデータ要素から異なる組み合わせで形成された追加データ要素グループから追加パリティデータを生成するステップと、
ｆ）パリティデータと追加パリティデータとを別々の記憶ロケーションに記憶するステップと、
を包含する、データを記録する方法が提供される。データ要素は、特定の要件にしたがって分割または区分されたデータの部分、部分集合、または区分でよい。例えば、データ要素は、単一ビット、バイト、バイトグループ、キロバイト、またはそれ以上であってもよく、同じサイズを有することが好ましい。データからのデータ要素は、順次、あるいはデータ内でのデータ要素の位置に基づいて各データ要素を記憶ロケーションと関連付けることにより、記憶される。例えば、データは、データストリーム、アレイ、またはファイルやファイルシステムの全体であってもよい。データ内の位置は相対位置であり、例えば、あらゆる第１データ要素が記憶ロケーション１と関連付けられ、あらゆる第２データ要素が記憶ロケーション２と関連付けられるというように、あらゆる第ｎデータ要素まで繰り返される。数ｎは、ｎ個のデータ要素と必要なパリティデータすべてとを追加記憶ロケーションに別々に記憶するのに必要とされる利用可能な記憶ロケーションの数に基づいて予め決定されるとよい。そのため、ｎは利用可能な記憶ロケーションの合計数よりも小さいとよい。
【００１１】
データ要素位置ｎと記憶ロケーションとのマッピングは、予め決定されるか、必要な時には計算されるとよい。このマッピングは、例えばテーブル、ルックアップテーブル、またはアレイとして記憶されるとよい。カスケーディングつまり各レベルのデータの分割および細分によるよりも、マッピング方法が使用されるとよい。
【００１２】
パリティデータは、データ要素のグループまたは集合から生成され、それから記憶される。前と同じデータ要素から、しかし異なる組み合わせで、追加パリティデータが生成される。こうして信頼性およびデータ復元性が向上する。
【００１３】
前もって生成されたパリティデータのグループから追加パリティデータが生成されることが好ましい。
【００１４】
そのため、データのカスケーディングを行う、つまり利用可能な記憶ロケーションを満たすまでデータを分割および細分するのではなく、マッチングプロセスによってデータが記憶されるとよい。必要とされるか利用可能である周知の数の記憶ロケーションが存在する場合には、この技術はより効率的で好都合である。
【００１５】
この方法はさらに、
ｅ）パリティデータの各要素を別々の記憶ロケーションに割り当てるステップと、
ｆ）各パリティデータ要素を別々の記憶ロケーションに記憶するステップと、
を包含することが好ましい。こうして復元性および安全性を向上させる。
この方法はさらに、
ｇ）追加パリティデータの各要素を別々の記憶ロケーションに割り当てるステップと、
ｈ）追加パリティデータ要素の各々を別々の記憶ロケーションに記憶するステップと、
を包含することが好ましい。
【００１６】
任意であるが、データ要素位置および記憶ロケーションについてのルックアップテーブルに基づいたマッチングであるとよい。
【００１７】
任意であるが、ルックアップテーブルは、
ｉ）データ要素位置を２個以上の位置集合に順次分割することと、
ｉｉ）各集合の各データ要素位置を２個以上の記憶ロケーションに順次割り当てることと、
により形成されるとよい。言い換えると、ルックアップテーブル、アレイ、またはデータスキーマは、シミュレーションに基づくか、データおよびパリティデータの順次分割に等しい。
【００１８】
任意であるが、ルックアップテーブルはさらに、利用可能な追加記憶ロケーションが無くなるまでｉ）およびｉｉ）を反復することにより形成される。
【００１９】
任意であるが、この方法はさらに、既存の記憶ロケーションを分割することにより追加記憶ロケーションを生成するステップを包含するとよい。必要に応じて、別々か異なる論理記憶エリアまたはロケーションを用意するように、記憶ロケーションは何回分割されてもよい。万一、記憶ロケーションまたは論理エリアが不足した場合には、再作成されたデータ要素またはパリティデータを入れるのにさらに分割が用いられてもよい。
【００２０】
任意であるが、各データ要素はビットまたはビット集合でよい。代替的に、これらがバイト、バイトグループ、または他のデータ部分集合であってもよい。
【００２１】
記憶ロケーションの各々は、別々の物理デバイスであることが好ましい。
【００２２】
任意であるが、この方法はさらに、データを暗号化するステップを包含してもよい。こうして安全性を向上させる。
【００２３】
別々の記憶ロケーションが、ハードディスクドライブ、光ディスク、フラッシュＲＡＭ、ウェブサーバ、ＦＴＰサーバ、およびネットワークファイルサーバで構成されるグループから選択されると、好都合である。
【００２４】
任意であるが、データはウェブページでもよい。
【００２５】
任意であるが、この方法はさらに、
一つ以上のデータ要素とパリティデータとに関数を適用して関連の認証コードを一つ以上生成するステップ、
を包含してもよい。
【００２６】
任意であるが、関数はハッシュ関数でよい。
【００２７】
任意であるが、ハッシュ関数は、チェックサム、チェックディジット、フィンガープリント、ランダム化関数、エラー訂正コード、および暗号学的ハッシュ関数で構成されるグループから選択されるとよい。
【００２８】
別々の記憶ロケーションはネットワークを通してアクセス可能であるとよい。このネットワークは、例えばインターネットでよい。
【００２９】
各データ要素をマッチングおよび／または記憶するステップが、パリティデータの生成および／または追加パリティデータの生成のステップと同時に実施されることが好ましい。言い換えると、データ要素が記憶ロケーションとマッチングされてからこのマッチングにしたがって記憶されている間に、パリティ生成が並行して行われるとよい。こうして、効率をさらに向上させてプロセスを高速化できる。データが復元または受信される時（つまり送受信に使用される場合）には、オリジナルデータの構築と並行して、パリティチェックを用いたデータ復元も実施されるとよい。多くの記憶ロケーションが消失するか受信データが破壊されて多くのデータ要素が再生成される必要がある場合には、これは特に重要であろう。
【００３０】
第二の態様にしたがえば、
ａ）データを複数のデータ要素に分離し、
ｂ）各データ要素の位置をデータ内の位置にしたがって記憶ロケーションとマッチングし、
ｃ）各データ要素を、マッチングされた記憶ロケーションに記憶し、
ｄ）グループ内の一つ以上のデータ要素がグループ内の残余データ要素とこのグループのパリティデータとから再作成されるように、データ要素グループからパリティデータを生成し、
ｅ）ステップｄ）で使用されたのと同じデータ要素から異なる組み合わせで形成された追加データ要素グループから、追加パリティデータを生成し、
ｆ）パリティデータおよび追加パリティデータを別々の記憶ロケーションに記憶する、
ように構成されたプロセッサを包含する、データを記憶するための装置が提供される。方法に関して説明され、これにしたがって実行される特徴が、装置にさらに組み込まれるとよい。
第三の態様にしたがえば、
ａ）データを複数のデータ要素に分離するステップと、
ｂ）各データ要素の位置をデータ内の位置にしたがって送信手段とマッチングするステップと、
ｃ）各データ要素を、マッチングされた送信手段で送信するステップと、
ｄ）グループ内の一つ以上のデータ要素がグループ内の残余データ要素とこのグループのパリティデータとから再作成されるように、データ要素グループからパリティデータを生成するステップと、
ｅ）ステップｄ）で使用されたのと同じデータ要素から異なる組み合わせで形成された追加データ要素グループから追加パリティデータを生成するステップと、
ｆ）パリティデータと追加パリティデータとを別々の送信手段で送信するステップと、
を包含する、データを送信する方法が提供される。記憶方法に関して説明され、これにしたがって実行される特徴が、送信方法にさらに組み込まれるとよい。
【００３１】
任意であるが、各送信手段は、異なるタイプの送信手段または異なる送信チャネルであるとよい。
【００３２】
任意であるが、異なる送信手段は、電信電話網、電波、インターネットプロトコル、および移動体通信で構成されるグループから選択される一つ以上でよい。
【００３３】
異なるチャネルが異なる無線周波数であることが好ましい。
【００３４】
任意であるが、データ内での位置の奇偶状態にしたがってデータがデータ要素に分離されるとよい。
【００３５】
任意であるが、複数のデータ部分集合に論理関数を実施することにより、パリティデータが生成されるとよい。
【００３６】
論理関数は排他的論理和であることが好ましい。これは特に効率的な関数であるが、他のものが使用されてもよい。
【００３７】
音声、携帯電話、パケットデータ、画像、リアルタイム二重データ、およびインターネットデータで構成されるグループから、データが選択されるとよい。
【００３８】
第四の態様にしたがえば、
ａ）データを複数のデータ要素に分離し、
ｂ）各データ要素の位置をデータ内の位置にしたがって送信手段とマッチングし、
ｃ）各データ要素を、マッチングされた送信手段で送信し、
ｄ）グループ内の一つ以上のデータ要素がグループ内の残余データ要素とこのグループのパリティデータとから再作成されるように、データ要素グループからパリティデータを生成し、
ｅ）ステップｄ）で使用されたのと同じデータ要素から異なる組み合わせで形成された追加データ要素グループから、追加パリティデータを生成し、
ｆ）パリティデータと追加パリティデータとを別々の送信手段で送信する、
ように構成されたプロセッサを包含する、データを送信するための装置が提供される。上述した特徴が送信装置にさらに組み込まれてもよい。
【００３９】
第五の態様にしたがえば、上述した装置を具備する携帯機器が提供される。
【００４０】
上述した方法は、例えば、ソフトウェア、ハードウェアまたはファームウェアを使用するコンピュータ装置、あるいは他の適当なプロセッサや集積回路を用いて実行されるとよい。例えばコンピュータ読み取り可能媒体に記憶されるか信号として送信されるコンピュータプログラムの中の命令として、この方法が実行されてもよい。
【００４１】
第五の態様にしたがえば、
ａ）オリジナルデータとパリティデータとを形成するデータ要素を記憶ロケーションから復元するステップと、
ｂ）復元されたデータ要素およびパリティデータから欠損データを再作成して再作成データ要素を形成するステップと、
ｃ）復元元であるか再形成先である記憶ロケーションに基づいて、復元および再作成されたデータ要素をオリジナルデータ内の位置にマッチングするステップと、
ｄ）マッチングされた位置にしたがってデータ要素を組み合わせてオリジナルデータを形成するステップと、
を包含する、記憶ロケーションに記憶されたデータを検索する方法が提供される。
【００４２】
データ要素位置および記憶ロケーションについてのルックアップテーブルに基づくマッチングであることが好ましい。
【００４３】
第六の態様にしたがえば、
ａ）オリジナルデータとパリティデータとを形成するデータ要素を記憶ロケーションから復元し、
ｂ）復元されたデータ要素およびパリティデータから欠損データを再作成して再作成データ要素を形成し、
ｃ）復元元であるか再作成先である記憶ロケーションに基づいて、復元および再作成されたデータ要素をオリジナルデータ内の位置にマッチングし、
ｄ）マッチングされた位置にしたがってデータ要素を組み合わせてオリジナルデータを形成する、
ように構成または設定されたプロセッサを包含する、記憶ロケーションに記憶されたデータを検索するための装置が提供される。
【００４４】
第七の態様にしたがえば、
ａ）オリジナルデータとパリティデータとを形成するデータ要素を別々の送信手段から受信するステップと、
ｂ）受信したデータ要素およびパリティデータとから欠損データ要素を再作成して再作成データ要素を形成するステップと、
ｃ）受信元であるか再作成先である送信手段に基づいて、受信および再作成されたデータ要素をオリジナルデータ内の位置にマッチングするステップと、
ｄ）マッチングされた位置にしたがってデータ要素を組み合わせてオリジナルデータを形成するステップと、
を包含する、データを受信する方法が提供される。
【００４５】
第八の態様にしたがえば、
ａ）オリジナルデータとパリティデータとを形成するデータ要素を別々の送信手段から受信し、
ｂ）受信されたデータ要素およびパリティデータから欠損データ要素を再作成して再作成データ要素を形成し、
ｃ）受信元であるか再作成先である送信手段に基づいて、受信データと再作成データ要素とをオリジナルデータ内の位置にマッチングし、
ｄ）マッチングされた位置にしたがってデータ要素を組み合わせてオリジナルデータを形成する、
ように構成または設定されたプロセッサを包含する、データを受信するための装置が提供される。
【図面の簡単な説明】
【００４６】
本発明はいくつかの方法で実行されるとよく、以下、添付図面を参照して単なる例として実施形態が説明される。
【図１】データを記憶するための方法のフローチャートを示し、本発明の説明を補うのに使用され、単なる例として挙げられている。
【図１ａ】図１に示されたものに類似した代替方法のフローチャートを示す。
【図２】図１の方法を用いて記憶されるデータの概略図を示す。
【図２ａ】図１ａの方法を用いて記憶されるデータの概略図を示す。
【図３】図１の方法により記憶されるデータの概略図を示す。
【図３ａ】図１ａの方法により記憶されるデータの概略図を示す。
【図３ｂ】単なる例として挙げられた、本発明により記憶されるデータの概略図を示す。
【図３ｃ】単なる例として挙げられた、本発明の一態様によりデータを記憶するための方法のフローチャートを示す。
【図４】図１の方法にしたがって記憶されるクラスタとして分散されたデータの概略図を示す。
【図４ａ】図１ａの方法にしたがって記憶されるクラスタとして分散されたデータの概略図を示す。
【図５】単なる例として挙げられた、データを記憶する方法の流れ図を示す。
【図６】データを記憶するのに使用されるネットワークの概略図を示す。
【図７】単なる例として挙げられた、本発明のさらなる態様による通信システムの概略図を示す。
【図７ａ】単なる例として挙げられた、本発明のさらなる態様による通信システムの概略図を示す。
【図８】単なる例として挙げられた、本発明のさらなる態様による通信システムの概略図を示す。
【図８ａ】単なる例として挙げられた、本発明のさらなる態様による通信システムの概略図を示す。表１は、図３ｂのデータをマッピングするのに使用される情報の概略表示を示している。図および表は、単純化のため描かれており必ずしも一定の比率ではないことに注意すべきである。
【発明を実施するための形態】
【００４７】
記憶されるデータは、一例を挙げるとバイナリファイルの形であるとよい。データは、データの部分集合またはデータ要素に分割されるとよい。一つ以上のデータ部分集合が破壊されるか消失した場合に残りの部分集合およびパリティデータから欠損部分集合が再作成されるように、データの部分集合からパリティデータが生成されるとよい。パリティまたは制御データは、エラー検査の目的で、または消失データが再生成されるように、オリジナルデータから生成されるとよい。しかし、パリティデータは、オリジナルデータに含まれていた情報以外の付加的な情報を含まない。このようなパリティデータの生成を行う論理演算はいくつかある。一例を挙げると、排他的論理和（ＸＯＲ）を２個の二進数に適用すると、第３の二進数が得られ、これがパリティ数である。万一、オリジナルの２個の二進数のいずれかが消失した場合には、残りのオリジナル数とパリティ数との間でＸＯＲを実施するだけでこれが復元される。パリティデータの計算についてのさらに詳細な説明については、
ｈｔｔｐ：／／ｗｗｗ．ｐｃｇｕｉｄｅ．ｃｏｍ／ｒｅｆ／ｈｄｄ／ｐｅｒｆ／ｒａｉｄ／ｃｏｎｃｅｐｔｓ／ｇｅｎＰａｒｉｔｙ−ｃ．ｈｔｍｌ
を参照すること。パリティデータが計算されると、データ部分集合およびパリティデータのすべてが別々のまたは遠隔のファイルロケーションに記憶されるとよい。
【００４８】
しかし、付加的な記憶ロケーションを利用するためには、データ部分集合またはパリティデータの各々が追加部分集合に分離されて、追加パリティデータが生成されるとよい。こうして、利用可能な記憶ロケーションがすべて利用されるか所定のロケーション数限界値に達するまで、データ部分集合のカスケードが作成されるとよい。適当な再生成の計算またはアルゴリズムを用いて残余データ部分集合およびパリティデータから欠損データ部分集合が再生成または再作成される逆プロセスを用いて、データが復元されるとよい。オリジナルデータが復元されるまで、読み取りプロセスが継続する。
【００４９】
代替的な一実施形態では、データ部分集合の認証を確認するのに使用するため、認証またはハッシュコードがデータ部分集合および／またはパリティデータのいずれかと関連付けられるとよい。データ部分集合の作成に続いて認証データ部分集合が故意にまたは偶然に変化するか変更されることはない。この代替実施形態またはその変形は、文中では認証実施形態と記される。
【００５０】
図１は、データを記憶するための方法例１０の流れ図を示している。ステップ３０では、オリジナルデータ２０がデータ部分集合ＡおよびＢに分割される。データは二つの等しい部分に分割されるとよいため、部分集合ＡおよびＢはサイズが等しい。サイズの等しい部分集合ＡおよびＢを保証するのに、ゼロパディングが使用されるとよい。例えば、パリティデータＰが生成される前に部分集合ＡおよびＢの最後に付加的なゼロバイト（またはビットグループ）が追加されてもよい。データ２０が部分集合ＡおよびＢに分割された後、ステップ４０において排他的論理和（ＸＯＲ）演算が部分集合ＡおよびＢに実行されて、パリティデータ集合Ｐが生成されてもよい。代替的に、分割または分離ステップ３０の間にパリティデータＰが生成されてもよい。
【００５１】
図１ａの流れ図１０’に示された認証実施形態の方法では、データ部分集合ＡおよびＢの生成の後、ステップ４５でハッシング関数ｈ（ｎ）が適用されるとよい。このハッシング関数は、ハッシュコードｈ（Ａ）およびｈ（Ｂ）を生成する。パリティデータＰもハッシュされてハッシュコードｈ（Ｐ）が生成されてもよい。ハッシング関数は、これを実施するか結果的に得られるハッシュコードを比較する計算力が許容範囲であるかシステム限界内であるように選択されるとよい。ハッシュ関数は、部分集合Ａ，Ｂおよび／またはパリティデータＰに適用されるとよい。データ部分集合またはパリティデータのうち一つ以上の何らかの組み合わせをハッシュしないことにより、コンピュータオーバーヘッドの削減が行われるとよい。
【００５２】
結果的に得られる２個のデータ部分集合ＡおよびＢとパリティデータ集合Ｐ（および任意のハッシュコード）が、ステップ５０で記憶されるとよい。例を挙げると、メモリまたはハードドライブに、部分集合Ａ，Ｂおよびパリティデータが記憶されるとよい。方法１０はこの点でループを描くとよい。ステップ６０では、利用可能であるか必要とされる追加記憶ロケーションが存在するかどうかが判断される。存在する場合には、方法ループはステップ３０へ戻り、ここでデータ部分集合Ａ，Ｂおよび／またはパリティデータＰのいずれかまたは各々が新しい部分集合および追加パリティデータ集合にさらに分割される。利用可能であるか予め設定された追加記憶ロケーションが無くなるまで、ループが継続して、各データ部分集合とパリティデータとが分割および生成され、ステップ７０で方法は終了する。
【００５３】
認証実施形態では、ハッシュまたは認証コードがデータ部分集合Ａ，Ｂおよび／またはパリティデータＰとともに記憶され、ヘッダ情報として記憶されるか、おそらくは専用ハッシュライブラリまたはストアに別々に記憶されるとよい。
【００５４】
付加的な記憶ロケーションが利用可能であって、この方法のループ操作がさらに行われる際には、一番下のレベルの分割データ、つまり中間データ部分集合でなく実際に記憶されるデータそのものに達するまで、ハッシュ生成が任意で変更されてもよい。こうして効率を向上させる。
【００５５】
非認証実施形態では、方法１０のループの最初の反復により、３個の別々のデータファイル（Ａ，Ｂ，Ｐ）が得られる。２回完全に反復されると、９個の別々のデータファイルが得られ、３回完全に反復されると、２７個の別々のデータファイルが得られる。代替的に、各データ部分集合を同一程度に分割することが必要とされなくてもよい。利用可能な多くの記憶ロケーションが存在する際には、所定の最小サイズの部分集合が作成されるまで、部分集合が分割されて追加部分集合が作成される。データ消失に対する回復力を高めるため、記憶ロケーションのさらなる利用が単純な複製を伴うものであってもよい。
【００５６】
図１ａに示された認証実施形態では、３個の別々のデータファイルが生成され（Ａ，Ｂ，Ｐ）、３個のハッシュコードが生成される（Ａｈ，Ｂｈ，Ｐｈ）。
【００５７】
データ２０が９個の別々のロケーションに分割された状態で、これらのデータ集合のうち４個が消失するか破壊されても（任意のハッシュコード比較により検出可能）、オリジナルデータ集合２０を再作成することが常に可能である。４個以上が消失しても、オリジナルデータ集合２０の正確な再生成が行われることがあるが、これは、どの特定集合が消失したかに左右されるので、保証は可能でない。
【００５８】
データの破壊または調節が発生していないことを保証するため、図１ａに示されたハッシュコードが、記憶されたすべてのデータファイルおよび／またはパリティデータについて生成されるとよい。
【００５９】
図２は、図１に示された方法を１回反復した結果であるデータの概略図を示している。同様の方法ステップは、同じ参照番号を有している。オリジナルデータ集合２０がバイト単位（またはビット単位）で分割されて、データ部分集合Ａおよびデータ部分集合Ｂ（つまり１バイトのブロックサイズ）が生成される。排他的論理和演算でパリティデータＰが生成される。利用可能な別々の記憶ロケーションが３個あるならば、方法１０はこの段階で終了して、分散した３個の個別データ部分集合Ａ，Ｂ，Ｐを有するデータクラスタ１５０が得られる。
【００６０】
図２ａは、ハッシュコードを含むデータの代替的な概略図を示している。
【００６１】
図３は、方法１０のステップ３０，４０，５０をさらに反復した結果を示している。この場合、９個の別々の記憶ロケーションが利用可能であり、３個のデータ部分集合Ａ，Ｂ，Ｐの各々が３個の追加データ部分集合にそれぞれ分割されるとよい。
【００６２】
図３ａに示されているように、認証実施形態では、一番下のレベルのデータ部分集合および／またはパリティデータＡＡ，ＡＢ，ＡＰ，ＢＡ，ＢＢ，ＢＰ，ＰＡ，ＰＢ，ＰＰのみにハッシュコードが必要とされるが、それは後で再生成のために記憶されるファイルはこれらのみである、つまり認証を確認するために読み取られる時にこれらが認証を必要とするからである。
【００６３】
カスケードのうち一番下のレベルのデータ集合について、様々なハッシュコードが生成されるとよい。
【００６４】
この付加的な再帰的分割２３０の結果、データ部分集合Ａが分割されて追加データ部分集合ＡＡおよび追加パリティデータＡＰが形成される。同様に、データ部分集合ＢがＢＡおよびＢＢに分割され、これらはパリティデータＢＰを形成するのに一緒に使用されるとよい。パリティデータＰは、ＰＡ，ＰＢ，ＰＰに分割されるとよい。この特定の方法実施形態では、３個のデータ部分集合の各々が同じサイズを有する。これら９個のデータ部分集合の各々を記憶するのに使用される９個の別々のデータロケーションは、図４にさらに詳しく示されている第２レベルクラスタ２５０を形成するとよい（認証実施形態については図４ａを参照すること）。
【００６５】
言い換えると、第１レベルクラスタ１５０が拡張されて第２レベルクラスタ２５０が形成されるのである。そのため、オリジナルの３個のデータ集合Ａ，Ｂ，Ｐを記憶する必要がなく（しかし、データ消失に対する回復力を追加するための代替的方法として、どこかでこれが行われてもよい）、これらは第２レベルクラスタ２５０の９個のデータ部分集合からそれぞれ再作成されるとよい。利用可能なすべての記憶ロケーションが使用されるか、所定の限界に達するか、各部分集合のサイズが特定のレベルに縮小されるまで、方法１０のループが必要な回数だけ反復されるとよい。
【００６６】
前出のステップは、万一、個々の別記憶ロケーションが利用不能となるか破損した場合にもデータが復元されるように、データおよびパリティデータをどのようにして特定の記憶ロケーションに設けるかを説明している。データのロケーションおよび分布は信頼できるソースにしか知られていないので、こうしてデータがより安全に保管される。要約すると、データは「層」に分割および再分割され、利用可能な記憶ロケーションを占める特定数のデータ部分集合およびパリティデータ部分集合を有するデータのカスケードが形成されるまで、各層でパリティデータが計算される。カスケードの一番下では、最終のデータ部分集合およびパリティが別々の記憶ロケーションに記憶される。言い換えると、各中間ステップまたは層のコンテンツが判断されるが、例えば最終レベルのみが記憶されるとよい。利用可能な記憶ロケーションを埋めるように、必要に応じて中間層の一部が記憶されてもよい。
【００６７】
特定の記憶ロケーションの破損の後でどのようにしてデータが再作成されるかも明白である。データの「リバースカスケード」が達成され、オリジナルのデータ部分集合が記憶される場所が分かって、最終的にはオリジナルデータが再作成および復元されるとよい。しかし、上述したものと同一のデータ構造が結果的に得られる一層効率的な手順が使用されて、再帰的データ分割ステップまたは層の各々を間に含む必要がないとよい。
【００６８】
特定数の別記憶ロケーションの各々について前もって判断を行うことによりこれが達成されるとよく、オリジナルデータ２０からの各データ要素が最終的に別々の記憶ロケーションに置かれることになるだろう。方法が等しいので、データの復元は前と同じようにして達成されるとよい。より程度の高い並行処理が採用されてもよい。
【００６９】
図３ｂは、このより効率的な並行した処理を説明するための例を示している。この特定例では、９個の別々の記憶ロケーションＳ１〜Ｓ９が設けられる。データ２０は、データ要素ａ１，ａ２，ａ３などのストリームにより表される。類似の構造を有する次の下位レベルのため、２７など、異なる数の記憶ロケーションが使用されてもよい。
【００７０】
第１レベルのデータ分割では、上の説明にしたがって、データ要素ａ１が第１データビン６２０に割り当てられ、データ要素ａ２は第２データビン６３０に割り当てられる。図３ｂは、次のレベルのデータ分割中に、データ要素ａ１が記憶ロケーションＳ１に記憶されてデータ要素ａ２が記憶ロケーションＳ４に記憶されることを示している。そのため、第１データビン６２０および第２データビン６３０のコンテンツを計算する必要はないが、これらは例示を目的として示されている。さらに、データ要素ａ３は記憶ロケーションＳ２に記憶され、データ要素ａ４は別の記憶ロケーションＳ５に記憶される。このようなデータ要素位置と記憶ロケーションとの特定のマッピングまたはマッチングは、例えばメモリに記憶されるルックアップテーブルまたは他のタイプのアレイであるとよい表１に示されている。ルックアップテーブルは、実行時間計算をより単純なルックアップ操作と置き換えるのに使用されるアレイ状のデータ構造でよい。
【００７１】
９個の別々の記憶ロケーションが使用されるこの特定例では、記憶ロケーションＳ３およびＳ６〜Ｓ９の各々がパリティデータを格納している。しかし、データ要素がどのように分割されるかに応じて、異なる数の別記憶ロケーションが利用されてもよい。図３ｂに示された例において、カスケードの各レベルでは、データを二つに分割して各分割で単一のパリティデータ要素を提供する。代替的に、各レベルでデータを３回以上分割するか、層ごとに程度の異なる分割が行われてもよい。こうして、利用可能な記憶ロケーションの数に応じて、代替的なデータ処理が行われるとよい。図３ｂおよび表１に示されているように、各レベルでデータが二つに分割されて二つの層が設けられるには、９個の別々の記憶ロケーションを必要とする。そのため、オリジナルデータ２０のデータ要素が連続位置に割り当てられ（第１、第２、第３、第４、第１、第２、第３、第４など）、各位置の各データ要素は常に同じ別記憶ロケーションに記憶される。これは、データ２０の４個のデータ要素による次のグループがｂ１，ｂ２，ｂ３，ｂ４であり、Ｂ１も最終的に記憶ロケーションＳ１に置かれ、ｂ２が最終的に記憶ロケーションＳ４に置かれることなどで例示されている。
【００７２】
そのため、点線のボックス６２０，６３０として示されている第１レベルでのデータ分割は必要ではなく、一列になったデータ要素位置を決定して、前もって規定された特定の記憶ロケーションとこれをマッチングすることにより、別の記憶ロケーションの最終層にデータが直接記憶されるとよい。
【００７３】
この結果、個々のデータ要素が、使用される各レベルについて中間データビン６２０，６３０に割り当てられる必要がないので、より効率的な手順が得られる。
【００７４】
さらに、データ要素と関連するパリティデータが最終層まで計算される必要がなく、さらなる効率が達成される。
【００７５】
最初のデータ２０から最終記憶ロケーションまで個々のデータ要素がマッピングされるとよいが、カスケードの各レベルでパリティデータが計算される必要があり、最終レベルのパリティデータは別の記憶ロケーションに記憶される。記憶ロケーションＳ７およびＳ８に記憶されるパリティデータは、Ｓ３およびＳ６の組み合わせとは異なるデータ要素の組み合わせから計算されるとよいことに注意すること。ロケーションＳ９に記憶されるパリティ情報が、Ｓ７およびＳ８のパリティ情報からさらに計算されるとよい。言い換えると、データからのどの特定のデータ要素がグループ化されてそのパリティ値が求められるかが前もって決定されるので、中間レベル（Ｓ７およびＳ８のレベルなど）がなくてもいくつかの（すべてではないとしても）パリティデータを計算することが可能である。カスケーディングされたパリティデータからのパリティデータが再び計算されて、最終レベルに記憶され、例えばロケーションＳ９に記憶される。しかし、パリティ計算は、マッチングされたデータを書き込むか送信するのに必要な比較的長い時間の間に実行されるとよい。
【００７６】
図３ｃは、図３ｂに示された別々の記憶ロケーションＳ１〜Ｓ９にデータを書き込むための方法７１０のフローチャートを示している。やはりこの例でも、最終結果および記憶されるデータは、同じデータ２０が使用される図１に示された方法のものと同一である。しかし、使用される代替的記憶構造によりプロセスをさらに調整するのに、プレマッピングが使用されてもよい。データ２０が順次読み取られ、データ２０内の各データ要素がデータ２０内での位置と関連付けられる（ステップ７３０）。ステップ７４０では、データ２０内の位置にしたがって（順次に、または他の形で）、各データ要素が記憶ロケーションＳ１〜Ｓ９とマッチングされる。ステップ７５０では、各データ要素がマッチングされた記憶ロケーションに記憶される。これは記憶ロケーションのすべてではなく、データ要素の記憶に使用されるロケーションのみとのマッチングであることに注意すること。
【００７７】
並行して実行されるこの方法の別のブランチでは、ステップ７３０で読み取られたデータ要素グループのパリティデータがステップ７６０で生成される（この例では、例えばロケーションＳ３，Ｓ６，Ｓ７，Ｓ８に記憶される）。これらのパリティデータを生成するのに使用されるデータ要素グループの特定の組み合わせは、予め分かっている。これらのパリティデータは最終レベルのパリティデータと等しいので、ステップ７６５で特定の記憶ロケーションに直接記憶されるとよい。ステップ７６０で生成されるパリティデータは、データ要素の異なるグループ分けを含む。この例では、各データ要素は２回使用される（例えばＰａ１ａ３およびＰａ１ａ２については、異なるデータ要素でａ１が２回使用される）が、他の組み合わせも可能である。言い換えると、ａ１が二つのパリティグループに入れられるのである。
【００７８】
データ要素ではなく高いレベルのパリティデータから全体が生成されたパリティデータ（例えば、記憶ロケーションＳ７，Ｓ８，Ｓ９に示されたパリティデータ）が、ステップ７７０で生成される。この例では、第２レベルデータが記憶される。しかし、２レベル以上のカスケードが使用される（または部分的にシミュレーションされるか計算される）実行例では、ステップ７８０で記憶される最終パリティデータ要素に到達するように、追加パリティデータが生成されるとよい。このようなパリティデータの中間的計算は、点線７７５で表されている。
【００７９】
この特定方法によって、あるレベルの並行処理がさらに可能となり、図１および関連の説明で例示されているように、あるデータ要素の記憶が達成される前に付加的な計算のために待機しなければならないのではなく、データが記憶されている間（それ自体がかなりの遅延を有する）に計算が行われることに注意すること。
【００８０】
多様な組み合わせおよび変形が可能であり、上述のカスケード手順を実行するよりも効率的である一層効率的な追加アルゴリズムを用いて最終レベルでのパリティデータが生成されるとよい。必要であるか利用可能である別々の記憶ロケーションの数と、利用可能なデータ記憶スペースと比較して必要な冗長性および復元性のレベルとに応じて、図３ｂに示された多様な構造のデータスキーマ６００が使用されるとよいことにも注意すること。
【００８１】
表１に示されたテーブル、ルックアップテーブル、またはアレイは、これらの特定データスキーマの各々について前もって生成されるか、必要に応じて計算されるとよい。別々の記憶ロケーションＳ１〜Ｓ９は別々の物理デバイスと記されてもよく、異なるタイプのものであってもよい。代替的に、単一の記憶ロケーションの別々の部分を単一のデバイスに分割する、仕切る、あるいは割り当てることにより、別の論理記憶ロケーションが生成されてもよい。図３ｂに示された例では、８個の別々の記憶ロケーションが利用可能である場合には、これらの記憶ロケーションの一つが二つに分割され、２個の別々の論理記憶ロケーションとして規定される。これは、カスケード内でレベルを上げることと、３個の別々の記憶ロケーションのみを有することよりも優先される。
【００８２】
図５は、図１に示された方法１０にしたがってデータを記憶するのに使用されるシステム３００の概略図を示している。図５に示されたシステムは、認証実施形態にしたがってシステム３００の安全性および信頼性を高めるのに使用される付加的な任意のステップを示している。中央サーバ３６０はこの方法を管理して、システム３１０へ入るリクエストをユーザから受け取る。ユーザはログオンして、暗号化キー３２０を提供される。さらに、ステップ４５では一組のハッシュコード（一意であってよい）が生成され、これは、認証を保証するのに使用されるファイル用の一意識別子として機能する。暗号化キーは、ハッシュコードを生成するのに使用されるとよい。この特定実施形態では、ファイルがデータ２０として記憶されている。ログイン情報および暗号化キーと記憶されるファイル名とを記憶するのにデータベース３７０が使用される。ステップ３４０では、ユーザがデータベースに登録してファイル名が作成され、データファイルが部分集合Ａ，Ｂに分割され、これらのデータ部分集合からパリティデータＰが作成される。ステップ３５０では、やはりデータベース３７０により管理される識別子が、データ部分集合およびパリティデータの各々に割り振られる。別々の記憶ロケーションはネットワークを通してアクセス可能であり、利用可能な記憶ロケーション３８０のプールを形成する。サーバ３６０は、達成される再帰的分割（または同等物）の最大レベルを決定し、これは、既定の優先順位またはシステムパラメータにより決定されるとよい。サーバ３６０はまた、プール３８０内の個々の別記憶ロケーションの各々の利用可能性を監視する。
【００８３】
このようにして、個々のユーザが、利用可能なプール３８０からの特定数の別々の記憶ロケーションにおいて、特定のファイルまたはそのデータ記憶システム全体をバックアップすればよい。サーバ３６０は、ユーザには見えない処理層として記憶を管理すればよい。言い換えると、システムにアクセスしてしまうと、データの記憶はユーザには従来の記憶および検索に見える。オリジナルデータ２０は記憶ロケーション３８０のプールから検索され、その間に要求されたデータ層からのパリティデータＰを用いて欠損データが再生成されるとよい。サーバ３６０は、データカスケーディング（または同等物）および各データ部分集合のレベルを追跡し続ける。サーバはまた、ハッシュコードを記憶および管理し、このコードは、別々に、またはデータ部分集合およびパリティデータと一緒に記憶されるとよい。
【００８４】
さらに、データ部分集合が暗号化キーを用いて暗号化され、ハッシュコードを用いて改ざんおよび歪曲防止機能が組み込まれるとよい。そのため、図５に示されたシステム３００では、この記憶プール３８０内の個々の別記憶ロケーションのうちいずれかまたはすべてにアクセスする第三者は、サーバ３６０によって管理されているオリジナルの暗号化キーがなければオリジナルデータ２０を再生成することができないので、保護必要情報を記憶するユーザにさらなる安全性を提供する。代替的に、暗号化キーが必要とされず、オリジナルと同じハッシュコードにより変更データ部分集合を生成するのに必要な計算力に禁止レベルを設けてもよい。さらなる安全性のためデータ部分集合を暗号化するのに暗号化キーが使用されてもよい。記憶プール３８０とユーザとの間でのデータ部分集合の転送が第三者によって妨害されても、暗号化キーがなければいかなるデータも彼らに利用可能とはならず、少なくとも最小数のデータ部分集合のコピーを入手することもできない。
【００８５】
方法１０または７１０を実施するのに使用されるシステムのさらなる実施形態が、図６に示されている。図６に示されたシステム４００は、インターネットまたはイントラネットなどのネットワークを通して情報を安全に分散するのに使用される。インターネットまたはウェブページ４２０の部分集合は、中央サーバ４１０を介してユーザ装置４４０へ安全に分散されるとよい。中央サーバ４１０はウェブページ４２０を取り込んで、図１に示された方法１０にしたがってこれを別の記憶ロケーション４３０に記憶する。図５を参照して説明されたように、認証を与えるためデータ部分集合が暗号化および／またはハッシュされる。中央サーバ４１０は、暗号化コード、または特定の記憶ロケーション４３０からのデータ部分集合を識別して配置するコードおよび情報、そしてオリジナルウェブページ４２０を形成するデータをどのようにして再作成するかをユーザ装置４４０に提供する。そのため、オリジナルデータ２０が別々の記憶ロケーション４３０の間で分散されるので、ウェブページ４２０が単一ポイントでの故障または攻撃（例を挙げると、単一ウェブサーバの機能停止）を受けることはもはやない。さらに、ユーザコンピュータ４４０のネットワークトラフィックを傍受する第三者がいても、中央サーバ４１０により供給される暗号化キーおよび再生成情報がなければ、ウェブページ４２０を形成するオリジナルデータを暗号化または再作成することができない。
【００８６】
データ部分集合および／またはパリティデータを再ハッシュして、その結果得られたハッシュコードをオリジナルと関連するコードと比較することにより、変更が検出されるとよい。相違が検出されると、認証されたデータ集合および／またはパリティデータのみを用いて、このデータ部分集合またはパリティデータが拒否されて再作成されるとよい。ハッシュコードによる認証に失敗した（さもなければ消失するか利用不能である）データ部分集合または要素のみが、再作成または再生成される必要がある。
【００８７】
このような安全システムは、銀行取引または他の形の安全データ、あるいはシステムユーザが付加的なプライバシーおよびセキュリティを必要とする場合に適しているだろう。
【００８８】
中央サーバ４１０は、利用可能なインターネット全体または特定の個別ウェブサイトの記憶またはキャッシュを行って、これらを特定の認証されたユーザのみに利用可能とする。中央サーバ４１０は、サーチエンジンまたは他の中央情報コンソリデータの機能も実施するとよい。このようにしてサーチエンジンに問い合わせると、ウェブサイトまたは追加検索可能ドキュメントを突き止めて再生成するのに使用される暗号化キーおよび情報を含むサーチ結果が得られる。
【００８９】
認証実施形態にしたがったこのような記憶システムのさらなる用途は、歪みおよび欠損データを回避して高品質のメディアを記憶および再作成することである。例えば、高いレベルのエラー検査が使用されることにより、高品質の音声または画像記録が得られる。各データ部分集合は、認証コードまたはハッシュコードを用いて認証（破壊など）について検査されるとよい。この認証試験を通過しなかったデータ部分集合は拒否され、認証を通過したパリティデータおよびデータ部分集合を用いて再生成される（パリティデータも検査されるとよい）。
【００９０】
例を挙げると、ハードドライブ、ＣＤ、ＤＶＤおよびブルーレイ（ＲＴＭ）などの光ディスク、そしてＭＰ３およびＭＰＥＧタイプのエンコーディングと類似したファイルエンコーディングにおいて、この記憶方法が実行されるとよい。この方法は、高品質のマルチメディアファイルを生成するのに使用されるとよい。
【００９１】
図７は、通信システムの概略図を示している。２台の通信デバイス５００，５１０が相互にデータの送受信を行う。これは、携帯電話ネットワークなどの通信ネットワークを介して、または双方向無線などのように直接、行われるとよい。以下の例では、音声データが実例として使用される。しかし、例を挙げると、画像、ウェブまたはインターネット、およびデータファイルなど、他の多くのタイプのデータが送信および受信されてもよい。
【００９２】
図７に示されているように、データ記憶のため、図１および３ｃに関して説明されたのと類似の方法を用いて、音声データがデータ部分集合または要素とパリティデータとに分割される。これらのデータ部分集合または要素Ａ，ＢおよびパリティデータＰは、個々のチャネルＣ１，Ｃ２，Ｃ３または追加送信手段により別々に送信される。これらのデータ集合は他の方法にしたがって一緒にまたは別々に送信され、異なる媒体、例を挙げると無線、ケーブル、および光ファイバ送信の混合を用いて送信されてもよい。分割機能は、通信デバイス５００において、または携帯電話基地局または類似物などの送信ネットワーク設備において実行されるとよい。記載された機能を実行する付加的なハードウェアの追加によって、携帯電話が改造されるとよい。代替的に、ソフトウェアとして機能が実行されてもよい。
【００９３】
データ記憶用実施形態についてであるが、代替的な認証実施形態として、ハッシュコードがハッシュまたは追加認証機能から生成されて、送信前にデータ部分集合と関連付けられるとよい。この認証実施形態は図７ａに図示されている。
【００９４】
分割手順の逆で、データ部分集合Ａ，Ｂが組み合わされてオリジナル音声データが形成されるとよい。部分集合または要素Ａ，Ｂのいずれかが消失する、受信した送信に欠損している、またはハッシング照合試験を通過しない場合には、上述した記憶データの検索と同じような方法で欠損データを再生成するのにパリティデータＰが使用されるとよい。そのため、チャネルＣ１，Ｃ２，Ｃ３のうち一つのみを受信している傍受者は、音声データを再構築できない。そのため、より安全であるばかりでなく、より信頼できる通信システムおよび方法が、こうして得られるのである。各チャネルのモード、タイプ、または周波数を変えることにより、安全性がさらに高められる。図７ａに示された認証実施形態では、ハッシュ関数認証検査によって整合性が得られるとよい。
【００９５】
図８は、図７に示されたものと類似したさらなる実施形態の概略図を示している。しかし、このさらなる実施形態では、送信前にデータ分割のさらなるカスケードまたは層（または同等物）が実行される。音声または他の送信データを再構築するのに、追加レベルの組み換えが使用されてもよい。ルックアップテーブルまたは同様のマッピング技術を用いて、データがオリジナルデータ位置と直接にマッチングされてもよい。図８に示された例では、このさらなるデータ分割およびパリティデータ生成のカスケードは、各データ部分集合とパリティデータとを通信する９本のチャネルを必要とする。このような付加的なカスケードは、データ消失に対してさらなる回復力を与える。チャネル５から送信されたデータは消失してもよく、データは完全に再構築可能（無損失）である。さらなる回復力を提供する追加カスケードが達成されてもよい。上記のデータ記憶例と全く同じように、他の数のデータチャネルが使用されてもよい。例を挙げると、各カスケードにおいてデータが３、４、または５方向以上に分割されてもよい。必要レベルの安全性または信頼性に応じて、さらなるカスケードレベルが実行されるとよい。こうして、利用可能なチャネル容量が満たされるが、こうする際に、各チャネルの出力要件を低下させて、同じデータ消失率を維持する（シャノンまたは雑音チャネルコード化定理）。
【００９６】
図８ａに示されているように、送信されるデータ部分集合および／またはパリティデータ（カスケードの一番下のレベル）の各々またはそのいずれかに、ハッシュ関数が適用される。ハッシュコードが受信器に送信されるとよい。
【００９７】
通信システムは、付加的な安全性または機能性の層を包含してもよい。データを受信する通信デバイス５１０は、どの特定チャネルによってどのデータ部分集合およびパリティデータが送信されるかについての情報を要求するとよい。図８および８ａに示された例では、チャネルＣ１はデータ部分集合ＡＡを送信するのに使用され、Ｃ２はＡＢに使用されるなどであるが、いかなる組み合わせが使用されてもよい。例を挙げるとチャネルおよびデータ部分集合の特定の組み合わせを表すコードの送信により、送信の前または間に、通信デバイス５００，５１０の間でこのような情報が交換されるとよい。特定の組み合わせは、送信および受信の間に変化してよい。これは予め構成されるか予め決定された方法にしたがったものであっても、送信器および受信器を同期化させるように特定の現在の組み合わせが送信されてもよい。両方の通信デバイス５００，５１０が、同時に送受信を行っても単独で行ってもよい。
【００９８】
さらなる安全性予防措置として、基準ファイルに対する差分またはデルタデータとしてデータが記憶または送信されてもよい。そのため、データを検索または受信するには、基準ファイルへのアクセスまたはその情報が必要とされるとよい。
【００９９】
あるタイプのデータの送信または記憶に対して実用的または法的な制約がある場合に、このさらなる安全性予防措置が使用されるとよい。例を挙げると、銀行取引または守秘情報の記憶が特定の組織または現場に限定されるとよい。しかし、その消失の危険が低下するようにこれらのデータを記憶することが、やはり必要である。そのため、暗号化を用いても、上述したように、異なる記憶ロケーションにわたってこのようなタイプのデータを分散または送信することが可能でなくてもよい。基礎データではなく差分またはデルタデータを代わりに送信または分散することにより、この問題が対処されるとよい。この状況では、データ保護要件が満たされ、消失または破壊に対してデータが保護されるとよい。
【０１００】
例えば、このさらなる代替的手順の実例として、ファイルＡ（または信号Ａ）が、記憶または送信される必要のある基礎データであるとよい。ファイルＢは基準ファイルでよい。ファイルＡおよびファイルＢの比較は、ファイルＣを生成するＵＮＩＸｄｉｆｆ、ｒｄｉｆｆ、ｒｓｙｎｃ手順と類似した比較関数を用いて行われるとよい。
【０１０１】
さらなる代替例では、例えば、おそらくバイト単位またはビット単位でＸＯＲ関数をファイルＡおよびファイルＢに適用することにより、差分ファイルが生成されるとよい。
【０１０２】
そのため、ファイルＣは、ファイルＡとファイルＢとの間の差分を表すか符号化したものである。ファイルＡは、ファイルＢについての知識があるかアクセスが可能でなければファイルＣから再生成されない。ファイルＢは多様な形を取り、ランダムに生成されたストリング、ドキュメント、音声ファイル、画像ファイル、書籍のテキスト、または他の周知であるか生成されたデータ集合でよい。周知のデータファイル（例えばよく周知の歌のＭＰ３ファイル）を使用する利点は、ユーザのコンピュータが消失、盗難、または破壊された場合に、周知で公共利用可能な基準ファイルの追加コピーを取得することで基礎データが再生成されることである。ユーザは、使用したのがどの特定ファイル（おそらくユーザのお気に入りの歌のＭＰ３ファイル）であったかを覚えているだけでよい。ユーザには何百万ものオプションが用意されているので、周知のデータファイルが使用される時でも比較的高い安全性が維持される。
【０１０３】
ファイルＣからファイルＡを再生成するため、差分またはデルタファイルＣを基準ファイルＢに適用するのに関数が使用されるとよい。差分またはデルタファイルＣがどのように生成および符号化されたのかに応じて、ファイルＡを再生成する際には様々な方法が使用されるとよい。ＸＯＲの例では、さらなるＸＯＲ関数がファイルＣおよびＢに適用されてファイルＡが再生されるとよい。これは例えばバイト単位またはビット単位で行われるとよい。このファイルＡおよびＢは、おそらく異なるサイズであろう。ファイルＡがファイルＢより小さいと、各バイトまたはファイルチャンクが比較される時に手順が停止するだけである。ファイルＡがファイルＢより大きいと、ファイルＡの各バイトが比較されるまでファイルＢの多数のコピーが使用される。他の変形、差分法、および比較関数が使用されてもよい。
【０１０４】
差分またはデルタファイル（またはデータストリーム）が生成されると、これは上述したオリジナルデータとして使用され、適宜（音声データなどとして）記憶または送信される。送受信実施形態では、差分データはデータストリームとして生成される、つまりリアルタイムで送信、受信、符号化または復号が行われる。言い換えると、上述した方法にしたがってデータ部分集合が分散式に記憶されるか送信されるように、生成されたパリティデータとともに、差分データがデータ部分集合に分割されるのである。
【０１０５】
差分データの形のデータストリームが送信される際には、基準ファイル（Ｂ）が再び使用されてデータストリームをリアルタイムで順次符号化する。万一、データストリームが基準ファイルの長さを超えた場合には、送信が終了するまで基準ファイルが再使用される。例えば、音声通信では、送信が開始するたびに、デジタル化音声または音声データストリームとの比較のために基準ファイルの冒頭が使用されて、差分データストリームが生成される。代替的に、新たな送信のたびに基準ファイルで使用された最終点から継続することにより、再使用が軽減されてもよい。この代替例は、安全性をさらに高める。
【０１０６】
別々の実施形態が説明されたが、とりわけデータの取り扱いに関してこれらの実施形態の特徴が互換性を持つとよいことに注意すべきである。さらに、送受信実施形態に関して説明された特徴が記憶実施形態に使用されても、その逆であってもよい。
【０１０７】
当業者には認識されるように、添付の請求項に規定された本発明の範囲から逸脱することなく上記の実施形態の詳細が変えられてもよい。
【０１０８】
例えば、ハードディスク、フラッシュＲＡＭ、ウェブサーバ、ＦＴＰサーバ、およびネットワークファイルサーバまたはこれらの混合など、多様なタイプの記憶媒体にデータが記憶されてもよい。３回反復される（Ａ，Ｂ，Ｃ）ごとに２個のデータ部分集合（Ａ，Ｂ）および単一のパリティデータブロック（Ｐ）に分割されるものとしてファイルが説明されているが、４個（Ａ〜Ｄ）またはそれ以上のデータ部分集合が生成されてもよい。
【０１０９】
パリティデータは例においてはＸＯＲ関数から生成されるものとして説明されているが、他の関数が使用されてもよい。例を挙げると、ハミング、リード・ソロモン、ゴレイ、リード・マラー、または他の適当なエラー訂正コードが使用されるとよい。
【０１１０】
同じハードディスクドライブまたはクラスタの中でありながら物理的に別々であるか論理的に別々のロケーションに、データ部分集合が記憶されてもよい。
【０１１１】
図７，７ａ，８，８ａを参照して説明された通信システムは、図３ｂおよび３ｃを参照して説明されたマッチング方法を使用してもよい。言い換えると、音声または他の送信データのマップデータ要素が、データストリーム内での位置に基づいて送信手段またはチャネルにマッピングまたはマッチングされるとよい。
【０１１２】
マッチング実行例（図３ｂおよび３ｃを参照して実施形態が説明されたもの）は、上述した認証、ハッシング、および暗号化特徴を使用してもよい。さらに、一つの実施形態または例に特に関連して説明された特徴のいずれかが、適切な変更を加えることにより他のいずれかの実施形態で使用されてもよい。
【０１１３】
各記憶ロケーションが多数のデータ要素位置に割り当てられてもよく、例えば記憶ロケーションＳ１が第１および第３データ要素のすべてを記憶してもよい。
【０１１４】
上記の実施形態の特徴についての多くの組み合わせ、変形、または変更は、当業者にとって容易に明らかになり、本発明の一部を成すものとする。
【図１】
2013521555.tif 000003
【図１ａ】
2013521555.tif 000004
【図２】
2013521555.tif 000005
【図２ａ】
2013521555.tif 000006
【図３】
2013521555.tif 000007
【図３ａ】
2013521555.tif 000008
【図３ｂ】
2013521555.tif 000009
【図３ｃ】
2013521555.tif 000010
【図４】
2013521555.tif 000011
【図４ａ】
2013521555.tif 000012
【図５】
2013521555.tif 000013
【図６】
2013521555.tif 000014
【図７】
2013521555.tif 000015
【図７ａ】
2013521555.tif 000016
【図８】
2013521555.tif 000017
【図８ａ】
2013521555.tif 000018
【国際調査報告】
2013521555.tif 000019
2013521555.tif 000020
2013521555.tif 000021
2013521555.tif 000022
2013521555.tif 000023