(57)【要約】      （修正有）【課題】データ保全性とキャッシュヒット率、及びフラッシュ効率を向上させるキャッシュメモリシステム、及びキャッシュメモリの制御方法を提供する。【解決手段】空きのチャンクへ一旦データ書き込みを行い、データ転送に成功したチャンクのみをキャッシュ上のデータチャンクとすり替える。またチャンクヘッダにストレージ装置３０上のアドレスと有効データサイズを記憶することにより、一部データが有効なチャンクもキャッシュ上に存在させる。更にはストレージ装置３０にフラッシュする際の順序を、ＬＢＡオーダーのソートを行って決める範囲を限定する。【選択図】図１
2010160544.tif 000002
【特許請求の範囲】
【請求項１】
データ処理を行うコンピュータとデータを保存するストレージ装置間で当該ストレージ装置に記憶されるデータをキャッシュするキャッシュメモリシステムにおいて、
キャッシュデータをチャンク単位で管理するキャッシュメモリと、
前記チャンクの内、前記キャッシュデータを書き込みが可能なチャンクを登録するフリーチャンクリストと、
前記キャッシュメモリへの書き込み要求に対して、前記フリーチャンクリストに登録されているチャンクにデータを書き込むデータを転送し、当該転送が完了後、当該データを転送されたチャンクを前記フリーチャンクリストの登録から外すデータ書き込み部と、
を備えることを特徴とするキャッシュメモリシステム。
【請求項２】
データ処理を行うコンピュータとデータを保存するストレージ装置間で当該ストレージ装置に記憶されるデータをキャッシュするキャッシュメモリシステムにおいて、
キャッシュデータをチャンク単位で管理するキャッシュメモリと、
各前記チャンクそれぞれに対応し、当該対応するチャンク内の有効なデータの大きさを示す情報をそれぞれ記憶する複数のチャンクヘッダと、
を備えることを特徴とするキャッシュメモリシステム。
【請求項３】
前記チャンクヘッダは、当該チャンクヘッダが対応する前記チャンクの前記ストレージ装置上の格納されている位置を示すアドレス情報をも記憶することを特徴とする請求項２に記載のキャッシュメモリシステム。
【請求項４】
前記複数のチャンクヘッダは、前記対応するチャンク内の情報の前記ストレージ装置上でのアドレスを示す情報と、前記対応するチャンクの前記キャッシュメモリでの位置を示す情報とをも記憶すると共にＢ＋木構造を有し、
キャッシュヒットまたはキャッシュミスの判定を、前記複数のチャンクヘッダに対して木検索アルゴリズムを用いて行う制御部を更に備えることを特徴とする請求項２に記載のキャッシュメモリシステム。
【請求項５】
データ処理を行うコンピュータとデータを保存するストレージ装置間で当該ストレージ装置に記憶されるデータをキャッシュするキャッシュメモリシステムにおいて、
キャッシュデータをチャンク単位で管理するキャッシュメモリと、
特定のアルゴリズムに従ってパージする前記チャンクを登録するキャッシュパージキューと、
前記キャッシュパージキューの特定範囲より早く前記パージの対象となっている前記チャンクは前記特定のアルゴリズムの順番で登録され、続いて前記特定範囲内の前記チャンクが前記ストレージ装置への書き込みが早くなる順番で登録されるキャッシュフラッシュキューと、
前記キャッシュフラッシュキューに登録されている順番で前記チャンク内のデータを前記ストレージ装置にフラッシュするフラッシュ制御部と、
を備えることを特徴とするキャッシュメモリシステム。
【請求項６】
前記特定のアルゴリズムはＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）アルゴリズムであることを特徴とする請求項５に記載のキャッシュメモリシステム。
【請求項７】
データ処理を行うコンピュータとデータを保存するストレージ装置間で当該ストレージ装置に記憶されるデータをキャッシュするキャッシュメモリの制御方法において、
前記キャッシュメモリ上のキャッシュデータをチャンク単位で管理し、
前記チャンクの内、前記キャッシュデータを書き込みが可能なチャンクをフリーチャンクリストに登録し、
前記キャッシュメモリへの書き込み要求に対して、前記フリーチャンクリストに登録されているチャンクにデータを書き込むデータを転送し、当該転送が完了後、当該データを転送されたチャンクを前記フリーチャンクリストの登録から外す
ことを特徴とするキャッシュメモリの制御方法。
【請求項８】
データ処理を行うコンピュータとデータを保存するストレージ装置間で当該ストレージ装置に記憶されるデータをキャッシュするキャッシュメモリの制御方法において、
前記キャッシュメモリ上のキャッシュデータをチャンク単位で管理し、
各前記チャンクそれぞれに対応するチャンクヘッダに、当該対応するチャンク内の有効なデータの大きさを示す情報をそれぞれ記憶させる
ことを特徴とするキャッシュメモリの制御方法。
【請求項９】
データ処理を行うコンピュータとデータを保存するストレージ装置間で当該ストレージ装置に記憶されるデータをキャッシュするキャッシュメモリの制御方法において、
前記キャッシュメモリ上のキャッシュデータをチャンク単位で管理し、
特定のアルゴリズムに従ってパージする前記チャンクをキャッシュパージキューに登録し、
前記キャッシュパージキューの特定範囲より早く前記パージの対象となっている前記チャンクを前記特定のアルゴリズムの順番でキャッシュフラッシュキューに登録し、
続いて前記特定範囲内の前記チャンクが前記ストレージ装置への書き込みが早くなる順番で前記キャッシュフラッシュキューに登録し、
前記キャッシュフラッシュキューに登録されている順番で前記チャンク内のデータを前記ストレージ装置にフラッシュする、
ことを特徴とするキャッシュメモリの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータとストレージ装置の間に設ける、キャッシュメモリシステムに関し、更に詳しくはストレージ装置へのアクセス速度を高速化するキャッシュメモリシステムに関する。
【背景技術】
【０００２】
コンピュータ上で動作するアプリケーションの処理速度を向上させる方策の１つとして、コンピュータがアクセスするストレージ装置のアクセス速度を高速化することが行われている。
【０００３】
ストレージのアクセス速度を高速化するものとしては、ＤＲＡＭ半導体ディスク装置と呼ばれるＤＲＡＭを記憶媒体としたランダムアドレスアクセスを高速で行うことが出来るストレージ装置がある。一方、シーケンシャルアドレスアクセスに対してのスループットが超高速（１ＧＢ／ｓ以上）なストレージ装置もある。また近年では、フラッシュメモリ型ＳＳＤを搭載したＲＡＩＤ装置が存在する。
【０００４】
しかしながら、ＤＲＡＭ半導体ディスク装置は、容量に制限があり、実際のアプリケーションに適応するには、アクセス頻度の高いデータ（ホットデータ）とアクセス頻度の低いデータ（コールドデータ）を解析分離し、ホットデータのみをＤＲＡＭ半導体ディスク装置へ格納するといった、非常に面倒な作業を必要とする。そのため、なかなか導入に至らないケースが多かった。フラッシュメモリ型のＳＳＤはランダムリードアクセスは非常に高速だが、ランダムライトアクセスは磁気ディスクと同程度の性能しか出ない。したがってランダム書き込みが多いアプリケーションで用いるストレージ装置としては、不向きである。
【０００５】
また、超高速なスループットを実現したストレージ装置は、ハイビジョン映像編集用途には適応しているが、ランダムアクセスの多いエンタープライズ市場向けアプリケーションに対しては、あまり高速化の効果が得られない。そこで、通常の磁気ディスク装置またはフラッシュ型ＳＳＤとホストコンピュータの間に、それらの弱点であるランダムライトアクセスを高速化する大容量キャッシュメモリシステムを設けることが提案されている。このキャッシュメモリシステムを設けることにより、様々なアプリケーションの実行処理速度を高速化することができる。
【０００６】
図１４に一般的なキャッシュメモリシステムする構成を示す。
図１４のキャッシュメモリシステム１２０は、ホストサーバ１１０と複数のハードディスク装置１３１−１〜１３１−ｌ等のソースデバイスを備えたストレージ装置１３０の間に設けられ、ホストサーバ１１０がストレージ装置１３０へアクセスするアクセス速度を向上させる。
【０００７】
図１４のキャッシュメモリシステム１２０は、キャッシュメモリシステム１２０全体を制御する制御ＣＰＵ１２１、ホストサーバ１１０との接続を行うインタフェースであるＳＣＳＩインタフェース１２２、ＳＣＳＩインタフェース１２２を制御するＩ／Ｏ制御部１２３、ストレージ装置１３０との接続を行うインタフェースであるＳＣＳＩインタフェース１２４、ＳＣＳＩインタフェース１２４を制御するＩ／Ｏ制御部１２４、キャッシュデータを記憶保持するキャッシュメモリ１２６、及びキャッシュメモリ１２６を制御するメモリ制御部１２７を有する。
【０００８】
ホストサーバ１１０からストレージ装置１３０に対して読出しが要求されたデータは、ハードディスク装置１３１などのソースデバイスから該当データを読み出してホストサーバ１１０へ転送すると同時にキャッシュメモリシステム１２０のキャッシュメモリ１２６上に格納される（ムーブイン）。またホストサーバ１１０から要求されたデータが、キャッシュメモリ１２６上に存在する場合は、キャッシュメモリシステム１２０は、キャッシュメモリ１２６上のデータを直接ホストサーバ１１０へ転送する（リードキャッシュヒット）。
【０００９】
またホストサーバ１１０からストレージ装置１３０に書き込まれるデータは、一旦キャッシュメモリシステム１２０上に格納され（ムーブイン）、ホストサーバ１１０からのライトコマンドを終了する（ライトバック）。キャッシュメモリ１２６上の更新されたデータは後ほどストレージ装置１３０に書き戻される（フラッシュ）。このとき書き込むデータが、キャッシュメモリ１２６上に存在するデータであったときは、キャッシュメモリシステム１２０はキャッシュメモリ１２６上の既にあるデータへ上書きして、ライトコマンドを完了する（ライトキャッシュヒット）。一方で、キャッシュメモリシステム１２０は、更新されたキャッシュメモリ１２６上のデータを、ストレージ装置１３０のソースデバイスへ順次同期させる（フラッシュ）。
【００１０】
キャッシュメモリシステム１２０は、書き込みデータを一旦キャッシュメモリ１２６上に格納する際に、該当するデータがキャッシュ上に存在せずかつ空きメモリがない場合はいずれかのキャッシュデータを捨てる（パージ）必要がある。選択したキャッシュデータがストレージ装置１３０と同期されていない場合はフラッシュとパージを同時に行う必要がある。また、捨てるデータが既にフラッシュされている場合はパージのみを行う。
【００１１】
なおキャッシュメモリシステム１２０において、制御ＣＰＵ１２１によりＲＡＩＤ（Ｒｅｄｕｎｄａｎｔ  Ａｒｒａｙ  ｏｆ  Ｉｎｄｕｓｔｒｉａｌ  Ｄｉｓｋｓ）機能もあわせて実現すれば、キャッシュメモリシステム１２０及びストレージ装置１３０は所謂キャッシュ機能つきＲＡＩＤ装置となる。
【００１２】
このキャッシュメモリシステムについての文献としては、例えば非特許文献１にはキャッシュデータの管理方法として、キャッシュメモリをセグメント単位で管理し、コンピュータ（ホストサーバ）からのアクセスサイズに対応してセグメントサイズを変更する方式が開示されている。
【００１３】
この非特許文献１の方式では、セグメントサイズを調整することにより、セグメントサイズより小さなデータによる無効領域の軽減を行っている。しかしこの非特許文献１にはＬＢＡ（Ｌｏｇｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ）がセグメント境界の途中から始まっているデータについての救済方法に関しては開示されていない。
【００１４】
また、非特許文献２には、各種キャッシュアルゴリズムを測定比較し、新たなキャッシュアルゴリズムが提案されている。
この非特許文献２には、ホストサーバから書き込まれてデータを効率的にソースデバイスへフラッシュするために、ＬＢＡオーダーに書き込む書き込み方式が開示されている。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】"Optimizing Cache for Individual Workloads with the Hitachi Cache Partition Manager Feature", On Hitachi TagmaStore Adaptable Modular Storage and Workgroup Modular Storage, An Application Brief by Kevin Sampson, April 2006
【非特許文献２】"WOW: Wise Ordering for Writes - Combining Spatial and Temporal Locality in Non-Volatile Caches", Binny S. Gill and Dharmendra S. Modia, IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120
【発明の概要】
【発明が解決しようとする課題】
【００１６】
従来のキャッシュメモリシステムには以下のような問題点がある。
１．ジャンクデータの発生
キャッシュメモリシステムが、キャッシュメモリ上に存在するデータへの書き込み命令を受け取った場合、キャッシュメモリシステムは、キャッシュメモリ上の該当するキャッシュデータに、受信したデータを上書きする（ライトキャッシュヒット）。その際にパリティエラーや転送エラー等の理由で、データ転送が失敗してしまう場合がある。
【００１７】
従来のキャッシュメモリシステムの制御方法では、データ転送が失敗した場合に、キャッシュ上のデータにジャンクデータ（意味のないデータ）を上書きしてしまうという問題がある。
【００１８】
図１５は、ジャンクデータの発生問題を示す図である。
キャッシュメモリ１２６上にホストサーバからの書き込みデータを格納する際、そのデータは、メモリ制御部によってキャッシュメモリ上にＤＭＡ（Ｄｉｒｅｃｔ  Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ）転送されるが、そのＤＭＡ転送の途中でパリティエラーや転送エラーが発生すると、キャッシュメモリ１２６上にジャンクデータが残ってしまう。
２．アドレス境界の問題
図１６に一般的なキャッシュデータ管理方式を示す。
【００１９】
キャッシュメモリ１２６上のデータはセグメント（以下本明細書ではチャンク（ｃｈｕｎｋ）と呼ぶ）単位で管理されている。このデータ管理では、ストレージ装置上のアドレス（ＬＢＡ）の０アドレスから順にチャンクサイズ単位で分割したアドレス単位でデータの読出しや書き込みを行う。そしてキャッシュメモリ１２６の各チャンク２０１は、ハッシュテーブル２００によって管理される。
【００２０】
しかしながら、ホストコンピュータはキャッシュメモリ１２６上のチャンクサイズとは無関係に、チャンクのアドレス境界をまたいでアクセスしてきてしまう。その場合、複数のチャンク上の一部のデータのみを書き込むことになる。
【００２１】
例えば、図１６では、チャンク２０１−１と２０１−２にまたがったデータ２０２が書き込まれているが、チャンク２０１−１では前半部分、チャンク２０１−２では後半部分が更新されていない。したがってこの場合チャンク２０１−１と２０１−２は半分の無効領域を持ってしまう問題がある。
【００２２】
非特許文献１では、セグメントサイズを変更して、無効な領域を軽減する方式が示されているが、この非特許文献１の方式でもアクセスされるＬＢＡアドレスが境界アドレスから始まっていない場合は、同様に無効領域が発生してしまう。
【００２３】
そして無効領域が多いとキャッシュ容量が有効に使用されず、キャッシュヒット率が低下してしまう。また無効領域をなくす方法として、一部データのみしか有効でないチャンクは、データを破棄してしまうという方法をとることにより、この問題を回避することができる。しかし、この方法では最近書き込んだデータがキャッシュに存在しないため、キャッシュヒット率が低下してしまう。
３．データフラッシュの効率化における問題
キャッシュメモリシステムでは、新たにデータをキャッシュメモリ上へ格納（ムーブイン）したいが、キャッシュメモリ上に空きチャンクがない場合、ＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）等に基づいて破棄するチャンクデータを選択し、新しいチャンクデータと入れ替えることを行う。
【００２４】
このときもし選択したチャンクデータが、ストレージ装置への書き込み（同期）がまだ行われていないダーティデータである場合は、選択されたダーティチャンクデータがソースデバイスへの書き込み（フラッシュ）が終了するまで、キャッシュメモリのデータの入れ替えを行うことができない。
【００２５】
一方で、キャッシュメモリシステムからストレージ装置へのデータの書き込み性能を向上させるため、ダーティチャンクデータをＬＢＡ順にソートしてした後にストレージ装置書き込む（フラッシュ）ことにより、ストレージ装置のヘッダシーク時間を短縮することで書き込み性能の向上が期待できる。しかしながら、キャッシュメモリシステムでチャンクの破棄に用いられるＬＲＵオーダーと、ストレージ装置のＬＢＡオーダーには依存関係が無い。
【００２６】
図１７は、このために生じる問題を示す図である。同図において網がけ部分はダーティデータを示しており、また（１）〜（８）は、キャッシュメモリ内のデータのホストサーバからアクセスされた順番、すなわちＬＲＵに基づいた順番を示している。
【００２７】
図１７においては、ＬＲＵオーダーに従い、チャンクデータ（１）、チャンクデータ（２）、・・・の順にキャッシュパージキュー３０１に積まれる。そして、最も古くにアクセスされたデータチャンク（１）を最初に破棄（パージ）することになる。しかしながらデータチャンク（１）はダーティデータのため、ストレージ装置１３０にフラッシュする必要がある。よってチャンクデータ（１）はキャッシュフラッシュキュー３０２に積まれているが、ＬＢＡオーダーではチャンクデータ（５）とチャンク（７）がチャンクデータ（１）より若いアドレスのため、キャッシュフラッシュキュー３０２にはこれらが先に積まれている。したがってこの２つのチャンクデータ（５）、（７）を先にストレージ装置１３０にフラッシュするまでチャンクデータ（１）のフラッシュが待たされ、その間新しいキャッシュデータのムーブインが待たされてしまう。よって、キャッシュメモリ１２６の更新に時間がかかる（ライトコマンドの潜伏時間が長い）という問題がある。
【００２８】
そこで上記問題点を鑑み、本発明はデータ保全性とキャッシュヒット率、及びフラッシュ効率を向上させるキャッシュメモリシステム、及びキャッシュメモリの制御方法を提供することを目的とする。
【課題を解決するための手段】
【００２９】
本発明によるキャッシュメモリシステムは、データ処理を行うコンピュータとデータを保存するストレージ装置間で当該ストレージ装置に記憶されるデータをキャッシュするキャッシュメモリシステムにおいて、キャッシュデータをチャンク単位で管理するキャッシュメモリと、前記チャンクの内、前記キャッシュデータを書き込みが可能なチャンクを登録するフリーチャンクリストと、前記キャッシュメモリへの書き込み要求に対して、前記フリーチャンクリストに登録されているチャンクにデータを書き込むデータを転送し、当該転送が完了後、当該データを転送されたチャンクを前記フリーチャンクリストの登録から外すデータ書き込み部と、を備えることを特徴とする。
【００３０】
本発明の第２のキャッシュメモリシステムは、データ処理を行うコンピュータとデータを保存するストレージ装置間で当該ストレージ装置に記憶されるデータをキャッシュするキャッシュメモリシステムにおいて、キャッシュデータをチャンク単位で管理するキャッシュメモリと、各前記チャンクそれぞれに対応し、当該対応するチャンク内の有効なデータの大きさを示す情報をそれぞれ記憶する複数のチャンクヘッダと、を備えることを特徴とする。
【００３１】
本発明の第３のキャッシュメモリシステムは、データ処理を行うコンピュータとデータを保存するストレージ装置間で当該ストレージ装置に記憶されるデータをキャッシュするキャッシュメモリシステムにおいて、キャッシュデータをチャンク単位で管理するキャッシュメモリと、特定のアルゴリズムに従ってパージする前記チャンクを登録するキャッシュパージキューと、前記キャッシュパージキューの特定範囲より早く前記パージの対象となっている前記チャンクは前記特定のアルゴリズムの順番で登録され、続いて前記特定範囲内の前記チャンクが前記ストレージ装置への書き込みが早くなる順番で登録されるキャッシュフラッシュキューと、前記キャッシュフラッシュキューに登録されている順番で前記チャンク内のデータを前記ストレージ装置にフラッシュするフラッシュ制御部と、を備えることを特徴とする。
【００３２】
又本発明は、キャッシュメモリの制御方法もその範囲に含む。
【発明の効果】
【００３３】
本実施形態のキャッシュメモリシステムによれば、データ保全性とキャッシュヒット率、及びフラッシュ効率を向上させることが出来る。
【図面の簡単な説明】
【００３４】
【図１】本実施形態のキャッシュメモリシステムが前提となるコンピュータシステムを示す図である。
【図２】本実施形態のコンピュータシステムにおけるコンピュータがストレージ装置からデータを読み出す際のデータの流れを示す図である。
【図３】実施形態のコンピュータシステムにおけるコンピュータがストレージ装置にデータの書き込む際のデータの流れを示す図である。
【図４】フリーチャンクリストによる未使用のチャンクの管理を示す図である。
【図５】フリーチャンクリストの構成を示す図である。
【図６】キャッシュメモリ上のチャンクの管理の仕方を示す図である。
【図７】キャッシュメモリへのデータの書き込みに失敗した場合のキャッシュメモリシステムの動作例を示す図である。
【図８】本実施形態のキャッシュメモリシステムのキャッシュメモリにデータを書き込む際の動作を示すフローチャートである。
【図９】一般的な４ｗａｙ連想方式によるキャッシュ検索方法を示す図である。
【図１０】本実施形態のキャッシュメモリシステムで用いられるキャッシュリストの構成例を示す図である。
【図１１】図１０の構成のキャッシュリストを用いた場合のキャッシュメモリへのデータの書き込みを説明する図である。
【図１２】本実施形態のキャッシュメモリシステムにおけるフラッシュの仕方を説明する図である。
【図１３】キャッシュメモリ上のダーティデータをストレージ装置にフラッシュするときの本実施形態のキャッシュメモリシステムの動作を示すフローチャートである。
【図１４】一般的なキャッシュメモリシステムする構成を示す図である。
【図１５】ジャンクデータの発生問題を示す図である。
【図１６】一般的なキャッシュデータ管理方式を示す図である。
【図１７】データフラッシュの効率化における問題を示す図である。
【発明を実施するための形態】
【００３５】
以下に図面を参照しながら本発明の一実施形態について説明する。
図１は、本実施形態のキャッシュメモリシステムが前提となるコンピュータシステムを示す図である。
【００３６】
図１に示すように本実施形態のコンピュータシステム１は、アプリケーションプログラムが稼働している１乃至複数のコンピュータ１０−１〜１０−ｍと１乃至複数のストレージ装置３０−１〜３０−ｎの間にキャッシュメモリシステム２０を設ける構成となっている。そしてキャッシュメモリシステム２０は、コンピュータ１０−１〜１０−ｍがストレージ装置３０−１〜３０−ｎにアクセスする際にキャッシュメモリとして働く。
【００３７】
なおストレージ装置３０−１〜３０−ｎはそれぞれ、ＲＡＩＤ構成のものを使用しても良い。
キャッシュメモリシステム２０は、制御ＣＰＵ２１、ＳＣＳＩインタフェース２２、Ｉ／Ｏ制御部２３、ＳＣＳＩインタフェース２４、Ｉ／Ｏ制御部２５、キャッシュメモリ２６、及びメモリ制御部２７を有する。
【００３８】
制御ＣＰＵ２１は、キャッシュメモリシステム２０全体を制御する制御ユニットである。ＳＣＳＩインタフェース２２は、ホストサーバ１０−１〜１０−ｍとの接続を行うインタフェースである。Ｉ／Ｏ制御部２３は、ＳＣＳＩインタフェース１２２によるホストサーバ１０−１〜１０−ｍとの接続を制御する制御ユニットである。ＳＣＳＩインタフェース２４は、ストレージ装置３０−１〜３０−ｎとの接続を行うインタフェースである。Ｉ／Ｏ制御部２５は、ＳＣＳＩインタフェース２４によるストレージ装置３０−１〜３０−ｎとの接続を制御する制御ユニットである。キャッシュメモリ２６は、ストレージ装置３０−１〜３０−ｎに対するキャッシュデータを記憶保持するメモリである。メモリ制御部２７は、キャッシュメモリ２６へのアクセスを制御する制御ユニットである。
【００３９】
本実施形態のキャッシュメモリシステム２０によるキャッシュメモリの制御は、制御ＣＰＵ２１が、自己のメモリに記憶されたプログラムを実行することによって実現する。
なおキャッシュメモリシステム２０の構成は、図１に示したような制御ＣＰＵ２１がプログラムを実行するプログラム実行型の構成ではなく、専用のハードウエアをロジックで組んだ構成としても良い。
【００４０】
次に本実施形態のコンピュータシステム１におけるコンピュータ１０が、ストレージ装置３０からデータを読み出す際のデータの流れを図２に示す。
本実施形態のコンピュータシステム１では、コンピュータ１０がストレージ装置３０に対してデータの読出しを要求すると、そのデータがキャッシュメモリシステム２０に格納されていない場合、要求されたデータはフロー３１に示すように一旦キャッシュメモリシステム２０のキャッシュメモリ２６に格納され、次にフロー３２に示すようにキャッシュメモリシステム２０からコンピュータ１０にデータが渡される。またコンピュータ１０が要求したデータが既にキャッシュメモリシステム２０に格納されていれば、フロー３２のように、データをキャッシュメモリシステム２０から読み出す。
【００４１】
なおキャッシュメモリシステム２０格納されていない場合の本実施形態のコンピュータシステム１におけるストレージ装置３０からの読出し時のデータの流れは、このようなものには限定されるものではなく、コンピュータ１０がストレージ装置３０からデータの読出しを行うと、そのデータはフロー３１に示すようにキャッシュメモリシステム２０に格納されると同時に、フロー３３に示すようにストレージ装置３０から直接コンピュータ１０にデータが渡される構成としても良い。
【００４２】
次に本実施形態のコンピュータシステム１におけるコンピュータ１０がストレージ装置３０にデータの書き込む際のデータの流れについて図３を用いて説明する。
図３に示すように、コンピュータ２は、アプリケーションプログラム実行中は、ストレージ装置３０に対してランダムに書き込みを行う。このときのデータは、一度キャッシュメモリシステム２０に格納（ムーブイン）され、後述する手順によるソートが行われた後、ストレージ装置３０に格納（フラッシュ）される。
【００４３】
したがって、コンピュータ１０が最近書き込んだデータは全てキャッシュメモリシステム２０内に存在するので、そのデータをコンピュータ１０が読み出すときは、キャッシュメモリシステム２０上のデータを高速に読み出すことが可能となる。
【００４４】
次に本実施形態のキャッシュメモリシステム２０に対するデータの書き込みについて説明する。
キャッシュメモリシステム２０に対するデータの書き込みは、コンピュータ１０がストレージ装置３０からキャッシュメモリシステム２０内に無いデータを読み出そうとしたとき、及びコンピュータ１０がストレージ装置３０に対してデータを書き込んだときに行われる。
【００４５】
このキャッシュメモリシステム２０に対するデータの書き込み時には、パリティエラーや転送エラー等の理由で、データ転送が失敗して、ジャンクデータが発生してしまうことがある。
【００４６】
それに対処するため、本実施形態のキャッシュメモリシステム２０では、キャッシュメモリシステム２０内のキャッシュメモリ１２６上の未使用で書き込みが可能なチャンクを管理するフリーチャンクリストを備える。
【００４７】
図４はフリーチャンクリストによる未使用のチャンクの管理を示す図である。
本実施形態のキャッシュメモリシステム２０では、キャッシュメモリ２６上の領域はチャンク単位で管理されるが、そのうちの現在未使用なチャンクをフリーチャンクリスト４０によって管理する。
【００４８】
コンピュータ１０から、書き込みコマンドやキャッシュメモリ１２６上に無いデータの読出しコマンドを受け取ると、キャッシュメモリシステム２０は、フリーチャンクリスト４０にあるチャンクから現在未使用なチャンクの位置情報を得る（（１）ゲットフリーチャンク）。そして次に（１）で得た位置のチャンクにコンピュータ１０から若しくはストレージ装置３０からのデータをＤＭＡ転送する（（２）ＤＭＡ）。このデータ転送が成功した後、このチャンクとキャッシュ上の該当する（同一ＬＢＡアドレスのデータ）チャンクとを入れ替える（（３）すり替え）。（３）で空きとなったチャンクをフリーチャンクリストへ戻す（（４）プットフリーチャンク）。なお（３）で該当するＬＢＡアドレスのチャンクが無いときはＬＲＵオーダーに基づいて最も古いデータのチャンクと入れ替える。
【００４９】
本実施形態では、空きのチャンクへデータ転送を行った後に、そのチャンクとキャッシュ内で有効となっているチャンクを入れ換えることにより、ジャンクデータの発生を防ぐ。
【００５０】
図５は、フリーチャンクリスト４０の構成を示す図である。
図５において、フリーチャンクリスト４０は、ポインター情報４２及びチャンクヘッダ４２−１〜４２−ｏからなる。
【００５１】
ポインター情報４１は、リスト構造を持つチャンクヘッダ４２の先頭（ヘッド）と最後（テイル）を示すポインター情報である。フリーチャンクリスト４０がこのポインター情報を持つことにより、フリーチャンクリスト４０へのポストやフリーチャンクリストからのチャンクヘッダの引き出しを高速に行うことができる。チャンクヘッダ４２−１〜４２−ｏは、キャッシュメモリ２６上の現在未使用のチャンクについて情報を持つリスト構造を持つデータである。このチャンクヘッダ４２は、キャッシュメモリ２６上の現在未使用のチャンク４３へのポインター情報をチャンク情報として記憶している。又チャンクヘッダ４２−１〜４２−ｏはリスト後続を持つので、新規のチャンクヘッダ４３を加えたり、使用中となったチャンク４３のチャンクヘッダ４２の削除を高速に行うことが出来る。
【００５２】
図６は、キャッシュメモリ２６上のチャンク４３の管理の仕方を示す図である。
各キャッシュメモリ２６上のチャンク４３内のデータが有効なデータかどうかは、チャンクヘッダ４２によって管理する。チャンクヘッダ４２がフリーチャンクリスト４０に登録されていれば、対応するチャンク４３は無効なデータを保持していることを意味し、チャンクヘッダ４２がキャッシュリスト４４に登録されていれば、対応するチャンクは有効なデータを保持していることを意味する。
【００５３】
キャッシュメモリ２６にデータを書き込む際は、まずフリーチャンクリスト４０の先頭からチャンクヘッダ４２を取り出し（ゲットフリーチャンク（図８のＳ２））、このチャンクヘッダ４２のチャンク情報からキャッシュメモリ２６内の空きのチャンク４３の位置を認識し、そのチャンク４３に書き込むデータをＤＭＡ転送する（ＤＭＡ転送（図８のＳ３））。そしてフリーチャンクリスト４０から取り出したチャンクヘッド４２をキャッシュリスト４４に送る（プットキャッシュチャンク（図８のＳ４））。このチャンクヘッダ４２と同一のＬＢＡアドレスのチャンクがあればそのチャンクと置き換えて、無ければそのままキャッシュリスト４４に登録する（チャンク入れ替え（図８のＳ５））。そしてキャッシュリスト４４で置き換えられたチャンクヘッド４２は、フリーチャンクリスト４０に登録される（プットフリーチャンク（図８のＳ６））。
【００５４】
図６に示すように、各チャンク４３内のデータがキャッシュデータとして有効なのかフリーリストのチャンクデータなのかは、そのチャンク４３に対応するチャンクヘッダ４２がフリーチャンクリスト４０に登録されているのかキャッシュリスト４４に登録されているのかによって判断することが出来る。よってキャッシュメモリ２６上の各チャンク４３はデータを保持しているチャンク４３と空きチャンク４３を混在させたまま管理することが出来る。
【００５５】
なおこのフリーチャンクリスト４０及びキャッシュリスト４４は、制御ＣＰＵ２１内の不図示のメモリ内に構築しても、あるいはキャッシュメモリ２６上に構築しても良い。
次にキャッシュメモリ２６へのデータの書き込みに失敗した場合について説明する。
【００５６】
図７は、キャッシュメモリ２６へのデータの書き込みに失敗した場合のキャッシュメモリシステム２０の動作例を示す図である。
キャッシュメモリ２６にデータを書き込む際は、フリーチャンクリスト４０の先頭から書き込み可能なチャンク４３のチャンクヘッダ４２を取り出して（ゲットフリーチャンク（図６のＳ２））、このチャンクヘッダ４２のチャンク情報からキャッシュメモリ２６内の空きのチャンク４３の位置を認識し、そのチャンク４３に書き込むデータをＤＭＡ転送する（ＤＭＡ転送（図６のＳ３））。このＤＭＡ転送を失敗して、チャンク４３に不正な書き込まれた場合は、書き込みコマンドを失敗とたことを、書き込みデータをキャッシュメモリシステム２０に送ってきたホストサーバ１０若しくはストレージ装置３０に書き込みが失敗したことを通知する。そして書き込みが失敗したチャンク４３のチャンクヘッダ４２をフリーチャンクリスト４０に再登録する。失敗を通知されたホストサーバ１０若しくはストレージ３０はデータを再転送して、キャッシュメモリ２６への書き込みを成功させる。
【００５７】
これにより、キャッシュメモリ２６への書き込みに失敗してジャンクデータが生じても、そのジャンクデータが書き込まれたチャンク４３は、空きチャンクとしてフリーチャンクリスト４０に登録される。したがってキャッシュメモリ２６上にジャンクデータが有効なデータとして残ってしまうことはない。
【００５８】
図８は、本実施形態のキャッシュメモリシステム２０のキャッシュメモリ２６にデータを書き込む際の動作を示すフローチャートである。なお同図の処理は、制御ＣＰＵ２１が制御ＣＰＵ２１内の不図示のメモリ上のプログラムを実行することによって実現する。
【００５９】
キャッシュメモリシステム２０は、コマンド受信待ち状態から、ストレージ装置３０へのアクセスコマンドを受信すると、そのコマンドがキャッシュメモリ２６に書き込みを行うものかどうかを判断する。コンピュータ１０からのコマンドが、ストレージ装置３０への書き込みコマンド、若しくはキャッシュメモリ上２６に無いデータの読出しコマンドであったなら、制御ＣＰＵ２１は、受信コマンドをキャッシュメモリ２６への書き込みコマンドと判定する（ステップＳ１）。そして制御ＣＰＵ２１は、ステップＳ２として、フリーチャンクリスト４０の先頭から書き込み可能なチャンクヘッダ４２を取得する。次に制御ＣＰＵ２１は、ステップＳ３としてステップＳ２で取得したチャンクヘッダ４２のチャンク情報からキャッシュメモリ２６内の対応するチャンク４３へ受信データを転送する。
【００６０】
そしてこのステップＳ３のデータ転送に失敗したならば（ステップＳ３、失敗）、制御ＣＰＵ２１はステップＳ７として、ステップＳ２で取得したチャンクヘッダ４２をフリーチャンクリスト４０に再登録する。
【００６１】
またステップＳ３において、チャンク４３へのデータ転送に成功したならば（ステップＳ３、成功）、ステップＳ４として、制御ＣＰＵ２１はステップＳ２で取得したチャンクヘッダ４２をキャッシュリスト４４へ移動する。そして制御ＣＰＵ２１は、ステップＳ５としてこのチャンク４３と同じＬＢＡアドレスのチャンク４３に対応するチャンクヘッダ４２がキャッシュリスト４４に登録されているかどうかを探す。そして登録されていれば、制御ＣＰＵ２１は、ステップＳ５としてそのチャンクヘッダ４２とステップＳ４で移動させた新しいチャンクヘッダとを入れ替える。また登録されていなければステップＳ４で移動させた新しいチャンクヘッダをそのままキャッシュリスト４４に登録する。
【００６２】
そしてステップＳ６として、制御ＣＰＵ２１は、ステップＳ５で入れ替えた古いチャンクヘッダ４２をフリーチャンクリスト４０に登録後、コマンド受信待ち状態に戻す。
このように、本実施形態のキャッシュメモリシステム２０では、キャッシュメモリ２６上の有効なチャンク２６へ直接データ転送することを回避する。そしてフリーチャンクリスト４０から取得したチャンクヘッダ４２に対応する空きチャンク４２へデータ転送を行い、転送に成功した場合のみ、チャンクヘッダ４２をキャッシュリス４４とへ移動して有効なデータと、データ転送に失敗した場合はチャンクヘッダ４２をフリーチャンクリスト４０へ戻します。この管理の仕方により、データ転送が失敗した場合でも、該当するキャッシュ上のチャンク４２に存在する元のデータを破壊することを防ぐことが出来る。
【００６３】
次に、本実施形態のキャッシュメモリシステム２０によるアドレス境界の問題に対する対処について説明する。
まず従来行われているハッシュテーブルによる検索管理について説明する。
【００６４】
図９は一般的な４ｗａｙ連想方式によるキャッシュ検索方法を示す図である。
図９の例では、４ｗａｙなのでハッシュテーブル５１を４個、チャンクサイズを１６ＫＢ（３２ブロック分、１ブロックは５１２（Ｂ）バイト）、最大ＬＢＡアドレスを６５，５３６（２の１６乗、１６（ｂ）ビット）、各ハッシュテーブルで６４個のチャンクを管理とした場合の例を示している。この場合、全チャンク数は６４×４＝２５６、また各チャンクは１６Ｋバイトなので、１６ＫＢ×２５６＝４ＭＢのキャッシュシステムとなっている。
【００６５】
ＬＢＡアドレス５４の内、ビット０からビット４はチャンクサイズ（１６ＫＢ）分のため、参照する必要は無い。ＬＢＡアドレス５４のビット５からビット９の６４個分は、チャンク番号に対応させる。ＬＢＡアドレス５４のビット１０からビット１１は、ハッシュテーブルＩＤ（０〜３）を対応させる。ＬＢＡアドレス５４のビット１２からビット１５は、ハッシュテーブル内にＬＢＡアドレスタグ５２として格納する。
【００６６】
このような構成において、ホストサーバから参照されたＬＢＡアドレスのビット５からビット９を使って各ハッシュテーブル５１参照して、該当するキャッシュデータ候補のＬＢＡアドレスビットを読み出す。そしてこのＬＢＡアドレスビットと要求されたＬＢＡアドレスを比較し、一致していれば、キャッシュヒットと認識する。そしてキャッシュヒットした場合は、セグメントＩＤとハッシュテーブルＩＤから該当するキャッシュデータを識別することができる。
【００６７】
この図９に示したような構成のハッシュテーブルを持ち、このハッシュテーブルを参照することにより、容易にキャッシュ検索を実現できる。
このようなハッシュテーブル参照方式はキャッシュメモリの容量が非常に小さい場合は有効である。しかしキャッシュメモリのサイズが非常に大きい場合は、チャンクの数が大きくなるため、テーブルサイズが非常に大きくなってしまう。そのため、ハッシュテーブル上の該当するチャンク情報を検索する時間が大きくなってしまう。
【００６８】
本実施形態のキャッシュメモリシステム２０は、大容量キャッシュメモリ２６を搭載することを前提としているので、ハッシュテーブル方式を採用するのは効率的ではない。
そこで本実施形態のキャッシュメモリシステム２０では、Ｂ＋木検索等のツリー検索を応用する。
【００６９】
図１０は、本実施形態のキャッシュメモリシステム２０で用いられるキャッシュリスト４４の構成例を示す図である。
本実施形態のキャッシュリスト４４は、図１０に示すようにＢ＋木構造を持つ。このＢ＋構造のキャッシュリスト４４を参照することによって、アクセス要求されたデータがキャッシュメモリ２６上に存在するか否か（キャッシュヒットまたはキャッシュミス）を判定する。
【００７０】
図１０のキャッシュリスト４４には、Ｂ＋木の末端レコードにチャンクヘッダ（ＣＨ）４２を設ける。
そして各チャンクヘッダ４２には、チャンク情報として次のフリーチャンクのアドレス（ＮＥＸＴ＿ＣＨＵＮＫ）、スタートアドレス（ＳＴＡＲＴ＿ＬＢＡ）、有効データ長（Ｎ＿ＬＢＡ）、及びデータアドレス（ＤＡＴＡ＿ＡＤＤＲＥＳＳ）が記録されている。
【００７１】
これらのチャンク情報の内、次のフリーチャンクのアドレス（ＮＥＸＴ＿ＣＨＵＮＫ）は、キャッシュリスト４４内のチャンクヘッダ４２どうしがリスト構造を持つためのポインターで、図６を用いて説明したキャッシュリスト４４内でのチャンクヘッダ４２の入れ替えに用いる。またスタートアドレス（ＳＴＡＲＴ＿ＬＢＡ）は、そのチャンクヘッダ４２に対応するチャンク４３内のデータ（チャンクデータ）のストレージ装置３０でのアドレス（ＬＢＡアドレス）を示す。有効データ長（Ｎ＿ＬＢＡ）は、対応するチャンク４３内のデータのうち有効なデータは先頭から何ブロックかを示す情報である。データアドレス（ＤＡＴＡ＿ＡＤＤＲＥＳＳ）は、そのチャンクヘッド４２に対応するチャンク４３のキャッシュメモリ２６上のアドレス情報である。
【００７２】
図１１は、図１０のような構成のキャッシュリスト４４を用いた場合のキャッシュメモリ２６へのデータの書き込みを説明する図である。
図１１は、コンピュータ１０が任意のアドレスへの任意のサイズの書き込みコマンドを受信した場合の例として、コンピュータ１０からアドレス１２８への書き込みサイズ４０ブロック（１ブロックは５１２バイト）のライトコマンドを発行した場合を例として示している。
【００７３】
このときキャッシュメモリシステム２０では、チャンク４３の大きさを８ＫＢ（１６ブロック分、１ブロックは５１２Ｂ）とすると、Ｂ＋木構造のキャッシュリスト４４には３つの３つのチャンクヘッダ４２が登録され、キャッシュメモリ２６上の３つのチャンク４３にデータが転送される。
【００７４】
このとき３つのチャンク４３のうちチャンク（１）及び（２）は、データを記憶するのに全ての領域を使用するが、チャンク（３）は８ブロック分しか使用しない。したがってチャンク（１）とチャンク（２）に対応するチャンクヘッダ４２内の有効データ長（Ｎ＿ＬＢＡ）は１６（ブロック）となるが、チャンク（３）の有効データ長（Ｎ＿ＬＢＡ）は８（ブロック）となり、チャンク（１）とチャンク（２）は全チャンクデータを使用しているが、チャンク３は有効データ長が全チャンクデータでないことを示す。
【００７５】
このように、各チャンク４３に対応するチャンクヘッダ４２にデータ開始アドレス（ＳＴＡＲＴ＿ＬＢＡ）とチャンクのデータ有効長（Ｎ＿ＬＢＡ）を保持することにより、ホストサーバからの任意のアドレスの任意の長さのデータをキャッシュメモリ２６上に保持することが可能となる。
【００７６】
また上述した例の場合、チャンク（３）のデータのみは全データが有効とは成らないが、従来の方式は書き込みコマンドのアドレスがチャンク４３の境界の先頭にならない限り、無効となってしまうので、それに比べ本方式では最後のチャンクデータが端数の場合のみ無効領域が発生することになります。そのため、従来方式よりキャッシュメモリ２６領域の使用効率を向上させることが出来る。
【００７７】
次に本実施形態のキャッシュメモリシステム２０における、キャッシュメモリ２６上のデータをストレージ装置３０にフラッシュバックする際の処理について説明する。
キャッシュメモリ２６上のデータの内。コンピュータ１０によって書き換えられたダーティデータを全て選択し、これらをＬＢＡオーダーにソートした後にストレージ装置３０にフラッシュバックするのが、ストレージ装置３０のシーク時間等から、フラッシュバックの効率を最も良くすることが知られています。
【００７８】
しかし、同時にキャッシュメモリ２６上の空きチャンクが不足（Ｃａｃｈｅフル）している場合、ＬＲＵオーダーに従い、パージするチャンク４３を緊急にフラッシュする必要が発生する。このとき、パージする予定のチャンク４３が既にＬＢＡオーダーでフラッシュ対象のキューに積まれてしまっていると、そのフラッシュが終了するまで受信したライトコマンドの実行を待たせることになる。
【００７９】
したがって、フラッシュが終了するまで、新しいデータをチャンク４３にムーブインすることができないため、次のコマンドを実行することができないので、コマンドの潜伏時間が長くなり、処理性能が低下してしまう問題がある。
【００８０】
本実施形態のキャッシュメモリシステム２０では、この問題に対処するため下限値を設け、フラッシュを行う順番の決め方をこの下限値に基づいて変更する。
図１２は、本実施形態のキャッシュメモリシステム２０におけるフラッシュの仕方を説明する図である。同図において、（１）〜（１０）は、チャンク４３内のデータがアクセスされた順番を示しており、網がけのチャンク４３はコンピュータ１０によってデーが更新された後、まだストレージ装置３０にパージされていないダーティデータを含むチャンク４３を示している。
【００８１】
キャッシュメモリ２５からパージされるチャンク４３は、そのチャンクヘッド４２がキャッシュパージキュー６１に登録される。この登録はＬＲＵオーダーの順で行われるので、（１）、（２）、・・・となる。なおキャッシュパージキュー６１に登録されたチャンクヘッダ４２はリスト構造を取り、次のチャンクヘッダ４２へのポインターをＮＥＸＴ＿ＬＲＵ＿ＣＨＵＮＫとして記憶している。
【００８２】
そして本実施形態のキャッシュパージキュー６１には下限値Ａと上限値Ｂが設けてある。
一方キャッシュメモリ２６からストレージ装置３０にフラッシュされるデータを含むチャンク４３は、そのチャンクヘッド４２がキャッシュフラッシュキュー６２に登録される。なおキャッシュフラッシュキュー６２に登録されたチャンクヘッダ４２もリスト構造を取り、次のチャンクヘッダ４２へのポインターをＮＥＸＴ＿ＦＬＵＳＨ＿ＣＨＵＮＫとして記憶している。
【００８３】
従来の方式では、キャッシュフラッシュキュー６２への登録はＬＢＡオーダー順にソートして行われていたが、本実施形態のキャッシュメモリシステム２０では、キャッシュパージキュー６１の下限Ａ値より古いダーティデータを含むチャンク４３はＬＢＡオーダーにソートせずに、ＬＲＵ順にキャッシュフラッシュキュー６２に積む。そしてキャッシュパージキュー６１の下限値Ａから上限値Ｂの範囲にあるダーティデータを含むチャンク４３はＬＢＡオーダーにソートしてキャッシュフラッシュキュー６２に積む。
【００８４】
これにより、近いうちにパージされると考えられるチャンク４３内のデータを優先的にストレージ装置３０にフラッシュすることができる。またそれ以外のダーティデータを含むチャンク４３はＬＢＡオーダーにソートしてフラッシュすることで、ストレージ装置３０のヘッダシーク時間を軽減してフラッシュを効率よく行うことが出来る。
【００８５】
このように本実施形態のキャッシュメモリシステム２０によれば、ストレージ装置３０へのフラッシュの高効率を維持しながら、キャッシュムーブインをブロックする現象を低減することが出来る。
【００８６】
なお各チャンクヘッダ４２には、チャンク情報としてこれまで説明したＮＥＸＴ＿ＦＬＵＳＨ＿ＣＨＡＮＫ、ＮＥＸＴ＿ＬＲＵ＿ＣＨＵＮＫ、ＳＴＡＲＴ＿ＬＢＡ、Ｎ＿ＬＢＡ、ＤＡＴＡ＿ＡＤＤＲＥＳＳの他に、フリーチャンクリスト４０のために次のチャンクヘッダのアドレス（ＮＥＸＴ＿ＦＲＥＥ＿ＣＨＵＮＫ）を備える。これらの情報を使って、これまで述べてきたフリーチャンクリスト４０、キャッシュパージキュー６１及びキャッシュフラッシュキュー６２を同時に実現する。
【００８７】
図１３は、キャッシュメモリ２６上のダーティデータをストレージ装置３０にフラッシュするときのキャッシュメモリシステム２０の動作を示すフローチャートである。同図の処理は、制御ＣＰＵ２１が制御ＣＰＵ２１内のメモリ上のプログラムを実行して実現する。
【００８８】
同図の処理では、ＬＢＡオーダーにソートして効率的にフラッシュするためにダーティデータをある程度貯める為、最初にｘ秒のインターバル時間を設けてある（ステップＳ１１、ＮＯ）。
【００８９】
最初にライトコマンドを受信してからｘ秒経過すると（ステップＳ１１、ＹＥＳ）、制御ＣＰＵ２１は、まずステップＳ１２として、キャッシュパージキュー６１のポインターＰを０にリセットする。
【００９０】
そしてポインターＰが指すキャッシュパージキュー６１がダーティデータのチャンク４３のチャンクヘッド４２のときは（ステップＳ１３、ＹＥＳ）、制御ＣＰＵ２１はステップＳ１４としてキャッシュパージキュー６１のポインターＰが指すチャンクヘッダ４２をキャッシュフラッシュキュー６１にポストする。またそしてポインターＰが指すキャッシュパージキュー６１がダーティデータのチャンク４３のチャンクヘッド４２でないときは（ステップＳ１３、ＮＯ）、制御ＣＰＵ２１はステップＳ１４をスキップする。
【００９１】
次に制御ＣＰＵ２１は、ポインターＰを＋１インクリメントする（ステップＳ１５）。そその結果ポインターＰの値が下限値Ａを超えないのならば（ステップＳ１６＜ＮＯ）、ステップＳ１３に処理を戻して、制御ＣＰＵ２１は、ポインターＰが指すキャッシュパージキュー６１の次のヘッダを確認する。
【００９２】
ステップＳ１６において、ポインターＰの値が下限値Ａを超えたならば（ステップＳ１６、ＹＥＳ）、制御ＣＰＵ２１は、ステップＳ１７として、キャッシュパージキュー６１の下限値Ａと上限値Ｂの間のチャンクヘッダ４２をＬＢＡオーダーに並び替え（ＬＡＢオーダーソート）、その順番でチャンクヘッダ４２をキャッシュフラッシュキュー６２へポスト後、処理を最初に戻す。
【００９３】
キャッシュフラッシュキュー６２にポストされたチャンクヘッダ４２に対応するチャンク４３内のデータは、順次ストレージ装置３０へフラッシュされる。
このように、本実施形態のキャッシュメモリシステム２０によるストレージ装置３０へのフラッシュ方法によれば、ＬＲＵオーダーを優先するチャンクデータとＬＢＡオーダーで効率的にフラッシュするチャンクデータを調整することが可能となり、チャンクのパージに処理がまたされることが無くなると共にフラッシュの高速化を実現できる。
【００９４】
以上のように本実施形態のキャッシュメモリシステム２０によれば、磁気ディスクあるいはＳＳＤ（フラッシュメモリディスク）によるストレージ装置３０の弱点であるランダムアクセス書き込みに対する低速性を高速化させることができます。
【００９５】
またキャッシュヒット率を向上させ、ＬＲＵ等に従いパージするデータを優先的にフラッシュしつつ、かつランダムアドレス書き込みによるデータをアドレスオーダー順に並び替えてストレージ装置へ効率よくライトバックすることにより、ストレージ装置への書き込みを向上させシステム性能を画期的に向上させることが出来る。
【００９６】
更には書き込みデータ用にキャッシュデータを事前にパージする必要がないので、リードデータのキャッシュヒット率を向上させることになり、大容ストレージ装置３０をあたかも、ＤＲＡＭベースの超高速半導体ディスク装置のように振舞うことが可能となる。そのため、コンピュータ１０からのあらゆるパターンのデータアクセスを高速に処理することが可能となり、ディスクＩＯのボトルネックを低減し、ランダムアクセスが頻繁に発生するデータベースアプリケーションのバッチジョブ等、処理時間を大幅に短縮させることが出来る。
【符号の説明】
【００９７】
１０、１１０  コンピュータ
２０、１２０  キャッシュメモリシステム
２１、１２１  制御ＣＰＵ
２２、２４、１２２、１２４  ＳＣＳＩインタフェース
２３、２５、１２３、１２５  Ｉ／Ｏ制御部
２６、１２６  キャッシュメモリ
２７、１２７  メモリ制御部
３０          ストレージ装置
４０          フリーチャンクリスト
４１          ポインター情報
４２          チャンクヘッダ
４３          チャンク
４４          キャッシュリスト
６１          キャッシュパージキュー
６２          キャッシュフラッシュキュー
【図４】
2010160544.tif 000003
【図５】
2010160544.tif 000004
【図８】
2010160544.tif 000005
【図９】
2010160544.tif 000006
【図１０】
2010160544.tif 000007
【図１３】
2010160544.tif 000008
【図１５】
2010160544.tif 000009
【図１】
2010160544.tif 000010
【図２】
2010160544.tif 000011
【図３】
2010160544.tif 000012
【図６】
2010160544.tif 000013
【図７】
2010160544.tif 000014
【図１１】
2010160544.tif 000015
【図１２】
2010160544.tif 000016
【図１４】
2010160544.tif 000017
【図１６】
2010160544.tif 000018
【図１７】
2010160544.tif 000019