(57)【要約】重複データを無くすための技術を提供する。新たなデータセットを受信し、そのデータセットの中から１以上のアンカーポイントを識別する。次に、受信したデータセット中のアンカーポイントを取り巻く領域を、パターンデータベース内のアンカーポイントを取り巻く領域と比較し、前方デルタ値、及び後方デルタ値を識別する。そして、アンカーポイント、前方デルタ値、及び後方デルタ値によって識別される受信したデータセット中の重複データを、ストレージインジケータで置き換える。
2009535704.tif 000002
【特許請求の範囲】
【請求項１】
データセットから重複データを削除する方法であって、
データセット中のアンカーを識別するステップと、
識別されたアンカーがアンカーデータベース中に存在するか否かを判定するステップと、
前記アンカーが前記アンカーデータベース中に存在するという判定に応答し、前記データセットと、記憶済みデータセットとの間のデータ比較を実施し、識別された前記アンカーに対する前方デルタ値、及び後方デルタ値を識別するステップと、
前記アンカー、前記前方デルタ値、及び前記後方デルタ値によって識別される前記データセットの領域をストレージインジケータで置き換え、変更されたデータセットを形成するステップと
からなる方法。
【請求項２】
前記アンカーを識別するステップは、前記データセットに対してローリングハッシュを実施するステップを含む、請求項１に記載の方法。
【請求項３】
前記アンカーを識別するステップは、前記データセット中の所定の位置にアンカーを配置するステップを含む、請求項１に記載の方法。
【請求項４】
前記記憶済みデータセットは、パターンデータベースに記憶される、請求項１に記載の方法。
【請求項５】
前記ストレージインジケータは、アンカー識別子、前記前方デルタ値、及び前記後方デルタ値を含む、請求項１に記載の方法。
【請求項６】
前記変更されたデータセットをデータオブジェクト記憶手段に記憶するステップをさらに含む、請求項１に記載の方法。
【請求項７】
前記データオブジェクト記憶手段は、ファイルシステムを含む、請求項６に記載の方法。
【請求項８】
２つの類似するデータセット間における重複データを探索するステップをさらに含む、請求項１に記載の方法。
【請求項９】
前記類似するデータセットは、共通データと固有データを混在して含む、請求項８に記載の方法。
【請求項１０】
前記重複データは、前記新たなデータセットのアンカーポイントを類似データのアンカーポイントと比較することにより探索される、請求項８に記載の方法。
【請求項１１】
類似データのアンカーポイントは、前記新たなデータセット中のアンカーポイントのパターンに基づいて識別される、請求項１０に記載の方法。
【請求項１２】
前記データセット中の複数の隣り合うアンカーに対してハッシュを計算することにより、アンカー階層を形成するステップをさらに含む、請求項１に記載の方法。
【請求項１３】
データセットから重複データを削除するように構成されたシステムであって、
データセット中のアンカーを識別する手段と、
識別されたアンカーがアンカーデータベース中に存在するか否かを判定する手段と、
前記アンカーが前記アンカーデータベース中に存在するという判定に応答し、前記データセットと、記憶済みデータセットとの間のデータ比較を実施し、識別された前記アンカーに対する前方デルタ値、及び後方デルタ値を識別する手段と、
前記アンカー、前記前方デルタ値、及び前記後方デルタ値によって識別される前記データセットの領域をストレージインジケータで置き換える手段と
を含むシステム。
【請求項１４】
前記アンカーを識別する手段は、前記データセットに対してローリングハッシュを実施する手段を含む、請求項１３に記載のシステム。
【請求項１５】
前記アンカーを識別する手段は、前記データセット中の所定の位置にアンカーを配置する手段を含む、請求項１３に記載のシステム。
【請求項１６】
前記記憶済みデータセットは、パターンデータベースに記憶される、請求項１３に記載のシステム。
【請求項１７】
前記ストレージインジケータは、アンカー識別子、前記前方デルタ値、及び前記後方デルタ値を含む、請求項１３に記載のシステム。
【請求項１８】
前記データセット中の複数の隣り合うアンカーに対してハッシュを計算することにより、アンカー階層を形成する手段をさらに含む、請求項１３に記載のシステム。
【請求項１９】
データセットから重複データを削除するように構成されたシステムであって、
データセットを提供するように構成されたストレージシステムと、
前記ストレージシステムから前記データセットを受信するように構成され、前記データセット中のアンカーを識別するように構成され、さらに、識別されたアンカーがアンカーデータベース中に存在するか否かを判定するように構成された仮想テープライブラリシステムと
を含むシステム。
【請求項２０】
前記仮想テープライブラリシステムは、前記アンカーが前記アンカーデータベース中に存在しないという判定に応答し、前記データセットと、記憶済みデータセットとの間のデータ比較を実施し、前方デルタ値、及び後方デルタ値を識別するようにさらに構成される、請求項１９に記載のシステム。
【請求項２１】
前記記憶済みデータセットを記憶するように構成されたパターンデータベースをさらに含む、請求項２０に記載のシステム。
【請求項２２】
前記仮想テープライブラリシステムは、前記アンカー、前記前方デルタ値、及び前記後方デルタ値によって識別される前記データセットの領域をストレージインジケータで置き換え、変更されたデータセットを形成するようにさらに構成される、請求項２０に記載のシステム。
【請求項２３】
前記ストレージインジケータは、アンカー識別子、前記前方デルタ値、及び前記後方デルタ値を含む、請求項２２に記載のシステム。
【請求項２４】
前記アンカーは、前記データセットに対してローリングハッシュを実施することにより識別される、請求項１９に記載のシステム。
【請求項２５】
前記アンカーは、前記データセット中の所定の位置にアンカーを配置することによって識別される、請求項１９に記載のシステム。
【請求項２６】
前記データセットは、バックアップデータストリームからなる、請求項１９に記載のシステム。
【請求項２７】
前記仮想テープライブラリシステムは、前記データセット中の複数の隣り合うアンカーに対してハッシュを計算することにより、アンカー階層を形成するようにさらに構成される、請求項１９に記載のシステム。
【請求項２８】
データセットから重複データを削除するためのコンピュータ読取可能媒体であって、
データセット中のアンカーを識別するステップと、
識別されたアンカーがアンカーデータベース中に存在するか否かを判定するステップと、
前記アンカーが前記アンカーデータベース中に存在するという判定に応答し、前記データセットと、記憶済みデータセットとの間のデータ比較を実施し、識別された前記アンカーに対する前方デルタ値、及び後方デルタ値を識別するステップと、
前記アンカー、前記前方デルタ値、及び前記後方デルタ値によって識別される前記データセット中の領域をストレージインジケータで置き換え、変更されたデータセットを形成するステップと
を実施するためのプログラム命令を含むコンピュータ読取可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
[発明の分野]
本発明は概して、データストレージ圧縮に関し、より具体的には、サンプリングを利用した重複データの削除（重複の解消）に関する。
【背景技術】
【０００２】
[発明の背景]
ストレージシステムは一般に、１以上の記憶装置を備え、要求に応じてその中に情報を入れたり、そこから情報を取得したりすることができる。ストレージシステムはストレージシステムを含み、ストレージオペレーティングシステムは、とりわけ、システムによって実施されるストレージサービスをサポートする種々のストレージオペレーションを実施することによって、システムを機能的に編成する。ストレージシステムは、種々のストレージアーキテクチャに従って実施され、限定はしないが、例えば、ネットワーク・アタッチド・ストレージ環境、ストレージ・エリア・ネットワーク、あるいは、クライアントコンピュータ、又はホストコンピュータに直接取り付けられるディスクアセンブリとして実施される場合がある。記憶装置は通常、ディスクアレイとして編成された幾つかのディスクドライブである。ここで、「ディスク」という用語は一般に、内蔵型の回転磁気媒体記憶装置を表わす。この文脈におけるディスクという用語は、ハードディスクドライブ（ＨＤＤ）や、ダイレクトアクセスストレージデバイス（ＤＡＳＤ）と同じ意味である。
【０００３】
データストレージは、銀行、政府機関／請負業者、及び警備保障会社といったアーカイブやコンプライアンスに関わる環境で運営される多くの産業の中心部である。そうした環境の多くでは、特定のデータ、例えば、電子メールメッセージ、金融文書、及び／又は取引記録を不変的な形で記憶する必要があり、場合によっては、それらを長期間にわたって記憶しなければならないことがある。一般に、データバックアップオペレーションは、故障発生時におけるそうしたデータの保護、及び復元を可能にするために実施される。しかしながら、バックアップオペレーションは、ディスクのようなバックアップストレージリソース上にデータの重複（複製）を生じさせることになるため、リソース上の記憶空間はしばしば、非効率的に消費されることになる。長期アーカイブストレージの一形態は、電子テープ媒体へのデータの記憶である。物理テープ媒体の大きな欠点は、データアクセス速度が遅いことや、多数の物理テープを管理する場合に要件が増加することにある。こうした大きな欠点に対処するために、幾つかのストレージシステムベンダは、複数のディスクドライブを使用してテープデバイスをエミュレートする仮想テープライブラリ（ＶＴＬ）システムを提供している。一般的なＴＶＬ環境では、一次記憶装置として機能するストレージシステムが、当該ストレージシステムのファイルシステム（又は、他のデータストレージ）をＶＴＬシステムへと完全バックアップオペレーションを実施する。時間をかけて複数の完全バックアップが行われる場合もあり、それによって、ＶＴＬシステム上の記憶空間は、非効率的に消費されることになる。従って、ＶＴＬシステムに関連するディスクのようなストレージリソース上の重複データを無くし、データの単一のインスタンスだけを記憶することにより、ストレージ圧縮を実現することが望まれている。
【０００４】
データ重複の低減（重複解消）を実現する一つの技術は、１９９９年１１月２３日に発行された「METHOD FOR PARTITIONING A BLOCK OF DATA INTO BLOCKS AND FOR STORING AND COMMUNICATING SUCH SUBBLOCKS」と題するRoss Williamsによる米国特許第５，９９０，８１０（以下、「８１０特許」）に記載されている。８１０特許に記載の方法は、まず、ローリングハッシュ関数を使用し、複数のサブブロックデータを生成する。ローリングハッシュは、固定サイズのデータウィンドウを使用し、２つのサブブロック間に配置される境界を生成する。あるデータブロックを複数のサブブロックに区分した後、各サブブロックのハッシュ値を計算し、ハッシュ値のテーブルを形成する。次に、ハッシュテーブルを使用し、新たなサブブロックが、ハッシュテーブルに既に記憶されているハッシュ値を有するいずれかのサブブロックと一致するか否かを判定する。この判定を実施するために、新たなサブブロックのハッシュ値を計算し、それをハッシュテーブルに記憶されている種々の値と比較する。もし、新たなサブブロックのハッシュ値が、ハッシュテーブルの中に既に記憶されていた場合、記憶されたハッシュ値を有するものと識別されたサブブロックは、新たなサブブロックと同一であるとみなされる。その場合、新たなサブブロックは既に記憶されているサブブロックへのポインタで置き換えられ、それによって、サブブロックに必要とされる記憶空間の量を低減する。８１０特許に記載された技術の大きな欠点は、膨大な数の集中的なハッシュ計算の処理能力を必要とする点にあり、そのような集中的なハッシュ計算は、そのような方法を実施するストレージ／ＶＴＬシステムの全体的処理能力に悪影響を与えることがある。もう一つの大きな欠点は、データセットのサイズが増大するのに従って、ハッシュテーブルのサイズも増大するため、数テラバイトや数ぺタバイトといった大きなデータセットには応用できないことがある点にある。
【０００５】
重複データを無くすためのもう一つの技術は、２００５年４月１３日に出願された「METHOD AND APPARATUS FOR IDENTIFYING AND ELIMINATING DUPLICATE DATA BLOCKS AND SHARING DATA BLOCKS IN A STORAGE SYSTEM」と題するLing Zheng他による米国特許出願第１１／１０５，８９５号に記載されている。この特許出願に記載のシステムでは、データ重複解消オペレーションが全て、例えば４キロバイト（ＫＢ）サイズのような固定サイズのブロックに対して実施される。新たなブロックを記憶する場合、ハッシュは、その４ＫＢブロックから計算され、それが、既に記憶されている種々のブロックのハッシュ値を含むハッシュテーブルと照合される。もし、新たなブロックのハッシュ値が既に記憶されているブロックのものと同一であった場合、新たなブロックは、既に記憶されているブロックと同一である可能性が高い。その場合、新たなブロックを、既に記憶されているブロックへのポインタで置き換えることにより、ストレージリソースの消費が低減される。ただし、このシステムの大きな欠点は、固定サイズのブロックに限定される点にある。動作として、データセットの中程への単一ビットの追加は、以後のデータブロック全てに不整合を引き起こし、重複解消を妨げるため、ストレージリソースの使用は非効率的なものになる場合がある。
【０００６】
第３の技術は、第３回ソフトウェア構成管理国際ワークショップ、１９９１年６月１２１４（１９９１年６月）、ノルウェイ、トロンヘイム、の議事録の中に、「DELTA STORAGE FOR ARBITRARY NONTEXT FILES」と題してChris Reichenbergerにより記載されたような技術であり、データのハッシュを使用して、最長の共通データシーケンスを見つけ出すものである。ただし、データセット中に発生しうる全ての部分文字列についてハッシュを計算し、比較するという上記の方法は、サンプリング技術を何も使用しない。従って、そのような方法は、大きなデータセットには応用されない。
【発明の開示】
【課題を解決するための手段】
【０００７】
[発明の概要]
本発明は、ディスクのようなストレージリソースに記憶された重複データを無くす（重複解消する）ための、サンプリングを利用した技術を提供することにより、従来技術の欠点を克服する。本発明によれば、新たなデータセットがサーバ、例えばストレージシステム１２５、又はシステム２００によって受信されると、その新たなデータセットの中から、１以上のアンカーが識別される。本明細書では、アンカーとは、データ重複の可能性があると考えられる領域を規定する、データセット中のポイントとして定義される。アンカーは、データセットのローリングハッシュを実施することにより発見される場合がある。その場合、アンカーポイント（「アンカー」）は、シグネチャ幅を規定する固定サイズ領域の中から探索される。なお、アンカーは、例えばファイルのようなデータコンテナ内の位置に基づいて選択される場合もあれば、例えばデータセット中の所定のオフセットのような、他のコンテキスト情報に基づいて選択される場合もある。
【０００８】
新たなデータセットの中から識別された各アンカーについて、そのアンカーが、アンカーデータベース（又は、他のデータ記憶装置）に既に記憶されているか否かの判定が成される。もし、識別されたアンカーが、アンカーデータベースに記憶されていなければ、そのアンカーは、データセット中のそのアンカーの位置を示す情報とともに、アンカーデータベースの中に記憶される。ただし、代替実施形態として、アンカー位置は単に、データセット中のオフセットであってもよい。もし、識別されたアンカーが、アンカーデータベースの中に既に記憶されていた場合、サーバは、パターンデータベースの中からそのアンカーを探索し、新たなデータセットと、パターンデータベースに記憶されたアンカーを有するデータセットとの間で、アンカーポイントから前後に、ビット単位（又は、バイト単位）のデータ比較を実施する。データ比較の結果、新たなデータセットと記憶されたデータセットとの間で一致した、アンカーポイントから前後に続く連続したデータビットの数をそれぞれ示す前方デルタ値、及び後方デルタ値が得られる。新たなデータセット中の重複データ、すなわち、アンカーポイントを中心として後方デルタ値と前方デルタ値の間の範囲にあるデータは、アンカー、前方デルタ値、及び後方デルタ値を識別するストレージインジケータで置き換えられる。
【０００９】
本発明の上記の利点、及び他の利点は、添付の図面と併せて下記の説明を読むことで、より深く理解することができる。図中、類似の符号は、同一の要素、又は機能的に類似の要素を指している。
【発明を実施するための最良の形態】
【００１０】
[例示的実施形態の詳細な説明]
Ａ．ストレージシステム環境
図１は、本発明と共に有利に使用されるストレージシステム環境１００を示す略ブロック図である。ストレージシステム環境１００は、ネットワーク１２０により複数のクライアント１１０に相互接続されたストレージシステム１２５を含む。図示のように、ネットワーク１２０は、イーサネット(登録商標)ネットワーク、又はファイバチャネル（ＦＣ）ネットワークとして実施される場合がある。ネットワーク１２０には更に、仮想テープライブラリ（ＶＴＬ）システム２００が相互接続される。仮想テープライブラリ（ＶＴＬ）システム２００は例えば、本発明のデータ重複解消技術を実施する。ＶＴＬシステム２００には更に、ストレージアレイ１６０として編成された１以上のディスク１３０のような記憶装置が接続される。
【００１１】
動作として、ストレージシステム１２５は、クライアント１１０からのデータアクセス要求に対するサービスを提供する。各クライアント１１０は、アプリケーションを実行するように構成され、クライアント／サーバモデルの情報配送に従ってストレージシステム１２５との間で情報をやりとりするように構成された汎用コンピュータであってもよい。すなわち、ネットワーク１２０を介してパケットをやりとりすることによって、クライアントは、ストレージシステムにサービスを要求し、ストレージシステムは、クライアントから要求されたサービスの結果を返すことができる。クライアントは、ファイルやディレクトリのようなデータコンテナの形をした情報をアクセスする場合、ＴＣＰ／ＩＰを介して、コモン・インターネット・ファイル・システム（ＣＩＦＳ）プロトコルやネットワーク・ファイル・システム（ＮＦＳ）プロトコルのようなファイルベースのアクセスプロトコルを含むバケットを発行する場合がある。あるいは、クライアントは、ブロックのようなデータコンテナの形をした情報をアクセスする場合、ＳＣＳＩ  ｏｖｅｒ  ＴＣＰ（ｉＳＣＳＩ）プロトコルやＳＣＳＩ  ｏｖｅｒ  ＦＣ（ＦＣＰ）プロトコルのようなブロックベースのアクセスプロトコルを含むパケットを発行する場合がある。
【００１２】
ストレージシステム１２５の管理者は、バックアップオペレーションを実施したい場合、従来のテープバックアップソフトウェアをストレージシステム１２５と共に使用し、ＶＴＬシステム２００へのバックアップオペレーションを実施する場合がある。ＶＴＬシステム２００は、ストレージシステム１２５にとって、リモートテープドライブであるかのように見えるため、ストレージシステム１２５は、従来のテープバックアップソフトウェアを使用して、ＶＴＬシステム２００への従来のテープバックアップオペレーションを実施することもできる。通常、各バックアップオペレーションの結果、ストレージシステム１２５に記憶されているファイルシステム全体が、例えば「バックアップ」としてＶＴＬシステム２００にコピーされる。そのようなコピーの結果、特に、ＶＴＬシステム２００は、相当な量の重複データ、すなわち、ストレージシステム１２５の複数バックアップ間における依然として共通なデータ、及び／又は種々のクライアント１１０のバックアップ間における余分なデータを有することになる場合がある。本発明は例えば、後で詳しく説明するようなサンプリングを利用した新規なデータ重複解消技術により、そのような重複データを無くす。
【００１３】
Ｂ．仮想テープライブラリシステム
図２は、本発明と共に有利に使用されるＶＴＬシステム２００を示す略ブロック図である。例えば、ＶＴＬシステム２００は、ローカルストレージ（ディスク）アレイ１６０のディスク１３０のような記憶装置上の情報の編成に関するストレージサービスを提供するコンピュータである。ＶＴＬシステム２００は例えば、システムバス２２５によって相互接続されたプロセッサ２２２、メモリ２２４、１以上のネットワークアダプタ２２６、及び１以上のストレージアダプタ２２８を含む。各ネットワークアダプタ２２６は、ネットワーク１２０を介してＶＴＬシステム２００をストレージシステム１２５に接続するために必要とされる機械的、電気的、信号的回路を含む。また、後で詳しく説明するように、ＶＴＬシステム２００は、仮想テープライブラリ（ＶＴＬ）モジュール２６０のような種々のモジュールと情報をやりとりするオペレーティングシステム２５０をさらに含む。オペレーティングシステム２５０は、ディスク１３０への論理データオブジェクト記憶手段を実施することができ、また、ＶＴＬシステム２００上で実行されるＶＴＬモジュール２６０のようなアプリケーションによって使用される場合もある。本明細書に記載するように、論理データオブジェクト記憶手段は、例えば、アンカーデータベース（ＤＢ）２７０、及びパターンデータベース２８０として実施される場合がある。
【００１４】
一実施形態において、メモリ２２４は、オペレーティングシステム２５０やＶＴＬモジュール２６０のようなソフトウェアプログラムコードを記憶するために、プロセッサ、及びアダプタからアドレス指定可能な多数の記憶場所を有する。また、プロセッサ、及びアダプタは、そのソフトウェアプログラムコードを実行し、データ構造を操作するように構成された処理要素、及び／又は論理回路を含む。当業者には明らかなように、本明細書に記載する本発明の技術に関係するプログラム命令の記憶、及び実行には、他の処理手段や、種々のコンピュータ読取可能媒体を含む他の記憶手段を使用してもよい。
【００１５】
ストレージアダプタ２２８は、ＶＴＬシステム２００で実行されるオペレーティングシステム２５０と協働し、例えば、ビデオテープ、光学的、ＤＶＤ、磁気テープ、バブルメモリ、電気的ランダムアクセスメモリ、ＭＥＭＳデバイス、並びに、データ、及びパリティ情報を含む情報を記憶するように構成された他の同様の媒体、といったような書き込み可能な記憶装置媒体の任意のタイプのアタッチド・アレイに対する、要求された情報の記憶や読み出しを行う。ただし、本明細書に例示するように、情報は好ましくは、ローカルストレージアレイ１６０のＨＤＤ、及び／又はＤＡＳＤのようなディスクに記憶される。ストレージアダプタは、従来の高性能ＦＣシリアルリンクトポロジのようなＩ／Ｏ相互接続構成を介してそれらのディスクに接続するための入出力（Ｉ／Ｏ）インタフェース回路を備える。
【００１６】
上記のように、オペレーティングシステム２５０は例えば、ディスク１３０上に対して論理データオブジェクト記憶手段を実施する。なお、代替実施形態では、例えば、ファイルシステムのような、他の形態のデータ編成が使用される場合もある。従って、データオブジェクト記憶手段の使用に関する説明は、単なる例として捉えるべきである。さらに、ＶＴＬモジュール２６０は、オペレーティングシステム２５０と協働し、ＶＴＬシステム２００の仮想テープライブラリ機能を実施する。例えば、ＶＴＬモジュール２６０は、データオブジェクト記憶手段を使用してデータを記憶する。なお、ＶＴＬモジュール２６０も、本発明のデータ重複解消技術を実施する。
【００１７】
Ｃ．サンプリングを利用したデータ重複の解消
本発明は、ディスク１３０のようなストレージリソースに記憶される重複データを無くす（重複解消する）ための、サンプリングを利用した技術を提供する。本発明によれば、新たなデータセットがサーバ、例えばストレージシステム１２５、又はシステム２００によって受信されると、その新たなデータセットの中から、１以上のアンカーが識別される。本明細書では、アンカーとは、データ重複の可能性があると考えられる領域を規定する、データセット中のポイントとして定義される。アンカーは、データセットのローリングハッシュを実施することにより発見される場合がある。その場合、アンカーポイント（「アンカー」）は、シグネチャ幅を規定する固定サイズの領域の中から探索される。なお、アンカーは、例えばファイルのようなデータコンテナ内の位置に基づいて選択される場合もあれば、例えばデータセット中の所定のオフセットのような、他のコンテキスト情報に基づいて選択される場合もある。なお、アンカーは、種々の技術を使用して特定することができる。従って、本明細書に記載する技術は、単なる例として捉えるべきである。
【００１８】
新たなデータセットの中から識別された各アンカーについて、そのアンカーが、アンカーデータベース２７０に既に記憶されているか否かの判定が成される。もし、識別されたアンカーが、アンカーデータベースに記憶されていなければ、そのアンカーは、データセット中のそのアンカーの位置を示す情報とともに、アンカーデータベース２７０の中に記憶される。例えば、データセットは、データオブジェクト記憶手段の最上部に配置され、実施されるパターンデータベース２５０の中に記憶される。ただし、代替実施形態として、アンカー位置は単に、データセット中のオフセットであってもよい。もし、識別されたアンカーが、アンカーデータベースの中に既に記憶されていた場合、サーバは、パターンデータベース２５０の中からそのアンカーを探索し、新たなデータセットと、パターンデータベース２５０に記憶されたアンカーを有するデータセットとの間で、アンカーポイントから前後に、ビット単位の比較を実施する。データ比較の結果、新たなデータセットと記憶されたデータセットとの間で一致した、アンカーポイントから前後に続く連続したデータビットの数をそれぞれ示す前方デルタ値、及び後方デルタ値が得られる。新たなデータセット中の重複データ、すなわち、アンカーポイントを中心として後方デルタ値と前方デルタ値の間の範囲にあるデータは、アンカー、前方デルタ値、及び後方デルタ値を識別するストレージインジケータで置き換えられる。
【００１９】
図３は、本発明の一実施形態による、サンプリングを利用したデータ重複解消手順３００のステップの詳細を示すフロー図である。手順３００はステップ３０５から開始され、ステップ３１０へ進み、そこで、新たなデータセットが、ＶＴＬシステム２００のようなサーバによって受信される。図１の例示的実施形態１００において、受信されるデータセットは、ストレージシステム１２５からＶＴＬシステム２００へ伝送される新たなテープバックアップデータストリームからなる場合がある。ただし、代替実施形態では、例えば、ストレージシステム１２５の中に記憶されたファイルのような任意のデータセットが、任意のコンピュータ上で使用される場合もある。従って、受信データセットがＶＴＬシステム２００へ伝送されるテープバックアップストリームであるものとした上記説明は、単なる例として捉えるべきである。上記のように、代替実施形態では、任意の形のデータセットが、任意のコンピュータ上で使用される場合がある。従って、本発明の教示は、以下で説明するＶＴＬシステム環境とは異なる環境でも、使用される場合がある。
【００２０】
新たなデータセットの受信に応答し、ステップ３１５において、ＶＴＬモジュール２６０は、新たなデータセットの中から１以上のアンカーを識別する。本発明によれば、アンカーは、複数の方法で識別することができる。一つのアンカー識別方法は、データセット中の所定のオフセットにアンカーを置くことである。こうしたオフセットは、固定であってもよいし、データセット内のデータのタイプに基づいて決めてもよい。例えば、データセットがテープアーカイブバックアップデータストリームである場合、アンカーは、データストリーム中の各レコードの始めに置かれる場合がある。アンカーを識別する他の方法は、例えば、データセットに沿って固定サイズのウィンドウを使用して、ローリングハッシュを実施することである。ハッシュ値（モジューロ  定数）が所定の値に等しいとき、そのウィンドウの中に、アンカーが配置される。例えば、５１２ビットのウィンドウサイズを使用するローリングハッシュが使用される場合がある。ハッシュ値  モジューロ  Ｎが０に等しい場合、アンカーポイントは、ウィンドウの開始位置に配かれる場合がある。
【００２１】
アンカーを識別した後、ＶＴＬモジュール２６０は次に、ステップ３２０において、識別されたアンカーが、アンカーデータベース２７０の中に置かれているか否かを判定する。もし、識別されたアンカーが、アンカーデータベースの中に記憶されていなかった場合、手順３００は、ステップ３２５へ分岐し、そこでＶＴＬモジュールは、そのアンカーをアンカーデータベースの中に置く。例えば、あまりにも頻繁に使用されるアンカーのように、アンカーによっては、アンカーデータベースに記憶されないものもある。ＶＴＬモジュールは、そのように頻繁に発生するアンカーを有するように構成される場合があり、代替実施形態では、そのように頻繁に発生するアンカーを追跡管理し、アンカーデータベース内に保持するべきでないアンカーを識別するように構成される場合もある。次に、ステップ３３０において、データセット中に別のアンカーがまだ有るか否かの判定が成される。まだある場合、手順はステップ３１５へループバックし、そこで、ＶＴＬモジュール２６０は、データセット内の他のアンカーを識別する。無ければ、手順３００はステップ３５５にて完了する。
【００２２】
一方、識別されたアンカーが、アンカーデータベース３７０の中で見付かった場合、ＶＴＬモジュール２６０は次に、パターンデータベース２８０内のアンカーを取り巻く領域と、受信したデータセット中のアンカーポイントとの間で、ビット単位（又は、バイト単位）の比較を開始し、前方デルタ値、及び後方デルタ値を識別する（ステップ３４０）。これらのデルタ値は、パターンデータベース２８０中の前記領域と、受信したデータセットとの間で一致した、アンカーポイントから前後に続く連続したビットの数を示す。例えば、アンカーポイントから前方に１千ビットにわたって一致し、アンカーポイントから後方に１５ビットだけ一致した場合、後方デルタ値は、値１５にセットされ、前方デルタ値は、値１０００にセットされる。なお、アンカーの配置にもよるが、状況によっては、デルタ値はゼロになる場合もある。例えば、アンカーポイントが、ローリングハッシュに使用されるウィンドウの開始位置として選択された場合、そのアンカーポイントよりも前方には、パターンデータベースとの間で一致するビットが何も存在しない場合がある。前方デルタ値／後方デルタ値（「デルタ」）は通常、スライド移動されるハッシュウィンドウの幅を包含する。ただし、これは、本発明にとって必須ではない。前方デルタ、後方デルタとともにアンカーポイントを使用することにより、重複データの範囲、すなわち、アンカーポイントから後ろに後方デルタ（ビット数）の位置からアンカーポイントの前方に前方デルタ（ビット数）の位置までの範囲にあるデータを識別することができる。本発明によれば、識別された範囲の重複データは記憶装置から削除され、それによって圧縮が実現され、ストレージリソースの使用効率も向上される。
【００２３】
次に、ステップ３４５において、新たなデータセット中の識別された範囲の重複データは、ストレージインジケータで置き換えられる。例えば、ストレージインジケータは、アンカー、並びに、前方デルタ、及び後方デルタを識別する。ストレージインジケータのサイズが、置換された重複データのサイズよりも小さければ、データセットの圧縮が得られる。従って、実施形態の詳細によっては、重複データを置換する前に、最小サイズが必要となる場合もある。例えば、ストレージインジケータに２５６ビットが必要とされる場合、（前方デルタ値＋後方デルタ値）＞２５６でなければ、何も圧縮は起きない。なお、代替実施形態として、システムは、置換を行う前の最小サイズに関して、管理者による調節が可能な閾値を有する場合がある。そうした閾値によれば、管理者は、予想するデータの性質に応じてシステムの処理能力をチューニングすることができる。従って、システムは、例えばストレージインジケータのサイズのような静的な閾値と、例えば管理者が設定するような動的な閾値との両方を有する場合もある。この場合も、データセット中に他にそれ以上のアンカーがなければ、手順は、ステップ３３５にて完了する。
【００２４】
ステップ３４０で識別される重複データの範囲には、さらに別のアンカーポイントが含まれる場合がある。ただし、そうしたアンカーポイントをステップ３１５で処理する必要はないであろう。処理すべき次のアンカーポイントは、識別された重複データの範囲の後ろにある新たなデータの中にあるであろう。また、見落とされたアンカーポイントをアンカー識別技術を使用して計算する必要もないかもしれない。重複データ領域中の新たなアンカーポイントのセットは、元のデータ領域中にあるアンカーポイントのセットと同じものになる。処理能力上の利点は、一致する長いデータストリームを処理する場合に、計算、及び処理しなければならないアンカーポイントの数が、比較的少なくて済む点である。
【００２５】
また、もし、新たなデータをストレージサーバに書き込む前に重複データを識別することが出来れば、新たなデータをＶＴＬシステム２００に書き込む必要は、全くないかもしれない。これにより、ネットワークを介したＩ／Ｏオペレーションの数を減らすことができるという利点も得られるであろう。
【００２６】
図４は、既に記憶されたデータセット４０５と、新たなデータセット４１０との間の前方デルタ、及び後方デルタの生成を示す環境４００の略図である。古いデータセット４０５、すなわち、ＶＴＬシステム２００によって既に受信され、処理されたデータセットの中に、３つのアンカーＡ１、Ａ２、Ａ３が既に識別されている。新たなデータセット、すなわち、現在処理中のデータセットの中に、単一のアンカーＡ２が存在するという判定がなされた。これに応答し、ＶＴＬシステム２００は、古いデータセット４０５と新たなデータセット４１０の両方にあるアンカーＡ２の前後の領域に関して、ビット単位の比較を開始する。ここで、各データセットにおいて、データが、前方ポイント４２０まで一致し、且つ後方ポイント４１５まで一致したものと仮定する。その場合、新たなデータセット４１０中のポイント４１５とポイント４２０の間の領域が、ストレージインジケータによって置き換えられる。
【００２７】
図５は、本発明の一実施形態による、ストレージインジケータによる置換を示す環境５００の略図である。古いデータセット４０５と新たなデータセット４１０はいずれも、アンカーＡ２を中心としてその付近にある。古いデータセット４０５中のアンカー付近の領域のデータは、Ｎ、Ｃ、Ｄ、Ｅ（アンカーポイント）、Ｆ、Ｇ、Ｈ、Ｏなどの値を有している。同様に、新たなデータセット４１０中のアンカー付近の領域のデータは、Ａ、Ｂ、Ｃ、Ｄ、Ｅ（アンカーポイント）、Ｆ、Ｇ、Ｈ、Ｉなどの値を有している。図示の実施形態では、アンカーポイントが識別されると、アンカーポイントから前後に、ビット単位の比較が行われる。各データセットのアンカーポイントの前方では、データＦ、Ｇ、及びＨだけが一致するという判定、すなわち、次のデータは、古いデータセット４０５では、Ｏの値を有するデータであり、新たなデータセット４１０では、Ｉの値を有するデータであるという判定がなされる。同様に、各データセットのアンカーポイントの後方では、データＣ、及びＤだけが一致するという判定がなされる。次に、新たなデータセット４１０の中のそれら６つの領域（アンカーＥを含む）にあるデータ（すなわち、ＣとＨの間の領域）は、ストレージインジケータ５０５で置き換えられる。従って、新たなデータセット４１０は、データＡ、Ｂ、ストレージインジケータ５０５、Ｉ、Ｊ、Ｋ、Ｌ、Ｍなどを含む新たなデータセット４１０‘に変更される。
【００２８】
例えば、ストレージインジケータ５０５は、アンカー識別子（ＩＤ）フィールド５１０、前方デルタフィールド５１５、及び後方デルタフィールド５２０を含む。アンカーＩＤフィールド５１０は、そのストレージインジケータ５０５に関連するアンカーを識別する。前方デルタフィールド、及び後方デルタフィールド５１５、５２０は、既に置き換えられた、アンカーの各側にある連続したビットの数を示す。従って、この例では、前方デルタ値は、データＦ、Ｇ、およびＨに含まれるビットの数を示し、後方デルタ値は、データＣ、及びＤに含まれるビットの数を示す。元のデータを復元（重複解消）するとき、システムは、ストレージインジケータによって識別されるパターンデータベース中の記憶されたデータを読み出し、それを復元されたデータに挿入する。例えば、システムは、ストレージインジケータが存在することを識別すると、識別されたアンカーを探索し、デルタ値によって指定されるアンカーポイントから前後にデータを読み出す。そして、その領域が、ストレージインジケータの代わりにデータセットの中に
【００２９】
アンカーデータベース２７０は、ステップ３２０において、古いデータセット４０５と新たなデータセット４１０の間の重複データを識別するために使用される。新たなデータセット４１０が、ＶＴＬシステム２００へ書き込まれる場合、ＶＴＬは、新たなデータセット４１０中のどこに重複データがあるのかに関する知識を有する場合がある。例えば、現在の完全バックアップに関する新たなデータは、最後の完全バックアップに関するデータに対して、最も多くの重複データを有することになるであろう。また、２つの完全バックアップにおいて、重複データの範囲は、同じ順序で現れることになるであろう。したがって、重複データを識別するためには、前回の完全バックアップに対応するアンカーポイントを順番にメモリにロードし、新たなデータセット４１０中のアンカーと比較すればよい。これによって、非常に少ないメモリ要件で、重複データ領域の非常に効率的な識別が可能になる。
【００３０】
代替実施形態では、コンピュータ・スーパー・アンカーにより、アンカー階層を生成する場合がある。スーパーアンカーは、例えば、複数の隣り合うアンカーに基づいてハッシュを計算することにより生成される。スーパーアンカーの数は、アンカーの数よりも少ないことが望ましく、それによって、スーパーアンカーを識別する速度を向上させることができる。スーパーアンカーに基づく一致が見付かると、システムは、複数の隣り合うアンカーにわたる重複データの範囲を識別する。
【００３１】
なお、本明細書の説明は、ストレージ重複解消を例として書かれているが、本発明の原理は、通信リンク上での重複解消にも使用される場合がある。そのような代替実施形態では、送信側システムが、上記の重複解消技術を実施することにより、データの伝送に使用される帯域幅の大きさを最小限に抑える場合がある。ソースシステムと宛先システムは、同期されたパターン、及びアンカーデータベースを共用するように動作しなければならない。
【００３２】
上記の説明は、本発明の特定の幾つかの実施形態に関するものである。しかしながら、当業者には明らかなように、それらの実施形態の利点の一部、又は全部を維持しつつ、記載した実施形態に対して、他にも変更や修正を施すことが可能である。例えば、本発明の教示は、コンピュータ上で実行されるプログラム命令を有するコンピュータ読取可能媒体を含むソフトウェアで実施しても、ハードウェアで実施しても、ファームウェアで実施してもよく、あるいは、それらの組み合わせで実施してもよい。さらに、本明細書の説明は、ＶＴＬシステムを例として書かれているが、本発明の教示が、それに限定されることはない。本発明は、例えばファイルシステムのような任意のデータ記憶を使用する如何なるコンピュータ環境でも利用することができる。従って、本明細書の説明は、単なる例として捉えるべきものであり、本発明の範囲を何ら制限するものではない。従って、添付の特許請求の範囲の目的は、そうした変更や修正も全て、本発明の真の思想、及び範囲の中に収めることにある。
【図面の簡単な説明】
【００３３】
【図１】本発明の一実施形態による仮想テープライブラリ（ＶＴＬ）システムを含む例示的なストレージシステム環境を示す略ブロック図である。
【図２】本発明の一実施形態によるＶＴＬシステムを示す略ブロック図である。
【図３】本発明の一実施形態による、サンプリングを利用したデータ重複解消手順を実施する手順のステップの詳細を示すフロー図である。
【図４】本発明の一実施形態による、アンカーポイントを中心とした前方デルタ、及び後方デルタの形成を示す図である。
【図５】本発明の一実施形態による、重複データのストレージインジケータによる置き換えを示すブロック図である。
【図１】
2009535704.tif 000003
【図２】
2009535704.tif 000004
【図３】
2009535704.tif 000005
【図４】
2009535704.tif 000006
【図５】
2009535704.tif 000007
【手続補正書】
【提出日】平成21年1月6日(2009.1.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピュータで実施される方法であって、
データセットの中からアンカーを識別するステップであって、該アンカーは、データセット中の関心のある領域を規定するポイントとして定義される、アンカーを識別するステップと、
識別されたアンカーが、アンカーデータベースの中に在るか否かを判定するステップと、
前記アンカーが、アンカーデータベースの中に在るという判定に応答して、前記データセットと記憶済みデータセットとの間のデータ比較を実施し、識別されたアンカーに対する前方デルタ値、及び後方デルタ値を識別するステップと、
前記アンカー、前記前方デルタ値、及び前記後方デルタ値によって識別された前記データセットの領域をストレージインジケータで置き換え、変更されたデータセットを形成するステップと
を含む方法。
【請求項２】
前記アンカーを識別するステップは、前記データセットに対してローリングハッシュを実施し、前記データセット内の所定の位置にアンカーを配置するステップを含む、請求項１に記載の、コンピュータで実施される方法。
【請求項３】
前記記憶済みデータセットはパターンデータベースに記憶され、前記ストレージインジケータは、アンカー識別子、前記前方デルタ値、及び前記後方デルタ値を含む、請求項１に記載の、コンピュータで実施される方法。
【請求項４】
前記データセット中の複数の隣り合うアンカーに対してハッシュを計算することにより、アンカー階層を形成するステップをさらに含む、請求項１に記載の、コンピュータで実施される方法。
【請求項５】
前記変更されたデータセットをデータオブジェクト記憶手段に記憶するステップをさらに含み、前記データオブジェクト記憶手段はファイルシステムからなる、請求項１に記載の、コンピュータで実施される方法。
【請求項６】
２つの類似するデータセット間における重複データを見付けるステップをさらに含み、前記類似するデータセットは、共通データと固有データの混在を含み、重複データは、新たなデータセットのアンカーポイントを類似データのアンカーポイントと比較することによって発見され、前記類似データのアンカーポイントは、前記新たなデータセット内のアンカーポイントのパターンに基づいて識別される、請求項１に記載の、コンピュータで実施される方法。
【請求項７】
前記データセット中の領域を置き換える前に、前記前方デルタ値、及び前記後方デルタ値の最小サイズの閾値をセットするステップをさらに含む、請求項１に記載の、コンピュータで実施される方法。
【請求項８】
データセットを提供するように構成されたストレージシステムと、
前記ストレージシステムから前記データセットを受信するように構成され、前記データセットの中からアンカーを識別するように構成され、識別されたアンカーがアンカーデータベースの中に在るか否かを判定するようにさらに構成された仮想テープライブラリシステムであって、当該仮想テープライブラリシステムが、前記アンカーが前記アンカーデータベース中に在るという判定に応答して、前記データセットと記憶済みデータセットとの間のデータ比較を実施し、前方デルタ値、及び後方デルタ値を識別するようにさらに構成される、仮想テープライブラリシステムと
を含み、前記仮想テープライブラリシステムは、前記アンカー、前記前方デルタ値、及び前記後方デルタ値によって識別される前記データセットの領域をストレージインジケータで置き換え、変更されたデータセットを形成するように更に構成される、システム。
【請求項９】
前記ストレージインジケータは、アンカー識別子、前記前方デルタ値、及び前記後方デルタ値を含む、請求項８に記載のシステム。
【請求項１０】
前記アンカーは、前記データセットに対してローリングハッシュを実施することによって識別され、または前記データセット内の所定の位置にアンカーを配置することによって識別される、請求項８に記載のシステム。
【国際調査報告】
2009535704.tif 000008
2009535704.tif 000009
2009535704.tif 000010