(57)【特許請求の範囲】
【請求項１】
方法を実行するための実行可能プログラム命令を含むコンピュータ可読記録媒体であって、前記方法は、
複数のネットワークノードであって各ノードが該ノード自身のローカルオブジェクト記憶装置を有する複数のネットワークノードにおいて、前記オブジェクト記憶装置によりオブジェクトを記憶し、１または複数のオブジェクトを共用するステップであって、前記オブジェクトが前記ネットワークノードにわたってグローバルに固有のオブジェクト名を有し、前記オブジェクト名は、前記オブジェクトが前記ノードでどこに記憶されるかに基づいて変化しない、ステップと、
前記ローカルオブジェクト記憶装置で記憶される任意のオブジェクトインスタンスとは独立したオブジェクト名のローカル参照のローカル参照カウントＬＲＣを各ノードで維持するステップであって、前記ＬＲＣが符号付きの整数として維持され、ローカルの新たな参照および参照解除ごとに前記ＬＲＣに対して調節がなされ、オブジェクト名を参照解除することにより、負のＬＲＣ値を生成することができる、ステップと、
オブジェクト名の所有権は異なるノードに割り当てられ、ある範囲のオブジェクト名は前記ネットワークノードのうちの１つに割り当てられ、所有権が割り当てられたノードである所有者ノードが、前記範囲のすべてまたは１サブセットについてのグローバル参照カウントＧＲＣ判定ステップを開始するステップと
を含み、前記ＧＲＣ判定ステップは、
前記所有者ノードにより、ＧＲＣが判定されるオブジェクトについての固有のタグを提供するステップと、
前記複数のノードによりメッセージを前記固有のタグとともに交換するステップであって、前記所有者ノードに他のノードは前記オブジェクトについての該他のノードのＬＲＣを提供する、ステップと、
前記所有者ノードにより、前記ＧＲＣを、前記他のノードから受けた前記ＬＲＣと、該所有者ノードの前記オブジェクトについての前記ＬＲＣとの合計として計算するステップと、
生じた前記ＧＲＣがゼロである場合に、前記所有者ノードにより、削除メッセージを前記固有のタグと共に前記他のノードに送るステップと
を含むことを特徴とするコンピュータ可読記録媒体。
【請求項２】
請求項１に記載の媒体であって、前記方法が、
前記ＧＲＣのカウントがゼロであるときに、前記所有者ノードおよび前記他のノードにより前記オブジェクトを削除するステップ
を含むことを特徴とする媒体。
【請求項３】
請求項２に記載の媒体であって、前記判定ステップが、
前記ノードが、ノードのピアトゥピアネットワークとして動作するステップ
を含むことを特徴とする媒体。
【請求項４】
請求項３に記載の媒体であって、前記ＧＲＣは、前記オブジェクトが読取られるかまたは前記オブジェクトに書込みがされ、ローカルオブジェクト参照カウントが修正される際に計算されることを特徴とする媒体。
【請求項５】
請求項１に記載の媒体であって、ローカルオブジェクト記憶装置は前記グローバルに固有のオブジェクト名の名前空間を集合的に備えることを特徴とする媒体。
【請求項６】
請求項１に記載の媒体であって、前記方法は、
前記ローカルオブジェクト記憶装置により、オブジェクト名のローカルマッピング索引、ＬＲＣ、および、前記オブジェクトが前記ローカルオブジェクト記憶装置上で記憶される任意の物理オブジェクト場所へのポインタを維持するステップ
を含むことを特徴とする媒体。
【請求項７】
請求項１に記載の媒体であって、各オブジェクトが、そのオブジェクト名として前記オブジェクトの内容から導出されたオブジェクトフィンガープリントを有することを特徴とする媒体。
【請求項８】
請求項７に記載の媒体であって、前記フィンガープリントが、前記オブジェクト内容のハッシュを含むことを特徴とする媒体。
【請求項９】
請求項１に記載の媒体であって、ファイルシステムが、該ファイルシステムのすべての永続的データを記憶するための方法として集合的に前記ローカルオブジェクト記憶装置を使用することを特徴とする媒体。
【請求項１０】
請求項９に記載の媒体であって、
すべてのファイルシステムデータ、メタデータおよびファイルが、１つまたは複数の前記オブジェクト記憶装置のオブジェクトを含み、各オブジェクトがそのオブジェクト名としてオブジェクトフィンガープリントを有し、
ファイルシステムオブジェクトの集合体が、１つまたは複数の前記オブジェクト記憶装置のオブジェクトも含み、各集合体が複数の前記ファイルシステムオブジェクトのマッピングを含み、前記集合体の前記内容から導出された該集合体自体のオブジェクトフィンガープリントを有し、前記集合体の１つまたは複数のオブジェクトへの変更により前記集合体のオブジェクトフィンガープリントが変更され、
ファイルシステムルートオブジェクトが、名前空間ファイルシステム内のあらゆるオブジェクトがルートオブジェクトを介してアクセス可能であるような、該ファイルシステムの全ての前記オブジェクトから導出されたルートオブジェクトフィンガープリントを有する
ことを特徴とする媒体。
【請求項１１】
請求項１に記載の媒体であって、前記方法が、
ネットワークまたはシステムの性能または信頼性に基づき、前記オブジェクト名とは独立したオブジェクトの１つまたは複数のインスタンスを記憶するための１つまたは複数の場所として前記ノードのうちの１つまたは複数を選択するステップ
を含むことを特徴とする媒体。
【請求項１２】
請求項１に記載の媒体であって、
１または複数のオブジェクトを共用する前記ステップが、記憶されたオブジェクトのオブジェクト名、ＬＲＣおよび場所に関してノード間で通信するステップを含む
ことを特徴とする媒体。
【請求項１３】
請求項１に記載の媒体であって、前記方法が、
アプリケーションがオブジェクト名を参照解除し、前記オブジェクトのコピーがローカルノードで記憶されていないときに、前記ローカルノードによりマイナス１のＬＲＣを生成するステップ
を含むことを特徴とする媒体。
【請求項１４】
請求項１に記載の媒体であって、記憶システムが、該記憶システムのすべての永続的データを記憶するための方法として集合的に前記ローカルオブジェクト記憶装置を使用することを特徴とする媒体。
【請求項１５】
複数のネットワークノードであって、各ノードがそれぞれの前記ノードでオブジェクトを記憶するためのローカルオブジェクト記憶装置を有し、前記オブジェクトが前記ネットワークノードにわたってグローバルに固有のオブジェクト名を有し、前記オブジェクト名は、前記オブジェクトが前記ノードでどこに記憶されるかに基づいて変化しない、複数のネットワークノードと、
前記オブジェクトのうちの１つまたは複数を共用する前記ローカルオブジェクト記憶装置と、
オブジェクトとして永続的データを記憶するための前記ローカルオブジェクト記憶装置を使用するアプリケーションであって、前記複数のノードをわたるそれぞれの前記オブジェクトへの独立の経路の数を含む前記ネットワークノードで記憶された各オブジェクトの参照カウントを必要とするアプリケーションと、
前記ローカルオブジェクト記憶装置で記憶された任意のオブジェクトインスタンスとは独立したオブジェクト名の参照のローカル参照カウントＬＲＣを各ノードで維持するための手段であって、前記ＬＲＣが符号付きの整数として維持され、ローカルの新たな参照および参照解除ごとに前記ＬＲＣに対して調節がなされ、オブジェクト名を参照解除することにより、負のＬＲＣ値を生成することができる、手段と、
オブジェクトのグローバル参照カウントＧＲＣを判定するための手段と
を備えた装置であって、オブジェクト名の所有権が異なるノードに割り当てられ、ある範囲のオブジェクト名が前記ネットワークノードのうちの１つに割り当てられ、所有権が割り当てられたノードである所有者ノードは、判定する前記手段に、前記範囲のすべてまたは１サブセットについてのＧＲＣ判定ステップを開始させるように構成され、ＧＲＣを判定するための前記手段及び前記ノードは、前記ＧＲＣ判定ステップを実施するように構成され、該ＧＲＣ判定ステップは、
前記所有者ノードにより、ＧＲＣが判定されるオブジェクトについての固有のタグを提供するステップと、
前記複数のノードによりメッセージを前記固有のタグと共に交換するステップであって、前記所有者ノードに他のノードは前記オブジェクトについての該他のノードのＬＲＣを提供する、ステップと、
前記所有者ノードにより、前記ＧＲＣを、前記他のノードから受けた前記ＬＲＣと、該所有者ノードの前記オブジェクトについての前記ＬＲＣとの合計として計算するステップと、
生じた前記ＧＲＣがゼロである場合に、前記所有者ノードにより、削除メッセージを前記固有のタグと共に前記他のノードに送るステップと
を含むことを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
[001]本発明は、データオブジェクトの記憶に関し、より詳細には、オブジェクトの参照のグローバルビューを維持しながら、ピアトゥピアネットワーク内の複数のノードで記憶されたオブジェクトを追跡するための方法および装置に関する。
【背景技術】
【０００２】
[002]性能または冗長性を目的として、現代の記憶システムは、ＴＣＰ／ＩＰネットワークなどネットワークと相互接続された、ノードと称される、離散的構成要素から構築され得る。各ノードは、通常は、ＣＰＵ、記憶装置、メモリなどを有する完全に機能するコンピュータである。そのようなシステム内のノードの編成は、ピアトゥピアネットワークでもよく、これはすべてのノードが同等であることを意味する（すなわち、中央の管理権限は存在せず、どのノードも特権を与えられない）。同等のピアとして、ノードは、それらの間で通信して状態を解決する。記憶システムをピアトゥピアネットワークとして編成することで、ノードは性能および／または容量を徐々に増やすことができ、１つのノードが故障した場合、その記憶システムはまた作動するので、より回復力のあるスケーラブルなストレージ解決策を提供することができる。
【０００３】
[003]単なるコンピュータの集合体とピアトゥピアネットワーク記憶システムを区別するものは、そのシステム内のノードが、下にあるデータ記憶装置、各ノードの健全性などに関して互いに通信するということである。具体的には、そのシステム内のノードは、性能およびデータ完全性を目的として情報を複写および交換することができる。この情報は、データオブジェクトまたはファイルの形でもよく、オブジェクトはファイルの一部でもよい。
【０００４】
[004]オブジェクトがそのシステムを介して伝播されるとき、データ構造体は、ａ）どこにそれらのオブジェクトがあるかを知っていること、およびｂ）いつそれらのオブジェクトがもはや必要とされなくなるかを知っていることが必要とされる。オブジェクトが参照カウント、すなわちオブジェクトが別のオブジェクトまたは他のデータ構造体によって参照される回数、を有する、先行技術のシステムでは、オブジェクトは、その参照カウントがゼロまで下がったときに、安全に割当てを解除するまたは削除すること（たとえば、ごみ集め）が可能である。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
[005]しかし、毎秒数百万のオブジェクトが渡されているとき、数十億のオブジェクトの参照カウントを追跡することは、単純化したアルゴリズムが使用される場合、受け入れ難いネットワークトラフィックおよびＣＰＵコストをもたらす。
【０００６】
[006]もう１つの課題は、参照カウントが実際にゼロであることを判定し、次いで、すべてのオブジェクトインスタンスが削除され得るようにそれらを発見することである。オブジェクトを追跡してこれらの問題を克服するためのより効率的なおよび高信頼のプロトコルへの継続的なニーズが存在する。
【課題を解決するための手段】
【０００７】
[007]本発明の一態様では、複数のネットワークノードにわたるオブジェクト参照を追跡するためのシステムおよび方法が提供され、オブジェクトはネットワークの１つまたは複数のノードでオブジェクトの１つまたは複数のインスタンス（オブジェクトのインスタンスが同一データを含む）を記憶することによってノードの間で分散される。このネットワークでは、その間に何らかの階層またはマスタ／スレーブ関係、すなわち１つのインスタンスが１次である、または別のインスタンスより特権的である関係が存在するインスタンスとは対照的に、オブジェクトのインスタンスは、すべて同等（ピアトゥピア）でもよい。これらのピアトゥピアインスタンスは、集中型管理エージェントなしで、ネットワークノードによって集合的に管理され得る。本発明の様々な実施形態に従って以下に記載されるように、複数のネットワークノードに記憶されたこれらのオブジェクトインスタンスを追跡するための方法およびシステムが提供され、その追跡は、いつオブジェクトがそのネットワークノードにわたって参照を有さず、安全に割当てを解除することができるかのグローバル判定を可能にする。
【０００８】
[008]本発明の一態様によれば、各ノードは、オブジェクトを追跡し、任意選択でそのノードでオブジェクトを記憶するためのローカルオブジェクト記憶装置を有し、そのローカルオブジェクト記憶装置は、そのネットワークにわたってそのオブジェクトのローカルに記憶されたインスタンスを集合的に共用する。１つまたは複数のアプリケーション、たとえばファイルシステムおよび／または記憶システムは、オブジェクトとしてそのアプリケーションのすべての永続的データを記憶するためのローカルオブジェクト記憶装置を使用する。そのアプリケーションは、記憶された各オブジェクトの参照カウントを必要とすることがあり、その参照カウントはそれぞれのオブジェクトの参照の数を備える。本発明の一態様によれば、オブジェクトのグローバル参照カウントは、それぞれのノードでのオブジェクト名の参照のローカル参照カウントＬＲＣ（オブジェクトインスタンスとは対照的な）を各ノードで維持することによって、追跡することができ、ＬＲＣの値はそのローカルノード上の参照カウント調整の合計を備え、ＬＲＣはローカルオブジェクト記憶装置で記憶されたそのオブジェクトの任意のインスタンスから独立している。インスタンスカウントから参照カウントを分離することによって、本方法は、先行技術の方法に反して、ＬＲＣの負の値（符号付きの整数）を可能にする。さらに、本明細書でグローバル参照カウントＧＲＣと称される、複数のノードからのＬＲＣの合計を計算することによって、結果として生じるＧＲＣは、オブジェクトとして永続的データを記憶するためにそのネットワークノードを使用する特定のアプリケーションについて、オブジェクトがそのアプリケーションによってもう参照されないという理由で、そのオブジェクト（そのすべてのインスタンス）の割当てを解除することが安全であるかどうかを判定するために使用することができる。ＧＲＣがゼロであると判定された場合におよびその場合にのみ、特定のオブジェクトのオブジェクトインスタンスの割当てを解除することは安全である。
【０００９】
[009]本発明のもう１つの態様によれば、それらのノードのうちの１つまたは複数でのオブジェクトインスタンスの配置は、そのオブジェクトの名とは独立して実行される。オブジェクト名に基づくオブジェクト記憶場所を強制する先行技術の方法に反して、本発明の様々な実施形態では、ノード上のオブジェクトインスタンスの配置は、たとえば、ネットワークもしくはシステム性能またはデータ信頼性に基づき、オブジェクトの実際のまたは意図された使用によって判定され得る。たとえば、ローカルオブジェクト記憶装置は、どのファイルシステム（複数可）が特定のオブジェクトを参照するかを知り、そのオブジェクトを使用するファイルシステム（複数可）に応じてそれらのノードのうちの１つまたは複数でのそのオブジェクトの好ましい配置を判定することができる。本システムは、そのオブジェクトが何か、たとえばそのオブジェクトの名、に応じてノードでのデータオブジェクトの配置を制約する先行技術のシステムよりも大幅に頑強で効率的である。
【００１０】
[010]本発明のもう１つの態様によれば、各ローカルノードは、そのオブジェクトが記憶されたローカルノード上の物理的な場所にオブジェクト名をマップするためのそれ自体のローカル索引を維持する。このマッピング索引は、たとえば、そのオブジェクトインスタンスが記憶されたローカルノード上の１つまたは複数の場所へのポインタを備えることができる。ローカルマッピング索引のエントリは、所与のオブジェクト名について、ＬＲＣ、および、そのローカルノード上の１つまたは複数の記憶場所へのポインタを含み得る。
【００１１】
[011]本発明の一実施形態によれば、
記憶されたオブジェクトの共用のための複数のネットワークノードにおいて、そのオブジェクトがそのネットワークノードにわたってグローバルに固有の名を有し、そのオブジェクト名は、そのオブジェクトがそのノードでどこに記憶されるかに基づいて変化しないこと、
そのローカルノードで記憶された任意のオブジェクトインスタンスから独立して、オブジェクト名の参照のローカル参照カウントＬＲＣを各ノードで維持するステップであって、そのＬＲＣが符号付きの整数として維持される、ステップ、
オブジェクト名を参照解除（ｄｅ−ｒｅｆｅｒｅｎｃｉｎｇ）することにより、負のＬＲＣ値を生成することができることを含む方法を実行するための実行可能プログラム命令を含む、コンピュータ可読記録媒体が提供される。
【００１２】
[012]一実施形態において、本方法は、
ＬＲＣの合計を備えるグローバル参照カウントＧＲＣを判定するステップを含む。
【００１３】
[013]一実施形態で、その判定するステップは、
そのＧＲＣがゼロであると判定されたときに、割当て解除のためのオブジェクトインスタンスを識別するステップを含む。
【００１４】
[014]一実施形態で、その判定するステップは、
オブジェクトが割当てを解除され得るかを判定するためにノード間の最終的一貫性ネットワークプロトコルを実施するステップを含む。
【００１５】
[015]一実施形態で、その判定するステップは、
それらのネットワークノードのうちの１つのノードにある範囲のオブジェクト識別子の所有権を割り当てるステップであって、その１つのノードがその範囲のすべてまたは１サブセットについてその判定するステップを開始する、ステップを含む。
【００１６】
[016]一実施形態で、本方法のステップは、
各ノードでローカルオブジェクト記憶装置を維持するステップであって、そのローカルオブジェクト記憶装置が、グローバルに固有のオブジェクト名の名前空間を集合的に備える、ステップを含む。
【００１７】
[017]一実施形態において、本方法は、
そのローカルオブジェクト記憶装置が、オブジェクト名のローカルマッピング索引、ＬＲＣ、および、そのオブジェクトがそのローカルノードで記憶された任意の物理オブジェクト場所へのポインタを維持することを含む。
【００１８】
[018]一実施形態において、本方法は、
各オブジェクトが、そのオブジェクト名としてそのオブジェクトの内容から導出されたオブジェクトフィンガープリントを有することを含む。
【００１９】
[019]一実施形態において、本方法は、
そのフィンガープリントが、そのオブジェクト内容のハッシュを備えることを含む。
【００２０】
[020]一実施形態において、本方法は、
ファイルシステムのすべての永続的データを記憶するための方法として集合的にピアトゥピアネットワーク記憶システム内のそれらのノードのうちの１つまたは複数でそれらのオブジェクト記憶装置を使用する、ファイルシステムを含む。
【００２１】
[021]一実施形態において、本方法は、
−  すべてのファイルシステムデータ、メタデータおよびファイルが、そのオブジェクト記憶装置（複数可）のオブジェクトを備え、各オブジェクトがそのオブジェクト名としてオブジェクトフィンガープリントを有することと、
−  ファイルシステムオブジェクトの集合体がまた、そのオブジェクト記憶装置（複数可）のオブジェクトを備え、各集合体が複数のそのファイルシステムオブジェクトのマッピングを備え、その集合体の内容から導出されたそれ自体のオブジェクトフィンガープリントを有し、その中でその集合体の１つまたは複数のオブジェクトへの変更がその集合体オブジェクトフィンガープリントを変更することと、
−  その名前空間ファイルシステム内のあらゆるオブジェクトがそのルートオブジェクトを介してアクセス可能であるような、ルートオブジェクトフィンガープリントを有する、ファイルシステムルートオブジェクトとを含む。
【００２２】
[022]一実施形態において、本方法は、
そのオブジェクト名とは独立してオブジェクトの１つまたは複数のインスタンスを記憶するための場所（複数可）としてそれらのノードのうちの１つまたは複数を、ネットワークまたはシステム性能または信頼性に基づき、選択するステップを含む。
【００２３】
[023]一実施形態において、本方法は、
その記憶されたオブジェクトの共用が、オブジェクト名、ＬＲＣおよび記憶されたオブジェクトの場所に関してノード間で通信するステップを備えることを含む。
【００２４】
[024]一実施形態において、本方法は、
アプリケーションがオブジェクト名を参照解除（ｄｅ−ｒｅｆｅｒｅｎｃｅｓ）し、そのオブジェクトのインスタンスがローカルオブジェクト記憶装置で記憶されていないときに、そのローカルオブジェクト記憶装置がマイナス１のＬＲＣを生成することを含む。
【００２５】
[025]一実施形態において、本方法は、
その記憶システムのすべての永続的データを記憶するための方法として集合的にピアトゥピアネットワーク記憶システム内のノードのうちの１つまたは複数でオブジェクト記憶装置を使用する、記憶システムを含む。
【００２６】
[026]本発明のもう１つの実施形態によれば、
オブジェクトがネットワークノードにわたってグローバルに固有の名を有し、各ノードがローカルノード上のオブジェクトを命名および記憶するためのローカルオブジェクト記憶装置を有し、そのローカルオブジェクト記憶装置がそれらのオブジェクトを共用する、複数のネットワークノードで動作する分散ピアトゥピア記憶システム内のデータオブジェクトの参照を追跡する方法
を実行するための実行可能命令を含む、コンピュータ可読記録媒体が提供され、
その方法は、
複数のローカルノードの各々で、そのローカルノードでデータオブジェクトのインスタンスを記憶するための１つまたは複数の場所を判定するステップと、
複数のローカルノードの各々で、そのオブジェクト名にそのローカルノード上のその記憶されたインスタンスの１つまたは複数の場所をマップするステップであって、その場所がそのオブジェクト名を変更しない、ステップと、
複数のローカルノードの各々で、オブジェクト名の参照のローカル参照カウントＬＲＣを維持するステップであって、そのＬＲＣの値がそのローカルノード上のそのオブジェクトの参照カウント調整の合計を備え、そのＬＲＣが、その参照されるオブジェクトの任意のインスタンスがそのローカルノードで記憶されたかどうかとは独立している、ステップと
を含む。
【００２７】
[027]本発明のもう１つの実施形態によれば、
複数のネットワークノードについて、各ノードがそれぞれのノードでオブジェクトを記憶するためのローカルオブジェクト記憶装置を有し、そのオブジェクトがそれらのネットワークノードにわたってグローバルに固有の名を有することと、
そのローカルオブジェクト記憶装置が、それらのオブジェクトのうちの１つまたは複数を共用することと、
アプリケーションが、オブジェクトとして永続的データを記憶するためにそのローカルオブジェクト記憶装置を使用し、そのアプリケーションが、それぞれのオブジェクトの参照の数を備えるそれらのネットワークノードで記憶された各オブジェクトの参照カウントを要求することと、
各ノードでそれらのオブジェクト名の参照のローカル参照カウントＬＲＣを維持するステップであって、そのＬＲＣの値がそのローカルノード上の参照カウント調整の合計を備え、そのＬＲＣが、そのＬＲＣの負の値を可能にするために、そのローカルオブジェクト記憶装置で記憶された参照されるオブジェクトの任意のインスタンスから独立している、ステップと、
それらのＬＲＣの合計を備えるグローバル参照カウントＧＲＣを判定するステップとを含む方法を実行するための実行可能プログラム命令を含む、コンピュータ可読記録媒体が提供される。
【００２８】
[028]一実施形態では、
そのアプリケーションは、ファイルシステムまたは記憶システムを備える。
【００２９】
[029]本発明のもう１つの実施形態によれば、
各ノードがそれぞれのノードでオブジェクトを記憶するためのローカルオブジェクト記憶装置を有し、それらのオブジェクトがそのネットワークノードにわたってグローバルに固有の名を有する、複数のネットワークノードと、
それらのオブジェクトのうちの１つまたは複数を共用する、ローカルオブジェクト記憶装置と、
オブジェクトとして永続的データを記憶するためにそれらのローカルオブジェクト記憶装置を使用するアプリケーションであって、それぞれのオブジェクトへの参照の数を備える、そのネットワークノードで記憶された各オブジェクトの参照カウントを必要とする、アプリケーションと、
各ノードでオブジェクト名の参照のローカル参照カウントＬＲＣを維持するための手段であって、そのＬＲＣの値がそのローカルノードでの参照カウント調整の合計を備え、そのＬＲＣが、そのＬＲＣの負の値を可能にするために、そのローカルオブジェクト記憶装置で記憶された参照されるオブジェクトの任意のインスタンスから独立している、手段と、
ＬＲＣの合計を備えるグローバル参照カウントＧＲＣを判定するための手段とを備える、装置が提供される。
【００３０】
[030]本発明のもう１つの実施形態によれば、
各ノードがそれぞれのノードでオブジェクトを記憶するためのローカルオブジェクト記憶装置を有し、それらのオブジェクトがそのネットワークノードにわたってグローバルに固有の名を有する、複数のネットワークノードと、
それらのオブジェクトのうちの１つまたは複数を共用する、ローカルオブジェクト記憶装置と、
オブジェクトとして永続的データを記憶するためにそのローカルオブジェクト記憶装置を使用するアプリケーションであって、それぞれのオブジェクトの参照の数を備えるそのネットワークノードで記憶された各オブジェクトの参照カウントを必要とする、アプリケーションと、
各ノードでオブジェクト名の参照のローカル参照カウントＬＲＣを維持するための手段であって、そのＬＲＣの値がそのローカルノードでの参照カウント調整の合計を備え、そのＬＲＣが、そのＬＲＣの負の値を可能にするために、そのローカルオブジェクト記憶装置で記憶された参照されるオブジェクトの任意のインスタンスから独立している、手段と、
ネットワークまたはシステム性能または信頼性に基づき、そのオブジェクト名から独立したオブジェクトインスタンスを記憶するための場所として、それらのローカルオブジェクト記憶装置のうちの１つまたは複数を選択するための手段とを備える、装置が提供される。
【００３１】
[031]本発明のこれらのおよび他の態様が、様々な詳細な実施形態に関して以下により具体的に説明される。
【００３２】
[032]添付の図面は、以下のように、本発明の１つまたは複数の実施形態を説明する。
【図面の簡単な説明】
【００３３】
【図１】本発明の一実施形態を実施するための複数のネットワークノードの概略図である。
【図２】オブジェクトブローカを介してネットワークと通信するネットワークの１つのノード上のローカルオブジェクト記憶装置の概略図である。
【図３】２つのネットワークノードアリスとボブの間のオブジェクトの共用の概略図である。
【図４】ノードボブにあるローカルマッピング索引の概略図である。
【図５】ネットワークのノードアリスとボブの間のグローバル参照カウント調整の概略図である。
【図６】アプリケーションのビューからのオブジェクトの複数の独立した参照を示す、ファイルシステム論理ビューの概略図である。
【図７】負の参照カウントが本発明に従って許される、ネットワークの３つのノード上のオブジェクト参照の追跡の一例である。
【図８】ローカル参照カウントを維持するためのネットワーク上の２つのノードアリスとボブの間の通信の流れ図である。
【図９】それらのネットワークノードにわたって参照カウントおよびインスタンスカウントの両方の調整を実施するための３つのノードアリス、ボブおよびイブの間のネットワーク通信の概略図である。
【発明を実施するための形態】
【００３４】
[033]本発明の一実施形態で、データ記憶システムは、ネットワーク上の複数のノードにわたって分散され、各ノードはそれ自体のローカルオブジェクト記憶装置を有し、そのローカルオブジェクト記憶装置はオブジェクトを共用する。ネットワークノードのこのグループは汎用命名規則に従い、そのネットワークで記憶された各オブジェクトは、そのネットワークにわたってグローバルに固有の名を有する。この実施形態で、それらの複数のノードはピアトゥピアネットワークとして動作し、どのノードも１次ではない。集中命名機関は存在せず、その代わりに、各々のローカルノード上のローカルエージェントが、ノード間の通信を必要とせずに、共通ハッシュアルゴリズムを使用してオブジェクトの名を判定することによって、そのオブジェクト名を独立して判定しそれに合意することができる。強いハッシュアルゴリズムを使用することによって、衝突は回避される。
【００３５】
[034]この実施形態で、それらの複数のローカルオブジェクト記憶装置は、数十億のオブジェクトを管理するものであり、各オブジェクトは小さく、たとえば、長さ４、８、１６、３２、６４、１２８または２５６ＫＢ（キロバイト）である。そのオブジェクト記憶装置内のオブジェクトは不透明であり、任意の複数のビットを備える。そのオブジェクト記憶装置は、それらのビットの意味的知識を有さず、そうではなくて、ファイルシステム、または別法としてブロック記憶システムなど上位層アプリケーションが、意味的内容（意味）、および、オブジェクト間の関係もしくは参照を定義する。各ローカルオブジェクト記憶装置は、オブジェクトインスタンスがローカルに記憶され得る物理的な場所へのオブジェクト名のマッピングのためのローカル索引（たとえば、物理的な場所へのポインタ）を含む。各ローカルオブジェクト記憶装置はまた、オブジェクト名のローカル参照カウントＬＲＣを維持する。しかし、先行技術とは対照的に、オブジェクト名のローカル参照カウントはオブジェクトインスタンスから分離される（独立している）。そのＬＲＣは、符号付きの整数として維持され、オブジェクトインスタンスのカウントとは対照的にオブジェクト名の参照の累計で構成される。また、そのＬＲＣを際立たせるのは、符号付きの整数としてのその維持であり、それによって負の値を許容することである。各々の新たな参照および参照解除に応じてＬＲＣの調整、すなわち、参照を追加するには＋１、そして、参照を削除するには−１、が行われる。
【００３６】
[035]一例では、ファイルシステムアプリケーションは、オブジェクトがそのファイルシステム内で参照された回数を備えるグローバル参照カウントを維持する。ここで、永続的データのファイルシステム記憶が複数のノード上の１つまたは複数のローカルオブジェクト記憶装置で集合的に実施される場合、ファイルシステムビューからのグローバル参照カウントは、それぞれのオブジェクトへのそれらの複数のネットワークノードにわたる参照の数を備える。一実施形態で、そのファイルシステムは、そのファイルシステムおよび記憶システムの両方を含み、そして、ＮＡＳなどファイル移送プロトコルを使用する、ファイラとして知られる物理デバイスとして、実施することができる。もう１つの実施形態で、ファイルシステムに加えてまたはその代わりに、ブロック記憶サーバは、永続的データオブジェクトを記憶するために、１つまたは複数のノードで集合的にそれらのローカルオブジェクト記憶装置を使用する。そのブロックサーバは、複数の物理記憶ディスクで記憶された仮想ディスクとして現われる物理デバイスであり、ｉＳＣＳＩまたはＦＣｏＥなどブロック移送プロトコルを使用する。
【００３７】
[036]オブジェクトインスタンスからローカル参照カウントを分離することによって、そのシステムは、オブジェクト特性に関係なくそれらのローカルノードのうちの任意の１つまたは複数でのオブジェクト（インスタンス）の配置を許す。代わりに、そのローカルノードは、各々、そのローカルノードでの参照カウント調整の履歴（合計）を備えるオブジェクト名の参照のローカルカウントを維持する。これらのローカル参照カウントはもはや、本願によるオブジェクトインスタンスの数には関係せず（たとえば、ファイルシステムまたはブロックサーバ）、したがって、そのローカル参照カウントの値は、負の値（それらがオブジェクトインスタンスの数に関係している場合には可能ではないことになる）でもよい。参照カウントをインスタンスの数と分離することによって、そのオブジェクトは、グローバル参照カウントまたはローカル参照カウントから独立して、ネットワークまたはシステムの性能または信頼性の向上の理由あるいは任意の他の理由でネットワーク上のどこにでも置くことができる。これは、そのオブジェクト名に基づいて配置を限定する、分散ハッシュテーブルおよび他の同様のアルゴリズムなど、オブジェクトの配置のための先行技術のアルゴリズムとは対照的である。その一方、本発明によれば、それらのノードにわたるオブジェクトの要望どおりの多数のインスタンス、あるいは、任意の目的、たとえば、ネットワークトラフィックを減らすため、処理時間を減らすため、またはデータ複製もしくは回復の目的で、要望どおりの少数のインスタンスを作ることができる。
【００３８】
[037]本発明のもう１つの態様によれば、参照カウントからインスタンスの数を分離することによって問題が生じる、すなわち、オブジェクトが安全に削除可能かどうかの判定するためにローカル参照カウントに頼ることがもはや可能ではなくなる。本発明の一実施形態によれば、この問題は、それらのネットワークノードにわたるすべてのローカル参照カウントの合計を備えるグローバル参照カウント（ＧＲＣ）を計算することによって、解決する。このＧＲＣは、それらのネットワークノードのすべてにわたるオブジェクトへのすべての参照の合計と厳密に等しいことになる。そのＧＲＣがゼロである場合におよびその場合にのみ、オブジェクトは、割当てを解除され得る（たとえば、削除される）。しかし、ローカル参照カウント調整はそのネットワークの他のノードと調整されるので、そのＧＲＣを知ることは困難であり、理想的には、そのシステムは活発に修正される（たとえば、オブジェクトがそれらのローカルノードで読取りおよび書込みされる）間に、ＧＲＣを計算することが望まれることになる。
【００３９】
[038]本発明の一実施形態によれば、ＧＲＣは、ネットワーク内の異なるノードに対して、グローバル名前空間内のオブジェクト識別子（以下、オブジェクト名）の所有権を割り当てることによって、判定される。そのネットワーク内のすべてのノードがその名前空間の一部を所有する必要はない。しかし、その名前空間全体が、それらのノードのすべてまたはサブセットによってカバーされる必要がある。ある範囲の識別子を所有するノードは、その範囲内の１つまたは複数のオブジェクトのＧＲＣ（複数可）の計算、およびオブジェクトのその結果として生じる割当て解除（たとえば、ごみ集め）を開始する。一実施形態によれば、最終的一貫性に基づくネットワークプロトコルが使用され、そこでは、システムがまだ活発に修正されている（たとえば、オブジェクトが読取りまたは書込みされ、オブジェクト参照カウントが修正される）間に、ＧＲＣが計算される。以下にさらに詳しく説明するように、所有者ノードは、それについてＧＲＣが判定されることになる１つまたは複数のオブジェクト識別子のタグを提供し、ローカルノードは、このタグを使用してそれぞれのオブジェクトにラベルを付け（そのノード上の活動が継続することを可能にし）、そして、それらのノードは、タグ付けされたメッセージを交換し、すべてのノードがその所有者ノードにそれぞれのオブジェクトについてのそれらのローカル参照カウントを提供し、その所有者ノードがそのローカル参照カウントの合計としてＧＲＣを計算することを可能にする。
【００４０】
[039]同様の方式で、所有者ノードは、インスタンス調整を開始および実行することができ、そこで、その所有者ノードは、各それぞれのノードでオブジェクトのインスタンスの数に関してそれらのローカルノードのすべてからメッセージを受信する。その所有者ノードは、次いで、ＳＬＡ（サービス内容合意書）および他のメトリクスに従ってそれらのネットワークノードにわたるインスタンスの所望の数および場所を計算し、次いで、オブジェクトインスタンスの所望の追加または削除を実行するようにその他のノードに指示することができる。
【００４１】
[040]本発明のこれらのおよび他の態様が、添付の図面に示された実施形態に関して以下にさらに詳細に説明される。これらの実施形態は、例として提供され、様々な修正形態が当業者には容易に明らかとなろう。したがって、本発明は、開示される実施形態によって限定されるものではない。いくらかの入門資料が背景として含まれ、実施形態のコンテキストを提供する。
【００４２】
[041]図１は、コンピュータネットワーク、ここではピアトゥピアネットワーク１０内の複数のネットワークノード１２、１４、１６の概略図である。各ノードはサーバ１１ａ、１１ｂ、１１ｃを含み、それらのサーバはネットワーク（クラウド１７として示す）によってともに結合され、ＴＣＰ／ＩＰなど標準通信プロトコルを使用して互いに通信する。サーバ１１は、インテルに基づくサーバ（たとえば、ＩＢＭ３６５０サーバ）を含むがこれに限定されない任意のタイプのサーバでもよい。
【００４３】
[042]各ノード１２、１４、１６は、ローカル１５ユーザのビュー１８でローカルノードと称され、サーバ１１およびデータ記憶装置１３の両方（ここでは複数の記憶ディスクとして示す）を含む。これらのローカル構成要素は、ともに結合され、システムバス２０を介して通信する。各サーバは、プロセッサ、メモリ、およびネットワークインターフェースを含むことができ、ディスプレイ、キーボードおよび／またはマウスなどユーザインターフェースデバイスをさらに含み得る。そのネットワークインターフェースは、各サーバをノードのネットワークに結合させる。
【００４４】
[043]グローバルに、それらの複数のネットワークノードは、グローバルネットワーク１０と称される。このグローバルネットワークを見るユーザ１９は、ネットワークのグローバルビューを有する。本発明の様々な実施形態に従って以下に説明するように、ソフトウェアおよび／またはハードウェアが、本発明の様々なシステムおよび方法の実施形態を実行するために各々のネットワークノードで提供される。
【００４５】
[044]図２は、本発明で使用するためのオブジェクトに基づくファイルシステムの一実施形態を示す。これによりその内容全体を参照によって本願明細書に引用したものとする、２０１０年６月２５日出願のＦｉｌｅ  ｓｙｓｔｅｍ（ファイルシステム）という名称の同時係属および共同所有の米国特許出願第１２／８２３，９２２号でさらに具体的に説明されるように、コンピュータプログラムおよび／または電子回路製品が、１つまたは複数のコンピュータ記憶装置でファイルを名前付けおよび記憶するために提供される。その製品は、オブジェクト記憶装置７２を使用する名前空間ファイルシステム７０を実施するための実行可能命令または論理回路を備える。一例では、その名前空間ファイルシステムは、仮想ファイルシステム層とブロック記憶抽象化層の間の記憶スタック内の層である。すべてのファイルシステムデータは、データ、メタデータ、およびファイルを含むオブジェクトを備える。各オブジェクトは、そのオブジェクト名としてオブジェクトフィンガープリントを有し、そのフィンガープリントはそのオブジェクト内容のハッシュである。ファイルシステムオブジェクトの集合体はまた、そのオブジェクト記憶装置のオブジェクトを備え、各集合体は、複数のファイルシステムオブジェクトのマッピングを備え、その集合体の内容から導出されたそれ自体のオブジェクトフィンガープリントを有し、その集合体の１つまたは複数のオブジェクトへの変更がその集合体オブジェクトフィンガープリントを変更する。ファイルシステムルートオブジェクトは、その名前空間ファイルシステム内のあらゆるオブジェクトがそのルートオブジェクトを介してアクセス可能であるような、そのファイルシステム内のすべてのオブジェクトから導出されたオブジェクトフィンガープリントを有する。そのルートオブジェクト内の追跡変更は、ファイルシステム活動の履歴、すなわち、ファイルシステムスナップ、を提供する。ファイルシステムｉノード数のマッピングおよびファイルシステムオブジェクトフィンガープリントを備える、ｉノードマップオブジェクトが提供され、そのファイルシステムをＰＯＳＩＸに準拠させる。
【００４６】
[045]図２に示すように、米国特許出願第１２／８２３，９２２号のオブジェクト記憶装置は、本発明に従って修正されて、複数のネットワークノードで機能する。図２は、そのファイルシステムのすべての永続的データオブジェクトを記憶するためのオブジェクト記憶装置７２を使用するグローバル名前空間ファイルシステム７０を示す。以下にさらに説明するように、名前空間ファイルシステム７０は、ここで、図１に示すように、複数のネットワークノード１２、１４、１６にある複数のピアトゥピアローカルオブジェクト記憶装置を使用する。この目的のために、各ローカルノード７２ａは、ここで、ローカルマッピング索引７３と、物理記憶装置（ディスク）７４と、ローカルノード１２、１４、１６の間で共用されるオブジェクトの割当ておよび追跡に関する通信を送信／受信するためにネットワーク１７とインターフェースをとるオブジェクトブローカ７６とを含む。
【００４７】
[046]図３は、本発明の一実施形態による分散オブジェクト記憶装置の動作を概略的に示し、名前空間ファイルシステムは、ネットワークの様々なローカルノードに存在する複数のローカルオブジェクト記憶装置を共用する。図示された実施形態で、第１のローカルノード８０はアリスと称され、第２のローカルノード８２はボブと称される。ファイルシステムＦＳ０８１は、ノードアリスと、参照オブジェクトＰ、ＱおよびＲとに存在する。ＦＳ０のコピーが、ノードボブにＦＳ０ルート署名を単に送信することによって、ノードボブで発行され得る（ステップ１）。そのルート署名は、そのファイルシステム内のすべてのオブジェクトに同じく由来するオブジェクトを参照するので、その名前空間ファイルシステム内のあらゆるオブジェクトがそのルートオブジェクトを介してアクセス可能である。したがって、その参照されるオブジェクト（Ｐ、Ｑ、Ｒ）自体をノードボブに転送する必要はない。ボブでのファイルシステムＦＳ０のこの発行は、破線の三角８３として示されて、そのファイルシステムルートオブジェクトはノードボブに非破線の円８４として記入され、そのルートオブジェクトが現在ノードボブに存在していることを示す。
【００４８】
[047]ノードボブのＦＳｏが続いてオブジェクトＰを必要とする場合（ステップ２）、それは、ノードボブのそのローカル索引８５を検査し、Ｐがノードボブに存在しないことを発見することになる。したがって、ノードボブオブジェクトブローカ８６は、要求メッセージ９０をそのネットワークのその他のノードに送信し、それらがオブジェクトＰを有するかを尋ねることになる。この例では、ノードアリスがその要求を受信し、そのローカル索引８８を検査し、それは、オブジェクトＰがアリスのローカルオブジェクト記憶装置８９に存在することを示す。ノードアリスは、Ｐのインスタンスでノードボブに応答メッセージ９１を送信する。オブジェクトＰは、ここで、ノードボブのそのローカルオブジェクト記憶装置で記憶され得る。
【００４９】
[048]図４は、分散オブジェクト記憶装置でのオブジェクト共用、さらに具体的には、ローカルノードで維持されるローカル参照カウントＬＲＣがいかにして負の値を有することを許されるかのさらなる例を示す。ここでは再び、オブジェクトＰ、ＱおよびＲを有するファイルシステムＦＳ０８１が、ノードアリス８０に存在する（ステップ１）。そのコピーが、ノードアリスからノードボブにファイルシステムルートオブジェクトを送信することによって、ノードボブ８２に転送される（ステップ２）。ノードボブのローカルユーザ９２は、次いで、そのファイルがファイルシステムＦＳ０の部分であり、そのファイルがＰを偶然含む、ファイルを削除するための命令を提供する（ステップ３）。Ｐを参照解除することによってこの命令を実施しようと試みて（ステップ４）、ノードボブは、オブジェクトＰの参照についてそのローカルオブジェクト記憶装置を検査する。しかし、ノードボブのローカルマッピング索引８５は、オブジェクトＰについてゼロの参照カウントを示す。オブジェクトＰの削除命令を実施するために、そのローカル索引エントリでＰの参照カウントは、ゼロ（０）からマイナス１（−１）に、１減らされる。ローカル参照カウントＬＲＣについて負の値を維持するこの能力は、過度のネットワークトラフィックを生成することになる、ネットワークにわたるオブジェクトインスタンスの即時の探索または調整を必要とせずに、グローバルビューで（すなわち、ノードのそのネットワークにわたる）参照値を保存する。そのノードにわたる参照カウント調整、すなわち参照カウントのグローバル計算ＧＲＣは、必要があれば、後から実行されて、そのネットワークにわたってオブジェクトＰのすべてのインスタンスの割当てを解除すること（たとえば、ごみ集めのために）が適切かを判定することができる。
【００５０】
[049]図５は、グローバル参照カウント判定の一例をさらに示す。本グローバル参照カウント、ＧＲＣは、所与のアプリケーションによって参照されるオブジェクトへのそのネットワークノード全体でのすべての参照の合計である。ＧＲＣは、その様々なローカルノードで記憶されたすべてのローカル参照カウント、ＬＲＣ、を合計することによって、判定される。ここでは、ＧＲＣを計算するために、時間の所与のインスタンスで、それらのすべてのＬＲＣを知ることが可能であると仮定する。この仮定の下で、図５は、プラス１（＋１）のローカル参照カウントを有するオブジェクトＰ、プラス１（＋１）のローカル参照カウントを有するオブジェクトＱ、および、プラス３（＋３）のローカル参照カウントを有するオブジェクトＺのエントリを含む、ノードアリス８０のローカルオブジェクト記憶装置索引を示す。ノードボブ８２は、プラス１（＋１）のローカル参照カウントを有するオブジェクトＸ、プラス１（＋１）のローカル参照カウントを有するオブジェクトＹ、および、プラス１（＋１）のローカル参照カウントを有するオブジェクトＺのエントリを有するローカルオブジェクト記憶装置索引を有する。このとき、オブジェクトＺのＧＲＣは、プラス３（＋３）であるノードアリス上の、およびプラス１（＋１）であるノードボブ上の、Ｚのローカル参照カウントの合計であり、オブジェクトＺのＧＲＣはプラス４（＋４）である。これは、オブジェクトＺへのそのネットワークノード内の参照がまだ存在し、Ｚは割当てを解除されるべきではないことを示す。オブジェクトＺのＧＲＣがゼロである場合にのみ、オブジェクトＺの割当てを解除することは安全である。
【００５１】
[050]図６は、ファイルシステム内のオブジェクトへの独立した参照の概念、および、オブジェクト記憶装置１０２がそのオブジェクトの場所（そのオブジェクトが記憶された）の物理ビューを維持する間に、オブジェクト記憶装置１０２を使用するファイルシステム１００がどのようにそのオブジェクトのファイルシステム論理ビュー（すなわち、そのオブジェクトの内容の知識）を維持するかを示す。図６では、２つの独立した参照が、ツリー構造で示され、そのツリーの最上部またはルートで、スラッシュ（／）は特定のファイルシステムを指示する。そのツリーの最上部のノードの下に、ファイルＦＯＯおよびファイルＢＡＲの各々への２つの分岐がある。ファイルＦＯＯの下には、オブジェクトＡおよびＢへの分岐がある。オブジェクトＢＡＲの下には、オブジェクトＢおよびＱへの分岐がある。この例では、オブジェクトＢへの２つの独立した参照が存在し、一方はファイルＦＯＯを介し、もう一方はファイルＢＡＲを介する。したがって、そのオブジェクト記憶装置は、オブジェクトＢの２の参照カウント（Ｂ２）を含む。残りのオブジェクトＡ、Ｑ、ＦＯＯ、ＢＡＲおよび／は、各々、１の参照カウントを有する。
【００５２】
[051]図７は、どのようにして本発明によるオブジェクト参照およびオブジェクトインスタンスの分離が、ノードのネットワークにわたるグローバル参照カウントの判定を可能にしたままで、可能にされ得るかをさらに示す。本発明で、ローカル参照カウント単独では、インスタンスが削除可能かどうかを判定しない。むしろ、前述のように、インスタンスが削除可能かどうかを判定するのは、オブジェクトのすべてのインスタンスの割当てを、（そのオブジェクトへのファイルシステム内の参照がもはや存在しないために）解除することが安全であるかどうかを判定する、すべてのローカル参照カウントを合計することによって取得されるグローバルビューのみである。たとえば、図７は、ネットワークノードアリス８０、ボブ８２およびイブ９４を示す。ファイルＦＯＯは、ノードアリスのローカルオブジェクト記憶装置１０３内に記憶されたオブジェクトＰを含み、ノードアリスの索引はオブジェクトＰのプラス１（＋１）のローカル参照カウントを有する。ノードボブ８２は、そのローカルオブジェクト記憶装置１０４内に記憶されたオブジェクトＰのコピーを有さず、そして、オブジェクトＰのローカル参照カウントはマイナス１（−１）である。ノードイブ９４は、そのローカルオブジェクト記憶装置１０５内にオブジェクトＰのインスタンスを有さず、オブジェクトＰのローカル参照カウントはプラス１（＋１）である。したがって、ノードボブおよびノードイブで、オブジェクトＰの参照カウントは、それぞれノードボブまたはノードイブに記憶されたインスタンスが存在するかどうかとは関係がない。しかし、オブジェクトＰの３つのローカル参照カウントの合計を備える、オブジェクトＰのグローバル参照カウントＧＲＣが計算されるとき、その計算される合計はプラス１（＋１）であり、オブジェクトＰの参照がまだ存在し、Ｐは割当てを解除されるべきではないことを指示する。
【００５３】
[052]図８は、複数のノードにわたるローカル参照カウントの維持の一例を説明する流れ図である。前述のように、すべての保留中の参照カウントがファイルシステムＡを通して完全に伝播されたと仮定し、任意のオブジェクトＯについて、ファイルシステムＰのＯのグローバル参照カウントは、それらのネットワークノードにわたるオブジェクトＯへのすべての参照の合計に完全に一致する。図８で、ローカルノードアリスおよびローカルノードボブは、各々、それら自体のローカルオブジェクト記憶装置およびオブジェクトブローカを有する。ノードアリスのファイルシステムＰは、オブジェクトＡおよびＢを含む。ファイルシステムＰは、ノードアリスのオブジェクトＡへの２つの参照を有し、ノードアリスのオブジェクトＡのローカル参照カウントはプラス２（Ａ２）である。オブジェクトＢのローカル参照カウントは、ノードアリスでプラス１（Ｂ１）である。ノードボブのファイルシステムＱは、参照されるオブジェクトＡを１度有し、したがって、ノードＢのオブジェクトＡのローカル参照カウントはプラス１（Ａ１）である。
【００５４】
[053]ノードボブのオブジェクトブローカは、ここで、オブジェクトＡをノードアリスに複製することを望む。ノードアリスのブローカは、ノードボブによって送信された要求を受信し、ノードアリスのオブジェクトＡのローカル参照カウントをプラス３（Ａ３）に増やす。
【００５５】
[054]その後、ノードアリスのファイルシステムＰは、ファイルシステムＰのコピーをノードボブに移動させることを望む。ノードボブのファイルシステムＰがオブジェクトＢを読み取るとき、それは、ノードボブのローカルオブジェクト記憶装置内でオブジェクトＢを見つけることができない。ノードボブのそのオブジェクトブローカは、次いで、ノードアリスにオブジェクトＢの読取り要求を送信する。ノードアリスのオブジェクトブローカは、ノードアリスのローカルオブジェクト記憶装置からＢを読み取り、オブジェクトＢをノードボブに送信し、オブジェクトＢは、次いで、ノードボブのファイルシステムに提供される。
【００５６】
[055]その後、ノードボブのファイルシステムＱは、Ａへのその第１の参照を参照解除し、オブジェクトＡのローカル参照カウントをゼロ（Ａ０）に減らす。続いて、ノードボブのファイルシステムＱは、オブジェクトＡの第２の参照解除を発行し、ノードボブのオブジェクトＡのローカル参照カウントをマイナス１（Ａ−１）に減らす。先行技術では、負の参照カウントは許されず、ノードボブは他方のノードと通信して、オブジェクトＡの負の参照カウントを受け付けるために別のノードを見つける必要があることになる。しかし、本発明によれば、即時の調整を行う必要はなく、このネットワークトラフィックは回避される。代わりに、以下にさらに説明するように、調整は、求められるまで延期することができる。
【００５７】
[056]本発明のもう１つの態様によれば、それらのローカルノードは、特定の範囲のオブジェクト識別子、または全鍵空間内の鍵（以下、オブジェクト名）、の所有権を与えられる。その所有者ノードは、参照カウント伝播を開始する責任を負う。その記憶システム内のあらゆるノードがその鍵空間の一部を所有する必要はない。しかし、鍵空間全体が、ノードの何らかのセットによってカバーされる必要がある。その鍵の所有者（ノード）は、対応するオブジェクトのグローバル参照カウントＧＲＣを計算する責任を負う。一実施形態で、本方法は、ローカル参照カウントおよびローカルインスタンスカウントの両方を集計するステップを含む。他の実施形態では、一方または他方の集計が、実行され得る。
【００５８】
[057]一例では、集計プロセスは、以下のステップを含み得る。
ａ．所有者ノード（タグ付け）
その所有者が、特定の時点にＧＲＣの計算を指示するための識別子である固有のタグを作成する。
【００５９】
その所有者が、そのＧＲＣが計算されることになる鍵の範囲ＲＫを決定する。
【００６０】
その所有者が、その記憶システム内のすべてのノードに（ＲＫ，Ｔ）を送信する。
ｂ．受信者ノード（複数可）（累算）
受信された各（ＲＫ，Ｔ）について、その受信者は、Ｔでローカルであるすべての鍵をタグ付けする必要がある。
【００６１】
タグＴの記入の後、ＲＫ内の鍵への任意のさらなる修正が、明確である必要がある、
ＲＫ内の各鍵について、受信者は、タグＴとともにその所有者ノードに、そのローカル参照カウント、および、インスタンスのローカル数を送り返す。
ｃ．所有者ノード（調整）
その所有者が、グローバル参照カウントを判定するために、それ自体のローカル参照カウントとともに、その他のノードから受信されるローカル参照カウントを合計する。そのグローバル参照カウントがゼロである場合、その所有者は、次いで、すべての他のノードにタグＴを有する削除メッセージを送信し、その所有者ノード上のその鍵の任意のローカルインスタンスを削除する、
その受信するノードおよびその所有者ノードは、そのオブジェクトへのＴの記入の後に活動が存在する場合、そのオブジェクトを実際に削除しなくてもよい、
その所有者はまた、そのネットワークの様々なノードのそのオブジェクトのインスタンスの数を見直し、様々なインスタンスが、性能を向上させるためなどに追加または削除され得るかどうかを判定する。
ｄ．受信者ノード（複数可）（アクション）
その受信者は、その削除命令を実行し、Ｔでその所有者に確認を送り返す、
その受信者は、そう命令された場合にインスタンス作成に関する命令を実行し、Ｔでその所有者に確認を送り返す。
【００６２】
[059]調整のこの方法は、「最終的整合性」を実現する。ノード間のメッセージが受信または処理される順番は、最終的に、それらがすべてその所有者ノードに戻る限り、重要ではない。そのタグは、そのノードが調整プロセスに従事している間に、その受信者ノードがセットＲＫで活動を継続することを可能にするバリアの機能を果たす。一実施形態で、そのタグは、ＧＵＩＤ（グローバルに固有のＩＤ）である。
【００６３】
[060]このタグ付けおよび集計プロセスの一例が、図９に示される。ここで、ノードアリスは、その鍵空間の一部を所有し、その範囲の２次部分で作動することを決定する。アリスは、固有のタグＴを生成し、そのタグＴとともに、所望の範囲ＫＲについてローカル参照カウントおよびローカルインスタンスカウントの両方の累算要求を送出する。
【００６４】
[061]ノードボブおよびイブは、最終的に、鍵範囲ＫＲ、タグＴ、についてアリスから要求を受信する。その要求は、任意の順番でノードボブおよびイブに到達することができる。各受信者ノードは、その鍵範囲にタグ付けする必要がある。たとえば、ノードボブ上の鍵範囲ＫＲ内のオブジェクトＸが修正されることになる場合、ボブはバリアを作成する必要があり、たとえば、ここで２つのオブジェクトＸ、すなわち、一方のオブジェクトＸｔａｇおよび他方のオブジェクトＸｏｔｈｅｒが存在する。各受信者ノードは、次いで、範囲Ｒ内のあらゆる鍵Ｋについて、そのローカル参照カウント（ｒｅｆｓ）、および、そのローカルノード上のインスタンス（物理インスタンスへのポインタ、ｌｏｎｓ）の数とともにノードアリスに応答する。
【００６５】
[062]所有者ノードアリスは、ここで、タグＴの下の範囲Ｒ内のあらゆる鍵Ｋのグローバル参照カウントおよびグローバルインスタンスカウントを計算するのに十分な情報を有する。アリスは、すべてのノードからの応答を累算する。オブジェクトのグローバル参照カウントＧＲＣがゼロである場合、アリスは、すべてのノードに命令を送信してそのオブジェクトの割当てを解除することができる。その受信者は、確認メッセージで応答する。アリスは、インスタンスがその他のノードのうちの１つまたは複数で作成または削除されるべきかどうかを判定するための様々な方法（たとえば、サービス内容合意書）を適用することができる。そのグローバル参照カウントがゼロである場合にのみ、すべてのインスタンスが削除され得る。
さらなる実施形態
[063]本発明は、両方とも２０１０年６月２５日に出願され、両方とも２００９年６月２６日出願された米国仮特許出願第６１／２６９，６３３号の優先権を主張する、Ａ．Ｊ．ＢｅａｖｅｒｓｏｎおよびＰ．Ｂｏｗｄｅｎによる同時係属のおよび共同所有のＦｉｌｅ  Ｓｙｓｔｅｍ（ファイルシステム）という名称の米国特許出願第１２／８２３，９２２号と、Ｐ．ＢｏｗｄｅｎおよびＡ．Ｊ．ＢｅａｖｅｒｓｏｎによるＳｃａｌａｂｌｅ  Ｉｎｄｅｘｉｎｇ（スケーラブル索引付け）という名称の米国特許出願第１２／８２３，４５２号で開示されるものなど、ファイルシステムおよび／またはファイルシステムの索引を実施するために使用することができる。これらの出願の各々に対して優先権が主張され、各々の完全な開示は、参照によってその全体を本明細書に組み込む。
【００６６】
[064]本発明の実施形態は、デジタル電子回路で、あるいは、コンピュータハードウェア、ファームウェア、ソフトウェア、またはそれらの組合せで、実施することができる。本発明の実施形態は、たとえば、データ処理装置、たとえば、プログラマブルプロセッサ、コンピュータ、もしくは複数のコンピュータ、による実行のために、またはその動作を制御するために、たとえば機械可読記憶装置で、コンピュータプログラム製品、すなわちコンピュータ可読記録媒体で有形に実施されたコンピュータプログラム、として実施することができる。コンピュータプログラムは、コンパイルされたまたは解釈された言語を含む任意の形のプログラミング言語で書き込むことができ、それは、スタンドアロンプログラムとして、または、モジュールとして、構成要素、サブルーチン、もしくは、コンピューティング環境で使用するのに適した他のユニットを含む、任意の形で配備することができる。コンピュータプログラムは、１つのコンピュータ上に、または、１つの現場にある複数のコンピュータ上に配備されて実行され得る、あるいは、複数の現場に分散され、通信ネットワークによって相互接続され得る。
【００６７】
[065]本発明の実施形態の方法のステップは、入力データ上で動作することおよび出力を生成することによって本発明の機能を実行するためにコンピュータプログラムを実行する１つまたは複数のプログラマブルプロセッサによって実行することができる。方法のステップはまた、専用論理回路、たとえばＦＰＧＡ（フィールドプログラマブルゲートアレイ）またはＡＳＩＣ（特定用途向け集積回路）、によって実行することができ、本発明の装置は、専用論理回路として実施することができる。
【００６８】
[066]コンピュータプログラムの実行に適したプロセッサは、例として、汎用および専用マイクロプロセッサの両方と、任意の種類のデジタルコンピュータの任意の１つまたは複数のプロセッサとを含む。一般に、プロセッサは、読取り専用メモリもしくはランダムアクセスメモリまたはその両方から命令およびデータを受信することになる。コンピュータの本質的要素は、命令を実行するためのプロセッサと、命令およびデータを記憶するための１つまたは複数のメモリデバイスとである。一般に、コンピュータは、データを記憶するための１つまたは複数の大容量記憶装置、たとえば磁気、光磁気ディスクまたは光ディスク、を含む、あるいは、そこからデータを受信する、もしくはそこにデータを転送する、またはその両方を行うために動作可能なように結合されることになる。コンピュータプログラム命令およびデータを実施するのに適した情報搬送波は、例として半導体メモリデバイス、たとえばＥＰＲＯＭ、ＥＥＰＲＯＭおよびフラッシュメモリデバイス、と、磁気ディスク、たとえば内部ハードディスクまたは取外し可能ディスク、と、光磁気ディスクと、ＣＤ  ＲＯＭおよびＤＶＤ−ＲＯＭディスクとを含む、すべての形の不揮発性メモリを含む。そのプロセッサおよびそのメモリは、専用論理回路によって補完され得る、または専用論理回路に組み込まれ得る。
【００６９】
[067]前述の説明は、本発明の範囲を説明するものであり、それを限定するものではないことを理解されたい。
【図１】
0005932024.tif 000002
【図２】
0005932024.tif 000003
【図３】
0005932024.tif 000004
【図４】
0005932024.tif 000005
【図５】
0005932024.tif 000006
【図６】
0005932024.tif 000007
【図７】
0005932024.tif 000008
【図８】
0005932024.tif 000009
【図９】
0005932024.tif 000010