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