JP6414852B2 - メモリシステムおよび制御方法 - Google Patents

Description

本発明の実施形態は、不揮発性メモリを制御する技術に関する。

近年、不揮発性メモリを備えるメモリシステムが広く普及している。

このようなメモリシステムの一つとして、ＮＡＮＤフラッシュ技術ベースのソリッドステートドライブ（ＳＳＤ）が知られている。

ＳＳＤは、その低電力消費、高性能という特徴により、様々なコンピュータのメインストレージとして使用されている。

国際公開第２０１２／０２０５４４号

ところで、ホストによってＳＳＤに書かれるデータには、そのデータの一部分が頻繁に書き換えられ、残りの部分は頻繁に書き換えられない、というデータ局所性が存在する場合がある。

このようなデータ局所性は、ＳＳＤのライトアンプリフィケーションを増加させ、結果としてＳＳＤの性能および寿命に影響を及ぼす場合がある。

本発明が解決しようとする課題は、データ局所性によるライトアンプリフィケーションを増加を抑制することができるメモリシステムおよび制御方法を提供することである。

実施形態によれば、メモリシステムは、不揮発性メモリと、前記不揮発性メモリに電気的に接続され、前記不揮発性メモリのガベージコレクション動作を実行するように構成されたコントローラとを具備する。前記コントローラは、前記複数のブロックの内の、ホストによって書き込まれたデータを含むブロック毎に、当該ブロック内のデータが前記ガベージコレクション動作によってコピーされた回数を示すガベージコレクション回数を管理する。前記コントローラは、同じガベージコレクション回数に関連づけられた複数の第１ブロックを、前記ガベージコレクション動作の対象ブロックとして選択する。前記コントローラは、前記複数の第１ブロック内の有効データをコピー先フリーブロックにコピーする。前記コントローラは、前記複数の第１ブロックのガベージコレクション回数に１を加えた値を、前記コピー先フリーブロックのガベージコレクション回数として設定する。

実施形態に係るメモリシステムの構成例を説明するブロック図。 同実施形態のメモリシステムによって実行される、ガベージコレクション回数管理動作とガベージコレクション動作とを説明するための図。 同実施形態のメモリシステムにおいて用いられるガベージコレクション（ＧＣ）回数管理リストの例を説明する図。 ガベージコレクション回数管理リストに基づいて同実施形態のメモリシステムによって実行されるガベージコレクション対象ブロック選択動作を説明するための図。 同実施形態のメモリシステムによって実行されるガベージコレクション動作を説明する図。 同実施形態のメモリシステムに書き込まれる複数種のデータの例を説明する図。 ガベージコレクション回数と複数種のデータ間のデータ量の割合との関係の例を説明する図。 同実施形態のメモリシステムによって実行されるガベージコレクション動作の手順を説明するフローチャート。 同実施形態のメモリシステムによって実行される、異なるガベージコレクション回数を有する２つのブロック群の有効データをマージする処理を含むガベージコレクション動作を説明する図。 同実施形態のメモリシステムによって実行される、異なるガベージコレクション回数を有する２つのブロック群の有効データをマージする処理を含むガベージコレクション動作の手順を説明するフローチャート。 マージ処理を特定のガベージコレクション回数以上のブロック群にのみ許可する動作を説明する図。 マージ処理を特定のガベージコレクション回数以上のブロック群にのみ許可する動作を含むガベージコレクション動作の手順を説明するフローチャート。 同実施形態のメモリシステムによって実行される、ホストからのデータの書き込み用にフリーブロックを順次割り当てる動作を説明するための図。 同実施形態のメモリシステムによって使用されるブロック使用順序管理リストの例を説明するための図。 同じＬＢＡへのライトが要求された時に同実施形態のメモリシステムによって実行される累積データ書き込み量算出動作を説明するための図。 同実施形態のメモリシステムによって実行される累積データ書き込み量応答処理の処理シーケンスを説明するための図。 同実施形態のメモリシステムによって実行される累積データ書き込み量応答処理の手順を説明するフローチャート。 同実施形態のメモリシステムによって実行される累積データ書き込み量応答処理の別の処理シーケンスを説明するための図。 同実施形態のメモリシステムによって実行される累積データ書き込み量応答処理の別の手順を説明するフローチャート。 同実施形態のメモリシステムにおいて使用されるルックアップテーブルの例を説明するための図。 同じＬＢＡへのライトが要求された時に同実施形態のメモリシステムによって実行される時間経過応答処理の手順を説明するためのフローチャート。 同実施形態のメモリシステムから受信される累積データ書き込み量／時間経過情報に基づいてホストによって実行される処理の手順の例を説明するフローチャート。 ホストの構成例を説明するブロック図。 同実施形態のメモリシステムとホストとを含むコンピュータの構成例を示す図。

以下、図面を参照して、実施形態を説明する。
まず、図１を参照して、一実施形態に係るメモリシステムを含む情報処理システム１の構成を説明する。

このメモリシステムは、不揮発性メモリにデータをライトし、不揮発性メモリからデータをリードするように構成された半導体ストレージデバイスである。このメモリシステムは、例えば、ＮＡＮＤフラッシュ技術ベースのソリッドステートドライブ（ＳＳＤ）３として実現されている。

情報処理システム１は、ホスト（ホストデバイス）２と、ＳＳＤ３とを含む。ホスト２は、サーバ、パーソナルコンピュータのような情報処理装置である。

ＳＳＤ３は、ホスト２として機能する情報処理装置のメインストレージとして使用され得る。ＳＳＤ３は、情報処理装置に内蔵されてもよいし、情報処理装置にケーブルまたはネットワークを介して接続されてもよい。

ホスト２とＳＳＤ３とを相互接続するためのインタフェースとしては、ＳＣＳＩ、Ｓｅｒｉａｌ Ａｔｔａｃｈｅｄ ＳＣＳＩ（ＳＡＳ）、ＡＴＡ、Ｓｅｒｉａｌ ＡＴＡ（ＳＡＴＡ）、ＰＣＩ Ｅｘｐｒｅｓｓ（ＰＣＩｅ）、Ｅｔｈｅｒｎｅｔ（登録商標），Ｆｉｂｒｅ ｃｈａｎｎｅｌ等が使用し得る。

ＳＳＤ３は、コントローラ４、不揮発性メモリ（ＮＡＮＤメモリ）５、およびＤＲＡＭ６を備える。ＮＡＮＤメモリ５は、限定されないが、複数のＮＡＮＤフラッシュメモリチップを含んでいてもよい。

ＮＡＮＤメモリ５は、多数のＮＡＮＤブロック（ブロック）Ｂ０〜Ｂｍ−１を含む。ブロックＢ０〜Ｂｍ−１は、消去単位として機能する。ブロックは「物理ブロック」または「消去ブロック」と称されることもある。

ブロックＢ０〜Ｂｍ−１は多数のページ（物理ページ）を含む。つまり、ブロックＢ０〜Ｂｍ−１の各々は、ページＰ０〜Ｐｎ−１を含む。ＮＡＮＤメモリ５においては、データのリードおよびデータのライトはページ単位で実行される。データの消去はブロック単位で実行される。

コントローラ４は、Toggle、ONFIのようなＮＡＮＤインタフェース１３を介して、不揮発性メモリであるＮＡＮＤメモリ５に電気的に接続されている。コントローラ４は、ＮＡＮＤメモリ５のデータ管理とＮＡＮＤメモリ５のブロック管理とを実行するように構成されたフラッシュトランスレーション層（ＦＴＬ）として機能し得る。

データ管理には、（１）論理ブロックアドレス（ＬＢＡ）と物理アドレスとの間の対応関係を示すマッピング情報の管理、（２）ページ単位のリード／ライトとブロック単位の消去動作とを隠蔽するための処理、等が含まれる。ＬＢＡと物理アドレスとの間のマッピングの管理は、論理物理アドレス変換テーブルとして機能するルックアップテーブル（ＬＵＴ）３３を用いて実行される。ルックアップテーブル（ＬＵＴ）３３は、所定の管理サイズ単位で、ＬＢＡと物理アドレスとの間のマッピングを管理する。ホスト２からのライトコマンドの多くは、４Ｋバイトのデータの書き込みを要求する。したがって、ルックアップテーブル（ＬＵＴ）３３は、例えば４Kバイト単位で、ＬＢＡと物理アドレスとの間のマッピングを管理してもよい。あるＬＢＡに対応する物理アドレスは、このＬＢＡのデータがライトされたＮＡＮＤメモリ５内の物理記憶位置を示す。物理アドレスは、物理ブロックアドレスと物理ページアドレスとを含む。物理ページアドレスは全てのページに割り当てられており、また物理ブロックアドレスは全てのブロックに割り当てられている。

ページへのデータ書き込みは、１消去サイクル当たり１回のみ可能である。

このため、コントローラ４は、同じＬＢＡへのライト（上書き）を、ＮＡＮＤメモリ５上の別のページにマッピングする。つまり、コントローラ４は、この別のページにデータをライトする。そして、コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を更新してこのＬＢＡをこの別のページに関連付けると共に、元のページ（つまりこのＬＢＡが関連付けられていた古いデータ）を無効化する。

ブロック管理には、不良ブロックの管理と、ウェアレベリングと、ガベージコレクション動作等が含まれる。ウェアレベリングは、物理ブロックそれぞれのプログラム／イレーズ回数を平準化するための動作である。

ガベージコレクション動作は、ＮＡＮＤメモリ５内のフリースペースを作り出すための動作である。このガベージコレクション動作は、ＮＡＮＤメモリ５のフリーブロックの個数を増やすため、有効データと無効データとが混在する幾つかのブロック内の全ての有効データを別のブロック（コピー先フリーブロック）にコピーする。そして、ガベージコレクション動作は、ルックアップテーブル（ＬＵＴ）３３を更新して、コピーされた有効データのＬＢＡそれぞれを正しい物理アドレスにマッピングする。有効データが別のブロックにコピーされることによって無効データのみなったブロックはフリーブロックとして開放される。これによって、このブロックは消去後に再利用することが可能となる。

ホスト２は、ライトコマンドをＳＳＤ３に送出する。このライトコマンドは、ライトデータ（つまり書き込むべきデータ）の論理アドレス（開始論理アドレス）と、転送長とを含む。この実施形態においては、ＬＢＡが論理アドレスとして使用されるが、他の実施形態においてはオブジェクトＩＤが論理アドレスとして使用されても良い。ＬＢＡは、論理セクタ（論理ブロック）に付与されるシリアル番号によって表現される。シリアル番号はゼロから始まる。論理セクタのサイズは、例えば５１２バイトである。

ＳＳＤ３のコントローラ４は、ライトコマンド内の開始論理アドレスと転送長とによって指定されるライトデータを、ＮＡＮＤメモリ５内のブロックのページにライトする。さらに、コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を更新することによって、ライトされたデータに対応するＬＢＡを、このデータがライトされた物理記憶位置を示す物理アドレスにマッピングする。

より詳しくは、コントローラ４は、ＮＡＮＤメモリ５内のフリーブロックの一つを、ホスト２からのデータの書き込みのために割り当てる。この割り当てられたブロックは、ホスト２からのデータが書き込まれるべき書き込み対象ブロックであり、「書き込み先ブロック」、または「入力ブロック」、等とも称される。コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を更新しながら、ホスト２から受信されるライトデータを書き込み対象ブロック（書き込み先ブロック）の利用可能ページに順次書き込む。書き込み先ブロックに利用可能ページが無くなった場合に、コントローラ４は、新たなフリーブロックを書き込み先ブロックとして割り当てる。

次に、コントローラ４の構成について説明する。

コントローラ４は、ホストインタフェース１１、ＣＰＵ１２、ＮＡＮＤインタフェース１３、ＤＲＡＭインタフェース１４、ＳＲＡＭ１５等を含む。これらＣＰＵ１２、ＮＡＮＤインタフェース１３、ＤＲＡＭインタフェース１４、ＳＲＡＭ１５は、バス１０を介して相互接続される。

ホストインタフェース１１は、ホスト２から様々なコマンド（ライトコマンド、リードコマンド、アンマップ（ＵＮＭＡＰ）コマンド、等）を受信する。

ライトコマンドは、ＳＳＤ３に対し、このライトコマンドによって指定されたデータをライトするように要求する。ライトコマンドは、ライトされるべき最初の論理ブロックのＬＢＡ（開始ＬＢＡ）と、転送長（論理ブロックの数）とを含む。リードコマンドは、ＳＳＤ３に対し、このリードコマンドによって指定されたデータをリードするように要求する。リードコマンドは、リードされるべき最初の論理ブロックのＬＢＡ（開始ＬＢＡ）と、転送長（論理ブロックの数）とを含む。

ＣＰＵ１２は、ホストインタフェース１１、ＮＡＮＤインタフェース１３、ＤＲＡＭインタフェース１４、ＳＲＡＭ１５を制御するように構成されたプロセッサである。ＣＰＵ１２は、上述のＦＴＬの処理に加え、ホスト２からの様々なコマンドを処理するためのコマンド処理等を実行する。

例えば、コントローラ４がホスト２からライトコマンドを受信した時、ＣＰＵ１２の制御の下、コントローラ４はライトコマンドによって指定されるライトデータをＮＡＮＤメモリ５に書き込む以下のライト動作を実行する。

つまり、コントローラ４は、ライトデータを現在の書き込み先ブロックの物理記憶位置（利用可能ページ）に書き込み、そしてルックアップテーブル（ＬＵＴ）３３を更新して、ライトコマンドに含まれるＬＢＡ（開始ＬＢＡ）にこの物理記憶位置の物理アドレスをマッピングする。

これらＦＴＬ処理およびコマンド処理は、ＣＰＵ１２によって実行されるファームウェアによって制御されてもよい。このファームウェアは、ＣＰＵ１２を、ガベージコレクション（ＧＣ）回数管理部２１、ガベージコレクション（ＧＣ）動作制御部２２、および更新頻度情報応答部２３として機能させる。

ホスト２によってＳＳＤ３に書かれるデータには、そのデータの一部分が頻繁に書き換えられ、残りの部分は頻繁には書き換えられない、というデータ局所性が存在する場合がある。この場合、例えば、無効データ量の多い上位幾つかのブロックをＧＣ対象ブロックとして選択するという通常のＧＣアルゴリズムによってＧＣ動作が実行されると、何度もＧＣ動作が繰り返されるにつれて、更新頻度の高いデータと更新頻度の低いデータとが同じブロックに混在しやくなる。更新頻度の高いデータと更新頻度の低いデータとの混在は、ＳＳＤ３のライトアンプリフィケーションを増加させる要因となり得る。

なぜなら、更新頻度の高いデータ（Ｈｏｔデータ）と更新頻度の低いデータ（Ｃｏｌｄデータ）とが混在するブロックにおいては、Ｈｏｔデータの更新によってブロック内の一部の領域だけが早いタイミングで無効化される一方、このブロック内の残りの領域（Ｃｏｌｄデータ）は有効状態に長い間維持されるからである。

もしＨｏｔデータのみによってブロックが満たされていたならば、このブロック内の全てのデータがそれらデータの更新（書き替え）によって、比較的速いタイミングで無効化される可能性が高い。したがって、このブロックは、ガベージコレクション動作を実行すること無しで、このブロックを消去することのみによって、再利用することが可能となる。

一方、Ｃｏｌｄデータのみによってブロックが満たされているならば、このブロック内の全てのデータは、長い間、有効状態に維持される。したがって、このブロックは、長い間、ガベージコレクション動作の対象とならない可能性が高い。

ライトアンプリフィケーション（ＷＡ）は、以下のように定義される。

WA=「ＳＳＤにライトされたデータの総量」 ／ 「ホストからＳＳＤにライトされたデータの総量」
「ＳＳＤにライトされたデータの総量」は、ホストからＳＳＤにライトされたデータの総量とガベージコレクション動作等によって内部的にＳＳＤにライトされたデータの総量との和に相当する。

ライトアンプリフィケーション（ＷＡ）の増加は、ＳＳＤ３内のブロックそれぞれの書き換え回数（プログラム／イレーズ回数）の増加を引き起こす。つまり、ライトアンプリフィケーション（ＷＡ）が大きい程、ブロックのプログラム／イレーズ回数が、そのプログラム／イレーズ回数の上限値に速く達しやすくなる。この結果、ＳＳＤ３の耐久性および寿命の劣化が引き起こされる。

本実施形態では、更新頻度の高いデータと更新頻度の低いデータとを分離できるようにするために、「ブロック内のデータのＧＣ回数を考慮したＧＣ機能」と、「ＬＢＡベースの更新頻度通知機能」とを有している。

ガベージコレクション（ＧＣ）回数管理部２１およびガベージコレクション（ＧＣ）動作制御部２２は、「ブロック内のデータのＧＣ回数を考慮したＧＣ機能」を実行する。「ブロック内のデータのＧＣ回数を考慮したＧＣ機能」は、データ局所性に起因するＳＳＤ３のライトアンプリフィケーションの増加を抑制可能な改善されたガベージコレクション（ＧＣ）動作を実行する。

ガベージコレクション（ＧＣ）回数管理部２１は、ホスト２によって書き込まれたデータを含むブロック毎に、ガベージコレクション（ＧＣ）回数を管理する。あるブロックのＧＣ回数は、このブロック内のデータがガベージコレクション（ＧＣ）動作によってコピーされた回数を示す。つまり、あるブロックのＧＣ回数は、このブロック内のデータが有効データとして過去に何回コピーされたかを示す。

ホスト２によってデータがライトされた直後のブロック、つまりそのデータがＧＣによって一度も集められた（コピーされた）ことのないブロックについては、このブロックのＧＣ回数はゼロに設定される。

ＧＣ回数がゼロである幾つかのブロックがＧＣの対象ブロック（コピー元ブロック）として選択され、これらブロックの有効データがコピー先フリーブロックにコピーされたならば、ＧＣ回数管理部２１は、このコピー先フリーブロックのＧＣ回数を１に設定する。コピー先フリーブロック内のデータは、有効データとしてＧＣ対象ブロック（コピー元ブロック）から１回コピーされたデータであるからである。

有効データがコピー先フリーブロックにコピーされることによって無効データのみなった各ブロック（コピー元ブロック）は、フリーブロックとなる。フリーブロックはデータを含まないので、このフリーブロックのＧＣ回数は管理する必要はない。

ＧＣ回数が１である幾つかのブロック（コピー元ブロック）がガベージコレクション（ＧＣ）の対象ブロックとして選択され、これらブロックの有効データがコピー先フリーブロックにコピーされたならば、ＧＣ回数管理部２１は、このコピー先のフリーブロックのＧＣ回数を２に設定する。このコピー先フリーブロック内のデータは、有効データとして過去に２回コピーされたデータであるからである。

このように、あるブロックに関連づけられたＧＣ回数の値は、このブロック内のデータが過去のＧＣ動作によって何回コピーされたか、つまりこのブロック内のデータに対して過去に何回のＧＣ動作が実行されたかを示す。

ＧＣ動作制御部２２は、同じＧＣ回数に関連づけられた幾つかのブロックをガベージコレクション（ＧＣ）動作の対象ブロックとして選択し、これら同じＧＣ回数に関連づけられたブロックの有効データのみを同じコピー先ブロックにコピーする、という改良されたＧＣ動作を実行する。

例えば、ＧＣ動作制御部２２は、同じＧＣ回数に関連づけられたブロック群（つまり、同じＧＣ回数を有するブロックの集合）の中から、幾つかのブロックを、ＧＣのための対象ブロックとして選択する。ＧＣ動作制御部２２は、このＧＣ対象ブロックとして選択されたこれらブロック内の有効データをコピー先フリーブロックにコピーする。そして、ＧＣ対象ブロックとして選択されたこれらブロックのＧＣ回数に１を加えた値が、ＧＣ回数管理部２１によって、このコピー先フリーブロックのＧＣ回数として設定される。

「ＬＢＡベースの更新頻度通知機能」は、個々のライトコマンドに含まれる個々のＬＢＡへのライトの頻度をホスト２に通知することによって、ホスト２がＨｏｔデータ／Ｃｏｌｄデータを分離するのを効率良くアシストする機能である。

「ＬＢＡベースの更新頻度通知機能」は、更新頻度情報応答部２３によって実行される。

更新頻度情報応答部２３は、ホスト２からＬＢＡを含むライトコマンドを受信した際に、このＬＢＡへの前回のライトからこのＬＢＡへの今回のライトまでの時間経過に関する値、またはこのＬＢＡへの前回のライトからこのＬＢＡへの今回のライトまでの累積データ書き込み量を、このライトコマンドに対する応答としてホスト２に通知する。これにより、ホスト２に対して、ユーザデータの実際の更新頻度（書き替え頻度）を知らせることができるので、ホスト２は、ユーザデータを互いに更新頻度の異なる複数種のデータ、例えば、頻繁に更新されるタイプのデータ（Ｈｏｔデータ）、更新の頻度が低いタイプのデータ（Ｃｏｌｄデータ）、ＨｏｔデータとＣｏｌｄデータの中間の更新頻度を有するタイプのデータ（Ｗａｒｍデータ）に、に分類できる。この結果、例えば、ホスト２は、必要に応じて、これら異なるタイプのデータを、異なるＳＳＤに分散させるための処理等を実行することができる。

次に、コントローラ４内の他のコンポーネントについて説明する。

ＮＡＮＤインタフェース１３は、ＣＰＵ１２の制御の下、ＮＡＮＤメモリ５を制御するように構成されたＮＡＮＤコントローラである。

ＤＲＡＭインタフェース１４は、ＣＰＵ１２の制御の下、ＤＲＡＭ６を制御するように構成されたＤＲＡＭコントローラである。

ＤＲＡＭ６の記憶領域の一部は、ＮＡＮＤメモリ５にライトすべきデータを一時的に格納するためのライトバッファ（ＷＢ）３１として利用されてもよい。また、ＤＲＡＭ６の記憶領域は、ガベージコレクション（ＧＣ）動作中に移動されるデータを一時的に格納するためのＧＣバッファ３２として利用されてもよい。また、ＤＲＡＭ６の記憶領域は、上述のルックアップテーブル３３の格納のために用いられてもよい。

さらに、ＤＲＡＭ６の記憶領域は、ＧＣ回数管理リスト３４、およびブロック使用順序管理リスト３５として利用されてもよい。

ＧＣ回数管理リスト３４は、ホスト２によって書き込まれたデータを含むブロック毎に、ＧＣ回数を保持するためのリストである。ＧＣ回数管理リスト３４は、ブロックそれぞれのブロックＩＤ（例えば物理ブロックアドレス）とこれらブロック内のデータのＧＣ回数との間の対応関係を示す表であってもよい。

あるいは、ＧＣ回数管理リスト３４は、ＧＣ回数（例えば、ＧＣ回数＝０〜ＧＣ回数＝ｎ）別にブロックそれぞれを管理するための複数のＧＣ回数リストから構成されてもよい。ここで、ｎは、管理すべきＧＣ回数の上限値である。例えば、ＧＣ回数＝０のＧＣ回数リストは、０回のＧＣ回数に関連づけられたブロックそれぞれのブロックＩＤ（例えば物理ブロックアドレス）のリストを保持する。ＧＣ回数＝１のＧＣ回数リストは、１回のＧＣ回数に関連づけられたブロックそれぞれのブロックＩＤ（例えば物理ブロックアドレス）のリストを保持する。

ブロック使用順序管理リスト３５は、書き込み先ブロック用に割り当てられたブロックそれぞれに付与される割り当て番号（シーケンシャル番号）を保持する。すなわち、コントローラ４は、書き込み対象ブロックとして割り当てられたブロックそれぞれに対してその割り当て順序を示す番号（割り当て番号）を付与する。番号は１から始まるシーケンシャル番号であってもよい。例えば、最初に書き込み先ブロック用に割り当てられたブロックには割り当て番号＝１が付与され、２番目に書き込み先ブロック用に割り当てられたブロックには割り当て番号＝２が付与され、３番目に書き込み先ブロック用に割り当てられたブロックには割り当て番号＝３が付与される。これにより、どのブロックがどのような順序で書き込み先ブロックとして割り当てられたかを示すブロック使用履歴を管理することができる。割り当て番号としては、新たなフリーブロックが書き込み先ブロック用に割り当てられる度にインクリメントされるカウンタの値を使用できる。

ＳＳＤ３は、さらに他の様々な管理情報を保持していてもよい。このような管理情報の例には、物理アドレスそれぞれに対応する有効／無効フラグを保持するページ管理テーブルが含まれていても良い。各有効／無効フラグは、対応する物理アドレス（物理ページ）が有効であるか無効であるかを示す。物理ページが有効であるとは、その物理ページ内のデータが有効データであることを意味する。物理ページが無効であるとは、その物理ページ内のデータが更新（書き替え）によって無効化されたデータであることを意味する。

次に、ホスト２の構成について説明する。

ホスト２は、様々なプログラムを実行する情報処理装置である。情報処理装置によって実行されるプログラムには、アプリケーションソフトウェアレイヤ４１、オペレーティングシステム（ＯＳ）４２、ファイルシステム４３が含まれる。

一般に知られているように、オペレーティングシステム（ＯＳ）４２は、ホスト２全体を管理し、ホスト２内のハードウェアを制御し、アプリケーションがハードウェアおよびＳＳＤ３を使用することを可能にするための制御を実行するように構成されたソフトウェアである。

ファイルシステム４３は、ファイルの操作（作成、保存、更新、削除等）のための制御を行うために使用される。例えば、ＺＦＳ、Ｂｔｒｆｓ、ＸＦＳ、ｅｘｔ４、ＮＴＦＳなどがファイルシステム４３として使用されても良い。あるいは、ファイルオブジェクトシステム（例えば、Ceph Object Storage Daemon）、Key Value Store System (例えば、Rocks DB) がファイルシステム４３として使用されても良い。

様々なアプリケーションソフトウェアスレッドがアプリケーションソフトウェアレイヤ４１上で走る。アプリケーションソフトウェアスレッドの例としては、クライアントソフトウェア、データベースソフトウェア、仮想マシン等がある。

アプリケーションソフトウェアレイヤ４１がリードコマンドまたはライトコマンドのようなリクエストをＳＳＤ３に送出することが必要な時、アプリケーションソフトウェアレイヤ４１は、ＯＳ４２にそのリクエストを送出する。ＯＳ４２はそのリクエストをファイルシステム４３に送出する。ファイルシステム４３は、そのリクエストを、コマンド（リードコマンド、ライトコマンド等）にトランスレートする。ファイルシステム４３は、コマンドを、ＳＳＤ３に送出する。ＳＳＤ３からのレスポンスが受信された際、ファイルシステム４３は、そのレスポンスをＯＳ４２に送出する。ＯＳ４２は、そのレスポンスをアプリケーションソフトウェアレイヤ４１に送出する。

次に、図２〜図１２を参照して、「ブロック内のデータのＧＣ回数を考慮したＧＣ機能」の詳細を説明する。

図２は、ＳＳＤ３によって実行されるＧＣ回数管理動作とＧＣ動作とを示す。

ＳＳＤ３のコントローラ４は、あるフリーブロックを、ホスト２からのデータ（ライトデータ）の書き込み用のブロック（書き込み先ブロック）として割り当て、ホスト２から受信されるライトデータをこの書き込み先ブロック内の利用可能ページに順次書き込む。現在の書き込み先ブロックの全てのページがデータで満たされた時、コントローラ４は、現在の書き込み先ブロックをアクティブブロック（データを含むブロック）として管理する。さらに、コントローラ４は、別のフリーブロックを新たな書き込み先ブロックとして割り当てる。このようにして、ＳＳＤ３においては、ホスト２から受信されるデータ（ライトデータ）は、その到着順に、現在の書き込み先ブロックの最初のページから最後のページに向けて順次書き込まれる。

図２のブロックＢ１１〜Ｂ１７は、ホスト２によってデータがライトされた直後のブロック、つまりそのブロック内のデータがガベージコレクション（ＧＣ）動作によって一度もコピーされたことのないブロックである。これらブロックＢ１１〜Ｂ１７に対応するＧＣ回数は０である。

時間が経過するにつれ、ブロックＢ１１〜Ｂ１７の各々のデータの一部は、その書き換えによって無効化されるかもしれない。これにより、ブロックＢ１１〜Ｂ１７の各々においては、有効データと無効データとが混在される場合がある。

フリーブロックの数が閾個数以下に低下した場合、コントローラ４は、有効データと無効データとが混在される幾つかのブロックからフリーブロックを作り出すＧＣ動作を開始する。

コントローラ４は、まず、有効データと無効データとが混在する幾つかのブロックをＧＣ対象ブロックとして選択する。このＧＣ対象ブロックの選択においては、コントローラ４は、上述したように、同じＧＣ回数に関連づけられたブロック群をＧＣ対象ブロックとして選択する。このブロック群は、例えば、最も無効データの量が多いブロックが属するブロック群、つまり最も無効データの量が多いブロックのＧＣ回数と同じＧＣ回数を有するブロックの集合、であってよい。この場合、コントローラ４は、最初に、ホスト２によって書き込まれたデータを含むブロックから、無効データ量が最も多いブロックを選択してもよい。次いで、コントローラ４は、無効データ量が最も多いブロックと、この無効データ量が最も多いブロックのＧＣ回数と同じＧＣ回数に関連づけられた一以上のブロックとを、ガベージコレクション（ＧＣ）動作の対象ブロックとして選択してもよい。

コントローラ４は、選択した幾つかのＧＣ対象ブロック（同じＧＣ回数に関連づけられた幾つかのブロック）内の有効データをコピー先フリーブロックにコピーし、これらＧＣ対象ブロックのＧＣ回数に１を加えた値を、コピー先フリーブロックのＧＣ回数として設定する。これにより、ＧＣ対象ブロックのＧＣ回数に１を加えた値がコピー先フリーブロックに引き継がれるので、コピー先フリーブロックのＧＣ回数は、そのコピー先フリーブロック内のデータがＧＣ動作によって過去に何回コピーされたかを正しく表すことができる。

例えば、同じＧＣ回数に関連づけられた２つのブロックＢ１１，Ｂ１２がＧＣ対象ブロックとして選択され、これらブロックＢ１１，Ｂ１２の有効データがコピー先フリーブロックＢ２１にコピーされたならば、このコピー先フリーブロックＢ２１のＧＣ回数は、ブロックＢ１１，Ｂ１２のＧＣ回数（ここでは、０）に１を加えた値（ここでは１）に設定される。

同様に、同じＧＣ回数に関連づけられた３つのブロックＢ１３、Ｂ１４、Ｂ１５がＧＣ対象ブロックとして選択され、これらブロックＢ１３、Ｂ１４、Ｂ１５の有効データがコピー先フリーブロックＢ２２にコピーされたならば、このコピー先フリーブロックＢ２２のＧＣ回数は、ブロックＢ１３、Ｂ１４、Ｂ１５のＧＣ回数（ここでは、０）に１を加えた値（ここでは１）に設定される。

同様に、同じＧＣ回数に関連づけられた２つのブロックＢ１６、Ｂ１７がＧＣ対象ブロックとして選択され、これらブロックＢ１６、Ｂ１７の有効データがコピー先フリーブロックＢ２３にコピーされたならば、このコピー先フリーブロックＢ２３のＧＣ回数は、ブロックＢ１６、Ｂ１７のＧＣ回数（ここでは、０）に１を加えた値（ここでは１）に設定される。

時間が経過するに連れ、ブロックＢ２１、Ｂ２２、Ｂ２３の各々のデータの一部は、その書き換えによって無効化されるかもしれない。これにより、ブロックＢ２１、Ｂ２２、Ｂ２３の各々においては、有効データと無効データとが混在される場合がある。

同じＧＣ回数に関連づけられた２つのブロックＢ２１、Ｂ２２がＧＣ対象ブロックとして選択され、これらブロックＢ２１、Ｂ２２の有効データがコピー先フリーブロックＢ３１にコピーされたならば、このコピー先フリーブロックＢ３１のＧＣ回数は、ブロックＢ２１、Ｂ２２のＧＣ回数（ここでは１）に１を加えた値（ここでは２）に設定される。

このように、本実施形態では、ブロック毎に管理されるＧＣ回数はそのブロック内のデータが過去のＧＣ動作によってコピーされた回数を示す。このＧＣ回数を正しく管理するために、ＧＣ対象ブロックのＧＣ回数に１を加えた値が、コピー先フリーブロック内のデータに引き継がれる。

図３は、ＧＣ回数管理リスト３４の例を示す。

管理すべきＧＣ回数の上限値ｎが例えば１０である場合、ＧＣ回数管理リスト３４は、ＧＣ回数=０〜ＧＣ回数=１０にそれぞれ対応する１１個のＧＣ回数リストから構成されてもよい。

ＧＣ回数=０のＧＣ回数リストは、ＧＣ回数＝０に関連づけられたブロックそれぞれのブロックＩＤ（例えば物理ブロックアドレス）のリストを示す。ＧＣ回数=１のＧＣ回数リストは、ＧＣ回数＝１に関連づけられたブロックそれぞれのブロックＩＤ（例えば物理ブロックアドレス）のリストを示す。同様にして、ＧＣ回数=１０のＧＣ回数リストは、ＧＣ回数＝１０に関連づけられたブロックそれぞれのブロックＩＤ（例えば物理ブロックアドレス）のリストを示す。各ＧＣ回数リストは、限定されないが、有効データと無効データとが混在するブロックだけを含んでもよい。

図４は、コントローラ４によって実行されるＧＣ対象ブロック選択動作を示す。

ＧＣ対象ブロックを選択する処理においては、コントローラ４のガベージコレクション動作制御部２２は、最初に、異なるＧＣ回数にそれぞれ関連づけられた複数のブロック群（複数のＧＣ回数リスト）から、ＧＣ対象のブロック群を選択してもよい。図４では、ＧＣ回数=５のブロック群（ブロックＢ２、ブロックＢ５、ブロックＢ１１、ブロックＢ２１）がＧＣ対象のブロック群として選択され、さらに、このＧＣ回数=５のブロック群から、幾つかのＧＣ対象ブロックが選択される場合が例示されている。

ＧＣ対象ブロックを選択する処理においては、例えば、まず、所定の条件に合致するブロックが最初のＧＣ候補として選択されてもよい。所定の条件に合致するブロックは、アクティブブロック（ホスト２によって書き込まれたデータを含むブロック）の中で最も無効データ量が多いブロックであってもよい。他の実施形態では、所定の条件に合致するブロックは、アクティブブロックの中で最も古いブロックであってもよい。以下では、最も無効データ量が多いブロックが、最初のＧＣ候補として選択される場合を想定する。

最も無効データ量が多いブロックがブロックＢ５であるならば、コントローラ４は、ブロックＢ５を含むＧＣ回数リスト（ここでは、ＧＣ回数＝５のＧＣ回数リスト）を特定し、このＧＣ回数＝５のＧＣ回数リストによって示されるブロック群（ブロックＢ２、ブロックＢ５、ブロックＢ１１、ブロックＢ２１）をＧＣ対象のブロック群として選択し、このＧＣ対象のブロック群から、幾つかのＧＣ対象ブロックを選択する。例えば、これらブロックＢ２、ブロックＢ５、ブロックＢ１１、ブロックＢ２１の中で無効データ量が多い上位幾つかのブロックがＧＣ対象ブロックとして選択されてもよい。この場合、例えば、ブロックＢ５と、ブロックＢ２、ブロックＢ１１、ブロックＢ２１内の中で最も無効データ量が多い上位の一つ以上のブロックとが、ＧＣ対象ブロックとして選択されてもよい。

図５は、コントローラ４によって実行されるＧＣ動作を示す。

コントローラ４は、全てのフリーブロックを含むフリーブロックプール（フリーブロックリスト）６０を管理する。コントローラ４は、これらフリーブロックから一つのフリーブロックを選択する。コントローラ４は、選択されたフリーブロックを、コピー先フリーブロックＢ１０００として割り当てる。コントローラ４は、同じＧＣ回数を有するＧＣ対象ブロック（ここでは、ブロックＢ２、Ｂ５、Ｂ１１）からコピー先フリーブロックＢ１０００に全ての有効データをコピーする。そして、コントローラ４は、ルックアップテーブル３３を更新して有効データのＬＢＡそれぞれをコピー先フリーブロックＢ１０００の物理アドレスそれぞれにマッピングする。

コピー先フリーブロックＢ１０００のＧＣ回数は、ブロックＢ２、Ｂ５、Ｂ１１のＧＣ回数（＝５）＋１に設定される。ブロックＢ１０００は、ＧＣ回数＝６のＧＣ回数リストに追加される。ブロックＢ２、Ｂ５、Ｂ１１は、有効データを含まないフリーブロックとなる。フリーブロックとなったブロックＢ２、Ｂ５、Ｂ１１は、ＧＣ回数＝５のＧＣ回数リストから破棄される。

図６は、ＳＳＤ３に書き込まれる複数種のデータの例を示す。

図６では、互いに更新頻度の異なる３種類のデータ（データＡ、データＢ、データＣ）がＳＳＤ３に書き込まれる場合が想定されている。ＳＳＤ３のデータ記憶領域（ＬＢＡスペース）は、ＬＢＡグループＡ、Ｂ、Ｃに対応する３つのスペースを含む。

ＬＢＡグループＡに書き込まれるデータＡは更新頻度の低いデータであり、且つデータＡの量はデータＡ、Ｂ、Ｃの中で最も多い。つまり、ＬＢＡグループＡは最も大きいＬＢＡ範囲を有する。

ＬＢＡグループＣに書き込まれるデータＣは、更新頻度の高いデータであり、且つデータＣの量はデータＡ、Ｂ、Ｃの中で最も少ない。つまり、ＬＢＡグループＣは最も小さいＬＢＡ範囲を有する。

ＬＢＡグループＢに書き込まれるデータＢは、データＡとデータＣの中間の更新頻度を有するデータであり、且つデータＢの量はデータＡの量とデータＣの量の中間である。

ＳＳＤ３の総ユーザ容量に対するデータＡの量の割合は、例えば、５０％であってもよい。ＳＳＤ３の総ユーザ容量に対するデータＢの量の割合は、例えば、３０％であってもよい。ＳＳＤ３の総ユーザ容量に対するデータＣの量の割合は、例えば、２０％であってもよい。

データＡの更新頻度つまりＬＢＡグループＡへのライトの頻度は、例えば、２０％であってもよい。データＢの更新頻度つまりＬＢＡグループＢへのライトの頻度は、例えば、３０％であってもよい。データＣの更新頻度つまりＬＢＡグループＣへのライトの頻度は、例えば、５０％であってもよい。

この場合、例えば、ＳＳＤ３がデータＡ、データＢ、データＣで満たされた後は、２回のライトコマンドに１回の割合で、データＣ（ＬＢＡグループＣ）へのライトを要求するライトコマンドがホスト２からＳＳＤ３に発行され、また５回のライトコマンドに１回の割合で、データＡ（ＬＢＡグループＡ）へのライトを要求するライトコマンドがホスト２からＳＳＤ３に発行される。例えば、データＣは、２回のライトコマンドに１回の割合（５０％）という高い頻度で更新される。

ＳＳＤ３に書き込まれるデータが図６のようなデータ局所性を有する場合においては、図６の下部に示すように、各書き込み先ブロックにはデータＡ、データＢ、データＣが混在される。

一つの書き込み先ブロックにおいて、ブロックの容量に対するデータＣの量の割合は５０％、ブロックの容量に対するデータＢの量の割合は３０％、ブロックの容量に対するデータＡの量の割合は２０％となる。

上述したように、データＣの量は、データＡ、データＢよりも少なく、且つデータＣの更新頻度は、データＡ、データＢよりも高いので、各ブロック内のデータＣのほとんどは速いタイミングで無効化される確率が高い。一方、データＡおよびデータＢについては、特にデータＡについては、長い間、有効状態に維持される確率が高い。

データＣの更新（書き換え）よって無効データ量が増えたブロックそれぞれは、いずれＧＣ対象ブロックとなり、これらブロックからコピー先フリーブロックに有効データがコピーされる。各ＧＣ対象ブロックにおいては、データＣの多くが無効化され且つデータＡ、データＢの多くが有効データに維持されている確率が高い。このため、コピー先ブロックにおいては、ＧＣ対象ブロックに比べてデータＡの量とデータＢの量とが増え、代わりに、ＧＣ対象ブロックに比べてデータＣの量が減る。

本実施形態では、同じＧＣ回数の幾つかのブロック内の有効データがコピー先フリーブロックにコピーされるので、ＧＣ回数の少ないブロック内の有効データとＧＣ回数の多いブロック内の有効データとがＧＣ動作によって同じコピー先フリーブロックにコピーされることはない。したがって、ＧＣ回数の多いブロックほど、そのブロックの容量に対するデータＡの量の割合を増やすことができ、これによってデータＡ（Ｃｏｌｄデータ）を、データＣ（ホットデータ）から分離することができる。

図７は、ＧＣ回数と、各ブロック内のデータＡ，Ｂ，Ｃ間のデータ量の割合との関係の例を示す。

ＧＣ回数＝０の各ブロックにおいては、ブロックの容量に対するデータＣの量の割合は５０％、ブロックの容量に対するデータＢの量の割合は３０％、ブロックの容量に対するデータＡの量の割合は２０％である。

ブロックの容量に対するデータＣの量の割合は、１回または２回程度のＧＣ動作によって速く低下される。ＧＣ回数が増えるにつれて、ブロックの容量に対するデータＢの量の割合も徐々に低下される。

上述したように、本実施形態では、ＧＣ回数の少ないブロック内の有効データとＧＣ回数の多いブロック内の有効データとが同じコピー先フリーブロックにコピーされることはないので、データを含むブロックそれぞれを、（１）ほぼデータＡのみを含むグループ（例えばＧＣ回数７〜１０程度）、（２）データＡとデータＢとを含み、且つデータＣをほとんど含まないグループ（例えばＧＣ回数３〜６程度）、（３）データＡとデータＢとデータＣを含むグループ（例えばＧＣ回数０〜２程度）に分類できる。

換言すれば、本実施形態では、同じＧＣ回数のブロックについては、それらブロックに含まれるデータＡ、Ｂ、Ｃの量の割合を同じにすることができる。

よって、同じＧＣ回数の幾つかのブロック内の有効データを同じコピー先フリーブロックにコピーするという本実施形態の改良されたＧＣ動作は、たとえＳＳＤ３に書かれるデータが高いデータ局所性を有する場合であっても、ほぼデータＡのみを含むブロックのグループと、データＡとデータＢとを含み且つデータＣをほとんど含まないブロックのグループと、データＡとデータＢとデータＣを含むブロックのグループとを作ることができ、これによってＨｏｔデータとＣｏｌｄデータとを徐々に分離することができる。この結果、ＳＳＤ３のライトアンプリフィケーションの増加を抑制することができる。

図８のフローチャートは、コントローラ４によって実行されるＧＣ動作の手順を示す。

コントローラ４は、残りフリーブロックの数をチェックし（ステップＳ１１）、残りフリーブロックの数が閾値ｔｈ１以下であるか否かを判定する（ステップＳ１２）。このチェックは、定期的に実行されてもよい。例えば、新たなフリーブロックを書き込み先ブロックとして割り当てるべき時に残りフリーブロックの数をチェックしてもよい。

残りフリーブロックの数が閾値ｔｈ１以下であるならば（ステップＳ１２のＹＥＳ）、コントローラ４は、まず、全てのアクティブブロックから最初のＧＣ候補を選択する。最初のＧＣ候補は、最大無効データ量のブロックであってもよい。この場合、全てのアクティブブロックから最大無効データ量のブロックが最初のＧＣ候補として選択される（ステップＳ１３）。コントローラ４は、ＧＣ回数管理リスト３４を参照して、最初のＧＣ候補（ここでは、例えば、最大無効データ量のブロック）のＧＣ回数と同じＧＣ回数に関連づけられたブロック群（第１ブロック群）を選択し、さらに、この第１ブロック群から、幾つかのＧＣ対象ブロックを選択する（ステップＳ１４）。ステップＳ１４では、最初のＧＣ候補（例えば、最大無効データ量のブロック）が含まれているＧＣ回数リストによって示されるブロック群（第１ブロック群）が選択され、そして第１ブロック群から、幾つかのＧＣ対象ブロックが選択される。この場合、最初のＧＣ候補（例えば、最大無効データ量のブロック）と、このＧＣ回数リストに含まれる別の１以上のブロックとが、ＧＣ対象ブロックとして選択されてもよい。

コントローラ４は、これら選択されたＧＣ対象ブロック内の全ての有効データをコピー先フリーブロックにコピーする（ステップＳ１５）。ステップＳ１５では、これら選択されたＧＣ対象ブロック内の有効ページそれぞれから有効データがリードされ、リードされた有効データがコピー先フリーブロックの利用可能ページそれぞれに書き込まれる。ステップＳ１５では、さらに、コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を更新して、コピーされた有効データのＬＢＡをコピー先フリーブロックの物理アドレスに関連付けると共に、ページ管理テーブルを更新して、各ＧＣ対象ブロック内の元のページ（つまりこのＬＢＡが関連付けられていた古いデータ）を無効化する。この場合、コントローラ４は、まず、ルックアップテーブル（ＬＵＴ）３３を参照することによって、コピーされた有効データが格納されている元のページの物理アドレスを取得してもよく、そして、ページ管理テーブルを更新して、この物理アドレスに対応する有効／無効フラグを無効を示す値に設定してもよい。

この後、コントローラ４は、これら選択されたＧＣ対象ブロックのＧＣ回数＋１、つまり第１ブロック群のＧＣ回数に１を加えた値を、コピー先フリーブロックのＧＣ回数として設定する（ステップＳ１６）。

図９は、異なるＧＣ回数を有する２つのブロック群の有効データをマージする処理を含むＧＣ動作を示す。

例えば、最大無効データ量のブロックのＧＣ回数と同じＧＣ回数に関連づけられたブロック群（ＧＣ対象ブロック群）に含まれる有効データの量が閾値よりも少ない場合、コントローラ４は、異なるＧＣ回数を有する２つのブロック群の有効データをマージする処理を実行する。この場合、コントローラ４は、ＧＣ対象ブロック群のＧＣ回数と出来るだけ近いＧＣ回数を有する別の一つのブロック群を選択してもよい。

例えば、いま、最大無効データ量のブロックがブロックＢ３００であり、ブロックＢ３００のＧＣ回数が１０である場合を想定する。この場合、コントローラ４は、ＧＣ回数＝１０のＧＣ回数管理リストに含まれるブロック群の総有効データ量をチェックする。例えば、ＧＣ回数＝１０のＧＣ回数管理リストに含まれるブロックがブロックＢ３００のみである場合、あるいはＧＣ回数＝１０のＧＣ回数管理リストに２つまたは３つ程度のブロックが含まれているがこれら各々の有効データ量が非常に少ない場合には、コントローラ４は、ＧＣ回数＝１０のブロック群と一緒にＧＣ動作が実行されるべきブロック群を選択する。

この場合、コントローラ４は、最大無効データ量のブロックＢ３００のＧＣ回数よりも１回以上少ないＧＣ回数を有する全てのブロック群（ここでは、ＧＣ回数９のブロック群、ＧＣ回数８のブロック群、ＧＣ回数７のブロック群、…ＧＣ回数０のブロック群）の中で、最大のガベージコレクション回数を有するブロック群を選択してもよい。

コントローラ４は、最初にＧＣ回数＝９のＧＣ回数管理リストを参照して、ＧＣ回数＝９のブロックが存在するか否かを判定する。ＧＣ回数＝９のブロックが存在しないならば、コントローラ４は、ＧＣ回数＝８のＧＣ回数管理リストを参照して、ＧＣ回数＝８のブロックが存在するか否かを判定する。

ＧＣ回数＝９のブロックが存在せず、ＧＣ回数＝８のブロックが存在するならば、コントローラ４は、ＧＣ回数＝８のブロック群（例えば、ブロックＢ４１、Ｂ４２、Ｂ４３）を、選択する。そして、コントローラ４は、ブロックＢ３００の有効データとＧＣ回数＝８のブロック群の有効データとをコピー先フリーブロックにコピーする。この場合、ブロックＢ４１、Ｂ４２、Ｂ４３の全ての有効データが必ずしも利用される必要は無く、ブロックＢ４１、Ｂ４２、Ｂ４３内の少なくとも一つのブロック内の有効データが利用されればよい。

図１０のフローチャートは、異なるＧＣ回数を有する２つのブロック群の有効データをマージする処理を含むＧＣ動作の手順を示す。

コントローラ４は、残りフリーブロックの数をチェックし（ステップＳ２１）、残りフリーブロックの数が閾値ｔｈ１以下であるか否かを判定する（ステップＳ２２）。上述したように、このチェックは、定期的に実行されてもよい。

残りフリーブロックの数が閾値ｔｈ１以下であるならば（ステップＳ２２のＹＥＳ）、コントローラ４は、まず、全てのアクティブブロックから最初のＧＣ候補を選択する。最初のＧＣ候補は、最大無効データ量のブロックであってもよい。この場合、全てのアクティブブロックから最大無効データ量のブロックが最初のＧＣ候補として選択される（ステップＳ２３）。コントローラ４は、ＧＣ回数管理リスト３４を参照して、最初のＧＣ候補（ここでは、例えば、最大無効データ量のブロック）のＧＣ回数と同じＧＣ回数に関連づけられたブロック群（第１ブロック群）を選択し、このブロック群（第１ブロック群）の有効データの総量が閾値ｔｈ２以下であるか否かを判定する（ステップＳ２４）。

閾値ｔｈ２の値は、固定であっても良いし、必要に応じて変更できる値であっても良い。閾値ｔｈ２の値が大きいほど、上述のマージ処理の実行が許可されやすくなる。

例えば、閾値ｔｈ２は、ＳＳＤ３内の一つのブロックの容量を示す値に予め設定されていてもよい。これにより、最初のＧＣ候補のＧＣ回数と同じＧＣ回数に関連づけられたブロック群のみでＧＣ動作が実行できない場合にのみ、マージ処理の実行を許可することができる。あるいは、閾値ｔｈ２は、ＳＳＤ３内の１つのブロックの容量の整数倍、例えば２倍の値に設定されていても良い。

この第１ブロック群の有効データの総量が閾値ｔｈ２以下でないならば（ステップＳ２４のＮＯ）、コントローラ４は、この第１ブロック群から、幾つかのＧＣ対象ブロックを選択する（ステップＳ２５）。ステップＳ２５では、最初のＧＣ候補（例えば、最大無効データ量のブロック）が含まれているＧＣ回数リストによって示される第１ブロック群から、これらＧＣ対象ブロックが選択される。この場合、最初のＧＣ候補（例えば、最大無効データ量のブロック）と、このＧＣ回数リストに含まれる別のブロックとが、ＧＣ対象ブロックとして選択されてもよい。

ステップＳ２５では、コントローラ４は、これら選択されたＧＣ対象ブロック内の全ての有効データをコピー先フリーブロックにコピーする。ステップＳ２５では、さらに、コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を更新して、コピーされた有効データのＬＢＡをコピー先フリーブロックの物理アドレスに関連付けると共に、各ＧＣ対象ブロック内の元のページを無効化する。

この後、コントローラ４は、これら選択されたＧＣ対象ブロックのＧＣ回数＋１を、つまり第１ブロック群のＧＣ回数に１を加えた値を、コピー先フリーブロックのＧＣ回数として設定する（ステップＳ２６）。

一方、第１ブロック群の有効データの総量が閾値ｔｈ２以下であるならば（ステップＳ２４のＹＥＳ）、コントローラ４は、この第１ブロック群のＧＣ回数よりも１回以上少ないＧＣ回数に関連づけられた全てのブロック群の中で、最大ＧＣ回数に関連づけられたブロック群（第２ブロック群）を選択する（ステップＳ２７）。

コントローラ４は、第１ブロック群の有効データと第２ブロック群の有効データとをコピー先フリーブロックにコピーする（ステップＳ２８）。ステップＳ２８では、さらに、コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を更新して、コピーされた有効データのＬＢＡをコピー先フリーブロックの物理アドレスに関連付けると共に、各ＧＣ対象ブロック内の元のページを無効化する。

コントローラ４は、第２ブロック群のＧＣ回数＋１をコピー先フリーブロックのＧＣ回数として設定するか、あるいは第１ブロック群のＧＣ回数＋１をコピー先フリーブロックのＧＣ回数として設定する（ステップＳ２９）。あるいは、第１ブロック群内のＧＣ対象ブロックの数よりも第２ブロック群内のＧＣ対象ブロックの数が多い場合には、第２ブロック群のＧＣ回数＋１をコピー先フリーブロックのＧＣ回数として設定してもよく、第１ブロック群内のＧＣ対象ブロックの数が第２ブロック群内のＧＣ対象ブロックの数よりも多い場合には、第１ブロック群のＧＣ回数＋１をコピー先フリーブロックのＧＣ回数として設定してもよい。

図１１は、マージ処理を特定のＧＣ回数以上のブロック群に対してのみ許可する動作を示す。

ＧＣ回数の多いブロック内に含まれている有効データは、更新頻度の低いデータ（データＡ）である可能性が高い。しかし、データＡも２０％の割合で書き替えられるので、ＧＣ回数の多いブロック、例えばＧＣ回数＝１０のブロック、についても、その無効データ量が多くなる場合がある。ＧＣ回数の多いブロック内の有効データは、これまで一度も更新（書き替え）されたことのないデータ、つまり、長い間、有効状態に維持されているデータである。このため、この有効データは、これからも更新されない確率が高い。

一方、ＧＣ回数の少ないブロックにおいては、データＢまたはデータＣが含まれている可能性が高い。このようなブロックについては、そのブロックのＧＣ動作をすぐに実行せずとも、時管理経過に伴ってブロック内の全てのデータが無効化される可能性がある。

したがって、マージ処理を許可するブロック群をマージ許可閾値ｔｈ３以上のＧＣ回数を有するブロック群に対してのみに許可することにより、無駄なコピーの発生を防ぐことができ、ＧＣの効率を高めることができる。

図１１では、マージ許可閾値ｔｈ３がＧＣ回数＝８に設定されている場合が例示されている。

この場合、最初のＧＣ候補のＧＣ回数と同じＧＣ回数に関連づけられたブロック群（第１ブロック群）のＧＣ回数が８以上であるならば、第１ブロック群と他のブロック群とのマージ処理が許可される。

例えば、ＧＣ回数＝１０のブロック群と他のブロック群とのマージ処理、およびＧＣ回数＝９のブロック群と他のブロック群とのマージ処理が、許可される。一方、例えば、ＧＣ回数＝７のブロック群と他のブロック群とのマージ処理は禁止される。

図１２のフローチャートは、マージ処理を特定のＧＣ回数以上のブロック群に対してのみ許可する動作を含むＧＣ動作の手順を示す。

この図１２のフローチャートに示されるＧＣ動作においては、図１０で説明した処理に加え、ステップＳ３０〜Ｓ３３の処理が追加されている。以下では、ステップＳ３０〜Ｓ３３の処理を主に説明する。

第１ブロック群の有効データの総量が閾値ｔｈ２以下であるならば（ステップＳ２４のＹＥＳ）、コントローラ４の処理は、ステップＳ３０に進む。ステップＳ３０において、コントローラ４は、第１ブロック群のＧＣ回数がマージ許可閾値ｔｈ３以上であるか否かを判定する。

第１ブロック群のＧＣ回数がマージ許可閾値ｔｈ３以上であるならば（ステップＳ３０のＹＥＳ）、コントローラ４は、図１０で説明したステップＳ２７〜Ｓ２９のマージ処理を実行する。

一方、第１ブロック群のＧＣ回数（最初のＧＣ候補のブロックのＧＣ回数）がマージ許可閾値ｔｈ３よりも少ないならば（ステップＳ３０のＮＯ）、コントローラ４は、ステップＳ２７〜Ｓ２９のマージ処理の実行を禁止し、代わりに、ステップＳ３１〜Ｓ３３の処理を実行する。

ステップＳ３１において、コントローラ４は、第１ブロック群とは異なる別のブロック群をＧＣ対象ブロック群として選択する。例えば、コントローラ４は、最初のＧＣ候補のブロックの次に無効データ量が多いブロックを新たなＧＣ候補として選択し、この新たなＧＣ候補が含まれているＧＣ回数リストによって示されるブロック群をＧＣ対象ブロック群として選択してもよい。

次いで、コントローラ４は、選択されたＧＣ対象ブロック群の有効データをコピー先フリーブロックにコピーし（ステップＳ３２）、コピー先フリーブロックのＧＣ回数を、ＧＣ対象ブロック群のＧＣ回数に１を加えた値に設定する（ステップＳ３３）。

最初のＧＣ候補のブロックが、マージ許可閾値ｔｈ３よりも少ないＧＣ回数に関連付けられている場合には、この最初のＧＣ候補のブロックは、頻繁に更新されるデータを含んでいる可能性が高い。このため、コントローラ４は、最初のＧＣ候補のブロックに対するＧＣを実行せずに、このブロックの有効データが全て無効化されるまで待っても良い。

次に、図１３〜図２２を参照して、「ＬＢＡベースの更新頻度通知機能」の詳細を説明する。

図１３は、フリーブロックをホスト２からのデータの書き込み用に順次割り当てる動作を示す。

コントローラ４は、フリーブロックリスト６０によって示されるフリーブロックの一つを書き込み先ブロック６２として割り当てる。この場合、コントローラ４は、ブロック使用順序管理リスト３５を更新して、書き込み先ブロック６２として最初に割り当てられたブロックの割り当て番号（シーケンシャル番号）を１に設定する。ブロック使用順序管理リスト３５は、図１４に示されているように、ブロックアドレスそれぞれに対応する割り当て番号（シーケンシャル番号）を保持する。これら割り当て番号は、書き込み先ブロック６２に割り当てられたブロックの順序関係を示す。つまり、コントローラ４は、書き込み対象ブロックとして割り当てられたブロックそれぞれに対してその割り当て順序を示す割り当て番号を付与し、これら割り当て番号をブロック使用順序管理リスト３５を使用して管理する。

コントローラ４は、ホスト２から受信されるライトデータをライトバッファ３１に書き込む。この後、コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を更新しながら、ライトバッファ３１内のライトデータを書き込み先ブロック６２の先頭ページから最終ページに向けて順次ライトする。

書き込み先ブロック６２に利用可能ページが無くなったならば、コントローラ４は、書き込み先ブロック６２をアクティブブロックリスト６１に移動し、フリーブロックリスト６０のフリーブロックを新たな書き込み先ブロック６２として割り当てる。この場合、コントローラ４は、ブロック使用順序管理リスト３５を更新して、この新たな書き込み先ブロック６２として割り当てられたこのブロックの割り当て番号（シーケンシャル番号）を２に設定する。

アクティブブロックリスト６１内の何れかのブロックの全てのデータがその更新によって無効化されたならば、このブロックはフリーブロックリスト６０に移動される。

フリーブロックリスト６０内のフリーブロックの数が閾値ｔｈ１以下に低下したならば、フリーブロックを作り出す上述のＧＣ動作が実行される。

図１５は、同じＬＢＡへのライトが要求された時に実行される累積データ書き込み量算出動作を示す。

コントローラ４は、ホスト２からあるＬＢＡを含むライトコマンドを受信した際に、このＬＢＡへの前回のライトからの累積データ書き込み量を、このライトコマンドに対する応答としてホスト２に通知する。累積データ書き込み量は、受信されたライトコマンドのＬＢＡと同じＬＢＡへの前回のライトからライトコマンドのＬＢＡへの今回のライトまでの間にホスト２によってＮＡＮＤメモリ５に書き込まれたデータの総量を示す。

累積データ書き込み量は、例えば、次の値から算出することができる。

（１）ブロック当たりの容量
（２）ブロック内に含まれるページの数
（３）同じＬＢＡへの前回のライトによってデータが書き込まれたＮＡＮＤメモリ５内の第１物理記憶位置（旧物理アドレス）
（４）今回のライトによってデータが書き込まれるべきＮＡＮＤメモリ５内の第２物理記憶位置（新物理アドレス）
（５）第１物理記憶位置（旧物理アドレス）を含むブロックの割り当てから第２物理記憶位置（新物理アドレス）を含むブロックの割り当てまでの間にホスト２からのデータの書き込みのために割り当てられたブロックの数
（１）〜（４）の値は、ＳＳＤ３内の通常の管理情報であり、累積データ書き込み量の算出のために専用に用意されたものではない。例えば、コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を参照することによって、受信されたライトコマンド内のＬＢＡにマッピングされている物理アドレスを第１物理記憶位置として容易に取得することができる。

（５）の「ブロックの数」は、例えば、第１物理記憶位置を含むブロックに付与された割り当て番号と第２物理記憶位置を含むブロックに付与された割り当て番号とから容易に算出することができる。

割り当て番号（シーケンシャル番号）は、図１４のブロック使用順序管理リスト３５によって管理されている。これら割り当て番号（シーケンシャル番号）の管理単位は、ブロック単位であるので、これら割り当て番号を保持するために必要な容量は少なくて済む。したがって、累積データ書き込み量は、その算出のための専用の管理情報をほとんど使用すること無く、低コストで取得することができる。

図１５では、ＬＢＡ１０を含むライトコマンドが受信された時に実行される累積データ書き込み量算出動作を示している。

ここでは、ＬＢＡ１０への前回のライトによってデータがブロックＢ５１のページＰｘに既に書き込まれており、且つＬＢＡ１０への今回のライトによってデータが現在の書き込み先ブロックＢ６２のページＰｙに書き込まれるべき場合が想定されている。もしブロックＢ５１の割り当て番号が１０で、ブロックＢ５１の割り当て番号が１３であれば、ブロック５１とブロックＢ６２との間に２つの書き込み先ブロック（例えばブロックＢ５２、Ｂ６１）が割り当てられていたことが分かる。

累積データ書き込み量は、ｄ１＋ｄ２＋ｄ２＋ｄ３で与えられる。

ここで、ｄ１は、ページＰｘに後続するブロックＢ５１内のページの数、またはこれらページの数に対応する容量を示す。ｄ２は、一つのブロック内のページの数、または一つのブロックの容量を示す。ｄ３は、ページＰｙに先行するブロックＢ６２内のページの数、またはこのページの数に対応する容量を示す。

ＬＢＡ１０を含む前回のライトコマンドの受信からＬＢＡ１０を含む今回のライトコマンドの受信までの間にホスト２から受信されるライトコマンドの数が多いほど、累積データ書き込み量は増加する。したがって、上述の累積データ書き込み量は、ＬＢＡ１０によって指定されるデータの更新頻度、つまりＬＢＡ１０へのライトの頻度を表すことができる。

ライトコマンドの受信時に、コントローラ４は、以下の手順で累積データ書き込み量を取得（算出）してもよい。

まず、コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を参照してライトコマンドに含まれるＬＢＡ（ここではＬＢＡ１０）にマッピングされている旧物理アドレス（ここではＰＡ１）を取得する。そして、コントローラ４は、ブロック使用順序管理リスト３５を参照して、旧物理アドレスによって指定されるブロックの割り当て番号（ここでは１０）と、新物理アドレス（ここではＰＡ２）によって指定されるブロックの割り当て番号（ここでは１３）とを取得する。コントローラ４は、ブロック内に含まれるページの数と旧物理アドレス（ＰＡ１）とからｄ１を求め、ブロック内に含まれるページの数と新物理アドレス（ＰＡ２）とからｄ３を求める。さらに、コントローラ４は、割り当て番号（１３）と割り当て番号（１０）との間の差分から、旧物理アドレスによって指定されるブロックの割り当てから新物理アドレスによって指定されるブロックの割り当てまでの間に、書き込み先ブロックとして割り当てられたブロックの総数（ここでは、２）を求める。これにより、累積データ書き込み量（＝ｄ１＋ｄ２＋ｄ２＋ｄ３）を取得（算出）することができる。

図１６は、累積データ書き込み量応答処理の処理シーケンスを示す。

ここでは、この処理シーケンスが、ライトコマンドとライトデータとが分割されているＮＣＱ（Ｎａｔｉｖｅ Ｃｏｍｍａｎｄ Ｑｕｅｉｎｇ）システムに適用される場合を想定する。

ホスト２は、あるＬＢＡ（＝ＬＢＡｘ）を示す開始ＬＢＡを含むライトコマンドをＳＳＤ３に送出する。このライトコマンドの受信に応答して、ＳＳＤ３のコントローラ４は、ＬＢＡｘへの前回のライトからＬＢＡｘへの今回のライトまでの累積データ書き込み量を算出し（ステップＳ４１）、算出された累積データ書き込み量を含むコマンド許可応答をホスト２に送信する。コマンド許可応答は、受信されたライトコマンドに対するアクノリッジ（ライトコマンドの実行許可）を示す許可応答である。ＳＳＤ３からホスト２に許可応答が送信されることにより、このライトコマンドによって指定されるライトデータの転送が開始される。許可応答は、実行を許可すべきライトコマンドを識別する値を含んでいても良い。累積データ書き込み量は、例えば、バイトで表されてもよいし、論理ブロック（論理セクタ）の数によって表されてもよい。

コマンド許可応答の受信に応答して、ホスト２は、ライトデータをＳＳＤ３に送出する。ＳＳＤ３のコントローラ４は、ライトデータをライトバッファ３１に書き込み、ライトバッファ３１のライトデータを書き込み先ブロックに書き込み（ステップＳ４２）、コマンド完了の応答（レスポンス）をホスト２に送信する。なお、ライトデータをライトバッファ３１に書き込んだ時点でコマンド完了のレスポンスをホスト２に送信してもよい。

ホスト２は、ＳＳＤ３から受信されるコマンド許可応答に含まれる累積データ書き込み量に基づいて、ＬＢＡｘのデータの実際の更新頻度（ＬＢＡｘへのライトの頻度）を把握することができる。

もしＬＢＡｘのデータの実際の更新頻度が、ホスト２によって予期されていたＬＢＡｘのデータの更新頻度と異なるならば、例えば、ＬＢＡｘのデータの実際の更新頻度がホスト２によって予期されていたＬＢＡｘのデータの更新頻度よりも高いならば、ホスト２は、必要に応じて、送出したライトコマンドをアボートするためのアボートコマンドをＳＳＤ３に送出してもよい。この場合、ライトコマンドによって指定されたデータの書き込みは実行されない。

図１７のフローチャートは、コントローラ４によって実行される累積データ書き込み量応答処理の手順を示す。

コントローラ４は、ＬＢＡｘを開始ＬＢＡとして含むライトコマンドをホスト２から受信する（ステップＳ５１）。コントローラ４は、ＬＢＡｘにマッピングされている旧物理アドレスと、ＬＢＡｘにマッピングされるべき新物理アドレスと、旧物理アドレスによって指定される物理記憶位置を含むブロックに付与された割り当て番号と、新物理アドレスによって指定される物理記憶位置を含むブロック（現在の書き込み先ブロック）に付与された割り当て番号、等とに基づいて、ＬＢＡｘへの前回の書き込みからＬＢＡｘへの今回の書き込みまでの累積データ書き込み量を算出する（ステップＳ５２）。コントローラ４は、累積データ書き込み量を含む許可応答をホスト２へ返す（ステップＳ５３）。

コントローラ４は、このライトコマンドに対応するライトデータまたはこのライトコマンドをアボートするためのアボートコマンドのいずれがホスト２から受信されるかを判定する（ステップＳ５４）。

もしライトデータが受信されたならば、コントローラ４は、ステップＳ５５に進む。ステップＳ５５では、コントローラ４は、このライトデータをライトバッファ３１に書き込み、ライトバッファ３１内のライトデータを現在の書き込み先ブロックに書き込み、ルックアップテーブル（ＬＵＴ）３３を更新してＬＢＡｘに新物理アドレスをマッピングし、そしてページ管理テーブルを更新して旧物理アドレス（旧データ）を無効化する。

この後、コントローラ４は、コマンド完了のレスポンスをホスト２へ返す（ステップＳ５６）。

なお、上述したように、ライトデータをライトバッファ３１に書き込んだ時点でコマンド完了のレスポンスをホスト２に送信してもよい。

一方、アボートコマンドが受信されたならば、コントローラ４は、このライトコマンドを破棄する（ステップＳ５７）。

図１８は、累積データ書き込み量応答処理の別の処理シーケンスを示す。

ホスト２は、あるＬＢＡ（＝ＬＢＡｘ）を開始ＬＢＡとして含むライトコマンドをＳＳＤ３に送出する。このライトコマンドの受信に応答して、ＳＳＤ３のコントローラ４は、コマンド許可応答をホスト２に送信する。コマンド許可応答の受信に応答して、ホスト２は、ライトデータをＳＳＤ３に送出する。ライトデータはライトバッファ３１に書き込まれる。ＳＳＤ３のコントローラ４は、累積データ書き込み量を算出する（ステップＳ５８）。累積データ書き込み量を算出する処理は、ライトコマンドの受信に応答して開始しても良い。

この後、コントローラ４は、書き込み先ブロックへのライトデータの書き込みを実行し（ステップＳ５９）、算出された累積データ書き込み量を含む、コマンド完了のレスポンスをホスト２に送信する。

なお、上述したように、ライトデータがライトバッファ３１に書き込まれた時点で、累積データ書き込み量を含むコマンド完了のレスポンスをホスト２に送信してもよい。

図１９のフローチャートは、累積データ書き込み量応答処理の別の手順を示す。

コントローラ４は、ＬＢＡｘを開始ＬＢＡとして含むライトコマンドをホスト２から受信する（ステップＳ６１）。コントローラ４は、許可応答をホスト２へ返す（ステップＳ６２）。コントローラ４は、ライトデータをホスト２から受信する（ステップＳ６３）。ライトデータはライトバッファ３１に書き込まれる。

コントローラ４は、ＬＢＡｘにマッピングされている旧物理アドレスと、ＬＢＡｘにマッピングされるべき新物理アドレスと、旧物理アドレスによって指定される物理記憶位置を含むブロックに付与された割り当て番号と、新物理アドレスによって指定される物理記憶位置を含むブロック（現在の書き込み先ブロック）に付与された割り当て番号等に基づいて、ＬＢＡｘへの前回の書き込みからＬＢＡｘへの今回の書き込みまでの累積データ書き込み量を算出する（ステップＳ６４）。コントローラ４は、ステップＳ６５に進む。

ステップＳ６５では、コントローラ４は、ライトバッファ３１内のライトデータを現在の書き込み先ブロックに書き込み、ルックアップテーブル（ＬＵＴ）３３を更新してＬＢＡｘに新物理アドレスをマッピングし、そしてページ管理テーブルを更新して旧物理アドレス（旧データ）を無効化する。

この後、コントローラ４は、累積データ書き込み量を含む、コマンド完了のレスポンスをホスト２へ返す（ステップＳ６６）。

なお、上述したように、ライトデータをライトバッファ３１に書き込んだ時点でコマンド完了のレスポンスをホスト２に送信してもよい。

次に、図２０〜図２３を参照して、累積データ書き込み量の代わりに、同じＬＢＡへの前回のライトからの時間経過値をホスト２に通知する処理について説明する。

この時間経過値は同じＬＢＡへの前回のライトからの時間経過に関する情報であり、時間経過値の例は、同じＬＢＡへの前回のライトの時刻であってもよいし、同じＬＢＡへの前回のライトの時刻とこの同じＬＢＡへの今回のライトの時刻との間の時間間隔であってもよい。

図２０は、例えば４Ｋバイトのような所定の管理単位で、ＬＢＡと、物理アドレスと、前回ライトされた時刻との対応関係を管理するように構成されたルックアップテーブル（ＬＵＴ）３３の例を示す。

ルックアップテーブル（ＬＵＴ）３３は、ＬＢＡ毎に物理アドレス記憶領域３３Ａと時刻記憶領域３３Ｂとを含む。各時刻記憶領域３３Ｂは、対応するＬＢＡへのライトが発生した時刻を示す値、つまり対応するＬＢＡのデータがライトされた時刻を示す値、を保持するために使用される。各時刻記憶領域３３Ｂに保持される時刻は、例えば、時分秒であってもよい。

あるＬＢＡを含むライトコマンドが受信された時、コントローラ４は、このＬＢＡに対応する物理アドレス領域３３Ａに物理アドレスを登録すると共に、このＬＢＡに対応する時刻領域３３Ｂに、ライトコマンドによって指定されるデータ（ライトデータ）がライトされた時刻を登録する。物理アドレスは、ライトコマンドによって指定されたデータが書き込まれた物理記憶位置の物理アドレスを示す。ライトされた時刻は、ライトコマンドが受信された時刻であってもよいし、ライトコマンドによって指定されたデータがライトバッファ３１に書き込まれた時刻であってもよいし、ライトコマンドによって指定されたデータがＮＡＮＤメモリ５の書き込み先ブロックにライトされた時刻であってもよい。

図２１のフローチャートは、コントローラ４によって実行される時間経過応答処理の手順を示す。

ここでは、時間経過値を含むコマンド許可応答をホスト２に送信する場合を想定する。

コントローラ４は、ＬＢＡｘを開始ＬＢＡとして含むライトコマンドをホスト２から受信する（ステップＳ７１）。コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を参照して、ＬＢＡｘへの前回のライトの時刻、つまりＬＢＡｘを含む前回のライトコマンドによってデータがライトされた時刻を、取得する（ステップＳ７２）。コントローラ４は、ＬＢＡｘへの前回のライトの時刻を示す時間経過値を含む許可応答をホスト２へ返す（ステップＳ７３）。上述したように、時間経過値は、ＬＢＡｘへの前回のライトの時刻とＬＢＡｘの今回のライトの時刻との間の時間間隔、つまり現在時刻（ＬＢＡｘへの今回のライトの時刻）からＬＢＡｘへの前回のライトの時刻を引いた値であってもよい。

コントローラ４は、このライトコマンドに対応するライトデータまたはこのライトコマンドをアボートするためのアボートコマンドのどちらがホスト２から受信されるかを判定する（ステップＳ７４）。

ライトデータが受信されたならば、コントローラ４は、ステップＳ７５に進む。ステップＳ７５では、コントローラ４は、このライトデータをライトバッファ３１に書き込み、ライトバッファ３１内のライトデータを現在の書き込み先ブロックに書き込み、ルックアップテーブル（ＬＵＴ）３３を更新してＬＢＡｘに新物理アドレスと新ライト時刻とをマッピングし、そしてページ管理テーブルを更新して旧物理アドレス（旧データ）を無効化する。

この後、コントローラ４は、コマンド完了のレスポンスをホスト２へ返す（ステップＳ７６）。

なお、上述したように、ライトデータをライトバッファ３１に書き込んだ時点でコマンド完了のレスポンスをホスト２に送信してもよい。

一方、アボートコマンドが受信されたならば、コントローラ４は、このライトコマンドを破棄する（ステップＳ７７）。

図２１のフローチャートでは、時間経過値を含むコマンド許可応答をホスト２に送信する場合を説明したが、時間経過値を含むコマンド完了のレスポンスをホスト２に送信してもよい。時間経過値を含むコマンド完了のレスポンスの送信は、図１８、図１９と同様の手順によって実行することができる。

図２２のフローチャートは、ＳＳＤ３から通知される累積データ書き込み量／時間経過値に基づいてホスト２によって実行される処理の手順を示す。

ホスト２は、ＳＳＤ３から通知される累積データ書き込み量／時間経過値に基づいて、データを更新頻度の異なる複数種のデータグループに分類してもよい。例えば、ホスト２のファイルシステム４３がデータ管理部を含み、このデータ管理部が、データを複数種のデータグループに分類して、データを頻繁に更新されるデータグループ（Ｈｏｔデータ）と頻度には更新されないデータグループ（Ｃｏｌｄデータ）とに分離してもよい。ＳＳＤ３に書き込んだデータの更新頻度がある閾値以上であるならば、データ管理部は、このデータがＨｏｔデータであると認識することができる。

データ管理部は、同じＳＳＤ内におけるＬＢＡ範囲それぞれの更新頻度をできるだけ同じ範囲の頻度に揃えるために、Ｈｏｔデータであると認識されたデータをＳＳＤ３から別のストレージデバイスに移動しても良い。

あるいは、もしＳＳＤ３が高い耐久性を有する高価格ＳＳＤとして実現されているならば、ＨｏｔデータをＳＳＤ３内に残し、ＣｏｌｄデータをＳＳＤ３から別のストレージデバイスに移動しても良い。高い耐久性を有する高価格ＳＳＤの例は、メモリセル当たりに１ビットの情報を格納するＳＬＣ−ＳＳＤを含む。

ＳＳＤの耐久性を示す指標の一つに、ＤＷＰＤ（Drive Write Per Day）がある。例えば、ＤＷＰＤ＝１０は、１Ｔバイトの総容量を有するＳＳＤに関しては、１日当たり１０Ｔバイト（＝１０×１Ｔバイト）のデータのライトを５年間に渡って毎日実行することができることを意味する。

以下では、前者のための処理の手順の例を説明する。

ホスト２は、ＬＢＡｘを含むライトコマンドをＳＳＤ３に送信し（ステップＳ８１）、累積データ書き込み量または時間経過値を含む応答（許可応答、コマンド完了レスポンス）をＳＳＤ３から受信する（ステップＳ８２）。

ホスト２は、累積データ書き込み量または時間経過値に基づき、ＬＢＡｘのデータの更新頻度（ＬＢＡｘへのライトの頻度）が所定の上限頻度（閾値ｔｈ４）以上であるか否かを判定する（ステップＳ８３）。例えば、ＳＳＤ３から累積データ書き込み量が通知されるケースにおいては、ホスト２は、累積データ書き込み量が閾値ｔｈ４によって示される閾データ量以上であるかを判定してもよい。ＳＳＤ３から時間経過値（同じＬＢＡへの前回のライトの時刻）が通知されるケースにおいては、ホスト２は、現在時刻から前回のライトの時刻を引くことによって時間間隔を算出し、この時間間隔が、閾値ｔｈ４によって示される閾時間間隔以上であるか否かを判定してもよい。あるいは、ホスト２は、累積データ書き込み量または時間経過値を、何回のライトアクセスに１回の割合でＬＢＡｘへのライトが発生するかを示す割合［パーセント］に換算し、この時間間隔が、閾値ｔｈ４によって示される閾時間間隔以上であるか否かを判定してもよい。

ＬＢＡｘのデータの更新頻度（ＬＢＡｘへのライトの頻度）が閾値ｔｈ４以上であるならば（ステップＳ８３のＹＥＳ）、ホスト２は、ＬＢＡｘのデータを高更新頻度データグループ（Ｈｏｔデータ）に分類し（ステップＳ８４）、ＬＢＡｘのデータをＳＳＤ３から他のストレージデバイスに移動する（ステップＳ８５）。

ステップＳ８４においては、もし累積データ書き込み量または時間経過値が含まれるレスポンスがライトコマンドに対する許可応答であったならば、ホスト２は、ライトコマンドをアボートする処理を実行してもよい。

図２３は、ホスト２として機能する情報処理装置のハードウェア構成例を示す。

この情報処理装置は、サーバコンピュータ、またはパーソナルコンピュータとして実現される。この情報処理装置は、プロセッサ（ＣＰＵ）１０１、メインメモリ１０２、ＢＩＯＳ−ＲＯＭ１０３、ネットワークコントローラ１０５、周辺インタフェースコントローラ１０６、コントローラ１０７、およびエンベデッドコントローラ（ＥＣ）１０８等を含む。

プロセッサ１０１は、この情報処理装置の各コンポーネントの動作を制御するように構成されたＣＰＵである。このプロセッサ１０１は、複数のＳＳＤ３のいずれか１つからメインメモリ１０２にロードされる様々なプログラムを実行する。メインメモリ１０２は、ＤＲＡＭのようなランダムアクセスメモリから構成される。プロセッサ１０１によって実行されるプログラムは、上述のアプリケーションソフトウェアレイヤ４１、ＯＳ４２およびファイルシステム４３を含む。

また、プロセッサ１０１は、不揮発性メモリであるＢＩＯＳ−ＲＯＭ１０３に格納された基本入出力システム（ＢＩＯＳ）も実行する。ＢＩＯＳはハードウェア制御のためのシステムプログラムである。

ネットワークコントローラ１０５は、有線ＬＡＮコントローラ、無線ＬＡＮコントローラのような通信デバイスである。周辺インタフェースコントローラ１０６は、ＵＳＢデバイスのような周辺デバイスとの通信を実行するように構成されている。

コントローラ１０７は、複数のコネクタ１０７Ａにそれぞれ接続されるデバイスとの通信を実行するように構成されている。本実施形態では、複数のＳＳＤ３が複数のコネクタ１０７Ａにそれぞれ接続される。コントローラ１０７は、ＳＡＳ ｅｘｐａｎｄｅｒ、ＰＣＩｅ Ｓｗｉｔｃｈ、ＰＣＩｅ ｅｘｐａｎｄｅｒ、フラッシュアレイコントローラ、またはＲＡＩＤコントローラ等である。

ＥＣ１０８は、情報処理装置の電力管理を実行するように構成されたシステムコントローラとして機能する。ＥＣ１０８は、ユーザによる電源スイッチの操作に応じて情報処理装置をパワーオンおよびパワーオフする。ＥＣ１０８はワンチップマイクロコントローラのような処理回路として実現されている。ＥＣ１０８は、キーボード（ＫＢ）などの入力デバイスを制御するキーボードコントローラを内蔵していてもよい。

図２２で説明した処理は、ファイルシステム４３の制御の下、プロセッサ１０１によって実行される。

図２４は、複数のＳＳＤ３とホスト２とを含む情報処理装置の構成例を示す。

この情報処理装置は、ラックに収容可能な薄い箱形の筐体２０１を備える。多数のＳＳＤ３は筐体２０１内に配置されても良い。この場合、各ＳＳＤ３は筐体２０１の前面２０１Ａに設けられたスロットに取り外し可能に挿入されてもよい。

システムボード（マザーボード）２０２は筐体２０１内に配置される。システムボード（マザーボード）２０２上においては、ＣＰＵ１０１、メモリ１０２、ネットワークコントローラ１０５、コントローラ１０７を含む様々な電子部品が実装されている。これら電子部品がホスト２として機能する。

以上説明したように、本実施形態の「ブロック内のデータのＧＣ回数を考慮したＧＣ機能」によれば、ホスト２によって書き込まれたデータを含むブロック毎に、当該ブロック内のデータがガベージコレクション（ＧＣ）動作によってコピーされた回数を示すＧＣ回数が管理され、且つ同じＧＣ回数に関連づけられた複数のブロック（第１ブロック）が、ガベージコレクション（ＧＣ）動作の対象ブロックとして選択される。そして、これら第１ブロック内の有効データがコピー先フリーブロックにコピーされ、これら第１ブロックのＧＣ回数に１を加えた値が、コピー先フリーブロックのＧＣ回数として設定される。したがって、更新頻度の高いデータと更新頻度の低いデータとがＧＣ動作によって一緒に同じブロックにコピーされてしまうことを防止できるようになる。これにより、ＧＣ回数の多いブロックほど、ブロックの容量に対する更新頻度の低いデータの量の割合を増やすことができるので、更新頻度の低いデータを、更新頻度の高いデータから分離することが可能とする。このことは、更新頻度の異なる複数種のデータが混在するブロックの数の増加を抑制できることを意味する。よって、たとえＳＳＤ３に書かれるデータが高いデータ局所性を有する場合であっても、更新頻度の高いデータと更新頻度の低いデータとが混在するブロックの数の増加を抑制でき、この結果、ＳＳＤ３のライトアンプリフィケーションの増加を抑制できる。

なお、本実施形態では、不揮発性メモリとしてＮＡＮＤメモリを例示した。しかし、本実施形態の機能は、例えば、ＭＲＡＭ（Ｍａｇｎｅｔｏｒｅｓｉｓｔｉｖｅ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＰＲＡＭ（Ｐｈａｓｅ ｃｈａｎｇｅ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＲｅＲＡＭ（Ｒｅｓｉｓｔｉｖｅ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、又は、ＦｅＲＡＭ（Ｆｅｒｒｏｅｌｅｃｔｒｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）のような他の様々な不揮発性メモリにも適用できる。

本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

２…ホスト、３…ＳＳＤ、４…コントローラ、５…ＮＡＮＤメモリ、２１…ガベージコレクション回数管理部、２２…ガベージコレクション動作制御部、２３…更新頻度情報応答部。

Claims (13)

1. 複数のブロックを含む不揮発性メモリと、
   前記不揮発性メモリに電気的に接続され、前記不揮発性メモリのガベージコレクション動作を実行するように構成されたコントローラとを具備し、
   前記コントローラは、
   前記複数のブロックの内の、ホストによって書き込まれたデータを含むブロック毎に、当該ブロック内のデータが前記ガベージコレクション動作によってコピーされた回数を示すガベージコレクション回数を管理し、
   同じガベージコレクション回数に関連づけられた複数の第１ブロックを、前記ガベージコレクション動作の対象ブロックとして選択し、
   前記複数の第１ブロック内の有効データをコピー先フリーブロックにコピーし、
   前記複数の第１ブロックのガベージコレクション回数に１を加えた値を、前記コピー先フリーブロックのガベージコレクション回数として設定するように構成されているメモリシステム。
2. 前記複数の第１ブロックは、無効データ量が最も多いブロックと、前記無効データ量が最も多いブロックのガベージコレクション回数と同じガベージコレクション回数に関連づけられた一以上の別のブロックとを含む請求項１記載のメモリシステム。
3. 前記コントローラは、
   同じガベージコレクション回数に関連づけられた第１ブロック群が前記ガベージコレクション動作の対象ブロックとして選択された場合、
   前記第１ブロック群内の有効データの総量が第１閾値よりも少ないか否かを判定し、
   前記第１ブロック群内の有効データの総量が前記第１閾値よりも少ない場合、前記第１ブロック群のガベージコレクション回数よりも１回以上少ないガベージコレクション回数に関連づけられた全てのブロック群の中で、最大のガベージコレクション回数に関連づけられている第２ブロック群を選択し、前記第１ブロック群の有効データと前記第２ブロック群内の有効データを前記コピー先フリーブロックにコピーするように構成されている請求項１記載のメモリシステム。
4. 前記第１閾値は、一つのブロックに書き込み可能なデータの総量を示す値に設定されている請求項３記載のメモリシステム。
5. 前記コントローラは、前記第１ブロック群のガベージコレクション回数に１を加えた値を、前記コピー先フリーブロックのガベージコレクション回数として設定するように構成されている請求項３記載のメモリシステム。
6. 前記コントローラは、前記第２ブロック群のガベージコレクション回数に１を加えた値を、前記コピー先フリーブロックのガベージコレクション回数として設定するように構成されている請求項３記載のメモリシステム。
7. 前記コントローラは、
   同じガベージコレクション回数に関連づけられた第１ブロック群が前記ガベージコレクション動作の対象ブロックとして選択された場合、
   前記第１ブロック群内の有効データの総量が第１閾値よりも少ないか否かを判定し、
   前記第１ブロック群内の有効データの総量が前記第１閾値よりも少ない場合、前記第１ブロック群のガベージコレクション回数が第２閾値以上であるか否かを判定し、
   前記第１ブロック群のガベージコレクション回数が前記第２閾値以上である場合、前記第１ブロック群のガベージコレクション回数よりも１回以上少ないガベージコレクション回数に関連づけられた全てのブロック群の中で、最大のガベージコレクション回数に関連づけられている第２ブロック群を選択し、前記第１ブロック群の有効データと前記第２ブロック群内の有効データを前記コピー先フリーブロックにコピーし、
   前記第１ブロック群のガベージコレクション回数が前記第２閾値よりも少ない場合、前記第２ブロック群の選択と前記第１ブロック群および前記第２ブロック群の有効データのコピーの代わりに、同じガベージコレクション回数を有する第３ブロック群を前記ガベージコレクション動作の対象ブロックとして選択するように構成されている請求項１記載のメモリシステム。
8. 前記第１閾値は、一つのブロックに書き込み可能なデータの総量を示す値に設定されている請求項７記載のメモリシステム。
9. 前記コントローラは、前記第１ブロック群のガベージコレクション回数に１を加えた値を、前記コピー先フリーブロックのガベージコレクション回数として設定するように構成されている請求項７記載のメモリシステム。
10. 前記コントローラは、前記第２ブロック群のガベージコレクション回数に１を加えた値を、前記コピー先フリーブロックのガベージコレクション回数として設定するように構成されている請求項７記載のメモリシステム。
11. 複数のブロックを含む不揮発性メモリと、
    前記不揮発性メモリに電気的に接続され、前記不揮発性メモリのガベージコレクション動作を実行するように構成されたコントローラとを具備し、
    前記コントローラは、
    前記複数のブロックの内の、ホストによって書き込まれたデータを含むブロック毎に、当該ブロック内のデータが前記ガベージコレクション動作によってコピーされた回数を示すガベージコレクション回数を管理し、
    前記ホストによって書き込まれたデータを含むブロックから、無効データ量が最も多いブロックを選択し、
    前記無効データ量が最も多いブロックと、前記無効データ量が最も多いブロックのガベージコレクション回数と同じガベージコレクション回数に関連づけられた一以上の第１ブロックとを、前記ガベージコレクション動作の対象ブロックとして選択し、
    前記無効データ量が最も多いブロックの有効データと前記一以上の第１ブロック内の有効データとを、コピー先フリーブロックにコピーし、
    前記ガベージコレクション動作の前記対象ブロックのガベージコレクション回数に１を加えた値を、前記コピー先フリーブロックのガベージコレクション回数として設定するように構成されているメモリシステム。
12. 複数のブロックを含む不揮発性メモリを制御し、前記不揮発性メモリのガベージコレクション動作を実行する制御方法であって、
    前記複数のブロックの内の、ホストによって書き込まれたデータを含むブロック毎に、当該ブロック内のデータが前記ガベージコレクション動作によってコピーされた回数を示すガベージコレクション回数を管理することと、
    同じガベージコレクション回数に関連づけられた複数の第１ブロックを、前記ガベージコレクション動作の対象ブロックとして選択することと、
    前記複数の第１ブロック内の有効データをコピー先フリーブロックにコピーすることと、
    前記複数の第１ブロックのガベージコレクション回数に１を加えた値を、前記コピー先フリーブロックのガベージコレクション回数として設定することとを具備する制御方法。
13. 前記複数の第１ブロックは、無効データ量が最も多いブロックと、前記無効データ量が最も多いブロックのガベージコレクション回数と同じガベージコレクション回数に関連づけられた一以上の別のブロックとを含む請求項１２記載の制御方法。

Images