(57)【要約】【課題】ブルームフィルタを用いた重複判定にかかる負荷を抑制すること。【解決手段】ストレージ装置１０１は、ボリューム１０２の記憶領域を複数に分割した領域１０４−１〜領域１０４−ｎから選ばれた少なくともいずれかに格納されたブロックのセキュアハッシュ値が登録されたブルームフィルタ１０５を記憶する。続けて、ストレージ装置１０１は、セキュアハッシュ値１０７の特徴量が、ブルームフィルタ１０５に登録されていないか否かを判断する。セキュアハッシュ値１０７の特徴量が、ブルームフィルタ１０５に登録されていないと判断した場合、ストレージ装置１０１は、領域１０４−２に書込対象ブロック１０６を書き込む。【選択図】図１
2014130549.tif 000002
【特許請求の範囲】
【請求項１】
複数に分割された記憶領域のいずれかに格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタを記憶する記憶部と、
前記記憶領域への書込対象データの特徴を抽出した第１の特徴量が、前記ブルームフィルタに登録されているかを判断する書込判断部と、
前記第１の特徴量が前記ブルームフィルタに登録されていないと前記書込判断部が判断した場合、前記記憶領域に前記書込対象データを書き込む書込部と、
を有することを特徴とするストレージ装置。
【請求項２】
前記ストレージ装置はさらに、
前記書込判断部が、前記第１の特徴量が登録されていないと判断した場合、前記ブルームフィルタに登録済である特徴量の個数に基づいて、前記ブルームフィルタに前記第１の特徴量を登録するかを判定する判定部と、
前記判定部が、前記ブルームフィルタに前記第１の特徴量を登録すると判定した場合、前記ブルームフィルタに前記第１の特徴量を登録する登録部と、
を有し、
前記書込部は、
前記判定部が前記ブルームフィルタに前記第１の特徴量を登録すると判定した場合、前記複数に分割された記憶領域のいずれかに前記書込対象データを書き込むことを特徴とする請求項１記載のストレージ装置。
【請求項３】
前記ストレージ装置はさらに、
前記判定部が、前記ブルームフィルタに前記第１の特徴量を登録しないと判定した場合、前記ブルームフィルタとは異なる他のブルームフィルタを前記記憶部から取得する取得部を有し、
前記判定部は、
前記取得部が前記他のブルームフィルタを取得した場合、前記他のブルームフィルタに登録済である特徴量の個数に基づいて、前記他のブルームフィルタに前記第１の特徴量を登録するかを判定し、
前記登録部は、
前記判定部が、前記他のブルームフィルタに前記第１の特徴量を登録すると判定した場合、前記他のブルームフィルタに前記第１の特徴量を登録し、
前記書込部は、
前記判定部が、前記他のブルームフィルタに前記第１の特徴量を登録すると判定した場合、前記複数に分割された記憶領域のうち、前記他のブルームフィルタに登録された特徴量を有するデータが格納された領域に前記書込対象データを書き込むことを特徴とする請求項２記載のストレージ装置。
【請求項４】
前記ストレージ装置はさらに、
前記取得部が、取得した前記他のブルームフィルタに基づいて、前記記憶部の記憶内容を更新する更新部を有することを特徴とする請求項３記載のストレージ装置。
【請求項５】
前記ストレージ装置はさらに、
前記書込判断部が、前記第１の特徴量が登録されていると判断した場合、前記複数に分割された記憶領域のいずれかから、前記第１の特徴量を有するデータを検出する書込検出部を有し、
前記書込部は、
前記書込検出部が、前記第１の特徴量を有するデータを検出した場合、前記記憶領域に前記書込対象データを書き込まないことを特徴とする請求項４記載のストレージ装置。
【請求項６】
前記ストレージ装置はさらに、
前記書込判断部が、前記第１の特徴量が登録されていると判断した場合、前記複数に分割された記憶領域のいずれかから、前記第１の特徴量を有するデータを検出する書込検出部を有し、
前記書込部は、
前記書込検出部が、前記第１の特徴量を有するデータを検出しなかった場合、前記記憶領域に前記書込対象データを書き込むことを特徴とする請求項４または５に記載のストレージ装置。
【請求項７】
前記記憶部は、
前記記憶領域への各書込対象データに対応して、各書込対象データに対応する論理アドレスに関連付けられた各書込対象データの特徴を抽出した特徴量を記憶し、
前記ストレージ装置はさらに、
前記記憶部に記憶された各書込対象データの特徴を抽出した特徴量から、前記記憶領域への読込対象データの論理アドレスに関連付けられた第２の特徴量を選択する選択部と、
前記選択部が選択した前記第２の特徴量が、前記記憶部に記憶された前記ブルームフィルタに登録されているかを判断する読込判断部と、
前記読込判断部が、前記第２の特徴量が登録されていると判断した場合、前記複数に分割された記憶領域のいずれかから、前記第２の特徴量を有するデータを検出する読込検出部と、
前記読込検出部が、前記第２の特徴量を有するデータを検出した場合、前記第２の特徴量を有するデータを出力する出力部と、
を有することを特徴とする請求項４〜６のいずれか１項に記載のストレージ装置。
【請求項８】
前記記憶部は、
前記複数に分割された記憶領域の各々に格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタを記憶し、
前記ストレージ装置はさらに、
前記読込判断部が、前記第２の特徴量が登録されていないと判断した場合、前記記憶部に記憶された前記複数に分割された記憶領域の各々に格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタのうち、前記第２の特徴量を有するデータが登録されたブルームフィルタを特定する特定部を有し、
前記読込検出部は、
前記複数に分割された記憶領域のうち、前記特定部が特定したブルームフィルタに登録された特徴量を有するデータが格納された領域から、前記第２の特徴量を有するデータを検出することを特徴とする請求項７記載のストレージ装置。
【請求項９】
前記更新部は、
前記特定部が特定した前記第２の特徴量の特徴量を有するデータが登録されたブルームフィルタに基づいて、前記記憶部の記憶内容を更新することを特徴とする請求項８記載のストレージ装置。
【請求項１０】
複数に分割された記憶領域のいずれかに格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタを記憶する記憶部を有するストレージ装置の制御方法において、
前記ストレージ装置が有する書込判断部が、前記記憶領域への書込対象データの特徴を抽出した第１の特徴量が、前記ブルームフィルタに登録されているかを判断し、
前記第１の特徴量が前記ブルームフィルタに登録されていないと前記書込判断部が判断した場合、前記ストレージ装置が有する書込部が、前記記憶領域に前記書込対象データを書き込むことを特徴とするストレージ装置の制御方法。
【請求項１１】
複数に分割された記憶領域のいずれかに格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタを記憶する記憶部を有するストレージ装置の制御プログラムにおいて、
前記ストレージ装置が有する書込判断部に、前記記憶領域への書込対象データの特徴を抽出した第１の特徴量が、前記ブルームフィルタに登録されているかを判断させ、
前記第１の特徴量が前記ブルームフィルタに登録されていないと前記書込判断部が判断した場合、前記ストレージ装置が有する書込部に、前記記憶領域に前記書込対象データを書き込ませることを特徴とするストレージ装置の制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージ装置、制御方法、および制御プログラムに関する。
【背景技術】
【０００２】
従来、ブルームフィルタ（Ｂｌｏｏｍ  Ｆｉｌｔｅｒ）と呼ばれるビット列のデータ構造がある。ブルームフィルタは、あるデータが既存のデータの集合に含まれるか否かを効率的に判断する際に用いられる。関連する技術として、検索値と範囲情報から特定される第１の区間に対応する第１のビット列が生成条件を満たさなければ入力データを第１のビット列に登録し、生成条件を満たせば、第２の区間の範囲情報と第２のビット列を生成するものがある。また、複数のデータベースピアが階層的に接続されたシステムにおいて、自身より下位の階層の装置の管理するファイル集合の存在を示すビット列を、下位の階層の装置単位で有するとともに、自身の管理するファイル集合の存在を示すビット列を有する技術がある。（たとえば、下記特許文献１、２を参照。）
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１０−２６６９５２号公報
【特許文献２】特開２００８−１０２７９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術によれば、ブルームフィルタを用いて、あるデータと同一の内容が既存のデータの集合にあるか否かを判定する重複判定を行う際、ブルームフィルタの数が増える程、重複判定にかかる負荷が増大する。
【０００５】
１つの側面では、本発明は、ブルームフィルタを用いた重複判定にかかる負荷を抑制することができるストレージ装置、制御方法、および制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一側面によれば、複数に分割された記憶領域のいずれかに格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタを記憶する記憶部を有し、記憶領域への書込対象データの特徴を抽出した第１の特徴量が、ブルームフィルタに登録されているかを判断し、第１の特徴量がブルームフィルタに登録されていないと判断した場合、記憶領域に書込対象データを書き込むストレージ装置、制御方法、および制御プログラムが提案される。
【発明の効果】
【０００７】
本発明の一態様によれば、ブルームフィルタを用いた重複判定にかかる負荷を抑制することができるという効果を奏する。
【図面の簡単な説明】
【０００８】
【図１】図１は、本実施の形態にかかるストレージ装置の動作例を示す説明図である。
【図２】図２は、ストレージシステムの接続例を示す説明図である。
【図３】図３は、ストレージ装置のハードウェア構成例を示すブロック図である。
【図４】図４は、ＭＢＦの記憶内容の一例を示す説明図である。
【図５】図５は、ＭＢＦのビットを転置して記憶する一例を示す説明図である。
【図６】図６は、ストレージ装置の機能例を示すブロック図である。
【図７】図７は、ブロックマップテーブルの記憶内容の一例を示す説明図である。
【図８】図８は、書込対象のＭＢＦキャッシュ、ＭＢＦキャッシュテーブル、およびＭＢＦテーブルとの記憶内容の一例を示す説明図である。
【図９】図９は、ハッシュログテーブルの記憶内容の一例を示す説明図である。
【図１０】図１０は、読込処理の動作例を示す説明図（その１）である。
【図１１】図１１は、読込処理の動作例を示す説明図（その２）である。
【図１２】図１２は、書込処理の動作例を示す説明図（その１）である。
【図１３】図１３は、書込処理の動作例を示す説明図（その２）である。
【図１４】図１４は、読込処理手順の一例を示すフローチャートである。
【図１５】図１５は、書込処理手順の一例を示すフローチャート（その１）である。
【図１６】図１６は、書込処理手順の一例を示すフローチャート（その２）である。
【図１７】図１７は、メモリの記憶容量とキャッシュヒット率との関係を示す説明図である。
【図１８】図１８は、読込時の性能比較を示す説明図である。
【発明を実施するための形態】
【０００９】
以下に図面を参照して、開示のストレージ装置、制御方法、および制御プログラムの実施の形態を詳細に説明する。
【００１０】
図１は、本実施の形態にかかるストレージ装置の動作例を示す説明図である。ストレージシステム１００に含まれるストレージ装置１０１は、データを記憶するボリューム１０２を制御するコンピュータである。ストレージシステム１００は、ボリューム１０２の記憶領域をストレージシステム１００のユーザに提供するシステムである。ストレージ装置１０１は、ボリューム１０２のデータを直接読み書きしてもよいし、ボリューム１０２を制御して読書指示を通知してもよい。
【００１１】
たとえば、ストレージシステム１００は、Ｗｅｂサーバからアクセスされ、Ｗｅｂサーバがユーザに提供するＷｅｂコンテンツを記憶する。また、たとえば、ストレージシステム１００は、ユーザが利用するファイルを記憶する。
【００１２】
ストレージ装置１０１は、ボリューム１０２の記憶量を抑制するために、重複除去技術を実行する。重複除去技術を実行するストレージ装置１０１は、書込処理と読込処理について、以下に示す処理を行う。
【００１３】
書込処理について、ストレージ装置１０１は、書込対象データを、ブロックに分割する。次に、ストレージ装置１０１は、各ブロックについての特徴を抽出した特徴量を算出する。特徴量は、たとえば、特徴量を変化させずにブロックを改竄することが困難であるセキュアハッシュ値である。セキュアハッシュ値を算出するアルゴリズムとしては、ＭＤ５（Ｍｅｓｓａｇｅ−Ｄｉｇｅｓｔ  ５）、ＳＨＡ（Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ）−１、ＳＨＡ−２５６等がある。以下の説明では、特徴量がセキュアハッシュ値であるとして説明を行う。
【００１４】
続けて、ストレージ装置１０１は、算出したセキュアハッシュ値と、ボリューム１０２に既に格納されたブロックのセキュアハッシュ値とを比較して、既存データであるか新規データであるかを判断する。既存データであれば、ストレージ装置１０１は、ブロックをボリューム１０２に書き込まないことにより、重複除去を行う。新規データであれば、ストレージ装置１０１は、ボリューム１０２内の書込先の物理アドレスを割り当て、ブロックを書き込む。そして、ストレージ装置１０１は、セキュアハッシュ値から物理アドレスを検索するインデックスに、算出したセキュアハッシュ値と割り当てた物理アドレスとを関連付けて追加する。また、ストレージ装置１０１は、論理アドレスとセキュアハッシュ値を関連付けて対応表に記憶する。
【００１５】
また、読込処理について、ストレージ装置１０１は、関連付けた論理アドレスとセキュアハッシュ値を記憶する対応表から、読込対象のブロックのセキュアハッシュ値を選択する。次に、ストレージ装置１０１は、読込対象のブロックのセキュアハッシュ値を用いて、セキュアハッシュ値から物理アドレスを検索するインデックスを参照し、物理アドレスを特定する。続けて、ストレージ装置１０１は、特定した物理アドレスから、読込対象のブロックの内容を読み込む。
【００１６】
上述した読込処理と書込処理において、セキュアハッシュ値から物理アドレスを検索するインデックスが巨大になる。また、セキュアハッシュ値を用いるため、インデックス内のレコードに局所性が少なく、たとえば、いくつかのレコードをメモリに格納しても、入れ替えが頻繁に発生してしまい、処理性能が低下してしまう。そこで、ブルームフィルタを用いることによって、インデックスのデータ量を少なくすることができる。ブルームフィルタのビットがＯＮの時、陽性または偽陽性を示し、ＯＦＦの時は陰性を示す。なお、ビットの値が１をＯＮとし、０をＯＦＦとしてもよく、逆に、ビットの値が０をＯＮとし、１をＯＦＦとしてもよい。本実施の形態では、ビットの値が１をＯＮとし、０をＯＦＦとする。
【００１７】
また、ブルームフィルタを複数用意して、どのブルームフィルタにヒットしたかを判定することにより、検索範囲を絞り込む技術もある。複数のブルームフィルタを用いる技術については、図４と図５にて後述する。このように、ブルームフィルタを用いると、インデックスのデータ量を抑制することができるが、インデックス全てに対応するブルームフィルタをメモリに配置して、ブルームフィルタをテストすることになり、処理量が多くなる。
【００１８】
そこで、ストレージ装置１０１は、小さなブルームフィルタを複数作成し、ヒットすると予測される一部のブルームフィルタをメモリに格納する。これにより、ストレージ装置１０１は、ある程度の重複除去を行いつつ、重複除去にかかる処理量を抑制できる。また、メモリの記憶容量を、少なくすることができる。
【００１９】
図１にて、ストレージ装置１０１は、ボリューム１０２の記憶領域を分割した複数の領域１０４−１〜領域１０４−ｎから選ばれた少なくともいずれか一つの領域に格納されたブロックのセキュアハッシュ値が登録されたブルームフィルタ１０５を記憶する。図１に示すブルームフィルタ１０５は、ビット列のうち、いくつかのビットがＯＮであることを、塗りつぶした領域として示す。
【００２０】
領域の選び方としては、ヒットすると予測される領域を選ぶために、キャッシュアルゴリズムに従うことが好ましく、たとえば、ストレージ装置１０１は、最近アクセスがあった領域や、アクセス回数が多い領域を選択する。また、各領域に書き込まれたブロックのセキュアハッシュ値が登録されたブルームフィルタは、同一のファイルから分割されたブロックのセキュアハッシュ値が含まれる可能性が高い。したがって、各領域に書き込まれたブロックのセキュアハッシュ値が登録されたブルームフィルタは、局所性が高くなる。局所性が高いため、ある書込対象データのセキュアハッシュ値がヒットしたブルームフィルタは、後続の書込対象データのセキュアハッシュ値もヒットする可能性が高い。また、上述した、ストレージ装置１０１は、セキュアハッシュ値から物理アドレスを検索するインデックスの記憶領域を分割してもよい。図１の例では、説明の簡略化のため、単に、分割された領域にブロックが格納される例を用いて説明する。
【００２１】
次に、ストレージ装置１０１は、書込対象ブロック１０６を受け付けると、書込対象ブロック１０６のセキュアハッシュ値１０７を算出する。図１の例では、セキュアハッシュ値１０７に対応するビットを、塗りつぶした領域として示す。続けて、ストレージ装置１０１は、セキュアハッシュ値１０７と同一内容の特徴量が、ブルームフィルタ１０５に登録されていないか否かを判断する。以下、あるセキュアハッシュ値と同一内容の特徴量がブルームフィルタに登録されていることを、単に、「あるセキュアハッシュ値がブルームフィルタに登録されている」と記述することもある。図１の例では、セキュアハッシュ値１０７に対応するビットが、ブルームフィルタ１０５上で塗りつぶされていないため、ストレージ装置１０１は、セキュアハッシュ値１０７と同一内容の特徴量が、ブルームフィルタ１０５に登録されていないと判断する。
【００２２】
セキュアハッシュ値１０７と同一内容の特徴量が、ブルームフィルタ１０５に登録されていないと判断した場合、ストレージ装置１０１は、領域１０４−２に書込対象ブロック１０６を書き込む。このように、多少の重複データを許容することにより、ストレージ装置１０１は、ある程度の重複除去を行いつつ、重複除去にかかる処理量を抑制できる。以下、図２〜図１８を用いて、ストレージ装置１０１について詳細に説明する。
【００２３】
図２は、ストレージシステムの接続例を示す説明図である。ストレージシステム１００は、ストレージ装置１０１と、ボリューム１０２と、ユーザ端末２０１＃１〜ユーザ端末２０１＃ｎを含む。ストレージ装置１０１と、ユーザ端末２０１＃１〜ユーザ端末２０１＃ｎは、インターネット、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）などのネットワーク２０２で接続される。
【００２４】
ユーザ端末２０１＃１〜ユーザ端末２０１＃ｎは、ストレージシステム１００を利用するクライアントである。たとえば、ユーザ端末２０１＃１〜ユーザ端末２０１＃ｎは、典型的にはＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）であり、Ｗｅｂブラウザ等といったアプリケーションソフトウェアを使用してストレージ装置１０１に接続し、ストレージシステム１００を利用する。以下、アプリケーションソフトウェアは、以下、「アプリ」と呼称する。
【００２５】
（ストレージ装置のハードウェア）
図３は、ストレージ装置のハードウェア構成例を示すブロック図である。図３において、ストレージ装置１０１は、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ）３０１と、Ｒｅａｄ‐Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）３０２と、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）３０３と、を含む。また、ストレージ装置１０１は、ディスクドライブ３０４およびディスク３０５と、通信インターフェース３０６と、を含む。また、ＣＰＵ３０１〜通信インターフェース３０６はバス３０７によってそれぞれ接続される。
【００２６】
ＣＰＵ３０１は、ストレージ装置１０１の全体の制御を司る演算処理装置である。ＲＯＭ３０２は、ブートプログラムなどのプログラムを記憶する不揮発性メモリである。ＲＡＭ３０３は、ＣＰＵ３０１のワークエリアとして使用される揮発性メモリである。
【００２７】
ディスクドライブ３０４は、ＣＰＵ３０１の制御に従ってディスク３０５に対するデータのリードおよびライトを制御する制御装置である。ディスクドライブ３０４には、たとえば、磁気ディスクドライブ、ソリッドステートドライブなどを採用することができる。ディスク３０５は、ディスクドライブ３０４の制御で書き込まれたデータを記憶する不揮発性メモリである。たとえばディスクドライブ３０４が磁気ディスクドライブである場合、ディスク３０５には、磁気ディスクを採用することができる。また、ディスクドライブ３０４がソリッドステートドライブである場合、ディスク３０５には、半導体素子メモリを採用することができる。
【００２８】
通信インターフェース３０６は、ネットワーク２０２と内部のインターフェースを司り、他の装置からのデータの入出力を制御する制御装置である。具体的に、通信インターフェース３０６は、通信回線を通じてネットワーク２０２を介して他の装置に接続される。通信インターフェース３０６には、たとえば、モデムやＬＡＮアダプタなどを採用することができる。また、ストレージ装置１０１は、光ディスクドライブ、光ディスク、キーボード、マウスを有していてもよい。
【００２９】
次に、ブルームフィルタを利用して、データの格納位置を示すインデックスとする多段ブルームフィルタについて図４と図５に説明する。以下、ブルームフィルタを、ＢＦと称する場合がある。また、多段ブルームフィルタを、ＭＢＦ（Ｍｕｌｔｉ  Ｂｌｏｏｍ  Ｆｉｌｔｅｒ）と称する場合がある。
【００３０】
図４は、ＭＢＦの記憶内容の一例を示す説明図である。図４の（Ａ）は、２分割５段のＭＢＦを示す。具体的には、１段目のブルームフィルタは、ＢＦ１−１である。２段目のブルームフィルタは、ＢＦ１−１の下位のＢＦ２−１と、ＢＦ２−２とである。３段目のブルームフィルタは、ＢＦ２−１の下位のＢＦ３−１およびＢＦ３−２と、ＢＦ２−２の下位のＢＦ３−３およびＢＦ３−４とである。４段目のブルームフィルタは、ＢＦ３−１の下位のＢＦ４−１およびＢＦ４−２と、ＢＦ３−２の下位のＢＦ４−３およびＢＦ４−４と、ＢＦ３−３の下位のＢＦ４−５およびＢＦ４−６と、ＢＦ３−４の下位のＢＦ４−７およびＢＦ４−８である。
【００３１】
５段目のブルームフィルタは、ＢＦ４−１の下位のＢＦ５−１およびＢＦ５−２と、ＢＦ４−２の下位のＢＦ５−３およびＢＦ５−４と、ＢＦ４−３の下位のＢＦ５−５およびＢＦ５−６と、ＢＦ４−４の下位のＢＦ５−７およびＢＦ５−８とを含む。さらに、５段目のブルームフィルタは、ＢＦ４−５の下位のＢＦ５−９およびＢＦ５−１０と、ＢＦ４−６の下位のＢＦ５−１１およびＢＦ５−１２とを含む。さらに、５段目のブルームフィルタは、ＢＦ４−７の下位のＢＦ５−１３およびＢＦ５−１４と、ＢＦ４−８の下位のＢＦ５−１５およびＢＦ５−１６とを含む。
【００３２】
ストレージ装置１０１は、検索対象データのハッシュ値が１段目のブルームフィルタＢＦ１−１のテストにてミスすれば、検索対象データがないと判断する。
【００３３】
また、ブルームフィルタＢＦ１−１のテストがヒットすれば、ストレージ装置１０１は、検索対象データが２段目のブルームフィルタＢＦ２−１にヒットするか否かを判断する。ヒットしない場合、ストレージ装置１０１は、検索対象データがブルームフィルタＢＦ２−２にあるか否かを検索する。このように、ストレージ装置１０１は、ヒットすれば下位のブルームフィルタのテストを行い、検索範囲を絞り込むことにより、目的のデータにたどり着く。
【００３４】
なお、ブルームフィルタは偽陽性を有するため、誤検出を生む可能性がある。誤検出となった場合、ストレージ装置１０１は、上位のブルームフィルタに戻り、まだテストしていないブルームフィルタをテストすればよい。たとえば、ストレージ装置１０１が、ＢＦ４−１のテストにてヒットしたが、ＢＦ５−１およびＢＦ５−２のテストにてミスしたとする。この場合、ＢＦ４−１のテストにてヒットしたことが偽陽性であったことになり、ストレージ装置１０１は、上位のブルームフィルタに戻り、次のＢＦ４−２のテストを行う。
【００３５】
分割数を制御することにより、ストレージ装置１０１は、段数を減らすことができる。図４の（Ｂ）は、４分割３段のＭＢＦを示す。具体的に、１段目のブルームフィルタは、ＢＦ１−１である。２段目のブルームフィルタは、ＢＦ１−１の下位のＢＦ２−１と、ＢＦ２−２と、ＢＦ２−３と、ＢＦ２−４である。３段目のブルームフィルタは、ＢＦ２−１の下位のＢＦ３−１、ＢＦ３−２、ＢＦ３−３およびＢＦ３−４と、ＢＦ２−２の下位のＢＦ３−５、ＢＦ３−６、ＢＦ３−７およびＢＦ３−８と、を含む。さらに、３段目のブルームフィルタは、ＢＦ２−３の下位のＢＦ３−９、ＢＦ３−１０、ＢＦ３−１１およびＢＦ３−１２と、ＢＦ２−４の下位のＢＦ３−１３、ＢＦ３−１４、ＢＦ３−１５およびＢＦ３−１６と、を含む。
【００３６】
図５は、ＭＢＦのビットを転置して記憶する一例を示す説明図である。図５では、図４で示したＭＢＦの検索を高速化するために、メモリ配置を変更し、記憶内容に局所性を持たせることにより、検索時のメモリアクセスを減らす方法について説明する。
【００３７】
図５の（Ａ）は、転置する前の４つのブルームフィルタとして、図４の（Ｂ）で示したＢＦ２−１と、ＢＦ２−２と、ＢＦ２−３と、ＢＦ２−４とを示す。そして、ＢＦ２−１のビット列が、“００１０１０１００１”であり、ＢＦ２−２のビット列が、“１００１０１０１００”であり、ＢＦ２−３のビット列が、“１００１０１００１０”でありＢＦ２−４のビット列が、“００１００００１１１”であるとする。このとき、ストレージ装置１０１が、検査対象データが登録された可能性があるか、または登録されていないかを、先頭から３番目と７番目のビットの判断により、判断する。なお、図５の説明では、先頭を０番目として数える。判断結果として、ストレージ装置１０１は、３番目と７番目のビットが“１”であるＢＦ２−２がヒットしたので、ＢＦ２−２の下位のブルームフィルタの判断に移る。
【００３８】
図５の（Ｂ）は、ＢＦ２−１〜ＢＦ２−４を転置した例である。転置したＢＦ−Ａｌｌは、ＢＦ２−１の０番目のビット、…、ＢＦ２−４の０番目のビット、…、ＢＦ２−１の９番目のビット、…、ＢＦ２−４の９番目のビット、というビット列となる。このようなビット列ＢＦ−Ａｌｌに対して、ストレージ装置１０１は、ＢＦ−Ａｌｌの３番目の４ビット“０１１０”と、７番目の４ビット“０１０１”と、のＡＮＤ演算を行う。ＡＮＤ演算の結果“０１００”より、１番目のビットが１となるため、ストレージ装置１０１は、ＢＦ２−２がヒットしたことが判断できる。
【００３９】
図５の（Ａ）の例では、１つのブルームフィルタにつき２回アクセスするため、計８回のアクセスが発生する。これに対し、図５の（Ｂ）の例では、２回のアクセスで済む。図５の（Ｂ）の例を適用すると、たとえば、６４個のブルームフィルタに分割する場合、ストレージ装置１０１は、６４ビットのＡＮＤ演算を行い、演算結果のビット列のうちの１となる部分に対応するブルームフィルタをヒットと判断する。図５の（Ｂ）の方法によれば、ストレージ装置１０１は、４［ｋＢ］のメモリブロックのＡＮＤ演算を行うだけでよく、ＡＮＤ演算の結果のビット列で１となる部分をせいぜい数ｕｓ程度の時間で判断できるようになる。
【００４０】
（ストレージ装置１０１の機能）
次に、ストレージ装置１０１の機能について説明する。図６は、ストレージ装置の機能例を示すブロック図である。ストレージ装置１０１は、書込判断部６０１と、判定部６０２と、取得部６０３と、書込検出部６０４と、書込部６０５と、登録部６０６と、更新部６０７と、選択部６１１と、読込判断部６１２と、特定部６１３と、読込検出部６１４と、出力部６１５とを含む。制御部となる書込判断部６０１〜出力部６１５は、記憶装置に記憶されたプログラムをＣＰＵ３０１が実行することにより、書込判断部６０１〜出力部６１５の機能を実現する。記憶装置とは、具体的には、たとえば、図３に示したＲＯＭ３０２、ＲＡＭ３０３、ディスク３０５などである。
【００４１】
また、ストレージ装置１０１は、記憶部６２０にアクセス可能である。記憶部６２０は、ＲＡＭ３０３、ディスク３０５といった記憶装置である。また、記憶部６２０は、ブロックマップテーブル６２１と、書込対象のＭＢＦキャッシュ６２２と、ＭＢＦキャッシュテーブル６２３と、ＭＢＦテーブル６２４と、ハッシュログテーブル６２５とを含む。書込対象のＭＢＦキャッシュ６２２と、ＭＢＦキャッシュテーブル６２３とは、ＲＡＭ３０３や、ＣＰＵ３０１のレジスタ、キャッシュメモリ等といった、主記憶装置となるメモリに存在する。ブロックマップテーブル６２１と、ＭＢＦテーブル６２４と、ハッシュログテーブル６２５とは、ディスク３０５といった補助記憶装置となるディスクに存在する。
【００４２】
ブロックマップテーブル６２１は、書込対象データ群の各々の書込対象データに対応して、各々の書込対象データの論理アドレスに関連付けられた各々の書込対象ブロックのセキュアハッシュ値を記憶する。ブロックマップテーブル６２１の詳細は、図７にて後述する。
【００４３】
書込対象のＭＢＦキャッシュ６２２とＭＢＦキャッシュテーブル６２３は、ボリューム１０２の記憶領域を分割した複数の領域から選ばれた少なくともいずれか一つの領域に格納されたブロックのセキュアハッシュ値が登録されたブルームフィルタを記憶する。ＭＢＦキャッシュテーブル６２３の中に、書込対象のＭＢＦキャッシュ６２２が含まれてもよい。また、ＭＢＦキャッシュテーブル６２３は、ハッシュログテーブル６２５の記憶領域を分割した複数の領域から選ばれた少なくともいずれか一つの領域に格納されたブロックのセキュアハッシュ値が登録されたブルームフィルタを記憶してもよい。本実施の形態では、ハッシュログテーブル６２５の記憶領域を分割した例を用いて説明する。
【００４４】
ＭＢＦテーブル６２４は、各々の領域ごとに当該領域に格納されたブロックのセキュアハッシュ値が登録されたブルームフィルタを記憶する。書込対象のＭＢＦキャッシュ６２２〜ＭＢＦテーブル６２４の詳細は、図８にて後述する。
【００４５】
ハッシュログテーブル６２５は、図１で説明したセキュアハッシュ値から物理アドレスを検索するインデックスに相当する。ハッシュログテーブル６２５の詳細は、図９にて後述する。
【００４６】
書込判断部６０１は、ハッシュログテーブル６２５の記憶領域への書込対象データの第１のセキュアハッシュ値と同一内容のセキュアハッシュ値が、ＭＢＦキャッシュテーブル６２３のブルームフィルタに登録されていないか否かを判断する。ＭＢＦキャッシュテーブル６２３にあるブルームフィルタは、１つのブルームフィルタでもよいし、複数のブルームフィルタでもよい。判断結果は、ＣＰＵ３０１のレジスタ、キャッシュメモリ、ＲＡＭ３０３等に記憶される。
【００４７】
判定部６０２は、書込判断部６０１によって同一内容のセキュアハッシュ値が登録されていないと判断された場合、次の条件に基づいて、書込対象のＭＢＦキャッシュ６２２のブルームフィルタに第１のセキュアハッシュ値を登録するか否かを判定する。次の条件とは、書込対象のＭＢＦキャッシュ６２２のブルームフィルタに登録済であるセキュアハッシュ値の個数である。
【００４８】
また、判定部６０２は、取得部６０３によって他のブルームフィルタが取得された場合、他のブルームフィルタに登録済であるセキュアハッシュ値の個数に基づいて、他のブルームフィルタに第１のセキュアハッシュ値を登録するか否かを判定してもよい。なお、判定結果は、ＣＰＵ３０１のレジスタ、キャッシュメモリ、ＲＡＭ３０３等に記憶される。
【００４９】
取得部６０３は、判定部６０２によってブルームフィルタに第１のセキュアハッシュ値を登録しないと判定された場合、ＭＢＦキャッシュテーブル６２３のブルームフィルタとは異なる他のブルームフィルタを記憶部６２０から取得する。他のブルームフィルタは、記憶部６２０上で新たに作成されたブルームフィルタでもよいし、ＭＢＦテーブル６２４のブルームフィルタのうちの登録上限数に達していないブルームフィルタでもよい。なお、取得結果は、ＣＰＵ３０１のレジスタ、キャッシュメモリ、ＲＡＭ３０３等に記憶される。
【００５０】
書込検出部６０４は、書込判断部６０１によって同一内容のセキュアハッシュ値が登録されていると判断された場合、少なくともいずれか一つの領域から、同一内容のセキュアハッシュ値を有するデータを検出する。なお、検出結果は、ＣＰＵ３０１のレジスタ、キャッシュメモリ、ＲＡＭ３０３等に記憶される。
【００５１】
書込部６０５は、書込判断部６０１によって同一内容のセキュアハッシュ値が登録されていないと判断された場合、ボリューム１０２の記憶領域に書込対象データを書き込む。また、ハッシュログテーブル６２５の記憶領域を分割したため、書込部６０５は、書込判断部６０１によって同一内容のセキュアハッシュ値が登録されていないと判断された場合、ハッシュログテーブル６２５に、書込対象データが格納された物理アドレスを書き込む。
【００５２】
また、書込部６０５は、判定部６０２によってブルームフィルタに第１のセキュアハッシュ値を登録すると判定された場合、少なくともいずれか一つの領域に書込対象データを書き込んでもよい。
【００５３】
また、書込部６０５は、判定部６０２によって他のブルームフィルタに第１のセキュアハッシュ値を登録すると判定された場合、他のブルームフィルタに登録されたセキュアハッシュ値を有するデータが格納された領域に書込対象データを書き込んでもよい。また、書込部６０５は、書込検出部６０４によって同一内容のセキュアハッシュ値を有するデータが検出された場合、ボリューム１０２の記憶領域に書込対象データを書き込まなくてよい。また、書込部６０５は、書込検出部６０４によって同一内容のセキュアハッシュ値を有するデータが検出されなかった場合、ボリューム１０２の記憶領域に書込対象データを書き込んでもよい。
【００５４】
登録部６０６は、判定部６０２によってブルームフィルタに第１のセキュアハッシュ値を登録すると判定された場合、ブルームフィルタに第１のセキュアハッシュ値を登録する。
【００５５】
更新部６０７は、取得部６０３によって取得された他のブルームフィルタに基づいて、書込対象のＭＢＦキャッシュ６２２の記憶内容を更新する。具体的に、更新部６０７は、ＭＢＦキャッシュテーブル６２３に、書込対象のＭＢＦキャッシュ６２２のデータを退避して、書込対象のＭＢＦキャッシュ６２２を他のブルームフィルタで上書きする。ＭＢＦキャッシュテーブル６２３に、書込対象のＭＢＦキャッシュ６２２を退避する際、更新部６０７は、ＭＢＦキャッシュテーブル６２３に空き領域があれば、空き領域に書込対象のＭＢＦキャッシュ６２２のデータを書き込む。また、ＭＢＦキャッシュテーブル６２３に空き領域がなければ、更新部６０７は、古いレコードを他のブルームフィルタで上書きする。
【００５６】
また、更新部６０７は、特定部６１３によって特定された第２のセキュアハッシュ値と同一内容のセキュアハッシュ値を有するデータが登録されたブルームフィルタに基づいて、書込対象のＭＢＦキャッシュ６２２の記憶内容を更新してもよい。
【００５７】
選択部６１１は、ブロックマップテーブル６２１から、読込対象データの論理アドレスに関連付けられた第２のセキュアハッシュ値を選択する。なお、選択結果は、ＣＰＵ３０１のレジスタ、キャッシュメモリ、ＲＡＭ３０３等に記憶される。
【００５８】
読込判断部６１２は、選択部６１１によって選択された第２のセキュアハッシュ値と同一内容のセキュアハッシュ値が、ＭＢＦキャッシュテーブル６２３のブルームフィルタに登録されていないか否かを判断する。なお、判断結果は、ＣＰＵ３０１のレジスタ、キャッシュメモリ、ＲＡＭ３０３等に記憶される。
【００５９】
特定部６１３は、次に示す場合、ＭＢＦテーブル６２４のブルームフィルタのうちの第２のセキュアハッシュ値と同一内容のセキュアハッシュ値を有するデータが登録されたブルームフィルタを特定する。次に示す場合とは、読込判断部６１２によって第２のセキュアハッシュ値と同一内容のセキュアハッシュ値が登録されていないと判断された場合である。なお、特定結果は、ＣＰＵ３０１のレジスタ、キャッシュメモリ、ＲＡＭ３０３等に記憶される。
【００６０】
読込検出部６１４は、次に示す場合、少なくともいずれか一つの領域から、第２のセキュアハッシュ値と同一の内容のセキュアハッシュ値を有するデータを検出する。次に示す場合、とは、読込判断部６１２によって第２のセキュアハッシュ値と同一内容のセキュアハッシュ値が登録されていると判断された場合である。
【００６１】
また、読込検出部６１４は、特定部６１３によって特定されたブルームフィルタに登録されたセキュアハッシュ値を有するデータが格納された領域から、第２のセキュアハッシュ値と同一内容のセキュアハッシュ値を有するデータを検出してもよい。なお、検出結果は、ＣＰＵ３０１のレジスタ、キャッシュメモリ、ＲＡＭ３０３等に記憶される。
【００６２】
出力部６１５は、読込検出部６１４によって第２のセキュアハッシュ値と同一内容のセキュアハッシュ値を有するデータが検出された場合、第２のセキュアハッシュ値と同一内容のセキュアハッシュ値を有するデータを出力する。出力先は、ＲＡＭ３０３、ディスク３０５といった記憶領域でもよいし、通信インターフェース３０６を介して、読込要求を行ったユーザ端末２０１のアプリに出力してもよい。
【００６３】
図７は、ブロックマップテーブルの記憶内容の一例を示す説明図である。ブロックマップテーブル６２１は、ブロックごとに、ブロックのボリュームの格納位置と、ブロックが登録されたブルームフィルタのＩＤと、ブロックのセキュアハッシュ値を記憶する。図７に示すブロックマップテーブル６２１は、レコード７０１−１〜レコード７０１−３を有する。ブロックマップテーブル６２１は、ボリュームＩＤ、論理ブロックアドレス、ＭＢＦ−ＩＤ、セキュアハッシュ値という４つのフィールドを含む。ボリュームＩＤフィールドには、対象のブロックのボリュームの識別番号が格納される。ボリュームは、ストレージシステムのサービスを利用するアプリによって使われる。論理ブロックアドレスフィールドには、対象のブロックの論理アドレスが格納される。ＭＢＦ−ＩＤフィールドには、ブロックが登録されたブルームフィルタの識別番号が格納される。セキュアハッシュ値フィールドには、対象のブロックのセキュアハッシュ値が格納される。
【００６４】
たとえば、レコード７０１−１が示すブロックは、格納されるボリュームのボリュームＩＤが１であり、論理ブロックアドレスが０であり、対象のブロックのＭＢＦ−ＩＤが０であり、対象のブロックのセキュアハッシュ値が０ｘｅ２５１ｅｂ７１…であることを示す。
【００６５】
図８は、書込対象のＭＢＦキャッシュ、ＭＢＦキャッシュテーブル、およびＭＢＦテーブルとの記憶内容の一例を示す説明図である。書込対象のＭＢＦキャッシュ６２２、ＭＢＦキャッシュテーブル６２３、およびＭＢＦテーブル６２４は、ＭＢＦ−ＩＤと、ＭＢＦインデックスデータという同一のフィールドを有する。図８に示すＭＢＦキャッシュは、レコード８０１−１を有する。図８に示すＭＢＦキャッシュテーブル６２３は、レコード８０２−１とレコード８０２−２とを有する。図８に示すＭＢＦテーブル６２４は、レコード８０３−１〜レコード８０３−４を有する。なお、レコード８０１−１とレコード８０３−４は、同一の内容である。また、レコード８０２−１とレコード８０３−２は、同一の内容である。同様に、レコード８０２−２とレコード８０３−３は、同一の内容である。
【００６６】
ＭＢＦ−ＩＤフィールドは、ブルームフィルタの識別番号が格納される。ＭＢＦインデックスデータフィールドには、ブルームフィルタとなるビット列が格納される。また、１つのＭＢＦインデックスデータフィールドには、複数のブルームフィルタが格納されてもよい。たとえば、図４の（Ｂ）では、１つのＭＢＦインデックスデータフィールドに、ＢＦ２−１と、ＢＦ３−１〜ＢＦ３−４とが格納されてもよい。
【００６７】
たとえば、レコード８０１−１は、ＭＢＦ−ＩＤが３であり、ブルームフィルタとなるビット列が“ｚｚｚｚｚｚｚｚ…”であることを示す。
【００６８】
図９は、ハッシュログテーブルの記憶内容の一例を示す説明図である。ハッシュログテーブル６２５は、ブロックのセキュアハッシュ値とブロックが格納された物理ブロックアドレスをブロックごとに記憶する。図９に示すハッシュログテーブル６２５は、レコード９０１−１〜レコード９０３−２を記憶する。ハッシュログテーブル６２５は、セキュアハッシュ値、物理ブロックアドレスという２つのフィールドを含む。セキュアハッシュ値フィールドには、対象のブロックのセキュアハッシュ値が格納される。物理ブロックアドレスフィールドには、対象のブロックが格納された物理ブロックアドレスが格納される。
【００６９】
また、ハッシュログテーブル６２５は、レコード数が膨大となるため、検索範囲を絞るために、ＭＢＦ−ＩＤとヒットしたブルームフィルタごとに、ハッシュログテーブル６２５の記憶内容が分割される。ヒットしたブルームフィルタにより絞られる検索範囲を、以下、「ハッシュログ範囲」と呼称する。図９の例では、ＭＢＦ−ＩＤが０であり、１番目のＢＦにヒットした検索対象のブロックは、ハッシュログ範囲９１１−１に含まれる。ハッシュログ範囲９１１−１には、レコード９０１−１と、レコード９０１−２が含まれる。同様に、ＭＢＦ−ＩＤが０であり、２番目のＢＦにヒットした検索対象のブロックは、ハッシュログ範囲９１１−２に含まれ、ＭＢＦ−ＩＤが１であり、１番目のＢＦにヒットした検索対象のブロックは、ハッシュログ範囲９１１−３に含まれる。
【００７０】
たとえば、図８で示した、レコード８０３−１のＭＢＦインデックスデータフィールドに、ＢＦ２−１と、ＢＦ３−１〜ＢＦ３−４とが格納されたとする。検索対象のブロックのハッシュ値がレコード８０３−１のＭＢＦインデックスデータのＢＦ３−１にヒットした場合、検索対象のブロックは、ハッシュログ範囲９１１−１に含まれることになる。したがって、ストレージ装置１０１は、検索対象のブロックを取得するために、ハッシュログ範囲９１１−１に含まれるレコード群を検索すればよいことになる。
【００７１】
次に、図７〜図９で示した記憶内容を用いて、ストレージ装置１０１の読込処理の動作と書込処理の動作を、図１０〜図１３を用いて説明する。図１０〜図１３では、読込対象のブロック、または書込対象のブロックのハッシュ値が、ＭＢＦキャッシュテーブル６２３のＭＢＦインデックスデータにヒットするか否かに応じて、場合分けして説明する。また、検索対象となるＭＢＦインデックスデータは、ＭＢＦキャッシュテーブル６２３の他に、書込対象のＭＢＦキャッシュ６２２が含まれてもよい。図１０〜図１３の説明では、説明の簡略化のため、ＭＢＦキャッシュテーブル６２３のＭＢＦインデックスデータに対して検索するものとする。
【００７２】
図１０は、読込処理の動作例を示す説明図（その１）である。図１０では、読込処理を行う際に、読込対象のブロックのハッシュ値が、ＭＢＦキャッシュテーブル６２３のＭＢＦインデックスデータにヒットした場合の例を示す。
【００７３】
ストレージ装置１０１は、アプリから、ボリュームＩＤが“１”であり、論理ブロックアドレスが“２”であるブロックの読込要求を受け付ける。次に、ストレージ装置１０１は、ブロックマップテーブル６２１から、ボリュームＩＤが“１”であり、論理ブロックアドレスが“２”であるレコードを検出する。図１０の例では、レコード７０１−３が該当するため、ストレージ装置１０１は、レコード７０１−３のＭＢＦ−ＩＤフィールドの値“１”と、セキュアハッシュ値フィールドの値“０ｘｃｃａａ８ｄ８ｄ…”とを取得する。
【００７４】
次に、ストレージ装置１０１は、ＭＢＦキャッシュテーブル６２３から、ＭＢＦ−ＩＤフィールドの値が“１”となるレコードを検索する。図１０の例では、レコード８０２−１がヒットする。続けて、ストレージ装置１０１は、取得したセキュアハッシュ値“０ｘｃｃａａ８ｄ８ｄ…”が、レコード８０２−１のＭＢＦインデックスデータフィールドに格納されたＢＦのうちのどのＢＦにヒットするか判断する。
【００７５】
図１０の例では、セキュアハッシュ値“０ｘｃｃａａ８ｄ８ｄ…”が、レコード８０２−１のＭＢＦインデックスデータの１番目のＢＦにヒットしたとする。ヒットした場合、ストレージ装置１０１は、検出したレコード８０２−１のＭＢＦインデックスデータから、ハッシュログ範囲９１１−３を取得する。続けて、ストレージ装置１０１は、ハッシュログテーブル６２５のハッシュログ範囲９１１−３に含まれるレコード群から、セキュアハッシュ値“０ｘｃｃａａ８ｄ８ｄ…”がセキュアハッシュ値フィールドに格納されたレコード９０３−１を検出する。次に、ストレージ装置１０１は、検出したレコード９０３−１の物理ブロックアドレスフィールドの値“１”を用いて、ボリュームから“０ｘ８９ａｂｃｄｅｆ”を読み込む。
【００７６】
図１１は、読込処理の動作例を示す説明図（その２）である。図１１では、読込処理を行う際に、読込対象のブロックのハッシュ値が、ＭＢＦキャッシュテーブル６２３のＭＢＦインデックスデータにヒットしなかった場合の例を示す。
【００７７】
ストレージ装置１０１は、アプリから、ボリュームＩＤが“１”であり、論理ブロックアドレスが“０”であるブロックの読込要求を受け付ける。次に、ストレージ装置１０１は、ブロックマップテーブル６２１から、ボリュームＩＤフィールドの値が“１”であり、論理ブロックアドレスフィールドの値が“０”であるレコードを検出する。図１１の例では、レコード７０１−１が該当するため、ストレージ装置１０１は、レコード７０１−１のＭＢＦ−ＩＤフィールドの値“０”と、セキュアハッシュ値フィールドの値“０ｘｅ２５１ｅｂ７１…”とを取得する。
【００７８】
次に、ストレージ装置１０１は、ＭＢＦキャッシュテーブル６２３から、ＭＢＦ−ＩＤフィールドの値が“０”となるレコードを検索する。図１１の例では、ストレージ装置１０１は、ＭＢＦ−ＩＤが“０”となるレコードがなく、キャッシュミスとなる。この場合、ストレージ装置１０１は、ＭＢＦテーブル６２４から、ＭＢＦ−ＩＤが“０”となるレコードを検索する。図１１の例では、レコード８０３−１が該当するため、ストレージ装置１０１は、取得したセキュアハッシュ値“０ｘｅ２５１ｅｂ７１…”が、レコード８０３−１のＭＢＦインデックスデータフィールドに格納されたＢＦのうちのどのＢＦにヒットするか判断する。また、ストレージ装置１０１は、レコード８０３−１の記憶内容で、ＭＢＦキャッシュテーブル６２３を更新する。具体的に、更新後のＭＢＦキャッシュテーブル６２３は、レコード８０２−１がレコード８０３−１の記憶内容で上書きされたレコード８０２−３と、レコード８０２−２とを有する。
【００７９】
どのＢＦにヒットするかについて、図１１の例では、セキュアハッシュ値“０ｘｅ２５１ｅｂ７１…”が、レコード８０３−１のＭＢＦインデックスデータの１番目のＢＦにヒットしたとする。ヒットした場合、ストレージ装置１０１は、検出したレコード８０３−１のＭＢＦインデックスデータから、ハッシュログ範囲９１１−１を取得する。続けて、ストレージ装置１０１は、ハッシュログテーブル６２５のハッシュログ範囲９１１−１に含まれるレコード群から、セキュアハッシュ値“０ｘｅ２５１ｅｂ７１…”がセキュアハッシュ値フィールドに格納されたレコード９０１−１を検出する。次に、ストレージ装置１０１は、検出したレコード９０１−１の物理ブロックアドレスフィールドの値“０”を用いて、ボリュームから“０ｘ０１２３４５６７”を読み込む。
【００８０】
図１２は、書込処理の動作例を示す説明図（その１）である。図１２では、書込処理を行う際に、書込対象のブロックのハッシュ値が、ＭＢＦキャッシュテーブル６２３のＭＢＦインデックスデータにヒットした場合の例を示す。また、図１２と図１３では、アプリから書込要求があったファイルｆ１がブロックｂ１とブロックｂ２とに分割されたとする。ブロックｂ１のデータの内容は、“０ｘ０１２３４５６７”であるとする。
【００８１】
ストレージ装置１０１は、ボリュームＩＤが“１”であり、論理ブロックアドレスが“３”であり、データ内容が“０ｘ０１２３４５６７”となるブロックｂ１の書込要求を受け付ける。次に、ストレージ装置１０１は、“０ｘ０１２３４５６７”のセキュアハッシュ値を算出する。図１２の例では、算出されたセキュアハッシュ値は、“０ｘｅ２５１ｅｂ７１…”であるとする。続けて、ストレージ装置１０１は、セキュアハッシュ値“０ｘｅ２５１ｅｂ７１…”がＭＢＦキャッシュテーブル６２３の各レコードのＭＢＦインデックスデータフィールドに格納されたＢＦのいずれかにヒットするか否かを判断する。
【００８２】
図１２の例では、セキュアハッシュ値“０ｘｅ２５１ｅｂ７１…”が、レコード８０２−３のＭＢＦインデックスデータの１番目のＢＦにヒットしたとする。ヒットした場合、ストレージ装置１０１は、偽陽性の可能性があるため、セキュアハッシュ値“０ｘｅ２５１ｅｂ７１”を有するレコードがあるか否かを確認する。レコードがあれば、既に同一の内容のブロックを有することになり、重複除去のため、ストレージ装置１０１、書込要求のブロックを書き込まない。
【００８３】
具体的には、図１０で説明した、読込処理を同じ処理をすればよいので、図１２では図示を省略する。図１２の例では、ストレージ装置１０１は、検出したレコード８０２−３のＭＢＦインデックスデータから、ハッシュログ範囲９１１を取得する。そして、ストレージ装置１０１は、ハッシュログテーブル６２５のハッシュログ範囲９１１に含まれるレコード群から、セキュアハッシュ値“０ｘｅ２５１ｅｂ７１…”を有するレコードがあることを確認する。レコードがない場合、ストレージ装置１０１は、図１３に示す、ＭＢＦキャッシュテーブル６２３のＭＢＦインデックスデータにヒットしなかった場合と同一の処理をすればよい。
【００８４】
セキュアハッシュ値“０ｘｅ２５１ｅｂ７１…”を有するレコードがあることを確認した後、ストレージ装置１０１は、書込要求の内容を用いて、ブロックマップテーブル６２１を更新する。具体的に、ストレージ装置１０１は、ブロックマップテーブル６２１に、ボリュームＩＤフィールドの値が“１”であり、論理ブロックアドレスが“３”であるレコードがあれば該当のレコードを更新し、なければ、レコードを追加する。該当のレコードがあれば、ストレージ装置１０１は、該当のレコードのＭＢＦ−ＩＤフィールドを、検出したレコード８０２−３のＭＢＦ−ＩＤフィールドの値“０”で更新するとともに、セキュアハッシュ値を“０ｘｅ２５１ｅｂ７１…”で更新する。図１２の例では、レコードがない場合を示し、ストレージ装置１０１は、レコード７０１−４を追加する。
【００８５】
図１３は、書込処理の動作例を示す説明図（その２）である。図１３では、書込処理を行う際に、書込対象のブロックのハッシュ値が、ＭＢＦキャッシュテーブル６２３のＭＢＦインデックスデータにヒットしなかった場合の例を示す。ブロックｂ２のデータの内容は、“０ｘ１３５７２４６８”であるとする。
【００８６】
ストレージ装置１０１は、ボリュームＩＤが“１”であり、論理ブロックアドレスが“４”であり、データ内容が“０ｘ１３５７２４６８”となるブロックｂ２の書込要求を受け付ける。次に、ストレージ装置１０１は、“０ｘ１３５７２４６８”のセキュアハッシュ値を算出する。図１３の例では、算出されたセキュアハッシュ値は、“０ｘ５５４１ａ０２２…”であるとする。続けて、ストレージ装置１０１は、セキュアハッシュ値“０ｘ５５４１ａ０２２…”がＭＢＦキャッシュテーブル６２３の各レコードのＭＢＦインデックスデータフィールドに格納されたＢＦのいずれかにヒットするか否かを判断する。
【００８７】
図１３の例では、セキュアハッシュ値“０ｘ５５４１ａ０２２…”が、ＭＢＦキャッシュテーブル６２３のいずれのレコードにもヒットせず、キャッシュミスしたとする。この場合、ストレージ装置１０１は、ブロックｂ２のデータの内容“０ｘ１３５７２４６８”をボリュームの物理ブロックアドレス“５”が示す領域に書き込む。さらに、ストレージ装置１０１は、ＭＢＦキャッシュのレコード８０１−１のＭＢＦインデックスデータフィールドに格納されたＢＦに、セキュアハッシュ値“０ｘ５５４１ａ０２２…”を登録する。図１３の例では、セキュアハッシュ値“０ｘ５５４１ａ０２２…”が登録されたことを、レコード８０１−１のＭＢＦインデックスデータフィールドに格納されたＢＦが、“ｚｚｚｚｚｚｚｚ…”から“ｚｚｚｗｚｚｚｚ…”に変更することにより示す。
【００８８】
また、ストレージ装置１０１は、レコード８０１−１のＭＢＦ−ＩＤフィールドの値“３”と、登録したＢＦにより指定されるハッシュログ範囲９１１−４を取得する。続けて、ストレージ装置１０１は、ハッシュログ範囲９１１−４に含まれるレコードであって、セキュアハッシュ値フィールドの値が“０ｘ５５４１ａ０２２…”であり、物理ブロックアドレスフィールドの値が“５”であるレコード９０４−１を追加する。また、ストレージ装置１０１は、書込要求の内容を用いて、ブロックマップテーブル６２１を更新する。図１３の例では、ストレージ装置１０１は、レコード７０１−５を追加する。
【００８９】
次に、図１０〜図１３を用いて説明した読込処理の動作と書込処理の動作を行うフローチャートを、図１４〜図１６を用いて説明する。
【００９０】
図１４は、読込処理手順の一例を示すフローチャートである。読込処理は、アプリからブロックの読込要求を受け付けた時に行う処理である。ストレージ装置１０１は、ブロックマップテーブル６２１から、受け付けた読込要求のボリュームＩＤとオフセットをキーにして、一致するレコードを検索する（ステップＳ１４０１）。次に、ストレージ装置１０１は、レコードを検出できたか否かを判断する（ステップＳ１４０２）。
【００９１】
レコードを検出できた場合（ステップＳ１４０２：Ｙｅｓ）、ストレージ装置１０１は、検出したレコードの、ＭＢＦ−ＩＤを取得する（ステップＳ１４０３）。次に、ストレージ装置１０１は、ＭＢＦキャッシュテーブル６２３から、取得したＭＢＦ−ＩＤをキーにして、一致するレコードを検索する（ステップＳ１４０４）。続けて、ストレージ装置１０１は、レコードを検出できたか否かを判断する（ステップＳ１４０５）。レコードを検出できなかった場合（ステップＳ１４０５：Ｎｏ）、ストレージ装置１０１は、ＭＢＦテーブル６２４から、取得したＭＢＦ−ＩＤをキーにして、一致するレコードを検索する（ステップＳ１４０６）。続けて、ストレージ装置１０１は、検出したレコードと、ＭＢＦキャッシュテーブル６２３のレコードを入れ替える（ステップＳ１４０７）。
【００９２】
ステップＳ１４０７の実行終了後、または、レコードを検出できた場合（ステップＳ１４０５：Ｙｅｓ）、ストレージ装置１０１は、検出したレコードのＭＢＦ−ＩＤとＭＢＦインデックスデータとから、ハッシュログ範囲を取得する（ステップＳ１４０８）。次に、ストレージ装置１０１は、取得したハッシュログ範囲に含まれるハッシュログテーブル６２５のレコード群から、ブロックマップテーブル６２１から発見したセキュアハッシュ値をキーにして、一致するレコードを検索する（ステップＳ１４０９）。続けて、ストレージ装置１０１は、検出したレコードの物理ブロックアドレスから、読込対象のブロックの内容を出力する（ステップＳ１４１０）。
【００９３】
また、レコードを検出できなかった場合（ステップＳ１４０２：Ｎｏ）、ストレージ装置１０１は、アプリにより書き込まれていないブロックであると判断して、０埋めしたデータを出力する（ステップＳ１４１１）。ステップＳ１４１０、またはステップＳ１４１１の実行終了後、ストレージ装置１０１は、読込処理を終了する。読込処理を実行することにより、ストレージ装置１０１は、重複除去技術が適用されたストレージに対して、ＢＦを利用することにより、ブロックの格納位置が高速に判断できるため、ブロックの内容の読込を高速に行うことができる。
【００９４】
図１５は、書込処理手順の一例を示すフローチャート（その１）である。また、図１６は、書込処理手順の一例を示すフローチャート（その２）である。書込処理は、アプリからブロックの書込要求を受け付けた時に行う処理である。
【００９５】
ストレージ装置１０１は、受け付けた書込要求のブロックの内容から、セキュアハッシュ値を算出する（ステップＳ１５０１）。次に、ストレージ装置１０１は、ＭＢＦキャッシュテーブル６２３から、算出したセキュアハッシュ値がＭＢＦインデックスデータに登録されたレコードを検索する（ステップＳ１５０２）。続けて、ストレージ装置１０１は、レコードを検出できたか否かを判断する（ステップＳ１５０３）。レコードが検出できなかった場合（ステップＳ１５０３：Ｎｏ）、ストレージ装置１０１は、図１６に示すステップＳ１６０１の処理に移行する。
【００９６】
レコードが検出できた場合（ステップＳ１５０３：Ｙｅｓ）、ストレージ装置１０１は、検出したレコードのＭＢＦ−ＩＤとＭＢＦインデックスデータとから、ハッシュログ範囲を取得する（ステップＳ１５０４）。次に、ストレージ装置１０１は、取得したハッシュログ範囲に含まれるハッシュログテーブル６２５のレコード群から、算出したセキュアハッシュ値をキーにして、一致するレコードを検索する（ステップＳ１５０５）。続けて、ストレージ装置１０１は、レコードを検出できたか否かを判断する（ステップＳ１５０６）。レコードを検出できなかった場合（ステップＳ１５０６：Ｎｏ）、ストレージ装置１０１は、図１６に示すステップＳ１６０１の処理に移行する。
【００９７】
レコードを検出できた場合（ステップＳ１５０６：Ｙｅｓ）、ストレージ装置１０１は、ＭＢＦキャッシュテーブル６２３から検出したレコードのＭＢＦ−ＩＤを取得する（ステップＳ１５０７）。ステップＳ１５０７の処理終了後、ストレージ装置１０１は、受け付けた書込要求のボリュームＩＤおよび論理ブロックアドレスと、取得したＭＢＦ−ＩＤと、算出したセキュアハッシュ値との組で、ブロックマップテーブル６２１を更新する（ステップＳ１５０８）。また、図１６に示すステップＳ１６０８の処理終了後にも、ストレージ装置１０１は、ステップＳ１５０８の処理を実行する。ステップＳ１５０８の実行終了後、ストレージ装置１０１は、書込処理を終了する。
【００９８】
ステップＳ１５０３：Ｎｏ、またはステップＳ１５０６：Ｎｏの場合、ストレージ装置１０１は、書込対象のＭＢＦキャッシュ６２２の登録数が所定値に達したか否かを判断する（ステップＳ１６０１）。ＭＢＦキャッシュの登録数が所定値に達した場合（ステップＳ１６０１：Ｙｅｓ）、ストレージ装置１０１は、書込対象のＭＢＦキャッシュ６２２を、ＭＢＦキャッシュテーブル６２３に書き込む（ステップＳ１６０２）。ステップＳ１６０２の処理について、ＭＢＦキャッシュテーブル６２３にあった古いレコードは、ＭＢＦテーブル６２４に同内容があるため、そのまま破棄する。続けて、ストレージ装置１０１は、全てのビットがＯＦＦとなるＭＢＦインデックスデータを作成する（ステップＳ１６０３）。次に、ストレージ装置１０１は、新たなＭＢＦ−ＩＤと、作成したＭＢＦインデックスデータとの組を、新たな書込対象のＭＢＦキャッシュ６２２として設定する（ステップＳ１６０４）。なお、ステップＳ１６０３、ステップＳ１６０４の処理において、ストレージ装置１０１は、上限数に達していない他のＢＦがあれば、ステップＳ１６０３の処理を実行せずに、前述のＢＦを新たな書込対象のＭＢＦキャッシュ６２２として設定してもよい。
【００９９】
ステップＳ１６０４の処理終了後、または、ＭＢＦキャッシュの登録数が所定値に達してない場合（ステップＳ１６０１：Ｎｏ）、ストレージ装置１０１は、書込対象のＭＢＦキャッシュ６２２のＭＢＦ−ＩＤを取得する（ステップＳ１６０５）。次に、ストレージ装置１０１は、受け付けた書込要求のブロックの内容を、ボリュームに書き込む（ステップＳ１６０６）。続けて、ストレージ装置１０１は、書込対象のＭＢＦキャッシュ６２２のＭＢＦインデックスデータに、算出したセキュアハッシュ値を登録する（ステップＳ１６０７）。次に、ストレージ装置１０１は、算出したセキュアハッシュ値と、書き込んだブロックの内容の物理ブロックアドレスとをレコードとして、ハッシュログテーブル６２５のうちの取得したＭＢＦ−ＩＤと、登録先のＢＦにより指定されるハッシュログ範囲に追加する（ステップＳ１６０８）。ステップＳ１６０８の処理終了後、ストレージ装置１０１は、ステップＳ１５０８の処理に移行する。
【０１００】
書込処理を実行することにより、ストレージ装置１０１は、ＢＦを利用して、重複除去をある程度行いつつ、重複除去にかかる処理量を減らすことができる。次に、図１７と図１８を用いて、本実施の形態にかかる性能の比較について説明する。
【０１０１】
図１７は、メモリの記憶容量とキャッシュヒット率との関係を示す説明図である。図１７にて示すグラフ１７０１は、４つのトレースデータを用いて、データが１０億個ある時の、メモリの記憶容量とキャッシュヒット率との関係を示す。図１７では、１０万を指数表記“１ｅ＋０５”として示し、１００万を“１ｅ＋０６”として示し、１０００万を“１ｅ＋０７”として示し、１億を“１ｅ＋０８”として示し、１０億を“１ｅ＋０９”として示す。グラフ１７０１の横軸は、メモリが保持するデータの数であり、グラフ１７０１の縦軸は、ヒット率である。
【０１０２】
４つのトレースデータについて、下記に記載する。１つ目のトレースデータ“ｉｏｄｅｄｕｐ．ｈｏｍｅｓ”は、ホームディレクトリのＩ／Ｏパターンが記載されてある。２つ目のトレースデータ“ｉｏｄｅｄｕｐ．ｍａｉｌ”は、メールサーバのＩ／Ｏパターンが記載されてある。３つ目のトレースデータ“ｓｒｃｍａｐ．ｈｏｍｅ１”は、ｈｏｍｅ１に対して、送信されたフレームやイベントが記載されてある。４つ目のトレースデータ“ｓｒｃｍａｐ．ｈｏｍｅ２”は、送信されたフレームやイベントが記載されてある。
【０１０３】
グラフ１７０１が示すように、１０億個のデータがある際、約１／１０００となる１００万個のデータがメモリにあれば、ストレージ装置１０１は、約９割の重複を発見することができる。
【０１０４】
図１８は、読込時の性能比較を示す説明図である。図１８では、ブロック読込時に、ＭＢＦキャッシュテーブル６２３を用いなかった場合の処理性能を１００［％］として、ＭＢＦキャッシュテーブル６２３を用いた場合の処理性能を、９つのサーバによるトレースデータに対して示す。１つ目のサーバは、ｔｓ（Ｔｅｒｍｉｎａｌ  Ｓｅｒｖｅｒ）である。２つ目のサーバは、ｓｔｇ（ｗｅｂ  ＳＴａＧｉｎｇ）である。３つ目のサーバは、ｈｍ（Ｈａｒｄｗａｒｅ  Ｍｏｎｉｔｏｒｉｎｇ）である。４つ目のサーバは、ｍｄｓ（ＭｅＤｉａ  Ｓｅｒｖｅｒ）である。５つ目のサーバは、ｒｓｒｃｈ（ＲｅＳｅａＲＣＨ  ｐｒｏｊｅｃｔｓ）である。６つ目のサーバは、ｓｒｃ２（ＳｏｕＲＣｅ  ｃｏｎｔｒｏｌ）である。７つ目のサーバは、ｗｄｅｖ（ｔｅｓｔ  Ｗｅｂ  ｓＥｒＶｅｒ）である。８つ目のサーバは、ｗｅｂ（ＷＥＢ／ＳＱＬ  ｓｅｒｖｅｒ）である。９つ目のサーバは、ｐｒｎ（ＰＲｉＮｔ  ｓｅｒｖｅｒ）である。
【０１０５】
図１８が示すように、処理性能低下の度合いは、サーバにも依存するが、ほぼ処理性能の低下は起こらない。最も処理性能が低下したサーバでも、１割程度の処理性能の低下で収まることがわかる。
【０１０６】
以上説明したように、ストレージ装置１０１によれば、ブロック書込時、ディスクにあるＭＢＦテーブル６２４は検索せずにメモリにあるＭＢＦキャッシュテーブル６２３を検索してブロックが登録されていない場合に書き込む。これにより、ストレージ装置１０１は、ある程度のデータの重複を除去しつつ、重複判定にかかる負荷が減少する。
【０１０７】
また、ストレージ装置１０１によれば、ブロック書込時に、ＭＢＦキャッシュテーブル６２３のブルームフィルタをテストしてブロックが登録されていない場合、書込対象のＭＢＦキャッシュ６２２に登録する。書込対象のＭＢＦキャッシュ６２２には、同時期に発生した書込対象ブロックのセキュアハッシュ値が登録されることになるため、ストレージ装置１０１は、書込対象のＭＢＦキャッシュ６２２の局所性を高めることができる。局所性が高まることにより、ディスクへのアクセス回数が減り、重複除去にかかる処理時間を短縮することができる。
【０１０８】
また、ストレージ装置１０１によれば、書込対象のＭＢＦキャッシュ６２２に登録されたセキュアハッシュ値の個数が上限に達した場合、他のブルームフィルタを用いてもよい。これにより、ストレージ装置１０１は、偽陽性判定率を抑えることができる。
【０１０９】
また、ストレージ装置１０１によれば、他のブルームフィルタを用いて、ＭＢＦテーブル６２４を更新してもよい。これにより、新しいブルームフィルタは、近いうちに読込要求、または書込要求が起こり易いため、ストレージ装置１０１は、キャッシュヒット率を向上することができる。
【０１１０】
また、ストレージ装置１０１によれば、ＭＢＦキャッシュテーブル６２３のブルームフィルタをテストして書込対象ブロックが登録されている場合、書込ブロックのセキュアハッシュ値と同一の値のブロックを検出し、あれば書き込まなくてもよい。これにより、ストレージ装置１０１は、重複除去を行い、ボリューム１０２の記憶量を削減することができる。
【０１１１】
また、ストレージ装置１０１によれば、ＭＢＦキャッシュテーブル６２３のブルームフィルタをテストして書込対象ブロックが登録されている場合、書込対象ブロックのセキュアハッシュ値と同一の値のブロックを検出し、なければ書き込んでもよい。これにより、ストレージ装置１０１は、偽陽性により誤検出したブロックであっても、正常にブロックの内容を保持することができる。
【０１１２】
また、ストレージ装置１０１によれば、ＭＢＦキャッシュテーブル６２３のブルームフィルタをテストして読込対象ブロックが登録されている場合、ブルームフィルタが示す記憶領域の範囲から、読込対象ブロックのセキュアハッシュ値と同一の値を検出してもよい。これにより、ストレージ装置１０１は、検索する検索範囲が絞り込まれたため、高速に対象のデータを出力することができる。
【０１１３】
また、ストレージ装置１０１によれば、ＭＢＦキャッシュテーブル６２３のブルームフィルタをテストして読込対象ブロックが登録されていなければ、ＭＢＦテーブル６２４のブルームフィルタをテストしてもよい。これにより、ストレージ装置１０１は、メモリにヒットしない場合でも、正常に読込対象のブロックを出力することができる。
【０１１４】
また、ストレージ装置１０１によれば、ＭＢＦテーブル６２４のブルームフィルタのうち、ヒットしたブルームフィルタを、ＭＢＦキャッシュテーブル６２３に設定してもよい。これにより、各ブルームフィルタは、局所性が高くなるようなセキュアハッシュ値が登録されたため、ストレージ装置１０１は、近いうちに読込要求、または書込要求が起こり易いと予想でき、キャッシュヒット率を向上することができる。
【０１１５】
また、ＭＢＦキャッシュテーブル６２３を用いない場合、たとえば最大１０［ＴＢ］の領域を４［ＫＢ］のブロックで管理するならば、ＭＢＦキャッシュテーブル６２３を用いないストレージ装置は、２５００万個のブロックを管理することになる。１ブロックあたり２３［ビット］使用する２段のＭＢＦを使用するストレージ装置は、２．５［ＭＢ］×２３×２［ビット］＝約１４［ＧＢ］のメモリを確保することになる。これに対し、本実施の形態では、領域のサイズと搭載メモリのサイズは無関係になり、たとえば、１０［ＴＢ］の領域を４［ＫＢ］のブロックで管理する場合であっても、ストレージ装置１０１は、１［ＧＢ］以下のメモリでも動作が可能になる。
【０１１６】
なお、本実施の形態で説明した制御方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本制御プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本制御プログラムは、インターネット等のネットワークを介して配布してもよい。
【０１１７】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１１８】
（付記１）複数に分割された記憶領域のいずれかに格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタを記憶する記憶部と、
前記記憶領域への書込対象データの特徴を抽出した第１の特徴量が、前記ブルームフィルタに登録されているかを判断する書込判断部と、
前記第１の特徴量が前記ブルームフィルタに登録されていないと前記書込判断部が判断した場合、前記記憶領域に前記書込対象データを書き込む書込部と、
を有することを特徴とするストレージ装置。
【０１１９】
（付記２）前記ストレージ装置はさらに、
前記書込判断部が、前記第１の特徴量が登録されていないと判断した場合、前記ブルームフィルタに登録済である特徴量の個数に基づいて、前記ブルームフィルタに前記第１の特徴量を登録するかを判定する判定部と、
前記判定部が、前記ブルームフィルタに前記第１の特徴量を登録すると判定した場合、前記ブルームフィルタに前記第１の特徴量を登録する登録部と、
を有し、
前記書込部は、
前記判定部が前記ブルームフィルタに前記第１の特徴量を登録すると判定した場合、前記複数に分割された記憶領域のいずれかに前記書込対象データを書き込むことを特徴とする付記１記載のストレージ装置。
【０１２０】
（付記３）前記ストレージ装置はさらに、
前記判定部が、前記ブルームフィルタに前記第１の特徴量を登録しないと判定した場合、前記ブルームフィルタとは異なる他のブルームフィルタを前記記憶部から取得する取得部を有し、
前記判定部は、
前記取得部が前記他のブルームフィルタを取得した場合、前記他のブルームフィルタに登録済である特徴量の個数に基づいて、前記他のブルームフィルタに前記第１の特徴量を登録するかを判定し、
前記登録部は、
前記判定部が、前記他のブルームフィルタに前記第１の特徴量を登録すると判定した場合、前記他のブルームフィルタに前記第１の特徴量を登録し、
前記書込部は、
前記判定部が、前記他のブルームフィルタに前記第１の特徴量を登録すると判定した場合、前記複数に分割された記憶領域のうち、前記他のブルームフィルタに登録された特徴量を有するデータが格納された領域に前記書込対象データを書き込むことを特徴とする付記２記載のストレージ装置。
【０１２１】
（付記４）前記ストレージ装置はさらに、
前記取得部が、取得した前記他のブルームフィルタに基づいて、前記記憶部の記憶内容を更新する更新部を有することを特徴とする付記３記載のストレージ装置。
【０１２２】
（付記５）前記ストレージ装置はさらに、
前記書込判断部が、前記第１の特徴量が登録されていると判断した場合、前記複数に分割された記憶領域のいずれかから、前記第１の特徴量を有するデータを検出する書込検出部を有し、
前記書込部は、
前記書込検出部が、前記第１の特徴量を有するデータを検出した場合、前記記憶領域に前記書込対象データを書き込まないことを特徴とする付記４記載のストレージ装置。
【０１２３】
（付記６）前記ストレージ装置はさらに、
前記書込判断部が、前記第１の特徴量が登録されていると判断した場合、前記複数に分割された記憶領域のいずれかから、前記第１の特徴量を有するデータを検出する書込検出部を有し、
前記書込部は、
前記書込検出部が、前記第１の特徴量を有するデータを検出しなかった場合、前記記憶領域に前記書込対象データを書き込むことを特徴とする付記４または５に記載のストレージ装置。
【０１２４】
（付記７）前記記憶部は、
前記記憶領域への各書込対象データに対応して、各書込対象データに対応する論理アドレスに関連付けられた各書込対象データの特徴を抽出した特徴量を記憶し、
前記ストレージ装置はさらに、
前記記憶部に記憶された各書込対象データの特徴を抽出した特徴量から、前記記憶領域への読込対象データの論理アドレスに関連付けられた第２の特徴量を選択する選択部と、
前記選択部が選択した前記第２の特徴量が、前記記憶部に記憶された前記ブルームフィルタに登録されているかを判断する読込判断部と、
前記読込判断部が、前記第２の特徴量が登録されていると判断した場合、前記複数に分割された記憶領域のいずれかから、前記第２の特徴量を有するデータを検出する読込検出部と、
前記読込検出部が、前記第２の特徴量を有するデータを検出した場合、前記第２の特徴量を有するデータを出力する出力部と、
を有することを特徴とする付記４〜６のいずれか１項に記載のストレージ装置。
【０１２５】
（付記８）前記記憶部は、
前記複数に分割された記憶領域の各々に格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタを記憶し、
前記ストレージ装置はさらに、
前記読込判断部が、前記第２の特徴量が登録されていないと判断した場合、前記記憶部に記憶された前記複数に分割された記憶領域の各々に格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタのうち、前記第２の特徴量を有するデータが登録されたブルームフィルタを特定する特定部を有し、
前記読込検出部は、
前記複数に分割された記憶領域のうち、前記特定部が特定したブルームフィルタに登録された特徴量を有するデータが格納された領域から、前記第２の特徴量を有するデータを検出することを特徴とする付記７記載のストレージ装置。
【０１２６】
（付記９）前記更新部は、
前記特定部が特定した前記第２の特徴量の特徴量を有するデータが登録されたブルームフィルタに基づいて、前記記憶部の記憶内容を更新することを特徴とする付記８記載のストレージ装置。
【０１２７】
（付記１０）複数に分割された記憶領域のいずれかに格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタを記憶する記憶部と、
前記記憶領域への書込対象データの特徴を抽出した第１の特徴量が、前記ブルームフィルタに登録されているかを判断する書込判断部と、
前記第１の特徴量が前記ブルームフィルタに登録されていないと前記書込判断部が判断した場合、前記記憶領域に前記書込対象データを書き込む書込部と、
を有するコンピュータを含むことを特徴とするストレージ装置。
【０１２８】
（付記１１）複数に分割された記憶領域のいずれかに格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタを記憶する記憶部を有するストレージ装置の制御方法において、
前記ストレージ装置が有する書込判断部が、前記記憶領域への書込対象データの特徴を抽出した第１の特徴量が、前記ブルームフィルタに登録されているかを判断し、
前記第１の特徴量が前記ブルームフィルタに登録されていないと前記書込判断部が判断した場合、前記ストレージ装置が有する書込部が、前記記憶領域に前記書込対象データを書き込むことを特徴とするストレージ装置の制御方法。
【０１２９】
（付記１２）複数に分割された記憶領域のいずれかに格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタを記憶する記憶部を有するストレージ装置の制御プログラムにおいて、
前記ストレージ装置が有する書込判断部に、前記記憶領域への書込対象データの特徴を抽出した第１の特徴量が、前記ブルームフィルタに登録されているかを判断させ、
前記第１の特徴量が前記ブルームフィルタに登録されていないと前記書込判断部が判断した場合、前記ストレージ装置が有する書込部に、前記記憶領域に前記書込対象データを書き込ませることを特徴とするストレージ装置の制御プログラム。
【０１３０】
（付記１３）複数に分割された記憶領域のいずれかに格納されたデータの特徴を抽出した特徴量が登録されたブルームフィルタを記憶する記憶部を有するストレージ装置の制御プログラムを記録したコンピュータが読み取り可能な記録媒体において、
前記ストレージ装置が有する書込判断部に、前記記憶領域への書込対象データの特徴を抽出した第１の特徴量が、前記ブルームフィルタに登録されているかを判断させ、
前記第１の特徴量が前記ブルームフィルタに登録されていないと前記書込判断部が判断した場合、前記ストレージ装置が有する書込部に、前記記憶領域に前記書込対象データを書き込ませることを特徴とするコンピュータが読み取り可能な記録媒体。
【符号の説明】
【０１３１】
１００  ストレージシステム
１０１  ストレージ装置
６０１  書込判断部
６０２  判定部
６０３  取得部
６０４  書込検出部
６０５  書込部
６０６  登録部
６０７  更新部
６１１  選択部
６１２  読込判断部
６１３  特定部
６１４  読込検出部
６１５  出力部
６２０  記憶部
６２１  ブロックマップテーブル
６２２  書込対象のＭＢＦキャッシュ
６２３  ＭＢＦキャッシュテーブル
６２４  ＭＢＦテーブル
６２５  ハッシュログテーブル
【図１】
2014130549.tif 000003
【図２】
2014130549.tif 000004
【図３】
2014130549.tif 000005
【図４】
2014130549.tif 000006
【図５】
2014130549.tif 000007
【図６】
2014130549.tif 000008
【図７】
2014130549.tif 000009
【図８】
2014130549.tif 000010
【図９】
2014130549.tif 000011
【図１０】
2014130549.tif 000012
【図１１】
2014130549.tif 000013
【図１２】
2014130549.tif 000014
【図１３】
2014130549.tif 000015
【図１４】
2014130549.tif 000016
【図１５】
2014130549.tif 000017
【図１６】
2014130549.tif 000018
【図１７】
2014130549.tif 000019
【図１８】
2014130549.tif 000020