(57)【要約】【課題】  データが書き込まれる際のレイテンシーの変動を抑制できるメモリシステムを実現する。【解決手段】  実施形態によれば、メモリシステムは不揮発性メモリとコントローラとを具備する。前記コントローラは、前記不揮発性メモリからガベージコレクション（ＧＣ）の対象ブロックとして選択された第１ブロック内のデータ部を順に選択し、前記選択されたデータ部が有効データであるならば、当該データ部を、前記不揮発性メモリ内のフリーブロック群から前記ＧＣのためのコピー先ブロックとして割り当てられた第２ブロックにコピーし、前記選択されたデータ部が無効データであるならば、前記ＧＣ動作中に見つけられた無効データ部の数を示す累積無効データ数に１を加算するＧＣ動作を実行し、前記累積無効データ数の範囲内でホストからの書き込みデータ部の受付を許可し、且つ受付た書き込みデータ部の数だけ前記累積無効データ数を減少させる。【選択図】図２
2018049522.tif 000002
【特許請求の範囲】
【請求項１】
不揮発性メモリと、
前記不揮発性メモリに電気的に接続されたコントローラであって、
前記不揮発性メモリからガベージコレクションの対象ブロックとして選択された第１ブロック内のデータ部を順に選択し、前記選択されたデータ部が有効データであるならば、当該データ部を、前記不揮発性メモリ内のフリーブロック群から前記ガベージコレクションのためのコピー先ブロックとして割り当てられた第２ブロックにコピーし、前記選択されたデータ部が無効データであるならば、ガベージコレクション動作中に見つけられた無効データ部の数を示す累積無効データ数に１を加算するガベージコレクション動作を実行し、
前記累積無効データ数の範囲内でホストからの書き込みデータ部の受付を許可し、且つ受付た書き込みデータ部の数だけ前記累積無効データ数を減少させるように構成されるコントローラとを具備するメモリシステム。
【請求項２】
前記コントローラは、さらに、アドレス変換テーブルを使用して論理ブロックアドレスそれぞれと前記不揮発性メモリの物理アドレスそれぞれとの間のマッピングを管理サイズ単位で管理し、前記累積無効データ数は、前記管理サイズ単位で無効データ部の数を示す請求項１記載のメモリシステム。
【請求項３】
前記コントローラは、さらに、前記フリーブロック群から、前記ホストからの書き込みデータ部それぞれを書き込むための書き込み先ブロックを割り当て、前記書き込み先ブロックが割り当てられた時、前記フリーブロック群に含まれるフリーブロックの数が閾値以上であるならば、前記累積無効データ数に、前記書き込み先ブロックに書き込み可能なデータ部の数を加算するように構成される請求項１記載のメモリシステム。
【請求項４】
前記コントローラは、さらに、前記フリーブロック群に含まれるフリーブロックの数が閾値以上である場合、前記ガベージコレクション動作を実行せず、前記フリーブロック群に含まれるフリーブロックの数が前記閾値未満である場合、前記ガベージコレクション動作を実行するように構成される請求項１記載のメモリシステム。
【請求項５】
前記コントローラは、さらに、前記ガベージコレクションの対象ブロックに対する前記ガベージコレクション動作の実行が完了した場合、前記対象ブロックを前記フリーブロック群に返却するように構成される請求項１記載のメモリシステム。
【請求項６】
前記コントローラは、さらに、
前記不揮発性メモリを、第１ネームスペースに関連付けられた書き込みデータ部それぞれを書き込むための第１領域と第２ネームスペースに関連付けられた書き込みデータ部それぞれを書き込むための第２領域とに論理的に分割し、
前記第１領域のガベージコレクションのための第１ガベージコレクション動作であって、前記第１領域に割り当てられた前記前記不揮発性メモリ内のブロック群から前記第１領域のガベージコレクションの対象ブロックとして選択された第３ブロック内のデータ部を順に選択し、前記選択されたデータ部が有効データであるならば、当該データ部を、前記フリーブロック群から前記第１領域のガベージコレクションのためのコピー先ブロックとして割り当てられた第４ブロックにコピーし、前記選択されたデータ部が無効データであるならば、前記第１ガベージコレクション動作中に見つけられた無効データ部の数を示す第１累積無効データ数に１を加算する第１ガベージコレクション動作を実行し、
前記第２領域のガベージコレクションのための第２ガベージコレクション動作であって、前記第２領域に割り当てられた前記前記不揮発性メモリ内のブロック群から前記第２領域のガベージコレクションの対象ブロックとして選択された第５ブロック内のデータ部を順に選択し、前記選択されたデータ部が有効データであるならば、当該データ部を、前記フリーブロック群から前記第２領域のガベージコレクションのためのコピー先ブロックとして割り当てられた第６ブロックにコピーし、前記選択されたデータ部が無効データであるならば、前記第２ガベージコレクション動作中に見つけられた無効データ部の数を示す第２累積無効データ数に１を加算する第２ガベージコレクション動作を実行し、
前記第１累積無効データ数の範囲内で前記ホストからの前記第１ネームスペースに関連付けられた書き込みデータ部の受付を許可し、且つ受付た書き込みデータ部の数だけ前記第１累積無効データ数を減少させ、
前記第２累積無効データ数の範囲内で前記ホストからの前記第２ネームスペースに関連付けられた書き込みデータ部の受付を許可し、且つ受付た書き込みデータ部の数だけ前記第２累積無効データ数を減少させるように構成される請求項１記載のメモリシステム。
【請求項７】
前記コントローラは、さらに、
前記不揮発性メモリを、第１ネームスペースに関連付けられた書き込みデータ部それぞれが書き込まれる第１領域と第２ネームスペースに関連付けられた書き込みデータ部それぞれが書き込まれる第２領域とに論理的に分割し、
前記第１領域のガベージコレクションのための第１ガベージコレクション動作であって、前記第１領域に割り当てられた前記前記不揮発性メモリ内のブロック群から前記第１領域のガベージコレクションの対象ブロックとして選択された第３ブロック内のデータ部を順に選択し、前記選択されたデータ部が有効データであるならば、当該データ部を、前記フリーブロック群から前記第１領域のガベージコレクションのためのコピー先ブロックとして割り当てられた第４ブロックにコピーし、前記選択されたデータ部が無効データであるならば、前記第１ガベージコレクション動作中に見つけられた無効データ部の数を示す第１累積無効データ数に１を加算する第１ガベージコレクション動作を実行し、
前記第２領域のガベージコレクションのための第２ガベージコレクション動作であって、前記第２領域に割り当てられた前記前記不揮発性メモリ内のブロック群から前記第２領域のガベージコレクションの対象ブロックとして選択された第５ブロック内のデータ部を順に選択し、前記選択されたデータ部が有効データであるならば、当該データ部を、前記フリーブロック群から前記第２領域のガベージコレクションのためのコピー先ブロックとして割り当てられた第６ブロックにコピーし、前記選択されたデータ部が無効データであるならば、前記第２ガベージコレクション動作中に見つけられた無効データ部の数を示す第２累積無効データ数に１を加算する第２ガベージコレクション動作を実行し、
前記第１累積無効データ数と前記第２累積無効データ数との合計の範囲内で前記ホストからの書き込みデータ部の受付を許可するように構成される請求項１記載のメモリシステム。
【請求項８】
前記コントローラは、さらに、前記メモリシステムで不足しているフリーブロックの数が２つ以上である場合、前記第１累積無効データ数と前記第２累積無効データ数との合計を、前記メモリシステムで不足しているフリーブロックの数で除した値の範囲内で前記ホストからの書き込みデータ部の受付を許可するように構成される請求項７記載のメモリシステム。
【請求項９】
不揮発性メモリと、
前記不揮発性メモリに電気的に接続されたコントローラであって、
前記不揮発性メモリを、第１ネームスペースに関連付けられた書き込みデータ部それぞれを書き込むための第１領域と第２ネームスペースに関連付けられた書き込みデータ部それぞれを書き込むための第２領域とに論理的に分割し、
前記第１領域のガベージコレクションのための第１ガベージコレクション動作であって、前記第１領域に割り当てられた前記前記不揮発性メモリ内のブロック群から前記第１領域のガベージコレクションの対象ブロックとして選択された第１ブロック内のデータ部を順に選択し、前記選択されたデータ部が有効データであるならば、当該データ部を、前記不揮発性メモリ内のフリーブロック群から前記第１領域のガベージコレクションのためのコピー先ブロックとして割り当てられた第２ブロックにコピーし、前記選択されたデータ部が無効データであるならば、前記第１ガベージコレクション動作中に見つけられた無効データ部の数を示す第１累積無効データ数に１を加算する第１ガベージコレクション動作を実行し、
前記第２領域のガベージコレクションのための第２ガベージコレクション動作であって、前記第２領域に割り当てられた前記前記不揮発性メモリ内のブロック群から前記第２領域のガベージコレクションの対象ブロックとして選択された第３ブロック内のデータ部を順に選択し、前記選択されたデータ部が有効データであるならば、当該データ部を、前記フリーブロック群から前記第２領域のガベージコレクションのためのコピー先ブロックとして割り当てられた第４ブロックにコピーし、前記選択されたデータ部が無効データであるならば、前記第２ガベージコレクション動作中に見つけられた無効データ部の数を示す第２累積無効データ数に１を加算する第２ガベージコレクション動作を実行し、
前記第１累積無効データ数の範囲内でホストからの前記第１ネームスペースに関連付けられた書き込みデータ部の受付を許可し、且つ受付た書き込みデータ部の数だけ前記第１累積無効データ数を減少させ、
前記第２累積無効データ数の範囲内で前記ホストからの前記第２ネームスペースに関連付けられた書き込みデータ部の受付を許可し、且つ受付た書き込みデータ部の数だけ前記第２累積無効データ数を減少させるように構成されるコントローラとを具備するメモリシステム。
【請求項１０】
前記コントローラは、さらに、
前記フリーブロック群から、前記第１ネームスペースに関連付けられた書き込みデータ部それぞれを書き込むための書き込み先ブロックを前記第１領域に割り当て、前記書き込み先ブロックが割り当てられた時、前記フリーブロック群に含まれるフリーブロックの数が閾値以上であるならば、前記第１累積無効データ数に、前記書き込み先ブロックに書き込み可能なデータ部の数を加算し、
前記フリーブロック群から、前記第２ネームスペースに関連付けられた書き込みデータ部それぞれを書き込むための書き込み先ブロックを前記第２領域に割り当て、前記書き込み先ブロックが割り当てられた時、前記フリーブロック群に含まれるフリーブロックの数が閾値以上であるならば、前記第２累積無効データ数に、前記書き込み先ブロックに書き込み可能なデータ部の数を加算するように構成される請求項９記載のメモリシステム。
【請求項１１】
前記コントローラは、さらに、第１アドレス変換テーブルを使用して前記第１ネームスペースの論理ブロックアドレスそれぞれと前記第１領域の物理アドレスそれぞれとの間のマッピングを管理サイズ単位で管理し、第２アドレス変換テーブルを使用して前記第２ネームスペースの論理ブロックアドレスそれぞれと前記第２領域の物理アドレスそれぞれとの間のマッピングを前記管理サイズ単位で管理し、
前記第１累積無効データ数および前記第１累積無効データ数は、前記管理サイズ単位で無効データ部の数を示す請求項９記載のメモリシステム。
【請求項１２】
不揮発性メモリを含むメモリシステムの制御方法であって、
前記不揮発性メモリからガベージコレクションの対象ブロックとして選択された第１ブロック内のデータ部を順に選択し、前記選択されたデータ部が有効データであるならば、当該データ部を、前記不揮発性メモリ内のフリーブロック群から前記ガベージコレクションのためのコピー先ブロックとして割り当てられた第２ブロックにコピーし、前記選択されたデータ部が無効データであるならば、前記ガベージコレクション動作中に見つけられた無効データ部の数を示す累積無効データ数に１を加算するガベージコレクション動作を実行することと、
前記累積無効データ数の範囲内でホストからの書き込みデータ部の受付を許可し、且つ受付た書き込みデータ部の数だけ前記累積無効データ数を減少させることとを具備する制御方法。
【請求項１３】
前記フリーブロック群から、前記ホストからの書き込みデータ部それぞれを書き込むための書き込み先ブロックを割り当てることと、
前記書き込み先ブロックが割り当てられた時、前記フリーブロック群に含まれるフリーブロックの数が閾値以上であるならば、前記累積無効データ数に、前記書き込み先第２ブロックに書き込み可能なデータ部の数に相当するデータ数を加算することとをさらに具備する請求項１２記載の制御方法。
【請求項１４】
アドレス変換テーブルを使用して論理ブロックアドレスそれぞれと前記不揮発性メモリの物理アドレスそれぞれとの間のマッピングを管理サイズ単位で管理することをさらに具備し、前記累積無効データ数は、前記管理サイズ単位で無効データ部の数を示す請求項１２記載の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、不揮発性メモリを制御する技術に関する。
【背景技術】
【０００２】
近年、不揮発性メモリを備えるメモリシステムが広く利用されている。このようなメモリシステムの一つとして、ＮＡＮＤフラッシュ技術ベースのソリッドステートドライブ（ＳＳＤ）が知られている。ＳＳＤは、その低電力消費、高性能という特徴により、様々なコンピュータのメインストレージとして使用されている。
【０００３】
最近では、ホストとメモリシステムとの間のデータ入出力に関する性能のさらなる向上が要求されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第４３５８２９９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ホストとメモリシステムとの間のデータ入出力の性能向上を図るためには、ライトレイテンシーの変動を低減するための新たな機能の実現が必要とされる。
【０００６】
本発明が解決しようとする課題は、ライトレイテンシーの変動を低減できるメモリシステム及び制御方法を提供することである。
【課題を解決するための手段】
【０００７】
実施形態によれば、メモリシステムは、不揮発性メモリと、コントローラとを具備する。前記コントローラは、前記不揮発性メモリに電気的に接続される。前記コントローラは、前記不揮発性メモリからガベージコレクションの対象ブロックとして選択された第１ブロック内のデータ部を順に選択し、前記選択されたデータ部が有効データであるならば、当該データ部を、前記不揮発性メモリ内のフリーブロック群から前記ガベージコレクションのためのコピー先ブロックとして割り当てられた第２ブロックにコピーし、前記選択されたデータ部が無効データであるならば、前記ガベージコレクション動作中に見つけられた無効データ部の数を示す累積無効データ数に１を加算するガベージコレクション動作を実行する。前記コントローラは、前記累積無効データ数の範囲内でホストからの書き込みデータ部の受付を許可し、且つ受付た書き込みデータ部の数だけ前記累積無効データ数を減少させる。
【図面の簡単な説明】
【０００８】
【図１】実施形態に係るメモリシステムを含む情報処理システムの構成例を示すブロック図。
【図２】同実施形態のメモリシステムによるデータ書き込み動作とガベージコレクション動作とを説明するための図。
【図３】図２のデータ書き込み動作が行われた場合のデータの流れの例を説明するための図。
【図４】図２のデータ書き込み動作及びガベージコレクション動作が行われた場合のデータの流れの例を説明するための図。
【図５】同実施形態のメモリシステムによって実行される書き込み処理の手順の例を示すフローチャート。
【図６】同実施形態のメモリシステムによって実行されるホスト書き込み先ブロック割り当て処理の手順の例を示すフローチャート。
【図７】同実施形態のメモリシステムによって実行されるガベージコレクション処理の手順の例を示すフローチャート。
【図８】同実施形態のメモリシステムがマルチネームスペース機能を有する場合のデータ書き込み動作とガベージコレクション動作との例を説明するための図。
【図９】同実施形態のメモリシステムによって実行される書き込み処理の手順の別の例を示すフローチャート。
【図１０】同実施形態のメモリシステムによって実行されるホスト書き込み先ブロック割り当て処理の手順の別の例を示すフローチャート。
【図１１】同実施形態のメモリシステムによって実行されるガベージコレクション処理の手順の別の例を示すフローチャート。
【図１２】同実施形態のメモリシステムがマルチネームスペース機能を有する場合のデータ書き込み動作とガベージコレクション動作との別の例を説明するための図。
【図１３】ホストの構成例を説明するブロック図。
【図１４】同実施形態のメモリシステムとホストとを含むコンピュータの構成例を示すブロック図。
【発明を実施するための形態】
【０００９】
以下、実施の形態について図面を参照して説明する。
【００１０】
まず、図１を参照して、一実施形態に係るメモリシステムを含む情報処理システム１の構成を説明する。
【００１１】
このメモリシステムは、不揮発性メモリにデータをライトし、不揮発性メモリからデータをリードするように構成された半導体ストレージデバイスである。このメモリシステムは、例えば、ＮＡＮＤフラッシュ技術ベースのソリッドステートドライブ（ＳＳＤ）３として実現されている。
【００１２】
この情報処理システム１は、ホスト計算機（以下、ホストとも称する）２と、ＳＳＤ３とを含む。ホスト２は、ＳＳＤ３にデータに保存するように構成された情報処理装置（コンピューティングデバイス）である。この情報処理装置の例には、サーバコンピュータ及びパーソナルコンピュータが含まれる。
【００１３】
ＳＳＤ３は、ホスト２として機能する情報処理装置に内蔵されてもよいし、この情報処理装置にケーブルまたはネットワークを介して接続されてもよい。
【００１４】
ホスト２とＳＳＤ３とを相互接続するためのインターフェースとしては、ＳＣＳＩ、Ｓｅｒｉａｌ  Ａｔｔａｃｈｅｄ  ＳＣＳＩ（ＳＡＳ）、ＡＴＡ、Ｓｅｒｉａｌ  ＡＴＡ（ＳＡＴＡ）、ＰＣＩ  Ｅｘｐｒｅｓｓ（ＰＣＩｅ）、ＮＶＭ  Ｅｘｐｒｅｓｓ（ＮＶＭｅ）、Ｅｔｈｅｒｎｅｔ（登録商標）、Ｆｉｂｒｅ  ｃｈａｎｎｅｌ等を使用し得る。
【００１５】
ＳＳＤ３は、コントローラ４、不揮発性メモリ（ＮＡＮＤメモリ）５、及びＤＲＡＭ６を備えていてもよい。ＮＡＮＤメモリ５は、限定されないが、複数のＮＡＮＤフラッシュメモリチップを含んでいてもよい。
【００１６】
ＮＡＮＤメモリ５はメモリセルアレイを含み、このメモリセルアレイは、多数のＮＡＮＤブロック（ブロック）Ｂ０〜Ｂｍ−１を含む。ブロックＢ０〜Ｂｍ−１は、消去単位として機能する。ブロックは「物理ブロック」または「消去ブロック」と称されることもある。
【００１７】
ブロックＢ０〜Ｂｍ−１は多数のページ（物理ページ）を含む。つまり、ブロックＢ０〜Ｂｍ−１の各々は、ページＰ０〜Ｐｎ−１を含む。同じワード線に接続された複数のメモリセルが一つのページとして編成される。ＮＡＮＤメモリ５においては、データのリード及びデータのライトはページ単位で実行される。データの消去は複数ページを含むブロック単位で実行される。
【００１８】
コントローラ４は、Ｔｏｇｇｌｅ、ＯＮＦＩのようなＮＡＮＤインターフェース１３を介して、不揮発性メモリであるＮＡＮＤメモリ５に電気的に接続されている。コントローラ４は、ＮＡＮＤメモリ５のデータ管理とＮＡＮＤメモリ５のブロック管理とを実行するように構成されたフラッシュトランスレーション層（ＦＴＬ）として機能し得る。
【００１９】
データ管理には、（１）論理ブロックアドレス（ＬＢＡ）と物理アドレスとの間の対応関係を示すマッピング情報の管理、（２）ページ単位のリード／ライトとブロック単位の消去動作とを隠蔽するための処理、等が含まれる。ＬＢＡと物理アドレスとの間のマッピングの管理は、論理物理アドレス変換テーブルとして機能するルックアップテーブル（ＬＵＴ）３３を用いて実行される。ルックアップテーブル（ＬＵＴ）３３は、所定の管理サイズ単位で、ＬＢＡと物理アドレスとの間のマッピングを管理サイズ単位で管理する。ホスト２からのライトコマンドの多くは、４Ｋバイトのデータの書き込みを要求する。したがって、ルックアップテーブル（ＬＵＴ）３３は、例えば４Ｋバイトの管理サイズ単位で、ＬＢＡと物理アドレスとの間のマッピングを管理してもよい。あるＬＢＡに対応する物理アドレスは、このＬＢＡのデータがライトされたＮＡＮＤメモリ５内の物理記憶位置を示す。物理アドレスは、物理ブロックアドレスと物理ページアドレスとを含む。物理ページアドレスは全てのページに割り当てられており、また物理ブロックアドレスは全てのブロックに割り当てられている。
【００２０】
ページへのデータ書き込みは、１消去サイクル当たり１回のみ可能である。
【００２１】
このため、コントローラ４は、同じＬＢＡへのライト（上書き）を、ＮＡＮＤメモリ５上の別のページにマッピングする。つまり、コントローラ４は、この別のページにデータをライトする。そして、コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を更新してこのＬＢＡをこの別のページに関連付けると共に、元のページ（つまりこのＬＢＡが関連付けられていた古いデータ）を無効化する。
【００２２】
ブロック管理には、不良ブロックの管理と、ウェアレベリングと、ガベージコレクション動作等が含まれる。
【００２３】
ガベージコレクション動作は、ＮＡＮＤメモリ５内のフリースペースを作り出すための動作である。このガベージコレクション動作は、ＮＡＮＤメモリ５のフリーブロックの個数を増やすため、有効データと無効データとが混在する一つ以上のブロック内の全ての有効データを別のブロック（コピー先フリーブロック）にコピーする。そして、ガベージコレクション動作は、ルックアップテーブル（ＬＵＴ）３３を更新して、コピーされた有効データのＬＢＡそれぞれを正しい物理アドレスにマッピングする。有効データが別のブロックにコピーされることによって無効データのみになったブロックはフリーブロックとして解放される。これによって、このブロックは消去後に再利用することが可能となる。
【００２４】
ホスト２は、ライトコマンドをＳＳＤ３に送出する。このライトコマンドは、書き込みデータ（つまり書き込むべきライトデータ）の論理アドレス（開始論理アドレス）と、転送長とを含む。この実施形態においては、ＬＢＡが論理アドレスとして使用されるが、他の実施形態においてはオブジェクトＩＤが論理アドレスとして使用されても良い。
【００２５】
ＳＳＤ３のコントローラ４は、ライトコマンド内の開始論理アドレスと転送長とによって指定されるライトデータを、ＮＡＮＤメモリ５内のブロックのページにライトする。さらに、コントローラ４は、ルックアップテーブル（ＬＵＴ）３３を更新することによって、ライトされたデータに対応するＬＢＡを、このデータがライトされた物理記憶位置を示す物理アドレスにマッピングする。
【００２６】
より詳しくは、コントローラ４は、ＮＡＮＤメモリ５内のフリーブロックの一つを、ホスト２からのデータの書き込みのための書き込み先ブロックとして割り当てる。この書き込み先ブロックは、ホスト２からのデータが書き込まれるべきブロックであり、「書き込み対象ブロック」、または「入力ブロック」、等とも称される。コントローラ４は、ホスト２から受信されるライトデータのＬＢＡとは無関係に、ルックアップテーブル（ＬＵＴ）３３を更新しながら、ホスト２から受信されるライトデータを書き込み先ブロックの利用可能ページに順次書き込む。書き込み先ブロックに利用可能ページが無くなった場合に、コントローラ４は、新たなフリーブロックを書き込み先ブロックとして割り当てる。
【００２７】
次に、コントローラ４の構成について説明する。
【００２８】
コントローラ４は、ホストインターフェース１１、ＣＰＵ１２、ＮＡＮＤインターフェース１３、ＤＲＡＭインターフェース１４等を含む。これらＣＰＵ１２、ＮＡＮＤインターフェース１３、ＤＲＡＭインターフェース１４は、バス１０を介して相互接続される。
【００２９】
ホストインターフェース１１は、ホスト２から様々なコマンドを受信する。このコマンドは、例えば、ライトコマンド、リードコマンド、及び消去コマンドである。
【００３０】
ＣＰＵ１２は、ホストインターフェース１１、ＮＡＮＤインターフェース１３、ＤＲＡＭインターフェース１４を制御するように構成されたプロセッサである。ＣＰＵ１２は、ＮＡＮＤメモリ５を管理する物理リソース管理処理、ホスト２から受信される様々なコマンドを処理するためのコマンド処理等を実行する。物理リソース管理処理及びコマンド処理は、ＣＰＵ１２によって実行されるファームウェアによって制御されてもよい。
【００３１】
このファームウェアは、ＣＰＵ１２を、ガベージコレクション制御部２１、ライト制御部２２、リード制御部２３、及びネームスペース管理部２４として機能させる。
【００３２】
ガベージコレクション制御部２１は、ガベージコレクション動作の実行を制御する。上述したように、ガベージコレクション動作は、ＮＡＮＤメモリ５内のフリースペースを作り出すための動作である。このガベージコレクション動作により、有効データと無効データとが混在するいくつかのブロック内の全ての有効データが別のブロックにコピーされる。ガベージコレクション制御部２１は、ブロック選択部２１１、データコピー制御部２１２及び累積無効データ数計測部２１３を含む。
【００３３】
ブロック選択部２１１は、ＮＡＮＤメモリ５内の多数のブロックから、ガベージコレクションの対象ブロックを選択する。
【００３４】
データコピー制御部２１２は、ガベージコレクションにおけるデータコピー動作を実行する。データコピー制御部２１２は、ガベージコレクションの対象ブロック内の有効データを、ガベージコレクションのためのコピー先ブロックにコピーするための動作を制御する。ガベージコレクションのためのコピー先ブロックは、ガベージコレクションのための書き込み先ブロックとも称される。
【００３５】
累積無効データ数計測部２１３は、ガベージコレクション動作中に発見された無効データ部の数計測することによって累積無効データ数を算出する。無効データ部の数の計測（カウント）は、例えば、上述の管理サイズ（例えば４ＫＢ）単位で実行されてもよい。累積無効データ数は、ガベージコレクション動作中に発見された無効データ部の数（総数）を示す。さらに、累積無効データ数計測部２１３は、ホスト２から受付た書き込みデータ部の数だけ累積無効データ数を減少させる。換言すれば、累積無効データ数計測部２１３は、ホスト２からの書き込み要求を受け入れた場合、その書き込み要求によって指定された書き込みデータのデータサイズに相当する数を、累積無効データ数から減算する。例えば、１６ＫＢの書き込みデータを書き込むための書き込み要求が受け入れられたならば、４個の書き込みデータ部（４×４ＫＢ）が受付られ、そして累積無効データ数から４が減算される。
【００３６】
ライト制御部２２は、ホスト２からの書き込み要求（ライトコマンド）に応じた書き込み動作を制御する。ライト制御部２２は、累積無効データ数の範囲内でホスト２からの書き込みデータ部の受付を許可する。つまり、ライト制御部２２は、累積無効データ数を上限とする数の書き込みデータ部をホスト２から受付けることができる。ライト制御部２２は、受付た書き込みデータ部それぞれを、ホスト２の書き込み先ブロックに書き込む。
【００３７】
リード制御部２３は、ホスト２からの読み出し要求（リードコマンド）に応じた読み出し動作を制御する。リード制御部２３は、例えば、読み出し要求によって指定されたＬＢＡのデータをＮＡＮＤメモリ５から読み出し、読み出されたデータをホスト２に送信する。
【００３８】
ネームスペース管理部２４は、ＳＳＤ３をあたかも複数のドライブであるかのように扱うことを可能にするために、複数のネームスペースそれぞれに対応する複数の論理アドレス空間（ＬＢＡ空間）を管理する。各ネームスペースには、指定された数のブロックが確保（予約）される。確保されるブロックの数はネームスペース毎に異なっていてもよい。ネームスペース管理部２４は、ＮＡＮＤメモリ５を、複数のネームスペースに関連付けられた複数の領域に論理的に分割する。例えば、第１ネームスペースと第２ネームスペースとがクリエイトされた場合には、ネームスペース管理部２４は、ＮＡＮＤメモリ５を、第１ネームスペースに関連付けられた書き込みデータ部それぞれを書き込むための第１領域と第２ネームスペースに関連付けられた書き込みデータ部それぞれを書き込むための第２領域とに論理的に分割する。
【００３９】
第１ネームスペースの識別子（ＮＳＩＤ＃１）に関連付けられた書き込み要求によって指定される書き込みデータ（つまり、第１ネームスペースに関連付けられた書き込みデータ部それぞれ）は、第１領域（第１ネームスペース）に書き込み先ブロックとして割り当てられたブロックに書き込まれる。この書き込み先ブロックがデータで満たされたならば、新たなブロックが第１領域（第１ネームスペース）に新たな書き込み先ブロックとして割り当てられる。
【００４０】
第２ネームスペースの識別子（ＮＳＩＤ＃２）に関連付けられた書き込み要求によって指定される書き込みデータ（つまり、第２ネームスペースに関連付けられた書き込みデータ部それぞれ）は、第２領域（第２ネームスペース）に書き込み先ブロックとして割り当てられたブロックに書き込まれる。この書き込み先ブロックがデータで満たされたならば、新たなブロックが第２領域（第２ネームスペース）に新たな書き込み先ブロックとして割り当てられる。
【００４１】
図２を参照して、ガベージコレクション制御部２１によるガベージコレクション動作と、ライト制御部２２による書き込み動作とについて説明する。
【００４２】
まず、ガベージコレクション動作について説明する。
【００４３】
ブロック選択部２１１は、アクティブブロック群５５からガベージコレクションの対象ブロック５５１（以下、ＧＣ対象ブロックとも称する）を選択する。アクティブブロック群５５には、現在使用されているブロック、すなわち、アクティブブロックが含まれている。アクティブブロックは、ホスト２からのデータを含むブロックである。無効データ数保持部３４は、各ブロックに含まれる無効データの数を保持していてもよい。ブロック選択部２１１は、この無効データ数保持部３４を参照することにより、例えば無効データが含まれている割合が高いブロックを、ガベージコレクションの対象ブロック５５１として選択してもよい。
【００４４】
データコピー制御部２１２は、ＧＣ対象ブロック５５１内のデータ部それぞれを順に選択する。データコピー制御部２１２は、あるデータ部が選択された時、選択されたデータ部が有効データであるか、それとも無効データであるかを判定する。無効データは、もはや使用されないデータ、つまりＬＢＡが関連付けられていないデータを意味する。有効データは、使用中のデータ、つまりＬＢＡが関連付けられているデータを意味する。選択されたデータ部が有効データである場合、データコピー制御部２１２はそのデータ部をＧＣバッファ３２に一時的に書き込む。また、選択されたデータ部が無効データである場合、データコピー制御部２１２はそのデータ部をＧＣバッファ３２に書き込むことなくスキップする。さらに、累積無効データ数計測部２１３は、データコピー制御部２１２によって一つの選択されたデータ部が無効データであると判定される度に、累積無効データ数に１を加算する。
【００４５】
データコピー制御部２１２は、ＧＣバッファ３２に書き込まれているデータを、例えば、１ページ分ずつ、ガベージコレクションのコピー先ブロック５１２（以下、ＧＣコピー先ブロックとも称する）に書き込む。このＧＣコピー先ブロック５１２はフリーブロック群５１から割り当てられたブロックである。フリーブロック群５１には、現在使用されていないブロック、すなわち、フリーブロックが含まれている。なお、データコピー制御部２１２は、ＧＣコピー先ブロックがまだ割り当てられていない場合には、フリーブロック群５１内の一つのフリーブロックを、新たなＧＣコピー先ブロック５１２として割り当てる。また、データコピー制御部２１２は、割り当てられているＧＣコピー先ブロック５１２の終端までデータが書き込まれた場合、そのＧＣコピー先ブロック５１２をアクティブブロック群５５に移動する。
【００４６】
データコピー制御部２１２は、ＧＣ対象ブロック５５１内の全ての有効データ部が、ＧＣコピー先ブロック５１２に書き込まれた（コピーされた）場合、このＧＣ対象ブロック５５１をフリーブロック群５１に移動する。データコピー制御部２１２は、このＧＣ対象ブロック５５１がフリーブロックとして解放されたことをブロック選択部２１１に通知するようにしてもよい。ブロック選択部２１１は、必要に応じて、新たなＧＣ対象ブロックを選択してもよい。
【００４７】
次いで、ホスト２からの書き込み要求に応じた書き込み動作について説明する。
【００４８】
ライト制御部２２はホスト２からの書き込み要求を受信する。この書き込み要求には、書き込まれるべきデータのデータサイズを指定する情報（転送長）が含まれている。ライト制御部２２は、累積無効データ数の範囲内でホスト２からの書き込みデータ部の受付を許可する。例えば、現在の累積無効データ数が４であれば、ライト制御部２２は、最大で、４つの書き込みデータ部（１６ＫＢの書き込みデータ＝４×４ＫＢ）を受付ることができる。このため、書き込み要求によって指定されているデータサイズに相当するデータ部の数が累積無効データ数以下である場合に、ライト制御部２２は、書き込み要求によって指定されているデータサイズの書き込みデータを受け入れ可能であると判断し、ホスト２に応答する。
【００４９】
この応答は書き込みが許可されたことを示すので、ホスト２は、この応答に応じてＳＳＤ３に書き込みデータを送信する。
【００５０】
ライト制御部２２は、ホスト２から書き込みデータ部それぞれを受付、受付た書き込みデータ部それぞれをライトバッファ３１に一時的に書き込む。また、累積無効データ数計測部２１３は、累積無効データ数から、受付た書き込みデータ部の数を減算することによって、ホスト２から受付た書き込みデータ部の数だけ累積無効データ数を減少させる。ライト制御部２２は、ライトバッファ３１に書き込まれた書き込みデータ部それぞれを、例えばページ単位で、ホスト２用の書き込み先ブロック５１１に書き込む。
【００５１】
なお、ライト制御部２２は、ホスト２の書き込み先ブロック５１１がまだ割り当てられていない場合、割り当てられている書き込み先ブロック５１１の終端までデータが書き込まれた場合、又は書き込み先ブロック５１１にエラーが発生した場合には、フリーブロック群５１内の一つのフリーブロックを、新たな書き込み先ブロック５１１として割り当てる。また、ライト制御部２２は、割り当てられている書き込み先ブロック５１１の終端までデータが書き込まれた場合、その書き込み先ブロック５１１をアクティブブロック群５５に移動する。
【００５２】
累積無効データ数計測部２１３は、ホスト２の書き込み先ブロック５１１が新たに割り当てられた時、フリーブロック群５１に含まれている残りのフリーブロックの数が閾値以上であるか否かを判定する。フリーブロック群５１に含まれている残りのブロックの数が閾値以上である場合、累積無効データ数計測部２１３は、累積無効データ数に、新たに割り当てられた書き込み先ブロック５１１に書き込み可能なデータ部の数を加算する。書き込み先ブロック５１１に書き込み可能なデータ部の数は、このブロックの容量に相当するデータ部の数である。さらに、累積無効データ数計測部２１３は、ライトバッファ３１に現在蓄積されているデータ部がある場合には、累積無効データ数からそのデータ部の数を減算するようにしてもよい。また、フリーブロック群５１に含まれている残りのフリーブロックの数が閾値未満である場合、累積無効データ数計測部２１３は、累積無効データ数に０を設定する。さらに、累積無効データ数計測部２１３は、ライトバッファ３１に現在蓄積されているデータ部がある場合には、累積無効データ数からそのデータ部の数を減算するようにしてもよい。
【００５３】
なお、ライト制御部２２は、書き込み要求によって指定されたデータサイズの書き込みデータを受け入れ可能でない場合には、その書き込みデータを受け入れ可能になるまでホスト２に応答しない。ライト制御部２２は、例えば、書き込み要求によって指定されたデータサイズに相当するデータの数が累積無効データ数を超える場合に、書き込み要求によって指定されているデータサイズの書き込みデータを受け入れられないと判断し、ホスト２に応答しない。そして、ライト制御部２２は、上述したガベージコレクション動作によって増加した累積無効データ数が、書き込み要求によって指定されたデータサイズに相当するデータの数以上となった場合に、書き込み要求によって指定されているデータサイズの書き込みデータを受け入れ可能であると判断し、ホスト２に応答する。
【００５４】
図３を参照して、データ書き込み動作が行われる場合のＮＡＮＤメモリ５及びライトバッファ３１上のデータの流れを説明する。ここでは、フリーブロック群５１に閾値以上の数のフリーブロックが含まれている場合を想定する。
【００５５】
（１）まず、フリーブロック群５１からホスト２の書き込み先ブロック５１１Ａが割り当てられ、累積無効データ数に書き込み先ブロック５１１Ａのブロックサイズに相当するデータ数が設定される。例えば、管理サイズが４ＫＢ、ページサイズが１６ＫＢ、ブロック当たりのページの数が２５６である場合には、このブロックサイズに相当するデータ数は、例１０２４（＝１６ＫＢ÷４ＫＢ×２５６）である。
【００５６】
（２）そして、累積無効データ数分の書き込みデータ部Ａ１，Ａ２，．．．，Ａｘがホスト２から受付られ、この書き込みデータ部Ａ１，Ａ２，．．．，Ａｘがライトバッファ３１に一時的に書き込まれる。その際、累積無効データ数は１つの書き込みデータが受付られる毎に１ずつ減算される。
【００５７】
（３）ライトバッファ３１内の書き込みデータ部Ａ１，Ａ２，．．．，Ａｘは、ページ単位で書き込み先ブロック５１１Ａに書き込まれる。
【００５８】
（４）書き込み先ブロック５１１Ａの終端までデータが書き込まれた場合、フリーブロック群５１から新たな書き込み先ブロック５１１Ｂが割り当てられる。そして、累積無効データ数にはブロックサイズに相当するデータ数（例えば、１０２４）が設定される。
【００５９】
（５）次いで、累積無効データ数分の書き込みデータ部Ｂ１，Ｂ２，．．．，Ｂｘがホスト２から受付られ、この書き込みデータ部Ｂ１，Ｂ２，．．．，Ｂｘがライトバッファ３１に一時的に書き込まれる。その際、累積無効データ数は１つの書き込みデータ部が受付られる毎に１ずつ減算される。
【００６０】
（６）ライトバッファ３１内の書き込みデータ部Ｂ１，Ｂ２，．．．，Ｂｘは、ページ単位で書き込み先ブロック５１１Ｂに書き込まれる。
【００６１】
このように、フリーブロック群５１に閾値以上の数のフリーブロックが含まれている間は、ホスト２の書き込み先ブロックの割り当てとそのブロックへのデータの書き込みとが繰り返し行われることになる。
【００６２】
次いで、図４を参照して、ガベージコレクション動作とデータ書き込み動作とが行われる場合の、ＮＡＮＤメモリ５、ライトバッファ３１及びＧＣバッファ３２上のデータの流れを説明する。ここでは、フリーブロック群５１に閾値未満の数のフリーブロックが含まれている場合を想定する。
【００６３】
（１）まず、ガベージコレクションの対象ブロック５５１の先頭から順に未処理のデータ部が選択される。あるデータ部が選択された場合、選択されたデータ部が有効データまたは無効データのいずれであるかが判定される。そして、データ部が無効データである場合には累積無効データ数に１が加算され、データ部が有効データである場合には、そのデータ部がＧＣバッファ３２にコピーされる。
【００６４】
例えば、第１ページの４つのデータ部Ｄ１，Ｄ２，Ｄ３，及びＤ４がそれぞれ無効データ、無効データ、有効データ、有効データである場合、無効データ部Ｄ１が検出されたことに応じて累積無効データ数に１が加算される。同様に、無効データ部Ｄ２が検出されたことに応じて累積無効データ数に１が加算される。そして、有効データ部Ｄ３及びＤ４がＧＣバッファ３２にコピーされる。なお、実際には、データ読み出しはページ単位で実行されるので、４つのデータ部Ｄ１，Ｄ２，Ｄ３，及びＤ４が同時に読み出され、これらデータ部内の有効データ部Ｄ３及びＤ４のみがＧＣバッファ３２に蓄積されてもよい。第２ページの４つのデータ部Ｄ５，Ｄ６，Ｄ７，及びＤ８が無効データ、無効データ、無効データ、有効データである場合、無効データ部Ｄ５が検出されたことに応じて累積無効データ数に１が加算される。同様に、無効データ部Ｄ６が検出されたことに応じて累積無効データ数に１が加算され、無効データ部Ｄ７が検出されたことに応じて累積無効データ数に１が加算される。そして、有効データＤ８がＧＣバッファ３２にコピーされる。上述したように、実際には、データ読み出しはページ単位で実行されるので、４つのデータ部Ｄ５，Ｄ６，Ｄ７，及びＤ８が同時に読み出され、これらデータ部内の有効データ部Ｄ８のみがＧＣバッファ３２に蓄積されてもよい。第３ページの４つのデータＤ９，Ｄ１０，Ｄ１１，及びＤ１２が有効データ、有効データ、無効データ、無効データである場合、有効データ部Ｄ９及びＤ１０がＧＣバッファ３２にコピーされる。そして、無効データＤ１１が検出されたことに応じて累積無効データ数に１が加算される。同様に、無効データＤ１２が検出されたことに応じて累積無効データ数に１が加算される。上述したように、実際には、データ読み出しはページ単位で実行されるので、４つのデータ部Ｄ９，Ｄ１０，Ｄ１１，及びＤ１２が同時に読み出され、これらデータ部内の有効データ部Ｄ９、Ｄ１０のみがＧＣバッファ３２に蓄積されてもよい。
【００６５】
以上のように第１ページから第３ページまでのデータが処理されたことにより、ＧＣバッファ３２には１ページサイズ以上の有効データ部Ｄ３，Ｄ４，Ｄ８，Ｄ９，及びＤ１０が蓄積され、累積無効データ数は７となる。
【００６６】
（２）そして、ＧＣバッファ３２に蓄積された有効データ部Ｄ３，Ｄ４，Ｄ８，Ｄ９，及びＤ１０の内、１ページ分の有効データ部Ｄ３、Ｄ４、Ｄ８、及びＤ９が、ガベージコレクションのコピー先ブロック５１２にコピーされる。この時点で、ガベージコレクション動作が一時中断されてもよく、そしてデータ書き込み動作が実行されてもよい。
【００６７】
（３）データ書き込み動作では、累積無効データ数の範囲内で書き込みデータ部の受付が許可される。例えば、累積無効データ数分の書き込みデータ部Ｗ１，Ｗ２，．．．，Ｗ７がホスト２から受付られ、この書き込みデータ部Ｗ１，Ｗ２，．．．，Ｗ７がライトバッファ３１に一時的に書き込まれる。その際、累積無効データ数は書き込みデータ部が受け入れられる毎に１ずつ減算される。したがって、７個の書き込みデータ部Ｗ１，Ｗ２，．．．，Ｗ７が受け入れられたことによって、累積無効データ数は０となる。
【００６８】
累積無効データ数が０となった場合、ホスト２からの新たな書き込みデータは受け入れられないので、例えば、この時点で、書き込み動作が一時中断されてもよく、そして続きのガベージコレクション動作が開始されてもよい。
【００６９】
（４）続きのガベージコレクション動作において、第４ページの４つのデータ部Ｄ１３，Ｄ１４，Ｄ１５，及びＤ１６が無効データ、有効データ、有効データ、有効データである場合、無効データ部Ｄ１３が検出されたことに応じて累積無効データ数に１が加算される。そして、有効データ部Ｄ１４，Ｄ１５及びＤ１６がＧＣバッファ３２にコピーされる。上述したように、実際には、データ読み出しはページ単位で実行されるので、４つのデータ部Ｄ１３，Ｄ１４，Ｄ１５，及びＤ１６が同時に読み出され、これらデータ部内の有効データ部Ｄ１４、Ｄ１５、Ｄ１６のみがＧＣバッファ３２に蓄積されてもよい。
【００７０】
これにより、ＧＣバッファ３２には１ページサイズ以上の有効データ部Ｄ１０，Ｄ１４，Ｄ１５，及びＤ１６が蓄積され、累積無効データ数は１となる。
【００７１】
（５）ＧＣバッファ３２に蓄積された１ページ分の有効データ部Ｄ１０，Ｄ１４，Ｄ１５，及びＤ１６は、ガベージコレクションのコピー先ブロック５１２にコピーされる。この時点で、ガベージコレクション動作が一時中断されてもよく、そしてデータ書き込み動作が実行されてもよい。
【００７２】
（６）データ書き込み動作では、ライトバッファ３１内の１ページ分の書き込みデータ部Ｗ１，Ｗ２，Ｗ３，及びＷ４が、書き込み先ブロック５１１Ｃに書き込まれる。
【００７３】
（７）そして、累積無効データ数分の書き込みデータ部Ｗ８がホスト２から受付けられ、この書き込みデータ部Ｗ８がライトバッファ３１に一時的に書き込まれる。累積無効データ数は書き込みデータ部Ｗ８が受付られたことに応じて１だけ減算される。したがって、１個の書き込みデータ部Ｗ８が受付られたことによって、累積無効データ数は０となる。例えば、この時点で、書き込み動作が一時中断されてもよく、そして続きのガベージコレクション動作が開始されてもよい。
【００７４】
図５及び図６のフローチャートを参照して、ＳＳＤ３によって実行される書き込み処理の手順の例を説明する。
【００７５】
図５のフローチャートに示すように、まず、ＳＳＤ３のコントローラ４は、ホスト２の書き込み先ブロックにエラーが発生している状態、書き込み位置が書き込み先ブロックの終端である状態、及び書き込み先ブロックがまだ割り当てられていない状態のいずれかであるかどうかを判定する（ステップＳ１０１）。これら３つの状態のいずれかである場合（ステップＳ１０１のＹＥＳ）、コントローラ４は、ホスト２の書き込み先ブロックの割り当て処理を実行する（ステップＳ１０２）。
【００７６】
このステップＳ１０２のホスト書き込み先ブロック割り当て処理の手順について、図６を参照して例示する。まず、コントローラ４は、フリーブロック群５１に含まれるフリーブロックをホスト２の書き込み先ブロックとして割り当てる（ステップＳ２１）。そして、コントローラ４は、フリーブロック群５１に含まれる残りのフリーブロックの数が閾値以上であるか否かを判定する（ステップＳ２２）。この閾値は、例えば１以上の値である。フリーブロック群５１に含まれるフリーブロックの数が閾値以上である場合（ステップＳ２２のＹＥＳ）、コントローラ４は、累積無効データ数に、一つのブロックに相当するデータ数であるブロックサイズから、ライトバッファ３１に蓄積されたデータ数を減算した値（すなわち、ブロックサイズ−蓄積データ数）を設定する（ステップＳ２３）。そして、コントローラ４は、不足ブロック数に１を設定する（ステップＳ２４）。
【００７７】
一方、フリーブロック群５１に含まれる残りのフリーブロックの数が閾値未満である場合（ステップＳ２２のＮＯ）、コントローラ４は、累積無効データ数に、ライトバッファ３１に蓄積されたデータ数に相当する負の値（すなわち、−蓄積データ数）を設定する（ステップＳ２５）。そして、コントローラ４は、不足ブロック数を算出する（ステップＳ２６）。コントローラ４は、例えば、使用できない不良ブロック（バッドブロック）の数と、ホスト２による書き込みのために次に使用されるブロックの分とを考慮して、不足ブロック数として、不良ブロックの数に１を加えた値を算出する。例えば、一つの不良ブロックが新たに発生したならば不足ブロックの数は２に設定され、二つの不良ブロックが新たに同時発生したならば不足ブロックの数は３に設定される。
【００７８】
図５のフローチャートに示すように、ステップＳ１０２のホスト書き込み先ブロック割り当て処理の手順が完了した後、あるいはホスト２の書き込み先ブロックにエラーが発生している状態、書き込み位置が書き込み先ブロックの終端である状態、及び書き込み先ブロックがまだ割り当てられていない状態のいずれでもない場合（ステップＳ１０１のＮＯ）、コントローラ４は、ホスト２からの書き込みデータが閾値以上蓄積されているか否かを判定する（ステップＳ１０３）。この書き込みデータは、例えば、ライトバッファ３１に格納されているデータである。書き込みデータが閾値以上蓄積されている場合、つまり閾値以上の数の書き込みデータ部がライトバッファ３１に蓄積されている場合（ステップＳ１０３のＹＥＳ）、コントローラ４は、蓄積されているデータを、ホスト２の書き込み先ブロックに書き込む（ステップＳ１０４）。コントローラ４は、例えば、書き込み先ブロックに対して、ページ単位でデータを書き込む。そして、コントローラ４は、書き込みのエラーが発生したか否かを判定する（ステップＳ１０５）。書き込みのエラーが発生した場合（ステップＳ１０５のＹＥＳ）、コントローラ４は、ホスト２の書き込み先ブロックの割り当て処理を実行する（ステップＳ１０２）。このホスト書き込み先ブロック割り当て処理の手順は図６を参照して上述した通りである。
【００７９】
書き込みのエラーが発生していない場合（ステップＳ１０５のＮＯ）、コントローラ４は書き込まれたデータに応じてＬＵＴ３３を更新し（ステップＳ１０６）、ステップＳ１０７の手順に進む。コントローラ４は、ＬＵＴ３３を更新することによって、書き込まれたデータに対応するＬＢＡそれぞれとＮＡＮＤメモリ５上の物理アドレスそれぞれとをマッピングする。
【００８０】
また、書き込みデータが閾値以上蓄積されていない場合（ステップＳ１０３のＮＯ）、ライトバッファ３１に蓄積されているデータを書き込むための処理は行われず、ステップＳ１０７の手順に進む。
【００８１】
ステップＳ１０７の手順において、コントローラ４は、累積無効データ数が１以上であるか否かを判定する。累積無効データ数が１以上でない場合（ステップＳ１０７のＮＯ）、コントローラ４は書き込み処理から抜け、ガベージコレクション処理を実行する。このガベージコレクション処理の手順については、図７を参照して後述する。
【００８２】
累積無効データ数が１以上である場合（ステップＳ１０７のＹＥＳ）、コントローラ４は、累積無効データ数を不足ブロック数で除した値まで、ホスト２からのデータの受付を許可する（ステップＳ１０８）。なお、累積無効データ数を不足ブロック数で除した値の小数点以下の値は切り捨てとする。次いで、コントローラ４は、その受付許可の範囲内のデータ数（又はデータ量）が指定された、ホスト２からの書き込み要求（ライトコマンド）があるかどうかを判定する（ステップＳ１０９）。
【００８３】
受付許可の範囲内のデータ数（又はデータ量）が指定された書き込み要求がない場合（ステップＳ１０９のＮＯ）、コントローラ４は、書き込み処理から抜け、ガベージコレクション処理を実行する。したがって、例えば、ホスト２が書き込み要求を発行しないホストアイドル状態の場合であっても、ガベージコレクション処理が進行される。
【００８４】
受付許可の範囲内のデータ数（又はデータ量）が指定された、ホスト２からの書き込み要求がある場合（ステップＳ１０９のＹＥＳ）、コントローラ４は、そのホスト２からの書き込み要求に応答し、ホスト２から書き込みデータを受信する（ステップＳ１１０）。受信した書き込みデータは、ライトバッファ３１に一時的に書き込まれる。コントローラ４は、累積無効データ数から、受信した書き込みデータ数に不足ブロック数を乗じた値を減算する（ステップＳ１１１）。そして、コントローラ４は、ライトバッファ３１に一時的に書き込まれたデータに応じてＬＵＴ３３を更新し（ステップＳ１１２）、ステップＳ１０７の手順に進む。コントローラ４は、ＬＵＴ３３を更新することによって、ライトバッファ３１に一時的に書き込まれたデータに対応するＬＢＡそれぞれとライトバッファ３１（すなわち、ＤＲＡＭ６）上の物理アドレスそれぞれとをマッピングする。
【００８５】
次いで、図７を参照して、ＳＳＤ３によって実行されるガベージコレクション処理の手順の例を説明する。
【００８６】
まず、ＳＳＤ３のコントローラ４は、フリーブロック群５１に含まれるフリーブロックの数が閾値以上であるか否かを判定する（ステップＳ３０１）。この閾値は、例えば１以上の値である。フリーブロック群５１に含まれるフリーブロックの数が閾値以上である場合（ステップＳ３０１のＹＥＳ）、コントローラ４はガベージコレクション処理を終了し、上述した書き込み処理を実行する。フリーブロック群５１に含まれるフリーブロックの数が閾値以上である場合には、ガベージコレクション処理が実行されないことによって、ガベージコレクション処理が過剰に行われることを抑制することができる。
【００８７】
フリーブロック群５１に含まれるフリーブロックの数が閾値未満である場合（ステップＳ３０１のＮＯ）、コントローラ４は、未コピーの有効データが残っているガベージコレクションの対象ブロックがあるかどうかを判定する（ステップＳ３０２）。未コピーの有効データが残っているガベージコレクションの対象ブロックがない場合（ステップＳ３０２のＮＯ）、コントローラ４は、新たなガベージコレクションの対象ブロックを選定する（ステップＳ３０３）。未コピーの有効データが残っているガベージコレクションの対象ブロックがある場合（ステップＳ３０２のＹＥＳ）、ステップＳ３０３の手順がスキップされる。
【００８８】
次いで、コントローラ４は、ガベージコレクションの対象ブロックから未処理のデータを１個選択する（ステップＳ３０４）。データの選択は、管理サイズ（例えば４ＫＢ）と同じサイズを有する最小データ単位で実行される。コントローラ４は、選択された未処理のデータ部が有効データまたは無効データのいずれであるかを判定する（ステップＳ３０５）。選択された未処理のデータ部が有効データでない場合、すなわち、無効データである場合（ステップＳ３０５のＮＯ）、コントローラ４は、累積無効データ数に１を加算する（ステップＳ３０６）。
【００８９】
一方、選択された未処理のデータ部が有効データである場合（ステップＳ３０５のＹＥＳ）、コントローラ４は、そのデータ部をコピー用データとして蓄積する（ステップＳ３０７）。コントローラ４は、そのデータ部を、例えばコピーバッファ３２に一時的に書き込む。そして、コントローラ４は、蓄積されたコピー用データ部の数が１ページ分以上であるか否かを判定する（ステップＳ３０８）。蓄積されたコピー用データの数が１ページ分未満である場合（ステップＳ３０８のＮＯ）、ステップＳ３０２の手順に戻る。
【００９０】
蓄積されたコピー用データ部の数が１ページ分以上である場合（ステップＳ３０８のＹＥＳ）、コントローラ４は、ガベージコレクションのコピー先ブロックが割り当てられているかどうかを判定する（ステップＳ３０９）。ガベージコレクションのコピー先ブロックが割り当てられていない場合（ステップＳ３０９のＮＯ）、コントローラ４は、フリーブロック群５１の一つのフリーブロックを、ガベージコレクションのコピー先ブロックとして割り当てる（ステップＳ３１０）。ガベージコレクションのコピー先ブロックが既に割り当てられている場合（ステップＳ３０９のＹＥＳ）、ステップＳ３１０の手順がスキップされる。
【００９１】
コントローラ４は、ガベージコレクションのコピー先ブロックに、蓄積されたコピー用データの内、１ページ分のデータをコピーする（ステップＳ３１１）。そして、コントローラ４は、コピーされたデータに対応するＬＵＴ３３を更新する（ステップＳ３１２）。コントローラ４は、ＬＵＴ３３を更新することによって、コピーされたデータに対応するＬＢＡそれぞれとコピー先ブロック上の物理アドレスそれぞれとをマッピングする。
【００９２】
次いで、コントローラ４は、ガベージコレクションの対象ブロック内の、全ての有効データに対応するＬＵＴ３３の更新が終了したかどうかを判定する（ステップＳ３１３）。全ての有効データに対応するＬＵＴ３３の更新が終了していない場合（ステップＳ３１３のＮＯ）、コントローラ４は書き込み処理を開始する。全ての有効データに対応するＬＵＴ３３の更新が終了した場合（ステップＳ３１３のＹＥＳ）、コントローラ４は、コピーが終了したガベージコレクションの対象ブロックをフリーブロックにし（ステップＳ３１４）、書き込み処理を開始する。
【００９３】
以上のように、本実施形態においては、ガベージコレクションの対象ブロック内のデータ部が順に一つずつ選択され、選択されたデータ部が有効データであるならば、当該データ部がＧＣのコピー先ブロックにコピーされ、選択されたデータ部が無効データであるならば、累積無効データ数に１が加算される。そして、この累積無効データ数の範囲内でホスト２からの書き込みデータ部の受付が許可される。累積無効データ数は、受付た書き込みデータ部の数だけ減少される。したがって、ガベージコレクション動作中に発見される無効データの数をカウントするという簡単な制御のみで、ホスト書き込みとガベージコレクション動作とを同期して進行させることができ、これによってライトレイテンシーの変動を減少させることができる。
【００９４】
ライトレイテンシーはデータの書き込みに要する応答時間を示す。最近では、ブロックサイズの増大により、ガベージコレクションのためにコピーすることが必要なデータ量が増えている。本実施形態では、ホスト書き込みとガベージコレクション動作との間の比率を、ブロック単位やページ単位ではなく、データ単位で制御することができる。つまり、本実施形態では、アドレス変換テーブルとして機能するＬＵＴ３３を使用してＬＢＡそれぞれとＮＡＮＤメモリ５の物理アドレスそれぞれとの間のマッピングを管理サイズ単位で管理され、累積無効データ数は、この管理サイズ単位で、ガベージコレクション動作中に見つけられた無効データ部の数を示す。したがって、ライトレイテンシーを、ブロック単位やページ単位ではなく、管理サイズのような最小データ単位（つまり、最小粒度）で制御することが可能となり、安定したレイテンシーでホスト書き込みを行うことができる。
【００９５】
また、残りフリーブロック数および累積無効データ数以外の他のパラメータ（例えば、オーバープロビジョニングサイズ、等）は不要であるので、たとえオーバープロビジョニングサイズが動的に変更されても安定して動作することができる。
【００９６】
さらに、仮に、ブロックサイズがブロック毎に異なるようなケースであっても、ライトレイテンシーを、管理サイズのような最小データ単位（つまり、最小粒度）で安定して制御することができる。
【００９７】
図８は、ＳＳＤ３がマルチネームスペース機能を有する場合のデータ書き込み動作とガベージコレクション動作の例を示す。ネームスペース管理部２４は、ＳＳＤ３をあたかも複数のドライブであるかのように扱うことを可能にするために、複数のネームスペースそれぞれに対応する複数の論理アドレス空間（ＬＢＡ空間）を管理することができる。各ネームスペースには、ＬＢＡ範囲（ＬＢＡ０〜ＬＢＡｎ−１）が割り当てられる。ＬＢＡ範囲のサイズ（つまりＬＢＡの数）はネームスペース毎に可変であってもよい。各ＬＢＡ範囲は、ＬＢＡ０から始まる。各ネームスペースには、指定された数のブロックが確保される。確保されるブロックの数はネームスペース毎に異なっていてもよい。ネームスペース管理部２４は、ネームスペース毎に異なるＬＵＴを使用することによって、ＬＢＡそれぞれと物理アドレスそれぞれとの間のマッピングをネームスペース毎に個別に管理してもよい。例えば、ＮＳＩＤ＃１のネームスペース（第１領域）に関しては、コントローラ４は、ＮＳＩＤ＃１のネームスペース用のＬＵＴを使用して、ＮＳＩＤ＃１のネームスペースのＬＢＡそれぞれと第１領域の物理アドレスそれぞれとの間のマッピングを管理サイズ単位で管理する。ＮＳＩＤ＃ｎのネームスペース（第ｎ領域）に関しては、コントローラ４は、ＮＳＩＤ＃ｎのネームスペース用のＬＵＴを使用して、ＮＳＩＤ＃ｎのネームスペースのＬＢＡそれぞれと第ｎ領域の物理アドレスそれぞれとの間のマッピングを管理サイズ単位で管理する。
【００９８】
ＮＡＮＤメモリ５のフリーブロックは共通フリーブロックプール５１で管理され、いくつかのブロックが、共通フリーブロックプール（フリーブロック群）５１からＮＳＩＤ＃１のネームスペースに割り当てられる。これら割り当てられたブロックは、ＮＳＩＤ＃１のネームスペースに関連付けられたデータの格納のために使用される。つまり、それらいくつかのブロックが、ＮＳＩＤ＃１のネームスペースに関連付けられたデータを格納するためのブロックとしてＮＳＩＤ＃１のネームスペースに割り当てられる。ＮＳＩＤ＃ｎのネームスペースについても、同様にしてブロックが割り当てられる。これにより、ＮＡＮＤメモリ５は、ＮＳＩＤ＃１〜ＮＳＩＤ＃ｎのネームスペースそれぞれに対応する複数の領域に論理的に分割される。
【００９９】
ＳＳＤ３においては、ネームスペース毎に独立した仮想フラッシュプールが設けられている。仮想フラッシュプール６−１は、ＮＳＩＤ＃１のネームスペース用に確保（予約）された物理リソース量（確保されたブロックの総数）を管理するために使用される。同様に、仮想フラッシュプール６−ｎは、ＮＳＩＤ＃ｎのネームスペース用に確保（予約）された物理リソース量（確保されたブロックの総数）を管理するために使用される。この場合、どのブロックを確保（予約）すべきかを考慮する必要はなく、確保（予約）すべきブロックの個数のみが各仮想フラッシュプールで管理される。
【０１００】
フリーブロックそれぞれは複数のネームスペースによって共有される共通フリーブロックプール５１で管理される。各ネームスペースの仮想フラッシュプールから返却されたブロックは、共通フリーブロックプール５１で管理される。
【０１０１】
複数のネームスペースの各々では、図２を参照して上述したようなデータ書き込み動作とガベージコレクション動作とが行われる。
【０１０２】
まず、ＮＳＩＤ＃１のネームスペースにおけるガベージコレクション動作について説明する。
【０１０３】
ブロック選択部２１１は、アクティブブロックプール（アクティブブロック群）５５−１からガベージコレクションの対象ブロック（ＧＣ対象ブロック）５５１−１を選択する。データコピー制御部２１２は、ＧＣ対象ブロック５５１−１内のデータ部それぞれを順に選択し、選択されたデータ部が有効データであれば、その選択されたデータ部をＧＣコピー先ブロック５１２−１に書き込む。また、選択されたデータ部が無効データであれば、累積無効データ数計測部２１３は、ＮＳＩＤ＃１のネームスペースの累積無効データ数に１を加算する。
【０１０４】
ＧＣコピー先ブロック５１２−１は共通フリーブロックプール５１から割り当てられたブロックである。データコピー制御部２１２は、割り当てられているＧＣコピー先ブロック５１２−１の終端までデータが書き込まれた場合、そのＧＣコピー先ブロック５１２−１をアクティブブロックプール５５−１に移動する。
【０１０５】
また、データコピー制御部２１２は、ＧＣ対象ブロック５５１−１内の全ての有効データが、ＧＣコピー先ブロック５１２−１に書き込まれた場合、このＧＣ対象ブロック５５１−１を共通フリーブロックプール５１に移動する。
【０１０６】
次いで、ホスト２からのＮＳＩＤ＃１のネームスペースへの書き込み要求に応じた書き込み動作について説明する。
【０１０７】
ＮＳＩＤ＃１を含む書き込み要求（ライトコマンド）は、ＮＳＩＤ＃１のネームスペース用のライト制御部２２に送られる。ライト制御部２２は、ＮＳＩＤ＃１のネームスペースの累積無効データ数の範囲内で、ＮＳＩＤ＃１のネームスペースに関連付けられた書き込みデータ部の受付を許可する。つまり、ライト制御部２２は、ＮＳＩＤ＃１のネームスペースに関連付けられた書き込みデータ部を、累積無効データ数を上限とする数だけホスト２から受付けることができる。ライト制御部２２は、受付た書き込みデータそれぞれをライトバッファ３１−１に一時的に書き込む。また、累積無効データ数計測部２１３は、ホスト２から受付た書き込みデータ部の数を、ＮＳＩＤ＃１のネームスペースの累積無効データ数から減算する。ライト制御部２２は、ライトバッファ３１−１に書き込まれたデータを、例えばページ単位で、ＮＳＩＤ＃１のネームスペースにおけるホスト２の書き込み先ブロック５１１−１に書き込む。
【０１０８】
なお、ライト制御部２２は、ＮＳＩＤ＃１のネームスペースにおけるホスト２の書き込み先ブロック５１１−１がまだ割り当てられていない場合、割り当てられている書き込み先ブロック５１１−１の終端までデータが書き込まれた場合、又は書き込み先ブロック５１１−１にエラーが発生した場合には、フリーブロックプール５１内の一つのフリーブロックを、新たな書き込み先ブロック５１１−１として割り当てる。また、ライト制御部２２は、割り当てられている書き込み先ブロック５１１−１の終端までデータが書き込まれた場合、その書き込み先ブロック５１１−１をアクティブブロックプール５５−１に移動する。
【０１０９】
累積無効データ数計測部２１３は、ホスト２の書き込み先ブロック５１１−１が新たに割り当てられた時、ＮＳＩＤ＃１のネームスペース用に割り当て可能な残りブロック数が閾値以上であるか否かを判定する。この残りブロック数は、ＮＳＩＤ＃１のネームスペース用に確保（予約された）された総ブロック数から、ＮＳＩＤ＃１のネームスペースにおいて使用されているブロックの数を示す使用ブロック数を減算することによって得られる。この残りブロック数が閾値以上である場合、累積無効データ数計測部２１３は、ＮＳＩＤ＃１のネームスペースの累積無効データ数に、新たに割り当てられた書き込み先ブロック５１１−１に書き込み可能なデータ部の数を加算する。書き込み先ブロック５１１−１に書き込み可能なデータ部の数は、このブロックの容量に相当するデータ部の数である。さらに、累積無効データ数計測部２１３は、ライトバッファ３１−１に現在蓄積されているデータ部がある場合には、ＮＳＩＤ＃１のネームスペースの累積無効データ数からそのデータ部の数を減算するようにしてもよい。また、ＮＳＩＤ＃１のネームスペース用に割り当て可能な残りブロック数が閾値未満である場合、累積無効データ数計測部２１３は、ＮＳＩＤ＃１のネームスペースの累積無効データ数に０を設定する。さらに、累積無効データ数計測部２１３は、ライトバッファ３１−１に現在蓄積されているデータ部がある場合には、ＮＳＩＤ＃１のネームスペースの累積無効データ数からそのデータ部の数を減算するようにしてもよい。
【０１１０】
同様にして、ＮＳＩＤ＃ｎのネームスペースにおけるガベージコレクション動作と、ホスト２からのＮＳＩＤ＃ｎのネームスペースへの書き込み要求に応じた書き込み動作とが行われる。
【０１１１】
図９及び図１０のフローチャートを参照して、複数のネームスペースのための複数の領域が設定されたＳＳＤ３によって実行される書き込み処理の手順の例を説明する。以下では、説明を分かりやすくするために、複数のネームスペースの内の、ある一つのネームスペースへの書き込み処理について説明するが、コントローラ４は、複数のネームスペースの各々について同様の書き込み処理を並行して実行することができる。
【０１１２】
図９のフローチャートに示すように、まず、ＳＳＤ３のコントローラ４は、ホスト２からあるネームスペースへの書き込み先ブロックにエラーが発生している状態、書き込み位置が書き込み先ブロックの終端である状態、及び書き込み先ブロックがまだ割り当てられていない状態のいずれかであるかどうかを判定する（ステップＳ４０１）。これら３つの状態のいずれかである場合（ステップＳ４０１のＹＥＳ）、コントローラ４は、ホスト２からそのネームスペースへの書き込み先ブロックの割り当て処理を実行する（ステップＳ４０２）。
【０１１３】
このステップＳ４０２のホスト書き込み先ブロック割り当て処理の手順について、図１０を参照して例示する。まず、コントローラ４は、フリーブロック群５１に含まれるフリーブロックを、ホスト２のネームスペースへの書き込み先ブロックとして割り当てる（ステップＳ５１）。そして、コントローラ４は、そのネームスペース用に確保された総ブロック数から、当該ネームスペースにおいて使用されているブロックの数を示す使用ブロック数を減算することによって得られる残りブロックの数が閾値以上であるか否かを判定する（ステップＳ５２）。この閾値は、例えば１以上の値である。残りブロック数が閾値以上である場合（ステップＳ５２のＹＥＳ）、コントローラ４は、ネームスペースの累積無効データ数に、一つのブロックに相当するデータ数であるブロックサイズから、ライトバッファ３１に蓄積されたデータ数を減算した値（すなわち、ブロックサイズ−蓄積データ数）を設定する（ステップＳ５３）。そして、コントローラ４は、ネームスペースの不足ブロック数に１を設定する（ステップＳ５４）。
【０１１４】
一方、フリーブロック群５１に含まれる残りのフリーブロックの数が閾値未満である場合（ステップＳ５２のＮＯ）、コントローラ４は、ネームスペースの累積無効データ数に、ライトバッファ３１に蓄積されたデータ数に相当する負の値（すなわち、−蓄積データ数）を設定する（ステップＳ５５）。そして、コントローラ４は、ネームスペースの不足ブロック数を算出する（ステップＳ５６）。コントローラ４は、例えば、使用できない不良ブロック（バッドブロック）の数と、ホスト２による書き込みのために次に使用されるブロックの分とを考慮して、不足ブロック数として、不良ブロックの数に１を加えた値を算出する。例えば、一つの不良ブロックが新たに発生したならば不足ブロックの数は２に設定され、二つの不良ブロックが新たに同時発生したならば不足ブロックの数は３に設定される。
【０１１５】
図９のフローチャートに示すように、ステップＳ４０２のホスト書き込み先ブロック割り当て処理の手順が完了した後、あるいはあるネームスペースにおけるホスト２の書き込み先ブロックにエラーが発生している状態、書き込み位置が書き込み先ブロックの終端である状態、及び書き込み先ブロックがまだ割り当てられていない状態のいずれでもない場合（ステップＳ４０１のＮＯ）、コントローラ４は、ホスト２からそのネームスペースへの書き込みデータが閾値以上蓄積されているか否かを判定する（ステップＳ４０３）。この書き込みデータは、例えば、ライトバッファ３１に格納されているデータである。書き込みデータが閾値以上蓄積されている場合、つまり閾値以上の数の書き込みデータ部がライトバッファ３１に蓄積されている場合（ステップＳ４０３のＹＥＳ）、コントローラ４は、蓄積されているデータを、そのネームスペースにおけるホスト２の書き込み先ブロックに書き込む（ステップＳ４０４）。コントローラ４は、例えば、書き込み先ブロックに対して、ページ単位でデータを書き込む。そして、コントローラ４は、書き込みのエラーが発生したか否かを判定する（ステップＳ４０５）。書き込みのエラーが発生した場合（ステップＳ４０５のＹＥＳ）、コントローラ４は、ホスト２の書き込み先ブロックの割り当て処理を実行する（ステップＳ４０２）。このホスト書き込み先ブロック割り当て処理の手順は図１０を参照して上述した通りである。
【０１１６】
書き込みのエラーが発生していない場合（ステップＳ４０５のＮＯ）、コントローラ４は書き込まれたデータに応じて、ネームスペースのＬＵＴ３３を更新し（ステップＳ４０６）、ステップＳ４０７の手順に進む。コントローラ４は、ネームスペースのＬＵＴ３３を更新することによって、そのネームスペースの領域に書き込まれたデータに対応するＬＢＡそれぞれとＮＡＮＤメモリ５上の物理アドレスそれぞれとをマッピングする。
【０１１７】
また、書き込みデータが閾値以上蓄積されていない場合（ステップＳ４０３のＮＯ）、ライトバッファ３１に蓄積されているデータを書き込むための処理は行われず、ステップＳ４０７の手順に進む。
【０１１８】
ステップＳ４０７の手順において、コントローラ４は、ネームスペースの累積無効データ数が１以上であるか否かを判定する。ネームスペースの累積無効データ数が１以上でない場合（ステップＳ４０７のＮＯ）、コントローラ４は書き込み処理から抜け、ガベージコレクション処理を実行する。このガベージコレクション処理の手順については、図１１を参照して後述する。
【０１１９】
ネームスペースの累積無効データ数が１以上である場合（ステップＳ４０７のＹＥＳ）、コントローラ４は、ネームスペースの累積無効データ数を不足ブロック数で除した値まで、ホスト２からのデータの受付を許可する（ステップＳ４０８）。なお、累積無効データ数を不足ブロック数で除した値の小数点以下の値は切り捨てとする。次いで、コントローラ４は、そのネームスペースに対する、受付許可の範囲内のデータ数（又はデータ量）が指定された、ホスト２からの書き込み要求（ライトコマンド）があるかどうかを判定する（ステップＳ４０９）。
【０１２０】
そのネームスペースに対する、受付許可の範囲内のデータ数（又はデータ量）が指定された書き込み要求がない場合（ステップＳ４０９のＮＯ）、コントローラ４は、書き込み処理から抜け、ガベージコレクション処理を実行する。したがって、例えば、ホスト２が書き込み要求を発行しないホストアイドル状態の場合であっても、ガベージコレクション処理が進行される。
【０１２１】
そのネームスペースに対する、受付許可の範囲内のデータ数（又はデータ量）が指定された、ホスト２からの書き込み要求がある場合（ステップＳ４０９のＹＥＳ）、コントローラ４は、そのホスト２からの書き込み要求に応答し、ホスト２から当該ネームスペースに対する書き込みデータを受信する（ステップＳ４１０）。受信した書き込みデータは、ネームスペース毎のライトバッファ３１に一時的に書き込まれる。コントローラ４は、ネームスペースの累積無効データ数から、受信した書き込みデータ数に不足ブロック数を乗じた値を減算する（ステップＳ４１１）。そして、コントローラ４は、ライトバッファ３１に一時的に書き込まれたデータに応じて、ネームスペースのＬＵＴ３３を更新し（ステップＳ４１２）、ステップＳ４０７の手順に進む。コントローラ４は、ネームスペースのＬＵＴ３３を更新することによって、ライトバッファ３１に一時的に書き込まれたデータに対応するＬＢＡそれぞれとライトバッファ３１（すなわち、ＤＲＡＭ６）上の物理アドレスそれぞれとをマッピングする。
【０１２２】
次いで、図１１を参照して、ＳＳＤ３によって実行されるガベージコレクション処理の手順の例を説明する。
【０１２３】
まず、ＳＳＤ３のコントローラ４は、ネームスペース用に確保された総ブロック数から、当該ネームスペースにおいて使用されているブロックの数を示す使用ブロック数を減算することによって得られる残りブロックの数が閾値以上であるか否かを判定する（ステップＳ６０１）。この閾値は、例えば１以上の値である。残りブロック数が閾値以上である場合（ステップＳ６０１のＹＥＳ）、コントローラ４はガベージコレクション処理を終了し、上述した書き込み処理を実行する。残りブロック数が閾値以上である場合には、ガベージコレクション処理が実行されないことによって、ガベージコレクション処理が過剰に行われることを抑制することができる。
【０１２４】
残りブロック数が閾値未満である場合（ステップＳ６０１のＮＯ）、コントローラ４は、未コピーの有効データが残っている、そのネームスペースのガベージコレクションの対象ブロックがあるかどうかを判定する（ステップＳ６０２）。未コピーの有効データが残っている、そのネームスペースのガベージコレクションの対象ブロックがない場合（ステップＳ６０２のＮＯ）、コントローラ４は、当該ネームスペースにおける、新たなガベージコレクションの対象ブロックを選定する（ステップＳ６０３）。未コピーの有効データが残っている、そのネームスペースのガベージコレクションの対象ブロックがある場合（ステップＳ６０２のＹＥＳ）、ステップＳ６０３の手順がスキップされる。
【０１２５】
次いで、コントローラ４は、ガベージコレクションの対象ブロックから未処理のデータを１個選択する（ステップＳ６０４）。データの選択は、管理サイズ（例えば４ＫＢ）と同じサイズを有する最小データ単位で実行される。コントローラ４は、選択された未処理のデータ部が有効データまたは無効データのいずれであるかを判定する（ステップＳ６０５）。選択された未処理のデータ部が有効データでない場合、すなわち、無効データである場合（ステップＳ６０５のＮＯ）、コントローラ４は、そのネームスペースの累積無効データ数に１を加算する（ステップＳ６０６）。
【０１２６】
一方、選択された未処理のデータ部が有効データである場合（ステップＳ６０５のＹＥＳ）、コントローラ４は、そのデータ部をコピー用データとして蓄積する（ステップＳ６０７）。コントローラ４は、そのデータ部を、例えばコピーバッファ３２に一時的に書き込む。そして、コントローラ４は、そのネームスペースについて、蓄積されたコピー用データ部の数が１ページ分以上であるか否かを判定する（ステップＳ６０８）。蓄積されたコピー用データの数が１ページ分未満である場合（ステップＳ６０８のＮＯ）、ステップＳ６０２の手順に戻る。
【０１２７】
蓄積されたコピー用データ部の数が１ページ分以上である場合（ステップＳ６０８のＹＥＳ）、コントローラ４は、そのネームスペースにおけるガベージコレクションのコピー先ブロックが割り当てられているかどうかを判定する（ステップＳ６０９）。ガベージコレクションのコピー先ブロックが割り当てられていない場合（ステップＳ６０９のＮＯ）、コントローラ４は、フリーブロック群５１の一つのフリーブロックを、当該ネームスペースにおけるガベージコレクションのコピー先ブロックとして割り当てる（ステップＳ６１０）。ガベージコレクションのコピー先ブロックが既に割り当てられている場合（ステップＳ６０９のＹＥＳ）、ステップＳ６１０の手順がスキップされる。
【０１２８】
コントローラ４は、そのネームスペースのガベージコレクションのコピー先ブロックに、蓄積されたコピー用データの内、１ページ分のデータをコピーする（ステップＳ６１１）。そして、コントローラ４は、ネームスペースの、コピーされたデータに対応するＬＵＴ３３を更新する（ステップＳ６１２）。コントローラ４は、ネームスペースのＬＵＴ３３を更新することによって、当該ネームスペースにおいて、コピーされたデータに対応するＬＢＡそれぞれとコピー先ブロック上の物理アドレスそれぞれとをマッピングする。
【０１２９】
次いで、コントローラ４は、ガベージコレクションの対象ブロック内の、全ての有効データに対応するＬＵＴ３３の更新が終了したかどうかを判定する（ステップＳ６１３）。全ての有効データに対応するＬＵＴ３３の更新が終了していない場合（ステップＳ６１３のＮＯ）、コントローラ４は書き込み処理を開始する。全ての有効データに対応するＬＵＴ３３の更新が終了した場合（ステップＳ６１３のＹＥＳ）、コントローラ４は、コピーが終了したガベージコレクションの対象ブロックをフリーブロックにし（ステップＳ６１４）、書き込み処理を開始する。
【０１３０】
以上のように、ＳＳＤ３に複数のネームスペースのための複数の領域が設定される場合にも、各ネームスペースにおいて、ガベージコレクション動作中に発見される無効データの数をカウントするという簡単な制御のみで、ホスト書き込みとガベージコレクション動作とを同期して進行させることができ、これによってライトレイテンシーの変動を減少させることができる。
【０１３１】
また、図１２は、ＳＳＤ３がマルチネームスペース機能を有する場合のデータ書き込み動作とガベージコレクション動作の別の例を示す。複数のネームスペースの各々では、図８を参照して上述したようなガベージコレクション動作が行われる。それにより、ネームスペース毎の累積無効データ数が算出される。
【０１３２】
図１２に示す例では、ライト制御部２２は、複数のネームスペースの累積無効データ数の合計を算出し、算出された合計の範囲内でホスト２からの書き込みデータ部の受付を許可する。つまり、ライト制御部２２は、書き込みデータ部を、複数のネームスペースの累積無効データ数の合計を上限とする数だけホスト２から受付けることができる。ライト制御部２２は、ホスト２から、受付た書き込みデータそれぞれをライトバッファ３１に一時的に書き込む。また、累積無効データ数計測部２１３は、ホスト２から受付たデータ部の数を、累積無効データ数の合計から減算してもよい。ライト制御部２２は、ライトバッファ３１に書き込まれたデータを、例えばページ単位で、その書き込み要求で指定されたネームスペースにおけるホスト２の書き込み先ブロック５１１−１、５１１−ｎに書き込む。
【０１３３】
なお、ライト制御部２２は、メモリシステムで不足しているフリーブロックの数が２つ以上である場合、複数の累積無効データ数の合計を、その不足しているフリーブロックの数で除した値の範囲内でホスト２からの書き込みデータ部の受付を許可するようにしても良い。
【０１３４】
図１３は、ホスト２として機能する情報処理装置のハードウェア構成例を示す。
【０１３５】
この情報処理装置は、サーバコンピュータ、またはパーソナルコンピュータとして実現される。この情報処理装置は、プロセッサ（ＣＰＵ）１０１、メインメモリ１０２、ＢＩＯＳ−ＲＯＭ１０３、ネットワークコントローラ１０５、周辺インタフェースコントローラ１０６、コントローラ１０７、及びエンベデッドコントローラ（ＥＣ）１０８等を含む。
【０１３６】
プロセッサ１０１は、この情報処理装置の各コンポーネントの動作を制御するように構成されたＣＰＵである。このプロセッサ１０１は、複数のＳＳＤ３のいずれか一つからメインメモリ１０２にロードされる様々なプログラムを実行する。メインメモリ１０２は、ＤＲＡＭのようなランダムアクセスメモリから構成される。プロセッサ１０１によって実行されるプログラムは、上述のアプリケーションソフトウェアレイヤ４１、ＯＳ４２及びファイルシステム４３を含む。
【０１３７】
また、プロセッサ１０１は、不揮発性メモリであるＢＩＯＳ−ＲＯＭ１０３に格納された基本入出力システム（ＢＩＯＳ）も実行する。ＢＩＯＳはハードウェア制御のためのシステムプログラムである。
【０１３８】
ネットワークコントローラ１０５は、有線ＬＡＮコントローラ、無線ＬＡＮコントローラのような通信デバイスである。周辺インタフェースコントローラ１０６は、ＵＳＢデバイスのような周辺デバイスとの通信を実行するように構成されている。
【０１３９】
コントローラ１０７は、複数のコネクタ１０７Ａにそれぞれ接続されるデバイスとの通信を実行するように構成されている。本実施形態では、複数のＳＳＤ３が複数のコネクタ１０７Ａにそれぞれ接続される。コントローラ１０７は、ＳＡＳ  ｅｘｐａｎｄｅｒ、ＰＣＩｅ  Ｓｗｉｔｃｈ、ＰＣＩｅ  ｅｘｐａｎｄｅｒ、フラッシュアレイコントローラ、またはＲＡＩＤコントローラ等である。
【０１４０】
ＥＣ１０８は、情報処理装置の電力管理を実行するように構成されたシステムコントローラとして機能する。ＥＣ１０８は、ユーザによる電源スイッチの操作に応じて情報処理装置をパワーオン及びパワーオフする。ＥＣ１０８はワンチップマイクロコントローラのような処理回路として実現されている。ＥＣ１０８は、キーボード（ＫＢ）などの入力デバイスを制御するキーボードコントローラを内蔵していてもよい。
【０１４１】
図１４は、複数のＳＳＤ３とホスト２とを含む情報処理装置の構成例を示す。
【０１４２】
この情報処理装置は、ラックに収容可能な薄い箱形の筐体２０１を備える。多数のＳＳＤ３は筐体２０１内に配置されても良い。この場合、各ＳＳＤ３は筐体２０１の前面２０１Ａに設けられたスロットに取り外し可能に挿入されてもよい。
【０１４３】
システムボード（マザーボード）２０２は筐体２０１内に配置される。システムボード（マザーボード）２０２上においては、ＣＰＵ１０１、メモリ１０２、ネットワークコントローラ１０５、コントローラ１０７を含む様々な電子部品が実装されている。これら電子部品がホスト２として機能する。
【０１４４】
以上のように、本実施形態においては、ライトレイテンシーの変動を低減することができる。本実施形態のメモリシステムは、ＮＡＮＤメモリ（不揮発性メモリ）５と、ＮＡＮＤメモリ５に電気的に接続されたコントローラ４とを備える。コントローラ４は、ＮＡＮＤメモリ５からガベージコレクションの対象ブロックとして選択されたＧＣ対象ブロック５５１内のデータ部を順に選択し、その選択されたデータ部が有効データであるならば、当該データ部を、ＮＡＮＤメモリ５内のフリーブロック群５１からガベージコレクションのためのコピー先ブロックとして割り当てられたＧＣコピー先ブロック５１２にコピーし、その選択されたデータ部が無効データであるならば、ガベージコレクション動作中に見つけられた無効データ部の数を示す累積無効データ数に１を加算するガベージコレクション動作を実行する。そして、コントローラ４は、累積無効データ数の範囲内でホスト２からの書き込みデータ部の受付を許可し、且つ受付た書き込みデータ部の数だけ累積無効データ数を減少させる。
【０１４５】
したがって、ガベージコレクション動作中に発見される無効データの数をカウントするという簡単な制御のみで、ホスト書き込みとガベージコレクション動作とを同期して進行させることができ、これによってライトレイテンシーの変動を減少させることができる。
【０１４６】
なお、本実施形態では、不揮発性メモリとしてＮＡＮＤメモリを例示した。しかし、本実施形態の機能は、例えば、ＭＲＡＭ（Ｍａｇｎｅｔｏｒｅｓｉｓｔｉｖｅ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＰＲＡＭ（Ｐｈａｓｅ  ｃｈａｎｇｅ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＲｅＲＡＭ（Ｒｅｓｉｓｔｉｖｅ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、又は、ＦｅＲＡＭ（Ｆｅｒｒｏｅｌｅｃｔｒｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）のような他の様々な不揮発性メモリにも適用できる。
【０１４７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１４８】
１…情報処理システム、２…ホスト計算機、３…ＳＳＤ、４…コントローラ、５…ＮＡＮＤメモリ、６…ＤＲＡＭ、１１…ホストインターフェース（Ｉ／Ｆ）、１２…ＣＰＵ、１３…ＮＡＮＤインターフェース（Ｉ／Ｆ）、１４…ＤＲＡＭインターフェース（Ｉ／Ｆ）、２１…ガベージコレクション制御部、２１１…ブロック選択部、２１２…データコピー制御部、２１３…累積無効データ数計測部、２２…ライト制御部、２３…リード制御部、２４…ネームスペース管理部、３１…ライトバッファ、３２…ＧＣバッファ、３３…ルックアップテーブル（ＬＵＴ）、３４…無効データ数、５１…フリーブロック群、５５…アクティブブロック群。
【図１】
2018049522.tif 000003
【図２】
2018049522.tif 000004
【図３】
2018049522.tif 000005
【図４】
2018049522.tif 000006
【図５】
2018049522.tif 000007
【図６】
2018049522.tif 000008
【図７】
2018049522.tif 000009
【図８】
2018049522.tif 000010
【図９】
2018049522.tif 000011
【図１０】
2018049522.tif 000012
【図１１】
2018049522.tif 000013
【図１２】
2018049522.tif 000014
【図１３】
2018049522.tif 000015
【図１４】
2018049522.tif 000016