(57)【特許請求の範囲】
【請求項１】
デジタルデータを分割し、保存するための、コンピュータによって実行される方法であって、
前記デジタルデータのフォーマットを判定する工程と、
前記デジタルデータ内のソース論理オブジェクトを特定する工程と、
を含んでおり、前記ソース論理オブジェクトを特定する工程は前記デジタルデータのフォーマットについての情報を適用することによって少なくとも部分的に達成され、
前記方法は更に、
判定された前記フォーマットに基づき、前記ソース論理オブジェクトから位置依存データを除去する処理、前記ソース論理オブジェクトからインスタンス依存データを除去する処理、前記ソース論理オブジェクトから一または複数のフォーマット固有のヘッダーもしくはフッターを除去する処理、および前記ソース論理オブジェクトからフォーマット固有の変換を除去する処理、のうちの一または複数を行い、新たなオブジェクトを作成する工程と、
前記新たなオブジェクトが既に保存されているか否かを判定する工程と、
前記新たなオブジェクトがまだ保存されていない場合、前記新たなオブジェクトを保存する工程と、
を含むことを特徴とする方法。
【請求項２】
前記デジタルデータが、デジタルファイル、ブロックベースのストレージ、バイナリ・ラージ・オブジェクト、およびデータストリームのうちの少なくとも一つであり、かつ、複合ファイルを含んでおり、前記ソース論理オブジェクトが前記複合ファイル内の一のファイルに保存されていることを特徴とする請求項１に記載の方法。
【請求項３】
請求項１に記載の方法であって、
付加的なデータを保存する工程を更に含んでおり、この付加的なデータは、前記位置依存データ、インスタンス依存データ、フォーマット固有のヘッダーもしくはフッター、および前記フォーマット固有の変換を示す情報のうちの一または複数を含んでおり、
前記方法は更に、
前記付加的なデータを前記新たなオブジェクトに関連付ける工程と、
保存された前記新たなオブジェクトと、関連付けられた前記付加的なデータとを用いて前記デジタルデータを再作成する工程と、を含むことを特徴とする方法。
【請求項４】
データを保存することができるメモリと、
プロセッサと、
を含むシステムであって、
前記プロセッサは、
デジタルデータのフォーマットを判定し、
前記デジタルデータ内のソース論理オブジェクトを特定するように構成されており、
前記ソース論理オブジェクトを特定することは前記デジタルデータのフォーマットについての情報を適用することによって少なくとも部分的に達成され、
前記プロセッサは更に、
決定された前記フォーマットに基づき、新しいオブジェクトを生成するために、前記ソース論理オブジェクトから位置依存データを除去する処理、前記ソース論理オブジェクトからインスタンス依存データを除去する処理、前記ソース論理オブジェクトから一または複数のフォーマット固有のヘッダーまたはフッターを除去する処理、および前記ソース論理オブジェクトからフォーマット固有の変換を除去する処理、前記新たなオブジェクトが既に保存されているか否かを判定する処理、前記新たなオブジェクトがまだ保存されていない場合に前記新たなオブジェクトを保存する処理、の一または複数を行うように構成されていることを特徴とするシステム。
【請求項５】
前記デジタルデータが、デジタルファイル、ブロックベースのストレージ、バイナリ・ラージ・オブジェクト、およびデータストリームのうちの少なくとも一つであり、かつ、複合ファイルであり、前記ソース論理オブジェクトが前記複合ファイル内の一のファイルに保存されていることを特徴とする請求項４に記載のシステム。
【請求項６】
請求項４に記載のシステムであって、
付加的なデータを保存することを更に含んでおり、この付加的なデータは、前記位置依存データ、インスタンス依存データ、フォーマット固有のヘッダーもしくはフッター、および前記フォーマット固有の変換を示す情報のうちの一または複数を含んでおり、
前記システムは更に、
前記付加的なデータを前記新たなオブジェクトに関連付けることと、
保存された前記新たなオブジェクトと、関連付けられた前記付加的なデータとを用いて前記デジタルデータを再作成することと、を含むことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、コンテンツアウェア・データ分割およびデータ重複排除のための方法ならびに装置に関するものである。
【背景技術】
【０００２】
（関連出願の相互参照）
本出願は、２００８年１２月１８日に出願された米国仮特許出願第６１／１３８，８２７号の優先権を主張するものであり、その内容全体を本願に援用する。
【０００３】
近年のコンピュータシステムは、急速に増大しつつある大量のデータを保持しており、実際に多くの場合には、この増大によりストレージシステム（記憶装置）の能力を上回ってしまう恐れがある。会社によっては、データの増加が一年で３０〜４０％にもなり得る。この増加により、より新しくより大きなストレージシステムに投資を続ける必要があるのみならず、これに対応してこうしたシステムを管理する費用も大きくなる。ストレージは会社の資本支出および運営費を著しく減少させることができるものであるため、会社内のストレージの量を減少させることが非常に望まれている。
【０００４】
ほとんどの大容量ストレージシステム（大容量記憶装置）において記憶（保存）されるデータの特性の一つは、非常に多くの重複データがあることである。例としては、複製ファイルや、僅かに異なるファイル（例えば、一の文書の複数の下書き）や、複数の文書に保存されている画像や、プレゼンテーション等に適用される同じテンプレートまたはひな形が含まれる。同一のファイルを検出することのできるシステムがいくつかあるが、それでもなお一般的なシステムは大量の重複データを保存する必要がある。例えば、特に会社における各文書はその中に埋め込まれた会社ロゴを有するが、今日のストレージ技術は、ロゴのための同じデータが全ての文書において繰り返されていることを認識することができず、それをストレージに保存することもできない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
バックアップやアーカイブといった主記憶装置および補助記憶装置のためのストレージおよびネットワークの占有面積を減らすために、サブファイルレベルで重複データを検出してサブファイルデータの重複排除をすることに強調が置かれてきている。最近では、サブファイルレベルで重複データを検出することができるように様々なシステムが設計されてきている。本質的に、全ての重複排除システムは、重複排除のために分析されるファイル記憶単位またはブロック記憶単位から一または複数の「チャンク」を作成し、重複するチャンクが作成されたか否かを検出するために一または複数の比較方法を用いる。
【０００６】
データをチャンキング（すなわち分割）する現在の方法は、重複除外のために評価されるデジタルデータ単位についての系統情報（ancestry information）がない状態で共通のサブオブジェクトを見つけることについて非効率的であることが多い。例えば、ある者がファイルＢがファイルＡから派生していると気づいた場合、その者はこれら２つのファイルを差分比較（デルタ比較）して共通のサブオブジェクトを見つけることができ、また、データを分割するために「スティッキー・ビット」法を用いることができる。しかしながら、系統情報なしに共通のサブオブジェクトを見つけることは、計算が極度に複雑になり、特に、系統情報が乏しい何千ものコンピュータシステムに亘って散りばめられた何百万ものファイルを有する、今日の高度に分散されたコンピュータシステムに適用する場合にはこれが顕著である。
【課題を解決するための手段】
【０００７】
本願は、デジタルデータ（例えば、ファイル、ブロック、ＢＬＯＢ（すなわちバイナリ・ラージ・オブジェクト）、またはストリームデータ）をコンテンツアウェアとオブジェクトとに基づき分割する方法およびシステム、または重複チャンクを特定する確率を高めるシステムおよび方法を提供するものである。これらのシステムおよび方法は様々な情報ストレージの状況のために用いることができ、これには以下のシナリオが含まれる。
１）  デジタルデータは一または複数の論理オブジェクトからなり、
２）  デジタルデータ内の論理オブジェクトは位置データを含んでおり、この位置データはオブジェクトの相対位置が変更された場合に変化し（例えば位置依存データ）、結果、そのオブジェクトにとって異なるバイトパターンになり、
３）  デジタルデータ内の論理オブジェクトはファイルが保存される毎に変化するメタデータを含んでおり（インスタンス依存データ）、係るメタデータの例は、作成者の名前、更新日時、改訂番号等であり、
４）  デジタルデータ内の論理オブジェクトは、オリジナルデータに変換（例えば圧縮／暗号化）が加えられた後に保存され、
５）  デジタルデータ内の論理オブジェクトは、特定のファイル、ブロックもしくはストリームに基づくストレージのインスタンスもしくは種類（タイプ）に固有の前に付けられたヘッダーや後ろに付けられたフッターと共に保存され、
６）  デジタルデータ内の同一の論理オブジェクトは、同一の種類または異なる種類の、異なるファイルまたはブロック記憶単位またはストリームに亘って共有され、
７）  論理オブジェクトをファイル／ブロック／ＢＬＯＢストレージに保存し、またはストリームで送信する間、この論理オブジェクトは複数の部分に分割され、および／または、
８）  複合ファイル／ブロック／ＢＬＯＢ／ストリームにおける論理オブジェクトが、ファイル・オブジェクトである（例えば、．ＰＳＴおよび．ＺＩＰファイルがこれらに埋め込まれた複数のファイル・オブジェクトを有する）。
【０００８】
重複するチャンクを特定するためにデジタルデータをチャンクに分割すると、位置データおよびメタデータが存在することにより、オブジェクトが保存される記憶単位の種類またはインスタンスに依って、同一の論理オブジェクトにとって異なるバイトパターンが保存される。バイトパターンは、その記憶単位における論理オブジェクトの位置に依っても異なり、更に、分割されるデジタルデータのフォーマットに固有の様々な変換に依っても異なる。結果として、様々なファイルもしくはブロックに基づく記憶単位／ストリームのバイトパターンを分析することに基づく従来の分割（チャンキング）の方法は、異なる記憶単位／ストリーム間で少しの共通性を見つけることができるのみである（これらは同一の論理オブジェクトを含むにもかかわらず）。用語「チャンク」および「論理オブジェクト（logical object）」は関連している。チャンクは、概して複数のファイルが共通して有し得る一連のデータである。チャンクは一のデジタルデータ単位に見られる論理オブジェクトまたは論理オブジェクトの一部分に基づき得る。
【０００９】
本願に記載する方法は、重複するチャンクを特定するためにデジタルデータをチャンクに分割する間、位置データ、インスタンス依存データ、フォーマット固有データ、および変換（例えば圧縮／暗号化）の効果を消滅させる。この方法によって、同一のファイルはもとより同一の種類もしくは異なる種類の異なるファイルに亘って共通するチャンクが作成され、従来の方法よりも重複するチャンクを特定する確率が高まる。この方法は、ネットワーク上で送信されるデータの量を減らすと共にバックアップもしくはアーカイブといった主記憶装置および補助記憶装置の占有面積を減らすために用いることができる。
【００１０】
本願に記載するシステムおよび方法は、デジタルデータシーケンス（例えばファイル）を分割するための完全に自動化された決定性処理を提供するものであり、複数の共通するオブジェクトもしくはチャンクが複数のコンピュータシステム（これらのコンピュータシステムは相互に関連していてもしていなくてもよい）において特定され、そこではこれらの共通するオブジェクトを見つける過程において他の処理手段と共に調査し、比較し、通信し、または協働するためにこれらのコンピュータ間で直接通信する必要性はない。
【００１１】
これらのシステムおよび方法の利点は、これらが使用する分割処理がうまく動作するために通信または比較を必要としないことである（従来の差分による因数分解システムとは対照的に）。この方法は分散された環境において特に効果的であり、デルタ属性分解システムが比較を必要としかつシーケンス同士を比較するために通信を必要とするのとは対照的に、本願発明のシステムおよび方法は、処理されるシーケンスのみを用いて孤立して遂行することができる。
【００１２】
一実施形態において、重複排除される必要があるデジタルデータ（ファイル、ブロック、ＢＬＯＢ、またはストリームに基づく）の任意の一部分からチャンクを作成するために、次の一または複数のステップが適用される。
１．  デジタルデータを保存または送信する様々なフォーマットについての情報を適用することによって、任意のデジタルデータを「全（ｗｈｏｌｅ）」論理オブジェクトに分割または「チャンキング」する。例えば、一の文書内にある一の画像が、この文書に固有のフォーマットに保存された「全」論理オブジェクトとなる。ファイルフォーマットには．ｐｐｔ、．ｄｏｃ、．ｘｌｓ、．ｐｐｔｘ、．ｄｏｃｘ、．ｘｌｓｘ、．ｐｄｆ、．ｘｍｌ、．ｃｐｐ、．ｏｎｅ、．ｍｄｂ、および．ａフォーマットが含まれる。
２．  「分割された」オブジェクトを扱う。すなわち、論理オブジェクトが隣接するストレージ／ストリームブロックに物理的に存在しない場合にこの論理オブジェクトを集めて組み立てる。場合によっては、論理オブジェクトを保存する間、この論理オブジェクトは複数のストレージ・ブロックに亘って散りばめられる数多くの小さなサブオブジェクトに分割され得る。この場合、この論理オブジェクトは、係る全てのサブオブジェクトが特定されてこれらが正しい順序に組み立てられた後に作成される。
３．  論理オブジェクトに適用されたフォーマット固有の変換を除去する。例えば、論理オブジェクトが一の記憶単位内で圧縮されたフォーマットに保存されている場合、この論理オブジェクトは重複排除のためにチャンクとして用いられる前にまず解凍される。同様に、論理オブジェクトが暗号化されて保存されている場合、この論理オブジェクトは重複排除のためにチャンクとして用いられる前に復号化される。
４．  論理オブジェクトに付けられたフォーマット固有のヘッダー／フッターを除去する。ほとんどのデジタルデータフォーマットは論理オブジェクトの前にヘッダーを付け、また、フッターを論理オブジェクトの一部として付けるか、論理オブジェクトを前記デジタルデータに挿入した後に付ける。
５．  位置特定データおよびメタデータを論理ブロックから除去する。多くのデジタルデータフォーマットは論理データ内またはこの周辺に位置データを保存する（例えばパワーポイント文書におけるスライド番号）。
６．  オブジェクトがファイル・オブジェクトであった場合、このファイル・オブジェクトをまず組み立ててから、上記ステップを用いて論理オブジェクトを抽出する。これにより、同一のオブジェクト（例えば．ＰＳＴ／．ＺＩＰといった複合ファイルフォーマットに埋め込まれたファイル・オブジェクト内の画像）を見つけることが可能になる。
【００１３】
上記一または複数のステップの後に残るものは、保存のために複数のサブオブジェクトに分割されたオブジェクトの効果と、フォーマット固有の変換と、埋め込まれた位置データと、周囲のメタデータとから独立している固有の形式（ｎａｔｉｖｅ  ｆｏｒｍ）の論理オブジェクトである。上記の方法を用いて得られた固有の形式の論理オブジェクトにおいて処理が行われることによって、無関係なファイルに亘ってもデータの重複チャンクを見つけることが可能になる。チャンクを特定するときに一のステップのみを適用することも可能であり、また、複数のステップを適用することも可能である。オブジェクトによっては異なるステップを使用することができ、使用される特定のステップはファイルの種類およびオブジェクトの種類に依存する。
【００１４】
上記システムおよび方法は、マップ（ブロックマップ等）を作成するためのものとしても本願で開示され、このマップは、オリジナルデジタルデータを再構築するために用いることができるオブジェクト／チャンクのリストを含むものである。加えて、上記システムおよび方法は、後で使用するためにチャンクから除去されたデータまたはこのチャンクの周囲から除去されたデータも保存することができる。このデータは、オリジナルファイルを構成した複数のオブジェクトのそれぞれについての情報を含んでおり、これにはページ番号等の非分割データと、分割処理の間にファイル内のオリジナルオブジェクトに適用された様々な方法とが含まれる。このデータは、分割処理の間にチャンクからあるいはその周囲から除去された様々な変換およびデータを再適用／復元するために用いることができ、更に、チャンクと非チャンクデータ（例えば、チャンクから除去されて別々に保存された、位置依存データや、インスタンス依存データや、ヘッダー／フッターデータ）との組み合わせを使ってオリジナルファイルを再構築するために用いることができる。
【００１５】
上記処理を用いて一旦オブジェクトが特定されると、この論理オブジェクトが既に存在しているか否かを判定するための適切な方法がこのオブジェクトに適用される。係る方法の２つの例は、新しく特定された論理オブジェクトにおけるハッシュ計算と、これとハッシュの既存のインデックスとの比較もしくは既存のオブジェクトとの実際のバイト毎の比較とである。
【００１６】
他の特徴および利点は、以下の詳細な説明、図面、および特許請求の範囲から理解できよう。
【図面の簡単な説明】
【００１７】
【図１】異なるオフセットにおいて保存されたオブジェクトの複数のインスタンスを示している。
【図２】様々な変換の後に保存されたオブジェクトの複数のインスタンスを示している。
【図３】インスタンスに埋め込められた異なる位置データと共に保存されたオブジェクトの複数のインスタンスを示している。
【図４】ヘッダーまたはフッターと共に保存されたオブジェクトの複数のインスタンスと、ヘッダーもフッターもなく保存されたオブジェクトのインスタンスを示している。
【図５】３つのファイルにおいて異なる配置に分散された複数のサブオブジェクトとして保存されたオブジェクトの複数のインスタンスを示している。
【図６】一のオブジェクトを示しており、その複数のインスタンスが異なるオフセットにおいて元々保存されており、その後このオブジェクトがオブジェクト・レポジトリに一度保存されることを示している。
【図７】一のオブジェクトを示しており、その複数のインスタンスが３つのファイルのそれぞれにおいて異なる配置に分散された複数のサブオブジェクトとして元々保存されており、その後このオブジェクトがオブジェクト・レポジトリにおいて互いに隣接して一度保存されることを示している。
【図８】一のオブジェクトを示しており、その複数のインスタンスが様々な変換の後に元々保存されており、その後このオブジェクトがオブジェクト・レポジトリに一度保存されることを示している。
【図９】一のオブジェクトを示しており、その複数のインスタンスがそれぞれ異なるメタデータまたは位置データが埋め込まれて元々記憶されており、その後これらの異なるデータがこのオブジェクトから除去されてこのオブジェクトと共に分離した状態でオブジェクト・リポジトリに一度保存されることを示している。
【図１０】ヘッダー／フッターと共に元々保存された一のオブジェクトの複数のインスタンスを示しており、その後オブジェクトから除去されたヘッダー／フッターと共に分離した状態でオブジェクト・レポジトリに一度保存されることを示している。
【図１１】一のオブジェクトの複数のインスタンス（それぞれ異なったストレージ配置構成や、位置データや、メタデータや、変換や、分離したヘッダー／フッターを有して異なるファイルに元々保存されているもの、および／または、異なるオフセットにおいて元々保存されているもの）を示しており、変換なしにオブジェクト・レポジトリに一度保存されているものである。
【図１２】一のオブジェクトを示しており、その複数のインスタンスは元々変換されており、かつ複合ファイル内の２つの隣接しないファイル・オブジェクトに保存されており、その後それぞれ変換が除去されてオブジェクトの隣接するインスタンスに再び組み立てられることを示している。
【図１３】ファイルからファイルチェックサムへのマッピングと、ファイルチェックサムからブロックチェックサムへのマッピングとを示している。
【発明を実施するための形態】
【００１８】
デジタルデータのコンテンツアウェアの分割
異なるデジタルデータフォーマット（例えば、ファイルベース、ブロックベース、ＢＬＯＢ（バイナリ・ラージ・オブジェクト）ベース、またはストリームベースのもの）は、その中に保存された論理オブジェクトに異なる属性を付加し、変換を加える、異なるフォーマットを有している。ほとんどの場合、これらの属性および変換は、前記デジタルデータ内に記憶された論理オブジェクト内およびこの周辺においてバイトパターンを変化させるものである。この結果、同じ論理オブジェクトが、デジタルデータの同じあるいは異なる単位内の２つの異なる場所において異なるバイトパターンと共に記憶され得る。この状況は、データの物理的なレイアウトのみを用いてこのデータを様々なブロックに分割するという従来のデジタルデータフォーマットにとらわれない重複排除方法において問題を生じさせる。これらの方法は、バイトパターンが変換のみによって、また論理オブジェクトの周辺に付属する位置データもしくはヘッダー／フッターのみによって異なるものであっても本質的なオブジェクトが共通であるということを判断できない。
【００１９】
デジタルデータの一単位内の複数の論理オブジェクトはこれらに加えられた一または複数の属性もしくは変換を一般に有しており、これらのそれぞれによって共通性を見つけることが阻害される。
【００２０】
図１は、データの異なる単位内の３つの異なる開始オフセットに保存された同一の論理オブジェクトを示している。例えば、同じ画像が３つの異なるパワーポイントファイルにおいて３つの異なるスライド上で３つの異なる開始オフセットで保存され得る。
【００２１】
図２は、３つの異なるデジタルデータフォーマットに保存された同一の論理オブジェクトを示しており、このオブジェクトの各インスタンスには保存される前に異なる変換が加えられている。例えば、オブジェクト１は、ファイル１に保存される前に第１の暗号化が行われ、また、ファイル２に保存される前に圧縮され、また、ファイル３に保存される前に第２の暗号化が行われている。この例においては、変換後のオブジェクトのバイトパターンは、変換のための入力による変更（例えば圧縮／暗号化アルゴリズム、シード値等への変更）によって、同一のオリジナルデータであっても異なるものとなり得る。
【００２２】
図３は、３つの異なるファイル内に保存されて異なる位置特定データを有する同一の論理オブジェクトを示している。例えば、パワーポイントファイルにおいて、スライドのための論理オブジェクトは当該オブジェクト内にスライド番号を有している。この結果、保存されたスライドが異なる位置に移動された場合に（同一のパワーポイントファイル内であっても異なるパワーポイントファイル内であっても）、論理スライドオブジェクトに他の変更がなされなくても、このスライドにおいて異なるバイトパターンが生じる。
【００２３】
図４は、ファイル１内でヘッダーを前に有する論理オブジェクトのインスタンスと、ファイル３内でフッターを後ろに有する同一の論理オブジェクトのインスタンスを示している。このヘッダーとフッターは、異なるデジタルデータ単位にとって異なっていてもよく、インスタンス固有の情報、種類特定情報、または位置特定情報を有していることが多い。２つの論理オブジェクトは同一であり得るが、付加されたヘッダーまたはフッターと組み合わせて見た場合にバイトパターンが異なるように見える。
【００２４】
図５は、オブジェクトを保存するために、複数のストレージ・ブロック／ストリームに亘って散りばめられた９つのより小さなサブオブジェクト（１〜９のラベルが付けられている）に分割された同一の論理オブジェクトを示している。
【００２５】
論理オブジェクト（上記方法で保存されている）内に存在する重複チャンクを特定する確率を高めるために、次に挙げる複数の方法が用いられる。これらの方法のそれぞれは、単独でも他の方法と組み合わせても用いることができる。
【００２６】
１．  様々なデジタルデータフォーマットの仕様の情報を適用することによりデジタルデータを複数の論理オブジェクトに分割する方法
従来の方法は、重複排除のために分析されるデジタルデータをデジタルデータフォーマットにとらわれない方法で複数のチャンクに分割する。この方法は次善の分割方法となることが多く、なぜなら、デジタルデータ内の論理オブジェクトがランダムな間隔で切断され、複数のチャンクに亘って分配されてしまうからである。より良い方法はデジタルデータフォーマットを理解することであり、論理オブジェクトの境界でチャンクを作成し、この工程において、一または複数の論理オブジェクトをランダムに組み合わせる代わりに、「全」論理オブジェクトを含むチャンクを作成することである。図６は、一のオブジェクトを示しており、その複数のインスタンスは異なるオフセットで元々保存されたものであり、このオブジェクトはオブジェクト・レポジトリに一度保存される。
【００２７】
２．  分割された複数のオブジェクトを一の論理オブジェクトに組み立てることによる、分割された複数のオブジェクトの処理
多くの場合、論理オブジェクトはファイル内の隣接する位置になくてもよい。結果として、全てのファイルオフセットのリストと分割されたオブジェクトのサイズとを保持したまま、このオブジェクトを一の論理オブジェクトにまず組み立てる必要がある。これにより、同一の論理オブジェクトが２つ以上のファイルに異なって分割されたとしても、それらの共通性を依然として見つけることが可能である。図７は一のオブジェクトを示しており、その複数のインスタンスは、ファイル１〜３に異なる配置で散りばめられた複数のサブオブジェクトとして元々保存されたものであり、オブジェクト・レポジトリに一度隣接して保存されている。
【００２８】
３．  論理オブジェクトに対する変換の非実施
デジタルデータ内の論理オブジェクトに施された共通する変換の例は圧縮および暗号化である。これらの変換が施された後は、オブジェクトは同一であるが結果として生じるバイトパターンは異なり得る。
【００２９】
本願で提案する方法は、重複チャンクを特定するためにチャンクを作成する前に、論理オブジェクトに施される変換を「施さない」。これにより、デジタルデータを同一および異なる種類の異なるファイル記憶単位もしくはブロック記憶単位、ＢＬＯＢ、ならびに／またはデータストリームに亘って共通する論理オブジェクトに分割することを可能にする。図８は、ファイル１に保存されているもののように暗号化（第１の態様）が行われ、ファイル２に保存されたもののように圧縮され、ファイル３に保存されたもののように暗号化（第２の態様）が行われた後に、オブジェクト・レポジトリに一のインスタンスとして保存されたオブジェクト１を示している。共通性を見つけるための例は以下のものである。
１．  同一の画像オブジェクトが、異なる圧縮アルゴリズムを用いる、同一の種類の２つの異なるファイルに保存される。
２．  同一の画像オブジェクトが、この同一の画像オブジェクトを保存する前に異なる暗号化アルゴリズムを用いる、２つの異なる種類の２つの異なるファイルに記憶される。
３．  同一の画像オブジェクトが、３つの異なる種類の３つの異なるファイルに保存され、第１のファイルは画像を保存する前にこの画像を圧縮し、第２のファイルは画像を保存する前にこの画像を暗号化し、第３のファイルは画像オブジェクトをオリジナルフォーマットで保存する。
【００３０】
図８で示されるように上記の例の全てにおいて、本願の新規な方法は、異なる複数のファイルに亘って共通するであろう論理画像オブジェクトにファイルを分割する。
【００３１】
４．  論理オブジェクトからの位置依存データまたはメタデータの除去
共通性を見つけるのを阻害する別の問題は、論理オブジェクトが、同一のデジタルデータ単位内または異なるデジタルデータ単位内でオブジェクトの相対位置が変化する毎に論理オブジェクトのバイトパターンを変化させる位置データを含んでいることである。例えば、パワーポイント文書内でスライドが移動された場合、論理スライドオブジェクトのバイトパターンはスライド番号がスライドオブジェクトの一部であるため変化する。このことによって、本質的なスライドオブジェクトが同一であってもこの共通性を見つける工程がやはり妨げられる。位置依存データの他の例には、ページ番号、パラグラフ番号、およびマイクロソフトエクセルのセル番号が含まれる。別の例は、いくつかのオブジェクトが、作成者の名前、改訂番号、更新日、合計編集時間、ページ数、文字数、行数、段落数、単語数等のインスタンス依存メタデータを含むものである。これらのメタデータはファイルが保存される毎に変化し得る。オブジェクトからこれらのメタデータを除去することで、高いレベルの重複排除を達成することができる。
【００３２】
本明細書において記載されたシステムおよび方法は、任意の位置依存データまたはメタデータのための論理オブジェクトを分析することができ、重複ブロックを特定するために作成されたチャンクからこのデータを除去する。図９は一のオブジェクトを示しており、このオブジェクトの複数のインスタンスはこれらに埋め込まれたそれぞれ異なるメタデータまたは位置データを有して元々保存されたものであり、このオブジェクトから除去された異なるデータと共に前記オブジェクトから分離してオブジェクト・レポジトリに一度保存される。これら３つのインスタンスは、これらのインスタンスが共通して有していたチャンクの単一のインスタンスとしてオブジェクト・レポジトリに保存され、更に、各インスタンスのインスタンス固有のメタデータもしくは位置データと、チャンクならびにインスタンス固有のメタデータもしくは位置データをこれらが元々保存されていた各ファイルにリンクする関連付けと共に保存される。論理オブジェクト／チャンクは、保存する代わりに送信するか、保存することに加えて送信してもよい。例えば、デジタルデータはストリームとして受信することができ、このストリーム上でコンテンツアウェア分割が行われ、その後、抽出されたチャンクおよび更なるデータは、チャンクと更なるデータとこれらをリンクする関連付けとを含む重複排除されたデータストリームとして送信することができる。このストレージ／送信および関連付け処理は以下に詳細に記載される。
【００３３】
５．  チャンク作成前のオブジェクト・ヘッダー／フッターの除去
別の問題は、デジタルデータフォーマットがヘッダーを論理オブジェクトの前に付け得るか、フッターを論理オブジェクトの後に付け得ることである。係るヘッダーまたフッターは、異なるデジタルデータのインスタンスもしくは種類において一般的に異なっており、位置依存情報を含み得る。２つの論理オブジェクトは同一であり得るが、付加されたヘッダーもしくはフッターとの組み合わせで見た場合、バイトパターンは異なるように見え、このことは重複排除のために共通性を見つけるための別の阻害要因となる。
【００３４】
本願で提案する方法は、任意のヘッダーデータもしくはフッターデータのための論理オブジェクトを分析し、重複ブロックを特定するために作成されたチャンクから、このヘッダーデータもしくはフッターデータを除去するものである。図１０は、論理オブジェクトの３つのインスタンスを示している。第１のインスタンスはヘッダーと共にファイル１に元々保存され、第２のインスタンスはヘッダーもしくはフッターなしにファイル２に保存され、第３のインスタンスはフッターと共にファイル３に保存されている。これら３つのインスタンスは、これらのインスタンスが（ヘッダー／フッターなしで）共通して有するチャンクの単一のインスタンスとしてオブジェクト・リポジトリに保存される。図１および図２のオブジェクト・インスタンスに元々含まれるヘッダーおよびフッターはレポリジトリにそれぞれ別々に保存され、ここにおいてこれらは、チャンクおよびヘッダーデータ／フッターデータをこれらが元々保存された各ファイルにリンクする関連付けと共に保存される。このストレージおよび関連付けの処理は以下に詳細に記載される。
【００３５】
複数のファイルが、上述の一または複数の変換を有し得る。図１１は、異なる変換を伴っても、このシステムが複数の異なるファイルに亘って共通のオブジェクトを見つけ、オブジェクト・レポジトリにオブジェクトの単一のインスタンスのみを保存することができることを示している。
【００３６】
６．  ファイル・オブジェクトを含む．ＰＳＴ／．ＺＩＰファイル等の複合データ単位の扱い
複合ファイルは、名前が示すようにファイルである一または複数のサブオブジェクトからなり、更に、ファイルでない他のサブオブジェクトを含み得る。複合ファイルフォーマットの例としては、．ｚｉｐ（圧縮ファイル）、．ｐｓｔ（マイクロソフトアウトルックファイル）、．ｃａｂ、．ａ、．ｅｄｂ（マイクロソフトエクスチェンジデータベースファイル）、マイクロソフトＳＱＬサーバデータベース、ロータスノーツ・メールボックス、シェアポイント・レポジトリ、ＥＭＣドキュメンタムフォーマットが含まれる。これらのファイル・オブジェクトは、これらの複合ファイルのフォーマットについての理解を用いて（他の方法を用いることに加えて）まず組み立てられる必要がある。組み立ての間、解読や解凍等の変換、ヘッダー／フッターの除去、散りばめられたファイルのサブオブジェクトの組み立てを行うこともできる。このファイル・オブジェクトを組み立てた後に、一のファイル・オブジェクト内で更なるチャンク／オブジェクトを見つけるために上記方法のいくつかまたは全てが行われる。図１２は、オブジェクトＡを示しており、その２つのインスタンスは元々変換されており、複合ファイル内の２つの隣接しないファイル・オブジェクト（ファイルＸおよびファイルＹ）に保存されている。この図は、これらのファイルが隣接するファイルに再度組み立てられた後に、双方のファイルにおいて重複ファイルとしてどのように特定されるかも示している。
【００３７】
一定の複合ファイルフォーマットは、階層的であり得、また、複数のオブジェクト（それ自体に複数のオブジェクトを含む複合オブジェクト）を含み得る。これらの場合において、上記方法は、再帰的に行われることができ、複合階層の下位層で論理オブジェクトを特定し組み立てる。
【００３８】
オリジナルデータの再構築を可能にする、論理オブジェクトとしてのデジタルデータの保存
共通するオブジェクト／チャンクが一組のデジタルデータにおいて特定された後、このデジタルデータは、データを保存するために要求されるストレージおよびネットワークの占有面積を減少させるために、これらのオブジェクト／チャンクによって保存される。共通する各オブジェクトは関連する識別子と共に重複排除オブジェクト・レポジトリに保存される。次に、後述するようにオリジナルデジタルデータの表現（表示）が、共通するオブジェクトの代わりに識別子を用いて保存される。
【００３９】
図１３は、４つのファイル内で共通する論理オブジェクト／チャンクを特定する上記方法を用いて、これら４つのファイルを保存した結果を表している。ファイル１〜ファイル４は、図１３に示したように保存される前に、互いに異なる名前を元々有していたが、複数の共通する論理オブジェクトを共有していた。具体的には、ファイル１およびファイル２は共に３つの同一のオブジェクトを含んでおり、これらのオブジェクトの一つはファイルであった。ファイル３およびファイル４はファイル１およびファイル２に含まれるファイルの更に別のインスタンスであった。加えて、ファイル３およびファイル４はファイル１およびファイル２にやはり含まれる共通する論理ブロックを含んでいた。
【００４０】
ファイルチェックサム（ＦｉｌｅＣｈｅｃｋＳｕｍ）
各ファイルにおいて、チェックサム（あるいはハッシュ）をそのファイル全体のために計算することができる。ハッシュ関数は安全なハッシュアルゴリズム（ＳＨＡ）（例えば、ＳＨＡ−０、ＳＨＡ−１、ＳＨＡ−２）やＭＤ５アルゴリズムを含み得る。論理オブジェクトとしてデジタルデータ（例えばファイル）を保存するときに、各オリジナルファイルは重複排除されたファイル・オブジェクトとして表され、カタログに保存される。重複排除されたファイル・オブジェクトはオリジナルファイルの名前を含んでおり、ファイルチェックサムおよび他の属性（最終更新日時等）も共に含む。チェックサムは、ファイルチェックサムのＩＤ（ファイルチェックサムへのポインタまたは参照）を提供する。ファイルチェックサムは、オリジナルファイルを表すが、ファイルに元々含まれる共通する論理オブジェクトによって保存される。場合によっては、用語「ファイルチェックサム」は、ファイルチェックサムを特定するために用いられるチェックサム／ハッシュ値を指すものとして用いられ得る。後述するように、ファイルチェックサムは、ブロックマップ（ＢｌｏｃｋＭａｐ）およびＸブロック（ＸＢｌｏｃｋ）を有する。
【００４１】
ファイルチェックサム（および後述するブロックチェックサム（ＢｌｏｃｋＣｈｅｃｋＳｕｍ）オブジェクト）は、重複排除されたファイル・オブジェクトを含むカタログに関連付けされた重複排除レポジトリに記憶される。このカタログはファイル・オブジェクトのバックアップカタログであってもよい。このカタログをバックアップ以外の目的のために用いることもできる（例えば主ファイルシステムの一部として（例えば積極的かつ継続的使用のため））。
【００４２】
ブロックマップ（ＢｌｏｃｋＭａｐ）
以下の情報は、ブロックマップに保存される。
１．  バージョンや長さ等を含む、ブロックマップ・ヘッダー
２．  Ｘブロックチェックサム（Ｘブロックについては後述する）
３．  このファイルのブロックのリスト（各ブロックについて以下のものを保存する）
ａ．  ブロックチェックサム
ｂ．  Ｘブロックにおいて使用するバイト数
４．  この複合ファイル内のファイルのリスト（各ファイルについて以下のものを保存する）
ａ．  ファイルチェックサム
ｂ．  Ｘブロックにおいて使用するバイト数
【００４３】
ブロックチェックサム（ＢｌｏｃｋＣｈｅｃｋＳｕｍ）
ブロックマップはブロックチェックサムオブジェクトのリストを有しており、このブロックチェックサムオブジェクトは元々保存されたデジタルデータのうちの少なくとも一部分を含んだ論理オブジェクト／チャンクを特定するものである。ブロックチェックサムは論理オブジェクト／チャンクと関係しており、この論理オブジェクトの情報は一度だけオブジェクト・レポジトリに保存される。このように、ブロックチェックサムは、「原材料（the raw material）」の一部分を提供するのであり、この「原材料」からファイルを再保存（復元）することができる。各ブロックチェックサムのために、このブロックチェックサムがファイルチェックサム識別子と同様に表す関連した論理オブジェクトのためにチェックサムが計算される。ブロックチェックサムはこのチェックサムによって特定される。図１３は３つのブロックチェックサム（ＢＣＳ１−ＢＣＳ３）を示しており、ＦＣＳ１のブロックマップはＢＣＳ１およびＢＣＳ２を指し示しており、ＦＣＳ２のブロックマップはＢＣＳ２およびＢＣＳ３を指し示している。ＦＣＳ１のブロックマップはＦＣＳ２も指し示している。
【００４４】
Ｘブロック（ＸＢｌｏｃｋ）
Ｘブロックはオリジナルファイルを構成する複数のオブジェクトのそれぞれについての情報を含んでおり、この情報には、分割処理の間にファイル内のオリジナルオブジェクトと非チャンクデータ（ページ番号など）とに施された様々な方法が含まれる。Ｘブロックは、分割処理の間に構成要素であるチャンクから除去された様々な変換およびデータを再び加え、チャンクと非チャンクデータとの組み合わせ（例えば、チャンクから除去されてこれらのチャンクとは別に保存された、位置依存データや、インスタンス依存データや、ヘッダー／フッターデータ）を用いてオリジナルファイルを再構成するために用いられる。Ｘブロックは、関連するブロックマップの各論理オブジェクトについての以下の情報を含んでおり、各オブジェクトのために保存された特定の情報は、その種類と、チャンク処理の間に施された方法とに依存する。
１．  変換の種類（例えば、ファイルにオブジェクトが圧縮／暗号化されて元々保存されている場合に用いられる、圧縮アルゴリズムや暗号化アルゴリズム）。この場合には、少なくとも次のフィールドがＸブロック内部で使われる。
ａ．  Ｘブロック情報の種類
ｂ．  圧縮／暗号化アルゴリズムの種類
２．  オブジェクトから分離された位置データ／メタデータ。この場合には、少なくとも次のフィールドがＸブロック内部で使われる。
ａ．  Ｘブロック情報の種類
ｂ．  この位置データ／メタデータが挿入されるべきオブジェクトへのオフセット
ｃ．  位置データ／メタデータの長さ
ｄ．  位置データ／メタデータ
３．  オブジェクトに付けられたヘッダー／フッター。この場合には、少なくとも次のフィールドがＸブロック内部で使われる。
ａ．  Ｘブロック情報の種類
ｂ．  これは、ヘッダーかフッターか
ｃ．  ヘッダーまたはフッターの長さ
ｄ．  ヘッダー／フッター・データ
この情報は、オブジェクトについてのヘッダー／フッター情報をこのオブジェクトから切り離すために用いることができる。
４．  分割されたオブジェクト。この場合には、少なくとも以下のフィールドがＸブロック内部で使われる。
ａ．  Ｘブロック情報の種類
ｂ．  オブジェクトを分割した部分の数
ｃ．  オブジェクトの分割された各部分のために、次の情報が保存される。
１．  この部分が存在するファイルのオフセット
２．  このオフセットにおけるこの部分の長さ
この情報がファイル内に元々隣接して配置されていなかった場合であっても、この情報はデジタルデータの復元したバージョンで論理オブジェクトを再作成するために用いることができる。多くのファイルフォーマットは、ファイル内の複数の非隣接位置にて一の論理オブジェクトを維持する。
５．  複合ファイル内のサブファイルのオブジェクト。この場合には少なくとも次のフィールドがＸブロック内部で使われる。
ａ．  Ｘブロック情報の種類
ｂ．  複合ファイル内のサブファイルを分割した部分の数
ｃ．  各部分について少なくとも次の情報が記憶される。
１．  複合ファイルのオフセット
２．  上記オフセットにおけるこの部分の長さ
ｄ．  施されるべき変換の種類、例えば、サブファイルを構築した後の圧縮の種類または暗号化の種類。例えば、．ＰＳＴファイルフォーマットにおいて、サブファイル（添付物）は、複合ファイルに分割され、暗号化されて保存されている。
この種類の情報は、複合ファイル内部で論理ファイル・オブジェクトを生成するために用いることができる。複合ファイルから各ファイル・オブジェクトを構築した後、より小さい論理オブジェクトがファイル・オブジェクト内部で再び見つけられる。これによって、オブジェクトが複合ファイルにおいてサブファイル内部にあるときにでも、システムは共通性を見つけることができる。
【００４５】
ファイルチェックサムへの重複排除されたファイル・オブジェクトのマッピング、およびブロックチェックサムへのファイルチェックサムのマッピング
前述したように、カタログ内に保存された重複排除したファイル・オブジェクトは、重複排除されたファイル・オブジェクトであるファイル１〜ファイル４において「ＦＣＳ１」および「ＦＣＳ２」として図１３に示される各ファイルチェックサムの識別子を含む。各ファイルチェックサムは、特定のファイルチェックサムを参照する重複排除したファイル・オブジェクト（および可能性としては他のファイルチェックサム）の数と等しい参照カウント（ｒｅｆｅｒｅｎｃｅ  ｃｏｕｎｔ）を有する。たとえば、図１３で、参照カウントが２であるためにファイルチェックサム１（ＦＣＳ１）は２つのファイルによって参照されるものであり、ファイルチェックサム２（ＦＣＳ２）は参照カウントが３であるために、ファイルで２回、ファイルチェックサム１で１回の合計３回参照される。
【００４６】
更に、前述したように、各ファイルチェックサムはブロックマップを有しており、このブロックマップはオリジナルのデジタルファイルを構成したブロックチェックサムのリスト（具体的にはブロックチェックサムの識別子）を含んでいる。ファイルチェックサムと同様に、各ブロックチェックサムはそれがブロックマップによって参照される回数に等しい参照カウントを有する。
【００４７】
ファイルチェックサムは参照カウントがゼロになるまで（例えばどのファイル（または他のどのファイルチェックサム）もこのファイルチェックサムを参照しなくなるまで）削除されない。同様に、ブロックチェックサムは参照カウントがゼロになるまで（例えばどのファイルチェックサムもこのブロックチェックサムを参照しなくなるまで）削除されない。
【００４８】
上述のシステムおよび方法は新しい文書が作成されたときに用いることができ、新しい文書を重複排除して保存することができる。これらのシステムおよび方法は、保存したデータの重複排除を行うためにストレージ内の既存のファイルおよび他のデータと共に用いることができ、保存されるデータ量を減少させることもできる。
【００４９】
特定の実施形態を記載してきたが、添付した特許請求の範囲から逸脱することなく改変を加えることができることは明らかである。例えば、異なる種類のプロセッサおよびメモリを用いることができる。ストレージにデータを保持するための文献が数多くある。記憶装置は、デジタルディスク、光ディスクまたは半導体メモリ等の任意の適した形態のメモリでよい。本願記載の処理は、任意の適したハードウェア論理もしくはソフトウェア論理またはこれらの組合せによって遂行することができ、汎用プロセッサ、または特別仕様の製品等の任意のプロセッサにおいて実行することができる。上記の処理の多くは、複数のステップ（例えば分割（チャンキング）、ハッシング、比較、データの保存（記憶）、ブロックの保持等）を遂行する命令としてコンピュータで読み取り可能なメモリに保存することができるソフトウェアにおいて、プロセッサによって遂行されることができる。
【００５０】
本明細書は、位置依存データの除去、インスタンス依存データの除去、ソース論理オブジェクトからの一または複数のフォーマット固有のヘッダーもしくはフッターの除去、ならびにソース論理オブジェクトからのフォーマット固有の変換の除去について記載しているが、他の種類のデータ除去も想定することができる。データのフォーマットは一種類のデータ除去または変換に対して一対一対応であり得、また、異なるフォーマットに関連するデータ除去および変換の複数の組合せがあり得る。例えば、一のフォーマットが、特定の位置依存データおよびインスタンス依存データを除去する工程を含むことができ、第二のフォーマットが位置依存データおよびフォーマット固有の変換を除去する工程を含むことができ、第三のフォーマットが一または複数のフォーマット固有のヘッダーもしくはフッターを除去する工程を含むことができる。
【００５１】
更に、データ分割は、複数のストレージ・ブロックに亘って散りばめられた一または複数のサブオブジェクトとしてデジタルデータに元々保存された論理オブジェクトを特定し、組み立てるステップのみからなり得る。この場合、組み立てられたオブジェクトはオリジナルのオブジェクトやそのサブオブジェクトの位置を示す情報と共に保存される。
【図１】
0005468620.tif 000002
【図２】
0005468620.tif 000003
【図３】
0005468620.tif 000004
【図４】
0005468620.tif 000005
【図５】
0005468620.tif 000006
【図６】
0005468620.tif 000007
【図７】
0005468620.tif 000008
【図８】
0005468620.tif 000009
【図９】
0005468620.tif 000010
【図１０】
0005468620.tif 000011
【図１１】
0005468620.tif 000012
【図１２】
0005468620.tif 000013
【図１３】
0005468620.tif 000014