(57)【特許請求の範囲】
【請求項１】
ファイルシステムオブジェクトをクローニングすることをコンピュータに実行させるためのコンピュータプログラムであって、
前記ファイルシステムオブジェクトは、ルートノードと、間接ノードと、少なくとも１つのデータブロックと、前記ファイルシステムオブジェクトの前記ルートノードに記憶されるポインタのセットであるポインタセットとを含んでおり、
前記ファイルシステムオブジェクトの前記ルートノードの前記ポインタセットは、前記少なくとも１つのデータブロックを、前記ファイルシステムオブジェクトの前記ルートノードの前記ポインタセットにより参照された前記間接ノードを介して参照し、
前記コンピュータプログラムは、
第１のスナップショットオブジェクトをファイルストレージシステムに作成し、前記第１のスナップショットオブジェクトに前記ファイルシステムオブジェクトの前記ポインタセットのコピーを記憶することと、
書込み可能なクローンオブジェクトを前記ファイルストレージシステムに作成し、前記クローンオブジェクトに前記ファイルシステムオブジェクトの前記ポインタセットのコピーを記憶すること
とをコンピュータに実行させ、
前記第１のスナップショットオブジェクトと前記クローンオブジェクトが、それぞれ、前記ポインタセットがコピーされるルートノードを含み、
前記ファイルシステムオブジェクトの前記ルートノードの前記ポインタセット、前記第１のスナップショットオブジェクトの前記ルートノードの前記ポインタセット、及び、前記クローンオブジェクトの前記ルートノードの前記ポインタセットが、同じ間接ノードを参照することで、前記第１のスナップショットオブジェクト及び前記クローンオブジェクトが、前記参照された間接ノードと前記少なくとも１つの参照されたデータブロックを前記ファイルシステムオブジェクトと共有し、
前記ファイルシステムオブジェクト及び前記クローンオブジェクトが、書込み可能な前記第１のスナップショットオブジェクトになり、前記第１のスナップショットオブジェクトによって表されるオブジェクトのコピーからの変化を記憶し、
前記第１のスナップショットオブジェクトを管理するメタデータが、前記第１のスナップショットオブジェクトを参照するオブジェクトの数を示す参照カウントを記憶する、
コンピュータプログラム。
【請求項２】
メタデータが前記ファイルシステムオブジェクトと前記クローンオブジェクトにおいて維持され、前記第１のスナップショットオブジェクトが前記ファイルシステムオブジェクト及び前記クローンオブジェクトに関連し、前記ファイルシステムオブジェクト及び前記クローンオブジェクトが前記第１のスナップショットオブジェクトに関連し、
前記ファイルシステムオブジェクトにおいて維持されるメタデータと前記クローンオブジェクトにおいて維持されるメタデータが前記第１のスナップショットオブジェクトに対する参照を記憶する、
請求項１に記載のコンピュータプログラム。
【請求項３】
前記第１のスナップショットオブジェクトと前記クローンオブジェクトの作成に際し、前記ファイルシステムオブジェクトのデータストリームが、前記ファイルシステムオブジェクトの前記ルートノードと前記クローンオブジェクトの前記ルートノードとにおいて、その関連した第１のスナップショットオブジェクトのデータストリームから分岐できる最も早いチェックポイントを定義するチェックポイント番号である最古のチェックポイント番号として、前記ファイルシステムオブジェクトの前記ルートノードは、前記ファイルシステムオブジェクトの最終変更のチェックポイントを記録する現在のチェックポイント番号を記憶する、
請求項１又は２に記載のコンピュータプログラム。
【請求項４】
前記第１のスナップショットオブジェクト及び前記クローンオブジェクトの作成に際し、前記第１のスナップショットオブジェクトの前記ルートノードにおける前記最古のチェックポイント番号として、前記ファイルシステムオブジェクトがすでにクローンであった場合、前記ファイルシステムオブジェクトの前記ルートノードに記憶された前記現在のチェックポイント番号がさらに記憶される、
請求項３に記載のコンピュータプログラム。
【請求項５】
前記ファイルストレージシステムは前記第１のスナップショットオブジェクトに対応しライブファイルシステムにおけるオブジェクトであるライブファイルオブジェクトを含み、それぞれのオブジェクトはユーザデータブロックの番号と関連しており、
前記コンピュータプログラムは、
前記第１のスナップショットオブジェクトにより所有され、前記ライブファイルオブジェクトと共有される各々のユーザデータブロックに関して、前記ユーザデータブロックの所有権を前記ライブファイルオブジェクトに移すことと、
このような転送に続いて、前記ファイルストレージシステムから前記第１のスナップショットオブジェクトを排除することを含む、ファイルのデクローニングと
を更にコンピュータに実行させる請求項３又は４に記載のコンピュータプログラム。
【請求項６】
各オブジェクトはいくつかのブロックポインタを含み、
各ポインタはそれぞれのチェックポイント番号に関連しており、
前記ユーザデータブロックの所有権を前記ライブファイルオブジェクトへ移すことは、
前記第１のスナップショットオブジェクトにおいて前記ブロックポインタを少なくすることと、
前記ライブファイルオブジェクトにおける前記対応するブロックポインタの前記チェックポイント番号を前記ライブファイルオブジェクトの前記クローン後に入るチェックポイント番号に設定することを含む、
請求項５に記載のコンピュータプログラム。
【請求項７】
前記第１のスナップショットオブジェクトが隠しファイルシステムオブジェクトである、
請求項１乃至６のうちのいずれか１項に記載のコンピュータプログラム。
【請求項８】
前記クローンオブジェクトが作成された前記ファイルシステムオブジェクトのサイズが前記クローンオブジェクトに起因すると判断すること
を更にコンピュータに実行させる請求項１乃至７のうちのいずれか１項に記載のコンピュータプログラム。
【請求項９】
前記書込み可能なファイルシステムオブジェクト又は前記書込み可能なクローンオブジェクトを変更する際、前記変更を記憶するために少なくとも１つのデータブロックを割り当て、前記少なくとも１つの割り当てられたデータブロックを前記変更後のオブジェクトに関連付けることを更にコンピュータに実行させ、
前記変更後のオブジェクトが、変更後のポインタセットを含む、
請求項１乃至８のうちのいずれか１項に記載のコンピュータプログラム。
【請求項１０】
前記ファイルストレージシステムにおいて、第２のスナップショットオブジェクトを作成し、前記第２のスナップショットオブジェクトに前記変更後のポインタセットのコピーを記憶することと、
前記ファイルストレージシステムにおいて、書込み可能な第２のクローンオブジェクトを作成し、前記第２のクローンオブジェクトに前記変更後のポインタセットのコピーを記憶すること
を更にコンピュータに実行させる請求項９に記載のコンピュータプログラム。
【請求項１１】
前記第２のスナップショットオブジェクトに、前記変更後のオブジェクトに対する参照、前記第２のクローンオブジェクトに対する参照、及び前記第１のスナップショットオブジェクトに対する参照を記憶することと、
前記変更後のファイルシステムオブジェクトに、前記第２のスナップショットオブジェクトに対する参照を記憶することと、
前記第２のクローンオブジェクトに、前記第２のスナップショットオブジェクトに対する参照を記憶すること
を更にコンピュータに実行させる請求項１０に記載のコンピュータプログラム。
【請求項１２】
前記第１のスナップショットオブジェクトを使用して、前記ファイルシステムオブジェクトの別のクローンを作成すること
を更にコンピュータに実行させる請求項１乃至１１のうちのいずれか１項に記載のコンピュータプログラム。
【請求項１３】
前記第１のスナップショットオブジェクトが、読取り専用データストリームスナップショットオブジェクトである、
請求項１乃至１２のうちのいずれか１項に記載のコンピュータプログラム。
【請求項１４】
ファイルシステムオブジェクトをクローニングするために構成されたファイルストレージシステムであって、
前記ファイルシステムオブジェクトが、ルートノード、間接ノードと、少なくとも１つのデータブロックと、前記ファイルシステムオブジェクトの前記ルートノードに記憶されるポインタのセットであるポインタセットとを含んでおり、
前記ファイルシステムオブジェクトの前記ルートノードの前記ポインタセットは、前記少なくとも１つのデータブロックを、前記ファイルシステムオブジェクトの前記ルートノードの前記ポインタセットにより参照された前記間接ノードを介して参照し、
前記ファイルストレージシステムは、
少なくとも１つの記憶デバイスと、
前記少なくとも１つの記憶デバイスと通信するプロセッサであって、前記ファイルストレージシステムに第１のスナップショットオブジェクトを作成し、前記第１のスナップショットオブジェクトに前記ファイルシステムオブジェクトの前記ポインタセットのコピーを格納することと、前記ファイルストレージシステムにおいて書込み可能なクローンオブジェクトを作成し、前記クローンオブジェクトに前記ファイルシステムオブジェクトの前記ポインタセットのコピーを格納することとを実行するプロセッサと
を備え、
前記第１のスナップショットオブジェクトと前記クローンオブジェクトが、それぞれ、前記ファイルシステムオブジェクトの前記ルートノードの前記ポインタセットがコピーされるルートノードを含み、
前記ファイルシステムオブジェクトの前記ルートノードの前記ポインタセット、前記第１のスナップショットオブジェクトの前記ルートノードの前記ポインタセット、及び、前記クローンオブジェクトの前記ルートノードの前記ポインタセットが、同じ間接ノードを参照することで、前記第１のスナップショットオブジェクト及び前記クローンオブジェクトが、前記参照された間接ノードと前記少なくとも１つの参照されたデータブロックを前記ファイルシステムオブジェクトと共有し、
前記ファイルシステムオブジェクト及び前記クローンオブジェクトが、書込み可能な前記第１のスナップショットオブジェクトになり、前記第１のスナップショットオブジェクトによって表されるオブジェクトのコピーからの変化を記憶し、
前記第１のスナップショットオブジェクトを管理するメタデータが、前記第１のスナップショットオブジェクトを参照するオブジェクトの数を示す参照カウントを記憶する、
ファイルストレージシステム。
【請求項１５】
メタデータが前記ファイルシステムオブジェクトと前記クローンオブジェクトにおいて維持され、前記第１のスナップショットオブジェクトが前記ファイルシステムオブジェクト及び前記クローンオブジェクトに関連し、前記ファイルシステムオブジェクト及び前記クローンオブジェクトが前記第１のスナップショットオブジェクトに関連し、
前記ファイルシステムオブジェクトにおいて維持されるメタデータと前記クローンオブジェクトにおいて維持されるメタデータの各々が前記第１のスナップショットオブジェクトの参照を記憶する、
請求項１４に記載のファイルストレージシステム。
【請求項１６】
前記第１のスナップショットオブジェクトと前記クローンオブジェクトの作成に際し、前記ファイルシステムオブジェクトのデータストリームが、前記ファイルシステムオブジェクトの前記ルートノードと前記クローンオブジェクトの前記ルートノードとにおいて、その関連した第１のスナップショットオブジェクトのデータストリームから分岐できる最も早いチェックポイントを定義するチェックポイント番号である最古のチェックポイント番号として、前記ファイルシステムオブジェクトの前記ルートノードは、前記ファイルシステムオブジェクトの最終変更のチェックポイントを記録する現在のチェックポイント番号を記憶する、
請求項１４又は１５に記載のファイルストレージシステム。
【請求項１７】
前記第１のスナップショットオブジェクト及び前記クローンオブジェクトの作成に際し、前記第１のスナップショットオブジェクトの前記ルートノードにおける前記最古のチェックポイント番号として、前記ファイルシステムオブジェクトがすでにクローンであった場合、前記ファイルシステムオブジェクトの前記ルートノードに記憶された前記現在のチェックポイント番号がさらに記憶される、
請求項１６に記載のファイルストレージシステム。
【請求項１８】
前記ファイルストレージシステムは前記第１のスナップショットオブジェクトに対応しライブファイルシステムにおけるオブジェクトであるライブファイルオブジェクトを含み、それぞれのオブジェクトはユーザデータブロックの番号と関連しており、
前記プロセッサは、
前記第１のスナップショットオブジェクトにより所有され、前記ライブファイルオブジェクトと共有される各々のユーザデータブロックに関して、前記ユーザデータブロックの所有権を前記ライブファイルオブジェクトに移すことと、
このような転送に続いて、前記ファイルストレージシステムから前記第１のスナップショットオブジェクトを排除することを含む、ファイルのデクローニングと
を更に実行する請求項１６又は１７に記載のファイルストレージシステム。
【請求項１９】
各オブジェクトはいくつかのブロックポインタを含み、
各ポインタはそれぞれのチェックポイント番号に関連しており、
前記ユーザデータブロックの所有権を前記ライブファイルオブジェクトへ移すために、前記プロセッサは、
前記第１のスナップショットオブジェクトにおいて前記ブロックポインタを少なくすることと、
前記ライブファイルオブジェクトにおける前記対応するブロックポインタの前記チェックポイント番号を前記ライブファイルオブジェクトの前記クローン後に入るチェックポイント番号に設定すること
とを実行する請求項１８に記載のファイルストレージシステム。
【請求項２０】
前記第１のスナップショットオブジェクトが隠しファイルシステムオブジェクトである、
請求項１４乃至１９のうちのいずれか１項に記載のファイルストレージシステム。
【請求項２１】
前記プロセッサが、前記クローンオブジェクトが作成された前記ファイルシステムオブジェクトのサイズは前記クローンオブジェクトに起因すると判断する、
請求項１４乃至２０のうちのいずれか１項に記載のファイルストレージシステム。
【請求項２２】
前記書込み可能なファイルシステムオブジェクト又は前記書込み可能なクローンオブジェクトを変更する際、前記プロセッサが、前記変更を格納するために少なくとも１つのデータブロックを割り当て、前記少なくとも１つの割り当てられたデータブロックを前記変更後のオブジェクトに関連付け、
前記変更後のオブジェクトが、変更後のポインタセットを含む
請求項１４乃至２１のうちのいずれか１項に記載のファイルストレージシステム。
【請求項２３】
前記プロセッサが、前記ファイルストレージシステムにおいて第２のスナップショットオブジェクトを作成し、前記第２のスナップショットオブジェクトに前記変更後のポインタセットのコピーを格納し、前記ファイルストレージシステムにおいて、書込み可能な第２のクローンオブジェクトを作成し、前記第２のクローンオブジェクトに前記変更後のポインタセットのコピーを格納する、
請求項２２に記載のファイルストレージシステム。
【請求項２４】
前記プロセッサが、前記第２のスナップショットオブジェクトに、前記変更後のオブジェクトに対する参照、前記第２のクローンオブジェクトに対する参照、及び前記第１のスナップショットオブジェクトに対する参照を格納し、前記変更後のファイルシステムオブジェクトに、前記第２のスナップショットオブジェクトに対する参照を格納し、前記第２のクローンオブジェクトに、前記第２のスナップショットオブジェクトに対する参照を格納する
請求項２３に記載のファイルストレージシステム。
【請求項２５】
前記プロセッサが、前記第１のスナップショットオブジェクトを使用して前記ソースオブジェクトの別のクローンを作成する、
請求項１４乃至２４のうちのいずれか１項に記載のファイルストレージシステム。
【請求項２６】
前記第１のスナップショットオブジェクトが、読取り専用データストリームスナップショットオブジェクトである、
請求項１４乃至２５のうちのいずれか１項に記載のファイルストレージシステム。
【発明の詳細な説明】
【関連出願の相互参照】
【０００１】
本特許出願は、Ｄａｎｉｅｌ  Ｊ．Ｎ．Ｐｉｃｋｅｎ及びＮｅｉｌ  Ｂｅｒｒｉｎｇｔｏｎの名前で、２０１０年１１月２２日に出願されたＦＩＬＩＮＧ  ＣＬＯＮＩＮＧ  ＩＮ  Ａ  ＤＡＴＡ  ＳＴＯＲＡＧＥ  ＳＹＳＴＥＭという名称の米国仮特許出願第６１／４１５，９２８号(代理人整理番号第２３３７／１２６)の利益を主張し、その全体が参照により本明細書に組み込まれる。
【０００２】
本特許出願は、以下の特許出願に関連するものであり、そのそれぞれが、その全体において参照により本明細書に組み込まれる。
Ｃｈｒｉｓｔｏｐｈｅｒ  Ｊ．Ａｓｔｏｎ，Ｓｉｍｏｎ  Ｌ．Ｂｅｎｈａｍ及びＮｅｉｌ  Ｂｅｒｒｉｎｇｔｏｎの名前で、２００８年６月３０日に出願されたＭＵＬＴＩ−ＷＡＹ  ＣＨＥＣＫＰＯＩＮＴＳ  ＩＮ  Ａ  ＤＡＴＡ  ＳＴＯＲＡＧＥ  ＳＹＳＴＥＭという名称の米国特許出願第１２／１６４，７３０号(代理人整理番号第２３３７／１１０)であり、本特許出願は、Ｃｈｒｉｓｔｏｐｈｅｒ  Ｊ．Ａｓｔｏｎの名前で、２００８年１月１６日に出願されたＶＡＬＩＤＡＴＩＮＧ  ＯＢＪＥＣＴＳ  ＩＮ  Ａ  ＤＡＴＡ  ＳＴＯＲＡＧＥ  ＳＹＳＴＥＭという名称の米国特許出願第１２／０１５，１９２号(代理人整理番号第２３３７／１１３)の一部継続出願であるため、その優先権を主張する。
【０００３】
本特許出願はまた、１つ以上の以下の特許出願に関連する可能性があり、そのそれぞれが、その全体において参照により本明細書に組み込まれる。
これと同一の日付に出願されたＤＹＮＡＭＩＣ  ＷＲＩＴＥ  ＢＡＬＡＮＣＩＮＧ  ＩＮ  Ａ  ＤＡＴＡ  ＳＴＯＲＡＧＥ  ＳＹＳＴＥＭという名称の米国特許出願（代理人整理番号第２３３７／１１１）；
Ｊｏｈｎ  Ｃ．Ｈｏｌｔｏｍの名前で、２００８年１０月９日に出願されたＳＹＳＴＥＭ，ＤＥＶＩＣＥ，ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＶＡＬＩＤＡＴＩＮＧ  ＤＡＴＡ  ＳＴＲＵＣＴＵＲＥＳ  ＩＮ  Ａ  ＳＴＯＲＡＧＥ  ＳＹＳＴＥＭという名称の米国特許出願第１２／２４８，３００号（代理人整理番号第２３３７／１１７）であり、これは、２００７年１０月１２日に出願されたＳＹＳＴＥＭ，ＤＥＶＩＣＥ，ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＶＡＬＩＤＡＴＩＮＧ  ＤＡＴＡ  ＳＴＲＵＣＴＵＲＥＳ  ＩＮ  Ａ  ＳＴＯＲＡＧＥ  ＳＹＳＴＥＭという名称の米国仮特許出願第６０／９７９，５６１号(代理人整理番号第２３３７／１１８)の利益を主張する;
２００１年６月１２日に出願されたＡＰＰＡＲＡＴＵＳ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＨＡＲＤＷＡＲＥ  ＩＭＰＬＥＭＥＮＴＡＴＩＯＮ  ＯＲ  ＡＣＣＥＬＥＲＡＴＩＯＮ  ＯＦ  ＯＰＥＲＡＴＩＮＧ  ＳＹＳＴＥＭ  ＦＵＮＣＴＩＯＮＳという名称の米国特許出願第０９／８７９，７９８号であり、現在は米国特許第６，８２６，６１５号（代理人整理番号第２３３７／１０３）;
２００４年７月１２日に出願されたＡＰＰＡＲＡＴＵＳ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＨＡＲＤＷＡＲＥ  ＩＭＰＬＥＭＥＮＴＡＴＩＯＮ  ＯＲ  ＡＣＣＥＬＥＲＡＴＩＯＮ  ＯＦ  ＯＰＥＲＡＴＩＮＧ  ＳＹＳＴＥＭ  ＦＵＮＣＴＩＯＮＳという名称の米国特許出願第１０／８８９，１５８号（代理人整理番号第２３３７／１０８）；
Ｇｅｏｆｆｒｅｙ  Ｓ．Ｂａｒｒａｌｌ等の名前で２００２年１１月１日に出願されたＡＰＰＡＲＡＴＵＳ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＨＡＲＤＷＡＲＥ−ＢＡＳＥＤ  ＦＩＬＥ  ＳＹＳＴＥＭという名称の米国特許出願第１０／２８６，０１５号（代理人整理番号第２３３７／１０４）；及び
Ｇｅｏｆｆｒｅｙ  Ｓ．Ｂａｒｒａｌｌ等の名前で２００７年８月２０日に出願されたＡＰＰＡＲＡＴＵＳ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＨＡＲＤＷＡＲＥ−ＢＡＳＥＤ  ＦＩＬＥ  ＳＹＳＴＥＭという名称の米国特許出願第１１／８４１，３５３号（代理人整理番号第２３３７／１１７）。
【技術分野】
【０００４】
本発明は、データストレージシステムに関し、より詳細にはデータストレージシステムにおいてファイルをクローニング及びデクローニングすることに関する。
【背景】
【０００５】
Ｇｅｏｆｆｒｅｙ  Ｓ．Ｂａｒｒａｌｌ等の名前で２００２年１１月１日に出願されたＡｐｐａｒａｔｕｓ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｈａｒｄｗａｒｅ−Ｂａｓｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍという名称の米国特許出願第１０／２８６，０１５号（代理人整理番号第２３３７／１０４)、及びＧｅｏｆｆｒｅｙ  Ｓ．Ｂａｒｒａｌｌ等の名前で２００７年８月２０日に出願されたＡｐｐａｒａｔｕｓ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｈａｒｄｗａｒｅ−Ｂａｓｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍという名称の米国特許出願第１１／８４１，３５３号（代理人整理番号第２３３７／１１７）は共に、その全体が参照により本明細書に組み込まれ、様々なファイルシステム構造を記載しており、その中でも特にファイルサーバがファイルシステムの２つのコピーを維持する、すなわちファイルシステムの現行バリエーションと、ファイルシステムの以前の「チェックポイント」バージョンとを可能にするファイルシステム構造を記載している。具体的にはファイルシステムは、ツリー構造を使用して維持され、このツリー構造には、左手側（ＬＨＳ）と右手側（ＲＨＳ）と呼ばれる実際には一組の構造である特定のルートノードが含まれる。実際には、一方の側を使用してファイルシステムの「チェックポイント」コピーを保持し、他方の側を使用して継続中のファイルシステムの管理（ファイルシステムオブジェクトの作成、削除及び変更を含む）を行なう。その時々で、２つの側の役割が逆になることで、継続中のファイルシステムの管理に使用されていた構造の側を使用して「チェックポイント」が取得され、継続中のファイルシステムの管理は、先の「チェックポイント」を保持する構造の側を使用して続けられる。２つのいわゆる動的スーパーブロックが維持されることで、ファイルシステムの現行バージョンとチェックポイントバージョンの形跡を保持する。
【０００６】
「チェックポイント」の１つの目的は、継続するファイルシステムを管理する際、万一エラーが起こった場合に備えてファイルシステムのコピーを記憶することである。特定の状況下では、ファイルシステムが、その「チェックポイント」型に戻される場合もある。このようなシステムにおける１つのリスクは、現行バージョンのファイルシステムと、「チェックポイント」バージョンのファイルシステムの両方が損なわれる可能性があることである。別のリスクは、情報の重要な部分が、排除あるいは変更され、現行バージョンのファイルシステムも、「チェックポイント」バージョンのファイルシステムも、情報の元の部分を含まなくなることである。
【例示の実施形態の概要】
【０００７】
本発明の特定の実施形態では、ファイルクローニング機構を利用することで、例えばユーザがファイルのコピーを作成する際、ファイルシステム内にファイルのコピー（クローン）を迅速に作成することを可能にする。例示の実施形態において、ソースオブジェクトのクローンは、少なくとも最初は、このソースオブジェクトの多様な要素（例えば間接オーノード、直接オーノード及びデータブロック）に対する参照を含む特定の構造によって表される。読取り専用クローンも可変クローンも共に作成することができる。ソースファイルと、そのクローンは、最初、このような要素を共有しており、ソースファイルまたは可変クローンが変更される際、変更されない要素を共有し続ける。ユーザデータブロックやメタデータブロックは、いずれも、クローンが作成される時にコピーされる必要があるソースファイルに関連するデータストリーム（すなわち、間接／直接オーノード）を表していない。このようなファイルクローニングの一部の特徴には、以下が含まれる。
−ファイルシステムオブジェクトのデータストリームを、ソースオブジェクトのデータストリームのサイズに関わらず比較的固定された時間量で、迅速に効果的にクローンすることができ、これは、このデータストリームを構成するいずれのユーザデータブロックもコピーする必要がないためである。また、データストリーム（すなわち間接／直接オーノード）を表すいずれのメタブロックもコピーする必要がない。極めて少ない一定の数のメタブロックが変化させられる。
−クローン後の／クローンオブジェクトにＩ／Ｏを対処させる複雑さは、通常のオブジェクトに匹敵する。
−特定のファイルやクローンをクローンすることができる回数は、ファイルシステム内のフリースペースの大きさによってのみ制限される。
−特定のファイルシステムが支持することができるクローンの数は、ファイルシステム内のフリースペースの大きさによってのみ制限される。
−このファイルクローニングは、固有のファイル重複排除特性を有しており、ソースファイルの完全なコピーを作成し、その後に重複排除を行なうのではなく、そのクローンは基本的に、ソースファイルと共にデータ及びメタデータブロックを共有する重複排除されたファイルとして作成される。
−共有されるブロックの破損は、複数のファイルに影響を与えることになるが、データの破損は、冗長記憶装置（すなわちＲＡＩＤ制御装置）及び他の機構によって軽減される。
【０００８】
本発明の一態様によれば、ファイルストレージシステムにおいてソースファイルシステムオブジェクトをクローニングするための方法が提供される。ソースファイルシステムオブジェクトは、少なくとも１つのデータブロックと、この少なくとも１つのデータブロックを直接または間接的に指すポインタのセットを含む。方法は、ファイルストレージシステム内に読取り専用データ・ストリーム・スナップショットオブジェクトを作成し、データ・ストリーム・スナップショットオブジェクト内にこのポインタセットのコピーを記憶すること、ファイルストレージシステム内に可変クローンオブジェクトを作成し、このポインタセットのコピーをクローンオブジェクトに記憶することとを含んでおり、データ・ストリーム・スナップショットオブジェクト及びクローンオブジェクトは、少なくとも１つのデータブロックをソースファイルシステムオブジェクトと共有しており、データ・ストリーム・スナップショットオブジェクトと、クローンオブジェクトに対して少なくとも１つのデータブロックの別々のコピーを形成することはなく、ソースファイルシステムオブジェクト及びクローンオブジェクトは事実上、可変バージョンのデータ・ストリーム・スナップショットオブジェクトになり、データ・ストリーム・スナップショットオブジェクトによって表されるオブジェクトの読取り専用コピーからの変化を事実上記憶する。
【０００９】
本発明の別の態様によれば、ソースファイルシステムオブジェクトを含むファイルシステムオブジェクトをファイルストレージシステムにおいてクローニングする装置が提供される。ソースファイルシステムオブジェクトは、少なくとも１つのデータブロックと、この少なくとも１つのデータブロックを直接または間接的に指すポインタのセットを含む。装置は、少なくとも１つの記憶デバイスと、この少なくとも１つの記憶デバイスと通信するストレージプロセッサとを含み、このストレージプロセッサは、ファイルストレージシステムにおいて読取り専用データ・ストリーム・スナップショットオブジェクトを作成し、データ・ストリーム・スナップショットオブジェクトにポインタセットのコピーを記憶し、ファイルストレージシステムにおいて可変クローンオブジェクトを作成し、クローンオブジェクト内にポインタセットのコピーを記憶するように構成されており、データ・ストリーム・スナップショットオブジェクト及びクローンオブジェクトは、少なくとも１つのデータブロックをソースファイルシステムオブジェクトと共有しており、スナップショットオブジェクトと、クローンオブジェクトに対して少なくとも１つのデータブロックの別々のコピーを形成することはなく、ソースファイルシステムオブジェクト及びクローンオブジェクトは事実上、可変バージョンのデータ・ストリーム・スナップショットオブジェクトになり、データ・ストリーム・スナップショットオブジェクトによって表されるオブジェクトの読取り専用コピーからの変化を事実上記憶する。
【００１０】
様々な代替の実施形態では、各々のオブジェクトが、ルートオーノードを含む場合もあり、ポインタセットを、このオブジェクトのルートオーノード内に記憶することができる。ポインタセットは、ソースファイルシステムからデータ・ストリーム・スナップショットオブジェクトにコピーされ、その後データ・ストリーム・スナップショットオブジェクトからクローンオブジェクトにコピーすることができる。
【００１１】
これらの実施形態はまた、データ・ストリーム・スナップショットオブジェクトに、ソースファイルシステムオブジェクトへの参照及びクローンオブジェクトへの参照を記憶することと、ファイルシステムオブジェクトに、データ・ストリーム・スナップショットオブジェクトへの参照を記憶することと、クローンオブジェクト内にデータ・ストリーム・スナップショットオブジェクトへの参照を記憶することとを含むことができる。
【００１２】
これらの実施形態にはまた、データ・ストリーム・スナップショットオブジェクトにおいて参照カウントを維持することが含まれる場合もあり、この参照カウントは、データ・ストリーム・スナップショットオブジェクトを参照するファイルシステム内のオブジェクトの数を示している。
【００１３】
これらの実施形態にはまた、クローンオブジェクトが作成されたソースファイルシステムオブジェクトのサイズがクローンオブジェクトに起因すると考えることが含まれる場合もある。
【００１４】
これらの実施形態にはまた、可変ソースファイルシステムオブジェクトまたは可変クローンオブジェクトを変更する際、少なくとも１つのデータブロックを割り当てることで、この変更を記憶し、少なくとも１つの割り当てられたデータブロックを変更後のオブジェクトに関連づけることが含まれる場合があり、変更後のオブジェクトは、変更後のポインタセットを含んでいる。変更後のオブジェクトは、例えばファイルストレージシステム内に第２読取り専用データ・ストリーム・スナップショットオブジェクトを作成し、この第２データ・ストリーム・スナップショットオブジェクト内に変更後のポインタセットのコピーを記憶し、ファイルストレージシステム内に第２可変クローンオブジェクトを作成し、変更後のポインタセットのコピーをこの第２クローンオブジェクト内に記憶することによって、クローン作成することができる。このクローニングはまた、第２データ・ストリーム・スナップショットオブジェクト内に変更後のオブジェクトに対する参照と、第２クローンオブジェクトに対する参照と、第１データ・ストリーム・スナップショットオブジェクトに対する参照を記憶することと、変更後のファイルシステムオブジェクト内に第２データ・ストリーム・スナップショットオブジェクトに対する参照を記憶することと、第２クローンオブジェクト内に、第２データ・ストリーム・スナップショットオブジェクトに対する参照を記憶することを含む場合もある。
【００１５】
これらの実施形態にはまた、データ・ストリーム・スナップショットオブジェクトを使用して、ソースオブジェクトの別のクローンを作成することが含まれる場合もある。
【００１６】
これらの実施形態にはまた、オブジェクトをデクローニングすることが含まれる場合もある。
【００１７】
本発明の上記の特徴は、添付の図面を参照して以下の詳細な記載を参照することによって、より容易に理解されるであろう。
【図面の簡単な説明】
【００１８】
【図１】本発明の例示の一実施形態によるファイルストレージシステムの概略ブロック図である。
【図２】本発明の例示の一実施形態による一般的な形式のファイルシステムを示す概略ブロック図である。
【図３】本発明の例示の一実施形態による一般的な形式のオブジェクトツリー構造を示す概略ブロック図である。
【図４】本発明の例示の一実施形態による、他のオーノードを持たないルートオーノードの利用を示すブロック図である。
【図５】本発明の例示の一実施形態による、直接オーノードを有するルートオーノードの利用を示すブロック図である。
【図６】本発明の例示の一実施形態による、直接オーノードだけでなく間接オーノードも有するルートオーノードの利用を示すブロック図である。
【図７】本発明の例示の一実施形態による、ルートオーノードと間接オーノードの間に配置された複数の層の間接オーノードの利用を示すブロック図である。
【図８】本発明の例示の一実施形態に関するオブジェクト番号の割当を表わす図である。
【図９】本発明の例示の一実施形態による一般的な形式の間接オブジェクトを示す概略ブロック図である。
【図１０】本発明の例示の一実施形態による、ＤＳＢと、間接オブジェクトと、ルート直接オブジェクトと、ファイルオブジェクトの一般的な関係を例示する概略ブロック図である。
【図１１】本発明の例示の一実施形態による、チェックポイント番号１における４つのデータブロックと、様々なオーノードを含む例示のオブジェクトの構造を示す概略図である。
【図１２】本発明の一実施形態による、変更後のオブジェクトのために新しいルートノードが作成された後の、図１１の例示のオブジェクトの構造を示す概略図である。
【図１３】本発明の一実施形態による、変更後のデータブロックのコピーが作成された後の、図１２の一例のオブジェクトの構造を示す概略図である。
【図１４】本発明の一実施形態による、変更後のデータブロックのコピーを指すために新しい直接オーノードが形成された後の、図１３の例示のオブジェクトの構造を示す概略図である。
【図１５】本発明の一実施形態による、新しい直接オーノードを指すために新しい間接オーノードが形成された後の、図１４の例示のオブジェクトの構造を示す概略図である。
【図１６】本発明の一実施形態による、新しい間接オーノードを指すように新しいルートオーノードが更新された後の、図１５の例示のオブジェクトの構造を示す概略図である。
【図１７】チェックポイントを記録するためのＤＳＢの循環リストを使用して、本発明の例示の実施形態によってチェックポイントを取得する前の、様々なファイルシステム構造を示す概略図である。
【図１８】チェックポイントを記録するためのＤＳＢの循環リストを使用して、本発明の例示の実施形態によってチェックポイントを取得した後の、図１７の様々なファイルシステム構造を示す概略図である。
【図１９】チェックポイントを記録するためのＤＳＢの循環リストを使用して、本発明の例示の実施形態によって間接オブジェクトを変更した後の、図１８の様々なファイルシステム構造を示す概略図である。
【図２０】１つのＤＳＢを再利用することで連続するチェックポイントを作成する本発明の例示の実施形態によって、チェックポイントを取得する前の様々なファイルシステム構造を示す概略図である。
【図２１】１つのＤＳＢを再利用することで連続するチェックポイントを形成する本発明の例示の実施形態によって、チェックポイントを取得した後の図２０の様々なファイルシステム構造を示す概略図である。
【図２２】１つのＤＳＢを再利用することで連続するチェックポイントを形成する本発明の例示の実施形態によって、間接オブジェクトを変更した後の、図２１の様々なファイルシステム構造を示す概略図である。
【図２３】本発明の例示の一実施形態による、ソースオブジェクト（ファイルＡ）２８０２と、隠しデータ・ストリーム・スナップショットオブジェクト２８０３と、可変コピー２８０５の関係を概略的に示す図である。
【図２４】本発明の例示の一実施形態による、概念上のチェックポイント番号４において図１１に表されるファイルシステムオブジェクトをクローニングした後の、オブジェクト２８０２、２８０３及び２８０５を概略的に示す図である。
【図２５】本発明の例示の一実施形態による、ソースオブジェクト（ファイルＡ）２８０２と、隠しデータ・ストリーム・スナップショットオブジェクト２８０３と、２つの可変コピー２８０５、２８０７の関係を概略的に示す図である。
【図２６】本発明の例示の一実施形態による、概念上のチェックポイント番号６において第２の可変コピーをクローニングした後の、オブジェクト２８０２、２８０３、２８０５及び２８０７を概略的に示す図である。
【図２７】変更後のソースオブジェクト２８０２’（このソースオブジェクトの変更後のタイプを表すアポストロフィが付いた）と、２つの元のソースオブジェクトクローン２８０５及び２８０７を有する第１データ・ストリーム・スナップショットオブジェクト２８０３と、第２データ・ストリーム・スナップショットオブジェクト２８０９と、第２データ・ストリーム・スナップショットオブジェクト２８０９の可変コピー２８１１との関係を概略的に示す図である。
【図２８】本発明の例示の一実施形態による、概念上のチェックポイント番号８において変更後のソースオブジェクト２８０２’をクローニングした後の、オブジェクト２８０２’、２８０３、２８０９及び２８１１を概略的に示す図である。
【図２９】本発明の例示の一実施形態による、特定のソースオブジェクトに関連付けられたＤＳＳオブジェクトが、このソースオブジェクトと、全てのコピーが削除されるまでいかにしてファイルシステム内に残されるかを概略的に示す図である。
【図３０】図３０Ａは、例示の一実施形態によるデクローニングを概略的に示す図である。図３０Ｂは、例示の一実施形態によるデクローニングを概略的に示す図である。図３０Ｃは、例示の一実施形態によるデクローニングを概略的に示す図である。
【特定の実施形態の詳細な記載】
【００１９】
図面中に描かれる前述の図及び要素は必ずしも一貫した縮尺または任意の縮尺どおりのものではないことに留意されたい。文脈がそれ以外の意味を示唆しない限り、類似の要素は類似の符号によって示される。
【００２０】
この記載及び添付のクレームにおいて使用されるように、以下の用語は、その文脈がそれ以外の意味を要求しない限り、指摘される意味を持つべきである。「記憶デバイス」とは、データを記憶するのに使用されるデバイスまたはシステムである。記憶デバイスは、１つ以上の磁気または磁気−光または光ディスクドライブ、ソリッドステート記憶デバイスまたは磁気テープを含むことができる。簡便にするために、記憶デバイスが、「ディスク」または「ハードディスク」と呼ばれる場合もある。データストレージシステムは、同一または異なる記憶容量を有する同一または異なるタイプの記憶デバイスを含むことができる。
【００２１】
「ＲＡＩＤ制御装置」は、複数の記憶デバイスの記憶容量を記憶スペースの仮想部分に合体させるデバイスまたはシステムであり、これは代替として「システムドライブ」（「ＳＤ」）、「論理ユニット」（「ＬＵ」または「ＬＵＮ」）または「ボリューム」と呼ばれる場合もある。典型的にはＳＤは、単一の記憶デバイスより大きく、複数の記憶デバイスからスペースを引き出し、冗長情報を含むことで、それはデータを損失せずに、特定の数のディスクの破損に耐えることができる。例示の実施形態において、各々のＳＤは、独自の識別子に対応付けられており（この識別子は、「論理ユニット識別子」または「ＬＵＩＤ」と以後呼ばれる）、各々のＳＤはもはや、例えば２ＴＢ−６４ＴＢまたはそれ以上の所定の最大サイズより大きくならない。特定のＳＤにコマンドが送られると、ＲＡＩＤ制御装置は典型的には、このコマンドを同時にこのＳＤの全ての記憶デバイスに転送する。ＲＡＩＤ制御装置は、典型的な記憶デバイスの３つの主な制約、すなわち記憶デバイスは典型的にはストレージシステムの最も遅い構成要素であること、それらが典型的には、重大な障害を受ける可能性が最も高いこと、及びそれらが典型的には相対的に小さな記憶容量を有するといった制約を克服する助けをする。
【００２２】
「ＲＡＩＤシステム」は、１つ以上のＲＡＩＤ制御装置と、いくつかの記憶デバイスを含むデバイスまたはシステムである。典型的にはＲＡＩＤシステムは、２つのＲＡＩＤ制御装置と（これにより一方は、他方が故障した場合に作動することが可能であり、また両方が正常なときは負荷を共有することができる）、数ダースの記憶デバイスを中に含む。例示の実施形態において、ＲＡＩＤシステムは典型的には、２つから３２個のＳＤによって構成される。ファイルサーバがデータの記憶または取り出しを必要とする際、それはＲＡＩＤシステムのＲＡＩＤ制御装置にコマンドを送り、このＲＡＩＤ制御装置が、個々の記憶デバイスに向けてコマンドを転送し、必要に応じてデータを記憶したり取り出したりする作業を担っている。一部のＲＡＩＤシステムの場合、ＳＤ間にミラー関係を確立することができるため、１つのＳＤ（「一次ＳＤ」と呼ばれる）に書き込まれたデータは、重複させる目的でＲＡＩＤシステムによって自動的に別のＳＤ（「本明細書では二次ＳＤ」または「ミラーＳＤ」と呼ばれる）に書き込まれる。二次ＳＤは、同一のＲＡＩＤシステムによって一次ＳＤとして、あるいは異なるローカルまたはリモートＲＡＩＤシステムによって管理される。ＳＤをミラーすることにより、ＳＤの全体にわたってＲＡＩＤ１＋０機能を効果的に与えることで、１つのＳＤ、あるいは一部の状況では場合によってさらに複数のＳＤの損失や破損から回復することができる。
【００２３】
「ファイルシステム」は、ファイルストレージシステム内に記憶された特定の構造のファイル及びディレクトリ（フォルダ）である。ファイルストレージシステムにおいて、ファイルシステムは典型的には、いくつかの仮想記憶構造を使用して管理されており、例示の実施形態では、フィイルシステムは、レンジ、ストライプセット及びスパンと呼ばれる仮想記憶構造のヒエラエルキーを使用して管理されている。「レンジ」は、一次ＳＤそのまま、または一次／二次ＳＤの組のいずれかで構成されており、この組は、同一のデータを含むため、単独のＳＤと同じ記憶容量を提供することが想定される。「ストライプセット」は、１つ以上のレンジで構成される。「スパン」は、１つ以上のストライプセットで構成される。よって特定のスパンは最終的には、１つ以上のＳＤ（典型的には４から５０のＳＤ）で構成される。スパンは、１つ以上のファイルシステムに分割することができ、各々のファイルシステムは、別々の名前と、識別子、及び場合によっては異なる特徴（例えばあるファイルシステムは３２ＫＢのクラスタによって初期化され、別のファイルシステムは４ＫＢのクラスタによって初期化される、あるファイルシステムは、ワームであり、別のファイルシステムはそうでない場合など）を有する。スパン上の各々のファイルシステムは、別々に初期化され、マウントされ、アンマウントされる。ファイルシステムは、任意の順番で随時作成され削除されてよい。ファイルシステムは、自動的に拡張する（または代替として自動拡張を阻止するまたは制限する）ように構成することができる、あるいは手動により拡張させることができる。
【００２４】
特定の「セット」の値は、１つ以上の値を含むことができる。
【００２５】
簡便にするために以下で見出しが使用されているが、これはいずれにしても本発明を限定するものとして解釈されるべきでない。
【００２６】
本発明の特定の実施形態において、ファイルクローニング機構を利用することで、例えばユーザがファイルのコピーを作成する際に、ファイルシステム内に迅速にファイルのコピー（クローン）を形成することを可能にする。例示の実施形態において、ソースオブジェクトのクローンは、少なくとも最初は、ソースオブジェクトの様々な要素（例えば間接オーノード、直接オーノード及びデータブロック）の参照を含む特定の構造によって表される。読取り専用クローンと可変クローンを共に作成することができる。ソースファイル及びそのクローンは最初はこのような要素を共有しており、ソースファイルや可変クローンが変更されると、変更されない要素を共有し続ける。ソースファイルに関連するデータストリーム（すなわち間接／直接オーノード）を表すユーザデータブロックやメタデータブロックを、クローンが作成されるときにコピーする必要がない。適宜クローンされたファイルは、「デクローン」することができる。
【００２７】
本発明の例示の実施形態は、例示のファイルシステムを参照して記載されているが、様々なクローニング及びデクローニングの概念が、他のタイプのファイルシステムに適用される場合もあることに留意されたい。
【００２８】
例示のファイルシステム
【００２９】
図１は、本発明の例示の一実施形態によるファイルストレージシステムの概略ブロック図である。とりわけ、ファイルストレージシステムは、いくつかのファイルサーバ（簡素化し、簡便にするために、１つのファイルサーバ９００２が示されている）を含んでおり、このサーバは、インターネットプロトコルネットワーク（例えばインターネット）などの通信ネットワーク９００４を介して様々なクライアントデバイス９００６１から９００６Ｍと通信し、またファイバチャネルネットワークなどの記憶ネットワーク９０１０を介して様々なＲＡＩＤシステム９００８１から９００８Ｎとも通信する。クライアントサーバ９００６１から９００６Ｍと、ファイルサーバ９００２は、１つ以上のネットワークファイルプロトコル、例えばＣＩＦＳ及び／またはＮＦＳなどを利用して通信する。ファイルサーバ９００２とＲＡＩＤシステム９００８１から９００８Ｎは、例えばＳＣＳＩなどの記憶プロトコルを利用して通信する。ファイルストレージシステムは、様々な構成で相互に接続された複数のファイルサーバと、複数のＲＡＩＤシステムを含む場合もあり、このような構成には、任意のファイルサーバが、冗長かつスイッチバージョンのファイバチャネルネットワークによって、任意のＲＡＩＤシステムと通信することができるフルメッシュ構造が含まれることに留意されたい。
【００３０】
ファイルサーバ９００２は、１つ以上のファイルシステムを管理するためのストレージプロセッサを含む。ファイルサーバ９００２は、クライアントが、ファイルシステムの一部、例えば指定された名の下にツリーまたはサブツリーにアクセスすることができるように構成することができる。ＣＩＦＳ用語では、このようなアクセスは、「シェア」と呼ばれることもあり、ＮＦＳ用語では、このようなアクセスは、「エクスポート」と呼ばれる場合もある。内部では、ファイルサーバ９００２は、例えば米国特許出願第０９／８７９，７９８号及び１０／８８９，１５８号に記載されるように（これらの特許出願は上記で参照により組み込まれている）、様々なハードウェアが実装された及び／またはハードウェアアクセレートされたサブシステムを含むことができ、例えば米国特許出願第１０／２８６，０１５号及び１１／８４１，３５３号に記載されるように（これらの特許出願は上記で参照により組み込まれている）複数の接続されたサブモジュールを含むハードウェアベースのファイルシステムを含む場合もある。
【００３１】
各々のＲＡＩＤシステム９００８は典型的には、少なくとも１つのＲＡＩＤ制御装置（通常は重複させるために２つのＲＡＩＤ制御装置）、ならびにこのＲＡＩＤ制御装置によって管理されるいくつかの物理的記憶デバイス（例えばディスク）を含む。ＲＡＩＤシステム９００８は、その記憶リソースをいくつかのＳＤに集約する。例えば各々のＲＡＩＤシステム９００８は、２から３２個のＳＤによって構成されてよい。各々のＳＤは、所定の最大サイズ（例えば２ＴＢから６４ＴＢまたはそれ以上）に制限されてよい。複数の記憶デバイスを１つのＳＤに合体させることにより、いくつかの利点を提供することが可能であり、これらの利点には、速度の上昇（個々の記憶デバイスは比較的速度が遅いが、データを複数の記憶デバイスにわたってストライプすることで、ボトルネックを広げることができる）、容量の増加（個々の記憶デバイスは比較的小さいが、複数の記憶デバイスを組み合わせることで、より広い利用可能なスペースを提供することができる）、抽象化（利用されるスペースの大きさは、単独の記憶デバイスのサイズより大きいか、あるいはそれより小さいかのいずれかであり得る）、及び復元力（パリティまたは冗長情報を、各々の記憶デバイスに記憶することができるため、ＳＤは、記憶デバイスの損失にも耐えることができる）が含まれる。
【００３２】
ファイルサーバ９００２は、１つ以上のＳＤを使用するように構成されており、これは、単独のＲＡＩＤシステムから、あるいは複数のＲＡＩＤシステムからであってよい。ファイルサーバ９００２は通常、ＲＡＩＤシステムに問い合わせをすることで、各々のＳＤが一次または二次であるかを突き止めることができる。どのＳＤがファイルサーバ９００２によって使用されるかを管理する方法は、本明細書では「ライセンシング」と呼ばれる。したがって実際には、ファイルサーバ９００２は典型的には、一部のＳＤのために認可され、他のＳＤには認可されないことになる。
【００３３】
内部ではファイルサーバ９００２は、複数のＳＤを、本明細書では「スパン」と呼ばれるより大きな記憶プールに組み込むことが可能である。スパンは基本的に、ＲＡＩＤ０配列の複数のＳＤである。複数のＳＤを１つのスパンに組み込むことで、複数の物理的ディスクを１つのＳＤに組み込むことによって得られるものと同様のいくつかの利点を実現することができ、この利点には、速度の上昇（複数のＲＡＩＤシステム上の複数のＳＤ間のＩ／Ｏを広げることで、記憶ボトルネックをさらに広げることができる）、記憶容量の増加（スパンは、単独のＳＤより大きくなる可能性があり、これは２テラバイトまで制限され得る）、及び付加的な復元力（これにより適応可能な記憶スペースの割り当てが可能になる）が含まれる。
【００３４】
ファイルシステムツリー構造
【００３５】
ファイルサーバ９００２は、ファイルシステム内に様々な種類のオブジェクトを記憶する。オブジェクトは一般に、システムオブジェクトとファイルオブジェクトとして分類することができる。ファイルオブジェクトは、ユーザデータ及び関連する属性、例えばワードプロセッサまたはスプレッドシートファイルなどを記憶するために作成される。システムオブジェクトは、ファイルストレージシステムによって情報を管理するために形成され、ルートディレクトリオブジェクト、フリースペース割り当てオブジェクト、変更後のチェックポイントオブジェクトリストオブジェクト、変更後に保持されるオブジェクトリストオブジェクト及びソフトウェアメタデータオブジェクトなどを含むが、ここに挙げたのはほんの数例である。より具体的には、ディレクトリオブジェクトは、ディレクトリ情報を記憶するために作成される。フリースペース割り当てオブジェクトは、フリースペース割り当て情報を記憶するために作成される。変更後のチェックポイントオブジェクトリストオブジェクト及び変更後に保持されるオブジェクトリストオブジェクトは（これらは共に以下でより詳細に記載される）、チェックポイント及び保持されるチェックポイントそれぞれに関連する情報を記憶するために作成される。ソフトウェアメタデータオブジェクト（これは以下に詳細に記載される）は、ファイルまたはディレクトリオブジェクトに関連する過剰なファイル属性（すなわち、以下に記載するようにファイルまたはディレクトリオブジェクトにおいて事前に指定された領域に適合することができないファイル属性、すなわちＣＩＦＳセキュリティ属性）を保持するための特殊なオブジェクトであり、ファイルまたはディレクトリオブジェクトの作成者によって作成され、これは、ファイルまたはディレクトリオブジェクトにおいてソフトウェアメタデータオブジェクトに対する参照を含む。
【００３６】
ファイルシステムのインスタンシエイションは、好ましくはストレージシステム内の固定位置に記憶されるルートノード（動的スーパーブロックまたはＤＳＢと呼ばれる）を有するツリー構造を使用して管理される。とりわけ、ＤＳＢを固定位置に記憶することにより、ファイルサーバ９００２がＤＳＢを特定し易くする。ファイルサーバ９００２は、複数のＤＳＢを保持することで、種々のチェックポイントを表す種々の型（例えば現在「作業中の」型及び１つ以上の「チェックポイント」型）のファイルシステムを記憶することができる。例示の実施形態において、ＤＳＢは、間接オブジェクトに対するポインタを含んでおり（これは以下に詳細に記載される）、この間接オブジェクトは、他のオブジェクトに対するポインタを含んでいる。
【００３７】
図２は、本発明の例示の一実施形態による一般的な形式のファイルシステムのインスタンシエイションを示す概略ブロック図である。ＤＳＢ２０２は、ファイルシステムツリー構造のルートを表す特定の構造である。とりわけＤＳＢ２０２は、間接オブジェクト２０４に対するポインタを含んでおり、この間接オブジェクトは、このファイルシステムシステムにおける他のオブジェクトに対するポインタを含んでおり、これにはオブジェクト２０６及びファイルオブジェクト２０８が含まれる。
【００３８】
本発明の実施形態において、Ｎ個の動的スーパーブロック（Ｎ＞２）が、ファイルシステムに対して維持され、このうちの１つのみが任意の所与の時点で最新であるとみなされる。ＤＳＢの数は、固定式または設定可能であってよい。ＤＳＢは、固定位置に位置付けられ、これを使用して、チェックポイントの状態をディスク上に記録する。各々のＤＳＢは、間接オブジェクトを指している。
【００３９】
とりわけ以下の情報が各々の動的スーパーブロックに記憶される。
・この動的スーパーブロックに関連するチェックポイント番号。
・このチェックポイントに関する変更後のチェックポイントオブジェクトリストオブジェクトのハンドル。
・最後に保持されたチェックポイントからの変更後のチェックポイントオブジェクトリストオブジェクトのオブジェクト番号。
・このチェックポイントの状態（すなわちチェックポイントが作成されたかどうか）。
・ＤＳＢ及び他の構造（例えば間接オブジェクト）の有効性をチェックすることが可能なＣＲＣ及び様々な他の情報。
【００４０】
例示の一実施形態において、ＤＳＢは循環リストとして扱われ（すなわち第１動的スーパーブロックが、連続して最後の動的スーパーブロックにつづくとみなされる）、各々の連続するチェックポイントは、この循環リストにある次の連続する動的スーバーブロックを使用する。ファイルサーバ９００２が、そのボリュームを開放する際、それは典型的に、全ての動的スーパーブロックを読み取り、これらのＤＳＢに対して様々なチェックを行なう。そのチェックポイント状態が完了であることが示され、種々の他のサニティチェックに通った最新のチェックポイント番号を有するＤＳＢが、このボリュームにおける最新の有効なチェックポイントを表すものとみなされる。ファイルサーバ９００２は次のチェックポイント用の循環リストにおける次のＤＳＢを使用し始める。
【００４１】
一般的な形式の間接オブジェクト２０４を以下で考察する。
【００４２】
オブジェクトツリー構造
【００４３】
一般的に言えば、ファイルシステム内の各々のオブジェクトは、間接オブジェクト２０４と、各々のシステムオブジェクト２０６と、各々のファイルオブジェクト２０８を含んでおり、別個のツリー構造を使用して実装され、このツリー構造は、別個のオブジェクトルートノードを含み、任意選択でいくつかの間接ノード、直接ノート及び記憶ブロックを含む。ＤＳＢ２０２は、間接オブジェクト２０４のルートノードに対するポインタを含む。間接オブジェクト２０４は、他のオブジェクトのルートノードに対するポインタを含む。
【００４４】
図３は、本発明の例示の一実施形態による、一般的な形式のオブジェクトツリー構造を示す概略ブロック図である。ルート（「Ｒ」）ノード３０２は、様々な間接（「Ｉ」）ノード３０４を指すことができ、そのそれぞれが、いくつかの直接（「Ｄ」）ノード３０６を指すことができ、そのそれぞれが、いくつかの記憶ブロック（「Ｂ」）３０８を指すことができる。実際には、オブジェクトツリー構造は、例えばオブジェクトのサイズによって広範にわたって変化する可能性がある。また特定のオブジェクトのツリー構造は、オブジェクトに情報が加えられたり、オブジェクトから情報が削除されたりする際、経時的に変化する場合もある。例えばこのオブジェクトのためにより大きな記憶スペースが使用される際、ツリー構造にノードを動的に追加することができ、必要に応じて異なる間接レベルを利用することができる（例えば特定の間接ノードが、直接ノードまたは他の間接ノードを指すことができる）。
【００４５】
オブジェクトが作成される際、このオブジェクトのためにオブジェクトルートノードが作成される。最初このような「エンプティ」オブジェクトのルートノードは、いずれの間接ノード、直接ノードまたはデータブロックに対するポインタも持たない。
【００４６】
このオブジェクトにデータが追加される際、それは最初に、ルートノードが直接指すデータブロックに入れられる。これは図４の図面に示されており、この図は、他のノードを持たないルートノードの利用を示している。この図面及び以下の全ての図面において、簡素化するためにルートノード及び直接ノードは、２つのデータポインタのみを有するように示されており、間接ノードは、２つの間接または直接ノードポインタのみを有するように示されていることに留意されたい。
【００４７】
ひとたびルートノードにおける全ての直接ブロックポインタが塞がると、このときルートノードから直接ノードへのポインタを有する直接ノードＡが形成される。図５は、この直接ノードＡを有するルートノードの利用を示している。ルートノードは、複数のデータブロックポインタを有するが、直接または間接ノードのいずれかに対するポインタは１つにしか持たないことに留意されたい。
【００４８】
オブジェクト内のデータが増大して、直接ノードにおける全てのデータポインタが塞がった場合、このとき図６に示されるように間接ノードＢが作成される。図６は、直接ノードだけでなく間接ノードも有するルートノードの利用を示している。直接ノードＡを指していたルートノードにあるポインタは、間接ノードＢに向けられるように変更され、間接ノードＢにおける第１ポインタは、直接ノードＡを指すように設定される。これと同時に新しい直接ノードＣが作成され、この直接ノードは、間接ノードＢから指される。より多くのデータが作成されるにつれ、より多くの直接ノードが作成され、これらの直接ノードは全て、間接ノードから指される。
【００４９】
間接ノードＢにおける全ての直接ノードポインタが使用されると、別の間接ノードＤが作成され、この間接ノードＤは、ルートノードと第１間接ノードＢの間に挿入される。また別の間接ノードＥ及び直接ノードＦが形成されることで、より多くのデータブロックを参照することが可能になる。このような状況は、図７に示されており、この図は、ルートノードと直接ノードの間に配置された複数の層の間接ノードの利用を示している。
【００５０】
間接ノードを加えることによって、より多くの間接レベルを形成するこのような工程を繰り返すことで、いかにオブジェクトが含むデータが多くともそれらは収容される。
【００５１】
オブジェクトルートノードは、特定のチェックポイント番号を含むことで、このオブジェクトが最後に変更されたチェックポイントを特定する（チェックポイント番号は最初、オブジェクトが作成されたチェックポイントを特定し、その後チェックポイント番号は、オブジェクトが新しいチェックポイントにおいて変更される毎に変化する）。例示の一実施形態において、オブジェクトが作成されたチェックポイント番号もまた、オブジェクトルートノードに記憶される。またオブジェクトルートノードにおいて、オブジェクトルートノードがメタデータを提供するオブジェクトのタイプを識別するのは特定のパラメータである。例えばオブジェクトタイプは、フリースペース、ファイルまたはディレクトリのいずれかであってよい。オブジェクトのタイプに加えて、オブジェクトルートノードはまた、ブロック内のオブジェクトの長さに関する特定のパラメータを有する。
【００５２】
オブジェクトルートノードはまた、一連のポインタを持っている。これらの１つは、任意の直前のバージョンのオブジェクトルートノードに対するポインタである。保持されるチェックポイントが該当するチェックポイントとみなされたことが判明した場合、このとき恐らく問題となる直前のバージョンのオブジェクトルートノードが記憶されており、ポインタは、このような直前バージョンのオブジェクトルートノードのセクター番号を特定する。
【００５３】
オブジェクトルートノードが対応する実際のデータに関して、オブジェクトルートノードは、対応するオブジェクトに関連する各々のデータのブロックに対する別個のポインタを含む。１８個までのデータブロックの配置が、オブジェクトルートノードに記憶される。データが１８個のブロックを超えている場合、直接ノードを追加する必要があり、この場合オブジェクトルートノードは、この直接ノードに対するポインタも有しており、このポインタは、オブジェクトルートノードにおいて、このディスク上のセクター番号によって特定される。
【００５４】
直接ノードは、チェックポイント番号を含んでおり、そのオブジェクトに関係する特定の数のブロック（例えばおよそ６０または６１のブロック）の位置を記憶するように構成されている。
【００５５】
データブロックを特定するのに第１直接ノードが完全に利用されると、次いで１つ以上の間接ノードを使用して、第１直接ノード、ならびにこのオブジェクトに対応するデータのブロックを有する追加の直接ノードを特定する。このような場合オブジェクトルートノードは、この間接ノードに対するポインタを有し、間接ノードは、対応する直接ノードに対するポインタを有する。間接ノードが完全に利用されると、次いで必要に応じて追加の間に介在する間接ノードが利用される。このような構造によって、ファイルの断片化に関わらずファイルの一部を迅速に特定することが可能になる。
【００５６】
本発明の種々の実施形態は、大きなファイルを容易に作成するための機構を含むことができ、このファイルは典型的には、最初に作成される際、ゼロで満たされるスパースファイルである。
【００５７】
このような１つの機構によって、ゼロで満たされたデータブロックを、実際にゼロをデータブロックに書き込まずに割り当てることが可能になる。具体的にはオブジェクトルートノード及び直接ノードは、対応するブロックが論理的にゼロで満たされているかどうかを示す（このブロックは、実際にはゼロで満たされる必要はない）各々のブロックポインタのためのフラグを含む。したがって例えば、データブロックが割り当てられる際、データブロックをゼロで満たすのではなく、このデータブロックに関連するビットを、データブロックがゼロで満たされていることを示し、実際にデータブロックからデータを読み取らずに、そのデータブロックがゼロに戻るようなアクセスを読み取るように設定することができる。
【００５８】
同様の機構によって、実際にファイルに全てのデータブロック及びノードを割り当てずに、ファイルを作成することが可能になる。具体的にはブロック及び他のノードに対するポインタは、そのブロックまたは他のノードが実際に作成されているかどうかを示すビットを含むことができる。関連するブロック及びノードがまだ作成されていない場合、次いで必要に応じてブロックとノードが作成されることで書き込み要求に対応し、割り当てビットは、これに従ってトグルされる。ブロックの作成は、スペースの割り当て、ブロックへのデータの書き込み、及び関連するノードに関するビットフラグの設定を必要とすることに留意されたい。特定の例示の一実施形態において、この機構は単に、全てのデータブロックを割り当てずにファイルを作成するために使用され、他のファイルノードは、上記に記載されるように取引ログを割り当てられるだけでなく、オンザフライでメタデータキャッシュに維持されている。
【００５９】
ノード構造はまた、例示の一実施形態においてノード構造に関連するディスク書き込みをさらに減らすように確立させることもできる。最終的に、ノード構造は、ファイルの中身だけでなく、ファイル属性も記憶するように適合する必要がある。ファイル属性は、多様なパラメータを含んでおり、これにはとりわけ、ファイルサイズ、ファイル作成時間及び作成日、ファイル変更時間及び変更日時、読取り専用状況、及びアクセス許可が含まれる。このような関係性により、オブジェクトルートノードの中身の変更は、所与のチェックポイントにおいて頻繁に行なわれる可能性があるが、これはこのオブジェクトルートノードがまだディスクに書き込まれていないためである（すなわち上記で考察したように、オブジェクトルートノードのディスク書き込みが遅れているためである）。したがって例示の一実施形態において、オブジェクトルートノードの一部は、ファイル属性を記憶するために確保されている。
【００６０】
より一般的には、ファイル属性を記憶するための以下の構造が、例示の一実施形態において定義される。
【００６１】
イーノード（ｅｎｏｄｅ）（更新するのにオーバーヘッドが少ない、容量が限定されている）。この構造は、オブジェクトルートノードにおいて規定され、例示の一実施形態では１２８バイトである。
【００６２】
ソフトウェアメタデータオブジェクト（更新するのにオーバーヘッドが高い、ほぼ無限の容量である）。これはメタデータを記憶するための専用オブジェクトであり、よってディスク上にその独自の記憶位置を有し、このオブジェクトはイーノードにおいて特定される。
【００６３】
したがって例示の一実施形態において各々のオブジェクトルートノードは以下の種類の情報を記憶する。
・チェックポイント番号
・このバージョンのオブジェクトに関するデータ長
・このオブジェクトに関してランリストで使用される間接レベルの数
・オブジェクトの種類。これは、特定のリクエストがオブジェクトにアクセスするようになったとき、サニティチェックとして主に使用される。
・保持されるチェックポイント（１つの場合）に対して形成されたより古いルートノード型に対するポインタ。
・より新しいルートノード型（これが保持されるチェックポイントに対して形成されたルートノードのコピーである場合に専ら有効である）に対するポインタ。
・１９個までのデータブロックディスクリプタ。各々のデータブロックディスクリプタは、特定のデータブロックに対するポインタ、チェックポイント番号及びブロックがゼロで満たされているかどうかを示すビットを含む。
・直接ノードまたは間接ノードのいずれかに対する１つのポインタ。
・このオブジェクトに対する１２８バイトのイーノードデータ。
・ルートノードの有効性をチェックすることができるＣＲＣ及び種々のサニティｄｗｏｒｄｓ。
【００６４】
以下で考察するように、オブジェクトは、保持されるチェックポイントが取得される毎に作成されるルートノードのコピーを含むことができる。より古いルートノードの型に対するポインタと、より新しいルートノードの型に対するポインタによって、ルートノードの二重リンク式のリストを作成することができ、これには現行のルートノード及び、保持されるチェックポイントに対して作成されるルートノードの任意のコピーが含まれる。この二重リンク式のリストによって、保持されるチェックポイントの作成や削除が容易になる。
【００６５】
上記で考察したように、間接ノードによって、ルートノードと直接ノードの間に特定の間接レベルが形成される。以下の情報は、例示の一実施形態において間接ノードに記憶される。
・チェックポイント番号。
・間接または直接ノードのいずれかに対するポインタ（例えば１２２までのこのようなポインタ）。
・間接ノードの有効性をチェックすることができるＣＲＣ及び種々のサニティｄｗｏｒｄｓ。
【００６６】
上記で考察したように、直接ノードによって、データブロックに対する直接ポインタがディスク上に提供される。以下の情報は、例示の一実施形態において直接ノードに記憶される。
・チェックポイント番号。
・いくつかのデータブロックディスクリプタ（例えば６２までのこのようなディスクリプタ）。各々のデータブロックディスクリプタは、特定のデータブロックに対するポインタ、チェックポイント番号及びブロックがゼロで満たされているかどうかを示すビットを含む。
・間接ノードの有効性をチェックすることができるＣＲＣ及び種々のサニティディーワード（ｄｗｏｒｄｓ）。
【００６７】
オブジェクトからデータが削除され、データブロックならびに直接及び間接ノードがもはや必要なくなったとき、それらはフリースペース割り当て制御装置に戻される。
【００６８】
一実施形態によると、間接レベルの数は、オブジェクトが小さくなるにつれて減少し、最終的にはオブジェクト内の全てのデータを、ルートノードにおける直接ブロックポインタを介して参照することが可能になり、その時点で、残りの直接及び間接ノードは全て解放され、間接レベルはゼロに設定される。
【００６９】
特定のファイルオブジェクトに対する書き込み作業は、このオブジェクトの現行の末端を超えるスタートオフセットを有する場合、あるいはオブジェクトの長さが、現行の長さより大きくなるように設定された場合、このときオブジェクトの規定されない部分（例えばオブジェクトの現行の末端と、新たに書き込まれたデータの冒頭の間）は典型的にはゼロで満たされる。典型的な実装形態では、これはオブジェクトのゼロで満たされた全ての部分に対してディスクブロックを割り当てることと、このようなディスクブロックをゼロで満たすこととを含む。１ＧＢのファイルの場合、これは１０秒程かかる可能性がある。１ＴＢのファイルの場合、それは３時間程かかる可能性がある。
【００７０】
本発明の例示の一実施形態において、オブジェクトの規定されない部分に関連するデータブロックを実際にゼロで満たすのではなく、このようなデータブロックの中身は書き出さないまま、各々のデータブロックポインタ内のビットを使用して、このブロックがゼロで満たされていると思われることを示す。ファイルサーバ９００２（及び具体的にはオブジェクト記憶サブモジュール）が、このビットセットを認めた場合、次いでそれは、このブロックが、たとえオンディスクではそれが何らかの完全に異なるものを含む場合があるとしても、ゼロで満たされるべきであることを知る。ブロックが読み取られた場合、次いでファイルサーバ９００２は、実際にオンディスクのその中身を戻すのではなく、このブロックに対してゼロを戻す。書き込みがブロック全体を占めないようにブロックが書き込まれた場合、次いでファイルサーバ９００２は、書き込まれていないブロックの部分にゼロを書き込み、その後このブロックに対して「ゼロで満たされた」ビットを再度設定する。
【００７１】
オブジェクト長さを何らかの極めて長い値に設定する作業に関連する別の問題は、データブロックを割り当て、必要な直接及び間接ノード構造を作成するのにかかる時間である。例えば４Ｋのディスクブロックサイズを使用する例示の一実施形態では、１ＴＢのオブジェクトは、およそ４百万の直接ノードと、これより少ない数の間接ノードを必要とする。これは恐らくディスクに書き込むのに４０秒程かかる。また必要とされる全てのデータブロックのフリースペース割り当て、及びこれに続くフリースペースビットマップに対する更新が、この時間に相当な時間を加えることになる。ファイルの作成が始まった直後にチェックポイントが取得されるとすると、システム全体は一般に、この時間全体にわたって（任意のボリュームに対する）リクエストの要求に応えるのを止めることになる。
【００７２】
本発明の代替の実施形態において、この問題は、上記で考察したように、ファイルのゼロで満たされた部分に実際にディスクブロックを割り当てないことによって対処することができる。これは、オブジェクト記憶装置が、ゼロで満たされたブロックへの書き込みを認めたとき、それはまずそのブロックに対してディスクスペースを割り当て、それに対するポインタを関連するノード構造に据える必要があることを意味する。
【００７３】
さらに別の代替の実施形態において、ファイルのゼロで満たされた部分に実際にはデータブロックを割り当てないことに加えて、この問題は、これに対応するノード構造を作成しないことによって対処される場合もある。この態様を履行するために、各々のノードポインタは、それが指しているノードが割り当てられているかどうかを示す特定のビットを含むことができる。ノードが割り当てられていない場合、特定の動作が出現し、そのノードが有効であることを要求したとき、このとき初めてそれに対してディスクスペースが割り当てられ、正しいポインタが挿入される。この方法では、ゼロで満たされた非常に大きなオブジェクトが、１つのルートノードのみを有することができ、このルートノードは極めて迅速に作成することが可能である。
オブジェクト番号及び間接オブジェクト
【００７４】
ファイルストレージシステムにおいて、各々のオブジェクトは、オブジェクト番号に関連付けられており、この番号はオブジェクトを参照するのに使用される。システムオブジェクトは典型的には、それらが概ねシステム内に常に存在するため、固定された所定のオブジェクト番号を有する。ファイルオブジェクトは典型的には、利用可能なオブジェクト番号のプールから動的にオブジェクト番号を割り当てられる。このようなファイルオブジェクト番号は、一部の状況（例えばファイルが削除され、そのオブジェクト番号がフリーになることで、その後のファイルオブジェクトによって再利用される場合）において再利用することができる。
【００７５】
図８は、本発明の例示の一実施形態に関するオブジェクト番号の割り当てを表す図である。具体的にはファイルシステムは、Ｚのオブジェクト番号を含むことができる（この場合は、Ｚは可変であり、オブジェクトの数が増加するにつれて経時的に増える可能性がある）。特定の範囲のオブジェクト番号が、システムオブジェクト２０６のために確保され（この例ではオブジェクト番号１−Ｊ）、残りのオブジェクト番号は（この例ではオブジェクト番号Ｋ−Ｚ）、ファイルオブジェクト２０８に割り当てられる。典型的にはシステムオブジェクト２０６の数が固定されるのに対して、ファイルオブジェクト２０８の数は変わる場合がある。
【００７６】
例示の一実施形態において、間接オブジェクト２０４は、特定のテーブルとして論理的に組織されており、オブジェクト当たりの１つのテーブルエントリは、オブジェクト番号によって指し示される。図９に示されるように、このテーブルにおける各々のエントリ５０２は、オブジェクトタイプフィールドと、ポインタフィールドを含む。オブジェクトタイプフィールドに関していくつかの異なる値が規定されるが、考察するために、１セットの値が、「使用されている」オブジェクトに関して規定され、別のセットの値が、「フリーな」オブジェクトに関して規定される。したがって特定のテーブルエントリのオブジェクトタイプフィールドにおける値は、これに対応するオブジェクト番号が使用されているか、自由であるかを示すことになる。
【００７７】
各々の使用されるテーブルエントリのポインタフィールドは、このオブジェクトのルートノードに対するポインタを含む。オブジェクトが作成される際、オブジェクトルートノードが作成され（上記で考察したように）、このオブジェクトにオブジェクト番号が割り当てられる。オブジェクトルートノードに対するポインタが、間接オブジェクト２０４に記憶され、具体的には割り当てられたオブジェクト番号に関連するテーブルエントリに記憶される。したがってファイルサーバ９００２は、任意のオブジェクトのオブジェクトルートノードを、そのオブジェクト番号に基づいて、具体的には間接オブジェクトテーブル構造内に指示し、そのポインタフィールドにアクセスすることによって容易に突き止めることができる。当初このような「エンプティ」オブジェクトのルートノードは、いずれの間接ノード、直接ノードまたはデータブロックに対するポインタも持たないが、データブロック、間接ノード及び直接ノードを経時的にオブジェクトツリー構造に加えることができる。
【００７８】
フリーのテーブルエントリのポインタフィールドを使用して、１つ以上のフリーのオブジェクト番号リスト（及び好ましくは個々にリンクした、非循環式のフリーのオブジェクト番号リストが維持されており、これは例えば、Ｓｙｓｔｅｍ，Ｄｅｖｉｃｅ，  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｖａｌｉｄａｔｉｎｇ  Ｄａｔａ  Ｓｔｒｕｃｔｕｒｅｓ  ｉｎ  ａ  Ｓｔｏｒａｇｅ  Ｓｙｓｔｅｍという名称の米国仮特許出願第６０／９７９，５６１号に記載されており、この特許出願は２００７年１０月１２日に出願され、その全体が参照により本明細書に組み込まれている。
【００７９】
具体的には各々のフリーオブジェクト番号に関連するテーブルエントリは、特定のオブジェクトのルートノードに対するポインタではなく、そのフリーオブジェクト番号リストにある次のフリーオブジェクト番号に対する参照を含む。その理由は、フリーオブジェクト番号リストが、例示の一実施形態では個々にリンクした非循環式のリストであり、フリーオブジェクト番号リストにある最後のフリーオブジェクト番号に関連するテーブルエントリが、「ヌル」参照（例えばその値はゼロ）を含むためである。
【００８０】
理論上は、間接オブジェクトにおいて１つのフリーオブジェクト番号リストを維持することは可能である。このリストにあるフリーオブジェクト番号は再利用され、新しいオブジェクトが作成される際にはこのリストから外すことができ、オブジェクトがシステムから削除される際、フリーオブジェクト番号をこのリストに加えることができる。
【００８１】
しかしながら、本発明の例示の一実施形態では、２つの別々のフリーオブジェクト番号が、間接オブジェクトに維持されており、一方は再利用するのに直ぐに利用可能なフリーオブジェクト番号を列挙しており、他方は、再利用するのに直ぐには利用できない新たにフリーになったオブジェクト番号を列記している。この例示の一実施形態では、ファイルサーバは、その時々でファイルシステムの「チェックポイント」または「スナップショット」を取得することで（例えば以下で、あるいはＧｅｏｆｆｒｅｙ  Ｓ．Ｂａｒｒａｌｌ等の名前でＡｐｐａｒａｔｕｓ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｈａｒｄｗａｒｅ−Ｂａｓｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍという名称で２００２年１１月１日に出願された米国特許出願第１０／２８６，０１５号またはＧｅｏｆｆｒｅｙ  Ｓ．Ｂａｒｒａｌｌの名前でＡｐｐａｒａｔｕｓ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｈａｒｄｗａｒｅ−Ｂａｓｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍという名称で２００７年８月２０日に出願された米国特許出願第１１／８４１，３５３号において（この２つの特許出願は共に、その全体が参照により本明細書に組み込まれる）考察されるように）、任意の所与のときに、ファイルサーバは、例えばオブジェクトが作成される、削除される及び変更される際に変化し得るファイルシステムの「ワーキングコピー」を有する。様々な理由により、この例示の実施形態の場合、再利用される特定のオブジェクト番号に割り当てられた異なるオブジェクトが経時的に、異なるオブジェクトハンドルを与えられることを確実にすることが重要である。したがってこの例示の一実施形態において、２つのフリーオブジェクト番号リストを利用することで、特定のオブジェクト番号がフリーになり、ファイルシステムの同一のワーキングコピーにおいて再利用することができないことを保証し（すなわち一方のリストにはフリーオブジェクト番号を加え、その一方で他方のリストからオブジェクト番号を割り当てることによって）、現行のチェックポイント番号のボトム３２ビットが、オブジェクトが作成される際、このオブジェクトハンドルに含まれ、その結果異なるチェックポイントにおいて作成されたオブジェクトは、異なるハンドルを有することになる。よってファイルシステムの任意の特定のワーキングコピーにおいて、ファイルサーバは、一方のリストからフリーオブジェクト番号を再利用し、その一方で他方のリストに新たにフリーになったオブジェクト番号を加える。各々の「チェックポイント」において、２つのリストの役割が「交換される」ことで、先のチェックポイントにおいてフリーになったオブジェクト番号は再利用するのに利用可能であるが、その一方で現行のチェックポイントにおいてフリーになった新しいオブジェクト番号は、そのチェックポイントにおいて再利用するのに利用することはできない。新しいオブジェクトが作成される際、フリーオブジェクト番号が再利用されるリストが空である場合、このとき間接オブジェクトが拡張されて、追加のフリーオブジェクト番号を提供する（実際には他方のリストに若干のフリーオブジェクト番号がある可能性があったとしても）。しかしながら、実際には、両方のリストは一般に、各々のチェックポイント��おいて役割を交換することによって、経時的にいくつかのフリーオブジェクト番号を蓄積している、定常状態において、間接オブジェクトを度々拡張させる必要はない。
【００８２】
例示の一実施形態において、ＤＳＢ２０２は、間接オブジェクト２０４に対する（より具体的には間接オブジェクト２０４のルートノードに対する）ポインタを含んでおり、また間接オブジェクト２０４におけるフリーオブジェクト番号リストそれぞれのための２つのポインタも含んでいる。各々のポインタは、その各々のフリーオブジェクト番号リストの冒頭において、そのテーブルエントリを指している。ＤＳＢ２０２は、ストレージシステム内の固定位置に記憶され、間接オブジェクト２０４及び間接オブジェクト２０４内のフリーオブジェクト番号リストに対するポインタを含んでいるため、ファイルサーバ９００２は、このＤＳＢ２０２を使用して間接オブジェクト２０４（及びこれにより任意の他のオブジェクトのルートノード）ならびにフリーオブジェクト番号リストを容易に突き止めることができる。
【００８３】
したがって図４に示される間接オブジェクト２０４のテーブル構造を再度参照すると、特定のテーブルエントリのオブジェクトタイプフィールドにおける値は、これに対応するオブジェクト番号が使用されているか、フリーかを示している。そのオブジェクト番号が使用されている場合、そのテーブルエントリのポインタフィールドは、対応するオブジェクトのルートノードに対するポインタを含むことになる。しかしながら、そのオブジェクト番号がフリーである場合、このときは、そのテーブルエントリのポインタフィールドは、そのフリーオブジェクト番号リストにある次のフリーオブジェクト番号に対する参照を含むことになる。
【００８４】
一般的に言えば、フリーオブジェクト番号は、フリーオブジェクト番号リストの先頭に加えられ、再利用されたオブジェクト番号もまた、フリーオブジェクト番号リストの先頭から取得される。
【００８５】
Ｓｙｓｔｅｍ，Ｄｅｖｉｃｅ，ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｖａｌｉｄａｔｉｎｇ  Ｄａｔａ  Ｓｔｒｕｃｔｕｒｅｓ  ｉｎ  ａ  Ｓｔｏｒａｇｅ  Ｓｙｓｔｅｍという名称の米国仮特許出願第６０／９７９，５６１号（これは上記で参照により組み込まれている）に考察されるように、その時々でフリーオブジェクト番号リストを含む間接オブジェクト２０４を検証することにより、全てのフリーオブジェクト番号がフリーオブジェクト番号リストに含まれ、「使用されている」オブジェクト番号は、フリーオブジェクト番号リストに含まれないことを確実にすることが必要である、あるいは望ましい。フリーオブジェクト番号リストを含む間接オブジェクト２０４を検証する１つの方法は、各々のフリーオブジェクト番号リストを冒頭から終わりまで詳しく点検することで、ループがないことを確実にし、リストの最後がヌル参照を有することを確実にすることである。しかしながら、作業中のデータストレージシステムにおいて、経時的に多数のオブジェクトが作成され削除されることはよくあることであるため、フリーオブジェクト番号リストは、かなり長いものになる可能性がある。さらにフリーオブジェクト番号リストは、順番通りではないが、その代わりに、オブジェクト番号が使用されたり、フリーになったりしたときに更新されるため、フリーオブジェクト番号リストの点検作業は一般に、個々にリンクしたリストの参照に従って、必然的に間接オブジェクト２０４をあちこち飛ぶことになる。このようなフリーオブジェクト番号リストの点検は一般に、ゆっくりであり、効率が悪い。
【００８６】
したがって、本発明の例示の一実施形態では、間接オブジェクトテーブル構造は、最上部から最下部まで順を追って点検され、「使用されている」及び「フリーの」オブジェクト番号は、ビットマップまたは他の適切なデータ構造を利用して追跡される。具体的には、特定のオブジェクト番号が使用されている場合、このときビットマップにおける対応するビットが選び出され、このビットが既に選び出されている場合、このとき間接オブジェクトは破損する（例えば「使用されている」オブジェクト番号が、先の「フリーな」エントリによって誤って参照されるため）。特定のオブジェクト番号がフリーな場合、このとき間接オブジェクトテーブル構造における対応するエントリが、フリーオブジェクト番号リストにおける次のフリーオブジェクト番号に対する参照を含むことで、このような次のオブジェクト番号に対応するビットが、ビットマップにおいて選び出され、万一そのビットが既に選び出されている場合、このとき間接オブジェクトは破損する（例えばフリーオブジェクト番号リストが、「使用されている」オブジェクト番号を含むため、あるいはフリーオブジェクト番号リストが、循環参照を含むため）。間接オブジェクトテーブル構造全体が点検された後、２つの開始テーブルエントリは（これはＤＳＢ２０２におけるポインタによって指されている）がチェックされるが、万一テーブルエントリ全体が「使用されている」場合、このとき間接オブジェクトは破損する。さらに間接オブジェクトテーブル構造の全体が点検された後、選び出されず残すべきビットのみが、２つのフリーオブジェクト番号リストに関する２つの開始テーブルエントリに関連するビットであり、これはＤＳＢ２０２におけるポインタによって指される。このようなビットのいずれかが選び出された場合、このとき間接オブジェクトは破損する。ビットマップにおける任意の他のビットが選び出されない場合、このとき対応するオブジェクト番号は、使用されないし、フリーオブジェクト番号リストにも含まれないが、この場合、間接オブジェクトは利用可能である（このような「リンクされない」フリーのエントリは、通常の過程では再利用されないため）。追加の処理を行なうことで、各々のフリーオブジェクト番号リストは、確実にヌル参照で終わることができる。
【００８７】
様々な代替の実施形態において、ビットマップは、全てゼロに初期化することができ、またビットマップにおける特定のビットは、このビットを設定する（すなわち１に）ことによって「選び出される」場合もあり、この点において、いわゆる「テストアンドセット」作業を利用することで、１回の作業でビットの値のテストと、ビットの設定の両方を行なうことができる。あるいはビットマップが、全て１に初期化される場合もあり、ビットマップにおける特定のビットは、このビットを消去する（すなわちゼロにする）ことによって「選び出される」場合もある。当然のことながら、他のタイプのデータ構造及び他のタイプのマーキングスキームが他の実施形態で使用される場合もある。本発明は、ビットマップの利用、任意の特定のタイプのデータ構造やマーキングスキームに限定されるものではない。
【００８８】
例示の一実施形態において、間接オブジェクトは、実際の記憶ブロックを持たない「擬似ファイル」として実装される場合もある。例示の一実施形態において、オブジェクトツリー構造（例えば図２に示されるように）内の実際のデータブロックに対するポインタを有する代わりに、間接オブジェクトツリー構造におけるこのようなポインタは、対応するオブジェクトのルートノードを指している。したがって例示の一実施形態において、間接オブジェクトは、対応するファイルシステムオブジェクトに関連するルートノードのセクターアドレスに各々のオブジェクト番号をマップする。間接オブジェクトツリー構造がこのとき、オブジェクト番号に基づいて点検されることで、対応するオブジェクトのルートノードに対するポインタを得ることができる。
【００８９】
例示の一実施形態において、間接オブジェクト「擬似ファイル」が構築されることで、共通のコードの一部を利用して、オブジェクト番号に基づいて間接オブジェクトツリー構造を点検することで、対応するオブジェクトのルートノードに対するポインタを獲得することができ、ファイルオフセットに基づいて他のオブジェクトツリー構造を点検することで、対応するデータブロックに対するポインタを獲得することができる。このような実施形態において、オブジェクト番号は基本的に、仮想ファイルオフセットに変換され、その後間接オブジェクトツリー構造は、他のオブジェクトツリー構造が実際のファイルオフセットを使用して点検されるのと同様の方法で点検される。間接オブジェクト「擬似ファイル」ツリー構造と、他のオブジェクトツリー構造の両方を点検するのに使用することができる共通コードを有することの１つの利点は、単一の論理ブロックを両方の機能に利用することができる点であり、これは特にハードウェアにおけるツリー点検機能に有利である。
【００９０】
例示のシステムオブジェクト
【００９１】
上記で考察したように、ファイルシステムは、様々なタイプのシステムオブジェクトを含む。一般的に言えば、システムオブジェクトは、固定式の事前に規定されたオブジェクト番号を有するが、特定のシステムオブジェクトは、可変のオブジェクト番号を有する場合もある。以下は、本発明の例示の一実施形態における一部のシステムオブジェクトの記載である。
【００９２】
ルートディレクトリオブジェクトは、その対応するオブジェクト番号にファイル名をマップするシステムオブジェクトである（すなわちそれはルートノードと、固定式の所定のオブジェクト番号を有する）。よってファイルが作成される際、ファイルストレージシステムは、このファイルに対してルートノードを割り当て、このファイルに対してオブジェクト番号を割り当て、ルートディレクトリオブジェクトにエントリを追加してオブジェクト番号にファイル名をマッピングし、間接オブジェクトにエントリを追加することで、このファイルのルートノードのディスクアドレスにオブジェクト番号をマッピングする。間接オブジェクトにおけるエントリは、ルートディレクトリオブジェクトのルートノードのディスクアドレスにルートディレクトリオブジェクト番号をマップする。
【００９３】
図１０は、本発明の例示の一実施形態による、ＤＳＢ２０２と、間接オブジェクト２０４と、ルートディレクトリオブジェクト６０６と、ファイルオブジェクト２０８の一般的な関係を証明する概略ブロック図である。上記に述べたように、間接オブジェクトにおけるエントリは、ルートディレクトリオブジェクトのルートノードのディスクアドレスにルートディレクトリオブジェクト番号をマップし、ルートディレクトリオブジェクトは、オブジェクト番号にファイル名をマップし、間接オブジェクトは、オブジェクトにオブジェクト番号をマップする。したがってファイルサーバ９００２がオブジェクトファイル名に基づいて特定のオブジェクトを突き止める必要があるとき、ファイルサーバ９００２は、間接オブジェクトを介してルートディレクトリオブジェクト６０６を突き止め（すなわちルートディレクトリオブジェクト６０６に関連するオブジェクト番号を使用して）、ルートディレクトリオブジェクト６０６を使用してその対応するオブジェクト番号にファイル名をマップし、その後オブジェクト番号を使用して間接オブジェクトを介してこのオブジェクトを突き止めることができる。
【００９４】
フリースペースビットマップオブジェクトは、ファイルストレージシステムにおけるフリーな記憶ブロックを示すシステムオブジェクトである（すなわちそれは、ルートノードと、固定式の所定のオブジェクト番号を有する）。間接オブジェクトにおけるエントリは、フリースペースビットマップオブジェクトのルートノードのディスクアドレスにフリースペースビットマップオブジェクト番号をマップする。
【００９５】
変更後のチェックポイントオブジェクトリストオブジェクトは、チェックポイントサイクルにおいて作成または変更されているオブジェクトを特定するシステムオブジェクトである（すなわちそれは、ルートノードと、固定式の所定のオブジェクト番号を有する）。各々のチェックポイントの開始点において、変更後のチェックポイントオブジェクトリストオブジェクトが作成される。異なるオブジェクトが、このチェックポイントの一部として形成または変更される度に、そのオブジェクト番号が、変更後のチェックポイントオブジェクトリストオブジェクトに書き込まれ、その結果チェックポイントが作成される際は、そのチェックポイントにおいて作成または変更された全てのオブジェクトを列挙する特定のオブジェクトが存在する。
【００９６】
フリーブロックオブジェクトは、特定のチェックポイントにおいてファイルシステムによって使用されなくなったデータブロックのトラックを維持するのに使用されるシステムオブジェクトである。フリーブロックオブジェクトは、フリーにするのに利用できるセクターアドレスを列挙している。特定のデータブロックがファイルシステムによって使用されなくなったことは、このデータブロックは、先のチェックポイント及び／または保持されるチェックポイントに関連する可能性があるため、必ずしもこのデータブロックを再利用するために空けることができることを意味するものではない。よって他の機構（例えばバックグラウンドクリーンアップタスク）を典型的に使用することで、フリーにするのにブロックがどのように利用可能で、いつ利用可能であるかを判断する。
【００９７】
考えられる一実施形態では、ファイルストレージシステムは、Ｎ個のチェックポイントのためにＮ個のフリーブロックオブジェクトを維持しており（この場合Ｎは典型的には３以上である）、間接オブジェクトは、固定式の所定のフリーブロックオブジェクト番号を使用してＮ個のフリーブロックオブジェクトに関する別個のエントリ（すなわち間接オブジェクトにおけるＮ個のエントリ）を含んでいる。このような実施形態では、特定のチェックポイント（例えばＮ＋１番目のチェックポイント）が削除されると、ファイルストレージシステムが、そのチェックポイントに関連するフリーブロックオブジェクトを処理するため、その中に含まれる情報が失われることはない。
【００９８】
代替の考えられる一実施形態では、ファイルストレージシステムは、Ｎ個を超えるフリーブロックオブジェクトを維持する場合もあり（たとえチェックポイントがＮ個だけ維持されていても）、その結果フリーブロックオブジェクトを、ランタイムプロセスではなく、バックグラウンドクリーンアッププロセスを利用して処理することができる。このような実施形態では、システム内のフリーブロックオブジェクトの数が変わる可能性もあるため、間接オブジェクト内に固定された数のエントリを有することは実用的ではなく、よってフリーブロックオブジェクトのディレクトリ（例えばフリーブロックディレクトリオブジェクト）が代わりに使用される場合もある。ここで間接オブジェクトにおける１つのエントリがフリーブロックディレクトリオブジェクトのために使用される場合もあり、フリーブロックディレクトリオブジェクトは、個々のブリーブロックオブジェクトに対するポインタを維持することができる。
【００９９】
保持されるチェックポイント構成オブジェクトは、保持されるチェックポイントのリストを維持するのに使用されるシステムオブジェクトである。間接オブジェクトにおけるエントリは、保持されるチェックポイント構成オブジェクトのルートノードのディスクアドレスに保持されるチェックポイント構成オブジェクト番号をマップする。保持されるチェックポイント構成オブジェクトを以下でさらに詳細に考察する。
【０１００】
多重チェックポイント
【０１０１】
特定の実施形態において、多様なチェックポイントを利用することで、多様なバージョンのファイルシステムを経時的に維持することができる。例えば多様な別々のルート構造（以後「動的スーパーブロック」または「ＤＳＢ）と呼ばれる）を使用することで、ファイルシステムの多様なインスタンシエイションを管理する。ＤＳＢは好ましくは、アクセスし易いようにストレージシステムにおける固定位置に記憶されるが、ＤＳＢは代替として他の方法で記憶される場合もある。典型的には３つ以上のＤＳＢが存在しており、いくつかのＤＳＢは固定式または可変であってよい。ＤＳＢの数には論理的な制限はない（但し恐らく様々な実装形態に関して実際の制限はある）。この方法では、ファイルを前の「チェックポイント」に戻す必要がある、あるいは戻すことが望ましい場合、選択するのに多様な「チェックポイント」があるため、このファイルシステムを戻すことができる元のままのバージョンのファイルシステムが存在する、あるいは特定のバージョンのファイルシステムを含むチェックポイントが存在するといったより望ましい機会が提供される。
【０１０２】
ファイルシステムリクエストの処理作業は、一連のチェックポイントによって線引きされており、これらのチェックポイントは、例えば１０秒毎など一部のユーザが特定した間隔の頻度を下回らないで現れるように予定されている。チェックポイントは、例えば現行のチェックポイントに使用されている不揮発性ＲＡＭの半分以上が一杯になった場合、セクターキャッシュが一杯になった場合、ユーザが保持されるチェックポイントを要求した場合（以下で考察する）、あるいは他の適切な状況下などの、それ以外のときに取得される場合もある。
【０１０３】
各々の連続するチェックポイントに関して、直前のチェックポイントから先に記憶されたファイル構造情報を受け継いだ現在のファイル構造情報が、オンディスクで記憶されている。チェックポイントは順番通りに番号が付けられ、ファイルリクエストの一時的なグループ処理に使用される。
【０１０４】
上記に考察したように、本発明の例示の実施形態は、Ｎ個のＤＳＢを保持する（この場合Ｎは、３より大きく、例えば１６である）。これらのＤＳＢを使用して、連続するチェックポイントを取得する。
【０１０５】
したがって任意の所与の時に、現行（作業中の）のバージョンのファイルシステムと、ファイルシステムの１つ以上のチェックポイントバージョンが存在する。ストレージシステムは典型的にはかなり動的であるため、現行バージョンのファイルシステムは、チェックポイントを取得したほとんど直後に、ほぼ間違いなく変化し始める。例えばファイルシステムオブジェクトは、経時的に追加、削除または変更されることがある。しかしながら、チェックポイントを維持する目的で、記憶されたチェックポイントに関連するいずれの構造も、少なくとも特定のチェックポイントが削除されたり、あるいは上書きされるまでは変わることが認められていない。したがって現行バージョンのファイルシステムにおけるオブジェクトが追加、削除及び変更される際、必要に応じて新しいバージョンのオブジェクトツリー構造が作成され、種々のポインタがこれに従って更新される。
【０１０６】
例えば図１１は、チェックポイント番号１において形成された例示のオブジェクトに関するオブジェクト構造を概略的に示している。このオブジェクトは、４つのデータブロックを含んでおり、すなわちデータブロック０（２３１０）と、データブロック１（２３１２）と、データブロック２（２３１４）と、データブロック３（２３１６）を含む。直接ノード２３０６は、データブロック０（２３１０）に対するポインタと、データブロック１（２３１２）に対するポインタを含む。直接ノード２３０８は、データブロック２（２３１４）に対するポインタと、データブロック３（２３１６）に対するポインタを含む。間接ノード２３０４は、直接ノード２３０６に対するポインタと、直接ノード２３０８に対するポインタを含む。ルートノード２３０２は、間接ノード２３０４に対するポインタを含む。全てのノードと、全てのブロックは、チェックポイント番号１によってはっきりと表されている。
【０１０７】
ここでデータブロック０（２３１０）が、チェックポイント番号３において変更されると仮定してみる。ルートノード２４０２は、先のチェックポイントの一部であるため、それを変更することはできない。代わりにファイルサーバ９００２のオブジェクト記憶サブモジュールは、古いルートノード２３０２のコピーをディスク上のフリースペースに保存し、この新しいルートノードをチェックポイント番号３（すなわち、それが形成されたチェックポイント）によって表す。図１２は、新しいルートノード２４０３を作成した後のオブジェクト構造を概略的に示している。この時点で、ルートノード２４０２と新しいルートノード２４０３は共に、間接ノード２３０４を指している。
【０１０８】
オブジェクト記憶サブモジュールはその後、このルートノードから開始して、それがデータブロック０（２３１０）のディスクリプタに達するまでオブジェクト構造を点検する。データブロック０（２３１０）は、先のチェックポイントの一部であるため、それを変更することはできない。代わりにオブジェクト記憶サブモジュールは、変更後のデータブロック２３１０のコピーをディスク上のフリースペースに作成し、この新しいデータブロックをチェックポイント番号３（すなわち、それが形成されたチェックポイント）によって表す。図１３は、新しいデータブロック２５１０を形成した後のオブジェクト構造を概略的に示している。
【０１０９】
オブジェクト記憶サブモジュールは、今度は、直接ノードに新しいデータブロック２５１０に対するポインタを据える必要があるが、オブジェクト記憶サブモジュールは、直接ノード２３０６に新しいデータブロック２５１０に対するポインタを据えることは不可能であり、その理由は、直接ノード２３０６は、これ以前のチェックポイントの構成要素であるためである。したがってオブジェクト記憶サブモジュールは、新しいデータブロック０（２５１０）と、古いデータブロック１（２３１２）に対するポインタを含め、ディスク上のフリースペースに直接ノード２３０６の変更後のコピーを作成し、この直接ノードをチェックポイント番号３（すなわちそれが形成されたチェックポイント）によって表す。図１４は、新しいデータブロック０（２５１０）と、古いデータブロック１（２３１２）に対するポインタを含め新しい直接ノード２６０６が形成された後の、オブジェクト構造を概略的に示している。
【０１１０】
オブジェクト記憶サブモジュールは、このとき、間接ノードに新しい直接ノード２６０６に対するポインタを据える必要があるが、オブジェクト記憶サブモジュールが、間接ノード２３０４に新しい直接ノード２６０６に対するポインタを据えることは不可能であり、それは、間接ノード２３０４は先のチェックポイントの構成要素であるためである。よってオブジェクト記憶サブモジュールは、新しい直接ノード２６０６と、古い直接ノード２３０８に対するポインタを有する変更後の間接ノード２３０４のコピーを形成する。図１５は、新しい直接ノード２６０６と、古い直接ノード２３０８に対するポインタを含む新しい直接ノードを形成した後のオブジェクト構造を概略的に示している。
【０１１１】
最終的にオブジェクト記憶サブモジュールは、新たなルートノード２４０３に新しい間接ノード２７０４に対するポインタを書き込む。図１６は、新たなルートノード２４０３に新しい間接ノード２７０４に対するポインタが、書き込まれた後のオブジェクト構造を概略的に示している。
【０１１２】
データブロック０の変更が完了した後、ブロック２４０２、２３０４、２３０６及び２３１０は、チェックポイント１バージョンの構成要素であって、オブジェクトの現行のチェックポイント３バージョンの構成要素ではなく、ブロック２３０８、２３１２、２３１４及び２３１６は、チェックポイント１型と、オブジェクトの現行のチェックポイント３バージョンの両方の構成要素であり、ブロック２４０３、２７０４、２６０６及び２５１０は、オブジェクトの現行のチェックポイント３バージョンの構成要素であり、チェックポイント１バージョンの構成要素ではないことに留意されたい。
【０１１３】
新しいノードは、必ずしも上記に記載した順番で形成される必要はないことに留意されたい。例えば新しいルートノードは、最初ではなく最後に形成される場合もある。
【０１１４】
よってファイルシステムオブジェクトが変更される際、この変化がオブジェクトツリー構造全体まで広がるため、変更後のオブジェクトのために新しいルートノードが作成される。新たなルートノードは、所与のチェックポイントにおいて一度特定のオブジェクトのために作成される必要があり、この新たなルートノードは、１つのチェックポイントにおいて複数回修正される場合もある。
【０１１５】
現行バージョンのファイルシステムに新たなバージョンのオブジェクトが含まれるように、現行の間接オブジェクトは、以前のバージョンのオブジェクトのルートノードではなく、変更後のオブジェクトのルートノードを指すように変更される。例えば再び図１６を参照すると、現行の間接オブジェクトは、このオブジェクトに関連するオブジェクト番号に関して、ルートノード２４０２ではなくルートノード２４０３を指すように更新される。
【０１１６】
同様に新しいオブジェクトが作成される、あるいは既存オブジェクトが現行バージョンのファイルシステム内で削除される場合、現行の間接オブジェクトは、これに従って更新される。例えば新しいオブジェクトが作成される場合、間接オブジェクトは、この新しいオブジェクトのルートノードに対するポインタを含むように変更される。既存のオブジェクトが削除される場合、間接オブジェクトは、対応するオブジェクト番号をフリーなものとして表すように変更される。
【０１１７】
また間接オブジェクトは、特定のルートノードを有するツリー構造であるため、間接オブジェクトの変更もツリー構造全体にまで広がるため、変更後の間接オブジェクトのために新たなルートノードが作成されることになる。ここでも、新しいルートノードは単に、所与のチェックポイントにおいて一度間接オブジェクトのために作成される必要があり、この新しいルートノードは、１つのチェックポイントにおいて複数回修正される場合もある。
【０１１８】
よって特定のチェックポイントにおいて新しいバージョンの間接オブジェクトが作成される際、このチェックポイントに関連するＤＳＢは、変更後の間接オブジェクトに対する新たなルートノードを指すように更新される。よって各々の型（すなわち現行バージョンと、各々のチェックポイントの型）のファイルシステムは一般に、別々のバージョンの間接オブジェクトを含むことになり、それぞれが異なる間接オブジェクトルートノードを有する（但し、１つ以上の間接ノード、直接ノード及び／またはデータブロックを共有する場合もある）。
【０１１９】
例示の一実施形態において、ＤＳＢは循環リストとしてみなされ、チェックポイントは、予定された間隔で取得され続けるため、定常状態において、各々の新しいチェックポイントが古いチェックポイントを「上書き」するため、この「上書きされた」チェックポイントによって表される古いバージョンのファイルシステムは失われる。
【０１２０】
図１７は、本発明の例示の一実施形態による、チェックポイントを取得する前の様々なファイルシステム構造を示す概略ブロック図である。具体的には２０２及び２０３と番号が付けられた２つのＤＳＢが示されている。ＤＳＢ２０２は、現行バージョンのファイルシステムに関連しており、現行バージョンの間接オブジェクト２０４のルートノードに対するポインタを含む。ＤＳＢ２０３は、次に利用可能なＤＳＢである。
【０１２１】
現行バージョンのファイルシステムからチェックポイントを作成するために、特定の循環リストにおける次のＤＳＢ（すなわちこの例ではＤＳＢ２０３）が、新しいチェックポイントのために初期化される。とりわけこのような初期化には、次のチェックポイント番号をＤＳＢ２０３に書き込むことと、間接オブジェクト２０４のルートノードに対するポインタをＤＳＢ２０３に記憶することが含まれる。図１８は、本発明の例示の一実施形態による、チェックポイントを取得した後の様々なファイルシステム構造を示す概略ブロック図である。この時点で、ＤＳＢ２０２は、最近のチェックポイントバージョンのファイルシステムを表しており、ＤＳＢ２０３は、現行の（作業中の）バージョンのファイルシステムを表している。
【０１２２】
上記で考察したように、現行バージョンのファイルシステムは、オブジェクトが形成、変更及び削除される際に変わる場合がある。また上記で考察したように、現行バージョンのファイルシステムが変わる際、新しいバージョンの間接オブジェクト（新しいルートノードを有する）が作成される。その結果、現行バージョンの間接オブジェクトが、図１８に描写されるようにチェックポイントが取得された後に変わることで、新たな間接オブジェクトルートノードが作成される際、現行バージョンのファイルシステムに対するＤＳＢ（すなわち図１８におけるＤＳＢ２０３）が、以前の間接オブジェクトルートノードではなく、新たな間接オブジェクトルートノードを指すように更新される。図１９は、本発明の例示の一実施形態による、間接オブジェクトを変更した後の様々なファイルシステム構造を示す概略ブロック図である。ここでＤＳＢ２０２は、チェックポイントバージョンのファイルシステムに関連しており、チェックポイントバージョンの間接オブジェクト２０４を指しており、その一方でＤＳＢ２０３は、現行バージョンのファイルシステムに関連しており、新たな間接オブジェクト２０５のルートノードを指している。
【０１２３】
上記で考察したようにチェックポイントは一般に、規則的な間隔で取得されるため、複数のバージョンのファイルシステムが経時的に維持される。各々のチェックポイントにおいて、現行の（作業中の）バージョンのファイルシステムが、循環リストにおける次に連続するＤＳＢに移動する。特定のチェックポイント型がシステムから削除されると（例えばそのＤＳＢが再利用されたため）、例えばもはや使用されていない記憶装置を識別し、フリーにするバックグラウンドタスクを利用して、削除されたチェックポイントに関連する記憶装置をいずれ回復させることができる。
【０１２４】
代替の一実施形態において、特定のＤＳＢが、連続するチェックポイントに関する現行のＤＳＢとして再利用される場合もあり、他のＤＳＢは、チェックポイントバージョンのファイルシステムを保存するのに使用される。
【０１２５】
図２０は、本発明の例示の一実施形態による、チェックポイントを取得する前の様々なファイルシステム構造を示す概略ブロック図である。具体的には、２０２及び２０３と番号が付けられた２つのＤＳＢが示されている。ＤＳＢ２０２は、現行バージョンのファイルシステムに関連しており、現行バージョンの間接オブジェクト２０４のルートノードに対するポインタを含む。ＤＳＢ２０３は、次に利用可能なＤＳＢである。
【０１２６】
現行バージョンのファイルシステムからチェックポイントを作成する目的で、次のＤＳＢ２０３が、新しいチェックポイントのために初期化される。とりわけこのような初期化には、次のチェックポイント番号をＤＳＢ２０３に書き込むことと、間接オブジェクト２０４のルートノードに対するポインタをＤＳＢ２０３に記憶することが含まれる。図１８は、本発明の例示の一実施形態による、チェックポイントを取得した後の様々なファイルシステム構造を示す概略ブロック図である。この時点で、ＤＳＢ２０３は、最近のチェックポイントバージョンのファイルシステムを表しており、ＤＳＢ２０２は、現行の（作業中の）バージョンのファイルシステムを表している。
【０１２７】
上記で考察したように、現行バージョンのファイルシステムは、オブジェクトが形成、変更及び削除される際に変わる場合がある。また上記で考察したように、現行バージョンのファイルシステムが変わる際、新しいバージョンの間接オブジェクト（新しいルートノードを有する）が作成される。その結果、現行バージョンの間接オブジェクトが、図２１に描写されるようにチェックポイントが取得された後に変わることで、新たな間接オブジェクトルートノードが作成される際、現行のファイルシステムバージョンのためのＤＳＢ（すなわち図２１におけるＤＳＢ２０２）が、以前の間接オブジェクトルートノードではなく、新たな間接オブジェクトルートノードを指すように更新される。図２２は、本発明の例示の一実施形態による、間接オブジェクトを変更した後の様々なファイルシステム構造を示す概略ブロック図である。ここでＤＳＢ２０３は、チェックポイントバージョンのファイルシステムに関連しており、チェックポイントバージョンの間接オブジェクト２０４を指しており、その一方でＤＳＢ２０２は、現行バージョンのファイルシステムに関連しており、新たな間接オブジェクト２０５のルートノードを指している。
【０１２８】
特定のボリュームがマウントされる際、システムは通常、最後の有効なチェックポイントに戻る必要がある。しかしながら、システムまたはユーザが、先の有効なチェックポイントに戻ることを選択するような場合もある。本発明の実施形態では、ファイルサーバ９００２は、２つ以上のチェックポイントを維持することが可能であるため、このファイルシステムが戻ることができる複数のバージョンのファイルシステムが存在する可能性がある。オペレータが種々のチェックポイントバージョンの内容を調べることができることにより、ファイルシステムを戻すためのチェックポイントバージョンの選択が容易になるという効用が与えられる。
【０１２９】
たとえＮ個のチェックポイントをシステム内に維持することができるにしても（この場合、Ｎは典型的には３つ以上であり、ユーザが構成可能なものであってよい）、ユーザ発動式の機構によって特定のチェックポイントの保持が可能であるため、ユーザがそれを削除することを選択するまで、それは有効かつアクセス可能（読取り専用）なままである。保持されるチェックポイントは基本的に、特定のチェックポイントにおける読取り専用バージョンのファイルシステム構造である。複数の保持チェックポイントを取得することが可能であり、機構は、選択された保持チェックポイントを削除する作業、あるいはファイルシステムを選択された保持チェックポイントに戻す（例えばファイルシステムをカタストフィの後の既知の状態に戻す）作業を含む。保持チェックポイントがアクティブな状態である限り、この保持チェックポイントを有するノード及びデータブロックを変更したり、フリースペースに戻したりすることはできない。ノードやデータブロックが、複数の保持チェックポイントの構成要素である可能性があり、特定のノードやデータブロックは、ノードやデータブロックが、少なくとも１つの保持チェックポイントの構成要素である限り、フリースペースに戻すことはできないことに留意されたい。
【０１３０】
例示の一実施形態において、保持チェックポイントの取得作業はとりわけ、対応するＤＳＢのコピーをオンディスクのフリースペースに保存することと、記憶したＤＳＢのコピーに対する参照を保持チェックポイント構成オブジェクトに記憶することを含む。保持チェックポイントがファイルシステムに記憶される限り、保持チェックポイントに関連する構造は削除することができない。これは、保持チェックポイントが取得されるチェックポイントが上書きされている場合でも当てはまる。例示の一実施形態においてファイルサーバ９００２は、保持チェックポイントに関連する構造が削除されるのを阻止する機構を含んでいる。
【０１３１】
ファイルクローニング
【０１３２】
本発明の特定の実施形態において、ファイルクローニング機構を利用することで、例えばユーザがファイルのコピーを作成する際に、ファイルシステム内にファイルのコピー（クローン）を迅速に形成することが可能になる。例示の実施形態において、ソースオブジェクトのクローンは、少なくとも最初はこのソースオブジェクトの様々な要素（例えば間接ノード、直接ノード及びデータブロック）に対する参照を含む特定の構造によって表される。読取り専用クローンと、可変クローンを共に形成することができる。ソースファイルとそのクローンは最初はこのような要素を共有し、ソースファイルまたは可変クローンが変更されたときは、変更されない要素を共有し続ける。ソースファイルに関連するデータストリーム（すなわち間接／直接オーノード）を表すユーザデータブロックやメタブロックをクローンが形成されるときにコピーする必要はない。このようなファイルクローニングの一部の特徴には、以下が含まれる。
−ファイルシステムオブジェクトのデータストリームを、ソースオブジェクトのデータストリームのサイズに関わらず比較的固定された時間量で効果的に迅速にクローンすることができ、これは、このデータストリームを構成するいずれのユーザデータブロックもコピーする必要がないためである。またデータストリーム（すなわち間接／直接オーノード）を表すいずれのメタブロックもコピーする必要がない。極めて少ない一定の数のメタブロックが可変である。
−クローン／コピーされたオブジェクトにＩ／Ｏの対応させる複雑さは、通常のオブジェクトに匹敵する。
−特定のファイルやクローンをクローンすることができる回数は、ファイルシステム内のフリースペースの大きさによってのみ制限される。
−特定のファイルシステムが支持することができるクローンの数は、ファイルシステム内のフリースペースの大きさによってのみ制限される。
−このファイルクローニングは、固有のファイルの重複排除特性を有しており、すなわちソースファイルの完全なコピーを作成し、その後重複排除を行なうのではなく、そのクローンは基本的に重複排除されたファイルとして作成され、このファイルは、データ及びメタデータブロックをソースファイルと共有する。
−共有されるブロックの破損は、複数のファイルに影響を与えることになるが、データの破損は、冗長記憶装置（すなわちＲＡＩＤ制御装置）及び他の機構によって軽減される。
【０１３３】
例示の一実施形態において、ファイルシステムオブジェクトは、先ずソースオブジェクトの読取り専用クローン（スナップショット）を表す新たなオブジェクトを作成し、（このオブジェクトは以後、「データ・ストリーム・スナップショット」オブジェクトまたは「ＤＳＳ」と呼ばれる）、その後、このオブジェクトの可変クローンを作成することによってクローンされる。クローンオブジェクトのルートオーノードにおけるブロックポインタと、オーノードブロックポインタは最初、ソースオブジェクトと同一のブロックを指すように設定される。ソースオブジェクトからの特定のメタデータ（例えばファイル時間、安全性など）、及び名前が付けられたデータストリームは、クローンオブジェクトにコピーされない。メタデータが、ソースオブジェクト及びクローンオブジェクトにおいて維持されることで、データ・ストリーム・スナップショットオブジェクトがソースオブジェクトと、可変クローンオブジェクトに結合され、またソースオブジェクトと、可変クローンオブジェクトが、データ・ストリーム・スナップショットオブジェクトに結合される。例示の一実施形態において、データ・ストリーム・スナップショットオブジェクトは、ファイルシステムのユーザには見ることができない「隠し」オブジェクトである。ソースオブジェクト及び可変クローンオブジェクトは共に、事実上書き込み可能なバージョンのＤＳＳオブジェクトになり、事実上ＤＳＳオブジェクトとの相違点を記憶する。
【０１３４】
データ・ストリーム・スナップショットオブジェクトを作成する前は、システムは好ましくは、ソースオブジェクトが休止していることを保証する。例示の一実施形態においてこれは以下のステップを含む。
【０１３５】
ステップＡ１．ソースオブジェクトを変化に対してロックする。
【０１３６】
ステップＡ２．ファイルシステムチェックポイントを実行するが、これは事実上所与のファイルシステムに対するクローン作成に通し番号を振る（但し作成速度は、ファイルシステムが以前のチェックポイントをディスクにコミットする速度によって制限されるため、記憶側が遅れることで作成時間がより長くなる）。
【０１３７】
その後チェックポイントが完了した後、システムは、データ・ストリーム・スナップショットオブジェクトを作成するが、これは以下のステップを含む。
【０１３８】
ステップＡ３．データ・ストリーム・スナップショットオブジェクトを作成する。
【０１３９】
ステップＡ４．ソースオブジェクトのルートオーノードからデータ・ストリーム・スナップショットオブジェクトのルートオーノードにブロックポインタをコピーする。
【０１４０】
ステップＡ５．現行のチェックポイント番号をソースオブジェクトルートオーノードに記録する。これはオブジェクトがクローン後に入るチェックポイント番号（「ＣＣＮ」）であり、これは、オブジェクトデータストリームが、その関連するデータ・ストリーム・スナップショットオブジェクトのデータストリームから分岐することができる最も早いチェックポイントを規定する。
【０１４１】
システムはまた、以下のメタデータを維持することで、このソースオブジェクトをデータ・ストリーム・スナップショットオブジェクトに関連付ける。
【０１４２】
ステップＡ６．データ・ストリーム・スナップショットオブジェクトのハンドルが、ソースオブジェクトのメタデータに記録される。
【０１４３】
ステップＡ７．データ・ストリーム・スナップショットオブジェクトを参照するオブジェクトの参照カウント及びリストが、データ・ストリーム・スナップショットオブジェクトのメタデータに記録される。
【０１４４】
ソースオブジェクトが既にクローンである（すなわち特定のクローンがクローンされている）場合、このときステップ４と５の間に２つの追加ステップがある。
【０１４５】
ステップＡ４ａ．新しいデータ・ストリーム・スナップショットオブジェクトをソースファイルの現行のデータ・ストリーム・スナップショットオブジェクトに関連付ける。
【０１４６】
ステップＡ４ｂ．ソースファイルの現行のクローン後に入るチェックポイント番号を新しいデータ・ストリーム・スナップショットオブジェクトのルートオーノードに記録する。
【０１４７】
データ・ストリーム・スナップショットオブジェクトのデータストリームの可変クローンを有する別のオブジェクトを以下のように作成することができる。
【０１４８】
ステップＢ１．新しいファイルシステムオブジェクトを作成する。
【０１４９】
ステップＢ２．データ・ストリーム・スナップショットオブジェクトのルートオーノードから新しいオブジェクトのルートオーノードにブロックポインタをコピーする。
【０１５０】
ステップＢ３．現行のチェックポイント番号を新しいオブジェクトのルートオーノードに記録する。
【０１５１】
ステップＢ４．データ・ストリーム・スナップショットオブジェクトのハンドルを新しいオブジェクトのメタデータに記録する。
【０１５２】
ステップＢ５．データ・ストリーム・スナップショットオブジェクトの参照カウントをインクリメントし、新しいオブジェクトのハンドルをデータ・ストリーム・スナップショットオブジェクトの参照リストに加える。
【０１５３】
クローン後に入るチェックポイント番号（ＣＣＮ）は、オブジェクトのチェックポイント番号（図１１では「ＣＮ」と名前が付けられている）とは別個であり、これはオブジェクトの最後の変更のチェックポイントを記録することに留意されたい。これらは共に、オブジェクトルートオーノードに記憶される。
【０１５４】
ユーザデータまたはメタデータブロックを変更する場合、ファイルシステムは、このブロックを新たなスペースに書き込む必要があるかどうかを判断する際、このブロックが既にクローンオブジェクトの関連するデータ・ストリーム・スナップショットオブジェクトと異なっているかどうかを考慮する。
・クローンのクローン後に入るチェックポイント番号より小さいチェックポイント番号を有するポインタを介するユーザ／メタデータブロック（異ならないブロック）に対する変更を新たなスペースに書き込む必要がある。
・クローンのクローン後に入るチェックポイント番号より大きい、あるいはこれと等しいチェックポイント番号を有するポインタを介するユーザ／メタデータブロック（異なったブロック）に対する変更は、ほぼ上記に記載したように「ライブ」ファイルシステムにおけるオブジェクトに対する通常のルールに従う。
【０１５５】
上記に記載したファイルクローニング概念の一部は、以下の例によって実証することができ、これらは図１１に表されるファイルシステムオブジェクトに基づいている。
【０１５６】
図２３は、本発明の例示の実施形態による、ソースオブジェクト（ファイルＡ）２８０２と、隠しデータ・ストリーム・スナップショットオブジェクト２８０３と、可変クローン２８０５の関係を概略的に示している。  
【０１５７】
図２４は、本発明の例示の実施形態による、概念上のチェックポイント番号４において図１１に表されるファイルシステムオブジェクトをクローニングした後のオブジェクト２８０２、２８０３及び２８０５を概略的に示している。
【０１５８】
上記で考察したように、ソースオブジェクトがロックされ、チェックポイントが取得された後（ステップＡ１及びＡ２）、データ・ストリーム・スナップショットオブジェクト２８０３が作成され（ステップＡ３）、ソースオブジェクトのルートオーノード２３０２からのブロックポインタが、データ・ストリーム・スナップショットオブジェクト２８０３のルートオーノードにコピーされる（ステップＡ４）。現行のチェックポイント番号が、ソースオブジェクト２８０２のルートオーノードに記録される（ステップＡ５）。データ・ストリーム・スナップショットオブジェクト２８０３のハンドルが、ソースオブジェクト２８０２メタデータに記録される（ステップＡ６）。データ・ストリーム・スナップショットオブジェクト２８０３を参照する参照カウント及びリストが、データ・ストリーム・スナップショットオブジェクト２８０３のメタデータに記録される（ステップＡ７）。この時点で、ソースオブジェクト２８０２のみがデータ・ストリーム・スナップショットオブジェクト２８０３を参照しており、参照カウントは（一時的に）１に設定される。
【０１５９】
また上記で考察したように、可変クローン２８０５が作成され（ステップＢ１）、データ・ストリーム・スナップショットオブジェクト２８０３のルートオーノードからのブロックポインタが、オブジェクト２８０５のルートオーノードにコピーされる（ステップＢ２）。現行のチェックポイント番号が、オブジェクト２８０５のルートオーノードにコピーされる（ステップＢ３）。データ・ストリーム・スナップショットオブジェクト２８０３のハンドルが、オブジェクト２８０５のメタデータに記録される（ステップＢ４）。データ・ストリーム・スナップショットオブジェクト２８０３における参照カウントがインクリメントされ、オブジェクト２８０５のハンドルが、データ・ストリーム・スナップショットオブジェクト２８０３の参照リストに記録される（ステップＢ５）。
【０１６０】
２８０２と２８０３の間にある点線の両方向の矢印は、これら２つの構造の結合状態を表しており、同様に２８０３と２８０５の間にある点線の両方向の矢印は、これらの２つの構造の結合状態を表していることに留意されたい。
【０１６１】
可変クローン２８０５が作成される際、ブロックポインタなどの情報が、ＤＳＳオブジェクト２８０３からではなく、ソースオブジェクト２８０２からコピーされる場合もあるが、ＤＳＳオブジェクト２８０３からコピーされるのが好ましく、これによりソースオブジェクト２８０３を休止状態からより早く解放することが可能になる（例えばＤＳＳオブジェクト２８０３を作成した後であり、可変クローン２８０５が作成される前など）ことに留意されたい。
【０１６２】
ソースオブジェクト２８０２が、変更される前に再度クローン形成される場合、第２の可変クローンが作成される。図２５は、本発明の例示の一実施形態による、ソースオブジェクト（ファイルＡ）２８０２と、隠しデータ・ストリーム・スナップショットオブジェクト２８０３と、２つの可変クローン２８０５及び２８０７の関係を概略的に示している。
【０１６３】
図２６は、本発明の例示の一実施形態よる、概念上のチェックポイント番号６において第２の可変クローンが作成された後の、オブジェクト２８０２、２８０３、２８０５及び２８０７を概略的に示している。具体的には第２の可変クローン２８０７が作成され、データ・ストリーム・スナップショットオブジェクト２８０３のルートオーノードからのブロックポインタが、オブジェクト２８０７のルートオーノードにコピーされる。現行のチェックポイント番号が、オブジェクト２８０７のルートオーノードに記録される。データ・ストリーム・スナップショットオブジェクト２８０３のハンドルが、オブジェクト２８０７のメタデータに記録される。データ・ストリーム・スナップショットオブジェクト２８０３における参照カウントがインクリメントされ、オブジェクト２８０７のハンドルが、データ・ストリーム・スナップショットオブジェクト２８０３の参照リストに記録される。
【０１６４】
ソースオブジェクト２８０２は事実上、データ・ストリーム・スナップショットオブジェクト２８０３の可変コピーであるため、ソースオブジェクト２８０２が経時的に変更される場合があり、これによりソースオブジェクト２８０２のデータストリームは、データ・ストリーム・スナップショットオブジェクト及び他のファイルクローンのデータストリームと異なるようになる。例えば図２４及び図１１から１６に示されるオブジェクト構造を再度参照すると、例えばいわば概念上のチェックポイント５において２８０２でルートされたソースオブジェクトのデータブロック０（２３１０）の変更は、新しい間接オーノードを指すルートオーノード２８０２を有する分岐ツリー構造となり（図１１に示されるオブジェクトが、図１２から１６に示されるように概念上のチェックポイント３において変更される際、ルートオーノード２４０３が最後には、間接オーノード２７０４を指すようになるとの同様に）、ルートオーノード２８０３と、２８０５は、間接オーノード２３０４を指し続ける。同様にデータ・ストリーム・スナップショットオブジェクトの可変クローンが経時的に変更される場合があり、これによりこの可変コピーのデータストリームは、データ・ストリーム・スナップショットオブジェクト及び他のクローンのデータストリームとは異なることになる。
【０１６５】
ソースオブジェクトが変更された後、変更後のソースオブジェクトのコピーが作成される場合、このとき変更後のソースオブジェクトのために、追加ステップＡ４ａ及びＡ４ｂを含めた上記に記載した過程を使用して第２のデータ・ストリーム・スナップショットオブジェクトが作成され、その後この第２のデータ・ストリーム・スナップショットオブジェクトの可変クローンが作成される。
【０１６６】
図２７は、変更後のソースオブジェクト２８０２’と（アポストロフィは、変更後のソースオブジェクトの型を表している）、２つの元のソースオブジェクトクローン２８０５及び２８０７を有する第１のデータ・ストリーム・スナップショットオブジェクト２８０３と、第２のデータ・ストリーム・スナップショットオブジェクト２８０９と、第２のデータ・ストリーム・スナップショットオブジェクト２８０９の可変クローン２８１１の関係を概略的に示している。ここに見ることができるように、データ・ストリーム・スナップショットオブジェクト２８０３及び２８０９は、論理上に階層的に結合されている。
【０１６７】
図２８は、本発明の例示の実施形態による、概念上のチェックポイント番号８において変更後のソースオブジェクト２８０２’をクローニングした後の、オブジェクト２８０２’、２８０３、２８０９及び２８１１を概念的に示している。
【０１６８】
上記で考察したように、データ・ストリーム・スナップショットオブジェクト２８０９が作成され（ステップＡ３）、ソースオブジェクト２８０２’のルートオーノードからのブロックポインタが、データ・ストリーム・スナップショットオブジェクト２８０９のルートオーノードにコピーされる（ステップＡ４）。データ・ストリーム・スナップショットオブジェクト２８０９は、ソースオブジェクトの現行のデータ・ストリーム・スナップショットオブジェクト２８０３に関連付けられ（ステップＡ４ａ）、これは具体的にはＤＳＳ２８０３のハンドルをＤＳＳ２８０９に記録し、ＤＳＳ２８０９のハンドルをＤＳＳ２８０３のオブジェクトリストに記録し、ＤＳＳ２８０３における参照カウントをインクリメントすることによって行なわれる。ソースファイル２８０２’の現行のクローン後に入るチェックポイント番号が、ＤＳＳ２８０９のルートノードに記録される（ステップＡ４ｂ）。現行のチェックポイント番号が、ソースオブジェクト２８０２’のルートオーノードに記録される（ステップＡ５）。データ・ストリーム・スナップショットオブジェクト２８０９のハンドルが、ソースオブジェクト２８０２’メタデータに記録される（ステップＡ６）。データ・ストリーム・スナップショットオブジェクト２８０９を参照する参照カウント及びオブジェクトリストが、データ・ストリーム・スナップショットオブジェクト２８０９のメタデータに記録される（ステップＡ７）。この時点で、ソースオブジェクト２８０２’のみが、データ・ストリーム・スナップショットオブジェクト２８０９を参照しており、その参照カウントは（一時的に）１に設定される。
【０１６９】
また上記で考察したように、可変ファイルコピー２８１１が作成され（ステップＢ１）、データ・ストリーム・スナップショットオブジェクト２８０９のルートオーノードからのブロックポインタがオブジェクト２８１１のルートオーノードにコピーされる（ステップＢ２）。現行のチェックポイント番号が、オブジェクト２８１１のルートオーノードにコピーされる（ステップＢ３）。データ・ストリーム・スナップショットオブジェクト２８０９のハンドルが、オブジェクト２８１１のメタデータに記録される（ステップＢ４）。データ・ストリーム・スナップショットオブジェクト２８０９における参照カウントがインクリメントされ、オブジェクト２８１１のハンドルが、データ・ストリーム・スナップショットオブジェクト２８０９の参照リストに記録される（ステップＢ５）。
【０１７０】
ソースオブジェクト２８０２’は経時的にさらに変更される場合もあり、将来バージョンのこのオブジェクトのクローンは、第１のＤＳＳ２８０３及び第２のＤＳＳ２８０９に階層的に結合された追加のデータ・ストリーム・スナップショットオブジェクトとなることに留意されたい。同様にクローン２８０５及び／またはクローン２８０７が経時的に変更される場合もあり、それらのクローン（未変更のものと変更後のものの両方）のコピーを、ほぼ上記に記載したようにその時々で作成することができ、必要に応じて追加のＤＳＳオブジェクトが階層的に加えられる。未変更のオブジェクト２８０５のクローニングは実質的に、未変更のソースオブジェクト２８０２のクローニングと同様であり、これは、第１のＤＳＳオブジェクト２８０３に結合された別の可変クローンとなり、これにより変更後のバージョンのオブジェクト２８０５のクローニングが、新しいＤＳＳに結合された変更後のオブジェクトの可変コピーを作成することになり、この新しいＤＳＳが今度は、第１のＤＳＳオブジェクト２８０３に結合される。
【０１７１】
例示の一実施形態において、特定のソースオブジェクトに関連するＤＳＳオブジェクトは、このソースオブジェクト及び全てのクローンが削除されるまで、ファイルシステム内に残ったままである。よって例えば、図２７に示されるクローン２８０５、２８０７及び２８１１がたとえ削除されたとしても、図２９に概略的に表されるように、ＤＳＳ２８０３、ＤＳＳ２８０９及びオブジェクト２８０２’は残される。この例では、ファイルシステムは、現行バージョンのオブジェクトだけでなく、２つの前のスナップショット型も含んでいる。ソースオブジェクトがスナップショットバージョンのオブジェクトと相当異ならない限り、及びそうなるまでは、オブジェクトは、多くのデータ及びメタデータを共有すべきであり、よってスナップショットオブジェクトを維持するのに、多くの記憶スペースを消費すべきではない。必要であれば、あるいは望ましい場合は、スナップショットオブジェクトは、例えばデクローニング作業によって排除される場合もあり、この作業は、基本的にオブジェクト２８０２’が元の（すなわちクローンされていない）オブジェクトとして現れるように再構築し、ＤＳＳオブジェクトを排除し、オブジェクト２８０２’と共有されないＤＳＳオブジェクトからのデータ及びメタデータブロックを解放する。このような機能の一部または全ては、「バックグラウンド」タスクとして行なうことができる。
【０１７２】
ステップＡ４ａ及びＡ４ｂを含むステップＡ１からＡ７を参照して上記の論理の流れを利用して、本発明の例示の一実施形態において種々のオブジェクトがいかにして形成され、結合されるかを実証している。履行上は任意選択のステップＡ４ａ及びＡ４ｂは仮想ステップであってよく、すなわち共通の論理を使用して、最初のクローニングとクローンのクローニングの両方を行なうことができる。例えば、各々のルートオーノードは基本的に、階層的により高いルートオーノードを参照する「アップポインタ」を含む。当初はソースオブジェクトにおけるアップポインタはヌルであるが、その理由はソースオブジェクトが、階層的にこれより高いＤＳＳオブジェクトを参照しないためである。ソースオブジェクトがクローンされる際、この共通の論理が、このアップポインタを、ソースオブジェクトのルートオーノードから新たに作成されたＤＳＳオブジェクト（すなわち第１のＤＳＳオブジェクト）にコピーすることができ、その後ソースオブジェクトのルートオーノードにおけるアップポインタをＤＳＳオブジェクトを参照するように設定することができ、同様に現行のチェックポイント番号をソースオブジェクトから第１のＤＳＳオブジェクトにコピーし、その後この現行のチェックポイント番号をソースオブジェクトに記録する。結果として生じるアップポインタが図２４に描かれている。ソースオブジェクトはこの時変更される場合がある。変更後のソースオブジェクトがクローンされる際、共通の論理は、このアップポインタを、変更後のソースオブジェクト（これは第１のＤＳＳオブジェクトを参照する）から新たに作成された第２ＤＳＳオブジェクトにコピーし、その後変更後のソースオブジェクトにおけるアップポインタを第２ＤＳＳオブジェクトを参照するように設定することができ、同様にこのチェックポイント番号を変更後のオブジェクトから第２ＤＳＳオブジェクトにコピーし、現行のチェックポイント番号の変更後のオブジェクトに記録することができる。結果として生じるアップポインタが図２８に描かれている。したがってこのような共通のコードは事実上、クローンされていないファイルのクローニングと、クローン後のファイルのクローニングとを区別する必要がなく、このような共通のコードは、任意の数の階層的な結合レベルを形成する。このような共通のコードの特定の利点は、ハードウェアベースのファイルシステムにおけるインプリメンテーションが容易であることである。
【０１７３】
上記に記載した例示の一実施形態において、ＤＳＳオブジェクトは、種々のオブジェクトに関連するファイルハンドルを利用して、ソースオブジェクト及び１つ以上のクローンオブジェクトに結合されており、その逆も同様である。とりわけこのような結合作業によって、ストレージシステム制御装置が、特定のファイルがクローン作成されているかを迅速に認識し、またクローン後のファイルに関連するオブジェクトを突き止めることが可能になる。本発明は、ルートオーノードを結合する目的でのファイルハンドルの利用に限定されるものではないことに留意されたい。むしろ、ファイルハンドルに加えて、あるいはその代わりに、例えばオブジェクト番号などの他の情報が使用される可能性がある。
【０１７４】
例示の一実施形態では、クローン後のファイルに属するサイズは、このクローンが作成されたソースファイルのサイズであることに留意されたい。よって例えば１ギガバイトのファイルをクローニングすると、このクローン後のファイルに関連する割り当て量に１ギガバイトが課されることに留意されたい。割り当て量は、クローンファイル同士のいかなるブロック共有も考慮しない。
【０１７５】
性能の点において、クローンオブジェクトに対する読み取り及び書き込み作業は、通常の非クローンファイルの読み取り及び書き込み作業と一致すべきである。非クローンファイルに関して、ハードウェアベースのファイルシステムは、クローン後のファイルに対して自動で問い合わせし、自動で応答するＮＦＳ／ＣＩＦＳ動作が可能である。クローン後のクライアント側の削除は（例えば「ｒｍ」コマンドを使用する）、即座に完了させることができ、実際のファイル及びＤＳＳオブジェクトの排除は、バックグウンドにおいて行なわれる。
【０１７６】
クローンオブジェクトは、異なるユーザ及び集団によって「所有される」場合があり、ソースオブジェクト及び他のクローンと異なるディレクトリツリーに位置付けられる場合もあることを留意されたい。
【０１７７】
上記に記載したファイルクローニング構造は、ファイルをファイルシステム内で管理する目的で使用されており、ファイルシステムの外からこのファイルにアクセスする方法には影響しないことに留意されたい。非クローンファイルに関して、クローン後のファイル（例えばＨＳＲ／ＮＤＭＰ）の転送は、ファイルの中身全体を転送するため、移動先では「膨れた」ファイルになる。
【０１７８】
上記に記載したクローニング論理は好ましくは、本発明の例示の一実施形態において、ハードウェアベースのファイルシステムの一部として大部分がハードウェアに実装されることに留意されたい。
【０１７９】
クローン後のオブジェクトのデクローニング
【０１８０】
上記で考察したように、例示の一実施形態において、特定のソースオブジェクトに関連するＤＳＳオブジェクトは、このソースオブジェクト及び全てのクローンが削除されるまでファイルシステム内に残ったままである。ソースオブジェクトがスナップショットバージョンのオブジェクトと相当異ならない限り、あるいはそうなるまで、オブジェクトは、多くのデータ及びメタデータブロックを共有すべきであるため、スナップショットオブジェクトを維持するのに多くの記憶スペースを消費すべきではない。必要であれば、あるいは望ましい場合は、スナップショットオブジェクトは、例えばデクローニング作業によって排除される場合もあり、この作業は、基本的にオブジェクト２８０２’が元の（すなわちクローンされていない）オブジェクトとして現れるように再構築し、ＤＳＳオブジェクトを排除し、オブジェクトと共有されないＤＳＳオブジェクトからのデータ及びメタデータブロックを解放する。このような機能の一部または全ては、「バックグラウンド」タスクとして行なうことができる。
【０１８１】
例示の一実施形態において、このような「デクローニング」は、以下のように行なわれる。ＤＳＳオブジェクトの参照カウントが１になり（図２９でのように）、残っている参照がクローンである（別のＤＳＳオブジェクトではない）場合、このクローンは、ＤＳＳオブジェクトから「デクローン」することができ、ＤＳＳオブジェクトは削除することができる。
【０１８２】
例示の一実施形態においてこのような「デクローニング」は、ユーザデータブロックの所有権をＤＳＳからその最後に残ったライブファイル可変クローンに移すことによって行なわれる。この点に関して、オブジェクト（ＤＳＳまたは可変クローン）は、ブロックポインタのチェックポイント番号がこのオブジェクトがクローン後に入るチェックポイント番号より大きいか、あるいはそれと等しい場合、独自のブロックを所有すると考えられる（この場合の所有権は、解放するための任務を意味する）。共有されるユーザデータブロックの所有権は、以下によりライブ−ファイルに移すことができる。
１．ライブ−ファイルのブロックポインタのチェックポイント番号を作成する。
ａ．このライブ−ファイルがクローン後に入るチェックポイント番号より大きいか、またはこれと等しい。
ｂ．ファイルシステムの現行のＣＰ番号より小さい（例えば、ブロックが現行のチェックポイントにおいて実質的に変更された場合、ブロックのクラッシュに対する堅牢性を確実に保つため）。
２．ＤＳＳのブロックポインタを少なくする。
【０１８３】
例示の一実施形態において、ステップ１での状況に合わせるために、ライブ−ファイルがクローン後に入るチェックポイント番号が使用される。チェックポイントが、いずれかのブロックポインタを変える前に発行されることデクローン後のファイルが入るチェックポイント番号が確実にファイルシステムの現行のＣＰ番号より小さくなるようにする。
【０１８４】
例示の一実施形態において、ＤＳＳに対する更新は、それが所有する（及びステップ１より前には、ライブ−ファイルと共有していた可能性がある）オーノードの一部を解放する可能性があるため、このような２つのステップの順番が重要である。
【０１８５】
図３０（サブパート３０Ａから３０Ｃを有する）を使用して、本発明の例示の一実施形態によるファイルデクローニングの種々の態様を実証する。
【０１８６】
図３０Ａは、各々のオブジェクトのルートオーノードにおける最初の３つのブロックポインタを描いている、特定の組織系統のオブジェクトを概略的に示している。
【０１８７】
具体的には、第１のスナップショットオブジェクトは、クローン後に入るチェックポイント番号１０を有する。そのブロックポインタは、ブロック１−３に記憶されたデータをそれぞれ指している。
【０１８８】
第２のスナップショットオブジェクトは、クローン後に入るチェックポイント番号２０を有する。それは(依然として）、その第１ブロックを第１のスナップショットオブジェクトと共有している。その第２及び第３ブロックは異なっており、そのため第２及び第３のブロックポインタは、ブロック４及び５に記憶されたデータをそれぞれ指している。
【０１８９】
ライブ−ファイルオブジェクトは、クローン後に入るチェックポイント番号３０を有する。それはその第１ブロックを、第１のスナップショット及び第２スナップショットオブジェクトと共有しており、その第２ブロックを第２スナップショットオブジェクトと共有している。その第３ブロックは異なっており、そのためその第３ブロックポインタは、ブロック６に記憶されたデータを指している。
【０１９０】
第２スナップショットオブジェクト（すなわち親ＤＳＳオブジェクト）の参照カウントが１に下がった場合、このときそれが所有し、かつライブ−ファイルオブジェクトと共有するユーザデータブロックの所有権が、対応するブロックポインタを自動的に変えることによってライブ−ファイルオブジェクトに移すことができる。具体的には、ＤＤＳオブジェクトに所有され、ライブ−ファイルオブジェクトと共有される各々のデータブロックに関して、ＤＤＳオブジェクトにおける対応するブロックポインタが「少なく」され（これは以下でもっと十分に考察するように、ブロックポインタのチェックポイント番号を更新する）、ライブファイルオブジェクトにおける対応するブロックポインタに関連するチェックポイント番号が、ライブ−ファイルオブジェクトがクローン後に入るチェックポイント番号に更新される。図３０Ｂは、第２スナップショットオブジェクト（すなわちＤＤＳオブジェクト）からライブ−ファイルオブジェクトへのブロック４の所有権の移動を概略的に描いている。具体的には、ブロック４に対する第２スナップショットのポインタが「少なく」され、ブロック４に対するライブ−ファイルのポインタのチェックポイント番号が、ライブ−ファイルオブジェクトがクローン後に入るチェックポイント番号に更新される。
【０１９１】
このような変換は、変更後のオーノードを保存するための以下の通常のルールに従って行なわれる。具体的にはブロックポインタが更新される毎に、そのブロックポインタに関連するチェックポイント番号が、現行のチェックポイント番号に更新される。ブロックポインタは変更されているため、中にあるオーノードは新たなスペースに書き込まれる。そのオーノードが直接または間接オーノードである場合、このとき親オーノードにおけるそのオーノードに対するブロックポインタも更新されることで、親オーノードが変更され、新たなスペースに書き込まれるなどされ、最終的にはルートオーノードが処理される。所有権移動プロセスの終わりには、ライブ−ファイルオブジェクトと、ＤＳＳオブジェクトはもはやいかなるオーノードも共有しない。
【０１９２】
よって例示の一実施形態において、共有されるブロックの所有権をＤＳＳオブジェクトからライブ−ファイルオブジェクトに移すために、ライブ−ファイルオブジェクトが詳しく点検され、各々の領域に関してＤＳＳオブジェクトによって共有され所有されることが分かった領域に関して、ライブ−ファイルオブジェクトにおける関連するブロックポインタに「作用し」（これは影響を受けたブロックポインタのチェックポイントを更新するが、それは、対応するブロックが書き込まれるが、いかなるデータも実際には書き込まれていない場合にチェックポイント番号を更新するのと同様であり、その結果ライブファイルオブジェクトが今度はこれらのブロックを所有する）、ＤＤＳオブジェクトにおける関連するブロックポインタが少なくされ（これにより、影響を受けたブロックポインタが何も指さないようにし、またチェックポイント番号を更新し、事実上ＤＳＳオブジェクトに「ホール」を形成し、その結果ＤＳＳオブジェクトが最終的に削除されるときは、ライブ−ファイルオブジェクトに移されたユーザデータブロックをもはや指してはいない）。これ以前はＤＳＳオブジェクトによって所有されていた全ての共有されるユーザデータブロックに関するブロックポインタが、このようにして変換されると、ＤＳＳオブジェクトを安全に削除することができる。
【０１９３】
再び図３０Ｂを参照すると、第２スナップショットオブジェクトの削除が始まる前に、ライブ−ファイルオブジェクトが第２スナップショットオブジェクトの参照リストから排除され、第１のスナップショットオブジェクトの参照リストに加えられ、これにより第１のスナップショットオブジェクトをライブ−ファイルの親ＤＳＳにする。第１のスナップショットオブジェクトに関する参照カウントが１に達した場合（すなわちライブ−ファイルオブジェクトが第１のスナップショットオブジェクトの唯一の子供である）、このとき第１のスナップショットオブジェクトを、上記で考察したようにデクローンすることができる。例えば図３０Ｃに概略的に描かれるように、ブロック１の所有権が、第１のスナップショットオブジェクトからライブ−ファイルオブジェクトに移される。第１のスナップショットオブジェクトによって所有され、ライブ−ファイルオブジェクトと共有される全てのブロックの所有権が移された後、第１のスナップショットオブジェクトを排除することができる。
【０１９４】
例示の一実施形態において、「デクローニング」プロセスは、限定された数のユーザデータブロックの所有権を、ライブ−ファイルをロックしたまま一度に移すことによって、同時発生的に変化するライブ−ファイルに対処する。またライブ−ファイルがこのプロセスにおいてクローンされる場合、このプロセスは中止される。この「デクローニング」プロセスは場合によって、多くの間接／直接オーノードを「汚す」ことがあるが、ユーザデータブロックを汚すことはない。けれども１つの有益な副産物は、それがライブ−ファイルのこれ以前に共有されていたオーノードを「正しい」オブジェクト番号を有するようにしたままにし、カウントを再利用することである。全てのライブ−ファイルの直前のＤＳＳオブジェクトの全てを削除した後、ライブ−ファイルは、通常の（クローンされていない）ファイルに戻るように変換することができる。
【０１９５】
その他
【０１９６】
用語「サーバ」は、本発明の特定の実施形態で使用される可能性のあるデバイスを記述するのに本明細書で使用することができ、文脈がそれ以外を要求しない限り、本発明を任意の特定のデバイスのタイプに限定するものと解釈すべきではないことに留意されたい。したがってデバイスは、限定せずに、ブリッジ、ルータ、ブリッジ−ルータ（ブルータ）、スイッチ、ノード、サーバ、コンピュータ、付属機器または他のタイプのデバイスを含むことができる。このようなデバイスは典型的には、通信ネットワークによって通信する１つ以上のネットワークインターフェースと、デバイスの機能を果たすようにこれに従って構成されたプロセッサ（例えばメモリ及び他の周辺装置及び／または特定用途のハードウェアを備えたマイクロプロセッサ）を含む。通信ネットワークは一般に、パブリック及び／またはプライベートネットワークを含むことができ、ローカルエリア、ワイドエリア、首都圏エリア、ストレージ及び／または他のタイプのネットワークを含むことができ、限定するものではないが、アナログ技術、デジタル技術、光技術、無線技術（例えばブルートゥース）、ネットワーキング技術及びインターネットワーキング技術を含めた通信技術を利用することができる。
【０１９７】
デバイスは、通信プロトコルと、（例えばこのデバイスによって作成された、伝送された、受信された、記憶された及び／または処理された）メッセージを使用する場合があり、このようなメッセージは、通信ネットワークや通信媒体によって伝えることができる。文脈がそうでないことを要求しない限り、本発明は、任意の特定の通信メッセージタイプ、通信メッセージフォーマットまたは通信プロトコルに限定されるものと解釈すべきではない。よって通信メッセージは一般に、限定ではなく、フレーム、パケット、データグラム、ユーザデータグラム、セルまたは他のタイプの通信メッセージを含むことができる。文脈がそうでないことを要求しない限り、特定の通信プロトコルに対する参照が代表的であり、代替の実施形態は適切であれば、いろいろな種類（例えば、その時々に形成され得るプロトコルの修正形態または拡張形態）のこのような通信プロトコル、あるいは将来知られる、または開発される他のプロトコルを利用することができることを理解されたい。
【０１９８】
また論理の流れは、本発明の様々な態様を実証するために本明細書に記載されてよく、本発明は、任意の特定の論理の流れまたは論理の実施に限定されるものと解釈すべきではないことに留意されたい。記載される論理は、全体の結論を変えずに、あるいはそうでければ本発明の真の範囲から逸脱せずに、様々な論理ブロック（例えばプログラム、モジュール、ファンクションまたはサブルーティン）に分割することができる。多くの場合、論理要素は、様々な順番で追加される、変更される、省略される、実施される、あるいは種々の論理構造を使用して（例えば論理ゲート、ルーピングプリミティブ、条件付きロジック及び他の論理構造）実施することができる。
【０１９９】
本発明は、多くの異なる形態で具現化することができ、これらの形態には、これに限定するものではないが、プロセッサ（例えばマイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサまたは汎用コンピュータ）と共に使用するためのコンピュータプログラム論理、プログラマブルロジックデバイス（例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）または他のＰＬＤ）と共に使用するためのプログラマブル論理、ディスクリート要素、集積回路（例えば特定用途向け集積回路（ＡＳＩＣ））、あるいはその何らかの組み合わせを含めた任意の他の手段が含まれる。記載される機能の一部または全てを履行するコンピュータプログラム論理は典型的には、コンピュータプログラム指示のセットとして履行され、この指示は、コンピュータ実行可能形態に変換され、コンピュータ読取り可能媒体にそのように記憶され、作動システムの制御の元にマイクロプロセッサによって実行される。記載される機能の一部または全てを履行するハードウェアベースの論理は、１つ以上の適切に構成されたＦＰＧＡを使用して履行される場合もある。
【０２００】
先に本明細書において記載された機能の一部または全てを履行するコンピュータプログラム論理は、種々の形態で具現化することができ、これらの形態には、これに限定するものではないがソースコード形態、コンピュータ実行可能形態及び種々の中間形態（例えばアセンブラ、コンパイラ、リンカーまたはロケータによって形成される形態）が含まれる。ソースコードは、種々の作動システムまたは作動環境で使用するための種々のプログラミング言語（例えばオブジェクトコード、アセンブリ言語またはフォートラン、Ｃ、Ｃ++、ジャバ、またはＨＴＭＬなどのハイレベル言語）のいずれかで履行される一連のコンピュータプログラム指示を含むことができる。ソースコードは、種々のデータ構造及び通信メッセージを定義し利用することができる。ソースコードは、コンピュータ実行可能形態（例えばインタープリタを介して）であってよい、あるいはソースコードは、（例えばトランスレータ、アセンブラまたはコンパイラを介して）コンピュータ実行可能形態に変換される場合もある。
【０２０１】
先に本明細書に記載した機能の全てまたは一部を履行するコンピュータプログラム論理は、それぞれ異なるときに１つのプロセッサにおいて実行することができる（例えば同時発生的に）、あるいは同一のまたは異なるときに複数のプロセッサにおいて実行することができ、単独の作動システムプロセス／スレッドの下、あるいは異なる作動システムプロセス／スレッドの下に動作することができる。したがって用語「コンピュータプロセス」は一般に、コンピュータプログラム指示のセットを指しており、これは、異なるコンピュータプロセスが同一のプロセッサにおいて実行されているか、あるいは異なるプロセッサにおいて実行されているか、異なるコンピュータプロセスが、同一の作動システムプロセス／スレッドの下に動作するのか、あるいは異なる作動システムプロセス／スレッドの下に動作するのかには関係ない。
【０２０２】
コンピュータプログラムは、任意の形態（例えばソースコード形態、コンピュータ実行可能形態または中間形態）で、実在する記憶媒体に永久的にあるいは一時的に固定することができ、この記憶媒体は例えば、半導体メモリデバイス（例えばＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＥＰＲＯＭまたはフラッシュプログラマブルＲＡＭ）、磁気メモリデバイス（例えばディスケットまたは固定ディスク）及び光メモリデバイス（例えばＣＤ−ＲＯＭ）、ＰＣカード（例えばＰＣＭＣＩＡカード）または他のメモリデバイスなどである。コンピュータプログラムは、任意の形態で特定の信号内に固定することができ、この信号は、種々の通信技術のいずれかを使用してコンピュータに転送可能であり、この通信技術には、これに限定するものではないがアナログ技術、デジタル技術、光技術、無線技術（例えばブルートゥース）、ネットワーキング技術及びインターネットワーキング技術が含まれる。コンピュータプログラムは、印刷または電子文書化（例えば収縮包装されたソフトウェア）を伴う取り外し可能な記憶媒体として任意の形態で分散される、コンピュータシステムと共に予めロードされる（例えばシステムＲＯＭまたは固定ディスク上に）、あるいはサーバまたは電子掲示板から通信システム（例えばインターネットまたはワールドワイドウェブ）を介して分散されてよい。
【０２０３】
先に本明細書に記載された機能の全てまたは一部を履行するハードウェア論理（プログラム可能論理デバイスと共に使用するためのプログラム可能論理を含めた）は、従来の手動式の方法を利用して設計することができる、あるいは種々のツールを利用して電子式に設計される、捕獲される、シミュレートされる、あるいは文書化されてよく、このツールは、例えば、計算機使用設計（ＣＡＤ）、ハードウェア記述言語（例えばＶＨＤＬまたはＡＨＤＬ）、あるいはＰＬＤプログラミング言語（例えば
ＰＡＬＡＳＭ、ＡＢＥＬまたはＣＵＰＬ）などが含まれる。
【０２０４】
プログラマブル論理は、実在する記憶媒体に永久的にまたは一時的に固定することができ、この記憶媒体は例えば、半導体メモリデバイス（例えばＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＥＰＲＯＭまたはフラッシュプログラマブルＲＡＭ）、磁気メモリデバイス（例えばディスケットまたは固定ディスク）及び光メモリデバイス（例えばＣＤ−ＲＯＭ）または他のメモリデバイスなどである。プログラマブル論理は、特定の信号内に固定することが可能であり、この信号は、種々の通信技術のいずれかを使用してコンピュータに転送可能であり、この通信技術には、これに限定するものではないがアナログ技術、デジタル技術、光技術、無線技術（例えばブルートゥース）、ネットワーキング技術及びインターネットワーキング技術が含まれる。プログラマブル論理は、印刷または電子文書化（例えば収縮包装されたソフトウェア）を伴う取り外し可能記憶媒体として分散される、コンピュータシステムと共に予めロードされる（例えばシステムＲＯＭまたは固定ディスク上に）、あるいはサーバまたは電子掲示板から通信システム（例えばインターネットまたはワールドワイドウェブ）を介して分散されてよい。当然のことながら、本発明の一部の実施形態は、ソフトウェアとハードウェアの両方を組み合わせたものとして実施される場合もある。本発明のさらに他の実施形態は、完全にハードウェアとして、あるいは完全にソフトウェアとして実施される。
【０２０５】
本発明は、本発明の真の範囲から逸脱することなく他の特定の形態で具現化される場合もある。「本発明」に対するいかなる言及も、本発明の例示の実施形態を指すことが意図されており、文脈がそうでないことを要求しない限り本発明の全ての実施形態を指すものと解釈すべきではない。記載される実施形態は全ての点において、限定ではなく例示としてみなすべきである。
【図１】
0005948340.tif 000002
【図２】
0005948340.tif 000003
【図３】
0005948340.tif 000004
【図４】
0005948340.tif 000005
【図５】
0005948340.tif 000006
【図６】
0005948340.tif 000007
【図７】
0005948340.tif 000008
【図８】
0005948340.tif 000009
【図９】
0005948340.tif 000010
【図１０】
0005948340.tif 000011
【図１１】
0005948340.tif 000012
【図１２】
0005948340.tif 000013
【図１３】
0005948340.tif 000014
【図１４】
0005948340.tif 000015
【図１５】
0005948340.tif 000016
【図１６】
0005948340.tif 000017
【図１７】
0005948340.tif 000018
【図１８】
0005948340.tif 000019
【図１９】
0005948340.tif 000020
【図２０】
0005948340.tif 000021
【図２１】
0005948340.tif 000022
【図２２】
0005948340.tif 000023
【図２３】
0005948340.tif 000024
【図２４】
0005948340.tif 000025
【図２５】
0005948340.tif 000026
【図２６】
0005948340.tif 000027
【図２７】
0005948340.tif 000028
【図２８】
0005948340.tif 000029
【図２９】
0005948340.tif 000030
【図３０】
0005948340.tif 000031