JP2017510925A - 分散型共有メモリアプリケーションのメモリ破損の検出サポート - Google Patents

Abstract

分散ノードシステム内のノードは、ノード間でメモリを共有する場合、メモリ破損の検出をサポートするように構成されている。本明細書において、分散ノードシステム内のノードがメモリ単位でデータを共有することを「共有キャッシュライン」として称する。ノードは、バージョン値を共有キャッシュライン内のデータに関連付ける。バージョン値およびデータは、ノードのメインメモリにおける共有キャッシュラインに格納されてもよい。ノードは、メモリ操作を実行する場合、バージョン値を用いて、メモリ破損が発生しているか否かを判断することができる。例えば、バージョン値にポインタを関連付けることができる。ポインタを用いてメモリにアクセスする場合、ポインタのバージョン値は、メモリ位置の予期バージョン値を示すことができる。これらのバージョン値が一致しない場合、メモリ破損が発生している。

Description

関連出願の相互参照、優先権主張
本願は、Zoran Radovic等によって２０１４年３月２８日に出願され、「分散型共有メモリアプリケーションのメモリ破損の検出サポート」と題された米国仮特許出願番号第６１／９７２０８２号に基づいて優先権を主張し、その出願の内容が参照により本明細書に援用される。本願は、２０１３年３月１５日に出願され、「個別の物理ドメインアドレス空間内のノードの間にクラスタの形成を可能にするメモリバスプロトコル」と題された米国特許出願番号第１３／８３８５４２号（代理人整理番号５０２７７−４０３２）、２０１３年３月１５日に出願され、「リモート鍵に基づいたメモリバッファアクセス制御メカニズム」と題された米国特許出願番号第１３／８３９５２５号（代理人整理番号５０２７７−４０９１）、および２０１３年３月１４日に出願され、「分散ノード間にメモリの共有」と題された米国特許出願番号第１３／８２８５５５号（代理人整理番号５０２７７−４０７２）に関連し、これらの出願の各々の内容が参照により本明細書に援用される。

発明の分野
本開示は、一般的に、分散ノードシステムにおいてメモリ破損を検出するための技術に関する。

背景
一クラスタ以上の分散コンピューティングノードは、インターネットまたは企業ネットワークを介して、多くの機能およびサービスを提供することができる。例えば、大規模なビジネスを実行するために使用されるデータベースは、複数のデータベースサーバによって維持され、これらのデータベースサーバを介して利用可能である。これらの複数のデータベースサーバは、クラスタに形成された複数の分散コンピューティングノード上で実行される。コンピューティングノードクラスタを使用して機能またはサービスを提供することは、多くの利点を有する。例えば、クラスタを使用する場合、増加する需要を満たすために、別のノードを追加することによって、システムの性能を比較的に容易に増加することができる。クラスタを使用することによって、負荷をさまざまなノード間に分散することができる。したがって、１つのノードが過負荷になった場合、作業を他のノードに割り当てることができる。また、クラスタを使用することによって、１つ以上のノードが故障した場合、故障を許容することができ、機能またはサービスの使用が可能である。さらに、クラスタ内のノードは、例えば、協同作業、取引の実行、負荷の分散、故障の防止および回復等を行うために、情報を共有することができる。

ノードクラスタ上で実行するアプリケーションに対して、メモリ破損を検出する必要がある。メモリ破損は、メモリ位置が不適切にアクセスされまたは変更される際に発生する。一例として、アプリケーションがポインタ変数を特定のデータ構造に割り当てられたメモリを越えて前に進めようとする場合、メモリ破損が発生する。これらのメモリエラーは、プログラムクラッシュまたは予期しないプログラム結果を引き起こす可能性がある。

シングルマシンのアプリケーションのメモリ破損を検出する方法が存在する。シングルマシンのメモリ破損を検出する方法によって、コンピュータは、実行時にアプリケーションのポインタを追跡し、メモリエラーをユーザに通知することができる。

しかしながら、ノードクラスタ上で実行するアプリケーションのデバッグは、シングルマシンのアプリケーションよりも困難である。ノードクラスタ上で実行するアプリケーションをデバッグするいくつかの解決策が存在する。これらのデバッグ解決策は、社内ツールサポート、実行時サポート、またはサムチェック法を含むことができる。残念ながら、これらの解決策は、プログラミングモデルを複雑にし、システムの性能にオーバーヘッドを加える上、メモリ破損を検出できない場合がある。

この節に説明された手法は、探究できるものであるが、必ずしも過去に想到されまたは探究されたものではない。したがって、特に断りのない限り、この節に説明された手法のいずれかは、単にこの節に包含されることによって先行技術として定義されると考えるべきではない。

一実施形態に従って、例示的な分散ノードシステムを示すブロック図である。 一実施形態に従って、分散ノードシステム内の一部のノードがメモリを共有する例を示す図である。 一実施形態に従って、ノード内のメモリ破損を検出するための手順を示すフローチャートである。 一実施形態に従って、キャッシュラインをロードする際に、メモリ破損を検出しながら、キャッシュラインを更新するための手順を示すフローチャートである。 一実施形態に従って、リモートノードにおいてストアを実行するための手順を示すフローチャートである。 一実施形態に従って、リモートノードからソースノードにストアを伝播するための手順を示すフローチャートである。 一実施形態に従って、ソースノードにストアを実行するための手順を示すフローチャートである。 本発明の一実施形態を実現し得るコンピュータシステムを示すブロック図である。

詳細な説明
以下の記載には、説明の目的で、本発明の実施形態を完全に理解できるようにするために、多くの具体的な詳細を記載する。しかしながら、これらの具体的な詳細がなくても本発明を実施できることは明らかであろう。本発明を明瞭にするために、必要に応じて、一部の周知の構造および装置は、ブロック図で示される。

総括
本明細書に記載の実施形態によれば、分散ノードシステム内のノードは、ノード間でメモリを共有する場合、メモリ破損の検出をサポートするように構成されている。本明細書において、分散ノードシステム内のノードがメモリの単位でデータを共有することを「共有キャッシュライン」として称する。ノードは、バージョン値を共有キャッシュラインのデータに関連付ける。バージョン値およびデータは、ノードのメインメモリ内の共有キャッシュラインに格納されてもよい。ノードは、メモリ操作を実行する場合、バージョン値を使用して、メモリ破損が発生したか否かを判断することができる。例えば、ポインタにバージョン値を関連付けることができる。ポインタを用いてメモリにアクセスする場合、ポインタのバージョン値は、メモリ位置の予期バージョン値を示すことができる。これらのバージョン値が一致しない場合、メモリ破損が発生している。

ポインタという用語は、本明細書に使用される場合、メモリに格納された別の値のメモリ位置を指定するアドレスを含む値である。この値は、プロセッサのレジスタにロード可能である。一実施形態によれば、ポインタは、２つの別個の値であるバージョン値および仮想アドレスを含む。この仮想アドレスは、メモリ操作を実行する際に、物理アドレスに変換される。

分散ノードシステムのノードは、そのメインメモリの一部をシステム内の他のノードと共有する。ノード（「ソースノード」）は、そのメインメモリの一部をシステム内の他のノードと共有可能にし、他のノード（「リモートノード」）は、そのメインメモリに共有メモリをコピーする。メモリの一部は、１つ以上の共有キャッシュラインを含むことができる。リモートノードは、ソースノード内のソースキャッシュラインのコピーである複製キャッシュラインを作成する。

一実施形態において、共有キャッシュラインは、バージョンビットとデータビットとを含む。共有キャッシュラインのバージョンビットは、共有キャッシュラインに関連付けられたバージョン値を示す。同様に、共有キャッシュラインを指し示すように構成されたポインタは、バージョン値を含む。ポインタを用いて、共有キャッシュライン上でメモリ操作を実行する場合、ノードは、ポインタのバージョン値と共有キャッシュラインのバージョンビットにより示されたバージョン値とを比較する。

一実施形態において、ソースノードは、メモリ割り当て要求に応答して、バージョン値を生成する。例えば、アプリケーションがデータ構造にメモリを割り当てる際に、ソースノードは、そのデータ構造に関連付けられるバージョン値を生成することができる。生成されたバージョン値および関連付けられたデータ構造は、ローカルノードのメインメモリにコピーされてもよい。

一実施形態において、アプリケーションは、メモリ操作を要求する。ノードは、メモリ破損が発生したことを検出した場合、エラーをアプリケーションに通知することができる。また、ノードは、メモリ操作を実行せず、終了させることもできる。

別の実施形態において、ノードは、バージョン値を用いて、ノード間のコヒーレンシを維持する。例えば、リモートキャッシュラインのバージョン値は、このリモートキャッシュラインが古くなっていることを示すことができる。よって、リモートノードは、対応するソースキャッシュラインに基づいて、リモートキャッシュラインを更新することができる。一実施形態において、１つ以上のバージョン値が、複製キャッシュラインが無効であることを示すために保留される。保留された１つ以上のバージョン値は、ノードがメモリ割り当て要求に応答してバージョン値を生成する際に、使用されない。

システムの概要
図１は、一実施形態に従って、例示的な分散ノードシステム１００を示すブロック図である。分散ノードシステム１００は、３つのノード、すなわち、第１ノード１０２Ａ、第２ノード１０２Ｂおよび第３ノード１０２Ｃを含む。図示には３つのノードが示されているが、システム１００は、より多くのノードまたはより少ないノードを含んでもよい。

各ノード１０２は、メインメモリ１０８を含む。メインメモリ１０８は、１つ以上の共有キャッシュライン１０６を含む。一実施形態において、共有キャッシュライン１０６は、バージョンビット１１２とデータビット１１４とを含む。データは、データビット１１４に格納される。バージョンビット１１２は、共有キャッシュライン１０６に関連付けられたバージョン値を示す。共有キャッシュライン１０６は、同一のサイズを有してもよく、異なるサイズを有してもよい。

１つのノード１０２は、そのメインメモリ１０８の一部（「共有メモリ」）を他のノードと共有することができる。他のノード１０２は、共有メモリの内容を複製するために、メインメモリ１０８の一部（「コピーメモリ」）を割り当てることができる。一実施形態において、１つのノード１０２は、メインメモリ１０８の一部を共有できるようにすることができ、他のノード１０２によってメインメモリ１０８の一部をコピーすることができる。本発明の目的のために、ノード１０２は、任意数（０または１以上）の共有メモリを有することができ、任意数（０または１以上）のコピーメモリを有することができる。各メモリ部分は、１つ以上の共有キャッシュライン１０６含むことができる。一実施形態において、メインメモリの一部１０８を共有するまたはコピーすることは、１つ以上の共有キャッシュライン１０６をそれぞれ共有するまたはコピーすることを含む。

一例として、図２において、第２ノード１０２Ｂは、メインメモリ１０８Ｂの一部を他のノードと共有している。第１ノードおよび第３ノードは、共有メモリ２０２をコピーする。したがって、第１ノード１０２Ａは、メインメモリ１０８Ａにおいて、共有メモリ２０２のコピーであるメモリ部分２０４Ａを有しており、第３ノード１０２Ｃは、メインメモリ１０８Ｃにおいて、共有メモリ２０２のコピーであるメモリ部分２０４Ｃを有している。また、第３ノード１０２Ｃは、メインメモリ１０８Ｃの一部を他のノードと共有している。第１ノードおよび第２ノードは、共有メモリ２０６をコピーする。したがって、第２ノード１０２Ｂは、共有メモリ２０６のコピーであるメモリ部分２０８Ｂを有しており、第１ノード１０２Ａは、共有メモリのコピーであるメモリ部分２０８Ａを有している。図示の例において、第２ノードおよび第３ノードの両方は、メモリの一部を共有すると共に、他のノードから共有メモリをコピーする。第１ノードは、２つのノードからメモリの一部をコピーするが、メモリの一部を共有していない。

一実施形態において、ノード１０２は、ディレクトリ２１０を含むことができる。ディレクトリ２１０は、共有メモリの部分毎に、システム１００内のどのノードが共有メモリのコピーを含むことを示す。一実施形態において、ディレクトリ２１０は、共有メモリ内の各ソースキャッシュラインのエントリを含む。すなわち、ディレクトリ２１０は、ソースノードであるノード１０２の各共有キャッシュラインのエントリを含む。

一実施形態において、ノード１０２は、インデックス２１２を含むことができる。インデックス２１２は、共有メモリの部分毎に、メインメモリ１０８の共有メモリに位置するディレクトリの場所を示す。また、インデックス２１２は、コピーメモリの部分毎に、メモリを共有したソースノードおよびソースノードのメインメモリに位置する共有メモリの位置を示す。一実施形態において、インデックス２１２は、メインメモリ１０８内の各共有キャッシュラインのエントリを含む。インデックス２１２は、コピーメモリ内の共有キャッシュラインの部分毎に、ソースキャッシュラインを共有したソースノードおよびソースノードのメインメモリに位置するソースキャッシュラインの位置を示す。

システムの初期化
メモリを共有するようにシステム１００内のノード１０２を準備するために、ノード１０２を初期化する。一実施形態において、以下のようにノード１０２を初期化することができる。ノード１０２は、任意数のメモリ部分を共有することができ、他のノードに共有される任意数のメモリ部分をコピーすることができる。ノード１０２は、決定した実行内容に応じて、説明された操作の一部または全部を実行してもよく、何も実行しなくてもよい。

初期化中に、ノード１０２は、そのメインメモリ１０８のいずれか一部をシステム１００内の他のノードと共有しようとするか否かを決定する。共有する場合、ノード１０２は、そのメインメモリの一部を共有することを示す情報を他のノード１０２に一斉放送する。放送情報は、ノード１０２、共有メモリ２０２のサイズ、およびメインメモリ１０８における共有メモリ２０２の位置に関する情報を含むことができる。この情報は、システム１００内の他のノードに、共有メモリのアクセス場所を指示する。

ノード１０２は、別のノードがそのメインメモリの一部を共有しようとすることを示す放送情報を受け取ることができる。放送情報を受け取ったことに応答して、ノード１０２は、共有メモリ２０２をコピーするか否かを判断することができる。ノード１０２は、共有メモリをコピーすると決定した場合、共有メモリのコピーを格納するのに十分なコピーメモリを割り当てる。

一実施形態において、ノード１０２は、割り当てられたメモリにデータを配置しない。すなわち、ノードは、メモリを割り当てるが、共有メモリからデータをコピーしない。ノードは、コピーメモリ内の各複製キャッシュラインのバージョン値を、複製キャッシュラインが無効であることを示す値に設定する。一実施形態において、ノード１０２は、アプリケーションがデータを要求するまで、共有メモリのデータをコピーメモリにコピーしない。ノードが複製キャッシュラインをターゲットする操作を実行しようとする場合、バージョン値は、共有キャッシュラインが無効であることをノードに指示する。よって、ノードは、共有メモリ内のソースキャッシュラインをコピーメモリ内の複製キャッシュラインにコピーする。

一実施形態において、ノード１０２は、そのメインメモリ１０８の一部を共有する場合、メインメモリ１０８において、ディレクトリ構造２１０を格納するためのメモリを割り当てる。ディレクトリ構造２１０は、ノード１０２により共有された各メモリ部分のコピーを含むノードを示す。一実施形態において、ディレクトリ構造２１０は、共有メモリに位置する各共有キャッシュラインのディレクトリエントリを含む。換言すれば、各ソースキャッシュラインは、ディレクトリエントリに関連付けられている。したがって、各ソースキャッシュラインのディレクトリエントリは、どのノードがソースキャッシュラインのコピーである複製キャッシュラインを有することを示す。一実施形態において、ディレクトリエントリは、リモートノード内の各複製キャッシュラインが有効な（最新の）コピーであるか否かを示すことができる。一実施形態において、ディレクトリエントリは、ディレクトリエントリへのアクセスをシリアライズするためのロック手段を含むことができる。

一実施形態において、ノード１０２は、メインメモリ１０８において、インデックス構造２１２用のメモリを割り当てる。インデックス構造２１２は、メインメモリ１０８において各共有キャッシュラインのインデックスエントリを含む。ノード１０２が共有メモリにおいて共有キャッシュラインを共有する場合、インデックスエントリは、メインメモリ１０８において、共有キャッシュラインのディレクトリエントリの位置を示す。共有キャッシュラインがコピーメモリに位置する場合、インデックスエントリは、共有メモリを共有したソースノード、およびソースノードのメインメモリに位置する対応のソースキャッシュラインの位置を示す。一実施形態において、ノード１０２は、ソースノードからブロードキャスト情報を受け取って、共有メモリをコピーすると決定する場合に、インデックス構造２１２を更新する。ソースノードから受け取った情報は、インデックス構造２１２に格納された情報と同様であってもよい。

メモリ割り当ての例示
一実施形態において、ノード１０２は、メモリを割り当てる際に、メモリ位置にバージョン値を与える。例えば、アプリケーションがmalloc要求を実行する際に、ノード１０２は、要求されたメモリ量を割り当て、割り当てられたメモリに関連付けるバージョン値を生成し、アプリケーションにポインタを返送する。一実施形態において、割り当てられたメモリは、１つ以上の共有キャッシュラインを含む。バージョン値は、各共有キャッシュラインのバージョンビットにより示されてもよい。

一実施形態において、バージョン値は、アプリケーションのヒープマネージャによって生成される。バージョン値は、有効値の範囲から選択されてもよい。一実施形態において、１つ以上のバージョン値は、共有キャッシュラインが無効であることを示すために使用され、有効値の選択範囲に含まれていない。バージョン値の形式は、実装に依存して変更してもよい。例えば、バージョン値は、１６個の使用可能な値を生成する４ビットの長さを有してもよい。別の例において、バージョン値は、４４ビットのタイムスタンプであってもよい。

また、バージョン値は、割り当てられたメモリのポインタに関連付けられる。一実施形態において、ポインタは、バージョン値と仮想アドレスとの両方を含む。例えば、ノードは、４４ビットのレジスタを用いてポインタを格納する。仮想アドレスは、４４ビットの全体を使用しないため、バージョン値は、４４ビットレジスタの未使用の余分ビットに格納されてもよい。

割り当てられたメモリが共有メモリの一部として共有される場合、他のノード１０２は、割り当てられたメモリに位置する共有キャッシュラインを各々のコピーメモリにコピーしてもよい。一実施形態において、共有キャッシュラインのコピーは、関連するバージョン値をコピーすることを含む。他のノード１０２は、コピーされた共有キャッシュラインにポインタを生成してもよい。バージョン値は、生成された各ポインタに関連付けて格納されてもよい。

ポインタに基づくメモリ破損の検出
図３は、ポインタに関連付けられたバージョン値を用いて、ノード１０２内のメモリ破損を検出するための手順を示すフローチャートである。この手順は、バージョン値に関連付けられたポインタによって参照される共有キャッシュラインに関与するメモリ操作を実行する際に、行われてもよい。以下、この手順は、ポインタに基づくメモリ破損の検出として呼ばれる。

例えば、ノード１０２は、アプリケーションからコマンドを受け取る。コマンドは、例えば、ロードコマンドまたはストアコマンドなどのメモリ操作を実行するための要求であってもよい。コマンドの実行中に、ノード１０２は、メモリ破損を検出するためのステップを実行する。コマンドは、メインメモリ１０８に位置する共有キャッシュラインのポインタを含むことができる。上述したように、一実施形態において、ノード１０２がメモリをアプリケーションに割り当てる際に、ノードは、バージョン値に関連付けられたポインタを返送する。

ステップ３０２において、ノード１０２は、コマンドに含まれるポインタに関連付けられたバージョン値を判断する。一実施形態において、ポインタは、バージョン値を含む。ポインタに関連付けられたバージョン値は、コマンドによって要求した共有キャッシュラインに関連付けて欲しいバージョン値を示すことができる。例えば、コマンドがポインタを用いてデータ構造にアクセスする場合、バージョン値をデータ構造に関連付けることができる。

ステップ３０４において、ノード１０２は、ポインタのバージョン値と、要求した共有キャッシュラインに関連付けられたバージョン値とを比較する。一実施形態において、共有キャッシュラインのバージョンビットは、共有キャッシュラインに関連付けられたバージョン値を示す。次に、方法は、判断ブロック３０８に進む。

判断ブロック３０８において、ポインタのバージョン値が要求された共有キャッシュラインに関連付けられたバージョン値と一致しない場合、メモリ破損を検出する。一実施形態において、トラップ操作が実行される。トラップ操作は、メモリ破損が検出されたことをアプリケーションに指示することができる。トラップ操作は、メモリ操作の実行を中止することもできる。代替的に、検出手順が終了し、メモリ操作が継続する。

ポインタのバージョン値が要求された共有キャッシュラインに関連付けられたバージョン値と一致した場合、検出手順が終了し、メモリ操作が継続する。

ポインタに関連付けられたバージョン値を用いてメモリ破損を検出するための図３の手順は、さまざまなメモリ操作と共に、実行することができる。メモリ操作の詳細は、以下にさらに説明する。

ノード間のコヒーレンシ
一実施形態において、共有キャッシュラインのバージョン値を用いて、ノード間の共有キャッシュラインのコヒーレンシを管理することができる。ソースノードがソースキャッシュラインを更新すると、リモートノードに位置する複製キャッシュラインが古くなる。しかしながら、リモートノードは、複製キャッシュラインを直ちに更新せず、その代わりに、複製キャッシュラインが無効であることを示すように、各複製キャッシュラインのバージョン値を設定する。その後、リモートノードが複製キャッシュラインにアクセスしようとする際に、ノードは、複製キャッシュラインが無効であることを発覚し、複製キャッシュラインを更新する。

一実施形態において、ノード１０２は、ストアコマンドを実行する際に、トラップ操作を実行することができる。一実施形態において、ノード１０２は、目標とする共有キャッシュラインがソースキャッシュラインであるかまたは複製キャッシュラインであるかに応じて、異なる操作を実行する。目標とする共有キャッシュラインが複製キャッシュラインである場合、ノード１０２は、ストアをソースノード内のソースキャッシュラインに伝播する。一実施形態において、リモートノードは、ストアをソースノードに送信する前に、ストアをストアバッファに格納する。

一実施形態において、ノード１０２は、インデックス２１２を含む。要求された共有キャッシュラインが複製キャッシュラインである場合、インデックスエントリは、ソースノードおよびソースキャッシュラインの位置を複製キャッシュラインに指示する。したがって、ノード１０２は、インデックス２１２を参照して、要求された共有キャッシュラインが複製キャッシュラインであるかまたはソースキャッシュラインであるかを判断することができる。その判断に基づいて、ノード１０２は、ストアコマンドを実行するための操作を判断することができる。

リモートノードのロード
一実施形態において、ソースノードが対応するソースキャッシュラインを更新する際に、ノードは、複製キャッシュラインを更新しない。ノードは、複製キャッシュラインをノードにロードする際に、複製キャッシュラインを更新する。複製キャッシュラインが無効であることを示すバージョン値は、更新をトリガする。複製キャッシュラインを更新した後、メモリ破損の検出が行われる。図４は、ノード１０２が複製キャッシュラインを要求した場合、共有キャッシュラインを更新するための手順を示すフローチャートである。

ステップ４０２において、ノード１０２は、アプリケーションからコマンドを受け取る。例えば、コマンドは、ロードコマンドなどのロード操作に関与するメモリ操作であってもよい。

コマンドは、メインメモリ１０８に位置する共有キャッシュラインのポインタを含むことができる。一実施形態において、上述したように、ノード１０２は、アプリケーションにメモリを割り当てる際に、バージョン値を関連付けたポインタを返送する。説明のために、コマンドに含まれるポインタは、バージョン値を関連付けたものとする。

ステップ４０４において、ノード１０２は、バージョン値が共有キャッシュラインが無効であることを示しているか否かを判断する。一実施形態において、少なくとも１つのバージョン値は、共有キャッシュラインが無効であることを示す際に使用されるが、メモリを割り当てる間に使用されない。一実施形態において、共有キャッシュラインは、複製キャッシュラインである。バージョン値は、例えば、複製キャッシュラインがデータと共にソースキャッシュラインから伝播されていない場合、共有キャッシュラインが無効であることを示すことができる。要求された共有キャッシュラインは、複製キャッシュラインであってもよく、複製キャッシュラインではなくてもよい。

一例において、共有キャッシュラインは、複製キャッシュラインではない。一実施形態において、コピーメモリに位置していない共有キャッシュラインは、常に有効であると推定される。

別の例において、共有キャッシュラインは、複製キャッシュラインである。共有キャッシュライン内のデータは、古くなっている可能性がある。すなわち、複製キャッシュライン内のデータは、ソースキャッシュライン内のデータと同様ではない。このような状況は、例えば、ソースノードがデータをソースキャッシュラインに格納する場合に、発生する可能性がある。

その後、方法は、判断ブロック４０６に進む。判断ブロック４０６において、バージョン値が、共有キャッシュラインが有効であることを示す場合、ノード１０２は、手順の実行を継続し、ステップ４１０に進み、ポインタに基づくメモリ破損の検出を行う。

バージョン値が、共有キャッシュラインが無効であることを示す場合、方法は、ステップ４０８に進む。ステップ４０８において、ノードは、コマンドの実行を中断し、トラップ操作を行う。

一実施形態において、トラップ操作は、ソースキャッシュラインを複製キャッシュラインにコピーすることを含む。ソースキャッシュラインのコピーは、ソースキャッシュラインのバージョンビットおよびデータビットのコピーを含む。したがって、コピーを実行した後、複製キャッシュラインのバージョン値は、ソースキャッシュラインのバージョン値に設定される。複製キャッシュライン内のデータは、ソースキャッシュラインに伝播されていないストアバッファに記録されたリモートノードによって、任意のストアが複製キャッシュラインに対する修正を行うと同様に、ソースキャッシュライン内の最新データに設定される。したがって、ノードは、他のノードとのコヒーレンシを維持するために、共有キャッシュライン内のデータを更新することができる。

一実施形態において、ノードは、インデックス２１２を含む。ノードは、要求された共有キャッシュラインに対応するインデックスエントリを用いて、対応するソースキャッシュラインを含むソースノード、およびノードソースノードのメインメモリに位置する対応のソースキャッシュラインの位置を判断することができる。

一実施形態において、ソースノードは、ディレクトリ２１０を含む。リモートノードがその複製キャッシュラインを更新する時に、ソースノードは、対応するソースキャッシュラインのディレクトリエントリを更新することによって、リモートノード内のコピーが有効なコピーであることを示すことができる。

リモートノードのストア
前述したように、一実施形態において、リモートノードは、ストアをソースノードに送信する前に、ストアバッファを用いてストアを記録する。図５Ａは、分散ノードシステム１００内のリモートノード１０２によって実行されるストアを説明するフローチャートである。ストアを実行することによって、ストアコマンドを実行することができる。コマンドは、メインメモリ１０８に位置する複製キャッシュラインのポインタを含むことができる。ポインタに、バージョン値を関連付けてもよい。

ステップ５０２において、ノード１０２は、コマンドの実行を中断し、トラップ操作を実行して、以下のステップを実行する。

ステップ５０４において、ストアをストアバッファに記録する。ストアバッファに記録された情報は、ストアを実行するおよびデータを記憶するためのメモリの位置を示すことができる。ストアバッファにストアを記録することは、ソースノード、ストアを実行すべきソースノードのメインメモリに位置するソースキャッシュラインの位置、格納スレッド、およびストアに関連付けられたバージョン値を示すことを含んでもよい。

一実施形態において、ノード１０２は、インデックス２１２を含む。ノードは、要求された共有キャッシュラインに対応するインデックスエントリを用いて、対応するソースキャッシュラインを含むソースノード、およびノードソースノードのメインメモリに位置する対応のソースキャッシュラインの位置を判断することができる。

ステップ５０６において、ノード１０２は、複製キャッシュラインのバージョン値が複製キャッシュラインが無効であることを示しているか否かを判断する。バージョン値が共有キャッシュラインが無効であることを示す場合、共有キャッシュラインにストアを実行しない。バージョン値が複製キャッシュラインが有効であることを示す場合、方法は、ステップ５０８に進む。

ステップ５０８において、ノード１０２は、ポインタに基づくメモリ破損の検出を実行する。ノード１０２によって実行されるポインタに基づくメモリ破損の検出は、メモリ破損を検出しない場合、方法は、ステップ５１０に進む。

ステップ５１０において、ノード１０２は、共有キャッシュラインにデータを格納する。

トラップ操作が終了する。
アップデートの伝播
一実施形態において、リモートノードは、ストアをストアバッファに記録するが、このストアを対応のソースキャッシュラインを含むソースノードに送信しない。ノードは、ストアをストアバッファに記録した後、ストアをソースノードに伝播する必要がある。ストアの伝播は、ストアバッファを記録する手順と同様の手順の一部として実行されてもよく、または別々に実行されてもよい。一実施形態において、ノードは、ストア伝播操作を含むコマンドを受け取ることができる。例えば、ストアコマンドは、ストアを伝播するための命令を含んでもよい。ストアは、トラップ操作が完了した後、ストアコマンドの再開実行の一部として、伝播されてもよい。別の実施形態において、ノード１０２は、エントリを共有キャッシュラインに書き込む前に、ストアバッファにエントリを検索することができる。図５Ｂは、分散ノードシステム１００におけるストアの伝播を示すフローチャートである。ストアは、別の実行スレッドによって、非同期的に伝播されてもよい。

ステップ５２２において、ノードは、ストアバッファからエントリを検索する。エントリは、ソースノード、ストアを実行すべきソースキャッシュライン、格納すべきデータ、ストアに関連付けられたバージョン番号、および格納スレッドを示す情報を含むことができる。

ステップ５２４において、ノード１０２は、キャッシュラインのために、ソースノードからリモートノードのリストを要求する。情報を受け取った後、方法は、ステップ５２６に進む。

一実施形態において、ソースノードは、要求に応じて、共有キャッシュラインのディレクトリエントリを参照する。ディレクトリエントリは、ソースキャッシュラインのコピーを格納しているノードを指示する。システム１００内の任意数のノードは、ソースキャッシュラインのコピーを含んでもよい。一実施形態において、要求された共有キャッシュラインのディレクトリエントリにアクセスする際に、ソースノードは、そのディレクトリエントリをロックすることができる。一実施形態において、ソースノードは、ソースキャッシュラインの有効コピーを含むリモートノードのリストのみを共有する。ディレクトリエントリは、すべてのリモートノードが無効コピーを含むことを指示するように、更新されてもよい。

ステップ５２６において、ノード１０２は、ソースキャッシュラインのコピーを含む他のリモートノードに指示して、リモートノードの複製キャッシュラインを無効にマークすることができる。ノードは、ソースキャッシュライン内のデータが変更されたことを、複製キャッシュラインを各々保持しているノードに指示する。リモートノードに位置する複製キャッシュラインのバージョン値は、複製キャッシュラインが無効であることを示すように、変更される。

ステップ５２８において、ノード１０２は、ストアを実行するようにソースノードに通知する。通知は、ソースノードのメインメモリに位置するソースキャッシュラインの位置、ソースキャッシュラインに格納されるデータ、およびバージョン番号を含むことができる。ストアを実行する前に、ソースノードは、ストアバッファからのバージョン番号と各ソースキャッシュラインのバージョン番号とを比較する。バージョンの不一致が検出された場合、ソースノードは、ストアを実行せず、例えば、非同期トラップを介して、発行するスレッドに通知する。

ステップ５３０において、格納されたデータは、ストアバッファから削除される。
一実施形態において、これらのステップは、ストアバッファ内の各エントリに対して、繰り返して行われる。

代替的な一実施形態において、リモートノードは、ストアをストアバッファに記録しない。ストアをストアバッファに書き込む代わりに、リモートノードは、トラップ操作の実行中に、アップデート伝播ステップを実行する。

ソースノードのストア
一実施形態において、ソースノードは、ストアバッファを使用せず、ストアコマンドを実行することによって、共有キャッシュラインを格納する。図６は、分散ノードシステム１００内のストアコマンドを実行するように、ソースノード１０２によって行われたステップを示すフローチャートである。ストアコマンドは、メインメモリ１０８に位置するソースキャッシュラインのポインタを含むことができる。ポインタには、バージョン値を関連付けてもよい。

ステップ６０２において、ノード１０２は、ストアコマンドの実行を中断し、トラップ操作を実行する。

ステップ６０４において、ノード１０２は、ソースキャッシュラインのために、ポインタに基づくメモリ破損の検出を実行する。メモリ破損が検出されない場合、方法は、ステップ６０６に進む。メモリ破損が検出された場合、方法は、ストアを実行せず、トラップ操作を終了する。

ステップ６０６において、ノード１０２は、各々の複製キャッシュラインを無効にするように、リモートノードに指示する。ノード１０２は、ソースキャッシュライン内のデータが変更されたことを各リモートノードに通知する。リモートノードに位置する複製キャッシュラインのバージョン値は、複製キャッシュラインが無効であることを示すように、変更される。

一実施形態において、ソースノードは、共有キャッシュラインのディレクトリエントリを参照する。ディレクトリエントリは、ソースキャッシュラインのコピーを格納しているノードを指示する。システム１００内の任意数のノードは、ソースキャッシュラインのコピーを含んでもよい。ノードは、ソースキャッシュラインをコピーしている各ノードに、データが変更されたことを指示する。他のノードに位置する複製キャッシュラインのバージョン値は、複製キャッシュラインが無効であることを示すように、変更される。

一実施形態において、ソースキャッシュラインの無効化が記録され、無効化する命令が遅延をもってリモートノードに送信される。例えば、ストアを実行するスレッド以外のスレッドは、無効化されたソースキャッシュラインの記録を発見してから、ソースキャッシュラインのコピーである複製キャッシュラインを無効にする命令をリモートノードに送信する。

ステップ６０８において、ソースノードは、ソースキャッシュライン上でストアを実行する。

ソースノードは、トラップ操作を終了させる。
ハードウェアの概要
一実施形態によれば、本明細書に記載された技術は、１つ以上の専用コンピューティング装置によって実現される。専用コンピューティング装置は、本発明の技術を実行するために配線で連結されてもよく、または本発明の技術を実行するように反復にプログラムされる１つ以上の特定用途向け集積回路（ＡＳＩＣ）またはフィールドプログラマブルゲートアレイ（ＦＰＧＡ）などのデジタル電子機器を含んでもよく、またはファームウェア、メモリ、他の記憶装置、またはその組み合わせに記憶されたプログラム命令に従って、本発明の技術を実行するようにプログラムされる１つ以上の汎用ハードウェアプロセッサを含んでもよい。これらの専用コンピューティング装置は、本発明の技術を達成するために、カスタムハードワイヤードロジック、ＡＳＩＣ、またはカスタムプログラミングを備えるＦＰＧＡと併用することができる。本発明の技術を実現するために、専用コンピューティング装置は、デスクトップコンピュータシステム、ポータブルコンピュータシステム、携帯式装置、ネットワーク装置、またはハードワイヤードジックおよび／またはプログラムロジックを組み込んだ他の任意の装置であってもよい。

例えば、図７は、本発明の一実施形態を実現し得るコンピュータシステム７００を示すブロック図である。コンピュータシステム７００は、情報を通信するためのバス７０２または他の通信機構、およびバス７０２に連結され、情報を処理するためのハードウェアプロセッサ７０４を含む。ハードウェアプロセッサ７０４は、例えば、汎用のマイクロプロセッサであってもよい。

コンピュータシステム７００は、バス７０２に連結され、プロセッサ７０４によって実行される情報および命令を記憶するためのメインメモリ７０６、例えば、ランダムアクセスメモリ（ＲＡＭ）または他の動的記憶装置を含む。プロセッサ７０４が命令を実行する間に、メインメモリ７０６は、一時変数または他の中間情報を記憶することができる。プロセッサ７０４にアクセス可能な非一時的記憶媒体に記憶されたこれらの命令は、命令により指定された操作を実行するように、コンピュータシステム７００を専用マシンに改造することができる。

コンピュータシステム７００は、さらに、バス７０２に連結され、プロセッサ７０４用の静的情報および命令を記憶するための読み出し専用メモリ（ＲＯＭ）７０８または他の静的記憶装置を含む。バス７０２に連結され、情報および命令を記憶するための磁気ディスク、光ディスクまたは固体ドライブなどの記憶装置７１０が設けられる。

情報をコンピュータユーザに表示するために、コンピュータシステム７００は、例えば、バス７０２を介して、陰極線管（ＣＲＴ）などのディスプレイ７１２に連結されてもよい。情報およびコマンドの選択をプロセッサ７０４に通信するために、英数字および他のキーを含む入力装置７１４は、バス７０２に連結される。方向情報およびコマンド選択をプロセッサ７０４に通信するためおよびディスプレイ７１２上のカーソルの動きを制御するための他の種類のユーザ入力装置は、マウス、トラックボールまたは他のカーソル方向キーなどのカーソル制御７１６を含む。このような入力装置は、通常２つの軸、すなわち、第１軸（例えば、ｘ軸）および第２軸（例えば、ｙ軸）に２つの自由度を有するため、平面に位置を指定することができる。

コンピュータシステム７００は、コンピュータシステムと併用すると、コンピュータシステム７００を専用マシンにカスタマイズするまたはプログラムするカスタムハードワイヤードロジック、１つ以上のＡＳＩＣまたはＦＰＧＡ、ファームウェアおよび／またはプログラムロジックを用いて、本明細書に記載の技術を実現することができる。一実施形態によれば、コンピュータシステム７００は、メインメモリ７０６に記憶される１つ以上の命令の１つ以上のシーケンスを実行するプロセッサ７０４に応答して、本明細書に記載の技術を実行する。これらの命令は、記憶装置７１０などの他の記憶媒体からメインメモリ７０６に読み込まれてもよい。プロセッサ７０４は、メインメモリ７０６に記憶される１つ以上の命令のシーケンスを実行すると、本明細書に記載された手順を実行する。代替的な実施形態において、ソフトウェア命令の代わりにまたはソフトウェア命令と組み合わせて、ハードワイヤード回路を使用することができる。

「記憶媒体」という用語は、本明細書に使用される場合、マシンを特定の方法で動作させるデータおよび／または命令を格納する任意の非一時的媒体を指す。このような記憶媒体は、不揮発性媒体および／または揮発性媒体を含むことができる。不揮発性媒体は、光ディスク、磁気ディスクまたは固体ドライブ、例えば記憶装置７１０を含む。揮発性媒体は、動的メモリ、例えば記憶媒体７０６を含む。一般的な記憶装置は、フロッピー（登録商標）ディスク、フレキシブルディスク、ハードディスク、固体ドライブ、磁気テープまたは任意の他の磁気データ記憶媒体、ＣＤ−ＲＯＭ、任意の他の光学データ記憶媒体、穴パターンを有する任意の物理的媒体、ＲＡＭ、ＡＰＲＯＭ、ＥＰＲＯＭ、フラッシュＥＰＲＯＭ、ＮＶＲＡＭ、任意の他のメモリチップまたはカートリッジを含む。

記憶媒体は、伝送媒体と異なるものであるが、伝送媒体と併用することができる。伝送媒体は、記憶媒体間の情報伝送に関与する。例えば、伝送媒体は、バス７０２を構成する同軸ケーブル、銅線および光ファイバを含む。また、伝送媒体は、無線データ通信または赤外線データ通信に生成される音波または光波を伝送することができる。

さまざまな種類の媒体は、１つ以上の命令の１つ以上のシーケンスをプロセッサ７０４に搬送して実行することに関与する。例えば、命令は、最初にリモートコンピュータの磁気ディスクまたは固体ドライブに保持されてもよい。リモートコンピュータは、命令を動的メモリに読み込み、モデムを用いて、電話回線を介して命令を送信することができる。コンピュータシステム７００のモデムは、電話回線からデータを受信し、赤外線発信機を用いて、データを赤外線信号に変換することができる。赤外線検出器は、赤外線信号により搬送されたデータを受信し、適切な回路は、データをバス７０２上に置くことができる。バス７０２は、データをメインメモリ７０６にして、プロセッサ７０４は、メインメモリ７０６から命令を取り出して実行する。必要に応じて、メインメモリ７０６が受け取った命令は、プロセッサ７０４に実行される前にまたは後に、記憶装置７１０に記憶されてもよい。

また、コンピュータシステム７００は、バス７０２に接続された通信インターフェイス７１８を含む。通信インターフェイス７１８は、ローカルネットワーク７２２に接続されたネットワークリンク７２０に双方向データ通信を提供する。通信インターフェイス７１８は、例えば、対応する種類の電話回線にデータ通信接続を提供する統合サービスデジタルネットワーク（ＩＳＤＮ）カード、ケーブルモデム、衛星モデム、またはモデムであってもよい。別の例として、通信インターフェイス７１８は、互換性のあるＬＡＮにデータ通信接続を提供するローカルエリアネットワーク（ＬＡＮ）カードであってもよい。無線リンクに実装されてもよい。いずれかの実装において、通信インターフェイス７１８は、さまざまな種類の情報を表すデジタルデータストリームを搬送する電気信号、電磁信号または光信号を送受信する。

ネットワークリンク７２０は、一般的には、１つ以上のネットワークを介して、他のデータ装置にデータを通信する。例えば、ネットワークリンク７２０は、ローカルネットワーク７２２を介してホストコンピュータ７２４に接続するまたはインターネットサービスプロバイダ（ＩＳＰ）７２６によって動作されるデータ機器に接続する。これによって、ＩＳＰ７２６は、現在一般的に「インターネット」７２８と呼ばれているワールドワイドパケットデータ通信ネットワークを介して、データ通信サービスを提供する。ローカルネットワーク７２２およびインターネット７２８の両方は、電気信号、電磁信号または光信号を使用して、デジタルデータストリームを搬送する。さまざまなネットワークを介してまたはネットワークリンク７２０および通信インターフェイス７１８を介して、デジタルデータをコンピュータシステム７００に搬送するまたはそれから搬送する信号は、伝送媒体の例示的な形態である。

コンピュータシステム７００は、ネットワーク、ネットワークリンク７２０および通信インターフェイス７１８を介して、メッセージを送信し、プログラムコードを含むデータを受信することができる。インターネットの例において、サーバ７３０は、インターネット７２８、ＩＳＰ７２６、ローカルネットワーク７２２および通信インターフェイス７１８を介して、応用プログラムのために要求されたコードを送信することができる。

送信されたコードは、受信されると、プロセッサ７０４によって実行され、および／または将来に実行するために、記憶装置７１０または他の不揮発性記憶装置に記憶されてもよい。

上記の明細書において、本発明の実施形態は、実現例毎に異なる可能性がある多数の特定の詳細を参照して説明されている。したがって、明細書および図面は、限定的な意味ではなく例示として考えられるべきである。本発明の範囲を表す唯一かつ排他的な指標、すなわち、出願人が意図している発明の範囲は、本願の特許請求の範囲の具体的な記載および後続補正の文言上範囲およびその同等物である。

Claims (17)

1. 方法であって、
   ローカルノードのメモリにおいて、ソースノード上のソースキャッシュラインのコピーである複製キャッシュラインを生成するステップを備え、前記複製キャッシュラインは、バージョンビットとデータビットとを含み、前記バージョンビットは、バージョン値に設定され、
   前記複製キャッシュラインを指し示すポインタを生成するステップを備え、前記ポインタの値は、前記バージョン値を含み、
   前記ポインタを用いて、前記複製キャッシュラインに対してメモリ操作を実行するステップを備え、
   前記メモリ操作を実行するステップは、
   前記ポインタに含まれるバージョン値と、前記複製キャッシュラインの前記バージョンビットが設定された前記バージョン値とを比較するステップと、
   前記比較に基づいて、メモリ破損が発生しているか否かを判断するステップとを含む、方法。
2. 前記複製キャッシュラインを生成するステップは、
   前記ソースキャッシュラインのバージョン値を判断するステップと、
   前記バージョンビットを前記ソースキャッシュラインのバージョン値に設定するステップとを含む、請求項１に記載の方法。
3. 前記バージョン値は、メモリ割り当て要求に応答して、前記ソースノードによって生成される、請求項２に記載の方法。
4. 前記バージョン値を比較するステップは、
   前記複製キャッシュラインが無効であるか否かを判断するステップと、
   前記複製キャッシュラインが無効であるという決定に応答して、前記ソースキャッシュラインを前記複製キャッシュラインにコピーするステップとを含む、請求項１に記載の方法。
5. 前記ローカルノードによって、前記ソースキャッシュラインに伝播されていない複製キャッシュラインの１つ以上のアップデートをストアバッファに格納するステップと、
   前記複製キャッシュラインが無効であるという決定に応答して、前記１つ以上のアップデートを前記複製キャッシュラインに伝播するステップとをさらに備える、請求項４に記載の方法。
6. メモリ破損が発生した場合、トラップ操作を実行するステップをさらに備える、請求項１に記載の方法。
7. 前記トラップ操作を実行するステップは、メモリ破損が発生したことをアプリケーションに通知するステップを含む、請求項６に記載の方法。
8. 前記トラップ操作を実行するステップは、前記メモリ操作を終了させるステップを含む、請求項６の方法。
9. コンピュータシステムであって、
   １つ以上のコンピューティングノードを備え、前記１つ以上のコンピューティングノードの各コンピューティングノードは、
   前記各コンピューティングノードのメモリにおいて、前記１つ以上のコンピューティングノードに属するソースノード上のソースキャッシュラインのコピーである複製キャッシュラインを生成するように構成され、前記複製キャッシュラインは、バージョンビットとデータビットとを含み、前記バージョンビットは、バージョン値に設定され、
   前記複製キャッシュラインを指し示すポインタを生成するように構成され、前記ポインタの値は、前記バージョン値を含み、
   前記ポインタを用いて、前記複製キャッシュラインに対してメモリ操作を実行するように構成され、
   前記メモリ操作は、
   前記ポインタに含まれるバージョン値と、前記複製キャッシュラインの前記バージョンビットが設定された前記バージョン値とを比較するステップと、
   前記比較に基づいて、前記複製キャッシュラインが破損しているか否かを判断するステップとを含む、システム。
10. 複製キャッシュラインを生成するために、前記１つ以上のコンピューティングノードの各コンピューティングノードは、前記ソースキャッシュラインのバージョン値を判断し、前記バージョンビットを前記ソースキャッシュラインのバージョン値に設定するように構成されている、請求項９に記載のシステム。
11. 前記バージョン値は、ソースノードによって、前記１つ以上のコンピューティングノードのコンピューティングノード毎に生成され、
    前記ソースノードは、メモリ割り当て要求に応答して、バージョン値を生成するように構成されている、請求項１０に記載のシステム。
12. 前記１つ以上のコンピューティングノードのコンピューティングノード毎に前記バージョン値を比較するために、各コンピューティングノードは、前記複製キャッシュラインが無効であるか否かを判断し、前記複製キャッシュラインが無効である場合、前記ソースキャッシュラインを前記複製キャッシュラインにコピーするように構成されている、請求項９に記載のシステム。
13. 各コンピューティングノードは、前記１つ以上のコンピューティングノードのコンピューティングノード毎に、
    前記ソースキャッシュラインに伝播されていない複製キャッシュラインの１つ以上のアップデートをストアバッファに格納し、
    前記複製キャッシュラインが無効であるという決定に応答して、前記１つ以上のアップデートを前記複製キャッシュラインに伝播するように構成されている、請求項９に記載のシステム。
14. 前記１つ以上のコンピューティングノードのコンピューティングノード毎にトラップ操作を実行するために、１つ以上のコンピューティングノードは、メモリ破損が発生した場合、トラップ操作を実行するように構成されている、請求項９に記載のシステム。
15. 前記１つ以上のコンピューティングノードのコンピューティングノード毎にトラップ操作を実行するために、１つ以上のコンピューティングノードは、メモリ破損が発生したことをアプリケーションに通知するように構成されている、請求項１４に記載のシステム。
16. トラップ操作を実行するために、前記１つ以上のコンピューティングノードの各コンピューティングノードは、メモリ操作を終了させるように構成されている、請求項１４に記載のシステム。
17. １つ以上のプロセッサによって実行されると、請求項１〜８のいずれか１項に記載の方法を実行される命令を格納する１つ以上の非一時的記憶媒体。

Images