(57)【特許請求の範囲】
【請求項１】
外部のホストに接続可能なメモリシステムであって、
前記ホストから受信したデータが格納される第１記憶領域を備える不揮発性の第１記憶装置と、
当該第１記憶装置に対し、データの書き込みおよびデータの読み出しの制御を行うコントローラと、
を備え、
前記第１記憶領域は、前記メモリシステムの論理アドレス空間のサイズである第１サイズより大きい第２サイズを有し、
前記コントローラは、前記第１サイズを変更する要求を前記ホストから受信し、前記要求に応じて、前記論理アドレス空間のうちの少なくとも一部のデータを有効な状態に保ちながら前記第１サイズを変更し、
前記論理アドレス空間内の論理アドレスと前記第１記憶領域内の物理アドレスとを対応付ける１以上のレコード、を備える第１対応情報が格納される第２記憶領域を備える第２記憶装置をさらに備え、
前記コントローラは、前記要求に応じて前記第１対応情報が備えるレコードの数を変更し、
前記第１対応情報は、１以上の第２レコードを備える第２対応情報と、物理アドレスが記録される１以上の第３対応情報とを含み、前記第２レコードは論理アドレスと前記１以上の第３対応情報のうちの対応する一つをポイントするポインタとを対応付ける情報であり、
前記コントローラは、前記要求に応じて前記第２対応情報が備える第２レコードの数を変更する、
ことを特徴とするメモリシステム。
【請求項２】
前記第２対応情報は、前記論理アドレス空間に含まれる第１単位領域毎に前記第２レコードを含み、
前記第３対応情報は、夫々前記第１単位領域よりも小さい第２単位領域毎の物理アドレスである複数の物理アドレスが記録される、
ことを特徴とする請求項１に記載のメモリシステム。
【請求項３】
前記コントローラは、前記第１サイズを増加する要求である第１要求に応じて前記第２対応情報に、前記第１サイズの増加に応じて追加される第１論理アドレス空間に対応する第２レコードである第３レコードを追加し、
前記第１サイズを削減する要求である第２要求に応じて前記第２対応情報から、前記第１サイズの削減に応じて削減される第２論理アドレス空間に対応する第２レコードである第４レコードを削除する、
ことを特徴とする請求項２に記載のメモリシステム。
【請求項４】
前記コントローラは、
前記論理アドレス空間内の前記第２単位領域の状態が、論理アドレスが何れかの物理アドレスに対応付けられている状態である第１状態であるか、論理アドレスが何れの物理アドレスにも対応付けられていない状態である第２状態であるか、を参照し、
前記第２要求を受信した場合、状態が前記第１状態である第２単位領域である第３単位領域が前記第２論理アドレス空間に存在するか否かを判定し、前記第２論理アドレス空間に前記第３単位領域が存在する場合、前記ホストに警告する、
ことを特徴とする請求項３に記載のメモリシステム。
【請求項５】
前記コントローラは、前記ホストに警告した後に許可を受信した場合、前記第４レコードを削除する、ことを特徴とする請求項４に記載のメモリシステム。
【請求項６】
前記コントローラは、前記ホストに警告した後に前記許可を受信しない場合、前記第４レコードを削除しない、ことを特徴とする請求項５に記載のメモリシステム。
【請求項７】
前記コントローラは、
前記論理アドレス空間内の前記第２単位領域の状態が、論理アドレスが何れかの物理アドレスに対応付けられている状態である第１状態であるか、論理アドレスが何れの物理アドレスにも対応付けられていない状態である第２状態であるか、を参照し、
前記第２要求を受信した場合、状態が前記第１状態である第２単位領域である第３単位領域が前記第２論理アドレス空間に存在するか否かを判定し、前記第２論理アドレス空間に前記第３単位領域が存在する場合、前記第４レコードを削除しない、
ことを特徴とする請求項３に記載のメモリシステム。
【請求項８】
前記コントローラは、
前記論理アドレス空間内の前記第２単位領域の状態が、論理アドレスが何れかの物理アドレスに対応付けられている状態である第１状態であるか、論理アドレスが何れの物理アドレスにも対応付けられていない状態である第２状態であるか、を参照し、
前記第２要求を受信した場合、状態が前記第１状態である第２単位領域である第３単位領域が前記第２論理アドレス空間に存在するか否かを判定し、
前記第２論理アドレス空間に前記第３単位領域が存在する場合、前記第３単位領域に関する第３対応情報に状態が前記第２状態であることを示す情報を記述し、前記第４レコードを削除し、
前記第２論理アドレス空間に前記第３単位領域が存在しない場合、前記第３単位領域に関する第３対応情報を更新しないで前記第４レコードを削除する、
ことを特徴とする請求項３に記載のメモリシステム。
【請求項９】
前記コントローラは、
第１単位領域毎に第２フラグを更新し、
前記第２要求を受信した場合、前記第２論理アドレス空間に前記第３単位領域が存在するか否かの判定を実行する前に、前記第２論理アドレス空間に含まれる第１単位領域の第２フラグを立て、前記第２フラグを立てた後、前記受信した第２要求に対する完了応答を前記ホストに通知し、
前記完了応答の通知後、前記判定を、前記第２フラグが立てられた第１単位領域に対して開始する、
ことを特徴とする請求項５に記載のメモリシステム。
【請求項１０】
前記第１記憶領域は、複数のブロックを備え、
前記コントローラは、
前記ホストからのデータを順次、前記複数のブロックのうちの空き領域を有するブロックである第１ブロックの前記空き領域に書き込み、
夫々同一の第１論理アドレスの指定を伴う２つのデータが前記第１記憶領域に記憶され、かつ、前記２つのデータは夫々異なる物理アドレスが示す位置に記憶される場合、前記２つのデータのうちの前記第１対応情報によって前記第１論理アドレスに対応付けられている物理アドレスが示す位置に記憶されるデータを有効なデータとして扱い、前記２つのデータのうちの前記第１対応情報によって前記第１論理アドレスに対応付けられていない物理アドレスが示す位置に記憶されるデータを無効なデータとして扱い、
前記複数のブロックから第２ブロックを選択し、前記第２ブロックに記憶されるデータのうちの有効なデータを前記複数のブロックのうちの空き領域を有するブロックである第３ブロックの前記空き領域にコピーし、前記第２ブロックをフリーブロックとして設定する、ガベージコレクションを実行し、
前記ガベージコレクションの後、前記フリーブロックに記憶される全データを消去し、
前記フリーブロックの数と前記第１サイズと前記第２サイズとに応じて、前記ホストからのデータの前記第１ブロックへの書き込み量に対する前記ガベージコレクションによるデータの前記第３ブロックへの書き込み量の比率を制御する、
ことを特徴とする請求項３に記載のメモリシステム。
【請求項１１】
前記コントローラは、
前記フリーブロックの数が第１値である場合には、前記フリーブロックの数が前記第１値よりも大きい第２値である場合に比べ、前記比率を増加させる、
ことを特徴とする請求項１０に記載のメモリシステム。
【請求項１２】
前記コントローラは、前記第１サイズが第３値である場合には、前記第１サイズが前記第３値よりも小さい第４値である場合に比べ、前記比率を増加させる、
ことを特徴とする請求項１１に記載のメモリシステム。
【請求項１３】
前記コントローラは、
前記第２サイズから前記第１サイズを減算して得られる値の前記第１サイズに対するパーセンテージが第３値である場合には、前記パーセンテージが前記第３値よりも大きい第４値である場合に比べ、前記比率を増加させる、
ことを特徴とする請求項１１に記載のメモリシステム。
【請求項１４】
前記コントローラは、ブロック毎に有効なデータのカウント値を管理し、前記複数のブロックのうちから前記有効なデータの数が最小のブロックを前記第２ブロックとして選択する、
ことを特徴とする請求項１０から請求項１３の何れか１項に記載のメモリシステム。
【請求項１５】
前記コントローラは、
前記論理アドレス空間内の前記第２単位領域の状態が、論理アドレスが何れかの物理アドレスに対応付けられている状態である第１状態であるか、論理アドレスが何れの物理アドレスにも対応付けられていない状態である第２状態であるか、を参照し、
前記第２要求を受信した場合、状態が前記第１状態である第２単位領域である第３単位領域が前記第２論理アドレス空間に存在するか否かを判定し、
前記第２論理アドレス空間に第３単位領域が存在する場合、前記第１対応情報を参照することによって前記第３単位領域を示す論理アドレス、に対応する物理アドレスを取得し、前記複数のブロックのうちの前記取得された物理アドレスを含むブロックについて前記カウント値をデクリメントし、前記第４レコードを削除する、
ことを特徴とする請求項１４に記載のメモリシステム。
【請求項１６】
前記第１対応情報は、前記レコードを前記論理アドレス空間に含まれる単位領域毎に備え、
前記コントローラは、前記第１サイズを増加する要求である第１要求に応じて前記第１対応情報が備えるレコードの数を増やし、前記第１サイズを削減する要求である第２要求に応じて前記第１対応情報が備えるレコードの数を削減する、
ことを特徴とする請求項１または請求項２に記載のメモリシステム。
【請求項１７】
前記第２対応情報は、第２レコード毎に第１フラグを備え、
前記コントローラは、
前記第３レコードを前記第２対応情報に追加し、
前記追加した第３レコードの第１フラグを立て、
前記第１論理アドレス空間に対するアクセスを行う場合、前記アクセスの宛先の物理アドレスを記録した新規の第３対応情報を生成し、前記第３レコードに前記新規の第３対応情報をポイントするポインタを記録し、前記第３レコードの第１フラグを下ろす、
ことを特徴とする請求項３に記載のメモリシステム。
【請求項１８】
前記コントローラは、前記ホストに警告した後、前記第４レコードを削除する、
ことを特徴とする請求項６に記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、メモリシステムに関する。
【背景技術】
【０００２】
従来、ホストは、メモリシステムの表記容量のサイズを上限として、当該メモリシステムにユーザデータを書き込むことができる。メモリシステムの実装容量は、表記容量よりも大きい。メモリシステムは、実装容量のサイズの記憶領域のうちから表記容量のサイズの記憶領域を確保する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１２−１７４０８６号公報
【特許文献２】特開２０１２−１２８５４５号公報
【特許文献３】特開２０１３−２００７４１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
一つの実施形態は、利便性の高いメモリシステムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
一つの実施形態によれば、メモリシステムは外部のホストに接続可能である。前記メモリシステムは、第１記憶領域を備える不揮発性の第１記憶装置と、コントローラとを備える。前記第１記憶領域は、前記ホストから受信したデータが格納される。前記コントローラは、前記第１記憶装置に対し、データの書き込みおよびデータの読み出しの制御を行う。前記第１記憶領域は、前記メモリシステムの論理アドレス空間のサイズである第１サイズより大きい第２サイズを有している。前記コントローラは、前記第１サイズを変更する要求を前記ホストから受信し、前記要求に応じて、前記論理アドレス空間のうちの少なくとも一部のデータを有効な状態に保ちながら前記第１サイズを変更する。前記メモリシステムは、前記論理アドレス空間内の論理アドレスと前記第１記憶領域内の物理アドレスとを対応付ける１以上のレコード、を備える第１対応情報が格納される第２記憶領域を備える第２記憶装置をさらに備える。前記コントローラは、前記要求に応じて前記第１対応情報が備えるレコードの数を変更する。前記第１対応情報は、１以上の第２レコードを備える第２対応情報と、物理アドレスが記録される１以上の第３対応情報とを含む。前記第２レコードは論理アドレスと前記１以上の第３対応情報のうちの対応する一つをポイントするポインタとを対応付ける情報である。前記コントローラは、前記要求に応じて前記第２対応情報が備える第２レコードの数を変更する。
【図面の簡単な説明】
【０００６】
【図１】図１は、第１の実施形態のメモリシステムの構成例を示す図である。
【図２】図２は、各メモリチップの構成例を示す図である。
【図３】図３は、各物理ブロックの構成例を示す図である。
【図４】図４は、各論理ブロックの構成例を示す図である。
【図５】図５は、メモリシステムに格納される各情報を説明する図である。
【図６】図６は、表記容量の制御を説明する図である。
【図７】図７は、アドレスの種類を説明するための図である。
【図８】図８は、1stNVおよび2ndTableのデータ構造例を示す図である。
【図９】図９は、1stVおよび2ndTableCacheのデータ構造例を示す図である。
【図１０】図１０は、LUTログのデータ構造例を示す図である。
【図１１】図１１は、物理ブロック情報のデータ構造例を示す図である。
【図１２】図１２は、LUTブロック情報のデータ構造例を示す図である。
【図１３】図１３は、LUTアクティブブロックリストのデータ構造例を示す図である。
【図１４】図１４は、第１クラスタカウンタのデータ構造例を示す図である。
【図１５】図１５は、UNMAP予約テーブルのデータ構造例を示す図である。
【図１６】図１６は、逆引きテーブルのデータ構造例を示す図である。
【図１７】図１７は、ギア比情報を説明するための図である。
【図１８】図１８は、ギア比情報を説明するための図である。
【図１９】図１９は、1stNVの復元の動作を説明するフローチャートである。
【図２０】図２０は、第１応答処理を説明するフローチャートである。
【図２１】図２１は、第２応答処理を説明するフローチャートである。
【図２２】図２２は、リージョンUNMAP処理を説明するフローチャートである。
【図２３】図２３は、アドレス解決処理を説明するフローチャートである。
【図２４】図２４は、アドレス更新処理を説明するフローチャートである。
【図２５】図２５は、レコードの不揮発化の動作を説明するフローチャートである。
【図２６】図２６は、LUTガベージコレクションを説明するフローチャートである。
【図２７】図２７は、ユーザガベージコレクションを説明するフローチャートである。
【図２８】図２８は、第１の実施形態の削減処理を説明するフローチャートである。
【図２９】図２９は、増加処理を説明するフローチャートである。
【図３０】図３０は、第２の実施形態の削減処理を説明するフローチャートである。
【図３１】図３１は、第２の実施形態の削減処理を説明するフローチャートである。
【図３２】図３２は、第２クラスタカウンタのデータ構造例を示す図である。
【図３３】図３３は、メモリシステムの実装例を示す図である。
【発明を実施するための形態】
【０００７】
以下に添付図面を参照して、実施形態にかかるメモリシステムを詳細に説明する。なお、これらの実施形態により本発明が限定されるものではない。
【０００８】
（第１の実施形態）
図１は、第１の実施形態のメモリシステムの構成例を示す図である。メモリシステム１は、通信路３を介してホスト２に接続される。ホスト２はコンピュータである。コンピュータは、例えば、パーソナルコンピュータ、ポータブルコンピュータ、または、携帯通信機器を含む。メモリシステム１は、ホスト２の外部記憶装置として機能する。通信路３のインタフェース規格としては任意の規格が採用可能である。ホスト２は、メモリシステム１に対してアクセス要求（書き込み要求、読み出し要求）、およびUNMAP要求を発行することができる。アクセス要求およびUNMAP要求は、論理的なアドレス情報（以降、第１アドレスという）を含んで構成される。UNMAP要求については後述する。ホスト２がメモリシステム１に対して用いる論理アドレス空間（即ち第１アドレスによってメモリシステム１内の位置の指定が可能な範囲）のサイズは、メモリシステム１の表記容量と等しい。言い換えると、メモリシステム１は、表記容量と等しいサイズの論理アドレス空間をホスト２に提供する。
【０００９】
メモリシステム１は、メモリコントローラ１０と、NAND型のフラッシュメモリ（NANDメモリ）２０と、RAM（Random  Access  Memory）３０とを備えている。NANDメモリ２０は、ストレージとして用いられる。なお、ストレージとして用いられるメモリの種類はNAND型のフラッシュメモリだけに限定されない。例えば、NOR型のフラッシュメモリ、ReRAM(Resistance Random Access  Memory)、またはMRAM(Magnetoresistive  Random  Access  Memory)などがストレージとして採用可能である。
【００１０】
NANDメモリ２０は、１以上のメモリチップ（CHIP）２１によって構成される。ここでは、NANDメモリ２０は、４つのメモリチップ２１を備える。
【００１１】
図２は、各メモリチップ２１の構成例を示す図である。各メモリチップ２１は、夫々メモリセルアレイ２３を備える。メモリセルアレイ２３は、複数のメモリセルがマトリクス状に配列されて構成される。メモリセルアレイ２３は、２つの領域（District）２４に分割されている。各District２４は、夫々、複数の物理ブロック２５を含む。各District２４は互いに独立した周辺回路（例えば、ロウデコーダ、カラムデコーダ、ページバッファ、データキャッシュ等）を備えていることにより、複数のDistrict２４が同時にアクセス（イレース、プログラムおよびリード）を実行することが可能である。プログラムとは、プログラム先の物理ブロック２５内のメモリセルにデータに応じた量の電荷を注入する動作をいう。各メモリチップ２１内の２つのDistrict２４の夫々は、プレーン番号（Plane#0、Plane#1）を用いて特定される。なお、各メモリチップ２１が備えるDistrict２４の数は「２」以外であってもよい。
【００１２】
物理ブロック２５は、各District２４におけるイレースの単位である。図３は、各物理ブロック２５の構成例を示す図である。各物理ブロック２５は、複数の物理ページ２６を備えて構成される。物理ページ２６は、各District２４におけるプログラムおよびリードの単位である。各物理ページ２６は、夫々ページ番号で識別される。
【００１３】
NANDメモリ２０を構成する４つのメモリチップ２１は、夫々、２つのチャネル（ch.0、ch.1）の何れかを介してメモリコントローラ１０に接続されている。ここでは、各チャネルに２つのメモリチップ２１が接続されている。各メモリチップ２１は、２つのチャネルのうちの何れか１つのみに接続されている。各チャネルは、Ｉ／Ｏ信号線および制御信号線を含む、配線群によって構成される。Ｉ／Ｏ信号線は、データ、アドレス、およびコマンドを送受信するための信号線である。なお、Ｉ／Ｏ信号線のビット幅は１ビットに限定されない。制御信号線は、ＷＥ（ライトイネーブル）信号、ＲＥ（リードイネーブル）信号、ＣＬＥ（コマンドラッチイネーブル）信号、ＡＬＥ（アドレスラッチイネーブル）信号、ＷＰ（ライトプロテクト）信号等を送受信するための信号線である。メモリコントローラ１０は、各チャネルを個別に制御することができる。メモリコントローラ１０は、２つのチャネルを同時にかつ個別に制御することによって、異なるチャネルに接続される２つのメモリチップ２１を同時に動作させることができる。
【００１４】
また、４つのメモリチップ２１は、複数のバンク２２を構成する。複数のバンク２２が構成されていることにより、メモリコントローラ１０は、バンクインターリーブを実行することができる。バンクインターリーブとは、並列動作の手法の一つである。具体的には、バンクインターリーブとは、１つのバンク２２に属する１以上のメモリチップ２１がデータにアクセスしている最中にメモリコントローラ１０が別のバンク２２へアクセスコマンドを発行することによって、NANDメモリ２０とメモリコントローラ１０との間のトータルの処理時間を短縮する手法である。図１の例においては、２つのバンク２２に対して異なるバンク番号（BANK#0、BANK#1）を付与することによって２つのバンク２２を夫々区別する。より詳しくは、各チャネルに接続される２つのメモリチップ２１のうちの一は、BANK#0を構成し、前記２つのメモリチップ２１のうちの他は、BANK#1を構成する。なお、アクセスコマンドは、プログラムコマンド、リードコマンド、およびイレースコマンドを含む。
【００１５】
このように、メモリコントローラ１０は、２つのチャネルを同時に動作させ、かつ、２つのバンク２２を用いたバンクインターリーブを実行することにより、合計４つのメモリチップ２１を並列動作させることができる。また、メモリコントローラ１０は、各メモリチップ２１に対しては、２つのDistrict２４に同時にアクセスする。メモリコントローラ１０は、並列にアクセスできる複数の物理ブロック２５をひとまとめにして、ひとつの論理ブロックとして管理する。例えば、論理ブロックを構成する複数の物理ブロック２５は、一括して消去される。
【００１６】
図４は、各論理ブロックの構成例を示す図である。ここでは、１つの論理ブロックは、夫々、チャネル番号、バンク番号、およびプレーン番号のうちの少なくとも１つが異なる８個の物理ブロック２５によって構成される。例えば、図４に示すハッチングが施された複数の物理ブロック２５は、１つの論理ブロックを構成する。１つの論理ブロックを構成する各物理ブロック２５の各District２４における物理的な位置は、同一でなくてもよい。各論理ブロックは、固有の論理ブロック番号が割り振られている。
【００１７】
RAM３０は、メモリコントローラ１０がNANDメモリ２０を制御するための各情報を記憶する。RAM３０に格納される各情報の詳細は後述する。また、RAM３０は、ホスト２とNANDメモリ２０との間のデータ転送のためのバッファとしてメモリコントローラ１０によって使用される。また、RAM３０は、ファームウェアプログラム（ファームウェアプログラム２０１）がロードされるバッファとしても使用される。なお、RAM３０としては任意の種類のメモリが適用可能である。例えば、DRAM（Dynamic Random Access Memory）、SRAM（Static Random Access Memory）、またはこれらの組み合わせがRAM３０として適用可能である。また、RAM３０の代わりに、ストレージよりも高速な任意のメモリが適用可能である。また、RAM３０はメモリコントローラ１０とともに１つのチップとして構成されてもよい。
【００１８】
メモリコントローラ１０は、CPU（Central  Processing  Unit）１１、ホストインタフェース（Host I/F）１２、RAMコントローラ（RAMC）１３、および、NANDコントローラ（NANDC）１４を備える。CPU１１、Host I/F１２、RAMC１３、およびNANDC１４は、バスで互いに接続されている。
【００１９】
Host I/F１２は、通信路３の制御を実行する。また、Host I/F１２は、ホスト２からの各種要求を受け付ける。また、Host I/F１２は、ホスト２とRAM３０との間のデータ転送を実行する。RAMC１３は、RAM３０を制御する。NANDC１４は、RAM３０とNANDメモリ２０との間のデータ転送を実行する。CPU１１は、RAM３０にロードされたファームウェアプログラム２０１に基づいて、メモリコントローラ１０全体の制御を実行する処理部として機能する。
【００２０】
図５は、メモリシステム１に格納される各情報を説明する図である。NANDメモリ２０は、システム領域２７と、available領域２８とを備える。システム領域２７は、ファームウェアプログラム２０１を予め記憶する。また、システム領域２７は、LUTログ２０２が格納される。また、システム領域２７は、LUTブロック領域２９が確保されている。LUTブロック領域２９は2ndTable２０４が格納される。
【００２１】
RAM３０は、物理ブロック情報３０１、LUTブロック情報３０２、LUTアクティブブロックリスト３０３、第１クラスタカウンタ３０４、表記容量設定値３０５、テーブル長設定値３０６、UNMAP予約テーブル３０７、1stV３０８、1stNV３０９、2ndTableCache３１０、逆引きテーブル３１１、ダーティリスト３１２、ギア比情報３１３、およびLUTブロック数設定値３１４が格納される。
【００２２】
システム領域２７は、システムデータを格納するための記憶領域である。システムデータとは、メモリシステム１を運用するために要するデータであり、ホスト２によって書き込みが要求されホスト２から送られてきたデータ（ユーザデータ２０５）、を除くデータである。available領域２８は、ユーザデータ２０５を格納するための記憶領域である。表記容量のサイズは、available領域２８のサイズよりも小さい。処理部は、available領域２８に、有効なユーザデータ２０５を最大で表記容量のサイズまで格納する。
【００２３】
available領域２８に記憶されているユーザデータ２０５の状態は、有効な状態と無効な状態とのうちの何れかである。NANDメモリ２０に第１のユーザデータ２０５が格納されている状態でホスト２から第１のユーザデータ２０５と同一の第１アドレスを指定して第２のユーザデータ２０５が送られてきた場合、メモリコントローラ１０は、空のページを有する論理ブロックに第２のユーザデータ２０５を書き込み、第１のユーザデータ２０５を無効なユーザデータ２０５としてみなす。「空の」状態とは、ここでは、無効なデータおよび有効なデータの何れも記憶されていない状態をいう。空のページは、データが書き込み可能な空き領域である。このような手法でNANDメモリ２０に対する書き込みが行われるため、各論理ブロックには、無効なユーザデータ２０５と有効なユーザデータ２０５とが記憶される。データが有効とは、そのデータが最新の状態であることをいう。同一の第１アドレスが指定された複数のデータがNANDメモリ２０に格納される場合において、最新の状態とは、その複数のデータのうちのホスト２が最後に書き込んだデータの状態をいう。無効なデータとは、前記複数のデータのうちの、ホスト２が最後に書き込んだデータ以外のデータをいう。
【００２４】
なお、NANDメモリ２０に対して上記のように書き込みが行われるため、書き込みが続くに応じて空の論理ブロックの数が減少する。メモリコントローラ１０は、空の論理ブロックを生成するために、ガベージコレクションを実行する。ガベージコレクションとは、一つの論理ブロックから有効なデータを他の論理ブロックの空き領域に移動（コピー）し、その後、移動元の論理ブロックに格納されている全データを無効なデータとしてみなす、処理をいう。移動元の論理ブロックは、ガベージコレクションの後、フリーブロックとしてみなされる。なお、フリーブロックの集合を、フリーブロックプールと表記する。各フリーブロックは、イレースが実行されることによって、何もデータを記憶していない状態になる。なお、ガベージコレクションに関し、移動元の論理ブロックを単にソースブロックと表記する。移動先の論理ブロックを単にデスティネーションブロックと表記する。available領域２８を構成する論理ブロックを対象とするガベージコレクションを、ユーザガベージコレクションと表記する。LUTブロック領域２９を構成する論理ブロックを対象とするガベージコレクションを、LUTガベージコレクションと表記する。
【００２５】
available領域２８のサイズから表記容量を減算して得られるサイズを、余裕容量（over-provisioning  capacity）と表記する。
【００２６】
本実施形態においては、メモリシステム１は、ホスト２から、表記容量を変更する要求（表記容量削減要求、表記容量増加要求）を受け付けることができる。表記容量増加要求をメモリシステム１が受信した場合、処理部は、図６のＳ１００１に示すように、表記容量を増加させる。表記容量の増加に応じて余裕容量が削減される。また、表記容量削減要求をメモリシステム１が受信した場合、処理部は、Ｓ１００２に示すように、表記容量を削減する。表記容量の削減に応じて余裕容量が増加する。表記容量削減要求および表記容量増加要求は、例えば、表記容量の変更量を示すサイズを含んで構成される。
【００２７】
前述した手法でNANDメモリ２０に対して書き込みが行われるため、ホスト２から指定される第１アドレスが示す物理的な位置が、書き込み毎に変更される。そこで、メモリシステム１は、ホスト２から指定される第１アドレスと物理的な位置との対応関係を記憶し、更新する。
【００２８】
図７は、メモリシステム１にて使用されるアドレスの種類を説明するための図である。ホスト２は、データの位置の指定のために第１アドレスを使用する。第１アドレスは、例えばセクタ毎にデータを指定することができる。ホスト２から指定される第１アドレスは、処理部によって、第２アドレスに変換される。第２アドレスは、データの位置をクラスタ単位で示す論理アドレス情報である。クラスタは、各セクタの位置を示す第１アドレスが連続する、複数のセクタ、によって構成される。第１アドレスと第２アドレスとの対応関係は、例えば固定されている。即ち、第２アドレスは、第１アドレスと同様に、論理アドレスの概念の範疇に含まれる。第１アドレスから第２アドレスへの変換は、例えば、クラスタのサイズに応じた量だけ第１アドレスを右方向にシフトするなどの所定の変換アルゴリズムを用いて実行される。以降、クラスタ単位のデータを単にクラスタと表記する。
【００２９】
第２アドレスは、リージョン番号と第１オフセットとを含む。リージョンは、各クラスタの位置を示す第２アドレスが連続する、複数のクラスタ、によって構成される。即ち、リージョンは、複数のクラスタのサイズに相当するサイズの、第２アドレス（および第１アドレス）の空間上における範囲をいう。リージョン番号は、各リージョンを特定するための番号である。例えば、第２アドレスの上位ビットがリージョン番号を示し、第２アドレスの下位ビットが第１オフセットを示す。第１オフセットは、リージョン番号で示されるリージョン内におけるクラスタ単位の位置を示す。
【００３０】
第２アドレスは、処理部によって、第３アドレスに翻訳される。第３アドレスは、論理ブロック番号および第２オフセットを含む。第２オフセットは、論理ブロック番号で示される論理ブロック内におけるクラスタ単位の位置を示す。また、第２オフセットは、チャネル番号、バンク番号、およびプレーン番号を含む。
【００３１】
第３アドレスは、処理部によって、第４アドレスに変換される。第４アドレスは、物理ブロック番号と第３オフセットとを含む。第３オフセットは、物理ブロック番号で示される物理ブロック２５内におけるクラスタ単位の物理的な位置を示す。第３オフセットは、ページ番号を含む。第３アドレスと第４アドレスとの対応関係は、例えば固定されている。即ち、第３アドレスは、第４アドレスと同様に、物理アドレスの概念の範疇に入る。
【００３２】
メモリシステム１は、データの書き込みに応じて第２アドレスと第３アドレスとの対応関係を変化させる。第２アドレスと第３アドレスとの対応関係は、階層構造のテーブルに記録される。ここでは、第２アドレスと第３アドレスとの対応関係は２つの階層を有するテーブルに記録されるものとする。第２階層目のテーブルには第３アドレスが記録される。第１階層目のテーブルは、第２アドレスと、当該第２アドレスに対応する第３アドレスが記憶されたレコードの格納位置を示すポインタと、の対応関係が記録される。第１階層目のテーブルは、リージョン単位でレコードが記録される。第２階層目のテーブルは、リージョン単位でレコードが記録される。第２階層目のテーブルの各レコードには、複数の第３アドレスが記録される。第２階層目のテーブルの各レコードに記録される複数の第３アドレスの夫々は、対応するリージョンに含まれる複数のクラスタの夫々に対応する。
【００３３】
2ndTable２０４は第２階層目のテーブルに該当する。2ndTableCache３１０は、2ndTable２０４がRAM３０にキャッシュされたものである。1stV３０８および1stNV３０９は、第１階層目のテーブルに該当する。LUTログ２０２は、1stNV３０９の変更によって生じた差分を記録したログ情報である。
【００３４】
図８は、1stNV３０９および2ndTable２０４のデータ構造例を示す図である。図示するように、1stNV３０９に記録される各レコードは、リージョン番号をインデックスとして含み、ポインタおよび第１フラグをデータ項目として含む。ポインタは、LUTブロック領域２９内の物理的な位置をポイントする。ポインタは、例えば第３アドレスまたは第４アドレスを用いて記述されている。ポインタが示す位置には、2ndTable２０４の対応するレコードが格納されている。2ndTable２０４の各レコードには、1stNV３０９のインデックスが示すリージョン、に含まれる複数のクラスタの夫々について、第３アドレスか、または、「UNMAP」が記録される。「UNMAP」は、UNMAP状態を示すマジックナンバーである。UNMAP状態とは、論理アドレスに対して物理アドレスが対応付けられていない状態をいう。実施形態では、第２アドレスが第３アドレスに対応付けられていない状態を以てUNMAP状態が実現する。なお、論理アドレスに対して物理アドレスが対応付けられている状態を非UNMAP状態（NOT-UNMAPPED state）と表記する。
【００３５】
第１フラグは、第２階層目のレコードが存在するか否かを示す。ここでは、例えば、第１フラグの値が「１」であることは、第２階層目のレコードが存在しないことを示し、第１フラグの値が「０」であることは、第２階層目のレコードが存在することを示す。第１フラグとして「１」が記録されているレコードにはポインタが記録されない。
【００３６】
図９は、1stV３０８および2ndTableCache３１０のデータ構造例を示す図である。図示するように、1stV３０８に記録される各レコードは、リージョン番号をインデックスとして含み、ポインタをデータ項目として含む。ポインタは、RAM３０内の物理的な位置をポイントする。ポインタが示す位置には、2ndTable２０４の対応するレコードが2ndTableCache３１０のレコードとして格納されている。2ndTableCache３１０にレコードが記録されていない場合には、1stV３０８の該当のレコードには、「Not cached」が記録される。なお、2ndTableCache３１０にレコードが記録されていることを、単に、リージョンがキャッシュされている、と表記する。
【００３７】
なお、1stV３０８および1stNV３０９のテーブル長は、定常状態においては、メモリシステム１に対して使用される論理アドレス空間が有するリージョンの数に等しい。定常状態とは、後述のＳ２０２０の処理またはＳ２１０３の処理によって表記容量の変更が1stV３０８および1stNV３０９に反映済みである状態をいう。ここではテーブル長はレコード数を示すこととする。なお、テーブル長は、テーブルのサイズを示すものであれば任意の種類の単位で示される。1stV３０８および1stNV３０９のテーブル長は、定常状態においては表記容量に対応する。1stV３０８および1stNV３０９のテーブル長は、テーブル長設定値３０６としてRAM３０に記憶される。ホスト２に対して提供する表記容量は、表記容量設定値３０５としてRAM３０に記憶される。メモリコントローラ１０は、所定番地を先頭とし表記容量設定値３０５が示すサイズの第１アドレスの範囲、に含まれない第１アドレスを指定するアクセス要求をホスト２から受信した場合、ホスト２に対してエラーを通知する。
【００３８】
図１０は、LUTログ２０２のデータ構造例を示す図である。図示するように、LUTログ２０２には、ポインタとリージョン番号との対からなる内容変更ログ２０２ａと、1stV３０８および1stNV３０９のテーブル長の変更内容を記録したサイズ変更ログ２０２ｂと、が記録される。サイズ変更ログ２０２ｂは、変更前のテーブル長（旧テーブル長）と変更後のテーブル長（新テーブル長）とが記録される。ここでは、テーブル長が大きくなるようにテーブル長が変更された場合のみサイズ変更ログ２０２ｂが記録される、として説明する。LUTログ２０２の各レコードは、時系列順に記録される。LUTログ２０２は、1stNV３０９をRAM３０に復元するために使用される。
【００３９】
2ndTableCache３１０に対する書き換えが行われた場合、2ndTableCache３１０にキャッシュされているレコードと2ndTable２０４に記録されているレコードとで内容が相違する事態が発生する。2ndTableCache３１０と2ndTable２０４とで内容が相違するレコードの状態を、ダーティと表記する。2ndTableCache３１０と2ndTable２０４とで内容が一致するレコードの状態を、クリーンと表記する。ダーティリスト３１２は、2ndTableCache３１０を構成する複数のレコードのうちのダーティレコードを記憶しておくためのリストである。ダーティリスト３１２は、例えば、クリーンな状態からダーティな状態に遷移したリージョンのリージョン番号が、時系列順に記録される。
【００４０】
図１１は、物理ブロック情報３０１のデータ構造例を示す図である。物理ブロック情報３０１は、第３アドレスを第４アドレスに変換する際に、物理ブロック番号を特定するためのテーブルである。図１１の例では、論理ブロック番号、チャネル番号、バンク番号、およびプレーン番号の組み合わせ毎に物理ブロック番号が記録されている。物理ブロック情報３０１は、例えば出荷前に生成され、システム領域２７に記録される。物理ブロック情報３０１は、起動後にシステム領域２７からRAM３０に読み出される。
【００４１】
図１２は、LUTブロック情報３０２のデータ構造例を示す図である。LUTブロック情報３０２は、LUTブロック領域２９を構成する複数の論理ブロックを管理する情報である。LUTブロック情報３０２に記録されている論理ブロックは、LUTブロック領域２９を構成する論理ブロックとして扱われ、LUTブロック情報３０２に記録されていない論理ブロックは、LUTブロック領域２９を構成する論理ブロックとして扱われない。図示するように、LUTブロック情報３０２に記録されている各レコードは、LUTブロックIDをインデックスとして含み、LUTブロック領域２９を構成する論理ブロックを示す論理ブロック番号をデータ項目として含む。LUTブロックIDは、LUTブロック領域２９を構成する各論理ブロックに対して付与される識別番号である。
【００４２】
LUTブロック数設定値３１４は、LUTブロック領域２９を構成する論理ブロックの数の設定値を記録した情報である。処理部は、テーブル長設定値３０６の変更に応じてLUTブロック数設定値３１４を更新する。そして、処理部は、LUTブロック領域２９を構成する論理ブロックの数がLUTブロック数設定値３１４に記録されている値に定常状態においては一致するように、LUTブロック領域２９を管理する。
【００４３】
図１３は、LUTアクティブブロックリスト３０３のデータ構造例を示す図である。LUTアクティブブロックリスト３０３は、LUTブロック情報３０２に記録されている複数の論理ブロックのうちの１以上のアクティブブロックについて、2ndTable２０４のレコードの記録が開始されたタイミングが最も古いアクティブブロックから順番に論理ブロック番号（またはLUTブロックID）が記録された情報である。なお、ここでは、一つの論理ブロックがいっぱいになるまで当該一つの論理ブロックに対して2ndTable２０４のレコードが記録された後、次の空の論理ブロックに対して2ndTable２０４のレコードの記録が開始されるものとする。アクティブブロックとは、いっぱいまで書き込みが行われ、書き込み可能な記憶領域がない論理ブロックをいう。以降、LUTアクティブブロックリスト３０３に記録されているアクティブブロックを、LUTアクティブブロックと表記する。
【００４４】
図１４は、第１クラスタカウンタ３０４のデータ構造例を示す図である。第１クラスタカウンタ３０４は、論理ブロックに記憶される有効なクラスタの数を論理ブロック毎に記録した情報である。ここでは、第１クラスタカウンタ３０４は、available領域２８を構成する論理ブロック毎にレコードが記録されているものとする。図示するように、第１クラスタカウンタ３０４に記録される各レコードは、論理ブロック番号をインデックスとして含み、有効クラスタ数をデータ項目として含む。
【００４５】
ユーザログ２０３は、available領域２８に書き込まれた各クラスタについて、書き込み要求またはガベージコレクションによって書き込みが要求された時に指定された第１アドレスから変換された第２アドレスを記録した情報である。ユーザログ２０３を構成する各レコードは、ユーザデータ２０５とクラスタ単位で対応付けられている。例えば、available領域２８を構成する各論理ブロックの一部にシステム領域２７が確保され、available領域２８を構成する各論理ブロックの一部に確保されたシステム領域２７にユーザログ２０３のレコードが記録される。これにより、論理ブロックのイレースによって、ユーザデータ２０５とそのユーザデータ２０５に対応するユーザログ２０３のレコードとは同じタイミングでイレースされる。
【００４６】
図１５は、UNMAP予約テーブル３０７のデータ構造例を示す図である。図示するように、UNMAP予約テーブル３０７の各レコードは、リージョン番号をインデックスとして含み、第２フラグをデータ項目として含む。第２フラグは、UNMAP処理の実行が予約されているか否かを示す。なお、UNMAP処理とは、第１アドレスの空間上の指定された範囲の状態を、非UNMAP状態からUNMAP状態に遷移させる処理をいう。ここでは、処理部は、第２アドレスの空間上の指定された範囲の状態を、第３アドレスが対応付けられている状態から第３アドレスが対応付けられていない状態に遷移させることによってUNMAP処理を実現する。UNMAP要求は、メモリシステム１にUNMAP処理を実行せしめるための要求である。
【００４７】
図１６は、逆引きテーブル３１１のデータ構造例を示す図である。前述のように、1stNV３０９は、リージョン番号から2ndTable２０４における当該リージョン番号に対応するレコードの格納位置を示すポインタを検索するためのテーブルである。これに対し、逆引きテーブル３１１は、2ndTable２０４におけるレコードの格納位置を示すポインタから当該レコードに対応するリージョン番号を検索するためのテーブルである。図１６の例によれば、逆引きテーブル３１１の各レコードは、LUTブロックIDをインデックスとして含み、複数のリージョン番号をデータ項目として含む。各レコードのデータ項目に記録されている複数のリージョン番号の順番は、論理ブロックにおける2ndTable２０４におけるレコードの格納位置の順番と対応する。従って、処理部は、図１６に示す逆引きテーブル３１１を参照することによって、検索対象のポインタからそのポインタが示す位置に格納されているレコードに対応するリージョン番号を取得することが可能である。
【００４８】
ギア比情報３１３は、available領域２８へ書き込まれる２種類のデータの量の比（以降、単にギア比）の設定値を求めるための情報である。前記２種類のデータのうちの一のデータは、ホスト２から書き込みが要求されたデータである。前記２種類のデータのうちの他のデータは、ユーザガベージコレクションによってavailable領域２８へ書き込まれるデータ（即ち、ソースブロックからデスティネーションブロックへコピーされるデータ）である。ここでは、ギア比は、前記一のデータの量に対する前記他のデータの量の比であることとする。ソースブロックからデスティネーションブロックへコピーされるデータ量（コピー量）が多い場合、コピー量が少ない場合に比べて、ギア比が大きい。処理部は、ギア比がギア比情報３１３から求まる設定値と等しくなるように、ガベージコレクションの実行を制御する。ギア比情報３１３は、フリーブロック数または余裕率またはその両方と、ギア比の設定値と、の関係を規定する。余裕率とは、余裕容量を表記容量で除算して得られる値である。ギア比情報３１３は、ルックアップテーブルのデータ構造を有していてもよい。また、ギア比情報３１３は、関数であってもよい。
【００４９】
図１７および図１８は、ギア比情報３１３によって規定される関係を説明するための図である。
【００５０】
図１７に示すように、ギア比情報３１３は、フリーブロック数が大きくなるほどギア比が小さくなるようにフリーブロック数とギア比との関係を規定する。フリーブロック数とギア比との関係は、ステップ状に変化するように規定されてもよいし、なめらかに変化するように規定されてもよい。ギア比情報３１３は、フリーブロック数が第３値である場合に、フリーブロック数が第３値よりも大きい第４値である場合に比べてギア比が大きくなるように、フリーブロック数とギア比との関係を規定する。
【００５１】
図１８に示すように、ギア比情報３１３は、余裕率が小さくなるほどギア比が大きくなるように余裕率とギア比との関係を規定する。余裕率とギア比との関係は、ステップ状に変化するように規定されてもよいし、なめらかに変化するように規定されてもよい。ギア比情報３１３は、余裕率が第１値である場合に、余裕率が第１値よりも大きい第２値である場合に比べてギア比が大きくなるように、余裕率とギア比との関係を規定する。
【００５２】
なお、ギア比情報３１３は、余裕率の代わりに余裕容量とギア比との関係を規定してもよい。余裕容量の増減に対するギア比の増減の傾向は、上記に説明した余裕率の増減に対するギア比の増減の傾向と等しい。また、ギア比情報３１３は、available領域２８のサイズは固定されていることを利用して、表記容量と余裕率との関係を規定してもよい。例えば、ギア比情報３１３は、表記容量が第５値である場合に、表記容量が第５値よりも小さい第６値である場合に比べてギア比が大きくなるように、表記容量とギア比との関係を規定する。
【００５３】
さらに、処理部は、LUTガベージコレクションについてもギア比の制御を実行する。LUTガベージコレクションに関するギア比を、ユーザガベージコレクションに関するギア比を区別するために、LUTギア比、と表記する。LUTギア比は、LUTブロック領域２９へ書き込まれる２種類のデータの量の比である。前記LUTブロック領域２９へ書き込まれる２種類のデータのうちの一のデータは、Ｓ１７０２の処理（後述する）によってLUTブロック領域２９に書き込まれるデータである。前記LUTブロック領域２９へ書き込まれる２種類のデータのうちの他のデータは、LUTガベージコレクションによってLUTブロック領域２９に書き込まれるデータである。処理部は、フリーブロック数に応じてLUTギア比の設定値を演算する。ここで、LUTガベージコレクションにおけるフリーブロック数とは、LUTアクティブブロックの数をLUTブロック数設定値３１４から減算して得られる値である。LUTギア比とフリーブロック数との関係は、図１７に示す関係と同様の関係が予め設定されている。処理部は、LUTギア比がLUTギア比の設定値に一致するように、LUTガベージコレクションの実行を制御する。
【００５４】
次に、第１の実施形態のメモリシステム１の動作を説明する。
【００５５】
メモリシステム１は、パワーオフの前に、ホスト２からパワーオフの予告を受信する。処理部は、パワーオフの予告を受信すると、パワーオフシーケンスを実行する。パワーオフシーケンスは、RAM３０内の各種情報をシステム領域２７に退避させる処理を含む。少なくともダーティリスト３１２に記載のダーティレコードは退避対象に設定される。例えば、退避のための専用領域がシステム領域２７に確保され、ダーティレコードは、RAM３０内の退避対象の他の情報とともに当該専用領域に退避せしめられる。また、ダーティレコードは、前記専用領域ではなく2ndTable２０４の末尾に記録されてもよい。
【００５６】
なお、ダーティレコードの他に何れの情報を退避対象とするかは任意に設計される。処理部は、パワーオンの直後に、パワーオンシーケンスを実行する。パワーオンシーケンスは、各種情報をRAM３０内にロードしたり、パワーオフシーケンスによってRAM３０から失われた情報を復元したりする処理を含む。例えば、パワーオンシーケンスの実行時に、NANDメモリ２０内に記憶される他の情報（2ndTable２０４、LUTログ２０２など）に基づいてRAM３０内に復元できない情報は、パワーオフシーケンスにおける退避対象に設定される。また、復元を行う場合と、パワーオフシーケンスにおいてシステム領域２７に退避し、かつ、パワーオンシーケンスにおいてRAM３０にロードする場合と、の何れの場合がパワーオンシーケンスの実行時間が短いかに応じて、パワーオフシーケンスにおける退避対象が設定されてもよい。ここでは一例として、LUTブロック情報３０２、LUTアクティブブロックリスト３０３、第１クラスタカウンタ３０４、表記容量設定値３０５、テーブル長設定値３０６、UNMAP予約テーブル３０７、ダーティリスト３１２に記載のダーティレコード、およびLUTブロック数設定値３１４が退避対象に含まれるものとする。ここでは、1stNV３０９は、LUTログ２０２に基づいて復元される。逆引きテーブル３１１は、1stNV３０９に基づいて復元される。また、物理ブロック情報３０１およびギア比情報３１３は、システム領域２７に予め記憶され（図示せず）、パワーオンシーケンスにおいてシステム領域２７からRAM３０にロードされる。物理ブロック情報３０１およびギア比情報３１３は、パワーオフシーケンスにおいてはRAM３０から失われる。
【００５７】
パワーオフの予告なく電力の供給が途絶える事象を、電源断と表記する。メモリシステム１は、電源断時においてもパワーオフシーケンスを実行するために、バッテリ（図示せず）を備える。メモリシステム１は、電源断の直後には、バッテリの電力を用いてパワーオフシーケンスを実行する。なお、予告に基づくパワーオフシーケンスと電源断時のパワーオフシーケンスとは、異なっていてもよいし、同じであってもよい。ここでは一例として、電源断時のパワーオフシーケンスにおいても、予告に基づくパワーオフシーケンスと同じ情報が退避対象として扱われるものとする。
【００５８】
実施形態においては、処理部はLUTログ２０２に基づいて1stNV３０９を復元する。図１９は、1stNV３０９の復元の動作を説明するフローチャートである。
【００５９】
まず、処理部は、テーブル長設定値３０６およびLUTアクティブブロックリスト３０３をシステム領域２７からRAM３０にロードする（Ｓ１１０１）。なお、テーブル長設定値３０６に記述されたテーブル長を「L」と表記する。そして、処理部は、「L」個のレコードを有し、全レコードのデータ項目が空欄の1stNV３０９を、RAM３０に生成する（Ｓ１１０２）。Ｓ１１０２の処理によって、リージョン番号が「０」から「Ｌ−１」までのレコードが生成される。
【００６０】
続いて、処理部は、全レコードに第１フラグを立てる（Ｓ１１０３）。第１フラグを立てるとは、ここでは、第１フラグに「１」を記録することである。そして、処理部は、LUTログ２０２から最も古いレコードを読み出す（Ｓ１１０４）。そして、処理部は、読み出したレコードは内容変更ログ２０２ａであるか否かを判定する（Ｓ１１０５）。読み出したレコードが内容変更ログ２０２ａである場合には（Ｓ１１０５、Ｙｅｓ）、処理部は、読み出した内容変更ログ２０２ａに含まれるリージョン番号が「L」未満であるか否かを判定する（Ｓ１１０６）。
【００６１】
読み出した内容変更ログ２０２ａに含まれるリージョン番号が「L」未満ではない場合（Ｓ１１０６、Ｎｏ）、処理部は、未だ読み出されていないレコードがあるか否かを判定する（Ｓ１１０７）。未だ読み出されていないレコードがある場合には（Ｓ１１０７、Ｙｅｓ）、処理部は、未だ読み出されていない１以上のレコードについてＳ１１０４の処理を再び実行する。読み出した内容変更ログ２０２ａに含まれるリージョン番号が「L」未満である場合（Ｓ１１０６、Ｙｅｓ）、処理部は、読み出した内容変更ログ２０２ａに基づいて1stNV３０９を更新する（Ｓ１１０８）。具体的には、処理部は、読み出した内容変更ログ２０２ａに含まれるリージョン番号をインデックスとして含む1stNV３０９のレコードを特定する。そして、処理部は、特定したレコードのデータ項目に、読み出した内容変更ログ２０２ａに含まれるポインタを記録する。処理部は、Ｓ１１０８の処理の後、Ｓ１１０７の処理を実行する。
【００６２】
読み出したレコードが内容変更ログ２０２ａではない場合（Ｓ１１０５、Ｎｏ）、即ち読み出したレコードがサイズ変更ログ２０２ｂである場合、処理部は、「Lold」が「L」未満であるか否かを判定する（Ｓ１１０９）。ここで、「Lold」はサイズ変更ログ２０２ｂに含まれる旧テーブル長の値である。「Lold」が「L」未満ではない場合（Ｓ１１０９、Ｎｏ）、処理部は、Ｓ１１０７の処理を実行する。「Lold」が「L」未満である場合（Ｓ１１０９、Ｙｅｓ）、処理部は、「Lold」から、「L」および新テーブル長「Lnew」のうちの小さいほうから１を減算して得られる値、までのリージョン番号、を含む全てのレコードに、第１フラグを立てる（Ｓ１１１０）。Ｓ１１１０の処理の後、処理部は、Ｓ１１０７の処理を実行する。
【００６３】
未だ読み出されていないレコードがない場合には（Ｓ１１０７、Ｎｏ）、1stNV３０９の復元が完了する。処理部は、1stNV３０９の復元の動作を終了する。
【００６４】
処理部は、復元された1stNV３０９に基づいて逆引きテーブル３１１を生成することが可能である。
【００６５】
図２０および図２１は、UNMAP要求に応じた応答処理を説明するフローチャートである。UNMAP要求は、UNMAP処理の対象の範囲の指定を含む。UNMAP処理の対象の範囲は、例えば、当該範囲の先頭位置を示す第１アドレスと、当該範囲のサイズと、の組み合わせによって指定される。処理部は、UNMAP処理の対象の範囲に応じて、第１応答処理または第２応答処理を実行する。UNMAP処理の対象の範囲がリージョンよりも小さい場合、処理部は、第１応答処理を実行する。UNMAP処理の対象の範囲が１以上のリージョンである場合、処理部は、第２応答処理を実行する。図２０は、第１応答処理を説明するフローチャートであり、図２１は、第２応答処理を説明するフローチャートである。
【００６６】
まず、第１応答処理を説明する。図２０の説明において、UNMAP処理の対象として指定されたクラスタを、対象クラスタと表記し、対象クラスタを含むリージョンを、対象リージョンと表記する。
【００６７】
処理部は、ホスト２からUNMAP要求を受信すると（Ｓ１２０１）、処理部は、1stNV３０９を参照することによって、対象リージョンについて第１フラグが立っているか否かを判定する（Ｓ１２０２）。対象リージョンについて第１フラグが立っていない場合（Ｓ１２０２、Ｎｏ）、処理部は、UNMAP予約テーブル３０７を参照することによって、対象リージョンについて第２フラグが立っているか否かを判定する（Ｓ１２０３）。対象リージョンについて第１フラグが立っている場合（Ｓ１２０２、Ｙｅｓ）、または、対象リージョンについて第２フラグが立っている場合（Ｓ１２０３、Ｙｅｓ）、処理部は、UNMAP処理の実行完了をホスト２に送信し（Ｓ１２０４）、第１応答処理を終了する。
【００６８】
対象リージョンについて第２フラグが立っていない場合（Ｓ１２０３、Ｎｏ）、1stV３０８を参照することによって、対象リージョンがキャッシュされているか否かを判定する（Ｓ１２０５）。対象リージョンがキャッシュされていない場合（Ｓ１２０５、Ｎｏ）、処理部は、1stNV３０９を参照することによって、対象リージョンのレコードのNANDメモリ２０上における格納位置を示すポインタを取得する（Ｓ１２０６）。そして、処理部は、対象リージョンのレコードを、取得したポインタが示す位置から2ndTableCache３１０に読み出す（Ｓ１２０７）。処理部は、Ｓ１２０７の処理による2ndTableCache３１０の更新に応じて、対象リージョンのレコードがキャッシュされている位置を示すポインタを1stV３０８に記録する（Ｓ１２０８）。
【００６９】
対象リージョンがキャッシュされている場合（Ｓ１２０５、Ｙｅｓ）、または、Ｓ１２０８の処理の後、処理部は、2ndTableCache３１０を参照することによって、対象クラスタがUNMAP状態であるか否かを判定する（Ｓ１２０９）。対象クラスタがUNMAP状態でない場合（Ｓ１２０９、Ｎｏ）、処理部は、2ndTableCache３１０を参照することによって、対象クラスタに設定されている第３アドレスを取得する（Ｓ１２１０）。第１応答処理において、Ｓ１２１０の処理によって取得される第３アドレスを、古い第３アドレス、と表記する。処理部は、古い第３アドレスが含まれる論理ブロックについて、第１クラスタカウンタ３０４に記録されている値をデクリメントする（Ｓ１２１１）。処理部は、2ndTableCache３１０において、対象クラスタに、「UNMAP」を設定する（Ｓ１２１２）。処理部は、対象リージョンをダーティリスト３１２に追加する（Ｓ１２１３）。そして、処理部は、Ｓ１２０４の処理を実行する。対象クラスタがUNMAP状態である場合（Ｓ１２０９、Ｙｅｓ）、処理部は、Ｓ１２１０〜Ｓ１２１３の処理をスキップする。
【００７０】
なお、UNMAP処理の対象として指定された範囲が複数のクラスタを含む場合には、処理部は、UNMAP処理の対象として指定された範囲内の全クラスタについて図２０に示した一連の処理を実行する。または、処理部は、UNMAP処理の対象として指定された範囲内の全クラスタについてＳ１２０４の処理を行う準備がととのった後に、UNMAP処理の実行完了を１回だけホスト２に送信する。
【００７１】
次に、第２応答処理を説明する。図２１において、UNMAP要求によってUNMAP処理の対象として指定されたリージョンを、対象リージョンと表記する。
【００７２】
処理部は、ホスト２からUNMAP要求を受信すると（Ｓ１３０１）、1stNV３０９を参照することによって、対象リージョンについて第１フラグが立っているか否かを判定する（Ｓ１３０２）。対象リージョンについて第１フラグが立っていない場合（Ｓ１３０２、Ｎｏ）、処理部は、UNMAP予約テーブル３０７を参照することによって、対象リージョンについて第２フラグが立っているか否かを判定する（Ｓ１３０３）。対象リージョンについて第２フラグが立っていない場合（Ｓ１３０３、Ｎｏ）、処理部は、対象リージョンについて第２フラグを立てる（Ｓ１３０４）。対象リージョンについて第１フラグが立っている場合（Ｓ１３０２、Ｙｅｓ）、または、対象リージョンについて第２フラグが立っている場合（Ｓ１３０３、Ｙｅｓ）、または、Ｓ１３０４の処理の後、処理部は、UNMAP処理の実行完了をホスト２に送信し（Ｓ１３０５）、第２応答処理を終了する。
【００７３】
このように、リージョン単位のUNMAP処理が要求された場合には、第１フラグが立っていない場合、処理部は、第２フラグを立てたのちにUNMAP処理の実行完了を送信する。処理部は、第２フラグが立てられているリージョンに対する実際のUNMAP処理を、後述する動作によって、UNMAP処理の実行完了の送信のタイミングの後に遅延して実行することができる。
【００７４】
なお、UNMAP処理の対象として指定された範囲が複数のリージョンを含む場合には、処理部は、UNMAP処理の対象として指定された範囲内の全リージョンについて図２１に示した一連の処理を実行する。または、処理部は、UNMAP処理の対象として指定された範囲内の全リージョンについてＳ１３０５の処理を行う準備がととのった後に、UNMAP処理の実行完了を１回だけホスト２に送信する。
【００７５】
図２２は、リージョン単位のUNMAP処理（以降、単にリージョンUNMAP処理）を説明するフローチャートである。処理部は、図２２に示す動作を、第２応答処理の後の任意のタイミングで実行することができる。また、リージョンUNMAP処理は、後述のアドレス解決処理、アドレス更新処理、ユーザガベージコレクション、および削減処理、のそれぞれの実行中に適宜、呼び出される。また、処理部は、第２フラグが立っているリージョンが存在する間、当該第２フラグが立っているリージョンを対象としてバックグラウンドにてリージョンUNMAP処理を実施することができる。処理部は、UNMAP予約テーブル３０７において第２フラグが立てられた状態のリージョンを対象としてリージョンUNMAP処理を実行する。図２２の説明において、UNMAP予約テーブル３０７において第２フラグが立てられた状態のリージョンであってリージョンUNMAP処理の対象であるリージョンを、対象リージョンと表記する。また、図２２の説明は、予め対象リージョンがキャッシュされていることを前提に説明する。即ち、処理部は、対象リージョンがキャッシュされていない場合には、対象リージョンのレコードをNANDメモリ２０から2ndTableCache３１０に読み出した後に、リージョンUNMAP処理を実行する。
【００７６】
処理部は、まず、2ndTableCache３１０を参照することによって、対象リージョン内に１以上の非UNMAP状態のクラスタが存在するか否かを判定する（Ｓ１４０１）。対象リージョン内に１以上の非UNMAP状態のクラスタが存在する場合（Ｓ１４０１、Ｙｅｓ）、処理部は、対象リージョン内に存在する１以上の非UNMAP状態のクラスタのうちの１つを着目クラスタとして設定する（Ｓ１４０２）。処理部は、2ndTableCache３１０を参照することによって、着目クラスタに設定されている第３アドレスを取得する（Ｓ１４０３）。処理部は、取得した第３アドレスが含まれる論理ブロックについて、第１クラスタカウンタ３０４に記録されている値をデクリメントする（Ｓ１４０４）。処理部は、2ndTableCache３１０において、着目クラスタに「UNMAP」を設定し（Ｓ１４０５）、対象リージョン内に１以上の非UNMAP状態のクラスタが存在するか否かを再び判定する（Ｓ１４０６）。対象リージョン内に１以上の非UNMAP状態のクラスタが存在する場合（Ｓ１４０６、Ｙｅｓ）、処理部は、Ｓ１４０２の処理を実行する。対象リージョン内に存在するクラスタの全てがUNMAP状態である場合（Ｓ１４０６、Ｎｏ）、処理部は、対象リージョンをダーティリスト３１２に追加し（Ｓ１４０７）、対象リージョンについての第２フラグを下ろす（Ｓ１４０８）。
【００７７】
対象リージョン内に存在するクラスタの全てがUNMAP状態である場合（Ｓ１４０１、Ｎｏ）、処理部は、Ｓ１４０２〜Ｓ１４０７の処理をスキップする。
【００７８】
なお、リージョンUNMAP処理の呼び出し元の１つに、後述の削減処理がある。削減処理によって呼び出されたリージョンUNMAP処理においては、Ｓ１４０７の処理は実行されてもよいしスキップされてもよい。
【００７９】
図２３は、第２アドレスを第３アドレスに翻訳する処理（以降、アドレス解決処理）を説明するフローチャートである。アドレス解決処理の対象の第２アドレスを、対象の第２アドレス、と表記する。対象の第２アドレスが含むリージョン番号、が示すリージョンを、対象リージョンと表記する。
【００８０】
まず、処理部は、対象リージョンのリージョン番号が「L」未満であるか否かを判定する（Ｓ１５０１）。対象リージョンのリージョン番号が「L」未満である場合（Ｓ１５０１、Ｙｅｓ）、処理部は、1stV３０８を参照することによって、対象リージョンがキャッシュされているか否かを判定する（Ｓ１５０２）。対象リージョンがキャッシュされていない場合（Ｓ１５０２、Ｎｏ）、処理部は、1stNV３０９を参照することによって、対象リージョンについて第１フラグが立っているか否かを判定する（Ｓ１５０３）。
【００８１】
対象リージョンについて第１フラグが立っていない場合（Ｓ１５０３、Ｎｏ）、処理部は、1stNV３０９を参照することによって、対象リージョンのレコードのNANDメモリ２０上における格納位置を示すポインタを取得する（Ｓ１５０４）。そして、処理部は、対象リージョンのレコードを、取得したポインタが示す位置から2ndTableCache３１０に読み出す（Ｓ１５０５）。処理部は、Ｓ１５０５の処理による2ndTableCache３１０の更新に応じて、対象リージョンのレコードがキャッシュされている位置を示すポインタを1stV３０８に記録する（Ｓ１５０６）。
【００８２】
対象リージョンがキャッシュされている場合（Ｓ１５０２、Ｙｅｓ）、または、Ｓ１５０６の処理の後、処理部は、UNMAP予約テーブル３０７を参照することによって、対象リージョンについて第２フラグが立っているか否かを判定する（Ｓ１５０７）。対象リージョンについて第２フラグが立っている場合（Ｓ１５０７、Ｙｅｓ）、処理部は、対象リージョンに対して、リージョンUNMAP処理を実行する（Ｓ１５０８）。
【００８３】
対象リージョンについて第２フラグが立っていない場合（Ｓ１５０７、Ｎｏ）、またはＳ１５０８の処理の後、処理部は、2ndTableCache３１０を参照することによって、対象の第２アドレスを第３アドレスに翻訳し（Ｓ１５０９）、動作を終了する。なお、処理部は、翻訳結果として、第３アドレスの代わりに「UNMAP」を取得することがある。
【００８４】
対象リージョンのリージョン番号が「L」未満ではない場合（Ｓ１５０１、Ｎｏ）、処理部は、翻訳結果として「無効」を取得し（Ｓ１５１０）、動作を終了する。また、対象リージョンについて第１フラグが立っている場合（Ｓ１５０３、Ｙｅｓ）、処理部は、翻訳結果として「UNMAP」を取得し（Ｓ１５１１）、アドレス解決処理を終了する。
【００８５】
なお、以上の説明においては、処理部は、対象リージョンについて第２フラグが立っているか否かの判定（Ｓ１５０７）の結果に基づいてリージョンUNMAP処理を実行する（S１５０８）。処理部は、対象リージョンについて第２フラグが立っている場合において（S１５０８）、リージョンUNMAP処理を実行することなく翻訳結果として「UNMAP」を取得するように構成されてもよい。
【００８６】
図２４は、新しい第３アドレスを記録する処理（以降、アドレス更新処理）を説明するフローチャートである。アドレス更新処理の対象の第２アドレスが示すクラスタを、対象クラスタと表記する。対象クラスタを含むリージョンを、対象リージョンと表記する。
【００８７】
まず、処理部は、1stV３０８を参照することによって、対象リージョンがキャッシュされているか否かを判定する（Ｓ１６０１）。対象リージョンがキャッシュされていない場合（Ｓ１６０１、Ｎｏ）、処理部は、1stNV３０９を参照することによって、対象リージョンについて第１フラグが立っているか否かを判定する（Ｓ１６０２）。
【００８８】
対象リージョンについて第１フラグが立っている場合（Ｓ１６０２、Ｙｅｓ）、処理部は、対象リージョンのレコードを2ndTableCache３１０に生成する（Ｓ１６０３）。なお、Ｓ１６０３の処理において、処理部は、対象リージョンのレコードに関しては、全クラスタに「UNMAP」を設定する。処理部は、Ｓ１６０３の処理による2ndTableCache３１０の更新に応じて、対象リージョンのレコードがキャッシュされている位置を示すポインタを1stV３０８に記録する（Ｓ１６０４）。そして、処理部は、対象リージョンについて第１フラグを下ろす（Ｓ１６０５）。
【００８９】
対象リージョンについて第１フラグが立っていない場合（Ｓ１６０２、Ｎｏ）、処理部は、1stNV３０９を参照することによって、対象リージョンのレコードのNANDメモリ２０上における格納位置を示すポインタを取得する（Ｓ１６０６）。そして、処理部は、対象リージョンのレコードを、取得したポインタが示す位置から2ndTableCache３１０に読み出す（Ｓ１６０７）。処理部は、対象リージョンのレコードがキャッシュされている位置を示すポインタを1stV３０８に記録する（Ｓ１６０８）。
【００９０】
対象リージョンがキャッシュされている場合（Ｓ１６０１、Ｙｅｓ）、または、Ｓ１６０８の処理の後、処理部は、UNMAP予約テーブル３０７を参照することによって、対象リージョンについて第２フラグが立っているか否かを判定する（Ｓ１６０９）。対象リージョンについて第２フラグが立っている場合（Ｓ１６０９、Ｙｅｓ）、処理部は、対象リージョンに対して、リージョンUNMAP処理を実行する（Ｓ１６１０）。
【００９１】
Ｓ１６０５の処理の後、または、対象リージョンについて第２フラグが立っていない場合（Ｓ１６０９、Ｎｏ）、または、Ｓ１６１０の処理の後、処理部は、2ndTableCache３１０を参照することによって、対象クラスタがUNMAP状態であるか否かを判定する（Ｓ１６１１）。対象クラスタがUNMAP状態ではない場合（Ｓ１６１１、Ｎｏ）、処理部は、2ndTableCache３１０を参照することによって、対象クラスタに設定されている第３アドレスを取得する（Ｓ１６１２）。図２４の説明において、Ｓ１６１２の処理によって取得される第３アドレスを、古い第３アドレス、と表記する。処理部は、古い第３アドレスが含まれる論理ブロックについて、第１クラスタカウンタ３０４に記録されている値をデクリメントする（Ｓ１６１３）。対象クラスタがUNMAP状態である場合（Ｓ１６１１、Ｙｅｓ）、処理部は、Ｓ１６１２およびＳ１６１３の処理をスキップする。
【００９２】
続いて、処理部は、2ndTableCache３１０において、対象クラスタに新しい第３アドレスを設定する（Ｓ１６１４）。処理部は、新しい第３アドレスが含まれる論理ブロックについて、第１クラスタカウンタ３０４に記録されている値をインクリメントする（Ｓ１６１５）。そして、処理部は、対象リージョンをダーティリスト３１２に追加し（Ｓ１６１６）、アドレス更新処理を終了する。
【００９３】
図２５は、ダーティリスト３１２に記載のレコードの不揮発化の動作を説明するフローチャートである。まず、処理部は、ダーティリスト３１２を参照することによって、不揮発化の対象のリージョンを特定する（Ｓ１７０１）。処理部は、Ｓ１７０１の処理においては、ダーティリスト３１２に記載されている１以上のリージョンのうちから最も古くにダーティリスト３１２に追加されたリージョンを、不揮発化の対象のリージョンとして特定する。図２５の説明において、不揮発化の対象のリージョンを、対象リージョンと表記する。
【００９４】
続いて、処理部は、2ndTableCache３１０に記録されている対象リージョンのレコードを2ndTable２０４の末尾に記録（追加）する（Ｓ１７０２）。処理部は、2ndTableCache３１０へのレコードの追加に応じて、1stNV３０９に記録されているポインタの更新（Ｓ１７０３）、逆引きテーブル３１１の更新（Ｓ１７０４）、およびLUTログ２０２への内容変更ログ２０２ａの追加（Ｓ１７０５）を実行する。具体的には、Ｓ１７０３の処理においては、処理部は、対象リージョンについて1stNV３０９に記録されているポインタを、Ｓ１７０２の処理によって対象リージョンのレコードが記録された位置を示すポインタで上書きする。Ｓ１７０４の処理においては、処理部は、Ｓ１７０２の処理によって対象リージョンのレコードが記録された論理ブロック、のLUTブロックIDを求める。そして、処理部は、求めたLUTブロックIDをインデックスとするレコードに、対象リージョンのリージョン番号を追加する。また、Ｓ１７０５の処理においては、処理部は、Ｓ１７０２の処理によって対象リージョンのレコードが記録された位置をポイントするポインタと、対象リージョンのリージョン番号と、の対からなる内容変更ログ２０２ａをLUTログ２０２の末尾に記録（追加）する。
【００９５】
そして、処理部は、対象リージョンをダーティリスト３１２から削除する（Ｓ１７０６）。さらに、対象リージョンのレコードを2ndTableCache３１０から削除するように設定されている場合には（Ｓ１７０７、Ｙｅｓ）、対象リージョンのレコードを2ndTableCache３１０から削除し（Ｓ１７０８）、1stV３０８のポインタのデータ項目に"Not  cached"を設定する（Ｓ１７０９）。そして、処理部は、動作を終了する。対象リージョンのレコードを2ndTableCache３１０から削除しないように設定されている場合には（Ｓ１７０７、Ｎｏ）、処理部は、Ｓ１７０８およびＳ１７０９の処理をスキップする。
【００９６】
図２６は、LUTガベージコレクションを説明するフローチャートである。まず、処理部は、LUTアクティブブロックリスト３０３を参照することによって、LUTアクティブブロックリスト３０３に記述されているアクティブブロックのうち最も古いアクティブブロックを特定し、特定したアクティブブロックをソースブロックとして設定する（Ｓ１８０１）。最も古いとは、LUTアクティブブロックリスト３０３に追加されたタイミングが最も古いことをいう。処理部は、ソースブロックの先頭の第３アドレスを着目位置として設定する（Ｓ１８０２）。処理部は、逆引きテーブル３１１を参照することによって、着目位置に記録されているレコードのリージョン番号を取得する（Ｓ１８０３）。処理部は、Ｓ１８０３の処理によって取得されたリージョン番号はテーブル長設定値３０６に記述されたテーブル長「L」未満であるか否かを判定する（Ｓ１８０４）。
【００９７】
リージョン番号が「Ｌ」未満である場合（Ｓ１８０４、Ｙｅｓ）、処理部は、1stNV３０９を参照することによって、Ｓ１８０３の処理によって取得されたリージョン番号に対応するポインタを取得する（Ｓ１８０５）。処理部は、Ｓ１８０５の処理によって取得されたポインタが、着目位置を示しているか否かを判定する（Ｓ１８０６）。Ｓ１８０５の処理によって取得されたポインタが、着目位置を示している場合には（Ｓ１８０６、Ｙｅｓ）、処理部は、着目位置に記録されたレコードを有効レコードとして判定する（Ｓ１８０７）。Ｓ１８０３の処理によって取得されたリージョン番号が「Ｌ」未満ではない場合（Ｓ１８０４、Ｎｏ）、または、Ｓ１８０５の処理によって取得されたポインタが、着目位置を示していない場合（Ｓ１８０６、Ｎｏ）、処理部は、着目位置に記録されたレコードを無効レコードとして判定する（Ｓ１８０８）。
【００９８】
Ｓ１８０７またはＳ１８０８の処理の後、処理部は、ソースブロックに記録されている全レコードについて有効レコードであるか無効レコードであるかの判定処理が実行されたか否かを判定する（Ｓ１８０９）。ソースブロックに記録されている何れかのレコードについて有効レコードであるか無効レコードであるかの判定処理が実行されていない場合（Ｓ１８０９、Ｎｏ）、処理部は、次のレコードが格納されている位置を新たな着目位置として設定し（Ｓ１８１０）、Ｓ１８０３の処理を再び実行する。ソースブロックに記録されている全レコードについて有効レコードであるか無効レコードであるかの判定処理が実行された場合（Ｓ１８０９、Ｙｅｓ）、処理部は、全ての有効レコードをソースブロックからデスティネーションブロックにコピーする（Ｓ１８１１）。そして、処理部は、2ndTable２０４における有効レコードのコピーに応じて、1stNV３０９に記録されているポインタの更新（Ｓ１８１２）、逆引きテーブル３１１の更新（Ｓ１８１３）、およびLUTログ２０２への内容変更ログ２０２ａの追加（Ｓ１８１４）を実行する。
【００９９】
続いて、処理部は、ソースブロックをフリーブロックプールに追加し（Ｓ１８１５）、ソースブロックをLUTブロック領域２９から削除する（Ｓ１８１６）。Ｓ１８１６の処理においては、具体的には、処理部は、LUTブロック情報３０２およびLUTアクティブブロックリスト３０３からソースブロックにかかるレコードを削除する。
【０１００】
続いて、処理部は、LUTアクティブブロックの数またはLUTブロック数設定値３１４が、前回のＳ１８１７の処理の実行後から変化したか否かを判定する（Ｓ１８１７）。LUTアクティブブロックの数およびLUTブロック数設定値３１４の何れかが変化した場合（Ｓ１８１７、Ｙｅｓ）、処理部は、LUTアクティブブロックの数をLUTブロック数設定値３１４から減算して得られる値に基づいてLUTギア比の設定値を調整し（Ｓ１８１８）、Ｓ１８０１の処理を再び実行する。処理部は、LUTギア比がLUTギア比の設定値に一致するように、LUTガベージコレクションの実行を制御する。LUTアクティブブロックの数およびLUTブロック数設定値３１４の何れも変化していない場合（Ｓ１８１７、Ｎｏ）、処理部は、Ｓ１８１８の処理をスキップする。
【０１０１】
なお、ここでは、処理部はソースブロックに含まれる全ての有効レコードをデスティネーションブロックにコピーする、として説明した。処理部は、有効レコードと判定されたレコードのリージョンがキャッシュされている場合には、2ndTableCache３１０にキャッシュされているレコードをデスティネーションブロックにコピーしてもよい。
【０１０２】
図２７は、ユーザガベージコレクションを説明するフローチャートである。処理部は、メモリシステム１の制御中に、ユーザガベージコレクションを断続的に実行する。処理部は、ギア比がギア比情報３１３から求まる設定値と等しくなるように、ユーザガベージコレクションの実行を制御する。また、処理部は、フリーブロック数および表記容量に基づいてギア比の設定値を動的に制御する。
【０１０３】
まず、処理部は、第１クラスタカウンタ３０４を参照することによって、１以上のアクティブブロックのうち有効クラスタ数が第１クラスタカウンタ３０４を参照した時点で最小である論理ブロックを特定し、特定した論理ブロックをソースブロックとして設定する（Ｓ１９０１）。処理部は、ソースブロックの先頭に位置するクラスタを着目クラスタとして設定する（Ｓ１９０２）。
【０１０４】
続いて、処理部は、ユーザログ２０３を参照することによって、着目クラスタに対応する第２アドレスを取得する（Ｓ１９０３）。処理部は、Ｓ１９０３の処理によって取得した第２アドレスについて、アドレス解決処理を実行する（Ｓ１９０４）。アドレス解決処理によって「無効」または「UNMAP」が得られた場合には、処理部は、後述のＳ１９０７の処理を実行する。
【０１０５】
アドレス解決処理によって第３アドレスが得られた場合には、その第３アドレスが着目クラスタの位置を示しているか否かを判定する（Ｓ１９０５）。アドレス解決処理によって得られた第３アドレスが着目クラスタの位置を示している場合（Ｓ１９０５、Ｙｅｓ）、処理部は、着目クラスタを有効クラスタとして判定する（Ｓ１９０６）。Ｓ１９０４の処理によって得られた第３アドレスが着目クラスタの位置を示していない場合（Ｓ１９０５、Ｎｏ）、処理部は、着目クラスタを無効クラスタとして判定する（Ｓ１９０７）。Ｓ１９０６またはＳ１９０７の処理の後、処理部は、未だ着目クラスタとして設定されていないクラスタがソースブロックに存在するか否かを判定する（Ｓ１９０８）。未だ着目クラスタとして設定されていないクラスタがソースブロックに存在する場合（Ｓ１９０８、Ｙｅｓ）、処理部は、ソースブロックから未だ着目クラスタとして設定されていないクラスタを選択し、選択されたクラスタを新たな着目クラスタとして設定する（Ｓ１９０９）。Ｓ１９０９の処理の後、処理部は、Ｓ１９０３の処理を実行する。
【０１０６】
未だ着目クラスタとして設定されていないクラスタがソースブロックに存在しない場合（Ｓ１９０８、Ｎｏ）、処理部は、全ての有効クラスタをソースブロックからデスティネーションブロックにコピーする（Ｓ１９１０）。処理部は、コピーされた全ての有効クラスタについてアドレス更新処理を実行する（Ｓ１９１１）。処理部は、ソースブロックをフリーブロックプールに追加する（Ｓ１９１２）。
【０１０７】
続いて、処理部は、フリーブロック数および表記容量のうちの何れかの変更が行われたか否かを判定する（Ｓ１９１３）。フリーブロック数および表記容量のうちの何れかが変更された場合（Ｓ１９１３、Ｙｅｓ）、処理部は、フリーブロック数および表記容量と、ギア比情報３１３と、に基づいてギア比の設定値を調整し（Ｓ１９１４）、Ｓ１９０１の処理を再び実行する。フリーブロック数および表記容量のうちの何れも変更されていない場合（Ｓ１９１３、Ｎｏ）、処理部は、Ｓ１９１４の処理をスキップする。
【０１０８】
図２８は、表記容量を削減する処理（以降、単に削減処理）を説明するフローチャートである。なお、ここでは、表記容量の削減の際には、第１アドレスの空間の末尾からリージョン単位で記憶領域が順番に削除され、表記容量の増加の際には、第１アドレスの空間の末尾にリージョン単位で記憶領域が追加されることとする。また、説明を簡単にするために、ここでは、１つのリージョンのサイズだけ表記容量を削減する処理を説明する。
【０１０９】
処理部は、ホスト２から表記容量削減要求を受信すると（Ｓ２００１）、削除対象のリージョンを特定する（Ｓ２００２）。図２８の説明において、Ｓ２００２の処理によって特定された削除対象のリージョンを、対象リージョンと表記する。
【０１１０】
続いて、処理部は、1stNV３０９を参照することによって、対象リージョンについて第１フラグが立っているか否かを判定する（Ｓ２００３）。対象リージョンについて第１フラグが立っていない場合（Ｓ２００３、Ｎｏ）、処理部は、1stV３０８を参照することによって、対象リージョンがキャッシュされているか否かを判定する（Ｓ２００４）。対象リージョンがキャッシュされていない場合（Ｓ２００４、Ｎｏ）、処理部は、1stNV３０９を参照することによって、対象リージョンのレコードのNANDメモリ２０上における格納位置を示すポインタを取得する（Ｓ２００５）。そして、処理部は、対象リージョンのレコードを、取得したポインタが示す位置から2ndTableCache３１０に読み出す（Ｓ２００６）。処理部は、Ｓ２００６の処理による2ndTableCache３１０の更新に応じて、対象リージョンのレコードがキャッシュされている位置を示すポインタを1stV３０８に記録する（Ｓ２００７）。
【０１１１】
対象リージョンがキャッシュされている場合（Ｓ２００４、Ｙｅｓ）、または、Ｓ２００７の処理の後、処理部は、UNMAP予約テーブル３０７を参照することによって、対象リージョンについて第２フラグが立っているか否かを判定する（Ｓ２００８）。対象リージョンについて第２フラグが立っている場合（Ｓ２００８、Ｙｅｓ）、処理部は、対象リージョンに対してリージョンUNMAP処理を実行する（Ｓ２００９）。
【０１１２】
対象リージョンについて第２フラグが立っていない場合（Ｓ２００８、Ｎｏ）、2ndTableCache３１０を参照することによって、対象リージョン内に１以上の非UNMAP状態のクラスタが存在するか否かを判定する（Ｓ２０１０）。対象リージョン内に１以上の非UNMAP状態のクラスタが存在する場合（Ｓ２０１０、Ｙｅｓ）、処理部は、非UNMAP状態のクラスタの存在をホスト２に通知する（Ｓ２０１１）。
【０１１３】
Ｓ２０１１の処理の後、処理部は、ホスト２から破棄許可の受信を待ち受ける。処理部は、破棄許可を受信した場合（Ｓ２０１２、Ｙｅｓ）、処理部は、Ｓ２０１３〜Ｓ２０１７においてＳ１４０１〜Ｓ１４０５の処理と同様の処理を実行することによって、対象リージョン内の全てのクラスタの状態をUNMAP状態に設定する。
【０１１４】
対象リージョンについて第１フラグが立っている場合（Ｓ２００３、Ｙｅｓ）、または、Ｓ２００９の処理の後、または、対象リージョン内に存在するクラスタの全てがUNMAP状態である場合（Ｓ２０１０、Ｎｏ）、または、対象リージョン内に存在するクラスタの全てがUNMAP状態である場合（Ｓ２０１３、Ｎｏ）、処理部は、対象リージョンのサイズだけ表記容量を小さくするように表記容量設定値３０５を更新し（Ｓ２０１８）、ホスト２に削減完了を通知する（Ｓ２０１９）。
【０１１５】
また、処理部は、テーブル長設定値３０６を更新する（Ｓ２０２０）。Ｓ２０２０の処理においては、１つのレコード分だけ値が小さくなるようにテーブル長設定値３０６を更新する。この処理によって、1stV３０８および1stNV３０９に記録されている対象リージョンのレコード（即ち各テーブルの末尾に記録されているレコード）が管理対象から削除される。なお、ここでは、1stV３０８または1stNV３０９に関し、管理対象の「管理」は、1stV３０８または1stNV３０９に対し、更新すること、または参照したりすること、を少なくとも含む。
【０１１６】
続いて、処理部は、LUTブロック数設定値３１４を更新する（Ｓ２０２１）。Ｓ２０２１の処理においては、処理部は、LUTブロック数設定値３１４の値を、更新前の値よりも１つのリージョンのサイズだけ小さくする。Ｓ２０２１の処理の後、処理部は、動作を終了する。
【０１１７】
ホスト２から破棄許可の受信がない場合には（Ｓ２０１２、Ｎｏ）、処理部は、動作を終了する。
【０１１８】
なお、ここでは１つのリージョンのサイズだけ表記容量を削減する処理を説明したが、複数のリージョンのサイズだけ表記容量の削減が要求された場合には、例えば、Ｓ２００２〜Ｓ２０２１の処理をリージョン単位で繰り返す。
【０１１９】
図２９は、表記容量を増加させる処理（以降、増加処理）を説明するフローチャートである。説明を簡単にするために、ここでは、１つのリージョンのサイズだけ表記容量を増加させる処理を説明する。
【０１２０】
処理部は、ホスト２から表記容量増加要求を受信すると（Ｓ２１０１）、追加対象のリージョンを特定する（Ｓ２１０２）。図２９の説明において、Ｓ２１０２の処理によって特定された追加対象のリージョンを、対象リージョンと表記する。
【０１２１】
処理部は、テーブル長設定値３０６を更新する（Ｓ２１０３）。Ｓ２１０３の処理においては、１つのレコード分だけ値が大きくなるようにテーブル長設定値３０６を更新する。この処理によって、1stV３０８の末尾および1stNV３０９の末尾に対象リージョンためのレコードが管理対象として追加される。追加された各レコードのデータ項目は空である。例えば、追加された各レコードには、初期値が記録されている。初期値は、無効な値であることを示すマジックナンバーである。処理部は、1stNV３０９に追加された対象リージョンのレコードに第１フラグを立てる（Ｓ２１０４）。処理部は、LUTログ２０２にサイズ変更ログ２０２ｂを追加する（Ｓ２１０５）。
【０１２２】
続いて、処理部は、LUTブロック数設定値３１４を更新する（Ｓ２１０６）。Ｓ２１０６の処理においては、処理部は、LUTブロック数設定値３１４の値を、更新前の値よりも１つのリージョンのサイズだけ大きくする。処理部は、ホスト２に増加完了を通知する（Ｓ２１０７）。Ｓ２１０７の処理の後、処理部は、動作を終了する。
【０１２３】
なお、ここでは１つのリージョンのサイズだけ表記容量を増加する処理を説明したが、複数のリージョンのサイズだけ表記容量の増加が要求された場合には、例えば、処理部は、追加対象の全てのリージョンについて一括してＳ２１０２〜Ｓ２１０６の各処理を実行する。その後、処理部は、一度だけＳ２１０７の処理を実行する。
【０１２４】
以上述べたように、第１の実施形態によれば、メモリシステム１は、ユーザデータ２０５を記憶するavailable領域２８を備えている。available領域２８のサイズ（第２サイズ）は、表記容量（第１サイズ）よりも大きい。処理部は、ホスト２からの要求（表記容量削減要求、表記容量増加要求）に応じて表記容量を、論理アドレス空間のうちの少なくとも一部によって示されるユーザデータ２０５をavailable領域２８に保持したまま、変更することができる。メモリシステム１の表記容量を動的に変更できるので、メモリシステム１の利便性を高めることができる。
【０１２５】
より詳しくは、図２８に示す削減処理によれば、論理アドレス空間のうちの削除対象ではないリージョンについては、第２アドレスと第３アドレスとの対応関係に対する変更は行われない。従って、処理部は、論理アドレス空間のうちの削除対象ではないリージョンが指定されて格納されたユーザデータ２０５を、有効な状態に維持したまま削減処理を実行する。これに対し、削除対象のリージョンが指定されて格納されたユーザデータ２０５が存在する場合、処理部は、破棄許可の受信の後（Ｓ２０１２、Ｙｅｓ）、削除対象のリージョンが指定されて格納されたユーザデータ２０５を、Ｓ２０１３〜Ｓ２０１７の処理によってUNMAP状態に設定する。さらに、処理部は、テーブル長設定値３０６の更新（Ｓ２０２０）によって、削除対象のリージョンを1stV３０８および1stNV３０９による管理対象から削除する。処理部は、管理対象から削除されたリージョンについてアドレス解決処理を実行した場合、「無効」という結果を取得する（Ｓ１５１０）。ここでは、論理アドレス空間に関し、管理対象の「管理」とは、論理アドレス空間に対し、ユーザデータ２０５を読み出すこと、ユーザデータ２０５を書き込むこと、またはUNMAP処理を実行すること、を少なくとも含む。データに関し、管理対象の「管理」とは、データが格納されている位置に対し、読み出すこと、書き込むこと、またはUNMAP処理を実行すること、を少なくとも含む。処理部は、ユーザガベージコレクション（図２７）においては、アドレス解決処理（Ｓ１９０４）によって「無効」を取得するため、管理対象から削除されたリージョンが指定されて格納されたユーザデータ２０５の状態を、無効な状態であると判定する（Ｓ１９０７）。処理部は、無効な状態のユーザデータ２０５をソースブロックからデスティネーションブロックにコピーすることなくソースブロックのイレースを行う。このように、処理部は、論理アドレス空間のうちの削除対象ではないリージョンと削除対象のリージョンとの夫々に有効なユーザデータ２０５が存在する場合には、削除対象ではないリージョンが指定されて格納されたユーザデータ２０５の削除は行わず、削除対象のリージョンが指定されて格納されたユーザデータ２０５を破棄許可の受信後に削除する。即ち、処理部は、論理アドレス空間のうちの少なくとも一部によって示されるユーザデータ２０５を有効なデータとしてavailable領域２８に保持したまま、表記容量を削減することができる。言い換えると、処理部は、論理アドレス空間のうちの少なくとも一部のデータ（有効なデータ）の管理を継続しながら、表記容量を削減することができる。さらに言い換えると、処理部は、論理アドレス空間内の少なくとも一部のデータを有効な状態に保ったまま、表記容量を削減することができる。
【０１２６】
また、図２９に示す増加処理によれば、論理アドレス空間のうちの既存のリージョンについても、第２アドレスと第３アドレスとの対応関係に対する変更は行われない。したがって、処理部は、論理アドレス空間のうちの既存のリージョンが指定されて格納されたユーザデータ２０５を有効な状態に維持したまま増加処理を実行する。即ち、処理部は、論理アドレス空間のうちの既存のリージョンが指定されて格納されたユーザデータ２０５をavailable領域２８に保持したまま、表記容量を増加させることができる。
【０１２７】
処理部は、削除対象のリージョンが指定されて格納されたユーザデータ２０５が存在する場合、レコードの削除を行う前にホスト２に警告する。これにより、有効なユーザデータ２０５が削減処理の実行によってホスト２に無断で削除される事象の発生を防止することが可能となる。
【０１２８】
なお、処理部は、削除対象のリージョンが指定されて格納されたユーザデータ２０５が存在する場合、ホスト２に警告を行わないで処理を中断する、ように構成されてもよい。また、処理部は、削除対象のリージョンが指定されて格納されたユーザデータ２０５が存在する場合、ホスト２に警告を行い、破棄許可を受信するか否かに関わらず削減処理を進める、ように構成されてもよい。また、処理部は、削減処理の後にホスト２への警告を行ってもよい。
【０１２９】
メモリシステム１は、１階層目のテーブル（1stV３０８および1stNV３０９）と２階層目のテーブル（2ndTableCache３１０および2ndTable２０４）とを、第２アドレスと第３アドレスとを対応付ける対応情報として記憶する。処理部は、ホスト２からの要求（表記容量削減要求、表記容量増加要求）に応じて、対応情報に具備される第２アドレスと第３アドレスとを対応付けるレコードの数を変更する。
【０１３０】
より詳しくは、処理部は、メモリシステム１が表記容量削減要求を受信した場合には、削除対象のリージョンについて、２階層目のテーブルのレコードに全クラスタについて「UNMAP」を設定する（S２００３〜S２０１７）。そして、処理部は、削除対象のリージョンについて、１階層目のテーブルからレコードを削除する（Ｓ２０２０）。処理部は、２階層目のテーブルにおける削除対象のリージョンのレコードは、１階層目のテーブルからポイントされないため、処理部は、LUTガベージコレクションにおいて、2ndTable２０４における削除対象のリージョンのレコードを無効レコードと判定する（S１８０８）。処理部は、無効レコードをソースブロックからデスティネーションブロックにコピーすることなくソースブロックのイレースを行う。なお、2ndTableCache３１０における削除対象のリージョンのレコードは、不揮発化の対象に設定されてもよいし不揮発化の対象に設定されなくてもよい。2ndTableCache３１０における削除対象のリージョンのレコードが不揮発化される場合においても、不揮発化後、LUTガベージコレクションによって当該レコードは削除される。このように、２階層目のテーブルにおける削除対象のレコードも、１階層目のテーブルからのレコードの削除に伴って、削除される。
【０１３１】
また、処理部は、メモリシステム１が表記容量増加要求を受信した場合には、1stV３０８および1stNV３０９にレコードを追加する（S２１０３）。そして、処理部は、1stNV３０９に追加したレコードに第１フラグを立てる（S２１０４）。なお、処理部は、第２階層目のテーブルに関し、追加対象のリージョン、のレコードを、アドレス更新処理の際に2ndTableCache３１０に生成し（S１６０３）、生成したレコードを不揮発化の対象に設定する（S１６１６）。したがって、処理部は、表記容量増加要求を受信した場合には、第１階層目のテーブルおよび第２階層目のテーブルの夫々にレコードを追加する。
【０１３２】
なお、追加対象のリージョン、のレコードを、第２階層目のテーブルに追加する処理は、任意のタイミングで実行可能である。以上の説明においては、処理部は、第１フラグが立てられた状態のリージョンについてアドレス解決処理を行うときに、対応するレコードを2ndTableCache３１０に生成しないで「UNMAP」の結果を取得する（S１５１１）として説明した。処理部は、アドレス解決処理においても、アドレス更新処理におけるS１６０３の処理と同様の処理を行うことで、対応するレコードを2ndTableCache３１０に生成してもよい。
【０１３３】
また、以上の説明においては、第１階層目のテーブルのレコード数と第２階層目のテーブルのレコード数との両方を変更するものとして説明したが、どちらか一方のテーブルのレコード数のみ変更してもよい。即ち、メモリシステム１が対応情報として記憶する情報のうち、論理アドレスおよび物理アドレスのうちの少なくとも一つを含む情報が、本実施形態において数の変更の対象であるレコードの概念の範疇に含まれる。
【０１３４】
また、処理部は、アドレス更新処理を実行する場合、当該アドレス更新処理内の処理として、第２階層目のテーブルのレコードを生成し、第１フラグを下ろす（S１６０５）。なお、処理部は、アドレス解決処理を実行する場合に、第２階層目のテーブルのレコードを生成してもよい。
【０１３５】
また、処理部は、各クラスタについて、UNMAP状態であるか非UNMAP状態であるかを管理する。ここでは、処理部は、各クラスタがUNMAP状態であるか非UNMAP状態であるかの管理を、2ndTable２０４の各データ項目に「UNMAP」または第３アドレスの何れかを設定することによって実現する。処理部は、各クラスタがUNMAP状態であるか非UNMAP状態であるかを、2ndTable２０４とは異なる情報に記録してもよい。
【０１３６】
また、処理部は、メモリシステム１の制御中に、ユーザガベージコレクションを断続的に実行する。処理部は、ギア比がギア比情報３１３から求まる設定値と等しくなるように、ユーザガベージコレクションの実行を制御する。また、処理部は、フリーブロック数および表記容量のうちの少なくとも一つに基づいてギア比の設定値を、動的に制御する。具体的には、処理部は、表記容量設定値３０５およびフリーブロック数を監視する（Ｓ１９１３）。処理部は、表記容量設定値３０５およびフリーブロック数を、図１７および図１８によって説明されるギア比情報３１３に適用することによって、ギア比の設定値を演算し、適用する（Ｓ１９１４）。そして、処理部は、ギア比が設定値に等しくなるように、ユーザガベージコレクションの実行を調整する。
【０１３７】
フリーブロック数とギア比の設定値との関係は、任意に規定される。例えば、フリーブロック数が第１値である場合には、フリーブロック数が第１値よりも大きい第２値である場合に比べて、ギア比の設定値が大きくなるように、フリーブロック数とギア比の設定値との関係が予め規定される。
【０１３８】
また、表記容量とギア比の設定値との関係は、任意に規定される。例えば、表記容量が第３値である場合には、表記容量が第３値よりも大きい第４値である場合に比べ、ギア比の設定値が大きくなるように、表記容量とギア比の設定値との関係が予め規定される。または、余裕率が第５値である場合には、余裕率が第５値よりも大きい第６値である場合に比べ、ギア比の設定値が大きくなるように、余裕率とギア比の設定値との関係が予め規定される。なお、余裕率とは、余裕容量を表記容量で除算して得られる値である。
【０１３９】
なお、処理部は、LUTガベージコレクションに関してもギア比の制御を行ってもよい。
【０１４０】
また、処理部は、ホスト２からのUNMAP要求に応じたリージョン単位のUNMAP処理を、UNMAP要求を受信した後に直ちに開始せずに、アドレス解決処理、アドレス更新処理、削減処理、または、ユーザガベージコレクション、の何れかの処理の一環として実行する、として説明した。処理部は、ホスト２からのUNMAP要求に応じたリージョン単位のUNMAP処理を、UNMAP要求を受信した後に直ちに実行してもよい。
【０１４１】
また、1stNV３０９はパワーオンシーケンスにおいて復元される、として説明した。1stNV３０９は、パワーオフシーケンスにおいてRAM３０からシステム領域２７に退避され、パワーオンシーケンスにおいてシステム領域２７からRAM３０にロードされてもよい。その場合には、LUTログ２０２の管理は不要である。
【０１４２】
また、処理部は増加処理時にサイズ変更ログ２０２ｂを記録し、削減処理時にサイズ変更ログ２０２ｂを記録しない、として説明したが、処理部は増加処理時および削減処理時の何れの場合においてもサイズ変更ログ２０２ｂを記録してもよい。処理部が増加処理時および削減処理時の何れの場合においてもサイズ変更ログ２０２ｂを記録する場合には、LUTログ２０２のみに基づいて1stNV３０９の復元が可能となるので、パワーオフシーケンスにおけるテーブル長設定値３０６の退避は不要である。
【０１４３】
（第２の実施形態）
図３０及び図３１は、第２の実施形態の削減処理を説明するフローチャートである。第２の実施形態においては、削減処理は、ホスト２に対する応答処理（フォアグラウンド処理）と、応答処理の後の内部処理（バックグラウンド処理）とに分割される。図３０はフォアグラウンド処理を説明するフローチャートであり、図３１はバックグラウンド処理を説明するフローチャートである。ここでは、説明を簡単にするために、１つのリージョンのサイズだけ表記容量を削減する処理を説明する。
【０１４４】
処理部は、ホスト２から表記容量削減要求を受信すると（Ｓ２２０１）、削除対象のリージョンを特定する（Ｓ２２０２）。図３０および図３１の説明においては、Ｓ２２０２の処理によって特定された削除対象のリージョンを、対象リージョンと表記する。
【０１４５】
続いて、処理部は、1stNV３０９およびUNMAP予約テーブル３０７を参照することによって、対象リージョンについて第１フラグおよび第２フラグの何れかが立っているか否かを判定する（Ｓ２２０３）。対象リージョンについて第１フラグおよび第２フラグの何れも立っていない場合（Ｓ２２０３、Ｎｏ）、処理部は、対象リージョンについて第２フラグを立て（Ｓ２２０４）、表記容量設定値３０５を更新する（Ｓ２２０５）。そして、処理部は、削減完了をホスト２に通知する（Ｓ２２０６）。Ｓ２２０６の処理の後、処理部は、フォアグラウンド処理を終了する。対象リージョンについて第１フラグおよび第２フラグの何れかが立っている場合（Ｓ２２０３、Ｙｅｓ）、処理部は、Ｓ２２０４の処理をスキップする。
【０１４６】
バックグラウンド処理においては、処理部は、UNMAP予約テーブル３０７を参照することによって、対象リージョンについて第２フラグが立っているか否かを判定する（Ｓ２３０１）。対象リージョンについて第２フラグが立っている場合（Ｓ２３０１、Ｙｅｓ）、処理部は、1stV３０８を参照することによって、対象リージョンがキャッシュされているか否かを判定する（Ｓ２３０２）。対象リージョンがキャッシュされていない場合（Ｓ２３０２、Ｎｏ）、処理部は、1stNV３０９を参照することによって、対象リージョンのレコードのNANDメモリ２０上における格納位置を示すポインタを取得する（Ｓ２３０３）。そして、処理部は、対象リージョンのレコードを、取得したポインタが示す位置から2ndTableCache３１０に読み出す（Ｓ２３０４）。処理部は、Ｓ２３０４の処理による2ndTableCache３１０の更新に応じて、1stV３０８に対象リージョンのレコードがキャッシュされている位置を示すポインタを記録する（Ｓ２３０５）。
【０１４７】
対象リージョンがキャッシュされている場合（Ｓ２３０２、Ｙｅｓ）、または、Ｓ２３０５の処理の後、処理部は、対象リージョンに対してリージョンUNMAP処理を実行する（Ｓ２３０６）。
【０１４８】
対象リージョンについて第２フラグが立っていない場合（Ｓ２３０１、Ｎｏ）、または、Ｓ２３０６の処理の後、処理部は、テーブル長設定値３０６を更新する（Ｓ２３０７）。そして、処理部は、LUTブロック数設定値３１４を更新し（Ｓ２３０８）、バックグラウンド処理を終了する。
【０１４９】
このように、第２の実施形態においては、メモリシステム１が表記容量削減要求を受信した場合、処理部は、削除対象のリージョンに非UNMAP状態のクラスタが存在するか否かを判定する前に、削除対象のリージョンに関して第２フラグを立て、削除完了をホスト２に通知する。処理部は、削除完了の通知後、第２フラグが立てられた状態の削除対象のリージョンについて、UNMAP処理を実行し、その後、削除対象のリージョンのレコードの削除を実行する。第２の実施形態によれば、メモリシステム１は、削除完了の通知を、第１の実施形態に比べて早く送信することができる。
【０１５０】
（第３の実施形態）
第３の実施形態においては、処理部は、第１アドレスの空間における所定サイズの記憶領域毎に、非UNMAP状態のクラスタ数を管理する。非UNMAP状態のクラスタ数の管理単位は、リージョン単位であってもよいしリージョン単位でなくてもよい。ここでは一例として、処理部は、非UNMAP状態のクラスタ数を１０２４個のリージョンからなる領域（リージョングループ）毎に管理する。
【０１５１】
処理部は、第２クラスタカウンタを管理する。図３２は、第２クラスタカウンタのデータ構造例を示す図である。図示するように、第２クラスタカウンタ３１５は、リージョングループ毎に、非UNMAP状態のクラスタ数が記録されている。処理部は、第２クラスタカウンタ３１５を、RAM３０に格納し、RAM３０に格納された第２クラスタカウンタ３１５を参照したり更新したりする。処理部は、第２クラスタカウンタ３１５を、パワーオフシーケンスにおいてRAM３０からシステム領域２７に退避し、パワーオンシーケンスにおいてシステム領域２７からRAM３０にロードする。
【０１５２】
処理部は、第２クラスタカウンタ３１５を次に説明するように更新する。処理部は、2ndTableCache３１０において、UNMAP状態のクラスタに第３アドレスを設定する場合に、当該クラスタが属するリージョングループについて第２クラスタカウンタ３１５に記録されている値をインクリメントする。また、処理部は、2ndTableCache３１０において、第３アドレスが設定されたクラスタに「UNMAP」を設定する場合に、当該クラスタが属するリージョングループについて第２クラスタカウンタ３１５に記録されている値をデクリメントする。また、処理部は、2ndTableCache３１０において、第３アドレスが設定されたクラスタに別の第３アドレスを設定する場合に、第２クラスタカウンタ３１５の更新は行わない。また、処理部は、2ndTableCache３１０において、「UNMAP」が設定されたクラスタに「UNMAP」を設定した際に、第２クラスタカウンタ３１５の更新は行わない。
【０１５３】
処理部は、削減処理の際に第２クラスタカウンタ３１５を参照する。表記容量削減要求によってリージョングループ単位の削除が要求された場合、処理部は、第１フラグの確認（Ｓ２００３）を行う前に、第２クラスタカウンタ３１５を参照することによって、削除対象のリージョングループに非UNMAP状態のクラスタが存在するか否かを判定する。削除対象のリージョングループに非UNMAP状態のクラスタが存在しない場合には、第１フラグが立てられていない場合のクラスタ単位の確認（Ｓ２０１０）を行うことなく削除対象のリージョングループに非UNMAP状態のクラスタが存在しないことの確認が完了するので、第１の実施形態よりも削除対象のリージョングループに非UNMAP状態のクラスタが存在しないことの確認が高速に実行される。
【０１５４】
なお、処理部は、リージョン単位またはクラスタ単位の削除が要求された場合であっても、第２クラスタカウンタ３１５を参照することによって削除対象のリージョングループに非UNMAP状態のクラスタが存在しないことの確認を行ってもよい。
【０１５５】
（第４の実施形態）
図３３は、メモリシステム１の実装例を示す図である。メモリシステム１は、例えばサーバシステム１０００に実装される。サーバシステム１０００は、ディスクアレイ２０００とラックマウントサーバ３０００とが通信インタフェース４０００によって接続されて構成される。通信インタフェース４０００の規格としては任意の規格が採用可能である。ラックマウントサーバ３０００は、サーバラックに１以上のホスト２がマウントされて構成される。複数のホスト２は、通信インタフェース４０００を介してディスクアレイ２０００にアクセスすることができる。
【０１５６】
また、ディスクアレイ２０００は、サーバラックに１以上のメモリシステム１と１以上のハードディスクユニット４とがマウントされて構成される。各メモリシステム１は、各ホスト２からのリードコマンドを実行することができる。また、各メモリシステム１は、第１〜第３の実施形態が採用された構成を有している。これにより、各メモリシステム１は、複数のホスト２の何れかから表記容量を変更する要求が発行された場合、動的に表記容量を変更することが可能である。
【０１５７】
なお、ディスクアレイ２０００においては、例えば、各メモリシステム１は、１以上のハードディスクユニット４のキャッシュとして使用されてもよい。ディスクアレイ２０００は、１以上のハードディスクユニット４にＲＡＩＤを構築するストレージコントローラユニットがマウントされてもよい。
【０１５８】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１５９】
１  メモリシステム、２  ホスト、３  通信路、１０  メモリコントローラ、２０  NANDメモリ、２７  システム領域、２８  available領域、２９  LUTブロック領域、２０２  LUTログ、２０２ａ  内容変更ログ、２０２ｂ  サイズ変更ログ、２０３  ユーザログ、２０４  2ndTable、２０５  ユーザデータ、３０１  物理ブロック情報、３０２  LUTブロック情報、３０３  LUTアクティブブロックリスト、３０４  第１クラスタカウンタ、３０５  表記容量設定値、３０６  テーブル長設定値、３０７  UNMAP予約テーブル、３０８  1stV、３０９  1stNV、３１０  2ndTableCache、３１１  逆引きテーブル、３１２  ダーティリスト、３１３  ギア比情報、３１４  LUTブロック数設定値、３１５  第２クラスタカウンタ、１０００  サーバシステム、２０００  ディスクアレイ、３０００  ラックマウントサーバ。
【図１】
0006388345.tif 000002
【図２】
0006388345.tif 000003
【図３】
0006388345.tif 000004
【図４】
0006388345.tif 000005
【図５】
0006388345.tif 000006
【図６】
0006388345.tif 000007
【図７】
0006388345.tif 000008
【図８】
0006388345.tif 000009
【図９】
0006388345.tif 000010
【図１０】
0006388345.tif 000011
【図１１】
0006388345.tif 000012
【図１２】
0006388345.tif 000013
【図１３】
0006388345.tif 000014
【図１４】
0006388345.tif 000015
【図１５】
0006388345.tif 000016
【図１６】
0006388345.tif 000017
【図１７】
0006388345.tif 000018
【図１８】
0006388345.tif 000019
【図１９】
0006388345.tif 000020
【図２０】
0006388345.tif 000021
【図２１】
0006388345.tif 000022
【図２２】
0006388345.tif 000023
【図２３】
0006388345.tif 000024
【図２４】
0006388345.tif 000025
【図２５】
0006388345.tif 000026
【図２６】
0006388345.tif 000027
【図２７】
0006388345.tif 000028
【図２８】
0006388345.tif 000029
【図２９】
0006388345.tif 000030
【図３０】
0006388345.tif 000031
【図３１】
0006388345.tif 000032
【図３２】
0006388345.tif 000033
【図３３】
0006388345.tif 000034