(57)【要約】【課題】読み出し要求に対する応答速度を向上すること。【解決手段】データが格納される記憶装置３０及び該データの一時記憶領域として利用されるキャッシュ装置４０に接続されたストレージ装置２０であって、記憶装置３０に格納されたデータの記憶場所と該データの内容に関する内容情報とを対応付ける場所情報２１ｂと、キャッシュ装置４０に格納されたデータに対応する内容情報を含むキャッシュ情報２１ａと、を記憶する記憶部２１と、記憶場所を指定してデータの読み出しを要求する読み出し要求ＲＱを受け付けたとき、該読み出し要求ＲＱで指定された記憶場所に対応する内容情報を特定し、該内容情報がキャッシュ情報２１ａに含まれる場合には該データをキャッシュ装置４０から読み出して応答する制御部２２とを有する、ストレージ装置２０が提供される。【選択図】図１
2016126632.tif 000002
【特許請求の範囲】
【請求項１】
データが格納される記憶装置及び該データの一時記憶領域として利用されるキャッシュ装置に接続されたストレージ装置であって、
前記記憶装置に格納されたデータの記憶場所と該データの内容に関する内容情報とを対応付ける場所情報と、前記キャッシュ装置に格納されたデータに対応する前記内容情報を含むキャッシュ情報と、を記憶する記憶部と、
前記記憶場所を指定してデータの読み出しを要求する読み出し要求を受け付けたとき、該読み出し要求で指定された前記記憶場所に対応する前記内容情報を特定し、該内容情報が前記キャッシュ情報に含まれる場合には該データを前記キャッシュ装置から読み出して応答する制御部と
を有する、ストレージ装置。
【請求項２】
前記制御部は、同じ内容のデータが同じ位置に格納される論理的なデータ格納領域と、該データ格納領域におけるデータの格納位置を管理する情報が含まれる情報領域とを有する管理領域を用いて、前記記憶装置に格納されるデータを管理し、
前記場所情報は、前記データの記憶場所と、該データに対応する前記内容情報及び前記管理領域と、を対応付け、
前記キャッシュ情報は、前記データに対応する前記内容情報と、該データに対応する前記管理領域と、を対応付け、
前記制御部は、前記内容情報と前記管理領域との組に基づいて、該組に対応するデータを前記キャッシュ装置から読み出して応答するかを判断する
請求項１に記載のストレージ装置。
【請求項３】
前記情報領域は、前記データの格納位置を管理する情報がデータ毎に格納される複数の小領域を含み、
前記場所情報は、前記データの記憶場所と、該データに対応する前記内容情報、該データに対応する前記管理領域及び前記小領域と、を対応付け、
前記キャッシュ情報は、前記データに対応する前記内容情報と、該データに対応する前記管理領域及び前記小領域と、を対応付け、
前記制御部は、前記内容情報と前記管理領域と前記小領域の組に基づいて、該組に対応するデータを前記キャッシュ装置から読み出して応答するかを判断する
請求項２に記載のストレージ装置。
【請求項４】
前記記憶装置には複数の記憶領域が設定されており、
前記制御部は、複数の前記管理領域のうち第１の管理領域に格納されたデータの中でアクセス頻度が基準値より大きいデータを前記第１の管理領域とは異なる第２の管理領域にコピーし、前記第１の管理領域を削除し、前記場所情報及び前記キャッシュ情報を更新する
請求項２又は３に記載のストレージ装置。
【請求項５】
データが格納される記憶装置と、該データの一時記憶領域として利用されるキャッシュ装置と、前記記憶装置及び前記キャッシュ装置に接続されたストレージ装置と、前記ストレージ装置に接続されたホスト装置と、を含み、
前記ホスト装置は、
前記記憶装置に格納されたデータの記憶場所を指定して該データの読み出しを要求する読み出し要求を前記ストレージ装置に送信し、
前記ストレージ装置は、
前記ホスト装置からの前記読み出し要求を受け付け、記憶部から、前記記憶装置に格納されたデータの記憶場所と該データの内容に関する内容情報とを対応付ける場所情報と、前記キャッシュ装置に格納されたデータに対応する前記内容情報を含むキャッシュ情報と、を取得し、前記読み出し要求で指定された前記記憶場所に対応する前記内容情報を特定し、該内容情報が前記キャッシュ情報に含まれる場合には該データを前記キャッシュ装置から読み出して前記ホスト装置に応答する
ストレージシステム。
【請求項６】
データが格納される記憶装置と、該データの一時記憶領域として利用されるキャッシュ装置と、前記記憶装置及び前記キャッシュ装置に接続されたストレージ装置と、前記ストレージ装置に接続されたホスト装置と、を含むストレージシステムにおけるデータ読み出し方法であって、
前記ホスト装置が、
前記記憶装置に格納されたデータの記憶場所を指定して該データの読み出しを要求する読み出し要求を前記ストレージ装置に送信し、
前記ストレージ装置が、
前記ホスト装置からの前記読み出し要求を受け付け、記憶部から、前記記憶装置に格納されたデータの記憶場所と該データの内容に関する内容情報とを対応付ける場所情報と、前記キャッシュ装置に格納されたデータに対応する前記内容情報を含むキャッシュ情報と、を取得し、前記読み出し要求で指定された前記記憶場所に対応する前記内容情報を特定し、該内容情報が前記キャッシュ情報に含まれる場合には該データを前記キャッシュ装置から読み出して前記ホスト装置に応答する
データ読み出し方法。
【請求項７】
データが格納される記憶装置及び該データの一時記憶領域として利用されるキャッシュ装置に接続されたコンピュータに、
記憶部から、前記記憶装置に格納されたデータの記憶場所と該データの内容に関する内容情報とを対応付ける場所情報と、前記キャッシュ装置に格納されたデータに対応する前記内容情報を含むキャッシュ情報と、を取得し、
前記記憶場所を指定してデータの読み出しを要求する読み出し要求を受け付けたとき、該読み出し要求で指定された前記記憶場所に対応する前記内容情報を特定し、該内容情報が前記キャッシュ情報に含まれる場合には該データを前記キャッシュ装置から読み出して応答する
処理を実行させる、ストレージプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージ装置、ストレージシステム、データ読み出し方法、及びストレージプログラムに関する。
【背景技術】
【０００２】
ＨＤＤ（Hard Disk Drive）などの記録媒体を複数接続し、ＲＡＩＤ（Redundant Arrays of Inexpensive Disks）技術などを利用して冗長化したディスクアレイと、ディスクアレイを制御するストレージ装置とを含むストレージシステムが広く利用されている。ストレージ装置は、仮想的な記憶領域（仮想ボリューム）をディスクアレイ上の記憶領域（物理ボリューム）に割り当て、仮想ボリュームを介してデータの読み出し処理及び書き込み処理を制御する。
【０００３】
ストレージ装置は、１つの仮想ボリュームを複数の論理ボリュームに分割し、論理ボリュームを単位としてデータを管理することがある。また、ストレージ装置は、論理ボリュームとは異なる論理的なデータ格納領域（コンテナ）を設定し、コンテナを利用してデータを管理することがある。なお、コンテナは、チャンクと呼ばれることもある。
【０００４】
上記のようなストレージシステムにおいて、複数の記憶領域に同じデータが重複して格納されている場合に、一部の記憶領域に重複して格納されているデータを除去して記憶領域の空き容量を増加させる技術（重複除去）がある。重複除去を実施することで、ディスクアレイの記憶領域を効率良く利用することができる。
【０００５】
なお、オンラインストレージサービスにデータをアップロードするシステムにおいて、アップロードの対象を複数の構成ブロックで管理し、構成ブロックの重複を排除した上でアップロードを実施する技術が提案されている。このシステムは、構成ブロックの重複度を示す参照カウントを利用して重複排除を実現する。また、ハッシュコードを付したデータを論理ボリュームに記憶しておき、重複除去の際に、ハッシュコードを比較して重複データを検出する技術が提案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１２−１４１７３８号公報
【特許文献２】特開２００９−２５１７２５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ストレージシステムは、データの読み出し要求に応じてストレージ装置がディスクアレイから読み出したデータを一時的に記憶するキャッシュ装置を含むことがある。キャッシュ装置は、ディスクアレイに比べてデータの読み出し速度が速い。そのため、ストレージ装置は、データの読み出し要求に応じてキャッシュ装置に格納されているデータを応答できれば、応答時間を短縮することができる。
【０００８】
読み出し処理の対象となるデータは、読み出し要求の中で指定されているデータの記憶場所（論理ボリューム上のアドレスなど）に基づいてストレージ装置が特定する。つまり、ストレージ装置は、異なる論理ボリュームに格納されているが、内容は同じ複数のデータをそれぞれ区別する。そのため、これまでのストレージ装置は、読み出し処理の対象となるデータと同じ内容のデータがキャッシュ装置にあっても、両データの記憶場所が異なる場合にはディスクアレイからデータを読み出して応答していた。
【０００９】
これに対し、読み出し要求の中で指定されているデータとは記憶場所が異なるけれど同じ内容を有するデータがキャッシュ装置にある場合に、そのデータを読み出して応答することができれば、読み出し要求に対して高速に応答できる機会が増加する。その結果、ストレージシステムの性能向上が期待できる。
【００１０】
そこで、１つの側面によれば、本発明の目的は、読み出し要求に対する応答速度を向上することが可能なストレージ装置、ストレージシステム、データ読み出し方法、及びストレージプログラムを提供することにある。
【課題を解決するための手段】
【００１１】
本開示の１つの側面によれば、データが格納される記憶装置及び該データの一時記憶領域として利用されるキャッシュ装置に接続されたストレージ装置が提供される。このストレージ装置は、記憶装置に格納されたデータの記憶場所と該データの内容に関する内容情報とを対応付ける場所情報と、キャッシュ装置に格納されたデータに対応する内容情報を含むキャッシュ情報と、を記憶する記憶部と、記憶場所を指定してデータの読み出しを要求する読み出し要求を受け付けたとき、該読み出し要求で指定された記憶場所に対応する内容情報を特定し、該内容情報がキャッシュ情報に含まれる場合には該データをキャッシュ装置から読み出して応答する制御部とを有する。
【発明の効果】
【００１２】
本発明によれば、読み出し要求に対する応答速度が向上する。
【図面の簡単な説明】
【００１３】
【図１】第１実施形態に係るストレージシステムの一例を示した図である。
【図２】第２実施形態に係るストレージシステムの一例を示した図である。
【図３】第２実施形態に係るホスト装置の機能を実現可能なハードウェアの一例を示した図である。
【図４】第２実施形態に係る制御装置が有する機能の一例を示したブロック図である。
【図５】第２実施形態に係るコンテナ情報について説明するための第１の図である。
【図６】第２実施形態に係るコンテナ情報について説明するための第２の図である。
【図７】第２実施形態に係るコンテナ情報について説明するための第３の図である。
【図８】第２実施形態に係るブロックマップについて説明するための図である。
【図９】第２実施形態に係るハッシュテーブルについて説明するための図である。
【図１０】第２実施形態に係るリード処理の流れを示した第１のフロー図である。
【図１１】第２実施形態に係るリード処理の流れを示した第２のフロー図である。
【図１２】第２実施形態に係る新規レコードの登録処理の流れを示したフロー図である。
【図１３】第２実施形態に係るライト処理の流れを示した第１のフロー図である。
【図１４】第２実施形態に係るライト処理の流れを示した第２のフロー図である。
【図１５】第２実施形態に係るインクリメント処理の流れを示したフロー図である。
【図１６】第２実施形態に係るデクリメント処理の流れを示したフロー図である。
【図１７】第２実施形態に係るＧＣ処理の流れを示したフロー図である。
【図１８】第２実施形態の一変形例に係るキャッシュ情報について説明するための図である。
【図１９】第２実施形態の一変形例に係るブロックマップについて説明するための図である。
【発明を実施するための形態】
【００１４】
以下に添付図面を参照しながら、本発明の実施形態について説明する。なお、本明細書及び図面において実質的に同一の機能を有する要素については、同一の符号を付することにより重複説明を省略する場合がある。
【００１５】
＜１．第１実施形態＞
図１を参照しながら、第１実施形態について説明する。図１は、第１実施形態に係るストレージシステムの一例を示した図である。図１に示したストレージシステム５は、第１実施形態に係るストレージシステムの一例である。
【００１６】
図１に示すように、ストレージシステム５は、ホスト装置１０、ストレージ装置２０、記憶装置３０、及びキャッシュ装置４０を有する。
ホスト装置１０は、記憶装置３０に格納されたデータの読み出し処理や、記憶装置３０に対するデータの書き込み処理をストレージ装置２０に要求するコンピュータである。
【００１７】
ストレージ装置２０は、ホスト装置１０、記憶装置３０、及びキャッシュ装置４０に接続されている。ストレージ装置２０は、ホスト装置１０から受けたデータの読み出し要求に応じて、読み出し対象のデータをホスト装置１０に応答する。また、ストレージ装置２０は、ホスト装置１０から受けたデータの書き込み要求に応じて、書き込み対象のデータを記憶装置３０に格納する。
【００１８】
記憶装置３０は、ＨＤＤやＳＳＤ（Solid State Drive）などの記録媒体を有する装置である。例えば、複数のＨＤＤを接続し、ＲＡＩＤ技術を利用して冗長化したディスクアレイは、記憶装置３０の一例である。
【００１９】
キャッシュ装置４０は、記録媒体として、ＨＤＤやＳＳＤなどの不揮発性メモリや、ＤＲＡＭ（Dynamic Random Access Memory）などの揮発性メモリを有し、データの読み出し速度が記憶装置３０より高速な装置である。キャッシュ装置４０は、記憶装置３０から読み出されたデータを一時的に格納する一時記憶領域としてストレージ装置２０により利用される。なお、キャッシュ装置４０は、ストレージ装置２０と一体に形成されていてもよい。
【００２０】
ストレージ装置２０は、記憶部２１及び制御部２２を有する。
記憶部２１は、ＲＡＭ（Random Access Memory）などの揮発性記憶装置、或いは、ＨＤＤやフラッシュメモリなどの不揮発性記憶装置である。制御部２２は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサである。但し、制御部２２は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの電子回路であってもよい。制御部２２は、例えば、記憶部２１又は他のメモリに記憶されたプログラムを実行する。
【００２１】
記憶部２１は、キャッシュ装置４０に格納されたデータに対応する内容情報を含むキャッシュ情報２１ａを記憶する。内容情報は、例えば、データのフィンガープリントである。フィンガープリントとしては、例えば、ハッシュ値が利用される。
【００２２】
ハッシュ値は、例えば、ＳＨＡ（Secure Hash Algorithm）−１やＭＤ５（Message Digest Algorithm 5）などのハッシュ関数を利用して計算できる。ＳＨＡ−１は１６０ビットのハッシュ値を出力する。ＭＤ５は１２８ビットのハッシュ値を出力する。図１の例では、データｄのハッシュ値がｆｐ（ｄ）と表現されている。
【００２３】
記憶部２１は、記憶装置３０に格納されたデータの記憶場所と該データの内容に関する内容情報とを対応付ける場所情報２１ｂを記憶する。データの記憶場所は、例えば、記憶装置３０を対象に設定された論理ボリュームのアドレスなどである。
【００２４】
制御部２２は、記憶場所を指定してデータの読み出しを要求する読み出し要求ＲＱをホスト装置１０から受け付けたとき、場所情報２１ｂを参照し、該読み出し要求ＲＱで指定された記憶場所に対応する内容情報を特定する。そして、制御部２２は、キャッシュ情報２１ａを参照し、特定した内容情報がキャッシュ情報２１ａに含まれる場合には該データをキャッシュ装置４０から読み出して応答する。
【００２５】
図１の例は、記憶場所ＡＤＲ１、ＡＤＲ３にそれぞれデータＤ１が格納され、記憶場所ＡＤＲ２にデータＤ２が格納された状況を示している。なお、図１（Ｃ）にある表記「Ｄ１＠ＡＤＲ１」は、記憶場所ＡＤＲ１に格納されているデータＤ１を示す。「Ｄ２＠ＡＤＲ２」、「Ｄ１＠ＡＤＲ３」についても同様である。また、図１の例では、キャッシュ装置４０にデータＤ１がキャッシュされている。このデータＤ１は、過去に記憶場所ＡＤＲ１から読み出された際にキャッシュされたものである。
【００２６】
この場合、図１（Ａ）に示すように、記憶部２１は、データＤ１と、データＤ１の内容情報ｆｐ（Ｄ１）とを対応付けるキャッシュ情報２１ａを有する。また、記憶部２１は、記憶場所ＡＤＲ１と内容情報ｆｐ（Ｄ１）、記憶場所ＡＤＲ２と内容情報ｆｐ（Ｄ２）、及び、記憶場所ＡＤＲ３と内容情報ｆｐ（Ｄ１）をそれぞれ対応付ける場所情報２１ｂを有する。
【００２７】
ケース（１）：制御部２２は、場所情報ＡＤＲ１を指定する読み出し要求ＲＱをホスト装置１０から受け付けた場合（図１（Ｂ）（１））、場所情報２１ｂから記憶場所ＡＤＲ１に対応する内容情報ｆｐ（Ｄ１）を特定する。そして、制御部２２は、キャッシュ情報２１ａに内容情報ｆｐ（Ｄ１）があるか判定する。この例ではキャッシュ情報２１ａに内容情報ｆｐ（Ｄ１）が含まれるため、制御部２２は、内容情報ｆｐ（Ｄ１）に対応するデータＤ１をキャッシュ装置４０から読み出し、データＤ１を含む応答ＲＰをホスト装置１０に返す。
【００２８】
ケース（２）：制御部２２は、場所情報ＡＤＲ２を指定する読み出し要求ＲＱをホスト装置１０から受け付けた場合（図１（Ｂ）（２））、場所情報２１ｂから記憶場所ＡＤＲ２に対応する内容情報ｆｐ（Ｄ２）を特定する。そして、制御部２２は、キャッシュ情報２１ａに内容情報ｆｐ（Ｄ２）があるか判定する。この例ではキャッシュ情報２１ａに内容情報ｆｐ（Ｄ２）が含まれないため、制御部２２は、場所情報ＡＤＲ２をもとに記憶装置３０からデータＤ２を読み出し、データＤ２を含む応答ＲＰをホスト装置１０に返す。
【００２９】
ケース（３）：制御部２２は、場所情報ＡＤＲ３を指定する読み出し要求ＲＱをホスト装置１０から受け付けた場合（図１（Ｂ）（３））、場所情報２１ｂから記憶場所ＡＤＲ３に対応する内容情報ｆｐ（Ｄ１）を特定する。そして、制御部２２は、キャッシュ情報２１ａに内容情報ｆｐ（Ｄ１）があるか判定する。この例ではキャッシュ情報２１ａに内容情報ｆｐ（Ｄ１）が含まれるため、制御部２２は、内容情報ｆｐ（Ｄ１）に対応するデータＤ１をキャッシュ装置４０から読み出し、データＤ１を含む応答ＲＰをホスト装置１０に返す。
【００３０】
上記のキャッシュ情報２１ａ及び場所情報２１ｂを利用することで、制御部２２は、上記ケース（３）のように、記憶場所は異なるが同じ内容のキャッシュ済みデータを用いてホスト装置１０に応答することができる（図１の符号ａ）。そのため、記憶装置３０からデータを読み出してホスト装置１０に応答する場合（図１の符号ｂ）に比べ、読み出し時間が短くなる分だけ読み出し要求ＲＱから応答ＲＰまでの時間が短縮される。つまり、ストレージシステム５の性能が向上する。
【００３１】
以上、第１実施形態について説明した。
＜２．第２実施形態＞
次に、第２実施形態について説明する。
【００３２】
［２−１．システム］
第２実施形態に係るストレージシステムについて説明する。図２は、第２実施形態に係るストレージシステムの一例を示した図である。
【００３３】
図２に示すように、第２実施形態に係るストレージシステムは、ホスト装置１００、制御装置２００、及び記憶装置３００を有する。
ホスト装置１００は、ネットワークを介して制御装置２００に接続されている。ネットワークは、有線又は無線の通信回線を組み合わせた通信網である。ホスト装置１００は、記憶装置３００に格納されたデータの読み出し処理や、記憶装置３００に対するデータの書き込み処理を制御装置２００に要求するコンピュータである。
【００３４】
制御装置２００は、キャッシュ装置２１０及び記憶装置３００に接続されている。制御装置２００は、ホスト装置１００から受けたデータの読み出し要求に応じて、読み出し対象のデータをホスト装置１００に応答する。また、制御装置２００は、ホスト装置１００から受けたデータの書き込み要求に応じて、書き込み対象のデータを記憶装置３００に格納する。
【００３５】
キャッシュ装置２１０は、記録媒体として、ＨＤＤやＳＳＤなどの不揮発性メモリや、ＤＲＡＭなどの揮発性メモリを有し、データの読み出し速度が記憶装置３００より高速な装置である。キャッシュ装置２１０は、記憶装置３００から読み出されたデータを一時的に格納する一時記憶領域として制御装置２００により利用される。なお、キャッシュ装置２１０は、制御装置２００と一体に形成されていてもよい。
【００３６】
記憶装置３００は、管理装置３１０、ディスク３２０ａ、３２０ｂ、３２０ｃ、３２０ｄ、及びキャッシュディスク３３０を有する。ディスク３２０ａ、３２０ｂ、３２０ｃ、３２０ｄは、ＨＤＤやＳＳＤなどの記録媒体である。また、ディスク３２０ａ、３２０ｂ、３２０ｃ、３２０ｄは相互に接続されている。キャッシュディスク３３０は、高速なアクセス性能を有する記録媒体（ＨＤＤやＳＳＤなどの不揮発性メモリや、ＤＲＡＭなどの揮発性メモリ）である。
【００３７】
管理装置３１０は、ディスク３２０ａ、３２０ｂ、３２０ｃ、３２０ｄの動作を制御し、ディスク３２０ａ、３２０ｂ、３２０ｃ、３２０ｄの組をディスクアレイとして動作させる。また、管理装置３１０は、ディスクアレイから読み出したデータをキャッシュディスク３３０にキャッシュし、制御装置２００から同じデータに対する読み出し要求を受けた場合にキャッシュディスク３３０から読み出したデータを制御装置２００に応答する。
【００３８】
以上、第２実施形態に係るストレージシステムについて説明した。説明の都合上、以下では図２に例示したストレージシステムを想定して説明を進めるが、第２実施形態に係る技術を適用可能なストレージシステムは図２の例に限定されない。例えば、ホスト装置１００と制御装置２００とが直接接続されていてもよいし、キャッシュディスク３３０が省略されていてもよい。このような変形例も第２実施形態の技術的範囲に属する。
【００３９】
［２−２．ハードウェア］
ここで、図３を参照しながら、ホスト装置１００の機能を実現可能なハードウェアについて説明する。図３は、第２実施形態に係るホスト装置の機能を実現可能なハードウェアの一例を示した図である。
【００４０】
ホスト装置１００が有する機能は、例えば、図３に示す情報処理装置のハードウェア資源を用いて実現することが可能である。つまり、ホスト装置１００が有する機能は、コンピュータプログラムを用いて図３に示すハードウェアを制御することにより実現される。
【００４１】
図３に示すように、このハードウェアは、主に、ＣＰＵ９０２と、ＲＯＭ（Read Only Memory）９０４と、ＲＡＭ９０６と、ホストバス９０８と、ブリッジ９１０とを有する。さらに、このハードウェアは、外部バス９１２と、インターフェース９１４と、入力部９１６と、出力部９１８と、記憶部９２０と、ドライブ９２２と、接続ポート９２４と、通信部９２６とを有する。
【００４２】
ＣＰＵ９０２は、例えば、演算処理装置又は制御装置として機能し、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ＲＯＭ９０４は、ＣＰＵ９０２に読み込まれるプログラムや演算に用いるデータなどを格納する記憶装置の一例である。ＲＡＭ９０６には、例えば、ＣＰＵ９０２に読み込まれるプログラムや、そのプログラムを実行する際に変化する各種パラメータなどが一時的又は永続的に格納される。
【００４３】
これらの要素は、例えば、高速なデータ伝送が可能なホストバス９０８を介して相互に接続される。一方、ホストバス９０８は、例えば、ブリッジ９１０を介して比較的データ伝送速度が低速な外部バス９１２に接続される。また、入力部９１６としては、例えば、マウス、キーボード、タッチパネル、タッチパッド、ボタン、スイッチ、及びレバーなどが用いられる。さらに、入力部９１６としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラが用いられることもある。
【００４４】
出力部９１８としては、例えば、ＣＲＴ（Cathode Ray Tube）、ＬＣＤ（Liquid Crystal Display）、ＰＤＰ（Plasma Display Panel）、又はＥＬＤ（Electro-Luminescence Display）などのディスプレイ装置が用いられる。また、出力部９１８として、スピーカやヘッドホンなどのオーディオ出力装置、又はプリンタなどが用いられることもある。つまり、出力部９１８は、情報を視覚的又は聴覚的に出力することが可能な装置である。
【００４５】
記憶部９２０は、各種のデータを格納するための装置である。記憶部９２０としては、例えば、ＨＤＤなどの磁気記憶デバイスが用いられる。また、記憶部９２０として、ＳＳＤやＲＡＭディスクなどの半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイスなどが用いられてもよい。
【００４６】
ドライブ９２２は、着脱可能な記録媒体であるリムーバブル記録媒体９２８に記録された情報を読み出し、又はリムーバブル記録媒体９２８に情報を書き込む装置である。リムーバブル記録媒体９２８としては、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリなどが用いられる。
【００４７】
接続ポート９２４は、例えば、ＵＳＢ（Universal Serial Bus）ポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ（Small Computer System Interface）、ＲＳ−２３２Ｃポート、又は光オーディオ端子など、外部接続機器９３０を接続するためのポートである。外部接続機器９３０としては、例えば、プリンタなどが用いられる。
【００４８】
通信部９２６は、ネットワーク９３２に接続するための通信デバイスである。通信部９２６としては、例えば、有線又は無線ＬＡＮ（Local Area Network）用の通信回路、ＷＵＳＢ（Wireless USB）用の通信回路、光通信用の通信回路やルータ、ＡＤＳＬ（Asymmetric Digital Subscriber Line）用の通信回路やルータ、携帯電話ネットワーク用の通信回路などが用いられる。通信部９２６に接続されるネットワーク９３２は、有線又は無線により接続されたネットワークであり、例えば、インターネット、ＬＡＮ、放送網、衛星通信回線などを含む。
【００４９】
以上、ホスト装置１００の機能を実現可能なハードウェアについて説明した。制御装置２００及び管理装置３１０が有する機能も図３に例示したハードウェアを利用して実現することができる。そのため、制御装置２００及び管理装置３１０のハードウェアについては説明を省略する。
【００５０】
［２−３．機能］
次に、図４〜図９を参照しながら、制御装置２００の機能について説明する。
図４は、第２実施形態に係る制御装置が有する機能の一例を示したブロック図である。
【００５１】
図４に示すように、制御装置２００は、記憶部２０１、Ｉ／Ｏ制御部２０２、ＦＰ算出部２０３、ＢＭ管理部２０４、ＲＣ制御部２０５、及びコンテナ制御部２０６を有する。
なお、記憶部２０１の機能は、上述したＲＡＭ９０６や記憶部９２０などを用いて実現できる。Ｉ／Ｏ制御部２０２、ＦＰ算出部２０３、ＢＭ管理部２０４、ＲＣ制御部２０５、及びコンテナ制御部２０６の機能は、上述したＣＰＵ９０２などを用いて実現できる。
【００５２】
記憶部２０１は、コンテナ情報２０１ａ、ブロックマップ２０１ｂ、及びハッシュテーブル２０１ｃを有する。以下、これらの情報について説明する。
（コンテナ情報）
まず、図５〜図７を参照しながら、コンテナ情報２０１ａについて説明する。
【００５３】
図５は、第２実施形態に係るコンテナ情報について説明するための第１の図である。図６は、第２実施形態に係るコンテナ情報について説明するための第２の図である。図７は、第２実施形態に係るコンテナ情報について説明するための第３の図である。
【００５４】
図５に示すように、制御装置２００は、仮想的な記憶領域（仮想ボリューム）をディスクアレイ上の記憶領域（物理ボリューム）に割り当て、仮想ボリュームを介してデータの読み出し処理及び書き込み処理を制御する。また、制御装置２００は、１つの仮想ボリュームを複数の論理ボリュームに分割し、論理ボリュームを単位としてデータを管理する。図５の例では、論理ボリューム＃１、＃２が設定されている。なお、第２実施形態では、重複除去の対象となる論理ボリュームを想定している。
【００５５】
また、制御装置２００は、論理ボリュームとは異なる論理的なデータ格納領域（コンテナ）を設定し、コンテナを利用してデータを管理する。各コンテナは、コンテナＩＤ（ＣｉＤ）を用いて識別される。図５の例では、ＣｉＤがＣｉＤ１、ＣｉＤ２、ＣｉＤ３のコンテナが設定されている。
【００５６】
各コンテナは、インデックス領域と、実データ格納領域とを有する。実データ格納領域は、データが格納される記憶領域である。実データ格納領域には、圧縮後のデータが格納されてもよい。インデックス領域は、実データ格納領域に格納されたデータに関する情報が格納される記憶領域である。インデックス領域は、図６に示すように、複数の小領域（スロット）に分割されている。各スロットは、スロットＩＤ（ＳｉＤ）を用いて識別される。
【００５７】
各スロットは、実データ格納領域に格納される個々のデータに対応する。また、スロットは、オフセット、フィンガープリント、及びカウンタ値が格納される。オフセットは、実データ格納領域におけるデータの格納位置を示す。フィンガープリントは、実データ格納領域に格納されたデータの内容に関する情報である。例えば、フィンガープリントは、ＳＨＡ−１やＭＤ５などのハッシュ関数にデータを入力して計算したハッシュ値である。
【００５８】
カウンタ値は、ゼロ以上の整数値である。カウント値の増減に関する処理については後述する。図６の例では、ＳｉＤがＳｉＤｍのスロットとデータＡとが対応付けられている。ＳｉＤｍのスロットに格納されたオフセットは、実データ格納領域におけるデータＡの位置を示している。このスロットに格納されたフィンガープリントｆｐＡはデータＡのハッシュ値である。また、このスロットに格納されたカウンタ値はデータＡの書き込み頻度に関する情報である。
【００５９】
コンテナ情報２０１ａは、上記のようなコンテナに関する情報を含む。また、コンテナ情報２０１ａは、図７に示すようなＦＰテーブルを含む。ＦＰテーブルは、フィンガープリント（ｆｐ）とＣｉＤとを対応付ける情報である。例えば、図６に例示したＣｉＤ１のコンテナにデータＡのフィンガープリントｆｐＡが含まれている場合、ＦＰテーブルは、図７に示すようにｆｐＡとＣｉＤ１とを対応付ける情報を有する。
【００６０】
図７の例では、データＢのフィンガープリントｆｐＢとＣｉＤ２、及び、データＣのフィンガープリントｆｐＣとＣｉＤ３が対応付けられている。このＦＰテーブルを利用すれば、ｆｐＢに対応するデータＢの格納先（ＣｉＤ２のコンテナ）、及びｆｐＣに対応するデータＣの格納先（ＣｉＤ３のコンテナ）を特定することができる。
【００６１】
以上、コンテナ情報２０１ａについて説明した。
（ブロックマップ）
次に、図８を参照しながら、ブロックマップ２０１ｂについて説明する。図８は、第２実施形態に係るブロックマップについて説明するための図である。
【００６２】
図８に示すように、ブロックマップ２０１ｂは、論理ボリューム（ＬＶ：Logical Volume）と、論理ボリューム上のアドレス（ＬＢＡ：Logical Block Addressing）と、フィンガープリント（ｆｐ）と、ＣｉＤとを対応付ける情報である。ブロックマップ２０１ｂは、ＬＶ毎にＬＢＡ、ｆｐ、ＣｉＤを対応付けるレコードを有する。ｆｐとデータとが対応することから、事実上、ブロックマップ２０１ｂは、ＬＶ上のデータの格納位置と、データが格納されたコンテナとを対応付けている。
【００６３】
図８の例示したブロックマップ２０１ｂでは、ＬＶ＃１のＬＢＡ１にｆｐＡ及びＣｉＤ１が対応付けられている。つまり、ｆｐＡに対応するデータＡは、ＬＶ＃１上ではＬＢＡ１を先頭とする記憶領域に格納され、さらにＣｉＤ１を有するコンテナの実データ格納領域に格納されている。また、この例では、ＬＶ＃１のＬＢＡ４にもｆｐＡ及びＣｉＤ１が対応付けられている。このことは、データＡがＬＶ＃１のＬＢＡ４を先頭とする記憶領域に重複して格納されていることを示す。
【００６４】
図８の下段に、コンテナ上のデータとブロックマップ２０１ｂの各レコードとの対応関係を模式的に示した。ＢＭ（Ａ）は、ＬＶ＃１に関するブロックマップ２０１ｂのレコードを示す。一方、ＢＭ（Ｂ）は、ＬＶ＃２に関するブロックマップ２０１ｂのレコードを示す。ＣｉＤ１のデータＡは、ＢＭ（Ａ）に含まれる２つのｆｐＡに対応する。つまり、ＬＶ＃１上でデータＡの重複が生じている。
【００６５】
ＣｉＤ２のデータＢは、ＢＭ（Ａ）に含まれる１つのｆｐＢと、ＢＭ（Ｂ）に含まれる１つのｆｐＢとに対応する。つまり、ＬＶ＃１、ＬＶ＃２にまたがってデータＢの重複が生じている。同様に、ＣｉＤ３のデータＣは、ＢＭ（Ａ）に含まれる１つのｆｐＣと、ＢＭ（Ｂ）に含まれる１つのｆｐＣとに対応する。つまり、ＬＶ＃１、ＬＶ＃２にまたがってデータＣの重複が生じている。このように、ブロックマップ２０１ｂを参照することで、データの重複を認識することができる。
【００６６】
以上、ブロックマップ２０１ｂについて説明した。
（ハッシュテーブル）
次に、図９を参照しながら、ハッシュテーブル２０１ｃについて説明する。図９は、第２実施形態に係るハッシュテーブルについて説明するための図である。
【００６７】
ハッシュテーブル２０１ｃは、キャッシュ装置２１０に格納済みのデータ（キャッシュ済みデータ）を特定するための情報である。例えば、ハッシュテーブル２０１ｃは、ハッシュ値とポインタとを登録したテーブルである。
【００６８】
ハッシュ値は、データのフィンガープリントをハッシュ関数（ＳＨＡ−１やＭＤ５など）に入力して計算した値である。図９の例では、ハッシュテーブル２０１ｃにハッシュ値ｈ０、ｈ１、…、ｈ５が登録されている。ポインタは、これらのハッシュ値と、キャッシュ済みデータとをリンクさせる情報である。ポインタの欄が「ｎｕｌｌ」となっているレコードは、キャッシュ済みデータとリンクしていないことを示す。
【００６９】
ハッシュテーブル２０１ｃに登録されるハッシュ値は、関連付けられるキャッシュ済みデータのフィンガープリントをハッシュ関数（ＳＨＡ−１やＭＤ５など）に入力して計算されるハッシュ値である。例えば、データＡに関連付けられるハッシュ値ｈ０は、データＡのフィンガープリントｆｐＡをハッシュ関数ｈに入力して計算されるハッシュ値ｈ（ｆｐＡ）である。ハッシュ値ｈ４についても同様である。
【００７０】
キャッシュ済みデータは、連結情報、時系列情報、フィンガープリント、ＣｉＤ、及びデータを含む。連結情報は、ハッシュテーブル２０１ｃのポインタと、キャッシュ済みデータとを関連付け、さらに、同じハッシュ値に関連付けられる他のキャッシュ済みデータとを関連付ける情報である。例えば、データＸのフィンガープリントがデータＡのフィンガープリントと同じ場合、ハッシュ値ｈ０に、データＡに関するキャッシュ済みデータと、データＸに関するキャッシュ済みデータとが関連付けられる。
【００７１】
時系列情報は、キャッシュ済みデータの新旧を判断するための情報である。例えば、新たなデータをキャッシュ装置２１０に格納する際に空き容量が十分でない場合、時系列情報をもとに古いキャッシュ済みデータが削除され、新たなデータがキャッシュされる。また、時系列情報は、アクセス頻度などに応じて更新される。以下、連結情報の集合を探索リスト、時系列情報の集合を時系列リストと呼ぶ場合がある。
【００７２】
ハッシュテーブル２０１ｃ、探索リスト、及び時系列リストを参照することで、ハッシュ値を用いたキャッシュ済みデータの検索が可能になる。同じハッシュ値をとるフィンガープリントがある場合、ハッシュ値を第１の検索キーとし、ＣｉＤを第２の検索キーとして線形探索することで所望のキャッシュ済みデータを検出することができる。
【００７３】
ここでは一例としてチェイン法によるデータの検索を実現するためのハッシュテーブル２０１ｃ及びキャッシュ済みデータの例を示したが、フィンガープリントを探索キーにキャッシュ済みデータを探索できる方法が実現できれば、これに限定されない。例えば、ハッシュテーブル２０１ｃは、フィンガープリントと、ＣｉＤと、キャッシュ装置２１０におけるキャッシュ済みデータのアドレスとを対応付けたテーブルであってもよい。
【００７４】
以上、ハッシュテーブル２０１ｃについて説明した。
再び図４を参照する。
Ｉ／Ｏ制御部２０２は、ホスト装置１００との間の入出力を制御する。ＦＰ算出部２０３は、記憶装置３００に書き込まれるデータのフィンガープリントを算出する。ＢＭ管理部２０４は、ブロックマップ２０１ｂを管理する。
【００７５】
ＲＣ制御部２０５は、キャッシュ装置２１０に格納されたキャッシュ済みデータのレコードやハッシュテーブル２０１ｃを管理する。ＲＣ制御部２０５は、記憶装置３００からのデータ読み出し時にデータをキャッシュ装置２１０に登録する。また、ＲＣ制御部２０５は、データの読み出し時に、ＬＲＵ（Least Recently Used）やＬＦＵ（Least Frequently Used）などの方式でキャッシュ済みデータのレコードを更新する。
【００７６】
コンテナ制御部２０６は、コンテナ情報２０１ａを管理し、コンテナを利用したデータの読み書き処理などを制御する。コンテナ制御部２０６は、登録処理部２０６ａ、ＲＷ制御部２０６ｂ、カウンタ管理部２０６ｃ、及びＧＣ制御部２０６ｄを有する。
【００７７】
登録処理部２０６ａは、コンテナの実データ格納領域に格納したデータのｆｐを対応するスロットに登録する。ＲＷ制御部２０６ｂは、コンテナへデータを書き込む処理及びコンテナからデータを読み出す処理を実行する。また、ＲＷ制御部２０６ｂは、コンテナにデータを書き込む際、インデックス領域のスロットに情報を登録する。
【００７８】
カウンタ管理部２０６ｃは、コンテナに格納されたデータへのアクセス頻度に応じてスロットに登録されたカウンタ値を更新する。ＧＣ制御部２０６ｄは、ガベージコレクション（ＧＣ）と呼ばれる処理を実行する。ＧＣは、対象のコンテナに格納されているデータのうちカウンタ値が条件を満たすデータを全て新たなコンテナに移動させ、移動後に対象のコンテナを削除する処理である。
【００７９】
以上、制御部２０２の機能について説明した。以下、フロー図を参照しながら、上述した機能に基づく制御部２０２の動作について、さらに説明する。
［２−４．制御装置の動作］
制御装置２００の動作について説明する。
【００８０】
（リード処理）
まず、図１０及び図１１を参照しながら、制御装置２００が実行するリード処理の流れについて説明する。図１０は、第２実施形態に係るリード処理の流れを示した第１のフロー図である。図１１は、第２実施形態に係るリード処理の流れを示した第２のフロー図である。
【００８１】
（Ｓ１０１）Ｉ／Ｏ制御部２０２は、ホスト装置１００からデータの読み出しを要求するＲｅａｄ要求を受信する。Ｒｅａｄ要求は、論理ボリューム（ＬＶ）を特定するための識別情報ＬＶｉＤ、そのＬＶにおけるデータの先頭アドレスＬＢＡ、データ長Ｌｅｎｇｔｈを含む。Ｉ／Ｏ制御部２０２は、受信したＲｅａｄ要求に応じて、データ格納用のバッファ（例えば、記憶部２０１の記憶領域）を確保する。
【００８２】
（Ｓ１０２）Ｉ／Ｏ制御部２０２は、予め設定した単位サイズ（例えば、４ＫＢ）毎にデータ位置を示すＬＢＡを特定し、Ｒｅａｄ要求を分割する。
例えば、Ｒｅａｄ要求が含むＬＢＡが０ＫＢ目であり、Ｌｅｎｇｔｈが２０ＫＢである場合、４ＫＢ単位でデータを分割した場合の各分割データの先頭位置を示すＬＢＡは、０ＫＢ目、４ＫＢ目、８ＫＢ目、１２ＫＢ目、１６ＫＢ目となる。
【００８３】
この場合、Ｉ／Ｏ制御部２０２は、１つ目の分割データに対応するＲｅａｄ要求のＬＶｉＤをホスト装置１００から受信したＲｅａｄ要求のＬＶｉＤに設定し、ＬＢＡを０ＫＢ目、Ｌｅｎｇｔｈを４ＫＢに設定する。同様に、Ｉ／Ｏ制御部２０２は、他の４つの分割データに対応するＲｅａｄ要求を生成する。つまり、Ｉ／Ｏ制御部２０２は、ホスト装置１００から受信したＲｅａｄ要求を５つの分割データに対応するＲｅａｄ要求に分割する。
【００８４】
（Ｓ１０３）Ｉ／Ｏ制御部２０２は、ブロックマップ２０１ｂを参照し、分割したＲｅａｄ要求に含まれるＬＶｉＤ及びＬＢＡに対応するｆｐ及びＣｉＤを特定する。Ｉ／Ｏ制御部２０２は、分割したＲｅａｄ要求の全てについて同様にｆｐ及びＣｉＤを特定し、特定したｆｐとＣｉＤの組を並べたリストを作成する。
【００８５】
（Ｓ１０４）Ｉ／Ｏ制御部２０２は、リストの全項目を処理し終えたか否かを判定する。つまり、Ｉ／Ｏ制御部２０２は、リストに含まれるｆｐとＣｉＤの組の全てについて、図１１に示すＳ１０６以降の処理が完了しているか否かを判定する。全項目を処理し終えている場合、処理はＳ１０５へと進む。一方、未処理の項目がある場合、処理は図１１のＳ１０６へと進む。
【００８６】
（Ｓ１０５）Ｉ／Ｏ制御部２０２は、バッファ内のデータをホスト装置１００に応答する。Ｓ１０５の処理が完了すると、図１０及び図１１に示した一連の処理は終了する。
（Ｓ１０６）ＲＣ制御部２０５は、Ｉ／Ｏ制御部２０２からリストの入力を受け付け、リストの先頭にあるｆｐとＣｉＤを取得する。
【００８７】
（Ｓ１０７）ＲＣ制御部２０５は、取得したＣｉＤがゼロか否かを判定する。ＣｉＤはゼロをとらないが、ブロックマップ２０１ｂが初期化された際に、ブロックマップ２０１ｂに含まれるＣｉＤの欄がゼロに設定される。つまり、ＬＶの該当部分にデータが書き込まれていない場合、ブロックマップ２０１ｂから読み出されたＣｉＤがゼロとなる。ＣｉＤがゼロの場合、処理はＳ１０８へと進む。一方、ＣｉＤがゼロでない場合、処理はＳ１０９へと進む。
【００８８】
（Ｓ１０８）ＲＣ制御部２０５は、Ｓ１０６で取得したｆｐとＣｉＤに対応するデータを書き込むために確保されたバッファの該当部分にゼロを格納する。そして、ＲＣ制御部２０５は、そのｆｐとＣｉＤの組をリストから削除する（処理済み）。Ｓ１０８の処理が完了すると、処理は図１０のＳ１０４へと進む。
【００８９】
（Ｓ１０９）ＲＣ制御部２０５は、Ｓ１０６で取得したｆｐのハッシュ値ｈ（ｆｐ）を計算する。ｈ（…）はハッシュ関数を示す。ｈ（…）は、例えば、ＳＨＡ−１やＭＤ５などのハッシュ関数である。
【００９０】
（Ｓ１１０）ＲＣ制御部２０５は、ハッシュテーブル２０１ｃ及び探索リストをもとにｈ（ｆｐ）とＣｉＤが一致するデータを探索する。例えば、ＲＣ制御部２０５は、図９に示すように、ハッシュテーブル２０１ｃの中でｈ（ｆｐ）と一致するハッシュ値を特定し、対応するポインタをもとにＣｉＤが一致するキャッシュ済みデータを特定する。同じハッシュ値に複数のキャッシュ済みデータが連結されている場合、ＲＣ制御部２０５は、探索リスト（連結情報の集合）を参照し、ＣｉＤを探索キーに線形探索を実施する。
【００９１】
（Ｓ１１１）ＲＣ制御部２０５は、キャッシュ装置２１０に該当データがあるかを判定する。つまり、ＲＣ制御部２０５は、Ｓ１１０の処理でｈ（ｆｐ）とＣｉＤの組に対応するキャッシュ済みデータ（該当データ）が検出されたか否かを判定する。該当データがある場合、処理はＳ１１３へと進む。該当データがない場合、処理はＳ１１２へと進む。
【００９２】
（Ｓ１１２）コンテナ制御部２０６のＲＷ制御部２０６ｂは、記憶装置３００から該当データを読み出し、ＲＣ制御部２０５に入力する。ＲＣ制御部２０５は、ＲＷ制御部２０６ｂから入力された該当データの新規レコードをキャッシュ装置２１０へ登録する。Ｓ１１２の処理については後段においてさらに説明する。
【００９３】
（Ｓ１１３）ＲＣ制御部２０５は、該当データのレコードが最新となるように時系列リスト（時系列情報の集合）を更新する。
例えば、図９に示したデータＡ、データＢ、データＸにそれぞれ対応する時系列情報ｔ１、ｔ２、ｔ３が、ｔ１、ｔ２、ｔ３の順で新しいレコードを示すものとする。該当データがデータＸである場合、例えば、データＸのレコードが最新となるようにデータＸの時系列情報がｔ１に、データＡの時系列情報がｔ２に、データＢの時系列情報がｔ３に書き換えられる。なお、ｔ１のレコードより新しいレコードを示すｔ０にデータＸの時系列情報が書き換えられるようにしてもよい。
【００９４】
（Ｓ１１４）ＲＣ制御部２０５は、バッファの該当部分にデータを格納する。
キャッシュ装置２１０に該当データがある場合、ＲＣ制御部２０５は、キャッシュ装置２１０から読み出した該当データをバッファに格納する。一方、キャッシュ装置２１０に該当データがない場合、ＲＣ制御部２０５は、Ｓ１１２でコンテナ制御部２０６を介して記憶装置３００から読み出した該当データをバッファに格納する。そして、ＲＣ制御部２０５は、該当データに対応するｆｐとＣｉＤの組をリストから削除する（処理済み）。Ｓ１１４の処理が完了すると、処理は図１０のＳ１０４へと進む。
【００９５】
ここで、図１２を参照しながら、キャッシュ装置２１０に対する新規レコードの登録処理（Ｓ１１２）について、さらに説明する。図１２は、第２実施形態に係る新規レコードの登録処理の流れを示したフロー図である。
【００９６】
（Ｓ１３１）ＲＣ制御部２０５は、記憶装置３００から読み出した該当データを登録することが可能な空きレコード（新規レコード）がキャッシュ装置２１０にあるかを判定する。新規レコードがある場合、処理はＳ１３３へと進む。一方、新規レコードがない場合、処理はＳ１３２へと進む。
【００９７】
（Ｓ１３２）ＲＣ制御部２０５は、時系列リストをもとに最古のレコードを特定し、リセットして新規レコードに設定する。つまり、ＲＣ制御部２０５は、時系列情報が最も古いレコードに登録された内容を削除し、新たに情報を登録できるようにリセットする。
【００９８】
（Ｓ１３３）ＲＣ制御部２０５は、コンテナ制御部２０６に対して該当データのＣｉＤとｆｐを通知する。この通知を受けたコンテナ制御部２０６のＲＷ制御部２０６ｂは、コンテナ情報２０１ａに基づいてＣｉＤに対応するコンテナのインデックス領域に含まれるスロットのうち、通知されたｆｐを含むスロットを特定する。そして、ＲＷ制御部２０６ｂは、特定したスロットのオフセットに基づいて実データ格納領域から該当データを取得する。ＲＷ制御部２０６ｂは、取得した該当データをＲＣ制御部２０５に入力する。
【００９９】
（Ｓ１３４）ＲＣ制御部２０５は、Ｓ１３３で取得した該当データをキャッシュ装置２１０の新規レコードに登録する。このとき、ＲＣ制御部２０５は、ｆｐ、ＣｉＤ、該当データを対応付けて新規レコードに登録する。
【０１００】
（Ｓ１３５）ＲＣ制御部２０５は、ハッシュテーブル２０１ｃを更新する。このとき、ＲＣ制御部２０５は、ハッシュテーブル２０１ｃのポインタと新規レコードとが連結されるように連結リストを更新する。また、ＲＣ制御部２０５は、新規レコードの時系列情報が最新となるように時系列リストを更新する。Ｓ１３５の処理が完了すると、図１２に示した一連の処理は終了する。
【０１０１】
以上、制御装置２００が実行するリード処理の流れについて説明した。
（ライト処理）
次に、図１３及び図１４を参照しながら、制御装置２００が実行するライト処理の流れについて説明する。図１３は、第２実施形態に係るライト処理の流れを示した第１のフロー図である。図１４は、第２実施形態に係るライト処理の流れを示した第２のフロー図である。
【０１０２】
（Ｓ２０１）Ｉ／Ｏ制御部２０２は、ホスト装置１００からデータの書き込みを要求するＷｒｉｔｅ要求を受信する。Ｗｒｉｔｅ要求は、論理ボリューム（ＬＶ）を特定するための識別情報ＬＶｉＤ、そのＬＶにおけるデータの先頭アドレスＬＢＡ、データ長Ｌｅｎｇｔｈ、及び書き込み対象のデータを含む。Ｉ／Ｏ制御部２０２は、Ｗｒｉｔｅ要求に含まれるデータを予め設定した単位サイズ（例えば、４ＫＢ）に分割する。
【０１０３】
（Ｓ２０２）Ｉ／Ｏ制御部２０２は、単位サイズ毎にデータ位置を示すＬＢＡを特定し、Ｗｒｉｔｅ要求を分割する。
例えば、Ｗｒｉｔｅ要求が含むＬＢＡが０ＫＢであり、Ｌｅｎｇｔｈが２０ＫＢである場合、４ＫＢ単位でデータを分割した場合の各分割データの先頭位置を示すＬＢＡは、０ＫＢ、４ＫＢ、８ＫＢ、１２ＫＢ、１６ＫＢとなる。
【０１０４】
この場合、Ｉ／Ｏ制御部２０２は、１つ目の分割データに対応するＷｒｉｔｅ要求のＬＶｉＤをホスト装置１００から受信したＷｒｉｔｅ要求のＬＶｉＤに設定し、ＬＢＡを０ＫＢ、Ｌｅｎｇｔｈを４ＫＢに設定する。そして、Ｉ／Ｏ制御部２０２は、分割データをＷｒｉｔｅ要求に含める。同様に、Ｉ／Ｏ制御部２０２は、他の４つの分割データに対応するＷｒｉｔｅ要求を生成する。つまり、Ｉ／Ｏ制御部２０２は、ホスト装置１００から受信したＷｒｉｔｅ要求を５つの分割データに対応するＷｒｉｔｅ要求に分割する。
【０１０５】
（Ｓ２０３）Ｉ／Ｏ制御部２０２は、ブロックマップ２０１ｂを参照し、分割したＷｒｉｔｅ要求に含まれるＬＶｉＤ及びＬＢＡに対応するｆｐ及びＣｉＤを特定する。Ｉ／Ｏ制御部２０２は、分割したＷｒｉｔｅ要求の全てについて同様にｆｐ及びＣｉＤを特定し、特定したｆｐとＣｉＤの組を並べたリストを作成する。
【０１０６】
（Ｓ２０４）Ｉ／Ｏ制御部２０２は、リストの全項目を処理し終えたか否かを判定する。つまり、Ｉ／Ｏ制御部２０２は、リストに含まれるｆｐとＣｉＤの組の全てについて、図１４に示すＳ２０６以降の処理が完了しているか否かを判定する。全項目を処理し終えている場合、処理はＳ２０５へと進む。一方、未処理の項目がある場合、処理は図１４のＳ２０６へと進む。
【０１０７】
（Ｓ２０５）Ｉ／Ｏ制御部２０２は、バッファ内のデータをホスト装置１００に応答する。Ｓ２０５の処理が完了すると、図１３及び図１４に示した一連の処理は終了する。
（Ｓ２０６）コンテナ制御部２０６は、Ｉ／Ｏ制御部２０２からリストの入力を受け付け、リストの先頭にあるｆｐとＣｉＤを取得する。
【０１０８】
（Ｓ２０７）コンテナ制御部２０６は、取得したＣｉＤがゼロか否かを判定する。ＣｉＤはゼロをとらないが、ブロックマップ２０１ｂが初期化された際に、ブロックマップ２０１ｂに含まれるＣｉＤの欄がゼロに設定される。つまり、ＬＶの該当部分にデータが書き込まれていない場合、ブロックマップ２０１ｂから読み出されたＣｉＤがゼロとなる。
【０１０９】
ＣｉＤがゼロの場合（つまり、同じデータがコンテナに書き込まれていない場合）、処理はＳ２０９へと進む。一方、ＣｉＤがゼロでない場合（つまり、既に同じデータがコンテナに書き込まれている場合）、処理はＳ２０８へと進む。
【０１１０】
（Ｓ２０８）コンテナ制御部２０６のカウンタ管理部２０６ｃは、Ｓ２０６で取得したＣｉＤに対応するコンテナのインデックス領域にあるスロットのうち、Ｓ２０６で取得したｆｐを含むスロットを特定する。そして、カウンタ管理部２０６ｃは、特定したスロットに含まれるカウンタ値に対するデクリメント処理を実行する。このデクリメント処理については後段においてさらに説明する。
【０１１１】
（Ｓ２０９）ＦＰ算出部２０３は、書き込み対象のデータ（Ｗｒｉｔｅデータ）からフィンガープリントｆｐを計算する。例えば、ＦＰ算出部２０３は、ＳＨＡ−１やＭＤ５などのハッシュ関数にＷｒｉｔｅデータを入力してハッシュ値を計算し、計算したハッシュ値をフィンガープリントｆｐとしてコンテナ制御部２０６に入力する。
【０１１２】
（Ｓ２１０）コンテナ制御部２０６は、Ｓ２０９で計算されたｆｐがコンテナに登録されているか否かを判定する。
ＣｉＤがゼロの場合、コンテナ制御部２０６は、ｆｐが未登録であると判定する。ＣｉＤがゼロでない場合、コンテナ制御部２０６は、そのＣｉＤに対応するコンテナのスロットを参照し、計算されたｆｐが登録されているか否かを判定する。計算されたｆｐがコンテナに登録されている場合、処理はＳ２１１へと進む。一方、計算されたｆｐがコンテナに登録されていない場合、処理はＳ２１２へと進む。
【０１１３】
（Ｓ２１１）コンテナ制御部２０６のカウンタ管理部２０６ｃは、Ｓ２０９で計算されたｆｐと同じｆｐが登録されているスロットのカウンタ値に対するインクリメント処理を実行する。このインクリメント処理については後段においてさらに説明する。Ｓ２１１の処理が完了すると、処理はＳ２１４へと進む。
【０１１４】
（Ｓ２１２）コンテナ制御部２０６のＲＷ制御部２０６ｂは、Ｓ２０６で取得したＣｉＤを有するコンテナの実データ格納領域に新規データ（Ｗｒｉｔｅデータ）を書き込む。
なお、Ｓ２０６で取得したＣｉＤがゼロの場合、ＲＷ制御部２０６ｂは、実データ格納領域の容量に空きがあるコンテナのＣｉＤを選択し、選択したＣｉＤのコンテナに新規データを書き込む。また、ＲＷ制御部２０６ｂは、インデックス領域の空きスロットを１つ選択し、書き込んだデータの位置を示すオフセットを登録する。
【０１１５】
（Ｓ２１３）ＲＷ制御部２０６ｂは、Ｓ２１２でオフセットを登録したスロットにｆｐを登録する。コンテナ制御部２０６のカウンタ管理部２０６ｃは、ＲＷ制御部２０６ｂがｆｐを登録したスロットのカウンタ値を１に設定する。
【０１１６】
（Ｓ２１４）ＢＭ管理部２０４は、ブロックマップ２０１ｂの該当する部分を新規のｆｐ（Ｓ２０９で計算したｆｐ）とＣｉＤに更新する。
Ｓ２０９で計算されたｆｐが未登録であり、コンテナに新規データが書き込まれた場合、ＢＭ管理部２０４は、Ｗｒｉｔｅ要求のＬＶｉＤとＬＢＡの組に該当する部分に新規のｆｐとＣｉＤを登録する。一方、同じｆｐがコンテナに登録済みの場合、ＢＭ管理部２０４は、Ｗｒｉｔｅ要求のＬＶｉＤとＬＢＡの組に該当する部分に既に書き込まれているｆｐを新規のｆｐに書き換える。そして、ＢＭ管理部２０４は、ｆｐとＣｉＤのリストから、先頭の項目を削除する（処理済み）。Ｓ２１４の処理が完了すると、処理は図１３のＳ２０４へと進む。
【０１１７】
ここで、図１５を参照しながら、カウンタのインクリメント処理（Ｓ２１１）について、さらに説明する。図１５は、第２実施形態に係るインクリメント処理の流れを示したフロー図である。
【０１１８】
（Ｓ２３１）カウンタ管理部２０６ｃは、登録済みｆｐのあるコンテナのカウンタ値をインクリメントする。つまり、カウンタ管理部２０６ｃは、Ｓ２０９で計算されたｆｐと同じｆｐが登録されているスロットを特定し、特定したスロットに含まれるカウンタ値を１増加させる。
【０１１９】
（Ｓ２３２）カウンタ管理部２０６ｃは、Ｓ２３１でカウンタ値をインクリメントしたコンテナがＧＣ処理中であるかを判定する。つまり、カウンタ管理部２０６ｃは、このコンテナのＣｉＤをＧＣ制御部２０６ｄに通知し、そのコンテナのデータを他のコンテナに移動中であるかを確認する。ＧＣ処理中でない場合、図１５に示した一連の処理は終了する。ＧＣ処理中である場合、処理はＳ２３３へと進む。
【０１２０】
（Ｓ２３３）カウンタ管理部２０６ｃは、カウンタ値をインクリメントしたスロットのｆｐに対応するデータがコピー済みかを判定する。つまり、カウンタ管理部２０６ｃは、そのスロットのＳｉＤをＧＣ制御部２０６ｄに通知し、そのＳｉＤのスロットに含まれるオフセットが示すデータを移動先のコンテナにコピーしたかを確認する。コピー済みである場合、処理はＳ２３４へと進む。一方、コピー済みでない場合、図１５に示した一連の処理は終了する。
【０１２１】
（Ｓ２３４）カウンタ管理部２０６ｃは、ＧＣ処理によりデータが移動される移動先コンテナのカウンタ値をインクリメントする。つまり、カウンタ管理部２０６ｃは、移動先コンテナのインデックス領域に含まれる同じｆｐを有するスロットを特定し、特定したスロットのカウンタ値を１増加させる。Ｓ２３４の処理が完了すると、図１５に示した一連の処理は終了する。
【０１２２】
次に、図１６を参照しながら、カウンタのデクリメント処理（Ｓ２０８）について、さらに説明する。図１６は、第２実施形態に係るデクリメント処理の流れを示したフロー図である。
【０１２３】
（Ｓ２５１）カウンタ管理部２０６ｃは、登録済みｆｐのあるコンテナのカウンタ値をデクリメントする。つまり、カウンタ管理部２０６ｃは、Ｓ２０９で計算されたｆｐと同じｆｐが登録されているスロットを特定し、特定したスロットに含まれるカウンタ値を１減少させる。
【０１２４】
（Ｓ２５２）カウンタ管理部２０６ｃは、Ｓ２５１でカウンタ値をデクリメントしたコンテナがＧＣ処理中であるかを判定する。つまり、カウンタ管理部２０６ｃは、このコンテナのＣｉＤをＧＣ制御部２０６ｄに通知し、そのコンテナのデータを他のコンテナに移動中であるかを確認する。ＧＣ処理中でない場合、図１６に示した一連の処理は終了する。ＧＣ処理中である場合、処理はＳ２５３へと進む。
【０１２５】
（Ｓ２５３）カウンタ管理部２０６ｃは、カウンタ値をデクリメントしたスロットのｆｐに対応するデータがコピー済みかを判定する。つまり、カウンタ管理部２０６ｃは、そのスロットのＳｉＤをＧＣ制御部２０６ｄに通知し、そのＳｉＤのスロットに含まれるオフセットが示すデータを移動先のコンテナにコピーしたかを確認する。コピー済みである場合、処理はＳ２５４へと進む。一方、コピー済みでない場合、図１６に示した一連の処理は終了する。
【０１２６】
（Ｓ２５４）カウンタ管理部２０６ｃは、ＧＣ処理によりデータが移動される移動先コンテナのカウンタ値をデクリメントする。つまり、カウンタ管理部２０６ｃは、移動先コンテナのインデックス領域に含まれる同じｆｐを有するスロットを特定し、特定したスロットのカウンタ値を１減少させる。Ｓ２５４の処理が完了すると、図１６に示した一連の処理は終了する。
【０１２７】
以上、制御装置２００が実行するライト処理の流れについて説明した。
（ＧＣ処理）
次に、図１７を参照しながら、制御装置２００が実行するＧＣ処理の流れについて説明する。図１７は、第２実施形態に係るＧＣ処理の流れを示したフロー図である。なお、図１７に示した処理は主にコンテナ制御部２０６のＧＣ制御部２０６ｄが実行する。
【０１２８】
（Ｓ３０１）ＧＣ制御部２０６ｄは、ＧＣ処理の実行条件を満たしているかを判定する。ＧＣ処理の実行条件は、例えば、前回ＧＣ処理を実行した後、所定時間が経過したことや、ユーザが指定したことなどである。ＧＣ処理の実行条件を満たしている場合、処理はＳ３０２へと進む。ＧＣ処理の実行条件を満たしていない場合、処理はＳ３０４へと進む。
【０１２９】
（Ｓ３０２）ＧＣ制御部２０６ｄは、ＧＣの対象コンテナを選択する。このとき、ＧＣ制御部２０６ｄは、各コンテナのインデックス領域にある各スロットのカウンタ値を参照し、カウンタ値が０のスロットを有するコンテナを対象コンテナとして選択する。なお、ＧＣ制御部２０６ｄは、カウンタ値が０のスロットが総スロット数の所定割合を上回ったコンテナを対象コンテナとして選択してもよい。
【０１３０】
（Ｓ３０３）ＧＣ制御部２０６ｄは、対象コンテナがあるかを判定する。対象コンテナがある場合、処理はＳ３０５へと進む。一方、対象コンテナがない場合、処理はＳ３０４へと進む。
【０１３１】
（Ｓ３０４）ＧＣ制御部２０６ｄは、予め設定された時間、ＧＣ処理を進めずに待機する。その時間が経過した後、処理はＳ３０１へと進む。
（Ｓ３０５）ＧＣ制御部２０６ｄは、新たに生成したコンテナを、対象コンテナに格納されたデータの移動先となるコンテナ（移動先コンテナ）に割り当てる。
【０１３２】
（Ｓ３０６）ＧＣ制御部２０６ｄは、未チェックのデータがあるかを判定する。つまり、対象コンテナの実データ格納領域に格納された各データについて、Ｓ３０７以降の処理が全て完了したかを判定する。未チェックのデータがある場合、処理はＳ３０７へと進む。一方、未チェックのデータがない場合、処理はＳ３１１へと進む。
【０１３３】
（Ｓ３０７）ＧＣ制御部２０６ｄは、対象コンテナから未チェックのデータを取得する。
（Ｓ３０８）ＧＣ制御部２０６ｄは、Ｓ３０７で取得したデータに対応するスロットのカウンタ値を参照し、そのカウンタ値が１以上であるかを判定する。カウンタ値が１以上である場合、処理はＳ３０９へと進む。一方、カウンタ値が１以上でない場合、Ｓ３０７で取得したデータはチェック済みとされ、処理はＳ３０６へと進む。
【０１３４】
（Ｓ３０９）ＧＣ制御部２０６ｄは、Ｓ３０７で取得したデータを移動先コンテナにコピーする。
（Ｓ３１０）ＧＣ制御部２０６ｄは、移動先コンテナのカウンタ値を対象コンテナのカウンタ値と同じ値に設定する。つまり、ＧＣ制御部２０６ｄは、Ｓ３０９でコピーしたデータについて、移動先コンテナのカウンタ値と対象コンテナのカウンタ値とを同期させる。Ｓ３１０の処理が完了すると、Ｓ３０７で取得したデータはチェック済みとされ、処理はＳ３０６へと進む。
【０１３５】
（Ｓ３１１）ＧＣ制御部２０６ｄは、移動先コンテナのＣｉＤを対象コンテナのＣｉＤに設定し、対象コンテナを回収する。つまり、ＧＣ制御部２０６ｄは、ＣｉＤを対象コンテナから移動先コンテナに付け替え、対象コンテナを削除する。Ｓ３１１の処理が完了すると、図１７に示した一連の処理は終了する。
【０１３６】
なお、ＧＣ処理の中で削除されたデータの情報は、ＲＣ制御部２０５に通知される。ＲＣ制御部２０５は、この情報が示すデータがキャッシュ装置２１０に格納されている場合に、そのデータのレコードをキャッシュ装置２１０から削除する。
【０１３７】
以上、制御装置２００が実行するＧＣ処理の流れについて説明した。
［２−５．変形例］
これまで、キャッシュ済みデータを探索する際に、ｆｐのハッシュ値ｈ（ｆｐ）を第１の探索キーとし、ＣｉＤを第２の探索キーとする方法を前提に説明してきた。ここでは、この方法を拡張し、ＳｉＤを第３の探索キーとして利用する変形例を提案する。
【０１３８】
図１８は、第２実施形態の一変形例に係るキャッシュ情報について説明するための図である。図１９は、第２実施形態の一変形例に係るブロックマップについて説明するための図である。
【０１３９】
ＳｉＤを第３の探索キーとして利用する場合、キャッシュ済みデータのレコードは、図１８に示すように、連結情報、時系列情報、ｆｐ、ＣｉＤの他にＳｉＤを含む。また、ブロックマップ２０１ｂは、図１９に示すように、ＬＶ毎に対応するＬＢＡ、ｆｐ、ＣｉＤ、ＳｉＤを含む。このように、キャッシュ済みデータのレコードとブロックマップ２０１ｂの構造を変形することで、ＳｉＤを第３の探索キーとして利用することができる。
【０１４０】
この変形例によれば、ｆｐとＣｉＤの組み合わせとデータとの対応関係が一意に決まらないような状況でも、ＳｉＤを利用してデータを一意に特定することが可能になる。つまり、ｆｐのデータ長が短く、ｆｐとＣｉＤの組み合わせだけではデータが一意に特定できない場合でも、ＳｉＤを組み合わせることでデータを一意に特定できるようになる。このことは、ｆｐのデータ長を短くし、保持すべきデータ量を減らすことなどに寄与する。
【０１４１】
以上、第２実施形態について説明した。
第２実施形態によれば、ｆｐを介してキャッシュ済みデータを読み出すため、読み出し対象のデータと同内容のデータがキャッシュされていれば、ＬＶｉＤやＬＢＡが異なっても、キャッシュ済みデータを読み出してホスト装置１００に応答することが可能になる。その結果、応答が高速化し、ストレージシステムの性能向上に寄与する。また、同一内容のデータをキャッシュせずに済むため、キャッシュ装置２１０の記憶容量を有効利用できる。さらに、記憶装置３００へのアクセスを減らせることから、ストレージシステムの信頼性向上に寄与する。
【符号の説明】
【０１４２】
５  ストレージシステム
１０  ホスト装置
２０  ストレージ装置
２１  記憶部
２１ａ  キャッシュ情報
２１ｂ  場所情報
２２  制御部
３０  記憶装置
４０  キャッシュ装置
ＲＱ  読み出し要求
ＲＰ  応答
Ｄ１、Ｄ２  データ
ｆｐ（Ｄ１）、ｆｐ（Ｄ２）  内容情報
ＡＤＲ１、ＡＤＲ２、ＡＤＲ３  記憶場所
【図１】
2016126632.tif 000003
【図２】
2016126632.tif 000004
【図３】
2016126632.tif 000005
【図４】
2016126632.tif 000006
【図５】
2016126632.tif 000007
【図６】
2016126632.tif 000008
【図７】
2016126632.tif 000009
【図８】
2016126632.tif 000010
【図９】
2016126632.tif 000011
【図１０】
2016126632.tif 000012
【図１１】
2016126632.tif 000013
【図１２】
2016126632.tif 000014
【図１３】
2016126632.tif 000015
【図１４】
2016126632.tif 000016
【図１５】
2016126632.tif 000017
【図１６】
2016126632.tif 000018
【図１７】
2016126632.tif 000019
【図１８】
2016126632.tif 000020
【図１９】
2016126632.tif 000021