(57)【要約】【課題】ファイルシステムによって使用される記憶領域内のライブデータを新しい記憶領域にコピー転送する手法を提供する。【解決手段】記憶領域は、記憶媒体内の永続性ストレージの範囲を指す。１つまたは複数のライブクランプ識別ワーカーが、ライブクランプリファレンスのセットを識別する。ライブクランプリファレンスは、ライブオブジェクトに属するライブクランプへの参照である。ライブクランプは、データの単位を表す。ライブクランプリファレンスのセットを識別した後、１つまたは複数のコンテナ識別ワーカーは、ライブクランプリファレンスのセットに対応するクランプを含む記憶領域のセットを識別する。ライブクランプリファレンスのセットに対応する記憶領域のセットを識別した後、複数のコピー転送タスクワーカーは、記憶領域のセットに対してコピー転送操作を実行して、ライブデータを新しい記憶領域にコピーする。【選択図】図１
2018073406.tif 000002
【特許請求の範囲】
【請求項１】
ファイルシステムによって使用される記憶領域に記憶されたライブクランプをコピー転送する方法において、
記憶領域識別フェーズ中に、複数のコンテナ識別ワーカーを実行して、ライブクランプリファレンスのセットに対応するクランプを含む記憶領域のセットを識別するステップであって、
前記ライブクランプリファレンスは、前記ファイルシステム内のライブオブジェクトに属するクランプへの参照であり、
前記複数のコンテナ識別ワーカーは、互いに独立して実行され、
各コンテナ識別ワーカーは、前記ライブクランプリファレンスのセットに対応するクランプを含む１つまたは複数の記憶領域を識別する、ステップと、
前記記憶領域識別フェーズの後に行われるコピー転送フェーズ中に、複数のコピー転送タスクワーカーを実行して、前記記憶領域のセットに対してコピー転送操作を実行するステップであって、
前記複数のコピー転送タスクワーカーは、互いに独立して実行され、
各コピー転送タスクワーカーは、前記記憶領域のセットから記憶領域のサブセットを割り当てられ、前記コピー転送タスクワーカーが割り当てられた前記記憶領域のサブセットに対してコピー転送操作を実行する、ステップと
を含むことを特徴とする方法。
【請求項２】
前記記憶領域識別フェーズの前に行われるライブクランプリファレンス識別フェーズ中に、１つまたは複数のライブクランプ識別ワーカーを実行して、ライブクランプリファレンスのセットを識別するステップをさらに含み、
前記１つまたは複数のライブクランプ識別ワーカーは、互いに独立して実行され、
前記１つまたは複数のライブクランプ識別ワーカーの各々は、前記ファイルシステム内のライブオブジェクトに属するクランプについての１つまたは複数のライブクランプリファレンスを識別すること
を特徴とする請求項１に記載の方法。
【請求項３】
前記ファイルシステム内の前記ライブオブジェクトに属する前記クランプは、前記コピー転送操作が実行される記憶領域を含む、記憶領域の候補セット内に記憶され、
前記記憶領域の候補セット内のクランプは、永続性ストレージにフラッシュされ、ライブクランプリファレンスのためのマッピングが前記ファイルシステム内のメタデータ内に生成されていること
を特徴とする請求項２に記載の方法。
【請求項４】
前記ライブクランプリファレンス識別フェーズの前に行われるライブオブジェクト識別フェーズ中に、ライブオブジェクトのセットを識別するために、１つまたは複数のライブオブジェクト識別ワーカーを実行するステップを含み、
前記１つまたは複数のライブオブジェクト識別ワーカーは、互いに独立して実行され、  前記１つまたは複数のライブオブジェクト識別ワーカーの各々は、前記ファイルシステムにおけるネームスペースメタデータに基づいて、前記ファイルシステム内の１つまたは複数のライブオブジェクトを識別すること
を特徴とする請求項３に記載の方法。
【請求項５】
前記記憶領域識別フェーズの後で前記コピー転送フェーズの前に行われる記憶領域スコアリングフェーズ中に、
前記記憶領域内のライブクランプの予想ライフタイム値、前記記憶領域内の前記ライブクランプの総数、または前記ライブクランプの総サイズのうち、少なくとも１つの記憶領域属性に基づいて、前記記憶領域のセット内の各記憶領域に優先度スコアを割り当てるために、複数の記憶領域スコアリングタスクワーカーを実行するステップを含み、
前記複数の記憶領域スコアリングタスクワーカーは、互いに独立して実行されること
を特徴とする請求項１に記載の方法。
【請求項６】
各コピー転送タスクワーカーによって実行される前記コピー転送操作は、
前記コピー転送タスクワーカーが割り当てられた前記記憶領域のサブセット内にある前記ライブクランプリファレンスのセット内のライブクランプリファレンスに対応する前記ライブクランプを、新しい記憶領域にコピーするステップと、
前記ライブクランプを前記新しい記憶領域にコピーするステップの完了時に、前記コピー転送タスクワーカーが割り当てられた前記記憶領域のサブセットを削除するステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記複数のコピー転送タスクワーカーの少なくとも２つが、並行して実行されること
を特徴とする請求項１に記載の方法。
【請求項８】
前記複数のコンテナ識別ワーカーの少なくとも２つが、並行して実行されること
を特徴とする請求項１に記載の方法。
【請求項９】
ファイルシステムによって使用される記憶領域に記憶されたライブクランプをコピー転送する方法において、
第１フェーズ中に、１つまたは複数の第１フェーズタスクワーカーは、
前記ファイルシステム内のライブオブジェクトを識別するステップと、
前記ライブオブジェクトの識別子に基づいて１つまたは複数の第２フェーズタスクワーカーに作業を配布するステップと
を実行し、
第２フェーズタスクワーカーは、
第１フェーズタスクワーカーによって識別されたライブオブジェクトのライブクランプリファレンスを識別するステップと、
前記ライブクランプリファレンスの値に基づいて１つまたは複数の第３フェーズタスクワーカーに作業を配布するステップと、
を実行し、
第３のフェーズタスクワーカーは、
第２のフェーズタスクワーカーによって識別された前記ライブクランプリファレンスに対応する記憶領域を決定するステップと、
前記ライブクランプリファレンスが属する前記記憶領域に基づいて、１つまたは複数のコピー転送タスクワーカーに作業を配布するステップと
を実行することを特徴とする方法。
【請求項１０】
前記ファイルシステム内の前記ライブオブジェクトを識別するステップは、さらに、
記憶領域の候補セットの一部である記憶領域間を、前記記憶領域の候補セットの一部ではない他の記憶領域から、線引きする候補セット境界を生成することによって、前記記憶領域の候補セットに属する記憶領域を決定するステップを含み、
前記記憶領域の候補セットは、前記ファイルシステム内の前記ライブオブジェクトに属する前記ライブクランプを含み、
前記候補セット境界は、依然として書き込み要求を受け取ることができる記憶領域の第１セットと、もはや書き込み要求を受け取らない記憶領域の第２セットとに、記憶領域を分割し、
前記記憶領域の第２セットは前記記憶領域の候補セットに属すること
を特徴とする請求項９に記載の方法。
【請求項１１】
前記記憶領域の前記候補セットは、永続性ストレージにフラッシュされたクランプを含み、前記ライブクランプリファレンスは、前記ファイルシステム内のメタデータ内で生成されていること
を特徴とする請求項１０に記載の方法。
【請求項１２】
前記ライブクランプリファレンスの値に基づいて前記第３フェーズタスクワーカーに作業を配布するステップは、前記第３のフェーズタスクワーカーの各第３のフェーズタスクワーカーに、ライブクランプリファレンスの連続した範囲内にあるライブクランプリファレンスのサブセットを割り当てるステップを含むこと
を特徴とする請求項９に記載の方法。
【請求項１３】
前記コピー転送タスクワーカーに作業を配布するステップは、
前記ライブクランプリファレンスと前記記憶領域との間の記憶領域対ライブクランプマッピングを生成するステップであって、
前記記憶領域対ライブクランプマッピングが前記記憶領域に基づいてソートされるように、前記記憶領域対ライブクランプマッピングが前記記憶領域を前記ライブクランプリファレンスにマップする、ステップと、
前記記憶領域に基づいて前記記憶領域対ライブクランプマッピングをソートするステップと、
前記記憶領域と前記記憶領域対ライブクランプマッピングに基づいて、前記コピー転送タスクワーカーに作業を配布するステップと
を含むことを特徴とする請求項９に記載の方法。
【請求項１４】
前記コピー転送タスクワーカーに作業を配布するステップは、さらに、各記憶領域に対して計算された優先度スコアに基づいており、
前記優先度スコアは、前記記憶領域内のライブクランプリファレンスの予想ライフタイム値、前記記憶領域内のライブクランプリファレンスの総数、および前記ライブクランプリファレンスの総サイズのうち、少なくとも１つの記憶領域属性に基づいていること
を特徴とする請求項１３に記載の方法。
【請求項１５】
ファイルシステムによって使用される記憶領域に記憶されたライブクランプをコピー転送するための命令を格納する非一時的なコンピュータ可読媒体において、１つまたは複数のプロセッサによって実行されると、
記憶領域識別フェーズ中に、複数のコンテナ識別ワーカーを実行して、ライブクランプリファレンスのセットに対応するクランプを含む記憶領域のセットを識別するステップであって、
前記ライブクランプリファレンスは、前記ファイルシステム内のライブオブジェクトに属するクランプへの参照であり、
前記複数のコンテナ識別ワーカーは、互いに独立して実行され、
各コンテナ識別ワーカーは、前記ライブクランプリファレンスのセットに対応するクランプを含む１つまたは複数の記憶領域を識別する、ステップと、
前記記憶領域識別フェーズの後に行われるコピー転送フェーズ中に、複数のコピー転送タスクワーカーを実行して、前記記憶領域のセットに対してコピー転送操作を実行するステップであって、
前記複数のコピー転送タスクワーカーは、互いに独立して実行され、
各コピー転送タスクワーカーは、前記記憶領域のセットから記憶領域のサブセットを割り当てられ、前記コピー転送タスクワーカーが割り当てられた前記記憶領域のサブセットに対してコピー転送操作を実行する、ステップと
を行う命令を含むことを特徴とするコンピュータ可読媒体。
【請求項１６】
１つまたは複数のプロセッサによって実行されると、
前記記憶領域識別フェーズの前に行われるライブクランプリファレンス識別フェーズ中に、１つまたは複数のライブクランプ識別ワーカーを実行して、ライブクランプリファレンスのセットを識別するステップを行う命令を更に含み、
前記１つまたは複数のライブクランプ識別ワーカーは、互いに独立して実行され、
前記１つまたは複数のライブクランプ識別ワーカーの各々は、前記ファイルシステム内のライブオブジェクトに属するクランプについての１つまたは複数のライブクランプリファレンスを識別すること
を特徴とする請求項１５に記載のコンピュータ可読媒体。
【請求項１７】
前記ファイルシステム内の前記ライブオブジェクトに属する前記クランプは、前記コピー転送操作が実行される記憶領域を含む、記憶領域の候補セット内に記憶され、
前記記憶領域の候補セット内のクランプは、永続性ストレージにフラッシュされ、ライブクランプリファレンスのためのマッピングが前記ファイルシステム内のメタデータ内に生成されていること
を特徴とする請求項１６に記載のコンピュータ可読媒体。
【請求項１８】
１つまたは複数のプロセッサによって実行されると、
前記ライブクランプリファレンス識別フェーズの前に行われるライブオブジェクト識別フェーズ中に、ライブオブジェクトのセットを識別するために、１つまたは複数のライブオブジェクト識別ワーカーを実行するステップを行う命令を更に含み、
前記１つまたは複数のライブオブジェクト識別ワーカーは、互いに独立して実行され、
前記１つまたは複数のライブオブジェクト識別ワーカーの各々は、前記ファイルシステムにおけるネームスペースメタデータに基づいて、前記ファイルシステム内の１つまたは複数のライブオブジェクトを識別すること
を特徴とする請求項１７に記載のコンピュータ可読媒体。
【請求項１９】
１つまたは複数のプロセッサによって実行されると、
前記記憶領域識別フェーズの後で前記コピー転送フェーズの前に行われる記憶領域スコアリングフェーズ中に、
前記記憶領域内のライブクランプの予想ライフタイム値、前記記憶領域内の前記ライブクランプの総数、および前記ライブクランプの総サイズのうち、少なくとも１つの記憶領域属性に基づいて、前記記憶領域のセット内の各記憶領域に優先度スコアを割り当てるために、複数の記憶領域スコアリングタスクワーカーを実行するステップを行う命令を更に含み、
前記複数の記憶領域スコアリングタスクワーカーは、互いに独立して実行されること
を特徴とする請求項１５に記載のコンピュータ可読媒体。
【請求項２０】
各コピー転送タスクワーカーによって実行される前記コピー転送操作は、
前記コピー転送タスクワーカーが割り当てられた前記記憶領域のサブセット内にある前記ライブクランプリファレンスのセット内のライブクランプリファレンスに対応する前記ライブクランプを、新しい記憶領域にコピーするステップと、
前記ライブクランプを前記新しい記憶領域にコピーするステップの完了時に、前記コピー転送タスクワーカーが割り当てられた前記記憶領域のサブセットを削除するステップと
を含むことを特徴とする請求項１５に記載のコンピュータ可読媒体。
【請求項２１】
前記複数のコピー転送タスクワーカーの少なくとも２つが、並行して実行されること
を特徴とする請求項１５に記載のコンピュータ可読媒体。
【請求項２２】
前記複数のコンテナ識別ワーカーの少なくとも２つが、並行して実行されること
を特徴とする請求項１５に記載のコンピュータ可読媒体。
【請求項２３】
ファイルシステムによって使用される記憶領域に記憶されたライブクランプをコピー転送するための命令を格納する非一時的なコンピュータ可読媒体において、１つまたは複数のプロセッサによって実行されると、
第１フェーズ中に、１つまたは複数の第１フェーズタスクワーカーは、
前記ファイルシステム内のライブオブジェクトを識別するステップと、
前記ライブオブジェクトの識別子に基づいて１つまたは複数の第２フェーズタスクワーカーに作業を配布するステップと
を実行し、
第２フェーズタスクワーカーは、
第１フェーズタスクワーカーによって識別されたライブオブジェクトのライブクランプリファレンスを識別するステップと、
前記ライブクランプリファレンスの値に基づいて１つまたは複数の第３フェーズタスクワーカーに作業を配布するステップと、
を実行し、
第３のフェーズタスクワーカーは、
第２のフェーズタスクワーカーによって識別された前記ライブクランプリファレンスに対応する記憶領域を決定するステップと、
前記ライブクランプリファレンスが属する前記記憶領域に基づいて、１つまたは複数のコピー転送タスクワーカーに作業を配布するステップと
を行う命令を含むことを特徴とするコンピュータ可読媒体。
【請求項２４】
前記ファイルシステム内の前記ライブオブジェクトを識別するステップは、さらに、
記憶領域の候補セットの一部である記憶領域間を、前記記憶領域の候補セットの一部ではない他の記憶領域から、線引きする候補セット境界を生成することによって、前記記憶領域の候補セットに属する記憶領域を決定するステップを含み、
前記記憶領域の候補セットは、前記ファイルシステム内の前記ライブオブジェクトに属する前記ライブクランプを含み、
前記候補セット境界は、依然として書き込み要求を受け取ることができる記憶領域の第１セットと、もはや書き込み要求を受け取らない記憶領域の第２セットとに、記憶領域を分割し、
前記記憶領域の第２セットは前記記憶領域の候補セットに属すること
を特徴とする請求項２３に記載のコンピュータ可読媒体。
【請求項２５】
前記記憶領域の前記候補セットは、永続性ストレージにフラッシュされたクランプを含み、前記ライブクランプリファレンスは、前記ファイルシステム内のメタデータ内で生成されていること
を特徴とする請求項２４に記載のコンピュータ可読媒体。
【請求項２６】
前記ライブクランプリファレンスの値に基づいて前記第３フェーズタスクワーカーに作業を配布するステップは、前記第３のフェーズタスクワーカーの各第３のフェーズタスクワーカーに、ライブクランプリファレンスの連続した範囲内にあるライブクランプリファレンスのサブセットを割り当てるステップを含むこと
を特徴とする請求項２３に記載のコンピュータ可読媒体。
【請求項２７】
前記コピー転送タスクワーカーに作業を配布するステップは、
前記ライブクランプリファレンスと前記記憶領域との間の記憶領域対ライブクランプマッピングを生成するステップであって、
前記記憶領域対ライブクランプマッピングが前記記憶領域に基づいてソートされるように、前記記憶領域対ライブクランプマッピングが前記記憶領域を前記ライブクランプリファレンスにマップする、ステップと、
前記記憶領域に基づいて前記記憶領域対ライブクランプマッピングをソートするステップと、
前記記憶領域と前記記憶領域対ライブクランプマッピングに基づいて、前記コピー転送タスクワーカーに作業を配布するステップと
を特徴とする請求項２３に記載のコンピュータ可読媒体。
【請求項２８】
前記コピー転送タスクワーカーに作業を配布するステップは、さらに、各記憶領域に対して計算された優先度スコアに基づいており、
前記優先度スコアは、前記記憶領域内のライブクランプリファレンスの予想ライフタイム値、前記記憶領域内のライブクランプリファレンスの総数、または前記ライブクランプリファレンスの総サイズのうち、少なくとも１つの記憶領域属性に基づいていること
を特徴とする請求項２７に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、もう使用されていないデータによって占有される記憶空間（スペース）を再利用することに関する。
【背景技術】
【０００２】
電子ファイルシステムは、ファイルおよびファイルメタデータなどの様々なタイプのオブジェクトをメモリの「クランプ（clump）」に格納する。本明細書で使用される「クランプ」は、連続したメモリの任意の範囲である。例えば、永続性ストレージ装置において、クランプは、物理的または論理的に連続したディスクブロックのセットを含むことができる。オブジェクトが永続性ストレージに最初に格納されると、ファイル管理システムは、オブジェクトを構成するデータを永続性ストレージ内の特定のクランプに書き込み、データオブジェクトのメタデータを生成する。メタデータは、例えば、オブジェクトのオブジェクト識別子を、オブジェクトのデータを格納する１つ以上のクランプに割り当てる（マップする）ことができる。例えば、オブジェクトfile1.txtがクランプ ａ、ｂ及ｃ に格納されている場合、file1.txtのメタデータには、file1.txtのオブジェクト識別子をクランプ ａ、ｂ、及びｃ にマップするマッピング情報が含まれる。オブジェクト識別子をクランプにマッピングするメタデータは、本明細書では、オブジェクト対クランプマッピング（object-to-clump mapping）情報と呼ぶ。
【０００３】
いくつかのシステムでは、単一のクランプを複数のオブジェクトにマッピングすることができる。これは、例えば、ファイル管理システムが重複排除技術を実装している場合に発生し得る。重複排除は、データの重複コピーを排除するための圧縮技術である。例えば、file1.txtの一部がfile2.txtの一部と同じであるとする。このような状況下では、その同一部分のデータは単一のクランプに格納され、file1.txtとfile2.txtの両方のオブジェクト対クランプマッピングが同じクランプになることがある。ファイル管理システムは、オブジェクトからクランプへの多対１の関係を可能にすることにより、同じデータの複製コピーを格納する必要性を低減する。しかしながら、同時に、オブジェクトからクランプへの多対一の関係は、記憶領域再利用（storage reclamation）のプロセスを複雑にする。具体的には、file1.txtを削除すると、file1.txtで使用されたクランプは、それらのクランプのうち１つ又は複数を別の活きているオブジェクトによって指し示されている可能性があるため、必ず再利用できるとは限らない。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】https://en.wikipedia.org/wiki/Tracing_garbage_collection
【発明の概要】
【発明が解決しようとする課題】
【０００５】
格納されたオブジェクトにアクセスするとき、ファイル管理システムは、どのクランプが特定のオブジェクトに属するかを決定するためにオブジェクト対クランプマッピングを参照する。所望のクランプが識別されると、ファイル管理システムは、永続性ストレージからクランプにアクセスする。オブジェクトを削除および/または更新する場合、ファイル管理システムは、オブジェクトと、該オブジェクトのデータを含む１つ以上のクランプとの間のオブジェクト対クランプマッピングを削除するが、それらのクランプは再利用しない。その結果、オブジェクトにマップされたクランプは、そのオブジェクトのオブジェクト識別子を介して、アプリケーションによってもはや到達可能ではない。しかしながら、オブジェクト識別子とクランプとの一対多のマッピングをサポートしているシステムでは、他のオブジェクトのオブジェクト識別子を通じて、それら同じクランプに到達することができる。これらクランプを再利用せずにオブジェクト対クランプマッピングだけを削除する手法は、オブジェクト対クランプマッピングを削除することが単に必要があるという点で効率的である。しかしながら、もはや使用されていないクランプは、新しいデータに使用されるように、最終的に再利用されなければならない。
【０００６】
ファイルシステムのオブジェクトが更新され、削除されると、ファイルシステムは、いかなるソフトウェアアプリケーションによってもはや使用されないデータ（本明細書では「デッドデータ」と呼ぶ）を含むクランプを蓄積する。デッドデータを含むクランプは、本明細書では「デッドクランプ」と呼ぶ。例えば、オブジェクトＯが最初にクランプＡ、Ｂ及びＣに格納されていると仮定する。オブジェクトＯが更新されると、オブジェクトＯの更新されたバージョンは、クランプＸ、Ｙ、Ｚに書き出される。更新に応じて、オブジェクトＯをクランプＡ、Ｂ、Ｃにマッピングするメタデータが削除され、オブジェクトＯをクランプＸ、Ｙ、Ｚにマッピングするメタデータが作成される。クランプＡ、Ｂ、Ｃに他のオブジェクトがマッピングされていないと仮定すると、クランプＡ、Ｂ、Ｃは更新後にデット（死んでいる）状態となる。つまり、クランプＡ、Ｂ、Ｃのデータは、ソフトウェアアプリケーションによってもはや使用されなくなる。効果的なストレージ管理では、デッドクランプを再利用して、新しい「ライブ」（活きている）データを格納するために再利用できるようにする必要がある。
【０００７】
デッドクランプを再利用するための１つの技術は、マークアンドスイープ（mark-and-sweep）アプローチと呼ばれる。マークアンドスイープアプローチの例は、en.wikipedia.org/wiki/Tracing_garbage_collection（非特許文献１）に記載されており、その内容は、参照により本明細書に組み込まれる。マークアンドスイープアプローチは、（ａ）ソフトウェアエンティティによって現在「ライブ」または「到達可能」であるオブジェクトを識別すること、（ｂ）それらのオブジェクトのデータを「ライブ」として格納するクランプをマーキングすること、そして（ｃ）「ライブ」とマークされていないすべてのクランプを解放することを含む。
【課題を解決するための手段】
【０００８】
いくつかの実施形態では、記憶領域断片化を低減するために、論理的または物理的に連続した記憶領域内のライブ（活きている）クランプを異なる位置に移動し、連続記憶領域全体を再利用可能にする。一領域のライブクランプを別の場所に移動するプロセスは、コピー転送（copy-forward）操作と呼ばれる。
【０００９】
上述したように、マークアンドスイープ手法の第１のステップは、オブジェクト対クランプマッピングメタデータ内にクランプへの参照が存在するかどうかに基づいてライブクランプを識別することを含む。ライブクランプを特定するアプローチには、オブジェクト間のマッピングのリスト全体をスキャンし、オブジェクト対クランプマッピング内のすべてのクランプをマーキングすることが含まれる。マーキングには、ライブクランプのリストを生成するか、クランプそのものの中にマークされた属性を設定することが含まれる。コピー転送操作の間、再利用（reclamation）プロセスは、永続性ストレージの領域内に格納されているすべてのクランプを処理し、クランプがライブとしてマークされている場合、クランプは、永続性ストレージの新しい領域にコピーされる。領域内のすべてのクランプが辿られると、すべてのライブクランプが既にコピーされているため、領域が再割り当てされる。
【００１０】
残念ながら、マークアンドスイープアプローチは、特にコピー転送操作と組み合わされた場合、かなりの計算量、及び、かなりのメモリリソースを消費する可能性がある。例えば、オブジェクト対クランプマッピングが比較的大きい場合、ライブクランプのオブジェクト対クランプマッピングをスキャンすると、完了するまでにかなりの時間がかかることがある。ストレージシステムが大規模になると、このアプローチは完了するまでにますます時間がかかり、非効率的になる。したがって、ライブクランプを判定し、ライブクランプを永続性ストレージの新しい領域に転送する効率的なアプローチが望まれる。
【００１１】
このセクションに記載されたアプローチは、達成され得るアプローチであるが、必ずしもこれまでに考え出されたまたは達成されたアプローチではない。したがって、特に明記しない限り、このセクションで説明されているアプローチのいずれかが、単にこのセクションに含まれているために、単に先行技術と見なされるものと仮定すべきではない。
【図面の簡単な説明】
【００１２】
【図１】図１は、ストレージプール内のストレージスペースを再利用するためのデータ管理サービスを含む分散ストレージシステムの実施形態を示す。
【図２】図２は、記憶空間再利用ジョブの複数のフェーズ中のジョブコントローラとタスクワーカーとの間の対話の実施形態を示す。
【図３】図３は、ストレージプール内のデータログのセットからコンテナの候補セットを生成する例を示す。
【図４】図４は、ライブオブジェクトのサブセットからクランプフィンガープリントを識別するタスクワーカーの例示的な実施形態を示す。
【図５】図５は、ジョブコントローラが、タスクワーカーにクランプフィンガープリントのパーティションを委任し、次にタスクワーカーがクランプフィンガープリントのコンテナ識別子を決定する例示的な実施形態を示す。
【図６】図６は、ジョブコントローラが、コンテナ識別子に基づくクランプフィンガープリントのセットをタスクワーカーに委任し、次にタスクワーカーがコンテナの記憶空間再利用スコアを計算する例示的な実施形態を示す。
【図７】図７は、ジョブコントローラがコピー転送操作をタスクワーカーに委任する例示的な実施形態を示す。
【図８】図８は、分散仮想アレイ（ＤＶＡ）システムの実施形態を示す。
【図９】図９は、ＤＶＡ内のコンポーネントを選択することの詳細な実施形態を示す。
【図１０】図１０は、書込み要求の受信時のワークフローの実施形態を示す。
【図１１】図１１は、読み取り要求を受信したときのワークフローの実施形態を示す。
【図１２】図１２は、本明細書に記載の技術を実施するために使用され得るコンピュータシステムを例示するブロック図を示す。
【発明を実施するための形態】
【００１３】
詳細な説明
以下の説明では、説明の目的のために、本発明の完全な理解を提供するために、多数の具体的な詳細が述べられている。しかしながら、本発明は、これらの具体的な詳細がなくても実施できることは明らかであろう。他の例では、本発明を不必要に不明瞭にすることを避けるために、周知の構造および装置は、ブロック図形式で示されている。
【００１４】
総括
並列化されたマークアンドスイープおよびコピー転送操作を使用して記憶領域再利用を実行する技術が本明細書に記載されている。１つの実施形態によれば、記憶領域再利用は一連のフェーズで実行され、それぞれのフェーズは特定の１つの作業に対応する。各フェーズでは、対応する作業が独立したタスクに分割され、タスクは利用可能なタスクワーカーに配布される。フェーズ内の各タスクはフェーズ内の他のタスクと独立しているため、任意のフェーズに属するタスクを実行するためにタスクワーカー間の調整は必要ない。フェーズ内の各タスクはフェーズ内の他のタスクとは独立しているため、複数のタスクワーカーが利用可能な場合は、任意のフェーズに属するタスクを並行して実行することができるため、スペースの再利用は、逐次的な再利用操作よりも大幅に高速に実行することができる。
【００１５】
構造の概要
分散ストレージシステムは、典型的には、これに限定されるものではないが、１つまたは複数のストレージノードおよびストレージプールマネージャを含むストレージ（記憶領域）プールを含む。図１は、ストレージプール１３０内のストレージスペースを再利用するためのデータ管理サービスを含む分散ストレージシステムの例示的な実施形態を示す。図１に示す実施形態では、ストレージプール１３０は、ストレージノード１０１０−１,１０１０−２、．．．、１０１０−Ｎを含む。 ストレージノード１０１０−１,１０１０−２、．．．、１０１０−Ｎは、ストレージ装置１０４０−１,１０４０−２、．．．、１０４０−Ｎを含む。
【００１６】
ファイルシステム１１５は、データがストレージプール１３０内でどのように編成されるかを管理する。例えば、ファイルシステム１１５は、ストレージプール１３０内のログ構造（log-structured）ファイルシステムとしてデータを編成することができる。ログ構造ファイルシステムは、データが１つ以上のデータログに順次書き込まれるファイルシステムである。各データログは、本明細書ではコンテナと呼ばれる特定の記憶領域を含むことができる。
【００１７】
コンテナは、コンテナの構成されたサイズに基づいて複数のクランプを格納することができる。再び図１を参照すると、吹き出し１３５は、ストレージプール１３０内に格納されたデータログを示す。他の実施形態では、ファイルシステム１１５は、ストレージプール１３０上の異なるファイル構造を使用してデータを編成することができる。ファイルシステムの構造、ストレージプール、およびホストと仮想マシン間のデータの読み取り、書き込み、および更新を行う相互接続の実装の詳細な説明は、本明細書の「分散仮想アレイ」のセクションで説明する。
【００１８】
ファイルシステム１１５は、ネームスペース１２０、ファイルマネージャ１２２、およびフィンガープリントインデックス１２５を使用して、ストレージプール１３０へのデータの読み書きを管理する。ネームスペース１２０は、ファイルシステムに格納されたオブジェクトを追跡するために実装される。ファイルマネージャ１２２は、オブジェクトおよびそれらに関連するクランプを編成するように実装される。一実施形態では、ネームスペース１２０は、オブジェクト名からオブジェクトへのマッピングを含むメタデータを含み、ファイルマネージャ１２２は、どのクランプがどのオブジェクトに関連しているかを識別するために使用されるオブジェクト対クランプマッピングを含むメタデータを含む。クランプリファレンス（参照）は、特定のコンテナ内の特定のクランプに対する一意の識別子である。クランプリファレンスの実施形態には、これに限定されるものではないが、永続性ストレージ内の特定のメモリ位置へのポインタ、または永続性ストレージ内のマッピング済みメモリアドレスをルックアップするために使用される主キーが含まれる。一実施形態では、フィンガープリントインデックス１２５は、特定のコンテナ内の特定の位置にクランプリファレンスをマッピングするために使用されるクランプリファレンス対コンテナ識別子マッピングを含む。一実施形態では、クランプリファレンスは、クランプフィンガープリントと呼ばれる固有のデータフィンガープリント値を使用して表すことができる。クランプフィンガープリントは、特定のクランプを一意的に識別する各クランプに関連する識別子である。一実施形態では、クランプフィンガープリントは、クランプにおけるデータの暗号ハッシュに基づいて計算される。
【００１９】
特定のオブジェクトに対するクランプを読み出し、書き出し、および/または更新するとき、ファイルシステム１１５は、ファイルマネージャ１２２にアクセスして、特定のオブジェクトにマッピングされたクランプフィンガープリントを決定し、そして、クランプフィンガープリントインデックス１２５にアクセスして、クランプフィンガープリントに基づいて、ストレージプール１３０に格納されたデータログ内のクランプの位置を決定する。
【００２０】
ジョブコントローラ
一実施形態では、記憶空間再利用（space reclamation）は、ライブクランプをデータログ内に作成された新しいコンテナに移動することによって、既存のコンテナから記憶領域の空き領域を再利用する記憶空間再利用ジョブを使用して実行することができる。ジョブコントローラ１０５は、記憶空間再利用操作を調整および管理するように構成されたコンポーネントを表す。一実施形態では、ジョブコントローラ１０５は、ストレージプール１３０に通信可能に接続されたサーバ上に実装されてもよい。別の実施形態では、ジョブコントローラ１０５は、ストレージプール１３０内の１つまたは複数のストレージデバイスを管理するように構成されたストレージノード上で動作するソフトウェアとして実装されてもよい。ジョブコントローラ１０５は、ストレージプール１３０内のストレージノード内のクランプの記憶領域を再編成することを管理する。ジョブコントローラ１０５は、ファイルシステム１１５およびストレージプール１３０と通信して、いつ記憶空間再利用ジョブを開始するかを決定し、記憶空間再利用の対象となるべきコンテナを決定することができる。
【００２１】
一実施形態では、ジョブコントローラ１０５は、記憶空間再利用ジョブの異なるフェーズをタスクワーカー１１０に委任する。例えば、記憶空間再利用ジョブを開始する必要があると判断した後で、ジョブコントローラ１０５は、記憶空間再利用ジョブの各フェーズに対するタスクをタスクワーカー１１０に割り当てることができる。タスクワーカーは、記憶空間再利用ジョブに関連するタスクを実行するように構成されたプロセスまたはスレッドを表すことができる。一実施形態では、タスクワーカー１１０は、並列に実行され、ストレージプール１３０内の特定のストレージノードに実装されるプロセスまたはスレッドを表すことができる。一実施形態では、特定のストレージノードに配置されたタスクワーカー１１０は、それら対応するストレージノード内に格納されたクランプに関するタスクを受け取る。
【００２２】
別の実施形態では、タスクワーカー１１０は、プールマネージャ１０５０上に実装されたプロセスまたはスレッドを表すことができる。この場合、タスクワーカー１１０にタスクが割り当てられると、タスクワーカー１１０は、割り当てられた各タスクに関連付けられた特定のストレージノードへの接続を確立する。さらに別の実施形態では、タスクワーカー１１０は、ファイルシステム１１５への読み書きを要求するアプリケーションをホストするホストデバイス上に実装されたプロセスまたはスレッドを表すことができる。他の実施形態では、タスクワーカー１１０は、複数の場所に実装されたプロセスまたはスレッドを表すことができ、ジョブコントローラ１０５は、タスクワーカー１１０にタスクを割り当て、ローカルおよび/またはリモートストレージノードに通信することによってタスクを実行する。
【００２３】
一実施形態では、記憶空間再利用ジョブの特定のフェーズに関連するすべてのタスクが完了すると、ジョブコントローラ１０５は、記憶空間再利用ジョブの次のフェーズに関連する新しいタスクを、別の一連の利用可能なタスクワーカー１１０に分配する。各フェーズのタスクを分配するプロセスは、すべてのフェーズが完了するまでジョブコントローラ１０５によって管理される。記憶空間再利用ジョブの各フェーズのためのタスクの分配技術およびタスクワーカー１１０の管理は、以下でより詳細に論じられる。
【００２４】
ジョブコントローラ１０５は、いつ記憶空間再利用ジョブをスケジュールするか、
利用可能なタスクワーカー１１０に委任するためにデータを複数のタスクにどのように分割するかを決定するように構成され、タスクワーカー１１０のステータス（状態）を管理して、どのタスクワーカー１１０が特定のタスクに利用可能であるかを決定することができる。
【００２５】
一実施形態では、ジョブコントローラ１０５は、ストレージプール１３０内の現在利用可能な記憶空間に基づいて記憶空間再利用ジョブを開始することを決定することができる。例えば、利用可能な記憶空間が設定されたしきい値を下回った場合に、設定された使用しきい値（usage threshold）を用いて、記憶空間再利用ジョブをトリガーすることができる。別の例では、記憶空間予測しきい値（space prediction threshold）を用いてもよく、ここで、記憶空間予測しきい値は、利用可能な記憶空間が使用される前に残っている予測残量を計算する。次に、記憶空間が使用される前に予測された時間残量に基づいて、１つまたは複数のストレージプール内の記憶空間のすべてを利用する前に、記憶空間再利用ジョブがトリガーされるか、または実行されるようにスケジューリングされ得る。別の実施形態では、ジョブコントローラ１０５は、設定された記憶空間再利用スケジュールに基づいて記憶空間再利用ジョブを開始することを決定することができる。例えば、記憶空間再利用ジョブは、時間別、日別、週別、またはその他の指定された時間に実行するようにスケジュールされている場合がある。
【００２６】
一実施形態では、ジョブコントローラ１０５は、タスクワーカー１１０の総数およびタスクワーカー１１０の現在のステータスを記録するように構成される。例えば、ジョブコントローラ１０５は、現在のステータスを判定し、利用可能なタスクワーカー１１０の現在の数を決定するために、利用可能なタスクワーカー１１０に接続の疎通確認（ping）を行うことができる。例えば、ジョブコントローラ１０５が、クランプフィンガープリントのリストを、２０のパーティションに分割した場合、ジョブコントローラ１０５は、タスクワーカー１１０に対して接続の疎通確認を実行して、クランプフィンガープリントのリストに対するコンテナを決定するタスクを割り当てられるタスクワーカー１１０の数を決定する。タスクワーカー１１０に対して接続の疎通確認をした後、ジョブコントローラ１０５は、１０個のタスクワーカー１１０しか利用できないと判断した場合、２０個の分割タスクのうち１０個の分割タスクをタスクワーカー１１０に割り当てることができる。一実施形態では、ジョブコントローラ１０５は、特定のタスクワーカーがまだ活きていることを保証するために、タスクを割り当てられた特定のタスクワーカーに対して定期的に疎通確認（ping）行うこともできる。特定のタスクワーカーが応答しない場合、ジョブコントローラ１０５は、特定のタスクワーカーが活きていないと結論付け、そのタスクを次の利用可能なタスクワーカー１１０に再割り当てすることができる。
【００２７】
一実施形態では、ジョブコントローラ１０５は、特定のタスクと共に、ソース命令、分割（パーティショニング）命令および宛先（destination）命令をタスクワーカー１１０に送信するように構成される。ソース命令は、特定のタスクを実行するために使用される入力を指定する命令を参照する。分割命令は、特定のタスクの結果をどのように分割するかを指定する命令を参照する。例えば、特定のタスクの結果が活きているクランプフィンガープリントを含む場合、分割命令は、範囲ベースのクランプフィンガープリント分割命令を指定することができる。宛先命令は、特定のタスクの結果の宛先を指定する命令を参照する。例えば、ジョブコントローラ１０５が、一組のクランプフィンガープリントに対するコンテナ識別子を決定するタスクを委任し、ストレージプール１３０内の宛先位置を含む宛先命令を指定する場合、特定のタスクワーカーは、タスクを完了した後、タスクからの出力をストレージプール１３０内の指定された宛先位置に送信する。一実施形態では、分割および宛先命令は、他のタスクワーカー１１０を指定することもできる。例えば、分割および宛先命令は、特定のタスクワーカーが、終了時に、記憶空間再利用ジョブにおける次のフェーズを開始するように指定されたタスクワーカー１１０の別のセットに出力を送信することを指定することができる。
【００２８】
機能概要
ここでは、記憶空間を再利用する操作（オペレーション）が複数の段階に分割される技術が説明される。各フェーズでは、フェーズに関連する作業が独立したタスクに分割される。各フェーズのタスクは、同じフェーズの他のタスクの進捗状況に関係なく、任意のフェーズの任意のタスクが実行され得るという点で独立している。
【００２９】
第１フェーズの前に、第１フェーズのタスクを確立しなければならない。一実施形態では、第１フェーズのタスクを確立することは、候補セットを確立することを含み、オブジェクトメタデータを同期させて永続化させ、そのオブジェクトメタデータをパーティションに分割し、それらのパーティションをタスクに割り当てることを含む。これらの操作のそれぞれについて、以下でさらに詳細に説明する。一実施形態では、候補セットを確立することは、記憶空間を再利用する操作の第１フェーズである。
【００３０】
「候補セット」を設定すること
ファイルシステムは、記憶領域再利用操作の間に使用中のままであり得るので、ライブクランプ及びデッドクランプは、記憶領域再利用操作中にファイルシステムによって連続的に作成されることがある。したがって、クランプが活きているのか死んでいるのか（ライブクランプであるかデッドクランプであるか）を判断することは複雑な作業である。一実施形態によれば、マークアンドスイープ操作が始まる前に、ジョブコントローラ１０５は、まず、記憶領域再利用操作に関与するコンテナに制限を加える。再利用操作に関与するように選択されたコンテナは、本明細書では、再利用操作の「候補セット」と呼ばれる。
【００３１】
一実施形態では、ジョブコントローラ１０５は、候補セットに対して、「安定化された（stabilized）」コンテナのみを選択する。安定化されたコンテナは、もはや書き込みプロセスによって使用されなくなったコンテナである。例えば、一実施形態では、各書き込みプロセスには異なる「ライターＩＤ」が割り当てられ、そのライターＩＤに関連付けられたログにのみ書き込む。したがって、任意のログ内の一連のコンテナは、ログのライターＩＤが割り当てられた１つの書き込みプロセスによってのみ書き込まれる。任意のログに属するコンテナを安定化させるには、そのログを使用している書き込みプロセスに新しいライターＩＤが割り当てられる。書き込みプロセスには新しいライターＩＤが割り当てられているため、書き込みプロセスは新しいログに書き込みを開始する。新しいライターＩＤが割り当てられた後、書き込みプロセスは、既にライターＩＤに関連付けられた一連のコンテナに書き込みを行うことはない。その結果、以前のライターＩＤに関連付けられたコンテナが安定化される。
【００３２】
一実施形態では、コンテナの候補セットを決定することは、複数のログの書き込みプロセスに新しいライターＩＤを割り当てることを含み、それにより、それらのログのそれぞれについて候補セット境界を確立することを含む。候補セット境界は、コンテナの候補セットの一部であるコンテナとコンテナの候補セットの一部ではないコンテナとの間の輪郭を線引きするために使用される。図３は、ストレージプール内のデータログの例示的なセットと、どのコンテナがコンテナの候補セットの一部であるかを識別するために使用される生成された候補セット境界とを示す。データログ３０１〜３０４は、それぞれ固有のデータログを表す。データログ３０１〜３０４の各々は、データログ内に四角で示されたデータのコンテナを含む。データログ３０１〜３０４に対応する書き込みプロセスの各々には、新しいライターＩＤが割り当てられ、データログ３０５〜３０８に書き込みを開始する。候補セット境界３１０は、安定化されたコンテナと書き込み要求および/または更新要求を依然として受信しているコンテナとの間を線引きするために使用される仮想境界線である。候補セット境界３１０の位置は、新しいライターＩＤが対応する書き込みプロセスに割り当てられる前に、データログ３０１〜３０４内のいくつのコンテナが書き込まれているかに応じて、データログ３０１〜３０４のそれぞれの間で変化してもよい。
【００３３】
一実施形態では、ジョブコントローラ１０５はファイルシステム１１５と通信して、新しいライターＩＤをファイルシステム書き込みプロセスに順次割り当てる。候補セット境界３１０は、書き込みプロセスの中で最大の以前のライターＩＤに基づいて生成され、どのコンテナがコンテナの候補セットを構成するかを決定するために使用される。図３を再び参照すると、候補セット３５０は、コンテナの候補セットを表す。候補セット３５０は、データログ３０１〜３０４からの安定化されたコンテナであるコンテナセット３２０〜３３５を含む。セット３４０内のコンテナは、依然としてアクティブな更新を受信している残りのコンテナである。
【００３４】
別の実施形態では、容器を安定化するために他の技術を使用することができる。例えば、書き込みプロセスに新しいライターＩＤを割り当てる（それによって、新しいログを開始させる）代わりに、ジョブコントローラ１０５は、特定のコンテナ内のデータに対する書き込みおよび/または更新要求を中断するようにファイルシステム１１５に要求することによって、コンテナの安定化を保証することができる。ジョブコントローラ１０５はまた、ファイルシステム１１５にデータログ３０１〜３０５のそれぞれの中のどのコンテナが安定化されているかを判断するように要求することによって、コンテナの安定化を保証してもよい。したがって、本明細書に記載の技術は、コンテナを安定化するための特定のアプローチに限定されない。
【００３５】
メタデータのフラッシュ
候補セットが確立された後、ジョブコントローラ１０５は、候補セットにおけるクランプを含むすべてのオブジェクトについて、ファイルシステムがオブジェクトのメタデータの生成を終了し、メタデータを永続性ストレージにフラッシュする（書き込む）ことを保証する。ファイルシステムがこれらのオブジェクトに必要なすべてのオブジェクトメタデータを生成するようにし、そのメタデータを永続性ストレージにフラッシュするために、（ａ）候補セット内にライブクランプを有するが、（ｂ）永続性ファイルシステムのメタデータで識別されない、オブジェクトがないことを保証する。
【００３６】
ライブ（活きている）オブジェクトの識別
上で説明したように、本明細書に記載された技術を使用して、マークアンドスイープおよびコピー転送記憶空間再利用に含まれる作業は、多くの段階で実行される。必要なファイルシステムメタデータがディスクにフラッシュされた後、最初のフェーズが開始される。図２は、記憶空間再利用ジョブの複数のフェーズを示す。図示された実施形態によれば、第１フェーズ２０５は、ライブオブジェクトを識別することを含む。
【００３７】
具体的には、フェーズ２０５は、コンテナの候補セット内にクランプを含むライブオブジェクトを識別することを含む。これらのオブジェクトは、ファイルシステムによってディスクにフラッシュされたメタデータから識別される。具体的には、一実施形態では、ジョブコントローラ１０５は、ファイルシステムメタデータを分割し、メタデータのパーティション（分割された各部分）を各ライブオブジェクト識別ワーカー２３０に割り当てる。したがって、ライブオブジェクト識別ワーカー２３０に割り当てられた各タスクは、ファイルシステムのメタデータの特定の部分に反映されるライブオブジェクトを識別することを含む。
【００３８】
メタデータが分割されるパーティションの数は、ライブオブジェクト識別ワーカー２３０の数よりも多くてもよい。そのような場合には、ジョブコントローラ１０５は、最初に各タスクワーカーに１つのパーティションに関連するタスクを割り当てることができる。各タスクワーカーが最初に割り当てられたパーティションの処理を終了すると、ジョブコントローラ１０５はタスクワーカーに別のパーティションに関連するタスクを割り当てることができる。このプロセスは、関連するメタデータのすべてのパーティションが、ライブオブジェクト識別ワーカーのうちの１つによって処理されるまで継続することができる。
【００３９】
ジョブコントローラ１０５によってライブオブジェクト識別ワーカー２３０に委任される各タスクは、他のライブオブジェクト識別ワーカー２３０によって実行されている他のタスクからの入力または通信を必要としない、独立して実行可能な作業である。ライブオブジェクト識別ワーカー２３０のそれぞれは、ファイルシステム１１５、ネームスペース１２０、およびストレージプール１３０と通信して、ライブオブジェクトのリストを決定することができる。一実施形態では、ライブオブジェクト識別ワーカー２３０のセット内の各タスクワーカーは、その指定されたメタデータパーティションをスキャンし、その中で識別されたライブオブジェクトのリストを生成することができる。各オブジェクト識別ワーカー２３０によって生成されたライブオブジェクトのリストは、ストレージプール１３０に格納される。結果をストレージプール１３０内に格納する利点は、その結果が、タスクワーカー１１０のいずれかが、後に続くフェーズで作業するために利用可能であるということである。これは、タスクワーカー１１０またはジョブコントローラ１０５のいずれにもパフォーマンスボトルネックが発生しないように、フェーズ内のタスクの並列化を促進する。さらに、この並列化により、各新しいストレージノードが１つまたは複数の新しいタスクワーカー１１０を実装する、追加のストレージノードのスケーラビリティが可能になる。
【００４０】
一実施形態によれば、ライブオブジェクトを識別するデータは、オブジェクトＩＤベースのパーティション２３２に格納され、各ライブオブジェクトを識別するデータが格納されているパーティションは、そのライブオブジェクトのオブジェクトＩＤに基づいている。例えば、ライブオブジェクトのオブジェクトＩＤにハッシュ関数を適用して、ライブオブジェクトを識別する情報を格納するパーティションを決定することができる。データのオブジェクトＩＤベースの再分配の結果は、オブジェクトＩＤベースのパーティション２３２のセットである。パーティション２３２はオブジェクトＩＤに基づいて形成されるので、任意の所与のオブジェクトＩＤはパーティション２３２の１つのみに現れる。
【００４１】
一実施形態によれば、ライブオブジェクト識別ワーカー２３０は、その結果を適切なパーティション２３２に書き込む。別の実施形態によれば、ライブオブジェクト識別ワーカー２３０は、単にその出力をジョブコントローラ１０５に提供し、ジョブコントローラ１０５は、ライブオブジェクトの複数のリストを、候補セット３５０内のすべてのライブオブジェクトを表すライブオブジェクトの単一のリストに集約し、次のそのリストを分割してパーティション２３２を形成する。
【００４２】
ライブクランプの識別
図２に戻って参照すると、フェーズ２１０において、ジョブコントローラ１０５は、ライブクランプ識別ワーカー２３５にタスクを割り当てる。フェーズ２１０の間、各タスクはパーティション２３２の１つに対応する。パーティションを割り当てられたタスクワーカーは、（ａ）割り当てられたパーティションのライブオブジェクトのリストを読み取り、（ｂ）これらのライブオブジェクトがマッピングされているライブクランプを識別する。
【００４３】
一実施形態では、ライブクランプ識別ワーカー２３５の各タスクワーカーは（その割り当てられたパーティションからの）ライブオブジェクトＩＤのサブセットを受信し、ライブオブジェクトＩＤのサブセット内のライブオブジェクトを構成するライブクランプリファレンスのリストを生成するために、ファイルマネージャ１２２においてオブジェクト対クランプマッピングを列挙する。一実施形態では、ライブクランプリファレンスのリストは、クランプフィンガープリントのリストである。
【００４４】
図４は、各ライブオブジェクトのクランプフィンガープリントを識別するために、ライブオブジェクトＩＤのサブセットを含むオブジェクトＩＤベースのパーティションを受け取るライブクランプ識別ワーカー２３５の例示的な実施形態を表す。パーティション２３２を構成するオブジェクトＩＤベースのパーティションのセットは、ジョブコントローラ１０５によって管理される。一実施形態では、ジョブコントローラ１０５は、利用可能なライブクランプ識別ワーカー２３５にオブジェクトＩＤベースのパーティション４１０，４１５、及び４２０を割り当てる。次に、ライブクランプ識別ワーカー２３５の各々は、オブジェクト対クランプマッピングメタデータを列挙して、割り当てられたオブジェクトＩＤベースのパーティション内の各ライブオブジェクトに関連するクランプフィンガープリントを決定する。例えば、オブジェクトＩＤベースのパーティション４１０の場合、対応するライブクランプ識別ワーカー２３５Ａは、オブジェクトＩＤ ｛１，３，５｝に関連するすべてのクランプを決定するために、オブジェクト対マッピングマッピングメタデータを列挙する。出力は、クランプフィンガープリント｛ＦＡ、ＣＤ、ＡＢ｝を含むクランプフィンガープリントリスト４２５である。
【００４５】
同様に、ライブクランプ識別ワーカー２３５Ｂは、オブジェクトＩＤベースのパーティション４１５を受け取り、次に、オブジェクトＩＤ ｛１０，２７｝に関連付けられたすべてのクランプを決定するために、オブジェクト対クランプマッピングメタデータを列挙する。クランプフィンガープリントリスト４３０は、｛ＦＡ｝を含むライブクランプ識別ワーカー２３５Ｂの出力を表す。最後に、ライブクランプ識別ワーカー２３５Ｃは、オブジェクトＩＤベースのパーティション４２０を受け取り、次に、オブジェクトＩＤ ｛２，１００｝に関連付けられたすべてのクランプを決定するために、オブジェクト対クランプマッピングメタデータを列挙する。クランプフィンガープリントリスト４３５は、ライブクランプ識別ワーカー２３５Ｃからの出力を表し、｛ＥＸ、ＤＦ、ＧＨ｝を含む。
【００４６】
一実施形態では、ライブクランプ識別ワーカー２３５Ａ、２３５Ｂ、及び２３５Ｃは、クランプフィンガープリントに基づいて範囲分割（range partitioning）を使用して、対応するクランプフィンガープリントリスト425,430、および435からの結果を書き込み、ストレージプール１３０に格納された適切なクランプフィンガープリントベースのパーティション２３７に転送する。範囲ベースの分割（パーティショニング）を使用する実施形態では、クランプフィンガープリントのベースのパーティション２３７は、パーティション２３７内の各パーティションがほぼ等しい範囲のクランプフィンガープリントを含むように、クランプフィンガープリントに基づいて形成される。一実施形態では、クランプフィンガープリントの範囲は、クランプフィンガープリントの範囲内に収まると予想されるユニークなクランプフィンガープリントの数、及びタスクワーカーのそれぞれのメモリに収まるクランプフィンガープリントの数に基づいて決定される。
【００４７】
別の実施形態では、ライブクランプ識別ワーカー２３５Ａ、２３５Ｂ、及び２３５Ｃは、クランプフィンガープリントリスト４２５，４３０、及び４３５をジョブコントローラ１０５に送信する。ジョブコントローラ１０５は、クランプフィンガープリントのリストを集約し、その後、分割キー（partitioning key）としてクランプフィンガープリントを使用して範囲ベースの分割を実行して、パーティション２３７を生成する。
【００４８】
一実施形態では、パーティション２３７内のクランプフィンガープリントのリストは、各クランプフィンガープリントに関連付けられた属性データも含むことができる。例えば、ライフタイム属性は、各クランプのフィンガープリントに含まれてもよく、ライフタイム属性は、永続性ストレージ内のクランプの予想される有効期限である。他の実施形態では、クランプフィンガープリントの特性を記述する他の属性をパーティション２３７内に格納することができる。
【００４９】
別の実施形態では、オブジェクトＩＤベースのパーティションからクランプフィンガープリントのリストを決定するために、ライブクランプフィンガープリントのリストは、ファイルシステム１１５からのクランプ参照カウントに基づいて決定されてもよい。ファイルシステム１１５は、メタデータ内でクランプが参照される回数の参照カウントを維持することができる。例えば、ファイルＡ、ファイルＢ、及びファイルＣがそれぞれクランプＺを参照する場合、クランプＺの参照カウント値は３である。ファイルＡ、Ｂ、及びＣのそれぞれが削除されると、クランプＺの参照カウントがデクリメントされる。３つのファイルがすべて削除された後、クランプＺの参照カウントはゼロになる。そのような実施形態では、ライブクランプは正の参照カウントを有するクランプである。ジョブコントローラ１０５は、参照カウントに基づいてライブクランプフィンガープリントを決定するために、クランプ参照カウントメタデータのパーティションをライブクランプ識別ワーカー３５に割り当てることができる。
【００５０】
ライブクランプためのコンテナの決定
図２に戻って参照すると、フェーズ２１５は、パーティション２３７内のクランプフィンガープリントのそれぞれのコンテナ識別子を決定するフェーズを表す。
【００５１】
一実施形態では、フェーズ２１５において、ジョブコントローラ１０５は、パーティション２３７からパーティションをコンテナ識別ワーカー２４０に割り当てる。均等なサイズのタスクが確実に割り当てられるように、ジョブコントローラ１０５は、パーティションがほぼ等しいサイズであることを保証するために、パーティション２３７内のパーティションを統合して再分割することができる。再分割ステップは、各パーティションが同様のサイズのクランプフィンガープリントの連続範囲を含むように、範囲ベースの分割に使用される範囲を選択することを含むことができる。各クランプフィンガープリントのコンテナを識別するタスクは、コンテナ識別ワーカー２４０に委任される。
【００５２】
図５は、各ライブクランプフィンガープリントのコンテナＩＤを識別するために、ライブクランプフィンガープリントのサブセットを含むクランプフィンガープリントパーティションを受け取るコンテナ識別ワーカー２４０の例示的な実施形態を示す。パーティション２３７を構成するクランプフィンガープリントパーティションのセットは、ジョブコントローラ１０５によって管理される。一実施形態では、ジョブコントローラ１０５は、利用可能なコンテナ識別ワーカー２４０にクランプフィンガープリントパーティション５１０，５１５、及び５２０を割り当てる。
【００５３】
コンテナ識別ワーカー２４０のそれぞれは、次に、クランプフィンガープリントパーティション２３７を、クランプフィンガープリントのソートされたリストに再編成する。図示された例では、クランプフィンガープリントリスト｛ＡＢ、ＣＤ｝、｛ＦＡ、ＦＡ、ＥＸ、ＤＦ｝および｛ＧＨ｝をそれぞれ含む３つのパーティション２３７がある。コンテナ識別ワーカー２４０は、各リストをソートして、クランプフィンガープリント｛ＡＢ、ＣＤ｝ ５２５、｛ＤＦ、ＥＸ、ＦＡ、ＦＡ｝ ５３０及び｛ＧＨ｝ ５３５のソート済みリストを生成する。現在の例では、クランプフィンガープリントはアルファベットコードとして表され、それに応じてソートされる。他の実施形態では、クランプフィンガープリントのソートは、１６進数、英数字、またはバイナリなどの他のタイプのコードに基づいてもよく、コードタイプに基づいてソートされてもよい。
【００５４】
一実施形態では、コンテナ識別ワーカー２４０は、受け取ったクランプフィンガープリントパーティションから重複したクランプフィンガープリントを除去する。例えば、コンテナ識別ワーカー２４０Ｂは、｛ＤＦ、ＥＸ、ＦＡ、ＦＡ｝を含むクランプフィンガープリントパーティションを受け取った。クランプフィンガープリントパーティション内にクランプフィンガープリントＦＡのコピーが２つあるので、コンテナ識別ワーカー２４０Ｂは、ＦＡの１つのコピーを除去して、｛ＤＦ、ＥＸ、ＦＡ｝のクランプフィンガープリントパーティションを結果としてもたらすことができる。
【００５５】
フィンガープリントインデックス
フィンガープリントインデックス１２５は、クランプフィンガープリントを、それぞれのクランプが格納されている対応するコンテナＩＤにマップするクランプリファレンスコンテナ識別子マッピングを含む。複数のコンテナがクランプを格納している可能性があるため、特定のクランプフィンガープリントに対応する複数のコンテナＩＤが存在する可能性がある。コンテナ識別ワーカー２４０は、フィンガープリントインデックス１２５を照会することによって、各クランプフィンガープリントのコンテナ識別子を決定する。
【００５６】
各パーティションは、フィンガープリントの特定の範囲に対するものであるので、フィンガープリント範囲に関連するパーティションを割り当てられたタスクワーカーは、そのフィンガープリント範囲に対応するフィンガープリントインデックス１２５の比較的小さな部分のみにアクセスする必要がある。一実施形態では、コンテナ識別ワーカー２４０のそれぞれは、割り当てられたクランプのフィンガープリントパーティション内のクランプフィンガープリントとフィンガープリントインデックス１２５との間の結合（join）操作を実行することができる。
【００５７】
結合操作
一実施形態では、実行される結合操作は、フィンガープリントインデックス１２５に対するクランプフィンガープリントパーティションの右外部結合（right outer join）である。例えば、クランプフィンガープリントパーティションは、属性がクランプフィンガープリントに関連する１つまたは複数の属性を表すことができる特定のパーティションに対するライブクランプフィンガープリント列＜フィンガープリント、属性＞を含む。フィンガープリントインデックス１２５は、＜フィンガープリント、コンテナID＞の列を含む。したがって、右外部結合は、＜フィンガープリント、属性、コンテナID＞などのタプルを生成する。結合操作は、右外側結合であるので、フィンガープリントインデックス１２５からのフィンガープリントが、クランプフィンガープリントパーティション内のフィンガープリントと一致しない場合、フィンガープリントおよび属性エントリの結果セットにヌル値が入力される。結果セットのこれらのヌル値は、フィンガープリントインデックス１２５における特定のフィンガープリントがライブクランプフィンガープリントではないことを示す。一実施形態では、クランプフィンガープリントパーティションおよび/またはフィンガープリントインデックス１２５は、上記のエントリに限定されず、結合操作の一部として他のエントリを含むことができる。
【００５８】
別の実施形態では、コンテナ識別ワーカー２４０のそれぞれは、クランプフィンガープリントパーティションにおけるクランプフィンガープリントとフィンガープリントインデックス１２５との間の内部結合（inner join）操作を実行する。先の例を用いると、内部結合操作は、クランプフィンガープリントパーティションからフィンガープリントインデックス１２５内の＜フィンガープリント、コンテナＩＤ＞エントリに、＜フィンガープリント、属性＞エントリを結合することを含むことができる。内部結合の結果セットには、クランプフィンガープリントパーティションのライブクランプフィンガープリントのみを含むエントリ＜フィンガープリント、属性、コンテナＩＤ＞のマッチングセットが含まれる。
【００５９】
一実施形態では、フィンガープリントインデックス１２５は、複数のコンテナが対応するクランプを格納している可能性があるため、特定のクランプフィンガープリントに対する複数のクランプリファレンス対コンテナ識別子マッピングを含むことができる。コンテナ識別ワーカーが、クランプフィンガープリントパーティションにおけるクランプフィンガープリントとフィンガープリントインデックス１２５との間の結合操作を実行する際に、所与のクランプフィンガープリントに対して複数のマッピングに遭遇すると、ワーカーは、結合操作の結果に含めるために複数のマッピングのうち１つを選択する。一実施形態では、コンテナ識別ワーカーは、直近に書き込まれたコンテナに対応する所与のクランプフィンガープリントに対する１つのクランプリファレンス対コンテナ識別子マッピングを選択する。
【００６０】
バイナリ検索による結合
結合操作の一実施形態では、結合操作は、コンテナ識別ワーカー２４０の各々がフィンガープリントインデックス１２５に対してバイナリ検索（binary search）を実行するバイナリ検索アプローチを使用して実施される。バイナリ検索では、まず、特定のクランプフィンガープリントをフィンガープリントインデックス１２５の中央のキーと比較することによって、クランプフィンガープリントパーティションからの特定のクランプフィンガープリントが、フィンガープリントインデックス１２５内のフィンガープリント（ここではキーと呼ぶ）と比較される。特定のクランプフィンガープリントがキーと一致しない場合、コンテナ識別ワーカー２４０Ａは、比較されたキーのポイントでフィンガープリントインデックス１２５を分割し、キーと特定のクランプフィンガープリントとの比較に基づいてフィンガープリントインデックス１２５の半分を選択する。
【００６１】
例えば、フィンガープリントインデックス１２５が１〜２０の範囲のキー値を含み、特定のクランプフィンガープリントが８である場合、中央のキー値である１１と比較すると、コンテナ識別ワーカー２４０Ａは、１１でキーの範囲を、キー範囲１〜１０および１２〜２０に分割し、特定のクランプフィンガープリントが最初のキー範囲１〜１０の範囲内にあるため、次のバイナリ比較のキー範囲１〜１０を選択する。次のキー範囲を選択した後、コンテナ識別ワーカー２４０は、特定のクランプフィンガープリントと一致する所望のキーが見つかるまで、新しいキー範囲１〜１０に対してバイナリ検索プロセスを繰り返す。
【００６２】
一実施形態では、コンテナ識別ワーカー２４０の各々は、ワーカーが処理しているクランプフィンガープリントのパーティションのフィンガープリント範囲に対応するフィンガープリントインデックスの部分をメモリにロードし、フィンガープリントインデックスのメモリ内部分をソートし、フィンガープリントインデックスのメモリ内ソート部分に対してバイナリ検索を使用して結合操作を実行する。
【００６３】
補間検索（interpolated search）による結合
コンテナ識別ワーカー２４０Ａによって実行される結合操作の別の実施形態では、結合操作は補間検索アルゴリズムを使用して実施される。補間検索アルゴリズムは、キー値によって順序付けられた配列（アレイ）に対して、指定されたキー値を検索する。配列の開始と終了のキー値を知り、配列のキー値が一様に分布していると仮定すると、コンテナ識別ワーカー２４０Ａは、配列内のキー値の範囲と配列内のキー値の一様な分布に基づいて、配列内の特定の位置のキーに特定のクランプフィンガープリントを比較することができる。配列内の特定の位置のキー値が特定のクランプフィンガープリントと一致しない場合、コンテナ識別ワーカー２４０Ａは、配列を特定の位置の左右に２つのパーティションに分割することができ、特定のクランプフィンガープリント値を含む範囲を持つパーティションで補間検索処理を繰り返す。
【００６４】
例えば、フィンガープリントインデックス１２５の範囲が１〜２０であり、特定のクランプフィンガープリントが４である場合、コンテナ識別ワーカー２４０Ａは、特定のクランプフィンガープリントを、フィンガープリントインデックス１２５の１／５に位置するキーと比較することができる。フィンガープリントインデックス１２５に１/５に位置するキーが５であると仮定すると、コンテナ識別ワーカー２４０Ａは、インデックス配列を２つのパーティション１−４および６−２０に分割し、特定のクランプフィンガープリント値を含む範囲を有するパーティションを選択する。この場合、１〜４のパーティションにはクランプフィンガープリント値が含まれている。次に、コンテナ識別ワーカー２４０Ａは、１〜４のパーティションについて補間検索を繰り返す。一実施形態では、補間検索ステップは、特定のクランプフィンガープリントと一致するキー値が一致するまで繰り返されてもよい。特定のクランプフィンガープリントが一致すると、コンテナ識別ワーカー２４０Ａは、クランプフィンガープリントパーティション内の各クランプフィンガープリントに対して当該ステップを繰り返す。
【００６５】
クランプフィンガープリントパーティションとフィンガープリントインデックス１２５を結合するときに補間検索を実行する利点は、特定のクランプフィンガープリントのコンテナＩＤを決定するために、キー値に一致するように検索ラウンドの数を減らすことである。検索ラウンドの数を減らすことは、コンテナ識別ワーカー２４０の各々に必要とされる計算サイクル数を減少させ、コンテナ識別ステップを実行するのに必要な時間を短縮する。
【００６６】
一実施形態では、コンテナ識別ワーカー２４０の各々は、ワーカーが処理しているクランプフィンガープリントのパーティションのフィンガープリント範囲に対応するフィンガープリントインデックスの部分をメモリにロードし、フィンガープリントのメモリ内部分をソートし、フィンガープリントインデックスのメモリ内ソート部分に対して補間検索を用いて結合演算を実行する。
【００６７】
クランプフィンガープリント対コンテナＩＤの結果を出力
図５に戻って参照すると、コンテナ識別ワーカー２４０Ａは、フィンガープリントインデックス１２５に対して結合操作を実行して、クランプフィンガープリントＡＢおよびＣＤがコンテナＩＤ１００１内に格納されていることを決定する。一実施形態では、コンテナ識別ワーカー２４０は、その結果をストレージプール１３０内に格納されたそれぞれのコンテナＩＤパーティション２４２に書き込む。結果は、ライブクランプフィンガープリントとそのコンテナＩＤ記憶位置との間のマッピングを含むので、ライブクランプフィンガープリント対コンテナＩＤリストと呼ぶことができる。一実施形態では、コンテナ識別ワーカー２４０は、所与のコンテナＩＤにマッピングされたすべてのライブクランプフィンガープリントが同じコンテナＩＤパーティションに書き込まれるように、コンテナＩＤのハッシュに基づいて選択されたコンテナＩＤパーティションに、各ライブクランプフィンガープリント対コンテナＩＤマッピングを書き込む。図５に示す実施形態では、コンテナＩＤパーティション２４２の第１のパーティションは、コンテナ１００１に関連するすべてのライブクランプフィンガープリントコンテナＩＤタプルを含み、第２のパーティションは、コンテナ１２０１に関連するすべてのタプルを含み、第３のパーティションは、コンテナ１１０１および１１０２に関連するすべてのタプルを含む。
【００６８】
別の実施形態では、コンテナ識別ワーカー２４０は、その結果をジョブコントローラ１０５に送信し、ジョブコントローラ１０５は、ライブクランプフィンガープリント対コンテナＩＤリストをコンテナＩＤパーティション２４２に集約する。図５は、コンテナ識別ワーカー２４０の結果から集約されたコンテナＩＤパーティション２４２の例示的なセットを示す。フィンガープリント対コンテナＩＤセット２４２は、各要素がフィンガープリントおよびコンテナＩＤを含むリストを含む。一実施形態では、フィンガープリント対コンテナＩＤセット２４２はまた、クランプのための他の属性を表す他のフィールドを含むことができる。
【００６９】
ライブクランプのコンテナのスコアリング
図２に戻って参照すると、フェーズ２２０は、対応するコンテナから記憶空間を再利用する優先度に基づいて、コンテナＩＤパーティション２４２内の各コンテナＩＤにスコアを割り当てるフェーズを表す。
【００７０】
一実施形態では、フェーズ２２０において、ジョブコントローラ１０５は、パーティション２４２からコンテナスコアリングタスクワーカー２４５にパーティションを割り当てる。次に、コンテナ識別ワーカー２４０は、コンテナ内のライブクランプの数および各ライブクランプの属性に基づいて、コンテナＩＤをスコア付けする。図６に示すように、ジョブコントローラは、コンテナＩＤ１００１のタプルを有するパーティションをコンテナスコアリングタスクワーカー２４５Ａに割り当て、コンテナＩＤ１２０１のタプルを有するパーティションをコンテナスコアリングタスクワーカー２４５Ｂに割り当て、コンテナＩＤ１１０１及び１１０２のタプルを有するパーティションをコンテナスコアリングタスクワーカー２４５Ｃに割り当てる。
【００７１】
一実施形態では、コンテナスコアリングタスクワーカー２４５の各々は、割り当てられたコンテナＩＤパーティションのライブクランプフィンガープリント対コンテナＩＤタプルをメモリにロードし、タプルのメモリ内リストをコンテナＩＤでソートし、それぞれのコンテナ内のライブクランプを決定する。その後、ワーカーは、各ライブクランプのライフタイム、特定のコンテナ内のライブクランプの数、および特定のコンテナ内のライブクランプのサイズなど、コンテナ内のライブクランプの属性に基づいて計算したスコアを各コンテナＩＤに割り当てる。ライフタイムとは、ライブクランプがどれくらい長く活き続けると予想されているかを指す。特定のコンテナＩＤのスコアの値は、コピー転送フェーズ中に記憶空間を再利用するために必要なタスクの量に対する、再利用される記憶空間の量を表す。
【００７２】
例えば、ライブクランプを含まないコンテナは、新しいコンテナにライブクランプをコピー転送するためにリソースを使用する必要なく、コンテナの記憶空間全体が再利用され得るので、最も高いスコアが割り当てられる。逆に、多くのライブクランプを含むコンテナは、ライブクランプをコピーするためにリソースが必要となり、コピー転送されたライブクランプが新しいコンテナにおける新しい記憶空間を占めるため、再利用される記憶空間の量は最小限に抑えられる。一実施形態では、すぐに活動を停止しまう多くのライブクランプを含むコンテナは、それらのコンテナから記憶空間を再利用する前にクランプが活動停止してしまうのを待つ方がより効率的であるため、比較的低い得点が割り当てられる。
【００７３】
このため、各ライブクランプのライフタイム、ライブクランプの数、および各ライブクランプのサイズは、各コンテナＩＤに割り当てられたスコアに影響を及ぼす。一実施形態では、スコアは、ライブクランプに関連するライフタイム、数、およびサイズ特性のそれぞれに異なる重みを適用するように構成されてもよい。
【００７４】
図６に戻って、コンテナスコアリングタスクワーカー２４５Ａ、２４５Ｂ、及び２４５Ｃは、割り当てられたパーティションにおけるコンテナＩＤにスコアを割り当てた後、コンテナスコアリングタスクワーカー２４５Ａ、２４５Ｂ、及び２４５Ｃは、それらの結果をストレージプール１３０内のスコアベースのパーティション２４７に書き込む。具体的には、スコアベースのパーティション２４７の各々はスコアの範囲に対応し、コンテナスコアリングタスクワーカー２４５によって範囲ベースの分割が使用され、各コンテナＩＤが、コンテナのスコアが入る範囲に関連するパーティションに書き込まれる。例えば、スコアリングシステムが０〜１００の値に基づいている場合、パーティション１はスコア９１〜１００をカバーし、パーティション２はスコア７６〜９０をカバーし、パーティション３はスコア５６〜７５をカバーし、パーティション４はスコア３１〜５５をカバーし、およびパーティション５はスコア０〜３０をカバーする。
【００７５】
一実施形態では、同じスコア範囲をカバーする複数のパーティションが存在してもよく、コンテナスコアリングタスクワーカー２４５は、まず、コンテナＩＤに割り当てられたスコアに基づいて各コンテナＩＤのパーティションを選択し、次に同じスコア範囲をカバーする複数のパーティションの中から選択するためにコンテナＩＤのハッシュを選択する。一実施形態では、しきい値未満のスコアを有するコンテナＩＤは、結果から除外され、スコアベースのパーティション２４７には含まれない。
【００７６】
別の実施形態では、コンテナスコアリングタスクワーカー２４５Ａ、２４５Ｂ、及び２４５Ｃは、その結果をジョブコントローラ１０５に送信する。次に、ジョブコントローラ１０５は、対応するコンテナについて決定されたスコアに基づいて、範囲ベースの分割を用いて、コンテナＩＤをパーティションに分割する。
【００７７】
ライブオブジェクトのコピー転送
候補セット３５０内の選択されたコンテナに対してコピー転送操作（コピーフォワードオペレーション）が実行され、選択されたコンテナ内のすべてのライブクランプが新しいコンテナに転送される。次に、選択されたコンテナが削除され、選択されたコンテナが占有する記憶空間が解放される。図２を再び参照すると、フェーズ２２５において、ジョブコントローラ１０５は、スコアベースのパーティション２４７内のコンテナを１つ以上のコピー転送タスクワーカー２５０に割り当てる。
【００７８】
図７は、１つ以上のコピー転送タスクワーカー２５０にコピー転送操作を割り当てる例示的な実施形態を示す。図７において、ジョブコントローラ１０５は、スコアベースのパーティションから特定のコピー転送ワーカーにコンテナＩＤを割り当てる。
【００７９】
スコアベースのパーティションは、パーティションのスコア範囲の順にコピー転送タスクワーカー２５０に割り当てられ、その結果、最も高いスコアに関連付けられたコンテナＩＤが最初にワーカー２５０に割り当てられる。最高スコアに基づくパーティション内のコンテナＩＤに対してコピー転送操作を実行すると、記憶空間を再利用するために必要なリソースを基準として相対的に最も多くの記憶空間再利用が生じることとなる。一実施形態では、同じスコア範囲をカバーするスコアベースの複数のパーティションが存在し、与えられたスコア範囲をカバーするパーティションの各々は、低いスコア範囲をカバーするパーティションの前にワーカー２５０に割り当てられる。
【００８０】
図７に示された実施形態に戻ると、コンテナＩＤ１００１および１１０１は、それぞれ割り当てられたスコアが９５および９１である。スコアおよびスコア範囲に対するスコアベースのパーティション定義に基づいて、コンテナＩＤ１００１および１１０１がスコアベースのパーティション７０５内に格納される。コンテナＩＤ１２０１は７０のスコアを有し、５６から７５のスコア範囲をカバーするスコアベースのパーティション７１０内に格納される。この例では、コンテナから記憶空間を再利用することは、記憶空間を再利用するために必要なリソースに対して多くの記憶空間を生成しないので、コンテナＩＤ１１０２はスコア１０を有し、スコアベースのパーティションからは省かれている。図７において、ジョブコントローラ１０５は、スコアベースのパーティション７０５からコンテナＩＤをコピー転送タスクワーカー２５０Ａに割り当て、その後、スコアベースのパーティション７１０からコンテナＩＤをコピー転送タスクワーカー２５０Ｂに割り当てる。
【００８１】
一実施形態では、コピー転送タスクワーカー２５０は、割り当てられた各コンテナにおけるライブクランプを読み取り、ライブコンテナを新しいコンテナに書き込む。新しいコンテナは、新しいデータログ内に配置することができる。 割り当てられたコンテナ内のライブクランプがすべて新しいコンテナに書き込まれた後、割り当てられたコンテナの記憶空間全体を再利用するために、割り当てられたコンテナが削除される。例えば、図７において、コンテナ７１５は、コピー転送タスクワーカー２５０Ａに割り当てられたコンテナＩＤ１００１を表す。次に、コピー転送タスクワーカー２５０Ａは、ライブログの新しいコピーを、コンテナ７１５からデータログ７２０内にある新しいコンテナ７２５に書き込む。このプロセスは、コンテナ７１５からのすべてのライブクランプが新しいコンテナ７２５内に生成されるまで続く。ライブクランプが新しいコンテナ７２５内に作成された後、コピー転送タスクワーカー２５０Ａはコンテナ７１５を削除し、コンテナ７１５が占有する記憶空間を再利用する。
【００８２】
一実施形態では、コピー転送タスクワーカー７１０の各々は、ワーカーに割り当てられたスコアベースのパーティションをメモリにロードし、各コンテナＩＤに関連付けられたスコアによってメモリ内スコアベースのパーティションをソートし、 ソートされたメモリ内スコアベースのパーティションの順に、コンテナ内のライブクランプをコピーする。
【００８３】
分散仮想アレイ
図８は、前述の方法に基づいて空間再利用を実行する分散仮想アレイ（DVA）システムの一実施形態を示す。ＤＶＡは、任意の数（１つを含む）のホスト８００と、例えば、サーバと、ストレージプール１０００とを含み、ストレージプール１０００は、ホストの観点から、単一のまだ分散したストレージシステムを形成することができるストレージノード１０１０−１,１０１０−２、．．．、１０１０−Ｎ（まとめて「１０１０」）を含む。ホスト８００内のエンティティは、不揮発性メモリ（ＮＶＲＡＭ１０３０として示される）に最初に記憶され、最終的にノードに位置する永続性ストレージ装置１０４０−１、．．．、１０４０−Ｎ（集合的に「１０４０」）に記憶されるデータを書き込む。
【００８４】
読取りおよび書込みエンティティは、仮想マシン８３０（「ＶＭ」８３０−１ ．．． ８３０−ｎとして別々に示される）またはユーザレベルアプリケーション８４０などのより一般的な非仮想化プロセスを含む、任意のタイプのものであってもよい。データの読み取りおよび/または書き込みを必要とするソフトウェアおよびハードウェアエンティティは、ここでは「クライアント」と呼ばれる。
【００８５】
各ホストは、１つまたは複数のプロセッサ（ＣＰＵ）８１１と、データおよび/またはＣＰＵ上で実行可能なコードの、非永続的、揮発性および/または永続的、不揮発性の、非一時的なストレージのためのいくつかのデバイス８１２とを含むシステムハードウェア８１０を含む。伝統的に、「メモリ」と「ストレージ」との間には、前者は典型的に高速、揮発性、ソリッドステート装置（固体装置）を含み、一方、後者は一般に、より遅く、不揮発性の、機械的または光機械的装置を含んだものであるから、比較的明確な技術的差異がある。しかしながら、バルクで持続的なストレージのための最新技術の広範な使用に伴い、この区別はますます明確になっていない。
例えば、現代のサーバの多くは、特に連続していない記憶位置の場合、通常、ＩＯＰＳ（Input / Output Operations Per Second）の観点から測定される、スループットとスピードを上げるために、「サーバフラッシュ」などのソリッドステートストレージデバイス（ＳＳＤ）を使用している。相変化メモリ（ＰＲＡＭ）などの新興技術は、この区別をさらに曖昧にしている。ここで説明する実施形態を実装するために特定のタイプのホスト側ストレージまたはメモリ技術は必要とされず、すべてのホストが同じストレージ技術を採用する必要はない。
【００８６】
ハードウェア８１０は、インターネット、内部企業ネットワークなどの任意の既知の公的または専有のローカルまたはワイドエリアネットワークであってもよい、１つまたは複数のネットワーク９００を介してシステムの様々なコンポーネント間でデータを転送するためのネットワーク接続デバイス８１４などの他の従来のメカニズムを含む。唯一の要件は、どのネットワークが使用されていても、すべてのクライアントがアクセスする必要のあるストレージノード（下記参照）にアクセスできることである。したがって、「ネットワーク」９００は、データが異なるネットワーク間を通過する必要がある場合には、必要なスイッチングまたは他の通信デバイスと共に、実装されているネットワークの集合として読み取られるべきである。
【００８７】
各ホストはまた、実装に応じて、オペレーティングシステム（ＯＳ）、デバイスドライバなどのような従来のシステムソフトウェア８１５を含むことになる。図示の構成では、ホスト８００の１つが仮想化プラットフォームをサポートするものとして示されているが、典型的には、システムハードウェア８１０と（図示の実施形態では）少なくとも１つの仮想マシン（ＶＭ）８３０−１、．．．、８３０−ｎとの間の何らかの形態のハイパーバイザ８２０または類似のインターフェースレイヤを含む。よく知られているように、ＶＭは、実際の物理コンピュータシステムのソフトウェア抽象化である。
【００８８】
ＶＭを図８に示す。ほとんどの実装では、仮想マシンは、ハイパーバイザ/ハードウェアホスト上で実行されている「ゲスト」である。いくつかの仮想化システムでは、「仮想マシンモニタ」が、ハイパーバイザやホストＯＳなどの基礎となるソフトウェアレイヤへのインターフェースとして含まれている。ＶＭｗａｒｅ社のＥＳＸ Ｓｅｒｖｅｒファミリ製品のような多くのハイパーバイザは、ホストＯＳとの対話の必要なしに、「ベアメタル（bare metal）」すなわちシステムハードウェア８１０上で直接実行される。他の仮想化プラットフォームでは、ハイパーバイザは、ハイパーバイザからのコールに応じていくつかの操作をサポートして実行するホストＯＳ上又はホストＯＳと同じレベルで実行することができる。ここに記載された様々な実施形態は、ＶＭ、ハイパーバイザまたは他の仮想化レイヤのいずれの特定の仮想化アーキテクチャにも依存しない。確かに、ＶＭはまったく前提とされていない。むしろ、ソフトウェアおよびハードウェアエンティティ（「クライアント」）からのデータストレージ読取り/書込み要求を処理するいくつかのシステムソフトウェアレイヤが想定される。したがって、「ホスト」は、以下に説明する分散記憶装置（distributed storage arrangement）へのデータの書き込みおよび/またはそこからのデータの読み出しを望むプロセス（そのＶＭは特別なケースである）が実行される任意のプラットフォームである。
【００８９】
プール１０００内の様々なストレージノード１０１０は、別個のユニットとして示されており、異なる物理サーバであってもよいが、アドレッシングの目的で単一の論理境界内にあるとみなされてもよい。しかしながら、アドレス指定可能なストレージプールの論理的概念的境界は、図示された物理ストレージノード１０１０−１,１０１０−２、．．．、１０１０−Ｎのセットを超えて拡張したストレージコンポーネントおよびプロセスも含むことができる。
【００９０】
所望のＤＶＡ機能に応じて、プールマネージャ１０５０も、ノード１０１０のいくつかの配信および制御機能を処理し、ノード１０１０などに共通の管理および他のデータを維持するために、含むことができる。そのようなプールマネージャは、１つ以上のストレージノード内、１つまたは複数のホスト内、または同じネットワークに接続された別個のコンピューティングシステム内で動作することができる。独立したエンティティとして実装することもできるが、プールマネージャは、プール内に格納された（仮想ディスクなどの）ファイルのファイルネームスペースを管理するため、クラスタ管理のため、および他のノード管理機能のため等の他の管理コンポーネントも含むことができる。
【００９１】
ストレージノードを実現するための可能な選択肢の多くの現在利用可能な例のうちの２つは、集中的な入出力タスクのための低電力サーバアーキテクチャである、複数のディスクコントローラを有するＸｙｒａｔｅｘシャーシまたは単一ディスク「ＦＡＷＮ」（弱小ノードの高速アレイ（Fast Array of Wimpy Nodes））であり得る。より一般的には、ノードは、任意の形態のバスまたはネットワーク接続を介して少なくとも１つのディスクと通信する任意の形態のコンピュータを使用して実装することができる。実際、ノード自体は、ストレージプールにデータを書き込むエンティティでもある。
【００９２】
各ノードは、１つまたは複数のディスク、フラッシュまたは他のＳＳＤデバイス、または（２つ以上の物理的装置を含む）永続性ストレージ装置１０４０を含む他のデバイスを制御する従来の処理回路をそれぞれ含む１つまたは複数のストレージコントローラ１０２０−１,１０２０−２、．．．、１０２０−Ｎ（まとめて１０２０）を含む。コントローラはまた、ネットワーク９００に接続するために必要な回路も含む。いくつかの実施形態では、コントローラは、単一の複合モジュール内の記憶装置と一体化することができる。ホスト８００と同様に、ストレージプール１０００のノード内で使用される様々なソフトウェアコンポーネントは、プール内の各ハードウェアプラットフォーム上のプロセッサ上で実行可能であるように任意の従来の方法でロードおよび/または格納される。これらのメディアおよびプロセッサは、簡潔にするために、図面に別々に図示されていない。熟練したプログラマはもちろんこれらが存在することを理解するであろう。これまで説明したシステムコンポーネントは、多くの従来技術のシステムにも見られる。
【００９３】
好ましい実施形態では、コントローラ１０２０の少なくとも１つは、非常に短い待ち時間（低レイテンシー）で新たに書き込まれたデータを受信して永続的に記憶するために、いくつかの不揮発性メモリ１０３０（ＮＶＲＡＭ―図９）を含むか、またはアクセスすることができる。一部のシステムでは、ＮＶＲＡＭはＰＣＩｅスロット内の特別なカード上にある場合がある。いくつかの実装形態では、コントローラはバッテリバックアップを有することができる。停電時に当該コントローラは、システムメモリの一部をフラッシュドライブにコピーするのに十分な時間がある。この場合、ＮＶＲＡＭ１０３０は、別個の物理的コンポーネント（構成要素）である必要はなく、他の標準的な目的のためにコントローラ内にある汎用ＲＡＭの論理部分であってもよい。システムによっては、ＮＶＲＡＭが低レイテンシーのＳＳＤであってもかまわない。実施形態のすべての実装では、ノードにディスクとＮＶＲＡＭの両方を持たせる必要があるわけではない。むしろ、任意の所与のノードは、これらの２つのタイプの永続的ストレージデバイスのうちの１つのみを有するか、または少なくともそれらにアクセスすることができるように構成されてもよい。したがって、図８が示すように、１つまたは複数のノードが永続性ストレージ装置および不揮発性メモリの両方を有することができるようにシステムを実装することが可能であり（例えばノード１０１０‐１）、一方で、 ノードは永続性ストレージ装置を含まなくてもよく（例えばノード１０１０‐２）、さらに他のノードは不揮発性メモリコンポーネント１０３０を全く有さなくてもよい。図８もノード１０１０−Ｎと同様に、１つ以上のノードが複数の永続性ストレージ装置（１０４０‐Ｎ）を有することが可能である。さらに、いくつかの実施形態では、ＮＶＲＡＭはホスト内にあってもよい。
【００９４】
好ましい実施形態では、ホストは、永続性ストレージ装置への書き込みとは異なり、ストレージノードまたはホスト内のＮＶＲＡＭにネットワークを介してデータを書き込むことができ、前記ＮＶＲＡＭからデータを削除するコマンドを与えることもできる。これは、ＮＶＲＡＭが永続性ストレージ装置への途中のデータの透過バッファである従来のストレージシステムの構成とは対照的である。
【００９５】
上述のように、２つの支配的なストレージの基本的な考え方は、トレードオフスペクトルの異なる終点近くに位置する：ハイパーコンバージドシステム（hyper-converged systems）では、実質的にストレージおよび計算負荷が全体的に相互依存するホスト内に集中するのに対して、他のシステムでは、計算負荷の大部分がリモートストレージユニット自体に置かれ、ホストは互いに直接依存しない。いくつかの実施形態は、ホストの通常より大きい計算資源が多くのストレージ関連機能に使用されるが、重要なホスト間通信および調整を必要としない方法で使用され、メインストレージ機能が主に、他のホストを経由せずにホストがアクセスできるリモートノードに残る、異なるアプローチを採用する。
【００９６】
このために、ホストおよびノードは、それぞれのＤＶＡコンポーネント―システムソフトウェアレベルのＤＶＡｈ１１０５モジュールおよびノードにおけるＤＶＡｎ１１２５を含む。図８が重複して示すように、ＤＶＡｈ１１０５は、システムソフトウェア８１５の一部として、または仮想化プラットフォームの制御ソフトウェア（ハイパーバイザ８２０など）の一部として、または両方で協働するコンポーネントとともに、実装されてもよい。オプションとしては、システムソフトウェア８１５内またはハイパーバイザ８２０内のドライバとしてＤＶＡｈコンポーネントを構成すること、必要に応じてホストオペレーティングシステム（システムソフトウェア）への呼び出し（call-outs）を含む。また、ＤＶＡｈ１１０５コンポーネントを、異なるユーザレベルまたはシステムレベルのプロセス内、または「ヘルパー（helper）」ＶＭ内で構成することも可能である。ＤＶＡｈおよびＤＶＡｎの構成にかかわらず、それらは、一般に、非一時的記憶装置に格納され、ホストＣＰＵ８１１によって実行するためにメモリにロードされるプロセッサ実行可能コードの対応する本体として実装される。
【００９７】
同様に、ノード内のＤＶＡｎ１１２５コンポーネントは、それぞれのストレージコントローラ１０２０上で動作するソフトウェアとして、またはストレージコントローラとは別個のソフトウェアコントローラとして実装されてもよいが、非一時記憶装置に記憶され、ノード１０１０内のプロセッサ（単数または複数）による実行のためにメモリにロードされる、プロセッサ実行可能コードの対応する本体として実装される。
【００９８】
キャッシュ８１３は、少なくとも１つのホストに、好ましくはメモリ/ストレージコンポーネント８１２の一部として含まれることが好ましい。キャッシュは、１つまたは複数のフラッシュメモリデバイス、相変化ランダムアクセスメモリ（ＰＲＡＭ）、メインシステムメモリの一部などを使用するなど、従来の十分に高速な技術を使用して実装することができる。キャッシュは、別個にパッケージされたソリッドステートディスク（ＳＳＤ）、サーバ内のバスに接続された回路カード、サーバマザーボード上のモジュールなどとして実装されてもよい。
【００９９】
図９は、図８に示されているがＤＶＡモジュールの様々なオプションのサブコンポーネントのより詳細なメインシステムコンポーネントの簡略化された図である。１つのホストと１つのノードのみが示されているが、同様のサブコンポーネントが他のホスト／ノードにも含まれていてもよい。すべてのホストまたはノードが図９に示すものと同じＤＶＡサブコンポーネントを含む必要はないことに留意されたい。任意の所与のホストの中で、任意の所与の実装の必要性に応じて、図示されたサブコンポーネントの任意の数（１つから全て）が任意の所望の組み合わせで含まれてもよい。したがって、図９に示されるＤＶＡサブコンポーネントのセットは、例示および説明の目的のみのものである。さらに、様々なサブコンポーネントは、図９において別個のものとして示されているが、これは例示および説明の目的に過ぎず、それらのうちのいずれかまたはすべてを実行可能コードの単一の本体に組み合わせることができる。
【０１００】
ＤＶＡサブコンポーネントおよびその機能は、バックグラウンドストレージ管理機能、データ変換機能、および／または以下に概説される他の機能を含む、様々なストレージ処理（記憶処理）機能のうちのいずれかまたはすべてを実行する。従来のストレージシステムでは、通常、これらの機能はストレージコントローラ内で実行され、ホスト内では実行されない。ＤＶＡｈのサブコンポーネントは、優先的に次のものを含む：
【０１０１】
既知の技術を使用してキャッシュ８１３への読み書きを処理するキャッシュマネージャ１２１３。一実施形態では、キャッシュは、ブロックのフィンガープリントに基づいてキャッシュ内のブロックを見つけることができるようにフィンガープリントされたデータブロックを含む。
【０１０２】
ホスト上のＶＭ（または他のプロセス、仮想化されたまたはされていない）からデータを受信し、それをプール１０００に格納するために設計されたフォーマットに処理するファイルマネージャコンポーネント１２３０。また、データの読込み要求を受け取り、キャッシュまたはプールからデータを取り出し、元の格納形式に戻して要求されたデータを戻す。ファイルマネージャは、他のコンポーネントを呼び出して、データのキャッシュ、処理、格納、または検索を支援することができる。
【０１０３】
ファイルマネージャ１２３０は、マップを、ファイルオフセットから、プール１０００に格納された対応するデータ項目（data item）への参照に、更新するマッピングモジュール１２２４を呼び出すことができる。いくつかの実施形態では、そのデータ項目参照は、データ項目を含むブロックのフィンガープリントを含む。いくつかの実施形態では、ホストはフィンガープリントを計算する。いくつかの実施形態では、データ項目参照は、データ項目のロケータを含む。ファイル中のあるオフセットに対する読み出し要求を満たすために、ファイルマネージャはマッピングモジュール１２２４を呼び出して、ファイル内のそのオフセットに対して格納されたデータ項目への参照を取得する。その後、その参照を使用してキャッシュからデータ項目を取り出すことができ、またはデータ項目が存在しない場合、データ項目をプールから取り出すことができる。
【０１０４】
周知のように、仮想マシンのストレージシステムも仮想化される。したがって、ＶＭ上で実行されるプロセスは、物理ストレージであると「考えられる」ものを扱うが、実際には「仮想ディスク」（ｖＤｉｓｋ）における仮想アドレスであり、対応するアドレスマップを使用して１つまたは複数のレベルのアドレスリダイレクションを受け、最終的には物理記憶空間におけるアドレスにつながる。分散ストレージシステムの場合では、ＶＭの読み取りおよび書き込みは、最終的に、プール１０００内の１つ（またはデータがミラー化されている場合はそれ以上）の物理ストレージデバイスの対応するアドレスにマップされる。
【０１０５】
データ処理コンポーネント（処理エンジン１２２０）は、好ましくは、圧縮、暗号化、データの完全性を保証するためのチェックサム、消去されたストライプへの受信データのパッキング、例えば、ＲＡＩＤストライプの一部としてエラー訂正コード（ＥＣＣ）値を計算すること、および/またはコンピューティングフィンガープリント、すなわち受信データブロックに対する固有の識別情報を計算することなどのような既知のデータ変換機能のいずれかまたはすべてを実行するために含まれる。ＳＨＡメソッド（ＳＨＡ−１など）のいずれかを使用するなど、可能なフィンガープリンティング手法の１つの例がハッシングである。選択されたフィンガープリンティング方法が十分に衝突耐性である（すなわち、同じフィンガープリント出力を生じる２つの異なる入力の確率が十分に低い）と仮定すると、同じフィンガープリントを有する異なるデータブロックは、同じコンテンツを有すると推定され、したがって重複であると推定され得る。
【０１０６】
一実施形態では、入力データはフィンガープリントを採取され、当該入力データのフィンガープリントを、ホスト８００内のキャッシュ８１３に、格納されたブロックのフィンガープリントと比較することによって、入力データの重複を排除する。これは、プール１０００に格納されたデータを分析して重複排除させる必要性を回避する。このような構成では、これらの計算集中型タスクを通常はより強力なホストで実行できるだけでなく、ホストが最初により遠隔のストレージノード１０１０からフィンガープリントを検索しなければならない場合に遭遇するであろうレイテンシーのほとんどを回避する。
【０１０７】
フィンガープリントされたブロックのキャッシュはまた、読み取り要求に応答してプールからデータブロックを取り出す待ち時間（レイテンシ―）を回避することができる。２つの異なるファイルには、それぞれ同じコンテンツ、したがって同じフィンガープリントを持つブロックが含まれている場合がある。重複ブロックは、１つのファイルに対する読取りまたは書込み要求を満たすためにキャッシュ８１３に挿入されている可能性がある。プールからブロックをフェッチする待ち時間を発生させることなく、キャッシュから他のファイル内の重複するブロックに対する次の読み出し要求を満たすことができる。
【０１０８】
データの完全性を保証し、不完全な書き込みを検出するために、フィンガープリントまたはチェックサムを使用することもできる。例えば、フィンガープリントは、バッファされたデータについて計算されてもよい。可能性のあるホスト障害および不完全な書き込みの兆候がある場合、現在のデータのフィンガープリントをバッファされたデータのフィンガープリントと比較することができる。値が同じでない場合、バッファリングされたデータは格納されるべきデータと同一ではないので、システムはバッファされたデータが不完全であることを認識する。
【０１０９】
ログ構造ファイルシステムを使用するＤＶＡにおいて、ガベージコレクションモジュール１２２２が含まれて、いくつかの実施形態では、コピー転送されるデータを識別し、そのようなデータを新しいストライプにコピーすることを含む従来のガベージコレクション機能を実行することができる。
【０１１０】
データがストライプを使用して格納されるシステムでは、ストライプマネージャ１２２３が含まれてもよい。ストライプマネージャは、ＥＣＣエンジン１２３２を使用または含むことができ、ＥＣＣ値を計算し、設計者が実装するために選択したマッピングまたは割り当て方式に従って、複数のストレージノードにわたって分散させるストライプに追加される。
【０１１１】
モジュール１２２６は、データ完全性などを保証するために、データ再構成（例えば、ＥＣＣ情報から欠落したＲＡＩＤストライプ要素のデータ再構成）、データリバランシング（data rebalancing）、またはデータスクラビング（data scribing）などの機能を実行するためにホストに含まれてもよい。このモジュールまたは１つまたは複数の他のホストモジュールは、データをホストフラッシュキャッシュにプリフェッチするなどの操作； データクランプを形成し、その粒度で重複除外し、そのようなクランプをリパック（repack）したり、ホストのフラッシュ障害を処理したり、ホスト上のｖＤｉｓｋマップを更新したりするなどを、実行することもできる。
【０１１２】
ＤＶＡｎサブコンポーネントは、次のものを含むことができる：
【０１１３】
フィンガープリントからデータブロックロケータまたは他の識別子にマップするための指紋インデックス１２２１。ホストがフィンガープリントされたデータブロックをストライプに格納し、ストライプをプールに書き込むとき、フィンガープリントと対応するデータブロックロケータをフィンガープリントインデックスに伝える。ホストがフィンガープリントされたブロックをプールから読み取る必要がある場合、まず、インデックスからブロックロケータを要求し、プールからブロックを読み取る。インデックス１２２１は、ホストに実装されてもよいが、好ましくは、コントローラ１０２０に実装される。なぜなら、インデックスのサイズは記憶容量に比例するからであり、一般に、対応する記憶ユニットとインデックス用のメモリをバンドルすることが最も効率的であるからである。
【０１１４】
ホスト上のロギングモジュール１２２５から最近書き込まれたデータおよび他のイベントを受信し、そのデータを不揮発性の低レイテンシーＮＶＲＡＭモジュール１０３０に格納するログ１０２５。ＮＶＲＡＭモジュール１０３０は、ノード１０１０の内部にあるものとして図９に示されているが、これは１つの実装例に過ぎない。他の可能性としては、ＮＶＲＡＭモジュール１０３０を異なる専用ノード内に置くこと、または他の場所にＮＶＲＡＭモジュール１０３０を置くことが挙げられる。最近書き込まれたデータをログまたは他の方法でＮＶＲＡＭに格納することにより、書き込みは、ディスクドライブのようなより待ち時間の長い（高レイテンシー）デバイス１０４０への書き込みの待ち時間を招くことなく、「安全」として確認することができる。ログ１０２５を含む、ホストの外部にこのようなデータを格納することによって、ホストがストレージ装置１０４０の１つの永続的な場所に格納する前に失敗した場合、別のエンティティ（ストレージノードの１つ、故障していないホストの１つ、または最初にデータを受信したホスト以外の他のエンティティなど）は、不揮発性デバイス１０３０からデータを読み取ることができ、そのデータを再処理してストレージ装置１０４０の１つに記憶することができる。これは、データの唯一のコピーが、現在起動に失敗したホストを介してのみアクセス可能であったキャッシュ８１３を使って、ホストの内部にある場合には、不可能であろう。
【０１１５】
ＮＶＲＡＭモジュール１０３０を含み、ログ１０２５などのインターフェースを介してホストにそれを公開するもう１つの利点は、ホストがストレージノード上のＮＶＲＡＭにデータを書き込むことによってデータを「安全」にすることができ、例えば、ストライプなどを形成するために十分なデータがバッチ処理された後に、さらに遅く、場合によっては遅延されたストレージ処理のための計算資源（computing resource）を活用することができる。いくつかの実施形態では、ＮＶＲＡＭに書き込まれたデータの一部は、ホストによるさらなるストレージ処理なしに永続性ストレージ装置に書き込まれることは決してない。いくつかの実施形態では、ＮＶＲＡＭデバイスまたはそれが接続されているコントローラの１つの故障に対して保護するために、データを複数のＮＶＲＡＭデバイスに書き込むことができる。ホストは、それ自体が複数のＮＶＲＡＭデバイスに書き込むことができ、または、コントローラは、単一のホスト書き込みを、複数のＮＶＲＡＭデバイスに、もしくは複数の他のコントローラおよびそれらのＮＶＲＡＭデバイスに、同一または異なるノード内で、ミラーリングすることができる。
【０１１６】
一例として、ＶＭが少なくとも１つの仮想ディスクｖＤｉｓｋまたはファイルにデータを書き込みたいと仮定する。ＶＭがゲストであるホストに障害が発生すると、新しく書き込まれたデータのコピーは、一部のストレージノードのログとＮＶＲＡＭで存続している。また、書き込みデータは、書き込みのログデータを保持していない１つ以上のストレージノードを含む可能性があるプールにデータが書き込まれる前に、ファイルマネージャにバッファリングされてもよいし、（例えば、ＲＡＩＤのようなシステムでは）完全なストライプのような、ある最小記録単位（minimum storage unit）を完成するのに十分なデータがあるまでＶＭホストのキャッシュ８１３に記憶されてもよい。後でｖＤｉｓｋ内の同じ場所を上書きするための時間を与えるために、新しい書き込みデータをＶＭホスト上でさらに長時間バッファリングすることもでき、これにより、上書きされたデータをストライプに書き出す必要がなくなる。ＤＶＡｈコンポーネントの一部として、またはオペレーティングシステムなどの他のホストエンティティとして、ホストは、書き込みユニット（Write unit）のための少なくとも１つの消去訂正符号ブロック（erasure coded block）を計算し、次いで、それをストレージノードに書き込むこともできる。
【０１１７】
動作が読み込み（ＲＥＡＤ）である場合、所望のデータはキャッシュ８１３で参照される。データがキャッシュされている場合は、キャッシュから読み込まれ、ＶＭなどの要求プロセスに返される。データがキャッシュされていない場合は、（中間アドレスマップを使用して）ストレージノードから直接読み取られ、要求プロセスに返される。読み込み（ＲＥＡＤ）データはまた、キャッシュに書き込まれてもよい。
【０１１８】
管理および計算負荷をホストに集中させることによって、ストレージノードは、ストレージ側で専用のバックプレーンおよびファイバチャネル接続を必要とせずに、比較的簡単で安価に保つことができ、さらに、ストレージ側全体が、標準的なネットワーク接続を介して直接ホストと通信することができる。また、ホストがプールと通信するが、お互いにまれにしか通信しない場合、あるホストは別のホスト上のノイジーネイバー（noisy neighbor）に悩まされない。最後に、ホストに大きなキャッシュが含まれている場合、それらは、プールにおけるノードにまれにしか接続する必要がなく、「ノイジーネイバー問題(noisy neighbor problem)」をさらに低減する。ホストは、ＶＭおよびその中で実行されているアプリケーションにデータを提供する権限があり、システム内の他の場所でのパフォーマンスの問題の影響を受けにくい。
【０１１９】
本明細書で開示される様々な機能またはプロセスは、様々な不揮発性のコンピュータ可読媒体に具体化されたデータおよび／または命令として説明されてもよく、ＤＶＡシステムの実施形態を実装することを希望するコンピュータプログラム製品として提供することができる。
【０１２０】
図１０は、書き込み要求を処理する１つの実装を示す。書き込み要求が受信されると、その要求はノード上のＮＶＲＡＭモジュール１０３０に記録される。書き込みを記録するには、書き込み中のファイル内のファイルとオフセットの表示が含まれる。書き込みデータ自体が書き込みバッファに書き込まれ、要求が確認応答される。例えば、ブロックを形成するのに十分なほど、書き込みバッファが処理をトリガーするのに十分でない場合、処理はより多くの書き込み要求を受け取るために戻り、さもなければ、書き込まれたデータはブロックに形成され、１つ以上のフィンガープリントが（データセット全体に単一のフィンガープリントが使用されるか、ブロックごとに別々のフィンガープリントが使用されるかに応じて）計算される。フィンガープリント計算の前、後、または同時に、ブロックデータは、圧縮、暗号化などによって処理されてもよい。所与のブロックが、（フィンガープリント比較によって判定することができる）ホストキャッシュ内にすでにある場合、ファイルマップはブロックへの参照によって更新され、処理は追加の書き込みを受け取るために戻ることができる。ブロックのフィンガープリントがホストキャッシュまたはグローバルフィンガープリントインデックス１２２１に見つからない場合、ブロックは現在構築中のストライプに追加される。ストライプがまだ完了していない場合、システムは追加の書き込み要求を受け取るために戻ることができる。現在のストライプが完了すると、そのストライプのＥＣＣストライプ要素が計算され、格納のために分散される。ストライプ内のブロックのフィンガープリントは、次にグローバルフィンガープリントインデックス１２２１に追加される。そして、ブロックをキャッシュに追加することもでき、その後、ストライプに格納されているブロックを参照するようにファイルマップが更新される。この時点では、ホスト障害が発生しても書き込まれたデータは安全であり、ＮＶＲＡＭ内のデータの一時コピーは不要になる。したがって、例えばロギングモジュール１２２５を使用するホストは、データを切り捨ててＮＶＲＡＭから取り除く可能性があることをログ１０２５に伝えることができる。コントローラはＮＶＲＡＭに一時的に格納されているデータを、より永久的な場所に書き換える必要はないことに留意する。最後に、処理が戻り、追加の書き込みを受け取る。他の実施形態では、ＤＶＡｈコンポーネントは、フィンガープリントを計算し、ホストキャッシュおよび/またはグローバルフィンガープリントインデックス内のそのフィンガープリントの存在をチェックし、ファイル内の対応するファイルおよびオフセットについては、書き込みを確認する前に、データ自体の代わりに以前に保存されたデータへの新しいリファレンスのみをリモートＮＶＲＡＭに記録する。
【０１２１】
図１１は、読み取り要求を処理する１つの実装を示す。読み出し要求が受信され、データを含むブロックへのリファレンスが、要求されたオフセットを提供するファイルマップモジュールから検索される。参照されたブロックがキャッシュ８１３内にある場合、それは取り出され、読み出し要求を満たすためにデータを返すことができる。ブロックがキャッシュにない場合は、プールから取得しなければならない。これは、フィンガープリントインデックスからブロックロケータを検索することによって達成することができる。ブロックが取り出されると、ブロックがキャッシュに追加され、要求されたデータを返すことができる。
【０１２２】
ハードウェアの概要
一実施形態によれば、本明細書に記載の技術は、１つまたは複数の専用コンピューティングデバイス（special-purpose computing devices）によって実装される。専用コンピューティングデバイスは、本明細書に記載の技術を実行するために配線されていてもよいし、本明細書に記載の技術を実行するために永続的にプログラムされた、１つまたは複数の特定用途向け集積回路（ＡＳＩＣ）またはフィールドプログラマブルゲートアレイ（ＦＰＧＡ）のようなデジタル電子デバイスを含んでいてもよい。または、専用コンピューティングデバイスは、ファームウェア、メモリ、他の記憶装置、または組み合わせにおけるプログラム命令に従って本明細書に記載の技術を実行するようにプログラムされた１つまたは複数の汎用ハードウェアプロセッサを含むことができる。そのような専用コンピューティングデバイスは、特定用途向けのハードワイヤードロジック（hard-wired logic）、ＡＳＩＣ、またはＦＰＧＡをカスタムプログラミングと組み合わせて、本明細書に記載の技術を達成することもできる。専用コンピューティングデバイスは、デスクトップコンピュータシステム、ポータブルコンピュータシステム、ハンドヘルドデバイス、ネットワーキングデバイス、または本明細書に記載の技術を実装するためのハードワイヤードおよび/またはプログラムロジック（program logic）を組み込んだ他の任意のデバイスであってもよい。
【０１２３】
例えば、図１２は、実施形態を実装することができるコンピュータシステム１２００を示すブロック図である。コンピュータシステム１２００は、情報を通信するためのバス１２０２または他の通信機構と、情報を処理するためにバス１２０２に結合されたハードウェアプロセッサ１２０４とを含む。ハードウェアプロセッサ１２０４は、例えば、汎用マイクロプロセッサであってもよい。
【０１２４】
コンピュータシステム１２００はまた、プロセッサ１２０４によって実行される情報および命令を記憶するためにバス１２０２に結合されたランダムアクセスメモリ（ＲＡＭ）または他の動的記憶装置などのメインメモリ１２０６を含む。メインメモリ１２０６はまた、プロセッサ１２０４によって実行される命令の実行中に一時的変数または他の中間情報を記憶するために使用されてもよい。このような命令は、プロセッサ１２０４にアクセス可能な一時的でない記憶媒体に格納されたときに、コンピュータシステム１２００を命令で指定された動作を実行するようにカスタマイズされた専用マシンにレンダリングする。
【０１２５】
コンピュータシステム１２００はさらに、静的情報およびプロセッサ１２０４のための命令を格納するために、バス１２０２に結合された読み出し専用メモリ（ＲＯＭ）１２０８または他の静的記憶装置を含む。磁気ディスク、光ディスク、またはソリッドステートドライブなどの記憶装置１２１０が提供され、情報および命令を記憶するためにバス１２０２に接続される。コンピュータシステム１２００は、コンピュータユーザに情報を表示するために、バス１２０２を介して、陰極線管（ＣＲＴ）などのディスプレイ１２１２に結合されてもよい。英数字および他のキーを含む入力装置１２１４は、情報およびコマンド選択をプロセッサ１２０４に通信するためにバス１２０２に接続される。別のタイプのユーザ入力デバイスは、マウス、トラックボール、または方向情報およびコマンド選択をプロセッサ１２０４に通信し、ディスプレイ１２１２上のカーソル移動を制御するためのカーソル方向キーなどのカーソル制御１２１６である。この入力装置は、典型的には、装置が平面内の位置を指定することを可能にする第１の軸（例えば、ｘ）および第２の軸（例えば、ｙ）の２つの軸の２つの自由度を有する。
【０１２６】
コンピュータシステムと組み合わせて、コンピュータシステム１２００を専用マシンとするか、またはプログラムする、カスタマイズされたハードワイヤードロジック、1つ以上のＡＳＩＣまたはＦＰＧＡ、ファームウェアおよび/またはプログラムロジックを使用して、コンピュータシステム１２００は、本明細書に記載の技術を実装することができる。一実施形態によれば、本明細書の技術は、プロセッサ１２０４がメインメモリ１２０６に含まれる１つまたは複数の命令の１つまたは複数のシーケンスを実行することに応じて、コンピュータシステム１２００によって実行される。そのような命令は、記憶装置１２１０のような別の記憶媒体からメインメモリ１２０６に読み込まれてもよい。
メインメモリ１２０６に含まれる一連の命令を実行することにより、プロセッサ１２０４は、本明細書に記載の処理ステップを実行する。別の実施形態では、ハードウェア回路をソフトウェア命令の代わりに、またはソフトウェア命令と組み合わせて使用することができる。
【０１２７】
本明細書で使用される用語「記憶媒体（storage media）」は、機械を特定の様式で動作させるデータおよび/または命令を格納する任意の非一時的媒体を指す。そのような記憶媒体は、不揮発性媒体および/または揮発性媒体を含むことができる。不揮発性媒体は、例えば、光ディスク、磁気ディスク、または記憶装置１２１０などのソリッドステートドライブを含む。揮発性媒体は、メインメモリ１２０６などの動的メモリを含む。一般的な形式の記憶媒体には、例えば、フロッピーディスク、フレキシブルディスク、ハードディスク、ソリッドステートドライブ、磁気テープ、または任意の他の磁気データ記憶媒体、ＣＤ−ＲＯＭ、任意の他の光データ記憶媒体、穴のパターンを有する任意の物理媒体、ＲＡＭ、ＰＲＯＭ、およびＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、ＮＶＲＡＭ、その他のメモリチップまたはカートリッジを含む。
【０１２８】
記憶媒体は、伝送媒体（transmission media）とは区別されるが、伝送媒体と共に使用することができる。伝送媒体は、記憶媒体間で情報を転送するのに関与する。例えば、伝送媒体は、バス１２０２を含むワイヤを含む同軸ケーブル、銅線及び光ファイバを含む。伝送媒体は、電波および赤外線データ通信中に生成されるような音響波または光波の形態をとることもできる。
【０１２９】
１つまたは複数の命令の１つまたは複数のシーケンスを、実行のためにプロセッサ１２０４に運ぶことには、様々な形態の媒体が関与し得る。例えば、命令は、最初に、リモートコンピュータの磁気ディスクまたはソリッドステートドライブ上で搬送されてもよい。リモートコンピュータは、命令をそのダイナミックメモリにロードし、モデムを使用して電話回線を介して命令を送信することができる。コンピュータシステム１２００にローカルなモデムは、電話線上のデータを受信し、赤外線送信機を使用してデータを赤外線信号に変換することができる。赤外線検出器は、赤外線信号で搬送されるデータを受信することができ、適切な回路がバス１２０２にデータを置くことができる。バス１２０２は、メインメモリ１２０６にデータを搬送し、そこからプロセッサ１２０４が命令を取り出して実行する。メインメモリ１２０６によって受信された命令は、プロセッサ１２０４による実行の前または後のいずれかに、オプションで記憶装置１２１０に記憶されてもよい。
【０１３０】
コンピュータシステム１２００はまた、バス１２０２に接続された通信インターフェース１２１８を含む。通信インターフェース１２１８は、ローカルネットワーク１２２２に接続されたネットワークリンク１２２０に結合する双方向データ通信を提供する。例えば、通信インターフェース１２１８は、対応するタイプの電話回線にデータ通信接続を提供するために、統合サービスデジタルネットワーク（ＩＳＤＮ）カード、ケーブルモデム、衛星モデム、またはモデムであってもよい。別の例として、通信インターフェース１２１８は、互換性のあるＬＡＮへのデータ通信接続を提供するローカルエリアネットワーク（ＬＡＮ）カードであってもよい。無線リンクを実装することもできる。このような実装では、通信インターフェース１２１８は、様々なタイプの情報を表すデジタルデータストリームを搬送する電気信号、電磁信号、または光信号を送受信する。
【０１３１】
ネットワークリンク１２２０は、通常、１つまたは複数のネットワークを介して他のデータデバイスへのデータ通信を提供する。例えば、ネットワークリンク１２２０は、ローカルネットワーク１２２２を介して、ホストコンピュータ１２２４またはインターネットサービスプロバイダ（ＩＳＰ）１２２６によって操作されるデータ機器への接続を提供することができる。ＩＳＰ１２２６は、現在一般に「インターネット」１２２８と呼ばれるワールドワイドパケットデータ通信ネットワークを介してデータ通信サービスを提供する。ローカルネットワーク１２２２およびインターネット１２２８の両方は、デジタルデータストリームを搬送する電気信号、電磁気信号または光信号を使用する。様々なネットワークを通る信号、およびコンピュータシステム１２００との間でデジタルデータを搬送する通信リンク１２２０およびネットワークリンク１２２０上の信号は、伝送媒体の一形態である。
【０１３２】
コンピュータシステム１２００は、ネットワーク、ネットワークリンク１２２０、および通信インターフェース１２１８を介して、メッセージを送信し、プログラムコードを含むデータを受信することができる。インターネットの例では、サーバ１２３０は、インターネット１２２８、ＩＳＰ１２２６、ローカルネットワーク１２２２、および通信インターフェース１２１８を介して、アプリケーションプログラムの要求されたコードを送信することができる。
【０１３３】
受信されるコードは、それが受信されるときに、および/または、後の実行のために、記憶装置１２１０または他の不揮発性記憶装置に格納されるときに、プロセッサ１２０４によって実行されてもよい。
【０１３４】
前述の明細書では、本発明の実施形態を、実装ごとに異なる可能性のある、多数の具体的詳細を参照して説明してきた。したがって、明細書および図面は、限定的ではなく例示的なものとみなされるべきである。
本発明の範囲の唯一の排他的な指標、および本出願人が本発明の範囲であると意図するものは、本願から出された一連の請求項における文字通りの範囲および均等な範囲であり、そのような請求項が生じさせる特定の形態（後続の修正を含む）である。
【図１】
2018073406.tif 000003
【図２】
2018073406.tif 000004
【図３】
2018073406.tif 000005
【図４】
2018073406.tif 000006
【図５】
2018073406.tif 000007
【図６】
2018073406.tif 000008
【図７】
2018073406.tif 000009
【図８】
2018073406.tif 000010
【図９】
2018073406.tif 000011
【図１０】
2018073406.tif 000012
【図１１】
2018073406.tif 000013
【図１２】
2018073406.tif 000014
【手続補正書】
【提出日】平成29年10月19日(2017.10.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ファイルシステムによって使用される記憶領域に記憶されたライブクランプをコピー転送する方法において、
記憶領域識別フェーズ中に、複数のコンテナ識別ワーカーを実行して、ライブクランプリファレンスのセットに対応するクランプを含む記憶領域のセットを識別するステップであって、
前記ライブクランプリファレンスは、前記ファイルシステム内のライブオブジェクトに属するクランプへの参照であり、
前記複数のコンテナ識別ワーカーは、互いに独立して実行され、
各コンテナ識別ワーカーは、前記ライブクランプリファレンスのセットに対応するクランプを含む１つまたは複数の記憶領域を識別する、ステップと、
前記記憶領域識別フェーズの後に行われるコピー転送フェーズ中に、複数のコピー転送タスクワーカーを実行して、前記記憶領域のセットに対してコピー転送操作を実行するステップであって、
前記複数のコピー転送タスクワーカーは、互いに独立して実行され、
各コピー転送タスクワーカーは、前記記憶領域のセットから記憶領域のサブセットを割り当てられ、前記コピー転送タスクワーカーが割り当てられた前記記憶領域のサブセットに対してコピー転送操作を実行する、ステップと
を含むことを特徴とする方法。
【請求項２】
前記記憶領域識別フェーズの前に行われるライブクランプリファレンス識別フェーズ中に、１つまたは複数のライブクランプ識別ワーカーを実行して、ライブクランプリファレンスのセットを識別するステップをさらに含み、
前記１つまたは複数のライブクランプ識別ワーカーは、互いに独立して実行され、
前記１つまたは複数のライブクランプ識別ワーカーの各々は、前記ファイルシステム内のライブオブジェクトに属するクランプについての１つまたは複数のライブクランプリファレンスを識別すること
を特徴とする請求項１に記載の方法。
【請求項３】
前記ファイルシステム内の前記ライブオブジェクトに属する前記クランプは、前記コピー転送操作が実行される記憶領域を含む、記憶領域の候補セット内に記憶され、
前記記憶領域の候補セット内のクランプは、永続性ストレージにフラッシュされ、ライブクランプリファレンスのためのマッピングが前記ファイルシステム内のメタデータ内に生成されていること
を特徴とする請求項２に記載の方法。
【請求項４】
前記ライブクランプリファレンス識別フェーズの前に行われるライブオブジェクト識別フェーズ中に、ライブオブジェクトのセットを識別するために、１つまたは複数のライブオブジェクト識別ワーカーを実行するステップを含み、
前記１つまたは複数のライブオブジェクト識別ワーカーは、互いに独立して実行され、  前記１つまたは複数のライブオブジェクト識別ワーカーの各々は、前記ファイルシステムにおけるネームスペースメタデータに基づいて、前記ファイルシステム内の１つまたは複数のライブオブジェクトを識別すること
を特徴とする請求項３に記載の方法。
【請求項５】
前記記憶領域識別フェーズの後で前記コピー転送フェーズの前に行われる記憶領域スコアリングフェーズ中に、
前記記憶領域内のライブクランプの予想ライフタイム値、前記記憶領域内の前記ライブクランプの総数、または前記ライブクランプの総サイズのうち、少なくとも１つの記憶領域属性に基づいて、前記記憶領域のセット内の各記憶領域に優先度スコアを割り当てるために、複数の記憶領域スコアリングタスクワーカーを実行するステップを含み、
前記複数の記憶領域スコアリングタスクワーカーは、互いに独立して実行されること
を特徴とする請求項１に記載の方法。
【請求項６】
各コピー転送タスクワーカーによって実行される前記コピー転送操作は、
前記コピー転送タスクワーカーが割り当てられた前記記憶領域のサブセット内にある前記ライブクランプリファレンスのセット内のライブクランプリファレンスに対応する前記ライブクランプを、新しい記憶領域にコピーするステップと、
前記ライブクランプを前記新しい記憶領域にコピーするステップの完了時に、前記コピー転送タスクワーカーが割り当てられた前記記憶領域のサブセットを削除するステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記複数のコピー転送タスクワーカーの少なくとも２つが、並行して実行されること
を特徴とする請求項１に記載の方法。
【請求項８】
前記複数のコンテナ識別ワーカーの少なくとも２つが、並行して実行されること
を特徴とする請求項１に記載の方法。
【請求項９】
ファイルシステムによって使用される記憶領域に記憶されたライブクランプをコピー転送する方法において、
第１フェーズ中に、１つまたは複数の第１フェーズタスクワーカーは、
前記ファイルシステム内のライブオブジェクトを識別するステップと、
前記ライブオブジェクトの識別子に基づいて１つまたは複数の第２フェーズタスクワーカーに作業を配布するステップと
を実行し、
第２フェーズタスクワーカーは、
第１フェーズタスクワーカーによって識別されたライブオブジェクトのライブクランプリファレンスを識別するステップと、
前記ライブクランプリファレンスの値に基づいて１つまたは複数の第３フェーズタスクワーカーに作業を配布するステップと、
を実行し、
第３のフェーズタスクワーカーは、
第２のフェーズタスクワーカーによって識別された前記ライブクランプリファレンスに対応する記憶領域を決定するステップと、
前記ライブクランプリファレンスが属する前記記憶領域に基づいて、１つまたは複数のコピー転送タスクワーカーに作業を配布するステップと
を実行することを特徴とする方法。
【請求項１０】
前記ファイルシステム内の前記ライブオブジェクトを識別するステップは、さらに、
記憶領域の候補セットの一部である記憶領域間を、前記記憶領域の候補セットの一部ではない他の記憶領域から、線引きする候補セット境界を生成することによって、前記記憶領域の候補セットに属する記憶領域を決定するステップを含み、
前記記憶領域の候補セットは、前記ファイルシステム内の前記ライブオブジェクトに属する前記ライブクランプを含み、
前記候補セット境界は、依然として書き込み要求を受け取ることができる記憶領域の第１セットと、もはや書き込み要求を受け取らない記憶領域の第２セットとに、記憶領域を分割し、
前記記憶領域の第２セットは前記記憶領域の候補セットに属すること
を特徴とする請求項９に記載の方法。
【請求項１１】
前記記憶領域の前記候補セットは、永続性ストレージにフラッシュされたクランプを含み、前記ライブクランプリファレンスは、前記ファイルシステム内のメタデータ内で生成されていること
を特徴とする請求項１０に記載の方法。
【請求項１２】
前記ライブクランプリファレンスの値に基づいて前記第３フェーズタスクワーカーに作業を配布するステップは、前記第３のフェーズタスクワーカーの各第３のフェーズタスクワーカーに、ライブクランプリファレンスの連続した範囲内にあるライブクランプリファレンスのサブセットを割り当てるステップを含むこと
を特徴とする請求項９に記載の方法。
【請求項１３】
前記コピー転送タスクワーカーに作業を配布するステップは、
前記ライブクランプリファレンスと前記記憶領域との間の記憶領域対ライブクランプマッピングを生成するステップであって、
前記記憶領域対ライブクランプマッピングが前記記憶領域に基づいてソートされるように、前記記憶領域対ライブクランプマッピングが前記記憶領域を前記ライブクランプリファレンスにマップする、ステップと、
前記記憶領域に基づいて前記記憶領域対ライブクランプマッピングをソートするステップと、
前記記憶領域と前記記憶領域対ライブクランプマッピングに基づいて、前記コピー転送タスクワーカーに作業を配布するステップと
を含むことを特徴とする請求項９に記載の方法。
【請求項１４】
前記コピー転送タスクワーカーに作業を配布するステップは、さらに、各記憶領域に対して計算された優先度スコアに基づいており、
前記優先度スコアは、前記記憶領域内のライブクランプリファレンスの予想ライフタイム値、前記記憶領域内のライブクランプリファレンスの総数、および前記ライブクランプリファレンスの総サイズのうち、少なくとも１つの記憶領域属性に基づいていること
を特徴とする請求項１３に記載の方法。
【請求項１５】
実行時に、請求項１から１４のいずれか１項に記載の方法を行う命令を格納したこと
を特徴とする非一時的なコンピュータ可読媒体。
【請求項１６】
コンピュータシステムであって、
１つまたは複数のプロセッサ、メモリ、および１つまたは複数のストレージ装置を備え、前記１つまたは複数のプロセッサは、前記メモリ内の命令を実行して、前記コンピュータシステムに請求項１から１４のいずれか１項に記載の方法を実行させること
を特徴とするコンピュータシステム。