(57)【特許請求の範囲】
【請求項１】
分散データ複製システムの複数の装置のうちの１つ以上の装置によって実行される方法であって、
前記１つ以上の装置において、クライアントから、オブジェクトをアップロードするという要求を受信するステップと、
前記要求に応答して、前記アップロードされたオブジェクトに対する固有のテンポラリ識別子を、前記１つ以上の装置により前記クライアントに送信するステップと、
前記アップロードされたオブジェクトを含み、前記固有のテンポラリ識別子を有する複数のチャンクを、前記１つ以上の装置において受信するステップと、
前記固有のテンポラリ識別子によって鍵付けされた、前記オブジェクトに対するエントリを、前記分散データ複製システムに対するインデックスにおいて、前記１つ以上の装置により作成するステップと、
前記アップロードされたオブジェクトをファイナライズする要求を、前記クライアントから、前記１つ以上の装置において受信するステップと、
前記アップロードされたオブジェクトをファイナライズする要求の受信に基づいて、前記アップロードされたオブジェクトを前記１以上の装置によってロックするステップと、
前記複数のチャンクから、前記アップロードされたオブジェクトを、前記１つ以上の装置において再構築するステップと、
前記アップロードされたオブジェクトに、コンテンツベース識別子を割当てるステップと、
前記コンテンツベース識別子によって鍵付けされた、前記オブジェクトに対する別のエントリを、前記分散データ複製システムに対する前記インデックスにおいて前記１つ以上の装置により作成するステップとを含む、方法。
【請求項２】
前記複数のチャンクの受信を確認するために、前記クライアントにサクセスコードを前記１つ以上の装置によって送信するステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記インデックス内の前記固有のテンポラリ識別子によって鍵付けされたエントリから、前記インデックス内の前記コンテンツベース識別子により鍵付けされた前記別のエントリへ、前記オブジェクトに対するリファレンスをコピーするステップをさらに含む、請求項１に記載の方法。
【請求項４】
前記インデックスは、前記インデックス内の各オブジェクトに対するコンテンツハンドルを含む、コンテンツ指定可能なインデックスである、請求項１に記載の方法。
【請求項５】
前記アップロードされたオブジェクトをロックするステップは、
前記アップロードされたオブジェクトに対する前記固有のテンポラリ識別子に関連付けられたインデックスの部分に、オブジェクトロックメッセージを前記１つ以上の装置によって書き込むステップを含み、
前記方法は、さらに、
前記アップロードされたオブジェクトに対する前記固有のテンポラリ識別子に関連付けられたインデックスの部分を、前記複数の装置のうちの１つ以上の別の装置に複製するステップとをさらに含む、請求項１に記載の方法。
【請求項６】
前記アップロードされたオブジェクトに対する前記固有のテンポラリ識別子に関連付けられたインデックスの部分に、前記アップロードされたオブジェクトに対する前記コンテンツベース識別子に関連付けられたインデックスの部分へのクロスリファレンスを、前記１つ以上の装置によって書き込むステップをさらに含む、請求項５に記載の方法。
【請求項７】
前記アップロードされたオブジェクトに対する前記コンテンツベース識別子に関連付けられたインデックスの部分への前記クロスリファレンスを書き込んだ後、前記オブジェクトに対する前記固有のテンポラリ識別子に関連付けられたインデックスの部分から前記オブジェクトロックメッセージを、前記１つ以上の装置によって削除するステップをさらに含む、請求項６に記載の方法。
【請求項８】
前記インデックスは、前記１つ以上の装置の各々において前記アップロードされたオブジェクトとは別々に記憶される、請求項１に記載の方法。
【請求項９】
分散データ複製システムにおける複数の装置のうちの装置であって、
前記分散データ複製システム内のオブジェクトのインデックスを記憶するための手段と、
前記分散データ複製システムに対して新しいオブジェクトのチャンクを受信するための手段とを含み、前記チャンクは、前記新しいオブジェクトを形成する複数のチャンクのうちの最後のチャンクを含み、前記複数のチャンクの各々は、同じテンポラリ識別子を含み、
前記新しいオブジェクトに対する前記テンポラリ識別子を、前記インデックスに書き込むための手段と、
前記新しいオブジェクトコンテンツのコンテンツのさらなる修正が不可能であるように前記新しいオブジェクトをロックするための手段と、
前記新しいオブジェクトに対するコンテンツベース識別子を演算するための手段と、
前記新しいオブジェクトが前記コンテンツベース識別子によってアクセスされることを可能にするように、前記インデックスを更新するための手段とを含む、装置。
【請求項１０】
前記インデックス内の前記テンポラリ識別子へのリファレンスを、前記インデックス内の前記コンテンツベース識別子にコピーするための手段をさらに含む、請求項９に記載の装置。
【請求項１１】
命令、オブジェクトのデータストア、および前記データストア内のオブジェクトのインデックスを記憶するメモリと、
同じ固有のテンポラリ識別子を有し、アップロードされるオブジェクトを含む複数のチャンクを受信し、
前記固有のテンポラリ識別子によって鍵付けされた、前記オブジェクトに対するエントリを、前記インデックスにおいて作成し、
前記オブジェクトのコンテンツのさらなる修正から前記オブジェクトをロックし、
前記オブジェクトに対するコンテンツベース識別子を演算し、
前記コンテンツベース識別子によって鍵付けされた、前記オブジェクトに対する別のエントリを、前記インデックスにおいて作成し、
前記固有のテンポラリ識別子から前記コンテンツベース識別子へ指し示すように前記インデックスを更新するために、前記メモリ内の前記命令を実行するプロセッサとを含む、システム。
【請求項１２】
前記プロセッサは、
前記オブジェクトをアップロードする要求を受け取り、
アップロードされるオブジェクトに対して前記固有のテンポラリ識別子を割当てるために、前記メモリ内の命令をさらに実行する、請求項１１に記載のシステム。
【請求項１３】
前記プロセッサは、
前記オブジェクトをファイナライズする要求を受け取り、
前記複数のチャンクから前記オブジェクトを再構築するために、前記メモリ内の命令をさらに実行する、請求項１１に記載のシステム。
【請求項１４】
前記プロセッサは、
前記複数のチャンクの受信を確認するためにサクセスコードを送信するために、前記メモリ内の命令をさらに実行する、請求項１１に記載のシステム。
【請求項１５】
前記プロセッサは、前記オブジェクトをファイナライズする要求を受信するために、前記メモリ内の命令をさらに実行し、
前記プロセッサは、前記要求の受信に基づいて、前記オブジェクトのコンテンツのさらなる修正から前記オブジェクトをロックする、請求項１１に記載のシステム。
【請求項１６】
前記プロセッサは、
前記インデックス内の前記固有のテンポラリ識別子によって鍵付けされたエントリから、前記インデックス内の前記コンテンツベース識別子によって鍵付けされたエントリへ、前記固有のテンポラリ識別子へのリファレンスをコピーするために、前記メモリ内の命令をさらに実行する、請求項１１に記載のシステム。
【請求項１７】
２つ以上の装置によって実行される方法であって、
同じ固有のテンポラリ識別子を有し、アップロードされるオブジェクトを含む複数のチャンクを、前記２つ以上の装置において受信するステップと、
前記２つ以上の装置の各々において分散型マルチマスタデータ複製システムの下層の複製層を用いて複製されたインデックスにおいて、前記固有のテンポラリ識別子によって鍵付けされた、前記オブジェクトに対するエントリを、前記２つ以上の装置にて作成するステップと、
前記複数のチャンクの集合が前記オブジェクトの全てのデータを含むことを、前記２つ以上の装置のうちの開始装置により、前記複製されたインデックスに基づいて、判定するステップと、
前記オブジェクトに対するコンテンツベース識別子を、前記開始装置によって演算するステップと、
前記コンテンツベース識別子によって鍵付けされた、前記オブジェクトに対する別のエントリを、前記複製されたインデックスにおいて、前記２つ以上の装置にて作成するステップと、
前記固有のテンポラリ識別子から前記コンテンツベース識別子へ指し示すように、前記２つ以上の装置によって、前記複製されたインデックスを更新するステップとを含む、方法。
【請求項１８】
前記２つ以上の装置によって、前記オブジェクトのコンテンツのさらなる修正から前記オブジェクトをロックするステップをさらに備える、請求項１７に記載の方法。
【請求項１９】
前記複製されたインデックスは、コンテンツを指定可能なインデックスである、請求項１７に記載の方法。
【請求項２０】
コンピュータ実行可能命令を含むコンピュータ読出可能メモリであって、
１以上のコンピュータによって実行されることによって前記１以上のコンピュータが、同じ固有のテンポラリ識別子を有する複数のチャンクを含むアップロードされたオブジェクトのチャンクを受信するための１以上の命令と、
１以上のコンピュータによって実行されることによって前記１以上のコンピュータが、前記複数のチャンクの集合が、前記アップロードされたオブジェクトの全てのデータを含むかどうかを判定するための１以上の命令と、
１以上のコンピュータによって実行されることによって前記１以上のコンピュータが、前記アップロードされたオブジェクトのコンテンツへのさらなる修正から前記アップロードされたオブジェクトをロックするための１以上の命令と、
１以上のコンピュータによって実行されることによって前記１以上のコンピュータが、前記アップロードされたオブジェクトに対してコンテンツベース識別子を演算するための１以上の命令と、
１以上のコンピュータによって実行されることによって前記１以上のコンピュータが、前記コンテンツベース識別子によって鍵付けされた、前記アップロードされたオブジェクトに対するエントリを、複製されたインデックス内に作成するための１以上の命令と、
１以上のコンピュータによって実行されることによって前記１以上のコンピュータが、前記複製されたインデックス内の前記固有のテンポラリ識別子へのリファレンスを、前記固有のテンポラリ識別子から前記コンテンツベース識別子に変更するように前記複製されたインデックスを更新するための１以上の命令とを含む、コンピュータ読出可能メモリ。
【請求項２１】
１以上のコンピュータによって実行されることによって前記１以上のコンピュータが、前記オブジェクトをアップロードする要求を受信するための１以上の命令と、
１以上のコンピュータによって実行されることによって前記１以上のコンピュータが、アップロードの前に前記オブジェクトに対して固有のテンポラリ識別子を割当てるための１以上の命令とをさらに含む、請求項２０に記載のコンピュータ読出可能メモリ。
【請求項２２】
１以上のコンピュータによって実行されることによって前記１以上のコンピュータが、前記複製されたインデックス内の前記テンポラリ識別子へのリファレンスを、前記複製されたインデックス内の前記コンテンツベース識別子にコピーするための１以上の命令をさらに含む、請求項２０に記載のコンピュータ読出可能メモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
背景
企業コンピューティングの景観は、ストレージ構造において、中央サービス構造が分散ストレージクラスタに取って代わられるという抜本的な転換期にある。企業が記憶効率を高める方法を求めるにつれ、汎用のコンピュータで作られたストレージクラスタは、一体型のディスクアレイに比べて僅かなコストで高い能力、可用性、新しいデータ集約型アプリケーションに対する拡張性を実現し得る。ストレージクラスタの潜在能力を全て解き放つため、データは複数の地理的な場所に亘って複製され、もって、可用性が高められ、クライアントからのネットワーク距離が短くされる。
【背景技術】
【０００２】
そのようなシステムにおいて、分散オブジェクトおよびリファレンスは、動的に作成され、クローンが作られ、（マルチマスターモデルを用いて）異なるクラスタにおいて削除され、全てのクラスタがデータの同じビューで終わることを確かにする書込み順序の忠実性を、下層のデータ複製層が維持する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
現在の視覚化、マルチメディア、および別のデータ集約的アプリケーションの中には、非常に大きなオブジェクト（典型的には数百ギガバイトまたは数テラバイトにもなり得る）を用いるものがある。そのようなオブジェクトの分散ストレージシステムへのアップロードは、典型的には、オブジェクトをチャンクに分割し、各チャンクを個別にアップロードすることによりストリーミングモードにおいてなされる。この処理は、アップロード時間における長い遅延を与え、遅延は、クライアントおよび／またはサーバの潜在的な不具合によって悪化し得る。結果的に、一貫性を保証する、ストリーミングモードにおける効率的な分散オブジェクトアップロードが、同時に利用可能な任意のクラスタへの接続をクライアントに許容する大規模システムの需要によって駆り立てられるストレージ産業にとってますます重要となっている。
【課題を解決するための手段】
【０００４】
概要
１つの実施例において、方法は、分散型データ複製システムの複数の装置のうちの１つ以上の装置によって実行され得る。方法は、１つ以上の装置において、クライアントから、オブジェクトをアップロードするという要求を受信するステップと、要求に応答して、オブジェクトに対する固有のテンポラリ識別子を、１つ以上の装置によりクライアントに送信するステップと、アップロードされたオブジェクトを含み、固有のテンポラリ識別子を有する複数のチャンクを、１つ以上の装置において受信するステップと、固有のテンポラリ識別子によって鍵付けされた、オブジェクトに対するエントリを、分散データ複製システムに対するインデックスにおいて、１つ以上の装置により作成するステップと、アップロードされたオブジェクトをファイナライズする要求を、クライアントから、１つ以上の装置において受信するステップと、複数のチャンクから、オブジェクトを、１つ以上の装置において再構築するステップと、アップロードされたオブジェクトに、コンテンツに基づく識別子を割当てるステップと、コンテンツベース識別子によって鍵付けされた、オブジェクトに対する別のエントリを、分散データ複製システムに対するインデックスにおいて１つ以上の装置により作成するステップとを含む。
【０００５】
別の実施例において、分散データ複製システムにおける複数の装置のうちの装置は、分散データ複製システム内のオブジェクトのインデックスを記憶するための手段と、分散データ複製システムに対する新しいオブジェクト内の特定のオフセットにあるチャンクを受信するための手段とを含み得る。チャンクの組のうちの各々は、同じテンポラリ識別子を含み得る。装置はさらに、新しいオブジェクトに対するテンポラリ識別子を、インデックスに書き込むための手段と、新しいオブジェクトコンテンツのコンテンツのさらなる修正が不可能であるように新しいオブジェクトをロックするための手段と、新しいオブジェクトに対するコンテンツベース識別子を演算するための手段と、新しいオブジェクトがコンテンツベース識別子によってアクセスされることを可能にするように、インデックスを更新するための手段とを含み得る。
【０００６】
さらに別の実施例において、システムは、命令、オブジェクトのデータストア、およびデータストア内のオブジェクトのインデックスを記憶するメモリを含み得る。システムは、同じ固有のテンポラリ識別子を有し、アップロードされるオブジェクトを含むチャンクの組を受信し、固有のテンポラリ識別子によって鍵付けされた、オブジェクトに対するエントリを、インデックスにおいて作成し、オブジェクトに対するコンテンツベース識別子を演算し、パーマネントコンテンツベース識別子によって鍵付けされた、新しいオブジェクトに対する別のエントリを、インデックスにおいて作成し、固有のテンポラリ識別子からコンテンツベース識別子へ指し示すようにインデックスを更新するために、メモリ内の命令を実行するプロセッサをも含み得る。
【０００７】
さらに別の実施例において、２つ以上の装置によって実行される方法は、同じ固有のテンポラリ識別子を有し、アップロードされるオブジェクトを含むチャンクの組を、２つ以上の装置において受信するステップと、２つ以上の装置の各々において複製されたインデックスにおいて、固有のテンポラリ識別子によって鍵付けされた、オブジェクトに対するエントリを、２つ以上の装置にて作成するステップと、チャンクの組の集合は、オブジェクトの全てのデータを含むことを、２つ以上の装置のうちの開始装置によって判定するステップと、オブジェクトに対するコンテンツベース識別子を、開始装置によって演算するステップと、コンテンツベース識別子によって鍵付けされた、オブジェクトに対する別のエントリを、複製されたインデックスにおいて、２つ以上の装置にて作成するステップと、固有のテンポラリ識別子からコンテンツベース識別子へ指し示すように、２つ以上の装置によって、複製されたインデックスを更新するステップとを含み得る。
【０００８】
さらに別の実施例において、コンピュータ読出可能メモリは、コンピュータ実行可能命令を含み得る。コンピュータ読出可能メモリは、同じ固有のテンポラリ識別子を有するチャンクの組を含むアップロードされたオブジェクトのチャンクを特定のオフセットにて受信するための命令と、チャンクの組の集合が、アップロードされたオブジェクトの全てのデータを含むかどうかを判定するための命令と、アップロードされたオブジェクトのコンテンツへのさらなる修正からアップロードされたオブジェクトをロックするための命令と、アップロードされたオブジェクトに対してコンテンツベース識別子を演算するための命令と、コンテンツベース識別子によって鍵付けされた、アップロードされたオブジェクトに対するエントリを、複製されたインデックス内に作成するための命令と、複製されたインデックス内の固有のテンポラリ識別子へのリファレンスを、固有のテンポラリ識別子からコンテンツベース識別子に変更するように複製されたインデックスを更新するための命令とを含み得る。
【０００９】
図面の簡単な説明
組み込まれてこの明細書の一部をなす添付の図面は、ここで説明される１つ以上の実施例を示し、記述とともにこれらの実施例を説明する。
【図面の簡単な説明】
【００１０】
【図１】ここで説明されるシステムおよび方法が実現され得る例示のシステムの図である。
【図２】図１のファイルシステムの例示の構成の図である。
【図３】図１のストレージクラスタの例示のコンポーネントの図である。
【図４】図１の例示のストレージクラスタの機能ブロック図である。
【図５】分散型マルチマスタデータ複製システムのインデックス内で用いられ得る例示のファイナライゼーション記録構造の図である。
【図６】ここで説明される実施例に従う、クライアントにより開始されたアップロード動作のための例示のプロセスのフローチャートである。
【図７】分散型マルチマスタデータ複製システムにおいてクライアントにより開始されたアップロードを受け取るための例示の処理のフローチャートである。
【図８】アップロードされたオブジェクトに対するファイナライズ要求を処理するための例示のプロセスのフローチャートである。
【図９】ここで説明される実施例に従う、ストレージクラスタにおいてスキャンニング動作を実行するための例示の処理のフローチャートである。
【図１０】複製ストレージクラスタのグローバルインデックスへの新しいリファレンスを作成するための例示のプロセスのフローチャートである。
【図１１】ここで説明される実施例に従う、例示のグローバルインデックスの一部を示す図である。
【発明を実施するための形態】
【００１１】
詳細な説明
以下の詳細な説明は添付の図面を参照する。異なる図面における同じ参照番号は同じまたは同様の要素を特定し得る。また、以下の詳細な説明は発明を限定しない。
【００１２】
ここで説明されるシステムおよび／または方法は、大きい不変のオブジェクトに対して可用性、活動性および一貫性の保証を与える複製されたストレージクラスタに対して、ストリーミングモードでの非同期的分散オブジェクトアップロードアルゴリズムを提供し得る。利用可能なクラスタにアプリケーションによって非同期的にアップロードされるチャンクに、オブジェクトが分割され得る。ここで説明される実施例は、異なるストレージクラスタの間で、コンテンツ指定可能インデックス（ここでは「グローバルインデックス」としても呼ばれる）においてチャンクの位置を複製するために、分散型マルチマスタデータ複製システムの下層の複製層を用い得る。一旦、アプリケーションによってオブジェクトがファイナライズされると、固有のコンテンツハンドル（たとえば、ハッシュ値またはデジタル署名）が、チャンクのコンテンツに基づいて演算され得、不変のオブジェクトとしてコンテンツ指定可能インデックスにオブジェクトが挿入される。
【００１３】
ここで用いられる「オブジェクト」という用語は、マルチメディアファイル、画像、データファイル、文書の組などの、個別に選択または操作されるデータのアイテムまたは集合を意味し得る。ここで用いられるように、「チャンク」という用語は、個別にアップロードされ、オブジェクトを再構築するために別のチャンクとともに後でグループ化される、オフセットおよびサイズによって個別に特定されるオブジェクトの一部を意味し得る。
【００１４】
例示のネットワーク構造
図１は、ここで説明されるシステムおよび方法が実現され得る例示のシステム１００の図である。システム１００は、クライアント１１０−１からクライアント１１０−Ｎ（まとめてクライアント１１０と呼ばれ、個別にクライアント１１０と呼ばれる）およびネットワーク１３０を介して接続された、ストレージクラスタ１２０−１から１２０−Ｍ（まとめてストレージクラスタ１２０と呼ばれ、個別にストレージクラスタ１２０と呼ばれる）を含み得る。ストレージクラスタ１２０は、ファイルシステム１４０（図１において破線で示される）を形成し得る。
【００１５】
ネットワーク１３０は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、公衆交換電話網（ＰＳＴＮ）のような電話網、イントラネット、インターネット、類似もしくは非類似のネットワーク、またはネットワークの組合せ等の１つ以上のネットワークを含み得る。クライアント１１０およびストレージクラスタ２０は、有線、および／または無線接続を介してネットワーク１３０に接続され得る。
【００１６】
クライアント１１０は、パーソナルコンピュータ、無線電話、携帯情報端末（ＰＤＡ）、ラップトップ、または別の種類の通信装置等の１つ以上の種類の装置、これらの装置の１つ上で実行しているスレッドまたはプロセス、および／またはこれらの装置によって実行されるオブジェクトを含み得る。１つの実施例において、クライアント１１０は、ファイルデータをアップロード、読出し、または削除するためにクライアント１１０の代わりにストレージクラスタ１２０と通信するアプリケーションを含む、もしくはこのアプリケーションに繋げられる。
【００１７】
ストレージクラスタ１２０は、１つ以上のサーバ装置、または、ここで説明される態様で情報を記憶、処理、検索、および／もしくは提供し得る別の種類の演算または通信装置を含み得る。１つの実施例において、ストレージクラスタ１２０は、ファイルに対して大型のランダムリード／ライトアクセスデータストアを維持することが可能な１つ以上のサーバ（たとえばコンピュータシステムおよび／またはアプリケーション）を含み得る。ストレージクラスタ１２０のデータストアは、変化が生じた場合にインデックスの一部を速やかに更新することをインデックス付けシステムに許可し得る。ストレージクラスタ１２０のデータストアは、１つ以上のテーブル（たとえば、ユニフォームリソースロケータ（ＵＲＬ）毎に１つの行を含み得るドキュメントテーブル、ＵＲＬとは異なる値が入力された補助テーブル等）を含み得る。一例として、ストレージクラスタ１２０は、非常に大きなサイズ（たとえば数千のサーバに亘るデータのペタバイト）を計測するように設計され得る構造化データ（たとえばドキュメントのランダムアクセスストレージクラスタ）を管理するための分散型ストレージシステム（たとえば、チャンその他、「ビッグテーブル：構造化データのための分散型ストレージシステム」、第７回ＯＳＤＩ会報、ｐｐ．２０５−２１８（２００６年１１月）において説明されるような「ビッグテーブル」）内に含まれ得る。
【００１８】
図１には示されないが、システム１００は１つ以上の専用の民生用サーバまたはハブ等のさまざまな別のコンポーネントを含み得る。民生用サーバはたとえば、クライアント１１０からのアクセスのために、１つ以上のストレージクラスタ１２０からの、データストアの読出専用のコピーを記憶し得る。ハブはたとえば、１つ以上の民生用サーバへの配布のために、１つ以上のストレージクラスタ１２０からのデータストアの読出専用コピーを記憶し得る。
【００１９】
例示のストレージクラスタ構造
図２は、ファイルシステム１４０の例示の構造の図である。図２において示されるように、ファイルシステム１４０は、ストレージクラスタ１２０−１，１２０−２，１２０−３，および１２０−４を含み得る。ある実施例において、ファイルシステム１４０は、各々のストレージクラスタ１２０−１，１２０−２，１２０−３，および１２０−４が別のストレージクラスタに対してマスタサーバとして振る舞い得る分散型マルチマスタデータ複製システムであり得る。ファイルシステム１４０において、データの可用性を高め、かつ、クライアント（たとえばクライアント１１０）からのネットワーク距離を短くするために、（たとえば複数の地理的位置における）ストレージクラスタ１２０−１，１２０−２，１２０−３，および１２０−４に亘ってデータが複製され得る。一般的に、分散されたオブジェクトおよびリファレンスは、異なるストレージクラスタ１２０において動的に作成、変形、複製および削除され得、最終的には全てのストレージクラスタ１２０が同じバージョンのデータに行き着くことを確実にするために下層データ複製層（図示せず）が書込指令の忠実性を維持する。したがって、データ複製層が、単一のオブジェクトに対する同じレプリカへの書込の指令を遵守する。
【００２０】
分散型マルチマスタデータ複製システムにおけるすべてのオブジェクトのグローバルインデックスは各ストレージクラスタ１２０に関連付けられる。各記憶されたオブジェクトは、グローバルインデックス内にある固有のコンテンツハンドル（ハッシュ値、デジタル署名など）によって列挙され得る。ここで説明される実施例において、クライアントからアップロードされる新しいオブジェクトには、新しいオブジェクトの各チャンクに関連付けられた、グローバルインデックス内の固有のテンポラリ識別子（ID）が割当てられる。アップロードされたオブジェクトのチャンクのすべてが受取られると、ストレージクラスタの１つがアップロードされたオブジェクトにパーマネントコンテンツハンドルを割当て、パーマネントコンテンツハンドルを用いてオブジェクトがアクセスされることができるようにグローバルインデックスを更新し得る。１つのストレージクラスタによってなされたグローバルインデックスの変更は他のストレージクラスタに複製され得る。
【００２１】
図２はファイルシステム１４０の例示の機能的なコンポーネントを示すが、別の実施例において、ファイルシステム１４０は図２に示されたものよりも少ない、付加的な、異なる、または異なって配置されたコンポーネントを含み得る。さらに別の実施例において、１つ以上の、ファイルシステム１４０の１つ以上のコンポーネントは、ファイルシステム１４０の１つ以上の別のコンポーネントによって実行されるものとして説明された１つ以上の別のタスクを実行し得る。
【００２２】
図３は、ストレージクラスタ１２０の例示のコンポーネントの図である。ストレージクラスタ１２０は、バス３１０、プロセッサ３２０、メインメモリ３３０、リードオンリーメモリ（ＲＯＭ）３４０、記憶装置３５０、入力装置３６０、出力装置３７０、および通信インターフェイス３８０を含み得る。バス３１０は、ストレージクラスタ１２０のコンポーネント間での通信を許容する１つ以上のコンダクタを含み得る。
【００２３】
プロセッサ３２０は、命令を解釈し実行し得る任意のタイプのプロセッサまたはマイクロプロセッサを含み得る。メインメモリ３３０は、ランダムアクセスメモリ（ＲＡＭ）または、情報ならびにプロセッサ３２０による実行のための命令を記憶し得る別の種類の動的記憶装置を含み得る。ＲＯＭ３４０は、ＲＯＭ装置または、静的情報ならびにプロセッサ３２０のよる使用のための命令を記憶し得る別の種類の静的記憶装置を含み得る。記憶装置３５０は、磁気および／または光学記録媒体ならびにその対応するドライブを含み得る。たとえば、記憶装置３５０は、永続的なストレージを提供する１つ以上のローカルディスク３５５を含み得る。１つの実施例において、ストレージクラスタ１２０は、メインメモリ３３０および／または記憶装置３５０等の１つ以上のコンピュータ読取可能媒体内において、ファイルシステム１４０内に記憶されたオブジェクトに対して、メタデータを維持し得る。たとえば、ストレージクラスタ１２０は、分散型マルチマスタデータ複製システム内に記憶されたオブジェクトの全てに対して、記憶装置３５０内にグローバルインデックスを記憶し得る。
【００２４】
入力装置３６０はキーボード、キーパッド、ボタン、マウス、ペン等の、操作者がストレージクラスタ１２０に情報を入力することを可能にする１つ以上の機構を含み得る。出力装置３７０は、ディスプレイ、発光ダイオード（ＬＥＤ）等を含む、操作者に対して情報を出力する１つ以上の機構を含み得る。通信インターフェイス３８０は、ストレージクラスタ１２０が別の装置および／またはシステムと通信できるようにする任意のトランシーバのような機構を含み得る。たとえば、通信インターフェイス３８０は、別のストレージクラスタ１２０および／またはクライアント１１０と通信するための機構を含み得る。
【００２５】
図４はストレージクラスタ１２０の機能ブロック図を示す。図４に示されるように、ストレージクラスタ１２０はデータストア４１０およびチャンク処理ロジック４２０を含み得る。１つの実施例において、図４において示されるように、データストア４１０はストレージクラスタ１２０内に配置され得る。別の実施例において、いくつかの、または全てのデータストア４１０は、外部メモリ装置またはインデックス付けシステムに関連付けられた装置（図示せず）等の、ストレージクラスタ１２０と通信するシステム１００の１つ以上の別の装置内に設けられてもよい。
【００２６】
データストア４１０は、複製されたインデックスストア４１２とローカルオブジェクトストア４１４とを含み得る。複製されたインデックスストア４１２は、分散型マルチマスタデータ複製システムの複製層の一部として含まれ得る。複製されたインデックスストア４１２は、グローバルインデックスに関連する情報を記憶し得る。複製されたインデックスストア４１２の少なくとも一部は、複数のストレージクラスタ１２０に複製され得る。各複製されたインデックスストア４１２に対する複製の数は、ユーザによって設定可能であり得る。ローカルオブジェクトストア４１４は、ストレージクラスタ１２０内でオブジェクトをローカルで記憶し得る。ローカルオブジェクトストア４１４は、クライアント（例えばクライアント１１０）によってアップロードされた画像または動画等のファイルを含み得る。
【００２７】
チャンク処理ロジック４２０は、クライアントからアップロードされたチャンク（各チャンクは、オブジェクト内のそのオフセットにより識別される）を受信するため、および／または、分散型マルチマスタデータ複製システム（たとえばストレージクラスタ１２０−１，１２０−２，１２０−３，および１２０−４）内の複数のチャンクからオブジェクトを自動的に再構築するためのロジックを含み得る。クライアント（たとえばクライアント１１０）がオブジェクトのアップロードを開始すると、チャンク処理ロジック４２０は、オブジェクトのすべてのチャンクをアップロードするためにクライアントが用いることができるオブジェクトに対して固有のテンポラリ識別子を割当て得る。クライアント（たとえばクライアント１１０）がオブジェクトのすべてのチャンクのアップロードを完了すると、クライアントは、クラスタ１２０のうちの１つにおいてチャンク処理ロジック４２０によって実行されるファイナライズ機能を呼出し得る。チャンク処理ロジック４２０は、オブジェクトをロック（またはシール）する（たとえばオブジェクトのコンテンツのさらなる修正が不可能であることを確実にする）ため、グローバルインデックスに変更を加え得る。チャンク処理ロジック４２０は、オブジェクトコンテンツハッシュ（たとえばオブジェクトのコンテンツに基づいて生成された英数字の文字列）を演算し、ハッシュに基づいてオブジェクトにパーマネント識別子を割当て得る。チャンク処理ロジック４２０は、さらに、パーマネント識別子を用いて分散型マルチマスタデータ複製システム内でオブジェクトがアクセスされることを可能にするようにグローバルインデックスを更新する。
【００２８】
複数のアップロードされたチャンクからのオブジェクトのファイナライゼーションを容易にするため、記録（たとえばメタデータ）がチャンク処理ロジック４２０によって生成され得、特定のコンテンツハンドルまたはテンポラリIDに関連付けられたグローバルインデックスの一部に加えられる。１つのクラスタによって生成された記録は、最終的には、分散型マルチマスタデータ複製システムにおける別のクラスタにあるインデックスの複製に伝搬し得る。記録は、たとえば、オブジェクトのファイナライゼーションが開始したことを示すための「FinStarted」指定子と、アップロードされたオブジェクトのチャンクのすべてのメタデータがインデックスによって複製され、オブジェクトのコンテンツに対するさらなる変更はなされ得ないことを示すための「FinSealed」指定子と、パーマネントIDへのクロスリファレンスがグローバルインデックスに含まれるべきであり、オブジェクトのリファレンスがテンポラリIDからパーマネントIDのインデックスエントリにコピーされるべきであることを示す「FinRefCopy」指定子と、グローバルインデックスの複製にクロスリファレンスが加えられ、すべてのオブジェクトリファレンスが、テンポラリIDからパーマネントIDのインデックスエントリにコピーされたことを示すための「FinRefCopyDone」指定子と、将来のリファレンスをテンポラリIDからパーマネントIDのインデックスエントリにリダイレクトする「FinDone」指定子とを含み得る。記録のフォーマットと仕様は以下により詳細に説明される。
【００２９】
図４はストレージクラスタ１２０の例示の機能的なコンポーネントを示すが、別の実施例において、ストレージクラスタ１２０は図４に示される機能的なコンポーネントよりも少ない、付加的な、異なる、または異なって配置されたコンポーネントを含み得る。さらに別の実施例において、ストレージクラスタ１２０の１つ以上の機能的なコンポーネントは、１つ以上の別の機能的なコンポーネントによって実行されるものとして説明された１つ以上の別のタスクを実行し得る。
【００３０】
例示の記録構造
図５は、例示の実施例においてグローバルインデックスに書込まれ得るファイナライゼーション記録のための例示の記録構造５００の図面を提供する。ファイナライゼーション記録は、オブジェクトの複製の特定のテンポラリIDを用いてグローバルインデックスにおいて関連付けられ得る。
【００３１】
図５に示されるように、記録構造５００は、指定部５１０と配置部５２０とを含み得る。指定部５１０は、たとえば、「FinStarted」指定子、「FinSealed」指定子、「FinRefCopy」指定子、「FinRefCopyDone」指定子、または「FinDone」指定子を含み得る。アップロードが完了した際にクライアント（たとえばクライアント１１０）からファイナライズ要求を受取ったストレージクラスタ１２０（ここでは、「開始クラスタ」と呼ばれる）は、テンポラリIDによって鍵付けされたオブジェクトのメタデータに「FinStarted」記録を加え得る。
【００３２】
「FinSealed」指定子は、「FinStarted」記録と遭遇した各ストレージクラスタ（開始クラスタを含む）によって加えられ得る。「FinSealed」指定子は、「FinStarted」記録と関連付けられたオブジェクトの複製にさらなる変更（たとえば追加、更新、または削除）がなされ得ないことを示すために用いられ得る。
【００３３】
「FinRefCopy」指定子は、テンポラリIDからパーマネントID（たとえばオブジェクトに対するコンテンツハッシュに基づく）へのクロスリファレンスを示すために開始クラスタによって用いられ得る。開始クラスタは、グローバルインデックス内のオブジェクトのメタデータに「FinRefCopy」メッセージを書込み得る。「FinRefCopy」指定子は、オブジェクトに対してパーマネントIDが利用可能であり、テンポラリIDに関連付けられたリファレンスがパーマネントIDのインデックスエントリにコピーされるべきであることを示すために別のストレージクラスタ１２０に、グローバルインデックスを用いて複製され得る。「FinRefCopy」指定子は、テンポラリIDのインデックスエントリに新しいリファレンスが加えられないことを示すためにも用いられ得る。
【００３４】
「FinRefCopyDone」指定子は、グローバルインデックスの複製におけるパーマネントIDに対する、テンポラリIDに関連付けられた任意のリファレンスをクラスタが有することを示すために用いられ得る。開始クラスタが、分散型マルチマスタデータ複製システムにおけるすべてのストレージクラスタに対して「FinRefCopyDone」指定子を見つけた場合、テンポラリIDに関連付けられた「FinStarted」、「FinSealed」、および「FinRefCopyDone」記憶は削除され得る。ある実施例において、「FinRefCopy」指定子は、将来のリファレンスをテンポラリIDからパーマネントIDに向けるためのクロスリファレンスを提供するためにグローバルインデックスにおいて残され得る。別の実施例において、「FinRefCopy」指定子は、他の記録と共に削除され新しい「FinDone」記録が加えられ得る。
【００３５】
「FinDone」指定子は、テンポラリIDによって鍵付けされたエントリから、対応するオブジェクトの複製に対するパーマネントID（たとえばオブジェクトに対するコンテンツハッシュに基づく）へのパーマネントクロスリファレンスを提供するために開始クラスタによって用いられ得る。開始クラスタは、グローバルインデックス内のオブジェクトのメタデータに「FinDone」メッセージを書込み得る。「FinDone」指定子は、オブジェクトに対してパーマネントIDが使用可能であり、テンポラリIDに関連付けられたリファレンスがパーマネントIDのインデックスエントリに変更されるべきであることを示すために、グローバルインデックスと共に別のストレージクラスタ１２０に複製され得る。
【００３６】
１つの実施例において、指定部５１０が「FinStarted」、「FinSealed」、または「FinRefCopyDone」指定を含む場合、配置部５２０は、指定部５１０における指定と関連付けられたストレージクラスタ１２０に対して固有の識別子（たとえば「クラスタID」）を含み得る。別の実施例において、指定部５１０が「FinRefCopy」または「FinDone」指定を含む場合、配置部５２０は、オブジェクトの複製のテンポラリIDに関連付けられた、パーマネントIDへのクロスリファレンスを含み得る。
【００３７】
記録構造５００は、「指定：配置」の形式で列挙され得る。たとえば、テンポラリIDを有する特定のオブジェクトに対する記録が、「FinStarted:01」の記録を有するストレージクラスタ１２０−１によってグローバルインデックスに加えられ得る。ここで、「FinStarted」は指定子であり、「01」はストレージクラスタ１２０−１に対するクラスタIDである。ストレージクラスタ１２０−２における同じオブジェクトの別の複製に対する記録は、「FinRefCopy:cat1324」であり得る。ここで、「FinRefCopy」は指定子であり、「cat1324」はオブジェクトに対するパーマネントIDである。
【００３８】
例示の処理フロー
図６は、ここで説明される実施例に従う、クライアントにより開始されたアップロード動作を管理するための例示のプロセス６００のフローチャートを提供する。ある実施例において、プロセス６００は、クライアント１１０のうちの１つによって実行され得る。別の実施例において、処理６００のいくつかあるいはすべては、別の装置あるいは、クライアント１１０を含むもしくは除く装置の組によって実行され得る。
【００３９】
図６を参照して、処理６００は、オブジェクトのアップロードを要求し（ブロック６１０）、オブジェクトに対するテンポラリIDを受信する（ブロック６２０）ことから始まり得る。たとえば、クライアント１１０は、ストレージクラスタ１２０に、分散型マルチマスタデータ複製システムにファイルをアップロードするように要求を提出し得る。ストレージクラスタは、要求を受信し、ファイルに対して固有のテンポラリIDを割当て得る。テンポラリIDは、グローバルインデックスにおいて用いられるパーマネントID（たとえばコンテンツベースのハッシュ）のフォーマットと区別することができる任意のフォーマットで提供され得る。クライアント１１０は、ストレージクラスタ１２０からテンポラリIDを受信し得る。
【００４０】
オブジェクトはチャンクに分割され得る（ブロック６３０）。たとえば、クライアント１１０は、ファイルを、重複するデータを有さない複数のチャンクに分割し得る。１つの実施例において、各チャンクは、そのオフセットおよびデータサイズによって識別される対応するバイト範囲を有する（たとえば、第１のチャンクはオフセットが０でありチャンクサイズが６３，９００，０００バイトであることを示し、第２のチャンクは、オフセットが６３，９００，０００でありチャンクサイズが６３，９８９，０５０バイトであることを示し、第３のチャンクはオフセットが１２７，８８９，０４９でありチャンクサイズが６２，８００，０００バイトであることを示し得る。）。
【００４１】
チャンクは非同期的にアップロードされ得（ブロック６４０）、ファイナライゼーション要求が開始され得る（ブロック６５０）。たとえば、クライアント１１０は、分散型マルチマスタデータ複製システム内の任意の利用可能なストレージクラスタ１２０にチャンクをアップロードし得る。各チャンクに同じ割当てられたテンポラリIDが標識付けられ、アップロードされたチャンクのバイトの範囲の集合がファイルの全体をカバーするようにチャンクがアップロードされ得る。最後のチャンクがアップロードされると、クライアント１１０は、ファイルをロックするように分散型マルチマスタデータ複製システム内のアクティビティを開始するようにファイナライズ機能を呼出し、ファイルのコンテンツハッシュを演算し、ハッシュに基づいてパーマネントIDを割当て得る。ファイナライズ要求は、アップロードされたオブジェクトのメタデータのレプリカを有する任意のストレージクラスタ１２０によって受信され得る。ファイナライズ要求を受信したストレージクラスタ１２０は、分散型マルチマスタデータ複製システム内の後のファイナライゼーションアクティビティに対して、特定のアップロードされたファイルに関して開始クラスタとして振る舞い得る。
【００４２】
サクセスコードが受信され得る（ブロック６６０）。たとえばクライアント１１０は、ファイルが成功裏に分散型マルチマスタデータ複製システムにアップロードされたことを示すためにストレージクラスタ１２０の１つから（たとえば開始クラスタから）サクセスコードを受信し得る。
【００４３】
図７は、分散型マルチマスタデータ複製システム（たとえばファイルシステム１４０）においてクライアントにより開始されたアップロードを受信するための例示の処理７００のフローチャートである。１つの実施例において、処理７００は、１つ以上のストレージクラスタ１２０によって実行され得る。別の実施例において、処理７００のいくつかあるいはすべてが、別の装置もしくは、ストレージクラスタ１２０を含むあるいは除く装置のグループによって実行され得る。処理７００は、各ストレージクラスタ１２０において定期的に実現され得、ストレージクラスタ１２０内のオブジェクトのすべてあるいは一部のスキャンを含み得る。以下に説明されるプロセス７００の特定の例において、ファイルシステム１４０のストレージクラスタ１２０−１および１２０−２についてリファレンスが作られ得る。ストレージクラスタ１２０−１は「01」のクラスタIDを含み、ストレージクラスタ１２０−２は「02」のクラスタIDを含む。
【００４４】
図７に示されるように、処理７００は、オブジェクトのアップロード要求を受取り（ブロック７１０）、オブジェクトに対して固有のテンポラリIDを割当てることから始まり得る。たとえば、ストレージクラスタ１２０−１は、クライアント１１０の１つからオブジェクトに対するアップロード要求を受信し得る。ストレージクラスタ１２０は、アップロード中にオブジェクトの各チャンクを指定するのにクライアント１１０が用いることができる、オブジェクトに対する固有のテンポラリIDを割当て得る。テンポラリIDは、アップロードされたオブジェクトに対して、グローバルインデックスにおいて鍵として用いられ得る。テンポラリIDは、グローバルインデックスにおいて用いられる、パーマネントID（コンテンツベースハッシュ）のフォーマットと区別することができる任意のフォーマットで提供され得る。
【００４５】
アップロードされたチャンクが受信され得る（ブロック７３０）。たとえば、１つ以上のストレージクラスタ１２０がクライアント１１０からチャンクを受信し得る。チャンクは、分散型マルチマスタデータ複製システムにおける任意の利用可能なクラスタ１２０にアップロードされ得るため、同じオブジェクトの異なるチャンクが異なるストレージクラスタ１２０において受信され得る。各チャンクに同じ割当てられたテンポラリIDが標識付けられ、もってアップロードされたチャンクのバイト範囲の集合がオブジェクトの全体をカバーするようにチャンクがアップロードされ得る。
【００４６】
ファイナライズ要求が受信され得る（ブロック７４０）。たとえば、オブジェクトのチャンクをアップロードしたクライアント１１０から、１つのストレージクラスタ１２０、がファイナライズ要求を受信し得る。ファイナライズ要求は、オブジェクトのすべてのチャンクがアップロードされた後に受信され得る、ファイナライズ要求を受信したストレージクラスタ１２０は、開始クラスタとも呼ばれ得る。
【００４７】
アップロードされたチャンクからオブジェクトが再構築され得る（ブロック７５０）。たとえば、１つのストレージクラスタ１２０（たとえば開始クラスタ）が、分散型マルチマスタデータ複製システムの下層の複製層を介して、アップロードされたオブジェクトに関連付けられたすべてのチャンクの位置を受信し得る。固有のテンポラリIDと各チャンクに対するバイト範囲シーケンスとを用いて、ストレージクラスタ１２０は、チャンクの現在の位置からチャンクをコピーし、アップロードされたオブジェクトを再構築するためにそれらを組合せ得る。
【００４８】
ファイナライズ要求が処理され得る（ブロック７６０）。たとえば、開始クラスタは、オブジェクトをロックする（たとえばオブジェクトのコンテンツのさらなる修正が不可能であるようにする）ために一連の非同期的なアクティビティを開始し、オブジェクトのコンテンツハッシュ（たとえばオブジェクトのコンテンツに基づく、基づいて生成された英数字の文字列）を演算し、ハッシュに基づいてオブジェクトにパーマネントIDを割当てる。ファイナライゼーションアクティビティも、パーマネントIDおよびテンポラリIDの両方を用いて、分散型マルチマスタデータ複製システムにおいてオブジェクトがアクセスされることができるようにグローバルインデックスを更新し得る。ファイナライズ要求の処理は図８から１０に関連してさらに述べられる。
【００４９】
図８は、上記のブロック７６０における、アップロードされたオブジェクトに対するファイナライズ要求を処理するための例示の処理のフローチャートである。１つの実施例において、処理は開始クラスタ（たとえばストレージクラスタ１２０のうちの１つ）によって実行され得る。別の実施例において、処理のいくつかもしくはすべては、別の装置もしくは開始クラスタを含むあるいは除く装置の組によって実行され得る。図８におけるプロセスの特定の例において、３つのストレージクラスタ、すなわちストレージクラスタ１２０−１，１２０−２，および１２０−３を含む分散型マルチマスタデータ複製システム（たとえばファイルシステム１４０）に対してリファレンスが作られ得る。ストレージクラスタ１２０−１がクラスタID（01）を有する開始クラスタであると想定する。ストレージクラスタ１２０−２および１２０−３は、それぞれ「02」および「03」のクラスタIDを有する別々のストレージクラスタである。
【００５０】
オブジェクトのメタデータにファイナライズ開始メッセージが加えられ得る（ブロック８００）。たとえば、開始クラスタ１２０−１（たとえばチャンク処理ロジック４２０）が、開始クラスタ１２０−１に記憶されたグローバルインデックスの複製内のオブジェクトのメタデータに「FinStarted:01」を加え得る。グローバルインデックスに対する如何なる更新と同様に、ファイナライゼーション開始メッセージは、最終的には、分散型マルチマスタデータ複製システム内の他のストレージクラスタ（たとえばストレージクラスタ１２０−２および１２０−３を含む）におけるすべてのグローバルインデックスの複製に伝搬し得る。
【００５１】
クライアントにサクセスコードが送られ得る（ブロック８１０）。たとえば、開始クラスタ１２０−１が、オブジェクトのアップロードを開始したクライアント１１０にサクセスコードを送り得る。サクセスコードは、オブジェクトのすべてのチャンクが成功裏にアップロードされ、クライアント１１０の観点からアップロード処理が完了したことを示し得る。
【００５２】
各クラスタにおいて、グローバルインデックスの非同期的なスキャンニング動作が実行され得る（ブロック８２０）。たとえば、ストレージクラスタ１２０−１，１２０−２，および１２０−３のいずれもが、それらのそれぞれのグローバルインデックスの複製のすべてもしくは一部に対して、スキャンおよび／または書込を定期的に実行し得る。スキャンニング動作は図９に関してさらに述べられる。
【００５３】
図９は、ここで説明される実施例に従う、ストレージクラスタにおけるスキャンニング動作を実行するための例示の処理のフローチャートである。１つの実施例において、処理はストレージクラスタ１２０のうちのいずれか（たとえばストレージクラスタ１２０−１，１２０−２，または１２０−３）によって実行され得る。分散型マルチマスタデータ複製システム内の各ストレージクラスタ１２０は、アップロードされたオブジェクトのファイナライゼーションが完了するまで処理を非同期的に実行し得る。図９のプロセスの特定の例において、３つのストレージクラスタ、すなわちストレージクラスタ１２０−１，１２０−２，および１２０−３を含む分散型マルチマスタデータ複製システム（たとえばファイルシステム１４０）に対してリファレンスが作られ得る。ストレージクラスタ１２０−１が「01」のクラスタIDを有する開始クラスタであると想定する。ストレージクラスタ１２０−２および１２０−３は、それぞれ「02」および「03」のクラスタIDを有する別々のストレージクラスタである。
【００５４】
グローバルインデックスの複製のスキャンが開始され得る（ブロック９００）。たとえば、ストレージクラスタ１２０−２が、ストレージクラスタ１２０−２内に記憶されたグローバルインデックスのレプリカのオフラインスキャンを実行し得る。スキャンは、ストレージクラスタ１２０−２内のすべてのインデックスエントリを検査し得る。
【００５５】
テンポラリIDによって鍵付けされたエントリがファイナライズ開始メッセージを有するかどうかが判断される（ブロック９１０）。たとえば、ストレージクラスタ１２０−２は、テンポラリIDによって鍵付けされ、別のストレージクラスタ（たとえばストレージクラスタ１２０−１）からのファイナライズ開始メッセージ（たとえば「FinStarted:01」）を含む、グローバルインデックスの複製内のオブジェクトに遭遇し得る。テンポラリIDによって鍵付けされたエントリがファイナライズスタートメッセージを有さない場合（ブロック９１０−NO）、スキャンを継続するか、あるいはグローバルインデックスの複製の別のスキャンを最終的に開始するために処理はブロック９００に戻り得る。
【００５６】
テンポラリIDによって鍵付けされたエントリがファイナライズ開始メッセージを有する場合（ブロック９１０−YES）、スキャンを実行したストレージクラスタに対してオブジェクトロックメッセージが既に存在していなければ、オブジェクトメッセージデータにオブジェクトロックメッセージが加えられ得る（ブロック９２０）。たとえば、ストレージクラスタ１２０−２内のスキャンによって、テンポラリIDによって鍵付けされたエントリにおいて「FinStarted:01」が見出された場合、ストレージクラスタ１２０は、ストレージクラスタ１２０−２内のグローバルインデックスの複製内のオブジェクトのメタデータに「FinSealed:02」を加え得る。「FinSealed」メッセージが存在することによって、対応するストレージクラスタの別のシステムコンポーネントは、オブジェクトのバイトを更新するような如何なる変更（付加、更新、削除）も禁止される。
【００５７】
分散型マルチマスタデータレプリカシステムにおけるすべてのストレージクラスタからのオブジェクトロックメッセージを、テンポラリIDによって鍵付けされたエントリが有するかどうかが判断される（ブロック９３０）。たとえば、開始クラスタ１２０−１は、テンポラリIDによって鍵付けされ、分散型マルチマスタデータ複製システムにおけるすべてのストレージクラスタから（たとえばストレージクラスタ１２０−１，１２０−２および１２０−３から）のオブジェクトロックメッセージ（たとえば「FinSealed:01」、「FinSealed:02」、「FinSealed:03」）を含む、グローバルインデックスの複製内のオブジェクトに遭遇し得る。テンポラリIDによって鍵付けされたエントリが、すべてのストレージクラスタからのオブジェクトロックメッセージを有さない場合（ブロック９３０−NO）、プロセスは、スキャンを継続するためあるいは、最終的にはグローバルインデックスの複製の別のスキャンを開始するために、ブロック９００に処理が戻り得る。
【００５８】
テンポラリIDによって鍵付けされたエントリがすべてのストレージクラスタからのオブジェクトロックメッセージを有する場合（ブロック９３０−YES）、既に存在していなければ、パーマネントIDエントリと、パーマネントIDへのコピーリファレンスとが加えられ得る。たとえば、開始クラスタ１２０−１内のスキャンによって、テンポラリIDによって鍵付けされたエントリにおいてすべてのストレージクラスタ（たとえば、すべてのストレージクラスタに対するオブジェクトロックメッセージ（たとえば「FinSealed:01」、「FinSealed:02」、「FinSealed:03」）が見出されると、ストレージクラスタ１２０−１（たとえばチャンク処理ロジック４２０）は、オブジェクトに対してコンテンツハッシュを演算し、コンテンツハッシュに基づいてパーマネントオブジェクトIDを作成し得る。そして、ストレージクラスタ１２０−１は、ストレージクラスタ１２０−１内のオブジェクトのメタデータに「FinRefCopy:PermID」を加え得る（PermIDはコンテンツハッシュに基づいて新しく作成されたパーマネントIDである）。「FinRefCopy:PermID」メッセージの存在により、オブジェクトのメタデータと共に記憶されたリファレンスに加えて、別のストレージクラスタ（たとえばストレージクラスタ１２０−２および１２０−３）内のオブジェクトのバイトに対する如何なる変更（たとえば付加、更新、削除）が、別のシステムコンポーネントに対して禁止され得る。
【００５９】
テンポラリIDによって鍵付けされたエントリが、パーマネントIDへのコピーリファレンスを有するかどうかが判断される（ブロック９５０）。たとえば、任意のストレージクラスタ１２０（たとえばストレージクラスタ１２０−１，１２０−２，または１２０−３のうちのいずれか）は、テンポラリIDによって鍵付けされ、コピーリファレンスメッセージ（たとえば「FinRefCopy:PermID」）を含む、グローバルインデックスの複製中のオブジェクトに遭遇し得る。テンポラリIDによって鍵付けされたエントリがパーマネントIDへのコピーリファレンスを有さない場合（ブロック９５０−NO）、スキャンを継続するためあるいは最終的にはグローバルインデックスの複製の別のスキャンを開始するために、処理はブロック９００に戻り得る。
【００６０】
テンポラリIDによって鍵付けされたエントリがパーマネントIDへのコピーリファレンスを有する場合（ブロック９５０−YES）、テンポラリIDエントリ中のオブジェクトリファレンスがパーマネントIDエントリにコピーされ得、既に存在していなければ、コピー済メッセージが加えられ得る（ブロック９６０）。たとえば、ストレージクラスタ１２０−２のスキャンによって、テンポラリIDによって鍵付けされたエントリ中に「FinRefCopy:PermID」が見出された場合、ストレージクラスタ１２０−２は、テンポラリIDエントリ中に列挙されたすべてのオブジェクトリファレンスを対応するパーマネントIDによって鍵付けされたエントリにコピーし得る。一旦コピーが完了すると、ストレージクラスタ１２０−２は、ストレージクラスタ１２０−２において、テンポラリIDによって鍵付けされたエントリに「FinRefCopyDone:02」を加え得る。
【００６１】
テンポラリIDによって鍵付けされたエントリが、すべてのクラスタからのコピー済メッセージを有するかどうかが判断される（ブロック９７０）。たとえば、開始クラスタ１２０−１は、テンポラリIDによって鍵付けされ、分散型マルチマスタデータ複製システム中のすべてのストレージクラスタからの（たとえばストレージクラスタ１２０−１，１２０−２および１２０−３からの）コピー済メッセージ（たとえば「FinRefCopyDone:01」、「FinRefCopyDone:02」、「FinRefCopyDone:03」）を含む、グローバルインデックスの複製中のオブジェクトに遭遇し得る。テンポラリIDによって鍵付けされたエントリがコピー済メッセージ（ブロック９７０−NO）を有さない場合、スキャンを継続するためあるいは最終的にはグローバルインデックスの複製の別のスキャンを開始するために処理はブロック９００に戻り得る。
【００６２】
テンポラリIDによって鍵付けされたエントリがコピー済メッセージを有する場合（ブロック９７０−YES）、テンポラリIDに関連付けられた余剰のメタデータが取り除かれ、ファイナライズ済メッセージが加えられ得る（ブロック９８０）。たとえば、開始クラスタ１２０−１のスキャンにおいて、テンポラリIDによって鍵付けされたエントリ中のすべてのストレージクラスタに対する「FinRefCopyDone」（たとえば「FinRefCopyDone:01」、「FinRefCopyDone:02」、「FinRefCopyDone:03」）が見出された場合、開始クラスタ１２０−１は、テンポラリIDによって鍵付けされたエントリから、ファイナライズ開始（「FinStarted」）、オブジェクトロック（「FinSealed」）、コピーリファレンス（「FinRefCopy」）メッセージおよびコピー済（「FinRefCopyDone」）メッセージのすべてを取除き得る。テンポラリIDによって鍵付けされたエントリから対応する（たとえばオブジェクトに対するコンテンツハッシュに基づく）パーマネントIDによって鍵付けされたエントリへのパーマネントクロスリファレンスを提供するため、開始クラスタは、「FinDone:PermID」も加え得る。なお、ファイナライゼーション処理は、テンポラリIDに対する既存のオブジェクトリファレンスの有効性に何ら影響を与えない。余剰のメタデータの除去によりアップロードされたオブジェクトに対するファイナライゼーション処理が完了し得る。処理は、スキャンを継続するため、あるいは最終的にはグローバルインデックスの複製の別のスキャンを開始するためにブロック９００に戻り得る。
【００６３】
別の実施例において、クライアント（たとえばクライアント１１０）がアップロード処理の開始に先立って事前にパーマネントオブジェクトIDを演算する場合、上記の処理は最適化され得る。この変形例において、新しいパーマネントIDにより鍵付けされたエントリへのリファレンス（たとえば「FinRefCopy」メッセージ）のコピーは省略される。代わりに、開始クラスタ１２０は、すべてのストレージクラスタ１２０から「FinSealed」メッセージが一旦受取られると、単に、ファイナライズされたものとしてアップロードされたオブジェクトに印を付け得る。なお、この変形例におけるテンポラリIDはパーマネントIDと同じである。
【００６４】
図１０は、複製されたストレージクラスタのグローバルインデックスに新しいオブジェクトリファレンスを加えるための例示の処理１０００のフローチャートを提供する。一般的に、テンポラリIDによって鍵付けされたインデックスエントリにリファレンスを加えようとする、分散型マルチマスタデータ複製システム中のシステムコンポーネントのいずれもが、最初に、そのエントリ内にコピーリファレンスメッセージが存在するかどうかをチェックする。コピーリファレンスメッセージが見つけられた場合、対応するパーマネントIDによって鍵付けされたエントリに対して新しいリファレンスが代わりに加えられる。１つの実施例において、ストレージクラスタ１２０のうちのいずれか１つ（たとえばストレージクラスタ１２０−１，１２０−２または１２０−３）によって、処理が実行され得る。分散型マルチマスタデータ複製システム中の各ストレージクラスタ１２０は、各ストレージクラスタ１２０において新しいリファレンスが複製されるまで、処理を非同期的に実行し得る。
【００６５】
テンポラリIDによって鍵付けされたオブジェクトに対するリファレンス要求が受信され得る（ブロック１０１０）。たとえば、ストレージクラスタ１２０−１は、「TempID3」というテンポラリIDによって鍵付けされたインデックスエントリに新しいリファレンス（たとえばアップロードされたがまだファイナライズされていないオブジェクトに基づくリファレンス）を加えるという要求を受信し得る。
【００６６】
テンポラリIDによって鍵付けされたエントリがパーマネントIDに対するクロスリファレンスを有するかどうかが判断され得る（ブロック１０２０）。たとえば、ストレージクラスタ１２０１は、エントリ中において「FinRefCopy」メッセージまたは「FinDone」メッセージのいずれかを識別子するために、「TempID3」によって鍵付けされたエントリをスキャンし得る。テンポラリIDによって鍵付けされたエントリがパーマネントIDに対するクロスリファレンスを有する場合（ブロック１０２０−YES）、パーマネントIDによって鍵付けされたエントリにリファレンスが加えられ得る（ブロック１０３０）。たとえば、ストレージクラスタ１２０−１は、「FinRefCopy:PermID4」メッセージを識別し、「PermID4」によって鍵付けされたエントリに新しいリファレンスを加え得る。テンポラリIDによって鍵付けされたエントリがパーマネントIDに対するクロスリファレンスを有さない場合（ブロック１０２０−NO）、テンポラリIDによって鍵付けされたエントリにリファレンスが加えられ得る（ブロック１０４０）。たとえば、「FinRefCopy」メッセージも「FinDone」メッセージも見つからなかった場合、ストレージクラスタ１２０−１は、「TempID3」によって鍵付けされたエントリに新しいリファレンスを加え得る。
【００６７】
例
図１１は、ここで説明される実施例に従う、例示のグローバルインデックスの複製の一部１１００を提供する。インデックスは、コンテンツハンドル欄１１１０とファイナライゼーション記録欄１１２０とを含み得る。オブジェクトリファレンスやチャンクのメタデータ（図示せず）などの別の情報もグローバルインデックスの複製に含まれ得る。コンテンツハンドル欄１１１０とファイナライゼーション記録欄１１２０とは、明瞭にするために部分１１００において示される。別の実施例において、グローバルインデックスの複製中のファイナライゼーション記録は、別の記録と混ぜられ、コラムを用いてあるいは用いずに、分離記号（たとえばカンマ、スペースなど）によって区別される。別のデータ構造もグローバルインデックスの複製に対して用いられ得る。
【００６８】
例示のインデックスの複製の一部１１００において、分散型マルチマスタデータ複製システムが３つのストレージクラスタXX，YYおよびZZを含むと想定する。ファイナライゼーションアルゴリズムはストレージクラスタXX，YYおよびZZの各々において定期的に実行され得、グローバルインデックスのすべてあるいは一部をスキャンし得る。また、ストレージクラスタXX，YYまたはZZのうちの１つによって、特定のオブジェクトコンテンツハンドルに関連付けられたグローバルインデックスのレプリカに対してメッセージ（たとえばFinStarted、FinSealed、FinRefCopyおよびFinRefCopyDone）が書込まれ得る。グローバルインデックスに対する変更は、別の加わっているクラスタのすべて（たとえばストレージクラスタXX，YYおよびZZの残り）に対して複製され得る。
【００６９】
図１１に示されるように、インデックスの部分１１００は、コンテンツハンドルと、３つのオブジェクトに対する関連するファイナライゼーション記録とを含む。「TempID06」によって鍵付けされた行１１３０は、「TempID06」に関連付けられたオブジェクトに対して、開始クラスタXXによってファイナライズ処理が開始されたことを示す記録を有する。行１１３０もまた、ストレージクラスタXXにおいてオブジェクトがロックされたことを示す記録（すなわち「FinSealed:XX」）、ストレージクラスタYYにおいてオブジェクトがロックされたことを示す記録（すなわち「FinSealed:YY」）およびストレージZZにおいてオブジェクトがロックされたことを示す記録（すなわち「FinSealed:ZZ」）を含む。開始クラスタXXは、分散型マルチマスタデータ複製システムにおけるすべてのストレージクラスタに対して「FinSealed」メッセージを識別し、「TempID06」に対応するオブジェクトのすべてのバイトがXX、YYおよびZZにアップロードされたことを確認したため、オブジェクトに対してコンテンツハッシュすなわち（「PermID07」）を演算する。したがって、ストレージクラスタXXは、行１１３０内のファイナライゼーション記録に「FinRefCopy:PermID07」を加え、行１１３０からのオブジェクトリファレンスを含む「PermID07」によって鍵付けされた新しい行１１５０を作成する。ストレージクラスタXXがコピー処理を完了したことを示すために、コピー済メッセージ（すなわち「FinRefCopyDone:XX」）も行１１３０に含まれる。一旦、別のストレージクラスタYYおよびZZから「FinRefCopyDone」メッセージが提供され（そして開始クラスタXXに複製され）ると、余剰のメッセージデータ（すなわち「FinStarted:XX」、「FinSealed:XX」、「FinSealed:YY」、「FinSealed:ZZ」、「FinRefCopy:PermID07」、「FinRefCopyDone:XX」および別の「FinRefCopyDone」メッセージ）が開始クラスタXXによって削除され得る。そして残りのクラスタに削除が複製される。
【００７０】
「TempID08」によって鍵付けされた行１１４０は、「TempID08」に関連付けられたオブジェクトに対してファイナライズ処理が完了したことを示す記録を有する。ファイナライゼーション処理からの余剰データは削除され、ファイナライゼーション記録にはパーマネントIDへのクロスリファレンス（すなわち「FinDone:PermID09」）のみが残る。「PermID09」によって鍵付けされた新しい行１１６０は、行１１４０からのオブジェクトリファレンスを含む。
【００７１】
上記の実施例に示されるように、ここで説明されたシステムおよび方法は、テンポラリIDから新しいパーマネントIDへの最終的な転移の完了を保証する。
【００７２】
オブジェクトのテンポラリIDのもとにこれまで記録されたすべてのリファレンスは、オブジェクトのパーマネントIDのもとでコピーされ得、将来的にオブジェクトのテンポラリIDのもとで新しいリファレンスが記録されることはない。
【００７３】
結論
ここで説明されたシステムおよび／または方法は、コンテンツを指定可能なストレージクラスタにおける複製された使用のための非同期的分散オブジェクトアップロードアルゴリズムを組込み得る。アルゴリズムは、オブジェクトを含むチャンクの位置を含むインデックスを複製するために、下層のデータ複製層を用いる。チャンクは、オブジェクトが明確にファイナライズされるまで徐々に異なるクラスタにアップロードされ得る。すべてのチャンクがアップロードされた後、オブジェクトがコンテンツ指定可能インデックスシステムに挿入され得る。
【００７４】
実施例の前述の説明は、解説と説明を提供するが、完全なものであることや開示された形式通りに発明を限定することを意図するものではない。上記の教示を踏まえて修正および変更が可能であり、または発明の実施から理解される。
【００７５】
たとえば、別の実施例において、異なるストレージクラスタが、分散型データ複製システム内で複製層を用いるよりも、むしろ、直接的に通信するファイナライゼーションアルゴリズムの同期的なバージョンが用いられ得る。
【００７６】
また、図６〜１０に関して一連のブロックが説明されたが、別の実施例においてブロックの順番を変更してもよい。さらに、非従属のブロックが平行的に実行され得る。
【００７７】
ここで説明されるように、実施の形態が、図において記載された実施例においてソフトウェア、ファームウェアおよびハードウェアの多くの異なる形式で実現され得ることが明らかである。ここで説明された実施の形態を実現するために用いられる実際のソフトウェアコードまたは専用の制御ハードウェアは発明を限定するものではない。したがって、実施の形態の作動および挙動は特定のソフトウェアコードを参照することなしに説明された。ソフトウェアおよび制御ハードウェアはここでの説明に基づく実施の形態を実現するために設計され得ることが理解される。
【００７８】
さらに、ここで説明されたある実施例は１つ以上の機能を実行する「ロジック」または「コンポーネント」として実現され得る。このロジックまたは「コンポーネント」は、プロセッサ、マイクロプロセッサなどのハードウェア、アプリケーション特有の集積回路、または、フィールドプログラマブルゲートアレイ、あるいはハードウェアとソフトウェアとの組合せ（たとえばソフトウェア、プロセッサにより実行されるソフトウェア）を含み得る。
【００７９】
この明細書において用いられるときの「含む」という用語は、述べられた特徴、整数、ステップ、または構成要素が存在することを特定するものとされるが、１つ以上の別の特徴、整数、ステップ、構成要素またはそれらの組の存在または付加を妨げるものではない。
【００８０】
特許請求の範囲および／または明細書中の開示において特定の特徴の組合せが記載されているが、これらの組合せは、発明の開示を限定することを意図するものではない。実際に、特許請求の範囲および／または明細書中の開示において具体的には記載されていない方法で、これらの特徴の多くが組み合わせられ得る。
【００８１】
本明細書の説明において用いられる要素、動作、または命令は、明確に記載されない限り、発明にとって重要であり不可欠なものとして解釈されるべきではない。また、ここで用いられるように、「ある」という冠詞は１つ以上の品目を含む。１つだけの品目が意図される場合、「１つ」という用語または類似の言葉が用いられる。さらに、「基づく」という表現は、ここで用いられるように、明確に述べられない限り、「少なくとも部分的に基づく」ことが意図される。
【図１】
0005433074.tif 000002
【図２】
0005433074.tif 000003
【図３】
0005433074.tif 000004
【図４】
0005433074.tif 000005
【図５】
0005433074.tif 000006
【図６】
0005433074.tif 000007
【図７】
0005433074.tif 000008
【図８】
0005433074.tif 000009
【図９】
0005433074.tif 000010
【図１０】
0005433074.tif 000011
【図１１】
0005433074.tif 000012