JP2024525170A - データ圧縮方法及び装置 - Google Patents

Abstract

この出願は、データ圧縮方法及び装置を開示する。方法は、読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックを取得することであって、ことと、ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得することであって、圧縮データ・ブロックの第１の容量は全て同じであり、第１の容量は、圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表し、ことと、ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立し、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録することであって、ことと、を含む。第１のインデックスは、ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。データ・ブロックが読み出されるときに、読み出し効率を効果的に向上させることができ、読み出し増幅係数が小さいランダム読み出しシナリオでデータを読み出すことを保証することができる。

Description

この出願は、２０２１年６月１６日に中国国家知識産権局に出願された「ＤＡＴＡ ＣＯＭＰＲＥＳＳＩＯＮ ＭＥＴＨＯＤ ＡＮＤ ＡＰＰＡＲＡＴＵＳ」と題する中国特許出願第２０２１１０６６７８８２．７号に対する優先権を主張し、その全体が参照により本明細書に組み込まれる。

この出願は、データ圧縮技術の分野に関係し、特に、データ圧縮方法及び装置に関係する。

ストレージ・システムの全体的な入出力（ｉｎｐｕｔ ｏｕｔｐｕｔ、ＩＯ）の読み出し／書き込み性能を向上させるために、メモリ内のファイルを圧縮する必要がある。現在、Ｌｉｎｕｘの読み出し／書き込みファイル・システムのＦ２ＦＳ、ジャーナリング・フラッシュ・ファイル・システム・バージョン２（ｊｏｕｒｎａｌｌｉｎｇ Ｆｌａｓｈ ｆｉｌｅ ｓｙｓｔｅｍ ｖｅｒｓｉｏｎ ２、ＪＦＦＳ２）、Ｂツリー・ファイル・システム（Ｂ－ｔｒｅｅ ｆｉｌｅ ｓｙｓｔｅｍ、ＢＴＲＦＳ）など、及びＷｉｎｄｏｗｓの読み出し／書き込みファイル・システムのＮＴＦＳなどがある。メタデータ領域は、ファイル・システム全体に占める割合が小さいため、データ領域が、通常、デバイスの記憶容量を大きく占有する。したがって、データ領域のデータを圧縮することにより、入出力ＩＯのサイズを縮小し、ＩＯの読み込み／書き込み性能を向上させることができる。

既存のデータ圧縮方法では、圧縮が必要とされるオリジナル・ファイル・データ（又はソース・データと呼ばれる）は、一般に、固定サイズの最小圧縮単位に基づいて圧縮されており、圧縮ファイル・データ（又は圧縮データと呼ばれる）は、ヘッダ・データと圧縮データを含んでもよい。ヘッダ・データはファイル・データの属性情報を表すために使用され、圧縮データはファイル・データのコンテンツを表すために使用される。次いで、圧縮ファイル・データは記憶媒体に保存される。しかし、既存の読み出し／書き込みファイル・システムの圧縮ソリューションでは、ランダム読み出し増幅の問題があり、読み出し効率が低い。

この出願の実施形態は、読み出し／書き込みファイル・システムのランダム読み出し増幅の問題を解決し、読み出し効率を向上させるデータ圧縮方法及び装置を提供する。

第１の態様によれば、この出願の一実施形態は、データ圧縮方法を提供する。本方法は、電子デバイスによって実行されてもよいし、電子デバイス内に位置するコンポーネント（例えば、チップ、チップ・システム、又はプロセッサ）によって実行されてもよい。以下、本方法が電子デバイスによって実行される例を使用して説明を提供する。本方法は、電子デバイスが、読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックを取得することであって、ｍは１以上の正の整数である、ことを含む。電子デバイスは、ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得し、圧縮データ・ブロックの第１の容量は全て同じであり、第１の容量は、圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表し、ｎは１以上の正の整数である。電子デバイスは、ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立し、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録する。ｉは１以上ｎ以下の正の整数であり、ｊは１以上ｍ以下の正の整数である。第１のインデックスは、ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

この出願の実施形態で提供されるデータ圧縮方法によれば、データ・ブロックが読み出されるときに、読み出し効率を効果的に向上させることができ、読み出し増幅係数が小さいランダム読み出しシナリオでデータを読み出すことを保証することができる。追加的に、データ・ブロックのインデックスに含まれる属性が修正されてもよく、そのため、ストレージ・デバイス上の圧縮ファイルが修正されてもよい。この出願の実施形態では、既存の読み出し／書き込みファイル・システムにおける圧縮ソリューションのランダム読み出し増幅の問題を解決し、固定出力圧縮方式を有する既存のファイル・システムがデータ及びメタデータ更新をサポートできないという問題を解決することが分かる。

具体的かつ可能な実装では、ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得することは、具体的には、ｍ個のデータ・ブロック内の全てのデータ・ブロックを予め設定された順序で第１のセットに順次割り当てることである。第１のセットのｊ個のデータ・ブロックのデータ容量が、第１のセットの定格容量と等しいときに、ｊ個のデータ・ブロックに対して、指定された圧縮閾値に基づいて圧縮動作が実行されて、ｉ番目の圧縮データ・ブロックを取得する。

ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、具体的には、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和が、ｊ個のデータ・ブロックの合計データ長以下であるときに、ｊ個のデータ・ブロックの各々の第１のインデックスを確立することである。

具体的かつ可能な実装では、属性情報は、属性情報は、データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と、データ・ブロックのデータ・ページが有効であるかどうかを表すために使用される第２の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と、データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と、データ・ブロックのデータ・ページが、データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と、データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットであり、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属しないときに、第７の属性の属性値が、データ・ブロックのデータ・ページと、圧縮データ・ブロックの第１の圧縮ページとの間の距離であることを表すために使用される第７の属性とのうちの少なくとも１つを含む。

具体的かつ可能な実装では、属性情報は第３の属性を含み、ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、具体的には、ｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページであるときに、第３の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページではないときに、第３の属性の属性値に０を代入することである。

具体的かつ可能な実装では、属性情報は、第７の属性を含み、本方法は、第３の属性の属性値が１であるときに、第７の属性の属性値を、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットに更新することか、又は第３の属性の属性値が０であるときに、第７の属性の属性値を、データ・ブロックのデータ・ページと圧縮データ・ブロックの第１の圧縮ページとの間の距離に更新することをさらに含む。

具体的かつ可能な実装では、属性情報は第４の属性を含み、ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、具体的には、ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるときに、第４の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれないときに、第４の属性の属性値に０を代入することである。

具体的かつ可能な実装では、属性情報は第２の属性を含み、ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、具体的には、ｊ個のデータ・ブロックの各々のデータ・ページが有効であるときに、第２の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが無効であるときに、第２の属性の属性値に０を代入することである。

いくつかの可能な実装では、本方法は、ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得することの前に、上書き対象データの第２のセットを取得することであって、第２のセットは、ｐ個の圧縮データ・ブロックを含み、ｐは１以上の正の整数である、ことと、ｐ個の圧縮データ・ブロックにおける第１の対象圧縮データの圧縮ページと、第１の対象圧縮データ・ブロックの圧縮ページに対応するｑ個のデータ・ブロックとを取得することであって、ｑは１以上の正の整数である、ことと、ｑ個のデータ・ブロックにおいて、ｑ個のデータ・ブロック内の第１の対象データ・ブロックの場所オフセットを決定することと、第１の対象データ・ブロックのデータ・ページが、上書き対象データのデータ・ページであると決定することと、をさらに含む。

具体的かつ可能な実装では、第１のインデックスは、記憶媒体におけるｉ番目の圧縮データ・ブロックの記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

いくつかの可能な実装では、本方法は、第１のデータ・ブロックの第１のインデックスを読み出して、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックス・アドレスを取得することであって、第１のインデックスが第１のデータ・ブロックの属性情報を含む、ことと、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックスを読み出すことと、第１の圧縮データ・ブロックのインデックスに基づいて第１の圧縮データ・ブロックを伸長して、第１の圧縮データ・ブロックに対応する複数のデータ・ブロックを取得することであって、複数のデータ・ブロックは第１のデータ・ブロックを含む、ことと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットを決定することと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットに基づいて第１のデータ・ブロックのデータを取得することと、をさらに含む。

第２の態様によれば、この出願の一実施形態は、データ圧縮装置を提供する。本装置は、読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックを取得するように構成されている第１の取得ユニットであって、ｍは１以上の正の整数である、第１の取得ユニットと、ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得するように構成されている圧縮ユニットであって、圧縮データ・ブロックの第１の容量は全て同じであり、第１の容量は、圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表し、ｎは１以上の正の整数である、圧縮ユニットと、ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立し、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録するように構成されている更新ユニットと、を含む。
ｉは１以上ｎ以下の正の整数であり、ｊは１以上ｍ以下の正の整数である。第１のインデックスは、ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

この出願の実施形態で提供されるデータ圧縮方法によれば、データ・ブロックが読み出されるときに、読み出し効率を効果的に向上させることができ、読み出し増幅係数が小さいランダム読み出しシナリオでデータを読み出すことを保証することができる。追加的に、データ・ブロックのインデックスに含まれる属性が修正されてもよく、そのため、ストレージ・デバイス上の圧縮ファイルが修正されてもよい。この出願の実施形態では、既存の読み出し／書き込みファイル・システムにおける圧縮ソリューションのランダム読み出し増幅の問題を解決し、固定出力圧縮方式を有する既存のファイル・システムがデータ及びメタデータ更新をサポートできないという問題を解決することが分かる。

具体的かつ可能な実装では、圧縮ユニットは、ｍ個のデータ・ブロックの全てのデータ・ブロックを予め設定された順序で第１のセットに順次割り当てるように構成されている。第１のセットのｊ個のデータ・ブロックのデータ容量が、第１のセットの定格容量と等しいときに、ｊ個のデータ・ブロックに対して、指定された圧縮閾値に基づいて圧縮動作が実行されて、ｉ番目の圧縮データ・ブロックを取得する。

具体的かつ可能な実装では、更新ユニットは、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和が、ｊ個のデータ・ブロックの合計データ長以下であるときに、ｊ個のデータ・ブロックの各々の第１のインデックスを確立するように構成されている。

具体的かつ可能な実装では、属性情報は、属性情報は、データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と、データ・ブロックのデータ・ページが有効であるかどうかを表すために使用される第２の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と、データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と、データ・ブロックのデータ・ページが、データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と、データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットであることを表すために使用される第７の属性とのうちの少なくとも１つを含む。データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属しないときに、第７の属性の属性値が、データ・ブロックのデータ・ページと圧縮データ・ブロックの第１の圧縮ページとの間の距離である。

具体的かつ可能な実装では、属性情報は、第３の属性を含み、更新ユニットは、ｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページであるときに、第３の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページではないときに、第３の属性の属性値に０を代入することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第７の属性を含み、更新ユニットは、第３の属性の属性値が１であるときに、第７の属性の属性値を、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットに更新することか、又は第３の属性の属性値が０であるときに、第７の属性の属性値を、データ・ブロックのデータ・ページと圧縮データ・ブロックの第１の圧縮ページとの間の距離に更新することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第４の属性を含み、更新ユニットは、ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるときに、第４の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれないときに、第４の属性の属性値に０を代入することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第２の属性を含み、更新ユニットは、ｊ個のデータ・ブロックの各々のデータ・ページが有効であるときに、第２の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが無効であるときに、第２の属性の属性値に０を代入することを行うようにさらに構成されている。

いくつかの可能な実施態様では、本装置は、上書き対象データの第２のセットを取得するように構成されている第２の取得ユニットであって、第２のセットは、ｐ個の圧縮データ・ブロックを含み、ｐは１以上の正の整数である、第２の取得ユニットと、ｐ個の圧縮データ・ブロックにおける第１の対象圧縮データの圧縮ページと、第１の対象圧縮データ・ブロックの圧縮ページに対応するｑ個のデータ・ブロックとを取得するように構成されている第３の取得ユニットであって、ｑは１以上の正の整数である、第３の取得ユニットと、ｑ個のデータ・ブロックにおいて、ｑ個のデータ・ブロック内の第１の対象データ・ブロックの場所オフセットを決定するように構成されている第１の決定ユニットと、第１の対象データ・ブロックのデータ・ページが、上書き対象データのデータ・ページであると決定するように構成されている第２の決定ユニットと、をさらに含む。

具体的かつ可能な実装では、第１のインデックスは、記憶媒体におけるｉ番目の圧縮データ・ブロックの記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

いくつかの可能な実装では、本装置は、第１のデータ・ブロックの第１のインデックスを読み出して、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックス・アドレスを取得するように構成されている第１の読み出しユニットであって、第１のインデックスが第１のデータ・ブロックの属性情報を含む、第１の読み出しユニットと、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックスを読み出すように構成されている第２の読み出しユニットと、第１の圧縮データ・ブロックのインデックスに基づいて第１の圧縮データ・ブロックを伸長して、第１の圧縮データ・ブロックに対応する複数のデータ・ブロックを取得するように構成されている伸長ユニットであって、複数のデータ・ブロックは第１のデータ・ブロックを含む、伸長ユニットと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットを決定するように構成されている第３の決定ユニットと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットに基づいて第１のデータ・ブロックのデータを取得するように構成されている第３の取得ユニットと、をさらに含む。

第３の態様によれば、この出願の一実施形態は、第１の態様の方法を実行するように構成されているデバイスを提供する。

第４の態様によれば、この出願の一実施形態は、コンピュータ可読記憶媒体を提供する。コンピュータ可読記憶媒体は、コンピュータ命令を記憶する。コンピュータ命令が電子デバイス上で実行されるときに、電子デバイスは、第１の態様のデータ圧縮方法を実行することが可能となる。

第５の態様によれば、本出願の一実施形態は、コンピュータ・プログラムを提供する。プログラムがプロセッサによって呼び出されるときに、第１の態様のデータ圧縮方法は、実行される。

第６の態様によれば、この出願の一実施形態は、１つ以上のプロセッサを含むチップ・システムを提供する。１つ以上のプロセッサが命令を実行するときに、１つ以上のプロセッサは、第１の態様のデータ圧縮方法を実行する。

この出願における技術的特徴、技術的解決策、有益な効果、又は類似の文言の説明は、全ての特徴及び利点が任意の個々の実施形態において実装可能であることを示唆しないと理解されたい。反対に、特徴又は有益な効果の説明は、少なくとも１つの実施形態が特定の技術的特徴、技術的解決策、又は有益な効果を含むことを意味すると理解されよう。したがって、この明細書における技術的特徴、技術的解決策、又は有益な効果の説明は、必ずしも同じ実施形態に属さなくてもよい。さらに、実施形態に記載される技術的特徴、技術的解決策、及び有益な効果は、任意の適切な方式で組み合わされてもよい。当業者は、実施形態が、特定の実施形態において、１つ以上の特定の技術的特徴、技術的解決策、又は有益な効果を伴わずに実装されてもよいと理解してもよい。他の実施形態では、全ての実施形態を反映するわけではない特定の実施形態において、追加の技術的特徴及び有益な効果が識別されてもよい。

この出願一実施形態による、オペレーティング・システムの構成ブロック図である。

この出願の一実施形態による、ストレージ・システムの構造の概略図である。

図１ｂのストレージ・システムのソリッド・ステート・ディスクの構造の概略図である。

図２のソリッド・ステート・ディスクのフラッシュ・チップの構造の概略図である。

図３のフラッシュ・チップに対応するフラッシュ変換層の概略図である。

固定入力圧縮モードの概略図である。

この出願の一実施形態による、固定出力圧縮モードの概略図である。

この出願の一実施形態による、データ・ブロック・インデックスの概略図である。

既存の拡張可能な読み出し専用ファイル・システムにおけるデータ・ブロック・インデックスの概略図である。

この出願の一実施形態による、データ圧縮方法の概略フローチャートである。 この出願の一実施形態による、データ圧縮方法の概略フローチャートである。

この出願の一実施形態による、データ・ブロック・インデックスを更新する概略フローチャートである。 この出願の一実施形態による、データ・ブロック・インデックスを更新する概略フローチャートである。

この出願の一実施形態による、データ圧縮中のデータ・ブロック・インデックス関係の概略図である。

この出願の一実施形態による、別のデータ圧縮方法の概略フローチャートである。

この出願の一実施形態による、上書き又は読み出し手順におけるデータ・ブロック・インデックス関係の概略図である。

この出願の一実施形態による、データ読み出し手順の概略フローチャートである。

この出願の一実施形態による、データ圧縮装置の構造の概略図である。

この出願の説明で言及される「含む」、「有する」、及び任意の他のそれらの変化形の用語は、非排他的な包含をカバーすることを意図している。例えば、一連のステップ又はユニットを含む、プロセス、方法、システム、製品又はデバイスは、列挙されたステップ又はユニットに限定されず、任意選択で、列挙されていない別のステップ又はユニットをさらに含むか、あるいは任意選択で、プロセス、方法、製品又はデバイスに固有の別のステップ又はユニットをさらに含む。

この出願の実施形態では、「例」又は「例えば」の文言は、例、例示又は説明を与えることを表すために使用されることに留意されたい。本出願において、「例」又は「例えば」として記載される任意の実施形態又は設計スキームは、他の実施形態又は設計スキームよりも好ましいものとして、又はより多くの利点を有するものとして説明されるべきではない。正確には、「例」、「例えば」などの文言は、関連概念を特定の方式で提示することを意図している。

この出願の実施態様の説明では、別段特定されない限り、「複数」とは、２以上を意味する。本明細書における「及び／又は」の用語は、関連するオブジェクト間の関連付け関係のみを記載し、３つの関係があり得ることを示す。例えば、Ａ及び／又はＢは、以下の３つのケース、すなわち、Ａのみが存在すること、Ａ及びＢの両方が存在すること、並びにＢのみが存在することを表してもよい。

理解を簡単にするために、この出願の実施形態で使用され得る関係する用語及び概念を最初に記載する。

図１ａは、オペレーティング・システムの構成ブロック図である。

オペレーティング・システム（ｏｐｅｒａｔｉｎｇ ｓｙｓｔｅｍ、略してＯＳ）は、コンピュータのハードウェア及びソフトウェアリソースを管理するコンピュータ・プログラムであり、例えば、ｕｎｉｘ、Ｗｉｎｄｏｗｓ、及びＬｉｎｕｘである。オペレーティング・システムは、基本的なトランザクション、例えば、メモリの管理と構成、システム・リソースの供給と需要の優先度の決定、入出力デバイスの制御、ネットワークの運用、及びファイル・システムの管理を処理する必要がある。オペレーティング・システムはまた、ユーザがシステムと対話するための動作インターフェースを提供する。

オペレーティング・システム・カーネルは、ほとんどのオペレーティング・システムのコア部分である。オペレーティング・システム・カーネルは、オペレーティング・システム内のストレージ・デバイス、ファイル、周辺機器、システム・リソースを管理するために使用される部分を含み、システムのプロセス、メモリ、デバイス・ドライバ、ファイル及びネットワーク・システムを管理し、オペレーティング・システムの性能や安定性を決定する。オペレーティング・システム・カーネルは、ハードウェア抽象化層、ディスク及びファイル・システム制御、マルチタスクなどの機能を提供するシステム・ソフトウェアである。オペレーティング・システム・カーネルは、多くのアプリケーションに対してコンピュータ・ハードウェアへの安全なアクセスを提供し、アプリケーションがコンピュータ・ハードウェアの一部に対していつ動作を実行するか、及びそれにかかる時間を決定することができる。コンピュータ・ハードウェア上での直接動作は非常に複雑であるため、オペレーティング・システム・カーネルは、これらの動作を完了するためのハードウェア抽象化方法のセットを提供することができる。

ファイル・システムは、オペレーティング・システム・カーネルのコア・モジュール、すなわち、メイン・コンポーネントである。ファイル・システムは、ストレージ・デバイス上のファイルを編成し、ファイル情報を管理及び記憶し、主にユーザのためのファイルを作成し、ファイルを記憶、読み出し、修正、ダンプを行い、ファイル・アクセスを制御し、ユーザがファイルを使用しなくなったときにファイルをキャンセルする方法である。

ファイル・システムは、カーネル内のファイルの抽象表現を提供し、ファイルを物理的なストレージ・デバイス（ディスク、ハード・ディスクなど）にマッピングし、ストレージ・デバイス上のファイルの物理アドレスをユーザが見ることができるパス及びファイル名にマッピングし、ファイル・データの迅速な読み出し、修正、及び永続化を容易にする。

ファイル・システムには、読み出し／書き込みファイル・システム及び読み出し専用ファイル・システムを含む。読み出し／書き込みファイル・システムは、ファイルをストレージ・デバイスに書き込むか、又はファイルをストレージ・デバイスから読み出すことができるファイル・システムであり、例えば、ファイル・アロケーション・テーブル（ｆｉｌｅ ａｌｌｏｃａｔｉｏｎ ｔａｂｌｅ、ＦＡＴ）、ハイ・パフォーマンス・ファイル・システム（ｈｉｇｈ ｐｅｒｆｏｒｍａｎｃｅ ｆｉｌｅ ｓｙｓｔｅｍ、ＨＰＦＳ）、ニュー・テクノロジー・ファイル・システム（ｎｅｗ ｔｅｃｈｎｏｌｏｇｙ ｆｉｌｅ ｓｙｓｔｅｍ、ＮＴＦＳ）、フォース・エクテンデット・ファイル・システム（ｆｏｕｒｔｈ ｅｘｔｅｎｄｅｄ ｆｉｌｅ ｓｙｓｔｅｍ、ＥＸＴ４）、フラッシュ・フレンドリー・ファイル・システム（ｆｌａｓｈ ｆｒｉｅｎｄｌｙ ｆｉｌｅ ｓｙｓｔｅｍ、Ｆ２ＦＳ）である。読み出し専用ファイル・システムは、ファイルをストレージ・デバイスから読み出すことのみが可能であり、ファイルをストレージ・デバイスに書き込むことができないファイル・システムであり、例えば、拡張可能な読み出し専用ファイル・システム（ｅｘｔｅｎｄａｂｌｅ ｒｅａｄ－ｏｎｌｙ ｆｉｌｅ ｓｙｓｔｅｍ、ＥＲＯＦＳ）である。

この出願をより明確にするために、最初に、この出願のアプリケーション・シナリオについて記載する。

図１ｂは、ストレージ・システムの構造の概略図である。

図１ｂに示すアプリケーション・シナリオでは、ユーザは、アプリケーションを使用してデータにアクセスする。これらのアプリケーションを実行するコンピュータは、「アプリケーション・サーバ」と呼ばれる。アプリケーション・サーバ１００は、物理マシンであってもよいし、仮想マシンであってもよい。物理アプリケーション・サーバは、デスクトップコンピュータ、サーバ、ノートブック・コンピュータ、及びモバイル・デバイスを含むが、これらに限定されない。アプリケーション・サーバは、データにアクセスするためにファイバ・チャネル・スイッチ１１０を使用してストレージ・システムにアクセスする。しかし、スイッチ１１０は、任意選択であり、アプリケーション・サーバ１００はまた、ネットワークを使用してストレージ・システム１２０と直接通信するようにしてもよい。代替的には、ファイバ・チャネル・スイッチ１１０は、Ｅｔｈｅｒｎｅｔスイッチ、ＩｎｆｉｎｉＢａｎｄスイッチ、ＲｏＣＥ（ＲＤＭＡ ｏｖｅｒ Ｃｏｎｖｅｒｇｅｄ Ｅｔｈｅｒｎｅｔ）スイッチなどで置き換えられてもよい。

図１ｂに示すストレージ・システム１２０は、集中型ストレージ・システムである。集中型ストレージ・システムは、１つ以上のメイン・デバイスを含む中央ノードである。データは中央ノードに記憶され、システム全体の全てのデータ処理サービスは、中央ノードに展開される。換言すれば、集中型ストレージ・システムでは、端末又はクライアントはデータの入出力のみを担当し、全てのデータ記憶及び制御処理は中央ノードによって完了される。集中型ストレージ・システムは統合ポータルを特徴とし、外部デバイスからの全てのデータはこのポータルを通過する。ポータルは、集中型ストレージ・システムのエンジン１２１である。エンジン１２１は、集中型ストレージ・システムのコア・コンポーネントであり、エンジン１２１には、ストレージ・システムの多くの高度な機能が実装されている。

図１ｂに示すように、エンジン１２１は、１つ以上のコントローラを有する。図１ｂでは、エンジンが２つのコントローラを含む例が説明のために使用される。コントローラ０とコントローラ１の間にはミラー・チャネルがある。したがって、コントローラ０がデータをコントローラ０のメモリ１２４に書き込んだ後、コントローラ０は、ミラー・チャネルを介してデータのコピーをコントローラ１に送信してもよく、コントローラ１は、そのコピーをコントローラ１のローカル・メモリ１２４に記憶する。したがって、コントローラ０とコントローラ１とは互いにバックアップを行う。コントローラ０が故障したときに、コントローラ１は、コントローラ０のサービスを引き継いでもよい。コントローラ１が故障したときに、コントローラ０は、コントローラ１のサービスを引き継いでもよく、ハードウェア故障によるストレージ・システム１２０全体の使用不能を回避する。４つのコントローラがエンジン１２１に配設されるときに、ミラー・チャネルが任意の２つのコントローラ間に存在し、したがって、任意の２つのコントローラが互いにバックアップする。

エンジン１２１は、フロントエンド・インターフェース１２５とバックエンド・インターフェース１２６とをさらに含み、フロントエンド・インターフェース１２５は、アプリケーション・サーバ１００と通信して、アプリケーション・サーバ１００にストレージ・サービスを提供するように構成されている。バックエンド・インターフェース１２６は、ハード・ディスク１３４と通信して、ストレージ・システムの容量を拡張するように構成されている。エンジン１２１は、バックエンド・インターフェース１２６を介してさらに多くのハード・ディスク１３４に接続して、大きなストレージ・リソース・プールを形成してもよい。

エンジン１２１とディスク・エンクロージャ１３０との間の通信プロトコルのタイプに基づいて、ディスク・エンクロージャ１３０は、ＳＡＳディスク・エンクロージャ、ＮＶＭｅディスク・エンクロージャ、ＩＰディスク・エンクロージャ、又は別のタイプのディスク・エンクロージャであってもよい。ＳＡＳディスク・エンクロージャはＳＡＳ ３．０プロトコルを使用し、各エンクロージャは２５のＳＡＳハード・ディスクをサポートする。エンジン１２１は、オンボードＳＡＳインターフェース又はＳＡＳインターフェース・モジュールを介してディスク・エンクロージャ１３０に接続される。ＮＶＭｅディスク・エンクロージャは、完全なコンピュータ・システムのようなものである。ＮＶＭｅハード・ディスクがＮＶＭｅディスク・エンクロージャに挿入されている。追加的に、ＮＶＭｅディスク・エンクロージャは、ＲＤＭＡポートを介してエンジン１２１に接続される。

ハードウェア的には、図１ｂに示すように、コントローラ０は、少なくともプロセッサ１２３とメモリ１２４とを含む。プロセッサ１２３は、ストレージ・システム（サーバ又は他のストレージ・システム）の外部からのデータ・アクセス要求を処理するように構成されており、かつストレージ・デバイス内部で生成された要求を処理するように構成されている中央処理ユニット（ｃｅｎｔｒａｌ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ、ＣＰＵ）である。例えば、プロセッサ１２３は、フロントエンド・ポート１２５を使用して、アプリケーション・サーバ１００から送信されたデータ書き込み要求を受信するときに、そのデータ書き込み要求のデータをメモリ１２４に一時的に記憶する。メモリ１２４内のデータの総量が特定の閾値に達するときに、プロセッサ１２３は、バックエンド・ポートを使用して、メモリ１２４に記憶されたデータを、永続的な記憶のためにハード・ディスク１３４に送信する。

メモリ１２４は、プロセッサと直接データを交換する内部メモリである。データは、いつでも高速にメモリに読み書きされ得、メモリは、オペレーティング・システム又は他の実行中のプログラムの一時的なデータ・メモリとして機能する。メモリは、少なくとも２つのタイプのメモリを含み、例えば、メモリは、ランダム・アクセス・メモリであってもよい。例えば、ランダム・アクセス・メモリは、ダイナミック・ランダム・アクセス・メモリ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ＤＲＡＭ）、又はストレージ・クラス・メモリ（Ｓｔｏｒａｇｅ Ｃｌａｓｓ Ｍｅｍｏｒｙ、ＳＣＭ）である。ＤＲＡＭは、半導体メモリであり、ほとんどのランダム・アクセス・メモリ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ＲＡＭ）と同様に、揮発性メモリ（ｖｏｌａｔｉｌｅ Ｍｅｍｏｒｙ）デバイスである。ＳＣＭは、従来のストレージ・デバイスの特徴とメモリの特徴の両方を組み合わせた複合ストレージ技術を使用する。ストレージ・クラス・メモリは、ハード・ディスクに比べて高速な読み書きを提供することができるが、アクセス速度の観点からＤＲＡＭよりも遅く、コストの観点からはＤＲＡＭよりも安い。しかし、ＤＲＡＭ及びＳＣＭは、実施形態における説明のための例示にすぎない。メモリは、別のランダム・アクセス・メモリ、例えば、スタティック・ランダム・アクセス・メモリ（Ｓｔａｔｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ＳＲＡＭ）をさらに含んでもよい。追加的に、メモリ１２４は、デュアル・インライン・メモリ・モジュール（Ｄｕａｌ Ｉｎ－ｌｉｎｅ Ｍｅｍｏｒｙ Ｍｏｄｕｌｅ、略してＤＩＭＭ）、すなわち、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）で構成されたモジュールであってもよいし、ソリッド・ステート・ディスク（Ｓｏｌｉｄ Ｓｔａｔｅ Ｄｉｓｋ、ＳＳＤ）であってもよい。実際のアプリケーションでは、コントローラ０には、複数のメモリ１２４と、異なるタイプのメモリ１２４とが構成されていてもよい。この実施形態では、メモリ１１３の数及びタイプは限定されない。追加的に、メモリ１２４は、停電保護機能を有するように構成されてもよい。停電保護機能とは、停電後にシステムの電源を再投入してもメモリ１２４に記憶されたデータが失われないことを意味する。停電保護機能を有するメモリは、不揮発性メモリと呼ばれる。

例えば、メモリ１２４及びハード・ディスク１３４は、いずれもソリッド・ステート・ドライブ（英語：Ｓｏｌｉｄ－ｓｔａｔｅ ｄｒｉｖｅ又はＳｏｌｉｄ－ｓｔａｔｅ ｄｉｓｋ、略してＳＳＤ）であってもよく、主にフラッシュ（ＮＡＮＤ Ｆｌａｓｈ）を不揮発性メモリとして使用するストレージ・デバイスである。図２に示すように、ＳＳＤ２００は、ＮＡＮＤフラッシュと、プライマリ・コントローラ（略してＰＣ）２０１とを含む。ＮＡＮＤフラッシュは、データを記憶するように構成されている複数のフラッシュ・チップ２０５を含む。ＰＣ２０１は、ＳＳＤの頭脳であり、データ記憶の管理、ＳＳＤの性能及び耐用年数の維持などのいくつかの複雑なタスクを担当する。ＰＣ２０１は、組み込み型のマイクロチップであり、ＳＳＤの動作要求を全て送信するためのコマンドセンタのような機能を有するプロセッサ２０２を含む。例えば、プロセッサ２０２は、バッファ内のファームウェアを使用して、データの読み書き、ガーベジ・コレクション、ウェア・レベリングなどの機能を実行してもよい。

ＳＳＤ ＰＣ２０１は、ホスト・インターフェース２０４と、いくつかのチャネル・コントローラとをさらに含む。ホスト・インターフェース２０４は、ホストと通信するように構成されている。本明細書におけるホストとは、サーバ、パーソナル・コンピュータ、アレイ・コントローラなどの任意のデバイスを指す。ＰＣ２０１は、複数のチャネル・コントローラを使用して、複数のフラッシュ・チップ２０５を並列に動作させて、最下層の帯域幅を改善してもよい。例えば、ＰＣ２０１とＦＬＡＳＨチップとの間に８つのチャネルがあり、ＰＣ２０１は、８つのチャネルを介して８つのフラッシュ・チップ２０５に対して並列にデータを読み書きする。

図３に示すように、ダイは、１つ以上のフラッシュ・チップのパッケージである。１つのダイが複数のパネル（ｐａｎｅｌ）を含んでもよく、マルチプレーンＮＡＮＤは性能を効果的に向上させることができる設計である。図３に示すように、１つのダイを２つのプレーンに分割され、２つのプレーンのブロック番号をシングル及びデュアルクロスする。したがって、動作中に、シングル及びデュアルクロス動作を実行して、性能を向上させてもよい。１つのパネルは、複数のブロック（ｂｌｏｃｋ）を含む。１つのブロックは、複数のページ（ｐａｇｅ）を含む。１６ＧＢのフラッシュ・チップが一例として使用される。各４３１４＊８＝３４５１２セルは、論理的にページを形成する。各ページは、４ＫＢのコンテンツと２１８－ＢのＥＣＣパリティ・データを記憶することができる。ページは、ＩＯ動作の最小単位でもある。１２８ページごとにブロックが形成され、２０４８ブロックごとにパネルが形成される。フラッシュ・チップ全体は、２つのパネルが含む。一方のパネルには奇数番号のブロックが記憶され、他方のパネルには偶数番号のブロックが記憶される。２つのプレーンは、同時に動作され得る。これは一例にすぎない。ページ・サイズ、ブロック容量、フラッシュ・チップ容量は、異なる使用を有する。これは、この出願では限定されない。

ホストは、ブロックにデータを書き込む。ブロックがフルであるときに、ＳＳＤ ＰＣ ２０１は、書き込みを継続するために次のブロックを選択してもよい。ページは、書き込まれるデータの最小単位である。換言すれば、ＰＣ２０１は、ページを粒度としてブロックにデータを書き込む。ブロックは、データ消去のための最小単位である。ＰＣは、一度にブロック全体しか消去できない。

ホストは、論理ブロック・アドレス（Ｌｏｇｉｃａｌ Ｂｌｏｃｋ Ａｄｄｒｅｓｓ、ＬＢＡ）を使用してＳＳＤにアクセスする。各ＬＢＡは、セクタを表す（一例として、５１２Ｂが使用される）。ＳＳＤでは、ＰＣは、ページ単位でＳＳＤにアクセスする（一例として、４ＫＢが使用される）。したがって、アプリケーション・サーバがデータを書き込むたびに、ＳＳＤ ＰＣは、データを書き込むページを検索する。ページのアドレスは、物理ブロック・アドレス（Ｐｈｙｓｉｃａｌ Ｂｌｏｃｋ Ａｄｄｒｅｓｓ、ＰＢＡ）と呼ばれる。ＬＢＡからＰＢＡへのマッピングは、ＳＳＤ内に記録される。このようなマッピングにより、ホストが次にＬＢＡのデータを読み出す必要があるときに、ＳＳＤは、フラッシュ・チップ内でデータが読み出される場所を知る。図４は、フラッシュ変換層（Ｆｌａｓｈ Ｔｒａｎｓｌａｔｉｏｎ Ｌａｙｅｒ、ＦＴＬ）の概略図である。ＦＴＬは、プロセッサ２０２のファームウェア内に位置する。図４に示すように、ホストが新しいデータを書き込むたびに、新しいマッピング関係が生成され、そのマッピング関係がＦＴＬに追加（ファーストライト）されるか、又はＦＴＬが変更（オーバライド）される。データを読み出すときに、ＳＳＤは、最初に、ＦＴＬ内のデータのＬＢＡに対応するＰＢＡを検索し、そのＰＢＡに基づいて対応するデータを読み出す。

フラッシュ・チップは、上書きをサポートすることができない。これは、ホストがＬＢＡ上のデータを修正するときに、そのＬＢＡに対応するＰＢＡ上のデータを直接修正することはできないことを意味する。データは新しいＰＢＡに書き込まれ、マッピングがＦＴＬに追加される必要がある。例えば、ＦＴＬのＬＢＡ ＤとＰＢＡ Ｄの間にはマッピング関係があった。ホストがＬＢＡ Ｄのデータを修正することを要求するＩＯ要求を送信するときに、ＳＳＤは、データを書き込む新しい場所（ＰＢＡ Ｅ）を検索し、ＬＢＡ ＤとＰＢＡ Ｅのマッピング関係をＦＴＬに追加する。その結果、ＰＢＡ Ｄ上のデータは無効になる。無効なデータ（ジャンク・データとも呼ばれる）とは、いかなるマッピング関係によって指し示されないデータである。データは新しいマッピング関係によって置き換えられるため、ユーザはデータのＦＬＡＳＨスペースにアクセスできないことがある。アプリケーション・サーバが書き込みを続けると、ＦＬＡＳＨストレージ・スペースは徐々に減少し、最後には使い果たされる。ジャンク・データが適時にクリアされない場合、データは、ホストに書き込むことができない。全てのＳＳＤは、ガベージ・コレクション・メカニズムを有する。基本原理は、いくつかのブロック内の有効なデータを新しいブロックに移動し、ブロックを消去することである。このようにして、新たな利用可能ブロックが生成される。

追加的に、メモリ１２４は、さらにソフトウェア・プログラムを記憶しており、プロセッサ１２３は、メモリ１２４内のソフトウェア・プログラムを実行することによりハード・ディスクを管理してもよい。例えば、ハード・ディスクをストレージ・リソース・プールに抽象化し、次いで、サーバが使用するＬＵＮに分割できる。このＬＵＮは、実際にはサーバ上にあるハード・ディスクである。確かに、一部の集中型ストレージ・システムはファイル・サーバでもあり、サーバに対して共有ファイル・サービスを提供してもよい。

メモリ１２４に記憶されたデータは、ファイル・システムを使用して提示されてもよい。ファイル・システムは、構造化データファイル・ストレージ及び編成形式である。既知のように、コンピュータ内の全てのデータは０と１であり、ハードウェア・メディアに記憶された一連の０１の組み合わせを区別して管理することはできない。したがって、コンピュータは、「ファイル」の概念を使用してデータを編成する。コンピュータは、異なるアプリケーションによって必要とされる構造に基づいて、同じ目的のために使用されるデータを異なるタイプのファイルに編成する。通常、異なるタイプを参照するために異なる接尾辞が使用され、コンピュータは各ファイルに理解しやすく覚えやすい名前を付ける。多数のファイルがあるときに、ファイルは、特定の方法でグループ化される。ファイルの各グループは、同じディレクトリ（又はフォルダ）に記憶される。カタログは、ファイルに加えて、下位レベルのカタログ（サブカタログ又はサブフォルダと呼ばれる）を含んでもよい。全てのファイルとカタログはツリー構造を形成する。ツリー構造は、ファイル・システム（Ｆｉｌｅ Ｓｙｓｔｅｍ）という特別な名前を有する。ＷｉｎｄｏｗｓのＦＡＴ、ＦＡＴ３２、ＮＴＦＳ、ＬｉｎｕｘのＥＸＴ２、ＥＸＴ３、ＥＸＴ４、ＸＦＳ、ＢｔｒＦＳなど、多くのタイプのファイル・システムがある。検索を容易にするために、ルート・ノードからファイルへのレベルごとの降順、カタログ、サブカタログ、及びファイルの名前は、特殊文字（例えば、Ｗｉｎｄｏｗｓ又はＤＯＳでは「￥」が使用され、Ｕｎｉｘのようなシステムでは「／」が使用される）と組み合わされ、このような文字列は、ファイル・パスと呼ばれ、Ｌｉｎｕｘでは「／ｅｔｃ／ｓｙｓｔｅｍｄ／ｓｙｓｔｅｍ．ｃｏｎｆ」であり、Ｗｉｎｄｏｗｓでは「Ｃ：￥Ｗｉｎｄｏｗｓ￥Ｓｙｓｔｅｍ ３２￥ｔａｓｋｍｇｒ．ｅｘｅ」である。パスは、特定のファイルにアクセスするための一意の識別子である。例えば、ＷｉｎｄｏｗｓでのＤ：￥ｄａｔａ￥ｆｉｌｅ．ｅｘｅはファイルのパスであり、パーティションＤのデータカタログ内のｆｉｌｅ．ｅｘｅファイルを示す。

ファイル・システムは、ブロック・デバイス上に構築される。ファイル・システムは、ファイル・パスだけでなく、ファイルを形成するブロック、及びカタログ／サブカタログ情報を記録するブロックも記録する。異なるファイル・システムは、異なる編成構造を有する。管理の容易さから、ハード・ディスクなどのブロック・デバイスは、一般に、複数の論理ブロック・デバイス、すなわち、ハード・ディスク・パーティション（Ｐａｒｔｉｔｉｏｎ）に分割されてもよい。逆に、単一の媒体の容量と性能は、限定される。複数の物理ブロック・デバイスは、ＲＡＩＤ、ＪＢＯＤなどの様々なレベルの技術を使用して、論理ブロック・デバイスに結合され得る。代替的には、ファイル・システムは、これらの論理ブロック・デバイス上に構築されてもよい。いずれの場合も、アプリケーション・サーバ上のアプリケーションは、配下のブロック・デバイス上のアクセス対象のファイルの特定の位置を考慮する必要はなく、ファイルのファイル名／ＩＤのみをファイル・システムに送信する必要がある。ファイル・システムは、ファイル名／ＩＤに基づくクエリを通じてファイル・パスを取得する。

比較的な一般的なファイル・アクセス・プロトコルは、ＮＦＳ、ＣＩＦＳ、ＳＭＢなどであるが、これは、この実施形態では限定されない。

この出願のファイル・システムは、読み出し／書き込み可能ファイル・システムである。読み出し／書き込みファイル・システムは、ストレージ・デバイスにファイルを書き込むか、又はストレージ・デバイスからファイルを読み出すことができるファイル・システムであり、例えば、ＦＡＴ、ＨＰＦＳ、ＮＴＦＳ、ＥＸＴ４及びＦ２ＦＳである。

ファイル・システムは、一般に、メタデータ領域とデータ領域とを含む。メタデータ領域は、スーパーブロックとｉノード（ｉｎｏｄｅ）領域とを含む。メタデータ領域のスーパーブロックは、ファイル・システムの制御情報、データ構造などのコンテンツを含んでもよい。メタデータ領域のｉノード領域は、ファイルの記述情報、例えば、ファイル長及びファイル・タイプを含んでもよい。ファイル・タイプは、例えば、通常アイノード（ｒｅｇｕｌａｒ ｉｎｏｄｅ）、ディレクトリ・ｉノード（ｄｉｒｅｃｔｏｒｙ ｉｎｏｄｅ）、シンボルリンク・ｉノード（ｓｙｍｂｏｌ ｌｉｎｋ ｉｎｏｄｅ）、特殊ｉノード（ｓｐｅｃｉａｌ ｉｎｏｄｅ）である。データ領域に記憶されるデータは、可逆圧縮技術に基づくファイルレベルの圧縮処理を実行して取得されたデータであってもよい。データ領域内のデータは、ディスク・ブロックのセットに基づいて、記憶媒体（例えば、ディスク又はフラッシュ）の物理的な記憶空間に記憶される。同じファイルのデータは、連続したディスク・ブロックに記憶されていてもよいし、クロス方式で不連続なディスク・ブロックに記憶されてもよい。

本出願においてディスク・ブロックの概念を導入したからといって、記憶媒体がディスクに限定されるものではなく、ディスク・ブロックが、記憶媒体の物理的な記憶空間を分割することによって小さな物理的な記憶空間を表すために使用されてもよいことが理解されよう。

もちろん、本出願のストレージ・システムは、スケールアウト・ストレージ・システムをさらに含んでもよい。スケールアウト・ストレージ・システムは、独立した複数のストレージ・ノードにデータが記憶されるシステムである。従来のネットワーク・ストレージ・システムは、全てのデータを記憶するために集中型ストレージ・アレイを使用する。ストレージ・アレイの性能は、システム性能のボトルネックであるだけでなく、信頼性とセキュリティの焦点でもあり、大規模なストレージ・アプリケーションの要件を満たすことができない。

以上、この出願のアプリケーション・シナリオについて簡単に説明した。

上記のストレージ・システムでは、データの読み出し／書き込み能力に基づいて、コンポーネントのレートがソートされており、降順で、中央処理ユニット（ｃｅｎｔｒａｌ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ、ＣＰＵ）＞＞ダブル・データ・レート同期ダイナミック・ランダム・アクセス・メモリ（ｄｏｕｂｌｅ ｄａｔａ ｒａｔｅ ｓｙｎｃｈｒｏｎｏｕｓ ｄｙｎａｍｉｃ ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ、ＤＤＲ ＳＤＲＡＭ）＞フラッシュ・チップ・フラッシュである。ストレージ・システムにおけるデータ・アクセスのボトルネックは、メモリとフラッシュとの間のデータのＩＯ（ｉｎｐｕｔ ｏｕｔｐｕｔ）時間オーバヘッドであることが分かる。

ストレージ・システムの全体的なＩＯ読み出し／書き込み性能を向上させるには、メモリ内のファイルを圧縮する必要がある。メタデータ領域は、ファイル・システム全体に占める割合が小さいため、通常、デバイスの記憶容量を大きく占有する。したがって、フラッシュにデータを書き込むときに、データを圧縮して、圧縮データをフラッシュに書き込むことにより、フラッシュの記憶容量占有を削減し、フラッシュの態様年数を延ばすことができる。

現在、Ｌｉｎｕｘの読み出し／書き込みファイル・システムのＦ２ＦＳ、ジャーナリング・フラッシュ・ファイル・システム・バージョン２（ｊｏｕｒｎａｌｌｉｎｇ Ｆｌａｓｈ ｆｉｌｅ ｓｙｓｔｅｍ ｖｅｒｓｉｏｎ ２、ＪＦＦＳ２）、Ｂツリー・ファイル・システム（Ｂ－ｔｒｅｅ ｆｉｌｅ ｓｙｓｔｅｍ、ＢＴＲＦＳ）など、及びＷｉｎｄｏｗｓの読み出し／書き込みファイル・システムのＮＴＦＳなどに対してデータ圧縮方式が使用されることがある。

圧縮が必要とされるオリジナル・ファイル・データ（又はソース・データと呼ばれる）は、固定サイズの最小圧縮単位（クラスタ）に基づいて圧縮されており、圧縮ファイル・データ（又は圧縮データと呼ばれる）は、ヘッダ・データと圧縮データを含む。ヘッダ・データはファイル・データの属性情報を表すために使用され、圧縮データはファイル・データのコンテンツを表すために使用される。圧縮ファイル・データはフラッシュに保存され、４ＫＢのサイズに調整されます。

例えば、図５の固定入力圧縮モードの模式図に示すように、連続するアドレスを有する４つのデータ・ブロック（ｂｌｏｃｋ）をクラスタ０として圧縮し、ヘッダ・データ（ｈｅａｄｅｒ）＋圧縮データ（ｃｏｍｐｒｅｓｓｅｄ ｄａｔａ）を含む圧縮ファイル・データを取得する。圧縮ファイル・データのサイズが４ＫＢ未満である場合、圧縮ファイル・データは４ＫＢのサイズでフラッシュに記憶される。

図５に示すオリジナル・ファイル・データ（又はソース・データと呼ばれる）のサイズは、４ブロックであり、各ブロックのサイズは、４ＫＢであり、１ブロックが１論理ページであると仮定する。オリジナル・ファイル・データの論理ページは、０、１、２、及び３で番号付けられている。オリジナル・ファイル・データは、圧縮率７５％の圧縮ファイル・データに圧縮され、圧縮ファイル・データのサイズは１２ＫＢである。したがって、圧縮ファイル・データのサイズは、３ブロックである。したがって、圧縮ファイル・データの実際のページは３ページ分であり、１論理ページを読み出すために読み出す必要があるフラッシュの実際のページのサイズを表１に示す。

圧縮ファイル・データをフラッシュに保存した後、オリジナル・ファイル・データの対象論理ページをフラッシュ内で読み出す必要がある場合、圧縮ファイル・データの３ページ分のデータを読み出す必要があり、圧縮ファイル・データを伸長した後でのみ対象論理ページを読み出すことができる。例えば、ランダム読み出しのシナリオでは、論理ページ０のオリジナル・ファイル・データをフラッシュ上で読み出す必要がある場合、３ページ分の圧縮ファイル・データを読み出し、圧縮ファイル・データを伸長した後にのみ、論理ページ０のオリジナル・ファイル・データを正常に読み出すことができる。したがって、データ読み出し効率は、以下のようである。

ランダム読み出しのシナリオでは、図５に示すデータ圧縮方法で取得された圧縮ファイル・データの読み出し効率は、比較的低いことが分かる。

前述の問題を解決するために、この出願の一実施形態は、データ圧縮方法を提供する。この方法では、読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックが取得される。ｍ個のデータ・ブロックが予め設定された圧縮アルゴリズムを使用して圧縮されて、ｎ個の圧縮データ・ブロックを順次取得し、圧縮データ・ブロックの第１の容量は全て同じであり、第１の容量は、圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表す。ｍとｎは、両方とも１以上の正の整数である。

予め設定された圧縮アルゴリズムは、固定出力圧縮モードに対応する圧縮アルゴリズム、例えば（ｌｅｍｐｅｌ－ｚｉｖ ４， ＬＺ４）圧縮アルゴリズムであってもよい。もちろん、予め設定された圧縮アルゴリズムは、別の圧縮アルゴリズムであってもよい。これは、本出願の本実施形態において具体的に限定されない。

例えば、図６に示すように、アプリケーション・シナリオにおいて、ソース・データのサイズが１６ＫＢであり、４ＫＢのデータがデータ・ブロックであり、また、論理ページが例として使用されると仮定する。ソース・データの論理ページは、表２の第１行に示すように、０、１、２、及び３で番号付けされている。

論理ページの連続する１６ＫＢのソース・データが、それぞれ６ＫＢ、７ＫＢ、５ＫＢの３つに分割されると仮定する。圧縮データ・ブロック内の各圧縮データのサイズが４ＫＢとなるまで、予め設定された圧縮アルゴリズム（例えば、ＬＺ４）を使用して３つのデータが圧縮される。

圧縮データ・ブロックは、それぞれ、図６に示す圧縮ページ４、圧縮ページ５、及び圧縮ページ６として番号付けされた３つのデータ・ページを有する。

圧縮ページ４では、論理ページ０のソース・データが全て圧縮されていることが分かる。したがって、論理ページ０は１ページに圧縮される。論理ページ１の一部のソース・データは圧縮ページ４に圧縮され、論理ページ１の他のソース・データは圧縮ページ５に圧縮される。したがって、論理ページ１は２ページに圧縮される。論理ページ２の一部のソース・データは圧縮ページ５に圧縮され、論理ページ２の他のソース・データは圧縮ページ６に圧縮される。したがって、論理ページ２は２ページに圧縮される。圧縮ページ６には、論理ページ３のソース・データが全て圧縮されている。したがって、論理ページ３は１ページに圧縮される。

したがって、ランダム読み出しシナリオでは、任意の１つ以上の論理ページが読み出されることがある。例えば、論理ページ０が読み出されるときに、表２の２行目と２列目に示すように、１つの圧縮ページのみが読み出される必要がある。伸長後、論理ページ０の全てのデータが取得されてもよい。

この場合、読み出し効率は、以下の式２に従って計算されてもよい。

論理ページ３の読み出し効率は、論理ページ０の読み出し効率と同じである。

例えば、論理ページ１が読み出されるときに、表２の２行目と３列目に示すように、３つの圧縮ページが読み出される必要がある。論理ページ１の全てのデータは、圧縮ページ４のデータと圧縮ページ５のデータとが伸長された後のみ取得することができる。

この場合、読み出し効率は、以下の式３に従って計算されてもよい。

論理ページ２の読み出し効率は、論理ページ１の読み出し効率と同じである。

追加的に、４つの論理ページの平均読み出し効率は、以下の式４に従って計算されてもよい。

式２、式３、式４の計算により得られる読み出し効率から、ランダム読み出しシナリオにおいて、図６に示すデータ圧縮方式の読み出し効率は、図５に示すデータ圧縮方式の読み出し効率よりもはるかに高いことが分かる。

この出願のこの実施形態では、固定出力圧縮モードに対応する圧縮アルゴリズムを使用して、読み書き可能なファイル・システムのデータ領域のｍ個のデータ・ブロックを圧縮して、出力される各圧縮データ・ブロックが固定サイズを有するように、同じバイト数のｎ個の圧縮データ・ブロックを順次取得することが分かる。データ・ブロックが読み出されるときに、読み出し効率を効果的に向上させることができ、読み出し増幅係数が小さいランダム読み出しシナリオでデータを読み出すことを保証することができる。

追加的に、図８は、既存の拡張可能な読み出し専用ファイル・システム（ｅｘｔｅｎｄａｂｌｅ ｒｅａｄ－ｏｎｌｙ ｆｉｌｅ ｓｙｓｔｅｍ、ｅｒｏｆｓ）におけるデータ・ブロックのインデックス付け方式を示す。データ・ブロックアドレス配列ｄａｔａ＿ａｄｄｒでは、ブロック・アドレスがアクセスされ、実際のデータ・ブロックのアドレスを指し示す。ｅｒｏｆｓがミラーを作成するときに図５に示す方法を使用してデータを圧縮するときに、ストレージ・デバイス（例えば、ディスク）の構造やファイル・コンテンツが固定されているため、ファイルの修正はサポートされない。しかし、ユーザの実際の動作シナリオでは、ストレージ・デバイス上の多くの圧縮ファイルを頻繁に修正する必要があることがある。ｅｒｏｆｓはこの要件をサポートしていない。

対応するデータ・ブロックは、データ・ブロック・インデックスに基づいて見つけることができ、データ・ブロック・インデックスもｉノード、すなわちメタデータであることが理解されよう。ｉノードは、メタデータを記憶するために使用される領域であり、ファイルに関する属性情報、例えば、ファイルの作成者、作成日、サイズ、データ・ブロックの場所を記憶するために使用される領域である。各ｉノードは番号を有し、オペレーティング・システムは、異なるｉノード番号を使用して異なるファイルを識別する。例えば、表向きは、ユーザは、ファイル名を使用してファイルを開く。実際には、最初に、ファイル名に基づいて対応するｉノード番号を見つけ、ｉノード番号に基づいてｉノード情報を取得し、次いで、ｉノード情報に基づいてデータ・ブロックのアドレスを見つけて、データを読み出す。

すなわち、ｉノードには、ファイルの属性と、ファイルの実際のストレージ場所、すなわちブロック番号（ｂｌｏｃｋ ｎｕｍｂｅｒ）が記録される。各ブロック（一般的なサイズは４ＫＢ）は、ｉノードを使用して検索及び位置特定され得る。ｉノードはＬｉｎｕｘにおけるものであり、Ｕｎｉｘではｖノードと呼ばれる。基本的に、ｉノードは、少なくとも以下の情報、すなわち、（１）ファイル・タイプ、（２）ファイル・アクセス許可、（３）ファイル所有者及びグループ、（４）ファイル・サイズ、（５）リンクの数、すなわち、ｉノードを指し示すファイル名の総数、（６）ファイル状態変更時間（ｃｔｉｍｅ）、最終アクセス時間（ａｔｉｍｅ）、及び最終修正時間（ｍｔｉｍｅ）、（７）ＳＵＩＤ、ＳＧＩＤ、及びＳＢＩＴを含む特別なファイル属性、及び（８）ファイル・コンテンツの真のポイント（ポインタ）を含む。

図８は、既存のデータ・ブロック・インデックス・フォーマットを示す。データ・ブロック・インデックス・フォーマットは、スケーラビリティ、例えば、追記、ブロック予約、又は切り捨て（ｔｒｕｎｃａｔｅ）をサポートしない。追記は、オリジナル・ファイルのコンテンツを削除することなく、オリジナル・ファイルに新たなコンテンツを追加することを示す。ブロック予約は、ディスク・ブロックを割り当てることができる領域をファイル・システムが考え、ファイル・サイズが増加した場合、ディスク・ブロックを予約することを示す。切り詰めは、ファイルを修正、例えば、ファイルを削除又は追加することを示す。

例えば、図８に示すように、データ・ブロック・インデックスは、ｂｌｋ ｅｎｔｒｙで表され、説明の便宜上、簡単にｂｌｋと呼ばれる。ｂｌｋ １は、圧縮データ・ブロック１のインデックスであり、ストレージ・デバイス内の圧縮データ・ブロック１のアドレスがｂｌｋ １に記憶される。ｂｌｋ ２は、圧縮データ・ブロック２のインデックスであり、ストレージ・デバイス内の圧縮データ・ブロック２のアドレスがｂｌｋ ２に記憶される。ｂｌｋ ３は、圧縮データ・ブロック３のインデックスであり、ストレージ・デバイス内の圧縮データ・ブロック３のアドレスがｂｌｋ ３に記憶される。ｂｌｋ ４は、圧縮データ・ブロック４のインデックスであり、ストレージ・デバイス内の圧縮データ・ブロック４のアドレスがｂｌｋ ４に記憶される。したがって、ｂｌｋに記憶されたアドレスに基づいて、ストレージ・デバイス内の圧縮データ・ブロックの場所を決定することができる。

読み出し／書き込みファイル・システムが、書き込み、上書き、事前割り当て、切り捨てなどをサポートすることを可能にするために、この出願の実施形態で提供されるデータ圧縮方法は、ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１インデックスを確立することと、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録することとをさらに含む。ｉは、１以上ｎ以下の正の整数である。ｉは、１以上ｍ以下の正の整数である。第１のインデックスは、ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。第１のインデックスは、記憶媒体におけるｉ番目の圧縮データ・ブロックの記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

属性情報は、
データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と、
データ・ブロックのデータ・ページが有効であるかどうか、すなわち、データ・ページが通常のデータ・ページであるか、又は空のデータ・ページであるかを表すために使用される第２の属性であって、空のデータ・ページは、ブランク・データ・ページと理解され得る、第２の属性と、
データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と、
データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と、
データ・ブロックのデータ・ページが、データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と、
データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と、
データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットであり、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属しないときに、第７の属性の属性値が、データ・ブロックのデータ・ページと、圧縮データ・ブロックの第１の圧縮ページとの間の距離であることを表すために使用される第７の属性とのうちの少なくとも１つを含む。

例えば、図７に示すように、データ・ブロックの第１のインデックスは、データ・ブロック又は圧縮データ・ブロックのアドレスを記憶するｂｌｋエントリと、拡張属性情報を記憶するｅｘｔｅｎｔエントリとを含む。各ｅｘｔｅｎｔエントリは、ｂｌｋエントリと１対１で対応し、各データ・ページは、対応するｅｘｔｅｎｔエントリと、対応するｂｌｋエントリとを有する。

ｅｘｔｅｎｔエントリ・メンバのセットは、以下の方式で表される。

例えば、セットＡに示すように、データ・ブロック・インデックスに含まれるメンバをセットＡに示してもよい。各データ・ページは、対応するセットＡを有することに留意されたい。

セット・メンバの意味は、以下のように記載される。
ｉｓ＿ｒｅｓｅｒｖｅｄは第１の属性である。
ｉｓ＿ｖａｌｉｄは第２の属性である。
ｆｉｒｓｔ＿ｐａｇｅは第３の属性である。
ｃｒｏｓｓ＿ｂｌｏｃｋは第４の属性である。
ｉｓ＿ｃｏｍｐｒｅｓｓは第５の属性である。
ｂｌｋｉｄｘは、第６の属性である。
ｏｆｓは第７の属性である。

図６に示す方法を用いて、読み出し／書き込みファイル・システムにおいてデータを圧縮するときに、ストレージ・デバイス上の圧縮ファイルが修正されてもよいように、図７に示すデータ・ブロックのインデックスに含まれる属性が修正されてもよいことが分かる。

以下、この出願の実施形態で提供されるデータ圧縮方法について、特定の例を参照して記載する。

図９Ａ及び図９は、この出願の一実施形態による、データ圧縮方法の概略フローチャートである。図９Ａ及び図９Ｂに示すように、方法は、以下のステップを含む。

Ｓ９０１：読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックを取得し、ｍは１以上の正の整数である。

ｍ個のデータ・ブロックは、ライト・バックされる必要があるデータ・ブロックとして理解されよう。ライト・バックとは、書き込み動作中に、データが最初にキャッシュのためにメモリに書き込まれるが、すぐにはストレージ・デバイス（例えばディスク）に書き込まれないことを意味してもよい。メモリにキャッシュされたデータは、いくつかの特定の条件又は動作（例えば、リフレッシュ機構やシンク（ｓｙｎｃ）動作）の下でのみ、ストレージ・デバイスに書き込まれる。

Ｓ９０２：ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得し、圧縮データ・ブロックの第１の容量は全て同じであり、第１の容量は、圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表し、ｎは１以上の正の整数である。

予め設定された圧縮アルゴリズムは、ＬＺ４圧縮アルゴリズムであってもよいし、もちろん、固定出力を有する別の圧縮アルゴリズムであってもよい。これは、本出願の本実施形態において具体的に限定されない。

ｍは任意の正の整数である。例えば、ｍは４であるか、ｍは１０であるか、又はｍは２０である。

Ｓ９０２は、具体的には、以下のように実装されてもよい。

Ｓ９０２１：ｍ個のデータ・ブロックの全てのデータ・ブロックを予め設定された順序で第１のセットに順次割り当てる。

予め設定された順序は、連続するストレージ：アドレスの順序、すなわち、ｍ個のデータ・ブロックの連続する順序であってもよい。

第１のセットは、最小圧縮可能単位（クラスタ）と呼ばれてもよい。換言すれば、第１のセットは、最小圧縮可能データ・ブロック・セット、例えば、図６に示す６ＫＢデータ・ブロック・セット、７ＫＢデータ・ブロック・セット、５ＫＢデータ・ブロック・セットである。

例えば、ｍ個のデータ・ブロックは、記憶媒体において連続するアドレスのセグメントにマッピングされる。データ・ブロックを始点とし、記憶媒体にマッピングされたデータ・ブロックのアドレス順に従って、固定サイズのデータ・セットが順次分割される。図６に示すように、データ・ブロック０とデータ・ブロック１の１／２データとで６ＫＢのデータ・セットを形成し、データ・ブロック１の１／２データとデータ・ブロック２の３／４データとブランク・データ・ページとで７ＫＢのデータ・セットを形成し、データ・ブロック２の１／４データとデータ・ブロック３とで５ＫＢのデータ・セットを形成する。

Ｓ９０２２：第１のセットのｊ個のデータ・ブロックのデータ容量が、第１のセットの定格容量と等しいかどうかを決定し、ｊは１以上ｍ以下の正の整数である。ｊ個のデータ・ブロックのデータ容量が第１のセットの定格容量と等しくない場合、Ｓ９０２１が実行されるか、又はｊ個のデータ・ブロックのデータ容量が第１のセットの定格容量と等しい場合、Ｓ９０２３が実行される。

Ｓ９０２３：第１のセットのｊ個のデータ・ブロックに対して、指定された圧縮閾値に基づいて固定圧縮動作を実行し、ｉ番目の圧縮データ・ブロックを取得する。

指定された圧縮閾値は、圧縮率を表すために使用される。例えば、指定された圧縮閾値の数式は、指定された圧縮閾値＝合計データ長－合計データ長＊圧縮率であってもよい。

Ｓ９０２４：ｊ個のデータ・ブロックの合計データ長が、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和よりも大きいかどうかを決定する。ｊ個のデータ・ブロックの合計データ長が、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和よりも大きい場合、Ｓ９０３が実行される。ｊ個のデータ・ブロックの合計データ長が、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和よりも大きくない場合、ソース・データ・ページがフラッシュにサブミットされる。

Ｓ９０３：ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立し、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録し、ｉは１以上ｎ以下の正の整数であり、ｊは１以上ｍ以下の正の整数である。

圧縮データ・ブロックを圧縮するときに、その圧縮データ・ブロックに対応するデータ・ブロックの各々のインデックスが確立される。

第１のインデックスは、ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

例えば、Ｌｉｎｕｘのｆ２ｆｓ読み出し／書き込みファイル・システムを例として使用し、ｆ２ｆｓにおけるデータ・ブロックの第１のインデックス／フォーマットは、以下のようであってもよい。

第１のインデックスに含まれる属性情報のデータ構造は、以下のようであってもよい。例えば、エントリ・データ構造は、

であり、属性情報は、
データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と（ｉｓ＿ｒｅｓｅｒｖｅｄ）、
データ・ブロックのデータ・ページが有効であるかどうかを表すために使用される第２の属性と（ｉｓ＿ｖａｌｉｄ）、
データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と（ｆｉｒｓｔ＿ｐａｇｅ）、
データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と（ｃｒｏｓｓ＿ｂｌｏｃｋ）、
データ・ブロックのデータ・ページが、データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と（ｉｓ＿ｃｏｍｐｒｅｓｓ）、
データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と（ｂｌｋｉｄｘ）、
データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットであり、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属しないときに、第７の属性の属性値が、データ・ブロックのデータ・ページと、圧縮データ・ブロックの第１の圧縮ページとの間の距離であることを表すために使用される第７の属性と（ｏｆｓ）のうちの少なくとも１つを含んでもよい。

具体的かつ可能な実装では、図１０Ａ及び図１０Ｂは、この出願の一実施形態による、データ・ブロック・インデックスを更新する概略フローチャートである。図１０Ａ及び図１０Ｂに示すように、属性情報は、第３の属性（ｆｉｒｓｔ＿ｐａｇｅ）及び第７の属性（ｏｆｓ）を含んでもよく、Ｓ９０３は、具体的には、以下のように実装されてもよい。

Ｓ１０３１：ｊ個のデータ・ブロックの各々のデータ・ページが、ｉ番目の圧縮データ・ブロックの第１の圧縮ページであるかどうかを決定する。ｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページであるときに、第３の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページではないときに、第３の属性の属性値に０を代入することを行う。

Ｓ１０３２：第３の属性の属性値が１であるときに、第７の属性の属性値を、圧縮データ・ブロックに対応する第１のセットにおけるオフセットに更新する。

Ｓ１０３３：第３の属性の属性値が０であるときに、第７の属性の属性値を、データ・ブロックのデータ・ページとｉ番目の圧縮データ・ブロックの第１の圧縮ページとの間の距離に更新する。

もちろん、属性情報は、第４の属性（ｃｒｏｓｓ＿ｂｌｏｃｋ）をさらに含んでいてもよく、Ｓ１０３は、具体的には以下のように実装されてもよい。

Ｓ１０３４：２つの圧縮ブロックの圧縮データ・ページにｊ個のデータ・ブロックの各々のデータ・ページが含まれているかどうかを決定する。ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれる場合、第４の属性の属性値に１を代入するか、又はｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれない場合、第４の属性の属性値に０を代入する。

もちろん、属性情報は、第２の属性（ｉｓ＿ｖａｌｉｄ）をさらに含んでいてもよく、Ｓ１０３は、具体的には以下のように実装されてもよい。

Ｓ１０３５：ｊ個のデータ・ブロックの各々のデータ・ページが有効であるかどうかを決定する。ｊ個のデータ・ブロックの各々のデータ・ページが有効である場合、第２の属性の属性値に１を代入し、ｊ個のデータ・ブロックの各々のデータ・ページが無効である場合、第２の属性の属性値に０を代入する。

もちろん、属性情報は、第６の属性（ｂｌｋｉｄｘ）をさらに含んでいてもよく、Ｓ１０３は、具体的には以下のように実装されてもよい。

Ｓ１０３６：ｍ個のデータ・ブロックの各データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを決定する。

圧縮は、メモリのｍ個のデータ・ブロックの記憶場所のシーケンスに従って、最小固定圧縮単位（例えば、第１のセット）のサイズを使用して実行される。１回目の圧縮が完了した（すなわち、第１の圧縮データ・ブロックが取得された）ときに、第１の圧縮データ・ブロックに対応する完了データ・ブロックのデータ・ページは、全て第１の圧縮ブロックのインデックス位置にある。例えば、第１の圧縮データ・ブロックに対応するデータ・ブロックは、データ・ブロック０のデータの一部、データ・ブロック１、データ・ブロック２、及びデータ・ブロック３を含む。第１の圧縮データ・ブロックに対応する完全データ・ブロックは、データ・ブロック０、データ・ブロック１、及びデータ・ブロック２である。したがって、データ・ブロック０、データ・ブロック１、データ・ブロック２のデータ・ページは、第１の圧縮データ・ブロックのインデックス位置にある。

第３の属性に付加する必要がある第７の属性に加えて、他の属性に対応するデータ・ブロック・インデックス更新手順は互いに独立していることに留意されたい。第１の属性、第２の属性、第４の属性、第５の属性、及び第６の属性に対応するデータ・ブロック・インデックス更新手順のシーケンスは、この出願のこの実施形態においては特に限定されない。

例えば、図１１に示すように、ｍ個のデータ・ブロックは、データ・ブロック０（すなわち、ブロック０）、データ・ブロック１（すなわち、ブロック１）、データ・ブロック２（すなわち、ブロック２）、及びデータ・ブロック３（すなわち、ブロック３）を含むと仮定される。ブロック０、ブロック１、ブロック２、及びブロック３を使用して連続するアドレスのセグメントがメモリにマッピングされる。圧縮中に、ブロック０、ブロック１、ブロック２、及びブロック３使用してメモリ上にマッピングされた連続するアドレスのセグメントのシーケンス（例えば、図１１の左から右への圧縮方向）に従って、最小固定圧縮単位（例えば、第１のセット）のサイズを使用して圧縮が実行されるときに、
ブロック０の一部とブロック１が最小固定圧縮単位（例えば４ＫＢ）に達したときに、１回目の圧縮が実行されて、第１の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ ０）を取得する。この場合、ブロック０のデータ・ブロック・インデックスは、表３に示すように確立される。

図１０Ａ及び図１０Ｂを参照すると、ブロック０のデータ・ページが、第１の圧縮データ・ブロックの第１の圧縮ページにあることが分かる。したがって、ｆｉｒｓｔ＿ｐａｇｅに１が代入される。ブロック０のデータ・ページは、第１の圧縮データ・ブロックの第１の圧縮ページにのみある。したがって、ｃｒｏｓｓ＿ｂｌｏｃｋに０が代入される。ブロック０のデータ・ページの第１の圧縮データ・ブロック内のインデックス・アドレスは、第１の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ ０）の番号である。したがって、ｂｌｋｉｄｘに０が代入される。ブロック０のデータ・ページは、第１の圧縮データ・ブロックの第１の圧縮ページにあり、ブロック０に対応する第１のセットにおけるブロック０のオフセットは０である。したがって、ｏｆｓに０が代入される。ブロック０のデータ・ページは、有効なデータ・ページである。したがって、ｉｓ＿ｖａｌｉｄに１が代入される。

ブロック１の残りの部分、ブロック２の一部及びブロック３が最小固定圧縮単位（例えば４ＫＢ）に達したときに、２回目の圧縮が実行されて、第２の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ １）を取得する。この場合、ブロック１とブロック２のデータ・ブロック・インデックスは、表４に示すように確立される。

図１０Ａ及び図１０Ｂを参照すると、ブロック１のデータ・ページが、第２の圧縮データ・ブロックの第１の圧縮ページにあることが分かる。したがって、ｆｉｒｓｔ＿ｐａｇｅに１が代入される。ブロック１のデータ・ページは、第１の圧縮データ・ブロックの圧縮ページと第２の圧縮データ・ブロックの圧縮ページとにある。したがって、ｃｒｏｓｓ＿ｂｌｏｃｋに１が代入される。ブロック１のデータ・ページの第２の圧縮データ・ブロック内のインデックス・アドレスは、第２の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ １）の番号である。したがって、ｂｌｋｉｄｘに１が代入される。ブロック１のデータ・ページは、第２の圧縮データ・ブロックの第１の圧縮ページにあり、データ・ブロックのセットにおけるブロック１のオフセットはＯｆｓ１である。したがって、ｏｆｓ１にＯｆｓ１が代入される。ブロック１のデータ・ページは、有効なデータ・ページである。したがって、ｉｓ＿ｖａｌｉｄに１が代入される。

同様に、ブロック２のデータ・ページは、第２の圧縮データ・ブロックの第１の圧縮ページにはない。したがって、ｆｉｒｓｔ＿ｐａｇｅに０が代入される。ブロック２のデータ・ページは、第２の圧縮データ・ブロックの圧縮ページにのみある。したがって、ｃｒｏｓｓ＿ｂｌｏｃｋに０が代入される。ブロック２のデータ・ページの第２の圧縮データ・ブロック内のインデックス・アドレスは、第２の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ １）の番号である。したがって、ｂｌｋｉｄｘに１が代入される。ブロック２のデータ・ページは、第２の圧縮データ・ブロックの第１の圧縮ページにはなく、ブロック２のデータ・ページと第１の圧縮データ・ブロックの第１の圧縮ページとの間の距離は１である。したがって、ｏｆｓに１が代入される。ブロック２のデータ・ページは、有効なデータ・ページである。したがって、ｉｓ＿ｖａｌｉｄに１が代入される。

ブロック３の残りの部分が最小固定圧縮単位（例えば４ＫＢ）に達したときに、３回目の圧縮が実行されて、第３の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ ２）を取得する。この場合、ブロック３のデータ・ブロック・インデックスは、表５に示すように確立される。

図１０Ａ及び図１０Ｂを参照すると、ブロック３のデータ・ページが、第３の圧縮データ・ブロックの第１の圧縮ページにあることが分かる。したがって、ｆｉｒｓｔ＿ｐａｇｅに１が代入される。ブロック１のデータ・ページは、第２の圧縮データ・ブロックの圧縮ページと第３の圧縮データ・ブロックの圧縮ページとにある。したがって、ｃｒｏｓｓ＿ｂｌｏｃｋに１が代入される。ブロック１のデータ・ページの第３の圧縮データ・ブロック内のインデックス・アドレスは、第２の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ ２）の番号である。したがって、ｂｌｋｉｄｘに２が代入される。ブロック３のデータ・ページは、第３の圧縮データ・ブロックの第１の圧縮ページにあり、データ・ブロックのセットにおけるブロック３のオフセットはＯｆｓ２である。したがって、ｏｆｓ１にＯｆｓ２が代入される。ブロック３のデータ・ページは、有効なデータ・ページである。したがって、ｉｓ＿ｖａｌｉｄに１が代入される。

Ｓ９０４：ｍ個のデータの圧縮が完了したかどうかを決定する。圧縮が完了すると、圧縮データ・ブロックの圧縮ページがデバイスにサブミットされる。圧縮が完了していない場合は、Ｓ９０２を実行する。

いくつかの実施形態では、図１２は、この出願の一実施形態による、データ圧縮方法の概略フローチャートである。図１２に示すように、Ｓ９０２が実行される前に、この出願のこの実施形態で提供されるデータ圧縮方法は、以下のステップを含む。

Ｓ９０５：上書き対象データの第２のセットを取得する。

Ｓ９０６：上書き対象データの第２のセットが圧縮データ・ブロックを含むかどうかを決定する。上書き対象データの第２のセットが圧縮データ・ブロックを含む場合、Ｓ９０７が実行されるか、又は上書き対象データの第２のセットが圧縮データ・ブロックを含まない場合、既存のデータの上書き処理が実行される。

第２のセットは、ｐ個の圧縮データ・ブロックを含んでもよく、ｐは１以上の正の整数である。

Ｓ９０７：ｐ個の圧縮データ・ブロックにおける第１の対象圧縮データの圧縮ページと、第１の対象圧縮データ・ブロックの圧縮ページに対応するｑ個のデータ・ブロックとを取得し、ｑは１以上の正の整数である。

Ｓ９０８：ｑ個のデータ・ブロックにおいて、ｑ個のデータ・ブロック内の第１の対象データ・ブロックの場所オフセットを決定する。

具体的には、第２のセットの各圧縮データ・ブロックのインデックス・アドレスが読み出され、圧縮データ・ブロックが伸長されて、圧縮データ・ブロックに対応するデータ・ブロックを取得する。次いで、ｑ個のデータ・ブロックの各々の場所オフセットが決定される。

Ｓ９０９：第１の圧縮ページと、圧縮ページにおける第１のデータ・ブロックのオフセット位置とに基づいて、第１のデータ・ブロックのデータ・ページを取得する。

Ｓ９１０：第１の対象データ・ブロックのデータ・ページが、上書き対象データのデータ・ページであると決定する。

Ｓ９１１：第１のデータ・ブロックのデータ・ページを第２のデータ・ブロックで上書きする。

Ｓ９１２：第１のセットに第２のデータ・ブロックを割り当てる。

要するに、読み出し／書き込みファイル・システムｆ２ｆｓでは、この出願のこの実施形態で提供される固定出力圧縮モードを使用して、指定されたｓｏファイル、ｖｄｅｘファイル、ｏｄｅｘファイルなどを圧縮することにより、例えば、電子デバイス上に４０個のアプリケーションをインストールするプロセスにおいて、各アプリケーションが平均１２％の時間的効果を得ることができるという有益な効果が達成され得る。アプリケーションのインストール中、ｓｏファイルには追記手順を有し、ｖｄｅｘファイルとｏｄｅｘファイルの両方は、上書き手順を有する。４０個のアプリケーションの平均ブート・ゲインは、固定入力圧縮モードでの圧縮データのブート・ゲインよりも８％高くなる。

この出願のこの実施形態で提供されるデータ圧縮方法によれば、前述のデータ圧縮方法を使用してデータが圧縮された後、データを読み出す必要がある。図１４は、この出願の一実施形態による、データ読み出し手順の概略フローチャートである。図１４に示すように、データの読み出し手順は、以下のようである。

Ｓ１４１：第１のデータ・ブロックの属性情報を含む第１のインデックスを読み出して、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックス・アドレスを取得し、第１のインデックスが、第１のデータ・ブロックの属性情報を含む。

前述の実施形態では、第１のデータ・ブロックの属性情報は、第１の属性～第７の属性のうちの少なくとも１つを含んでもよい。例えば、第１のデータ・ブロックの属性情報は、第３の属性（ｆｉｒｓｔ＿ｐａｇｅ）、第４の属性（ｃｒｏｓｓ＿ｂｌｏｃｋ）、第６の属性（ｂｌｋｉｄｘ）、及び第７の属性（ｏｆｓ）を含む。

上書きシナリオ及び読み出し専用シナリオでは、第１のデータ・ブロックは、図１３に示すデータ・ブロック２（ブロック２）であると仮定する。ブロック２のｏｆｓ、ｃｒｏｓｓ＿ｂｌｏｃｋ、ｂｌｋｉｄｘなどの属性情報を読み出し、ブロック２に対応する第１の圧縮データ・ブロックのインデックス・アドレスを取得する。具体的には、表４が依然として使用される。ブロック２のｏｆｓに代入された値が１であることが読み出されたときに、ブロック２のデータ・ページが第２の圧縮データ・ブロックの第１の圧縮ページにはなく、ブロック２のデータ・ページと第１の圧縮データ・ブロックの第１の圧縮ページとの間の距離が１として取得されてもよいと決定されてもよい。次いで、ブロック２のｃｒｏｓｓ＿ｂｌｏｃｋに代入された値が０であることが読み出されたときに、ブロック２のデータ・ページが第１の圧縮データ・ブロックの圧縮ページのみにり、別の圧縮データ・ブロックの圧縮ページにはないと決定されてもよい。次いで、ブロック２のｂｌｋｉｄｘに代入された値が１であることが読み出されたときに、ブロック２のデータ・ページの第１の圧縮データ・ブロックにおけるインデックス・アドレスが第１の圧縮データ・ブロックの番号であると決定されてもよく、すなわち、第１の圧縮データ・ブロックのインデックス・アドレスが１として取得されてもよい。

Ｓ１４２：第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックスを読み出す。

Ｓ１４３：第１の圧縮データ・ブロックのインデックスに基づいて、第１の圧縮データ・ブロックを伸長して、第１の圧縮データ・ブロックに対応する複数のデータ・ブロックを取得し、複数のデータ・ブロックは、第１のデータ・ブロックを含む。

具体的には、第１の圧縮データ・ブロックは、第１の圧縮データ・ブロックのインデックスに基づいてデバイス上で見出される。第１の圧縮データ・ブロックが見出された後、第１の圧縮データ・ブロックが解析され、解析された複数のデータ・ブロックが取得される。例えば、図１３に示すように、第１の圧縮データ・ブロックをｃｏｍｐｒｅｓｓ ｂｌｋ １とし、ｃｏｍｐｒｅｓｓ ｂｌｋ １を解析した後、以下のデータ、すなわち、データ・ブロック１（ブロック１）のデータの一部、データ・ブロック２（ブロック２）、及びデータ・ブロック３（ブロック３）のデータの一部が取得される。

Ｓ１４４：複数の伸長データ・ブロックのうちの第１のデータ・ブロックのオフセットを決定する。

具体的には、第１のデータ・ブロックの属性情報に基づいて、第１のデータ・ブロックが図１３に示すデータ・ブロック２（ブロック２）であることが分かる。図１３に示すように、圧縮データｂｌｋ １から解析された複数のデータ・ブロックにおけるブロック２のオフセット（ｄｓｔｏｆｓ）の表現は以下のようである。

式中、ｄｓｔｏｆｓは、圧縮ブロック１から解析された複数のデータ・ブロックにおけるブロック２のオフセットを示し、ｂｌｏｃｋ＿ｓｉｚｅは、データ・ブロックの長さを示し、ｏｆｓ１は、第７の属性の属性値を示し、ｏｆｓ１％ｂｌｏｃｋ＿ｓｉｚｅは、余りを示す。

Ｓ１４５：複数の伸長データ・ブロックのうちの第１のデータ・ブロックのオフセットに基づいて、第１のデータ・ブロックのデータを取得する。

前述の例は、依然として使用される。第１のデータ・ブロックは、ブロック２である。図１３及び表４に示すように、ブロック２のデータを取得されてもよい。

具体的には、この可能な設計における通信システムは、図９に示すデータ圧縮方法で各デバイスの機能を実行するように構成されているため、前述のデータ圧縮方法と同じ効果を達成することができる。

図１５は、この出願の一実施形態によるデータ圧縮装置を示す。データ圧縮装置１５００は、読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックを取得するように構成されている第１の取得ユニットであって、ｍは１以上の正の整数である、第１の取得ユニット１５０１と、ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得するように構成されている圧縮ユニットであって、圧縮データ・ブロックの第１の容量は全て同じであり、第１の容量は、圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表し、ｎは１以上の正の整数である、圧縮ユニット１５０２と、ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立し、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録するように構成されている更新ユニット１５０３と、を含む。ｉは１以上ｎ以下の正の整数であり、ｊは１以上ｍ以下の正の整数である。第１のインデックスは、ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

具体的かつ可能な実装では、圧縮ユニット１５０２は、ｍ個のデータ・ブロックの全てのデータ・ブロックを予め設定された順序で第１のセットに順次割り当てるように構成されている。第１のセットのｊ個のデータ・ブロックのデータ容量が、第１のセットの定格容量と等しいときに、ｊ個のデータ・ブロックに対して、指定された圧縮閾値に基づいて圧縮動作が実行されて、ｉ番目の圧縮データ・ブロックを取得する。

具体的かつ可能な実装では、更新ユニット１５０３は、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和が、ｊ個のデータ・ブロックの合計データ長以下であるときに、ｊ個のデータ・ブロックの各々の第１のインデックスを確立するように構成されている。

具体的かつ可能な実装では、属性情報は、属性情報は、データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と、データ・ブロックのデータ・ページが有効であるかどうかを表すために使用される第２の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と、データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と、データ・ブロックのデータ・ページが、データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と、データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットであり、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属しないときに、第７の属性の属性値が、データ・ブロックのデータ・ページと、圧縮データ・ブロックの第１の圧縮ページとの間の距離であることを表すために使用される第７の属性とのうちの少なくとも１つを含む。

具体的かつ可能な実装では、属性情報は、第３の属性を含み、更新ユニット１５０３は、ｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページであるときに、第３の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページではないときに、第３の属性の属性値に０を代入することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第７の属性を含み、更新ユニット１５０３は、第３の属性の属性値が１であるときに、第７の属性の属性値を、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットに更新することか、又は第３の属性の属性値が０であるときに、第７の属性の属性値を、データ・ブロックのデータ・ページと圧縮データ・ブロックの第１の圧縮ページとの間の距離に更新することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第４の属性を含み、更新ユニット１５０３は、ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるときに、第４の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれないときに、第４の属性の属性値に０を代入することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第２の属性を含み、更新ユニットは、ｊ個のデータ・ブロックの各々のデータ・ページが有効であるときに、第２の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが無効であるときに、第２の属性の属性値に０を代入することを行うようにさらに構成されている。

いくつかの可能な実施態様では、本装置は、上書き対象データの第２のセットを取得するように構成されている第２の取得ユニットであって、第２のセットは、ｐ個の圧縮データ・ブロックを含み、ｐは１以上の正の整数である、第２の取得ユニット１５０４と、ｐ個の圧縮データ・ブロックにおける第１の対象圧縮データの圧縮ページと、第１の対象圧縮データ・ブロックの圧縮ページに対応するｑ個のデータ・ブロックとを取得するように構成されている第３の取得ユニットであって、ｑは１以上の正の整数である、第３の取得ユニット１５０５と、ｑ個のデータ・ブロックにおいて、ｑ個のデータ・ブロック内の第１の対象データ・ブロックの場所オフセットを決定するように構成されている第１の決定ユニット１５０６と、第１の対象データ・ブロックのデータ・ページが、上書き対象データのデータ・ページであると決定するように構成されている第２の決定ユニット１５０７と、をさらに含む。

いくつかの可能な実装では、本装置は、第１のデータ・ブロックの第１のインデックスを読み出して、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックス・アドレスを取得するように構成されている第１の読み出しユニットであって、第１のインデックスが第１のデータ・ブロックの属性情報を含む、第１の読み出しユニットと、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックスを読み出すように構成されている第２の読み出しユニットと、第１の圧縮データ・ブロックのインデックスに基づいて第１の圧縮データ・ブロックを伸長して、第１の圧縮データ・ブロックに対応する複数のデータ・ブロックを取得するように構成されている伸長ユニットであって、複数のデータ・ブロックは第１のデータ・ブロックを含む、伸長ユニットと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットを決定するように構成されている第３の決定ユニットと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットに基づいて第１のデータ・ブロックのデータを取得するように構成されている第３の取得ユニットと、をさらに含む。

具体的かつ可能な実装では、第１のインデックスは、記憶媒体におけるｉ番目の圧縮データ・ブロックの記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

この出願の実施形態で提供されるデータ圧縮方法によれば、データ・ブロックが読み出されるときに、読み出し効率を効果的に向上させることができ、読み出し増幅係数が小さいランダム読み出しシナリオでデータを読み出すことを保証することができる。追加的に、データ・ブロックのインデックスに含まれる属性が修正されてもよく、そのため、ストレージ・デバイス上の圧縮ファイルが修正されてもよい。この出願の実施形態では、既存の読み出し／書き込みファイル・システムにおける圧縮ソリューションのランダム読み出し増幅の問題を解決し、固定出力圧縮方式を有する既存のファイル・システムがデータ及びメタデータ更新をサポートできないという問題を解決することが分かる。

この出願の一実施形態は、デバイスをさらに提供する。デバイスは、前述の実装のいずれか１つに従ってステップを実行するように構成されたユニット、又は前述の実装のいずれか１つに従ってステップを実行するように構成されたユニットを含む。

この出願の一実施形態は、命令を含むコンピュータ可読記憶媒体をさらに提供する。命令がコンピュータ上で動作するときに、コンピュータは、前述の方法のいずれか１つを実行することが可能となる。

この出願の一実施形態は命令を含むコンピュータ・プログラム製品を提供する。コンピュータ・プログラム製品がコンピュータ上で動作するときに、コンピュータは、前述の方法のいずれか１つを行うことが可能となる。

この出願の一実施形態は、チップをさらに提供する。チップは、プロセッサ及びインターフェース回路を含む。インターフェース回路は、プロセッサに結合される。プロセッサは、コンピュータ・プログラム又は命令を実行して、前述の方法を実装するように構成されている。インターフェース回路は、チップの外側の別のモジュールと通信するように構成されている。

この出願の説明では、別段の定めがない限り、「／」は「又は」を意味する。例えば、Ａ／Ｂは、Ａ又はＢを表してもよい。本明細書における「及び／又は」の用語は、関連するオブジェクト間の関連付け関係のみを説明し、３つの関係があり得ることを示す。例えば、Ａ及び／又はＢは、以下の３つのケース、すなわち、Ａのみが存在すること、Ａ及びＢの両方が存在すること、並びにＢのみが存在することを表してもよい。追加的に、「少なくとも１つ」とは、１つ以上を意味し、「複数の」とは、２つ以上を意味する。「第１」、「第２」などの文言は、数又は実行シーケンスを制限せず、「第１」、「第２」などの文言は、明確な差異を示さない。

この出願の説明では、「例」、「例えば」などの文言は、例、例示又は説明を与えることを表すために使用される。本出願において、「例」又は「例えば」として記載される任意の実施形態又は設計スキームは、他の実施形態又は設計スキームよりも好ましいものとして、又はより多くの利点を有するものとして説明されるべきではない。正確には、「例」、「例えば」などの文言は、関連概念を特定の方式で提示することを意図している。

実装に関する前述の説明は、便宜的かつ簡潔な説明を目的として、まさに前述の機能モジュールへの分割が説明のための例として使用されることを当業者が明確に理解することを可能にする。実際のアプリケーションでは、前述の機能は、必要に応じて実装のために異なる機能モジュールに割り当てられ得る。換言すれば、装置の内部構造は、上記の機能の全部又は一部を実装するために、異なる機能モジュールに分割される。

この出願で提供されるいくつかの実施形態では、開示された装置及び方法は、他の方式で実装され得ると理解されたい。例えば、記載された装置の実施形態は、一例にすぎない。例えば、モジュール又はユニット分割は、単に論理関数分割であり、実際の実装の際には他の分割であってもよい。例えば、複数のユニット又はコンポーネントが別の装置に組み合わされたり、統合されてもよいし、いくつかの特徴が無視されたり、実行されなくてもよい。追加的に、表示又は議論された相互結合、直接結合、又は通信接続は、いくつかのインターフェースを使用することによって実装されてもよい。装置又はユニット間の間接結合又は通信接続は、電子的、機械的、又は他の形態において実装されてもよい。

別個の部分として記載されるユニットは、物理に分離されていても、されていなくてもよく、ユニットとして表示される部分は、１つ以上の物理ユニットであってもよいし、１つの場所に位置していてもよいし、複数の場所に分散されてもよい。ユニットの一部又は全部は、実施形態の解決策の目的を達成するために実際の要件に基づいて選択されてもよい。

追加的に、本出願の実施形態における機能ユニットは、１つの処理ユニットに統合されてもよく、ユニットの各々は、物理的に単独で存在してもよく、又は２つ以上のユニットが１つのユニットに統合される。統合されたユニットは、ハードウェアの形態で実装されてもよいし、ソフトウェア機能ユニットの形態で実装されてもよい。

この出願は、特定の特徴及びその実施形態を参照して記載されているが、この出願の精神及び範囲から逸脱することなく、様々な修正及び組み合わせがそれらに対して行われてもよいことは明らかである。これに対応して、明細書及び添付の図面は、添付の特許請求の範囲によって定義されるこの出願の例示的な説明にすぎず、この出願の範囲をカバーする修正、変形、組み合わせ又は均等のいずれか又は全てと考えられる。当業者が、この出願の精神及び範囲から逸脱することなく、この出願に様々な修正及び変形を行うことができることが明らかである。この出願は、以下の特許請求の範囲及びそれらの均等の技術によって画定される保護の範囲内にあることを条件として、この出願のこれらの修正及び変形をカバーすることを意図している。

前述の説明は、この出願の単に具体的な実装に過ぎないが、この出願の保護範囲を制限することを意図したものではない。この出願に開示された技術的範囲内で、当業者によって容易に理解することができる変更又は代替は、この出願の保護範囲に含まれるものとする。したがって、この出願の保護範囲は、特許請求の範囲の保護範囲に従うものとする。

この出願は、２０２１年６月１６日に中国国家知識産権局に出願された「ＤＡＴＡ ＣＯＭＰＲＥＳＳＩＯＮ ＭＥＴＨＯＤ ＡＮＤ ＡＰＰＡＲＡＴＵＳ」と題する中国特許出願第２０２１１０６６７８８２．７号に対する優先権を主張し、その全体が参照により本明細書に組み込まれる。

この出願は、データ圧縮技術の分野に関係し、特に、データ圧縮方法及び装置に関係する。

ストレージ・システムの全体的な入出力（ｉｎｐｕｔ ｏｕｔｐｕｔ、ＩＯ）の読み出し／書き込み性能を向上させるために、メモリ内のファイルを圧縮する必要がある。現在、Ｌｉｎｕｘの読み出し／書き込みファイル・システムのＦ２ＦＳ、ジャーナリング・フラッシュ・ファイル・システム・バージョン２（ｊｏｕｒｎａｌｌｉｎｇ Ｆｌａｓｈ ｆｉｌｅ ｓｙｓｔｅｍ ｖｅｒｓｉｏｎ ２、ＪＦＦＳ２）、Ｂツリー・ファイル・システム（Ｂ－ｔｒｅｅ ｆｉｌｅ ｓｙｓｔｅｍ、ＢＴＲＦＳ）など、及びＷｉｎｄｏｗｓの読み出し／書き込みファイル・システムのＮＴＦＳなどがある。メタデータ領域は、ファイル・システム全体に占める割合が小さいため、データ領域が、通常、デバイスの記憶容量を大きく占有する。したがって、データ領域のデータを圧縮することにより、入出力ＩＯのサイズを縮小し、ＩＯの読み込み／書き込み性能を向上させることができる。

既存のデータ圧縮方法では、圧縮が必要とされるオリジナル・ファイル・データ（又はソース・データと呼ばれる）は、一般に、固定サイズの最小圧縮単位に基づいて圧縮されており、圧縮ファイル・データ（又は圧縮データと呼ばれる）は、ヘッダ・データと圧縮データを含んでもよい。ヘッダ・データはファイル・データの属性情報を表すために使用され、圧縮データはファイル・データのコンテンツを表すために使用される。次いで、圧縮ファイル・データは記憶媒体に保存される。しかし、既存の読み出し／書き込みファイル・システムの圧縮ソリューションでは、ランダム読み出し増幅の問題があり、読み出し効率が低い。

この出願の実施形態は、読み出し／書き込みファイル・システムのランダム読み出し増幅の問題を解決し、読み出し効率を向上させるデータ圧縮方法及び装置を提供する。

第１の態様によれば、この出願の一実施形態は、データ圧縮方法を提供する。本方法は、電子デバイスによって実行されてもよいし、電子デバイス内に位置するコンポーネント（例えば、チップ、チップ・システム、又はプロセッサ）によって実行されてもよい。以下、本方法が電子デバイスによって実行される例を使用して説明を提供する。本方法は、電子デバイスが、読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックを取得することであって、ｍは１以上の正の整数である、ことを含む。電子デバイスは、ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得し、圧縮データ・ブロックの第１の容量は全て同じであり、第１の容量は、圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表し、ｎは１以上の正の整数である。電子デバイスは、ｎ個の圧縮データ・ブロックのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立し、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録する。ｉは１以上ｎ以下の正の整数であり、ｊは１以上ｍ以下の正の整数である。第１のインデックスは、ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

この出願の実施形態で提供されるデータ圧縮方法によれば、データ・ブロックが読み出されるときに、読み出し効率を効果的に向上させることができ、読み出し増幅係数が小さいランダム読み出しシナリオでデータを読み出すことを保証することができる。追加的に、データ・ブロックのインデックスに含まれる属性が修正されてもよく、そのため、ストレージ・デバイス上の圧縮ファイルが修正されてもよい。この出願の実施形態では、既存の読み出し／書き込みファイル・システムにおける圧縮ソリューションのランダム読み出し増幅の問題を解決し、固定出力圧縮方式を有する既存のファイル・システムがデータ及びメタデータ更新をサポートできないという問題を解決することが分かる。

具体的かつ可能な実装では、ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得することは、具体的には、ｍ個のデータ・ブロック内の全てのデータ・ブロックを予め設定された順序で第１のセットに順次割り当てることである。第１のセットのｊ個のデータ・ブロックのデータ容量が、第１のセットの定格容量と等しいときに、ｊ個のデータ・ブロックに対して、指定された圧縮閾値に基づいて圧縮動作が実行されて、ｉ番目の圧縮データ・ブロックを取得する。

ｎ個の圧縮データ・ブロックのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、具体的には、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和が、ｊ個のデータ・ブロックの合計データ長以下であるときに、ｊ個のデータ・ブロックの各々の第１のインデックスを確立することである。

具体的かつ可能な実装では、属性情報は、属性情報は、データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と、データ・ブロックのデータ・ページが有効であるかどうかを表すために使用される第２の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と、データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と、データ・ブロックのデータ・ページが、データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と、データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットであり、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属しないときに、第７の属性の属性値が、データ・ブロックのデータ・ページと、圧縮データ・ブロックの第１の圧縮ページとの間の距離であることを表すために使用される第７の属性とのうちの少なくとも１つを含む。

具体的かつ可能な実装では、属性情報は第３の属性を含み、ｎ個の圧縮データ・ブロックのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、具体的には、ｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページであるときに、第３の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページではないときに、第３の属性の属性値に０を代入することである。

具体的かつ可能な実装では、属性情報は、第７の属性を含み、本方法は、第３の属性の属性値が１であるときに、第７の属性の属性値を、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットに更新することか、又は第３の属性の属性値が０であるときに、第７の属性の属性値を、データ・ブロックのデータ・ページと圧縮データ・ブロックの第１の圧縮ページとの間の距離に更新することをさらに含む。

具体的かつ可能な実装では、属性情報は第４の属性を含み、ｎ個の圧縮データ・ブロックのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、具体的には、ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるときに、第４の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれないときに、第４の属性の属性値に０を代入することである。

具体的かつ可能な実装では、属性情報は第２の属性を含み、ｎ個の圧縮データ・ブロックのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、具体的には、ｊ個のデータ・ブロックの各々のデータ・ページが有効であるときに、第２の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが無効であるときに、第２の属性の属性値に０を代入することである。

いくつかの可能な実装では、本方法は、ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得することの前に、上書き対象データの第２のセットを取得することであって、第２のセットは、ｐ個の圧縮データ・ブロックを含み、ｐは１以上の正の整数である、ことと、ｐ個の圧縮データ・ブロックにおける第１の対象圧縮データ・ブロックの圧縮ページと、第１の対象圧縮データ・ブロックの圧縮ページに対応するｑ個のデータ・ブロックとを取得することであって、ｑは１以上の正の整数である、ことと、ｑ個のデータ・ブロックにおいて、ｑ個のデータ・ブロック内の第１の対象データ・ブロックの場所オフセットを決定することと、第１の対象データ・ブロックのデータ・ページが、上書き対象データのデータ・ページであると決定することと、をさらに含む。

具体的かつ可能な実装では、第１のインデックスは、記憶媒体におけるｉ番目の圧縮データ・ブロックの記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

いくつかの可能な実装では、本方法は、第１のデータ・ブロックの第１のインデックスを読み出して、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックス・アドレスを取得することであって、第１のインデックスが第１のデータ・ブロックの属性情報を含む、ことと、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックスを読み出すことと、第１の圧縮データ・ブロックのインデックスに基づいて第１の圧縮データ・ブロックを伸長して、第１の圧縮データ・ブロックに対応する複数のデータ・ブロックを取得することであって、複数のデータ・ブロックは第１のデータ・ブロックを含む、ことと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットを決定することと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットに基づいて第１のデータ・ブロックのデータを取得することと、をさらに含む。

第２の態様によれば、この出願の一実施形態は、データ圧縮装置を提供する。本装置は、読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックを取得するように構成されている第１の取得ユニットであって、ｍは１以上の正の整数である、第１の取得ユニットと、ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得するように構成されている圧縮ユニットであって、圧縮データ・ブロックの第１の容量は全て同じであり、第１の容量は、圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表し、ｎは１以上の正の整数である、圧縮ユニットと、ｎ個の圧縮データ・ブロックのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立し、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録するように構成されている更新ユニットと、を含む。
ｉは１以上ｎ以下の正の整数であり、ｊは１以上ｍ以下の正の整数である。第１のインデックスは、ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

この出願の実施形態で提供されるデータ圧縮方法によれば、データ・ブロックが読み出されるときに、読み出し効率を効果的に向上させることができ、読み出し増幅係数が小さいランダム読み出しシナリオでデータを読み出すことを保証することができる。追加的に、データ・ブロックのインデックスに含まれる属性が修正されてもよく、そのため、ストレージ・デバイス上の圧縮ファイルが修正されてもよい。この出願の実施形態では、既存の読み出し／書き込みファイル・システムにおける圧縮ソリューションのランダム読み出し増幅の問題を解決し、固定出力圧縮方式を有する既存のファイル・システムがデータ及びメタデータ更新をサポートできないという問題を解決することが分かる。

具体的かつ可能な実装では、圧縮ユニットは、ｍ個のデータ・ブロックの全てのデータ・ブロックを予め設定された順序で第１のセットに順次割り当てるように構成されている。第１のセットのｊ個のデータ・ブロックのデータ容量が、第１のセットの定格容量と等しいときに、ｊ個のデータ・ブロックに対して、指定された圧縮閾値に基づいて圧縮動作が実行されて、ｉ番目の圧縮データ・ブロックを取得する。

具体的かつ可能な実装では、更新ユニットは、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和が、ｊ個のデータ・ブロックの合計データ長以下であるときに、ｊ個のデータ・ブロックの各々の第１のインデックスを確立するように構成されている。

具体的かつ可能な実装では、属性情報は、属性情報は、データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と、データ・ブロックのデータ・ページが有効であるかどうかを表すために使用される第２の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と、データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と、データ・ブロックのデータ・ページが、データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と、データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットであることを表すために使用される第７の属性とのうちの少なくとも１つを含む。データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属しないときに、第７の属性の属性値が、データ・ブロックのデータ・ページと圧縮データ・ブロックの第１の圧縮ページとの間の距離である。

具体的かつ可能な実装では、属性情報は、第３の属性を含み、更新ユニットは、ｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページであるときに、第３の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページではないときに、第３の属性の属性値に０を代入することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第７の属性を含み、更新ユニットは、第３の属性の属性値が１であるときに、第７の属性の属性値を、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットに更新することか、又は第３の属性の属性値が０であるときに、第７の属性の属性値を、データ・ブロックのデータ・ページと圧縮データ・ブロックの第１の圧縮ページとの間の距離に更新することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第４の属性を含み、更新ユニットは、ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるときに、第４の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれないときに、第４の属性の属性値に０を代入することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第２の属性を含み、更新ユニットは、ｊ個のデータ・ブロックの各々のデータ・ページが有効であるときに、第２の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが無効であるときに、第２の属性の属性値に０を代入することを行うようにさらに構成されている。

いくつかの可能な実施態様では、本装置は、上書き対象データの第２のセットを取得するように構成されている第２の取得ユニットであって、第２のセットは、ｐ個の圧縮データ・ブロックを含み、ｐは１以上の正の整数である、第２の取得ユニットと、ｐ個の圧縮データ・ブロックにおける第１の対象圧縮データ・ブロックの圧縮ページと、第１の対象圧縮データ・ブロックの圧縮ページに対応するｑ個のデータ・ブロックとを取得するように構成されている第３の取得ユニットであって、ｑは１以上の正の整数である、第３の取得ユニットと、ｑ個のデータ・ブロックにおいて、ｑ個のデータ・ブロック内の第１の対象データ・ブロックの場所オフセットを決定するように構成されている第１の決定ユニットと、第１の対象データ・ブロックのデータ・ページが、上書き対象データのデータ・ページであると決定するように構成されている第２の決定ユニットと、をさらに含む。

具体的かつ可能な実装では、第１のインデックスは、記憶媒体におけるｉ番目の圧縮データ・ブロックの記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

いくつかの可能な実装では、本装置は、第１のデータ・ブロックの第１のインデックスを読み出して、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックス・アドレスを取得するように構成されている第１の読み出しユニットであって、第１のインデックスが第１のデータ・ブロックの属性情報を含む、第１の読み出しユニットと、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックスを読み出すように構成されている第２の読み出しユニットと、第１の圧縮データ・ブロックのインデックスに基づいて第１の圧縮データ・ブロックを伸長して、第１の圧縮データ・ブロックに対応する複数のデータ・ブロックを取得するように構成されている伸長ユニットであって、複数のデータ・ブロックは第１のデータ・ブロックを含む、伸長ユニットと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットを決定するように構成されている第３の決定ユニットと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットに基づいて第１のデータ・ブロックのデータを取得するように構成されている第３の取得ユニットと、をさらに含む。

第３の態様によれば、この出願の一実施形態は、第１の態様の方法を実行するように構成されているデバイスを提供する。

第４の態様によれば、この出願の一実施形態は、コンピュータ可読記憶媒体を提供する。コンピュータ可読記憶媒体は、コンピュータ命令を記憶する。コンピュータ命令が電子デバイス上で実行されるときに、電子デバイスは、第１の態様のデータ圧縮方法を実行することが可能となる。

第５の態様によれば、本出願の一実施形態は、コンピュータ・プログラムを提供する。プログラムがプロセッサによって呼び出されるときに、第１の態様のデータ圧縮方法は、実行される。

第６の態様によれば、この出願の一実施形態は、１つ以上のプロセッサを含むチップ・システムを提供する。１つ以上のプロセッサが命令を実行するときに、１つ以上のプロセッサは、第１の態様のデータ圧縮方法を実行する。

この出願における技術的特徴、技術的解決策、有益な効果、又は類似の文言の説明は、全ての特徴及び利点が任意の個々の実施形態において実装可能であることを示唆しないと理解されたい。反対に、特徴又は有益な効果の説明は、少なくとも１つの実施形態が特定の技術的特徴、技術的解決策、又は有益な効果を含むことを意味すると理解されよう。したがって、この明細書における技術的特徴、技術的解決策、又は有益な効果の説明は、必ずしも同じ実施形態に属さなくてもよい。さらに、実施形態に記載される技術的特徴、技術的解決策、及び有益な効果は、任意の適切な方式で組み合わされてもよい。当業者は、実施形態が、特定の実施形態において、１つ以上の特定の技術的特徴、技術的解決策、又は有益な効果を伴わずに実装されてもよいと理解してもよい。他の実施形態では、全ての実施形態を反映するわけではない特定の実施形態において、追加の技術的特徴及び有益な効果が識別されてもよい。

この出願一実施形態による、オペレーティング・システムの構成ブロック図である。

この出願の一実施形態による、ストレージ・システムの構造の概略図である。

図１ｂのストレージ・システムのソリッド・ステート・ディスクの構造の概略図である。

図２のソリッド・ステート・ディスクのフラッシュ・チップの構造の概略図である。

図３のフラッシュ・チップに対応するフラッシュ変換層の概略図である。

固定入力圧縮モードの概略図である。

この出願の一実施形態による、固定出力圧縮モードの概略図である。

この出願の一実施形態による、データ・ブロック・インデックスの概略図である。

既存の拡張可能な読み出し専用ファイル・システムにおけるデータ・ブロック・インデックスの概略図である。

この出願の一実施形態による、データ圧縮方法の概略フローチャートである。 この出願の一実施形態による、データ圧縮方法の概略フローチャートである。

この出願の一実施形態による、データ・ブロック・インデックスを更新する概略フローチャートである。 この出願の一実施形態による、データ・ブロック・インデックスを更新する概略フローチャートである。

この出願の一実施形態による、データ圧縮中のデータ・ブロック・インデックス関係の概略図である。

この出願の一実施形態による、別のデータ圧縮方法の概略フローチャートである。

この出願の一実施形態による、上書き又は読み出し手順におけるデータ・ブロック・インデックス関係の概略図である。

この出願の一実施形態による、データ読み出し手順の概略フローチャートである。

この出願の一実施形態による、データ圧縮装置の構造の概略図である。

この出願の説明で言及される「含む」、「有する」、及び任意の他のそれらの変化形の用語は、非排他的な包含をカバーすることを意図している。例えば、一連のステップ又はユニットを含む、プロセス、方法、システム、製品又はデバイスは、列挙されたステップ又はユニットに限定されず、任意選択で、列挙されていない別のステップ又はユニットをさらに含むか、あるいは任意選択で、プロセス、方法、製品又はデバイスに固有の別のステップ又はユニットをさらに含む。

この出願の実施形態では、「例」又は「例えば」の文言は、例、例示又は説明を与えることを表すために使用されることに留意されたい。本出願において、「例」又は「例えば」として記載される任意の実施形態又は設計スキームは、他の実施形態又は設計スキームよりも好ましいものとして、又はより多くの利点を有するものとして説明されるべきではない。正確には、「例」、「例えば」などの文言は、関連概念を特定の方式で提示することを意図している。

この出願の実施態様の説明では、別段特定されない限り、「複数」とは、２以上を意味する。本明細書における「及び／又は」の用語は、関連するオブジェクト間の関連付け関係のみを記載し、３つの関係があり得ることを示す。例えば、Ａ及び／又はＢは、以下の３つのケース、すなわち、Ａのみが存在すること、Ａ及びＢの両方が存在すること、並びにＢのみが存在することを表してもよい。

理解を簡単にするために、この出願の実施形態で使用され得る関係する用語及び概念を最初に記載する。

図１ａは、オペレーティング・システムの構成ブロック図である。

オペレーティング・システム（ｏｐｅｒａｔｉｎｇ ｓｙｓｔｅｍ、略してＯＳ）は、コンピュータのハードウェア及びソフトウェアリソースを管理するコンピュータ・プログラムであり、例えば、ｕｎｉｘ、Ｗｉｎｄｏｗｓ、及びＬｉｎｕｘである。オペレーティング・システムは、基本的なトランザクション、例えば、メモリの管理と構成、システム・リソースの供給と需要の優先度の決定、入出力デバイスの制御、ネットワークの運用、及びファイル・システムの管理を処理する必要がある。オペレーティング・システムはまた、ユーザがシステムと対話するための動作インターフェースを提供する。

オペレーティング・システム・カーネルは、ほとんどのオペレーティング・システムのコア部分である。オペレーティング・システム・カーネルは、オペレーティング・システム内のストレージ・デバイス、ファイル、周辺機器、システム・リソースを管理するために使用される部分を含み、システムのプロセス、メモリ、デバイス・ドライバ、ファイル及びネットワーク・システムを管理し、オペレーティング・システムの性能や安定性を決定する。オペレーティング・システム・カーネルは、ハードウェア抽象化層、ディスク及びファイル・システム制御、マルチタスクなどの機能を提供するシステム・ソフトウェアである。オペレーティング・システム・カーネルは、多くのアプリケーションに対してコンピュータ・ハードウェアへの安全なアクセスを提供し、アプリケーションがコンピュータ・ハードウェアの一部に対していつ動作を実行するか、及びそれにかかる時間を決定することができる。コンピュータ・ハードウェア上での直接動作は非常に複雑であるため、オペレーティング・システム・カーネルは、これらの動作を完了するためのハードウェア抽象化方法のセットを提供することができる。

ファイル・システムは、オペレーティング・システム・カーネルのコア・モジュール、すなわち、メイン・コンポーネントである。ファイル・システムは、ストレージ・デバイス上のファイルを編成し、ファイル情報を管理及び記憶し、主にユーザのためのファイルを作成し、ファイルを記憶、読み出し、修正、ダンプを行い、ファイル・アクセスを制御し、ユーザがファイルを使用しなくなったときにファイルをキャンセルする方法である。

ファイル・システムは、カーネル内のファイルの抽象表現を提供し、ファイルを物理的なストレージ・デバイス（ディスク、ハード・ディスクなど）にマッピングし、ストレージ・デバイス上のファイルの物理アドレスをユーザが見ることができるパス及びファイル名にマッピングし、ファイル・データの迅速な読み出し、修正、及び永続化を容易にする。

ファイル・システムには、読み出し／書き込みファイル・システム及び読み出し専用ファイル・システムを含む。読み出し／書き込みファイル・システムは、ファイルをストレージ・デバイスに書き込むか、又はファイルをストレージ・デバイスから読み出すことができるファイル・システムであり、例えば、ファイル・アロケーション・テーブル（ｆｉｌｅ ａｌｌｏｃａｔｉｏｎ ｔａｂｌｅ、ＦＡＴ）、ハイ・パフォーマンス・ファイル・システム（ｈｉｇｈ ｐｅｒｆｏｒｍａｎｃｅ ｆｉｌｅ ｓｙｓｔｅｍ、ＨＰＦＳ）、ニュー・テクノロジー・ファイル・システム（ｎｅｗ ｔｅｃｈｎｏｌｏｇｙ ｆｉｌｅ ｓｙｓｔｅｍ、ＮＴＦＳ）、フォース・エクテンデット・ファイル・システム（ｆｏｕｒｔｈ ｅｘｔｅｎｄｅｄ ｆｉｌｅ ｓｙｓｔｅｍ、ＥＸＴ４）、フラッシュ・フレンドリー・ファイル・システム（ｆｌａｓｈ ｆｒｉｅｎｄｌｙ ｆｉｌｅ ｓｙｓｔｅｍ、Ｆ２ＦＳ）である。読み出し専用ファイル・システムは、ファイルをストレージ・デバイスから読み出すことのみが可能であり、ファイルをストレージ・デバイスに書き込むことができないファイル・システムであり、例えば、拡張可能な読み出し専用ファイル・システム（ｅｘｔｅｎｄａｂｌｅ ｒｅａｄ－ｏｎｌｙ ｆｉｌｅ ｓｙｓｔｅｍ、ＥＲＯＦＳ）である。

この出願をより明確にするために、最初に、この出願のアプリケーション・シナリオについて記載する。

図１ｂは、ストレージ・システムの構造の概略図である。

図１ｂに示すアプリケーション・シナリオでは、ユーザは、アプリケーションを使用してデータにアクセスする。これらのアプリケーションを実行するコンピュータは、「アプリケーション・サーバ」と呼ばれる。アプリケーション・サーバ１００は、物理マシンであってもよいし、仮想マシンであってもよい。物理アプリケーション・サーバは、デスクトップコンピュータ、サーバ、ノートブック・コンピュータ、及びモバイル・デバイスを含むが、これらに限定されない。アプリケーション・サーバは、データにアクセスするためにファイバ・チャネル・スイッチ１１０を使用してストレージ・システムにアクセスする。しかし、スイッチ１１０は、任意選択であり、アプリケーション・サーバ１００はまた、ネットワークを使用してストレージ・システム１２０と直接通信するようにしてもよい。代替的には、ファイバ・チャネル・スイッチ１１０は、Ｅｔｈｅｒｎｅｔスイッチ、ＩｎｆｉｎｉＢａｎｄスイッチ、ＲｏＣＥ（ＲＤＭＡ ｏｖｅｒ Ｃｏｎｖｅｒｇｅｄ Ｅｔｈｅｒｎｅｔ）スイッチなどで置き換えられてもよい。

図１ｂに示すストレージ・システム１２０は、集中型ストレージ・システムである。集中型ストレージ・システムは、１つ以上のメイン・デバイスを含む中央ノードである。データは中央ノードに記憶され、システム全体の全てのデータ処理サービスは、中央ノードに展開される。換言すれば、集中型ストレージ・システムでは、端末又はクライアントはデータの入出力のみを担当し、全てのデータ記憶及び制御処理は中央ノードによって完了される。集中型ストレージ・システムは統合ポータルを特徴とし、外部デバイスからの全てのデータはこのポータルを通過する。ポータルは、集中型ストレージ・システムのエンジン１２１である。エンジン１２１は、集中型ストレージ・システムのコア・コンポーネントであり、エンジン１２１には、ストレージ・システムの多くの高度な機能が実装されている。

図１ｂに示すように、エンジン１２１は、１つ以上のコントローラを有する。図１ｂでは、エンジンが２つのコントローラを含む例が説明のために使用される。コントローラ０とコントローラ１の間にはミラー・チャネルがある。したがって、コントローラ０がデータをコントローラ０のメモリ１２４に書き込んだ後、コントローラ０は、ミラー・チャネルを介してデータのコピーをコントローラ１に送信してもよく、コントローラ１は、そのコピーをコントローラ１のローカル・メモリ１２４に記憶する。したがって、コントローラ０とコントローラ１とは互いにバックアップを行う。コントローラ０が故障したときに、コントローラ１は、コントローラ０のサービスを引き継いでもよい。コントローラ１が故障したときに、コントローラ０は、コントローラ１のサービスを引き継いでもよく、ハードウェア故障によるストレージ・システム１２０全体の使用不能を回避する。４つのコントローラがエンジン１２１に配設されるときに、ミラー・チャネルが任意の２つのコントローラ間に存在し、したがって、任意の２つのコントローラが互いにバックアップする。

エンジン１２１は、フロントエンド・インターフェース１２５とバックエンド・インターフェース１２６とをさらに含み、フロントエンド・インターフェース１２５は、アプリケーション・サーバ１００と通信して、アプリケーション・サーバ１００にストレージ・サービスを提供するように構成されている。バックエンド・インターフェース１２６は、ハード・ディスク１３４と通信して、ストレージ・システムの容量を拡張するように構成されている。エンジン１２１は、バックエンド・インターフェース１２６を介してさらに多くのハード・ディスク１３４に接続して、大きなストレージ・リソース・プールを形成してもよい。

エンジン１２１とディスク・エンクロージャ１３０との間の通信プロトコルのタイプに基づいて、ディスク・エンクロージャ１３０は、ＳＡＳディスク・エンクロージャ、ＮＶＭｅディスク・エンクロージャ、ＩＰディスク・エンクロージャ、又は別のタイプのディスク・エンクロージャであってもよい。ＳＡＳディスク・エンクロージャはＳＡＳ ３．０プロトコルを使用し、各エンクロージャは２５のＳＡＳハード・ディスクをサポートする。エンジン１２１は、オンボードＳＡＳインターフェース又はＳＡＳインターフェース・モジュールを介してディスク・エンクロージャ１３０に接続される。ＮＶＭｅディスク・エンクロージャは、完全なコンピュータ・システムのようなものである。ＮＶＭｅハード・ディスクがＮＶＭｅディスク・エンクロージャに挿入されている。追加的に、ＮＶＭｅディスク・エンクロージャは、ＲＤＭＡポートを介してエンジン１２１に接続される。

ハードウェア的には、図１ｂに示すように、コントローラ０は、少なくともプロセッサ１２３とメモリ１２４とを含む。プロセッサ１２３は、ストレージ・システム（サーバ又は他のストレージ・システム）の外部からのデータ・アクセス要求を処理するように構成されており、かつストレージ・デバイス内部で生成された要求を処理するように構成されている中央処理ユニット（ｃｅｎｔｒａｌ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ、ＣＰＵ）である。例えば、プロセッサ１２３は、フロントエンド・インターフェース１２５を使用して、アプリケーション・サーバ１００から送信されたデータ書き込み要求を受信するときに、そのデータ書き込み要求のデータをメモリ１２４に一時的に記憶する。メモリ１２４内のデータの総量が特定の閾値に達するときに、プロセッサ１２３は、バックエンド・インターフェースを使用して、メモリ１２４に記憶されたデータを、永続的な記憶のためにハード・ディスク１３４に送信する。

メモリ１２４は、プロセッサと直接データを交換する内部メモリである。データは、いつでも高速にメモリに読み書きされ得、メモリは、オペレーティング・システム又は他の実行中のプログラムの一時的なデータ・メモリとして機能する。メモリは、少なくとも２つのタイプのメモリを含み、例えば、メモリは、ランダム・アクセス・メモリであってもよい。例えば、ランダム・アクセス・メモリは、ダイナミック・ランダム・アクセス・メモリ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ＤＲＡＭ）、又はストレージ・クラス・メモリ（Ｓｔｏｒａｇｅ Ｃｌａｓｓ Ｍｅｍｏｒｙ、ＳＣＭ）である。ＤＲＡＭは、半導体メモリであり、ほとんどのランダム・アクセス・メモリ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ＲＡＭ）と同様に、揮発性メモリ（ｖｏｌａｔｉｌｅ Ｍｅｍｏｒｙ）デバイスである。ＳＣＭは、従来のストレージ・デバイスの特徴とメモリの特徴の両方を組み合わせた複合ストレージ技術を使用する。ストレージ・クラス・メモリは、ハード・ディスクに比べて高速な読み書きを提供することができるが、アクセス速度の観点からＤＲＡＭよりも遅く、コストの観点からはＤＲＡＭよりも安い。しかし、ＤＲＡＭ及びＳＣＭは、実施形態における説明のための例示にすぎない。メモリは、別のランダム・アクセス・メモリ、例えば、スタティック・ランダム・アクセス・メモリ（Ｓｔａｔｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ＳＲＡＭ）をさらに含んでもよい。追加的に、メモリ１２４は、デュアル・インライン・メモリ・モジュール（Ｄｕａｌ Ｉｎ－ｌｉｎｅ Ｍｅｍｏｒｙ Ｍｏｄｕｌｅ、略してＤＩＭＭ）、すなわち、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）で構成されたモジュールであってもよいし、ソリッド・ステート・ディスク（Ｓｏｌｉｄ Ｓｔａｔｅ Ｄｉｓｋ、ＳＳＤ）であってもよい。実際のアプリケーションでは、コントローラ０には、複数のメモリ１２４と、異なるタイプのメモリ１２４とが構成されていてもよい。この実施形態では、メモリ１１３の数及びタイプは限定されない。追加的に、メモリ１２４は、停電保護機能を有するように構成されてもよい。停電保護機能とは、停電後にシステムの電源を再投入してもメモリ１２４に記憶されたデータが失われないことを意味する。停電保護機能を有するメモリは、不揮発性メモリと呼ばれる。

例えば、メモリ１２４及びハード・ディスク１３４は、いずれもソリッド・ステート・ドライブ（英語：Ｓｏｌｉｄ－ｓｔａｔｅ ｄｒｉｖｅ又はＳｏｌｉｄ－ｓｔａｔｅ ｄｉｓｋ、略してＳＳＤ）であってもよく、主にフラッシュ（ＮＡＮＤ Ｆｌａｓｈ）を不揮発性メモリとして使用するストレージ・デバイスである。図２に示すように、ＳＳＤ２００は、ＮＡＮＤフラッシュと、プライマリ・コントローラ（略してＰＣ）２０１とを含む。ＮＡＮＤフラッシュは、データを記憶するように構成されている複数のフラッシュ・チップ２０５を含む。ＰＣ２０１は、ＳＳＤの頭脳であり、データ記憶の管理、ＳＳＤの性能及び耐用年数の維持などのいくつかの複雑なタスクを担当する。ＰＣ２０１は、組み込み型のマイクロチップであり、ＳＳＤの動作要求を全て送信するためのコマンドセンタのような機能を有するプロセッサ２０２を含む。例えば、プロセッサ２０２は、バッファ内のファームウェアを使用して、データの読み書き、ガーベジ・コレクション、ウェア・レベリングなどの機能を実行してもよい。

ＳＳＤ ＰＣ２０１は、ホスト・インターフェース２０４と、いくつかのチャネル・コントローラとをさらに含む。ホスト・インターフェース２０４は、ホストと通信するように構成されている。本明細書におけるホストとは、サーバ、パーソナル・コンピュータ、アレイ・コントローラなどの任意のデバイスを指す。ＰＣ２０１は、複数のチャネル・コントローラを使用して、複数のフラッシュ・チップ２０５を並列に動作させて、最下層の帯域幅を改善してもよい。例えば、ＰＣ２０１とＦＬＡＳＨチップとの間に８つのチャネルがあり、ＰＣ２０１は、８つのチャネルを介して８つのフラッシュ・チップ２０５に対して並列にデータを読み書きする。

図３に示すように、ダイは、１つ以上のフラッシュ・チップのパッケージである。１つのダイが複数のパネル（ｐａｎｅｌ）を含んでもよく、マルチプレーンＮＡＮＤは性能を効果的に向上させることができる設計である。図３に示すように、１つのダイを２つのプレーンに分割され、２つのプレーンのブロック番号をシングル及びデュアルクロスする。したがって、動作中に、シングル及びデュアルクロス動作を実行して、性能を向上させてもよい。１つのパネルは、複数のブロック（ｂｌｏｃｋ）を含む。１つのブロックは、複数のページ（ｐａｇｅ）を含む。１６ＧＢのフラッシュ・チップが一例として使用される。各４３１４＊８＝３４５１２セルは、論理的にページを形成する。各ページは、４ＫＢのコンテンツと２１８－ＢのＥＣＣパリティ・データを記憶することができる。ページは、ＩＯ動作の最小単位でもある。１２８ページごとにブロックが形成され、２０４８ブロックごとにパネルが形成される。フラッシュ・チップ全体は、２つのパネルが含む。一方のパネルには奇数番号のブロックが記憶され、他方のパネルには偶数番号のブロックが記憶される。２つのプレーンは、同時に動作され得る。これは一例にすぎない。ページ・サイズ、ブロック容量、フラッシュ・チップ容量は、異なる使用を有する。これは、この出願では限定されない。

ホストは、ブロックにデータを書き込む。ブロックがフルであるときに、ＳＳＤ ＰＣ ２０１は、書き込みを継続するために次のブロックを選択してもよい。ページは、書き込まれるデータの最小単位である。換言すれば、ＰＣ２０１は、ページを粒度としてブロックにデータを書き込む。ブロックは、データ消去のための最小単位である。ＰＣは、一度にブロック全体しか消去できない。

ホストは、論理ブロック・アドレス（Ｌｏｇｉｃａｌ Ｂｌｏｃｋ Ａｄｄｒｅｓｓ、ＬＢＡ）を使用してＳＳＤにアクセスする。各ＬＢＡは、セクタを表す（一例として、５１２Ｂが使用される）。ＳＳＤでは、ＰＣは、ページ単位でＳＳＤにアクセスする（一例として、４ＫＢが使用される）。したがって、アプリケーション・サーバがデータを書き込むたびに、ＳＳＤ ＰＣは、データを書き込むページを検索する。ページのアドレスは、物理ブロック・アドレス（Ｐｈｙｓｉｃａｌ Ｂｌｏｃｋ Ａｄｄｒｅｓｓ、ＰＢＡ）と呼ばれる。ＬＢＡからＰＢＡへのマッピングは、ＳＳＤ内に記録される。このようなマッピングにより、ホストが次にＬＢＡのデータを読み出す必要があるときに、ＳＳＤは、フラッシュ・チップ内でデータが読み出される場所を知る。図４は、フラッシュ変換層（Ｆｌａｓｈ Ｔｒａｎｓｌａｔｉｏｎ Ｌａｙｅｒ、ＦＴＬ）の概略図である。ＦＴＬは、プロセッサ２０２のファームウェア内に位置する。図４に示すように、ホストが新しいデータを書き込むたびに、新しいマッピング関係が生成され、そのマッピング関係がＦＴＬに追加（ファーストライト）されるか、又はＦＴＬが変更（オーバライド）される。データを読み出すときに、ＳＳＤは、最初に、ＦＴＬ内のデータのＬＢＡに対応するＰＢＡを検索し、そのＰＢＡに基づいて対応するデータを読み出す。

フラッシュ・チップは、上書きをサポートすることができない。これは、ホストがＬＢＡ上のデータを修正するときに、そのＬＢＡに対応するＰＢＡ上のデータを直接修正することはできないことを意味する。データは新しいＰＢＡに書き込まれ、マッピングがＦＴＬに追加される必要がある。例えば、ＦＴＬのＬＢＡ ＤとＰＢＡ Ｄの間にはマッピング関係があった。ホストがＬＢＡ Ｄのデータを修正することを要求するＩＯ要求を送信するときに、ＳＳＤは、データを書き込む新しい場所（ＰＢＡ Ｅ）を検索し、ＬＢＡ ＤとＰＢＡ Ｅのマッピング関係をＦＴＬに追加する。その結果、ＰＢＡ Ｄ上のデータは無効になる。無効なデータ（ジャンク・データとも呼ばれる）とは、いかなるマッピング関係によって指し示されないデータである。データは新しいマッピング関係によって置き換えられるため、ユーザはデータのＦＬＡＳＨスペースにアクセスできないことがある。データが連続的にホストに書き込まれると、ＦＬＡＳＨストレージ・スペースは徐々に減少し、最後には使い果たされる。ジャンク・データが適時にクリアされない場合、データは、ホストに書き込むことができない。全てのＳＳＤは、ガベージ・コレクション・メカニズムを有する。基本原理は、いくつかのブロック内の有効なデータを新しいブロックに移動し、ブロックを消去することである。このようにして、新たな利用可能ブロックが生成される。

追加的に、メモリ１２４は、さらにソフトウェア・プログラムを記憶しており、プロセッサ１２３は、メモリ１２４内のソフトウェア・プログラムを実行することによりハード・ディスクを管理してもよい。例えば、ハード・ディスクをストレージ・リソース・プールに抽象化し、次いで、サーバが使用するＬＵＮに分割できる。このＬＵＮは、実際にはサーバ上にあるハード・ディスクである。確かに、一部の集中型ストレージ・システムはファイル・サーバでもあり、サーバに対して共有ファイル・サービスを提供してもよい。

メモリ１２４に記憶されたデータは、ファイル・システムを使用して提示されてもよい。ファイル・システムは、構造化データファイル・ストレージ及び編成形式である。既知のように、コンピュータ内の全てのデータは０と１であり、ハードウェア・メディアに記憶された一連の０１の組み合わせを区別して管理することはできない。したがって、コンピュータは、「ファイル」の概念を使用してデータを編成する。コンピュータは、異なるアプリケーションによって必要とされる構造に基づいて、同じ目的のために使用されるデータを異なるタイプのファイルに編成する。通常、異なるタイプを参照するために異なる接尾辞が使用され、コンピュータは各ファイルに理解しやすく覚えやすい名前を付ける。多数のファイルがあるときに、ファイルは、特定の方法でグループ化される。ファイルの各グループは、同じディレクトリ（又はフォルダ）に記憶される。カタログは、ファイルに加えて、下位レベルのカタログ（サブカタログ又はサブフォルダと呼ばれる）を含んでもよい。全てのファイルとカタログはツリー構造を形成する。ツリー構造は、ファイル・システム（Ｆｉｌｅ Ｓｙｓｔｅｍ）という特別な名前を有する。ＷｉｎｄｏｗｓのＦＡＴ、ＦＡＴ３２、ＮＴＦＳ、ＬｉｎｕｘのＥＸＴ２、ＥＸＴ３、ＥＸＴ４、ＸＦＳ、ＢｔｒＦＳなど、多くのタイプのファイル・システムがある。検索を容易にするために、ルート・ノードからファイルへのレベルごとの降順、カタログ、サブカタログ、及びファイルの名前は、特殊文字（例えば、Ｗｉｎｄｏｗｓ又はＤＯＳでは「￥」が使用され、Ｕｎｉｘのようなシステムでは「／」が使用される）と組み合わされ、このような文字列は、ファイル・パスと呼ばれ、Ｌｉｎｕｘでは「／ｅｔｃ／ｓｙｓｔｅｍｄ／ｓｙｓｔｅｍ．ｃｏｎｆ」であり、Ｗｉｎｄｏｗｓでは「Ｃ：￥Ｗｉｎｄｏｗｓ￥Ｓｙｓｔｅｍ ３２￥ｔａｓｋｍｇｒ．ｅｘｅ」である。パスは、特定のファイルにアクセスするための一意の識別子である。例えば、ＷｉｎｄｏｗｓでのＤ：￥ｄａｔａ￥ｆｉｌｅ．ｅｘｅはファイルのパスであり、パーティションＤのデータカタログ内のｆｉｌｅ．ｅｘｅファイルを示す。

ファイル・システムは、ブロック・デバイス上に構築される。ファイル・システムは、ファイル・パスだけでなく、ファイルを形成するブロック、及びカタログ／サブカタログ情報を記録するブロックも記録する。異なるファイル・システムは、異なる編成構造を有する。管理の容易さから、ハード・ディスクなどのブロック・デバイスは、一般に、複数の論理ブロック・デバイス、すなわち、ハード・ディスク・パーティション（Ｐａｒｔｉｔｉｏｎ）に分割されてもよい。逆に、単一の媒体の容量と性能は、限定される。複数の物理ブロック・デバイスは、ＲＡＩＤ、ＪＢＯＤなどの様々なレベルの技術を使用して、論理ブロック・デバイスに結合され得る。代替的には、ファイル・システムは、これらの論理ブロック・デバイス上に構築されてもよい。いずれの場合も、アプリケーション・サーバ上のアプリケーションは、配下のブロック・デバイス上のアクセス対象のファイルの特定の位置を考慮する必要はなく、ファイルのファイル名／ＩＤのみをファイル・システムに送信する必要がある。ファイル・システムは、ファイル名／ＩＤに基づくクエリを通じてファイル・パスを取得する。

比較的な一般的なファイル・アクセス・プロトコルは、ＮＦＳ、ＣＩＦＳ、ＳＭＢなどであるが、これは、この実施形態では限定されない。

この出願のファイル・システムは、読み出し／書き込み可能ファイル・システムである。読み出し／書き込みファイル・システムは、ストレージ・デバイスにファイルを書き込むか、又はストレージ・デバイスからファイルを読み出すことができるファイル・システムであり、例えば、ＦＡＴ、ＨＰＦＳ、ＮＴＦＳ、ＥＸＴ４及びＦ２ＦＳである。

ファイル・システムは、一般に、メタデータ領域とデータ領域とを含む。メタデータ領域は、スーパーブロックとｉノード（ｉｎｏｄｅ）領域とを含む。メタデータ領域のスーパーブロックは、ファイル・システムの制御情報、データ構造などのコンテンツを含んでもよい。メタデータ領域のｉノード領域は、ファイルの記述情報、例えば、ファイル長及びファイル・タイプを含んでもよい。ファイル・タイプは、例えば、通常アイノード（ｒｅｇｕｌａｒ ｉｎｏｄｅ）、ディレクトリ・ｉノード（ｄｉｒｅｃｔｏｒｙ ｉｎｏｄｅ）、シンボルリンク・ｉノード（ｓｙｍｂｏｌ ｌｉｎｋ ｉｎｏｄｅ）、特殊ｉノード（ｓｐｅｃｉａｌ ｉｎｏｄｅ）である。データ領域に記憶されるデータは、可逆圧縮技術に基づくファイルレベルの圧縮処理を実行して取得されたデータであってもよい。データ領域内のデータは、ディスク・ブロックのセットに基づいて、記憶媒体（例えば、ディスク又はフラッシュ）の物理的な記憶空間に記憶される。同じファイルのデータは、連続したディスク・ブロックに記憶されていてもよいし、クロス方式で不連続なディスク・ブロックに記憶されてもよい。

本出願においてディスク・ブロックの概念を導入したからといって、記憶媒体がディスクに限定されるものではなく、ディスク・ブロックが、記憶媒体の物理的な記憶空間を分割することによって小さな物理的な記憶空間を表すために使用されてもよいことが理解されよう。

もちろん、本出願のストレージ・システムは、スケールアウト・ストレージ・システムをさらに含んでもよい。スケールアウト・ストレージ・システムは、独立した複数のストレージ・ノードにデータが記憶されるシステムである。従来のネットワーク・ストレージ・システムは、全てのデータを記憶するために集中型ストレージ・アレイを使用する。ストレージ・アレイの性能は、システム性能のボトルネックであるだけでなく、信頼性とセキュリティの焦点でもあり、大規模なストレージ・アプリケーションの要件を満たすことができない。

以上、この出願のアプリケーション・シナリオについて簡単に説明した。

上記のストレージ・システムでは、データの読み出し／書き込み能力に基づいて、コンポーネントのレートがソートされており、降順で、中央処理ユニット（ｃｅｎｔｒａｌ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ、ＣＰＵ）＞＞ダブル・データ・レート同期ダイナミック・ランダム・アクセス・メモリ（ｄｏｕｂｌｅ ｄａｔａ ｒａｔｅ ｓｙｎｃｈｒｏｎｏｕｓ ｄｙｎａｍｉｃ ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ、ＤＤＲ ＳＤＲＡＭ）＞フラッシュ・チップである。ストレージ・システムにおけるデータ・アクセスのボトルネックは、メモリとフラッシュとの間のデータのＩＯ（ｉｎｐｕｔ ｏｕｔｐｕｔ）時間オーバヘッドであることが分かる。

ストレージ・システムの全体的なＩＯ読み出し／書き込み性能を向上させるには、メモリ内のファイルを圧縮する必要がある。メタデータ領域は、ファイル・システム全体に占める割合が小さいため、通常、デバイスの記憶容量を大きく占有する。したがって、フラッシュにデータを書き込むときに、データを圧縮して、圧縮データをフラッシュに書き込むことにより、フラッシュの記憶容量占有を削減し、フラッシュの態様年数を延ばすことができる。

現在、Ｌｉｎｕｘの読み出し／書き込みファイル・システムのＦ２ＦＳ、ジャーナリング・フラッシュ・ファイル・システム・バージョン２（ｊｏｕｒｎａｌｌｉｎｇ Ｆｌａｓｈ ｆｉｌｅ ｓｙｓｔｅｍ ｖｅｒｓｉｏｎ ２、ＪＦＦＳ２）、Ｂツリー・ファイル・システム（Ｂ－ｔｒｅｅ ｆｉｌｅ ｓｙｓｔｅｍ、ＢＴＲＦＳ）など、及びＷｉｎｄｏｗｓの読み出し／書き込みファイル・システムのＮＴＦＳなどに対してデータ圧縮方式が使用されることがある。

圧縮が必要とされるオリジナル・ファイル・データ（又はソース・データと呼ばれる）は、固定サイズの最小圧縮単位（クラスタ）に基づいて圧縮されており、圧縮ファイル・データ（又は圧縮データと呼ばれる）は、ヘッダ・データと圧縮データを含む。ヘッダ・データはファイル・データの属性情報を表すために使用され、圧縮データはファイル・データのコンテンツを表すために使用される。圧縮ファイル・データはフラッシュに保存され、４ＫＢのサイズに調整されます。

例えば、図５の固定入力圧縮モードの模式図に示すように、連続するアドレスを有する４つのデータ・ブロック（ｂｌｏｃｋ）をクラスタ０として圧縮し、ヘッダ・データ（ｈｅａｄｅｒ）＋圧縮データ（ｃｏｍｐｒｅｓｓｅｄ ｄａｔａ）を含む圧縮ファイル・データを取得する。圧縮ファイル・データのサイズが４ＫＢ未満である場合、圧縮ファイル・データは４ＫＢのサイズでフラッシュに記憶される。

図５に示すオリジナル・ファイル・データ（又はソース・データと呼ばれる）のサイズは、４ブロックであり、各ブロックのサイズは、４ＫＢであり、１ブロックが１論理ページであると仮定する。オリジナル・ファイル・データの論理ページは、０、１、２、及び３で番号付けられている。オリジナル・ファイル・データは、圧縮率７５％の圧縮ファイル・データに圧縮され、圧縮ファイル・データのサイズは１２ＫＢである。したがって、圧縮ファイル・データのサイズは、３ブロックである。したがって、圧縮ファイル・データの実際のページは３ページ分であり、１論理ページを読み出すために読み出す必要があるフラッシュの実際のページのサイズを表１に示す。

圧縮ファイル・データをフラッシュに保存した後、オリジナル・ファイル・データの対象論理ページをフラッシュ内で読み出す必要がある場合、圧縮ファイル・データの３ページ分のデータを読み出す必要があり、圧縮ファイル・データを伸長した後でのみ対象論理ページを読み出すことができる。例えば、ランダム読み出しのシナリオでは、論理ページ０のオリジナル・ファイル・データをフラッシュ上で読み出す必要がある場合、３ページ分の圧縮ファイル・データを読み出し、圧縮ファイル・データを伸長した後にのみ、論理ページ０のオリジナル・ファイル・データを正常に読み出すことができる。したがって、データ読み出し効率は、以下のようである。

ランダム読み出しのシナリオでは、図５に示すデータ圧縮方法で取得された圧縮ファイル・データの読み出し効率は、比較的低いことが分かる。

前述の問題を解決するために、この出願の一実施形態は、データ圧縮方法を提供する。この方法では、読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックが取得される。ｍ個のデータ・ブロックが予め設定された圧縮アルゴリズムを使用して圧縮されて、ｎ個の圧縮データ・ブロックを順次取得し、圧縮データ・ブロックの第１の容量は全て同じであり、第１の容量は、圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表す。ｍとｎは、両方とも１以上の正の整数である。

予め設定された圧縮アルゴリズムは、固定出力圧縮モードに対応する圧縮アルゴリズム、例えば（ｌｅｍｐｅｌ－ｚｉｖ ４， ＬＺ４）圧縮アルゴリズムであってもよい。もちろん、予め設定された圧縮アルゴリズムは、別の圧縮アルゴリズムであってもよい。これは、本出願の本実施形態において具体的に限定されない。

例えば、図６に示すように、アプリケーション・シナリオにおいて、ソース・データのサイズが１６ＫＢであり、４ＫＢのデータがデータ・ブロックであり、また、論理ページが例として使用されると仮定する。ソース・データの論理ページは、表２の第１行に示すように、０、１、２、及び３で番号付けされている。

論理ページの連続する１６ＫＢのソース・データが、それぞれ６ＫＢ、７ＫＢ、５ＫＢの３つに分割されると仮定する。圧縮データ・ブロック内の各圧縮データのサイズが４ＫＢとなるまで、予め設定された圧縮アルゴリズム（例えば、ＬＺ４）を使用して３つのデータが圧縮される。

圧縮データ・ブロックは、それぞれ、図６に示す圧縮ページ４、圧縮ページ５、及び圧縮ページ６として番号付けされた３つのデータ・ページを有する。

圧縮ページ４では、論理ページ０のソース・データが全て圧縮されていることが分かる。したがって、論理ページ０は１ページに圧縮される。論理ページ１の一部のソース・データは圧縮ページ４に圧縮され、論理ページ１の他のソース・データは圧縮ページ５に圧縮される。したがって、論理ページ１は２ページに圧縮される。論理ページ２の一部のソース・データは圧縮ページ５に圧縮され、論理ページ２の他のソース・データは圧縮ページ６に圧縮される。したがって、論理ページ２は２ページに圧縮される。圧縮ページ６には、論理ページ３のソース・データが全て圧縮されている。したがって、論理ページ３は１ページに圧縮される。

したがって、ランダム読み出しシナリオでは、任意の１つ以上の論理ページが読み出されることがある。例えば、論理ページ０が読み出されるときに、表２の２行目と２列目に示すように、１つの圧縮ページのみが読み出される必要がある。伸長後、論理ページ０の全てのデータが取得されてもよい。

この場合、読み出し効率は、以下の式２に従って計算されてもよい。

論理ページ３の読み出し効率は、論理ページ０の読み出し効率と同じである。

例えば、論理ページ１が読み出されるときに、表２の２行目と３列目に示すように、３つの圧縮ページが読み出される必要がある。論理ページ１の全てのデータは、圧縮ページ４のデータと圧縮ページ５のデータとが伸長された後のみ取得することができる。

この場合、読み出し効率は、以下の式３に従って計算されてもよい。

論理ページ２の読み出し効率は、論理ページ１の読み出し効率と同じである。

追加的に、４つの論理ページの平均読み出し効率は、以下の式４に従って計算されてもよい。

式２、式３、式４の計算により得られる読み出し効率から、ランダム読み出しシナリオにおいて、図６に示すデータ圧縮方式の読み出し効率は、図５に示すデータ圧縮方式の読み出し効率よりもはるかに高いことが分かる。

この出願のこの実施形態では、固定出力圧縮モードに対応する圧縮アルゴリズムを使用して、読み書き可能なファイル・システムのデータ領域のｍ個のデータ・ブロックを圧縮して、出力される各圧縮データ・ブロックが固定サイズを有するように、同じバイト数のｎ個の圧縮データ・ブロックを順次取得することが分かる。データ・ブロックが読み出されるときに、読み出し効率を効果的に向上させることができ、読み出し増幅係数が小さいランダム読み出しシナリオでデータを読み出すことを保証することができる。

追加的に、図８は、既存の拡張可能な読み出し専用ファイル・システム（ｅｘｔｅｎｄａｂｌｅ ｒｅａｄ－ｏｎｌｙ ｆｉｌｅ ｓｙｓｔｅｍ、ｅｒｏｆｓ）におけるデータ・ブロックのインデックス付け方式を示す。データ・ブロックアドレス配列ｄａｔａ＿ａｄｄｒでは、ブロック・アドレスがアクセスされ、実際のデータ・ブロックのアドレスを指し示す。ｅｒｏｆｓがミラーを作成するときに図５に示す方法を使用してデータを圧縮するときに、ストレージ・デバイス（例えば、ディスク）の構造やファイル・コンテンツが固定されているため、ファイルの修正はサポートされない。しかし、ユーザの実際の動作シナリオでは、ストレージ・デバイス上の多くの圧縮ファイルを頻繁に修正する必要があることがある。ｅｒｏｆｓはこの要件をサポートしていない。

対応するデータ・ブロックは、データ・ブロック・インデックスに基づいて見つけることができ、データ・ブロック・インデックスもｉノード、すなわちメタデータであることが理解されよう。ｉノードは、メタデータを記憶するために使用される領域であり、ファイルに関する属性情報、例えば、ファイルの作成者、作成日、サイズ、データ・ブロックの場所を記憶するために使用される領域である。各ｉノードは番号を有し、オペレーティング・システムは、異なるｉノード番号を使用して異なるファイルを識別する。例えば、表向きは、ユーザは、ファイル名を使用してファイルを開く。実際には、最初に、ファイル名に基づいて対応するｉノード番号を見つけ、ｉノード番号に基づいてｉノード情報を取得し、次いで、ｉノード情報に基づいてデータ・ブロックのアドレスを見つけて、データを読み出す。

すなわち、ｉノードには、ファイルの属性と、ファイルの実際のストレージ場所、すなわちブロック番号（ｂｌｏｃｋ ｎｕｍｂｅｒ）が記録される。各ブロック（一般的なサイズは４ＫＢ）は、ｉノードを使用して検索及び位置特定され得る。ｉノードはＬｉｎｕｘにおけるものであり、Ｕｎｉｘではｖノードと呼ばれる。基本的に、ｉノードは、少なくとも以下の情報、すなわち、（１）ファイル・タイプ、（２）ファイル・アクセス許可、（３）ファイル所有者及びグループ、（４）ファイル・サイズ、（５）リンクの数、すなわち、ｉノードを指し示すファイル名の総数、（６）ファイル状態変更時間（ｃｔｉｍｅ）、最終アクセス時間（ａｔｉｍｅ）、及び最終修正時間（ｍｔｉｍｅ）、（７）ＳＵＩＤ、ＳＧＩＤ、及びＳＢＩＴを含む特別なファイル属性、及び（８）ファイル・コンテンツの真のポイント（ポインタ）を含む。

図８は、既存のデータ・ブロック・インデックス・フォーマットを示す。データ・ブロック・インデックス・フォーマットは、スケーラビリティ、例えば、追記、ブロック予約、又は切り捨て（ｔｒｕｎｃａｔｅ）をサポートしない。追記は、オリジナル・ファイルのコンテンツを削除することなく、オリジナル・ファイルに新たなコンテンツを追加することを示す。ブロック予約は、ディスク・ブロックを割り当てることができる領域をファイル・システムが考え、ファイル・サイズが増加した場合、ディスク・ブロックを予約することを示す。切り詰めは、ファイルを修正、例えば、ファイルを削除又は追加することを示す。

例えば、図８に示すように、データ・ブロック・インデックスは、ｂｌｋ ｅｎｔｒｙで表され、説明の便宜上、簡単にｂｌｋと呼ばれる。ｂｌｋ １は、圧縮データ・ブロック１のインデックスであり、ストレージ・デバイス内の圧縮データ・ブロック１のアドレスがｂｌｋ １に記憶される。ｂｌｋ ２は、圧縮データ・ブロック２のインデックスであり、ストレージ・デバイス内の圧縮データ・ブロック２のアドレスがｂｌｋ ２に記憶される。ｂｌｋ ３は、圧縮データ・ブロック３のインデックスであり、ストレージ・デバイス内の圧縮データ・ブロック３のアドレスがｂｌｋ ３に記憶される。ｂｌｋ ４は、圧縮データ・ブロック４のインデックスであり、ストレージ・デバイス内の圧縮データ・ブロック４のアドレスがｂｌｋ ４に記憶される。したがって、ｂｌｋに記憶されたアドレスに基づいて、ストレージ・デバイス内の圧縮データ・ブロックの場所を決定することができる。

読み出し／書き込みファイル・システムが、書き込み、上書き、事前割り当て、切り捨てなどをサポートすることを可能にするために、この出願の実施形態で提供されるデータ圧縮方法は、ｎ個の圧縮データ・ブロックのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１インデックスを確立することと、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録することとをさらに含む。ｉは、１以上ｎ以下の正の整数である。ｉは、１以上ｍ以下の正の整数である。第１のインデックスは、ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。第１のインデックスは、記憶媒体におけるｉ番目の圧縮データ・ブロックの記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

属性情報は、
データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と、
データ・ブロックのデータ・ページが有効であるかどうか、すなわち、データ・ページが通常のデータ・ページであるか、又は空のデータ・ページであるかを表すために使用される第２の属性であって、空のデータ・ページは、ブランク・データ・ページと理解され得る、第２の属性と、
データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と、
データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と、
データ・ブロックのデータ・ページが、データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と、
データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と、
データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットであり、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属しないときに、第７の属性の属性値が、データ・ブロックのデータ・ページと、圧縮データ・ブロックの第１の圧縮ページとの間の距離であることを表すために使用される第７の属性とのうちの少なくとも１つを含む。

例えば、図７に示すように、データ・ブロックの第１のインデックスは、データ・ブロック又は圧縮データ・ブロックのアドレスを記憶するｂｌｋエントリと、拡張属性情報を記憶するｅｘｔｅｎｔエントリとを含む。各ｅｘｔｅｎｔエントリは、ｂｌｋエントリと１対１で対応し、各データ・ページは、対応するｅｘｔｅｎｔエントリと、対応するｂｌｋエントリとを有する。

ｅｘｔｅｎｔエントリ・メンバのセットは、以下の方式で表される。

例えば、セットＡに示すように、データ・ブロック・インデックスに含まれるメンバをセットＡに示してもよい。各データ・ページは、対応するセットＡを有することに留意されたい。

セット・メンバの意味は、以下のように記載される。
ｉｓ＿ｒｅｓｅｒｖｅｄは第１の属性である。
ｉｓ＿ｖａｌｉｄは第２の属性である。
ｆｉｒｓｔ＿ｐａｇｅは第３の属性である。
ｃｒｏｓｓ＿ｂｌｏｃｋは第４の属性である。
ｉｓ＿ｃｏｍｐｒｅｓｓは第５の属性である。
ｂｌｋｉｄｘは、第６の属性である。
ｏｆｓは第７の属性である。

図６に示す方法を用いて、読み出し／書き込みファイル・システムにおいてデータを圧縮するときに、ストレージ・デバイス上の圧縮ファイルが修正されてもよいように、図７に示すデータ・ブロックのインデックスに含まれる属性が修正されてもよいことが分かる。

以下、この出願の実施形態で提供されるデータ圧縮方法について、特定の例を参照して記載する。

図９Ａ及び図９は、この出願の一実施形態による、データ圧縮方法の概略フローチャートである。図９Ａ及び図９Ｂに示すように、方法は、以下のステップを含む。

Ｓ９０１：読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックを取得し、ｍは１以上の正の整数である。

ｍ個のデータ・ブロックは、ライト・バックされる必要があるデータ・ブロックとして理解されよう。ライト・バックとは、書き込み動作中に、データが最初にキャッシュのためにメモリに書き込まれるが、すぐにはストレージ・デバイス（例えばディスク）に書き込まれないことを意味してもよい。メモリにキャッシュされたデータは、いくつかの特定の条件又は動作（例えば、リフレッシュ機構やシンク（ｓｙｎｃ）動作）の下でのみ、ストレージ・デバイスに書き込まれる。

Ｓ９０２：ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得し、圧縮データ・ブロックの第１の容量は全て同じであり、第１の容量は、圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表し、ｎは１以上の正の整数である。

予め設定された圧縮アルゴリズムは、ＬＺ４圧縮アルゴリズムであってもよいし、もちろん、固定出力を有する別の圧縮アルゴリズムであってもよい。これは、本出願の本実施形態において具体的に限定されない。

ｍは任意の正の整数である。例えば、ｍは４であるか、ｍは１０であるか、又はｍは２０である。

Ｓ９０２は、具体的には、以下のように実装されてもよい。

Ｓ９０２１：ｍ個のデータ・ブロックの全てのデータ・ブロックを予め設定された順序で第１のセットに順次割り当てる。

予め設定された順序は、連続するストレージ：アドレスの順序、すなわち、ｍ個のデータ・ブロックの連続する順序であってもよい。

第１のセットは、最小圧縮可能単位（クラスタ）と呼ばれてもよい。換言すれば、第１のセットは、最小圧縮可能データ・ブロック・セット、例えば、図６に示す６ＫＢデータ・ブロック・セット、７ＫＢデータ・ブロック・セット、５ＫＢデータ・ブロック・セットである。

例えば、ｍ個のデータ・ブロックは、記憶媒体において連続するアドレスのセグメントにマッピングされる。データ・ブロックを始点とし、記憶媒体にマッピングされたデータ・ブロックのアドレス順に従って、固定サイズのデータ・セットが順次分割される。図６に示すように、データ・ブロック０とデータ・ブロック１の１／２データとで６ＫＢのデータ・セットを形成し、データ・ブロック１の１／２データとデータ・ブロック２の３／４データとブランク・データ・ページとで７ＫＢのデータ・セットを形成し、データ・ブロック２の１／４データとデータ・ブロック３とで５ＫＢのデータ・セットを形成する。

Ｓ９０２２：第１のセットのｊ個のデータ・ブロックのデータ容量が、第１のセットの定格容量と等しいかどうかを決定し、ｊは１以上ｍ以下の正の整数である。ｊ個のデータ・ブロックのデータ容量が第１のセットの定格容量と等しくない場合、Ｓ９０２１が実行されるか、又はｊ個のデータ・ブロックのデータ容量が第１のセットの定格容量と等しい場合、Ｓ９０２３が実行される。

Ｓ９０２３：第１のセットのｊ個のデータ・ブロックに対して、指定された圧縮閾値に基づいて固定圧縮動作を実行し、ｉ番目の圧縮データ・ブロックを取得する。

指定された圧縮閾値は、圧縮率を表すために使用される。例えば、指定された圧縮閾値の数式は、指定された圧縮閾値＝合計データ長－合計データ長＊圧縮率であってもよい。

Ｓ９０２４：ｊ個のデータ・ブロックの合計データ長が、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和よりも大きいかどうかを決定する。ｊ個のデータ・ブロックの合計データ長が、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和よりも大きい場合、Ｓ９０３が実行される。ｊ個のデータ・ブロックの合計データ長が、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和よりも大きくない場合、ソース・データ・ページがフラッシュにサブミットされる。

Ｓ９０３：ｎ個の圧縮データ・ブロックのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立し、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録し、ｉは１以上ｎ以下の正の整数であり、ｊは１以上ｍ以下の正の整数である。

圧縮データ・ブロックを圧縮するときに、その圧縮データ・ブロックに対応するデータ・ブロックの各々のインデックスが確立される。

第１のインデックスは、ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

例えば、Ｌｉｎｕｘのｆ２ｆｓ読み出し／書き込みファイル・システムを例として使用し、ｆ２ｆｓにおけるデータ・ブロックの第１のインデックス／フォーマットは、以下のようであってもよい。

第１のインデックスに含まれる属性情報のデータ構造は、以下のようであってもよい。例えば、エントリ・データ構造は、

であり、属性情報は、
データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と（ｉｓ＿ｒｅｓｅｒｖｅｄ）、
データ・ブロックのデータ・ページが有効であるかどうかを表すために使用される第２の属性と（ｉｓ＿ｖａｌｉｄ）、
データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と（ｆｉｒｓｔ＿ｐａｇｅ）、
データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と（ｃｒｏｓｓ＿ｂｌｏｃｋ）、
データ・ブロックのデータ・ページが、データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と（ｉｓ＿ｃｏｍｐｒｅｓｓ）、
データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と（ｂｌｋｉｄｘ）、
データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットであり、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属しないときに、第７の属性の属性値が、データ・ブロックのデータ・ページと、圧縮データ・ブロックの第１の圧縮ページとの間の距離であることを表すために使用される第７の属性と（ｏｆｓ）のうちの少なくとも１つを含んでもよい。

具体的かつ可能な実装では、図１０Ａ及び図１０Ｂは、この出願の一実施形態による、データ・ブロック・インデックスを更新する概略フローチャートである。図１０Ａ及び図１０Ｂに示すように、属性情報は、第３の属性（ｆｉｒｓｔ＿ｐａｇｅ）及び第７の属性（ｏｆｓ）を含んでもよく、Ｓ９０３は、具体的には、以下のように実装されてもよい。

Ｓ１０３１：ｊ個のデータ・ブロックの各々のデータ・ページが、ｉ番目の圧縮データ・ブロックの第１の圧縮ページであるかどうかを決定する。ｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページであるときに、第３の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページではないときに、第３の属性の属性値に０を代入することを行う。

Ｓ１０３２：第３の属性の属性値が１であるときに、第７の属性の属性値を、圧縮データ・ブロックに対応する第１のセットにおけるオフセットに更新する。

Ｓ１０３３：第３の属性の属性値が０であるときに、第７の属性の属性値を、データ・ブロックのデータ・ページとｉ番目の圧縮データ・ブロックの第１の圧縮ページとの間の距離に更新する。

もちろん、属性情報は、第４の属性（ｃｒｏｓｓ＿ｂｌｏｃｋ）をさらに含んでいてもよく、Ｓ１０３は、具体的には以下のように実装されてもよい。

Ｓ１０３４：２つの圧縮ブロックの圧縮データ・ページにｊ個のデータ・ブロックの各々のデータ・ページが含まれているかどうかを決定する。ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれる場合、第４の属性の属性値に１を代入するか、又はｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれない場合、第４の属性の属性値に０を代入する。

もちろん、属性情報は、第２の属性（ｉｓ＿ｖａｌｉｄ）をさらに含んでいてもよく、Ｓ１０３は、具体的には以下のように実装されてもよい。

Ｓ１０３５：ｊ個のデータ・ブロックの各々のデータ・ページが有効であるかどうかを決定する。ｊ個のデータ・ブロックの各々のデータ・ページが有効である場合、第２の属性の属性値に１を代入し、ｊ個のデータ・ブロックの各々のデータ・ページが無効である場合、第２の属性の属性値に０を代入する。

もちろん、属性情報は、第６の属性（ｂｌｋｉｄｘ）をさらに含んでいてもよく、Ｓ１０３は、具体的には以下のように実装されてもよい。

Ｓ１０３６：ｍ個のデータ・ブロックの各データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを決定する。

圧縮は、メモリのｍ個のデータ・ブロックの記憶場所のシーケンスに従って、最小固定圧縮単位（例えば、第１のセット）のサイズを使用して実行される。１回目の圧縮が完了した（すなわち、第１の圧縮データ・ブロックが取得された）ときに、第１の圧縮データ・ブロックに対応する完了データ・ブロックのデータ・ページは、全て第１の圧縮データ・ブロックのインデックス位置にある。例えば、第１の圧縮データ・ブロックに対応するデータ・ブロックは、データ・ブロック０のデータの一部、データ・ブロック１、データ・ブロック２、及びデータ・ブロック３を含む。第１の圧縮データ・ブロックに対応する完全データ・ブロックは、データ・ブロック０、データ・ブロック１、及びデータ・ブロック２である。したがって、データ・ブロック０、データ・ブロック１、データ・ブロック２のデータ・ページは、第１の圧縮データ・ブロックのインデックス位置にある。

第３の属性に付加する必要がある第７の属性に加えて、他の属性に対応するデータ・ブロック・インデックス更新手順は互いに独立していることに留意されたい。第１の属性、第２の属性、第４の属性、第５の属性、及び第６の属性に対応するデータ・ブロック・インデックス更新手順のシーケンスは、この出願のこの実施形態においては特に限定されない。

例えば、図１１に示すように、ｍ個のデータ・ブロックは、データ・ブロック０（すなわち、ブロック０）、データ・ブロック１（すなわち、ブロック１）、データ・ブロック２（すなわち、ブロック２）、及びデータ・ブロック３（すなわち、ブロック３）を含むと仮定される。ブロック０、ブロック１、ブロック２、及びブロック３を使用して連続するアドレスのセグメントがメモリにマッピングされる。圧縮中に、ブロック０、ブロック１、ブロック２、及びブロック３使用してメモリ上にマッピングされた連続するアドレスのセグメントのシーケンス（例えば、図１１の左から右への圧縮方向）に従って、最小固定圧縮単位（例えば、第１のセット）のサイズを使用して圧縮が実行されるときに、
ブロック０の一部とブロック１が最小固定圧縮単位（例えば４ＫＢ）に達したときに、１回目の圧縮が実行されて、第１の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ ０）を取得する。この場合、ブロック０のデータ・ブロック・インデックスは、表３に示すように確立される。

図１０Ａ及び図１０Ｂを参照すると、ブロック０のデータ・ページが、第１の圧縮データ・ブロックの第１の圧縮ページにあることが分かる。したがって、ｆｉｒｓｔ＿ｐａｇｅに１が代入される。ブロック０のデータ・ページは、第１の圧縮データ・ブロックの第１の圧縮ページにのみある。したがって、ｃｒｏｓｓ＿ｂｌｏｃｋに０が代入される。ブロック０のデータ・ページの第１の圧縮データ・ブロック内のインデックス・アドレスは、第１の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ ０）の番号である。したがって、ｂｌｋｉｄｘに０が代入される。ブロック０のデータ・ページは、第１の圧縮データ・ブロックの第１の圧縮ページにあり、ブロック０に対応する第１のセットにおけるブロック０のオフセットは０である。したがって、ｏｆｓに０が代入される。ブロック０のデータ・ページは、有効なデータ・ページである。したがって、ｉｓ＿ｖａｌｉｄに１が代入される。

ブロック１の残りの部分、ブロック２の一部及びブロック３が最小固定圧縮単位（例えば４ＫＢ）に達したときに、２回目の圧縮が実行されて、第２の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ １）を取得する。この場合、ブロック１とブロック２のデータ・ブロック・インデックスは、表４に示すように確立される。

図１０Ａ及び図１０Ｂを参照すると、ブロック１のデータ・ページが、第２の圧縮データ・ブロックの第１の圧縮ページにあることが分かる。したがって、ｆｉｒｓｔ＿ｐａｇｅに１が代入される。ブロック１のデータ・ページは、第１の圧縮データ・ブロックの圧縮ページと第２の圧縮データ・ブロックの圧縮ページとにある。したがって、ｃｒｏｓｓ＿ｂｌｏｃｋに１が代入される。ブロック１のデータ・ページの第２の圧縮データ・ブロック内のインデックス・アドレスは、第２の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ １）の番号である。したがって、ｂｌｋｉｄｘに１が代入される。ブロック１のデータ・ページは、第２の圧縮データ・ブロックの第１の圧縮ページにあり、データ・ブロックのセットにおけるブロック１のオフセットはＯｆｓ１である。したがって、ｏｆｓ１にＯｆｓ１が代入される。ブロック１のデータ・ページは、有効なデータ・ページである。したがって、ｉｓ＿ｖａｌｉｄに１が代入される。

同様に、ブロック２のデータ・ページは、第２の圧縮データ・ブロックの第１の圧縮ページにはない。したがって、ｆｉｒｓｔ＿ｐａｇｅに０が代入される。ブロック２のデータ・ページは、第２の圧縮データ・ブロックの圧縮ページにのみある。したがって、ｃｒｏｓｓ＿ｂｌｏｃｋに０が代入される。ブロック２のデータ・ページの第２の圧縮データ・ブロック内のインデックス・アドレスは、第２の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ １）の番号である。したがって、ｂｌｋｉｄｘに１が代入される。ブロック２のデータ・ページは、第２の圧縮データ・ブロックの第１の圧縮ページにはなく、ブロック２のデータ・ページと第１の圧縮データ・ブロックの第１の圧縮ページとの間の距離は１である。したがって、ｏｆｓに１が代入される。ブロック２のデータ・ページは、有効なデータ・ページである。したがって、ｉｓ＿ｖａｌｉｄに１が代入される。

ブロック３の残りの部分が最小固定圧縮単位（例えば４ＫＢ）に達したときに、３回目の圧縮が実行されて、第３の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ ２）を取得する。この場合、ブロック３のデータ・ブロック・インデックスは、表５に示すように確立される。

図１０Ａ及び図１０Ｂを参照すると、ブロック３のデータ・ページが、第３の圧縮データ・ブロックの第１の圧縮ページにあることが分かる。したがって、ｆｉｒｓｔ＿ｐａｇｅに１が代入される。ブロック１のデータ・ページは、第２の圧縮データ・ブロックの圧縮ページと第３の圧縮データ・ブロックの圧縮ページとにある。したがって、ｃｒｏｓｓ＿ｂｌｏｃｋに１が代入される。ブロック１のデータ・ページの第３の圧縮データ・ブロック内のインデックス・アドレスは、第２の圧縮データ・ブロック（ｃｏｍｐｒｅｓｓ ｂｌｋ ２）の番号である。したがって、ｂｌｋｉｄｘに２が代入される。ブロック３のデータ・ページは、第３の圧縮データ・ブロックの第１の圧縮ページにあり、データ・ブロックのセットにおけるブロック３のオフセットはＯｆｓ２である。したがって、ｏｆｓ１にＯｆｓ２が代入される。ブロック３のデータ・ページは、有効なデータ・ページである。したがって、ｉｓ＿ｖａｌｉｄに１が代入される。

Ｓ９０４：ｍ個のデータの圧縮が完了したかどうかを決定する。圧縮が完了すると、圧縮データ・ブロックの圧縮ページがデバイスにサブミットされる。圧縮が完了していない場合は、Ｓ９０２を実行する。

いくつかの実施形態では、図１２は、この出願の一実施形態による、データ圧縮方法の概略フローチャートである。図１２に示すように、Ｓ９０２が実行される前に、この出願のこの実施形態で提供されるデータ圧縮方法は、以下のステップを含む。

Ｓ９０５：上書き対象データの第２のセットを取得する。

Ｓ９０６：上書き対象データの第２のセットが圧縮データ・ブロックを含むかどうかを決定する。上書き対象データの第２のセットが圧縮データ・ブロックを含む場合、Ｓ９０７が実行されるか、又は上書き対象データの第２のセットが圧縮データ・ブロックを含まない場合、既存のデータの上書き処理が実行される。

第２のセットは、ｐ個の圧縮データ・ブロックを含んでもよく、ｐは１以上の正の整数である。

Ｓ９０７：ｐ個の圧縮データ・ブロックにおける第１の対象圧縮データ・ブロックの圧縮ページと、第１の対象圧縮データ・ブロックの圧縮ページに対応するｑ個のデータ・ブロックとを取得し、ｑは１以上の正の整数である。

Ｓ９０８：ｑ個のデータ・ブロックにおいて、ｑ個のデータ・ブロック内の第１の対象データ・ブロックの場所オフセットを決定する。

具体的には、第２のセットの各圧縮データ・ブロックのインデックス・アドレスが読み出され、圧縮データ・ブロックが伸長されて、圧縮データ・ブロックに対応するデータ・ブロックを取得する。次いで、ｑ個のデータ・ブロックの各々の場所オフセットが決定される。

Ｓ９０９：第１の圧縮ページと、圧縮ページにおける第１のデータ・ブロックのオフセット位置とに基づいて、第１のデータ・ブロックのデータ・ページを取得する。

Ｓ９１０：第１の対象データ・ブロックのデータ・ページが、上書き対象データのデータ・ページであると決定する。

Ｓ９１１：第１のデータ・ブロックのデータ・ページを第２のデータ・ブロックで上書きする。

Ｓ９１２：第１のセットに第２のデータ・ブロックを割り当てる。

要するに、読み出し／書き込みファイル・システムｆ２ｆｓでは、この出願のこの実施形態で提供される固定出力圧縮モードを使用して、指定されたｓｏファイル、ｖｄｅｘファイル、ｏｄｅｘファイルなどを圧縮することにより、例えば、電子デバイス上に４０個のアプリケーションをインストールするプロセスにおいて、各アプリケーションが平均１２％の時間的効果を得ることができるという有益な効果が達成され得る。アプリケーションのインストール中、ｓｏファイルには追記手順を有し、ｖｄｅｘファイルとｏｄｅｘファイルの両方は、上書き手順を有する。４０個のアプリケーションの平均ブート・ゲインは、固定入力圧縮モードでの圧縮データのブート・ゲインよりも８％高くなる。

この出願のこの実施形態で提供されるデータ圧縮方法によれば、前述のデータ圧縮方法を使用してデータが圧縮された後、データを読み出す必要がある。図１４は、この出願の一実施形態による、データ読み出し手順の概略フローチャートである。図１４に示すように、データの読み出し手順は、以下のようである。

Ｓ１４１：第１のデータ・ブロックの属性情報を含む第１のインデックスを読み出して、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックス・アドレスを取得し、第１のインデックスが、第１のデータ・ブロックの属性情報を含む。

前述の実施形態では、第１のデータ・ブロックの属性情報は、第１の属性～第７の属性のうちの少なくとも１つを含んでもよい。例えば、第１のデータ・ブロックの属性情報は、第３の属性（ｆｉｒｓｔ＿ｐａｇｅ）、第４の属性（ｃｒｏｓｓ＿ｂｌｏｃｋ）、第６の属性（ｂｌｋｉｄｘ）、及び第７の属性（ｏｆｓ）を含む。

上書きシナリオ及び読み出し専用シナリオでは、第１のデータ・ブロックは、図１３に示すデータ・ブロック２（ブロック２）であると仮定する。ブロック２のｏｆｓ、ｃｒｏｓｓ＿ｂｌｏｃｋ、ｂｌｋｉｄｘなどの属性情報を読み出し、ブロック２に対応する第１の圧縮データ・ブロックのインデックス・アドレスを取得する。具体的には、表４が依然として使用される。ブロック２のｏｆｓに代入された値が１であることが読み出されたときに、ブロック２のデータ・ページが第２の圧縮データ・ブロックの第１の圧縮ページにはなく、ブロック２のデータ・ページと第１の圧縮データ・ブロックの第１の圧縮ページとの間の距離が１として取得されてもよいと決定されてもよい。次いで、ブロック２のｃｒｏｓｓ＿ｂｌｏｃｋに代入された値が０であることが読み出されたときに、ブロック２のデータ・ページが第１の圧縮データ・ブロックの圧縮ページのみにり、別の圧縮データ・ブロックの圧縮ページにはないと決定されてもよい。次いで、ブロック２のｂｌｋｉｄｘに代入された値が１であることが読み出されたときに、ブロック２のデータ・ページの第１の圧縮データ・ブロックにおけるインデックス・アドレスが第１の圧縮データ・ブロックの番号であると決定されてもよく、すなわち、第１の圧縮データ・ブロックのインデックス・アドレスが１として取得されてもよい。

Ｓ１４２：第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックスを読み出す。

Ｓ１４３：第１の圧縮データ・ブロックのインデックスに基づいて、第１の圧縮データ・ブロックを伸長して、第１の圧縮データ・ブロックに対応する複数のデータ・ブロックを取得し、複数のデータ・ブロックは、第１のデータ・ブロックを含む。

具体的には、第１の圧縮データ・ブロックは、第１の圧縮データ・ブロックのインデックスに基づいてデバイス上で見出される。第１の圧縮データ・ブロックが見出された後、第１の圧縮データ・ブロックが解析され、解析された複数のデータ・ブロックが取得される。例えば、図１３に示すように、第１の圧縮データ・ブロックをｃｏｍｐｒｅｓｓ ｂｌｋ １とし、ｃｏｍｐｒｅｓｓ ｂｌｋ １を解析した後、以下のデータ、すなわち、データ・ブロック１（ブロック１）のデータの一部、データ・ブロック２（ブロック２）、及びデータ・ブロック３（ブロック３）のデータの一部が取得される。

Ｓ１４４：複数の伸長データ・ブロックのうちの第１のデータ・ブロックのオフセットを決定する。

具体的には、第１のデータ・ブロックの属性情報に基づいて、第１のデータ・ブロックが図１３に示すデータ・ブロック２（ブロック２）であることが分かる。図１３に示すように、圧縮データｂｌｋ １から解析された複数のデータ・ブロックにおけるブロック２のオフセット（ｄｓｔｏｆｓ）の表現は以下のようである。

式中、ｄｓｔｏｆｓは、圧縮ブロック１から解析された複数のデータ・ブロックにおけるブロック２のオフセットを示し、ｂｌｏｃｋ＿ｓｉｚｅは、データ・ブロックの長さを示し、ｏｆｓ１は、第７の属性の属性値を示し、ｏｆｓ１％ｂｌｏｃｋ＿ｓｉｚｅは、余りを示す。

Ｓ１４５：複数の伸長データ・ブロックのうちの第１のデータ・ブロックのオフセットに基づいて、第１のデータ・ブロックのデータを取得する。

前述の例は、依然として使用される。第１のデータ・ブロックは、ブロック２である。図１３及び表４に示すように、ブロック２のデータを取得されてもよい。

具体的には、この可能な設計における通信システムは、図９に示すデータ圧縮方法で各デバイスの機能を実行するように構成されているため、前述のデータ圧縮方法と同じ効果を達成することができる。

図１５は、この出願の一実施形態によるデータ圧縮装置を示す。データ圧縮装置１５００は、読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックを取得するように構成されている第１の取得ユニットであって、ｍは１以上の正の整数である、第１の取得ユニット１５０１と、ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得するように構成されている圧縮ユニットであって、圧縮データ・ブロックの第１の容量は全て同じであり、第１の容量は、圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表し、ｎは１以上の正の整数である、圧縮ユニット１５０２と、ｎ個の圧縮データ・ブロックのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立し、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録するように構成されている更新ユニット１５０３と、を含む。ｉは１以上ｎ以下の正の整数であり、ｊは１以上ｍ以下の正の整数である。第１のインデックスは、ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

具体的かつ可能な実装では、圧縮ユニット１５０２は、ｍ個のデータ・ブロックの全てのデータ・ブロックを予め設定された順序で第１のセットに順次割り当てるように構成されている。第１のセットのｊ個のデータ・ブロックのデータ容量が、第１のセットの定格容量と等しいときに、ｊ個のデータ・ブロックに対して、指定された圧縮閾値に基づいて圧縮動作が実行されて、ｉ番目の圧縮データ・ブロックを取得する。

具体的かつ可能な実装では、更新ユニット１５０３は、ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、指定された圧縮閾値との和が、ｊ個のデータ・ブロックの合計データ長以下であるときに、ｊ個のデータ・ブロックの各々の第１のインデックスを確立するように構成されている。

具体的かつ可能な実装では、属性情報は、属性情報は、データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と、データ・ブロックのデータ・ページが有効であるかどうかを表すために使用される第２の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と、データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と、データ・ブロックのデータ・ページが、データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と、データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットであり、データ・ブロックのデータ・ページが、データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属しないときに、第７の属性の属性値が、データ・ブロックのデータ・ページと、圧縮データ・ブロックの第１の圧縮ページとの間の距離であることを表すために使用される第７の属性とのうちの少なくとも１つを含む。

具体的かつ可能な実装では、属性情報は、第３の属性を含み、更新ユニット１５０３は、ｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページであるときに、第３の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページがｉ番目の圧縮データ・ブロックの第１の圧縮ページではないときに、第３の属性の属性値に０を代入することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第７の属性を含み、更新ユニット１５０３は、第３の属性の属性値が１であるときに、第７の属性の属性値を、圧縮データ・ブロックに対応するセットにおけるデータ・ブロックのオフセットに更新することか、又は第３の属性の属性値が０であるときに、第７の属性の属性値を、データ・ブロックのデータ・ページと圧縮データ・ブロックの第１の圧縮ページとの間の距離に更新することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第４の属性を含み、更新ユニット１５０３は、ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるときに、第４の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれないときに、第４の属性の属性値に０を代入することを行うようにさらに構成されている。

具体的かつ可能な実装では、属性情報は、第２の属性を含み、更新ユニットは、ｊ個のデータ・ブロックの各々のデータ・ページが有効であるときに、第２の属性の属性値に１を代入することか、又はｊ個のデータ・ブロックの各々のデータ・ページが無効であるときに、第２の属性の属性値に０を代入することを行うようにさらに構成されている。

いくつかの可能な実施態様では、本装置は、上書き対象データの第２のセットを取得するように構成されている第２の取得ユニットであって、第２のセットは、ｐ個の圧縮データ・ブロックを含み、ｐは１以上の正の整数である、第２の取得ユニット１５０４と、ｐ個の圧縮データ・ブロックにおける第１の対象圧縮データ・ブロックの圧縮ページと、第１の対象圧縮データ・ブロックの圧縮ページに対応するｑ個のデータ・ブロックとを取得するように構成されている第３の取得ユニットであって、ｑは１以上の正の整数である、第３の取得ユニット１５０５と、ｑ個のデータ・ブロックにおいて、ｑ個のデータ・ブロック内の第１の対象データ・ブロックの場所オフセットを決定するように構成されている第１の決定ユニット１５０６と、第１の対象データ・ブロックのデータ・ページが、上書き対象データのデータ・ページであると決定するように構成されている第２の決定ユニット１５０７と、をさらに含む。

いくつかの可能な実装では、本装置は、第１のデータ・ブロックの第１のインデックスを読み出して、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックス・アドレスを取得するように構成されている第１の読み出しユニットであって、第１のインデックスが第１のデータ・ブロックの属性情報を含む、第１の読み出しユニットと、第１のデータ・ブロックに対応する第１の圧縮データ・ブロックのインデックスを読み出すように構成されている第２の読み出しユニットと、第１の圧縮データ・ブロックのインデックスに基づいて第１の圧縮データ・ブロックを伸長して、第１の圧縮データ・ブロックに対応する複数のデータ・ブロックを取得するように構成されている伸長ユニットであって、複数のデータ・ブロックは第１のデータ・ブロックを含む、伸長ユニットと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットを決定するように構成されている第３の決定ユニットと、複数の伸長データ・ブロックにおける第１のデータ・ブロックのオフセットに基づいて第１のデータ・ブロックのデータを取得するように構成されている第３の取得ユニットと、をさらに含む。

具体的かつ可能な実装では、第１のインデックスは、記憶媒体におけるｉ番目の圧縮データ・ブロックの記憶場所、及びｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される。

この出願の実施形態で提供されるデータ圧縮方法によれば、データ・ブロックが読み出されるときに、読み出し効率を効果的に向上させることができ、読み出し増幅係数が小さいランダム読み出しシナリオでデータを読み出すことを保証することができる。追加的に、データ・ブロックのインデックスに含まれる属性が修正されてもよく、そのため、ストレージ・デバイス上の圧縮ファイルが修正されてもよい。この出願の実施形態では、既存の読み出し／書き込みファイル・システムにおける圧縮ソリューションのランダム読み出し増幅の問題を解決し、固定出力圧縮方式を有する既存のファイル・システムがデータ及びメタデータ更新をサポートできないという問題を解決することが分かる。

この出願の一実施形態は、デバイスをさらに提供する。デバイスは、前述の実装のいずれか１つに従ってステップを実行するように構成されたユニット、又は前述の実装のいずれか１つに従ってステップを実行するように構成されたユニットを含む。

この出願の一実施形態は、命令を含むコンピュータ可読記憶媒体をさらに提供する。命令がコンピュータ上で動作するときに、コンピュータは、前述の方法のいずれか１つを実行することが可能となる。

この出願の一実施形態は命令を含むコンピュータ・プログラム製品を提供する。コンピュータ・プログラム製品がコンピュータ上で動作するときに、コンピュータは、前述の方法のいずれか１つを行うことが可能となる。

この出願の一実施形態は、チップをさらに提供する。チップは、プロセッサ及びインターフェース回路を含む。インターフェース回路は、プロセッサに結合される。プロセッサは、コンピュータ・プログラム又は命令を実行して、前述の方法を実装するように構成されている。インターフェース回路は、チップの外側の別のモジュールと通信するように構成されている。

この出願の説明では、別段の定めがない限り、「／」は「又は」を意味する。例えば、Ａ／Ｂは、Ａ又はＢを表してもよい。本明細書における「及び／又は」の用語は、関連するオブジェクト間の関連付け関係のみを説明し、３つの関係があり得ることを示す。例えば、Ａ及び／又はＢは、以下の３つのケース、すなわち、Ａのみが存在すること、Ａ及びＢの両方が存在すること、並びにＢのみが存在することを表してもよい。追加的に、「少なくとも１つ」とは、１つ以上を意味し、「複数の」とは、２つ以上を意味する。「第１」、「第２」などの文言は、数又は実行シーケンスを制限せず、「第１」、「第２」などの文言は、明確な差異を示さない。

この出願の説明では、「例」、「例えば」などの文言は、例、例示又は説明を与えることを表すために使用される。本出願において、「例」又は「例えば」として記載される任意の実施形態又は設計スキームは、他の実施形態又は設計スキームよりも好ましいものとして、又はより多くの利点を有するものとして説明されるべきではない。正確には、「例」、「例えば」などの文言は、関連概念を特定の方式で提示することを意図している。

実装に関する前述の説明は、便宜的かつ簡潔な説明を目的として、まさに前述の機能モジュールへの分割が説明のための例として使用されることを当業者が明確に理解することを可能にする。実際のアプリケーションでは、前述の機能は、必要に応じて実装のために異なる機能モジュールに割り当てられ得る。換言すれば、装置の内部構造は、上記の機能の全部又は一部を実装するために、異なる機能モジュールに分割される。

この出願で提供されるいくつかの実施形態では、開示された装置及び方法は、他の方式で実装され得ると理解されたい。例えば、記載された装置の実施形態は、一例にすぎない。例えば、モジュール又はユニット分割は、単に論理関数分割であり、実際の実装の際には他の分割であってもよい。例えば、複数のユニット又はコンポーネントが別の装置に組み合わされたり、統合されてもよいし、いくつかの特徴が無視されたり、実行されなくてもよい。追加的に、表示又は議論された相互結合、直接結合、又は通信接続は、いくつかのインターフェースを使用することによって実装されてもよい。装置又はユニット間の間接結合又は通信接続は、電子的、機械的、又は他の形態において実装されてもよい。

別個の部分として記載されるユニットは、物理に分離されていても、されていなくてもよく、ユニットとして表示される部分は、１つ以上の物理ユニットであってもよいし、１つの場所に位置していてもよいし、複数の場所に分散されてもよい。ユニットの一部又は全部は、実施形態の解決策の目的を達成するために実際の要件に基づいて選択されてもよい。

追加的に、本出願の実施形態における機能ユニットは、１つの処理ユニットに統合されてもよく、ユニットの各々は、物理的に単独で存在してもよく、又は２つ以上のユニットが１つのユニットに統合される。統合されたユニットは、ハードウェアの形態で実装されてもよいし、ソフトウェア機能ユニットの形態で実装されてもよい。

この出願は、特定の特徴及びその実施形態を参照して記載されているが、この出願の範囲から逸脱することなく、様々な修正及び組み合わせがそれらに対して行われてもよいことは明らかである。これに対応して、明細書及び添付の図面は、添付の特許請求の範囲によって定義されるこの出願の例示的な説明にすぎず、この出願の範囲をカバーする修正、変形、組み合わせ又は均等のいずれか又は全てと考えられる。当業者が、この出願の精神及び範囲から逸脱することなく、この出願に様々な修正及び変形を行うことができることが明らかである。この出願は、以下の特許請求の範囲及びそれらの均等の技術によって画定される保護の範囲内にあることを条件として、この出願のこれらの修正及び変形をカバーすることを意図している。

前述の説明は、この出願の単に具体的な実装に過ぎないが、この出願の保護範囲を制限することを意図したものではない。この出願に開示された技術的範囲内で、当業者によって容易に理解することができる変更又は代替は、この出願の保護範囲に含まれるものとする。したがって、この出願の保護範囲は、特許請求の範囲の保護範囲に従うものとする。

Claims (24)

1. データ圧縮方法であって、
   読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックを取得することであって、ｍは１以上の正の整数である、ことと、
   前記ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得することであって、前記圧縮データ・ブロックの第１の容量は全て同じであり、前記第１の容量は、前記圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表し、ｎは１以上の正の整数である、ことと、
   前記ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立し、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録することであって、ｉは１以上ｎ以下の正の整数であり、ｊは１以上ｍ以下の正の整数である、ことと、を含み、
   前記第１のインデックスは、前記ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所と、前記ｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される、方法。
2. 前記ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得することは、
   前記ｍ個のデータ・ブロックの全てのデータ・ブロックを予め設定された順序で第１のセットに順次割り当てることと、
   前記第１のセットの前記ｊ個のデータ・ブロックのデータ容量が、前記第１のセットの定格容量と等しいときに、前記ｊ個のデータ・ブロックに対して、指定された圧縮閾値に基づいて圧縮動作を実行して、前記ｉ番目の圧縮データ・ブロックを取得することと、を含む、請求項１に記載の方法。
3. 前記ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、
   前記ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、前記指定された圧縮閾値との和が、ｊ個のデータ・ブロックの合計データ長以下であるときに、前記ｊ個のデータ・ブロックの各々の第１のインデックスを確立することを含む、請求項２に記載の方法。
4. 前記属性情報は、
   データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と、
   データ・ブロックのデータ・ページが有効であるかどうかを表すために使用される第２の属性と、
   データ・ブロックのデータ・ページが、前記データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と、
   データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と、
   データ・ブロックのデータ・ページが、前記データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と、
   データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と、
   データ・ブロックのデータ・ページが、前記データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、前記圧縮データ・ブロックに対応するセットにおける前記データ・ブロックのオフセットであり、前記データ・ブロックの前記データ・ページが、前記データ・ブロックの前記圧縮データ・ブロックの前記第１の圧縮ページに属しないときに、前記第７の属性の前記属性値が、前記データ・ブロックの前記データ・ページと、前記圧縮データ・ブロックの前記第１の圧縮ページとの間の距離であることを表すために使用される第７の属性とのうちの少なくとも１つを含む、請求項１～３のいずれか一項に記載の方法。
5. 前記属性情報は前記第３の属性を含み、前記ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、
   前記ｊ個のデータ・ブロックの各々のデータ・ページが前記ｉ番目の圧縮データ・ブロックの第１の圧縮ページであるときに、前記第３の属性の属性値に１を代入することか、又は
   前記ｊ個のデータ・ブロックの各々のデータ・ページが前記ｉ番目の圧縮データ・ブロックの第１の圧縮ページではないときに、前記第３の属性の属性値に０を代入することを含む、請求項４に記載の方法。
6. 前記属性情報は、前記第７の属性を含み、前記方法は、
   前記第３の属性の前記属性値が１であるときに、前記第７の属性の前記属性値を、前記圧縮データ・ブロックに対応する前記セットにおける前記データ・ブロックの前記オフセットに更新することか、又は
   前記第３の属性の前記属性値が０であるときに、前記第７の属性の前記属性値を、前記データ・ブロックの前記データ・ページと前記圧縮データ・ブロックの前記第１の圧縮ページとの間の前記距離に更新することを含む、請求項４又は５に記載の方法。
7. 前記属性情報は前記第４の属性を含み、前記ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、
   前記ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるときに、前記第４の属性の属性値に１を代入することか、又は
   前記ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれないときに、前記第４の属性の属性値に０を代入することを含む、請求項４～６のいずれか一項に記載の方法。
8. 前記属性情報は前記第２の属性を含み、前記ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立することは、
   前記ｊ個のデータ・ブロックの各々のデータ・ページが有効であるときに、前記第２の属性の属性値に１を代入することか、又は
   前記ｊ個のデータ・ブロックの各々のデータ・ページが無効であるときに、前記第２の属性の属性値に０を代入することを含む、請求項４～７のいずれか一項に記載の方法。
9. 前記ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得することの前に、
   上書き対象データの第２のセットを取得することであって、前記第２のセットは、ｐ個の圧縮データ・ブロックを含み、ｐは１以上の正の整数である、ことと、
   前記ｐ個の圧縮データ・ブロックにおける第１の対象圧縮データの圧縮ページと、前記第１の対象圧縮データ・ブロックの前記圧縮ページに対応するｑ個のデータ・ブロックとを取得することであって、ｑは１以上の正の整数である、ことと、
   前記ｑ個のデータ・ブロックにおいて、前記ｑ個のデータ・ブロック内の第１の対象データ・ブロックの場所オフセットを決定することと、
   前記第１の対象データ・ブロックのデータ・ページが、前記上書き対象データのデータ・ページであると決定することと、をさらに含む、請求項１～８のいずれか一項に記載の方法。
10. 前記第１のインデックスは、前記記憶媒体における前記ｉ番目の圧縮データ・ブロックの記憶場所、及び前記ｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される、請求項１～９のいずれか一項に記載の方法。
11. データ圧縮装置であって、
    読み書き可能なファイル・システムのデータ領域におけるｍ個のデータ・ブロックを取得するように構成されている第１の取得ユニットであって、ｍは１以上の正の整数である、第１の取得ユニットと、
    前記ｍ個のデータ・ブロックを予め設定された圧縮アルゴリズムを使用して圧縮して、ｎ個の圧縮データ・ブロックを順次取得するように構成されている圧縮ユニットであって、前記圧縮データ・ブロックの第１の容量は全て同じであり、前記第１の容量は、前記圧縮データ・ブロックに含まれ得る圧縮データのバイト数を表し、ｎは１以上の正の整数である、圧縮ユニットと、
    前記ｎ個の圧縮データのうちのｉ番目の圧縮データ・ブロックに対応するｊ個のデータ・ブロックの各々の第１のインデックスを確立し、第１のインデックスとｊ個のデータ・ブロックとの間のマッピング関係を記録するように構成されている更新ユニットであって、ｉは１以上ｎ以下の正の整数であり、ｊは１以上ｍ以下の正の整数である、更新ユニットと、を含み、
    前記第１のインデックスは、前記ｊ個のデータ・ブロックに含まれる各データ・ブロックの記憶媒体における記憶場所、及び前記ｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される、装置。
12. 前記圧縮ユニットは、
    前記ｍ個のデータ・ブロックの全てのデータ・ブロックを予め設定された順序で第１のセットに順次割り当てることと、
    前記第１のセットの前記ｊ個のデータ・ブロックのデータ容量が、前記第１のセットの定格容量と等しいときに、前記ｊ個のデータ・ブロックに対して、指定された圧縮閾値に基づいて圧縮動作を実行して、前記ｉ番目の圧縮データ・ブロックを取得することと、を行うように構成されている、請求項１１に記載の装置。
13. 前記更新ユニットは、
    前記ｉ番目の圧縮データ・ブロックのヘッダ・データと圧縮データの合計データ長と、前記指定された圧縮閾値との和が、ｊ個のデータ・ブロックの合計データ長以下であるときに、前記ｊ個のデータ・ブロックの各々の第１のインデックスを確立するように構成されている、請求項１２に記載の装置。
14. 前記属性情報は、
    データ・ブロックが圧縮される圧縮データ・ブロックの記憶場所が予め割り当てられているかどうかを表す第１の属性と、
    データ・ブロックのデータ・ページが有効であるかどうかを表すために使用される第２の属性と、
    データ・ブロックのデータ・ページが、前記データ・ブロックの圧縮データ・ブロックの第１の圧縮ページであるかどうかを表すために使用される第３の属性と、
    データ・ブロックのデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるかどうかを表すために使用される第４の属性と、
    データ・ブロックのデータ・ページが、前記データ・ブロックを圧縮することによって取得された圧縮データ・ブロックの圧縮ページであるかどうかを示す第５の属性と、
    データ・ブロックのデータ・ページが位置する圧縮データ・ブロックのインデックス・アドレスを表すために使用される第６の属性と、
    データ・ブロックのデータ・ページが、前記データ・ブロックの圧縮データ・ブロックの第１の圧縮ページに属するときに、第７の属性の属性値が、前記圧縮データ・ブロックに対応するセットにおける前記データ・ブロックのオフセットであり、前記データ・ブロックの前記データ・ページが、前記データ・ブロックの前記圧縮データ・ブロックの前記第１の圧縮ページに属しないときに、前記第７の属性の前記属性値が、前記データ・ブロックの前記データ・ページと、前記圧縮データ・ブロックの前記第１の圧縮ページとの間の距離であることを表すために使用される第７の属性とのうちの少なくとも１つを含む、請求項１１～１３のいずれか一項に記載の装置。
15. 前記属性情報は、前記第３の属性を含み、前記更新ユニットは、
    前記ｊ個のデータ・ブロックの各々のデータ・ページが前記ｉ番目の圧縮データ・ブロックの第１の圧縮ページであるときに、前記第３の属性の属性値に１を代入することか、又は
    前記ｊ個のデータ・ブロックの各々のデータ・ページが前記ｉ番目の圧縮データ・ブロックの第１の圧縮ページではないときに、前記第３の属性の属性値に０を代入することを行うようにさらに構成されている、請求項１４に記載の装置。
16. 前記属性情報は、前記第７の属性を含み、前記更新ユニットは、
    前記第３の属性の前記属性値が１であるときに、前記第７の属性の前記属性値を、前記圧縮データ・ブロックに対応する前記セットにおける前記データ・ブロックの前記オフセットに更新することか、又は
    前記第３の属性の前記属性値が０であるときに、前記第７の属性の前記属性値を、前記データ・ブロックの前記データ・ページと前記圧縮データ・ブロックの前記第１の圧縮ページとの間の前記距離に更新することを行うようにさらに構成されている、請求項１４又は１５に記載の装置。
17. 前記属性情報は、前記第４の属性を含み、前記更新ユニットは、
    前記ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれるときに、前記第４の属性の属性値に１を代入することか、又は
    前記ｊ個のデータ・ブロックの各々のデータ・ページが２つの圧縮ブロックの圧縮データ・ページに含まれないときに、前記第４の属性の属性値に０を代入することを行うようにさらに構成されている、請求項１４～１６のいずれか一項に記載の装置。
18. 前記属性情報は、前記第２の属性を含み、前記更新ユニットは、
    前記ｊ個のデータ・ブロックの各々のデータ・ページが有効であるときに、前記第２の属性の属性値に１を代入することか、又は
    前記ｊ個のデータ・ブロックの各々のデータ・ページが無効であるときに、前記第２の属性の属性値に０を代入することを行うようにさらに構成されている、請求項１４～１７のいずれか一項に記載の装置。
19. 上書き対象データの第２のセットを取得するように構成されている第２の取得ユニットであって、前記第２のセットは、ｐ個の圧縮データ・ブロックを含み、ｐは１以上の正の整数である、第２の取得ユニットと、
    前記ｐ個の圧縮データ・ブロックにおける第１の対象圧縮データの圧縮ページと、前記第１の対象圧縮データ・ブロックの前記圧縮ページに対応するｑ個のデータ・ブロックとを取得するように構成されている第３の取得ユニットであって、ｑは１以上の正の整数である、第３の取得ユニットと、
    前記ｑ個のデータ・ブロックにおいて、前記ｑ個のデータ・ブロック内の第１の対象データ・ブロックの場所オフセットを決定するように構成されている第１の決定ユニットと、
    前記第１の対象データ・ブロックのデータ・ページが、前記上書き対象データのデータ・ページであると決定するように構成されている第２の決定ユニットと、をさらに含む、請求項１１～１８のいずれか一項に記載の装置。
20. 前記第１のインデックスは、前記記憶媒体における前記ｉ番目の圧縮データ・ブロックの記憶場所、及び前記ｊ個のデータ・ブロックの各々に含まれる属性情報を識別するために使用される、請求項１１～１９のいずれか一項に記載の装置。
21. 請求項１～１０のいずれか一項に記載のデータ圧縮方法を実行するように構成されているデバイス。
22. コンピュータ命令を含むコンピュータ可読記憶媒体であって、前記コンピュータ命令が電子デバイス上で実行されるときに、前記電子デバイスは、請求項１～１０のいずれか一項に記載のデータ圧縮方法を実行することが可能となる、コンピュータ可読記憶媒体。
23. コンピュータ・プログラムであって、前記プログラムが、プロセッサによって呼び出されると、請求項１～１０のいずれか一項に記載のデータ圧縮方法が実行される、コンピュータ・プログラム。
24. １つ以上のプロセッサを含むチップ・システムであって、前記１つ以上のプロセッサが命令を実行するときに、前記１つ以上のプロセッサは、請求項１～１０のいずれか一項に記載の方法を実行することが可能となる、チップ・システム。

Images