複製されたコンテンツアドレス可能ストレージクラスタのための非同期分散型重複排除
分散型データ複製システムにおける装置群のうちの1つの装置によって、方法が実行される。方法は、分散型データ複製システムにおけるオブジェクトのインデックスを記憶することを含み、そのインデックスは、オブジェクトが、分散型データ複製システム内の複数の装置によって局部的に記憶される間に複製される。方法は、また、インデックスの少なくとも一部のスキャンを実行すること、およびそのインデックスのスキャンに基づいて、オブジェクトの少なくとも1つのの冗長な複製を識別することを含む。方法は、さらに、冗長な複製を重複排除すること、および冗長な複製の状態を反映するためにインデックスを更新することを含む。
【発明の詳細な説明】
【背景技術】
【0001】
背景
企業コンピューティングランドスケープは、中央サービスアーキテクチャが分散型ストレージクラスタへ移行したという点で、ストレージアーキテクチャにおいて抜本的な変化をもたらした。ビジネスは記憶効率を増加するための手法を模索しているので、汎用コンピュータから構築されるストレージクラスタは、新しいデータ量の多いアプリケーションのための高い性能、利用可能性、およびスケーラビリティを、モノリシックディスクアレイと比較して、わずかなコストで供給し得る。ストレージクラスタの全潜在能力を解き放つために、データは複数の地理的位置にわたって複製され、それによって、利用可能性を増大させるとともに、クライエントからのネットワーク距離を低減する。
【発明の概要】
【発明が解決しようとする課題】
【0002】
データの重複排除は、重複オブジェクトを識別し、重複を除去することによって必要とされる記憶空間を低減し得る。結果として、データ重複排除は、ストレージ産業について非常に重要となりつつあり、多くの重複を含み得る大規模システムの必要性によって促進されつつある。
【課題を解決するための手段】
【0003】
要約
1つの実行例によれば、方法は、分散型データ複製システムにおける、装置群のうちの1つの装置によって実行され得る。方法は、分散型データ複製システムにおいて、オブジェクトのインデックスを記憶することを含み、オブジェクトの複製が分散型データ複製システムにおける複数の装置によって局部的に記憶される間に、そのインデックスが複製される。方法は、そのインデックスの少なくとも一部のスキャンを実行すること、および、インデックのスキャンに基づいて、オブジェクトの少なくとも1つの冗長な複製を識別することも含み得る。方法は、さらに、インデックスの一部に重複排除レコードを書き込むことによって、冗長な複製の重複排除を行なうことを含み得る。
【0004】
他の実行例によれば、分散型データ複製システムにおける装置群のうちの1つの装置は、分散型データ複製システムにおけるオブジェクトのインデックスを記憶するための手段と、インデックスの変化を書き込んでオブジェクトのうちの1つの複製の状態を指定するための手段と、そのインデックスへの変化を分散型データ複製システムにおける複数の装置に複製するための手段と、インデックスの少なくとも一部のスキャンを実行するための手段と、インデックスのスキャンに基づいてオブジェクトのうちの1つの冗長な複製を識別するための手段と、冗長な複製を重複排除するための手段とを含み得る。
【0005】
さらに他の実行例によれば、システムは、指令、オブジェクトのデータストア、およびオブジェクトのインデックスを記憶するためのメモリと、プロセッサとを含み得る。プロセッサは、メモリ内の指令を実行して、データストア内のオブジェクトの状態を識別し、その状態は、オブジェクトが複製を有しているか否か、および削除リクエストがそのオブジェクトに関連しているか否かに関連し、プロセッサは、オブジェクトの状態に基づいて重複排除指示レコードをそのインデックスに書き込み、その重複排除指示レコードを伴うインデックスを1つまたはより多くの装置に複製し、その1つまたはより多くの装置から、そのオブジェクトに関連する他の重複排除指示レコードを受信し、重複排除指示レコードおよび他の重複排除指示レコードは、そのオブジェクトの1つまたはより多くの複製の削除のための基準を提供する。
【0006】
さらに他の実行例によれば、1つまたより多くの装置によって実行される方法は、分散型データ複製システムにおける複数の装置内のオブジェクトのインデックスを記憶すること、およびそのオブジェクトを局部的に記憶する間に、分散型データ複製システムを通してそのインデックスを複製することを含み、各装置はそのインデックスの特定のサブセットにおけるオブジェクトの重複排除に関与し、方法は、そのインデックスのサブセットの各々のスキャンを実行してそのスキャンに基づいて冗長な複製を識別すること、その冗長を重複排除すること、および進行中の削除リクエストを有する複製を伴う装置からのオブジェクトを、以前に重複排除された複製を伴う装置に自動的にコピーすることをさらに含み得る。
【0007】
さらなる実行例によれば、コンピュータ読取可能メモリは、コンピュータ実行可能指令を含み得る。コンピュータ読取可能メモリは、分散型データ複製システムにおけるオブジェクトのインデックスの一部のスキャンを実行するための1つまたはより多くの指令と、そのインデックスの一部のスキャンに基づいてオブジェクトのうちの1つの複製の冗長な複製を識別するための1つまたはより多くの指令と、その冗長な複製を重複排除するための1つまたはより多くの指令とを含み得る。
【0008】
図面の簡単な説明
添付の図面は、この明細書に含まれるとともにこの明細書の一部を成し、明細書に記載される1つまたはより多くの実施形態を例示し、その記述とともに、これらの実施形態を説明する。
【図面の簡単な説明】
【0009】
【図1】本明細書に記載される方法およびシステムが実現され得る例示的なネットワークの図である。
【図2】図1のファイルシステムの例示的な構成を示す図である。
【図3】図1のストレージクラスタの例示的な要素を示す図である。
【図4】図1の例示的なストレージクラスタの機能ブロック図である。
【図5】分散型マルチマスタデータ複製システムのインデックスにおいて用いられ得る、例示的なレコード構造を示す図である。
【図6A】クライエント起動されるアップロード/削除動作を管理するための例示的なプロセスのフローチャートである。
【図6B】クライエント起動されるアップロード/削除動作を管理するための例示的なプロセスのフローチャートである。
【図7】分散型マルチマスタデータ複製システムにおける重複排除を実行するための例示的なプロセスのフローチャートである。
【図8】削除リクエストを管理するための例示的なプロセスのフローチャートである。
【図9】重複した複製を除去するための例示的なプロセスのフローチャートである。
【図10】分散型マルチマスタデータ複製システムにおいて、バンド幅消費を最適化するとともに時間遅れを低減するための例示的なプロセスのフローチャートである。
【図11】本明細書に記載された実行例に従う、例示的なグローバルインデックスの一部を示す図である。
【発明を実施するための形態】
【0010】
詳細な説明
以下の詳細な説明は、添付の図面を参照する。異なる図面における同じ参照番号は、同じまたは類似の要素を特定し得る。また、以下の詳細な説明は、本発明を限定するものではない。
【0011】
本明細書に記載されるシステムおよび/または方法は、不変オブジェクト(immutable object)についての利用可能性、活性(liveness)および一貫性保証を提供する複製されたストレージクラスタのための、非同期分散型重複排除アルゴリズムを提供し得る。本明細書に記載される実行例は、分散型マルチマスタデータ複製システムの下部複製層を用いて、異なるストレージクラスタ間のコンテンツアドレス可能インデックス(本明細書においては、「グローバルインデックス」とも称する。)を複製し得る。グローバルインデックスの各オブジェクトは、固有のコンテンツ処理(たとえば、ハッシュ値またはデジタル署名)を有し得る。本明細書に記載される実行例においては、冗長な複製の除去プロセスが、少なくとも1つの活性中の複製を保持し得る。
【0012】
例示的なネットワーク構成
図1は、本明細書において説明されるシステムおよび方法が実行され得る例示的なシステム100の図である。システム100は、ネットワーク130を介して接続される、クライエント110−1〜110−N(総称してクライエント110、および個々にクライエント110とも称する。)およびストレージクラスタ120−1〜120−M(総称してストレージクラスタ120、および個々にストレージクラスタ120とも称する。)を含む。ストレージクラスタ120は、(図1の点線によって示されるような)ファイルシステム140を形成する。
【0013】
ネットワーク130は、ローカルエリアネットワーク(local area network:LAN)、広域ネットワーク(wide area network:WAN)、電話回線ネットワーク(たとえば、公衆交換電話網(Public Switched Telephone Network:PSTN))、イントラネット、インターネット、類似または非類似ネットワーク、あるいはネットワークの組み合わせのような、1つまたはより多くのネットワークを含み得る。クライエント110およびストレージクラスタ120は、有線または無線接続を介してネットワーク130と接続し得る。
【0014】
クライエント110は、パーソナルコンピュータ、無線電話、携帯情報端末(personal digital assistant:PDA)、ラップトップ、または他のタイプの通信装置、および/または、これらの装置のうちの1つにおいて実行されるスレッドまたはプロセスのような、1つまたはより多くのタイプの装置を含み得る。一実行例においては、クライエント110は、そのクライエント110に代わってファイルデータを読出しまたは修正する(たとえば、書き込む)ためにストレージクラスタ120と通信するアプリケーションを含み、あるいはアプリケーションにリンクされる。
【0015】
ストレージクラスタ120は、本明細書で説明される態様で情報を記憶し、処理し、検索し、およびまたは提供し得る1つまたはより多くのサーバ装置、あるいは、他のタイプのコンピュータまたは通信装置を含み得る。一実行例においては、ストレージクラスタ120は、ファイルに対して、大規模でランダムな読出し/書込みアクセスデータストアを維持することが可能な、1つまたはより多くのサーバ(たとえば、コンピュータシステムおよび/またはアプリケーション)を含み得る。ストレージクラスタ120のデータストアは、変化が生じた場合に、インデキシングシステムが迅速にインデックスの一部を更新することを許可し得る。ストレージクラスタ120のデータストアは、1つまたはより多くのテーブル(たとえば、ユニフォームリソースロケータ(uniform resource locator:URL)ごとに1つの列を含む文書テーブル、URL以外の値によって検索される補助テーブルなど)を含み得る。一例においては、ストレージクラスタ120は、非常に大規模(たとえば、数千のサーバにわたるペタバイトのデータ)に設計され得る構造データ(たとえば、文書のランダムアクセスストレージクラスタ)を管理するための、分散型記憶システム(たとえば、チャン(Chang)らによって書かれた「ビッグテーブル:構造データ用の分散型記憶システム(Bigtable: A Distributed Storage System for Structured Data)」、第7回OSDI会報、205〜218ページ(2006年11月)における「ビッグテーブル(Bigtable)」)に含まれ得る。
【0016】
図1には示されていないが、システム100は、1つまたはより多くの専用の民生サーバまたはハブのような、多数の他の要素を含み得る。民生サーバは、たとえば、クライエント110によるアクセスのために、1つまたはより多くのストレージクラスタ120からのデータストアの読出し専用コピーを記憶し得る。ハブは、たとえば、1つまたはより多くの民生サーバへ分配するために、1つまたはより多くのストレージクラスタ120からのデータストアの読出し専用コピーを記憶し得る。
【0017】
例示的なストレージクラスタ構造
図2は、ファイルシステム140の例示的構成の図である。図2に示されるように、ファイルシステム140は、ストレージクラスタ120−1、120−2、120−3、および120−4を含み得る。一実行例においては、ファイルシステム140は、分散型マルチマスタデータ複製システムであり、ストレージクラスタ120−1、120−2、120−3、および120−4の各々は、他のストレージクラスタについてのマスタサーバとして動作し得る。ファイルシステム140においては、データは、(たとえば、複数の地理的場所において)ストレージクラスタ120−1、120−2、120−3、および120−4にわたって複製され、データ利用可能性を増加するとともにクライエント(たとえば、クライエント110)からのネットワーク距離を低減し得る。一般的に、分散型オブジェクトおよび参照は、異なるストレージクラスタ120において、動的に生成され、変化され、模造され、そして削除され得、下部データ複製層(図示せず)は、書込み順の忠実性を維持して、すべてのストレージクラスタ120が同じデータのバージョンに至ることを保証する。したがって、データ複製層は、単一のオブジェクトについての同じ複製についての書込み順を遵守する。
【0018】
分散型マルチマスタデータ複製システムにおけるすべてのオブジェクトのグローバルインデックスは、各ストレージクラスタ120に関連し得る。各記憶されたオブジェクトは、グローバルインデックスにおいて、(ハッシュ値、デジタル署名などのような)固有のコンテンツ処理によってリスト化され得る。選択されたストレージクラスタは、各々、グローバルインデックスにおけるコンテンツ処理の個別の領域に関与するように割り当てられ得る。たとえば、単一のストレージクラスタ120は、特定のコンテンツ処理に関連するオブジェクトの重複排除に関与し得る。1つのストレージクラスタによってなされたグローバルインデックスへの変更は、他のストレージクラスタに複製され得る。
【0019】
図2は、ファイルシステム140の例示的な機能要素を示すが、他の実行例においては、ファイルシステム140は、図2に記載されているよりも、より少ない要素、追加的な要素、異なる要素、または異なった配置の要素を含み得る。さらの他の実行例においては、ファイルシステム140の1つまたはより多くの要素は、ファイルシステム140の1つまたはより多くの要素によって実行されるものとして記述された1つまたはより多くのタスクを実行し得る。
【0020】
図3は、ストレージクラスタ120の例示的な要素の図である。ストレージクラスタ120は、バス310と、プロセッサ320と、メインメモリ330と、読み取り専用メモリ(ROM)340と、記憶装置350と、入力装置360と、出力装置370と、通信インターフェース380とを含み得る。バス310は、ストレージクラスタ120の要素間の通信を許可する、1つまたはより多くの導体を含み得る。
【0021】
プロセッサ320は、指令を解釈して実行し得る、任意のプロセッサまたはマイクロプロセッサを含み得る。メインメモリ330は、プロセッサ320によって実行される情報および指令を記憶し得る、ランダムアクセスメモリ(RAM)または他のタイプのダイナミック記憶装置を含み得る。ROM340は、プロセッサ320による使用のための、静的情報および指令を記憶し得る、ROM装置または他のタイプのスタティック記憶装置を含み得る。記憶装置350は、磁気およびまたは光記録媒体、ならびにそれに対応するドライブを含み得る。たとえば記憶装置350は、持続性記憶を提供する1つまたはより多くのローカルディスクを含み得る。一実行例においては、ストレージクラスタ120は、ファイルシステム140に記憶されたオブジェクトのためのメタデータを、メインメモリ330および/または記憶装置350のような1つまたはより多くのコンピュータ読取可能媒体内に維持し得る。たとえば、ストレージクラスタ120は、分散型マルチマスタデータ複製システムにおいて記憶されたすべてのオブジェクトのために、記憶装置350内にグローバルインデックスを記憶し得る。
【0022】
入力装置360は、キーボード、キーパッド、ボタン、マウス、ペンなどのような、操作者がストレージクラスタ120に情報を入力することを許可する1つまたはより多くの機構を含み得る。出力装置370は、ディスプレイ、発光ダイオード(light emitting diode:LED)などを含む、操作者に情報を出力する1つまたはより多くの機構を含み得る。通信インターフェース380は、ストレージクラスタ120が、他の装置および/またはシステムと通信できるようにする、任意の送受信機のような機構を含み得る。たとえば、通信インターフェース380は、他のストレージクラスタ120および/またはクライエント110と通信するための機構を含み得る。
【0023】
図4は、ストレージクラスタ120の機能ブロック図を示す。図4に示されるように、ストレージクラスタ120は、データストア410および重複排除論理420を含み得る。一実行例においては、図4に示されるように、データストア410が、ストレージクラスタ120内に設けられる。他の実行例においては、データストア410のいくつかまたはすべては、ストレージクラスタ120との通信により、インデックスシステムに関連する外部メモリ装置(図示せず)のような、システム100の1つまたはより多くの装置内に記憶され得る。
【0024】
データストア410は、複製インデックスストア412およびローカルオブジェクトストア414を含み得る。複製インデックスストア412は、分散化マルチマスタデータ複製システムの複製層の一部として含まれ得る。複製インデックスストア412は、グローバルインデックスに関連する情報を記憶し得る。複製インデックスストア412の少なくとも一部は、複数のストレージクラスタ120において複製され得る。各複製インデックスストア412についての複製の数は、ユーザ設定可能であり得る。ローカルオブジェクトストア414は、ストレージクラスタ120において局部的にオブジェクトを記憶し得る。ローカルオブジェクトストア414は、クライエント(たとえば、クライエント110)によってアップロードされた画像またはビデオのような、ファイルを含み得る。
【0025】
複製削除論理420は、分散化マルチマスタデータ複製システム内のストレージクラスタ(たとえば、ストレージクラスタ120−1、120−2、120−3、および120−4)から冗長な複製を除去するための論理を含み得る。各参加ストレージクラスタについての複製削除論理420は、グローバルインデックスの特定のセクションに関与するように割り当てられ得る。たとえば、複製削除論理420は、グローバルインデックスについてのコンテンツ処理の特定の範囲に割り当てられ得る。したがって、分散化マルチマスタデータ複製システム内の1つのストレージクラスタだけが、システム内の複製オブジェクトについての破壊的操作(destructive operation)(たとえば、複製の削除)を実行することができる。
【0026】
重複排除を容易にするために、レコードが重複排除論理420によって生成され、特定のコンテンツ処理に関連するグローバルインデックスの一部に追加され得る。レコードは、たとえば、活性中の複製を起動するための「データ(Data)」指示子、実行中の削除リクエストを示す「削除リクエスト(DeleteRequest)」指示子、および重複排除のために選択された複製を示す「重複排除(Deduped)」指示子を含み得る。レコードフォーマットおよびその使用は、以下でより詳細に説明される。
【0027】
図4は、ストレージクラスタ120の例示的な機能要素を示すが、他の実行例においては、ストレージクラスタ120は、図4に示されたものよりも、より少ない機能要素、追加の機能要素、異なる機能要素、または、異なる配列の機能要素を含み得る。さらに他の実行例においては、ストレージクラスタ120の1つまたはより多くの機能要素は、1つまたはより多くの他の機能要素によって実行されるものとして記述される1つまたはより多くの他のタスクを実行し得る。
【0028】
例示的なレコード構造
図5は、例示的な実行例においてグローバルインデックスに書き込まれ得る、重複排除指示子レコードについての例示的なレコード構造500の図を提供する。重複排除指示子レコードは、オブジェクト複製の特定のコンテンツ処理を有するグローバルインデックスに関連し得る。図5に示されるように、レコード構造500は、ストレージクラスタ識別子(ID)セクション510と、記憶位置セクション520と、指示セクション530とを含み得る。ストレージクラスタ識別セクション510は、レコードが書き込まれるオブジェクト複製を記憶しているストレージクラスタ120についての固有の識別(たとえば、「クラスタID」)を含み得る。位置セクション520は、ストレージクラスタ識別セクション510によって識別されたストレージクラスタ120における複製の位置についてのアドレスを含み得る。指示セクション530は、たとえば、「データ」指示子、「削除リクエスト」指示子、または「重複排除」指示子を含み得る。
【0029】
レコード構造500は、「クラスタID:位置:指示」の形式でリスト化され得る。たとえば、複製のためのレコードは、ストレージクラスタ120−1によって、レコード「01:234523/2000:削除リクエスト」でグローバルインデックスに追加され得、ここで、「01」はストレージクラスタ120−1のクラスタIDであり、「234523/2000」はストレージクラスタ120−1内の複製が記憶される位置であり、「削除リクエスト」は指示子である。ストレージクラスタ120−2における同じオブジェクトの他の複製のレコードは、「02:234544/1000:データ」であり得、ここで、「02」はストレージクラスタ120−2のクラスタIDであり、「234544/1000」はストレージクラスタ120−2における位置であり、「データ」は指示子である。
【0030】
例示的なプロセスフロー
図6Aおよび図6Bは、クライエント起動アップロード/削除動作を管理するための例示的なプロセスのフローチャートである。図6Aは、クライエントからオブジェクトをアップロードする例示的なプロセス600についてのフローチャートを示す。図6Bは、クライエントによって削除されるオブジェクトを除去する例示的なプロセス650についてのフローチャートを示す。一実行例においては、プロセス600および650は、ストレージクラスタ120の1つによって実行され得る。プロセス600および650は、クライエント(たとえば、クライエント110)の動作に応答して実行され得る。以下に説明されるプロセス600および650の特有の例については、参照は、ファイルシステム140のストレージクラスタ120−1に対してなされ、ストレージクラスタ120は、クラスタID「01」を含む。
【0031】
図6Aを参照して、プロセス600は、アップロードファイルが、クライエントから受信されたると開始し得る(ブロック610)。たとえば、ストレージクラスタ120−1は、クライエント110のうちの1つから新しいファイルを受信し得る。アップロードファイルは記憶され(ブロック620)、アップロードファイルについての「データ」指示子がグローバルインデックスに書き込まれ得る(ブロック630)。たとえば、ストレージクラスタ120−1は、メモリ(たとえば、記憶装置350)にアップロードファイルを記憶し、オブジェクトについてのコンテンツ処理をグローバルインデックスに追加し得る。ストレージクラスタ120−1は、また、データレコード(たとえば、「01:位置:データ」)を、オブジェクトのコンテンツ処理によってアドレス指定された、複製されたグローバルインデックスに書き込み得る。
【0032】
図6Bを参照して、プロセス650は、削除ファイルの通知が受信されると開始し得る(ブロック660)。たとえば、ストレージクラスタ120−1は、クライエント110のうちの1つがファイルを削除した指示を受信し得る。削除リクエストが起動され(ブロック670)、削除ファイルについての「削除リクエスト」指示子がグローバルインデックスに書き込まれ得る(ブロック680)。たとえば、ストレージクラスタ120−1は、削除リクエストを起動して、ファイルシステム140から削除ファイルを非同期に除去する。ストレージ装置120−1は、また、オブジェクトのコンテンツ処理によってアドレス指定された、複製グローバルインデックスに、「削除リクエスト」レコード(たとえば、「01:位置:削除リクエスト」)を書き込み得る。
【0033】
図7は、分散型マルチマスタデータ複製システム(たとえば、ファイルシステム140)における重複排除を実行するための例示的なプロセス700のフローチャートである。一実行例においては、プロセス700は、ストレージクラスタ120のうちの1つによって実行され得る。他の実行例においては、プロセス700のいくつかまたはすべてが、ストレージクラスタ120を含むまたは含まない、他の装置または装置群によって実行され得る。プロセス700は、各ストレージクラスタ120において周期的に実行され、ストレージクラスタ120内のオブジェクトのすべてまたは一部のスキャンを含み得る。以下に説明されるプロセス700の特定の例について、参照はファイルシステム140のストレージクラスタ120−1および120−2に対してなされ、ここでストレージクラスタ120−1は「01」のクラスタIDを含み、ストレージクラスタ120−2は「02」のクラスタIDを含む。
【0034】
図7に示されるように、プロセス700は、グローバルインデックスのスキャンの実行で始まり得る(ブロック710)。たとえば、(たとえば、重複排除論理420を用いた)ストレージクラスタ120−2は、グローバルインデックスに列挙されたすべてまたは一部のオブジェクトのスキャンを実行し得る。スキャンは、たとえば、削除のマークが付けられた複数の複製および/またはオブジェクトを識別し得る。
【0035】
削除リクエストに遭遇したか否かが判定され得る(ブロック720)。たとえば、ストレージクラスタ120−1は、グローバルインデックスにおいて、他のストレージクラスタから(たとえば、ストレージクラスタ120−2から)の削除リクエスト指示子(たとえば、「02:位置:削除リクエスト」)を含むオブジェクトに遭遇し得る。削除リクエストに遭遇したと判定された場合(ブロック720−YES)は、削除リクエストが処理され得る(ブロック730)。たとえば、ストレージクラスタ120−1は、図8を参照してより詳細に説明されるように、削除リクエストを処理し得る。
【0036】
削除リクエストに遭遇しなかったと判定された場合(ブロック720−NO)は、冗長な複製が存在するか否かが判定され得る(ブロック740)。冗長な複製は、オブジェクトについての実行中の削除リクエストを有していない、異なる位置における複製されたオブジェクトであり得る。たとえば、ストレージクラスタ120−1は、ストレージクラスタ120−1が関与するコンテンツ処理に対応する、同じオブジェクトについての複数の複製を識別し得る。複数の複製は、たとえば、異なるストレージクラスタ(たとえば、ストレージクラスタ120−1およびストレージクラスタ120−2)または同じストレージクラスタ内の異なる位置に記憶され得る。
【0037】
冗長な複製が存在すると判定された場合(ブロック740−YES)は、冗長な複製は除去され得る(ブロック750)。たとえば、ストレージクラスタ120−1は、図9を参照してより詳細に説明されるように、冗長な複製を除去し得る。冗長な複製が存在しないと判定された場合(ブロック740−NO)は、プロセスはブロック710に戻り、グローバルインデックスの他のスキャンが実行され得る(ブロック710)。
【0038】
図8は、図6のブロック660の削除リクエストの処理に関連した例示的な動作を示す。削除リクエストは、オブジェクトについて見つけられ得る(ブロック810)。たとえば、ストレージクラスタ120−1によって実行されるスキャンは、グローバルインデックス内において、特定のストレージクラスタにおける複製を削除するための、ストレージクラスタ120−1によって事前に書き込まれた削除リクエスト指示子(たとえば、「02:位置:削除リクエスト」)を有するコンテンツ処理を識別し得る。ストレージクラスタ120−1がそのコンテンツ処理に関与すると想定すると、ストレージクラスタ120−1は、動作を適用して、その複製がまさに重複排除され得るか否かを判定する。
【0039】
重複排除指示子が存在するか否かが判定され得る(ブロック820)。たとえば、ストレージクラスタ120−1は、グローバルインデックスにおいてそのコンテンツ処理に関連する他のレコードを調べ、重複排除指示子(たとえば、「02:位置:重複排除」)が存在するか否かを判定する。重複排除指示子が存在すると判定された場合(ブロック820−YES)は、グローバルインデックスにおける複製および関連するレコードが、重複排除され得る(ブロック830)。たとえば、ストレージクラスタ120−1は、削除リクエストを起動して、(もし、あれば)ストレージクラスタ120−2における複製を削除し、その削除された複製についてのコンテンツ処理に関連するすべてのレコード(たとえば、「02:位置:*」、ここで「*」は任意の指示子)をグローバルインデックスから削除する。
【0040】
重複排除指示子が存在しないと判定された場合(ブロック820−NO)は、他の活性中の複製が存在するか否かが判定され得る(ブロック840)。たとえば、ストレージクラスタ120−2は、グローバルインデックスについてのコンテンツ処理を調べて、そのオブジェクトについての他の活性中の複製が存在するか否かを判定する。グローバルインデックスは、たとえば、他のストレージクラスタからのコンテンツ処理についてのデータレコード(たとえば、「03:位置:データ」)を含み得る。
【0041】
他の活性中の複製が存在する場合(ブロック840−YES)は、ブロック830を参照して上記で説明されたように、その複製は重複排除され得る。他の活性中の複製が存在しない場合(ブロック840−NO)は、すべての複製が削除リクエストを有しているか否かが判定され得る(ブロック850)。たとえば、ストレージクラスタ120−1は、グローバルインデックスについてのコンテンツ処理を調べ、そのコンテンツ処理に関連するすべての複製が実行中の削除リクエストを有しているか否かを判定し得る(たとえば、「*:*:削除リクエスト」、ここで、「*」は、それぞれ任意のクラスタIDおよび任意の位置であり得る)。
【0042】
すべての複製が削除リクエストを有していると判定された場合(ブロック850−YES)は、複製は、ブロック830を参照して上記で説明されたように、重複排除され得る。すべての複製が削除リクエストを有してはいないと判定された場合(ブロック850−NO)は、オブジェクトは、削除リクエストを起動したストレージクラスタから異なるストレージクラスタへコピーされ、グローバルインデックスが更新され得る(ブロック860)。たとえば、レコード「02:位置:削除リクエスト」に応答して、ストレージクラスタ120−1は、ストレージクラスタ120−2から、重複排除レコード(たとえば、「03:位置:重複排除」)がありかつ実行中の削除リクエストがない他のストレージクラスタ120−3へオブジェクトをコピーし得る。ストレージクラスタ120−1は、その複製に関連する以前の重複排除レコード(たとえば、「03:位置:重複排除」)を削除し、グローバルインデックスにおいてそのオブジェクトの対応するコンテンツ処理に、データ指示子(たとえば、「03:位置:データ」)を書き込む。
【0043】
図9は、図7のブロック750の、重複参照(duplicate reference)の除去に関連する例示的な動作を示す。削除リクエストを有しない複数の複製が、識別され得る(ブロック910)。たとえば、ストレージクラスタ120−1は、グローバルインデックスを調べて、ストレージクラスタ120−01が関与するコンテンツ処理に対応する実行中の削除リクエストを有しない、2つまたはより多くの複製を識別する。
【0044】
重複排除されるべき複製を決定する基準が、適用され得る(ブロック920)。たとえば、ストレージクラスタ120−1は、ストレージクラスタ120−1内に記憶され得る冗長な複製の重複排除を行なうための基準を適用し得る。冗長な複製を重複排除する基準は、複製の地理的近接性、ストレージクラスタにおける利用可能な記憶容量、または他の要因のような、様々な要因に基づき得る。(たとえば、重複排除論理420を用いる)ストレージクラスタ120−1は、上記識別された、実行中の削除リクエストを有しない2つまたはより多くの複製に、その基準を適用し得る。いくつかの実行例においては、複数の複製が、重複排除されるべきであると識別され得る。他の実行例においては、ストレージクラスタ120−1は、(たとえば、重複排除のマークが付けられていない)1つより多くの活性中の複製を残し得る。
【0045】
グローバルインデックスは、更新されて、重複排除された複製を「重複排除」と指定し得る(ブロック930)。たとえば、重複排除された各複製について、ストレージクラスタ120−1は、その複製に関連する以前のデータレコード(たとえば、「02:位置:データ」)を削除し、グローバルインデックスの対応するコンテンツ処理に、重複排除指示子(たとえば、「02:位置:重複排除」)を書き込み得る。
【0046】
冗長な複製の重複排除は、グローバルインデックスの一部として複製された重複排除メッセージを用いて達成され得る。重複排除のマークが付けられた複製は、ストレージクラスタ120−1または他のストレージクラスタ(たとえば、ストレージクラスタ120−2,120−3,120−4など)に記憶され得る。一実行例においては、ストレージクラスタ120−1は、局部的に記憶された複製および対応する「01:位置:データ」のレコードをグローバルインデックスから削除し、「01:位置:重複排除」をグローバルインデックスに追加し得る。ストレージクラスタ120−1は、また、複製されたグローバルインデックスを用いて、削除メッセージを起動し、他のクラスタに記憶された複製を削除する。
【0047】
図10は、分散化マルチマスタデータ複製システム(たとえば、ファイルシステム140)における、バンド幅消費の最適化および時間遅れの低減のための例示的なプロセス1000のフローチャートを与える。一実行例においては、プロセス1000は、ストレージクラスタ120のうちの1つによって実行され得る。他の実行例においては、プロセス1000のいくつかまたはすべてが、ストレージクラスタ120を含むまたは含まない、他の装置または装置群によって実行され得る。以下に説明されるプロセス1000の特定の例について、参照はファイルシステム140のストレージクラスタ120−1でなされ、ここでストレージクラスタ120−1は「01」のクラスタIDを含む。
【0048】
図1000に示されるように、プロセス1000は、オブジェクトについてのリクエストの受信で開始され得る(ブロック1010)。たとえば、ストレージクラスタ120−1は、クライエント(たとえば、クライエント110)から、オブジェクトを取得するリクエストを受信し得る。
【0049】
オブジェクト位置は、グローバルインデックスにおいて検索され得る(ブロック1020)。たとえば、ストレージクラスタ120−1は、オブジェクトのコンテンツ処理を用いて、複製されたグローバルインデックス内のオブジェクトについての複製位置を検索し得る。
【0050】
「最良の」複製位置が識別され得る(ブロック1030)。たとえば、1つより多くの複製が利用可能であると想定すると、ストレージクラスタ120−1は、ネットワークリソースを最小化するように読み出すための「最良の」複製を決定し得る。たとえば、「最良の」複製は、ストレージクラスタ120−1に最も近い地理的位置を有する複製であり得る。他の実行例においては、「最良の」複製は、利用可能なネットワーク接続性、地理的位置、および/または他の基準の組み合わせに基づき得る。したがって、いくつかの実行例においては、オブジェクトについての「最良の」複製は、ストレージクラスタ120−1内に局部的に記憶され得る。
【0051】
オブジェクトは、識別された位置から読み出され得る(ブロック1040)。たとえば、ストレージクラスタ120−1は、最も近い利用可能なストレージクラスタから「最良の」複製を要求し、クライアントの要求を満たす複製を受信し得る。そして、ストレージクラスタ120−1は、クライエントにその複製を送信し得る。
【0052】
事例
図11は、本明細書で説明される実行例に従う、例示的なグローバルインデックス部1100を与える。インデックスは、他の情報の中で、コンテンツ処理列1110および重複排除指示子レコード列1120を含み得る。例示的なインデックス部1100において、分散型マルチマスタデータ複製システムが、3つのストレージクラスタXX、YY、およびZZを含むものと仮定する。重複排除アルゴリズムは、ストレージクラスタXX、YY、およびZZの各々において周期的に実行され、グローバルインデックスのすべてまたは一部をスキャンし得る。また、レコード(たとえば、データ、削除リクエスト、および重複排除)は、ストレージクラスタXX、YY、およびZZのうちの1つによって、特定のオブジェクトコンテンツ処理に関連するグローバルインデックスに書き込まれ得る。グローバルインデックスへの修正は、他のすべての参加クラスタ(たとえば、残余のストレージクラスタXX、YY、およびZZ)へ複製され得る。
【0053】
図11に示されるように、インデックス部1100は、コンテンツ処理と、4つのオブジェクトについての関連する削除指示子レコードを含む。「処理11」は、複製が、ストレージクラスタXX(「XX:位置01:データ」)およびストレージクラスタYY(「YY:位置01:データ」)に記憶されていることをそれぞれ示すレコードを有する。「処理21」は、1つの複製がストレージクラスタXX(「XX:位置02:データ」)に記憶され、ストレージクラスタYYの他の複製が実行中の削除リクエスト(「YY:位置02:削除リクエスト」)を有することを示すレコードを有する。「処理31」は、複製がストレージクラスタYY(「XX:位置03:データ」)およびストレージクラスタZZ(「ZZ:位置01:データ」)にそれぞれ記憶されていることを示すレコードを有する。「処理31」は、さらに、複製が、ストレージクラスタYY(「YY:位置03:削除リクエスト」)およびストレージクラスタZZ(「ZZ:位置01:削除リクエスト」)における実行中の削除リクエストを有する2つのレコードを有する。「処理41」は、複製がストレージクラスタYYに記憶されていることを示すレコード(「XX:位置04:データ」)、およびストレージクラスタYYにおける実行中の削除リクエストを有する複製を示すレコード(「YY:位置04:削除リクエスト」)を有する。処理41は、さらに、複製の重複排除が生じたことを示す1つのレコード(「ZZ:位置02:重複排除」)を有する。ストレージクラスタによって用いられる重複排除アルゴリズムは、本明細書で説明される原理に一致するガイドラインを用いて動作し得る。ストレージクラスタXXは、「処理11」、「処理21」、「処理31」、および「処理41」を含むグローバルインデックスの部分への関与に割り当てられるものと仮定する。
【0054】
オブジェクトが、ストレージクラスタに完全にアップロードされると、ストレージクラスタは、オブジェクトのコンテンツ処理によってアドレス指定された複製グローバルインデックスへ、データレコード(たとえば、「クラスタID:位置:データ」)を書き込み得る。たとえば、「XX:位置01:データ」および「YY:位置01:データ」は、「処理11」の複製についてのデータレコードを示す。また、「XX:位置02:データ」は、「処理21」の複製についてのデータレコードを示す。類似のデータレコードが、「処理31」および「処理41」について見ることができる。
【0055】
オブジェクトがストレージクラスタ内で要求されると、ストレージクラスタは、オブジェクトのコンテンツ処理を用いて、複製グローバルインデックスにおける複製位置を検索し、「最良の」(たとえば、最も近い)クラスタから複製を取得する。たとえば、「処理11」に対応するオブジェクトがストレージクラスタZZで要求され、ストレージクラスタYYがストレージクラスタXXよりもストレージクラスタZZに近いと仮定すると、ストレージクラスタZZは、ストレージクラスタYYからの「処理11」に対応するオブジェクト複製を要求し得る。
【0056】
オブジェクトがストレージクラスタにおいて削除されると、ストレージクラスタは、そのオブジェクトのコンテンツ処理によってアドレス指定された複製グローバルインデックスへ、「クラスタID:位置:削除リクエスト」を書き込み得る。たとえば、「YY:位置02:削除リクエスト」は、ストレージクラスタYYにおける「処理21」の削除された複製についてのレコードを示す。同様に、「YY:位置03:削除リクエスト」および「ZZ:位置01:削除リクエスト」は、それぞれ、ストレージクラスタYYおよびZZについての「処理31」の削除された複製についてのレコードを示す。
【0057】
ストレージクラスタにおけるスキャンが、そのストレージクラスタが関与するコンテンツ処理に対応する実行中の削除リクエストを有しない複数の複製に遭遇した場合、ストレージクラスタはそのオブジェクトの冗長な複製を削除し得る(あるいは、1つより多くの活性中の複製を残す)。他のストレージクラスタにおける削除された各複製について、ストレージクラスタは、データレコードを削除するとともに、重複排除レコードを書き込み得る。たとえば、ストレージクラスタXXにおけるスキャンは、複製がストレージクラスタXX(「XX:位置01:データ」)およびストレージクラスタYY(「YY:位置01:データ」)にそれぞれ記憶されていることを示すレコードを「処理11」が有していると識別し得る。冗長な参照を除去するために与えられた基準に基づいて、ストレージクラスタXXは、ストレージクラスタYYにおける複製の削除を起動し得る。ストレージクラスタXXは、図11に示されるレコード「YY:位置01:データ」を削除するとともに、その代わりに「YY:位置01:重複排除」を書き込み得る。
【0058】
ストレージクラスタXXにおけるスキャンが、ストレージクラスタXXが関与するコンテンツ処理に対応する、他のストレージクラスタ(たとえば、ストレージクラスタYYまたはZZ)における複製についての削除リクエスト(たとえば、「クラスタID:位置:削除リクエスト」)に遭遇した場合、ストレージクラスタXXは、以下のような解析を適用し得る。削除リクエストと同じストレージクラスタおよび同じ位置についての「重複排除」レコードがある場合、そのオブジェクトの他の活性中の複製が存在する場合、または、すべての複製が実行中の削除リクエストを有している場合は、ストレージクラスタXXは、(もしあれば)ストレージクラスタYYまたはZZにおけるオブジェクトの複製を削除し、レコード「YY:位置:*」または「ZZ:位置:*」を削除し得る。たとえば、(レコード「XX:位置02:データ」によって示される)他の活性中のオブジェクトが存在しているので、ストレージクラスタYYにおける「処理21」についての複製およびレコード「YY:位置02:削除リクエスト」が、ストレージクラスタXXによって削除され得る。同様に、ストレージクラスタYYおよびストレージクラスタZZにおける両方の複製が実行中の削除リクエストを有しているので、ストレージクラスタYYにおける「処理31」についての複製およびレコード「YY:位置03:削除リクエスト」が、ストレージクラスタXXによって削除され得る。
【0059】
ストレージクラスタXXが、ストレージクラスタYYまたはZZにおけるオブジェクトの複製を削除できない(たとえば、「重複排除」レコードまたはオブジェクトの他の活性中の複製がなく、かつ、すべての複製が実行中の削除リクエストを有していない)場合、ストレージクラスタXXは、YYまたはZZから、重複排除レコードがありかつ実行中の削除リクエストのない他のストレージクラスタへオブジェクトをコピーし、重複排除レコードを削除するとともにデータレコードを書き込み得る。たとえば、ストレージクラスタYYにおける「処理41」の複製(「YY:位置04:削除リクエスト」)は、ストレージクラスタXXを起動して、ストレージクラスタZZに「処理41」に関連するオブジェクトをコピーさせ得る。ストレージクラスタXXは、グローバルインデックスを更新し、「ZZ:位置02:重複排除」を「ZZ:位置02:データ」に変化させる。
【0060】
オブジェクトについてのすべての削除動作が、そのコンテンツ処理に関与するストレージクラスタにおける、スキャンプロセスによってのみ実行され得るので、アルゴリズムの正確さは直接的である。アルゴリズムは、また、異なる位置(たとえば、XX:位置1およびXX:位置2)を有する同じクラスタにおける複数のオブジェクト複製を透過的に処理する。
【0061】
結論
本明細書に記載されたシステムおよび/または方法は、分散型データ複製システムにおけるオブジェクトのグローバルインデックスを記憶するとともに、分散型データ複製システムを通して、グローバルインデックスおよびいくつかのオブジェクトを複製し得る。ストレージクラスタは、グローバルインデックスの特定のサブセットにおける重複排除のための、重要なエンティティとして割り当てられる。ストレージクラスタは、グローバルインデックスのサブセットのスキャンを実行し、そのスキャンに基づいて冗長な複製を識別し得る。ストレージクラスタは、局部的に記憶された冗長な複製、または遠隔ストレージクラスタ内の冗長な複製を重複排除し得る。
【0062】
上記の実行例の記載は、例示および説明を提供するが、包括的であること、または、開示されたそのままの形式に本発明を限定することを意図したものではない。修正および変更が、上記の教示に照らして可能であり、または本発明の実施から得られる。
【0063】
たとえば、他の実行例においては、重複排除アルゴリズムの同期バージョンが用いられ、それにおいては、分散型データ複製システムにおける複製層を用いるよりはむしろ、異なるストレージクラスタが直接的に通信する。
【0064】
また、図6A〜10に関連して一連のブロックが説明されたが、他の実行例においては、ブロックの順序は修正され得る。さらに、非従属ブロックが並行して実行され得る。
【0065】
本明細書に記載される実施形態は、図中の示された実行例において、ソフトウェア、ファームウェア、およびハードウェアの多くの異なる形式で実現され得ることが明らかであろう。本明細書に記載される実施形態を実行するために用いられる実際のソフトウェアコードまたは特別の制御ハードウェアは、本発明を限定するものではない。したがって、実施形態に動作および振る舞いは、特定のソフトウェアコードを考慮せずに説明されたが、ソフトウェアおよび制御ハードウェアは、本明細書における記述に基づく実施形態を実現するために設計され得ることが理解される。さらに、本明細書において記載された特定の実行例は、1つまたはより多くの機能を実行する「論理」または「要素」として実現され得る。この論理または要素は、プロセッサ、マイクロプロセッサ、特定用途向け集積回路、またはフィールドプログラマブルゲートアレイのようなハードウェア、あるいは、ハードウェおよびソフトウェアの組み合わせ(たとえば、プロセッサによって実行されるソフトウェア)を含み得る。語句「備える(comprises)」および/または「備えている(comprising)」は、本明細書において用いられるときは、言及された特徴、整数、ステップ、または要素の存在を特定するために採用されるが、1つまたはより多くの他の特徴、整数、ステップ、要素、またはそのグループの存在または追加を除外するものではないことが強調されるべきである。
【0066】
たとえ、特徴の特定の組み合わせが特許請求の範囲に記載され、および/または明細書中に開示されているとしても、これらの組み合わせは、本発明の開示を制限することが意図されたものではない。実際、これらの特徴の多くは、特許請求の範囲に具体的に記載されておらず、および/または、明細書中に具体的に開示されていない手法で組み合わされ得る。
【0067】
本願の記載において用いられる要素、動作、または指令のいずれも、そのように明示的に記載されていなければ、本発明に必須または必要不可欠なものとして解釈されるべきではない。また、本明細書で用いられる、冠詞「a」は、1つまたはより多くの事項含むことが意図される。1つの事項のみが意図される場合は、語句「one」または同様の言語が用いられる。さらに、本明細書において用いられる、句「基づいて」は、そうでないものと明示的に言及されていなければ、「少なくとも一部に基づいて」を意味することが意図される。
【背景技術】
【0001】
背景
企業コンピューティングランドスケープは、中央サービスアーキテクチャが分散型ストレージクラスタへ移行したという点で、ストレージアーキテクチャにおいて抜本的な変化をもたらした。ビジネスは記憶効率を増加するための手法を模索しているので、汎用コンピュータから構築されるストレージクラスタは、新しいデータ量の多いアプリケーションのための高い性能、利用可能性、およびスケーラビリティを、モノリシックディスクアレイと比較して、わずかなコストで供給し得る。ストレージクラスタの全潜在能力を解き放つために、データは複数の地理的位置にわたって複製され、それによって、利用可能性を増大させるとともに、クライエントからのネットワーク距離を低減する。
【発明の概要】
【発明が解決しようとする課題】
【0002】
データの重複排除は、重複オブジェクトを識別し、重複を除去することによって必要とされる記憶空間を低減し得る。結果として、データ重複排除は、ストレージ産業について非常に重要となりつつあり、多くの重複を含み得る大規模システムの必要性によって促進されつつある。
【課題を解決するための手段】
【0003】
要約
1つの実行例によれば、方法は、分散型データ複製システムにおける、装置群のうちの1つの装置によって実行され得る。方法は、分散型データ複製システムにおいて、オブジェクトのインデックスを記憶することを含み、オブジェクトの複製が分散型データ複製システムにおける複数の装置によって局部的に記憶される間に、そのインデックスが複製される。方法は、そのインデックスの少なくとも一部のスキャンを実行すること、および、インデックのスキャンに基づいて、オブジェクトの少なくとも1つの冗長な複製を識別することも含み得る。方法は、さらに、インデックスの一部に重複排除レコードを書き込むことによって、冗長な複製の重複排除を行なうことを含み得る。
【0004】
他の実行例によれば、分散型データ複製システムにおける装置群のうちの1つの装置は、分散型データ複製システムにおけるオブジェクトのインデックスを記憶するための手段と、インデックスの変化を書き込んでオブジェクトのうちの1つの複製の状態を指定するための手段と、そのインデックスへの変化を分散型データ複製システムにおける複数の装置に複製するための手段と、インデックスの少なくとも一部のスキャンを実行するための手段と、インデックスのスキャンに基づいてオブジェクトのうちの1つの冗長な複製を識別するための手段と、冗長な複製を重複排除するための手段とを含み得る。
【0005】
さらに他の実行例によれば、システムは、指令、オブジェクトのデータストア、およびオブジェクトのインデックスを記憶するためのメモリと、プロセッサとを含み得る。プロセッサは、メモリ内の指令を実行して、データストア内のオブジェクトの状態を識別し、その状態は、オブジェクトが複製を有しているか否か、および削除リクエストがそのオブジェクトに関連しているか否かに関連し、プロセッサは、オブジェクトの状態に基づいて重複排除指示レコードをそのインデックスに書き込み、その重複排除指示レコードを伴うインデックスを1つまたはより多くの装置に複製し、その1つまたはより多くの装置から、そのオブジェクトに関連する他の重複排除指示レコードを受信し、重複排除指示レコードおよび他の重複排除指示レコードは、そのオブジェクトの1つまたはより多くの複製の削除のための基準を提供する。
【0006】
さらに他の実行例によれば、1つまたより多くの装置によって実行される方法は、分散型データ複製システムにおける複数の装置内のオブジェクトのインデックスを記憶すること、およびそのオブジェクトを局部的に記憶する間に、分散型データ複製システムを通してそのインデックスを複製することを含み、各装置はそのインデックスの特定のサブセットにおけるオブジェクトの重複排除に関与し、方法は、そのインデックスのサブセットの各々のスキャンを実行してそのスキャンに基づいて冗長な複製を識別すること、その冗長を重複排除すること、および進行中の削除リクエストを有する複製を伴う装置からのオブジェクトを、以前に重複排除された複製を伴う装置に自動的にコピーすることをさらに含み得る。
【0007】
さらなる実行例によれば、コンピュータ読取可能メモリは、コンピュータ実行可能指令を含み得る。コンピュータ読取可能メモリは、分散型データ複製システムにおけるオブジェクトのインデックスの一部のスキャンを実行するための1つまたはより多くの指令と、そのインデックスの一部のスキャンに基づいてオブジェクトのうちの1つの複製の冗長な複製を識別するための1つまたはより多くの指令と、その冗長な複製を重複排除するための1つまたはより多くの指令とを含み得る。
【0008】
図面の簡単な説明
添付の図面は、この明細書に含まれるとともにこの明細書の一部を成し、明細書に記載される1つまたはより多くの実施形態を例示し、その記述とともに、これらの実施形態を説明する。
【図面の簡単な説明】
【0009】
【図1】本明細書に記載される方法およびシステムが実現され得る例示的なネットワークの図である。
【図2】図1のファイルシステムの例示的な構成を示す図である。
【図3】図1のストレージクラスタの例示的な要素を示す図である。
【図4】図1の例示的なストレージクラスタの機能ブロック図である。
【図5】分散型マルチマスタデータ複製システムのインデックスにおいて用いられ得る、例示的なレコード構造を示す図である。
【図6A】クライエント起動されるアップロード/削除動作を管理するための例示的なプロセスのフローチャートである。
【図6B】クライエント起動されるアップロード/削除動作を管理するための例示的なプロセスのフローチャートである。
【図7】分散型マルチマスタデータ複製システムにおける重複排除を実行するための例示的なプロセスのフローチャートである。
【図8】削除リクエストを管理するための例示的なプロセスのフローチャートである。
【図9】重複した複製を除去するための例示的なプロセスのフローチャートである。
【図10】分散型マルチマスタデータ複製システムにおいて、バンド幅消費を最適化するとともに時間遅れを低減するための例示的なプロセスのフローチャートである。
【図11】本明細書に記載された実行例に従う、例示的なグローバルインデックスの一部を示す図である。
【発明を実施するための形態】
【0010】
詳細な説明
以下の詳細な説明は、添付の図面を参照する。異なる図面における同じ参照番号は、同じまたは類似の要素を特定し得る。また、以下の詳細な説明は、本発明を限定するものではない。
【0011】
本明細書に記載されるシステムおよび/または方法は、不変オブジェクト(immutable object)についての利用可能性、活性(liveness)および一貫性保証を提供する複製されたストレージクラスタのための、非同期分散型重複排除アルゴリズムを提供し得る。本明細書に記載される実行例は、分散型マルチマスタデータ複製システムの下部複製層を用いて、異なるストレージクラスタ間のコンテンツアドレス可能インデックス(本明細書においては、「グローバルインデックス」とも称する。)を複製し得る。グローバルインデックスの各オブジェクトは、固有のコンテンツ処理(たとえば、ハッシュ値またはデジタル署名)を有し得る。本明細書に記載される実行例においては、冗長な複製の除去プロセスが、少なくとも1つの活性中の複製を保持し得る。
【0012】
例示的なネットワーク構成
図1は、本明細書において説明されるシステムおよび方法が実行され得る例示的なシステム100の図である。システム100は、ネットワーク130を介して接続される、クライエント110−1〜110−N(総称してクライエント110、および個々にクライエント110とも称する。)およびストレージクラスタ120−1〜120−M(総称してストレージクラスタ120、および個々にストレージクラスタ120とも称する。)を含む。ストレージクラスタ120は、(図1の点線によって示されるような)ファイルシステム140を形成する。
【0013】
ネットワーク130は、ローカルエリアネットワーク(local area network:LAN)、広域ネットワーク(wide area network:WAN)、電話回線ネットワーク(たとえば、公衆交換電話網(Public Switched Telephone Network:PSTN))、イントラネット、インターネット、類似または非類似ネットワーク、あるいはネットワークの組み合わせのような、1つまたはより多くのネットワークを含み得る。クライエント110およびストレージクラスタ120は、有線または無線接続を介してネットワーク130と接続し得る。
【0014】
クライエント110は、パーソナルコンピュータ、無線電話、携帯情報端末(personal digital assistant:PDA)、ラップトップ、または他のタイプの通信装置、および/または、これらの装置のうちの1つにおいて実行されるスレッドまたはプロセスのような、1つまたはより多くのタイプの装置を含み得る。一実行例においては、クライエント110は、そのクライエント110に代わってファイルデータを読出しまたは修正する(たとえば、書き込む)ためにストレージクラスタ120と通信するアプリケーションを含み、あるいはアプリケーションにリンクされる。
【0015】
ストレージクラスタ120は、本明細書で説明される態様で情報を記憶し、処理し、検索し、およびまたは提供し得る1つまたはより多くのサーバ装置、あるいは、他のタイプのコンピュータまたは通信装置を含み得る。一実行例においては、ストレージクラスタ120は、ファイルに対して、大規模でランダムな読出し/書込みアクセスデータストアを維持することが可能な、1つまたはより多くのサーバ(たとえば、コンピュータシステムおよび/またはアプリケーション)を含み得る。ストレージクラスタ120のデータストアは、変化が生じた場合に、インデキシングシステムが迅速にインデックスの一部を更新することを許可し得る。ストレージクラスタ120のデータストアは、1つまたはより多くのテーブル(たとえば、ユニフォームリソースロケータ(uniform resource locator:URL)ごとに1つの列を含む文書テーブル、URL以外の値によって検索される補助テーブルなど)を含み得る。一例においては、ストレージクラスタ120は、非常に大規模(たとえば、数千のサーバにわたるペタバイトのデータ)に設計され得る構造データ(たとえば、文書のランダムアクセスストレージクラスタ)を管理するための、分散型記憶システム(たとえば、チャン(Chang)らによって書かれた「ビッグテーブル:構造データ用の分散型記憶システム(Bigtable: A Distributed Storage System for Structured Data)」、第7回OSDI会報、205〜218ページ(2006年11月)における「ビッグテーブル(Bigtable)」)に含まれ得る。
【0016】
図1には示されていないが、システム100は、1つまたはより多くの専用の民生サーバまたはハブのような、多数の他の要素を含み得る。民生サーバは、たとえば、クライエント110によるアクセスのために、1つまたはより多くのストレージクラスタ120からのデータストアの読出し専用コピーを記憶し得る。ハブは、たとえば、1つまたはより多くの民生サーバへ分配するために、1つまたはより多くのストレージクラスタ120からのデータストアの読出し専用コピーを記憶し得る。
【0017】
例示的なストレージクラスタ構造
図2は、ファイルシステム140の例示的構成の図である。図2に示されるように、ファイルシステム140は、ストレージクラスタ120−1、120−2、120−3、および120−4を含み得る。一実行例においては、ファイルシステム140は、分散型マルチマスタデータ複製システムであり、ストレージクラスタ120−1、120−2、120−3、および120−4の各々は、他のストレージクラスタについてのマスタサーバとして動作し得る。ファイルシステム140においては、データは、(たとえば、複数の地理的場所において)ストレージクラスタ120−1、120−2、120−3、および120−4にわたって複製され、データ利用可能性を増加するとともにクライエント(たとえば、クライエント110)からのネットワーク距離を低減し得る。一般的に、分散型オブジェクトおよび参照は、異なるストレージクラスタ120において、動的に生成され、変化され、模造され、そして削除され得、下部データ複製層(図示せず)は、書込み順の忠実性を維持して、すべてのストレージクラスタ120が同じデータのバージョンに至ることを保証する。したがって、データ複製層は、単一のオブジェクトについての同じ複製についての書込み順を遵守する。
【0018】
分散型マルチマスタデータ複製システムにおけるすべてのオブジェクトのグローバルインデックスは、各ストレージクラスタ120に関連し得る。各記憶されたオブジェクトは、グローバルインデックスにおいて、(ハッシュ値、デジタル署名などのような)固有のコンテンツ処理によってリスト化され得る。選択されたストレージクラスタは、各々、グローバルインデックスにおけるコンテンツ処理の個別の領域に関与するように割り当てられ得る。たとえば、単一のストレージクラスタ120は、特定のコンテンツ処理に関連するオブジェクトの重複排除に関与し得る。1つのストレージクラスタによってなされたグローバルインデックスへの変更は、他のストレージクラスタに複製され得る。
【0019】
図2は、ファイルシステム140の例示的な機能要素を示すが、他の実行例においては、ファイルシステム140は、図2に記載されているよりも、より少ない要素、追加的な要素、異なる要素、または異なった配置の要素を含み得る。さらの他の実行例においては、ファイルシステム140の1つまたはより多くの要素は、ファイルシステム140の1つまたはより多くの要素によって実行されるものとして記述された1つまたはより多くのタスクを実行し得る。
【0020】
図3は、ストレージクラスタ120の例示的な要素の図である。ストレージクラスタ120は、バス310と、プロセッサ320と、メインメモリ330と、読み取り専用メモリ(ROM)340と、記憶装置350と、入力装置360と、出力装置370と、通信インターフェース380とを含み得る。バス310は、ストレージクラスタ120の要素間の通信を許可する、1つまたはより多くの導体を含み得る。
【0021】
プロセッサ320は、指令を解釈して実行し得る、任意のプロセッサまたはマイクロプロセッサを含み得る。メインメモリ330は、プロセッサ320によって実行される情報および指令を記憶し得る、ランダムアクセスメモリ(RAM)または他のタイプのダイナミック記憶装置を含み得る。ROM340は、プロセッサ320による使用のための、静的情報および指令を記憶し得る、ROM装置または他のタイプのスタティック記憶装置を含み得る。記憶装置350は、磁気およびまたは光記録媒体、ならびにそれに対応するドライブを含み得る。たとえば記憶装置350は、持続性記憶を提供する1つまたはより多くのローカルディスクを含み得る。一実行例においては、ストレージクラスタ120は、ファイルシステム140に記憶されたオブジェクトのためのメタデータを、メインメモリ330および/または記憶装置350のような1つまたはより多くのコンピュータ読取可能媒体内に維持し得る。たとえば、ストレージクラスタ120は、分散型マルチマスタデータ複製システムにおいて記憶されたすべてのオブジェクトのために、記憶装置350内にグローバルインデックスを記憶し得る。
【0022】
入力装置360は、キーボード、キーパッド、ボタン、マウス、ペンなどのような、操作者がストレージクラスタ120に情報を入力することを許可する1つまたはより多くの機構を含み得る。出力装置370は、ディスプレイ、発光ダイオード(light emitting diode:LED)などを含む、操作者に情報を出力する1つまたはより多くの機構を含み得る。通信インターフェース380は、ストレージクラスタ120が、他の装置および/またはシステムと通信できるようにする、任意の送受信機のような機構を含み得る。たとえば、通信インターフェース380は、他のストレージクラスタ120および/またはクライエント110と通信するための機構を含み得る。
【0023】
図4は、ストレージクラスタ120の機能ブロック図を示す。図4に示されるように、ストレージクラスタ120は、データストア410および重複排除論理420を含み得る。一実行例においては、図4に示されるように、データストア410が、ストレージクラスタ120内に設けられる。他の実行例においては、データストア410のいくつかまたはすべては、ストレージクラスタ120との通信により、インデックスシステムに関連する外部メモリ装置(図示せず)のような、システム100の1つまたはより多くの装置内に記憶され得る。
【0024】
データストア410は、複製インデックスストア412およびローカルオブジェクトストア414を含み得る。複製インデックスストア412は、分散化マルチマスタデータ複製システムの複製層の一部として含まれ得る。複製インデックスストア412は、グローバルインデックスに関連する情報を記憶し得る。複製インデックスストア412の少なくとも一部は、複数のストレージクラスタ120において複製され得る。各複製インデックスストア412についての複製の数は、ユーザ設定可能であり得る。ローカルオブジェクトストア414は、ストレージクラスタ120において局部的にオブジェクトを記憶し得る。ローカルオブジェクトストア414は、クライエント(たとえば、クライエント110)によってアップロードされた画像またはビデオのような、ファイルを含み得る。
【0025】
複製削除論理420は、分散化マルチマスタデータ複製システム内のストレージクラスタ(たとえば、ストレージクラスタ120−1、120−2、120−3、および120−4)から冗長な複製を除去するための論理を含み得る。各参加ストレージクラスタについての複製削除論理420は、グローバルインデックスの特定のセクションに関与するように割り当てられ得る。たとえば、複製削除論理420は、グローバルインデックスについてのコンテンツ処理の特定の範囲に割り当てられ得る。したがって、分散化マルチマスタデータ複製システム内の1つのストレージクラスタだけが、システム内の複製オブジェクトについての破壊的操作(destructive operation)(たとえば、複製の削除)を実行することができる。
【0026】
重複排除を容易にするために、レコードが重複排除論理420によって生成され、特定のコンテンツ処理に関連するグローバルインデックスの一部に追加され得る。レコードは、たとえば、活性中の複製を起動するための「データ(Data)」指示子、実行中の削除リクエストを示す「削除リクエスト(DeleteRequest)」指示子、および重複排除のために選択された複製を示す「重複排除(Deduped)」指示子を含み得る。レコードフォーマットおよびその使用は、以下でより詳細に説明される。
【0027】
図4は、ストレージクラスタ120の例示的な機能要素を示すが、他の実行例においては、ストレージクラスタ120は、図4に示されたものよりも、より少ない機能要素、追加の機能要素、異なる機能要素、または、異なる配列の機能要素を含み得る。さらに他の実行例においては、ストレージクラスタ120の1つまたはより多くの機能要素は、1つまたはより多くの他の機能要素によって実行されるものとして記述される1つまたはより多くの他のタスクを実行し得る。
【0028】
例示的なレコード構造
図5は、例示的な実行例においてグローバルインデックスに書き込まれ得る、重複排除指示子レコードについての例示的なレコード構造500の図を提供する。重複排除指示子レコードは、オブジェクト複製の特定のコンテンツ処理を有するグローバルインデックスに関連し得る。図5に示されるように、レコード構造500は、ストレージクラスタ識別子(ID)セクション510と、記憶位置セクション520と、指示セクション530とを含み得る。ストレージクラスタ識別セクション510は、レコードが書き込まれるオブジェクト複製を記憶しているストレージクラスタ120についての固有の識別(たとえば、「クラスタID」)を含み得る。位置セクション520は、ストレージクラスタ識別セクション510によって識別されたストレージクラスタ120における複製の位置についてのアドレスを含み得る。指示セクション530は、たとえば、「データ」指示子、「削除リクエスト」指示子、または「重複排除」指示子を含み得る。
【0029】
レコード構造500は、「クラスタID:位置:指示」の形式でリスト化され得る。たとえば、複製のためのレコードは、ストレージクラスタ120−1によって、レコード「01:234523/2000:削除リクエスト」でグローバルインデックスに追加され得、ここで、「01」はストレージクラスタ120−1のクラスタIDであり、「234523/2000」はストレージクラスタ120−1内の複製が記憶される位置であり、「削除リクエスト」は指示子である。ストレージクラスタ120−2における同じオブジェクトの他の複製のレコードは、「02:234544/1000:データ」であり得、ここで、「02」はストレージクラスタ120−2のクラスタIDであり、「234544/1000」はストレージクラスタ120−2における位置であり、「データ」は指示子である。
【0030】
例示的なプロセスフロー
図6Aおよび図6Bは、クライエント起動アップロード/削除動作を管理するための例示的なプロセスのフローチャートである。図6Aは、クライエントからオブジェクトをアップロードする例示的なプロセス600についてのフローチャートを示す。図6Bは、クライエントによって削除されるオブジェクトを除去する例示的なプロセス650についてのフローチャートを示す。一実行例においては、プロセス600および650は、ストレージクラスタ120の1つによって実行され得る。プロセス600および650は、クライエント(たとえば、クライエント110)の動作に応答して実行され得る。以下に説明されるプロセス600および650の特有の例については、参照は、ファイルシステム140のストレージクラスタ120−1に対してなされ、ストレージクラスタ120は、クラスタID「01」を含む。
【0031】
図6Aを参照して、プロセス600は、アップロードファイルが、クライエントから受信されたると開始し得る(ブロック610)。たとえば、ストレージクラスタ120−1は、クライエント110のうちの1つから新しいファイルを受信し得る。アップロードファイルは記憶され(ブロック620)、アップロードファイルについての「データ」指示子がグローバルインデックスに書き込まれ得る(ブロック630)。たとえば、ストレージクラスタ120−1は、メモリ(たとえば、記憶装置350)にアップロードファイルを記憶し、オブジェクトについてのコンテンツ処理をグローバルインデックスに追加し得る。ストレージクラスタ120−1は、また、データレコード(たとえば、「01:位置:データ」)を、オブジェクトのコンテンツ処理によってアドレス指定された、複製されたグローバルインデックスに書き込み得る。
【0032】
図6Bを参照して、プロセス650は、削除ファイルの通知が受信されると開始し得る(ブロック660)。たとえば、ストレージクラスタ120−1は、クライエント110のうちの1つがファイルを削除した指示を受信し得る。削除リクエストが起動され(ブロック670)、削除ファイルについての「削除リクエスト」指示子がグローバルインデックスに書き込まれ得る(ブロック680)。たとえば、ストレージクラスタ120−1は、削除リクエストを起動して、ファイルシステム140から削除ファイルを非同期に除去する。ストレージ装置120−1は、また、オブジェクトのコンテンツ処理によってアドレス指定された、複製グローバルインデックスに、「削除リクエスト」レコード(たとえば、「01:位置:削除リクエスト」)を書き込み得る。
【0033】
図7は、分散型マルチマスタデータ複製システム(たとえば、ファイルシステム140)における重複排除を実行するための例示的なプロセス700のフローチャートである。一実行例においては、プロセス700は、ストレージクラスタ120のうちの1つによって実行され得る。他の実行例においては、プロセス700のいくつかまたはすべてが、ストレージクラスタ120を含むまたは含まない、他の装置または装置群によって実行され得る。プロセス700は、各ストレージクラスタ120において周期的に実行され、ストレージクラスタ120内のオブジェクトのすべてまたは一部のスキャンを含み得る。以下に説明されるプロセス700の特定の例について、参照はファイルシステム140のストレージクラスタ120−1および120−2に対してなされ、ここでストレージクラスタ120−1は「01」のクラスタIDを含み、ストレージクラスタ120−2は「02」のクラスタIDを含む。
【0034】
図7に示されるように、プロセス700は、グローバルインデックスのスキャンの実行で始まり得る(ブロック710)。たとえば、(たとえば、重複排除論理420を用いた)ストレージクラスタ120−2は、グローバルインデックスに列挙されたすべてまたは一部のオブジェクトのスキャンを実行し得る。スキャンは、たとえば、削除のマークが付けられた複数の複製および/またはオブジェクトを識別し得る。
【0035】
削除リクエストに遭遇したか否かが判定され得る(ブロック720)。たとえば、ストレージクラスタ120−1は、グローバルインデックスにおいて、他のストレージクラスタから(たとえば、ストレージクラスタ120−2から)の削除リクエスト指示子(たとえば、「02:位置:削除リクエスト」)を含むオブジェクトに遭遇し得る。削除リクエストに遭遇したと判定された場合(ブロック720−YES)は、削除リクエストが処理され得る(ブロック730)。たとえば、ストレージクラスタ120−1は、図8を参照してより詳細に説明されるように、削除リクエストを処理し得る。
【0036】
削除リクエストに遭遇しなかったと判定された場合(ブロック720−NO)は、冗長な複製が存在するか否かが判定され得る(ブロック740)。冗長な複製は、オブジェクトについての実行中の削除リクエストを有していない、異なる位置における複製されたオブジェクトであり得る。たとえば、ストレージクラスタ120−1は、ストレージクラスタ120−1が関与するコンテンツ処理に対応する、同じオブジェクトについての複数の複製を識別し得る。複数の複製は、たとえば、異なるストレージクラスタ(たとえば、ストレージクラスタ120−1およびストレージクラスタ120−2)または同じストレージクラスタ内の異なる位置に記憶され得る。
【0037】
冗長な複製が存在すると判定された場合(ブロック740−YES)は、冗長な複製は除去され得る(ブロック750)。たとえば、ストレージクラスタ120−1は、図9を参照してより詳細に説明されるように、冗長な複製を除去し得る。冗長な複製が存在しないと判定された場合(ブロック740−NO)は、プロセスはブロック710に戻り、グローバルインデックスの他のスキャンが実行され得る(ブロック710)。
【0038】
図8は、図6のブロック660の削除リクエストの処理に関連した例示的な動作を示す。削除リクエストは、オブジェクトについて見つけられ得る(ブロック810)。たとえば、ストレージクラスタ120−1によって実行されるスキャンは、グローバルインデックス内において、特定のストレージクラスタにおける複製を削除するための、ストレージクラスタ120−1によって事前に書き込まれた削除リクエスト指示子(たとえば、「02:位置:削除リクエスト」)を有するコンテンツ処理を識別し得る。ストレージクラスタ120−1がそのコンテンツ処理に関与すると想定すると、ストレージクラスタ120−1は、動作を適用して、その複製がまさに重複排除され得るか否かを判定する。
【0039】
重複排除指示子が存在するか否かが判定され得る(ブロック820)。たとえば、ストレージクラスタ120−1は、グローバルインデックスにおいてそのコンテンツ処理に関連する他のレコードを調べ、重複排除指示子(たとえば、「02:位置:重複排除」)が存在するか否かを判定する。重複排除指示子が存在すると判定された場合(ブロック820−YES)は、グローバルインデックスにおける複製および関連するレコードが、重複排除され得る(ブロック830)。たとえば、ストレージクラスタ120−1は、削除リクエストを起動して、(もし、あれば)ストレージクラスタ120−2における複製を削除し、その削除された複製についてのコンテンツ処理に関連するすべてのレコード(たとえば、「02:位置:*」、ここで「*」は任意の指示子)をグローバルインデックスから削除する。
【0040】
重複排除指示子が存在しないと判定された場合(ブロック820−NO)は、他の活性中の複製が存在するか否かが判定され得る(ブロック840)。たとえば、ストレージクラスタ120−2は、グローバルインデックスについてのコンテンツ処理を調べて、そのオブジェクトについての他の活性中の複製が存在するか否かを判定する。グローバルインデックスは、たとえば、他のストレージクラスタからのコンテンツ処理についてのデータレコード(たとえば、「03:位置:データ」)を含み得る。
【0041】
他の活性中の複製が存在する場合(ブロック840−YES)は、ブロック830を参照して上記で説明されたように、その複製は重複排除され得る。他の活性中の複製が存在しない場合(ブロック840−NO)は、すべての複製が削除リクエストを有しているか否かが判定され得る(ブロック850)。たとえば、ストレージクラスタ120−1は、グローバルインデックスについてのコンテンツ処理を調べ、そのコンテンツ処理に関連するすべての複製が実行中の削除リクエストを有しているか否かを判定し得る(たとえば、「*:*:削除リクエスト」、ここで、「*」は、それぞれ任意のクラスタIDおよび任意の位置であり得る)。
【0042】
すべての複製が削除リクエストを有していると判定された場合(ブロック850−YES)は、複製は、ブロック830を参照して上記で説明されたように、重複排除され得る。すべての複製が削除リクエストを有してはいないと判定された場合(ブロック850−NO)は、オブジェクトは、削除リクエストを起動したストレージクラスタから異なるストレージクラスタへコピーされ、グローバルインデックスが更新され得る(ブロック860)。たとえば、レコード「02:位置:削除リクエスト」に応答して、ストレージクラスタ120−1は、ストレージクラスタ120−2から、重複排除レコード(たとえば、「03:位置:重複排除」)がありかつ実行中の削除リクエストがない他のストレージクラスタ120−3へオブジェクトをコピーし得る。ストレージクラスタ120−1は、その複製に関連する以前の重複排除レコード(たとえば、「03:位置:重複排除」)を削除し、グローバルインデックスにおいてそのオブジェクトの対応するコンテンツ処理に、データ指示子(たとえば、「03:位置:データ」)を書き込む。
【0043】
図9は、図7のブロック750の、重複参照(duplicate reference)の除去に関連する例示的な動作を示す。削除リクエストを有しない複数の複製が、識別され得る(ブロック910)。たとえば、ストレージクラスタ120−1は、グローバルインデックスを調べて、ストレージクラスタ120−01が関与するコンテンツ処理に対応する実行中の削除リクエストを有しない、2つまたはより多くの複製を識別する。
【0044】
重複排除されるべき複製を決定する基準が、適用され得る(ブロック920)。たとえば、ストレージクラスタ120−1は、ストレージクラスタ120−1内に記憶され得る冗長な複製の重複排除を行なうための基準を適用し得る。冗長な複製を重複排除する基準は、複製の地理的近接性、ストレージクラスタにおける利用可能な記憶容量、または他の要因のような、様々な要因に基づき得る。(たとえば、重複排除論理420を用いる)ストレージクラスタ120−1は、上記識別された、実行中の削除リクエストを有しない2つまたはより多くの複製に、その基準を適用し得る。いくつかの実行例においては、複数の複製が、重複排除されるべきであると識別され得る。他の実行例においては、ストレージクラスタ120−1は、(たとえば、重複排除のマークが付けられていない)1つより多くの活性中の複製を残し得る。
【0045】
グローバルインデックスは、更新されて、重複排除された複製を「重複排除」と指定し得る(ブロック930)。たとえば、重複排除された各複製について、ストレージクラスタ120−1は、その複製に関連する以前のデータレコード(たとえば、「02:位置:データ」)を削除し、グローバルインデックスの対応するコンテンツ処理に、重複排除指示子(たとえば、「02:位置:重複排除」)を書き込み得る。
【0046】
冗長な複製の重複排除は、グローバルインデックスの一部として複製された重複排除メッセージを用いて達成され得る。重複排除のマークが付けられた複製は、ストレージクラスタ120−1または他のストレージクラスタ(たとえば、ストレージクラスタ120−2,120−3,120−4など)に記憶され得る。一実行例においては、ストレージクラスタ120−1は、局部的に記憶された複製および対応する「01:位置:データ」のレコードをグローバルインデックスから削除し、「01:位置:重複排除」をグローバルインデックスに追加し得る。ストレージクラスタ120−1は、また、複製されたグローバルインデックスを用いて、削除メッセージを起動し、他のクラスタに記憶された複製を削除する。
【0047】
図10は、分散化マルチマスタデータ複製システム(たとえば、ファイルシステム140)における、バンド幅消費の最適化および時間遅れの低減のための例示的なプロセス1000のフローチャートを与える。一実行例においては、プロセス1000は、ストレージクラスタ120のうちの1つによって実行され得る。他の実行例においては、プロセス1000のいくつかまたはすべてが、ストレージクラスタ120を含むまたは含まない、他の装置または装置群によって実行され得る。以下に説明されるプロセス1000の特定の例について、参照はファイルシステム140のストレージクラスタ120−1でなされ、ここでストレージクラスタ120−1は「01」のクラスタIDを含む。
【0048】
図1000に示されるように、プロセス1000は、オブジェクトについてのリクエストの受信で開始され得る(ブロック1010)。たとえば、ストレージクラスタ120−1は、クライエント(たとえば、クライエント110)から、オブジェクトを取得するリクエストを受信し得る。
【0049】
オブジェクト位置は、グローバルインデックスにおいて検索され得る(ブロック1020)。たとえば、ストレージクラスタ120−1は、オブジェクトのコンテンツ処理を用いて、複製されたグローバルインデックス内のオブジェクトについての複製位置を検索し得る。
【0050】
「最良の」複製位置が識別され得る(ブロック1030)。たとえば、1つより多くの複製が利用可能であると想定すると、ストレージクラスタ120−1は、ネットワークリソースを最小化するように読み出すための「最良の」複製を決定し得る。たとえば、「最良の」複製は、ストレージクラスタ120−1に最も近い地理的位置を有する複製であり得る。他の実行例においては、「最良の」複製は、利用可能なネットワーク接続性、地理的位置、および/または他の基準の組み合わせに基づき得る。したがって、いくつかの実行例においては、オブジェクトについての「最良の」複製は、ストレージクラスタ120−1内に局部的に記憶され得る。
【0051】
オブジェクトは、識別された位置から読み出され得る(ブロック1040)。たとえば、ストレージクラスタ120−1は、最も近い利用可能なストレージクラスタから「最良の」複製を要求し、クライアントの要求を満たす複製を受信し得る。そして、ストレージクラスタ120−1は、クライエントにその複製を送信し得る。
【0052】
事例
図11は、本明細書で説明される実行例に従う、例示的なグローバルインデックス部1100を与える。インデックスは、他の情報の中で、コンテンツ処理列1110および重複排除指示子レコード列1120を含み得る。例示的なインデックス部1100において、分散型マルチマスタデータ複製システムが、3つのストレージクラスタXX、YY、およびZZを含むものと仮定する。重複排除アルゴリズムは、ストレージクラスタXX、YY、およびZZの各々において周期的に実行され、グローバルインデックスのすべてまたは一部をスキャンし得る。また、レコード(たとえば、データ、削除リクエスト、および重複排除)は、ストレージクラスタXX、YY、およびZZのうちの1つによって、特定のオブジェクトコンテンツ処理に関連するグローバルインデックスに書き込まれ得る。グローバルインデックスへの修正は、他のすべての参加クラスタ(たとえば、残余のストレージクラスタXX、YY、およびZZ)へ複製され得る。
【0053】
図11に示されるように、インデックス部1100は、コンテンツ処理と、4つのオブジェクトについての関連する削除指示子レコードを含む。「処理11」は、複製が、ストレージクラスタXX(「XX:位置01:データ」)およびストレージクラスタYY(「YY:位置01:データ」)に記憶されていることをそれぞれ示すレコードを有する。「処理21」は、1つの複製がストレージクラスタXX(「XX:位置02:データ」)に記憶され、ストレージクラスタYYの他の複製が実行中の削除リクエスト(「YY:位置02:削除リクエスト」)を有することを示すレコードを有する。「処理31」は、複製がストレージクラスタYY(「XX:位置03:データ」)およびストレージクラスタZZ(「ZZ:位置01:データ」)にそれぞれ記憶されていることを示すレコードを有する。「処理31」は、さらに、複製が、ストレージクラスタYY(「YY:位置03:削除リクエスト」)およびストレージクラスタZZ(「ZZ:位置01:削除リクエスト」)における実行中の削除リクエストを有する2つのレコードを有する。「処理41」は、複製がストレージクラスタYYに記憶されていることを示すレコード(「XX:位置04:データ」)、およびストレージクラスタYYにおける実行中の削除リクエストを有する複製を示すレコード(「YY:位置04:削除リクエスト」)を有する。処理41は、さらに、複製の重複排除が生じたことを示す1つのレコード(「ZZ:位置02:重複排除」)を有する。ストレージクラスタによって用いられる重複排除アルゴリズムは、本明細書で説明される原理に一致するガイドラインを用いて動作し得る。ストレージクラスタXXは、「処理11」、「処理21」、「処理31」、および「処理41」を含むグローバルインデックスの部分への関与に割り当てられるものと仮定する。
【0054】
オブジェクトが、ストレージクラスタに完全にアップロードされると、ストレージクラスタは、オブジェクトのコンテンツ処理によってアドレス指定された複製グローバルインデックスへ、データレコード(たとえば、「クラスタID:位置:データ」)を書き込み得る。たとえば、「XX:位置01:データ」および「YY:位置01:データ」は、「処理11」の複製についてのデータレコードを示す。また、「XX:位置02:データ」は、「処理21」の複製についてのデータレコードを示す。類似のデータレコードが、「処理31」および「処理41」について見ることができる。
【0055】
オブジェクトがストレージクラスタ内で要求されると、ストレージクラスタは、オブジェクトのコンテンツ処理を用いて、複製グローバルインデックスにおける複製位置を検索し、「最良の」(たとえば、最も近い)クラスタから複製を取得する。たとえば、「処理11」に対応するオブジェクトがストレージクラスタZZで要求され、ストレージクラスタYYがストレージクラスタXXよりもストレージクラスタZZに近いと仮定すると、ストレージクラスタZZは、ストレージクラスタYYからの「処理11」に対応するオブジェクト複製を要求し得る。
【0056】
オブジェクトがストレージクラスタにおいて削除されると、ストレージクラスタは、そのオブジェクトのコンテンツ処理によってアドレス指定された複製グローバルインデックスへ、「クラスタID:位置:削除リクエスト」を書き込み得る。たとえば、「YY:位置02:削除リクエスト」は、ストレージクラスタYYにおける「処理21」の削除された複製についてのレコードを示す。同様に、「YY:位置03:削除リクエスト」および「ZZ:位置01:削除リクエスト」は、それぞれ、ストレージクラスタYYおよびZZについての「処理31」の削除された複製についてのレコードを示す。
【0057】
ストレージクラスタにおけるスキャンが、そのストレージクラスタが関与するコンテンツ処理に対応する実行中の削除リクエストを有しない複数の複製に遭遇した場合、ストレージクラスタはそのオブジェクトの冗長な複製を削除し得る(あるいは、1つより多くの活性中の複製を残す)。他のストレージクラスタにおける削除された各複製について、ストレージクラスタは、データレコードを削除するとともに、重複排除レコードを書き込み得る。たとえば、ストレージクラスタXXにおけるスキャンは、複製がストレージクラスタXX(「XX:位置01:データ」)およびストレージクラスタYY(「YY:位置01:データ」)にそれぞれ記憶されていることを示すレコードを「処理11」が有していると識別し得る。冗長な参照を除去するために与えられた基準に基づいて、ストレージクラスタXXは、ストレージクラスタYYにおける複製の削除を起動し得る。ストレージクラスタXXは、図11に示されるレコード「YY:位置01:データ」を削除するとともに、その代わりに「YY:位置01:重複排除」を書き込み得る。
【0058】
ストレージクラスタXXにおけるスキャンが、ストレージクラスタXXが関与するコンテンツ処理に対応する、他のストレージクラスタ(たとえば、ストレージクラスタYYまたはZZ)における複製についての削除リクエスト(たとえば、「クラスタID:位置:削除リクエスト」)に遭遇した場合、ストレージクラスタXXは、以下のような解析を適用し得る。削除リクエストと同じストレージクラスタおよび同じ位置についての「重複排除」レコードがある場合、そのオブジェクトの他の活性中の複製が存在する場合、または、すべての複製が実行中の削除リクエストを有している場合は、ストレージクラスタXXは、(もしあれば)ストレージクラスタYYまたはZZにおけるオブジェクトの複製を削除し、レコード「YY:位置:*」または「ZZ:位置:*」を削除し得る。たとえば、(レコード「XX:位置02:データ」によって示される)他の活性中のオブジェクトが存在しているので、ストレージクラスタYYにおける「処理21」についての複製およびレコード「YY:位置02:削除リクエスト」が、ストレージクラスタXXによって削除され得る。同様に、ストレージクラスタYYおよびストレージクラスタZZにおける両方の複製が実行中の削除リクエストを有しているので、ストレージクラスタYYにおける「処理31」についての複製およびレコード「YY:位置03:削除リクエスト」が、ストレージクラスタXXによって削除され得る。
【0059】
ストレージクラスタXXが、ストレージクラスタYYまたはZZにおけるオブジェクトの複製を削除できない(たとえば、「重複排除」レコードまたはオブジェクトの他の活性中の複製がなく、かつ、すべての複製が実行中の削除リクエストを有していない)場合、ストレージクラスタXXは、YYまたはZZから、重複排除レコードがありかつ実行中の削除リクエストのない他のストレージクラスタへオブジェクトをコピーし、重複排除レコードを削除するとともにデータレコードを書き込み得る。たとえば、ストレージクラスタYYにおける「処理41」の複製(「YY:位置04:削除リクエスト」)は、ストレージクラスタXXを起動して、ストレージクラスタZZに「処理41」に関連するオブジェクトをコピーさせ得る。ストレージクラスタXXは、グローバルインデックスを更新し、「ZZ:位置02:重複排除」を「ZZ:位置02:データ」に変化させる。
【0060】
オブジェクトについてのすべての削除動作が、そのコンテンツ処理に関与するストレージクラスタにおける、スキャンプロセスによってのみ実行され得るので、アルゴリズムの正確さは直接的である。アルゴリズムは、また、異なる位置(たとえば、XX:位置1およびXX:位置2)を有する同じクラスタにおける複数のオブジェクト複製を透過的に処理する。
【0061】
結論
本明細書に記載されたシステムおよび/または方法は、分散型データ複製システムにおけるオブジェクトのグローバルインデックスを記憶するとともに、分散型データ複製システムを通して、グローバルインデックスおよびいくつかのオブジェクトを複製し得る。ストレージクラスタは、グローバルインデックスの特定のサブセットにおける重複排除のための、重要なエンティティとして割り当てられる。ストレージクラスタは、グローバルインデックスのサブセットのスキャンを実行し、そのスキャンに基づいて冗長な複製を識別し得る。ストレージクラスタは、局部的に記憶された冗長な複製、または遠隔ストレージクラスタ内の冗長な複製を重複排除し得る。
【0062】
上記の実行例の記載は、例示および説明を提供するが、包括的であること、または、開示されたそのままの形式に本発明を限定することを意図したものではない。修正および変更が、上記の教示に照らして可能であり、または本発明の実施から得られる。
【0063】
たとえば、他の実行例においては、重複排除アルゴリズムの同期バージョンが用いられ、それにおいては、分散型データ複製システムにおける複製層を用いるよりはむしろ、異なるストレージクラスタが直接的に通信する。
【0064】
また、図6A〜10に関連して一連のブロックが説明されたが、他の実行例においては、ブロックの順序は修正され得る。さらに、非従属ブロックが並行して実行され得る。
【0065】
本明細書に記載される実施形態は、図中の示された実行例において、ソフトウェア、ファームウェア、およびハードウェアの多くの異なる形式で実現され得ることが明らかであろう。本明細書に記載される実施形態を実行するために用いられる実際のソフトウェアコードまたは特別の制御ハードウェアは、本発明を限定するものではない。したがって、実施形態に動作および振る舞いは、特定のソフトウェアコードを考慮せずに説明されたが、ソフトウェアおよび制御ハードウェアは、本明細書における記述に基づく実施形態を実現するために設計され得ることが理解される。さらに、本明細書において記載された特定の実行例は、1つまたはより多くの機能を実行する「論理」または「要素」として実現され得る。この論理または要素は、プロセッサ、マイクロプロセッサ、特定用途向け集積回路、またはフィールドプログラマブルゲートアレイのようなハードウェア、あるいは、ハードウェおよびソフトウェアの組み合わせ(たとえば、プロセッサによって実行されるソフトウェア)を含み得る。語句「備える(comprises)」および/または「備えている(comprising)」は、本明細書において用いられるときは、言及された特徴、整数、ステップ、または要素の存在を特定するために採用されるが、1つまたはより多くの他の特徴、整数、ステップ、要素、またはそのグループの存在または追加を除外するものではないことが強調されるべきである。
【0066】
たとえ、特徴の特定の組み合わせが特許請求の範囲に記載され、および/または明細書中に開示されているとしても、これらの組み合わせは、本発明の開示を制限することが意図されたものではない。実際、これらの特徴の多くは、特許請求の範囲に具体的に記載されておらず、および/または、明細書中に具体的に開示されていない手法で組み合わされ得る。
【0067】
本願の記載において用いられる要素、動作、または指令のいずれも、そのように明示的に記載されていなければ、本発明に必須または必要不可欠なものとして解釈されるべきではない。また、本明細書で用いられる、冠詞「a」は、1つまたはより多くの事項含むことが意図される。1つの事項のみが意図される場合は、語句「one」または同様の言語が用いられる。さらに、本明細書において用いられる、句「基づいて」は、そうでないものと明示的に言及されていなければ、「少なくとも一部に基づいて」を意味することが意図される。
【特許請求の範囲】
【請求項1】
分散型データ複製システムにおける複数の装置のうちの1つの装置によって実行される方法であって、
前記方法は、
前記分散型データ複製システムにおけるオブジェクトのインデックスを記憶するステップを備え、
前記インデックスは、オブジェクトの複製が前記分散型データ複製システムにおける前記複数の装置によって局部的に記憶される間に複製され、
前記方法は、
前記インデックスの少なくとも一部のスキャンを実行するステップと、
前記インデックスの前記スキャンに基づいて、前記オブジェクトの少なくとも1つの冗長な複製を識別するステップと、
前記インデックスの一部に、重複排除レコードを書き込むことによって、前記冗長な複製を重複排除するステップとを備える、方法。
【請求項2】
前記インデックスの変化は、前記分散型データ複製システムの下部複製層を用いて複製される、請求項1に記載の方法。
【請求項3】
前記装置は、前記インデックスの特定のサブセット内におけるオブジェクトについての冗長な複製を低減することに関与する唯一の装置である、請求項1に記載の方法。
【請求項4】
前記インデックスは、前記インデックスにおける各オブジェクトについてのコンテンツ処理を含む、コンテンツアドレス可能インデックスである、請求項1に記載の方法。
【請求項5】
前記オブジェクトの前記コンテンツ処理に関連した前記インデックスの一部に、データレコードまたは削除リクエストレコードを書き込むステップと、
前記オブジェクトの前記コンテンツ処理に関連した前記インデックスの一部を、前記複数の装置のうちの1つまたはより多くの他の装置に複製するステップとをさらに備える、請求項4に記載の方法。
【請求項6】
前記インデックスに含まれる他のオブジェクトについてのリクエストを受信するステップと、
前記インデックスに基づいて、前記他のオブジェクトの複製をそこから読み出すために、複数の装置の選択された装置を決定するステップと、
前記選択された装置から前記他のオブジェクトの複製を読み出すステップとをさらに備える、請求項1に記載の方法。
【請求項7】
前記冗長な複製を識別するステップは、2つまたはより多くの複製間の優先順を区別するための基準にさらに基づく、請求項1に記載の方法。
【請求項8】
前記インデックスは、前記装置における前記複製とは分離して記憶される、請求項1に記載の方法。
【請求項9】
分散型データ複製システムにおける複数の装置のうちの1つの装置であって、
前記装置は、
前記分散型データ複製システムにおけるオブジェクトのインデックスを記憶するための手段と、
前記インデックスへの変化を書き込んで、前記オブジェクトのうちの1つの複製の状態を指定するための手段と、
前記分散型データ複製システムにおいて、前記インデックスへの変化を、前記複数の装置に複製するための手段と、
前記インデックスの少なくとも一部のスキャンを実行する手段と、
前記インデックスの前記スキャンに基づいて、前記オブジェクトのうちの1つの冗長な複製を識別するための手段と、
前記冗長な複製を重複排除するための手段とを備える、装置。
【請求項10】
前記インデックスを更新して、重複排除された複製の状態を反映するための手段をさらに備える、請求項9に記載のシステム。
【請求項11】
システムであって、
指令、オブジェクトのデータストア、および前記データストア内の前記オブジェクトのインデックスを記憶するためのメモリと、
前記メモリにおける前記指令を実行して、以下を行なうプロセッサとを備え、
前記プロセッサは、
前記データストア内のオブジェクトの状態を識別し、前記状態は、前記オブジェクトが複製を有しているか否か、および削除リクエストが前記オブジェクトに関連しているか否かに関連し、
前記プロセッサは、
前記オブジェクトの前記状態に基づいて、前記インデックスへ、重複排除指定レコードを書込み、
前記重複排除指定レコードを有する前記インデックスを、1つまたはより多くの装置に複製し、
前記1つまたはより多くの装置のうちの1つから、前記オブジェクトに関連した他の重複排除指定レコードを受信し、
前記重複排除指定レコードおよび前記他の重複排除指定レコードは、前記オブジェクトの1つまたはより多くの複製の削除についての基準提供する、システム。
【請求項12】
前記重複排除指定レコードおよび前記他の重複排除指定レコードは、分散化マルチマスタデータ複製環境における複製層を用いて交換される、請求項11に記載のシステム。
【請求項13】
前記プロセッサは、前記インデックスの一部のスキャンを実行して、前記オブジェクトの冗長な複製を識別するようにさらに構成される、請求項11に記載のシステム。
【請求項14】
前記装置は、前記インデックスにおけるオブジェクトのサブセットの重複排除にもっぱら関与する、請求項11に記載のシステム。
【請求項15】
前記重複排除指定レコードは、
前記オブジェクトを記憶する前記装置についてのクラスタ識別と、
前記装置における前記オブジェクトの記憶位置についての位置識別と、
前記オブジェクトの重複排除状態についての指示セクションとを含む、請求項11に記載のシステム。
【請求項16】
前記指示セクションは、
前記オブジェクトの活性中の複製を示すためのデータ指示、
複製についての実行中の削除リクエストを示すための削除リクエスト指示、および
重複排除が選択された複製を示すための重複排除指示のうちの1つを含む、請求項15に記載のシステム。
【請求項17】
1つまたはより多くの装置によって実行される方法であって、
分散化データ複製システムにおける複数装置内のオブジェクトのインデックスを記憶するとともに、前記オブジェクトを局部的に記憶している間に、前記分散化データ複製システムを通して前記インデックスを複製するステップを備え、
各装置は、前記インデックスの特定のサブセットにおける前記オブジェクトの重複排除に関与し、
前記方法は、
前記インデックスの前記サブセットの各々のスキャンを実行して、前記スキャンに基づいて冗長な複製を識別するステップと、
前記冗長な複製を重複排除するステップと、
実行中の削除リクエストを有する複製を伴う装置からのオブジェクトを、以前に重複排除された複製を伴う装置に自動的にコピーするステップとをさらに備える、方法。
【請求項18】
前記オブジェクトの1つに関連した前記インデックスの一部へ変化を書き込むステップをさらに備え、
前記変化は、データレコード、削除リクエストレコード、または前記オブジェクトの複製についての重複排除レコードを含む、請求項17に記載の方法。
【請求項19】
前記分散化データ複製システムの下部複製層を用いて、前記インデックスへ前記変化を複製するステップをさらに備える、請求項17に記載の方法。
【請求項20】
前記インデックスは、前記インデックスにおける各オブジェクトについてのコンテンツ処理を含むコンテンツアドレス可能インデックスである、請求項17に記載の方法。
【請求項21】
コンピュータ実行可能指令を含むコンピュータ読取可能メモリであって、
前記コンピュータ読取可能メモリは、
分散化データ複製システムにおけるオブジェクトのインデックスの一部のスキャンを実行するための1つまたはより多くの指令と、
前記インデックスの一部の前記スキャンに基づいて、前記オブジェクトの1つの冗長な複製を識別するための1つまたはより多くの指令と、
前記冗長な複製を重複排除するための1つまたはより多くの指令とを含む、コンピュータ読取可能メモリ。
【請求項22】
前記冗長な複製に関連した前記インデックスの一部へ変化を書き込むための1つまたはより多くの指令をさらに含み、
前記変化は、前記冗長な複製についての重複排除レコードを含む、請求項21に記載のコンピュータ読取可能メモリ。
【請求項23】
前記インデックスに含まれる他のオブジェクトについてのリクエストを受信するための1つまたはより多くの指令と、
前記インデックスに基づいて、前記他のオブジェクトの複製をそれから読み出すためのストレージクラスタを選択するための1つまたはより多くの指令と、
前記選択されたストレージクラスタから、前記他のオブジェクトの前記複製を読み出すための1つまたはより多くの指令とをさらに含む、請求項21に記載のコンピュータ読取可能メモリ。
【請求項1】
分散型データ複製システムにおける複数の装置のうちの1つの装置によって実行される方法であって、
前記方法は、
前記分散型データ複製システムにおけるオブジェクトのインデックスを記憶するステップを備え、
前記インデックスは、オブジェクトの複製が前記分散型データ複製システムにおける前記複数の装置によって局部的に記憶される間に複製され、
前記方法は、
前記インデックスの少なくとも一部のスキャンを実行するステップと、
前記インデックスの前記スキャンに基づいて、前記オブジェクトの少なくとも1つの冗長な複製を識別するステップと、
前記インデックスの一部に、重複排除レコードを書き込むことによって、前記冗長な複製を重複排除するステップとを備える、方法。
【請求項2】
前記インデックスの変化は、前記分散型データ複製システムの下部複製層を用いて複製される、請求項1に記載の方法。
【請求項3】
前記装置は、前記インデックスの特定のサブセット内におけるオブジェクトについての冗長な複製を低減することに関与する唯一の装置である、請求項1に記載の方法。
【請求項4】
前記インデックスは、前記インデックスにおける各オブジェクトについてのコンテンツ処理を含む、コンテンツアドレス可能インデックスである、請求項1に記載の方法。
【請求項5】
前記オブジェクトの前記コンテンツ処理に関連した前記インデックスの一部に、データレコードまたは削除リクエストレコードを書き込むステップと、
前記オブジェクトの前記コンテンツ処理に関連した前記インデックスの一部を、前記複数の装置のうちの1つまたはより多くの他の装置に複製するステップとをさらに備える、請求項4に記載の方法。
【請求項6】
前記インデックスに含まれる他のオブジェクトについてのリクエストを受信するステップと、
前記インデックスに基づいて、前記他のオブジェクトの複製をそこから読み出すために、複数の装置の選択された装置を決定するステップと、
前記選択された装置から前記他のオブジェクトの複製を読み出すステップとをさらに備える、請求項1に記載の方法。
【請求項7】
前記冗長な複製を識別するステップは、2つまたはより多くの複製間の優先順を区別するための基準にさらに基づく、請求項1に記載の方法。
【請求項8】
前記インデックスは、前記装置における前記複製とは分離して記憶される、請求項1に記載の方法。
【請求項9】
分散型データ複製システムにおける複数の装置のうちの1つの装置であって、
前記装置は、
前記分散型データ複製システムにおけるオブジェクトのインデックスを記憶するための手段と、
前記インデックスへの変化を書き込んで、前記オブジェクトのうちの1つの複製の状態を指定するための手段と、
前記分散型データ複製システムにおいて、前記インデックスへの変化を、前記複数の装置に複製するための手段と、
前記インデックスの少なくとも一部のスキャンを実行する手段と、
前記インデックスの前記スキャンに基づいて、前記オブジェクトのうちの1つの冗長な複製を識別するための手段と、
前記冗長な複製を重複排除するための手段とを備える、装置。
【請求項10】
前記インデックスを更新して、重複排除された複製の状態を反映するための手段をさらに備える、請求項9に記載のシステム。
【請求項11】
システムであって、
指令、オブジェクトのデータストア、および前記データストア内の前記オブジェクトのインデックスを記憶するためのメモリと、
前記メモリにおける前記指令を実行して、以下を行なうプロセッサとを備え、
前記プロセッサは、
前記データストア内のオブジェクトの状態を識別し、前記状態は、前記オブジェクトが複製を有しているか否か、および削除リクエストが前記オブジェクトに関連しているか否かに関連し、
前記プロセッサは、
前記オブジェクトの前記状態に基づいて、前記インデックスへ、重複排除指定レコードを書込み、
前記重複排除指定レコードを有する前記インデックスを、1つまたはより多くの装置に複製し、
前記1つまたはより多くの装置のうちの1つから、前記オブジェクトに関連した他の重複排除指定レコードを受信し、
前記重複排除指定レコードおよび前記他の重複排除指定レコードは、前記オブジェクトの1つまたはより多くの複製の削除についての基準提供する、システム。
【請求項12】
前記重複排除指定レコードおよび前記他の重複排除指定レコードは、分散化マルチマスタデータ複製環境における複製層を用いて交換される、請求項11に記載のシステム。
【請求項13】
前記プロセッサは、前記インデックスの一部のスキャンを実行して、前記オブジェクトの冗長な複製を識別するようにさらに構成される、請求項11に記載のシステム。
【請求項14】
前記装置は、前記インデックスにおけるオブジェクトのサブセットの重複排除にもっぱら関与する、請求項11に記載のシステム。
【請求項15】
前記重複排除指定レコードは、
前記オブジェクトを記憶する前記装置についてのクラスタ識別と、
前記装置における前記オブジェクトの記憶位置についての位置識別と、
前記オブジェクトの重複排除状態についての指示セクションとを含む、請求項11に記載のシステム。
【請求項16】
前記指示セクションは、
前記オブジェクトの活性中の複製を示すためのデータ指示、
複製についての実行中の削除リクエストを示すための削除リクエスト指示、および
重複排除が選択された複製を示すための重複排除指示のうちの1つを含む、請求項15に記載のシステム。
【請求項17】
1つまたはより多くの装置によって実行される方法であって、
分散化データ複製システムにおける複数装置内のオブジェクトのインデックスを記憶するとともに、前記オブジェクトを局部的に記憶している間に、前記分散化データ複製システムを通して前記インデックスを複製するステップを備え、
各装置は、前記インデックスの特定のサブセットにおける前記オブジェクトの重複排除に関与し、
前記方法は、
前記インデックスの前記サブセットの各々のスキャンを実行して、前記スキャンに基づいて冗長な複製を識別するステップと、
前記冗長な複製を重複排除するステップと、
実行中の削除リクエストを有する複製を伴う装置からのオブジェクトを、以前に重複排除された複製を伴う装置に自動的にコピーするステップとをさらに備える、方法。
【請求項18】
前記オブジェクトの1つに関連した前記インデックスの一部へ変化を書き込むステップをさらに備え、
前記変化は、データレコード、削除リクエストレコード、または前記オブジェクトの複製についての重複排除レコードを含む、請求項17に記載の方法。
【請求項19】
前記分散化データ複製システムの下部複製層を用いて、前記インデックスへ前記変化を複製するステップをさらに備える、請求項17に記載の方法。
【請求項20】
前記インデックスは、前記インデックスにおける各オブジェクトについてのコンテンツ処理を含むコンテンツアドレス可能インデックスである、請求項17に記載の方法。
【請求項21】
コンピュータ実行可能指令を含むコンピュータ読取可能メモリであって、
前記コンピュータ読取可能メモリは、
分散化データ複製システムにおけるオブジェクトのインデックスの一部のスキャンを実行するための1つまたはより多くの指令と、
前記インデックスの一部の前記スキャンに基づいて、前記オブジェクトの1つの冗長な複製を識別するための1つまたはより多くの指令と、
前記冗長な複製を重複排除するための1つまたはより多くの指令とを含む、コンピュータ読取可能メモリ。
【請求項22】
前記冗長な複製に関連した前記インデックスの一部へ変化を書き込むための1つまたはより多くの指令をさらに含み、
前記変化は、前記冗長な複製についての重複排除レコードを含む、請求項21に記載のコンピュータ読取可能メモリ。
【請求項23】
前記インデックスに含まれる他のオブジェクトについてのリクエストを受信するための1つまたはより多くの指令と、
前記インデックスに基づいて、前記他のオブジェクトの複製をそれから読み出すためのストレージクラスタを選択するための1つまたはより多くの指令と、
前記選択されたストレージクラスタから、前記他のオブジェクトの前記複製を読み出すための1つまたはより多くの指令とをさらに含む、請求項21に記載のコンピュータ読取可能メモリ。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6A】
【図6B】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6A】
【図6B】
【図7】
【図8】
【図9】
【図10】
【図11】
【公表番号】特表2012−513640(P2012−513640A)
【公表日】平成24年6月14日(2012.6.14)
【国際特許分類】
【出願番号】特願2011−542576(P2011−542576)
【出願日】平成21年12月22日(2009.12.22)
【国際出願番号】PCT/US2009/069234
【国際公開番号】WO2010/075407
【国際公開日】平成22年7月1日(2010.7.1)
【出願人】(502208397)グーグル インコーポレイテッド (161)
【公表日】平成24年6月14日(2012.6.14)
【国際特許分類】
【出願日】平成21年12月22日(2009.12.22)
【国際出願番号】PCT/US2009/069234
【国際公開番号】WO2010/075407
【国際公開日】平成22年7月1日(2010.7.1)
【出願人】(502208397)グーグル インコーポレイテッド (161)
[ Back to top ]