(57)【要約】  重複排除データシステムにおけるガーベジコレクション用のコンピュータ実行方法には、１）重複排除データシステムを識別することと、２）重複排除データシステムのガーベジコレクションプロセス中に重複排除データシステムに追加された少なくとも１つのセグメントオブジェクトを識別することと、３）ガーベジコレクションプロセスによるセグメントオブジェクトの除去を防ぐために、セグメントオブジェクトをロックすることと、４）ガーベジコレクションプロセス後にセグメントオブジェクトをロック解除することと、を含んでもよい。この方法によって、有用なセグメントオブジェクトを誤って除去する可能性を小さくすることが可能になる。この方法はまた、ガーベジコレクションプロセス中にデータオブジェクトを検証し、誤って除去されたセグメントオブジェクトを回復してもよい。様々な他の方法、システム、およびコンピュータ可読媒体がまた開示される。
2013522718.tif 000002
【特許請求の範囲】
【請求項１】
重複排除データシステムにおけるガーベジコレクション用のコンピュータ実行方法であって、前記方法の少なくとも一部が、少なくとも１つのプロセッサを含むコンピューティング装置によって実行され、前記方法が、
重複排除データシステムを識別することと、
前記重複排除データシステムのガーベジコレクションプロセス中に前記重複排除データシステムに追加された少なくとも１つのセグメントオブジェクトを識別することと、
前記ガーベジコレクションプロセスによる前記セグメントオブジェクトの除去を防ぐために、前記セグメントオブジェクトをロックすることと、
前記ガーベジコレクションプロセス後に前記セグメントオブジェクトをロック解除することと、
を含む方法。
【請求項２】
前記セグメントオブジェクトをロックすることが、前記セグメントオブジェクトに対する参照を、ロックされたセグメントオブジェクトマップに追加することを含む、請求項１に記載のコンピュータ実行方法。
【請求項３】
前記ガーベジコレクションプロセス後に前記セグメントオブジェクトをロック解除することが、
前記ロックされたセグメントオブジェクトマップを消去することと、
前記ロックされたセグメントオブジェクトマップを削除することと、
前記セグメントオブジェクトに対する前記参照を、前記ロックされたセグメントオブジェクトマップから除去することと、
の少なくとも１つを含む、請求項２に記載のコンピュータ実行方法。
【請求項４】
前記重複排除データシステムに追加された前記セグメントオブジェクトを識別することが、
前記重複排除データシステム内における前記セグメントオブジェクトの生成を識別することと、
前記重複排除データシステム内における前記セグメントオブジェクトに対する新しい参照を識別することと、
の少なくとも１つを含む、請求項１に記載のコンピュータ実行方法。
【請求項５】
前記ガーベジコレクションプロセス前に前記重複排除データシステムに追加された追加セグメントオブジェクトを識別することと、
前記ガーベジコレクションプロセスの一部として、前記追加セグメントオブジェクトが前記重複排除データシステム内で参照されないと判定することと、
前記判定に基づいて前記追加セグメントオブジェクトを除去することと、
をさらに含む、請求項１に記載のコンピュータ実行方法。
【請求項６】
前記追加セグメントオブジェクトが追加された後で前記重複排除データシステムに追加されたデータオブジェクトを識別することと、
前記データオブジェクトが前記追加セグメントオブジェクトを参照すると判定することと、
前記追加セグメントオブジェクトの別のコピーを検索することと、
をさらに含む、請求項５に記載のコンピュータ実行方法。
【請求項７】
前記ガーベジコレクションプロセス中に前記重複排除データシステムに追加された前記セグメントオブジェクトを識別することが、ひとたび前記ガーベジコレクションプロセスが始まると、新しいデータセグメント用に前記重複排除データシステムを監視することを含む、請求項１に記載のコンピュータ実行方法。
【請求項８】
ひとたび前記ガーベジコレクションプロセスが完了すると、新しいデータセグメント用の、前記重複排除データシステムの前記監視を終了することをさらに含む、請求項７に記載のコンピュータ実行方法。
【請求項９】
前記ガーベジコレクションプロセス中に前記重複排除データシステムに追加された少なくとも１つのデータオブジェクトを識別することと、
前記ガーベジコレクションプロセスによる前記データオブジェクトの除去を防ぐために前記データオブジェクトをロックすることと、
前記ガーベジコレクションプロセス後に前記データオブジェクトをロック解除することと、
をさらに含む、請求項１に記載のコンピュータ実行方法。
【請求項１０】
重複排除データシステムにおけるガーベジコレクション用のシステムであって、
識別モジュールであって、
重複排除データシステムを識別するように、
前記重複排除データシステムのガーベジコレクションプロセス中に前記重複排除データシステムに追加された少なくとも１つのセグメントオブジェクトを識別するように、プログラムされた識別モジュールと、
前記ガーベジコレクションプロセスによる前記セグメントオブジェクトの除去を防ぐために、前記セグメントオブジェクトをロックするようにプログラムされたロッキングモジュールと、
前記ガーベジコレクションプロセス後に前記セグメントオブジェクトをロック解除するようにプログラムされたロック解除モジュールと、
前記識別モジュール、前記保存モジュール、前記供給モジュール、および前記削除モジュールを実行するように構成された少なくとも１つのプロセッサと、
を含むシステム。
【請求項１１】
前記ロッキングモジュールが、前記セグメントオブジェクトに対する参照を、ロックされたセグメントオブジェクトマップに追加することによって、前記セグメントオブジェクトをロックするようにプログラムされる、請求項１０に記載のシステム。
【請求項１２】
前記ロック解除モジュールが、
前記ロックされたセグメントオブジェクトマップを消去することと、
前記ロックされたセグメントオブジェクトマップを削除することと、
前記セグメントオブジェクトに対する前記参照を、前記ロックされたセグメントオブジェクトマップから除去することと、
の少なくとも１つによって、前記ガーベジコレクションプロセス後に前記セグメントオブジェクトをロック解除するようにプログラムされる、請求項１１に記載のシステム。
【請求項１３】
前記識別モジュールが、
前記重複排除データシステム内における前記セグメントオブジェクトの生成を識別することと、
前記重複排除データシステム内における前記セグメントオブジェクトに対する新しい参照を識別することと、
の少なくとも１つによって、前記重複排除データシステムに追加された前記セグメントオブジェクトを識別するようにプログラムされる、請求項１０に記載のシステム。
【請求項１４】
前記ガーベジコレクションプロセス前に前記重複排除データシステムに追加された追加セグメントオブジェクトを識別するように、
前記ガーベジコレクションプロセスの一部として、前記追加セグメントオブジェクトが前記重複排除データシステム内で参照されないと判定するように、
前記判定に基づいて前記追加セグメントオブジェクトを除去するように、
プログラムされたガーベジコレクションモジュールをさらに含む、請求項１０に記載のシステム。
【請求項１５】
前記追加セグメントオブジェクトが追加された後で前記重複排除データシステムに追加されたデータオブジェクトを識別するように、
前記データオブジェクトが前記追加セグメントオブジェクトを参照すると判定するように、
前記追加セグメントオブジェクトの別のコピーを検索するように、
プログラムされた回復モジュールをさらに含む、請求項１４に記載のシステム。
【請求項１６】
前記識別モジュールが、ひとたび前記ガーベジコレクションプロセスが始まると、新しいデータセグメント用に前記重複排除データシステムを監視することによって、前記ガーベジコレクションプロセス中に前記重複排除データシステムに追加された前記セグメントオブジェクトを識別するようにプログラムされる、請求項１０に記載のシステム。
【請求項１７】
前記識別モジュールが、ひとたび前記ガーベジコレクションプロセスが完了すると、新しいデータセグメント用の、前記重複排除データシステムの前記監視を終了するようにさらにプログラムされる、請求項１６に記載のシステム。
【請求項１８】
前記識別モジュールが、前記ガーベジコレクションプロセス中に前記重複排除データシステムに追加された少なくとも１つのデータオブジェクトを識別するようにさらにプログラムされ、
前記ロッキングモジュールが、前記ガーベジコレクションプロセスによる前記データオブジェクトの除去を防ぐために、前記データオブジェクトをロックするようにさらにプログラムされ、
前記ロック解除モジュールが、前記ガーベジコレクションプロセス後に前記データオブジェクトをロック解除するようにさらにプログラムされる、請求項１０に記載のシステム。
【請求項１９】
１つまたは複数のコンピュータ実行可能命令であって、コンピューティング装置の少なくとも１つのプロセッサによって実行された場合に、前記コンピューティング装置に、
重複排除データシステムを識別させ、
前記重複排除データシステムのガーベジコレクションプロセス中に前記重複排除データシステムに追加された少なくとも１つのセグメントオブジェクトを識別させ、
前記ガーベジコレクションプロセスによる前記セグメントオブジェクトの除去を防ぐために前記セグメントオブジェクトをロックさせ、
前記ガーベジコレクションプロセス後に前記セグメントオブジェクトをロック解除させる１つまたは複数のコンピュータ実行可能命令を含むコンピュータ可読記憶媒体。
【請求項２０】
前記セグメントオブジェクトをロックすることが、前記セグメントオブジェクトに対する参照を、ロックされたセグメントオブジェクトマップに追加することを含む、請求項１９に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【背景技術】
【０００１】
重複排除（ｄｅｄｕｐｌｉｃａｔｅｄ）データシステムは、冗長データパターンを認識することによって、ファイルを記憶するために必要な空き容量を低減できることが多い。例えば、重複排除データシステムは、ファイルをデータセグメントに分割し、かつユニークなデータセグメントだけを記憶することによって、類似のファイルを記憶するために必要な空き容量を低減してもよい。この例において、各重複排除ファイルは、単に、ファイルを構成するデータセグメントのリストからなってもよい。
【０００２】
従来の重複排除データシステムは、ファイルを記憶するために必要なスペースを低減可能であるが、重複排除データを管理するかかる従来のシステムによって用いられる機構は、望ましくない制約をもたらす場合がある。例えば、１を超えるファイルが、任意の所与のデータセグメントを参照する可能性があるので、ファイルが削除される場合に、ファイルを構成するデータセグメントは、とても全てを削除できるわけではない。データセグメントを差しつかえなく削除するために、重複排除データシステムは、参照されるおよび参照されないデータセグメントを区別しなければならない。
【０００３】
残念なことに、場合によっては、新しく追加された、参照されるデータセグメントが、参照されないように一時的に見える可能性があり、したがって不適切なことに削除される可能性がある。例えば、重複排除データシステムが、新しいファイルを受信する場合に、重複排除データシステムは、ファイルを構成するデータセグメントを最初に受信し、次にファイル自体を受信する場合がある（例えば、重複排除データシステムは、ファイルがデータセグメントを参照できる前に、データセグメントが存在することを要求する可能性がある）。重複排除データシステムのガーベジコレクションサブシステムが、新しいファイル自体に気付く前に新しいデータセグメントを調べた場合に、重複排除データシステムは、新しいデータセグメントを削除する可能性がある。
【０００４】
場合によっては、従来の重複排除データシステムは、データセグメントが時期尚早に除去されないことを保証するために、全ての新しく追加されたデータセグメントに時間インジケータを取り付ける場合がある。残念なことに、この解決法は、多くの欠陥に苦慮する。例えば、全ての新しく追加されたデータセグメントに時間インジケータを追加すること（および次に続いて、対応するファイルが追加された場合にインジケータを削除すること）は、著しい性能オーバーヘッドを課する可能性がある。さらに、この解決法は、ガーベジコレクションサブシステムのいくつかのインプリメンテーション（マークアンドスイープアプローチまたは参照カウントアプローチなど）と適合しない可能性がある。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
したがって、本開示は、重複排除データシステムにおけるガーベジコレクション動作を効率的に実行するためのシステムおよび方法の必要性を確認する。
【課題を解決するための手段】
【０００６】
以下でより詳細に説明するように、本開示は、一般に、ガーベジコレクションプロセス中に重複排除データシステムに追加されたセグメントオブジェクトをロックすることにより、誤って除去される新しい追加データセグメント（例えば、セグメントオブジェクト）の数を最小化することによって、重複排除データシステムにおけるガーベジコレクション動作を改善するためのシステムおよび方法に関する。一例において、本明細書で説明する様々なシステムの１つまたは複数は、このタスクを、１）重複排除データシステムを識別することと、２）重複排除データシステムのガーベジコレクションプロセス中に重複排除データシステムに追加された少なくとも１つのセグメントオブジェクトを識別することと、３）ガーベジコレクションプロセスによるセグメントオブジェクトの除去を防ぐために、セグメントオブジェクトをロックすることと、次に４）ガーベジコレクションプロセス後にセグメントオブジェクトをロック解除することと、によって達成してもよい。
【０００７】
本明細書で説明するシステムは、ガーベジコレクションプロセス中に重複排除データシステムに追加されたセグメントオブジェクトを様々な方法および様々なシナリオで識別してもよい。一例において、本明細書で説明するシステムは、セグメントオブジェクトが重複排除データシステム内で生成されたときに、セグメントオブジェクトを識別してもよい。追加または代替として、これらのシステムは、重複排除データシステム内のセグメントオブジェクトに対する新しい参照を識別することによって、セグメントオブジェクトを識別してもよい。
【０００８】
一例において、本明細書で説明するシステムは、ひとたびガーベジコレクションプロセスが始まると、新しいデータセグメント用に重複排除データシステムを監視することによって、セグメントオブジェクトを識別してもよい。この例において、これらのシステムは、ひとたびガーベジコレクションプロセスが完了すると、重複排除データシステムの監視を終了してもよい。
【０００９】
いくつかの例において、本明細書で説明するシステムは、セグメントオブジェクトに対する参照を、ロックされたセグメントオブジェクトマップに追加することによって、セグメントオブジェクトをロックしてもよい。これらの例において、本明細書で説明するシステムは、続いて、ガーベジコレクションプロセスが完了した後で、ロックされたセグメントオブジェクトマップを消去すること、ロックされたセグメントオブジェクトマップを削除すること、および／またはセグメントオブジェクトに対する参照を、ロックされたセグメントオブジェクトマップから除去することによって、セグメントオブジェクトをロック解除してもよい。
【００１０】
いくつかの例において、本明細書で説明するシステムはまた、１）ガーベジコレクションプロセス前に重複排除データシステムに追加された追加セグメントオブジェクトを識別し、２）ガーベジコレクションプロセスの一部として、追加セグメントオブジェクトが重複排除データシステム内で参照されないと判定し、次に３）判定に基づいて追加セグメントオブジェクトを除去してもよい。これらのシステムはまた、１）追加セグメントオブジェクトが追加された後で、重複排除データシステムに追加されたデータオブジェクトを識別し、２）データオブジェクトが追加セグメントオブジェクトを参照すると判定し、次に、３）追加セグメントオブジェクトの別のコピーを検索してもよい。
【００１１】
いくつかの例において、本明細書で説明するシステムはまた、１）ガーベジコレクションプロセス中に重複排除データシステムに追加された少なくとも１つのデータオブジェクトを識別し、２）ガーベジコレクションプロセスによるデータオブジェクトの除去を防ぐために、データオブジェクトをロックし、次に３）ガーベジコレクションプロセス後にデータオブジェクトをロック解除してもよい。
【００１２】
以下でより詳細に説明するように、ガーベジコレクションプロセス中に追加されたセグメントオブジェクトをロックすることによって、本明細書で説明するシステムおよび方法は、対応するデータオブジェクトが重複排除データシステムにまだ追加されていないセグメントオブジェクトの望ましくない削除を防いでもよい。さらに、これらのシステムおよび方法は、１）ガーベジコレクションプロセスが始まる前に、セグメントオブジェクトが重複排除データシステムに追加され、かつ２）ガーベジコレクションプロセスが既に始まった後まで、対応するデータオブジェクトが追加されなかったのでセグメントオブジェクトが削除された境界事例における望ましくない削除を回復してもよい。かかるものとして、本明細書で説明するシステムおよび方法は、多くの場合に、ガーベジコレクション動作中の望ましくない削除を効率的に防ぎ、比較的少数の境界事例における望ましくない削除のよりコストのかかる回復を場合によっては実行してもよい。
【００１３】
前述の実施形態のいずれかにおける特徴は、本明細書で説明する一般原理に従って互いに組み合わせて用いてもよい。これらや他の実施形態、特徴、および利点は、添付の図面および特許請求の範囲と共に以下の詳細な説明を読むことによって、より完全に理解されよう。
【００１４】
添付の図面は、多数の例示的な実施形態を示し、かつ本明細書の一部である。以下の説明と共に、これらの図面は、本開示の様々な原理を例示し説明する。
【図面の簡単な説明】
【００１５】
【図１】重複排除データシステムにおけるガーベジコレクション用の例示的なシステムのブロック図である。
【図２】重複排除データシステムにおけるガーベジコレクション用の例示的なシステムのブロック図である。
【図３】重複排除データシステムにおけるガーベジコレクション用の例示的な方法の流れ図である。
【図４】重複排除データシステムにおけるガーベジコレクション用の例示的なシステムの例示的な時系列の実例である。
【図５】重複排除データシステムにおけるガーベジコレクション用の例示的なシステムのブロック図である。
【図６】重複排除データシステムにおけるガーベジコレクション用の例示的な方法の流れ図である。
【図７】重複排除データシステムにおけるガーベジコレクション用の例示的な方法の流れ図である。
【図８】本明細書で説明および／または図示する実施形態の１つまたは複数を実行できる例示的なコンピューティングシステムのブロック図である。
【図９】本明細書で説明および／または図示する実施形態の１つまたは複数を実行できる例示的なコンピューティングネットワークのブロック図である。
【００１６】
図面の全体にわたって、同一の参照文字および記載は、必ずしも同一ではないが類似の要素を示す。本明細書で説明する例示的な実施形態は、様々な修正および代替形態の余地があるが、特定の実施形態が、図面において例として示され、本明細書で詳細に説明される。しかしながら、本明細書で説明する例示的な実施形態は、開示される特定の形態に限定されるようには意図されていない。より正確に言えば、本開示は、添付の特許請求の範囲内に入る全ての修正、均等物、および代替をカバーする。
【発明を実施するための形態】
【００１７】
以下でより詳細に説明するように、本開示は、一般に、重複排除データシステムにおけるガーベジコレクション用のシステムおよび方法に関する。一例において、以下でより詳細に説明するように、本明細書で説明する様々なシステムは、このタスクを、１）重複排除データシステムを識別することと、２）重複排除データシステムのガーベジコレクションプロセス中に重複排除データシステムに追加された少なくとも１つのセグメントオブジェクトを識別することと、３）ガーベジコレクションプロセスによるセグメントオブジェクトの除去を防ぐために、セグメントオブジェクトをロックすることと、４）次に、ガーベジコレクションプロセス後にセグメントオブジェクトをロック解除することと、によって達成してもよい。
【００１８】
下記は、図１、２および５に関連して、重複排除データシステムにおけるガーベジコレクション用の例示的なシステムにおける詳細な説明を提供する。対応するコンピュータ実行方法の詳細な説明もまた、図３、４、６および７に関連して提供される。さらに、本明細書で説明する実施形態の１つまたは複数を実施できる例示的なコンピューティングシステムおよびネットワークアーキテクチャの詳細な説明が、それぞれ、図８および９に関連して提供される。
【００１９】
図１は、重複排除データシステムにおけるガーベジコレクション用の例示的なシステム１００のブロック図である。この図に示すように、例示的なシステム１００には、１つまたは複数のタスクを実行するための１つまたは複数のモジュール１０２を含んでもよい。例えば、以下でより詳細に説明するように、例示的なシステム１００には、重複排除データシステムのガーベジコレクションプロセス中に重複排除データシステムに追加された少なくとも１つのセグメントオブジェクトを識別するようにプログラムされた識別モジュール１０４を含んでもよい。例示的なシステム１００にはまた、ガーベジコレクションプロセスによるセグメントオブジェクトの除去を防ぐために、セグメントオブジェクトをロックするようにプログラムされたロッキングモジュール１０６を含んでもよい。
【００２０】
さらに、以下でより詳細に説明するように、例示的なシステム１００には、ガーベジコレクションプロセスが完了した後でセグメントオブジェクトをロック解除するようにプログラムされたロック解除モジュール１０８を含んでもよい。別個の要素として示されているが、図１におけるモジュール１０２の１つまたは複数は、単一のモジュールまたはアプリケーションの一部を表してもよい。
【００２１】
ある実施形態において、図１におけるモジュール１０２の１つまたは複数は、コンピューティング装置によって実行されると、１つまたは複数のタスクをコンピューティング装置に実行させ得る１つまたは複数のソフトウェアアプリケーションまたはプログラムを表してもよい。例えば、以下でより詳細に説明するように、モジュール１０２の１つまたは複数は、図２に示す装置（例えばコンピューティングシステム２０２）、図８におけるコンピューティングシステム８１０、および／または図９における例示的なネットワークアーキテクチャ９００の一部などの１つまたは複数のコンピューティング装置に記憶された、かつそれらを走るように構成されたソフトウェアモジュールを表してもよい。図１におけるモジュール１０２の１つまたは複数はまた、１つまたは複数のタスクを実行するように構成された１つまたは複数の専用コンピュータの全てまたは一部を表してもよい。
【００２２】
図１に示すように、例示的なシステム１００にはまた、重複排除データシステム１２０を含んでもよい。重複排除データシステム１２０は、単一の記憶システムもしくはコンピューティング装置または複数の記憶システムもしくはコンピューティング装置の一部を表してもよい。例えば、重複排除データシステム１２０は、図２におけるコンピューティングシステム２０２の一部、図８におけるコンピューティングシステム８１０、および／または図９における例示的なネットワークアーキテクチャ９００の一部を表してもよい。代替として、図１における重複排除データシステム１２０は、図８におけるコンピューティングシステム８１０、および／または図９における例示的なネットワークアーキテクチャ９００の一部など、コンピューティング装置によってアクセスできる１つまたは複数の物理的に別個の装置を表してもよい。
【００２３】
図１における例示的なシステム１００は、様々な方法で展開してもよい。例えば、例示的なシステム１００の全てまたは一部は、図２に示す例示的なシステム２００の一部を表してもよい。図２に示すように、システム２００には、重複排除データシステム１２０を備えたコンピューティングシステム２０２を含んでもよい。一実施形態において、以下でより詳細に説明するように、図１のモジュール１０２は、１）重複排除データシステムを識別するように、２）重複排除データシステムのガーベジコレクションプロセス中に重複排除データシステムに追加された少なくとも１つのセグメントオブジェクトを識別するように、３）ガーベジコレクションプロセスによるセグメントオブジェクトの除去を防ぐために、セグメントオブジェクトをロックするように、かつ４）ガーベジコレクションプロセス後にセグメントオブジェクトをロック解除するように、コンピューティングシステム２０２をプログラムしてもよい。
【００２４】
コンピューティングシステム２０２は、一般に、コンピュータ実行可能命令を読み取ることができる任意のタイプまたは形態のコンピューティング装置を表す。コンピューティングシステム２０２の例には、限定するわけではないが、ラップトップ、デスクトップ、サーバ、携帯電話、携帯情報端末（ＰＤＡ）、マルチメディアプレーヤ、埋め込みシステム、これらの１つまたは複数の組み合わせ、図８における例示的なコンピューティングシステム８１０、または任意の他の適切なコンピューティング装置が含まれる。
【００２５】
図３は、重複排除データシステムにおけるガーベジコレクション用の例示的なコンピュータ実行方法３００の流れ図である。図３に示すステップは、任意の適切なコンピュータ実行可能コードおよび／またはコンピューティングシステムによって実行してもよい。いくつかの実施形態において、図３に示すステップは、図１におけるシステム１００および／または図２におけるシステム２００のコンポーネントの１つまたは複数によって実行してもよい。
【００２６】
図３に示すように、ステップ３０２において、本明細書で説明するシステムの１つまたは複数は、重複排除データシステムを識別してもよい。例えば、ステップ３０２において、識別モジュール１０４は、図２におけるコンピューティングシステム２０２の一部として、重複排除データシステム１２０を識別してもよい。用語「重複排除データシステム」は、本明細書で用いられているように、一般に、単一のデータインスタンス（例えば、セグメントオブジェクト）だけを記憶し、潜在的に各データインスタンスを複数回参照することによって、冗長データを低減する記憶システムを指す。重複排除データシステムの例には、ＳＹＭＡＮＴＥＣのＮＥＴＢＡＣＫＵＰ  ＰＵＲＥＤＩＳＫを含んでもよい。以下でより詳細に説明するように、単一のデータインスタンスは、この重複排除データシステム内の単一のデータオブジェクト（例えばファイル）または複数のデータオブジェクトによって参照してもよい。
【００２７】
識別モジュール１０４は、任意の適切な方法でステップ３０２を実行してもよい。一例において、識別モジュール１０４は、重複排除データシステムに関連する構成ファイルを読み取ることによって、重複排除データシステムを識別してもよい。追加または代替として、識別モジュール１０４は、新しいセグメントオブジェクトを重複排除データシステムに追加する試みを識別（例えば、インターセプト、受信、または検索）することによって、重複排除データシステムを識別してもよい。いくつかの文脈において、識別モジュール１０４は、重複排除データシステムの拡張部および／またはコンポーネントであってもよく、単にそれが動作している文脈を通して重複排除データシステムを暗黙裡に識別してもよい。
【００２８】
ステップ３０４において、本明細書で説明するシステムの１つまたは複数は、重複排除データシステムのガーベジコレクションプロセス中に重複排除データシステムに追加された少なくとも１つのセグメントオブジェクトを識別してもよい。例えば、ステップ３０４において、識別モジュール１０４は、図２におけるコンピューティングシステム２０２の一部として、重複排除データシステム１２０のガーベジコレクションプロセス中に重複排除データシステム１２０に追加されたセグメントオブジェクトを識別してもよい。
【００２９】
図４は、（データオブジェクト４１０、４２０および４３０のそれぞれのセグメントオブジェクトが先行する）データオブジェクト４１０、４２０および４３０が重複排除データシステムに追加される例示的な時系列４００を示す。この例において、識別モジュール１０４は、ガーベジコレクションプロセス４５０中に重複排除データシステムに追加されるセグメントオブジェクト４３２を識別してもよい。
【００３０】
本明細書で用いるように、用語「セグメントオブジェクト」は、データのセグメント、データのブロック、またはデータ重複排除用に用いられるデータの他の任意の適切な単位を指してもよい。同様に、用語「データオブジェクト」は、１つまたは複数のセグメントオブジェクトを包む、かつ／または指すことができる任意のオブジェクト（ファイルなど）を指してもよい。本明細書で用いられるように、用語「ガーベジコレクションプロセス」は、参照されないデータセグメントを重複排除データシステムから除去するか、かつ／または除去を支援することによって、参照されないデータセグメントを削除し、かつ／または記憶スペースを回復するプロセスの任意の部分を指してもよい。いくつかの例において、「ガーベジコレクションプロセス」には、マークアンドスイーププロセスおよび／または参照カウントプロセスの一部を含んでもよい。
【００３１】
識別モジュール１０４は、様々なシナリオでステップ３０４を実行してもよい。例えば、識別モジュール１０４は、重複排除データシステム内におけるセグメントオブジェクトの生成（例えば、データオブジェクトによって参照されるセグメントオブジェクトが重複排除データシステムに追加、コピー、および／またはアップロードされること）を識別することによって、セグメントオブジェクトを識別してもよい。識別モジュール１０４は、任意の適切な方法でセグメントオブジェクトの生成を識別してもよい。例えば、識別モジュール１０４は、セグメントオブジェクトの生成を識別する通信を重複排除データシステムから受信してもよい。追加または代替として、識別モジュール１０４には、セグメントオブジェクトを生成する命令が通過し得るフィルタドライバの一部を含んでもよい。
【００３２】
別のシナリオにおいて、識別モジュール１０４は、重複排除データシステム内のセグメントオブジェクトへの新しい参照を識別することによって、セグメントオブジェクトを識別してもよい。例えば、セグメントオブジェクトは、最初は、単一のデータオブジェクトによって参照される可能性がある。次に、識別モジュール１０４は、追加データオブジェクトによる、セグメントオブジェクトへの新しい参照を識別する可能性がある。続いて最初の参照が除去された場合（例えば、セグメントオブジェクトを最初に参照した単一のデータオブジェクトが削除される）、および（例えば、ガーベジコレクションプロセスが、追加データオブジェクトがセグメントオブジェクトを参照する前に追加データオブジェクトを分析したので）ガーベジコレクションプロセスが、新しい参照に気付くことなく最初の参照が除去されるのを観察した場合に、以下でより詳細に説明するように、本明細書で説明するシステムは、セグメントオブジェクトを識別した後でセグメントオブジェクトをロックすることによって、セグメントオブジェクトを不当な削除から防いでもよい。
【００３３】
ステップ３０４に戻ると、識別モジュール１０４は、ガーベジコレクションプロセス中に追加されたセグメントオブジェクトを任意の適切な方法で識別してもよい。例えば、識別モジュール１０４は、ひとたびガーベジコレクションプロセスが始まると、新しいデータセグメント用に重複排除データシステムを監視することによって、セグメントオブジェクトを識別してもよい。前に言及したように、「ガーベジコレクションプロセス」には、参照されないデータセグメントを除去するためのプロセスの任意の部分を含んでもよい。したがって、識別モジュール１０４は、様々な時間に監視を開始してもよい。例えば、識別モジュール１０４は、重複排除データシステムがガーベジコレクションデーモンをロードした場合に、監視を開始してもよい。追加または代替として、識別モジュール１０４は、マークアンドスイーププロセスのマーキング段階の直前に監視を開始してもよい。
【００３４】
いくつかの例において、識別モジュール１０４はまた、ひとたびガーベジコレクションプロセスが完了すると、新しいデータセグメント用の重複排除データシステムの監視を終了してもよい。例えば、識別モジュール１０４は、ひとたびガーベジコレクションデーモンが終了すると、新しいデータセグメント用の監視を終了してもよい。追加または代替として、識別モジュール１０４は、マークアンドスイーププロセスのスイープ段階の直後に監視を終了してもよい。いくつかの例において、識別モジュール１０４は、ガーベジコレクションプロセスが進行するにつれて、監視の範囲を低減してもよい。例えば、ガーベジコレクションプロセスが、参照されないセグメントオブジェクトを領域ごとにスイープするように構成される場合に、識別モジュール１０４は、まだスイープされていない領域だけに追加された新しいデータセグメントを監視してもよい。
【００３５】
図３に戻ると、ステップ３０６において、本明細書で説明するシステムの１つまたは複数は、ガーベジコレクションプロセスによるセグメントオブジェクトの除去を防ぐために、セグメントオブジェクトをロックしてもよい。例えば、ステップ３０６において、ロッキングモジュール１０６は、図２におけるコンピューティングシステム２０２の一部として、重複排除データシステム１２０のガーベジコレクションプロセス中に重複排除データシステム１２０に追加されたセグメントオブジェクトをロックしてもよい。別の例において、ロッキングモジュール１０６は、ガーベジコレクションプロセス４５０によるセグメントオブジェクト４３２の除去を防ぐために、図４におけるセグメントオブジェクト４３２をロックしてもよい。
【００３６】
ロッキングモジュール１０６は、任意の適切な方法でステップ３０６を実行してもよい。例えば、ロッキングモジュール１０６は、ガーベジコレクションプロセスがセグメントオブジェクトを削除できないように、セグメントオブジェクトに対する許可を変更することによって、セグメントオブジェクトをロックしてもよい。追加または代替として、ロッキングモジュール１０６は、フィルタドライバの一部を含んでもよく、かつセグメントオブジェクトを除去するどんな試みもインターセプトしてもよい。いくつかの例において、ロッキングモジュール１０６は、セグメントオブジェクトを無視するようにガーベジコレクションプロセスに命令してもよい。
【００３７】
いくつかの例において、ロッキングモジュール１０６は、セグメントオブジェクトに対する参照を、ロックされたセグメントオブジェクトマップに追加することによって、セグメントオブジェクトをロックしてもよい。ロックされたセグメントオブジェクトマップには、ロックされたセグメントオブジェクトを識別するための任意の適切なデータ構造を含んでもよい。例えば、ロックされたセグメントオブジェクトマップには、ビットマップを含んでもよい。例として図５を用いると、例示的なシステム５００には、ロックされたセグメントオブジェクトマップ５０６を含んでもよい。この例において、ロッキングモジュール１０６は、セグメントオブジェクトに対する参照を追加するために、ロックされたセグメントオブジェクトマップ５０６に書き込んでもよい。以下でより詳細に説明するように、例示的なシステム５００にはまた、重複排除データシステム１２０から削除してもよい明らかに参照されないセグメントオブジェクトを識別するために、ロックされたセグメントオブジェクトマップ５０６を参照し得るガーベジコレクションモジュール５１０を含んでもよい。
【００３８】
セグメントオブジェクトを参照するデータオブジェクトが、セグメントオブジェクト後に重複排除データシステムに追加されるゆえに、セグメントオブジェクトが明らかに参照されない間、ロッキングモジュール１０６は、セグメントオブジェクトをロックすることによって、ガーベジコレクションプロセスが誤ってセグメントオブジェクトを削除するのを防いでもよい。例として図４を用いると、データオブジェクト４３０は、セグメントオブジェクト４３２、４３４および４３６を参照可能である。この例において、データオブジェクトを重複排除データシステムに追加する場合に、データオブジェクト４３０が重複排除データシステムに追加されるとデータオブジェクト４３０がセグメントオブジェクト４３２、４３４および４３６に対する正確な参照を含み得るように、セグメントオブジェクト４３２、４３４および４３６は、データオブジェクト４３０に先行してもよい。ロッキングモジュール１０６は、セグメントオブジェクト４３２、４３４および４３６のそれぞれが重複排除データシステムに追加されたときに、それらをロックしてもよい。したがって、ガーベジコレクションプロセス４５０が、データオブジェクト４３０を説明するこれらのセグメントオブジェクトのいずれかを調べた場合に、ガーベジコレクションプロセス４５０は、データオブジェクト４３０がセグメントオブジェクトを参照することを観察できないにもかかわらず、これらのセグメントオブジェクトをそのまま残してもよい。
【００３９】
図３に戻ると、ステップ３０８において、本明細書で説明するシステムの１つまたは複数は、ガーベジコレクションプロセス後にセグメントオブジェクトをロック解除してもよい。例えば、ステップ３０８において、ロック解除モジュール１０８は、図２におけるコンピューティングシステム２０２の一部として、重複排除データシステム１２０のガーベジコレクションプロセス中に重複排除データシステム１２０に追加されたセグメントオブジェクトをロック解除してもよい。別の例において、ロック解除モジュール１０８は、ガーベジコレクションプロセス４５０後に（例えば通常状態４４０（ｂ）中に）、図４におけるセグメントオブジェクト４３２をロック解除してもよい。
【００４０】
上記のように、ロッキングモジュール１０６は、様々な方法でセグメントオブジェクトをロックしてもよい。かかるものとして、ロック解除モジュール１０８もまた、様々な方法でセグメントオブジェクトをロック解除してもよい。例えば、ロック解除モジュール１０８は、セグメントオブジェクトに対する許可を変更することによってセグメントオブジェクトをロック解除し、（例えば、ガーベジコレクションプロセスが次に走行したときに）ガーベジコレクションプロセスがセグメントオブジェクトを削除できるようにしてもよい。追加または代替として、ロッキングモジュール１０６には、セグメントオブジェクトを除去するどんな試みもインターセプトするように設計されたフィルタドライバの一部を含んでもよく、ロック解除モジュール１０８は、ロッキングモジュール１０６をアンロードしてもよい。いくつかの例において、ロック解除モジュール１０８は、ロッキングモジュール１０６によってガーベジコレクションプロセスに送信されたどんな命令も消去および／または反転してもよい。
【００４１】
前述のように、いくつかの例において、ロッキングモジュール１０６は、セグメントオブジェクトに対する参照を、ロックされたセグメントオブジェクトマップに追加することによって、セグメントオブジェクトをロックしてもよい。それに応じて、ロック解除モジュール１０８は、ロックされたセグメントオブジェクトマップに影響を及ぼすことによってセグメントオブジェクトをロック解除してもよい。
【００４２】
例えば、ロック解除モジュール１０８は、ロックされたセグメントオブジェクトマップを消去してもよい。この例において、ロックされたセグメントオブジェクトマップは、次にガーベジコレクションプロセスが始まるまで空であってもよい。別の例において、ロック解除モジュール１０８は、ロックされたセグメントオブジェクトマップを削除してもよい。例えば、ロック解除モジュール１０８は、ロックされたセグメントオブジェクトマップを含むファイルを削除し、かつ／またはロックされたセグメントオブジェクトマップに用いられるメモリを解放する。この例において、ロッキングモジュール１０６は、ガーベジコレクションプロセスが次に始まった場合に、ロックされたセグメントオブジェクトマップを後で再生成してもよい。追加または代替として、ロック解除モジュール１０８は、セグメントオブジェクトに対する参照を、ロックされたセグメントオブジェクトマップから除去してもよい。例えば、ロック解除モジュール１０８は、セグメントオブジェクトに対応するビットマップにおけるビットを消去してもよい。例として図５を用いると、ロック解除モジュール１０８は、セグメントオブジェクトをロック解除するために、ロックされたセグメントオブジェクトマップ５０６を消去、削除および／または修正してもよい。ステップ３０８が完了すると、図３における例示的な方法３００は、終了してもよい。
【００４３】
図６は、重複排除データシステムにおけるガーベジコレクション用の例示的なコンピュータ実行方法６００の流れ図である。図６に示すステップは、任意の適切なコンピュータ実行可能コードおよび／またはコンピューティングシステムによって実行してもよい。いくつかの実施形態において、図６に示すステップは、図１におけるシステム１００、図２におけるシステム２００、および／または図５におけるシステム５００のコンポーネントの１つまたは複数によって実行してもよい。
【００４４】
図６に示すように、ステップ６０２において、本明細書で説明するシステムの１つまたは複数は、ガーベジコレクションプロセス前に重複排除データシステムに追加された追加セグメントオブジェクトを識別してもよい。例えば、ステップ６０２において、ガーベジコレクションモジュール５１０は、図５におけるシステム５００の一部として、ガーベジコレクションプロセス前に重複排除データシステム１２０に追加された追加セグメントオブジェクトを識別してもよい。
【００４５】
ガーベジコレクションモジュール５１０は、任意の適切な方法でステップ６０２を実行してもよい。例えば、ガーベジコレクションモジュール５１０は、マークアンドスイーププロセスのスイープ動作中に追加セグメントオブジェクトを識別してもよい。追加または代替として、ガーベジコレクションモジュール５１０は、セグメントオブジェクトに対する参照数を評価する間に追加セグメントオブジェクトを識別してもよい。例えば、図４に示すように、ガーベジコレクションモジュール５１０は、ガーベジコレクションプロセス４５０の前の通常状態４４０（ａ）中にセグメントオブジェクト４１２を識別してもよい。
【００４６】
図６に戻ると、ステップ６０４において、本明細書で説明するシステムの１つまたは複数は、ガーベジコレクションプロセスの一部として、追加セグメントオブジェクトが重複排除データシステム内で参照されないと判定してもよい。例えば、ステップ６０４において、ガーベジコレクションモジュール５１０は、図５におけるシステム５００の一部として、追加セグメントオブジェクトが重複排除データシステム１２０内で参照されないと判定してもよい。
【００４７】
ガーベジコレクションモジュール５１０は、追加データセグメントが参照されないと任意の適切な方法で判定してもよい。例えば、ガーベジコレクションモジュール５１０は、追加データセグメントがマークアンドスイープ動作においてマークを付けられなかったと判定してもよい。追加または代替として、ガーベジコレクションモジュール５１０は、追加データセグメント用の参照カウントがゼロであると判定してもよい。いくつかの例において、ガーベジコレクションモジュール５１０は、追加データセグメントが、追加データセグメントを参照するものとして、どんなデータオブジェクトもリストしていないことに気付く場合がある。
【００４８】
例として図４を用いると、セグメントオブジェクト４１２は、通常状態４４０（ａ）中にデータオブジェクトによる参照がないことを明示してもよい。なぜなら、データオブジェクト４１０（例えば、参照セグメントオブジェクト４１２を参照するただ一つのデータオブジェクト）は、ガーベジコレクションプロセス４５０が既に進行中になるまで、重複排除データシステムに追加されない可能性があるからである。したがって、ガーベジコレクションモジュール５１０は、セグメントオブジェクト４１２を参照するデータオブジェクト４１０の追加が、たとえ差し迫っていても、セグメントオブジェクト４１２が重複排除データシステム内で参照されないと判定する可能性がある。
【００４９】
図６に戻ると、ステップ６０６において、本明細書で説明するシステムの１つまたは複数は、追加セグメントオブジェクトを重複排除データシステムから除去してもよい。例えば、ステップ６０６において、ガーベジコレクションモジュール５１０は、図５におけるシステム５００の一部として、追加セグメントオブジェクトを重複排除データシステム１２０から除去してもよい。追加例として、ガーベジコレクションモジュール５１０は、図４におけるセグメントオブジェクト４１２を重複排除データシステムから除去してもよい。
【００５０】
ガーベジコレクションモジュール５１０は、任意の適切な方法でステップ６０６を実行してもよい。例えば、ガーベジコレクションモジュール５１０は、追加セグメントオブジェクトを記憶装置から削除してもよい。
【００５１】
再び図４を参照すると、いくつかの例において、（例えば、ガーベジコレクションプロセス４５０が、セグメントオブジェクト４１２および／または４１４を除去する前に、データオブジェクト４１０を認識できない場合に）ガーベジコレクションモジュール５１０は、セグメントはオブジェクト４１２および／または４１４を、重複排除データシステムから時期尚早に除去する可能性がある。しかしながら、以下でより詳細に説明するように、いくつかの例において、本明細書で説明するシステムは、これらの時期尚早に除去されたセグメントオブジェクト４１２および／または４１４を後で回復可能である。ステップ６０６が完了すると、図６における例示的な方法６００は、終了してもよい。
【００５２】
図７は、重複排除データシステムにおけるガーベジコレクション用の例示的なコンピュータ実行方法７００の流れ図である。図７に示すステップは、任意の適切なコンピュータ実行可能コードおよび／またはコンピューティングシステムによって実行してもよい。いくつかの実施形態において、図６に示すステップは、図１におけるシステム１００、図２におけるシステム２００、および／または図５におけるシステム５００のコンポーネントの１つまたは複数によって実行してもよい。
【００５３】
図７に示すように、ステップ７０２において、本明細書で説明するシステムの１つまたは複数は、追加セグメントオブジェクトが追加された後で重複排除データシステムに追加されたデータオブジェクトを識別してもよい。例えば、ステップ７０２において、回復モジュール５１２は、図５におけるシステム５００の一部として、追加セグメントオブジェクトが追加された後で重複排除データシステム１２０に追加されたデータオブジェクトを識別してもよい。例として図４を用いると、回復モジュール５１２は、データオブジェクト４１０を識別してもよい。
【００５４】
回復モジュール５１２は、任意の適切な方法でステップ７０２を実行してもよい。例えば、回復モジュール５１２は、重複排除データシステムへのデータオブジェクトの追加を観察するフィルタドライバの一部を含んでもよい。追加または代替として、回復モジュール５１２は、データオブジェクトを識別する通信を重複排除データシステムから受信することによって、データオブジェクトを識別してもよい。
【００５５】
ステップ７０４において、本明細書で説明するシステムの１つまたは複数は、データオブジェクトが追加セグメントオブジェクトを参照すると判定してもよい。例えば、ステップ７０４において、回復モジュール５１２は、図５におけるシステム５００の一部として、データオブジェクトが、重複排除データシステム１２０から除去された追加セグメントオブジェクトを参照すると判定してもよい。例として図４を用いると、回復モジュール５１２は、データオブジェクト４１０が、セグメントオブジェクト４１２（および／または例えばセグメントオブジェクト４１４）を参照すると判定してもよい。
【００５６】
回復モジュール５１２は、任意の適切な方法でステップ７０４を実行してもよい。例えば、回復モジュール５１２は、データオブジェクトによって参照される追加セグメントオブジェクトを識別する通信を重複排除データシステムから受信することによって、データオブジェクトが追加セグメントオブジェクトを参照すると判定してもよい。追加または代替として、回復モジュール５１２は、データオブジェクトが元のままであることを検証しようと試み、かつ追加セグメントオブジェクトが重複排除データシステムから除去されたことを発見することによって、データオブジェクトが追加セグメントオブジェクトを参照すると判定してもよい。
【００５７】
ステップ７０６において、本明細書で説明するシステムの１つまたは複数は、追加セグメントオブジェクトの別のコピーを検索してもよい。例えば、ステップ７０６において、回復モジュール５１２は、図５におけるシステム５００の一部として、重複排除データシステム１２０から除去された追加セグメントオブジェクトの別のコピーを検索してもよい。例として図４を用いると、回復モジュール５１２は、セグメントオブジェクト４１２（および／または例えばセグメントオブジェクト４１４）の別のコピーを検索してもよい。
【００５８】
回復モジュール５１２は、任意の適切な方法でステップ７０６を実行してもよい。例えば、回復モジュール５１２は、追加セグメントオブジェクトの別のコピーをバックアップから検索してもよい。追加または代替として、回復モジュール５１２は、データオブジェクトを重複排除データシステムに追加しようと試みたプロセスにエラーメッセージを送信してもよい（例えば、データオブジェクトおよび／またはデータオブジェクトが参照するセグメントオブジェクトを送信する別の試みを行うプロセスに帰着する）。いくつかの例において、回復モジュール５１２は、（例えば、削除ヒープから）追加セグメントオブジェクトを回復および／または復活させてもよい。ステップ７０６が完了すると、図７における例示的な方法７００は、終了してもよい。
【００５９】
いくつかの実施形態において、本明細書で説明するシステムおよび方法はまた、ガーベジコレクションプロセス中に重複排除データシステムに追加されたデータオブジェクトをロックしてもよい。例えば、本明細書で説明するシステムおよび方法は、１）ガーベジコレクションプロセス中に重複排除データシステムに追加された少なくとも１つのデータオブジェクトを識別し、２）ガーベジコレクションプロセスによるデータオブジェクトの除去を防ぐために、データオブジェクトをロックし、次に３）ガーベジコレクションプロセス後にデータオブジェクトをロック解除してもよい。
【００６０】
重複排除データシステムにおけるデータオブジェクトが、多数のデータオブジェクトコレクション（例えば、多重バックアップ）によって参照される可能性があるので、ガーベジコレクションプロセス中にデータオブジェクトをロックすることによって、不当な削除からデータオブジェクトを防いでもよい。例えば、第１のバックアップが、ガーベジコレクションプロセス中にデータオブジェクトを参照する可能性があり、第２のバックアップが、ガーベジコレクションプロセス中にデータオブジェクトを参照しない可能性があり、ガーベジコレクションプロセスは、データオブジェクトが参照されることを考慮せずに、データオブジェクトが参照されないことを考慮する可能性がある。
【００６１】
本明細書で説明するシステムおよび方法は、任意の適切な方法で上記のステップを実行してもよい。例えば、本明細書で説明するシステムおよび方法は、データセグメントの識別、ロッキング、およびロック解除に関して前に説明した任意の適切なアプローチを用いて、上記のステップを実行してもよい。
【００６２】
例えば、識別モジュール１０４は、１）重複排除データシステム内におけるデータオブジェクトの生成を識別すること、および／または２）（例えば、バックアップによる）重複排除データシステム内のデータオブジェクトに対する新しい参照を識別することによって、ガーベジコレクション動作中に重複排除データシステムに追加されたデータオブジェクトを識別してもよい。いくつかの例において、識別モジュール１０４は、ひとたびガーベジコレクションプロセスが始まると、新しいデータオブジェクト用に重複排除データシステムを監視することによって、データオブジェクトを識別するようにプログラムしてもよい。識別モジュール１０４はまた、ひとたびガーベジコレクションプロセスが完了すると、新しいデータオブジェクト用の重複排除データシステムの監視を終了するようにプログラムしてもよい。識別モジュール１０４は、セグメントオブジェクトの識別に関して前に説明した技法を含む任意の適切な方法で、これらのタスクのいずれかを実行してもよい。
【００６３】
ロッキングモジュール１０６は、データオブジェクトに対する参照を、ロックされたデータオブジェクトマップに追加することによって、データオブジェクトをロックするようにプログラムしてもよい。いくつかの例において、ロックされたデータオブジェクトマップには、ロックされたセグメントオブジェクトマップの少なくとも一部を含んでもよい（例えば、ロッキングモジュール１０６は、データオブジェクトおよびセグメントオブジェクトの両方用に１つのマップを用いてもよい）。ロッキングモジュール１０６は、セグメントオブジェクトをロックすることに関して前に説明した技法を含む任意の適切な方法で、このタスクを実行してもよい。
【００６４】
ロック解除モジュール１０８は、１）ロックされたデータオブジェクトマップを消去すること、２）ロックされたデータオブジェクトマップを削除すること、および／または３）データオブジェクトに対する参照を、ロックされたデータオブジェクトマップから除去することによって、ガーベジコレクションプロセス後にデータオブジェクトをロック解除するようにプログラムしてもよい。ロック解除モジュール１０８は、セグメントオブジェクトをロック解除することに関して前に説明した技法を含む任意の適切な方法で、これらのタスクのいずれかを実行してもよい。
【００６５】
上記で詳述したように、ガーベジコレクションプロセス中に追加されたセグメントオブジェクト（例えば、図４におけるセグメントオブジェクト４３２、４３４および４３６など）をロックすることによって、本明細書で説明するシステムおよび方法は、対応するデータオブジェクト（例えば、図４におけるデータオブジェクト４３０など）がまだ重複排除データシステムに追加されていないセグメントオブジェクトの望ましくない削除を防いでもよい。さらに、これらのシステムおよび方法は、これらの境界事例、すなわちセグメントオブジェクト（例えば、図４におけるセグメントオブジェクト４１２および４１４など）が削除されたこれらの境界事例における望ましくない削除を回復してもよい。なぜなら、１）ガーベジコレクションプロセスが始まる前に、セグメントオブジェクトが重複排除データシステムに追加され、２）対応するデータオブジェクト（例えば、図４におけるデータオブジェクト４１０など）が、ガーベジコレクションプロセスが既に始まった後まで追加されなかったからである。かかるものとして、本明細書で説明するシステムおよび方法は、多くの場合において、ガーベジコレクション動作中の望ましくない削除を効率的に防ぎ、比較的少数の境界事例における望ましくない削除のよりコストのかかる回復を場合によっては実行してもよい。
【００６６】
本明細書で説明する様々なシステムは、様々な方法で展開してもよい。例えば、図１における例示的なシステム１００の全てまたは一部は、クラウドコンピューティングまたはネットワークベース環境の一部を表してもよい。クラウドコンピューティング環境は、インターネットを介して様々なサービスおよびアプリケーションを提供してもよい。これらのクラウドベースサービス（例えば、サービスとしてのソフトウェア、サービスとしてのプラットホーム、サービスとしてのインフラストラクチャ等）は、ウェブブラウザまたは他の遠隔インターフェースを介してアクセス可能であってもよい。本明細書で説明する様々な機能は、遠隔デスクトップ環境または任意の他のクラウドベースコンピューティング環境を介して提供してもよい。
【００６７】
図８は、本明細書で説明および／または図示する実施形態の１つまたは複数を実行できる例示的なコンピューティングシステム８１０のブロック図である。コンピューティングシステム８１０は、コンピュータ可読命令を実行できる任意のシングルもしくはマルチプロセッサコンピューティング装置またはシステムを広く表す。コンピューティングシステム８１０の例には、限定するわけではないが、ワークステーション、ラップトップ、クライアント側端末、サーバ、分散コンピューティングシステム、ハンドヘルド装置、または任意の他のコンピューティングシステムもしくは装置が含まれる。コンピューティングシステム８１０には、その最も基本的な構成において、少なくとも１つのプロセッサ８１４およびシステムメモリ８１６を含んでもよい。
【００６８】
プロセッサ８１４は、一般に、データを処理できるかまたは命令を解釈および実行できる任意のタイプまたは形態の処理装置を表す。ある実施形態において、プロセッサ８１４は、ソフトウェアアプリケーションまたはモジュールから命令を受信してもよい。これらの命令は、本明細書で説明および／または図示する例示的な実施形態の１つまたは複数の機能を、プロセッサ８１４に実行させてもよい。例えば、プロセッサ８１４は、本明細書で説明する識別ステップ、監視ステップ、終了ステップ、追加ステップ、消去ステップ、削除ステップ、除去ステップ、判定ステップ、および／または検索ステップの１つまたは複数を、単独でまたは他の要素と一緒に実行するか、かつ／または実行するための手段であってもよい。プロセッサ８１４はまた、本明細書で説明および／または図示する任意の他のステップ、方法、またはプロセスを実行するか、かつ／または実行するための手段であってもよい。
【００６９】
システムメモリ８１６は、一般に、データおよび／または他のコンピュータ可読命令を記憶できる任意のタイプまたは形態の揮発性または不揮発性記憶装置または媒体を表す。システムメモリ８１６の例には、限定するわけではないが、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、フラッシュメモリ、または任意の他の適切なメモリ装置が含まれる。要求はされないが、ある実施形態において、コンピューティングシステム８１０には、揮発性メモリユニット（例えば、システムメモリ８１６など）および不揮発性記憶装置（例えば、以下で詳細に説明するような主記憶装置８３２など）の両方を含んでもよい。一例において、図１のモジュール１０２の１つまたは複数は、システムメモリ８１６にロードしてもよい。
【００７０】
ある実施形態において、例示的なコンピューティングシステム８１０にはまた、プロセッサ８１４およびシステムメモリ８１６に加えて、１つまたは複数のコンポーネントまたは要素を含んでもよい。例えば、図８に示すように、コンピューティングシステム８１０には、メモリコントローラ８１８、入力／出力（Ｉ／Ｏ）コントローラ８２０、および通信インターフェース８２２を含んでもよく、これらのそれぞれは、通信インフラストラクチャ８１２を介して相互接続してもよい。通信インフラストラクチャ８１２は、一般に、コンピューティング装置の１つまたは複数のコンポーネント間の通信を促進できる任意のタイプまたは形態のインフラストラクチャを表す。通信インフラストラクチャ８１２の例には、限定するわけではないが、通信バス（ＩＳＡ、ＰＣＩ、ＰＣＩｅまたは類似のバスなど）およびネットワークが含まれる。
【００７１】
メモリコントローラ８１８は、一般に、メモリもしくはデータを扱えるか、またはコンピューティングシステム８１０の１つまたは複数のコンポーネント間の通信を制御することができる任意のタイプまたは形態の装置を表す。例えば、ある実施形態において、メモリコントローラ８１８は、通信インフラストラクチャ８１２を介して、プロセッサ８１４、システムメモリ８１６、およびＩ／Ｏコントローラ８２０間の通信を制御してもよい。ある実施形態において、メモリコントローラ８１８は、識別、監視、終了、追加、消去、削除、除去、判定、および／または検索など、本明細書で説明および／または図示するステップまたは機能の１つまたは複数を、単独でまたは他の要素と一緒に実行するか、かつ／または実行するための手段であってもよい。
【００７２】
Ｉ／Ｏコントローラ８２０は、一般に、コンピューティング装置の入力および出力機能を調整および／または制御できる任意のタイプまたは形態のモジュールを表す。例えば、ある実施形態において、Ｉ／Ｏコントローラ８２０は、プロセッサ８１４、システムメモリ８１６、通信インターフェース８２２、ディスプレイアダプタ８２６、入力インターフェース８３０、および記憶インターフェース８３４など、コンピューティングシステム８１０の１つまたは複数の要素間におけるデータ転送を制御または促進してもよい。Ｉ／Ｏコントローラ８２０は、例えば、本明細書で説明する識別ステップ、監視ステップ、終了ステップ、追加ステップ、消去ステップ、削除ステップ、除去ステップ、判定ステップ、および／または検索ステップの１つまたは複数を、単独でまたは他の要素と一緒に実行するか、かつ／または実行するための手段となるように用いてもよい。Ｉ／Ｏコントローラ８２０はまた、本開示で述べる他のステップおよび機能を実行するか、かつ／または実行するための手段となるように用いてもよい。
【００７３】
通信インターフェース８２２は、例示的なコンピューティングシステム８１０と１つまたは複数の追加装置との間の通信を促進できる任意のタイプまたは形態の通信装置またはアダプタを広く表す。例えば、ある実施形態において、通信インターフェース８２２は、コンピューティングシステム８１０と、追加コンピューティングシステムを含むプライベートまたはパブリックネットワークとの間の通信を促進してもよい。通信インターフェース８２２の例には、限定するわけではないが、有線ネットワークインターフェース（ネットワークインターフェースカードなど）、無線ネットワークインターフェース（無線ネットワークインターフェースカードなど）、モデム、および任意の他の適切なインターフェースが含まれる。少なくとも一実施形態において、通信インターフェース８２２は、インターネットなどのネットワークへの直接リンクを介して、遠隔サーバへの直接接続を提供してもよい。通信インターフェース８２２はまた、例えば、ローカルエリアネットワーク（イーサネットネットワークなど）、パーソナルエリアネットワーク、電話もしくはケーブルネットワーク、携帯電話接続、衛星データ接続、または任意の他の適切な接続を通して、かかる接続を間接的に提供してもよい。
【００７４】
ある実施形態において、通信インターフェース８２２はまた、外部バスまたは通信チャネルを介して、コンピューティングシステム８１０と１つまたは複数の追加ネットワークまたは記憶装置との間の通信を促進するように構成されたホストアダプタを表してもよい。ホストアダプタの例には、限定するわけではないが、ＳＣＳＩホストアダプタ、ＵＳＢホストアダプタ、ＩＥＥＥ１３９４ホストアダプタ、ＳＡＴＡおよびｅＳＡＴＡホストアダプタ、ＡＴＡおよびＰＡＴＡホストアダプタ、ファイバチャネルインターフェースアダプタ、イーサネットアダプタ等が含まれる。また、通信インターフェース８２２によって、コンピューティングシステム８１０は、分散または遠隔コンピューティングに従事することが可能になり得る。例えば、通信インターフェース８２２は、実行用に、遠隔装置から命令を受信するか、または遠隔装置に命令を送信してもよい。ある実施形態において、通信インターフェース８２２は、本明細書で開示する識別ステップ、監視ステップ、終了ステップ、追加ステップ、消去ステップ、削除ステップ、除去ステップ、判定ステップ、および／または検索ステップの１つまたは複数を、単独でまたは他の要素と一緒に実行するか、かつ／または実行するための手段であってもよい。通信インターフェース８２２はまた、本開示で述べる他のステップおよび機能を実行するか、かつ／または実行するための手段となるように用いてもよい。
【００７５】
図８に示すように、コンピューティングシステム８１０にはまた、ディスプレイアダプタ８２６を介して通信インフラストラクチャ８１２に結合される少なくとも１つのディスプレイ装置８２４を含んでもよい。ディスプレイ装置８２４は、一般に、ディスプレイアダプタ８２６によって転送された情報を視覚的に表示できる任意のタイプまたは形態の装置を表す。同様に、ディスプレイアダプタ８２６は、一般に、ディスプレイ装置８２４における表示のために、通信インフラストラクチャ８１２から（または当該技術分野において周知のようなフレームバッファから）グラフィックス、テキスト、および他のデータを転送するように構成された任意のタイプまたは形態の装置を表す。
【００７６】
図８に示すように、例示的なコンピューティングシステム８１０にはまた、入力インターフェース８３０を介して通信インフラストラクチャ８１２に結合される少なくとも１つの入力装置８２８を含んでもよい。入力装置８２８は、一般に、コンピュータまたは人間によって生成された入力を例示的なコンピューティングシステム８１０に供給できる任意のタイプまたは形態の装置を表す。入力装置８２８の例には、限定するわけではないが、キーボード、ポインティング装置、音声認識装置、または任意の他の入力装置が含まれる。少なくとも一実施形態において、入力装置８２８は、本明細書で開示する識別ステップ、監視ステップ、終了ステップ、追加ステップ、消去ステップ、削除ステップ、除去ステップ、判定ステップ、および／または検索ステップの１つまたは複数を、単独でまたは他の要素と一緒に実行するか、かつ／または実行するための手段であってもよい。入力装置８２８はまた、本開示で述べる他のステップおよび機能を実行するか、かつ／または実行するための手段となるように用いてもよい。
【００７７】
図８に示すように、例示的なコンピューティングシステム８１０にはまた、記憶インターフェース８３４を介して通信インフラストラクチャ８１２に結合される主記憶装置８３２およびバックアップ記憶装置８３３を含んでもよい。記憶装置８３２および８３３は、一般に、データおよび／または他のコンピュータ可読命令を記憶できる任意のタイプまたは形態の記憶装置または媒体を表す。例えば、記憶装置８３２および８３３は、磁気ディスクドライブ（例えば、いわゆるハードドライブ）、フロッピーディスクドライブ、磁気テープドライブ、光ディスクドライブ、フラッシュドライブ等であってもよい。記憶インターフェース８３４は、一般に、コンピューティングシステム８１０の記憶装置８３２および８３３と他のコンポーネントとの間でデータを転送するための任意のタイプまたは形態のインターフェースまたは装置を表す。一例において、図１の重複排除データシステム１２０は、主記憶装置８３２に記憶してもよい。
【００７８】
ある実施形態において、記憶装置８３２および８３３は、コンピュータソフトウェア、データ、または他のコンピュータ可読情報を記憶するように構成されたリムーバブル記憶ユニットから読み出すか、かつ／またはそこに書き込むように構成してもよい。適切なリムーバブル記憶ユニットの例には、限定するわけではないが、フロッピーディスク、磁気テープ、光ディスク、フラッシュメモリ装置等が含まれる。記憶装置８３２および８３３にはまた、コンピュータソフトウェア、データ、または他のコンピュータ可読命令をコンピューティングシステム８１０にロードできるようにするための他の類似構造または装置を含んでもよい。例えば、記憶装置８３２および８３３は、ソフトウェア、データ、または他のコンピュータ可読情報を読み出し、かつ書き込むように構成してもよい。記憶装置８３２および８３３はまた、コンピューティングシステム８１０の一部であってもよく、または他のインターフェースシステムを介してアクセスされる別個の装置であってもよい。
【００７９】
ある実施形態において、記憶装置８３２および８３３は、例えば、本明細書で開示する識別ステップ、監視ステップ、終了ステップ、追加ステップ、消去ステップ、削除ステップ、除去ステップ、判定ステップ、および／または検索ステップの１つまたは複数を、単独でまたは他の要素と一緒に実行するか、かつ／または実行するための手段となるように用いてもよい。記憶装置８３２および８３３はまた、本開示で述べる他のステップおよび機能を実行するか、かつ／または実行するための手段となるように用いてもよい。
【００８０】
多くの他の装置またはサブシステムを、コンピューティングシステム８１０に接続してもよい。反対に、図８に示すコンポーネントおよび装置の全てが、本明細書で説明および／または図示する実施形態を実行するために存在する必要があるわけではない。上記で参照した装置およびサブシステムはまた、図８に示す方法とは異なる方法で相互接続してもよい。コンピューティングシステム８１０はまた、任意の数のソフトウェア、ファームウェア、および／またはハードウェア構成を用いてもよい。本明細書で開示する例示的な実施形態の１つまたは複数は、例えば、コンピュータ可読媒体上のコンピュータプログラム（コンピュータソフトウェア、ソフトウェアアプリケーション、コンピュータ可読命令、またはコンピュータ制御論理とも呼ばれる）としてコード化してもよい。用語「コンピュータ可読媒体」は、一般に、コンピュータ可読命令を記憶または担持できる任意の形態の装置、キャリア、または媒体を指す。コンピュータ可読媒体の例には、限定するわけではないが、搬送波などの伝送型媒体、および磁気記憶媒体（例えば、ハードディスクドライブおよびフロッピーディスク）、光記憶媒体（例えば、ＣＤ−ＲＯＭまたはＤＶＤ−ＲＯＭ）、電子記憶媒体（例えば、ソリッドステートドライブおよびフラッシュ媒体）などの物理媒体、ならびに他の分散システムが含まれる。
【００８１】
コンピュータプログラムを含むコンピュータ可読媒体は、コンピューティングシステム８１０にロードしてもよい。次に、コンピュータ可読媒体上に記憶されたコンピュータプログラムの全てまたは一部は、システムメモリ８１６、ならびに／または記憶装置８３２および８３３の様々な部分に記憶してもよい。プロセッサ８１４によって実行されると、コンピューティングシステム８１０にロードされたコンピュータプログラムが、本明細書で説明および／または図示する例示的な実施形態の１つまたは複数における機能を、プロセッサ８１４に実行させるか、かつ／またはプロセッサ８１４を、実行するための手段にしてもよい。追加または代替として、本明細書で説明および／または図示する例示的な実施形態の１つまたは複数は、ファームウェアおよび／またはハードウェアにおいて実行してもよい。例えば、コンピューティングシステム８１０は、本明細書で開示する例示的な実施形態の１つまたは複数を実行するように適合された特定用途向け集積回路（ＡＳＩＣ）として構成してもよい。
【００８２】
図９は、例示的なネットワークアーキテクチャ９００のブロック図であり、そこでは、クライアントシステム９１０、９２０、９３０、ならびにサーバ９４０および９４５は、ネットワーク９５０に結合してもよい。クライアントシステム９１０、９２０および９３０は、一般に、図８における例示的なコンピューティングシステム８１０など、任意のタイプまたは形態のコンピューティング装置またはシステムを表す。一例において、クライアントシステム９１０には、図１のシステム１００を含んでもよい。
【００８３】
同様に、サーバ９４０および９４５は、一般に、様々なデータベースサービスを提供し、かつ／またはあるソフトウェアアプリケーションを実行するように構成された、アプリケーションサーバまたはデータベースサーバなどのコンピューティング装置またはシステムを表す。ネットワーク９５０は、一般に、例えば、イントラネット、ワイドエリアネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、パーソナルエリアネットワーク（ＰＡＮ）、またはインターネットを含む任意の電気通信またはコンピュータネットワークを表す。
【００８４】
図９に示すように、１つまたは複数の記憶装置９６０（１）−（Ｎ）は、サーバ９４０に直接装着してもよい。同様に、１つまたは複数の記憶装置９７０（１）−（Ｎ）は、サーバ９４５に直接装着してもよい。記憶装置９６０（１）−（Ｎ）および記憶装置９７０（１）−（Ｎ）は、一般に、データおよび／または他のコンピュータ可読命令を記憶できる任意のタイプまたは形態の記憶装置または媒体を表す。ある実施形態において、記憶装置９６０（１）−（Ｎ）および記憶装置９７０（１）−（Ｎ）は、ＮＦＳ、ＳＭＢまたはＣＩＦＳなどの様々なプロトコルを用いて、サーバ９４０および９４５と通信するように構成されたネットワーク接続ストレージ（ＮＡＳ）装置を表してもよい。
【００８５】
サーバ９４０および９４５はまた、ストレージエリアネットワーク（ＳＡＮ）ファブリック９８０に接続してもよい。ＳＡＮファブリック９８０は、一般に、複数の記憶装置間の通信を促進できる任意のタイプまたは形態のコンピュータネットワークまたはアーキテクチャを表す。ＳＡＮファブリック９８０は、サーバ９４０および９４５と、複数の記憶装置９９０（１）−（Ｎ）および／またはインテリジェントストレージアレイ９９５との間の通信を促進してもよい。ＳＡＮファブリック９８０はまた、装置９９０（１）−（Ｎ）およびアレイ９９５が、クライアントシステム９１０、９２０および９３０にローカルに装着された装置として現れるような方法で、ネットワーク９５０ならびにサーバ９４０および９５０を介して、クライアントシステム９１０、９２０および９３０と、記憶装置９９０（１）−（Ｎ）および／またはインテリジェントストレージアレイ９９５との間の通信を促進してもよい。記憶装置９６０（１）−（Ｎ）および記憶装置９７０（１）−（Ｎ）と同様に、記憶装置９９０（１）−（Ｎ）およびインテリジェントストレージアレイ９９５は、一般に、データおよび／または他のコンピュータ可読命令を記憶できる任意のタイプまたは形態の記憶装置または媒体を表す。
【００８６】
ある実施形態において、かつ図８の例示的なコンピューティングシステム８１０に関連して、図８における通信インターフェース８２２などの通信インターフェースを用いて、各クライアントシステム９１０、９２０および９３０とネットワーク９５０との間の接続を提供してもよい。クライアントシステム９１０、９２０および９３０は、例えばウェブブラウザまたは他のクライアントソフトウェアを用いて、サーバ９４０または９４５上の情報にアクセスすることができる。かかるソフトウェアによって、クライアントシステム９１０、９２０および９３０は、サーバ９４０、サーバ９４５、記憶装置９６０（１）−（Ｎ）、記憶装置９７０（１）−（Ｎ）、記憶装置９９０（１）−（Ｎ）、またはインテリジェントストレージアレイ９９５によりホストされる情報にアクセスすることが可能になる。図９は、データを交換するためにネットワーク（インターネットなど）を使用することを示すが、本明細書で説明および／または図示する実施形態は、インターネットにも、どんな特定のネットワークベースの環境にも限定されない。
【００８７】
少なくとも一実施形態において、本明細書で開示する例示的な実施形態の１つまたは複数における全てまたは一部は、コンピュータプログラムとしてコード化し、サーバ９４０、サーバ９４５、記憶装置９６０（１）−（Ｎ）、記憶装置９７０（１）−（Ｎ）、記憶装置９９０（１）−（Ｎ）、インテリジェントストレージアレイ９９５、またはそれらの任意の組み合わせにロードし、かつそれらによって実行してもよい。本明細書で開示する例示的な実施形態の１つまたは複数における全てまたは一部はまた、コンピュータプログラムとしてコード化し、サーバ９４０に記憶し、サーバ９４５によって実行し、かつネットワーク９５０を通じてクライアントシステム９１０、９２０および９３０に分散してもよい。したがって、ネットワークアーキテクチャ９００は、本明細書で開示する識別ステップ、監視ステップ、終了ステップ、追加ステップ、消去ステップ、削除ステップ、除去ステップ、判定ステップ、および／または検索ステップの１つまたは複数を、単独でまたは他の要素と一緒に実行するか、かつ／または実行するための手段であってもよい。ネットワークアーキテクチャ９００はまた、本開示で述べる他のステップおよび機能を実行するか、かつ／または実行するための手段となるように用いてもよい。
【００８８】
上記で詳述したように、コンピューティングシステム８１０および／またはネットワークアーキテクチャ９００の１つまたは複数のコンポーネントは、重複排除データシステムにおけるガーベジコレクション用の例示的な方法の１つまたは複数のステップを、単独でまたは他の要素と一緒に実行するか、かつ／または実行するための手段であってもよい。
【００８９】
前述の開示は、特定のブロック図、流れ図、および例を用いて様々な実施形態を説明したが、本明細書で説明および／または図示する各ブロック図の要素、流れ図のステップ、動作、および／またはコンポーネントは、広範囲なハードウェア、ソフトウェア、もしくはファームウェア（またはそれらの任意の組み合わせ）構成を用いて、個別に、かつ／または集団的に実現してもよい。さらに、他のコンポーネント内に含まれるコンポーネントのどんな開示もまた、本質的に例示的であると考えるべきである。なぜなら、同じ機能を達成するために他の多くのアーキテクチャを実現することができるからである。
【００９０】
本明細書で説明および／または図示するステップのプロセスパラメータおよびシーケンスは、例としてのみ与えられており、必要に応じて変更することができる。例えば、本明細書で図示および／または説明するステップは、特定の順序で図示または説明してもよいが、これらのステップは、必ずしも図示または説明される順序で実行する必要はない。本明細書で説明および／または図示する様々な例示的な方法はまた、本明細書で説明または図示するステップの１つもしくは複数を省略してもよく、または開示されるステップに加えて追加ステップを含んでもよい。
【００９１】
完全に機能的なコンピューティングシステムの文脈において、様々な実施形態を本明細書で説明および／または図示したが、これらの例示的な実施形態の１つまたは複数は、分散を実際に実行するために用いられる特定のタイプのコンピュータ可読媒体に関係なく、プログラムプロダクトとして様々な形態で分散してもよい。本明細書で開示する実施形態はまた、あるタスクを実行するソフトウェアモジュールを用いて実行してもよい。これらのソフトウェアモジュールには、コンピュータ可読記憶媒体またはコンピューティングシステムに記憶可能なスクリプト、バッチ、または他の実行可能ファイルを含んでもよい。いくつかの実施形態において、これらのソフトウェアモジュールは、本明細書で開示する例示的な実施形態の１つまたは複数を実行するようにコンピューティングシステムを構成してもよい。
【００９２】
さらに、本明細書で説明するモジュールの１つまたは複数は、データ、物理装置、および／または物理装置の表現を、ある形態から別の形態へと変形してもよい。例えば、本明細書で説明するモジュールの１つまたは複数は、コンピューティングシステムを重複排除データシステム用のガーベジコレクションのための効率的なシステムに変形してもよい。
【００９３】
前述の説明は、当業者が、本明細書で開示する例示的な実施形態の様々な態様を最も良く利用できるようにするために提供された。この例示的な説明は、網羅的であるようにも、開示されるいずれかの形態に正確に限定されるようにも意図されていない。多くの修正および変更が、本開示の趣旨および範囲から逸脱せずに可能である。本明細書で開示する実施形態は、全ての点において、実例であり限定ではないと考えるべきである。本開示の範囲を決定する際には、添付の特許請求の範囲およびその均等物を参照するべきである。
【００９４】
特に断りのない限り、明細書および特許請求の範囲において用いられるような用語「ａ」または「ａｎ」は、「〜の少なくとも１つ」を意味すると解釈するべきである。さらに、使い易さのために、明細書および特許請求の範囲において用いられるような単語「含む（ｉｎｃｌｕｄｉｎｇ）」および「有する（ｈａｖｉｎｇ）」は、単語「含む（ｃｏｍｐｒｉｓｉｎｇ）」と交換可能であり、かつそれと同じ意味を有する。
【図１】
2013522718.tif 000003
【図２】
2013522718.tif 000004
【図３】
2013522718.tif 000005
【図４】
2013522718.tif 000006
【図５】
2013522718.tif 000007
【図６】
2013522718.tif 000008
【図７】
2013522718.tif 000009
【図８】
2013522718.tif 000010
【図９】
2013522718.tif 000011
【手続補正書】
【提出日】平成24年9月13日(2012.9.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
重複排除データシステムにおけるガーベジコレクション用のコンピュータ実行方法であって、前記方法の少なくとも一部が、少なくとも１つのプロセッサを含むコンピューティング装置によって実行され、前記方法が、
重複排除データシステムを識別することと、
前記重複排除データシステムのガーベジコレクションプロセス中に前記重複排除データシステムに追加された少なくとも１つのセグメントオブジェクトを識別することと、
前記ガーベジコレクションプロセスによる前記セグメントオブジェクトの除去を防ぐために、前記セグメントオブジェクトをロックすることと、
前記ガーベジコレクションプロセス後に前記セグメントオブジェクトをロック解除することと、
を含む方法。
【請求項２】
前記セグメントオブジェクトをロックすることが、前記セグメントオブジェクトに対する参照を、ロックされたセグメントオブジェクトマップに追加することを含む、請求項１に記載のコンピュータ実行方法。
【請求項３】
前記ガーベジコレクションプロセス後に前記セグメントオブジェクトをロック解除することが、
前記ロックされたセグメントオブジェクトマップを消去することと、
前記ロックされたセグメントオブジェクトマップを削除することと、
前記セグメントオブジェクトに対する前記参照を、前記ロックされたセグメントオブジェクトマップから除去することと、
の少なくとも１つを含む、請求項２に記載のコンピュータ実行方法。
【請求項４】
前記重複排除データシステムに追加された前記セグメントオブジェクトを識別することが、
前記重複排除データシステム内における前記セグメントオブジェクトの生成を識別することと、
前記重複排除データシステム内における前記セグメントオブジェクトに対する新しい参照を識別することと、
の少なくとも１つを含む、請求項１に記載のコンピュータ実行方法。
【請求項５】
前記ガーベジコレクションプロセス前に前記重複排除データシステムに追加された追加セグメントオブジェクトを識別することと、
前記ガーベジコレクションプロセスの一部として、前記追加セグメントオブジェクトが前記重複排除データシステム内で参照されないと判定することと、
前記判定に基づいて前記追加セグメントオブジェクトを除去することと、
をさらに含む、請求項１に記載のコンピュータ実行方法。
【請求項６】
前記追加セグメントオブジェクトが追加された後で前記重複排除データシステムに追加されたデータオブジェクトを識別することと、
前記データオブジェクトが前記追加セグメントオブジェクトを参照すると判定することと、
前記追加セグメントオブジェクトの別のコピーを検索することと、
をさらに含む、請求項５に記載のコンピュータ実行方法。
【請求項７】
前記ガーベジコレクションプロセス中に前記重複排除データシステムに追加された前記セグメントオブジェクトを識別することが、ひとたび前記ガーベジコレクションプロセスが始まると、新しいデータセグメント用に前記重複排除データシステムを監視することを含む、請求項１に記載のコンピュータ実行方法。
【請求項８】
ひとたび前記ガーベジコレクションプロセスが完了すると、新しいデータセグメント用の、前記重複排除データシステムの前記監視を終了することをさらに含む、請求項７に記載のコンピュータ実行方法。
【請求項９】
前記ガーベジコレクションプロセス中に前記重複排除データシステムに追加された少なくとも１つのデータオブジェクトを識別することと、
前記ガーベジコレクションプロセスによる前記データオブジェクトの除去を防ぐために前記データオブジェクトをロックすることと、
前記ガーベジコレクションプロセス後に前記データオブジェクトをロック解除することと、
をさらに含む、請求項１に記載のコンピュータ実行方法。
【請求項１０】
重複排除データシステムにおけるガーベジコレクション用のシステムであって、
識別モジュールであって、
重複排除データシステムを識別するように、
前記重複排除データシステムのガーベジコレクションプロセス中に前記重複排除データシステムに追加された少なくとも１つのセグメントオブジェクトを識別するように、プログラムされた識別モジュールと、
前記ガーベジコレクションプロセスによる前記セグメントオブジェクトの除去を防ぐために、前記セグメントオブジェクトをロックするようにプログラムされたロッキングモジュールと、
前記ガーベジコレクションプロセス後に前記セグメントオブジェクトをロック解除するようにプログラムされたロック解除モジュールと、
前記識別モジュール、前記保存モジュール、前記供給モジュール、および前記削除モジュールを実行するように構成された少なくとも１つのプロセッサと、
を含むシステム。
【請求項１１】
前記ロッキングモジュールが、前記セグメントオブジェクトに対する参照を、ロックされたセグメントオブジェクトマップに追加することによって、前記セグメントオブジェクトをロックするようにプログラムされる、請求項１０に記載のシステム。
【請求項１２】
前記ロック解除モジュールが、
前記ロックされたセグメントオブジェクトマップを消去することと、
前記ロックされたセグメントオブジェクトマップを削除することと、
前記セグメントオブジェクトに対する前記参照を、前記ロックされたセグメントオブジェクトマップから除去することと、
の少なくとも１つによって、前記ガーベジコレクションプロセス後に前記セグメントオブジェクトをロック解除するようにプログラムされる、請求項１１に記載のシステム。
【請求項１３】
前記識別モジュールが、
前記重複排除データシステム内における前記セグメントオブジェクトの生成を識別することと、
前記重複排除データシステム内における前記セグメントオブジェクトに対する新しい参照を識別することと、
の少なくとも１つによって、前記重複排除データシステムに追加された前記セグメントオブジェクトを識別するようにプログラムされる、請求項１０に記載のシステム。
【請求項１４】
前記ガーベジコレクションプロセス前に前記重複排除データシステムに追加された追加セグメントオブジェクトを識別するように、
前記ガーベジコレクションプロセスの一部として、前記追加セグメントオブジェクトが前記重複排除データシステム内で参照されないと判定するように、
前記判定に基づいて前記追加セグメントオブジェクトを除去するように、
プログラムされたガーベジコレクションモジュールをさらに含む、請求項１０に記載のシステム。
【請求項１５】
前記追加セグメントオブジェクトが追加された後で前記重複排除データシステムに追加されたデータオブジェクトを識別するように、
前記データオブジェクトが前記追加セグメントオブジェクトを参照すると判定するように、
前記追加セグメントオブジェクトの別のコピーを検索するように、
プログラムされた回復モジュールをさらに含む、請求項１４に記載のシステム。
【国際調査報告】
2013522718.tif 000012
2013522718.tif 000013