(57)【特許請求の範囲】
【請求項１】
コンテンツのバックアップに使用されるストレージ装置において、
書き込み対象であるコンテンツから切り出されるチャンクのうちコンテンツタイプ毎に共通して出現する第１のチャンクの格納に使用する１つ又は複数の第１のコンテナと、第１のチャンク以外のチャンクの格納に使用する１つ又は複数の第２のコンテナの記憶領域を提供する記憶装置と、
書き込み対象であるコンテンツから切り出される各チャンクが、前記第１のコンテナに格納されたチャンクと重複する第１の重複チャンクか否かを判定し、前記第１の重複チャンクでないと判定されたチャンクについてのみ、各チャンクが前記第２のコンテナに格納されたチャンクと重複する第２の重複チャンクか否かを更に判定し、前記第２の重複チャンクでもないと判定されたチャンクだけを前記第２のコンテナに格納するバックアップ部と
を有するストレージ装置。
【請求項２】
請求項１に記載のストレージ装置において、
前記第１のコンテナの管理情報である第１のコンテナ索引表を有するメモリを備え、
前記バックアップ部は、前記第１のコンテナ索引表の検索により、処理対象とするチャンクと同一のチャンクが前記第１のコンテナに存在しないと判定された場合、チャンク索引表を参照して重複チャンクか否かを判定する
ことを特徴とするストレージ装置。
【請求項３】
請求項１に記載のストレージ装置において、
前記バックアップ部は、
コンテンツのバックアップ開始前に特定された前記第１のチャンクと、コンテンツのバックアップ開始後に特定された前記第１のチャンクを前記第１のコンテナに格納し、
コンテンツのバックアップ開始前に特定された前記第１のチャンクの管理情報と、コンテンツのバックアップ開始後に特定された前記第１のチャンクの管理情報を第１のコンテナ索引表に格納する
ことを特徴とするストレージ装置。
【請求項４】
請求項３に記載のストレージ装置において、
前記バックアップ部は、コンテンツのバックアップ開始後における前記第１のチャンクの特定処理を、各コンテンツの書き込みと並行に実行する
ことを特徴とするストレージ装置。
【請求項５】
請求項１に記載のストレージ装置において、
前記第１のコンテナは、第１の静的コンテナと第１の動的コンテナとを有し、
前記第１のコンテナと対をなす第１のコンテナ索引表は、第１の静的コンテナ索引表と第１の動的コンテナ索引表とを有し、
前記バックアップ部は、
コンテンツのバックアップ開始前に特定された前記第１のチャンクを前記第１の静的コンテナに格納すると共に、その管理情報を前記第１の静的コンテナ索引表に格納し、
コンテンツのバックアップ開始後に特定された前記第１のチャンクを前記第１の動的コンテナに格納すると共に、その管理情報を前記第１の動的コンテナ索引表に格納する
ことを特徴とするストレージ装置。
【請求項６】
請求項５に記載のストレージ装置において、
前記バックアップ部は、コンテンツのバックアップ開始後、コンテンツのバックアップ開始前には前記第１のコンテナが作成されなかった全てのコンテンツタイプを対象に第１のチャンクの特定処理を実行し、特定された前記第１のチャンクの管理情報を前記第１の動的コンテナ索引表に格納する
ことを特徴とするストレージ装置。
【請求項７】
請求項１に記載のストレージ装置において、
前記第１のコンテナと対をなす第１のコンテナ索引表は、第１の静的コンテナ索引表と第１の動的コンテナ索引表とを有し、
前記バックアップ部は、
コンテンツのバックアップ開始前に、事前に選択されたコンテンツタイプについて特定された前記第１のチャンクの管理情報を前記第１の静的コンテナ索引表に格納し、
コンテンツのバックアップ開始後に、前記選択されたコンテンツタイプについて特定された前記第１のチャンクの管理情報を前記第１の動的コンテナ索引表に格納する
ことを特徴とするストレージ装置。
【請求項８】
請求項７に記載のストレージ装置において、
前記バックアップ部は、コンテンツのバックアップ開始前には選択されなかった全てのコンテンツタイプを対象に前記第１のチャンクの特定処理を実行し、コンテンツのバックアップ開始後に特定された前記第１のチャンクの管理情報を前記第１の動的コンテナ索引表に格納する
ことを特徴とするストレージ装置。
【請求項９】
請求項７に記載のストレージ装置において、
前記第１のコンテナは、第１の静的コンテナと第１の動的コンテナとを有し、
前記バックアップ部は、
コンテンツのバックアップ開始前に、事前に選択されたコンテンツタイプについて特定された前記第１のチャンクを前記第１の静的コンテナに格納し、
コンテンツのバックアップ開始後に、前記選択されたコンテンツタイプについて特定された前記第１のチャンクを前記第１の動的コンテナに格納する
ことを特徴とするストレージ装置。
【請求項１０】
請求項７に記載のストレージ装置において、
前記バックアップ部は、操作画面上におけるオペレータの選択操作を通じて、コンテンツタイプの選択を受付ける
ことを特徴とするストレージ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、重複排除方式に基づいてコンテンツをバックアップするストレージ装置に関する。
【背景技術】
【０００２】
ホスト計算機には、ネットワーク経由でストレージ装置が接続される。この種のストレージ装置は、データを記憶する記憶デバイスとして、例えば複数のハードディスク装置（ＨＤＤ：Hard Disk Drive）を備える。保存媒体に要するコスト低減のため、記憶デバイスにデータを格納する際には、データ量の削減処理が実行される。データ量の削減には、ファイル圧縮処理（Compression）や重複排除処理（Deduplication）が用いられる。ファイル圧縮処理は、１ファイル内で同一内容のデータセグメントを縮約することにより、データ容量を削減する。一方、重複排除処理は、１ファイル内だけでなく、ファイル間で検出される同一内容のデータセグメントを縮約することにより、ファイルシステムやストレージシステムの総データ容量を削減する。
【０００３】
以下では、重複排除処理の単位となるデータセグメントを「チャンク（Chunk）」という。また、複数のチャンクをまとめたデータを「コンテナ」という。また、記憶デバイスに格納する単位である論理的にまとまったデータを「コンテンツ（Content）」という。コンテンツには、通常ファイルの他、例えばアーカイブファイル、バックアップファイル、仮想ボリュームファイルなどの通常のファイルを集約したファイルも含まれる。重複排除処理されたチャンクは、コンテナ単位で記憶デバイスに格納される。
【０００４】
コンテナには、予め所定のチャンク数または容量が設定されている。１または２以上のコンテンツから生成されたチャンクは、コンテナが一杯になるまでまとめられ、コンテナ単位で記憶デバイスに書き込まれる。書き込み後、コンテナ内のチャンク格納位置を示すコンテナ索引表が、各コンテナに対応して作成される。この際、いずれのチャンクがいずれのコンテナに格納されているかを示すチャンク索引表も作成される。例えば複数世代に亘るバックアップデータが重複排除されて記憶デバイスに格納される場合、バックアップのタイミングによっては、バックアップの世代毎に異なるコンテナが用意され、各コンテナに各世代のバックアップデータが格納される（例えば特許文献１を参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許第６９２８５２６号明細書
【非特許文献】
【０００６】
【非特許文献１】Andrew S. Tanenbaum and Albert S. Woodhull, Operating Systems: Design and Implementation, Third Edition, Prentice Hall, 2006. 3.4.7 Simulating LRU in Software.
【非特許文献２】Donald E. Knuth, The Art of Computer Programming, Volume 3 /Sorting and Searching, Addison-Wesley Publishing Company, 1973. 6.4. Hashing, 6.5. Retrieval on Secondary Keys.
【非特許文献３】Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, Second Edition, MIT press, 2001. 32.2The Rabin-Karp algorithm.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
なお、バックアップデータには、複数のコンテンツに共通して出現するチャンクが存在する。以下、このチャンクを「普遍チャンク」という。普遍チャンクは、初期バックアプ時に用意されたコンテナに格納される。
【０００８】
ところが、従来手法には、(1) 普遍チャンクが初期バックアップ時に用意されたコンテナに格納されている場合において、(2) 重複排除処理が実行された複数世代目のバックアップデータをリストアするときに、以下の理由により、リストア性能が劣化する問題がある。具体的には、普遍チャンクを読み出すには、同じコンテナに含まれる普遍チャンク以外のほとんど参照されないチャンクも同時に読み出す必要がある。すなわち、リストアに必要なデータの読み出し効率が悪い。
【０００９】
また、従来手法には、バックアップ性能も低い問題がある。やはり、重複排除処理の際に参照するコンテナ索引表には、普遍チャンクだけでなく、ほとんど参照されることのないチャンクの管理情報も含まれているためである。しかも、普遍チャンクは、アクセスの多いデータをメモリに保持しておくキャッシュとは異なり、複数のバックアップ世代に亘って必ず現れるものの、必ずしもアクセスが多いチャンクではない。そのため、通常のキャッシュ機構では、必ずしもメモリ上には存在せず、ハードディスク装置上に保持されている。このため、コンテナ索引表は、重複排除処理の際にメモリ上に読み出され展開されるが、前述の通り、コンテナ索引表には参照する必要の無い普遍チャンク以外の管理情報も多く含まれている。このため、データ処理効率が悪く、また、メモリの利用効率の点でも問題がある。
【００１０】
なお、普遍チャンクには、例えば0x0 で埋められたデータ、0xF で埋められたデータ、コンテンツの終端を示すトレーラデータ、複数のコンテンツを集約して１つのコンテンツを作成するアーカイブファイルのパディングデータなどがある。因みに、パディングデータは、集約したコンテンツの境界が、ある規定バイトの整数倍になるように付加されるデータである。
【課題を解決するための手段】
【００１１】
本発明は以上の技術的課題を考慮してなされたものであり、コンテンツタイプ毎に共通して出現する第１のチャンクを、第１のコンテナに格納して管理するストレージ装置を提案する。
【００１２】
より具体的には、本発明に係るストレージ装置は、(1) 第１のチャンクの格納に使用する１つ又は複数の第１のコンテナと、第１のチャンク以外のチャンクの格納に使用する１つ又は複数の第２のコンテナの記憶領域を提供する記憶装置と、(2) 書き込み対象であるコンテンツから切り出される各チャンクが、前記第１のコンテナに格納されたチャンクと重複する第１の重複チャンクか否かを判定し、第１の重複チャンクでないと判定されたチャンクについてのみ、各チャンクが前記第２のコンテナに格納されたチャンクと重複する第２の重複チャンクか否かを更に判定し、第２の重複チャンクでもないと判定されたチャンクだけを前記第２のコンテナに格納するバックアップ部とを有する。
【００１３】
前述したように、本発明に係るストレージ装置においては、コンテンツタイプ毎に共通して出現する第１のチャンクは第１のコンテナに集約される。第１のコンテナには、従来方式のように、各コンテンツにおいて、ほとんど参照されることのないチャンクが含まれていない。このため、第１のチャンクの検出効率が高く、バックアップ性能が向上する。また、リストア時にも、第１のコンテナには、リストアに必須の第１のチャンクが集約されているため、効率的にリストアを実行できる。
【発明の効果】
【００１４】
本発明によれば、バックアップ性能及びリストア性能を従来に比して向上させることができる。上記した以外の課題、構成及び効果は、以下の実施形態の説明により明らかにされる。
【図面の簡単な説明】
【００１５】
【図１】第１の実施形態に係るストレージ装置のブロック構成を示す図。
【図２】従来のバックアップ処理及びリストア処理を概念的に説明する図。
【図３】第１の実施形態に係るバックアップ処理を概念的に説明する図。
【図４Ａ】バックアップ処理とリストア処理で利用するコンテナ索引表およびチャンク索引表の構成例を示す図表。
【図４Ｂ】リストア処理で使用するコンテンツ索引表の構成例を示す図表。
【図５】第１の実施形態に係るバックアップ処理の処理手順を示すフローチャート。
【図６】第１の実施形態に係るリストア処理の処理手順を示すフローチャート。
【図７】第１の実施形態に係る計測表の構成例を示す図表。
【図８】第１の実施形態に係る普遍チャンクの特定処理手順を示すフローチャート。
【図９】第２の実施形態に係る普遍チャンクと管理情報の格納方法を概念的に示す図。
【図１０】第３の実施形態に係る普遍チャンクと管理情報の格納方法を概念的に示す図。
【図１１】第４の実施形態に係る普遍チャンクと管理情報の格納方法を概念的に示す図。
【図１２】第４の実施形態に係る普遍チャンクの特定処理手順を示すフローチャート。
【図１３】第５の実施形態に係る選択画面例を示す図。
【図１４】第５の実施形態に係る普遍チャンクと管理情報の格納方法を概念的に示す図。
【発明を実施するための形態】
【００１６】
以下、図面に基づいて、本発明の実施の形態を説明する。なお、本発明の実施態様は、後述する形態例に限定されるものではなく、その技術思想の範囲において、種々の変形が可能である。
【００１７】
（１）第１の実施形態
（１−１）ストレージ装置に搭載する重複排除機能の概要
まず、本実施形態に係る重複排除機能の概要を説明する。実施形態に係るストレージ装置は、ネットワーク経由でホスト計算機に接続される。ストレージ装置は、データを記憶する記憶デバイスとして、例えば複数のハードディスク装置（ＨＤＤ：Hard Disk Drive）を有する。ストレージ装置には、記憶デバイスにデータを格納する際にデータ量を削減する処理機能が搭載されている。データ量の削減には、例えばファイル圧縮処理（Compression）や重複排除処理（Deduplication）が用いられる。ファイル圧縮処理は、１ファイル内で同一内容のデータセグメントを縮約することにより、データ容量を削減する。一方、重複排除処理は、１ファイル内だけでなく、ファイル間で検出される同一内容のデータセグメントを縮約することにより、ファイルシステムやストレージシステムの総データ容量を削減する。
【００１８】
本実施形態の説明でも、重複排除処理の単位となるデータセグメントを「チャンク（Chunk）」といい、複数のチャンクをまとめたデータを「コンテナ」という。また、記憶デバイスに格納する単位である論理的にまとまったデータを「コンテンツ（Content）」という。以下に説明する実施形態の場合も、コンテンツには、通常のファイルの他、例えばアーカイブファイル、バックアップファイル、仮想ボリュームファイルなどの通常のファイルを集約したファイルが含まれる。また、重複排除処理されたチャンクは、コンテナ単位で記憶デバイスに格納される。
【００１９】
チャンク単位の重複排除処理は、以下のように実行される。ストレージ装置は、任意のチャンクをハードディスク装置に格納する前に、同じ内容のチャンクがハードディスク装置に既に格納されているか否かを判定する。同じチャンクはハードディスク上に存在しないと判定された場合、ストレージ装置は、当該チャンクをそのままハードディスク装置に格納する。一方、同じチャンクがハードディスク装置に存在すると判定された場合、ストレージ装置は、当該チャンク（以下「重複チャンク」という）をハードディスク装置に格納せずに、その格納場所を示すリンク情報をハードディスク装置に格納する。このように、実施形態に係るストレージ装置は、チャンクの重複排除処理を繰り返し実行し、重複チャンクの多重登録を排除する。この重複チャンクの排除処理により、実施形態に係るストレージ装置は、ハードディスク装置の使用容量を抑制し、バックアップ処理を高速化する。
【００２０】
前述したように、「コンテナ」は、１または２以上のコンテンツを分割して得られる複数のチャンクで構成される、ハードディスク装置に格納する際の処理単位である。また、各「コンテナ」に対し、ストレージ装置は、コンテナを構成する各チャンクの配置を管理するコンテナ索引表を作成する。コンテナ索引表には、チャンクのオフセット（コンテナ内における位置）とチャンクのサイズが格納される。コンテナ索引表は、チャンクの重複判定に利用される。
【００２１】
この他、ストレージ装置は、チャンク索引表も作成する。チャンク索引表は、バックアップデータの分割により生成されたチャンクがどのコンテナ索引表に格納されているかを示すテーブルである。チャンク索引表は、チャンクを格納するコンテナが決定された時に、ストレージ装置により作成される。チャンク索引表は、バックアップ処理の実行時に、チャンクの重複排除判定に使用するコンテナ索引表を決定するために利用される。
【００２２】
一般に、チャンクのサイズは数キロバイト以上である。このため、重複判定処理の実行時に、チャンクの先頭から順番にチャンク同士を比較すると、多くの処理時間とコストを必要とする。そこで、実施形態に係るストレージ装置は、チャンクのメッセージダイジェストを利用し、短時間かつ低コストで重複判定処理の実行を可能とする。メッセージダイジェストとは、任意の長さのデータ入力に対し、固定長のダイジェストを出力する技術である。本明細書では、メッセージダイジェストの出力結果を、フィンガプリント（FP：finger print）という。フィンガプリントは、ハッシュ関数を用いて取得することができる。例えばＳＨＡ２５６などの乱数性が極めて高く、チャンクに対して一意に定まる可能性の高いハッシュ関数を利用する。
【００２３】
本実施形態では、前述したコンテナ索引表に各チャンクのフィンガプリントを格納し、重複判定処理時には、チャンクのフィンガプリント同士を比較する。これにより、チャンク同士をビット単位で比較する場合に比べて、重複判定処理の高速化及び低コスト化を実現する。
【００２４】
また、データの完全性を保証し、信頼性の高いバックアップを実現するために、本実施形態では、ライトワンス型の記憶装置を使用する。ライトワンス型の記憶装置は、データの書き込みは１回限りであるが、読み取りは何度でも可能である。ライトワンス型の記憶装置に書き込まれたデータは、消去も改変もできないため、証拠保全のアーカイブなどに適している。このような記憶装置には、例えばＲＯＭ（Read Only Memory）光ディスクを使用する光ディスク装置がある。一般的に、磁気ディスク装置は書き込まれたデータを更新できるため、ライトワンス型の記憶装置ではない。しかし、ファイルシステムやドライバ装置の構成を工夫して追記のみを許可することにより（データの上書きを禁止することにより）、磁気ディスク装置をライトワンス型の記憶装置として利用することができる。本実施形態の望ましい形態では、主に、データのバックアップに適した追記型のハードディスク装置をバックアップ用の記憶デバイスに適用する。
【００２５】
前述したコンテナには、予め所定のチャンク数または容量が設定されている。このため、チャンクは、コンテナが一杯になるまでメモリ側で集約され、コンテナが一杯になると、コンテナ単位でバックアップ用の記憶デバイスに書き込まれる。例えば記憶デバイスに追記型のハードディスク装置を使用する場合、ストレージ装置は、コンテナが一杯になるまでメモリ上のコンテナにチャンクを追記する。同時に、ストレージ装置は、コンテナ内のチャンクの配置を管理するコンテナ索引表と、チャンクとコンテナ索引表の対応関係を管理するチャンク索引表を作成する。なお、バックアップデータには、バックアップ世代毎に必ず出現する普遍チャンクが存在し、その普遍チャンクは初期バックアップ時に用意されたコンテナに格納される。
【００２６】
前述したように、普遍チャンクを初期バックアップ時に用意したコンテナに格納する場合、従来手法では、同じコンテナ内に普遍チャンク以外のチャンクも一緒に保存される。このため、従来手法では、複数世代目に重複排除処理を実行したバックアップデータをリストアする際に、普遍チャンクを含んでいるが、そのリストアでは参照する必要がないチャンクも含むコンテナを参照する。しかし、コンテナに占める普遍チャンクの割合が少ない場合、普遍チャンクが複数のコンテナに分散する場合もある。この場合、必要とする普遍チャンクを含む他のコンテナを別途参照する必要があり、ハードディスク装置からの読み出し回数が増加してしまう。このため、リストア性能が劣化する問題がある。また、普遍チャンクを含むコンテナをメモリ上に展開すると、ほとんど参照されないチャンクも一緒に展開されることになるため、メモリの利用効率が悪い問題がある。
【００２７】
また、従来手法では、バックアップの際、必ずコンテナ索引表を参照し、データの重複排除処理を実行する。この際、複数世代目の重複排除処理に際し、普遍チャンクだけでなく、ほとんど参照されないチャンクの管理情報も含むコンテナ索引表を参照する必要がある。このため、バックアップ性能が低下する問題がある。また、コンテナ索引表では、普遍チャンクの管理情報だけでなく、ほとんど参照されないチャンクの管理情報も含まれるため、メモリの利用効率が悪い問題もある。
【００２８】
そこで、本実施形態では、複数世代に亘るバックアップデータを重複排除して記憶デバイスに格納する際に、各バックアップ世代に普遍的に出現する普遍チャンクを、普遍チャンク専用のコンテナ（以下「普遍コンテナ」という）に格納する。さらに、本実施形態では、作成した普遍コンテナを常にメモリ上に保持し、ハードディスク装置からの読み出し回数を低減する。これにより、バックアップ性能およびリストア性能の向上を実現する。
【００２９】
なお、普遍チャンクは、コンテンツタイプ（通常ファイル、仮想ディスクボリューム、アーカイブファイル等のファイルフォーマット）毎に共通して出現する。従って、普遍チャンクは、コンテンツタイプ毎の重複チャンクを比較することにより、特定することができる。
【００３０】
（１−２）ストレージ装置の構成
図１に、本実施形態に係るストレージ装置１００のハードウェア構成を示す。図１に示すように、ストレージ装置１００は、ネットワーク１７４を介して不図示のバックアップサーバその他の上位装置に接続されている。ネットワーク１７４は、例えばＬＡＮ（Local Area Network）、インターネット、公衆回線または専用回線などであってもよい。
【００３１】
ストレージ装置１００は、管理者端末装置１７２とネットワーク経由で接続されている。管理者端末装置１７２は、例えばＣＰＵおよびメモリ等の情報処理資源、ディスプレイ等の出力装置、キーボード等の入力装置を備えるコンピュータ装置である。管理者端末装置１７２は、オペレータによる入力操作等に応じてストレージ装置１００の起動や停止を指示する。また、管理者端末装置１７２は、ストレージ装置１００の動作をモニタし、動作結果や障害発生等のログを記録する。また、管理者端末装置１７２は、ストレージ装置１００におけるバックアップ処理やリストア処理に関するシステム設定を指定する。
【００３２】
ストレージ装置１００は、主に、プロセッサ１０２、メモリ１０４、ディスク１０６及びネットワークインタフェース１０８で構成される。
【００３３】
プロセッサ１０２は、演算処理装置として機能し、メモリ１０４に記憶されているプログラムや演算パラメータ等に従って、ストレージ装置１００の動作を制御する。
【００３４】
メモリ１０４には、オペレーティングシステム１５４と、当該オペレーティングシステム１５４と連携動作する各種プログラム、バックアッププログラム１５０、リストアプログラム１５２、新規チャンク判定フィルタ（不図示）及び各種テーブルが格納されている。
【００３５】
バックアッププログラム１５０は、コンテナ索引表（T）１１０、チャンク索引表１６２、普遍コンテナ索引表１１８、計測表１６０及びライトバッファ１４２を利用し、ネットワーク１７４を通じて提供されたバックアップ対象データをディスク１０６に格納する。
【００３６】
図１に示すように、コンテナ索引表１１０は、メモリ１０４上に複数存在する。以下では、バックアッププログラム１５０が利用するコンテナ索引表１１０をコンテナ索引表（Tf）１１２と呼び、リストアプログラム１５２が利用するコンテナ索引表１１０をコンテナ索引表（TF）１１４と呼ぶ。コンテナ索引表１１０は、コンテナ単位でのチャンクの格納先を管理するテーブルである。コンテナ索引表１１０の構成については、後に詳細に説明する。
【００３７】
普遍コンテナ索引表（Tc）１１８は、バックアップ世代毎に必ず出現する普遍チャンクの格納先を管理するテーブルである。普遍コンテナ索引表（Tc）１１８は、バックアッププログラム１５０と共にメモリ１０４に展開され、そのままメモリ１０４上に保持される。
【００３８】
コンテナ索引表１１２は、各コンテナに対してそれぞれ作成される。バックアッププログラム１５０が重複判定処理を行う際には、少なくとも１つ以上のコンテナ索引表１１２のフィンガプリントを参照する。このため、コンテナ索引表１１２をメモリ１０４上に展開させる必要がある。しかし、メモリ１０４の容量は有限である。このため、全てのコンテナ索引表１１２をメモリ１０４上に展開させることは困難である。そこで、ストレージ装置１００においては、ディスク１０６からメモリ１０４にコンテナ索引表１１２をロールインしたり、メモリ１０４からディスク１０６にコンテナ索引表１１２をロールアウトして、メモリ１０４の資源を有効活用する。
【００３９】
本実施形態において、コンテナ索引表１１２のロールイン／ロールアウトは、ＬＲＵ（Least Recently Used）方式で行われる。ＬＲＵ方式では、メモリ１０４上で最も長い間参照されていないデータをロールアウトする一方、新たに参照するデータをディスク１０６からメモリ１０４にロールインする。この制御動作は、最も長い間参照されていないデータは、次に参照される可能性が一番低いという性質に基づく。ロールイン／ロールアウトの制御は、メモリ１０４とディスク１０６の両方に透過的にアクセスする必要がある。このため、この制御は、オペレーティングシステム１５４またはプロセッサ１０２により提供される。この制御技術は、仮想記憶管理技術（virtual memory management）と呼ばれる。仮想記憶におけるページ置き換え処理は、参照ビット（ｒビット）、更新ビット（ｃビット）及び有効／無効ビット（ｖビット）の３種類のビットを利用して実行される。これらのビットは、コンテンツに含まれるチャンクが到着する毎に更新される。
【００４０】
本実施形態では、このような仮想記憶管理技術を、コンテナ索引表（Tf）１１２を用いて実現する。例えばコンテンツに重複チャンクが含まれる場合、該当チャンクを格納するコンテナの参照ビット（ｒビット）が「１」に設定される。一方、コンテンツに含まれるチャンクをディスク１０６に書き込む場合、該当チャンクを格納するコンテナの更新ビット（ｃビット）が「１」に設定される。また、該当コンテナ索引表１１２がロールインされる場合、ｖビットが「１」に設定される。また、該当コンテナ索引表１１２がロールアウトされる場合、ｖビットが「０」に設定される。
【００４１】
また、ＬＲＵ方式の実装方式の１つとしてaging 方式が挙げられる（例えば非特許文献１を参照）。aging 方式は、参照ビット（ｒビット）を複数備える。aging 方式では、所定の時間間隔毎に、参照ビット（ｒビット）のビット値を右方向にシフトする。特に、参照があった場合、aging 方式は、右シフト後に最上位ビットを「１」に設定する。このようなシフト演算処理により、以下で述べる重み付けを容易に実現することができる。例えば参照時期が過去であるほど重みを軽くし、参照時期が現在に近いほど重みを重くする。例えば、あるデータについて、所定の時間間隔で取得された５回分の参照ビットは、以下のように与えられる。ここで、ビットの「１」は参照があったことを表している。
１回目…１
２回目…０
３回目…１
４回目…０
５回目…０
【００４２】
前述した参照ビットに重みを付けて８ビットのカウンタ値で表現すると、以下のようになる。なお、初期値は００００００００である。
１回目…１０００００００
２回目…０１００００００（右シフト＋「０」付与）
３回目…１０１０００００（右シフト＋「１」付与）
４回目…０１０１００００（右シフト＋「０」付与）
５回目…００１０１０００（右シフト＋「０」付与）
【００４３】
このように、８ビットのカウンタ値によって参照ビット（ｒビット）を表現することにより、過去に参照されたデータほどその値は小さい値で表現され、参照された時期が現在に近いほど大きい値で表現される。
【００４４】
計測表１６０は、コンテナ索引表１１０のロールイン／ロールアウト管理だけでなく、コンテナ単位での重複チャンクの有無や数などの管理にも使用される。ロールイン／ロールアウトを管理するテーブルと、重複チャンクを管理するテーブルは必ずしも１つのテーブルで構成される必要は無く、別々のテーブルで構成されてもよい。前述したように、本実施形態では、ロールイン／ロールアウトを管理するテーブルと重複チャンクを管理するテーブルとを１つのテーブルで構成する。計測表１６０の構成については、後に詳細に説明する。
【００４５】
リストアプログラム１５２は、コンテンツ索引表（S）１６４、コンテナ索引表（TF）１１４及びリードキャッシュ１４４を利用し、ディスク１０６に格納されているバックアップデータを読み出す。
【００４６】
コンテンツ索引表（S）１６４は、コンテンツ単位でチャンクの格納先を管理するテーブルである。コンテンツ索引表１６４の構成内容については、後に詳細に説明する。
【００４７】
ディスク１０６は、ハードディスク装置などから構成され、コンテナ索引表用（T 表用）ＤＢ１２０、チャンク索引表用（U 表用）ＤＢ１８２、コンテンツ索引表用（S 表用）ＤＢ１８４及び複数のコンテナ（コンテナ１３２、１３４、１３６、１３８）が格納されている。コンテナ索引表用ＤＢ１２０には、複数のコンテナ索引表が格納されている（表１２２、１２４、１２６、１２８）。チャンク索引表用ＤＢ１８２には、複数のチャンク索引表が格納されている。コンテンツ索引表用ＤＢ１８４には、複数のコンテンツ索引表が格納されている。
【００４８】
普遍コンテナ索引表１１８は、コンテナ索引表用ＤＢ１２０に格納してもよいし、別の独立した（不図示）ＤＢとして保存してもよい。また、コンテナ１３２、１３４、１３６、１３８には、バックアッププログラム１５０により重複排除処理されたバックアップデータが格納される。この格納時にライトバッファ１４２が使用される。
【００４９】
（１−３）バックアップ処理及びリストア処理の概要
本実施形態に係るバックアップ処理及びリストア処理の理解のために、まず、従来のバックアップ処理及びリストア処理について説明する。
【００５０】
（１−３−１）従来のバックアップ処理及びリストア処理
従来手法を図２を用いて説明する。従来手法で用いるバックアッププログラム１４５０は、コンテンツf1（１４６０）、コンテンツf2（１４７０）及びコンテンツf3（１４８０）を到達順にバックアップする。因みに、コンテンツf1（１４６０）は第１世代のバックアップデータであり、コンテンツf2（１４７０）は第２世代のバックアップデータであり、コンテンツf3（１４８０）は第３世代のバックアップデータである。
【００５１】
図２に示すように、コンテンツf1 は、チャンクａ（１４６２）、普遍チャンクｆ（１４６４）を含む。コンテンツf2 は、チャンクｂ（１４７２）、チャンクｃ（１４７４）、普遍チャンクｆ（１４７６）を含む。コンテンツf3 は、チャンクｂ（１４８２）、チャンクｃ（１４８４）、チャンクｄ（１４８６）、チャンクｅ（１４８８）、普遍チャンクｆ（１４８９）を含む。コンテンツf1〜f3 は、バックアッププログラム１４５０による重複排除処理後に記憶デバイスに格納される。このため、コンテナCf（１４３０）、Cg（１４３２）、Ch（１４３４）には、チャンクａ（１４６２）、普遍チャンクｆ（１４６４）、チャンクｂ（１４７２）、チャンクｃ（１４７６）、チャンクｄ（１４８６）及びチャンクｅ（１４８８）が格納される。
【００５２】
ここで、第１世代のバックアップデータと第２世代のバックアップデータの到着間隔が大きく開いている場合、すなわちコンテンツf1（１４６０）をバックアップしてからコンテンツf2（１４７０）をバックアップするまでの間隔が大きく空いている場合を考える。この場合、バックアッププログラム１４５０は、コンテナCf（１４３０）に、コンテンツf1 のチャンクａ（１４６２）と普遍チャンクｆ（１４６４）を格納する。
【００５３】
ところが、従来手法は、チャンクを到着順にコンテナに格納する。すなわち、チャンクの内容は判断しない。このため、コンテンツf2 のバックアップ時には、既に、コンテナCf が、世代関係のない他のコンテンツのチャンクで一杯になることが起こり得る。この場合、チャンクｂ（１４７２）とチャンクｃ（１４７６）は、チャンクａとは異なるコンテナCg（１４３２）に格納される。同様に、コンテンツf3 のチャンクｄとチャンクｅは、コンテナCf（１４３０）ともコンテナCg（１４３２）とも異なるコンテナCh（１４３４）に格納される。また、これらのコンテナに対応して、コンテナ索引表Tf（１４１０）、Tg（１４１２）、Th（１４１４）が作成される。すなわち、普遍チャンクｆは初期のコンテナCf（１４３０）に格納され、対応するコンテナ索引表はコンテナ索引表Tｆ（１４１０）に格納される。
【００５４】
例えばコンテンツf3（１４８０）をリストアする場合、従来手法では、コンテナCf（１４３０）、コンテナCg（１４３２）、コンテナCh（１４３４）の３つをメモリ上に展開する。
【００５５】
この際、リストアプログラム１４５２は、展開されたコンテナCf（１４３０）から普遍チャンクｆ（１４６４）だけを参照する。すなわち、チャンクａは参照しない。このように、リストアプログラム１４５２は、コンテンツf3（１４８０）のリストアには参照の必要がないチャンクａ（１４６２）もメモリ上に展開する必要がある。
【００５６】
また、データをバックアップする場合も、従来手法では、バックアッププログラム１４５０が、コンテナ索引表Tf（１４１０）等を参照してデータの重複排除処理を実行する。例えばコンテンツf3（１４８０）をバックアップする場合、バックアッププログラム１４５０は、コンテナ索引表Tf（１４１０）とコンテナ索引表Tg（１４１２）をメモリに展開し、コンテンツf3（１４８０）から切り出されるチャンクの管理情報と照合する。ここで、展開されたコンテナ索引表Tf（１４１０）は、普遍チャンクｆの重複排除処理のためだけに参照されればよく、それ以外のチャンク（すなわちｂ、ｃ、ｄ、ｅ）の重複排除処理では参照が不要である。このように、従来手法は、コンテナ及びコンテナ索引表単位でメモリに展開する必要があるため、ほとんど参照されないデータもメモリ上に展開する必要がある。
【００５７】
このように、従来手法では、バックアップ時やリストア時にほとんど参照する必要の無いデータも含めてメモリ上に展開する必要があり、これらほとんど参照する必要の無いデータの存在がバックアップ性能やリストア性能を低下させている。
【００５８】
（１−３−２）実施形態によるバックアップ処理の概要
図３を参照し、本実施形態に係るストレージ装置１００によるバックアップ処理の概要を説明する。図２の場合と同様、バックアッププログラム１５０は、コンテンツf1（２６０）、コンテンツf2（２７０）及びコンテンツf3（２８０）を到着順にバックアップするものとする。因みに、コンテンツf1（２６０）が１番最初に到達し、コンテンツf2（２７０）が２番目に到達し、コンテンツf3（２８０）が３番目に到着するものとする。
【００５９】
図３に示すように、コンテンツf1 は、チャンクａ（２６２）、普遍チャンクｆ（２６４）を含む。コンテンツf2 は、チャンクｂ（２７２）、チャンクｃ（２７４）、普遍チャンクｆ（２７６）を含む。コンテンツf3 は、チャンクｂ（２８２）、チャンクｃ（２８４）、チャンクｄ（２８６）、チャンクｅ（２８８）、普遍チャンクｆ（２８９）を含む。
【００６０】
図３に示すように、本実施形態の場合、バックアッププログラム１５０は、普遍コンテナCc（１３８）と対応する普遍コンテナ索引表Tc（１２８）を用意する。ここで、コンテナ索引表Tc は、常にメモリ104 上に保持させてもよい。また、コンテナCc も常にメモリ１０４上に保持させてもよい。普遍コンテナCc および普遍コンテナ索引表Tc には、普遍チャンクとその管理情報だけが格納される。例えばバックアッププログラム１５０の起動時に、普遍コンテナ索引表Tc（１２８）をメモリ１０４に展開し、同プログラムの終了時に普遍コンテナ索引表Tc（１２８）をディスク１０６に保存する。同様に、普遍コンテナCc（１３８）もバックアッププログラム１５０の起動時にメモリ１０４に展開し、同プログラムの終了時にディスク１０６に保存してもよい。
【００６１】
バックアッププログラム１５０に対するこれらの指示（コマンド等の発行）は、オペレータによる管理者端末装置１７２に対する操作入力を通じて行う。もっとも、バックアッププログラム１５０に対するこれらの指示は、管理者端末装置１７２から指定しない場合も考えられる。この場合、対応する指示は、初期化ファイル等に初期値として予め格納しておき、バックアッププログラム１５０の起動時に当該初期値を読み込んでもよい。
【００６２】
本実施形態の場合、バックアッププログラム１５０は、コンテンツf1 を格納するために、コンテナCf（１３２）を新規に作成し、当該コンテナにチャンクａ（２６４）を格納する。なお、チャンクｆ（２４２）は、普遍コンテナ索引表Tc（１２８）の参照により重複排除される。このため、チャンクｆは、コンテナCf（１３２）には格納されない。その結果、コンテナ索引表Tf（１２２）には、チャンクａの管理情報FPa（２２０）が格納される。なお、普遍コンテナ索引表Tc（１２８）には、普遍チャンクｆの管理情報FPf（２２２）が格納される。
【００６３】
次に、バックアッププログラム１５０は、コンテンツf2（２７０）をバックアップする。この場合、バックアッププログラム１５０は、チャンクｂ（２７２）、チャンクｃ（２７４）及びチャンクｆ（２７６）のうち重複チャンクであるチャンクｆ以外のチャンクｂ及びチャンクｃだけをコンテナCg（１３４）に格納する。勿論、コンテンツf2（２７０）がコンテンツｆ１（２６０）に続いて到達する場合、バックアッププログラム１５０は、コンテナCf（１３２）にチャンクｂ、チャンクｃを格納する可能性もあるが、ここではコンテナCf（１３２）が既に一杯になっているものとする。バックアッププログラム１５０は、コンテナCg（１３４）に対応してコンテナ索引表Tg（１２４）を作成し、チャンクｂとチャンクｃの管理情報FPb（２２４）、FPc（２２６）を格納する。
【００６４】
同様に、コンテンツf3 をバックアップする場合、バックアッププログラム１５０は、チャンクｂ（２８２）、チャンクｃ（２８４）、チャンクｄ（２８６）、チャンクｅ（２８８）、チャンクｆ（２８９）のうち重複チャンクであるチャンクｂ、チャンクｃ、チャンクｆを普遍コンテナ索引表Tc（１２８）とコンテナ索引表Tg（１２４）を用いて検出し、それら以外のチャンクｄ及びチャンクｅをコンテナCh（１３６）に格納する。その後、バックアッププログラム１５０は、コンテナ索引表Th（１２６）に、チャンクｄ及びチャンクｅの管理情報FPd（２２８）、FPe（２２９）をそれぞれ格納する。
【００６５】
このように、本実施形態に係るバックアッププログラム１５０では、コンテンツf3 の重複排除判定に際し、普遍コンテナ索引表Tc（１２８）とコンテナ索引表Tg（１２４）をメモリ１０４上に展開するだけでよい。一方、リストアプログラム１５２は、コンテンツf3(２８０)をリストアする場合、コンテナCg（１３４）、コンテナCh（１３６）及び普遍コンテナCc（１３８）を参照し、コンテンツf3（２８０）を読み出す。
【００６６】
（１−３−３）実施形態で使用する各種索引表の構成
図４Ａを参照して、バックアップ処理時とリストア処理時の両方で使用されるコンテナ索引表T（１１０）の構成例とチャンク索引表U（１６２）の構成例を説明する。コンテナ索引表１１０は、コンテナ単位で作成されるテーブルである。また、チャンク索引表１６２は、コンテナに格納されるチャンクを管理するテーブルである。
【００６７】
図４Ａには、コンテナ索引表１１０のうち一例であるコンテナ索引表Tg（１２４）と普遍コンテナ索引表Tc（１２８）を表している。コンテナ索引表１１０と普遍コンテナ索引表Tc（１２８）の構造は同じであり、フィンガプリント欄３２２、コンテナオフセット欄３２４及びチャンク長欄３２６から構成される。
【００６８】
フィンガプリント欄３２２には、チャンクのフィンガプリントが格納される。コンテナオフセット欄３２４には、コンテナ内におけるチャンクの先頭位置を与えるオフセット値が格納される。チャンク長欄３２６には、チャンクの長さを示す情報が格納される。すなわち、コンテナ索引表１１０の各行には、チャンク毎の管理情報が格納される。図４Ａのコンテナ索引表１１０は、図３に示すコンテンツf2 の到着後の状態に対応する。このため、チャンクｂの管理情報２２４と、チャンクｃの管理情報２２６が格納されている。
【００６９】
複数のコンテナ索引表１１０は、チャンク索引表１６２により管理される。チャンク索引表１６２には、コンテナを識別するコンテナＩＤ３１４と、チャンクのフィンガプリント３１２とが対応づけられている。ここでのコンテナＩＤ３１４は、コンテナ索引表１１０を参照可能とするポインタ情報としても利用される。本実施形態では、コンテナＩＤ（CF）と対応するコンテナ索引表（TF）は、uuid(Universally Unique Identifier)と呼ばれる識別子で共通化されている。
【００７０】
なお、チャンク索引表１６２の参照は、新規チャンクか否かを識別するフィルタ処理の処理結果に応じて判断してもよい。すなわち、チャンク索引表１６２に記録されていないことが確実なチャンクは、チャンク索引表１６２の参照処理自体をスキップし、新規コンテナに直接格納してもよい。この処理手法を採用すれば、チャンク索引表１６２を参照する回数を低減することができる。
【００７１】
例えばディスク１０６に、コンテナと、コンテナ索引表、チャンク索引表とコンテンツ索引表の４つのファイルが存在し、それぞれ４つのディレクトリの下に配置されているものとする。
Container/uuid-Cf…コンテナ本体
ContainerIndexIndex/uuid-Cf…コンテナ索引表データベース（テーブルＴＦを格納するファイル）
ChunkIndex/fp の上位Nbit…チャンク索引表データベース
Contents/uuid-Cf…コンテンツ索引表データベース
【００７２】
例えばコンテナ索引表Tg がメモリ１０４上に展開されていない場合において、コンテンツf3 がバックアップされるとき、バックアッププログラム１５０は、チャンクｂの管理情報FPb を使用してチャンク索引表１６２を検索する。図４Ａの場合、管理情報FPb には、コンテナＩＤのTg（２３０）が対応付けられている。そこで、バックアッププログラム１５０は、コンテナ索引表Tg（１２４）をメモリ１０４上に展開する。チャンクｃの格納情報は、展開されたコンテナ索引表Tg（１２４）を検索することにより、重複判定を行うことができる。
【００７３】
前述の通り、普遍コンテナ索引表Tc（１２８）は、コンテナ索引表１１０と同じ構造を有している。すなわち、普遍コンテナ索引表Tc（１２８）は、フィンガプリント欄３２２、コンテナオフセット欄３２４及びチャンク長欄３２６から構成される。図４Ａでは紙面の都合から既述を省略している。ただし、普遍コンテナ索引表Tc（１２８）は、バックアッププログラム１５０の起動時に、メモリ１０４に展開され保持されている。このため、例えば普遍チャンクｆが格納される普遍コンテナ索引Tc（１２８）の情報は、チャンク索引表１６２に登録してもよいし、登録してなくてもよい。なぜなら、本実施形態の場合、後述するように、チャンク索引表１６２の検索前には必ず普遍コンテナ索引表Tc（１２８）が検索されるため、普遍チャンクｆがどのコンテナ索引表に登録されているかを検出する目的で、チャンク索引表１６２を参照する必要はないからである。
【００７４】
次に、図４Ｂを参照して、リストア時に使用するコンテンツ索引表S（１６４）の構成例を説明する。コンテンツ索引表１６４は、コンテンツ単位で作成されるテーブルであって、コンテンツに含まれるチャンクを管理するテーブルである。コンテンツ索引表１６４は、コンテンツＩＤ欄３６１、フィンガプリント欄３６２、コンテナＩＤ欄３６４、コンテンツオフセット欄３６６及びチャンク長欄３６８から構成される。
【００７５】
コンテンツＩＤ欄３６１には、コンテンツを識別する情報が格納される。フィンガプリント欄３６２には、チャンクのフィンガプリントが格納される。コンテナＩＤ欄３６４には、チャンクが格納されているコンテナの識別情報が格納される。コンテンツオフセット欄３６６には、コンテンツ内のチャンクの位置を示す情報が格納される。チャンク長欄３６８には、チャンクの長さを示す情報が格納される。
【００７６】
例えば図４Ｂでは、コンテンツ索引表１６４の例として、Sf1（２０２）、Sf2（２０４）、Sf3（２００）、Sfn（３６０）を描いている。このうち、Sf3（２００）には、図３に示すコンテンツf3 の情報が格納されている。Sf3（２００）の情報により、コンテンツf3 は、チャンクｂと、チャンクｃ、チャンクｄ、チャンクｅ及びチャンクｆにより再構成できること、各チャンクはどのコンテナのどの領域（オフセットとチャンク長）に格納されているかが分かる。
【００７７】
コンテンツ索引表１６４を構成するコンテンツのオフセット（３６６）とチャンク長（３６８）は、コンテンツ内のチャンクの論理的な配置を示している。なお、前述したコンテナ索引表１１０（図４Ａ）におけるチャンクのオフセット（３２４）とチャンク長（３２６）は、ディスク１０６内のチャンクの物理的な配置を示している。
【００７８】
リストア処理時、リストアプログラム１５２は、コンテンツ索引表１６４を参照し、各チャンクのコンテナＩＤを取得して、当該コンテナＩＤからコンテナ索引表１１０を検索する。次に、リストアプログラム１５２は、コンテナ索引表１１０に格納されている情報に基づいて各チャンクの物理的な格納位置を取得し、該当チャンクをディスク１０６から読み込む。この後、リストアプログラム１５２は、コンテンツ索引表１６４の論理的な配
置に従ってコンテンツを再構成する。
【００７９】
（１−３−４）実施形態によるバックアップ処理動作の詳細
図５に、バックアッププログラム１５０により実行されるバックアップ処理動作の詳細を示す。まず、バックアッププログラム１５０は、バックアップ対象のコンテンツをチャンクsi（ｉ＝１、２、…、ｎ）に分解する（ステップＳ１０１）。
【００８０】
次に、バックアッププログラム１５０は、チャンクsi の管理情報msi（ｉ＝１、２、…、ｎ）を作成する（ステップＳ１０２）。チャンクの管理情報msi には、チャンクのフィンガプリント、チャンクのコンテンツ内の位置（オフセット）、チャンクの長さが含まれる。
【００８１】
続いて、バックアッププログラム１５０は、ループ処理に用いられるカウンタｉを初期化（ｉ＝０）し、以下で説明するチャンクsi の重複判定を開始する（ステップＳ１０３）。
【００８２】
バックアッププログラム１５０は、メモリ１０４上に展開された普遍コンテナ索引表Tc（１１８）を検索し、重複判定を行う（ステップＳ１１０）。具体的には、バックアッププログラム１５０は、ステップＳ１０１において分解したチャンクのフィンガプリントと一致するフィンガプリントが普遍コンテナ索引表Tc（１２８）に含まれるか否かを判定する。バックアッププログラム１５０は、チャンクのフィンガプリントが普遍コンテナ索引表Tc（１２８）のフィンガプリントと一致する場合に「重複あり」と判定し、一致しない場合に「重複なし」と判定する。因みに、普遍コンテナ索引表Tc（１２８）は、バックアッププログラム１５０のプログラム起動時にメモリ１０４に読み込まれて常駐し、バックアッププログラム１５０の終了時にディスク１０６に書き出される。
【００８３】
ステップＳ１１０においてフィンガプリントが一致するチャンクsi が見つかった場合（重複チャンクであると判定された場合）、バックアッププログラム１５０は、ステップＳ１４０の処理を実行する。一方、ステップＳ１１０においてフィンガプリントが一致するチャンクsi が見つからなかった場合（重複チャンクではないと判定された場合）、バックアッププログラム１５０は、ステップＳ１１２の処理を実行する。
【００８４】
ステップＳ１１２において、バックアッププログラム１５０は、メモリ１０４上にあるコンテナ索引表Tf（１１２）を検索し、重複判定を行う。ステップＳ１１２においてフィンガプリントが一致するチャンクsi が見つかった場合（重複チャンクであると判定された場合）、バックアッププログラム１５０は、ステップＳ１４０の処理を実行する。一方、ステップＳ１１２においてフィンガプリントが一致するチャンクsi が見つからなかった場合（重複チャンクではないと判定された場合）、バックアッププログラム１５０は、ステップＳ１２０の処理を実行する。
【００８５】
ステップＳ１２０において、バックアッププログラム１５０は、フィルタを用いて重複チャンクか否かを判定する。ステップＳ１２０においてチャンクsi が新規チャンクであると判定された場合、バックアッププログラム１５０は、ステップＳ１３０の処理を実行する。一方、ステップＳ１２０においてチャンクsi が重複チャンクの可能性が高いと判定された場合、バックアッププログラム１５０は、ステップＳ１２２の処理を実行する。
【００８６】
ステップＳ１２２において、バックアッププログラム１５０は、チャンク索引表U（１６２）を検索し、チャンクsi が重複チャンクか否かを判定する。ステップＳ１２２においてチャンクsi が見つからなかった場合、バックアッププログラム１５０は、ステップＳ１３０の処理を実行する。一方、ステップ１２２においてチャンクsi が見つかった場合、バックアッププログラム１５０は、チャンクsi が格納されているコンテナＩＤを取得し、ステップＳ１１４の処理を実行する。
【００８７】
ステップＳ１１４において、バックアッププログラム１５０は、メモリ上の上限コンテナ索引数までコンテナ索引表Tf（１１２）をメモリ１０４上に展開しているか否か判定する。ステップＳ１１４で上限まで使用されていると判定された場合、バックアッププログラム１５０は、メモリ上に展開されているコンテナ索引表Tf（１１２）のうち最も参照されていないコンテナをロールアウトし(ステップＳ１１６)、ステップＳ１１８の処理を実行する。一方、ステップＳ１１４で上限まで使用していないと判定された場合、バックアッププログラム１５０は、ステップＳ１１８の処理を実行する。
【００８８】
因みに、バックアッププログラム１５０が参照する「メモリ上の上限コンテナ索引表数」は、オペレータによる管理者端末装置１７２に対する操作入力を介して発生されるコマンド等を通じて指定されている。また、「メモリ上の上限コンテナ索引表数」を管理者端末装置１７２を通じて指定しない場合、これらの値は、初期値として初期化ファイル等に予め格納しておいてもよい。この初期値は、バックアッププログラム１５０がその起動時に読み込む。
【００８９】
ステップ１１８において、バックアッププログラム１５０は、チャンクsi が格納されているコンテナ索引表Tf（１１２）をメモリ１０４上に展開する。ステップＳ１１８の実行後、バックアッププログラム１５０は、ステップＳ１１２に戻る。
【００９０】
前述したように、本実施形態の場合、バックアッププログラム１５０は、チャンク索引表U（１６２）とコンテナ索引表T（１１０）を併用して重複判定処理を実行する。メモリ１０４は有限であるため、全てのコンテナ索引表１１０をメモリ１０４に展開することはできない。そのため、コンテナ索引表１１０とチャンク索引表１６２の２段階で重複判定を実行し、コンテナ索引表に関連性の高いチャンクを集約させることにより、重複判定に必要なコンテナ索引表のエントリ数を減らし、メモリ１０４の記憶容量を逼迫させずに、かつ、ディスク１０６との入出力回数を減らすことができる。
【００９１】
前述のステップＳ１２０で新規チャンクと判定された場合、又は、ステップＳ１２２で検索対象のチャンクがチャンク索引表に見つからなかった場合、バックアッププログラム１５０は、コンテナ領域がＦＵＬＬか否かを判定する（ステップＳ１３０）。ステップＳ１３０においてＦＵＬＬと判定された場合、バックアッププログラム１５０は、新規コンテナとそのコンテナ索引表を作成し（ステップＳ１３２）、ステップＳ１３４を実行する。一方、ステップＳ１３０においてＦＵＬＬでないと判定された場合、バックアッププログラムは、ステップＳ１３４を実行する。
【００９２】
ステップＳ１３４において、バックアッププログラム１５０は、コンテナにチャンクsiを書き出し、コンテナ索引表にチャンクsi の管理情報msi を書き出し、チャンク索引表にチャンクsi のメッセージダイジェストを書き出す。因みに、ステップＳ１３４の処理は、ステップＳ１３０の処理において、ライトバッファ１４２に書き出したコンテナがＦＵＬＬだった場合には、コンテナ、コンテナ索引表、チャンク索引表を書き出し、一方、ＦＵＬＬでなかった場合には、ライトバッファ１４２上のコンテナ、コンテナ索引表、チャンク索引表に書き出すという処理を採用してもよい。この処理の採用により、ディスク１０６との間の入出力回数を減らすことができ、バックアップ性能を向上させることができる。
【００９３】
ステップＳ１３４の実行後、バックアッププログラム１５０は、ステップＳ１４０を実行する。ステップＳ１４０において、バックアッププログラム１５０は、リストア用にコンテンツ索引表S（１６４）を書き出す。
【００９４】
この後、バックアッププログラム１５０は、全てのチャンクについて、重複判定処理及び書き出し処理が終わったか否かを判定する（ステップＳ１０４）。具体的には、バックアッププログラム１５０は、コンテンツに含まれるチャンク数ｎと、カウンタｉのカウンタ数とを比較する。
【００９５】
ステップＳ１０４において、全てのチャンクに対して重複判定処理及び書き出し処理が終わったと判定された場合、バックアッププログラム１５０は、当該コンテンツのバックアップ処理を終了する。一方、ステップＳ１０４において、全てのチャンクに対して重複判定処理及び書き出し処理が終わっていないと判定された場合、バックアッププログラム１５０は、カウンタｉに１を加算し、ステップＳ１０４に戻る（ステップＳ１０５）。
【００９６】
（１−３−５）実施形態によるリストア処理動作の詳細
図６に、リストアプログラム１５２により実行されるリストア処理動作の詳細を示す。まず、リストアプログラム１５２は、コンテンツ索引表S（１６４）を参照し、読み込み対象であるコンテンツに含まれるチャンクsi（si＝１、２、…、ｎ）の情報を取得する（ステップＳ２０１）。具体的には、リストアプログラム１５２は、コンテンツ索引表１６４から、読み込む必要のあるチャンクsi のリストを作成する。
【００９７】
次に、リストアプログラム１５２は、カウンタｉに０を設定する（ステップＳ２０２）。その後、リストアプログラム１５２は、コンテナ索引表TF（１１４）の管理情報msi を読み込む（ステップＳ２０３）。具体的には、リストアプログラム１５２は、ステップＳ２０１において取得したコンテンツ索引表１６４のチャンクsi の情報から、当該チャンクsi が属するコンテナ索引表１１４をディスク１０６から読み込み、該当チャンクの管理情報を読み込む。チャンクの管理情報とは、前述したように、チャンクのフィンガプリント、コンテナ内における位置、チャンクの長さの情報などである。
【００９８】
次に、リストアプログラム１５２は、ステップＳ２０３で読み込んだチャンクの管理情報msi に基づいて、コンテナ索引表１１４に対応するコンテナ１３２等に格納されているチャンクsi を読み込む（ステップＳ２０４）。
【００９９】
続いて、リストアプログラム１５２は、リストア対象のコンテンツに含まれる全てのチャンクについて読み込みが終了したか否かを判定する（ステップＳ２０５）。具体的には、リストアプログラム１５２は、コンテンツに含まれるチャンク数ｎと、カウンタｉのカウンタ数とを比較する。
【０１００】
ステップＳ２０５において、全てのチャンクについて読み込みが終了したと判定された場合、リストアプログラム１５２は、読み込んだチャンクsi（ｉ＝１、２、…、ｎ）に基づいてコンテンツを再合成し、リストア処理を終了する（ステップＳ２０７）。具体的には、リストアプログラム１５２は、コンテンツ索引表１６４に既述されたコンテンツ内のオフセット情報やチャンク長情報に基づいて、読み込んだチャンクsi をコンテンツに再合成する。一方、ステップＳ２０５において、全てのチャンクについて読み込みが終了していないと判定された場合、リストアプログラム１５２は、カウンタｉに１を加算し、ステップＳ２０３に戻る（ステップＳ２０６）。
【０１０１】
（１−４）普遍コンテナの構成
（１−４−１）普遍チャンクの定義
続いて、本実施形態に係る普遍コンテナCc（１３８）の構成方法について説明する。普遍コンテナ１３８は、普遍チャンクの集合として構成される。普遍チャンクは、コンテンツタイプ毎に必ず出現するチャンクであり、必ずしも普遍チャンクのアクセスが多いわけではない。従って、コンテンツ毎に１回しかアクセスされなくても、必ずアクセスされるチャンクは普遍チャンクである。
【０１０２】
（１−４−２）普遍チャンクの特定処理の概念
バックアッププログラム１５０は、計測表R（１６０）を使用して普遍チャンクを特定する。図７に、計測表１６０の具体的な構成を示す。計測表１６０は、メッセージダイジェスト３００と、参照（reference）ビット３０２と、ni ビット３１０で構成される。メッセージダイジェスト３００は、処理対象の特定に使用される。参照ビット３０２は、初期化時に「０」に更新され、登録されたメッセージダイジェスト３００に参照があった場合に「１」に更新される。ni ビット３１０は、初期登録かどうかを示す。ni ビット３１０は、「０」に初期化され、初期登録でなくなった場合に「１」に更新される。
【０１０３】
以下では、コンテンツf1（２６０）、コンテンツf2（２７０）、コンテンツf3（２８０）がバックアップされる場合について説明する。図７（１）に示す計測表１６０は、バックアッププログラム１５０がコンテンツf1（２６０）をバックアップした後の計測表１６０の状態を示す。前述したように、コンテンツf1 は、チャンクａおよびチャンクｆで構成される。ここでは、チャンクのFP（Finger Print）値をメッセージダイジェスト３００に登録している。なお、ni ビット３１０が「０」であるため、コンテンツf1 を構成する全てのチャンクが計測表１６０に登録される。バックアッププログラム１５０は、コンテンツf1 のバックアップが終了した時点で、ni ビットを「１」に更新する。
【０１０４】
次に、バックアッププログラム１５０は、コンテンツf2（２７０）をバックアップする。この際、ni ビットに「１」が設定されている。このため、バックアッププログラム１５０は、コンテンツf2 に重複チャンクがある場合、重複チャンクに対応する参照ビット３０２を「１」に更新する。図７(２)に示す計測表１６０は、コンテンツf2 のバックアップを行った時点における計測表１６０の状態である。ここでのコンテンツf2 は、チャンクｂ、チャンクｃ及びチャンクｆで構成される。このため、チャンクｆに対応するＦＰ値FPf の参照ビットのみが「１」に更新される。
【０１０５】
続いて、バックアッププログラム１５０は、コンテンツf2 のバックアップが終了した時点において参照ビット３０２が「０」であるメッセージダイジェストを削除する。そして、計測表１６０に残っている登録がある場合には、その参照ビットを「０」で更新する。
【０１０６】
バックアッププログラム１５０は、同様の処理をコンテンツf3 に繰り返し適用する。図７（３）に示す計測表１６０は、コンテンツf3 のバックアップ処理後の計測表１６０の状態を表している。このとき、計測表１６０に登録されているデータは、チャンクｆである。この際、バックアッププログラム１５０は、チャンクｆが普遍チャンクであると判定する。
【０１０７】
（１−４−３）普遍チャンク特定処理の詳細
図８に、バックアッププログラム１５０により実行される普遍チャンク特定処理の詳細を示す。なお、本実施形態の場合、普遍チャンク特定処理は、本来のバックアップ処理（ストレージ装置の運用開始）に先立って実行される。
【０１０８】
まず、バックアッププログラム１５０は、計測するコンテンツ数をｍにセットし（ステップＳ３０１）、変数ｊを０に初期化する（ステップＳ３０２）。
【０１０９】
続いて、バックアッププログラム１５０は、図５のステップＳ１０１、Ｓ１０２、Ｓ１０３と同様の処理を実行し、コンテンツfj を構成するチャンクsi の管理情報msi を作成する。その後、バックアッププログラム１５０は、計測表１６０（図７）のni ビット３１０を参照し、２個以上のコンテンツの計測か否かを判定する（ステップＳ３１０）。
【０１１０】
最初のコンテンツの計測であると判定された場合（ステップＳ３１０で否定結果の場合）、バックアッププログラム１５０は、ステップＳ３１４の処理を実行する。ステップＳ３１４において、バックアッププログラム１５０は、チャンクsi のFP 値FPsi を計測表１６０に登録する。この後、バックアッププログラム１５０は、ステップＳ１０４の処理を実行する。
【０１１１】
一方、ステップＳ３１０において、２個以上のコンテンツの計測であると判定された場合、バックアッププログラム１５０は、ステップＳ３１２の処理を実行する。ステップＳ３１２において、バックアッププログラム１５０は、チャンクsi のFP 値FPsi が計測表１６０に既に登録済みか否かを判定する。FP 値FPsi が既登録だった場合、バックアッププログラム１５０は、ステップＳ３１６を実行する。一方、FP 値FPsi が既登録でなかった場合、バックアッププログラム１５０は、ステップＳ１０４の処理を実行する。ステップＳ３１６において、バックアッププログラム１５０は、FP 値FPsi の参照ビット３０２を「１」に更新する。この後、バックアッププログラム１５０は、ステップＳ１０４の処理を実行する。
【０１１２】
ステップＳ１０４において、バックアッププログラム１５０は、コンテンツfj の全てのチャンクについて処理が終了したか否かを判定する（ステップＳ１０４）。具体的には、バックアッププログラム１５０は、変数ｉとチャンク数ｎを比較する。変数ｉがチャンク数ｎより小さい場合、バックアッププログラム１５０は、変数ｉに１を加え、ステップＳ３１０に戻る（ステップＳ１０５）。一方、ｉがｎ以上の場合、バックアッププログラム１５０は、ステップＳ３２０の処理を実行する。
【０１１３】
ステップＳ３２０において、バックアッププログラム１５０は、計測表１６０（図７）のni ビット３１０を参照し、２個以上のコンテンツの計測か否かを判定する。２個以上のコンテンツの計測であると判定した場合、バックアッププログラム１５０はステップＳ３２２の処理を実行する。一方、最初のコンテンツの計測であると判定した場合は、バックアッププログラム１５０は、ステップＳ３０４の処理を実行する。
【０１１４】
ステップＳ３２２において、バックアッププログラム１５０は、参照ビット３０２が「０」であるメッセージダイジェスト３００を計測表１６０から削除する。この処理により、コンテンツfj の計測において参照のなかったチャンク情報が計測表１６０から削除される。この後、バックアッププログラム１５０は、計測表１６０に残ったデータの参照ビットを全て「０」に設定し、次の計測に備える（ステップＳ３２４）。
【０１１５】
この後、バックアッププログラム１５０は、変数ｊと計測コンテンツ数ｍを比較する（ステップＳ３０４）。変数ｊが計測コンテンツ数ｍより小さい場合、バックアッププログラム１５０は、変数ｊに１を加え、ステップＳ１０１に戻る（ステップＳ３０５）。一方、変数ｊがｍ以上であった場合、バックアッププログラム１５０は、処理を終了する。
【０１１６】
ところで、図７及び図８の場合、バックアッププログラム１５０は、チャンクsi のFP（finger print）値を用いて、普遍チャンクの特定処理を実行している。しかし、普遍チャンクの特定には、FP（finger print）値に代えて、ローリングハッシュ方式により導出されたハッシュ値を使用してもよい。例えば非特許文献２及び非特許文献３に記されているように、ローリングハッシュ方式は、決められたウィンドウ幅に収められたデータ列のハッシュ値を高速に計算する方式である。具体的には、あるウィンドウ幅のハッシュ値を計算すると、ウィンドウをずらし、そのウィンドウ内のデータ列のハッシュ値を、ずらす前のハッシュ値を用いて計算する。
【０１１７】
（１−４−４）普遍コンテナ及び普遍コンテナ索引表の作成処理の詳細
前述した普遍チャンク特定処理は、コンテンツのバックアップ開始前に、バックアッププログラム１５０を利用して実行される。また、バックアッププログラム１５０は、計測表１６０のメッセージダイジェスト３００を利用し、普遍コンテナCc（１３８）と普遍コンテナ索引表Tc（１２８）を作成する。なお、普遍コンテナ１３８と普遍コンテナ索引表１２８は、普遍チャンク特定処理に伴って作成されたコンテナとコンテナ索引表を参照して作成される。普遍コンテナ１３８と普遍コンテナ索引表１２８の作成後、普遍チャンク特定処理に伴って作成されたチャンク索引表、コンテナ、コンテナ索引表はいずれも削除される。
【０１１８】
この普遍チャンクの特定処理は、オペレータによる管理者端末装置１７２に対する操作入力を介して発生されるコマンド等を通じて指定されている。これらの指定に管理者端末装置１７２からのコマンド等を使用しない場合、指示内容を初期化ファイル等に初期値として予め格納し、バックアッププログラム１５０の起動時に読み込んで使用してもよい。
【０１１９】
普遍コンテナ索引表１２８は、バックアッププログラム１５０の起動時に、メモリ１０４に展開され保持される。また、普遍コンテナ１３８も、バックアッププログラム１５０の起動時に、メモリ１０４に展開され保持されてもよい。プログラムの終了時、バックアッププログラム１５０は、メモリ上に展開した普遍コンテナ索引表１２８を終了する。もし、普遍コンテナ１３８もメモリ上に展開していた場合には、バックアッププログラム１５０は、プログラムの終了時に普遍コンテナ１３８も終了する。
【０１２０】
（１−５）本実施形態の効果
以上説明したように、本実施形態に係るストレージ装置１００は、普遍チャンクを集約的に管理する普遍コンテナ１３８と普遍コンテナ索引表１２８を用意する。普遍チャンク用のコンテナとその索引表を用意することにより、従来方式のように、普遍チャンクの属するコンテナに普遍チャンク以外のチャンクが混在したまま管理されることはない。このため、バックアップ処理時には、普遍チャンクに関する管理情報だけを集約した普遍コンテナ索引表１２８をメモリ１０４上に展開し、格納するチャンクが普遍チャンクか否かの判定に使用することができる。
【０１２１】
一方、従来方式の場合には、ほとんど参照されることが無い普遍チャンク以外のチャンクも一緒に管理するコンテナ索引表をメモリ上に展開する必要がある。このため、ほとんど参照されることのない情報がメモリ上に何度も展開されてしまう。
【０１２２】
本実施形態に係るストレージ装置１００は、コンテンツから切り出したチャンクが重複チャンクか否かを検出する際に、アクセス頻度は低くとも必ず参照される普遍チャンクだけを含む普遍コンテナ索引表をメモリ１０４上に展開するため、メモリ１０４の効率的な利用を実現できる。
【０１２３】
また、リストアに際しても、普遍チャンクは普遍コンテナに集約的に格納されているため、普遍チャンクをディスク１０６からメモリ１０４に読み出す際の入出力回数を従来方式に比して削減し、メモリ１０４の効率的な利用を実現することができる。
【０１２４】
以上の結果、ストレージ装置１００のバックアップ性能及びリストア性能を、従来方式
に比して向上させることができる。
【０１２５】
（２）第２の実施形態
（２−１）ストレージ装置に搭載する重複排除機能の概要
まず、本実施形態に係る重複排除機能の概要について説明する。第１の実施形態では、バックアッププログラム１５０を利用して、コンテンツのバックアップ開始前に普遍コンテナCc（１３８）を作成し、ストレージ装置１００によるバックアップ処理の運用開始後は、普遍チャンクの特定処理を実行しない場合について説明した。
【０１２６】
しかし、本実施形態に係るストレージ装置の場合には、運用開始後も普遍チャンクの特定処理を実行し、特定した普遍チャンクを普遍コンテナに追加登録できるようにする。
【０１２７】
本実施形態に係るバックアッププログラム１５０は、バックアップ対象のコンテンツが到着した時点で、図８と同様の普遍チャンク特定処理を開始する。バックアッププログラム１５０による特定処理の終了は、世代毎のバックアップが完了した時であり、計測表１６０で特定した普遍チャンクを普遍コンテナCc（１３８）に登録する。続いて、バックアッププログラム１５０は、普遍コンテナ１３８をディスク１０６に書き出し、普遍コンテナに追加登録された普遍チャンクのデータが、次回のバックアップ処理に反映されるように処理する。
【０１２８】
図９に、本実施形態による普遍コンテナおよびその索引表の登録イメージを示す。図９に示すように、運用開始前に特定された普遍チャンクおよびその管理情報の組５０２と、運用開始後に特定された普遍チャンクとその管理情報の組５０４は、同じ普遍コンテナ索引表１２８および普遍コンテナ１３８に格納される。
【０１２９】
（２−２）ストレージ装置の構成
本実施形態に係るストレージ装置１００の機能構成は、バックアッププログラム１５０に設ける追加機能を除き、第１の実施形態と同様である。従って、詳細な説明は省略する。
【０１３０】
（２−３）バックアップ処理及びリストア処理
本実施形態に係るバックアップ処理及びリストア処理は、第１の実施の形態とほぼ同様である。従って、詳細な説明は省略する。
【０１３１】
（２−４）普遍コンテナの構成
本実施形態に係るバックアップ処理開始前の普遍コンテナの構成は、第１の実施形態と
同様である。従って、詳細な説明は省略する。
【０１３２】
（２−５）バックアップ処理中における普遍チャンクの登録および削除
ここでは、バックアップ処理の開始後に普遍チャンクが特定された場合に、特定された
普遍チャンクを普遍コンテナに追加登録するための処理手順を説明する。
【０１３３】
本実施形態の場合、バックアッププログラム１５０は、バックアップ処理の開始と同時に、普遍チャンク特定処理を開始する。バックアッププログラム１５０は、処理対象とするコンテンツのバックアップが完了し、新たなバックアップ世代が作成されると、計測表１６０に登録されたデータに基づいてコンテナ索引表T（１１０）を検索し、その検索結果である管理情報を普遍コンテナ索引表Tc（１１８）に追加登録する。すなわち、バックアッププログラム１５０は、特定した普遍チャンクの管理情報のコピーを、普遍コンテナCc（１３８）に登録する。
【０１３４】
リストア性能の向上を期待する場合には、チャンクデータそのものを普遍コンテナ１３８に追加し、コピーを作成してもよい。しかし、この手法では、チャンクデータの重複が生じてしまう。また、追加登録するチャンクデータそのものは、普遍コンテナ以外のコンテナに既に登録されているため、必ずしも普遍コンテナ１３８へ登録する必要はない。
【０１３５】
例えばバックアッププログラム１５０は、以下の処理動作を実行する。バックアッププログラム１５０は、新規バックアップの開始後にあってバックアップ世代を進める際、計測表１６０のコピーをとり、新規の普遍チャンク特定処理を開始する。普遍チャンク特定処理の完了後、バックアッププログラム１５０は、コピーをとっておいた１世代前の計測表１６０と比較し、１世代前の計測表１６０にはあるが、現在の計測表１６０にはない普遍チャンク情報を、普遍コンテナ索引表１１８から削除する。もし、普遍コンテナ１３８にもチャンクデータが登録されていた場合、バックアッププログラム１５０は、同様にチャンクデータを削除する。
【０１３６】
（２−６）本実施形態の効果
以上のように、本実施形態では、普遍チャンク特定処理をバックアップの運用開始後も適用し、バックアップ世代が進む度に新規な普遍チャンクの特定を可能にする。また、本実施形態では、使用されなくなった普遍チャンクを削除し、普遍コンテナ及び普遍コンテナ索引表が無限に増加することを回避する。これにより、バックアップ世代の変化に対応した普遍コンテナ及び普遍コンテナ索引表の運用が可能になる。
【０１３７】
（３）第３の実施形態
（３−１）ストレージ装置に搭載する重複排除機能の概要
まず、本実施形態に係る重複排除機能の概要を説明する。第２の実施形態に係るストレージ装置は、バックアッププログラム１５０が、運用開始前に普遍コンテナ１３８を作成するだけでなく、運用開始後も普遍チャンク特定処理を実行する。そして、第２の実施形態に係るバックアッププログラム１５０は、新たに特定された普遍チャンクを普遍コンテナに追加登録する一方、使用しない普遍チャンクを普遍コンテナから削除する。このように、第２の実施形態の場合、予め作成され登録されていた普遍チャンクが、普遍コンテナから事後的に削除される可能性がある。ところが、データベースは、通常、レコードの登録と削除を繰り返すことでフラグメンテーションが発生し、レコードの検索性能も登録性能も劣化する。
【０１３８】
そこで、本実施形態に係るストレージ装置では、予め作成した普遍コンテナ索引表（以下「静的普遍コンテナ索引表」という）と、運用開始後に新たに特定された普遍チャンクが登録される普遍コンテナ索引表（以下「動的普遍コンテナ索引表」という）とを別の表として管理する手法を採用する。なお、本実施形態に係るストレージ装置は、運用開始後は、静的普遍コンテナ索引表を読み込み処理だけに制限し、フラグメンテーションによる性能劣化部位を動的普遍コンテナ索引表のみに制限する。
【０１３９】
本実施形態において、バックアッププログラム１５０は、プログラムの起動時に、静的普遍コンテナ索引表および動的普遍コンテナ索引表をメモリ１０４上に展開し、バックアップ対象のコンテンツが到着したときに、普遍チャンク特定処理を開始する。
【０１４０】
バックアッププログラム１５０による普遍チャンク特定処理の終了は、世代毎のバックアップが完了した時であり、計測表１６０で新たに特定された普遍チャンクを動的普遍コンテナに登録する。続いて、バックアッププログラム１５０は、動的普遍コンテナをディスク１０６へ書き出し、動的普遍コンテナに追加登録された普遍チャンクのデータが、次回のバックアップ処理に反映されるように処理する。
【０１４１】
図１０に、本実施形態による普遍コンテナおよびその索引表の登録イメージを示す。図１０に示すように、運用開始前に特定された普遍チャンクおよびその管理情報の組５０２は、静的普遍コンテナ索引表５１２と静的普遍コンテナ５２２に格納され、運用開始後に特定された普遍チャンクとその管理情報の組５０４は、動的普遍コンテナ索引表５１４と動的普遍コンテナ５２４に格納される。
【０１４２】
（３−２）ストレージ装置の構成
本実施形態に係るストレージ装置１００の機能構成は、バックアッププログラム１５０に設ける追加機能を除き、第１の実施形態とほぼ同様である。従って、詳細な説明は省略する。
【０１４３】
（３−３）バックアップ処理およびリストア処理
本実施形態に係るバックアップ処理及びリストア処理は、第１の実施の形態とほぼ同様である。従って、詳細な説明は省略する。
【０１４４】
（３−４）普遍コンテナの構成
本実施形態の場合も、バックアップ処理開始前の普遍コンテナの構成は、第２の実施形態と同様である。従って、バックアップ処理開始前の普遍コンテナの構成についての詳細な説明は省略する。
【０１４５】
（３−５）バックアップ処理中における普遍チャンクの登録および削除
ここでは、バックアップ処理開始後に普遍チャンクが新たに特定された場合に、特定された普遍チャンクを普遍コンテナに追加登録するための処理手順について説明する。
【０１４６】
本実施形態の場合、バックアッププログラム１５０は、バックアップ処理の開始と同時に、普遍チャンク特定処理を開始する。バックアッププログラム１５０は、処理対象とするコンテンツのバックアップが完了し、新たなバックアップ世代が作成されると、計測表１６０に登録されたデータに基づいてコンテナ索引表を検索し、その検索結果である管理情報を動的普遍コンテナ索引表５１４に追加登録する。すなわち、バックアッププログラム１５０は、特定した普遍チャンクの管理情報のコピーを、動的普遍コンテナ索引表５１４に登録する。リストア性能の向上を期待する場合には、チャンクデータそのものを動的普遍コンテナ５２４に追加し、コピーを作成してもよい。しかし、この手法では、チャンクデータの重複が生じてしまう。また、追加登録するチャンクデータそのものは、普遍コンテナ以外のコンテナに既に登録されているため、必ずしも動的普遍コンテナ５２４に登録する必要はない。
【０１４７】
例えばバックアッププログラム１５０は、以下の処理動作を実行する。バックアッププログラム１５０は、新規バックアップの開始後にあってバックアップ世代を進める際、計測表１６０のコピーをとり、新規の普遍チャンク特定処理を開始する。普遍チャンク特定処理の完了後、バックアッププログラム１５０は、コピーをとっておいた１世代前の計測表１６０と比較し、１世代前の計測表１６０にはあるが、現在の計測表１６０にはない動的普遍チャンク情報を、動的普遍コンテナ索引表５１４から削除する。もし、動的普遍コンテナにもチャンクデータが登録されていた場合、バックアッププログラム１５０は、同様にチャンクデータを削除する。
【０１４８】
更に、削除により全てのデータがなくなった場合、バックアッププログラム１５０は、動的普遍コンテナ索引表５１４の初期化を実行する。初期化とは、データベースに付随する初期化機能を利用してもよいし、既存の動的普遍コンテナ索引表５１４を削除して、新規に動的普遍コンテナ索引表５１４を作成してもよい。これらの処理により、データベース内部で起きたフラグメンテーションによる性能劣化を回避することができる。
【０１４９】
（３−６）本実施形態の効果
以上のように、本実施形態では、普遍チャンク特定処理をバックアップの運用開始後も適用し、バックアップ世代が進む度に新規に特定される普遍チャンクを動的普遍コンテナ５２４に登録し、使用されなくなった普遍チャンクを動的普遍コンテナ索引表５１４から削除する。これにより、静的普遍コンテナ５２２内の登録データが削除されることを回避することができ、データベースのフラグメンテーションによる性能劣化を回避することができる。
【０１５０】
（４）第４の実施形態
（４−１）ストレージ装置に搭載する重複排除機能の概要
まず、本実施形態に係る重複排除機能の概要を説明する。前述した第１、第２及び第３の実施形態では、バックアッププログラム１５０が、バックアップ世代毎に普遍チャンクを特定していた。通常、普遍チャンクは、ファイルフォーマットに依存し、コンテンツタイプ毎に存在する。
【０１５１】
バックアップするコンテンツに複数のコンテンツタイプが含まれる場合、バックアップ世代毎に普遍チャンクの特定処理を実行しても、コンテンツタイプ毎の普遍チャンクを特定することはできず、複数のコンテンツタイプに共通する普遍チャンクのみが特定される。すなわち、コンテンツタイプ毎の普遍チャンクは、他のチャンクと同様、通常のコンテナに登録される。
【０１５２】
例えば、あるバックアップ世代では、コンテンツタイプＡのコンテンツがバックアップされたものの、後続する１又は複数のバックアップ世代では、コンテンツタイプＡのコンテンツのバックアップが実行されず、それ以後のバックアップ世代で、コンテンツタイプＡのコンテンツのバックアップが実行される場合に、前述した状況が発生する。
【０１５３】
このため、コンテンツタイプ毎に必ず出現する普遍チャンクを参照する際には、ほとんど参照されることのない他のデータの管理情報も含むコンテナ索引表や対応するコンテナをメモリ上に展開する必要がある。この場合、必要性の低いデータの読み書きが多く発生すると共に、必要性の低いデータでメモリ資源が消費される。このことは、バックアップ性能およびリストア性能の低下に通じる。
【０１５４】
そこで、本実施形態では、普遍チャンクをコンテンツタイプ毎に特定する手法を採用する。このために、本実施形態に係るバックアッププログラム１５０は、静的普遍コンテナを作成する際に、コンテンツタイプ毎に計測表１６０を作成し、普遍チャンクを特定する。また、バックアッププログラム１５０は、特定した普遍チャンクを静的普遍コンテナに登録し、静的普遍コンテナ索引表を作成する。
【０１５５】
バックアッププログラム１５０は、その起動時に静的普遍コンテナ索引表および動的普遍コンテナ索引表をメモリ１０４に展開し、バックアップ対象のコンテンツが到着すると、普遍チャンク特定処理をコンテンツタイプ別に開始する。本実施形態における普遍チャンク特定処理の終了は、世代毎のバックアップが完了した時であり、計測表１６０で特定された普遍チャンクを動的普遍コンテナに登録する。続いて、バックアッププログラム１５０は、動的普遍コンテナをディスク１０６へ書き出し、動的普遍コンテナに追加登録された普遍チャンクのデータが、次回のバックアップ処理に反映されるように処理する。
【０１５６】
図１１に、本実施形態に係る普遍チャンクおよび管理情報の登録イメージを示す。図１１の場合、運用開始前に特定された普遍チャンクおよびその管理情報の組６００は、コンテンツタイプ別の組６１０、６１２、６１４で構成される。コンテンツタイプ別に生成された管理情報は静的普遍コンテナ索引表５１２に格納され、コンテンツタイプ別に特定された普遍チャンクは静的普遍コンテナ５２２に格納される。運用開始後に特定される普遍チャンクおよびその管理情報の組６０２は、コンテンツタイプ別の組６２０、６２２、６２４、６２６で構成される。なお、運用開始後に初めて扱う１又は複数のコンテンツタイプについては、それらを１つのグループとして扱い、それらに共通する普遍チャンクおよびその管理情報の組６２６とする。コンテンツタイプ別に生成された管理情報は動的普遍コンテナ索引表５１４に格納され、コンテンツタイプ別に特定された普遍チャンクは動的普遍コンテナ５２４に格納される。
【０１５７】
（４−２）ストレージ装置の構成
本実施形態に係るストレージ装置１００の機能構成は、バックアッププログラム１５０に設ける追加機能を除き、第１の実施形態とほぼ同様である。従って、詳細な説明は省略する。
【０１５８】
（４−３）バックアップ処理およびリストア処理
本実施形態に係るバックアップ処理及びリストア処理は、第１の実施の形態とほぼ同様である。従って、詳細な説明は省略する。
【０１５９】
（４−４）普遍コンテナの構成
本実施形態の場合も、バックアップ処理の開始前には、コンテンツタイプ毎に計測表１６０を用意して普遍チャンクを特定し、特定された普遍チャンクを静的普遍コンテナに登録する点以外は、前述した実施形態と同様である。また、バックアップ処理の開始中には、コンテンツタイプ毎に計測表１６０を用いて普遍チャンクを特定し、特定された普遍チャンクを動的普遍コンテナに登録する点以外は、前述した実施形態と同様である。
【０１６０】
図１１に示したように、本実施形態の場合、静的普遍コンテナ、動的普遍コンテナおよびそれらの索引表を、コンテンツタイプ毎にディスク１０６に格納する。各コンテンツタイプに対応する静的普遍コンテナ５２２は、バックアッププログラム１５０の起動時に、メモリ１０４に展開される。この際、バックアッププログラム１５０は、コンテンツタイプ別に用意された静的普遍コンテナ５２２を、１つの静的普遍コンテナおよびその索引表に集約した形態で新規登録することもできる。勿論、バックアッププログラム１５０は、それぞれを独立した静的コンテナおよび索引表としてメモリに展開してもよい。動的普遍コンテナおよびその索引表についても、コンテンツタイプ毎に独立したものとして構成してもよいし、それぞれを集約したものとして構成してもよい。
【０１６１】
（４−５）コンテンツタイプ毎に普遍チャンクを特定する処理
図１２に、コンテンツタイプ毎に普遍チャンクを特定するための処理手順を示す。バックアッププログラム１５０は、まず、バックアップ対象であるコンテンツ毎にそのコンテンツタイプを認識する（ステップＳ４０１）。このコンテンツタイプは、コンテンツのヘッダに格納されているマジックナンバーや拡張子などに基づいて認識することができる。なお、認識できなかったコンテンツタイプは１つのグループとして扱う。
【０１６２】
コンテンツタイプの認識後、バックアッププログラム１５０は、コンテンツタイプ別に図８に示した処理（ステップＳ４０２、Ｓ４０３、Ｓ４０４およびＳ４０５）を実行する。すなわち、コンテンツタイプ毎に普遍チャンクを特定する。
【０１６３】
（４−６）本実施形態の効果
以上のように、本実施形態では、普遍チャンク特定処理をコンテンツタイプ毎に適用する。このため、バックアップするコンテンツに複数のコンテンツタイプが混在している場合にも、コンテンツタイプ別の普遍チャンクを特定し、普遍コンテナおよびその索引表として管理することができる。このため、バックアップやリストアの実行時には、バックアップ対象であるコンテンツに必ず出現する普遍チャンクだけを格納する普遍コンテナとその索引表だけをメモリ上に展開することができる。すなわち、普遍チャンクの参照時以外にはほとんど参照されることがないコンテナ索引表やコンテナがメモリ上に展開される可能性を回避できる。この結果、バックアップ性能およびリストア性能を向上することができる。
【０１６４】
（５）第５の実施形態
（５−１）ストレージ装置に搭載する重複排除機能の概要
まず、本実施形態に係る重複排除機能の概要を説明する。前述した第４の実施形態では、バックアッププログラム１５０が、コンテンツタイプ毎の普遍チャンクの特定処理を静的にも動的にも実行する場合について説明した。しかし、コンテンツタイプは多数存在する。
【０１６５】
従って、全てのコンテンツタイプに対応して普遍チャンクの特定処理を実行することは処理負荷が大きい。また、コンテンツタイプの数だけ計測表１６０が必要となり、メモリ領域を消費する。また、実用上は、バックアップシステム毎に使用されるファイルフォーマットについてのみ静的普遍コンテナ、動的普遍コンテナおよびそれらの索引表を構成できればよく、全てのファイルフォーマットについて個別に普遍チャンクを登録する必要は無い。実際、全てのファイルフォーマットについて、静的普遍コンテナ、動的普遍コンテナおよびそれらの索引表を登録すると、使用頻度の少ない普遍チャンクの登録が発生し、リソースの無駄でもある。
【０１６６】
そこで、本実施形態では、実際に使用されるコンテンツタイプについてのみ、静的普遍コンテナ、動的普遍コンテナおよびそれらの索引表を構成することを可能にする。具体的には、静的普遍コンテナの作成に先立って、普遍コンテナとその索引表を作成するコンテンツタイプを、予めオペレータが指定する方式を採用する。選択後は、選択されたコンテンツタイプについてのみ計測表１６０を作成し、該当するコンテンツタイプについて普遍チャンクの特定処理を実行する。バックアッププログラム１５０は、特定された普遍チャンクを静的普遍コンテナに登録し、その管理情報の格納用に静的普遍コンテナ索引表を作成する。
【０１６７】
運用開始後、バックアッププログラム１５０は、その起動時に静的普遍コンテナ索引表および動的普遍コンテナ索引表をメモリ１０４上に展開し、バックアップ対象のコンテンツが到着するたびに、普遍チャンク特定処理を選択されたコンテンツタイプ毎に開始する。普遍チャンク特定処理は、世代毎のバックアップが完了した時に終了する。バックアッププログラム１５０は、計測表１６０を用いて特定された普遍チャンクを動的普遍コンテナに登録する。次にバックアッププログラム１５０は、動的普遍コンテナをディスク１０６に書き出し、動的普遍コンテナに追加登録された普遍チャンクのデータが、次回のバックアップに反映されるように処理する。
【０１６８】
使用予定のコンテンツタイプの選択および指定は、オペレータによる管理者端末装置１７２に対する操作入力を通じて行う。管理者端末装置１７２は、操作入力に応じた指示（コマンド等）をバックアッププログラム１５０に発行する。もっとも、バックアッププログラム１５０に対するこれらの指示は、管理者端末装置１７２から指定しない場合も考えられる。この場合、対応する指示は、初期化ファイル等に初期値として予め格納しておき、バックアッププログラム１５０の起動時に当該初期値を読み込んでもよい。
【０１６９】
図１３に、管理者端末装置１７２の操作画面に表示されるコンテンツタイプ選択画面７００の構成例を示す。図１３（Ａ）は、コンテンツタイプを選択する前の画面構成例を示す。選択画面７００は、選択可能コンテンツタイプのリスト欄７０２、選択済みコンテンツタイプ欄７０４、リスト欄７０２で選択されたコンテンツタイプを選択済みコンテンツタイプ欄７０４に反映させるボタン７１０、選択済みコンテンツタイプ欄７０４に選択されたコンテンツタイプをバックアップシステムに反映させる登録ボタン７１２から構成される。
【０１７０】
図１３（Ｂ）は、コンテンツタイプを選択した後の画面構成を説明する画面例である。図１３（Ｂ）は、リスト欄７０２に示される４つのコンテンツタイプの中からコンテンツタイプＦＴ２が選択され、ボタン７１０がクリック操作された後の画面を表している。リスト欄７０２の網掛け表示７２０は、コンテンツタイプＦＴ２が選択状態にあることを表している。選択状態は、例えば選択前とは異なる色で表示される。ボタン７１０の操作後であるので、選択済コンテンツタイプ欄７０４には、選択されたコンテンツタイプの名称７２２が示される。
【０１７１】
図１４に、本実施形態による普遍コンテナおよびその索引表の登録イメージを示す。図１４は、運用開始前に特定された（又は特定可能な）普遍チャンクおよびその管理情報の組６００のうち図１３（Ｂ）に示す操作画面で選択されたコンテンツタイプだけが静的普遍コンテナ５２２および静的普遍コンテナ索引表５１２に格納される様子を表している。
【０１７２】
図１４では、普遍チャンクおよびその管理情報の組６００として、コンテンツタイプＦＴ１に対応する組６１０、コンテンツタイプＦＴ２に対応する組６１２、コンテンツタイプＦＴｘに対応する組６１４を描いている。また、選択済みのコンテンツタイプＦＴ２に対応する静的普遍コンテナが静的普遍コンテナ５２２に登録され、対応する管理情報が静的普遍コンテナ索引表５１２に登録されている。
【０１７３】
本実施形態の場合、運用開始後における普遍チャンクの特定処理は、選択されたコンテンツタイプとそれ以外のコンテンツタイプについて実行される。図１３（Ｂ）の場合、選択されたコンテンツタイプは１つである。従って、図１４においても、運用開始後に特定される普遍チャンクおよびその管理情報の組６０２は、コンテンツタイプＦＴ２に対応する組６２２とそれ以外のコンテンツタイプに対応する組６２６の２種類となる。この場合、これら２種類のコンテンツタイプについてそれぞれ特定された普遍チャンクは動的普遍コンテナ５２４に格納され、その管理情報は動的普遍コンテナ索引表５１４に登録される。
【０１７４】
（５−２）ストレージ装置の構成
本実施形態に係るストレージ装置１００の機能構成は、バックアッププログラム１５０に設ける追加機能を除き、第１の実施形態とほぼ同様である。従って、詳細な説明は省略する。
【０１７５】
（５−３）バックアップ処理およびリストア処理
本実施形態に係るバックアップ処理及びリストア処理は、第１の実施の形態とほぼ同様である。従って、詳細な説明は省略する。
【０１７６】
（５−４）普遍コンテナの構成
本実施形態の場合も、バックアップ処理の開始前には、選択されたコンテンツタイプ毎に計測表１６０を用意して普遍チャンクを特定し、特定された普遍チャンクを静的普遍コンテナに登録する点以外は第４の実施形態と同じである。
【０１７７】
同様に、本実施形態の場合も、バックアップ処理の開始中には、選択されたコンテンツタイプとそれ以外のコンテンツタイプ毎に計測表１６０を用いて普遍チャンクを特定し、特定された普遍チャンクを動的普遍コンテナに登録する点以外は、前述した実施形態と同様である。
【０１７８】
また、本実施形態の場合も、静的普遍コンテナ、動的普遍コンテナおよびそれらの索引表を、コンテンツタイプ毎にディスク１０６に格納する。選択されたコンテンツタイプに対応する静的普遍コンテナ５２２は、バックアッププログラム１５０の起動時に、メモリ１０４に展開される。この際、選択された複数のコンテンツタイプに対応する静的普遍コンテナおよびその索引表を、１つの静的普遍コンテナおよびその索引表に集約した形態で新規登録することもできる。勿論、バックアッププログラム１５０は、それぞれを独立した静的コンテナおよび索引表としてメモリに展開してもよい。動的普遍コンテナおよびその索引表についても、選択されたコンテンツタイプ毎に独立したものとして構成してもよいし、それぞれを集約したものとして構成してもよい。
【０１７９】
（５−５）本実施形態の効果
以上のように、本実施形態では、普遍チャンク特定処理を指定されたコンテンツタイプについてのみ適用する。このため、考えられる又は出現する全てのコンテンツタイプについて、個別に普遍チャンク特定処理を実行する場合に比して処理負荷を抑制することができる。また、本実施形態の場合には、考えられる又は出現する全てのコンテンツタイプについて個別の計測表１６０を用意する必要がない。従って、コンテンツタイプを選択しない場合に比して、メモリの消費量を必要最低限に抑制することができる。また、考えられる又は出現する全てのファイルフォーマット毎に普遍チャンクを登録する場合には、静的普遍コンテナ、動的普遍コンテナおよびその索引表に、使用頻度の小さい普遍チャンクの登録が発生し、リソースの無駄でもある。しかし、本実施形態の場合には、選択されたコンテンツタイプについてのみ、静的普遍コンテナ、動的普遍コンテナおよびその索引表を生成し、管理することにより、バックアップ性能およびリストア性能を向上することができる。
【０１８０】
（６）他の実施の形態
前述の実施形態においては、各種処理機能の全体を制御する制御部としてプロセッサ１０２を適用する場合について説明した。しかし、本発明はこれに限らず、かかる制御部としての処理を実行するハードウェアやソフトウェアを、プロセッサ１０２とは別に用意してもよい。このような構成を採用する場合にも、前述の実施形態と同様の効果を実現することができる。
【０１８１】
また、各実施形態に係る重複排除機能を実現する処理ステップは、必ずしもフローチャートに記載した順序に沿って時系列に処理する必要はない。すなわち、ストレージ装置１００等で実行される処理ステップの実行順序は実施形態とは異なっていてもよいし、並列的に実行されてもよい。
【０１８２】
また、ストレージ装置１００等に内蔵されるＣＰＵ、ＲＯＭおよびＲＡＭなどのハードウェア構成を、これらと同等の機能を有するコンピュータプログラムの処理を通じて実現してもよい。また、このコンピュータプログラムは、ネットワーク経由で配信してもよいし、記憶媒体に記憶した状態で提供してもよい。
【産業上の利用可能性】
【０１８３】
本発明は、コンテンツをチャンク単位で重複排除してコンテナに格納する方式のストレージ装置に広く適用することができる。
【符号の説明】
【０１８４】
１００ ストレージ装置
１０２ プロセッサ
１０４ メモリ
１０６ ディスク
１０８ ネットワークインタフェース
１１０ コンテナ索引表
１１２ コンテナ索引表
１１４ コンテナ索引表
１１８ 普遍コンテナ索引表
１３８ 普遍コンテナ
１４２ ライトバッファ
１４４ リードキャッシュ
１５０ バックアッププログラム
１５２ リストアプログラム
１５４ オペレーティングシステム
１６０ 計測表
１６２ チャンク索引表
１６４ コンテンツ索引表
【図１】
0005881859.tif 000002
【図２】
0005881859.tif 000003
【図３】
0005881859.tif 000004
【図４Ａ】
0005881859.tif 000005
【図４Ｂ】
0005881859.tif 000006
【図５】
0005881859.tif 000007
【図６】
0005881859.tif 000008
【図７】
0005881859.tif 000009
【図８】
0005881859.tif 000010
【図９】
0005881859.tif 000011
【図１０】
0005881859.tif 000012
【図１１】
0005881859.tif 000013
【図１２】
0005881859.tif 000014
【図１３】
0005881859.tif 000015
【図１４】
0005881859.tif 000016