(57)【要約】【課題】階層間のデータ移動を効率化できるようにする。【解決手段】実施形態によれば、階層化ストレージシステムのストレージコントローラは、ホストからのアクセス要求が第１の論理ブロックを含む１つ以上の論理ブロックへのアクセスを指定し、且つ前記第１の論理ブロックが第１の論理エクステントに含まれていて、且つ前記第１の論理エクステントが前記第２のストレージ装置内のｑ個の物理エクステントが割り当てられたｑ個の論理エクステントを含むエクステントグループに属している場合、前記ｑ個の物理エクステントのデータを、上位階層に位置付けられるストレージ装置内の空きのｑ個の物理エクステントに移動する。【選択図】図２
2017167819.tif 000002
【特許請求の範囲】
【請求項１】
各々が第１の数の物理ブロックから構成される複数の物理エクステントを有する第１の記憶領域を含み、且つ上位階層に位置付けられる第１のストレージ装置と、
各々が前記第１の数と同数の物理ブロックから構成される複数の物理エクステントを有する第２の記憶領域を含み、且つ前記第１のストレージ装置よりもアクセス速度が低く、且つ下位階層に位置付けられる第２のストレージ装置と、
前記第１及び第２のストレージ装置へのアクセスを制御するストレージコントローラと  を具備する階層化ストレージシステムであって、
前記ストレージコントローラは、
各々が前記物理ブロックと同サイズの複数の論理ブロックから構成される仮想化された記憶領域を含む論理ユニットを構築し、前記階層化ストレージシステムを利用するホスト計算機に前記論理ユニットを提供する構成管理部と、
前記ホスト計算機からのアクセス要求に応じて、前記第１もしくは第２のストレージ装置からデータをリードし、または前記第１もしくは第２のストレージ装置にデータをライトする入出力制御部と、
前記論理ユニット内の前記仮想化された記憶領域を、各々が前記第１の数と同数の論理ブロックから構成される複数の論理エクステントを有する記憶領域として管理する入出力管理部と、
前記複数の論理エクステント内のそれぞれ異なる２つの論理エクステントから構成される組み合わせ毎に、対応する２つの論理エクステントのアクセスに関する結合の強さを、当該対応する２つの論理エクステントが順にアクセスされる度合いを示す結合度に基づいて管理し、且つ相互に結合関係を有する組み合わせの系列毎に対応する系列に含まれている論理エクステントの集合をエクステントグループとして管理するグループ管理部と、
前記アクセス要求が第１の論理ブロックを含む１つ以上の論理ブロックへのアクセスを指定し、且つ前記第１の論理ブロックが第１の論理エクステントに含まれていて、且つ前記第１の論理エクステントが前記第２のストレージ装置内のｑ個の物理エクステントが割り当てられたｑ個の論理エクステントを含むエクステントグループに属している場合、前記ｑ個の物理エクステントのデータを、前記第１のストレージ装置内の空きのｑ個の物理エクステントに移動し、且つ前記ｑ個の論理エクステントに割り当てられるｑ個の物理エクステントを、前記データの移動元のｑ個の物理エクステントから、前記データの移動先のｑ個の物理エクステントに変更する階層化制御部と
を具備する階層化ストレージシステム。
【請求項２】
前記入出力管理部は、前記複数の論理エクステントそれぞれへのアクセスの状況を示すアクセス統計値を取得し、
前記グループ管理部は、エクステントグループ毎のアクセス統計値を、対応するエクステントグループに属する全ての論理エクステントのアクセス統計値に基づいて決定し、
前記階層化制御部は、前記第１のストレージ装置内の空きの物理エクステントの数が前記ｑに対してｒだけ不足する場合、いずれのエクステントグループにも属さない論理エクステントのうち、前記第１のストレージ装置内のそれぞれの物理エクステントが割り当てられる論理エクステントのアクセス統計値、及び前記第１のストレージ装置内のそれぞれの物理エクステントの集合が割り当てられる論理エクステントの集合から構成されるエクステントグループのアクセス統計値の昇順に、前記第１のストレージ装置から前記第２のストレージ装置へデータが移動されるべき少なくともｒ個の物理エクステントに対応する、いずれのエクステントグループにも属さない１つ以上の論理エクステント及び／または１つ以上のエクステントグループを選択して、選択された１つ以上の論理エクステント及び／または１つ以上のエクステントグループ内の全ての論理エクステントに割り当てられた、前記第１のストレージ装置内の前記少なくともｒ個の物理エクステントのデータを、前記１のストレージ装置内の前記少なくともｒ個の物理エクステントと同数の前記第２のストレージ装置内の空きの物理エクステントに移動することにより、前記第１のストレージ装置内の空きの物理エクステントの数を少なくともｒ増やす
請求項１記載の階層化ストレージシステム。
【請求項３】
前記入出力管理部は、前記対応するエクステントグループに属する全ての論理エクステントのアクセス統計値の最大値または平均値を、前記対応するエクステントグループのアクセス統計値として決定する請求項２記載の階層化ストレージシステム。
【請求項４】
前記入出力管理部は、前記複数の論理エクステントそれぞれへのアクセスの状況を、前記複数の論理エクステントそれぞれのアクセス統計値と最終アクセス時刻とを用いて管理し、
前記グループ管理部は、前記エクステントグループの各々を構成する論理エクステントの最終アクセス時刻のうち最も新しい最終アクセス時刻を、前記エクステントグループの各々の最終アクセス時刻として用い、
前記階層化制御部は、アクセス統計値が同一の複数の選択候補が存在する場合、最終アクセス時刻がより古い選択候補ほど、選択される順位を上げる
請求項２及び請求項３のいずれか一項に記載の階層化ストレージシステム。
【請求項５】
前記グループ管理部は、エクステントグループそれぞれを構成する論理エクステントの数に基づき、第２の数を超える論理エクステントから構成される第１のエクステントグループを検出して、前記第１のエクステントグループ内で最小の結合度を持つ、第２及び第３の論理エクステントの組み合わせを検出し、前記第１のエクステントグループを、前記第２の論理エクステントを含む第２のエクステントグループと、前記第３の論理エクステントを含む第３のエクステントグループとに再グループ分けする請求項１乃至請求項４のいずれか一項に記載の階層化ストレージシステム。
【請求項６】
前記グループ管理部は、前記組み合わせ毎の結合度を前記最小の結合度で正規化し、且つ前記正規化された最小の結合度を結合無しを示す値に置き換える請求項５記載の階層化ストレージシステム。
【請求項７】
前記第２の数は、前記第１のストレージ装置においてデータが配置可能な物理エクステントの数に基づいて決定される請求項５及び請求項６のいずれか一項に記載の階層化ストレージシステム。
【請求項８】
ｐが２以上の整数であるものとすると、前記１つ以上の論理ブロックが前記論理ユニット内で連続するｐ個の論理ブロックであり、且つ前記ｐ個の論理ブロックの一部が前記第１の論理エクステントに含まれていて、且つ前記ｐ個の論理ブロックの他の一部が第４の論理エクステントに含まれているならば、前記第１の論理エクステントと前記第４の論理エクステントとの組み合わせの結合度をインクリメントする請求項５乃至請求項７のいずれか一項に記載の階層化ストレージシステム。
【請求項９】
前記複数の論理エクステントの各々に対応付けて、対応する論理エクステントが属するエクステントグループを示すエクステントグループ識別子、アクセス順に関し、当該対応する論理エクステントに先行する論理エクステントを示す前方リンクエクステント識別子、アクセス順に関し、当該対応する論理エクステントに後続する論理エクステントを示す後方リンクエクステント識別子、当該対応する論理エクステントのアクセス統計値、及び当該対応する論理エクステントが最後にアクセスされた最終アクセス時刻を示す最終アクセス時刻情報を保持するエクステント管理テーブルを更に具備し、
前記入出力管理部は、前記アクセス要求で指定されたアクセス範囲に対応する少なくとも１つの論理エクステントに対応付けられたアクセス統計値及び最終アクセス時刻情報を、前記アクセス要求に応じて更新し、
前記グループ管理部は、前記指定された前記アクセス範囲に対応する少なくとも１つの論理エクステントに対応付けられたエクステントグループ識別子、前方リンクエクステント識別子及び後方リンクエクステント識別子を、前記アクセス要求に応じて更新する
請求項４乃至請求項８のいずれか一項に記載の階層化ストレージシステム。
【請求項１０】
前記組み合わせ毎に、対応する組み合わせの結合度を保持する結合管理テーブルを更に具備する請求項９記載の階層化ストレージシステム。
【請求項１１】
各々が第１の数の物理ブロックから構成される複数の物理エクステントを有する第１の記憶領域を含み、且つ上位階層に位置付けられる第１のストレージ装置と、各々が前記第１の数と同数の物理ブロックから構成される複数の物理エクステントを有する第２の記憶領域を含み、且つ前記第１のストレージ装置よりもアクセス速度が低く、且つ下位階層に位置付けられる第２のストレージ装置とを具備する階層化ストレージシステムにおいて、前記第１及び第２のストレージ装置へのアクセスを制御するストレージコントローラであって、
各々が前記物理ブロックと同サイズの複数の論理ブロックから構成される仮想化された記憶領域を含む論理ユニットを構築し、前記階層化ストレージシステムを利用するホスト計算機に前記論理ユニットを提供する構成管理部と、
前記ホスト計算機からのアクセス要求に応じて、前記第１もしくは第２のストレージ装置からデータをリードし、または前記第１もしくは第２のストレージ装置にデータをライトする入出力制御部と、
前記論理ユニット内の前記仮想化された記憶領域を、各々が前記第１の数と同数の論理ブロックから構成される複数の論理エクステントを有する記憶領域として管理する入出力管理部と、
前記複数の論理エクステント内のそれぞれ異なる２つの論理エクステントから構成される組み合わせ毎に、対応する２つの論理エクステントのアクセスに関する結合の強さを、当該対応する２つの論理エクステントが順にアクセスされる度合いを示す結合度に基づいて管理し、且つ相互に結合関係を有する組み合わせの系列毎に対応する系列に含まれている論理エクステントの集合をエクステントグループとして管理するグループ管理部と、
前記アクセス要求が第１の論理ブロックを含む１つ以上の論理ブロックへのアクセスを指定し、且つ前記第１の論理ブロックが第１の論理エクステントに含まれていて、且つ前記第１の論理エクステントが前記第２のストレージ装置内のｑ個の物理エクステントが割り当てられたｑ個の論理エクステントを含むエクステントグループに属している場合、前記ｑ個の物理エクステントのデータを、前記第１のストレージ装置内の空きのｑ個の物理エクステントに移動し、且つ前記ｑ個の論理エクステントに割り当てられるｑ個の物理エクステントを、前記データの移動元のｑ個の物理エクステントから、前記データの移動先のｑ個の物理エクステントに変更する階層化制御部と
を具備するストレージコントローラ。
【請求項１２】
各々が第１の数の物理ブロックから構成される複数の物理エクステントを有する第１の記憶領域を含む第１のストレージ装置、及び、各々が前記第１の数と同数の物理ブロックから構成される複数の物理エクステントを有する第２の記憶領域を含み、且つ前記第１のストレージ装置よりもアクセス速度が低い第２のストレージ装置へのアクセスを制御するストレージコントローラであって、各々が前記物理ブロックと同サイズの複数の論理ブロックから構成される仮想化された記憶領域を含む論理ユニットを構築し、前記第１のストレージ装置及び前記第２のストレージ装置を具備する階層化ストレージシステムを利用するホスト計算機に前記論理ユニットを提供するストレージコントローラにおいて、前記第１及び第２のストレージ装置を、それぞれ上位階層及び下位階層として階層化するための階層化制御方法であって、
前記ホスト計算機からのアクセス要求に応じて、前記第１もしくは第２のストレージ装置からデータをリードし、または前記第１もしくは第２のストレージ装置にデータをライトし、
前記論理ユニット内の前記仮想化された記憶領域を、各々が前記第１の数と同数の論理ブロックから構成される複数の論理エクステントを有する記憶領域として管理し、
前記複数の論理エクステント内のそれぞれ異なる２つの論理エクステントから構成される組み合わせ毎に、対応する２つの論理エクステントのアクセスに関する結合の強さを、当該対応する２つの論理エクステントが順にアクセスされる度合いを示す結合度に基づいて管理し、
相互に結合関係を有する組み合わせの系列毎に対応する系列に含まれている論理エクステントの集合をエクステントグループとして管理し、
前記アクセス要求が第１の論理ブロックを含む１つ以上の論理ブロックへのアクセスを指定し、且つ前記第１の論理ブロックが第１の論理エクステントに含まれていて、且つ前記第１の論理エクステントが前記第２のストレージ装置内のｑ個の物理エクステントが割り当てられたｑ個の論理エクステントを含むエクステントグループに属している場合、前記ｑ個の物理エクステントのデータを、前記第１のストレージ装置内の空きのｑ個の物理エクステントに移動し、且つ前記ｑ個の論理エクステントに割り当てられるｑ個の物理エクステントを、前記データの移動元のｑ個の物理エクステントから、前記データの移動先のｑ個の物理エクステントに変更する
階層化制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、階層化ストレージシステム、ストレージコントローラ、及び階層化制御方法に関する。
【背景技術】
【０００２】
近年、アクセス速度の異なる第１及び第２のストレージ装置を備えたストレージシステムが開発されている。ここで、第１のストレージ装置のアクセス速度及び記憶容量は高速で小容量であり、第２のストレージ装置のアクセス速度及び記憶容量は、第１のストレージ装置のそれと比較して低速で大容量であるものとする。ストレージシステムは、第１及び第２のストレージ装置を、それぞれ上位階層及び下位階層として階層的に組み合わせることにより実現される。このような技術はストレージ階層化技術とも呼ばれ、当該ストレージ階層化技術を適用するストレージシステムは階層化ストレージシステムとも呼ばれる。
【０００３】
階層化ストレージシステムでは、データが配置（格納）されるべき階層（ストレージ装置）が、当該データの特性に応じて決定・変更される。具体的には、アクセス頻度の高いデータは上位階層（第１のストレージ装置）に配置され、アクセス頻度の低いデータは下位階層（第２のストレージ装置）に配置される。このような配置（つまり階層化）により、階層化ストレージシステムの高パフォーマンス化と低コスト化とを両立することができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第５３６２１４５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
階層化ストレージシステムにおける階層化は、一般に自動的に行われる。この自動的な階層化のためにストレージコントローラは、例えば、階層化ストレージシステムにおけるアクセスの状況を、エクステントと呼ばれるデータ集合を単位に監視する。エクステントは一般に、データ管理（データアクセス）の基本サイズ（いわゆるブロックサイズ）よりも大きいサイズを有する。エクステントそれぞれへのアクセスの状況は、アクセス回数のようなアクセス統計値により表される。
【０００６】
ストレージコントローラは、例えば定期的に、エクステントそれぞれのアクセス統計値に基づいて、当該エクステントそれぞれのアクセス頻度に関する評価を行う。そしてストレージコントローラは、この定期的な評価結果に基づいて、下位階層から上位階層へのデータの移動（再配置）、及び／または、上位階層から下位階層へのデータの移動をエクステントを単位に行う。しかし、定期的なアクセス頻度評価に基づく階層間のデータ移動は、オーバーヘッドが大きく、処理に時間を費やす。
【０００７】
本発明が解決しようとする課題は、階層間のデータ移動を効率化できる階層化ストレージシステム、ストレージコントローラ、及び階層化制御方法を提供することにある。
【課題を解決するための手段】
【０００８】
実施形態によれば、階層化ストレージシステムは、第１のストレージ装置と、ストレージコントローラとを含む。前記第１のストレージ装置は、各々が第１の数の物理ブロックから構成される複数の物理エクステントを有する第１の記憶領域を含み、且つ上位階層に位置付けられる。前記第２のストレージ装置は、各々が前記第１の数と同数の物理ブロックから構成される複数の物理エクステントを有する第２の記憶領域を含み、且つ前記第１のストレージ装置よりもアクセス速度が低く、且つ下位階層に位置付けられる。前記ストレージコントローラは、前記第１及び第２のストレージ装置へのアクセスを制御し、構成管理部と、入出力制御部と、入出力管理部と、グループ管理部と、階層化制御部とを含む。前記構成管理部は、各々が前記物理ブロックと同サイズの複数の論理ブロックから構成される仮想化された記憶領域を含む論理ユニットを構築し、前記階層化ストレージシステムを利用するホスト計算機に前記論理ユニットを提供する。前記入出力制御部は、前記ホスト計算機からのアクセス要求に応じて、前記第１もしくは第２のストレージ装置からデータをリードし、または前記第１もしくは第２のストレージ装置にデータをライトする。前記入出力管理部は、前記論理ユニット内の前記仮想化された記憶領域を、各々が前記第１の数と同数の論理ブロックから構成される複数の論理エクステントを有する記憶領域として管理する。前記グループ管理部は、前記複数の論理エクステント内のそれぞれ異なる２つの論理エクステントから構成される組み合わせ毎に、対応する２つの論理エクステントのアクセスに関する結合の強さを、当該対応する２つの論理エクステントが順にアクセスされる度合いを示す結合度に基づいて管理し、且つ相互に結合関係を有する組み合わせの系列毎に対応する系列に含まれている論理エクステントの集合をエクステントグループとして管理する。前記階層化制御部は、前記アクセス要求が第１の論理ブロックを含む１つ以上の論理ブロックへのアクセスを指定し、且つ前記第１の論理ブロックが第１の論理エクステントに含まれていて、且つ前記第１の論理エクステントが前記第２のストレージ装置内のｑ個の物理エクステントが割り当てられたｑ個の論理エクステントを含むエクステントグループに属している場合、前記ｑ個の物理エクステントのデータを、前記第１のストレージ装置内の空きのｑ個の物理エクステントに移動し、且つ前記ｑ個の論理エクステントに割り当てられるｑ個の物理エクステントを、前記データの移動元のｑ個の物理エクステントから、前記データの移動先のｑ個の物理エクステントに変更する。
【図面の簡単な説明】
【０００９】
【図１】実施形態に係る階層化ストレージシステムを含むコンピュータシステムの典型的なハードウェア構成を示すブロック図。
【図２】図１に示されるストレージコントローラの典型的な機能構成を主として示すブロック図。
【図３】同実施形態における、物理エクステントと物理ブロックとの典型的な関係を示す図。
【図４】同実施形態における、論理エクステントと論理ブロックとの典型的な関係を示す図。
【図５】図２に示されるアドレス変換テーブルのデータ構造例を示す図。
【図６】図２に示されるエクステント管理テーブルのデータ構造例を示す図。
【図７】図２に示される結合管理テーブルのデータ構造例を示す図。
【図８】同実施形態におけるアクセス処理の典型的な手順を示すフローチャート。
【図９】図８に示されるアクセス処理に含まれているテーブル更新処理の典型的な手順を示すフローチャート。
【図１０】図９に示されるテーブル更新処理に含まれている第１のテーブル更新処理の典型的な手順を示すフローチャート。
【図１１】図９に示されるテーブル更新処理に含まれている第２のテーブル更新処理の典型的な手順を示すフローチャート。
【図１２】第１のアクセス要求に応じてテーブル更新処理が実行された後のエクステント管理テーブルの例を示す図。
【図１３】第１のアクセス要求に応じてテーブル更新処理が実行された後の結合管理テーブルの例を示す図。
【図１４】第２のアクセス要求に応じてテーブル更新処理が実行された後のエクステント管理テーブルの例を示す図。
【図１５】第２のアクセス要求に応じてテーブル更新処理が実行された後の結合管理テーブルの例を示す図。
【図１６】第３のアクセス要求に応じてテーブル更新処理が実行された後のエクステント管理テーブルの例を示す図。
【図１７】第３のアクセス要求に応じてテーブル更新処理が実行された後の結合管理テーブルの例を示す図。
【図１８】第４のアクセス要求に応じてテーブル更新処理が実行された後のエクステント管理テーブルの例を示す図。
【図１９】第４のアクセス要求に応じてテーブル更新処理が実行された後の結合管理テーブルの例を示す図。
【図２０】図８に示されるアクセス処理に含まれているデータ移動元決定処理の典型的な手順を示すフローチャート。
【図２１】図８に示されるアクセス処理に含まれている空き領域確保処理の典型的な手順を示すフローチャート。
【図２２】同実施形態の変形例における再グループ分け処理の典型的な手順を示すフローチャート。
【図２３】拡張されたエクステントグループの構成と、当該拡張されたエクステントグループ内のアクセスが連続する論理エクステントの対毎の結合度との例を、結合管理テーブルの例と共に示す図。
【図２４】同変形例における第２の前処理実行前後の結合管理テーブルの例を対比して示す図。
【図２５】同変形例における第３の前処理実行前後の結合管理テーブルの例を対比して示す図。
【図２６】第３の前処理実行直後における結合管理テーブルの例を示すと共に、再グループ分け前後のエクステントグループの例を対比して示す図。
【発明を実施するための形態】
【００１０】
以下、実施の形態につき図面を参照して説明する。  
図１は一つの実施形態に係る階層化ストレージシステムを含むコンピュータシステムの典型的なハードウェア構成を示すブロック図である。図１に示されるコンピュータシステムは、階層化ストレージシステム１０及びホストコンピュータ（以下、ホストと称する）２０から構成される。つまりコンピュータシステムは、単一のホストを備えている。しかし、コンピュータシステムが、複数のホストを備えていても良い。
【００１１】
ホスト２０は、階層化ストレージシステム１０が提供する論理ユニットを自身の外部ストレージ装置として利用する。論理ユニットは、論理ディスクまたは論理ボリュームとも呼ばれ、仮想化された記憶領域（つまり、論理記憶領域）を含む。ホスト２０は、例えば、ホストインタフェースバス３０を介して階層化ストレージシステム１０（より、詳細には、階層化ストレージシステム１０のストレージコントローラ１３）と接続されている。本実施形態においてホストインタフェースバス３０は、ファイバチャネル（ＦＣ）である。しかしホストインタフェースバス３０が、スモールコンピュータシステムインタフェース（ＳＣＳＩ）、シリアルアタッチドＳＣＳＩ（ＳＡＳ）、インターネットＳＣＳＩ（ｉＳＣＳＩ）、イーサネット（登録商標）、或いはシリアルＡＴアタッチメント（ＳＡＴＡ）のような、ＦＣ以外のインタフェースバスであっても構わない。またホスト２０が、ストレージエリアネットワーク（ＳＡＮ）、インターネット或いはイントラネットのようなネットワークを介して階層化ストレージシステム１０と接続されていても良い。
【００１２】
ホスト２０は、サーバ、或いはクライアントパーソナルコンピュータのような物理計算機である。ホスト２０内では、階層化ストレージシステム１０が提供する論理ユニット内のデータにアクセスするためのアプリケーションプログラムが動作する。このアプリケーションプログラムに従い、ホスト２０はホストインタフェースバス３０を介して階層化ストレージシステム１０を利用する。
【００１３】
階層化ストレージシステム１０は、高速ストレージ装置（第１のストレージ装置）１１と、低速ストレージ装置（第２のストレージ装置）１２と、ストレージコントローラ１３とを備えている。高速ストレージ装置１１及び低速ストレージ装置１２は、ストレージインタフェースバス１４を介してストレージコントローラ１３と接続されている。本実施形態においてストレージインタフェースバス１４はＦＣ（ファイバチャネル）である。しかしストレージインタフェースバス１４が、ホストインタフェースバス３０と同様に、ＦＣ以外のインタフェースバスであっても構わない。
【００１４】
高速ストレージ装置１１は、例えば、ハードディスクドライブ（ＨＤＤ）との互換性を有し、且つＨＤＤよりもアクセス速度が高速な（つまりアクセス性能が優れた）単一のソリッドステートドライブ（ＳＳＤ）から構成される。一方、低速ストレージ装置１２は、例えば単一のＨＤＤから構成される。
【００１５】
したがって本実施形態において低速ストレージ装置１２は、高速ストレージ装置１１よりもアクセス速度が低い（つまりアクセス性能が劣る）。これに対して低速ストレージ装置１２の記憶容量は、高速ストレージ装置１１のそれよりも大きいものとする。本実施形態では、高速ストレージ装置１１は上位階層（高速階層、第１の階層）のストレージ装置として、低速ストレージ装置１２は下位階層（低速階層、第２の階層）のストレージ装置として、それぞれ用いられる。なお、階層化ストレージシステム１０が、低速ストレージ装置１２よりも更に低速（低階層）のストレージ装置（第３の階層のストレージ装置）を備えていても良い。
【００１６】
なお、本実施形態とは異なって、高速ストレージ装置１１が、フラッシュメモリを搭載したフラッシュアレイストレージ装置或いはオールフラッシュアレイと呼ばれるストレージ装置であっても構わない。同様に、低速ストレージ装置１２が、複数のＨＤＤから構成されるアレイ構成のストレージ装置であっても構わない。
【００１７】
また、高速ストレージ装置１１が、ＦＣ用のＨＤＤのような高速ＨＤＤから構成され、低速ストレージ装置１２が、ＳＡＴＡ用のＨＤＤのような低速ＨＤＤから構成されても構わない。また低速ストレージ装置１２が、ブルーレイディスク（登録商標）ドライブ、或いはＤＶＤ（登録商標）ドライブのような光学式ディスクドライブ、或いはテープ装置であっても構わない。また、テープ装置が低速ストレージ装置１２として用いられる場合、光学式ディスクドライブが高速ストレージ装置１１として用いられても構わない。
【００１８】
ストレージコントローラ１３は、ホスト２０から与えられる、論理アドレスを用いたアクセス（リードアクセスまたはライトアクセス）の要求（入出力要求）を受信して、要求されたアクセス（入出力）を実行する。このアクセスの実行に際し、ストレージコントローラ１３は、周知のアドレス変換機能を用いて、論理アドレスを物理アドレスに変換する。論理アドレスは、論理ユニット内のアドレスを指す。物理アドレスは、高速ストレージ装置１１または低速ストレージ装置１２に含まれていて、且つ論理アドレスに対応付けられている記憶領域の物理位置を示す。ストレージコントローラ１３は、物理アドレスに基づいて、高速ストレージ装置１１または低速ストレージ装置１２にアクセスする。
【００１９】
ストレージコントローラ１３は、ホストインタフェースコントローラ（以下、ＨＩＦコントローラと称する）１３１と、ストレージインタフェースコントローラ（以下、ＳＩＦコントローラと称する）１３２と、メモリ１３３と、ローカルＨＤＤ１３４と、ＣＰＵ１３５とを備えている。
【００２０】
ＨＩＦコントローラ１３１は、当該ＨＩＦコントローラ１３１とホスト２０との間のデータ転送（データ転送プロトコル）を制御する。ＨＩＦコントローラ１３１は、ホストからのアクセス要求を受信し、当該アクセス要求に対する応答を返信する。アクセ要求は、論理ユニットからデータをリードすること、或いは当該論理ユニットにデータをライトすること（つまり、論理ユニットへのアクセス）を指定する。ＨＩＦコントローラ１３１は、ホスト２０からアクセス要求を受信すると、当該アクセス要求を、ＣＰＵ１３５に伝達する。アクセス要求を受け取ったＣＰＵ１３５は、当該アクセス要求を処理する。
【００２１】
ＳＩＦコントローラ１３２は、ＣＰＵ１３５が受信したホスト２０からのアクセス要求に対応するアクセスコマンド（より詳細には、高速ストレージ装置１１または低速ストレージ装置１２に対するリードコマンドまたはライトコマンド）を、ＣＰＵ１３５から受信する。ＳＩＦコントローラ１３２は、受信されたアクセスコマンドに応じて、高速ストレージ装置１１または低速ストレージ装置１２へのアクセスを実行する。
【００２２】
メモリ１３３は、ＤＲＡＭのような、書き換えが可能な揮発性メモリである。メモリ１３３の記憶領域の一部は、ローカルＨＤＤ１３４からロードされる制御プログラムの少なくとも一部を格納するのに用いられる。メモリ１３３の記憶領域の他の一部は、ローカルＨＤＤ１３４からロードされるアドレス変換テーブル１３３１、エクステント管理テーブル１３３２、及び結合管理テーブル１３３３（図２）を格納するのに用いられる。
【００２３】
ローカルＨＤＤ１３４には、制御プログラムが格納されている。ＣＰＵ１３５は、ストレージコントローラ１３が起動されたときにイニシャルプログラムローダ（ＩＰＬ）を実行することにより、ローカルＨＤＤ１３４に格納されている制御プログラムの少なくとも一部をメモリ１３３にロードする。ＩＰＬは、ＲＯＭまたはフラッシュＲＯＭのような不揮発性メモリに格納されている。
【００２４】
ＣＰＵ１３５は、例えば、マイクロプロセッサのようなプロセッサである。ＣＰＵ１３５は、メモリ１３３にロードされた制御プログラムに従い、構成管理部１３５１、入出力（ＩＯ）制御部１３５２、入出力（ＩＯ）管理部１３５３、グループ管理部１３５４、及び階層化制御部１３５５（図２）として機能する。つまりＣＰＵ１３５は、メモリ１３３に格納されている制御プログラムを実行することで、階層化ストレージシステム１０全体を制御する。
【００２５】
本実施形態においてストレージコントローラ１３は、図１に示されているようにホスト２０から独立して備えられている。しかし、ストレージコントローラ１３が、ホスト２０に内蔵されていても構わない。この場合、ストレージコントローラ１３（より詳細には、ストレージコントローラ１３の機能）が、ホスト２０の有するオペレーティングシステム（ＯＳ）の機能の一部を用いて実現されていても構わない。
【００２６】
また、ストレージコントローラ１３が、ホスト２０のカードスロットに装着して用いられるカードに備えられていても構わない。また、ストレージコントローラ１３の一部がホスト２０に内蔵され、当該ストレージコントローラ１３の残りがカードに備えられていても構わない。また、ホスト２０と、ストレージコントローラ１３と、高速ストレージ装置１１及び低速ストレージ装置１２の一部または全部とが、１つの筐体に収められていても構わない。
【００２７】
図２は、図１に示されるストレージコントローラ１３の典型的な機能構成を主として示すブロック図である。ストレージコントローラ１３は、構成管理部１３５１、ＩＯ制御部１３５２、ＩＯ管理部１３５３、グループ管理部１３５４及び階層化制御部１３５５を含む。構成管理部１３５１、ＩＯ制御部１３５２、ＩＯ管理部１３５３、グループ管理部１３５４及び階層化制御部１３５５の少なくとも１つがハードウェアによって実現されても構わない。
【００２８】
構成管理部１３５１は、階層化ストレージシステム１０のストレージ構成を管理する。この構成管理は、高速ストレージ装置１１及び低速ストレージ装置１２の記憶領域に基づいて、論理ユニットを構築し、当該論理ユニットをホスト２０に提供することを含む。本実施形態では、論理ユニットの記憶領域（論理記憶領域）は当該論理ユニットの管理のために、論理ブロックと呼ばれる一定サイズの小領域に分割される。つまり論理ユニットは、複数の論理ブロックから構成される。
【００２９】
一方、高速ストレージ装置１１及び低速ストレージ装置１２の記憶領域（物理記憶領域）は、物理エクステントと呼ばれる、論理ブロックより大きなサイズの領域に分割される。各物理エクステントは、物理ブロックと呼ばれる、論理ブロックと同サイズの小領域に更に分割される。つまり、高速ストレージ装置１１及び低速ストレージ装置１２の記憶領域は複数の物理エクステントから構成され、各物理エクステントは一定数（第１の数）の連続する物理ブロックから構成される。
【００３０】
本実施形態において論理ユニットの記憶領域は、論理エクステントと呼ばれる、物理エクステントと同サイズの領域にも分割される。つまり論理ユニットの記憶領域は、複数の論理エクステントからも構成される。各論理エクステントは、物理エクステントを構成する物理ブロックの数（つまり、第１の数）と同数の連続する論理ブロックから構成される。つまり、各論理エクステントの境界は、論理ブロックの境界に一致する。
【００３１】
物理エクステント及び論理エクステントのサイズ（つまりエクステントサイズ）は、例えば４キロバイト（ＫＢ）、即ち４，０９６バイト（Ｂ）である。一方、物理ブロック及び論理ブロックのサイズ（つまりブロックサイズ）は、例えば５１２バイト（Ｂ）である。つまり、第１の数は８であり、物理エクステント（論理エクステント）は、８個の物理ブロック（論理ブロック）から構成される。しかし、エクステントサイズ及びブロックサイズは、それぞれ、４ＫＢ及び５１２Ｂに限らず、第１の数も８に限らない。
【００３２】
ＩＯ制御部１３５２は、ホスト２０からのデータリードのためのアクセス要求に応じて、高速ストレージ装置１１または低速ストレージ装置１２からデータをリードする、またＩＯ制御部１３５２は、ホスト２０からのデータライトのためのアクセス要求に応じて、高速ストレージ装置１１または低速ストレージ装置１２にデータをライトする。
【００３３】
ＩＯ管理部１３５３は、ホスト２０からのアクセス要求に対応するＩＯ（アクセス）を管理する。ＩＯ管理部１３５３は、主としてこのＩＯ管理のために、論理ユニットの記憶領域を前記複数の論理エクステントに分割する。つまりＩＯ管理部１３５３は、論理ユニットの記憶領域を、複数の論理エクステントを有する記憶領域として管理する。ＩＯ管理は、高速ストレージ装置１１及び低速ストレージ装置１２の記憶領域内の物理ブロックを、論理ユニットの記憶領域内の論理ブロックに割り当てること、及び当該割り当ての状態を管理することを含む。この割り当ての状態の管理には、アドレス変換テーブル１３３１が用いられる。なお、論理エクステントへの分割が、構成管理部１３５１によってなされても構わない。ＩＯ管理は更に、各論理エクステントへのアクセスの状況を示すアクセス（ＩＯ）統計値（以下、アクセスカウントと称する）を取得することを含む。論理エクステント毎のアクセスカウントは、エクステント管理テーブル１３３２を用いて管理される。
【００３４】
グループ管理部１３５４は、前記複数の論理エクステント内のそれぞれ異なる２つの論理エクステントから構成される組み合わせ毎に、対応する２つの論理エクステントのアクセスに関する結合の強さを、当該対応する２つの論理エクステントが順にアクセスされる度合いを示す結合度に基づいて管理する。組み合わせ毎の結合度は、結合管理テーブル１３３３を用いて管理される。グループ管理部１３５４は更に、相互に結合関係を有する組み合わせの系列毎に対応する系列に含まれている論理エクステントの集合をエクステントグループとして管理する。
【００３５】
階層化制御部１３５５は、低速ストレージ装置１２内のアクセスの頻度の高い物理エクステント内のデータを、高速ストレージ装置１１内の物理エクステントに移動（再配置）する。また階層化制御部１３５５は、高速ストレージ装置１１内のアクセスの頻度の低い物理エクステント内のデータを、低速ストレージ装置１２内の物理エクステントに移動する。
【００３６】
図３は、本実施形態における、物理エクステントと物理ブロックとの典型的な関係を示す。図３に示されるように、高速ストレージ装置１１の記憶領域は、ｍ個の物理エクステントＰＥ０，ＰＥ１，…，ＰＥｍ−１に分割される。つまり高速ストレージ装置１１は、ｍ個の物理エクステントＰＥ０乃至ＰＥｍ−１を備えている。また、高速ストレージ装置１１の記憶領域は、ｍ×ｎ個の物理ブロックＰＢ０＿０，…，ＰＢ０＿ｎ−１，ＰＢ１＿０，…，ＰＢ１＿ｎ−１，…，ＰＢｍ−１＿０，…，ＰＢｍ−１＿ｎ−１に分割される。つまり高速ストレージ装置１１はｍ×ｎ個の物理ブロックＰＢ０＿０，…，ＰＢ０＿ｎ−１，ＰＢ１＿０，…，ＰＢ１＿ｎ−１，…，ＰＢｍ−１＿０，…，ＰＢｍ−１＿ｎ−１を備えている。
【００３７】
ここで、高速ストレージ装置１１におけるｉ番目（ｉ＝０，１，…，ｍ−１）の物理エクステントを物理エクステントＰＥｉと表記する。物理エクステントＰＥｉは、高速ストレージ装置１１の記憶領域において連続するｎ個の物理ブロックＰＢｉ＿０乃至ＰＢｉ＿ｎ−１から構成される。換言するならば、物理ブロックＰＢｉ＿０乃至ＰＢｉ＿ｎ−１は、物理エクステントＰＥｉを構成する。ｎは前述の第１の数を示し、エクステントサイズが４ＫＢ、ブロックサイズが５１２Ｂである本実施形態では８である。
【００３８】
上述の高速ストレージ装置１１における物理エクステントと物理ブロックとの関係は、低速ストレージ装置１２においても同様である。必要ならば、上述の物理エクステントと物理ブロックとの関係に関する説明において、高速ストレージ装置１１を低速ストレージ装置１２に、記号ｍを他の記号（例えば、ｄ）に、それぞれ置き換えられたい。記号ｄは、低速ストレージ装置１２内の物理エクステントの数を示す。
【００３９】
高速ストレージ装置１１内の物理エクステントＰＥｉは、例えば、物理エクステント番号０ｉによって示される。つまり物理エクステント番号０ｉは、物理エクステントＰＥｉを識別するための識別子である。物理エクステント番号０ｉは、例えば、ストレージ番号０と内部物理エクステント番号ｉとの結合から構成される。ストレージ番号０は、高速ストレージ装置１１を示す識別子（ストレージ識別子）として用いられる。内部物理エクステント番号ｉは、ストレージ番号０によって示されるストレージ装置（つまり、高速ストレージ装置１１）内のｉ番目の物理エクステント（つまり、物理エクステントＰＥｉ）を示す識別子（エクステント識別子）として用いられる。
【００４０】
物理エクステントＰＥｉ内のｊ番目の物理ブロックＰＢｉ＿ｊ（ｊ＝０，１，…，ｎ−１）は、物理エクステント番号０ｉとオフセットＯＦＳＴｊとによって示される。オフセットＯＦＳＴｊは、物理エクステントＰＥｉにおけるｊ番目の物理ブロック（つまり、物理ブロックＰＢｉ＿ｊ）の相対位置を示す。
【００４１】
同様に、低速ストレージ装置１２内のｋ番目の物理エクステントＰＥｋ（ｋ＝０，１，…，ｈ−１）は、物理エクステント番号１ｋによって示される。物理エクステント番号１ｋは、ストレージ番号１と内部物理エクステント番号ｋとの結合から構成される。ストレージ番号１は、低速ストレージ装置１２を示す識別子として用いられる。内部物理エクステント番号ｋは、ストレージ番号１によって示されるストレージ装置（つまり、低速ストレージ装置１２）内のｋ番目の物理エクステント（つまり、物理エクステントＰＥｋ）を示す識別子として用いられる。
【００４２】
物理エクステントＰＥｋ内のｊ番目の物理ブロックＰＢｋ＿ｊは、物理エクステント番号１ｋとオフセットＯＦＳＴｊとによって示される。上述の物理エクステント番号０ｉ及び１ｋは、高速ストレージ装置１１及び低速ストレージ装置１２を用いて提供される物理記憶領域全体（物理アドレス空間）においてユニークである。
【００４３】
図４は、本実施形態における、論理エクステントと論理ブロックとの典型的な関係を示す。図４には論理ユニットＬＵが示されている。論理ユニットＬＵの記憶領域（より詳細には、仮想的な記憶領域）は、ｕ×ｎ個の論理ブロックＬＢ０＿０，…，ＬＢ０＿ｎ−１，ＬＢ１＿０，…，ＬＢ１＿ｎ−１，…，ＬＢｕ−１＿０，…，ＬＢｕ−１＿ｎ−１に分割される。つまり論理ユニットＬＵは、ｕ×ｎ個の論理ブロックＬＢ０＿０，…，ＬＢ０＿ｎ−１，ＬＢ１＿０，…，ＬＢ１＿ｎ−１，…，ＬＢｕ−１＿０，…，ＬＢｕ−１＿ｎ−１を備えている。また、論理ユニットＬＵの記憶領域は、ｕ個の論理エクステントＬＥ０，…，ＬＥｕ−１に分割される。つまり論理ユニットＬＵは、ｕ個の論理エクステントＬＥ０乃至ＬＥｕ−１を備えている。
【００４４】
ここで、論理ユニットＬＵ内のｓ番目（ｓ＝０，１，…，ｕ−１）の論理エクステントを論理エクステントＬＥｓと表記する。論理エクステントＬＥｓは、論理ユニットＬＵの記憶領域において連続するｎ個の論理ブロックＬＢｓ＿０乃至ＬＢｓ＿ｎ−１から構成される。換言するならば、論理ブロックＬＢｓ＿０乃至ＬＢｓ＿ｎ−１は、論理エクステントＬＥｓを構成する。論理ブロックＬＢｓ＿０乃至ＬＢｓ＿ｎ−１は、それぞれ、論理ユニットＬＵ内のｓ×ｎ番目乃至（ｓ＋１）×ｎ−１番目の論理ブロックである。
【００４５】
本実施形態においてストレージコントローラ１３は、論理ユニットＬＵ内の論理ブロックＬＢ０＿０，…，ＬＢ０＿ｎ−１，ＬＢ１＿０，…，ＬＢ１＿ｎ−１，…，ＬＢｕ−１＿０，…，ＬＢｕ−１＿ｎ−１、及び論理ユニットＬＵ内の論理エクステントＬＥ０乃至ＬＥｕ−１を認識できる。これに対してホスト２０は、論理ブロックＬＢ０＿０，…，ＬＢ０＿ｎ−１，ＬＢ１＿０，…，ＬＢ１＿ｎ−１，…，ＬＢｕ−１＿０，…，ＬＢｕ−１＿ｎ−１のみを認識できる。しかし、構成管理部１３５１が、論理エクステントのサイズを含む論理エクステントに関する定義内容をホスト２０に通知することにより、当該ホスト２０が論理ユニットＬＵ内の論理エクステントＬＥ０乃至ＬＥｕ−１を認識できるようにしても構わない。
【００４６】
ホスト２０は、論理ユニットＬＵ内のｔ番目（ｔ＝０，１，…，ｕ×ｎ−１）の論理ブロックを、論理ユニット番号ＬＵＮと論理ブロックアドレスＬＢＡｔ（ＬＢＡ＝ＬＢＡｔ＝ｔ）とによって認識（指定）する。論理ユニット番号ＬＵＮ（例えば０）は論理ユニットＬＵを示す識別子として用いられ、論理ブロックアドレスＬＢＡｔは論理ユニット（より詳細には、論理ユニット番号ＬＵＮによって示される論理ユニットＬＵ）内のｔ番目の論理ブロックを示すアドレスとして用いられる。
【００４７】
論理ユニットＬＵ内のｔ番目の論理ブロック（つまり、論理ブロックアドレスがＬＢＡｔ＝ｔの論理ブロック）は、ｔ／ｎの商をｖ（ｖ＝０，１，…，ｕ−１）、剰余をｗ（ｗ＝０，１，…，ｎ−１）と表記するならば、ＬＢｖ＿ｗ（論理ブロックＬＢｖ＿ｗ）のように表される。ＬＢｖ＿ｗは、論理ユニットＬＵ内のｖ番目の論理エクステントにおけるｗ番目の論理ブロックを示す。明らかなように、ｔはｖ×ｎ＋ｗ＝（ｖ＋１）×ｎ−（ｎ−ｗ）に一致する。本実施形態においてＩＯ管理部１３５３は、論理ブロックアドレスＬＢＡｔ（＝ｔ）をｎで除することにより、当該論理ブロックアドレスＬＢＡｔで指定される論理ブロック（ＬＢｖ＿ｗ）が属する論理エクステントＬＥｖ、及び当該論理ブロックの論理エクステントＬＥｖ内の相対位置ｗを特定する。
【００４８】
図５は、図２に示されるアドレス変換テーブル１３３１のデータ構造例を示す。アドレス変換テーブル１３３１は、例えば、構成管理部１３５１が提供する全ての論理ユニット内の全ての論理ブロックに対応付けられたエントリの群を有している。アドレス変換テーブル１３３１の各エントリは、論理ユニット番号（ＬＵＮ）フィールド、論理ブロックアドレス（ＬＢＡ）フィールド、論理エクステント番号（ＬＥＮ）フィールド、物理エクステント番号（ＰＥＮ）フィールド及びオフセットフィールドを有している。
【００４９】
ＬＵＮフィールドは、対応する論理ブロックを含む論理ユニットを示す論理ユニット番号を保持するのに用いられる。ＬＢＡフィールドは、対応する論理ブロックのアドレス（論理ブロックアドレス）を保持するのに用いられる。
【００５０】
ＬＥＮフィールドは、対応する論理ブロックを含む論理エクステントを識別するための識別子としての論理エクステント番号を保持するのに用いられる。論理エクステント番号は、構成管理部１３５１によって提供される全ての論理ユニットが属する論理記憶領域全体（論理アドレス空間）においてユニークである。論理エクステント番号は、論理ユニット番号と内部論理エクステント番号との結合から構成される。内部論理エクステント番号は、対応する論理ブロックを含む論理ユニットにおいてユニークであり、当該論理ユニットにおいて当該対応する論理ブロックを含む論理エクステントを識別するための識別子である。
【００５１】
ＰＥＮフィールドは、物理エクステント番号を保持するのに用いられる。この物理エクステント番号は、対応する論理ブロックを含む論理エクステントに割り当てられる物理エクステント（つまり、対応する論理ブロックに割り当てられる物理ブロックを含む物理エクステント）を示す。オフセットフィールドは、オフセット（オフセットデータ）を保持するのに用いられる。このオフセットは、対応する論理ブロックに割り当てられる物理ブロックの、当該物理ブロックを含む物理エクステントにおける相対位置を示す。
【００５２】
図６は、図２に示されるエクステント管理テーブル１３３２のデータ構造例を示す。エクステント管理テーブル１３３２は、例えば、構成管理部１３５１が提供する全ての論理ユニット内の全ての論理エクステントに対応付けられたエントリの群を有している。エクステント管理テーブル１３３２の各エントリは、論理エクステント番号（ＬＥＮ）フィールド、エクステントグループ番号（ＥＧＮ）フィールド、前方リンクエクステント（ＰＬＥ）フィールド、後方リンクエクステント（ＳＬＥ）フィールド、アクセスカウント（ＡＣ）フィールド及び最終アクセス時刻（ＬＡＴ）フィールドを有している。
【００５３】
ＬＥＮフィールドは、対応する論理エクステントを示す論理エクステント番号を保持するのに用いられる。ＥＧＮフィールドは、対応する論理エクステントが属するエクステントグループを識別するための識別子としてのエクステントグループ番号を保持するのに用いられる。図６に示されるエクステント管理テーブル１３３２の例では、全てのエントリのＥＧＮフィールドに値０が設定されている。ＥＧＮフィールドにおける値０は初期値であり、対応する論理エクステントがエクステントグループに属していないことを示す。そのため本実施形態では、エクステントグループ番号０の使用は禁止されているものとする。しかし、ＥＧＮフィールドの初期値は０に限るものではなく、使用可能なエクステントグループ番号以外の特定値であれば良い。
【００５４】
ＰＬＥフィールド及びＳＬＥフィールドは、それぞれ、前方リンクエクステントの論理エクステント番号及び後方リンクエクステントの論理エクステント番号をそれぞれ保持するのに用いられる。前方リンクエクステントとは、アクセス順に関し、対応する論理エクステントに先行する直近の論理エクステントを指す。後方リンクエクステントとは、アクセス順に関し、対応する論理エクステントに後続する直近の論理エクステントを指す。
【００５５】
図６に示されるエクステント管理テーブル１３３２の例では、全てのエントリのＰＬＥフィールド及びＳＬＥフィールドに、値０が設定されている。ＰＬＥフィールド及びＳＬＥフィールドにおける値０は初期値であり、アクセス順に関し、それぞれ対応する論理エクステントに先行論理エクステント及び後続する論理エクステントが存在しないことを示す。そこで本実施形態では、論理エクステント番号０の使用は禁止されているものとする。なお、ＰＬＥフィールド及びＳＬＥフィールドの初期値は０に限るものではなく使用可能な論理エクステント番号以外の特定値であれば良い。
【００５６】
ＰＬＥフィールドに、初期値及び論理エクステント番号以外の特定値、例えば−１が設定されている場合、当該特定値（−１）は、アクセス順に関し、対応する論理エクステントに先行する論理エクステントが存在しないことを示す。同様に、ＳＬＥフィールドに、−１が設定されている場合、当該特定値（−１）は、アクセス順に関し、対応する論理エクステントに後続する論理エクステントが存在しないことを示す。なお、ＰＬＥフィールド及びＳＬＥフィールドに、初期値及び論理エクステント番号以外のそれぞれ異なる特定値（例えば−１及び−２）が設定されても構わない。
【００５７】
ＡＣフィールドは、対応する論理エクステントがアクセスされた回数（アクセス頻度）を示すアクセスカウントを保持するのに用いられる。ＬＡＴフィールドは、対応する論理エクステントが最後にアクセスされた時刻（日時）を示す最終アクセス時刻データを保持するのに用いられる。
【００５８】
エクステント管理テーブル１３３２のそれぞれのエントリは次のように初期設定される。まず、それぞれのエントリに対応付けられた論理エクステントの論理エクステント番号が、当該それぞれのエントリのＬＥＮフィールドに設定される。それぞれのエントリの他の各フィールドには、例えば０が設定される。図６は、初期化されたエクステント管理テーブル１３３２を示す。
【００５９】
図７は、図２に示される結合管理テーブル１３３３のデータ構造例を示す。結合管理テーブル１３３３は、行列の構造を有している。即ち、結合管理テーブル１３３３は、複数の行項目及び複数の列項目を有している。複数の行項目には、それぞれ固有の論理エクステント番号が設定される。複数の列項目には、それぞれ固有の論理エクステント番号が設定される。行項目の数は列項目の数に一致する。また、本実施形態では、全行項目における論理エクステント番号の並び順は、全列項目における論理エクステント番号の並び順に一致する。
【００６０】
図７において、Ａ，Ｂ，Ｃ，Ｄ及びＥは、それぞれ論理エクステントＡ，Ｂ，Ｃ，Ｄ及びＥの論理エクステント番号を示す。ここで、行列における第ｘ行（ｘ＝１，２，…）及び第ｙ行（ｙ＝１，２，…，但しｙ≠ｘ）が、それぞれエクステント番号Ｘ（Ｘ＝Ａ，Ｂ，Ｃ，Ｄ，Ｅ，…）及びＹ（Ｙ＝Ａ，Ｂ，Ｃ，Ｄ，Ｅ，…，但しＹ≠Ｘ）に対応し、したがって行列における第ｘ列及び第ｙ列も、それぞれエクステント番号Ｘ及びＹに対応しているものとする。エクステント番号Ｘ及びＹで示される論理エクステントを、それぞれ論理エクステントＸ及びＹと表記する。
【００６１】
行列における第ｘ行、第ｙ列の位置（ｘ，ｙ）、つまり結合管理テーブル１３３３における第ｘ行、第ｙ列のエントリ（ｘ，ｙ）は、例えば、論理エクステントＹが論理エクステントＸに先行または後続してアクセスされた回数を保持するのに用いられる。同様に、行列における第ｙ行、第ｘ列の位置（ｙ，ｘ）、つまり結合管理テーブル１３３３における第ｙ行、第ｘ列のエントリ（ｙ，ｘ）は、例えば、論理エクステントＸが論理エクステントＹに先行または後続してアクセスされた回数を保持するのに用いられる。
【００６２】
エントリ（ｘ，ｙ）及び（ｙ，ｘ）に保持される回数は一致する。この回数は、論理エクステントＸ及びＹが、その順、または、その逆順に続けてアクセスされる度合いを示す。この度合い（回数）は、連続するアクセスに関する論理エクステントＸ及びＹの関連性（つまり、結合）の強さを示す。そこで、この回数を結合度と称する。エントリ（ｘ，ｙ）及び（ｙ，ｘ）内の結合度は、論理エクステントＸに続いて論理エクステントＹがアクセスされる場合、或いは論理エクステントＹに続いて論理エクステントＸがアクセスされる場合、グループ管理部１３５４によって１インクリメントされる。
【００６３】
結合管理テーブル１３３３のエントリ（ｘ，ｙ）及び（ｙ，ｘ）の初期値（つまり初期結合度）は、例えば０である。図７に示される結合管理テーブル１３３３において、空欄のエントリは、結合度０が設定されたエントリを示す。必要ならば、結合管理テーブル１３３３における空欄のエントリに数値０を加えられたい。
【００６４】
本実施形態では、結合管理テーブル１３３３は行列の構造を有している。しかし、結合管理テーブル１３３３が、結合関係を有する全ての論理エクステントの組み合わせに対応付けられた結合度の配列（つまり、リスト構造）を有していても構わない。
【００６５】
次に、本実施形態の動作について、アクセス処理を例に図８を参照して説明する。図８はアクセス処理の典型的な手順を示すフローチャートである。まず、ホスト２０から階層化ストレージシステム１０のストレージコントローラ１３に、ホストインタフェースバス３０を介してアクセス要求が発行されたものとする。
【００６６】
ストレージコントローラ１３のＨＩＦコントローラ１３１は、ホスト２０によって発行されたアクセス要求をホストインタフェースバス３０から受領する。アクセス要求は、論理ユニット番号ＬＵＮ、論理ブロックアドレスＬＢＡｔ及びデータ転送サイズを含む。データ転送サイズは、転送（アクセス）されるべき論理ブロックの数を示す。データ転送サイズが例えばＮである場合、アクセス要求は、論理ブロックアドレスＬＢＡｔから始まる連続するＮ論理ブロックの範囲へのアクセスを指定する。
【００６７】
ストレージコントローラ１３のＩＯ管理部１３５３は、受領されたアクセス要求によって指定される論理ブロック範囲に対応する論理エクステント範囲を、次のように特定する（ステップＳ１）。まず、ＩＯ管理部１３５３は、アドレス変換テーブル１３３１において、指定論理ブロック範囲内のそれぞれの論理ブロックを示す論理ユニット番号及び論理ブロックアドレスの組に対応付けられたエントリを参照する。そしてＩＯ管理部１３５３は、指定論理ブロック範囲内のそれぞれの論理ブロックに対応付けられた論理エクステント番号によって示される論理エクステントを特定する。これによりＩＯ管理部１３５３は、指定論理ブロック範囲に対応する論理エクステント範囲を特定する。特定された論理エクステント範囲は、ホスト２０からのアクセス要求で指定された論理ブロック範囲に対応することから、ホスト２０からのアクセス要求で（間接的に）指定されたと称することもできる。
【００６８】
論理エクステント範囲が特定されると（ステップＳ１）、グループ管理部１３５４が起動される。グループ管理部１３５４は、エクステント管理テーブル１３３２及び結合管理テーブル１３３３を、特定された論理エクステント範囲に基づいて更新するためのテーブル更新処理を、ＩＯ管理部１３５３と協同して実行する（ステップＳ２）。
【００６９】
以下、テーブル更新処理（ステップＳ２）の詳細について、図９を参照して説明する。図９はテーブル更新処理の典型的な手順を示すフローチャートである。まずグループ管理部１３５４は、メモリ１３３内の特定領域を参照する（ステップＳ２１）。この特定領域は、後述するように、図８のフローチャートで示されるアクセス処理で最後に処理された論理エクステントの論理エクステント番号を格納するのに用いられる。
【００７０】
次にグループ管理部１３５４は、メモリ１３３内の特定領域に、有効な論理エクステント番号が格納されているかを判定する（ステップＳ２２）。もし、有効な論理エクステント番号が格納されていないならば（ステップＳ２２のＮｏ）、グループ管理部１３５４は、今回のアクセス処理が、エクステント管理テーブル１３３２及び結合管理テーブル１３３３の初期化後に最初に実行されるアクセス処理であると判断する。この場合、グループ管理部１３５４は、特定された論理エクステント範囲内の先頭の論理エクステントをＬＥ１（論理エクステントＬＥ１）として選択する（ステップＳ２３）。そしてグループ管理部１３５４は、第１のテーブル更新処理を実行して（ステップＳ２４）、図９のフローチャートに従うテーブル更新処理を終了する。
【００７１】
これに対し、特定領域に、有効な論理エクステント番号（ＬＥＮｚ）が格納されているならば（ステップＳ２２のＹｅｓ）、グループ管理部１３５４は、今回のアクセス処理に先行するアクセス処理が既に実行されており、ＬＥＮｚは、当該先行するアクセス処理において最後に処理（アクセス）された論理エクステントを示している判断する。この場合、グループ管理部１３５４は、ＬＥＮｚによって示される論理エクステントをＬＥ１として選択する（ステップＳ２５）。またグループ管理部１３５４は、特定された論理エクステント範囲内の先頭の論理エクステントをＬＥ２（論理エクステントＬＥ２）として選択する（ステップＳ２６）。そしてグループ管理部１３５４は、第２のテーブル更新処理を実行して（ステップＳ２７）、図９のフローチャートに従うテーブル更新処理を終了する。
【００７２】
以下、第１のテーブル更新処理（ステップＳ２４）の詳細について、図１０を参照して説明する。図１０は第１のテーブル更新処理の典型的な手順を示すフローチャートである。なお、図９のステップＳ２３が、第１のテーブル更新処理の先頭で実行されても良い。
【００７３】
まずグループ管理部１３５４は、特定された論理エクステント範囲内に、現在の論理エクステントＬＥ１（つまり、図９のステップＳ２３で選択された論理エクステント）の次の論理エクステントが存在するかを判定する（ステップＳ３１）。もし、特定された論理エクステント範囲が、複数の論理エクステントを含む場合、次の論理エクステントは存在する（ステップＳ３１のＹｅｓ）。この場合、グループ管理部１３５４は、次の論理エクステントを、ＬＥ２として選択する（ステップＳ３２）。ここで、ＬＥ１及びＬＥ２の論理エクステント番号（ＬＥＮ）を、それぞれＬＥＮ＿ＬＥ１及びＬＥＮ＿ＬＥ２と表記する。また、ＬＥ１及びＬＥ２に対応付けられたエクステント管理テーブル１３３２のエントリを、それぞれ、エントリＥＭＴＥ＿ＬＥ１及びＥＭＴＥ＿ＬＥ２と表記する。
【００７４】
次にグループ管理部１３５４は、エントリＥＭＴＥ＿ＬＥ１のＥＧＮフィールド、ＰＬＥフィールド及びＳＬＥフィールドの内容（初期値０）を、それぞれ、先頭のＥＧＮ（＝１）、−１及びＬＥＮ＿ＬＥ２に変更する。（ステップＳ３３）。なお、先頭のＥＧＮ以外のＥＧＮが用いられても構わない。一方、ＩＯ管理部１３５３は、エントリＥＭＴＥ＿ＬＥ１のＡＣフィールド及びＬＡＴフィールドの内容を更新する（ステップＳ３４）。即ちＩＯ管理部１３５３は、ＡＣフィールドの内容（初期値０）を１インクリメントし、ＬＡＴフィールドの内容（初期値０）を現在時刻を示すように更新する。
【００７５】
次にグループ管理部１３５４は、エントリＥＭＴＥ＿ＬＥ２のＥＧＮフィールド、ＰＬＥフィールド及びＳＬＥフィールドの内容（初期値０）を、それぞれ、先頭ＥＧＮ（＝１）、ＬＥＮ＿ＬＥ１及び−１に変更する（ステップＳ３５）。グループ管理部１３５４はまた、エントリＥＭＴＥ＿ＬＥ２のＡＣフィールド及びＬＡＴフィールドの内容を更新する（ステップＳ３６）。グループ管理部１３５４は更に、ＬＥ１及びＬＥ２の組み合わせに対応付けられた結合管理テーブル１３３３のエントリの内容（結合度）を１インクリメントする（ステップＳ３７）。
【００７６】
次にグループ管理部１３５４は、特定された論理エクステント範囲内に次の論理エクステント（つまり、現在のＬＥ２の次の論理エクステント）が存在するかを判定する（ステップＳ３８）。もし、次の論理エクステントが存在しないならば（ステップＳ３８のＮｏ）、グループ管理部１３５４は、図１０のフローチャートに従う第１のテーブル更新処理（図９のステップＳ２４）を終了する。つまりグループ管理部１３５４は、図９のフローチャートに従うテーブル更新処理（図８のステップＳ２）を終了する。
【００７７】
これに対して、次の論理エクステントが存在するならば（ステップＳ３８のＹｅｓ）、グループ管理部１３５４は現在のＬＥ２を新たなＬＥ１として選択する（ステップＳ３９）。またグループ管理部１３５４は、特定された論理エクステント範囲内の次の論理エクステント（つまり、新たなＬＥ１の次の論理エクステント）を新たなＬＥ２として選択する（ステップＳ４０）。
【００７８】
次にグループ管理部１３５４は、新たなＬＥ１に対応付けられたエントリＥＭＴＥ＿ＬＥ１（つまり、前回のＬＥ２に対応付けられたエントリＥＭＴＥ＿ＬＥ２）のＳＬＥフィールドの内容を、−１からＬＥＮ＿ＬＥ２に変更する（ステップＳ４１）。そしてグループ管理部１３５４はステップＳ３５に戻る。
【００７９】
一方、ステップＳ３１において、次の論理エクステントが存在しないと判定されたものとする。つまり、特定された論理エクステント範囲が単一の論理エクステントのみを含むものとする。この場合（ステップＳ３１のＮｏ）、グループ管理部１３５４は、エントリＥＭＴＥ＿ＬＥ１のＥＧＮフィールド、ＰＬＥフィールド及びＳＬＥフィールドの内容を、それぞれ、先頭のＥＧＮ（＝１）、−１及び−１に変更する（ステップＳ４２）。一方、ＩＯ管理部１３５３は、ステップＳ３４と同様に、エントリＥＭＴＥ＿ＬＥ１のＡＣフィールド及びＬＡＴフィールドの内容を更新する（ステップＳ４３）。その後、グループ管理部１３５４は、図１０のフローチャートに従う第１のテーブル更新処理（図９のステップＳ２４）を終了する。
【００８０】
次に、第２のテーブル更新処理（図９のステップＳ２７）の詳細について、図１１を参照して説明する。図１１は第２のテーブル更新処理の典型的な手順を示すフローチャートである。なお、図９のステップＳ２５及びＳ２６が、第２のテーブル更新処理の先頭で実行されても良い。
【００８１】
まずグループ管理部１３５４は、現在のＬＥ１及びＬＥ２に対応付けられたエントリＥＭＴＥ＿ＬＥ１及びＥＭＴＥ＿ＬＥ２から、エントリＥＭＴＥ＿ＬＥ１のＳＬＥフィールドの内容ＬＥＮ＿ＳＬＥ（ＬＥ１）とエントリＥＭＴＥ＿ＬＥ２のＰＬＥフィールドの内容ＬＥＮ＿ＰＬＥ（ＬＥ２）とを取得する（ステップＳ５１）。次にグループ管理部１３５４は、エントリＥＭＴＥ＿ＬＥ１のＳＬＥフィールドの内容を、ＬＥＮ＿ＬＥ２に変更する（ステップＳ５２）。
【００８２】
次にグループ管理部１３５４は、エントリＥＭＴＥ＿ＬＥ２のＥＧＮフィールド及びＳＬＥフィールドの内容に応じて、当該内容を変更する（ステップＳ５３）。以下、ステップＳ５３について詳細に説明する。
【００８３】
ステップＳ５３においてグループ管理部１３５４は、エントリＥＭＴＥ＿ＬＥ２のＥＧＮフィールドの内容が、ＬＥ１が属するエクステントグループ（ＥＧα）を示すＥＧＮ＿ＬＥ１（＝ＥＧＮα）とは異なるかを判定する。もし、異なるならば、グループ管理部１３５４は、ＥＧＮフィールドの内容をＥＧＮαに変更する。またステップＳ５３においてグループ管理部１３５４は、エントリＥＭＴＥ＿ＬＥ２のＳＬＥフィールドの内容が初期値０であるならば、当該ＳＬＥフィールドの内容を−１に変更する。
【００８４】
ここで、エントリＥＭＴＥ＿ＬＥ２のＥＧＮフィールドの内容がＥＧＮαとは異なるものの、初期値０以外であるものとする。つまり、ＬＥ２がＥＧαとは異なるエクステントグループＥＧβに属しているものとする。この場合、グループ管理部１３５４は、エントリＥＭＴＥ＿ＬＥ２のＳＬＥフィールドの内容が初期値０（及び−１）以外の値、つまりＥＧβに属する論理エクステントＬＥγの論理エクステント番号であったとしても、当該ＳＬＥフィールドの内容を−１に変更する。そしてグループ管理部１３５４は、ＬＥ２及びＬＥγの結合を解消するために、ＬＥ２及びＬＥγの組み合わせに対応付けられた結合管理テーブル１３３３のエントリの内容（結合度）を、初期値０に変更する。
【００８５】
グループ管理部１３５４は、上述のステップＳ５３を実行するとステップＳ５４に進む。ステップＳ５４においてグループ管理部１３５４は、エントリＥＭＴＥ＿ＬＥ２のＰＬＥフィールドの内容を、ＬＥＮ＿ＬＥ１に変更する。一方、ＩＯ管理部１３５３は、エントリＥＭＴＥ＿ＬＥ２のＡＣフィールド及びＬＡＴフィールドの内容を、ステップＳ３４と同様に更新する（ステップＳ５５）。
【００８６】
すると、グループ管理部１３５４は、ＬＥ１及びＬＥ２の組み合わせに対応する結合度を１インクリメントする（ステップＳ５６）。次にグループ管理部１３５４は、取得されたＬＥＮ＿ＳＬＥ（ＬＥ１）がＬＥＮ＿ＬＥ２とは異なっており、且つ−１以外（より詳細には−１及び０以外）であるかを判定する（ステップＳ５７）。ここで、ＬＥＮ＿ＳＬＥ（ＬＥ１）によって示される論理エクステントをＬＥｓと表記する。
【００８７】
もし、ステップＳ５７の判定がＹｅｓであるならば、グループ管理部１３５４は、ＬＥ１にＬＥ２を結合させるには、ＬＥｓ及びＬＥ１の結合を解消する必要があると判断する。そこでグループ管理部１３５４は、ＬＥｓをＬＥ１との結合から切り離す（ステップＳ５８）。即ちグループ管理部１３５４は、ＬＥｓ及びＬＥ１の組み合わせに対応する結合度を０に変更（設定）し、且つ、エントリＥＭＴＥ＿ＬＥｓのＰＬＥフィールドの内容を−１に変更する。そしてグループ管理部１３５４は、ステップＳ５９に進む。これに対し、ステップＳ５７の判定がＮｏであるならば、グループ管理部１３５４はステップＳ５８をスキップしてステップＳ５９に進む。
【００８８】
ステップＳ５９においてグループ管理部１３５４は、取得されたＬＥＮ＿ＰＬＥ（ＬＥ２）がＬＥＮ＿ＬＥ１とは異なっており、且つ−１以外（より詳細には−１及び０以外）であるかを判定する。ここで、ＬＥＮ＿ＰＬＥ（ＬＥ２）によって示される論理エクステントをＬＥｐと表記する。
【００８９】
もし、ステップＳ５９の判定がＹｅｓであるならば、グループ管理部１３５４は、ＬＥ１にＬＥ２を結合させるには、ＬＥｐ及びＬＥ２の結合を解消する必要があると判断する。そこでグループ管理部１３５４は、ＬＥｐをＬＥ２との結合から切り離す（ステップＳ６０）。即ちグループ管理部１３５４は、ＬＥｐ及びＬＥ２の組み合わせに対応する結合度を０に変更し、且つ、エントリＥＭＴＥ＿ＬＥｐのＳＬＥフィールドの内容を−１に変更する。
【００９０】
次にグループ管理部１３５４は、ＬＥＮ＿ＳＬＥ（ＬＥ１）がＬＥＮ＿ＰＬＥ（ＬＥ２）に等しいかを判定する（ステップＳ６１）。図１１のフローチャートでは、ステップＳ６１は、ステップＳ５９の判定がＹｅｓであれば、ステップＳ５７の判定の結果に無関係に実行される。しかし、ステップＳ６０が、ステップＳ５７及びＳ５９の判定がいずれもＹｅｓの場合に実行されても構わない。
【００９１】
ＬＥＮ＿ＳＬＥ（ＬＥ１）がＬＥＮ＿ＰＬＥ（ＬＥ２）に等しい場合（ステップＳ６１のＹｅｓ）、グループ管理部１３５４はＬＥｓ及びＬＥｐが同一の論理エクステントであり、当該ＬＥｓ（＝ＬＥｐ）は、ＬＥ１及びＬＥ２が属しているエクステントグループから切り離されるべきであると判断する。この場合、グループ管理部１３５４は、エントリＥＭＴＥ＿ＬＥｓ（＝ＬＥｐ）のＥＧＮフィールドの内容を、新たなエクステントグループを示すＥＧＮに変更する（ステップＳ６２）。
【００９２】
次にグループ管理部１３５４は、特定された論理エクステント範囲内に次の論理エクステント（つまり、現在のＬＥ２の次の論理エクステント）が存在するかを判定する（ステップＳ６３）。もし、次の論理エクステントが存在しないならば（ステップＳ６３のＮｏ）、グループ管理部１３５４は、図１１のフローチャートに従う第２のテーブル更新処理（図９のステップＳ２７）を終了する。つまりグループ管理部１３５４は、図９のフローチャートに従うテーブル更新処理（図８のステップＳ２）を終了する。
【００９３】
これに対して、次の論理エクステントが存在するならば（ステップＳ６３のＹｅｓ）、グループ管理部１３５４は現在のＬＥ２を新たなＬＥ１として選択する（ステップＳ６４）。またグループ管理部１３５４は、特定された論理エクステント範囲内の次の論理エクステントを新たなＬＥ２として選択する（ステップＳ６５）。そしてグループ管理部１３５４はステップＳ５１に戻る。
【００９４】
次に、上述のテーブル更新処理の具体例について、第１の場合を例に、図６及び図７に加えて、図１２及び図１３を参照して説明する。第１の場合とは、ホスト２０からの第１のアクセス要求に応じてテーブル更新処理（図８のステップＳ２）が実行される場合を指す。このとき、エクステント管理テーブル１３３２及び結合管理テーブル１３３３は、それぞれ図６及び図７に示される初期状態にあるものとする。図１２及び図１３は、第１のアクセス要求に応じてテーブル更新処理が実行された後のエクステント管理テーブル１３３２及び結合管理テーブル１３３３の例を示す。
【００９５】
まず、第１のアクセス要求に基づいて特定される論理エクステント範囲が、論理エクステントＡ及びＢの２つの論理エクステントにまたがる範囲であり、論理エクステントＢが論理エクステントＡに後続するものとする。この場合、グループ管理部１３５４は、論理エクステントＡをＬＥ１として選択する（図９のステップＳ２３）。そしてグループ管理部１３５４は、第１のテーブル更新処理（図９のステップＳ２４）を、図１０のフローチャートに従って、ＩＯ管理部１３５３と協同して次のように実行する。
【００９６】
まずグループ管理部１３５４は、論理エクステントＡに後続する論理エクステントＢをＬＥ２として選択する（ステップＳ３１及びＳ３２）。次にグループ管理部１３５４は、論理エクステントＡ（＝ＬＥ１）に対応付けられたエントリＥＭＴＥ＿ＡのＥＧＮフィールド、ＰＬＥフィールド及びＳＬＥフィールドの内容を、図６に示される０、０及び０から図１２に示される１（先頭ＥＧＮ）、−１及びＢに、それぞれ変更する（ステップＳ３３）。先頭ＥＧＮは、グループ管理部１３５４によって決定される。一方、ＩＯ管理部１３５３は、エントリＥＭＴＥ＿ＡのＡＣカウントフィールドの内容を、図６に示される０から図１２に示される１に１だけインクリメントし、且つ当該エントリＥＭＴＥ＿ＡのＬＡＴフィールドの内容を、現在の時刻を示すように更新する（ステップＳ３４）。
【００９７】
すると、グループ管理部１３５４は、論理エクステントＢ（＝ＬＥ２）に対応付けられたエントリＥＭＴＥ＿ＢのＥＧＮフィールド、ＰＬＥフィールド及びＳＬＥフィールドの内容を、図６に示される０、０及び０から図１２に示される１（先頭ＥＧＮ）、Ａ及び−１に、それぞれ変更する（ステップＳ３５）。一方、ＩＯ管理部１３５３は、エントリＥＭＴＥ＿ＢのＡＣカウントフィールドの内容を、図６に示される０から図１２に示される１に１だけインクリメントし、且つ当該エントリＥＭＴＥ＿ＢのＬＡＴフィールドの内容を、現在の時刻を示すように更新する（ステップＳ３６）。
【００９８】
すると、グループ管理部１３５４は、論理エクステントＡ及びＢに対応付けられた結合管理テーブル１３３３のエントリ（Ａ，Ｂ）及び（Ｂ，Ａ）中の結合度を、図７に示される０（空欄によって示される０）から図１３に示される１に１だけインクリメントする（ステップＳ３７）。グループ管理部１３５４は、上述のテーブル更新処理を含むアクセス処理の最後で、最後に処理された論理エクステントＢ（つまり、第１のアクセス要求に基づいて特定される論理エクステント範囲の最後の論理エクステントＢ）の論理エクステント番号Ｂを、有効な論理エクステント番号ＬＥＮｚとして、メモリ１３３の特定領域に格納する（図８のステップＳ１８）。
【００９９】
次に、上述のテーブル更新処理の具体例について、第２の場合を例に、図１２及び図１３に加えて、図１４及び図１５を参照して説明する。第２の場合とは、第１のアクセス要求の次に発行されたホスト２０からの第２のアクセス要求に応じてテーブル更新処理（図８のステップＳ２）が実行される場合を指す。このとき、エクステント管理テーブル１３３２及び結合管理テーブル１３３３は、それぞれ図１２及び図１３に示される状態にある。図１４及び図１５は、第２のアクセス要求に応じてテーブル更新処理が実行された後のエクステント管理テーブル１３３２及び結合管理テーブル１３３３の例を示す。
【０１００】
ここで、第２のアクセス要求に基づいて特定される論理エクステント範囲が、論理エクステントＣ及びＤの２つの論理エクステントにまたがる範囲であり、論理エクステントＤが論理エクステントＣに後続するものとする。このとき、メモリ１３３の特定領域には、論理エクステントＢの論理エクステント番号Ｂが格納されている。論理エクステントＢは、第１のアクセス要求に基づいて特定された論理エクステント範囲の最後の論理エクステントである。明らかなように、論理エクステントＢはアクセス順に関し、論理エクステントＣに先行する論理エクステントであり、論理エクステントＣはアクセス順に関し、論理エクステントＢに後続する論理エクステントである。つまり、論理エクステントＢ及びＣは、アクセス順に関して連続している。
【０１０１】
この場合、グループ管理部１３５４は、論理エクステントＢ及びＣをそれぞれＬＥ１及びＬＥ２として選択する（図９のステップＳ２５及びＳ２６）。するとグループ管理部１３５４は、第２のテーブル更新処理（図９のステップＳ２７）を、図１１のフローチャートに従って、ＩＯ管理部１３５３と協同して次のように実行する。
【０１０２】
グループ管理部１３５４は、論理エクステントＢ（＝ＬＥ１）に対応付けられたエクステント管理テーブル１３３２のエントリＥＭＴＥ＿ＢのＳＬＥフィールドの内容を、図１２に示される−１から図１４に示されるＣに変更する（ステップＳ５２）。また、グループ管理部１３５４は、論理エクステントＣ（＝ＬＥ２）に対応付けられたエクステント管理テーブル１３３２のエントリＥＭＴＥ＿ＣのＥＧＮフィールド及びＳＬＥフィールドの内容を、図１２に示される０及び０から図１４に示される１（つまり、先行する論理エクステントＢが属するエクステントグループのＥＧＮ）及び−１に、それぞれ変更する（ステップＳ５３）。
【０１０３】
グループ管理部１３５４は更に、エントリＥＭＴＥ＿ＣのＰＬＥフィールドの内容を、図１２に示される０から図１４に示されるＢに変更する（ステップＳ５４）。一方、ＩＯ管理部１３５３は、エントリＥＭＴＥ＿ＣのＡＣカウントフィールドの内容を、図１２に示される０から図１４に示される１に１だけインクリメントし、且つ当該エントリＥＭＴＥ＿ＣのＬＡＴフィールドの内容を、現在の時刻を示すように更新する（ステップＳ５５）。すると、グループ管理部１３５４は、論理エクステントＢ及びＣに対応付けられた結合管理テーブル１３３３のエントリ（Ｂ，Ｃ）及び（Ｃ，Ｂ）中の結合度を、図１３に示される０（空欄によって示される０）から図１５に示される１に１だけインクリメントする（ステップＳ５６）。
【０１０４】
その後、グループ管理部１３５４は、論理エクステントＣ及びＤをそれぞれＬＥ１及びＬＥ２として選択する（図１１のステップＳ６４及びＳ６５）。そしてグループ管理部１３５４は、エントリＥＭＴＥ＿ＣのＳＬＥフィールドの内容を、図１４に示されるように−１からＤに変更する（ステップＳ５２）。また、グループ管理部１３５４は、論理エクステントＤに対応付けられたエクステント管理テーブル１３３２のエントリＥＭＴＥ＿ＤのＥＧＮフィールド及びＳＬＥフィールドの内容を、図１２に示される０及び０から図１４に示される１（つまり、先行する論理エクステントＣが属するエクステントグループのＥＧＮ）及び−１に、それぞれ変更する（ステップＳ５３）。
【０１０５】
グループ管理部１３５４は更に、エントリＥＭＴＥ＿ＤのＰＬＥフィールドの内容を、図１２に示される０から図１４に示されるＣに変更する（ステップＳ５４）。一方、ＩＯ管理部１３５３は、エントリＥＭＴＥ＿ＤのＡＣカウントフィールドの内容を、図１２に示される０から図１４に示される１に１だけインクリメントし、且つ当該エントリＥＭＴＥ＿ＤのＬＡＴフィールドの内容を、現在の時刻を示すように更新する（ステップＳ５５）。
【０１０６】
すると、グループ管理部１３５４は、論理エクステントＣ及びＤに対応付けられた結合管理テーブル１３３３のエントリ（Ｃ，Ｄ）及び（Ｄ，Ｃ）中の結合度を、図１３に示される０（空欄によって示される０）から図１５に示される１に１だけインクリメントする（ステップＳ５６）。グループ管理部１３５４は、上述のテーブル更新処理を含むアクセス処理の最後で、最後に処理された論理エクステントＤの論理エクステント番号Ｄを、メモリ１３３の特定領域に格納する（図８のステップＳ１８）。
【０１０７】
次に、上述のテーブル更新処理の具体例について、第３の場合を例に、図１４及び図１５に加えて、図１６及び図１７を参照して説明する。第３の場合とは、第２のアクセス要求の次に発行されたホスト２０からの第３のアクセス要求に応じてテーブル更新処理（図８のステップＳ２）が実行される場合を指す。このとき、エクステント管理テーブル１３３２及び結合管理テーブル１３３３は、それぞれ図１４及び図１５に示される状態にある。図１６及び図１７は、第３のアクセス要求に基づくテーブル更新処理が実行された後のエクステント管理テーブル１３３２及び結合管理テーブル１３３３の例を示す。
【０１０８】
ここで、第３のアクセス要求に基づいて特定される論理エクステント範囲が、論理エクステントＡ及びＢの２つの論理エクステントにまたがる範囲であるものとする。このとき、メモリ１３３の特定領域には、論理エクステントＤの論理エクステント番号Ｄが格納されている。論理エクステントＤは、第２のアクセス要求に基づいて特定された論理エクステント範囲の最後の論理エクステントである。明らかなように、論理エクステントＤ及びＡは、アクセス順に関して連続している。
【０１０９】
この場合、グループ管理部１３５４は、論理エクステントＤ及びＡをそれぞれＬＥ１及びＬＥ２として選択する（図９のステップＳ２５及びＳ２６）。するとグループ管理部１３５４は、第２のテーブル更新処理（図９のステップＳ２７）を、図１１のフローチャートに従って、ＩＯ管理部１３５３と協同して次のように実行する。
【０１１０】
グループ管理部１３５４は、論理エクステントＤ（＝ＬＥ１）に対応付けられたエクステント管理テーブル１３３２のエントリＥＭＴＥ＿ＤのＳＬＥフィールドの内容を、図１４に示される−１から図１６に示されるＡに変更する（ステップＳ５２）。このとき、グループ管理部１３５４は、論理エクステントＡ（＝ＬＥ２）に対応付けられたエクステント管理テーブル１３３２のエントリＥＭＴＥ＿ＡのＥＧＮフィールド及びＳＬＥフィールドの内容（１及びＢ）を変更しない（ステップＳ５３）。
【０１１１】
グループ管理部１３５４は更に、エントリＥＭＴＥ＿ＡのＰＬＥフィールドの内容を、図１４に示される−１から図１６に示されるＤに変更する（ステップＳ５４）。一方、ＩＯ管理部１３５３は、エントリＥＭＴＥ＿ＡのＡＣカウントフィールドの内容を、図１４に示される１から図１６に示される２に１だけインクリメントし、且つ当該エントリＥＭＴＥ＿ＡのＬＡＴフィールドの内容を、現在の時刻を示すように更新する（ステップＳ５５）。すると、グループ管理部１３５４は、論理エクステントＤ及びＡに対応付けられた結合管理テーブル１３３３のエントリ（Ｄ，Ａ）及び（Ａ，Ｄ）中の結合度を、図１５に示される０（空欄によって示される０）から図１７に示される１に１だけインクリメントする（ステップＳ５６）。
【０１１２】
その後、グループ管理部１３５４は、論理エクステントＡ及びＢをそれぞれＬＥ１及びＬＥ２として選択する（ステップＳ６４及びＳ６５）。次にグループ管理部１３５４は、論理エクステントＡ（＝ＬＥ１）及びＢ（＝ＬＥ２）に対応付けられたエントリＥＭＴＥ＿Ａ及びＥＭＴＥ＿Ｂから、エントリＥＭＴＥ＿ＡのＳＬＥフィールドの内容ＬＥＮ＿ＳＬＥ（Ａ）とエントリＥＭＴＥ＿ＢのＰＬＥフィールドの内容ＬＥＮ＿ＰＬＥ（Ｂ）とを取得する（ステップＳ５１）。取得されたＬＥＮ＿ＳＬＥ（Ａ）及びＬＥＮ＿ＰＬＥ（Ｂ）は、図１４に示されるように、それぞれＢ及びＡである。つまり論理エクステントＢ及びＡは、それぞれ、論理エクステントＡの後方リンクエクステント及び論理エクステントＢの前方リンクエクステントとして、既にエクステント管理テーブル１３３２に登録されている。このことは、論理エクステントＡ及びＢが、既に互いに結合関係を有していることを示す。
【０１１３】
このような場合、図１１のフローチャートでは省略されているが、グループ管理部１３５４は、ステップＳ５２及び５４をスキップする。これによりグループ管理部１３５４は、エントリＥＭＴＥ＿ＡのＳＬＥフィールド及びエントリＥＭＴＥ＿ＢのＰＬＥフィールドの内容ＬＥＮ＿ＳＬＥ（Ａ）及びＬＥＮ＿ＰＬＥ（Ｂ）を、図１６に示されるように、現在の状態（つまり、図１４に示されるＢ及びＡ）に維持する。このとき、グループ管理部１３５４は、エントリＥＭＴＥ＿ＢのＥＧＮフィールド及びＳＬＥフィールドの内容（１及びＣ）を変更しない（ステップＳ５３）。
【０１１４】
なお、ステップＳ５２及び５４が実行されても構わない。その理由は、ステップＳ５２の実行により、エントリＥＭＴＥ＿ＡのＳＬＥフィールドにＢが再設定され、且つステップＳ５４の実行により、エントリＥＭＴＥ＿ＢのＰＬＥフィールドにＡが再設定されるためである。つまりステップＳ５２及び５４が実行されても、エントリＥＭＴＥ＿ＡのＳＬＥフィールド及びエントリＥＭＴＥ＿ＢのＰＬＥフィールドの内容が、それぞれＢ及びＡに維持されるためである。
【０１１５】
一方、ＩＯ管理部１３５３は、エントリＥＭＴＥ＿ＢのＡＣカウントフィールドの内容を、図１４に示される１から図１６に示される２に１だけインクリメントし、且つ当該エントリＥＭＴＥ＿ＢのＬＡＴフィールドの内容を、現在の時刻を示すように更新する（ステップＳ５５）。すると、グループ管理部１３５４は、論理エクステントＡ及びＢに対応付けられた結合管理テーブル１３３３のエントリ（Ａ，Ｂ）及び（Ｂ，Ａ）中の結合度を、図１５に示される１から図１７に示される２に１だけインクリメントする（ステップＳ５６）。グループ管理部１３５４は、上述のテーブル更新処理を含むアクセス処理の最後で、最後に処理された論理エクステントＢの論理エクステント番号Ｂを、メモリ１３３の特定領域に格納する（図８のステップＳ１８）。
【０１１６】
次に、上述のテーブル更新処理の具体例について、第４の場合を例に、図１６及び図１７に加えて、図１８及び図１９を参照して説明する。第４の場合とは、第３のアクセス要求の次に発行されたホスト２０からの第４のアクセス要求に応じてテーブル更新処理（図８のステップＳ２）が実行される場合を指す。このとき、エクステント管理テーブル１３３２及び結合管理テーブル１３３３は、それぞれ図１６及び図１７に示される状態にある。図１８及び図１９は、第４のアクセス要求に基づくテーブル更新処理が実行された後のエクステント管理テーブル１３３２及び結合管理テーブル１３３３の例を示す。
【０１１７】
ここで、第４のアクセス要求に基づいて特定される論理エクステント範囲が、論理エクステントＤ及びＥの２つの論理エクステントにまたがる範囲であるものとする。このとき、メモリ１３３の特定領域には、論理エクステントＢの論理エクステント番号Ｂが格納されている。論理エクステントＢは、第３のアクセス要求に基づいて特定された論理エクステント範囲の最後の論理エクステントである。明らかなように、論理エクステントＢ及びＤは、アクセス順に関して連続している。
【０１１８】
この場合、グループ管理部１３５４は、論理エクステントＢ及びＤをそれぞれＬＥ１及びＬＥ２として選択する（図９のステップＳ２５及びＳ２６）。するとグループ管理部１３５４は、第２のテーブル更新処理（図９のステップＳ２７）を、図１１のフローチャートに従って、ＩＯ管理部１３５３と協同して次のように実行する。
【０１１９】
まずグループ管理部１３５４は、論理エクステントＢ（＝ＬＥ１）及びＤ（＝ＬＥ２）に対応付けられたエクステント管理テーブル１３３２のエントリＥＭＴＥ＿Ｂ及びＥＭＴＥ＿Ｄから、エントリＥＭＴＥ＿ＢのＳＬＥフィールドの内容ＬＥＮ＿ＳＬＥ（Ｂ）とエントリＥＭＴＥ＿ＤのＰＬＥフィールドの内容ＬＥＮ＿ＰＬＥ（Ｄ）とを取得する（ステップＳ５１）。取得されたＬＥＮ＿ＳＬＥ（Ｂ）及びＬＥＮ＿ＰＬＥ（Ｄ）は、図１６に示されるように、いずれもＣである。つまり論理エクステントＣは、論理エクステントＢの後方リンクエクステント及び論理エクステントＤの前方リンクエクステントとして既にエクステント管理テーブル１３３２に登録されている。このことは、論理エクステントＢ及びＣが、既に互いに結合関係を有しており、論理エクステントＢＣ及びＤも、既に互いに結合関係を有していることを示す。
【０１２０】
次にグループ管理部１３５４は、論理エクステントＢに対応付けられたエクステント管理テーブル１３３２のエントリＥＭＴＥ＿ＢのＳＬＥフィールドの内容を、図１６に示されるＣから図１８に示されるＤに変更する（ステップＳ５２）。このとき、グループ管理部１３５４は、論理エクステントＤに対応付けられたエクステント管理テーブル１３３２のエントリＥＭＴＥ＿ＤのＥＧＮフィールド及びＳＬＥフィールドの内容（１及びＡ）を変更しない（ステップＳ５３）。
【０１２１】
グループ管理部１３５４は更に、エントリＥＭＴＥ＿ＤのＰＬＥフィールドの内容を、図１６に示されるＣから図１８に示されるＢに変更する（ステップＳ５４）。一方、ＩＯ管理部１３５３は、エントリＥＭＴＥ＿ＤのＡＣカウントフィールドの内容を、図１６に示される１から図１８に示される２に１だけインクリメントし、且つ当該エントリＥＭＴＥ＿ＤのＬＡＴフィールドの内容を、現在の時刻を示すように更新する（ステップＳ５５）。すると、グループ管理部１３５４は、論理エクステントＢ及びＤに対応付けられた結合管理テーブル１３３３のエントリ（Ｂ，Ｄ）及び（Ｄ，Ｂ）中の結合度を、図１７に示される０（空欄によって示される０）から図１９に示される１に１だけインクリメントする（ステップＳ５６）
次にグループ管理部１３５４は、取得されたＬＥＮ＿ＳＬＥ（Ｂ）がＬＥＮ＿Ｄ（＝Ｄ）とは異なっており、且つ−１以外であるかを判定する（ステップＳ５７）。この例では、取得されたＬＥＮ＿ＳＬＥ（Ｂ）はＣであり、ＬＥＮ＿Ｄ（＝Ｄ）とは異なっており、且つ−１以外である（ステップＳ５７のＹｅｓ）。
【０１２２】
この場合、グループ管理部１３５４は、論理エクステントＢに論理エクステントＤを結合させるには、ＬＥＮ＿ＳＬＥ（Ｂ）で示される論理エクステントＣと論理エクステントＢとの結合を解消する必要があると判断する。そこでグループ管理部１３５４は、論理エクステントＣ（＝ＬＥｓ）を論理エクステントＢ（＝ＬＥ１）との結合から切り離す（ステップＳ５８）。即ちグループ管理部１３５４は、論理エクステントＣ及びＢの組み合わせに対応する結合度を、図１７に示される１から図１９に示される０に変更し、且つ、エントリＥＭＴＥ＿ＣのＰＬＥフィールドの内容を、図１６に示されるＢから図１８に示される−１に変更する。
【０１２３】
次にグループ管理部１３５４は、取得されたＬＥＮ＿ＰＬＥ（Ｄ）がＬＥＮ＿Ｂ（＝Ｂ）とは異なっており、且つ−１以外であるかを判定する（ステップＳ５９）。この例では、取得されたＬＥＮ＿ＰＬＥ（Ｄ）はＣであり、ＬＥＮ＿Ｂ（＝Ｂ）とは異なっており、且つ−１以外である（ステップ５９のＹｅｓ）。
【０１２４】
この場合、グループ管理部１３５４は、論理エクステントＢに論理エクステントＤを結合させるには、ＬＥＮ＿ＰＬＥ（Ｄ）によって示される論理エクステントＣと論理エクステントＤとの結合を解消する必要があると判断する。そこでグループ管理部１３５４は、論理エクステントＣ（＝ＬＥｐ）を論理エクステントＤ（＝ＬＥ２）との結合から切り離す（ステップＳ６０）。即ちグループ管理部１３５４は、論理エクステントＣ及びＤの組み合わせに対応する結合度を、図１７に示される１から図１９に示される０に変更し、且つ、エントリＥＭＴＥ＿ＣのＳＬＥフィールドの内容を、図１６に示されるＤから図１８に示される−１に変更する。
【０１２５】
次にグループ管理部１３５４は、取得されたＬＥＮ＿ＳＬＥ（Ｂ）及びＬＥＮ＿ＰＬＥ（Ｄ）が等しいかを判定する（ステップＳ６１）。この例では、取得されたＬＥＮ＿ＳＬＥ（Ｂ）及びＬＥＮ＿ＰＬＥ（Ｄ）は、いずれもＣであり、等しい（ステップＳ６１のＹｅｓ）。このことは、ステップＳ５８において論理エクステントＢ（＝ＬＥ１）との結合関係が解消された論理エクステント（ＬＥｓ）が、ステップＳ６０において論理エクステントＤ（＝ＬＥ２）との結合関係が解消された論理エクステント（ＬＥｐ）に等しい論理エクステントＣであることを示す。そこでグループ管理部１３５４は、論理エクステントＣを、論理エクステントＢ及びＤが属しているエクステントグループから切り離すために、エントリＥＭＴＥ＿ＣのＥＧＮフィールドの内容を、図１６に示される１から、新たなエクステントグループを示すＥＧＮ（例えば図１８に示される２）に変更する（ステップＳ６２）。
【０１２６】
その後、グループ管理部１３５４は、論理エクステントＤ及びＥをそれぞれＬＥ１及びＬＥ２として選択する（ステップＳ６４及びＳ６５）。次にグループ管理部１３５４は、論理エクステントＤ（＝ＬＥ１）及びＥ（＝ＬＥ２）に対応付けられたエントリＥＭＴＥ＿Ｄ及びＥＭＴＥ＿Ｅから、エントリＥＭＴＥ＿ＤのＳＬＥフィールドの内容ＬＥＮ＿ＳＬＥ（Ｄ）とエントリＥＭＴＥ＿ＤのＰＬＥフィールドの内容ＬＥＮ＿ＰＬＥ（Ｅ）とを取得する（ステップＳ５１）。取得されたＬＥＮ＿ＳＬＥ（Ｄ）及びＬＥＮ＿ＰＬＥ（Ｅ）は、図１６に示されるように、それぞれＡ及び０である。
【０１２７】
次にグループ管理部１３５４は、エントリＥＭＴＥ＿ＤのＳＬＥフィールドの内容を、図１６に示されるＡから図１８に示されるＥに変更する（ステップＳ５２）。またグループ管理部１３５４は、エントリＥＭＴＥ＿ＥのＥＧＮフィールド及びＳＬＥフィールドの内容を、図１６に示される０及び０から図１８に示される１及び−１に変更する（ステップＳ５３）。
【０１２８】
グループ管理部１３５４は更に、エントリＥＭＴＥ＿ＥのＰＬＥフィールドの内容を、図１６に示される０から図１８に示されるＤに変更する（ステップＳ５４）。一方、ＩＯ管理部１３５３は、エントリＥＭＴＥ＿ＥのＡＣカウントフィールドの内容を、図１６に示される０から図１８に示される１に１だけインクリメントし、且つ当該エントリＥＭＴＥ＿ＥのＬＡＴフィールドの内容を、現在の時刻を示すように更新する（ステップＳ５５）。すると、グループ管理部１３５４は、論理エクステントＤ及びＥに対応付けられた結合管理テーブル１３３３のエントリ（Ｄ，Ｅ）及び（Ｅ，Ｄ）中の結合度を、図１７に示される０（空欄によって示される０）から図１９に示される１に１だけインクリメントする（ステップＳ５６）
さて、取得されたＬＥＮ＿ＳＬＥ（Ｄ）は上述のようにＡであり、ＬＥＮ＿Ｅ（＝Ｅ）とは異なり、且つ−１以外である（ステップＳ５７のＹｅｓ）。この場合、グループ管理部１３５４は、論理エクステントＤに論理エクステントＥを結合させるには、ＬＥＮ＿ＳＬＥ（Ｄ）で示される論理エクステントＡと論理エクステントＤとの結合を解消する必要があると判断する。そこでグループ管理部１３５４は、論理エクステントＡ（＝ＬＥｓ）を論理エクステントＤ（＝ＬＥ１）との結合から切り離す（ステップＳ５８）。即ちグループ管理部１３５４は、論理エクステントＡ及びＤの組み合わせに対応する結合度を、図１７に示される１から図１９に示される０に変更し、且つ、エントリＥＭＴＥ＿ＡのＰＬＥフィールドの内容を、図１６に示されるＤから図１８に示される−１に変更する。本実施形態では、現在のＬＥ２、つまり論理エクステントＥは、特定された論理エクステント範囲の最後の論理エクステントである（ステップＳ６３のＮｏ）。そこでグループ管理部１３５４は、第２のテーブル更新処理（図９のステップＳ２７）を終了する。即ちグループ管理部１３５４は、テーブル更新処理（図８のステップＳ２）を終了する。
【０１２９】
図８のフローチャートに戻る。テーブル更新処理（ステップＳ２）が実行されると、ＩＯ制御部１３５２が起動される。まずＩＯ制御部１３５２は、受領されたアクセス要求で示されるアクセスを実行するために、特定された論理エクステント範囲内の論理エクステントの数を変数ｅとして設定する（ステップＳ３）。変数ｅは、アクセスされるべき（つまり、アクセスが未完了の）論理エクステントの数を示す。
【０１３０】
次にＩＯ制御部１３５２は、次にアクセスされるべき１つの論理エクステント（つまりターゲット論理エクステント）を、変数ｅで示される数の論理エクステントの中から選択する（ステップＳ４）。次にＩＯ制御部１３５２は、ターゲット論理エクステント内のアクセスされるべき全ての論理ブロックに割り当てられた同数の物理ブロックに、次のようにアクセスする（ステップＳ５）。ここで、ターゲット論理エクステント内のアクセスされるべき論理ブロックの数がｃであるものとする。この場合、このｃ個の論理ブロックに割り当てられた物理ブロックの数もｃである。
【０１３１】
まずＩＯ制御部１３５２は、ターゲット論理エクステント内のアクセスされるべき全論理ブロックのうちの先頭の論理ブロックに割り当てられた物理ブロック（つまり先頭の物理ブロック）の物理エクステント番号及びオフセットの組を取得する。この物理エクステント番号及びオフセットの組は、上述の先頭の論理ブロックの論理ブロックアドレス及び論理エクステント番号に基づいて、ＩＯ制御部１３５２がアドレス変換テーブル１３３１を参照することにより取得される。
【０１３２】
ＩＯ制御部１３５２は、先頭の物理ブロックの物理エクステント番号及びオフセットの組を取得することにより、先頭の物理ブロックから始まる、実際にアクセスされるべきｃ個の物理ブロックと、当該ｃ個の物理ブロックを含むストレージ装置（階層）とを特定する。そしてＩＯ制御部１３５２は、特定されたストレージ装置内の特定されたｃ個の物理ブロックに、ＳＩＦコントローラ１３２を介してアクセスする。なお、アクセス要求がライトアクセス要求であり、且つ当該アクセス要求で指定される論理ブロック範囲内の論理ブロックに物理ブロックが割り当てられていない場合、ＩＯ管理部１３５３は、例えばステップＳ３の実行時に、論理ブロック範囲内の論理ブロックに高速ストレージ装置１１（上位階層）内の連続する同数の空き物理ブロックを割り当てる。
【０１３３】
ＩＯ制御部１３５２は、特定されたｃ個の物理ブロックにアクセスすると（ステップＳ５）、ＨＩＦコントローラ１３１を介してホスト２０に応答を返す（ステップＳ６）。そしてＩＯ制御部１３５２は、階層化制御部１３５５に制御を渡す。すると階層化制御部１３５５は、低速ストレージ装置１２（下位階層）へのアクセスであったかを判定する（ステップＳ７）。
【０１３４】
もし、下位階層へのアクセスであったならば（ステップＳ７のＹｅｓ）、ターゲット論理エクステントは近い将来アクセスされる可能性が高いことから、階層化制御部１３５５は、当該ターゲット論理エクステントに割り当てられた物理エクステントのデータを、アクセス性能の向上のために上位階層に移動すべきであると判断する。また、ターゲット論理エクステントがエクステントグループに属しているならば、当該エクステントグループ内の他の全ての論理エクステントも近い将来アクセスされる可能性が高いことから、階層化制御部１３５５は、当該他の全ての論理エクステントに割り当てられたそれぞれの物理エクステントのデータも、上位階層に移動すべきであると判断する。そこで、階層化制御部１３５５は、ターゲット論理エクステントに割り当てられた物理エクステントを含む１つ以上の物理エクステントをデータ移動元として決定するためのデータ移動元決定処理を実行する（ステップＳ８）。
【０１３５】
以下、データ移動元決定処理（ステップＳ８）の詳細について、図２０を参照して説明する。図２０はデータ移動元決定処理の典型的な手順を示すフローチャートである。まず階層化制御部１３５５は、ターゲット論理エクステントに対応付けられたエクステント管理テーブル１３３２のエントリのＥＧＮフィールドを参照する（ステップＳ７１）。
【０１３６】
次に階層化制御部１３５５は、参照されたＥＧＮフィールドに初期値０以外の数値が設定されているかに応じて、ターゲット論理エクステントがエクステントグループに属しているかを判定する（ステップＳ７２）。もし、ターゲット論理エクステントがエクステントグループに属しているならば（ステップＳ７２のＹｅｓ）、階層化制御部１３５５はステップＳ７３に進む。ステップＳ７３において階層化制御部１３５５は、ターゲット論理エクステントが属しているエクステントグループ内の全論理エクステントに割り当てられた物理エクステントの集合を特定する。また、ステップＳ７３において階層化制御部１３５５は、特定された物理エクステントの集合に含まれている、下位階層内の全物理エクステントを、データ移動元として決定する。決定されたデータ移動元は、ターゲット論理エクステントが割り当てられた物理エクステントを含む。そして階層化制御部１３５５は、データ移動元決定処理を終了する。
【０１３７】
一方、ターゲット論理エクステントがエクステントグループに属していないならば（ステップＳ７２のＮｏ）、階層化制御部１３５５は、当該ターゲット論理エクステントに割り当てられた物理エクステントのみを、データ移動元として決定する（ステップＳ７４）。そして階層化制御部１３５５は、データ移動元決定処理を終了する。
【０１３８】
図８に戻って、アクセス処理について更に説明する。階層化制御部１３５５は、図２０のフローチャートに従ってデータ移動元決定処理（ステップＳ８）を実行すると、ステップＳ９に進む。ステップＳ９において階層化制御部１３５５は、データ移動元として決定された物理エクステントの数を変数ｑとして設定する（ステップＳ９）。
【０１３９】
次に階層化制御部１３５５は、上位階層内の空き領域を探索する（ステップＳ１０）。即ち階層化制御部１３５５は、アドレス変換テーブル１３３１に基づいて、上位階層（高速ストレージ装置１１）に含まれていて、且つ論理エクステントに割り当てられてない物理エクステント（つまり、空き物理エクステント）を探索する。なお、空き物理エクステントリストがメモリ１３３（ローカルＨＤＤ１３４）に格納されているならば、階層化制御部１３５５が、上位階層内の空き物理エクステントを、当該リストから探索しても良い。但し、空き物理エクステントリストには、空き物理エクステントの物理エクステント番号の配列が保持されているものとする。
【０１４０】
階層化制御部１３５５は、上位階層内の空き物理エクステントを探索すると、当該空き物理エクステントの数を変数ｆとして設定する（ステップＳ１１）。ステップＳ１１において階層化制御部１３５５は、変数ｑから変数ｆを差し引いて、その差分ｑ−ｆを変数ｒとして設定する。次に階層化制御部１３５５は、変数ｒ（＝ｑ−ｆ）が正であるかを判定する（ステップＳ１２）。
【０１４１】
もし、変数ｒが正であるならば（ステップＳ１２のＹｅｓ）、即ちｑ＞ｆであるならば、階層化制御部１３５５は、データ移動元として決定されたｑ個の物理エクステントのデータを上位階層に移動するのにｒ個の空きの物理エクステントが不足していると判断する。この場合、階層化制御部１３５５は、少なくともｒ個の新たな空きの物理エクステントを上位階層内に確保するための空き領域確保処理を実行する（ステップＳ１３）。そして階層化制御部１３５５は、ステップＳ１４に進む。
【０１４２】
これに対して変数ｒが正でないならば（ステップＳ１２のＮｏ）、即ちｑ≦ｆであるならば、階層化制御部１３５５は、データ移動元として決定されたｑ個の物理エクステントのデータを上位階層に移動するのに十分な数の空きの物理エクステントが既に存在すると判断する。この場合、階層化制御部１３５５は、ステップＳ１３をスキップしてステップＳ１４に進む。
【０１４３】
以下、空き領域確保処理（ステップＳ１３）の詳細について、図２１を参照して説明する。図２１は空き領域確保処理の典型的な手順を示すフローチャートである。以下の説明では、論理エクステントに上位階層内の物理エクステントが割り当てられている場合、当該論理エクステントを、上位階層に対応する論理エクステントと称する。同様に、エクステントグループ内の複数の論理エクステントに上位階層内の同数の物理エクステントが割り当てられている場合、当該エクステントグループを、上位階層に対応するエクステントグループと称する。
【０１４４】
空き領域確保処理において、まず階層化制御部１３５５は、上位階層に対応しており、且つエクステントグループに属していない全ての論理エクステント、及び上位階層に対応する全てのエクステントグループに関するリストを生成する（ステップＳ８１）。生成されたリストは、エクステントグループに属していない論理エクステントに関する要素群、及びエクステントグループに関する要素群の配列を含む。
【０１４５】
リストに含まれている、エクステントグループに属していない論理エクステントに関する各要素は、当該論理エクステントの論理エクステント番号、アクセスカウント及び最終アクセス時刻情報の組を有する。一方、リストに含まれている、エクステントグループに関する各要素は、当該エクステントグループのエクステントグループ番号、アクセスカウント及び最終アクセス時刻情報の組を有する。
【０１４６】
本実施形態において階層化制御部１３５５は、エクステントグループに属する全ての論理エクステントのアクセスカウントの平均値を、当該エクステントグループのアクセスカウントとして用いる。しかし階層化制御部１３５５が、エクステントグループに属する全ての論理エクステントのアクセスカウントのうち、最大のアクセスカウントを、当該エクステントグループのアクセスカウントとして用いても構わない。また、本実施形態において階層化制御部１３５５は、エクステントグループに属する全ての論理エクステントの最終アクセス時刻のうち、最も新しい最終アクセス時刻を示す最終アクセス時刻情報を、当該エクステントグループの最終アクセス時刻情報として用いる。
【０１４７】
上述のリストの生成において階層化制御部１３５５は、エクステントグループに属していない論理エクステント、及びエクステントグループを、エクステント管理テーブル１３３２に基づいて特定する。また階層化制御部１３５５は、特定された論理エクステントが上位階層に対応するかを、当該論理エクステントの論理エクステント番号に基づいてアドレス変換テーブル１３３１を参照することにより判定する。つまり階層化制御部１３５５は、特定された論理エクステントに割り当てられた物理エクステントの物理エクステント番号に基づいて、当該特定された論理エクステントが上位階層に対応するかを判定する。同様に階層化制御部１３５５は、特定されたエクステントグループが上位階層に対応するかを、当該特定されたエクステントグループ内の論理エクステントの論理エクステント番号に基づいてアドレス変換テーブル１３３１を参照することにより判定する。つまり階層化制御部１３５５は、特定されたエクステントグループ内の論理エクステントに割り当てられた物理エクステントの物理エクステント番号に基づいて、当該特定されたエクステントグループ内の論理エクステントが上位階層に対応するかを判定し、この判定結果に基づいて。当該特定されたエクステントグループが上位階層に対応するかを判定する。
【０１４８】
階層化制御部１３５５は、上述のリストを生成すると、当該リスト内の全要素を、それぞれの要素のアクセスカウント（より詳細には、アクセスカウント及び最終アクセス時刻）に基づいて（例えば、アクセスカウントの昇順に）ソートする（ステップＳ８２）。このソートにおいて、アクセスカウントが同一の複数の要素が存在する場合、階層化制御部１３５５は、最終アクセス時刻が古い要素ほど低い順位に位置付ける。但し、説明の簡略化のために、或る要素の順位が別の要素の順位よりも高い（低い）場合、当該或る要素のアクセスカウントは当該別の要素のアクセスカウントよりも大きい（小さい）ものとする。また、アクセスカウントが最小の要素の順位は最下位として扱われる。
【０１４９】
次に階層化制御部１３５５は、生成されたリスト内の要素の数を変数ｘの初期値として設定する（ステップＳ８３）。変数ｘは、生成されたリスト内の要素（より詳細には、ソート後の要素）の位置（つまり順位）を示すポインタとして用いられる。そこで、以下の説明では、変数ｘをポインタｘと称する。ステップＳ８３において階層化制御部１３５５は、変数ｙを初期値０に設定する。変数ｙは、空き領域確保処理において上位階層から下位階層にデータが移動された物理エクステントの数、つまり上位階層内に新たに確保された空き物理エクステントの数を示す。
【０１５０】
次に階層化制御部１３５５は、ポインタｘで指定されるリスト内の要素（つまり順位が第ｘ位の要素）が、エクステントグループであるかを判定する（ステップＳ８４）。もし、第ｘ位の要素がエクステントグループであるならば（ステップＳ８４のＹｅｓ）、階層化制御部１３５５は、当該第ｘ位のエクステントグループ内の全論理エクステントに割り当てられた同数の物理エクステント内のデータを、上位階層（高速ストレージ装置１１）から下位階層（低速ストレージ装置１２）内の空き領域に移動する（ステップＳ８５）。このデータの移動により、階層化制御部１３５５は、第ｘ位のエクステントグループ内の全論理エクステントに割り当てられた上位階層内の同数の物理エクステントを、空き物理エクステント（空き領域）として新たに確保することができる。
【０１５１】
次に階層化制御部１３５５は、変数ｙを、今回のステップＳ８４の実行によってデータが移動された物理エクステントの数だけインクリメントする（ステップＳ８６）。そして階層化制御部１３５５は、ステップＳ８９に進む。
【０１５２】
これに対し、第ｘ位の要素がエクステントグループでないならば（ステップＳ８４のＮｏ）、つまり第ｘ位の要素が論理エクステントであるならば、階層化制御部１３５５は、当該第ｘ位の論理エクステントに割り当てられた物理エクステント内のデータを、上位階層から下位階層内の空き領域に移動する（ステップＳ８７）。このデータの移動により、階層化制御部１３５５は、第ｘ位の論理エクステントに割り当てられた上位階層内の物理エクステントを、空き物理エクステントとして確保することができる。次に階層化制御部１３５５は、変数ｙを１だけインクリメントして（ステップＳ８８）、ステップＳ８９に進む。
【０１５３】
ステップＳ８９において階層化制御部１３５５は、ステップＳ８５またはＳ８７におけるデータの移動が反映されるように、アドレス変換テーブル１３３１を更新する。即ち、ステップＳ８５の実行に応じてステップＳ８９が実行される場合、階層化制御部１３５５は、第ｘ位のエクステントグループ内の全論理エクステント（内の論理ブロック群）に割り当てられる同数の物理エクステント（内の物理ブロック群）が、ステップＳ８５におけるデータ移動元の物理エクステント群（内の物理ブロック群）からステップＳ８５におけるデータ移動先の物理エクステント群（内の物理ブロック群）に変更されるように、アドレス変換テーブル１３３１を更新する。これに対してステップＳ８７の実行に応じてステップＳ８９が実行される場合、階層化制御部１３５５は、第ｘ位の論理エクステントに割り当てられる物理エクステントが、ステップＳ８７におけるデータ移動元の物理エクステントからステップＳ８７におけるデータ移動先の物理エクステントに変更されるように、アドレス変換テーブル１３３１を更新する。
【０１５４】
階層化制御部１３５５は、アドレス変換テーブル１３３１を更新すると、ステップＳ９０に進む。ステップＳ９０において階層化制御部１３５５は、ステップＳ８６またはＳ８８で更新された変数ｙが変数ｒ以上であるかを判定する。もし、変数ｙが変数ｒ以上であるならば（ステップＳ９０のＹｅｓ）、階層化制御部１３５５は、空き領域確保処理によって、少なくともｒ個の新たな空きの物理エクステントを上位階層内に確保できたと判断する。そこで階層化制御部１３５５は、空き領域確保処理を終了する。
【０１５５】
上述のように本実施形態では、階層化制御部１３５５は、ステップＳ８５及びＳ８７で実行される空き領域を確保するためのデータ移動を、エクステント管理テーブル１３３２及び結合管理テーブル１３３３に反映しない。しかし階層化制御部１３５５が、空き領域を確保するためのデータ移動に応じて、エクステント管理テーブル１３３２及び結合管理テーブル１３３３を更新しても構わない。但し、このデータ移動がステップＳ８７において実行される場合、結合管理テーブル１３３３は更新されない。
【０１５６】
一方、変数ｙが変数ｒ以上でないならば（ステップＳ９０のＮｏ）、階層化制御部１３５５は、少なくともｒ個の新たな空きの物理エクステントを上位階層内に未だ確保できていないと判断する。そこで、階層化制御部１３５５は、空き領域確保処理を次のように継続する。
【０１５７】
まず階層化制御部１３５５は、ポインタｘを１だけディクリメントする（ステップＳ９１）。そして、階層化制御部１３５５はステップＳ８４に戻って、ディクリメントされたポインタｘで指定されるリスト内の要素が、エクステントグループであるかを判定する。明らかなように、今回の判定に用いられた要素の順位は、前回の判定に用いられた要素より１つだけ高い。以降の動作は、前回の判定後の動作と同様である。ステップＳ８４乃至Ｓ９１は、少なくともｒ個の新たな空きの物理エクステントが上位階層内に確保されるまで繰り返し実行される。
【０１５８】
図８に戻って、アクセス処理について更に説明する。階層化制御部１３５５は、図２１のフローチャートに従って空き領域確保処理（ステップＳ１３）を実行すると、ステップＳ１４に進む。このとき上位階層内には、少なくともｆ＋ｒ（＝ｑ）個の空き物理エクステントが存在する。そこで階層化制御部１３５５は、データ移動元決定処理（ステップＳ８）で決定されたｑ個の物理エクステント内のデータを、上位階層内の空き領域（より詳細には、ｑ個の空き物理エクステント）に移動する（ステップＳ１４）。また階層化制御部１３５５は、空き領域確保処理（ステップＳ１３）をスキップした場合にも（ステップＳ１２のＮｏ）、上述のデータの移動を実行する（ステップＳ１４）。
【０１５９】
次に階層化制御部１３５５は、ステップＳ１４におけるデータの移動が反映されるように、アドレス変換テーブル１３３１、エクステント管理テーブル１３３２、及び結合管理テーブル１３３３を更新する（ステップＳ１５）。即ち階層化制御部１３５５は、データ移動元のｑ個の物理エクステント（内の物理ブロック群）が割り当てられていたｑ個の論理エクステント（内の論理ブロック群）に、データ移動先のｑ個の物理エクステント（内の物理ブロック群）が割り当てられるように、アドレス変換テーブル１３３１を更新する。また階層化制御部１３５５は、エクステント管理テーブル１３３２において、上述のｑ個の論理エクステントに対応付けられているエントリ中のアクセスカウント及び最終アクセス時刻情報を更新する。また、階層化制御部１３５５は、上述のｑ個の論理エクステントにおけるアクセスが連続する論理エクステントの組み合わせ毎に、結合管理テーブル１３３３における対応する結合度を１インクリメントする。
【０１６０】
階層化制御部１３５５はステップＳ１５を実行すると、ＩＯ制御部１３５２に制御を返す。するとＩＯ制御部１３５２は、変数ｅを１ディクリメントする（ステップＳ１６）。そしてＩＯ制御部１３５２は、１ディクリメントされた変数ｅが０未満（負）であるかを判定する（ステップＳ１７）。もし、１ディクリメントされた変数ｅが０未満であるならば（ステップＳ１７のＹｅｓ）、ＩＯ制御部１３５２は特定された論理エクステント範囲内の全ての論理エクステントへのアクセスが完了したと判断する。そこでＩＯ制御部１３５２は、最後に処理されたターゲット論理エクステント（つまり、特定された論理エクステント範囲の最後の論理エクステント）の論理エクステント番号を、メモリ１３３の特定領域に格納して（ステップＳ１８）、図８のフローチャートに従うアクセス処理を終了する。
【０１６１】
これに対し、１ディクリメントされた変数ｅが０未満でないならば（ステップＳ１７のＮｏ）、ＩＯ制御部１３５２は、特定された論理エクステント範囲内に未だアクセスされていないｅ個の論理エクステントが存在すると判断する。そこで、ＩＯ制御部１３５２はステップＳ４に戻り、未だアクセスされていないｅ個（つまり、変数ｅで示される数）の論理エクステントの中から、先行してアクセスされた論理エクステントに後続する論理エクステントをターゲット論理エクステントとして選択する。そして、最初のステップＳ４でターゲット論理エクステントが選択された場合と同様に、ステップＳ４に続く処理（つまり、ステップＳ５乃至Ｓ７を含む処理）が実行される。
【０１６２】
最初のステップＳ４で選択されたターゲット論理エクステントに割り当てられた物理エクステントが下位階層に存在する場合（ステップＳ７のＹｅｓ）、最初のステップＳ１４で下位階層から上位階層へのデータ移動が実行される。このため、最初のステップＳ４で選択されたターゲット論理エクステントがエクステントグループに属しているならば、最初のステップＳ１４の実行後、当該エクステントグループ内の全論理エクステントに割り当てられた物理エクステントの集合は上位階層に存在する。したがって、２回目のステップＳ４で選択されたターゲット論理エクステントに割り当てられた物理エクステントは、上位階層に存在する（ステップＳ７のＮｏ）。この場合、ステップＳ８乃至Ｓ１５をスキップしてステップＳ１６が実行される。
【０１６３】
なお、最初のステップＳ４で選択されたターゲット論理エクステントに割り当てられた物理エクステントが上位階層に存在する場合にも（ステップＳ７のＮｏ）、ステップＳ８乃至Ｓ１５をスキップしてステップＳ１６が実行される。そして、２回目のステップＳ４で選択されたターゲット論理エクステントに割り当てられた物理エクステントが下位階層に存在するならば（ステップＳ７のＹｅｓ）、ステップＳ８が実行される。
【０１６４】
本実施形態によれば、階層化制御部１３５５は、ホスト２０からのアクセス要求で指定された論理エクステント範囲が属するエクステントグループ内の全ての論理エクステントに割り当てられた物理エクステントの集合に含まれている、下位階層内の全ての物理エクステントのデータを、当該アクセス要求に従うアクセス処理におけるステップＳ１４の実行により、上位階層に移動する。このデータ移動は、従来実行されていた、定期的なアクセス頻度評価に基づく階層間のデータ移動に比べて、オーバーヘッドが小さく、短時間で実行できる。
【０１６５】
指定の論理エクステント範囲が属するエクステントグループ内のそれぞれの論理エクステントは、同時アクセスに関する関連性が高く、仮にアクセスカウントが小さいとしても、近い将来アクセスされる可能性が高い。本実施形態では、このエクステントグループ内のそれぞれの論理エクステント（に割り当てられた物理エクステント）のデータは、上述のデータ移動により、全て上位階層に存在することが保証される。したがって、データ移動後の近い将来に、上述のエクステントグループ内の任意の論理ブロック範囲へのアクセスが要求された場合、ＩＯ制御部１３５２は、当該任意の論理ブロック範囲に対応する物理ブロック範囲に高速にアクセスすることができる。
【０１６６】
図８のフローチャートでは、変数ｅに関する判定（ステップＳ１７）が、変数ｅのディクリメント（ステップＳ１６）の直後に実行される。しかし、変数ｅに関する判定が、例えば、ターゲット論理エクステントの選択（ステップＳ４）の直前に実行されても良い。この場合、ＩＯ制御部１３５２は、ステップＳ１７とは異なって、変数ｅが１未満であるかを判定する必要がある。もし、変数ｅが１未満でないならば、ＩＯ制御部１３５２はステップＳ４に進み、変数ｅが１未満であるならば、ＩＯ制御部１３５２はステップＳ１８に進めば良い。またＩＯ制御部１３５２は、変数ｅのディクリメント（ステップＳ１６）の後に、変数ｅが１未満であるかを判定すれば良い。
【０１６７】
＜変形例＞
次に前記実施形態の変形例について説明する。前記実施形態では、エクステントグループの規模について制約は設けられていない。このため、時間の経過に伴い、エクステントグループが巨大化する可能性がある。エクステントグループが巨大化すると、当該エクステントグループ内の例えば全論理エクステント（に割り当てられている物理エクステント）のデータを下位階層から上位階層に移動するのに、多大な時間を要する。そこで、本変形例の特徴は、巨大化したエクステントグループを、再グループ分け処理により、２つのエクステントグループに分けることにある。
【０１６８】
以下、本変形例における再グループ分け処理について、図２２を参照して説明する。図２２は、再グループ分け処理の手順を示すフローチャートである。本変形例では、再グループ分け処理は、図８のフローチャートで示されるアクセス処理において、ステップＳ３の直前（つまり、ステップＳ２の直後）に追加されるものとする。したがって必要ならば、図８のフローチャートにおいて、ステップＳ２とステップＳ３との間に、再グループ分け処理を挿入されたい。
【０１６９】
まず、グループ管理部１３５４は、図８のステップＳ２におけるエクステント管理テーブル１３３２の更新の結果に基づいて、エクステントグループの拡張が発生したかを判定する（ステップＳ１０１）。エクステントグループの拡張とは、当該エクステントグループを構成する論理エクステントの数が増加することを指す。前述の第２の場合、エクステントグループの拡張が発生する。
【０１７０】
もし、エクステントグループの拡張が発生していないならば（ステップＳ１０１のＮｏ）、グループ管理部１３５４は再グループ分けは不要であると判断する。この場合、グループ管理部１３５４は図２２のフローチャートに従う再グループ分け処理を終了して、図８のステップＳ３に進む。
【０１７１】
これに対し、エクステントグループの拡張が発生しているならば（ステップＳ１０１のｙｅｓ）、グループ管理部１３５４は、拡張されたエクステントグループを特定する（ステップＳ１０２）。次にグループ管理部１３５４は、エクステント管理テーブル１３３２に基づいて、特定されたエクステントグループを構成する論理エクステントの数Ｎｅを検出する（ステップＳ１０３）。
【０１７２】
なお、エクステントグループ毎に論理エクステントの数を管理するために、グループ管理部１３５４が、各エクステントグループに対応付けられたエントリを有するエクステントグループ管理テーブルを用いても良い。このエクステントグループ管理テーブルの各エントリは、対応するエクステントグループを構成する論理エクステントの数を保持するのに用いられる。
【０１７３】
次にグループ管理部１３５４は、検出された論理エクステントの数Ｎｅが閾値Ｎｔｈを超えているかを判定する（ステップＳ１０４）。閾値Ｎｔｈは、特定されたエクステントグループが巨大化しているかを判定するための基準値である。本変形例において、閾値Ｎｔｈは、上位階層（高速ストレージ装置１１）に配置可能な最大のエクステントの数の一定割合、例えば１／２に設定される。しかし、閾値Ｎｔｈが他の値であっても構わない。
【０１７４】
もし、ＮｅがＮｔｈを超えていないならば（ステップＳ１０４のＮｏ）、グループ管理部１３５４は、特定されたエクステントグループを再グループ分けすることは不要であると判断する。この場合、グループ管理部１３５４は再グループ分け処理を終了して、図８のステップＳ３に進む。
【０１７５】
これに対し、ＮｅがＮｔｈを超えているならば（ステップＳ１０４のＹｅｓ）、グループ管理部１３５４は、特定されたエクステントグループを再グループ分けするための３つの前処理（第１乃至第３の前処理）を次のように実行する。まずグループ管理部１３５４は、第１の前処理を実行して、特定されたエクステントグループ内で最小の結合度（より詳細には、０以外で最小の結合度）を持つ論理エクステントの対（第２及び第３の論理エクステントの組み合わせ）を検出する（ステップＳ１０５）。以下、ステップＳ１０５の詳細について説明する。
【０１７６】
まずグループ管理部１３５４は、エクステント管理テーブル１３３２に基づいて、特定されたエクステントグループ内の全論理エクステントを特定する。次にグループ管理部１３５４は、特定された全論理エクステントにおけるアクセスが連続する論理エクステントの対毎の結合度を、結合管理テーブル１３３３から取得する。そしてグループ管理部１３５４は、取得された結合度の中から最小の結合度を検出する。これによりグループ管理部１３５４は、最小の結合度を持つ論理エクステントの対を検出する。
【０１７７】
図２３は、拡張されたエクステントグループとしてエクステントグループＧＲ１が特定された場合の、当該エクステントグループＧＲ１の構成と、当該エクステントグループＧＲ１内のアクセスが連続する論理エクステントの対毎の結合度との例を、結合管理テーブル１３３３の例と共に示す。図２３の例は、簡略化のために、エクステントグループＧＲ１が、６つの論理エクステントＡ，Ｂ，Ｃ，Ｄ，Ｅ及びＦから構成され（Ｎｅ＝６）、Ｎｔｈが５である場合を想定している。しかし、Ｎｅ及びＮｔｈは、一般にこの例よりも十分に大きい。
【０１７８】
図２３において、論理エクステントＡ，Ｂ，Ｃ，Ｄ，Ｅ及びＦをこの順で結合する矢印は、アクセス順を示す。したがって、例えば論理エクステントＣの前方リンクエクステント及び後方リンクエクステントは、それぞれ、論理エクステントＢ及びＤである。図２３の例では、クステントグループＧＲ１内の互いに隣接する論理エクステントの対の結合度（Ａ，Ｂ）［＝（Ｂ，Ａ）］，（Ｂ，Ｃ）［＝（Ｃ，Ｂ）］，（Ｃ，Ｄ）［＝（Ｄ，Ｃ）］，（Ｄ，Ｅ）［＝（Ｅ，Ｄ）］，及び（Ｅ，Ｆ）［＝（Ｆ，Ｅ）］は、それぞれ、５０，１３２，５，３７及び８２である。これらの結合度は、矢印２３０で示されるように、結合管理テーブル１３３３に反映されている。図２３の例では、最小の結合度として５が検出される。
【０１７９】
次にグループ管理部１３５４は、第２の前処理を実行して、結合管理テーブル１３３３内の全結合度（より詳細には、０以外の全結合度）を、検出された最小の結合度で正規する（ステップＳ１０６）。この正規化とは、結合管理テーブル１３３３内の全結合度を検出された最小の結合度で除することを指す。図２３の例では、最小の結合度は結合度（Ｃ，Ｄ）［＝（Ｄ，Ｃ）］であり、５である。
【０１８０】
図２４は、第２の前処理（正規化）実行前後の結合管理テーブル１３３３の例を対比して示す。図２４において、正規化前の結合管理テーブル１３３３は矢印２４０の基端側に、正規化後の結合管理テーブル１３３３は矢印２４０の先端側に、それぞれ示されている。正規化前の結合管理テーブル１３３３の内容は、図２３に示される結合管理テーブル１３３３のそれに一致する。結合管理テーブル１３３３における最小の結合度（Ｃ，Ｄ）［＝（Ｄ，Ｃ）］は、正規化により、図２４に示されているように、５から１に変更される。
【０１８１】
次にグループ管理部１３５４は、第３の前処理を実行して、結合管理テーブル１３３３内の正規化された最小の結合度（つまり、１）を、結合無しを示す０に置き換える（ステップＳ１０７）。結合度０は、前述のように、空欄で示されるそれと等価である。この置き換えにより、最小の結合度１を持つ論理エクステントの対の結合は解消される。
【０１８２】
図２５は、第３の前処理（０置き換え）実行前後の結合管理テーブル１３３３の例を対比して示す。図２５において、０置き換え前の結合管理テーブル１３３３は矢印２５０の基端側に、０置き換え後の結合管理テーブル１３３３は矢印２５０の先端側に、それぞれ示されている。
【０１８３】
次にグループ管理部１３５４は、特定されたエクステントグループ内の全エクステントを、上述の結合度０への置き換えが反映される（つまり、結合度が０に置き換えられた論理エクステントの対の結合関係が解消される）ように、再グループ分けする（ステップＳ１０８）。即ちグループ管理部１３５４は、特定されたエクステントグループ（第２のエクステントグループ）を、結合度が０に置き換えられた論理エクステントの対の一方（第２の論理エクステント）を含むエクステントグループ（第３のエクステントグループ）と、当該論理エクステントの対の他方（第３の論理エクステント）を含むエクステントグループ（第４のエクステントグループ）とに、エクステント管理テーブル１３３２及び結合管理テーブル１３３３に基づいて分割する。
【０１８４】
本変形例においてグループ管理部１３５４は、結合度が０に置き換えられた論理エクステントの対のうちの先行する論理エクステント（以下、前エクステントと称する）を含むエクステントグループに、現在用いられていない新たなエクステントグループ番号を付与する。またグループ管理部１３５４は、結合度が０に置き換えられた論理エクステントの対のうちの後続する論理エクステント（以下、後エクステントと称する）を含むエクステントグループに、元のエクステントグループ（つまり、特定されたエクステントグループ）のエクステントグループ番号を付与する。しかし、この逆であっても構わない。
【０１８５】
再グループ分け（ステップＳ１０８）においてグループ管理部１３５４は、エクステント管理テーブル１３３２を次のように更新する。まずグループ管理部１３５４は、前エクステントに対応付けられたエクステント管理テーブル１３３２のエントリ中のＥＧＮフィールドの内容及びＳＬＥフィールドの内容を、それぞれ、上述の新たなエクステントグループ番号及び−１に更新する。またグループ管理部１３５４は、後エクステントに対応付けられたエクステント管理テーブル１３３２のエントリ中のＰＬＥフィールドの内容を−１に更新する。
【０１８６】
グループ管理部１３５４は、再グループ分け（ステップＳ１０８）を実行すると、図２２のフローチャートに従う再グループ分け処理を終了する。そして本変形例では、図８のフローチャートにおけるステップＳ３が実行される。なお、再グループ分け処理が、ステップＳ３の直前以外のタイミング、例えばステップＳ３の直後に実行されても構わない。
【０１８７】
図２６は、再グループ分け前（つまり、第３の前処理実行直後）における結合管理テーブル１３３３の例を示すと共に、再グループ分け前後のエクステントグループの例を対比して示す。図２６において、再グループ分け前の結合管理テーブル１３３３は、矢印２６１の基端側に示されている。上述のステップＳ１０８の説明から明らかなように、再グループ分けでは、結合管理テーブル１３３３の更新は発生しない。つまり、結合管理テーブル１３３３は、再グループ分けの前後で変わらない。したがって、図２６に示される結合管理テーブル１３３３は、再グループ分け後の状態をも示す。図２６において、矢印２６１の先端側及び矢印２６２の基端側には、エクステントグループＧＲ１の再グループ分け前の構成が示されている。図２６に示される再グループ分け前のエクステントグループＧＲ１は、図２３からも明らかなように、論理エクステントＡ，Ｂ，Ｃ，Ｄ，Ｅ及びＦから構成されている。
【０１８８】
再グループ分け前のエクステントグループＧＲ１内の論理エクステントＣ及びＤの対の結合度は、第３の前処理（ステップＳ１０７）により０に変更されている。そこで階層化制御部１３５５は、論理エクステントＣ及びＤの結合を解消する。そして階層化制御部１３５５は、論理エクステントＣと、論理エクステントＡ及びＢ（つまり、論理エクステントＣと間接または直接に結合関係を有する論理エクステントＡ及びＢ）とを、エクステントグループＧＲ１から外して、新たなエクステントグループＧＲａに所属させる。即ち階層化制御部１３５５は、エクステントグループＧＲ１内の論理エクステントＡ，Ｂ，Ｃ，Ｄ，Ｅ及びＦを、図２６において矢印２６２で示されるように、論理エクステントＡ，Ｂ及びＣから構成される新たなエクステントグループＧＲａと、論理エクステントＤ，Ｅ及びＦから構成される縮小されたエクステントグループＧＲ１とに、再グループ分けする（ステップＳ１０８）。
【０１８９】
以上説明した少なくとも１つの実施形態によれば、階層間のデータ移動を効率化できる。
【０１９０】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１９１】
１０…階層化ストレージシステム、１１…高速ストレージ装置（第１のストレージ装置）、１２…低速ストレージ装置（第２のストレージ装置）、１３…ストレージコントローラ、２０…ホスト（ホスト計算機）、１３３…メモリ、１３４…ローカルＨＤＤ、１３５…ＣＰＵ、１３３１…アドレス変換テーブル、１３３２…エクステント管理テーブル、１３３３…結合管理テーブル、１３５１…構成管理部、１３５２…入出力（ＩＯ）制御部、１３５３…ＩＯ管理部、１３５４…グループ管理部、１３５５…階層化制御部。
【図１】
2017167819.tif 000003
【図２】
2017167819.tif 000004
【図３】
2017167819.tif 000005
【図４】
2017167819.tif 000006
【図５】
2017167819.tif 000007
【図６】
2017167819.tif 000008
【図７】
2017167819.tif 000009
【図８】
2017167819.tif 000010
【図９】
2017167819.tif 000011
【図１０】
2017167819.tif 000012
【図１１】
2017167819.tif 000013
【図１２】
2017167819.tif 000014
【図１３】
2017167819.tif 000015
【図１４】
2017167819.tif 000016
【図１５】
2017167819.tif 000017
【図１６】
2017167819.tif 000018
【図１７】
2017167819.tif 000019
【図１８】
2017167819.tif 000020
【図１９】
2017167819.tif 000021
【図２０】
2017167819.tif 000022
【図２１】
2017167819.tif 000023
【図２２】
2017167819.tif 000024
【図２３】
2017167819.tif 000025
【図２４】
2017167819.tif 000026
【図２５】
2017167819.tif 000027
【図２６】
2017167819.tif 000028