(57)【特許請求の範囲】
【請求項１】
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備え、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を備え、
前記データ管理部は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータがレベル１段階における予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータをレベル２段階の前記第二補助記憶装置に記憶保持し、このレベル２段階の第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除し、レベル２段階の前記第二補助記憶装置に記憶保持された前記インデックスデータがレベル２段階における予め設定された量に達した場合に、レベル２段階の当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合してレベル３段階の前記第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータをレベル２段階の前記第二補助記憶装置から削除する、
ストレージシステム。
【請求項２】
請求項１に記載のストレージシステムであって、
前記データ管理部は、レベル２段階の前記第二補助記憶装置に記憶保持されている前記複数単位のインデックスデータと前記主記憶装置に記憶保持されている前記インデックスデータとを結合してレベル３段階の前記第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータをレベル２段階の前記第二補助記憶装置及び前記主記憶装置から削除する、
ストレージシステム。
【請求項３】
請求項１又は２に記載のストレージシステムであって、
前記データ管理部は、レベル２段階の前記第二補助記憶装置に記憶された前記インデックスデータが存在するか否かを判定するために用いられる当該インデックスデータのデータ内容に基づく要素データを、前記主記憶装置に記憶する、
ストレージシステム。
【請求項４】
請求項３に記載のストレージシステムであって、
前記データ管理部は、レベル２段階の前記第二補助記憶装置に記憶された前記インデックスデータをまとめてレベル３段階の当該第二補助記憶装置に記憶し直す際に、前記主記憶装置に記憶された前記インデックスデータの前記要素データを解放する、
ストレージシステム。
【請求項５】
請求項１乃至４のいずれかに記載のストレージシステムであって、
前記第一補助記憶装置はハードディスクドライブであり、前記第二補助記憶装置はＳＳＤ（Solid State Drive）である、
ストレージシステム。
【請求項６】
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えた情報処理装置に、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を実現させると共に、
前記データ管理部は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータがレベル１段階における予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータをレベル２段階の前記第二補助記憶装置に記憶保持し、このレベル２段階の第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除し、レベル２段階の前記第二補助記憶装置に記憶保持された前記インデックスデータがレベル２段階における予め設定された量に達した場合に、レベル２段階の当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合してレベル３段階の前記第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータをレベル２段階の前記第二補助記憶装置から削除する、
ことを実現させるためのプログラム。
【請求項７】
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えたストレージシステムにて、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照することにより、記憶対象データを管理し、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定すると共に、
記憶対象データを管理する際に、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータがレベル１段階における予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータをレベル２段階の前記第二補助記憶装置に記憶保持し、このレベル２段階の第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除し、レベル２段階の前記第二補助記憶装置に記憶保持された前記インデックスデータがレベル２段階における予め設定された量に達した場合に、レベル２段階の当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合してレベル３段階の前記第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータをレベル２段階の前記第二補助記憶装置から削除する、
データ管理方法。
【請求項８】
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備え、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を備え、
前記データ管理部は、前記インデックスデータからなるハッシュテーブルを所定サイズのスイープ領域に分割して記憶すると共に、前記ハッシュテーブルの更新の際に、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置にキャッシュとして記憶保持し、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記キャッシュとしての前記インデックスデータを前記第二補助記憶装置に形成された前記スイープ領域に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、
ストレージシステム。
【請求項９】
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備え、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を備え、
前記データ管理部は、
前記インデックスデータからなるハッシュテーブルを所定サイズのスイープ領域に分割して記憶すると共に、
前記ハッシュテーブルの更新の際に、
前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置にキャッシュとして記憶保持し、前記主記憶装置に対して記憶保持された前記インデックスデータが当該主記憶装置における予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記キャッシュとしての前記インデックスデータを前記第二補助記憶装置に前記キャッシュとして記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除し、
前記第二補助記憶装置に前記キャッシュとして記憶保持された前記インデックスデータが当該第二補助記憶装置における予め設定された量に達した場合に、当該第二補助記憶装置に記憶保持されている前記キャッシュとしての前記インデックスデータを当該第二補助記憶装置に形成された前記スイープ領域に記憶保持する、
ストレージシステム。
【請求項１０】
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備え、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を備え、
前記データ管理部は、
前記インデックスデータからなるハッシュテーブルを所定サイズのスイープ領域に分割して記憶すると共に、
前記ハッシュテーブルの更新の際に、
前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置にキャッシュとして記憶保持し、前記主記憶装置に対して記憶保持された前記インデックスデータがレベル１段階における予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記キャッシュとしての前記インデックスデータをレベル２段階の前記第二補助記憶装置に前記キャッシュとして記憶保持し、このレベル２段階の第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除し、
レベル２段階の第二補助記憶装置に前記キャッシュとして記憶保持された前記インデックスデータがレベル２段階における予め設定された量に達した場合に、レベル２段階の当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合してレベル３段階の前記第二補助記憶装置に前記キャッシュとして記憶保持し直すと共に、結合される前の前記インデックスデータをレベル２段階の前記第二補助記憶装置から削除し、
レベル３段階の第二補助記憶装置に前記キャッシュとして記憶保持された前記インデックスデータがレベル３段階における予め設定された量に達した場合に、レベル３段階の当該第二補助記憶装置に記憶保持されている前記キャッシュとしての前記インデックスデータを前記第二補助記憶装置に形成された前記スイープ領域に記憶保持する、
ストレージシステム。
【請求項１１】
請求項９又は１０に記載のストレージシステムであって、
前記データ管理部は、前記インデックスデータを前記スイープ領域に記憶保持するときに、前記主記憶装置及び前記第二補助記憶装置に前記キャッシュとして記憶保持されているすべての前記インデックスデータを前記スイープ領域に記憶保持する、
ストレージシステム。
【請求項１２】
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えた情報処理装置に、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を実現させると共に、
前記データ管理部は、前記インデックスデータからなるハッシュテーブルを所定サイズのスイープ領域に分割して記憶すると共に、前記ハッシュテーブルの更新の際に、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置にキャッシュとして記憶保持し、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記キャッシュとしての前記インデックスデータを前記第二補助記憶装置に形成された前記スイープ領域に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、
ことを実現させるためのプログラム。
【請求項１３】
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えたストレージシステムにて、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照することにより、記憶対象データを管理し、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定すると共に、
記憶対象データを管理する際に、前記インデックスデータからなるハッシュテーブルを所定サイズのスイープ領域に分割して記憶すると共に、前記ハッシュテーブルの更新時に、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置にキャッシュとして記憶保持し、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記キャッシュとしての前記インデックスデータを前記第二補助記憶装置に形成された前記スイープ領域に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、
データ管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージシステムにかかり、特に、重複記憶排除機能を有するストレージシステムに関する。
【背景技術】
【０００２】
この数年の間に、データ重複排除技術はストレージシステムの分野で最も広く研究されるテーマの１つになった。重複排除技術により、特にバックアップの用途については必要な記憶領域が２０分の１にまで削減されるため、使用する領域を著しく節約することができる。重複排除機能は、容量の最適化に加えて、書込みの帯域幅も最適化することもできる。システムがインラインで重複排除機能を提供し（データ書込み中に実行）、ハッシュ値のみを比較してチャンクが等しいことを検証すれば、重複するチャンクのデータをディスクに格納したり、またネットワークを通して送信する必要がない。しかし、重複を識別する有効な方法を提供することは簡単ではない。
【０００３】
信頼性のあるインライン重複排除機能を持つ、単一ノードのディスクベースのストレージシステムの例について検討する。２Ｕのストレージノードが１２台の１ＴＢのディスクを有する、つまり各ノードが計１２ＴＢのディスクを有すると仮定する。重複排除は、チャンクレベルで、それらの内容のハッシュ値を比較することによって行われる。関連する技術では、８ｋＢのチャンクサイズが効果的な選択だと記載している。このチャンクサイズで重複排除を行うためには、１５億のエントリを含む辞書が必要である。これらのハッシュ値のみを保存するだけで、ＳＨＡ−１の場合は３０ＧＢ、ＳＨＡ−２５６の場合は５０ＧＢを消費することになり、妥当なサイズのＲＡＭには収まらない。
【０００４】
現在のシステムは、辞書をディスク常駐型のハッシュテーブルとして実装している。しかし、データチャンクのハッシュ値は一様に分散されており、それらにアクセスする上で局所性がない。そのため単純なキャッシュは効果がなく、検索時にディスクからランダムにアクセスすることになる。非特許文献１，２は、次の２つの最適化技術を組み合わせることを提案している。
【０００５】
１．システム内に存在しないチャンクの検索時にディスクにアクセスしないように、すべてのハッシュ値をメモリ内のブルームフィルタに集約しておく。これにより、チャンクがシステム内に存在しない場合の処理が早くなる。
２．重複する内容の書込みの順序がオリジナルのチャンクの書込みの順序と同じであると仮定してプリフェッチを行う。さらにハッシュ値を、当初書き込まれた順序が反映された特別なファイルに保存しておく。これにより、順序が保存されている場合は、チャンクがシステム内に存在する場合の処理が早くなる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】ZHU, B., LI, K., AND PATTERSON, H. Avoiding the disk bottleneck inthe data domain deduplication file system. In FAST’08: Proceedings of the 6thUSENIX Conference on File and Storage Technologies (Berkeley, CA, USA, 2008),USENIX Association, pp. 1‐14.
【非特許文献２】RHEA, S., COX, R., AND PESTEREV, A. Fast, inexpensive content-addressedstorage in foundation. In Proceedings of the 2008 USENIX Annual TechnicalConference (Berkeley, CA, USA, 2008), USENIX Association, pp. 143‐156.
【非特許文献３】DEBNATH, B., SENGUPTA, S., AND LI, J. Chunkstash: Speeding up inlinestorage deduplication using flash memory. In 2010 USENIX Annual TechnicalConference (June 2010).
【非特許文献４】MEISTER, D., AND BRINKMANN, A. dedupv1: ImprovingDeduplication Throughput using Solid StateDrives (SSD). In Proceedings of the 26th IEEE Symposium on Massive Storage Systemsand Technologies (MSST) (May 2010).
【非特許文献５】QUINLAN, S., AND DORWARD, S. Venti: a new approach to archivalstorage. In First USENIX conference on File and Storage Technologies (Monterey,CA, 2002), USENIX Association, pp. 89‐101.
【非特許文献６】WEI, J., JIANG, H., ZHOU, K., AND FENG, D. Mad2: A scalable high-throughputexact deduplication approach for network backup services. In Proceedings of the26th IEEE Symposium on Massive Storage Systems and Technologies (MSST) (May2010).
【非特許文献７】LILLIBRIDGE,M., ESHGHI, K., BHAGWAT, D., DEOLALIKAR, V., TREZIS, G.,AND CAMBLE, P. Sparse indexing: Large scale, inline deduplication usingsampling and locality. In FAST (2009), pp. 111‐123.
【非特許文献８】BHAGWAT, D., ESHGHI, K., LONG, D. D. E., AND LILLIBRIDGE, M. Extremebinning: Scalable, parallel deduplication for chunk-based file backup.
【非特許文献９】MING YANG, T., FENG, D., YING NIU, Z., AND PING WAN, Y. Scalablehigh performance de-duplication backup via hash join. Journal of ZhejiangUniversity ‐ Science C 11, 5 (2010), 315‐327.
【非特許文献１０】YANG, T., JIANGY, H., FENGZ, D., AND NIU, Z. Debar: A scalablehigh-performance de-duplication storage system for backup and archiving. Tech.rep., University of Nebraska - Lincoln, 2009.
【非特許文献１１】CLEMENTS, A., AHMAD, I., VILAYANNUR, M., AND LI, J. Decentralizeddeduplication in san cluster file systems. In Proceedings of the USENIX AnnualTechnical Conference (June 2009).
【非特許文献１２】GOKHALE, S., AGRAWAL, N., NOONAN, S., AND UNGUREANU, C. KVZone andthe Search for a Write-Optimized Key-Value Store. In USENIX 2nd Workshop on HotTopics in Storage and File Systems (HotStorage ’10) (Boston, MA, June 2010).
【非特許文献１３】YIN, S., PUCHERAL, P., AND MENG, X. Pbfilter: Indexing flash-residentdata through partitioned summaries. Research Report RR-6548, INRIA, 2008.
【非特許文献１４】YIN, S., PUCHERAL, P., AND MENG, X. Pbfilter: indexing flash-residentdata through partitioned summaries. In CIKM (2008), pp. 1333‐1334.
【非特許文献１５】CHANG, F., DEAN, J., GHEMAWAT, S., HSIEH, W. C., WALLACH, D. A.,BURROWS, M., CHANDRA, T., FIKES, A., AND GRUBER, R. E. Bigtable: A distributedstorage system for structured data. In OSDI’06: 7th USENIX Symposium onOperating Systems Design and Implementation (Berkeley, CA, USA, 2006), USENIXAssociation, pp. 205‐218.
【非特許文献１６】LEE, S.-W., AND MOON, B. Design of flash-based dbms: an inpage loggingapproach. In SIGMOD Conference (2007), pp. 55‐66.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
これらの技術は適切な帯域幅を実現することは可能かもしれないが、次のような欠点がある。
【０００８】
ブルームフィルタおよびプリフェッチの両方に追加のメモリが必要なため、サイズが著しく大きくなる（メモリの消費については後に詳細に述べる。
ＲＡＭを使用する動作もあればディスクへのアクセスが必要な動作もあるため、検索動作のレイテンシが安定しない。レイテンシが数ミリ秒のディスクの読出しは、用途によっては十分ではない（例えばプライマリストレージ）。
重複する書込みがオリジナルの書込みと同じ順序で行われない場合、プリフェッチは事実上作業を停止し、スループットが数オーダーの規模で低下する。
【０００９】
３番目の欠点が最も深刻だと思われる。上記非特許文献２によれば、重複を書き込む順序はパフォーマンスに多大な影響を与える。基盤システムは、重複がオリジナルの書き込みと同じ順序であれば２２ＭＢ／秒の性能を達成するが、重複の順序が異なる場合は６ＫＢ／秒の性能しか達成されない。ここで問題となるのは、実際のバックアップに用いる際に順序通りでない重複がどの程度の頻度で発生するか、ということである。バックアップが行われる度に、データの断片が多少変化する。２回のバックアップ間での変化は小さくても、最初と最後のバックアップの間では、その違いはかなり大きくなると思われる。毎回、次のバックアップが行われる度に重複の順序の精度が低下し、最終的には順序が変わってしまうであろう。我々はこの分野に関する研究をまだ発見していないが、バックアップを何十回も繰り返せばこのような事態になると予想される。この問題は、同一データのバックアップの回数だけでなく、バックアップ群の数によっても悪化する。なぜなら、複数のバックアップ群に渡って、データが重複しうるからである。１つのバックアップが多数の小さなファイルで構成される場合、これらのファイルが異なる順序で書き込まれる可能性があるため、この問題は更に深刻になると思われる。
【００１０】
このため、本発明の目的は、上述した課題である、メモリサイズの増大を抑制しつつ、レイテンシの安定化を図り、順序が異なる書き込みに対して効率的な重複排除を実現できるストレージシステムを提供することにある。
【課題を解決するための手段】
【００１１】
本発明の一形態であるストレージシステムは、
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備え、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を備え、
前記データ管理部は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、
という構成をとる。
【００１２】
また、本発明の他の形態であるプログラムを記憶した記憶媒体は、
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えた情報処理装置に、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を実現させると共に、
前記データ管理部は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、
ことを実現させるためのプログラムを記憶した記憶媒体である。
【００１３】
また、本発明の他の形態であるデータ管理方法は、
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えたストレージシステムにて、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照することにより、記憶対象データを管理し、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定すると共に、
記憶対象データを管理する際に、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、
という構成をとる。
【発明の効果】
【００１４】
本発明は、以上のように構成されることにより、メモリサイズの増大を抑制しつつ、レイテンシの安定化を図り、順序が異なる書き込みに対して効率的な重複排除を実現できるストレージシステムを提供することができる。
【図面の簡単な説明】
【００１５】
【図１】実施形態１におけるＳＳＤの性能テストの結果を示す図である。
【図２】実施形態１におけるチャンクを検索するときの様子を示す図である。
【図３】実施形態１におけるソリッドステート重複排除インデックスを示す図である。
【図４】実施形態１においてλに対する書込みキャッシュのサイズ、相対価格、およびスイープによるＳＳＤ使用率を示す図である。
【図５】実施形態１における３階層の書込みキャッシュ構成を示す図である。
【図６】実施形態１における様々な書込みキャッシュ構成の比較を示す図である。
【図７】実施形態１で行ったテストにおける書込み性能を示す図である。
【図８】実施形態１で行ったテストにおける書込み時のディスク使用率を示す図である。
【図９】実施形態１で行ったテストにおけるＬＲＵストリームプリフェッチの効果を示す図である。
【図１０】実施形態１における様々な解決策のコストを示す図である。
【図１１】実施形態１における方法と非特許文献における方法との比較結果を示す図である。
【図１２】実施形態２におけるストレージシステムを含むシステム全体の構成を示すブロック図である。
【図１３】実施形態２におけるストレージシステムの構成の概略を示すブロック図である。
【図１４】実施形態２におけるストレージシステムの構成を示す機能ブロック図である。
【図１５】図１４に開示したストレージシステムにおけるデータ記憶処理の様子を説明するための説明図である。
【図１６】図１４に開示したストレージシステムにおけるデータ記憶処理の様子を説明するための説明図である。
【図１７】図１４に開示したストレージシステムにおけるデータ読み出し処理の様子を説明するための説明図である。
【図１８】実施形態２におけるデータ格納時の様子を示す図である。
【図１９】実施形態２におけるインデックスデータ格納時の様子を示す図である。
【図２０】本発明の付記１におけるストレージシステムの構成を示すブロック図である。
【発明を実施するための形態】
【００１６】
＜実施形態１＞
本願では、フラッシュベースのＳＳＤ用に設計された重複検索構造であるソリッドステート重複排除インデックス（ＳｏｌｉｄＳｔａｔｅＤｅｄｕｐｌｉｃａｔｉｏｎＩｎｄｅｘ：ＳＳＤＩ）を提案する。本願で提案する解決策は、前述の欠点を解決し、順序が異なる重複排除にも有効であり、検索動作に安定性がありかつレイテンシが短く、ＲＡＭの消費が少ない。また、重複排除を検索するためにＳＳＤに基づく別の構造を提案している最近の研究とは異なり、本願における設計はＳＳＤの削除制限と書込み耐性についても考慮し、またこの解決策に必要なＲＡＭの定量化を行っている。
【００１７】
本願は次のように構成されている。まず、フラッシュベースＳＳＤの読出し／書込み動作の効率について説明する。次に、ＣｌｏｓｅｄＨａｓｈ法について説明し、それをＳＳＤに適用することによって発生する問題点を示す。次に、性能要件を満たす辞書構造であるＳＳＤＩを提示する。次に、提案した解決策の性能を評価し、他のアプローチと比較する。次に、関連技術を提示し、最後に、結論を出す。
【００１８】
［ＳＳＤの特徴］
重複識別構造をＳＳＤに実装可能にするためには、毎秒十分な数の小さなランダムな読出しを行うことができるＳＳＤ装置を探す必要がある。ＳＳＤ装置のその他の特徴は、本発明にとってはそれほど重要ではない。例えば停電耐性は必要ない。その理由は、データディスクに保存されている情報に基づいて構造を再構築することができると想定しているからである。さらに、本発明におけるシステムで使用するハードウェアの価格を抑えるため、この装置はかなり安価なものでなければならない。
【００１９】
８０ＧＢのＩｎｔｅｌ  Ｘ２５−Ｍ  ＳＡＴＡ  ＳＳＤおよび１ＴＢのＨｉｔａｃｈｉ  Ｕｌｔｒａ−ｓｔａｒｔ  ７２００  ＲＰＭ  ＳＡＴＡ  ＨＤＤで実行した性能テストの結果を示す。テストを行う前に、ＳＳＤ装置をランダムなデータで満たした（ＳＳＤの状態が性能に影響を与える場合がある。例えば、装置にデータを入れた後では、装置外の書込みの帯域幅がかなり高くなる場合がある）。このテストは、Ｌｉｎｕｘ上でダイレクトＩ／ＯとＮａｔｉｖｅＣｏｍｍａｎｄＱｕｅｉｎｇを用いて行い、ＳＳＤ上の書込みキャッシュを無効にした。
【００２０】
その結果を図１に示す。ランダムな読出しとランダムな書込みの特徴はＨＤＤ用のものと似ているが、ＳＳＤではランダムな書込みはランダムな読出しよりもはるかに遅い。ＳＳＤはディスクよりも早く最大帯域幅に達する（つまり、より小さなブロックについて）。小さなＳＳＤの読出しは、非常に高速なＩＯＰＳレートで良好な帯域幅に達する。一方、小さなＳＳＤの書込みは特に非効率である。
【００２１】
ＳＳＤの書込み帯域幅は、「削除ブロックサイズ」（６４ＫＢ）を上限として要求サイズに合わせて拡大される。ランダムな書込みは、削除ブロックのサイズと同等またはそれより大きい場合に最適な帯域幅に達する。その理由は、小さな要求の書込みを行う場合、フラッシュトランザクションレイヤ（ＦＴＬ：ＦｌａｓｈＴｒａｎｓａｃｔｉｏｎＬａｙｅｒ）は通常、削除ブロック全体を削除して再び書き込む必要があるからである（小さな連続書込みは装置の書込みキャッシュによってバッファリングされる）。より安価な装置のＦＴＬは一般的に削除ブロックレベルで動作する。そうでないと、ＦＴＬは変換を保存するためにＳＳＤの内部ＲＡＭを過剰に消費することになる。
【００２２】
通常、ＳＳＤが処理する小さなランダムな読出しの数は多いが、適切な書込み帯域幅を達成するために、ＳＳＤの書込みは大きなブロックで出される必要がある。
【００２３】
［クローズドハッシュ法］
ハッシュテーブルは、重複排除辞書とてして当然選択されるものである。データチャンクはそのハッシュ値によって識別されるため、データチャンクのハッシュ値はハッシュテーブルの鍵となる。各ハッシュテーブルのエントリには、１つのチャンクのメタデータ記録が保存される。チャンク毎に、少なくともそのハッシュ値（例えばＳＨＡ−１は２０バイト、ＳＨＡ−２５６は３２バイト）とディスク上の場所を保存する必要があるため、各メタデータ記録は数十バイトを消費する。
【００２４】
本願で提案する構造について、クローズドハッシュ法から推論を開始し、その後で、なぜフラッシュベースの重複辞書に直接利用できないのかを述べる。クローズドハッシュ法では、キーをエントリが保存されているテーブル内のインデックスに変換するハッシュ関数がある。効率的に機能させるために、ハッシュテーブルには開放されるエントリの一定の断片が必要である。本願で使用するメタデータ記録はかなり大きいため、記録の値をテーブルに直接保存するのは効率的でない。それを避けるために、ハッシュテーブルとメタデータテーブルの２つを利用する（図２参照）。キーに関するハッシュ関数がハッシュテーブル内のインデックスを決定し、データの衝突は線形走査法を用いて解決する。ハッシュテーブル内では、メタデータテーブルに対するインデックスのみが保存される。検索の際、メタデータテーブルからキーを読み出しそれを所望するキーと比較することによって、ハッシュテーブルからエントリを確認する。ハッシュ関数で得られたインデックスを持つエントリから順に１つずつ確認し、一致するメタデータ記録が得られるまで、またはハッシュテーブル内に空のエントリがあるまで、これを行う。
【００２５】
上記の構造をフラッシュベースのソリッドステートドライブに適用する場合の効率について検討する。上記で述べた見解によれば、小さなランダムな読出しは効率的である。唯一懸念されることは、検索時にハッシュテーブルとメタデータテーブルの両方を確認する必要があることである。ハッシュテーブルからの読出しは、候補がグループ化されており１回の読出し要求ですむため、効率的である。しかし、候補となるメタデータ記録はメタデータテーブル全体にランダムに配置されているため、１回の要求では読み出すことができない。各候補について、メタデータテーブルからキーを得るために追加の読出し要求を発行しなければならない。所定のキーがあるかどうかを確認する読出し要求の数は、ハッシュテーブルの負荷率が増えるに従って増大する。例えば、図２に示すケースでは、chunk1の検索にメタデータテーブルから２回の読出しが必要となる。
【００２６】
新たなエントリが入力されると、より深刻な問題が発生する。ハッシュの分散は一様であるため、入力する際に領域の局所性がない。ランダムな書込みのＩＯＰＳ数は、すべての入力に対してＳＳＤ構造を更新可能にすることはできない。小さなランダムな書込みはコストがかかり、その帯域幅は狭く、削除されるデータ量が実際に修正および書込みされるデータよりもはるかに大きいため、早く更新回数の上限に達することがある。メタデータテーブルは一括書込みで更新できるため、問題となるのは主にハッシュテーブルに関するものである。本願では、書込み要求のサイズがより大きくなるように、好ましくは削除ブロックと等しいサイズになるように、構造を構築する必要がある。
【００２７】
［ソリッドステート重複排除インデックス］
ここでは、重複排除に関する性能の要件を満たすフラッシュベース構造であるソリッドステート重複排除インデックスについて説明する。この構造によると、上記段落で最後に述べた問題が解決されている。
【００２８】
メタデータテーブルからの不要な読出しを避けるために、もう１つフィルタ機能を導入する。ハッシュテーブルの各エントリは、メタデータテーブルに対するインデックスだけでなく、このメタデータからのキーの小さな部分であるフィルタも保存する。メタデータテーブルからの読出しは、フィルタのビットが、検索されるキーの対応するビットと一致する場合にのみ実行される。図３に示す状況では、chunk1の検索時、key2用のメタデータ記録は、f(key1)=f(key2)でない限り読み出されない。なお、このようなフィルタリングにより、誤ったキーでメタデータ記録が読み出される確率が効果的に減少する。各エントリで、フィルタに使用する容量が１０ビットだけだとしても、誤ったキーのメタデータ記録が読み出される確率は１／１０２４である。ハッシュテーブルを拡大して同じ削減率を達成するには、何倍も大きくする必要がある。
【００２９】
フラッシュのアーキテクチャは、ハッシュテーブルのインプレース更新を不可能にする。大きなブロックの書込みだけが満足できる帯域幅を達成する。したがって、ハッシュテーブルの更新はバッチモードで行う必要がある。そのために、本願では、ＲＡＭに保存する書込みキャッシュを導入する。更新の際、新たなキーはこのキャッシュにしか入力されない。書込みキャッシュは、効率的なキー検索を可能にするハッシュマップとして構築される。キーを検索する一方で、ハッシュテーブルの確認に加えて書込みキャッシュを確認する必要がある。図３では、key4のメタデータ記録のインデックスを書込みキャッシュから取得する。なお、書込みキャッシュ全体はメモリに保存されるため、追加の確認作業が性能に与える影響は無視できる程度である。キャッシュが完全にロードされたら「スイープ」動作を行う。つまりハッシュテーブルは、この処理での書込みキャッシュをクリアする、すべてのキャッシュされた修正の適用に伴って書き換えられる。スイープの実装を簡易にするために、本願ではハッシュテーブルを固定サイズの非連結領域に分割する。このサイズは、メモリ内に領域全体を読み込めるような小さなサイズでなければならない。書込みキャッシュはこのように分割されるため、各領域はＲＡＭ内に独自のキャッシュを有し、これは独立してスイープすることが可能である。
【００３０】
また、インプレース更新を避けるために、メタデータテーブルの構成を修正する必要がある。そのために、まずディスクベースの重複排除ストレージシステムにおけるデータ構成について説明する。調査したすべてのシステムにおいて、データチャンク用コンテナの抽象的概念が導入されている。このコンテナに関して提案されている名称はシステムごとに異なる。例えば、アリーナ、メガブロック、コンテナ、ｓｙｎｃｈｒｕｎコンポーネントコンテナ（ＳＣＣ）と言われることがある。コンテナ内のデータの詳細な構造はシステム毎に異なるが、コンテナはディスク上の個別のファイルに保存されるようになっている。コンテナ上の動作は、コンテナファイルへのアクセス時に連続して読取り／書込みができるように実行され、これにより次のようにディスクが効率的に使用される。
【００３１】
数個のコンテナしか追加用に空いておらず新規書込みはそれらに直接行われるため、コンテナへの新規書込みは順次的に行われる（ログで構成されるファイルシステムと類似）。
チャンクが書込み時と同じ順序で読み込まれると、コンテナからの読出しも順次的になる。
システムによって保存されているチャンクの修正または同期の動作により、すべてのコンテナが一度に更新される（例えば、チャンクが削除済みとマークする、削除されたチャンクが占有している領域を再利用する、等）
【００３２】
本願における設計はコンテナのアプローチを採用している。１つのグローバルなメタデータテーブルではなく、コンテナ毎に個別のメタデータファイルを保存する。例えば、図３には３つのコンテナ（Ａ、Ｂ、Ｃ）があり、各々が対応する１つのメタデータファイルを含む。メタデータファイルはメタデータテーブルと同じ記録で構成される（チャンクのキーとコンテナ内でのチャンクの場所）。各メタデータ記録はそのコンテナの修正に合わせて更新される。
【００３３】
［ＲＡＭ限定書込みキャッシュの制限］
近年のＭＬＣ  ＮＡＮＤフラッシュの書込み耐性は、通常５ｋ〜１０ｋのプログラム削除サイクルが可能である。長年に渡り測定されたシステム寿命から考えると、ハッシュテーブルのスイープのために行われる書込みがフラッシュ装置の更新回数の上限に達しないようにするためには、RAM内にかなりの書込みキャッシュが必要となる。
【００３４】
以下の等式は、書込みキャッシュのサイズ、ＳＳＤが使用不能になる時間、およびスイープによって消費されるＳＳＤの読出し／書込み帯域幅の関係を表している。
【００３５】
【数１】
0005445682.tif 000002
【００３６】
耐久性は、ＳＳＤのフラッシュセルのプログラム削除サイクルにおける書込み耐久性である。スイープ期間は、ハッシュテーブルの各スイープ間の時間的間隔であり、新たなチャンクの書込みで書込みキャッシュ全体を満たすのに必要な時間である。ＳＳＤの寿命を延ばすために、ハッシュテーブルを保存するＳＳＤ上の領域を拡張することができ、λはこの拡張のための因数である。スイープ帯域幅は、読出しと書込みの帯域幅で、ハッシュテーブルのスイープに利用される。ＳＳＤの性能はこれらの動作によって低下する（１秒当たりのクエリー数が影響を受ける）。
【００３７】
等式（２）と（３）によれば、スイープ期間が長いほど寿命が長くなり、結果として性能の低下も少ない。しかし、等式（１）によれば、期間が長いほど大きな書込みキャッシュが必要となる。すべての書込みキャッシュはＲＡＭに保存されるため、この等式はハードウェアのトレードオフを定めている。つまり、我々は大型化／高速化／ＳＳＤ装置数の増加というコストと引き換えに、書込みキャッシュのためにＲＡＭを確保することができる。
【００３８】
上記で定めたストレージシステムの要件を見直してみる。このシステムは１２台の１ＴＢのディスクを装備し、非重複書込みに対するシステム全体の対象帯域幅は約３５０ＭＢ／秒（１時間当たり約１億６０００万チャンクの書き込み）である。ハッシュテーブルのサイズは約１６ＧＢである（容量が１５億エントリ、最大負荷率７５％、エントリサイズが８バイトと想定すると、メタデータファイルの識別子とメタデータファイル内のチャンクのオフセットに５４ビット、エントリ毎のフィルタにさらに１０ビット）。図４では、１０ｋのフラッシュを使用する寿命６年のシステムを比較している。相対的な価格を計算するために、ＲＡＭ用の１ＧＢ当たりコストはＳＳＤ用のものよりも１１倍高いと仮定した（下記（１）参照）。
（１）Ｋｉｎｇｓｔｏｎの４ＧＢ  ＥＣＣフルバッファＲＡＭとＩｎｔｅｌのＸ２５−Ｍ  ＳＳＤ  ８０ＧＢドライブとを比較
【００３９】
図４は、システムの寿命が６年だと仮定すると、書込みキャッシュに１ＧＢ近くから４ＧＢの間のＲＡＭが必要なことを示している。最初の行は、ＲＡＭにハッシュテーブル全体を保存しているシステムを示している。ＳＳＤにハッシュテーブルを保存するとハードウェアのコストが大幅に削減される。さらに、ハッシュテーブル（λ）の保存用にＳＳＤの領域を増加すると書込みキャッシュに必要なＲＡＭが減少するが、必ずしも使用するハードウェアの総コストが減少するわけではない。（ＳＳＤに空き領域がある場合はλを増やして利用することができるが、λを増やすために、ＲＡＭの追加購入の代わりにＳＳＤを追加購入しても経済的な違いはない。）メモリ消費とハードウェア全体のコストとの両方を削減するように改良した書込みキャッシュ構成を以下に提案する。他の解決策の実際のコストについては第５章で比較する。
【００４０】
［階層的書込みキャッシュ］
メモリの一部をＳＳＤに搭載することで、書込みキャッシュに必要なメモリのサイズを削減することができる。ＲＡＭ内の書込みキャッシュについては、等しいサイズのバッファをＳＳＤに配置し、このバッファを使用することで、ＲＡＭ内のキャッシュが一杯になった場合はＲＡＭ内のキャッシュのコンテンツを廃棄することができる。このようなバッファはハッシュテーブルとしても構成される。ＲＡＭ内のキャッシュとそのバッファとの両方が一杯になった場合にのみスイープを実行する。メインハッシュテーブルのスイープ数を維持したい場合は、このようなバッファを追加することでＲＡＭ内のキャッシュサイズを半分に減らすことができる。残念ながら、現在は各検索動作でのＳＳＤ上のバッファを確認する必要がある。
【００４１】
この問題を軽減するためには、このＳＳＤバッファにブルームフィルタを取り付けることができる。これにより、想定されるＳＳＤの読出しの追加を大幅に減らすことができる。この解決策を数量化するため、偽陽性率１％のブルームフィルタを使用すると仮定する。これにより、平均追加読出し数を１００分の１に減らすことができる。かかるブルームフィルタのサイズ（ビット）は、そこに保存されるエントリ数の１０倍の大きさが必要である。ハッシュテーブル内の１つのエントリのサイズは８バイトで、我々のハッシュテーブルの最高負荷率は７５％なので、このフィルタのサイズはその書込みキャッシュの約８分の１の大きさとなる。
【００４２】
このようなＳＳＤバッファ１つではなく、各々にブルームフィルタを取り付けた複数のＳＳＤバッファを使用することもできる。バッファが増えればＲＡＭ内のキャッシュサイズを小さくすることができるが、ブルームフィルタの数が多くなるためＲＡＭ消費が増加する。より多くのバッファを追加すればトータルのＲＡＭ消費は最大８分の１減らすことができる。その理由は、ＲＡＭ内の各書込みキャッシュが減少するため、この減少の１／８をブルームフィルタのＲＡＭ消費に還元する必要があるからだ。
【００４３】
ＲＡＭ内のキャッシュサイズを更に小さくするために、ＲＡＭ内の書込みキャッシュ（第１階層）と、第２階層を構成する上述の読出し専用のバッファとの上に、第３階層のキャッシュを導入することを提案する。第３階層のキャッシュもハッシュテーブルとして構成される。
【００４４】
３階層のキャッシュの構成は次の通りである（図５参照）。
１．１つの書込みキャッシュがＲＡＭ内に保存され、ｌエントリを上限として保存することができる。
２．ＳＳＤ上のｎ２の書込みキャッシュを上限として、各々がｌエントリを保存し、各々がブルームフィルタを含む。
３．ＳＳＤ上のｎ３の書込みキャッシュを上限として、各々がｌ(ｎ２＋１)エントリを保存し、ブルームフィルタは含まない。
【００４５】
入力の際、エントリはＲＡＭ内に保存される第１階層の書込みキャッシュに入力される。このキャッシュが一杯になっている場合は、第２階層の書込みキャッシュとしてＳＳＤに書き込まれ、その概要がＲＡＭ内のブルームフィルタに保存される。第２階層の書込みキャッシュの数には制限がある（ｎ２、図では制限数は４）。他のＲＡＭキャッシュの廃棄によりこの制限を超えた場合は、第１階層のキャッシュと第２階層のすべてのキャッシュが結合され第３階層のキャッシュとしてＳＳＤに書き込まれる。結合する際、第１階層と第２階層にあるすべてのエントリが新たな第３階層の書込みキャッシュに書き込まれ、第１階層と第２階層のキャッシュはクリアされる。したがって、各第３階層の書込みキャッシュは、第１階層／第２階層のキャッシュよりも（ｎ２＋１）倍大きい。結合された第１階層と第２階層のキャッシュが第３階層のキャッシュの制限（ｎ３、図では第３階層のキャッシュ数の制限は２）を超えた場合は、スイープを行う。すべてのキャッシュがスイープ領域と結合されて新たなスイープ領域が書き込まれる。
【００４６】
なお、ここでは、第２階層キャッシュ用のメモリ内ブルームフィルタを維持しているが、第３階層のキャッシュ用は維持していない。このブルームフィルタのサイズはそのキャッシュのサイズに比例し、検索の際にほぼ必ず１つの不要なＳＳＤ読出しを回避する。
【００４７】
第２階層のキャッシュは第３階層のキャッシュよりも数分の１の大きさのため、これによって第２階層のブルームフィルタがより効率的になる。
【００４８】
検索の際は、すべての書込みキャッシュを確認する必要がある。図５において、領域Ａをスイープするためには、第３階層の書込みキャッシュから２回の追加読出し、第２階層のキャッシュから最大４回の追加読出しが必要となる。この回数はブルームフィルタの偽陽性率によって決まる。また、第３階層の書込みキャッシュがなく第２階層の書込みキャッシュのみの領域Ｂをスイープするためには、追加の読出しは１回だけである。
【００４９】
［複数階層の書込みキャッシュ構成の評価］
様々な書込みキャッシュ構成の比較を、図６に示す。比較対象のすべての構成はｋ個のエントリを保存することを目的としている。偽陽性率１％のブルームフィルタを使用すると仮定する。ファクタα（alpha）は、書込みキャッシュ負荷率のオーバーヘッドを含む、１つの書込みキャッシュメタデータ記録（またはハッシュテーブルメタデータ記録）の保存に必要な領域である。
【００５０】
【数２】
0005445682.tif 000003
【００５１】
すべての階層での書込みキャッシュの最大負荷率は同じで、７５％であると仮定する。エントリサイズは８バイトに設定する。ファクタγ（gamma）は、ソリッドステート重複排除インデックス全体に保存されている総エントリ数に対する、すべての階層の書込みキャッシュに保存されるエントリ数の割合である。
【００５２】
【数３】
0005445682.tif 000004
【００５３】
本願では、γ（gamma）が約０．２（書込みキャッシュ内のエントリの５倍のエントリがハッシュテーブル内に保存されている）になると想定している。
【００５４】
第３階層の書込みキャッシュのみを使用する場合（図６の２列目）は、追加の読出し数の線形増加と引き換えに、ＲＡＭの線形減少が得られる。第２階層の書込みキャッシュのみを使用する場合（３列目）は、書込みキャッシュ用のＲＡＭは削減されるがブルームフィルタ用に追加のＲＡＭが必要となるため、総合的に見ると減少が制限される。第２階層と第３階層の書込みキャッシュの組み合わせが最も効率的である。第２階層と第３階層の書込みキャッシュによって実現されるＲＡＭの減少が乗算される（４列目）。右端の列では、３階層のキャッシュ構成でｎ２＝４、ｎ３＝２の場合に、メモリ消費が１０分の１になり、それに伴う平均コストは検索時にＳＳＤからの読出しが約１回増えるだけである。
【００５５】
［エントリの削除］
重複排除ストレージシステムからデータを削除することは重要な問題である。重複排除機能があるため、ユーザが削除を望むチャンクを本当にシステムから削除すべきかどうか判断することは難しい。そのため、システムはそのチャンクを直ちに削除せず、マークアンドスイープのガーベジコレクションと同様に、データチャンクを構築してオフライン処理として削除を実施する。削除処理はシステム全体に影響を与え、新たなシステム状態を計算するため、事実上、新たなバージョンのコンテナが計算される。ソリッドステート重複排除インデックスからエントリを削除する設計は、このアプローチにうまく適合する。
【００５６】
削除処理はコンテナレベルで実行される。マーキングの段階では、メタデータファイル内の回収するチャンクを「削除対象」としてマークするが、直ちにそのチャンクをコンテナから削除するわけではない。領域の再利用はバックグラウンド処理であり、チャンクは独立して各コンテナから回収される。回収によってコンテナが書き換えられると、「削除対象」としてマークされていないチャンクのみが残る。各コンテナには固有の識別子があり、コンテナの識別子は回収の前後で異なる。回収の際、古い識別子を「削除」としてマークすることによって、その変換のすべてをハッシュテーブルから論理的に削除する（なお、削除中にコアハッシュテーブルの状態が修正されることはない）。新たなバージョン内に存在するチャンクは、通常の入力動作を用いて（新たな識別子と共に）ハッシュテーブルに入力される。ハッシュテーブルは、ハッシュテーブルのスイープの間に古い場所（localization）から更新され、古い識別子はスイープが終了した後、再利用することができる。
【００５７】
ハッシュテーブル内に存在するエントリが、メタデータファイルから削除されることもあり得る。なぜならメタデータファイルの状態が上位にくるからである。検索の際に、そのような削除済みのエントリが発見された場合は、メタデータテーブルからの読出し後のキー検証に失敗した場合と同様に、ハッシュテーブルに戻って所定のキーの検索を継続する。すでに削除されたブロックの問い合わせを行うことは、検索時のパフォーマンスの低下（ＳＳＤからの読出しの追加）をもたらす場合がある。このようなパフォーマンスの低下は深刻なものではなく、最終的にハッシュテーブルの状態はスイープによって修正される。
【００５８】
［性能評価］
様々な解決策について、２ラックユニットボックスに搭載されるシステムを対象とすると仮定して評価する。これらのシステムは通常、ＤａｔａＤｏｍａｉｎ  ＤＤ６３０またはＮＥＣ  ＨＹＤＲＡｓｔｏｒ  ＨＳ３−２１０と同様に、データ記憶装置用に１２台の１ＴＢディスクを搭載している。
【００５９】
以下の４つの解決策を比較した。
ＤａｔａＤｏｍａｉｎ（ＤＤ）システム（非特許文献１）：偽陽性率０．３％のブルームフィルタ（２．３ＧＢのＲＡＭ）でチャンクがシステム内に存在しない場合の処理を高速化し、ストリームプリフェッチ（１ＧＢのＲＡＭ）でチャンクがシステム内に存在する場合の処理を高速化する。この解決策については第１章で詳しく述べた。
ＭｉｃｒｏｓｏｆｔのＣｈｕｎｋＳｔａｓｈ（ＣＳ）（非特許文献３）：ｃｕｃｋｏｏハッシュテーブル（１ＧＢのＲＡＭ）とストリームプリフェッチ（１ＧＢのＲＡＭ）を使用。ＳＳＤＩと同様に、ＣＳは辞書構造をハッシュテーブルとコンテナのメタデータを持つファイル（我々の解決策でのメタデータファイルに匹敵）に分割する。ハッシュテーブルをＲＡＭに保存し、メタデータファイルをＳＳＤに保存する。ハッシュテーブルのサイズを削減するためにｃｕｃｋｏｏハッシュを使用し（通常のハッシュよりも高負荷率が可能）、テーブルエントリはメタデータファイルの識別子のみを含む（ファイル内の正確なオフセットについては不明）。１５０億チャンク用のハッシュテーブルは約１０ＧＢのメモリを消費する（エントリサイズは６バイト）。
ソリッドステート重複排除インデックス（ＳＳＤＩ）：ストリームプリフェッチを使用せず、メモリ内にすべての書込みキャッシュを保存する（４ＧＢのＲＡＭ、ＳＳＤには書込みキャッシュなし）。
ソリッドステート重複排除インデックス（３階層ＳＳＤＩ）：３階層の書込みキャッシュを使用し、ｎ２＝４、ｎ３＝２（０．４ＧＢのＲＡＭ、約４ＧＢのＳＳＤ）。ストリームプリフェッチは使用しない。
【００６０】
解決策を比較するために、ディスクとＳＳＤの使用率を計算するシミュレータを実装した。シミュレータの結果と上記で説明したＳＳＤ／ＨＨＤの特徴に基づいて、各々の解決策の性能を推測した（サーバが１２台のＨｉｔａｃｈｉＵｌｔｒａｓｔａｒｔ  １ＴＢ  ７２００ＲＰＭディスクと２台のＩｎｔｅｌ  Ｘ２５−５  ＳＳＤを搭載し、最大１５億チャンクを格納できると仮定）。チャンクはＳＨＡ−２５６（下記（２）参照）で識別し、メタデータ記録のサイズは５０バイトである。ＤａｔａＤｏｍａｉｎサーバの設計にしたがって、ストレージディスク（コンテナファイルおよびメタデータファイルの両方を格納）はＲＡＩＤ−６で構成されると仮定した。この構成はディスクが２つ失われても耐えられる。ＤＤとＳＳＤＩのシミュレーションでは、メタデータファイルのサイズは１ＭＢで、ＣＳについては６４ＫＢである（下記（３）参照）。コンテナファイルは５ＭＢのチャンクにフラッシュされた（下記（４）参照）.
【００６１】
（２）チャンクの識別には任意の暗号ハッシュ関数を使用することができるが、本願ではＳＨＡ−１ではなくＳＨＡ−２５６に焦点を当てることに決定した。その理由は、ＳＨＡ−１の弱点が発見されたため、攻撃の脅威が継続的に増していくからである。しかし、我々の解決策はＳＨＡ−１でも機能する。
（３）ＣＳはメタデータファイルのオフセットを保存しないため、ＤＤ／ＳＳＤＩよりも小さなメタデータファイルを使用して読出し要求サイズを縮小する。
（４）これは楽観的な推測である。フラッシュのチャンクサイズが大きいとレイテンシも大きくなり、バックアップアプリケーションにとっては厄介である。
【００６２】
境界状態でのパフォーマンス
最初の実験では、各解決策について次の２つのテストを実行した。
新規（fresh）書込み（重複０％）
重複書込み（重複１００％、ランダムな順序の重複）
【００６３】
各テストでは、８ＫＢの複数のブロック内の計１ＴＢのデータを書き込んだ。
その結果を図７に示す。新規書込みについては、ＳＳＤＩはＤＤおよびＣＳよりもわずかに良い結果となった。その理由は、ＳＳＤＩではデータチャンクのコンテナファイルへの書込みによってディスクがほぼ完全に使用されているためである（図８参照）。ＤＤはディスク常駐型ハッシュテーブルからの読出しにもディスクを使用してブルームフィルタの偽陽性に対応するが、ＣＳはより小さなサイズのコンテナのメタデータファイルを実行するため、それらを書き込むためのディスクの使用が増加する。なお、我々の実験で測定されたＤＤに関する書込み性能は、上記（１）で述べたＤＤ６３０システムの書込み性能（１．１ＴＢ／時、つまり３２０ＭＢ／秒）とほぼ確実に一致する。
【００６４】
ランダムな重複（図７）については、ＳＳＤＩには匹敵するものがない。なお、ＳＳＤＩと比較して、３階層の書込みキャッシュによるパフォーマンスの低下はそれほど深刻ではなく（約２０％）、ランダムな重複は３階層のＳＳＤＩでも新規書込みより速く処理される。ＣＳはメタデータファイルをＲＡＭにプリフェッチし、ＤＤと同様に、次の実行時の重複の順序が保存されるという事実に依存している。ランダムな重複の場合、ヒット毎にメタデータファイル全体を読み出す必要がある。実際のところ、ランダムな重複排除の帯域幅はディスクベースの解決策よりも良いが、しかし依然として劣っている。
【００６５】
通常状態での性能
２番目の実験は、ＳＳＤＩへのメモリ内ストリームプリフェッチの実装が実現可能かどうかを判定するために行った。実際のバックアップからのデータを用いて、ストリームプリフェッチサイズが性能に与える影響を推測した。プリフェッチに保存するハッシュの数を、システム内に格納される全ハッシュの０．０５％〜４％に制限した（３２バイトのハッシュと仮定すると、ＲＡＭ消費は３７５ＭＢから３ＧＢに相当する）。この実験は、解決策がビジネスに利用できるかどうかを評価するものである。したがって、メモリ消費が多大なＣＳとＳＳＤＩは競争力がないため除外することに決定し、ＤＤと３階層ＳＳＤＩのみについて検討する（ＣＳは約１０ＧＢのＲＡＭが必要、ＳＳＤＩは約４ＧＢ。これは４００ＭＢしか必要としない３階層ＳＳＤＩより多く、またＤＤは２．３ＧＢ必要だが、より小さなブルームフィルタを使用すれば実質的に削減することができる）。
【００６６】
プリフェッチは、ＬＲＵ（ＬｅａｓｔＲｅｃｅｎｔｌｙＵｓｅｄ）読出しキャッシュとして実装された。メタデータファイルのサイズは１ＭＢで、これは１つ目の実験と同じであるが、プリフェッチのサイズは１２８ＫＢであった（各メタデータファイルは８つのプリフェッチを含む）。
【００６７】
３種類の実際のデータ群についてテストを行った。各データ群は次の一連のバックアップから構成される。
Ｗｉｋｉｐｅｄｉａ：Ｗｉｋｉｐｅｄｉａの５ヶ月分の月次バックアップで、各バックアップは約２５ＧＢ、最後のバックアップでは４０．９％が重複。
Ｍａｉｌｂｏｘｅｓ：ソフトウェア開発会社に勤務する従業員の約５０のメールボックスの、３２日分の日次バックアップ。各バックアップは約３４ＧＢ、最後のバックアップでは９４％が重複。
Ｈｏｍｅｄｉｒｓ： ＩＴ研究所に勤務する従業員約１００人のホームディレクトリの、１４週分の週次バックアップ。各バックアップは約７８ＧＢで、最後のバックアップでは９８．６％が重複。
【００６８】
バックアップのストリームは、コンテンツ指定チャンク分割（Content Defined Chunking）と言われる技術を用いてチャンクに分割された（Ｒａｂｉｎのフィンガ−プリントは入力ストリームの小さな移動ウィンドウ上で計算され、フィンガープリントが特徴的な値に達したらチャンクの境界が設定される）。平均チャンクサイズは８ＫＢであった。
【００６９】
このシーケンスの最後のバックアップの書込み性能を提示する。図９は、この結果を示している。
【００７０】
Ｗｉｋｉｐｅｄｉａは過半数が新たな書込みであり（４０．９％が重複）、これは書込み帯域幅に影響を及ぼす。プリフェッチのサイズにかかわらず、３階層ＳＳＤＩはＤＤよりも３倍近い速さである。重複の順序は保存されるが、プリフェッチされたチャンクのかなりの部分は変更され、使用されない。性能はディスク帯域幅によって制限される。３階層ＳＳＤＩは新たなデータの書込みにこの帯域幅を使用するが、ＤＤは新たなデータの書込みとメタデータファイルの読み出しの両方にこれを使用する。Ｈｏｍｅｄｉｒｓはほとんどが重複であり（９８．６％）、ここでは３階層ＳＳＤＩはＤＤよりも５倍以上速い。Ｈｏｍｅｄｉｒｓについては、性能は主にディスクとＳＳＤからメタデータファイルを読み出す帯域幅によって制限される。ＷｉｋｉｐｅｄｉａとＨｏｍｅｄｉｒｓの双方に関して、ＬＲＵのプリフェッチサイズの増加に比例する性能の向上はあまり重要ではない。
【００７１】
最も興味深い結果が観測されたのはＭａｉｌｂｏｘｅｓであった。メールボックスのバクアップは９４％が重複であったが、Ｅメールは小さなファイルに保存され、またアーカイブパリティ内のファイルの順序は、後続のバックアップの際には異なっている。これは書込みの局所性を損なう。したがって、ＤＤのパフォーマンスは非常に悪かった。３階層ＳＳＤのパフォーマンスは約２０〜３０倍優れていたが、ストリームプリフェッチのサイズはパフォーマンスに大きな影響を及ぼす。ストリームプリフェッチのサイズが０．５％よりも小さい場合は逆効果であった。１つ目の実験でわかったように、プリフェッチなしも３階層ＳＳＤＩは所定の重複率に関して４００ＭＢ／秒を上回る。小さなプリフェッチに関するパフォーマンスは低かった。その理由は、ＳＳＤからの１回の読出し要求のサイズが５１２Ｂ[5]ではなく１２８ＫＢだからである（下記（５）参照）。
【００７２】
（５）この問題はＬＲＵよりも精巧なプリフェッチアルゴリズムを使用することで解決される可能性が高いが、これは本発明の対象外である。
【００７３】
コスト評価。
様々な解決策のコストを比較するために、ＲＡＭ価格は＄３１．２５／ＧＢ（Ｋｉｎｇｓｔｏｎの４ＧＢ  ＥＣＣ、フルバッファＲＡＭが＄１２５であることに基づく）、ＳＳＤ価格は＄２．７５／ＧＢ（ＩｎｔｅｌのＸ２５−Ｍ  ＳＳＤ  ８０ＧＢドライブが＄２２０であることに基づく）と仮定した。この結果を図１０に示す。我々はストリームプリフェッチなしの解決策を比較する。３階層ＳＳＤＩはＣＳに比べて約１／２の価格だが、ＤＤよりは約４倍高い。これは残念なことのように思われるが、３階層ＳＳＤＩはＤＤよりもはるかにパフォーマンスが良く、ＳＳＤはＲＡＭよりもはるかに早いスピードで価格が低下している。我々は、３階層ＳＳＤＩおよびＣＳの全体的なコストが数年で一致すると予想している。
【００７４】
［関連技術］
インライン重複排除を高速化するためにフラッシュメモリを使用するアイデアは、ＣｈｕｎｋＳｔａｓｈ（ＣＳ）（非特許文献３）に記載されている。ＣＳについては上記で説明したが、我々の解決策よりもはるかに多くのメモリを消費し、ランダムな重複に関するパフォーマンスは我々のものよりもはるかに悪い。この文献の著者は、ハッシュテーブル内にチャンクの断片のみを保存することでハッシュテーブルのサイズを削減できる可能性があるとしているが、これは重複排除機能の信頼性を損なうことを意味する。
【００７５】
非特許文献４に記載されているシステムｄｅｄｕｐｖ１（ＤＤｖ１）も、ＳＳＤベースの構造を用いてインライン重複排除を実施している。ＤＤｖ１ではすべてのチャンクのメタデータをフラッシュベースのハッシュテーブルに直接保存する（我々の解決策とは違い、メタデータファイルは個別に保存されない）。ハッシュテーブルをインプレースで更新しない代わりに、メモリ内で修正がキャッシュされ、テーブル全体を書き換えることで、これが適用される（我々の解決策のスイープと似ているが、このテーブルはスイープ領域に分割されることはない）。一見すると、このような構成はランダムな重複をＳＳＤＩと同様に効率的に処理できるように思われる。しかし、非特許文献４はＳＳＤの限られた削除／書込耐性により発生する問題に対処しておらず、またスイープによって発生するＳＳＤのパフォーマンスの低下について研究しておらず、書込みキャッシュの保存に必要なＲＡＭの容量についても論じていない。
【００７６】
上記で述べたＳＳＤ耐性、ＳＳＤ利用率、およびＲＡＭ消費に関する説明に続いて、ここでＤＤｖ１とＳＳＤＩとを比較する。ＤＤｖ１でハッシュテーブルに保存されるエントリは、ＳＳＤＩで保存されるエントリよりもはるかに大きい。ＳＨＡ−２５６のハッシュ値については、ＤＤｖ１のエントリは約５０バイトだが、ＳＳＤＩのエントリは８バイトである。負荷率が７５％と仮定すると（ｃｕｃｋｏｏハッシュは検索時のＳＳＤの読出しを増加させるため、いずれもこのハッシュは使用できない）、ＤＤｖ１のハッシュテーブルは１００ＧＢ消費するが、ＳＳＤＩのハッシュテーブルはわずか１６ＧＢである。確かに、ＳＳＤＩはメタデータファイルを保存するため更に７５ＧＢ必要になる（ＤＤｖ１ではすべてがハッシュテーブルに含まれるため追加の領域は必要ない）。図１１は、ＳＳＤＩとＤＤｖ１を比較したものである。ハッシュテーブルが大きくなれば、スイープによるＳＳＤのパフォーマンスの低下も大きくなる。しかし、最も重要な違いは書込みキャッシュに必要なＲＡＭである。ＤＤｖ１のハッシュテーブルに保存されるエントリの方が大きいため、それに比例してＤＤｖ１の書込みキャッシュも大きくなる。全体として、ＤＤｖ１が必要なＲＡＭはＳＳＤＩが必要なＲＡＭの６倍以上である。これは特に重要である。なぜなら、２４ＧＢというのは、ディスクベースの解決策（非特許文献１，２）に必要なＲＡＭよりもはるかに大きく、またＳＳＤＩのハッシュテーブルよりも大きいため、ＤＤｖ１の有用性を低下させるからである。
【００７７】
重複識別問題に対するディスクベースの解決策は数多くあるが、そのすべてに何らかの弱点がある。まず、Ｖｅｎｔｉのシステム（非特許文献５）では、問題が認められているが解決されていない。（非特許文献１，２）に記載されている最も一般的な解決策は、メモリ内のブルームフィルタとストリームプリフェッチを使用している。ストリームプリフェッチは、重複の順序が当初の書込み時のものと異なる場合は有効に機能せず、その場合に書込み性能が著しく低下する。 
【００７８】
ＭＡＤ２（非特許文献６）は、インライン重複排除を提供するディスクベースの解決策の１つである。ハッシュ領域はタンカ（tankers）に分割され、時間的に近接して書き込まれたチャンクのハッシュ値は同じタンカに入力される。各タンカは自身のブルームフィルタを所有し、自身のチャンクが重複していると識別された場合、そのタンカはメモリにプリフェッチされる。このアプローチも重複の順序が当初の書込みの順序と同じであるという事実に依存しており、ランダムな重複については機能しない。
【００７９】
ＳｐａｒｓｅＩｎｄｅｘｉｎｇ（非特許文献７）およびＥｘｔｒｅｍｅＢｉｎｎｉｎｇ（非特許文献８）は、後続のバックアップ内のデータの類似性に依存している。これらの技術は、システムに書き込まれるチャンクのハッシュ値を、事前に書き込まれたすべてのチャンクのハッシュ値と比較するのではなく、類似するチャンクのブロックからのハッシュ値とのみ比較する。これは、過半数の重複を識別することのみを目的としているため（ランダムな重複には機能しない）、重複排除の信頼性に欠ける。
【００８０】
ディスクベースの解決策の中には、ＨａｓｈＪｏｉｎ（非特許文献９）、Ｄｅｂａｒ（非特許文献１０）、またはＤｅｃｅｎｔｒａｌｉｚｅｄＤｅｄｕｐｌｉｃａｔｉｏｎ（非特許文献１１）のように、オフラインでの重複排除を提案するものも多い。チャンクは常に新規のものとしてディスクに書き込まれ、オフラインでチェックと重複排除の処理を行う。このような解決策では、すべての重複チャンクは必要性がないにもかかわらず各バックアップ時に書き込まれることとなり、パフォーマンスに悪影響を及ぼす。
【００８１】
非特許文献１２で提案されているＡｌｐｈａｒｄは、ＳＳＤを用いて書込みインセンティブ（write-incentive）作業負荷を効率的にサポートするキー値格納装置（key-value store）を提供する。Ａｌｐｈａｒｄの設計が目指したものは我々とは違っており、ディスクベースのストレージシステム用の低レイテンシチャンク書込みキャッシュとして機能する。Ａｌｐｈａｒｄはディスクベースのシステムよりも保存するチャンクが少ないため、Ａｌｐｈａｒｄに格納されるすべてのチャンクのインデックスをＲＡＭに保存することができる。
【００８２】
ＳＳＤＩの設計は、ＤＢＭＳでのインデック作成を目的とするＰＢＦｉｌｔｅｒ（非特許文献１３，１４）がその動機となった部分がある。ＰＢＦｉｌｔｅｒはＳＳＤ上にも保存されるが、ハッシュテーブルを使用する代わりに、インデックスを追加のみのログとして構成する。ブルームフィルタを使用して書込みキャッシュを集約するというアイデアは非特許文献１５に記載されているが、キャッシュは階層的に構成されておらず、ディスク上に保存されている。
【００８３】
フラッシュデバイス上の非常に小さなブロックに効率的に書込みを行う方法に関する興味深いアイデアが非特許文献１６に記載されている。このアイデアはＳＳＤＩの設計に取り入れることもできたが、ＳＡＴＡ（ＳＳＤによく利用されている）は必要なインタフェースを持っていない。
【００８４】
［結論］
本願における研究により、２つの商用フラッシュベースＳＳＤを持つ２Ｕサーバを使用すれば、インライン重複排除時にディスクがボトルネックになる問題を解決できることがわかった。ＳＳＤＩと３階層ＳＳＤＩによって達成された結果には期待が持てる。さらに、より多くのＳＳＤドライブ、または１秒当たりのランダムな読出しを増やすことができるフラッシュベースの装置を使用し、提案した解決策とストリームプリフェッチを組み合わせることで、より優れたパフォーマンスが得られる可能性もある。
【００８５】
プライマリストレージは、バックアップやアーカイブストレージに加えて、ＳＳＤＩを適用できるもう１つの分野である。ランダムな読出しおよび書込み時における検索動作のレイテンシが低いことは、プライマリストレージの非常に大きな利点である。したがって、ＳＳＤＩはプライマリストレージの重複排除機能を可能にする主要な技術の１つになり得る。
【００８６】
＜実施形態２＞
本発明の第２の実施形態を、図１２乃至図１９を参照して説明する。図１２は、システム全体の構成を示すブロック図である。図１３は、ストレージシステムの概略を示すブロック図であり、図１４は、構成を示す機能ブロック図である。図１５乃至図１９は、ストレージシステムの動作を説明するための説明図である。
【００８７】
ここで、本実施形態では、ストレージシステムがＨＹＤＲＡｓｔｏｒといったシステムであり、複数台のサーバコンピュータが接続されて構成されている場合を説明する。但し、本発明におけるストレージシステムは、複数台のコンピュータにて構成されることに限定されず、１台のコンピュータで構成されていてもよい。
【００８８】
図１２に示すように、本発明におけるストレージシステム１０は、ネットワークＮを介してバックアップ処理を制御するバックアップシステム１１に接続している。そして、バックアップシステム１１は、ネットワークＮを介して接続されたバックアップ対象装置１２に格納されているバックアップ対象データ（記憶対象データ）を取得し、ストレージシステム１０に対して記憶するよう要求する。これにより、ストレージシステム１０は、記憶要求されたバックアップ対象データをバックアップ用に記憶する。
【００８９】
そして、図１３に示すように、本実施形態におけるストレージシステム１０は、複数のサーバコンピュータが接続された構成を採っている。具体的に、ストレージシステム１０は、ストレージシステム１０自体における記憶再生動作を制御するサーバコンピュータであるアクセラレータノード１０Ａと、データを格納する記憶装置を備えたサーバコンピュータであるストレージノード１０Ｂと、を備えている。なお、アクセラレータノード１０Ａの数とストレージノード１０Ｂの数は、図１３に示したものに限定されず、さらに多くの各ノード１０Ａ，１０Ｂが接続されて構成されていてもよい。
【００９０】
さらに、本実施形態におけるストレージシステム１０は、データを分割及び冗長化し、分散して複数の記憶装置に記憶すると共に、記憶するデータの内容に応じて設定される固有のコンテンツアドレスによって、当該データを格納した格納位置を特定するコンテンツアドレスストレージシステムである。このコンテンツアドレスストレージシステムについては、後に詳述する。
【００９１】
なお、以下では、ストレージシステム１０が１つのシステムであるとして、当該ストレージシステム１０が備えている構成及び機能を説明する。つまり、以下に説明するストレージシステム１０が有する構成及び機能は、アクセラレータノード１０Ａあるいはストレージノード１０Ｂのいずれに備えられていてもよい。なお、ストレージシステム１０は、図１３に示すように、必ずしもアクセラレータノード１０Ａとストレージノード１０Ｂとを備えていることに限定されず、いかなる構成であってもよく、例えば、１台のコンピュータにて構成されていてもよい。さらには、ストレージシステム１０は、コンテンツアドレスストレージシステムであることにも限定されない。
【００９２】
図１４に、ストレージシステム１０の構成を示す。この図に示すように、ストレージシステム１０は、一般的な情報処理装置と同様に、所定の処理を行うための作業領域である主記憶装置としてＲＡＭ３１を備えており、また、記憶対象となるバックアップ対象データ自体を記憶する第一補助記憶装置であるハードディスクドライブ３３（ＨＤＤ：Hard Disk Drive）を備えている。さらに、一般的に（例えば、比較的小さいサイズのデータの書き込みなどの一部の処理を除いて）、ＨＤＤ３３よりもアクセス速度が高速な第二補助記憶装置としてＳＳＤ（Solid State Drive）３２を備えている。なお、ＲＡＭ３１は、ＨＤＤ３３及びＳＳＤ３２よりもデータのアクセス速度が高速である。
【００９３】
また、ストレージシステム１０は、記憶対象となるデータの格納位置を管理するデータ管理部２１と、新たに記憶されるデータが既にＨＤＤ３３に記憶されているか否かを判定する重複判定部２２と、を備えている。
【００９４】
なお、実際には、上記データ管理部２１と重複判定部２２とは、図１３に示したアクセラレータノード１０Ａ及びストレージノード１０Ｂが備えているＣＰＵ（Central Processing Unit）などの複数の演算装置にプログラムが組み込まれることで構成されている。また、ＨＤＤ３３は、主にストレージノード１０Ｂが備えている記憶装置にて構成されている。
【００９５】
ここで、上記プログラムは、例えば、ＣＤ−ＲＯＭなどの記憶媒体に格納された状態でストレージシステム１０に提供される。あるいは、上記プログラムは、ネットワーク上の他のサーバコンピュータの記憶装置に記憶され、当該他のサーバコンピュータからネットワークを介してストレージシステム１０に提供されてもよい。
【００９６】
以下、上記データ管理部２１と重複判定部２２の構成について詳述する。まず、データ管理部２１は、図１６の矢印Ｙ１に示すように、ストリームデータであるバックアップ対象データＡの入力を受けると、図１５及び図１６の矢印Ｙ２に示すように、当該バックアップ対象データＡを、所定容量（例えば、６４ＫＢ）のブロックデータＤに分割する。そして、このブロックデータＤのデータ内容に基づいて、当該データ内容を代表する固有のハッシュ値Ｈ（特徴データ）を算出する（矢印Ｙ３）。例えば、ハッシュ値Ｈは、予め設定されたハッシュ関数を用いて、ブロックデータＤのデータ内容から算出する。なお、このデータ管理部２１による処理は、アクセラレータノード１０Ａにて実行される。
【００９７】
そして、上記重複判定部２２は、バックアップ対象データＡのブロックデータＤのハッシュ値Ｈを用いて、当該ブロックデータＤが既に記憶装置３０に格納されているか否かを調べる。具体的には、まず、既に格納されているブロックデータＤは、そのハッシュ値Ｈと格納位置を表すコンテンツアドレスＣＡが、関連付けてＭＦＩ（Ｍａｉｎ  Ｆｒａｇｍｅｎｔ  Ｉｎｄｅｘ）ファイルに登録されている。従って、重複判定部２２は、格納前に算出したブロックデータＤのハッシュ値ＨがＭＦＩファイル内に存在している場合には、既に同一内容のブロックデータＤが格納されていると判断できる（図１６の矢印Ｙ４）。この場合には、格納前のブロックデータＤのハッシュ値Ｈと一致したＭＦＩ内のハッシュ値Ｈに関連付けられているコンテンツアドレスＣＡを、当該ＭＦＩファイルから取得する。そして、このコンテンツアドレスＣＡを、記憶要求にかかるブロックデータＤのコンテンツアドレスＣＡとして記憶する。あるいは、既に格納されているブロックデータＤを参照するコンテンツアドレスＣＡをさらに参照する他のアドレスデータを、ツリー構造にて記憶する。これにより、このコンテンツアドレスＣＡにて参照される既に格納されているデータが、記憶要求されたブロックデータＤとして使用されることとなり、当該記憶要求にかかるブロックデータＤは記憶する必要がなくなる。なお、重複判定部２２は、実際には、ブロックデータＤのハッシュ値をさらにハッシュ計算したインデックスデータも用いて重複判定を行っているが、これについては後述する。
【００９８】
また、データ管理部２１は、は、上述したように重複判定部２２にてまだ記憶されていないと判断されたブロックデータＤを圧縮して、図１６の矢印Ｙ５に示すように、複数の所定の容量のフラグメントデータに分割する。例えば、図１５の符号Ｄ１〜Ｄ９に示すように、９つのフラグメントデータ（分割データ４１）に分割する。さらに、データ管理部２１は、分割したフラグメントデータのうちいくつかが欠けた場合であっても、元となるブロックデータを復元可能なよう冗長データを生成し、上記分割したフラグメントデータ４１に追加する。例えば、図１５の符号Ｄ１０〜Ｄ１２に示すように、３つのフラグメントデータ（冗長データ４２）を追加する。これにより、９つの分割データ４１と、３つの冗長データとにより構成される１２個のフラグメントデータからなるデータセット４０を生成する。なお、上記データ管理部２１による処理は、１つのストレージノード１０Ｂによって実行される。
【００９９】
そして、データ管理部２１は、生成されたデータセットを構成する各フラグメントデータを、ＨＤＤ３３に形成された各記憶領域に、それぞれ分散して格納する。例えば、図１５に示すように、１２個のフラグメントデータＤ１〜Ｄ１２を生成した場合には、１２個のＨＤＤ３３内にそれぞれ形成したデータ格納ファイルＦ１〜Ｆ１２（データ格納領域）に、各フラグメントデータＤ１〜Ｄ１２を１つずつそれぞれ格納する（図１６の矢印Ｙ６参照）。
【０１００】
また、データ管理部２１は、上述したようにＨＤＤ３３に格納したフラグメントデータＤ１〜Ｄ１２の格納位置、つまり、当該フラグメントデータＤ１〜Ｄ１２にて復元されるブロックデータＤの格納位置を表す、コンテンツアドレスＣＡを生成して管理する。具体的には、格納したブロックデータＤの内容に基づいて算出したハッシュ値Ｈの一部（ショートハッシュ）（例えば、ハッシュ値Ｈの先頭８Ｂ（バイト））と、論理格納位置を表す情報と、を組み合わせて、コンテンツアドレスＣＡを生成する。そして、このコンテンツアドレスＣＡを、ストレージシステム１０内のファイルシステム、つまり、アクセラレータノード１０Ａに返却する（図１６の矢印Ｙ７）。すると、アクセラレータノード１０Ａは、バックアップ対象データのファイル名などの識別情報と、コンテンツアドレスＣＡとを関連付けてファイルシステムで管理する。このとき、コンテンツアドレスＣＡは、ＳＳＤ３２に形成されたメタデータテーブル内に格納される。
【０１０１】
また、データ管理部２１は、さらに、格納したブロックデータＤの格納位置を表すコンテンツアドレスに含まれるハッシュ値（特徴データ）を参照するインデックスデータを生成して管理する。具体的には、ブロックデータＤのハッシュ値のデータ内容をさらにハッシュ計算した値をインデックスデータとして算出してハッシュテーブルに格納し、このインデックスデータにて上記ブロックデータＤのハッシュ値を参照する。ここで、上記ブロックデータＤと、ハッシュ値を含むコンテンツアドレスＣＡと、インデックスデータと、の関係を図１８に示す。
【０１０２】
以上のようにして、ＨＤＤ３３に格納されるブロックデータＤは、まず、コンテンツアドレスＣＡにて参照され、そしてこのコンテンツアドレスＣＡがハッシュテーブルのインデックスデータにて参照された状態となる。従って、上述した重複判定部２２は、新たに記憶しようとするデータを分割したブロックデータＤのハッシュ値と、このハッシュ値をさらにハッシュ計算したインデックスから辿ることができる既に記憶されているメタデータテーブルに格納されたコンテンツアドレスＣＡ内のハッシュ値と、を比較することで、重複判定を行うことができる。なお、本発明では、上記インデックスデータの格納方法に特徴を有するが、これについては後述する。
【０１０３】
また、データ管理部２１は、ブロックデータＤのコンテンツアドレスＣＡと、当該ブロックデータＤのハッシュ値Ｈと、を関連付けて、各ストレージノード１０ＢがＭＦＩファイルにて管理する。
【０１０４】
さらに、データ管理部２１は、上述したように格納したバックアップ対象データを読み出す制御を行う。例えば、ストレージシステム１０に対して、特定のファイルを指定して読み出し要求があると（図１７の矢印Ｙ１１参照）、まず、ファイルシステムに基づいて、読み出し要求にかかるファイルに対応するハッシュ値の一部であるショートハッシュと論理位置の情報からなるコンテンツアドレスＣＡを指定する（図１７の矢印Ｙ１２参照）。そして、データ管理部２１は、コンテンツアドレスＣＡがＭＦＩファイルに登録されているか否かを調べる（図１７の矢印１３参照）。登録されていなければ、要求されたデータは格納されていないため、エラーを返却する。
【０１０５】
一方、読み出し要求にかかるコンテンツアドレスＣＡが登録されている場合には、上記コンテンツアドレスＣＡにて指定される格納位置を特定し、この特定された格納位置に格納されている各フラグメントデータを、読み出し要求されたデータとして読み出す（図１７の矢印Ｙ１４参照）。このとき、各フラグメントが格納されているデータ格納ファイルＦ１〜Ｆ１２と、当該データ格納ファイルのうち１つのフラグメントデータの格納位置が分かれば、同一の格納位置から他のフラグメントデータの格納位置を特定することができる。
【０１０６】
そして、データ管理部２１は、読み出し要求に応じて読み出した各フラグメントデータからブロックデータＤを復元する（図１７の矢印Ｙ１５参照）。さらに、データ管理部２１は、復元したブロックデータＤを複数連結し、ファイルＡなどの一群のデータに復元して、読み出し制御を行っているアクセラレータノード１０Ａに返却する（図１７の矢印Ｙ１６参照）。
【０１０７】
ここで、本発明におけるデータ管理部２１は、上述したようにブロックデータＤをＨＤＤ３３に格納する際に、このブロックデータＤのハッシュ値をさらにハッシュ計算して算出したインデックデータを、図１９に示すようにＲＡＭ３１とＳＳＤ３２に格納する。これについて詳述する。
【０１０８】
まず、図１９の斜線にて示すように、レベル１段階として、ＲＡＭ３１内に１エントリを上限としインデックスデータを保存する。すると、ＲＡＭ３１内に保存されたインデックスデータの量が上限に達するため、その後さらにインデックスデータを保存する際には、既にＲＡＭ３１内に保存されているインデックスデータを、レベル２段階としてＳＳＤ３２内に保存する。同時に、ＲＡＭ３１に保存されていたインデックスデータを削除することで、ＲＡＭ３１に空きができ、新たなインデックスデータを保存する。なお、上記では、レベル１段階でＲＡＭ３１内にインデックスデータを保存する上限は、１エントリ（単位）である場合を例示したが、さらに多くの単位のインデックスデータを保存可能としてもよい。
【０１０９】
そして、ＲＡＭ３１からレベル２段階としてＳＳＤ３２にインデックスデータを保存することを、当該レベル２段階としてＳＳＤ３２に予め設定された保存量の上限となるまで繰り返す。ここでは、例えば、ｎ２個の単位のインデックスデータを格納する。このとき、レベル２段階では、斜線にて示すように、ＳＳＤ３２に保存された各インデックスデータのブルームフィルタを、それぞれＲＡＭ３１に保存する。なお、ブルームフィルタは、レベル２段階のＳＳＤ３２に保存されているインデックスデータのデータ内容に基づいて算出されたデータ（要素データ）であり、当該ＳＳＤ３２にインデックスデータが存在するか否かを高速に判定するために用いられるものである。つまり、新たに書き込まれるデータとの重複判定の際に使用される。
【０１１０】
その後、レベル２段階のＳＳＤ３２に保存されたインデックスデータが、予め設定された上限（量）であるｎ２個に達すると、このレベル２段階のＳＳＤ３２に保存されたｎ２個のインデックスデータと、ＲＡＭ３１に保存された１個のインデックスデータと、を結合する。そして、結合した（ｎ２＋１）のインデックスデータを、レベル３段階のＳＳＤ３２に格納し直す。同時に、レベル２段階のＳＳＤ３２に保存されたインデックスデータ及びＲＡＭ３１に保存されたブルームフィルタ、さらに、レベル１段階のＲＡＭ３１に保存された１個のインデックスデータを、それぞれ削除する。これにより、新たなにレベル１段階のＲＡＭ３１とレベル２段階のＳＳＤ３２に空きができ、新たなインデックスデータを保存できる。そして、上記レベル３段階のＳＳＤ３２に保存したインデックスデータが、予め設定された上限、例えば、ｎ３×（ｎ２＋１）個（単位）に達すると、全てのインデックスデータがスイープ領域に書き込まれる。
【０１１１】
なお、上記では、レベル２段階からレベル３段階のＳＳＤ３２に保存される際に、レベル２段階のＳＳＤ３２に保存されているインデックスデータに加えて、レベル１段階のＲＡＭ３１に保存しているインデックスデータを結合する場合を例示したが、ＲＡＭ３１内のインデックスデータを結合することに限定されない。つまり、レベル２段階のＳＳＤ３２に保存されている複数個（単位）のインデックスデータのみを結合して、レベル３段階としてもよい。また、上記では、レベル２段階のＳＳＤ３２に保存されるインデックスデータのブルームフィルタをＲＡＭ３１内に保存する場合を例示したが、ブルームフィルタは必ずしも保存しなくてもよい。
【０１１２】
＜付記＞
上記実施形態の一部又は全部は、以下の付記のようにも記載されうる。以下、本発明におけるストレージシステム１００（図２０参照）、プログラムを記憶した記憶媒体、データ管理方法の構成の概略を説明する。但し、本発明は、以下の構成に限定されない。
【０１１３】
（付記１）
記憶対象データを格納する第一補助記憶装置１１３と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置１１２と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置１１１と、を備え、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部１０１と、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部１０２と、を備え、
前記データ管理部１０１は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、
ストレージシステム１００。
【０１１４】
（付記２）
付記１に記載のストレージシステムであって、
前記データ管理部は、前記第二補助記憶装置に記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合して当該第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置から削除する、
ストレージシステム。
【０１１５】
（付記３）
付記２に記載のストレージシステムであって、
前記データ管理部は、前記第二補助記憶装置に記憶保持されている前記複数単位のインデックスデータと前記主記憶装置に記憶保持されている前記インデックスデータとを結合して前記第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置及び前記主記憶装置から削除する、
ストレージシステム。
【０１１６】
（付記４）
付記２に記載のストレージシステムであって、
前記データ管理部は、前記第二補助記憶装置に記憶された前記インデックスデータが存在するか否かを判定するために用いられる当該インデックスデータのデータ内容に基づく要素データを、前記主記憶装置に記憶する、
ストレージシステム。
【０１１７】
（付記５）
付記４に記載のストレージシステムであって、
前記データ管理部は、前記第二補助記憶装置に記憶された前記インデックスデータをまとめて当該第二補助記憶装置に記憶し直す際に、前記主記憶装置に記憶された前記インデックスデータの前記要素データを解放する、
ストレージシステム。
【０１１８】
（付記６）
付記１に記載のストレージシステムであって、
前記第一補助記憶装置はハードディスクドライブであり、前記第二補助記憶装置はＳＳＤ（Solid State Drive）である、
ストレージシステム。
【０１１９】
（付記７）
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えた情報処理装置に、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を実現させると共に、
前記データ管理部は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、
ことを実現させるためのプログラムを記憶した記憶媒体。
【０１２０】
（付記８）
付記７に記載のプログラムを記憶した記憶媒体であって、
前記データ管理部は、前記第二補助記憶装置に記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合して当該第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置から削除する、
プログラムを記憶した記憶媒体。
【０１２１】
（付記９）
記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えたストレージシステムにて、
記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照することにより、記憶対象データを管理し、
新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定すると共に、
記憶対象データを管理する際に、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、
データ管理方法。
【０１２２】
（付記１０）
付記９に記載のデータ管理方法であって、
記憶対象データを管理する際に、前記第二補助記憶装置に記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合して当該第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置から削除する、
データ管理方法。
【図１】
0005445682.tif 000005
【図２】
0005445682.tif 000006
【図３】
0005445682.tif 000007
【図４】
0005445682.tif 000008
【図５】
0005445682.tif 000009
【図６】
0005445682.tif 000010
【図７】
0005445682.tif 000011
【図８】
0005445682.tif 000012
【図９】
0005445682.tif 000013
【図１０】
0005445682.tif 000014
【図１１】
0005445682.tif 000015
【図１２】
0005445682.tif 000016
【図１３】
0005445682.tif 000017
【図１４】
0005445682.tif 000018
【図１５】
0005445682.tif 000019
【図１６】
0005445682.tif 000020
【図１７】
0005445682.tif 000021
【図１８】
0005445682.tif 000022
【図１９】
0005445682.tif 000023
【図２０】
0005445682.tif 000024