(57)【要約】  本発明の実施例は、データオブジェクトを１つ以上のブロックに分割し、各ブロックのサンプル圧縮率を計算し、同じサンプル圧縮率特性を有する隣接する連続ブロックを１つのデータセグメントに集約し、データセグメントのそれぞれのサンプル圧縮率を取得し、データセグメントのそれぞれの長さが属する長さの範囲と、データセグメントのそれぞれのサンプル圧縮率が属する圧縮率範囲とに従って、データセグメントをデータチャンクに分割するための期待長を選択することができるデータオブジェクト処理方法及び装置を提供する。データセグメントのそれぞれのサンプル圧縮率は、圧縮率範囲の１つに一意に属し、データセグメントのそれぞれの長さは、長さの範囲の１つに一意に属する。本発明で提供される技術を適用することにより、データオブジェクトは、データチャンクに分割され得る。
2016515250.tif 000002
【特許請求の範囲】
【請求項１】
データオブジェクトを１つ以上のブロックに分割するステップと、
各ブロックのサンプル圧縮率を計算し、同じサンプル圧縮率特性を有する連続ブロックを１つのデータセグメントに集約し、前記データセグメントのそれぞれの前記サンプル圧縮率を取得するステップと、
前記データセグメントのそれぞれの長さが属する長さの範囲と、前記データセグメントのそれぞれの前記サンプル圧縮率が属する圧縮率範囲とに従って、前記データセグメントをデータチャンクに分割するための期待長を選択するステップであり、前記データセグメントのそれぞれの前記サンプル圧縮率は、前記圧縮率範囲の１つに一意に属し、前記データセグメントのそれぞれの前記長さは、前記長さの範囲の１つに一意に属するステップと
を有するデータオブジェクト処理方法。
【請求項２】
データオブジェクトを１つ以上のブロックに分割するステップは、具体的に、
前記データオブジェクトを１つ以上の固定長ブロックに分割するステップである、請求項１に記載の方法。
【請求項３】
隣接するデータセグメントについて、前のデータセグメントの終わりのデータチャンクと、次のデータセグメントの開始のデータチャンクとを接合データチャンクに接合するステップを更に有する、請求項１に記載の方法。
【請求項４】
前記接合データチャンクを複数のデータチャンクに分割するステップを更に有し、
分割に使用される前記期待長は、前記前のデータセグメントに対応する期待長以下であり、分割に使用される前記期待長は、前記次のデータセグメントに対応する期待長以下である、請求項３に記載の方法。
【請求項５】
データオブジェクトを１つ以上のブロックに分割するステップは、具体的に、
異なる期待長を有する候補チャンク境界の複数のグループを計算し、前記候補チャンク境界の複数のグループのうち１つを使用することにより、前記データオブジェクトを１つ以上の可変長ブロックに分割するステップである、請求項１に記載の方法。
【請求項６】
前記データセグメントをデータチャンクに分割するための期待長を選択するステップは、具体的に、
前記選択された期待長に従って、候補チャンク境界の複数のグループから、前記データセグメントをデータチャンクに分割するための同じ期待長を有するチャンク境界を選択するステップである、請求項１又は５に記載の方法。
【請求項７】
同じサンプル圧縮率特性を有する連続ブロックを１つのデータセグメントに集約するステップは、具体的に、
前記サンプル圧縮率が同じ圧縮率範囲に属する隣接する連続ブロックを１つのデータセグメントに集約するステップである、請求項１に記載の方法。
【請求項８】
同じサンプル圧縮率特性を有する連続ブロックを１つのデータセグメントに集約するステップは、具体的に、
前記サンプル圧縮率の値の間の差が指定された閾値未満である隣接する連続ブロックを１つのデータセグメントに集約するステップである、請求項１に記載の方法。
【請求項９】
前記方法の後に、
前記データチャンクのそれぞれのフィンガープリントを計算し、前記フィンガープリントを使用することにより、前記データチャンクのそれぞれが記憶デバイスに記憶されているか否かを決定し、前記記憶デバイスに記憶されていない前記データチャンクを、記憶されていない前記データチャンクに対応する前記フィンガープリント及び前記サンプル圧縮率と共に前記記憶デバイスに送信するステップと、
前記記憶デバイスにより、受信したデータチャンクの前記フィンガープリントを記憶し、前記受信したデータチャンクの前記サンプル圧縮率が圧縮率閾値に従うか否かを決定し、前記サンプル圧縮率が前記圧縮率閾値に従う前記データチャンクを圧縮して記憶するステップと
を更に有する、請求項１又は３に記載の方法。
【請求項１０】
前記データチャンクが取得されたセグメントの前記サンプル圧縮率は、前記データチャンクの前記サンプル圧縮率として使用される、請求項９に記載の方法。
【請求項１１】
前記データセグメントの前記サンプル圧縮率は、具体的に、
前記データセグメントを形成する前記ブロックの前記サンプル圧縮率の算術平均を計算すること、又は
前記データセグメントを形成する前記ブロックの前記サンプル圧縮率をフラグ値として使用し、前記ブロックの長さを重みとして使用することにより、前記ブロックの前記サンプル圧縮率の加重平均を計算することである、請求項１に記載の方法。
【請求項１２】
データオブジェクトを１つ以上のブロックに分割するように構成されたブロック分割モジュールと、
各ブロックのサンプル圧縮率を計算し、同じサンプル圧縮率特性を有する連続ブロックを１つのデータセグメントに集約し、前記データセグメントのそれぞれの前記サンプル圧縮率を取得するように構成されたデータセグメント生成モジュールと、
前記データセグメントのそれぞれの長さが属する長さの範囲と、前記データセグメントのそれぞれの前記サンプル圧縮率が属する圧縮率範囲とに従って、前記データセグメントをデータチャンクに分割するための期待長を選択するように構成されたデータチャンク生成モジュールであり、前記データセグメントのそれぞれの前記サンプル圧縮率は、前記圧縮率範囲の１つに一意に属し、前記データセグメントのそれぞれの長さは、前記長さの範囲の１つに一意に属するデータチャンク生成モジュールと
を有するデータオブジェクト処理装置。
【請求項１３】
前記ブロック分割モジュールは、前記データオブジェクトを１つ以上の固定長ブロックに分割するように具体的に構成される、請求項１２に記載の装置。
【請求項１４】
前記データチャンク生成モジュールは、隣接するデータセグメントについて、前のデータセグメントの終わりのデータチャンクと、次のデータセグメントの開始のデータチャンクとを接合データチャンクに接合するように更に構成される、請求項１２に記載の装置。
【請求項１５】
前記データチャンク生成モジュールは、前記接合データチャンクを複数のデータチャンクに分割するように更に構成され、分割に使用される前記期待長は、前記前のデータセグメントに対応する期待長以下であり、分割に使用される前記期待長は、前記次のデータセグメントに対応する期待長以下である、請求項１４に記載の装置。
【請求項１６】
前記ブロック分割モジュールは、異なる期待長を有する候補チャンク境界の複数のグループを計算し、前記候補チャンク境界の複数のグループのうち１つを使用することにより、前記データオブジェクトを１つ以上の可変長ブロックに分割するように具体的に更に構成される、請求項１２に記載の装置。
【請求項１７】
前記データセグメントをデータチャンクに分割するための期待長を選択することは、具体的に、
前記選択された期待長に従って、候補チャンク境界の複数のグループから、前記データセグメントをデータチャンクに分割するための同じ期待長を有するチャンク境界を選択することである、請求項１２又は１６に記載の装置。
【請求項１８】
前記データセグメント生成モジュールは、各ブロックの前記サンプル圧縮率を計算し、前記サンプル圧縮率が同じ圧縮率範囲に属する隣接する連続ブロックを１つのデータセグメントに集約し、前記データセグメントのそれぞれの前記サンプル圧縮率を取得するように具体的に構成される、請求項１２に記載の装置。
【請求項１９】
前記データセグメント生成モジュールは、各ブロックの前記サンプル圧縮率を計算し、前記サンプル圧縮率の値の間の差が指定された閾値未満である隣接する連続ブロックを１つのデータセグメントに集約し、前記データセグメントのそれぞれの前記サンプル圧縮率を取得するように具体的に構成される、請求項１２に記載の装置。
【請求項２０】
前記データチャンクのそれぞれのフィンガープリントを計算し、前記フィンガープリントを使用することにより、前記データチャンクのそれぞれが記憶デバイスに記憶されているか否かを決定し、前記記憶デバイスに記憶されていない前記データチャンクを、記憶されていない前記データチャンクに対応する前記フィンガープリント及び前記サンプル圧縮率と共に前記記憶デバイスに送信するように構成されたデータチャンク送信モジュールを更に有し、
前記記憶デバイスは、受信したデータチャンクの前記フィンガープリントを記憶し、前記受信したデータチャンクの前記サンプル圧縮率が圧縮率閾値に従うか否かを決定し、前記サンプル圧縮率が前記圧縮率閾値に従う前記データチャンクを圧縮して記憶するように構成される、請求項１２に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報技術の分野に関し、特にデータオブジェクト処理方法及び装置に関する。
【背景技術】
【０００２】
重複データ除去（Duplicate  Data  Elimination）としても知られるデータ重複排除（Data  Deduplication）は、データ記憶及び／又はデータ送信の効率を改善するために、データセット又はデータストリーム内の重複コンテンツを識別及び除去する処理であり、略して重複排除又は重複除去と呼ばれる。一般的に、重複排除技術では、データセット又はデータストリームは、一連のデータユニットに分割され、重複した１つのみのデータユニットを保持する。これにより、データ記憶処理における空間コスト又はデータ送信処理における帯域幅の消費を低減する。
【０００３】
重複コンテンツが容易に識別されることができる、データオブジェクトをデータユニットに分割する方法は、解決される必要がある主要な問題である。データオブジェクトがデータユニットに分割された後に、データチャンクのハッシュ値h(・)は、フィンガープリントとして計算され得る。同じフィンガープリントを有するデータユニットは、重複データとして規定される。従来技術では、重複排除のために一般的に使用されるデータユニットは、ファイル、固定長ブロック（Block）、コンテンツにより規定された可変長チャンク（Chunk）等を含む。コンテンツ・デファインド・チャンキング（Content  Defined  Chunking、CDC）方法は、データセット又はデータストリームを可変長チャンク系列に分割するため、データをスキャンして予め設定された特性に従うバイト列を識別し、チャンク境界としてのバイト列の位置に印を付けるためにスライディングウィンドウを採用する。この方法では、チャンク境界は、データのコンテンツ特性に基づいて選択され、同様のファイル又はデータストリームにより共有されるデータユニットを更に正確に識別することができる。従って、この方法は、様々なデータ重複排除の解決策に広く適用されている。研究によれば、コンテンツ・デファインド・チャンキング方法がデータセット又はデータストリームを分割するために採用される場合、更に細かいチャンキング粒度は、重複データの更に高い識別確率及び更に高い重複排除結果を意味する。しかし、更に細かいチャンキング粒度は、所与のデータセットから分割される更に多くの数のチャンクを意味し、これにより、インデックス化のオーバーヘッド及び重複データを検索する複雑性を増加させる。その結果、データ重複排除の時間効率が低減される。
【０００４】
期待長は、チャンキング粒度を制御するためのコンテンツ・デファインド・チャンキング（Content  Defined  Chunking、CDC）方法の主要なパラメータである。一般的に、CDCチャンキング方法は、特定のデータオブジェクトについて可変長チャンク系列を出力する。様々なチャンクの長さは、統計的に正規分布に従い、期待長は、正規分布の平均値を調整するために使用される。一般的に、正規分布の平均値は、平均チャンク長により表される。確率変数が正規分布のもとでの最高の確率の平均値に割り当てられるため、平均チャンク長はまた、ピーク長とも呼ばれ、理想的な状況における期待長に等しくなり得る。例えば、CDC方法では、スライディングウィンドウ内のデータのフィンガープリントf(w-bytes)は、リアルタイムで計算される。f(w-bytes)の特定のビットが予め設定された値に合致する場合、スライディングウィンドウの位置は、チャンク境界として選択される。データコンテンツの更新は、ハッシュフィンガープリントのランダムな変化を生じ得るため、f(w-bytes)&0xFFF=0が合致条件として設定され、ただし、&は２進数フィールドにおけるビットのAND演算であり、0xFFFは4095の１６進数表現である場合、１つのフィンガープリントの合致は、理論上でf(w-bytes)の4096個のランダムな変化で生じる可能性がある。すなわち、チャンク境界は、スライディングウィンドウが4KB（4096バイト）前にスライドする毎に見つけられ得る。理想的な状況のもとでのチャンク長は、CDC方法における期待チャンク長（Expected  Chunk  Length）であり、略して期待長と呼ばれる。
【０００５】
重複排除の空間効率を維持しつつ、できるだけチャンクの数を低減するために、従来技術は、コンテンツ・デファインド二方式チャンキング方法を提供する。コンテンツ・デファインド二方式チャンキング方法の中心の概念は、２つの異なる期待長を有する可変長チャンキングモードを採用することである。ファイルをデータチャンクに分割する場合、重複排除記憶システムに問い合わせることにより候補チャンクの重複を決定し、重複データと非重複データとの間の遷移の領域ではスモールチャンクモードを採用し、非遷移領域ではラージチャンクモードを採用する。
【０００６】
しかし、この技術は独立して動作することができず、どのようにデータオブジェクトをチャンキングするかを決定する場合、チャンク計算デバイスは、重複排除記憶デバイスに存在するデータチャンクのフィンガープリントを頻繁に問い合わせる必要がある。重複排除記憶デバイスは、データ重複排除が実行されたデータチャンクを記憶する。そして、候補チャンクの重複に従って、重複データと非重複データとの間の遷移の領域が存在するか否かを決定し、どのチャンキングモードが最終的に採用されるかを決定する必要がある。従って、従来技術は、重複排除記憶デバイスに問い合わせ負荷の圧力を引き起こす。
【発明の概要】
【０００７】
本発明の実施例は、データオブジェクトをデータチャンクに分割することができるデータオブジェクト処理技術を提供する。
【０００８】
第１の態様によれば、本発明の実施例は、データオブジェクト処理方法を提供し、この方法は、データオブジェクトを１つ以上のブロックに分割するステップと、各ブロックのサンプル圧縮率を計算し、同じサンプル圧縮率特性を有する連続ブロックを１つのデータセグメントに集約し、データセグメントのそれぞれのサンプル圧縮率を取得するステップと、データセグメントのそれぞれの長さが属する長さの範囲と、データセグメントのそれぞれのサンプル圧縮率が属する圧縮率範囲とに従って、データセグメントをデータチャンクに分割するための期待長を選択するステップであり、データセグメントのそれぞれのサンプル圧縮率は、圧縮率範囲の１つに一意に属し、データセグメントのそれぞれの長さは、長さの範囲の１つに一意に属するステップとを含む。
【０００９】
第２の態様によれば、本発明の実施例は、データオブジェクト処理装置を提供し、この装置は、データオブジェクトを１つ以上のブロックに分割するように構成されたブロック分割モジュールと、各ブロックのサンプル圧縮率を計算し、同じサンプル圧縮率特性を有する連続ブロックを１つのデータセグメントに集約し、データセグメントのそれぞれのサンプル圧縮率を取得するように構成されたデータセグメント生成モジュールと、データセグメントのそれぞれの長さが属する長さの範囲と、データセグメントのそれぞれのサンプル圧縮率が属する圧縮率範囲とに従って、データセグメントをデータチャンクに分割するための期待長を選択するように構成されたデータチャンク生成モジュールであり、データセグメントのそれぞれのサンプル圧縮率は、圧縮率範囲の１つに一意に属し、データセグメントのそれぞれの長さは、長さの範囲の１つに一意に属するデータチャンク生成モジュールとを含む。
【００１０】
本発明の実施例の適用では、データオブジェクトはブロックに分割され、ブロックは各ブロックの圧縮率に従ってデータセグメントに集約され、データセグメントはデータチャンクに分割される。このことは、データオブジェクトをデータチャンクに分割するという結果を達成する。
【図面の簡単な説明】
【００１１】
本発明の実施例又は従来技術の技術的解決策を明確に説明するために、以下に、実施例又は従来技術を説明するために必要な添付図面について簡単に紹介する。以下の説明における添付図面は、本発明の単にいくつかの実施例を示しているに過ぎず、依然として他の図面もこれらの添付図面から導かれ得る。
【図１】データオブジェクト処理方法の実施例のフローチャート
【図２】データオブジェクト処理方法の実施例のフローチャート
【図３】データオブジェクト処理方法の実施例のフローチャート
【図４】データオブジェクト処理方法の実施例のフローチャート
【図５】データオブジェクト処理方法の実施例のフローチャート
【図６】データオブジェクト処理装置の実施例の概略図
【発明を実施するための形態】
【００１２】
以下に、本発明の実施例の添付図面を参照して、本発明の実施例の技術的解決策を明確且つ完全に説明する。明らかに、説明する実施例は、本発明の実施例の全てではなく、一部に過ぎない。本発明の実施例に基づいて得られる全ての他の実施例は、本発明の保護範囲内に入るものとする。
【００１３】
データチャンクの期待長を低減することは、高い重複排除率を取得する助けとなるが、データチャンクの数及び対応するインデックスを増加させる可能性があり、これにより、重複データチャンクを検索する複雑性を増加させ、重複排除性能を制限する可能性がある。
【００１４】
従来技術では、細粒度チャンキングは、重複コンテンツと非重複コンテンツとの間の遷移の領域に採用されるが、粗粒度チャンキングは、他の領域に採用され、これにより、二方式チャンキング方法を形成する。しかし、この方法は、チャンキング処理において候補チャンクの重複を頻繁に問い合わせることを必要とし、従って、重複排除記憶システムに問い合わせ負荷の圧力を引き起こす。更に、この方法のチャンキング結果は、複数バージョンのデータの送信順序に依存するため、この方法は不安定である。
【００１５】
本発明の実施例は、圧縮性を提供し、データオブジェクトをデータチャンクに分割することができるコンテンツ・デファインド多方式データ重複排除チャンキング方法を提供する。具体的に、本発明の実施例の適用では、データオブジェクトはブロックに分割され、ブロックは各ブロックのサンプル圧縮率に従ってデータセグメントに集約され、各データセグメントをデータチャンクに分割するためにデータセグメントの長さ及びサンプル圧縮率に従って期待長が選択される。このことは、多方式の長さ分布においてデータオブジェクトをデータチャンク系列に分割するという結果を達成する。
【００１６】
本発明の実施例では、データオブジェクトは、動作可能なデータのセグメント、例えば、ファイル又はデータストリームを示す。チャンキングポリシー・マッピングテーブルは、圧縮率範囲と長さの範囲と期待チャンク長との間のマッピング関係を維持管理するために使用される。データセグメントの期待チャンク長は、データセグメントの長さ及び圧縮率の増加と共に大きくなる。
【００１７】
本発明の実施例で提供される方法では、データオブジェクトはデータチャンクに分割されてもよく、分割の後に取得されたデータチャンクは、データ重複排除の単位として使用されてもよい。これにより、データ損失なしに記憶空間利用率が低減されるという前提でデータオブジェクトが記憶又は送信され得る。明らかに、分割から生成されたデータチャンクは、データ重複排除以外の目的に更に使用されてもよい。本発明の実施例は、(a)データオブジェクト（Data  Object）をチャンキングデバイスに入力するステップであり、データオブジェクトは、チャンキングデバイスの外又は中のメモリから生じてもよく、例えば、データオブジェクトは、重複排除動作要件を満たす限りファイル又はデータストリームでもよく、これは本発明の実施例では限定されないステップと、(b)データオブジェクトを１つ以上のブロック（Block）に分割し、サンプリング方法を使用することにより各ブロックの圧縮率を推定し、チャンキングポリシー・マッピングテーブルに問い合わせ、圧縮率が同じ圧縮率範囲に属する隣接する連続ブロックを１つのデータセグメント（Segment）に集約するステップであり、サンプル圧縮率は、データチャンクの圧縮性の尺度であり、サンプル圧縮率は、サンプリングが全体ブロックで実行された場合にブロックの圧縮率と同じであるステップと、(c)各データセグメントについてチャンキングポリシー・マッピングテーブルに問い合わせ、データセグメントに対応する圧縮率範囲及び長さの範囲に従って期待長を選択し、コンテンツ・デファインド・チャンキング方法を使用することにより、選択された期待長に従ってデータセグメントをチャンク（Chunk）系列に分割するステップと、(d)異なるデータセグメントにある隣接するチャンクを接合し、データ重複排除のための各チャンクのハッシュ値を計算するステップであり、接合ステップは任意選択のステップであり、ハッシュ値は接合なしに直接計算されてもよいステップとを含む。ステップ(b)において、データオブジェクトは、ブロック系列のサンプル圧縮率情報を使用することにより、データセグメント系列に再び分割される。複数の分割方法が存在してもよく、例えば、他の実現方式では、ステップ(b)において、圧縮率範囲に参照が行われなくてもよく、代わりにサンプル圧縮率の値の間の差が指定された閾値未満にある隣接する連続ブロックが１つのデータセグメントにされてもよい。
【００１８】
＜実施例１＞
図１を参照すると、以下は、本発明の実施例によるデータオブジェクト処理方法を詳細に説明した具体的なステップを使用する。
【００１９】
ステップ11：重複排除されるべきデータオブジェクトを１つ以上のブロックに分割し、各ブロックのサンプル圧縮率を計算し、同じ圧縮率特性を有する隣接する連続ブロックを１つのデータセグメントに集約し、データセグメントのそれぞれのサンプル圧縮率を取得する。各ブロックは、固定長でもよく、可変長でもよい。ブロックが可変長である場合、特定の範囲内のランダムな長さがブロックの長さとして選択されてもよい。或いは、データオブジェクトは、異なる期待長を有する候補チャンク境界の複数のグループを出力するようにスキャンされてもよく、候補チャンク境界の複数のグループのうち１つがデータオブジェクトを１つ以上の可変長ブロックに分割するために使用される。
【００２０】
圧縮率は、データが圧縮可能な程度を測定するために使用され、圧縮率=圧縮データの量／元のデータの量として計算される。圧縮率を推定する方法は、サンプリングレートSに基づいて各ブロックからサンプルデータのセグメントを抽出し、データ圧縮アルゴリズム、例えば、可逆圧縮アルゴリズムLZアルゴリズム及びRLE符号化を使用することによりサンプルデータを圧縮し、圧縮率を計算し、サンプルの圧縮率をサンプリングされたブロックの圧縮率として使用するものである。更に高いサンプリングレートは、サンプルの圧縮率がサンプリングされたブロックの実際の圧縮率に更に近くなることを意味する。
【００２１】
圧縮可能なデータセグメントでは、その圧縮率は一般的に1未満である。圧縮不可能なデータセグメントでは、記述フィールドのようなメタデータのオーバーヘッドの追加のため、圧縮符号化の後のデータセグメントの長さは、元のデータ長より大きくなってもよい。このことは、圧縮率が1より大きくなることを引き起こしてもよい。圧縮率のエントリは、一連の圧縮率範囲を含み、異なる圧縮率範囲の間の交わりは空であり、全ての圧縮率範囲の結合は、完全な圧縮率の値の範囲[0,∞)を構成する。
【００２２】
圧縮率特性は、ブロックを集約するパラメータとして圧縮率を使用することを示す。圧縮率又はブロックの圧縮レート演算から取得された値が予め設定された条件を満たす場合、ブロックは圧縮率特性に従う。具体的に、圧縮率特性は、圧縮率範囲、すなわち、圧縮率の範囲でもよく、また、隣接するブロックの圧縮率の値の間の差の閾値でもよい。表１を参照すると、圧縮率範囲が圧縮率特性として使用されている。データオブジェクトは、ブロック1〜7の７個のブロックに分割される。各ブロックでサンプリングを実行し、これらの圧縮率を推定することにより、各ブロックのサンプル圧縮率が取得される。例えば、ブロック1のサンプル圧縮率は0.4であり、ブロック2のサンプル圧縮率は0.42である。各サンプル圧縮率は、１つの圧縮率範囲に属する。例えば、圧縮率0.4は圧縮率範囲[0,0.5)に属し、圧縮率0.61は圧縮率範囲[0.5,0.8)に属する。各ブロックは１つのサンプル圧縮率に対応するため、各ブロックが１つの圧縮率範囲に属するとも考えられてもよい。同じ圧縮率範囲に属するブロックは１つのデータセグメントに集約される。従って、ブロック1及びブロック2はデータセグメント1に集約されてもよく、ブロック3、ブロック4及びブロック5はデータセグメント2に集約されてもよく、ブロック6及びブロック7はデータセグメント3に集約されてもよい。
【表１】
2016515250.tif 000003
【００２３】
ステップ12：各データセグメントの長さが属する長さの範囲と、各データセグメントのサンプル圧縮率が属する圧縮率範囲とに従って、データセグメントをデータチャンクに分割するための期待長を選択する。データセグメントの長さの値の範囲は、長さの範囲の少なくとも１つに分類され、データセグメントのそれぞれの長さは、長さの範囲の１つに一意に属し、データセグメントのそれぞれのサンプル圧縮率は、サンプル圧縮率範囲の１つに一意に属する。
【００２４】
異なる圧縮率範囲は交わらず、異なる長さの範囲は交わらず、圧縮率範囲及び長さの範囲のそれぞれの組み合わせは、１つの期待長に対応する。各データセグメントのサンプル圧縮率は、１つの圧縮率範囲に一意に属し、各データセグメントの長さは、１つの長さの範囲に一意に属する。データセグメントのサンプル圧縮率は、データセグメントにおいてサンプリング及び圧縮を実行することにより取得されてもよく、データセグメントを形成するブロックのサンプル圧縮率の平均値を計算することにより取得されてもよい。平均値は、算術平均でもよい。或いは、各ブロックの長さに基づいてブロックのサンプル圧縮率の加重平均を計算することにより取得されてもよい。具体的な方法は、データセグメントを形成するブロックのサンプル圧縮率をフラグ値として使用し、ブロックの長さを重みとして使用することにより、ブロックのサンプル圧縮率の加重平均を計算することである。
【００２５】
データセグメントをデータチャンクに分割する場合、データチャンクの境界が見つけられる必要がある。データチャンクは、隣接する境界の間にある。
【００２６】
ステップ11で使用されるブロックを分割する方法が、異なる期待長を有する候補チャンク境界の複数のグループを計算し、候補チャンク境界の複数のグループのうち１つを使用することにより、データオブジェクトを１つ以上の可変長ブロックに分割することである場合、ステップ12は、選択された期待長に従って、候補チャンク境界の複数のグループから、データセグメントをデータチャンクに分割するための同じ期待長を有するチャンク境界を選択することでもよい。すなわち、データセグメントを再びスキャンする代わりに、ステップ11におけるスキャンにより取得された候補境界の複数のグループから対応するチャンク境界を選択する。他の方法、例えば、固定長ブロックを使用する方法がブロックを分割するためにステップ11で使用される場合、ステップ12は、データセグメントをデータチャンクに分割するために、期待長を選択し、データセグメントをスキャンすることにより各ブロックの境界を見つけることでもよい。異なる期待長を有する候補チャンク境界の複数のグループを計算する方法と比べて、後者の方法は、データセグメントをスキャンすることによりデータチャンクの境界を見つける１つ以上のステップを有する。
【００２７】
表２の例を参照すると、圧縮率の値の範囲は、３つの圧縮率範囲[0,0.5)、[0.5,0.8)及び[0.8,∞)に分割される。圧縮率範囲の間に交わりは存在せず、各データセグメントのサンプル圧縮率は、１つの圧縮率範囲に属する。このことはまた、各データセグメントが１つの圧縮率範囲に対応することとして理解されてもよい。更に、データセグメントの長さの値の範囲は、少なくとも１つの長さの範囲に分割される。長さの範囲の間に交わりは存在せず、従って、各データセグメントは、１つの長さの範囲に対応する。長さの範囲及び圧縮率範囲は、併せてデータセグメントの期待長を決定する。例えば、データセグメントAの長さの範囲が[0MB,10MB)であり、データセグメントAのサンプル圧縮率が圧縮率範囲[0,0.5)内にあり、長さの範囲[0MB,10MB)及び圧縮率範囲[0,0.5)により併せて決定された期待長が32KBである場合、データセグメントAの期待長は32KBである。同様に、データセグメントBの長さが属する長さの範囲と、データセグメントBのサンプル圧縮率が属する圧縮率範囲とに従って、データセグメントBの期待長が256KBであることが取得されてもよい。期待長が取得された後に、各データセグメントは、期待長に従ってデータチャンクに分割されてもよい。例えば、データセグメントAは、期待長32KBに従ってデータチャンクに分割され、データセグメントBは、期待長256KBに従ってデータチャンクに分割される。KBにおけるBはバイト（Byte）の省略であり、1KB=1024Bytesであり、1MB=1024KBである。
【００２８】
期待長は理論値であるため、データチャンクの実際の長さは異なってもよい。すなわち、データチャンクは可変長である。しかし、データセグメントAから分割されたデータチャンクの平均チャンク長は、期待長32KBに近く、従って、可変長のこれらのデータチャンクの長さの値が32KBであることが最高の確率になり、32KBがピーク長でもある。本発明の実施例では、各期待長は１つのピーク長に対応し、従って、本発明の実施例は、複数のピーク長が存在するデータチャンキング及び重複排除方法を提供する。
【表２】
2016515250.tif 000004
【００２９】
この実施例では、期待長は、経験値を使用することにより、又は分析統計を用いて取得されてもよい。表２に示すように、期待長を決定するための任意選択のルールは、圧縮率範囲が同じである場合、長さの範囲の下限値が増加するほど対応する期待長が増加し、他方、長さの範囲が同じである場合、圧縮率範囲の下限値が増加するほどマッピングテーブルの対応する期待長が増加することである。データセグメントの期待チャンク長は、データセグメントのサンプル圧縮率が属する圧縮率範囲の下限値と、データセグメントの長さが属する長さの範囲の下限値とに正相関する。或る場合には、大きいデータオブジェクト及び圧縮することが困難なデータオブジェクトの重複排除率は、チャンキング粒度にとって敏感ではなく、期待長を使用したチャンキング方法は、重複排除率を急速に悪化させることなくチャンクの数を急速に低減することができる。
【００３０】
データセグメント内のデータチャンクの位置に基づいて、データセグメントから分割されたデータチャンクは順序になっており、順序におけるデータチャンクはデータチャンク系列を形成する。データチャンク系列は、チャンキングサブ系列と呼ばれてもよい。ステップ12はまた、分割からの異なるデータチャンクにより生成されたチャンキングサブ系列を接合し、データオブジェクトのチャンキング系列を形成することを含んでもよい。チャンキング系列におけるチャンクの順序は、データオブジェクトにおけるチャンクデータの順序と同じである。
【００３１】
ステップ13：隣接するデータセグメントについて、前のデータセグメントの終わりのデータチャンクと、次のデータセグメントの開始のデータチャンクとをデータチャンクに接合する。接合の後に形成されたデータチャンクは、接合データチャンクと呼ばれてもよい。ステップ13は任意選択のステップである。例えば、ステップ11のデータセグメントの境界が固定長ブロックの境界である場合、ステップ13が使用されてもよく、接合は、固定長ブロックの境界がチャンクの境界として使用されることを回避することができる。このことは、更に良い重複排除効果を達成し得る。
【００３２】
更に、２つのデータセグメントの間の遷移の領域で生成された接合データチャンクでは、接合データチャンクの２つの側における隣接するデータチャンクは、それぞれ異なる期待長に対応する。任意選択で、２つの期待長の間の更に小さい値は、接合データチャンクを更に細かい粒度のデータチャンクに分割するために採用されてもよい。これにより、２つのデータセグメントの間の遷移の領域において重複コンテンツが更に良好に識別され得る。このことは、データチャンクの総数のわずかな増加を引き起こしつつ、重複排除効果を改善する。他の実施例では、２つの期待長の間の更に小さい値未満の期待長も、接合データチャンクを更に細かい粒度のデータチャンクに分割するために採用されてもよい。
【００３３】
ステップ12がチャンキングサブ系列を接合するステップを含む場合、ステップ13は、チャンキングサブ系列が接合される前に実行されてもよく、また、チャンキングサブ系列が接合された後に実行されてもよい。
【００３４】
ステップ14：データチャンクのそれぞれのフィンガープリントを計算し、フィンガープリントを使用することにより、データチャンクのそれぞれが記憶デバイスに記憶されているか否かを決定し、記憶デバイスに記憶されていないデータチャンクを、記憶されていないデータチャンクに対応するフィンガープリント及びサンプル圧縮率と共に記憶デバイスに送信する。
【００３５】
フィンガープリントは、データチャンクを一意に識別するために使用され、データチャンク及びデータチャンクに対応するフィンガープリントは、１対１の対応関係を有する。フィンガープリント計算方法は、データチャンクのハッシュ（Hash）値をフィンガープリントとして計算することである。
【００３６】
ステップ15：記憶デバイスは、受信したデータ及びデータチャンクのフィンガープリントを記憶する。記憶中に、記憶デバイスは、受信したデータチャンクのサンプル圧縮率が圧縮率閾値に従うか否かを決定してもよい。そして、記憶空間を節約するために、圧縮率閾値に従うデータチャンクを圧縮して記憶し、圧縮率閾値に従わないデータを、そのデータを圧縮することなく直接記憶する。例えば、圧縮率閾値が0.7以下である場合、サンプル圧縮率が0.7以下であるデータチャンクは、圧縮された後に記憶されてもよく、サンプル圧縮率が0.7より大きいデータは、圧縮されることなく直接記憶される。
【００３７】
ステップ11において１つより多くのセグメンテーション方式が使用されてもよい点に留意すべきである。例えば、他の実現方式では、ステップ11で使用されるセグメンテーションポリシーは、サンプル圧縮率の値の間の差が指定された閾値未満である隣接する連続ブロックを１つのデータセグメントに集約することとして変更されてもよい。換言すると、サンプル圧縮率の値の間の差が指定された閾値未満であることが、圧縮率特性である。依然として表１が例として使用される。サンプル圧縮率の値の間の差が0.1未満であることが閾値として使用されることを仮定する。この場合、0.42-0.4<0.1であるため、ブロック1及びブロック2は１つのデータセグメントに配置される。0.53-0.42>0.1であるため、ブロック3及びブロック2は１つのデータセグメントに配置されない。類推して、ブロック1及びブロック2は第１のデータセグメントに配置され、ブロック3及びブロック4は第２のデータセグメントに配置され、ブロック5、ブロック6及びブロック7は第３のデータセグメントに配置される。
【００３８】
＜実施例２＞
図２に示すように、実施例２について詳細に説明する。この実施例によるデータオブジェクト処理方法は以下のステップを含む。
【００３９】
21：チャンキングポリシー・マッピングテーブルをロードする。表１及び表２を参照すると、チャンキングポリシー・マッピングテーブルは、どの圧縮率が同じ圧縮率特性を有するかを記録する。更に、チャンキングポリシー・マッピングテーブルは、データセグメントの長さが属する長さの範囲と、データセグメントの圧縮率が属する圧縮率範囲と、長さの範囲及び圧縮率範囲により併せて決定される期待長とを更に記録する。期待長は、データセグメントをデータチャンクに分割するために使用される。このステップはまた、チャンキングポリシー・マッピングテーブルが使用される必要がある前にロードされる限り、後に実行されてもよい。
【００４０】
22：処理される必要のあるデータオブジェクトを、この方法を実現する装置に入力する。換言すると、処理される必要のあるデータオブジェクトを取得する。データオブジェクトを取得する源は、この方法を実現する装置でもよく、この方法を実現する装置に接続された外部の装置でもよい。
【００４１】
23：固定長を使用することによりデータオブジェクトを分割する。具体的な実現では、このステップにおいて、データオブジェクトは、各固定長ブロックの境界を取得するためにスキャンされる必要がある。２つの隣接する境界の間のデータはブロックである。
【００４２】
24：各ブロックのデータにおいてサンプリング及び圧縮を実行し、サンプリング及び圧縮により取得された圧縮率を全体ブロックのデータサンプル圧縮率として使用する。
【００４３】
25：チャンキングポリシー・マッピングテーブルに従って同じ圧縮率特性を有する連続ブロックをデータセグメントに集約する。
【００４４】
26：チャンキングポリシー・マッピングテーブルに従って各データセグメントを指定された期待長のデータチャンクに分割する。具体的な実現では、このステップにおいて、各データセグメントは、データチャンクの境界を見つけるためにスキャンされる必要があり、データセグメントは、一連のデータチャンクを形成するために境界を使用することにより分割される。
【００４５】
この実施例では、データ26が実行された後に、データオブジェクトの処理が完了し、データオブジェクトをデータチャンクに分割する効果が達成される。後のステップ27、28及び29は、データオブジェクト処理方法に対する更なる拡張である。
【００４６】
27：各データセグメントにより生成されたチャンキングサブ系列を接合する。各データセグメントを分割することにより形成されたデータチャンクは、データセグメントにおけるデータチャンクの位置と同じ順序になっており、順序におけるデータチャンクは、チャンキングサブ系列と呼ばれてもよい。このステップにおいて、接合方式は、いずれか２つの隣接するデータセグメントについて、データセグメントの間の境界を除去し、複数のチャンキングサブ系列を結合し、全体データオブジェクトのデータチャンク系列を形成するように、前のデータセグメントの終わりのデータチャンクと、次のデータセグメントの開始のデータチャンクとをデータチャンクに接合することである。任意選択で、このステップにおいて接合されたデータチャンクは、更に細かい粒度のデータチャンクに分割されてもよい。このことは、重複排除効果を改善する。他の接合方法は、全体データオブジェクトのデータチャンク系列を形成するために、各データチャンクを変更せずに保持したまま、次のデータセグメントの開始のデータチャンクが前のデータセグメントの終わりのデータチャンクによって先行される、データオブジェクトにおけるデータセグメントの順序に従って、各データセグメントのチャンキングサブ系列をソートすることである。
【００４７】
28：チャンクのハッシュ値をフィンガープリントとして計算する。
【００４８】
29：チャンク及び各チャンクのフィンガープリントを出力し、任意選択で、各チャンクのサンプル圧縮率も出力されてもよい。チャンクのサンプル圧縮率は、チャンクが属するセグメントのサンプル圧縮率を使用することによる計算を通じて取得されてもよく、１つの方式は、セグメントのサンプル圧縮率をそのセグメントのチャンクのサンプル圧縮率として直接使用することである。
【００４９】
１つより多くのデータオブジェクトが存在する場合、全てのデータオブジェクトが処理されるまでステップ22〜29を繰り返す。
【００５０】
前述のステップを実現する具体的な方法は、w-bytesのスライディングウィンドウを使用することによりデータオブジェクトをスキャンし、それぞれ1バイトの前進スライディングにおいてラピッド・ハッシュ・アルゴリズムを採用することにより、ウィンドウ内のデータのフィンガープリントf(w-bytes)を再計算し、現在のデータセグメントの期待長がEである場合、式Match(f(w-bytes),E)=Dが有効であるか否かに基づいて、現在のフィンガープリントがチャンク境界フィルタ基準を満たすか否かを決定することである。ただし、整数D∈[0,E)は、予め規定された固有値であり、関数Match(・)は、f(w-bytes)を範囲[0,E)にマッピングするために使用される。ハッシュ関数f(・)はランダムであるため、フィルタ基準は、ピーク長がEである一連のチャンクを出力することができる。この処理が新たなデータセグメントに到達した場合、新たなデータセグメントの期待長Eが変化する。従って、新たなピーク長のチャンキングサブ系列が出力される。２つのデータセグメントの隣接する領域でチャンキングを実行する場合、データチャンクの前者の境界は、前のデータセグメントの期待長により決定され、後者の境界は、次のデータセグメントの期待長により決定される。従って、データチャンクの前者及び後者の境界は、それぞれ２つのセグメント内にあり、このことは、処理がセグメント境界をチャンク境界として使用しないように、隣接するセグメントの間のチャンキングサブ系列が自動的に接合されることと等価である。
【００５１】
理解を容易にするために、実施例２は、図３に示すフローチャートを更に提供する。ステップの処理は、連続して、3a,データオブジェクト処理方法が実行される必要のあるデータオブジェクトを入力するステップであり、データオブジェクトは、データオブジェクト処理がデータオブジェクトにおいて実行される前にバッファに一時的に記憶されてもよいステップ、3b,データオブジェクトにおいてブロック分割、サンプリング及び圧縮率推定を実行するステップであり、L、M及びHはそれぞれ３つの異なる圧縮率範囲を表すステップ、3c,同じ圧縮率特性を有する連続ブロックをデータセグメントに集約するステップ、3d,各データセグメントの圧縮率及び長さの特性に従って期待長を選択し、チャンク境界を計算し、計算されたチャンク境界に従って各データセグメントをデータチャンクに分割するステップであり、各データセグメントから分割されたデータチャンクはチャンキングサブ系列を形成するステップ、及び3e,データセグメントのチャンキングサブ系列を接合し、チャンキングフィンガープリントを計算するステップである。
【００５２】
＜実施例３＞
実施例２では、重複排除されるべきデータオブジェクトは、複数の固定長ブロックに分割される。しかし、実施例３では、期待長を使用することにより、重複排除されるべきデータオブジェクトにおいて事前チャンキングが実行される。具体的に、データオブジェクト（ファイル／データストリーム）は、コンテンツ・デファインド・チャンキング方法を使用することによりスキャンされ、異なる期待長を有する候補チャンク境界の複数のグループが生成される。候補チャンク境界の各グループは、データオブジェクトの１つの候補チャンキング系列に対応し、チャンキング系列はまた、その後のチャンキングの解決策として理解されてもよい。事前チャンキングの解決策の１つは、データオブジェクトをブロックに分割するために使用される。サンプリング及び圧縮は、ブロックにおいて実行され、データセグメントを分割する方法が決定され、データセグメントをデータチャンクに分割する後のステップにおいて、対応する候補チャンク境界が、期待長に従ってデータチャンクを分割するために選択される。
【００５３】
従って、実施例２では、データオブジェクトがブロックに分割される場合、且つ、データセグメントがデータチャンクに分割される場合、データオブジェクトがスキャンされる必要がある。この実施例では、データオブジェクトは１回のみスキャンされる必要があり、これにより、システムリソースを節約し、データオブジェクトの処理効率を改善する。更に、実施例３のブロック及び又はデータチャンクの境界は候補チャンク境界に基づくため、ブロック集約により生成されたセグメント境界は重複排除に逆効果を有さない。このことは、データチャンクのセグメント境界を除去するための動作を実行する必要はないことを意味する。換言すると、隣接するデータセグメントについて、データチャンクを形成するために、前のデータセグメントの終わりのデータチャンクと次のデータセグメントの開始のデータチャンクとを接合する必要はない。
【００５４】
更に小さい期待長は、更に細かい平均チャンキング粒度を意味し、データコンテンツの部分圧縮率の変化を認識するのに更に助けになる。更に大きい期待長は、更に粗い平均チャンキング粒度を意味する。
【００５５】
図４に示すように、この実施例で提供されるデータオブジェクト処理方法は、具体的に以下のステップを含んでもよい。
【００５６】
41：チャンキングポリシー・マッピングテーブルをロードする。表１及び表２を参照すると、チャンキングポリシー・マッピングテーブルは、どの圧縮率が同じ圧縮率特性に属するかを記録する。更に、チャンキングポリシー・マッピングテーブルは、データセグメントの長さが属する長さの範囲と、データセグメントの圧縮率が属する圧縮率範囲と、長さの範囲及び圧縮率範囲により併せて決定される期待長とを更に記録する。期待長は、データセグメントをデータチャンクに分割するために使用される。このステップはまた、チャンキングポリシー・マッピングテーブルが使用される必要がある前にロードされる限り、後に実行されてもよい。
【００５７】
42：処理される必要のあるデータオブジェクトを、この方法を実現する装置に入力する。換言すると、処理される必要のあるデータオブジェクトを取得する。データオブジェクトを取得する源は、この方法を実現する装置でもよく、この方法を実現する装置に接続された外部の装置でもよい。
【００５８】
43：スキャン処理において、候補チャンク境界の複数のグループを出力する。候補チャンク境界の各グループ及び期待長は１対１の対応関係を有する。これらの期待長は、後のステップにおけるデータセグメントに対応する期待長を含む。
【００５９】
44：ステップ43における候補チャンク境界の複数のグループから候補チャンク境界の１つのグループを選択し、選択された候補境界のグループにより形成された候補チャンキング系列においてサンプリング及び圧縮を実行する。このステップは、データオブジェクトをブロックに分割する。ブロックの期待長は、ステップ43で使用される複数の期待長のうち１つである。ブロック分割が期待長に従って実行される場合、データオブジェクトは、再びスキャンされる必要はなく、期待長に対応する候補チャンク境界に従って直接ブロックに分割される。次に、各ブロックのデータにおいてサンプリング及び圧縮を実行し、サンプリング及び圧縮により取得された圧縮率を全体ブロックデータのサンプル圧縮率として使用する。
【００６０】
45：チャンキングポリシー・マッピングテーブルに従って同じ圧縮率特性を有する連続ブロックをデータセグメントに集約する。
【００６１】
46：チャンキングポリシー・マッピングテーブルに従って、各データセグメントの期待長に対応する候補チャンク境界を選択する。データチャンクの境界は、データチャンクの長さ及び位置を決定するため、このステップは、データセグメントをデータチャンクに分割する。前述のように、ステップ46における候補チャンク境界はステップ43から来たものである。このため、データセグメントがデータチャンクに分割されるときに、データオブジェクトは再びスキャンされる必要はなく、これにより、システムリソースを節約する。
【００６２】
この実施例では、データ46が実行された後に、データオブジェクトの処理が完了し、データオブジェクトをデータチャンクに分割する効果が達成される。後のステップ47、48及び49は、データオブジェクト処理方法に対する更なる拡張である。
【００６３】
47：隣接するデータセグメントのチャンキングサブ系列を接合する。データオブジェクトのデータチャンキング系列を形成するために、データオブジェクトにおけるデータセグメントの順序に従って各データセグメントのサブ系列をソートする。データチャンクはまた、チャンクと呼ばれてもよい。
【００６４】
48：データチャンクのハッシュ値をフィンガープリントとして計算する。
【００６５】
49：チャンク及びチャンクのフィンガープリントを出力し、任意選択で、チャンクのサンプル圧縮率も出力されてもよい。チャンクのサンプル圧縮率は、チャンクが属するセグメントのサンプル圧縮率を使用することによる計算を通じて取得されてもよく、１つの方式は、セグメントのサンプル圧縮率をそのセグメントのチャンクのサンプル圧縮率として直接使用することである。
【００６６】
データチャンクを記憶する場合、チャンクのサンプル圧縮率に従って、データチャンクが記憶される前に圧縮される必要があるか否かを決定する。
【００６７】
データ処理が完了していない場合、すなわち、１つより多くのデータオブジェクトが存在する場合、全てのデータオブジェクトが処理されるまで、残りのオブジェクトにおいてステップ42〜49が連続して実行される。
【００６８】
前述のステップ43を実現する具体的な方法は、この処理において、表２に示すチャンキングポリシー・マッピングテーブルの全ての期待長Ei及び対応する固有値Diをパラメータリストに構成し、異なるパラメータ<Ei,Di>を連続して使用することにより、スライディングウィンドウにより出力された各フィンガープリントf(w-bytes)が合致条件Match(f(w-bytes),Ei)=Diを満たすか否かを決定し、フィンガープリントが合致条件を満たす場合、現在のウィンドウEiに対応する候補チャンク境界が選択される。フィンガープリント合致効率は、パラメータ<Ei,Di>を最適化することにより改善され得る。例えば、Match(f(w-bytes),Ei)=f(w-bytes)  mod  Eiが規定され、E0=212B=4KB、E1=215B=32  KB、D0=D1=0が選択されたときに、f(w-bytes)  mod  E0≠D0である場合、明らかにf(w-bytes)  mod  E1≠D1が生じる。すなわち、１つのフィンガープリントが期待長4KBに対応するフィルタ基準を満たさない場合、フィンガープリントが期待長32KBに対応するフィルタ基準を満たすか否かを検査し続ける必要はない。
【００６９】
理解を容易にするために、実施例３は、図５に示すフローチャートを更に提供する。図５のステップは、5a,データオブジェクト処理方法が実行される必要のあるデータオブジェクトを出力するステップであり、データオブジェクトは、データオブジェクト処理がデータオブジェクトにおいて実行される前にバッファに一時的に記憶されてもよいステップ、5b,異なる期待長を使用することにより、候補チャンク境界の複数のグループを決定するステップ、5c,5bにおいて決定された候補チャンク境界の複数のグループの中で、データオブジェクトを分割して分割後に取得されたチャンクにおいてサンプリング及び圧縮率推定を実行するために、候補チャンキング系列のグループを選択するステップ、5d,同じ圧縮率特性を有する連続候補ブロックをデータセグメントに集約するステップ、5e,各データセグメントの圧縮率及び長さの特性に従って期待長及び対応するチャンク境界を選択するステップであり、対応するチャンク境界に従って各データセグメントから分割されたデータチャンクはチャンキングサブ系列を形成するステップ、及び5f,データセグメントのチャンキングサブ系列を接合し、チャンキングフィンガープリントを計算するステップである。
【００７０】
＜実施例４＞
図６を参照すると、この実施例は、実施例１、実施例２及び実施例３で提供される方法が適用されるデータオブジェクト処理装置6を説明する。データオブジェクト処理装置6は、ブロック分割モジュール61と、データセグメント生成モジュール62と、データチャンク生成モジュール63とを含む。
【００７１】
オブジェクト処理装置6において、ブロック分割モジュール61は、データオブジェクトを１つ以上のブロックに分割するように構成される。データセグメント生成モジュール62は、各ブロックのサンプル圧縮率を計算し、同じサンプル圧縮率特性を有する連続ブロックを１つのデータセグメントに集約し、データセグメントのそれぞれのサンプル圧縮率を取得するように構成される。データチャンク生成モジュール63は、データセグメントのそれぞれの長さが属する長さの範囲と、データセグメントのそれぞれのサンプル圧縮率が属する圧縮率範囲とに従って、データセグメントをデータチャンクに分割するための期待長を選択するように構成され、データセグメントのそれぞれのサンプル圧縮率は、圧縮率範囲の１つに一意に属し、データセグメントのそれぞれの長さは、長さの範囲の１つに一意に属する。
【００７２】
具体的に、ブロック分割モジュール61は、データオブジェクトを１つ以上の固定長ブロックに分割するように構成されてもよく、また、異なる期待長を有する候補チャンク境界の複数のグループを計算し、候補チャンク境界の複数のグループのうち１つを使用することにより、データオブジェクトを１つ以上の可変長ブロックに分割するように構成されてもよい。
【００７３】
データセグメント生成モジュール62は、各ブロックのサンプル圧縮率を計算し、サンプル圧縮率が同じ圧縮率範囲に属する隣接する連続ブロックを１つのデータセグメントに集約し、データセグメントのそれぞれのサンプル圧縮率を取得するように具体的に構成される。
【００７４】
データセグメント生成モジュール62は、各ブロックのサンプル圧縮率を計算し、サンプル圧縮率の値の間の差が指定された閾値未満である隣接する連続ブロックを１つのデータセグメントに集約し、データセグメントのそれぞれのサンプル圧縮率を取得するように具体的に更に構成される。
【００７５】
データオブジェクト処理装置6の様々な可能な実現解決策では、データチャンク生成モジュール63の機能である、データセグメントをデータチャンクに分割するための期待長を選択することは、具体的に、選択された期待長に従って、ブロックモジュールにより計算された候補チャンク境界の複数のグループから、データセグメントをデータチャンクに分割するための同じ期待長を有するチャンク境界を選択することでもよい。
【００７６】
データチャンク生成モジュール63は、隣接するデータセグメントについて、前のデータセグメントの終わりのデータチャンクと、次のデータセグメントの開始のデータチャンクとを接合データチャンクに接合するように更に構成されてもよい。更に、データチャンク生成モジュール63は、接合データチャンクを複数のデータチャンクに分割するように更に構成されてもよい。分割に使用される期待長は、前のデータセグメントに対応する期待長以下であり、分割に使用される期待長は、次のデータセグメントに対応する期待長以下である。
【００７７】
更に、オブジェクト処理装置6は、データチャンク送信モジュール64を更に含んでもよい。データチャンク送信モジュール64は、データチャンクのそれぞれのフィンガープリントを計算し、フィンガープリントを使用することにより、データチャンクのそれぞれが記憶デバイスに記憶されているか否かを決定し、記憶デバイスに記憶されていないデータチャンクを、記憶されていないデータチャンクに対応するフィンガープリント及びサンプル圧縮率と共に記憶デバイスに送信するように構成される。記憶デバイスは、受信したデータチャンクのフィンガープリントを記憶し、受信したデータチャンクのサンプル圧縮率が圧縮率閾値に従うか否かを決定し、圧縮率閾値に従うデータチャンクを圧縮して記憶する。
【００７８】
オブジェクト処理装置6はまた、CPUとメモリとにより形成されるデバイスとして考えられてもよい。メモリは、プログラムを記憶し、CPUは、メモリのプログラムに従って実施例１、実施例２及び実施例３で提供される方法を実行する。オブジェクト処理装置6は、インタフェースを更に含んでもよい。インタフェースは、記憶デバイスに接続するために使用される。例えば、インタフェースの機能は、CPUにより処理された後に生成されたデータチャンクを記憶デバイスに送信することでもよい。
【００７９】
実施例の前述の説明に基づいて、当業者は、本発明が必要な一般的なハードウェアに加えてソフトウェアにより実現されてもよく、ハードウェアのみにより実現されてもよいことを明確に理解し得る。ほとんどの場合には、前者が好ましい実現方式である。このような理解に基づいて、従来技術に対して本質的に又は部分的に寄与する本発明の技術的解決策は、ソフトウェアプロダクトの形式で実現されてもよい。コンピュータソフトウェアプロダクトは、コンピュータのフロッピーディスク、ハードディスク又は光ディスクのような読み取り可能記憶媒体に記憶され、コンピュータデバイス（パーソナルコンピュータ、サーバ、ネットワークデバイス等でもよい）に対して本発明の実施例に記載の方法を実行するように命令する複数の命令を含む。
【００８０】
前述の具体的な実現方式は、本発明の目的、技術的解決策及び有利な効果を詳細に記載しているが、本発明の保護範囲を限定することを意図するものではない。本発明に開示された技術的範囲内で当業者により容易に考えられる如何なる変更又は置換も、本発明の保護範囲内に入るものとする。従って、本発明の保護範囲は、特許請求の範囲の保護範囲に従うものとする。
【図１】
2016515250.tif 000005
【図２】
2016515250.tif 000006
【図３】
2016515250.tif 000007
【図４】
2016515250.tif 000008
【図５】
2016515250.tif 000009
【図６】
2016515250.tif 000010
【手続補正書】
【提出日】平成27年9月15日(2015.9.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データオブジェクトを１つ以上のブロックに分割するステップと、
各ブロックのサンプル圧縮率を計算し、同じサンプル圧縮率特性を有する連続ブロックを１つのデータセグメントに集約し、前記データセグメントのそれぞれの前記サンプル圧縮率を取得するステップと、
前記データセグメントのそれぞれの長さが属する長さの範囲と、前記データセグメントのそれぞれの前記サンプル圧縮率が属する圧縮率範囲とに従って、前記データセグメントをデータチャンクに分割するための期待長を選択するステップであり、前記データセグメントのそれぞれの前記サンプル圧縮率は、前記圧縮率範囲の１つに属し、前記データセグメントのそれぞれの前記長さは、前記長さの範囲の１つに属するステップと
を有するデータオブジェクト処理方法。
【請求項２】
データオブジェクトを１つ以上のブロックに分割するステップは、
前記データオブジェクトを１つ以上の固定長ブロックに分割するステップである、請求項１に記載の方法。
【請求項３】
隣接するデータセグメントについて、前のデータセグメントの終わりのデータチャンクと、次のデータセグメントの開始のデータチャンクとを接合データチャンクに接合するステップを更に有する、請求項１又は２に記載の方法。
【請求項４】
前記接合データチャンクを複数のデータチャンクに分割するステップを更に有し、
分割に使用される前記期待長は、前記前のデータセグメントに対応する期待長以下であり、分割に使用される前記期待長は、前記次のデータセグメントに対応する期待長以下である、請求項３に記載の方法。
【請求項５】
データオブジェクトを１つ以上のブロックに分割するステップは、
異なる期待長を有する候補チャンク境界の複数のグループを計算し、前記候補チャンク境界の複数のグループのうち１つを使用することにより、前記データオブジェクトを１つ以上の可変長ブロックに分割するステップである、請求項１に記載の方法。
【請求項６】
前記データセグメントをデータチャンクに分割するための期待長を選択するステップは、
前記選択された期待長に従って、候補チャンク境界の複数のグループから、前記データセグメントをデータチャンクに分割するための同じ期待長を有するチャンク境界を選択するステップである、請求項１又は５に記載の方法。
【請求項７】
同じサンプル圧縮率特性を有する連続ブロックを１つのデータセグメントに集約するステップは、
前記サンプル圧縮率が同じ圧縮率範囲に属する隣接する連続ブロックを１つのデータセグメントに集約するステップ、又は
前記サンプル圧縮率の値の間の差が指定された閾値未満である隣接する連続ブロックを１つのデータセグメントに集約するステップである、請求項１に記載の方法。
【請求項８】
前記方法の後に、
前記データチャンクのそれぞれのフィンガープリントを計算し、前記フィンガープリントを使用することにより、前記データチャンクのそれぞれが記憶デバイスに記憶されているか否かを決定し、前記記憶デバイスに記憶されていない前記データチャンクを、記憶されていない前記データチャンクに対応する前記フィンガープリント及び前記サンプル圧縮率と共に前記記憶デバイスに送信するステップと、
前記記憶デバイスにより、受信したデータチャンクの前記フィンガープリントを記憶し、前記受信したデータチャンクの前記サンプル圧縮率が圧縮率閾値に従うか否かを決定し、前記サンプル圧縮率が前記圧縮率閾値に従う前記データチャンクを圧縮して記憶するステップと
を更に有する、請求項１又は３に記載の方法。
【請求項９】
前記データチャンクが取得されたセグメントの前記サンプル圧縮率は、前記データチャンクの前記サンプル圧縮率として使用される、請求項８に記載の方法。
【請求項１０】
前記データセグメントの前記サンプル圧縮率は、
前記データセグメントを形成する前記ブロックの前記サンプル圧縮率の算術平均を計算すること、又は
前記データセグメントを形成する前記ブロックの前記サンプル圧縮率をフラグ値として使用し、前記ブロックの長さを重みとして使用することにより、前記ブロックの前記サンプル圧縮率の加重平均を計算することである、請求項１に記載の方法。
【請求項１１】
データオブジェクトを１つ以上のブロックに分割するように構成されたブロック分割モジュールと、
各ブロックのサンプル圧縮率を計算し、同じサンプル圧縮率特性を有する連続ブロックを１つのデータセグメントに集約し、前記データセグメントのそれぞれの前記サンプル圧縮率を取得するように構成されたデータセグメント生成モジュールと、
前記データセグメントのそれぞれの長さが属する長さの範囲と、前記データセグメントのそれぞれの前記サンプル圧縮率が属する圧縮率範囲とに従って、前記データセグメントをデータチャンクに分割するための期待長を選択するように構成されたデータチャンク生成モジュールであり、前記データセグメントのそれぞれの前記サンプル圧縮率は、前記圧縮率範囲の１つに属し、前記データセグメントのそれぞれの長さは、前記長さの範囲の１つに属するデータチャンク生成モジュールと
を有するデータオブジェクト処理装置。
【請求項１２】
前記ブロック分割モジュールは、前記データオブジェクトを１つ以上の固定長ブロックに分割するように構成される、請求項１１に記載の装置。
【請求項１３】
前記データチャンク生成モジュールは、隣接するデータセグメントについて、前のデータセグメントの終わりのデータチャンクと、次のデータセグメントの開始のデータチャンクとを接合データチャンクに接合するように更に構成される、請求項１１又は１２に記載の装置。
【請求項１４】
前記データチャンク生成モジュールは、前記接合データチャンクを複数のデータチャンクに分割するように更に構成され、分割に使用される前記期待長は、前記前のデータセグメントに対応する期待長以下であり、分割に使用される前記期待長は、前記次のデータセグメントに対応する期待長以下である、請求項１３に記載の装置。
【請求項１５】
前記ブロック分割モジュールは、異なる期待長を有する候補チャンク境界の複数のグループを計算し、前記候補チャンク境界の複数のグループのうち１つを使用することにより、前記データオブジェクトを１つ以上の可変長ブロックに分割するように更に構成される、請求項１１に記載の装置。
【請求項１６】
前記データセグメントをデータチャンクに分割するための期待長を選択することは、
前記選択された期待長に従って、候補チャンク境界の複数のグループから、前記データセグメントをデータチャンクに分割するための同じ期待長を有するチャンク境界を選択することである、請求項１１又は１５に記載の装置。
【請求項１７】
前記データセグメント生成モジュールは、
各ブロックの前記サンプル圧縮率を計算し、前記サンプル圧縮率が同じ圧縮率範囲に属する隣接する連続ブロックを１つのデータセグメントに集約し、前記データセグメントのそれぞれの前記サンプル圧縮率を取得するように、或いは
各ブロックの前記サンプル圧縮率を計算し、前記サンプル圧縮率の値の間の差が指定された閾値未満である隣接する連続ブロックを１つのデータセグメントに集約し、前記データセグメントのそれぞれの前記サンプル圧縮率を取得するように構成される、請求項１１に記載の装置。
【請求項１８】
前記データチャンクのそれぞれのフィンガープリントを計算し、前記フィンガープリントを使用することにより、前記データチャンクのそれぞれが記憶デバイスに記憶されているか否かを決定し、前記記憶デバイスに記憶されていない前記データチャンクを、記憶されていない前記データチャンクに対応する前記フィンガープリント及び前記サンプル圧縮率と共に前記記憶デバイスに送信するように構成されたデータチャンク送信モジュールを更に有し、
前記記憶デバイスは、受信したデータチャンクの前記フィンガープリントを記憶し、前記受信したデータチャンクの前記サンプル圧縮率が圧縮率閾値に従うか否かを決定し、前記サンプル圧縮率が前記圧縮率閾値に従う前記データチャンクを圧縮して記憶するように構成される、請求項１１に記載の装置。
【請求項１９】
請求項１ないし１０のうちいずれか１項に記載の方法をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能記憶媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
期待長は、チャンキング粒度を制御するためのコンテンツ・デファインド・チャンキング（Content  Defined  Chunking、CDC）方法の主要なパラメータである。一般的に、CDC方法は、特定のデータオブジェクトについて可変長チャンク系列を出力する。様々なチャンクの長さは、統計的に正規分布に従い、期待長は、正規分布の平均値を調整するために使用される。一般的に、正規分布の平均値は、平均チャンク長により表される。確率変数が正規分布のもとでの最高の確率の平均値に割り当てられるため、平均チャンク長はまた、ピーク長とも呼ばれ、理想的な状況における期待長に等しくなり得る。例えば、CDC方法では、スライディングウィンドウ内のデータのフィンガープリントf(w-bytes)は、リアルタイムで計算される。f(w-bytes)の特定のビットが予め設定された値に合致する場合、スライディングウィンドウの位置は、チャンク境界として選択される。データコンテンツの更新は、ハッシュフィンガープリントのランダムな変化を生じ得るため、f(w-bytes)&0xFFF=0が合致条件として設定され、ただし、&は２進数フィールドにおけるビットのAND演算であり、0xFFFは4095の１６進数表現である場合、１つのフィンガープリントの合致は、理論上でf(w-bytes)の4096個のランダムな変化で生じる可能性がある。すなわち、チャンク境界は、スライディングウィンドウが4KB（4096バイト）前にスライドする毎に見つけられ得る。理想的な状況のもとでのチャンク長は、CDC方法における期待チャンク長（Expected  Chunk  Length）であり、略して期待長と呼ばれる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
ステップ11で使用されるブロックを分割する方法が、異なる期待長を有する候補チャンク境界の複数のグループを計算し、候補チャンク境界の複数のグループのうち１つを使用することにより、データオブジェクトを１つ以上の可変長ブロックに分割することである場合、ステップ12は、選択された期待長に従って、候補チャンク境界の複数のグループから、データセグメントをデータチャンクに分割するための同じ期待長を有するチャンク境界を選択することでもよい。すなわち、データセグメントを再びスキャンする代わりに、ステップ11におけるスキャンにより取得された候補チャンク境界の複数のグループから対応するチャンク境界を選択する。他の方法、例えば、固定長ブロックを使用する方法がブロックを分割するためにステップ11で使用される場合、ステップ12は、データセグメントをデータチャンクに分割するために、期待長を選択し、データセグメントをスキャンすることにより各ブロックの境界を見つけることでもよい。異なる期待長を有する候補チャンク境界の複数のグループを計算する方法と比べて、後者の方法は、データセグメントをスキャンすることによりデータチャンクの境界を見つける１つ以上のステップを有する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】変更
【補正の内容】
【００２９】
この実施例では、期待長は、経験値を使用することにより、又は分析統計を用いて取得されてもよい。表２に示すように、期待長を決定するための任意選択のルールは、圧縮率範囲が同じである場合、長さの範囲の下限値が増加するほど対応する期待長が増加し、長さの範囲が同じである場合、圧縮率範囲の下限値が増加するほどマッピングテーブルの対応する期待長が増加することである。データセグメントの期待チャンク長は、データセグメントのサンプル圧縮率が属する圧縮率範囲の下限値と、データセグメントの長さが属する長さの範囲の下限値とに正相関する。或る場合には、大きいデータオブジェクト及び圧縮することが困難なデータオブジェクトの重複排除率は、チャンキング粒度にとって敏感ではなく、期待長を使用したチャンキング方法は、重複排除率を急速に悪化させることなくチャンクの数を急速に低減することができる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３６
【補正方法】変更
【補正の内容】
【００３６】
ステップ15：記憶デバイスは、受信したデータチャンク及びデータチャンクのフィンガープリントを記憶する。記憶中に、記憶デバイスは、受信したデータチャンクのサンプル圧縮率が圧縮率閾値に従うか否かを決定してもよい。そして、記憶空間を節約するために、圧縮率閾値に従うデータチャンクを圧縮して記憶し、圧縮率閾値に従わないデータを、そのデータを圧縮することなく直接記憶する。例えば、圧縮率閾値が0.7以下である場合、サンプル圧縮率が0.7以下であるデータチャンクは、圧縮された後に記憶されてもよく、サンプル圧縮率が0.7より大きいデータチャンクは、圧縮されることなく直接記憶される。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００４５
【補正方法】変更
【補正の内容】
【００４５】
この実施例では、ステップ26が実行された後に、データオブジェクトの処理が完了し、データオブジェクトをデータチャンクに分割する効果が達成される。後のステップ27、28及び29は、データオブジェクト処理方法に対する更なる拡張である。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
この実施例では、ステップ46が実行された後に、データオブジェクトの処理が完了し、データオブジェクトをデータチャンクに分割する効果が達成される。後のステップ47、48及び49は、データオブジェクト処理方法に対する更なる拡張である。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００７１
【補正方法】変更
【補正の内容】
【００７１】
データオブジェクト処理装置6において、ブロック分割モジュール61は、データオブジェクトを１つ以上のブロックに分割するように構成される。データセグメント生成モジュール62は、各ブロックのサンプル圧縮率を計算し、同じサンプル圧縮率特性を有する連続ブロックを１つのデータセグメントに集約し、データセグメントのそれぞれのサンプル圧縮率を取得するように構成される。データチャンク生成モジュール63は、データセグメントのそれぞれの長さが属する長さの範囲と、データセグメントのそれぞれのサンプル圧縮率が属する圧縮率範囲とに従って、データセグメントをデータチャンクに分割するための期待長を選択するように構成され、データセグメントのそれぞれのサンプル圧縮率は、圧縮率範囲の１つに一意に属し、データセグメントのそれぞれの長さは、長さの範囲の１つに一意に属する。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００７５
【補正方法】変更
【補正の内容】
【００７５】
データオブジェクト処理装置6の様々な可能な実現解決策では、データチャンク生成モジュール63の機能である、データセグメントをデータチャンクに分割するための期待長を選択することは、具体的に、選択された期待長に従って、ブロック分割モジュールにより計算された候補チャンク境界の複数のグループから、データセグメントをデータチャンクに分割するための同じ期待長を有するチャンク境界を選択することでもよい。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００７７
【補正方法】変更
【補正の内容】
【００７７】
更に、データオブジェクト処理装置6は、データチャンク送信モジュール64を更に含んでもよい。データチャンク送信モジュール64は、データチャンクのそれぞれのフィンガープリントを計算し、フィンガープリントを使用することにより、データチャンクのそれぞれが記憶デバイスに記憶されているか否かを決定し、記憶デバイスに記憶されていないデータチャンクを、記憶されていないデータチャンクに対応するフィンガープリント及びサンプル圧縮率と共に記憶デバイスに送信するように構成される。記憶デバイスは、受信したデータチャンクのフィンガープリントを記憶し、受信したデータチャンクのサンプル圧縮率が圧縮率閾値に従うか否かを決定し、圧縮率閾値に従うデータチャンクを圧縮して記憶する。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００７８
【補正方法】変更
【補正の内容】
【００７８】
データオブジェクト処理装置6はまた、CPUとメモリとにより形成されるデバイスとして考えられてもよい。メモリは、プログラムを記憶し、CPUは、メモリのプログラムに従って実施例１、実施例２及び実施例３で提供される方法を実行する。データオブジェクト処理装置6は、インタフェースを更に含んでもよい。インタフェースは、記憶デバイスに接続するために使用される。例えば、インタフェースの機能は、CPUにより処理された後に生成されたデータチャンクを記憶デバイスに送信することでもよい。
【国際調査報告】
2016515250.tif 000011
2016515250.tif 000012
2016515250.tif 000013
2016515250.tif 000014