(57)【要約】  ストレージシステムが、物理アドレス空間を構成する複数の物理領域から、それぞれ断片空き領域を含んだ1以上の追記不可物理領域を1以上のコピー元物理領域として選択し、且つ、追記可能物理領域をコピー先物理領域として選択する。ストレージシステムは、選択された1以上のコピー元物理領域内の1以上の生存データを、選択されたコピー先物理領域の空き領域の先頭からシーケンシャルに、ストリップ単位又はストライプ単位に書き込む。書込み対象データのサイズがストリップ単位又はストライプ単位の書込みに必要なサイズに満たない場合、ストレージシステムは、その書込み対象データに対してパディングを行うことで、その書込み対象データをストリップ単位又はストライプ単位で書き込む。
2016181481.tif 000002
【特許請求の範囲】
【請求項１】
1以上のRAIDグループを含む複数の物理記憶デバイスと、
前記複数の物理記憶デバイスに接続されプロセッサ及び記憶部を含んだコントローラと
を有し、
前記1以上のRAIDグループの各々の領域は、複数のストライプに分割されており、前記複数のストライプの各々は、複数の物理記憶デバイスにそれぞれ対応した複数の領域である複数のストリップで構成されており、
前記1以上のRAIDグループの各々のRAID構成は、ストライプ毎にパリティが必要なRAID構成であり、
論理アドレス空間の論理アドレスと、前記1以上のRAIDグループについての物理アドレス空間の物理アドレスとの間のアドレス変換のために前記コントローラにより参照される情報であるアドレス変換情報が、前記記憶部と物理記憶デバイスとのうちの少なくとも1つに存在し、
前記物理アドレス空間には、前記コントローラによりデータが追記的に書き込まれるようになっており、
前記物理アドレス空間には、更新、圧縮及び排除のうちのいずれかの対象のデータである旧データが前記コントローラにより無効化されることにより断片空き領域が生じるようになっており、
前記コントローラが、前記アドレス変換情報を用いてコピーGC（ガベージコレクション）処理を実行し、
前記コピーGC処理が、
（Ａ）前記物理アドレス空間を構成する複数の領域である複数の物理領域から、それぞれ断片空き領域を含んだ1以上の追記不可物理領域を1以上のコピー元物理領域として選択すること、
（Ｂ）前記複数の物理領域から、追記可能物理領域をコピー先物理領域として選択すること、
（Ｃ）前記選択された1以上のコピー元物理領域内の1以上の生存データを、前記選択されたコピー先物理領域の空き領域の先頭からシーケンシャルに、ストリップ単位又はストライプ単位に書き込むこと
を含み、
（Ｃ）において、前記コントローラが、書込み対象データのサイズがストリップ単位又はストライプ単位の書込みに必要なサイズに満たない場合、その書込み対象データに対してパディングを行うことで、その書込み対象データをストリップ単位又はストライプ単位で書き込む、
ストレージシステム。
【請求項２】
（Ｃ）において、前記コントローラは、
前記1以上の生存データのうちの最後の書込み対象データ以外の書込み対象データを、パディング無しにストライプ単位で書込み、
前記1以上の生存データのうちの最後の書込み対象データのサイズがストリップ単位又はストライプ単位の書込みに必要なサイズに満たない場合にのみ、ストリップ単位又はストライプ単位の書き込みためのパディングを行う、
請求項1記載のストレージシステム。
【請求項３】
パディングされるデータのサイズは、ストリップサイズ未満である、
請求項2記載のストレージシステム。
【請求項４】
前記コントローラは、物理アドレス順に断片空き領域を含んだ物理領域を探索し見つかった物理領域をコピー元物理領域として選択するモードである領域前方探索モードと、コピー元物理領域となることの利得及びコストを基に算出されたGC効率が比較的高い物理領域を探索し見つかった物理領域をコピー元物理領域として選択するモードである高GC効率領域探索モードとのうちのいずれかのモードを選択し、
（Ａ）は、選択されたモードに従いコピー元物理領域を選択することである、
請求項1記載のストレージシステム。
【請求項５】
前記コントローラは、前記アドレス変換情報が前記メモリにあれば、前記高GC効率領域探索モードを選択する、
請求項4記載のストレージシステム。
【請求項６】
前記コントローラは、前記アドレス変換情報が前記メモリになくても、前記物理アドレス空間に対応したRAIDグループを構成する物理記憶デバイスが追記型デバイスでなければ、前記高GC効率領域探索モードを選択する、
請求項5記載のストレージシステム。
【請求項７】
前記コントローラは、前記アドレス変換情報が前記メモリになくても、前記物理アドレス空間に対応したRAIDグループを構成する物理記憶デバイスが追記型デバイスでなく、且つ、前記物理アドレス空間に関しデータ年齢に対するアクセス頻度低下変動の速度が比較的遅ければ、前記高GC効率領域探索モードを選択する、
請求項6記載のストレージシステム。
【請求項８】
前記コントローラは、前記アドレス変換情報が前記メモリになければ、前記領域前方探索モードを選択する、
請求項4記載のストレージシステム。
【請求項９】
前記コントローラは、前記アドレス変換情報が前記メモリにあっても、前記物理アドレス空間に対応したRAIDグループを構成する物理記憶デバイスが追記型デバイスであれば、前記領域前方探索モードを選択する、
請求項8記載のストレージシステム。
【請求項１０】
前記コントローラは、前記アドレス変換情報が前記メモリにあり、且つ、前記物理アドレス空間に対応したRAIDグループを構成する物理記憶デバイスが追記型デバイスでなくても、前記物理アドレス空間に関しデータ年齢に対するアクセス頻度低下変動の速度が比較的早ければ、前記領域前方探索モードを選択する、
請求項9記載のストレージシステム。
【請求項１１】
前記コントローラは、前記物理アドレス空間に対応したRAIDグループを構成する物理記憶デバイスが追記型デバイスでなければ、前記高GC効率領域探索モードを選択し、前記物理アドレス空間に対応したRAIDグループを構成する物理記憶デバイスが追記型デバイスであれば、前記領域前方探索モードを選択する、
請求項4記載のストレージシステム。
【請求項１２】
前記コントローラは、前記物理アドレス空間に関しデータ年齢に対するアクセス頻度低下変動の速度が比較的遅ければ、前記高GC効率領域探索モードを選択し、前記物理アドレス空間に関しデータ年齢に対するアクセス頻度低下変動の速度が比較的早ければ、前記領域前方探索モードを選択する、
請求項4記載のストレージシステム。
【請求項１３】
前記コントローラは、前記物理アドレス空間に存在するデータを更新、圧縮又は重複排除することにより前記既存データを無効化した結果として、その無効化されたデータの領域を含んだ物理領域が新たに空き物理領域になった場合、追記先物理アドレスを、その新たな空き物理領域の先頭に変更する、
請求項1記載のストレージシステム。
【請求項１４】
前記物理アドレス空間は、複数の追記型デバイスで構成されたRAIDグループに対応しており、
前記複数の追記型デバイスの各々は、複数のドライブ追記領域を有しており、
前記複数のドライブ追記領域の各々は、データがアドレス順に書き込まれるべき記憶領域であり、
前記物理アドレス空間内の前記複数の物理領域に、それぞれ、異なる複数のドライブ追記領域セットが対応付けられており、
前記複数のドライブ追記領域セットの各々は、前記複数の追記型デバイスがそれぞれ有する複数のドライブ追記領域である、
請求項1記載のストレージシステム。
【請求項１５】
ストレージシステムの記憶制御方法であって、
前記ストレージシステムが、
1以上のRAIDグループを含む複数の物理記憶デバイスと、
前記複数の物理記憶デバイスに接続されプロセッサ及び記憶部を含んだコントローラと
を有し、
前記1以上のRAIDグループの各々の領域は、複数のストライプに分割されており、前記複数のストライプの各々は、複数の物理記憶デバイスにそれぞれ対応した複数の領域である複数のストリップで構成されており、
前記1以上のRAIDグループの各々のRAID構成は、ストライプ毎にパリティが必要なRAID構成であり、
論理アドレス空間の論理アドレスと、前記1以上のRAIDグループについての物理アドレス空間の物理アドレスとの間のアドレス変換のために前記コントローラにより参照される情報であるアドレス変換情報が、前記記憶部と物理記憶デバイスとのうちの少なくとも1つに存在し、
前記物理アドレス空間には、前記コントローラによりデータが追記的に書き込まれるようになっており、
前記物理アドレス空間には、更新、圧縮及び排除のうちのいずれかの対象のデータである旧データが前記コントローラにより無効化されることにより断片空き領域が生じるようになっており、
前記記憶制御方法が、
（Ａ）前記アドレス変換情報を参照して、前記物理アドレス空間を構成する複数の領域である複数の物理領域から、それぞれ断片空き領域を含んだ1以上の追記不可物理領域を1以上のコピー元物理領域として選択し、
（Ｂ）前記アドレス変換情報を参照して、前記複数の物理領域から、追記可能物理領域をコピー先物理領域として選択し、
（Ｃ）前記選択された1以上のコピー元物理領域内の1以上の生存データを、前記選択されたコピー先物理領域の空き領域の先頭からシーケンシャルに、ストリップ単位又はストライプ単位に書き込み、書込み対象データのサイズがストリップ単位又はストライプ単位の書込みに必要なサイズに満たない場合、その書込み対象データに対してパディングを行うことで、その書込み対象データをストリップ単位又はストライプ単位で書き込む、
記憶制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、ストレージシステムにおけるガベージコレクションに関する。
【背景技術】
【０００２】
ストレージシステムへのコスト低減要求は高く、当該システムに格納されるデータの量を低減することができる算術圧縮や重複排除に対する期待は大きい。【０００３】
算術圧縮が適用されたデータは、元のデータとは異なるサイズとなり、結果として、元のデータの論理アドレス範囲のサイズと、圧縮データの物理アドレス範囲のサイズとが異なる。また、重複排除が適用された場合、重複する複数のデータのうちの少なくとも1つの重複データが削除され、削除された重複データの論理アドレスに、残ったデータの物理アドレスが関連付けられる。これらのことから、算術圧縮及び重複排除のうちの少なくとも1つを採用するストレージシステムは、論理アドレスとは異なる物理アドレスに追記的に書込む方式であるログ構造化方式を採用する（ログ構造化方式は、算術圧縮及び重複排除のいずれも採用しないストレージシステムにおいて採用されてもよい）。【０００４】
ログ構造化方式では、既に格納されているデータの少なくとも一部を更新する更新書込み、互いに重複した複数のデータのうちの少なくとも1つのデータを排除する重複排除、及び、既に格納されているデータを圧縮する算術圧縮（ポストプロセスの算術圧縮）での旧データ（例えば、更新書込みによる更新前のデータ、重複排除により排除対象とされたデータ、及び、算術圧縮前のデータのうちのいずれかに該当するデータ）の格納領域が無効となる。無効化された領域は、空き領域となるため、このような無効化は、空き領域の断片化の原因となる。そこで、ログ構造化方式を採用するストレージシステムは、断片化空き領域（断片化無効領域）の回収を行うガベージコレクション（GC）を必要とする。【０００５】
特許文献1は、GCの制御方法に関する。特許文献1の技術は、物理アドレスから論理アドレスを導出するための物論テーブルを用いて有効データ（無効ではない生存データ）を特定し、論理アドレスから物理アドレスを導出する論物テーブルを用いて有効データの論理アドレスを特定し、有効データを別領域にコピーし、コピー先の物理アドレスと有効データの論理アドレスとを関連付けるよう物論テーブル及び論物テーブルを更新する。【０００６】
また、非特許文献1の技術は、物理アドレス空間を一定の大きさを持つセグメントに分割し、GC効率の高いセグメントをコピー元として選定できる。具体的には、非特許文献1の技術は、セグメント毎に、得られるGC効率を数1で形式化し、GC効率の高いセグメントをコピー元として選定する。なお、数1は、GC効率の考え方を意味する式であり、具体的には、セグメント内のコピー対象データの量である生存データ量（live data space）をコストuとし、セグメントの古さを示す係数a（age）をかけたセグメント空き容量（1-u）（free space）をセグメント利得（benefit）とし、コストに対する利得をGC効率（benefit / cost）としている。ここで、セグメントの古さは、セグメント内のデータのタイムスタンプの平均などである。
（数1）benefit / cost = free space * age / live data space = (1-u) * a / u
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】US 8,527,544
【非特許文献】
【０００８】
【非特許文献１】Rosenblum, M., & Ousterhout, J. K. (1992). The design and implementation of a log-structured file system. ACM Transactions on Computer Systems (TOCS), 10(1), 26-52.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献1の技術でGCを制御し、非特許文献1の技術でGC効率の高いセグメントを選定したとしても、ストレージシステムにおける高いGC効率を必ずしも実現できない。その理由の一例は、次の通りである。すなわち、RAIDレベルとして、1つのストライプにつき少なくとも1つのパリティを必要とするRAIDレベル（例えばRAID5、RAID6）が、そのようなRAIDレベルでは、パリティの読出しのためにGC効率が減少し得る。具体的には、例えば、1つのストライプを構成する1つのストリップ内の旧データの一部を更新するデータ書込みでは、ストレージシステム内のコントローラが、旧パリティ（既に格納されているパリティ）及び旧データをそれぞれドライブデバイスから読み出す必要がある。この場合、旧データの一部を更新することで新データを生成し、新データと旧パリティを用いた算術演算により新パリティを生成する。【００１０】
このような課題は、算術圧縮及び重複排除の少なくとも1つが採用されているか否かに関わらずログ構造化方式が採用されている他のストレージシステムについても有り得る。
【課題を解決するための手段】
【００１１】
ストレージシステムが、1以上のRAIDグループを含む複数の物理記憶デバイスと、複数の物理記憶デバイスに接続されプロセッサ及び記憶部を含んだコントローラとを有する。1以上のRAIDグループの各々の領域は、複数のストライプに分割されている。複数のストライプの各々は、複数の物理記憶デバイスにそれぞれ対応した複数の領域である複数のストリップで構成されている。1以上のRAIDグループの各々のRAID構成は、ストライプ毎にパリティが必要なRAID構成である。論理アドレス空間の論理アドレスと、1以上のRAIDグループについての物理アドレス空間の物理アドレスとの間のアドレス変換のためにコントローラにより参照される情報であるアドレス変換情報が、記憶部と物理記憶デバイスとのうちの少なくとも1つに存在する。物理アドレス空間には、コントローラによりデータが追記的に書き込まれるようになっている。物理アドレス空間には、更新、圧縮及び排除のうちのいずれかの対象のデータである旧データが前記コントローラにより無効化されることにより断片空き領域が生じるようになっている。コントローラが、アドレス変換情報を用いてコピーGC（ガベージコレクション）処理を実行する。コピーGC処理が、（Ａ）物理アドレス空間を構成する複数の領域である複数の物理領域から、それぞれ断片空き領域を含んだ1以上の追記不可物理領域を1以上のコピー元物理領域として選択すること、（Ｂ）複数の物理領域から、追記可能物理領域をコピー先物理領域として選択すること、（Ｃ）選択された1以上のコピー元物理領域内の1以上の生存データを、選択されたコピー先物理領域の空き領域の先頭からシーケンシャルに、ストリップ単位又はストライプ単位に書き込むことを含む。（Ｃ）において、コントローラが、書込み対象データのサイズがストリップ単位又はストライプ単位の書込みに必要なサイズに満たない場合、その書込み対象データに対してパディングを行うことで、その書込み対象データをストリップ単位又はストライプ単位で書き込む。
【発明の効果】
【００１２】
ストレージシステムにおけるGCの性能を向上できる。
【図面の簡単な説明】
【００１３】
【図１】実施例1に係るストレージシステムの構成例を示す。
【図２】ログ構造化方式によるRAIDグループへのデータ格納の一例を示す。
【図３】論物テーブル及び物論テーブルのそれぞれの構成例を示す。
【図４】実施例1に係るGCの処理フローの一例を示す。
【図５】実施例2に係るストレージシステムの構成例を示す。
【図６】コピー元選択の処理フローの一例を支援す。
【図７】GC効率分布の一例を示す。
【図８】GC効率分布の別の一例を示す。
【図９】実施例3に係るThreading GCの説明図である。
【図１０】実施例3に係るCopying GCの説明図である。
【図１１】実施例4に係る物理アドレス空間内のページのサイズと実施例4に係るSMRドライブのブロックのサイズの関係の一例を示す。
【発明を実行するための形態】
【００１４】
以下、幾つかの実施例を説明する。
【００１５】
以下の説明では、「xxxテーブル」の表現にて情報を説明することがあるが、情報は、どのようなデータ構造で表現されていてもよい。すなわち、情報がデータ構造に依存しないことを示すために、「xxxテーブル」を「xxx情報」と呼ぶことができる。また、以下の説明において、各テーブルの構成は一例であり、1つのテーブルは、2以上のテーブルに分割されてもよいし、2以上のテーブルの全部又は一部が1つのテーブルであってもよい。
【００１６】
また、以下の説明では、同種の要素を区別しないで説明する場合には、参照符号又は参照符号における共通番号を使用し、同種の要素を区別して説明する場合は、その要素の参照符号を使用又は参照符号に代えてその要素に割り振られたIDを使用することがある。
【００１７】
また、以下の説明では、「記憶部」は、メモリを含んだ1以上の記憶デバイスでよい。例えば、記憶部は、主記憶デバイス（典型的には揮発性のメモリ）及び補助記憶デバイス（典型的には不揮発性の記憶デバイス）のうちの少なくとも主記憶デバイスでよい。
【００１８】
また、以下の説明では、「PDEV」は、物理的な記憶デバイスを示し、典型的には、不揮発性の記憶デバイス（例えば補助記憶デバイス）でよい。PDEVは、例えば、HDD（Hard Disk Drive）又はSSD（Solid State Drive)でよい。なお、以下の実施例では、PDEVは、「ドライブデバイス」と呼ばれる。
【００１９】
また、以下の説明では、「RAID」は、Redundant Array of Independent (or Inexpensive) Disksの略である。RAIDグループは、複数のドライブデバイスで構成され、そのRAIDグループに関連付けられたRAIDレベルに従いデータを記憶する。RAIDグループは、パリティグループと呼ばれてもよい。パリティグループは、例えば、パリティを格納するRAIDグループのことでよい。
【００２０】
また、以下の説明では、コンピュータプログラムを主語として処理を説明する場合があるが、プログラムは、プロセッサ（例えばCPU（Central Processing Unit））によって実行されることで、定められた処理を、適宜に記憶部（例えばメモリ）及び／又はインターフェースデバイス（例えば通信ポート）等を用いながら行うため、処理の主語がプロセッサとされてもよい。プログラムを主語として説明された処理は、プロセッサあるいはそのプロセッサを有する装置又はシステムが行う処理としてもよい。また、プロセッサは、処理の一部または全部を行うハードウェア回路を含んでもよい。プログラムは、プログラムソースから計算機のような装置にインストールされてもよい。プログラムソースは、例えば、プログラム配布サーバまたは計算機が読み取り可能な記憶メディアであってもよい。プログラムソースがプログラム配布サーバの場合、プログラム配布サーバはプロセッサ（例えばＣＰＵ）と記憶部を含み、記憶部はさらに配布プログラムと配布対象であるプログラムとを記憶してよい。そして、プログラム配布サーバのプロセッサが配布プログラムを実行することで、プログラム配布サーバのプロセッサは配布対象のプログラムを他の計算機に配布してよい。また、以下の説明において、2以上のプログラムが1つのプログラムとして実現されてもよいし、1つのプログラムが2以上のプログラムとして実現されてもよい。
【００２１】
また、以下の説明では、「VOL」は、論理ボリュームの略であり、論理的な記憶デバイスでよい。VOLは、実体的なVOL（RVOL）であってもよいし、仮想的なVOL（VVOL）であってもよい。また、VOLは、そのVOLを提供するストレージシステムに接続されているホストシステムに提供されるオンラインVOLと、ホストシステムには提供されない（ホストシステムからは認識されない）オフラインVOLとがあってよい。「RVOL」は、そのRVOLを有するストレージシステムが有するドライブデバイス（例えば、1以上のRAIDグループ）に基づくVOLでよい。「VVOL」としては、外部接続VOL（EVOL）と、容量拡張VOL（TPVOL）と、スナップショットVOLとのうちの少なくとも1種類でよい。EVOLは、外部のストレージシステムの記憶空間（例えばVOL）に基づいておりストレージ仮想化技術に従うVOLでよい。TPVOLは、複数の仮想領域（仮想的な記憶領域）で構成されており容量仮想化技術（典型的にはThin Provisioning）に従うVOLでよい。スナップショットVOLは、オリジナルのVOLのスナップショットとして提供されるVOLでよい。TPVOLは、典型的にはオンラインVOLでよい。スナップショットVOLは、RVOLであってもよい。「プール」は、論理的な記憶領域（例えば複数のプールＶＯＬの集合）であり、用途ごとに用意されてよい。例えば、プールとして、TPプールと、スナップショットプールとのうちの少なくとも1種類があってよい。TPプールは、複数の実領域（実体的な記憶領域）で構成された記憶領域でよい。TPプールからTPVOLの仮想領域に実領域が割り当てられてよい（例えば、TPVOLのライト先仮想領域に実領域が割り当てられていない場合にTPプールからそのライト先仮想領域に未割当ての実領域が割り当てられてよい）。スナップショットプールは、オリジナルのVOLから退避されたデータが格納される記憶領域でよい。1つのプールが、TPプールとしてもスナップショットプールとしても使用されてもよい。「プールVOL」は、プールの構成要素となるVOLでよい。プールVOLは、RVOLであってもよいしEVOLであってもよい。プールVOLは、典型的にはオフラインVOLでよい。
【実施例１】
【００２２】
図1は、実施例1に係るストレージシステムの構成例を示す。【００２３】
クライアント（ホストシステムの一例）1は、ネットワーク3を介して、ストレージシステム2が提供するデータサービスの提供を受ける。クライアント1は複数台であってもよく、図1では、クライアント1として、クライアント1a及び1bが示されている。ネットワーク3は、イントラネットワークでよいが、ネットワークスイッチを介してクライアント1とストレージシステム2を接続するインターネット又はLAN（Local Area Network）でもよいし、SAN（Storage Area Network）でもよい。【００２４】
ストレージシステム2は、クライアント1から送信されるデータを格納し（クライアント1から受信した書込み要求に付随する書込み対象のデータを格納し）、また、クライアント1に格納データを提供する（クライアント1から受信した読出し要求に従う読出し対象のデータをクライアント1に提供する）。ストレージシステム2は、複数台のストレージ装置で構成されてもよいが、図1では、ストレージシステム2は、1台のストレージ装置で構成されている。また、ストレージシステム2は、様々なデータサービスを提供できる。データサービスとして、例えば、ストレージ装置内のデータコピー、ストレージ装置間のデータリモートコピー、スナップショット取得等がある。【００２５】
ストレージシステム2は、複数のドライブデバイス（以下、ドライブ）111と、複数のドライブ111（及びクライアント1）に接続されたコントローラとを有する。【００２６】
ドライブ111は、クライアント1からのデータの少なくとも一部を格納する。複数のドライブ111は、複数（又は1つ）のRAIDグループ104を構成する。複数のRAIDグループ104として、図1では、RAIDグループ104a及び104bが示されている。RAIDグループ104aは、一例として、4台のドライブ111a〜111dを有しているが、RAIDグループ104a以外のRAIDグループ104のうちの少なくとも1つは、RAIDグループ104aと異なる構成でもよい。【００２７】
コントローラは、プロセッサ101、ネットワークインタフェース102及びメモリ（記憶部の一例）103を含む。プロセッサ101は、メモリ103に展開されたプログラムの演算を実行する。ネットワークインタフェース102は、ネットワーク3と接続するためのインタフェースである。メモリ103に展開されるプログラムとして、例えば、OS（Operating System）201、スケジューラ202、VOLコントローラ203、算術圧縮204、重複排除205、及び、GC（ガベージコレクション）206がある。プロセッサ101が行う処理の少なくとも一部、例えば、算術圧縮及び重複排除のうちの少なくとも1つが、プロセッサ101に代えてハードウェア回路（例えばASIC（Application Specific Integrated Circuit）又はFPGA（Field-Programmable Gate Array））により行われてもよい。メモリ103は、RAIDグループ104に書き込まれるデータやRAIDグループ104から読み出されたデータが一時的に書き込まれるキャッシュメモリとしても使用される。【００２８】
OS201は、他のプログラムが動作するための基本的な機能であるメモリへのロード機能等を提供する。スケジューラ202は、VOLコントローラ203、算術圧縮204、重複排除205及びGC206の動作タイミングを制御する。【００２９】
VOLコントローラ203は、RAIDグループ104の管理や、RAIDグループ104へのクライアント1からの書込み対象データの格納、及び、クライアント1からの読出し要求に応じた格納データの読み出しを制御する。具体的には、例えば、VOLコントローラ203は、論理アドレス空間（論理空間）と物理アドレス空間（物理空間）とを管理する。論理アドレス空間は、クライアント1に提供されるRVOLとしての空間であってもよいし、クライアント1に提供されたTPVOLに関連付けられるプールの空間でもよい。物理アドレス空間は、論理アドレス空間に関連付けられているRAIDグループの物理アドレスの空間でよい。VOLコントローラ203は、ログ構造化方式に従う書込みを実行する。例えば、VOLコントローラ203は、第1データの次の書込み対象が第2データの場合、論理アドレス空間において第2データが第1データと離れていても、物理アドレス空間において第1データと第2データ間に空きが生じないようにする。なお、本実施例の説明において、物理アドレス空間にデータを書き込むということは、詳細には、そのデータの書込み先物理アドレスに対応した領域（RAIDグループ104内の領域）を提供する1以上のドライブ111にそのデータを書き込むことに相当する。【００３０】
算術圧縮204は、クライアント1からの書込み対象データに算術圧縮を実行する。なお、算術圧縮204は、算術圧縮をインラインとポストプロセスのいずれで実施してもよい。インラインの場合、算術圧縮204は、クライアント1の書込み要求に従う書込み処理の最中に、算術圧縮を実行する。ポストプロセスの場合、算術圧縮204は、一旦クライアント1からの書込み対象データをドライブ111に書込み、その後非同期に、ドライブ111から対象のデータをメモリ103に読み出し、算術圧縮を実施し、当該圧縮後データを物理アドレス空間に書込む。【００３１】
重複排除205は、ドライブ111に格納されたデータ間の重複（同一性）をチェックし、重複データのうちの少なくとも1つを残しその重複データのうちの残りを削除する。なお、重複排除205は、重複排除をインラインとポストプロセスのいずれで実施してもよい。インラインの場合、重複排除205は、クライアント1からの書込み要求に従う書込み処理の最中に、重複排除を実行する。ポストプロセスの場合、重複排除205は、一旦クライアント1からの書込み対象データをドライブ111に書込み、その後非同期に、ドライブ111から対象のデータをメモリ103に読み出し、重複排除を実行する。また、インラインの場合、重複排除205は、データ間の同一性のチェックに用いるトークンの計算を行い、排除そのものはクライアント1の書込みと非同期に実施してもよい。なお、トークンは、データをハッシュ関数に適用することにより得られたハッシュ値でよい。【００３２】
更新書込み、重複排除、及び、ポストプロセスで実施される算術圧縮後のデータの書込みのうちのいずれにおいても、物理アドレス空間において旧データ（例えば、更新書込みにより更新されたデータ、重複排除により排除対象となった重複データ、及び、算術圧縮前のデータのうちのいずれかに該当するデータ）が格納されている領域は無効化される。GC206は、更新書込み、重複排除、及び、ポストプロセスで実施される算術圧縮により発生した空き領域（無効領域）を回収するGCを実行する。【００３３】
続けて、図2を用いて、ログ構造化方式によるRAIDグループ104aへのデータ格納の一例を述べる。【００３４】
RAIDグループ104aは、3つのデータに対して1つのパリティを格納するRAID構成（RAID5（3D+1P））を有する。RAIDグループ104aが提供する領域が複数のストライプ304に分割される。ストライプ304は、RAIDグループ104aを構成するドライブ111a〜111dがそれぞれ提供する複数のストリップ303で構成されている。ストリップ303は、ドライブ111が提供する単位領域である。ドライブ111が提供する領域は、複数のストリップ303に分割される。ストリップサイズは、例えば512KBである。ページ305が、複数のストライプ304に対応する。ページ305は、物理アドレス空間302における単位領域である。つまり、物理アドレス空間302が、複数のページ305に分割されていてもよい。ページ305が物理的な単位領域である場合、例えば、例えばプールにおける実領域が、論理アドレス空間301における単位領域であってもよい。ページ305のサイズは、典型的には、ページ305に対応するストライプ数とストライプサイズの積より小さい（パリティが格納されるストリップのサイズがカウントされないためである）。なお、以下の説明では、ストリップ単位のデータを「ストリップデータ」と言い、ストライプ単位のデータ（正確には、ストライプサイズからパリティ分のストリップサイズを除いたサイズのデータ）を「ストライプデータ」と言い、ページ単位のデータを「ページデータ」と言うことができる。【００３５】
RAIDグループ104aを構成するドライブ111の数を変更することができる。例えば、RAIDレベルはRAID5のままで、3つのデータに対して1つのパリティを付与する3D+1Pの構成から、7つのデータに対して1つのパリティを付与する7D+1Pの構成に変更することができる。ページ305のサイズは、複数のRAIDグループ104にそれぞれ対応した複数のRAID構成（xD+yP）のうちのデータ数（x）の公倍数でよい。例えば、複数のRAIDグループ104が、RAID5（3D+1P）のRAIDグループと、RAID5（7D+1P）のRAIDグループの場合、ページ305のサイズは、42MBでよい。42は、RAID5（3D+1P）のデータ数である3と、RAID5（7D+1P）のデータ数である7の公倍数である。【００３６】
論理アドレス空間301は、例えばクライアント1向けのアドレス空間（例えばRVOL）である。VOLコントローラ203は、論理アドレス空間301においてデータ0〜3の論理アドレス範囲とデータ5〜6の論理アドレス範囲が離れていても、物理アドレス空間（論理アドレス空間301と異なるアドレス体系の空間）302において、データ5〜6の物理アドレス範囲を、データ0〜3の物理アドレス範囲の次とする（データ0〜3の物理アドレス範囲とデータ5〜6の物理アドレス範囲の間に空き領域が生じないようにする）。具体的には、例えば、データ0〜3及び5〜6の書込み先は、物理アドレス空間302の先頭から連続した領域とされる。データ0〜3及び5〜6は、実際には、それぞれ、物理アドレス空間302における物理アドレスと対応する位置（RAIDグループ104内の領域）に書き込まれる。【００３７】
更新書込み、ポストプロセスで実施される算術圧縮204による圧縮後データの書込みも同様である。例えば、図2におけるデータ0を更新する場合、新データ（更新後データ）0’は、物理アドレス空間202においてデータ6に対して詰められ（データ6の次に追記され）、旧データ0の格納領域（物理アドレス範囲）は無効化される。また、重複排除205により、例えば、互いに重複するデータ1とデータ5のうちのデータ5が排除対象となれば、旧データ5の格納領域は無効化される。【００３８】
RAIDグループ104aには、データは、ストリップ303を単位に書き込まれる。具体的には、例えば、ドライブ111aのストリップ303に、物理アドレス空間におけるデータ0〜3及び5〜6を含むデータのうちの先頭のストリップデータが書き込まれ、ドライブ111bのストリップ303に、その先頭のストリップデータの次のストリップデータ（先頭のストリップデータの物理アドレスの次の物理アドレスのストリップデータ）が書き込まれる。そして、3つのドライブ111a〜111cにそれぞれ書き込まれる3つのストリップデータに基づくパリティ（ストリップサイズ）が、ドライブ111dに書き込まれる。【００３９】
続けて、図3を用いて、論物テーブルT1及び物論テーブルT2について説明する。【００４０】
論物テーブルT1は、論物変換情報の一例であり、論理アドレスを物理アドレスへ変換するためのアドレス変換テーブルである。物論テーブルT2は、物論変換情報の一例であり、物理アドレスを論理アドレスへ変換するためのアドレス変換テーブルである。好ましくは、論物テーブルT1及び物論テーブルT2のうちの少なくとも1つのテーブルの全てがメモリ103に格納されることであるが、テーブルのサイズが大きい等の理由から、論物テーブルT1及び物論テーブルT2の少なくとも一部が少なくとも1つのドライブ111に格納されてもよい。【００４１】
論物テーブルT1は、論理アドレス毎にエントリを有し、各エントリに、論理アドレス、物理アドレス、サイズ及びハッシュ値が登録される。なお、論物テーブルT1に登録される情報の種類はこれらに限定しないでよい。一方、物論テーブルT2は、物理アドレス毎にエントリを有し、各エントリに、物理アドレス、論理アドレス及びサイズが登録される。なお、物論テーブルT2に登録される情報の種類もこれらに限定しないでよい。例えば、図3では、論物テーブルT1は論理アドレスを持つが、論理アドレスの管理単位を固定のブロックサイズとし、論理アドレス順に整列することで、論理アドレスの登録は不要となり、論物テーブルT1は、物理アドレス、サイズ及びハッシュ値さえ持てばよい。また、算術圧縮及び重複排除が採用されない場合、サイズは、クライアント1からの書込みの単位サイズであり、可変ではないため、サイズも論物テーブルT1に登録されないでもよい。同様に、図3では、物論テーブルT2は、物理アドレスを持つが、物理アドレスの管理単位を固定のブロックサイズとし、物理アドレス順に整列することで、物理アドレスの登録は不要となり、物論テーブルT2は、論理アドレスとサイズさえ持てばよい。さらに、物論テーブルT2においては、物理アドレスに対応する論理アドレスに対応したサイズを論物テーブルT1から知ることができるため、サイズは、物論テーブルT2及び論物テーブルT1の一方に登録されればよい。なお、固定のブロックサイズとは、例えば、512B又は4KBである。また、図3では、論物テーブルT1にハッシュ値が登録されるが、論理アドレスとハッシュ値を組とする別テーブルが用意されてもよい。その場合、ハッシュ値をキーとするB-Tree形式といった実装形態を取ることができるため、重複排除205の処理負荷の軽減が期待される。【００４２】
通常の書込みにおいて、VOLコントローラ203は、クライアント1からの書込み要求に従う書込み対象のデータをメモリ103にキャッシュし、追記の最終アドレスを当該データ用の物理アドレスとして決定し、当該物理アドレスの指す位置（RAIDグループ104内の領域）にデータを書込み、論物テーブルT1及び物論テーブルT2を更新する。【００４３】
更新書込みにおいて、VOLコントローラ203は、クライアント1からの書込み要求に従う書込み対象のデータをメモリ103にキャッシュし、そのデータを基いて旧データを更新することにより得られる新データの物理アドレスを決定する。VOLコントローラ203は、当該物理アドレスの指す位置（RAIDグループ104内の領域）に新データを書込む。VOLコントローラ203は、論物テーブルT1及び物論テーブルT2から、それぞれ、旧データに関する削除し、新データに関する情報を、論物テーブルT1及び物論テーブルT2にそれぞれ登録する。例えば、論理アドレスが「0x100」及びサイズが「2」である旧データ（更新前データ）が更新される場合、論物テーブルT1の論理アドレス「0x100」を含んだエントリにおいて、物理アドレスは「9」（新データの物理アドレス）に更新され、サイズは「2」（新データは旧データの更新後データであるため同じサイズ）のままであり、ハッシュ値は、新データのハッシュ値に更新される。また、物論テーブルT2から、旧データの物理アドレス「0」のエントリ（エントリの情報）が削除され、新たに、物論テーブルT2のエントリに、物理アドレス「9」、論理アドレス「0x100」及びサイズ「2」が登録される。この結果、物理アドレス「0」の領域が無効領域となる。【００４４】
ポストプロセス算術圧縮において、算術圧縮204は、対象のデータをメモリ103にキャッシュし、算術圧縮し、物理アドレスを決定し、当該物理アドレスの指す位置（RAIDグループ104内の領域）にデータを書き込む。算術圧縮204は、論物テーブルT1及び物論テーブルT2から、旧データ（算術圧縮前のデータ）に関する情報を削除し、圧縮後のデータに関する情報を、論物テーブルT1及び物論テーブルT2に登録する。例えば、図3にて論理アドレスが「0x100」及びサイズが「2」であるデータが算術圧縮され、新データ（圧縮後データ）のサイズが「1」となる場合、論物テーブルT1の論理アドレス「0x100」を含んだエントリにおいて、物理アドレスは「9」（新データの物理アドレス）、サイズは「1」、ハッシュ値は、圧縮後データのハッシュ値となる。また、物論テーブルT2から、旧データの物理アドレス「0」のエントリが削除され、新たに、物論テーブルT2のエントリに、物理アドレス「9」、論理アドレス「0x100」及びサイズ「1」が登録される。【００４５】
重複排除において、重複排除205は、対象のデータをメモリ103にキャッシュし、ハッシュ値を導出し、導出したハッシュ値と同一のハッシュ値を論物テーブルT1から検索する。重複排除205は、同一ハッシュ値が見つかった場合、論物テーブルT1及び物論テーブルT2を更新する。例えば、図3にて、論理アドレスが「0x100」及びサイズが「2」である第1データと論理アドレスが「0x300」及びサイズが「2」である第2データが同一であり、第2データを排除する場合、論物テーブルT1の論理アドレス「0x300」のエントリにおいて、物理アドレスは「0」（第1データの物理アドレスと同じ）とされる（サイズ及びハッシュ値は変更なし）。物論テーブルT2から、物理アドレス「7」のエントリは削除される。本実施例では、説明を容易にするために、物論テーブルT2の物理アドレス「0」のエントリに、排除対象の第2データの論理アドレス「0x300」が追記されてもよい。但し、これは本実施例の実装を限定するものではなく、例えば物論テーブルT2に関して、各物理アドレスに対して複数の論理アドレスを参照できるように実装してもよい。【００４６】
続けて、GCを説明する。【００４７】
GCとして、Threading GCとCopying GCがある。【００４８】
Threading GCは、更新書込み及び重複排除により生成される断片化した空き領域を、空き領域の位置情報（例えば先頭アドレスとサイズ）をテーブルに登録する等の方法により管理し、クライアント1からの書込み対象のデータの書込み先物理アドレスを、管理している断片空き領域の物理アドレスとする方法である。Threading GCにおいて、データの書込み先物理アドレスとして、そのデータのサイズと同じサイズの空き領域の物理アドレスが探し出されてもよいし、データが分割されることで複数の空き領域のアドレスが複数の書込み先物理アドレスとされてもよい。【００４９】
一方、Copying GCは、断片空き領域を含んだ第1領域内の生存データ（有効データ）を、第1領域と別の第2領域にコピーし、第1領域を連続した空き領域とする方法である。第1領域及び第2領域は、それぞれ、所定サイズの単位領域、例えばページでよい。【００５０】
本実施例に係るストレージシステム2は、Copying GCを採用する。そして、そのCopying GCは、ストリップ単位又はストライプ単位でデータをRAIDグループに書き込むよう改良されており、結果として、GC効率が向上される。GC206は、書込み処理とは非同期に（例えば定期的に）、GCの処理フロー（例えば図4の処理フロー）を開始する。処理フロー開始時に、断片空き領域のあるページが2以上存在していれば、2以上のページをそれぞれコピー元としたCopying GCの実行により、それら2以上のページの各々のを空きページとすることができる。GCの処理フローの開始タイミングは、スケジューラ202により決定される。GCの処理フローの開始の周期を、「GC周期」と言うことができる。GC周期は、短い周期であっても長い周期であってもよい。短い周期の場合、一度のGCでコピー対象となるデータ量が少ないため、GCにかかる時間（TAT（Turn Around Time））は小さいと考えられる。一方、長い周期の場合、一度のGCでコピー対象となるデータ量が多いため、GCのスループットは大きいと考えられる。例えば、クライアント1からのI/Oの頻度（例えば、書込み要求及び読出し要求の受信頻度）が高い場合、GC周期は短いことが好ましいと考えられる。GC周期が長いと、多くの断片空き領域が生じ、I/O性能（特にリード性能）が低下すると考えられるためである。一方で、夜間等のようにクライアント1からのI/Oの頻度が低い場合、GC周期が長くても問題ないと考えられる。GC周期の長さは、管理ポリシ等により決定可能である。【００５１】
本実施例では、Copying GCの処理単位（コピー単位）は、ページ305である。ストレージシステム2が、ページ単位で空き容量を管理しており、ページ単位未満での空き容量確保は、管理上の空き容量確保とはならず、非効率であるためである。【００５２】
図4を用いて、GCの処理フローを説明する。【００５３】
GC206は、全ての対象ページについてGCをしたか否かを判定する（F1）。ここで言う「対象ページ」は、断片空き領域を含んだ追記不可ページである。「追記不可ページ」とは、先頭から終端までデータが書き込まれたページである。追記不可ページは、生存データのみが存在するページと、生存データに加えて断片空き領域が存在するページとがあるが、ここで言う「対象ページ」は、上述したように、断片空き領域を含んだ追記不可ページである。断片空き領域を含んだ追記不可ページは、物論テーブルT2（各エントリの物理アドレス及びサイズ）を参照することにより特定可能である。F1の判定結果が肯定の場合、処理フローが終了する。【００５４】
F1の判定結果が真の場合、GC206は、1つの対象ページをコピー元ページとして選択し、選択した対象ページのページデータをそのままメモリ103にロードする（F2）。このため、F2の結果、メモリ103において、対象ページのページデータが占める領域には、空き領域（無効データが占める領域）が存在する。続けて、GC206は、F2でロードしたページデータ内の生存データを、物論テーブルT2を参照することにより特定する（F3）。GC206は、F2でロードしたページデータから、F3で特定された生存データのみをメモリ103にロード（コピー）する（F4）。続けて、GC206は、F4にてロードした生存データ間の隙間（空き領域）を詰める（F5）。F4及びF5に代えて、GC206は、F4でロードしたページデータから2以上の生存データを物理アドレス順に（換言すれば、追記型であるため時系列の古い順に）、データ間の隙間を空けることなく、メモリ103における別領域にコピーしてよい。この時、GC206は、2以上の生存データを論理アドレス順に整列させてもよい（しかし、論理アドレス順の整列は、多数のデータをメモリにロードする必要があり、短い周期でのGCには向かないと考えられる）。【００５５】
GC206は、F5にて連続して並べられたデータの合計がストライプデータのサイズ以上であるか否か判定する（F6）。【００５６】
F6の判定結果が真の場合、GC206は、メモリ103において連続した1以上の生存データのうちのストライプデータを、コピー先ページに対応した空きストライプに書き込む（F12）。また、GC206は、F12での書き込みに基づき、論物テーブルT1及び物論テーブルT2を更新する（F13）。「コピー先ページ」は、コピー先としてGC206により選択された追記可能ページである。「追記可能ページ」とは、オープンページ（ページの先頭からデータが書き込まれたが終端までデータが書き込まれていないページ）、又は、空きページ（生存データが存在せず空き領域のみ存在するページ）である。GCの処理フローにおける書込み（F12又はF10）において、コピー先ページが無ければ、GC206は、追記可能ページをコピー先ページとして選択する。追記可能ページは、物論テーブルT2から特定可能である。GCの処理フローにおける書込み（F12又はF10）において、GC206は、コピー先ページの先頭空きストライプに、ストライプデータを書き込む。これにより、コピー先ページに物理アドレス順にストライプデータが書き込まれる。【００５７】
F6の後、GC206は、全ての対象ページについてGCをしたか否かを判定する（F7）。F7の判定結果が偽の場合、F2〜F5が行われる。そのF2〜F5では、コピー先ページに未書込みのデータがメモリ103に残っていれば、そのデータの次から、生存データが並べられる。【００５８】
F7の判定結果が真の場合、GC206は、コピー先ページに未書込みのデータがメモリ103に存在しているか否かを判定する（F14）。F14の判定結果が偽の場合、処理フローが終了する。【００５９】
F14の判定結果が真の場合、GC206は、コピー先ページに未だ書き込まれていない未書込みデータ（メモリ103に存在している1以上の生存データ（有効データ））に対してパディングを行うか否かを判定する（F8）。パディング方法は問わないが、本実施例では、ゼロデータ（全ビット値が「0」のデータ）でパディングする方法が採用される。パディングされるデータを、「パディングデータ」と言い、パディングデータのサイズを「パディングサイズ」と言うことができる。F8の判定結果が真となる場合は、例えば、以下の（8-1）〜（8-3）のいずれかに該当する場合である。
（8-1）未書込みデータのサイズが、ストリップサイズ未満である。この場合、パディング無しに、ストリップ単位の書込み及びストライプ単位の書込みのいずれもできない。
（8-2）未書込みデータのサイズが、ストリップサイズ以上であるが、ストリップサイズの整数倍ではない。この場合、パディング無しに、ストリップ単位の書込み及びストライプ単位の書込みのいずれもできない。
（8-3）未書込みデータのサイズが、ストリップサイズ以上且つストリップサイズの整数倍であるが、ストライプ単位の書込みが必要とされる。この場合、パディング無しに、ストライプ単位の書込みをできない。【００６０】
F8の判定結果が真の場合、GC206は、未書込みのデータに対してパディングを行うことで、その未書込みのデータを、m個のストリップデータ（mは、1以上であり、ストライプデータを構成するストライプデータの数未満の整数）、又は、1つのストライプデータとする（F9）。GC206は、m個のストリップデータを、それぞれ、コピー先ページの空きストライプにおけるm個のストリップに書き込む、又は、1つのストライプデータを、コピー先ページの空きストライプに書き込む（F10）。GC206は、F10での書き込みに基づき、論物テーブルT1及び物論テーブルT2を更新する（F11）。【００６１】
F11及びF13でのテーブル更新は、例えば次のように行われる。GC206は、コピー先ページにコピーされた（書き込まれた）全ての生存データの各々について、物論テーブルT2及び論物テーブルT1でのコピー元物理アドレスをそれぞれコピー先物理アドレスに更新する。これにより、パディングデータの書込み先領域は未使用領域として扱われる。なお、物論テーブルT2が、1つの物理アドレスに対して、重複排除にて排除されなかったデータの論理アドレスだけでなく、リンクしている全ての論理アドレスを保持する場合には、物論テーブルT2から該当するデータの論理アドレスを参照し、論物テーブルT1の当該論理アドレスが指す物理アドレスを書き換えることができる。【００６２】
以上が、GCの処理フローの一例である。【００６３】
図4の処理フローによれば、コピー先ページには、1以上の生存データがシーケンシャルに書き込まれ、コピー先ページへの書込みは、なるべく、パディング無しにストライプ単位で行われる。ストライプ単位の書込みであれば、書込み先からのデータの読出しもパリティの読出しも不要である。このため、書込み負荷を低減できる。【００６４】
また、パディングは、最後の未書込みデータのサイズがストライプデータのサイズ又はストリップデータのサイズに満たない場合にのみ行われる。このため、書込み負荷を一層低減できる。【００６５】
なお、処理フローでは、最後の未書込みデータについては、ストリップ単位での書き込みも可能である。ストリップ単位の書込みであれば、書込み先からのデータの読出しが不要である。このため、書込み負荷を低減できる。【００６６】
また、パディングサイズは、ストリップサイズ未満に制限されてもよい。これにより、パディングについての負荷を軽減できる。また、パディングサイズがストリップサイズ未満であっても、ストライプ単位の書き込みとストリップ単位の書き込みのうちの少なくともストリップ単位の書き込みは可能である。【００６７】
また、F9及びF10において、ストライプ単位の書込みとするかストリップ単位の書込みとするかは、予め決められていてもよいし、設定されている情報（例えばポリシー）から選択的に決定されてもよい。後者の具体例として、例えば、以下の（10-1）〜（10-3）のうちのいずれかが採用されてよい。
（10-1）未書込みデータのサイズが、ストライプサイズの1/2（50%）より大きければ（パディングサイズが、ストライプサイズの1/2未満であれば）、ストライプ単位の書込みのためのパディングが行われる。比較的パディングサイズが小さくて済むためである。
（10-2）未書込みデータのサイズをストリップサイズで割ったときの商Qが、（M-1）である場合、ストライプ単位の書込みのためのパディングが行われる。Mは、ストライプデータを構成するストリップデータの数である。従って、Q=M-1であるということは、パディングサイズがストリップサイズ未満である。この例によれば、わずかなパディングで未書込みデータをストライプデータにできる。
（10-3）未書込みデータのサイズが、ストリップサイズ未満の場合、1つのストリップデータの生成のためのパディングが行われる。ストライプデータを生成するためのパディングよりも少ないパディングで書込みを実行できるためである。【００６８】
また、図4の処理フローによれば、最初からストライプ単位でデータの書込みが行われるが、直前回の処理フローの結果として、コピー先ページの使用ストライプ（少なくとも1つのストリップデータが書き込まれているストライプ）のうちの末尾の使用ストライプに空きのストリップがあれば、その使用ストライプの全てのストリップを埋めるためのストリップ単位の書込みが行われ、その後に、なるべくストライプ単位での書込みが行われてもよい。
【実施例２】
【００６９】
実施例2を説明する。その際、実施例1との相違点を主に説明し、実施例1との共通点については説明を省略又は簡略する。【００７０】
実施例1は、GC（Copying GC）での書込みの負荷の低減に着目した例であった。本実施例は、コピー元ページの選定に着目した例である。【００７１】
図5は、実施例2に係るストレージシステムの構成例を示す。【００７２】
ストレージシステム502において、プロセッサ101により実行されるプログラムとして、更に、テーブル管理207と、データ年齢統計208がある。テーブル管理207は、論物テーブルT1及び物論テーブルT2がメモリ503上に常駐しているか否かを管理する。データ年齢統計208は、GC稼働対象VOLに格納されるデータの対年齢アクセス頻度低下の変動に関する統計を取得する。データの「対年齢アクセス頻度低下の変動」とは、データの年齢（例えば、データが物理アドレス空間に書き込まれてからの経過時間）に対して、アクセス頻度がどの程度低下するかを意味する。例えば、当日から3ヶ月前までの比較的新しいデータへのアクセス頻度は高いが、3か月より前から数年前の古いデータへのアクセス頻度が低い。ファイルサーバなどでは、データ年齢の増加とともにアクセス頻度は指数的に低下する。一方、データベースサーバやデータウェアハウスなどでは、データ年齢に関わらず全てのデータを検索対象とするために、データ年齢に関わらずアクセス頻度は一定である。GC506は、GCの処理フローにおいて、コピー元ページの選択の処理フローを実行する。【００７３】
論物テーブルT1及び物論テーブルT2の配置場所、及び、データの対年齢アクセス頻度低下変動は、それぞれ、GC対象ページ（コピー元ページ）の選択に影響を与える。それは、GC利得はデータ年齢に比例し、コスト（GC処理負荷）に反比例するためである。【００７４】
図7及び図8は、論物テーブルT1及び物論テーブルT2の配置場所、対年齢アクセス頻度低下変動、及び、GC対象として選択されるページの条件を異とするGC効率の分布を示している。これらのデータは、ストレージシステム502における実測値を基に、ランダムな空き領域量を持つページを作成し、そのGC効率をモンテカルロ法によりシミュレートした結果である。図7及び図8共に、次の通りである。すなわち、左の図は、時系列に古い順に（物理アドレスの先頭から順に）ページをコピー元（GC対象）として選択するケースでのGC効率分布を示す。真ん中の図は、論物テーブルT1及び物論テーブルT2が1以上のドライブ111にあり数1により得られたGC効率の高いページをコピー元として選択するケースでのGC効率分布を示す。右の図は、論物テーブルT1及び物論テーブルT2がメモリ103にあり数1により得られた利得の高いページをコピー元として選択するケースでのGC効率分布を示す。なお、数1により得られたGC効率について、「セグメント」は「ページ」と読み替えられる。図7は、対年齢アクセス頻度低下速度が遅い場合のGC効率分布を示し、図8は、対年齢アクセス頻度低下速度が速い場合のGC効率分布を示す。図7及び図8の結果として得られるGC効率（benefit / cost）は、数1により導出された。【００７５】
図7及び図8の結果によると、論物テーブルT1及び物論テーブルT2がメモリ503にある場合、データの対年齢アクセス頻度変動に関わらずGC効率は高い。一方、対年齢アクセス頻度変動速度が速い場合、単純に前方から（物理アドレスの先頭から順に）ページをコピー元として選択するケースと、論物テーブルT1及び物論テーブルT2がメモリ503に無い時に高いGC効率を持つページをコピー元として選択するケースとでは、GC効率に大きな差は無い。【００７６】
以上の結果に従うコピー元ページ（GCの対象とするページ）の選択の処理フローを、図6が示す。この処理フローは、GCの処理フローにおいて実行される（例えば、F1とF2の間に実行される）。【００７７】
GC506は、論物テーブルT1及び物論テーブルT2がメモリ503にある（オンメモリ）か否かを判定する（F11）。【００７８】
F11の判定結果が真であれば、GC506は、「高GC効率ページ探索」モードを選択する（F12）。このモードでは、メモリ503にある論物テーブルT1及び物論テーブルT2のうちの少なくとも1つを基に数1により得られたGC効率が比較的高いページがコピー元として選択される。具体的には、例えば、GC対象候補ページ（断片空き領域を含んだ追記不可ページ）毎にGC効率が算出され、GC効率が比較的高いページが選択されてよい。なお、「GC効率が比較的高いページ」とは、GC効率が所定の閾値以上のGC対象候補ページであってもよいし、複数のGC対象候補ページにそれぞれ対応した複数のGC効率のうち上記X％（X>0）に該当するGC効率のページであってもよい。【００７９】
F11の判定結果が偽であれば、GC506は、ドライブ111（例えば、物理アドレス空間に対応したRAIDグループを構成するドライブ111）が追記型ドライブか否かを判定する（F13）。【００８０】
F13の判定結果が真であれば、GC506は、「ページ前方探索」モードを選択する（F14）。このモードでは、時系列に古い順に（物理アドレス順に）、GC対象候補ページが探索され、見つかったページがコピー元として選択される。なお、「追記型ドライブ」とは、SMR（Singled Magnetic Recording）ドライブや、NANDフラッシュメモリを含んだSSD（Solid State Drive）などであり、これらのドライブにおける各ブロックが、ドライブ追記領域（アドレス順にデータが書き込まれるべき領域）である。ここで言う「ブロック」は、単位領域の一例である（例えば、NANDフラッシュメモリについては、ブロックは、データの消去単位である）。ブロック全体を開放することなく、利用可能な空き容量の確保はできない。そのため、複数の追記型ドライブで構成されたRAIDグループに関して、ランダムな位置に存在する高GC効率のページを探す「高GC効率ページ探索」モードは、不向きである。【００８１】
F13の判定結果が偽であれば、GC506は、データ年齢統計208を呼び出すことで、物理アドレス空間に関して対年齢アクセス頻度低下変動速度を特定し、対年齢アクセス頻度低下変動速度が遅いか否か（例えば、所定の閾値未満か否か）を判定する（F15）。F15の判定結果が真であれば、GC506は、「高GC効率ページ探索」モードを選択する（F16）。F15の判定結果が偽であれば、GC506は、「ページ前方探索」モードを選択する。なお、対年齢アクセス頻度低下速度が速い場合に、「高GC効率ページ探索」も「ページ前方探索」も同程度のGC効率となる時でも、「ページ前方探索」モードが選択される。それは、物理アドレス順にまとまった空き領域の確保が保証されること、「ページ前方探索」モードの方がGCのTATが小さいこととを理由とする。【００８２】
実施例2によれば、ストレージシステム502の構成や状態に適したページがコピー元として選択されるので、GC効率をより向上させることが期待できる。【００８３】
なお、判定の順序は、必ずしも、F11、F13、F15の順でなくてもよい。また、F11、F13及びF15の全ての判定が行われないでもよい。例えば、F11の判定結果が偽の場合、F13及びF15無しに、ページ前方探索モードが選択されてもよい。また、F11の判定無しに、F13の判定が行われ、F13の判定結果が真の場合、ページ前方探索モードが選択されてもよい。また、F13の判定結果が偽の場合、F11の判定及びF15の判定のいずれも行うこと無しに、高GC効率ページ探索モードが選択されてもよい。【００８４】
また、実施例2でも実施例1でも、ストレージシステムには、複数の追記型ドライブで構成されたRAIDグループである追記型RAIDグループと、複数の非追記型ドライブ（追記型ドライブではないドライブ）で構成されたRAIDグループである非追記型RAIDグループとのうち少なくとも追記型RAIDグループが含まれていてよい。
【実施例３】
【００８５】
実施例3を説明する。その際、実施例1及び2との相違点を主に説明し、実施例1及び2との共通点については説明を省略又は簡略する。【００８６】
一般に、GCを行うストレージシステムに採用されるGCの種類は1種類であるが、本実施例に係るストレージシステムでは、Threading GCとCopying GCの両方が採用されている。Threading GCの1つの問題点として、空き領域の管理ために論物テーブル及び物論テーブルのうちの少なくとも一方がメモリに収まらない程に大サイズになり得る点があるが、本実施例では、Threading GCは、Copying GCでコピーが行われる領域単位と同じ領域単位で行われる。【００８７】
すなわち、図9に例示するように、コントローラ（プロセッサ及びメモリを含む）が、Threading GCとして、物理アドレス空間に既存のデータを更新、圧縮又は重複排除することによりその既存データを無効化した結果として、その無効化されたデータの領域を含んだページが空きページになった場合（例えば、物理アドレス空間において、現在の追記先物理アドレスよりも前方に（先頭側に）空きページが生じた場合）、データの追記先となる物理アドレスを、現在の追記先物理アドレスが指すページが追記可能ページであっても（又は追記不可ページとなった場合に）、既存データの無効化により新たに生じた空きページの先頭に変更する。このため、次の追記では、追記対象のデータは、その空きページの先頭から書き込まれる。図9の例によれば、ページ305A、305B、305C及び305Eが、追記不可ページであり、ページ305Dが、物理アドレス空間の途中に生じた空きページ（追記可能ページ）である。図9の例によれば、コントローラは、新たな追記対象データ（例えば、クライアント1からの更新後データ、又は、ポストプロセス算術圧縮により生成された圧縮データ）の追記先物理アドレスとして、追記不可ページ305A、305B、305C及び305Eのいずれのページのいずれの断片空き領域の先頭アドレスも選択しない。コントローラは、新たな追記対象データの追記先物理アドレスとして、追記可能ページ504Dの空き領域の先頭アドレスを選択する。【００８８】
一方、Coping GC（例えば所定のGC周期に開始するGC）では、コントローラは、図10に例示するように、追記可能ページ305Dに、追記不可ページ305A、305B、305C及び305Eの生存データをコピーする。これにより、ページ305A、305B、305C及び305Eの各々が、追記可能ページとなる。【００８９】
本実施例によれば、Copying GCに加えてThreading GCが行われ、Threading GCが、Copying GCでコピーが行われる領域単位と同じ領域単位で行われる。このため、論物テーブルT1及び物論テーブルT2のうちの少なくとも1つのサイズを増やすこと無しに、Copying GCに加えてThreading GCを行うことができる。
【実施例４】
【００９０】
実施例4を説明する。その際、実施例1〜3との相違点を主に説明し、実施例1〜3との共通点については説明を省略又は簡略する。【００９１】
実施例4では、少なくとも1つの追記型RAIDグループにおける各追記型ドライブのブロックのサイズが、ページサイズより大きい。例えば、図11に例示するように、SMRドライブのブロックのサイズが、ページサイズのｗ倍（ｗは2以上の整数）であるとする。1つのブロックは、複数のサブブロックで構成されている。1つのサブブロックは、1つのページ、又は、1つのページの一部分に対応した領域である。後者の場合、例えば、1つのページに、追記型RAIDグループ内の異なる複数のSMRドライブがそれぞれ有する複数のサブブロックが対応している。【００９２】
このようなケースでは、Copying GC又はThreading GCにおいて、追記先ページの遷移順が、ブロックにおけるアドレス順と異なると、ブロックから生存データを読み出せないことが起こり得る。【００９３】
そこで、本実施例では、コントローラは、追記型ドライブのブロックのサイズに基づき物理アドレス空間についての単位領域サイズを決定する。以下、物理アドレス空間における各単位領域を、「物理追記領域」と言う。複数の物理追記領域には、それぞれ、異なる複数のブロックセットが対応している。各ブロックセットは、物理アドレス空間に対応した追記型RAIDグループ内の異なる複数の追記型ドライブがそれぞれ有する複数のブロックである。【００９４】
コントローラは、ページ単位に代えて又は加えて、物理追記領域単位で、追記不可領域か追記可能領域かを管理する。コントローラは、Copying GCにおいて、生存データのコピー先を、ページ単位ではなく、物理追記領域単位で選択する。これにより、Copying GCでは、図11に例示するように、追記型ドライブ（図11ではSMRドライブ）において、1以上のコピー元ブロックからコピー先ブロックに1以上の生存データがコピーされる。その際、その1以上の生存データは、コピー先ブロックにアドレス順にシーケンシャルに書き込まれる。1以上のコピー元ブロックは、1以上のコピー元物理追記領域（断片空き領域を含んだ追記不可領域）に対応する。コピー先ブロックは、コピー先物理追記領域に対応する。【００９５】
実施例4によれば、追記型ドライブからの生存データの読み出しを不可能にしてしまうこと無しに、Copying GC（及びThreading GC）を実行できる。【００９６】
以上、幾つかの実施例を説明したが、これらは本発明の説明のための例示であって、本発明の範囲をこれらの実施例にのみ限定する趣旨ではない。本発明は、他の種々の形態でも実行することが可能である。例えば、必ずしも論物テーブルT1及び物論テーブルT2の両方が無くてもよく、論物テーブルT1及び物論テーブルT2の一方があればよい。つまり、論物テーブルT1及び物論テーブルT2の一方又はそれらの組合せが、論理アドレスと物理アドレス間のアドレス変換のためのアドレス変換情報の一例でよい。
【符号の説明】
【００９７】
2，502  ストレージシステム
【図１】
2016181481.tif 000003
【図２】
2016181481.tif 000004
【図３】
2016181481.tif 000005
【図４】
2016181481.tif 000006
【図５】
2016181481.tif 000007
【図６】
2016181481.tif 000008
【図７】
2016181481.tif 000009
【図８】
2016181481.tif 000010
【図９】
2016181481.tif 000011
【図１０】
2016181481.tif 000012
【図１１】
2016181481.tif 000013
【国際調査報告】
2016181481.tif 000014
2016181481.tif 000015