(57)【特許請求の範囲】
【請求項１】
重複排除マネージャを含んだソフトウェアコンポーネントを実行する第１のシステムとファイルシステムを管理するファイルシステム・マネージャを含んだ第２のシステムとを備えるファイルサーバにデータ重複排除方法を実行させるコンピュータプログラムであって、
前記データ重複排除方法が、
前記第１のシステムにより、ファイルシステムに関するデータの複数のデータユニットの中から、重複排除候補のデータユニットである候補ユニットを特定し、
前記第１のシステムにより、前記特定された候補ユニットのハッシュ値を送信することを前記第２のシステムに要求し、
前記第２のシステムにより、前記特定された候補ユニットのハッシュ値を前記第１のシステムに返し、
前記特定された候補ユニットがインデックス付きデータユニットと重複することが前記返されたハッシュ値に基づき判断される場合、前記第１のシステムにより、前記特定された候補ユニットの重複排除を前記第２のシステムに要求する、
ことを含む、
コンピュータプログラム。
【請求項２】
前記データ重複排除方法が、更に、
前記第１のシステムにより、前記ファイルシステムのスナップショットコピーを行い、
前記第１のシステムにより、前記第２のシステムにより管理される複数のチェックポイントであり前記ファイルシステムの複数のチェックポイントのうちから、重複排除のためのチェックポイント範囲を決定する、
ことを含み、
前記候補ユニットの特定が、前記決定されたチェックポイント範囲に基づき前記スナップショットコピーにおいて行われる、
請求項１記載のコンピュータプログラム。
【請求項３】
前記データ重複排除方法が、更に、
前記候補ユニットが前記インデックス付きデータユニットにマッチする場合、前記第１のシステムにより、前記インデックス付きデータユニットのメタデータを提供し、
前記第２のシステムにより、前記提供されたメタデータに基づき前記インデックス付きデータユニットを用いて前記ファイルシステムにおいて前記候補ユニットが重複排除されることが可能かどうか検証する、
ことを含む、
請求項１又は２記載のコンピュータプログラム。
【請求項４】
前記データ重複排除方法が、更に、
前記ファイルシステムにおいて前記候補ユニットが重複排除されることが可能であると判断される場合、前記第２のシステムにより、前記候補ユニットに関連付けられたポインタの各々を、前記インデックス付きデータユニットに関連付けられた対応するポインタに置き換える
ことを含む、
請求項１乃至３のうちのいずれか１項に記載のコンピュータプログラム。
【請求項５】
前記候補ユニットは、ファイルシステムオブジェクトからの単一又は複数のファイルシステムブロックを包含する、
請求項１乃至４のうちのいずれか１項に記載のコンピュータプログラム。
【請求項６】
前記ファイルシステムにおいて前記候補ユニットが重複排除されることが可能かどうか検証することは、前記候補ユニットに関連付けられたチェックポイント番号および前記インデックス付きデータユニットに関連付けられたチェックポイント番号に少なくとも部分的に基づいている、
請求項３記載のコンピュータプログラム。
【請求項７】
前記ファイルシステムにおいて前記候補ユニットが重複排除されることが可能かどうか検証することは、前記インデックス付きデータユニットのブロックに関連付けられた参照カウントに少なくとも部分的に基づいている、
請求項３記載のコンピュータプログラム。
【請求項８】
前記候補ユニットに関連付けられたポインタの各々を、前記インデックス付きデータユニットに関連付けられた対応するポインタで置き換えることは、対応する各ポインタに関連付けられた参照カウントを増加させることを含む、
請求項４記載のコンピュータプログラム。
【請求項９】
前記候補ユニットを特定することは、
ファイルシステムオブジェクトのルートノード内の作成チェックポイントを調べることと、
前記作成チェックポイントに少なくとも部分的に基づいて、前記ファイルシステムオブジェクトがいずれかの候補ユニットを含むかどうか判断することと
を含む、
請求項１乃至８のうちのいずれか１項に記載のコンピュータプログラム。
【請求項１０】
前記ファイルシステムオブジェクトがいずれかの候補ユニットを含むかどうか判断することは、
前記作成チェックポイントがチェックポイント範囲内にあって、かつ前記ファイルシステムオブジェクトがクローンオブジェクトではない場合に、前記ファイルシステムオブジェクトに関連付けられたデータユニットはすべて候補ユニットであると判断することと、
前記作成チェックポイントが前記チェックポイント範囲内にあって、かつ前記ファイルシステムオブジェクトがクローンオブジェクトである場合に、前記ファイルシステムオブジェクトのクローン元のオブジェクトから分岐したデータユニットをいずれも特定するために、オブジェクトツリー構造をトラバースすることと、
前記作成チェックポイントが前記チェックポイント範囲外にある場合に、前記チェックポイント範囲内にある変更チェックポイントを持つデータユニットをいずれも特定するために、オブジェクトツリー構造をトラバースすることと
を含む、
請求項９記載のコンピュータプログラム。
【請求項１１】
前記ファイルシステムオブジェクトがいずれかの候補ユニットを含むかどうか判断することは、
前記作成チェックポイントがチェックポイント範囲内にあって、かつ前記ファイルシステムオブジェクトがクローンオブジェクトではなく、かつ前記ファイルシステムオブジェクトが疎なオブジェクトではない場合に、前記ファイルシステムオブジェクトに関連付けられたデータユニットはすべて候補ユニットであると判断することと、
前記作成チェックポイントが前記チェックポイント範囲内にあって、かつ前記ファイルシステムオブジェクトがクローンオブジェクトではなく、かつ前記ファイルシステムオブジェクトが疎なオブジェクトである場合に、疎ではない候補ユニットをいずれも特定するためにオブジェクトツリー構造をトラバースすることと、
前記作成チェックポイントが前記チェックポイント範囲内にあって、かつ前記ファイルシステムオブジェクトがクローンオブジェクトである場合に、前記ファイルシステムオブジェクトのクローン元のオブジェクトから分岐した候補ユニットをいずれも特定するためにオブジェクトツリー構造をトラバースすることと、
前記作成チェックポイントが前記チェックポイント範囲外にある場合に、前記チェックポイント範囲内にある変更チェックポイントを持つ候補ユニットをいずれも特定するためにオブジェクトツリー構造をトラバースすることと
を含む、
請求項９記載のコンピュータプログラム。
【請求項１２】
前記データ重複排除方法が、更に、
前記候補ユニットが前記インデックス付きデータユニットにマッチする場合、前記第１のシステムにより、前記インデックス付きデータユニットのメタデータを提供し、
重複排除のために前記インデックス付きデータユニットを使用できないと判断される場合に、前記候補ユニットに関連付けられた前記ハッシュ値および前記メタデータに基づいて、前記候補ユニットをインデキシングすること
を含む、
請求項１乃至１１のうちのいずれか１項に記載のコンピュータプログラム。
【請求項１３】
重複排除マネージャを含んだソフトウェアコンポーネントを実行する第１のシステムとファイルシステムを管理するファイルシステム・マネージャを含んだ第２のシステムとを備えるファイルサーバを有するデータストレージシステムにおけるデータ重複排除方法であって、
前記第１のシステムにより、ファイルシステムに関するデータの複数のデータユニットの中から、重複排除候補のデータユニットである候補ユニットを特定し、
前記第１のシステムにより、前記特定された候補ユニットのハッシュ値を送信することを前記第２のシステムに要求し、
前記第２のシステムにより、前記特定された候補ユニットのハッシュ値を前記第１のシステムに返し、
前記特定された候補ユニットがインデックス付きデータユニットと重複することが前記返されたハッシュ値に基づき判断される場合、前記第１のシステムにより、前記特定された候補ユニットの重複排除を前記第２のシステムに要求する、
ことを含む、
データ重複排除方法。
【請求項１４】
重複排除マネージャを含んだソフトウェアコンポーネントを実行する第１のシステムと、
ファイルシステムを管理するファイルシステム・マネージャを含んだ第２のシステムとを備え、
前記第１のシステムが、ファイルシステムに関するデータの複数のデータユニットの中から、重複排除候補のデータユニットである候補ユニットを特定し、
前記第１のシステムが、前記特定された候補ユニットのハッシュ値を送信することを前記第２のシステムに要求し、
前記第２のシステムが、前記特定された候補ユニットのハッシュ値を前記第１のシステムに返し、
前記特定された候補ユニットがインデックス付きデータユニットと重複することが前記返されたハッシュ値に基づき判断される場合、前記第１のシステムが、前記特定された候補ユニットの重複排除を前記第２のシステムに要求する、
ファイルサーバ。
【請求項１５】
１以上のファイルサーバと、
前記１以上のファイルサーバと通信可能に接続された複数のクライアント計算機と
を備え、
前記１以上のファイルサーバの各々が、
重複排除マネージャを含んだソフトウェアコンポーネントを実行する第１のシステムと、
ファイルシステムを管理するファイルシステム・マネージャを含んだ第２のシステムとを備え、
前記第１のシステムが、ファイルシステムに関するデータの複数のデータユニットの中から、重複排除候補のデータユニットである候補ユニットを特定し、
前記第１のシステムが、前記特定された候補ユニットのハッシュ値を送信することを前記第２のシステムに要求し、
前記第２のシステムが、前記特定された候補ユニットのハッシュ値を前記第１のシステムに返し、
前記特定された候補ユニットがインデックス付きデータユニットと重複することが前記返されたハッシュ値に基づき判断される場合、前記第１のシステムが、前記特定された候補ユニットの重複排除を前記第２のシステムに要求する、
データストレージシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、ファイルストレージシステムに関し、より具体的には、ファイルストレージシステムにおける重複排除に関する。
【背景技術】
【０００２】
重複排除は、ストレージ利用の向上のための機構である。それは、主に、データストレージシステムにおいてデータの重複チャンクを特定することと、そのデータの単一コピーのみを、その単一コピーへの参照と共に維持して、重複を解消することと、を伴う。特に、重複排除によって、例えばディスクおよび／またはソリッドステートストレージにおいて、データの保存に必要な容量が削減される。
【発明の概要】
【課題を解決するための手段】
【０００３】
第１の例示的な実施形態において、ライブファイルシステムが稼働しているファイルストレージシステムにおいてデータの重複排除を実行する方法を提供し、該ファイルストレージシステムは、ソフトウェアベースのシステムとハードウェアベースのシステムとを有し、ソフトウェアベースのシステムは、重複排除検出／インデキシング・エンジンと相互通信可能に構成されたソフトウェアベースの重複排除マネージャを含み、ハードウェアベースのシステムは、ハードウェアベースのファイルシステム・マネージャとハッシュ生成器とを含み、ライブファイルシステムは、一連のチェックポイントによって区切られる。該方法は、ソフトウェアベースの重複排除マネージャによりファイルシステムのスナップショットコピーを作成することと、重複排除のためのチェックポイント範囲をソフトウェアベースの重複排除マネージャにより決定することと、ソフトウェアベースの重複排除マネージャにより該チェックポイント範囲に基づいてスナップショットコピーにおける候補チャンクを特定することと、ソフトウェアベースの重複排除マネージャによりハードウェアベースのファイルシステム・マネージャに対してハッシュ生成器を用いた候補チャンクのハッシュ化を要求することと、ハードウェアベースのファイルシステム・マネージャによりソフトウェアベースの重複排除マネージャに対して候補チャンクのハッシュ値およびチャンク・メタデータを返すことと、ソフトウェアベースの重複排除マネージャにより重複排除検出／インデキシング・エンジンに対して候補チャンクのハッシュ値を送ることと、候補チャンクがインデックス付きチャンクとマッチした場合にソフトウェアベースの重複排除マネージャによって重複排除検出／インデキシング・エンジンから該インデックス付きチャンクのチャンク・メタデータを受信することと、ソフトウェアベースの重複排除マネージャによりハードウェアベースのファイルシステム・マネージャに対してインデックス付きチャンクのチャンク・メタデータに基づいた候補チャンク重複排除を要求することと、ハードウェアベースのファイルシステム・マネージャによりチャンク・メタデータに基づいてライブファイルシステムにおいてインデックス付きチャンクを用いた候補チャンクの重複排除が可能かどうか検証することと、ライブファイルシステムにおいてインデックス付きチャンクを用いた候補チャンクの重複排除が可能であると判断される場合に、候補チャンクに関連付けられたポインタの各々を、インデックス付きチャンクに関連付けられた対応するポインタで置き換えることと、を含む。
【０００４】
第２の例示的な実施形態において、一連のチェックポイントで区切られるライブファイルシステムが稼働しているファイルストレージシステムを提供する。該ファイルストレージシステムは、重複排除検出／インデキシング・エンジンとインタフェースするように構成されたソフトウェアベースの重複排除マネージャを含むソフトウェアベースのシステムと、ハードウェアベースのファイルシステム・マネージャおよびハッシュ生成器を含むハードウェアベースのシステムと、を有する。ソフトウェアベースの重複排除マネージャは、（１）ファイルシステムのスナップショットコピーを作成し、（２）重複排除のためのチェックポイント範囲を決定し、（３）該チェックポイント範囲に基づいて、スナップショットコピーにおいて候補チャンクを特定し、（４）ハードウェアベースのファイルシステム・マネージャによるハッシュ生成器を用いた候補チャンクのハッシュ化を要求し、ハードウェアベースのファイルシステム・マネージャによりソフトウェアベースの重複排除マネージャに対して候補チャンクのハッシュ値およびチャンク・メタデータが返され、（５）重複排除検出／インデキシング・エンジンに対して候補チャンクのハッシュ値を送り、候補チャンクがインデックス付きチャンクとマッチした場合に重複排除検出／インデキシング・エンジンから該インデックス付きチャンクのチャンク・メタデータを受信し、（６）ハードウェアベースのファイルシステム・マネージャによるインデックス付きチャンクのチャンク・メタデータに基づいた候補チャンクの重複排除を要求する、ように構成されている。ハードウェアベースのファイルシステム・マネージャは、（１）チャンク・メタデータに基づいて、ライブファイルシステムにおいてインデックス付きチャンクを用いた候補チャンクの重複排除が可能かどうか検証し、（２）ライブファイルシステムにおいてインデックス付きチャンクを用いた候補チャンクの重複排除が可能であると判断される場合に、候補チャンクに関連付けられたポインタの各々を、インデックス付きチャンクに関連付けられた対応するポインタで置き換える、ように構成されている。
【０００５】
いくつかの代替的実施形態において、候補チャンクは、所与のファイルシステムオブジェクトからの単一のファイルシステムブロックを包含することができ、または所与のファイルシステムオブジェクトからの複数のファイルシステムブロックを包含することができる。
【０００６】
いくつかの代替的実施形態において、ライブファイルシステムにおいて候補チャンクの重複排除が可能かどうか検証することは、候補チャンクに関連付けられたチェックポイント番号およびインデックス付きチャンクに関連付けられたチェックポイント番号に少なくとも部分的に基づくことができ、および／またはインデックス付きチャンクのブロックに関連付けられた参照カウントに少なくとも部分的に基づくことができる。
【０００７】
いくつかの代替的実施形態において、候補チャンクに関連付けられたポインタの各々を、インデックス付きチャンクに関連付けられた対応するポインタで置き換えることは、対応する各ポインタに関連付けられた参照カウントを増加させることを含み得る。
【０００８】
いくつかの代替的実施形態において、チェックポイント範囲に基づいてスナップショットコピーにおいて候補チャンクを特定することは、ファイルシステムオブジェクトのルートノード内の作成チェックポイントを調べることと、その作成チェックポイントに少なくとも部分的に基づいて該ファイルシステムオブジェクトがいずれかの候補チャンクを含むかどうか判断することと、を含み得る。ファイルシステムオブジェクトがいずれかの候補チャンクを含むかどうか判断することは、その作成チェックポイントが該チェックポイント範囲内にあって、かつそのファイルシステムオブジェクトがクローンオブジェクトではない場合に、そのファイルシステムオブジェクトに関連付けられたチャンクはすべて候補チャンクであると判断することと、その作成チェックポイントが該チェックポイント範囲内にあって、かつそのファイルシステムオブジェクトがクローンオブジェクトである場合に、そのファイルシステムオブジェクトのクローン元のオブジェクトから分岐したチャンクをいずれも特定するためにオブジェクトツリー構造をトラバースすることと、その作成チェックポイントが該チェックポイント範囲外にある場合に、該チェックポイント範囲内にある変更チェックポイントを持つチャンクをいずれも特定するためにオブジェクトツリー構造をトラバースすることと、を含み得る。あるいは、ファイルシステムオブジェクトがいずれかの候補チャンクを含むかどうか判断することは、その作成チェックポイントが該チェックポイント範囲内にあって、かつそのファイルシステムオブジェクトがクローンオブジェクトではなく、かつそのファイルシステムオブジェクトが疎なオブジェクトではない場合に、そのファイルシステムオブジェクトに関連付けられたチャンクはすべて候補チャンクであると判断することと、その作成チェックポイントが該チェックポイント範囲内にあって、かつそのファイルシステムオブジェクトがクローンオブジェクトではなく、かつそのファイルシステムオブジェクトが疎なオブジェクトである場合に、疎ではない候補チャンクをいずれも特定するためにオブジェクトツリー構造をトラバースすることと、その作成チェックポイントが該チェックポイント範囲内にあって、かつそのファイルシステムオブジェクトがクローンオブジェクトである場合に、そのファイルシステムオブジェクトのクローン元のオブジェクトから分岐した候補チャンクをいずれも特定するためにオブジェクトツリー構造をトラバースすることと、その作成チェックポイントが該チェックポイント範囲外にある場合に、該チェックポイント範囲内にある変更チェックポイントを持つ候補チャンクをいずれも特定するためにオブジェクトツリー構造をトラバースすることと、含み得る。
【０００９】
上記実施形態のいずれかにおいて、重複排除のためにインデックス付きチャンクを使用できないと判断される場合に、その候補チャンクは、候補チャンクに関連付けられたハッシュ値およびチャンク・メタデータに基づいてインデキシングされることができる。
【００１０】
別の例示的な実施形態において、一連のチェックポイントで区切られるライブファイルシステムが稼働しているファイルストレージシステムにおいてデータの重複排除を実行するためのコンピュータプログラムがその中で具現化された、有形の非一時的コンピュータ読取り可能な媒体を備える装置を提供し、該コンピュータプログラムは、ファイルストレージシステムのコンピュータプロセッサ上で実行されることで、ファイルシステムのスナップショットコピーを作成することと、重複排除のためのチェックポイント範囲を決定することと、該チェックポイント範囲に基づいてスナップショットコピーにおいて候補チャンクを特定することと、ハードウェアベースのファイルシステム・マネージャに対して候補チャンクのハッシュ化の要求を送信することと、ハードウェアベースのファイルシステム・マネージャから候補チャンクのハッシュ値およびチャンク・メタデータを受信することと、ハッシュ値に基づいて候補チャンクがインデックス付きチャンクの重複であるかどうか判断することと、候補チャンクがインデックス付きチャンクの重複であると判断される場合に、候補チャンクの重複排除のための要求であって、該インデックス付きチャンクのチャンク・メタデータを含む要求を、ハードウェアベースのファイルシステム・マネージャに対して送信することと、を含むプロセスをコンピュータプロセッサに実行させるための命令を含む。
【００１１】
さらに別の例示的な実施形態において、一連のチェックポイントで区切られるライブファイルシステムが稼働しているファイルストレージシステムにおいてデータの重複排除を実行するための装置を提供し、該装置は、ハッシュ生成器と、ハードウェアベースのファイルシステム・マネージャと、を備え、ハードウェアベースのファイルシステム・マネージャは、候補チャンクのハッシュ化の要求をソフトウェアベースの重複排除マネージャから受信し、該候補チャンクに関連付けられたチェックポイント番号に基づいて候補チャンクをハッシュ化すべきかどうか判断し、候補チャンクをハッシュ化すべきと判断される場合には、該チャンクをハッシュ化するためにハッシュ生成器を起動し、候補チャンクのハッシュ値およびチャンク・メタデータをソフトウェアベースの重複排除マネージャに返し、候補チャンクの重複排除の要求をソフトウェアベースの重複排除マネージャから受信し、ライブファイルシステムにおいてインデックス付きチャンクに基づいた候補チャンクの重複排除が可能かどうか検証し、ライブファイルシステムにおいてインデックス付きチャンクを用いた候補チャンクの重複排除が可能であると判断される場合に、候補チャンクに関連付けられたポインタの各々を、インデックス付きチャンクに関連付けられた対応するポインタで置き換える、ように構成されている。
【００１２】
さらに別の例示的な実施形態では、複数のファイルシステムオブジェクトを含むライブファイルシステムを有するファイルストレージシステムにおいて重複排除のための候補チャンクを特定する方法を提供し、ライブファイルシステムは、一連のチェックポイントで区切られるものであり、重複排除は、所定のチェックポイント範囲に関するものである。該方法は、ファイルシステムオブジェクトのルートノード内の作成チェックポイントを調べることと、その作成チェックポイントに少なくとも部分的に基づいて該ファイルシステムオブジェクトがいずれかの候補チャンクを含むかどうか判断することと、を含み、該ファイルシステムオブジェクトがいずれかの候補チャンクを含むかどうか判断することは、その作成チェックポイントがチェックポイント範囲内にあって、かつ該ファイルシステムオブジェクトがクローンオブジェクトではなく、かつ該ファイルシステムオブジェクトが疎なオブジェクトではない場合に、該ファイルシステムオブジェクトに関連付けられたチャンクはすべて候補チャンクであると判断することと、その作成チェックポイントがチェックポイント範囲内にあって、かつ該ファイルシステムオブジェクトがクローンオブジェクトではなく、かつ該ファイルシステムオブジェクトが疎なオブジェクトである場合に、疎ではない候補チャンクをいずれも特定するためにオブジェクトツリー構造をトラバースすることと、その作成チェックポイントがチェックポイント範囲内にあって、かつ該ファイルシステムオブジェクトがクローンオブジェクトである場合に、該ファイルシステムオブジェクトのクローン元のオブジェクトから分岐した候補チャンクをいずれも特定するためにオブジェクトツリー構造をトラバースすることと、その作成チェックポイントがチェックポイント範囲外にある場合に、チェックポイント範囲内にある変更チェックポイントを持つ候補チャンクをいずれも特定するためにオブジェクトツリー構造をトラバースすることと、を含む。
【００１３】
さらなる実施形態が、開示され、特許請求され得る。
【００１４】
上記の実施形態の特徴は、添付の図面を共に参照して、以下の詳細な説明を参照することで、より容易に理解されるであろう。
【図面の簡単な説明】
【００１５】
【図１】図１は、本発明の例示的な実施形態によるファイルストレージシステムの概略ブロック図である。
【図２】図２は、そのような例示的な実施形態によるソフトウェア／ハードウェア・アーキテクチャの概略図である。
【図３】図３は、本発明の例示的な実施形態によるオブジェクトツリー構造の一般形式を示す概略ブロック図である。
【図４】図４は、例示的な一実施形態によるソフトウェアベースの重複排除マネージャのコンポーネントを示す概略図である。
【図５】図５は、本発明のいくつかの例示的な実施形態による重複排除についての概略論理フロー図である。
【図６】図６は、例示的な一実施形態により候補チャンクを特定する場合の論理フロー図である。
【発明を実施するための形態】
【００１６】
上記の図面および図中に示す要素は、必ずしも一貫した縮尺またはいずれかの縮尺で描かれたものではないことに留意すべきである。文脈上別段の示唆がない限り、類似の要素は同様の符号で示している。
【００１７】
本明細書および添付の請求項で使用される場合の以下の用語は、文脈上別段の解釈を要する場合を除き、以下に示す意味を持つものとする。
【００１８】
「ストレージデバイス」は、データを保存するために使用されるデバイスまたはシステムである。ストレージデバイスは、１つ以上の磁気もしくは光磁気もしくは光ディスクドライブ、ソリッドステートストレージデバイス、または磁気テープを含み得る。便宜上、ストレージデバイスは、「ディスク」または「ハードディスク」と呼ばれることがある。データストレージシステムは、同じまたは異なるストレージ容量を有する同じまたは異なるタイプのストレージデバイスを含み得る。
【００１９】
「ＲＡＩＤコントローラ」は、複数のストレージデバイスのストレージ容量を統合して、「システムドライブ」（「ＳＤ」）、「論理ユニット」（「ＬＵ」もしくは「ＬＵＮ」）、または「ボリューム」と別称することができる仮想ストレージ空間にするデバイスまたはシステムである。一般に、ＳＤは、複数のストレージデバイスからの空間が集められて、単一のストレージデバイスよりも容量が大きく、また、いくつかのディスクの障害にもデータ損失なく耐え得るように冗長な情報を含んでいる。例示的な実施形態では、各ＳＤには、以下で「論理ユニット識別子」または「ＬＵＩＤ」と呼ぶ固有識別子が関連付けられており、また、各ＳＤは、例えば２ＴＢ〜６４ＴＢまたはさらに大きい所定の最大容量を超えない大きさである。ＳＤにコマンドが送られると、ＲＡＩＤコントローラは、一般に、それらのコマンドを、そのＳＤのすべてのストレージデバイスに同時に転送する。ＲＡＩＤコントローラは、一般的なストレージデバイスにおける主な制限のうちの３つ、すなわち、ストレージデバイスは一般にストレージシステムにおける最も低速の構成要素であることと、それらは一般に破局故障を引き起こす可能性が最も高いことと、それらは一般にストレージ容量が比較的小さいことについて、その克服を助ける。
【００２０】
「ＲＡＩＤシステム」は、１つ以上のＲＡＩＤコントローラと複数のストレージデバイスとを含むデバイスまたはシステムである。一般に、ＲＡＩＤシステムは、２つのＲＡＩＤコントローラ（他方に障害が発生した場合でも一方によって動作が維持され得るように、また、両方が正常であるときに負荷を分担するため）と、数十個のストレージデバイスと、を含む。例示的な実施形態では、ＲＡＩＤシステムは、一般に、２〜３２個のＳＤで構成される。ファイルサーバは、データを保存または取得する必要があるときには、ＲＡＩＤシステムのＲＡＩＤコントローラにコマンドを送り、そしてこれが、そこから個々のストレージデバイスへのコマンドのルーティング、ならびに必要に応じてデータの保存または取得を担う。一部のＲＡＩＤシステムでは、あるＳＤ（「プライマリＳＤ」と呼ばれる）に書き込まれたデータが、冗長目的で、ＲＡＩＤシステムによって別のＳＤ（本明細書では「セカンダリＳＤ」または「ミラーＳＤ」と呼ぶ）に自動的に書き込まれるように、ＳＤ間にミラー関係を確立することができる。セカンダリＳＤは、プライマリＳＤと同じＲＡＩＤシステムによって、または別のローカルもしくはリモートＲＡＩＤシステムによって、管理されることができる。ＳＤを効果的にミラーリングすることによって、いくつかの状況において、ＳＤの損失または破損からの、さらに場合によっては複数のＳＤの損失または破損からの、リカバリを提供するための、ＲＡＩＤ１＋０機能がＳＤの間で得られる。
【００２１】
「ファイルシステム」は、ファイルストレージシステムに保存されたファイルおよびディレクトリ（フォルダ）からなる構造である。ファイルストレージシステム内で、ファイルシステムは、一般に、いくつかの仮想ストレージ構成体を用いて管理され、例示的な実施形態では、ファイルシステムは、レンジ、ストライプセット、スパンと呼ばれる仮想ストレージ構成体の階層を用いて管理される。「レンジ」は、プライマリＳＤ自体か、またはプライマリ／セカンダリＳＤペアか、いずれかで構成され、これらは、同じデータを格納するものであり、よって、単一のＳＤと同じストレージ容量を提供する。「ストライプセット」は、１つ以上のレンジで構成される。「スパン」は、１つ以上のストライプセットで構成される。従って、スパンは、結局、１つ以上のＳＤ（一般的には、４〜５０個のＳＤ）で構成される。スパンは、１つ以上のファイルシステムに分割することができ、各ファイルシステムは、個別の名前および識別子を有し、また、異なる特性を有し得る（例えば、あるファイルシステムを３２ＫＢクラスタで、別のものを４ＫＢクラスタでフォーマットすることができ、あるファイルシステムはＷＯＲＭとし、別のものはＷＯＲＭではないものとすることができる、など）。スパンの各ファイルシステムは、個別に、フォーマット、マウント、およびアンマウントされる。ファイルシステムは、任意の順序で、任意の時点で、作成および削除され得る。ファイルシステムは、一般に、自動的に拡張されるように（あるいは自動拡張を回避または制限するように）設定することができるか、または手動で拡張することができる。
【００２２】
「ブロック」は、ファイルシステムにおけるストレージの単位であり、ユーザデータおよび／またはシステムデータが保存された物理ストレージの一部に対応している。（後述する）ファイルシステムオブジェクトは、一般に、１つ以上のブロックを含む。
【００２３】
「チャンク」は、ファイルシステムにおけるストレージの概念単位であり、ファイルシステムオブジェクトの１つ以上のブロックを包含する。本明細書で記載する例示的な実施形態では、重複排除がチャンク単位で実行される。
【００２４】
値の「セット」は、１つ以上の値を含み得る。
【００２５】
以下で、便宜上、見出しが使用されるが、それらは、決して本発明を限定するものとして解釈されるべきではない。
【００２６】
本発明の例示的な実施形態について、日立データシステムズ社が販売しているＢｌｕｅＡｒｃ Ｔｉｔａｎ（登録商標）およびＭｅｒｃｕｒｙ（登録商標）ファイルサーバとして一般に知られる各種ファイルサーバで使用されるタイプの典型的なファイルシステムを参照して説明するが、種々のコンセプトは、他のタイプのファイルシステムに適用され得ることに留意すべきである。
【００２７】
［例示的なファイルストレージシステム］
図１は、本発明の例示的な実施形態によるファイルストレージシステムの概略ブロック図である。ファイルストレージシステムは、特に、いくつかのファイルサーバ（簡単にするため、便宜上、単一のファイルサーバ１０２を示している）を含み、これらは、インターネットプロトコル・ネットワーク（例えば、インターネット）などの通信ネットワーク１０４を介して様々なクライアント装置１０６1〜１０６Mと通信し、さらに、ファイバチャネル（ＦｉｂｒｅＣｈａｎｎｅｌ）ネットワークなどのストレージネットワーク１１０を介して様々なＲＡＩＤシステム１０８1〜１０８Nと通信する。クライアント装置１０６1〜１０６Mとファイルサーバ１０２とは、ＣＩＦＳおよび／またはＮＦＳなど、１つ以上のネットワークファイルプロトコルを用いて通信する。ファイルサーバ１０２とＲＡＩＤシステム１０８1〜１０８Nとは、ＳＣＳＩなどのストレージプロトコルを用いて通信する。留意すべきことは、ファイルストレージシステムは、様々な構成で相互接続された複数のファイルサーバと複数のＲＡＩＤシステムを含み得るということであり、それには、冗長スイッチド・ファイバチャネルネットワークを介して任意のファイルサーバが任意のＲＡＩＤシステムと通信することが可能なフルメッシュ構成が含まれる。
【００２８】
ファイルサーバ１０２は、１つ以上のファイルシステムを管理するためのストレージプロセッサを備える。ファイルサーバ１０２は、指定された名前で、ツリーまたはサブツリーなど、ファイルシステムの部分へのクライアントアクセスを可能とするように構成され得る。ＣＩＦＳの用語では、そのようなアクセスを「共有」と呼ぶことができ、ＮＦＳの用語では、そのようなアクセスを「エクスポート」と呼ぶことができる。ファイルサーバ１０２は、内部には、例えば、その全体が参照により本明細書にそれぞれ組み込まれる米国特許第６８２６６１５号（２３３７／１０３）および第８１８０８９７号（２３３７／１０８）に記載されているような、ハードウェア実装および／またはハードウェアアクセラレートされる各種サブシステムを含むことができ、さらに、例えば、その全体が参照により本明細書にそれぞれ組み込まれる米国特許第７４５７８２２号（２３３７／１０４）および第８２２４８７７号（２３３７／１１７）に記載されているような、複数のリンクされたサブモジュールを含むハードウェアベースのファイルシステムを含むことができる。
【００２９】
各ＲＡＩＤシステム１０８は、一般に、少なくとも１つのＲＡＩＤコントローラ（通常は、冗長のために、２つのＲＡＩＤコントローラ）と、ＲＡＩＤコントローラによって管理される複数の物理ストレージデバイス（例えば、ディスク）と、を備える。ＲＡＩＤシステム１０８は、そのストレージ資源を複数のＳＤに集約する。例えば、各ＲＡＩＤシステム１０８は、２〜３２個のＳＤで構成することができる。各ＳＤは、所定の最大容量（例えば、２ＴＢ〜６４ＴＢ、またはさらに大きい容量）に制限され得る。複数のストレージデバイスをＳＤに統合することによって、いくつかの効果を得ることができ、それには、高速化（個々のストレージデバイスは比較的低速であるが、このボトルネックを緩和するために、データを複数のストレージデバイスの間にストライピングすることができる）、大容量化（個々のストレージデバイスは比較的小容量であるが、複数のストレージデバイスを統合することで、より大きな使用可能空間を提供することができる）、抽象化（使用される容量は、単一のストレージデバイスの容量よりも大きいか、または小さいことが可能である）、耐障害性（ＳＤがストレージデバイスの損失に耐えることができるように、各ストレージデバイスにパリティ情報または冗長情報を記憶することができる）、が含まれる。
【００３０】
ファイルサーバ１０２は、単一のＲＡＩＤシステムまたは複数のＲＡＩＤシステムからのものであり得る１つ以上のＳＤを使用するように構成される。ファイルサーバ１０２は、通常、各ＳＤがプライマリであるか、またはセカンダリであるかを確認するために、ＲＡＩＤシステムに問い合わせることができる。どのＳＤがファイルサーバ１０２によって使用されるのかを制御する方法を、本明細書では、「ライセンシング」と呼ぶ。よって、実際には、ファイルサーバ１０２は、一般に、一部のＳＤについてライセンスされて、他のものについてはライセンスされないことになる。
【００３１】
ファイルサーバ１０２は、内部では、複数のＳＤを統合して、本明細書では「スパン」と呼ぶ、より大容量のストレージプールにすることが可能である。スパンは、実質的には、複数のＳＤからなるＲＡＩＤ０アレイである。複数のＳＤをスパンに統合することによって、複数の物理ディスクをＳＤに統合することにより得られるものと同様のいくつかの効果を得ることができ、それには、高速化（複数のＲＡＩＤシステムの複数のＳＤの間にＩ／Ｏを分散させることによって、ストレージのボトルネックをさらに緩和することができる）、ストレージの大容量化（スパンは、２ＴＢに制限され得る単一のＳＤよりも大容量とすることが可能である）、より柔軟なストレージ空間の割り当てを可能とする更なる抽象化、が含まれる。
【００３２】
［ソフトウェア／ハードウェア・アーキテクチャ］
いくつかの例示的な実施形態において、ファイルサーバは、ソフトウェアベースのシステムとハードウェアベースのシステムとの間の独特な役割分担によって重複排除を実現する。図２は、そのような例示的な実施形態によるソフトウェア／ハードウェア・アーキテクチャの概略図である。この場合、ソフトウェアベースのシステム２１０は、ソフトウェアベースの重複排除マネージャ２１２と重複排除検出／インデキシング・エンジン２１３とを含む各種ソフトウェアコンポーネントを有し、それらは、マイクロプロセッサシステム（例えば、マイクロプロセッサと、関連付けられたメモリおよび周辺機器と、を含む）上で動作するオペレーティングシステム２１１の下で実行される。ソフトウェアベースの重複排除マネージャ２１２と重複排除検出／インデキシング・エンジン２１３との間で通信を可能とするために、（例えば、Ｂｏｓｓｏｃｋソケット層を介して）プロセス間通信チャネル２１４が提供される。ハードウェアベースのシステム２２０は、ハードウェアベースのハッシュ生成器２２２（より詳細に後述する）およびファイルシステム２２３と通信するハードウェアベースのファイルシステム・マネージャ２２１を含む各種ハードウェアコンポーネントを有し、ファイルシステムは、各種メモリおよびストレージデバイスに保存されており、それらの一部はファイルサーバ１０２内（例えば、内部キャッシュメモリ内）にある場合があり、また、それらの一部はファイルサーバ１０２の外部にある場合がある（例えば、各種ＲＡＩＤシステムまたは他のストレージシステムに保存される）。ソフトウェアベースの重複排除マネージャ２１２とハードウェアベースのファイルシステム・マネージャ２２１との間の通信を可能とするために、インタフェース２３０が提供される。
【００３３】
図２に示す役割分担によって、特に、重複排除がハードウェアベースのファイルシステムの性能に及ぼす影響を制御するように、ソフトウェアベースの重複排除マネージャ２１２が、バックグラウンドで重複排除機能を誘導することが可能になるとともに、ソフトウェアベースとハードウェアベースのコンポーネント間の通信量が減少する。後述するように、ソフトウェアベースの重複排除マネージャ２１２とハードウェアベースのファイルシステム・マネージャ２２１はどちらも、重複排除の実行に要する処理量および通信量を削減する様々な最適化を含んでいる。
【００３４】
［ファイルシステムオブジェクトおよびツリー構造］
ファイルサーバ１０２は、各種タイプのオブジェクトをファイルシステムに保存する。オブジェクトは、一般にシステムオブジェクトとファイルオブジェクトに分類することができる。ファイルオブジェクトは、ワードプロセッサファイルまたはスプレッドシートファイルなどのように、ユーザデータおよび関連付けられた属性の保存用に作成される。システムオブジェクトは、情報の管理用に、ファイルストレージシステムによって作成されるものであり、数例を挙げると、ルートディレクトリオブジェクト、空き領域割り当てオブジェクト、変更チェックポイントオブジェクトリストオブジェクト、変更保持オブジェクトリストオブジェクト、ソフトウェアメタデータオブジェクト、などが含まれる。より具体的には、ディレクトリオブジェクトは、ディレクトリ情報の保存用に作成される。空き領域割り当てオブジェクトは、空き領域の割り当て情報の保存用に作成される。変更チェックポイントオブジェクトリストオブジェクトおよび変更保持オブジェクトリストオブジェクト（これら両方についてはより詳細に後述する）は、それぞれ、チェックポイントおよび保持チェックポイントに関する情報の保存用に作成される。ソフトウェアメタデータオブジェクト（より詳細に後述する）は、ファイルオブジェクトまたはディレクトリオブジェクトに関連付けられた余分なファイル属性（すなわち、ＣＩＦＳセキュリティ属性など、後述するように、そのファイルオブジェクトまたはディレクトリオブジェクト内の予め定められた領域内に収めることができないファイル属性）を保持するための特殊オブジェクトであって、ファイルオブジェクトまたはディレクトリオブジェクトの作成者によって作成されるものであり、そのファイルオブジェクトまたはディレクトリオブジェクト内には、ソフトウェアメタデータオブジェクトへの参照が格納される。
【００３５】
いくつかの実施形態において、ファイルシステムのインスタンス化は、ルートノード（動的スーパーブロックまたはＤＳＢと呼ばれる）を有するツリー構造を用いて管理される。ファイルサーバ１０２は、ファイルシステムの異なるチェックポイントを表す異なるバージョン（例えば、現在「使用中」のバージョンと、１つ以上の「チェックポイント」バージョン）を保存するために、複数のＤＳＢを保持することができる。例示的な一実施形態において、ＤＳＢは、間接オブジェクトへのポインタを有し、そして、その間接オブジェクトは、他のオブジェクトへのポインタを有する。間接オブジェクトにより参照される各オブジェクトには、オブジェクト番号が関連付けられる。システムオブジェクトは、一般に、常にシステム内に存在するので、典型的には、事前定義された固定のオブジェクト番号を有する。ファイルオブジェクトは、一般に、使用できるオブジェクト番号のプールから動的にオブジェクト番号が割り当てられ、それらのファイルオブジェクト番号は、状況によって、再使用することができる（例えば、ファイルが削除されると、そのオブジェクト番号は、後のファイルオブジェクトによる再使用が可能な空きとなり得る）。間接オブジェクトは、対応するオブジェクトへのポインタを取得するために、オブジェクト番号によってインデキシングすることができる。
【００３６】
一般的に、間接オブジェクト、システムオブジェクトの各々、ファイルオブジェクトの各々を含む、ファイルシステムにおける各オブジェクトは、別個のオブジェクトルートノード（ルートｏノードと呼ばれることがある）を有するとともに、オプションとして、いくつかの間接ノード（間接ｏノードと呼ばれることがある）、直接ノード（直接ｏノードと呼ばれることがある）、およびストレージブロックを有する別個のツリー構造を用いて実現される。ＤＳＢは、間接オブジェクトのルートノードへのポインタを有する。間接オブジェクトは、その他のオブジェクトのルートノードへのポインタを有する。
【００３７】
図３は、本発明の例示的な実施形態によるオブジェクトツリー構造の一般形式を示す概略ブロック図である。ルート（「Ｒ」）ノード３０２は、いくつかの間接（「Ｉ」）ノード３０４を指すことができ、それらの各々は、いくつかの直接（「Ｄ」）ノード３０６を指すことができ、それらの各々は、いくつかのストレージブロック（「Ｂ」）３０８を指すことができる。実際には、オブジェクトツリー構造は、例えば、そのオブジェクトのサイズによって、大きく異なり得る。また、特定のオブジェクトのツリー構造は、そのオブジェクトに情報が追加および削除されることで、時間とともに変化し得る。例えば、より多くのストレージ空間がそのオブジェクトのために使用されるときには、ツリー構造にノードが動的に追加される場合があり、また、必要に応じて、いくつかの異なる間接レベルが用いられることがある（例えば、間接ノードは、直接ノードまたは他の間接ノードを指し得る）。
【００３８】
オブジェクトが作成されると、そのオブジェクトのためのオブジェクトルートノードが作成される。最初は、そのような「空の」オブジェクトのルートノードは、間接ノード、直接ノード、またはデータブロックへのポインタをいずれも有していない。
【００３９】
そのオブジェクトにデータが追加されると、まず最初に、そのデータは、ルートノードが直接指すデータブロックに入れられる。ルートノードにおける直接ブロックポインタが全て使い尽されたら、次に、直接ノードが、ルートノードからその直接ノードへのポインタと共に作成される。そのオブジェクトのデータが、直接ノードにおけるデータポインタを全て使い尽すまで増大すると、次に、間接ノードが作成される。
【００４０】
一時コピーと、さらにオプションとして保持される様々な時点でのファイルシステムのコピーを作成するために、例えば、上記で参照により組み込まれた米国特許第７４５７８２２号（２３３７／１０４）、およびその全体が参照により本明細書に組み込まれる米国特許第８０４１７３５号（２３３７／１０５）に記載されているような、チェックポイント機構が設けられる。具体的には、ファイルシステム要求の処理は、１０秒ごとなど、ユーザ指定の間隔よりも低くない頻度で生じるようにスケジュールされた一連のチェックポイントによって区切られる。連続するチェックポイントのそれぞれに関して、現在のファイル構造情報がディスクに保存され、これが、直前のチェックポイントからの保存済みファイル構造情報に取って代わる。チェックポイントは、順番に番号が付されて、ファイル要求の処理を時間的にグループ分けするために用いられる。各ファイルシステムオブジェクトには、それが作成されたチェックポイントが関連付けられ、その作成チェックポイント番号が、オブジェクトルートノードに保存される。
【００４１】
様々な目的で、選択された時点でのファイルシステム構造についての知識を得ることが有用となり得る。このような機能は、以下では便宜上、保持チェックポイントまたはスナップショットと呼ばれる、現在保存されているチェックポイントに関連付けられたファイルシステム構造データの保存を可能にすることによって提供される。保持チェックポイントは、実質的に、特定のチェックポイントでのファイルシステム構造の読み取り専用バージョンである。複数の保持チェックポイントを取得することができ、また、選択された保持チェックポイントを削除するための、または（例えば、カタストロフィの後にファイルシステムを既知の状態に戻すために）選択された保持チェックポイントにファイルシステムを戻すための、機構が設けられる。
【００４２】
本発明のいくつかの実施形態において、ユーザがファイルのコピーを作成するときなどに、ファイルシステム内でファイルのコピー（クローン）を迅速に作成することを可能とするために、例えば、その全体が参照により本明細書に組み込まれる米国特許出願公開第２０１２／０１３０９４９号（２３３７／１３０）に記載されているようなファイルクローニング機構が設けられる。例示的な実施形態において、ソースオブジェクトのクローンは、少なくとも最初は、そのソースオブジェクトの各種要素（例えば、間接ｏノード、直接ｏノード、データブロック）への参照を格納した構造で表される。読み取り専用のクローンと可変クローンの両方を作成することができる。ソースファイルとクローンは、最初は、そのような要素を共有しており、ソースファイルまたは可変クローンに変更が加えられると、変更されていない要素を共有し続ける。ソースファイルに関連付けられたユーザデータブロック、またはデータストリームを記述するメタデータブロック（すなわち、間接／直接ｏノード）は、いずれも、クローンを作成する時点では複製される必要がない。クローニングされたファイルは、適時に、「デクローニング」され得る。
【００４３】
オブジェクトルートノードは、オブジェクトが直近で変更されたチェックポイントを示すためのチェックポイント番号を含む（チェックポイント番号は、最初は、オブジェクトが作成されたチェックポイントを示し、その後、オブジェクトが新しいチェックポイントで変更される度に、チェックポイント番号は変更される）。例示的な一実施形態では、さらに、オブジェクトが作成されたチェックポイント番号も、オブジェクトルートノードに保存される。
【００４４】
オブジェクトルートノードが対応している実際のデータのために、オブジェクトルートノードは、対応するオブジェクトに関連付けられたデータの各ブロックへの個別のポインタを有する。一般に、最大１６個までのデータブロックへのポインタが、オブジェクトルートノードに保存される。１６個のブロックを超えるデータのためには、１つ以上の間接ノードおよび／または直接ノードが、オブジェクトツリーにおいて必要になるとともに、各種ノードにリンクするための適切なポインタが、必要に応じて、各ノードに保存される。そのようなポインタは、対応するデータブロックまたはノードに関連付けられたディスク上のブロックのセクタ番号を記憶している。
【００４５】
直接ノードは、チェックポイント番号を有し、また、そのオブジェクトに関連する一定数のブロック（例えば、約６０または６１個のブロック）の場所を記憶するように構成されている。
【００４６】
第１の直接ノードが、データブロックを示すために全て使用されると、次に、１つ以上の間接ノードを用いて、第１の直接ノードと、さらに、そのオブジェクトに対応するデータのブロックを有する追加の直接ノードが示される。そのような場合、オブジェクトルートノードは、間接ノードへのポインタを有し、間接ノードは、対応する直接ノードへのポインタを有する。間接ノードが全て使用されると、次に、必要に応じて、追加の介在する間接ノードが用いられる。この構造体によって、ファイルのフラグメンテーションに関わりなく、ファイルの一部分の高速同定が可能となる。
【００４７】
上述のように、間接ノードは、ルートノードと直接ノードとの間の間接レベルを提供する。例示的な一実施形態において、間接ノードには、以下の情報が保存される。
・  チェックポイント番号。
・  間接ノードまたは直接ノードのいずれかへのポインタ（例えば、最大６０個までの、そのようなポインタ）。
・  間接ノードの妥当性チェックを可能とするためのＣＲＣおよび各種サニティ・ダブルワード。
【００４８】
上述のように、直接ノードは、ディスク上のデータブロックへの直接ポインタを提供する。例示的な一実施形態において、直接ノードには、以下の情報が保存される。
・  チェックポイント番号。
・  複数のデータブロック記述子（例えば、最大６０個までの、そのような記述子）。各データブロック記述子は、データブロックへのポインタと、チェックポイント番号と、そのブロックがゼロ充填されるかどうかを示すビットと、を含む。
・  直接ノードの妥当性チェックを可能とするためのＣＲＣおよび各種サニティ・ダブルワード。
【００４９】
各ノード（すなわち、ルートノード、直接ノード、間接ノード）において、ブロックまたは他のノードへの各ポインタには、該ポインタにより参照されるブロック／ノードに関連付けられたチェックポイントを示すためのチェックポイント番号が関連付けられている。後述するいくつかの例示的な実施形態において、それらのチェックポイント番号は、重複排除の可能性について特定のファイルシステムオブジェクト・チャンクを調べるべきかどうか判断するために用いられる。
【００５０】
いかにしてファイルシステムオブジェクトツリー構造が管理されるかについての上記説明では、オブジェクトが書き込まれる際に、データブロックおよびツリーノードが密に割り当てられたが、いくつかの例示的な実施形態では、疎なファイルシステムオブジェクトがサポートされ、その場合、データブロックおよびツリーノードを全て割り当てなくても、さらにオブジェクトのゼロ充填部分については、データブロック（複数の場合もある）にゼロ充填しなくても、ファイルシステムオブジェクトを書き込むことができる。
【００５１】
例えば、ファイルへの書き込みが、ファイルの現在の終わりからの開始オフセットを有する場合、現在の終わりと新しい書き込みデータの始まりとの間のファイルの未定義部分は、ゼロ充填されることが技術的に必要となる。オブジェクトの長さが、現在の長さよりも大きく設定される場合にも、同じことが生じる。これは、ファイルが作成されて、その長さが、例えば１ＧＢに設定される場合に、特に問題となり得る。そのようなファイルシステムオブジェクトにデータブロックを全て割り当てると、そのオブジェクトに割り当てられたディスクブロックに、実際にゼロを書き込むことが必要となる。１ＧＢファイルの場合、これは、例えば１０秒程度を要し得る。１ＴＢファイルの場合、それは、例えば３時間程度を要し得る。
【００５２】
本発明のいくつかの実施形態において、この問題は、各データブロックポインタと共に、そのブロックがゼロ充填されるかどうかを示すビットを有することによって、回避される。このビットが設定されている場合には、ファイルサーバは、このブロックが、ディスク上では非ゼロデータが入っているとしても、ゼロ充填されるべきであることが分かる。ブロックが読み出される場合には、実際のディスク上の内容ではなく、ゼロが、このブロックとして返される。ブロック全体に満たない書き込みによってブロックが書き込まれる場合には、書き込まれていないブロックの部分にゼロが書き込まれ、そして、そのブロックがゼロ充填されるものではないことを示すために、ビットがリセットされる。この場合、注目されるのは、ファイルのゼロ充填される全ての部分にディスクブロックが割り当てられるものの、実際にディスクブロックがゼロ充填されることはないということである。
【００５３】
一部の例では、ファイルシステムオブジェクトのそのようなゼロ充填される部分に対しては、データブロックおよびツリーノードの割り当ては過度に時間を要し得るので、データブロックおよび関連するツリーノードの割り当てさえされない。例えば、４Ｋのディスクブロックサイズの場合、１ＴＢのオブジェクトは、約４００万個の直接ｏノードと、それより少数の間接ｏノードとを必要とし、これをディスクに書き込むには、４０秒程度を要し得る。また、必要な全てのデータブロックの空き領域割り当て、およびその後の空き領域ビットマップの更新によって、この時間はさらに大きく増加される。仮に、ファイルの作成が開始された直後にチェックポイントが取得されるとしたら、通常、システム全体が、この時間全体にわたって、（どのボリュームの要求であっても）要求に対するサービス提供を停止することになる。
【００５４】
そこで、いくつかの例示的な実施形態において、この問題は、二面的なアプローチにより解決される。ソリューションの第１の側面は、ファイルのゼロ充填される部分に対して、実際にはディスクブロックを割り当てないことである。これは、オブジェクト保存が、ゼロ充填されるブロックへの書き込みを伴う場合に、最初に、そのブロック用にディスク領域を割り当てるとともに、それへのポインタを、関連するｏノード構造に入れることが必要となることを意味する。
【００５５】
第２の側面は、第１の側面を基礎とするものであって、データブロックを割り当てないことに加えて、ｏノード構造も作成しないことを伴う。この側面を実施するために、各ｏノードポインタは、それが指すｏノードが割り当てられているか否かを示すためのビットを有する。割り当てられていない場合は、そのｏノードが有効であることがオペレーションで必要となったときにのみ、そのときにディスク領域がそれに割り当てられて、正しいポインタが挿入される。このようにして、膨大なゼロ充填オブジェクトは、ルートｏノードのみ有することが可能であり、これによって、非常に迅速に作成され得ることは明らかである。
【００５６】
ほんの一例として、ルートノード、およびルートノードから参照される次のレベルのノードに格納されるタイプの情報の表現を、以下に示している（注釈は下線を付して括弧内に示している）。
ファイルのルートノードの実例：
onode/ccache: onode -o 16392
onode/ccache: Read 1024 bytes from sector 0x38b560 (Byte Offset 0x716ac000)
onode/ccache: 
onode/ccache: ActiveRootNode
onode/ccache:   AsciiDescriptor  : RONA
onode/ccache:   SanityDWord0     : WFS1 (valid)
onode/ccache:   ObjectNumber     : 0x4008 (Type: OBJ_TYPE_FSOBJECT_FILE)
onode/ccache:   Checkpoint       : 0x123ab （本オブジェクトが直近で変更されたときのチェックポイント番号）
onode/ccache:   ReuseCount       : 0x123ab
onode/ccache:   WriteCount       : 0x3
onode/ccache:   IndirectionCount : 2
onode/ccache:   ResiliencyMode   : None
onode/ccache:   DataLength       : 1 MB (1048576 B)
onode/ccache:   FreeRootOnodePtr : 0x0 (unused)
onode/ccache:   SavedRootOnodePtr: 0x0 (unused)
onode/ccache:   BlockPtr[00]     : 0x38d0c8 (Checkpoint: 0x123ab) （チェックポイント０ｘ１２３ａｂで書き込まれたデータブロックへのポインタ）
onode/ccache:   BlockPtr[01]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[02]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[03]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[04]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[05]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[06]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[07]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[08]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[09]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[10]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[11]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[12]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[13]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[14]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   BlockPtr[15]     :  (Checkpoint: 0x123ab) (ZeroFill) (Sparse)
onode/ccache:   LeafOnodePtr     : 0x38b5c0 (Checkpoint: 0x123ab) （残りのデータブロックを指す追加のｏノードツリー）
onode/ccache:   Format TimeStamp : 0x5034155431d149c3
onode/ccache: WfsEnode
onode/ccache:   <Enode contains file's attributes - snipped>
onode/ccache:
onode/ccache:   Cloned Checkpoint: 0x0 （本オブジェクトが他のオブジェクトのクローンである場合は、Cloned Checkpointは非ゼロである）
onode/ccache:   Reserved[1]      : 0x0
onode/ccache:   Reserved[2]      : 0x0
onode/ccache:   BlockCount       : 0x100 (sparse blocks)
onode/ccache:   CreationChkpoint : 0x123ab （本オブジェクトが作成されたチェックポイント）
onode/ccache:   Crc32            : 0xcbe306ba (valid)
onode/ccache:   SanityDWord1     : WFS2 (valid)
ｏノードツリーにおける次のレベルの実例：
onode/ccache: onode -s 0x38b5c0
onode/ccache: Read 1024 bytes from sector 0x38b5c0 (Byte Offset 0x716b8000)
onode/ccache: Leaf Onode:
onode/ccache: IndirectOnode
onode/ccache:   AsciiDescriptor  : IONA
onode/ccache:   SanityDWord0     : WFS1 (valid)
onode/ccache:   ObjectNumber     : 0x4008 (Type: OBJ_TYPE_FSOBJECT_FILE)
onode/ccache:   Checkpoint       : 0x123ab （本ノードが書き込まれたときのチェックポイントであり、これは、本ノードを指すポインタにおけるチェックポイントフィールドと一致していなければならず、それは、本例では、上記ルートｏノードからのリーフｏノードポインタである）
onode/ccache:   ReuseCount       : 0x123ab
onode/ccache:   WriteCount       : 0x3
onode/ccache:   ResiliencyMode   : None
onode/ccache:   ObjectPtr[00]    : 0x38b5b8 (Checkpoint: 0x123ab) （ツリーの第１の次の分岐へのポインタ）
onode/ccache:   ObjectPtr[01]    : 0x38b5c8 (Checkpoint: 0x123ab) （ツリーの第２の次の分岐へのポインタ）
onode/ccache:   ObjectPtr[02]    : 0x38b5d0 (Checkpoint: 0x123ab) （ツリーの第３の次の分岐へのポインタ）
onode/ccache:   ObjectPtr[03]    : 0x38b5d8 (Checkpoint: 0x123ab) （ツリーの第４の次の分岐へのポインタ）
onode/ccache:   Reserved[0]      : 0x0
onode/ccache:   Reserved[1]      : 0x0
onode/ccache:   Reserved[2]      : 0x0
onode/ccache:   Crc32            : 0x25972e2f (valid)
onode/ccache:   SanityDWord1     : WFS2(valid)
【００５７】
［重複排除検出／インデキシング・エンジン］
本発明の実施形態が、特定の重複排除検出／インデキシング・エンジンに限定されることはないものの、いくつかの例示的な実施形態では、重複排除検出／インデキシング・エンジン２１３は、マサチューセッツ州ケンブリッジのＰｅｒｍａｂｉｔ Ｔｅｃｈｎｏｌｏｇｙ社からライセンスされるＡＬＢＩＲＥＯ（登録商標）データ最適化ソフトウェアとして知られる市販のソフトウェア製品（以下、「エンジン」と呼ぶ）であり、これは、プリコンパイル済みの共有ライブラリと実行ファイルとして提供されて、ソフトウェアベースのシステム２１０に統合される。
【００５８】
エンジンは、２つのタイプのインデキシング、すなわち、疎インデキシングとデフォルト・インデキシングをサポートしている。インデキシングは、チャンクのＳＨＡ−２５６ハッシュに基づくものである。どちらのインデックスタイプも、インデキシングされたチャンクごとに４バイトのインメモリ・エントリと、さらに、チャンクに関する情報がエンジンに提示されるものとして（かつ提示される順序で）記録されるオンディスク・データ構造と、を使用する。このオンディスク・データ構造は、各チャンクに関するアプリケーション固有の情報（以下、「チャンク・メタデータ」と呼び、より詳細は後述する）を保存するために使用される。いくつかの例示的な実施形態において、疎インデキシングが用いられるのは、一般的にはそのような時間局所性が好ましいと考えられるものの、重複排除のためにチャンクが必ずしも時間的順序で（すなわち、チャンクが実際に変更された順序で）処理されないバックグラウンド重複排除プロセスでは、疎インデキシングが好ましい場合があるためである。（必ずしもそうではないが）好ましくは、オンディスク・データ構造は、それが関連しているファイルシステム内に保存され、これにより、ＥＶＳおよびファイルシステムの移行時の両方において、オンディスク・データ構造を、ファイルシステムと共に自動的に移動させることが可能である。
【００５９】
［チェックポイントに基づく重複排除］
極めて上位のレベルでは、重複排除プロセスは、重複排除の候補となるチャンクを特定することと、特定の候補チャンクが、ファイルシステム内の別のチャンクの重複であるかどうか判断することと、候補チャンク（ひいては、重複データ）が保存される必要がないように、重複チャンクを、その別のチャンクへの参照で置き換えることと、を伴う。また、保存されるデータ量をさらに削減するように、同じくその別のチャンクの重複である他の候補チャンクも、その別のチャンクへの参照で置き換えることができる。
【００６０】
本発明のいくつかの例示的な実施形態では、バックグラウンド重複排除プロセスを管理するため、さらに、重複排除の候補となるチャンクの特定およびそのようなチャンクの処理に関する処理の複雑さを低減するために、ファイルシステム・チェックポイント機構を利用する。
【００６１】
いくつかの実施形態においてチェックポイントを利用する１つの方法は、ソフトウェアベースの重複排除マネージャにより、重複排除をバックグラウンド機能として、連続した重複排除サイクルで実行することであり、この場合、重複排除サイクルは、（スケジュールされるか、所定数のブロックが変更された後もしくは所定数のチェックポイントが取得された後などの一定の条件下で実施されるか、または手動で開始されることができる）様々な時点で実行され、また、各サイクルは、所定の範囲の必ずしも連続していないチェックポイント番号をカバーする。例示的な一実施形態では、各チェックポイントで、前のチェックポイントから変更されたブロック数を追跡および累積し、そして、最後の重複排除サイクル以降にファイルシステムにおいて変更されたブロック数を用いて、重複排除サイクルを開始させる時点を決定する。重複排除がライブファイルシステムから所定量で遅れている（例えば、重複排除された最後のチェックポイント範囲以降に、所定数を超えるブロックが変更された）と、ソフトウェアベースの重複排除マネージャが判断する場合には、ソフトウェアベースの重複排除マネージャは、ライブファイルシステムに「追い付く」ために、いくつかのチェックポイント範囲の重複排除を省略することができる。また、チェックポイント番号は、ソフトウェアベースの重複排除マネージャによって、候補チャンクの検出のために必要な処理量を削減するために用いられるとともに、ハードウェアベースのファイルシステム・マネージャによって、重複排除のためのマッチを検証するのに必要な処理量を削減するため、さらには、重複チャンクの実際の重複排除を実行するために用いられる。チェックポイントの使用についてはより詳細に後述する。
【００６２】
例示的な重複排除プロセスについての以下の説明では、各チャンクは、単一のファイルシステムブロックを包含すると仮定し、よって、この例示的な実施形態では、「チャンク」と「ブロック」という用語は、基本的に区別なく使用され得る。より一般的な、各チャンクが複数のファイルシステムブロックを包含し得る実施形態についての考察は、後述する。
【００６３】
いくつかの例示的な実施形態において、ソフトウェアベースの重複排除マネージャ２１２は、図４に概略的に示すように３つのｉステージに分けられた「パイプライン」アーキテクチャを用いる。この場合、ソフトウェアベースの重複排除マネージャ２１２は、「変更ブロック検出」ステージ４０２と、「重複排除アドバイス取得」ステージ４０４と、「チャンク重複排除」ステージ４０６と、を含む。この例示的な実施形態では、各ステージは、単一スレッドから非同期要求を発行する。
【００６４】
図５は、本発明のいくつかの例示的な実施形態による重複排除についての概略論理フロー図である。
【００６５】
一般的には、バックグラウンド機能として、ソフトウェアベースの重複排除マネージャ２１２は、ブロック５０２で、ファイルシステムのスナップショットを取得し、ブロック５０４で、重複排除のためのチェックポイント範囲を決定する。チェックポイント範囲は、基本チェックポイント番号（「チェックポイント・ロー」と呼ばれる）と、上チェックポイント番号（「チェックポイント・ハイ」と呼ばれる）と、を含み、チェックポイント・ハイは、一般的には、スナップショットに関連付けられたチェックポイント番号であり、チェックポイント・ローは、直前の重複排除の反復のチェックポイント・ハイの値と同じであってもそうでなくてもよい所定の過去のチェックポイントである。（後述のように、複数のファイルシステムの重複排除をサポートすることを可能にする）ファイルシステム識別子と、その重複排除サイクルを開始すべきオブジェクト番号と、単一ジョブでチェックすべきオブジェクト数と、基本チェックポイント番号（チェックポイント・ロー）と、上チェックポイント番号（チェックポイント・ハイ）と、を含むジョブが、「変更ブロック検出」キューに送られる。
【００６６】
ソフトウェアベースの重複排除マネージャ２１２の変更ブロック検出スレッドプール／プロセス４０２により、ブロック５０６において、所定のチェックポイント範囲内で変更されたチャンク、ひいては重複排除の候補であるチャンクを特定するために、ファイルシステムの「スナップショット」コピーを処理する。候補チャンクを特定するための例示的なプロセスについては後述する。
【００６７】
候補チャンクが見つかった場合（ブロック５０８でＹＥＳ）は、変更ブロック検出ステージ４０２で、候補チャンクに関する関連情報（例えば、そのチャンクのブロックポインタおよびチェックポイント）を含むジョブを、重複排除アドバイス取得ステージ４０４に送る。ブロック５１０において、条件付きで（すなわち、後述するいくつかの制限を受けて）ストレージから候補チャンク（複数の場合もある）を読み込むとともに、ハードウェアベースのハッシュ生成器２２２を用いて候補チャンクのハッシュを計算するための要求を、重複排除アドバイス取得ステージ４０４で、インタフェース２３０を介してハードウェアベースのファイルシステム・マネージャ２２１に送る。
【００６８】
例えば、候補チャンクに関連付けられたファイルシステムオブジェクトが、ソフトウェアベースの重複排除マネージャ２１２により使用されたファイルシステムのスナップショットコピーが取得されて以降に、その候補チャンクを排除するために削除または破棄されているか、またはソフトウェアベースの重複排除マネージャ２１２により使用されたファイルシステムのスナップショットコピーが取得されて以降に、そのチャンクが変更されているかもしれないので、ハードウェアベースのファイルシステム・マネージャ２２１は、特定の候補チャンクの読み込み／ハッシュ化の前に、その候補チャンクを読み込みおよびハッシュ化すべきか否か判断する。最初の２つのケースでは、候補チャンクのハッシュ値を計算する必要はなく、これによって、処理資源が節約されるとともに、ソフトウェアベースの重複排除マネージャとハードウェアベースのファイルシステム・マネージャとの間の通信が削減される。後者のケースでは、その候補チャンクが、「スナップショット」コピーにあったときと同じチェックポイントにある場合には、ハードウェアベースのファイルシステム・マネージャ２２１は、上述のように、その候補チャンクのハッシュ値を計算し、そのハッシュ値および関連のチャンク・メタデータを、ソフトウェアベースの重複排除マネージャに送る。
【００６９】
ハードウェアベースのファイルシステム・マネージャ２２１が、候補チャンクを読み込み／ハッシュ化すべきと判断すると仮定すると、その場合、ハードウェアベースのファイルシステム・マネージャ２２１は、ハッシュ生成器２２２を起動して、これにより、ハッシュを生成し、そのハッシュを、候補チャンクに関連するチャンク・メタデータ（特に、オブジェクト番号、チェックポイント番号などを含む）と共に、重複排除アドバイス取得ステージ４０４に返送する。ソフトウェアベースの重複排除マネージャ２１２が、（例示的な一実施形態では３２Ｋバイトであり得る）候補チャンク全体を要求し、ソフトウェアベースのシステム２１０内で（例えば、ソフトウェアベースの重複排除マネージャ２１２によって、または重複排除検出／インデキシング・エンジン２１３によって）ハッシュ化を実施していたのに対して、この機構によれば、候補チャンク全体ではなく、（例示的な一実施形態では、２５６ビットのハッシュ値に、最大３２バイトまでのチャンク・メタデータを加えた、６４バイト程度の情報である）ハッシュ値および関連するチャンク・メタデータを送ることで、ソフトウェアベースのシステム２１０とハードウェアベースのシステム２２０との間の通信が削減され、またはドウェアでハッシング関数を実行することで、ソフトウェアベースのシステム２１０においてマイクロプロセッサへの負荷が軽減される。
【００７０】
候補チャンクがハッシュ化されたと仮定すると（ブロック５１２でＹＥＳ）、この場合、ブロック５１４において、重複排除アドバイス取得ステージ４０４で、インタフェース２１４を介して重複排除インデキシング／マッチング・エンジン２１３を呼び出し、これにより、ハッシュ値が、インデックス付きチャンクのハッシュとマッチするかどうか判断する。候補チャンクのハッシュが、インデックス付きチャンクのハッシュとマッチしない場合（ブロック５１６でＮＯ）は、重複排除アドバイス取得ステージ４０４で、典型的には、そのハッシュ値に関してハードウェアベースのファイルシステム・マネージャ２２１から受信したチャンク・メタデータを保存する（すなわち、その候補チャンクが、その後の重複検出のためのインデックス付きチャンクとなる）ことによる候補チャンクのインデキシングを、重複排除検出／インデキシング・エンジン２１３に指示する。一方、候補チャンクのハッシュが、インデックス付きチャンクのハッシュとマッチする場合（ブロック５１６でＹＥＳ）は、重複排除インデキシング／マッチング・エンジン２１３は、そのインデックス付きチャンクの保存されたチャンク・メタデータを、重複排除アドバイス取得ステージ４０４に返し、そしてこれによって、チャンク重複排除スレッドプール／プロセス４０６に対してジョブが送られる。
【００７１】
チャンク重複排除ステージ４０６で、（重複排除検出／インデキシング・エンジン２１３により返されたチャンク・メタデータに基づいて）インデックス付きチャンクに関連付けられたオブジェクトをロックして、そしてブロック５１８において、重複排除検出／インデキシング・エンジン２１３により返されたチャンク・メタデータに基づいて、そのマッチを検証するとともに、その候補チャンクの重複排除を条件付きで実行するための要求を、ハードウェアベースのファイルシステム・マネージャ２２１に送る。
【００７２】
候補チャンクがインデックス付きチャンクにマッチしたことが、ハードウェアベースのファイルシステム・マネージャ２２１に通知されると、ハードウェアベースのファイルシステム・マネージャ２２１は、ソフトウェアベースの重複排除マネージャ２１２により使用されたファイルシステムのスナップショットコピーが取得されて以降に、さらにはハッシュが生成されて以降に、重複排除する目的で、そのインデックス付きチャンクおよび／または候補チャンクが古いため使用できないように、関連する情報がライブファイルシステムにおいて変更されているかもしれないので、その候補チャンクの重複排除を実行するか否かを判断する必要がある。例えば、ソフトウェアベースの重複排除マネージャが候補チャンクを重複として特定する時点までに、その候補チャンクに関連付けられたオブジェクトは、ライブファイルシステムから削除されているかもしれず、または、その候補チャンクに関連付けられたオブジェクトは、もはやその候補チャンクがそのオブジェクトの一部ではないように破棄されているかもしれず、または、その候補チャンクは変更されているかもしれない。このように、候補チャンクのマッチは仮定的なものにすぎず、候補チャンクの重複排除を実行可能とする前に検証されなければならない。そこで、ハードウェアベースのファイルシステム・マネージャ２２１は、チェックポイント番号を用いて、インデックス付きチャンクと候補チャンクの両方を検証し、具体的には、インデックス付きブロックポインタの現在のチェックポイントを、インデックスからのチャンク・メタデータの中に返されたチェックポイントと比較することにより、それら２つのブロックに変更がなく、依然として使用中であり、従って重複排除に使用できることを確認する。
【００７３】
また、それ以外に、インデックス付きチャンクが、候補チャンクの重複排除のために使用できる場合であっても、いくつかの例示的な実施形態において、ハードウェアベースのファイルシステム・マネージャ２２１は、そのインデックス付きチャンクに関連付けられたブロックが、既に所定の最大回数、参照（すなわち、共有）されている場合には、候補チャンクの重複排除を実行しないことがある。よって、そのような例示的な一実施形態では、特定のブロックが参照（すなわち、共有）され得る回数に制限を課すことができる。この例示的な実施形態では、ハードウェアベースのファイルシステム・マネージャ２２１は、そのブロックの（後述する）参照カウントを、最大参照カウントに達したかどうか判断するためにチェックする。最大参照カウントに達しており、そのインデックス付きチャンクからのブロックを用いて候補チャンクの重複排除を実行できないことが示された場合は、ハードウェアベースのファイルシステム・マネージャ２２１は、チャンク重複排除ステージ４０６に通知する。
【００７４】
候補チャンクの重複排除を実行できると、ハードウェアベースのファイルシステム・マネージャ２２１が判断すると仮定して、その場合、ハードウェアベースのファイルシステム・マネージャ２２１は、特に、対応するファイルシステムオブジェクトにおける候補チャンクへの参照を、インデックス付きチャンクへの参照で置き換えるとともに、インデックス付きチャンクに関連付けられた参照カウントを増加させ、さらに、そのファイルシステムオブジェクトに必要なストレージ容量を削減するために、その候補チャンクを解放するようにマークする。
【００７５】
ハードウェアベースのファイルシステム・マネージャ２２１によって、候補チャンクの重複排除が正常に実行された場合（ブロック５２０でＹＥＳ）は、処理すべきオブジェクトが残っていれば（ブロック５２６でＮＯ）、プロセスは、基本的に、ブロック５０６に戻る。一方、ハードウェアベースのファイルシステム・マネージャ２２１により、候補チャンクの重複排除が正常に実行されず（ブロック５２０でＮＯ）、より詳細は後述するように、候補チャンクの重複排除のそのような失敗が、インデックス付きチャンクが、その最大参照カウントに達したことで、候補チャンクの重複排除に使用できないことによるものであった場合（ブロック５２２でＹＥＳ）は、ブロック５２４において、チャンク重複排除スレッドステージ４０６で、典型的には、そのハッシュ値に関してハードウェアベースのファイルシステム・マネージャ２２１から受信したチャンク・メタデータを保存する（すなわち、その候補チャンクが、その後の重複検出のためのインデックス付きチャンクとなる）ことによる候補チャンクのインデキシングを、重複排除検出／インデキシング・エンジン２１３に指示する。候補チャンクの重複排除が実行されたか否かに関わりなく、また、候補チャンクに基づいてインデックスが更新されたか否かに関わりなく、処理すべきオブジェクトが残っている場合（ブロック５２６でＮＯ）は、プロセスは、基本的に、ブロック５０６に戻る。
【００７６】
［候補チャンクの特定］
上述のように、変更ブロック検出ステージ４０２では、ファイルシステムにおける変更を、それらの重複排除を試みるために、特定しなければならない。いくつかの例示的な実施形態において、ソフトウェアベースの重複排除マネージャ２１２は、変更されたオブジェクトを特定することと、そしてさらに、チェックポイント番号を用いて、そのような変更されたオブジェクト内で変更されたブロックを特定することを、間接オブジェクトについて繰り返す。図６は、例示的な一実施形態により候補チャンクを特定する場合の論理フロー図である。この場合、ブロック６０２において、変更ブロック検出ステージ４０２で、ファイルシステムオブジェクトのルートノードを調べる。そのオブジェクトの作成チェックポイントが、チェックポイント範囲内にある場合（ブロック６０４でＹＥＳ）は、そのオブジェクトが（後述する）クローンオブジェクトでなければ、そのファイルシステムオブジェクトに関連付けられた全てのブロックは、そのチェックポイント範囲内で変更されていることになり、従って、そのファイルシステムオブジェクトの全てのブロックは、（オプションとして、後述する例を除いて）典型的には、候補チャンクとみなされる。
【００７７】
そのファイルシステムオブジェクトがクローンオブジェクトである場合（ブロック６０６でＹＥＳ）は、元のオブジェクト（すなわち、このオブジェクトのクローン元のオブジェクト）から分岐した、ファイルシステムオブジェクトのブロックのみが候補チャンクとみなされ、従って、ブロック６０８において、変更ブロック検出ステージ４０２で、元のオブジェクトから分岐した候補ブロックをいずれも特定するために、オブジェクトツリーを「探索」（すなわち、トラバース）する。そのような分岐したブロックは、オブジェクトルートノードに保存されているオブジェクトのクローニング時のチェックポイント番号よりも、大きいチェックポイント番号を有することになる。
【００７８】
そのファイルシステムオブジェクトがクローンオブジェクトではないが（ブロック６０６でＮＯ）、そのオブジェクトが疎なオブジェクトである場合（ブロック６１０でＹＥＳ）には、そのオブジェクトの全てのブロック（それらのブロックのうち一部は未割り当てであり得る）を候補チャンクとして扱うのではなく、ソフトウェアベースの重複排除マネージャ２１２は、オプションとして、ブロック６１２において、割り当ておよび書き込みされているブロックのみを見つけるために、オブジェクトツリーを「探索」し、そのようなブロックを候補チャンクとして扱うことができる。
【００７９】
そのオブジェクトの作成チェックポイントがチェックポイントウィンドウ内にあって、かつそのオブジェクトはクローンではなく、かつ（疎なオブジェクトが上記のように処理される実施形態において）そのオブジェクトが疎ではない場合には、変更ブロック検出ステージ４０２で、ブロック６１４において、そのオブジェクトのすべてのブロックを候補チャンクとして扱う。
【００８０】
そのオブジェクトの作成チェックポイントが、チェックポイント範囲の下限よりも小さい場合（ブロック６０４でＮＯ）は、ブロック６１６において、変更ブロック検出スレッドプール／プロセス４０２で、チェックポイント範囲内で変更された候補ブロックをいずれも特定するために、オブジェクトツリーを「探索」する。
【００８１】
追加的または代替的に、いくつかの代替的実施形態において、ハードウェアベースのファイルシステム・マネージャ２２１は、変更されたオブジェクトのリストおよび／または変更されたブロックのリストを維持することができ、そして、変更ブロック検出ステージ４０２で、所与のチェックポイント範囲内でのファイルシステムにおける変更を特定するために、そのようなリスト（複数の場合もある）を使用することができる。
【００８２】
［データパッキング］
いくつかの例示的な実施形態において、ストレージ空間を節約するために、システムは、一般的に行われているように各データセグメントを別個のブロックに保存するのではなく、同じファイルシステムオブジェクトからの、または異なるファイルシステムオブジェクトからの、複数のデータセグメント（例えば、フルブロックよりも小さい、ｏノードおよび／またはユーザデータセグメント）を単一のブロックにパックすることを可能にすることができる。例えば、所定数までのｏノードを単一のブロックに保存することができ、または、複数のデータセグメントを（複数のファイルシステムオブジェクトに関連付けられたデータであっても）単一のブロックに保存することができる。
【００８３】
例えば、データセグメントのためにブロック全体が要求および取得されるのではなく、データセグメントのためにストレージ空間が要求される場合、システムは、そのデータセグメント用に１つ以上のセクタを要求および取得することができ、その場合、セクタは、必ずしもブロック境界の最初にあるとは限らず、既存の部分充填されたブロックから割り当てることができ、よって、複数のデータセグメントで単一のブロックを共有することができる。それらのセクタは、データセグメントのタイプによっては（例えば、リーフｏノードは、固定サイズである）、固定サイズの増分ずつ割り当てることができ、または、他のタイプのデータセグメント（例えば、可変サイズのユーザデータセグメント）に対しては、可変サイズの増分ずつ割り当てることができる。このようなパックされたブロックは、実質的に、複数のエンティティによって共有（すなわち、参照）されており、重複排除の結果としてブロックが複数のエンティティによって共有（すなわち、参照）され得るのと同様に、このようなパックされたブロックは、そのブロックに含まれる全てのデータセグメントが削除されるまでは、削除することができない。従って、重複排除によるブロックの共有と同様に、システムは、例えば、より詳細は後述する重複排除に用いられるのと同じ参照カウント機構を用いて、そのようなパックされたブロックに関連付けられた参照の数を追跡することが可能でなければならない。ブロックにデータセグメントが追加されるときには、参照カウントがインクリメントされ、ブロックからデータセグメントが削除されるときには、参照カウントがデクリメントされる。
【００８４】
いくつかの具体的な例示的実施形態では、ルートｏノードを処理するいくつかのユーティリティ（例えば、「ｆｉｘｆｓ」ユーティリティ）の修正を回避するために、ルートｏノードは、パックされることなく、個別のブロックに保存されることになるが、一方、固定サイズのリーフｏノードおよび可変サイズのデータブロックはパックすることができる。データブロックのパッキングに関して、所与のデータセグメントを保存するのに十分な空間が、既存の部分充填されたブロックにない場合には、そのデータセグメントの一部を既存の部分充填されたブロックに保存して、データセグメントの残り部分を新しいブロックに保存するのではなく、一般的には、そのデータセグメントは、新しいブロックに保存されることになるが、一部の実施形態では、データセグメントのそのような「分割」を許可する場合がある。
【００８５】
なお、パックされたブロックは、本明細書で解説するように、他のデータブロックの重複排除と同様にして重複排除され得るということに留意すべきである。
【００８６】
［ブロック参照カウント］
上述のように、重複排除と、さらにデータパッキングによって、ブロックは２つ以上のエンティティにより参照（共有）されることがある。従って、各ブロックへの参照を追跡するための機構が必要となる。典型的には、参照は、参照カウントを用いて追跡され、参照カウントがゼロに達しない限り（すなわち、ブロックを参照する最後のエンティティが削除されるまでは）、ブロックを削除することはできない。
【００８７】
本発明は、各ブロックの参照カウントを追跡するための、いずれかの特定の機構に限定されることはないものの、いくつかの実施形態では、参照カウントは、各ブロックに関連付けられた複数のビットを有するビットマップを用いて追跡される。いくつかの例示的な実施形態では、ビットマップは、既存の空き領域ビットマップ（ＦＳＢ）の修正版であり、ブロックのステータス（例えば、ブロックごとに２ビットを要する、オリジナルのＦＳＢにおける「使用中」と「空き」）だけではなく参照カウントも追跡するために使用される。便宜上、そのようなビットマップを、本明細書では「参照カウントビットマップ」または「ＲＣＢ」と呼ぶ。例えば、ＲＣＢは、ブロックごとに４ビットまたは８ビットを含むことができ、それらは、ブロックのステータス（例えば、「使用中」と「空き」）および参照カウントを表すように符号化される。以下は、ブロックごとに８ビットを用いる１つの例示的な符号化方式にすぎないが、これによって、重複排除と、ブロックごとに最大８個までのルートｏノードによるルートｏノード・パッキングの両方が可能となる。
−  値＝０：ブロックは未割り当てである
−  値＝［１，２３９（０ｘＥＦ）］：通常のブロックまたはスナップショット・ブロックの参照カウント
−  値＝［２４０（０ｘＦ０），２４７（０ｘＦ７）］：パックされたブロックの参照カウント（参照カウント１〜８）
−  値＝２４８（０ｘＦ８）〜２５５（０ｘＦＦ）：未使用／予備
【００８８】
あるいは、各ブロックの参照カウントを追跡するために、別個のビットマップまたは他のデータ構造を用いることができる。
【００８９】
［拡張重複排除］
いくつかの例示的な実施形態では、（例えば、インデックス付きチャンクに関連付けられたオリジナルのオブジェクトが削除または破棄されていることによって）インデックス付きチャンクが、もはや、そのオリジナルのオブジェクトに関連付けられていない場合に、重複排除のプロセスを放棄する必要はない。その代わりに、ファイルシステムごとに、インデキシングされたチャンク内のブロック（複数の場合もある）の連結リストを格納する別個のデータ構造を維持することができる。このデータ構造は、ファイルシステムごとのウェルノウン・オブジェクト内に保持することができる。上述のように、重複排除検出／インデキシング・エンジン２１３によって重複が検出された場合は、このデータ構造を用いて、インデックス付きチャンクに関連付けられたブロック（複数の場合もある）を見つけることができ、そしてこれを調べることで、そのブロックを候補チャンクの重複排除に使用可能かどうか（例えば、そのブロックの内容が変更されていないこと）を判断することができる。候補チャンクの重複排除のためにインデックス付きチャンクを使用する場合は、各ブロックに関連付けられた参照カウントがインクリメントされ、ブロックは、その後、それを参照しているものがなくならない限り、解放されることはできない。
【００９０】
［多層ファイルシステムにおける重複排除処理］
いくつかの例示的な実施形態では、ファイルシステムは、例えば、その全体が参照により本明細書に組み込まれる米国特許出願第１３／０４３８３７号（２３３７／１２８）に記載されているような多層ファイルシステム（ＭＴＦＳ）とすることができる。ＭＴＦＳでは、より高速なストレージ（メタデータ層）にファイルシステム・メタデータを配置することにより性能を向上させることができる。
【００９１】
好ましくは、重複排除では、ユーザオブジェクトが、メタデータ層のファイルシステム・メタデータに使用されるブロックを共有することは許可されず、もしこれが許可されると、そのブロックがファイルシステムのメタデータの一部ではなくなった後であっても、ユーザオブジェクトがメタデータ層のそのブロックに留まり得る可能性があるからである。
【００９２】
一般的に、メタデータがユーザデータ層のブロックを共有することは、許容され得るということに留意すべきである。
【００９３】
［耐障害性オブジェクトの処理］
いくつかの例示的な実施形態では、いわゆる「耐障害性」オブジェクトをサポートすることができ、この場合、耐障害性オブジェクトとは、そのオブジェクトの２つの完全なコピーが保存されているファイルシステムオブジェクトである。そのような耐障害性オブジェクトは、重複排除され得るものの、いずれかのブロックを２つのコピーで共有する（これによって、オブジェクトの耐障害性が基本的に取り除かれることになる）ようにして重複排除されてはならない。従って、耐障害性オブジェクトを重複排除する場合、システムは、２つのコピーがディスク上の同じデータを指すことにならないことを保証する。
【００９４】
［ＮＶＲＡＭ留保］
いくつかの例示的な実施形態において、重複排除の際に実行される変更オペレーションはいずれも、ＮＶＲＡＭにログ記録されない。これは、クラッシュした場合に、その後のロールバックによって、最後のチェックポイントの後でファイルシステムにおいて実施された全ての重複排除が取り消されることを意味する。
【００９５】
［複数のファイルシステムの重複排除］
複数のファイルシステムの重複排除は、例えば、複数のファイルシステムに単一のインデックスを用いる、またはファイルシステムごとに別個のインデックスを用いるなど、様々な方法で処理することができる。いくつかの例示的な実施形態では、後者のアプローチを用いる。
【００９６】
［スナップショット復元ファイル］
いくつかの例示的な実施形態において、オブジェクトのスナップショットコピーは、ライブファイルシステムにおいて新しいオブジェクト番号を割り当てるとともに、そのオブジェクトのｏノードツリーおよびブロックポインタをスナップショットのファイルと共有させることによって、復元することができる。各共有ブロックは、その参照カウントをインクリメントされることが必要となる。その最大参照カウントに達しているブロックがある場合、そのブロックのコピーを作成して、そのコピーブロックを指すようにライブオブジェクトが更新されることになる。この新しいオブジェクトが、ライブファイルシステム・ディレクトリツリーに挿入されて、必要であれば、オリジナルとスナップショット復元オブジェクトの両方を共存させることが可能となる。そのオブジェクトがスナップショット復元されたことを示すためのフラグを、ルートｏノードに含むことができる。ライブオブジェクトの変更は、必要に応じて共有ブロックの参照カウントをインクリメントしつつ、可能とすることができる。
【００９７】
［別のチャンクサイズでの重複排除］
上述の例示的な実施形態では、各チャンクは、所与のファイルシステムオブジェクトの単一のブロックを包含し、これにより、実施上の観点から、重複排除におけるいくつかの単純化が得られたが、それらは、各チャンクが複数のブロック（例えば、チャンクごとに４個または８個のブロック）を包含する代替的実施形態についての以下の説明から明らかになるであろう。
【００９８】
重複排除検出／インデキシング・エンジンは、基本的に、割り当てられた所与の容量のメモリに対して固定数のチャンクのインデキシングが可能であるので、チャンクサイズがより大きければ、より大きな量のデータのインデキシングが可能となるが、チャンクサイズがより大きいことによって、いくつかの状況において、重複の検出の可能性が低減し得る（例えば、４Ｋチャンクのデータのマッチングの可能性は、一般的に、２５６Ｋチャンクのデータのマッチングよりも高くなり得る）。
【００９９】
チャンクごとに複数のブロックを有する、いくつかの例示的な実施形態では、オブジェクトは、所定の方式に従ってチャンクに分割される。例えば、オブジェクトは、Ｎブロックのチャンクに順次分割されることができ、例えば、ブロック１〜Ｎ、ブロック（Ｎ＋１）〜２Ｎ、などである。
【０１００】
そのような複数ブロックのチャンクを上記の重複排除方式に統合するためには、各チャンクにチェックポイント番号が割り当てられなければならない。いくつかの例示的な実施形態では、チャンクのチェックポイント番号は、最も高いチェックポイント番号を有するブロックのチェックポイント番号である。
【０１０１】
また、複数ブロックのチャンクの重複排除の場合は、候補チャンクに関連付けられたオブジェクトは、その候補チャンクの全てのブロックへの参照を、インデックス付きチャンクからの対応する参照で置き換えるように、更新されなければならない。ブロック参照カウントは、一般的には、（チャンクごとではなく）ブロックごとに処理されることになり、最大参照カウントに達していないブロックのみが共有され得る。
【０１０２】
［代替的重複排除管理］
上述の例示的な実施形態では、重複排除は、変更されたチャンクの検出と重複チャンクの重複排除の両方が、バックグラウンド機能として実行される。しかしながら、本発明者らは、他のタイプの重複排除管理が可能であることを認識している。例えば、１つの代替例では、重複排除は、チャンクが変更されるときの書き込み過程と同期して実施することができ、その場合、書き込みが生じると、それらのチャンクは、重複排除検出／インデキシング・エンジンによってハッシュ化および処理されて、もし重複が検出された場合には、その重複排除が、書き込みオペレーションの一部として実行される。このような同期重複排除によって、書き込み過程に待ち時間が導入されることになり、ファイルシステムの性能にマイナスの影響を及ぼし得る。別の代替例では、重複排除は、「ハイブリッド」同期／非同期方式で実施することができ、この場合、書き込みが生じると、それらのチャンクは、（上記の同期ソリューションの場合と同様に）重複排除検出／インデキシング・エンジンによってハッシュ化および処理され、一方で、それらのチャンク自体は、（完全バックグラウンド重複排除プロセスの場合と同様に）ストレージに書き込まれ、もし重複が検出された場合には、その重複排除が、後にバックグラウンドで実行される。
【０１０３】
［ハッシュ生成器の代替的使用］
本発明のいくつかの実施形態では、重複排除に加えて、またはそれに代えて、ハッシュベースの他の機能のために、例えば、ＩＰｓｅｃ、ＳＭＢ２署名、ＨＣＰ外部移行、またはその他の、ＳＨＡ−２５６ハッシュを利用する機能のためなどに、ソフトウェアベースのシステムによって、さらに／またはハードウェアベースのシステムによって、ハッシュ生成器２２２を起動することができるように、ハードウェアベースのシステム２２０が構成される。
【０１０４】
［その他の諸事項］
上記では、重複排除およびデータパッキング機能について説明している。これらの機構は相互排他的、すなわち、いくつかの実施形態では、重複排除は実施され得るが、データパッキングは実施されず、他のいくつかの実施形態では、データパッキングは実施され得るが、重複排除は実施されない、と考えられるべきものであるが、さらに他の実施形態では、重複排除とデータパッキングの両方が実施され得る。重複排除とデータパッキングの両方に使用できる参照カウント機構（例えば、参照カウントビットマップ、または他の機構）が、例示的な実施形態において実現されることによって、例えば、一方または両方の機能の後の追加が可能となることが好ましい。
【０１０５】
上記では、例示的な実施形態について、ソフトウェアベースのシステム２１０に統合される市販の重複排除検出／インデキシング・エンジンを参照して説明しているが、様々な代替的実施形態によって、重複排除検出／インデキシング・エンジンは、ソフトウェアベースの重複排除マネージャの一部として、またはハードウェアベースのファイルシステム・マネージャの一部として、実装できることに留意すべきである。重複排除検出／インデキシング・エンジンが、ハードウェアベースのファイルシステム・マネージャの一部として実装される場合は、ハードウェアベースのファイルシステム・マネージャは、典型的には、候補チャンクのハッシュ値が生成された後に、そのハッシュ値をソフトウェアベースの重複排除マネージャに渡すことなく、重複排除検出／インデキシング・エンジンを起動することになる。
【０１０６】
図面において、２つ以上のエンティティに関わる通信、送信、またはその他のアクティビティを表すために、矢印が使用される場合があることに留意すべきである。両方向矢印は、一般に、双方向に発生し得るアクティビティ（例えば、一方向のコマンド／要求と、逆方向に戻される対応する応答、または、どちらかのエンティティによって開始されるピアツーピア通信）を示しているが、状況によっては、アクティビティが必ずしも双方向に発生しないことがある。単方向矢印は、一般に、専ら一方向または主として一方向のアクティビティを示しているが、ただし状況によっては、そのような方向性のあるアクティビティは、実際には双方向のアクティビティ（例えば、送信側から受信側へのメッセージと、受信側から送信側へ戻される確認応答、または、送信前の接続の確立、および送信後の接続の終了）を伴い得るということに留意すべきである。従って、特定の図面で特定のアクティビティを表すために使用される矢印の種類は、例示的なものであって、限定するものとみなされるべきではない。
【０１０７】
留意すべきことは、上記では、便宜上、見出しを使用しているが、それらは、決して本発明を限定するものと解釈されるべきではないということである。
【０１０８】
留意すべきことは、「クライアント」および「サーバ」といった用語が、本明細書において、本発明のいくつかの実施形態で使用され得るデバイスを記述するために用いられることがあるが、これらは、文脈上別段の解釈を要する場合を除き、本発明をいずれかの特定のデバイスタイプに限定するものと解釈されるべきではないということである。従って、デバイスとして、限定するものではないが、ノード、サーバ、コンピュータ、アプライアンス、または他のタイプのデバイス、を含むことができる。そのようなデバイスは、一般に、通信ネットワークを介して通信するための１つ以上のネットワークインタフェースと、デバイスの機能をそれにより実行するように構成されたプロセッサ（例えば、メモリおよび他の周辺機器を備えたマイクロプロセッサ、および／または専用ハードウェア）と、を備える。一般に、通信ネットワークとして、パブリックネットワークおよび／またはプライベートネットワークを含むことができ、それには、ローカルエリアネットワーク、広域ネットワーク、メトロポリタンエリアネットワーク、ストレージネットワーク、および／または他のタイプのネットワークを含むことができ、また、通信技術として、アナログ技術、デジタル技術、光技術、ワイヤレス技術（例えば、ブルートゥース）、ネットワーキング技術、インターネットワーキング技術などを採用することができるが、ただし、決してこれらに限定されない。
【０１０９】
さらに、留意すべきことは、デバイスは、通信プロトコルおよびメッセージ（例えば、デバイスによって作成、送信、受信、保存、および／または処理されるメッセージ）を用いることができ、そのようなメッセージは、通信ネットワークまたは通信媒体によって送信され得るということである。本発明は、文脈上別段の解釈を要する場合を除き、いずれかの特定の通信メッセージタイプ、通信メッセージフォーマット、または通信プロトコルに限定されるものと解釈されるべきではない。従って、一般に、通信メッセージとして、限定するものではないが、フレーム、パケット、データグラム、ユーザデータグラム、セル、または他のタイプの通信メッセージを含むことができる。文脈上別段の解釈を要する場合を除き、特定の通信プロトコルへの言及は例示的なものであり、理解されるべきことは、代替的実施形態では、適宜、そのような通信プロトコルの変形版（例えば、随時、策定され得るプロトコルの改良版もしくは拡張版）、または、周知の、もしくは将来開発される他のプロトコルを採用することができるということである。
【０１１０】
また、留意すべきことは、本明細書では、本発明の種々の態様を明らかにするために、論理フローが記載されることがあるが、これらは、本発明をいずれかの特定の論理フローまたは論理実装に限定するものと解釈されるべきではないということである。記載されるロジックは、全体的な結果を変えることなく、あるいは本発明の真の範囲から逸脱することなく、いくつかの異なる論理ブロック（例えば、プログラム、モジュール、関数、またはサブルーチン）に分割することができる。論理要素は、全体的な結果を変えることなく、あるいは本発明の真の範囲から逸脱することなく、しばしば、追加、変更、省略され得るとともに、異なる順序で実行されることができ、または、いくつかの異なる論理構成体（例えば、論理ゲート、ルーピングプリミティブ、条件付きロジック、およびその他の論理構成体）を用いて実装され得る。
【０１１１】
上述の例示的な実施形態は、プロセッサ（例えば、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ、または汎用コンピュータ）と共に用いられるコンピュータプログラムロジックと、ハードウェアベースのロジックと、その両方を備える。ハードウェアベースのロジックとして、プログラマブルロジックデバイス（例えば、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、または他のＰＬＤ）と共に用いられるプログラマブルロジック、ディスクリート部品、集積回路（例えば、特定用途向け集積回路（ＡＳＩＣ））、またはこれらの任意の組合せを含む他のいずれかの手段、を含むことができる。記載した機能の一部または全てを実現するコンピュータプログラムロジックは、一般に、コンピュータプログラム命令のセットとして実装されて、コンピュータ実行形式に変換され、コンピュータ読取り可能な媒体などに保存されて、オペレーティングシステムの制御の下でマイクロプロセッサにより実行される。記載した機能の一部または全てを実現するハードウェアベースのロジックは、１つ以上の適切に構成されたＦＰＧＡを用いて実装することができる。
【０１１２】
本明細書で前述した機能の全てまたは一部を実現するコンピュータプログラムロジックは、様々な形式で具現化することができ、それには、ソースコード形式、コンピュータ実行形式、各種中間形式（例えば、アセンブラ、コンパイラ、リンカ、またはロケータにより生成される形式）が含まれるが、ただし、決してこれらに限定されない。ソースコードは、様々なオペレーティングシステムまたはオペレーティング環境で使用される各種プログラミング言語（例えば、オブジェクトコード、アセンブリ言語、または、フォートラン、Ｃ、Ｃ＋＋、ＪＡＶＡ、もしくはＨＴＭＬなどの高級言語）のいずれかで実現される一連のコンピュータプログラム命令を含むことができる。ソースコードで、各種データ構造および通信メッセージを定義および使用することができる。ソースコードは、（例えば、インタプリタによって）コンピュータ実行可能な形式とすることができ、またはソースコードは、コンピュータ実行可能な形式に（例えば、トランスレータ、アセンブラ、またはコンパイラによって）変換することができる。
【０１１３】
本明細書で前述した機能の全てまたは一部を実現するコンピュータプログラムロジックは、単一のプロセッサで、時をずらして（例えば、並行して）実行することができ、または複数のプロセッサで、同時に、もしくは時をずらして実行することができ、さらに、単一のオペレーティングシステムプロセス／スレッドで、またはいくつかの異なるオペレーティングシステムプロセス／スレッドで、実行することができる。従って、「コンピュータプロセス」という用語は、いくつかの異なるコンピュータプロセスが同じもしくは異なるプロセッサ上で実行されるかどうかに関わりなく、また、いくつかの異なるコンピュータプロセスが同じオペレーティングシステムプロセス／スレッドもしくは異なるオペレーティングシステムプロセス／スレッドで実行されるかどうかに関わりなく、一般的に、コンピュータプログラム命令のセットの実行を指す。
【０１１４】
コンピュータプログラムは、半導体メモリデバイス（例えば、ＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＥＰＲＯＭ、またはフラッシュプログラマブルＲＡＭ）、磁気メモリデバイス（例えば、ディスケット、または固定ディスク）、光メモリデバイス（例えば、ＣＤ−ＲＯＭ）、ＰＣカード（例えば、ＰＣＭＣＩＡカード）、または他のメモリデバイスなど、有形の記憶媒体内に、永久的または一時的に、任意の形式（例えば、ソースコード形式、コンピュータ実行形式、または中間形式）で、保持することができる。コンピュータプログラムは、各種通信技術のいずれかを用いてコンピュータに送信可能な信号において、任意の形式で保持することができ、そのような通信技術には、アナログ技術、デジタル技術、光技術、ワイヤレス技術（例えば、ブルートゥース）、ネットワーキング技術、インターネットワーキング技術が含まれるが、ただし、決してこれらに限定されない。コンピュータプログラムは、印刷もしくは電子ドキュメントが添付されたリムーバブル記憶媒体（例えば、市販ソフトウェア）として任意の形式で配布されることができ、またはコンピュータシステムで（例えば、システムＲＯＭ、もしくは固定ディスクに）プリロードされることができ、またはサーバもしくは電子掲示板から通信システム（例えば、インターネット、もしくはワールドワイドウェブ）を介して配布されることができる。
【０１１５】
本明細書で前述した機能の全てまたは一部を実現するハードウェアロジック（プログラマブルロジックデバイスと共に用いられるプログラマブルロジックを含む）は、伝統的な手作業による方法を用いて設計することができ、またはコンピュータ支援設計（ＣＡＤ）、ハードウェア記述言語（例えば、ＶＨＤＬ、またはＡＨＤＬ）、もしくはＰＬＤプログラミング言語（例えば、ＰＡＬＡＳＭ、ＡＢＥＬ、またはＣＵＰＬ）などの各種ツールを使用して、設計、キャプチャ、シミュレーション、もしくは電子ドキュメント化することができる。
【０１１６】
プログラマブルロジックは、半導体メモリデバイス（例えば、ＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＥＰＲＯＭ、またはフラッシュプログラマブルＲＡＭ）、磁気メモリデバイス（例えば、ディスケット、または固定ディスク）、光メモリデバイス（例えば、ＣＤ−ＲＯＭ）、または他のメモリデバイスなど、有形の記憶媒体内に、永久的または一時的に保持することができる。プログラマブルロジックは、各種通信技術のいずれかを用いてコンピュータに送信可能な信号に保持することができ、そのような通信技術には、アナログ技術、デジタル技術、光技術、ワイヤレス技術（例えば、ブルートゥース）、ネットワーキング技術、インターネットワーキング技術が含まれるが、ただし、決してこれらに限定されない。プログラマブルロジックは、印刷もしくは電子ドキュメントが添付されたリムーバブル記憶媒体（例えば、市販ソフトウェア）として配布されることができ、またはコンピュータシステムで（例えば、システムＲＯＭ、もしくは固定ディスクに）プリロードされることができ、またはサーバもしくは電子掲示板から通信システム（例えば、インターネット、もしくはワールドワイドウェブ）を介して配布されることができる。当然のことながら、本発明は、一部の実施形態では、ソフトウェア（例えば、コンピュータプログラム・プロダクト）とハードウェアの両方の組み合わせとして実装することができる。本発明は、さらに別の実施形態では、全体がハードウェアとして、または全体がソフトウェアとして、実装される。
【０１１７】
本発明は、発明の真の範囲から逸脱することなく、他の具体的な形態で実施することができ、また、本明細書の教示に基づいて、数多くの変形および変更が、当業者には明らかであろう。「発明」についての言及は、本発明の例示的な実施形態について述べるものであり、文脈上別段の解釈を要する場合を除き、本発明のあらゆる実施形態について言及しているものと解釈されるべきではない。記載した実施形態は、あらゆる点において、単なる例示であって、限定するものではないと考えられるべきものである。
【図１】
0005925968.tif 000002
【図２】
0005925968.tif 000003
【図３】
0005925968.tif 000004
【図４】
0005925968.tif 000005
【図５】
0005925968.tif 000006
【図６】
0005925968.tif 000007