(57)【要約】【課題】キャッシュ管理のための方法を提供。【解決手段】キャッシュ中の第１のタイプのトラックのリストが生成される。キャッシュ中の第２のタイプのトラックのリストが生成され、Ｉ／Ｏオペレーションは、第２のタイプのトラックに対してよりも第１のタイプのトラックに対して相対的により速く完了される。ある１つのトラックを第１のタイプのトラックのリストから、または第２のタイプのトラックのリストからデモートすべきかどうかについて判定が行われる。【選択図】図１
2020531959.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュ管理の方法であって、
キャッシュ中の第１のタイプのトラックのリストを生成するステップと、
前記キャッシュ中に第２のタイプのトラックのリストを生成するステップであって、Ｉ／Ｏオペレーションは、前記第２のタイプのトラックに対してよりも前記第１のタイプのトラックに対して相対的により速く完了される、前記生成するステップと、
ある１つのトラックを前記第１のタイプのトラックの前記リストから、または前記第２のタイプのトラックの前記リストからデモートすべきかどうかを判定するステップと
を備える、方法。
【請求項２】
前記第１のタイプのトラックは、ｓｙｎｃｉｏトラックであり、ｓｙｎｃｉｏトラックに対してＩ／Ｏオペレーションを行うために、アプリケーション・スレッドがスピン・ループ中に保持されて、前記Ｉ／Ｏオペレーションが完了するのを待機する、請求項１に記載の方法。
【請求項３】
前記第２のタイプのトラックは、ｎｏｎ−ｓｙｎｃｉｏトラックであり、ｎｏｎ−ｓｙｎｃｉｏトラックに対して前記Ｉ／Ｏオペレーションを行うために、前記アプリケーション・スレッドを前記スピン・ループ中に保持するステップが回避され、前記トラック上で行われる最後のＩ／Ｏオペレーションがｓｙｎｃｉｏオペレーションを備える第１のタイプのＩ／Ｏオペレーションまたはｎｏｎ−ｓｙｎｃｉｏオペレーションを備える第２のタイプのＩ／Ｏオペレーションであるかどうかに基づいて、ある１つのトラックが前記第１のタイプのトラックの前記リストへ、または前記第２のタイプのトラックの前記リストへ追加される、請求項２に記載の方法。
【請求項４】
前記第１のタイプのトラックの前記リスト中のトラックは、前記第１のタイプのトラックの前記リスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられ、前記第２のタイプのトラックの前記リスト中のトラックは、前記第２のタイプのトラックの前記リスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられる、請求項３に記載の方法。
【請求項５】
前記方法は、
前記第２のタイプのトラックの前記リスト中のトラックについてのリード・ヒット率が前記第１のタイプのトラックにおけるトラックについてのリード・ヒット率の所定の係数より小さいと判定するステップに応答して、ある１つのトラックを前記第２のタイプのトラックの前記リストからデモートするステップ
をさらに備える、請求項４に記載の方法。
【請求項６】
前記第１のタイプのトラックの前記リスト中のトラックについての前記リード・ヒット率および前記第２のタイプのトラックの前記リスト中のトラックについての前記リード・ヒット率は、前記第１のタイプのトラックおよび前記第２のタイプのトラックの前記リストの所定の底の部分に対するリード・ヒットに基づいて計算される、請求項５に記載の方法。
【請求項７】
前記方法は、
入力／出力（Ｉ／Ｏ）オペレーションの速度を増加させるために前記所定の係数を調整するステップ
をさらに備える、請求項５に記載の方法。
【請求項８】
キャッシュ管理のためのシステムであって、
メモリ、および
前記メモリに結合されたプロセッサを備え、前記プロセッサは、オペレーションを行い、前記プロセッサによって行われる前記オペレーションは、
キャッシュ中の第１のタイプのトラックのリストを生成するステップと、
前記キャッシュ中に第２のタイプのトラックのリストを生成するステップであって、Ｉ／Ｏオペレーションは、前記第２のタイプのトラックに対してよりも前記第１のタイプのトラックに対して相対的により速く完了される、前記生成するステップと、
ある１つのトラックを前記第１のタイプのトラックの前記リストから、または前記第２のタイプのトラックの前記リストからデモートすべきかどうかを判定するステップと
を備える、方法。
【請求項９】
前記第１のタイプのトラックは、ｓｙｎｃｉｏトラックであり、ｓｙｎｃｉｏトラックに対してＩ／Ｏオペレーションを行うために、アプリケーション・スレッドがスピン・ループ中に保持されて、前記Ｉ／Ｏオペレーションが完了するのを待機する、請求項８に記載のシステム。
【請求項１０】
前記第２のタイプのトラックは、ｎｏｎ−ｓｙｎｃｉｏトラックであり、ｎｏｎ−ｓｙｎｃｉｏトラックに対して前記Ｉ／Ｏオペレーションを行うために、前記アプリケーション・スレッドを前記スピン・ループ中に保持するステップが回避され、前記トラック上で行われる最後のＩ／Ｏオペレーションがｓｙｎｃｉｏオペレーションを備える第１のタイプのＩ／Ｏオペレーションまたはｎｏｎ−ｓｙｎｃｉｏオペレーションを備える第２のタイプのＩ／Ｏオペレーションであるかどうかに基づいて、ある１つのトラックが前記第１のタイプのトラックの前記リストへ、または前記第２のタイプのトラックの前記リストへ追加される、請求項９に記載のシステム。
【請求項１１】
前記第１のタイプのトラックの前記リスト中のトラックは、前記第１のタイプのトラックの前記リスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられ、前記第２のタイプのトラックの前記リスト中のトラックは、前記第２のタイプのトラックの前記リスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられる、請求項１０に記載のシステム。
【請求項１２】
前記オペレーションは、
前記第２のタイプのトラックの前記リスト中のトラックについてのリード・ヒット率が前記第１のタイプのトラックにおけるトラックについてのリード・ヒット率の所定の係数より小さいと判定するステップに応答して、ある１つのトラックを前記第２のタイプのトラックの前記リストからデモートするステップ
をさらに備える、請求項１１に記載のシステム。
【請求項１３】
前記第１のタイプのトラックの前記リスト中のトラックについての前記リード・ヒット率および前記第２のタイプのトラックの前記リスト中のトラックについての前記リード・ヒット率は、前記第１のタイプのトラックおよび前記第２のタイプのトラックの前記リストの所定の底の部分に対するリード・ヒットに基づいて計算される、請求項１２に記載のシステム。
【請求項１４】
前記オペレーションは、
入力／出力（Ｉ／Ｏ）オペレーションの速度を増加させるために前記所定の係数を調整するステップ
をさらに備える請求項１２に記載のシステム。
【請求項１５】
キャッシュ管理のためのコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品は、それをもって具現化されたコンピュータ可読プログラム・コードを有するコンピュータ可読ストレージ媒体を備え、前記コンピュータ可読プログラム・コードは、オペレーションを行うように構成され、前記オペレーションは、
キャッシュ中の第１のタイプのトラックのリストを生成するステップと、
前記キャッシュ中に第２のタイプのトラックのリストを生成するステップであって、Ｉ／Ｏオペレーションは、前記第２のタイプのトラックに対してよりも前記第１のタイプのトラックに対して相対的により速く完了される、前記生成するステップと、
ある１つのトラックを前記第１のタイプのトラックの前記リストから、または前記第２のタイプのトラックの前記リストからデモートすべきかどうかを判定するステップと
を備える、コンピュータ・プログラム製品。
【請求項１６】
前記第１のタイプのトラックは、ｓｙｎｃｉｏトラックであり、ｓｙｎｃｉｏトラックに対してＩ／Ｏオペレーションを行うために、アプリケーション・スレッドがスピン・ループ中に保持されて、前記Ｉ／Ｏオペレーションが完了するのを待機する、請求項１５に記載のコンピュータ・プログラム製品。
【請求項１７】
前記第２のタイプのトラックは、ｎｏｎ−ｓｙｎｃｉｏトラックであり、ｎｏｎ−ｓｙｎｃｉｏトラックに対して前記Ｉ／Ｏオペレーションを行うために、前記アプリケーション・スレッドを前記スピン・ループ中に保持するステップが回避され、前記トラック上で行われる最後のＩ／Ｏオペレーションがｓｙｎｃｉｏオペレーションを備える第１のタイプのＩ／Ｏオペレーションまたはｎｏｎ−ｓｙｎｃｉｏオペレーションを備える第２のタイプのＩ／Ｏオペレーションであるかどうかに基づいて、ある１つのトラックが前記第１のタイプのトラックの前記リストへ、または前記第２のタイプのトラックの前記リストへ追加される、請求項１６に記載のコンピュータ・プログラム製品。
【請求項１８】
前記第１のタイプのトラックの前記リスト中のトラックは、前記第１のタイプのトラックの前記リスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられ、前記第２のタイプのトラックの前記リスト中のトラックは、前記第２のタイプのトラックの前記リスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられる、請求項１７に記載のコンピュータ・プログラム製品。
【請求項１９】
前記オペレーションは、
前記第２のタイプのトラックの前記リスト中のトラックについてのリード・ヒット率が前記第１のタイプのトラックにおけるトラックについてのリード・ヒット率の所定の係数より小さいと判定するステップに応答して、ある１つのトラックを前記第２のタイプのトラックの前記リストからデモートするステップ
をさらに備える、請求項１８に記載のコンピュータ・プログラム製品。
【請求項２０】
前記第１のタイプのトラックの前記リスト中のトラックについての前記リード・ヒット率および前記第２のタイプのトラックの前記リスト中のトラックについての前記リード・ヒット率は、前記第１のタイプのトラックおよび前記第２のタイプのトラックの前記リストの所定の底の部分に対するリード・ヒットに基づいて計算される、請求項１９に記載のコンピュータ・プログラム製品。
【請求項２１】
前記オペレーションは、
入力／出力（Ｉ／Ｏ）オペレーションの速度を増加させるために前記所定の係数を調整するステップ
をさらに備える請求項１９に記載のコンピュータ・プログラム製品。
【請求項２２】
キャッシュ管理のためのストレージ・コントローラであって、
キャッシュ、および
前記ストレージ・コントローラ中に維持されたキャッシュ管理アプリケーションを備え、前記キャッシュ管理アプリケーションは、オペレーションを行い、前記オペレーションは、
前記キャッシュ中の第１のタイプのトラックのリストを生成するステップと、
前記キャッシュ中に第２のタイプのトラックのリストを生成するステップであって、Ｉ／Ｏオペレーションは、前記第２のタイプのトラックに対してよりも前記第１のタイプのトラックに対して相対的により速く完了される、前記生成するステップと、
ある１つのトラックを前記第１のタイプのトラックの前記リストから、または前記第２のタイプのトラックの前記リストからデモートすべきかどうかを判定するステップと
を備える、
ストレージ・コントローラ。
【請求項２３】
前記第１のタイプのトラックは、ｓｙｎｃｉｏトラックであり、ｓｙｎｃｉｏトラックに対してＩ／Ｏオペレーションを行うために、アプリケーション・スレッドがスピン・ループ中に保持されて、前記Ｉ／Ｏオペレーションが完了するのを待機する、請求項２２に記載のストレージ・コントローラ。
【請求項２４】
前記第２のタイプのトラックは、ｎｏｎ−ｓｙｎｃｉｏトラックであり、ｎｏｎ−ｓｙｎｃｉｏトラックに対して前記Ｉ／Ｏオペレーションを行うために、前記アプリケーション・スレッドを前記スピン・ループ中に保持するステップが回避され、前記トラック上で行われる最後のＩ／Ｏオペレーションがｓｙｎｃｉｏオペレーションを備える第１のタイプのＩ／Ｏオペレーションまたはｎｏｎ−ｓｙｎｃｉｏオペレーションを備える第２のタイプのＩ／Ｏオペレーションであるかどうかに基づいて、ある１つのトラックが前記第１のタイプのトラックの前記リストへ、または前記第２のタイプのトラックの前記リストへ追加される、請求項２３に記載のストレージ・コントローラ。
【請求項２５】
前記第１のタイプのトラックの前記リスト中のトラックは、前記第１のタイプのトラックの前記リスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられ、前記第２のタイプのトラックの前記リスト中のトラックは、前記第２のタイプのトラックの前記リスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられる、請求項２４に記載のストレージ・コントローラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の複数の実施形態は、入力／出力（Ｉ／Ｏ：ｉｎｐｕｔ／ｏｕｔｐｕｔ）オペレーションのタイプに基づくキャッシュ管理に関する。
【背景技術】
【０００２】
あるストレージ・システム環境において、ストレージ・コントローラ（またはストレージ・コントローラ・コンプレックス）は、互いに結合された複数のストレージ・サーバを備えてよい。ストレージ・コントローラは、ホスト・コンピューティング・システムが、ストレージ・コントローラによって制御されたストレージ・デバイスを用いて入力／出力（Ｉ／Ｏ）オペレーションを行うことを許容してよく、ここで、ホスト・コンピューティング・システムは、ホストと呼ばれることがある。
【０００３】
ストレージ・コントローラは、データに対するホストからの将来のリクエストがより速くサービスされるようにそのデータを記憶するキャッシュを含む。データは、ストレージ・デバイスへ書き込み、またはそれから読み取るのと比較してずっとより速くキャッシュへ書き込まれ、またはそれから読み取られうる。キャッシュ・ヒットは、ホストからリクエストされたデータがキャッシュ中で見つかるときに発生し、キャッシュ・ミスは、リクエストされたデータがキャッシュ中で見つからないときに発生する。キャッシュ・ヒットは、キャッシュからデータを読み取ることによってサービスされ、この読み取りは、ストレージ・コントローラに結合されたストレージ・デバイスからの読み取りより速い。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
キャッシュは、スペースまたはセグメントが不足しているときには、データ項目をキャッシュからエビクト（evict）する必要があり、データ項目のキャッシュからのこのエビクション（eviction）がデモーションと呼ばれる。新しいデータ項目のための余地を作るのにキャッシュ中のどのデータ項目がデモートされるべきかを決定するためにキャッシュ置換ポリシーが用いられてよい。リースト・リーセントリ・ユーズド（ＬＲＵ：ｌｅａｓｔ  ｒｅｃｅｎｔｌｙ  ｕｓｅｄ）ポリシーは、最近、最も長い時間にわたってアクセスされなかった項目を最初にデモート（demote）する。本発明は、キャッシュ管理のための方法、システム、およびコンピュータ・プログラムを提供する。
【課題を解決するための手段】
【０００５】
典型的な実施形態において、キャッシュ中の第１のタイプのトラックのリストが生成され、キャッシュ中の第２のタイプのトラックのリストが生成され、Ｉ／Ｏオペレーションは、第２のタイプのトラックに対してよりも第１のタイプのトラックに対して相対的により速く完了される。ある１つのトラックを第１のタイプのトラックのリストから、または第２のタイプのトラックのリストからデモートすべきかどうかについて判定が行われる。判定の結果として、デモートされるトラックがＩ／Ｏオペレーションの速度を増加させる。
【０００６】
さらなる実施形態例において、第１のタイプのトラックは、ｓｙｎｃｉｏトラックであり、ｓｙｎｃｉｏトラックに対してＩ／Ｏオペレーションを行うためには、アプリケーション・スレッドがスピン・ループ中に保持されて、そのＩ／Ｏオペレーションが完了するのを待機する。結果として、ある実施形態においては、Ｉ／Ｏオペレーションの速度を増加させるために、ｓｙｎｃｉｏトラックをデモートしない方が望ましいことがある。
【０００７】
なおさらなる実施形態において、第２のタイプのトラックは、ｎｏｎ−ｓｙｎｃｉｏトラックであり、ｎｏｎ−ｓｙｎｃｉｏトラックに対してＩ／Ｏオペレーションを行うためには、アプリケーション・スレッドをスピン・ループ中に保持するステップが回避され、トラック上で行われる最後のＩ／Ｏオペレーションがｓｙｎｃｉｏオペレーションを備える第１のタイプのＩ／Ｏオペレーションまたはｎｏｎ−ｓｙｎｃｉｏオペレーションを備える第２のタイプのＩ／Ｏオペレーションであるかどうかに基づいて、ある１つのトラックが第１のタイプのトラックのリストへ、または第２のタイプのトラックのリストへ追加される。結果として、２つの異なるタイプのリストを構築することによってＩ／Ｏオペレーションの速度が増加される。
【０００８】
さらなる実施形態において、第１のタイプのトラックのリスト中のトラックは、第１のタイプのトラックのリスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられ、第２のタイプのトラックのリスト中のトラックは、第２のタイプのトラックのリスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられる。結果として、２つの異なるタイプのトラックのリースト・リーセントリ・ユーズド・リストを構築することによってＩ／Ｏオペレーションの速度が増加される。
【０００９】
ある実施形態において、第２のタイプのトラックのリスト中のトラックについてのリード・ヒット率が第１のタイプのトラックにおけるトラックについてのリード・ヒット率の所定の係数より小さいと判定するステップに応答して、ある１つのトラックが第２のタイプのトラックのリストからデモートされる。第２のタイプのトラックからのデモーション（demotion）の結果として、Ｉ／Ｏオペレーションの速度が増加される。
【００１０】
追加の実施形態において、第１のタイプのトラックのリスト中のトラックについてのリード・ヒット率および第２のタイプのトラックのリスト中のトラックについてのリード・ヒット率が第１のタイプのトラックおよび第２のタイプのトラックのリストの所定の底の部分に対するリード・ヒットに基づいて計算される。結果として、トラックのデモーションは、より最近に用いられたトラックのセットに関する統計データを収集するステップに基づく。
【００１１】
さらなる実施形態において、入力／出力（Ｉ／Ｏ）オペレーションの速度を増加させるために所定の係数が調整される。結果として、システム中のＩ／Ｏオペレーションの速度がかかるデモーションの結果として減少しないかぎり、可能ならばいつでも、ｓｙｎｃｉｏトラックのＬＲＵリストからのトラックではなく、むしろｎｏｎ−ｓｙｎｃｉｏトラックのＬＲＵリストからのトラックがデモートされる。
【００１２】
次に、同様の参照番号が全体にわたって対応する部分を表す図面を参照する。
【図面の簡単な説明】
【００１３】
【図１】ある実施形態に従って、ｓｙｎｃｉｏベースのＩ／Ｏオペレーションがホストからストレージ・コントローラに向かって発生する、１つ以上のホストおよび１つ以上のストレージ・デバイスに結合されたストレージ・コントローラを備えるコンピューティング環境のブロック図を図示する。
【図２】ある実施形態に従って、トラックのリースト・リーセントリ・ユーズド（ＬＲＵ）リストがどのようにストレージ・コントローラ中に維持されるかを示すブロック図を図示する。
【図３】ある実施形態に従って、トラックのｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリストからまたはｓｙｎｃｉｏ  ＬＲＵリストからのデモーションを示す第１のフローチャートを図示する。
【図４】ある実施形態に従って、トラックのｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリストからまたはｓｙｎｃｉｏ  ＬＲＵリストからのデモーションを示す第２のフローチャートを図示する。
【図５】ある実施形態に従って、リード・ヒット率がどのように計算されるかを示すフローチャートを図示する。
【図６】ある実施形態に従って、トラックのデモーションについての所定の係数がどのように計算されるか示すブロック図を図示する。
【図７】ある実施形態に従って、２つの異なるタイプのトラックのリストを生成するステップに基づくトラックのデモーションを示すフローチャートを図示する。
【図８】ある実施形態に従って、クラウド・コンピューティング環境のブロック図を図示する。
【図９】ある実施形態に従って、図８のクラウド・コンピューティング環境のさらなる詳細のブロック図を図示する。
【図１０】ある実施形態に従って、図１〜９に記載されるような、ストレージ・コントローラまたはホスト中に含まれてよいいくつかの要素を示す計算システムのブロック図を図示する。
【発明を実施するための形態】
【００１４】
以下の記載においては、本明細書の一部を形成し、かついくつかの実施形態を図示する添付図面が参照される。他の実施形態が利用されてもよく、構造およびオペレーションの変更が行われてもよいことが理解される。
【００１５】
ｓｙｎｃｉｏ（ｓｙｎｃ  Ｉ／Ｏとも呼ばれる）は、計算デバイスのための装着型ハードウェアおよびプロトコルを備える。ｓｙｎｃｉｏは、超低レイテンシのランダム・リードおよび小ブロックのシーケンシャル・ライト用に設計される。計算デバイス間のｓｙｎｃｉｏ接続は、ポイント・ツー・ポイントの光学的ペリフェラル・コンポーネント・インターコネクト・エキスプレス（ＰＣＩｅ：Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ  Ｅｘｐｒｅｓｓ）インターフェースを通じてよい。ｓｙｎｃｉｏオペレーションは、ｓｙｎｃｉｏではＩ／Ｏオペレーションが完了するのを待機している間、ホスト計算デバイスがアプリケーション・スレッドをスピン・ループ中に保持してよいという点で従来型Ｉ／Ｏとは異なって振舞う。これは、プロセッサ・サイクルが従来型Ｉ／Ｏの２つのコンテキストのスワップを行う必要性、Ｉ／Ｏスレッドをスリープ状態にして、その後、Ｉ／Ｏスレッドを再ディスパッチするためのオペレーションを行う必要性、およびＩ／Ｏ割り込みの必要性を回避する。
【００１６】
ｓｙｎｃｉｏオペレーションの時間要件を満たすためには、計算デバイス中のコード・パスが極度に最適化される必要がある。キャッシュ・ミスのような、ｓｙｎｃｉｏオペレーションを遅延させるいずれかの状態がｓｙｎｃｉｏオペレーションを行うことができないことを示すステータスを生成して、ｓｙｎｃｉｏオペレーションが再試行されなければならないことがある。ｓｙｎｃｉｏオペレーションは、キャッシュ・ヒットがあるときにのみ首尾よく行われうるので、ある実施形態がｓｙｎｃｉｏオペレーションのためのキャッシュ・ヒットを増加させるために提供される。かかる実施形態において、ｓｙｎｃｉｏトラックおよびｎｏｎ−ｓｙｎｃｉｏトラックに対して別個のリースト・リーセントリ・ユーズド（ＬＲＵ）リストを維持し、別個のＬＲＵリストに基づくデモーション・メカニズムを用いることによって、単一のＬＲＵリストのみが維持される実施形態と比較して、ｓｙｎｃｉｏオペレーションがより速く完了される。ある実施形態においては、可能であればいつでも、システム中のＩ／Ｏオペレーションの速度がかかるデモーションの結果として減少しない限り、ｓｙｎｃｉｏトラックのＬＲＵリストからのトラックではなく、むしろｎｏｎ−ｓｙｎｃｉｏトラックのＬＲＵリストからのトラックがデモートされる。
【００１７】
例示的な実施形態
図１は、ある実施形態に従って、１つ以上のホスト１０４、１０６および１つ以上のストレージ・デバイス１０８、１１０に結合されたストレージ・コントローラ１０２を備えるコンピューティング環境１００のブロック図を図示する。ストレージ・コントローラ１０２は、複数のホスト１０４、１０６がストレージ・コントローラ１０２により維持された論理ストレージを用いて入力／出力（Ｉ／Ｏ）オペレーションを行うことを許容する。論理ストレージに対応する物理ストレージは、ストレージ・デバイス１０８、１１０もしくはストレージ・コントローラ１０２のキャッシュ１１２（例えば、メモリ）またはその両方のうちの１つ以上に見出されてよい。
【００１８】
ストレージ・コントローラ１０２およびホスト１０４、１０６は、当技術分野において現在知られているもの、例えば、パーソナル・コンピュータ、ワークステーション、サーバ、メインフレーム、ハンド・ヘルド・コンピュータ、パーム・トップ・コンピュータ、テレフォニ・デバイス、ネットワーク・アプライアンス、ブレード・コンピュータ、処理デバイスなどを含めて、任意の適切な計算デバイスを備えてよい。ストレージ・コントローラ１０２、ホスト１０４、１０６およびストレージ・デバイス１０８、１１０は、任意の適切なネットワーク１１４、例えば、ストレージ・エリア・ネットワーク、ワイド・エリア・ネットワーク、インターネット、イントラネット中の要素であってよい。ある実施形態において、ストレージ・コントローラ１０２、ホスト１０４、１０６およびストレージ・デバイス１０８、１１０は、コンピューティング環境１００を備えるクラウド・コンピューティング環境中の要素であってよい。ストレージ・デバイス１０８、１１０は、ストレージ・ディスク、テープ・ドライブ、固体ストレージなどからなってよく、ストレージ・コントローラ１０２によって制御されてよい。
【００１９】
ある実施形態において、ホスト１０４、１０６は、バス・インターフェース（例えば、ポイント・ツー・ポイントの光学的ＰＣＩｅインターフェース）１１６、１１８およびネットワーク・インターフェース１２０、１２２を介してストレージ・コントローラ１０２に結合されてよい。ホスト１０４、１０６からのｓｙｎｃｉｏオペレーションは、バス・インターフェース１１６、１１８を通じて行われてよい。ホスト１０４、１０６からの従来型Ｉ／Ｏオペレーション（すなわち、ｎｏｎ−ｓｙｎｃｉｏオペレーション）は、ネットワーク・インターフェース１２０、１２２を通じて行われてよい。バス・インターフェース１１６、１１８は、ネットワーク・インターフェース１２０、１２２より速いＩ／Ｏ用アクセス・チャネルを備えてよい。イーサネットを通じてのＰＣＩｅを、例えば、ＥｘｐＥｔｈｅｒ技術を用いて、可能にするために、分散型ＰＣＩｅスイッチのような、ＰＣＩｅ拡張ケーブルまたはコンポーネントを含めて、バス・インターフェース１１６、１１８を拡張するための追加のバス・インターフェース技術が利用されてもよい。
【００２０】
キャッシュ１１２は、ある実施形態において、１つ以上のランクに区分された読み出し／書き込みキャッシュを備えてよく、ここで各ランクは、１つ以上のストレージ・トラックを含んでよい。キャッシュ１１２は、当技術分野で知られているまたは将来に開発される任意の適切なキャッシュであってよい。いくつかの実施形態において、キャッシュ１１２は、揮発性メモリもしくは不揮発性メモリまたはその両方を用いて実装されてよい。キャッシュ１１２は、修正および未修正データの両方を記憶してよい。キャッシュ１１２は、ｓｙｎｃｉｏトラック１２４およびｎｏｎ−ｓｙｎｃｉｏトラック１２６を含む複数のトラックにデータを記憶してよい。ｓｙｎｃｉｏトラック１２４は、ホスト１０４、１０６からストレージ・コントローラ１０２上で行われるｓｙｎｃｉｏオペレーション１２８を介して読み出され、かつ書き込まれてよく、ｎｏｎ−ｓｙｎｃｉｏトラック１２６は、ホスト１０４、１０６からストレージ・コントローラ１０２上で行われるｎｏｎ−ｓｙｎｃｉｏオペレーション１３０を介して読み出され、かつ書き込まれてよい。
キャッシュ管理アプリケーション１３２は、キャッシュ１１２中の未修正ｓｙｎｃｉｏトラックのｓｙｎｃｉｏリースト・リーセントリ・ユーズド（ＬＲＵ）リスト１３４およびキャッシュ１１２中の未修正ｎｏｎ−ｓｙｎｃｉｏトラックのｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３６を生成し、ここで未修正ｓｙｎｃｉｏトラックおよび未修正ｎｏｎ−ｓｙｎｃｉｏトラックは、キャッシュ１１２中の空間を開放するためのキャッシュ１１２からのデモーションの候補である。ある実施形態において、キャッシュ管理アプリケーション１３２は、ソフトウェア、ハードウェア、ファームウェアまたはそれらの組み合わせで実装されてよい。
【００２１】
図２は、ある実施形態に従って、トラックのＬＲＵリストがどのようにストレージ・コントローラ１０２中に維持されるかを示すブロック図２００を図示する。
【００２２】
ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４は、それに対してｎｏｎ−ｓｙｎｃｉｏオペレーションが行われてよいキャッシュ１１２中の未修正ｎｏｎ−ｓｙｎｃｉｏトラックのリストであり、ｓｙｎｃｉｏ  ＬＲＵリスト１３６は、それに対してｓｙｎｃｉｏオペレーションが行われてよいキャッシュ１１２中の未修正ｓｙｎｃｉｏトラックのリストである。
【００２３】
ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中のエントリは、モースト・リーセントリ・ユーズド（most recently used）２０２からリースト・リーセントリ・ユーズド２０４まで上から下へ配置された、キャッシュ１１２中の未修正ｎｏｎ−ｓｙｎｃｉｏトラックである。ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４に対するリード・ヒット率を計算するために、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４の底の部分２０６におけるいくつかの所定のエントリが用いられてよい。
ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４に対するリード・ヒット率を計算するために底の部分２０６（例えば、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中の１０００個のリースト・リーセントリ・ユーズドｎｏｎ−ｓｙｎｃｉｏトラック）のみを選択することによって、キャッシュ１１２からデモートされる可能性のあるトラックについてリード・ヒット率が決定される。
【００２４】
ｓｙｎｃｉｏ  ＬＲＵリスト１３６中のエントリは、モースト・リーセントリ・ユーズド２０８からリースト・リーセントリ・ユーズド２１０まで上から下へ配置された、キャッシュ１１２中の未修正ｓｙｎｃｉｏトラックである。ｓｙｎｃｉｏ  ＬＲＵリスト１３６に対するリード・ヒット率を計算するために、ｓｙｎｃｉｏ  ＬＲＵリスト１３６の底の部分２１２におけるいくつかの所定のエントリが用いられてよい。ｓｙｎｃｉｏ  ＬＲＵリスト１３６に対するリード・ヒット率を計算するために底の部分２１２（例えば、ｓｙｎｃｉｏ  ＬＲＵリスト１３６中の１０００個のリースト・リーセントリ・ユーズドｓｙｎｃｉｏトラック）のみを選択することによって、キャッシュ１１２からデモートされる可能性のあるトラックについてリード・ヒット率が決定される。
【００２５】
図３は、ある実施形態に従って、トラックのｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリストからまたはｓｙｎｃｉｏ  ＬＲＵリストからのデモーションを示す第１のフローチャート３００を図示する。図３に示されるオペレーションは、ストレージ・コントローラ１０２中で実行するキャッシュ管理アプリケーション１３２によって行われてよい。
【００２６】
制御は、キャッシュ管理アプリケーション１３２がｓｙｎｃｉｏ  ＬＲＵリスト１３６を生成して維持するブロック３０２において開始する。キャッシュ管理アプリケーション１３２は、ｓｙｎｃｉｏ  ＬＲＵリスト１３６中のトラックについてリード・ヒット率を（ブロック３０４において）決定し、制御は、ブロック３０２へ戻る。
【００２７】
ブロック３０２、３０４に示されるオペレーションと並行して、キャッシュ管理アプリケーション１３２は、（ブロック３０６において）ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４を生成して維持する。キャッシュ管理アプリケーション１３２は、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中のトラックについてリード・ヒット率を（ブロック３０８において）決定し、制御は、ブロック３０６へ戻る。
【００２８】
ブロック３０２、３０４、３０６、３０８のオペレーションが行われている間に、キャッシュ管理アプリケーション１３２は、トラックをキャッシュ１１２からデモートするためのオペレーションを（ブロック３１０において）行うステップを継続するかまたは開始する。キャッシュ管理アプリケーション１３２は、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中のトラックについてのリード・ヒット率がｓｙｎｃｉｏ  ＬＲＵリスト１３６中のトラックについてのリード・ヒット率の所定の係数（例えば、倍数）より小さいかどうかを（ブロック３１２において）判定する。例えば、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中のトラックについてのリード・ヒット率が０．２であり、ｓｙｎｃｉｏ  ＬＲＵリスト１３６中のトラックについてのリード・ヒット率が０．１であり、所定の係数が３であれば、所定の係数を乗じたｓｙｎｃｉｏ  ＬＲＵリスト１３６中のトラックについてのリード・ヒット率は、０．３である。ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中のトラックについてのリード・ヒット率は、０．３より小さい０．２である。それゆえに、この例では、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中のトラックについてのリード・ヒット率がｓｙｎｃｉｏ  ＬＲＵリスト１３６中のトラックについてのリード・ヒット率の所定の係数より小さい。
【００２９】
ブロック３１２において、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中のトラックについてのリード・ヒット率がｓｙｎｃｉｏ  ＬＲＵリスト１３６中のトラックについてのリード・ヒット率の所定の係数より小さいと判定されれば（「Ｙｅｓ」分岐３１４）、そのときにはキャッシュ管理アプリケーション１３２がトラックをｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４から（ブロック３１６において）デモートし、ｓｙｎｃｉｏオペレーションの性能は、ｓｙｎｃｉｏトラックがデモートされる状況を超えて向上されうる。ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中のトラックは、ｓｙｎｃｉｏ  ＬＲＵリスト１３６中のトラックより十分に少なく用いられており、従って、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４からデモートするのが望ましい。
【００３０】
ブロック３１２において、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中のトラックについてのリード・ヒット率がｓｙｎｃｉｏ  ＬＲＵリスト１３６中のトラックについてのリード・ヒット率の所定の係数より小さくないと判定されれば（「Ｎｏ」分岐３１８）、そのときにはキャッシュ管理アプリケーション１３２がトラックをｓｙｎｃｉｏ  ＬＲＵリスト１３６から（ブロック３２０において）デモートする。ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中のトラックは、ｓｙｎｃｉｏ  ＬＲＵリスト１３６中のトラックより十分に多く用いられており、従って、ｓｙｎｃｉｏ  ＬＲＵリスト１３６からデモートするのが望ましい。ｓｙｎｃｉｏ  ＬＲＵリスト１３６中のトラックに対する比較的少ないリード・ヒットがあってよく、従って、トラックをｓｙｎｃｉｏ  ＬＲＵリスト１３６からデモートするのが望ましい。
【００３１】
それゆえに、図３は、ｓｙｎｃｉｏおよびｎｏｎ−ｓｙｎｃｉｏトラックに対して異なるＬＲＵリストを維持することによって、単一のＬＲＵリストのみが維持される実施形態と比較して、ｓｙｎｃｉｏオペレーションがより速く実行されうる実施形態を記載する。
【００３２】
図４は、ある実施形態に従って、トラックのｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４からまたはｓｙｎｃｉｏ  ＬＲＵリスト１３６からのデモーションを示す第２のフローチャートを図示する。図４に示されるオペレーションは、ストレージ・コントローラ１０２中で実行するキャッシュ管理アプリケーション１３２によって行われてよい。
【００３３】
制御は、キャッシュ管理アプリケーション１３２がｓｙｎｃｉｏ  ＬＲＵリスト１３６が空かどうかを判定するブロック４０２において開始する。空であれば（「Ｙｅｓ」分岐４０４）、制御は、キャッシュ管理アプリケーション１３２がトラックをｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４からデモートするブロック４０６へ進む。そうでない場合には（「Ｎｏ」分岐４０８）、制御は、キャッシュ管理アプリケーション１３２がｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４が空かどうかを判定するブロック４１０へ進む。
【００３４】
ブロック４１０において、キャッシュ管理アプリケーション１３２がｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４が空であると判定すれば（「Ｙｅｓ」分岐４１２）、そのときにはキャッシュ管理アプリケーション１３２がトラックをｓｙｎｃｉｏ  ＬＲＵリスト１３６からデモートする。そうでない場合には（「Ｎｏ」分岐４１６）、キャッシュ管理アプリケーション１３２がｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４の最も古いトラックがｓｙｎｃｉｏ  ＬＲＵリスト１３６の最も古いトラックより古いかどうかを判定するブロック４１８へ進み、ここでリストの最も古いトラックとは、リスト中の他のすべての最後の使用より前の時間に最後に用いられた（すなわち、リード・ヒットがトラックに対して発生した）トラックであり、２番目のトラックの最後の使用の前の時間に最後に用いられた１番目のトラックは、２番目のトラックより古い。
【００３５】
ブロック４１８において、キャッシュ管理アプリケーション１３２がｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４中の最も古いトラックがｓｙｎｃｉｏ  ＬＲＵリスト１３６中の最も古いトラックより古いと判定すれば（「Ｙｅｓ」分岐４２０）、制御は、キャッシュ管理アプリケーション１３２がトラックをｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４からデモートするブロック４２２へ進む。そうでない場合には（「Ｎｏ」分岐４２４）、キャッシュ管理アプリケーション１３２が（ａ）ｓｙｎｃｉｏ  ＬＲＵリストの底の部分２１２、および（ｂ）ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリストの底の部分２０６に対するリード・ヒット率を（ブロック４２６において）計算する。
【００３６】
ｓｙｎｃｉｏ  ＬＲＵリストの底の部分２１２に対するリード・ヒット率は、ＳＩＯ＿ＢＯＴＴＯＭＨＩＴＳと呼ばれ、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリストの底の部分２０６に対するリード・ヒット率は、ＮＯＮＳＩＯ＿ＢＯＴＴＯＭＨＩＴＳと呼ばれる。
【００３７】
ブロック４２６から、制御は、キャッシュ管理アプリケーション１３２がＮＯＮＳＩＯ＿ＢＯＴＴＯＭＨＩＴＳが所定の係数を乗じたＳＩＯ＿ＢＯＴＴＯＭＨＩＴＳより小さいかどうかを判定するブロック４２８へ進む。小さければ（「Ｙｅｓ」分岐４３０）、キャッシュ管理アプリケーション１３２がトラックをｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４からデモートする。そうでない場合には（「Ｎｏ」分岐４３４）、キャッシュ管理アプリケーション１３２がトラックをｓｙｎｃｉｏ  ＬＲＵリスト１３６から（ブロック４３６において）デモートする。
【００３８】
それゆえに、図４は、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４およびｓｙｎｃｉｏ  ＬＲＵリスト１３６中の相対的により古いトラックであるトラックに対するリード・ヒットの比較が行われるように、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４およびｓｙｎｃｉｏ  ＬＲＵリスト１３６の少なくとも底の部分２０６、２１２がリード・ヒットの比較のために用いられる、ある実施形態を図示する。トラックのデモーションは、これらの相対的により古いトラックからであり、従って、リード・ヒット率は、これらの相対的により古いトラックについて計算される。
【００３９】
図５は、ある実施形態に従って、リード・ヒット率がどのように計算されるか示すフローチャート５００を図示する。図５に示されるオペレーションは、ストレージ・コントローラ１０２中で実行するキャッシュ管理アプリケーション１３２によって行われてよい。
【００４０】
制御は、キャッシュ管理アプリケーション１３２がｓｙｎｃｉｏ  ＬＲＵリストの底の部分２１２についてリード・ヒット・カウンタを、およびｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリストの底の部分２０６についてリード・ヒット・カウンタをゼロにセットするブロック５０１において開始する。制御は、リード・オペレーションがキャッシュ１１２に対するリード・ヒットを生成するブロック５０２へ進み、制御は、並行してブロック５０４および５０６へ進む。ブロック５０４において、キャッシュ管理アプリケーション１３２は、リード・ヒットがｓｙｎｃｉｏ  ＬＲＵリストの底の部分２１２に対するものかどうかを判定し、そうであれば（「Ｙｅｓ」分岐５０８）、ｓｙｎｃｉｏ  ＬＲＵリストの底の部分２１２についてリード・ヒットが（ブロック５１０において）インクリメントされる。そうでない場合には（「Ｎｏ」分岐５１２）、制御は、ブロック５０２へ戻る。
【００４１】
ブロック５０６において、キャッシュ管理アプリケーション１３２は、リード・ヒットがｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリストの底の部分２０６に対するものかどうかを判定し、そうであれば（「Ｙｅｓ」分岐５１４）、ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリストの底の部分２０６についてリード・ヒット・カウンタが（ブロック５１６において）インクリメントされる。そうでない場合には（「Ｎｏ」分岐５１８）、制御は、ブロック５０２へ戻る。ブロック５０１、５０２、５０４、５０６、５０８、５１０、５１２、５１４、５１６、５１８のオペレーションが（参照数字５２０によって示されるように）ある時間の間隔（例えば、８００ミリ秒）にわたって繰り返して行われる。
【００４２】
参照数字５２０によって示されるオペレーションが行われている間に、ブロック５２２および５２４に示されるオペレーションが行われる。ブロック５２２において、キャッシュ管理アプリケーション１３２は、最後のＮ個の間隔についてリード・ヒットを加算して、それらの間隔にわたる累計時間で除することによって、ｓｙｎｃｉｏリストの底の部分２１２についてリード・ヒット率を計算する。ブロック５２４において、キャッシュ管理アプリケーション１３２は、最後のＮ個の間隔についてリード・ヒットを加算し、それらの間隔にわたる累計時間で除することによって、ｎｏｎ−ｓｙｎｃｉｏリストの底の部分２０６についてリード・ヒット率を計算する。ある実施形態において、Ｎは、３０のような数であってよい。
【００４３】
それゆえに、図５は、図４に示されるオペレーションに用いるべくｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４およびｓｙｎｃｉｏ  ＬＲＵリスト１３６の底の部分に対するリード・ヒット率を計算するためのある実施形態を図示する。
【００４４】
図６は、ある実施形態に従って、トラックのデモーションについての所定の係数がどのように計算されるかを示すブロック図６００を図示する。例示的な所定の係数は、図３のブロック３１２、および図４のブロック４２８に用いられることが示された。
【００４５】
ある実施形態において、所定の係数は、（参照数字６０２によって示されるように）システムの性能ベンチマークに基づいてよい。他の実施形態では、所定の係数は、（参照数字６０４によって示されるように）ｎｏｎ−ｓｙｃｉｏワークロードよりもｓｙｃｉｏワークロードについてより良好な性能を所望するカスタマによって構成されてよい。なおさらなる実施形態において、所定の係数は、（参照数字６０６によって示されるように）ストレージ・コントローラ１０２において発生しているＩ／Ｏオペレーションの速度に基づいて動的に変更されてよい。例えば、所定の係数を増加するにつれてＩ／Ｏオペレーションの速度が増加すれば、そのときにはキャッシュ管理アプリケーション１３２が所定の係数を増加させ続け、所定の係数を増加するにつれてＩ／Ｏオペレーションの速度が減少すれば、そのときにはキャッシュ管理アプリケーション１３２が所定の係数を減少させ続ける。
【００４６】
図７は、ある実施形態に従って、２つの異なるタイプのトラックのリストを生成するステップに基づくトラックのデモーションを示すフローチャート７００を図示する。図７に示されるオペレーションは、ストレージ・コントローラ１０２中で実行するキャッシュ管理アプリケーション１３２によって行われてよい。
【００４７】
制御は、キャッシュ１１２中の第１のタイプのトラックのリスト（例えば、ｓｙｎｃｉｏ  ＬＲＵリスト１３６）が生成されるブロック７０２において開始する。制御は、キャッシュ１１２中の第２のタイプのトラックのリスト（ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４）が生成されるブロック７０４へ進み、Ｉ／Ｏオペレーションは、第２のタイプのトラックに対してよりも第１のタイプのトラックに対して相対的により速く完了され、トラック上で行われる最後のＩ／Ｏオペレーションが第１のタイプのＩ／Ｏオペレーション（例えば、ｓｙｎｃｉｏオペレーション）または第２のタイプのＩ／Ｏオペレーション（例えば、ｎｏｎ−ｓｙｎｃｉｏオペレーション）であるかどうかに基づいて、ある１つのトラックが第１のタイプのトラックのリストに、または第２のタイプのトラックのリストに追加される。例えば、ある１つのトラック上で行われる最後のＩ／Ｏオペレーションがｓｙｎｃｉｏオペレーションであれば、そのときにはそのトラックがｓｙｎｃｉｏ  ＬＲＵリスト１３６に追加され、ある１つのトラック上で行われる最後のＩ／Ｏオペレーションがｎｏｎ−ｓｙｎｃｉｏオペレーションであれば、そのときにはそのトラックがｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４に追加される。ある１つのトラックを第１のタイプのトラックのリストから、または第２のタイプのトラックのリストからデモートすべきかどうかについて（ブロック７０６において）判定が行われる。第１のタイプのトラックは、ｓｙｎｃｉｏトラックであってよく、ここでｓｙｎｃｉｏトラックに対してＩ／Ｏオペレーションを行うために、アプリケーション・スレッドがスピン・ループ中に保持されて、Ｉ／Ｏオペレーションが完了するのを待機する。第２のタイプのトラックは、ｎｏｎ−ｓｙｎｃｉｏトラックであってよく、ここでｎｏｎ−ｓｙｎｃｉｏトラックに対してＩ／Ｏオペレーションを行うために、アプリケーション・スレッドをスピン・ループ中に保持するステップは、回避される。
【００４８】
ある実施形態において、第１のタイプのトラックのリスト中のトラックは、（例えば、参照数字２０８、２１０によって示されるように）第１のタイプのトラックのリスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられ、第２のタイプのトラックのリスト中のトラックは、（例えば、参照数字２０２、２０４によって示されるように）第２のタイプのトラックのリスト中の各トラックがどれほど最近に用いられたかに基づいて順序付けられ、ここでリード・ヒットがある１つのトラックに対して発生すれば、そのトラックは用いられたと言われる。
【００４９】
ブロック７０６に示されるトラック・デモーションに関する判定を行うために、ある実施形態において、第２のタイプのトラックのリスト中のトラックについてのリード・ヒット率が第１のタイプのトラックにおけるトラックについてのリード・ヒット率の所定の係数より小さいと判定するステップに応答して、ある１つのトラックが第２のタイプのトラックのリストから（ブロック７０８において）デモートされる。第１のタイプのトラックのリスト中のトラックについてのリード・ヒット率および第２のタイプのトラックのリスト中のトラックについてのリード・ヒット率は、第１のタイプのトラックおよび第２のタイプのトラックのリストの所定の底の部分に対するリード・ヒットに基づいて計算される。入力／出力（Ｉ／Ｏ）オペレーションの速度を増加させるために所定の係数が調整される。
【００５０】
それゆえに、図１〜７は、ｓｙｎｃｉｏトラックおよびｎｏｎ−ｓｙｎｃｉｏトラックに対して別個のＬＲＵリストを維持し、別個のＬＲＵリストに基づくデモーション・メカニズムを用いることによって、単一のＬＲＵリストのみが維持される実施形態と比較して、ｓｙｎｃｉｏオペレーションがより速く完了される、ある実施形態を図示する。ある実施形態において、可能であればいつでも、システム中のＩ／Ｏオペレーションの速度がかかるデモーションの結果として減少しない限り、ｓｙｎｃｉｏトラックのＬＲＵリスト（ｓｙｎｃｉｏ  ＬＲＵリスト１３６）からのトラックではなく、むしろｎｏｎ−ｓｙｎｃｉｏトラックのＬＲＵリスト（ｎｏｎ−ｓｙｎｃｉｏ  ＬＲＵリスト１３４）からのトラックがデモートされる。
【００５１】
クラウド・コンピューティング環境
クラウド・コンピューティングは、最小限の管理努力またはサービス・プロバイダとの相互作用によって迅速にプロビジョンし、かつ解除することができるコンフィギュラブルなコンピューティング・リソース（例えば、ネットワーク、サーバ、ストレージ、アプリケーション、およびサービス）の共有プールへの便利なオンデマンド・ネットワーク・アクセスを可能にするためのモデルである。
【００５２】
次に、図８を参照すると、例示的なクラウド・コンピューティング環境５０が描かれる。示されるように、クラウド・コンピューティング環境５０は、クラウド・コンシューマによって用いられるローカル・コンピューティング・デバイス、例えば、携帯情報端末（ＰＤＡ：ｐｅｒｓｏｎａｌ  ｄｉｇｉｔａｌ  ａｓｓｉｓｔａｎｔ）または携帯電話５４Ａ、デスクトップ・コンピュータ５４Ｂ、ラップトップ・コンピュータ５４Ｃ、もしくは自動車コンピュータ・システム５４Ｎまたはそれらのすべてなどが通信してよい１つ以上のクラウド・コンピューティング・ノード１０を備える。ノード１０は、互いに通信してよい。これらのノードは、先に記載されたようなプライベート、コミュニティ、パブリック、もしくはハイブリッド・クラウド、またはそれらの組み合わせなど、１つ以上のネットワークに、物理的または仮想的にグループ分けされてよい（示されない）。これは、クラウド・コンシューマがそのためにリソースをローカル・コンピューティング・デバイス上に維持する必要のないフラストラクチャ、プラットフォームもしくはソフトウェア・アズ・サービスまたはそれらのすべてをクラウド・コンピューティング環境５０が提供することを許容する。図８に示されるタイプのコンピューティング・デバイス５４Ａ〜Ｎは、例示に過ぎないことが意図され、コンピューティング・ノード１０およびクラウド・コンピューティング環境５０は、任意のタイプのネットワークもしくはネットワークによってアドレス可能な接続またはその両方を通じて（例えば、ｗｅｂブラウザを用いて）、任意のタイプのコンピュータ化デバイスと通信できることが理解される。
【００５３】
次に、図９を参照すると、クラウド・コンピューティング環境５０（図８）によって提供される機能抽象化層のセットが示される。図９に示されるコンポーネント、層、および機能は、例示に過ぎないことが意図され、本発明の実施形態は、それらに限定されないことが予め理解されるべきである。
【００５４】
ハードウェアおよびソフトウェア層６０は、ハードウェアおよびソフトウェア・コンポーネントを含む。ハードウェア・コンポーネントの例は、メインフレーム、一例ではＩＢＭ  ｚＳｅｒｉｅｓシステム、ＲＩＳＣ（縮小命令セット・コンピュータ：Ｒｅｄｕｃｅｄ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｅｒ）アーキテクチャ・ベースのサーバ、一例ではＩＢＭ  ｐＳｅｒｉｅｓシステム、ＩＢＭ  ｘＳｅｒｉｅｓシステム、ＩＢＭ  ＢｌａｄｅＣｅｎｔｅｒシステム、ストレージ・デバイス、ネットワークおよびネットワーキング・コンポーネントを含む。ソフトウェア・コンポーネントの例は、ネットワーク・アプリケーション・サーバ・ソフトウェア、一例ではＩＢＭ  ＷｅｂＳｐｈｅｒｅアプリケーション・サーバ・ソフトウェア、およびデータベース・ソフトウェア、一例ではＩＢＭ  ＤＢ２データベース・ソフトウェアを含む。（ＩＢＭ、ｚＳｅｒｉｅｓ、ｐＳｅｒｉｅｓ、ｘＳｅｒｉｅｓ、ＢｌａｄｅＣｅｎｔｅｒ、ＷｅｂＳｐｈｅｒｅ、およびＤＢ２は、世界中の多くの管轄区域において登録されたＩｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎの商標である）
【００５５】
仮想化層６２は、抽象化層を提供し、抽象化層からは仮想エンティティの以下の例、すなわち、仮想サーバ、仮想ストレージ、仮想プライベート・ネットワークを含めて、仮想ネットワーク、仮想アプリケーションおよびオペレーティング・システム、ならびに仮想クライアントが提供されてよい。
【００５６】
一例において、管理層６４は、以下に記載される機能を提供してよい。リソース・プロビジョニングは、クラウド・コンピューティング環境内でタスクを行うために利用されるコンピューティング・リソースおよび他のリソースの動的な調達を提供する。計量及び料金設定は、クラウド・コンピューティング環境内でリソースが利用される際のコスト追跡、およびこれらのリソースの消費に対する課金または請求を提供する。一例において、これらのリソースは、アプリケーション・ソフトウェア・ライセンスを備えてよい。セキュリティは、クラウド・コンシューマおよびタスクについての識別情報検証、ならびにデータおよび他のリソースのための保護を提供する。ユーザ・ポータルは、コンシューマおよびシステム・アドミニストレータのためにクラウド・コンピューティング環境へのアクセスを提供する。サービス・レベル管理は、要求されるサービス・レベルが満たされるようなクラウド・コンピューティング・リソース割り当ておよび管理を提供する。サービス・レベル・アグリメント（ＳＬＡ：Ｓｅｒｖｉｃｅ  Ｌｅｖｅｌ  Ａｇｒｅｅｍｅｎｔ）計画および履行は、それらに対する将来の要求がＳＬＡに従って予期されるクラウド・コンピューティング・リソースのための事前配置およびその調達を提供する。
【００５７】
ワークロード層６６は、クラウド・コンピューティング環境がそのために利用されてよい機能性の例を提供する。この層から提供されてよいワークロードおよび機能の例は、マッピングおよびナビゲーション、ソフトウェア開発およびライフサイクル管理、仮想教室教育配信、データ解析処理、取引処理、および図１〜８に示されるようなデモート・オペレーション６８の処理を含む。
【００５８】
追加の実施形態の詳細
記載されるオペレーションは、ソフトウェア、ファームウェア、ハードウェア、またはそれらの任意の組み合わせを作り出すために標準的なプログラミングもしくは工学技術またはその両方を用いた方法、装置またはコンピュータ・プログラム製品として実装されてよい。それに応じて、実施形態の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、あるいは、本明細書ではすべてが全般的に「回路」、「モジュール」または「システム」と呼ばれてよいソフトウェアおよびハードウェアの態様を組み合わせた実施形態の形をとってよい。さらにまた、実施形態の態様は、コンピュータ・プログラム製品の形をとってもよい。コンピュータ・プログラム製品は、本実施形態の態様をプロセッサに実施させるためのコンピュータ可読プログラム命令をその上に有する（１つまたは複数の）コンピュータ可読ストレージ媒体を含んでよい。
【００５９】
コンピュータ可読ストレージ媒体は、命令実行デバイスによる使用のための命令を保持し、記憶できる有形のデバイスとすることができる。コンピュータ可読ストレージ媒体は、例えば、以下には限定されないが、電子ストレージ・デバイス、磁気ストレージ・デバイス、光ストレージ・デバイス、電磁ストレージ・デバイス、半導体ストレージ・デバイス、または前述のものの任意の適切な組み合わせであってよい。コンピュータ可読ストレージ媒体のより具体的な例の非網羅的なリストは、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ：ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、リード・オンリ・メモリ（ＲＯＭ：ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、消去可能プログラマブル・リード・オンリ・メモリ（ＥＰＲＯＭ：ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙまたはフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ：ｓｔａｔｉｃ  ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、ポータブル・コンパクト・ディスク・リード・オンリ・メモリ（ＣＤ−ＲＯＭ：ｐｏｒｔａｂｌｅ  ｃｏｍｐａｃｔ  ｄｉｓｃ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、デジタル多用途ディスク（ＤＶＤ：ｄｉｇｉｔａｌ  ｖｅｒｓａｔｉｌｅ  ｄｉｓｋ）、メモリ・スティック、フレキシブルディスク、パンチ・カードまたはその上に記録された命令を有する溝中の隆起構造のような機械的に符号化されたデバイス、および前述のものの任意の適切な組み合わせを含む。コンピュータ可読ストレージ媒体は、本明細書では、それ自体が一時的な信号、例えば、電波、または他の自由に伝搬する電磁波、導波路もしくは他の送信媒体を通して伝搬する電磁波（例えば、光ファイバ・ケーブルを通過する光パルス）、あるいはワイヤを通して送信される電気信号などであると解釈されるべきではない。
【００６０】
本明細書に記載されるコンピュータ可読プログラム命令を、コンピュータ可読ストレージ媒体からそれぞれのコンピューティング／処理デバイスへ、あるいはネットワーク、例えば、インターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワークもしくは無線ネットワークまたはそれらのすべてを介して外部コンピュータまたは外部ストレージ・デバイスへダウンロードできる。ネットワークは、銅送信ケーブル、光送信ファイバ、無線送信、ルータ、ファイヤウォール、スイッチ、ゲートウェイ・コンピュータもしくはエッジ・サーバまたはそれらのすべてを備えてよい。各コンピューティング／処理デバイス中のネットワーク・アダプタ・カードまたはネットワーク・インターフェースは、コンピュータ可読プログラム命令をネットワークから受信して、それらのコンピュータ可読プログラム命令をそれぞれのコンピューティング／処理デバイス内のコンピュータ可読ストレージ媒体に記憶するために転送する。
【００６１】
本実施形態のオペレーションを実施するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ：ｉｎｓｔｒｕｃｔｉｏｎ−ｓｅｔ−ａｒｃｈｉｔｅｃｔｕｒｅ）命令、マシン命令、マシン依存命令、マイクロコード、ファームウェア命令、状態設定データ、または、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋などのようなオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語または同様のプログラミング言語のような従来の手続き型プログラミング言語を含む、１つ以上のプログラミング言語の任意の組み合わせで書かれたソース・コードまたはオブジェクト・コードのいずれかであってよい。コンピュータ可読プログラム命令は、全体的にユーザのコンピュータ上で、部分的にユーザのコンピュータ上で、スタンド・アロン・ソフトウェア・パッケージとして、部分的にユーザのコンピュータ上かつ部分的にリモート・コンピュータ上で、あるいは全体的にリモート・コンピュータまたはサーバ上で実行してよい。後者のシナリオにおいては、リモート・コンピュータが、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）を含む、任意のタイプのネットワークを通してユーザのコンピュータへ接続されてもよく、あるいは外部コンピュータへ接続が（例えば、インターネット・サービス・プロバイダを用い、インターネットを通して）行われてもよい。いくつかの実施形態においては、本実施形態の態様を行うために、例えば、プログラマブル・ロジック回路素子、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ：ｆｉｅｌｄ−ｐｒｏｇｒａｍｍａｂｌｅ  ｇａｔｅ  ａｒｒａｙ）、またはプログラマブル・ロジック・アレイ（ＰＬＡ：ｐｒｏｇｒａｍｍａｂｌｅ  ｌｏｇｉｃ  ａｒｒａｙｓ）を含む、電子回路素子が、コンピュータ可読プログラム命令の状態情報を利用し、電子回路素子をパーソナライズすることによって、コンピュータ可読プログラム命令を実行してよい。
【００６２】
本実施形態の態様は、本発明の実施形態による方法、装置（システム）、およびコンピュータ・プログラム製品のフローチャート説明図もしくはブロック図またはその両方を参照して本明細書に記載される。フローチャート説明図もしくはブロック図またはその両方の各ブロック、およびフローチャート説明図もしくはブロック図またはその両方におけるブロックの組み合わせをコンピュータ可読プログラム命令によって実装できることが理解されるであろう。
【００６３】
これらのコンピュータ可読プログラム命令は、コンピュータまたは他のプログラマブル・データ処理装置のプロセッサを介して実行するそれらの命令がフローチャートもしくはブロック図またはその両方の１つあるいは複数のブロックにおいて指定された機能／動作を実装するための手段を作り出すような、マシンを作り出すために、汎用コンピュータ、専用コンピュータ、または他のプログラマブル・データ処理装置のプロセッサのプロセッサへ提供されてよい。これらのコンピュータ可読プログラム命令は、コンピュータ可読ストレージ媒体に記憶されてもよく、その中に記憶された命令を有するコンピュータ可読ストレージ媒体がフローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて指定された機能／動作の態様を実装する命令を含んだ製造品を備えるような、特定の仕方で機能するようにコンピュータ、プログラマブル・データ装置、もしくは他のデバイスまたはそれらのすべてに命令できる。
【００６４】
コンピュータ可読プログラム命令は、コンピュータ、他のプログラマブル装置、または他のデバイス上で実行する命令がフローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて指定された機能／動作を実装するような、コンピュータ実装プロセスを作り出すための一連のオペレーション・ステップがコンピュータ、他のプログラマブル装置、または他のデバイス上で行われるようにするために、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイス上へロードされてもよい。
【００６５】
図中のフローチャートおよびブロック図は、本発明の様々な実施形態によるシステム、方法、およびコンピュータ・プログラム製品の可能な実装のアーキテクチャ、機能性、およびオペレーションを図示する。この点において、フローチャートまたはブロック図中の各ブロックは、指定されたロジック機能（単数または複数）を実装するための１つ以上の実行可能な命令を備えるモジュール、セグメント、または命令の一部を表してよい。いくつかの代わりの実装では、ブロック中に記された機能が図中に記された順序以外で発生してよい。例えば、連続して示される２つのブロックが、実際には、実質的に同時に実行されてもよく、または関与する機能性によっては、ブロックがときには逆の順序で実行されてもよい。ブロック図もしくはフローチャート説明図またはその両方の各ブロック、およびブロック図もしくはフローチャート説明図またはその両方におけるブロックの組み合わせを、指定された機能または動作を行うかあるいは専用ハードウェアとコンピュータ命令との組み合わせを実施する専用ハードウェア・ベースのシステムによって実装できることにも気付くであろう。
【００６６】
図１０は、ある実施形態に従って、ストレージ・コントローラ１０２もしくはホスト１０４、１０６、または他の計算デバイス中に含まれてよいいくつかの要素を示すブロック図を図示する。システム１０００は、ある実施形態においては少なくとも１つのプロセッサ１００４を含む回路素子１００２を備えてよい。システム１０００は、メモリ１００６（例えば、揮発性メモリ・デバイス）、およびストレージ１００８も含んでよい。ストレージ１００８は、不揮発性メモリ・デバイス（例えば、ＥＥＰＲＯＭ、ＲＯＭ、ＰＲＯＭ、フラッシュ、ファームウェア、プログラマブル・ロジックなど）、磁気ディスク・ドライブ、光ディスク・ドライブ、テープ・ドライブなどを含んでよい。ストレージ１００８は、内部ストレージ・デバイス、接続型ストレージ・デバイスもしくはネットワーク・アクセス可能なストレージ・デバイスまたはそれらのすべてを備えてよい。システム１０００は、メモリ１００６中へロードされて、プロセッサ１００４または回路素子１００２によって実行されてよいコード１０１２を含んだプログラム・ロジック１０１０を含んでよい。ある実施形態において、コード１０１２を含んだプログラム・ロジック１０１０は、ストレージ１００８に記憶されてよい。ある他の実施形態において、プログラム・ロジック１０１０は、回路素子１００２中に実装されてよい。システム１０００中のコンポーネントのうちの１つ以上は、バスを介して、または他の結合もしくは接続１０１４を介して通信してよい。それゆえに、図１０は、プログラム・ロジック１０１０を他の要素から分離して示すが、メモリ１００６もしくは回路素子１００２またはその両方にプログラム・ロジック１０１０が実装されてもよい。
【００６７】
ある実施形態は、人によるコンピューティング命令または自動処理統合コンピュータ可読コード（automated processing integrating computer-readable code）をコンピューティング・システム中へデプロイするための方法を対象とし、このコードをコンピューティング・システムと組み合わせて、記載される実施形態のオペレーションを行うことが可能である。
【００６８】
「ある１つの実施形態（ａｎ  ｅｍｂｏｄｉｍｅｎｔ）」、「実施形態（ｅｍｂｏｄｉｍｅｎｔ）」、「複数の実施形態（ｅｍｂｏｄｉｍｅｎｔｓ）」、「その実施形態（ｔｈｅ  ｅｍｂｏｄｉｍｅｎｔ）」、「それらの複数の実施形態（ｔｈｅ  ｅｍｂｏｄｉｍｅｎｔｓ）」、「いくつかの実施形態（ｓｏｍｅ  ｅｍｂｏｄｉｍｅｎｔｓ）」、および「一実施形態（ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ）」の用語は、明示的に別に指定されない限り「本発明（単数または複数）の１つ以上の（しかしすべてではない）実施形態」を意味する。
【００６９】
「含んでいる（ｉｎｃｌｕｄｉｎｇ）」、「備えている（ｃｏｍｐｒｉｓｉｎｇ）」、「有している（ｈａｖｉｎｇ）」の用語およびそれらの変形は、明示的に別に指定されない限り、「含んでいるが限定されない」を意味する。
【００７０】
項目の列挙されたリストは、明示的に別に指定されない限り、これらの項目のいずれかまたはすべてが相互排他的であることを示唆しない。
【００７１】
「ａ（１つの）」、「ａｎ（１つの）」、および「ｔｈｅ（前記）」の用語は、明確に別に指示されない限り、「１つ以上の」を意味する。
【００７２】
互いに通信しているデバイスは、明示的に別に指示されない限り、互いに連続的に通信している必要はない。加えて、互いに通信しているデバイスは、直接的にまたは１つ以上の仲介物を介して間接的に通信してもよい。
【００７３】
互いに通信しているいくつかのコンポーネントを用いた実施形態の記載は、すべてのかかるコンポーネントが必要なことを示唆しない。逆に、本発明の広範囲にわたる可能な実施形態を示すために種々の随意的なコンポーネントが記載される。
【００７４】
さらに、プロセス・ステップ、方法ステップ、アルゴリズムまたは同様のものがシーケンス順に記載されうるが、かかるプロセス、方法およびアルゴリズムが交互順に作動するように構成されてもよい。言い換えれば、記載されうるステップのいずれかのシーケンスまたは順序は、それらのステップがその順序で行われるという必要条件を必ずしも示さない。本明細書に記載されるプロセスのステップは、実用的ないずれかの順序で行われてよい。さらに、いくつかのステップが同時に行われてもよい。
【００７５】
単一のデバイスまたは物品が本明細書に記載されるときに、すぐに明らかになるのは、単一のデバイス／物品の代わりに１つより多いデバイス／物品が（それらが協働するか否かにかかわらず）用いられてよいことである。同様に、１つより多いデバイスまたは物品が（それらが協働するか否かにかかわらず）本明細書に記載されるときに、すぐに明らかになるのは、単一のデバイスまたは物品が１つより多いデバイスまたは物品の代わりに用いられてもよく、あるいは示される数のデバイスまたはプログラムの代わりに、異なる数のデバイス／物品が用いられてもよいことである。ある１つのデバイスの機能性もしくは特徴またはその両方がかかる機能性／特徴を有するとして明示的には記載されない１つ以上の他のデバイスによって代わりに具現されてもよい。従って、本発明の他の実施形態は、デバイスそれ自体を含む必要がない。
【００７６】
図に示された少なくともあるオペレーションは、ある一定の順序で発生するある事象を示す。代わりの実施形態においては、あるオペレーションが異なる順序で行われてもよく、修正され、または削除されてもよい。そのうえ、上記のロジックにステップが追加されてもよく、記載される実施形態に依然として適合する。さらに、本明細書に記載されるオペレーションは、順次に発生してもよく、またはあるオペレーションが並列に発生してもよい。なお、さらに、オペレーションは、単一の処理ユニットによって、または分散された処理ユニットによって行われてよい。
【００７７】
本発明の様々な実施形態の先の記載は、例示および説明の目的で提示された。この記載が網羅的であること、または本発明を開示される通りの形態に限定することは意図されない。上記の教示を踏まえて、多くの修正および変更が可能である。意図されるのは、本発明の範囲が、この詳細な記載によってではなく、むしろそれに添付された特許請求の範囲によって限定されることである。上記の明細書、例およびデータは、本発明の構成物の製造および使用の完全な記載を提供する。本発明の範囲から逸脱することなく、本発明の多くの実施形態を作ることができるため。
【図１】
2020531959.tif 000003
【図２】
2020531959.tif 000004
【図３】
2020531959.tif 000005
【図４】
2020531959.tif 000006
【図５】
2020531959.tif 000007
【図６】
2020531959.tif 000008
【図７】
2020531959.tif 000009
【図８】
2020531959.tif 000010
【図９】
2020531959.tif 000011
【図１０】
2020531959.tif 000012
【国際調査報告】
2020531959.tif 000013
2020531959.tif 000014