(57)【特許請求の範囲】
【請求項１】
ファイルサーバによってファイルストレージシステムにファイルを格納する方法であって、
元のファイルを複数のチャンクに分割し前記複数のチャンクをそれぞれ圧縮することにより、それぞれが圧縮されたチャンクである複数の圧縮チャンクを形成し、
前記複数の圧縮チャンクを含むファイルである圧縮ファイルを形成し、
前記圧縮ファイルを前記ファイルストレージシステムに格納し、
前記元のファイルのファイル部分の更新要求を受信し、
前記元ファイルのファイル部分と前記圧縮ファイル内の圧縮チャンクとのマッピングを表す情報であるマッピングメタデータを用いて、前記更新要求に従う更新対象のファイル部分に関連する圧縮チャンクを識別し、
前記圧縮ファイルから前記識別された圧縮チャンクを検索し、
見つかった圧縮チャンクである元の圧縮チャンクを、前記ファイル部分に関連する元のデータを回復するために解凍し、
回復された前記元のデータを、前記更新要求に従い変更し、
変更された元のデータを含むチャンクを圧縮することにより、変更された圧縮チャンクである変更圧縮チャンクを形成し、
前記変更圧縮チャンクのサイズが前記元の圧縮チャンクのサイズ以下である場合、前記元の圧縮チャンクの場所に前記元の圧縮チャンクの代わりに前記変更圧縮チャンクを前記圧縮ファイルに格納し、一方、前記変更圧縮チャンクのサイズが前記元の圧縮チャンクのサイズより大きい場合、前記変更圧縮チャンクを前記圧縮ファイルの、前記元の圧縮チャンクの存在する場所とは異なる場所に格納する、
方法。
【請求項２】
前記異なる場所とは、前記圧縮ファイルの端である、
請求項１に記載の方法。
【請求項３】
前記異なる場所とは、前記変更圧縮チャンクのサイズ以上であり前記圧縮ファイル内の使用していないスペースである、
請求項１又は２に記載の方法。
【請求項４】
前記圧縮ファイルを形成することは、前記圧縮ファイル内に前記マッピングメタデータを維持することを含む、
請求項１乃至３のうちのいずれか１項に記載の方法。
【請求項５】
前記圧縮ファイル内の使用していないスペースを回復する、
請求項１乃至４のうちのいずれか１項に記載の方法。
【請求項６】
前記圧縮ファイル内の使用していないスペースを回復することは、前記圧縮ファイルを解凍することと、前記圧縮ファイルを再圧縮することとを含む、
請求項５に記載の方法。
【請求項７】
チャンクをその対応する圧縮チャンクにマッピングすることと、前記元のファイルの一定サイズの範囲を、前記圧縮ファイル内の対応する圧縮チャンクにマッピングすることにとのうちの少なくとも１つにより、前記マッピングメタデータを維持する、
請求項１乃至６のうちのいずれか１項に記載の方法。
【請求項８】
前記圧縮ファイルに対する圧縮メタデータを維持し、
前記圧縮メタデータは、前記圧縮ファイルの圧縮タイプと、各圧縮チャンクの圧縮タイプと、各チャンクのサイズと、各圧縮チャンクのサイズと、前記圧縮チャンクが圧縮されたデータと圧縮されていないデータとのいずれを含むか各圧縮チャンクについて示すインジケータとのうちの少なくとも１つを含む、
請求項１乃至７のうちのいずれか１項に記載の方法。
【請求項９】
元のファイルを複数のチャンクに分割し前記複数のチャンクをそれぞれ圧縮することにより、それぞれが圧縮されたチャンクである複数の圧縮チャンクを形成する手段と、
前記複数の圧縮チャンクを含むファイルである圧縮ファイルを形成する手段と、
前記圧縮ファイルをファイルストレージシステムに格納する手段と、
前記元のファイルのファイル部分の更新要求を受信する手段と、
前記元ファイルのファイル部分と前記圧縮ファイル内の圧縮チャンクとのマッピングを表す情報であるマッピングメタデータを用いて、前記更新要求に従う更新対象のファイル部分に関連する圧縮チャンクを識別する手段と、
前記圧縮ファイルから前記識別された圧縮チャンクを検索する手段と、
見つかった圧縮チャンクである元の圧縮チャンクを、前記ファイル部分に関連する元のデータを回復するために解凍する手段と、
回復された前記元のデータを、前記更新要求に従い変更する手段と、
変更された元のデータを含むチャンクを圧縮することにより、変更された圧縮チャンクである変更圧縮チャンクを形成する手段と、
前記変更圧縮チャンクのサイズが前記元の圧縮チャンクのサイズ以下である場合、前記元の圧縮チャンクの場所に前記元の圧縮チャンクの代わりに前記変更圧縮チャンクを前記圧縮ファイルに格納し、一方、前記変更圧縮チャンクのサイズが前記元の圧縮チャンクのサイズより大きい場合、前記変更圧縮チャンクを前記圧縮ファイルの、前記元の圧縮チャンクの存在する場所とは異なる場所に格納する手段と
を有するファイルサーバ。
【請求項１０】
前記異なる場所とは、前記圧縮ファイルの端である、
請求項９に記載のファイルサーバ。
【請求項１１】
前記異なる場所とは、前記変更圧縮チャンクのサイズ以上であり前記圧縮ファイル内の使用していないスペースである、
請求項９又は１０に記載のファイルサーバ。
【請求項１２】
前記圧縮ファイルを形成することは、前記圧縮ファイル内に前記マッピングメタデータを維持することを含む、
請求項９乃至１１のうちのいずれか１項に記載のファイルサーバ。
【請求項１３】
前記圧縮ファイル内の使用していないスペースを回復する手段、
を更に有する請求項９乃至１２のうちのいずれか１項に記載のファイルサーバ。
【請求項１４】
前記圧縮ファイル内の使用していないスペースを回復することは、前記圧縮ファイルを解凍することと、前記圧縮ファイルを再圧縮することとを含む、
請求項１３に記載のファイルサーバ。
【請求項１５】
チャンクをその対応する圧縮チャンクにマッピングすることと、前記元のファイルの一定サイズの範囲を、前記圧縮ファイル内の対応する圧縮チャンクにマッピングすることとのうちの少なくとも１つにより、前記マッピングメタデータを維持する手段、
を更に有する請求項９乃至１４のうちのいずれか１項に記載のファイルサーバ。
【請求項１６】
前記圧縮ファイルに対する圧縮メタデータを維持する手段を更に有し、
前記圧縮メタデータは、前記圧縮ファイルの圧縮タイプと、各圧縮チャンクの圧縮タイプと、各チャンクのサイズと、各圧縮チャンクのサイズと、前記圧縮チャンクが圧縮されたデータと圧縮されていないデータとのいずれを含むか各圧縮チャンクについて示すインジケータとのうちの少なくとも１つを含む、
請求項９乃至１５のうちのいずれか１項に記載のファイルサーバ。
【発明の詳細な説明】
【技術分野】
【０００１】
(関連出願の相互参照）
本発明は、以下の米国特許出願の１つ以上に関係し、そのそれぞれは本明細書に参照により全体が援用されている。
【０００２】
２００１年６月１２日に出願された、「Ａｐｐａｒａｔｕｓ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｈａｒｄｗａｒｅ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｒ  Ａｃｃｅｌｅａｒａｔｉｏｎ  ｏｆ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ  Ｆｕｎｃｔｉｏｎｓ」と題する米国特許出願番号第０９／８７９，７９８号、現在は米国特許番号第６，８２６，６１５号（代理人整理番号第２３３７／１０３号）；
２００４年７月１２日に出願された、「Ａｐｐａｒａｔｕｓ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｈａｒｄｗａｒｅ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｒ  Ａｃｃｅｌｅａｒａｔｉｏｎ  ｏｆ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ  Ｆｕｎｃｔｉｏｎｓ」と題する米国特許出願番号第１０／８８９，１５８号（代理人整理番号第２３３７／１０８号）；
２００２年１１月１日に出願された、「Ａｐｐａｒａｔｕｓ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｈａｒｄｗａｒｅ−Ｂａｓｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍ」と題する、Ｇｅｏｆｆｒｅｙ  Ｓ．  Ｂａｒｒａｌｌほかによる米国特許出願番号第１０／２８６，０１５号（代理人整理番号第２３３７／１０４号）；
２００７年８月２０日に出願された、「Ａｐｐａｒａｔｕｓ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｈａｒｄｗａｒｅ−Ｂａｓｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍ」と題する、Ｇｅｏｆｆｒｅｙ  Ｓ．  Ｂａｒｒａｌｌほかによる米国特許出願番号第１１／８４１，３５３号（代理人整理番号第２３３７／１１７号）。
【０００３】
（発明の分野）
本発明は、ファイル格納システムに関し、特にファイルシステムにおけるファイルの圧縮に関する。
【背景技術】
【０００４】
データ圧縮は、いくつかのファイルを格納するために必要な格納スペースの量を減少するために、ファイル格納システムにおいてしばしば使用される。頻繁にはアクセスされないファイルにとって、データ圧縮は特に有益である。そのような「アクティブでない」ファイルは圧縮され、圧縮されたファイルは、例えば二次格納にアーカイブされ得る。一般に言って、圧縮されたファイルの一部分を読み書きするために、圧縮されたファイル全体が格納から読み出されて解凍され、元のファイルのデータが回復される。そのような解凍は、時間の浪費であり、格納システムの処理負荷を増加させ得る。
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明の実施形態は、ファイルをチャンクに論理的に分割し、ファイルの一部分に対応する圧縮されたチャンクのみを読み出し解凍することにより、その部分を含む要求が満たされるように各チャンクを別個に圧縮する。
【０００６】
本発明の１つの局面によると、ファイル格納システムのファイルサーバによりファイルを格納する方法が提供され、ファイルは論理的にチャンクに分割される。方法は各チャンクを圧縮して対応する圧縮されたチャンクを形成することと、圧縮されたチャンクを含む圧縮されたファイルを形成することと、圧縮されたフィルをファイル格納システムに格納することと、圧縮されたファイルに対するマッピングメタデータを維持することとを含み、マッピングメタデータは元のファイルの部分を圧縮されたファイルにおける対応する圧縮されたチャンクにマッピングする。
【０００７】
圧縮されていないファイルはチャンクに分割され得、また、チャンクは、公称的には固定サイズチャンクであり得る（例えば、既存ファイルの最後のチャンクは、全チャンクのデータの価値よりも少ないことがあり得る）。加えてあるいは代替として、ファイルに対する各書き込み要求は、別個のチャンクとして扱われ得る。マッピングメタデータは、各チャンクをその対応する圧縮されたチャンクにマッピングし、あるいは、ファイルの固定サイズ範囲を圧縮されたファイルにおける対応する圧縮されたチャンクにマッピングする。
【０００８】
マッピングメタデータは、例えば、少なくとも１つのマップを圧縮されたファイル内で維持することにより、圧縮されたファイル内で維持され得る。マッピングメタデータは、圧縮されたファイルのルートノード内で、および／または、圧縮されたファイル内のどこか他に維持され得る。加えてあるいは代替として、各圧縮されたチャンクは、ヘッダを含み得、また、マッピングメタデータがヘッダ内で維持され得る（例えば、圧縮されたファイルにおける逐次的に次の圧縮されたチャンクに対するポインタを各ヘッダ内に含む）。
【０００９】
マッピングメタデータは、加えてあるいは代替として、圧縮されたファイルとは別個のマップファイルにおいて維持され得、その場合、マップファイルへの参照は圧縮されたファイル内で維持され得る(例えば、圧縮されたファイルのルートノード内で）。
【００１０】
圧縮されたファイルに対する圧縮タイプ、圧縮されたファイルの各圧縮されたチャンクに対する圧縮タイプ、各チャンクに対するサイズ、各圧縮されたチャンクに対するサイズ、または、圧縮されたチャンクが圧縮されたデータを含むか、または圧縮されていないデータを含むかを示す、各圧縮されたチャンクに対するインジケータのような圧縮メタデータは、例えば、圧縮されたファイルのルートノード内で、マップ内で、および／またはヘッダ内で、圧縮されたファイルに対して維持され得る。
【００１１】
追加の実施形態において、元のファイルの一部分に関する要求を受信すると、方法は、元のファイルのその部分に関連する少なくとも１つの圧縮されたチャンクをマップ情報を用いて識別することと、圧縮されたファイルからの各識別された圧縮されたチャンクを検索することと、該部分に関連する元のデータを回復するのに十分な、各検索された圧縮されたチャンクを解凍することと、回復された元のデータを用いて要求を満たすこととをさらに含む。
【００１２】
該部分に関連する元のデータを回復するのに十分な、各検索された圧縮されたチャンクを解凍することは、要求を満たすために十分な量の元のデータを回復すると、圧縮されたチャンクの解凍を終結することを含み得る。
【００１３】
方法は、要求を満たすことが変更されたチャンクをもたらす場合、変更されたチャンクを圧縮して変更された圧縮されたチャンクを形成することと、変更された圧縮されたチャンクを圧縮されたファイルの部分として格納することと、マッピングメタデータを更新して変更された圧縮されたチャンクを含むようにすることとをさらに含み得る。変更された圧縮されたチャンクを圧縮されたファイルの部分として格納することは、変更された圧縮されたチャンクのサイズが、圧縮されたファイルから検索された対応する圧縮されたチャンクのサイズより小さいか等しい場合、圧縮されたチャンクの代わりに、変更された圧縮されたチャンクを圧縮されたファイルに挿入することと、および、変更された圧縮されたチャンクが、圧縮されたファイルから検索された対応する圧縮されたチャンクのサイズより大きい場合、変更された圧縮されたチャンクを圧縮されたファイルのどこか他に挿入することとを含み得る。
【００１４】
時間とともに、圧縮されたファイルは使用されていないスペースを含むようになる。この使用されていないスペースは、例えば、圧縮されたファイルを解凍することによって、およびそれを使用されていないスペースなしに再圧縮することによって、時々回復され得る。
【００１５】
本発明の他の局面によると、ファイル格納システムおよび、上記の方法を行うように構成された格納プロセッサを有するファイルサーバが提供される。
【００１６】
本発明の前述の特徴は、添付の図面を参照に、以下の詳細な説明を参照することによってより容易に理解される。
例えば、本発明は以下の項目を提供する。
（項目１）
ファイル格納システムに、ファイルサーバによってファイルを格納する方法であって、該ファイルは複数のチャンクに論理的に分割されており、該方法は、
各チャンクを圧縮することにより、対応する圧縮されたチャンクを形成することと、
該圧縮されたチャンクを含む圧縮されたファイルを形成することと、
該圧縮されたファイルを該ファイル格納システムに格納することと、
該圧縮されたファイルに対するマッピングメタデータを維持することであって、該マッピングメタデータは元のファイルの部分を、該圧縮されたファイル内の対応する圧縮されたチャンクにマッピングする、ことと
を含む、方法。
（項目２）
圧縮されていないファイルを複数のチャンクに分割することをさらに含む、項目１に記載の方法。
（項目３）
上記圧縮されていないファイルを複数のチャンクに分割することは、
該圧縮されていないファイルを公称的に固定サイズの複数のチャンクに分割することを含む、項目２に記載の方法。
（項目４）
上記ファイルに対する書き込み要求を受信することをさらに含み、各書き込み要求は別個のチャンクとして扱われる、項目１に記載の方法。
（項目５）
上記圧縮されたファイルを形成することは、
該圧縮されたファイル内のマッピングメタデータを維持することを含む、項目１に記載の方法。
（項目６）
上記圧縮されたファイル内のマッピングメタデータを維持することは、該圧縮されたファイル内の少なくとも１つのマップを維持することを含む、項目５に記載の方法。
（項目７）
上記圧縮されたファイルは、ルートノードを含み、該圧縮されたファイル内の上記マッピングメタデータを維持することは、該ルートノード内のマッピングメタデータを維持することを含む、項目５に記載の方法。
（項目８）
チャンクを圧縮することにより、対応する圧縮されたチャンクを形成することは、該圧縮されたチャンクに対するヘッダを生成することを含み、上記マッピングメタデータを維持することは、該ヘッダ内のマッピングメタデータを維持することを含む、項目１に記載の方法。
（項目９）
上記ヘッダ内のマッピングメタデータを維持することは、該ヘッダ内に、上記圧縮されたファイル内の逐次的に次に圧縮されるチャンクへのポインタを維持することを含む、項目８に記載の方法。
（項目１０）
上記マッピングメタデータを維持することは、
上記圧縮されたファイルとは別個のマップファイル内にマッピングメタデータを維持することと、
該圧縮されたファイル内に該マップファイルへの参照を維持することと
を含む、項目１に記載の方法。
（項目１１）
上記圧縮されたファイルはルートノードを含み、該圧縮されたファイル内に上記マップファイルへの参照を格納することは、該参照を該ルートノード内に格納することを含む、項目１０に記載の方法。
（項目１２）
マッピングメタデータを維持することは、各チャンクをその対応する圧縮されたチャンクにマッピングすることを含む、項目１に記載の方法。
（項目１３）
マッピングメタデータを維持することは、上記ファイルの一定サイズの範囲を、上記圧縮されたファイル内の対応する圧縮されたチャンクにマッピングすることを含む、項目１に記載の方法。
（項目１４）
上記圧縮されたファイルに対する圧縮メタデータを維持することをさらに含み、該圧縮メタデータは、
該圧縮されたファイルに対する圧縮タイプと、
該圧縮されたファイルの各圧縮されたチャンクに対する圧縮タイプと、
各チャンクに対するサイズと、
各圧縮されたチャンクに対するサイズと、
該圧縮されたチャンクが圧縮されたデータを含むか、または、圧縮されていないデータを含むかを示す、各圧縮されたチャンクに対するインジケータと
のうちの少なくとも１つを含む、項目１に記載の方法。
（項目１５）
上記元のファイルの部分に関する要求を受信すると、
上記マップ情報を用いて、該元のファイルの該部分に関連する、少なくとも１つの圧縮されたチャンクを識別することと、
上記圧縮されたファイルから、各識別された圧縮されたチャンクを検索することと、
各検索された圧縮されたチャンクを、該部分に関連する元のデータを回復するために十分に解凍することと、
該回復された元のデータを用いて、該要求を満たすことと
をさらに含む、項目１に記載の方法。
（項目１６）
各検索された圧縮されたチャンクを、上記部分に関連する元のデータを回復するために十分に解凍することは、上記要求を満たすために十分な量の元のデータを回復すると、圧縮されたチャンクの解凍を終結することを含む、項目１５に記載の方法。
（項目１７）
上記要求を満たすことが、変更されたチャンクをもたらす場合、
該変更されたチャンクを圧縮することにより、変更された圧縮されたチャンクを形成することと、
該変更された圧縮されたチャンクを、上記圧縮されたファイルの一部分として格納することと、
上記マッピングメタデータを更新することにより、該変更された圧縮されたチャンクを含むことと
をさらに含む、項目１５に記載の方法。
（項目１８）
上記変更された圧縮されたチャンクを、上記圧縮されたファイルの一部分として格納することは、
該変更された圧縮されたチャンクのサイズが、該圧縮されたファイルから検索された対応する圧縮されたチャンクのサイズ以下である場合、該圧縮されたチャンクの代わりに、該変更された圧縮されたチャンクを該圧縮されたファイルに挿入することと、
該変更された圧縮されたチャンクのサイズが、該圧縮されたファイルから検索された対応する圧縮されたチャンクのサイズより大きい場合、該変更された圧縮されたチャンクを該圧縮されたファイルの他の場所に挿入することと
を含む、項目１７に記載の方法。
（項目１９）
上記圧縮されたファイル内の使用していないスペースを回復することをさらに含む、項目１８に記載の方法。
（項目２０）
上記圧縮されたファイル内の使用していないスペースを回復することは、
該圧縮されたファイルを解凍することと、
該圧縮されたファイルを再圧縮することと
を含む、項目１９に記載の方法。
（項目２１）
ファイルを格納するためのファイル格納システムであって、該ファイルはチャンクに論理的に分割され、該ファイル格納システムは、
少なくとも１つの格納デバイスと、
該少なくとも１つの格納デバイスと通信するファイルサーバであって、該ファイルサーバは、項目１から２０のいずれかに記載の方法を行うように構成された格納プロセッサを含む、ファイルサーバと
を含む、ファイル格納システム。
（項目２２）
ファイルを格納するためのファイルサーバであって、該ファイルはチャンクに論理的に分割され、該ファイルサーバは、項目１から２０のいずれかに記載の方法を行うように構成された格納プロセッサを含む、ファイルサーバ。
【図面の簡単な説明】
【００１７】
【図１】図１は、本発明の例示的な実施形態による、ネットワーク付属ファイル格納システムの概略的なブロック図である。
【図２】図２は、本発明の例示的な実施形態による、オブジェクトツリー構造体の一般的なフォーマットを示す概略的なブロック図である。
【図３】図３は、本発明の例示的な実施形態による、ファイルを圧縮するための論理流れ図である。
【図４】図４は、本発明の例示的な実施形態による、元のファイル、チャンク、圧縮されたチャンク、圧縮されたファイル、およびマップの間の関係を示す概略図である。
【図５】図５は、本発明の例示的な実施形態による、元のファイルに関する要求を処理するための論理流れ図である。
【図６】図６は、本発明の例示的な実施形態による、特定のチャンク内の１つ以上のバイトの変更を含む要求を処理するための論理流れ図である。
【図７】図７は、本発明の例示的な実施形態による、圧縮されたファイルの変更を示す概略図である。
【図８】図８は、本発明の例示的な実施形態による、新しいデータのファイルへの付加を示す概略図である。
【図９】図９は、本発明の例示的な実施形態による、元のファイルの固定サイズ範囲を圧縮されたチャンクにマッピングするための概略図である。
【図１０】図１０は、本発明の例示的な実施形態による、埋め込まれたマップを備えた圧縮されたファイル１００８の概略図である。
【図１１】図１１は、本発明の例示的な実施形態による、変更された圧縮されたファイル１１０８の概略図である。
【発明を実施するための形態】
【００１８】
この説明および添付の特許請求の範囲に使用される場合、以下の用語は、文脈により別に要求されない限り、示される意味を有する。
【００１９】
「格納デバイス」は、データを格納するために使用されるデバイスまたはシステムである。格納デバイスは、１つ以上の磁気もしくは光磁気もしくは光ディスクドライブ、固体格納デバイス、または磁気テープを含み得る。便宜上、格納デバイスは時として、「ディスク」または「ハードディスク」と称される。データ格納システムは、同じかまたは異なるタイプの格納デバイスを含み得、これら同じかまたは異なるタイプの格納デバイスは、同じかまたは異なる格納容量を有する。
【００２０】
「ＲＡＩＤコントローラ」は、幾つかの格納デバイスの格納容量を組み合わせて仮想的な一個の格納スペースにするデバイスまたはシステムであり、この仮想的な一個の格納スペースは、別に、「システムドライブ」（「ＳＤ」）、「論理ユニット」（「ＬＵ」または「ＬＵＮ」）、または「ボリューム」とも称され得る。通常、ＳＤは、単一の格納デバイスよりも大きく、幾つかの格納デバイスからスペースを引き出し、データの喪失なく特定の数のディスクの故障に耐えることができるように冗長情報を含む。例示的な実施形態において、各ＳＤは、一意識別子と関連し、この一意識別子は、今後「論理ユニット識別子」または「ＬＵＩＤ」と称され、各ＳＤは、所定の最大サイズ、例えば２ＴＢ〜６４ＴＢ以上よりも大きくはない。コマンドがＳＤへ送信されたとき、ＲＡＩＤコントローラは通常、このコマンドを同時にＳＤのすべての格納デバイスに転送する。ＲＡＩＤコントローラは、通常の格納デバイスの主な制限のうちの３つ、すなわち、格納デバイスは通常、格納システムのうちで最も遅いコンポーネントである、格納デバイスは通常、破局故障を被る可能性が最も高い、および格納デバイスは通常、比較的小さな格納容量を有する。
【００２１】
「ＲＡＩＤシステム」は、１つ以上のＲＡＩＤコントローラおよび多数の格納デバイスを含むデバイスまたはシステムである。通常、ＲＡＩＤシステムは、２つのＲＡＩＤコントローラ（１つが故障しても、他方が作動し続けることができるように、また、両方ともが健全である間は、ロードを共有するために）と幾十かの格納デバイスとを含む。例示的な実施形態において、ＲＡＩＤシステムは通常、２と３２との間のＳＤで構成される。ファイルサーバが、データを格納または検索する必要があるとき、ファイルサーバは、ＲＡＩＤシステムのＲＡＩＤコントローラにコマンドを送信し、ＲＡＩＤコントローラは、個々の格納デバイスにコマンドを前方にルーティング（ｒｏｕｔｉｎｇ）すること、必要に応じてデータを格納または検索することを担当する。一部のＲＡＩＤシステムに対して、ＳＤ間でミラー関係が確立されることができ、それによって、１つのＳＤに（「一次ＳＤ」）書き込まれたデータは、ＲＡＩＤシステムによって自動的に別のＳＤ（本明細書においては「二次ＳＤ」または「ミラーＳＤ」と称される）に冗長目的で書き込まれる。二次ＳＤは、一次ＳＤと同じＲＡＩＤシステムによって管理され得るか、または異なるローカルのまたはリモートのＲＡＩＤシステムによって管理され得る。ＳＤを効果的にミラーすることは、ＳＤにわたってＲＡＩＤ１＋０機能性を提供し、それによって、１つのＳＤまたは可能性として一部の状況では複数のＳＤの喪失または破壊からの回復を提供する。
【００２２】
「ファイルシステム」は、ファイル格納システムに格納されたファイルおよびディレクトリ（フォルダ）の構造体である。ファイル格納システム内において、ファイルシステムは通常、多数の仮想的な格納構成を使用して管理され、例示的な実施形態において、ファイルシステムは、範囲、ストライプセット（ｓｔｒｉｐｅｓｅｔ）、スパンと称される仮想的な格納構成の階層を使用して管理される。「範囲」は、それ自身の上の一次ＳＤ、または同一のデータを含むことになっている、従って単一のＳＤと同じ格納容量を提供することになっている一次／二次ＳＤの対から構成される。「ストライプセット」は、１つ以上の範囲から構成される。「スパン」は、１つ以上のストライプセットから構成される。このように、スパンは、究極的に１つ以上のＳＤ（通常４〜５０のＳＤ）から構成される。スパンは、１つ以上のファイルシステムに分割されることができ、各ファイルシステムは、別個の名前および識別子ならびに潜在的に異なる特性（例えば、１つのファイルシステムは、３２ＫＢクラスタでフォーマットされ得、別のファイルシステムは、４ＫＢクラスタでフォーマットされ得、１つのファイルシステムは、ワーム（Ｗｏｒｍ）であり、別のファイルシステムはワームではない、など）を有する。スパンの各ファイルシステムは、別個にフォーマットされ、取り付けられ、および取り付け解除される。ファイルシステムは、任意の順序でおよび任意のときに作成、削除され得る。ファイルシステムは、自動的に拡張するように（または、代替として、自動拡張を防止、制限するように）構成されるか、または手動で拡張されることができる。
【００２３】
一「組」の値は、１つ以上のちを含み得る。
【００２４】
「ファイルサーバ」は、ファイル格納システムにおけるファイルの格納を管理するデバイスである。
【００２５】
本発明の実施形態は、ファイルシステムにおけるファイルの圧縮に対して備える。ファイルは、個別のピース（これ以降、「チャンク（ｃｈｕｎｋ）」と称される）に格納され、各チャンクは別個に圧縮され、それによって、ファイルの一部分を含む要求は、その部分に対応する圧縮されたチャンクのみを読み出し、解凍することによって満足されることができる。このようなファイル圧縮スキームは、ライブファイルシステムにおけるアクティブなファイルを圧縮することに対して特に有用であり得るが、しかし、このようなファイル圧縮スキームはまた、ファイルの格納／アーカイブ収納に対しても一般的に有用であり得る。
【００２６】
本発明の実施形態は、直接のおよびネットワーク付属格納システムを含んで、様々なタイプの格納システムにおいて有用であり得る。図１は、本発明の例示的な実施形態によるネットワーク付属ファイル格納システムの概略的なブロック図である。とりわけ、ファイル格納システムは、多数のファイルサーバを含み（単一のファイルサーバ１０２が、簡潔さと便宜のために示される）、これらのファイルサーバは、通信ネットワーク１０４、例えばインターネットプロトコルネットワーク（例えばインターネット）を介して様々なクライアントデバイス１０６１〜１０６Ｍと通信し、また、格納ネットワーク１１０、例えばファイバチャネルネットワークを介して様々なＲＡＩＤシステム１０８１〜１０８Ｎとも通信する。クライアントデバイス１０６１〜１０６Ｍおよびファイルサーバ１０２が、１つ以上のネットワークファイルプロトコル、例えばＣＩＦＳおよび／またはＮＦＳを使用して通信する。ファイルサーバ１０２およびＲＡＩＤシステム１０８１〜１０８Ｎは、格納プロトコル、例えばＳＣＳＩを使用して通信する。ファイル格納システムは、様々な構成で相互に接続する複数のファイルサーバと複数のＲＡＩＤシステムとを含み得、それら様々な構成の中には、任意のファイルサーバが、冗長ファイバチャネルネットワークおよび切り換えられたファイバチャネルネットワークを介して任意のＲＡＩＤシステムと通信することができる完全なメッシュ構造が含まれることに留意されるべきである。
【００２７】
ファイルサーバ１０２は、１つ以上のファイルシステムを管理するための格納プロセッサを含む。ファイルサーバ１０２は、ファイルシステムの部分、例えば指定された名前の下でのツリーまたはサブツリーへのクライアントアクセスを許すように構成されることができる。ＣＩＦＳ用語においては、そのようなアクセスは、「シェア（ｓｈａｒｅ）」と称され得、一方、ＮＦＳ用語においては、そのようなアクセスは、「エクスポート」と称され得る。内部的に、ファイルサーバ１０２は、例えば、参考として上に援用された米国特許出願第０９／８７９，７９８号および米国特許出願第１０／８８９，１５８号に記載されるような様々なハードウェア実装および／またはハードウェア加速サブシステムを含み得、かつ、例えば、上に参考として援用された米国特許出願第１０／２８６，０１５号および米国特許出願第１１／８４１，３５３号に記載されるような複数のリンクされたサブモジュールを含むハードウェアベースのファイルシステムを含み得る。
【００２８】
各ＲＡＩＤシステム１０８は通常、少なくとも１つのＲＡＩＤコントローラ（および冗長のために普通２つのＲＡＩＤコントローラ）ならびに該ＲＡＩＤコントローラによって管理される多数の物理的格納デバイス（例えばディスク）を含む。ＲＡＩＤシステム１０８は、その格納リソースを統合して多数のＳＤとする。例えば、各ＲＡＩＤシステム１０８は、２と３２との間の数のＳＤによって構成され得る。各ＳＤは、所定の最大サイズ（例えば、２ＴＢ〜６４ＴＢ以上）に制限され得る。幾つかの格納デバイスを組み合わせてＳＤにすることにより、多数の利益が提供され、それら多数の利益の中には、増加したスピード（個々の格納デバイスは比較的遅いが、しかし、データは、幾つかの格納デバイスにわたってストライプ状にされ、ボトルネックを広くすることができる）と、増加した容量（個々の格納デバイスは比較的小さいが、しかし、幾つかの格納デバイスは組み合わせられて、より多くの使用可能なスペースを提供することができる）と、抽象化（使用されるスペースの量は、単一の格納デバイスのサイズよりも大きいかまたは小さくあることができる）と、弾力性（パリティまたは冗長情報が、各格納デバイスに格納されることができ、それによってＳＤは、格納デバイスの喪失に耐えることができる）とが含まる。
【００２９】
ファイルサーバ１０２は、１つ以上のＳＤを使用するように構成され、これら１つ以上のＳＤは、単一のＲＡＩＤシステムまたは複数のＲＡＩＤシステムからのものであることができる。ファイルサーバ１０２は普通、ＲＡＩＤシステムに応答指令信号を送り、各ＳＤが一次または二次であるかどうかを発見することができる。どのＳＤがファイルサーバ１０２によって使用されているかを制御する方法は、本明細書においては、「ライセンシング」と称される。このように、実際には、ファイルサーバ１０２は通常、一部のＳＤに対してライセンシングされ、他に対してはライセンシングされない。
【００３０】
内部的には、ファイルサーバ１０２は、幾つかのＳＤを組み合わせて、本明細書では「スパン」と称されるより大きな格納プールにすることができる。スパンは本質的に、幾つかのＳＤのＲＡＩＤ０アレイである。幾つかのＳＤを組み合わせてスパンにすることにより、複数の物理的ディスクを組み合わせてＳＤにすることによって得られる利益と同様の多数の利益が提供されることができ、それら多数の利益の中には、増加したスピード（複数のＲＡＩＤシステム上において複数のＳＤ間でＩ／Ｏを広げることにより、格納ボトルネックをさらに広くすることができる）と、増加した格納容量（スパンは単一のＳＤよりも大きくあることができ、単一のＳＤは、２テラバイトに制限され得る）と、さらなる抽象化とが含まれ、このさらなる抽象化は、より柔軟な格納スペース割り当てを可能にする。
【００３１】
ファイルサーバ１０２は、ファイルシステムの中に様々なタイプのオブジェクトを格納する。オブジェクトは、一般的に、システムオブジェクトおよびファイルオブジェクトとして分類され得る。ファイルオブジェクトは、ユーザデータおよび関連する属性の格納に対して作成され、かつ、例えばワードプロセッサまたはスプレッドシートファイルのようなものを含み得る。システムオブジェクトは、情報を管理するためのファイル格納システムによって作成される。
【００３２】
一般的に言って、システムオブジェクトの各々とファイルオブジェクトの各々とを含むファイルシステムにおける各オブジェクトは、別個のツリー構造体を使用して実装され、この別個のツリー構造は、別個のオブジェクトルート（ｒｏｏｔ）ノードを含み、かつ、多数の間接的なノード、直接的なノード、および格納ブロックを選択的に含む。図２は、本発明の例示的な実施形態によるオブジェクトツリー構造体の一般的なフォーマットを示す概略的なブロック図である。ルート（「Ｒ」）ノード２０２は、様々な間接的な（「Ｉ」）ノード２０４を指し得、様々な間接的な（「Ｉ」）ノード２０４の各々は、多数の直接的な（「Ｄ」）ノード２０６を指し得、多数の直接的な（「Ｄ」）ノード２０６の各々は、多数の格納ブロック（「Ｂ」）２０８を指し得る。実際には、オブジェクトツリー構造体は、例えば、オブジェクトのサイズに依存して幅広く変化することができる。また、特定のオブジェクトのツリー構造体は、情報がオブジェクトに付加され、かつ削除されるにつれて、時間と共に変化することができる。例えば、ノードは、より多くの格納スペースがオブジェクトに対して使用されるにつれて、ツリー構造体に動的に付加され得、そして、間接性の様々なレベルが必要に応じて使用され得る（例えば、間接的なノードが直接的なノードまたは他の間接的なノードを指すことができる）。データがオブジェクトおよびデータブロックから削除され、直接的および間接的なノードがもはや必要でなくなると、それらは、空きスペースに戻される。
【００３３】
一般的に言って、ファイルを圧縮された形に格納するためには、ファイルは、チャンクに論理的に区分され、各チャンクは、所定のデータ圧縮スキームを使用して圧縮され、対応する圧縮されたチャンクを形成し、圧縮されたチャンクは、共にパッキングされて圧縮されたファイルを形成する。ファイルは、例えば、既存のファイルを主として固定サイズのチャンク（ファイルの最後のチャンクは、ファイルサイズが整数の複数のチャンクサイズではない場合、より小さくなり得る）に論理的に分割することによって明確に、および／または、例えば、（様々なサイズであり得る）書き込み要求を別個のチャンクとして取り扱うことによって暗黙に、論理的にチャンクに区分され得る。特定の実施形態において、圧縮されたファイルが元のファイルよりも小さい場合、圧縮されたファイルは格納システムに格納され、そうでない場合は（すなわち、圧縮されたファイルが元のファイルよりも大きい場合であるが、これは一般的に、データのタイプおよび他の要因に依存して、大抵のデータ圧縮に関してあり得ることである）、元のファイルが圧縮されたファイルの代わりに圧縮されずに格納システムに格納される。他の実施形態において、ファイルの特定のクラスは、圧縮されたファイルが元のファイルよりも大きいか小さいかにかかわりなく圧縮されて、圧縮された形で格納され得る。各ファイルは、ファイルが圧縮されているか、または圧縮されていないかを示すために、インジケータを（例えば、ファイルルートノードの中に）含み得る。
【００３４】
上に論議されたように、このような圧縮されたファイルに対しては、ファイルの一部分を含む要求は、その部分に対応する圧縮されたチャンクのみを読み出し、解凍することによって満足されることができる。このような機能性をサポートするために、元のファイルの各チャンクを圧縮されたファイル内のその対応する圧縮されたチャンクに直接的にまたは間接的にマッピングする情報（これ以降、「マッピングメタデータ」と称される）は、圧縮されたファイルに対して維持される。特定の実施形態において、マッピングメタデータは、表または他の適切な論理構成（これ以降、「マップ」と称される）を使用して維持される。そのようなマップは、例えば、圧縮されたファイルそれ自体の内に（例えば、ファイルルートノード内におよび／またはデータブロック内に）、または別個のファイルとして格納され得る。さらに、または代替として、マッピングメタデータは、圧縮されたチャンクに含まれるヘッダ内に維持され得る。このような各ヘッダは、圧縮されたファイル内の「次の」圧縮されたチャンクのヘッダへのリンクを含み得（すなわち、圧縮されたチャンクがリンクされたリストを形成する）、それによって特定の圧縮されたチャンクは、圧縮されたチャンクヘッダ内に含まれたリンクに基づいてリンクされたリストを横断することによって見つけ出されることができる。
【００３５】
一部の実施形態において、マップは、全ての圧縮されたファイルに対して維持され得る。代替として、ヘッダは、マップと共に、またはマップなしで使用され得る。マップなしでヘッダを使用することは、一般的に、小さくて、かつ／または一般的に順次に読み出され、そして書き込まれるファイルに対して受容可能である。しかしながら、おおきなファイルおよび／または一般的にランダムにアクセスされるファイルに対しては、リンクされたリストを横断して、特定のチャンクを発見すると、費用が高くなり得る。なぜならば、読み出される各ヘッダは、別個のディスクアクセス（およびディスク応答時間）を要求し得る（そして多分要求すると思われる）からである。この場合は、別個のマップが一般的に好まれる。なぜならば、このマップは、多くの圧縮されたチャンクに対するマッピング情報が、一度にロードされることを可能にするからである。マップは、表構造体として実施され得る一方、別の可能性は、マップが、迅速かつ効率的に元のファイルオフセットをチャンク位置にマッピングするためのより複雑なデータ構造体を含むことである（これによって、さらなるデータ構造を維持することにおけるさらなる複雑さという代価で、必要なチャンクを発見することがより容易となる）。
【００３６】
他の情報（これ以降、「圧縮メタデータ」と称される）は通常、各圧縮されたチャンクに対して格納され、そして、例えば元のチャンクのサイズ、圧縮されたチャンクのサイズ、圧縮されたチャンクが圧縮されたデータまたはもとのデータを含むかどうかを示す「フラグ」、および／または圧縮タイプインジケータのようなものを含み得る。このような圧縮メタデータは、例えば、マップにまたは各圧縮されたチャンクに含まれたヘッダに格納され得る。
【００３７】
通常の実施形態においては、単一のデータ圧縮スキームが全てのファイルに対して使用されるが、しかし、代替の実施形態においては、様々なデータ圧縮スキームが、（例えば、ファイル内容、ファイル延長、または他のファイル属性に基づいて）様々なタイプのファイルに対しておよび／または（例えば、チャンク内容または他のチャンク属性に基づいて）ファイル内の様々なチャンクに対して使用され得る。複数のデータ圧縮スキームがファイルレベルにおいて適用される場合、圧縮タイプインジケータは通常、各圧縮されたファイルに対して（例えば、ファイルルートノードに）格納される。複数のデータ圧縮スキームがチャンクレベルにおいて適用される場合、圧縮タイプインジケータは通常、各圧縮されたチャンクに対して（例えば、下に論議されるように、マップテーブルにまたは各圧縮されたチャンクに含まれたヘッダに）格納される。簡潔さのために、下に説明される例示的な実施形態は、単一のデータ圧縮スキームが、全てのファイルおよびチャンクに対して使用され、それによって、ファイルまたはチャンクに対する圧縮タイプインジケータを格納する必要がないことを仮定する。
【００３８】
上に論議されたように、各チャンクは、データ圧縮スキームを使用して圧縮される。データ圧縮スキームは通常、例えば、「圧縮された」データが元のデータよりも大きいとき元のデータに復帰することによってデータ拡張を避けるためのメカニズムを含む。このように、本発明の通常の実施形態においては、圧縮されたチャンクは、データ圧縮スキームに従って、圧縮された（符号化された）データまたは元の（符号化されていない）データを含み得、したがって、圧縮されたファイルは、圧縮されたデータを含む幾つかの圧縮されたチャンクと元のデータを含む幾つかの圧縮されたチャンクとを含み得る。したがって、この点において、圧縮されたチャンクは、必ずしも元のチャンクよりも小さくはなく、例えば、データ圧縮スキームが拡張回避メカニズムを含まない場合、または、各圧縮されたチャンクが、下に論議されるようにヘッダを含む場合（この場合、元のデータを含む圧縮されたチャンクでさえも、元のチャンクよりも大きくあり得る）、元のチャンクよりも大きくあり得る。
【００３９】
図３は、本発明の例示的な実施形態にしたがって既存のファイルを圧縮するための論理流れ図である。ブロック３０２において、元のファイルは、論理的にチャンクに分割される。ブロック３０４において、各チャンクは、所定のデータ圧縮スキームを使用して圧縮され、対応する圧縮されたチャンクを形成する。ブロック３０６において、圧縮されたチャンクは、パッキングされて圧縮されたファイルを形成する。圧縮されたファイルが元のファイルよりも小さい場合（ブロック３０８における、はい）、ブロック３１０において、マップが圧縮されたファイルに対して準備され、そして、ブロック３１２において、圧縮されたファイルは格納される。そうではない場合（ブロック３０８における、いいえ）、ブロック３１４において、元のファイルが格納される。
【００４０】
図４は、本は発明の例示的な実施形態にしたがって、元のファイル、チャンク、圧縮されたチャンク、圧縮されたファイル、およびマップの間の関係を示す概略図である。上に論議されたように、元のファイル４０２は論理的にチャンク４０４に分割される。この例において、チャンク４０４は、各々Ｘバイト（例えば、４Ｋまたは６４Ｋバイト）の固定サイズのチャンクであるが、しかし、ファイルの最後のチャンクは、Ｘバイトよりも少ないバイトを含み得ることに留意されるべきである。チャンク４０４は個々に圧縮されて圧縮されたチャンク４０６となり、圧縮されたチャンク４０６は次に、共にパッキングされて、圧縮されたファイル４０８を形成する。マップ４１０は、元のファイルからの各チャンク４０４を（例えば、「範囲」４１１は、元のファイルのスタートに対するチャンクと関連するファイルオフセットを示す）圧縮されたファイル４０８内の対応する圧縮されたチャンクに（例えば、「ポインタ」４１３は、圧縮されたファイルのスタートから圧縮されたチャンクのスタートへの相対的なオフセットを示す）マッピングする。マップ４１０はまた、各圧縮されたチャンクに対する圧縮メタデータ４１２、例えば、元のチャンクのサイズ、圧縮されたチャンクのサイズ、および圧縮されたチャンクが圧縮されたデータまたは元のデータを含むかどうかを示す「フラグ」を含み得る。
【００４１】
図５は、本発明の例示的な実施形態に従って、元のファイルに関する要求を処理するための論理流れ図である。ブロック５０２において、元のファイルの一部分と関連する要求を受取ると、ブロック５０４において、マップが使用されてファイルのその部分と関連する圧縮されたチャンクを（例えば、元のファイルのスタートに対する部分と関連するオフセットに基づいて）識別する。このような各圧縮されたチャンクは、ブロック５０６において、格納から検索され、そして、ブロック５０８において、その部分と関連する元のファイルデータを回復するために十分に解凍される。詳細には、（圧縮されたチャンクに対する圧縮メタデータによって示されるとおり）圧縮されたチャンクが圧縮されたデータを含む場合、圧縮されたデータは、その部分と関連するもとのデータを少なくとも回復するために十分に解凍される（すなわち、十分な量の元のデータが圧縮されたチャンクから回復されたあと、要求は、圧縮されたチャンクの残りを解凍することなく満足され得るが、しかし、例えば、下に論議されるように、解凍されたデータをキャッシュに入れるために圧縮されたチャンク全体を解凍することが望ましくあり得る）。他の場合では、圧縮されたチャンクは既に、チャンクに対するもとのデータを含む。いずれの場合においても、解凍されたデータは、ブロック５１０において、キャッシュされ、それによって、後の要求に対して利用可能である。要求は次に、ブロック５１２において、回復された元のファイルデータを使用して満足される。
【００４２】
１つの例に対して、ファイルオフセット２Ｘと（３Ｘ−１）との間（ただし２Ｘと（３Ｘ−１）とを除く）（すなわち、元のファイルデータを完全に元のチャンクＣ内に包含する）の図３の元のファイルの一部分に対する要求が受取られると仮定されたい。マップテーブルに基づき、圧縮されたチャンクＣ’が、圧縮されたファイルから検索され、そして解凍されて元のデータをチャンクＣから回復する。詳細には、メタデータが、圧縮されたチャンクＣ’が圧縮されたデータを含むと示す場合、圧縮されたチャンクは、少なくともその部分を回復するために十分なだけ解凍される。他の場合では、圧縮されたチャンクは既にチャンクに対する元のデータを含み、したがって、解凍は実行されない。要求は次に、回復された部分を使用して満足される。
【００４３】
別の例に対して、ファイルオフセット（２Ｘ＋ｙ）と（３Ｘ＋ｙ）との間（ただし、（２Ｘ＋ｙ）と（３Ｘ＋ｙ）とを含める）の図３の元のファイルの一部分に対する要求が受取られると仮定されたい。ここで、０＜ｙ＜Ｘである（すなわち、チャンクＣおよびＤの元のファイルデータスパン部分を包含する）。マップテーブルに基づいて、圧縮されたチャンクＣ’およびＤ’は、圧縮されたファイルから検索される。圧縮されたチャンクＣ’は解凍されて、範囲（２Ｘ＋ｙ）〜（３Ｘ−１）内（ただし、（２Ｘ＋ｙ）と（３Ｘ−１）とを含める）の元のファイルデータを回復し（これは通常、圧縮されたチャンク全体の解凍を含む）、そして圧縮されたチャンクＤ’の少なくとも十分なだけ（および、普通、圧縮されたチャンク全体）が解凍され、範囲３Ｘ〜（３Ｘ＋ｙ）内（ただし、３Ｘと（３Ｘ＋ｙ）とを含める）の元のファイルデータを回復する。要求は次に、回復された部分を使用して満足される。
【００４４】
図６は、本発明の例示的な実施形態に従って、特定のチャンク内で１つ以上のバイトの変更を含む要求を処理するための論理流れ図である。ブロック６０２において、圧縮されたファイルから対応する圧縮されたチャンクを検索、解凍したあと、ブロック６０４において、チャンクのバイトは変更され、ブロック６０６において、変更されたチャンクは、圧縮されて、変更された圧縮されたチャンクを形成する。変更により、変更された圧縮されたチャンクのサイズは、圧縮されたファイルから検索された圧縮されたチャンクのサイズよりも大きいか、または小さくあり得る。変更された圧縮されたチャンクのサイズが、圧縮されたファイルから検索された圧縮されたチャンクのサイズより小さいか、または等しい場合（ブロック６０８において、はい）、変更された圧縮されたチャンクは、ブロック６１０において、圧縮されたチャンクの代わりに圧縮されたファイルの中に挿入されることができる。一方、変更された圧縮されたチャンクのサイズが、圧縮されたファイルから検索された圧縮されたチャンクのサイズよりも大きく（ブロック６０８において、いいえ）、したがって、変更された圧縮されたチャンクは、圧縮されたチャンクによって締められたスペース内に嵌らない場合、変更された圧縮されたチャンクは、ブロック６１２において、圧縮されたファイル内の別の場所、例えば、圧縮されたファイルの端に置かれる。マップおよび圧縮メタデータは、ブロック６１４において、必要に応じて更新され、圧縮されたファイルへの変化を反映する。例えば、マップは更新されて、圧縮されたファイル内での、変更された圧縮されたチャンクの位置（例えば、圧縮されたファイルの端）を反映し、そして、圧縮メタデータは更新されて、変更された圧縮されたチャンクのサイズを反映し得る。
【００４５】
例えば、ここで、要求は、チャンクＣ内でバイトを変更することを含むと仮定されたい。図７に示されるように、マップテーブルに基づいて、圧縮されたチャンクＣ’は、圧縮されたファイル４０８から検索され、そして解凍されて、チャンクＣに対する元のデータ７０４を回復する。次に、チャンクＣにおけるバイトは変更されて、変更されたチャンク
【００４６】
【数１】
0005295394.tif 000002
を形成する。変更されたチャンク
【００４７】
【数２】
0005295394.tif 000003
は圧縮されて、変更された圧縮されたチャンク
【００４８】
【数３】
0005295394.tif 000004
を形成する。変更された圧縮されたチャンク
【００４９】
【数４】
0005295394.tif 000005
のサイズが、圧縮されたチャンクＣ’のサイズより小さいか、または等しい場合（ブロック７０７における、はい）、変更された圧縮されたチャンク
【００５０】
【数５】
0005295394.tif 000006
は、圧縮されたチャンクＣ’の代わりに圧縮されたファイルの中に挿入されることができ、圧縮されたファイル７０８を生じる（圧縮されたファイル７０８は、ハッチングによって示されるように、変更された圧縮されたチャンク
【００５１】
【数６】
0005295394.tif 000007
の端と圧縮されたチャンクＤ’の始まりとの間に幾らかの使用されないスペースを含み得る）。一方、変更された圧縮されたチャンク
【００５２】
【数７】
0005295394.tif 000008
のサイズが、圧縮されたチャンクＣ’のサイズよりも大きい場合（ブロック７における、いいえ）、変更された圧縮されたチャンク
【００５３】
【数８】
0005295394.tif 000009
は、圧縮されたファイルの端に挿入され、圧縮されたファイル７０９を生じ、そして、マップはこれに応じて更新されて、マップ７１０を生じる。
【００５４】
圧縮されたファイル７０９において、圧縮ブロックＣ’によって既に占められたスペースは使用されないことに留意されるべきである。この使用されないスペースは後に、下に論議されるように、さらなる圧縮されたデータを格納するために使用され得るか、または、例えば、適切なときにファイル全体を解凍することによって回復され得（例えば、システムのロードが低いとき、システムへの衝撃の量を制限するために背景タスクを使用して）、そして、図３を参照して論議されたように、圧縮されたチャンクが順にパッキングされて再圧縮されたファイルになるようにファイルを再圧縮する。
【００５５】
新しいデータが元のファイルの端に（単一の書き込みで、または一連の書き込みで）追加されると、その新しいデータは、しばらくの間、圧縮されたファイルに圧縮されずに格納され得、および／または、圧縮されたファイルへの格納のために適切なとき（例えば、書き込みのたびに、新しいデータが完全なチャンクのサイズに達したときに、もしくはチェックポイントで、または他の適切なときに）に圧縮され得る。新しいデータのサイズが完全なチャンクのサイズよりも小さい場合、新しいデータの圧縮は、圧縮に対して完全なチャンクが利用可能になるまで延期され得るか、または、部分的なチャンクが圧縮されて、圧縮された部分的なチャンクを形成し得、この圧縮された部分的なチャンクは、圧縮されたファイルに格納される。後者の場合、元の部分的なチャンクは、キャッシュに入れられ得、それによって、さらなるデータは、既に格納された圧縮された部分的なチャンクを解凍する必要なく部分的なチャンクに追加されることができる。
【００５６】
さらなる情報が圧縮されたファイルに追加されたとき、さらなる情報は圧縮されたファイルの端に格納され得るか、または、圧縮されたファイル内に十分な量の空きスペースがある場合（例えば、図７を参照して示され、説明されるように、圧縮されたチャンクＣ’が、圧縮されたファイル７０９から除去されたときのように）、空きスペース内に格納され得る。例えば、図８に示されるように、新しいデータＥ８０４が、（単一の書き込みで、または一連の書き込みで）元のファイルの端に追加されるとき、新しいデータＥ８０４は、適切なときに圧縮されて、圧縮されたチャンクＥ’８０６を形成する。圧縮されたチャンクＥ’８０６のサイズが、圧縮されたチャンクＣ’によって空けられたスペースのサイズより小さいか、または等しい場合、圧縮されたチャンクＥ’８０６は、そのスペースに挿入されて、圧縮されたファイル８０８を形成し得、この場合、マップはこれにしたがって更新されて、マップ８１０を生じる。このようにして、圧縮されたファイル８０８は、圧縮されたファイル７０９と同じサイズであるが、しかし、拡大された元のファイルを保持する。
【００５７】
実質的に上述されたように、所与のファイルに対する圧縮は、ファイルが書き込まれながら圧縮されるように、スタートから可能とされ得ることに留意すべきである。ファイルは最初に、「空の」圧縮されたファイルとして、すなわち、圧縮されたチャンクを含まずに空のマップを選択的に有するように作成され得る。いずれの場合においても、データはファイルに書き込まれ、データは通常、１つの書き込みを基礎として圧縮され、対応する圧縮されたチャンクは、上述のように、圧縮されたファイルに追加されるが、しかし、多数の書き込みからのデータが、図８を参照して示され、説明されるように実質的に圧縮され得る。マップおよび／または圧縮されたチャンクヘッダが、これに従って更新される。
【００５８】
一部の実施形態において、マップの各エントリが、元のファイルの固定サイズ範囲（例えば、４Ｋ範囲）を１つ以上の圧縮されたチャンクにマッピングすることが有益であり得る（例えば、マップは、ファイル範囲０〜（４Ｋ−１）に対する第１のポインタ、ファイル範囲４Ｋ〜（８Ｋ−１）に対する第２のポインタ、などを含み得る）。上記のように、データは、元のファイルに書き込まれながら圧縮され得、書き込みは、様々なサイズであることができるので、特定の書き込みは、固定サイズ範囲よりも大きいか、もしくは小さくあり得るか、または複数の範囲に及び得る。固定サイズ範囲よりも大きい書き込みに対しては、書き込み全体を圧縮して単一の圧縮されたチャンクにするほうが、書き込みを複数のチャンクに分割して、チャンクを別個に圧縮するよりも有益であり得る（例えば、データ圧縮スキームは一般的に、より大きなデータのサンプルに適用されたときのほうが、より効率的であり、また、圧縮されたチャンクがヘッダを含む実施形態に対しては、特定の書き込みに関連する複数のヘッダを有するよりも、１つのヘッダを有するほうが、スペースを節約することができる）。したがって、そのような実施形態においては、複数の範囲が、単一の圧縮されたチャンクにマッピングし得る。固定サイズ範囲よりも小さいか、または複数の範囲に及ぶ書き込みに対しては、単一の範囲が、複数の圧縮されたチャンクと関連し得る。特に、後者の場合においては、ポインタが使用されて、単一の範囲と関連する複数の圧縮されたチャンクをリンクし得る。
【００５９】
図９は、本発明の例示的な実施形態に従って、元のファイルの固定サイズ範囲を圧縮されたチャンクにマッピングするための概略図である。この例においては、それぞれ、４Ｋ（チャンクＦ）、１２Ｋ（チャンクＧ）、５１２（チャンクＨ）、および５１２（チャンクＩ）バイトの４つの連続する書き込みが存在する。各チャンクは圧縮されて、対応する圧縮されたチャンクＦ’、Ｇ’、Ｈ’、およびＩ’をそれぞれ形成する。この例においては、圧縮されたチャンクは、（各圧縮されたチャンクの始まりに黒いバーによって表現された）ヘッダを含む。圧縮されたチャンクは、圧縮されたファイル９０８として共に格納される。マップ９１０は、元のファイル範囲０−＞（４Ｋ−１）を圧縮されたチャンクＦ’にマッピングし、元のファイル範囲４Ｋ−＞（８Ｋ−１）、８Ｋ−＞（１２Ｋ−１）、および１２Ｋ−＞（１６Ｋ−１）を圧縮されたチャンクＧ’にマッピングし、そして、元のファイル範囲１６Ｋ−＞（２０Ｋ−１）を圧縮されたチャンクＨ’にマッピングする。圧縮されたチャンクＨ’のヘッダは、圧縮されたチャンクＩ’の始まりへのポインタ９１３を含む（また、図９に示されるように、圧縮されたチャンクＦ’のヘッダは、圧縮されたチャンクＧ’のスタートへのポインタを含み得、そして、圧縮されたチャンクＧ’のヘッダは、圧縮されたチャンクＨ’のスタートへのポインタを含みえる）。
【００６０】
ここで、要求が、範囲、例えば、８Ｋ−＞（１２Ｋ−１）内のデータに関する場合、マップ９１０に基づいて、圧縮されたチャンクＧ’が検索され、要求を満足させるために必要なデータを回復するために十分な程度に解凍される。範囲４Ｋ−＞（８Ｋ−１）に関する要求に対しても同じであり、また、範囲１２Ｋ−＞（１６Ｋ−１）に関する要求に対しても同じであることに留意されるべきである。
【００６１】
同様に、要求が、範囲１６Ｋ−＞（２０Ｋ−１）内のデータに関する場合、マップ９１０に基づいて、圧縮されたチャンクＨ’が検索、解凍され、要求を満足するためには不十分なデータが回復された場合、ポインタ９１３に基づいて、圧縮されたチャンクＩ’が検索され、要求を満足させるために必要なデータを回復するために少なくとも十分な程度に解凍される。マップ９１０は、圧縮されたチャンクＩ’へのポインタを含まないが、しかし、圧縮されたチャンクＩ’は、圧縮されたチャンクＨ’のヘッダに含まれたポインタ９１３を使用してアクセスされることに留意されるべきである。
【００６２】
特定の実施形態において、圧縮されたファイルは、圧縮されたファイルそれ自体の内に格納された１つ以上のマップと関連し得る。例えば、最初のマップは、例えば、圧縮されたファイルが最初に作成されたとき、圧縮されたファイルの始まりに置かれ得、そして、さらなるマップが必要に応じて追加されて、元のファイルデータを圧縮されたチャンクにマッピングし得る。図１０は、本発明の例示的な実施形態に従って、埋め込まれたマップを備えた圧縮されたファイル１００８の概略図であり、ここで、圧縮されたファイル１００８は、圧縮されたチャンク１００６へのポインタ１０１３を備えた第１のマップ１０１０と、圧縮されたチャンク１００７へのポインタ１０１４を備えた第２のマップ１０１１とを含む。この例において、各マップは、圧縮されたファイル内の「次の」マップへのポインタを含み（すなわち、第１のマップ１０１０は、第２のマップ１０１１へのポインタ１０１５を含む）、マップを横断することを容易にするが、しかし、マップは、他の論理構造体を使用しても見つけ出され、横断され得る。圧縮されたファイルが時間と共に変更されるにつれて（例えば、圧縮されたチャンクが、圧縮されたファイルの端に、または圧縮されたファイル内の空いた場所に追加されるにつれて）、マップポインタはこれに従って更新されることに留意されるべきである。図１１は、本発明の例示的な実施形態に従って、変更された圧縮されたファイル１１０８の概略図であり、ここで、第１のマップ１１１０は、圧縮されたチャンク１１０７のうちの１つへのポインタ１１１３を含み、第２のマップ１１１１は、圧縮されたチャンク１１０６へのポインタ１１１４を含む。これまでのように、第１のマップ１１１０は、第２のマップ１１１１へのポインタ１１１５を含む。  代替として、マップは別個のファイルシステムオブジェクトとして格納され得、この場合、圧縮されたファイルは、例えば、圧縮されたファイルのルートノード内にマップを格納するオブジェクトへのポインタを含み得る。
【００６３】
「クライアント」、「サーバ」、「スイッチ」、および「ノード」のような用語は、本明細書では、本発明のいくつかの実施形態において使用され得るデバイスを記述するために用いられることに注意すべきであり、文脈が他に必要としない限り、本発明をいかなる特定のデバイスタイプに限定すると解釈されるべきではない。従って、デバイスは、限定はされないが、ブリッジ、ルータ、ブリッジ−ルータ（ブルータ）、スイッチ、ノード、サーバ、コンピュータ、アプライアンス、または、他のタイプのデバイスを含み得る。そのようなデバイスは、一般に、通信ネットワーク上で通信するための、１つ以上のネットワークインターフェイスと、デバイスの機能を行うように構成されたプロセッサ（例えば、メモリと他の周辺デバイスおよび／または特定用途用ハードウェアを有するマイクロプロセッサ）とを含む。通信ネットワークは、一般に、公衆および／またはプライベートネットワークを含み得、ローカルエリア、広域、大都市圏エリア、格納、および／または他のタイプのネットワークを含み得、また、アナログ技術、デジタル技術、光技術、無線技術（例えば、Ｂｌｕｅｔｏｏｔｈ（登録商標））、ネットワーク技術、およびインターネット技術を含むが、限定はされない、通信技術を採用し得る。
【００６４】
デバイスは通信プロトコルおよび通信メッセージ（例えば、デバイスによって生成、送信、受信、格納、および／または処理されるメッセージ）を使用し得、そのようなメッセージは通信ネットワークまたは通信媒体によって運ばれることにも注意すべきである。文脈が他に必要としない限り、本発明はいなかる特定の通信メッセージタイプ、通信メッセージフォーマット、または通信プロトコルに限定されると解釈されるべきではない。従って、通信メッセージは、限定はされないが、概してフレーム、パケット、データグラム、ユーザデータグラム、セル、または他のタイプの通信メッセージを含み得る。
【００６５】
論理フローは、本発明の様々な局面を例証するために本明細書に記述され得、本発明をいかなる特定の論理フローあるいは論理実装に限定すると解釈されるべきではないことに注意すべきである。記述された論理は、全体の結果を変更することなく、あるいはそうでなければ本発明の範囲から外れることなく、異なる論理ブロック（例えば、プログラム、モジュール、機能またはサブルーチン）に分割され得る。しばしば、全体の結果を変更することなく、あるいはそうでなければ本発明の範囲から外れることなく、論理要素は追加され、変更され、省略され、異なる順序で実行され、または異なる論理構成（例えば、論理ゲート、ループプリミティブ、条件論理、および他の論理構成）を用いて実装され得る。
【００６６】
本発明は、プロセッサと共に使用されるコンピュータプログラム論理（例えば、マイクロプロセッサ、マイクロコントローラ、デジタルシグナルプロセッサ、または、汎用コンピュータ）、プログラム可能論理デバイスと共に使用されるプログラム可能論理（例えば、フィールドプログラム可能ゲートアレイ（ＦＰＧＡ）または他のＰＬＤ），個別部品、集積回路網（例えば、特定用途向け集積回路（ＡＳＩＣ））、または、それらの任意の組み合わせを含む任意の他の手段を含むが限定はされない、多くの異なる形式で実現され得る。本発明の典型的な実施形態においては、記述された論理のほとんどはコンピュータプログラム命令の組として実装され、命令は、コンピュータ実行可能な形式に変換され、コンピュータ読み込み可能な媒体等に格納され、オペレーティングシステムの制御の下でマイクロプロセッサによって実行される。
【００６７】
本明細書で前に記載された機能性のすべてあるいは一部を実装するコンピュータプログラム論理は、ソースコード形式、コンピュータ実行可能形式、および様々な中間形式（例えば、アセンブラ、コンパイラ、リンカまたはローケータによって生成される形式）を含むが限定はされない、様々な形式で実施され得る。ソースコードは、様々なオペレーティングシステムまたはオペレーティング環境と共に使用される、任意の様々なプログラミング言語（例えば、オブジェクトコード、アセンブリ言語、あるいはＦｏｒｔｒａｎ、Ｃ、Ｃ＋＋、ＪＡＶＡ（登録商標）、またはＨＴＭＬのような高級言語）で実装される一連のコンピュータプログラム命令を含み得る。ソースコードは、様々なデータ構造および通信メッセージを定義し使用し得る。ソースコードは、コンピュータ実行可能な形式（例えば、インタープレッタを介する）であり得、または、ソースコードは、コンピュータ実行可能な形式に（例えば、トランスレータ、アセンブラ、またはコンパイラを介して）変換され得る。
【００６８】
コンピュータプログラムは、任意の形式（例えば、ソースコード形式、コンピュータ実行可能形式、または中間形式）において恒久的にかまたは一時的にかのいずれかで、半導体メモリデバイス（例えば、ＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＥＰＲＯＭ、またはフラッシュプログラマブルＲＡＭ）、磁気メモリデバイス（例えば、ディスケット、または固定ディスク）、光学メモリデバイス（例えば、ＣＤ−ＲＯＭ）、ＰＣカード（例えば、ＰＣＭＣＩＡカード）、または、他のメモリデバイスのような、実体的な格納媒体に固定され得る。コンピュータプログラムは、任意の様々な通信技術を使用してコンピュータに送信可能な信号中の任意の形式において固定され得、様々な通信技術には、アナログ技術、デジタル技術、光技術、無線技術（例えば、Ｂｌｕｅｔｏｏｔｈ(登録商標））、ネットワーク技術、およびインターネットワーキング技術が含まれるがそれらに限定はされない。コンピュータプログラムは、印刷されたあるいは電子的文書（例えば、パッケージソフトウェア）を伴う取り外し可能な格納媒体として、任意の形式で配布され得、コンピュータシステムにあらかじめロードされて（例えば、オンシステムＲＯＭまたは固定ディスク）配布され、または、サーバまたは、通信システム（例えば、インターネットまたは、Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）上の電子掲示板から配布され得る。
【００６９】
本明細書で前に記載された機能性のすべてあるいは一部を実装するハードウェア論理（プログラム可能論理デバイスで使用するプログラマブル論理を含む）は、従来の人手による方法を使用して設計され得るか、あるいは、Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ（ＣＡＤ）、ハードウェア記述言語（例えば、ＶＨＤＬまたはＡＨＤＬ）、あるいは、ＰＬＤプログラミング言語（例えば、ＰＡＬＡＳＭ、ＡＢＥＬ、またはＣＵＰＬ）のような様々なツールを使用して、設計され、捕捉され、シミュレートされ、または電子的に文書化され得る。
【００７０】
プログラム可能論理は、恒久的にかまたは一時的にかのいずれかで、半導体メモリデバイス（例えば、ＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＥＰＲＯＭ、またはフラッシュプログラマブルＲＡＭ）、磁気メモリデバイス（例えば、ディスケット、または固定ディスク）、光メモリデバイス（例えば、ＣＤ−ＲＯＭ）、または、他のメモリデバイスのような、実体的な格納媒体に固定され得る。プログラム可能論理は、任意の様々な通信技術を使用してコンピュータに送信可能な信号において固定され得、様々な通信技術には、アナログ技術、デジタル技術、光技術、無線技術（例えば、Ｂｌｕｅｔｏｏｔｈ(登録商標））、ネットワーク技術、およびインターネット技術が含まれるがそれらに限定はされない。プログラム可能論理は、印刷されたあるいは電子的文書（例えば、パッケージソフトウェア）を伴う取り外し可能な格納媒体として、任意の形式で配布され得、コンピュータシステムにあらかじめロードされて（例えば、システムＲＯＭまたは固定ディスク上に）配布され、または、サーバまたは通信システム（例えば、インターネットまたは、Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）上の電子掲示板から配布され得る。
【００７１】
本発明は、本発明の範囲から外れることなく、他の特定の形式において実装され得る。本「発明」へのいかなる参照も、本発明の例示的実施形態の参照を意図しており、文脈が他に必要としない限り、本発明のすべての実施形態を参照すると解釈されるべきではない。記載された実施形態は、あらゆる点において、単に例示と考えられるべきであり、制限と考えるべきではない。
【図１】
0005295394.tif 000010
【図２】
0005295394.tif 000011
【図３】
0005295394.tif 000012
【図４】
0005295394.tif 000013
【図５】
0005295394.tif 000014
【図６】
0005295394.tif 000015
【図７】
0005295394.tif 000016
【図８】
0005295394.tif 000017
【図９】
0005295394.tif 000018
【図１０】
0005295394.tif 000019
【図１１】
0005295394.tif 000020