JP2008533564A - データ管理のための方法および装置 - Google Patents

Abstract

改善されたアクセシビリティ、完全性、スケーラビリティ、および他の特徴を提供するために、データ格納からデータ処理を切り離すデータアクセスシステム。システムは：各々独立にアクセス可能な仮想パーティションに配列されるデータベースユニット、複数のデータ処理ユニット、および仮想パーティション間でデータ処理ユニットを交換し、それによってデータ処理容量をそれぞれの仮想パーティションに割り当てるための交換網を含む。
【選択図】 なし

Description

本発明は、データ管理のための方法または装置に関し、さらに詳しくは、分散アーキテクチャを使用するそのような方法または装置に関するが、それに限定されない。

分散データリポジトリ
最もミッションクリティカルなデータリポジトリは、データネットワークによって相互接続された幾つかのコンピューティングサーバで実行される分散システム、つまり分散データリポジトリとして構築される。分散データリポジトリの例として、ファイルシステム、ディレクトリ、およびデータベースがある。ミッションクリティカルなデータリポジトリは、主として高い可用性および高いスケーラビリティをもたらす分散システムとして構築される。

１．高い可用性は、単一のコンピューティングサーバの障害により、各々および全部のデータ要素を含むデータリポジトリの全体としての可用性が損なわれないようにもたらされる。

２．高いスケーラビリティは、２つの異なる次元で、すなわち（１）データの量、および（２）読出し／書込みトランザクションレート（スループット）でもたらされる。いずれの場合も、より多くのデータ量および／またはより高いトランザクションレートをサポートするために、より多くのコンピューティングサーバをシステムに追加することができれば、分散データリポジトリは「高度にスケーラブル」である。ミッションクリティカルな分散データリポジトリのスケーラビリティは「オンラインスケーラビリティ」をも必要とし、それは、システムがデータ管理サービスを提供し続けながらスケーリングすることができることを意味する。

実時間事象処理
分散データリポジトリが、実時間事象処理を実行するデータアプリケーションを提供するときに、分散データリポジトリは高い応答性をサポートすることも期待される。

３．高い応答性は、各読出しおよび各書込みトランザクションが予め定められた時間量内に非常に高い確率で完了することが保証されるように、実時間データリポジトリにもたらされる。実時間データリポジトリでは、高可用性およびオンラインスケーラビリティ要件は、障害時およびスケーラビリティ事象中に、システムの連続的な高応答性を維持することも期待される。

実時間事象処理データアプリケーションの例として、テレコム呼制御、移動電話ホームロケーションレジストラ（ＨＬＲ）、インターネットマルチメディアシステム（ＩＭＳ）、ホームサブスクライバサーバ（ＨＳＳ）、オンラインバンキングおよびトレーディングシステムがある。

ミッションクリティカルな実時間データリポジトリシステムは、可用性が高く、スケーラビリティが高く、かつ応答性が高いことが期待される。これらの要件の組合せをサポートすることは、非常にやりがいのある課題である。応答性要件は、要求される時間量内にトランザクションが完了することを確実にするために、トランザクション用の専用コンピューティング資源を割り当て、かつ振り向けることを示唆するかもしれない。この戦略は、応答性に悪影響を及ぼすので、典型的なパイプラインおよび時分割処理スケジューリングによるトランザクションレートを加速させる効率を低下させる。

他方、高可用性要件は一般的に、高可用性ストレージデバイス（例えばＲＡＩＤ−独立ディスクの冗長アレイ）に全てのミッションクリティカルなデータ項目を格納することを示唆する。それは、全ての書込みトランザクションがコミットされ完了する前に、それをディスクに書き込む必要があることを意味する。さもなければ、書込み演算素子が故障した場合に、データが利用不能になる。この戦略は、多数のＣＰＵを持つ大型コンピューティングサーバで実行されるときでさえ、達成されるトランザクションレートを低減する（ＳＭＰ−対称型多重処理）。

多くの場合、ミッションクリティカルなデータリポジトリは、読出し／書込みトランザクションのために幾つかの異なるコンピューティングエンティティ（「クライアント」）によって同時にアクセスされ、したがって分散データリポジトリはまた、システム全体の一貫性を提供することも必要である。全てのクライアントの観点から各データ要素値の変化の順序が同一である場合、データリポジトリは「一貫性がある」（または「順序一貫性がある」）とみなされる。

書込みトランザクションを実行する多数の並行クライアントをサポートする分散データリポジトリのほとんどの実現において、一貫性の要件は、トランザクションレートに関するシステムスケーラビリティに対する制限因子でもある。これは、書込みトランザクションをシリアル化する必要があり、かつ読出しトランザクションを一般的に、保留中の書込みトランザクションが完了するまで遅延しなければならないからである。読出し／書込みトランザクションのシリアル化は一般的に、システム内のデータの編成の仕方のため（例えば同一ディスク上に、同一メモリ内に、等）、異なるトランザクションが異なるデータ要素にアクセスするときにも行なわれる（つまり独立トランザクション）。

「全共有」分散キャッシュコヒーレンシアーキテクチャ
従来の分散データリポジトリ（例えばＯｒａｃｌｅ Ｒｅａｌ Ａｐｐｌｉｃａｔｉｏｎ Ｃｌｕｓｔｅｒｉｎｇおよびその他）は、高可用性ストレージを使用して（一般的にＲＡＩＤ技術を使用して）、ミッションクリティカルなデータを格納しながら、データのメモリ内コピーのコヒーレントローカルキャッシュを維持する。この「全共有」分散キャッシュコヒーレンシアーキテクチャは、柔軟性のあるアクティブ−アクティブＮ＋Ｍ高可用性を提供することができるので、全てのコンピューティングノードを利用して、全てのデータ処理負荷を共有することができる。１つまたはそれ以上のノードが故障した場合、存続するノードを利用して、故障したノードによって取り扱われたデータ処理を引き継ぐことができる。

「全共有」分散キャッシュコヒーレンシアーキテクチャを図１に示す。該アーキテクチャは、読出しトランザクションレートのスケーラビリティを提供することができる。つまり、システムにより多くのノードを追加すると、読出しトランザクションレートを高めることができる。しかし、「全共有」分散キャッシュコヒーレンシアーキテクチャは一般的に、全てのローカルキャッシュ間で各書込みを調整する必要性のため、書込みトランザクションレートスケーラビリティが無く、または低下する場合さえあるという欠点がある。したがって、システムに追加されるノードが多いほど、全てのローカルキャッシュの間でキャッシュコヒーレンシを維持するために、各書込みトランザクションをコミットし完了するまでにかかる時間が長くなる。書込みトランザクションのコミットおよび完了におけるこの遅延の増大のため、トランザクションの大部分が書込みトランザクションである場合、「全共有」分散キャッシュコヒーレンシアーキテクチャは、実時間トランザクション処理を必要とするアプリケーションをサポートするには適さなくなる。大きい書込みトランザクションレートが存在する場合には、応答性要件を満たすことができず、上述した実時間事象処理アプリケーションは高い書込みトランザクションレートを有することが一般的であるので、これは問題となる。したがって、「全共有」分散キャッシュコヒーレンシアーキテクチャは、大規模に展開される場合にはそのようなアプリケーションには適さない。

「無共有」データパーティショニングアーキテクチャ
他の分散データリポジトリ（例えばＩＢＭ ＤＢ２ ＵＤＢおよびＭｙＳＱＬ）は、図２に示すような「無共有」データパーティショニングアーキテクチャを使用する。無共有アーキテクチャでは、分散データリポジトリシステムは、幾つかの独立分散データリポジトリサブシステムにパーティション化され、各々がデータの異なる部分を管理する。「無共有」データパーティショニングアーキテクチャでは、各パーティションを「全共有」分散キャッシュコヒーレンシサブシステムとして表示することができ、各々がそれ自体の高可用性ストレージを持つ。

「無共有」データパーティショニングアーキテクチャは、システムが有する独立パーティションが多いほど、非ブロッキング方法で同時に実行できる異なるパーティションへの書込みトランザクションが多くなるので、書込みレートスケーラビリティの問題を克服する。したがって、書込みコミット応答性もそのようなアーキテクチャによって充分に取り扱うことができる。

「無共有」データパーティショニングアーキテクチャの鍵は、コンピューティング資源のパーティショニングがデータパーティショニングに緊密に結合されていることである。これは、コンピューティング資源が各データパーティションに静的に割り当てられることを意味する。システムの書込みレートが高くなったときに、システムをスケールアップする唯一の方法は、システムをより多数のパーティションに再分割し、新しいパーティションにより多くのコンピューティング資源を割り当てることである。このスケーリングプロセスは一般的にパーティション間のデータの再分散を必要とし、応答性の高いオンラインデータベースサービスを提供し続けるシステムの能力を害することなく実行することはできない。したがって、再パーティショニングは一般的に、システム全体の計画ダウンタイムを必要とする。したがって、オンラインスケーラビリティは「無共有」データパーティショニングアーキテクチャでは達成することができない。さらに、「無共有」アーキテクチャの潜在的な同時並行性を完全に利用するためには、クライアントアプリケーションは一般的に、データがパーティション化される方法を知っている必要があり、それは再パーティショニング事象がクライアントアプリケーション自体の変更をも必要とし得ることを意味する。これは、「無共有」アーキテクチャの管理および保守を非常に高価にする。

「メモリ内」データリポジトリアーキテクチャ
より良い応答性をもたらし、かつより良い全体的トランザクションレートをもたらすために、トランザクション待ち時間を低減することに重点を置いた、他のデータリポジトリアーキテクチャが出現した。これは、単一の機械の１つの充分に大きいメモリ内に全てのデータを維持し、かつ全てのデータベース動作をこのメモリ内で直接実行することによって、行なわれる。コンピュータ作業メモリにアクセスする待ち時間は、ディスク等のストレージデバイスにアクセスするより数桁短縮することができる。したがって、メモリ内の全データを管理することにより、該データリポジトリはずっと短いトランザクション待ち時間を獲得し、したがって、より高いトランザクションレートをも獲得する。

ミッションクリティカルなメモリ内データリポジトリは一般的に、メモリ内データがローカルネットワークを介して複製インスタンス間で連続的に同期化されるように（「全共有」アーキテクチャのキャッシュコヒーレンシ機構の場合と同様に）、システムを２つ以上の同一インスタンスに複製している。ネットワークベースのデータコミットは、書込みトランザクション完了の待ち時間を増大し、したがって書込みトランザクションレートをも低下させる。しかし、ネットワークベースのデータ同期化は耐障害性を可能にする。

上記の変形として、冗長性のために２つ以上のデータリポジトリを設け、リポジトリ間で更新を行なうことが可能である。

図３を参照すると、耐障害性を持つメモリ内リポジトリが図示されている。

メモリ内データリポジトリは、単一のコンピューティングサーバによって提供される容量および書込みトランザクションレートを超えてスケーリングすることはできない。「メモリ内」データリポジトリシステムの容量および／または書込みトランザクションレートをスケーリングする唯一の方法は、コンピューティングシステムにメモリを追加すること、あるいはコンピューティングシステムのメモリ容量が限度まで使用し尽くされた場合には、システムをより多くのメモリおよびより多くのＣＰＵ（つまり、より大型のＳＭＰサーバ）を持つより大型のコンピューティングシステムに移すことである。両方のスケーラビリティ戦略はどちらもシステムの計画ダウンタイムを必要とし、したがって高可用性およびオンラインスケーラビリティ要件に適合しない。容量および書込みトランザクションレートはどちらも、単にコンピューティングサーバを追加するだけではスケーリングすることができない。

メモリ内データリポジトリは一般的に、最大限の性能および短い待ち時間を達成するために、アプリケーションおよびデータベースのコロケーションを必要とする。データベースは一般的にＣＰＵ毎に価格設定されるが、ＣＰＵはデータベース専用ではなく、アプリケーションにも使用されるので、これはデータベースの実際のコストを引き上げる。したがって、ＣＰＵおよびメモリ資源を使用する実際のアプリケーションは、データベースの実際のコストパフォーマンスを著しく低減させる。他方、メモリ内データベースおよびアプリケーションを別個のボックスに分離すると、データベースで使用されるメモリの最大限の利用が可能になるが、最初にメモリ内データベースを使用することによって獲得される性能がしばしば低減される。

したがって、上記システムの利点を結合しかつ欠点を回避するシステムの必要性が広く認識されており、かつそれを手にすることは非常に有利であろう。

本発明の１態様では、
各々独立にアクセス可能な仮想パーティションに配列されるデータベースユニットと、
複数のデータ処理ユニットと、
仮想パーティション間でデータ処理ユニットを交換し、それによってデータ処理容量をそれぞれの仮想パーティションに動的に割り当てるための（１つまたはそれ以上の相互接続されたスイッチングユニットを結合した）交換網と
を備えたデータアクセスシステムを提供する。

好ましくは、各データベースユニットは、それぞれのネットワークチャネルとして独立にアクセス可能である。

該システムは、データにハッシュプロセスを実行するためのハッシュユニットを備えることができ、その場合、データは、ハッシュプロセスの結果を介して、それぞれのデータベースユニットに割り当てられる。

好ましくは、データは１つまたはそれ以上のテーブルの集合の形で割り当てられる。好ましくは、各テーブルは、一次キーおよび／または１つもしくはそれ以上の二次キーを有するレコードの集合の形で割り当てられる。ハッシュプロセスは、キーの１つ、ここではテーブルの先頭キーに対して実行される。テーブルの先頭キーは、２つ以上のフィールドを意味する複合キーおよび／または非一意キーおよび／または外部キーをはじめ、任意のキーとすることができる。

好ましくは、データは、先頭キーおよびおそらく１つまたはそれ以上の二次キーを有するレコードの形で割り当てられ、その場合、各レコードは、一次アドレス、先頭キーに基づく「一次ハッシュ」、および二次ハッシュと呼ばれる二次キーに基づくおそらく１つまたはそれ以上の二次アドレスをも割り当てられる。

２つ以上のテーブルが同じ先頭キーを共有することができる。一般的に、そのような先頭キーは外部キーであってもよいが、これは不可欠ではない。その結果、一次ハッシュアドレスは、同じ一次キーを共有する異なるテーブルの全てのレコードに対して同一であり続ける。したがって、必要な場合には、レコードを単一のデータエンティティとして管理することもできる。

２つ以上のテーブルが１つまたはそれ以上の二次キーを共有することもでき、したがって異なるテーブルのレコードが二次ハッシュアドレスを共有することもできる。

システムは、二次アドレスを対応する一次アドレスに解決する（ｒｅｓｏｌｖｉｎｇ）ためのレゾリューションユニット（ｒｅｓｏｌｕｔｉｏｎ ｕｎｉｔ）を備えることができる。

好ましくは、レゾリューションユニットは少なくとも１つのルータを含む。システムの高可用性を確実にするために、バックアップルータを設けることもできる。１つのルータの故障後に、データ要素が二次アドレスを使用して利用可能であり続けるように、残りのルータが依然として二次アドレスから一次アドレスへの解決を取り扱うことができることを確実にするには、１つのバックアップルータだけで充分である。

二次キー解決（ｓｅｃｏｎｄａｒｙ ｋｅｙ ｒｅｓｏｌｕｔｉｏｎ）、つまりルーティングは、二次キーが一意であるか否かによって、二次キーを１つまたはそれ以上の一次キーにマッピングする内部インデックステーブルをシステムに維持させることによって、行なうこともできる。この内部インデックステーブルは、二次キーをインデックステーブルの先頭キーとして使用して、全ての仮想パーティションにわたってハッシングされる。そのような場合、二次キーの一次キーへのルーティングは、いずれかの他のテーブルが読み出されるのと同様の仕方でインデックステーブルを読み出すことによって行なわれる。

該システムは、データ処理ユニットの故障後に、システムが依然として全てのデータにアクセスすることができるように、全ての仮想パーティションが幾つかのデータ処理ユニットによって格納されかつ管理されるように構成することができる。

好ましくは、各仮想データパーティションは奇数個のコピーを有する。奇数個は、バージョン間の多数決が一般的に働くことを確実にする。好ましくは、書込みおよび読出し動作を含め、全てのデータ処理は過半数に基づくグループ決定によって実行され、例えば幾つかのデータ処理ユニットの故障のため、各仮想パーティションのコピーのマイノリティが失われた場合でさえも、システムはデータへの不断のアクセシビリティを提供し続けることができる。マイノリティの最大サイズは、システムの耐障害性のレベルである。例えばシステムが各仮想データパーティションに５つのコピーを有する場合には、システムは、各読出しおよび書込みトランザクションに対する多数決を喪失することなく、各仮想データパーティションのコピーを最大２つまで喪失することができる。したがって、システム内の各データ要素のアクセシビリティを喪失することなく、最高２つまでのコピーを喪失することができる。

システムは、競合する同時並行書込み動作間の調停を行なうリーダまたはコーディネータとして、データ処理ユニットの１つを各仮想パーティションに動的に割り当てるための選定機能を含むことができる。

システムは、仮想パーティションをデータ処理ユニットに動的に割り当てるための選定機能を含むことができる。

システムは、第１データ処理ユニットの故障後に、仮想データパーティションの紛失コピーが残りのデータ処理ユニットの全部または一部に再割当てされるように、トリガされる自己回復機構を含むことができる。その結果、システムの耐障害性は、その目標レベルに戻る傾向がある。

９が５つ並んだ数字（９９．９９９％）の可用性は、キャリアグレードのシステムの典型的な要件である。現在、大規模システムの場合、基礎を成すデータ処理ユニット自体が各々９９．９％の可用性を持ち、かつ自己回復機構が数分以内にトリガされることを前提として、各データレコードまたは仮想パーティションの３つのコピーがあれば、一般的に充分である。９９．９９９％レベルを超える超高可用性の場合、かつ／または巨大システムの場合、５つのコピーがあれば充分である。特に明記しない限り、本書で使用する全ての科学技術用語は、本発明が属する技術分野の通常の熟練者によって一般的に理解されるのと同じ意味を有する。本書に提示する材料、方法、および実施例は単なる例示であって、限定の意図は無い。

本発明の方法およびシステムの実現は、特定の選択されたタスクまたはステップを手動的に、自動的に、またはそれらを組み合わせて実行または完遂することを含む。さらに、本発明の方法およびシステムの好適な実施形態の実際の機器および設備では、幾つかの選択されたステップをハードウェアによって、またはいずれかのファームウェアのいずれかのオペレーティングシステムにおけるソフトウェアによって、またはそれらを組み合わせて実現することができる。例えば、ハードウェアとしては、本発明の選択されたステップは、チップまたは回路として実現することができる。ソフトウェアとしては、本発明の選択されたステップは、いずれかの適切なオペレーティングシステムを使用するコンピュータによって実行される、複数のソフトウェア命令として実現することができる。いずれの場合にも、本発明の方法およびシステムの選択されたステップは、複数の命令を実行するためのコンピューティングプラットフォーム等のデータプロセッサによって実行されると記載することができる。

図面の簡単な記述
本明細書では本発明を単に例示し図面を参照して説明する。特に詳細に図面を参照して、示されている詳細が例示として本発明の好ましい実施態様を例示考察することだけを目的としており、本発明の原理や概念の側面の最も有用でかつ容易に理解される説明であると考えられるものを提供するために提示していることを強調するものである。この点について、本発明を基本的に理解するのに必要である以上に詳細に本発明の構造の詳細は示さないが、図面について行う説明によって本発明のいくつもの形態を実施する方法は当業者には明らかになるであろう。

図１は、先行技術の全共有分散キャッシュコヒーレンシアーキテクチャを示す。
図２は、データが異なるデータノードにパーティション化され、各パーティションが全共有分散キャッシュコヒーレンシとして管理される、先行技術の無共有アーキテクチャを示す。
図３は、全てのデータがメモリ内に維持され、異なるコンピューティングユニットの２つ以上のメモリの間で完全に複製され、かつ同期化される、先行技術の耐障害性メモリ内データリポジトリアーキテクチャを示す。
図４は、仮想パーティションとコンピューティングユニットとの間の動的マッピングのために交換チャネルネットワーキングが使用される、本発明の好適な実施形態に係るアーキテクチャを示す簡略図である。この簡略化された事例では、仮想パーティションは複製されず、各コンピューティングユニットが１つまたはそれ以上の仮想データパーティションの単一のコピーを格納かつ管理するように、コンピューティングユニットと仮想パーティションとの間に１対多数の関係が存在することができる。
図５は、図４のアーキテクチャを示す簡略図であるが、ここではデータ複製を有するので、コンピューティングユニットとデータ複製との間に多数対多数の関係が存在する。各コンピューティングユニットは１つまたはそれ以上の仮想データパーティションを格納かつ管理し、各データパーティションは３つのコンピューティングユニットによって格納かつ管理される。
図６〜８は、本発明の好適な実施形態に係る階層ベースの仮想パーティションを使用して表わすことのできる、階層状のデータ編成のためのツリー構造を示す。
図９は、本発明の好適な実施形態に係るパーティショニング手順を示す簡略フローチャートである。
図１０Ａおよび１０Ｂは、２つのレベルのサブチャネルを有するチャネルを示し、かつさらに、本発明の好適な実施形態に係るチャネル階層内のマイクロリポジトリの割当てを示す。
図１１および図１２Ｂは、仮想パーティションが本発明の好適な実施形態に係る階層ベースである、図４のアーキテクチャの部分を示す簡略ブロック図である。
図１２Ａは、本発明の好適な実施形態を使用する３フェーズコミット書込み動作を示す簡略フローチャートである。
図１２Ｃは、本発明の好適な実施形態に係る障害復旧動作の簡略フローチャートを示す。
図１２Ｄは、本発明の好適な実施形態に係る自己回復動作の簡略フローチャートを示す。
図１３および１４は、本発明の好適な実施形態に係る、自己回復機構の一部としてのサーバおよびデータのマイクロリポジトリの再マッピングのブロック図である。
図１５は、本発明の好適な実施形態に係る、チャネル交換網グラフ兼マルチキャストスパンニングツリーである。
図１６は、顧客機器を示す本発明の好適な実施形態に係るネットワークの一部のブロック図である。
図１７および１８は、本発明の好適な実施形態に係る分散チャネルハッシュ実現を示すブロック図である。
図１９および２０Ａは、本発明の好適な実施形態に従って、二次キーを使用してデータのマッピングをいかに実行することができるかを示すブロック図である。
図２０Ｂは、３部および５部構成のストレージならびに２つの異なる可用性レベルの場合のデータストレージユニットＸＤＢの数に対する１秒当たりの演算実行回数による性能および可用性を示すグラフである。
図２１および２２は、本発明の好適な実施形態に従ってプロセス状態をいかに維持することができるかを示すブロック図である。
図２３は、本発明の好適な実施形態に係るプロセス状態の維持のための状態データベースの使用を示すブロック図である。
図２４は、チャネルがグループ毎に切り換えられる、本発明の好適な実施形態を示す簡略図である。

本発明の実施形態は、マルチキャストドメインネットワーキングを使用して分散データリポジトリを構築するための装置および方法を含む。本発明の実施形態のデータリポジトリは、データパーティショニングをコンピューティング資源パーティショニングから切り離すことを含む。そのようなアーキテクチャの利点は、保証された応答性、高可用性、高スケーラビリティ、および動的オンラインスケーラビリティをもたらすことである。無共有アーキテクチャと同様のシステムがもたらされるが、データを一種のグループアドレスであるネットワークチャネルにマッピングすることによって、物理的パーティションの代わりに、仮想パーティショニングが使用される。次いで、交換網アドレス指定管理およびルーティングを使用することによって、ネットワークチャネルはコンピューティング資源に動的にマッピングされる。その結果により、データパーティショニングがコンピューティング資源の割当てから切り離される。データ処理はデータストレージから切断され、提供することのできる仮想チャネルの数は、ネットワークアドレス指定空間のみによって制限される。データ処理資源は自由に再割当てすることができる。

１実施形態では、データを検索するために使用されるアドレス指定空間は、単一のデータレコードに対し複数のアドレスを含み得、一次キー、二次キー、または追加キーのいずれかを使用してデータを突き止めることができる。

下述する実施形態では、「ネットワーク内」データリポジトリアーキテクチャについて記載する。該アーキテクチャは、以下で詳述するように、分散アーキテクチャに勝る「全共有」、「無共有」、および「メモリ内」の利点を組み合わせながら、各ソリューションの欠点を回避する、分散データリポジトリシステムの構築を定義する。該アーキテクチャは、上述した「メモリ内」アーキテクチャの応答性を有する。同時に、「ネットワーク内」アーキテクチャは上述した「全共有」アーキテクチャの対称的負荷均衡およびＮ＋Ｍ高可用性を有するが、システムのスケーラビリティおよび応答性を制限するブロッキング要素は無い。

加えて、本書に記載する「ネットワーク内」アーキテクチャは、上述した「無共有」アーキテクチャの非ブロッキングデータパーティショニング属性を有する。しかし、以下に説明するように、明示的データパーティショニングを行なう必要も、あるいは異なるデータパーティションの間で明示的コンピューティング資源割当てを行なう必要も無く、したがってシステムは、演算素子間の真に高応答性の動的負荷均衡を達成する。

本発明による装置および方法の原理および作用は、図面および付随する説明を参照してより十分に理解されることができる。

本発明の少なくとも１つの実施形態を詳しく説明する前に、本発明は、その適用において、下記の説明において示されるか、または、図面によって例示される構成要素の構成および配置の細部に限定されないことを理解しなければならない。本発明は他の実施形態が可能であり、または、様々な方法で実施または実行されることができる。また、本明細書中で用いられる表現法および用語法は記述のためであって、限定であると見なしてはならないことを理解しなければならない。

ここで、図４を参照すると、本発明の第１の好ましい実施形態の簡略図が示されている。データアクセスシステムは、各々独立にアクセス可能な仮想パーティションに配列されるデータベースユニットと、複数のデータ処理ユニットとを備える。前記仮想パーティション間で前記データ処理ユニットを交換し、それによってデータ処理容量をそれぞれの仮想パーティションに動的に割り当てるためのスイッチングユニットがさらに提供される。より具体的には、図４において、データパーティション４０１．１．．．４０１．Ｍは、チャネル１．．．Ｍ上にマッピングされる。コンピュータノード４０３．１〜４０３．Ｋは、各々メモリを備え、そして格子型のネットワークが設定されるようにチャネルへの交換を介して接続される。

図４は、交換チャネルネットワーキングを使用して仮想パーティションとコンピューティングユニットとの間の動的マッピングを行なうアーキテクチャを示す。この簡略化された事例では、仮想パーティションは複製されず、コンピューティングユニットと仮想パーティションとの間に１対多数の関係が存在し得、各コンピューティングユニットは、１つまたはそれ以上の仮想データパーティションの単一のコピーを格納かつ管理する。

図４に示す分散データリポジトリアーキテクチャでは、データおよび処理能力の編成は、それが非ブロッキングであり、したがってメモリ内の独立読出し／書込みトランザクションのサービス提供の同時並行性が最大になる一方、比較的高レベルの応答性、一貫性、および比較的容易なスケーラビリティが提供されるように行なわれる。

上記の利点は、次のことによって達成される。
１．データパーティショニングをコンピューティング資源パーティショニングから切り離す。その結果、「全共有」零管理スケーラビリティと結合されるように、「無共有」非ブロッキング同時並行性が達成される。

２．メモリ内のデータを管理し、それによって上述した「メモリ内」アーキテクチャを達成する。

データパーティションおよびコンピューティング資源パーティションの切り離しは、交換チャネルネットワーキングを使用し、かつ、データパーティショニングが静的にネットワークチャネルにマッピングされる一方、コンピューティング資源をこれらのネットワーキングチャネルに動的に割り当てることができるように、本書でチャネルと呼ぶ中間ネットワーキング構造を形成することによって行なわれる。したがって、１つまたはそれ以上のチャネルに割り当てられた各コンピューティングサーバは、そのメモリ内でそのチャネルにマッピングされた全てのデータを維持する。

コンピューティングサーバとチャネルとの間のマッピングは１対多数である必要はなく、多数対多数であってもよい。したがって、幾つかのコンピューティングサーバを同一チャネルに割り当てることができ、データパーティションはメモリ内で複製され、同一チャネルに割り当てられた全てのコンピューティングサーバの間で同期化される。

ここで、図５を参照すると、複製を持つコンピューティングパーティションからのデータの切離しを図解するために、図４の実施形態がもう少し詳細に示されている。図４と同一である部分には同一参照番号が付与されており、同一実施形態の理解に必要である場合を除き、それについて再度言及することはしない。交換チャネルネットワーキングは、データパーティションのいずれかを必要に応じて動的にコンピュータノードのいずれかに接続することを可能にする。

図５は、図４と同じ基本的アーキテクチャを有するが、データ複製が提供されるという点において異なる。データ複製は、コンピューティングユニットとデータ複製との間の多数対多数の関係を可能にする。各コンピューティングユニットは１つまたはそれ以上の仮想データパーティションを格納かつ管理し、各データパーティションは例えば３つまたは５つのコンピューティングユニットによって格納かつ管理される。

次の要素は図５の実施形態を構成する。
中間ネットワーキングチャネルを使用し、交換チャネルネットワーキングを通して独立デュアルマッピングを実現することによって、データパーティションをコンピューティングパーティションから切り離す。
ａ．データパーティション４０１．１〜４０１．ｍとベースネットワーキングチャネル１．．．チャネルＭとの１対１の静的マッピング。
ｂ．コンピューティングサーバ４０３．１．．．４０３．ｋとチャネル（チャネル１．．．チャネルＭ）との多数対多数の動的マッピング。

２．チャネル割当てのワイヤ速度応答性および実時間再構成を確保するように、標準パケットネットワーキングを推進するために、ネットワーキングチャネリング方法が提供される。

３．分散データ管理プロトコル、ここではデータアクセスプロトコルまたはＸＤＡＰ。

４．経路制御ネットワーキングのみならず、パーティション化されたインデックステーブルハンドリングを使用するデータインデクシングは、代替的二次インデックスを介して同一データへのワイヤ速度アクセスを確実にする。

図５に示す分散データリポジトリアーキテクチャでは、データおよび処理能力の編成は、それが非ブロッキングとなり、したがって応答性レベル、一貫性、スケーラビリティ、および可用性レベルを損ねることなく、メモリ内の独立読出し／書込みトランザクションのサービス提供の同時並行性が最大になるように行なわれる。

上述した利点は、
データパーティションをコンピューティング資源パーティショニングから切り離し、「無共有」非ブロッキング同時並行性と「全共有」トランスペアレントスケーラビリティとを達成し、ネットワーク越しに複製されたメモリ内のデータパーティショニングを管理し、「メモリ内」応答性および耐障害性を達成する、
ことによって達成される。

本発明のさらなる態様をここで、ほとんどのデータリポジトリに適用可能な階層データパーティショニングの説明として例証する。本発明は、上述したものを含め、それらに限らず、多数のデータ型に適用可能である。データ型の説明に続いて、パブリッシュ−サブスクライブネットワーキングチャネルを使用して、階層データパーティションをいかにしてコンピューティングパーティショニングから切り離すことができるかを説明し、次いで、標準パケットネットワーキングを使用して、そのような「パブリッシュ−サブスクライブ」ネットワーキングチャネルをいかにして実現することができるかを論じる。

チャネルの実現の後に、ワイヤ速度データ同期化、トランザクション完全性、耐障害性、オンラインスケーラビリティ、および自己回復を確実にする、上述したコア分散データ管理プロトコル（ＸＤＡＰ）について記載する。

以下、標準経路制御ネットワーキングのみならず、インデックステーブルパーティショニングハンドリングをも推進するインデクシング方法を説明する。

データパーティショニング階層
ここで、図６を参照すると、ツリー型データ階層６０１が示されている。データリポジトリ内のデータ要素は通常、「部分」関係または全順序関係を表わすツリー状構造の階層にパーティション化される。例えば、リレーショナルデータベースはスキーマ単位で編成される。各スキーマはテーブル単位で編成される。各テーブルは、異なるキー値を有するレコードのリストを有する。

「部分」（⊃）関係は、そのような階層で明確に定義された関係である。上の例では、「音楽ライブラリ」６０３⊃「アルバムデータベース」６０５⊃「ジャズアルバム」６０７⊃「パワー・オブ・スリー」６０９⊃「Ｌｉｍｂｏ．ｍｐ３」６１１である。

別の例のファイルシステムを図７に示す。図７の例は、フォルダの階層として編成されたディレクトリシステム７０１を示す。階層内で、各フォルダは他のフォルダおよび／またはファイルを含む。各ファイルはブロックのリストを含む。

「部分」（⊃）関係は、上記のファイルシステムの例、つまり「ルートディレクトリフォルダ」７０３⊃「プログラムファイルフォルダ」７０５⊃「Ａｄｏｂｅフォルダ」７０７⊃「Ａｃｒｏｂａｔ６．０フォルダ」７０９⊃「ＡｃｒｏＲｄ３２．ｅｘｅファイル」７１１でも明確に定義される。

ここで、図８を参照すると、ツリー構造のさらなる例が示されている。図８において、ディレクトリもまたリストのツリー８０１として構築され、リストにおける各要素はデータレコードまたはデータレコードのリストのいずれかである。

ツリー８０１において、データは階層状に編成され、したがって各データ要素は、データリポジトリ内で、例えば「ＤＮＳディレクトリ」⊃「．ｉｌ」⊃「．ｃｏ．ｉｌ」⊃「．ｘｅｒｏｕｎｄ．ｃｏ．ｉｌ」⊃「ｗｗｗ．ｘｅｒｏｕｎｄ．ｃｏ．ｉｌ」で、一意の「座標」を有する。

データ要素の座標は要素を一意に識別し、したがって常に書込みトランザクションの一部として提供される。多くの場合、特定のデータ座標が読出しトランザクションでも提供される。例えばｗｗｗ．ｘｅｒｏｕｎｄ．ｃｏ．ｉｌドメイン名のＩＰアドレスを解決するために、ディレクトリクエリ内に特定の座標が提供される。しかし、いくつかの読出しクエリは階層のより上位、例えば「．ｃｏ．ｉｌの全ドメイン名」を参照し得る。この場合、クエリは、情報が読み出されるサブツリーを「選択する」。

下述する実施形態は、応答性、データの一貫性、トランザクションの完全性、非常に高いスケーラビリティ、動的なオンラインスケーラビリティ、および高可用性を達成しながら、全ての種類のクエリをサポートする分散データリポジトリの骨格を構成するネットワークチャネルの階層に全てのデータ要素をマッピングする、階層ベースのハッシュ関数を使用して、データリポジトリ内のデータおよび処理資源を編成する方法を教示する。

コンピューティングパーティションからのデータパーティションの切離し
構築された分散型階層ベースのハッシュデータリポジトリは、マルチキャストネットワークチャネルの階層を含むので、様々なクエリを様々なチャネルに経路指定することができ、かつ、他方で、異なるコンピューティングサーバが任意の組のチャネルにサブスクライブして、それらの全てのメッセージを受信することができる。以下に、そのようなパブリッシュ−サブスクライブネットワーキングチャネル機構を実現するために使用することができる様々な標準ネットワーキング技術を列挙する。

ここで、図４に戻ると、チャネル自体の中に、「同一チャネルまたはサブチャネル内」を意味する順序「≧」が定義されている。つまりチャネル１≧チャネル１．１≧チャネル１．１．１である一方、チャネル１．１≧チャネル１．２であり、かつチャネル１．２≧チャネル１．１である。

切離しを図９のフローチャートに示し、それは次の構成要素から構成される。
＊マイクロ（μ）パーティショニング９０３：グローバルデータリポジトリは、各々異なる組のチャネルにサブスクライブされた多くの独立マイクロリポジトリ（μリポジトリ９０５）に静的かつ仮想的にパーティション化される。マイクロリポジトリの数は、数千またはそれ以上とすることさえ可能である。

＊ハッシング９０７：単調階層ベースのハッシュ関数をデータリポジトリ座標に使用して、それらをチャネルにマッピングする。ａ⊃ｂ⇒ｈ（ａ）≧ｈ（ｂ）のとき、ハッシュ関数ｈ（）は単調である。同時並行性が最大になるように、ソリューションは完全ハッシュ関数（つまりターゲットチャネル間の均一分布）を使用する。ハッシュ関数は実際にグローバルデータリポジトリを多くの独立μリポジトリにパーティション化する。

＊複製９０９：各μリポジトリは、同一の独立したコピーの３部（または５部もしくはそれ以上）構成である。同一μリポジトリの全てのコピーは、同一組のチャネルにサブスクライブされる。以下でさらに詳述するように、トランザクションの完全性、データの一貫性、および高可用性を得るために、過半数原理がクエリ結果に使用される。

＊分散およびシャッフル９１１：μリポジトリのコピーは、コンピューティングサーバに統合される。各μリポジトリはコンピューティングサーバ上の単一のプロセス、スレッド、テーブル、またはサブテーブルである。したがって各コンピューティングサーバは、そのμリポジトリのチャネルにサブスクライブされる。μリポジトリは負荷均衡を最大にし、かつ相互依存性およびブロッキングを最小にするように、コンピューティングサーバ間でよく分散され、シャッフルされる。

ここで、図１０Ａを参照すると、サブチャネルに分割された一連のチャネルを示す概念図が示されている。したがって、チャネル１はチャネル１．１およびチャネル１．２に分割される。チャネル１．１は次にサブチャネル１．１．１、１．１．２、および１．１．３．に分割される。

ここで、図１０Ｂを参照すると、チャネルおよびサブチャネルに割り当てられたマイクロリポジトリが示されている。複製およびシャッフル原理を適用する例は、サブチャネルにサブスクライブされた各μリポジトリが、そのチャネルより上位の全てのチャネルレベルにもサブスクライブされることに見ることができる。

ネットワーキングチャネリングパブリッシュ−サブスクライブ法
ネットワーキングチャネルはここでは、各サーバがどのチャネルでもメッセージをパブリッシュつまり送信することができるように、パブリッシュ−サブスクライブ機構として提供される。しかし、チャネルにプレサブスクライブされたサーバだけが、そのチャネルにパブリッシュされるメッセージを読むことができる。いずれのサーバも、いずれかのチャネルに／からいつでも動的にサブスクライブかつ／またはサブスクライブ解除することができる。任意のサーバが多くのチャネルに同時にサブスクライブすることができる。

標準パケットネットワーキングを使用してそのようなネットワーキング「パブリッシュサブスクライブ」チャネルを実現するための幾つかの方法を以下で説明する。

分散データアクセスおよび管理プロトコルＸＤＡＰ
図９に戻ると、「クエリルータ」（またはＸＤＲ−データルータ）と呼ばれる分散コンピューティングコンポーネントで、座標ハッシング８０７が実行される。ここで、図１１を参照すると、クエリルータ１１０１．１．．．１１０１．３を使用するネットワークアーキテクチャが示されている。各クエリルータは複数のクエリを同時に処理する。読出し／書込みクエリ／トランザクションを生成する全てのデータリポジトリクライアントをサポートするためにソリューションで必要なだけ多数のクエリルータが存在し得る。各クライアントは、１つまたはそれ以上の特定のクエリルータに対抗するように事前設定される。クエリルータは、彼のクライアントに対し、それが読出し／書込みクエリを受信し、クエリを実行し、かつ次いでクエリの結果値または状態をクライアントに返送するように、データリポジトリを提示する。

クエリルータは、次の一般的にアルゴリズムを使用してクエリを処理する。
それは、先頭キーまたは二次キーから形成されたクエリの座標を使用して、クエリを正しいチャネルにハッシングし、経路指定する。全てのサーバが任意のチャネルに書き込むことができることに注目されたい。しかし、チャネルにサブスクライブされたサーバだけが、そのメッセージを受信する。読出しトランザクションの処理は、書込み（挿入、更新、削除）トランザクションの処理とは異なる。クエリルータは、単一のクエリを幾つかの読出しトランザクション、書込みトランザクション、およびロッキングアクションに変換することができる。クエリルータは、下述するように、そのようなクエリ実行プランまたはアクセスプランを生成し、次いで各々のそのようなトランザクションを実行する。ロッキングアクションは、一般的に知られるように実行され、データベースドメインで使用される。

読出しトランザクション：先頭キーに基づく読出しトランザクションは１つのフェーズ、「スイッチングフェーズ」で行なわれ、そこで読出し要求は正しいチャネルに切り換えられ、それに続いて、手順はそのチャネルにサブスクライブされているμリポジトリを待ち、それら自体の内部データリポジトリに対して読出しクエリを独立に計算し、それらの結果を要求データルータに返送する。読出しクエリの結果に関する充分な情報をμリポジトリから受信した後、データルータは情報を統合し、クエリを計算し、結果をクライアントに返送する。

二次キーに基づく読出しトランザクションは、スイッチングフェーズの前にルーティングフェーズを持つことによって実行される。ルーティングフェーズは二次キーを一次キーにマッピングすることを含み、次いでそれは上述したようにスイッチングフェーズで使用される。ルーティングフェーズはルータを使用することによって達成することができ、あるいはこれは、正しい二次インデックステーブルに対して読出しトランザクションを実行することによって行なうこともできる。二次インデックステーブルは二次キーをオリジナルテーブルの先頭キーにマッピングする。したがって、インデックステーブルの先頭キーはオリジナルテーブルの二次キーであり、そのようなインデックス読出しトランザクションは、上述した１つのスイッチングフェーズにおける任意の先頭キーに基づくトランザクションと同様に行なわれる。ルーティングフェーズがネットワークルータによって実現される場合には、ＸＤＲは、二次キーを読出しトランザクションが送信される一意のネットワークアドレスにマッピングする、別のハッシュ関数を使用する。ルータはここで、ＸＤＲの観点からだけではなく、二次キーに基づく読出しトランザクションが単一フェーズを必要とするためにも、メッセージを受信してクエリをリダイレクトし、あるいはクエリを正しいチャネルに経路指定する。

書込みトランザクション：書込みトランザクションは、所与のチャネルにサブスクライブされている全てのサーバによって受信される。しかし、書込みトランザクションの分散コミットプロセスは、３フェーズコミットプロトコルを使用して所与のチャネルのメンバの間から選定される特別なコーディネータによって管理される。コーディネータの管理下でひとたび３フェーズコミットが完了すると、コーディネータは書込みトランザクション完了標識をＸＤＲに報告し、それは次いでクライアントに転送される。コーディネータが必要であるのは、異なるソースからの同一データレコードへの同時アクセスを可能にし、しかも同時書込みの事象が試みられた場合にデータ完全性を維持しなければならないからである。

コーディネータの選択に関するさらなる詳細については、後述する過半数ベースのリーダ選定に関する節を参照されたい。

非ブロッキング同時並行処理、順序一貫性、トランザクションの完全性、および耐障害性を達成しながらの書込みクエリおよび読出しクエリの処理について、これから、より詳細に論じる。

書込みトランザクション処理
ここで、図１２Ａを参照すると、書込みトランザクションを示す簡略フローチャートである。書込みトランザクションは、挿入、変更、または削除トランザクションを含む。挿入トランザクションは常に、それを追加する特定データレコードの完全な座標「Ｃ」、つまり先頭キーを指定する。しかし、削除および変更トランザクションは先頭キーを提供しなくてもよい。それらは二次キー値または何らかの他の検索基準を提供することができる。先頭キーが書込みトランザクションの一部として指定されない場合には、ＸＤＲはまず最初に、変更または削除する必要のある全てのレコードを見つけ出す読出しトランザクションを実行する必要があり、次いで入手した先頭キー値により書込みトランザクションを実行する。本書の図１２Ａの説明は、書込みトランザクションのための先頭キーがすでに識別されたことを前提とする。書込み動作が全てのコピーで無事に完了したことを確実にするために、全てのμリポジトリのコピーに３フェーズコミットプロトコルを実行する。コミットプロトコルは、上述の通りコーディネータとなるように選定されたサーバの１つによって調整される。

さらに詳しくは、各チャネルに対し、コーディネータが選定される。コーディネータは任意のトランザクションのコミットを開始する。コーディネータは従属トランザクションをシリアル化する。同時並行読出し、つまり書込みアクセス中に発生する読出しアクセスは一般的に、更新前のレコードのバージョンの使用を完了し、あるいは代替的に、それらは更新後のバージョンを待つ。読出しが更新中に実行された場合、アプリケーションがそのように要求すれば、読出しを失敗させることもできる。また、ひとたび書込みがコミットされ（かつ応答がクエリルータに送信され）ると、新しい読出しは応答として以前のバージョンを受け取らない。

コーディネータは好ましくは単調カウンタを使用して、各チャネルでそれが開始した各トランザクションにマーキングする。３フェーズコミットの第１フェーズは、トランザクションを全ての参加者に送信することである。したがってコーディネータは、トランザクションを全ての参加者に送信する。次のステップは、それらのプレコミットまたはアボート応答を収集することである。原子トランザクションは単一のコーディネータを介して維持され、チャネルのメンバは常に、各トランザクションに関し完全に同期して作業する。したがって、応答は常に同一（３フェーズコミット技術ではプレコミットまたはアボートのいずれか）でなければならない。完全な同期化のために、チャネルメンバは、応答がプレコミットされた（つまりプロトコルフェーズのあるマージングが発生した）ときに、トランザクションを即座に局所的にコミットすることができる。過半数の肯定応答（プレコミットまたはアボート）の受信後、コーディネータは適切な応答をクエリルータに返却することができる。

書込み動作の途中でコーディネータに障害が発生した場合、復旧を確実にするために、全メンバがトランザクション情報を維持する。チャネルメンバの完全な同期性を維持するために、コーディネータは、全メンバが肯定応答するまで、全メンバにトランザクションを再送信し続ける。例えば肯定応答の欠如後に再送信を繰り返す必要性は、チャネルの障害を示唆しており、障害を反映してチャネルを再編成しなければならないかもしれない。トランザクションについて、および何がうまくいかなかったかについて、コンセンサスが得られると、チャネルメンバ全体の多数決によりコンセンサスおよびしたがって復旧を導くことができるので、それを処分することができる。次いでコーディネータは、トランザクションが合意されかつその全ての情報を処分することができることを全メンバに伝える、通常の３フェーズコミットプロトコルの最終コミットメッセージと事実上同様のメッセージを送信することができる。

ここで、複合トランザクション管理は１組の原子トランザクションに分割され、１つのコーディネータがトランザクション全体に関与する一方、他のコーディネータは原子サブトランザクションを取り扱うことができる。原子サブトランザクションの１つまたはそれ以上に障害が発生した場合、複合トランザクションコーディネータは、完了したかもしれない複合組内の他の原子サブトランザクションをロールバックまたは取り消す役割を果たす。

ネットワークメッセージングを低減するため、かつ同一トランザクションの他の部分に関する情報を非実時間で伝達する必要性のため、「他の部分」情報を他のトランザクションのピギーバックとして送信することもできる。より正確には、各々の通常のトランザクションメッセージは、そのトランザクションより前の、またはそのトランザクションを含め、全てのトランザクションがチャネルによってすでに完全に吸収された最大トランザクションのＩＤを含む。

そのようなプロトコルは、データベースの原子性（Ａｔｏｍｉｃｉｔｙ）、一貫性（Ｃｏｎｓｉｓｔｅｎｃｙ）、分離（Ｉｓｏｌａｔｉｏｎ）、および耐久性（Ｄｕｒａｂｉｌｉｔｙ）、つまりＡＣＩＤ特性を維持しながら、コーディネータ自体を含め、チャネルのメンバのマイノリティの障害に耐えることができる。データベースシステムのＡＣＩＤ特性は、データの安全な共有を可能にする。これらのＡＣＩＤ特性無しには、コンピュータシステムを使用して製品を購入する等の日常的な出来事は困難であり、誤りの潜在的可能性が大きくなるであろう。したがって、よくある出来事で、２人以上の人間が所与のコンピュータ化カタログから同じサイズおよび色のセーターを同時に購入しようとした場合に、ＡＣＩＤ特性は、商人がこれらのセーター購入トランザクションを相互に重複させないことを可能にし、商人の誤った在庫および勘定収支を防ぐ。上記は書込みアクセスにつながり、上記プロトコルは、書込み動作を制御し続けることができるように、総合スーパバイザがチャネル全体を管理することを確実にする。

上記プロトコルの基礎を成す効果は、メンバの大多数が所与のトランザクションを肯定応答した場合に、オブジェクトの以前のバージョンはこれらの機械から除去されているので、その後の読出しは以前のバージョンを含まなくなることである。その後の読出しは新しいバージョンを有するか、あるいはタイムアウトする。復旧すると、書込みトランザクションは全てのメンバに対して実現されているか、あるいは元の大多数の少なくとも１メンバが依然としてトランザクション内容を有し、それが最終的に現在のメンバで実現されることを確実にすることができる。ひとたびそれが発生すると、読出しはもはやタイムアウトせず、それらはオブジェクトの新しいバージョンを含む。

データレコードの書込みに成功するたびに、現在のレコードの通し書込み番号である一意の「認証」が生成され、プロトコルが正常に動作する限り、レコードの最後の値の認証は全てのコピーに対して同一であることを期待することができる。この認証は、読出しプロセスの一部として値検証に使用される。

読出し処理
クエリの読出し処理は、上記の書込みクエリと同様に、正しいレコードを見つけ出し、次いで求められている情報を出力する必要がある。想起される通り、同一データレコードが２つ以上の場所に存在する。

ここで、データレコードは一般的に、そこからレコードを取得することのできる第１の検索可能フィールドである先頭キー付きで格納される。それは他の検索可能フィールドを持つこともできる。データベースは、先頭キーの使用をハッシングしてレコードの直接アドレス指定を行なうことができるように、構成することが好ましい。

読出しクエリがデータ要素の先頭キーを含む場合、
１．クエリをハッシングして、ＸＤＲによって正しいチャネルに切り換えることができる。

２．レコードのバージョンを有する各ＸＤＢが、チャネルからクエリを受信する。

３．レコードの内容および最後の書込み動作を示す認証を含め、結果がＸＤＢによって要求ＸＤＲに返される。

４．ＸＤＲが充分な（過半数で）一貫した結果、つまり同一値および同一認証を受信した後、受信した内容が結果値としてクライアントに返送される。

上述の通り、ここで、２つ以上のフィールドが検索可能である。したがって、特定の番号を見つけ出すために主として名前によって検察するように意図された電話ディレクトリの場合、名前フィールドは一次キーを構成する。しかし、ディレクトリは、必要な場合、逆に探索することも可能であり、名前を探すために番号を入力することができる。この場合、クエリは非先頭キーを含む。

読出しクエリがデータ要素のそのような非先頭キー（それは一次または二次インデックスであり得る）を含む場合には、読出しクエリは、一次キーを提供するために、最初にインデックステーブルと照合される。上記の例では、電話番号は一意であり、したがって単一の結果を導くが、多くのそのようなキーは言うまでもなく一意であるとは限らず、２つ以上の結果が取得されるかもしれない。次いでクエリ処理は、上述の通り、単数または複数の先頭キーを使用して単数または複数のデータ要素を突き止めるように進行する。二次インデクシングについては以下でさらに詳述する。一次キーが取得された場合、それは正しいチャネルを導く。

ここで、検索クエリはキーを全く含まないこともある。読出しクエリがデータ要素の一次キーを含まず、それに対する二次インデクシングも含まない（つまりそれがフラット「検索」クエリである）場合、それは検索を行なう階層の１つまたはそれ以上のレベルを「選択」しなければならない（デフォルトでは全部検索される。それは、ルートディレクトリが選択されていることを意味する）。図６のディレクトリ構造に対して行なわれる、キーではなくむしろ条件を有するクエリの１例は次の通りである。
１．１０分より長いジャズトラックを見つけだす（「ジャズアルバム」が選択される）。
２．２５歳以下のアーティストのアルバムを見つけ出す（「ジャズアルバム」および「アーティストデータベース」の結合クエリが選択される）。

図６の階層をチャネルの階層に変換するための階層ハッシュ関数マップを図１２Ｂに示す。図１２のマッピングでは、図６の構造の全てのデータベースおよびテーブルがｓｕｐｅｒチャネル、つまりＳｕｐｅｒチャネル１、Ｓｕｐｅｒチャネル２等にマッピングされ、所与のテーブル内の全てのデータ要素は、１組のサブチャネルにマッピングされる。例えば、「ジャズアルバム」テーブルはＳｕｐｐｅｒチャネル２．１にマッピングされ、全てのジャズレコードエントリは１組のチャネル２．１．ｘにハッシングされる。

特定のジャズレコードを指す読出しクエリは、２．１．ｘチャネルの１つに直接マッピングされる。次いで、データベース内に該レコードが存在する場合には、そのチャネルにサブスクライブされている全てのμリポジトリコピーに詳細が存在する。

「ジャズアルバム」テーブルを「選択」する読出しクエリは、Ｓｕｐｅｒチャネル２．１にマッピングされる。探索クエリを受信した各μリポジトリは、それ自体の内部リポジトリに対してクエリを独立に実行し、取得された結果を返す。クエリルータは全ての個別μリポジトリ結果のコピーに過半数の原理を適用し、次いで全ての結果をマージしてクライアントに返送する。

結合データクエリは、一連の原子「選択」トランザクションによって組み合わされる複合トランザクションとして実現される。別々のクエリは一度に１つずつ実行され、複合トランザクションは、結合データクエリにどのような論理が要求されるかに関わらず、１つの選択の結果が次の選択で行なわれるクエリに影響することを確実にするように構成される。

復旧および自己回復
ここで、図１２Ｃを参照すると、それは自己回復の手順を示す簡略図である。上述したシステムは任意の単一の障害に耐えるので、任意の単一の障害ではシステムの可用性および機能性は損なわれない。システムの耐障害性のレベルは、各データレコードのより多数のμリポジトリコピーを使用することによって構成することができる。しかし、ひとたび障害が発生すると、システムはその「耐障害性」レベルの一部を失い、それ以上の障害を切り抜けることができないかもしれない。したがって、要求される耐障害性レベルを自動的に復活させる、「自己回復」と呼ばれる「耐障害性復旧」機構について、これから論じる。

以下で、最初の障害から設定可能な時間量後にトリガされる、耐障害性復旧のための完全に対称的かつ分散型の自己回復機構について記載する。

μリポジトリの障害は、同じチャネルのそのピアによって自動的に認識される。

μリポジトリ障害の検出の後に、次の復旧プロセスが実現される。
１．μリポジトリが属するチャネルの他のメンバは、そのチャネルのリポジトリの１つに障害があることを認識する。チャネルのコーディネータが障害発生体ではない場合には、コーディネータは、欠落したμリポジトリコピーをホストするために、チャネルに新しいサーバを追加することによって、チャネルのメンバの組の変更を開始する。新しく再ホストされたコピーは、チャネルコーディネータによってチャネルと再同期化される。チャネルにおけるその後の書込みトランザクションは、図１２Ｄに記載するように、この変更を反映する。

２．代替的に、障害のあるサーバがチャネルのコーディネータである場合には、チャネルの残りのサーバが、図１２Ｄで上記１に記載したように、チャネルへのサーバの追加を調整しかつチャネルデータの追加を調整する、チャネル用の新しいコーディネータを選定する。

図１２Ｃに記載するように、サーバが故障すると、障害サーバにサブスクライブしている全てのチャネルで復旧プロセスを行なう必要がある。これらのチャネルの幾つかにおいて、障害サーバはコーディネータであった。したがって、復旧プロセスの一部として、チャネルに新しいコーディネータを選定する必要がある。全ての復旧チャネルの復旧プロセスを調整するために、全体的「自己回復」コーディネータが選定され、プレコンパイルされた復旧プランを使用することによって、または必要ならば新しい復旧プランを生成することによって、復旧プロセスを調整する。そのような復旧プランは、図１４に記載するように、障害サーバにホストされていた各μリポジトリコピーに対し、残存サーバのうちのどれにそれを効果的に退避させるべきかを指定する、「復旧マトリックス」と考えることができる。このシステムを使用して、障害サーバの損失がそれにホストされていたμリポジトリのデータの可用性に対して与える影響が最小限となるように、データは再均衡化される。

ここで、図１３を参照すると、それは７つのカラムＢ１．．．Ｂ７が７つのサーバを表わす図表である。サーバはそれらの間に３５のチャネルＣ１．．．Ｃ３５をホストする。各サーバは、塗りつぶされた欄によって表わされる１５のチャネルにサブスクライブされており、各サブスクリプションはホストされているμリポジトリを表わす。したがって、図示するように、７つのサーバは各々１５のμリポジトリをホストしている。各μリポジトリは３回コピーされ、３５のベースμリポジトリの３倍の全部で１０５のコピーができ、それらが３５のチャネルにマッピングされる。Ｂ２とＣ１１との交差部は塗りつぶされており、サーバ２がμリポジトリ１１のコピーをホストしており、したがってチャネル１１にもサブスクライブされていることを意味する。

ここで、図１４を参照すると、それは、例えばサーバＮｏ．３の障害を補償するために、図１３の構造をいかに変化させることができるかを示す。サーバＢ３は故障しているが、黒く塗りつぶされたサーバ３の全てのリポジトリは、他の２つの場所に存在する。復旧プランで、サーバ７を例に挙げると、それは緊急事態のチャネルから「サーバ３ダウン」緊急信号を受信し、次いでそれは３つの新しいμリポジトリ複写プロセスを開始して、チャネル１、３、および４にあるリポジトリを複写し、Ｂ３／Ｃ１、Ｂ３／Ｃ２、およびＢ３／Ｃ４で失われたマイクロリポジトリを複写する。内容は、これらのチャネルにサブスクライブされる他の２つのコピーから複製される。同様にサーバ６はチャネル６、８、および１０の内容を複写する。サーバ５はチャネル１１、１５、および１８の内容を複写する。サーバ４はチャネル１９、２２、および２６の内容を複写し、次いでサーバ２および１はそれらの間でチャネル３０ないし３３を共有する。複写されたリポジトリは、より濃い塗りつぶしで示される。

チャネルの実現
上述の通り、チャネルは階層ハッシング図表を実現する。チャネルは、単純化のために、μリポジトリ間の共有メディアと考えることができる。しかし、一般的に、共有メディアは、リポジトリを追加したときにあまりよく対応されない。これは、密度が増加したときに、共有メディアが全てのリポジトリに対し処理圧力を増大するからである。

最も効率的なネットワーキングアーキテクチャは、したがって、相互接続ノードのグラフを開く交換インフラストラクチャ、およびμリポジトリを葉として保持する最小マルチキャストスパンニングツリーを通して実現される。

ここで、図１５を参照すると、マルチキャストスパンニングツリーを表わすチャネル交換網グラフの略図である。

アプリケーション転送ノードを有するアプリケーション層交換網を定義することができる。転送ノードは、ＤＨＴ（分散ハッシュテーブル）実現のランドマークとしても知られる。物理層、リンク層、またはネットワーク層で標準ネットワーク技術のアドレス空間にマッピングするチャネルハッシュ関数を使用することが効率的である。そのような方法は、市販の標準的ネットワーキング機器を介して交換ハッシュグラフを実現することを可能にする。そのようなチャネルハッシュマップは、チャネルの実現のための計算層の折畳みを可能にし、結果的にチャネル内の分散交換ハッシングのワイヤ速度処理を達成することができる。したがって、そのようなハッシュマップの使用は、ハッシュ図表の効率的で高速で費用効率が高くかつスケーラビリティの高い実現を可能にする。

チャネルの標準ベースの実現
ハッシュ階層を維持することができる標準ベースのアドレス空間の例は、以下を含む。
＊ ＩＥＴＦ ＩＰ Ｖ４またはＶ６
＊ ＡＴＭＦ ＡＴＭ ＶＣＩ ＶＰＩ
＊ ＩＥＥＥ８０２．Ｄ Ｅｔｈｅｒｎｅｔ（登録商標） ｄｏｔ１ＱｉｎＱ ＶＬＡＮ
＊ ＩＴＵＴ Ｅ．１６４

標準マルチキャストチャネルインライン登録／サブスクリプションプロトコルをもサポートする標準ネットワーキング環境は、例えば以下を含む。
＊ ＩＰのためのＩＧＭＰ
＊ ＶＬＡＮのためのＧＡＲＰ
＊ ＡＴＭのためのＵＮＩ−ＮＮＩシグナリング

ＩＥＥＥ ＭＡＣアドレス等の非階層アドレス空間を選択し、マルチレイヤサブネットネットワークを構成して、チャネルハッシュ図表を実現することも可能である。標準ハードウェアによってワイヤ速度処理をサポートし、かつ汎用交換網インフラストラクチャ内に容易にカプセル化もされる、効率的な実現の例として、汎用公衆ＭＰＬＳバックボーン上でＭａｒｔｉｎｉまたは同様のトンネルを介してカプセル化されるＱ ＶＬＡＮにおけるＩＥＥＥ ｄｏｔ１Ｑがある。それを代替的に汎用公衆ＡＴＭバックボーン上でＬＡＮＥ／ＭＰＯＡを介してカプセル化して、マルチサイト実現を提供することができる。

ここで、図１６を参照すると、Ｐスイッチ（Ｐ）がプロバイダエッジ（ＰＥ）機器につながり、それが次に顧客エッジ（ＣＥ）機器につながるネットワーク構成を示す簡略図が示されている。顧客エッジ（ＣＥ）機器はＩＥＥＥ ８０２ ｄｏｔ１Ｑ ＶＬＡＮを実現し、データストレージを保持する。ＣＰＥポートおよびタグに従って、ＣＥは、公衆／専用サービスプロバイダエッジ（ＰＥ）機器へのＱｉｎＱダブルタグ付きアップリンクのトラフィックをハッシングする。ＰＥはポートおよびＶＬＡＮによるＣＥアップリンクトラフィックをＭＰＬＳでトンネルにハッシングする。トンネルはＭＰＬＳの内部ＩＰアドレス空間にハッシングされ、ルート記述子に従ってこれらはＭＰＬＳのタギングスキームにハッシングされ、プロバイダ（Ｐ）コアスイッチに転送される。Ｐコアスイッチはトラフィックをタグに従って直接またはさらなるハッシングを通して、分散チャネルの実現を共有する全てのサイトに適合するように、ＤＷＤＭ周波数、ＴＤＭタイムスロット、または他のトランスポート機構にハッシングする。標準ネットワーク技術に上述した方法を使用することにより、システムはネットワーク技術内で継承ハッシングを利用することが可能になる。したがって、ＶＬＡＮタグ、ＩＰアドレス、タグスイッチング、時分割または波長分割多重化を使用して、ワイヤ速度で、かつ全ワイヤ容量で、データに直接ハッシュデータキーを提供することができる。

分散ハッシュフローの実現例は次の通りである。
ＣＰＥおよびＣＥストレージエリアの分散ハッシュフロー：
データキー → チャネル → ＶＬＡＮタグ → タグ＋ポート → スーパタグ．タグ＋アップリンクポート
ＰＥおよびＰ公衆エリアの分散ハッシュフロー：
アップリンクポート＋ＶＬＡＮ → トンネルＩＤ → ＬＳＰ ＩＰ接続 → 内部タグ →外部タグ
光伝送基底ハッシュフロー：
外部タグ＋ポート → 光波長（ＷＤＭ）または／および光タイムスロット（ＳＯＮＥＴ）

さらなる詳細については、下述する特定のチャネルの実現に関する節を参照されたい。

ここで、図１７を参照すると、様々なハッシュ段階で無限大サイズの高速ストレージネットワークにどのようにチャネル分散ハッシュテーブルを実現するかを示す。図１７は分散ディレクトリの実現を示す。分散ディレクトリの実現の場合、クライアントクエリプロトコルはＬＤＡＰ（軽量ディレクトリアクセスプロトコル）である。

さらに図１８を参照すると、本発明の好適な実施形態に係るネットワークレイアウトのチャネルハッシュ実現が図示されている。図１８の実現は、顧客エッジ機器による中央のネットワークリングを示す。中央のリングの周囲にデータベースＸＤＢおよびクエリ定式化またはスイッチングユニットＸＤＲがある。

ＶＬａｎ技術およびＧＶＲＰ登録プロトコルを使用して、アクセスポイントとストレージ要素ＸＤＢとの間の分散データベース通信を実現する実現について説明する。

ＧＶＲＰベースのチャネルの実現
ここで説明する、パブリッシュ−サブスクライブネットワークチャネルを実現するための方法は、非常に効率的なチャネルの実現のために、ＶＬＡＮ技術およびＧＶＲＰダイナミック登録技術を使用する。

分散データベースシステムは２種類の要素、アクセス要素ＸＤＲおよびデータストレージ要素ＸＤＢから構成される。要素間の通信は、上述の通り、チャネルを介する。各チャネルは、データベースに格納されたデータの一種の部分集合を表わす。各チャネルを構成するデータストレージ要素の集合は、様々な理由で経時変化することがある。アクセス要素とチャネルを構成する実際のデータストレージ要素との間のチャネル接続性を維持することは、非常に重要である。データストレージ要素はまた、原子コミット動作を実行するために、同じチャネルを使用してそれらの間でも通信する。データストレージ要素がそれらの間で通信するときに、通信のために選択されるチャネルは、データ自体からも推断される。

この方法の強みは、チャネルに送信されるデータが送信側から１回しか送信されないことである。次いで、メッセージが全ての宛先に到達することを確実にするために、ネットワークが必要最小限度にメッセージを複製して、データは全てのチャネルメンバに到達する。

提示した方法は、次の構成ブロックを含む。
１．システム内の各論理チャネルは、ＩＥＥＥ８０２．１ｑ ＶＬＡＮ技術を使用するＶＬＡＮによって物理的に実現される。

２．ストレージ要素は、チャネルのデータの受信器である。

ａ．ストレージ要素は、適切なＶＬＡＮのためのＧＶＲＰ登録メッセージを周期的に送信することによって、受信器としてチャネルにエンロールする。

ｂ．ストレージ要素を複数のＶＬＡＮにエンロールさせるために、一般的にそれらをトランクポートとしてイーサネット（登録商標）スイッチに接続する必要がある。

ｃ．ストレージ要素はまた、チャネル上のデータを他のチャネルメンバに送信することもできる。それらは、チャネルタグ付きのブロードキャストメッセージを送信することによってそうする。それらは適切なＶＬＡＮに対して登録しているだけであるので、これは他のストレージ要素に到達するだけである。

３．アクセスポイントはチャネルへのデータの送信器である。

ａ．それらがデータを複数のチャネルに送信することを可能にするために、それらはＩＥＥＥ８０２．１ｑ ＶＬＡＮをタギングしたブロードキャストメッセージを送信する。

ｂ．アクセスポイントにタグ付きパケットを発生させるために、一般的にそれらをトランクポートとしてイーサネット（登録商標）スイッチに接続する必要がある。

ｃ．アクセスポイントはチャネル自体上のデータを受信しない。したがって、それらはチャネルにエンロールすべきではない。それらはＧＶＲＰシグナリングを実行する必要が無い。

４．要素が接続されるイーサネット（登録商標）スイッチは、ＶＬＡＮタグおよびＧＶＲＰシグナリングをサポートする必要がある。効率性のために、トランクポートの着信データは、該ポートが受信者ではない場合、ＶＬＡＮタグが付けられる。さもなければ、チャネル上の全ての送信データをアクセスポイントでフィルタリングしなければならなくなるので、これは該ソリューションの効率の要素である。

５．データストレージ要素からアクセスポイントに送信される応答メッセージは、標準ＩＰメッセージまたは標準イーサネット（登録商標）ユニキャストであり得る。

今日、ＶＬＡＮタグ付きパケットをＷＡＮネットワーク上で仮想ＬＡＮにより送信するためのソリューションがある。この目的のために幾つかの提案が、ＩＥＴＦ組織内で草案化されてきた。Ｃｉｓｃｏ等の大手製造者のものを含め、幾つか実現されているものもある。したがって、データベースアクセスポイントとデータストレージ要素との間の通信チャネルとして低待ち時間分散ハッシュテーブルを実現する方法の基礎として、標準ＶＬＡＮおよびＧＶＲＰ技術を使用することが可能である。そうすると、データ通信は、データ自体の関数となる（つまりデータ要素をハッシングすることによって通信が選択される）。

この方法は、チャネル上の複数の受信者向けに意図されたメッセージが送信者によって単一のメッセージとして送信されるので、生成されるメッセージの数において効率的である。メッセージは、全ての宛先に実際に到達するために必要な最小限の量だけ複製される。

ＩＧＭＰスヌーピングに基づくチャネルの実現
ここに記載する方法は、以下でさらに詳述するように、非常に効率的なチャネルの実現のために、ＩＧＭＰプロトコルおよびＩＧＭＰスヌーピングの広範な実現を使用する。

本方法の強みは、チャネルに送信されるデータが送信側から１回しか送信されないことである。次いで、メッセージが全ての宛先に到達することを確実にするために、ネットワークが必要最小限度にメッセージを複製して、データは全てのチャネルメンバに到達する。

本実施形態の方法は、次の構成ブロックを含む。
１．システム内の各論理チャネルは、専用ＩＰマルチキャストアドレスを使用して実現される。

２．ＩＰマルチキャストメッセージは一般的に、スイッチに複数の受信者がいるかもしれないので、イーサネット（登録商標）ブロードキャストメッセージを使用してイーサネット（登録商標）スイッチ内で送信される。最新イーサネット（登録商標）スイッチはしばしば、ＩＧＭＰスヌーピングとして知られる技術を使用して、パケット内をより深く調べかつＩＰマルチキャストアドレスを使用することによって、そのようなパケットを全てのスイッチポートに同報通信することを回避する。またスイッチ上のＩＧＭＰプロトコル通信を監視することによっても、スイッチは、ＩＰパケットがどのポートに関連しているかを知ることができる。この幅広く使用される技術をＩＧＭＰスヌーピングと呼ぶ。ここに示唆する方法は、この最適化を取り入れたスイッチと共に使用したときに、効率が著しく向上する。

３．ストレージ要素はチャネル上のデータの受信器である。

ａ．ストレージ要素は、ＩＧＭＰプロトコルを使用して適切なＩＰマルチキャストアドレスのデータの受信者となることによって、受信器としてチャネルにエンロールする。

ｂ．ストレージ要素はチャネル上のデータを他のチャネルメンバに送信することもできる。それらは、チャネルに関連付けられるマルチキャストアドレスにＩＰメッセージを送信することによってそうする。これは、チャネルに関連付けられる他のストレージ要素だけがこのマルチキャストアドレスを受信するように登録しているので、それらにだけ到達する。

４．アクセスポイントはチャネルへのデータの送信器である。

ｃ．データは、宛先アドレスをチャネルに関連付けられるマルチキャストアドレスに設定して、ＩＰメッセージを使用してチャネル上で送信される。

ｄ．アクセスポイントはチャネル自体上のデータを受信しない。したがって、それらはいずれのチャネルにもエンロールしない。それらはＩＧＭＰシグナリングを実行する必要が無い。

５．ソリューションの効率は、ＩＧＭＰスヌーピングを使用するイーサネット（登録商標）スイッチを使用することによって、著しく改善される。

６．データストレージ要素からアクセスポイントに送信される応答メッセージは、標準ＩＰメッセージまたは標準イーサネット（登録商標）ユニキャストであり得る。

７．ＩＧＭＰはＷＡＮリンク上のその横断が効率的である。受信者へのルートまたは経路が分岐するときにだけ、パケットが複製される。

したがって、通信がデータ自体の関数であり（つまり通信がデータ要素のハッシングによって選択され）、データベースアクセスポイントとデータストレージ要素との間の通信チャネルとして使用される低待ち時間分散ハッシュテーブルを実現する方法の基礎として、標準ＩＧＭＰ技術を使用することが可能である。

この方法は、イーサネット（登録商標）スイッチがＩＧＭＰスヌーピング能力を持つときに、いっそう効率的になる。チャネル上の複数の受信者用に意図されたメッセージは、送信者によって単一のメッセージとして送信されるので、生成されるメッセージの数は最小限である。ネットワーキングハードウェアは、全ての受信者に到達するために必要な最小限のポイントでメッセージを複製するだけである。

イーサネット（登録商標）ユニキャストに基づくチャネルの実現
ここに記載する方法は、通信チャネルにイーサネット（登録商標）（ユニキャスト）通信を使用する。

本発明の方法は、イーサネット（登録商標）ユニキャストメッセージの使用に基づく。すなわち、チャネル内の通信は、ユニキャストメッセージを使用して行なわれる。イーサネット（登録商標）ユニキャスト送信器は、送信器自体がチャネルのメンバであるか否かに関係なく、メッセージの発信元である。チャネル向け意図された各メッセージは、イーサネット（登録商標）宛先アドレスとしてメンバのＭＡＣアドレスを使用して各メンバにユニキャストされるので、チャネルの全てのメンバに対して複製される。したがって、各チャネルのＭＡＣアドレスの会員リストを維持するための機構が必要である。本発明の方法は、チャネルと通信する各要素に、それがチャネルのメンバであるか否かに関係なく、それ自体のＭＡＣアドレスの会員リストを維持させることを含む。これらのリストは動的に更新され、通信障害は会員リストの更新を促す。提示する方法のチャネルメンバシップ解決プロトコル（ｃｈａｎｎｅｌ ｍｅｍｂｅｒｓｈｉｐ ｒｅｓｏｌｕｔｉｏｎ ｐｒｏｔｏｃｏｌ）は、一時的マッピングキャッシュが２つのネットワークアドレスの間に維持されるという意味で、周知のＡＲＰプロトコルとの実質的な類似性を持つ。主な相違は、ＡＲＰプロトコルがＩＰアドレスとＭＡＣアドレスとの間の１対１のマッピングを維持する一方、提示する方法が単一のチャネルアドレスを幾つかのＭＡＣアドレスに変換することである。

各要素は、チャネル対ＭＡＣアドレス情報のそれ自体のキャッシュを維持する。次いでキャッシュは、メッセージをチャネルに送信しようとするときに、要素によってアクセスされる。古い情報はキャッシュから除去される。キャッシュ内の情報が不充分である場合、必要な情報を得るためにチャネル解決プロトコル（ｃｈａｎｎｅｌ ｒｅｓｏｌｕｔｉｏｎ ｐｒｏｔｏｃｏｌ）が使用される。そのメッセージについては下述する。ターゲットの数が一種の機能的最小値を下回る場合、情報は不充分であるとみなされる。上述したデータベースの場合、最小値はチャネルメンバの過半数である。また、要素がチャネルでメッセージを生成するが、古い情報のキャッシュ期限除去時間タイムアウトより短いタイムフレーム内に充分な応答を受信しない場合、要素は関連チャネル情報を明示的にリフレッシュすることができる。

イーサネット（登録商標）ユニキャストに基づくチャネルの実現に使用されるメッセージ
以下のメッセージは、チャネル解決プロトコル（以下、ＣＲＰ）として知られる、提示する方法のチャネルメンバシッププロトコルで使用される。

１．ＣＲＰ要求メッセージは、ＭＡＣアドレスを要求者に送信するように１つまたはそれ以上のチャネルのメンバに要求するために使用される、イーサネット（登録商標）ブロードキャストメッセージである。要求者はまた、各チャネルに関するそれ自体の状態を以下のオプションによって示す。
ａ．要求者は自らをチャネルのメンバとみなしていない。
ｂ．要求者は、チャネル（データストレージ要素の１つの）通常のメンバである。
ｃ．要求者はチャネルのコーディネータである。これは、それが現在、チャネル内の原子コミット手順を調整する役割を果たす要素であることを意味する。本書の別の場所におけるコーディネータに関する記載を参照されたい。

２．ＣＲＰ応答メッセージは、ＣＲＰ要求メッセージに応答してチャネルメンバから送信されるイーサネット（登録商標）ユニキャストメッセージである。該応答メッセージは、チャネル上の各要素の役割をはじめ、応答要素が有するチャネルに関する情報を含む。該応答メッセージはチャネルのリストを含む。各チャネルに対し、メンバのＭＡＣアドレスのリストおよびそのメンバがチャネルで有する役割が存在し、つまり、それがチャネルの通常のメンバであるか、それともチャネルの現在のコーディネータである。
ａ．一般的に、チャネルのコーディネータはチャネルの全メンバを知っている。
ｂ．一般的に、通常のメンバはそれ自体しか知らない。
ｃ．ここでユニキャストメッセージに代替するものは、イーサネット（登録商標）ブロードキャストメッセージを使用してメッセージを同報通信することである。利点は、情報が他の要素にも関係し、システム内の要求の全体数が低減されることである。欠点は、ブロードキャストが他の要素とは無関係であり得、ネットワークの過度のフラッディングが生じることである。

３．周期的に、ストレージ要素は、それらのチャネルメンバシップ全体の状態情報を含むイーサネット（登録商標）ブロードキャストメッセージを送信することによって同報通信される。そのようなブロードキャストメッセージは、ＣＲＰ応答と同じ内部構造を有する。

イーサネット（登録商標）ユニキャストの拡張に基づくチャネルの実現
１．同じ方法を、小さい変更を加えて使用することができる、例えば他のレイヤ２技術を非信頼性（または信頼性）ブロードキャストおよびユニキャストメッセージング、例えばインフィニバンドと共に使用する。

２．イーサネット（登録商標）ユニキャストをＩＰ通信に（生ＩＰとして、またはＵＤＰパケットとして）置換することによって、同じ方法をＩＰ技術に適応させることができる。加えて、イーサネット（登録商標）ブロードキャストを、全てのストレージ要素が記載されているＩＰマルチキャストに置換することが賢明である。

したがって、データベースアクセスポイントとデータストレージ要素との間の通信チャネルとして使用するために低待ち時間分散ハッシュテーブルを実現するための方法として、広く利用可能なイーサネット（登録商標）ユニキャスト通信を使用することが可能である。ハッシングは、通信をデータ自体の関数とすることを可能にする。つまり、通信はデータ要素のハッシングによって選択される。

上に説明した通り、データを損ねることなく、複数の読出し動作を略同時に実行することができる。しかし、書込み動作は相互に干渉することがあり得る。

ＸＤＡＰプロトコルで使用される過半数に基づくリーダ選定プロトコル
以下で、書込みをベースとする動作の意思決定制御をもたらす主導処理ユニットを選択することができるように、分散非同期ネットワークにおける過半数ベースのリーダ選定の実施形態について記載する。

今まで、分散システムにおける様々な種類のノードおよびリンクの障害に耐えるプロトコルに関し、目覚しい研究が行なわれてきた。この分野の最新の論文として、次のようなものがある。

Ｌｅａｄｅｒ Ｅｌｅｃｔｉｏｎ ｉｎ ｔｈｅ Ｐｒｅｓｅｎｃｅ ｏｆ Ｌｉｎｋ Ｆａｉｌｕｒｅｓ，Ｇｕｒｄｉｐ Ｓｉｎｇｈ，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｓｔｅｍｓ ７（３），Ｍａｒｃｈ １９９６

Ｌｅａｄｅｒ Ｅｌｅｃｔｉｏｎ ｉｎ Ａｓｙｎｃｈｒｏｎｏｕｓ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｓｔｅｍｓ，Ｓｃｏｔｔ Ｄ． Ｓｔｏｌｌｅｒ，Ｔｅｃｈｎｉｃａｌ Ｐａｐｅｒ，Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ Ｄｅｐａｒｔｍｅｎｔ，Ｉｎｄｉａｎａ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｌｏｏｍｉｎｇｔｏｎ，ＩＮ，ＵＳＡ，Ｍａｒｃｈ ９，２０００

並行して、原子コミットを目的とするグループ意思決定のための頑健なプロトコルに関し、目覚しい研究が過去に行なわれている。優れた要約を次の文献に見ることができる。

Ｃｏｎｓｉｓｔｅｎｃｙ ａｎｄ Ｈｉｇｈ Ａｖａｉｌａｂｉｌｉｔｙ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｄｉｓｓｅｍｉｎａｔｉｏｎ ｉｎ Ｍｕｌｔｉ−Ｐｒｏｃｅｓｓｏｒ Ｎｅｔｗｏｒｋｓ（博士論文）−Ｃｈａｐｔｅｒ ８，Ｉｄｉｔ Ｋｅｉｄａｒ（１９９８年イスラエル国ヘブライ大学に提出）

本発明者らの知る限りでは、科学界は、リーダ選定の問題および分散コンピューティング領域における原子コミットの問題を単一の文脈内で捉えてこなかった。同時に、ほとんどの原子コミットアルゴリズムで、コーディネータが要求される。コーディネータは一般的に、リーダ選定アルゴリズムを使用してグループによって選択される。リンクおよびコンポーネントの障害に耐える実際の分散コンピューティング環境の脈絡内で、２つの領域の分離は、成功裏に完結する別々のソリューションの成功が一貫性を欠く状況を導いている。換言すると、不合理にも、現行の技術では、障害のパターンおよび選択されるアルゴリズムから、原子コミットを調整できないリーダが選定されることがあるという状況が存在する。また、不合理にも、現行の技術では、障害のパターンおよび選択されるアルゴリズムから、原子コミットを首尾よく調整することができるノードがあるにも拘らず、リーダが選定されないという状況が存在し得る。

先行技術の上記欠点を克服するために、本書で教示するリーダ選定は、過半数に基づく３フェーズ原子コミットに強固に結合される。したがって、リーダ選定プロセスおよびしたがって過半数に基づく３フェーズ原子コミットの結果の一貫性を欠く成否を防止することが可能である。

本発明のソリューションは、ＩＭＳレディ型のデータベースを生成する希望の直接的な結果である。本発明のソリューションは、様々な種類の幾つかの障害に耐えることのできる分散データベースソリューションを含むので、何百万ものサブスクライバの使用に意図されたＩＭＳ準拠通信網の展開によって課せられる、データベースの保証された待ち時間、高スループット、および連続的可用性の要件を満たす１つの方法を提供する。幾つかの障害に耐える能力の一部は、厳しい障害状況で原子コミットを実行する能力を含む。原子コミットを実行するために、リーダ選定および原子コミットアルゴリズム自体の両方が、厳しい障害状況で成功することができることが好ましい。リーダ選定と原子コミットアルゴリズムとの固い結合は、要求される通信の要求されるノード間パターンが比較的小さいので、他のリーダ選定アルゴリズムより、障害に対する回復力のずっと高いリーダ選定アルゴリズムを導く。つまり、要求されるノード間通信は、過半数に基づく３フェーズコミットのための必要最小限である。

固く結合されたアルゴリズムは、データベースを構成するノードのグループのサイズを考慮することによって、簡潔なショートカットを作成する。アルゴリズムは、未知のサイズのグループに一般化することができる。

根本的に、提案する固く結合されたアルゴリズムは、Ｇａｒｃｉａ−Ｍｏｌｉｎａインビテーションアルゴリズムの向上に基づく（Ｈｅｃｔｏｒ Ｇａｒｃｉａ−Ｍｏｌｉｎａ，Ｅｌｅｃｔｉｏｎｓ ｉｎ ａ ｄｉｓｔｒｉｂｕｔｅｄ ｃｏｍｐｕｔｉｎｇ ｓｙｓｔｅｍ，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ，Ｃ−３１（１）：４７−５９，Ｊａｎｕａｒｙ １９８２）。該アルゴリズムは、リーダ選定および３ＰＣ耐障害性プロトコルを、同一障害シナリオによる選定およびコミットを保証する１つのプロトコルに結合することを含む。

以下に、選定アルゴリズムの高レベル特性について記載する。

過半数に基づくリーダ選定プロトコルの高レベルステージ
本発明の好適な実施形態では、リーダまたはコーディネータの選定は、次のような状況で実行される。
１．システム初期化：全てのノード（またはプロセス）が分散データベースを初期化し、初めてそれに結合するときに、現在の既知のコーディネータは存在しない。したがってコーディネータが選定され、コーディネータアイデンティティが共通の知識であることを確実にするために、全てのノードが選定を承認する。

２．ノード結合：例えば再起動の後に新しいノードがシステムに結合するときに、現在のコーディネータを承認することが好ましい。したがって、新しいノードが加わることで選定プロセスはトリガされず、新しいノードの一意の識別子が現在のコーディネータの一意の識別子より高い場合でも、これは真である。下述するように、識別子は選定プロセスで使用される。コーディネータ移行動作から発生するデータベースシステムの性能の流出を制限するために、現在のコーディネータを可能な限り試行しかつ維持することは、該アルゴリズムの望ましい特徴である。

３．コーディネータ障害：コーディネータ障害時、例えばコーディネータ機械が破損した場合、接続し続けている全てのノードによって選定を実行することが好ましい。本質的に、選定はシステムの初期化時に呼び出されるものと同一である。

４．接続性障害：コーディネータおよびノードの過半数を構成しないノードグループ、換言すると（Ｎ−１）／２未満のノードが、過半数から切断されたときに、依然として接続されている過半数のノードは、新しいコーディネータを選定することが好ましい。ひとたび完全な通信が再開すると、前コーディネータを含め少数派のノードは、新しいコーディネータの主導権を認識し、それに加わることが好ましい。

５．オンデマンド選定：コーディネータは自らを指名することなく、選定プロセスを呼び出すことが好ましい。これは、コーディネータがコーディネータ（ＣＰＵ、メモリ、熱等）として機能することにおける問題を識別し、責任を代替ノードに継承することを決定した場合に発生し得る。

過半数に基づくリーダ選定プロトコルのアルゴリズム
コーディネータ選定プロトコルは、各要素が一意の識別子を有することを要求し、特定のシステムメッセージを要求し、多数の予め定められた選定状態を有し、かつ特定のタイミング信号およびタイムアウトを要求する。ここでこれらの問題に取り掛かる。１．一意の識別子（ＵＩＤ）：各ノード（またはプロセス）には一意の識別子（ＵＩＤ）が割り当てられる。ＵＩＤを生成するための様々な周知の技術が存在する。最も単純なものは、システムのＭＡＣアドレスをＵＩＤとして使用する。

２．メッセージ：全てのメッセージが同じ既知のメンバリストを共有する。以下は、例示的選定シナリオで使用されるメッセージのリストである。言及する周波数は、シグナリングに周波数分割多重化が使用される実施形態に関連する。

２．１ Ｉ＿ＡＭ＿ＥＬＥＣＴＥＤ＿ＣＯＯＲＤ：これは、コーディネータによってＦ１の周波数を使用して周期的に送信されるブロードキャストメッセージである。全てのシステムノード向けに意図されており、それらが依然としてコーディネータとの通信を維持することを確実にするために使用される。

２．２ Ｉ＿ＡＭ＿ＣＯＯＲＤ＿ＣＡＮＤＩＤＡＴＥ：これは、選定中に送信されるブロードキャストメッセージである。自らをコーディネータ候補とみなしているノードが、周波数Ｆ２でこのメッセージを同報通信する。

２．３ Ｉ＿ＥＬＥＣＴ＿ＹＯＵ：これは、ノードから潜在的コーディネータへ送信されるユニキャストメッセージである。このメッセージは、Ｉ＿ＡＭ＿ＣＯＯＲＤ＿ＣＡＮＤＩＤＡＴＥメッセージに対する応答として、またＩ＿ＡＭ＿ＥＬＥＣＴＥＤ＿ＣＯＯＲＤメッセージへの応答としても送信される。

２．４ ＩＳ＿ＴＨＥＲＥ＿ＣＯＯＲＤ：これは、各ノードが選定に参加し始めるときに、各ノードによってＴ３のタイムアウト付きで送信されるブロードキャストメッセージである。

３．ＸＤＢ選定状態：
以下は、選定の過程において、またはその中間に、要素またはノードが入ることのできる例示的状態のリストである。

３．１． ＩＳ＿ＴＨＥＲＥ＿ＣＯＯＲＤ：この「コーディネータが存在するか」状態は、ノードが選定に参加し始めるときの初期状態である。上述したＴ３は、ＩＳ＿ＴＨＥＲＥ＿ＣＯＯＲＤメッセージを送出した後の沈黙期間であり、その間、該ノードは選定メッセージが存在するか否かを知るために着信を待つ。

３．２． ＣＡＮＤＩＤＡＴＥ（候補）：ノードが候補状態になるときは、Ｉ＿ＡＭ＿ＣＯＯＲＤ＿ＣＡＮＤＩＤＡＴＥメッセージを送信することによって、自らをコーディネータ候補として指名する。ノードは、最長でＴ６の時間だけ候補状態を維持する。その間に別のノードがコーディネータになった場合、ノードはそのコーディネータに結合しようと試みる。より高いＵＩＤを持つノードから受信し、本ノードが最近そのノードに投票していない場合、ノードはそのノードへの投票に移る。Ｔ６タイムアウトに達すると、ノードは、たとえそれがより低いＵＩＤを持つ場合でも、別のノードへの投票に移る。

３．３． ＶＯＴＥＤ（投票）：ノードが別のノードをコーディネータとして投票することを希望するときに、ノードは「投票」状態になる。ノードは投票状態にある間に１つの候補にのみ投票することができる。通常、ノードは最も高いＵＩＤを持つノードに投票するが、ノードへの投票が、成功裏にその候補がコーディネータになるという結果につながらなかった場合、ノードは次回にそれがこのステージに入ったときにその投票を変更し、それが最近投票していないノードの中から最も高いＵＩＤを選択する。

この状態のノードは、候補状態から移行した場合、それ自体の立候補のメッセージの送信を停止する。

ノードは、Ｔ４のタイムアウト期間中に投票候補からの着信が無ければ、Ｔ４のタイムアウト後にＩＳ＿ＴＨＥＲＥ＿ＣＯＯＲＤ状態に移行する。この機構は、最終的に投票の変更を可能にする。

ノードは、Ｔ５のタイムアウト期間中に候補がコーディネータになることができず、他のコーディネータが選定されなかった場合、Ｔ５のタイムアウト後にＩＳ＿ＴＨＥＲＥ＿ＣＯＯＲＤ状態に移行する。この機構は、最終的に投票の変更を可能にする。

３．４． ＥＬＥＣＴＥＤ（選定）：候補は、その立候補のブロードキャストに対し過半数の票を受信した場合、候補状態からこの状態に移行する（応答は、Ｉ＿ＥＬＥＣＴ＿ＹＯＵメッセージとみなされる）。ひとたびこの状態になると、該ノードは、Ｉ＿ＡＭ＿ＥＬＥＣＴＥＤ＿ＣＯＯＲＤブロードキャストを送信することを含むコーディネータの責任を負う。

３．５． ＡＣＣＥＰＴ（受入れ）：これは、たとえノードが他のノードに投票したか、あるいは自らを候補と見ていた場合でも、Ｉ＿ＡＭ＿ＥＬＥＣＴＥＤ＿ＣＯＯＲＤメッセージを同報通信したノードがコーディネータであることを、ノードが受け入れる状態である。

４．タイマ：時間、タイマ、および頻度の次のリストは、選定プロセスによって使用される。

４．１． Ｆ１−Ｉ＿ＡＭ＿ＥＬＥＣＴＥＤ＿ＣＯＯＲＤメッセージが送信される頻度。時間Ｔ１＝１／Ｆ１

４．２． Ｆ２−Ｉ＿ＡＭ＿ＣＯＯＲＤ＿ＣＡＮＤＩＤＡＴＥメッセージが候補状態のノードによって送信される頻度。時間Ｔ２＝１／Ｆ２
経験的に、適正な実施は次の通りであることが決定された。
４．３ Ｆ２＝２．５×Ｆ１

４．４． Ｔ３−ＩＳ＿ＴＨＥＲＥ＿ＣＯＯＲＤ状態中にネットワークトラフィックを観察する期間。

４．５． Ｔ３＝５×Ｔ１、ここでＴ１＝１／Ｆ１である。
４．６． Ｔ４−ノードがその候補に（候補メッセージに対する応答として）最後に投票したときから、それが投票した候補からブロードキャストを受信しなかった期間。そのノードがこの合間にどれか他のノードに投票したこと、およびこのノードが選定をこの時点で再始動することによってその投票を変更することができるあることを前提とする。

Ｔ４＝１０×Ｔ１
４．７． Ｔ５−ノードが一貫して特定のノードに投票する期間であって、投票されたノードが過半数を達成するのに失敗した期間。その後、ノードは選定を再始動する。

Ｔ５＝２００×Ｔ１

４．８． Ｔ６−これは、ノードが過半数を集めることができず、それにも拘らず別の選定されたコーディネータ、またはより高いＵＩＤを持つ候補からの着信が無い場合に、候補であり続ける時間を制限する期間である。ノードはその立候補を諦め、投票すべき別のノードを探す。
Ｔ６＝５００×Ｔ１

４．９． Ｔ７−これは総合選定タイムアウトである。コーディネータの選定がこのタイムフレーム内に終了しない場合、選定プロセス全体が再始動する。
Ｔ７＝１０００×Ｔ１

４．１０ Ｔ８−Ｔ８はタイムアウトである。Ｔ８のタイムアウト後、投票は失効したとみなされる。
Ｔ８＝３０×Ｔ１

４．１１ Ｔ９−Ｔ９はタイムアウトである。Ｔ９のタイムアウト後に、候補ノードはもはや候補とみなされなくなる。
Ｔ９＝７×Ｔ１

本アルゴリズムの注目すべき要素は、３フェーズ原子コミットを実行するために、他の全てのデータベースノードへの双方向通信を必要とする分散データベースのコーディネータとなるべきリーダが選定される目的に適合するように、それを調整する仕方である。他のノードは必ずしもそれらの間で通信する必要は無い。

この観点は、通常論じられるものとは異なるアルゴリズムを導き、要求される通信パターンが存在する場合にのみリーダの選定が終結するという利点を持つ。

レコードをネットワークアドレスにマッピングするための基礎として２次インデックスを使用することによるデータレコードへのアクセス
上記データ管理システムでは、マッピング／ハッシング関数を使用してデータレコードの先頭キーをネットワークアドレスにマッピングするデータレコードインデクシングの実現、およびそれを実行するための規定のＸＤＡＰデータアクセスプロトコルに基づく、データベース、ディレクトリ、レジストリ、ストレージシステム、またはリポジトリのための実現が達成される。

しかし、先頭キーのみに基づいてデータにアクセスすることは必ずしも充分ではない。往々にして、少なくとも時々、二次、三次、およびさらなるレベルのキーを探索する必要がある。

したがって、本発明の実施形態の他の利益のために一次キーを超える探索能力、すなわち高速、高スループット、および高スケーラビリティの読出しおよび書込み動作のためにデータレコードを格納しかつ取り出すように、標準高速ネットワーク機器を強化する能力を追加することが意図されている。記載する技術を使用して、前述した一次インデックスをベースとするアクセスと同様に、二次インデックスを使用したデータのアクセスが可能となるように、機能性を拡張する。

本実施形態は、レコードをネットワークアドレスにマッピングするための基礎として二次インデックスを使用して、システムでデータレコードにアクセスする技術および実現を教示する。したがって、一次アドレスの場合と同様に、標準ネットワーク要素を使用して非ブロッキングワイヤ速度で、リモートコンピュータにレコードを格納しかつ取り出すために、二次アドレスを使用することができる。

例えば行政機関によって維持される市民のレコードを例に挙げる。レコードは次のようなフィールド、すなわち氏名、社会保障番号、住所、電話番号、およびパスポート番号を含むことができる。全てのフィールドが完全に検索可能であることが望ましいが、１つのキーだけが先頭キーとなり、一次ネットワークのアドレシングシステムに直接ハッシングすることができる。

フィールドは、次のスキームすなわち：レコード人物；一次キー：社会保障番号（レコードをネットワークアドレス７：９：Ｂ：８：４：Ａにマッピングする先頭キーとして使用される）を使用して、一次および二次フィールドに編成することができる。二次キー１は住所であり、二次キー２は電話番号であり、二次キー３はパスポート番号である。

一次キーは、効率性を求めて選択することが好ましい。したがって、探索される可能性が最も高いフィールド、または常に一意の回答をもたらす可能性が最も高いフィールドを、一次キーに対する一次フィールドとして選択される。一意であってもなくてもよい二次キーも、データ管理システムのクライアントアプリケーションによって、データレコードにアクセスするために使用することもできる。

二次キーは、値の範囲および２つ以上のフィールドに関与する任意の複合セットに対して定義することができる。例えば、年齢：未成年および住所の合成値を使用して、特定の家庭に住んでいる子供のデータレコードにアクセスすることができると言うことができる。

従来の技術つまり先行技術の二次および一次データレコードインデクシングは、コンピュータベースのデータ構造および検索手順、主に２／３ツリー、赤／黒ツリー、またはＡＶＬツリー等の検索ツリーを使用して実現される。これらの方法を使用して二次キーをベースとするアクセスを実現し、基本的に一次インデックスに戻ってクロスインデックスすると、先頭キーアクセスを使用して実現されるような上述したシステムの利点が妨げられる。

上述したデータ管理システムで、標準ネットワーキングは、データレコードを格納し、かつ取り出すために使用される。レコードを検索する際に、この方法がいかにしてメモリアクセスにおける障壁およびブロッキングライン（ｂｌｏｃｋｉｎｇ ｌｉｎｅ）を回避するかを説明した。従来の技術つまり先行技術を使用して実現される二次キー検索では、これらの利点は全て損なわれ、先頭キーが取得されるまでデータは二次キーを介して検索される。一次キーが取得されて初めて、その後の動作が非ブロッキングかつ効率的になる。これは、二次キーを使用してデータにアクセスする全てのクエリに対して、メモリまたはディスクをベースとするデータ構造へのアクセス付近で、シーケンシャルラインのブロッキングが発生しそうであることを意味する。

これまで、データ管理システムはほとんどが単一のコンピュータをベースにし、あるいは代替的に、コンピュータネットワークを通してアクセス可能な複数のデータシステムにパーティション化され、階層システムとして管理されてきた。上述した背景を参照されたい。これらの実現におけるインデクシングは一般的に、検索ツリー等の検索手順および構造をサポートするメモリ内およびディスク内データ構造に基づいている。

そのような構造は一般的に、データ管理システムをホストするサーバの速度および容量が、クライアントアプリケーションをホストするコンピュータの速度および容量に比例して成長するので、これらのより限定された状況では充分である。したがって、サーバがＮ個のクライアントをサポートし（かつクライアントコンピュータよりＮ倍高速であり）、これらのクライアント処理容量が技術の進歩（ムーアの法則）を通してＫ倍成長すると、サーバの処理容量もそうなり（Ｎ＊Ｋ）、サーバメモリおよびＣＰＵを使用するデータインデクシングの実現は要件を満たし続ける。

しかし、今日、コンピュータのピアツーピアの通信アプリケーションのパターンが増加しており、クライアントサーバアプリケーションだけではなくなっている。そのようなアプリケーションがピアツーピア通信の副次的効果としてデータアクセスを要求すると、以前には存在した線形性がもはや適用不能になる。Ｎ個のコンピュータがピアツーピアアプリケーションに関与すると、Ｎ２乗の圧力係数がアクセス関連データ管理システムに発生し（Ｎ＊（Ｎ−１）／２変換）、比例線形性は破綻する。

消費者電話（ｃｏｎｓｕｍｅｒ ｔｅｌｅｐｈｏｎｙ）等の古典的なピアツーピアアプリケーションでは、まさにこの理由で、商用データベース等の標準汎用データ管理システムは、今までオンラインデータ管理の運用に使用されていなかった。ネットワークにおける電話機の位置を解決する（ｒｅｓｏｌｖｉｎｇ）ような動作は、汎用データ管理システムよりむしろ、専用特殊用途電話網および特定用途向けネットワークシグナリングの不可分の一部であった。

今、ようやく、汎用ネットワークが大規模なピアツーピアアプリケーションに使用され始め、汎用データ管理システムは、それがオンライン呼データを解決し（ｒｅｓｏｌｖｅ）格納するために使用されるときに、ネットワーク活動の完全多項式圧力（メトカーフの法則）に適合することを要求されている。

上記のソリューションとして、以下の実施形態は、障壁を克服するために、ネットワークを使用してデータレコードアクセスをいかに実現するかを教示する。ネットワークリンク層は、コンピュータメモリまたはディスクではなく、システムのための基礎および支柱であり、したがって、ネットワーク層オーバレイを使用し、かつネットワーク層アドレスを各レコードに追加して、インデクシングを実現することが可能である。したがって、複数のネットワーク層サブネットを同じリンク層ネットワーク上にオーバレイするのと全く同様に、複数の対データインデクシングスキームをオーバレイし、効率的な同時並行標準ネットワーク機器を使用してデータ管理システムを実現し続けることができる。

したがって、説明した通り、一次データレコードアクセスは、イーサネット（登録商標）リンク層ネットワークおよびＭＡＣアドレスに各レコードを関連付けかつマッピングすることによって実現される。加えて、二次インデックスが次いで、同じイーサネット（登録商標）リンク層ネットワーク上にオーバレイされた複数のＩＰサブネットとして実現され、標準ルータのみならず、分散ルータおよび経路指定方法を使用して、二次インデックスのネットワークアドレスを一次インデックスのＭＡＣにマッピングすることができる。したがって、一次キーへの二次マッピングが、まさしくそのために設計された機能を実行する標準ネットワークコンポーネント、ルータによって実行される。リンクおよびネットワーク層アドレス、つまりこの例ではＭＡＣおよびＩＰアドレス両方のグループアドレス指定を使用することによって、データコピーおよび非一意のインデックスは依存として存在し得る。

本実施形態に係る、二次キーを使用するデータアクセスのための技術を図１９に示す。それは上述の通り、次の要素を含む。
ＸＤＲ−データアクセスクエリを受け取るオブジェクト、ＸＤＲ１．．．ＸＤＲｎ

ＸＤＢ−サイトＡ、Ｂ、Ｃ、およびＤでデータレコードを格納するオブジェクト、ＸＤＢ１．．．１２、ならびに、
ＸＤＡＰプロトコル−複数の複写、パケット複製、パケット損失、および要素またはセグメント損失が与えられたレコードを格納し、かつ取り出すために使用されるプロトコル

加えて、スイッチ１９０１は、ネットワーク構造で相互接続され、かつ全てのＸＤＢおよびＸＤＲを接続するリンク層オブジェクトである。
ルータ１９０３−ネットワークアドレスが与えられると、１つのリンク層アドレスから別のリンク層アドレスを持つ宛先に、パケットを転送するネットワーク層オブジェクト。

図１９は、分散インデックスルータを使用してネットワーク上のマルチインデクシングをサポートするルータの使用を示す。上で説明した通り、システムは負荷均衡および冗長性をも組み込んでいる。

ここで、図２０を参照すると、一次キーに従って配列されたデータベースの二次キーによる検索を可能にするための１アームルータが示されている。二次キーに基づくクエリはＸＤＲ２００２によって発行され、ルータ２００４に送られる。ルータはクエリを受信し、対応する一次キーを見つけるためにそのルーティングテーブルで二次キーを捜索する。一次キーは通常の方法でハッシングされ、ハッシュ結果を使用して、クエリはＸＤＢ２００６に差し向けられる。クエリは次いで、正しいＸＤＢをターゲットリンク層アドレスとして同じネットワークに転送される。

特に二次キーを使用する、本実施形態に係るデータアクセスシステムの使用例は移動電話であり、そこではＳＩＭカードＩＤおよび電話番号は両方ともキーであるが、それらのうちの１つだけが一次キーである。二次キー（例えば電話番号）に関する全てのクエリは、これらのキー用に割り当てられたサブネットでネットワークアドレスにマッピングされる。電話番号を含むクエリを受信したときに、ＸＤＲが番号をネットワークアドレスにマッピングし、次いでそれをサブネットのルータに転送するように、充分な１アームルータがデータアクセスネットワークにプラグインされる。ルータは、ＭＡＣアドレスが一次キーに対応する正しいＸＤＢにクエリを転送する。ＸＤＢが最後の二次キー更新を持ち、関連ネットワーク層アドレスを取り、サブネットルータとの標準登録手順を実行したときに、一次キーはルータによってトランスペアレントに学習される。これは事実上、ＩＰアドレスがコンピュータで設定される場合と同様に働く。

ネットワークを通して、ネットワークアプリケーションの結果として、大量のデータにアクセスし、インデクシングすることが鍵である。該技術は、大型分散ストレージ、キャリアインフラストラクチャに基づくデータベース、または相互接続されたエンドステーション間で完全分散されたデータベースを形成するために使用することができる。

上記の使用の１例として、非常に厳しい時間または他の性能限界内でデータルックアップが要求される、すなわち高度に定義されたサービス品質要件を持つ、サービスの場合がある。

他のテーブルとして格納されハッシングされた二次インデックスを使用することによるデータレコードへのアクセス
ルータを使用しないが、依然として二次インデックスを介してデータレコードへの非ブロッキング実時間アクセスを提供する、二次インデックスを実現する別の方法についてここに記載する。無共有分散データリポジトリでは、テーブルはパーティショニングキーを使用してパーティション化され、異なるコンピューティング資源間に分散される。そのような無共有アーキテクチャでは、二次インデックスも一般的に異なるパーティション間に分散され、各パーティションは、そのパーティションに属するサブテーブルの二次インデックスを保持する。テーブルパーティショニングとその対応するサブインデックスとのこの緊密なコロケーションは、全てが所与のパーティション内に充分に範囲を限定されるデータベースの運用をサポートするときに、有利である。

例えば、ＣＤＲ（呼データレコード）を保持するデータベースは、日付別にパーティション化することができる。つまり、特定の日付に行なわれた全ての呼が１つのパーティションに属する。ＣＤＲデータベースのための二次インデックスの１例は、発呼電話番号であり得る。そのようなパーティション化の例では、特定の日付に行なわれた全ての呼の発呼電話番号別のサブインデックスを、その日付に行なわれた全ての呼と同じパーティションに共通配置すると、共通のクエリ（例えば所与のサブスクライバによって所与の日付に行なわれた全ての呼）の演算が効率的になる。

しかし、多くの他の場合、パーティショニングサブインデックスをパーティショニング日付自体と共通配置すると、二次インデックスを介するデータアクセスを非スケーラブルにする、ブロッキングデータ構造が形成される。

例えば、ＩＤ番号を持つ上述したデータベースは、先頭キーおよびパーティショニングキーとすることができる。各ＩＤ番号パーティションレンジに対し電話番号二次インデックスがサブインデクシングされた場合、電話番号を使用することによってデータレコードにアクセスするには、クエリを全てのサブスクライバに同報通信する必要がある。

ルータ無しで、しかし依然として二次インデックスを介してデータレコードへの非ブロッキング実時間アクセスを提供する、二次インデックスを実現する別の方法は、ここに記載するネットワーク内分散データ管理の一部である。電話番号二次インデックスは別のテーブル、「インデックステーブル」として実現され、それは２つのフィールド、すなわち「電話番号」および「ＩＤ番号」を有する。インデックステーブルは次いで、二次インデックスフィールド「電話番号」がインデックステーブルの先頭キーとなるように、パーティション化される。二次テーブルは、オリジナルテーブルが変更されるたびに、システムによって自動的に更新される。二次テーブルは、（読出しおよび書込み動作に関連して）システム内のいずれかの他のテーブルとして管理される。したがって、その先頭キーを使用していずれかのデータ要素にアクセスするのと同様に、インデックステーブル内のエントリへのアクセスはワイヤ速度で行なわれる。したがって、二次キーを使用してオリジナルテーブル内のデータ要素にアクセスすることは、次によって実現される。
１．インデックステーブルの先頭キーを使用してインデックステーブルにアクセスし、オリジナルテーブルの先頭キーを受け取る。
２．結果として得られる先頭キーを使用してオリジナルテーブルのデータ要素にアクセスする。

インデックステーブルクロスパーティションをハッシングするこの方法は、２回の先頭キーベースデータ要素アクセスを使用して、最初にインデックステーブルにアクセスし、次いでオリジナルテーブルにアクセスすることによって、ユーザがその二次キーを使用して非ブロッキングで任意のデータ要素を突き止めることを可能にする。

システムのアップタイムモデル
次に、わずか３〜５部の複製を使用して、システム可用性に関して９が５個以上並ぶ性能（＞９９．９９９％）を達成することを実証する。

上述したメモリ内分散データシステムに基づいて、演算素子の個数、および仮想データパーティショニングが演算素子にマッピングされる方法の関数として、システムの期待される可用性を算出することが可能である。

上で説明した通り、仮想データパーティショニングコピーをコンピューティングノード間でシャッフルすることを通して、コンピューティングノード間の全体的負荷均衡および相互依存性が増大する。他方、図２４に示すように、チャネルのグループに割り当てられるセットとしてコンピューティングノードを配列することによって（本書では回復力セットと呼ぶ）、システムの可用性を高めることができる。全ての回復力セットはそのコピーのマイノリティを失うことができ、それでもシステムは依然として利用可能であるので、システム全体の回復力は非常に高い。

以下のアップタイムモデルは、システムの各演算素子「スロット」に使用される。

システム可用性モデル：
上記システムの可用性モデルを使用して、図２０Ｂに示すグラフを計算することが可能である。上述のグラフは、各ＸＤＢの性能が１５０００回の毎秒演算数であることを前提としている（実験室での試験で実証された通り）。

グラフから分かるように、最高２００までのＸＤＢを有し、毎秒約１００万回のトランザクションを生成するシステムの場合、３部複写は、９が５個以上並ぶ可用性（＞９９．９９９％）を達成するのに充分である。そのようなシステムは、８０００００００〜１００００００００までのサブスクライバをサポートするほとんどのＩＭＳキャリアクラスのアプリケーションにとって充分である。

同じく上述したグラフから分かるように、５部複写は、上記容量のシステムの場合、９が８個以上（＞９９．９９９９９９％）の可用性を達成し、ＩＭＳシステムに対する実際の需要を超える容量である、

の４〜５倍をもたらすシステムの場合には、９が６個以上並ぶ可用性を提供することができる。

同時並行データベースクライアント間のサービスの品質（ＱｏＳ）の管理

トランザクション待ち時間およびスループットに関して、同時並行データベースクライアント間のサービスの品質（ＱｏＳ）を管理するための実施形態について、ここに記載する。

今日、データベースのサービスレベルメトリックは一般的に次のようなものを指す。
（１）レコードの読出しまたはレコードの書込み等の原子データベース動作の待ち時間
（２）同時並行セッションの数
（３）トランザクションレート

加えて、データベースの待ち時間保証の実現は通常、特定タスクに優先度を設定することによって行なわれる。次のような状況下で待ち時間メトリックを保証することは疑問である。
１．システム負荷が高い（システム負荷は待ち時間メトリックに悪影響を及ぼす）。
２．分散データベース（システムの分散は動作時間の制限を難しくする）。

実時間データベースは、ｅトレーディング、電気通信、および製造等の多数の分野で幅広く使用される実時間アプリケーションの基本的なコンポーネントである。実時間アプリケーションは、それらが提供するサービスレベルによって評価される。サービスレベルは、エンドユーザの経験を測定することになる。エンドユーザの経験は次のようなものを含む。
１．サービスの可用性：
２．ユーザはいつでも希望するときにサービスを利用することができるか
３．サービスの応答性：サービスは充分迅速に応答するか
４．サービス全体の品質：
サービス自体が充分に良好であるか−ユーザの全体的経験

当然、実時間アプリケーションサービスレベルは、アプリケーションプラットフォーム内の任意の単一コンポーネントによって達成されるサービスレベルの連結である。

実時間アプリケーションは発展しつつあり、それらは明らかに、
１．事実上分散化されることが多くなってきている。
２．予測不能なテーブル作業負荷を有する。
３．予想外のアクセスパターンを持つ。
４．クライアント−サーバよりむしろサービス指向になってきている。

現在、データベースおよび特に分散実時間データベースは、データベースの次の項目を保証するサービスの品質機構を実現していないと思われる。
（ａ）アクセスポイント毎の可用性（スループット：毎秒演算数）
（ｂ）応答性（原子動作当たりの有界待ち時間）ならびに
（ｃ）データ鮮度および一貫性（データは最新版でありかつ正確である）

次の相互条件の存在を可能にする一方で、上記メトリックが保証されなければならない。
１．データベースは任意の数のサイト全体に分散される。
２．データベースは任意の数の同時並行アクセスポイントを可能にする。
３．データベースは、無差別に任意の動作の組合せを実行することができる。
４．データベースは、任意の作業負荷状態で無差別に実行する。

本発明の実施形態は、ネットワーク内実時間データベースを含む。実施形態はネットワークを使用して、データベースを単一のグローバルクロスロケーションネットワークサービス（ｇｌｏｂａｌ ｃｒｏｓｓ−ｌｏｃａｔｉｏｎ ｎｅｔｗｏｒｋｅｄ ｓｅｒｖｉｃｅ）に転換する。そういうものとして、それはネットワーク自体から幾つかの特性を継承し、中でも特に典型的なネットワークのＱｏＳメトリックは遅延、帯域幅、および改善された損失特性である。データベースＱｏＳの新しい概念は、実時間アプリケーションサービスレベル一致要件を満足する。

本書で記載する実施形態は、実時間アプリケーションサービスレベルメトリックを実時間データベース性能メトリックにマッピングするために使用することのできるＱｏＳ概念を示唆しかつ実現する、初めてのデータベースである。
そのようなメトリックとして、次のようなものが含まれる。
１．アクセスノード毎の保証されたデータベースのスループット：
ａ．データベース作業負荷に関係無く
ｂ．同時並行アクセスノードの数に関係無く（各ノードは異なるアプリケーションにサービスを提供することができる）

２．原子動作毎の保証されたデータベース待ち時間：
ａ．オペレーションミックス（ｏｐｅｒａｔｉｏｎｓ ｍｉｘ）に関係無く
ｂ．データベース作業負荷に関係無く
ｃ．データの物理位置に関係無く
ｄ．データスキーマに関係無く

３．アプリケーション品質⇔データベースのデータの一貫性：
ａ．データの物理位置に関係無く
ｂ．システム全体のデータ複製の数に関係無く

本書のどこか別の場所に記載するように、データベース内で障害が発生した場合、最大限の努力が果たされる。

上で図４に関連して説明した通り、分散データベースシステムは、３つの基本型のノード、つまりアクセスノード、データノード、およびスイッチングノードを含むサーバのクラスタである。アクセスノードは主としてクライアント要求を取り扱い、それに従って応答を返す。データノードは主としてデータレコードをそのメモリ内に格納し、データを管理し、例えばデータレコードを取得し、あるいはデータレコードを不揮発性ストレージに格納する。スイッチングノードは主として、全てのクラスタノードを接続し、様々なノードの間でメッセージを経路指定する。アクセスノードおよびデータノードは両方とも、システム内の残りのノードに関係なく、任意の物理位置に常駐することができる。

サービスレベルメトリックにより実時間アプリケーションにマッピングすることのできる実時間データベース保証ＱｏＳの概念は、様々なＱｏＳメトリックを含むことができ、その各々を様々な仕方で実現することができる。以下は、可能なデータベースＱｏＳメトリックおよび可能な実現方法を開示するが、これらおよびさらに多くのＱｏＳメトリックを実現するために他の方法を使用することができる。

保証されるスループット
目的は、データベースクライアント（実時間アプリケーション）に対し、実行することのできる毎秒当たりの原子動作数を保証することである。原子動作は、レコードの作成、レコードの読出し、レコードの修正、レコードの削除を含む。スループットレベルはアプリケーション要件に従う。

本発明の実施形態は、以下を通してスループットＱｏＳメトリックを保証することができる。
＊スループットスケーラビリティ：本発明の実施形態の分散データベースは、さらなるノードをそのクラスタ（アクセスノード、データノード、スイッチングノード）に単純に追加するだけで、そのスループットを無限に拡張することができる。各アクセスノードは特定のスループット（毎秒Ｘ回の演算数）を保証し、システム全体のスループットは、全アクセスノードのスループットの合計である。したがって、アプリケーションは任意の所要スループットを要求することができる。
＊スループット割当て機構：本発明の実施形態は、システムアドミニストレータがアクセスノード毎のスループット割当て量を割り当てることを可能にする、スループット制御機構を実現する。特定のアプリケーションは、そのスループット要件を満たすために必要なだけの数のアクセスノードを使用することができる。しかし、アプリケーションスループットは、データベースにアクセスするために使用されるアクセスノードに割り当てられたスループット割当て量によって制限され、同じデータベース資源を使用する他のアプリケーションがそれらの所要スループットを保証することを可能にする。

原子動作毎の保証される低待ち時間
目的は、原子動作を実行するために要する時間を制限し、それをできるだけ低く維持することである。原子動作は、レコードの作成、レコードの読出し、レコードの修正、レコードの削除を含む。待ち時間上限値は、システムの瞬時負荷によって、あるいはアクセスノードの物理位置に対するデータの物理位置によって影響されてはならない。

本実施形態に係るシステム内の動作ラウンドトリップは次の通りである。

アクセスノード（構文解析）→スイッチング（要求転送）→データノード（処理）→スイッチング（応答転送）→アクセスノード（応答）

目標は、典型的なラウンドトリップのサブフェーズの各々の待ち時間を最小化することである。本発明の実施形態のシステムは現在、以下を通して低待ち時間ＱｏＳメトリックを保証する。
＊過半数に基づくデータアクセスおよびデータアフィニティ：ノード障害および瞬間ネットワーク切断がどちらも、データの可用性またはシステムの性能に悪影響を及ぼさないことを確実にすることを希望する。したがってデータレコードの幾つかの複製を維持し、その各々を異なるデータノードに格納する。データレコードを書き込み、または読み出すときに（過半数に基づくリーダを参照されたい）：
・このデータレコードを格納するように現在要求されている全てのデータノードは、コーディネータを選択する。コーディネータは、要求により動作を管理しかつ監視する責任がある。

・レコードを読み出し／書き込むためにデータ複製の過半数が要求される場合のみ。これは、誤作動ノードが動作を低速化しないことを確実にする。

・システムアドミニストレータはデータアフィニティポリシーを規定することができる。つまり、データの過半数の位置をできるだけそのアクセスポイントの近くに設定し、ネットワーク（スイッチング）待ち時間を無効化することができる。

＊同時並行性および負荷均衡：各データノードは、異なるデータノードの間に均等に分散されたデータの一部分を管理する責任がある。各データノードは他のノードから独立している。つまりそれは、データを他のデータノードと同時に処理することができる。これは、システムが高負荷状態で作業するときでも、１動作当たりの短い待ち時間を達成することを可能にする。本発明の実施形態のデータベースは、必要に応じた数のデータノードをそのクラスタに追加することができる。システムの有するデータノードが多いほど、同時並行データ処理容量が増大し、したがって１動作当たりの待ち時間が短くなる。より多数のデータノードを追加することにより、低い待ち時間レベルを維持することができる。

＊データパケット化およびネットワーキング技術：本発明の好適な実施形態は、アクセスノードをデータノードと接続するためにネットワークおよびスイッチノードを提供する。システムは、データベーステーブルを原子レコードに分解し、それらをパケット化することを含む。各レコードはネットワークで伝送され、ネットワークを通して異なる場所（データノード）に格納される。これは、いずれのデータレコードも、現在実行される動作回数またはデータスキーマに関係なく、根底にあるネットワークのＱｏＳレベルとしてワイヤ速度でそのデータノードに到達しかつ戻ることを意味する。

保証される実時間データ鮮度および一貫性
目的は、データレコードのどんな変更も即座に有効になることを確実にすることである。アプリケーションは最新の更新データを取得し、かつこのデータがシステム全体で一貫していることを確実にすることができる。

本発明の実施形態は現在、データ鮮度を確保するために、次のような幾つかの機構およびアルゴリズムを使用する。
＊３フェーズコミット：これについては本書の別の場所に記載されている。
＊過半数に基づくデータアクセスおよび誤り訂正：これについては上述している。

データノード障害の場合の最大限の努力の実施
データベースはそのＱｏＳレベルを保証することが好ましい。しかし、データノード障害が発生した場合、システムはその残存資源により、要求されるＱｏＳを充足するために最善を尽くす。

本発明の好適な実施形態は幾つかの機構およびアルゴリズムを使用して、データ鮮度を確保する。
＊無制限のアクセスノード数：本発明の実施形態は、任意の数のアクセスノードを可能にする。アクセスノードは、各アプリケーションを複数のアクセスノードに接続することを可能にする。アクセスノードの１つに障害が発生した場合、アプリケーションは別のノードで作業することができ、そのアクセスレート（スループット）が低下しないことを確実にする。

＊原子自己回復：本発明の実施形態は、それらのデータノードの自己回復機構を実現する。各データレコードは異なるノードに幾つかのコピーを有するので、１つのデータノードに障害が発生しても、データは依然として残存するデータノードで入手可能である。したがって、残存データノードはそのデータに対する責任を負う。データアフィニティはシステム資源全体にわたって最適であり、したがって作業負荷は、クラスタ内の全てのデータノードの間で均等に分散される。残存データノードが、割り当てられた追加量のデータを格納する容量を有し、かつそれらが完全に利用されていないことを前提として、データベーストランザクションの同時並行性は維持される。同時並行性は、各動作の待ち時間および同時に処理できる動作数がＱｏＳ要件に適合することを確実にする。追加データを処理するだけの充分な資源が無い場合、システムはＱｏＳ要件を満たすべく最善の努力を払って、依然としてその資源を最適に利用する。

実時間データベースは、実時間アプリケーションの基本的コンポーネントである。実時間アプリケーションはそれらのサービスレベルによって測定される。アプリケーションサービスレベルは、実時間データベース等のアプリケーションプラットフォーム内の全ての単一ノードのサービスレベルの連結である。データベースＱｏＳは、アプリケーションサービスレベルメトリックをデータベース性能メトリックにマッピングし、瞬間システム負荷またはアクセス方法と関係なく、実時間アプリケーションサービスレベルを保証することを可能にする。

ステートフルアプリケーションのＮ＋Ｍ高可用性および災害復旧のためのネットワーク内データベースの使用
次に、ステートフルアプリケーションのＮ＋Ｍ高可用性および災害復旧のためのネットワーク内データベースの使用について記載する。

実時間ステートフル事象処理アプリケーション
セッションベースの実時間事象処理アプリケーションは、現在のセッションの状態を維持する必要がある。所与のセッションに属する各々の新しい事象は、そのセッションの「履歴」（つまり「状態」）の脈絡内で処理される。一般的に、パケットベースのアプリケーションは個々のパケットを処理し、それらを受け渡すだけであるが、これは必ずしも充分ではない。多くの場合、セッションの状態に応じてパケットを様々に処理する必要があるかもしれない。そのようなアプリケーションをステートフルアプリケーションと呼ぶ。

実時間ステートフル事象処理アプリケーションの例として、テレコム呼制御およびソフトスイッチ、移動電話ホームロケーションレジストラ（ＨＬＲ）、インターネットマルチメディアシステム（ＩＭＳ）のホームサブスクライバサーバ（ＨＳＳ）、サービスセレクションゲートウェイ（ＳＳＧ）、ＡＡＡサーバ、オンライン課金サーバ、ボーダーコントローラ、ファイヤウォール、オンラインバンキングおよびトレーディングシステムがある。

高可用性および災害復旧
実時間ステートフル事象処理アプリケーションの高可用性（ＨＡ）および災害復旧は、ステートフルフェイルオーバを確実にするために、異なるサーバ間でアプリケーションの内部状態を実時間で複製しかつ同期化することを必要とする。災害復旧プランニング（ＤＲＰ）の場合、アプリケーション内部状態の実時間複製および同期化は、異なる場所の異なるサーバ間で実行される。

実時間ステートフル事象処理アプリケーションの今日稼動している唯一のＤＲＰおよびＨＡモデルは、１＋１モデルである。１＋１可用性モデルでは、アプリケーションサーバは１対単位で構成され、各サーバがその待機フェイルオーバサーバを伴う。２つのサーバの内部状態は、暗黙にまたは明示的に同期して維持される。

暗黙の内部状態同期化高可用性１＋１モデル
暗黙の内部状態同期化は、システムの全ての入力を２つのサーバに同時に供給し、かつ各々に同じ事象を同時に対称的に処理させることによって、行なわれる。その結果、両方のアプリケーションサーバが対称な内部状態を維持する。しかし、両方のサーバの容量は、単一サーバの容量に低減される。

暗黙の内部状態同期化モデルは、２つ以上の障害に対する耐障害性を達成するために、３つ以上のアプリケーションサーバ間で状態を同期化するために使用することができる。しかし、全ての暗黙同期サーバの容量は依然として、単一サーバの容量と同等である。

ここで、図２１を参照すると、２つのユニット、一次ユニット２１０１および二次ユニット２１０２が両方とも処理の状態を格納する、暗黙の状態同期化１＋１ＨＡモデルが示されている。暗黙の同期化は２つのユニットの間で機能し、２つのユニットが更新されるのが単に同時であるだけでなく、実時間でもあることを確実にする。

明示的内部状態同期化高可用性１＋１モデル
ここで図２２を参照すると、暗黙の内部状態同期化の非効率的な資源利用を克服するために、明示的内部状態同期化が使用されている。明示的状態同期化は、２つのサーバ間で専用の接続およびプロトコルを使用して、サーバ間で内部状態を実時間で交換する。各サーバは異なるセッションおよび事象を独立に処理することができる。しかし、各サーバは両方のサーバの内部状態を有する。サーバの一方が障害を発生すると、第２のサーバはそれらの更新された状態を内部に格納しているので、第２のサーバが全てのセッションおよび事象を処理し続けることができる。

図２２は、明示的状態同期化プロトコルを利用して各サーバが両方の状態を有することを確実にするリンク２２０２を介して、サーバ１がサーバ２に接続された、明示的状態同期化１＋１ＨＡモデルを示す。

１＋１ＨＡモデルで明示的内部状態同期化を使用する場合、両方のサーバを完全に利用することができる。しかし、サーバの一方がダウンすると、システムの容量は単一のサーバ容量まで、つまり５０％低下する。これは、システムによって提供されるサービスの品質の深刻な劣化を引き起こし得る。したがって、明示的内部状態同期化の場合でも、障害発生時のサービスの劣化がそれほど深刻にならないように、各サーバはその全容量を完全には利用しないようである。これは資源利用率を低減させる。

実時間ステートフル事象処理アプリケーションは通常、実時間生産事象より多くの実時間状態同期化事象を処理することができないので、明示的内部状態同期化は一般的に１＋１モデルに限定される。したがって、内部状態同期化は単一の障害を越える耐障害性を提供することができない。

本発明の実施形態の場合のように、Ｎ＋Ｍモデルを達成するために、ネットワーク内高可用性データベースを使用して、ネットワーク内分散偏在高可用性の非ブロッキングデータベースを提供し、Ｎ＋Ｍ ＨＡモデルが達成されるように、多くの実時間ステートフル事象処理アプリケーションを実時間で明示的に同期化することが可能である。Ｎ＋Ｍ ＨＡモデルとは、システムの可用性が、最大Ｍ個までのサーバの障害発生状態で、Ｎ個のサーバの最小容量を提供することを確実にすることを意味する。これは、Ｎ＋Ｍ ＨＡモデルを使用して、Ｎ＋Ｍ個のサーバでシステムを作動させることによって達成される。

Ｎ＋Ｍ ＨＡモデルでは、Ｎ＋Ｍ個のサーバは全部、完全に利用することができ、各サーバの障害でシステム容量はわずか１／Ｎ＋Ｍ低下するだけである。あるいはＮ＋Ｍサーバは、Ｍ個のサーバ障害の最高限度まで、個別のサーバ障害でシステムの容量が低減しないように、Ｎ個の完全利用サーバのレベルまで利用することができる。どちらの場合も、資源利用率はＮ／Ｎ＋Ｍであり、それは１＋１ＨＡモデルによって達成可能な最高５０％の利用よりずっと高い。Ｎが１０もの大きい値である場合でも、Ｍは一般的に１または２であるので、Ｎ＋Ｍモデルによって達成される資源利用率は一般的に８５％〜９５％の間である。

我々が提案しているＮ＋Ｍ ＨＡおよびＤＲＰのためのデータベース中心実時間状態同期化モデルは、異なる場所のＮ個の異なるクライアントからの多くの同時並行書込みを同時にサポートするために拡張することのできない、ブロッキングディスク内またはメモリ内アーキテクチャを有する現在のデータベース技術を使用するオプションではない。

Ｎ＋Ｍ高可用性のためのデータベース中心実時間状態同期化モデル
本発明の実施形態は、Ｎ＋Ｍ ＨＡおよびＤＲＰのための偏在する高可用性データベース中心実時間状態同期化モデルを提供する。それは以下を提供する。
１．より高い資源利用率：今日達成可能な５０％の最大限度に対して、およそ９０％。
２．より高レベルの耐障害性：今日達成可能な単一耐障害性をはるかに超える

本発明の好適な実施形態は、今日使用されている明示的状態同期化機構をピアツーピアの１対１のプロトコルからクライアントサーバの１対多数のモデルに拡張して、全ての場所から全ての実時間ステートフル処理アプリケーションインスタンスの全ての状態を格納するために、グローバルネットワーク内偏在非ブロッキングデータベースを使用する。１つまたはそれ以上のアプリケーションインスタンスが障害を発生した場合、同じ場所および／または他の場所の存続アプリケーションインスタンスによって、状態データベースからの全ての所要状態の実時間同期化によって、全てのセッション処理のステートフル復旧が実行される。

本発明の実施形態は、明示的状態同期化１＋１高可用性モデルで今日使用されている、同一マルチアプリケーションインスタンス環境に基づく。実際、本実施形態は、１＋１高可用性モデルからＮ＋Ｍ高可用性モデルへの改善を実行するために、アプリケーションインスタンスにも、アプリケーション環境に対しても変更を行なう必要が無い。

明示的状態同期化１＋１高可用性モデルで今日使用されている、先行技術のマルチアプリケーションインスタンス環境では、各実時間ステートフル事象処理アプリケーションインスタンスは、その内部状態を実時間でそのピアパートナ（ｐｅｅｒ ｐａｒｔｎｅｒ）と同期化する。ピアの一方が障害を発生した場合、アプリケーション環境は事象およびメッセージを障害サーバからその存続同期化ピアパートナに再経路指定する。

本発明の実施形態は、同一プロトコルを使用してでも、ピアツーピアアーキテクチャの場合と全く同様に、各アプリケーションインスタンスがその状態を実時間で状態データベースと同期化することを提供する。しかし、ピアツーピアシナリオとは異なり、障害が発生しない限り、状態は状態データベースに書き込まれるだけであり、状態はアプリケーションインスタンスに同期化されない。

ここで、図２３を参照すると、状態データベースを使用するＮ＋Ｍ高可用性モデルが示されている。

ピアツーピアの場合と同様に、１つまたはそれ以上のアプリケーションインスタンスに障害が発生した場合、事象およびメッセージは障害サーバから存続アプリケーションインスタンスの一部または全部に再経路指定される。システムが動作することのできる２つの可能なモードが存在する。
１）プッシュ同期化モード：ピアツーピアの場合と全く同様に、アプリケーション環境は、所与の障害サーバに属する全ての事象およびメッセージを、同一場所または別の場所の存続サーバの１つに再経路指定する。この場合、状態データベースは、再び、ピアツーピア同期化で使用されている同じプロトコルを使用して、適切な状態を存続サーバに「プッシュ」することによって、それらを積極的に同期化する。

２）プル同期化モード：この場合、アプリケーション環境は事象およびメッセージを、障害サーバから同一場所および／または異なるサーバにある全ての存続サーバに再経路指定する。したがって、その状態を持たないので、それが認識しない事象またはメッセージを受信した存続サーバの各々は、状態を状態データベースから積極的に「プル」する。

プッシュおよびプルモードは両方とも、同一実現に共存することができる。そのような場合、プッシュモードは、それが無い場合にはデマンドによって１つずつ要求される状態の一種の「事前取出し」とみなすこともできる。

既述の通り、本発明の実施形態はネットワーク内分散偏在高可用性および非ブロッキングデータベースを提供し、Ｎ＋Ｍ ＨＡモデルが達成され、資源利用率が２倍に増大する一方で、無制限の耐障害性レベルがもたらされるように、多くの実時間ステートフル事象処理アプリケーションの内部状態を実時間で明示的に同期化する。

上記は、アプリケーションインスタンスまたは動作環境のいずれかに任意の修正を加えて、１＋１ＨＡのための明示的状態同期機構を実現するシステム用に達成することができる。

メモリ内データベースシステム価格決定モデル
次に、上述した実施形態および他の同様のアプリケーションに適した価格決定モデルについて説明する。ＤＢＭＳ（データベース管理システム）のための価値ベースの価格決定モデルは、トランザクションレート、容量、およびスループット等の主要顧客価値を使用して導出される。

Ｏｒａｃｌｅ、ＩＢＭ ＤＢ２、およびその他のような現在のプロバイダによって使用されている既存のＤＢＭＳソフトウェアライセンス価格決定は、主要顧客の利益の問題ではなくしたがって不公正またはせいぜい恣意的とみなされ、最悪の場合には顧客に対立して、特にサービスプロバイダの利益に適う、パラメータを彼らの価格決定システムに使用している。

以下は、現在の価格決定システムの調査である。
１．ユーザ／サブスクライバ／ＤＢ−クライアントモデル−請求される価格は、データベースサーバに接続しているかあるいは接続を許可されたユーザ／サブスクライバ／ＤＢ−クライアントの数に関連付けられる。顧客の観点からは、ユーザベースの価格決定は、ユーザ／サブスクライバ／ＤＢ−クライアントの一部がヘビーユーザである一方、その他が稀に使用する場合には、非効率性を生み出す。ユーザベースの価格決定は、実際の使用レベルに関係なく、すべてのユーザに対して同一である。

２．プロセッサの数モデル−このモデルでは、請求される金額は、システムによって利用されているプロセッサの数に基づく。ＣＰＵは同一マルチＣＰＵサーバ（ＳＭＰ）内で、またはクラスタ構成（例えばＯｒａｃｌｅ ＲＡＣ）で作動する異なるサーバ全体で計数される。時々、マルチコアＣＰＵは各コア毎に計数される。ＣＰＵ／コア当たりの価格は、ＣＰＵのクロック速度および後で追加されたＣＰＵの限界性能寄与とは関係なく同一である。この限界性能寄与に関し、マルチＣＰＵ構成では、ＳＭＰおよび／またはクラスタ構成のいずれでも、プロセッサがシステムに追加されると、プロセッサの各々からの限界効用が縮小することが認められる。追加された１０番目のプロセッサがもたらす寄与は、最初のプロセッサよりずっと小さい。これは、支払いが全てのプロセッサに対して均等であるが、追加プロセッサ当たりの追加限界効用がますます低下し、したがって顧客の観点からは非効率性を生み出すことを意味する。さらに、顧客が感じるのは、彼らはＤＢＭＳソフトウェアによるＣＰＵの非効率的な利用に対して割増料金を支払わなければならず、ＤＢＭＳの製造供給元は彼らのソフトウェア製品のＣＰＵ効率性を改善することに対し後ろ向きの動機を持つということである。容量を最も効率的に提供するようにシステムを再構成するより、所要の容量に達するまでＣＰＵを追加する方が、プロバイダにとっては費用効率が高い。

本発明の実施形態のＤＢＭＳソフトウェアライセンス価格決定モデルは、クライアントが自分の受けるサービスに対して支払う、つまりクライアントが支払うためのパラメータが、得られる利益に直接関係することが分かる、価値ベースの価格決定モデルを生成することを目指している。したがって本発明の実施形態は、顧客の観点からＤＢＭＳシステムの実際の性能を価格決定の基礎にする。したがって、１サブスクライバ当たり、または１ＣＰＵ当たり等のテクニカルパラメータではなく、最大トランザクションスループット等のパラメータが使用される。

本発明の実施形態のＤＢＭＳライセンス価格決定モデルは、システムの実際の最大スループットに基づく。
ソフトウェアライセンス価格＝（１秒当たりのスループット数）^＊×（１スループット当たりの価格）^＊＊
＊スループットは、次のよって測定することができる。
１．データベースの１秒当たりのトランザクションカウント。
２．全てのクエリおよび返却結果を含め、データベースクライアントとデータベースサーバとの間の通信の全データベーストランザクションビットレート。全トランザクションビットレートは１秒当たりのメガビット数単位で測定される。
^＊＊１スループット当たりの価格は、次に関連付けられる。
１．ＧＢに関するデータベースの容量。
２．サブスクライバ／ユーザの総数。
３．または、固定金額とすることもできる。

価格決定の好適な態様は、クライアントが、ソフトウェアの使用量によって導出される重要な性能値であるスループット単位毎に直接支払うことである。

１スループット当たりの価格：
ＧＢ＝＜３ ３０００ドル
ＧＢ＝＜６ ４０００ドル
ＧＢ＞６ ５０００ドル

過去における低い要求とは対照的に、毎秒当たりの非常に高いスループットがますます必要になっている。この必要性の高まりは、ＩＰ電話サービスの展開が成長するにつれて、劇的に増大することが予想される。過去に、顧客は非効率に対して喜んで支払いを行なったが、本発明の実施形態はその必要性を取り除く。支払いはトランザクションのスループットに直接結び付けられる。クライアントは、主要な価値であるシステムの総合最大スループットに対して支払いを行ない、支払いはＣＰＵの数またはサブスクライバの数等の他の技術的パラメータには結びつかない。

この特許の存続期間中に、多数の関連する装置およびシステムが開発されることが予想され、本書における用語の範囲、特にネットワーキング、データベース管理、ＱｏＳ、およびスループットといった用語の範囲は、全てのそのような新しい技術を先験的に含むことを意図している。

明確にするため別個の実施態様の文脈で説明されている本発明の特定の特徴は単一の実施態様に組み合わせて提供することもできることは分かるであろう。逆に、簡潔にするため単一の実施態様の文脈で説明されている本発明の各種の特徴は別個にまたは適切なサブコンビネーションで提供することもできる。

本発明はその特定の実施態様によって説明してきたが、多くの別法、変更および変形があることは当業者には明らかであることは明白である。従って、本発明は、本願の請求項の精神と広い範囲の中に入るこのような別法、変更および変形すべてを包含するものである。本願で挙げた刊行物、特許および特許願はすべて、個々の刊行物、特許および特許願が各々あたかも具体的にかつ個々に引用提示されているのと同程度に、全体を本明細書に援用するものである。さらに、本願で引用または確認したことは本発明の先行技術として利用できるという自白とみなすべきではない。

先行技術の全共有分散キャッシュコヒーレンシアーキテクチャを示す。 データが異なるデータノードにパーティション化され、各パーティションが全共有分散キャッシュコヒーレンシとして管理される、先行技術の無共有アーキテクチャを示す。 全てのデータがメモリ内に維持され、異なるコンピューティングユニットの２つ以上のメモリの間で完全に複製され、かつ同期化される、先行技術の耐障害性メモリ内データリポジトリアーキテクチャを示す。 仮想パーティションとコンピューティングユニットとの間の動的マッピングのために交換チャネルネットワーキングが使用される、本発明の好適な実施形態に係るアーキテクチャを示す簡略図である。 図４のアーキテクチャを示す簡略図である。 本発明の好適な実施形態に係る階層ベースの仮想パーティションを使用して表わすことのできる、階層状のデータ編成のためのツリー構造を示す。 本発明の好適な実施形態に係る階層ベースの仮想パーティションを使用して表わすことのできる、階層状のデータ編成のためのツリー構造を示す。 本発明の好適な実施形態に係る階層ベースの仮想パーティションを使用して表わすことのできる、階層状のデータ編成のためのツリー構造を示す。 本発明の好適な実施形態に係るパーティショニング手順を示す簡略フローチャートである。 ２つのレベルのサブチャネルを有するチャネルを示し、かつさらに、本発明の好適な実施形態に係るチャネル階層内のマイクロリポジトリの割当てを示す。 仮想パーティションが本発明の好適な実施形態に係る階層ベースである、図４のアーキテクチャの部分を示す簡略ブロック図である。 本発明の好適な実施形態を使用する３フェーズコミット書込み動作を示す簡略フローチャートである。 仮想パーティションが本発明の好適な実施形態に係る階層ベースである、図４のアーキテクチャの部分を示す簡略ブロック図である。 本発明の好適な実施形態に係る障害復旧動作の簡略フローチャートを示す。 本発明の好適な実施形態に係る自己回復動作の簡略フローチャートを示す。 本発明の好適な実施形態に係る、自己回復機構の一部としてのサーバおよびデータのマイクロリポジトリの再マッピングのブロック図である。 本発明の好適な実施形態に係る、自己回復機構の一部としてのサーバおよびデータのマイクロリポジトリの再マッピングのブロック図である。 本発明の好適な実施形態に係る、チャネル交換網グラフ兼マルチキャストスパンニングツリーである。 顧客機器を示す本発明の好適な実施形態に係るネットワークの一部のブロック図である。 本発明の好適な実施形態に係る分散チャネルハッシュ実現を示すブロック図である。 本発明の好適な実施形態に係る分散チャネルハッシュ実現を示すブロック図である。 本発明の好適な実施形態に従って、二次キーを使用してデータのマッピングをいかに実行することができるかを示すブロック図である。 本発明の好適な実施形態に従って、二次キーを使用してデータのマッピングをいかに実行することができるかを示すフローチャートである。 ３部および５部構成のストレージならびに２つの異なる可用性レベルの場合のデータストレージユニットＸＤＢの数に対する１秒当たりの演算実行回数による性能および可用性を示すグラフである。 本発明の好適な実施形態に従ってプロセス状態をいかに維持することができるかを示すブロック図である。 本発明の好適な実施形態に従ってプロセス状態をいかに維持することができるかを示すブロック図である。 本発明の好適な実施形態に係るプロセス状態の維持のための状態データベースの使用を示すブロック図である。 チャネルがグループ毎に切り換えられる、本発明の好適な実施形態を示す簡略図である。

Claims (43)

1. 各々独立にアクセス可能な仮想パーティションに配列されるデータベースユニット、
   複数のデータ処理ユニット、および
   前記仮想パーティション間で前記データ処理ユニットを交換し、それによってデータ処理容量をそれぞれの仮想パーティションに動的に割り当てるための交換網
   を含むデータアクセスシステム。
2. 前記交換網は、スイッチングユニットの相互接続を含む、請求項１に記載のデータアクセスシステム。
3. 各データベースユニットは、それぞれのネットワークチャネルとして独立にアクセス可能である、請求項１に記載のデータアクセスシステム。
4. データにハッシュプロセスを実行するためのハッシュユニットをさらに含み、データは前記ハッシュプロセスの結果を介してそれぞれのデータベースユニットに割り当てられる、請求項１に記載のデータアクセスシステム。
5. データは一次キーおよび少なくとも１つの二次キーを有するレコードの形で割り当てられ、ハッシュプロセスは前記一次キーに対して実行される、請求項４に記載のデータアクセスシステム。
6. それぞれの二次キーに基づく検索クエリが前記一次キーにルータを介して関連付けられることができるように、二次キーと前記ハッシングされた一次キーとの間の関係を表にする少なくとも１つのルータで構成される、請求項５に記載のデータアクセスシステム。
7. それぞれの二次キーに基づく検索クエリが前記一次キーに内部インデックステーブルを介して関連付けられることができるように、二次キーと前記ハッシングされた一次キーとの間の関係をマッピングする、少なくとも１つのさらなる自動的に管理された内部インデックステーブルで構成される、請求項５に記載のデータアクセスシステム。
8. データは、少なくとも２つのデータパーティションにわたって少なくとも一度複製される、請求項１に記載のデータアクセスシステム。
9. 競合する書込み動作間の調停を行なうコーディネータとして前記データ処理ユニットの１つを動的に割り当てるための選定機能を含む、請求項１に記載のデータアクセスシステム。
10. 前記コーディネータは、コーディネータとして継続しているという信号を規則正しく送るように構成され、前記選定機能は前記規則正しい信号が終わったときに前記動的に割り当てることを繰り返すように構成される、請求項９に記載のデータアクセスシステム。
11. 前記動的に割り当てることによって中断された書込み動作は、前記動的に割り当てることが終わったときに、最も進行した回復可能位置から再開する、請求項１０に記載のデータアクセスシステム。
12. 前記コーディネータは、レコード変更動作後にレコードに一意の認証を割り当て、それによって前記レコードのバージョンを比較できるようにするように構成される、請求項９に記載のデータアクセスシステム。
13. データは少なくとも３つのキーを有するレコードの形で割り当てられ、各レコードは前記キーのうちの１つに基づく一次アドレスおよび前記キーの残りのものに基づく二次アドレスを割り当てられる、請求項４に記載のデータアクセスシステム。
14. 二次アドレスを対応する一次アドレスに解決するためのレゾリューションユニットを含み、それによって、対応する一次キーを使用して二次キーによって定義されるレコードを見つける、請求項１３に記載のデータアクセスシステム。
15. 前記レゾリューションユニットは少なくとも１つのルータを含む、請求項１４に記載のデータアクセスシステム。
16. 前記レゾリューションユニットは少なくとも１つのバックアップルータをさらに含む、請求項１５に記載のデータアクセスシステム。
17. スイッチング機構は、全ての前記仮想パーティションの可用性が維持されるように、前記データ処理ユニットの１つまたはそれ以上の故障後にデータパーティションバージョンを前記データ処理ユニットの残りのものに再割り当てするように構成される、請求項８に記載のデータアクセスシステム。
18. 各仮想パーティションは、所定のデータ処理ユニットの故障後に全てのデータがアクセス可能なままであるように、予め決められた数のデータ処理ユニットに格納される、請求項１に記載のデータアクセスシステム。
19. 前記予め決められた数は少なくとも３である、請求項１８に記載のデータアクセスシステム。
20. 前記少なくとも３である数は奇数であり、それによって前記データの完全性を確実にするためにコピーされた仮想パーティション間の多数決を可能にする、請求項１９に記載のデータアクセスシステム。
21. 前記奇数は少なくとも５である、請求項２０に記載のデータアクセスシステム。
22. 前記データアクセスシステムの個々の顧客による使用量を測定するための使用測定機能、および前記顧客に顧客の最大使用量に基づいて課金する課金機能をさらに含む、請求項１に記載のデータアクセスシステム。
23. データ処理ユニット、
    データ格納ユニット、
    前記データ処理ユニットと前記データ格納ユニットを動的に交換するための、それらの間のスイッチングシステム、および
    前記データアクセスシステムの個々の顧客による使用量を測定するための使用測定機能、および前記顧客に顧客の最大使用量に基づいて課金する課金機能
    を含むデータアクセスシステム。
24. データクエリ構成を提供すること、
    前記データクエリ構成から分離したデータ格納構成を提供すること、および
    現在のクエリの影響下で前記データ格納構成と前記データクエリ構成を動的に接続するスイッチングシステムを提供すること
    を含む、高い可用性で高いスケーラビリティのデータ格納およびクエリシステムを提供する方法。
25. 前記データ格納構成を複数のチャネルとして提供することを含む、請求項２４に記載の方法。
26. 各データ項目をレコードとして格納すること、および予め決められた数の前記チャネルにおいて所定のデータレコードのコピーを提供することを含む、請求項２５に記載の方法。
27. 前記予め決められた数は奇数である、請求項２６に記載の方法。
28. 前記データの完全性を確実にするために、前記奇数のコピー間で多数決を使用することをさらに含む、請求項２７に記載の方法。
29. 前記データレコードのフィールドを一次キーとして設定すること、および前記一次キーを前記チャネルにアドレス指定するためにハッシングすることを含む、請求項２６に記載の方法。
30. 前記データレコードのフィールドを二次キーとして設定すること、および前記二次キーと前記一次キーを相関させるために少なくとも１つのルータを提供することを含む、請求項２９に記載の方法。
31. 前記チャネルは、パブリッシュサブスクライブチャネルである、請求項２５に記載の方法。
32. 前記データ格納構成は複数のデータ格納ユニットを含み、方法は複数のデータ格納ユニットにおいて複数コピーでデータを格納すること、および所定のデータ格納ユニットの故障を検出すると前記所定のデータ格納ユニットにおいて格納されるデータユニットの他の場所からさらなるコピーを作成することを含む、請求項２４に記載の方法。
33. 前記データはクエリを介してアクセスされ、所定のクエリに対する応答は、前記データに関する現在の状態に依存する、請求項３２に記載の方法。
34. それぞれのデータ格納ユニット間の明示的な状態同期化によって、少なくとも１つのデータ格納ユニットの故障の場合に前記現在の状態を保持することをさらに含む、請求項３３に記載の方法。
35. 前記明示的な状態同期化は、プル同期化である、請求項３４に記載の方法。
36. 前記明示的な状態同期化は、プッシュ同期化である、請求項３４に記載の方法。
37. 顧客による使用量を測定することをさらに含む、請求項２４に記載の方法。
38. 前記使用量は最大使用量として測定される、請求項３７に記載の方法。
39. 前記最大使用量に基づいて前記顧客に課金することを含む、請求項３８に記載の方法。
40. データ格納資源の動的パーティショニングを提供すること、
    データ処理資源の動的割当てを提供すること、および
    前記データ格納資源の前記動的パーティショニングが前記データ処理資源の前記動的パーティショニングから切り離されるように、前記データ格納資源と前記データ処理資源との間の動的スイッチングを使用すること
    を含む、データ格納資源およびデータ処理資源を有するデータリポジトリを提供する方法。
41. 前記データ格納資源において少なくとも２つの場所に個々のデータ項目をコピーすること、および前記少なくとも２つの場所にグループアドレスを提供することを含む、請求項４０に記載の方法。
42. 故障を検出すると、前記リポジトリが前記検出の前の状態を回復するように、前記データリポジトリに複数の状態を割り当てることを含む、請求項４０に記載の方法。
43. 各データ項目が一次キーおよび１つまたはそれ以上の二次キーを有する、複数のデータパーティションおよびデータ項目を含む無共有データレポジトリであって、前記一次キーは前記データパーティションを定義し、そして各二次キーは、二次キーによってパーティション化されるさらなる自動的に管理された内部インデックステーブルとして実現され、内部インデックステーブルは、それぞれの二次キーに基づく検索クエリが前記一次キーに前記内部インデックステーブルを介して関連付けられることができるように、二次キーと前記パーティション化された一次キーとの間の関係をマッピングする、無共有データレポジトリ。

Images