(57)【特許請求の範囲】
【請求項１】
データ格納手段に格納されるデータをキャッシュするために用いられるキャッシュ格納手段、キャッシュデータテーブル及びキャッシュインデックステーブルを備えるキャッシュ装置に適用されるキャッシュ方法であって、
前記データ格納手段に格納されるデータ及び当該データを示すインデックスを入力するステップと、
前記入力されたデータの内容に対応する識別子を生成するステップと、
前記入力されたデータをキャッシュするための空き領域が前記キャッシュ格納手段に存在するかを判定するステップと、
前記空き領域が前記キャッシュ格納手段に存在すると判定された場合、前記入力されたデータを前記キャッシュ格納手段にキャッシュするステップと、
前記生成された識別子を前記キャッシュされたデータに対応付けて前記キャッシュデータテーブルに登録するステップと、
前記生成された識別子を前記入力されたインデックスに対応付けて前記キャッシュインデックステーブルに登録するステップと、
前記空き領域が前記キャッシュ格納手段に存在しないと判定された場合、当該空き領域を当該キャッシュ格納手段に確保するステップと、
前記確保された空き領域に前記入力されたデータをキャッシュするステップと、
前記確保された領域にキャッシュされていたデータに対応付けて前記キャッシュデータテーブルに登録されている識別子を非登録とするステップと
を具備することを特徴とするキャッシュ方法。
【請求項２】
前記データ格納手段からのデータの読み込みを要求するための当該データを示すインデックスを含む読み込み要求を入力するステップと、
前記入力された読み込み要求に含まれるインデックスに対応付けて前記キャッシュインデックステーブルに登録されている識別子を特定するステップと、
前記キャッシュデータテーブルによって前記特定された識別子に対応付けられているデータが前記キャッシュ格納手段に存在するかを判定するステップと、
前記データが存在すると判定された場合、前記読み込み要求元に対して、当該データを出力するステップと
を更に具備することを特徴とする請求項１記載のキャッシュ方法。
【請求項３】
前記生成された識別子が前記キャッシュデータテーブルに登録されているかを判定するステップを更に具備し、
前記空き領域が存在するかを判定するステップにおいては、前記生成された識別子がキャッシュデータテーブルに登録されていないと判定された場合に、前記空き領域が前記キャッシュ格納手段に存在するかを判定する
ことを特徴とする請求項１記載のキャッシュ方法。
【請求項４】
前記入力されたデータが前記データ格納手段に対する書き込みデータである場合に、当該データを示すインデックスに対応付けて当該キャッシュインデックステーブルに登録されている識別子を取得するステップと、
前記キャッシュデータテーブルを参照して、前記取得された識別子に対応付けられているデータが存在するかを判定するステップと、
前記データが存在すると判定された場合に、前記キャッシュ格納手段に格納されている当該データを前記書き込みデータに更新するステップと
を更に具備することを特徴とする請求項１記載のキャッシュ方法。
【請求項５】
前記データが存在するかを判定するステップにおいて前記データが存在しないと判定された場合、当該データを示すインデックスに対応付けて前記キャッシュインデックステーブルに登録されている識別子を無効化するステップを更に具備することを特徴とする請求項４記載のキャッシュ方法。
【請求項６】
前記識別子を生成するステップにおいては、前記データの内容に対応する識別子として予め定められたハッシュ関数を用いてハッシュ値を生成することを特徴とする請求項１記載のキャッシュ方法。
【請求項７】
前記生成されたハッシュ値が前記キャッシュデータテーブルに登録されているかを判定するステップと、
前記キャッシュデータテーブルに登録されていると判定された場合に、前記生成されたハッシュ値に対応付けられているデータ及び前記入力したデータが同一であるかを判定するステップと、
前記同一でないと判定された場合、ハッシュ衝突を検出するステップと
を更に具備し、
前記ハッシュ衝突が検出された場合には、前記入力されたデータを前記キャッシュ格納手段にキャッシュしないステップを更に具備することを特徴とする請求項６記載のキャッシュ方法。
【請求項８】
前記生成されたハッシュ値が前記キャッシュデータテーブルに登録されているかを判定するステップと、
前記キャッシュデータテーブルに登録されていると判定された場合に、前記生成されたハッシュ値に対応付けられているデータ及び前記入力したデータが同一であるかを判定するステップと、
前記同一でないと判定された場合、ハッシュ衝突を検出するステップと
を更に具備し、
前記ハッシュ衝突が検出された場合に、前記ハッシュ関数とは別のハッシュ関数を用いてハッシュ値を生成するステップとを更に具備することを特徴とする請求項６記載のキャッシュ方法。
【請求項９】
前記生成されたハッシュ値が前記キャッシュデータテーブルに登録されているかを判定するステップと、
前記キャッシュデータテーブルに登録されていると判定された場合に、前記生成されたハッシュ値に対応付けられているデータ及び前記入力したデータが同一であるかを判定するステップと、
前記同一でないと判定された場合、ハッシュ衝突を検出するステップと
を更に具備し、
前記ハッシュ衝突が検出された場合に、前記ハッシュ値とは異なる識別子を生成するステップとを更に具備することを特徴とする請求項６記載のキャッシュ方法。
【請求項１０】
前記入力されたデータは、前記キャッシュ装置とは別に設けられた転送元装置から転送先装置に対して転送される転送データであることを特徴とする請求項１記載のキャッシュ方法。
【請求項１１】
前記データ格納手段は、前記転送元装置に設けられるディスクボリュームであり、
前記入力されたデータは、前記ディスクボリュームに格納されているブロックボリュームであり、
前記インデックスは、前記ディスクボリュームを識別する識別番号及び前記ブロックボリュームが格納されている論理ブロックアドレスを含む
ことを特徴とする請求項１０記載のキャッシュ方法。
【請求項１２】
データ及び当該データを示すインデックスを入力する入力手段と、
前記入力されたデータの内容に対応する識別子を生成する識別子生成手段と、
前記入力されたデータをキャッシュするための空き領域がキャッシュ格納手段に存在するかを判定する判定手段と、
前記空き領域が存在すると判定された場合、前記入力されたデータをキャッシュするキャッシュ格納手段と、
前記生成された識別子が前記キャッシュ格納手段にキャッシュされたデータに対応付けて登録されるキャッシュデータテーブルと、
前記生成された識別子が前記入力されたインデックスに対応付けて登録されるキャッシュインデックステーブルと、
前記空き領域が前記キャッシュ格納手段に存在しないと判定された場合、当該空き領域を当該キャッシュ格納手段に確保する確保手段と、
前記確保された空き領域に前記入力されたデータをキャッシュするキャッシュ処理手段と、
前記確保された領域にキャッシュされていたデータに対応付けて前記キャッシュデータテーブルに登録されている識別子を非登録とする非登録手段と
を具備することを特徴とするキャッシュ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データをキャッシュするキャッシュ方法及びキャッシュ装置に関する。
【背景技術】
【０００２】
近年、例えばインターネット（Internet）のような、ＬＡＮ（Local Area Network）と比較して帯域が細く遅延が大きい回線を利用して遠隔地にあるストレージ装置にアクセスするためのＷＡＮ加速化装置（ＷＡＮ高速化装置）と呼ばれる装置が知られている。
【０００３】
このＷＡＮ加速化装置は、例えばＴＣＰ／ＩＰのレイヤまたはＮＦＳ（Network File System）／ＣＩＦＳ（Common Internet File System）／ｉＳＣＳＩ（Internet Small Computer Systems Interface）等のアプリケーションレイヤで、遅延制御・転送データ圧縮・キャッシュを行う。
【０００４】
ところで、このＷＡＮ加速化装置に限らず、キャッシュに用いられる記憶領域の大きさは有限である。ここで、例えばＷＡＮ加速化装置において、当該ＷＡＮ加速化装置と例えばインターネットを介して接続されているストレージ装置上のデータがキャッシュされる場合を想定する。この場合、ストレージ装置にある記憶領域（例えばディスクボリューム）のサイズと、ＷＡＮ加速化装置上のキャッシュに用いられる記憶領域の大きさは、一般的には後者の方が小さい。
【０００５】
よって、限られた記憶領域の中で、如何に有効なキャッシュ制御を行うかが重要である。そこで、例えばＬＲＵ（Least Recent Used）のような時間的局所性または空間的局所性に注目したキャッシュ制御の方法が検討されている。
【０００６】
また一方で、インデックス（例えばアドレスまたはファイル名等）は異なっているが同一の内容のデータ（以下、同一データと表記）が、既にキャッシュ上に登録されている場合、当該同一データを別の領域にキャッシュするのではなく、既にキャッシュされているデータをポイントする技術（以下、先行技術と表記）が開示されている（例えば、非特許文献１を参照）。これにより、同一データ（同一の内容のキャッシュデータ）は共有される。このように同一の内容のキャッシュデータを共有することにより、キャッシュデータを格納するための記憶領域を節約することが可能となる。
【０００７】
この先行技術によれば、データの内容が同じであるか否かを判定するために、当該データのハッシュ値を求め、このハッシュ値を利用することで高速に検索し、その後にデータ自体が比較される。
【０００８】
一般的に、データを格納するために要する記憶領域の大きさに対して、データに対するポインタ（つまり、メモリアドレス）を格納するのに要する記憶領域の大きさは、はるかに小さい。このことから、上記した先行技術を用いることにより限られた記憶領域の中でキャッシュするデータ量を増やすことができる。
【非特許文献１】Carl A. Waldspurger, VMware Inc. “Memory Resource Management in VMware ESX Server”, USENIX OSDI ’02, (2002)
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記した先行技術では、例えばキャッシュ用の記憶領域が枯渇した際に、必要性の低いキャッシュデータを破棄した場合には、同一データをポイントしていたインデックスについてもキャッシュデータは同時に破棄される。
【００１０】
更に、破棄された後に再び同一データがキャッシュされたとき、破棄される前に当該同一データをポイントしていたインデックスを、再びこの同一データをポイントさせて再登録することもできない。
【００１１】
例えば同一データが破棄された後に再びキャッシュされた場合に、当該破棄される前に同一データをポイントしていたインデックスに対して例えば読み込み（リード）要求があった場合を想定する。この場合、このインデックスは再びキャッシュされた同一データに対してはポイントされていない（再登録されていない）ため、既に同一データがキャッシュされているにもかかわらず当該同一データを例えばストレージ装置から取得する（読み込む）必要がある。
【００１２】
本発明の目的は、複数のインデックスからポイントされているキャッシュデータが破棄された後に当該データが再びキャッシュに登録されたとき、当該複数のインデックスに当該データをポイントさせることができるキャッシュ方法及びキャッシュ装置を提供することにある。
【課題を解決するための手段】
【００１３】
本発明の１つの態様によれば、データキャッシュするために用いられるキャッシュ格納手段、キャッシュインデックステーブル及びキャッシュデータテーブルを備えるキャッシュ装置に適用されるキャッシュ方法が提供される。この方法は、データ及び当該データを示すインデックスを入力するステップと、前記入力されたデータの内容に対応する識別子を生成するステップと、前記入力されたデータをキャッシュするための空き領域が前記キャッシュ格納手段に存在するかを判定するステップと、前記空き領域が前記キャッシュ格納手段に存在すると判定された場合、前記入力されたデータを前記キャッシュ格納手段にキャッシュするステップと、前記生成された識別子を前記キャッシュされたデータに対応付けて前記キャッシュデータテーブルに登録するステップと、前記生成された識別子を前記入力されたインデックスに対応付けて前記キャッシュインデックステーブルに登録するステップと、前記領域が前記キャッシュ格納手段に存在しないと判定された場合、当該空き領域を確保するステップと、前記確保された空き領域に前記入力されたデータをキャッシュするステップと、前記確保された領域にキャッシュされていたデータに対応付けて前記キャッシュデータテーブルに登録されている識別子を非登録とするステップとを具備する。
【発明の効果】
【００１４】
本発明によれば、複数のインデックスからポイントされているキャッシュデータが破棄された後に、当該データが再びキャッシュに登録されたとき、当該複数のインデックスに当該データをポイントさせることを可能とする。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して、本発明の実施形態について説明する。
【００１６】
図１は、本実施形態に係る中継装置（キャッシュ装置）のハードウェア構成を示すブロック図である。図１に示すように、コンピュータ１０は、例えばハードディスクドライブ（ＨＤＤ）のような外部記憶装置２０と接続されている。この外部記憶装置２０は、コンピュータ１０によって実行されるプログラム２１を格納する。コンピュータ１０及び外部記憶装置２０は、中継装置３０を構成する。
【００１７】
図２は、本実施形態に係る中継装置３０の主として機能構成を示すブロック図である。中継装置３０は、クライアント装置（転送先装置）４０及びストレージ装置（転送元装置）と通信可能に接続されている。中継装置３０とクライアント装置４０との間では、例えばｉＳＣＳＩ（Internet Small Computer System Interface）による通信が実行される。中継装置３０とストレージ装置５０との間についても同様である。
【００１８】
クライアント装置４０は、例えばストレージ装置５０に対してアクセスする装置である。また、クライアント装置４０は、ｉＳＣＳＩ（ＳＣＳＩ）でのイニシエータ（Initiator）としての機能を有する。
【００１９】
ストレージ装置５０は、各種データを格納するディスクボリュームを備える。ストレージ装置５０は、クライアント装置４０に対して当該ストレージ装置５０のディスクボリュームへのアクセスを提供する。ストレージ装置５０は、ｉＳＣＳＩ（ＳＣＳＩ）でのターゲット（Target）としての機能を有する。
【００２０】
中継装置３０は、例えばクライアント装置４０及びストレージ装置５０の通信を中継する。中継装置３０は、例えばストレージ装置５０から送信されたデータ（ブロックボリューム）をクライアント装置４０に転送する。このとき、中継装置３０は、この転送されるデータをキャッシュする機能を有する。これにより、クライアント装置及びストレージ装置５０間のデータ転送効率を向上させる。
【００２１】
クライアント装置４０からは、中継装置３０のクライアント装置４０側インタフェイスを指定してストレージ装置５０への接続を試みる。それを受け付けた中継装置３０では、ストレージ装置５０側インタフェイスからストレージ装置５０に対して接続を行う。これにより、クライアント装置４０とストレージ装置５０間の接続が確立される。
【００２２】
なお、クライアント装置４０側／ストレージ装置５０側インタフェイスは物理的に１つのインタフェイスであっても良い。例えばｉＳＣＳＩであれば、ＴＣＰ／ＩＰのＩＰアドレスやポート番号で別インタフェイスであることが識別可能であれば十分である。
【００２３】
中継装置３０は、中継部３１、キャッシュ管理部３２及び識別子生成部３３を含む。本実施形態において、中継部３１、キャッシュ管理部３２及び識別子生成部３３は、図１に示されるコンピュータ１０が外部記憶装置２０に格納されているプログラム２１を実行することにより実現されるものとする。このプログラム２１は、コンピュータ読み取り可能な記憶媒体に予め格納して頒布可能である。また、このプログラム２１が、例えばネットワークを介してコンピュータ１０にダウンロードされても構わない。
【００２４】
また、中継装置３０は、キャッシュ格納部２２、キャッシュデータテーブル２３及びキャッシュインデックステーブル２４を含む。本実施形態において、キャッシュ格納部２２、キャッシュデータテーブル２３及びキャッシュインデックステーブル２４は、外部記憶装置２０に格納される。
【００２５】
中継部３１は、例えばクライアント装置４０及びストレージ装置５０間でｉＳＣＳＩ−ＰＤＵを中継する。このｉＳＣＳＩ−ＰＤＵが、データ転送に関わるもの（READ&SCSI DATAIN／WRITE&DATAOUT）であれば、キャッシュ管理部３２を通してキャッシュへのアクセスが実行される。一方、このＩＳＣＳＩ−ＰＤＵがデータ転送に関わらないものであれば、当該ＰＤＵは、そのまま相手先に対して中継部３１により転送される。
【００２６】
ここで、例えばクライアント装置４０がストレージ装置５０からデータの読み込み（リード）を行う場合を想定する。この場合、クライアント装置４０は、リード要求を中継装置３０に送信する。このリード要求には、例えば読み込み（リード）の対象となるデータを示すインデックスが含まれる。インデックスは、例えば読み込みの対象となるデータのファイル名または当該データが格納されているストレージ装置５０内のアドレス等を含む。中継部３１は、クライアント装置４０によって送信されたリード要求を入力する。中継部３１は、入力されたリード要求をストレージ装置５０に転送する。中継部３１は、転送されたリード要求に応じて読み出されたデータ（リード要求に含まれるインデックスによって示されるデータ）をストレージ装置５０から入力する。
【００２７】
一方、例えばクライアント装置４０がストレージ装置５０に対してデータの書き込み（ライト）を行う場合を想定する。この場合、クライアント装置４０は、ライト要求を中継装置３０に送信する。このライト要求には、例えば書き込み（ライト）の対象となるデータ及び当該データを示すインデックスが含まれる。インデックスは、例えば書き込みの対象となるデータのファイル名または当該データを書き込み先であるストレージ装置５０内のアドレス等を含む。中継部３１は、クライアント装置４０によって送信されたライト要求を入力する。中継部３１は、入力されたライト要求をストレージ装置５０に転送する。
【００２８】
キャッシュ管理部３２は、例えば読み込みの対象となるデータまたは書き込みの対象となるデータ（以下、対象データと表記）に対するキャッシュ制御を実行する。キャッシュ管理部３２は、対象データをキャッシュするための空き領域がキャッシュ格納部２２に存在するか否かを判定する。キャッシュ管理部３２は、対象データをキャッシュするための空き領域が存在する場合、当該対象データをキャッシュ格納部２２の当該空き領域に格納することによって当該対象データをキャッシュする。また、キャッシュ管理部３２は、対象データをキャッシュするための空き領域が存在しない場合、例えばキャッシュ格納部２２に格納されているデータ（キャッシュデータ）を削除することによって当該空き領域を確保する。
【００２９】
キャッシュ管理部３２は、対象データの内容に対応する識別子を、当該対象データに対応付けてキャッシュデータテーブル２３に登録する。また、キャッシュ管理部３２は、対象データの内容に対応する識別子を、当該対象データを示すインデックスに対応付けてキャッシュインデックステーブル２４に登録する。
【００３０】
また、例えばクライアント装置４０からリード要求があった場合、キャッシュ管理部３２は、当該リード要求に含まれるインデックスに応じてキャッシュヒットの判定を行う。キャッシュヒットした場合には、キャッシュ格納部２２に格納されているデータが、中継部３１を介してクライアント装置４０に送出される。一方、キャッシュミスヒットの場合には、リード要求がストレージ装置５０に転送され、当該リード要求によって指定されるデータがストレージ装置５０から読み出される。
【００３１】
また、キャッシュ管理部３２は、キャッシュ格納部２２からキャッシュデータが削除（空き領域が確保）された場合には、当該データに対応付けてキャッシュデータテーブル２３に登録されている識別子を削除することにより、当該識別子を非登録とする。
【００３２】
識別子生成部３３は、キャッシュ管理部３２から例えば対象データを受け取る。識別子生成部３３は、受け取られた例えば対象データの内容に対応する識別子を生成する。このとき、識別子生成部３３は、識別子の生成に例えばＭＤ５またはＳＨＡ１のような予め定められたハッシュ関数を用いる。つまり、識別子生成部３３は、識別子としてハッシュ値を生成する。
【００３３】
キャッシュデータテーブル２３には、上記したキャッシュ格納部２２に格納（キャッシュ）された対象データ（キャッシュデータ）に対応付けて、当該対象データの内容に対応するハッシュ値（識別子）が保持（登録）される。
【００３４】
キャッシュインデックステーブル２４には、上記したリード要求またはライト要求に含まれるインデックスに対応付けて、当該リード要求またはライト要求によって指定される対象データの内容に対応するハッシュ値が保持（登録）される。なお、以下の説明では、例えば対象データが読み込まれる、または書き込まれるディスクボリュームのシリアル番号及び論理ブロックアドレス（ＬＢＡ：Logical Block Address）の組合せをインデックスとする。シリアル番号は、ストレージ装置５０内にあるディスクボリュームを識別するための番号であり、中継装置３０からストレージ装置に対して例えば問い合わせのＣＤＢ（Command Descriptor Block）を発行することで取得される。また、ｉＳＣＳＩの場合は、ｉＳＣＳＩ−ＩｎｉｔｉａｔｏｒＮａｍｅ及びＬＵＮの組をシリアル番号として利用することも可能であり、様々な実現方法がある。
【００３５】
なお、キャッシュインデックステーブル２４は、ストレージ装置５０上に存在する全てのディスクボリューム毎に用意されている。つまり、ストレージ装置５０内にあるディスクボリュームの各々に対応するキャッシュインデックステーブル２４が存在する。また、例えばストレージ装置５０内に新たにディスクボリュームが作成された場合には、当該作成されたディスクボリュームに対応するキャッシュインデックステーブル２４が作成される。例えばインデックス（シリアル番号及び論理ブロックアドレス）によって示されるデータのハッシュ値が生成されていない場合には、例えば無効を示すハッシュ値（例えば、値が全て０）が当該インデックスに対応付けてキャッシュインデックステーブル２４に登録されている。
【００３６】
キャッシュインデックステーブル２４に登録されるハッシュ値は、例えば論理ブロックアドレスのａセクタ（５１２バイトの倍数）単位のデータのハッシュ値である。以下では、便宜的に１セクタ（５１２バイト）単位とする。
【００３７】
図３は、キャッシュデータテーブル２３のデータ構造の一例を示す。図３に示すように、キャッシュデータテーブル２３には、キャッシュデータ（格納先のアドレス）及び識別子が対応付けて登録されている。ここでは、キャッシュデータのアドレスは、当該キャッシュデータがキャッシュ格納部２２に格納されているアドレスであり、例えば８バイトで表される。また、識別子は、対応付けられているデータの内容から、予め定められたハッシュ関数（例えば、ＳＨＡ１）を用いて生成されたハッシュ値である。また、このハッシュ値は、例えば２０バイトで表される。
【００３８】
図３に示す例では、キャッシュデータのアドレス「０ｘ１５Ａ０００１００００２００００（８バイト）」に対応付けてハッシュ値「０ｘ５Ｃ３ＥＢ８００６６４２０００２ＢＣ３ＤＣＣ７ＣＡ４ＡＢ６ＥＦＡＤ７ＥＤ４ＡＥ５（２０バイト）」が登録されている。データのアドレス「０ｘ１５Ａ０００１００００２０２００」に対応付けてハッシュ値「０ｘＦ２８Ｅ８ＢＤＢ１Ｆ９５０３３Ｄ３１Ｄ３３２ＡＤ１Ｃ１９２Ｅ５２６３６８７Ｆ２７」が登録されている。また、データのアドレス「０ｘ１５Ａ０００１００００２０４００」に対応付けてハッシュ値「０ｘＢ３７６８８５ＡＣ８４５２Ｂ６ＣＢＦ９ＣＥＤ８１Ｂ１０８０ＢＦＤ５７０Ｄ９Ｂ９１」が登録されている。
【００３９】
図４は、キャッシュインデックステーブル２４のデータ構造の一例を示す。図４に示すように、キャッシュインデックステーブル２４には、ディスクボリュームのシリアル番号、論理ブロックアドレス（ＬＢＡ）及び識別子が登録されている。キャッシュインデックステーブル２４では、ディスクボリュームのシリアル番号及び論理ブロックアドレスの組合せをインデックスとしている。また、キャッシュインデックステーブル２４は、ディスクボリューム（ディスクボリュームのシリアル番号）毎に存在する。
【００４０】
また、図４に示すように、キャッシュインデックステーブル２４には、シリアル番号によって識別されるディスクボリューム内の論理ブロックアドレス毎に対応付けて識別子が登録されている。
【００４１】
ここでは、ディスクボリュームのシリアル番号は、例えば１０バイトで表される。また、論理ブロックアドレスは、４バイトで表される。識別子は、ディスクボリュームのシリアル番号及び論理ブロックアドレスによって示される（論理ブロックアドレスに格納されている）データの内容から、予め定められたハッシュ関数（例えば、ＳＨＡ１）を用いて生成されたハッシュ値である。このハッシュ値は、例えば２０バイトで表される。
【００４２】
図４には、シリアル番号が「０ｘＦ４ＢＡＡＣＤＤＤ８ＦＡ４ＡＣＢＦ８３４」によって識別されるディスクボリュームに対応するキャッシュインデックステーブル２４が示されている。図４に示す例では、論理ブロックアドレス「０ｘ００００００００（４バイト）」に対応付けてハッシュ値「０ｘ５Ｃ３ＥＢ８００６６４２０００２ＢＣ３ＤＣＣ７ＣＡ４ＡＢ６ＥＦＡＤ７ＥＤ４ＡＥ５（２０バイト）」が登録されている。論理ブロックアドレス「０ｘ０００００００１」に対応付けてハッシュ値「０ｘＦ２８Ｅ８ＢＤＢ１Ｆ９５０３３Ｄ３１Ｄ３３２ＡＤ１Ｃ１９２Ｅ５２６３６８７Ｆ２７」が登録されている。論理ブロックアドレス「０ｘ０００００００３」に対応付けてハッシュ値「０ｘＢ３７６８８５ＡＣ８４５２Ｂ６ＣＢＦ９ＣＥＤ８１Ｂ１０８０ＢＦＤ５７０Ｄ９Ｂ９１」が登録されている。論理ブロックアドレス「０ｘ０００００００７」に対応付けてハッシュ値「０ｘ５Ｃ３ＥＢ８００６６４２０００２ＢＣ３ＤＣＣ７ＣＡ４ＡＢ６ＥＦＡＤ７ＥＤ４ＡＥ５」が登録されている。
【００４３】
次に、図５を参照して、キャッシュデータテーブル２３及びキャッシュインデックステーブル２４の関係について説明する。なお、図５においては、上記した図３及び図４とは異なり、キャッシュデータテーブル２３及びキャッシュインデックステーブル２４に保持（登録）されているディスクボリュームのシリアル番号、論理ブロックアドレス、識別子（ハッシュ値）及びデータのアドレスについては、便宜的に簡略化して記載されている。
【００４４】
図５では、ディスクボリュームのシリアル番号「１」によって識別されるストレージ装置５０内のディスクボリュームに対応するキャッシュインデックステーブル２４について説明する。
【００４５】
このキャッシュインデックステーブル２４には、論理ブロックアドレス「１」に対応付けて識別子「ハッシュ値１」が登録されている。また、論理ブロックアドレス「２」に対応付けて識別子「ハッシュ値２」、論理ブロックアドレス「３」に対応付けて識別子「ハッシュ値３」、論理ブロックアドレス「４」に対応付けて識別子「ハッシュ値１」が登録されている。つまり、論理ブロックアドレス「１」に格納されているデータ及び論理ブロックアドレス「４」に格納されているデータは同一データである。換言すれば、論理ブロックアドレス「１」及び論理ブロックアドレス「４」は、同一データをポイントしている状態である。
【００４６】
一方、キャッシュデータテーブル２３には、識別子「ハッシュ値１」に対応付けてキャッシュデータのアドレスとして「アドレス１」が登録されている。また、識別子「ハッシュ値２」に対応付けてキャッシュデータのアドレスとして「アドレス２」、識別子「ハッシュ値３」に対応付けてキャッシュデータのアドレスとして「アドレス３」が登録されている。
【００４７】
また、キャッシュ格納部２２の「アドレス１」にはデータＡが格納されている。キャッシュ格納部２２の「アドレス２」にはデータＢが格納されている。また、キャッシュ格納部２２の「アドレス３」にはデータＣが格納されている。
【００４８】
なお、データＡは、キャッシュ格納部２２の「アドレス１」にキャッシュされているデータであり、ストレージ装置５０のディスクボリュームシリアル番号「１」の論理ブロックアドレス「１」及び論理ブロックアドレス「４」に格納されているデータ（と同一）である。
【００４９】
データＢは、キャッシュ格納部２２の「アドレス２」にキャッシュされているデータであり、ストレージ装置５０のディスクボリュームシリアル番号「１」の論理ブロックアドレス「２」に格納されているデータ（と同一）である。
【００５０】
また、データＣは、キャッシュ格納部２２の「アドレス３」にキャッシュされているデータであり、ストレージ装置５０のディスクボリュームシリアル番号「１」の論理ブロックアドレス「３」に格納されているデータ（と同一）である。
【００５１】
上記したように、キャッシュデータテーブル２３及びキャッシュインデックステーブル２４は、識別子（ハッシュ値）により関連付けられている。これにより、例えばクライアント装置４０からストレージ装置５０に対してリード要求があった場合には、中継装置３０は、当該リード要求に含まれるインデックス（ディスクボリュームシリアル番号及び論理ブロックアドレス）からキャッシュ格納部２２に格納されているキャッシュデータを特定できる。
【００５２】
次に、図６のフローチャートを参照して、例えばクライアント装置４０からリード要求があった場合における中継装置３０のキャッシュヒット判定処理の処理手順について説明する。クライアント装置４０から送信されるリード要求には、当該リード要求によって指定される（読み込みの対象となる）データを示すインデックスが含まれる。このインデックスには、リード要求によって指定されるデータが格納されているストレージ装置５０内のディスクボリュームを識別するディスクボリュームシリアル番号及び当該ディスクボリューム内の論理ブロックアドレスが含まれる。
【００５３】
まず、中継装置３０中継部３１は、クライアント装置４０から送信されたリード要求を入力（受信）する。中継部３１は、入力されたリード要求をキャッシュ管理部３２に渡す。
【００５４】
次に、キャッシュ管理部３２は、中継部３１から渡されたリード要求に含まれるディスクボリュームシリアル番号によって識別されるディスクボリュームに対応するキャッシュインデックステーブル２４を特定する（ステップＳ１）。
【００５５】
キャッシュ管理部３２は、特定されたキャッシュインデックステーブル２４において、リード要求に含まれる論理ブロックアドレスに対応付けて登録されているハッシュ値を特定する。キャッシュ管理部３２は、特定されたハッシュ値が有効であるか否かを判定する（ステップＳ２）。
【００５６】
例えば上述したようにリード要求によって指定されるデータのハッシュ値が生成されていない場合には、当該データが格納されている論理ブロックアドレスに対応付けて無効を示すハッシュ値（例えば、値が全て０）が登録されている。
【００５７】
つまり、キャッシュ管理部３２は、特定されたハッシュ値が無効を示すハッシュ値でない場合には、当該ハッシュ値が有効であると判定する。
【００５８】
特定されたハッシュ値が有効であると判定された場合（ステップＳ２のＹＥＳ）、キャッシュ管理部３２は、当該ハッシュ値を取得する（ステップＳ３）。
【００５９】
キャッシュ管理部３２は、取得されたハッシュ値がキャッシュデータテーブル２３に存在するか否かを判定する（ステップＳ４）。
【００６０】
取得されたハッシュ値がキャッシュデータテーブル２３に存在すると判定された場合（ステップＳ４のＹＥＳ）、キャッシュ管理部３２は、当該ハッシュ値に対応付けてキャッシュデータテーブル２３に登録されているキャッシュデータのアドレスを特定する（ステップＳ５）。
【００６１】
キャッシュ管理部３２は、キャッシュ格納部２２を参照して、特定されたアドレスに格納（キャッシュ）されているデータ（キャッシュデータ）を取得する。キャッシュ管理部３２は、取得されたデータを、中継部３１を介してクライアント装置４０に出力（送信）する（ステップＳ６）。
【００６２】
例えばクライアント装置４０からストレージ装置５０に対してリード要求が送信された場合には、上記したようにして当該リード要求によって指定されるデータがキャッシュ格納部２２にキャッシュされているかの判定（キャッシュヒット判定）の処理が実行される。
【００６３】
一方、ステップＳ２において特定されたハッシュ値が有効でないと判定された場合、リード要求によって指定されるデータはキャッシュされていない、つまり、キャッシュミスヒットであるとして処理は終了される。
【００６４】
また、ステップＳ４において取得されたハッシュ値がキャッシュデータテーブル２３に存在しないと判定された場合、キャッシュミスヒットであるとして処理は終了される。
【００６５】
次に、中継装置３０のキャッシュ格納部２２にデータを登録（つまり、キャッシュ）する処理手順について説明する。なお、このキャッシュ格納部２２にデータを登録する処理（以下、キャッシュ登録処理と表記）は、例えばクライアント装置４０からストレージ装置５０に対する要求がリード要求である場合とライト要求である場合とで、実行されるタイミングが異なる。
【００６６】
ここで、図７のフローチャートを参照して、例えばクライアント装置４０からストレージ装置５０に対してリード要求が送信された場合の処理の流れについて説明する。
【００６７】
まず、クライアント装置４０は、中継装置３０にリード要求を送信する（ステップＳ１１）。
【００６８】
中継装置３０では、クライアント装置４０によって送信されたリード要求が入力される。ここで、中継装置３０は、上記した図６に示すようにキャッシュヒット判定処理を実行する（ステップＳ１２）。
【００６９】
ここで、中継装置３０によるキャッシュヒット判定処理においてキャッシュミスヒットであった場合を想定する。この場合、中継装置３０は、リード要求をストレージ装置５０に対して転送する（ステップＳ１３）。なお、キャッシュヒットであった場合には、中継装置３０は、キャッシュデータをクライアント装置４０に対して送信し、処理は終了される。
【００７０】
ストレージ装置５０では、中継装置３０によって転送されたリード要求によって指定されるデータ（読み込みデータ）が読み出される（ステップＳ１４）。ストレージ装置５０は、読み出されたデータを中継装置３０に送信する。
【００７１】
中継装置３０は、ストレージ装置５０によって送信されたデータをクライアント装置４０に対して転送する（ステップＳ１５）。
【００７２】
中継装置３０は、ストレージ装置５０によって送信されたデータに対してキャッシュ登録処理（以下、第１のキャッシュ登録処理と表記）を実行する（ステップＳ１６）。
【００７３】
次に、図８のフローチャートを参照して、例えばクライアント装置４０からストレージ装置５０に対してライト要求が送信された場合の処理の流れについて説明する。なお、ライト要求には、当該ライト要求によって指定されるデータ（書き込みデータ）及び当該データを示すインデックスが含まれる。このインデックスには、例えば書き込みデータが書き込まれるストレージ装置５０内のディスクボリュームを識別するディスクボリュームシリアル番号及び当該ディスクボリュームの論理ブロックアドレスが含まれる。
【００７４】
まず、クライアント装置４０は、中継装置３０にライト要求を送信する（ステップＳ２１）。
【００７５】
中継装置では、クライアント装置４０によって送信されたライト要求が入力される。中継装置３０は、入力されたライト要求をストレージ装置３０に対して転送する（ステップＳ２２）。中継装置３０によってライト要求が転送されると、ストレージ装置５０では、当該ライト要求に応じてデータの書き込み処理が実行される。
【００７６】
一方、中継装置３０では、クライアント装置４０によって送信されたライト要求によって指定されるデータ（書き込みデータ）に対してキャッシュ登録処理（以下、第２のキャッシュ登録処理と表記）が実行される（ステップＳ２３）。
【００７７】
ここで、図９のフローチャートを参照して、上記した図７に示すステップ１６及び図８に示すステップＳ２３のキャッシュ登録処理の処理手順について説明する。
【００７８】
なお、上記したようにクライアント装置４０からの要求の種類（リード要求またはライト要求）に応じて、キャッシュ登録処理が実行されるタイミングは異なる。しかしながら、上記した第１及び第２のキャッシュ登録処理は、中継装置３０（の中継部３１）によってディスクボリュームシリアル番号、論理ブロックアドレス及びデータ（読み込みデータまたは書き込みデータ）が入力されることによって実行される。このため、第１及び第２のキャッシュ登録処理は同一の処理である。よって、以下、同一の処理であるものとして説明する。
【００７９】
なお、ディスクボリュームシリアル番号及び論理ブロックアドレスは、例えばリード要求またはライト要求に含まれるインデックスである。また、中継装置３０によって入力されるデータを対象データとして説明する。
【００８０】
中継部３１は、入力されたディスクボリュームシリアル番号、論理ブロックアドレス及び対象データをキャッシュ管理部３２に渡す。キャッシュ管理部３２は、渡された対象データを識別子生成部３３に送出する。
【００８１】
識別子生成部３３は、キャッシュ管理部３２によって送出された対象データの内容に対応する識別子を生成する。このとき、識別子生成部３３は、識別子としてハッシュ値を生成する。このハッシュ値は、例えばＳＨＡ１のような予め定められたハッシュ関数を用いて生成される。
【００８２】
キャッシュ管理部３２は、識別子生成部３３によって生成されたハッシュ値を取得する（ステップＳ３１）。
【００８３】
次に、キャッシュ管理部３２は、取得されたハッシュ値がキャッシュデータテーブル２３に存在するか否かを判定する（ステップＳ３２）。
【００８４】
取得されたハッシュ値がキャッシュデータテーブル２３に存在しないと判定された場合（ステップＳ３２のＮＯ）、キャッシュ管理部３２は、例えばキャッシュ格納部２２に対象データを格納（キャッシュ）するための空き領域が存在するか否か、つまり、キャッシュ格納部２２の記憶領域が枯渇したか否かを判定する（ステップＳ３３）。
【００８５】
キャッシュするための空き領域が存在しないと判定された場合（ステップＳ３３のＮＯ）、キャッシュ管理部３２は、キャッシュ格納部２２内に対象データをキャッシュするための空き領域を確保する。このとき、キャッシュ管理部３２は、キャッシュ格納部２２にキャッシュされているキャッシュデータのうち、例えば最も必要性の低いデータを当該キャッシュ格納部２２から削除する。ここで、最も必要性の低いデータは、例えば時間的・空間的局所性を考慮して判別される。例えばＬＲＵ（Least Recent Used）等を適用することが考えられる。
【００８６】
また、キャッシュ管理部３２は、確保された領域に格納されていたキャッシュデータのアドレス及び当該キャッシュデータの内容に対応する識別子（ハッシュ値）をキャッシュデータテーブル２３から削除することにより、非登録とする。
【００８７】
キャッシュ格納部２２に対象データをキャッシュするための空き領域が確保されると、キャッシュ管理部３２は、当該対象データをキャッシュ格納部２２の確保された領域にキャッシュする（ステップＳ３５）。また、キャッシュ管理部３２は、キャッシュされた対象データが格納されたアドレス及び当該対象データの内容に対応する識別子（エントリ）をキャッシュデータテーブル２３に追加（登録）する（ステップＳ３５）。なお、対象データの内容に対応する識別子は、上記したステップＳ３１において生成されたハッシュ値である。
【００８８】
次に、キャッシュ管理部３２は、中継部３１から渡されたディスクボリュームシリアル番号によって識別されるディスクボリュームに対応するキャッシュインデックステーブル２４を特定する。キャッシュ管理部３２は、特定されたキャッシュインデックステーブル２４において、中継部３１から渡された論理ブロックアドレスに対応付けられているハッシュ値を上記したステップＳ３１において取得されたハッシュ値に書き換える（ステップＳ３６）。
【００８９】
一方、ステップＳ３２において取得されたハッシュ値がキャッシュデータテーブル２３に存在すると判定された場合、キャッシュ管理部３２は、当該取得されたハッシュ値に対応付けてキャッシュデータテーブル２３に登録されているアドレスを特定する。キャッシュ管理部３２は、キャッシュ格納部２２の特定されたアドレスに格納されているデータ（キャッシュデータ）及び対象データが同一であるか否かを判定する（ステップＳ３７）。
【００９０】
キャッシュ格納部２２の特定されたアドレスに格納されているデータ及び対象データが同一であると判定された場合（ステップＳ３７のＹＥＳ）、ステップＳ３６の処理が実行される。
【００９１】
一方、ステップＳ３７においてキャッシュ格納部２２の特定されたアドレスに格納されているデータ及び対象データが同一でないと判定された場合、同一のハッシュ値で複数のデータに対応しているためハッシュ衝突が検出される。例えばハッシュ衝突が検出された場合、対象データに対するキャッシュ登録処理は終了される。つまり、対象データはキャッシュされない。
【００９２】
なお、ハッシュ衝突が検出されると、それまでハッシュ値の生成に用いられていたハッシュ関数とは別のハッシュ関数を用いてハッシュ値が生成される構成でもよい。また、ハッシュ値とは別の識別子が生成され、当該別の識別子が第２識別子として付与される構成であっても構わない。これにより、例えばハッシュ衝突を回避しながらキャッシュ登録処理を実行することが可能となる。
【００９３】
また、例えばクライアント装置４０からストレージ装置５０に対する要求がライト要求である場合における上記したキャッシュ登録処理では、既にキャッシュされているデータに対するライト要求のときは当該データが書き込みデータに更新され、キャッシュされていないデータに対するライト要求のときは書き込みデータがキャッシュされる。しかしながら、例えばキャッシュされていないデータに対するライト要求のときは、書き込みデータをキャッシュせず、例えば当該ライト要求に含まれるディスクボリュームシリアル番号及び論理ブロックアドレスに対応付けてキャッシュインデックステーブル２４に登録されている識別子（ハッシュ値）を無効化する構成でもよい。この場合、ライト要求によって指定される書き込みデータは、例えばストレージ装置５０から読み出された場合に中継装置３０内においてキャッシュされる。
【００９４】
次に、図１０を参照して、本実施形態の動作について具体的に説明する。図１０に示すように、まず、キャッシュインデックステーブル２４ａには、インデックス１に対応付けてハッシュ値１が登録されている。同様に、インデックス２に対応付けてハッシュ値２、インデックス３に対応付けてハッシュ値３、インデックス４に対応付けてハッシュ値１が登録されているものとする。一方、キャッシュデータテーブル２３ａには、ハッシュ値１に対応付けてアドレス１が登録されている。同様に、ハッシュ値２に対応付けてアドレス２、ハッシュ値３に対応付けてアドレス３が登録されているものとする。なお、例えばキャッシュ格納部２２のアドレス１に格納（キャッシュ）されているデータをデータＡとする。
【００９５】
つまり、アドレス１に格納されているデータＡは、キャッシュインデックステーブル２４ａに登録されているインデックス１及びインデックス４によって示されるデータである。
【００９６】
ここで、例えばデータＡが格納されている領域（アドレス１によって示される領域）が、例えばキャッシュ格納部２２の記憶領域が枯渇したことにより空き領域として確保された場合を想定する。この場合、キャッシュデータテーブル２３ａに登録されていたハッシュ値１及びアドレス１は、当該キャッシュデータテーブル２３ａから削除されることにより、非登録とされる。これにより、図１０に示すように、キャッシュデータテーブル２３ａは、キャッシュデータテーブル２３ｂとなる。
【００９７】
よって、上記したインデックス１及びインデックス４によって示されるデータ（データＡ）はキャッシュされていない状態となる。
【００９８】
一方、キャッシュデータテーブル２３ａに登録されていたハッシュ値１及びアドレス１が非登録とされた場合であっても、キャッシュインデックステーブル２４ａに登録されているインデックス及びハッシュ値は非登録とされない。このため、キャッシュインデックステーブル２４ａは、キャッシュインデックステーブル２４ｂ（キャッシュインデックステーブル２４ａと同じ）となる。
【００９９】
ここで、例えばインデックス１を含むリード要求がクライアント装置４０によって送信された場合を想定する。なお、インデックス１によって示されるデータは、データＡである。この場合、例えば上述したようなキャッシュ登録処理によってデータＡは、キャッシュ格納部２２にキャッシュされる。このとき、データＡは、キャッシュ格納部２２のアドレス１にキャッシュされたものとする。
【０１００】
この場合、キャッシュデータテーブル２３ｂには、データＡの内容に対応するハッシュ値１及び当該データＡのアドレス１が対応付けて登録される。つまり、図１０に示すように、キャッシュデータテーブル２３ｂは、キャッシュデータテーブル２３ｃとなる。
【０１０１】
これにより、上記したキャッシュデータテーブル２３ｂの段階でインデックス１及びインデックス４によって示されるデータＡは、キャッシュされていない状態となったにもかかわらず、例えばインデックス１を含むリード要求に応じてデータＡが再キャッシュされることにより、インデックス４に対してもキャッシュされた状態とすることができる。
【０１０２】
よって、例えばインデックス４を含むリード要求があった場合には、インデックス４に対するキャッシュ登録処理が実行されていない場合であっても、キャッシュヒットの判定がされ、高速にデータを転送することが可能となる。
【０１０３】
上記したように本実施形態においては、キャッシュデータテーブル２３及びキャッシュインデックステーブル２４を管理することにより、複数のインデックスからポイントされているキャッシュデータが破棄された後に当該データが再びキャッシュされたとき、当該複数のインデックスに当該データをポイントさせることができる。
【０１０４】
つまり、キャッシュデータテーブル２４から識別子（ハッシュ値）及びデータのアドレスが非登録とされた場合であっても、キャッシュインデックステーブルのエントリ（ハッシュ値）は非登録とされない。これにより、例えばキャッシュデータテーブル２４から非登録とされたエントリが再びキャッシュに登録されると、当該エントリをポイントしていた全てのキャッシュインデックステーブルのエントリが有効になる。よって、複数からポイントされているキャッシュデータが破棄された場合の、キャッシュミスヒットによる弊害を小さくすることができる。これにより、効率的なデータ転送を行うことが可能となる。
【０１０５】
なお、上記した本実施形態においては、中継装置３０においてストレージ装置５０内のディスクボリュームに格納されているデータ（ブロックボリューム）をキャッシュするものとして説明したが、上記した本実施形態に係るキャッシュ方法は、本実施形態において説明した以外の一般的なキャッシュについても適用可能である。例えばキャッシュ格納部２２、キャッシュデータテーブル２３及びキャッシュインデックステーブル２４が、例えばコンピュータ１０のメモリに格納される構成であっても構わない。
【０１０６】
また、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。
【図面の簡単な説明】
【０１０７】
【図１】本発明の実施形態に係る中継装置のハードウェア構成を示すブロック図。
【図２】本実施形態に係る中継装置３０の主として機能構成を示すブロック図。
【図３】キャッシュデータテーブル２３のデータ構造の一例を示す図。
【図４】キャッシュインデックステーブル２４のデータ構造の一例を示す図。
【図５】キャッシュデータテーブル２３及びキャッシュインデックステーブル２４の関係について説明するための図。
【図６】クライアント装置４０からのリード要求があった場合における中継装置３０のキャッシュヒット判定処理の処理手順を示すフローチャート。
【図７】クライアント装置４０からストレージ装置５０に対してリード要求が送信された場合の処理の流れを示すフローチャート。
【図８】クライアント装置４０からストレージ装置５０に対してライト要求が送信された場合の処理の流れを示すフローチャート。
【図９】中継装置３０におけるキャッシュ登録処理の処理手順を示すフローチャート。
【図１０】本実施形態の動作について具体的に説明するための図。
【符号の説明】
【０１０８】
１０…コンピュータ、２０…外部記憶装置、２２…キャッシュ格納部、２３…キャッシュデータテーブル、２４…キャッシュインデックステーブル、３０…中継装置、３１…中継部、３２…キャッシュ管理部、３３…識別子生成部、４０…クライアント装置、５０…ストレージ装置。
【図１】
0004405533.tif 000002
【図２】
0004405533.tif 000003
【図３】
0004405533.tif 000004
【図４】
0004405533.tif 000005
【図５】
0004405533.tif 000006
【図６】
0004405533.tif 000007
【図７】
0004405533.tif 000008
【図８】
0004405533.tif 000009
【図９】
0004405533.tif 000010
【図１０】
0004405533.tif 000011