(57)【要約】拡張可能で耐障害性の記憶システムを構成するための方法。本方法には、数Ｄの記憶要素をまとめて記憶システムを形成する段階であって、Ｄが２以上である段階と、表登録項目が含まれる記憶領域割当て表を構築する段階と、各記憶要素に対して、記憶システム内における冗長データの配置に関する制約条件に依存する利用可能容量を演算する段階と、利用可能容量を合計して、記憶システム用の総利用可能容量を形成する段階と、記憶領域割当て表の表登録項目を割り当て、記憶要素の内の１つを各々識別する段階と、が含まれる。本方法において、各記憶要素の利用可能容量は、記憶システムの一部として用いられる場合、その有効記憶容量であり、記憶システムを形成するＤ個の記憶要素の全てが、同じ利用可能容量を有しておらず、更に、記憶要素の１つを識別する全表登録項目の割合は、総利用可能容量の内のその割合に依存する。データブロックを符号化して、偶発的又は故意の改変にもかかわらず、それを正確に格納又は送信させるための方法。本方法には、１より大きい数ｎの初期構成要素を構築する段階であって、それらは、各々ブロックから導出され、また、それらは、各々ブロックより小さい段階と、初期構成要素を組み合わせて、１より大きい数ｍの新構成要素を構築する段階とを含む。本方法において、新しい各構成要素は、それを生成するために組み合わせられた初期構成要素のサイズの和より小さく、ブロックは、初期構成要素及び新構成要素から選択された任意の組のｎ個の異なる構成要素から再構築することが可能であり、更に、初期構成要素から選択されたｎ個の異なる構成要素と新構成要素の組は、ｎ個の初期構成要素の組より冗長なブロック情報を含む。
2009532812.tif 000002
【特許請求の範囲】
【請求項１】
拡張可能な耐障害性の記憶システムを構成するための方法であって、
Ｄが２以上であるとき、Ｄ個の記憶要素をまとめて、前記記憶システムを形成する段階と、
表登録項目が含まれる記憶領域割当て表を構築する段階と、
前記各記憶要素に対して、前記記憶システムにおける冗長データの配置に関する制約条件に依存した利用可能容量を計算する段階と、
前記利用可能容量を合計して、前記記憶システムの総利用可能容量を形成する段階と、
前記記憶領域割当て表の前記表登録項目を前記記憶要素の内の１つの各識別子に割り当てる段階とを備え、
前記各記憶要素の前記利用可能容量は、前記記憶システムの一部として用いられる場合、その有効記憶容量であり、
前記記憶システムを形成する前記Ｄ個の記憶要素の全てが、必ずしも同じ利用可能容量を有しておらず、
前記記憶要素の１つを識別する全表登録項目の割合は、前記総利用可能容量のその割合に依存し、
３つ以上の冗長データ構成要素として符号化された前記記憶システムにおいて記憶される少なくとも１つのデータブロックが存在し、前記少なくとも１つのデータブロックを再構築するために、必ずしも前記３つ以上の冗長データ構成要素の全てを必要としない、方法。
【請求項２】
請求項１に記載の方法であって、  前記記憶システム内のどこに格納されるかとは独立して、データブロックを一意に識別するブロックアドレスを決定する段階と、
一組のＲ個の冗長データ構成要素として、前記データブロックを符号化する段階であって、前記ブロックを再構築するために、必ずしも一組のＲ個の冗長データ構成要素の全てを必要としない、前記符号化する段階と、
前記ブロックアドレスを用いて、前記記憶領域割当て表内に表入力項目を配置する段階と、
前記表入力項目を用いて、前記記憶要素の前記１つを識別する段階と、
前記組のＲ個の冗長データ構成要素の１つを前記記憶要素の前記１つに格納する段階とを更に備える方法。
【請求項３】
請求項１に記載の方法であって、前記記憶要素の前記１つを識別する全表登録項目の割合は、所定の許容誤差Ｔ内において、前記総利用可能容量のその割合に等しい、方法。
【請求項４】
請求項２に記載の方法であって、前記ブロックアドレスは、少なくともブロックアドレスの一部に対して、不規則な分布を生成するように構成された処理を用いて決定される、方法。
【請求項５】
請求項２に記載の方法であって、前記符号化する段階は、消去順応符号を利用する、方法。
【請求項６】
請求項３に記載の方法であって、新しい記憶要素が、前記記憶システムに付加され、前記総利用可能容量を増加させ、且つ前記記憶領域割当て表は、前記各記憶要素を識別する前記全表登録項目の割合が、前記総利用可能容量のその割合の（１＋Ｔ）倍以下であることを保証するように、更新される、方法。
【請求項７】
請求項６に記載の方法であって、前記総利用可能容量が、前記新記憶要素の前記利用可能容量を超えて増加する、方法。
【請求項８】
請求項３に記載の方法であって、前記記憶要素の前記１つが、故障して、前記記憶システムから除去され、前記総利用可能容量が減少すると、前記記憶領域割当て表は、前記記憶要素の前記１つを識別した全表登録項目を再度割り当て、代わりに前記記憶要素の残りを識別するように更新され、前記再割り当ては、前記記憶要素の残りのいずれにも、前記総利用可能容量のその割合の（１＋Ｔ）倍より大きい割合の前記全表登録項目が割り当てられないことを保証するように実施される、方法。
【請求項９】
請求項１に記載の方法であって、前記記憶領域配分表は、複数の表登録項目をまとめるように構成され、各複数の前記異なるメンバが、異なる記憶要素を識別する、方法。
【請求項１０】
請求項１に記載の方法であって、前記記憶要素の前記１つには、少なくとも１つのディスクドライブに取り付けられたコンピュータが含まれ、また、前記記憶要素の前記１つは、前記記憶要素の他のものによって用いられるコピーとは別の前記記憶領域割当て表のコピーを利用する、方法。
【請求項１１】
請求項１に記載の方法であって、記憶装置は、前記記憶システムに付加又は前記記憶システムから除去され、前記記憶領域割当て表は、一度に１つの入力項目を変更することによって更新され、幾つかの変更を行う判断は、割合の比較に依存し、前記各割合は、前記表中の登録項目の数を利用可能容量で除算したものを含む、方法。
【請求項１２】
請求項１に記載の方法であって、記憶装置は、前記記憶システムに付加又は前記記憶システムから除去され、前記記憶領域割当て表は、幾つかの登録項目を変更することによって更新され、且つ、変わる全登録項目の割合は、付加又は除去された前記記憶装置によって表される前記総利用可能容量の前記割合にほぼ等しい、方法。
【請求項１３】
請求項１に記載の方法であって、前記記憶要素の前記１つには、故障のリスクが大きくなったと確信された期間中、小利用可能容量が割り当てられる、方法。
【請求項１４】
請求項２に記載の方法であって、前記記憶要素の前記１つには、第２レベル記憶システムが含まれ、前記ブロックアドレスの一部分は、前記記憶領域割当て表内の表登録項目を特定するために用いられ、前記部分は、前記第２レベル記憶システム内で用いられる前記記憶領域割当て表内の表登録項目を特定するために用いられる前記ブロックアドレスの部分とは異なる、方法。
【請求項１５】
請求項２に記載の方法であって、前記記憶要素の前記１つが故障して、前記記憶システムから除去されると、前記記憶要素の前記１つを識別した前記表入力項目は、前記記憶要素の残りの１つを識別するように再度割り当てられ、前記組のＲ個の冗長データ構成要素の前記１つは、前記組のＲ個の冗長データ構成要素の残っているものからの前記記憶要素の前記残りの１つによって再構築される、方法。
【請求項１６】
請求項２に記載の方法であって、前記記憶要素の前記１つが、故障して前記記憶システムから除去されると、ＤをＲより小さくし、異なる冗長構成要素を異なる記憶要素置くという制約条件が緩和される、方法。
【請求項１７】
請求項２に記載の方法であって、２つの各データブロックは、そのデータの暗号ハッシュを計算することによって決定されたブロックアドレスを有し、前記２つのブロックは、前記記憶システムにおける記憶空間を共有する、方法。
【請求項１８】
データブロックを符号化して、偶発的又は故意の改変にもかかわらず、それを正確に格納又は送信させることを可能にする方法であって、
１より大きい数ｎの初期構成要素を構築する段階であって、それら各々が、前記ブロックから導出され、また、それら各々は、前記ブロックより小さい、前記構築する段階と、
初期構成要素を組み合わせて、１より大きい数ｍの新構成要素を構築する段階とを備え、
前記各新構成要素は、それを生成するために組み合わせられた前記初期構成要素のサイズの和より小さく、
前記ブロックは、前記初期構成要素及び新構成要素から選択された任意の組のｎ個の異なる構成要素から再構築することが可能であり、
前記初期構成要素及び新構成要素から選択された一組のｎ個の異なる構成要素は、前記組のｎ個の初期構成要素より冗長な前記ブロックに関する情報を含む、方法。
【請求項１９】
請求項１８に記載の方法であって、前記組み合わせる段階は、
初期構成要素を拡張して、拡張された初期構成要素を決定する段階と、
拡張された初期構成要素を蓄積して、前記ｍ個の新構成要素の１つを決定する段階とを更に備え、
拡張する段階は、前記初期構成要素の１つから、前記拡張された初期構成要素の１つを決定する段階であって、前記初期構成要素の前記１つが、前記拡張された初期構成要素の前記１つから決定されるように行われる、前記決定する段階を含み、
蓄積する段階には、前記初期構成要素の前記１つの部分と初期構成要素から導出された他の構成要素の対応する部分とを組み合わせる段階を含む、方法。
【請求項２０】
請求項１９に記載の方法であって、前記拡張する段階は、非周期的桁送り演算を実施する段階を含む、方法。
【請求項２１】
請求項２０に記載の方法であって、前記非周期的桁送り演算は、メモリアドレッシング動作として実現される、方法。
【請求項２２】
請求項２０に記載の方法であって、前記非周期的桁送り演算の桁送り量は、少なくとも部分的に、素数を法とした乗算によって決定される、方法。
【請求項２３】
請求項１９に記載の方法であって、前記拡張する段階は、前記初期構成要素の前記１つのビット又は拡大係数により決定されるビットを含む２進数表現がを有する整数を乗ずる段階を含む、方法。
【請求項２４】
請求項１９に記載の方法であって、前記蓄積する段階において部分と対応する部分とを組み合わせる段階は、前記部分から取られた第１引数と前記対応する部分から取られた第２引数とで２項演算を実施する段階を含む、方法。
【請求項２５】
請求項１９に記載の方法であって、初期構成要素から導かれる他の構成要素は、初期構成要素を拡大したものである、方法。
【請求項２６】
請求項１８に記載の方法であって、前記ｍ個の新構成要素の少なくとも１つは、前記ｎ個の初期構成要素の少なくとも１つより大きい、方法。
【請求項２７】
請求項１８に記載の方法であって、前記各初期構成要素のサイズの和プラス前記各新構成要素のサイズの和は、前記ブロックのサイズの１パーセントより小さく、（１＋ｍ／ｎ）倍より大きい、方法。
【請求項２８】
請求項１８に記載の方法であって、ｍ個の新構成要素が、固定された組のｎ個の初期構成要素から構成され、ｍは、新構成要素の構築が終了するまで選択されず、また、ｍのサイズには、上限がない、方法。
【請求項２９】
請求項１８に記載の方法であって、前記初期構成要素及び新構成要素の各々は、前記初期構成要素及び新構成要素の内のいずれか他方が格納されるものと異なる記憶サブシステムに優先的に格納される、方法。
【請求項３０】
請求項２９に記載の方法であって、前記記憶サブシステムは、少なくとも１つのディスクドライブを含む、方法。
【請求項３１】
請求項１８に記載の方法であって、前記組み合わせる段階は、
前記初期構成要素の１つが整数から決定されることが可能であるように、前記初期構成要素の前記１つから前記整数を決定する段階と、
前記整数を拡大して、拡大された整数を生成する段階であって、拡大には、２つの引数に対する乗算のような演算の適用が含まれ、前記２つの引数の１番目は、前記整数であり、前記２つの引数の２番目は、拡大係数である、前記生成する段階と、
拡大された整数を蓄積して、前記ｍ個の新構成要素の１つを決定する段階とを更に含み、
前記蓄積する段階は、２項演算を適用して、前記拡大された整数と、初期構成要素から導出された他の整数とを組み合わせる段階を含み、
前記乗算のような演算は、その２つの引数の内の１つが正であり、且つ２の累乗である時はいつでも、整数乗算と同じである、方法。
【請求項３２】
請求項２４又は３１に記載の方法であって、前記２項演算は、加算である、方法。
【請求項３３】
請求項２４又は３１に記載の方法であって、前記２項演算は、ビット毎のＸＯＲである、方法。
【請求項３４】
請求項２４又は３１に記載の方法であって、前記拡大係数は、２の累乗であり、前記指数が、素数を法とする乗算によって決定される、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、コンピュータ用の記憶システムに関し、特に、複数の記憶装置を含む耐障害性システムに関する。
【背景技術】
【０００２】
参照関連出願
本出願は、２００６年４月４日に出願した米国仮出願連番第６０／７８９，０１６号に対する優先権を主張するものである。
【０００３】
大規模記憶システムのハードディスクの数が多くなるにつれて、データを喪失することも、データへのアクセスを中断することもなく、ハードウェア故障に耐えるために、冗長性を用いる手法が益々重要になっている。この種類の最も一般的な手法は、ＲＡＩＤ５と呼ばれるが、この用語は、１９８８年９月に発行されたパターソン（Ｄａｖｉｄ  Ａ．Ｐａｔｔｅｒｓｏｎ）、ギブソン（Ｇａｒｔｈ＿Ａ．Ｇｉｂｓｏｎ）、及びカズ（Ｒａｎｄｙ＿Ｈ．Ｋａｔｚ）著の「安価なディスクＲＡＩＤの冗長アレイの事例」、データの管理に関する１９８８年ＡＣＭ  ＳＩＧＭＯＤ国際会議の論文集中の論文で導入されたものである。ＲＡＩＤ５システムは、複数のディスク全体にデータオブジェクトを分散することによるＩ／Ｏ性能改善、及び単一の故障したディスク上のデータを再構築するのに充分な冗長情報を格納することによるデータ安全性改善の双方を提供し得る。アレイ状のディスクは、結合されたＲＡＩＤ５グループを形成し、また、単純なパリティ符号（この場合、１つのディスクの領域に格納されたデータは、グループ内の他のディスクの対応する領域に格納されたビット毎のＸＯＲのデータである）が、通常、最小記憶空間オーバーヘッドで冗長性を提供するために用いられる。更に、ディスクを結合して単一ディスクの故障後の復旧を行うための他の方法が、２つの異なるディスク（ここでは、ＲＡＩＤ１と呼ばれている）における各データブロックの複製を含み、１９８８年の論文で概説されている。２つの同時ディスク故障後の復旧を可能にするＲＡＩＤ５の発展型は、ＲＡＩＤ６として知られるようになった。
【０００４】
ＲＡＩＤベース記憶システムの容量は、各々それ自体の内部ＲＡＩＤ冗長性によって保護されたサブシステムを単純に付加することによって、大きくできると思われる。この場合、システム全体は、誤りを免れない追加サブシステムがそれに含まれるため、信頼度が低下する。更に拡張可能な他の選択肢としては、互いの故障から充分に隔離された全サブシステムに冗長性を提供して、サブシステム全体の故障に耐え得るようにすることである。この種類の冗長性は、全サブシステムにおいて動作するＲＡＩＤによって、例えば、２００６年３月に発行された、トマシアン（Ａｌｅｘａｎｄｅｒ  Ｔｈｏｍａｓｉａｎ）著の「超大規模ディスクアレイ用マルチレベルＲＡＩＤ」、ＡＣＭ＿ＳＩＧＭＥＴＲＩＣＳ性能評価論評において説明されたように提供される。この手法には、ＲＡＩＤグループの要素間のデータ構成要素の厳格な対応を用いると、規模拡大変更が困難になるという不利な点がある。例えば、１つのサブシステムの容量を増加させるだけでは、総記憶容量を増やすことはできない。
【０００５】
他の選択肢の方式は、サブシステム全体に冗長性を分散するために提案されており、記憶責任は、個々のサブシステムが付加又は除去されにつれて増加する方向に移行する。更に、記憶領域割当ての管理は、もちろん、障害に耐性を有するものでなければならない。コード（Ｃｈｏｒｄ）システムは、ピアツーピアの世界において、これらの目標を達成するための不規則化されたアルゴリズムを導入した。コードは、２００１年９月に発行された、ストイカ（Ｉｏｎ  Ｓｔｏｉｃａ）、モリス（Ｒｏｂｅｒｔ  Ｍｏｒｒｉｓ）、カーガ（Ｄａｖｉｄ  Ｋａｒｇｅｒ）、カーシューク（Ｍ．Ｆｒａｎｓ  Ｋａａｓｈｏｅｋ）、及びバラクリシャナン（Ｈａｒｉ  Ｂａｌａｋｒｉｓｈｎａｎ）著の論文「コード：インターネット用途用の拡張可能なピアツーピア検索サービス」、ＡＣＭ  ＳＩＧＣＯＭＭ  ‘０１論文集、Ｓａｎ  Ｄｉｅｇｏで説明されている。これは、１９９７年５月に発行された、カーガ（Ｄ．Ｋａｒｇｅｒ）、レーマン（Ｅ．Ｌｅｈｍａｎ）、レイトン（Ｆ，Ｌｅｉｇｈｔｏｎ）、レビン（Ｍ．Ｌｅｖｉｎｅ）、レウィン（Ｄ．Ｌｅｗｉｎ）、パニグラフィ（Ｒ．Ｐａｎｉｇｒａｈｙ）著の「ハッシッ計算及びランダムツリーの両立：ワールドワイドウェブ上のホットスポットを緩和するための分散キャッシングプロトコル」、第２９回コンピュータ処理理論に関する年次ＡＣＭシンポジウムの論文集、Ｅｌ  Ｐａｓｏ、ＴＸの研究の上に構築されたものである。不変ハッシッ計算の研究は、１９９８年６月に申請された、カーガ（Ｋａｒｇｅｒ）らによる、「複数の資源間に要求を分散するための方法と装置」と題された米国特許第６５５３４２０号明細書の主題でもあった。
【０００６】
コードは、記憶サーバにデータを割り当てる不規則化されたメカニズムである。コードアルゴリズムは、データブロック用の恒久的な識別子として、ハッシュベースのブロック名を用いており、また、全ての可能なブロック名のアドレス空間を記憶サーバ間で分割する。この分割は、アドレス空間において複数の点を各記憶サーバに擬似乱数を使って割り当てることによって達成される。全ての割り当てられた点の集合体は、一組のアドレス範囲を定義するために用いられる。即ち、各サーバは、開始点が割り当てられた範囲のアドレス範囲に入る名前を持った全てのブロックに対して責任を負っている。アドレス範囲は、サーバに割り当てられた次の点にまで及ぶ。新しいサーバが記憶システムに付加される場合、新しい点が、それに擬似乱数を使って割り当てられ、そのアドレス空間の部分に対する責任は、これに伴って移行する。即ち、データが、サーバ間で移行する。サーバに割り当てられた点の数は、その記憶容量に比例する。同じ組のアドレス範囲が、ブロックの一次コピー及び冗長コピー双方に対する責任を定義するために用いられる。即ち、一次コピーは、あるアドレス範囲に位置し、冗長コピーは、後続の範囲が割り当てられたサーバに属する。サーバが機能停止したり、システムから除去されたりすると、その割り当てられた点は、消滅する。これによって、幾つかの隣接アドレス範囲が、拡張され、記憶責任が移行する。記憶責任をランダムに割り当てるコード手法は、極めて多数のサーバには良好に機能するが、より少数のサーバに対しては同じでは無い。例えば、冗長データコピーが異なるサーバに割り当てられるというコードが行う唯一の保証は、統計的なものであり、この保証は、少数のサーバの場合、破綻する。データブロックの全てのコピーが同じサーバに格納される場合、そのサーバが故障すると、そのデータは喪失する。
【０００７】
この問題の影響を受けない不規則化された記憶領域割当て方法が、２００４年４月に発行された、ホニッキ（Ｒ．Ｈｏｎｉｃｋｙ）及びミラー（Ｅｔｈａｎ＿Ｍｉｌｌｅｒ）著の論文「拡張可能なハッシング下での複製：拡張可能な分散データ分配のためのアルゴリズムの系列」、第１８回国際並列＆分散処理シンポジウムの論文集に記載されている。そこでは、データブロックの複製（又はブロックから導出された他の冗長構成要素）を一組の記憶装置に割り当て、各複製を異なる記憶装置に配置するためのアルゴリズムが提供されている。ＲＵＳＨアルゴリズムは、記憶システムに同時に付加された記憶装置をグループ化する段階と、各グループを固有のクラスタ識別子でラベル表示する段階とを伴う。ブロック識別子及びクラスタ識別子の決定論的機能は、各複製がどこに常駐しているか判断する。新しいクラスタが付加される度に、アルゴリズムは、新しい記憶装置に全ての複製のいずれかの部分を再度割り当てる。
【０００８】
ＲＵＳＨは、個々の故障した記憶装置を除去させず、クラスタ全体の装置だけを除去させ、また、クラスタの最小サイズに関する制約条件がある。更に、これらのアルゴリズムは、複製がどこに常駐しているか判断するのに必要な作業量が、クラスタの数が増加するにつれて、増えるという欠点がある。既に格納されたブロック用の全ての識別子は、新しい記憶装置が付加された場合、どのブロックが新しい記憶装置に再度割り当てられ、また、除去する必要があるか判断するために、ＲＵＳＨアルゴリズムを用いてチェックする必要がある。
【０００９】
ＲＡＩＤ５システムに用いられるものと同様な冗長方式は、冗長構成要素のランダム配置を用いる記憶システムでも用いられる。このクラスの冗長方式は、「消去順応符号」と称されることがあるが、これは、欠落データを再構築するために、どの冗長構成要素が「消去」されたかを知ることに依存するためである。ＲＡＩＤ５でのようなパリティブロックを用いることは、単一のディスク故障から保護する効率的な方法である。即ち、各ディスクの対応するビットは、符号語のビットとして処理され、単一のパリティビットによって保護され、任意の単一ビット消去（即ち、任意の単一のディスク故障）を回復し得る。この手法は、更に洗練された誤り訂正符号で長い符号語を保護することによって、複数のハードウェア故障から復旧できる方式に拡張し得る。このことは、例えば、２００５年９月に発行された、フェング（Ｇ．Ｆｅｎｇ）らによる、「ＲＡＩＤ用の新しい効率的ＭＤＳアレイ符号、パートＩ：３つのディスク故障を許容するためのリード−ソロモン的符号」と題されたＩＥＥＥコンピュータに関する議事録で記載されているように、ＲＡＩＤ５手法の発展の礎である。また、同じ分散符号語の考え方は、１９９１年５月に申請された、ラビン（Ｍｉｃｈａｅｌ  Ｒａｂｉｎ）により、「情報分散及び再構築のための方式」と題された、米国第０５４８５４７４号明細書において記載されている方法等、耐障害性分散型記憶方法の礎である。この分散符号語の考え方に対する分散型記憶保護方式の包括的な依存性には、欠点がある。即ち、誤り訂正符号は、各々わずか数ビット長である要素の集合体を保護するように構成される。保護されている記憶容量の基本的な単位が、実際には、数百又は数千バイト長である（又はそれより長い）という事実から利点を得ることができれば、より良い利用可能な符号が存在しそうである。
【００１０】
要約すると、規模を拡大変更可能な形態で、ディスクの大きな集合体が含まれる記憶システムを故障から保護する必要性がある。その方法は、大きくなる記憶システムが大きい状態で始まるわけではないことから、相対的に小さいディスク集合体に合わせて規模を縮小変更できることが望ましい。わずかずつ記憶装置を付加及び除去する能力は、拡張のためばかりでなく、新しいハードウェアへの非分断的移行のためにも有用である。データのランダム配置に基づくデータ割当て方式は、魅力的であるが、既存のアルゴリズムには、拡張性及び効率向上の観点で、歴然とした不利な点がある。最後に、既存の記憶方式では、それらの故障復旧は、極めて小さいデータ要素を保護するように構成された誤り訂正符号に基づいており、また、保護されている記憶装置の基本的な単位の比較的大きなサイズの利点を利用していない。
【発明の開示】
【課題を解決するための手段】
【００１１】
第１の態様において、本発明は、拡張可能で耐障害性の記憶システムを構成するための方法を特徴とする。本方法には、Ｄ個の記憶要素をまとめて記憶システムを形成する段階であって、Ｄが２以上である段階と、表登録項目が含まれる記憶領域割当て表を構築する段階と、各記憶要素に対して、記憶システム内における冗長データの配置に関する制約条件に依存する利用可能容量を演算する段階と、利用可能容量を合計して、記憶システム用の総利用可能容量を形成する段階と、記憶領域割当て表の表登録項目を割り当て、記憶要素の内の１つを各々識別する段階とが含まれる。本方法において、各記憶要素の利用可能容量は、記憶システムの一部として用いられる場合、その有効記憶容量であり、記憶システムを形成するＤ個の記憶要素の全てが、同じ利用可能容量を有しておらず、また、記憶要素の１つを識別する全表登録項目の割合は、総利用可能容量のその割合に依存する。
【００１２】
本発明のこの態様の好適な実施例は、以下の１つ又は複数を組み込み得る。
本発明には、更に、記憶システム内のどこに格納されるかとは独立して、データブロックを一意的に識別するブロックアドレスを決定する段階と、一組のＲ個の冗長データ構成要素として、データブロックを符号化する段階であって、ブロックを再構築するために、それらの全てを必要としない段階と、ブロックアドレスを用いて、記憶領域割当て表内において表入力項目を特定する段階と、表入力項目を用いて、記憶要素の１つを識別する段階と、一組のＲ個の冗長データ構成要素の１つを記憶要素の１つに格納する段階とを含む。
【００１３】
記憶要素の１つを識別する全表登録項目の割合は、所定の許容誤差Ｔ内において、総利用可能容量のその割合に等しくてよい。
ブロックアドレスは、少なくともブロックアドレスの一部に対して、不規則な分布を生成するように構成された処理を用いて決定し得る。
【００１４】
符号化する段階は、消去順応符号を利用する。
新しい記憶要素が、記憶システムに付加され、総利用可能容量を増加させ、また、記憶領域割当て表は、各記憶要素を識別する全表登録項目の割合が、総利用可能容量のその割合の（１＋Ｔ）倍以下であることを保証するように、更新される。
【００１５】
総利用可能容量は、新しい記憶要素の利用可能容量を超えて増大する。
記憶要素の１つが、故障し、記憶システムから除去され、総利用可能容量が減少することがある。すると、その記憶要素の１つを識別した全表登録項目を再度割り当て、代わりに記憶要素の残りを識別するように、記憶領域割当て表が更新される。この再割り当ては、記憶要素の残りのいずれにも、総利用可能容量のその割合の（１＋Ｔ）倍より大きい割合の全表登録項目が割り当てられないことを保証するように実施される。
【００１６】
記憶領域配分表は、複数の表登録項目をまとめるように構成され、各複数の異なるメンバが、異なる記憶要素を識別する。
記憶要素の１つには、少なくとも１つのディスクドライブに取り付けられたコンピュータを含むことができ、また、記憶要素の１つは、記憶要素の他のものによって用いられるコピーとは別の記憶領域割当て表のコピーを利用する。
【００１７】
記憶装置は、記憶システムに付加又はそれから除去でき、記憶領域割当て表は、一度に１つの入力項目を変更することによって更新され、幾つかの変更を行う判断は、割合の比較に依存するが、この場合、各割合は、表中の登録項目の数を利用可能容量で除算したものを含む。
【００１８】
記憶装置は、記憶システムに付加又はそれから除去でき、また、記憶領域割当て表は、幾つかの登録項目を変更することによって更新でき、更に、変わる全登録項目の割合は、付加又は除去された記憶装置によって表し得る総利用可能容量の割合にほぼ等しい。
【００１９】
記憶要素の１つには、故障のリスクが大きくなったと確信された期間中、小利用可能容量を割り当て得る。
記憶要素の１つには、第２レベル記憶システムを含むことができ、ブロックアドレスの一部分は、記憶領域割当て表内の表登録項目を特定するために用いることができ、その部分は、第２レベル記憶システム内で用いられる記憶領域割当て表内の表登録項目を特定するために用いられるブロックアドレスの部分とは異なってよい。
【００２０】
記憶要素の１つが故障して、記憶システムから除去されることがあると、記憶要素の１つを識別した表入力項目は、記憶要素の残りの１つを識別するように再度割り当てられ、その組のＲ個の冗長データ構成要素の１つは、その組のＲ個の冗長データ構成要素の残っているものからの記憶要素の残りの１つによって再構築される。
【００２１】
記憶要素の１つが、故障して記憶システムから除去されると、ＤをＲより小さくし、異なる冗長構成要素を異なる記憶要素に置くという制約条件を緩和し得る。
２つの各データブロックは、そのデータの暗号ハッシュを演算することによって求められたブロックアドレスを有し、２つのブロックは、記憶システムの記憶空間を共有し得る。
【００２２】
３つ以上の冗長データ構成要素として符号化される記憶システムに格納された少なくとも１つのデータブロックがあり、その全てが、少なくとも１つのブロックを再構築するために、必要ではないことがある。
【００２３】
第２の態様において、本発明は、データブロックを符号化して、偶発的又は故意の改変にもかかわらず、それを正確に格納又は送信させるための方法を特徴とする。本方法には、１より大きい数であるｎの初期構成要素を構築する段階であって、それら各々が、ブロックから導出され、また、それら各々は、ブロックより小さい段階と、初期構成要素を組み合わせて、１より大きい数であるｍの新構成要素を構築する段階とが含まれる。本方法において、各新構成要素は、それを生成するために組み合わせられた初期構成要素のサイズの和より小さく、ブロックは、初期構成要素及び新構成要素から選択された任意の組のｎ個の異なる構成要素から再構築することが可能であり、初期構成要素及び新構成要素から選択された一組のｎ個の異なる構成要素は、上記組のｎ個の初期構成要素より冗長なブロックに関する情報を含む。
【００２４】
この本発明の態様の好適な実施例は、以下の１つ又は複数を組み込むことができる。
組み合わせる段階には、更に、初期構成要素を拡張して、拡張された初期構成要素を決定する段階と、拡張された初期構成要素を蓄積して、ｍ個の新構成要素の１つを決定する段階と、を含み得る。拡張する段階には、初期構成要素の１つから、拡張された初期構成要素の１つを決定する段階であって、初期構成要素の１つが、拡張された初期構成要素の１つから決定されるように行われる段階が含まれる。また、蓄積する段階には、初期構成要素の１つの部分と、初期構成要素から導出された他の構成要素の対応する部分とを組み合わせる段階が含まれる。
【００２５】
拡張する段階には、非周期的桁送り演算を実施する段階を含み得る。
非周期的桁送り演算は、メモリアドレッシング動作として実現し得る。
非周期的桁送り演算の桁送り量は、少なくとも部分的に、素数を法とした乗算によって求め得る。
【００２６】
拡張する段階には、初期構成要素の１つの２進数表現が含まれる整数に拡大係数を乗ずる段階を含み得る。
蓄積する段階において部分と対応する部分とを組み合わせる段階には、部分から取られた第１オペランドと対応する部分から取られた第２オペランドとで加算演算又はビット毎のＸＯＲ演算を実施する段階を含み得る。
【００２７】
ｍ個の新構成要素の少なくとも１つは、ｎ個の初期構成要素の少なくとも１つより大きくてよい。
各初期構成要素のサイズの和プラス各新構成要素のサイズの和は、ブロックサイズの１パーセントより小さく、（１＋ｍ／ｎ）倍より大きくてよい。
【００２８】
数ｍの新構成要素が、固定された組のｎ個の初期構成要素から構成でき、この場合、ｍは、新構成要素の構築が終了するまで選択されず、また、ｍのサイズには、上限がなくてよい。
【００２９】
初期構成要素及び新構成要素の各々は、初期構成要素及び新構成要素の内のいずれか他方が格納されるものと異なる記憶サブシステムに優先的に格納される。
記憶サブシステムには、少なくとも１つのディスクドライブが含まれる。
【００３０】
組み合わせる段階には、更に、初期構成要素の１つが整数から決定されるように、初期構成要素の１つから整数を決定する段階と、整数を拡張して、拡張された整数を生成する段階であって、拡張には、２つのオペランドに対する乗算のような演算の適用が含まれ、２つのオペランドの１番目は、整数であり、２つのオペランドの２番目は、拡大係数である段階と、拡張された整数を蓄積して、ｍ個の新構成要素の１つを決定する段階と、が含まれる。蓄積する段階には、２項演算を適用して、拡張された整数と初期構成要素から導出された他の整数とを組み合わせる段階が含まれる。更に、乗算のような演算は、その２つの引数の内の１つが正であり、また、２の累乗である時はいつでも、整数乗算と同じである。
【００３１】
２項演算は、加算であってよい。
２項演算は、ビット毎のＸＯＲであってよい。
拡大係数は、２の累乗であり、指数が、素数を法とする乗算によって決定される。
【００３２】
初期構成要素から導出された他の構成要素は、拡張された初期構成要素であってよい。
本発明の他の特徴及び利点は、詳細な説明、図面、及び請求項において見出されるであろう。
【発明を実施するための最良の形態】
【００３３】
本明細書に記載できないほど多くの本発明の可能な実施例が存在する。幾つかの可能な実施例について、以下に説明する。しかしながら、これらは、本発明の実施例の説明であって、本発明の説明ではない。本発明は、本節で説明する詳細な実施例に限定されず、請求項においてより広義の言葉で記載されるということは、どのように強く強調してもし過ぎることはない。
【００３４】
容量の拡張可能な分散式記憶システムにおいて、幾つかの基本的な問題は、以下の通りである。
１）オブジェクトの格納場所を追跡すること、
２）記憶サーバ間で格納作業のバランスをとること、
３）装置の故障に耐えること、
４）装置の故障から復旧すること、
５）記憶サーバ間で復旧作業のバランスをとること、
６）記憶装置の付加及び除去を可能にすること。
【００３５】
上記したコード（Ｃｈｏｒｄ）方式は、これらの問題の幾つかを良好に取り扱う。例えば、データオブジェクトの索引付けは、完全に分散され、また、オブジェクトへのアクセスに必要な作業は、記憶装置の付加及び除去の履歴から独立している。しかしながら、コードは、小規模システムに対して良好に機能せず、また、下位の組のサーバの幾つかが、他のものより充分に相互接続されるということを利用していない。例えば、同じネットワーク交換機に接続された組のサーバは、異なる交換機上のサーバと通信を行うより効率的に、また、同じローカルエリアネットワーク上にないサーバと通信を行うより更に効率的に、互いに通信を行うことができる。
【００３６】
余裕を持って相互接続されたサーバのクラスタから記憶システムを構築すると、耐障害性を階層的に提供し得ることから、システム全体の拡張性を制限することはない。「クリーク」と呼ばれる単位クラスタは、複数のサーバの広い範囲に渡って拡張し得るが、無制限にできるわけではない。クリーク内における記憶装置間にデータを分散するために用いられる同一の手法は、クリーク全体に又は追加レベルの記憶階層全体にデータを分散するために再利用される。
【００３７】
一実施例において、全てのブロックは、固定サイズの擬似乱数を使って生成された固有の識別子で命名される。識別子が充分に長い場合、識別子を常に生成する疑似乱数を使用した処理が、２つの異なるブロックに対して同じ識別子を生成する可能性は、無視できると仮定する。適切な識別子の幾つかの例を図１に示す。ランダムに生成された数が、適切な識別子である。ブロックのコンテンツの暗号ハッシュは、適切であり、同じブロックが２度以上格納される場合、それを用いて、記憶装置の共有を簡素化し得るという特性を有する。ブロックに既に割り当てられた他の任意の固有識別子の暗号ハッシュも適切である。また、開示実施例に用いられる識別子は、セグメントが、充分に不規則であり、また、充分に長い場合、他の任意の識別子の固定サイズのセグメントであってよい。
【００３８】
クリーク内の全サーバには、記憶装置がサービスに付加又はそれから除去された時はいつでも再計算される共通のアドレス範囲割当て表のコピーが提供される。この表は、格納されたデータのブロックを表す全ての冗長構成要素に記憶装置を割り当て、構成要素の場所を構成して、ハードウェア故障から最大限の保護を行う。このことは、図２及び図３に示す。図２において、２進数の“１０１０”で始まる識別子を備えたブロック用の冗長データは、３つの異なる記憶サーバ上の３つの異なるデータ記憶装置に割り当てられることが分かる。従って、任意の単一の記憶装置が故障した場合、又は任意の単一のサーバが故障した場合、そのブロック用の冗長構成要素の１つだけが失われる。図３は、“１０１０”で始まる識別子を備えた特定のブロックＢを示す。ブロックは、３つの冗長構成要素に符号化され、それらの内の少なくとも１つは、喪失して他の２つから再構築し得る。３つの冗長構成要素は、図２のルーティング表情報に示すように、３つの異なるサーバに格納される。適切な冗長符号の２つの例を図４に示す。第１例は、単に各ブロックの３つのコピーを生成する。この場合、利用可能な記憶空間の３分の１だけが各々のデータに用いられる。第２例は、各データブロックの半分のサイズの追加パリティブロックを付加する。この場合、利用可能な記憶空間の３分の２は、各々のデータに用いられる。低オーバーヘッドでデータ喪失に対する耐性が大きい符号化については、「冗長構成要素の符号化及び用途」の節で議論する。
【００３９】
ここで用いられるアドレス範囲ベースの手法では、表が再度生成された時はいつでも記憶装置の最適化及び復旧特性を可能にしつつ、個々のデータオブジェクトがどこに格納されているかを示す集中型の指標を全く必要としない。ここでは、主として、この最適化問題に焦点を当てる。（改善された性能での実施を選択する処理を幅広く参照するために、用語「最適化」を用いるのであって、真に最適な、即ち、超最適性能の実施に限定するものではない）。各記憶サーバ内の擬似乱数を使って命名されたデータに対するアクセス及び索引付けに関連する問題は、マーゴラス（Ｍａｒｇｏｌｕｓ）らによる米国特許出願第２００６／０１１６９９０号、「ランダムに命名されたデータブロック用記憶システム」（２００５年９月３０日）において検討されており、本明細書において参照により組み込まれる。冗長構成要素を符号化し再構築するための単純で効率的な幾つかの方式をここでも提示する。
【００４０】
最適化問題
クリークは、Ｓ個の記憶サーバ間で分割されたＤ個のデータ記憶装置を含む。各データ記憶装置には、複数のアドレス範囲に対する責任が割り当てられる。様々なデータ記憶装置の責任アドレス範囲を記録する表は、ルーティング表と呼ばれる。ルーティング表は、総アドレス空間を一組の等しいサイズのアドレス範囲に分割し、各範囲に対する責任が割り当てられたデータ記憶装置の組を指定する。
【００４１】
耐障害性を達成するために、各データオブジェクトは、Ｒ個の冗長構成要素によって、記憶装置システム内において表される。これら冗長構成要素は、データオブジェクトの完全な複製であってよく、又は、他の何らかの消去順応符号化方式の要素であってよい。
【００４２】
ルーティング表構成及び生成アルゴリズムは、以下の４つの主な制約条件を調整する。
１）最大容量：記憶装置責任は、理想的には、総記憶容量を最大にするように、データ記憶装置に割り当てられるべきである。所定の許容範囲Ｔは、クリークが満杯時浪費し得る記憶容量の最大部分を指定する。
２）耐障害性：単一のデータオブジェクトの冗長構成要素は、理想的には、出来るだけ多くの同時ハードウェア故障を許容するために、異なるデータ記憶装置及び異なるサーバに割り当てられるべきである。
３）迅速な復旧：冗長構成要素は、理想的には、全てのデータ記憶装置が、ハードウェア故障後、同時に参加して復旧を早めるように構成すべきである。理想的には、記憶装置が除去される場合、復旧を早めるために、データ移動を出来るだけ少なくすべきである。
４）逐次増大：理想的には、少しずつ記憶装置を付加及び除去できるべきである。理想的には、新しい記憶装置にその公平な格納作業負荷を分担させるために、移動するデータは、出来るだけ少ない方がよい。
【００４３】
最大容量
最大容量制約条件は、無駄な空間に制限を設定する。ブロックが、データ記憶装置に擬似乱数を使って割り当てられることから、無駄な空間に対する統計的な構成要素がある。アドレス範囲のサイズは、ルーティング表に出現する時、量子化されることから、系統的構成要素もある。１つのデータ記憶装置は、その公平なデータ分担を超える責任を負わされると、システムの他の場所にまだ空間が残されているにもかかわらず満杯になる。一旦１つのデータ記憶装置が満杯になると、システムは、満杯と見なされ、他の場所に残っている空間は、いずれも浪費される。浪費される利用可能な記憶容量の最大部分は、許容範囲Ｔによって与えられる。
【００４４】
最初に、無駄な空間の統計的な構成要素に焦点をあてる。しばらくの間、アドレス範囲の量子化を一切無視し、各データ記憶装置には、その記憶容量に厳密に比例する総アドレス空間の一部が割り当てられるものとする。各データ記憶装置は、それに割り当てられたアドレス範囲に入るアドレスを備えた全てのブロックを格納する責任を負っている。ブロックは、固定最大サイズを有し、アドレスが擬似乱数を使って割り当てられ、データ記憶装置へのブロックの配分が統計的になっている。解析を単純にするために、全てのブロックは、サイズが８ＫＢであり、また、与えられたデータ記憶装置には、単一の５００ＧＢディスクドライブが含まれるものとする。そして、記憶装置システムがほぼ満杯である場合、与えられたデータ記憶装置は、そのブロックアドレスの公平な分担に対して責任を負っていることから、ほぼ満杯である。平均的に、５００ＧＢデータ記憶装置は、標準偏差約８０００ブロックで約６３０万の８ＫＢブロックを格納する責任を負っている。従って、記憶領域割当ての期待統計ばらつきは、データ記憶装置の容量のわずか１パーセントの数百分の一である。許容範囲Ｔが、これよりかなり大きい場合、統計的なばらつきによる無駄な空間は、無視することができる。
【００４５】
従って、無駄な空間は、ルーティング表における系統的量子化効果によると仮定する。即ち、アドレス空間は、Ｗをルーティング表の列の数（表の幅）とすると、Ｗ個の等しいサイズのアドレス範囲に均等に分割されることから、記憶領域割当ては、必ずしも厳密に容量に比例しない。Ｒ台の記憶装置が各アドレス範囲に割り当てられており、表の割当ての総数（登録項目Ｅ）が、許容範囲で除したデータ記憶装置の数と少なくとも同じ大きさ（Ｅ＞＝Ｄ／Ｔ）である限り、クリークの総利用可能容量は、最適値の許容範囲Ｔ以内に割り当て得ることを示すのは、簡単である。このことは、図１０に示す。また、境界は、付録Ａにおいて導出する。従って、許容範囲制約条件は、ルーティング表の最小幅を設定する。例えば、１００のデータ記憶装置、各データブロックを表す２つの冗長構成要素、及び浪費記憶装置に対する１％の許容範囲のクリークの場合、ルーティング表の幅は、少なくとも５０００列でなければならない。
【００４６】
耐障害性
第２制約条件である耐障害性は、別々に故障するハードウェア間に各データオブジェクトの冗長構成要素を分散することによって達成される。データ記憶装置が冗長構成要素より多い限り、各データオブジェクトのＲ個の構成要素は、Ｒ台の異なる記憶装置に置かなければならない。このことは、各アドレス範囲にＲ台の異なる記憶装置を割り当てることによって達成される。しかしながら、最大容量制約条件を満たすために、各記憶装置には、更に、その容量に比例する総アドレス空間の一部が割り当てられなければならないことに留意されたい。双方の制約条件を満たすことが可能でない場合、耐障害制約条件には、優先権が与えられ、一部の容量が、割り当てられずに残される。例えば、各データオブジェクトが、２つの冗長構成要素（２つの複製）を有する場合、耐障害性は、単一の記憶装置には、全てのデータブロックの半分を超える責任が割り当てられないことを要求する。従って、組み合わせられたシステムにおける他の全ての記憶装置のものよりも、１つの記憶装置が未調整で大きい容量を有する場合、ブロックの半分以下の記憶容量に限定される。この種類の容量制限は、記憶装置のサイズが著しく異なる場合にのみ作用し始め、更に記憶装置がシステムに付加されるにつれて、以前割り当てられていない容量が使用可能になる。用語「利用可能容量」は、この制約条件が無視された場合に潜在的に割り当て得る生の容量とは対照的に、耐障害制約条件を考慮して、実際に割り当て可能な記憶装置の容量を指すために用いる。
【００４７】
全記憶サーバは、単体として故障し得ることから、耐障害性は、更に、Ｒを超えるサーバがある限り、各オブジェクトのＲ個の構成要素をＲ台の異なるサーバに置かなければならないという制約条件を課す。この制約条件が満たされた場合、Ｒ個の構成要素は、異なる記憶装置に自動的に置かれることに留意されたい。サーバがＲ個未満である場合、耐障害性は、冗長構成要素をできるだけ均等に分散するように要求する。例えば、各データオブジェクトは、これらの構成要素の任意の２つを他の２つから復旧させる符号化を用いて、４つの冗長構成要素として表される。この場合、各オブジェクトのわずか２つの構成要素が、最後まで同じサーバ上にある限り、あらゆる単一サーバ故障は、許容される。
【００４８】
少なくともＲのサーバがクリークにある限り、冗長構成要素の格納に利用可能な容量は、サーバが任意のデータオブジェクトの複数の冗長構成要素を保持しないという制約条件に基づき、算出し得る。Ｃｉが、ｉ番目のサーバの生の容量であり、Ａｉが、サーバの利用可能容量であり、また、サーバが、最大から最小容量の方に（減少する方向に）付番されると、Ｓ台のサーバを備えたクリークの場合、利用可能容量は、以下の式によって与えられる。
【００４９】
【数１】
2009532812.tif 000003
総利用可能容量Ａｔｏｔは、Ａｋの和である。記憶装置の利用可能容量は、サーバの未加工の容量のそれらの分担に比例して割り当てられる。サーバｓ（ｉ）上にあり、生の容量ｃｉを有する記憶装置ｉの利用可能容量は、以下の式によって与えられる。
【００５０】
ａｉ＝Ａｉ（ｃｉ／Ｃｓ（ｉ））
図５は、異なる数のサーバ及び異なる数の冗長構成要素を備えた記憶システム用の利用可能容量を示す幾つかの例を提供する。本例では、各記憶サーバの生の容量が与えられている。記憶システム＃１において、サーバ１は、強制的にサーバ２より多くのデータを保持せず、従って、総利用可能容量は、６００ＧＢのみである。用いられないサーバ１の１００ＧＢは、追加の記憶装置がシステム（記憶システム＃２）に付加された時、利用可能になる。厳密に同じサーバがＲ＝３で用いられる場合、１００ＧＢが、再度利用不可能になる。記憶システム＃３は、Ｒ＝２、３又は４かどうかに依存して、同じハードウェア用の３つの異なる利用可能容量を示す。
【００５１】
サーバがＲ個未満である場合、データオブジェクトの唯１つの冗長構成要素を各サーバに置き得るという制約条件を緩和する。１つの冗長構成要素だけを各データ記憶装置に置き得るという制約条件を代用すると、利用可能容量は、Ａｋの場合のように厳密に算出されるが、記憶サーバに対するＡｋ及びＣｋの代わりに、データ記憶装置に対するａｋ及びｃｋを用いる。上記したように、データオブジェクトの冗長符号化によって、複数の冗長構成要素を喪失し、また復旧し得る。この理由により、記憶装置がＲ台未満である場合でも、耐障害性は、依然として、記憶装置間全体に冗長構成要素をできるだけ均等に分散することによって強化される。
【００５２】
このことを図６に示す。ここで、Ｒ＝４であり、４台の単一記憶サーバがあり、各々ブロックＤの１つの冗長構成要素を保持する。サーバ２が故障すると、４つの構成要素は、もはや異なるサーバに置くことができない。本例では、Ｄ４が、サーバ３上に再構築され、他の構成要素は、そのままの状態に留まる。Ｄの２つの欠落構成要素を他のものから再構築し得る限り、この構成は、最小のデータ移動で耐障害性を継続して提供する。
【００５３】
迅速な復旧
第３制約条件は、迅速な復旧である。理想的には、１台の記憶装置上で表されるデータオブジェクトの組は、それらの冗長構成要素を他の全ての記憶装置に渡って均等に分散すべきであり、また、故障後の記憶責任の新しい割当てもまた、全ての記憶装置に渡って均等に分散すべきである。これらの２つの特性は、故障後、故障からの復旧作業が全ての記憶装置に渡って均等に分散されることを共に保証する。
【００５４】
復旧処理は、図７に示す。記憶装置３が故障する前、冗長ブロックは、記憶装置３を含む全ての記憶装置に渡って分散されている。２つのサンプルブロックＡ及びＢ用の構成要素を示す（Ｒ＝３）。記憶装置３が故障すると、記憶装置３に格納されていた冗長構成要素は、他の記憶装置上に再現しなければならない。ブロックＡ及びＢの場合、これらは、構成要素Ａ３及びＢ２である。これら構成要素を含むアドレス範囲は、記憶装置Ｄ−１及び４にそれぞれ再度割り当てられる。Ａの残りの構成要素の１つ又は複数は、記憶装置Ｄ−１に送り、そこでＡ３を再構築させねばならず、また、Ｂの残りの構成要素の１つ又は複数は、記憶装置４に送らねばならない。通知すべき構成要素の数は、どのようにブロックが符号化されているかに依存する。Ｂが単に複製されている（全ての冗長構成要素が、ブロックＢの完全なコピーである）場合、Ｂの唯１つの構成要素を記憶装置４に通知する必要がある。Ｂ３がＢ１とＢ２とのＸＯＲである場合、Ｂ１及びＢ３双方は、Ｂ２を再構築するために、記憶装置４に送らねばならない。
【００５５】
（故障ではなく）予定された除去の場合、幾つかの又は全ての構成要素は、記憶装置３から供給し得ることに留意されたい。しかしながら、記憶装置３だけを用いると、相対的に遅くなる。図において、全ての冗長構成要素が完全な複製であり、Ｄ＝１００の記憶装置があり、また、冗長データがそれら全てに渡って均等に分散されている場合、各記憶装置は、そのデータの１％を供給し、記憶装置３から失われた構成要素の１％を再現するだけでよい。ＸＯＲ符号化が用いられた場合、それらは、各々２％供給する必要がある。これは、１つの記憶装置が全てのデータを供給するよりはるかに速い。
【００５６】
もちろん、冗長性の完全に均等な分布は、一般的に、各記憶装置に割り当てられたアドレス範囲の数が、その利用可能容量に比例しなければならないとする最大容量制約条件と対立する。迅速な復旧よりも最大容量に優先権を与えることから、もっと現実的な分布目標を用いる。即ち、共に出現し得る記憶装置の各対には、それらの利用可能容量の積算量に比例する回数、同じアドレス範囲に対する責任が割り当てられるべきである。従って、例えば、記憶装置ｘが、記憶装置ｙ及びｚ（例えば、ｘは、異なるサーバ上にある）と対にされる場合、ｙが記憶装置ｚの２倍であれば、ｙは、ｚより２倍頻繁にｘと対にされるべきである。
【００５７】
この目標の場合でも、表において利用可能容量を正確に表しつつ、全ての対に対して一定の比率を有することは、一般的に可能ではないが、通常、これに近い状態にすることができる。各記憶装置は、既にそれ自体の利用可能容量に比例して表に表されている。更に、対でのその出現が、それが対をなす記憶装置の総量の利用可能容量に比例する場合、この合計は、全ての記憶装置に対して同じである必要があり、このことは、近似的に真である。例えば、記憶装置が、同じサーバ上の記憶装置との対から除外されるだけの場合について考える。この場合、サーバの容量が等しくなければ、１つのサーバ上の記憶装置が対をなし得る記憶装置の総量は、他のサーバ上の記憶装置から見たものと異なることがあるが、一般的には、あまり違わない。異なるサーバ上の利用可能容量の範囲（即ち、最大マイナス最小）が、クリークの総利用可能容量の数パーセントほどである限り、対も数パーセント内に比例し得る。重要なパラメータは、いずれかの記憶装置が対をなしえない最大グループの容量ＡＬ、最も小さいそのようなグループの容量ＡＳ、及びクリークの総利用可能容量Ａｔｏｔである。全ての対は、約（１−（ＡＬ−ＡＳ）／（Ａｔｏｔ−ＡＬ））の係数内で利用可能容量の積算量に比例し得る。
【００５８】
ハードウェア及びソフトウェアでは、復旧スピードのボトルネックがどこにあるかに依存して、サーバ間にデータを均等に分散することが、記憶装置間にそれを均等に分散することより重要なことがある。しかしながら、データが、対の記憶装置の利用可能容量の積算量に比例して分散されていると、それは、対のサーバの利用可能容量の積算量に比例して分散されており、従って、双方の目標が、最大限達成される。
【００５９】
迅速な復旧制約条件は、また、復旧するために故障後移動すべきブロックの数を低減するように、ルーティング表が構成され修正されることを要求する。記憶装置ｘが故障すると、以前ｘによって保持されていた冗長構成要素に対する責任は、他の記憶装置に再度割り当てられなければならない。理想的には、ｘによって保持されていたアドレス範囲だけが、再度割り当てられるべきである。残りの各記憶装置が現時点で表す総容量の割合が大きくなっていることから、表における他の記憶装置の表示は、増やすべきである。しかしながら、ｘのデータの複製が他の記憶装置全体で均等に分散されなかった場合、この理想的な状態は、不可能であろう。極端な例として、ｘが、ルーティング表において、記憶装置ｙとのみ対をなしたとする。ｙは、それ自体と対をなし得ないことから、表におけるその表現は、ｘ以外の記憶装置からのアドレス範囲をそれに引き継がせることによって増やすしかない。追加のアドレス範囲再割り当てに対する同様な必要性は、新しい表を構築する際、アルゴリズムが不均一な対を生成すると生じる。
【００６０】
また、迅速な復旧制約条件は、新しい表が準備できるまで復旧が始まらないことから、サーバ又は記憶装置が故障した後、新しいルーティング表を迅速に利用可能にすべきであることを要求する。単一の故障の場合、全ての可能な故障に対する表は、事前に計算しキャッシュに入れることができる。複数の同時故障は、稀であると仮定される。従って、高速表生成は、データ喪失の予想頻度に大きく影響を及ぼさない。しかしながら、適度に速い表生成により、利便性及び検証可能性が増大する。記憶装置が離脱した後、新しい表が所定の位置に配置されるまで、クリークへの書き込みが抑制されるシステムでは、単一の故障事例用の少なくともキャッシング表が、重要な利用可能性の課題である。
【００６１】
逐次増大
最後に、記憶システムは、逐次増大をサポートしなければならない。このことは、表ベースの方式を用いることによって主にサポートされ、この場合、冗長構成要素に責任を負っている記憶装置を特定するのにかかる時間は、記憶装置付加及び除去の履歴から独立している。更に、等しいサイズのアドレス範囲を用いると、記憶装置が付加又は除去される際、記憶領域割当ての再構成が簡単になる。
【００６２】
他のデータ・アドレスベースの配分アルゴリズムと同様に、新しい記憶装置が付加される場合、一部の古いデータは、新しいハードウェアに移る。このことは、このデータを検索する負担もまた新しいハードウェアに移動するという利点を有する。システム性能に及ぼす記憶領域増大の影響は、所望の記憶領域均衡を達成するために、出来るだけ少ないデータを移動することによって最小化される。また、このことは、新しい記憶装置を付加する際、古い記憶装置間で記憶領域を不必要に再配分する割当てを回避する問題である。
【００６３】
記憶領域を付加する処理を図８に示す。記憶装置Ｄ＋１が、記憶システムに付加される場合、他の記憶装置に関連付けられたアドレス範囲の一部が、新しい記憶装置に再度割り当てられる。他の記憶装置に格納された冗長構成要素の対応する部分は、新しい記憶装置に通知される。この場合、構成要素は、再現されるよりもむしろ単にコピーし得るが、その処理は、この全ての通信に対して単一の出力先しかないため、故障した記憶装置からの復旧よりかなり遅い。記憶領域が付加されている間、復旧が続く場合、記憶装置Ｄ＋１上の構成要素の一部は、コピーされるよりもむしろ再現される。
【００６４】
ハードディスクドライブには、数ヶ月間続くことがある初期不良期間があることから、記憶容量を付加する場合、いずれかの初期未成熟期間中、新しい記憶装置の利用可能容量を一時的に低減することが望ましい。従って、これによって、新しい記憶装置が故障すると、復旧すべきデータがより少ないことから、復旧処理が速くなる。この一時的な低減は、ルーティング表生成中、利用可能容量を低減する未成熟期間制約条件を課すことによって、また、一旦未成熟期間が終わると、この制約条件なしで表を再度生成することによって、達成される。これは、（未成熟期間後）クリークに記憶装置を付加する段階には、新しい記憶装置を物理的に取り付ける段階を伴わず、むしろ、既存の記憶装置の生の容量を修正する段階だけを伴う場合である。
【００６５】
この考え方は、図５を参照して、図９に示す。図５の記憶システム＃１から始めて、３００ＧＢの生の容量を備えたサーバ３を付加する。これは、新しいハードウェアであることから、それに３０ＧＢだけの利用可能容量を割り当てるが、最大容量を付加することも可能である。サーバが活発に使用されたある初期不良期間の後、サーバ３には、３００ＧＢの利用可能容量が再度割り当てられ、その記憶領域割当てを支配するルーティング表が再計算される。これで、Ｒ＝２の図５の記憶システム＃２の状況になり、全サーバの最大容量が、利用可能である。
【００６６】
予定された記憶装置の付加及び除去時のアドレス範囲移行は、その範囲にある全てのデータの新しいコピーが行われる後まで、ソースデータを削除する必要がないため、安全性の課題ではないことに留意されたい。この場合、全てのデータ修正は、移行処理中、古い及び新しい場所双方に書き込まれる。
【００６７】
表の構成
便宜上、表は、２の累乗幅で構成される。これは、列番号としてのブロックアドレスのｌｏｇ２Ｗビットを用いて、表の照合を実施することを意味する。開示実施例において、ブロックアドレスの初期のセグメントが、このために用いられる。
【００６８】
表の各列は、対応するアドレス範囲に割り当てられたＲ台の記憶装置が順序よく並べられた一覧である。図５の記憶システム＃３用のサンプル表を図１０に示す。例示の目的のために、許容範囲Ｔを１０％に設定してある。この許容範囲が満たされることを保証するために、Ｗ＞＝Ｄ／ＲＴ＝４０／３でなければならず、従って、Ｗ＝１６を選択するが、これは、次に大きい２の累乗である。各列は、アドレス範囲で表記され、アドレス範囲に入る識別子を持つブロックのＲ個の冗長構成要素は、対応する列にリスト化されたＲ台の記憶装置に割り当てられる。理想的には、各記憶装置は、総利用可能容量の一部に厳密に整合する表の４８登録項目の一部を有すべきである。これら登録項目の理想的な数は、第１列にリスト化される（Ｐｉｊは、記憶装置が共に出現すべき理想的な回数であり、次節で議論する）。表に出現する各記憶装置の実際の回数は、第２列にリスト化されている。これらは、全て所定の理想的な許容範囲内にあることに留意されたい。最も過大表示の記憶装置は、記憶装置３又は記憶装置４のいずれかであり、各々３％過大表示されている。これらの内の１つが満杯である場合、クリークが満杯であると見なされる。各々１００ＧＢの容量及び１１の登録項目を有することから、各入力項目は、（１００／１１）ＧＢを表す。記憶領域が、表の表現に厳密に比例していると、表全体が、４８登録項目を有することから、表全体の利用可能容量は、４８（１００／１１）ＧＢ＝４３６．４ＧＢである。各記憶装置の利用可能容量は、同様に演算される。最大過大表示が３％である場合、利用可能容量は、理想的な最大値より３％小さい。
【００６９】
列に割り当てられたＲ台の各記憶装置は、Ｒ個の異なる役割（冗長構成要素＃０、冗長構成要素＃１等）の１つを果たす。幾つかの役割は、他の役割より多い格納作業を伴い得る（例えば、小さい番号の構成要素は、優先的に検索される可能性がある）ことから、列の記憶装置の作業負荷は、ブロックアドレスの一部に基づき、各ブロックアドレスに対してＲ台の記憶装置にＲ個の役割を擬似乱数により割り当てることによって等しくできる（開示実施例では、ブロックアドレスの第５バイトｂ５がこの目的のために用いられる）。従って、列ｋによって網羅されるアドレス範囲に入るブロックアドレス用の冗長構成要素ｎを保持するように割り当てられた記憶装置を見つけるには、以下のようになる。即ち、
ｓｔｏｒｅ＿ｆｏｒ＿ｒｅｄｕｎｄａｎｔ＿ｃｏｍｐｏｎｅｎｔ（ｎ）＝ｔａｂｌｅ＿ｅｎｔｒｙ（（ｂ５＋ｎ）ｍｏｄｕｌｏＲ，ｋ）。
【００７０】
記憶装置用の入力項目は、ブロックアドレス、構成要素番号、及びＲから直接特定される。
ルーティング表は、記憶容量の何らかの付加又は除去に応じて、変更されるものとする。新しく割り当てられた記憶装置上の冗長構成要素のコピー又は再生には、いくらか時間がかかることから、古い表の情報が適切なままである期間がある。例えば、新しい記憶装置が、システムに付加される場合、新しいハードウェア上に移行されるアドレス範囲の冗長構成要素は、古い表の入力項目に記録された記憶装置から供給され、新しい表の対応する入力項目に記録された記憶装置にコピーされる（新しい記憶装置は、同じ記憶の役割を引き継ぐ）。古い記憶装置に格納された冗長構成要素は、移転が完了するまで除去されない。一旦、アドレス範囲に対する権限／責任の移行（権限移転と呼ぶ）の全処理が完了すると、古い表は、廃棄してよい。
【００７１】
アルゴリズムに用いられる用語
・目標値
登録項目及び対の登録項目の分散用の目標値は、アルゴリズムによって明示的に用いられず、これらのための目標は、アルゴリズムの動作において良い又は悪いと見なされる選択において暗示的である。
【００７２】
記憶装置ｉ用の登録項目の数の目標値は、非整数値である
ｅｉ＝（ａｉ／Ａｔｏｔ）Ｅｔｏｔ
上式において、ａｉは、記憶装置の利用可能容量であり、Ａｔｏｔは、クリークの総利用可能容量（全ての記憶装置の利用可能容量の和に等しい）であり、Ｅｔｏｔは、表の登録項目の総数である（表幅Ｗ掛ける冗長構成要素の数Ｒに等しい）。従って、目標は、各記憶装置が、その総利用可能容量の分担に厳密に比例して表される目標である。上記したように、この目標値は、アドレス範囲の量子化のために、厳密に達成することはできないが、表が充分な登録項目を有する限り、浪費空間は、許容範囲Ｔ内に維持し得る。
【００７３】
記憶装置ｉが記憶装置ｊと対にされる回数の目標値は、近似的に以下の通りである。  Ｐｉｊ＝（ａｉ／Ａｔｏｔ）（ａｊ／Ａｔｏｔ）Ｅｔｏｔ（Ｒ−１）
全ての対が許される場合、（例えば）、ｊについてＰｉｊ／（Ｒ−１）を加算すると、ａｊ／Ａｔｏｔの加算を伴い、これによって１が与えられ、予想通り、ｅｉの定義そのものを得る。幾つかの対は、許されないことから、Ｐｉｊの幾つかの値は、強制的にゼロになり、他の対は、補正のために大きくしなければならない。しかしながら、許される対と比較して、許されない対の割合が小さい限り、これによって、許される対の理想的な分布に対する卓越した近似式が与えられる。Ｐｉｊの予想及び観察値を図１０に示す。許されない対の数は、本例において、記憶装置の数が少ない場合、極めて重要になる。
【００７４】
・過大及び過少表示
記憶装置ｉは、記憶装置ｉに対応する登録項目の実際の数ｅ＊ｉがｅｉより大きい場合、過大表示であると言われ、ｅ＊ｉが小さ過ぎる場合、記憶装置ｉは、過少表示であると言われる。記憶装置に配分されたデータの量が、それがルーティング表において有する登録項目の数に厳格に比例しているとすると、データがクリークに書き込まれる際、最大過大表示記憶装置が、最初に満杯になる。いずれかの記憶装置が満杯になると、クリークが満杯になったと解釈されることから、最大過大表示記憶装置は、クリークの総利用可能容量を限定する。
【００７５】
ｅ＊ｉは、整数であり、ｅｉはそうではないことから、記憶装置は、一般的に、過大表示されているか又は過少表示されているかのいずれかである。浪費空間の許容範囲Ｔが１％である場合、１％より少なく過大表示されている記憶装置は、いずれも総記憶容量を許容範囲内に制限しない。この理由により、過大及び過少表示は、常に、利用可能容量と比較して、分数として測定され、ｅ＊ｉ／ａｉ＞ｅ＊ｊ／ａｊである場合、記憶装置ｉは、ｊよりも過大表示されている。従って、記憶装置ｉは、記憶装置ｊよりかなり小さい場合、たとえルーティング表に追加の登録項目がほとんどなくても、記憶装置ｊより過大表示されることがある。アルゴリズムの本来の目的は、ｅ＊ｉ／ａｉの最大比をできるだけ小さくすることである。このことは、目標との比較を必要とせず、異なる記憶装置のこの比の値間の比較だけを必要とすることに留意されたい。表が充分な登録項目（Ｅ＞Ｄ／ＲＴ）を含む限り、最大過大表示は、許容範囲Ｔより少ないことが保証される。
【００７６】
同様に、ルーティング表において、どの対が最も過大又は過少表示されているか決定する際、記憶装置の相対的なサイズを考慮しなければならない。Ｅｔｏｔ、Ａｔｏｔ及びＲだけに依存するＰｉｊ／ａｉａｊの理想的な比が存在する。対の表示を比較する際、これらの比を比較する。また、根本的には、最も大きい過大表示を低減しようと努める。過大対は、復旧において、いずれかの記憶装置がその公平な分担を超える分担を提供することを要求することがあり、また更に、全ての記憶装置によって復旧において伝達されるアドレス範囲の総数を増やすことを要求することがある。ｅ＊ｉ／ａｉのように、目標との比較よりもむしろ、異なるｉ及びｊに対する対形成比の値間の比較が、用いられる。
【００７７】
・アルゴリズム
新しいルーティング表は、最初の近似として用いられる既存のルーティング表から開始して生成される。近似表は、登録項目を一度に１つ置き換えることによって、繰り返し更新される。どの記憶装置が対形成を許されるかに関する制約を侵害する変更は一切行われない。アルゴリズムの第１の目的は、最大限の利用可能容量を備えた表を生成することである。第２の目的は、最小限の量のアドレス範囲再構成でこれを達成することである。第３の目的は、記憶装置ができるだけ均等に対にされる表を生成することである。
【００７８】
これらの目的を達成するために、欲張りなアルゴリズムが用いられる。各ステップにおいて、最大過大表示記憶装置は、表のどこかで置き換えられる。最大過大表示を低減する置き換えだけが、実施される。より良い置き換えが、以前の置き換えに取って代わることがある。置き換え候補の間で選択肢がある場合、対形成が考慮される。結果を改善するために、将来の選択に対して最大の範囲を提供する置き換えを最初に試みることによって調査を進める。このアルゴリズムは、置き換えが最大過大表示をもはや低減する可能性がない時、終了する。
【００７９】
図１１は、ルーティング表更新アルゴリズムの擬似符号記述である。プログラムについて、一度に１節説明する。
【００８０】
【表１】
2009532812.tif 000004
更新を始める前に、変数ＯｌｄＴａｂｌｅ及びＮｅｗＴａｂｌｅを初期化する。クリークが新しい場合、それらは、双方共生成され、ＮＵＬＬＳＴＯＲＥと呼ばれる特別な入力項目が記入されるが、これは、容量ゼロの存在しない記憶装置を表す予備の記憶装置番号である。記憶装置は、既存のクリークから除去されつつある場合、ヌル記憶装置によって新表に再配置される。故障した（従って、どんなデータも供給できない）記憶装置もまた、ヌル記憶装置によって旧表に再配置される。
【００８１】
【表２】
2009532812.tif 000005
新しい表に表示される合計Ｄ台の記憶装置があり、また、Ｔの無駄な空間部分許容範囲がある場合、表の登録項目の数は、少なくともＤ／Ｔでなければならない。新表が小さ過ぎる場合、その幅は、それが充分広くなるまで、何回か２倍され、各倍増時、各アドレス範囲は、２つに分割され、各２分の一範囲に対する登録項目は、分割された範囲に対する登録項目と初期的に同じになる。表は、その最大幅に達すれば、分割されず、また、許容範囲制約条件は、もはや満たされる保証はない。１％の許容範囲の場合、百万の登録項目を備えた表は、最大１０，０００の記憶装置を表示するのに充分である。
【００８２】
【表３】
2009532812.tif 000006
アルゴリズムは、新表を一度に１つの入力項目変化させることによって機能する。どの記憶装置を置き換えるかの選択、それを何で置き換えるか、また、表中のどこで置き換えを行うかは、各置き換え後更新される統計値に基づき全て行う。用いられる統計値は、各記憶装置が出現する場所の登録項目の数、表における登録項目の総数、各記憶装置の利用可能容量、クリークの総利用可能容量、及び同じアドレス範囲において、各対の記憶装置が一緒に出現する回数である。これらの統計値は、アルゴリズムが始まる前、表にされる。
【００８３】
【表４】
2009532812.tif 000007
アルゴリズムは、新表に出現する全ての記憶装置用の識別子の一覧で機能する。この一覧表には、旧表に出現しないが、付加されつつある任意の記憶装置が含まれる。
【００８４】
【表５】
2009532812.tif 000008
表更新の途中から条件付きで終了させる。表を更に改善できない時、終了する。
【００８５】
【表６】
2009532812.tif 000009
クリーク全体の利用可能容量を制限するのは、最大過大表示記憶装置である（それが最初に満杯になる）。置き換えるべき対象（Ｔａｒｇｅｔ）として、これを選択する。
【００８６】
【表７】
2009532812.tif 000010
一覧表の代替記憶装置の候補は、初期的には、対象記憶装置を除く全ての記憶装置である。
【００８７】
【表８】
2009532812.tif 000011
列を更新するループの途中からの条件付き終了を可能にできる。代替品（Ｒｅｐｌａｃｅｍｅｎｔ）と、それを生成する場所を表中に見つけるとすぐに、新しい対象を選択できるように、直ちに終了する。
【００８８】
【表９】
2009532812.tif 000012
表の過大表示統計値を改善するものを見つけるか又は選択肢がなくなるまで、代替記憶装置の全ての可能な選択を考慮する。役に立つ代替品を見つけることができなければ、表の更新を終えた状態である。もう１つの代替品の例と１つ少ない対象の例があることが改善かどうか確認するために、もう１つの代替品の例を表に付加した場合、これによって、対象がそうであったよりも過大表示されないこと、
（ｅ＊代替品＋１）／ａ代替品）＜ｅ＊対象／ａ対象
であることを検証する。
【００８９】
記憶装置がＳ＿ｒから選択される順番は、表を生成するのにかかる時間を最小にするように、又は追加の制約条件を満たす際、見合った表現制約条件の影響を最小にするように調整し得る。最も迅速に表を生成するために、Ｓ＿ｒのどの要素を選択すべきかに対する優先順位は、
１）最も過少表示されている記憶装置
２）最も大きいサーバ上の最も大きい記憶装置
３）最小番号の記憶装置
である。
【００９０】
下位の優先順位により選択肢が唯一生成されていない場合、上位の優先順位だけを考慮する。Ｓの要素は、記憶サーバサイズによって並び替えて、（２）を更に効率的にすることができる。表の各記憶装置の比例した表現以外の制約条件を満たす必要がある場合、第１及び第２の優先順位を反転すると、アルゴリズムの後続のステップに最大の選択の余地が残る。
【００９１】
【表１０】
2009532812.tif 000013
代替候補記憶装置があることを念頭において、実際に、新表を見て、対象が発生し、対象を代替品で置き換えることが許される全ての列を見つける。置き換えを許さない唯一のものは、対形成制約条件の組である。これは、通常、同じサーバ上の２つの記憶装置は、同じ列に出現できないという制約条件であり、対象以外の記憶装置の内の１つが、同じサーバ上にある場合、その列は、許されない。
【００９２】
しかしながら、サーバの数がＲより小さいならば、対形成制約条件を緩めたいと考え得ることに留意されたい。例えば、緩い制約条件は、記憶装置が、同じ列に２度出現できないということであってよい。これによっても、故障した記憶装置からの復旧が可能である。制約条件は、表＿更新（ＵＰＤＡＴＥ＿ＴＡＢＬＥ）ループを始める前に、初期化中にのみ変更され、利用可能容量統計値の計算に反映される。
【００９３】
【表１１】
2009532812.tif 000014
候補列のリストに少なくとも１つのメンバを有する場合、最良のものを抜き出して置き換えを行う。リストが空である場合、列＿更新（ＵＰＤＡＴＥ＿ＣＯＬＵＭＮ）ループを継続して、まだ試みていない残りの記憶装置の一覧表Ｓ＿ｒから新しい代替記憶装置候補を見つけようと試みる。
【００９４】
リスト列に複数の選択肢がある場合、一連の優先順位を用いて、単一の列に選択肢を絞る。
１）以前の置き換えの結果として、対象が存在する列がある場合、その列に選択肢を絞る。これによって、余分な入力項目を変更することなく、置き換えが改善される。そのような列がない場合、選択肢を絞らない。
【００９５】
２）まだ単一の列に絞っていない場合、その時は、過剰対形成が最も低減される列を選択する。これは、最初に、置き換えが過剰対形成を悪化させない列を選択することによって行う。
【００９６】
各候補列について、列に出現する全ての記憶装置ｊに対する（Ｐ代替品ｊ＋１）／ａｊ）の最大値を計算する。この値が最小である列を選択する。
３）複数の列が同じ最小値を有する場合、次に、対象を除去することで過剰対形成が最も改善される列を選択する。
【００９７】
各候補列について、列に出現する全ての記憶装置ｊに対する（Ｐ対象ｊ−１）／ａｊ）の最大値を計算する。この値が最も大きい列を選択する。
４）複数の列がまだ残っている場合、最上位番号列を選択する。
【００９８】
より良い対の表が、絶対最小変更数（即ち、記憶装置間におけるデータの入れ替えが最小）の表より重要だと見なされる場合、（１）は、（３）の後に移すべきである。
最良の列を選択したら、新表の選択された列において代替品で対象を置き換えることによって変更を行う。ｅ＊代替品をインクレメントし、ｅ＊対象をデクレメントし、影響を受けたＰｉｊを更新する。列を正常に更新したことから、列＿更新ループを終了し、改善すべき他の対象を見つけに行く。
【００９９】
【表１２】
2009532812.tif 000015
ループで起こることに応じて、繰り返す又は終了する。
【０１００】
階層型記憶システム
記憶システムの規模が、単一の堅く結合されたグループのサーバによって、確実に保護される記憶領域の量（例えば、単一のネットワーク交換機にプラグ接続し得るサーバの数）を超過する場合、ルーティング表の階層構造を用いて、記憶領域及び冗長性を構成することができる。
【０１０１】
階層構造の各レベルにおける集合は、上述した通りに機能する。即ち、単一のルーティング表が、記憶システムのグループを支配して、そのグループに割り当てられたブロックをその構成要素間で配分する。階層構造における最下位レベルの構成要素は、ブロック記憶装置であり、次のレベルは、ブロック記憶装置のクリークであり、そして、クリークのクリーク等々である。ブロック記憶装置のサーバへのグループ化は、別個のレベルとは見なされないが、その代わり、第１集合レベルにおける表生成に関する追加の制約条件として取り扱われる。
【０１０２】
階層構造の各レベルにおいて、ルーティングに用いられるアドレスの不規則性が、独立であることを保証するために、ブロックアドレスの異なる部分が、各レベルで用いられる。このことは、図１２に示す。ここでは、２５６ビットブロックアドレスが、６つの３２ビットアドレスセグメントに分割され、最初の６４ビットは、ルーティングに用いられないため、各ブロック記憶装置は、ランダムな分布のブロックアドレスを見ることになる。各レベルのルーティングにおいて、異なるアドレスセグメントが、ルーティング表への索引付けのために用いられる。
【０１０３】
階層記憶システムは、当然、上から下に記載される。ここでの表記法では、Ｓを最上位レベルの記憶システムとし、Ｓを構成する第２レベル記憶システムのｉ番目をＳ［ｉ］とし、Ｓ［ｉ］のｊ番目の構成要素記憶システムをＳ［ｉ］［ｊ］などとする。この同じ表記法を用いて、Ｄが、Ｓを構成する第２レベル記憶システムの数であると、Ｄ［ｉ］は、Ｓ［ｉ］の構成要素の数であり、Ｄ［ｉ］［ｊ］は、Ｓ［ｉ］［ｊ］の構成要素の数であり、以下同様である。同様に、Ｒは、Ｓにおいて用いられる冗長構成要素の数であり、Ｒ［ｉ］は、Ｓ［ｉ］において用いられる数であり、Ａは、Ｓの（理想的な）総利用可能容量であり、Ａ［ｉ］は、Ｓ［ｉ］の（理想的な）総利用可能容量であり、以下同様である。
【０１０４】
１つのレベルに格納された各構成要素は、次のレベルにおいて、何らかのオーバーヘッドで冗長に符号化される。従って、最上位レベルＳにおいて見える使用可能な容量Ｃは、最上位レベルにおける冗長性によって用いられる記憶オーバーヘッドだけ実際の利用可能容量Ａ＊を減少させることによって、計算される。Ａ＊を計算する際、構成要素記憶システム［ｉ］の使用可能な容量Ｃ［ｉ］は、生の容量の役割を果たすが、この理由は、Ｓ［ｉ］内の構成要素を冗長に符号化するために用いられる記憶オーバーヘッドが、最上位レベルでは、使用可能な空間として出現しないためである。同様に、各レベルにおいて、構成要素記憶システムの使用可能な容量は、冗長性オーバーヘッドを差し引くことによって、その実際の利用可能容量から計算され、また、使用可能な容量は、集合の次のレベルにおける理想的な利用可能容量を計算する際、生の容量の役割を果たす。
【０１０５】
実際の記憶システムでは、通常、実際の利用可能容量と理想的な利用可能容量との間の差異を無視できるのに充分なほど小さくなるように、許容範囲Ｔを設定する。図１３に示す２つのレベルの階層記憶システムの例においてこれを仮定する。最上位レベルは、Ｄ＝２クリークを有し、Ｒ＝１構成要素が、各ブロックを表す。最上位レベルで冗長性がない場合、記憶領域は、２つのクリーク間で単に分割され、アドレス責任が、使用可能な容量Ｃ［１］＝４ＴＢ及びＣ［２］＝６ＴＢに比例して配分される。第２レベルにおいて、本例では、ブロックを表すＲ［ｉ］の冗長構成要素が、ブロックの完全な複製であると仮定する（図４、例１参照）。クリークＳ［１］は、Ｄ［１］＝１６の記憶装置を有し、各々５００ＧＢの容量であり、利用可能容量Ａ［１］＝８ＴＢを生成する。Ｒ［１］＝２（複製）であることから、使用可能な容量Ｃ［１］＝４ＴＢである。同様に、クリークＳ［２］は、Ｄ［２］＝２４の記憶装置を有し、各々７５０ＧＢの容量であり、１８ＴＢの利用可能容量を生成し、Ｒ［２］＝３（複製）であり、使用可能な容量が６ＴＢである。
【０１０６】
この階層表記に続き、新表は、Ｓ内において用いられるルーティング表であり、新表［ｉ］は、Ｓ［ｉ］内において用いられるルーティング表であり、以下同様である。新表は、Ｓを構成するＤの第２レベル記憶システム間で総アドレス空間を分割する。新表には、最上位レベル記憶システムが、その理想的な利用可能容量を許容範囲Ｔ内で実現できるように、少なくともＤ／Ｔ個の登録項目が含まれる。Ｓ［ｉ］の容量が増加する場合、アドレス範囲は、Ｓの他の構成要素記憶システムから移される。Ｒ＝１である場合、最上位レベルにおいて、１つの構成要素記憶システムが失われると、データは失われるが、各Ｓ［ｉ］の信頼度が充分に高い場合、これは、信頼度が高い構成のままである。上記したように、新表が再度生成され、いずれかのアドレス範囲に対する権限の移転を反映する場合、データが最初にコピーされ、そして、この移転が完了すると、もはや権限がないあらゆるＳ［ｉ］は、それが放棄した範囲用のデータを削除できる。Ｒ＞１である場合、最上位レベルの各ブロックは、複数のＳ［ｉ］上に冗長構成要素を格納することによって表される。
【０１０７】
第２レベルでは、Ｓ［ｉ］の新表［ｉ］は、Ｓ［ｉ］に割り当てられた全てのアドレスの空間を分割し、Ｓ［ｉ］を構成するＤ［ｉ］の記憶システムにアドレスを配分する。新表［ｉ］は、少なくともＤ［ｉ］／Ｔ個の登録項目を有する。新しいアドレス範囲が、新表において、構成要素記憶システム［ｉ］に割り当てられる場合、対応する構成要素が、そこに格納される。これらの構成要素は、Ｓ［ｉ］内において冗長に符号化され、結果的に生じる構成要素は、Ｓ［ｉ］を構成する構成要素記憶システム間で新表［ｉ］によって配分される。他のレベルは、同様に機能する。階層構造の異なる結合レベルにおけるルーティング表を索引付けするために用いられるアドレスセグメントの不規則性が、独立である（図１２）ことから、１つのレベルの構成要素記憶システムに割り当てられた各アドレス範囲は、次のレベルでそのレベルのアドレス範囲間において均等に分割される。
【０１０８】
複数のルーティング表を備えた階層記憶システムを図１４に示す。図の最上位レベルにおいて、３つの構成要素記憶システムがあり、容量は、２９１ＧＢ、４００ＧＢ、及び２００ＧＢであり、Ｒ＝２であり、全記憶システム用の理想的な利用可能容量８９１ＧＢを生成する。実際の利用可能容量８００ＧＢを与えるサンプルの最上位レベル新表が、示されている。一般的に、このように広い表は、約１９％を超えて理想的な値に近づくことが保証されない。Ｓ［１］に対する第２レベル新表［１］が、図１０に与えられている。Ｓ［１］の４３６ＧＢの実際の利用可能容量Ａ＊［１］は、その構成要素記憶システムの容量及びルーティング表の幅に依存する。１０２４列の広さであった新表［１］は、１パーセントの約１／１０内で、Ｓ［１］に対する理想的な４５０ＧＢの利用可能容量に届くことができたはずである。Ｓ［１］内の冗長性が、追加のパリティブロック（図４、第２例を参照）であると仮定すると、使用可能な容量Ｃ［１］は、Ａ＊［１］の２／３であり、このため、Ｃ［１］＝２９１ＧＢである。これは、最上位レベルにおいて実際の利用可能容量Ａ＊＝８００ＧＢを計算する際、生の容量の役割を果たす容量である（図１４）。最上位レベルルーティングは、Ｒ＝２（複製）を用いることから、示された記憶システムの使用可能な容量は、Ｃ＝４００ＧＢである。
【０１０９】
上記したように、ルーティングの各レベルは、ルーティング表の登録項目による記憶装置の表示に比例して各レベルの記憶装置にブロックを独立に配分するために、ブロックアドレスの異なるセグメントを用いて索引付けされている。図１４の例では、最上位レベルの３つの構成要素記憶システムは、３つの異なる深さにある。即ち、Ｓ［１］は、２つのルーティングレベルを有し、Ｓ［２］は、１つのルーティングレベルを有し、また、Ｓ［３］は、何も有さない。慣例によって、アドレスセグメントは、ルーティングレベルに対して、配分時に用い得る最小番号のセグメントを用いて、最下位から最上位レベルに配分される。従って、記憶システムが、図示のように最初定義された場合、Ｓ［１］［３］内におけるルーティングは、セグメント１を用い、Ｓ［１］内ではセグメント２、Ｓ［２］内ではセグメント１、及びＳ（全記憶システム）内ではセグメント３を用いる。他方、Ｓ［２］及びＳ［３］が元の記憶システムを構成し、また、Ｓ［１］が後で付加された場合、アドレスセグメントの配分は、異なる。即ち、Ｓ［２］内におけるルーティングは、セグメント１を用い、Ｓ内ではセグメント２、Ｓ［１］［３］内ではセグメント１、また、Ｓ［１］内ではセグメント３を用いる。この慣習により、記憶システム内において、それが階層的に大きくなる場合、不必要なブロック再配分が回避される。
【０１１０】
例えば、最上位レベルルーティングに用いられるセグメントにおいて値“０１１．．．１”及び第２レベルルーティングに用いられるセグメントにおいて“１１０１．．．０１１０００１１”のアドレスを有するＳに格納されるブロックについて考える。ここで、各レベルにおいて、セグメントアドレスの最後の８ビットが、役割番号を（上記したような固定バイトではなく）不規則化するために用いられると仮定する。最上位レベルにおいて、関心があるのは、役割０を果たす冗長構成要素であるものとする。図１４の新表によれば、この構成要素は、Ｓ［１］に割り当てられる。Ｓ［１］内において、この構成要素は、３つの新構成要素として符号化される（依然として、全て同じブロックアドレスを有する）。第２レベルでは、構成要素２に注目するものとする。“０１１０００１１”は、０モジュロ３に等しいことから、構成要素２は、図１０の新表［１］によって、Ｓ［１］［４］に割り当てられる。
【０１１１】
図１４に示す階層システムにおいて、階層構造の葉ノードは、ブロック記憶装置、即ち、Ｓ［１］［１］、Ｓ［１］［２］、Ｓ［１］［３］［１］、Ｓ［１］［３］［２］、Ｓ［１］［４］、Ｓ［２］［１］、Ｓ［２］［２］及びＳ［３］である。ブロックアドレスの別個のセグメントが、階層構造の各レベルにおけるアドレス範囲を定義するために用いられることから、任意のレベルにおけるルーティングに用いられる任意のアドレス範囲は、ブロックアドレス特定部における特定のパターンのビットに対応し、アドレスの他の部分に制約はない。例えば、図１４の新表のアドレス範囲“０１１．．．”に割り当てられた全ての構成要素は、最上位レベルルーティングに用いられるアドレスセグメントの最初の３ビットとして、パターン“０１１”を有する。従って、任意のレベルにおける任意の構成要素記憶システムが、アドレス範囲に対する責任を失う場合、ビットパターンマスクは、階層的にずっと下りそのブロック記憶装置に渡され、それらが、指定パターンを含む名前を備えたあらゆるブロックを削除し得ることをそれらに告げることができる。同様に、アドレス範囲におけるブロックの名前のリストが必要な場合、対応するビットパターンは、ブロック記憶装置レベルに渡され、リストを戻すことができる。
【０１１２】
階層記憶システムの上記議論は、マーゴラス（Ｍａｒｇｏｌｕｓ）らによる、「コンピュータ記憶システムにおける履歴保存」と題された関連特許出願米国第２００４／０１６７８９８Ａ１号明細書に該当し、これは、本明細書に参照によって組み込まれる。ここで記載した各レベルの階層構造には、関連する用途において説明した種類の保護を実現し得る分散式記憶システムが含まれる。ルーティング表は、どの記憶装置構成要素が、他の記憶装置構成要素用の冗長情報を保持する責任を負っているかを単に指定する。個々の記憶構成要素の妥協点を検出するために、読み出しには、異なる構成要素に格納された充分な冗長構成要素を読み出し、読み出したデータの完全性を検証する段階を伴い得る。問題が、検出されると、追加構成要素を読み出して、問題がどこにあるか決定し得る。
【０１１３】
冗長構成要素の符号化及び用途
クリークに格納されたブロックは、ハードウェア故障の場合、失われた構成要素を復旧させるために、ある数の冗長構成要素によって表される。アクセス又は復旧の目的で元のブロックを再構築するために、ルーティング表を用いた処理は、構成要素によって用いられる符号化を知る必要がある。ここでは、上述したルーティング表構成によってサポートされる幾つかの符号化の形態及び用途について議論し、特に、分散型記憶用途に良く適合する２つの新しい種類の符号化に焦点をあてる。
【０１１４】
同一複製
最も単純な冗長符号化は、複製である。即ち、格納されたブロックを表す各冗長構成要素は、ブロック全体の完全なコピーである。Ｒ＝２の場合、これは、本質的に、冗長性の唯一の可能な形態であるが、その理由は、２つの冗長構成要素の一方の喪失に耐え得ることは、各構成要素が、元のブロックの全ての情報を符号化しなければならないことを意味する。
【０１１５】
複製の記憶領域は、簡潔さという利点を有し、また、単一のハードウェア故障からの素早い復旧を可能にするが、その理由は、冗長構成要素から格納されたブロックの再構築のために、計算作業が不要なためである。その不利な点として、Ｒ−１の同時ハードウェア故障に耐える能力は、単一の全てのコピーに必要とされるよりもＲ倍の記憶領域を用いることを要求する。
【０１１６】
複製された記憶領域の場合、故障からの復旧は、失われたアドレス範囲の供給元を最初に識別することによって、また、新しく権限が与えられた記憶装置にデータをコピーすることによって進む。新表の各列の場合、新しい登録項目は、対応するアドレス範囲に新しく権限が与えられた記憶装置を表す。どの登録項目が新しいかは、新表を旧表と比較することによって決定し得る。新表が広げられた場合、旧表の各列は、新表の複数の列に対応する。故障した記憶装置は、旧表のヌル記憶装置によって表され、従って、どの記憶装置が、有効なコピー元かは、常に明確である。記憶装置が、計画的に除去された（制御された離脱と呼ぶ）場合、除去された記憶装置の登録項目は、旧表に残るが、新表には、残らない。
【０１１７】
追加の故障の場合の堅牢さについては、新表又は旧表のいずれかにおいて、アドレス範囲に割り当てられた全記憶装置に全ての新しい書き込みを複製することが、便利である。一旦、全ての新しく割り当てられた記憶装置が、それらに割り当てられた全ての冗長構成要素のコピーを有すると、権限移転の処理が完了する。即ち、新表が旧表にコピーされ、また、それらに対して権限がない記憶装置に常駐する任意の冗長構成要素は、廃棄し得る。権限移転中、追加の故障がある場合、旧表は、変更されないが、新表は、上記のアルゴリズムを用いて、修正される。旧表と新表との間で異なる各入力項目の場合、新しく権限が与えられた記憶装置にまだ移行されていない冗長構成要素だけを移行する必要がある。
【０１１８】
消去順応符号化
大きな記憶空間を追加して用いることなく、記憶装置における耐障害性を高くするために広く用いられる冗長方式は、パリティＲＡＩＤである。この方式では、保護される各データブロックが、等しいサイズのＮの部分に分割される。１つの追加な構成要素が生成されるが、この場合、その各ビットは、元のＮ部分の対応するビットの和、モジュロ２である。これらＮ＋１の構成要素は、この時点で冗長である。即ち、それらの内のいずれか１つが失われると、それは、残りのＮ構成要素の対応するビット、モジュロ２を加算することによって再構築し得る。Ｎ＋１の冗長構成要素は、Ｎ＋１の別個のハードウェアに格納される。記憶システムに書き込まれる全てのデータブロックは、このようにして保護される。別個のハードウェアの内のいずれか１つが故障した場合、記憶システムに書き込まれた全てのデータブロックは、再構築し得る。
【０１１９】
パリティＲＡＩＤは、消去順応符号化の例である。一般的に、データブロックは、Ｎ部分に分割され、そして、Ｍの追加構成要素が、元のＮから生成される。Ｎ＋Ｍ冗長構成要素の内のＭまでを消去可能であり、符号化によって、それらは、残りの構成要素から再構築される。幾つかの消去順応方式の場合、任意のＭ構成要素を消去し復旧することができる。他の幾つかの方式は、Ｍの喪失構成要素の幾つかの組合せを復旧不可能にし、その代わり、保証の程度を軽減することによって、符号化／復号化の労力を低減する。例えば、場合によっては、他のものを再構築するために、Ｎを超える構成要素が必要である。
【０１２０】
広く用いられる消去順応方式は、元のデータブロックのＮ部分が、Ｎの冗長構成要素として用いられるという制約条件を課す。このことは、構成要素が消去されていない（即ち、ハードウェアが故障していない）場合、元のブロックは、余分な計算労力なしで、単にこれらのＮ部分にアクセスすることによって再構築し得ることを意味する。広く用いられる全ての消去順応方式において課される他の制約条件は、元の及び導出された構成要素の双方共、全ての構成要素が、同じサイズであることである。このサイズの制約条件は、可変サイズのチャンクデータを格納させるシステムでは、不必要である。（固定チャンクサイズのシステムにおいてさえ、単に、格納された各チャンクのサイズをわずかに大きくして、それらの幾つかに余分なデータを収容することが、可能な場合がある。）従って、このサイズ制約条件に従わない方式について考える。
【０１２１】
どのＮ＋Ｍ符号化が用いられるかにかかわらず、それがルーティング表と対話する方法は、本質的に同じである。故障が起こっていない場合、未符号化の最初のＮ構成要素の１つ又は複数は、格納されたブロックの全て又は一部を読み出せという要求に応じて読み出される。ブロックアドレスの一部を用いて記憶装置に構成要素の役割を割り当てると、この不均一な構成要素の使用によって暗に示される作業負荷が均一になる。故障が取り扱われる方法は、同一複製の場合とほとんど同じであるが、幾つかの重要な相違点がある。
【０１２２】
記憶装置が、付加又は除去されたが、記憶装置が故障していない場合、権限移転処理は、対応する構成要素のコピー処理だけを必要とする。即ち、１つの記憶装置は、列中の他の記憶装置のスロットを引き継ぎ、また、置き換えられる記憶装置に属する対応するアドレス範囲用の全てのブロックを得る。このことは、ちょうどコピー処理であり、本質的に、同一複製の場合に起こることと異ならない。
【０１２３】
１つ又は複数の記憶装置が故障した場合、欠落冗長構成要素は、残りの構成要素から再現されなければならない。以前と同様に、新表のどの登録項目が新しいかは、旧表との比較によって決定される。一般的に、記憶装置に新しく割り当てられた各アドレス範囲の場合、同じアドレス範囲に責任を負っている他の記憶装置のＮからのそのアドレス範囲用の全ての冗長構成要素は、新しい記憶装置に移行しなければならない。これによって、新しい記憶装置は、そのアドレス範囲用の格納された元の全ブロックを再構築し、また、これらから、それが格納の責任を負っている１つの冗長構成要素を構築しる。
【０１２４】
従って、復旧中、記憶装置に割り当てられた各新しいアドレス範囲に対して、記憶装置は、それが恒久的に保持する責任を負っている各々に対してＮ個の構成要素を一時的に蓄積しなければならない。この一時的な記憶要件は、様々なやり方で取り扱い得る。本開示実施例において、余分な記憶装置は、単に回避される。全てのＮの供給元から一度に全ての構成要素を受け取る代わりに、新しく割り当てられた記憶装置は、唯１つの供給元から全ての構成要素を最初に受け取り、これらを格納する。これによって、それが必要とする全てのブロックアドレスの完全な一覧が新しい記憶装置に提供され、各ブロックの単一の構成要素用の記憶空間だけを占める。そして、新しい記憶装置は、これらの各構成要素を一度に１つ処理し、同一ブロック用の他のＮ−１個の構成要素を要求し、欠落構成要素を再構築し、それを格納する。そのままの状態の各ブロックの冗長構成要素は、この復旧処理中の更なる故障からシステムを保護する。
【０１２５】
単純な消去順応符号化
複数の消去に耐えるように構成された従来の線形符号は、単純なパリティ符号よりもっと複雑である。それらは、従来のコンピュータハードウェアによって直接サポートされない有限体演算に基づく。一実施例において、普通の算術、論理、及び桁送りだけを用いる更に単純な符号化を利用し、全構成要素を大きな整数として処理する。冗長性を与えるために付加される追加構成要素は、場合によっては、他の構成要素より数ビット大きい。これらの符号は、符号化及び復号化双方に対して効率的である。アルゴリズム及び関連する数学的処理の簡単さは、実行及び試験にとって利点である。
【０１２６】
例
単純な例として、Ｎ＋Ｍ＝２＋２符号について考える。符号化される各データブロックをＡ及びＢの半分に２等分するものとする。Ａ及びＢを大きな整数であると解釈すると、２つの追加構成要素Ｘ及びＹを構築し得る。即ち、
Ｘ＝Ａ＋Ｂ
Ｙ＝Ａ−Ｂ
上式において、＋及び−は、普通の２の補数算術演算である。構成要素は、希望通りの大きさであってよい。Ａ及びＢが、ｎビット長である場合、Ｘ及びＹは、ｎ＋１ビット長である必要がある。ｎビット構成要素が、ブロックタイプで表記される場合、余分なビットは、ブロックタイプに吸収してよい。Ｘ及びＹは、喪失した場合、加算及び減算だけを用いて、Ａ及びＢから再計算される。更に、Ａ及びＢは、喪失した場合、
Ａ＝（Ｘ＋Ｙ）／２
Ｂ＝（Ｘ−Ｙ）／２
であることから、加算、減算、及び桁送り（２による除算）だけを用いて、再構築することができる。Ａ及びＢが、喪失した場合、
Ａ＝Ｙ＋Ｂ
Ｘ＝Ｙ＋２Ｂ
であり、他の場合も同様である。構成要素を組み合わせるために用いられる係数が小さい整数である限り、係数乗算は、少ない数の加算及び桁送り演算によって実現し得る。２の累乗の係数だけが用いられる場合、符号化には、桁送り及び加算だけが必要である。
【０１２７】
更に大きな例
符号化されるデータブロックが、４つの等しいサイズの構成要素｛Ａ、Ｂ、Ｃ、Ｄ｝に分割され、これらから、最大４つの追加構成要素｛Ｗ、Ｘ、Ｙ、Ｚ｝を次のように構築する。即ち、
【０１２８】
【数２】
2009532812.tif 000016
これら４つの式は、線形独立であり、任意の行（Ｗ、Ｘ、Ｙ又はＺ）及び任意の列（Ａ、Ｂ、Ｃ又はＤ）を省略すると、線形独立の組が生成され、任意の２つの行及び任意の２つの列を省略すると、線形独立の組が生成される。従って、８つの構成要素のいずれか４つが、欠落している場合、他の４つについて解くことができる。例えば、Ｗ、Ｘ、Ｂ及びＣが欠落している場合、最初は、Ｗ及びＸの式を無視し、そして、Ｙ及びＺの式を用いて、Ｂ及びＣ（２つの式、２つの未知数）について解く。そして、最初の２つの式を用いて、Ｗ及びＸを再構築する。４つより少ない追加構成要素を構築したい場合、これらの式の内の一部だけ用いる。この例は、各追加構成要素Ｗ、Ｘ、Ｙ及びＺが、元のブロック、Ａ、Ｂ、Ｃ、及びＤのものより４ビット長いことが必要である。
【０１２９】
任意のサイズの標準的な例
Ｍ個の線形式の組は、全構成要素が、それらの任意のＮ個から再構築される限り、消去符号の一部として用いられるＭ個の追加構成要素を生成する。このことは、係数行列の各正方部分行列（即ち、行及び列を省くことによって形成される各正方行列）が、線形独立行を有する限り該当する。Ｎが素数である場合、これらの式の任意の部分集合、
【０１３０】
【数３】
2009532812.tif 000017
が機能し、希望通りの大きさのＮについて２の累乗の係数を備えた例を与える。例えば、Ｎ＝５の場合、この正準式は、以下の式を生成する。
【０１３１】
【数４】
2009532812.tif 000018
５＋３符号の場合、最初の３行だけを用い得る。３＋５符号の場合、Ｂ３及びＢ４を常にゼロであると見なし得る。このように列を省略することによっても、Ｂｊの非素数用の符号を構築するための系統だった方法が提供される。
【０１３２】
係数に行列として現れる指数だけを一覧表示することによって、Ｎ＝５例を表現し得る。
０００００
０１２３４
０２４１３
０３１４２
０４３２１
同様に、Ｎの任意の素数値について、Ｘｋの正準式は、第１行及び第１列が全てゼロである指数の行列を生成する。第１行及び列を除外することによって、より単純な組のＮの係数で素数より１小さいものを導出することができ、そして、残りの全ての係数は、２によって除算可能であるため、他の全ての指数を１だけ低減し得る。従って、Ｎ＝４の正準指数の縮小行列は、以下のようになる。
【０１３３】
０１２３
１３０２
２０３１
３２１０
これは、ちょうど前節からの４＋４例の書き直しである。
【０１３４】
更なる簡略化として、Ｎの正準指数の縮小行列で素数より１小さいものを選択し、任意の単一の行（又は列）をゼロの行（又は列）によって置き換えて、追加構成要素を構築するための桁送りが少ない縮約行列を得ることができる。
【０１３５】
０１２３
１３０２
００００
３２１０
真ん中の行を置き換える限り、これら全ての行列は、｛０、１、２、．．．｝の第１行、この行の反転である最後の行、及び全てゼロである他の幾つかの行を有することに留意されたい。これら３種類の行だけを用いて、任意のＮに対するＭ＝３についての符号を構築することができる。即ち、
【０１３６】
【数５】
2009532812.tif 000019
例えば、Ｎ＝１２及びＭ＝３について考える。この場合、Ｘ０は、Ｂｉより４ビット長いく、Ｘ１及びＸ２は、各々、１２ビット長い。Ｍ＝２及び任意のＮの場合、これらの式の最初の２つだけを用いる。指数の正準行列の第１、第２、及び最後の行を用いると、Ｍ＝３の場合、ほとんど同じ符号を生成するが、最後の行が１つの位置だけ回転されていることに留意されたい。この他の選択肢肢としての符号は、任意の奇数のＮに適するが、偶数のＮには適さない。
【０１３７】
また、上記例のいずれかの転置行列を用いることができる。例えば、任意のＮ＋３用の符号を構築するための方法は、任意の３＋Ｍ用の符号を構築するためにも用い得る。これら指数のどの行列においても、全ての要素に定数を加算するか、又は、全ての要素に定数の係数を乗算することができる。正の２の累乗係数を備えた符号の幾つかの他の例を図１５に示す。第２例（３＋３）は、上記の一般的なＮ＋３符号より１つ少ない桁送りを符号化のために用いることに留意されたい。最後の例（３＋６）は、ブロックを９つに符号化し、その内の任意の３つが、ブロックの復旧には充分である。この符号は、ブロックの３つの複製を格納するのに必要な場合と同じ量の記憶空間を用いて、６つの故障に耐え得るが、３重の複製は、２つの故障にのみ耐えることが可能である。第２の最後の例（６＋３）は、通常、より良い記憶妥協案である。これは、３＋６例と厳密に同じ数の冗長構成要素を生成するが、この冗長性によって用いられる追加の空間は、２００％ではなく、ブロックサイズの５０％だけである。この符号は、３つの同時故障に耐え得る。
【０１３８】
小さい符号付き係数
場合によっては、正の数だけであるよりは、むしろ小さい符号付き係数を用いることに利点があり得る。例えば、
【０１３９】
【数６】
2009532812.tif 000020
これを前出の例と比較する。
【０１４０】
【数７】
2009532812.tif 000021
双方の場合において、全ての係数は、２の累乗であり、従って、各乗算は、単一の桁送り演算で実施し得る。最初の場合、桁送りは、若干小さい。用いる係数値の数が少ないと、有益な場合がある。例えば、上記最初の組の式において、２５６で２を置き換えると、以下の通りになり、
【０１４１】
【数８】
2009532812.tif 000022
依然として、８つの冗長構成要素の内の任意の４つについて、他のものの関数として解くことができる。この場合の全ての桁送りは、全バイト量だけであり、従って、バイトアドレス指定によって実施し得る。この場合、バイトアドレス指定が効率的であれば、符号化処理は、各追加構成要素について、ほぼＡ、Ｂ、Ｃ及びＤを一度加算するだけの場合と同様に速くできる。元のブロックが、各々ｎビット長である場合、Ｗは、ｎ＋２ビットであり、Ｘ、Ｙ及びＺは、各々ｎ＋１０ビットである。
【０１４２】
一般的に、上記任意の２の累乗の例における指数には、バイト桁送りが速くなるか又は便利になり、余分な記憶オーバーヘッドが許容可能であれば、３を乗ずることができる。
復号化の効率
上記したように、冗長構成要素が失われていない場合、元のブロックの未符号化部分（即ち、Ａ、Ｂ、Ｃ及びＤ）が、検索され、ブロックの再構築に関与する追加の作業はない。幾つかの冗長構成要素が失われた場合、一般的に、欠落構成要素を求めるには、小さい整数による除算が伴う。例えば、
Ｗ＝Ａ＋Ｂ＋Ｃ＋Ｄ
Ｘ＝Ａ＋２Ｂ−２Ｃ−Ｄ
であり、Ｂ及びＣ双方が、失われ復旧が必要な場合、以下の様になる。
【０１４３】
４Ｂ＝２Ｗ＋Ｘ−３Ａ−Ｄ
従って、Ｂは、２Ｗ＋Ｘ−３Ａ−Ｄの和を４で除算することによって復旧し得る。この場合、除算は、単純な桁送り演算によって線形時間で実施し得る（ブロックＢのサイズにおいて）。しかしながら、Ａ及びＣが欠落している場合、以下のようになることが分かる。
【０１４４】
３Ａ＝２Ｗ＋Ｘ−４Ｂ−Ｄ
従って、Ａの復旧には、３での除算の実施を伴う。しかしながら、これは、小さい整数ｍによるｎビット数の除算は、一般的に、（ｍのサイズに依存して）ｎｌｏｇｎのオーダの時間で実施されることから、効率の問題ではない。これが仮定することは、この事例のように、対象の数が、ｍによって厳密に割り切れることである。例えば、加算すると３Ａになるあるものの３による除算は、乗算によって実施し得る。
【０１４５】
（３＿Ａ）／３＝−（３＿Ａ）＊（−１／３）
２の補数表記法において、−１は、２進数で全て１であるｎビット数である（これは、１を加えるとゼロになる数）である。従って、−１／３は、
１１１１１１．．．１１／１１＝０１０１０１．．．０１
であり、そして、規則的な繰り返しパターンのため、−１／３による−（３＿Ａ）の乗算は、ｌｏｇｎ桁送り及び加算で実施でき、Ａが与えられる。
【０１４６】
ちょうど１０進数の算術の場合と同じように、有理分数は、常に、繰り返しパターンを有し、従って、常に、ｍによる除算の代わりに、−１／ｍを乗じて、除算からの繰り返しパターンが、偶数回繰り返すように、ｎの値を少し大きくできる。ｍが２の累乗から１だけ異なる（即ち、いずれかのｊの場合の）幾つかの例を一覧で表す。
【０１４７】
−１／３＝０１０１．．．０１
−１／５＝００１１００１１．．．００１１
−１／７＝００１００１．．．００１
−１／９＝０００１１１０００１１１．．．０００１１１
−１／２５５＝０００００００１０００００００１．．．０００００００１
−１／２５７＝００００００００１１１１１１１１００００００００１１１１１１１１．．．００００００００１１１１１１１１
ここで、各式の左辺は、１０進数であり、右辺は、２進数である。
【０１４８】
ｍ＝２ｊ−１の場合、ｊ−１のゼロからなり単一の１が続くｊビットパターンの繰り返しを得ること、また、ｍ＝２ｊ＋１の場合、ｊの１と交互に出現するｊのゼロの繰り返しを得ることに留意されたい。ｍ＝２５５及びｍ＝２５７の場合は、Ｎ＋Ｍ＝４＋２の場合に用いられる符号化を反転するために（桁送り以外に）必要とされるものだけであり、
Ｗ＝１Ａ＋１Ｂ＋１Ｃ＋１Ｄ
Ｘ＝１Ａ＋２５６Ｂ−２５６Ｃ−１Ｄ
である。
【０１４９】
ＸＯＲ符号化
符号化又は復号化を速くするために、追加構成要素のサイズをわずかに膨らませる他の単純な消去順応符号化方式がある。他の選択肢肢としての魅力的な符号化は、対応するビットの和モジュロ２（ｓｕｍ−ｍｏｄ−２）（プラス桁送り）で整数の加算（プラス桁送り）を単に置き換える。
【０１５０】
正の２の累乗係数の上記全算術符号化例では、係数が変更されず、和のプラス演算が、対応するビットの和モジュロ２で置き換えられる（また、乗算がそのままである）場合、これらの例は、計算が簡単で、また、反転が簡単なままである。これには、２の累乗係数、低減された及び簡略化した変量等について標準公式から導出する全ての例が含まれる。図１５からの第３例、
Ｘ＝Ａ＋Ｂ＋Ｃ＋Ｄ
Ｙ＝Ａ＋２Ｂ＋４Ｃ＋８Ｄ
について考える。
【０１５１】
乗算は、依然として桁送りであり、加算は、今度は、ＸＯＲ演算である。この場合、Ｘは、それが構築された構成要素と厳密に同じサイズであり、Ｙは、３ビット大きい。Ａ及びＢが失われた場合、
Ｘ’＝Ｘ＋Ｃ＋Ｄ、及び
Ｙ’＝Ｙ＋４Ｃ＋８Ｄ
とする。
【０１５２】
これらは、残りの構成要素から簡単に計算される。従って、
Ｘ’＝Ａ＋Ｂ、及び
Ｙ’＝Ａ＋２Ｂ
従って、
Ｘ’＋Ｙ’＝Ｂ＋２Ｂ
また、Ｂのビットが、｛ｂ０、ｂ１、ｂ２、．．．｝である場合、Ｂ＋２Ｂのビットは、｛ｂ０、ｂ０＋ｂ１、ｂ１＋ｂ２、ｂ２＋ｂ３、．．．｝である。従って、Ｂは、Ｂ＋２Ｂの第１ビットを第２のビットに加算し、その結果を第３ビットに、その結果を第４ビットに、以下同様に加算することによって、復旧される。従って、Ａは、Ａ＝Ｘ’＋Ｂを用いて復旧することができる。他の任意の対のブロックは、喪失している場合、同様なやり方で再構築し得る。任意の数の係数の一般的な場合は、同様であり、また、識別Ｚ＋Ｚ＝０を用いて、複数の式を足し合わせて、１つのブロックの桁送りの和だけが残るまで、項を消去することによって解くことができる。従って、そのブロックのビットは、上記Ｂのビットと同様なやり方で計算される。
【０１５３】
このＸＯＲ方式において、以前と同様に、ビット桁送りをバイト又はワード桁送りで置き換えると、追加構成要素の記憶空間の浪費がわずかに多くなるという犠牲を払って、符号化及び復号化が速くなることに留意されたい。
【０１５４】
更に、この方式では、２の累乗ではない係数を用いることができることに留意されたい。例えば、＋をＸＯＲのままとして、３Ｂ＝（１＋２）Ｂ＝Ｂ＋２Ｂと定義する。一般的に、｛ｃ０、ｃ１、．．．｝が、数Ｃの２進数表現のビットである場合、
Ｃ＝ｃ０＋ｃ１２１＋ｃ２２２＋．．．
が成り立つ。
【０１５５】
上式において、＋は、ビット毎のＸＯＲである。以前と同様に、２の累乗の場合、２ｉ＊２ｊ＝２ｉ＋ｊである。２の累乗でない場合、この表現を分配法則及び加算則と組み合わせることによって、乗算用の規則を定義する。例えば、２＋２＝０であることから、３＊３＝（１＋２）（１＋２）＝１＋２＋２＋４＝５である。従って、３（３Ｂ）＝５Ｂである。加算及び乗算は、双方共、交換及び結合可能であり、更に、乗算は、加算に分配する。この数学的な構造は、単位元を有する可換環と呼ばれ、それは、多くの点で、整数の普通の加算及び乗算の様に振舞う。例えば、前節で定義された基準係数の行列に整数Ｂｊのベクトルを乗算すると、追加構成要素Ｘｋのベクトルが、
【０１５６】
【数９】
2009532812.tif 000023
と生成される。
【０１５７】
上式において、総和中の加算は、ここでは、ＸＯＲである（しかし、係数を定義する指数中の算術は、変わらない）。係数の行列（又はその正方部分行列）は、行列式を（この環について）計算し、また、それがゼロ以外であることを確認することによって、線形独立行を有することが分かる。
【０１５８】
この符号化には、繰り上がる数が関与しないことから、普通の加算を用いるものより簡単に平行化される。復号化は、全てのＮについて線形である。
復号化は、図１６の通常の算術及びビット毎ＸＯＲ方式の場合、３＋３符号と比較されるが、これは、いずれの方式と分け隔てなく用い得る。Ｘｉは、ブロックＢを３つの部分に分割し、また、それらを足し合わせることによって２の累乗係数で構成される。ブロックＢの全ての３つの部分が喪失し再構築される必要がある場合の復号化を示す。ガウスの消去法によってＢ１を再構築するのに必要な係数に対する演算の数は、双方の場合で同じである。算術の場合における最後のステップは、６による除算である（これは、本質的に３による除算と同じ作業である）。ビット毎ＸＯＲの場合では、最後のステップは、Ｂの２つの桁送りされた複製のＸＯＲを分離することであり、これについては、前出の例において既に議論した。Ｂの３つ以上の桁送りされた複製を分離することは、あまり大変な作業ではない。
【０１５９】
性能比較
本記憶領域クラスタ化用途の場合、実用的なブロックサイズは、相対的に大きく（数キロバイト）、消去符号は、システムが、失われた構成要素を再現する間、わずかに起こる新しい故障を乗り越えるのに充分なほど堅牢でなければならない。追加構成要素用の許容可能な記憶オーバーヘッドは、１０％と１００％との間の範囲である。
【０１６０】
これらの制約条件の場合、Ｎ及びＭの値が相対的に小さいＮ＋Ｍ消去符号は、最大の関心の的であり、失われた構成要素の全ての可能な組合せ用の式は、事前に計算される。例えば、Ｂ２及びＢ５が失われている場合、Ｂ２を再構築するための公式は、
７Ｂ２＝１２Ｂ１＋１０Ｂ３＋３Ｂ４
のようであってよい。
【０１６１】
従って、唯一の適切な性能パラメータは、構成要素を符号化する（即ち、Ｘｋを計算する）のに必要な時間及び残りの構成要素から欠落構成要素を復号するのに必要な時間である。
【０１６２】
符号化の場合、算術及びＸＯＲ符号は、双方共、符号化行列における全ての係数が、２の累乗（即ち、桁送り）である場合、本質的に最適なＮ＋Ｍ消去符号である。桁送りをバイト又はワードの倍数にすると、ある程度有益なことがあるが、最近のＣＰＵは、単一の機械命令において任意の量だけのワードの桁送りが可能であることから、利点は、小さい。バイト又はワードの倍数の桁送りをアドレス指定によって行うと、各Ｘｋの符号化には、符号化されるブロックをメモリから読み出し、結果的に生じる構成要素をメモリに書き戻すのに必要な時間とほぼ同じ時間がかかる。
【０１６３】
復号化は、２つのステップを伴う。即ち、残りの構成要素から欠落構成要素の倍数を計算する段階（例えば、上記例では、１２Ｂ１＋１０Ｂ３＋３Ｂ４の加算）と、次に倍数から欠落構成要素を再構築する段階（例えば、本例では、Ｂ２の７による除算）とを伴う。
【０１６４】
欠落構成要素の倍数の計算は、算術及びＸＯＲ事例の双方において、極めて良く似おり、残りの構成要素の項による式の値が求められる。係数が小さい場合、乗算に対して、桁送り及び加算を用いることは、有益である。係数が、全てほぼ同じサイズである場合、各係数中の１の数がほぼｌｏｇ（ｍ）であると推定されるが、ここで、ｍは、評価される式中の欠落構成要素の係数である。Ｎ個の残りの構成要素は、任意の欠落構成要素を再現するのに充分であることから、このステップにかかる時間は、構成要素をコピーする時間のＮｌｏｇ（ｍ）倍より小さい。Ｎの同様な値の間、構成要素は、全て並行に走査することが可能であり、ウィンドウ分のデータがレジスタにバッファされ、結果のワードは、メモリに書き戻される。この場合、メモリ動作と比較したレジスタ動作の速さのために、所要時間は、Ｎ個の全ての必要な構成要素を単に読み出して、結果を書き込むのに必要な時間に近いと思われる。
【０１６５】
構成要素の既知の倍数から欠落構成要素を再構築する場合、算術及びＸＯＲの事例は、異なる。算術の場合、小さい係数ｍによる除算を構成要素と同じ長さの整数による乗算に変換し、ｍとほぼ同じ長さのパターンを繰り返す。桁送り及び加算を用いたこのパターンによる一度の乗算には、構成要素をコピーするｌｏｇ（ｍ）倍以下しかかからない。また、この動作は、乗算される構成要素全体を一度走査することによって実施し、構成要素の幾つかのワードをレジスタに保存でき、その間、パターンを適用して、その結果の各ワードを順に生成することから、時間は、大幅に短くできる。
【０１６６】
一旦、欠落構成要素の倍数にパターンを一度乗ずると、繰り返しによる乗算は、ｎを構成要素の長さとすると、桁送り及び加算によって、構成要素をコピーするのに必要な時間の約ｌｏｇｎ倍で演算できる。従って、欠落構成要素の全体的な再構築は、コピーの最大ｌｏｇ（ｎｍ）倍かかる。ｌｏｇ（ｎ）は、ｌｏｇ（ｍ）よりかなり大きいと仮定されることから、また、ｌｏｇ（ｍ）には、レジスタ動作対メモリ動作の速度に相当する１未満の係数が掛けられることから、この時間を構成要素のコピーのｌｏｇ（ｎ）倍と称する。
【０１６７】
この全てにおいて、バイト又はワード幅の桁送りを用いると、欠落構成要素を復号するのに必要な時間への影響はほとんどない。
ＸＯＲの場合、復号化演算が元来直列であることから、桁送りのサイズは、より重要になる。上記例では、桁送りは、単一のビット桁送りであり、７Ｂ２のビットは、｛ｂ０、ｂ０＋ｂ１、ｂ０＋ｂ１＋ｂ２、ｂ１＋ｂ２＋ｂ３、ｂ２＋ｂ３＋ｂ４＋．．．｝である。Ｂ２を再構築するのに必要な動作は、文字列を線形的に下方移動し、一度に１つの部分に局所的に作用し、各ビットに順に２ＸＯＲ演算を実施する。桁送りが、代わりにｋビット幅である場合、演算は、各機械操作でｋビットを更新する。しかしながら、演算は、全て局所的であり、７Ｂ２に等しい全てのデータを一度だけ読み出す必要があり、また、Ｂ２は、一度書き込めばよいことから、桁送りを広くする実際の利点は、メモリのワードの読み出し及びワードの書き込みに要する時間にどれだけ多くのレジスタ動作を実施し得るかに依存する。一般的に、ビット当り必要とされるＸＯＲ演算の数は、約ｌｏｇ（ｍ）であることから、Ｂ２を復号するのにかかる時間は、桁送りのサイズに依存するオーダ１の係数を符号化に用いて、ブロックをコピーするのにかかる時間の約ｌｏｇ（ｍ）倍であると予想する。
【０１６８】
要約すると、双方の方式での符号化は、最適に近く、ＸＯＲの場合の復号は、メモリから必要なＮ構成要素にアクセスするのに要する時間の約ｌｏｇ（ｍ）倍かかり、算術の場合の復号は、アクセス時間の約ｌｏｇ（ｎ）倍かかる。復号化時間は、ネットワーク及びディスクアクセス時間によって支配されると予想されることから、２つの方式間の実際の差異は、小さい。
【０１６９】
ＲＡＩＤ用途用の一般化リードソロモン符号の最良の実施例（背景技術の節において引用されたフェング（Ｆｅｎｇ）らによる論文と、同機関紙において２００５年１２月発行されたパートＩＩとを参照）と比較して、符号化及び復号化に必要なＸＯＲの数、及びＸＯＲの平行化の可能性の観点での性能は、ほぼ同等であり、４を超える追加構成要素を生成するための符号化の場合、ほぼ２倍の利点がある。構成要素の数により、全ての可能な消去の場合から復旧するのに必要な式の事前計算が実際的でない場合、必要な式は、要請に応じて導出しなければならない。ブロックが大きいと仮定すると、あるサイズまでは、実際の復号に必要な時間と比較して、式を導出するためにかかる時間は、短い。符号化されたブロックがサイズＢである場合、Ｎ＋Ｍ符号において、Ｍ個の失われた構成要素を復旧するために必要な演算の数は、式が与えられると、ＭＢと同程度の桁の数である。式が、ガウスの消去法によって（図１６でのように）決定される場合、それらを導出するのに必要な演算の数は、Ｍ３と同程度の桁の数である。従って、ＢがＭ２よりかなり大きい限り、式を決定するのに必要な時間は、復号時間のわずかな部分である。係数行列の構造によって、式が、Ｍ３演算未満で導出可能な場合、これよりより良い状況である。
【０１７０】
他の実施形態
上記したもの以外の他の多くの実施例が、本発明の範囲内であるが、これは、以下の請求項によって、また、出願人が資格を与えられる他の請求項によって規定されるものである。上記したように、本発明の全ての可能な実施例についてここで説明することは不可能であるが、以下の節において幾つかの可能性について説明する。上に記載した及び以下の幾つかの請求項に出現する特徴の全てが、本発明を実践する際に必要なわけではない。特定の請求項に記載された特徴だけが、その請求項述べられた発明を実践するのに必要である。発明者の寄与と一致する範囲で本発明について記載するために、特徴は、請求項から作為的に除外した。
【０１７１】
記憶領域割当て（ルーティング）表（例えば、図１０）は、多くの異なるやり方で実現することができるが、それは、アドレス範囲、冗長構成要素、及びデータ記憶装置間の関係を指定する限り、厳密な意味での表である必要はない。
【０１７２】
効率的なアクセスを提供するために、記憶装置を付加又は除去させるために、また、故障後の復旧を可能にするために、一組の記憶要素間においてブロック識別子アドレス空間を分割するルーティング表を構築するメカニズムについて記載した。格納されたデータブロックを表す冗長構成要素用の特定の符号化方式の幾つかについても説明した。
【０１７３】
多くの細目が、開示実施例の作用を明確にするために提示されたが、必ずしも必要ではない（例えば、特定のデータ構造及びフォーマット）。含まれた幾つかの特性（例えば、記憶装置への役割の疑似ランダム割当て、表の可変サイズ等）は、最適なものであり、省略又は異なる様に取り扱い得る。本節では、幾つかの他の選択肢肢としての実施形態について説明する。
【０１７４】
ルーティング表
表品質の複数の目安を取り入れ、また、それらを特定の方法で優先順位をつける特定の検索アルゴリズムを提示したが、その代わりに他の任意のアルゴリズムを用いることも可能であった。他の発見的検索アルゴリズムを用いて、明示的な又は暗示的なバージョンの同じ品質尺度を検討して、ルーティング表を埋めることも可能である。他のデータ構造を用いて、等価な情報を記録することが可能であり、また、説明した新表及び旧表は、１つの構造に組み合わせたり、複数の構造に分離したりできる。構造又は複数の構造は、何らかの最大サイズを有することができ、また、徐々に大きくなるよりもむしろ、この最大サイズで開始することさえ可能である。表を含む全ての構造は、表が再生成される度に、再計算しなくてもよい。
【０１７５】
恐らく、表ベースの手法の最大の利点は、所望の特性を組み込むルーティング表を生成するために、尺度が、付加又は修正できることであり、また、異なる尺度の重要性の順番を調整できることである。一旦、表が生成されると、表に記録された割当てを用いて、データにアクセスするのに必要な時間は、それに組み込まれた組の特性を最適化することが如何に難しかったかには関係しない。
【０１７６】
ルーティング表品質の尺度は、主として以下の項目に関連する。即ち、
（１）許容されるハードウェア故障の数
（２）達成される総利用可能容量
（３）権限移転の速さ
これらの尺度は、開示された実施例において、ほとんど明示的によりもむしろ暗示的に取り扱われ、尺度を改善するように構成された特性は、尺度の実際の値の計算を試行せずに、ルーティング表に課される。例えば、データの不必要な再入れ替えを最小にすると、復旧の速度が改善することが予想される。実際には、システム性能の決定要因は、複雑であり、更に、尺度の優先順位付け順の変更やどの尺度を用いるかは、所望の結果を達成するために、確認する必要がある。開示実施例において、これら３種類の尺度には、設計の際、所定順に優先順位をつける。幾つかの関連尺度について以下に記載する。
【０１７７】
（１）許容されたハードウェア故障の数。ルーティング表生成に関する限り、この尺度は、各アドレス範囲用の冗長構成要素の数と、厳格に実施される対形成制約条件とに反映される。上記において注意を促したように、対形成制約条件は、システムサイズの関数として変更し得るが、例えば、システムが小さくなり過ぎた場合、できるだけ復旧が可能なままにしておくために、緩和し得る。冗長データの配置に対する追加の制約条件は、構成要素故障において予想される相互関係（例えば、何らかの資源を共有するサブシステムは、互いに物理的に近い等）を明らかにするために付加し得る。
【０１７８】
開示実施例は、全てのブロックに対して固定数の冗長構成要素を用いるが、冗長構成要素の数が、異なる種類のデータに対して異なる場合、同じルーティング表が、この役割を果たす。例えば、小さいブロックは、Ｍ＋１回複製し得るが、一方、大きなブロックは、Ｎ個に分割され、Ｍ個の追加構成要素に符号化される。双方の場合において、システムは、Ｍ個の構成要素の喪失から復旧し得る。ルーティング表は、単に、列当り最大数（本例では、Ｎ＋Ｍ）の登録項目で構築し得るが、全登録項目が、全てのブロックに用いられるわけではない。他の例として、より重要なデータは、２つの異なるＭの値を用いることによって、より重要でないデータと比較して、より多くのハードウェア故障から保護し得るが、ルーティング表は、より大きな値を取り扱うように構築される。
【０１７９】
Ｓ台のサーバを備えたクリークにおいて、Ｍ個の冗長構成要素が失われ復旧される可能性がある場合、
【０１８０】
【数１０】
2009532812.tif 000024
である限り、単一のサーバは、
【０１８１】
【数１１】
2009532812.tif 000025
回を超えて、同じアドレス範囲に割り当てられないという対形成制約条件を課すことは、有用である。更に、これによって、大きな値のＲを備えた記憶システムは、相対的に少数のサーバに規模を縮小し得る。この柔軟性を可能にする実施代価は、本質的にルーティング表にこの制約条件を課す能力だけである。また、
【０１８２】
【数１２】
2009532812.tif 000026
である限り、
【０１８３】
【数１３】
2009532812.tif 000027
で表される数以下の冗長構成要素を、同じ記憶装置に割り当て得るという制約条件も課し得る。
【０１８４】
【数１４】
2009532812.tif 000028
であれば、最初の制約条件は、撤回すべきである。
【０１８５】
一例を図１７に示す。各記憶装置は、円によって表され、各サーバは、矩形によって表される。ブロックＢの８つの冗長構成要素は、８つの黒い正方形によって示され、サーバ内の記憶装置に配置されている。本例において、Ｎ＋Ｍ＝６＋２符号を用いており、従って、８つの冗長構成要素の内の任意の２つは、喪失して復旧が可能であり、この能力のためのオーバーヘッドは、３３％の追加記憶容量である。クリークに少なくとも８つのサーバがある限り、それは、いずれか２つの喪失に耐え得る。４つのサーバだけが、クリークにある場合、各々、各ブロックの２つの構成要素を保持しなければならない。クリークは、任意の単一のサーバ故障から依然として安全である。少なくとも総数８台の記憶装置が、クリークにある限り、クリークは、記憶装置のいずれか２つの同時故障から安全なままである。クリークは、残りの記憶装置を用いて、できる限り安全にデータを維持する。他のサーバが故障して、６台の記憶装置だけが残った場合、クリークは、同じ記憶装置上に同じブロックの２つまでの構成要素を許容し、単一の記憶装置故障に依然として耐え得る。
【０１８６】
（２）達成される総利用可能容量。表ベースの方式が与えられると、アドレス範囲サイズの量子化には、浪費空間用の指定許容範囲によって決定される最小表サイズが必要である。このことは、全てのアドレス範囲が同じサイズではない場合であっても当てはまる。
【０１８７】
総利用可能容量には、開示実施例では、耐障害後、最優先権が与えられる。互いに関係する故障可能性の階層構造を備えたシステムでは、総利用可能容量に対して、小さい故障可能性のグループの一部より高い優先度を与えることが、望ましい場合がある。これは、開示実施例のアルゴリズムの観点では、幾つかの対形成制約条件が、（候補列の選択において）厳格に励行され、一方、他の対形成制約条件が、他の高優先度の表品質尺度が複数の選択によって等しく良好に満たされる場合、（列からのその列の選択において）好みとしてのみ用いられることを意味する。
【０１８８】
（３）権限移転の速さ。この尺度は、開示実施例に暗に反映されるが、この反映は、復旧のためのデータ供給時、任意のサーバに不公平な負荷をかけることを回避する役割と、許されない対制約条件の影響を最小にすることによって、余分なデータを移転する必要性を回避する役割との双方を果たす過剰対形成尺度を最小にすることによって行われる。表生成中、選択された場合、新しい登録項目を変更するよりもむしろ、（最良の変更を行うために）、既に変った登録項目を変更すると（これが表を改善するのであれば）、変わる登録項目の数を低減し、従って、入れ替える必要があるデータの量を低減する役割を果たす。
【０１８９】
このアルゴリズムは、現在、幾つかの記憶装置サブシステムが、それらの記憶装置へのより高い帯域幅アクセスを提供されるか又はより速いネットワーク接続を有されるという事実を加味していない。これらの種類の因子は、どの過剰対形成が悪いのか決定するために、比較の重み付けに用いられる。他の選択肢肢として、追加の優先順位は、ハードウェア因子に基づき、アルゴリズムに含むことができ、また、均衡を破るために用いられる。残りのものより多い数台の記憶装置を備えたシステムでは、これらが権限移転性能を制限し、また、過剰対形成が、残りのものに対して加味されないことや少なくとも与えられる重みが小さいことがある。
【０１９０】
開示実施例で述べたアルゴリズムの形態においては、選択肢の内、変更されるが良好な過剰対形成尺度を依然達成し得る幾つかの選択肢には、次のものが含まれる。代替品の選択を支配する優先順位の変更、その列の選択を支配する優先順位の変更、対象の幾つかの優先順位の除去、又は対形成制約条件計算方法の変更が含まれる。これらの最後のものには、例えば、最小限の悪化の場合の前に最も改善する場合を考慮すること、又は、これら２つの場合を交互に入れ替えることによって対形成制約条件を計算すること、各ステップにおいて最良の対又は最も悪くない対だけを考慮すること、そして、次のステップにおいて、単一の最良のその列が見つかるか又は全ての対が検討されるまで、それらを検討の対象から排除することを伴う。高次の均一性尺度は、対形成だけを検討するよりもむしろ、ルーティング表に出現する組合せの分散にも適用し得る。
【０１９１】
権限移転処理の実施を簡素化するために、対形成制約条件もまた課される。例えば、Ｒ＝２の場合、（旧表に一覧表示された）送信元記憶装置が、複数の場所に冗長構成要素を一切送らなくてもよいことが望ましい。これは、任意の列において、新表が、旧表との複数の相違を含むことができないことを意味する。この制約条件は、本アルゴリズムの開示実施例において、代替品が、最大のサーバの最大の記憶装置であるように最優先で選択され、また、表が、その最大サイズに達していない限り、クリークの総利用可能容量を低減することなく、常に満たし得る。（クリークが、けた外れに異なる容量の記憶装置を含む場合、表を広くしてアルゴリズムを再実行することが必要なこともあり得る）。
【０１９２】
消去符号化
開示実施例のために説明した符号化方式は、例示の目的のためだけに提供され、（単純な複製を含む）あらゆる消去順応符号は、上記ルーティング表メカニズムに適合する。これには、冗長構成要素が、符号化前にブロックから分割された元の部分ではない符号が含まれる。上記ルーティング表アルゴリズムは、全く冗長性のないシステム（又はシステムの階層構造のレベル）用の表にも用いられる。この場合、対形成制約条件及び対優先順位は、関係がなくなり省略される。
【０１９３】
追加冗長構成要素を元のブロックの部分より大きくできる他の多くの符号化方式が可能である。与えられた例は、２の累乗の係数を備えた線形式を用いるが、他の係数を備えた線形式が、場合によっては、算術及びＸＯＲ符号化双方に対して利点を有する。例えば、２の累乗係数及び議論した種類の符号だけを用いて、追加冗長構成要素の平均のサイズは、元のブロックの部分の数に比例して増加する。他の係数を用いると、この増加は、より遅いことがある。
【０１９４】
標準方式は、２の累乗係数により線形式を構築するために提示されるが、特別な場合、もっと効率的な符号化が存在し得る。例えば、図１５の３＋３符号は、標準方式によって与えられる３＋３符号より１つ少ない桁送りを符号化に用いる。一般的に、各２ｘ２部分行列が満杯の序列を有する行列は、消去符号を生成するための良い候補である。
【０１９５】
開示実施例で記載した符号化は、他の種類の記憶システム用の用途、及び他の種類のデータ保護用の用途を有する。例えば、これらの符号は、高度ＲＡＩＤに用いるために提案された最良の方式とほぼ同じように効率的であるが、これらの符号は、実施、試験、及び最適化が、極めて簡単である。ＲＡＩＤシステムにおいて、セクタサイズは、通常、固定されているが、これにより生じる疑問は、これらの符号によって生成された余分なビットをどこに保持するかということである。理想的には、物理セクタサイズだけをわずかに大きくするか、又はセクタ当り予備の数ビットをＲＡＩＤコントローラに公開する。もちろん、実際には、ＲＡＩＤコントローラに余分なビット用の場所を見つけさせる方が簡単である。１つの可能性は、ＲＡＩＤコントローラによって用いられる論理セクタサイズを大きくすることである。例えば、６４ＫＢ論理セクタ当り、１つの５１２バイトの物理セクタが予約された場合、オーバーヘッドは、１％未満である。これより小さい論理セクタサイズが好ましい場合、ＲＡＩＤコントローラは、単に、幾つかの隣接する論理セクタ間で１つの５１２バイト物理セクタを共有する。
【０１９６】
開示実施例では、故障復旧中、冗長構成要素の一時的な追加の記憶を回避するために用いられるメカニズムについて、新しく権限が与えられた記憶装置が、アドレス範囲用の各ブロックの１つの欠落構成要素を受信し、そして、各欠落構成要素のために、他の構成要素を順に要求する段階を伴うものとして説明した。この考え方の延長は、構成要素が要求される発信元が、複数の未処理の要求を同時に有し、それらをそれらのディスクにもっと効率的にアクセスさせるように、より大きなグループの欠落構成要素を要求し同時に処理することである。
【０１９７】
また、外部の一時的な記憶領域は、冗長構成要素の発信元が、宛先記憶装置の要求ではなくむしろ、それら自体の都合でそれらを送る場合、回避される。この場合、宛先記憶装置は、部分的に利用可能になるように、ブロックを徐々に再現する。このことは、ほとんどの消去符号で行い得る。例えば、１つの記憶装置が、（上記の一例でそうであったように）式３Ａ＝２Ｗ＋Ｘ−４Ｂ−Ｄによって残りの構成要素から得ることができる冗長構成要素Ａを再現しようとしている場合、この式の右辺の構成要素は、任意の順番で一度に１つ供給して、合計を積算される。各段階において、それまでの合計（及び、どれが既に受信されたかについての記録）は、Ａに対して格納する必要がある全てである。一旦、合計が完了すると、Ａは、それから導出される。この手法は、加算演算がＸＯＲである場合と同様に良好に機能する。
【０１９８】
付録Ａ：ルーティング表の幅
ルーティング表は、総利用可能容量Ａｔｏｔの部分Ｔを超えて浪費されないように、全ての記憶装置を表すのに充分な大きさが充分な解像度と共に必要である。これは、許容範囲制約条件である。
【０１９９】
ルーティング表の各入力項目は、固定幅のアドレス範囲と関連付けられる。利用可能容量ａｉの記憶装置が、ｅｉ登録項目と関連している場合、各アドレス範囲は、ａｉ／ｅｉの利用可能容量を表す。この比が、全ての記憶装置に対して一定である場合、Ａｔｏｔ＝ａｉ＊Ｅｔｏｔ／ｅｉとなり、ここで、Ｅｔｏｔは、表中の登録項目の総数である。表中のアドレス範囲の数（表幅）は、Ｗ＝Ｅｔｏｔ／Ｒであり、ここで、Ｒは、各アドレス範囲用に格納された冗長構成要素の数である。
【０２００】
実際には、各記憶装置には、理想的な（非整数）数ｅｉ＝ａｉ＊Ｅｔｏｔ／Ａｔｏｔよりもむしろ、整数のアドレス範囲ｅ＊ｉを割り当てなければならない。利用可能容量の単位当り最も多い登録項目が割り当てられる記憶装置は、どれであってもまず充足されるが、充足率は、表登録項目の数に厳密に比例すると仮定する。この記憶装置は、クリークの容量を限定するものである。
【０２０１】
【数１５】
2009532812.tif 000029
であることを保証する。
【０２０２】
従って、実際の利用可能容量は、以下の通りである。
【０２０３】
【数１６】
2009532812.tif 000030
この制約条件を満たすｅ＊ｉの整数割当てが、表中の登録項目の数
【０２０４】
【数１７】
2009532812.tif 000031
である限り、存在することを示し得るが、上式において、Ｄは、クリークのデータ記憶装置の総数である。
【０２０５】
Ｄ／Ｔ個の登録項目が充分であることの証明
Ｅｔｏｔ≧Ｄ／Ｔを整数とすると、様々なｅ＊ｉ間で分割する必要がある一定の数の登録項目がある。
【０２０６】
【数１８】
2009532812.tif 000032
が、ｅｉの許容範囲ｅｉＴ内にある場合、このより大きな整数であるようにｅ＊ｉを選択することができ、こうして、残りの記憶装置間で配分すべき登録項目が少なくなり、いずれかの記憶装置に登録項目を与え過ぎることは、簡単に回避できる。問題は、切り捨てなければならない記憶装置が、許容範囲を超過することなく別の場所で登録項目を付加することによって、常に補正し得るかどうかである。
【０２０７】
αを切り捨てなければならない記憶装置の集合とすると、
【０２０８】
【数１９】
2009532812.tif 000033
である。集合αの全ての記憶装置に対して、
【０２０９】
【数２０】
2009532812.tif 000034
であるように選択しなければならない。記憶装置当りの登録項目の平均の数は、（式Ａ１から）少なくとも１／Ｔであり、また、記憶装置は、ｅｉＴ＞＝１ならば、集合αに属することができないことから、全ての記憶装置が、集合αに属しているわけではない。βを残りの記憶装置からなる集合とする。理想的な数の登録項目と、集合αの記憶装置に割り当てられた実際の数の登録項目と、の間の差異は、
【０２１０】
【数２１】
2009532812.tif 000035
である。
【０２１１】
上式において、最後の不等号は、式Ａ２及び
【０２１２】
【数２２】
2009532812.tif 000036
から生じる。この多くの追加登録項目は、βの記憶装置に割り当てなければならない。どの記憶装置にもその許容範囲を超過させることなく記憶装置に割り当て得る最大数の追加登録項目は、
【０２１３】
【数２３】
2009532812.tif 000037
である。
【０２１４】
上式において、最後の不等号は任意のｘに対して、
【０２１５】
【数２４】
2009532812.tif 000038
という事実から生じる。従って、Ｅｔｏｔ≧Ｄ／Ｔを選択したことから、
【０２１６】
【数２５】
2009532812.tif 000039
となる。
【０２１７】
従って、どの記憶装置にもその理想的数の登録項目を許容範囲Ｔ以上に超過させることなく、他のものを切り上げることによって、切り捨てなければならない記憶装置を常に補償し得る。従って、式Ａ０から、達成可能な記憶装置Ａ＊ｔｏｔは、理想的なＡｔｏｔの許容範囲Ｔ内にある。
【図面の簡単な説明】
【０２１８】
【図１】固定アドレス空間内にランダムに分散され、ランダムアドレス・ベースのデータ分散用途に適する識別子の従来技術による例を与える図。
【図２】冗長構成要素は、異なるサーバに置かなければならないという制約条件を想定して、あるアドレス範囲へのデータ記憶装置の有効な及び無効な割当てを示す図。
【図３】異なるサーバの異なる記憶装置に格納される３つの冗長構成要素として符号化されたブロックＢを示す図。
【図４】３つの冗長構成要素へのブロックＢの符号化の従来技術による２つの例を提供する図。
【図５】サーバの数、生の容量、及び冗長構成要素の数が異なる記憶システム用の利用可能容量の３つの例を提供する図。
【図６】Ｒより少ないサーバへの移行を示し、サーバ当りの冗長構成要素の数に対する制約条件が移行後緩和された状態を示す図。
【図７】２つのブロックの冗長構成要素を伴う復旧処理の一部を示す図。
【図８】Ｄ台の記憶装置を備えた記憶システムに記憶装置Ｄ＋１を付加する際に関与するデータ経路を示す図。
【図９】高い“初期”故障率の新しい記憶ハードウェアが、最大記憶容量より小さいシステムに最初に追加される例を提供する図。
【図１０】Ｔ＝１０％の状態で、図５の記憶システム＃３用のサンプルルーティング表（及び関連する統計値）を示す図。
【図１１】ルーティング表生成アルゴリズムの擬似符号記述を提供する図。
【図１２】階層記憶システムにおける異なるルーティング表への索引付けに用いられる独立アドレスセグメントに分割された２５６ビットブロックアドレスを示す図。
【図１３】ルーティングの２つのレベルを備え、最上位レベルにおいて冗長性が用いられず、第２レベルにおいて複製が用いられる階層記憶システムを示す図。
【図１４】階層構造のルーティング表による記憶システムの階層的構造を示す図。
【図１５】２の累乗係数によるＮ＋Ｍ消去符号の５つの例を提供する図であって、指数の行列が示され、総和符号が、加算又はＸＯＲのいずれかを示す図。
【図１６】通常の算術を用いた消去符号化及び復号化を示し、また、これと、加算演算としてビット毎のＸＯＲを用いたものとを比較する図。
【図１７】サーバが故障した際、６＋２消去符号（黒の正方形）の８つの冗長構成要素の配置の時間履歴を示す図。
【図１】
2009532812.tif 000040
【図２】
2009532812.tif 000041
【図３】
2009532812.tif 000042
【図４】
2009532812.tif 000043
【図５】
2009532812.tif 000044
【図６】
2009532812.tif 000045
【図７】
2009532812.tif 000046
【図８】
2009532812.tif 000047
【図９】
2009532812.tif 000048
【図１０】
2009532812.tif 000049
【図１１】
2009532812.tif 000050
【図１２】
2009532812.tif 000051
【図１３】
2009532812.tif 000052
【図１４】
2009532812.tif 000053
【図１５】
2009532812.tif 000054
【図１６】
2009532812.tif 000055
【図１７】
2009532812.tif 000056
【国際調査報告】
2009532812.tif 000057