(57)【要約】【課題】ハッシュ値検索管理情報用メモリ領域のサイズを大きくすることなく、データ重複排除効率の向上をはかる。【解決手段】記憶装置３１を制御するストレージ制御装置１は、第１配置制御部１５１および第２配置制御部１５２を含む。第１配置制御部１５１は、記憶装置３１に格納される各単位データについてのハッシュ値を含む第１管理情報を、所定サイズの第１メモリ領域１６３に配置する。第２配置制御部１５２は、前記所定サイズを超えた第１管理情報を、第２管理情報として、第１メモリ領域１６３とは異なる第２メモリ領域３１１に配置する。また、第２配置制御部１５２は、前記第２管理情報における各単位データについてのハッシュ値を検索するインデックス情報を、第１メモリ領域１６３を含む第１メモリ１０６におけるインデックス情報用メモリ領域１６４に配置する。【選択図】図２
2017049806.tif 000002
【特許請求の範囲】
【請求項１】
記憶装置を制御するストレージ制御装置であって、
前記記憶装置に格納される複数の単位データのそれぞれについてのハッシュ値と物理格納情報とを含む第１管理情報を、所定サイズの第１メモリ領域に配置する第１配置制御部と、
前記所定サイズを超えた前記第１管理情報を、第２管理情報として、前記第１メモリ領域とは異なる第２メモリ領域に配置するとともに、前記第２管理情報における各単位データについてのハッシュ値を検索するインデックス情報を、前記第１メモリ領域を含む第１メモリにおけるインデックス情報用メモリ領域に配置する第２配置制御部と、を有する、ストレージ制御装置。
【請求項２】
前記第２配置制御部は、
前記第２管理情報における各単位データについての書込シーケンス時の重複参照回数が基準値以上である上位単位データに対応する上位エントリのハッシュ値を検索する上位インデックス情報を、前記インデックス情報として、前記第１メモリにおける前記インデックス情報用メモリ領域に配置する、請求項１に記載のストレージ制御装置。
【請求項３】
前記第２配置制御部は、
前記重複参照回数が前記基準値未満である下位単位データに対応する下位エントリのハッシュ値を検索する下位インデックス情報を、前記第２メモリ領域を含む第２メモリにおける下位インデックス情報用メモリ領域に配置する、請求項２に記載のストレージ制御装置。
【請求項４】
前記第１メモリは、前記ストレージ制御装置によって用いられる、前記記憶装置の制御用のメモリであり、
前記第２メモリは、前記記憶装置である、請求項３に記載のストレージ制御装置。
【請求項５】
書込対象単位データの検索用ハッシュ値を生成するハッシュ値生成部と、
前記ハッシュ値生成部が生成した検索用ハッシュ値について前記第１管理情報を検索し、前記検索用ハッシュ値が前記第１管理情報に含まれるか否かを判定する第１判定部と、
前記第１判定部が前記検索用ハッシュ値が前記第１管理情報に含まれないと判定した場合、前記検索用ハッシュ値について前記上位インデックス情報を参照し、前記検索用ハッシュ値が前記第２管理情報の前記上位エントリに含まれるか否かを判定する第２判定部と、
前記第１判定部が前記検索用ハッシュ値が前記第１管理情報に含まれると判定した場合、または、前記第２判定部が前記検索用ハッシュ値が前記第２管理情報の前記上位エントリに含まれると判定した場合、前記書込対象単位データについて重複排除処理を行なう重複排除部と、を有する、請求項３または請求項４に記載のストレージ制御装置。
【請求項６】
前記第２判定部が前記検索用ハッシュ値が前記第２管理情報の前記上位エントリに含まれないと判定した場合、前記検索用ハッシュ値について前記下位インデックス情報を参照し、前記検索用ハッシュ値が前記第２管理情報の前記下位エントリに含まれるか否かを判定する第３判定部を有し、
前記第３判定部が前記検索用ハッシュ値が前記第２管理情報の前記下位エントリに含まれると判定した場合、前記重複排除部は、前記重複排除処理を行なう、請求項５に記載のストレージ制御装置。
【請求項７】
前記第３判定部が前記検索用ハッシュ値が前記第２管理情報の前記下位エントリに含まれないと判定し且つ前記第１メモリ領域に空きがない場合、
前記第２配置制御部は、前記第１管理情報における他のハッシュ値を前記第２管理情報に追加登録し、前記他のハッシュ値に対応する単位データについての前記重複参照回数を参照し、参照した前記重複参照回数が前記基準値以上である場合、前記他のハッシュ値を前記上位インデックス情報に登録し、
前記第１配置制御部は、前記第１管理情報において前記他のハッシュ値に代え前記検索用ハッシュ値を登録する、請求項６に記載のストレージ制御装置。
【請求項８】
参照した前記重複参照回数が前記基準値未満である場合、前記第２配置制御部は、前記他のハッシュ値を前記下位インデックス情報に登録する、請求項７に記載のストレージ制御装置。
【請求項９】
前記第１判定部が前記検索用ハッシュ値が前記第１管理情報に含まれないと判定し且つ前記第１メモリ領域に空きがある場合、前記第１配置制御部は、前記検索用ハッシュ値を前記第１管理情報に追加登録する、請求項５〜請求項８のいずれか一項に記載のストレージ制御装置。
【請求項１０】
記憶装置を制御するコンピュータに、
前記記憶装置に格納される複数の単位データのそれぞれについてのハッシュ値と物理格納情報とを含む第１管理情報を、所定サイズの第１メモリ領域に配置し、
前記所定サイズを超えた前記第１管理情報を、第２管理情報として、前記第１メモリ領域とは異なる第２メモリ領域に配置するとともに、
前記第２管理情報における各単位データについてのハッシュ値を検索するインデックス情報を、前記第１メモリ領域を含む第１メモリにおけるインデックス情報用メモリ領域に配置する、処理を実行させる、ストレージ制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、ストレージ制御装置およびストレージ制御プログラムに関する。
【背景技術】
【０００２】
業務で取り扱うデータ量の増大や仮想環境の普及に伴って、ストレージ（記憶装置）の使用量は著しく増大している。このため、ストレージシステムでは、限られたストレージの容量を効率的に利用可能にすべく、ストレージ制御装置によるデータ重複排除機能が採用される場合がある。ここで、ストレージは、例えばＨＤＤ（Hard Disk Drive），ＳＳＤ（Solid State Drive）等のドライブである。
【０００３】
データ重複排除機能を有するストレージ制御装置では、書込対象単位データをストレージに書き込む際、書込対象単位データについての特徴量であるハッシュ値（フィンガプリントとも呼ぶ）が算出される。そして、算出されたハッシュ値とストレージ内に既に格納された単位データのハッシュ値とを比較し一致／不一致を判断することで、書込対象単位データが既存データであるか新規データであるかの判断が行なわれる。
【０００４】
なお、既に格納された単位データのハッシュ値は、当該単位データの書込先の物理アドレスに対応付けられて、データ重複排除用ハッシュ値検索テーブル（ハッシュキャッシュとも呼ぶ）に登録されている。データ重複排除用ハッシュ値検索テーブルに係る情報は、ストレージ制御装置におけるストレージ制御用のメモリに保存される。
【０００５】
上記判断の結果、書込対象単位データが既存データである場合、書込対象単位データをストレージに書き込まないことにより、データ重複排除が行なわれる。一方、上記判断の結果、書込対象単位データが新規データである場合、書込対象単位データにストレージ内の書込先の物理アドレスが割り当てられ、書込対象単位データは、割り当てられた物理アドレスに書き込まれる。そして、ストレージ制御装置では、データ重複排除用ハッシュ値検索テーブルに、書込対象単位データについて算出されたハッシュ値と割り当てられた物理アドレスとが対応付けられて追加登録される。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００９−２５１７２５号公報
【特許文献２】特開２０１４−１３０５４９号公報
【特許文献３】特表２０１３−５０８８１０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
データ重複排除用ハッシュ値検索テーブルに係る情報は、ストレージ制御装置による制御対象のストレージ（ＨＤＤ，ＳＳＤ等のドライブ）ではなく、ストレージ制御装置内のメモリに保存される。これは、ドライブへ保存した場合のアクセスコストがストレージシステムの性能に大きな影響を与えるためである。なお、以下、データ重複排除用ハッシュ値検索テーブルを、管理情報またはテーブルまたはハッシュキャッシュという場合がある。
【０００８】
一方、ストレージシステムのメモリコストに鑑みると、テーブルのサイズを極力小さくしてメモリコストを削減することが望ましい。しかし、テーブルのサイズを小さくするとテーブルに登録されるハッシュ値の数が減ることになり、書込対象単位データのハッシュ値でテーブルを検索してもヒットする可能性が低くなる。つまり、データ重複の検出可能性が低くなり、結果として、データ重複排除効率が低下し、限られたストレージの容量を効率的に利用することができない。
【０００９】
一つの側面で、本件明細書に開示の発明は、ハッシュ値検索管理情報用メモリ領域のサイズを大きくすることなく、データ重複排除効率の向上をはかることを目的とする。
【課題を解決するための手段】
【００１０】
本件のストレージ制御装置は、記憶装置を制御するものであって、第１配置制御部および第２配置制御部を有する。前記第１配置制御部は、前記記憶装置に格納される複数の単位データのそれぞれについてのハッシュ値と物理格納情報とを含む第１管理情報を、所定サイズの第１メモリ領域に配置する。前記第２配置制御部は、前記所定サイズを超えた前記第１管理情報を、第２管理情報として、前記第１メモリ領域とは異なる第２メモリ領域に配置する。また、前記第２配置制御部は、前記第２管理情報における各単位データについてのハッシュ値を検索するインデックス情報を、前記第１メモリ領域を含む第１メモリにおけるインデックス情報用メモリ領域に配置する。
【発明の効果】
【００１１】
一実施形態によれば、ハッシュ値検索管理情報用メモリ領域のサイズを大きくすることなく、データ重複排除効率を向上させることができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施形態としてのストレージ制御装置を含むストレージ装置のハードウェア構成の一例を示すブロック図である。
【図２】本発明の一実施形態としてのストレージ制御装置の機能構成の一例を示すブロック図である
【図３】本実施形態のメモリ（第１メモリ）における第１ハッシュキャッシュ用メモリ領域（第１メモリ領域）および上位インデックス情報用メモリ領域に格納される情報を説明する図である。
【図４】本実施形態の記憶装置（第２メモリ）における第２ハッシュキャッシュ用メモリ領域（第２メモリ領域），上位インデックス情報用メモリ領域および下位インデックス情報用メモリ領域に格納される情報を説明する図である。
【図５】本実施形態のストレージ制御装置の動作概要を説明する図である。
【図６】本実施形態のストレージ制御装置の動作概要を説明する図である。
【図７】本実施形態のストレージ制御装置の動作概要を説明する図である。
【図８】本実施形態との比較対象になる関連技術による重複排除検索手順を説明するフローチャートである。
【図９】書込動作時における本実施形態の重複排除検索手順を説明するフローチャートである。
【図１０】書込動作時における本実施形態の重複排除検索手順を説明するフローチャートである。
【図１１】書込動作時における本実施形態の重複排除検索手順を説明するフローチャートである。
【図１２】本実施形態のハッシュ値登録手順を説明するフローチャートである。
【図１３】本実施形態のハッシュ値登録手順を説明するフローチャートである。
【発明を実施するための形態】
【００１３】
以下に、図面を参照し、本願の開示するストレージ制御装置およびストレージ制御プログラムの実施形態について、詳細に説明する。ただし、以下に示す実施形態は、あくまでも例示に過ぎず、実施形態で明示しない種々の変形例や技術の適用を排除する意図はない。すなわち、本実施形態を、その趣旨を逸脱しない範囲で種々変形して実施することができる。また、各図は、図中に示す構成要素のみを備えるという趣旨ではなく、他の機能を含むことができる。そして、各実施形態は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【００１４】
〔１〕本実施形態のストレージ装置のハードウェア構成
まず、図１を参照しながら、本実施形態のストレージ制御装置１００を含むストレージ装置１について説明する。なお、図１は、本実施形態のストレージ制御装置１００を含むストレージ装置１のハードウェア構成の一例を示すブロック図である。
【００１５】
本ストレージ装置１は、ドライブエンクロージャ（ＤＥ：Drive Enclosure）３０に格納された記憶装置（第２メモリ）３１を仮想化して、仮想ストレージ環境を形成する。そして、ストレージ装置１は、仮想ボリュームを上位装置であるホスト装置２に提供する。
【００１６】
本ストレージ装置１は、１以上（図１に示す例では１つ）のホスト装置２に対して通信可能に接続されている。ホスト装置２とストレージ装置１とは、後述するＣＡ（Communication Adapter）１０１，１０２により接続されている。
【００１７】
ホスト装置２は、例えば、サーバ機能をそなえた情報処理装置であり、本ストレージ装置１との間において、ＮＡＳ（Network Attached Storage）やＳＡＮ（Storage Area Network）のコマンドを送受信する。ホスト装置２は、例えば、ストレージ装置１に対してＮＡＳにおけるリード／ライト等のストレージアクセスコマンドを送信することにより、ストレージ装置１が提供するボリュームにデータの書込または読出を行なう。
【００１８】
そして、本ストレージ装置１は、ホスト装置２からボリュームに対して行なわれる入出力要求（例えば、リードコマンドやライトコマンド）に応じて、このボリュームに対応する記憶装置３１に対して、データの読出や書込等の処理を行なう。なお、ホスト装置２からの入出力要求のことをＩＯ（Input Output）要求もしくはＩＯコマンドという場合がある。
【００１９】
なお、図１に示す例においては１つのホスト装置２が図示されているが、これに限定されるものではなく、ストレージ装置１に２つ以上のホスト装置２を接続してもよい。
【００２０】
また、ストレージ装置１には、管理端末３が通信可能に接続されている。管理端末３は、キーボードやマウス等の入力装置や表示装置を備える情報処理装置であって、システム管理者等のユーザが各種情報の入力操作を行なう。例えば、ユーザは、管理端末３を介して、各種設定等に係る情報を入力する。入力された情報は、ホスト装置２やストレージ装置１に送信される。
【００２１】
本ストレージ装置１は、図１に示すように、複数（本実施形態では２つ）のＣＭ（Controller Module）１００ａ，１００ｂ及び１つ以上（図１に示す例では３つ）のドライブエンクロージャ３０をそなえる。
【００２２】
ドライブエンクロージャ３０は、１以上（図１に示す例では４つ）の記憶装置（物理ディスク）３１を搭載可能であり、これらの記憶装置３１の記憶領域（実ボリューム，実ストレージ）を、本ストレージ装置１に対して提供する。
【００２３】
例えば、ドライブエンクロージャ３０は、複数段のスロット（図示省略）をそなえ、これらのスロットに、記憶装置３１を挿入することにより、実ボリューム容量を随時変更することができる。また、複数の記憶装置３１を用いてＲＡＩＤ（Redundant Arrays of Inexpensive Disks）を構成することができる。
【００２４】
記憶装置（第２メモリ）３１は、後述するメモリ１０６と比較すると容量の大きい、ＨＤＤ，ＳＳＤ等の記憶装置（ストレージ）であって、種々のデータを格納するものである。なお、以下では、記憶装置のことをドライブもしくはディスクという場合がある。
【００２５】
各ドライブエンクロージャ３０は、ＣＭ１００ａのデバイスアダプタ（Device Adapter：ＤＡ）１０３，１０３とＣＭ１００ｂのＤＡ１０３，１０３とそれぞれ接続されている。そして、各ドライブエンクロージャ３０には、ＣＭ１００ａ，１００ｂのいずれからもアクセスして、データの書込や読出を行なうことができる。すなわち、ドライブエンクロージャ３０の各記憶装置３１に対して、ＣＭ１００ａ，１００ｂのそれぞれを接続することにより、記憶装置３１へのアクセス経路が冗長化されている。
【００２６】
コントローラエンクロージャ４０は、１以上（図１に示す例では２つ）のＣＭ１００ａ，１００ｂを備える。
【００２７】
ＣＭ１００ａ，１００ｂは、ストレージ装置１内の動作を制御するコントローラ（ストレージ制御装置）であり、ホスト装置２から送信されるＩＯコマンドに従って、ドライブエンクロージャ３０の記憶装置３１へのデータアクセス制御等、各種制御を行なう。又、ＣＭ１００ａ，１００ｂは互いに同様の構成を有している。以下、ＣＭを示す符号としては、複数のＣＭのうち１つを特定する場合には符号１００ａ，１００ｂを用い、任意のＣＭを指すときには符号１００を用いる。また、ＣＭ１００ａをＣＭ＃１と、ＣＭ１００ｂをＣＭ＃２と、それぞれ表す場合がある。
【００２８】
ＣＭ１００ａ，１００ｂは二重化されており、通常は、ＣＭ１００ａ（ＣＭ＃１）がプライマリとして各種制御を行なう。しかし、プライマリＣＭ１００ａの故障時には、セカンダリのＣＭ１００ｂ（ＣＭ＃２）がプライマリとしてＣＭ１００ａの動作を引き継ぐ。
【００２９】
ＣＭ１００ａ，１００ｂは、ＣＡ１０１，１０２を介して、それぞれホスト装置２に接続される。そして、ＣＭ１００ａ，１００ｂは、ホスト装置２から送信されるリード／ライト等のＩＯコマンドを受信し、ＤＡ１０３等を介して記憶装置３１の制御を行なう。また、ＣＭ１００ａ，１００ｂは、ＰＣＩｅ（Peripheral Component Interconnect Express）等の図示しないインタフェースを介して相互に通信可能に接続される。
【００３０】
ＣＭ１００は、図１に示すように、ＣＡ１０１，１０２と複数（図１に示す例では２つ）のＤＡ１０３，１０３とをそなえるとともに、ＣＰＵ（Central Processing Unit）１０５，メモリ１０６，フラッシュメモリ１０７およびＩＯＣ（Input Output Controller）１０８をそなえる。ＣＡ１０１，１０２，ＤＡ１０３，ＣＰＵ１０５，メモリ１０６，フラッシュメモリ１０７，ＩＯＣ１０８は、例えばＰＣＩｅインタフェース１０４を介して相互に通信可能に接続される。
【００３１】
ＣＡ１０１，１０２は、ホスト装置２や管理端末３等から送信されたデータを受信したり、ＣＭ１００から出力するデータをホスト装置２や管理端末３等に送信する。すなわち、ＣＡ１０１，１０２は、ホスト装置２等の外部装置との間でのデータの入出力（ＩＯ）を制御する。
【００３２】
ＣＡ１０１は、ＮＡＳを介してホスト装置２や管理端末３と通信可能に接続するネットワークアダプタであり、例えば、ＬＡＮ（Local Area Network）インタフェース等である。各ＣＭ１００は、ＣＡ１０１により図示しない通信回線を介してホスト装置２等とＮＡＳにより接続され、ＩＯコマンドの受信やデータの送受信等を行なう。図１に示す例においては、ＣＭ１００ａ，１００ｂのそれぞれに２つのＣＡ１０１，１０１がそなえられている。
【００３３】
ＣＡ１０２は、ＳＡＮを介してホスト装置２と通信可能に接続するネットワークアダプタであり、例えば、ｉＳＣＳＩ（Internet Small Computer System Interface）インタフェースやＦＣ（Fibre Channel）インタフェースである。各ＣＭ１００は、ＣＡ１０２により図示しない通信回線を介してホスト装置２等とＳＡＮにより接続され、ＩＯコマンドの受信やデータの送受信等を行なう。図１に示す例においては、ＣＭ１００ａ，１００ｂのそれぞれに１つのＣＡ１０２がそなえられている。
【００３４】
ＤＡ１０３は、ドライブエンクロージャ３０や記憶装置３１等と通信可能に接続するためのインタフェースである。ＤＡ１０３は、ドライブエンクロージャ３０の記憶装置３１が接続され、各ＣＭ１００は、ホスト装置２から受信したＩＯコマンドに基づき、記憶装置３１に対するアクセス制御を行なう。
【００３５】
各ＣＭ１００は、ＤＡ１０３を介して、記憶装置３１に対するデータの書込や読出を行なう。また、図１に示す例においては、ＣＭ１００ａ，１００ｂのそれぞれに２つのＤＡ１０３，１０３がそなえられている。そして、ＣＭ１００ａ，１００ｂのそれぞれにおいて、各ＤＡ１０３にドライブエンクロージャ３０が接続されている。
【００３６】
これにより、ドライブエンクロージャ３０の記憶装置３１には、ＣＭ１００ａ，１００ｂのいずれからもデータの書込や読出を行なうことができる。
【００３７】
フラッシュメモリ１０７は、ＣＰＵ１０５が実行するプログラムや種々のデータ等を格納する記憶装置である。
【００３８】
メモリ（第１メモリ）１０６は、種々のデータやプログラムを一時的に格納する記憶装置であり、後述するキャッシュ領域１６１やメモリ領域１６２，１６３，１６４をそなえる（図２および図３参照）。キャッシュ領域１６１は、ホスト装置２から受信したデータや、ホスト装置２に対して送信するデータを一時的に格納する。アプリケーション用メモリ領域１６２は、ＣＰＵ１０５がアプリケーションプログラムを実行する際に、データやプログラムを一時的に格納する。アプリケーションプログラムは、例えば、本実施形態のストレージ制御機能を実現すべくＣＰＵ１０５が実行するストレージ制御プログラム１６０であり、ストレージ制御プログラム１６０は、メモリ１０６あるいはフラッシュメモリ１０７に保存される。なお、メモリ領域１６３および１６４の詳細については、図２および図３を参照しながら後述する。また、メモリ（第１メモリ）１０６は、前述した記憶装置（第２メモリ，ドライブ）３１と比較するとアクセス速度は高速であるが容量の小さい、ＲＡＭ（Random Access Memory）等である。
【００３９】
ＩＯＣ１０８は、各ＣＭ１００内におけるデータ転送を制御する制御装置であり、例えば、メモリ１０６に格納されたデータをＣＰＵ１０５を介することなく転送させるＤＭＡ（Direct Memory Access）転送を実現する。
【００４０】
ＣＰＵ１０５は、種々の制御や演算を行なう処理装置であり、例えばマルチコアプロセッサ（マルチＣＰＵ）である。ＣＰＵ１０５は、メモリ１０６，フラッシュメモリ１０７等に格納されたＯＳ（Operating System）やプログラムを実行することにより、種々の機能を実現する。
【００４１】
〔２〕本実施形態のストレージ制御装置の機能構成
ついで、図２〜図４を参照しながら、本実施形態のストレージ制御装置（ＣＭ）１００の機能構成について説明する。なお、図２は、ＣＭ１００の機能構成の一例を示すブロック図である。図３は、本実施形態のメモリ（第１メモリ）１０６における第１ハッシュキャッシュ用メモリ領域（第１メモリ領域）１６３および上位インデックス情報用メモリ領域１６４に格納される情報を説明する図である。図４は、本実施形態のドライブ（第２メモリ）３１における第２ハッシュキャッシュ用メモリ領域（第２メモリ領域）３１１，上位インデックス情報用メモリ領域３１２および下位インデックス情報用メモリ領域３１３に格納される情報を説明する図である。
【００４２】
本実施形態のＣＭ１００は、ＤＥ３０における各記憶装置３１を制御するもので、各記憶装置３１に保存される各単位データが重複するのを排除する機能（データ重複排除機能）を有している。ＣＭ１００は、ホスト装置２からの書込対象単位データを記憶装置３１に書き込む際、当該書込対象単位データがメモリ１０６のキャッシュ領域１６１に書き込まれると、データ重複排除機能によって、以下のような基本的な重複排除動作を行なう。
【００４３】
つまり、ＣＭ１００では、書込対象単位データについての特徴量であるハッシュ値（フィンガプリント）が生成される。そして、生成されたハッシュ値と記憶装置３１内に既に格納された単位データのハッシュ値とを比較し一致／不一致を判断することで、書込対象単位データが既存データであるか新規データであるかの判断が行なわれる。上記判断の結果、書込対象単位データが既存データである場合、書込対象単位データを記憶装置３１に書き込まないことにより、データ重複排除が行なわれる。一方、上記判断の結果、書込対象単位データが新規データである場合に係る、本実施形態のＣＭ１００の機能や動作については後述する。
【００４４】
既にドライブ３１に格納された単位データのハッシュ値は、当該単位データの書込先の物理アドレス（物理格納情報）に対応付けられ、後述するごとく、メモリ１０６上の第１ハッシュキャッシュまたはドライブ３１上の第２ハッシュキャッシュに登録される。ハッシュキャッシュは、データ重複排除用ハッシュ値検索テーブルともいう。第１ハッシュキャッシュに係る情報は、ＣＭ１００におけるストレージ制御用のメモリ１０６のメモリ領域（第１メモリ領域）１６３に保存される。また、第２ハッシュキャッシュに係る情報は、ドライブ３１のメモリ領域（第２メモリ領域）３１１に保存される。
【００４５】
ここで、図３を参照しながら、メモリ１０６のメモリ領域１６３に保存される第１ハッシュキャッシュ（オンメモリテーブル）について説明する。図３に示すように、第１ハッシュキャッシュには、ｎ個のバンドル＃１〜＃ｎ（ｎは２以上の整数で例えば２６２１４４）が含まれる。各バンドルには、例えば１２８のエントリが含まれる。各エントリには、Key-Valueとポインタとが含まれる。Keyは、ハッシュ値（例えば２０バイト）である。Valueは、ドライブ３１における格納先を示す物理格納情報（物理アドレス）に対応するコンテナＩＤ（４バイト）およびスロット番号（４バイト）である。また、ポインタは、前ポインタ（２バイト）および後ポインタ（２バイト）を含み、１２８エントリ内でリンクを構成する。
【００４６】
図３に示すような第１ハッシュキャッシュにおいて、空のエントリに新たなハッシュ値を追加登録（格納）する場合、または、検索用ハッシュ値で第１ハッシュキャッシュに対する検索を行なう場合、ハッシュ値（キー値）の剰余演算（mod演算）が行なわれる。つまり、ハッシュ値をバンドル総数ｎで割って得られる剰余に基づいて、検索先バンドルが決定される。検索先バンドルにおける全てのエントリにハッシュ値が登録された状態で新たなハッシュ値を追加登録する場合、ＬＲＵ（Least Recently Used）によって決まる先頭（最古）のエントリのKey-Valueが第１ハッシュキャッシュから追い出される。追い出されたKey-Valueは、メモリ１０６上からドライブ３１（ディスク上）の第２ハッシュキャッシュの対応バンドルに移動されるとともに、新たなKey-Valueが先頭のエントリに格納される。新たなKey-Valueが格納された場合、または、検索用ハッシュ値がヒットした場合、対応するエントリは、ポインタによって最後尾につなぎ直される。なお、以下では、第１ハッシュキャッシュにおける検索先バンドルに対応するドライブ３１上のバンドルを、対応バンドルという場合がある。
【００４７】
次に、図４を参照しながら、ドライブ３１のメモリ領域３１１に保存される第２ハッシュキャッシュ（オンディスクテーブル）について説明する。図４に示すように、第２ハッシュキャッシュには、図３に示す第１キャッシュハッシュにおけるｎ個のバンドルにそれぞれ対応する、ｎ個のバンドル＃１〜＃ｎが含まれる。各バンドルには、例えば３８９１２のエントリが含まれる。各エントリには、Key-Valueと参照数とポインタとが含まれる。Key-Valueは、上述したように、第１ハッシュキャッシュにおいてＬＲＵによってバンドルから溢れ出たKey-Valueである。参照数は、例えば、各単位データについての書込シーケンス時にリファレンスカウンタによって計数される重複参照回数であり、各単位データの重複度合いを示す情報である。各単位データの参照数は、所定のコンテナ（ドライブ３１）に保存される。第１ハッシュキャッシュから溢れたKey-Valueを第２ハッシュキャッシュに登録する際、当該Key-Valueに対応する単位データの参照数が、所定のコンテナから読み出され、対応するエントリに登録される。第２ハッシュキャッシュの各バンドル内におけるエントリは、参照数の大きい順にソートされる。
【００４８】
次に、図４を参照しながら、ドライブ３１のメモリ領域３１２および３１３にそれぞれ保存される上位インデックス情報および下位インデックス情報（オンディスクインデックス）について説明する。上位インデックス情報および下位インデックス情報は、ｎ個のバンドル＃１〜＃ｎのそれぞれに対応して作成される。
【００４９】
図４に示すように、バンドル＃ｉ（ｉは１〜ｎの整数）用の上位インデックス情報は、第２ハッシュキャッシュにおけるバンドル＃ｉのエントリのうち、基準値以上の参照数をもつ上位エントリを検索する情報である。なお、バンドル＃ｉ用の上位インデックス情報は、第２ハッシュキャッシュにおけるバンドル＃ｉのエントリのうち、上位側の基準数分の上位エントリ（例えば上位側の１４００個のエントリ）を検索する情報であってもよい。例えば、上位インデックス情報は、参照数が基準値以上の上位エントリのみを検索対象にして作成されたブルームフィルタ（Bloom Filter；以下、上位ＢＦという場合がある）である。バンドル＃ｉ用上位ＢＦに検索用ハッシュ値を通すことにより、検索用ハッシュ値がバンドル＃ｉの上位エントリに含まれるか否かの判定を素早く行なうことができる。上位ＢＦによって検索用ハッシュ値がバンドル＃ｉの上位エントリに含まれると判定された場合、偽陽性（False Positive）による誤検索の可能性がある。このため、バンドル＃ｉの上位エントリを検索対象にして検索用ハッシュ値による検索を行なうことで、検索用ハッシュ値がバンドル＃ｉの上位エントリに実際に含まれるか否かの確認が行なわれる。ドライブ３１のメモリ領域３１２に保存される、上述のごときバンドル＃１〜＃ｎ用上位ＢＦは、ドライブ３１上からメモリ１０６の上位ＢＦ用メモリ領域１６４にコピーされる。なお、例えば、一つのＢＦのサイズは４ＫＢであり、４ＫＢのＢＦによって、物理容量５．６ＭＢ分のエントリを検索対象とすることができる。
【００５０】
また、バンドル＃ｉ用の下位インデックス情報は、第２ハッシュキャッシュにおけるバンドル＃ｉのエントリのうち、基準値未満の参照数をもつ下位エントリを検索する情報である。なお、バンドル＃ｉ用の下位インデックス情報は、第２ハッシュキャッシュにおけるバンドル＃ｉのエントリのうち、上位側の基準数分以外の下位エントリ（例えば下位側の３７５１２個のエントリ）を検索する情報であってもよい。例えば、下位インデックス情報は、参照数が基準値未満の下位エントリのみを検索対象にして作成されたブルームフィルタ（以下、下位ＢＦという場合がある）である。バンドル＃ｉ用下位ＢＦに検索用ハッシュ値を通すことにより、検索用ハッシュ値がバンドル＃ｉの下位エントリに含まれるか否かの判定を素早く行なうことができる。下位ＢＦによって検索用ハッシュ値がバンドル＃ｉの下位エントリに含まれると判定された場合、偽陽性による誤検索の可能性がある。このため、バンドル＃ｉの下位エントリを検索対象にして検索用ハッシュ値による検索を行なうことで、検索用ハッシュ値がバンドル＃ｉの下位エントリに実際に含まれるか否かの確認が行なわれる。
【００５１】
そして、図３を参照しながら、メモリ１０６のメモリ領域１６４に保存される上位インデックス情報（オンメモリインデックス）について説明する。図３に示すように、ドライブ３１上のバンドル＃１〜＃ｎ用上位ＢＦは、上述のごとく、ドライブ３１上からメモリ１０６の上位ＢＦ用メモリ領域１６４にコピーされ、メモリ１０６上でも保持される。
【００５２】
本実施形態のＣＭ１００において、ＣＰＵ１０５は、メモリ１０６上の第１ハッシュキャッシュおよび上位ＢＦを参照するとともに、必要に応じてドライブ３１上の第２ハッシュキャッシュおよび下位ＢＦを参照し、以下のように機能する。つまり、ＣＰＵ１０５は、ストレージ制御プログラム１６０を実行することで、図２に示すように、第１配置制御部１５１，第２配置制御部１５２，ハッシュ値生成部１５３，第１判定部１５４，第２判定部１５５，第３判定部１５６，および重複排除部１５７として機能する。
【００５３】
なお、ストレージ制御プログラム１６０は、コンピュータ読取可能な記録媒体であって可搬型の非一時的な記録媒体に記録された形態で提供される。当該記録媒体としては、磁気ディスク，光ディスク，光磁気ディスクなどが挙げられる。また、光ディスクとしては、ＣＤ（Compact Disk），ＤＶＤ（Digital Versatile Disk），ブルーレイディスクなどが挙げられる。ＣＤは、ＣＤ−ＲＯＭ（Read Only Memory），ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などを含む。ＤＶＤは、ＤＶＤ−ＲＡＭ，ＤＶＤ−ＲＯＭ，ＤＶＤ−Ｒ，ＤＶＤ＋Ｒ，ＤＶＤ−ＲＷ，ＤＶＤ＋ＲＷ，ＨＤ(High Definition) ＤＶＤなどを含む。
【００５４】
このとき、ＣＰＵ１０５は、上述のごとき記録媒体からストレージ制御プログラム１６０を読み取って内部記憶装置（例えばメモリ１０６やフラッシュメモリ１０７）または外付けの記憶装置に格納して用いる。なお、ＣＰＵ１０５は、ストレージ制御プログラム１６０を、ネットワーク（図示略）を介して受信し内部記憶装置または外付けの記憶装置に格納して用いてもよい。
【００５５】
第１配置制御部１５１は、ＤＥ３０における各ドライブ３１に格納される各単位データについてのハッシュ値と物理アドレスとを含む第１ハッシュキャッシュ（第１管理情報）を、上記バンドル毎に、所定サイズの第１メモリ領域１６３に配置する。所定サイズとしては、本実施形態では、バンドル毎に、例えば１２８エントリ分の容量が設定される。なお、本実施形態において、ハッシュ値算出の対象となる上記単位データは、ＨＤＤ，ＳＳＤ等への書込み単位（物理ブロック単位；例えば５１２Ｂ（バイト））のサイズを有するデータブロックであってもよいし、複数のデータブロックを一つにまとめたデータブロック群（例えば４キロバイト）であってもよい。
【００５６】
第２配置制御部１５２は、所定サイズを超えＬＲＵによって溢れたエントリのKey-Value（第１管理情報）を、第２ハッシュキャッシュ（第２管理情報）として、第１メモリ領域１６３とは異なる、ドライブ３１上の第２メモリ領域３１１に配置する。このとき、第２配置制御部１５２は、溢れたエントリに対応する単位データの参照数を、所定のコンテナから読み出し、第２ハッシュキャッシュの対応エントリに登録し、対応バンドル内のエントリを、参照数の大きい順にソートする。
【００５７】
また、第２配置制御部１５２は、バンドル毎に作成された、第２ハッシュキャッシュにおけるハッシュ値を検索するインデックス情報（ＢＦ）を、第１メモリ領域１６３を含むメモリ１０６における上位インデックス情報用メモリ領域１６４に配置する。このとき、第２配置制御部１５２は、第２ハッシュキャッシュの各単位データについての参照数が基準値以上である上位単位データに対応する上位エントリのハッシュ値を素早く検索する上位ＢＦを、上記インデックス情報として、メモリ１０６のメモリ領域１６４に配置する。なお、第２配置制御部１５２は、バンドル毎の上位ＢＦを、ドライブ３１における上位インデックス情報用メモリ領域３１２に配置し、メモリ領域３１２に配置された上位ＢＦのコピーを、メモリ１０６におけるメモリ領域１６４に配置する。
【００５８】
さらに、第２配置制御部１５２は、参照数が基準値未満である下位単位データに対応する下位エントリのハッシュ値を素早く検索する下位ＢＦを、第２メモリ領域３１１を含むドライブ３１における下位インデックス情報用メモリ領域３１３に配置する。
【００５９】
ハッシュ値生成部１５３は、ホスト装置２からの書込対象単位データがメモリ１０６のキャッシュ領域１６１に書き込まれると、書込対象単位データの検索用ハッシュ値を生成する。ハッシュ値生成部１５３がハッシュ値を算出するアルゴリズムとしては、ＭＤ（Message-Digest）５や、ＳＨＡ（Secure Hash Algorithm）−１や、ＳＨＡ−２５６などが挙げられる。
【００６０】
第１判定部１５４は、ハッシュ値生成部１５３が生成した検索用ハッシュ値について、メモリ１０６上の第１ハッシュキャッシュを検索し、検索用ハッシュ値が第１ハッシュキャッシュに含まれるか否かを判定する。このとき、第１判定部１５４は、検索用ハッシュ値の剰余演算を行ない、検索先バンドルを決定し、決定された検索先バンドルのエントリを検索する。
【００６１】
第２判定部１５５は、第１判定部１５４が検索用ハッシュ値が第１ハッシュキャッシュに含まれないと判定した場合、検索用ハッシュ値について、メモリ１０６上の検索先バンドル用上位ＢＦを参照する。そして、第２判定部１５５は、検索先バンドル用上位ＢＦに検索用ハッシュ値を通すことで、検索用ハッシュ値がドライブ３１上の第２ハッシュキャッシュの上位エントリに含まれるか否かを判定する。
【００６２】
上位ＢＦによって検索用ハッシュ値が第２ハッシュキャッシュの上位エントリに含まれると判定した場合、偽陽性による誤検索の可能性がある。このため、第２判定部１５５は、検索先バンドルの上位エントリを、ドライブ３１上の第２ハッシュキャッシュからメモリ１０６のアプリケーション用メモリ領域１６２に読み出す。そして、第２判定部１５５は、読み出した上位エントリを検索用ハッシュ値で検索し、検索用ハッシュ値が上位エントリにおけるハッシュ値のいずれかとマッチすることを確認する。
【００６３】
第３判定部１５６は、第２判定部１５５が検索用ハッシュ値が第２ハッシュキャッシュの上位エントリに含まれないと判定した場合、対応バンドル用下位ＢＦを、ドライブ３１上のメモリ領域３１３からメモリ１０６のアプリケーション用メモリ領域１６２に読み出す。そして、第３判定部１５６は、読み出した対応バンドル用下位ＢＦに、検索用ハッシュ値を通すことで、検索用ハッシュ値がドライブ３１上の第２ハッシュキャッシュの下位エントリに含まれるか否かを判定する。
【００６４】
下位ＢＦによって検索用ハッシュ値が第２ハッシュキャッシュの下位エントリに含まれると判定した場合、偽陽性による誤検索の可能性がある。このため、第３判定部１５６は、対応バンドルの下位エントリを、ドライブ３１上の第２ハッシュキャッシュからメモリ１０６のアプリケーション用メモリ領域１６２に読み出す。そして、第３判定部１５６は、読み出した下位エントリを検索用ハッシュ値で検索し、検索用ハッシュ値が下位エントリにおけるハッシュ値のいずれかとマッチすることを確認する。
【００６５】
重複排除部１５７は、下記（ａ１）〜（ａ３）のいずれかの場合に、書込対象単位データについて重複排除処理を行なう。
【００６６】
（ａ１）第１判定部１５４が検索用ハッシュ値が第１ハッシュキャッシュに含まれると判定した場合。
【００６７】
（ａ２）第２判定部１５５が検索用ハッシュ値が第２ハッシュキャッシュの上位エントリに含まれると判定した場合。
【００６８】
（ａ３）第３判定部１５６が検索用ハッシュ値が第２ハッシュキャッシュの下位エントリに含まれると判定した場合。
【００６９】
また、第１配置制御部１５１および第２配置制御部１５２は、下記（ｂ１）または（ｂ２）の場合に、以下のように動作する。
【００７０】
（ｂ１）第３判定部１５６が検索用ハッシュ値が第２ハッシュキャッシュの下位エントリに含まれないと判定し且つ第１メモリ領域１６３の検索先バンドルに空きエントリがない場合。
【００７１】
（ｂ２）第１判定部１５４が検索用ハッシュ値が第１ハッシュキャッシュに含まれないと判定し且つ第１メモリ領域１６３の検索先バンドルに空きエントリがなく且つ第２ハッシュキャッシュが空状態であるか存在しない場合。
【００７２】
上記（ｂ１）または（ｂ２）の場合、第２配置制御部１５２は、第１ハッシュキャッシュの検索先バンドルにおける他のハッシュ値（Key）を、ドライブ３１上の第２ハッシュキャッシュに追加登録する。他のハッシュ値は、ＬＲＵによって選択される。第２配置制御部１５２は、他のハッシュ値に対応する単位データについての参照数（重複参照回数）を所定のコンテナで参照する。そして、第２配置制御部１５２は、参照した参照数が基準値以上である場合、他のハッシュ値を、対応バンドル用上位ＢＦに登録し、メモリ１０６上およびドライブ３１上における格納先／対応バンドル用上位ＢＦを更新する。このとき、他のハッシュ値の対応バンドル用上位ＢＦへの登録は、他のハッシュ値を含む上位エントリを検索対象とする対応バンドル用上位ＢＦを作成することによって行なわれる。
【００７３】
上記（ｂ１）または（ｂ２）の場合、第１配置制御部１５１は、メモリ１０６上の第１ハッシュキャッシュにおいて、前記他のハッシュ値に代え、検索用ハッシュ値（Key）を、対応単位データの格納先の物理アドレス（Value）に対応付けて登録する。また、参照した参照数が基準値未満である場合、第２配置制御部１５２は、前記他のハッシュ値を、対応バンドル用下位インデックス情報に登録し、ドライブ３１上における対応バンドル用下位ＢＦを更新する。このとき、他のハッシュ値の対応バンドル用下位ＢＦへの登録は、他のハッシュ値を含む下位エントリを検索対象とする対応バンドル用下位ＢＦを作成することによって行なわれる。
【００７４】
なお、第１判定部１５４が検索用ハッシュ値が第１ハッシュキャッシュに含まれないと判定し且つ第１メモリ領域１６３（検索先バンドルのエントリ）に空きがある場合、第１配置制御部１５１は、検索用ハッシュ値を、第１ハッシュキャッシュにおいて、検索先バンドルのエントリに追加登録する。
【００７５】
〔３〕本実施形態のストレージ制御装置の動作概要
次に、図５〜図７を参照しながら、本実施形態のストレージ制御装置１００の動作概要について説明する。図５〜図７は、本実施形態のストレージ制御装置１００の動作概要を説明する図である。
【００７６】
まず、図５を参照しながら、本実施形態のＣＭ１００の基本動作について説明する。
図５に示すように、ホスト装置２からの書込対象単位データがメモリ１０６のキャッシュ領域１６１に保持されると、書込単位データのハッシュ値が、ＣＰＵ１０５によって生成され、アプリケーション用メモリ領域１６２に保存される（矢印Ａ１参照）。そして、ＣＰＵ１０５によってハッシュ値の剰余演算が行なわれ、ハッシュ値の検索先バンドルが決定される（矢印Ａ２参照）。
【００７７】
本実施形態のＣＭ１００では、メモリ１０６上に、ｎ個のバンドル＃１〜＃ｎそれぞれについての第１ハッシュキャッシュ（オンメモリテーブル）と、バンドル＃１〜＃ｎ用上位ＢＦ（オンメモリインデックス）とが配置される。また、ドライブ（例えばＨＤＤ，ＳＳＤ）３１上に、ｎ個のバンドル＃１〜＃ｎそれぞれについての第２ハッシュキャッシュ（オンディスクテーブル）と、バンドル＃１〜＃ｎ用上位／下位ＢＦ（オンディスクインデックス）とが配置される。
【００７８】
新たなハッシュ値を第１ハッシュキャッシュの検索先バンドルに追加登録する際、検索先バンドルのエントリに空きが無い場合つまり検索先バンドルが所定容量を超えた場合、ＣＰＵ１０５は、ＬＲＵで選択される最古のエントリのKey-Valueを追い出す（矢印Ａ３参照）。第１ハッシュキャッシュから溢れ出たKey-Valueは、捨てられることなく、ドライブ３１上の第２ハッシュキャッシュにおける対応バンドルに格納されドライブ３１に残される（矢印Ａ４，図３，図４参照）。これにより、メモリ１０６における第１ハッシュキャッシュのサイズを大きくすることなく、重複排除効率を向上させることができる。なお、ドライブ３１上の第２ハッシュキャッシュにおいては、上述のごとく、ハッシュ値に対応する単位データの参照数が登録保存されており、第２ハッシュキャッシュの各バンドル内におけるエントリは、参照数の大きい順にソートされる。
【００７９】
そして、第２ハッシュキャッシュの各バンドルにおけるエントリは、参照数が多く重複度合いの高い上位エントリと、それ以外（つまり参照数が少なく重複度合いの低い）の下位エントリとに分けられる。上位エントリと下位エントリとの区分けは、参照数が基準値以上であるか否かで行なってもよいし、参照数の多い上位側基準数分を上位エントリとしそれ以外を下位エントリとしてもよい。ＣＰＵ１０５は、バンドル毎に、上位エントリのみを対象として検索を行なう上位ＢＦと、下位エントリのみを対象として検索を行なう下位ＢＦとを作成する。作成された上位ＢＦおよび下位ＢＦは、ドライブ３１上に保存されるとともに、上位ＢＦについては、メモリ１０６上のメモリ領域１６４にもコピーされて保存される（矢印Ａ５，図３，図４参照）。
【００８０】
したがって、第１ハッシュキャッシュの検索先バンドルに検索用ハッシュ値が含まれていない場合、ＣＰＵ１０５は、メモリ１０６上の検索先バンドル用上位ＢＦに、検索用ハッシュ値を通すことができる。これにより、ＣＰＵ１０５は、ドライブ３１にアクセスすることなく、検索用ハッシュ値がドライブ３１上の第２ハッシュキャッシュにおける対応バンドルの上位エントリに含まれるか否かを判断することができる。このように、重複度合いの高い単位データについての上位ＢＦをメモリ１０６上に載置することで、上位ＢＦをメモリ１０６上に載置しない場合と比較して、ドライブ３１に対するアクセス量が少なくなり、ストレージの性能向上に寄与する。
【００８１】
次に、図６を参照しながら、ホスト装置２からの書込対象単位データをドライブ３１に書き込む際（書込シーケンス時）におけるＣＭ１００の動作について説明する。
図６に示すように、ホスト装置２からの書込対象単位データがメモリ１０６のキャッシュ領域１６１に保持されると、書込単位データのハッシュ値が、ＣＰＵ１０５によって生成され、アプリケーション用メモリ領域１６２に保存される（矢印Ａ１参照）。そして、ＣＰＵ１０５によってハッシュ値の剰余演算が行なわれ、ハッシュ値の検索先バンドルが決定され、メモリ１０６上の第１ハッシュキャッシュにおける検索先バンドルが、検索用ハッシュ値で検索される（矢印Ａ２参照）。
【００８２】
検索の結果、検索用ハッシュ値がメモリ１０６上の第１ハッシュキャッシュに存在しない場合、ＣＰＵ１０５は、検索先バンドル用の上位ＢＦに、検索用ハッシュ値を通す。これにより、ＣＰＵ１０５は、ドライブ３１にアクセスすることなく、検索用ハッシュ値が、ドライブ３１上の第２ハッシュキャッシュにおける対応バンドルの上位エントリに含まれるか否かを判断する（矢印Ａ６および(1)参照）。
【００８３】
上位ＢＦに検索用ハッシュ値を通した結果、検索用ハッシュ値がドライブ３１上に存在するという陽性判定が得られた場合、偽陽性による誤検索の可能性がある。このため、ＣＰＵ１０５は、対応バンドルの上位エントリ（Key-Value）を、ドライブ３１上の第２ハッシュキャッシュからメモリ１０６上のアプリケーション用メモリ領域１６２に読み出す（矢印Ａ７および(2)参照）。そして、ＣＰＵ１０５は、読み出した上位エントリを検索用ハッシュ値で検索し、検索用ハッシュ値が上位エントリにおけるハッシュ値のいずれかとマッチすることを確認する（(3)参照）。
【００８４】
次に、図６においてメモリ１０６における検索先バンドル用上位ＢＦに検索用ハッシュ値を通した結果、検索用ハッシュ値がドライブ３１上に存在しないという陰性判定が得られた場合におけるＣＭ１００の動作について、図７を参照しながら説明する。
【００８５】
メモリ１０６における上位ＢＦに検索用ハッシュ値を通した結果、陰性判定が得られた場合、図７に示すように、ＣＰＵ１０５は、対応バンドル用下位ＢＦを、ドライブ３１上のメモリ領域３１３からメモリ１０６のアプリケーション用メモリ領域１６２に読み出す（矢印Ａ８および(2)参照）。そして、ＣＰＵ１０５は、読み出した対応バンドル用下位ＢＦに、検索用ハッシュ値を通すことで、検索用ハッシュ値がドライブ３１上の第２ハッシュキャッシュの下位エントリに含まれるか否かを判定する（(3)参照）。なお、図７では、検索先バンドル（対応バンドル）がバンドル＃１である例が示されている。
【００８６】
下位ＢＦに検索用ハッシュ値を通した結果、検索用ハッシュ値がドライブ３１上に存在するという陽性判定が得られた場合、偽陽性による誤検索の可能性がある。このため、ＣＰＵ１０５は、対応バンドルの下位エントリを、ドライブ３１上の第２ハッシュキャッシュからメモリ１０６のアプリケーション用メモリ領域１６２に読み出す（矢印Ａ９および(4)参照）。そして、ＣＰＵ１０５は、読み出した下位エントリを検索用ハッシュ値で検索し、検索用ハッシュ値が下位エントリにおけるハッシュ値のいずれかとマッチすることを確認する（(5)参照）。
【００８７】
このように、図７では、メモリ１０６における検索先バンドル用上位ＢＦを用いて検索用ハッシュ値がドライブ３１上に存在しないという陰性判定が得られた場合、ＣＰＵ１０５は、ドライブ３１にアクセスし、下位エントリを検索対象として検索用ハッシュ値の検索を行なう。これにより、重複排除効率の更なる向上を実現することができる。
【００８８】
〔４〕本実施形態の重複排除検索手順およびハッシュ値登録手順
〔４−１〕本実施形態との比較対象になる関連技術による重複排除検索手順
図８に示すフローチャート（ステップＳ１１〜Ｓ１５）に従って、本実施形態との比較対象になる関連技術による重複排除検索手順について説明する。
【００８９】
図８に示すように、関連技術による重複排除検索手順では、ＣＭ（ＣＰＵ）がホスト装置からの新規書込ＩＯを受け付けると（ステップＳ１１）、ＣＭは、例えば４ＫＢの単位データ（チャンク）毎にハッシュ値を生成する（ステップＳ１２）。そして、ＣＭは、生成したハッシュ値でハッシュキャッシュ（オンメモリテーブル）を検索することで、ハッシュキャッシュでの当該ハッシュ値の有無（マッチ）を検出する（ステップＳ１３）。このとき、ＣＭは、ハッシュ値の剰余演算を行ない、ハッシュキャッシュにおける検索先バンドルを決定し、決定した検索先バンドル内を当該ハッシュ値で検索する。
【００９０】
検索の結果、当該ハッシュ値が検索先バンドル内に有る場合（ステップＳ１３の「ハッシュ値検出」ルート）、ＣＭは、書込対象単位データと重複するデータが記憶装置（ストレージ）上に存在すると判断する。つまり、ＣＭは、重複検出と判断し、重複排除を実行する（ステップＳ１４）。
【００９１】
一方、検索の結果、当該ハッシュ値が検索先バンドル内に無い場合（ステップＳ１３の「ハッシュ値未検出」ルート）、ＣＭは、書込対象単位データと重複するデータが記憶装置（ドライブ）上に存在しないと判断する。つまり、ＣＭは、重複未検出と判断し、当該ハッシュ値を、新規の重複排除検索対象として、ハッシュキャッシュ（オンメモリテーブル）に登録する（ステップＳ１５）。
【００９２】
なお、ハッシュキャッシュの検索先バンドルに空きが無い場合（容量一杯の場合）、ＣＭは、ＬＲＵアルゴリズムによって最古のハッシュ値を追い出して破棄してから、今回書込対象になる単位データのハッシュ値（新規のハッシュ値）を、ハッシュキャッシュに登録する。このようにＬＲＵアルゴリズムに従って最古のハッシュ値を追い出して破棄すると、ハッシュキャッシュ（テーブル）のサイズを小さくすることが可能である。しかしながら、次回の書込ＩＯのハッシュ値検索時に、破棄したハッシュ値は検索対象にならないため、次回の書込ＩＯの書込対象単位データについてのデータ重複の検出可能性が低くなる。結果として、データ重複排除効率が低下し、限られたストレージの容量を効率的に利用することができない。
【００９３】
〔４−２〕本実施形態の重複排除検索手順
これに対し、本実施形態では、第１ハッシュキャッシュ用メモリ領域１６３のサイズを大きくすることなくデータ重複排除効率を向上させるべく、ドライブ３１に格納された全ての単位データを対象として重複排除検索を実行することが可能になっている。このため、第１ハッシュキャッシュ（オンメモリテーブル）から追い出したハッシュ値を破棄することなく、以下に説明する手順で重複排除検索が行なわれる。以下、図９〜図１１に示すフローチャートを参照しながら、本実施形態の重複排除検索手順について説明する。
【００９４】
本実施形態の重複排除検索手順では、ＣＰＵ１０５がホスト装置２からの新規書込ＩＯを受け付けキャッシュ領域１６１に保存すると（図９のステップＳ１）、ＣＰＵ１０５（ハッシュ値生成部１５３）は、例えば４ＫＢの単位データ（チャンク）毎に検索用ハッシュ値を生成する（図９のステップＳ２）。そして、ＣＰＵ１０５（第１判定部１５４）は、検索用ハッシュ値で、メモリ１０６上の第１ハッシュキャッシュ（オンメモリテーブル）を検索することで、第１ハッシュキャッシュでの検索用ハッシュ値の有無（マッチ）を検出する（図９のステップＳ３）。このとき、ＣＰＵ１０５は、検索用ハッシュ値の剰余演算を行ない、第１ハッシュキャッシュにおける検索先バンドルを決定し、決定した検索先バンドル内を検索用ハッシュ値で検索する。
【００９５】
検索の結果、検索用ハッシュ値が検索先バンドル内に有る場合（ステップＳ３の「ハッシュ値検出」ルート）、ＣＰＵ１０５は、書込対象単位データと重複するデータがドライブ３１上に存在すると判断し、重複検出と判断する。これに伴い、ＣＰＵ１０５（重複排除部１５７）は、重複排除を実行する（図９のステップＳ４）。この後、ＣＰＵ１０５は、重複排除検索処理を終了する。
【００９６】
一方、検索の結果、検索用ハッシュ値が検索先バンドル内に無い場合（ステップＳ３の「ハッシュ値未検出」ルート）、ＣＰＵ１０５は、書込対象単位データと重複するデータがドライブ３１上に存在しないと判断し、重複未検出と判断する。これに伴い、ＣＰＵ１０５は、検索用ハッシュ値で、ドライブ３１上の第２ハッシュキャッシュ（オンディスクテーブル）の対応バンドルを検索し、必要に応じて検索用ハッシュ値の登録を行なう（図９のステップＳ５）。この後、ＣＰＵ１０５は、重複排除検索処理を終了する。
【００９７】
このとき、ＣＰＵ１０５は、メモリ１０６上の検索先バンドル用上位ＢＦ（オンメモリインデックス）やドライブ３１上の対応バンドル用下位ＢＦ（オンディスクインデックス）を用いて、検索用ハッシュ値が第２ハッシュキャッシュの対応バンドルに存在するか否かを判定する。なお、ドライブ３１上の第２ハッシュキャッシュ等の検索手順については、図１０および図１１を参照しながら後述する。また、検索用ハッシュ値の登録手順については、図１２および図１３を参照しながら後述する。
【００９８】
次に、図１０および図１１に示すフローチャート（図１０のステップＳ５０１〜Ｓ５０８および図１１のステップＳ５１１〜Ｓ５１６）に従って、図９のステップＳ５における重複排除検索手順について説明する。
【００９９】
まず、ＣＰＵ１０５は、まず、メモリ１０６上の第１ハッシュキャッシュの検索先バンドル内に空きエントリが有るか無いかを判定する（ステップＳ５０１）。
【０１００】
空きエントリが有る場合（ステップＳ５０１の「有」ルート）、ＣＰＵ１０５は、ドライブ３１上の第２ハッシュキャッシュは未使用であり第２ハッシュキャッシュには検索用ハッシュ値が存在しないと判断することができる（ステップＳ５０２）。したがって、ＣＰＵ１０５は、書込対象単位データと重複するデータがドライブ３１上に存在せず重複未検出と判断し、検索用ハッシュ値による検索を実行することなく検索用ハッシュをメモリ１０６上の第１ハッシュキャッシュに登録する。このとき、ＣＰＵ１０５（第１配置制御部１５１および第２配置制御部１５２）は、検索用ハッシュ値を、新規の重複排除検索対象として、メモリ１０６上の第１ハッシュキャッシュ（オンメモリテーブル）の検索先バンドルに登録する（ステップＳ５０３）。当該登録の手順については、図１２および図１３を参照しながら後述する。この後、ＣＰＵ１０５は、重複排除検索処理を終了する。
【０１０１】
一方、空きエントリが無い場合（ステップＳ５０１の「無」ルート）、ドライブ３１上の第２ハッシュキャッシュには、検索先バンドルに対応する対応バンドルが存在すると判断される。これに伴い、第２ハッシュキャッシュの検索が実行される（図１０のステップＳ５０４）。その際、ＣＰＵ１０５（第２判定部１５５）は、まず、メモリ１０６上の検索先バンドル用上位ＢＦ（オンメモリインデックス）に、検索用ハッシュ値を通すことで、検索用ハッシュ値がドライブ３１上の第２ハッシュキャッシュの上位エントリに含まれるか否かを判定する（ステップＳ５０５）。
【０１０２】
上位ＢＦによって検索用ハッシュ値が第２ハッシュキャッシュの上位エントリに含まれると判定した場合（陽性判定の場合；ステップＳ５０５の「ハッシュ値検出」ルート）、前述したように、偽陽性による誤検索の可能性がある。このため、ＣＰＵ１０５（第２判定部１５５）は、対応バンドルの上位エントリ（オンディスクテーブル）を、ドライブ３１上の第２ハッシュキャッシュからメモリ１０６上のアプリケーション用メモリ領域１６２に読み出す（図６の矢印Ａ７参照）。そして、ＣＰＵ１０５（第２判定部１５５）は、読み出した上位エントリを検索用ハッシュ値で検索し、検索用ハッシュ値が上位エントリにおけるハッシュ値のいずれかとマッチすることを確認する（ステップＳ５０６）。
【０１０３】
確認後、ＣＰＵ１０５は、書込対象単位データと重複するデータがドライブ３１上に存在すると判断し、重複検出と判断する。これに伴い、ＣＰＵ１０５（重複排除部１５７）は、重複排除を実行する（ステップＳ５０７）。この後、ＣＰＵ１０５は、重複排除検索処理を終了する。
【０１０４】
一方、上位ＢＦによって検索用ハッシュ値が第２ハッシュキャッシュの上位エントリに含まれないと判定した場合（陰性判定の場合；ステップＳ５０５の「ハッシュ値未検出」ルート）、ＣＰＵ１０５は、第２ハッシュキャッシュの上位エントリには検索用ハッシュ値が存在しないと判断する。そして、ＣＰＵ１０５（第３判定部１５６）は、検索用ハッシュ値について、ドライブ３１上の下位ＢＦ（オンディスクインデックス）および第２ハッシュキャッシュ（オンディスクテーブル）を対象とした検索を行なう（ステップＳ５０８）。この後、ＣＰＵ１０５は、重複排除検索処理を終了する。
【０１０５】
以下、図１０のステップＳ５０８における検索手順について、図１１を参照しながら説明する。まず、ＣＰＵ１０５（第３判定部１５５）は、ドライブ３１上に下位エントリ用の第２ハッシュキャッシュ（検索テーブル）およびＢＦ（インデックス情報）が存在するか否か、つまりオンディスクテーブル／インデックスの有無を判定する（ステップＳ５１１）。
【０１０６】
判定の結果、下位エントリ用の第２ハッシュキャッシュおよび下位ＢＦが存在しない場合（ステップＳ５１１の「無」ルート）または第２ハッシュキャッシュが空状態で検索用ハッシュ値の検索を行なえない場合、ＣＰＵ１０５は、以下のように動作する。つまり、ＣＰＵ１０５は、ドライブ３１上において第２ハッシュキャッシュの下位エントリや下位ＢＦは未登録であり検索用ハッシュ値が存在しないものと判断することができる。
【０１０７】
したがって、ＣＰＵ１０５は、書込対象単位データと重複するデータがドライブ３１上に存在せず重複未検出と判断し、検索用ハッシュ値をメモリ１０６上の第１ハッシュキャッシュに登録する。このとき、ＣＰＵ１０５（第１配置制御部１５１および第２配置制御部１５２）は、検索用ハッシュ値を、新規の重複排除検索対象として、メモリ１０６上の第１ハッシュキャッシュ（オンメモリテーブル）の検索先バンドルに登録する（ステップＳ５１２）。当該登録の手順については、図１２および図１３を参照しながら後述する。この後、ＣＰＵ１０５は、重複排除検索処理を終了する。
【０１０８】
一方、下位エントリ用の第２ハッシュキャッシュおよび下位ＢＦが存在する場合（ステップＳ５１１の「有」ルート）、ＣＰＵ１０５は、以下のように動作する。つまり、ＣＰＵ１０５は、ドライブ３１上の対応バンドル用下位ＢＦおよび対応バンドルの下位エントリをメモリ１０６上のアプリケーション用メモリ領域１６２に読み出す（ステップＳ５１３；図７の矢印Ａ８，Ａ９参照）。
【０１０９】
そして、ＣＰＵ１０５（第３判定部１５６）は、メモリ１０６上の対応バンドル用下位ＢＦ（オンメモリインデックス）に、検索用ハッシュ値を通すことで検索用ハッシュ値がドライブ３１上の第２ハッシュキャッシュの下位エントリに含まれるか否かを判定する。下位ＢＦによって検索用ハッシュ値が第２ハッシュキャッシュの下位エントリに含まれると判定した場合（陽性判定の場合）、前述の通り、偽陽性による誤検索の可能性がある。このため、ＣＰＵ１０５（第３判定部１５６）は、メモリ１０６上に読み出した対応バンドルの下位エントリを検索用ハッシュ値で検索し、検索用ハッシュ値が下位エントリにおけるハッシュ値のいずれかとマッチすることを確認する（ステップＳ５１４）。
【０１１０】
確認後（ステップＳ５１４の「ハッシュ値検出」ルート）、ＣＰＵ１０５は、書込対象単位データと重複するデータがドライブ３１上に存在すると判断し、重複検出と判断する。これに伴い、ＣＰＵ１０５（重複排除部１５７）は、重複排除を実行する（ステップＳ５１５）。この後、ＣＰＵ１０５は、重複排除検索処理を終了する。
【０１１１】
一方、下位ＢＦによって検索用ハッシュ値が第２ハッシュキャッシュの下位エントリに含まれないと判定した場合（陰性判定の場合；ステップＳ５１４の「ハッシュ値未検出」ルート）、ＣＰＵ１０５は、第２ハッシュキャッシュの下位エントリには検索用ハッシュ値が存在しないと判断する。したがって、ＣＰＵ１０５（第３判定部１５６）は、書込対象単位データと重複するデータがドライブ３１上に存在せず重複未検出と判断し、検索用ハッシュ値をメモリ１０６上の第１ハッシュキャッシュに登録する。このとき、ＣＰＵ１０５（第１配置制御部１５１および第２配置制御部１５２）は、検索用ハッシュ値を、新規の重複排除検索対象として、メモリ１０６上の第１ハッシュキャッシュ（オンメモリテーブル）の検索先バンドルに登録する（ステップＳ５１６）。当該登録の手順については、図１２および図１３を参照しながら後述する。この後、ＣＰＵ１０５は、重複排除検索処理を終了する。
【０１１２】
なお、図１１に示す手順では、ステップＳ５１３において、対応バンドル用下位ＢＦと対応バンドルの下位エントリとの両方をメモリ１０６上に読み出しているが、対応バンドル用下位ＢＦと対応バンドルの下位エントリとを別々に読み出してもよい。つまり、図７で説明したように、まず、対応バンドル用下位ＢＦを読み出し、読み出した下位ＢＦに検索用ハッシュ値を通して陽性判定が得られた場合に、対応バンドルの下位エントリを読み出してもよい。この場合、読み出した下位ＢＦに検索用ハッシュ値を通して陰性判定が得られた時には、対応バンドルの下位エントリを読み出す必要が無くなるので、ドライブ３１に対するアクセス量を削減することができ、ストレージの性能低下を抑止できる。
【０１１３】
〔４−３〕本実施形態のハッシュ値登録手順
次に、図１２および図１３に示すフローチャート（図１２のステップＳ５２１〜Ｓ５２４および図１３のステップＳ５３１〜Ｓ５３８）に従って、本実施形態のハッシュ値登録手順について説明する。当該ハッシュ値登録手順は、上述した図１０のステップＳ５０３と図１１のステップＳ５１２およびＳ５１６において実行される処理手順である。
【０１１４】
まず、ＣＰＵ１０５（第１判定部１５４）は、メモリ１０６上における第１ハッシュキャッシュの検索先バンドルの空き（空きエントリ）の有無を判定する（ステップＳ５２１）。このとき、ＣＰＵ１０５は、検索用ハッシュ値の剰余演算を行ない、検索先バンドルを決定し、決定された検索先バンドル内をポインタに従って各エントリを検索する。その結果、空きエントリが有る場合（ステップＳ５２１の「有」ルート）、ＣＰＵ１０５（第１配置制御部１５１）は、検索用ハッシュ値を、第１ハッシュキャッシュにおいて、検索先バンドルの空きエントリに追加登録する（ステップＳ５２２）。この後、ＣＰＵ１０５は、重複排除検索処理を終了する。
【０１１５】
判定の結果、空きエントリが無い場合（ステップＳ５２１の「無」ルート）、ＣＰＵ１０５は、ＬＲＵアルゴリズムによって最古のエントリにおけるハッシュ値（Key-Value）を第１ハッシュキャッシュから追い出す（ステップＳ５２３）。ＣＰＵ１０５は、追い出したハッシュ値（Key-Value）を破棄することなく、ドライブ３１上の第２ハッシュキャッシュの対応バンドルおよび対応バンドル用インデックス情報（上位ＢＦまたは下位ＢＦ）に登録する（ステップＳ５２４）。なお、以下、第１ハッシュキャッシュから追い出したハッシュ値を追出しハッシュ値という。
【０１１６】
そして、ＣＰＵ１０５（第１配置制御部１５１）は、第１ハッシュキャッシュにおいて、ハッシュ値を追い出されたエントリに検索用ハッシュ値を登録するとともに、検索用ハッシュ値を登録した当該エントリを、ポインタによって最後尾につなぎ直す（ステップＳ５２２）。この後、ＣＰＵ１０５は、重複排除検索処理を終了する。
【０１１７】
以下、図１２のステップＳ５２４における処理手順について、図１３を参照しながら説明する。
【０１１８】
まず、ＣＰＵ１０５（第２配置制御部１５２）は、先に剰余演算によって決定された、追出しハッシュ値の属するバンドルに対応する対応バンドルを、ドライブ３１上の第２ハッシュキャッシュ内のバンドルから選択する（ステップＳ５３１）。この後、ＣＰＵ１０５（第２配置制御部１５２）は、第２ハッシュキャッシュの各バンドルにおけるエントリについての参照数に係るランキングの見直し処理を以下のように行なう（ステップＳ５３２）。
【０１１９】
ＣＰＵ１０５は、追出しハッシュ値を第２ハッシュキャッシュの上位エントリと下位エントリのいずれに登録するかについて判定すべく、追出しハッシュ値に対応する単位データについての参照数（レファレンスカウンタ）を参照する。参照数は、前述したように、所定のコンテナ（ドライブ３１）に保存されている。そして、ＣＰＵ１０５は、参照した参照数を基準値と比較する（ステップＳ５３３）。
【０１２０】
比較の結果、追出しハッシュ値に係る参照値が基準値未満である場合（ステップＳ５３３のＮＯルート）、ＣＰＵ１０５は、追出しハッシュ値を、第２ハッシュキャッシュの下位エントリに追加登録し、下位エントリのポインタを更新する（ステップＳ５３４）。そして、ＣＰＵ１０５は、追出しハッシュ値を、対応バンドル用下位ＢＦにエントリし、ドライブ３１上における対応バンドル用下位ＢＦを更新する（ステップＳ５３５）。このとき、追出しハッシュ値の対応バンドル用下位ＢＦへの登録は、追出しハッシュ値を含む下位エントリを検索対象とする対応バンドル用下位ＢＦを作成することによって行なわれる。この後、ＣＰＵ１０５は、追出しハッシュ値登録処理を終了する。
【０１２１】
一方、比較の結果、追出しハッシュ値に係る参照値が基準値以上である場合（ステップＳ５３３のＹＥＳルート）、ＣＰＵ１０５は、追出しハッシュ値を、第２ハッシュキャッシュの上位エントリに追加登録し、上位エントリのポインタを更新する（ステップＳ５３６）。そして、ＣＰＵ１０５は、追出しハッシュ値を、対応バンドル用上位ＢＦにエントリし、ドライブ３１上における対応バンドル用上位ＢＦを更新する（ステップＳ５３７）。このとき、追出しハッシュ値の対応バンドル用上位ＢＦへの登録は、追出しハッシュ値を含む上位エントリを検索対象とする対応バンドル用上位ＢＦを作成することによって行なわれる。さらに、ＣＰＵ１０５は、メモリ１０６上における対応バンドル用上位ＢＦを、ステップＳ５３７で作成された新たな対応バンドル用上位ＢＦに更新する（ステップＳ５３８）。この後、ＣＰＵ１０５は、追出しハッシュ値登録を終了する。
【０１２２】
〔５〕その他
以上、本発明の好ましい実施形態について詳述したが、本発明は、係る特定の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲内において、種々の変形、変更して実施することができる。
【０１２３】
上述した実施形態では、メモリ１０６上の各バンドル用上位ＢＦは、追出しハッシュ値を第２ハッシュキャッシュの上位エントリに追加登録した場合（図１３のステップＳ５３８参照）に更新されているが、本発明は、これに限定されるものでない。例えば、ＣＰＵ１０５は、所定時間が経過する毎に、各バンドルにおいて、参照数は大きいがアクセス頻度の低いハッシュ値を上位エントリから下位エントリに移動させてもよい。この場合、ＣＰＵ１０５は、ハッシュ値の移動後のエントリについて上位ＢＦおよび下位ＢＦを作成しメモリ１０６上の上位ＢＦを更新する。これにより、メモリ１０６における第１ハッシュキャッシュのサイズを大きくすることなく、重複排除効率をより向上させることができる。
【０１２４】
また、検索用ハッシュ値が第２ハッシュキャッシュに登録されたハッシュ値と一致した場合（ヒットした場合）、ＣＰＵ１０５は、ヒットしたハッシュ値を、第２ハッシュキャッシュのエントリ（上位エントリまたは下位エントリ）からメモリ１０６上に移動させてもよい。この場合、ＣＰＵ１０５は、図１２および図１３を参照しながら上述したハッシュ値登録処理を実行することになる。これにより、メモリ１０６における第１ハッシュキャッシュのサイズを大きくすることなく、重複排除効率をより向上させることができる。
【０１２５】
さらに、ＣＰＵ１０５は、関連ＬＢＡ（Logical Block Addressing）のハッシュ値をプリフェッチしてハッシュキャッシュに登録してもよく、この場合も、メモリ１０６における第１ハッシュキャッシュのサイズを大きくすることなく、重複排除効率をより向上させることができる。
【０１２６】
〔６〕付記
以上の各実施形態を含む実施形態に関し、さらに以下の付記を開示する。
【０１２７】
（付記１）
記憶装置を制御するストレージ制御装置であって、
前記記憶装置に格納される複数の単位データのそれぞれについてのハッシュ値と物理格納情報とを含む第１管理情報を、所定サイズの第１メモリ領域に配置する第１配置制御部と、
前記所定サイズを超えた前記第１管理情報を、第２管理情報として、前記第１メモリ領域とは異なる第２メモリ領域に配置するとともに、前記第２管理情報における各単位データについてのハッシュ値を検索するインデックス情報を、前記第１メモリ領域を含む第１メモリにおけるインデックス情報用メモリ領域に配置する第２配置制御部と、を有する、ストレージ制御装置。
【０１２８】
（付記２）
前記第２配置制御部は、
前記第２管理情報における各単位データについての書込シーケンス時の重複参照回数が基準値以上である上位単位データに対応する上位エントリのハッシュ値を検索する上位インデックス情報を、前記インデックス情報として、前記第１メモリにおける前記インデックス情報用メモリ領域に配置する、付記１に記載のストレージ制御装置。
【０１２９】
（付記３）
前記第２配置制御部は、
前記重複参照回数が前記基準値未満である下位単位データに対応する下位エントリのハッシュ値を検索する下位インデックス情報を、前記第２メモリ領域を含む第２メモリにおける下位インデックス情報用メモリ領域に配置する、付記２に記載のストレージ制御装置。
【０１３０】
（付記４）
前記第１メモリは、前記ストレージ制御装置によって用いられる、前記記憶装置の制御用のメモリであり、
前記第２メモリは、前記記憶装置である、付記３に記載のストレージ制御装置。
【０１３１】
（付記５）
書込対象単位データの検索用ハッシュ値を生成するハッシュ値生成部と、
前記ハッシュ値生成部が生成した検索用ハッシュ値について前記第１管理情報を検索し、前記検索用ハッシュ値が前記第１管理情報に含まれるか否かを判定する第１判定部と、
前記第１判定部が前記検索用ハッシュ値が前記第１管理情報に含まれないと判定した場合、前記検索用ハッシュ値について前記上位インデックス情報を参照し、前記検索用ハッシュ値が前記第２管理情報の前記上位エントリに含まれるか否かを判定する第２判定部と、
前記第１判定部が前記検索用ハッシュ値が前記第１管理情報に含まれると判定した場合、または、前記第２判定部が前記検索用ハッシュ値が前記第２管理情報の前記上位エントリに含まれると判定した場合、前記書込対象単位データについて重複排除処理を行なう重複排除部と、を有する、付記３または付記４に記載のストレージ制御装置。
【０１３２】
（付記６）
前記第２判定部が前記検索用ハッシュ値が前記第２管理情報の前記上位エントリに含まれないと判定した場合、前記検索用ハッシュ値について前記下位インデックス情報を参照し、前記検索用ハッシュ値が前記第２管理情報の前記下位エントリに含まれるか否かを判定する第３判定部を有し、
前記第３判定部が前記検索用ハッシュ値が前記第２管理情報の前記下位エントリに含まれると判定した場合、前記重複排除部は、前記重複排除処理を行なう、付記５に記載のストレージ制御装置。
【０１３３】
（付記７）
前記第３判定部が前記検索用ハッシュ値が前記第２管理情報の前記下位エントリに含まれないと判定し且つ前記第１メモリ領域に空きがない場合、
前記第２配置制御部は、前記第１管理情報における他のハッシュ値を前記第２管理情報に追加登録し、前記他のハッシュ値に対応する単位データについての前記重複参照回数を参照し、参照した前記重複参照回数が前記基準値以上である場合、前記他のハッシュ値を前記上位インデックス情報に登録し、
前記第１配置制御部は、前記第１管理情報において前記他のハッシュ値に代え前記検索用ハッシュ値を登録する、付記６に記載のストレージ制御装置。
【０１３４】
（付記８）
参照した前記重複参照回数が前記基準値未満である場合、前記第２配置制御部は、前記他のハッシュ値を前記下位インデックス情報に登録する、付記７に記載のストレージ制御装置。
【０１３５】
（付記９）
前記第１判定部が前記検索用ハッシュ値が前記第１管理情報に含まれないと判定し且つ前記第１メモリ領域に空きがある場合、前記第１配置制御部は、前記検索用ハッシュ値を前記第１管理情報に追加登録する、付記５〜付記８のいずれか一項に記載のストレージ制御装置。
【０１３６】
（付記１０）
記憶装置を制御するコンピュータに、
前記記憶装置に格納される複数の単位データのそれぞれについてのハッシュ値と物理格納情報とを含む第１管理情報を、所定サイズの第１メモリ領域に配置し、
前記所定サイズを超えた前記第１管理情報を、第２管理情報として、前記第１メモリ領域とは異なる第２メモリ領域に配置するとともに、
前記第２管理情報における各単位データについてのハッシュ値を検索するインデックス情報を、前記第１メモリ領域を含む第１メモリにおけるインデックス情報用メモリ領域に配置する、処理を実行させる、ストレージ制御プログラム。
【０１３７】
（付記１１）
前記第２管理情報における各単位データについての書込シーケンス時の重複参照回数が基準値以上である上位単位データに対応する上位エントリのハッシュ値を検索する上位インデックス情報を、前記インデックス情報として、前記第１メモリにおける前記インデックス情報用メモリ領域に配置する、処理を、前記コンピュータに実行させる、付記１０に記載のストレージ制御プログラム。
【０１３８】
（付記１２）
前記重複参照回数が前記基準値未満である下位単位データに対応する下位エントリのハッシュ値を検索する下位インデックス情報を、前記第２メモリ領域を含む第２メモリにおける下位インデックス情報用メモリ領域に配置する、処理を、前記コンピュータに実行させる、付記１１に記載のストレージ制御プログラム。
【０１３９】
（付記１３）
前記第１メモリは、前記ストレージ制御装置によって用いられる、前記記憶装置の制御用のメモリであり、
前記第２メモリは、前記記憶装置である、付記１２に記載のストレージ制御プログラム。
【０１４０】
（付記１４）
書込対象単位データの検索用ハッシュ値を生成し、
生成した検索用ハッシュ値について前記第１管理情報を検索し、前記検索用ハッシュ値が前記第１管理情報に含まれるか否かを判定し、
前記検索用ハッシュ値が前記第１管理情報に含まれないと判定した場合、前記検索用ハッシュ値について前記上位インデックス情報を参照し、前記検索用ハッシュ値が前記第２管理情報の前記上位エントリに含まれるか否かを判定し、
前記検索用ハッシュ値が前記第１管理情報に含まれると判定した場合、または、前記検索用ハッシュ値が前記第２管理情報の前記上位エントリに含まれると判定した場合、前記書込対象単位データについて重複排除処理を行なう、処理を、前記コンピュータに実行させる、付記１２または付記１３に記載のストレージ制御プログラム。
【０１４１】
（付記１５）
前記検索用ハッシュ値が前記第２管理情報の前記上位エントリに含まれないと判定した場合、前記検索用ハッシュ値について前記下位インデックス情報を参照し、前記検索用ハッシュ値が前記第２管理情報の前記下位エントリに含まれるか否かを判定し、
前記検索用ハッシュ値が前記第２管理情報の前記下位エントリに含まれると判定した場合、前記重複排除処理を行なう、処理を、前記コンピュータに実行させる、付記１４に記載のストレージ制御プログラム。
【０１４２】
（付記１６）
前記検索用ハッシュ値が前記第２管理情報の前記下位エントリに含まれないと判定し且つ前記第１メモリ領域に空きがない場合、
前記第１管理情報における他のハッシュ値を前記第２管理情報に追加登録し、前記他のハッシュ値に対応する単位データについての前記重複参照回数を参照し、参照した前記重複参照回数が前記基準値以上である場合、前記他のハッシュ値を前記上位インデックス情報に登録し、
前記第１管理情報において前記他のハッシュ値に代え前記検索用ハッシュ値を登録する、処理を、前記コンピュータに実行させる、付記１５に記載のストレージ制御プログラム。
【０１４３】
（付記１７）
参照した前記重複参照回数が前記基準値未満である場合、前記他のハッシュ値を前記下位インデックス情報に登録する、処理を、前記コンピュータに実行させる、付記１６に記載のストレージ制御プログラム。
【０１４４】
（付記１８）
前記検索用ハッシュ値が前記第１管理情報に含まれないと判定し且つ前記第１メモリ領域に空きがある場合、前記検索用ハッシュ値を前記第１管理情報に追加登録する、処理を、前記コンピュータに実行させる、付記１４〜付記１７のいずれか一項に記載のストレージ制御プログラム。
【符号の説明】
【０１４５】
１    ストレージ装置
２    ホスト装置
３    管理端末
１００，１００ａ，１００ｂ    ＣＭ（ストレージ制御装置）
１０１，１０２    ＣＡ
１０３    ＤＡ
１０４    ＰＣＩｅインタフェース
１０５    ＣＰＵ（処理部，コンピュータ）
１５１    第１配置制御部
１５２    第２配置制御部
１５３    ハッシュ値生成部
１５４    第１判定部
１５５    第２判定部
１５６    第３判定部
１５７    重複排除部
１０６    メモリ（第１メモリ）
１６０    ストレージ制御プログラム
１６１    キャッシュ領域
１６２    アプリケーション用メモリ領域
１６３    第１ハッシュキャッシュ用メモリ領域（第１メモリ領域）
１６４    上位インデックス情報（ＢＦ）用メモリ領域
１０７    フラッシュメモリ
１０８    ＩＯＣ
３０    ドライブエンクロージャ（ＤＥ）
３１    記憶装置（ドライブ，第２メモリ）
３１１    第２ハッシュキャッシュ用メモリ領域（第２メモリ領域）
３１２    上位インデックス情報（ＢＦ）用メモリ領域
３１３    下位インデックス情報（ＢＦ）用メモリ領域
４０    コントローラエンクロージャ（ＣＥ）
【図１】
2017049806.tif 000003
【図２】
2017049806.tif 000004
【図３】
2017049806.tif 000005
【図４】
2017049806.tif 000006
【図５】
2017049806.tif 000007
【図６】
2017049806.tif 000008
【図７】
2017049806.tif 000009
【図８】
2017049806.tif 000010
【図９】
2017049806.tif 000011
【図１０】
2017049806.tif 000012
【図１１】
2017049806.tif 000013
【図１２】
2017049806.tif 000014
【図１３】
2017049806.tif 000015