(57)【特許請求の範囲】
【請求項１】
分散コンピューティング環境においてキーの管理をサポートするための方法であって、
複数の２進キーを格納する複数のノードを含む２進基数木を形成するステップと、
前記２進基数木をバッファにシリアル化するステップと、
前記バッファにインターフェイスを提供するステップとを含み、前記インターフェイスは、複数の参照を形成するように構成され、前記複数の参照の各々は、前記２進基数木のうち１つのノードおよび前記複数の２進キーのうち１つの２進キーに関連付けられ、
前記方法は、前記複数の参照を複数の参照元に提供するステップをさらに含み、これによって、前記複数の参照元は、前記複数の２進キーのコピーを保有することなく、前記複数の参照から前記複数の２進キーを取得可能である、方法。
【請求項２】
前記２進基数木内に複数のサテライトノードを形成するステップをさらに含み、
前記複数のサテライトノードは、前記２進基数木における位置を示す情報を用いて、拡張される、請求項１に記載の方法。
【請求項３】
前記２進基数木内に複数のサテライトノードを形成するステップをさらに含み、
前記複数のサテライトノードは、前記２進基数木における位置を示す位置情報を用いて、拡張され、
前記サテライトノードに暗号化された前記位置情報を用いて、前記２進基数木の走査効率を改善するステップをさらに含む、請求項１に記載の方法。
【請求項４】
前記インターフェイスは、複数の参照を形成するように構成され、前記複数の参照の各々は、前記２進基数木のうち１つのノードおよび前記複数の２進キーのうち１つの２進キーに関連付けられ、
前記バッファにインターフェイスを提供するステップは、前記バッファにバイトシーケンスインターフェイスを提供するステップを含み、前記バイトシーケンスインターフェイスは、複数の参照を形成するように構成され、前記複数の参照の各々は、前記２進基数木のノードのうち、前記バイトシーケンスインターフェイスに位置する１つのノードの位置および前記複数の２進キーのうち１つの２進キーに関連付けられる、請求項１〜３のいずれか１項に記載の方法。
【請求項５】
前記インターフェイスは、複数の参照を形成するように構成され、前記複数の参照の各々は、前記２進基数木のうち１つのノードおよび前記複数の２進キーのうち１つの２進キーに関連付けられ、
前記バッファにインターフェイスを提供するステップは、前記バッファにバイトシーケンスインターフェイスを提供するステップを含み、前記バイトシーケンスインターフェイスは、複数の参照を形成するように構成され、前記複数の参照の各々は、前記２進基数木のノードのうち、前記バイトシーケンスインターフェイスに位置する１つのノードの位置および前記複数の２進キーのうち１つの２進キーに関連付けられ、
前記バッファにインターフェイスを提供するステップは、前記バイトシーケンスインターフェイスを用いて、byteAt(n)メソッドをサポートするステップを含み、前記byteAt(n)メソッドは、前記バイトシーケンスインターフェイスのｎ番目位置でバイトを返答する、請求項１〜３のいずれか１項に記載の方法。
【請求項６】
前記インターフェイスは、複数の参照を形成するように構成され、前記複数の参照の各々は、前記２進基数木のうち１つのノードおよび前記複数の２進キーのうち１つの２進キーに関連付けられ、
前記バッファにインターフェイスを提供するステップは、前記バッファにバイトシーケンスインターフェイスを提供するステップを含み、前記バイトシーケンスインターフェイスは、複数の参照を形成するように構成され、前記複数の参照の各々は、前記２進基数木のノードのうち、前記バイトシーケンスインターフェイスに位置する１つのノードの位置および前記複数の２進キーのうち１つの２進キーに関連付けられ、
前記バッファにインターフェイスを提供するステップは、前記バイトシーケンスインターフェイスを用いて、length()メソッドをサポートするステップを含み、前記length()メソッドは、前記バイトシーケンスインターフェイスのノードに示されたデータのバイト数を決定することができる、請求項１〜３のいずれか１項に記載の方法。
【請求項７】
前記複数の参照元は、複数の逆索引を含み、
各逆索引は、１セットの参照を含む、請求項１〜６のいずれか１項に記載の方法。
【請求項８】
前記複数の参照元は、複数の逆索引を含み、
各逆索引は、１セットの参照を含み、
各逆索引は、１セットの２進キーを保有することに比べて、メモリ負荷を低減する、請求項１〜６のいずれか１項に記載の方法。
【請求項９】
前記２進基数木内の各ノードを、前記ノードに関連するキーに関連付けられた値に対応するアドレスに関連付けるステップをさらに含む、請求項１〜８のいずれか１項に記載の方法。
【請求項１０】
複数の前記キーに関連付けられた値に対応する複数のアドレスを保持するlongストレージアレイを形成するステップと、
前記２進基数木内の各ノードを前記longストレージアレイ内のスロットに関連付けることによって、各ノードを前記ノードに関連するキーに関連付けられた値に対応するアドレスに関連付けるステップとをさらに含む、請求項１〜９のいずれか１項に記載の方法。
【請求項１１】
分散コンピューティング環境においてキーの管理をサポートするためのシステムであって、
マイクロプロセッサとメモリとを含むコンピュータシステムと、
前記コンピュータシステム上で動作する前記分散コンピューティング環境のサーバノードとを備え、
前記サーバノードは、
複数の２進キーを格納する複数のノードを含む２進基数木を形成し、
前前記２進基数木をバッファにシリアル化し、
前記バッファにインターフェイスを提供するように構成され、前記インターフェイスは、複数の参照を形成するように構成され、前記複数の参照の各々は、前記２進基数木のうち１つのノードおよび前記複数の２進キーのうち１つの２進キーに関連付けられ、
前記サーバノードは、前記複数の参照を複数の参照元に提供するように構成され、これによって、前記複数の参照元は、前記複数の２進キーのコピーを保有することなく、前記複数の参照から前記複数の２進キーを取得可能である、システム。
【請求項１２】
機械可読プログラム命令を含むコンピュータプログラムであって、
前記機械可読プログラム命令は、コンピュータシステムによって実行されると、前記コンピュータシステムに、請求項１〜１０のいずれか１項に記載の方法を実行させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
著作権の表示
この特許文書の開示の一部には、著作権保護の対象となるものが含まれている。著作権者は、特許商標庁の特許ファイルまたは記録に掲載された特許文書または特許開示の複製に対しては異議を唱えないが、その他の場合、すべての著作権を留保する。
【０００２】
発明の分野
本発明は、一般にコンピュータシステムに関し、特に分散データグリッドに関する。
【発明の概要】
【課題を解決するための手段】
【０００３】
概要
本開示は、実施形態において、分散コンピューティング環境内でキーの管理をサポートすることができるシステムおよび方法を記載する。システムは、２進基数木を用いて、２進キーを格納することができ、２進キーは、分散コンピューティング環境内の複数の参照元によって参照される。さらに、システムは、分散コンピューティング環境内の複数の参照元によって参照される２進キーに関連付けられる２進基数木内のノードの参照を形成することができる。各参照元は、２進キーのコピーをローカルに保管する必要なく、２進基数木内のノードの参照を用いて、２進キーを取得することができる。
【０００４】
また、本開示は、分散コンピューティング環境内で参照ストアをサポートすることができるシステムおよび方法を記載する。システムは、チケットを参照ストアに関連付けることができ、参照ストアは、複数の参照を含む。また、システムは、チケットを用いて、参照ストアを分散コンピューティング環境内の１つ以上のコンシューマに公開することができる。参照ストアは、格納する必要がある参照の数に応じて、拡大または縮小することができる。さらに、システムは、参照ストアに生じた１つ以上の変更に関する情報を１つ以上のコンシューマに通知することができる。
【０００５】
本発明のこれらのおよび他の目的および利点は、当業者なら、添付図面を参照して、さまざまな実施形態の以下の説明から分かるであろう。
【図面の簡単な説明】
【０００６】
【図１】本発明の一実施形態に従った分散データグリッドを示す図である。
【図２】本発明の一実施形態に従って、分散コンピューティング環境においてゼロコピー２進基数木の使用を示す図である。
【図３Ａ】本発明の一実施形態に従って、分散コンピューティング環境においてゼロコピー２進基数木を示す図である。
【図３Ｂ】本発明の一実施形態に従って、分散コンピューティング環境においてゼロコピー２進基数木を作成する方法を示す図である。
【図４】本発明の一実施形態に従って、分散コンピューティング環境内の参照ストアを示す図である。
【図５】本発明の一実施形態に従って、分散コンピューティング環境内の参照ストアを示す図である。
【図６】本発明の一実施形態に従って、分散コンピューティング環境内の参照ストアを作成する方法を示す図である。
【発明を実施するための形態】
【０００７】
詳細な説明
本開示は、分散コンピューティング環境内でキーの管理をサポートすることができるシステムおよび方法を記載している。システムは、２進基数木を用いて、２進キーを格納することができ、２進キーは、分散コンピューティング環境内の複数の参照元によって参照される。さらに、システムは、分散コンピューティング環境内の複数の参照元によって参照される２進キーに関連付けられる２進基数木内のノードの参照を形成することができる。各参照元は、２進キーのコピーをローカルに保管する必要なく、２進基数木内のノードの参照を用いて、２進キーを取得することができる。また、本開示は、さまざまなサイズの参照セットをメモリに効率的に格納するための参照ストアを記載している。本開示に記載の２進キーを格納する２進基数木をサポートするシステムおよび方法並びに参照ストアは、図１を参照して以下に説明する分散データグリッドに特に有用である。本開示に記載の２進キーを格納する２進基数木をサポートするシステムおよび方法並びに参照ストアは、さまざまな代替の分散コンピューティング環境およびアプリケーションに適用することができる。
【０００８】
以下の説明において、本発明は、限定ではなく例示として、添付の図面に示される。本開示において、さまざまな実施形態の言及は、必ずしも同一の実施形態に限定されず、少なくとも１つの実施形態を意味する。特定の実装形態を説明する場合、これらの特定の実装形態は、例示のみの目的で提供されていることを理解すべきである。当業者なら、本発明の範囲および精神から逸脱することなく、他の要素および構成を使用できることを理解するであろう。
【０００９】
場合によって、本発明の完全な説明を提供するように、多数の具体的な詳細を記載する。しかしながら、これらの具体的な詳細がなくても、本発明を実施できることは、当業者にとって明らかであろう。また、場合によって、本発明を不明瞭にしないように、周知の特徴は、詳細に記載されない。
【００１０】
本発明は、特定の機能の実行およびそれらの関係を示す機能性構成ブロックを用いて説明される。これらの機能性構成ブロックの境界は、通常、説明の便宜上、本開示に任意に定義される。したがって、同様の要素によって実行されるように示された機能は、代替的な実施形態において、異なる要素によって実行されてもよい。代替的には、別々の要素によって実行されるように示された機能は、１つの要素によって実行されてもよい。特定の機能およびそれらの関係が適切に実行される限り、代替的な境界を定義してもよい。したがって、これらの代替的な境界のいずれも、本発明の範囲および精神内に含まれる。
【００１１】
共通の参照番号を使用して、図面および詳細な説明における同様の要素を示す。したがって、他の箇所で図示された要素を説明する場合、図面に使用されている参照番号は、必ずしもこの図面に対応する詳細な説明に記載する必要がない。３桁の参照番号のうち、最初の数字は、要素が最初に現れる図面の順番を示す。
【００１２】
分散データグリッド
分散データグリッドとは、分散型環境またはクラスタ化環境において情報および関連動作、例えば演算を管理するために、複数のコンピュータサーバが１つ以上のクラスタに協働して動作するシステムを指す。分散データグリッドを使用して、サーバ間に共有されているアプリケーションオブジェクトおよびデータを管理することができる。分散データグリッドは、短い応答時間、高い処理量、予測可能な拡張性、継続的な可用性、情報の信頼性を提供する。その結果、分散データグリッドは、計算集約型ステートフル中間層アプリケーションの使用に適している。特定の例において、分散データグリッド、例えばOracle（登録商標）Coherenceデータグリッドは、高性能を達成するように情報をインメモリに格納し、その情報のコピーを複数のサーバ間に同期するように冗長性を採用しているため、サーバの故障時に、システムの復元性およびデータの継続的な可用性を確保する。
【００１３】
以下の記載において、分割キャッシュを有するOracle（登録商標）Coherenceデータグリッドを説明する。しかしながら、当業者であれば、本発明の範囲から逸脱することなく、例えば上記の概要に記載された発明を当該技術分野に知られている任意の分散データグリッドに適用することができることを理解するであろう。さらに、本発明の完全な説明を提供するために、Oracle（登録商標）Coherence分散データグリッドの多くの具体的な詳細を記載するが、本発明は、これらの特定の詳細がなくても、分散データグリッドに実施することができる。したがって、いくつかの実施形態において、本発明を具体化する分散データグリッドの特定の実装は、本発明の範囲から逸脱することなく、以下に説明する分散データグリッドの特定の特徴を含まなくてもよく、および／または以下に説明する分散データグリッドの特定の特徴と異なる特徴またはその変更特徴を含んでもよい。
【００１４】
図１は、データを格納し、クライアント１５０にデータの利用を提供する分散データグリッド１００の例を示している。「データグリッドクラスタ」または「分散データグリッド」は、分散型環境またはクラスタ化環境において情報および関連動作、例えば計算を格納および管理するために、１つ以上のクラスタ（例えば、１００ａ、１００ｂ、１００ｃ）に協働して動作する複数のコンピュータサーバ（例えば、１２０ａ、１２０ｂ、１２０ｃおよび１２０ｄ）を含むシステムを指す。分散データグリッド１００は、例として、クラスタ１００ａ内に５つのデータノード１３０ａ、１３０ｂ、１３０ｃ、１３０ｄおよび１３０ｅを有する４つのサーバ１２０ａ、１２０ｂ、１２０ｃおよび１２０ｄを含むものとして図示されているが、任意数のクラスタを含むことができ、各クラスタ内に任意数のサーバおよび／または任意数のノードを含むことができる。分散データグリッドは、高性能を達成するように情報をインメモリに格納し、その情報のコピーを複数のサーバ間に同期するように冗長性を採用しているため、サーバの故障時に、システムの復元性およびデータの継続的な可用性を確保することができる。一実施形態において、分散データグリッド１００は、例えば、上記の概要および以下の詳細な説明に記載される本発明を実現する。
【００１５】
図１に示すように、分散データグリッドは、協働して動作する多数のサーバ（例えば、１２０ａ、１２０ｂ、１２０ｃおよび１２０ｄ）の間にデータを分散することによって、データの記憶および管理機能を提供する。データグリッドクラスタの各サーバは、例えば、１〜２個のプロセッサソケットを備え、各プロセッサソケットに２〜４個のＣＰＵコアを配置した「汎用ｘ８６」サーバハードウェアプラットフォームなどの従来のコンピュータシステムであってもよい。各サーバ（例えば、１２０ａ、１２０ｂ、１２０ｃおよび１２０ｄ）は、例えば、１つ以上のＣＰＵ、ネットワークインターフェイスカード（ＮＩＣ）、および最低４ＧＢ最大６４ＧＢまたはそれ以上のＲＡＭを含むメモリを備えるように構成される。図示されたサーバ１２０ａは、ＣＰＵ１２２ａ、メモリ１２４ａおよびＮＩＣ１２６ａ（これらの要素は、他のサーバ１２０ｂ、１２０ｃ、１２０ｄにも存在するが、図示されていない）を備える。必要に応じて、各サーバは、溢流記憶容量を提供するために、フラッシュメモリ（例えば、ＳＳＤ１２８ａ）を備えてもよい。ＳＳＤを備える場合、その容量は、好ましくはＲＡＭの容量の１０倍である。データグリッドクラスタ１００ａ内のサーバ（例えば、１２０ａ、１２０ｂ、１２０ｃおよび１２０ｄ）は、高帯域幅のＮＩＣ（例えば、ＰＣＩ−ＸまたはＰＣＩｅ）を介して、高性能（例えば、ギガビットイーサネット（登録商標）またはそれ以上）ネットワークスイッチ１２０に接続される。
【００１６】
故障時にデータを損失する可能性を回避するために、クラスタ１００ａは、好ましくは最低４つの物理サーバを含むが、典型的な実装として、より多くのサーバを含んでもよい。各クラスタに存在するサーバが多くなればなるほど、フェイルオーバ（failover）およびフェイルバック（failback）がより効率的になり、サーバの故障によってクラスタに与える影響が軽減される。サーバ間の通信時間を最短にするために、各データグリッドクラスタは、理想的には、サーバ間にシングルホップ通信を提供する単一のスイッチ１０２に接続される。したがって、クラスタは、スイッチ１０２上のポート数によって制限される。よって、典型的なクラスタは、４〜９６個の物理サーバを含む。
【００１７】
分散データグリッド１００の殆どの広域ネットワーク（ＷＡＮ）構成において、ＷＡＮ内の各データセンタは、相互独立しているが、相互接続されたデータグリッドクラスタ（例えば、１００ａ、１００ｂおよび１００ｃ）を備える。ＷＡＮは、例えば図１に示されたクラスタよりも多くのクラスタを含んでもよい。さらに、相互接続されているが相互独立しているクラスタ（例えば、１００ａ、１００ｂ、１００ｃ）を使用することによって、および／または相互接続されているが相互独立しているクラスタを相互遠隔であるデータセンタに配置することによって、分配型データグリッドは、自然災害、火災、洪水、長期間の電力損失などによって、１つのクラスタ内のすべてのサーバが同時に喪失しないように、安全性のあるデータおよびサービスをクライアント１５０に提供することができる。企業および地区の全体に亘って維持されているクラスタは、企業データの自動バックアップ記憶および高可用性サービスを構成する。
【００１８】
１つ以上のノード（例えば、１３０ａ、１３０ｂ、１３０ｃ、１３０ｄおよび１３０ｅ）は、クラスタ１００ａの各サーバ（例えば、１２０ａ、１２０ｂ、１２０ｃおよび１２０ｄ）上で動作する。分散データグリッドにおいて、ノードは、例えばソフトウェアアプリケーション、仮想マシンなどであってもよく、サーバは、ノードが動作するオペレーティングシステム、ハイパーバイザ（図示せず）などを含んでもよい。Oracle（登録商標）Coherenceデータグリッドにおいて、各ノードは、Ｊａｖａ（登録商標）仮想マシン（ＪＶＭ）である。サーバのＣＰＵ処理能力および利用可能なメモリに応じて、各サーバは、複数のＪＶＭ／ノードを備えてもよい。分散データグリッドの需要に応じて、ＪＶＭ／ノードを起動、停止、追加および削除することができる。Oracle（登録商標）Coherenceを実行するＪＶＭは、起動時に自動的に結合し、クラスタ化する。クラスタに加入したＪＶＭ／ノードは、クラスタメンバまたはクラスタノードと呼ばれる。
【００１９】
Oracle（登録商標）Coherenceデータグリッドにおいて、クラスタメンバは、ＴＣＭＰ（Tangosol Cluster Management Protocol）を使用して通信する。ＴＣＭＰは、クラスタメンバの検出、クラスタの管理、サービスの提供、およびクラスタメンバ間でデータの送信に使用されているＩＰベースプロトコルである。ＴＣＭＰプロトコルは、完全な信頼性で順序通りに、すべてのメッセージを配信する。基礎のＵＤＰ／ＩＰプロトコルが信頼性のある配信または順序通りの配信を提供しないため、ＴＣＭＰは、行列化された完全非同期ＡＣＫおよびＮＡＣＫに基づくメカニズムを使用することによって、信頼性のあるメッセージ配信を行うと共に、一体化された特定のＩＤを使用することによって、サーバ上で動作するＪＶＭに関連して行列化されたメッセージの順序を保証する。ＴＣＭＰプロトコルは、クラスタサイズに関係なく、ＪＶＭ／ノード毎に３つのＵＤＰ／ＩＰソケット（１つのマルチキャスト、２つのユニキャスト）および６つのスレッドしか必要としない。
【００２０】
データグリッドクラスタの機能は、クラスタノードによって提供されたサービスに依存する。クラスタノードによって提供された各サービスは、特定の機能を有する。各クラスタノードは、クラスタサービスの提供およびクラスタサービスの使用の両方の観点から、多くのクラスタサービスに加入することができる（メンバになることができる）。一部のクラスタサービスは、クラスタ内のすべてのノードによって提供されるが、他のサービスは、クラスタ内の１つのノードのみまたは一部のノードのみによって提供される。各サービスは、データグリッドクラスタ内のサービスを一意に識別するサービス名と、行えるサービスを規定するサービス種類とを有する。（ルートクラスタサービスを除き）データグリッドクラスタのノードによって提供された各サービス種類には、複数の名前付きインスタンスが存在することがある。すべてのサービスは、好ましくは、データ損失なしに、フェイルオーバーおよびフェイルバックを提供する。
【００２１】
クラスタノードによって提供された各サービスインスタンスは、通常、１つのサービススレッドを使用して、サービスの特定の機能を提供する。例えば、あるノードによって提供された分散キャッシュサービスは、そのノードの単一サービススレッドによって提供される。ＪＶＭ／ノードで分散キャッシュのスキーマ定義を解析する場合、サービススレッドは、スキーマに指定された名前でインスタンス化される。このサービススレッドは、スキーマ定義を使用して作成されたキャッシュ内にデータを管理する。一部のサービスは、必要に応じて、サービススレッドに追加の処理リソースを提供するように構成することができる作業スレッドのスレッドプールをサポートする。このサービススレッドは、スレッドプール内の作業スレッドと連携して、特定のサービス機能を提供する。
【００２２】
Oracle（登録商標）Coherenceデータグリッドにおいて、クラスタサービス（例えば、１３６ａ、１３６ｂ、１３６ｃ、１３６ｄ、１３６ｅ）は、クラスタ内のメンバシップおよびサービスを追跡する。各クラスタノードは、常に１つのみのこの種のサービスを実行している。クラスタサービスは、自動的に起動して、クラスタノードをクラスタに加入することができる。クラスタサービスは、他のクラスタノードの検出、クラスタノードの故障（停止）の検出、およびクラスタに利用可能な他のサービスの登録を行う。プロキシサービス（例えば、１３８ｃ）によって、クラスタ外部のクライアントは、（例えば、ＴＣＰを使用して）クラスタに接続することができる。呼び出しサービス（例えば、１３４ｄ）によって、アプリケーションコードは、エージェントを呼び出して、クラスタ内の任意のノードまたは任意のノードグループまたはクラスタ全体に亘って、動作を実行することができる。呼び出しサービスおよびプロキシサービスは、図示では各々が１つのみのノードに設けられていると示されているが、分散データグリッド内の任意数のノード上に、最大すべてのノード上に設けられることができる。
【００２３】
Oracle（登録商標）Coherenceデータグリッドにおいて、分散キャッシュサービス（例えば、１３２ａ、１３２ｂ、１３２ｃ、１３２ｄ、１３２ｅ）は、分散データグリッドにデータ記憶を提供し、クラスタ内のノードが記憶不能に設定されても、クラスタ内のすべてのノード上でキャッシュデータの読み取り／書き込み／記憶を行うことができる。分散キャッシュサービスによって、クラスタノードは、クラスタ１００ａの全体にデータを分散（分配）することができる。これによって、キャッシュ内の各データ断片は、主に１つのみのクラスタノードによって管理（保持）される。分散キャッシュサービスは、putおよびgetなどの記憶操作要求を処理する。分散キャッシュサービスは、分散スキーマ定義に定義され、クラスタのノード間に分配された分散キャッシュ（例えば、１４０ａ、１４０ｂ、１４０ｃ、１４０ｄ、１４０ｅ）を管理する。
【００２４】
パーティションは、分散データグリッドに管理されたデータの基本単位であり、分散キャッシュ（例えば、１４０ａ、１４０ｂ、１４０ｃ、１４０ｄおよび１４０ｅ）に格納される。論理的に、データは、基本パーティション（例えば、１４２ａ、１４２ｂ、１４２ｃ、１４２ｄおよび１４２ｅ）に分配される。これらの基本パーティションは、複数のクラスタノードに分散され、クラスタ内の１つのみのノードがキャッシュ内の各データ断片を格納する。各キャッシュ（例えば、１４０ａ、１４０ｂ、１４０ｃ、１４０ｄおよび１４０ｅ）は、複数のパーティションを保持することができる。各パーティション（例えば、１４２ａ、１４２ｂ、１４２ｃ、１４２ｄ、１４２ｅ）は、１つのデータム（datum）を保持することができ、多くのデータムを保持することもできる。パーティションは、必要または要望に応じて、１つのノードのキャッシュから、別のノードのキャッシュに移行することができる。例えば、クラスタにノードを追加する場合、新しく追加されたノードを含む使用可能なノード間にパーティションを分散するように、これらのパーティションを移行する。非複製型の分散データグリッドには、各パーティション（基本パーティション）は、１つのアクティブコピーしか有しない。しかしながら、通常、各パーティションは、１つ以上のレプリカ／バックアップコピーを有する。これらのレプリカ／バックアップコピーは、別のサーバに格納され、フェイルオーバーに使用される。クラスタのサーバ間に分散されたパーティションにデータを分配するため、データを管理する負荷およびデータを利用する負荷は、クラスタの全体に自動的に分散される。
【００２５】
分散キャッシュサービスは、各データ断片が１つ以上の他のクラスタノードによってバックアップされ、データ損失なしにフェイルオーバーをサポートするように構成することができる。例えば、図１に示すように、各パーティションは、基本パーティション（例えば、濃い色の四角形１４２ａ、１４２ｂ、１４２ｃ、１４２ｄおよび１４２ｅ）および同期されたパーティションの１つ以上のバックアップコピー（例えば、薄い色の四角形１４４ａ、１４４ｂ、１４４ｃ、１４４ｄおよび１４４ｅ）に格納される。各パーティションのバックアップコピーは、同期の元である基本パーティションと異なるサーバ／ノードに格納される。ノード上の分散キャッシュサービスのフェイルオーバーは、パーティションのバックアップコピーを基本パーティションに昇格する必要がある。特定のサーバ／ノードが故障した場合、残りのすべてのクラスタノードは、故障したノードの基本パーティションに対応して保持されたバックアップパーティションを決定する。次に、クラスタノードは、任意のクラスタノード上に保持されているバックアップパーティションを基本パーティションに昇格する（その後、新規バックアップパーティションを作成する）。
【００２６】
分散キャッシュは、データオブジェクトの集合である。各データオブジェクト／データムは、例えば、データベーステーブルの一行に等価することができる。各データムは、データムを識別する特定のキーに関連付けられる。各パーティション（例えば、１４２ａ、１４２ｂ、１４２ｃ、１４２ｄ、１４２ｅ）は、１つのデータムを保持することができ、多くのデータムを保持することもできる。これらのパーティションは、クラスタ内のすべてのノード間に分散される。Oracle（登録商標）Coherenceのデータグリッドにおいて、各キーおよび各データムは、ＰＯＦ（Portable Object Format）と呼ばれる効率的な非圧縮バイナリエンコーディングによってシリアル化されたデータオブジェクトとして、格納される。
【００２７】
特定のデータムを探し出すために、各ノードは、キーをパーティションにマッピングするマップ、例えばハッシュマップを有する。このマップは、クラスタ内のすべてのノードに認識され、クラスタのすべてのノード間に同期され、更新される。各パーティションは、パーティションに関連付けられた各キーをそのパーティションに格納された対応のデータムにマッピングするバッキングマップを有する。分散データグリッド内の任意のノードは、クライアントから、特定のキー／データムに関連付けられた操作を受信することができる。ノードが操作を受信すると、キーが受信ノード上の基本パーティションに関連付けられている場合、ノードは、そのキーに関連付けられた値／オブジェクトを直接に利用することができる。キーが受信ノード上の基本パーティションに関連付けられていない場合、ノードは、操作をそのキーに関連付けられた基本パーティションを保持するノードに直接に（シングルホップで）導くことができる。したがって、各ノードは、ハッシュマップおよびパーティションマップを使用することによって、分散キャッシュにおいて、各キーに対応する各データムを直接利用するまたはシングルホップを介して利用することができる。
【００２８】
いくつかのアプリケーションにおいて、分散キャッシュ内のデータは、最初に、データ１１２を含むデータベース１１０から取り込まれる。データベース１１０内のデータ１１２は、シリアル化され、分散データグリッドのノード間に分配され、分散される。分散データグリッド１００は、データベース１１０のデータ１１２から作成されたデータオブジェクトをサーバ１１０ａ、１２０ｂ、１２０ｃ、１２０ｄのメモリ内のパーティションに格納する。これによって、クライアント１５０および／またはデータグリッド１００内のアプリケーションは、メモリからこれらのデータオブジェクトを直接利用することができる。したがって、分散データグリッド１００からデータオブジェクトの読み出しおよび分散データグリッド１００にデータオブジェクトの書き込みは、遥かに高速になり、データベース１１０を直接使用することよりも、多くの同時接続を達成できる。データのインメモリ複製および保証されたデータ一貫性によって、分散データグリッドは、保管および報告のためにトランザクションをデータベース１１０などの外部データソースに長期保存されるまで、メモリ内でトランザクションを管理することができる。メモリ内のデータオブジェクトに変更があった場合、その変更は、基本パーティションとバックアップパーティションとの間に同期された後、非同期書き込み（ライトバック）を用いてデータベース１１０に書き込まれ、ボトルネックを回避する。
【００２９】
データがクラスタノード間に分散されていることにも関わらず、クライアント１５０は、任意のクラスタノードに接続して、任意のデータを取り出すことができる。このことは、位置透明性（location transparency）と呼ばれ、開発者がキャッシュのトポロジーに基づいてコードを作成する必要がない。いくつかの実施形態において、クライアントは、特定のサービス、例えば特定のノード上のプロキシサービスに接続することができる。他の実施形態において、接続プールまたはロードバランサを使用して、クライアントを特定のノードに導くことができ、クライアントの接続を一部またはすべてのデータノード間に確実に分散することができる。どのように接続されても、分散データグリッド内の受信ノードは、クライアント１５０からタスクを受信することができる。各タスクは、特定のデータムに関連付けられているため、特定のノードによって処理されなければならない。ノードは、特定のデータムに対応するタスク（例えば、キャッシュサービスに対するコール）を受信すると、そのデータムを格納するパーティション、およびそのパーティションに対応するノードを特定する。その後、受信ノードは、例えばリモートキャッシュを呼び出すことによって、タスクを要求されたパーティションを保持するノードに導く。各データムが１つのみのクラスタノードにより管理されているため、ネットワークを経由したアクセスは、「シングルホップ」操作である。この種のアクセスは、ポイントツーポイント（point-to-point）通信を使用するので、インフィニバンド（InfiniBand）などのスイッチドファブリックネットワークを最大限に活用することができるため、拡張性が非常に高い。
【００３０】
同様に、キャッシュ更新動作は、同様のシングルホップポイントツーポイント方法を使用して、基本パーティションを備えるノードおよびパーティションのバックアップコピーを備えるノードの両方にデータを送信する。キャッシュに対する変更は、すべてのバックアップから承認応答を受け取るまで完了していないと見なされる。これによって、データの一貫性が維持され、書き込み操作中にクラスタノードが予期せず故障した場合に、データが損失しないことが保証される。また、分散キャッシュサービスは、一部のクラスタノードを、データを格納するように構成することができ、他のクラスタノードを、データを格納しないように構成することができる。
【００３１】
いくつかの実施形態において、必要に応じて、分散データグリッドは、固体装置（例えば、ＳＳＤ１２８ａ）、最も典型的にはフラッシュドライブを利用して、キャッシュに溢流容量を提供する弾性データ機構を有するように構成される。弾性データ機構を使用する場合、キャッシュは、ＲＡＭまたはＤＩＳＫジャーナルに基づくバッキングマップを使用するように指定される。ジャーナルは、オブジェクトの状態変化を格納するメカニズムを提供する。各データム／値は、特定のキーに関連して記録され、インメモリ木を使用して、データムへのポインタを格納する（小さなデータム／値は、木に直接格納されてもよい）。これにより、一部の値（データ）を固体装置（例えば、ＳＳＤ１２８ａ）に格納すると共に、索引／メモリ木をメモリ（例えば、ＲＡＭ１２４ａ）に格納することができる。弾性データ機構によって、分散データグリッドは、完全にＲＡＭに基づく解決策に比べて、性能を殆ど損なうことなく、各ノードにより多くのデータをサポートすることができる。
【００３２】
上述したOracle（登録商標）Coherenceデータグリッドのような分散データグリッドは、データ操作の遅延問題を解決し、リアルタイムでデータをキャッシュおよび処理することによって、システムの性能を改善することができる。アプリケーションは、データをデータグリッドにキャッシュすることによって、高価なバックエンドデータソースを要求することを回避する。共有データキャッシュは、キャッシュされたデータの一貫性のある単一鏡像を提供する。キャッシュからの読み取りは、バックエンドデータソースのクエリよりも高速であり、アプリケーション層の規模に従って変化する。インメモリ実行は、ボトルネックを軽減し、データの競合を減少し、アプリケーションの応答性を改善する。並列のクエリおよび演算をサポートすることによって、データに基づく計算の性能を改善する。分散データグリッドは、故障許容性を有するため、データの信頼性、正確性、整合性、高可用性および災害復旧性を実現する。分散データグリッドによって、予測可能なコストで、リソース使用率を改善するように、アプリケーションを線形的に且つ動的に拡張することができる。分散データグリッドは、多くのアプリケーションに、データソースを共有する貴重な解決策を提供する。
【００３３】
実施形態において、分散データグリッド１００は、例えば、以下に記載され、図２〜６に示されるように、キーを管理するための１つ以上のゼロコピー２進基数木および／または参照ストアを実装する。特定の実施形態において、ゼロコピー２進基数木は、ＲＡＭまたはＤＩＳＫジャーナルに基づくバッキングマップを参照して、キーを管理するために実装されてもよい。一実施形態において、ＲＡＭまたはＤＩＳＫジャーナルに基づくバッキングマップは、固体装置（例えば、ＳＳＤ１２８ａ）、最も典型的にはフラッシュドライブを利用する分散データグリッドの弾性データ機能と併せて使用され、キャッシュに溢流容量を提供する。分散データグリッドは、ゼロコピー２進基数木を利用することによって、サーバのＲＡＭ内に複数のキーのコピーを保管することに関連するメモリの浪費を低減または排除し、したがって、分散データグリッドの性能を改善する。さらに、分散データグリッド１００は、ゼロコピー２進基数木内に格納されたキーの参照をメモリ効率的な方法で記憶するための参照ストアを実装することができる。
【００３４】
分散データグリッド内のキーの管理
本開示は、例えば図１の分散データグリッドを含む分散コンピューティング環境において、ゼロコピー２進基数木を用いてキーの管理をサポートすることができるシステムおよび方法を記載する。また、本開示は、ゼロコピー２進基数木内に格納されたキーの参照をメモリ効率的な方法で記憶するための参照ストアを記載する。
【００３５】
２進基数木は、トライの一種である。トライは、通常文字列であるキーの動的セットまたは連想配列を格納するために使用される順序付きデータ構造である。２進検索木とは異なり、トライのノードは、そのノードに関連するキーの全体を格納しない。代わりに、木内のノードの位置は、ノードに関連するキーを規定する。一ノードのすべての子孫ノードは、そのノードに関連する文字列の共通プレフィックスを有し、トライのルートは、空文字列に関連付けられる。トライを使用して、キーに関連する値を取得することができる。必ずしもすべてのノードに値を関連する必要がない。トライの一部の内部ノードは、単に追加のノードを参照するものである。むしろ、値は、リーフノードおよび関心のあるキーに対応する一部の内部ノードのみに関連付けられる傾向がある。
【００３６】
基数木は、空間最適化トライを表すデータ構造である。この基数木構造において、親ノードの唯一の子である各ノードは、その親ノードに合併される。通常の木とは異なり、２進基数木は、キーの起点からキーの不等点まで、キーの全体を比較する必要がないため、有利である。２進基数トライにおいて、トライを走査するときに、キーのノード部分を比較することによって、子ノードのうち１つを選択する（例えば、左子ノードの場合、次のビットが１であり、右子ノードの場合、次のビットが０である）。特定の内部ノードのすべての子ノードは、不等点まで同様のプレフィックスを共有する。すなわち、すべての子ノードは、特定の内部ノードから分岐する。２進基数木は、２進キーのセットを空間効率良く格納する方法を提供し、木を走査して所定の２進キーに関連付けられた値を取得する効率的なメカニズムを可能にする。
【００３７】
図２は、ゼロコピー２進基数木を用いて、分散データグリッド内で弾性データ構造をサポートする例を示している。図１に示すように、ノード１３０ａは、ランダムアクセスメモリ（ＲＡＭ１２４ａ）と、固体装置（ＳＳＤ１２８ａ）などのさまざまなディスクに基づく装置との両方を含むことができる。データグリッドクラスタ１００のノード１３０ａは、弾性データ構造を利用することができる。これによって、データグリッドクラスタは、ＳＳＤ１２８ａにデータを格納し、および／または格納速度と近い速度でＳＳＤ１２８ａからデータを読み取ることができる（図１を参照）。図２に示すように、ノード１３０ａは、ＲＡＭジャーナル２１０を用いてデータをインメモリに格納し、フラッシュジャーナル２２０を用いてデータをフラッシュに基づく装置に格納する。ジャーナル２１０および２２０は、データ記憶装置内の値／オブジェクトの一連の変更に関連する状態変化を記録する。さらに、ＲＡＭジャーナル２１０は、フラッシュジャーナル２２０と協働して、ＲＡＭ記憶装置からフラッシュディスク記憶装置へのデータのシームレスオーバーフローを可能にする。異なる方法で、ＲＡＭジャーナル２１０およびフラッシュジャーナル２２０を使用することができる。例えば、ＲＡＭジャーナル２１０およびフラッシュジャーナル２２０は、バックアップマップをサポートする、バックアップ保存をサポートする、および／またはノード１３０ａ内の複合キャッシュ（例えば、ニアキャッシュ）をサポートするために使用することができる。
【００３８】
ノード１３０ａに使用されたジャーナル２１０および２２０の各々は、複数のエントリを含むことができる。例えば、ＲＡＭジャーナル２１０は、ＲＡＭジャーナルエントリ２１２〜２１４を含むことができ、フラッシュジャーナル２２０は、フラッシュジャーナルエントリ２２２〜２２４を含むことができる。システムは、異なるジャーナルエントリ２１２、２１４、２２２および２２４に各々格納された値／オブジェクトの各々に、特定のキーを関連付ける。弾性データ構造に変更を適用すると、各キーは、値／オブジェクトの現在バージョンを含むジャーナルエントリに関連付けられた状態を維持する。したがって、ユーザは、ヒープ２０２に格納された関連キーを用いて、弾性データ構造２００内のジャーナルエントリに格納された値を見い出すことができる。
【００３９】
値を見い出すために、各ジャーナルエントリは、ヒープ２０２に別々に格納されたジャーナルチケットに関連付けられる。ジャーナルチケットは、ＲＡＭジャーナル２１０またはフラッシュジャーナル２２０内のエントリの位置を特定する。ジャーナルチケットは、ヒープから離れて、例えばキーに対応するジャーナルのエントリに格納された値の仮想アドレスを表すことができる。さらに、ジャーナルチケットは、ヒープから離れて格納された値に関連する追加の属性（例えば、削除属性および満期属性）を含むことができる。ジャーナルチケットは、longプリミティブデータ型を使用する。Ｊａｖａ（登録商標）において、longデータ型は、６４ビット符号付き２の補数である。各エントリに関連するジャーナルチケットを格納するために、longストレージアレイ２３０を設けることができる。図２に示すように、longストレージアレイ２３０は、複数の番号付きスロット／行２３２を含む。各スロット／行は、複数のジャーナルチケット２３４のうち１つを含み、必要に応じて、ジャーナルエントリ２３４に関連する複数の属性２３６を含む。longストレージアレイ２３０によって、スロット番号を用いて、スロット／行に位置するジャーナルチケットを取得することができる。このジャーナルチケットを用いて、対応するエントリを格納するジャーナル（ＲＡＭまたはフラッシュ）から、エントリを取得することができる。
【００４０】
しかしながら、リクエスタは、特定のキーに関連するエントリを見い出す必要がある。これを達成する簡単な方法は、各エントリに関連付けられたキーを含む列をlongストレージアレイ２３０に追加することである。しかしながら、この解決策は、すべてのキーのコピーをlongストレージアレイに入れる必要があり、且つ一致するキーの検索操作が高価であるため、望ましくない。代わりに、図２に示すように、ジャーナルエントリに関連するキーを圧縮方法で格納し、キーに応じて、ジャーナルエントリに対応するジャーナルチケットを効率的に取得するために、ゼロコピー２進基数木２４０を形成する。ゼロコピー２進基数木２４０は、２進キーをlongストレージアレイ２３０内のスロット２３２に関連付ける。これによって、２進キーを用いて、ジャーナル２１０、２２０に関連する値を見い出すことができる。
【００４１】
図２に示すように、サーバノード１３０ａは、ゼロコピー２進基数木２４０を用いて、異なるキー２４１〜２４５をノード１３０ａのヒープ２０２に格納する。例えば、ゼロコピー２進基数木２４０に格納されたキー２４１〜２４５は、「ＡＬＢＥＲＴ」２４１、「ＡＬＦＲＥＤ」２４２、「ＡＮＤＲＥＷ」２４３、「ＡＮＴＯＮＩＯ」２４４および「ＡＮＴＯＮＹ」２４５を含む。図２に示すように、ゼロコピー２進基数木２４０に格納されたすべてのキー２４１〜２４５が文字「Ａ」で始まるため、ゼロコピー２進基数木２４０のルートノード２４６は、文字「Ａ」を格納する。さらに、２つのキー「ＡＬＥＲＴ」３３１および「ＡＬＦＲＥＤ」３３２は、文字「ＡＬ」で始まるため、同一の内部ノード２４７を共有する。さらに、キー「ＡＬＢＥＲＴ」３３１は、文字「ＢＥＲＴ」を含むノード２４１を使用し、キー「ＡＬＦＲＥＤ」は、文字「ＦＲＥＤ」を含むノード２４２を使用する。同様に、キー「ＡＮＤＲＥＷ」３３３は、ノード２４６、２４８および２４３を使用し、キー「ＡＮＴＯＮＩＯ」は、ノード２４６、２４８、２４９および２４４を使用し、キー「ＡＮＴＯＮＹ」は、ノード２４６、２４８、２４９および２４５を使用する。説明を容易にするためにアルファベットキーを示しているが、基数木は、通常２進基数木であり、キーは、通常２進数であり、ノードは、２進数内の特定のビットまたはビットの一部を表す。
【００４２】
また、ゼロコピー２進基数木２４０に格納された圧縮キーを表す各ノード２４１〜２４５は、longストレージアレイ２３０内の番号付きスロット２３２のうち１つのスロットにも関連付けられる。これによって、各特定の圧縮キーは、特定のジャーナルチケット２３４を含み且つフラッシュジャーナル２２０またはラムジャーナル２１０内の特定の値／オブジェクトに関連するlongストレージアレイに関連付けられる。したがって、ゼロコピー２進基数木２４０は、２進キーを（long型）ジャーナルチケットに関連付ける２進longマップとして機能する。ジャーナルチケットは、そのキーに関連する値／オブジェクトを含むジャーナルエントリを特定する。さらに、効率を改善するために、非常に小さい値（例えば、７バイトまでの値）は、ヒープから離れてジャーナル２１０、２２０に格納する代わりに、ゼロコピー２進基数木２４０に直接に格納することができる。
【００４３】
図２に示すように、キー「ＡＬＢＥＲＴ」を格納するために使用されたノード２４１は、ジャーナルチケット「０×１１２ｃａ５３０」を格納するlongストレージアレイ２３０のスロット１の参照を含む。キー「ＡＬＦＲＥＤ」を格納するために使用されたノード２４２は、ジャーナルチケット「０×３８ｆｃｅ７８８」を格納するlongストレージアレイ２３０のスロット２の参照を含む。キー「ＡＮＤＲＥＷ」を格納するために使用されたノード２４３は、ジャーナルチケット「０×ｆｄ７３８ｄ８０」を格納するlongストレージアレイ２３０のスロット３の参照を含む。キー「ＡＮＴＯＮＩＯ」を格納するために使用されたノード２４４は、ジャーナルチケット「０×３８１９ｅ６ｃ０」を格納するlongストレージアレイ２３０のスロット４の参照を含む。最後に、キー「ＡＮＴＯＮＹ」を格納するために使用されたノード２４５は、ジャーナルチケット「０×ｂ３８１ｅｆｄ０」を格納するlongストレージアレイ２３０のスロット５の参照を含む。
【００４４】
したがって、図２に示すように、キー「ＡＬＢＥＲＴ」に関連付けられた値を取得する要求が得られたときに、キー「ＡＬＢＥＲＴ」を基数木２４０に適用することによって、キー「ＡＬＢＥＲＴ」に対応するノード２４１を特定する。ノード２４１がlongストレージアレイ２３０のスロット１の参照を含むため、ジャーナルチケット「０×１１２ｃａ５３０」がlongストレージアレイ２３０のスロット１から使用される。ジャーナルチケット「０×１１２ｃａ５３０」は、ヒープから離れてジャーナルのエントリ２２４に格納されたキー「ＡＬＢＥＲＴ」値２２５の仮想アドレスを表す。したがって、システムは、値２２５に関連するキー「ＡＬＢＥＲＴ」を含む要求に応答して、ジャーナルから値２２５を取得することができる。さらに、システムは、このようなコンパクトなデータ構造を利用することによって、非常に大きなデータセットのメタデータ情報を格納することができる。
【００４５】
分散データグリッドにおいて２進基数木の使用は、例えば、２０１４年７月２日に出願され、「分散データグリッド内で弾性データメタデータ圧縮をサポートするためのシステムおよび方法」と題された米国特許出願第１４／３２２５７６号、２０１４年７月２日に出願され、「分散データグリッド内でプッシュバックによるメモリ割当制御をサポートするためのシステムおよび方法」と題された米国特許出願第１４／２９８４５８号、および２０１３年１２月３１日に発行され、「ＲＡＭおよびフラッシュ型メモリを用いて、キャッシュ記憶を管理するための弾性データ技術」と題された米国特許第８６２１１４３号にさらに記載されている。上述した米国特許出願の両方および米国特許は、参照により本開示に組み込まれる。上記文献に記載したように、データのキー２０２、２０３、２０４は、効率的な２進基数木データ構造に圧縮される。この２進基数木は、ＲＡＭディスクおよびフラッシュディスク内のメモリブロックに格納された値／オブジェクトに対応する索引として機能する。
【００４６】
図１の分散データグリッドにおいて、多くのデータ構造がキーを中心にして旋回する。したがって、図２に示すゼロコピー２進基数木２４０は、キーに関連付けられた値／オブジェクトに対して、（木から直接にまたはジャーナルチケットを用いて）演算を実行するための手段を提供する。特に、２進基数木内のノードが、キーの全体ではなく、子ノードを選択するために必要なキーの一部を格納するため、２進基数木の空間効率がよい。分散データグリッドは、値／オブジェクトのパラメータに基づいて、オブジェクトを見い出すことを可能にするおよび／または容易にする複数の索引および逆索引を提供するように構成することもできる。例えば、Oracle（登録商標）Coherenceデータグリッドは、効率的なクエリを実現するように、データに索引を付ける。クエリを適切に実行するように、逆索引を作成することによって、クエリ値に一致するキーを特定する（索引値−＞＜キー＞セット）。索引値が多く存在する場合、多くの＜キー＞セットを保有する必要がある。
【００４７】
従来のシステムにおいて、値／オブジェクトの参照は、キーセットの各メンバに対応する２進キー全体（例えば、「ＡＮＴＯＮＹ」）のコピーを保有する各参照元を必要とする。したがって、各参照元は、２進基数木を用いて値を検索するために、値に対応するキーのバイトコピーを保有しなければならない。例えば、索引／参照元は、セット内の各値／オブジェクトに対応するキーのバイトコピーを保有しなければならない。逆索引は、文字通りに、索引値を満たすオブジェクトに対応するキーのバイトコピーセットである。さらに、複数の参照元が同一のキーを参照する場合、各参照元は、２進キー全体のコピーを保有しなければならないため、２進キー全体の複数のコピーを作成する必要がある。これらの参照元／索引がヒープ上に格納されるため、多くの２進キーの複数のコピーを保有すると、分散データグリッド内でキーの管理に関連するメモリを大幅に浪費してしまう。
【００４８】
ゼロコピー機能
したがって、分散データグリッドまたは他の分散コンピューティング環境の性能を改善するために、望ましくは、多くの２進キー全体の複数のコピーを分散データグリッド内の参照元（例えば、索引など）に保管することによって生じたメモリ浪費を低減することである。したがって、本開示は、分散データグリッド内で多くの２進キーの複数のコピーを保有することによって生じたメモリ浪費を低減または排除するゼロコピー２進基数木をサポートするためのシステムおよび方法を記載する。本発明の実施形態によれば、参照元は、２進キー全体のバイトコピーを保有する代わりに、ゼロコピー２進基数木２４０内のノード位置によって、ゼロコピー２進基数木内のノードの参照を保有する。ゼロコピー２進基数木内のノード位置の参照は、２進キー全体のコピーよりも遥かに少ないメモリを使用するため、多くの２進キーの複数のコピーを保有することによって生じたメモリ浪費を低減または排除し、分散データグリッドまたは他の分散コンピューティング環境の性能を改善することができる。
【００４９】
図２は、本発明の一実施形態に従って、分散コンピューティング環境において２進基数木のゼロコピー機能をサポートすることを示す図である。図２に示すように、分散コンピューティング環境内の複数の参照元２７１〜２７３は、キーのコピーをローカルに保管する必要なく（すなわち、ゼロコピー機能）、ゼロコピー２進基数木２４０に格納された同一のキーを参照することができる。例えば、すべての参照元２７１〜２７３は、リーフノード２４１を介して、同一のキー「ＡＬＢＥＲＴ」を参照することができる。さらに、ゼロコピー２進基数木２４０は、並行変更をしてもよく、不変にしてもよい。したがって、ゼロコピー２進基数木２４０は、適切な２進キー内のバイトにアクセスするための非常に効率的なメカニズムおよびゼロコピー２進基数木２４０のノードを参照する安全な外部参照を提供することができる。
【００５０】
ゼロコピー機能がない場合、各参照元は、参照するキーのコピーを保有する必要がある。例えば、異なる参照元２７１〜２７３の各々は、ゼロコピー２進基数木２４０に格納された２進キー「ＡＬＢＥＲＴ」を参照する外部参照を維持するために、ヒープ２０２上のキー「ＡＬＢＥＲＴ」の別々のコピー２８１〜２８３（すなわち、参照元当たりに１つのコピー）を格納する必要がある。ゼロコピー機能を使用する場合、異なる参照元２７１〜２７３の各々は、キー「ＡＬＢＥＲＴ」の別々のコピー２８１〜２８３を格納する必要がない。したがって、ゼロコピー機能は、分散コンピューティング環境２００内でキーの管理に関連するオンヒープメモリ浪費を大幅に低減することができる。
【００５１】
図２に示すように、２進キーを２進基数木２１０に格納する機能が提供される。２進基数木２１０は、共有バイトを重複排除することができる非常にコンパクトなデータ構造を形成する。２進基数木は、キャッシュを開始するときに開始され、キャッシュに関連するキーを格納する。通常、バイト配列を参照する場合、これらのバイトのコピーが必要である。しかしながら、ゼロコピー２進基数木２１０内の２進数を使用して、キーをバイトバッファ（目的地：ネットワーク、ディスク）に直接シリアル化することによって、２進「ビュー」を作成することができる。２進「ビュー」は、ナビゲート可能なバイト配列をコンシューマに公開し、ゼロコピー２進基数木に格納された２進数をナビゲートする。参照元は、下位のバイトをコピーすることなく、２進「ビュー」内のバイトにアクセスすることができる。したがって、ゼロコピー２進基数木システムは、ゼロコピー参照を可能にし、バイトを参照する密度および能力の両方を達成する。
【００５２】
次に、すべての参照元２１１〜２１３は、ゼロコピー２進基数木２４０内のノード（例えば、図２のノード２４１）である読取バッファ（ReadBuffer）内の位置を参照することができる。参照は、本質的に、ナビゲート可能なバイト配列を公開するインターフェイスである。バイトシーケンス（ByteSequence）と呼ばれたインターフェイスは、byteAt(n)およびlength()などのメソッドを提供するため、forループ構造内に使用され、バイト配列内のキーを効果的に参照することができる。バイトシーケンスインターフェイスは、ナビゲート可能なバイト配列内の一連のバイトを示す。byteAt(n)メソッドは、バイトシーケンスのｎ番目のバイトを決定する。length()メソッドは、バイトシーケンスのノードに示されたデータのバイト数を決定する。したがって、逆索引などの参照元は、バイトにアクセスできるように、２進基数木に「ビュー」／バイトシーケンスを形成する＜バイトシーケンス＞セットとして実装することができる。このことは、逆索引参照元を、２進基数木内のすべてのバイトのコピーを用いてセット内の各２進数を完全に取得する必要のある＜２進＞セットとして実装することに比べて、有利である。したがって、ゼロコピー２進基数木システムは、ゼロコピー参照（すなわち、２進基数木のコピーをしないこと）を可能にし、２進基数木のバイトを参照する密度および能力の両方を達成することができる。ゼロコピー２進基数木２４０内の位置は、参照されるキーを表す。これによって、キーをコピーする必要がなく、メモリの浪費が少なくなる。すなわち、参照元２１１〜２１３は、キー「ＡＬＢＥＲＴ」のコピー２８１、２８２および２８３を保有する必要がない。
【００５３】
ゼロコピー２進基数木は、キーの取得と並行して、キーを追加または削除することができる流体データ構造である。キーを追加すると、新しいリーフノードが追加され、古いリーフノードが分岐する。ゼロコピー２進基数木は、例えば、参照収集プロセスを用いて、木の分岐および孤立参照を引き起こす木の変更を考慮する。この参照収集プロセスにおいて、参照収集スレッドは、ゼロコピー２進基数木２４０の孤立した参照を収集し、訂正する。参照元は、廃止した参照を変更するように通知される。参照（バイトシーケンス）は、自己更新することができる。参照の自己更新とは、その参照が既に無効になり、有効な参照を引き出すべきであることを基数木内の「ビュー」／バイトシーケンスに通知することを意味する。有効な参照は、無効な参照を置換する。孤立ノードの決定は、サービスのデーモンプールに与えられるタスクであるため、専用のスレッドを必要しない。参照収集スレッドは、孤立したすべてのノードを認識／通知し、孤立ノードを導き出す識別子に基づいて、逆索引のセットをチェックすることができる。
【００５４】
さらに、ノードは、孤立になった場合、親ノードへの一方向の参照を保有しているため、木のエントリポイントとして機能することができる。孤立ノードは、機能上正常である。ノードの親参照を調べることによって、そのノードが孤立ノードであるを判断することができる。指定の親がノードを参照できなくなる場合、そのノードは、孤立ノードである。木の分岐によってノードが孤立してしまうが、親ノードは、引き続き孤立ノード内の一部のバイトを参照することができる。したがって、新規／有効ノードは、木に沿って、親ノードから新規／有効ノードまで走査することによって、判断することができる。
【００５５】
孤立ノードが機能的に正常であり且つ新規／有効ノードを見い出すために使用することができるが、孤立ノードを参照解除することは依然として重要である。その理由は、孤立ノードが、例えば木の分岐後、この孤立ノードを置換したノードと重複するためである。孤立ノードは、参照解除されない場合、ガーベージコレクションを行うことができない。したがって、存在する孤立ノードは、２進基数木の実効メモリ密度を低下する。よって、シグナリング、コレクションおよび参照解除を実行することによって、孤立ノードのガーベージコレクションを行い、２進基数木の実効メモリ密度を増加し、全体的なメモリ使用量を減少する。
【００５６】
図３Ａは、ルートノード３０２および複数のリーフノード（３０６ａ〜３０６ｌ）を含むゼロコピー２進基数木３００の実施形態を示す（例示の目的のために、限定された数のノードを示しているが、より多くのノードが存在してもよい）。ゼロコピー機能を可能にするインターフェイスを介して２進基数木を参照するが、２進基数木自体は、実質的に従来の方法に従って実装される。図３Ａに示すように、各ノードは、複数の子ノードを有し、各子ノードは、配列に配置され、２進検索するにより、第１バイトを与える正確なノードを見い出すことができる（各子ノードが特定のバイトを示すため、子ノードの数は、最大２５５である）。２進基数木は、コンパクトノードと、バイト配列ノードとを含む。コンパクトノードとは、８バイト（long）ですべての情報を格納できるノードである。情報が８バイトで格納できないほど長い場合、バイト配列ノードを使用する。リーフノードは、２進基数木に格納されたバイト配列の末尾を表す。例えば、０×ＦＦＦ１、０×ＦＦＦ２および０×ＦＦＦ１ＦＦを２進基数木に格納する場合、下線文字部分は、リーフノードになる。また、Ｆ１は、第３のキー０×ＦＦＦ１ＦＦのリーフノードおよび親ノードの両方になる。２進基数木のノード位置は、格納されているキーの数に加えて、格納されているバイト配列の共有バイトに依存する。
【００５７】
しかしながら、２進基数木の深さの増加に連れて、単一のキーを取得するために走査しなければならないリンクノードの数が増加し、それによって、キーを取得するために２進基数木を走査するコストも増加する。byteAt(n)のような質問を回答するために、木のｎ番目位置でバイトを返答する効率的な走査メカニズムを用意した。効率的な走査メカニズムは、木のｎ番目位置のバイトを決定するために走査しなければならないノードの数を減らす。従来の２進基数木とは異なり、本開示に記載された２進基数木は、「サテライト」ノードを用いて、強化されている。「サテライト」ノードは、byteAt(n)のような質問を回答するために、２進基数木を走査しなければならない最大距離を短くすることができる。「サテライト」ノード３０４は、木における自己位置を特定する情報を暗号化することによって、木の全体を走査せず、２進キー全体のbyteAt(n)などの質問を容易に回答することができる。したがって、ゼロコピー２進基数木２４０を用いて値を検索することは、格納されたキーに対して非常に効率的である。
【００５８】
サテライトノード３０４は、ルートノードに対する自己位置が分かる「特別な」ノードである。サテライトノードの位置情報は、２進基数木の走査中に使用できるように、long（コンパクトノード）またはバイト配列のいずれかに格納される。２進基数におけるサテライトノードの位置は、使用モデルに基づく適応アルゴリズムによって決定することができる。適応アルゴリズムは、位置情報の格納に必要な追加メモリと木の走査負荷の減少との間にトレードオフを行う。例えば、頻繁にアクセスするキーを得るために走査しなければならないノードの数を減らすために、サテライトノードは、最適には、頻繁に走査するノードの近くに配置される。代替的に、サテライトノードは、二進基数木のリーフノードからルートノードまでの距離の１／８に設けられる。サテライトノードは、ルートノード３０２からの距離を「知っている」ため、byteAt(n)を回答するときに木を横断する走査は、正しいリーフノードに向かって移動する前に、サテライトノードまで移動すればよい。例えば、１００バイトがＢＲＴに格納され、関数byteAt(91)が呼び出されたとする。位置９１のバイトを決定するために、木の最上部に走査して位置０を見い出し、木の下方に走査して位置９１を見い出す必要がある。しかしながら、バイト５０にサテライトノード３０４を設けることによって、上方へ１００バイトおよび下方へ９１バイトの走査に比べて、ナビゲーションを上方へ５０バイトおよび下方へ４１バイトに制限した。
【００５９】
ゼロコピー２進基数木と従来の２進基底木との主な違いは、サテライトノード以外に、２進基数木からキーを返答する方法にある。以前の実装において、参照元が２進基数木からキーを要求するときに、キーのバイト配列コピーが返答される。一方、本開示において、ゼロコピー２進基数木は、バイト配列におけるノードの位置の参照を返答する。したがって、例えば、逆索引３３０は、２進キーのコピーの代わりに、バイト配列３１０内の位置（例えば、３３６ａ、３３６ｄ、３３６ｉ、３３６ｊ）の参照のセットを含む。これにより、索引のメモリ負荷が削減される。
【００６０】
上述したように、ゼロコピー２進基数木２１０内の２進数を使用して、キーをバイト配列３１０に直接シリアル化することによって、２進「ビュー」を作成することができる。２進「ビュー」は、リーフノード３０６ａ〜３０６ｌからなるナビゲート可能なバイト配列３１０をコンシューマに公開する。リーフノード３０６ａ〜３０６ｌのそれ自体は、バイトシーケンスという名前で実装されたインターフェイス３２０として公開される。このバイトシーケンスインターフェイス３２０によって、バイト配列を実現する２進基数木内のバイトをコピーせず、２進基数木３００に格納されたバイト配列３１０を参照することができる。２進基数木のノードは、２進基数木の外部に直接露出されることがないが、その代わりに、バイトシーケンスインターフェイス３２０は、バイト配列内の特定の位置のノードの参照を用いて、バイト配列をナビゲートすることができ、バイト配列の走査を行うことができる。
【００６１】
したがって、逆索引３３０などの参照元は、下位のバイトをコピーすることなく、２進「ビュー」内のバイトにアクセスすることができる。したがって、リーフノードの参照によって、コンシューマは、２進キーのコピーを作成する必要なく、２進数をナビゲートすることができる。さらに、参照を使用することによって、最適化ハッシュコードおよび同等な実装などの機能を提供することができ、逆キー索引などのハッシュ型コンテナに効率的に使用することができる。例えば、以下で説明する参照ストアの実装を参照する。各索引は、すべてのキーを少なくとも２回に参照する必要がある（順索引および逆索引）。したがって、キーのバイトコピーを作成する代わりに、参照を使用すると、索引のメモリ負荷を大幅に削減し、ナビゲート可能な２進数を、ソケット経由でバイトを送信するDataOutputなどのストリームに直接にストリーミングすることができる。
【００６２】
図３Ｂは、本発明の一実施形態に従って、分散コンピューティング環境においてゼロコピー２進基数木を作成する方法を示す図である。図３Ｂに示すように、この方法は、ステップ３４０において２進基数木を形成することを含む。２進基数木は、複数の２進キーを格納する複数のノードを含む。ステップ３４２において、２進基数木をバッファにシリアル化することによって、２進ビューを形成する。ステップ３４４において、バッファにインターフェイスを提供する。インターフェイスは、例えば、byteAt(n)およびlength()などのメソッドをサポートするバイトシーケンスバッファである。ステップ３４６において、バッファ内のノードを参照する複数の参照は、複数の参照元に提供される。参照元は、複数の逆索引を含むことができる。参照元は、参照を用いて、２進キーを取得し、キーのコピーを保有しなくてもキーに関連付けられた値を見い出すことができる。２進キーのバイトコピーの代わりに参照を使用すると、逆索引に関連するメモリ負荷が削減される。ステップ３４８において、ノードを２進基数木に追加することができる。ステップ３５０において、収集スレッドは、孤立ノードの参照を収集し、訂正する。
【００６３】
いくつかの実施形態において、逆索引などの参照元は、以下に説明する参照ストアを利用して、バッファ内のノードの参照を記憶することができる。
【００６４】
参照ストア
分散コンピューティング環境に、例えば図１の分散データグリッド１００において、索引を使用する場合、（例えば、クエリを効率的に実行するように、検索される値を記憶されたキーの参照にマッピングする）多数の参照を保持することを必要とする。例えば、効率的なクエリを実現するために、Oracle（登録商標）Coherenceデータグリッドは、索引値に対応するオブジェクトに対し、１セットのキーを特定する逆索引（索引値−＞＜キー＞セット）を作成することによって、データに索引を付ける。索引値が多く存在するため、多くの＜キー＞セットを保有する必要がある。さらに、一部のセット（例えば、共通値のセット）の数が多く、一部のセット（例えば、稀少値のセット）の数が少ない。保管する必要のある＜キー＞セットの数が多い場合、望ましくは、これらの＜キー＞セットをメモリ効率の良い方法で格納する。しかしながら、従来のシステムは、従来の＜キー＞セットのＪＤＫ実装を利用する。この従来の＜キー＞セット実装は、少ない数の要素または多い数の要素を記憶するように最適化されていないため、メモリ効率が良くない。したがって、少ない数の要素および多い数の要素の両方を記憶するように最適化されたメモリ効率のよい方法で、索引値を記憶されたキーの参照にマッピングするシステムおよび方法を提供することが望ましい。
【００６５】
本発明の一実施形態によれば、分散コンピューティング環境において、参照ストアを使用して、メモリ効率的な方法で参照をキー値ストアに記憶することができる。参照ストアを使用することによって、一連の参照を効率的に記憶することができる。さらに、特定の参照セットに使用される参照ストアのサイズは、データセットが変更されると、メモリ要件の変更に対応するために、拡大または縮小することができる。参照ストアの拡大または縮小は、ストアの参照を削除または追加することによってトリガされる。ＡＰＩは、ストアの挿入または削除の結果として、ストアにハンドル／チケットを返答する。元のストアの場合、返答されたハンドルは、同様であり、ストアの拡大または縮小の場合、返答されたハンドルは、異なる。
【００６６】
図４は、本発明の一実施形態に従って、分散コンピューティング環境内の参照ストア４０２を示す図である。図４に示すように、例えば分散データグリッドのような分散コンピューティング環境４００内の参照ストアインスタンス４０１は、複数の参照４１０（例えば、上述のゼロコピー２進基数木の実装によって提供されたナビゲート可能なバイト配列の逆索引または参照に関連するさまざまなキー）を含むことができる。
【００６７】
図４に示すように、参照ストア４０２は、複数の参照ストアインスタンス４０１を含む。各参照ストアインスタンス４０１は、少くない数の参照を記憶するように最適化されてもよく、多い数の参照を記憶するように適応的に最適化されてもよい。さらに、各参照ストアインスタンス４０１は、チケット４２０（例えば、Long変数）に関連付けられている。システムは、チケット４２０を用いて、参照ストアインスタンス４０１を分散コンピューティング環境４００内の１つ以上のコンシューマ４１２に公開する。コンシューマは、参照ストアインスタンスの変更を知る必要がある任意の関係者である。例えば、逆索引が参照ストアインスタンス（キーの集合）を参照する場合、索引自体は、参照ストアインスタンスが変更されると通知され、新規の参照ストアインスタンスを取得することができるコンシューマになる。さらに、参照ストア４０２は、参照ストアインスタンス４０１に発生した任意の変更、例えば参照ストアインスタンス４０１の拡大または縮小に関する変更を１つ以上のコンシューマ４１２に通知する。
【００６８】
各参照ストアインスタンスは、少くない数の参照を記憶するように最適化されたストアを、多い数の参照を記憶するように最適化されたストアに拡大することができ、または多い数の参照を記憶するように最適化されたストアを、少くない数の参照を記憶するように最適化されたストアに縮小することができる。さらに、拡大／縮小イベントの後、参照ストアに使用されたメモリの再割当を行う必要なく、参照ストアインスタンスを再利用できるように管理することができる。これによって、メモリの使用および参照のアクセス回数が非常に効率的になる。コンシューマ（参照ストアを参照するユーザ）は、ストアに変更が発生したときに通知されるように登録することができる。登録されたコンシューマは、参照ストアからの信号、すなわち、拡大／縮小イベントに関する信号を実行することができる。逆索引の数および索引値あたりのキーの数が増えると、参照ストアがより有益になる。
【００６９】
したがって、参照ストアが作成され、チケットで参照される。チケットは、longプリミティブデータ型で表される。Ｊａｖａ（登録商標）において、longデータ型は、６４ビット符号付き２の補数である。参照ストアインスタンスをlongデータ型として公開すると、参照元は、効率的なコンパクトデータ構造を用いて、ストア（すなわち、LongLongマップ）を参照することができる。Ｊａｖａ（登録商標）において、LongLongマップは、キーを単一値に一意的に結び付ける連想型コンテナを提供する。このアプリケーションにおいて、LongLongマップは、参照ストアを表すキーを、参照ストアのコンテンツに関連付ける。特定の索引に対応する参照ストアインスタンスを拡大または縮小するときに、特定の索引に関連付けられたチケットは、変化することができる。したがって、特定の索引に対応する参照ストアインスタンスを拡大または縮小する場合、参照ストア内の索引に新規チケットを割り当てる。
【００７０】
図５は、複数の参照ストアインスタンス５２０〜５２８と共に、LongLongマップ５１０を使用する参照ストア５００を示す図である。参照ストアインスタンス５２０は、索引値「赤色」を満たすオブジェクトに対応するキーに対応するゼロコピー２進基数木のノードに、参照セット５３０を格納する。参照ストアインスタンス５２２は、索引値「青色」を満たすオブジェクトに対応するキーに対応するゼロコピー２進基数木のノードに、参照セット５３２を格納する。参照ストアインスタンス５２４は、索引値「白色」を満たすオブジェクトに対応するキーに対応するゼロコピー２進基数木のノードに、参照セット５３４を格納する。参照ストアインスタンス５２６は、索引値「黒色」を満たすオブジェクトに対応するキーに対応するゼロコピー２進基数木のノードに、参照セット５３６を格納する。参照ストアインスタンス５２８は、索引値「紫色」を満たすオブジェクトに対応するキーに対応するゼロコピー２進基数木のノードに、参照セット５３８を格納する。
【００７１】
LongLongマップ５１０は、複数の索引値５１４を複数のチケット５１２に関連付ける複数の行を含む。チケットは、索引値に関連付けられた参照ストアの仮想アドレスを表す。したがって、LongLongマップ５１０は、索引値「赤色」をチケット「０×１１２ｃａ５３３」に、索引値「青色」をチケット「０×３８ｆｃｅ７８６」に、索引値「白色」をチケット「０×ｆｄ７３８ｄ８４」に、索引値「黒色」をチケット「０×３８１９ｅ６ｃ３」に、索引値「紫色」をチケット「０×ｂ３８１ｅｆｄ２」に関連付ける。したがって、すべての「赤色」オブジェクトに対するクエリに応答して、LongLongマップは、チケット「０×１１２ｃａ５３３」を用いて参照ストア５２０を特定して、参照セット５３０を返答することができる。参照セット５３０は、索引値「赤色」を満たす値／オブジェクトのキーに対応するゼロコピー２進基数木２４０内のノードを特定する。したがって、システムは、クエリに応答して、索引値「赤色」を満たす全ての値／オブジェクトを返答することができる。特定の索引に対応する参照ストアインスタンスを拡大または縮小するときに、特定の索引に関連付けられたチケットは、変化することができる。したがって、特定の索引に対応する参照ストアインスタンスを拡大または縮小する場合、LongLongマップ５１０の索引に新規チケットを割り当てる。
【００７２】
さらに、各参照ストアインスタンスにおける参照の数は、特定の索引値を満たす値／オブジェクトの数に応じて、著しく変化することができる。例えば、「紫色」オブジェクトは、「黒色」オブジェクトよりも著しく少ない可能性がある。参照ストアインスタンスは、メモリの使用を最適化するために、格納された参照の数に応じて、異なるデータ構造を利用することができる。これは、従来の＜キー＞セット実装とは異なる。従来の＜キー＞セット実装は、例えば、セット内のキーの数に関係なく、ハッシュセットを使用して、索引値をキーに関連付ける。従来の＜キー＞セット実装は、メモリ使用およびアクセスコストの両方で高価であった。特に、参照の数が少ない場合、ハッシュセットの使用は、必要以上のメモリ使用およびアクセス負荷をもたらす。
【００７３】
したがって、参照ストア５００は、異なるサイズの参照のグループを格納するためのメモリ使用およびアクセス効率に関して、より効率的なメカニズムを提供する。参照ストア５００は、ストア内の参照の数に基づいて、索引値に対応する参照を記憶する必要がある索引とのコントラクトを実装する。例えば、参照が６４個またはそれ以下の場合、参照ストア５００は、ビットマスク型参照ストアインスタンスを利用して、参照を記憶する。参照をストアに提供するたびに、この参照は、ビットマスク型参照ストアインスタンス内の６４個のスロットのうち、異なるスロットに配置される。すべてのスロットが一杯になると、受信した別の参照を格納する場合、参照ストアインスタンスを拡大する。
【００７４】
参照ストアインスタンスを拡大するために、参照の数に応じて、新規のリスト型参照ストアまたはハッシュ型参照ストアを参照する新規チケットに、索引を関連付ける。新規の参照ストアインスタンスは、この時点で作成されてもよく、既に割り当てられており、現在に使用されていないものを使用してもよい。従来のビットマスク型参照ストア内の参照は、新規の参照ストアに移行される。参照ストアは、現在使用されていないビットマスク型参照ストアのメモリ割当を保持しているため、必要に応じてこのメモリを別の索引に割り当てることができる。
【００７５】
リスト型参照ストアインスタンスは、良いメモリ効率を有し、無限数の参照を保持することができる。しかしながら、単純なリスト型参照ストアは、ハッシュセマンティクスを有しないため、参照の数が増加すると、ストア内の参照にアクセスするキャストも増加する。したがって、参照ストアは、リスト型参照ストアインスタンスを継続的に使用するアクセスコストが高すぎるという参照の閾値数に達するまで、リスト型参照ストアインスタンスを用いて、特定の索引に対応する参照を記憶する。この時点で、更なる参照を参照ストアインスタンスに追加する場合、参照ストアインスタンスを再度拡大する。
【００７６】
リスト型参照ストアインスタンスを拡大するために、ハッシュ型参照ストアを参照する新規チケットに、索引を関連付ける。ハッシュ型参照ストアインスタンスは、この時点で作成されてもよく、既に割り当てられており、現在に使用されていないものを使用してもよい。従来のリスト型参照ストア内の参照は、新規のハッシュ型参照ストアに移行される。参照ストアは、現在使用されていないビットマスク型参照ストアのメモリ割当を保持しているため、必要に応じてこのメモリを別の索引に割り当てることができる。ハッシュ型参照ストアインスタンスは、リスト型参照ストアインスタンスよりも多くのメモリを必要とするが、ハッシュセマンティクスは、参照の数が多い場合に、ストア内の参照にアクセスするコストを削減することができる。ハッシュ型参照ストアは、オープンハッシュセットとして実装された最大の参照ストア実装である。
【００７７】
一方、参照ストア５００は、参照ストア内の参照の数を減少することによって、参照ストアインスタンスを縮小することができる。これによって、参照をより小さい参照ストアインスタンスのうち１つに格納することができる。したがって、リスト型参照ストアに対応するチケットを形成し且つ参照を移行することによって、ハッシュ型参照ストアインスタンスは、リスト型参照ストアインスタンスに縮小することができる。同様に、ビットマスク型参照ストアに対応するチケットを形成し且つ参照を移行することによって、リスト型参照ストアインスタンスは、ビットマスク型参照ストアインスタンスに縮小することができる。いずれのケースにおいて、移行後に、異なる索引に使用されるまで未使用のデータ構造を保有することができる。これによって、新規の参照ストアを作成する必要性およびノード／ＪＶＭに対応する新規メモリ割当を要求する必要性を減らすことができる。一実施形態において、参照ストアは、各種の参照ストアインスタンスの典型要件の理解に基づいて、各種の参照ストアインスタンスのメモリを事前に割り当てることができる。
【００７８】
図６は、本発明の一実施形態に従って、索引に対応する参照を記憶するための参照ストアを使用する方法を示す。同様の方法は、参照ストアによって、複数の索引サービスの各々に対して実行される。方法は、ステップ６００から開始され、参照を記憶する必要がある索引とのコントラクトを実装する参照ストアを作成する。ステップ６０２において、索引は、第１参照を格納する。第１参照が追加されると、ビットマスク型参照ストアは、作成され、使用される。ステップ６０４において、参照ストアは、ビットマスク型参照ストアインスタンスに対応するチケットに、索引を関連し、そのチケットを参照元に返答する。ステップ６０６において、第１参照は、ビットマスク型参照ストアインスタンスに格納される。ステップ６０８において、索引に応じて、参照をビットマスク型参照ストアインスタンスに追加するまたはそこから削除する。ステップ６１０において、参照を追加または削除した後、参照の数が６４以下である場合、方法は、ステップ６０８に戻り、引き続きビットマスク型参照ストアインスタンスを使用して、参照を記憶する。ステップ６１０において、６５番目の参照を追加しようとする場合、方法は、ステップ６１２に進み、参照ストアインスタンスを拡大する。
【００７９】
ステップ６１２において、索引に関連付けられた参照ストアインスタンスは、拡大される。参照ストアは、リスト型参照ストアインスタンスを参照する新規チケットに、索引を関連付ける。代替的には、リストは、ハッシュ型参照ストアに直接に拡大される（ステップ６２４）。リスト型参照ストアは、ハッシュ型参照ストアから縮小した後のみ、使用される。ステップ６１４において、リスト型参照ストアインスタンスに６５番目の参照を追加し、他の６４個の参照をリスト型参照ストアインスタンスに移行する。ステップ６１６において、索引に応じて、参照をリスト型参照ストアインスタンスに追加するまたはそこから削除する。ステップ６１８において、参照の数が縮小閾値より大きく且つ拡大閾値よりも小さい場合、方法は、ステップ６１６に戻り、引き続きリスト型参照ストアインスタンスを使用して、索引に対応する参照を記憶する。
【００８０】
ステップ６１８において、参照の数が縮小閾値以下である場合、方法は、ステップ６２０に進み、参照ストアインスタンスを縮小する。縮小は、少なくとも７５％の参照ストアまたは参照ストア内の合計スロットに対して２５％以下の参照が浪費される場合のみ行われる。初期使用に対する補償もあるため、縮小は、安定使用になるまで行わない。ステップ６１８において、参照の数が拡大閾値以上である場合、方法は、ステップ６２４に進み、参照ストアインスタンスを拡大する。
【００８１】
ステップ６２０におけるリスト型参照ストアの縮小は、ビットマスク型参照ストアインスタンスを参照するチケットに、索引を関連付けることを含む。ステップ６２２において、参照は、リスト型参照ストアインスタンスから、ビットマスク型参照ストアインスタンスに移行される。その後、方法は、ステップ６０８に戻り、参照をビットマスク型参照ストアインスタンスに追加するまたはそこから削除することができる。過度の移行サイクルを防止するために、リスト型参照ストアをビットマスク型参照ストアに縮小するための閾値は、例えば、ビットマスク型参照ストアをリスト型参照ストアに拡大する閾値の８０％である。
【００８２】
ステップ６２４におけるリスト型参照ストアインスタンスの拡大は、ハッシュ型参照ストアインスタンスを参照するチケットに、索引を関連付けるを含む。ステップ６２６において、（拡大閾値を超える）参照がハッシュ型参照ストアインスタンスに追加され、既に格納されている参照がハッシュ型参照ストアインスタンスに移行される。ステップ６２８において、参照をハッシュ型参照ストアインスタンスに追加するまたはそこから削除することができる。ステップ６３０において、参照の数が縮小閾値より大きい場合、方法は、ステップ６２８に進み、索引は、引き続きチケットに関連付けられたハッシュ型参照ストアインスタンスを使用して、参照を記憶する。なお、ハッシュ型参照ストアが使用可能な最大ストアであるため、更なる拡大は不可能である。ステップ６３０において、参照の数が縮小閾値以下である場合、方法は、ステップ６３２に進み、参照ストアインスタンスを縮小する。縮小は、少なくとも７５％の参照ストアまたは参照ストア内の合計スロットに対して２５％以下の参照が浪費される場合のみ行われる。初期使用に対する補償もあるため、過度の移行サイクルを防止するために、縮小は、安定使用になるまで行わない。
【００８３】
ステップ６３２におけるハッシュ型参照ストアインスタンスの縮小は、リスト型参照ストアインスタンスを参照するチケットに、索引を関連付けることを含む。ステップ６３４において、（閾値未満の）参照が削除され、残りの参照がリスト型参照ストアインスタンスに移行される。その後、方法は、ステップ６１６に戻り、索引は、参照をチケットに関連付けられたリスト型参照ストアインスタンスに追加またはそこから削除することができる。
【００８４】
一実施形態は、分散コンピューティング環境において参照ストアをサポートする方法を提供する。この方法は、ビットマスク型ストアを含む参照ストアを作成するステップと、参照を参照ストアに格納するステップと、チケットを参照ストアに関連付けるステップと、１つ以上のコンシューマにチケットを提供するステップと、ビットマスク型参照ストアに複数の参照を追加するステップと、参照ストア内の参照の数が閾値を超える場合に、参照ストアを拡大するステップとを含む。
【００８５】
一実施形態は、参照ストア内の参照の数が閾値を超える場合に、参照ストアを拡大するための方法を提供する。この方法は、参照ストアを、リスト型参照ストアおよびハッシュ型参照のうちの１つを含む新規参照ストアに拡大するステップと、参照を参照ストアから新規の参照ストアに移行するステップと、新規チケットを新規の参照ストアに関連付けるステップと、新規チケットを１つ以上のコンシューマに提供するステップとを含む。
【００８６】
一実施形態は、参照ストア内の参照の数が閾値を超える場合に、参照ストアを拡大するための方法を提供する。この方法は、参照ストアを、リスト型参照ストアおよびハッシュ型参照のうちの１つを含む新規参照ストアに拡大するステップと、参照を参照ストアから新規の参照ストアに移行するステップと、参照ストアの拡大に関する情報を１つ以上のコンシューマに送信するステップとを含む。
【００８７】
一実施形態は、チケットを索引値に関連付ける方法を提供する。
一実施形態は、複数のチケットに関連付けられた複数の参照ストアを作成するステップと、複数のチケットを複数の索引値に関連付けるマップを形成するステップとを方法を提供する。複数の参照ストアの各々は、１つ以上の異なる索引値に関連付けられる。
【００８８】
一実施形態は、参照を参照ストアに追加するまたはそこから削除することに応答して、参照ストアを拡大または縮小する方法を提供する。
【００８９】
一実施形態は、ゼロコピー２進基数木を形成するための方法を提供する。参照ストア内の複数の参照の各々は、ゼロコピー２進基数木内のノードを参照する。
【００９０】
一実施形態は、拡大または縮小の後に、参照ストアのメモリ構造をリサイクルする方法を提供する。
【００９１】
一実施形態は、拡大閾値を超えるように参照を追加することに応答して、参照ストアを拡大するステップと、残りの参照の数が縮小閾値未満になるように参照を削除することに応答して、参照ストアを縮小するステップとを含む方法を提供する。
【００９２】
一実施形態において、分散コンピューティング環境は、分散データグリッドであり、方法は、参照ストアを使用して、分散データグリッドにキャッシュされたオブジェクトセットに関連する参照セットを保持するステップをさらに含む。
【００９３】
一実施形態は、分散コンピューティング環境においてキーの管理をサポートするためのシステムを提供する。このシステムは、マイクロプロセッサとメモリとを含むコンピュータシステムと、コンピュータシステム上で動作する分散コンピューティング環境のサーバノードとを備え、サーバノードは、サーバノードに割り当てられたコンピュータシステムのメモリ内に、ビットマスク型ストアを含む参照ストアを作成し、参照ストア内に参照を格納し、参照ストアにチケットを関連付け、チケットを１つ以上のコンシューマに提供し、ビットマスク型参照ストアに複数の参照を追加し、参照ストア内の参照の数が閾値を超えた場合に、参照ストアを拡大するように構成される。
【００９４】
一実施形態に記載のシステムにおいて、サーバノードは、リスト型参照ストアおよびハッシュ型参照ストアのうちの１つを含む新規の参照ストアを作成し、参照ストアから参照を新規の参照ストアに移行し、新規チケットを新規の参照ストアに関連付け、および、１つ以上のコンシューマに新規チケットを提供することによって、参照ストアを拡大するように構成される。
【００９５】
一実施形態に記載のシステムにおいて、サーバノードは、参照ストアを、リスト型参照ストアおよびハッシュ型参照ストアのうちの１つを含む新規の参照ストアに拡大し、参照ストアから参照を新規の参照ストアに移行し、１つ以上のコンシューマに参照ストアの拡大に関する情報を送信することによって、参照ストアを拡大するように構成される。
【００９６】
一実施形態に記載のシステムにおいて、チケットは、索引値に関連付けられる。
一実施形態に記載のシステムにおいて、サーバノードは、複数のチケットに関連付けられた複数の参照ストアを作成し、複数のチケットを複数の索引値に関連付けるマップを形成するように構成される。複数の参照ストアの各々は、１つ以上の異なる索引値に関連付けられる。
【００９７】
一実施形態に記載のシステムにおいて、サーバノードは、参照を参照ストアに追加するまたはそこから削除することに応答して、参照ストアを拡大または縮小するように構成される。
【００９８】
一実施形態に記載のシステムにおいて、サーバノードは、ゼロコピー２進基数木を形成するように構成され、参照ストア内の複数の参照の各々は、ゼロコピー２進基数木内のノードを参照する。
【００９９】
一実施形態に記載のシステムにおいて、サーバノードは、拡大または縮小の後に、参照ストアのメモリ構造をリサイクルするように構成される。
【０１００】
一実施形態に記載のシステムにおいて、分散コンピューティング環境は、分散データグリッドであり、サーバノードは、参照ストアを使用して、分散データグリッドにキャッシュされたオブジェクトセットに関連する参照セットを保持するように構成される。
【０１０１】
一実施形態は、分散コンピューティング環境においてキーの管理をサポートするための命令を格納する非一時的なコンピュータ可読媒体を提供する。これらの命令は、実行されると、分散コンピューティング環境のサーバノードに、以下のステップを実行させ、当該ステップは、ビットマスク型ストアを含む参照ストアを作成するステップと、参照ストア内に参照を格納するステップと、参照ストアにチケットを関連付けるステップと、チケットを１つ以上のコンシューマに提供するステップと、ビットマスク型参照ストアに複数の参照を追加するステップと、参照ストア内の参照の数が閾値を超えた場合に、参照ストアを拡大するステップとを含む。
【０１０２】
上記で本発明のさまざまな実施形態を説明したが、これらの実施形態は、限定ではなく例示として提示されることを理解すべきである。本発明の精神および範囲から逸脱することなく、形態および詳細のさまざまな変更を行うことができることは、当業者にとって明らかであろう。
【０１０３】
本発明の多くの特徴は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの組み合わせに実行する、またはそれらを使用して実行する、またはそれらの援助で実行することができる。本発明は、本開示の教示に従ってプログラムされた１つ以上のプロセッサ、メモリおよび／またはコンピュータ可読記憶媒体を含む１つ以上の従来の汎用または専用デジタルコンピュータ、コンピューティング装置、機械、またはマイクロプロセッサを使用して都合よく実施することができる。本発明の特徴は、例えば、特定用途向け集積回路（ＡＳＩＣ）およびプログラマブル論理装置などのハードウェア要素を使用して、ハードウェアで実施することもできる。本開示に記載の機能を実行するために、ハードウェア状態機械を実装することは、当業者には明らかであろう。
【０１０４】
本発明の特徴は、処理システムのハードウェアを制御し、本発明の結果を利用して処理システムと他の機構との相互作用を可能にするソフトウェアおよび／またはファームウェアに組み込むことができる。そのようなソフトウェアまたはファームウェアは、アプリケーションコード、装置ドライバ、オペレーティングシステムおよび実行環境／コンテナを含むことができるがこれらに限定されない。ソフトウェア分野の当業者には明らかであるように、熟練したプログラマは、本開示の教示に基づいて、適切なソフトウェアのコーディングを容易に準備することができる。
【０１０５】
いくつかの実施形態において、本発明は、本発明のプロセスのうちいずれかを実行するようにコンピュータをプログラムするために使用できる命令を格納する非一時的な記録媒体またはコンピュータ読取可能な媒体であるコンピュータプログラム製品を含む。この記録媒体は、フロッピー（登録商標）ディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロドライブ、および光磁気ディスクを含む、任意の種類のディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＶＲＡＭ、フラッシュメモリデバイス、磁気もしくは光カード、ナノシステム（分子メモリＩＣを含む）、または、命令および／もしくはデータを格納するのに適した任意の種類の媒体もしくは装置を含むことができるが、これらに限定されない。
【０１０６】
本発明の上記記載は、例示および説明を目的として提供される。本発明を網羅的なものまたは開示された形態そのものに限定することを意図していない。当業者には数多くの変更および変形が明らかであろう。修正例および変形例は、開示された特徴の任意可能な組み合わせを含む。実施形態は、本発明の原理およびその実際の応用を最も良く説明することによって、他の当業者がさまざまな実施形態および考えられる特定の用途に適したさまざまな変形に応じて本発明を理解できるように、選択され説明される。本発明の範囲は、添付の特許請求の範囲およびそれらの同等物によって規定されると意図する。
【図１】
0006549704.tif 000002
【図２】
0006549704.tif 000003
【図３Ａ】
0006549704.tif 000004
【図３Ｂ】
0006549704.tif 000005
【図４】
0006549704.tif 000006
【図５】
0006549704.tif 000007
【図６】
0006549704.tif 000008