JP6026738B2 - 重複排除記憶システムのスケーラビリティを向上させるシステムおよび方法 - Google Patents

Description

重複排除記憶システムは一般に、類似ファイル内で冗長なデータパターンを識別することにより、ファイルの保存に必要な記憶空間の量を減らすために用いられる。例えば、重複排除記憶システムは、複数のファイルをファイルセグメントに分割して、別のファイルから得られた少なくとも１個のファイルセグメントと同一である１個のファイルから得られた少なくとも１個のファイルセグメントを識別し得る。重複排除記憶システムは、特定のファイルセグメントの複数のインスタンスを保存するのではなく、当該ファイルセグメントの単一のインスタンスを保存して、複数のファイルがファイルセグメントの当該インスタンスだけを参照することにより、ファイルの保存に必要な記憶空間の量を減らすことができる。このように、重複排除記憶システムは通常、一意の（すなわち非冗長な）ファイルセグメントだけを保存する。

保存されているファイルセグメントが時期尚早に、または誤って削除されるのを防止すべく、重複排除記憶システムは、１個以上のバックアップ済みファイルが現在特定のファイルセグメントを参照しているか否かを各々示す複数の参照オブジェクト（参照リストおよび／または参照カウント等）を保持し得る。参照オブジェクトが、現在特定のファイルセグメントを参照しているファイルが無いことを示す場合、重複排除記憶システムは当該ファイルセグメントを削除して、同セグメントにより占有されていた記憶空間を再利用し得る。

残念ながら、このような参照オブジェクトは通常、時間の経過に伴い極めて巨大化して扱い難くなり得る単一のデータベースに保存されている。更に、従来の重複排除記憶システムは、特定のファイルセグメントを現在参照しているファイルに対応するよう参照オブジェクトを更新すべく、データベース全体の更新動作を実行することが必要な場合があり得るため、不必要な処理遅延および計算資源の制約が生じる恐れがある。このように、本開示は、重複排除記憶システムのスケーラビリティを向上させるシステムおよび方法の必要性を認識している。

以下に詳述するように、本開示は一般に、重複排除記憶システムのスケーラビリティを向上させるシステムおよび方法に関する。一例において、データ重複排除ソフトウェアはそのような目的を、（１）複数の参照オブジェクト（参照リストおよび／または参照カウント等）を保存するデータベースを識別し、（２）データベースの少なくとも１個のサイズ関連特徴（当該データベースに保存されている参照オブジェクトの数または参照オブジェクトが占有する保存スペースの量等）が所定の閾値に達したと判定し、（３）当該データベースを、互いに独立に更新可能な複数の部分データベースに分割し、（４）少なくとも１個の部分データベースに保存されている１個以上の参照オブジェクトを更新する更新動作の実行を要求するリクエストを識別して、（５）当該部分データベースの全数より少ない個数に対して更新動作を実行することにより達成してもよい。本例では、各参照オブジェクトは、１個以上のバックアップ済みファイルが現在、重複排除記憶システムに保存されている特定の一意のファイルセグメントを参照しているか否かを示し得る。

一例において、データ重複排除ソフトウェアはデータベースを部分データベースに分割したならば、１個以上の新たに生成された参照オブジェクトを保存する有効な部分データベースとして特定の部分データベースを指定し得る。例えば、データ重複排除ソフトウェアは、分割時点においてデータベース内で識別された参照オブジェクトを１個の部分データベースに保存し、次いで別の部分データベースを有効な部分データベースとして指定し得る。本例では、データ重複排除ソフトウェアは、有効な部分データベース内で、分割時点以降に少なくとも１個のファイルが重複排除記憶システムに追加された結果として生成された１個以上の新たな参照オブジェクトを保存し得る。

いくつかの例において、各参照オブジェクトは、重複排除記憶システムに保存されている一意のファイルセグメントを現在参照している１個以上の特定のバックアップ済みファイルを識別する参照リストであってもよい。そのような例において、当該部分データベースの全数より少ない個数に対して実行される更新動作は、部分データベースに保存されている１個以上の参照リストに参照子（例：フィンガープリントまたはハッシュ等）を追加する、または部分データベースに保存されている１個以上の参照リストから参照を削除するステップを含んでいてもよい。１個以上の参照リストに対して追加または削除された参照は、重複排除記憶システムに保存されている特定のバックアップ済みファイルを識別し得る。追加的または代替的に、当該部分データベースの全数より少ない個数に対して実行される更新動作は、１個の部分データベース（有効な部分データベース等）内で、重複排除記憶システムに追加された新たな一意のファイルセグメントを参照する１個以上のバックアップ済みファイルを識別する新たな参照リストを生成するステップを含んでいてもよい。

他の例において、各参照オブジェクトは、重複排除記憶システムに保存されている一意のファイルセグメントを現在参照しているバックアップ済みファイルの数を単に識別する参照カウントであってもよい。これらの例において、当該部分データベースの全数より少ない個数に対して実行される更新動作は、少なくとも１個の参照カウントを増減させて、特定の一意のファイルセグメントを現在参照しているバックアップ済みファイルの数を更新するステップを含んでいてもよい。追加的または代替的に、当該部分データベースの全数より少ない個数に対して実行される更新動作は、重複排除記憶システムに追加された新たな一意ファイルを現在参照しているバックアップ済みファイルセグメントの数を識別する新たな参照カウントを、１個の部分データベース内に、生成するステップを含んでいてもよい。

特定の実施形態において、重複排除記憶システムは、部分データベースに対する更新動作の実行を要求するリクエストを待ち行列に入れるトランザクションキューを含んでいてもよい。一例において、データ重複排除ソフトウェアは、トランザクションキュー内で、少なくとも１個の異なる部分データベースに対する別の更新動作の実行を要求する別のリクエストを識別し得る。本例では、データ重複排除ソフトウェアは、重複排除記憶システムの効率および性能を向上させるべく、異なる部分データベースに対して当該更新動作およびもう一方の更新動作を同時に実行し得る。

別の例において、データ重複排除ソフトウェアは、別の更新動作を実行すべく所定の数の別のリクエストを識別するまで当該更新動作の実行を延期し得る。例えば、データ重複排除ソフトウェアは、トランザクションキュー内で、当該更新動作と同一の部分データベースに対して別の更新動作の実行を要求する別のリクエストを識別し得る。本例では、データ重複排除ソフトウェアは、トランザクションキュー内で識別される別のリクエストの数が所定の数に達したと判定されたならば、重複排除記憶システムの効率および性能を向上させるべく、同一の部分データベースに対して当該更新動作およびもう一方の更新動作を順次実行し得る。

以下に詳述するように、本明細書に記述するシステムおよび方法は、巨大で扱い難いデータベースをより小さい部分データベースに分割することにより、重複排除記憶システムのスケーラビリティを向上させてもよい。特に、本明細書に記述する各種のシステムおよび方法は、個数が制限された部分データベースに対して更新動作を実行することにより、重複排除記憶システムが、巨大で扱い難いデータベースに対してそのような更新動作を実行するのに伴う処理コストを回避可能にさせ得る。

本明細書に記述する一般的原理に従い、上述の実施形態の任意の特徴を互いに組み合わせて用い得る。これらおよび他の実施形態、特徴、および利点は、添付の図面および請求項と合わせて以下の詳細な説明を精査すればより完全に理解されよう。

添付の図面は、多くの例示的な実施形態を示すと共に、本明細書の一部をなす。これらの図面は、以下の説明と共に、本開示の各種の原理を例示および説明するものである。

重複排除記憶システムのスケーラビリティを向上させる例示的なシステムのブロック図である。 重複排除記憶システムのスケーラビリティを向上させる例示的なシステムのブロック図である。 重複排除記憶システムのスケーラビリティを向上させる例示的な方法のフロー図である。 少なくとも１個の部分データベースおよび例示的な参照リストに対して更新動作を実行する例示的なリクエストを示す図である。 本明細書に記述および／または図示する１個以上の実施形態を実装可能な例示的コンピュータシステムのブロック図である。 本明細書に記述および／または例示する１個以上の実施形態を実装可能な例示的な計算ネットワークのブロック図である。

これら図面全体を通じて、同一の参照符号および記述は同様の、しかし必ずしも同一ではない要素を示す。本明細書に記述する例示的な実施形態には各種の変型および代替方式があり得るが、特定の実施形態を例として図面に示して本明細書において詳述する。しかし、本明細書に記述する例示的な実施形態は、開示する特定の形式に限定することを意図していない。むしろ、本開示は、添付の請求範囲内で全ての変型、均等物、および代替物を包含している。

以下に詳述するように、本開示は一般に、重複排除記憶システムのスケーラビリティを向上させるシステムおよび方法に関する。本明細書で用いる「重複排除記憶システム」という用語は一般に、バックアップ済みファイル内の冗長なデータパターンを識別してデータの単一インスタンスだけを保存することによりそのような冗長性を無くすことが可能な任意の種類または形式の記憶システムまたは装置に関する。以下に詳述するように、データの当該単一インスタンスは、重複排除記憶システムでバックアップされた単一のファイルまたは複数のファイルにより参照され得る。

図１、２を参照しながら、重複排除記憶システムのスケーラビリティを向上させる例示的なシステムについて以下に詳細に説明する。対応するコンピュータ実装された方法の詳細な説明もまた図３、４を参照しながら与える。また、本明細書に記述する１個以上の実施形態を実装可能な例示的コンピュータシステムおよびネットワークアーキテクチャの詳細について各々図５、６を参照しながら説明する。

図１は、重複排除記憶システムのスケーラビリティを向上させる例示的なシステム１００のブロック図である。本図に示すように、例示的なシステム１００は、１個以上のタスクを実行する１個以上のモジュール１０２を含んでいてもよい。例えば、以下に詳述するように、例示的なシステム１００は、複数の参照オブジェクト（参照リストおよび／または参照カウント等）を保存するデータベースを識別すべくプログラムされた識別モジュール１０４を含んでいてもよい。各参照オブジェクトは、１個以上のバックアップ済みファイルが、重複排除記憶システムに保存されている特定の一意のファイルセグメントを現在参照しているか否かを示し得る。

また、以下に詳述するように、例示的なシステム１００は、データベース（データベースに保存されている参照オブジェクトの数または参照オブジェクトにより占有される記憶空間の量等）の少なくとも１個のサイズ関連特徴が所定の閾値に達したと判定すべくプログラムされた分割モジュール１０６を含んでいてもよい。データベースのサイズ関連特徴が所定の閾値に達したと判定されたならば、分割モジュール１０６はデータベースを、互いに独立に更新可能な複数の部分データベースに分割し得る。

例示的なシステム１００はまた、少なくとも１個の部分データベースに保存されている１個以上の参照オブジェクトを更新する更新動作の実行を要求するリクエストを識別し、次いで当該部分データベースの全数より少ない個数に対して要求された更新動作実行すべくプログラムされた更新モジュール１０８を含んでいてよい。別々の要素として例示されているが、図１の１個以上のモジュール１０２は単一のモジュールまたはアプリケーション（データ重複排除ソフトウェア（例：シマンテック社のＮＥＴＢＡＣＫＵＰ ＰＵＲＥＤＩＳＫ）等）の一部を表していてもよい。

特定の実施形態において、図１の１個以上のモジュール１０２は、計算装置により実行された際に、当該計算装置に１個以上のタスクを実行させ得る１個以上のソフトウェアアプリケーションまたはプログラムを表していてもよい。例えば、以下に詳述するように、１個以上のモジュール１０２は、図２に示す装置（例：計算装置２０２（１）〜（Ｎ）および／またはサーバ２０６）、図５の計算システム５１０、および／または図６の例示的なネットワークアーキテクチャ６００の一部等、１個以上の計算装置で動作すべく保存および構成されたソフトウエアモジュールを表していてもよい。図１の１個以上のモジュール１０２はまた、１個以上のタスクを実行すべく構成された１個以上の専用コンピュータの全体または一部を表していてもよい。

図１に示すように、例示的なシステム１００はまた、１個以上のデータベース１２０を含んでいてもよい。データベース１２０は、単一のデータベースまたは計算装置の一部または複数のデータベースまたは計算装置を表していてもよい。いくつかの実施形態において、例示的なシステム１００は、１個以上のバックアップ済みファイルが、重複排除記憶システムに保存されている特定の一意のファイルセグメントを現在参照しているか否かを各々示す参照オブジェクトを保存すべく構成された参照オブジェクトデータベース１２２を含んでいてもよい。

一実施形態において、例示的なシステム１００はまた、参照オブジェクトデータベース１２２から分割された１個以上の部分データベース１２６（１）〜（Ｎ）を含んでいてもよい。また、例示的なシステム１００は、重複排除記憶システムに保存されているバックアップ済みファイルの一部を表す一意のファイルセグメントを保存すべく構成されたファイルセグメントデータベース１２４を含んでいてもよい。図１には示していないが、一実施形態において、参照オブジェクトおよび対応するファイルセグメントは単一のデータベースに保存されていてもよい。

図１のデータベース１２０は、１個以上の計算装置の一部を表していてもよい。例えば、データベース１２０は、図２のサーバ２０６の一部、図５の計算システム５１０、および／または図６の例示的なネットワークアーキテクチャ６００の一部を表していてもよい。あるいは、図１のデータベース１２０は、図２のサーバ２０６、図５の計算システム５１０、および／または図６の例示的なネットワークアーキテクチャ６００の一部等の計算装置によりアクセス可能な１個以上の物理的に別々の装置を表していてもよい。

図１の例示的なシステム１００は、各種の方法で実現し得る。例えば、例示的なシステム１００の全体または一部が、図２の例示的な重複排除記憶システム２００の一部を表していてもよい。図２に示すように、重複排除記憶システム２００は、ネットワーク２０４を介してサーバ２０６と通信する１個以上の計算装置２０２（１）〜（Ｎ）を含んでいてもよい。重複排除記憶システム２００はまた、１個以上のモジュール１０２および／またはデータベース１２０を含んでいてもよい。

一実施形態において、また以下に詳述するように、サーバ２０６は、（１）複数の参照オブジェクト（参照リストおよび／または参照カウント等）を保存するデータベース（例：参照オブジェクトデータベース１２２）を識別し、（２）データベースの少なくとも１個のサイズ関連特徴（データベースに保存されている参照オブジェクトの数または参照オブジェクトにより占有される記憶空間の量等）が所定の閾値に達したと判定し、（３）当該データベースを、互いに独立に更新可能な複数の部分データベース（部分データベース１２６（１）〜（Ｎ））に分割し、（４）少なくとも１個の部分データベースに保存されている１個以上の参照オブジェクトを更新する更新動作の実行を要求するリクエストを識別し、次いで（５）部分データベースの全数（すなわちデータベース全体）に対する更新動作の実行に伴う処理コストを回避すべく全数より少ない個数の部分データベースに対して更新動作を実行することにより、重複排除記憶システム２００のスケーラビリティを向上させるべく１個以上のモジュール１０２によりプログラムされていてもよい。

計算装置２０２（１）〜（Ｎ）は一般に、コンピュータ実行可能命令の読出しおよびネットワーク２０４を介してサーバ２０６と通信可能な任意の種類または形式の計算装置を表していてよい。計算装置２０２（１）〜（Ｎ）の例として、ラップトップ、デスクトップ、サーバ、携帯電話、携帯情報端末（ＰＤＡ）、マルチメディアプレーヤー、組み込みシステム、これらの１個以上の組合せ、図５の例示的な計算システム５１０、または他の任意の適当な計算装置が含まれるが、これらに限定されない。

サーバ２０６は一般に、重複排除記憶システム２００の一部として重複排除およびデータ保存が可能な任意の種類または形式の計算装置を表していてよい。サーバ２０６の例として、各種のデータベースサービス、バックアップサービスを提供すべく、および／または特定のソフトウェアアプリケーションを実行すべく構成されたアプリケーションサーバ、バックアップサーバ、およびデータベースサーバが含まれるが、これらに限定されない。

ネットワーク２０４は一般に、通信またはデータ転送を容易にすることが可能な任意の媒体またはアーキテクチャを表す。ネットワーク２０４の例として、イントラネット、広域ネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、パーソナルエリアネットワーク（ＰＡＮ）、インターネット、電力線通信（ＰＬＣ）、セルラネットワーク（例：ＧＳＭネットワーク）、図６の例示的なネットワークアーキテクチャ６００等が含まれるが、これらに限定されない。ネットワーク２０４は、無線または有線接続を用いた通信またはデータ転送を容易にし得る。一実施形態において、ネットワーク２０４は計算装置２０２（１）〜（Ｎ）とサーバ２０６間の通信を容易にし得る。

図３は、重複排除記憶システムのスケーラビリティを向上させる例示的なコンピュータに実装された方法３００のフロー図である。図３に示すステップは、任意の適当なコンピュータ実行可能コードおよび／または計算システムにより実行し得る。いくつかの実施形態において、図３に示すステップは、図１のシステム１００の構成要素、図２の重複排除記憶システム２００、図５の計算システム５１０、および／または図６の例示的なネットワークアーキテクチャ６００の一部のうち１個以上により実行し得る。

図３に示すように、ステップ３０２において、本明細書に記述する各種システムの１個以上により、複数の参照オブジェクトを保存するデータベースを識別し得る。例えば、識別モジュール１０４は、図２のサーバ２０６の一部として、複数の参照オブジェクトを保存する参照オブジェクトデータベース１２２を識別し得る。本例では、参照オブジェクトデータベース１２２に保存されている各参照オブジェクトは、１個以上のバックアップ済みファイルが、重複排除記憶システム２００（例えばファイルセグメントデータベース１２４内の）に保存されている特定の一意のファイルセグメントを現在参照しているか否かを示し得る。また、各参照オブジェクトに関連付けられた一意のファイルセグメントは、１個以上のバックアップ済みファイルの一部を表していてもよい。

本明細書に記述するシステムは、各種の方法でステップ３０２を実行し得る。一例において、識別モジュール１０４は、重複排除記憶システム２００が構築、構成、または初期化されたならば、参照オブジェクトデータベース１２２を識別し得る。別の例において、識別モジュール１０４は、第１の参照オブジェクトが生成されて参照オブジェクトデータベース１２２に保存された際に参照オブジェクトデータベース１２２を識別し得る。

本明細書で用いる「参照オブジェクト」という用語は一般に、１個以上のバックアップ済みファイルが、重複排除記憶システム２００に保存されている特定の一意のファイルセグメントを現在参照しているか否かを示すことが可能な任意の種類または形式の参照子または識別子を指す。そのような参照オブジェクトの例として、重複排除記憶システム２００に保存されている一意のファイルセグメントを現在参照している１個以上の特定のバックアップ済みファイルを識別する参照リスト（図４の参照リスト４０２等）、重複排除記憶システム２００に保存されている一意のファイルセグメントを現在参照しているバックアップ済みファイルの数を単に識別する参照カウント、あるいは１個以上のバックアップ済みファイルが、重複排除記憶システム２００に保存されている特定の一意のファイルセグメントを現在参照しているか否かを識別可能な他の任意の適当な参照子が含まれるが、これらに限定されない。

再び図３を参照するに、ステップ３０４において、本明細書に記述する各種システムは、データベースの少なくとも１個のサイズ関連特徴が所定の閾値に達したと判定し得る。例えば、分割モジュール１０６は、図２のサーバ２０６の一部として、参照オブジェクトデータベース１２２に保存されている参照オブジェクトの数が所定の閾値に達したと判定し得る。別の例において、分割モジュール１０６は、参照オブジェクトデータベース１２２に保存されている参照オブジェクトが、重複排除記憶システム２００の所定量の記憶空間を消費していると判定し得る。

本明細書に記述するシステムは、各種の方法でステップ３０４を実行し得る。一例において、分割モジュール１０６は、参照オブジェクトデータベース１２２を監視して所定の閾値に達した参照オブジェクトデータベース１２２のサイズ関連特徴を識別し得る。例えば、分割モジュール１０６は、参照オブジェクトデータベース１２２に保存されている参照オブジェクトの数をカウントして、カウントされた参照オブジェクトの数が所定の閾値に達したかまたは上回ったと判定し得る。別の例において、分割モジュール１０６は、参照オブジェクトデータベース１２２を監視すべく構成された別のソフトウェア構成要素から、参照オブジェクトデータベース１２２のサイズ関連特徴が所定の閾値に達したことを示す通知を受け取り得る。

再び図３を参照するに、ステップ３０６において、本明細書に記述する各種システムはデータベースを、互いに独立に更新可能な複数の部分データベースに分割し得る。例えば、分割モジュール１０６は、図２のサーバ２０６の一部として、参照オブジェクトデータベース１２２を部分データベース１２６（１）〜（Ｎ）に分割し得る。本例では、部分データベース１２６（１）〜（Ｎ）は各々、参照オブジェクトデータベース１２２に割り当てられた記憶空間の一部を表していてよく、各々の部分データベース１２６（１）〜（Ｎ）は互いに独立に更新できるため部分データベースの全数１２６（１）〜（Ｎ）（実質的に参照オブジェクトデータベース１２２に等価である）を同時に更新することに伴う処理コストを減らし得る。また、分割モジュール１０６は、局所性の原理に基づいて参照オブジェクトを保存すべく部分データベース１２６（１）〜（Ｎ）を構成し得る。

本明細書に記述するシステムは、各種の方法でステップ３０６を実行し得る。一例において、分割モジュール１０６は、分割時点において参照オブジェクトデータベース１２２内で識別された参照オブジェクトを部分データベース１２６（１）内に保存し得る。本例では、分割モジュール１０６は、参照オブジェクトデータベース１２２が分割された後で少なくとも１個のファイルが重複排除記憶システム２００に追加された結果として生成された１個以上の新たな参照オブジェクトを保存する有効な部分データベースとして部分データベース１２６（Ｎ）を指定し得る。

いくつかの実施形態において、分割モジュール１０６は、参照オブジェクトデータベース１２２を２個の部分データベースに単に分割して、一方の部分データベースが分割時点において参照オブジェクトデータベース１２２内で識別された参照オブジェクトを保存し、もう一方の部分データベースが新たな参照オブジェクトを保存する有効な部分データベースであるようにしてもよい。そのような実施形態において、分割モジュール１０６は更に、必要に応じて（例えば、ある部分データベースの少なくとも１個のサイズ関連特徴が所定の閾値に達したと判定された場合）少なくとも１個の部分データベースを追加的な部分データベースに分割してもよい。

他の実施形態において、分割モジュール１０６は、参照オブジェクトデータベース１２２のサイズ関連特徴が所定の閾値に達したと判定されたならば直ちに、参照オブジェクトデータベース１２２を複数の部分データベース（例えば１００個の部分データベース）に分割し得る。例えば、分割モジュール１０６は、参照オブジェクトデータベース１２２を１００個の異なるデータベースに分割して、少なくとも１個の部分データベースが分割時点において参照オブジェクトデータベース１２２内で識別された参照オブジェクトを保存し、他の１個の部分データベースが新たな参照オブジェクトを保存する有効な部分データベースであるようしてもよい。本例では、いくつかの部分データベースは無効であって、分割モジュール１０６がそのような部分データベースを新たな参照オブジェクトを保存する有効な部分データベースとして指定するまで空のままであってもよい。

再び図３を参照するに、ステップ３０８において、本明細書に記述する各種システムは、少なくとも１個の部分データベース内で１個以上の参照オブジェクトを更新する更新動作の実行を要求するリクエストを識別し得る。例えば、更新モジュール１０８は、図２のサーバ２０６の一部として、部分データベース１２６（Ｎ）に保存されている複数の参照オブジェクトを更新する更新動作の実行を要求するリクエスト（図４のリクエスト４００等）を識別し得る。以下に詳述するように、要求された更新動作は、重複排除記憶システム２００を管理するための各種動作のいずれかを含んでいてもよい。

本明細書に記述するシステムは、各種の方法でステップ３０８を実行し得る。いくつかの実施形態において、図２の重複排除記憶システム２００は、更新動作の実行を要求するリクエストを待ち行列に入れるトランザクションキューを含んでいてもよい。トランザクションキューは、要求された更新動作を、対応するリクエストがトランザクションキューに入れられた順序で実行するのを容易にすべく構成された先入れ先出し（ＦＩＦＯ）方式であってもよい。一例において、更新モジュール１０８は、計算装置２０２（１）がリクエストをネットワーク２０４を介してトランザクションキューに入れた際に更新動作の実行を要求するリクエストを識別してもよい。別の例において、更新モジュール１０８は、トランザクションキュー内で、リクエストが次に実行される場合に更新動作の実行を要求するリクエストを識別してもよい。

図４に示すように、リクエスト４００は、実行したい更新動作（本例では、「ファイル参照子を参照リストに追加」）を識別する情報、更新したい参照オブジェクト（本例では「０ｘＥＦ９Ａ０３４９」）に関連付けられた一意のファイルセグメントを参照するバックアップ済みファイルの参照子（例：フィンガープリントまたはハッシュ）、更新したい参照オブジェクト（本例では「０ｘＡ２Ｆ１Ｂ９２１」）に関連付けられた一意のファイルセグメントの参照子（例：フィンガープリントまたはハッシュ）、参照オブジェクトが保存されている部分データベース（本例では「部分データベース１２６（Ｎ）」）を識別する部分データベース識別子、およびリクエスト４００がトランザクションキューに入れられた時刻を示すタイムスタンプを含んでいてもよい。

１個以上の実施形態において、更新モジュール１０８は、タイムスタンプが示す時刻に基づいて、トランザクションキュー内で待ち行列に入れられたリクエストをソートし得る。複数のリクエストに含まれる複数のタイムスタンプが同一時刻を示す場合、更新モジュール１０８は更に、参照オブジェクトに関連付けられた一意のファイルセグメントの参照子に基づいてそれらのリクエストをソートし得る。また、更新モジュール１０８は、参照オブジェクトに関連付けられた一意のファイルセグメントの参照子に基づいて、データベース１２６（１）〜（Ｎ）に保存されている参照オブジェクトをソート（または部分データベース１２６（１）〜（Ｎ）に保存されている参照オブジェクトがソート済みであることを保証）し得る。以下に詳述するように、トランザクションキューおよび部分データベース１２６（１）〜（Ｎ）をこのようにソートすることにより、更新モジュール１０８は、トランザクションキューを部分データベース１２６（１）〜（Ｎ）の少なくとも１個（但し全部ではない）に保存されている参照オブジェクトと単にマージする（マージソートの一部として）ことにより、要求された更新動作を実行し得る。

再び図３を参照するに、ステップ３１０において、本明細書に記述する各種システムは、部分データベースの全数に対する更新動作の実行に伴う処理コストを回避すべく全数より少ない個数の部分データベースに対して更新動作を実行し得る。例えば、更新モジュール１０８は、図２のサーバ２０６の一部として、部分データベース１２６（Ｎ）に保存されている複数の参照オブジェクトに対して要求された更新動作を実行し得る。本例では、部分データベース１２６（Ｎ）に対して更新動作を処理するだけで、更新モジュール１０８は、更新動作の影響を受けない他の参照オブジェクト（例：部分データベース１２６（１）に保存されている参照オブジェクト）を検索することにより生じる処理コストを回避し得る。

本明細書に記述するシステムは、各種の方法でステップ３１０を実行し得る。一例において、重複排除記憶システム２００にファイルが追加された場合、更新動作は、バックアップ済みファイルの一部を表すファイルセグメントに関連付けられた参照リストに、バックアップ済みファイルを識別する参照子を追加し得る。本例では、参照リストに追加される参照子は、バックアップ済みファイルのフィンガープリントまたはハッシュを含む任意の種類または形式のファイル参照子または識別子であってもよい。同様の例において、重複排除記憶システム２００にファイルが追加された場合、更新動作は参照カウントを増やして、増加した数のバックアップ済みファイルが参照カウントに関連付けられたファイルセグメントを現在参照していることを示し得る。

別の例において、重複排除記憶システム２００からファイルが削除された場合、更新動作は、前のバックアップ済みファイルの一部を表すファイルセグメントに関連付けられた参照リストから、前のバックアップ済みファイルを識別する参照子を削除し得る。本例では、参照リストから削除される参照子は、バックアップ済みファイルのフィンガープリントまたはハッシュを含む任意の種類または形式のファイル参照子または識別子であってもよい。更に別の例において、重複排除記憶システム２００からファイルが削除された場合、更新動作は参照カウントを減らして、減少した数のバックアップ済みファイルが参照カウントに関連付けられたファイルセグメントを現在参照していることを示し得る。

更なる例において、重複排除記憶システム２００に追加されたファイルが一意のファイルセグメントとして保存されなかったデータの少なくとも一部を含んでいる場合、更新動作はまた、重複排除記憶システム２００に追加された新たな一意ファイルを参照する１個以上のバックアップ済みファイルを識別する新たな参照リストを有効な部分データベース内に生成し得る。まだ更なる例において、重複排除記憶システム２００に追加されたファイルが一意のファイルセグメントとして保存されなかったデータの少なくとも一部を含んでいる場合、更新動作は、重複排除記憶システム２００に追加された新たな一意ファイルを現在参照しているバックアップ済みファイルの数を識別する新たな参照カウントを部分データベース内に生成し得る。

１個以上の実施形態において、参照リストから前のバックアップ済みファイルを識別する参照子を削除したならば、あるいは参照カウントを減らしたならば、更新モジュール１０８は、参照リストまたは参照カウントが、どのバックアップ済みファイルも特定の一意のファイルセグメントを現在参照していないことを示していると判定し得る。このような実施形態において、更新モジュール１０８は、重複排除記憶システム２００が再利用できるように参照リストまたは参照カウントに関連付けられた一意のファイルセグメントにマーク付けし得る。例えば、重複排除記憶システム２００は、記憶再利用動作の一部として、マーク付けされたファイルセグメントを削除して、同セグメントが占有していた記憶空間を再利用し得る。

いくつかの実施形態において、更新動作が以前に生成された少なくとも１個の参照オブジェクトの更新を含んでいる場合、更新モジュール１０８は、更新動作の実行に先立って更新動作の影響を受ける参照オブジェクトを保存する部分データベースを識別し得る。例えば、更新モジュール１０８は、部分データベース１２６（Ｎ）が、重複排除記憶システム２００内で修正されたバックアップ済みファイルの一部を表す特定の一意のファイルセグメントに関連付けられた参照リストを保存していると判定し得る。

一例において、更新モジュール１０８は、これらの参照リストに関連付けられた一意のファイルセグメントを識別して、局所性原理と合わせて一意のファイルセグメントを用いて、部分データベース１２６（Ｎ）がこれらの参照リストの保存場所であると識別することにより、これらの参照リストが部分データベース１２６（Ｎ）に保存されていると判定し得る。別の例において、更新モジュール１０８は、更新動作の実行を要求するリクエスト内で、部分データベース１２６（Ｎ）がこれらの参照リストの保存場所であると識別する部分データベース識別子（図４のリクエスト４００に含まれる部分データベース識別子）を特定することにより、これらの参照リストが部分データベース１２６（Ｎ）に保存されていると判定し得る。

更に図４に示すように、参照リスト４０２は、参照リスト４０２（本例では「０ｘＡ２Ｆ１Ｂ９２１」）に関連付けられた一意のファイルセグメント参照子、および参照リスト４０２（本例では「０ｘ１７３８Ｆ１２Ａ」、「０ｘＤ１２８Ｂ３７９」、および「０ｘＥＦ９Ａ０３４９」）に関連付けられた一意のファイルセグメントを参照するバックアップ済みファイルの参照リストを識別する情報を含んでいてもよい。本例では、参照子０ｘＡ２Ｆ１Ｂ９２１で表される一意のファイルセグメントは、参照子０ｘ１７３８Ｆ１２Ａ、０ｘＤ１２８Ｂ３７９、および０ｘＥＦ９Ａ０３４９で表される各々のバックアップ済みファイルの一部を構成または生成することができる。このように、参照子０ｘ１７３８Ｆ１２Ａ、０ｘＤ１２８Ｂ３７９、および０ｘＥＦ９Ａ０３４９で表されるバックアップ済みファイルは、互いに同一のデータの少なくとも一部を共有していてもよい。

１個以上の実施形態において、更新モジュール１０８は、重複排除記憶システム２００の効率および性能の最適化を試みる各種の技術を実装し得る。一例において、更新モジュール１０８は、少なくとも１個の異なる部分データベースに保存されている１個以上の参照オブジェクトを更新する別の更新動作の実行を要求する別のリクエストを識別し得る。本例では、更新モジュール１０８は次いで、異なる部分データベースに対する更新動作およびもう一方の更新動作を同時に実行し得る。例えば、部分データベース１２６（１）に保存されている参照リストに対する別の更新動作の実行を要求する別のリクエストを識別したならば、更新モジュール１０８は、部分データベース１２６（Ｎ）に対する更新動作および部分データベース１２６（１）に対する別の更新動作を同時に実行し得る。

別の例において、更新モジュール１０８は、当該更新動作と同一の部分データベースに対する別の更新動作の実行を要求する所定の数の別のリクエストを識別するまで、更新動作の実行を延期（または遅延）し得る。例えば、更新動作の実行に先立って、更新モジュール１０８は、部分データベース１２６（Ｎ）に対する別の更新動作の実行を要求する各種の別のリクエストをトランザクションキュー内で識別し得る。本例では、更新モジュール１０８は次いで、トランザクションキュー内で識別された別のリクエストの数が、別のリクエスト所定数に達したと判定し得る。

トランザクションキュー内で識別された別のリクエストの数が別のリクエストの所定数に達したと判定された後で、更新モジュール１０８は、部分データベース１２６（Ｎ）に対して更新動作およびもう一方の更新動作を順次実行し得る。例えば、トランザクションキューおよび部分データベース１２６（Ｎ）が（上述の）マージソートの一環としてソートされている場合、更新モジュール１０８は、単にトランザクションキューを部分データベース１２６（Ｎ）に保存されている参照オブジェクトにマージすることにより、部分データベース１２６（Ｎ）に対する更新動作およびもう一方の更新動作を実行し得る。より具体的には、更新モジュール１０８は、トランザクションキューを部分データベース１２６（Ｎ）に保存されている参照オブジェクトにマージするために、トランザクションキューと部分データベース１２６（Ｎ）の単一パスすなわち比較を実行することにより、部分データベース１２６（Ｎ）に保存されている、影響を受けた参照オブジェクトを識別し得る。ステップ３１０が完了したならば、図３の例示的な方法３００を終了し得る。

上述のように、本明細書に記述するシステムおよび方法は、巨大で扱い難いデータベースをより小さい部分データベースに分割することにより、重複排除記憶システムのスケーラビリティを向上させ得る。特に、本明細書に記述する各種システムおよび方法は、個数が制限された部分データベースに対して更新動作を実行することにより、重複排除記憶システムが、巨大で扱い難いデータベースに対してそのような更新動作を実行することに伴う処理コストを回避できるようにし得る。

図５は、本明細書に記述および／または例示する１個以上の実施形態を実装可能な例示的な計算システム５１０のブロック図である。計算システム５１０は概ね、任意のシングルまたはマルチプロセッサ計算装置、あるいはコンピュータ可読な命令を実行可能なシステムを表している。計算システム５１０の例として、ワークステーション、ラップトップ、クライアント側端末、サーバ、分散計算システム、携帯機器、または他の任意の計算システムまたは装置が含まれるが、これらに限定されない。計算システム５１０は、その最も基本的な構成において、少なくとも１個のプロセッサ５１４およびシステムメモリ５１６を含んでいてもよい。

プロセッサ５１４は一般に、データの処理または命令の解釈および実行を行うことができる任意の種類または形式の処理ユニットを表している。特定の実施形態において、プロセッサ５１４は、ソフトウェアアプリケーションまたはモジュールから命令を受け取り得る。これらの命令はプロセッサ５１４に、本明細書に記述および／または図示する１個以上の例示的な実施形態の機能を実行させ得る。例えば、プロセッサ５１４は、単独で、または他の要素と組み合わせて、本明細書に記述するステップの識別、判定、分割、実行、保存、指定、追加、削除、生成、マーク付け、および延期のうち１個以上を実行可能および／または実行するための手段であってもよい。プロセッサ５１４はまた、本明細書に示す他の任意のステップ、方法、または処理を実行してもよく、および／または実行するための手段であってもよい。

システムメモリ５１６は一般に、データおよび／または他のコンピュータ可読な命令を保存ができる任意の種類または形式の揮発性または不揮発性記憶システム装置または媒体を表している。システムメモリ５１６の例として、ランダムアクセスメモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、フラッシュメモリ、または他の任意の適当なメモリ装置を含んでいるが、これらに限定されない。必須ではないが、特定の実施形態において、計算システム５１０は揮発性メモリ装置（システムメモリ５１６）および不揮発性記憶装置（以下に詳細に記載するように、例えば一次記憶装置５３２）を含んでいてもよい。一例において、図１のモジュール１０２の１個以上がシステムメモリ５１６に搭載されていてもよい。

特定の実施形態において、例示的な計算システム５１０はまた、プロセッサ５１４およびシステムメモリ５１６に加えて１個以上の構成要素または要素を含んでいてもよい。例えば、図５に示すように、計算システム５１０は、各々通信基盤５１２を介して相互接続し得る、メモリコントローラ５１８、入出力（Ｉ／Ｏ）コントローラ５２０、および通信インターフェース５２２を含んでいてもよい。通信基盤５１２は一般に、計算装置の１個以上の構成要素間の通信を容易にすることができる任意の種類または形式の基盤を表している。通信基盤５１２の例として、通信バス（ＩＳＡ、ＰＣＩ、ＰＣＩｅ等、または同様のバス）およびネットワークが含まれるが、これらに限定されない。

メモリコントローラ５１８は一般に、計算システム５１０の１個以上の構成要素間でメモリやデータの取り扱いまたは通信制御が行える任意の種類または形式の装置を表している。例えば、特定の実施形態において、メモリコントローラ５１８は通信基盤５１２を介して、プロセッサ５１４、システムメモリ５１６、および入出力コントローラ５２０の間の通信を制御し得る。特定の実施形態において、メモリコントローラ５１８は、単独で、または他の要素と組み合わせて、本明細書に記述および／または図示する１個以上のステップまたは特徴の識別、判定、分割、実行、保存、指定、追加、削除、生成、マーク付け、および延期を実行してもよく、および／または実行するための手段であってもよい。

入出力コントローラ５２０は一般に、計算装置の入出力機能の調整および／または制御を行うことができる任意の種類または形式のモジュールを表している。例えば、特定の実施形態において、入出力コントローラ５２０は、プロセッサ５１４、システムメモリ５１６、通信インターフェース５２２、ディスプレイアダプタ５２６、入力インターフェース５３０、および記憶ンターフェース５３４等、計算システム５１０の１個以上の要素間のデータ転送を制御または容易にし得る。入出力コントローラ５２０は、単独で、または他の要素と組み合わせて、例えば、本明細書に記述するステップを識別、判定、分割、実行、保存、指定、追加、削除、生成、マーク付け、および延期のうち１個以上を実行するために使用してもよく、および／または実行するための手段であってもよい。入出力コントローラ５２０はまた、本開示において記述した他のステップおよび特徴を実行するために使用してもよく、および／または実行するための手段であってもよい。

通信インターフェース５２２は概ね、例示的な計算システム５１０と１個以上の追加的な装置の間の通信を容易にすることができる任意の種類または形式の通信装置またはアダプタを表している。例えば、特定の実施形態において、通信インターフェース５２２は、計算システム５１０と追加的な計算システムを含む私的または公的ネットワーク間の通信およびを容易にし得る。通信インターフェース５２２の例として、有線ネットワークインターフェース（ネットワークインターフェースカード等）、無線ネットワークインターフェース（無線ネットワークインターフェースカード等）、モデム、および他の任意の適当なインターフェースを含んでいるが、これらに限定されない。少なくとも１個の実施形態において、通信インターフェース５２２は、インターネット等のネットワークへの直接的な接続を介して遠隔サーバに直接接続し得る。通信インターフェース５２２はまた、例えばローカルエリアネットワーク（イーサネットネットワーク等）、パーソナルエリアネットワーク、電話またはケーブルネットワーク、携帯電話接続、衛星データ接続、または他の任意の適当な接続を介してそのような接続を間接的に行い得る。

特定の実施形態において、通信インターフェース５２２はまた、外部バスまたは通信チャネルを介して計算システム５１０と１個以上の追加的なネットワークまたは記憶システムとの間の通信を容易にすべく構成されたホストアダプタを表していてもよい。ホストアダプタの例として、ＳＣＳＩホストアダプタ、ＵＳＢホストアダプタ、ＩＥＥＥ１３９４ホストアダプタ、ＳＡＴＡおよびｅＳＡＴＡホストアダプタ、ＡＴＡおよびＰＡＴＡがホストアダプタ、ファイバーチャネルインターフェースアダプタ、イーサネット・アダプタ等が含まれるが、これらに限定されない。通信インターフェース５２２により、計算システム５１０が分散または遠隔計算に係わることも可能になり得る。例えば、通信インターフェース５２２は、実行のため遠隔装置から命令を受信、および遠隔装置に命令を送信し得る。特定の実施形態において、通信インターフェース５２２は、単独で、または他の要素と組み合わせて、本明細書に開示するステップの識別、判定、分割、実行、保存、指定、追加、削除、生成、マーク付け、および延期のうち１個以上を実行してもよく、および／または実行するための手段であってもよい。通信インターフェース５２２はまた、本開示に記述する他のステップおよび特徴を実行するために使用してもよく、および／または実行するための手段であってもよい。

図５に示すように、計算システム５１０はまた、ディスプレイアダプタ５２６を介して通信基盤５１２に接続された少なくとも１個のディスプレイ装置５２４を含んでいてもよい。ディスプレイ装置５２４は一般に、ディスプレイアダプタ５２６により転送された情報を視覚的に表示できる任意の種類または形式の装置を表している。同様に、ディスプレイアダプタ５２６は一般に、ディスプレイ装置５２４上で表示すべく通信基盤５１２から（または当分野で公知のフレームバッファから）のグラフィックス、テキスト、および他のデータを転送すべく構成された任意の種類または形式の装置を表している。

図５に示すように、例示的な計算システム５１０はまた、入力インターフェース５３０を介して通信基盤５１２に接続された少なくとも１個の入力装置５２８を含んでいてもよい。入力装置５２８は一般に、コンピュータまたは人間のいずれかにより生成された入力を例示的な計算システム５１０に与えることができる任意の種類または形式の入力装置を表している。入力装置５２８の例として、キーボード、位置指示装置、音声認識装置、または他の任意の入力装置を含んでいるが、これらに限定されない。少なくとも１個の実施形態において、入力装置５２８は、単独で、または他の要素と組み合わせて、本明細書に開示するステップの識別、判定、分割、実行、保存、指定、追加、削除、生成、マーク付け、および延期のうち１個以上を実行してもよく、および／または実行するための手段であってもよい。入力装置５２８はまた、本開示に記述する他のステップおよび特徴を実行するために使用してもよく、および／または実行するための手段であってもよい。

図５に示すように、例示的な計算システム５１０はまた、記憶ンターフェース５３４を介して通信基盤５１２に接続された一次記憶装置５３２およびバックアップ記憶装置５３３を含んでいてもよい。記憶装置５３２および５３３は一般に、データおよび／または他のコンピュータ可読な命令を保存できる任意の種類または形式の記憶システムまたは媒体を表している。例えば、記憶装置５３２および５３３は、磁気ディスクドライブ（例：いわゆるハードディスク）、フロッピーディスクドライブ、磁気テープドライブ、光ディスクドライブ、フラッシュドライブ等であってもよい。記憶ンターフェース５３４は一般に、記憶装置５３２および５３３と計算システム５１０の他の構成要素の間でデータを転送する任意の種類または形式のインターフェースまたは装置を表している。一例において、図１のデータベース１２０は一次記憶装置５３２に保存されていてもよい。

特定の実施形態において、記憶装置５３２および５３３は、コンピュータソフトウェア、データ、または他のコンピュータ可読情報を保存すべく構成された着脱可能記憶装置の読み出しおよび／または書き込みを行うべく構成されていてもよい。適当な着脱可能記憶装置の例として、フロッピーディスク、磁気テープ、光ディスク、フラッシュメモリ装置等が含まれるが、これらに限定されない。記憶装置５３２および５３３はまた、コンピュータソフトウェア、データ、または他のコンピュータ可読命令を計算システム５１０にロードできる他の類似構造または装置を含んでいてもよい。例えば、記憶装置５３２および５３３は、ソフトウェア、データ、または他のコンピュータ可読情報の読み出しおよび書き込みを行うべく構成されていてもよい。記憶装置５３２および５３３はまた、計算システム５１０の一部であってもよく、あるいは他のインターフェースシステムを介してアクセスされる別個の装置であってもよい。

特定の実施形態において、記憶装置５３２および５３３は例えば、単独で、または他の要素と組み合わせて、本明細書に開示するステップの識別、判定、分割、実行、保存、指定、追加、削除、生成、マーク付け、および延期のうち１個以上を実行するために使用してもよく、および／または実行するための手段であってもよい。記憶装置５３２および５３３はまた、本開示に記述するステップおよび特徴を実行するために使用してもよく、および／または実行するための手段であってもよい。

他の多くの装置またはサブシステムが計算システム５１０に接続されていてもよい。逆に、図５に示す全ての構成要素および装置は、本明細書に記述および／または図示する実施形態の実施に必要な訳ではない。上述の装置およびサブシステムはまた、図５に示すものとは異なる仕方で相互接続されていてもよい。計算システム５１０はまた、任意の数のソフトウェア、ファームウェア、および／またはハードウェア構成を採用してもよい。例えば、本明細書に開示する１個以上の例示的な実施形態は、コンピュータ可読媒体上のコンピュータプログラム（コンピュータソフトウェア、ソフトウェアアプリケーション、コンピュータ可読命令、またはコンピュータ制御ロジックとも称する）として符号化されてもよい。「コンピュータ可読媒体」という用語は一般に、任意の形式の装置、キャリア、またはコンピュータ可読命令を保存または搬送可能な媒体を指す。コンピュータ可読媒体の例として、搬送波等の伝送媒体、および磁気記録媒体（例：ハードディスクドライブおよびフロッピーディスク）、光記憶媒体（例：ＣＤ−またはＤＶＤ−ＲＯＭ）、電子記憶媒体（例：固体ドライブおよびフラッシュ媒体）等の物理媒体、および他の配信システムが含まれるが、これらに限定されない。

コンピュータプログラムを収納しているコンピュータ可読媒体は、計算システム５１０にロードし得る。コンピュータ可読媒体に保存されているコンピュータプログラムの全部または一部は次いで、記憶装置５３２および５３３のシステムメモリ５１６および／または様々な部分に保存し得る。プロセッサ５１４により実行されたならば、計算システム５１０にロードされたコンピュータプログラムによりプロセッサ５１４に、本明細書に記述および／または図示する１個以上の例示的な実施形態の機能を実行してもよく、および／または実行するための手段であってもよい。追加的または代替的に、本明細書に記述および／または図示する１個以上の例示的な実施形態がファームウェアおよび／またはハードウェアに実装されていてもよい。例えば、計算システム５１０は、本明細書に開示する１個以上の例示的な実施形態を実装するのに適している特定用途向け集積回路（ＡＳＩＣ）として構成されていてもよい。

図６は、例示的なネットワークアーキテクチャ６００のブロック図であり、クライアントシステム６１０、６２０、および６３０、並びにサーバ６４０、６４５がネットワーク６５０に接続されていてもよい。クライアントシステム６１０、６２０、および６３０は一般に、図５の例示的な計算システム５１０等、任意の種類または形式の計算装置またはシステムを表している。

同様に、サーバ６４０、６４５は一般に、各種のデータベースサービスを提供、および／または特定のソフトウェアアプリケーションを実行すべく構成された、アプリケーションサーバまたはデータベースサーバ等の計算装置またはシステムを表している。ネットワーク６５０は一般に、例えばイントラネット、広域ネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、パーソナルエリアネットワーク（ＰＡＮ）、またはインターネットを含む任意の電気通信またはコンピュータネットワークを表している。一例において、クライアントシステム６１０、６２０、および／または６３０および／またはサーバ６４０および／または６４５は、図１のシステム１００を含んでいてもよい。

図６に示すように、１個以上の記憶システム６６０（１）〜（Ｎ）は、直接サーバ６４０に接続されていてもよい。同様に、１個以上の記憶システム６７０（１）〜（Ｎ）は、直接サーバ６４５に接続されていてもよい。記憶システム６６０（１）〜（Ｎ）および記憶システム６７０（１）〜（Ｎ）は一般に、データおよび／または他のコンピュータ可読命令を保存可能な任意の種類または形式の記憶装置または媒体を表している。特定の実施形態において、記憶装置６６０（１）〜（Ｎ）および記憶装置６７０（１）〜（Ｎ）は、ＮＦＳ、ＳＭＢまたはＣＩＦＳ等、各種のプロトコルを用いてサーバ６４０、６４５と通信すべく構成されたネットワーク接続記憶（ＮＡＳ）装置を表していてもよい。

サーバ６４０、６４５はまた、記憶域ネットワーク（ＳＡＮ）ファブリック６８０に接続されていてもよい。ＳＡＮファブリック６８０は一般に、複数の記憶装置間の通信を容易にすることができる任意の種類または形式のコンピュータネットワークまたはアーキテクチャを表している。ＳＡＮファブリック６８０は、サーバ６４０、６４５と複数の記憶装置６９０（１）〜（Ｎ）および／またはインテリジェント記憶アレイ６９５の間の通信を容易にし得る。ＳＡＮファブリック６８０はまた、装置６９０（１）〜（Ｎ）およびアレイ６９５が、クライアントシステム６１０、６２０および６３０にローカル接続された装置であるように見えるような仕方で、ネットワーク６５０およびサーバ６４０、６４５を介して、クライアントシステム６１０、６２０、および６３０と記憶装置６９０（１）〜（Ｎ）および／またはインテリジェント記憶アレイ６９５の間の通信を容易にし得る。記憶装置６６０（１）〜（Ｎ）および記憶装置６７０（１）〜（Ｎ）と同様に、記憶装置６９０（１）〜（Ｎ）およびインテリジェント記憶アレイ６９５は一般に、データおよび／または他のコンピュータ可読命令を保存可能な任意の種類または形式の記憶装置または媒体を表している。

特定の実施形態において、かつ図５の例示的な計算システム５１０を参照するに、図５の通信インターフェース５２２等の通信インターフェースを用いて、各クライアントシステム６１０、６２０、および６３０とネットワーク６５０の間を接続させ得る。クライアントシステム６１０、６２０、および６３０は、例えばウェブブラウザその他のクライアントソフトウェアを用いてサーバ６４０または６４５上の情報にアクセスすることが可能であってもよい。そのようなソフトウェアにより、クライアントシステム６１０、６２０、および６３０は、サーバ６４０、サーバ６４５、記憶装置６６０（１）〜（Ｎ）、記憶装置６７０（１）〜（Ｎ）、記憶装置６９０（１）〜（Ｎ）、またはインテリジェント記憶アレイ６９５がホスティングするデータにアクセスできるようになり得る。図６に、データ交換のためにネットワーク（インターネット等）を利用している様子を示しているが、本明細書に記述および／または図示する実施形態は、インターネットまたは何らかの特定のネットワーク的環境に限定されない。

少なくとも１個の実施形態において、本明細書に開示する１個以上の例示的な実施形態の全部または一部は、コンピュータプログラムとして符号化し、サーバ６４０、サーバ６４５、記憶装置６６０（１）〜（Ｎ）、記憶装置６７０（１）〜（Ｎ）、記憶装置６９０（１）〜（Ｎ）、インテリジェント記憶アレイ６９５、またはこれらを任意に組合せたものにロードして実行し得る。本明細書に開示する１個以上の例示的な実施形態の全部または一部はまた、コンピュータプログラムとして符号化し、サーバ６４０に保存し、サーバ６４５により実行し、ネットワーク６５０を介してクライアントシステム６１０、６２０、および６３０に配信し得る。従って、ネットワークアーキテクチャ６００は、単独で、または他の要素と組み合わせて、本明細書に開示するステップの識別判定、分割、実行、保存、指定、追加、削除、生成、マーク付け、および延期のうち１個以上を実行可能および／または実行するための手段であってもよい。ネットワークアーキテクチャ６００はまた、本開示に記述する他のステップおよび特徴を実行するために使用可能および／または実行するための手段であってもよい。

上で詳述したように、計算システム５１０および／またはネットワークアーキテクチャ６００の１個以上の構成要素は、単独で、または他の要素と組み合わせて、重複排除記憶システムのスケーラビリティを向上させる例示的な方法の１個以上のステップを実行可能および／または実行するための手段であってもよい。

上述の開示は特定のブロック図、フロー図、および例を用いて各種の実施形態を記述しているが、各々のブロック図の構成要素、フロー図のステップ、動作、および／または本明細書に記述および／または図示する構成要素は、広範なハードウェア、ソフトウェア、またはファームウェア（あるいはこれらの任意の組合せ）構成を用いて、個別および／または集合的に実装し得る。また、同じ機能を実現するために他の多くのアーキテクチャを実装可能であるため、他の構成要素内に含まれる構成要素のあらゆる開示は本質的に例示的であると考えるべきである。

いくつかの実施形態において、図１の例示的なシステム１００の全部または一部は、クラウド計算またはネットワーク的環境の一部を表していてもよい。クラウド計算環境は、インターネットを介して各種のサービスおよびアプリケーションを提供し得る。これらのクラウド型サービス（例：サービスとしてのソフトウェア（ＳａａＳ）、サービスとしてのプラットフォーム（ＰａａＳ）、サービスとしての基盤（ＩａａＳ）等）は、ウェブブラウザまたは他の遠隔インターフェースを介してアクセス可能であり得る。本明細書に記述する各種の機能は、リモートデスクトップ環境または他の任意のクラウド型計算環境を介して提供し得る。

本明細書に記述および／または図示するステップの処理パラメータおよびシーケンスは単なる例として挙げたものであって、必要ならば変更することができる。例えば、本明細書に図示および／または記述するステップは特定の順序で図示または説明され得るが、これらのステップは必ずしも図示または説明された順序で実行する必要がある訳ではない。本明細書に記述および／または図示する各種の例示的な方法はまた、本明細書に記述または図示するステップのうち１個以上を省略しても、あるいは開示したものに更に追加ステップが含まれていてもよい。

完全に機能する計算システムを前提として本明細書に各種の実施形態を記述および／または図示しているが、これらの例示的な実施形態のうち１個以上を各種形式のプログラム製品として配信し得、実際に配信の実行に用いる特定の種類のコンピュータ可読媒体とは無関係である。本明細書に開示する実施形態はまた、特定のタスクを実行するソフトウエアモジュールを用いて実装し得る。これらのソフトウエアモジュールは、スクリプト、バッチ、またはコンピュータ可読記憶媒体または計算システム内に保存し得る他の実行可能ファイルを含んでいてもよい。いくつかの実施形態において、これらのソフトウエアモジュールは、本明細書に開示する１個以上の例示的な実施形態を実行すべく計算システムを構成し得る。

また、本明細書に記述する１個以上のモジュールは、データ、物理装置、および／または物理装置の表現をある形式から別の形式へ変換し得る。例えば、図１の１個以上のモジュール１０２は、少なくとも１個の部分データベースに保存されている１個以上の参照オブジェクトを更新する更新動作を実行することにより、物理装置（図２のサーバ２０６等）の特徴または特性を変換し得る。

上述の説明は、本明細書に開示する例示的な実施形態の各種の態様を他の当業者が最適に利用できるようにすべく提供している。この例示的な記述は、網羅的であることを意図しておらず、または開示したいかなる厳密な形式にも限定されることは意図していない。本開示の趣旨および範囲から逸脱することなく多くの変更や変型が可能である。本明細書に開示する実施形態は、あらゆる点で例示的であって限定的ではないと考えるべきである。本開示の範囲を確定するには、添付の請求項およびその等価物を参照されたい。

別途に注記しない限り、本明細書および請求項で用いる冠詞「ａ（１個の）」または「ａｎ（１個の）」は「少なくとも１個の」を意味するものと解釈されたい。また、使い易さを旨として、本明細書および請求項で用いる「含む（ｉｎｃｌｕｄｉｎｇ）」および「有する（ｈａｖｉｎｇ）」という単語は、「含んでなる（ｃｏｍｐｒｉｓｉｎｇ）」という単語と交換可能かつ同義である。

１００ システム
１０２ モジュール
１０４ 識別モジュール
１０６ 分割モジュール
１０８ 更新モジュール
１２０ データベース
１２２ 参照オブジェクトデータベース
１２４ ファイルセグメントデータベース
１２６（１）〜（Ｎ） 部分データベース
２００ 重複排除記憶システム
２０２（１）〜（Ｎ） 計算装置
２０４ ネットワーク
２０６ サーバ
４００ 更新動作の実行を要求するリクエスト
４０２ 参照リスト
５１２ 通信基盤
５１４ プロセッサ
５１６ システムメモリ
５１８ メモリコントローラ
５２０ 入出力コントローラ
５２２ 通信インターフェース
５２４ ディスプレイ装置
５２６ ディスプレイアダプタ
５２８ 入力装置
５３０ 入力インターフェース
５３２ 一次記憶装置
５３３ バックアップ記憶装置
５３４ 記憶インターフェース
６００ ネットワークアーキテクチャ
６１０，６２０，６３０ クライアント
６４５，７４０ サーバ
６５０ ネットワーク
６６０（１）〜（Ｎ），６７０（１）〜（Ｎ），６９０（１）〜（Ｎ） 装置
６８０ ＳＡＮファブリック
６９５ インテリジェント記憶アレイ

Claims (15)

1. 重複排除記憶システムのスケーラビリティを向上させるコンピュータ実装された方法であって、前記方法の少なくとも一部が少なくとも１個のプロセッサを含む計算装置により実行され、
   複数の参照オブジェクトを保存するデータベースを識別するステップであって、前記データベース内の各々の参照オブジェクトが、
   重複排除記憶システム内に保存された少なくとも１個の一意のファイルセグメントと、
   各々の一意のファイルセグメントについて、前記重複排除記憶システム内の１個以上のバックアップされたファイルが前記一意のファイルセグメントを現在参照しているか否かとを識別するステップと、
   前記データベースのサイズが所定の閾値に達したと判定するステップと、
   前記データベース全体の前記サイズが前記所定の閾値に達したと判定することに応じて、
   前記データベースを、互いに独立に更新可能な複数の部分データベースに分割するステップであって、前記複数の部分データベースは、前記分割時点以降に空であり且つ参照オブジェクトを保存する有効な部分データベースとして指定されるまで空のままである無効な部分データベースを含む、ステップと、
   前記複数の部分データベース内の前記無効な部分データベースを、指定時点以降に作成される参照オブジェクトを保存するために、前記有効な部分データベースとして指定するステップと、
   前記有効な部分データベースに保存されている１個以上の参照オブジェクトを更新する更新動作の実行を要求するリクエストを識別するステップと、
   前記有効な部分データベースのみに対して前記更新動作を実行して、前記複数の部分データベース内の前記部分データベースの全てに対する前記更新動作の実行に伴う処理コストを回避するステップと
   を含む方法。
2. 前記データベースの前記サイズが前記所定の閾値に達していると決定するステップが、
   前記データベースに保存されている参照オブジェクトの数が所定の閾値に達したと判定するステップと、
   前記データベースに保存されている前記参照オブジェクトが所定量の記憶空間を消費していると判定するステップの少なくとも１個を含んでいる、請求項１に記載のコンピュータに実装された方法。
3. 前記データベースを部分データベースに分割するステップが、
   前記分割時点において前記データベース内で識別される前記参照オブジェクトを１個の部分データベースに保存するステップと、
   前記無効な部分データベースを前記有効な部分データベースとして指定するステップは、前記分割時点以降に少なくとも１個のファイルが前記重複排除記憶システムに追加された結果として生成された１個以上の新たな参照オブジェクトを保存するために、前記無効な部分データベースを前記有効な部分データベースとして指定するステップを含んでいる、請求項１〜２のいずれか１項に記載のコンピュータに実装された方法。
4. 各参照オブジェクトが、
   前記重複排除記憶システムに保存されている一意のファイルセグメントを現在参照している１個以上のバックアップ済みファイルを識別する参照リストと、
   前記重複排除記憶システムに保存されている一意のファイルセグメントを現在参照しているバックアップ済みファイルの数を識別する参照カウント、のうち少なくとも１個を含んでいる、請求項１〜３のいずれか１項に記載のコンピュータに実装された方法。
5. 前記更新動作が、
   前記有効な部分データベースに保存されている１個以上の参照リストに、特定のバックアップ済みファイルを識別する参照子を追加するステップと、
   前記有効な部分データベースに保存されている１個以上の参照リストから、特定のバックアップ済みファイルを識別する参照子を削除するステップと、
   前記有効な部分データベース内に、前記重複排除記憶システムに追加された新たな一意のファイルセグメントを参照する１個以上のバックアップ済みファイルを識別する新たな参照リストを生成するステップ、のうち少なくとも１個を含んでいる、請求項４に記載のコンピュータに実装された方法。
6. 前記更新動作が、
   少なくとも１個の参照カウントを増やして、増加した数のバックアップ済みファイルが特定の一意のファイルセグメントを現在参照していることを示すステップと、
   少なくとも１個の参照カウントを減らして、減少した数のバックアップ済みファイルが特定の一意のファイルセグメントを現在参照していることを示すステップと、
   前記有効な部分データベース内に、前記重複排除記憶システムに追加された新たな一意のファイルセグメントを現在参照しているバックアップ済みファイルの数を識別する新たな参照カウントを生成するステップ、のうち少なくとも１個を含んでいる、請求項４に記載のコンピュータに実装された方法。
7. 前記更新動作を実行したならば、前記更新動作により更新された前記参照オブジェクトのうち１個が、前記重複排除記憶システムに保存されている特定の一意のファイルセグメントを現在参照しているバックアップ済みファイルが無いことを示していると判定するステップと、
   前記重複排除記憶システムに再利用されるように、前記重複排除記憶システムに保存される前記特定の一意のファイルセグメントをバックアップ済みファイルが現在参照していないことを示す前記参照オブジェクトに関連付けられた前記特定の一意のファイルセグメントにマーク付けするステップとを更に含んでいる、請求項１〜６のいずれか１項に記載のコンピュータに実装された方法。
8. 少なくとも１個の異なる部分データベースに保存されている１個以上の参照オブジェクトを更新する別の更新動作の実行を要求する別のリクエストを識別するステップをさらに含み、
   前記有効な部分データベースのみに前記更新動作を実行するステップは、異なる部分データベースに対して前記更新動作および別の更新動作を同時に実行するステップを含んでいる、請求項１〜７のいずれか１項に記載のコンピュータに実装された方法。
9. 前記有効な部分データベースのみに対して前記更新動作を実行するステップが、
   前記有効な部分データベースに対して別の更新動作の実行を要求する別のリクエストの所定数を識別するまで前記更新動作の実行を延期するステップと、
   前記有効な部分データベースに対して別の更新動作の実行を要求する別のリクエストを識別するステップと、
   前記識別された別のリクエストの数が前記別のリクエストの前記所定数に達したと判定するステップと、
   前記有効な部分データベースに対して前記更新動作および前記別の更新動作を順次実行するステップを含んでいる、請求項１〜８に記載のコンピュータに実装された方法。
10. 前記部分データベース内に保存された参照オブジェクトの数が所定の閾値に達したと判定することと、
    前記部分データベース内に保存された前記参照オブジェクトが所定量の記憶領域を消費していると判定することと、
    の少なくとも１つによって、前記部分データベースのサイズが所定の閾値に達したと判定するステップと、
    前記部分データベースの前記サイズが前記所定の閾値に達したと判定することに応じて、前記部分データベースを、互いに独立に更新可能な複数の追加的な部分データベースに分割するステップとを更に含んでいる、請求項１〜９に記載のコンピュータに実装された方法。
11. 重複排除記憶システムのスケーラビリティを向上させるシステムであって、
    複数の参照オブジェクトを保存するデータベースを識別する識別手段であって、前記データベース内の各々の参照オブジェクトが、
    重複排除記憶システムに保存された少なくとも１個の一意のファイルセグメントと、
    各々の一意のファイルセグメントについて、前記重複排除記憶システム内の１個以上のバックアップされたファイルが前記一意のファイルセグメントを現在参照しているか否かとを識別する識別手段と、
    分割手段であって、
    前記データベースのサイズが所定の閾値に達したと判定し、
    前記データベース全体の前記サイズが前記所定の閾値に達したと判定することに応じて、
    前記データベースを、互いに独立に更新可能な複数の部分データベースであって、前記分割時点以降に空であり且つ参照オブジェクトを保存する有効な部分データベースとして指定されるまで空のままである無効な部分データベースを含む複数の部分データベースに分割し、
    前記複数の部分データベース内の前記無効な部分データベースを、指定時点以降に作成される参照オブジェクトを保存するために、前記有効な部分データベースとして指定する、
    分割手段と、
    更新手段であって、
    前記有効な部分データベースに保存されている１個以上の参照オブジェクトを更新する更新動作の実行を要求するリクエストを識別し、
    前記有効な部分データベースのみに対して前記更新動作を実行して、前記複数の部分データベース内の前記部分データベースの全てに対する前記更新動作の実行に伴う処理コストを回避する更新手段とを含むシステム。
12. 前記識別手段が、
    前記データベースに保存されている参照オブジェクトの数が所定の閾値に達したと判定する、および／または、
    前記データベースに保存されている前記参照オブジェクトが所定量の記憶空間を消費していると判定する、請求項１１に記載のシステム。
13. 前記分割手段が、
    前記分割時点において前記データベース内で識別される前記参照オブジェクトを１個の部分データベースに保存し、
    前記無効な部分データベースを前記有効な部分データベースとして指定するステップが、前記分割時点以降に少なくとも１個のファイルが前記重複排除記憶システムに追加された結果として生成された１個以上の新たな参照オブジェクトを保存するために、前記無効な部分データベースを前記有効な部分データベースとして指定するステップを含む、請求項１１〜１２のいずれか１項に記載のシステム。
14. 各参照オブジェクトが、
    前記重複排除記憶システムに保存されている一意のファイルセグメントを現在参照している１個以上のバックアップ済みファイルを識別する参照リストと、
    前記重複排除記憶システムに保存されている一意のファイルセグメントを現在参照しているバックアップ済みファイルの数を識別する参照カウント、のうち少なくとも１個を含んでいる、請求項１１〜１３のいずれか１項に記載のシステム。
15. 前記更新手段が、
    前記更新動作を実行したならば、前記更新動作により更新された前記参照オブジェクトのうち１個が、前記重複排除記憶システムに保存されている特定の一意のファイルセグメントを現在参照しているバックアップ済みファイルが無いことを示していると判定し、
    前記重複排除記憶システムに再利用されるように、前記重複排除記憶システムに保存される前記特定の一意のファイルセグメントをバックアップ済みファイルが現在参照していないことを示す前記参照オブジェクトに関連付けられた前記特定の一意のファイルセグメントにマーク付けする、請求項１１〜１４のいずれか１項に記載のシステム。
    

Images