(57)【要約】【課題】ストレージのための第１キャッシュおよび第２キャッシュにおけるトラックのキャッシュ管理のためのコンピュータ・プログラム製品、システム、および方法が提供される。【解決手段】第１キャッシュは、入力／出力（Ｉ／Ｏ）要求に従う該ストレージ内の改変済みトラックおよび未改変トラックを維持する。改変済みトラックおよび未改変トラックは第１キャッシュからデモートされる。第１キャッシュからデモートされる改変済みトラックおよび未改変トラックは第２キャッシュへプロモートされる。第２キャッシュからデモートされる未改変トラックは廃棄される。ストレージ・デバイス上で近接する物理的位置に存在する第２キャッシュ内の改変済みトラック同士はグループ化され、それらのグループ化された改変済みトラックは第２キャッシュからストレージ・デバイスへデステージングされる。【選択図】図１
2014519650.tif 000002
【特許請求の範囲】
【請求項１】
第１キャッシュ、第２キャッシュ、およびストレージ・デバイスを含むキャッシュ・システムにおいてデータを管理するためのコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品は、操作を行うべく実行するコンピュータ可読プログラム・コードがその中に具体化されているコンピュータ可読記憶媒体を含み、前記操作は：
入力／出力（Ｉ／Ｏ）要求に従う前記ストレージ内の改変済みトラックおよび未改変トラックを前記第１キャッシュにおいて維持することと；
改変済みトラックおよび未改変トラックを前記第１キャッシュからデモートすることと；
前記第１キャッシュからデモートされた前記改変済みトラックおよび前記未改変トラックを前記第２キャッシュへプロモートすることと；
前記第２キャッシュからデモートされた未改変トラックを廃棄することと；
前記ストレージ・デバイス上で近接する物理的位置に存在する前記第２キャッシュ内の改変済みトラックをグループ化することと；
前記グループ化された改変済みトラックを前記第２キャッシュから前記ストレージ・デバイスへデステージングすることと；
を含む、コンピュータ・プログラム製品。
【請求項２】
前記第１キャッシュは前記第２キャッシュより高速のアクセスのデバイスであり、前記第２キャッシュは前記ストレージより高速のアクセスのデバイスである、請求項１に記載のコンピュータ・プログラム製品。
【請求項３】
前記第１キャッシュはランダム・アクセス・メモリ（ＲＡＭ）を含み、前記第２キャッシュはフラッシュ・デバイスを含み、前記ストレージ・デバイスはシーケンシャル書き込みデバイスを含む、請求項１に記載のコンピュータ・プログラム製品。
【請求項４】
前記操作は：
前記第２キャッシュ内の前記改変済みトラックを前記ストレージにおけるそれらの物理的位置に基づく配列で示す空間的インデックスを維持することをさらに含み、前記空間的インデックスは、前記ストレージ・デバイス上で近接する物理的位置に存在するグループ化されるべき前記改変済みトラックを前記空間的インデックスにおけるそれらの順序に基づいて決定するために使用される、請求項１に記載のコンピュータ・プログラム製品。
【請求項５】
前記操作は：
デモートされるべき前記第１キャッシュ内の改変済みトラックがシーケンシャルなトラックであるか否か判定することと；
シーケンシャルであると判定されたデモートされるべき前記改変済みトラックを、前記第２キャッシュをバイパスして前記ストレージに書き込むことと；
ノンシーケンシャルであると判定されたデモートされるべき前記改変済みトラックを前記第２キャッシュへプロモートすることと；
をさらに含む、請求項１に記載のコンピュータ・プログラム製品。
【請求項６】
前記第２キャッシュへプロモートされる前記第１キャッシュからデモートされる前記改変済みトラックおよび未改変トラックはオンライン・ライン・トランザクション・プロセッシング（ＯＬＴＰ）トラックを含む、請求項１に記載のコンピュータ・プログラム製品。
【請求項７】
前記操作は：
シーケンシャルな未改変トラックであるデモートされるべき前記未改変トラックを、前記デモートされるシーケンシャルな未改変トラックを前記第２キャッシュにも前記ストレージにも書き込まずに廃棄することをさらに含み、前記第１キャッシュからデモートされる未改変ノンシーケンシャル・トラックは前記第２キャッシュへプロモートされる、請求項１に記載のコンピュータ・プログラム製品。
【請求項８】
前記操作は：
前記第１キャッシュ内の未改変ノンシーケンシャル・トラックを示す第１ＬＲＵリストを維持することと；
前記第１キャッシュ内の未改変シーケンシャル・トラックを示す第２ＬＲＵリストを維持することと；
前記第１キャッシュ内の未改変ノンシーケンシャル・トラックをデモートすることを決定することと；
デモートされるべき前記未改変ノンシーケンシャル・トラックを決定するために前記第１ＬＲＵリストを使用することと；
前記第１キャッシュ内の未改変シーケンシャル・トラックをデモートすることを決定することと；
デモートされるべき前記未改変シーケンシャル・トラックを決定するために前記第２ＬＲＵリストを使用することと；
をさらに含む、請求項１に記載のコンピュータ・プログラム製品。
【請求項９】
前記操作は：
前記第２キャッシュ内の未改変トラックの最長時間未使用（ＬＲＵ）リストを維持することと；
スペースを解放するために前記第２キャッシュからトラックがデモートされる必要があると判定することと；
前記第２キャッシュ内の未改変トラックの前記ＬＲＵリストから未改変トラックを決定することと；
前記第２キャッシュからの前記決定された未改変トラックを無効にすることと；
をさらに含む、請求項１に記載のコンピュータ・プログラム製品。
【請求項１０】
前記操作は：
前記第１キャッシュからデモートされた改変済みトラックおよび未改変トラックを前記第２キャッシュにおいてログ・ストラクチャード・アレイ（ＬＳＡ）に格納することと；
前記第２キャッシュ内のトラックと、各トラックのために前記ＬＳＡにおける前記トラックの位置を示す前記トラックのための制御ブロックを指すポインタとを示す前記第２キャッシュのためのＬＳＡインデックスを維持することと；
をさらに含む、請求項１に記載のコンピュータ・プログラム製品。
【請求項１１】
前記操作は：
前記第１キャッシュに加えられた改変済みトラックをキャッシュ・バックアップ・デバイスに書き込むことと；
前記第１キャッシュ内の改変済みトラックを示す第１キャッシュ改変済みＬＲＵリストを維持することと；
前記キャッシュ・バックアップ・デバイスからデータをデステージングすると決定することと；
前記第１キャッシュ改変済みＬＲＵリストが満杯であることに応答して前記第１キャッシュからデステージングされるべき改変済みトラックを決定するために前記第１キャッシュ改変済みＬＲＵリストを使用することと；
デモートされるべき前記決定された改変済みトラックのコピーであるトラックを前記キャッシュ・バックアップ・デバイスから廃棄することと；
をさらに含む、請求項１に記載のコンピュータ・プログラム製品。
【請求項１２】
前記操作は：
要求されたトラックのための読み出し要求を受け取ることと；
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュ内に存在するものを取り出すことと；
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュ内に見出されなくて前記第２キャッシュ内に存在するものを取り出すことと；
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュおよび第２キャッシュ内に見出されないものを前記ストレージから取り出すことと；
前記要求されたトラックのうちの前記第２キャッシュおよび前記ストレージから取り出されたものを前記第１キャッシュへプロモートすることと；
をさらに含む、請求項１に記載のコンピュータ・プログラム製品。
【請求項１３】
ストレージ・デバイスと通信するシステムであって：
第１キャッシュと；
第２キャッシュと；
プロセッサと；
操作を行うために前記プロセッサによって実行されるコードを有するコンピュータ可読記憶媒体とを含み、前記操作は：
入力／出力（Ｉ／Ｏ）要求に従う前記ストレージ内の改変済みトラックおよび未改変トラックを前記第１キャッシュにおいて維持することと；
改変済みトラックおよび未改変トラックを前記第１キャッシュからデモートすることと；
前記第１キャッシュからデモートされた前記改変済みトラックおよび前記未改変トラックを前記第２キャッシュへプロモートすることと；
前記第２キャッシュからデモートされた未改変トラックを廃棄することと；
前記ストレージ・デバイス上で近接する物理的位置に存在する前記第２キャッシュ内の改変済みトラックをグループ化することと；
前記グループ化された改変済みトラックを前記第２キャッシュから前記ストレージ・デバイスへデステージングすることと；
を含む、システム。
【請求項１４】
前記第１キャッシュはランダム・アクセス・メモリ（ＲＡＭ）を含み、前記第２キャッシュはフラッシュ・デバイスを含み、前記ストレージ・デバイスはシーケンシャル書き込みデバイスを含む、請求項１３に記載のシステム。
【請求項１５】
前記操作は、前記第２キャッシュ内の前記改変済みトラックを前記ストレージにおけるそれらの物理的位置に基づく配列で示す空間的インデックスを維持することをさらに含み、前記空間的インデックスは、前記ストレージ・デバイス上で近接する物理的位置に存在するグループ化されるべき前記改変済みトラックを前記空間的インデックスにおけるそれらの順序に基づいて決定するために使用される、請求項１３に記載のシステム。
【請求項１６】
前記操作は：
デモートされるべき前記第１キャッシュ内の改変済みトラックがシーケンシャルなトラックであるか否か判定することと；
シーケンシャルであると判定されたデモートされるべき前記改変済みトラックを、前記第２キャッシュをバイパスして前記ストレージに書き込むことと；
ノンシーケンシャルであると判定されたデモートされるべき前記改変済みトラックを前記第２キャッシュへプロモートすることと；
をさらに含む、請求項１３に記載のシステム。
【請求項１７】
前記操作は：
シーケンシャルな未改変トラックであるデモートされるべき前記未改変トラックを、前記デモートされるシーケンシャルな未改変トラックを前記第２キャッシュにも前記ストレージにも書き込まずに廃棄することをさらに含み、前記第１キャッシュからデモートされる未改変ノンシーケンシャル・トラックは前記第２キャッシュへプロモートされる、請求項１３に記載のシステム。
【請求項１８】
前記操作は：
前記第１キャッシュ内の未改変ノンシーケンシャル・トラックを示す第１ＬＲＵリストを維持することと；
前記第１キャッシュ内の未改変シーケンシャル・トラックを示す第２ＬＲＵリストを維持することと；
前記第１キャッシュ内の未改変ノンシーケンシャル・トラックをデモートすることを決定することと；
デモートされるべき前記未改変ノンシーケンシャル・トラックを決定するために前記第１ＬＲＵリストを使用することと；
前記第１キャッシュ内の未改変シーケンシャル・トラックをデモートすることを決定することと；
デモートされるべき前記未改変シーケンシャル・トラックを決定するために前記第２ＬＲＵリストを使用することと；
をさらに含む、請求項１３に記載のシステム。
【請求項１９】
前記操作は：
要求されたトラックのための読み出し要求を受け取ることと；
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュ内に存在するものを取り出すことと；
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュ内に見出されなくて前記第２キャッシュ内に存在するものを取り出すことと；
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュおよび第２キャッシュ内に見出されないものを前記ストレージから取り出すことと；
前記要求されたトラックのうちの前記第２キャッシュおよび前記ストレージから取り出されたものを前記第１キャッシュへプロモートすることと；
をさらに含む、請求項１３に記載のシステム。
【請求項２０】
入力／出力（Ｉ／Ｏ）要求に従うストレージ内の改変済みトラックおよび未改変トラックを第１キャッシュにおいて維持することと；
改変済みトラックおよび未改変トラックを前記第１キャッシュからデモートすることと；
前記第１キャッシュからデモートされた前記改変済みトラックおよび前記未改変トラックを第２キャッシュへプロモートすることと；
前記第２キャッシュからデモートされた未改変トラックを廃棄することと；
前記ストレージ・デバイス上で近接する物理的位置に存在する前記第２キャッシュ内の改変済みトラックをグループ化することと；
前記グループ化された改変済みトラックを前記第２キャッシュから前記ストレージ・デバイスへデステージングすることと；
を含む、方法。
【請求項２１】
前記第１キャッシュはランダム・アクセス・メモリ（ＲＡＭ）を含み、前記第２キャッシュはフラッシュ・デバイスを含み、前記ストレージ・デバイスはシーケンシャル書き込みデバイスを含む、請求項２０に記載の方法。
【請求項２２】
前記第２キャッシュ内の前記改変済みトラックを前記ストレージにおけるそれらの物理的位置に基づく配列で示す空間的インデックスを維持することをさらに含み、前記空間的インデックスは、前記ストレージ・デバイス上で近接する物理的位置に存在するグループ化されるべき前記改変済みトラックを前記空間的インデックスにおけるそれらの順序に基づいて決定するために使用される、請求項２０に記載の方法。
【請求項２３】
デモートされるべき前記第１キャッシュ内の改変済みトラックがシーケンシャルなトラックであるか否か判定することと；
シーケンシャルであると判定されたデモートされるべき前記改変済みトラックを、前記第２キャッシュをバイパスして前記ストレージに書き込むことと；
ノンシーケンシャルであると判定されたデモートされるべき前記改変済みトラックを前記第２キャッシュへプロモートすることと；
をさらに含む、請求項２０に記載の方法。
【請求項２４】
シーケンシャルな未改変トラックであるデモートされるべき前記未改変トラックを、前記デモートされるシーケンシャルな未改変トラックを前記第２キャッシュにも前記ストレージにも書き込まずに廃棄することをさらに含み、前記第１キャッシュからデモートされる未改変ノンシーケンシャル・トラックは前記第２キャッシュへプロモートされる、請求項２０に記載の方法。
【請求項２５】
前記第１キャッシュ内の未改変ノンシーケンシャル・トラックを示す第１ＬＲＵリストを維持することと；
前記第１キャッシュ内の未改変シーケンシャル・トラックを示す第２ＬＲＵリストを維持することと；
前記第１キャッシュ内の未改変ノンシーケンシャル・トラックをデモートすることを決定することと；
デモートされるべき前記未改変ノンシーケンシャル・トラックを決定するために前記第１ＬＲＵリストを使用することと；
前記第１キャッシュ内の未改変シーケンシャル・トラックをデモートすることを決定することと；
デモートされるべき前記未改変シーケンシャル・トラックを決定するために前記第２ＬＲＵリストを使用することと；
をさらに含む、請求項２０に記載の方法。
【請求項２６】
要求されたトラックのための読み出し要求を受け取ることと；
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュ内に存在するものを取り出すことと；
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュ内に見出されなくて前記第２キャッシュ内に存在するものを取り出すことと；
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュおよび第２キャッシュ内に見出されないものを前記ストレージから取り出すことと；
前記要求されたトラックのうちの前記第２キャッシュおよび前記ストレージから取り出されたものを前記第１キャッシュへプロモートすることと；
をさらに含む、請求項２０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージのための第１キャッシュおよび第２キャッシュにおけるトラックのキャッシュ管理のためのコンピュータ・プログラム製品（プログラム）、システム、および方法に関する。
【背景技術】
【０００２】
キャッシュ管理システムは、読み出し操作および書き込み操作の結果として最近アクセスされたストレージ・デバイス内のトラックを、その要求されたトラックを記憶しているストレージ・デバイスよりも高速なアクセスの、メモリ等のストレージ・デバイスにバッファリングする。より高速なアクセスのキャッシュ・メモリ内のトラックに対する爾後の読み出し要求は、要求されたトラックをより低速のアクセスのストレージから返すよりも速い速度で返され、従って読み出し待ち時間を短縮する。キャッシュ管理システムは、ストレージ・デバイスに向けられた改変済みトラックがキャッシュ・メモリに書き込まれたとき、改変済みトラックがハード・ディスク・ドライブ等のストレージ・デバイスへ完全に書き込まれる前に、書き込み要求に対するコンプリートを返すこともできる。ストレージ・デバイスへの書き込み待ち時間は、通例、キャッシュ・メモリへの書き込みのための待ち時間より著しく長い。従って、キャッシュを使用すれば書き込み待ち時間も短縮される。
【０００３】
キャッシュ管理システムは、キャッシュに格納されている各トラックのために１つのエントリを有するリンク・リストを維持することができ、それは、ストレージ・デバイスへ書き込む前にキャッシュにバッファリングされた書き込みデータまたは読み出しデータを含むことができる。一般的に使用される最長時間未使用（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ（ＬＲＵ））キャッシュ手法では、キャッシュ内のトラックがアクセスされると、すなわちキャッシュ“ヒット”ならば、アクセスされるトラックのためのＬＲＵリスト内のエントリは該リストの最短時間未使用（Ｍｏｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ（ＭＲＵ））エンドへ移される。要求されたトラックがキャッシュ内に存在しなければ、すなわちキャッシュ・ミスならば、そのエントリが該リストのＬＲＵエンドに存在するキャッシュ内のトラックが除去（あるいはストレージにデステージング）されることができ、ストレージからキャッシュへステージングされるトラック・データのためのエントリがＬＲＵリストのＭＲＵエンドに加えられる。このＬＲＵキャッシュ手法では、より頻繁にアクセスされるトラックはキャッシュに残留しやすく、あまり頻繁にはアクセスされないデータは、新たにアクセスされるトラックのためにキャッシュ内に空間を作るために該リストのＬＲＵエンドからより除去されやすいであろう。
【０００４】
ＬＲＵキャッシュ手法は、デステージング操作の数を最小にするためにすぐに再書き込みされる可能性の最も小さいトラックをデステージングするように時間的ローカリティを最適化しようとする、すなわち、デステージングされない書き込みがオーバーライトされるならば、そのオーバーライトされる書き込みのデステージングが回避され、それによりデータをキャッシュからディスクへ書き込む時間および労力を節約する。一方、空間的ローカリティを利用する仕方でデステージングを行いたいという希望もあり、そのことは、書き込まれるべき次の記憶場所に到達するためにストレージ・デバイス書き込みメカニズムおよび記憶媒体が動かされなければならない距離を最小にするために互いに最も近い記憶場所にデータが書き込まれるということを意味する。
【０００５】
時間的ローカリティおよび空間的ローカリティの両方を利用するための１つの手法はワイズ・オーダリング・フォー・ライツ（Ｗｉｓｅ  Ｏｒｄｅｒｉｎｇ  ｆｏｒ  Ｗｒｉｔｅｓ（ＷＯＷ））アルゴリズムである。ＷＯＷアルゴリズムは円形リンク・リストまたはクロックを使用し、該円形リンク・リストはキャッシュにバッファリングされている各書き込み要求について１つのエントリを有する。エントリは、該リンク・リストにおいて、空間的ローカリティの利益を利用するために関連する書き込み要求が向けられる記憶場所に応じて配列される。さらに、各エントリは、キャッシュ内の該記憶場所のための書き込みデータが最近更新されたか否かを示すビットを含む。エントリのための該ビットは、そのエントリのための書き込みデータが更新されるとセットされる。ポインタが、該円形リンク・リスト内の現在のエントリを指す。ＷＯＷアルゴリズムを使用するタスクは、ポインタによりアドレス指定されたエントリにアクセスする。キャッシュ内の該エントリのためのデータが最近更新されたことを該エントリのためのビットが示すならば、該ビットは、該書き込みデータが最近更新されていないことを示すようにセットされ、ポインタは、前に書き込まれた記憶場所の空間的近傍において次に最も近い記憶場所への書き込みデータを有するエントリが考慮されるように次のエントリを指すようにインクリメントされる。最後に書き込まれた記憶場所の空間的近傍において最も近くて、該エントリのための書き込みデータが最近更新されていないことをそのビットが示しているエントリが書き込みのために選択される。
【０００６】
このように、ＷＯＷアルゴリズムでは、最後にデステージングされた書き込み要求に空間的近傍において最も近い書き込まれるべき次のエントリが考慮されるべく選択されるので、空間的ローカリティが利用される。さらに、最近書き込まれたエントリは、ポインタがそのスキップされたエントリを考慮するべく回り戻ってくるまではスキップされるので、時間的ローカリティが利用される。
【０００７】
ディスク・ドライブは、書き込みトラックの線形位置および角度位置の両方を考慮するとともに、最小総サービス時間を決定するために現在の書き込みヘッド位置に関して両方を最適化するＷＯＷアルゴリズムおよび他のアルゴリズムを実行することができる。このプロセスは“シークおよび回転最適化に基づくコマンド再配列（ｃｏｍｍａｎｄ  ｒｅ−ｏｒｄｅｒｉｎｇ  ｂａｓｅｄ  ｏｎ  ｓｅｅｋ  ａｎｄ  ｒｏｔａｔｉｏｎａｌ  ｏｐｔｉｍｉｚａｔｉｏｎ）”と称される。ディスク・ドライブのロジック・ボードは、複数の書き込み要求を分析して、書き込まれるべきトラックの種々のシリンダおよび角度位置へシークするためにどれだけの時間がかかるか、およびヘッドの下で該データが回転するのを待つ間にどれだけの時間が経過するかの両方に基づいて、先にどれを行うかを決定する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
当該技術において、ストレージ・システムでキャッシュを使用する改善された手法に対するニーズが存在する。
【課題を解決するための手段】
【０００９】
ストレージのための第１キャッシュおよび第２キャッシュにおけるトラックのキャッシュ管理のためのコンピュータ・プログラム製品、システム、および方法が提供される。第１キャッシュは、入力／出力（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ（Ｉ／Ｏ））要求に従う該ストレージ内の改変済みトラックおよび未改変トラックを維持する。改変済みトラックおよび未改変トラックは第１キャッシュからデモートされる。第１キャッシュからデモートされる改変済みトラックおよび未改変トラックは第２キャッシュへプロモートされる。第２キャッシュからデモートされる未改変トラックは廃棄される。ストレージ・デバイス上で近接する物理的位置に存在する第２キャッシュ内の改変済みトラック同士はグループ化され、それらのグループ化された改変済みトラックは第２キャッシュからストレージ・デバイスへデステージングされる。
【図面の簡単な説明】
【００１０】
【図１】コンピューティング環境の実施態様を示す。
【図２】第１キャッシュ管理情報の実施態様を示す。
【図３】第２キャッシュ管理情報の実施態様を示す。
【図４】第１キャッシュ制御ブロックの実施態様を示す。
【図５】第２キャッシュ制御ブロックの実施態様を示す。
【図６】空間的インデックス・エントリの実施態様を示す。
【図７】第１キャッシュから未改変トラックをデモートする操作の実施態様を示す。
【図８】改変済みトラックを第１キャッシュからデステージングする操作の実施態様を示す。
【図９】第１キャッシュにトラックを加える操作の実施態様を示す。
【図１０】第２キャッシュへトラックをプロモートする操作の実施態様を示す。
【図１１】第２キャッシュ内でスペースを解放する操作の実施態様を示す。
【図１２】改変済みトラックを第２キャッシュからデステージングする操作の実施態様を示す。
【図１３】読み出し要求に返すためにトラックに対する要求を処理する操作の実施態様を示す。
【発明を実施するための形態】
【００１１】
図１は、コンピューティング環境の実施態様を示す。複数のホスト２ａ、２ｂ・・・２ｎは、ストレージ１０内のボリューム８（例えば、ロジカル・ユニット・ナンバ、ロジカル・デバイス、ロジカル・サブシステムなど）に存するデータにアクセスするためにネットワーク６を介してストレージ・コントローラ４に入力／出力（Ｉ／Ｏ）要求を提出することができる。ストレージ・コントローラ４は、単一のもしくは複数のコアを有する１つ以上のプロセッサを含むプロセッサ・コンプレックス１２と、第１キャッシュ１４と、キャッシュ１４内のトラックをバックアップする第１キャッシュ・バックアップ・デバイス１６と、第２キャッシュ１８とを含む。第１キャッシュ１４および第２キャッシュ１８は、ホスト２ａ、２ｂ・・・２ｎとストレージ１０との間で転送されるキャッシュ・データをキャッシュする。第１キャッシュ・バックアップ・デバイス１６は、第１キャッシュ１４内のトラックの不揮発性記憶を提供することができる。さらなる実施態様では、第１キャッシュ・バックアップ・デバイス１６は、第１キャッシュ１４のそれとは異なる電力境界上のクラスタまたはハードウェア内に置かれ得る。
【００１２】
ストレージ・コントローラ４は、ホスト２ａ、２ｂ・・・２ｎとストレージ１０との間で転送されるトラックの転送を管理するためのストレージ・マネージャ２２と、第１キャッシュ１４、第１キャッシュ・バックアップ・デバイス１６および第２キャッシュ１８内のホスト２ａ、２ｂ・・・２ｎとストレージ１０との間で転送されるデータを管理するキャッシュ・マネージャ２４とを含むメモリ２０を有する。トラックは、ボリューム、ロジカル・デバイスなどのような複数のトラックのより大きなグルーピングの一部であるトラック、ロジカル・ブロック・アドレス（Ｌｏｇｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ（ＬＢＡ））などのような、ストレージ１０において構成されているデータの任意の単位を含み得る。キャッシュ・マネージャ２４は、第１キャッシュ１４および第２キャッシュ１８内の読み出し（未改変）トラックおよび書き込み（改変済み）トラックを管理するために第１キャッシュ管理情報２６および第２キャッシュ管理情報２８を維持する。第１キャッシュ・バックアップ・デバイス・インデックス３０は、第１キャッシュ・バックアップ・デバイス１６内の位置に対するトラック識別子のインデックスを提供する。
【００１３】
ストレージ・マネージャ２２およびキャッシュ・マネージャ２４は、メモリ２０にロードされてプロセッサ・コンプレックス１２により実行されるプログラム・コードとして図１に示されている。代わりに、該機能の幾つかまたは全部は、特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔｓ（ＡＳＩＣ））などの、ストレージ・コントローラ４内のハードウェア・デバイスで実行され得る。
【００１４】
第２キャッシュ１８は、トラックを、トラックが受け取られた順に書き込まれるログ・ストラクチャード・アレイ（ｌｏｇ  ｓｔｒｕｃｔｕｒｅｄ  ａｒｒａｙ（ＬＳＡ））３２に格納することができ、従って第２キャッシュ１８に書き込まれたトラックの時間的配列を提供する。ＬＳＡでは、該ＬＳＡ内に既に存在するトラックの遅いほうのバージョンはＬＳＡ３２の末尾に書き込まれる。代わりの実施態様では、第２キャッシュ１８は、ＬＳＡ以外のフォーマットでデータを記憶することができる。
【００１５】
一実施態様では、第１キャッシュ１４はダイナミック・ランダム・アクセス・メモリ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＤＲＡＭ））などのランダム・アクセス・メモリ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ））を含むことができ、第２キャッシュ１８はソリッド・ステート・デバイスなどのフラッシュ・メモリを含むことができ、ストレージ１０はハード・ディスク・ドライブおよび磁気テープなどの１つ以上のシーケンシャル・アクセス・ストレージ・デバイスから構成される。ストレージ１０は、単一のシーケンシャル・アクセス・ストレージ・デバイスを含むことができ、あるいは、ジャスト・ア・バンチ・オブ・ディスクス（Ｊｕｓｔ  ａ  Ｂｕｎｃｈ  ｏｆ  Ｄｉｓｋｓ（ＪＢＯＤ））、ダイレクト・アクセス・ストレージ・デバイス（Ｄｉｒｅｃｔ  Ａｃｃｅｓｓ  Ｓｔｏｒａｇｅ  Ｄｅｖｉｃｅ（ＤＡＳＤ））、リダンダント・アレイ・オブ・インディペンデント・ディスクス（Ｒｅｄｕｎｄａｎｔ  Ａｒｒａｙ  ｏｆ  Ｉｎｄｅｐｅｎｄｅｎｔ  Ｄｉｓｋｓ（ＲＡＩＤ））アレイ、仮想化デバイスなどの複数のストレージ・デバイスのアレイを含むことができる。一実施態様では、第１キャッシュ１４は第２キャッシュ１８より高速のアクセスのデバイスであり、第２キャッシュ１８はストレージ１０より高速のアクセスのデバイスである。さらに、第１キャッシュ１４は第２キャッシュ１８より大きな単位記憶当たりコスト（ｃｏｓｔ  ｐｅｒ  ｕｎｉｔ  ｏｆ  ｓｔｏｒａｇｅ）を有することができ、第２キャッシュ１８はストレージ１０内のストレージ・デバイスより大きな単位記憶当たりコストを有することができる。
【００１６】
第１キャッシュ１４は、メモリ２０の一部であることができ、あるいはＤＲＡＭなどの別のメモリ・デバイスに実装されることができる。一実施態様では、第１キャッシュ・バックアップ・デバイス１６は、たとえばバッテリー・バックアップされるランダム・アクセス・メモリ（ＲＡＭ）、スタティックＲＡＭ（ｓｔａｔｉｃ  ＲＡＭ（ＳＲＡＭ））などの、不揮発性メモリのような不揮発性バックアップ・ストレージ（ｎｏｎ−ｖｏｌａｔｉｌｅ  ｂａｃｋｕｐ  ｓｔｏｒａｇｅ（ＮＶＳ））を含むことができる。
【００１７】
ネットワーク６は、ストレージ・エリア・ネットワーク（Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＳＡＮ））、ローカル・エリア・ネットワーク（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＬＡＮ））、ワイド・エリア・ネットワーク（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＷＡＮ））、インターネット、およびイントラネットなどを含むことができる。
【００１８】
図２は、制御ブロック・ディレクトリ５２内のブロックを制御するための第１キャッシュ１４内のトラックのインデックスを提供するトラック・インデックス５０と；第１キャッシュ１４内の未改変シーケンシャル・トラックの時間的配列を提供する未改変シーケンシャルＬＲＵリスト５４と；第１キャッシュ１４内の改変済みシーケンシャル・トラックおよび改変済みノンシーケンシャル・トラックの時間的配列を提供する改変済みＬＲＵリスト５６と；第１キャッシュ１４内の未改変ノンシーケンシャル・トラックの時間的配列を提供する未改変ノンシーケンシャルＬＲＵリスト５８とを含む第１キャッシュ管理情報２６の実施態様を示す。
【００１９】
或る実施態様では、第１キャッシュ・バックアップ・デバイス１６が満杯であると判定すると、新たな改変済みトラックのために第１キャッシュ・バックアップ・デバイス１６内に空間を作るために第１キャッシュ・バックアップ・デバイス１６内の改変済みトラックのコピーが廃棄され得るように第１キャッシュ１４から改変済みトラックをデステージングするために改変済みＬＲＵリスト５６が使用される。
【００２０】
図３は、制御ブロック・ディレクトリ７２内のブロックを制御するための第２キャッシュ１８内のトラックのインデックスを提供するトラック・インデックス７０と；第２キャッシュ１８内の未改変トラックの時間的配列を提供する未改変リスト７４と；改変済みトラックが格納されているストレージ１０内の物理的位置に基づいて第２キャッシュ１８内の改変済みトラックの空間的配列を提供する空間的インデックス７６とを含む第２キャッシュ管理情報２８の実施態様を示す。
【００２１】
すべてのＬＲＵリスト５４、５６、５８、および７４は、識別されたトラックが最後にアクセスされた時に応じて配列された第１キャッシュ１４および第２キャッシュ１８内のトラックのトラックＩＤを含むことができる。ＬＲＵリスト５４、５６、５８、および７４は、最も最近にアクセスされたトラックを示す最短時間未使用（ｍｏｓｔ  ｒｅｃｅｎｔｌｙ  ｕｓｅｄ（ＭＲＵ））エンドと、最も古くに使用またはアクセスされたトラックを示すＬＲＵエンドとを有する。キャッシュ１４および１８に加えられるトラックのトラックＩＤはＬＲＵリストのＭＲＵエンドに加えられ、キャッシュ１４および１８からデモートされるトラックはＬＲＵエンドからアクセスされる。トラック・インデックス５０および７０および空間的インデックス７６は、スキャッター・インデックス・テーブル（ｓｃａｔｔｅｒ  ｉｎｄｅｘ  ｔａｂｌｅ（ＳＩＴ））を含むことができる。キャッシュ１４および１８内のトラックの時間的配列および第２キャッシュ１８内のトラックの空間的配列を提供するために代わりのタイプのデータ構造が使用され得る。
【００２２】
ノンシーケンシャル・トラックはオンライン・ライン・トランザクション・プロセッシング（Ｏｎｌｉｎｅ  Ｌｉｎｅ  Ｔｒａｎｓａｃｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ（ＯＬＴＰ））トラックを含むことができ、該トラックは、しばしば、完全にはランダムでなくて参照の或る程度のローカリティを有する、すなわち繰り返しアクセスされる確率を有する、小ブロック書き込みを含む。
【００２３】
図４は、制御ブロック・ディレクトリ５２内の第１キャッシュ制御ブロック１００エントリの実施態様であって、制御ブロック識別子（ＩＤ）１０２と、第１キャッシュ１４内のトラックの物理的位置の第１キャッシュ位置１０４と、トラックが改変済みであるのか未改変であるのかを示す情報１０６と、トラックがシーケンシャル・アクセスであるのかノンシーケンシャル・アクセスであるのかを示す情報１０８とを含む。
【００２４】
図５は、第２キャッシュ制御ブロック・ディレクトリ７２内の第２キャッシュ制御ブロック１２０エントリの実施態様であって、制御ブロック識別子（ＩＤ）１２２と、トラックがＬＳＡ３２において位置するＬＳＡ位置１２４と、トラックが改変済みであるのか未改変であるのかを示す情報１２６とを含む。
【００２５】
図６は、第２キャッシュ１８内のトラックのトラック識別子１４２と、ストレージ１０においてトラックが格納されている、シリンダ、プラッタ、ブロック・アドレス、およびストレージ・デバイス識別子などの物理的位置１４４とを含む空間的インデックス・エントリ１４０を示す。
【００２６】
図７は、第１キャッシュ１４から未改変トラックをデモートするためにキャッシュ・マネージャ２４により実行される操作の実施態様を示す。デモート操作は、第１キャッシュ１４内のスペースを解放すると決定したときに開始され得る。第１キャッシュ１４内のスペースを解放するために第１キャッシュ１４からトラックを除去するか否かを決定する操作を（ブロック２００で）開始するとき、キャッシュ・マネージャ２４は（ブロック２０２で）種々のタイプの未改変トラックに対する予想されるヒットに基づいてノンシーケンシャルな未改変トラックをデモートするか、それともシーケンシャルな未改変トラックをデモートするかを決定する。（ブロック２０４で）その決定が未改変シーケンシャル・トラックをデモートする決定であれば、キャッシュ・マネージャ２４は（ブロック２０６で）、第２キャッシュ１８へプロモートされない、デモートされるべき未改変シーケンシャル・トラックを未改変シーケンシャルＬＲＵリスト５４のＬＲＵエンドから決定するために該未改変シーケンシャルＬＲＵリスト５４を使用する。（ブロック２０４で）未改変ノンシーケンシャル・トラックをデモートする決定が行われたならば、キャッシュ・マネージャは、デモートされるべき未改変ノンシーケンシャル・トラックを（ブロック２０８で）決定するために未改変ノンシーケンシャルＬＲＵリスト５８を使用する。該未改変ノンシーケンシャル・トラックは（ブロック２１０で）第２キャッシュ１８へプロモートされる。
【００２７】
図８は、改変済みトラックを第１キャッシュ１４からデステージングするためにキャッシュ・マネージャ２４により実行される操作の実施態様を示す。キャッシュ・マネージャ２４は、スケジュールされた操作の一部として定期的にトラックをデステージングすることができるとともに第１キャッシュ・バックアップ・デバイス１６においてスペースが必要ならばデステージングの速度を高めることができる。改変済みトラックをデステージングする操作を（ブロック２５０で）開始するとき、キャッシュ・マネージャ２４は、ＬＲＵリスト５６のＬＲＵエンドから、デステージングされるべき改変済みトラックを決定するために改変済みＬＲＵリスト５６を（ブロック２５２で）処理する。（ブロック２５４で）決定された改変済みトラックがシーケンシャルならば、キャッシュ・マネージャ２４は、第２キャッシュ１８をバイパスして、決定された改変済みシーケンシャル・トラックを（ブロック２５６で）ストレージ１０に書き込む。（ブロック２５４で）改変済みトラックがノンシーケンシャルならば、キャッシュ・マネージャ２４は決定された改変済みノンシーケンシャル・トラックを（ブロック２５８で）第２キャッシュ１８へプロモートするとともに決定された改変済みトラックのコピーを（ブロック２６０で）第１キャッシュ・バックアップ・デバイス１６から廃棄する。
【００２８】
図７および８の操作では、ノンシーケンシャル・トラックはデモートされるけれども第２キャッシュ１８へプロモートされない。シーケンシャルな改変済み（書き込み）は、第２キャッシュをバイパスして、ストレージ１０に直接書き込まれる。シーケンシャルな未改変トラック（読み出し）は廃棄されてどこへもコピーされず、第１キャッシュ１４からデモートされる未改変ノンシーケンシャル・トラックは第２キャッシュ１８へプロモートされる。
【００２９】
図９は、トラックを第１キャッシュ１４に加える、すなわちプロモートするためにキャッシュ・マネージャ２４により実行される操作の実施態様を示し、そのトラックは、ホスト２ａ、２ｂ・・・２ｎからの書き込みまたは改変済みトラック、読み出し要求に従い、結果として第１キャッシュ１４へ移動させられる第２キャッシュ１８内のノンシーケンシャル・トラック、または、キャッシュ１４内にも１８内にも見出されなくてストレージ１０から取り出される読み出し要求されたデータを含み得る。第１キャッシュ１４に加えられるべきトラックを（ブロック３００で）受け取ると、キャッシュ・マネージャ２４は、第１キャッシュ１４内の１０４位置と、該トラックが改変済み／未改変１０６であるかおよびシーケンシャル／ノンシーケンシャル１０８であるかとを示す、該加えられるべきトラックのための制御ブロック１００（図４）を（ブロック３０１で）作成する。この制御ブロック１００は、第１キャッシュ１４の制御ブロック・ディレクトリ５２に加えられる。キャッシュ・マネージャ２４は、加えられるべきトラックのトラックＩＤと、制御ブロック・ディレクトリ５２内の作成されたキャッシュ制御ブロック１００へのインデックスとを有するエントリを第１キャッシュ・トラック・インデックス５０に（ブロック３０２で）加える。加えられるべきトラックのトラック・タイプについてのエントリがＬＲＵリスト５４、５６または５８のＭＲＵエンドに（ブロック３０４で）加えられる。（ブロック３０６で）加えられるべきトラックが改変済みノンシーケンシャル・トラックであれば、その加えられるべきトラックは（ブロック３０８で）第１キャッシュ・バックアップ・デバイス１６にコピーもされ、その加えられたトラックのためのエントリが第１キャッシュ・バックアップ・デバイス・インデックス３０に加えられる。（ブロック３０６で）加えられるべきトラックが未改変シーケンシャルであれば、制御は終了する。
【００３０】
図１０は、第１キャッシュ１４からデモートされるノンシーケンシャル・トラックを第２キャッシュ１８へプロモートするためにキャッシュ・マネージャ２４により実行される操作の実施態様を示す。（ブロック３５０で）トラックを第２キャッシュ１８へプロモートする操作を開始するとき、キャッシュ・マネージャ２４は、プロモートされるトラックを第２キャッシュ１８内のＬＳＡ３２に（ブロック３５２で）加えるとともに、ＬＳＡ３２内のトラック位置１２４と該トラックが改変済み／未改変１２６であるかとを示す該加えられるべきトラックのための制御ブロック１２０（図５）を（ブロック３５４で）作成する。プロモートされるトラックのトラックＩＤと、第２キャッシュ１８のための制御ブロック・ディレクトリ７２内の作成されたキャッシュ制御ブロック１２０へのインデックスとを有するエントリが第２キャッシュ・トラック・インデックス７０に（ブロック３５６で）加えられる。（ブロック３５８の「いいえ」ブランチから）プロモートされるトラックが未改変データであれば、キャッシュ・マネージャ２４は、該トラックＩＤをＭＲＵエンドに加えることなどにより、プロモートされるトラックを（ブロック３６０で）未改変ＬＲＵリスト７４のＭＲＵエンドに示す。（ブロック３５８で）プロモートされるトラックが改変済みデータであるならば、キャッシュ・マネージャ２４は、その改変済みのプロモートされるトラックを書き込むべきストレージ１０上の物理的位置を（ブロック３６２で）決定するとともに、プロモートされるトラックのトラックＩＤ１４２と該プロモートされるトラックのストレージ１０上の決定された物理的位置１４４とを示すエントリを空間的インデックス７６に（ブロック３６４で）加える。
【００３１】
図１１は、第２キャッシュ１８に加えられるべき新しいトラック、すなわち第１キャッシュ１４からデモートされるトラック、のために第２キャッシュ１８内のスペースを解放するためにキャッシュ・マネージャ２４により実行される操作の実施態様を示す。この操作を（ブロック４００で）開始するとき、キャッシュ・マネージャ２４は未改変ＬＲＵリスト７４のＬＲＵエンドから第２キャッシュ１８内の未改変トラックを（ブロック４０２で）決定し、該決定された未改変トラックを（ブロック４０４で）無効にし、該無効にされた未改変トラックをストレージ１０へデステージングすることなく、さらに該無効にされた未改変トラックを未改変ＬＲＵリスト７４から除去する。
【００３２】
図１２は、第２キャッシュ１２内の改変済みトラックをストレージ１０へデステージングするためにキャッシュ・マネージャ２４により実行される操作の実施態様を示す。該デステージング操作を（ブロック４２０で）開始するとき、キャッシュ・マネージャ２４は、位置配列された空間的インデックス７６内の連続するエントリ１４０（図６）に存するトラックのグループなど、ストレージ・デバイス上で近接した物理的位置にあるグループ化されるべき第２キャッシュ１８内の改変済みトラックを空間的インデックス７６内でのそれらの順序に基づいて決定するために空間的インデックス７６を（ブロック４２２で）使用する。その決定されたグループ化された改変済みトラックは第２キャッシュ１８からストレージ・デバイス１０へ（ブロック４２４で）デステージングされる。
【００３３】
図１２の操作は、ストレージ１０書き込みトラックをストレージ１０書き込み表面上で物理的に最も近接している物理的位置に有し、従って第２キャッシュ１８内のトラックをストレージ１０に書き込むためのストレージ１０書き込みヘッドのシークおよび移動の量を最小にすることによって、シーケンシャル・アクセス・ストレージ・デバイスを含むストレージ１０への書き込み操作を最適化する。トラックは、ハード・ディスク・ドライブのようなシーケンシャル・アクセス・ストレージ１０へのシーケンシャルな書き込みのために最適化された順序ではなくてＬＲＵリスト５４、５６、５８におけるそれらの位置などの時間的ファクターに基づいて第１キャッシュ１６から第２キャッシュ１８へプロモートされた。従って、図１２の操作は、ストレージ１０における書き込みを最適化するために、時間的に配列された改変済みトラックをストレージ１０上でのそれらの空間的位置に基づいて最適化する。
【００３４】
図１３は、読み出し要求のために要求されたトラックをキャッシュ１４および１８およびストレージ１０から取り出すためにキャッシュ・マネージャ２４により実行される操作の実施態様を示す。該読み出し要求を処理するストレージ・マネージャ２２は、要求されたトラックのためにキャッシュ・マネージャ２４に要求を提示することができる。該トラックに対する該要求を（ブロック４５０で）受け取ると、キャッシュ・マネージャ２４は、要求されたトラックのすべてが第１キャッシュ１４内に存在するか否かを判定するために第１キャッシュ・トラック・インデックス５０を（ブロック４５４で）使用する。（ブロック４５４で）すべての要求されたトラックが第１キャッシュ１４内に存在するわけでは無ければ、キャッシュ・マネージャ２４は、要求されたトラックのうちの第１キャッシュ１４内には存在しなくて第２キャッシュ１８内に存在するトラックを判定するために第２キャッシュ・トラック・インデックス７０を（ブロック４５６で）使用する。（ブロック４５８で）いずれかの要求されたトラックが第１キャッシュ１４および第２キャッシュ１８内に見出されなければ、キャッシュ・マネージャ２４は、要求されたトラックのうちの第１キャッシュ１４および第２キャッシュ１８内に存在せずにストレージ１０内に存在するトラックを第２キャッシュ・トラック・インデックス７０から（ブロック４６０で）判定する。その後、キャッシュ・マネージャ２４は、第２キャッシュ１８およびストレージ１０内の該判定されたトラックを第１キャッシュ１４へ（ブロック４６２で）プロモートする。キャッシュ・マネージャ２４は、読み出し要求に返すために、要求されたトラックを第１キャッシュ１４から取り出すために第１キャッシュ・トラック・インデックス５０を（ブロック４６４で）使用する。取り出されたトラックのためのエントリは、取り出されたトラックのためのエントリを含むＬＲＵリスト５４、５６、５８のＭＲＵエンドへ（ブロック４６６で）移される。図１３の操作では、キャッシュ１４および１８は要求されたトラックの最も最近の改変済みバージョンを有するので、キャッシュ・マネージャ２４は要求されたトラックを最高レベルのキャッシュ１４から取り出し、その後に、ストレージ１０へ移行する前に先ず第２キャッシュ１８から取り出す。その最も最近のバージョンは、先ず第１キャッシュ１４内に見出され、もし第１キャッシュ１４内に見出されなければ第２キャッシュ１８内に見出され、その後、もしどちらのキャッシュ１４、１８にも見出されなければストレージ１０内に見出される。
【００３５】
図１３の操作では、キャッシュ１４および１８は要求されたトラックの最も最近の改変済みバージョンを有するので、キャッシュ・マネージャ２４は要求されたトラックを最高レベルのキャッシュ１４から取り出し、その後に、ストレージ１０へ移行する前に先ず第２キャッシュ１８から取り出す。その最も最近のバージョンは、先ず第１キャッシュ１４内に見出され、もし第１キャッシュ１４内に見出されなければ第２キャッシュ１８内に見出され、その後、もしどちらのキャッシュ１４、１８にも見出されなければストレージ１０内に見出される。
【００３６】
記載された実施態様は、最高速アクセスの第１キャッシュ１４が最も高価なスペース、バイトあたりコスト、を有し、第１キャッシュよりは安価であるがストレージよりは高速である第２キャッシュがシステム内でキャッシュされるデータの量を増やすために使用され得るときにキャッシュ・スペースを増やすために主要なあるいは第１レベルのキャッシュとストレージとの間の第２レベルのキャッシュの使用を可能にするための技術を提供する。より高速なアクセスのキャッシュ記憶スペースを増やせば、要求されたデータがキャッシュ内にあって、より低速のアクセスのより安価なストレージから取り出す必要なくキャッシュから返され得るときに、キャッシュされたデータへのアクセスが改善される。さらに、記載された実施態様では、ストレージへのトラックの書き込みを最適化するためにデステージングされるトラックがストレージ内の近接するあるいは連続する物理的位置にトラックのグループをなして書き込まれるように、トラックは、第１キャッシュにおける時間的配列に基づいて第２キャッシュに加えられ、その後に、シーケンシャル・アクセス・ストレージにおける空間的物理的位置に基づいて第２キャッシュにおいてソートされる。
【００３７】
記載された操作は、ソフトウェア、ファームウェア、ハードウェア、あるいはそれらの任意の組み合わせを作るための標準的なプログラミングもしくはエンジニアリング技術またはその両方を用いて方法、装置またはコンピュータ・プログラム製品として実装され得る。従って、該実施態様の側面は、完全にハードウェアの実施態様、完全にソフトウェアの実施態様（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）あるいは本明細書において全く一般的に“回路”、“モジュール”もしくは“システム”と称され得るソフトウェア側面およびハードウェア側面を組み合わせた実施態様の形をとることができる。さらに、該実施態様の側面は、コンピュータ可読プログラム・コードがその上に具体化されている１つ以上のコンピュータ可読媒体において具体化されるコンピュータ・プログラム製品の形をとることができる。
【００３８】
１つ以上のコンピュータ可読媒体の任意の組み合わせが利用され得る。コンピュータ可読媒体は、コンピュータ可読信号媒体またはコンピュータ可読記憶媒体であり得る。コンピュータ可読記憶媒体は、たとえば、それに限定はされないが、電子、磁気、光、電磁、赤外線、または半導体のシステム、装置、もしくはデバイス、または前記のものの任意の適切な組み合わせであり得る。コンピュータ可読記憶媒体のより具体的な例（非網羅的なリスト）は、次のもの：１つ以上のワイヤを有する電気的接続、ポータブルなコンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能でプログラマブルな読み出し専用メモリ（ＥＰＲＯＭ（ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）またはフラッシュ・メモリ）、光ファイバ、ポータブルなコンパクト・ディスク読み出し専用メモリ（ｃｏｍｐａｃｔ  ｄｉｓｃ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ（ＣＤ−ＲＯＭ））、光記憶装置、磁気記憶装置、あるいは前記のものの任意の適切な組み合わせ、を含む。この文書の文脈においては、コンピュータ可読記憶媒体は、命令実行システム、装置、またはデバイスによりまたはこれらと関連して使用されるプログラムを包含または記憶できる任意の有形媒体であり得る。
【００３９】
コンピュータ可読信号媒体は、コンピュータ可読プログラム・コードがたとえばベースバンドにあるいは搬送波の一部としてその中に具体化されている伝播されるデータ信号を含み得る。そのような伝播される信号は、電磁、光、あるいはそれらの任意の適切な組み合わせを含むがこれらに限定はされない種々の形のうちのいずれをもとることができる。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体ではなくて、命令実行システム、装置、またはデバイスによりまたはこれらと関連して用いられるプログラムを伝達、伝播、またはトランスポートすることのできる任意のコンピュータ可読媒体であり得る。
【００４０】
コンピュータ可読媒体上に具体化されたプログラム・コードは、無線、ワイヤライン、光ファイバ・ケーブル、ＲＦなど、あるいは前記のものの任意の適切な組み合わせを含むがこれらに限定はされない任意の適切な媒体を用いて送信され得る。
【００４１】
本発明の側面のための操作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋などのようなオブジェクト指向プログラミング言語ならびに“Ｃ”プログラミング言語もしくは類似のプログラミング言語のような在来の手続き型プログラミング言語を含む１つ以上のプログラミング言語の任意の組み合わせで書かれ得る。該プログラム・コードは、完全にユーザのコンピュータ上で、部分的にユーザのコンピュータ上でスタンドアロン・ソフトウェア・パッケージとして、部分的にユーザのコンピュータ上でかつ部分的にリモート・コンピュータ上で、あるいは完全にリモート・コンピュータまたはサーバ上で、実行することができる。後者のシナリオにおいては、リモート・コンピュータはローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを通してユーザのコンピュータに接続されることができ、あるいは接続は（たとえば、インターネット・サービス・プロバイダを用いてインターネットを通して）外部コンピュータに対してなされることができる。
【００４２】
本発明の側面は、本発明の実施態様に従う方法、装置（システム）およびコンピュータ・プログラム製品のフローチャート図もしくはブロック図またはその両方と関連して上で記述されている。該フローチャート図もしくはブロック図またはその両方の各ブロック、ならびに該フローチャート図もしくはブロック図またはその両方のブロックの組み合わせがコンピュータ・プログラム命令によって実現され得るということが理解されるであろう。これらのコンピュータ・プログラム命令は、汎用コンピュータ、特殊目的コンピュータ、またはマシンを作るための他のプログラマブルなデータ処理装置のプロセッサに、該コンピュータもしくは他のプログラマブルなデータ処理装置の該プロセッサを介して実行する該命令が該フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて明示される機能／行為を実行するための手段を生すように、提供されることができる。
【００４３】
これらのコンピュータ・プログラム命令は、コンピュータ可読媒体に格納された命令が該フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて明示される機能／行為を実行する命令を含む製造物品を作るように特定の仕方で機能するようにコンピュータ、他のプログラマブルなデータ処理装置、または他のデバイスに命令することのできるコンピュータ可読媒体に格納されることもできる。
【００４４】
該コンピュータ・プログラム命令は、コンピュータまたは他のプログラマブルな装置上で実行する命令がフローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて明示される機能／行為を実行するためのプロセスを提供するようにコンピュータ実行されるプロセスを作るために一連の操作ステップを該コンピュータ、他のプログラマブルな装置または他のデバイス上で実行させるためにコンピュータ、他のプログラマブルなデータ処理装置、または他のデバイスにロードされることもできる。
【００４５】
“ａｎ  ｅｍｂｏｄｉｍｅｎｔ”、“ｅｍｂｏｄｉｍｅｎｔ”、“ｅｍｂｏｄｉｍｅｎｔｓ”、“ｔｈｅ  ｅｍｂｏｄｉｍｅｎｔ”、“ｔｈｅ  ｅｍｂｏｄｉｍｅｎｔｓ”、“ｏｎｅ  ｏｒ  ｍｏｒｅ  ｅｍｂｏｄｉｍｅｎｔｓ”、“ｓｏｍｅ  ｅｍｂｏｄｉｍｅｎｔｓ”、および“ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ”という用語は、明示的に別様に特定されていなければ、“ｏｎｅ  ｏｒ  ｍｏｒｅ  （ｂｕｔ  ｎｏｔ  ａｌｌ）  ｅｍｂｏｄｉｍｅｎｔｓ  ｏｆ  ｔｈｅ  ｐｒｅｓｅｎｔ  ｉｎｖｅｎｔｉｏｎ（ｓ）（１つまたは複数の本発明の１つ以上の（けれども全部ではない）実施態様）”を意味する。
【００４６】
“ｉｎｃｌｕｄｉｎｇ”、“ｃｏｍｐｒｉｓｉｎｇ”、“ｈａｖｉｎｇ”およびこれらのバリエーションは、明示的に別様に特定されていなければ、“ｉｎｃｌｕｄｉｎｇ  ｂｕｔ  ｎｏｔ  ｌｉｍｉｔｅｄ  ｔｏ（含むけれども限定はされない）”を意味する。
【００４７】
列挙されたアイテムのリスティングは、明示的に別様に特定されていなければ、該アイテムのうちのいずれかまたは全部が相互に排他的であることを意味しない。
【００４８】
“ａ”、“ａｎ”および“ｔｈｅ”は、明示的に別様に特定されていなければ、“ｏｎｅ  ｏｒ  ｍｏｒｅ（１つ以上）”を意味する。
【００４９】
互いに通信するデバイス同士は、明示的に別様に特定されていなければ、互いに連続的に通信していなくてもよい。さらに、互いに通信するデバイス同士は直接にあるいは１つ以上の媒介を通して間接的に通信することができる。
【００５０】
互いに通信する数個のコンポーネントを有する実施態様についての記述は、そのようなコンポーネントがすべて必要であることを意味しない。反対に、本発明の広範な可能な実施態様を示すために多様な任意選択のコンポーネントが記載されている。
【００５１】
さらに、プロセス・ステップ、方法ステップ、アルゴリズムなどが順次に記載されているかも知れないけれども、そのようなプロセス、方法およびアルゴリズムは代わりの順序で働くように構成されることができる。換言すれば、記載され得るステップのシーケンスまたは順序は、該ステップがその順序で実行されなければならないことを必ずしも示さない。本明細書に記載されているプロセスのステップは任意の実際的な順序で実行されることができる。さらに、幾つかのステップは同時に実行され得る。
【００５２】
本明細書において単一のデバイスまたは物品が記載されるとき、単一のデバイス／物品の代わりに２つ以上のデバイス／物品（それらが協働してもしなくても）が使用され得ることは明白であろう。同様に、本明細書において２つ以上のデバイスまたは物品が記載される場合（それらが協働してもしなくても）、その２つ以上のデバイスまたは物品の代わりに単一のデバイス／物品が使用され得ることあるいはその示された数のデバイスまたはプログラムの代わりに異なる数のデバイス／物品が使用され得ることは明白であろう。デバイスの機能もしくはフィーチャまたはその両方は、そのような機能／フィーチャを持っていると明示的に記載されてはいない１つ以上の他のデバイスによって代わりに具体化されることができる。従って、本発明の他の実施態様は、そのデバイス自体を含んでいなくてもよい。
【００５３】
図７〜図１３に示されている操作は、一定の順序で起こる一定のイベントを示す。代わりの実施態様では一定の操作は異なる順序で実行され、改変されあるいは除去されることができる。さらに、ステップが上記のロジックに加えられ、なお記載された実施態様に従うことができる。さらに、本明細書に記載された操作は順次に起こることができ、あるいは一定の操作は並行して処理されることができる。さらに、操作は単一の処理装置によってまたは分散された処理装置によって行われることができる。
【図１】
2014519650.tif 000003
【図２】
2014519650.tif 000004
【図３】
2014519650.tif 000005
【図４】
2014519650.tif 000006
【図５】
2014519650.tif 000007
【図６】
2014519650.tif 000008
【図７】
2014519650.tif 000009
【図８】
2014519650.tif 000010
【図９】
2014519650.tif 000011
【図１０】
2014519650.tif 000012
【図１１】
2014519650.tif 000013
【図１２】
2014519650.tif 000014
【図１３】
2014519650.tif 000015
【手続補正書】
【提出日】平成25年12月20日(2013.12.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１キャッシュ、第２キャッシュ、およびストレージ・デバイスを含むキャッシュ・システムにおいてデータを管理するためのプログラムであって、
入力／出力（Ｉ／Ｏ）要求に従う前記ストレージ内の改変済みトラックおよび未改変トラックを前記第１キャッシュにおいて維持することと、
改変済みトラックおよび未改変トラックを前記第１キャッシュからデモートすることと、
前記第１キャッシュからデモートされた前記改変済みトラックおよび前記未改変トラックを前記第２キャッシュへプロモートすることと、
前記第２キャッシュからデモートされた未改変トラックを廃棄することと、
前記ストレージ・デバイス上で近接する物理的位置に存在する前記第２キャッシュ内の改変済みトラックをグループ化することと、
前記グループ化された改変済みトラックを前記第２キャッシュから前記ストレージ・デバイスへデステージングすることと、
をコンピュータに実行させるコンピュータ・プログラム。
【請求項２】
前記第１キャッシュは前記第２キャッシュより高速のアクセスのデバイスであり、前記第２キャッシュは前記ストレージより高速のアクセスのデバイスである、請求項１に記載のプログラム。
【請求項３】
前記第１キャッシュはランダム・アクセス・メモリ（ＲＡＭ）を含み、前記第２キャッシュはフラッシュ・デバイスを含み、前記ストレージ・デバイスはシーケンシャル書き込みデバイスを含む、請求項１に記載のプログラム。
【請求項４】
前記操作は：
前記第２キャッシュ内の前記改変済みトラックを前記ストレージにおけるそれらの物理的位置に基づく配列で示す空間的インデックスを維持することをさらに含み、前記空間的インデックスは、前記ストレージ・デバイス上で近接する物理的位置に存在するグループ化されるべき前記改変済みトラックを前記空間的インデックスにおけるそれらの順序に基づいて決定するために使用される、請求項１に記載のプログラム。
【請求項５】
前記操作は：
デモートされるべき前記第１キャッシュ内の改変済みトラックがシーケンシャルなトラックであるか否か判定することと、
シーケンシャルであると判定されたデモートされるべき前記改変済みトラックを、前記第２キャッシュをバイパスして前記ストレージに書き込むことと、
ノンシーケンシャルであると判定されたデモートされるべき前記改変済みトラックを前記第２キャッシュへプロモートすることと、
をさらに含む、請求項１に記載のプログラム。
【請求項６】
前記第２キャッシュへプロモートされる前記第１キャッシュからデモートされる前記改変済みトラックおよび未改変トラックはオンライン・ライン・トランザクション・プロセッシング（ＯＬＴＰ）トラックを含む、請求項１に記載のプログラム。
【請求項７】
前記操作は：
シーケンシャルな未改変トラックであるデモートされるべき前記未改変トラックを、前記デモートされるシーケンシャルな未改変トラックを前記第２キャッシュにも前記ストレージにも書き込まずに廃棄することをさらに含み、前記第１キャッシュからデモートされる未改変ノンシーケンシャル・トラックは前記第２キャッシュへプロモートされる、請求項１に記載のプログラム。
【請求項８】
前記操作は：
前記第１キャッシュ内の未改変ノンシーケンシャル・トラックを示す第１ＬＲＵリストを維持することと、
前記第１キャッシュ内の未改変シーケンシャル・トラックを示す第２ＬＲＵリストを維持することと、
前記第１キャッシュ内の未改変ノンシーケンシャル・トラックをデモートすることを決定することと、
デモートされるべき前記未改変ノンシーケンシャル・トラックを決定するために前記第１ＬＲＵリストを使用することと、
前記第１キャッシュ内の未改変シーケンシャル・トラックをデモートすることを決定することと、
デモートされるべき前記未改変シーケンシャル・トラックを決定するために前記第２ＬＲＵリストを使用することと、
をさらに含む、請求項１に記載のプログラム。
【請求項９】
前記操作は：
前記第２キャッシュ内の未改変トラックの最長時間未使用（ＬＲＵ）リストを維持することと、
スペースを解放するために前記第２キャッシュからトラックがデモートされる必要があると判定することと、
前記第２キャッシュ内の未改変トラックの前記ＬＲＵリストから未改変トラックを決定することと、
前記第２キャッシュからの前記決定された未改変トラックを無効にすることと、
をさらに含む、請求項１に記載のプログラム。
【請求項１０】
前記操作は：
前記第１キャッシュからデモートされた改変済みトラックおよび未改変トラックを前記第２キャッシュにおいてログ・ストラクチャード・アレイ（ＬＳＡ）に格納することと、
前記第２キャッシュ内のトラックと、各トラックのために前記ＬＳＡにおける前記トラックの位置を示す前記トラックのための制御ブロックを指すポインタとを示す前記第２キャッシュのためのＬＳＡインデックスを維持することと、
をさらに含む、請求項１に記載のプログラム。
【請求項１１】
前記操作は：
前記第１キャッシュに加えられた改変済みトラックをキャッシュ・バックアップ・デバイスに書き込むことと、
前記第１キャッシュ内の改変済みトラックを示す第１キャッシュ改変済みＬＲＵリストを維持することと、
前記キャッシュ・バックアップ・デバイスからデータをデステージングすると決定することと、
前記第１キャッシュ改変済みＬＲＵリストが満杯であることに応答して前記第１キャッシュからデステージングされるべき改変済みトラックを決定するために前記第１キャッシュ改変済みＬＲＵリストを使用することと、
デモートされるべき前記決定された改変済みトラックのコピーであるトラックを前記キャッシュ・バックアップ・デバイスから廃棄することと、
をさらに含む、請求項１に記載のプログラム。
【請求項１２】
前記操作は：
要求されたトラックのための読み出し要求を受け取ることと、
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュ内に存在するものを取り出すことと、
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュ内に見出されなくて前記第２キャッシュ内に存在するものを取り出すことと、
前記読み出し要求に返すために前記要求されたトラックのうちの前記第１キャッシュおよび第２キャッシュ内に見出されないものを前記ストレージから取り出すことと、
前記要求されたトラックのうちの前記第２キャッシュおよび前記ストレージから取り出されたものを前記第１キャッシュへプロモートすることと、
をさらに含む、請求項１に記載のプログラム。
【請求項１３】
ストレージ・デバイスと通信するシステムであって：
第１キャッシュと、
第２キャッシュと、
プロセッサと、
操作を行うために前記プロセッサによって実行されるコードを有するコンピュータ可読記憶媒体とを含み、前記操作は：
入力／出力（Ｉ／Ｏ）要求に従う前記ストレージ内の改変済みトラックおよび未改変トラックを前記第１キャッシュにおいて維持することと、
改変済みトラックおよび未改変トラックを前記第１キャッシュからデモートすることと、
前記第１キャッシュからデモートされた前記改変済みトラックおよび前記未改変トラックを前記第２キャッシュへプロモートすることと、
前記第２キャッシュからデモートされた未改変トラックを廃棄することと、
前記ストレージ・デバイス上で近接する物理的位置に存在する前記第２キャッシュ内の改変済みトラックをグループ化することと、
前記グループ化された改変済みトラックを前記第２キャッシュから前記ストレージ・デバイスへデステージングすることと、
を含む、システム。
【請求項１４】
前記第１キャッシュはランダム・アクセス・メモリ（ＲＡＭ）を含み、前記第２キャッシュはフラッシュ・デバイスを含み、前記ストレージ・デバイスはシーケンシャル書き込みデバイスを含む、請求項１３に記載のシステム。
【請求項１５】
前記操作は、前記第２キャッシュ内の前記改変済みトラックを前記ストレージにおけるそれらの物理的位置に基づく配列で示す空間的インデックスを維持することをさらに含み、前記空間的インデックスは、前記ストレージ・デバイス上で近接する物理的位置に存在するグループ化されるべき前記改変済みトラックを前記空間的インデックスにおけるそれらの順序に基づいて決定するために使用される、請求項１３に記載のシステム。
【請求項１６】
入力／出力（Ｉ／Ｏ）要求に従うストレージ内の改変済みトラックおよび未改変トラックを第１キャッシュにおいて維持することと、
改変済みトラックおよび未改変トラックを前記第１キャッシュからデモートすることと、
前記第１キャッシュからデモートされた前記改変済みトラックおよび前記未改変トラックを第２キャッシュへプロモートすることと、
前記第２キャッシュからデモートされた未改変トラックを廃棄することと、
前記ストレージ・デバイス上で近接する物理的位置に存在する前記第２キャッシュ内の改変済みトラックをグループ化することと、
前記グループ化された改変済みトラックを前記第２キャッシュから前記ストレージ・デバイスへデステージングすることと、
を含む、方法。
【国際調査報告】
2014519650.tif 000016
2014519650.tif 000017
2014519650.tif 000018