(57)【要約】  本発明は（ｋ，ｒ）個のデータを符号化する方法及びデータを再構築する方法に関する。本方法は、以下のステップ、すなわち−  初期データａをｋ個のデータブロックａｉに分割するステップと、−  ｋ個のデータブロックをデータブロックのｒ−１個の部分集合Ｓｊにグループ化するステップと、−  各部分集合Ｓｊ毎に、前記部分集合Ｓｊに割り当てられたデータブロックの一次結合として定義される一次関数ｇｊ（ａ）を生成するステップと、−  ｋ個のデータブロックａｉの一次結合としての一次パリティ関数ｆ０（ａ）、及び各二次パリティ関数ｆｊ（ａ）が一次パリティ関数ｆ０（ａ）と一次関数ｇｊ（ａ）の和として定義されるｒ−１個の二次パリティ関数を含む、ｒ個のパリティ関数を生成するステップとを含む。
2021521701.tif 000002
【特許請求の範囲】
【請求項１】
（ｋ，ｒ）個のデータを符号化する方法であって、
−  初期データａを同一サイズのｋ個のデータブロックａｉに分割するステップ（３０２）と、
−  前記ｋ個のデータブロックをデータブロックのｒ−１個の接続されていない部分集合Ｓｊにグループ化するステップ（３０４）と、
−  各部分集合Ｓｊ毎に、前記部分集合Ｓｊに割り当てられたデータブロックの一次結合として定義される一次関数ｇｊ（ａ）を生成するステップ（６０６）と、
−  前記ｋ個のデータブロックａｉの一次結合としての一次パリティ関数ｆ０（ａ）、及び各二次パリティ関数ｆｊ（ａ）が前記一次パリティ関数ｆ０（ａ）と一次関数ｇｊ（ａ）の和として定義されるｒ−１個の二次パリティ関数を含むｒ個のパリティ関数を生成するステップ（６０４）とを含む方法。
【請求項２】
前記ｒ個のパリティ関数を生成するステップ（３０８）が、ｒ個の符号化ベクトルを生成するステップ（３０６）を含み、前記符号化ベクトルが、
−  ｋ個の一次符号化係数ｃ０，１〜ｃ０，ｋを含む一次符号化ベクトルＣ０と、
−  各二次符号化ベクトルがｋ個の二次符号化係数ｃｊ，１〜ｃｊ，ｋを含むｒ−１個の二次符号化ベクトルＣｊ（１≦ｊ≦ｒ−１）とを含む、請求項１に記載の方法。
【請求項３】
各一次符号化係数ｃ０，ｉが非ゼロ乱数に対応し、二次符号化係数ｃｊ，ｉが前記データブロックａｉが前記部分集合Ｓｊに属するか否かに応じて非ゼロ又はゼロ乱数に対応している、請求項２に記載の方法。
【請求項４】
前記一次関数ｇｊ（ａ）を生成するステップが、前記ｋ個のデータブロック（ａ１，．．．，ａｋ）及び前記二次符号化ベクトルＣｊの前記ｋ個の二次符号化係数ｃｊ，１〜ｃｊ，ｋから一次結合を生成するステップを含む、請求項３に記載の方法。
【請求項５】
ｋ＝１０且つｒ＝４である、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
ｋ＋ｒ個のデータを記憶する方法であって、ｋ個のシステム化記憶装置Ｎｉ，ｉ∈｛１，．．，ｋ｝にｋ個のデータブロックａｉ、及びｒ個のパリティ記憶装置Ｎｉ，ｉ∈｛ｋ＋１，．．，ｋ＋ｒ｝に、ｒ個のパリティ関数であって請求項１〜５のいずれか１項に記載のデータ符号化方法に従い取得されたｒ個のパリティ関数を記憶するステップを含む少なくとも１個のステップを含む方法。
【請求項７】
請求項１〜５のいずれか１項に記載のデータ符号化方法のステップの実行に適した手段を含む、データ符号化装置。
【請求項８】
ｋ個のデータブロックａｉをｋ個のシステム化記憶装置Ｎｉ，ｉ∈｛１，．．，ｋ｝に、及びｒ個のパリティ関数ｆｊ（ａ）をｒ個のパリティ記憶装置Ｎｉ，ｉ∈｛ｋ＋１，．．，ｋ＋ｒ｝に記憶している複数の記憶装置のうち１個の記憶装置のコンテンツを再構築する方法であって、前記ｋ個のデータブロック及びｒ個のパリティ関数が、請求項１〜５のいずれか１項に記載の方法に従い取得され、前記再構築方法が少なくとも以下を含むステップ、すなわち、
−  前記コンテンツを再構築する前記記憶装置がシステム化又はパリティ記憶装置であるか否かを判定するステップ（７００）と、
−  前記装置がシステム化記憶装置Ｎｉ，ｉ∈｛１，．．，ｋ｝である場合、
−  前記装置のデータブロックがどのデータ部分集合Ｓｊに属するかを判定し（７１６）、
−  前記パリティ記憶装置ｋ＋１及びｋ＋１＋ｊに記憶されている前記一次及び二次パリティ関数を取得し（７１８）、
−  前記部分集合Ｓｊに関連付けられた前記一次関数ｇｊ（ａ）を計算し（７２０）、
−  前記ブロックａｉ以外の前記部分集合Ｓｊのデータブロックを取得して（７２２）、
−  前記システム化記憶装置Ｎｉ，ｉ∈｛１，．．，ｋ｝のコンテンツを再構築するステップ（７２４）と、
−  前記装置がパリティ記憶装置Ｎｉ，ｉ∈｛ｋ＋１，．．，ｋ＋ｒ｝である場合、前記記憶装置を識別する添え字ｉを判定して（７２６）、
−  前記添え字ｉがｋ＋１に等しい場合、
・添え字ｉ＝ｋ＋２の前記パリティ記憶装置及び前記部分集合Ｓ１の前記データブロックａｉに記憶されている前記二次パリティ関数ｆ１（ａ）を取得し（７２８）、
・前記部分集合Ｓ１に関連付けられた前記一次関数ｇ１（ａ）を計算して（７３０）前記一次パリティ関数ｆ０（ａ）を復号化して、
・添え字ｉ＝ｋ＋１の前記パリティ装置のコンテンツを再構築するステップと（７３２）、
−  前記添え字ｉがｋ＋１よりも大きい場合、
・添え字ｉ＝ｋ＋１の前記パリティ記憶装置及び前記部分集合Ｓｉ−ｋ＋１の前記データブロックａｉに記憶されている前記一次パリティ関数ｆ０（ａ）を取得し（７３４）、
・前記部分集合Ｓｉ−ｋ＋１に関連付けられた前記一次関数ｇｉ−ｋ＋１（ａ）を計算して（７３６）前記二次パリティ関数ｆｉ−ｋ＋１（ａ）を復号化して、
・添え字ｉ＞ｋ＋１の前記パリティ装置のコンテンツを再構築するステップ（７３８）とを含む方法。
【請求項９】
前記パリティ関数を取得するステップが、前記対応する記憶装置からデータ収集装置にデータを転送するステップを含む、請求項８に記載の方法。
【請求項１０】
ｉ∈｛１，．．，ｋ｝であるシステム化ノードｉを再構築すべく前記部分集合Ｓｊに関連付けられた前記一次関数ｇｊ（ａ）を計算するステップが、前記記憶装置Ｎｋ＋１＋ｊに記憶されている前記二次パリティ関数から前記記憶装置Ｎｋ＋１に記憶されている前記一次パリティ関数を減算するステップを含む、請求項８又は９に記載の方法。
【請求項１１】
ｉ＝ｋ＋１であるパリティノードｉを再構築すべく前記部分集合Ｓ１に関連付けられた前記一次関数ｇ１（ａ）を計算するステップが、前記部分集合Ｓ１のデータブロック及び前記符号化ベクトルＣ１から一次結合を生成するステップを含み、ｉ∈｛ｋ＋２，．．，ｋ＋ｒ｝であるパリティノードｉを再構築すべく前記部分集合Ｓｊに関連付けられた前記一次関数ｇｊ（ａ）を計算するステップが、前記部分集合Ｓｊのデータブロック及び前記符号化ベクトルＣｊから一次結合を生成するステップを含む、請求項８〜１０のいずれか１項に記載の方法。
【請求項１２】
前記システム化記憶装置の前記コンテンツを再構築するステップが、前記一次関数ｇｊ（ａ）から前記データブロックａｉを復号化するステップを含む、請求項８〜１１のいずれか１項に記載の方法。
【請求項１３】
ｉ＝ｋ＋１である前記パリティ記憶装置ｉの前記コンテンツを再構築するステップが、前記計算された一次関数ｇ１（ａ）から添え字ｉ＝ｋ＋１の前記パリティ記憶装置の前記二次パリティ関数を復号化するステップを含み、ｉ＞ｋ＋１である前記パリティ記憶装置ｉの前記コンテンツを再構築するステップが、前記計算された一次関数ｇｉ−ｋ＋１（ａ）から添え字ｉ＞ｋ＋１の前記パリティ装置の前記二次パリティ関数を復号化するステップを含む、請求項８〜１１のいずれか１項に記載の方法。
【請求項１４】
ｋ個のデータブロックａｉをｋ個のシステム化記憶装置Ｎｉ，ｉ∈｛１，．．，ｋ｝に、及びｒ個のパリティ関数ｆｊ（ａ）をｒ個のパリティ記憶装置Ｎｉ，ｉ∈｛ｋ＋１，．．，ｋ＋ｒ｝に記憶している複数の装置のうち１個の記憶装置のコンテンツを再構築する装置であって、前記ｋ個のデータブロック及びｒ個のパリティ関数が請求項１〜５のいずれか１項に記載の方法に従い取得され、前記装置が、記憶装置のコンテンツを再構築する請求項８〜１３のいずれか１項に記載の方法のステップの実行に適した手段を含む装置。
【請求項１５】
プログラムを含むコンピュータプログラム製品であって、前記プログラムが、請求項１〜５のいずれか１項に記載の方法のステップを実行可能にする符号命令を含み、及び／又は前記プログラムがコンピュータ上で実行された場合に請求項８〜１３のいずれか１項に記載の方法のステップを実行可能にする符号命令を含むコンピュータプログラム製品。
【請求項１６】
請求項７及び／又は請求項１４に記載の少なくとも１個の装置を含むＡＳＩＣ又はＦＰＧＡ型の集積回路。
【請求項１７】
分散記憶システムにおける請求項８〜１３のいずれか１項に記載のコンテンツ再構築方法の使用であって、前記分散記憶システムが請求項１〜５のいずれか１項に記載の符号化方法に従い符号化されたデータを記憶可能な複数のデータ記憶ノードを含む使用。
【請求項１８】
ローカル記憶システムにおける請求項８〜１３のいずれか１項に記載のコンテンツ再構築方法の使用であって、前記ローカル記憶システムが請求項１〜５のいずれか１項に記載の符号化方法に従い符号化されたデータを記憶可能なデータ記憶ディスクを含む使用。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ記憶システム及びそのようなシステムにおける故障管理の一般的な分野に関する。より具体的には、本発明は、故障の発生後に記憶システムの修復に必要となるデータ読み込み／書き込み動作の最適化、及び転送されるデータ量の最適化を可能にする、データの符号化及び復号化方法及び装置に関する。
【背景技術】
【０００２】
近年、ソーシャルネットワーク、電子メール、ファイル共有、及びビデオ共有等のアプリケーションの利用に起因してデジタルデータの量が顕著に増大している。従って、オンラインサービスを提供する企業は、数十ペタバイト（１ＰＢ＝１０１５バイト）のデータ量を管理する必要がある。毎年指数的に増大し続けるこれらのデータ量を高い信頼性で記憶する必要がある。
【０００３】
分散記憶システム（ＤＳＳ）は、開放的で信頼性の高い記憶ソリューションを提供すべく昨今広く利用されている。これらのアーキテクチャは、図１に示すように、データが分散して記憶されている複数の記憶ノード（１１０、１１２、１１４）を含んでいる。１個の記憶ノードは１個（１１２）又は複数個の記憶装置（１１０、１１４）を含んでいてよい。複数の記憶装置を含むノードの各記憶装置自体を記憶ノードと表記する。一般に、記憶装置は記憶ディスクである。コントローラ（１０２）は、通信ネットワーク（１０４）に結合されたコンピュータ（１０６）から受信したリクエストに基づくディスクの読み込み／書き込み動作を含むノードからの／ノードへの通信の管理を可能にする。
【０００４】
今日、ディスク、装置又は記憶ノードの故障は稀でなく、数千個のノードについて毎日平均数十回もの故障が報告されるのは普通である。分散記憶システムは、１個又は複数個のノード或いは記憶装置又はディスクが故障した場合に、データの保護を保証しなければならない。
【０００５】
データの信頼性及び利用可能性を保証すべく、標準的な実装において、故障時に消失したデータを取り出し可能にすべくデータの冗長性に基づくソリューションが組み込まれている。
【０００６】
記憶システムに信頼性を付与することを可能にするいくつかの方法を以下に列挙する。
【０００７】
複製は、最も広く利用されている方法の１つである。これは、複数の記憶ノードに跨る同一のデータブロックを複製するものである。一般に、同一のデータブロックはｎ個の異なるノードに記憶されているため、ｎ−１件の故障に耐えられるようになる。実際、各データブロックは３個の異なるノードに記憶されているため、２件の故障に耐えることが可能になる。たとえ複製が良好な故障耐性を提供するにせよ、３個のノードの場合に複製が２００％と推定される記憶オーバーヘッドが生じる短所がある。
【０００８】
消去符号。このアプローチは、公知のリードソロモン（ＲＳ）符号の使用に基づいている。各データファイルは、ｋ個のデータブロックに分割され、これにｒ個のパリティ機能ブロックが追加されてｋ＋ｒ個のデータブロックが生成され、且つタームコードＲＳ（ｋ，ｒ）が用いられる。ｋ＋ｒ個のデータブロックは、ｋ＋ｒ個の異なるノードに記憶され、このうちｋ個のノードはｋ個の元ブロックを記憶し、ｒ個のパリティノードはｒ個のパリティ機能ブロックを記憶する。符号ＲＳ（ｋ，ｒ）は二つの基本的特性を有している。すなわち、ｋ＋ｒ個のブロックのうち任意のｋ個のデータブロックが元のデータを再生成するのに充分であり、故障の種類に依らずｒ件の故障に耐えられる。実際には、符号ＲＳ（１０，４）の場合、各データファイルは１０個のブロックに分割されて４個のパリティ機能ブロックが生成されるため、４件の故障まで耐えることが可能になる。ＲＳ符号は、複製と比較してより良好な記憶効率を提供し、符号ＲＳ（１０，４）について記憶オーバーヘッドが４０％と評価される。
【０００９】
データ記憶システムにおいて、故障時には、データの再構築は、冗長ノードに記憶されているデータの読み込み、次いでネットワーク内で「プロバイダ」とも呼ばれるデータを供給しているノードから「新参者」とも呼ばれる新たな記憶ノードへのデータの転送を伴う。単一ノードの故障発生時において、複製の場合は単一のプロバイダだけが必要とされる場合も、符号ＲＳ（ｋ，ｒ）の場合にｋ個のプロバイダが必要となり、次いでｋ個のプロバイダからのネットワークを介したデータの転送が含まれる。単一の故障の修復は従って、数百テラバイト（ＴＢ）の読み込み及び送信を伴う可能性がある。また、帯域幅の観点からの修復及び読み出し／書き込みコストも顕著になり得る。
【００１０】
以下に列挙するいくつかのソリューションは、修復フェーズ中に必要とされる帯域幅、すなわち「帯域幅修復」を削減するものである。
【００１１】
再生成符号は一例である。文献「Ｎｅｔｗｏｒｋ  ｃｏｄｉｎｇ  ｆｏｒ  ｄｉｓｔｒｉｂｕｔｅｄ  ｓｔｏｒａｇｅ  ｓｙｓｔｅｍｓ」，Ａｌｅｘａｎｄｒｏｓ  Ｇ  Ｄｉｍａｋｉｓ，Ｐ  Ｂｒｉｇｈｔｅｎ  Ｇｏｄｆｒｅｙ，Ｙｕｎｎａｎ  Ｗｕ，Ｍａｒｔｉｎ  Ｊ  Ｗａｉｎｗｒｉｇｈｔ，ａｎｄ  Ｋａｎｎａｎ  Ｒａｍｃｈａｎｄｒａｎ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ５６（９）：４５３９−４５５１，２０１０に記述されているような主要なアイディアは、各ノードが、自身が利用できるデータブロックからのデータの一次結合を生成するものである。各プロバイダノードから転送されるデータの量は従って、各ノードに記憶されているデータの量よりも少なく、そのため修復に必要な帯域幅が削減される。しかし、再生成符号に関して、新ノードで取り出される情報は転送されたデータの一次結合であり、従って必ずしも消失したデータブロックに等しい訳ではない。
【００１２】
正確な再生成符号が、消失したものと全く同一のデータブロックを取り出すために提案されている。文献「Ｏｐｔｉｍａｌ  ｅｘａｃｔ−ｒｅｇｅｎｅｒａｔｉｎｇ  ｃｏｄｅｓ  ｆｏｒ  ｄｉｓｔｒｉｂｕｔｅｄ  ｓｔｏｒａｇｅ  ａｔ  ｔｈｅ  ＭＳＲ  ａｎｄ  ＭＢＲ  ｐｏｉｎｔｓ  ｖｉａ  ａ  ｐｒｏｄｕｃｔ−ｍａｔｒｉｘ  ｃｏｎｓｔｒｕｃｔｉｏｎ」，Ｒａｓｈｍｉ，Ｋｏｒｌａｋａｉ  Ｖｉｎａｙａｋ，Ｎｉｈａｒ  Ｂ．Ｓｈａｈ，  ａｎｄ  Ｐ．Ｖｉｊａｙ  Ｋｕｍａｒ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ５７（８）：５２２７−５２３９，２０１１に示すような主要なアイディアは、干渉アラインメントの概念を用いて不要なデータブロックを除去するものである。たとえ正確な再生成符号は修復用の帯域幅を大幅に削減可能にするにせよ、ディスク入出力（「Ｉ／Ｏオーバーヘッド」）のコストは最適化されない。実際に、単一の故障を修復するには、正確な再生成符号は全ての読み出し対象ノードに記憶されている全てのデータが読み込まれることを必要とする。
【００１３】
修復帯域幅及びディスク入出力双方のコストを削減するためのソリューションが提案されている。
【００１４】
例えば、文献「Ｈｉｅｒａｒｃｈｉｃａｌ  ｃｏｄｅｓ：Ｈｏｗ  ｔｏ  ｍａｋｅ  ｅｒａｓｕｒｅ  ｃｏｄｅｓ  ａｔｔｒａｃｔｉｖｅ  ｆｏｒ  ｐｅｅｒ−ｔｏ−ｐｅｅｒ  ｓｔｏｒａｇｅ  ｓｙｓｔｅｍｓ」，Ａｌｅｓｓａｎｄｒｏ  Ｄｕｍｉｎｕｃｏ  ａｎｄ  Ｅｒｎｓｔ  Ｂｉｅｒｓａｃｋ，Ｐ２Ｐ’０８，８ｔｈ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｃｏｍｐｕｔｉｎｇ，ｐａｇｅｓ  ８９−９８に示すような階層的符号を用いる主要なアイディアは、元の符号よりも小さい符号から特定のパリティ関数を階層的に生成するものである。階層的符号（ｋ，ｒ）は、単一の故障を修復するために
【数１】
2021521701.tif 000003
（ｋ／ｒ−１の整数部分）〜ｋ個のデータブロックを読んでダウンロードする必要がある。しかし、階層的符号は従来のＲＳ符号の全てのプロパティを維持する訳ではない。実際、階層的符号（ｋ，ｒ）はｒ件の故障のいずれにも耐えられない。従って同じ冗長性でも信頼性が低いことが分かる。
【００１５】
ヒッチハイカ符号は、ＲＳ符号と同じ特性を維持して、帯域幅及びディスクの入出力の観点から低いコストで故障の修復を実行可能にする符号である。「Ａ  ｈｉｔｃｈｈｉｋｅｒ’ｓ  ｇｕｉｄｅ  ｔｏ  ｆａｓｔ  ａｎｄ  ｅｆｆｉｃｉｅｎｔ  ｄａｔａ  ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｉｎ  ｅｒａｓｕｒｅ−ｃｏｄｅｄ  ｄａｔａ  ｃｅｎｔｅｒｓ」，ＫＶ  Ｒａｓｈｍｉ，Ｎｉｈａｒ  Ｂ  Ｓｈａｈ，Ｄｉｋａｎｇ  Ｇｕ，Ｈａｉｒｏｎｇ  Ｋｕａｎｇ，Ｄｈｒｕｂａ  Ｂｏｒｔｈａｋｕｒ，ａｎｄ  Ｋａｎｎａｎ  Ｒａｍｃｈａｎｄｒａｎ，ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ，４４（４）：３３１−３４２，２０１５に記述されている主要なアイディアは、単一の故障の修復に必要なデータブロックの個数を削減するものである。ヒッチハイカアプローチは、同一構造（ｋ，ｒ）を有する２個のＲＳサブ符号を考慮する。第２の符号及び第１の符号に依存する特定のパリティ関数は、第２のＲＳサブ符号内で生成される。これらのインターリーブされたパリティ関数によりデータブロック修復のために読み込まれて転送されるデータの量が削減可能になる。ヒッチハイカ符号（１０，４）により、修復帯域幅及びディスクの入出力コストの３０％〜３５％が削減可能になる。
【００１６】
以下の参照文献に帯域幅を削減するデータ符号化方法が提案されている。
−  Ｃｈｅｎｇ  Ｈｕａｎｇ  ｅｔ  ａｌ．：「Ｅｒａｓｕｒｅ  Ｃｏｄｉｎｇ  ｉｎ  Ｗｉｎｄｏｗｓ  Ａｚｕｒｅ  Ｓｔｏｒａｇｅ」，ＵＳＥ−ＮＩＸ，１１  Ａｐｒｉｌ  ２０１３（２０１３−０４−１１），ｐａｇｅｓ  １−１２，ＸＰ０６１０１３９４１。このＬＲＣ（ｋ，ｌ，ｒ）法は、記憶ノードに記憶されるローカルパリティ関数の生成に基づいている。しかし、ＬＲＣ符号はローカルパリティ関数の追加的な記憶に起因して記憶オーバーヘッドをもたらす。
−  Ｃｈｅｎｇ  Ｈｕａｎｇ  ｅｔ  ａｌ．：「Ｐｙｒａｍｉｄ  Ｃｏｄｅｓ：Ｆｌｅｘｉｂｌｅ  Ｓｃｈｅｍｅｓ  ｔｏ  Ｔｒａｄｅ  Ｓｐａｃｅｓ  ｆｏｒ  Ａｃｃｅｓｓ  Ｅｆｆｉｃｉｅｎｃｙ  ｉｎ  Ｒｅｌｉａｂｌｅ  Ｄａｔａ  Ｓｔｏｒａｇｅ  ｓｙｓｔｅｍｓ」，Ｐｒｏｃ．Ｓｉｘｔｈ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｎｅｔｗｏｒｋ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ２００７，ＩＥＥＥ，１  Ｊｕｌｙ  ２００７（２００７−０１−０７），ｐａｇｅｓ  ７９−８６，ＸＰ０３１１１９２８１，ＩＳＢＮ：９７８−０−７６９５−２９２２−６。この方法はＬＲＣ方法の代替方式を提案している。しかし、ＬＲＣ符号と同様に、ピラミッド符号は、従来の消去符号及びバビロン符号と比較して記憶オーバーヘッドをもたらす。
【００１７】
これらのアプローチでは、従来の消去符号と同じ記憶効率を維持しながら帯域幅の削減を可能にするヒッチハイカ符号、再生成符号、及び階層的符号とは逆に、従来の消去符号と同じ記憶効率が得られない。
【００１８】
新たな消去符号の定義に基づいて上で述べた方法とは逆に、Ｂｌａｕｍ  Ｍａｒｉｏらによる特許出願ＵＳ２０１６／２１１８６９Ａ１号が提案するソリューションは、目的関数として異なる符号間で切り替え可能な複数の消去符号が組み込まれた動的記憶システムを提案している。当該システムは、ファイルの参照頻度の関数として修復帯域幅の削減又は記憶オーバーヘッドの削減のどちらかを決定する。当該システムは特に２個の符号すなわち（上述の）ＬＲＣ及び「プロダクト符号」（ＰＣ）をサポートする。
【００１９】
１個以上のデータ記憶要素の故障に際して消失又は損傷したデータを、従来の消去符号と同じ記憶効率を維持しながら再構築するデータ符号化／復号化ソリューションに対するニーズがあり、且つ修復帯域幅コスト及びディスク入出力コストの観点から高まっている。
【００２０】
更に、ＳＳＤ（固体ドライブ）ディスクの出現に伴い、記憶要素は益々高速化しており、各ディスクは読み出しモードで毎秒数十ギガバイトを生成することができる。記憶要素を接続するインターフェースのビットレートは従って特に重要であり、記憶システムのボトルネックとなる。従って、再構築に際して交換されるフローの削減が特に重要である。従って、故障の後で記憶システムを修復する際に転送されるデータの量の最適化を可能にするソリューションに対するニーズがある。
【００２１】
本発明は、上述の各種のニーズについて述べる。
【先行技術文献】
【特許文献】
【００２２】
【特許文献１】米国特許出願公開第２０１６／２１１８６９号明細書
【非特許文献】
【００２３】
【非特許文献１】「Ｎｅｔｗｏｒｋ ｃｏｄｉｎｇ ｆｏｒ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ｓｙｓｔｅｍｓ」，Ａｌｅｘａｎｄｒｏｓ Ｇ Ｄｉｍａｋｉｓ，Ｐ Ｂｒｉｇｈｔｅｎ Ｇｏｄｆｒｅｙ，Ｙｕｎｎａｎ Ｗｕ，ＭａｒｔｉｎＪ Ｗａｉｎｗｒｉｇｈｔ，ａｎｄ Ｋａｎｎａｎ Ｒａｍｃｈａｎｄｒａｎ，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ ５６（９）：４５３９−４５５１，２０１０
【非特許文献２】「Ｏｐｔｉｍａｌ ｅｘａｃｔ−ｒｅｇｅｎｅｒａｔｉｎｇ ｃｏｄｅｓ ｆｏｒ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ａｔ ｔｈｅ ＭＳＲ ａｎｄ ＭＢＲ ｐｏｉｎｔｓ ｖｉａ ａ ｐｒｏｄｕｃｔ−ｍａｔｒｉｘ ｃｏｎｓｔｒｕｃｔｉｏｎ」，Ｒａｓｈｍｉ，Ｋｏｒｌａｋａｉ Ｖｉｎａｙａｋ，Ｎｉｈａｒ Ｂ．Ｓｈａｈ， ａｎｄ Ｐ．Ｖｉｊａｙ Ｋｕｍａｒ，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ ５７（８）：５２２７−５２３９，２０１１
【非特許文献３】「Ｈｉｅｒａｒｃｈｉｃａｌ ｃｏｄｅｓ：Ｈｏｗ ｔｏ ｍａｋｅ ｅｒａｓｕｒｅ ｃｏｄｅｓ ａｔｔｒａｃｔｉｖｅ ｆｏｒ ｐｅｅｒ−ｔｏ−ｐｅｅｒｓｔｏｒａｇｅ ｓｙｓｔｅｍｓ」，Ａｌｅｓｓａｎｄｒｏ Ｄｕｍｉｎｕｃｏ ａｎｄ Ｅｒｎｓｔ Ｂｉｅｒｓａｃｋ，Ｐ２Ｐ’０８，８ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ Ｃｏｍｐｕｔｉｎｇ，ｐａｇｅｓ ８９−９８
【非特許文献４】「Ａ ｈｉｔｃｈｈｉｋｅｒ’ｓ ｇｕｉｄｅ ｔｏ ｆａｓｔ ａｎｄ ｅｆｆｉｃｉｅｎｔ ｄａｔａ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｉｎ ｅｒａｓｕｒｅ−ｃｏｄｅｄ ｄａｔａ ｃｅｎｔｅｒｓ」，ＫＶ Ｒａｓｈｍｉ，Ｎｉｈａｒ Ｂ Ｓｈａｈ，Ｄｉｋａｎｇ Ｇｕ，Ｈａｉｒｏｎｇ Ｋｕａｎｇ，Ｄｈｒｕｂａ Ｂｏｒｔｈａｋｕｒ，ａｎｄ Ｋａｎｎａｎ Ｒａｍｃｈａｎｄｒａｎ，ＡＣＭ ＳＩＧＣＯＭＭ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｒｅｖｉｅｗ，４４（４）：３３１−３４２，２０１５
【非特許文献５】Ｃｈｅｎｇ Ｈｕａｎｇ ｅｔ ａｌ．：「Ｅｒａｓｕｒｅ Ｃｏｄｉｎｇ ｉｎ Ｗｉｎｄｏｗｓ Ａｚｕｒｅ Ｓｔｏｒａｇｅ」，ＵＳＥ−ＮＩＸ，１１ Ａｐｒｉｌ ２０１３（２０１３−０４−１１），ｐａｇｅｓ １−１２，ＸＰ０６１０１３９４１
【非特許文献６】Ｃｈｅｎｇ Ｈｕａｎｇ ｅｔ ａｌ．：「Ｐｙｒａｍｉｄ Ｃｏｄｅｓ：Ｆｌｅｘｉｂｌｅ Ｓｃｈｅｍｅｓ ｔｏ Ｔｒａｄｅ Ｓｐａｃｅｓ ｆｏｒ Ａｃｃｅｓｓ Ｅｆｆｉｃｉｅｎｃｙ ｉｎ Ｒｅｌｉａｂｌｅ Ｄａｔａ Ｓｔｏｒａｇｅ ｓｙｓｔｅｍｓ」，Ｐｒｏｃ．Ｓｉｘｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｎｅｔｗｏｒｋ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ ２００７，ＩＥＥＥ，１ Ｊｕｌｙ ２００７（２００７−０１−０７），ｐａｇｅｓ ７９−８６，ＸＰ０３１１１９２８１，ＩＳＢＮ：９７８−０−７６９５−２９２２−６
【発明の概要】
【発明が解決しようとする課題】
【００２４】
本発明は、転送されるデータの量、及び故障の後で記憶システムの修復に必要とされる読み込み／書き込み動作を最適化可能にするデータ符号化及び復号化方法及び装置を提案することにより、公知の技術の限界を克服することを目的とする。
【課題を解決するための手段】
【００２５】
有利には、本発明は、記憶効率及びｋ＋ｒ件の故障のうちｒ個の全てに耐えられる信頼性の特性を維持しながら、修復帯域幅及びディスク入出力コストの両方を削減可能にする。
【００２６】
本発明の１つの目的はデータ符号化方法に関するものである。特に（ｋ，ｒ）個のデータを符号化する方法を提案し、方法は、
−  初期データａをｋ個のデータブロックａｉに分割するステップと、
−  ｋ個のデータブロックをデータブロックのｒ−１個の部分集合Ｓｊにグループ化するステップと、
−  各部分集合Ｓｊ毎に、前記部分集合Ｓｊに割り当てられたデータブロックの一次結合として定義される一次関数ｇｊ（ａ）を生成するステップと、
−  ｋ個のデータブロックａｉの一次結合としての一次パリティ関数ｆ０（ａ）、及び各二次パリティ関数ｆｊ（ａ）が一次パリティ関数ｆ０（ａ）と一次関数ｇｊ（ａ）の和として定義されるｒ−１個の二次パリティ関数を含む、ｒ個のパリティ関数を生成するステップとを含んでいる。
【００２７】
修復帯域幅及びディスク入出力コストの両方を削減するソリューションを提案する。
【００２８】
例えば、文献「Ｈｉｅｒａｒｃｈｉｃａｌ  ｃｏｄｅｓ：Ｈｏｗ  ｔｏ  ｍａｋｅ  ｅｒａｓｕｒｅ  ｃｏｄｅｓ  ａｔｔｒａｃｔｉｖｅ  ｆｏｒ  ｐｅｅｒ−ｔｏ−ｐｅｅｒ  ｓｔｏｒａｇｅ  ｓｙｓｔｅｍｓ」，Ａｌｅｓｓａｎｄｒｏ  Ｄｕｍｉｎｕｃｏ  ａｎｄ  Ｅｒｎｓｔ  Ｂｉｅｒｓａｃｋ，Ｐ２Ｐ’０８，８ｔｈ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｃｏｍｐｕｔｉｎｇ，ｐａｇｅｓ  ８９−９８に示すような階層的符号を用いる主要なアイディアは、元の符号よりも小さい符号から特定のパリティ関数を階層的に生成するものである。階層的符号（ｋ，ｒ）は、単一の故障を修復するために
【数２】
2021521701.tif 000004
（ｋ／ｒ−１の整数部分）〜ｋ個のデータブロックを読んでダウンロードする必要がある。しかし、階層的符号は従来のＲＳ符号の全てのプロパティを維持する訳ではない。実際、階層的符号（ｋ，ｒ）はｒ件の故障のいずれにも耐えられない。従って同じ冗長性でも信頼性が低いことが分かる。
【００２９】
ヒッチハイカ符号は、ＲＳ符号と同じ特性を維持して、帯域幅及びディスクの入出力の観点から低いコストで故障の修復を実行可能にする符号である。「Ａ  ｈｉｔｃｈｈｉｋｅｒ’ｓ  ｇｕｉｄｅ  ｔｏ  ｆａｓｔ  ａｎｄ  ｅｆｆｉｃｉｅｎｔ  ｄａｔａ  ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｉｎ  ｅｒａｓｕｒｅ−ｃｏｄｅｄ  ｄａｔａ  ｃｅｎｔｅｒｓ」，ＫＶ  Ｒａｓｈｍｉ，Ｎｉｈａｒ  Ｂ  Ｓｈａｈ，Ｄｉｋａｎｇ  Ｇｕ，Ｈａｉｒｏｎｇ  Ｋｕａｎｇ，Ｄｈｒｕｂａ  Ｂｏｒｔｈａｋｕｒ，ａｎｄ  Ｋａｎｎａｎ  Ｒａｍｃｈａｎｄｒａｎ，ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ，４４（４）：３３１−３４２，２０１５に記述されている主要なアイディアは、単一の故障の修復に必要なデータブロックの個数を削減するものである。ヒッチハイカアプローチは、同一構造（ｋ，ｒ）を有する２個のＲＳサブ符号を考慮する。第２の符号及び第１の符号に依存する特定のパリティ関数は、第２のＲＳサブ符号内で生成される。これらのインターリーブされたパリティ関数によりデータブロック修復のために読み込まれて転送されるデータの量が削減可能になる。ヒッチハイカ符号（１０，４）により、修復帯域幅及びディスクの入出力コストの３０％〜３５％が削減可能になる。
【００３０】
以下の参照文献に帯域幅を削減するデータ符号化方法が提案されている。
−  Ｃｈｅｎｇ  Ｈｕａｎｇ  ｅｔ  ａｌ．：「Ｅｒａｓｕｒｅ  Ｃｏｄｉｎｇ  ｉｎ  Ｗｉｎｄｏｗｓ  Ａｚｕｒｅ  Ｓｔｏｒａｇｅ」，ＵＳＥ−ＮＩＸ，１１  Ａｐｒｉｌ  ２０１３（２０１３−０４−１１），ｐａｇｅｓ  １−１２，ＸＰ０６１０１３９４１。このＬＲＣ（ｋ，ｌ，ｒ）法は、記憶ノードに記憶されるローカルパリティ関数の生成に基づいている。しかし、ＬＲＣ符号は、ローカルパリティ関数の追加的な記憶に起因して記憶オーバーヘッドをもたらす。
−  Ｃｈｅｎｇ  Ｈｕａｎｇ  ｅｔ  ａｌ．：「Ｐｙｒａｍｉｄ  Ｃｏｄｅｓ：Ｆｌｅｘｉｂｌｅ  Ｓｃｈｅｍｅｓ  ｔｏ  Ｔｒａｄｅ  Ｓｐａｃｅｓ  ｆｏｒ  Ａｃｃｅｓｓ  Ｅｆｆｉｃｉｅｎｃｙ  ｉｎ  Ｒｅｌｉａｂｌｅ  Ｄａｔａ  Ｓｔｏｒａｇｅ  ｓｙｓｔｅｍｓ」，Ｐｒｏｃ．Ｓｉｘｔｈ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｎｅｔｗｏｒｋ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ２００７，ＩＥＥＥ，１  Ｊｕｌｙ  ２００７（２００７−０１−０７），ｐａｇｅｓ  ７９−８６，ＸＰ０３１１１９２８１，ＩＳＢＮ：９７８−０−７６９５−２９２２−６。この方法はＬＲＣ方法の代替方式を提案している。しかし、ＬＲＣ符号と同様に、ピラミッド符号は、従来の消去符号及びバビロン符号と比較して記憶オーバーヘッドをもたらす。
【００３１】
これらのアプローチでは、従来の消去符号と同じ記憶効率を維持しながら帯域幅の削減を可能にするヒッチハイカ符号、再生成符号、及び階層的符号とは逆に、従来の消去符号と同じ記憶効率が得られない。
【００３２】
新たな消去符号の定義に基づいて上で述べた方法とは逆に、Ｂｌａｕｍ  Ｍａｒｉｏらによる特許出願ＵＳ２０１６／２１１８６９Ａ１号が提案するソリューションは、目的関数として異なる符号間で切り替え可能な複数の消去符号が組み込まれた動的記憶システムを提案している。当該システムは、ファイルの参照頻度の関数として修復帯域幅の削減又は記憶オーバーヘッドの削減のどちらかを決定する。当該システムは特に２個の符号すなわち（上述の）ＬＲＣ及び「プロダクト符号」（ＰＣ）をサポートする。
【００３３】
１個以上のデータ記憶要素の故障に際して消失又は損傷したデータを、従来の消去符号と同じ記憶効率を維持しながら再構築するデータ符号化／復号化ソリューションに対するニーズがあり、且つ修復帯域幅コスト及びディスク入出力コストの観点から高まっていることが分かる。
【００３４】
本符号化方法の代替的又は組み合わされた実施形態によれば、
−  ｒ個のパリティ関数を生成するステップは、ｒ個の符号化ベクトルを生成するステップを含み、符号化ベクトルは、
−  ｋ個の一次符号化係数ｃ０，１〜ｃ０，ｋを含む一次符号化ベクトルＣ０と、
−  各二次符号化ベクトルがｋ個の二次符号化係数ｃｊ，１〜ｃｊ，ｋを含むｒ−１個の二次符号化ベクトルＣｊ（１≦ｊ≦ｒ−１）とを含み、
−  各一次符号化係数ｃ０，ｉは非ゼロ乱数に対応し、二次符号化係数ｃｊ，ｉは当該データブロックａｉが部分集合Ｓｊに属するか否かに応じて非ゼロ又はゼロ乱数に対応しており、
−  一次関数ｇｊ（ａ）を生成するステップは、ｋ個のデータブロック（ａ１，．．．，ａｋ）と二次符号化ベクトルＣｊの一次結合を生成するステップを含み、
−  ｋ＝１０且つｒ＝４である。
【００３５】
本発明のデータ符号化方法は、記憶装置の故障に続いて消失したデータを再構築する目的で複数の記憶装置にデータを分散させることに特に適している。また、ｋ＋ｒ個のデータを記憶する方法も請求項に記載しており、方法は、ｋ個のシステム化記憶装置Ｎｉ，ｉ∈｛１，．．，ｋ｝にｋ個のデータブロックａｉ、及びｒ個のパリティ記憶装置Ｎｉ，ｉ∈｛ｋ＋１，．．，ｋ＋ｒ｝に、ｒ個のパリティ関数であって請求項に記載のデータ符号化方法に従い取得されたｒ個のパリティ関数を記憶するステップを含む少なくとも１個のステップを含んでいる。
【００３６】
本発明はまた、請求項に記載のデータ符号化方法のステップを実行する手段を含むデータ符号化装置も対象とする。
【００３７】
本発明の別の目的は、請求項に記載の符号化方法により符号化されたデータを記憶する装置のコンテンツを再構築又は複製する方法に関する。特に、ｋ個のデータブロックａｉをｋ個のシステム化記憶装置Ｎｉ，ｉ∈｛１，．．，ｋ｝に、及びｒ個のパリティ関数ｆｊ（ａ）をｒ個のパリティ記憶装置Ｎｉ，ｉ∈｛ｋ＋１，．．，ｋ＋ｒ｝に記憶している複数の記憶装置のうち１個の記憶装置のコンテンツを再構築する方法を請求項に記載しており、前記ｋ個のデータブロック及びｒ個のパリティ関数は、請求項に記載のデータ符号化方法に従い取得され、当該再構築方法は少なくとも以下を含むステップ、すなわち、
−  コンテンツを再構築する記憶装置がシステム化又はパリティ記憶装置であるか否かを判定するステップと、
−  前記装置がシステム化記憶装置Ｎｉ，ｉ∈｛１，．．，ｋ｝である場合、
−  前記装置のデータブロックがどのデータ部分集合Ｓｊに属するかを判定し、
−  パリティ記憶装置ｋ＋１及びｋ＋１＋ｊに記憶されている一次及び二次パリティ関数を取得し、
−  部分集合Ｓｊに関連付けられた一次関数ｇｊ（ａ）を計算し、
−  ブロックａｉ以外の部分集合Ｓｊのデータブロックを取得して、
−  前記システム化記憶装置Ｎｉ，ｉ∈｛１，．．，ｋ｝のコンテンツを再構築するステップと、
−  前記装置がパリティ記憶装置Ｎｉ，ｉ∈｛ｋ＋１，．．，ｋ＋ｒ｝である場合、前記記憶装置を識別する添え字ｉを決定して、
−  添え字ｉがｋ＋１に等しい場合、
・添え字ｉ＝ｋ＋２のパリティ記憶装置及び部分集合Ｓ１のデータブロックａｉに記憶されている二次パリティ関数ｆ１（ａ）を取得し、
・部分集合Ｓ１に関連付けられた一次関数ｇ１（ａ）を計算して一次パリティ関数ｆ０（ａ）を復号化して、
・添え字ｉ＝ｋ＋１の前記パリティ装置のコンテンツを再構築するステップと、
−  添え字ｉがｋ＋１よりも大きい場合、
・添え字ｉ＝ｋ＋１のパリティ記憶装置及び部分集合Ｓｉ−ｋ＋１のデータブロックａｉに記憶されている一次パリティ関数ｆ０（ａ）を取得し、
・部分集合Ｓｉ−ｋ＋１に関連付けられた一次関数ｇｉ−ｋ＋１（ａ）を計算して二次パリティ関数ｆｉ−ｋ＋１（ａ）を復号化して、
・添え字ｉ＞ｋ＋１の前記パリティ装置のコンテンツを再構築するステップとを含んでいる。
【００３８】
コンテンツ再構築方法は、記憶装置の故障に続いて消失したデータのコンテンツの再構築に特に適している。
【００３９】
再構築方法の代替的又は組み合わされた実施形態によれば、
−  パリティ関数を取得するステップは、対応する記憶装置からデータ収集装置にデータを転送するステップを含み、
−  ｉ∈｛１，．．，ｋ｝であるシステム化ノードｉを再構築すべく部分集合Ｓｊに関連付けられた一次関数ｇｊ（ａ）を計算するステップは、記憶装置Ｎｋ＋１＋ｊに記憶されている二次パリティ関数から記憶装置Ｎｋ＋１に記憶されている一次パリティ関数を減算するステップを含み、
−  ｉ＝ｋ＋１であるパリティノードｉを再構築すべく部分集合Ｓ１に関連付けられた一次関数ｇ１（ａ）を計算するステップは、部分集合Ｓ１のデータブロック及び符号化ベクトルＣ１から一次結合を生成するステップを含み、
−  ｉ∈｛ｋ＋２，．．，ｋ＋ｒ｝であるパリティノードｉを再構築すべく部分集合Ｓｊに関連付けられた一次関数ｇｊ（ａ）を計算するステップは、部分集合Ｓｊのデータブロック及び符号化ベクトルＣｊから一次結合を生成するステップを含み、
−  前記システム化記憶装置のコンテンツを再構築するステップは、一次関数ｇｊ（ａ）からデータブロックａｉを復号化するステップを含み、
−  ｉ＝ｋ＋１である前記パリティ記憶装置ｉのコンテンツを再構築するステップは、計算された一次関数ｇ１（ａ）から添え字ｉ＝ｋ＋１の前記パリティ記憶装置の二次パリティ関数を復号化するステップを含み、
−  ｉ＞ｋ＋１である前記パリティ記憶装置ｉのコンテンツを再構築するステップは、計算された一次関数ｇｉ−ｋ＋１（ａ）から添え字ｉ＞ｋ＋１の前記パリティ装置の二次パリティ関数を復号化するステップを含んでいる。
【００４０】
本発明はまた、ｋ個のデータブロックａｉをｋ個のシステム化記憶装置Ｎｉ，ｉ∈｛１，．．，ｋ｝に、及びｒ個のパリティ関数ｆｊ（ａ）をｒ個のパリティ記憶装置Ｎｉ，ｉ∈｛ｋ＋１，．．，ｋ＋ｒ｝に記憶している複数の装置のうち１個の記憶装置のコンテンツを再構築する装置も対象としており、前記ｋ個のデータブロック及びｒ個のパリティ関数は請求項に記載の符号化方法に従い取得され、装置は、記憶装置のコンテンツを再構築する請求項に記載の方法のステップを実行する手段を含んでいる。
【００４１】
本発明は、ＡＳＩＣ又はＦＰＧＡ型の集積回路等のハードウェア及び／又ソフトウェア要素に組み込まれていてよい。
【００４２】
本発明はまた、請求項に記載の符号化方法のステップを実行可能にする符号命令を含む、及び／又は前記プログラムがコンピュータ上で実行された場合に請求項に記載のコンテンツ再構築方法のステップを実行可能にする符号命令を含むコンピュータプログラムにも関する。
【００４３】
本発明は、請求項に記載の符号化方法及び／又はコンテンツ再構築方法を実行する符号命令を含むプログラムが記憶されているプロセッサ可読記憶媒体として入手可能であってよい。
【００４４】
請求項に記載のコンテンツ再構築方法の有利な使用の１つは、請求項に記載の符号化方法に従い符号化されたデータを記憶可能な複数のデータ記憶ノードを含む分散記憶システムである。
【００４５】
請求項に記載のコンテンツ再構築方法の別の有利な使用は、請求項に記載の符号化方法に従い符号化されたデータを記憶可能なデータ記憶ディスクを含むローカル記憶システムである。
【００４６】
本発明の異なる態様及び利点を、以下の図面を参照しながら本発明の好適であるが非限定的な実装例の記述を精査することにより明らかになろう。
【図面の簡単な説明】
【００４７】
【図１】一実施形態において本発明を実装可能にする分散システム環境を示す。
【図２】本発明の一実施形態におけるデータの記憶の表現を示す。
【図３】一実施形態における本発明の符号化方法のステップを示す。
【図４】本発明の原理による、一次符号化ベクトルの生成を示す。
【図５】本発明の原理による、二次符号化ベクトルの生成を示す。
【図６】本発明の原理による、一次パリティ関数及び二次パリティ関数の生成を示す。
【図７ａ】本発明の原理によるシステム化パリティノードの再構築ステップを示す。
【図７ｂ】本発明の原理によるシステム化パリティノードの再構築ステップを示す。
【図７ｃ】本発明の原理によるシステム化パリティノードの再構築ステップを示す。
【図８】異なる符号の性能レベルを比較する表である。
【発明を実施するための形態】
【００４８】
以下の記述全体にわたり、表現「記憶ノード」は一般的な意味で用いられ、単一のディスクであるか、又はノードを形成する一群の記憶装置であるかに依らず、記憶実体を表記する。記述する本発明の複数の実施形態は、本発明を実装可能にする環境の一例に過ぎない図１に示す分散記憶システムの任意の変型例に適用できる。従って、本例は限定的でなく、記述する原理は、ファイルに又はオブジェクトに基づくか否かに依らず、クラウドシステム、データセンター、分散ファイルシステム等の、分散型であるか否かに依らない記憶システムが組み込まれた他の任意の環境にも適用できる。本発明はまた、「ディスクアレイ」等の非分散記憶システムに適用できる。更に、初期データから導出されたデータを記憶する記憶ノードを「システム化ノード」と呼び、パリティ関数を記憶する記憶ノードを「パリティノード」と呼ぶ。
【００４９】
本発明の原理を分かり易くすべく、符号（ｋ＝１０，ｒ＝４）の特定の例について最初に符号化方法を記述し、次いで任意の符号（ｋ，ｒ）に一般化される。
【実施例】
【００５０】
符号（１０，４）の例に関する符号化方法の記述
図２に、符号ｋ＝１０及びｒ＝４の例に基づく、本発明の符号化方法の適用によるデータの記憶の表現を示す。以下の記述において、本発明の符号化ステップは、表現「バビロン符号」又は「バビロン符号化」により表すことができる。初期データａがｋ＝１０個の部分（２００）又はａｉ，ｉ∈｛１，．．，１０｝と表記するデータブロック（ａ１，．．．，ａ１０）に分割され、これにデータ（ａ１，．．．，ａ１０）の一次結合であって以下にｆ０（ａ），ｆ１（ａ），ｆ２（ａ），ｆ３（ａ）又はｆ０（ａ）及びｆｊ（ａ），ｊ∈｛１，２，３｝と表記するｒ＝４個のパリティブロック又はパリティ関数ｆ０，ｆ１，ｆ２及びｆ３が追加される。パリティ関数ｆ０（ａ）は一次パリティ関数と呼ばれ、パリティ関数ｆｊ（ａ）は二次パリティ関数と呼ばれる。一次及び二次パリティ関数は、本発明のバビロン符号化（２０２）により生成されて記憶ノード（２０４）に記憶される。
【００５１】
システム化データブロックａ１〜ａ１０は（Ｎ１〜Ｎ１０）と表記する１０個の対応するシステム化記憶ノード（２０６）に記憶され、一次ｆ０（ａ）及び二次ｆ１（ａ）、ｆ２（ａ）、ｆ３（ａ）パリティ関数は、Ｎ１１〜Ｎ１４と表記する４個の対応するパリティ記憶ノード（２０８）に記憶される。
【００５２】
図３に、符号（ｋ＝１０，ｒ＝４）の一実施形態における本発明の符号化方法（３００）のステップを示す。本方法は第１のステップ（３０２）において初期データａを１０個のデータブロック（ａ１，．．．，ａ１０）に分割し、次いで次ステップ（３０４）において３個のデータ部分集合（Ｓ１，Ｓ２，Ｓ３）を生成可能にする。各データ部分集合は、生成された１０個のブロックからの異なるデータブロックを含んでいる。一実施形態において、２個の部分集合（Ｓ１，Ｓ２）は各々３個のデータブロックを含み、第３の部分集合（Ｓ３）は４個のデータブロックを含んでいる。第１の部分集合Ｓ１は、初期データから取得された先頭３ブロック（ａ１，ａ２，ａ３）を含み、第２の部分集合Ｓ２は次の３ブロック（ａ４，ａ５，ａ６）を含み、最後の部分集合Ｓ３は残った最後の４ブロック（ａ７，ａ８，ａ９，ａ１０）を含んでいる。
【００５３】
次のステップ（３０６）において、本方法は、４個のパリティノードに対応する長さ（ｋ＝１０）の４個の符号化ベクトルを生成可能にする。Ｃ０〜Ｃ４と表記された符号化ベクトルは、一次符号化ベクトルＣ０及び３個の二次符号化ベクトルＣ１、Ｃ２、Ｃ３に対応している。
【００５４】
図４及び５に、本発明の原理による符号化ベクトルの生成ステップを詳述する。
【００５５】
図４に、一実施形態における一次符号化ベクトルＣ０（４００）の生成を示す。一次符号化ベクトルＣ０は、１０個の一次符号化係数ｃ０，１〜ｃ０，１０を含み、各一次符号化係数ｃ０，ｉ（４０２−ｉ）が非ゼロ乱数（４０４−ｉ）に対応している。
【００５６】
図５に、一実施形態（５００）における二次符号化ベクトルＣｊ（１≦ｊ≦３）の生成を示す。各二次符号化ベクトルＣｊは、１０個の二次符号化係数ｃｊ，１〜ｃｊ，１０を含んでいる。
【００５７】
ベクトルＣｊを生成すべく、本方法は各ブロックａｉ毎に、ブロックａｉが部分集合Ｓｊに属するか否かを調べる（５０４−ｉ）。結果が肯定的な場合（ｙｅｓ分岐）、本方法は係数ｃｊ，ｉに対し非ゼロ乱数（５０６−ｉ）を関連付けられるようにする。ブロックａｉが部分集合Ｓｊに属しない（ｎｏ分岐）場合、本方法は係数ｃｊ，ｉに対しゼロ乱数（５０８−ｉ）を関連付けられるようにする。
【００５８】
例えば、符号化ベクトルＣ１を生成するために、本方法は各データブロックａ１，ａ２，．．ａ１０が部分集合Ｓ１に属するか否かを調べる。データブロックａ１，ａ２，ａ３は部分集合Ｓ１に属するため、本方法は従って係数ｃ１，１，ｃ１，２及びｃ１，３に対して非ゼロ乱数を生成する。データブロックａ４，．．．，ａ１０はＳ１に属しないため、本方法は係数ｃ１，４．．．ｃ１，１０に関連付けられたゼロ乱数を生成する。
【００５９】
従って、部分集合Ｓ１に対して、本方法は（ｃ１，１，ｃ１，２，ｃ１，３，０，０，０，０，０，０，０）に等しい符号化ベクトルＣ１を生成可能にし、ここでｃ１，１、ｃ１，２及びｃ１，３は非ゼロ乱数である。
【００６０】
部分集合Ｓ２に対して、本方法は（０，０，０，ｃ２，４，ｃ２，５，ｃ２，６，０，０，０，０）に等しい符号化ベクトルＣ２を生成可能にし、ここでｃ２，４、ｃ２，５及びｃ２，６は非ゼロ乱数である。
【００６１】
部分集合Ｓ３に対して、本方法は（０，０，０，０，０，０，ｃ３，７，ｃ３，８，ｃ３，９，ｃ３，１０）に等しい符号化ベクトルＣ３を生成可能にし、ここでｃ３，７、ｃ３，８，ｃ３，９及びｃ３，１０は非ゼロ乱数である。
【００６２】
図３に戻り、符号化ベクトルの生成ステップの後、本方法は、一次パリティ関数ｆ０（ａ）及び３個の二次パリティ関数ｆ１（ａ）、ｆ２（ａ）及びｆ３（ａ）を含むデータブロック（ａ１，．．．，ａ１０）の一次結合として４個のパリティ関数を生成する（３０８）ことを可能にする。
【００６３】
図６に、本発明の原理による一次パリティ関数ｆ０（ａ）及び二次パリティ関数ｆｊ（ａ）ｊ∈｛１，２，３｝の生成を詳述する。一次パリティ関数（６０２）は１０個のデータブロック（ａ１，．．．，ａ１０）の一次結合であり、パリティノードＮ１１に記憶されている。各データブロックａｉには一次符号化ベクトルＣ０（４００）の符号化係数ｃ０，ｉが関連付けられている。一次パリティ関数ｆ０（ａ）は、次式のように書くことができる。
−  ｆ０（ａ）＝ｃ０，１＊ａ１＋ｃ０，２＊ａ２＋ｃ０，３＊ａ３＋ｃ０，４＊ａ４＋ｃ０，５＊ａ５＋ｃ０，６＊ａ６＋ｃ０，７＊ａ７＋ｃ０，８＊ａ８＋ｃ０，９＊ａ９＋ｃ０，１０＊ａ１０
ここで係数ｃ０，１，ｃ０，２，．．．，ｃ０，１０は非ゼロ乱数である。
【００６４】
図６に示すように、３個の二次パリティ関数ｆｊ（ａ）（１≦ｊ≦３）（６０４）を生成するために、本方法は最初に３個の一次関数ｇｊ（ａ）（１≦ｊ≦３）（６０６）を生成する。各一次関数ｇｊ（ａ）は、１０個のデータブロック（ａ１，．．．，ａ１０）と符号化ベクトルＣｊ（１≦ｊ≦３）（５００）の一次結合である。
【００６５】
一次関数ｇ１（ａ）は１０個のデータブロック（ａ１，．．．，ａ１０）と符号化ベクトルＣ１の一次結合により得られ、次式のように書くことができる。
−  ｇ１（ａ）＝ｃ１，１＊ａ１＋ｃ１，２＊ａ２＋ｃ１，３＊ａ３
【００６６】
一次関数ｇ２（ａ）は１０個のデータブロック（ａ１，．．．，ａ１０）と符号化ベクトルＣ２の一次結合により得られ、次式のように書くことができる。
−  ｇ２（ａ）＝ｃ２，４＊ａ４＋ｃ２，５＊ａ５＋ｃ２，６＊ａ６
【００６７】
同様に、一次関数ｇ３（ａ）は１０個のデータブロック（ａ１，．．．，ａ１０）と符号化ベクトルＣ３の一次結合により得られ、次式のように書くことができる。
−  ｇ３（ａ）＝ｃ３，７＊ａ７＋ｃ３，８＊ａ８＋ｃ３，９＊ａ９＋ｃ３，１０＊ａ１０
【００６８】
関数ｇｊ（ａ）（１≦ｊ≦３）が生成されたならば、本方法は二次パリティ関数ｆ１（ａ）、ｆ２（ａ）及びｆ３（ａ）を生成可能にする。二次パリティ関数ｆ１（ａ）は、一次パリティ関数ｆ０（ａ）と一次関数ｇ１（ａ）の和により得られ、次式のように表すことができる。
−  ｆ１（ａ）＝ｆ０（ａ）＋ｇ１（ａ）
【００６９】
同様に、二次パリティ関数ｆ２（ａ）は一次パリティ関数ｆ０（ａ）と一次関数ｇ２（ａ）の和により得られ、次式のように表すことができる。
−  ｆ２（ａ）＝ｆ０（ａ）＋ｇ２（ａ）
【００７０】
同様に、二次パリティ関数ｆ３（ａ）は一次パリティ関数ｆ０（ａ）と一次関数ｇ３（ａ）の和により得られ、次式のように表すことができる。
−  ｆ３（ａ）＝ｆ０（ａ）＋ｇ３（ａ）
【００７１】
二次パリティ関数ｆ１（ａ）、ｆ２（ａ）、ｆ３（ａ）は、各パリティノードＮ１２、Ｎ１３及びＮ１４（２０８）に記憶されている。
【００７２】
有利には、一次関数ｇ１（ａ）、ｇ２（ａ）、ｇ３（ａ）及び一次パリティ関数ｆ０（ａ）は、互いに一次独立であるように生成される。更に、これらの関数の任意の２個の和も他の関数とは一次独立である。最後に、有利には、全てのデータブロックが一次独立であるため、バビロン符号は同じ特性をＲＳ符号として維持する。
【００７３】
図７ａ〜７ｃに、本発明の原理による、故障を検知して、システム化ノード及びパリティノードのコンテンツを再構築するステップを示す。
【００７４】
図７ａに示すように、本方法は、記憶システムの故障の検知に関する、故障の件数（７０４）を示す情報が利用できるときに開始される（７０２）。故障の件数が５以上である場合、修復方法は動作不可能なことがあり、システムに不具合がある（７０６）と考えられる。故障の件数が２〜４である場合、故障した２、３又は４個のノードは、消去符号又はリードソロモン型の公知の修復方法（７０８）に従い再構築することができる。
【００７５】
バビロン符号による請求項に記載の方法は、ローカル又は分散記憶システムの単一の記憶ノードが故障した場合に機能する。修復ステップは、他の記憶ノード内で、故障したノードに含まれていた消失データを取得して、新規な記憶ノードを同じデータで再構築可能にする。本方法は、故障が検知された後で、故障していた（７１０）ノードの性質、すなわちシステム化ノード又はパリティノードのいずれであるかを判定する。
【００７６】
本発明の原理の理解を容易にすべく、且つ限定することなく、本再構築方法について最初に符号（ｋ＝１０，ｒ＝４）の特定の例を挙げて記述し、次いで任意の符号（ｋ，ｒ）に一般化する。
【００７７】
符号（１０，４）を用いる記憶システムの例に関する本発明の復号化方法の記述
故障がシステム化ノードＮｉ，ｉ∈｛１，．．，１０｝、すなわちデータブロックａｉを記憶しているノードに関係している場合、再構築（７１２）は図７ｂに記述する方法のステップにより行われる。
【００７８】
故障がパリティノードＮｉ，ｉ∈｛１１，．．，１４｝、すなわちパリティ関数を記憶しているノードに関係している場合、再構築（７１４）は図７ｃに記述する方法のステップにより行われる。
【００７９】
図７ｂに、本発明のシステム化ノードの再構築ステップを示す。
【００８０】
本方法を説明するために、ノードＮ１に位置するブロックａ１が消失していて再構築する必要があると仮定する。第１のステップ（７１６）において、本方法は、故障したノードＮｉのデータａｉが属するデータの部分集合Ｓｊ，ｊ∈［１，２，３］を判定可能にする。本例では、データブロックａ１はデータ（ａ１，ａ２，ａ３）を含む部分集合Ｓ１に属する。次のステップ（７１８）において、本方法はノードＮ１１に記憶されている一次パリティ関数ｆ０（ａ）のデータの取得、及びノードＮ１２に記憶されている識別された部分集合Ｓ１の添え字に対応する二次パリティ関数ｆ１（ａ）のデータの取得を可能にする。表現「データを取得する」を用いて記憶ノードからデータ収集装置へのデータ転送動作を表す。データ収集装置は、ノードの再構築方法を実行可能な汎用記憶システムコントローラに組み込まれていてよい。データの取得はまた、記憶ノード及びデータ収集装置のメモリ要素との間の読み出し／書き込み動作を含んでいる。
【００８１】
データ収集ステップの後で、本方法は、取得されたデータからデータＳ１の部分集合に関連付けられた一次関数ｇ１（ａ）を計算することを可能にする（７２０）。一実施形態において、一次関数ｇｊ（ａ）は、ノードＮ１２に位置する二次パリティ関数ｆ１（ａ）からノードＮ１１に位置する一次パリティ関数ｆ０（ａ）を減算することにより得られる。
【００８２】
次のステップ（７２２）において、本方法は、消失したブロックａ１以外の部分集合Ｓ１のデータブロック（ａ２，ａ３）をロード可能にする。これらのデータを一次関数ｇ１（ａ）から減算することにより、データａ１が取得され、消失したデータブロックａ１の一次記憶ノードＮ１が再構築される（７２４）。
【００８３】
ａ１のノードの再構築は、１０個のブロックを要する従来のＲＳ符号とは異なり、４個のデータブロック｛ａ２，ａ３，ｆ０（ａ），ｆ１（ａ）｝だけを用いればよく、すなわち６０％の節減となる。同様に、ｉ∈｛１，２，３｝である任意のデータブロックａｉのシステム化ノードの再構築もまた、添え字ｉ∈｛１，２，３｝＼｛ｉ｝を有する、すなわち、故障したノードＮｉに対応する添え字ｉのデータブロック以外のデータブロックを用い、且つ一次パリティｆ０（ａ）及び二次パリティｆ１（ａ）関数のデータブロックを用いるため、４個のブロックだけを必要とする。
【００８４】
ｉ∈｛４，５，６｝である任意のデータブロックａｉのシステム化ノードの再構築は、添え字ｉ∈｛４，５，６｝＼｛ｉ｝を有するデータブロックを用い、且つ一次パリティｆ０（ａ）及び二次パリティｆ２（ａ）関数のデータブロックを用いるため４個のブロックを必要とする。
【００８５】
ｉ∈｛７，８，９，１０｝である任意のデータブロックａｉのシステム化ノードの再構築は、添え字ｉ∈｛７，８，９，１０｝＼｛ｉ｝を有するデータブロックを用い、且つ一次パリティｆ０（ａ）及び二次パリティｆ３（ａ）関数のデータブロックを用いるため、５個のブロックを必要とする。
【００８６】
図７ｃに、本発明のパリティノードの再構築ステップを示す。
【００８７】
ノードＮｉ，ｉ∈［１１，１４］は、一次ｆ０（ａ）及び二次ｆ１（ａ）、ｆ２（ａ）、ｆ３（ａ）パリティ関数を含んでいる。本方法は最初に、修復対象のノードが一次パリティ関数ｆ０（ａ）を含むＮ１１であるか否かを判定する（７２６）。ｙｅｓの場合、本方法はデータｆ１（ａ）とａ１、ａ２、ａ３を含む部分集合Ｓ１のデータをノードＮ１２，Ｎ１，Ｎ２及びＮ３から転送する（７２８）ことを可能にする。次のステップ（７３０）において、本方法は、データａ１、ａ２、ａ３を用いて一次関数ｇ１（ａ）の生成、次いでパリティ関数ｆ１（ａ）から一次関数ｇ１（ａ）を減算することによる一次パリティ関数ｆ０（ａ）の復号化を可能にする。本方法は次いでノードＮ１１を再構築可能にする。
【００８８】
ノードｉ，ｉ∈｛１，．．，１０｝と同様に，Ｎ１１の修復は、４個のデータブロック（ｆ１（ａ），ａ１，ａ２，ａ３）だけを必要とする。
【００８９】
ステップ（７２６）に戻り、修復対象のノードがｉ∈［１２，１４］のようなパリティノードＮｉである場合、本方法はパリティ関数ｆ０（ａ）を含むノードＮ１１のデータのロード（７３４）、及び部分集合Ｓｉ−１１のデータのロードを可能にする。次のステップ（７３６）において、本方法は、部分集合Ｓｉ−１１のデータを用いて一次関数ｇｉ−１１（ａ）の生成、及び一次パリティ関数ｆ０（ａ）と一次関数ｇｉ−１１（ａ）の和を求めることにより、パリティ関数ｆｉ−１１（ａ）の復号化を可能にする。本方法は次いで、ノードＮｉ，ｉ∈［１２，１４］の再構築（７３８）を可能にする。
【００９０】
従って、二次パリティ関数ｆ１（ａ）を含むノードＮ１２を再構築すべく、本方法はノードＮ１１のパリティ関数ｆ０（ａ）及び部分集合Ｓ１のデータをロードする（ノードＮ１からａ１、ノードＮ２からａ２及びノードＮ３からａ３）ことを可能にする。第１段階において、部分集合Ｓ１のデータａ１、ａ２、ａ３を用いてパリティ関数ｇ１（ａ）を生成する。次に、ｆ０（ａ）とｇ１（ａ）の和を求めることにより、二次パリティ関数ｆ１（ａ）を復号化してノードＮ１２を再構築する。
【００９１】
同様に、二次パリティ関数ｆ２（ａ）を含むノードＮ１３を再構築すべく、本方法はパリティ関数ｆ０（ａ）を含むノードＮ１１のデータ及び部分集合Ｓ２のデータのロードを可能にする。第１ステージにおいて、部分集合Ｓ２のデータａ４、ａ５、ａ６を用いてパリティ関数ｇ２（ａ）を生成する。次に、ｆ０（ａ）とｇ２（ａ）の和を求めることにより、二次パリティ関数ｆ２（ａ）を復号化してノードＮ１３を再構築する。
【００９２】
最後に、二次パリティ関数ｆ３（ａ）を含むノードＮ１４を再構築すべく、本方法はノードＮ１１に含まれるパリティ関数ｆ０（ａ）及び部分集合Ｓ３のデータをロード可能にする。第１ステージにおいて、部分集合Ｓ３のデータａ７、ａ８、ａ９、ａ１０を用いてパリティ関数ｇ３（ａ）を生成する。次に、ｆ０（ａ）とｇ３（ａ）の和を求めることにより、二次パリティ関数ｆ３（ａ）を復号化してノードＮ１４を再構築する。
【００９３】
ノードＮ１２及びＮ１３の修復は、各々４個のデータブロック｛ｆ０（ａ），ａ１，ａ２，ａ３｝及び｛ｆ０（ａ），ａ４，ａ５，ａ６｝だけを転送すればよく、ノードＮ１４の修復は５個のデータブロック｛ｆ０（ａ），ａ７，ａ８，ａ９，ａ１０｝の転送を必要とする点に注意されたい。
【００９４】
従って、有利には、請求項に記載の再構築方法は、任意のノードｉ∈｛１，．．，１４｝の再構築に４又は５個のデータブロックだけを必要とする。これによりＲＳ符号と比較して帯域幅及び入出力が５０％〜６０％削減可能になる。
【００９５】
本発明の符号化方法の一般的原理を任意の符号（ｋ，ｒ）について以下に記述する。
【００９６】
入力としてサイズＭのデータから開始して、本発明の一般的原理は、各ブロックのサイズがＭ／ｋであるｋ個のデータブロック（ａ１，．．．，ａｋ）にデータを分割する。ノードＮｉに記憶されている各データブロックａｉのサイズはｍ＝Ｍ／ｋに固定されている。
【００９７】
以下の表記は以下の記述に適している。
【数３】
2021521701.tif 000005
はＸの整数部を表し、
【数４】
2021521701.tif 000006
はＸの切り上げ整数部を表す。
【００９８】
バビロン符号化方法は、ｋ個のデータブロック（ａ１，．．．，ａｋ）をＳｊ，１≦ｊ≦ｒ−１と表記する（ｒ−１）個の部分集合（Ｓ１，Ｓ２，．．．，Ｓｒ−１）に分割するステップで開始される。ｋがｒ−１の倍数である場合、これらの部分集合は同一のサイズｋ／ｒ−１を有している。ｋがｒ−１の倍数でない場合、先頭ｒ−１−ｑ個の部分集合の各々はｔｆ個のデータブロックを含み、残りｑ個の部分集合はｔｃ個のデータブロックを含んでいて次式が成り立つ。
【数５】
2021521701.tif 000007
【００９９】
第１の部分集合Ｓ１は、（ａ１，．．，ａｔｆ）に属するデータブロックを含んでいる。ｊ番目の部分集合Ｓｊは（ａ（ｊ−１）ｔｆ＋１，．．．，ａｊｔｆ）に属するデータブロックを含んでいる（１≦ｊ≦ｒ−１）。
【０１００】
本方法の第２のステップは、一次符号化ベクトルＣ０及びｒ−１個の二次符号化ベクトルＣｊ（１≦ｊ≦ｒ−１）を含んでいるｒ個の符号化ベクトルを生成する。
【０１０１】
一次符号化ベクトルＣ０は、各一次符号化係数ｃ０，ｉが非ゼロ乱数に対応するｋ個の符号化係数ｃ０，１〜ｃ０，ｋを含んでいる。
【０１０２】
二次符号化ベクトルＣｊはｋ個の符号化係数ｃｊ，１〜ｃｊ，ｋを含んでいる。二次符号化ベクトルＣｊを生成すべく、本方法は、各ブロックａｉ毎に、ブロックａｉが部分集合Ｓｊに属するか否かを調べる。そうである場合、本方法は、係数ｃｊ，ｉに非ゼロ乱数を関連付けられるようにし、ブロックａｉが部分集合Ｓｊに属していない場合、本方法は係数ｃｊ，ｉにゼロ乱数を関連付けられるようにする。
【０１０３】
符号化ベクトルＣ０〜Ｃｒ−１の構造は以下のように表される。
ｃ０＝［ｃ０，１，ｃ０，２，．．，ｃ０，ｋ］
ｃ１＝［ｃ１，１，ｃ１，２，ｃ１，ｔｆ，．．．．，０，．．，０］
ｃ２＝［０，．．，０，ｃ２，ｔｆ＋１，．．，ｃ２，２ｔｆ，０，．．，０］
．．．
ｃｒ−ｑ＝［０，．．，０，ｃｒ−ｑ，（ｒ−ｑ−１）ｔｆ＋１，．．，ｃｒ−ｑ，（ｒ−ｑ）ｔｃ，０，．．，０］
ｃｒ−ｑ＋１＝［０，．．，０，ｃｒ−ｑ＋１，（ｒ−ｑ）ｔｃ＋１，．．，ｃｒ−ｑ＋１，（ｒ−ｑ）ｔｃ，０，．．，０］
．．．
ｃｒ−１＝［０，．．，．．，．．，０，ｃｒ−１，ｒｔｃ＋１，．．，ｃｒ−１，ｋ］
【０１０４】
符号化ベクトルの生成ステップの後、本方法は、データ（ａ１，．．．，ａｋ）の一次結合であって、一次パリティ関数ｆ０（ａ）及びｒ−１個の二次パリティ関数ｆ１（ａ），．．，ｆｒ−１（ａ）を含むｒ個のパリティ関数を生成可能にする。
【０１０５】
一次パリティ関数は、ｋ個のデータブロック（ａ１，．．．，ａｋ）の一次結合であって、添え字ｋ＋１、Ｎｋ＋１のパリティノードに記憶されている。各データブロックａｉには一次符号化ベクトルＣ０の符号化係数ｃ０，ｉが関連付けられている。一次パリティ関数ｆ０（ａ）は、次式のように書くことができる。
−  ｆ０（ａ）＝ｃ０，１＊ａ１＋ｃ０，２＊ａ２＋．．．．．．ｃ０，ｋ＊ａｋ
ここに係数ｃ０，１，ｃ０，２，．．．，ｃ０，ｋは非ゼロ乱数である。
【０１０６】
ｒ−１個の二次パリティ関数ｆｊ（ａ）（１≦ｊ≦ｒ−１）を生成すべく、本方法は最初にｒ−１個の一次関数ｇｊ（ａ）（１≦ｊ≦ｒ−１）の全てを生成可能にする。各一次関数ｇｊ（ａ）は、ｋ個のデータブロック（ａ１，．．．，ａｋ）と符号化ベクトルＣｊ（１≦ｊ≦ｒ−１）の一次結合である。一次関数ｇｊ（ａ）（１≦ｊ≦ｒ−１）が生成されたならば、本方法は、一次パリティ関数ｆ０（ａ）を一次関数ｇｊ（ａ）に加算することにより二次パリティ関数ｆｊ（ａ），１≦ｊ≦ｒ−１が得られるように、二次パリティ関数ｆ１（ａ），ｆ２（ａ）．．．ｆｒ−１（ａ）を生成可能にする。
−  ｆｊ（ａ）＝ｆ０（ａ）＋ｇｊ（ａ）
【０１０７】
本発明の符号化により生成されたデータブロック及びパリティ関数は、ローカル又は分散記憶システムの記憶ノードに記憶される。ｋ個のデータブロック（ａ１，．．．，ａｋ）は、ｋ個のシステム化ノードＮｉ，ｉ∈｛１，．．，ｋ｝に記憶され、パリティ関数により得られたｒ個のパリティブロックの各々は、以下の表に示すようにパリティノードＮｉ，ｉ∈｛ｋ＋１，．．，ｋ＋ｒ｝に記憶されている。
【０１０８】
【表１】
2021521701.tif 000008
【０１０９】
有利には、一次関数ｇｊ（ａ），１≦ｊ≦ｒ−１及び一次パリティ関数ｆ０（ａ）は互いに一次独立であるように生成される。更に、これらの関数のうち任意の２個の和もまた他の関数とは一次独立である。最後に、有利には、全てのデータブロックが一次独立であり、バビロン符号はＲＳ符号と同じ特性を維持している。
【０１１０】
本発明の再構築方法の一般的原理を以下に任意の符号（ｋ，ｒ）について記述する。再構築方法は、記憶システムの故障の検知に関する情報が利用可能な場合に開始される。本方法はノードのコンテンツを複製すべく開始することができる。故障発生時の再構築方法は、ローカル又は分散記憶システム内の単一の記憶ノードが故障した場合に機能する。修復ステップは、他の記憶ノード内で、故障したノードに含まれていた消失データの取得、及び同じデータを用いた新たな記憶ノードの再構築を可能にする。
【０１１１】
故障が検知された場合、本方法は故障したノードの性質、すなわちシステム化ノード又はパリティノードのいずれであるかを判定する。
【０１１２】
故障がシステム化ノードＮｉ，ｉ∈｛１，．．，ｋ｝、すなわちデータブロックａｉを記憶しているノードに関する場合、再構築は以下に記述するケース１に従い行われる。
【０１１３】
故障がパリティノードＮｉ，ｉ∈｛ｋ＋１，．．，ｋ＋ｒ｝、すなわちパリティ関数を記憶しているノードに関する場合、再構築は以下に記述するケース２に従い行われる。
【０１１４】
−  ケース１：ノードＮｉ，ｉ∈｛１，．．，ｋ｝の再構築
ノードＮｉに記憶されているａｉ∈Ｓｊ且つ（１≦ｊ＜ｒ）であるデータａｉ（１≦ｉ≦ｋ）の修復を考慮するに、本方法は最初に添え字ｋ＋１のノードＮ（ｋ＋１）及び添え字ｋ＋１＋ｊのノードＮ（ｋ＋１＋ｊ）に含まれるデータを転送可能にする。次に、添え字ｋ＋１のノードＮ（ｋ＋１）に記憶されているデータｆ０（ａ）を、添え字ｋ＋１＋ｊのノードＮ（ｋ＋１＋ｊ）に記憶されているデータｆｊ（ａ）から減算して、部分集合Ｓｊに関連付けられた一次関数ｇｊ（ａ）を復旧する。本方法は次いで、部分集合Ｓｊ＼｛ａｉ｝の（すなわちデータブロックａｉ以外の）データを転送可能にする。一次関数ｇｊ（ａ）の使用により、消失したデータａｉが復号化可能になる。ａｉの再構築に必要なデータブロックの個数は従って、ｉが先頭（ｒ−１−ｑ）個の部分集合に属する場合、（ｔｆ＋１）である。ｉが最後のｑ個の部分集合に属する場合、必要なデータブロックの総数は（ｔｃ＋１）である。
【０１１５】
−  ケース２：ノードＮｉ，ｉ∈｛ｋ＋１，．．，ｋ＋ｒ｝の再構築
前のケースと同様に、ノードＮｉ（ｋ＋１＜ｉ≦ｋ＋ｒ）を再構築すべく、本方法は添え字ｋ＋１のノードＮ（ｋ＋１）に記憶されているデータｆ０（ａ）及び部分集合Ｓｉ−ｋ＋１に位置するデータを転送可能にする。一次関数ｇｉ−ｋ＋１（ａ）は部分集合Ｓｉ−ｋ＋１のデータから得られる。次に、復号化は、一次関数ｆ０（ａ）及び一次関数ｇｉ−ｋ＋１（ａ）を用いて二次関数ｆｉ−ｋ＋１（ａ）（実際には、ｆｉ−ｋ＋１（ａ）＝ｆ０（ａ）＋ｇｉ−ｋ＋１（ａ））を取得することにより実行される。（ｉ−ｋ＋１）が先頭（ｒ−１−ｑ）個のブロックに属するならば、修復に（ｔｆ＋１）個のデータブロックを必要とする点に注意されたい。（ｉ−ｋ＋１）∈｛ｒ−ｑ，．．，ｒ−１｝ならば、修復に（ｔｃ＋１）個のブロックを必要とする。
【０１１６】
一次パリティ関数ｆ０（ａ）を含む添え字ｋ＋１のノードＮｋ＋１の特定のケースの場合、本方法は一次関数ｇ１（ａ）を生成すべく第１の部分集合Ｓ１を転送可能にする。本方法は次いで、二次パリティ関数ｆ１（ａ）を含む添え字ｋ＋２のノードＮｋ＋２からデータを転送可能にする。二次パリティ関数ｆ１（ａ）から一次関数ｇ１（ａ）を減算することにより、一次パリティ関数ｆ０（ａ）を復号化する（実際には、ｆ０（ａ）＝ｆ１（ａ）−ｇ１（ａ））。（ｔｆ＋１）個のデータブロックを用いることにより、一次パリティ関数ｆ０（ａ）を含む添え字ｋ＋１のノードＮｋ＋１のデータが取得される。
【０１１７】
一般に、再構築／修復のために転送及び読み出されるデータの平均値は、ノードの種類に依らず次式で与えられる。
【数６】
2021521701.tif 000009
【０１１８】
記述が値ｒ≧３を例として挙げている点に注意されたい。値ｒ＝１の場合、バビロン符号は従来のＲＳ符号として機能する。値ｒ＝２の場合、データは２個の部分集合Ｓ１及びＳ２に分割され、Ｓ１は先頭ｔｓ個のブロックを含み、Ｓ２は最後のｋ−ｔｓ個のブロックを含み、ここで
【数７】
2021521701.tif 000010
である。
【０１１９】
有利には、本発明の方法は再構築の処理に全てのノードを使用しなくて済むようにする。更に、再構築に寄与するノードは計算を実行する必要がなく、単に自身のコンテンツを復号化動作が実行されるデータ収集器に転送するだけでよい。データ収集器は、故障したノードを代替する新たな記憶ノードであってよい。
【０１２０】
更に有利には、バビロン符号化方法により、ｋ個のノードのデータブロックの全てが再構築に必要な行列に基づく方法と比較して再構築時間が削減される。
【０１２１】
図８は、異なる既知の符号の結果を本発明のバビロン符号により得られた結果と比較する性能レベルの比較表である。表（８００）において、第１列は比較された符号、すなわちＲＳ、再生器、精密再生器、階層的、ヒッチハイカ、及びバビロンの一覧を示す。
【０１２２】
全ての符号に対して、（ｋ＝１０，ｒ＝４）の構成を用いて符号化された同一サイズＭバイトのファイルを考察した。
【０１２３】
異なるパラメータ、すなわち修復に要する平均帯域幅（８０６）、ディスク入出力（８０８）及び故障耐性（８１０）に対して同一の記憶効率（７１％）の列（８０４）の各符号について評価が行われた。帯域幅及びディスク入出力は、元ファイルのサイズＭに対するパーセンテージとして表されている。表内のパーセンテージは、システム化ノード及びパリティノードの修復を考慮しながら計算された。
【０１２４】
結果は以下の通りである。
−  ＲＳ符号の場合、単一の故障の修復にＭバイトの読み出し及び転送を要する。これはファイルの下のサイズの１００％に等しい。
−  同一記憶効率の場合、再生器符号及び精密再生器符号が必要とする帯域幅が計算された。故障の修復に用いる帯域幅は平均３２．５％に等しい。しかし、ディスク入出力は最適化されていない。単一の故障を修復するには、再生器符号は、ノードに記憶されている全てのデータが転送される前に読み込まれることを必要とする。
−  階層的符号は、帯域幅及びディスク入出力の両方を最適化する。ネットワーク内で読み込まれて転送されるデータの量は３３．５７％に等しい。しかし、階層的符号はＲＳ符号と同レベルの故障耐性を維持しない。実際、階層的符号を用いてどの４件の故障にも耐えられない。
−  ヒッチハイカ符号は、ＲＳ符号と同レベルの故障耐性を維持しながら、帯域幅及びディスク入出力の両方の最適化を可能にする。この場合、読み込まれて転送されるデータの量は７６．４２％に等しい。
−  バビロン符号は、単一の故障を帯域幅及びディスク入出力の両方の観点から修復するのに元ファイルのサイズの平均４３．５７％を必要とする。バビロン符号はまた、１４個のノードのうち任意の４件の故障に耐えられるようにする。
【０１２５】
本発明は、ハードウェア及び／又はソフトウェア要素により実装できる。本発明は、コンピュータ可読媒体上のコンピュータプログラム製品として利用可能であってよい。媒体は、電子、磁気、光学又は電磁気であってよい。一実施形態において、本方法はコンピュータにより実装される。コンピュータプログラム製品について記述され、前記コンピュータプログラムは、前記プログラムがコンピュータ上で動作した際に本方法の１個以上のステップを実行可能にする符号命令を含んでいる。一実施形態において、本発明を実装する装置は、１個以上のプロセッサで動作した際に上述の複数の実施形態の機能を実行するコンピュータプログラム（すなわち実行可能な複数の命令）により符号化されたコンピュータ可読記憶媒体（ＲＡＭ、ＲＯＭ、フラッシュメモリ又は他のメモリ技術、例えばディスク媒体又は他の非一時的コンピュータ可読記憶媒体）を含んでいる。本発明の実装に適したハードウェアアーキテクチャの一例として、一装置は、中央演算処理装置又はマイクロプロセッサ（ＣＰＵすなわちＣｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔの略）が接続された通信バス（当該プロセッサは「マルチコア」又は「多コア」であってよい）、本発明の実施に必要なプログラムを格納可能な読み出し専用メモリ（ＲＯＭ）、上述のプログラムの実行中に生成及び変更された変数及びパラメータの格納に適したレジスタを含むランダムアクセスメモリ又はキャッシュメモリ（ＲＡＭ）、データの送受信に適した通信又はＩ／Ｏ（入出力）インターフェースを含んでいてよい。本発明が再プログラム可能な計算機（例：ＦＰＧＡ回路）上にインストールされた場合、対応するプログラム（すなわち一連の命令）は着脱可能な記憶媒体（例：ＳＤカード、又はハードディスク、例えばＳＳＤ等の大容量ストレージ）又は着脱不可能な、揮発性又は不揮発性記憶媒体に記憶することができ、記憶媒体はコンピュータ又はプロセッサにより一部又は全部が読み出し可能である。コンピュータ可読媒体は、搬送可能又は通信可能或いは移動可能又は送信可能であってよい（すなわち、２Ｇ、３Ｇ、４Ｇ、Ｗｉｆｉ、ＢＬＥ、光ファイバー又は他の通信ネットワークを介して）。動作時に、上述の機能の任意の１個を実行するコンピュータプログラムへの言及は、単一のホストコンピュータで動作するアプリケーションプログラムに限定されない。逆に、ここでは、用語「コンピュータプログラム」及び「ソフトウェア」を、本明細書に記述する技術の態様を実行させるべく１個以上のプロセッサをプログラムするのに使用できる任意の種類のコンピュータ符号（例：アプリケーションソフトウェア、ファームウェア、マイクロコード、又はウェブサービス或いはＳＯＡ等の、又はプログラムインターフェースＡＰＩを介した他の任意の形式のコンピュータ命令）に言及すべく、一般的な意味で用いている。コンピュータ手段又はリソースは特に、恐らくピアツーピア及び／又は可視化技術と合わせて、又はこれらに従い分散（「クラウドコンピューティング」）されていてよい。ソフトウェアコードは、単一の計算装置で提供されるか又は複数の計算装置（恐らく当該装置の環境でアクセス可能）に分散されているかに依らず、任意の適��なプロセッサ（例：マイクロプロセッサ）又はプロセッサコア或いは一組のプロセッサ上で実行することができる。セキュリティ技術（暗号のプロセッサ、認証、暗号化、チップカード等）を用いてもよい。
【図１】
2021521701.tif 000011
【図２】
2021521701.tif 000012
【図３】
2021521701.tif 000013
【図４】
2021521701.tif 000014
【図５】
2021521701.tif 000015
【図６】
2021521701.tif 000016
【図７ａ】
2021521701.tif 000017
【図７ｂ】
2021521701.tif 000018
【図７ｃ】
2021521701.tif 000019
【図８】
2021521701.tif 000020
【国際調査報告】
2021521701.tif 000021
2021521701.tif 000022
2021521701.tif 000023
2021521701.tif 000024
2021521701.tif 000025
2021521701.tif 000026