(57)【特許請求の範囲】
【請求項１】
コンポーネントデータストレージシステムを備える分散データストレージシステム（１０２〜１０９）内における現在の構成（１１３０）のマイグレーション（図１１Ｇ）又は再構成（図１１Ｅ〜図１１Ｆ）の期間中に前記現在の構成及び新しい構成（１１２８）のデータブロックのデータ一貫性を維持するための方法であって、
第１のフェーズ（３４０２）において、前記コンポーネントデータストレージシステムが、前記現在の構成を再構成することを決定することと、
第２のフェーズ（３４０４）において、前記コンポーネントデータストレージシステムが、前記新しい構成を初期化して、前記現在の構成から前記新しい構成へデータブロックをコピーすることと、
第３のフェーズ（３４０８）において、前記コンポーネントデータストレージシステムが、前記現在の構成及び前記新しい構成のデータブロックを記憶する前記コンポーネントデータストレージシステムによって保持される構成状態を同期させることと、
前記第３のフェーズの期間中に、前記コンポーネントデータストレージシステムが、連続ＷＲＩＴＥオペレーション及び連続ＲＥＡＤオペレーションを前記現在の構成及び前記新しい構成の双方に向けることと、
第４のフェーズ（３４１２）において、前記コンポーネントデータストレージシステムが、前記現在の構成を割り当て解除することと
を含み、
前記マイグレーション又は前記再構成に関与している前記分散データストレージシステムの前記コンポーネントデータストレージシステム（１０２〜１０９）それぞれは、当該コンポーネントデータストレージシステムの現在のフェーズに達しているすべての他の前記コンポーネントデータストレージシステムよりも前に、次のフェーズに遷移しない
方法。
【請求項２】
前記第２のフェーズの期間中に、前記コンポーネントデータストレージシステムが、連続ＷＲＩＴＥオペレーション（continuing WRITE operations）を前記現在の構成（１１３０）及び前記新しい構成（１１２８）の双方に向ける（directing）が、連続ＲＥＡＤオペレーション（continuing READ operations）を前記現在の構成に向けることと、
前記第３のフェーズの期間中に、前記コンポーネントデータストレージシステムが、連続ＷＲＩＴＥオペレーション及び連続ＲＥＡＤオペレーションを前記現在の構成及び前記新しい構成の双方に向けることと
をさらに含む請求項１に記載の方法。
【請求項３】
前記現在の構成から前記新しい構成へのマイグレーション又は再構成の期間中に、前記現在の構成及び前記新しい構成について、構成の各データブロックに関連付けられるタイムスタンプ（３０００）が独立にガベージコレクトされ、
前記分散データストレージシステムにおける階層的なデータ構造体は、対応する階層的な複数のコーディネータによって処理され、
前記タイムスタンプは、前記マイグレーション又は前記再構成を管理するコーディネータよりも上の階層のコーディネータでは比較されない
請求項１に記載の方法。
【請求項４】
請求項１に記載の方法を組み込む分散データストレージシステム（１０２〜１０９）であって、
コンポーネントデータストレージシステム
を備え、
該コンポーネントデータストレージシステムにわたってデータブロックのセグメントが分散され、前記データブロックの各セグメントは、通常オペレーションの期間中は１つの構成（１１２４）に従って分散され、マイグレーションの期間中は２つの構成（１１２８、１１３０）に従って分散され、又は再構成の期間中は２つ以上の構成に従って分散され、
前記コンポーネントデータストレージシステムは、現在の構成及び新しい構成について、同期された独立クォーラムベース一貫性方法を使用して、データブロックのセグメントに対して前記現在の構成から前記新しい構成へのマイグレーションオペレーション又は再構成オペレーションを実行する
分散データストレージシステム。
【請求項５】
現在の構成（１１３０）から新しい構成（１１２８）への分散データストレージシステム（１０２〜１０９）内におけるマイグレーション（図１１Ｇ）又は再構成（図１１Ｅ〜図１１Ｆ）の期間中に前記現在の構成及び前記新しい構成のデータブロックのデータ一貫性を維持するための方法であって、
前記分散データストレージシステムが、前記現在の構成（１１３０）を再構成することを決定することと、
前記分散データストレージシステムが、前記現在の構成のデータブロックに向けられている連続ＲＥＡＤオペレーション及び連続ＷＲＩＴＥオペレーションをデータ一貫性のある方法で実行している間、
前記分散データストレージシステムが、前記新しい構成（１１２８）を初期化して、前記現在の構成から前記新しい構成へデータブロックをコピーすることと、
前記分散データストレージシステムが、前記現在の構成及び前記新しい構成のデータブロックのタイムスタンプ及びデータ状態を同期させることと
を含み、
前記現在の構成のデータブロックに向けられている連続ＷＲＩＴＥオペレーションをデータ一貫性のある方法で実行することは、
前記分散データストレージシステムが、前記ＷＲＩＴＥオペレーションの共通のタイムスタンプを生成すること（３５０２）と、
前記分散データストレージシステムが、該共通のタイムスタンプを使用して、前記連続ＷＲＩＴＥオペレーションに対応する複数のＷＲＩＴＥオペレーションを前記現在の構成及び前記新しい構成の双方に向けること（３５０４、３５０６）と
を含み、
前記連続ＲＥＡＤオペレーションをデータ一貫性のある方法で実行することは、
前記分散データストレージシステムが、前記現在の構成及び前記新しい構成の一方にデータＲＥＡＤオペレーションを向け（３７０２）、前記現在の構成及び前記新しい構成の双方にタイムスタンプＲＥＡＤオペレーションを向けること（３７０２、３７０４）と、
前記ＲＥＡＤオペレーションによって返された前記タイムスタンプも前記データも同一でない場合、前記分散データストレージシステムが、前記現在の構成に向けられていた前記ＲＥＡＤオペレーションによって返された前記データを書き込むためのＷＲＩＴＥオペレーションを前記新しい構成に向けることと
を含む
方法。
【請求項６】
前記現在の構成のデータブロックに向けられている連続ＷＲＩＴＥオペレーションをデータ一貫性のある方法で実行することは、
前記分散データストレージシステムが、前記ＷＲＩＴＥオペレーションの共通のタイムスタンプを生成すること（３５０２）と、
前記分散データストレージシステムが、該共通のタイムスタンプを使用して、前記連続ＷＲＩＴＥオペレーションに対応する複数のＷＲＩＴＥオペレーションを前記現在の構成及び前記新しい構成の双方に向けること（３５０４、３５０６）と、
前記現在の構成及び前記新しい構成の双方に向けられている複数の前記ＷＲＩＴＥオペレーションが完了する時に、
前記分散データストレージシステムが、ステータスを返すこと（３５１０）と、
前記分散データストレージシステムが、前記現在の構成及び前記新しい構成において、前記共通のタイムスタンプを独立にガベージコレクトすること（３５１２）と
をさらに含む
請求項５に記載の方法。
【請求項７】
前記現在の構成のデータブロックに向けられている連続ＲＥＡＤオペレーションをデータ一貫性のある方法で実行することは、
前記分散データストレージシステムが、前記共通のタイムスタンプを使用して、前記現在の構成（１１３０）及び前記新しい構成（１１２８）の双方に、前記連続ＲＥＡＤオペレーションに対応するＲＥＡＤオペレーションを向けること（３６０２、３６０４）と、
前記現在の構成及び前記新しい構成の双方に向けられている前記ＲＥＡＤオペレーションが完了し、各ＲＥＡＤオペレーションがタイムスタンプ及びデータを返す時に、
前記ＲＥＡＤオペレーションによって返された前記タイムスタンプが同一である場合、前記分散データストレージシステムが、前記ＲＥＡＤオペレーションの１つによって返された前記データ及び成功ステータスを返すことと、
前記ＲＥＡＤオペレーションによって返された前記タイムスタンプが同一でないが、前記現在の構成及び前記新しい構成の双方に向けられていた前記ＲＥＡＤオペレーションによって返された前記データが同一である場合、前記分散データストレージシステムが、前記ＲＥＡＤオペレーションの１つによって返された前記データ及び成功ステータスを返すこと（３６１２）と、
前記ＲＥＡＤオペレーションによって返された前記タイムスタンプも前記データも同一でない場合、前記分散データストレージシステムが、前記現在の構成に向けられていた前記ＲＥＡＤオペレーションによって返された前記データを書き込むためのＷＲＩＴＥオペレーションを前記新しい構成に向け（３６１４）、前記ＷＲＩＴＥオペレーションが成功すると、前記分散データストレージシステムが、該ＷＲＩＴＥオペレーションによって書き込まれた前記データ及び成功ステータスを返すこと（３６１２）と
をさらに含む
請求項５に記載の方法。
【請求項８】
前記連続ＲＥＡＤオペレーションをデータ一貫性のある方法で実行することは、
前記分散データストレージシステムが、前記現在の構成及び前記新しい構成の一方にデータＲＥＡＤオペレーションを向け（３７０２）、前記現在の構成及び前記新しい構成の双方にタイムスタンプＲＥＡＤオペレーションを向けること（３７０２、３７０４）と、
前記現在の構成及び前記新しい構成に向けられている前記ＲＥＡＤオペレーションが完了する時に、
前記ＲＥＡＤオペレーションによって返された前記タイムスタンプが同一でない場合、前記分散データストレージシステムが、前記現在の構成及び前記新しい構成の他方にＲＥＡＤオペレーションを向け（３７０６）、双方のデータＲＥＡＤオペレーションによって返された前記データが同一である場合、前記分散データストレージシステムが、前記ＲＥＡＤオペレーションの一方によって返された前記データ及び成功ステータスを返すことと、
前記ＲＥＡＤオペレーションによって返された前記タイムスタンプが同一であるが、前記現在の構成及び前記新しい構成の双方に向けられていた前記ＲＥＡＤオペレーションによって返された前記データが同一である場合、前記分散データストレージシステムが、前記ＲＥＡＤオペレーションの一方によって返された前記データ及び成功ステータスを返すことと、
前記２つのデータＲＥＡＤオペレーションによって返された前記タイムスタンプも前記データも同一でない場合、前記分散データストレージシステムが、前記現在の構成に向けられていた前記ＲＥＡＤオペレーションによって返された前記データを書き込むためのＷＲＩＴＥオペレーションを前記新しい構成に向け、前記ＷＲＩＴＥオペレーションが成功すると、前記分散データストレージシステムが、該ＷＲＩＴＥオペレーションによって書き込まれた前記データ及び成功ステータスを返すことと
をさらに含む
請求項５に記載の方法。
【請求項９】
請求項５に記載の方法を組み込む分散データストレージシステム（１０２〜１０９）であって、
コンポーネントデータストレージシステム
を備え、
該コンポーネントデータストレージシステムにわたってデータブロックのセグメントが分散され、前記データブロックの各セグメントは、通常オペレーションの期間中は１つの構成（１１２４）に従って分散され、マイグレーション（図１１Ｇ）の期間中は２つの構成（１１２８、１１３０）に従って分散され、再構成（図１１Ｅ〜図１１Ｆ）の期間中は２つ以上の構成に従って分散され、
前記コンポーネントデータストレージシステムは、現在の構成及び新しい構成について、同期されていない独立クォーラムベース一貫性方法を使用して、データブロックのセグメントに対して前記現在の構成から前記新しい構成へのマイグレーションオペレーション又は再構成オペレーションを実行する
分散データストレージシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一貫性方法及び一貫性システムに関する。
【背景技術】
【０００２】
コンピュータネットワーキングシステム及び相互接続システムが、能力、信頼性、及びスループットにおいて着実に進歩するとともに、ネットワーキングシステムおよび相互接続システムに基づく分散コンピューティングシステムが、それに対応して、サイズ及び能力において増大したことから、分散コンピューティング問題の理論的理解の発展において多大な進歩がなされ、その結果として、コンピューティングタスクを分散システム内に分散させるための強力且つ有益なツール及び手法の開発及び広範囲に及ぶ普及が可能になった。分散システムの開発の初期においては、大きな計算タスクの処理を分散させるために、それぞれがマスストレージデバイスを含む多数の周辺デバイスを有する大きなメインフレームコンピュータ及びミニコンピュータが、直接又はネットワークを通じて相互接続されていた。ネットワーキングシステムが、よりローバスト、より有能且つより経済的になるにつれて、１つ又は複数のネットワークを通じてリモートホストコンピュータと相互接続された独立したディスクアレイ等の独立したマスストレージデバイスが、メインフレームからパーソナルコンピュータに至るまでの多数のコンピュータシステムによって共有された大量のデータを記憶するために開発された。近年、以下で詳細に説明するように、開発努力は、１つ又は複数のネットワークによって相互接続された多数のマスストレージデバイスにわたってマスストレージシステムを分散させる方向に向けられ始めてきている。
【０００３】
マスストレージデバイスは、単一のコンピュータシステムに別個に取り付けられて単一のコンピュータシステムにより制御される周辺デバイスから、リモートホストコンピュータによって共有される独立したデバイスへ発展し、最終的には、相互にネットワーク接続された多数の別個のマスストレージユニットで構成された分散システムへ発展したことから、データを共有することに関連した問題、及び、一貫性があり且つローバストな状態で共有データを保持することに関連した問題が劇的に増加している。分散システムの設計者、開発者、製造業者、ベンダ、及び最終的にはユーザは、すでに開発された分散コンピューティング方法及びルーチンを拡張する必要性を認識し続け、より大きく、より複雑で且つより高度に分散されたシステムにおいて所望のレベルのデータローバスト性及び一貫性を提供する新しい方法及びルーチンの必要性を認識し続けている。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、一貫性方法及び一貫性システムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の実施の形態は、分散データストレージシステム内における現在の構成の新しい構成へのマイグレーション又は再構成の期間中にデータブロックのデータ一貫性を維持するための方法を対象としている。本発明の一実施の形態では、最初に、現在の構成を再構成することが決定される。次に、新しい構成が初期化され、現在の構成から新しい構成へデータブロックがコピーされる。次に、現在の構成及び新しい構成のデータブロックを記憶するコンポーネントデータストレージシステムによって保持された構成状態が同期される。最後に、現在の構成が割り当て解除される。本発明の第２の実施の形態では、現在の構成を再構成することが決定され、現在の構成のデータブロックに向けられている連続ＲＥＡＤオペレーション及び連続ＷＲＩＴＥオペレーションをデータ一貫性のある方法で実行している間、新しい構成が初期化され、現在の構成から新しい構成へデータブロックがコピーされ、現在の構成及び新しい構成のデータブロックのタイムスタンプ及びデータ状態が同期される。
【発明を実施するための最良の形態】
【０００６】
本発明のさまざまな実施の形態は、独立したクォーラムシステム（quorum system）を使用して、マイグレーションオペレーション及び再構成オペレーション中のデータ一貫性を維持する。以下では、現在開発中の分散マスストレージデバイスを背景として本発明の一実施の形態を説明する。この背景は、幾分複雑である。以下の小節では、本発明の実施の形態が後に説明される背景を提供するために、分散マスストレージシステム、及び分散マスストレージシステムの処理コンポーネントによって使用されるさまざまな方法を最初に解説する。
【０００７】
［ＦＡＢ概論］
ブリックの連合アレイ（「ＦＡＢ（federated array of bricks）」）アーキテクチャは、マスストレージの新しい、高度に分散した手法を表す。図１は、本発明の一実施の形態によるＦＡＢマスストレージシステムの高レベルの図を示している。ＦＡＢマスストレージシステムを以下では「ＦＡＢシステム」と呼ぶ。ＦＡＢシステムは、複数の小さな別個のコンポーネントデータストレージシステム、すなわちマスストレージデバイス１０２〜１０９を備える。これらのマスストレージデバイス１０２〜１０９は、第１の通信媒体１１０を通じて互いに相互通信を行い、第２の通信媒体１１４を通じて、複数のリモートホストコンピュータ１１２〜１１３から要求を受信することができ、複数のリモートホストコンピュータ１１２〜１１３へ返答を送信することができる。各別個のコンポーネントデータストレージシステム１０２〜１０９は、「ブリック（brick）」と呼ばれる場合がある。ブリックは、インターフェースを含むことができ、このインターフェースを通じて、リモートホストコンピュータから要求を受信することができ、受信された要求に対する応答をリモートホストコンピュータへ返信することができる。ＦＡＢシステムのいずれのブリックも、ホストコンピュータからの要求を受信することができ、この要求に応答することができる。ＦＡＢシステムの１つのブリックは、任意の特定の要求に関して調整役を引き受け、その特定の要求に対する応答に関与するすべてのブリックのオペレーションを調整し、ＦＡＢシステムのどのブリックも、所与の要求に関する調整役を引き受けることができる。したがって、ＦＡＢシステムは、大部分がソフトウェアで実施される一種の対称分散コンピューティングシステムである。いくつかの代替的な実施の形態では、ブリックの相互接続、及び、ＦＡＢシステムのリモートホストコンピュータへの相互接続の双方に単一のネットワークを使用することができる。他の代替的な実施の形態では、３つ以上のネットワークを使用することもできる。
【０００８】
図２は、本発明の一実施の形態による一例示のＦＡＢブリックの高レベルの図を示している。図２に示すＦＡＢブリックは、ディスクＩ／Ｏプロセッサ２１４にインターフェースしている１２個のＳＡＴＡディスクドライブ２０２〜２１３を含む。ディスクＩ／Ｏプロセッサ２１４は、１つ又は複数の高速バス２１６を通じて中央ブリッジデバイス２１８に相互接続されている。次に、中央ブリッジ２１８は、１つ又は複数の汎用プロセッサ２２０、ホストＩ／Ｏプロセッサ２２２、相互ブリックＩ／Ｏプロセッサ２２４、及び１つ又は複数のメモリ２２６〜２２８に相互接続されている。ホストＩ／Ｏプロセッサ２２２は、第２の通信媒体（図１の１１４）への通信インターフェースを提供する。この通信インターフェースを通じて、ブリックは、リモートホストコンピュータと通信する。相互ブリックＩ／Ｏプロセッサ２２４は、第１の通信媒体（図１の１１０）への通信インターフェースを提供する。この通信インターフェースを通じて、ブリックは、ＦＡＢの他のブリックと通信する。１つ又は複数の汎用プロセッサ２２０は、多くのタスク及び担当の中で、リモートホストコンピュータ及びリモートブリックからの要求の処理、１つ又は複数のメモリ２２６〜２２８及びストレージデバイス２０２〜２１３に記憶されている状態情報の管理、並びにブリック内のデータストレージ及びデータ一貫性の管理を行うための制御プログラムを実行する。１つ又は複数のメモリは、データのキャッシュとしての機能に加えて、ＦＡＢシステム内に記憶されたデータへのアクセスを制御するプロセス、及び、ＦＡＢシステム内のデータを一貫性のある状態に維持する制御プロセスによって使用される、タイムスタンプ及びデータ構造体を含むさまざまなエンティティのストレージロケーションとしての機能を果たす。これらのメモリには、通常、揮発性メモリ及び不揮発性メモリの双方が含まれる。以下の解説では、１つ又は複数の汎用プロセッサ、１つ又は複数のメモリ、及び他のコンポーネントは、フレーズ「１つ又は複数」を繰り返すことを回避するために単数形で参照される場合がある。なお、上記他のコンポーネントの１つ又は複数のものは、最初に、含まれるものとして言及したものである。
【０００９】
本発明の一定の実施の形態では、ＦＡＢのすべてのブリックは、基本的に同一であり、同じ制御プログラムを実行し、それらのメモリ２２６及びマスストレージデバイス２０２〜２１３内に基本的に同じデータ構造体及び制御情報を保持し、Ｉ／Ｏプロセッサを通じてホストコンピュータ、ＦＡＢ内の他のブリック、及び内部ディスクドライブへ標準インターフェースを提供する。本発明のこれらの実施の形態では、ＦＡＢ内のブリックは、制御プログラムのバージョン、内部ディスクドライブの特定のモデル及び能力、さまざまなハードウェアコンポーネントのバージョン、並びに他のこのような変形に関して互いにわずかに異なっていてもよい。インターフェース及び制御プログラムは、このような変形をＦＡＢ内で許容することを可能にするために、下位互換性及び上位互換性の双方で設計される。
【００１０】
また、各ブリックは、図２に図示しない他の多数のコンポーネントも含むことができる。これら他の多数のコンポーネントには、１つ又は複数の電源、冷却システム、制御パネル又は他の外部制御インターフェース、標準的なランダムアクセスメモリ、及び他のこのようなコンポーネントが含まれる。ブリックは、比較的簡単なデバイスであり、一般に、コモディティＩ／Ｏプロセッサ及びディスクドライブを含むコモディティコンポーネントから構築される。１２個の１００−ＧＢ  ＳＡＴＡディスクドライブを使用するブリックは、１．２テラバイトの記憶容量を提供する。その記憶容量のわずかしか内部の使用に必要とされない。ＦＡＢは、数百個又は数千個のブリックを備えることができ、大きなＦＡＢシステムは、５，０００個〜１０，０００個のブリックを収容することが現在想定されており、ペタバイト（「ＰＢ」）の記憶容量を提供する。このように、ＦＡＢマスストレージシステムは、記憶容量及び費用効率において、現在のディスクアレイ及びネットワーク接続型ストレージデバイスを超える膨大な増加を提供する。
【００１１】
［冗長性］
ＦＡＢシステム等の大きなマスストレージシステムは、膨大な記憶容量を提供するだけでなく、冗長ストレージの提供及び管理も行い、ブリックの故障、ディスクドライブの故障、ディスクドライブ上の特定のシリンダ、トラック、セクタ、若しくはブロックの故障、電子コンポーネントの故障、又はそれ以外の故障のために、記憶データの一部が喪失した場合に、ホストコンピュータによる介入もユーザによる手動の介入もなく、大規模マスストレージシステムによって記憶され管理されている冗長データから喪失データをシームレスに且つ自動的に回復できるようになっている。データベースシステム及びエンタープライズクリティカルデータ（enterprise-critical data）を含む重要なデータストレージの用途の場合、地理的に分散した複数のデータインスタンスを記憶して保持するために、２つ以上の大規模マスストレージシステムが使用されることが多く、壊滅的な事象であっても回復不可能なデータ喪失につながらないように、より高いレベルの冗長性が提供されている。
【００１２】
本発明の一定の実施の形態では、ＦＡＢシステムは、少なくとも２つの異なるクラスの下位レベルの冗長性を自動的にサポートする。第１のクラスの冗長性は、１つのブリックの故障が回復不可能なデータ喪失につながらないように、ブリックレベルのミラーリングを含む。換言すれば、２つ以上のブリックにデータオブジェクトの複数の別個のコピーを記憶することを含む。図３〜図４は、データミラーリングの概念を示している。図３は、本発明の一実施の形態によるデータオブジェクト３０２及び３つのブリック３０４〜３０６のコンテンツの論理表現を示している。データオブジェクト３０２は、データユニット３０８等、図３の「１」〜「１５」の番号を付けられた１５個の連続したデータユニットを備える。データオブジェクトは、ボリューム、ファイル、データベース、又は別のタイプのデータオブジェクトとすることができ、データユニットは、ブロック、ページ、又は他のこのような連続アドレス指定されるストレージロケーションのグループとすることができる。図４は、本発明の一実施の形態による３つのブリック３０４〜３０６におけるデータオブジェクト３０２のトリプルミラーリング冗長ストレージを示している。３つのブリックのそれぞれは、データオブジェクト３０２内の１５個のデータユニットのすべてのコピーを含む。ミラーリングの多くの説明図では、データユニットのレイアウトは、データオブジェクトのすべてのミラーコピーにおいて同一であることが示されている。しかしながら、実際には、ブリックは、その内部ディスクドライブのどの場所にもデータユニットを記憶することを決めることができる。図４では、データオブジェクト３０２内のデータユニットのコピーは、３つの異なるブリック内で異なる順序及び位置に示されている。３つのブリック３０４〜３０６のそれぞれは、データオブジェクトの完全なコピーを記憶するので、たとえ３つのブリックの２つが故障しても、データオブジェクトは回復可能である。単一のブリックの故障確率は、一般に比較的わずかであり、３ブリックミラーの３つすべてのブリックの故障の組み合わせ確率は、一般に極めて小さい。一般に、ＦＡＢシステムは、数百万個、数十億個、数兆個、又はそれよりも多くの異なるデータオブジェクトを記憶することができ、異なる各データオブジェクトは、ＦＡＢシステム内で異なる個数のブリック上に個別にミラーリングすることができる。たとえば、或るデータオブジェクトは、ブリック１、７、８、及び１０上にミラーリングすることができる一方、別のデータオブジェクトは、ブリック４、８、１３、１７、及び２０上にミラーリングすることができる。
【００１３】
第２の冗長クラスは、「イレージャ符号化（erasure coding：抹消符号化）」冗長性と呼ばれる。イレージャ符号化冗長性は、ミラー冗長性よりも幾分複雑である。イレージャ符号化冗長性は、雑音のあるチャネルを通じて転送される通信メッセージ及び他のデジタルデータの誤り制御符号化に使用されるリード・ソロモン符号化技法を使用することが多い。これらの誤り制御符号化技法は、２元線形符号の具体的な例である。
【００１４】
図５は、イレージャ符号化冗長性を示す高レベルの図を示している。図５では、ｎ＝４個のデータユニットを備えるデータオブジェクト５０２が、ｎよりも多くの個数のブリック５０４〜５０９にわたって分散されている。最初のｎ個のブリック５０４〜５０７は、それぞれ、ｎ個のデータユニットの１つを記憶する。最後のｍ＝２個のブリック５０８〜５０９は、データオブジェクトから計算されたチェックサムデータ又はパリティデータを記憶する。図５に示すイレージャ符号化冗長性方式は、ｍ＋ｎイレージャ符号化冗長性方式の一例である。ｎ＝４であり、ｍ＝２であるので、図５に示す具体的なｍ＋ｎイレージャ符号化冗長性方式は、「４＋２」冗長性方式と呼ばれる。８＋２方式、３＋３方式、及び他の方式を含めて、他の多くのイレージャ符号化冗長性方式が可能である。一般に、ｍはｎ以下である。故障したブリックがｍ個又はｍ＋ｎ個よりも少ない限り、それらの故障したブリックがデータを含んでいようとパリティ値を含んでいようと、データオブジェクト全体を復元することができる。たとえば、図５に示すイレージャ符号化方式では、ブリック５０５及び５０８等のどのブリック対の故障にもかかわらず、データオブジェクト５０２を完全に回復させることができる。
【００１５】
図６は、図３及び図４で使用されたものと同じ説明図の規則を使用する一例示の３＋１イレージャ符号化冗長性方式を示している。図６では、１５個のデータユニットのデータオブジェクト３０２が、４つのブリック６０４〜６０７にわたって分散されている。これらのデータユニットは、４つのディスクにわたってストライプされ、データオブジェクトの各３つのデータユニットは、ブリック６０４〜６０６にわたって連続的に分散され、ストライプのチェックサムデータユニット又はパリティデータユニットは、ブリック６０７に配置されている。最初のストライプは、３つのデータユニット６０８から成り、図６において矢印６１０〜６１２によって示されている。図６では、チェックサムデータユニットは、すべて単一のブリック６０７に配置されているが、ストライプは、ブリックに関して別のやり方で整列することができ、各ブリックが、チェックサムデータユニット又はパリティデータユニットの或る部分を含むことができる。
【００１６】
イレージャ符号化冗長性は、一般に、データユニットの各バイト、各ワード、又は各ロングワードのチェックサムビット又はパリティビットを数学的に計算することによって実行される。したがって、ｍビットのパリティビットは、ｎビットのデータビットから計算される。ここで、ｎ＝８、１６、若しくは３２、又はそれよりも大きな２のべき乗である。たとえば、８＋２イレージャ符号化冗長性方式では、２ビットのパリティチェックビットが、データの各バイトについて生成される。したがって、８＋２イレージャ符号化冗長性方式では、データの８つのデータユニットが、チェックサムビット又はパリティビットの２つのデータユニットを生成する。これら２つのデータユニットのすべては、１０データユニットのストライプに含めることができる。以下の解説では、用語「ワード」は、符号化が行われるデータユニットの粒度を指し、ビットからロングワード又はそれよりも長いデータユニットに変化することができる。データストレージの用途では、データユニットの粒度は、通常、５１２バイト以上とすることができる。
【００１７】
ｉ番目のチェックサムワードｃｉは、関数Ｆｉ（ｄ１，ｄ２，…，ｄｎ）により、ｎ個のすべてのデータワードの関数として計算することができる。この関数Ｆｉは、以下のように、データワードｄｊのそれぞれに係数ｆｉ，ｊを乗算したものの線形結合である。
【００１８】
【数１】
0004516087.tif 000002
【００１９】
行列表記では、この式は、
【００２０】
【数２】
0004516087.tif 000003
【００２１】
又は、
【００２２】
【数３】
0004516087.tif 000004
【００２３】
となる。リード・ソロモン技法では、関数Ｆは、要素ｆｉ，ｊがｊｉ―１に等しいｍ×ｎバンデルモンド行列となるように選ばれる。すなわち、
【００２４】
【数４】
0004516087.tif 000005
【００２５】
である。特定のワードｄｊが、新しい値ｄｊ'を有するように変更された場合、新しいｉ番目のチェックサムワードｃｉ'は、
ｃｉ'＝ｃｉ＋ｆｉ，ｊ（ｄｊ'−ｄｊ）
又は
【００２６】
【数５】
0004516087.tif 000006
【００２７】
として計算することができる。したがって、新しいチェックサムワードは、前のチェックサムワード及び行列Ｆの単一の列から容易に計算される。
【００２８】
ストライプから喪失されたワードは、行列の反転によって回復される。行列Ａ及び列ベクトルＥは、以下のように構築される。
【００２９】
【数６】
0004516087.tif 000007
【００３０】
【数７】
0004516087.tif 000008
【００３１】
以下であることが容易に分かる。
【００３２】
【数８】
0004516087.tif 000009
【００３３】
変更された行列Ａ'及びＥ'を作成するために、行列Ａの任意のｍ行及びベクトルＥの対応する行を削除することができる。ここで、Ａ'は正方行列である。次に、元のデータワードを表すベクトルＤは、以下のように行列の反転によって回復させることができる。
【００３４】
【数９】
0004516087.tif 000010
【００３５】
したがって、ｍ個以下のデータワード又はチェックサムワードが消去又は喪失された場合、それらｍ個以下の喪失されたデータワード又はチェックサムワードを含むｍ個のデータワード又はチェックサムワードをベクトルＥから削除することができ、上記に示したように、行列Ａから対応する行が削除され、元のデータワード又はチェックサムワードは、行列の反転によって回復させることができる。
【００３６】
行列の反転は、実数については、加算、減算、乗算、及び除算のよく知られている実数算術演算を使用して容易に実行されるが、デジタル誤り制御符号化に使用される離散値の行列要素及び列要素は、離散値が、対応する離散算術演算の下で閉じた算術体（arithmetic field）を形成する場合にのみ、行列乗算に適している。一般に、チェックサムビットは、長さｗのワード
【００３７】
【数１０】
0004516087.tif 000011
【００３８】
について計算される。ｗビットワードは、２ｗ個の異なる値のいずれかを有することができる。ガロア体として知られている数学体（mathematical field）は、２ｗ個の要素を有するように構築することができる。ガロア体の要素の算術演算は、好都合なことに、
【００３９】
【数１１】
0004516087.tif 000012
【００４０】
である。ここで、ガロア体の要素の対数及び真数の表は、ｗ次原始多項式を含む伝播方法を使用して計算することができる。
【００４１】
ミラー冗長性方式は、概念的にはより簡単であり、さまざまな再構成オペレーションに明らかに向いている。たとえば、３ブリックトリプルミラー冗長性方式の１つのブリックが故障した場合、ダブルミラーリング冗長性方式の下で、残りの２つのブリックを２ブリックミラー対として再構成することができる。或いは、新しいブリックを選択して、故障したブリックと取り替えることができ、残存しているブリックの１つからこの新しいブリックへデータをコピーして、３ブリックトリプルミラー冗長性方式を復元することもできる。対照的に、イレージャ符号化冗長性方式の再構成は、それほど簡単ではない。たとえば、ストライプ内の各チェックサムワードは、そのストライプのすべてのデータワードに依存している。４＋２イレージャ符号化冗長性方式を８＋２イレージャ符号化冗長性方式に変換することが望まれる場合、チェックサムビットのすべてが再計算される場合があり、データは、４＋２方式の６個のブリックの関連があるコンテンツを新しいロケーションにコピーするのではなく、新しい８＋２方式に使用される１０個のブリック上に再分散される場合がある。その上、同じイレージャ符号化方式のストライプサイズの変更であっても、チェックサムデータユニットのすべてを再計算し、それらデータを新しいブリックロケーションに再分散させることが伴う場合がある。ミラーリング冗長性方式の場合には、元のブリックから新しいブリックへデータをコピーすることで、複数のブリックの１つのブリックの消去又は１つのブリックの追加を行うが、イレージャ符号化方式に対する変更は、ほとんどの場合、そのような消去又は追加ではなく、古い構成から取り出されたデータに基づいて新しい構成を完全に構築することを伴う。ミラーリングは、一般に、イレージャ符号化よりも空間効率がよくないが、処理サイクルの時間及び費用の効率はよい。
【００４２】
［ＦＡＢストレージユニット］
上述したように、ＦＡＢシステムは、膨大な量のデータストレージ空間を提供することができる。全ストレージ空間は、階層的なデータユニットに論理的に区画することができ、最も低くない各階層レベルのデータユニットは、次に最も低い（next-lowest）階層レベルのデータユニットで論理的に編成される。論理データユニットは、１つ又は複数のブリック内の物理ストレージ空間にマッピングすることができる。
【００４３】
図７は、本発明の一実施の形態を表す、現在のＦＡＢの実施態様で使用される階層的なデータユニットを示している。最上位レベルのデータユニットは、「仮想ディスク」と呼ばれ、ＦＡＢシステム内の全利用可能ストレージ空間は、１つ又は複数の仮想ディスクに区画されているとみなすことができる。図７では、全ストレージ空間７０２は、第１の仮想ディスク７０４を含む５つの仮想ディスクに区画されて示されている。仮想ディスクは、「セグメント」と呼ばれる次に最も低い階層的なデータユニットのサイズ以上の任意のサイズを有するように構成することができる。図７では、第３の仮想ディスク７０６は、複数のセグメント７０８に論理的に区画されていることが示されている。これらのセグメントは、連続して順序付けることができ、合わせることによって、仮想ディスクに対応する線形論理ストレージ空間を構成する。図７に示すように、セグメント４（図７の７１０）等の各セグメントは、特定の冗長性方式に従って複数のブリック７１２上に分散させることができる。セグメントは、ブリックにわたるデータ分散の粒度を表している。たとえば、図７では、セグメント４（図７の７１０）は、８＋２イレージャ符号化冗長性方式に従ってブリック１〜９及び１３上に分散させることができる。したがって、８＋２イレージャ符号化冗長性方式の下で、パリティデータがセグメントデータとは別に記憶される場合、ブリック３は、セグメントデータの８分の１を記憶することができ、ブリック２は、セグメントのパリティデータの２分の１を記憶することができる。ブリック７（図７の７１４）等の各ブリックは、そのブリックの内部ディスク７１６のいずれか又はキャッシュメモリ上に、セグメント又はセグメントの一部を分散させることを決めることができる。セグメント又はセグメントの一部は、内部ディスク又はキャッシュメモリに記憶されると、図７に示すページ７１８等の複数のページを備えていると論理的にみなされる。各ページは、図７に示すブロック７２０等の連続した一連のブロックを備える。ブロック（たとえば、図７の７２０）は、タイムスタンプが関連付けられているデータユニットレベルである。タイムスタンプは、後述するストレージレジスタデータ一貫性レジーム（storage register data-consistency regime）に従って管理される。開発中の或るＦＡＢシステムでは、セグメントは、連続した２５６メガバイトを備え、ページは、８メガバイトを備え、ブロックは５１２バイトを備える。
【００４４】
図８Ａ〜図８Ｄは、本発明の一実施の形態を表す、ＦＡＢシステムのブリック及び内部ディスクへの論理データユニットの仮想的なマッピングを示している。図８Ａ〜図８Ｄは、すべて、図８Ａに関して次に解説する同じ説明図の規則を使用している。ＦＡＢシステムは、１６個のブリック８０２〜８１７として表されている。各ブリックは、ブリック８０２内の内部ディスクドライブ８２０〜８２３等、４つの内部ディスクドライブを含むものとして示されている。図８Ａ〜図８Ｄにおいて、図示されている論理データユニットは、図の左側に示されている。図８Ａで図示される論理データユニットは、全利用可能ストレージ空間８２６である。内部ディスクドライブの正方形表現内の陰影は、その図で図示される論理データユニットがマッピングされる内部ディスクドライブの領域を示している。たとえば、図８Ａでは、全ストレージ空間８２６は、すべてのブリックのすべての内部ディスクにおいて利用可能な全空間にわたってマッピングされることが示されている。一定の少量の内部ストレージ空間を、各ブリックの制御ロジックによる制御目的及び管理目的で予約できることに留意すべきであるが、その内部空間は、図８Ａには示されていない。また、データは、ディスクに書き込まれる前に、ランダムアクセスメモリのキャッシュに存在する場合があるが、このストレージ空間は、説明図を簡単にするために、図８Ａ〜図８Ｄにおいては、各ブリックについて４つの内部ディスクのみを備えているとみなされる。
【００４５】
図８Ｂは、ＦＡＢシステム８００のストレージ空間への仮想ディスク論理データユニット８２８の一例示のマッピングを示している。図８Ｂは、ＦＡＢシステム８００のブリック内の多くの内部ディスクの一部に、又は、すべての内部ディスクの一部にも仮想ディスクをマッピングできることを示している。図８Ｃは、ＦＡＢシステム８００の内部ストレージ空間への仮想ディスクイメージ論理データユニット８３０の一例示のマッピングを示している。仮想ディスクイメージ論理データユニットは、ＦＡＢシステム内のかなりの個数のブリックの内部ストレージ空間の大部分にマッピングすることができる。仮想ディスクイメージ論理データユニットは、仮想ディスクのコピー又はイメージを表している。高レベルの冗長性を提供するために、仮想ディスクは、２つ以上の仮想ディスクイメージとして複製することができる。各仮想ディスクイメージは、ＦＡＢシステム内のブリックの別々のパーティションに置かれる。仮想ディスクの複製によって、たとえば、ＦＡＢシステム内のブリックの地理的に異なった別々のパーティション上に仮想ディスクを複製することが可能になり、１つの地理的ロケーションにおける大規模な惨事が仮想ディスクデータの回復不可能な損失にならないようにされる。
【００４６】
図８Ｄは、ＦＡＢシステム８００のブリック内の内部ストレージ空間へのセグメント８３２の一例示のマッピングを示している。図８Ｄに見ることができるように、セグメントは、ＦＡＢシステム内のブリックの比較的小さなサブセットの内部ディスクの多くの小さな部分にマッピングすることができる。上述したように、セグメントは、本発明の多くの実施の形態では、イレージャ符号化方式及びミラーリング方式を含む下位レベル冗長性方式によるデータの分散のための論理データユニットレベルである。したがって、データ冗長性が所望されていない場合には、セグメントを単一のブリックの単一のディスクドライブにマッピングすることができる。一方、ほとんどの目的では、セグメントは、２つのブリックに少なくともミラーリングされる。上述したように、ブリックは、セグメントのページ又はセグメントの一部を、さまざまな考慮すべき事項に従ってその内部ディスク間に分散させる。これらさまざまな考慮すべき事項には、利用可能な空間が含まれ、また、内部ディスクドライブのさまざまな特性を利用するための最適な分散が含まれる。これら内部ディスクドライブのさまざまな特性には、ヘッドの移動遅延、回転遅延、アクセス頻度、及び他の考慮すべき事項が含まれる。
【００４７】
図９は、本発明の一実施の形態を表す、ＦＡＢシステム内で使用される論理データユニットを示している。全利用可能データストレージ空間９０２は、仮想ディスク９０４〜９０７に区画することができる。仮想ディスクは、次に、所望される場合に、複数の仮想ディスクイメージに複製される。たとえば、仮想ディスク９０４は、仮想ディスクイメージ９０８〜９１０に複製される。仮想ディスクが複製されない場合、仮想ディスクは、単一の仮想ディスクイメージを備えているとみなすことができる。たとえば、仮想ディスク９０５は、単一の仮想ディスクイメージ９１２に対応する。各仮想ディスクイメージは、順序付けられた一連のセグメントを備える。たとえば、仮想ディスクイメージ９０８は、セグメントの順序付きリスト９１４を備える。各セグメントは、冗長性方式に従って１つ又は複数のブリックにわたって分散される。たとえば、図９では、セグメント９１６は、８＋２イレージャ符号化冗長性方式に従って１０個のブリック９１８にわたって分散される。別の例では、セグメント９２０は、トリプルミラーリング冗長性方式に従って３つのブリック９２２にわたって分散されたものとして図９に示されている。
【００４８】
［ＦＡＢデータ状態記述データ構造体］
上述したように、ＦＡＢシステム内の各ブリックは、基本的に同じ制御プログラムを実行することができ、各ブリックは、リモートホストコンピュータからの要求を受信することができ、その要求に応答することができる。したがって、人体の各細胞が有機体全体の全ＤＮＡの符号化された構造（DNA-encoded architecture）を含むのとほとんど同じように、各ブリックは、個々のブリックによって適切に管理されるブリック特有の状態情報（一般的には、この状態情報は含まない）に至るまで、ＦＡＢシステムの全データ状態を表すデータ構造体を、内部の揮発性ランダムアクセスメモリ、不揮発性メモリ、及び／又は内部ディスク空間に含む。全データ状態は、ブリックの動作状態、すなわち健全性と、セグメントが記憶される冗長性方式とに関する情報と共に、図９に示す階層的なデータユニットのサイズ及びロケーションを含む。一般に、内部のページ及びブリック内に記憶されたデータのブロックアドレスを含めて、ブリック特有のデータ状態情報は、ＦＡＢシステムの全データ状態の一部とはみなされない。
【００４９】
図１０Ａは、各ブリックによって保持されるデータ構造体であって、ＦＡＢシステムの全データ状態を記述し、且つ、本発明の一実施の形態を表すデータ構造体を示している。このデータ構造体は、一般に、前の小節で説明した階層的な論理データユニットをミラーリングするために階層的である。最上位レベルでは、データ構造体は、仮想ディスクテーブル１００２を含むことができる。仮想ディスクテーブル１００２の各エントリーは、仮想ディスクを記述する。各仮想ディスクテーブルエントリー（「ＶＤＴＥ」）は、１つ又は複数の仮想ディスクイメージ（「ＶＤＩ」）テーブルを参照することができる。たとえば、ＶＤＴＥ１００４は、図１０Ａでは、ＶＤＩテーブル１００６を参照する。ＶＤＩテーブルは、仮想ディスクイメージの各セグメントについて、セグメント構成ノード（「ＳＣＮ」）への参照子を含むことができる。このデータ構造体に充てられるメモリ及びストレージ空間を節約するために、複数のＶＤＩテーブルエントリーは、単一のＳＣＮを参照することができる。図１０Ａでは、ＶＤＩテーブルエントリー１００８はＳＣＮ１０１０を参照する。各ＳＣＮは、１つ又は複数の構成グループ（「ｃｇｒｐ」）を表すことができる。たとえば、図１０Ａでは、ＳＣＮ１０１０はｃｇｒｐ１０１２を参照する。各ｃｇｒｐは、１つ又は複数の構成（「ｃｆｇ」）を参照することができる。たとえば、図１０Ａでは、ｃｇｒｐ１０１４はｃｆｇ１０１６を参照する。最後に、各ｃｆｇは、単一のレイアウトのデータ構造体要素に関連付けることができる。たとえば、図１０Ａでは、ｃｆｇ１０１６は、レイアウトデータ構造体要素１０１８に関連付けられている。レイアウトデータ構造体要素は、関連付けられているｃｆｇ内に収容しても、ｃｆｇとは別個としてもよく、関連付けられているｃｆｇ内にブリックの表示を含んでもよい。ＶＤＩテーブルは、かなり大きな場合があり、効率的なストレージ方式を使用して、ＶＤＩテーブル又はＶＤＩテーブルの一部をメモリ及び不揮発性記憶媒体に効率的に記憶することができる。たとえば、ＵＮＩＸ（登録商標）のようなｉノード構造体がある。このｉノード構造体は、セグメントへの参照子を直接含んだルートノードと、間接参照子又は２重間接参照子を有する追加ノードとを有する。２重間接参照子は、ｉノード参照子を含んだノードを通じて、セグメント参照子を含んだ追加ノードに向かう参照子である。他の効率的なストレージ方式も可能である。
【００５０】
ＶＤＩテーブルと、ＦＡＢシステムの全データ状態を記述する、各ブリックによって保持されるデータ構造体の他のすべてのデータ構造体要素との双方について、多種多様な物理表現及びストレージ技法を使用することができる。一例として、可変長のデータ構造体要素を、可能な最大個数のデータエントリー又は予想される最大個数のデータエントリーを収容するのに十分なサイズの固定長のデータ構造体要素として割り当てることができる。或いは、可変長のデータ構造体要素は、リンクリスト、ツリー、又は、他のこのような動的なデータ構造体要素として表すこともできる。他のこのような動的なデータ構造体要素とは、新しいデータを収容するか、又はもはや必要とされないデータを削除するために、必要に応じてリアルタイムでサイズの変更が可能なものである。図１０Ａ及び図１１Ａ〜図１１Ｈに示すツリーのような表現において、分離され且つ区別されるものとして表されているノードは、実際の実施態様では、共にテーブルに記憶することができる。ただし、ノード又はテーブルに記憶されるものとして示されているデータ構造体要素は、代替的に、リンクリスト、ツリー、又はより複雑な他のデータ構造体の実施態様に記憶することもできる。
【００５１】
上述したように、ＶＤＩは、仮想ディスクの複製を表すのに使用することができる。したがって、ＶＤＴＥからＶＤＩへの階層的なファンアウトは、仮想ディスクの複製を表しているとみなすことができる。ＳＣＮは、或る冗長性方式から別の冗長性方式へのセグメントのマイグレーションを可能にするのに使用することができる。４＋２イレージャ符号化冗長性方式に従って分散されたセグメントを８＋２イレージャ符号化冗長性方式へ転写することが望ましいか又は必要な場合がある。セグメントのマイグレーションには、場合によっては新しいブリックグループにわたって分散される新しい冗長性方式の空間を作成すること、新しい構成を既存の構成と同期させること、および新しい構成が既存の構成と同期されると既存の構成を削除することが伴う。したがって、マイグレーションが行われている期間中、ＳＣＮは、或る冗長性方式の下での既存の構成と異なる冗長性方式の下での新しい構成とを含む過渡状態を表す２つの異なるｃｇｒｐを同時に参照することができる。マイグレーション中にセグメントに対して実行されるデータ変更オペレーション及びデータ状態変更オペレーションは、完全な同期が達成されるまで、過渡状態の双方の構成に対して実行され、古い構成は削除することができる。同期には、新しい構成のすべてのブロックについて、後述するクォーラムを確立すること、必要に応じて古い構成から新しい構成へデータをコピーすること、およびマイグレーション中にセグメントに向けられたオペレーションを実行するのに必要とされるすべてのデータ更新を実行することが伴う。場合によっては、新しい構成の構築中の故障によって、構成が回復不可能な損傷を受けたまま残されるので、過渡状態は、新しい構成が完全に構築されるまで維持される。後述する場合を含めて、それ以外の場合には、古い構成のすべての既存のクォーラムは、新しい構成で引き続き有効であるので、最小限の同期しか必要ない。
【００５２】
既存の冗長性方式に従ってセグメントを分散させる一組のブリックは、新しい冗長性方式に従ってセグメントを分散させる一組のブリックと重なり合う場合がある。したがって、セグメントが現在マイグレーション中である場合に、ＦＡＢシステム内のブロックアドレスは、その特定の冗長性方式を記述する追加フィールド又は追加オブジェクト、すなわちブロックのロールを含むことができる。したがって、ブロックアドレスは、２つの異なる冗長性方式の下で単一のブリックに記憶された同じセグメントの２つのブロックを区別する。図１０Ｂは、本発明の一実施の形態によるブリックロールを組み込んだブリックセグメントアドレスを示している。図１０Ｂに示すブロックアドレスは、次のフィールド、すなわち、（１）そのブロックアドレスによって参照されるブロックを含んだブリックの識別情報を含むブリックフィールド１０２０、（２）そのブロックアドレスによって参照されるブロックを含んだセグメントの識別情報を含むセグメントフィールド１０２２、（３）セグメントフィールドで特定されるセグメント内のブロックの識別情報を含むブロックフィールド１０２４、（４）セグメントが記憶される冗長性方式の表示を含むフィールド１０２６、（５）セグメントがイレージャ符号化冗長性方式の下で記憶される場合に、イレージャ符号化冗長性方式内のブリックフィールドによって特定されるブリックのブリック位置の表示を含むフィールド１０２８、及び（６）セグメントがイレージャ符号化冗長性方式の下で記憶される場合に、イレージャ符号化冗長性方式のストライプサイズの表示を含むフィールド１０３０、を含む。ブロックアドレスは、必要に応じて、所与のＦＡＢの実施態様においてブロックの位置を十分に記述するための追加フィールドを含むことができる。一般に、フィールド１０２６、１０２８、及び１０３０は、合わさってブリックロールを構成する。このブリックロールは、参照されたブロックを記憶しているブリックが果たす役割を定義するものである。冗長性方式、ブリック位置、及びストライプサイズのさまざまな数値符号化のいずれを使用しても、ブリックロール符号化に充てられるビット数を最小にするすることができる。たとえば、このＦＡＢの実施態様が、さまざまなイレージャ符号化冗長性方式について少数の異なるストライプサイズしか使用しない場合、ストライプサイズは、或る一覧表のさまざまな値によって表すことができる。すなわち、換言すれば、少数の異なるストライプサイズの数値表現を含むのに十分な比較的小さなビットフィールドによって表すことができる。
【００５３】
ｃｇｒｐは、再構成を受けている時、複数のｃｆｇデータ構造体要素を参照することができる。再構成は、セグメントを分散させるブリックの変更を伴う場合があるが、ミラーリング冗長性方式からイレージャ符号化冗長性方式への変更、４＋３等の或るイレージャ符号化冗長性方式から８＋２等の別のイレージャ符号化冗長性方式への変更、又は、複数のブリックのコンテンツの再構成若しくは変更を伴う他のこのような変更を伴う場合はない。たとえば、再構成は、ブリック１、２、及び３に記憶されているトリプルミラーをブリック２及び３に記憶されるダブルミラーに再構成することを伴う場合がある。
【００５４】
ｃｆｇデータ構造体要素は、一般に、特定の冗長性方式の下で特定のセグメントを共に記憶する一組の１つ又は複数のブリックを記述する。ｃｆｇデータ構造体要素は、一般に、ｃｆｇデータ構造体要素によって表される構成内のブリックの健全性、すなわち動作状態についての情報を含む。
【００５５】
図１０Ａのレイアウト１０１８等のレイアウトデータ構造体要素は、特定の冗長性方式の下で特定のセグメントを分散させるすべてのブリックの識別子を含む。レイアウトデータ構造体要素は、表されるセグメントが記憶される特定の冗長性方式を記述する１つ又は複数のフィールドを含むことができ、追加フィールドも含むことができる。図１０Ａに示すデータ構造体の他のすべての要素は、必要に応じて、データ構造体によって表されるデータ分散方式に従ったデータの記憶及び維持を容易にするための追加フィールド及び記述的サブ要素を含むことができる。図１０Ａの下部には、次に続くレベルのデータ構造体要素間のマッピング関係の表示が設けられている。１つ又は複数のＶＤＩテーブル内の複数の異なるセグメントエントリーは、単一のＳＣＮノードを参照でき、同じ冗長性方式に従った、同一の一組のブリックにわたる異なるセグメントの分散を表していることに留意すべきである。
【００５６】
各ブリックによって保持されるデータ構造体であって、ＦＡＢシステムの全データ状態を記述し、且つ、本発明の一実施の形態を表すデータ構造体は、絶えず変化する動的表現であり、且つ、ブロックが記憶、アクセス、及び削除される、ブリックが追加及び削除される、ブリック及び相互接続が故障する、冗長性方式並びにＦＡＢシステムの他のパラメータ及び特性が管理インターフェースを通じて変更される、並びに他のイベントが発生するときに、さまざまな制御ルーチンを引き起こして状態変化をさらに起こす動的表現である。ロック方式がデータ構造体の一部に向けられたオペレーションを制御して直列化するための大きなオーバーヘッドを回避するために、ｃｇｒｐレベルからレイアウトレベルに至るまでのすべてのデータ構造体要素は、不変であるとみなすことができる。それらのコンテンツ又は相互接続を変更する必要がある場合、ｃｇｒｐレベルからレイアウトレベルに至るまでのデータ構造体要素がロックされて、変更され、そしてロック解除されるのではなく、新しいコンテンツ及び／又は新しい相互接続を有する新しいデータ構造体要素が追加され、前のバージョンへの参照子が最終的には消去される。この方法で取って代わられたデータ構造体要素は、古いデータ構造体要素によって表されるデータ及び新しいデータ構造体要素によって表されるデータが、新しいクォーラムを確立してあらゆる必要な更新を実行することにより同期された後、最終的には孤立状態になり、そして、孤立状態のデータ構造体要素は、その後、ガベージコレクトされる。この手法は、ｃｇｒｐレベルからレイアウトレベルに至るまでのデータ構造体要素を不変であると呼ぶことによって要約することができる。
【００５７】
各ブリックによって保持されるデータ構造体であって、ＦＡＢシステムの全データ状態を記述し、且つ、本発明の一実施の形態を表すデータ構造体の別の態様は、各ブリックが、データ構造体のメモリ内バージョン又は部分的なメモリ内バージョンと、不揮発性データ記憶媒体に記憶された永続バージョンとの双方を保持できることである。メモリ内バージョン又は部分的なメモリ内バージョンは、最も頻繁にアクセスされるレベル及びデータ構造体要素並びに最も近時にアクセスされたレベル及びデータ構造体要素に高速アクセスするために保持される。データ構造体のメモリ内バージョンのデータ要素は、データ構造体の永続バージョンには含まれない追加フィールドを含むことができる。この追加フィールドは、一般に、図１０Ａ、図１１Ａ〜図１１Ｈ、及びその後の図には示されていない。たとえば、メモリ内バージョンは、ポインタ等の逆マッピング要素を含むことができる。この逆マッピング要素によって、図に示すポインタの下向き方向によって示されるトップダウンのトラバースに加えて、ボトムアップ方向、横方向、及びより複雑な方向でのデータ構造体の効率的なトラバースが可能になる。データ構造体のメモリ内バージョンのデータ構造体要素の中のいくつかのものは、参照カウントフィールドも含むことができる。この参照カウントフィールドによって、ガベージコレクションが容易になり、且つ、そのデータ構造体を含んだブリックの状態を変更する、制御ルーチンの実行するオペレーションの調整が容易になる。
【００５８】
図１１Ａ〜図１１Ｈは、本発明の一実施の形態を表す、ＦＡＢシステム内における図１０Ａに示すデータ記述データ構造体に反映されるさまざまな異なるタイプの構成の変更を示している。図１１Ａ〜図１１Ｄは、ブリックの健全性ステータスの変更を伴う簡単な構成の変更を示している。この場合、トリプルミラーリング冗長性方式に従ってブリック１、２、及び３上に分散されたセグメント（図１１Ａの１１０２）は、（１）ブリック３の修復により、トリプルミラーリング方式に従ってブリック１、２、及び３（図１１Ｂの１１０４）上、（２）ブリック３の故障及びブリック４内のスペアのストレージ空間によるブリック３の取り替えにより、トリプルミラーリング方式に従ってブリック１、２、及び４（図１１Ｃの１１０６）上、又は（３）ブリック３の故障により、ダブルミラーリング方式に従ってブリック１及び２（図１１Ｄの１１０８）上、のいずれかに分散されるように再構成される。ブリック３の故障が最初に検出されると、新しいｃｇｒｐ１１１２がデータ構造体に追加される。この新しいｃｇｒｐ１１１２は、ブリック３がデッドであることを示すブリック３のブリック健全性表示１１１４を有する新しいｃｆｇ１１１０に加えて、初期ｃｆｇのコピー１０１１も含む。この追加によって、分散されたセグメントの初期ｃｇｒｐ、初期ｃｆｇ、及び初期レイアウト表現が取り替えられる（図１１Ａの１１０２）。ブリック３の健全性ステータスとして記憶される「デッドブリック」表示は、図１０Ａに示す全データ構造体の重要な特徴である。「デッドブリック」ステータスによって、その後に故障したブリックの以前の関与の記録をデータ構造体に保存することが可能になり、それによって、その後の同期、及び、故障したブロックの前の関与に気付くことが必要となり得る他のオペレーションが可能になる。ブリック３の故障により現在のクォーラムを有しないブロックの新しいクォーラムを確立することを含めて、初期構成と新しい構成との間のあらゆる同期が完了し、分散されたセグメント１１１６の新しい表現がデータ構造体に追加されると、データ構造体要素１１１０〜１１１２を備える分散されたセグメントの過渡的な２−ｃｆｇ表現を消去してガベージコレクトすることができ、ブリック３が故障したことを示す単一のｃｆｇデータ構造体を有する分散されたセグメント１１１６の最終的な表現が残される。図１１Ａ〜図１１Ｄ及びその後の図では、たとえば、図１１Ａに示すｃｇｒｐが１つ又は複数のＳＣＮノードによって参照されるとの理解を前提にして、データ構造体の関連がある部分のみが示されている。
【００５９】
図１１Ｂ〜図１１Ｄは、ブリック３が故障した場合の３つの異なる結果を説明している。各結果は、図１１Ａの下部に示す、分散されたセグメント１１１６の表現から開始している。３つのすべての結果には、データ構造体の中間状態として示す過渡的な２−ｃｆｇ状態が伴う。この過渡的な２−ｃｆｇ状態は、２つの新しいｃｆｇデータ構造体要素を参照するさらに別の新しいｃｇｒｐで構成される。２つの新しいｃｆｇデータ構造体要素の一方は、図１１Ａの下部に示す分散されたセグメント１１１６の表現からのｃｆｇのコピーを含み、他方は、新しいブリック健全性情報を含む。図１１Ｂでは、ブリック３が修復され、過渡的な２−ｃｆｇ１１１８は、ブリック３の故障状態の記述と、ブリック３の修復状態の記述との双方を含む。図１１Ｃでは、ブリック３は、ブリック４のスペアのストレージ空間によって取り替えられており、過渡的な２−ｃｆｇ状態１１２０は、ブリック３の故障状態の記述と、ブリック３がブリック４によって取り替えられた新しい構成の記述との双方を含む。図１１Ｄでは、ブリック３は完全に故障し、セグメントは、３つのブリックではなく２つのブリック上への分散に再構成され、過渡的な２−ｃｆｇ状態１１２２は、ブリック３の故障状態の記述と、データがブリック１及び２上に分散されているダブルミラーリング構成の記述との双方を含む。
【００６０】
図１１Ｅ及び図１１Ｆは、４＋２イレージャ符号化冗長性方式に従ってセグメントが分散されるブリックが喪失され、その喪失されたブリックの代わりに新しいブリックが使用されることを示している。最初に、セグメントは、ブリック１、４、６、９、１０、及び１１上に分散されている（図１１Ｅの１１２４）。ブリック４の故障が検出されると、２つの新しいｃｆｇデータ構造体要素を参照する新しいｃｇｒｐを含んだ過渡的な２−ｃｆｇ状態１１２６が、ブリック４が故障したことを示す新しいｃｆｇ１１２８を得る。分散されたセグメント１１２４の初期表現は、その後、ガベージコレクトすることができる。故障したブリック４を有する新しい構成の同期が古い構成に対して実行され、ブリック４が故障したことを示す単一のｃｆｇデータ構造体要素を参照する新しいｃｇｒｐを有する、分散されたセグメント１１３２の記述が追加されると、過渡的な２−ｃｆｇ表現１１２６をガベージコレクトすることができる。次に、新しい構成が追加されて、過渡的な２−ｃｆｇ状態１１３３が作成される。この新しい構成は、ブリック５におけるスペアのストレージ空間が、ブリック４により前に提供されたストレージ空間に取って代わったものである。その後、前の表現１１３２はガベージコレクトされる。ブリック５がブリック４に取って代わった新しい構成の同期が完了し、分散されたセグメントの最終的な新しい表現１１３６が追加されると、過渡的な２−ｃｆｇ表現１１３４をガベージコレクトすることができる。
【００６１】
図１１Ｆのｃｆｇ１１３５等の新しい構成が、図１１Ｆのｃｆｇ１１３４等の古い構成と同期されている時間の間、図１１Ｆのｃｆｇ１１３４及び１１３５等の２−ｃｆｇ過渡状態の２つの代替的な構成は、図１１Ａ〜図１１Ｆに示す過渡的な２−ｃｆｇ表現に同時に保持される。たとえば、ブリック５のコンテンツが、前の小節で解説した行列反転方法に従って再構築されている間、セグメントに発行される新しいＷＲＩＴＥ（書き込み）オペレーションは双方の構成に発行され、それらのＷＲＩＴＥオペレーションが、各構成におけるブリックのクォーラムで成功して完了することが確実にされる。クォーラム及び他の一貫性メカニズムについては後述する。最後に、新しい構成１１３５が完全に再構築され、新しい構成のデータ状態が、古い構成のデータ状態１１１４に対して完全に同期されると、古い構成は、表現１１３３全体を、最終的な構成のみを含む新しい表現１１３６と取り替えることによって削除することができる。過渡的な２−ｃｆｇ表現は、その後ガベージコレクトされる。ｃｇｒｐレベル及びそれより低レベルの既存のデータ構造体要素を変更しないが、その代わり、２−ｃｆｇ過渡状態を通じて新しいデータ構造体要素を追加することによって、適切な同期を完成させることができ、データ構造体へのアクセスを制御するために、ロッキングも他の直列化技法も使用する必要はない。ＷＲＩＴＥオペレーションは、１つ又は複数のブリック内のデータ状態を変更する、データに対するオペレーションの例示である。したがって、この解説では、ＷＲＩＴＥオペレーションは、オペレーション又はタスクの実行中に、ＦＡＢシステムのデータ状態が変更されることにより、データ一貫性問題が発生するそれらオペレーション又はタスクのクラスを表すのに使用される。一方、他のオペレーション及びタスクもデータ状態を変更する場合があり、このような他のオペレーション及びタスクがＦＡＢの実施態様で実行される場合に、上述した技法によって、構成間の適切な遷移が可能になる。さらに他の場合において、初期構成の下でのブロックのすべてのクォーラムが、基本的に変更されずに維持され、且つ、新しい構成において有効であるとき、２−ｃｆｇ過渡表現が必要とされない場合があり、長い期間保持する必要がない場合がある。たとえば、ダブルミラーリングされたセグメントが、２つのブリックの一方の故障によって非冗長構成に再構成される場合、すべてのクォーラムは有効のままである。その理由は、ダブルミラーリングされた構成のブリックの過半数が各ブロックの値について一致していることを必要とされていたからである。これは、したがって、すべてのブリックが前の構成で一致していたことを意味する。２つのブリックの一方の喪失に起因して、あいまいさも損傷したクォーラムも生じない。
【００６２】
図１１Ｇは、ＦＡＢシステムのブリック上にセグメントを分散させる冗長性方式の変更を伴う、さらに複雑な構成の変更を示している。図１１Ｇに示すケースでは、当初、４＋２イレージャ符号化冗長性に従ってブリック１、４、６、９、１０、及び１１（図１１Ｇの１１４０）上に分散されたセグメントが、ブリック４、１３、及び１８（図１１Ｇの１１４２）上のトリプルミラーリング冗長性方式にマイグレーションされる。冗長性方式の変更は、新しい構成１１２８が前の構成１１４０と同期されている間、ＳＣＮノード１１４６から参照される２つの異なるｃｇｒｐデータ構造体要素１１４４〜１１４５を保持することを伴う。新しい構成が古い構成と同期されている間、ＳＣＮレベルの制御ロジックは、２つの異なる構成に対するＷＲＩＴＥオペレーションの方向を調整する。その理由は、ＷＲＩＴＥオペレーションの一貫性のある実行を確実にするための技法が、２つの異なる冗長性方式の間で異なるからである。ＳＣＮノードをロックすることができ、また、ＳＣＮノードへのアクセスを別の方法で操作可能に制御することもできるので、ＳＣＮノードの状態をマイグレーション中に変更することができる。しかしながら、ＳＣＮノードは、複数のＶＤＩテーブルエントリーによって参照される場合があるので、新しいＳＣＮノード１１４６が、一般に、マイグレーションオペレーション用に割り当てられる。
【００６３】
最後に、図１１Ｈは、ＦＡＢシステム内の仮想ディスクの一例示の複製を示している。仮想ディスクは、単一のＶＤＩテーブル１１５０を参照するＶＤＴＥエントリー１１４８によって表される。仮想ディスクの複製は、元のＶＤＩテーブル１１５０と共に、ＶＤＴＥ１１３２から同時に参照される新しいＶＤＩテーブル１１５２を作成することを伴う。制御ロジックの階層内における仮想ディスクレベルの制御ロジックは、新しいＶＤＩの前のＶＤＩとの同期を調整し、同期プロセス中に仮想ディスクに向けられるＷＲＩＴＥオペレーションを受け止め続ける。
【００６４】
図１０Ａに示すデータ記述データ構造体内における階層レベルは、ＦＡＢシステムの各ブリックによって実行される制御ロジック内における制御ロジックレベルを反映している。この制御ロジックレベルは、データ状態記述データ構造体の対応するレベルにおけるデータ構造体要素と、そのレベルよりも下のデータ構造体要素とを操作する。ホストコンピュータから受信された要求は、最初に、最上位処理レベルで受信され、最上位処理レベルにより、実行用の１つ又は複数のオペレーションとして、適切な仮想ディスクに向けられる。仮想ディスクレベルの制御ロジックは、次に、仮想ディスクの１つ又は複数の複製を表す１つ又は複数のＶＤＩにこのオペレーションを向ける。ＶＤＩレベルの制御ロジックは、オペレーションが向けられる１つ又は複数のＶＤＩのセグメントを決定し、適切なセグメントにオペレーションを向ける。ＳＣＮレベルの制御ロジックは、オペレーションを適切な構成グループに向け、構成グループレベルの制御ロジックは、オペレーションを適切な構成に向ける。構成レベルの制御ロジックは、要求をその構成のブリックに向け、ブリック内の内部ブリックレベル制御ロジックは、要求を内部ディスクドライブ内の特定のページ及びブロックにマッピングして、ローカルな物理アクセスオペレーションを調整する。
【００６５】
［ストレージレジスタモデル］
ＦＡＢシステムは、クォーラムベースの分散ＲＥＡＤ（読み出し）オペレーション及び分散ＷＲＩＴＥ（書き込み）オペレーションについてストレージレジスタモデルを使用することができる。ストレージレジスタは、データの分散単位である。現在のＦＡＢシステムでは、ブロックがストレージレジスタとして扱われる。
【００６６】
図１２〜図１８は、分散ストレージレジスタの基本オペレーションを示している。図１２に示すように、分散ストレージレジスタ１２０２は、好ましくは、或る特定の電子デバイスのハードウェアで実施される物理レジスタではなく、抽象的なレジスタ、すなわち仮想レジスタである。プロセッサ又はコンピュータシステム１２０４〜１２０８で実行される各プロセスは、分散ストレージレジスタに関係する少数のルーチンと共に、ダイナミックメモリに記憶された少数の値を使用して、分散ストレージレジスタ１２０２を共同で実施する。これら少数の値は、オプションとして、不揮発性メモリにバックアップされる。最低でも、一組の記憶された値及びルーチンが、分散ストレージレジスタにアクセスする各処理エンティティに関連付けられる。いくつかの実施態様では、物理プロセッサ又はマルチプロセッサシステムで実行される各プロセスは、それ自身の記憶された値及びルーチンを管理することができ、他の実施態様では、特定のプロセッサ又はマルチプロセッサシステムで実行されるプロセスは、記憶された値及びルーチンを共有することができるが、共有がローカルに調整されて、プロセッサで実行される複数のプロセスによる同時アクセス問題が防止されることが条件である。
【００６７】
図１２では、各コンピュータシステムは、分散ストレージレジスタのローカル値１２１０〜１２１４を保持する。一般に、異なるコンピュータシステムによって記憶されたローカル値は通常、同一であり、分散ストレージレジスタ１２０２の値と等しい。しかしながら、時に、ローカル値は、図１２に示す例のように、すべて同一であるとは限らない場合がある。この場合、コンピュータシステムの過半数が、現在ローカルに記憶されている単一の値を保持している場合、分散ストレージレジスタの値が過半数保持値（majority-held value）となる。
【００６８】
分散ストレージレジスタは、当該分散ストレージレジスタを共同で実施する複数の相互通信プロセスに２つの基本高レベル関数を提供する。図１３に示すように、プロセスは、ＲＥＡＤ要求１３０２を分散ストレージレジスタ１２０２に向けることができる。図１４において分散ストレージレジスタ１２０２内に値「Ｂ」により示すように、分散ストレージレジスタが有効な値を現在保持している場合、この現在の有効な値が要求側プロセスへ返される（１４０２）。一方、図１５に示すように、分散ストレージレジスタ１２０２が現在、有効な値を含んでいない場合、値ＮＩＬ１５０２が要求側プロセスへ返される。値ＮＩＬは、分散ストレージレジスタ内に記憶されている有効な値となることができない値である。
【００６９】
また、プロセスは、分散ストレージレジスタに値を書き込むこともできる。図１６では、プロセスは、ＷＲＩＴＥメッセージ１６０２を分散ストレージレジスタ１２０２へ向ける。このＷＲＩＴＥメッセージ１６０２は、分散ストレージレジスタ１２０２に書き込まれる新しい値「Ｘ」を含む。図１７に示すように、分散ストレージレジスタに現在どのような値が記憶されていようとも、分散ストレージレジスタへ送信された値の上書きが成功した場合、ブール値「ＴＲＵＥ」が、ＷＲＩＴＥ要求を分散ストレージレジスタへ向けたプロセスへ返される（１７０２）。そうでない場合、図１８に示すように、ＷＲＩＴＥ要求は失敗し、ブール値「ＦＡＬＳＥ」が、ＷＲＩＴＥ要求を分散ストレージレジスタへ向けたプロセスへ返され（１８０２）、分散ストレージレジスタに記憶された値は、ＷＲＩＴＥ要求によって変更されない。一定の実施態様では、分散ストレージレジスタは、２値「ＯＫ」及び「ＮＯＫ」を返す。ＯＫは、ＷＲＩＴＥ要求の実行が成功したことを示し、ＮＯＫは、分散ストレージレジスタのコンテンツが不明確であることを示し、また換言すれば、ＷＲＩＴＥは、成功している場合もあるし、成功していない場合もある。
【００７０】
図１９は、複数の他のプロセス及び／又は処理エンティティＰｊ≠ｉと共に分散ストレージレジスタを実施するプロセス又は処理エンティティＰｉによって使用されるコンポーネントを示している。プロセッサ又は処理エンティティは、３つの低レベルプリミティブ、すなわち、タイマメカニズム１９０２、一意のＩＤ１９０４、及び時計１９０６を使用する。プロセッサ又は処理エンティティＰｉは、ローカルタイマメカニズム１９０２を使用する。このローカルタイマメカニズム１９０２によって、Ｐｉは、タイマを指定された期間に設定して、その後、そのタイマが満了するのを待つことが可能になる。Ｐｉは、或るオペレーションを続けるために、タイマの満了時に通知を受ける。プロセスは、タイマを設定して、タイマの満了をチェック又はポーリングしながら、実行を続けることもできるし、タイマを設定して、実行を一時停止し、タイマが満了した時に再び目覚めることもできる。いずれの場合も、タイマによって、プロセスは、オペレーションを論理的に一時停止し、その後、指定された期間後にオペレーションを再開することも可能であり、またタイマが満了するまで、指定された期間の間、或るオペレーションを実行することも可能になる。また、プロセス又は処理エンティティＰｉは、確実に記憶され且つ確実に取り出し可能なローカルプロセスＩＤ（「ＰＩＤ」）１９０４も有する。各プロセッサ又は各処理エンティティは、分散ストレージレジスタを共に実施する他のすべてのプロセス及び／又は処理エンティティに対して一意のローカルＰＩＤを有する。最後に、プロセッサ及び／又は処理エンティティＰｉは、或る絶対時刻にほぼ調整されたリアルタイム時計１９０６を有する。分散ストレージレジスタを共に共同で実施するすべてのプロセス及び／又は処理エンティティのリアルタイム時計は、正確に同期されている必要はないが、絶対時刻の或る共有概念を適度に反映しているべきである。パーソナルコンピュータを含むほとんどのコンピュータは、バッテリーで電力供給を受けるシステム時計を含む。このシステム時計は、現在の世界時の値を反映している。分散ストレージレジスタの実施態様を含めて、ほとんどの目的において、これらのシステム時計は、正確に同期されている必要はないが、現在の世界時をほぼ反映していることだけが必要とされる。
【００７１】
各プロセッサ又は各処理エンティティＰｉは、揮発性メモリ１９０８を含み、いくつかの実施の形態では、不揮発性メモリ１９１０も含む。揮発性メモリ１９０８は、実行用の命令と、分散ストレージレジスタプロトコルに使用される複数の変数のローカル値とを記憶するのに使用される。不揮発性メモリ１９１０は、いくつかの実施の形態では、分散ストレージレジスタプロトコルに使用される変数を永続的に記憶するのに使用される。変数値の永続ストレージによって、クラッシュ又は通信中断後に、プロセスが分散ストレージレジスタの共同実施への関与を再開することが比較的簡単になる。一方、永続ストレージは、クラッシュしたプロセッサ又は一時的に分離されたプロセッサが、分散ストレージレジスタの共同実施への関与を再開することには必要とされない。その代わり、非永続ストレージの実施の形態において、ダイナミックメモリに記憶された変数値が喪失される場合にすべて同時に喪失されるという条件で、且つ、喪失された変数が適切に再初期化されるという条件で、且つ、プロセッサのクォーラムが常に機能的で且つ相互接続された状態にあるという条件で、分散ストレージレジスタプロトコルは、正常に動作し、分散ストレージレジスタを使用するプロセス及び処理エンティティの進行は維持される。各プロセスＰｉは、３つの変数、すなわち、（１）分散ストレージレジスタの現在のローカル値を保有するｖａｌ１９３４、（２）分散ストレージレジスタの現在のローカル値に関連付けられたタイムスタンプ値を示すｖａｌ−ｔｓ１９３６、及び（３）ＷＲＩＴＥオペレーションに関連付けられた最も近時のタイムスタンプを示すｏｒｄ−ｔｓ１９３８を記憶する。変数ｖａｌは、特に非永続ストレージの実施の形態では、値ＮＩＬに初期化される。この値ＮＩＬは、プロセス又は処理エンティティによって分散ストレージレジスタに書き込まれるどの値とも異なる。すなわち、したがって値ＮＩＬは、分散ストレージレジスタの他のすべての値と区別可能である。同様に、変数ｖａｌ−ｔｓ及びｏｒｄ−ｔｓの値は、値「ｉｎｉｔｉａｌＴＳ」に初期化される。この値「ｉｎｉｔｉａｌＴＳ」は、タイムスタンプ値を生成するのに使用されるルーチン「ｎｅｗＴＳ」によって返されるどのタイムスタンプ値よりも小さな値である。ｖａｌ、ｖａｌ−ｔｓ、及びｏｒｄ−ｔｓが、共にこれらの値に再初期化されるという条件で、共同で実施される分散ストレージレジスタは、通信中断並びにプロセス及び処理エンティティのクラッシュに耐性を有する。ただし、プロセス及び処理エンティティの少なくとも過半数が回復して正常なオペレーションを再開することが条件である。
【００７２】
各プロセッサ又は各処理エンティティＰｉは、他のプロセス及び処理エンティティＰｊ≠ｉからメッセージを受信し（１９１２）、他のプロセス及び処理エンティティＰｊ≠ｉへメッセージ送信する（１９１４）ために、メッセージベースのネットワークを介して他のプロセス及び処理エンティティＰｊ≠ｉに相互接続することができる。各プロセッサ又は各処理エンティティＰｉは、ルーチン「ｎｅｗＴＳ」（新しいＴＳ）１９１６を含む。このルーチン「ｎｅｗＴＳ」１９１６は、呼び出された時にタイムスタンプＴＳｉを返し、タイムスタンプＴＳｉは、或る初期値「ｉｎｉｔｉａｌＴＳ」（初期ＴＳ）よりも大きい。ルーチン「ｎｅｗＴＳ」は、呼び出されるたびに、前に返したどのタイムスタンプよりも大きなタイムスタンプＴＳｉを返す。また、プロセッサ又は処理エンティティＰｉによって呼び出されたｎｅｗＴＳが返すどのタイムスタンプ値ＴＳｉも、他のどのプロセッサ又は処理エンティティＰｊによって呼び出されたｎｅｗＴＳが返すどのタイムスタンプ値ＴＳｊとも異なるべきである。ｎｅｗＴＳを実施するための１つの実際的な方法は、ｎｅｗＴＳが、システム時計１９０６によって報告された現在の値とローカルＰＩＤ１９０４を連結したものを含むタイムスタンプＴＳを返すことである。分散ストレージレジスタを実施する各プロセッサ又は各処理エンティティＰｉは、４つの異なるハンドラルーチン、すなわち、（１）ＲＥＡＤハンドラ１９１８、（２）ＯＲＤＥＲ（命令）ハンドラ１９２０、（３）ＷＲＩＴＥハンドラ１９２２、及び（４）ＯＲＤＥＲ＆ＲＥＡＤ（命令＆読み出し）ハンドラ１９２４を含む。ハンドラルーチンは、クリティカルセクション、すなわち、ロックによってシングルスレッド化されたコードセクションを使用して、さまざまなローカルデータ値の試験及び設定における競合状態を防止することが必要な場合があることに留意することは重要である。また、各プロセッサ又は各処理エンティティＰｉは、４つの操作ルーチン、すなわち、（１）ＲＥＡＤ１９２６、（２）ＷＲＩＴＥ１９２８、（３）ＲＥＣＯＶＥＲ（回復）１９３０、及び（４）ＭＡＪＯＲＩＴＹ（過半数）１９３２も有する。４つのハンドラルーチン及び４つの操作ルーチンの双方については、以下で詳述する。
【００７３】
分散ストレージレジスタの正常なオペレーション、並びに、分散ストレージレジスタを使用するプロセス及び処理エンティティの活性、すなわち進行は、複数の前提に依存する。各プロセス又は各処理エンティティＰｉは、悪意をもって振る舞わないことが前提とされる。換言すれば、各プロセッサ又は各処理エンティティＰｉは、分散ストレージレジスタプロトコルを忠実に順守する。もう１つの前提は、分散ストレージレジスタを共同で実施するプロセス及び／又は処理エンティティＰｉの過半数が、決してクラッシュしないか、又は最終的にはクラッシュを停止して確実に実行することである。上述したように、分散ストレージレジスタの実施態様は、メッセージの喪失、通信中断、並びにプロセス及び処理エンティティのクラッシュに対して耐性を有する。プロセス又は処理エンティティのクォーラムを破壊するほど十分ではない個数のプロセス又は処理エンティティがクラッシュ又は分離された場合、分散ストレージレジスタは、正常状態及び活性状態を維持する。十分な個数のプロセス又は処理エンティティが、クラッシュ又は分離されて、プロセス又は処理エンティティのクォーラムが破壊された場合、システムは、正常状態を維持するが、活性状態を維持しない。上述したように、プロセス及び／又は処理エンティティのすべてが、メッセージベースのネットワークによって十分に相互接続されている。このメッセージベースのネットワークは、非同期とすることができ、メッセージ送信回数（message-transmission times）に限界がない。しかしながら、このネットワークのフェアロス（fair-loss）プロパティが前提とされる。このフェアロスプロパティは、基本的に、ＰｉがＰｊからメッセージｍを受信した場合に、Ｐｊがメッセージｍを送信したことを保証し、また、基本的に、ＰｉがメッセージｍをＰｊへ繰り返し送信した場合において、Ｐｊが正常なプロセス又は処理エンティティであるときは、Ｐｊが最終的にメッセージｍを受信することを保証するものである。この場合も、上述したように、すべてのプロセス又は処理エンティティのシステム時計がすべて、或る共有された時刻標準を適度に反映しているが、正確に同期されている必要はないことが前提とされる。
【００７４】
これらの前提は、分散ストレージレジスタプロトコルの正常性を証明し、且つ、進行を保証するのに有益である。しかしながら、或る実際的な実施態様では、これらの前提の１つ又は複数は違反される場合があり、適度に機能的な分散ストレージレジスタが得られる場合がある。加えて、ハードウェアプラットフォーム及び処理エンティティの特定の不備を克服するために、ハンドラルーチン及び操作ルーチン内に安全装置を追加して構築することができる。
【００７５】
分散ストレージレジスタのオペレーションは、クォーラムの概念に基づいている。図２０は、クォーラムによる分散ストレージレジスタの現在の値の求値を示している。図２０は、図１２〜図１８で使用されたものと類似の説明図の規則を使用する。図２０では、プロセス又は処理エンティティ２００２〜２００６のそれぞれは、プロセス又は処理エンティティ２００２によって保持されたローカル変数２００７等のローカル変数ｖａｌ−ｔｓを保持する。このローカル変数ｖａｌ−ｔｓは、分散ストレージレジスタのローカルタイムスタンプ値を保有する。図１６と同様に、共同で分散ストレージレジスタを実施するさまざまなプロセス及び／又は処理エンティティによって保持されるローカル値の過半数が、分散ストレージレジスタに関連付けられたタイムスタンプ値ｖａｌ−ｔｓについて現在一致している場合、分散ストレージレジスタ２００８の現在の値は、プロセス又は処理エンティティの過半数によって保有される変数ｖａｌの値であるとみなされる。プロセス及び処理エンティティの過半数が、タイムスタンプ値ｖａｌ−ｔｓについて一致することができない場合、又は過半数が保有する単一の値が存在しない場合、分散ストレージレジスタのコンテンツは定義されない。一方、その場合に、分散ストレージレジスタを回復させるために、少数派が保有する値を選択して、プロセス及び／又は処理エンティティの過半数により一致させることができる。
【００７６】
図２１は、図１９に概略的に示すルーチンハンドラ及び操作ルーチンの擬似コードの実施態様を示している。これらの擬似コードの実施態様は、詳細なエラーハンドリング、並びに、低レベル通信プリミティブ、ローカルロック、及びコンピュータプログラミングの技術分野の当業者によってよく理解され簡単に実施される他の細部の具体的な詳細を省略していることに留意すべきである。ルーチン「ｍａｊｏｒｉｔｙ」２１０２は、ライン２において、プロセス又は処理エンティティＰｉからＰｉ自身及び他のすべてのプロセス又は処理エンティティＰｊ≠ｉへメッセージを送信する。他のすべてのプロセス又は処理エンティティＰｊ≠ｉは、Ｐｉと共に共同で分散ストレージレジスタを実施するものである。このメッセージは、十分な個数の返答が受信されるまで、周期的に再送信される。多くの実施態様では、このステップに有限時間及び実行制限を設けるために、タイマが設定される。次に、ライン３〜４において、ルーチン「ｍａｊｏｒｉｔｙ」は、メッセージに対する返答が受信されるのを待ち、その後、ライン５において受信された返答を返す。上述した、プロセスの過半数が正常であるという前提によって、タイマが使用されていようといまいと、ルーチン「ｍａｊｏｒｉｔｙ」は最終的には復帰することが基本的に保証される。実際的な実施態様では、タイマによって、ハンドリングエラーの発生がタイミングよく発生することが促進される。プロセスＰｉが受信した返答を前に送信されたメッセージと相関させることができるように、各メッセージは、一般にタイムスタンプまたの他の一意の番号によって一意に特定されることに留意されたい。
【００７７】
ルーチン「ｒｅａｄ」２１０４は、分散ストレージレジスタから値を読み出す。ライン２において、ルーチン「ｒｅａｄ」は、ルーチン「ｍａｊｏｒｉｔｙ」を呼び出して、ＲＥＡＤメッセージをＰｉ自身及び他のプロセス又は処理エンティティＰｊ≠ｉのそれぞれへ送信する。このＲＥＡＤメッセージは、プロセスＰｉによって保有されるローカルな現在の分散ストレージレジスタ値に関連付けられたタイムスタンプ値ｖａｌ−ｔｓだけでなく、当該メッセージがＲＥＡＤメッセージであることの表示も含む。ルーチン「ｍａｊｏｒｉｔｙ」が一組の返答を返し、ライン３で判断されるように、すべてがブール値「ＴＲＵＥ」を含む場合、ルーチン「ｒｅａｄ」は、ローカルな現在の分散ストレージレジスタ値ｖａｌを返す。そうでない場合、ライン４において、ルーチン「ｒｅａｄ」は、ルーチン「ｒｅｃｏｖｅｒ」を呼び出す。
【００７８】
ルーチン「ｒｅｃｏｖｅｒ」２１０６は、クォーラム技法によって分散ストレージレジスタの現在の値を求めようとする。最初に、ライン２において、ルーチン「ｎｅｗＴＳ」を呼び出すことによって、新しいタイムスタンプｔｓが得られる。次に、ライン３において、ルーチン「ｍａｊｏｒｉｔｙ」が呼び出されて、プロセス及び／又は処理エンティティのすべてへＯＲＤＥＲ＆ＲＥＡＤメッセージが送信される。ライン４において、ルーチン「ｍａｊｏｒｉｔｙ」によって返された返答のいずれかのステータスが「ＦＡＬＳＥ」である場合、「ｒｅｃｏｖｅｒ」は値ＮＩＬを返す。そうでない場合、ライン５において、分散ストレージレジスタのローカルな現在の値ｖａｌは、ルーチン「ｍａｊｏｒｉｔｙ」によって返された一組の返答における最も高い値のタイムスタンプに関連付けられた値に設定される。次に、ライン６において、ルーチン「ｍａｊｏｒｉｔｙ」が再び呼び出されて、ＷＲＩＴＥメッセージが送信される。このＷＲＩＴＥメッセージは、ライン２で得られた新しいタイムスタンプｔｓと、分散ストレージレジスタの新しいローカルな現在の値ｖａｌとを含む。すべての返答のステータスがブール値「ＴＲＵＥ」を有する場合、ＷＲＩＴＥオペレーションは成功し、プロセス及び／又は処理エンティティの過半数は、現在、ライン５においてローカルコピーに記憶されたその新しい値ｖａｌと一致する。そうでない場合、ルーチン「ｒｅｃｏｖｅｒ」は、値ＮＩＬを返す。
【００７９】
ルーチン「ｗｒｉｔｅ」２１０８は、分散ストレージレジスタに新しい値を書き込む。新しいタイムスタンプｔｓがライン２において得られる。ルーチン「ｍａｊｏｒｉｔｙ」が、ライン３において呼び出され、新しいタイムスタンプを含むＯＲＤＥＲメッセージをプロセス及び／又は処理エンティティのすべてへ送信する。ルーチン「ｍａｊｏｒｉｔｙ」によって返された返答メッセージで返されるステータス値のいずれかが「ＦＡＬＳＥ」である場合、ライン４において、値「ＮＯＫ」が、ルーチン「ｗｒｉｔｅ」によって返される。そうでない場合、ライン５において、ルーチン「ｍａｊｏｒｉｔｙ」を介してＷＲＩＴＥメッセージを送信することにより、値ｖａｌが、他のプロセス及び／又は処理エンティティに書き込まれる。ルーチン「ｍａｊｏｒｉｔｙ」によって返された返答のすべてのステータス値が「ＴＲＵＥ」であるとライン６で判断された場合、ルーチン「ｗｒｉｔｅ」は値「ＯＫ」を返す。そうでない場合、ライン７において、ルーチン「ｗｒｉｔｅ」は値「ＮＯＫ」を返す。ルーチン「ｒｅｃｏｖｅｒ」２１０６及びルーチン「ｗｒｉｔｅ」の双方の場合において、分散ストレージレジスタ値ｖａｌのローカルコピー及びタイムスタンプ値ｖａｌ−ｔｓのローカルコピーは、共に、後述するローカルハンドラルーチンによって更新されることに留意されたい。
【００８０】
次に、ハンドラルーチンを解説する。手始めに、ハンドラルーチンは、受信された値をローカル変数値と比較し、次に、比較の結果に従ってローカル変数値を設定することに留意すべきである。これらのタイプのオペレーションは、厳密に直列化され、複数の値を記憶するデータ構造体について、各プロセス及び／又は各処理エンティティ内での競合状態から保護されることが必要な場合がある。ローカルな直列化は、不可分なテスト・アンド・セット命令に基づくクリティカルセクション又はローカルロックを使用して容易に行われる。ＲＥＡＤハンドラルーチン２１１０は、ＲＥＡＤメッセージを受信し、このＲＥＡＤメッセージに対してｓｔａｔｕｓ（ステータス）値で返答する。このｓｔａｔｕｓ値は、受信プロセス又は受信エンティティにおけるタイムスタンプｖａｌ−ｔｓのローカルコピーが、ＲＥＡＤメッセージで受信されたタイムスタンプと等しいか否かと、ＲＥＡＤメッセージで受信されたタイムスタンプｔｓが、ローカル変数ｏｒｄ−ｔｓの現在の値以上であるか否かとを示している。ＷＲＩＴＥハンドラルーチン２１１２は、ライン２において、ＷＲＩＴＥメッセージを受信し、ローカル変数ｓｔａｔｕｓの値を求める。このローカル変数ｓｔａｔｕｓは、受信プロセス又は受信エンティティにおけるタイムスタンプｖａｌ−ｔｓのローカルコピーが、ＷＲＩＴＥメッセージで受信されたタイムスタンプよりも大きいか否かと、ＷＲＩＴＥメッセージで受信されたタイムスタンプｔｓが、ローカル変数ｏｒｄ−ｔｓの現在の値以上であるか否かとを示している。ｓｔａｔｕｓローカル変数の値が「ＴＲＵＥ」であるとライン３で判断された場合、ＷＲＩＴＥハンドラルーチンは、ライン４〜５において、ダイナミックメモリ及び永続メモリの双方にローカルに記憶された値ｖａｌ及びタイムスタンプｖａｌ−ｔｓを、ＷＲＩＴＥメッセージで受信された値及びタイムスタンプで更新する。最後に、ライン６において、ローカル変数ｓｔａｔｕｓに保有された値は、ＷＲＩＴＥハンドラルーチン２１１２によってハンドリングされたＷＲＩＴＥメッセージを送信したプロセス又は処理エンティティに返される。
【００８１】
ＯＲＤＥＲ＆ＲＥＡＤハンドラ２１１４は、ライン２において、ローカル変数ｓｔａｔｕｓの値を計算し、その値を、受信されたＯＲＤＥＲ＆ＲＥＡＤメッセージの送信元のプロセス又は処理エンティティへ返す。ｓｔａｔｕｓの計算値は、ＯＲＤＥＲ＆ＲＥＡＤメッセージで受信されたタイムスタンプが、ローカル変数ｖａｌ−ｔｓに記憶された値及びローカル変数ｏｒｄ−ｔｓに記憶された値の双方よりも大きいか否かを示すブール値である。ｓｔａｔｕｓの計算値が「ＴＲＵＥ」である場合、受信されたタイムスタンプｔｓは、ダイナミックメモリ及び永続メモリの双方の変数ｏｒｄ−ｔｓに記憶される。
【００８２】
同様に、ＯＲＤＥＲハンドラ２１１６は、ライン２において、ローカル変数ｓｔａｔｕｓの値を計算し、そのステータスを、受信されたＯＲＤＥＲメッセージの送信元のプロセス又は処理エンティティへ返す。このステータスは、受信されたタイムスタンプが、ローカル変数ｖａｌ−ｔｓ及びｏｒｄ−ｔｓに保有された値よりも大きいか否かを反映している。ｓｔａｔｕｓの計算値が「ＴＲＵＥ」である場合、受信されたタイムスタンプｔｓは、ダイナミックメモリ及び永続メモリの双方の変数ｏｒｄ−ｔｓに記憶される。
【００８３】
上述した分散ストレージレジスタ方法及びプロトコルを使用すると、分散データストレージシステムに絶えず一貫して保持される共有状態情報を、一組の分散ストレージレジスタに記憶することができる。記憶は、１つのレジスタにつき１ユニットの共有状態情報で行われる。レジスタのサイズは、共有状態情報のユニットの異なる自然のサイズに適合するように変化することができる。状態情報ユニットの粒度は、パーフォーマンスモニタリングによるか、又は特定の分散システム内の状態情報のユニットの予想交換率の解析によって決定することができる。ユニットが大きいほど、プロトコル変数及び分散ストレージレジスタ用に保持された他のデータの被るオーバーヘッドは小さくなるが、ユニットの異なる部分が異なる時刻にアクセスされる場合、通信オーバーヘッドが増加する場合がある。また、上記擬似コード及び説明図は、単一の分散ストレージレジスタの実施態様を対象にしているが、これらの擬似コードルーチンは一般化できることにも留意すべきである。この一般化は、特定の分散ストレージレジスタを特定する、状態情報のユニットのパラメータであって、オペレーションが向けられたパラメータを追加すること、及びこの特定するパラメータによってインデックスされるｖａｌ−ｔｓ、ｖａｌ、ｏｒｄ−ｔｓ等の変数のアレイを保持することによって行われる。
【００８４】
［一般化されたストレージレジスタモデル］
ストレージレジスタモデルは一般に、ミラーリング冗長性方式に従って分散されたセグメントにわたって一貫性を維持するために、ＦＡＢシステムによってブロックレベルで適用される。換言すれば、セグメントの各ブロックは、複数のブリックにわたって分散されたストレージレジスタであるとみなすことができ、クォーラム及びメッセージパッシングを伴う上記分散技法は、ミラーコピーにわたってデータ一貫性を維持するのに使用される。一方、ストレージレジスタ方式は、イレージャ符号化冗長性方式をハンドリングするように拡張することができる。第１に、上記節で説明し、ミラーリング冗長性方式に使用されるように、ブロックが分散されたブリックの過半数から成るクォーラムではなく、イレージャ符号化冗長性方式は、ｍ＋［（ｎ−ｍ）／２］個のブリックのクォーラムを使用し、任意の２つのクォーラムの交わりが、少なくともｍ個のブリックを含むようにする。このタイプのクォーラムは、「ｍ−クォーラム」と呼ばれる。第２に、新しく受信された値を、ＷＲＩＴＥオペレーションの第２のフェーズで、内部ストレージのブロックに書き込むのではなく、ブリックはその代わりに、その新しい値をその値に関連付けられたタイムスタンプと共にログに記録することができる。ログは、その後、ログに記録されたエントリーのｍ−クォーラムが受信されてログに記録された時に、非同期に処理されて、ログに記録されたＷＲＩＴＥをコミットすることができる。ログ記録が使用される理由は、ブリックのｍ−クォーラムが特定のＷＲＩＴＥオペレーションを受信せず、正常の実行していなかった場合に、ミラーリング冗長性方式と異なって、ブリックのクラッシュによりデータを回復させることができないからである。図２２は、図１７に提供した擬似コードに類似した修正擬似コードを示している。この修正擬似コードは、本発明の一実施の形態を表す、ＦＡＢシステム内におけるイレージャ符号化冗長性方式に従ってブリックにわたるセグメントの分散をハンドリングする、ストレージレジスタモデルへの拡張を含む。たとえば、ｍ個のブリックが、最も近時に書き込まれた値をログに記憶できなかった場合、その最も近時に書き込まれた値は、ログ内の少なくともｍ個のコピーに存在する前の値又は少なくともｍ個のブリック内に記憶された前の値にロールバックされる。
【００８５】
図２３は、本発明の一実施の形態を表す、ＦＡＢシステム内におけるストレージレジスタモデルに基づいたデータ一貫性技法によるタイムスタンプに対する大きな依存関係を示している。図２３では、ブロック２３０２は、トリプルミラーリング冗長性方式に従って３つのブリック２３０４〜２３０６にわたって分散され、且つ、３＋２イレージャ符号化方式に従って５つのブリック２３０８〜２３１２にわたって分散されて示されている。トリプルミラーリング冗長性方式では、ブロック２３１４等のブロックの各コピーは、前の小節で解説したように、２つのタイムスタンプ２３１６及び２３１７に関連付けられる。イレージャ符号化冗長性方式では、最初のブロック２３１８等の各ブロックは、少なくとも２つのタイムスタンプに関連付けられる。ブロック２３２０及び２３２１と、ブロックのストライプにおける他のブロックとから計算されたチェックサムビットは、２つのタイムスタンプに関連付けられるが、ブロック２３２４等のブロックは、これに加えて、ログエントリー２３２６等の（以下に図示され、且つ、ブロックによって重ねられた）ログエントリーにも関連付けることができる。ログエントリーのそれぞれも、タイムスタンプ２３２８等のタイムスタンプに関連付けられる。明らかに、ストレージレジスタモデルに基づくデータ一貫性技法は、非常の多くのタイムスタンプの記憶及び保持を伴う可能性があり、タイムスタンプに充てられた全ストレージ空間は、ＦＡＢシステム内の全体の利用可能なストレージ空間のかなりの割合となるおそれがある。その上、ストレージレジスタに向けられた上述したＲＥＡＤオペレーション及びＷＲＩＴＥオペレーションの期間中にブリック間でタイムスタンプを渡すことに起因して、メッセージトラフィックのオーバーヘッドが発生するおそれがある。
【００８６】
タイムスタンプに関係する膨大なオーバーヘッドが潜在することから、ＦＡＢシステムは、複数の技法を使用して、タイムスタンプに関係する記憶オーバーヘッド及びメッセージングオーバーヘッドを改善することができる。第１に、単一のＷＲＩＴＥオペレーションで書き込まれた多数の連続したブロックに単一のタイムスタンプを関連付けることができるように、ブリックは、タイムスタンプを不揮発性ランダムアクセスメモリに階層的に記憶することができる。図２４は、本発明の一実施の形態を表す階層的なタイムスタンプ管理を示している。図２４では、タイムスタンプは、「区間木」として知られている大きな一種の非循環グラフのリーフノードに関連付けられている。非循環グラフの小さな部分のみが図２４に示されている。グラフの表示部分では、２つのリーフノード２４０２及び２４０４が、ブロック１０００〜１０５０及び１０５１〜２０００にそれぞれ関連付けられたタイムスタンプを表している。その後のＷＲＩＴＥオペレーションにおいて、ＷＲＩＴＥがブロック１０５１〜１０９９に向けられている場合、元の非循環グラフのリーフノード２４０４は、２つの下位レベルブロック２４０６及び２４０８に分割されて、修正非循環グラフになる。個別のタイムスタンプをそれら新しいリーフノードブロックのそれぞれに関連付けることができる。逆に、ブロック１０５１〜２０００が、その後、単一のＷＲＩＴＥオペレーションで書き込まれた場合、２つのブロック２４０６及び２４０８は、その後、合体されて、この非循環グラフは元の非循環グラフ２４００に戻される。単一のＷＲＩＴＥオペレーションで書き込まれるブロックグループにタイムスタンプを関連付けることによって、ブリックにより保持されるタイムスタンプの個数を大幅に減少させることができる。
【００８７】
ブリックによって保持されるタイムスタンプの個数を減少させる別の方法は、タイムスタンプを積極的にガベージコレクトすることである。前の小節で解説したように、タイムスタンプをブロックに関連付けて、ストレージレジスタモデルのクォーラムベースの一貫性方法を容易にすることができる。しかしながら、ブロックが分散されるすべてのブリックの更新が成功した場合、それらのブロックは、完全に一貫性のある状態にあり、且つ、十分冗長に記憶された状態にあるので、それらのブロックに関連付けられたタイムスタンプはもはや必要とされない。したがって、ＦＡＢシステムは、ストレージレジスタモデルをさらに拡張して、ＷＲＩＴＥオペレーションの全完了の後に、タイムスタンプの積極的なガベージコレクションを含めることができる。ＦＡＢシステムが、タイムスタンプに関係するオーバーヘッドを減少させるのに使用するさらに別の方法には、他のメッセージ内におけるタイムスタンプに関係するメッセージをピギーバックすること、及び、後述する階層的降格を含めて、結合された処理タスクにおいて、関係するタイムスタンプを同時に処理することが含まれ得る。
【００８８】
クォーラムベースのストレージレジスタモデルは、前の小節で上述した再構成及びマイグレーションをハンドリングするようにさらに拡張することができる。クォーラムベースのストレージレジスタモデルでは、レイアウト及び冗長性方式が変更される。その小節で解説したように、再構成オペレーションの期間中、前の構成の削除及びガベージコレクションの前に、新しい構成が前に存在する構成と同期されている間、２つ以上の異なる構成を同時に保持することができる。ＷＲＩＴＥオペレーションは、同期プロセスの期間中、双方の構成に向けられる。したがって、ｃｆｇグループ又はＳＣＮレベルの制御ロジックが、受信されたＷＲＩＴＥオペレーションの完了が成功したとみなす前に、構成の上位レベルのクォーラムは、ＷＲＩＴＥオペレーションの完了に成功している必要がある。図２５及び図２６は、さらに拡張されたストレージレジスタモデルの擬似コードを提供する。このさらに拡張されたストレージレジスタモデルは、本発明の一実施の形態を表す、ＦＡＢシステム内における分散されたセグメントの再構成に起因して存在し得る複数のアクティブな構成に対するクォーラムベースの書き込みの概念を含む。
【００８９】
あいにく、マイグレーションは、ストレージレジスタモデルにさらなる拡張を必要とする場合があるさらに別のレベルの再構成である。前述した再構成のシナリオのように、マイグレーションは、新しい構成を古い構成と同期させている間、ＳＣＮ−レベルの制御ロジックがＷＲＩＴＥオペレーションを向ける複数のアクティブな構成を伴う。しかしながら、再構成レベルと異なり、マイグレーションレベルは、アクティブな構成に向けられたＷＲＩＴＥがアクティブな構成のクォーラムではなくすべての構成において成功して完了することを必要とする。その理由は、冗長性方式がアクティブな構成によって異なり、或る冗長性方式で失敗したＷＲＩＴＥは、異なる冗長性方式を使用する異なるアクティブな構成から回復可能でない場合があるからである。したがって、マイグレーションレベルでは、アクティブな構成のクォーラムは、アクティブな構成のすべてから成る。したがって、ストレージレジスタモデルをマイグレーションレベルに拡張することによって、より一般的なストレージレジスタのようなモデルが得られる。図２７は、本発明の一実施の形態を表す、ＦＡＢシステム内でストレージレジスタモデルをマイグレーションレベルへ拡張するための高レベルの擬似コードを示している。さらに異なる考慮すべき事項が、複製レベルで適用される場合がある。複製レベルでは、ＷＲＩＴＥは、仮想ディスクの複数の複製に向けられる。しかしながら、ＶＤＩレベルの考慮すべき事項が一般的なストレージレジスタモデルに組み込まれる場合、図２７に関して上述した最も一般的なストレージレジスタモデルの拡張は、ＶＤＩレベル及び仮想ディスクレベルの適用について十分一般的である。
【００９０】
上述したストレージレジスタモデルの拡張及び考慮すべき事項の結果、ＦＡＢシステム内の階層的な制御ロジック及び階層的なデータストレージの最終的な高レベルの記述が得られる。図２８は、本発明の一実施の形態を表す、ＦＡＢシステム内の制御処理及びデータストレージの双方の全階層構造を示している。「最上位レベルコーディネータ」２８０２と呼ばれる最上位レベルコーディネータロジックは、階層的データストレージモデルの仮想ディスクレベル２８０４に関連付けることができる。「ＶＤＩレベルコーディネータ」２８０６と呼ばれるＶＤＩレベル制御ロジックは、データストレージモデルのＶＤＩレベル２８０８に関連付けることができる。「ＳＣＮコーディネータ」２８１０と呼ばれるＳＣＮレベル制御ロジックは、データストレージモデルのＳＣＮレベル２８１２に関連付けることができる。「構成グループコーディネータ」２８１４と呼ばれる構成グループレベル制御ロジックは、データストレージモデルの構成グループレベル２８１６に関連付けることができる。最後に、「構成コーディネータ」２８１８と呼ばれる構成レベル制御ロジックは、データストレージモデルの構成レベル２８２０に関連付けることができる。図２８及び図２８で使用される説明図の規則を使用するその後の図では、ｃｆｇデータ構造体要素及びレイアウトデータ構造体要素が、互いに結合されて、１つのデータストレージモデルノードにされることに留意されたい。コーディネータの階層編成におけるコーディネータのそれぞれは、コーディネータの階層レベルに適した拡張されたストレージレジスタモデル一貫性方法を実行する。たとえば、ｃｆｇグループコーディネータは、ミラーリング冗長性方式についてはクォーラムベースの技法を使用し、イレージャ符号化冗長性方式についてはｍ−クォーラムベース技法を使用する。これとは対照的に、ＳＣＮコーディネータは、ＷＲＩＴＥオペレーションが成功しているとみなされるように、参照されるすべての構成グループによるＷＲＩＴＥオペレーションの完了を必要とする拡張されたストレージレジスタモデルを使用する。
【００９１】
［タイムスタンプ問題］
前の小節で解説したデータストレージモデルの階層的な制御処理は、現在想定されるデータストレージモデル及びオペレーションと、今後のＦＡＢシステムアーキテクチャに追加できる追加データストレージモデル及び追加オペレーションとをサポートするための論理的な拡張可能モデルを提供するが、タイムスタンプに関する重大な問題が残っている。このタイムスタンプ問題は、具体例を参照することで最も良く解説される。図２９Ａ〜図２９Ｃは、特定のセグメントを分散するための、４＋２イレージャ符号化冗長性方式から８＋２イレージャ符号化冗長性方式へのマイグレーションの状況におけるタイムスタンプ問題を示している。図２９Ａは、前の４＋２冗長性方式及び新しい８＋２イレージャ符号化冗長性方式のセグメントのレイアウトを示している。図２９Ａでは、セグメント２９０２は、連続した一連の８つのブロック２９０４〜２９１１として示されている。４＋２冗長性方式のレイアウト２９１２は、これら８つのブロックをブリック２、３、６、９、１０、及び１１にわたって２つのストライプで分散させる。８＋２冗長性方式のレイアウト２９１４は、これら８つのブロックをブリック１、４、６、８、９、１５、１６、１７、１８、及び２０にわたって単一のストライプで分散させる。双方のレイアウトは、ブリック６及び９を使用するので、ブリック６及び９は、古い構成及び新しい構成の双方のブロックを含む。４＋２構成では、チェックサムブロックが、ブリック１０及び１１にわたって分散される（２９１６）。８＋２構成では、チェックサムブロックが、ブリック１８及び２０にわたって分散される（２９１８）。図２９Ａでは、セグメント２９０４〜２９１１のブロックとブリック内のストライプとの間のマッピングは、両頭矢印２９２０等の両頭矢印によって示されている。
【００９２】
図２９Ａに矢印２９２２によって示すセグメントの最終ブロック２９１１のＷＲＩＴＥを考える。イレージャ符号化冗長性方式のレイアウトでは、ブロックが書き込まれるストライプのすべてのブロックは、ＷＲＩＴＥオペレーションの新しいタイムスタンプに関連付けられる。その理由は、どのブロックへの書き込みも、そのストライプのすべてのブロックのパリティビットに影響を与えるからである。したがって、図２９Ｂに示すように、セグメントの最後のブロック２９１１への書き込みによって、４＋２レイアウトの第２のストライプ２９２４〜２９２７のすべてのブロックが、ＷＲＩＴＥオペレーションに対応する新しいタイムスタンプに関連付けられる。一方、８＋２レイアウトでは、単一のストライプ内のすべてのブロックが、新しいタイムスタンプ２９２８〜２９３５に関連付けられる。図２９Ｂでは、新しいタイムスタンプに関連付けられたブロックが暗くされている。次に、図２９Ｃに示すように、セグメントの最初のブロック２９０４のＲＥＡＤを考える。４＋２レイアウト２９１２から読み出す時、最初のブロックは、ブロック２９３６で陰影を付けていないことによって示すように、古いタイムスタンプに関連付けられる。一方、８＋２レイアウト２９１４から読み出す時、最初のブロックは、最初のブロックの陰影によって示すように、新しいタイムスタンプ２９３８に関連付けられる。したがって、読み出されたブロック及びタイムスタンプを受け取る制御ロジックは、セグメントの最初のブロックに関してタイムスタンプの不一致があるものと結論付けることができ、したがって、ブロックのコピーが一貫性を有しないと結論付けることができる。セグメントについての２つの同時に存在する異なった冗長性方式を管理する２つの異なるｃｇｒｐｓによってタイムスタンプの相違がＳＣＮコーディネータに報告されたことにより、たとえば、ＳＣＮコーディネータは、ＲＥＡＤを失敗する場合があり、回復ステップに着手する場合がある。つまり、データ矛盾は存在せず、タイムスタンプの相違は、ＳＣＮコーディネータの下の構成コーディネータレベルで管理される２つの異なる冗長性方式の異なったタイムスタンプ割り当ての振る舞いからのみ生じる。図２９Ａ〜図２９Ｃに示すタイムスタンプ問題は、図２８に示す階層的なコーディネータ及びデータストレージモデルに発生し得る多くの異なるタイムスタンプに関係する問題のほんの一例にすぎない。
【００９３】
［タイムスタンプ問題に対する階層的なタイムスタンプ解決法］
前の小節で扱ったタイムスタンプ問題を解決するためのさまざまな異なる解決法を提案することができるが、提案された解決法の多くは、オーバーヘッド及び非効率性をさらに導入し、ストレージレジスタモデルの多くの具体的且つ拡張不能な変更を必要とする。本発明の一実施の形態は、比較的簡単且つ拡張可能な方法である。この方法は、新しいタイプのタイムスタンプを使用し、階層処理レベルがタイムスタンプに関連付けられたオペレーションを完了するにつれてタイムスタンプの範囲を段階的に収縮することにより、異なる階層処理レベルを互いに分離するものである。タイムスタンプの範囲は、この実施の形態では、タイムスタンプが活性であるみなされる処理レベルの範囲である。一実施の形態では、タイムスタンプの範囲は、トップダウン形式に制約され、タイムスタンプの範囲は、下位の処理レベルに向かうにつれて連続的に縮小されている。ただし、異なる実施の形態は、タイムスタンプの範囲を異なって収縮させることができる。本質的に、本発明のこの実施の形態は、図２８に示す階層的な処理及びデータストレージモデルに直接マッピングされる新しいタイプのタイムスタンプを対象としている。
【００９４】
図３０は、本発明の一実施の形態を表す新しいタイプのタイムスタンプの１つを示している。タイムスタンプ３０００は、一般に、データ構造体、データ構造体ノード、及びデータエンティティに関連してブリック内の不揮発性ランダムアクセスメモリに記憶され、且つ、ブリックとプロセスとの間をメッセージで通信されるデータ構造体である。図３０に示す新しいタイプのタイムスタンプ３０００の一例は、フィールド３００２、フィールド３００４、レベルフィールド３００６、及びオプションとして追加フィールド３００８を含むことができる。フィールド３００２は、データブロック又はログエントリー等、タイムスタンプが関連付けられているエンティティを説明、すなわち参照するものである。フィールド３００４は、第１のフィールド３００２で説明すなわち参照されるエンティティにタイムスタンプが関連付けているリアルタイム時刻値、論理時刻値、又はシーケンス値を含むものである。レベルフィールド３００６は、タイムスタンプが活性であるとみなされる、図２８に示す処理及びデータストレージ階層内の最も高いレベルを示すものである。追加フィールド３００８は、高速ガベージコレクション及び他の目的を含むさまざまな目的で使用されるものである。タイムスタンプは、さまざまな異なるシステムでは、多種多様な異なるエンティティに関連付けることができる。これら多種多様な異なるエンティティには、メモリ、マスストレージデバイス、又は別の形式で記憶されるデータ構造体、プロセス、ポート、物理デバイス、メッセージ、及び、ソフトウェアルーチンが参照、操作、又は管理できる他のほぼあらゆる物理エンティティ又は計算エンティティが含まれる。
【００９５】
レベルフィールド及び新しいタイプのタイムスタンプの使用のセマンティクスは、具体例を参照することで最もよく説明される。図３１Ａ〜図３１Ｆは、複数の冗長性方式の下で複数のブリック上に分散されたＦＡＢセグメントへのＷＲＩＴＥオペレーション中のデータ一貫性を容易にするための、本発明の一実施の形態を表す新しいタイプのタイムスタンプの使用を示している。図３１Ａ〜図３１Ｆはすべて、図２８に関して上述した図２８で使用されたものと同じ説明図の規則を使用する。ＦＡＢシステム内の特定の仮想ディスク３１０４に向けられたＷＲＩＴＥオペレーション３１０２を考える。最上位レベルコーディネータは、ＷＲＩＴＥ要求を仮想ディスクの２つのＶＤＩ複製３１０６及び３１０７に向ける。次に、ＶＤＩコーディネータは、ＷＲＩＴＥ要求を、ＷＲＩＴＥ要求が向けられたセグメントに対応する２つの異なるＳＣＮノード３１０８及び３１０９に向ける。マイグレーションは、第１のＳＣＮノード３１０８に対して行われている。したがって、ＳＣＮコーディネータは、ＷＲＩＴＥ要求を２つの異なるｃｆｇグループ３１１０及び３１１２に向ける。第１のｃｆｇグループは、トリプルミラー冗長性を表し、第２のｃｆｇグループ３１１２は、ＲＡＩＤ−６イレージャ符号化冗長性方式を表している。これら２つのｃｆｇグループ３１１０及び３１１２は、次に、ＷＲＩＴＥ要求を対応する構成３１１４及び３１１６にそれぞれ向ける。第２のＳＣＮノード３１０９は、ＷＲＩＴＥ要求を単一の構成グループ３１１８に向ける。構成グループ３１１８は、次に、ＷＲＩＴＥ要求を、関連付けられた構成３１２０に向ける。ＷＲＩＴＥが、第１のＳＣＮノード３１０８のトリプルミラーリングｃｆｇグループ３１１０に関連付けられた構成３１１４のブリック「ｃ」３１２２に対して失敗するものと仮定する。関連がある構成グループ内のブリックに対する他のすべてのＷＲＩＴＥオペレーションは成功する。したがって、図３１Ｂに示すように、関連がある構成３１１４、３１１６、及び３１２０内のブリックのすべてにおける、ＷＲＩＴＥ要求により影響を受けるブロックのすべてが、新しいタイムスタンプに関連付けられる一方、ブリック「ｃ」のブロックは、古いタイムスタンプに関連付けられる。新しいタイムスタンプは、図３１Ｂにも示すように、階層の最上位レベルを示すレベルフィールド値を有する。これは、タイムスタンプが、制御処理及びデータストレージモデルのすべての階層レベルに関して活性であることを意味する。
【００９６】
次に、図３１Ｃに示すように、さまざまな階層レベルが、階層モデルの上方に向かってＷＲＩＴＥオペレーションに対する返答を行っている。たとえば、構成コーディネータレベルでは、構成３１１４は、ブリック「ｃ」に対するＷＲＩＴＥが有効でなかったことの表示を構成グループノード３１１０に返すと共に、ブリック「ａ」及び「ｂ」に対するＷＲＩＴＥの成功の表示も返す。構成３１１６は、その構成の５つすべてのブリックのＷＲＩＴＥオペレーションの成功の表示を返す。同様に、構成３１２０は、構成３１２０の５つすべてのブリックに対するすべてのＷＲＩＴＥオペレーションの成功の表示を返す。成功表示は、最上位レベルコーディネータまでずっと処理階層の上へレベルごとに返される。構成グループノード３１１０は、ブリック「ｃ」に対するＷＲＩＴＥの失敗にもかかわらず、成功の表示を返すことに留意されたい。その理由は、トリプルミラーリング冗長性方式の下では、ブリック「ａ」及び「ｂ」に対するＷＲＩＴＥの成功が、それらブリックのクォーラムに対するＷＲＩＴＥの成功を構成するからである。
【００９７】
成功の表示を返すことに続いて、階層的なコーディネータレベルは、最上位レベルコーディネータから下流へ、ＷＲＩＴＥオペレーションに関連付けられたタイムスタンプのレベルフィールドを、それらタイムスタンプよりも下のレベルに対応するレベルフィールド値に降格させる。換言すれば、最上位レベルコーディネータは、ＷＲＩＴＥオペレーションによって影響を受けるブリックに関連付けられたタイムスタンプのレベルフィールドを、ＶＤＩコーディネータレベルの表示に降格させ、ＶＤＩコーディネータレベルは、タイムスタンプのレベルフィールドの値をＳＣＮコーディネータレベルの表示に降格させる。以下、同様に降格が行われる。その結果、ＷＲＩＴＥオペレーションに関連付けられたすべてのタイムスタンプのレベルフィールドは、図３１Ｄに示すように、構成コーディネータレベルの表示に降格される。ブリック「ｃ」に対するＷＲＩＴＥの失敗により、タイムスタンプは構成コーディネータレベルでは活性状態に維持される。これらのタイムスタンプは、失敗したＷＲＩＴＥが解決されて、ＷＲＩＴＥオペレーションの成功完了が得られるまで活性状態に維持される。一方、構成コーディネータレベルよりも上のすべてのコーディネータレベルは、タイムスタンプがすでにガベージコレクトされているとみなす。
【００９８】
図３１Ｅに示すように、構成グループコーディネータは、故障したブリックを含む構成３１１４を再構成することによって、失敗したＷＲＩＴＥを解決する。したがって、構成グループ３１１０は、古い構成３１１４と、古い構成における故障したブリック「ｃ」の代わりに新しいブリック「ｐ」を使用する新しい構成３１２４との双方を参照する。再構成の一部として、ブロックは、古い構成３１１４から新しい構成３１２４へコピーされる。図３１Ａ〜図３１Ｆに示す例では、コピーされたブロックは、新しい構成では、新しいタイムスタンプ値を有する新しいタイムスタンプを受け取る。或る場合に、再同期（resync）ルーチンがデータを再構築して、既存のタイムスタンプを保存することができる一方、現在の例のようなそれ以外の場合には、新しいタイムスタンプが生成される。したがって、前述したＷＲＩＴＥオペレーションで書き込まれたブロックは、古い構成の或るタイムスタンプ値と、新しい構成のより新しいタイムスタンプ値とに関連付けられる。したがって、タイムスタンプの相違は、新しい構成のブロック及び残りの構成の他のすべてのブロックに関して存在する。
【００９９】
しかしながら、タイムスタンプの相違は、構成コーディネータレベルよりも上の制御処理階層内では見ることができない。その理由は、タイムスタンプの階層的な性質のために、古い構成３１１４のタイムスタンプは構成コーディネータレベルに降格されているからであり、また、新しい構成３１２４の新しいタイムスタンプは、構成コーディネータによって作成されたので、当初、構成コーディネータレベルに設定されていたからである。したがって、構成グループコーディネータも、構成グループコーディネータよりも上のどのコーディネータも、タイムスタンプの相違に気づかない。現在の制御処理階層よりも下のレベルを有するタイムスタンプは、その処理レベルによってガベージコレクトされるとみなされる。したがって、構成グループコーディネータ及びそれよりも高いすべてのコーディネータの観点からすると、ブロックに関連付けられたタイムスタンプは、ＷＲＩＴＥオペレーションが構成グループコーディネータ及びそれよりも高いレベルのすべてのコーディネータの観点から成功した結果として、すでにガベージコレクトされている。図３１Ｆに示すように、構成グループノード３１１０の再構成が一旦完了すると、古い構成（図３１Ｅの３１１４）は、消去されてガベージコレクトされ、単一の新しい構成３１２４のみが残される。その時点で、ブロック「ｃ」に対するＷＲＩＴＥの失敗は解決されており、したがって、構成コーディネータは、そのＷＲＩＴＥオペレーションによって影響を受けるブロックに関連付けられたすべてのタイムスタンプのレベルフィールドのレベル表示を降格させる。構成コーディネータレベルにおける降格は、タイムスタンプがどの処理レベルにおいてももはや活性ではなく、ガベージコレクションメカニズムによって物理的にガベージコレクトできることを意味する。
【０１００】
要約すれば、本発明の一実施の形態を表す新しい階層的なタイムスタンプは、タイムスタンプが活性であるとみなされる、処理階層内における最も高いレベルを示すレベルフィールドを含むことができる。そのレベルよりも上のコーディネータは、タイムスタンプがすでにガベージコレクトされているとみなし、したがって、タイムスタンプは、そのレベルよりも上のコーディネータによって、タイムスタンプの相違に関係するエラー検出に関して考慮されない。したがって、図２９Ａ〜図２９Ｃに関して説明したタイムスタンプの相違等、データの矛盾を表すものではないタイムスタンプの相違は、そのタイムスタンプの相違がデータ矛盾を表すものではないことを認識するのに十分な知識を有する処理レベルへ自動的に分離され、その結果、それよりも高いレベルの制御ロジックは、データ矛盾が存在せず、他のエラーが存在する場合に、不注意に故障を推論することはなく、また、回復オペレーションを起動することがない。処理レベルフィールドを階層的なタイムスタンプ内に含めることによって、データに関係する処理タスク又はタイムスタンプに関連付けられた他の計算エンティティの処理レベルと、処理が完了した処理レベルとの間の望ましくない依存関係を防止することができる。また、階層的なタイムスタンプによって、階層的処理段階を通じたタイムスタンプの段階的なガベージコレクションも容易になる。
【０１０１】
タイムスタンプのガベージコレクションは、階層の最上位処理レベルでは非同期に実行することができる。図３２は、本発明の一実施の形態を表す、非同期タイムスタンプコレクションプロセスの擬似コードを示している。この擬似コードルーチンは、ローカル宣言された３つの変数ｌｅｖｅｌ、ｉ、及びｔｓを使用する。これらの変数はライン３〜５で宣言されている。タイムスタンプガベージコレクションルーチンには、タイムスタンプクラスｔｉｍｅｓｔａｍｐｓのインスタンスが渡される。階層的な処理レベルが、タイムスタンプに関連したオペレーション及びタスクを完了すると、タイムスタンプを降格させて最終的にガベージコレクトするために、タイムスタンプガベージコレクションルーチンは、ライン６〜２０のｄｏ−ｗｈｉｌｅループを絶えず実行する。ライン８〜１９のｆｏｒループでは、タイムスタンプガベージコレクションルーチンは、最上位レベルから下に向かって各処理レベルを検討する。ライン１０〜１８のｆｏｒループでは、タイムスタンプガベージコレクションルーチンは、現在検討されているレベルの未処理の各タイムスタンプを検討する。ライン１３で検出されるように、そのタイムスタンプに関連付けられたＷＲＩＴＥオペレーションが完了した場合において、現在のレベルが構成レベル又は最も低い制御処理レベルであるときは、タイムスタンプは、ライン１５において割り当て解除のためにマーキングされる。そうでない場合、タイムスタンプは、ライン１６において、次の最も低いレベルに降格される。すべてのレベルに関連付けられたすべてのタイムスタンプを検討した後、ライン２０において、ガベージコレクションルーチンが呼び出され、割り当て解除のためにマーキングされたすべてのタイムスタンプが削除される。
【０１０２】
階層的なタイムスタンプは、ＦＡＢシステムに加えて、多種多様な異なる階層構造の処理システムに用途を見出すことができる。階層的な処理システムには、ネットワーク通信システム、データベース管理システム、オペレーティングシステム、複雑なプロセスの制御システムを含むさまざまなリアルタイムシステム、及びそれ以外の階層的処理システムが含まれ得る。図３３Ａ〜図３３Ｆは、本発明の一実施の形態を表す、階層的に編成された処理システム内でタイムスタンプの範囲を段階的に制約するための一般的方法を要約したものである。図３３Ａに示すように、タイムスタンプ３３０４に関連付けられた初期要求３３０２が、最も高いレベルの処理ノード３３０６に入力される。タイムスタンプ３３０４は、それよりも高いレベルのインターフェースにおいて要求に関連付けておくこともできるし、処理ノード３３０６によって要求に関連付けることもできる。処理ノード３３０６は、次に、処理階層を通じて下方に要求を転送する。要求は、最初に第２のレベルの処理ノード３３０８へ転送される。第２のレベルの処理ノード３３０８は次に、２つの第３のレベルの処理ノード３３１０及び３３１２へ要求を転送する。２つの第３のレベルの処理ノード３３１０及び３３１２は、次に、第４のレベルの処理ノード３３１４及び３３１６へ要求を転送する。要求は、それ以降のレベルの処理ノードへ転送することができ、且つ／又は、コピーして転送することができる。
【０１０３】
処理ノード３３０６によって処理ノード３３０８へ転送された要求３３２０のレベルフィールド３３１８等、転送された要求に関連付けられたタイムスタンプのレベルフィールドは、すべて、処理階層内における最上位レベルの処理を数値的に表す０に設定される。次に、図３３Ｂに示すように、要求に対する応答が、処理階層を上に戻って最上位レベルの処理ノード３３０６へ返される。要求のコピーは、それらコピーを受信する処理ノードのそれぞれに引き続き関連付けられる。処理要求に関連付けられたタイムスタンプのレベルフィールドは、引き続き値０を有し、タイムスタンプが処理階層全体を通じて活性であることを示す。次に、図３３Ｃに示すように、最上位レベルの処理ノード３３０６は、次に最も低いレベルの処理ノード３３０８から成功の返答を受信すると、要求の実行が成功したものと判断し、その要求に関連付けられたタイムスタンプのすべてのレベルフィールドのレベル値を降格させる。したがって、図３３Ｃでは、処理階層全体を通じて保持される、すなわち処理階層全体の通じて見える、タイムスタンプのすべてのレベルフィールドのすべてが、値「１」に降格されている。最上位レベルの処理ノードの視点からすれば、タイムスタンプは、今や、ガベージコレクトされており、もはや活性ではない。したがって、最上位レベルの処理ノードは、その後、完了したオペレーションに関して、タイムスタンプの相違を検出することができない。
【０１０４】
図３３Ｄに示すように、第２のレベルの処理ノード３３０８は、それよりも低いレベルの処理ノードから成功の応答を受信すると、要求の完了が成功したものと判断し、処理階層全体を通じて保持される要求に関連付けられたすべてのタイムスタンプのレベルフィールドを値「２」に降格させる。この時点で、最上位レベルの処理ノード３３０６も第２のレベルの処理ノード３３０８もその後、完了したオペレーションに関してタイムスタンプの相違を検出することができない。図３３Ｅ及び図３３Ｆに示すように、各後続の次に最も低いレベルの１つ又は複数の処理ノードが、要求の完了が成功したことを決定すると、要求に関連付けられたすべてのタイムスタンプのレベルフィールドのレベル値はその後降格され、タイムスタンプの範囲は、引き続き、処理階層の次第に低い部分へ縮小されていく。最終的に、最終の降格の結果として、タイムスタンプは物理的にガベージコレクトされる。
【０１０５】
［タイムスタンプ問題に対する代替的な解決法］
前の小節で説明した階層的なタイムスタンプは、複製並びにマイグレーション及び再構成に適用できる、タイムスタンプ問題に対する密接した（well-bounded）解決法を表しているが、階層的なタイムスタンプは、或る場合に、タイムスタンプデータベースに対する更新回数を増加させるおそれがあり、ブリック間のメッセージングオーバーヘッド及びタイムスタンプデータベースオペレーションの複雑度の双方を増加させるおそれがある。タイムスタンプ問題に対する１つの代替的な解決法は、マイグレーションオペレーション及び再構成オペレーション中に、古い構成及び新しい構成に独立クォーラムシステムを使用することを伴う。
【０１０６】
同期された独立クォーラムシステム（「ＳＩＱＳ」）では、タイムスタンプは、現在の構成から新しい構成へのマイグレーション又は再構成の期間中に各構成について、独立クォーラムベース一貫性メカニズムの下で独立に管理され、独立にガベージコレクトされる。タイムスタンプは、２つの独立クォーラムシステムを管理するコーディネータよりも上の階層的なコーディネータシステムのレベルでは比較されない。したがって、再構成の場合には、タイムスタンプは、階層的なコーディネータシステム内の構成グループレベルよりも上では比較されず、マイグレーションの場合には、タイムスタンプは、ＳＣＮ−ノードレベルよりも上では比較されない。ＳＩＱＳ手法は、本発明の一実施の形態では、マイグレーション及び再構成の双方について、４フェーズプロセスを使用する。４フェーズプロセスの期間中、マイグレーション又は再構成に関与するすべてのブリックは、どの時点においても、互いの１フェーズ内にいる必要がある。そうでない場合、データ一貫性に関してなされた前提は有効ではない。したがって、マイグレーション又は再構成に関与する或るブリックは、当該ブリックのＳＩＱＳロジックを他のブリックのＳＩＱＳロジックと同期させて、どのブリックも、４フェーズプロセス内の当該ブリックの現在のフェーズに達しているすべてのブリックよりも前に次にフェーズに遷移しないことを確実にする。この同期は、多数の同期プロトコルのいずれによっても行うことができる。
【０１０７】
図３４は、本発明の一実施の形態を表すＳＩＱＳを示す制御フロー図である。ステップ３４０２は、マイグレーション及び再構成の４フェーズプロセスのフェーズ０を表している。このフェーズ０は、現在の構成のみが存在する初期フェーズである。ステップ３４０４において、フェーズＩが、新しい構成の初期化から開始する。ステップ３４０６において、現在の構成からのデータが新しい構成にコピーされる。フェーズＩの期間中、現在の構成及び新しい構成の双方が同時に存在する。現在の構成に向けられたＩ／Ｏオペレーションは、マイグレーション又は再構成の期間中処理され続ける。フェーズＩでは、ＲＥＡＤオペレーションは、現在の構成のみに向けられる一方、ＷＲＩＴＥオペレーション及びブロック再構築の一部として着手される読み出し回復（read-recovery）オペレーションは、現在の構成及び新しい構成の双方に向けられる。ステップ３４０６もフェーズＩの一部ではあるが、このステップ３４０６において、現在の構成からのデータが新しい構成にコピーされる。各ブリックのフロントエンドロジック及びバックエンドロジックによって保持されたデータ構造体は、さまざまなデータ構造体及び記憶された情報を使用して、このコピープロセス中に、構成内の未書き込みのブロック及び未割り当てのブロックの大きなグループをコピーすることを回避することができる。
【０１０８】
現在の構成からのデータを新しい構成にコピーすることが一旦成功すると、フェーズＩＩが、ステップ３４０８において開始する。フェーズＩＩの期間中、構成の変更に関与するすべてのブリックの構成状態を、必要に応じて、比較及び更新して、すべてのブリックの構成状態を、共通に共有された構成状態にする必要がある。ＳＩＱＳプロセスのフェーズＩＩの部分の期間中、すべてのＩ／Ｏオペレーションは、現在の構成及び新しい構成の双方に向けられる。現在の構成及び新しい構成に向けられたＲＥＡＤオペレーションが返すデータを比較して、データが同じであることを検証する必要がある。データが一致しない場合、２つのＲＥＡＤオペレーションが返すタイムスタンプに基づいて、現在の構成からのデータを新しい構成に書き込むか、又は新しい構成から返されたデータを使用するかの決定を行わなければならない。現在の構成から返されたタイムスタンプ値が、新しい構成から返されたタイムスタンプ値よりも大きい場合、データは、現在の構成から新しい構成に書き込まれる。現在の構成から返されたタイムスタンプ値が、新しい構成から返されたタイムスタンプ値よりも小さい場合、新しい構成から返されたデータが使用される。最終的に、タイムスタンプの一貫性及びデータ一貫性の双方がフェーズＩＩで達成されている場合、ステップ３４１２においてフェーズＩＩＩに入る。フェーズＩＩＩの期間中、現在の構成は、効力をなくして割り当て解除され、新しい構成のみが残される。
【０１０９】
タイムスタンプ問題に対する第２の代替的な解決法は、同期されていない独立クォーラムシステム（「ＵＩＱＳ」）を使用することを伴う。前述したＳＩＱＳの代替形態は、同期されたフェーズを使用する。この同期されたフェーズでは、現在の構成及び新しい構成の双方が、同期形式で完了までフェーズ内を同時に進む。これとは対照的に、ＵＩＱＳは、フェーズが同期されているのではなく、読み出しチェックに依拠して、マイグレーションオペレーション及び再同期オペレーションの期間中に一貫したデータ状態を保証する。図３５は、本発明の一実施の形態を表す、マイグレーション又は再構成の期間中にＵＩＱＳに向けられているＷＲＩＴＥオペレーションのハンドリングを示すフロー制御図である。ステップ３５０２において、マイグレーション又は再構成の階層レベルよりも上のコーディネータによって共通のタイムスタンプが生成される。ステップ３５０４において、このコーディネータは、ステップ３５０２で生成された共通のタイムスタンプを使用して、現在の構成によるＷＲＩＴＥオペレーションの実行を指揮する。ステップ３５０６において、それよりも上位レベルのコーディネータは、ステップ３５０２で生成された共通のタイムスタンプを使用して、新しい構成によるＷＲＩＴＥオペレーションの実行を指揮する。ステップ３５０８において双方のＷＲＩＴＥが完了したと判断されると、ステップ３５１０において、上位レベルのコーディネータは、ＷＲＩＴＥオペレーションからのステータスをホストに返すことを指揮し、次に、ステップ３５１２において、現在の構成及び新しい構成の双方においてガベージコレクションを開始する。ステップ３５１０においてホストに返されたステータスは、双方のＷＲＩＴＥが成功した場合には成功の表示となり、そうでない場合には失敗の表示となる。
【０１１０】
図３６は、本発明の一実施の形態を表す、ＵＩＱＳ手法による、マイグレーション又は再構成の期間中に着手されるＲＥＡＤオペレーションのフロー制御図である。ステップ３６０２において、ブロックが現在の構成から読み出される。ステップ３６０４において、ブロックが新しい構成から読み出される。ステップ３６０６において、ステップ３６０２及び３６０４で開始された２つのＲＥＡＤオペレーションにより返されたタイムスタンプが比較される。ステップ３６０８においてこれらのタイムスタンプが一致すると判断された場合、ＲＥＡＤオペレーションの一方からのデータが、ステータスＳＵＣＣＥＳＳ（成功）と共に返される。そうでない場合、ステップ３６１０において、２つのＲＥＡＤオペレーションによって返されたデータは比較され、データが等しいか否かが判断される。等しい場合には、ステップ３６１２において、ステータスＳＵＣＣＥＳＳと共にそのデータが返される。そうでない場合、ステップ３６１４において、ＷＲＩＴＥオペレーションが新しい構成に向けられ、ブロックの現在の構成のデータ値が新しい構成に書き込まれる。このＷＲＩＴＥオペレーションは、分散データストレージシステムで使用されるクォーラムベース一貫性システムによるタイムスタンプの比較を伴う。ステップ３６１６においてＷＲＩＴＥが成功したと判断された場合、ステップ３６１２において、新しい構成に書き込まれたデータは、ステータスＳＵＣＣＥＳＳと共に返される。そうでない場合、ステップ３６１８において、ステータスＦＡＩＬＵＲＥ（失敗）が返される。ＵＩＱＳ手法では、構成がＳＩＱＳの代替形態で使用されるフェーズベースのプロセスを受ける必要なく、データが現在の構成から新しい構成へコピーされて同期される。
【０１１１】
ＵＩＱＳのＲＥＡＤオペレーションの最適化は、データについては現在の構成及び新しい構成の一方のみから読み出すが、タイムスタンプについては双方から読み出すことである。図３７は、本発明の一実施の形態を表す、ＵＩＱＳ手法による、マイグレーション又は再構成の期間中に着手される最適化されたＲＥＡＤオペレーションのフロー制御図である。ステップ３７０２において、現在の構成のデータブロックについては、データ及びタイムスタンプの双方が読み出されるが、ステータス３７０４において、新しい構成のデータブロックについては、タイムスタンプのみが読み出される。これらのタイムスタンプが同一である場合、双方からデータを読み出して比較する必要はない。これらのタイムスタンプが異なる値を有する場合にのみ、データ比較ステップ３７０８に備えて、ステップ３７０６で、新しい構成からデータが読み出される。この最適化を使用すると、ＵＩＱＳをＳＩＱＳよりも効率的にすることができる。また、ＵＩＱＳ方法によって、複数のブリック上でＳＩＱＳを同期させるためのＳＩＱＳ方法で使用される同期方式に関連した通信オーバーヘッドも回避される。
【０１１２】
ＳＩＱＳ手法及びＵＩＱＳ手法は、マイグレーションプロセス及び再構成プロセスとは異なり、複製プロセスの期間中に連続Ｉ／Ｏオペレーション（continuing I/O operations）をハンドリングするにはそれほど望ましくない場合がある。ＵＩＱＳシステムは、マイグレーションプロセス及び再構成プロセスによってその後コピーされて同期されることになるブロックのＲＥＡＤオペレーションの期間中に、ブロック再構築を省くことによってさらに最適化することができる。
【０１１３】
本発明を特定の実施の形態の点から説明してきたが、本発明はこれらの実施の形態に限定されることを目的とするものではない。本発明の精神の範囲内での変更は、当業者に明らかである。たとえば、ＳＩＱＳ方法及びＵＩＱＳ方法は、基本的に無制限の個数の異なるデータ構造体、モジュール構造、制御構造、並びに他のこのようなプログラミング選択肢及びパラメータのいずれかを使用する任意の個数の異なるプログラミング言語で実施することができる。ＳＩＱＳ手法及びＵＩＱＳ手法は、複製、マイグレーション、及び再構成に対する２つの可能な独立クォーラムシステム手法を表しているが、複製、マイグレーション、及び再構成の期間中に２つの独立クォーラムシステムを一時的に調整するための他の方法が可能である。上記説明は、説明のためのものであり、具体的な専門用語を使用して本発明の徹底した理解を提供している。しかしながら、本発明を実施するのに、具体的な細部は必要とされないことが当業者には明らかであろう。本発明の具体的な実施の形態の上記説明は、図示及び説明の目的で提示されるものである。それら説明は、網羅的であることを目的とするものでもなければ、開示した正確な形に本発明を限定することを目的とするものでもない。上記教示に鑑み、多くの変更及び変形が可能であることは明らかである。実施の形態は、本発明の原理及びその実用的な用途を最も良く説明し、それによって、当業者が、本発明及びさまざまな変更を有するさまざまな実施の形態を、検討した特定の使用に適するように最も良く利用することを可能にするために図示して説明されたものである。本発明の範囲は、添付の特許請求の範囲及びその均等物によって画定されることが意図されている。
【図面の簡単な説明】
【０１１４】
【図１】本発明の一実施の形態によるＦＡＢマスストレージシステムの高レベルの図である。
【図２】本発明の一実施の形態による例示的なＦＡＢブリックの高レベルの図である。
【図３】データミラーリングの概念を示す図である。
【図４】データミラーリングの概念を示す図である。
【図５】イレージャ符号化冗長性を示す高レベルの図である。
【図６】図３及び図４で使用されたのと同じ説明図の規則を使用する３＋１イレージャ符号化冗長性方式を示す図である。
【図７】本発明の一実施の形態を表す、現在のＦＡＢの実施態様で使用される階層的なデータユニットを示す図である。
【図８Ａ】本発明の一実施の形態を表す、ＦＡＢシステムの物理ディスクへの論理データユニットの仮想的なマッピングを示す図である。
【図８Ｂ】本発明の一実施の形態を表す、ＦＡＢシステムの物理ディスクへの論理データユニットの仮想的なマッピングを示す図である。
【図８Ｃ】本発明の一実施の形態を表す、ＦＡＢシステムの物理ディスクへの論理データユニットの仮想的なマッピングを示す図である。
【図８Ｄ】本発明の一実施の形態を表す、ＦＡＢシステムの物理ディスクへの論理データユニットの仮想的なマッピングを示す図である。
【図９】本発明の一実施の形態を表す、ＦＡＢシステム内で使用される論理データユニットを、異なる説明図の規則で示す図である。
【図１０Ａ】各ブリックによって保持されたデータ構造体であって、ＦＡＢシステムの全データ状態を記述するとともに本発明の一実施の形態を表すデータ構造体を示す図である。
【図１０Ｂ】本発明の一実施の形態によるブリックロールを組み込むブリックセグメントアドレスを示す図である。
【図１１Ａ】本発明の一実施の形態を表す、ＦＡＢシステム内における図１０Ａに示すデータ記述データ構造体に反映されるさまざまな異なるタイプの構成の変更を示す図である。
【図１１Ｂ】本発明の一実施の形態を表す、ＦＡＢシステム内における図１０Ａに示すデータ記述データ構造体に反映されるさまざまな異なるタイプの構成の変更を示す図である。
【図１１Ｃ】本発明の一実施の形態を表す、ＦＡＢシステム内における図１０Ａに示すデータ記述データ構造体に反映されるさまざまな異なるタイプの構成の変更を示す図である。
【図１１Ｄ】本発明の一実施の形態を表す、ＦＡＢシステム内における図１０Ａに示すデータ記述データ構造体に反映されるさまざまな異なるタイプの構成の変更を示す図である。
【図１１Ｅ】本発明の一実施の形態を表す、ＦＡＢシステム内における図１０Ａに示すデータ記述データ構造体に反映されるさまざまな異なるタイプの構成の変更を示す図である。
【図１１Ｆ】本発明の一実施の形態を表す、ＦＡＢシステム内における図１０Ａに示すデータ記述データ構造体に反映されるさまざまな異なるタイプの構成の変更を示す図である。
【図１１Ｇ】本発明の一実施の形態を表す、ＦＡＢシステム内における図１０Ａに示すデータ記述データ構造体に反映されるさまざまな異なるタイプの構成の変更を示す図である。
【図１１Ｈ】本発明の一実施の形態を表す、ＦＡＢシステム内における図１０Ａに示すデータ記述データ構造体に反映されるさまざまな異なるタイプの構成の変更を示す図である。
【図１２】分散ストレージレジスタの基本オペレーションを示す図である。
【図１３】分散ストレージレジスタの基本オペレーションを示す図である。
【図１４】分散ストレージレジスタの基本オペレーションを示す図である。
【図１５】分散ストレージレジスタの基本オペレーションを示す図である。
【図１６】分散ストレージレジスタの基本オペレーションを示す図である。
【図１７】分散ストレージレジスタの基本オペレーションを示す図である。
【図１８】分散ストレージレジスタの基本オペレーションを示す図である。
【図１９】多数の他のプロセス及び／又は処理エンティティＰｊ≠ｉと共に分散ストレージレジスタを実施するプロセス又は処理エンティティＰｉによって使用されるコンポーネントを示す図である。
【図２０】クォーラムによる分散ストレージレジスタの現在の値の求値を示す図である。
【図２１】図１９に図的に示すルーチンハンドラ及び操作ルーチンの擬似コードの実施態様を示す図である。
【図２２】図１７に提供した擬似コードに類似した修正擬似コードであって、本発明の一実施の形態を表すＦＡＢシステム内におけるイレージャ符号化冗長性方式に従ってブリックにわたるセグメントの分散をハンドリングするストレージレジスタモデルへの拡張を含む、修正擬似コードを示す図である。
【図２３】本発明の一実施の形態を表す、ＦＡＢシステム内におけるストレージレジスタモデルに基づいたデータ一貫性技法によるタイムスタンプに対する大きな依存関係を示す図である。
【図２４】本発明の一実施の形態を表す階層的なタイムスタンプ管理を示す図である。
【図２５】本発明の一実施の形態を表す、ＦＡＢシステム内における分散されたセグメントの再構成に起因して存在し得る複数のアクティブな構成に対するクォーラムベースの書き込みの概念を含むさらに拡張されたストレージレジスタモデルの擬似コードを提供する図である。
【図２６】本発明の一実施の形態を表す、ＦＡＢシステム内における分散されたセグメントの再構成に起因して存在し得る複数のアクティブな構成に対するクォーラムベースの書き込みの概念を含むさらに拡張されたストレージレジスタモデルの擬似コードを提供する図である。
【図２７】本発明の一実施の形態を表す、ＦＡＢシステム内でストレージレジスタモデルをマイグレーションレベルへ拡張するための高レベルの擬似コードを示す図である。
【図２８】本発明の一実施の形態を表す、ＦＡＢシステム内の制御処理及びデータストレージの双方の全階層構造を示す図である。
【図２９Ａ】特定のセグメントを分散するための、４＋２イレージャ符号化冗長性方式から８＋２イレージャ符号化冗長性方式へのマイグレーションの状況におけるタイムスタンプ問題を示す図である。
【図２９Ｂ】特定のセグメントを分散するための、４＋２イレージャ符号化冗長性方式から８＋２イレージャ符号化冗長性方式へのマイグレーションの状況におけるタイムスタンプ問題を示す図である。
【図２９Ｃ】特定のセグメントを分散するための、４＋２イレージャ符号化冗長性方式から８＋２イレージャ符号化冗長性方式へのマイグレーションの状況におけるタイムスタンプ問題を示す図である。
【図３０】本発明の一実施の形態を表す新しいタイプのタイムスタンプの１つを示す図である。
【図３１Ａ】複数の冗長性方式の下で複数のブリック上に分散されたＦＡＢセグメントへのＷＲＩＴＥオペレーション中のデータ一貫性を容易にするための、本発明の一実施の形態を表す新しいタイプのタイムスタンプの使用を示す図である。
【図３１Ｂ】複数の冗長性方式の下で複数のブリック上に分散されたＦＡＢセグメントへのＷＲＩＴＥオペレーション中のデータ一貫性を容易にするための、本発明の一実施の形態を表す新しいタイプのタイムスタンプの使用を示す図である。
【図３１Ｃ】複数の冗長性方式の下で複数のブリック上に分散されたＦＡＢセグメントへのＷＲＩＴＥオペレーション中のデータ一貫性を容易にするための、本発明の一実施の形態を表す新しいタイプのタイムスタンプの使用を示す図である。
【図３１Ｄ】複数の冗長性方式の下で複数のブリック上に分散されたＦＡＢセグメントへのＷＲＩＴＥオペレーション中のデータ一貫性を容易にするための、本発明の一実施の形態を表す新しいタイプのタイムスタンプの使用を示す図である。
【図３１Ｅ】複数の冗長性方式の下で複数のブリック上に分散されたＦＡＢセグメントへのＷＲＩＴＥオペレーション中のデータ一貫性を容易にするための、本発明の一実施の形態を表す新しいタイプのタイムスタンプの使用を示す図である。
【図３１Ｆ】複数の冗長性方式の下で複数のブリック上に分散されたＦＡＢセグメントへのＷＲＩＴＥオペレーション中のデータ一貫性を容易にするための、本発明の一実施の形態を表す新しいタイプのタイムスタンプの使用を示す図である。
【図３２】本発明の一実施の形態を表す、非同期タイムスタンプコレクションプロセスの擬似コードを示す図である。
【図３３Ａ】本発明の一実施の形態を表す、階層的に編成された処理システム内でタイムスタンプの範囲を段階的に制約するための一般的方法を要約した図である。
【図３３Ｂ】本発明の一実施の形態を表す、階層的に編成された処理システム内でタイムスタンプの範囲を段階的に制約するための一般的方法を要約した図である。
【図３３Ｃ】本発明の一実施の形態を表す、階層的に編成された処理システム内でタイムスタンプの範囲を段階的に制約するための一般的方法を要約した図である。
【図３３Ｄ】本発明の一実施の形態を表す、階層的に編成された処理システム内でタイムスタンプの範囲を段階的に制約するための一般的方法を要約した図である。
【図３３Ｅ】本発明の一実施の形態を表す、階層的に編成された処理システム内でタイムスタンプの範囲を段階的に制約するための一般的方法を要約した図である。
【図３３Ｆ】本発明の一実施の形態を表す、階層的に編成された処理システム内でタイムスタンプの範囲を段階的に制約するための一般的方法を要約した図である。
【図３４】本発明の一実施の形態を表す同期された独立クォーラムシステム（「ＳＩＱＳ」）を示す制御フロー図である。
【図３５】本発明の一実施の形態を表す、マイグレーション又は再構成の期間中に、同期されていない独立クォーラムシステム（「ＵＩＱＳ」）に向けられたＷＲＩＴＥオペレーションのハンドリングを示すフロー制御図である。
【図３６】本発明の一実施の形態を表す、ＵＩＱＳ手法による、マイグレーション又は再構成の期間中に着手されるＲＥＡＤオペレーションのフロー制御図である。
【図３７】本発明の一実施の形態を表す、ＵＩＱＳ手法による、マイグレーション又は再構成の期間中に着手される最適化されたＲＥＡＤオペレーションのフロー制御図である。
【符号の説明】
【０１１５】
１０２〜１０９・・・マスストレージデバイス
１１０，１１４・・・通信媒体
１１２，１１３・・・リモートホストコンピュータ
２０２〜２１３・・・ＳＡＴＡディスクドライブ
２１４・・・ディスクＩＯＰ
２１６・・・高速バス
２１８・・・中央ブリッジ
２２０・・・プロセッサ
２２２・・・ホストＩＯＰ
２２４・・・ブリック間ＩＯＰ
２２６，２２７，２２８・・・メモリ
７０２・・・全ストレージアドレス空間
７０４，７０６・・・仮想ディスク
７０８，７１０・・・セグメント
７１２，７１４・・・ブリック
７１６・・・ディスク
７１８・・・ページ
７２０・・・ブロック
８２６・・・全ストレージ
８２８・・・仮想ディスク
８３０・・・仮想ディスクイメージ
８３２・・・セグメント
９０２・・・全ストレージ
９０４，９０５，９０６，９０７・・・仮想ディスク
９０８，９０９，９１０，９１２・・・仮想ディスクイメージ
９１６，９２０・・・セグメント
９１４・・・順序付きリスト
９１８，９２２・・・ブリック
１００２・・・仮想ディスクテーブル
１００４・・・ＶＤＴＥエントリー
１００６，１００８・・・ＶＤＩテーブル
１０１０・・・ＳＣＮ
１０１２，１０１４・・・ｃｇｒｐ
１０１６・・・ｃｆｇ
１０１８・・・レイアウト
１０２０・・・ブリック
１０２２・・・セグメント
１０２４・・・ブロック
１０２６・・・冗長性方式
１０２８・・・ブリック位置
１０３０・・・ストライプサイズ
１１４１，１１４５・・・ｃｇｒｐ
１１４６・・・ＳＣＮ
１１４８・・・ＶＤＴＥエントリー
１１５０，１１５２・・・ＶＤＩテーブル
１９０２・・・タイマメカニズム
１９０４・・・ＰＩＤ
１９０６・・・リアルタイム時計
１９０８・・・揮発性メモリ
１９１０・・・不揮発性メモリ
１９１８・・・ＲＥＡＤハンドラ
１９２０・・・ＯＲＤＥＲハンドラ
１９２２・・・ＷＲＩＴＥハンドラ
１９２４・・・ＯＲＤＥＲデュアルハンドラ
２３０２，２３１４，２３１８，２３２０，２３２１，２３２４・・・ブロック
２３０４〜２３１２・・・ブリック
２３１６，２３１７，２３２８・・・タイムスタンプ
２３２６・・・ログエントリー
２４００・・・非循環グラフ
２４０２，２４０４・・・リーフノード
２４０６，２４０８・・・ブロック
２８０２・・・最上位レベルコーディネータ
２８０４・・・仮想ディスクレベル
２８０６・・・ＶＤＩコーディネータ
２８０８・・・ＶＤＩレベル
２８１０・・・ＳＣＮコーディネータ
２８１２・・・ＳＣＮレベル
２８１４・・・構成グループコーディネータ
２８１６・・・構成グループレベル
２８１８・・・構成コーディネータ
２８２０・・・構成レベル
３０００・・・タイムスタンプ
３００２・・・タイムスタンプが適用されるエンティティの説明
３００４・・・時刻又はシーケンス値
３００６・・・レベル
３００８・・・追加フィールド
３１１０・・・トリプルミラー
３３０２，３３２０・・・要求
３３０４，３３１８・・・タイムスタンプ
３３０６〜３３１６・・・処理ノード
【図１】
0004516087.tif 000013
【図２】
0004516087.tif 000014
【図３】
0004516087.tif 000015
【図４】
0004516087.tif 000016
【図５】
0004516087.tif 000017
【図６】
0004516087.tif 000018
【図７】
0004516087.tif 000019
【図８Ａ】
0004516087.tif 000020
【図８Ｂ】
0004516087.tif 000021
【図８Ｃ】
0004516087.tif 000022
【図８Ｄ】
0004516087.tif 000023
【図９】
0004516087.tif 000024
【図１０Ａ】
0004516087.tif 000025
【図１０Ｂ】
0004516087.tif 000026
【図１１Ａ】
0004516087.tif 000027
【図１１Ｂ】
0004516087.tif 000028
【図１１Ｃ】
0004516087.tif 000029
【図１１Ｄ】
0004516087.tif 000030
【図１１Ｅ】
0004516087.tif 000031
【図１１Ｆ】
0004516087.tif 000032
【図１１Ｇ】
0004516087.tif 000033
【図１１Ｈ】
0004516087.tif 000034
【図１２】
0004516087.tif 000035
【図１３】
0004516087.tif 000036
【図１４】
0004516087.tif 000037
【図１５】
0004516087.tif 000038
【図１６】
0004516087.tif 000039
【図１７】
0004516087.tif 000040
【図１８】
0004516087.tif 000041
【図１９】
0004516087.tif 000042
【図２０】
0004516087.tif 000043
【図２１】
0004516087.tif 000044
【図２２】
0004516087.tif 000045
【図２３】
0004516087.tif 000046
【図２４】
0004516087.tif 000047
【図２５】
0004516087.tif 000048
【図２６】
0004516087.tif 000049
【図２７】
0004516087.tif 000050
【図２８】
0004516087.tif 000051
【図２９Ａ】
0004516087.tif 000052
【図２９Ｂ】
0004516087.tif 000053
【図２９Ｃ】
0004516087.tif 000054
【図３０】
0004516087.tif 000055
【図３１Ａ】
0004516087.tif 000056
【図３１Ｂ】
0004516087.tif 000057
【図３１Ｃ】
0004516087.tif 000058
【図３１Ｄ】
0004516087.tif 000059
【図３１Ｅ】
0004516087.tif 000060
【図３１Ｆ】
0004516087.tif 000061
【図３２】
0004516087.tif 000062
【図３３Ａ】
0004516087.tif 000063
【図３３Ｂ】
0004516087.tif 000064
【図３３Ｃ】
0004516087.tif 000065
【図３３Ｄ】
0004516087.tif 000066
【図３３Ｅ】
0004516087.tif 000067
【図３３Ｆ】
0004516087.tif 000068
【図３４】
0004516087.tif 000069
【図３５】
0004516087.tif 000070
【図３６】
0004516087.tif 000071
【図３７】
0004516087.tif 000072