(57)【要約】【課題】重複排除の効率を改善すること。【解決手段】物理記憶領域２１ｃに書き込まれるデータブロックのハッシュ値が格納される第１のキャッシュ領域２１ａと、物理記憶領域２１ｃから読み出されるデータブロックのハッシュ値が格納される第２のキャッシュ領域２１ｂとを有するキャッシュメモリ２１と、物理記憶領域２１ｃに対するデータブロックの書き込み要求を受け付けたとき、第１のキャッシュ領域２１ａ又は第２のキャッシュ領域２１ｂに該データブロックのハッシュ値と同じハッシュ値があるかを判定し、同じハッシュ値がある場合には該データブロックの重複排除を実施する制御部２２とを有する、ストレージ制御装置２０が提供される。【選択図】図１
2019028954.tif 000002
【特許請求の範囲】
【請求項１】
物理記憶領域に書き込まれるデータブロックのハッシュ値が格納される第１のキャッシュ領域と、前記物理記憶領域から読み出されるデータブロックのハッシュ値が格納される第２のキャッシュ領域とを有するキャッシュメモリと、
前記物理記憶領域に対するデータブロックの書き込み要求を受け付けたとき、前記第１のキャッシュ領域又は前記第２のキャッシュ領域に該データブロックのハッシュ値と同じハッシュ値があるかを判定し、前記同じハッシュ値がある場合には該データブロックの重複排除を実施する制御部と
を有する、ストレージ制御装置。
【請求項２】
前記制御部は、前記書き込み要求を受け付けたとき、前記第１のキャッシュ領域を対象に該データブロックのハッシュ値と同じハッシュ値の検索を実施し、前記同じハッシュ値がない場合には前記第２のキャッシュ領域を対象に前記同じハッシュ値の検索を実施する
請求項１に記載のストレージ制御装置。
【請求項３】
前記制御部は、新たなハッシュ値の格納により前記第１のキャッシュ領域が溢れる場合に前記第１のキャッシュ領域のハッシュ値を古い順に削除する
請求項２に記載のストレージ制御装置。
【請求項４】
前記物理記憶領域に書き込まれるデータブロックには該データブロックのハッシュ値が付加されており、
前記制御部は、前記物理記憶領域から読み出したデータブロックに付加されているハッシュ値を取得し、取得した該ハッシュ値を前記第２のキャッシュ領域に格納する
請求項３に記載のストレージ制御装置。
【請求項５】
物理記憶領域に書き込まれるデータブロックのハッシュ値を第１のキャッシュ領域に格納し、前記物理記憶領域から読み出されるデータブロックのハッシュ値を第２のキャッシュ領域に格納し、
前記物理記憶領域に対するデータブロックの書き込み要求を受け付けたとき、前記第１のキャッシュ領域又は前記第２のキャッシュ領域に該データブロックのハッシュ値と同じハッシュ値があるかを判定し、前記同じハッシュ値がある場合には該データブロックの重複排除を実施する
処理をコンピュータに実行させる、プログラム。
【請求項６】
コンピュータが、
物理記憶領域に書き込まれるデータブロックのハッシュ値を第１のキャッシュ領域に格納し、前記物理記憶領域から読み出されるデータブロックのハッシュ値を第２のキャッシュ領域に格納し、
前記物理記憶領域に対するデータブロックの書き込み要求を受け付けたとき、前記第１のキャッシュ領域又は前記第２のキャッシュ領域に該データブロックのハッシュ値と同じハッシュ値があるかを判定し、前記同じハッシュ値がある場合には該データブロックの重複排除を実施する
重複排除方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージ制御装置、プログラム、及び重複排除方法に関する。
【背景技術】
【０００２】
ストレージシステムでは、ＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）などの記憶装置に格納されるデータの量を削減するために重複排除と呼ばれる技術が採用されることがある。重複排除は、記憶装置に書き込むデータ（ライトデータ）と、既に記憶装置に格納済みのデータ（既存データ）との重複を検出し、重複するデータの書き込みを回避する技術である。
【０００３】
重複を検出する方法としては、例えば、ライトデータのハッシュ値と既存データのハッシュ値とを比較し、ハッシュ値が同じ既存データの有無を検出する方法がある。なお、ハッシュ値が一致するデータ同士をさらに比較する方法が提案されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開2009-251725号公報
【特許文献２】特開2014-137814号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記のようにハッシュ値を利用することで高速に重複を検出することができる。既存データのハッシュ値は、例えば、ストレージシステムで重複排除などの処理を制御するストレージ制御装置のキャッシュメモリに格納される。キャッシュメモリの容量は有限であり、全ての既存データのハッシュ値を格納しきれないことがある。キャッシュメモリの空きが不足する場合、キャッシュメモリの空きを確保するために、例えば、キャッシュメモリ内のハッシュ値の中で一番古いハッシュ値が削除される。
【０００６】
キャッシュメモリからハッシュ値が削除されると、削除されたハッシュ値と同じハッシュ値に対応するライトデータには重複排除が実施されず、既存データと重複するライトデータが記憶装置に書き込まれる。
【０００７】
一例として、記憶装置内の一の領域にある既存データを大量に他の領域へとコピーする場合、ストレージ制御装置は、一の領域から読み出した既存データを他の領域に書き込む。重複排除の対象から外れたライトデータのハッシュ値は、キャッシュメモリに順次格納される。キャッシュメモリの空き不足が生じると、キャッシュメモリからハッシュ値が削除される。削除されたハッシュ値と重複するはずだったライトデータは、ハッシュ値の不一致が生じ、重複排除されない。
【０００８】
コピーの場合にはライトデータは既存データと重複する。しかし、上記のようにキャッシュメモリの空き不足によりハッシュ値の不一致が生じ、既存データと重複するライトデータが記憶装置に書き込まれる。つまり、キャッシュメモリの空き不足により重複排除の対象から漏れるライトデータが生じて重複排除の効率が低下する。
【０００９】
コピーのように、読み出しと書き込みとが続けて実施される状況ではライトデータと既存データとが重複する可能性が高くなる。このような場合、キャッシュメモリに対するハッシュ値の格納制御を工夫することで上記の効率低下を低減できる余地がある。
【００１０】
１つの側面によれば、本発明の目的は、重複排除の効率を改善できるストレージ制御装置、プログラム、及び重複排除方法を提供することにある。
【課題を解決するための手段】
【００１１】
一態様によれば、物理記憶領域に書き込まれるデータブロックのハッシュ値が格納される第１のキャッシュ領域と、物理記憶領域から読み出されるデータブロックのハッシュ値が格納される第２のキャッシュ領域とを有するキャッシュメモリと、物理記憶領域に対するデータブロックの書き込み要求を受け付けたとき、第１のキャッシュ領域又は第２のキャッシュ領域に該データブロックのハッシュ値と同じハッシュ値があるかを判定し、同じハッシュ値がある場合には該データブロックの重複排除を実施する制御部とを有する、ストレージ制御装置が提供される。
【発明の効果】
【００１２】
重複排除の効率を改善できる。
【図面の簡単な説明】
【００１３】
【図１】第１実施形態に係るストレージシステムの一例を示した図である。
【図２】第２実施形態に係るストレージシステムの一例を示した図である。
【図３】書き込み制御と重複排除について説明するための第１の図である。
【図４】書き込み制御と重複排除について説明するための第２の図である。
【図５】ＷＨＣの構造について説明するための図である。
【図６】読み出し制御について説明するための図である。
【図７】データコピー時の重複排除について説明するための第１の図である。
【図８】データコピー時の重複排除について説明するための第２の図である。
【図９】制御情報の一例を示した図である。
【図１０】ＷＲＩＴＥ時の処理の流れを示したフロー図である。
【図１１】ＲＥＡＤ時の処理の流れを示したフロー図である。
【発明を実施するための形態】
【００１４】
以下に添付図面を参照しながら、本発明の実施形態について説明する。なお、本明細書及び図面において実質的に同一の機能を有する要素については、同一の符号を付することにより重複説明を省略する場合がある。
【００１５】
＜１．第１実施形態＞
図１を参照しながら、第１実施形態について説明する。第１実施形態は、重複排除（Deduplication）を実施するストレージシステムに適用可能なキャッシュ制御に関する。図１は、第１実施形態に係るストレージシステムの一例を示した図である。
【００１６】
図１に示すように、第１実施形態に係るストレージシステムは、ホスト装置１０、ストレージ制御装置２０、及び記憶装置３０を含む。
ホスト装置１０は、例えば、ＰＣ（Personal Computer）やサーバ装置などのコンピュータである。また、ホスト装置１０は、ＦＣ（Fibre Channel）やＬＡＮ（Local Area Network）などの通信回線を介してストレージ制御装置２０と接続される。また、ホスト装置１０は、ストレージ制御装置２０を介して記憶装置３０にアクセスする。
【００１７】
ストレージ制御装置２０及び記憶装置３０は、データを格納するためのストレージ装置として機能する。ストレージ制御装置２０と記憶装置３０とは、例えば、ＳＡＳ（Serial Attached Small Computer System Interface）やＳＡＴＡ（Serial Advanced Technology Attachment）などのインターフェースを介して接続される。
【００１８】
ストレージ制御装置２０は、記憶装置３０に対するデータの読み書きを制御する。ストレージ装置の動作を制御するＣＭ（Controller Module）は、ストレージ制御装置２０の一例である。ストレージ制御装置２０は、キャッシュメモリ２１、制御部２２、記憶部２３を有する。
【００１９】
キャッシュメモリ２１は、例えば、ＲＡＭ（Random Access Memory）などのメモリである。キャッシュメモリ２１は、第１のキャッシュ領域２１ａ、第２のキャッシュ領域２１ｂ、及び物理記憶領域２１ｃを有する。第１のキャッシュ領域２１ａ及び第２のキャッシュ領域２１ｂは、後述するハッシュ値の格納に利用される。物理記憶領域２１ｃは、書き込み対象のデータ（ＷＲＩＴＥデータ）を一時的に格納するためのデータキャッシュとして利用される。
【００２０】
なお、第１のキャッシュ領域２１ａ、第２のキャッシュ領域２１ｂ、物理記憶領域２１ｃはそれぞれ別のメモリに確保されてもよい。第２のキャッシュ領域２１ｂのサイズは、第１のキャッシュ領域２１ａのサイズより小さく設定されてもよい。
【００２１】
制御部２２は、例えば、ＣＰＵ（Central Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）などのプロセッサである。
【００２２】
記憶部２３は、例えば、ＲＡＭ、ＨＤＤ、ＳＳＤなどのメモリである。記憶部２３には、制御部２２が実行するプログラムなどが格納される。記憶装置３０は、データが格納される記録媒体３２、３３、３４を有する。ＲＡＩＤ（Redundant Arrays of Inexpensive Disks）装置は、記憶装置３０の一例である。記録媒体３２、３３、３４は、例えば、ＨＤＤやＳＳＤなどである。
【００２３】
記録媒体３２、３３、３４は物理記憶領域３１を形成する。複数の記録媒体の記憶領域を仮想的に１つの記憶領域として運用するストレージプールや物理ボリュームなどは、物理記憶領域３１の一例である。
【００２４】
ストレージ制御装置２０は、制御部２２にてプログラムの実行により重複排除を実施する。重複排除は、ＷＲＩＴＥデータと同じ内容のデータが物理記憶領域２１ｃ、３１の少なくとも一方にある場合に、ＷＲＩＴＥデータの書き込み先アドレスと既に格納済みのデータ（既存データ）とを対応付け、書き込み処理を回避する処理である。この処理により重複するデータの書き込みが抑制されるため、記憶容量の節約に寄与する。
【００２５】
上記の重複排除は、重複排除率を高めるために所定サイズ（例えば、４ＫＢ）のデータブロックを単位として実施される。制御部２２は、ＷＲＩＴＥデータを複数のデータブロックに分割し、ＷＲＩＴＥデータの各データブロックと既存データのデータブロックとを比較する。このとき、制御部２２は、各データブロックのハッシュ値を利用してデータブロックの内容を比較する。
【００２６】
一例としてデータブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５を物理記憶領域２１ｃに書き込む場合、制御部２２は、所定のハッシュ関数を用いてデータブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５のハッシュ値Ｈ＃１、…、Ｈ＃５を計算する。例えば、制御部２２は、４ＫＢのデータ入力に対し、そのデータ内容に応じた２０Ｂｙｔｅのハッシュ値を出力するハッシュ関数を利用してハッシュ値Ｈ＃１、…、Ｈ＃５を計算する。
【００２７】
データブロックｄＢＬＫ＃１を書き込むとき、制御部２２は、データブロックｄＢＬＫ＃１から計算されたハッシュ値Ｈ＃１と、第１のキャッシュ領域２１ａに格納されている各ハッシュ値とを比較する。この例では第１のキャッシュ領域２１ａにハッシュ値Ｈ＃１がないため、制御部２２は、図１のＡに示すように、データブロックｄＢＬＫ＃１にハッシュ値Ｈ＃１を付加したデータを物理記憶領域２１ｃに格納する。
【００２８】
なお、データブロックｄＢＬＫ＃２、…、ｄＢＬＫ＃５についても制御部２２はデータブロックｄＢＬＫ＃１と同様に上記の処理を実行する。また、データブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５は圧縮後に物理記憶領域２１ｃに格納される。
【００２９】
制御部２２は、データブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５の書き込み処理とは非同期に物理記憶領域２１ｃにあるデータの少なくとも一部を記憶装置３０の物理記憶領域３１に移動し、物理記憶領域３１に格納済みのデータを物理記憶領域２１ｃから削除する処理（書き出し処理）を実行する。書き出し処理は、例えば、物理記憶領域２１ｃが溢れる場合など、空き容量や使用率に応じたタイミングで実行される。
【００３０】
他方、制御部２２は、ホスト装置１０からデータブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５に対応するＲＥＡＤデータの読み出し要求を受け付けると、物理記憶領域２１ｃ、３１のいずれかからデータブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５を読み出す。
【００３１】
例えば、データブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５が物理記憶領域３１にある場合、制御部２２は、物理記憶領域３１から読み出したデータブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５を物理記憶領域２１ｃに一時的に格納する。そして、制御部２２は、データブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５を結合してＲＥＡＤデータを生成し、読み出し要求に対する応答としてＲＥＡＤデータをホスト装置１０に送信する。
【００３２】
データブロックｄＢＬＫ＃１を読み出すとき、制御部２２は、データブロックｄＢＬＫ＃１に付加されているハッシュ値Ｈ＃１を分離し、ハッシュ値Ｈ＃１を第２のキャッシュ領域２１ｂに格納する。データブロックｄＢＬＫ＃２、…、ｄＢＬＫ＃５を読み出すときも同様に、ハッシュ値Ｈ＃２、…、Ｈ＃５が第２のキャッシュ領域２１ｂに格納される。
【００３３】
上記のように、第１のキャッシュ領域２１ａ、第２のキャッシュ領域２１ｂは、ハッシュ値を格納するために利用される。データブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５のハッシュ値と同じハッシュ値が第１のキャッシュ領域２１ａにない場合、上記の流れに沿って物理記憶領域２１ｃへの書き込み処理が実行される。一方、データブロックｄＢＬＫ＃ｋ（ｋ＝１，…，５）のハッシュ値と同じハッシュ値が第１のキャッシュ領域２１ａにある場合、データブロックｄＢＬＫ＃ｋについて重複排除が実施される。
【００３４】
まず、４つのデータブロックを格納可能なサイズの第１のキャッシュ領域２１ａが空の状態でデータブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５が論理記憶領域４１に書き込まれる状況について説明する。論理記憶領域４１は、例えば、物理記憶領域２１ｃの一部領域に対応付けられている。この場合、上記と同様に、制御部２２は、データブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５のハッシュ値Ｈ＃１、…、Ｈ＃５を計算し、ハッシュ値Ｈ＃１、…、Ｈ＃５を順次第１のキャッシュ領域２１ａに格納する。
【００３５】
この例ではハッシュ値Ｈ＃１、…、Ｈ＃４を第１のキャッシュ領域２１ａに格納した時点で第１のキャッシュ領域２１ａは一杯になる。そのため、制御部２２は、図１のＢに示すように、第１のキャッシュ領域２１ａにあるハッシュ値の中で最も古いハッシュ値Ｈ＃１を削除して空き領域を確保し、ハッシュ値Ｈ＃５を第１のキャッシュ領域２１ａに格納する。また、制御部２２は、データブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５にハッシュ値Ｈ＃１、…、Ｈ＃５を付加し、論理記憶領域４１に対応する物理記憶領域２１ｃの範囲にデータブロックｄＢＬＫ＃１、…、ｄＢＬＫ＃５のデータを格納する。
【００３６】
上記の状態で、図１のＣに示すように、論理記憶領域４１にあるデータブロックｄＢＬＫ＃１、ｄＢＬＫ＃２を論理記憶領域４２にコピーする場合、制御部２２は、物理記憶領域２１ｃからデータブロックｄＢＬＫ＃１、ｄＢＬＫ＃２を順次読み出す。また、制御部２２は、データブロックｄＢＬＫ＃１、ｄＢＬＫ＃２に付加されているハッシュ値Ｈ＃１、Ｈ＃２を順次第２のキャッシュ領域２１ｂに格納する。
【００３７】
また、制御部２２は、読み出したデータブロックｄＢＬＫ＃１を論理記憶領域４２に対応する物理記憶領域２１ｃの範囲に格納する前にデータブロックｄＢＬＫ＃１の重複排除が可能か否かを判定する。このとき、制御部２２は、第１のキャッシュ領域２１ａ及び第２のキャッシュ領域２１ｂ内でハッシュ値Ｈ＃１を検索する。
【００３８】
図１のＢに示したように、ハッシュ値Ｈ＃１は第１のキャッシュ領域２１ａから削除されている。そのため、第１のキャッシュ領域２１ａからハッシュ値Ｈ＃１は検出されない（キャッシュＭＩＳＳ）。一方、第２のキャッシュ領域２１ｂには、データブロックｄＢＬＫ＃１の読み出し時に格納されたハッシュ値Ｈ＃１が格納されている。そのため、第２のキャッシュ領域２１ｂからハッシュ値Ｈ＃１が検出される（キャッシュＨＩＴ）。
【００３９】
第２のキャッシュ領域２１ｂからハッシュ値Ｈ＃１が検出されたため、制御部２２は、データブロックｄＢＬＫ＃１の重複排除が可能であると判定する。この場合、制御部２２は、論理記憶領域４１に対応する物理記憶領域２１ｃの範囲と論理記憶領域４２とを対応付け、物理記憶領域２１ｃに対するデータブロックｄＢＬＫ＃１の格納を回避する（重複排除の実施）。同様にデータブロックｄＢＬＫ＃２についても重複排除が実施される。
【００４０】
上記のように、制御部２２は、物理記憶領域２１ｃに対するデータブロックの書き込み要求を受け付けたとき、第１のキャッシュ領域２１ａ又は第２のキャッシュ領域２１ｂに該データブロックのハッシュ値と同じハッシュ値があるかを判定する。そして、制御部２２は、同じハッシュ値がある場合には該データブロックの重複排除を実施する。
【００４１】
コピーを実施する場合、前提として物理記憶領域２１ｃ、３１にコピー対象のデータがある。そのため、データの読み出し時に第２のキャッシュ領域２１ｂでハッシュ値を保存し、書き込み時に第２のキャッシュ領域２１ｂを参照することで、第１のキャッシュ領域２１ａでキャッシュＭＩＳＳになっても重複排除が実施される。
【００４２】
なお、説明の都合上、コピーを実施する場合について説明したが、第２のキャッシュ領域２１ｂを設けることでコピー以外の処理を実施する場合においても重複排除率の向上に寄与しうる。例えば、データの一部を書き換えるとき、物理記憶領域２１ｃ、３１からデータを読み出し、読み出したデータを更新して更新前後のデータを異なる領域に書き込む場合がある。更新部分が少ない場合、多くのデータブロックが同じ内容になる。このような場合もキャッシュＭＩＳＳの低減効果が得られうる。
【００４３】
以上、第１実施形態について説明した。上記のように、読み出し時にハッシュ値を保存しておき、書き込み時に保存したハッシュ値と読み出し時に保存したハッシュ値とを参照して重複排除を実施することで重複排除の効率を改善することができる。
【００４４】
＜２．第２実施形態＞
次に、第２実施形態について説明する。第２実施形態は、重複排除を実施するストレージシステムに適用可能なキャッシュ制御に関する。
【００４５】
［２−１．ストレージシステム］
図２を参照しながら、ストレージシステム１００について説明する。図２は、第２実施形態に係るストレージシステムの一例を示した図である。図２に示したストレージシステム１００は、第２実施形態に係るストレージシステムの一例である。
【００４６】
図２に示すように、ストレージシステム１００は、ホスト装置１０１、及びストレージ装置１０２を有する。ストレージ装置１０２は、ＣＭ１２１、１２２、及び記憶装置１２３を有する。
【００４７】
なお、図２にはストレージ装置１０２に２つのＣＭが搭載される例を示しているが、第２実施形態に係る技術は１つ又は３つ以上のＣＭがストレージ装置１０２に搭載される場合にも適用可能である。また、ＣＭ１２１、１２２は実質的に同じハードウェア及び機能を有するものとし、ＣＭ１２２については詳細な説明を省略する場合がある。
【００４８】
ＣＭ１２１は、複数のＣＡ（Channel Adapter）、複数のＩ／Ｆ（Interface）、プロセッサ１２１ａ、及びメモリ１２１ｂを有する。
ＣＡは、ホスト装置１０１との間の接続制御を実施するアダプタ回路である。例えば、ＣＡは、ＦＣなどの通信回線を介して、ホスト装置１０１に搭載されるＨＢＡ（Host Bus Adapter）や、ＣＡとホスト装置１０１との間に設置されるスイッチに接続される。Ｉ／Ｆは、ＳＡＳやＳＡＴＡなどの回線を介して記憶装置１２３と接続するためのインターフェースである。
【００４９】
プロセッサ１２１ａは、例えば、ＣＰＵ、ＤＳＰ、ＡＳＩＣ、ＦＰＧＡなどである。メモリ１２１ｂは、例えば、ＲＡＭやフラッシュメモリなどである。なお、図２の例ではＣＭ１２１の内部にメモリ１２１ｂが搭載されているが、ＣＭ１２１の外部に接続されたメモリを利用してもよい。
【００５０】
メモリ１２１ｂには、後述する制御情報が格納される制御情報領域（Ｃｔｒｌ）２０１、及びユーザデータが一時的に格納されるユーザデータキャッシュ領域（ＵＤＣ）２０２が設定される。また、メモリ１２１ｂには、書き込みデータのハッシュ値が格納される書き込みハッシュキャッシュ領域（ＷＨＣ）２０３、及び読み出しデータのハッシュ値が格納される読み出しハッシュキャッシュ領域（ＲＨＣ）２０４が設定される。
【００５１】
なお、ＵＤＣ２０２は物理記憶領域の一例である。また、ＵＤＣ２０２、ＷＨＣ２０３、ＲＨＣ２０４の少なくとも一部は、ＣＭ１２１の外部に接続されたメモリに設定されてもよい。また、ＵＤＣ２０２、ＷＨＣ２０３、ＲＨＣ２０４はそれぞれ別のメモリに設定されてもよい。
【００５２】
記憶装置１２３は、記録媒体Ｄ１、…、Ｄｎを有する。記録媒体Ｄ１、…、Ｄｎは、例えば、ＳＳＤやＨＤＤなどである。記録媒体Ｄ１、…、Ｄｎには、異なる種類の記録媒体（ＨＤＤ、ＳＳＤなど）が混在していてもよい。記憶装置１２３に搭載される記録媒体の数ｎは１以上の任意数である。ディスクアレイ（ストレージアレイ）やＲＡＩＤ装置などは記憶装置１２３の一例である。記憶装置１２３は物理記憶領域の一例である。
【００５３】
ＣＭ１２２は、上述したＣＭ１２１と同じ要素を有する。また、ＣＭ１２１、１２２はストレージ装置１０２の内部で接続されており、相互に通信可能である。また、ＣＭ１２２は、ＣＭ１２１と同様に記憶装置１２３へのアクセスが可能である。
【００５４】
以上、ストレージシステム１００について説明した。以下では、図２に示したストレージシステム１００を例に第２実施形態に係るキャッシュ制御について説明する。
［２−２．キャッシュ制御と重複排除］
第２実施形態に係るキャッシュ制御及び重複排除は主にプロセッサ１２１ａにより実施される。
【００５５】
プロセッサ１２１ａは、ユーザデータをＵＤＣ２０２に書き込む際にユーザデータのハッシュ値をＷＨＣ２０３に格納する。また、プロセッサ１２１ａは、ＵＤＣ２０２からユーザデータを読み出す際にユーザデータのハッシュ値をＲＨＣ２０４に格納する。そして、プロセッサ１２１ａは、重複排除を実施する際、ＷＨＣ２０３及びＲＨＣ２０４に格納されているハッシュ値を参照して重複排除の要否を判定する。
【００５６】
ＷＨＣ２０３だけを利用する場合、ＷＨＣ２０３が溢れるとＵＤＣ２０２に同じユーザデータがあっても重複排除が実施されず、内容が重複するユーザデータ（重複データ）がＵＤＣ２０２に書き込まれるリスクが生じうる。その結果、重複データが占める割合（重複率）が増加しうる。言い換えると、重複排除率が低下しうる。一方、ＷＨＣ２０３とＲＨＣ２０４とを併用することで、ＷＨＣ２０３の溢れにより重複排除率が低下するリスクを低減することができる。
【００５７】
なお、ＷＨＣ２０３のサイズを拡大すればキャッシュＭＩＳＳの発生を低減できる。また、書き込まれるユーザデータ（ＷＲＩＴＥデータ）に占める重複データの割合（重複率）が大きければ、ＷＨＣ２０３が溢れるリスクが低くなる。しかし、大容量のＷＨＣ２０３を確保するには非現実的なコストがかかる。また、ＷＲＩＴＥデータの重複率をストレージ装置１０２側で制御することは困難である。そのため、ＲＨＣ２０４を設けて重複排除率が低下するリスクを抑制することは有益である。
【００５８】
以下、上記のキャッシュ制御と重複排除について、さらに説明する。
（書き込み制御と重複排除）
プロセッサ１２１ａは、ホスト装置１０１からＷＲＩＴＥデータの書き込み要求を受け付けたとき、例えば、図３に示すような方法で書き込み制御と重複排除を実施する。図３は、書き込み制御と重複排除について説明するための第１の図である。
【００５９】
書き込み要求を受け付けたプロセッサ１２１ａは、ＷＲＩＴＥデータを所定サイズ（例えば、４ＫＢ）のデータブロックに分割する。図３の例では、ＷＲＩＴＥデータが５つのデータブロックＢ＃１、…、Ｂ＃５に分割されている。プロセッサ１２１ａは、データブロックＢ＃１、…、Ｂ＃５のハッシュ値Ｈ＃１、…、Ｈ＃５を計算し、ハッシュ値Ｈ＃１、…、Ｈ＃５を順次ＷＨＣ２０３のハッシュ値と比較する。
【００６０】
図３の例において、ＷＨＣ２０３には、古い順にハッシュ値Ｈ＃７、Ｈ＃８、Ｈ＃３、Ｈ＃４が格納されている。例えば、プロセッサ１２１ａは、ハッシュ値Ｈ＃１と、ＷＨＣ２０３のハッシュ値Ｈ＃７、Ｈ＃８、Ｈ＃３、Ｈ＃４とをそれぞれ比較する（Search）。この例では、ハッシュ値Ｈ＃１がＷＨＣ２０３に格納されていない。この場合、プロセッサ１２１ａは、ハッシュ値Ｈ＃１とＲＨＣ２０４のハッシュ値とをそれぞれ比較する。
【００６１】
図３の例では、ＲＨＣ２０４にハッシュ値が格納されていない。そのため、プロセッサ１２１ａは、ハッシュ値Ｈ＃１がＷＨＣ２０３及びＲＨＣ２０４のいずれにも格納されていない（キャッシュＭＩＳＳ）と判定する。この場合、プロセッサ１２１ａは、データブロックＢ＃１を重複排除の対象外にし、ハッシュ値Ｈ＃１をＷＨＣ２０３に格納する。
【００６２】
但し、ＷＨＣ２０３にはハッシュ値Ｈ＃７、Ｈ＃８、Ｈ＃３、Ｈ＃４が格納されており、ハッシュ値Ｈ＃１を格納する空き領域が不足している。この場合、プロセッサ１２１ａは、ＷＨＣ２０３の中で最も古いハッシュ値Ｈ＃７を削除し、ＷＨＣ２０３に空き領域を確保する。そして、プロセッサ１２１ａは、ＷＨＣ２０３の空き領域にハッシュ値Ｈ＃１を格納する。このように、ＷＨＣ２０３が溢れる場合には古い順にハッシュ値の削除が実施され、ＷＨＣ２０３の内容が更新される（Update）。
【００６３】
また、プロセッサ１２１ａは、重複排除の対象外であるデータブロックＢ＃１を圧縮し、圧縮後のデータブロックＢ＃１にハッシュ値Ｈ＃１を付加した圧縮データＢＨ＃１を生成する。そして、プロセッサ１２１ａは、圧縮データＢＨ＃１をＵＤＣ２０２に格納する。なお、プロセッサ１２１ａは、ＵＤＣ２０２が溢れうる場合（例えば、空き容量が基準値以下の場合や、使用率が閾値以上の場合など）、ＷＲＩＴＥデータの書き込みとは非同期に、ＵＤＣ２０２に格納されている圧縮データを記憶装置１２３に書き出す。
【００６４】
上記のように、キャッシュＭＩＳＳが生じた場合には図３のような処理が実行される。一方、ＷＨＣ２０３又はＲＨＣ２０４に比較対象のハッシュ値がある場合（キャッシュＨＩＴ）、図４のような処理が実行される。図４は、書き込み制御と重複排除について説明するための第２の図である。
【００６５】
図４の例において、ＷＨＣ２０３には、古い順にハッシュ値Ｈ＃３、Ｈ＃４、Ｈ＃１、Ｈ＃２が格納されている。例えば、プロセッサ１２１ａは、ハッシュ値Ｈ＃４と、ＷＨＣ２０３のハッシュ値Ｈ＃３、Ｈ＃４、Ｈ＃１、Ｈ＃２とをそれぞれ比較する（Search）。この例では、ハッシュ値Ｈ＃４がＷＨＣ２０３に格納されている。この場合、プロセッサ１２１ａは、データブロックＢ＃４を重複排除の対象とする。
【００６６】
また、プロセッサ１２１ａは、ＷＨＣ２０３の中でハッシュ値Ｈ＃４を最新の位置に移動する。このように、ＷＨＣ２０３が溢れない場合にはハッシュ値の移動が実施され、ＷＨＣ２０３の内容が更新される（Update）。なお、データブロックＢ＃４は重複排除の対象であるため、データブロックＢ＃４及びハッシュ値Ｈ＃４のＵＤＣ２０２への書き込みは回避される。また、プロセッサ１２１ａは、ＵＤＣ２０２又は記憶装置１２３におけるデータブロックＢ＃４の位置（圧縮データＢＨ＃４のアドレス）と書き込み先とを対応付け、書き込み完了の応答をホスト装置１０１に返す。
【００６７】
プロセッサ１２１ａは、プログラムの実行により上記のような方法で書き込み制御及び重複排除を実施する。
（ＷＨＣの構造）
ここで、図５を参照しながら、ＷＨＣ２０３の構造について説明する。図５は、ＷＨＣの構造について説明するための図である。なお、図５に示す構造は一例であり、ＷＨＣ２０３の構造は変形してもよい。ＲＨＣ２０４もＷＨＣ２０３と同じ構造に設定しうる。
【００６８】
図５に示すように、ＷＨＣ２０３では、１つのデータブロックに対応するハッシュ値をエントリと呼ばれる単位で管理する。また、Ｍ個（例えば、Ｍ＝１２８）のエントリを纏めた単位をバンドルと呼ぶ場合がある。バンドルには、バンドルの識別情報などが含まれるヘッダと、Ｍ個のエントリが登録されうるエントリ領域とが含まれる。エントリには、ハッシュ値やスロット番号（後述）と共にエントリの位置を示すポインタが含まれる。
【００６９】
プロセッサ１２１ａは、個々のバンドル内でエントリの新旧を管理し、エントリ領域が溢れると最も古いエントリを削除して新たなエントリを格納する。なお、ハッシュ値の格納先となるバンドルの決め方としては、例えば、ハッシュ値をバンドルの総数で割った値に基づいて格納先を決める方法などがある。この方法によれば、検索の際には、既知であるバンドルの総数を用いてハッシュ値から格納先を特定することができる。
【００７０】
（読み出し制御）
次に、図６を参照しながら、読み出し制御について説明する。図６は、読み出し制御について説明するための図である。
【００７１】
例えば、ＵＤＣ２０２からデータブロックＢ＃１を読み出す場合、プロセッサ１２１ａは、図６に示すような処理を実行する。なお、データブロックＢ＃１に対応する圧縮データＢＨ＃１が記憶装置１２３だけに格納されている場合、プロセッサ１２１ａは、記憶装置１２３から圧縮データＢＨ＃１を読み出してＵＤＣ２０２に格納する。
【００７２】
プロセッサ１２１ａは、ＵＤＣ２０２から圧縮データＢＨ＃１を読み出し、圧縮後のデータブロックＢ＃１を伸長して圧縮前のデータブロックＢ＃１を復元する。また、プロセッサ１２１ａは、圧縮データＢＨ＃１に含まれるハッシュ値Ｈ＃１を取得し、ハッシュ値Ｈ＃１をＲＨＣ２０４に格納する。また、プロセッサ１２１ａは、読み出し要求に対する応答としてデータブロックＢ＃１をホスト装置１０１に送信する。
【００７３】
図６の例では、ＲＨＣ２０４に空き領域があり、そのままハッシュ値Ｈ＃１をＲＨＣ２０４に格納できる。仮にＲＨＣ２０４が溢れる場合には、ＷＨＣ２０３と同様、古いハッシュ値を削除して得られる空き領域にハッシュ値Ｈ＃１が格納される。読み出し時の処理は上記のようになる。
【００７４】
（データコピー時の重複排除）
次に、図７及び図８を参照しながら、データコピー時の重複排除について説明する。図７は、データコピー時の重複排除について説明するための第１の図である。図８は、データコピー時の重複排除について説明するための第２の図である。
【００７５】
図７のＡに示すように、ＷＲＩＴＥ命令により、ホスト装置１０１からストレージ装置１０２にデータブロックＢ＃１、…、Ｂ＃５を含むＷＲＩＴＥデータが書き込まれていると仮定する。ＷＨＣ２０３が空の状態でデータブロックＢ＃１、…、Ｂ＃５がＵＤＣ２０２に書き込まれる場合、図７のＢに示すように、ＷＨＣ２０３には、古い順にハッシュ値Ｈ＃２、…、Ｈ＃５が格納される。他方、図７のＣに示すように、ＲＨＣ２０４は空であると仮定する。
【００７６】
既に説明したように、データブロックＢ＃１、…、Ｂ＃５をＵＤＣ２０２に書き込むとき、プロセッサ１２１ａは、データブロックＢ＃１、…、Ｂ＃５を圧縮し、ハッシュ値Ｈ＃１、…、Ｈ＃５を付加した圧縮データＢＨ＃１、…、ＢＨ＃５を生成する。そして、圧縮データＢＨ＃１、…、ＢＨ＃５がＵＤＣ２０２に格納される。
【００７７】
ＵＤＣ２０２の空き容量や使用率に基づく所定の条件を満たした場合、ＷＲＩＴＥ命令に応じた処理とは非同期に、ＵＤＣ２０２に格納されている圧縮データＢＨ＃１、…、ＢＨ＃５は、図７のＤに示すように、記憶装置１２３に書き出される。書き出しの後、ＵＤＣ２０２に格納されていた圧縮データＢＨ＃１、…、ＢＨ＃５はＵＤＣ２０２に空きがあればそのまま保持し、空きがなければ削除される。
【００７８】
上記の処理が完了した状態で、図７のＥに示すように、ホスト装置１０１からストレージ装置１０２が上記ＷＲＩＴＥデータのコピー命令を受けると、プロセッサ１２１ａは、圧縮データＢＨ＃１、…、ＢＨ＃５のコピーを実施する。このとき、プロセッサ１２１ａは、図８のような方法でキャッシュ制御及び重複排除を実施する。
【００７９】
プロセッサ１２１ａは、コピー対象のデータブロックＢ＃１を含む圧縮データＢＨ＃１を記憶装置１２３から読み出してＵＤＣ２０２に格納する。また、プロセッサ１２１ａは、図８に示すように、圧縮データＢＨ＃１からハッシュ値Ｈ＃１を取得し、取得したハッシュ値Ｈ＃１をＲＨＣ２０４に格納する。
【００８０】
次に、プロセッサ１２１ａは、ＷＨＣ２０３内でハッシュ値Ｈ＃１を検索する（Write時のSearch）。図７のＢに示したようにＷＨＣ２０３にはハッシュ値Ｈ＃１が格納されていない。そのため、ＷＨＣ２０３についてはキャッシュＭＩＳＳになる。この場合、プロセッサ１２１ａは、ＲＨＣ２０４内でハッシュ値Ｈ＃１を検索する（Write時のSearch）。上記のように、圧縮データＢＨ＃１から取得されたハッシュ値Ｈ＃１がＲＨＣ２０４に格納されている（キャッシュＨＩＴ）。
【００８１】
ＲＨＣ２０４でキャッシュＨＩＴしたため、プロセッサ１２１ａは、データブロックＢ＃１の重複排除を実施する。例えば、プロセッサ１２１ａは、データブロックＢ＃１のコピー先となる論理アドレス（ＬＢＡ：Logical Block Addressing）と、圧縮データＢＨ＃１の物理アドレスとを対応付ける。この場合、プロセッサ１２１ａは、新たに圧縮データＢＨ＃１をＵＤＣ２０２に格納する処理を回避する。また、プロセッサ１２１ａは、データブロックＢ＃１のコピーが完了した旨の応答をホスト装置１０１に返す。
【００８２】
データコピーのように、既存のデータブロックを読み出して別の論理アドレスに書き込む場合、重複するデータブロックが確実に存在する。そのため、読み出し時にＲＨＣ２０４でハッシュ値を捕捉し、そのハッシュ値を書き込み時に参照することで重複排除の漏れを防止することができる。
【００８３】
ここで、図９を参照しながら、制御情報領域２０１に格納される制御情報２０１ａについて説明する。図９は、制御情報の一例を示した図である。
図９に示すように、制御情報２０１ａは、ハッシュ情報２１１、ブロックマップ２１２、及びコンテナメタ情報２１３を有する。
【００８４】
既に述べたように、ストレージ装置１０２において、ユーザデータは、所定サイズを有するデータブロックに分割され、データブロックの単位で管理される。データブロックの格納先はスロット番号により管理される。例えば、データブロックＢ＃１、Ｂ＃２、Ｂ＃３、…の格納先は、それぞれスロット番号１、２、３、…に対応付けられる。
【００８５】
ハッシュ情報２１１は、ハッシュ値とスロット番号とを対応付ける情報である。例えば、ハッシュ情報２１１は、スロット番号１、２、３、…にハッシュ値Ｈ＃１、Ｈ＃２、Ｈ＃３、…を対応付ける。データブロックとハッシュ値とは１対１に対応するため、ハッシュ情報２１１は、スロット番号とデータブロックとを対応付けている。
【００８６】
ブロックマップ２１２は、データブロックの格納位置を示す論理アドレスと、そのデータブロックに対応するスロット番号とを対応付ける情報である。論理アドレスは、例えば、論理ボリューム、仮想ディスク、ＬＵＮ（Logical Unit Number）などで表現される論理記憶領域内の位置を示すアドレスである。重複排除の対象となるデータブロックの場合、複数の論理アドレスに同じスロット番号が対応付けられる。
【００８７】
上記のように、スロット番号とデータブロックとが対応するため、ブロックマップ２１２を介してデータブロックと論理アドレスとが対応付けられる。重複排除を実施した場合、同じデータブロックが複数の論理アドレスから参照されるため、上記のように、複数の論理アドレスに同じスロット番号が対応付けられる。図９の例では、論理アドレスｘ２、ｘ１０にスロット番号２が対応付けられている。
【００８８】
コンテナメタ情報２１３は、スロット番号と、そのスロット番号に対応するデータブロックの格納位置を示す物理アドレスとを対応付ける情報である。なお、コンテナメタ情報２１３には、データブロックの圧縮サイズが含まれていてもよい。物理アドレスは、ＵＤＣ２０２又は記憶装置１２３により提供される物理記憶領域内の位置を示すアドレスである。ブロックマップ２１２及びコンテナメタ情報２１３から、各データブロックの論理アドレスと物理アドレスとの対応関係を特定することができる。
【００８９】
なお、制御情報２０１ａはメタデータと呼ばれる場合がある。また、制御情報２０１ａの少なくとも一部は記憶装置１２３に格納されてもよい。
以上、第２実施形態に係るキャッシュ制御及び重複排除について説明した。
【００９０】
［２−３．処理の流れ］
次に、ストレージ装置１０２による処理の流れについて説明する。
（ＷＲＩＴＥ時の処理）
まず、図１０を参照しながら、ＷＲＩＴＥ時の処理の流れについて説明する。図１０は、ＷＲＩＴＥ時の処理の流れを示したフロー図である。
【００９１】
（Ｓ１０１）ホスト装置１０１からＷＲＩＴＥデータの書き込み要求を受けると、プロセッサ１２１ａは、ＷＲＩＴＥデータを複数のデータブロックに分割する。また、プロセッサ１２１ａは、各データブロックのハッシュ値を計算する。
【００９２】
（Ｓ１０２）プロセッサ１２１ａは、Ｓ１０１で計算した複数のハッシュ値から未選択のハッシュ値を１つ選択する。なお、Ｓ１０２で選択されたハッシュ値を選択ハッシュ値と表記する場合がある。
【００９３】
（Ｓ１０３）プロセッサ１２１ａは、選択ハッシュ値がＷＨＣ２０３にあるか否かを判定する。選択ハッシュ値がＷＨＣ２０３にある場合、処理はＳ１０４へと進む。一方、選択ハッシュ値がＷＨＣ２０３にない場合、処理はＳ１０５へと進む。
【００９４】
（Ｓ１０４）プロセッサ１２１ａは、選択ハッシュ値が最新になるように、ＷＨＣ２０３内で選択ハッシュ値の位置を移動する（図４を参照）。Ｓ１０４の処理が完了すると、処理はＳ１０８へと進む。
【００９５】
（Ｓ１０５）プロセッサ１２１ａは、ＷＨＣ２０３に選択ハッシュ値を格納する。ＷＨＣ２０３に空きがない場合、プロセッサ１２１ａは、ＷＨＣ２０３内で最も古いハッシュ値を削除して空き領域を確保する。そして、プロセッサ１２１ａは、ＷＨＣ２０３に選択ハッシュ値を格納する（図３を参照）。
【００９６】
（Ｓ１０６）プロセッサ１２１ａは、選択ハッシュ値がＲＨＣ２０４にあるか否かを判定する。選択ハッシュ値がＲＨＣ２０４にある場合、処理はＳ１０８へと進む。一方、選択ハッシュ値がＲＨＣ２０４にない場合、処理はＳ１０７へと進む。
【００９７】
（Ｓ１０７）プロセッサ１２１ａは、選択ハッシュ値に対応するデータブロックを圧縮する。また、プロセッサ１２１ａは、圧縮後のデータブロックに選択ハッシュ値を付加して圧縮データを生成し、圧縮データをＵＤＣ２０２に格納する。
【００９８】
（Ｓ１０８）プロセッサ１２１ａは、制御情報２０１ａを更新する。
（更新内容＃１）選択ハッシュ値がＷＨＣ２０３にあった場合（Ｓ１０３：ＹＥＳ）、プロセッサ１２１ａは、ハッシュ情報２１１を参照して選択ハッシュ値に対応するスロット番号を特定する。また、プロセッサ１２１ａは、選択ハッシュ値の書き込み先である論理アドレスをブロックマップ２１２に登録し、登録した論理アドレスと、特定したスロット番号とを対応付ける。これにより選択ハッシュ値に対応するデータブロックの重複が排除される。
【００９９】
（更新内容＃２）選択ハッシュ値がＲＨＣ２０４にあった場合（Ｓ１０６：ＹＥＳ）、プロセッサ１２１ａは、ハッシュ情報２１１を参照して選択ハッシュ値に対応するスロット番号を特定する。また、プロセッサ１２１ａは、選択ハッシュ値の書き込み先である論理アドレスをブロックマップ２１２に登録し、登録した論理アドレスと、特定したスロット番号とを対応付ける。これにより選択ハッシュ値に対応するデータブロックの重複が排除される。
【０１００】
（更新内容＃３）選択ハッシュ値がＷＨＣ２０３及びＲＨＣ２０４のいずれにもない場合（Ｓ１０３：ＮＯ、Ｓ１０６：ＮＯ）、プロセッサ１２１ａは、選択ハッシュ値の書き込み先である論理アドレスをブロックマップ２１２に登録し、登録した論理アドレスと新たに確保したスロット番号とを対応付ける。また、プロセッサ１２１ａは、ハッシュ情報２１１に新たなスロット番号を登録し、登録したスロット番号と選択ハッシュ値とを対応付ける。
【０１０１】
また、プロセッサ１２１ａは、コンテナメタ情報２１３に新たなスロット番号を登録し、登録したスロット番号と、選択ハッシュ値に対応するデータブロックの格納先となる物理アドレス（この場合はＵＤＣ２０２内の位置を示すアドレス）とを対応付ける。また、プロセッサ１２１ａは、コンテナメタ情報２１３に登録したスロット番号と、データブロックの圧縮サイズとを対応付ける。
【０１０２】
（Ｓ１０９）プロセッサ１２１ａは、ハッシュ値を選択し終えたか否かを判定する。未選択のハッシュ値がある場合、処理はＳ１０２へと進む。一方、ハッシュ値を選択し終えた場合、処理はＳ１１０へと進む。
【０１０３】
（Ｓ１１０）プロセッサ１２１ａは、書き込み要求に対する応答として、ＷＲＩＴＥデータの書き込みが完了した旨の通知をホスト装置１０１に送信する。Ｓ１１０の処理が完了すると、図１０に示した一連の処理は終了する。
【０１０４】
（ＲＥＡＤ時の処理）
次に、図１１を参照しながら、ＲＥＡＤ時の処理の流れについて説明する。図１１は、ＲＥＡＤ時の処理の流れを示したフロー図である。
【０１０５】
（Ｓ１１１）ホスト装置１０１からＲＥＡＤデータの読み出し要求を受けたとき、プロセッサ１２１ａは、ＲＥＡＤデータがＵＤＣ２０２にあるか否かを判定する。
例えば、プロセッサ１２１ａは、ブロックマップ２１２及びコンテナメタ情報２１３を参照し、読み出し元の論理アドレスに対応する物理アドレスがＵＤＣ２０２に対応するか、記憶装置１２３に対応するかを判定する。
【０１０６】
読み出し元の論理アドレスがＵＤＣ２０２の物理アドレスに対応する場合、プロセッサ１２１ａは、ＲＥＡＤデータがＵＤＣ２０２にあると判定する。一方、読み出し元の論理アドレスが記憶装置１２３の物理アドレスに対応する場合、プロセッサ１２１ａは、ＲＥＡＤデータが記憶装置１２３にあると判定する。
【０１０７】
ＲＥＡＤデータがＵＤＣ２０２にある場合、処理はＳ１１３へと進む。一方、ＲＥＡＤデータがＵＤＣ２０２にない場合（記憶装置１２３にある場合）、処理はＳ１１２へと進む。
【０１０８】
（Ｓ１１２）プロセッサ１２１ａは、ＲＥＡＤデータを記憶装置１２３から読み出してＵＤＣ２０２に格納する。例えば、プロセッサ１２１ａは、ブロックマップ２１２及びコンテナメタ情報２１３を参照し、読み出し元の論理アドレスに対応する物理アドレスを特定する。そして、プロセッサ１２１ａは、特定した物理アドレスにある圧縮データを読み出してＵＤＣ２０２に格納する。
【０１０９】
（Ｓ１１３）プロセッサ１２１ａは、ＵＤＣ２０２に格納した圧縮データに含まれる圧縮後のデータブロックを伸長して圧縮前のデータブロックを復元する。また、プロセッサ１２１ａは、復元した複数のデータブロックを結合してＲＥＡＤデータを復元する。そして、プロセッサ１２１ａは、読み出し要求に対する応答として、復元したＲＥＡＤデータをホスト装置１０１に送信する。
【０１１０】
（Ｓ１１４）プロセッサ１２１ａは、圧縮データに含まれるハッシュ値を取得し、取得したハッシュ値をＲＨＣ２０４に格納する（図８を参照）。Ｓ１１４の処理が完了すると、図１１に示した一連の処理は終了する。
【０１１１】
以上、ストレージ装置１０２による処理の流れについて説明した。上記のように、読み出し時にハッシュ値を保存しておき、書き込み時に保存したハッシュ値と読み出し時に保存したハッシュ値とを参照して重複排除を実施することで重複排除の効率を改善することができる。
【０１１２】
以上、第２実施形態について説明した。
なお、上述したホスト装置１０、１０１、ストレージ制御装置２０、ストレージ装置１０２（ＣＭ１２１、ＣＭ１２２）の機能は、これらの装置に搭載されるプロセッサにプログラムを実行させることで実現できる。
【０１１３】
上記プログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（Re-Writable）などがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。
【０１１４】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１１５】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラム又はサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、ネットワークを介して接続されたサーバコンピュータからプログラムが転送される度に、逐次、サーバコンピュータから受け取ったプログラムに従った処理を実行することもできる。
【０１１６】
＜３．付記＞
以上説明した実施形態に関し、さらに以下の付記を開示する。
（付記１）  物理記憶領域に書き込まれるデータブロックのハッシュ値が格納される第１のキャッシュ領域と、前記物理記憶領域から読み出されるデータブロックのハッシュ値が格納される第２のキャッシュ領域とを有するキャッシュメモリと、
前記物理記憶領域に対するデータブロックの書き込み要求を受け付けたとき、前記第１のキャッシュ領域又は前記第２のキャッシュ領域に該データブロックのハッシュ値と同じハッシュ値があるかを判定し、前記同じハッシュ値がある場合には該データブロックの重複排除を実施する制御部と
を有する、ストレージ制御装置。
【０１１７】
（付記２）  前記制御部は、前記書き込み要求を受け付けたとき、前記第１のキャッシュ領域を対象に該データブロックのハッシュ値と同じハッシュ値の検索を実施し、前記同じハッシュ値がない場合には前記第２のキャッシュ領域を対象に前記同じハッシュ値の検索を実施する
付記１に記載のストレージ制御装置。
【０１１８】
（付記３）  前記制御部は、新たなハッシュ値の格納により前記第１のキャッシュ領域が溢れる場合に前記第１のキャッシュ領域のハッシュ値を古い順に削除する
付記２に記載のストレージ制御装置。
【０１１９】
（付記４）  前記物理記憶領域に書き込まれるデータブロックには該データブロックのハッシュ値が付加されており、
前記制御部は、前記物理記憶領域から読み出したデータブロックに付加されているハッシュ値を取得し、取得した該ハッシュ値を前記第２のキャッシュ領域に格納する
付記３に記載のストレージ制御装置。
【０１２０】
（付記５）  物理記憶領域に書き込まれるデータブロックのハッシュ値を第１のキャッシュ領域に格納し、前記物理記憶領域から読み出されるデータブロックのハッシュ値を第２のキャッシュ領域に格納し、
前記物理記憶領域に対するデータブロックの書き込み要求を受け付けたとき、前記第１のキャッシュ領域又は前記第２のキャッシュ領域に該データブロックのハッシュ値と同じハッシュ値があるかを判定し、前記同じハッシュ値がある場合には該データブロックの重複排除を実施する
処理をコンピュータに実行させる、プログラム。
【０１２１】
（付記６）  コンピュータが、
物理記憶領域に書き込まれるデータブロックのハッシュ値を第１のキャッシュ領域に格納し、前記物理記憶領域から読み出されるデータブロックのハッシュ値を第２のキャッシュ領域に格納し、
前記物理記憶領域に対するデータブロックの書き込み要求を受け付けたとき、前記第１のキャッシュ領域又は前記第２のキャッシュ領域に該データブロックのハッシュ値と同じハッシュ値があるかを判定し、前記同じハッシュ値がある場合には該データブロックの重複排除を実施する
重複排除方法。
【０１２２】
（付記７）  前記書き込み要求を受け付けたとき、前記第１のキャッシュ領域を対象に該データブロックのハッシュ値と同じハッシュ値の検索を実施し、前記同じハッシュ値がない場合には前記第２のキャッシュ領域を対象に前記同じハッシュ値の検索を実施する
処理をコンピュータに実行させる、付記５に記載のプログラム。
【０１２３】
（付記８）  新たなハッシュ値の格納により前記第１のキャッシュ領域が溢れる場合に前記第１のキャッシュ領域のハッシュ値を古い順に削除する
処理をコンピュータに実行させる、付記７に記載のプログラム。
【０１２４】
（付記９）  前記物理記憶領域に書き込まれるデータブロックには該データブロックのハッシュ値が付加されており、
前記物理記憶領域から読み出したデータブロックに付加されているハッシュ値を取得し、取得した該ハッシュ値を前記第２のキャッシュ領域に格納する
処理をコンピュータに実行させる、付記８に記載のプログラム。
【符号の説明】
【０１２５】
１０  ホスト装置
２０  ストレージ制御装置
２１  キャッシュメモリ
２１ａ  第１のキャッシュ領域
２１ｂ  第２のキャッシュ領域
２１ｃ、３１  物理記憶領域
２２  制御部
２３  記憶部
３０  記憶装置
３２、３３、３４  記録媒体
４１、４２  論理記憶領域
ｄＢＬＫ＃１、…、ｄＢＬＫ＃５  データブロック
Ｈ＃１、…、Ｈ＃５  ハッシュ値
【図１】
2019028954.tif 000003
【図２】
2019028954.tif 000004
【図３】
2019028954.tif 000005
【図４】
2019028954.tif 000006
【図５】
2019028954.tif 000007
【図６】
2019028954.tif 000008
【図７】
2019028954.tif 000009
【図８】
2019028954.tif 000010
【図９】
2019028954.tif 000011
【図１０】
2019028954.tif 000012
【図１１】
2019028954.tif 000013