(57)【要約】      （修正有）【課題】利便性が高いメモリシステムを提供する。【解決手段】メモリシステム１のコントローラ１００は、ライトデータを不揮発化し、第１メモリ２００の論理変換テーブル２０２との差分を格納する差分テーブル３００を更新する。コントローラは、第１論理アドレス範囲の第１ライトデータを第１物理アドレス範囲に不揮発化した際、複数のエントリが第１エントリを含む場合、第１エントリの内容を更新する。第１エントリは、第２論理アドレス範囲と第２物理アドレス範囲との対応関係を記録し、第１論理アドレス範囲が第２論理アドレス範囲に後続し、かつ第１物理アドレス範囲が第２物理アドレス範囲に後続する、エントリである。コントローラは、複数のエントリが第１エントリを含まない場合、第２エントリに第１論理アドレス範囲と第１物理アドレス範囲との対応関係を記録する。第２エントリは複数のエントリのうちの新規に対応関係が記録可能なエントリである。【選択図】図１
2020113187.tif 000002
【特許請求の範囲】
【請求項１】
不揮発性の第１メモリであってホストから指定される位置情報である論理アドレスと前記第１メモリ内の位置情報である物理アドレスとの第１タイミングにおける対応関係を示す論物変換テーブルが格納される前記第１メモリと、
複数のエントリを有し、前記複数のエントリのそれぞれには前記論物変換テーブルと前記第１タイミングよりも後の第２タイミングにおける前記対応関係との差分である論理アドレス範囲と物理アドレス範囲との対応関係が記録され得るように構成された差分テーブルが格納される第２メモリと、
前記ホストからライトコマンドによって要求されたライトデータを不揮発化し、
前記ライトデータの不揮発化に応じて前記差分テーブルを更新し、
第１論理アドレス範囲の第１ライトデータを第１物理アドレス範囲に不揮発化した際、
前記複数のエントリが第１エントリを含む場合、前記第１エントリの内容を更新し、前記第１エントリは、第２論理アドレス範囲と第２物理アドレス範囲との対応関係が記録され、前記第１論理アドレス範囲が前記第２論理アドレス範囲に後続し、かつ前記第１物理アドレス範囲が前記第２物理アドレス範囲に後続する、エントリであり、
前記複数のエントリが前記第１エントリを含まない場合、第２エントリに前記第１論理アドレス範囲と第１物理アドレス範囲との対応関係を記録し、前記第２エントリは前記複数のエントリのうちの新規に対応関係が記録可能なエントリである、
コントローラと、
を備えるメモリシステム。
【請求項２】
前記複数のエントリのそれぞれに記録され得る対応関係は前記論理アドレス範囲または前記物理アドレス範囲の長さを示す長さ情報を含み、
前記コントローラは、前記第１エントリに記録された長さ情報を、前記第１論理アドレス範囲と前記第２論理アドレス範囲とを結合した範囲または前記第１物理アドレス範囲と前記第２物理アドレス範囲とを結合した範囲に対応した値で更新する、
請求項１に記載のメモリシステム。
【請求項３】
前記コントローラは、
最後に更新したエントリである第３エントリを記憶し、
前記第３エントリが前記第１エントリに該当するか否かを判定する、
請求項１に記載のメモリシステム。
【請求項４】
前記第３エントリには、第３論理アドレス範囲と第３物理アドレス範囲との対応関係が記録され、
前記コントローラは、
前記第３論理アドレス範囲および前記第３物理アドレス範囲のそれぞれの末尾に対応した末尾情報を記憶し、
前記第１論理アドレス範囲が前記第３論理アドレス範囲に後続し、かつ前記第１物理アドレス範囲が前記第３物理アドレス範囲に後続するか否かを、前記末尾情報に基づいて判定する、
請求項３に記載のメモリシステム。
【請求項５】
論理アドレス空間は複数の部分空間に分割され、
前記コントローラは、部分空間毎に前記第３エントリを記憶する、
請求項３に記載のメモリシステム。
【請求項６】
前記コントローラは、所定条件が満たされた場合に、前記複数のエントリのうちの１以上のエントリの内容を前記論物変換テーブルに反映させ、前記論物変換テーブルへの反映が完了した内容が記録されていた前記１以上のエントリを、新規に対応関係が記録され得る状態に設定する、
請求項１に記載のメモリシステム。
【請求項７】
前記論物変換テーブルは、それぞれが所定サイズの論理アドレス範囲に対応した複数のサブテーブルを備え、
前記コントローラは、
第３論理アドレス範囲に位置する第２ライトデータを第３物理アドレス範囲に不揮発化し、前記第３論理アドレス範囲が前記サブテーブルの境界に対応した第１論理アドレスを含む場合、
第４論理アドレス範囲にかかる対応関係と、第５論理アドレス範囲にかかる対応関係と、をそれぞれ異なるエントリに記録し、
前記第４論理アドレス範囲は前記第３論理アドレス範囲のうちの前記第１論理アドレスよりも前の範囲であり、
前記第５論理アドレス範囲は前記第３論理アドレス範囲のうちの前記第１論理アドレスよりも後の範囲である、
請求項６に記載のメモリシステム。
【請求項８】
前記コントローラは、前記１以上のエントリのそれぞれに対応したサブテーブルを特定し、前記特定したサブテーブルを前記第１メモリから読み出して更新し、更新後の前記サブテーブルを前記第１メモリに書き込む、
請求項７に記載のメモリシステム。
【請求項９】
不揮発性の第１メモリであってホストから指定される位置情報である論理アドレスと前記第１メモリ内の位置情報である物理アドレスとの第１タイミングにおける対応関係を示す論物変換テーブルが格納される前記第１メモリと、
複数のエントリを有し、前記複数のエントリのそれぞれには前記論物変換テーブルと前記第１タイミングよりも後の第２タイミングにおける前記対応関係との差分である論理アドレス範囲と物理アドレス範囲との対応関係が記録され得るように構成された差分テーブルが格納される第２メモリと、
前記ホストからライトコマンドによって要求されたライトデータの不揮発化を実行し、前記不揮発化に応じて前記ライトデータが関連付けられた論理アドレス範囲と前記ライトデータが不揮発化された先の物理アドレス範囲とを示す通知を生成する不揮発化装置と、
前記通知に応じて前記差分テーブルを更新する差分テーブル管理装置と、
を備え、
前記差分テーブル管理装置は、前記差分テーブルが第１エントリを含む場合、前記第１エントリを更新し、前記差分テーブルが前記第１エントリを含まない場合、第２エントリに第１論理アドレス範囲と第１物理アドレス範囲との対応関係を記録し、
前記第１論理アドレス範囲は、前記通知が示す論理アドレス範囲であり、
前記第１物理アドレス範囲は、前記通知が示す物理アドレス範囲であり、
前記第１エントリは、第２論理アドレス範囲と第２物理アドレス範囲との対応関係が記録され、前記第１論理アドレス範囲が前記第２論理アドレス範囲に後続し、かつ前記第１物理アドレス範囲が前記第２物理アドレス範囲に後続する、エントリであり、
前記第２エントリは、前記複数のエントリのうちの新規に対応関係が記録可能なエントリである、
メモリシステム。
【請求項１０】
それぞれ異なるライトコマンドによって要求された２以上のライトデータをバッファする第３メモリを備え、
前記不揮発化装置は、前記第３メモリにバッファされた前記２以上のライトデータを不揮発化し、不揮発化された前記２以上のライトデータのそれぞれ毎に前記通知を生成する、
請求項９に記載のメモリシステム。
【請求項１１】
前記論物変換テーブルは、それぞれが所定サイズの論理アドレス範囲に対応した複数のサブテーブルを備え、
前記不揮発化装置は、第３論理アドレス範囲に関連付けられた第１ライトデータを第３物理アドレス範囲に不揮発化し、前記第３論理アドレス範囲が前記所定サイズの論理アドレス範囲の境界に対応した第１論理アドレスを含む場合、前記第３論理アドレス範囲のうちの前記第１論理アドレスよりも前の範囲に対応した第１通知と、前記第３論理アドレス範囲のうちの前記第１論理アドレスよりも後の範囲に対応した第２通知と、を生成するとともに、前記第１通知にかかるエントリと前記第２通知にかかるエントリとを分ける要求を生成する、
請求項９に記載のメモリシステム。
【請求項１２】
前記不揮発化装置は、前記要求を前記第２通知に設定する、
請求項１１に記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、メモリシステムに関する。
【背景技術】
【０００２】
従来、ＳＳＤ（Solid  State  Drive）などのメモリシステムにおいては、ホストからアクセス先の指定に使用されるアドレス情報である論理アドレスと実際にデータが記録される物理的な位置を示すアドレス情報である物理アドレスとが異なるため、論理アドレスと物理アドレスとの対応関係を示す論物変換テーブル（Logical  Address  Physical  Address  Translation  Table）が使用される。
【０００３】
論物変換テーブルは、例えば、ＮＡＮＤ型フラッシュメモリなどの不揮発性メモリに保存される。しかしながら、ホストからの書き込み毎に論物変換テーブルにアクセスすると、処理速度またはＷＡＦ（Write  Amplification  Factor）の点で不利である。
【０００４】
よって、最近の書き込みによって更新された論理アドレスと物理アドレスとの対応関係を、論物変換テーブルの差分を集めた差分テーブルとして揮発性メモリに保持する方法が採用される場合がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１１−１８１８２号公報
【特許文献２】特開２０１３−１９６１１５号公報
【特許文献３】米国特許第８８１９３７５号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
一つの実施形態は、利便性が高いメモリシステムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
一つの実施形態によれば、メモリシステムは、第１メモリと、第２メモリと、コントローラとを備える。第１メモリは、不揮発性の第１メモリであって、論物変換テーブルが格納される。論物変換テーブルは、ホストから指定される位置情報である論理アドレスと第１メモリ内の位置情報である物理アドレスとの第１タイミングにおける対応関係を示す。第２メモリは、差分テーブルが格納される。差分テーブルは、複数のエントリを有し、複数のエントリのそれぞれには論物変換テーブルと第１タイミングよりも後の第２タイミングにおける対応関係との差分である論理アドレス範囲と物理アドレス範囲との対応関係が記録され得るように構成されている。コントローラは、ホストからライトコマンドによって要求されたライトデータを不揮発化し、ライトデータの不揮発化に応じて差分テーブルを更新する。コントローラは、第１論理アドレス範囲の第１ライトデータを第１物理アドレス範囲に不揮発化した際、複数のエントリが第１エントリを含む場合、第１エントリの内容を更新する。第１エントリは、第２論理アドレス範囲と第２物理アドレス範囲との対応関係が記録され、第１論理アドレス範囲が第２論理アドレス範囲に後続し、かつ第１物理アドレス範囲が第２物理アドレス範囲に後続する、エントリである。コントローラは、複数のエントリが第１エントリを含まない場合、第２エントリに第１論理アドレス範囲と第１物理アドレス範囲との対応関係を記録する。第２エントリは複数のエントリのうちの新規に対応関係が記録可能なエントリである。
【図面の簡単な説明】
【０００８】
【図１】図１は、第１の実施形態のメモリシステムの構成を示す模式的かつ例示的な図である。
【図２】図２は、第１の実施形態の１個のブロックの構成を示す模式的かつ例示的な回路図である。
【図３】図３は、第１の実施形態の差分テーブルのデータ構成を説明するための模式的かつ例示的な図である。
【図４】図４は、第１の実施形態の差分テーブルの１つのエントリに格納される内容を説明するための模式的かつ例示的な図である。
【図５】図５は、第１の実施形態の差分テーブル管理装置の動作の概要を説明するための模式的かつ例示的な図である。
【図６】図６は、第１の実施形態の差分テーブル管理装置の動作の概要を説明するための模式的かつ例示的な図である。
【図７】図７は、第１の実施形態のテーブル管理情報の構成を示す模式的かつ例示的な図である。
【図８】図８は、第１の実施形態のコマンド解析装置の動作を説明するための模式的かつ例示的なフローチャートである。
【図９】図９は、第１の実施形態のリード処理装置の動作を説明するための模式的かつ例示的なフローチャートである。
【図１０】図１０は、第１の実施形態の不揮発化装置の動作を説明するための模式的かつ例示的なフローチャートである。
【図１１】図１１は、第１の実施形態の差分テーブル管理装置による差分テーブルへの記録の動作を説明するための模式的かつ例示的なフローチャートである。
【図１２】図１２は、第１の実施形態の反映装置による反映処理の動作を説明するための模式的かつ例示的なフローチャートである。
【図１３】図１３は、第２の実施形態のライトデータの書き込み先を説明するための模式的かつ例示的な図である。
【図１４】図１４は、第２の実施形態のライトデータの書き込み先を説明するための模式的かつ例示的な図である。
【図１５】図１５は、第２の実施形態のテーブル管理情報の構成を説明するための模式的かつ例示的な図である。
【図１６】図１６は、第２の実施形態のテーブル管理情報に含まれるＮＥＸＴと複数のＣＵＲＲＥＮＴとの関係を説明するための模式的かつ例示的な図である。
【図１７】図１７は、第２の実施形態の差分テーブル管理装置による差分テーブルへの記録の動作を説明するための模式的かつ例示的なフローチャートである。
【図１８】図１８は、第３の実施形態のサブテーブルを説明するための模式的かつ例示的な図である。
【図１９】図１９は、第３の実施形態のライトコマンドとライトデータの位置およびサイズとの関係の一例を説明するための模式的かつ例示的な図である。
【図２０】図２０は、第３の実施形態の１回の不揮発化処理によって不揮発化された４つのライトデータの配置の例を説明するための模式的かつ例示的な図である。
【図２１】図２１は、第３の実施形態の不揮発化装置の動作を説明するための模式的かつ例示的なフローチャートである。
【図２２】図２２は、第３の実施形態にかかる通知生成処理の動作を説明するための模式的かつ例示的なフローチャートである。
【図２３】図２３は、第３の実施形態の差分テーブル管理装置による例外条件の判定の動作を説明するための模式的かつ例示的なフローチャートである。
【図２４】図２４は、第３の実施形態にかかる反映装置が実行する反映処理の具体例を説明するための模式的かつ例示的なフローチャートである。
【発明を実施するための形態】
【０００９】
以下に添付図面を参照して、実施形態にかかるメモリシステムを詳細に説明する。なお、これらの実施形態により本発明が限定されるものではない。
【００１０】
（第１の実施形態）
図１は、第１の実施形態のメモリシステムの構成を示す模式的かつ例示的な図である。
【００１１】
メモリシステム１は、ホスト２と接続される。接続の規格としては、任意の規格が採用され得る。ホスト２は、例えばパーソナルコンピュータ、携帯情報端末、またはサーバなどである。
【００１２】
メモリシステム１は、ホスト２からアクセスコマンド（リードコマンドおよびライトコマンド）を受け付けることができる。各アクセスコマンドは、アクセス先を示す論理アドレスを伴う。論理アドレスは、メモリシステム１がホスト２に提供する論理アドレス空間内の位置を示す位置情報である。メモリシステム１は、ライトコマンドとともに、書き込み対象のデータを受信する。以降、ホスト２から受信した書き込み対象のデータを、ライトデータと表記する。
【００１３】
メモリシステム１は、ＮＡＮＤ型のフラッシュメモリ（ＮＡＮＤメモリ）２００と、ホスト２とＮＡＮＤメモリ２００との間のデータ転送を実行するメモリコントローラ１００と、を備える。
【００１４】
ＮＡＮＤメモリ２００は、不揮発性のメモリであり、第１メモリの一例である。第１メモリとしては、任意の種類の不揮発性のメモリが採用され得る。
【００１５】
ＮＡＮＤメモリ２００は、複数のブロックからなるメモリセルアレイを備える。各ブロックに格納されているデータは、一括してイレースされる。各ブロックは、複数のページを備える。メモリセルアレイへのデータの書き込みおよびメモリセルアレイからのデータの読み出しは、ページ単位で実行される。
【００１６】
図２は、第１の実施形態の１個のブロックの構成を示す模式的かつ例示的な回路図である。図示するように、各ブロックは、Ｘ方向に沿って順に配列された（ｐ＋１）個のＮＡＮＤストリングを備えている（ｐ≧０）。（ｐ＋１）個のＮＡＮＤストリングにそれぞれ含まれる選択トランジスタＳＴ１は、ドレインがビット線ＢＬ０〜ＢＬｐに接続され、ゲートが選択ゲート線ＳＧＤに共通接続されている。また、選択トランジスタＳＴ２は、ソースがソース線ＳＬに共通接続され、ゲートが選択ゲート線ＳＧＳに共通接続されている。
【００１７】
各メモリセルＭＴは、半導体基板上に形成された積層ゲート構造を備えたＭＯＳＦＥＴ（Metal  Oxide  Semiconductor  Field  Effect  Transistor）から構成される。積層ゲート構造は、半導体基板上にトンネル酸化膜を介在して形成されたフローティングゲート、及びフローティングゲート上にゲート間絶縁膜を介在して形成された制御ゲート電極を含んでいる。フローティングゲートに蓄えられる電子の数に応じてメモリセルＭＴのしきい値電圧が変化する。メモリセルＭＴは、しきい値電圧の違いに応じてデータを記憶する。即ち、メモリセルＭＴは、フローティングゲートに、データに応じた量の電荷を保持する。
【００１８】
各ＮＡＮＤストリングにおいて、（ｑ＋１）個のメモリセルＭＴは、選択トランジスタＳＴ１のソースと選択トランジスタＳＴ２のドレインとの間に、それぞれの電流経路が直列接続されるように配置されている。そして、最もドレイン側に位置するメモリセルＭＴから順に、制御ゲート電極がワード線ＷＬ０〜ＷＬｑにそれぞれ接続されている。従って、ワード線ＷＬ０に接続されたメモリセルＭＴのドレインは選択トランジスタＳＴ１のソースに接続され、ワード線ＷＬｑに接続されたメモリセルＭＴのソースは選択トランジスタＳＴ２のドレインに接続されている。
【００１９】
ワード線ＷＬ０〜ＷＬｑは、ブロック内のＮＡＮＤストリング間で、メモリセルＭＴの制御ゲート電極を共通に接続している。つまり、ブロック内において同一行にあるメモリセルＭＴの制御ゲート電極は、同一のワード線ＷＬに接続される。各メモリセルＭＴに１ビットの値を保持可能に構成される場合には、同一のワード線ＷＬに接続される（ｐ＋１）個のメモリセルＭＴは１ページとして取り扱われ、このページごとにプログラム処理及びリード処理が行われる。
【００２０】
なお、各メモリセルＭＴには、複数ビットのデータが格納され得る。例えば、各メモリセルＭＴがｎ（ｎ≧２）ビットのデータを格納可能な場合、ワード線当たりの記憶容量はｎページ分のサイズに等しくなる。
【００２１】
なお、ブロックの構成はこれに限定されない。メモリセルＭＴは、２次元的に配列されてもよいし、３次元的に配列されてもよい。メモリセルＭＴが３次元的に配列される場合には、例えば、導電膜と絶縁膜とが交互に積層された積層体が柱状の半導体柱で貫通され、導電膜と半導体柱とが交差する部分にメモリセルＭＴが設けられ得る。
【００２２】
図１に説明を戻す。
ＮＡＮＤメモリ２００には、ライトデータ２０１と、論物変換テーブル２０２と、が格納される。
【００２３】
ライトデータ２０１は、メモリコントローラ１００において所定の処理が実施され、その後、ＮＡＮＤメモリ２００に格納される。所定の処理は、誤り訂正のための符号化、またはランダマイズ、などを含み得る。
【００２４】
論物変換テーブル２０２は、論理アドレスと物理アドレスとの対応関係を示す情報である。物理アドレスは、ＮＡＮＤメモリ２００内の物理的な位置を示す位置情報である。
【００２５】
メモリコントローラ１００は、ホスト２とＮＡＮＤメモリ２００との間のデータ転送を実行する。メモリコントローラ１００は、コントローラの一例である。
【００２６】
メモリコントローラ１００は、コマンド解析装置１１０、不揮発化装置１２０、リード処理装置１３０、差分テーブル管理装置１４０、および反映装置１５０を備える。
【００２７】
コマンド解析装置１１０は、ホスト２から受信したコマンドの種別を判定する。そして、コマンド解析装置１１０は、ホスト２から受信したコマンドがライトコマンドであった場合、当該ライトコマンドに含まれる論理アドレスを、当該ライトコマンドによって書き込みが要求されたライトデータとともに、不揮発化装置１２０に送信する。また、コマンド解析装置１１０は、ホスト２から受信したコマンドがリードコマンドであった場合、当該リードコマンドに含まれる論理アドレスをリード処理装置１３０に送信する。
【００２８】
リード処理装置１３０は、コマンド解析装置１１０からリードコマンドに含まれていた論理アドレスを受信すると、アドレス解決処理を実行することによって、当該論理アドレスを物理アドレスに変換する。そして、リード処理装置１３０は、変換によって得られた物理アドレスが示す位置に格納されているデータ（ライトデータ２０１）を読み出して、読み出された当該データをホスト２に送信する。
【００２９】
不揮発化装置１２０は、バッファメモリ１２１を備える。バッファメモリ１２１は、第３メモリの一例である。
【００３０】
第３メモリを構成するメモリの種類は、特定の種類に限定されない。第３メモリとしては、例えば、ＮＡＮＤメモリ２００に比べ、高速かつランダムアクセスの性能に優れた揮発性メモリが採用され得る。具体的には、例えば、DRAM（Dynamic  Random  Access  Memory）またはSRAM（Static  Random  Access  Memory）などが、第３メモリとして採用され得る。
【００３１】
不揮発化装置１２０は、論理アドレスとライトデータとを受信すると、ライトデータをバッファメモリ１２１に格納する。そして、不揮発化装置１２０は、バッファメモリ１２１に格納されたライトデータをＮＡＮＤメモリ２００に格納する、不揮発化処理を実行する。
【００３２】
なお、バッファメモリ１２１は、それぞれ異なるライトコマンドとともに受信した１以上のライトデータを蓄えることができる。そして、不揮発化装置１２０は、バッファメモリ１２１に格納された１以上のライトデータを１回の不揮発化処理によってＮＡＮＤメモリ２００に格納することができる。また、不揮発化装置１２０は、不揮発化処理において、バッファメモリ１２１に格納された１つのライトデータのうちの一部のみをＮＡＮＤメモリ２００に格納し、当該１つのライトデータのうちの他の一部を次回以降の不揮発化処理においてＮＡＮＤメモリ２００に格納し得る。
【００３３】
不揮発化処理の実行のトリガ条件は、任意に設定され得る。一例では、バッファメモリ１２１に格納されたライトデータの合計量が所定量を超えたことをトリガ条件として不揮発化処理を実行できる。所定量は、例えば、１ページ分の容量である。不揮発化装置１２０は、例えば、所定量のライトデータをＮＡＮＤメモリ２００に書き込むことができる。
【００３４】
不揮発化装置１２０は、不揮発化処理を実行すると、不揮発化処理の対象となったライトデータ毎に、論理アドレス空間内のライトデータが位置する範囲と、ＮＡＮＤメモリ２００内、つまり物理アドレス空間内、の当該ライトデータが格納された範囲と、の対応関係を示す通知を生成する。この通知は、論理アドレスと物理アドレスとの対応関係の更新内容を通知するものである。以降、この通知を、更新通知と表記する。不揮発化装置１２０は、生成した更新通知を差分テーブル管理装置１４０に送信する。
【００３５】
以降では、論理アドレス空間内の範囲を、論理アドレス範囲と表記する。また、物理アドレス空間内の範囲を、物理アドレス範囲と表記する。
【００３６】
差分テーブル管理装置１４０は、ＳＲＡＭ１４１と、レジスタ１４２と、を備える。ＳＲＡＭ１４１は、第２メモリの一例である。ＳＲＡＭ１４１には、論物変換テーブル２０２の差分が記録され得るよう構成された差分テーブル３００が格納される。差分は、具体的には、最新の論理アドレスと物理アドレスとの対応関係と、論物変換テーブル２０２が示す論理アドレスと物理アドレスとの対応関係と、の差分である。つまり、論物変換テーブル２０２は、あるタイミング（第１タイミング）における論理アドレスと物理アドレスとの対応関係を示しており、差分テーブル２０２には、論物変換テーブル２０２が示す対応関係と、第１タイミングよりも後のタイミング（第２タイミング）における論理アドレスと物理アドレスとの対応関係と、の差分が格納される。レジスタ１４２には、テーブル管理情報４００が格納される。
【００３７】
差分テーブル管理装置１４０は、差分テーブル３００の管理を実行する。
【００３８】
反映装置１５０は、差分テーブル３００に記録された情報を論物変換テーブル２０２に反映させる、反映処理を実行することができる。
【００３９】
図３は、第１の実施形態の差分テーブル３００のデータ構成を説明するための模式的かつ例示的な図である。本図に示されるように、差分テーブル３００は、Ｎ個のエントリを備えている。ただしＮは２以上の整数である。Ｎ個のエントリのそれぞれは、エントリＩＤが付されている。差分テーブル３００は、リングバッファとして構成されてもよいし、リングバッファとして構成されていなくてもよい。
【００４０】
差分テーブル３００が備えるＮ個のエントリのそれぞれには、連続する複数の論理アドレスと、当該連続する複数の論理アドレスにリニアに対応する連続する物理アドレスと、を対応付ける対応関係が記録され得る。つまり、差分テーブル３００が備えるＮ個のエントリのそれぞれには、論理アドレス範囲と、物理アドレス範囲と、の対応関係が記録され得る。
【００４１】
例えば、図３に示されるように、差分テーブル３００が備える各エントリは、論理アドレスＬＡが記録されるフィールドと、物理アドレスＰＡが記録されるフィールドと、長さＬが記録されるフィールドと、を備える。
【００４２】
図４は、第１の実施形態の差分テーブル３００の１つのエントリに格納される内容を説明するための模式的かつ例示的な図である。論理アドレスＬＡは、論理アドレス範囲の始点を意味する。物理アドレスＰＡは、当該論理アドレス範囲に対応した物理アドレス範囲の始点を意味する。長さＬは、論理アドレス範囲（または物理アドレス範囲）の幅を示す。
【００４３】
上記の構成によって、各エントリに記録された内容は、論理アドレスＬＡから論理アドレス（ＬＡ＋Ｌ−１）までの範囲を、物理アドレスＰＡから物理アドレス（ＰＡ＋Ｌ−１）までの範囲にリニアに対応付けることができる。
【００４４】
なお、長さＬは、論理アドレス範囲または物理アドレス範囲の長さ（幅）に対応する長さ情報の一例である。長さ情報はこれに限定されない。例えば、長さＬに替えて、各アドレス範囲の終点を示すアドレスが、長さ情報として採用され得る。
【００４５】
なお、差分テーブル３００の各エントリは、有効ビットＶＢが記録されるフィールドを備え得る。有効ビットＶＢは、その有効ビットＶＢを含むエントリが有効であるか無効であるかを示す。
【００４６】
例えば、エントリに新たに対応関係が記録されたとき、有効を示す値がそのエントリの有効ビットＶＢとして記録され、そのエントリは、有効なエントリと見なされる状態になる。
【００４７】
また、例えば、エントリに記録された対応関係が論物変換テーブル２０２に反映されたとき、無効を示す値がそのエントリの有効ビットＶＢとして記録され、そのエントリは、無効なエントリと見なされる状態になる。無効なエントリの内容は、いずれの処理においても使用されない。無効なエントリは、新たな対応関係が記録可能なエントリ、つまり空きエントリ、として見なされる。
【００４８】
なお、上記の方法は、有効ビットＶＢを操作する方法の一例である。有効ビットＶＢの操作方法は、上記の方法に限定されない。
【００４９】
不揮発化処理の際には、不揮発化装置１２０からの更新通知に基づき、ライトデータが位置する論理アドレス範囲と、当該ライトデータが格納された先の物理アドレス範囲と、の対応関係が、差分テーブル３００に記録される。つまり、不揮発化処理によって、論理アドレスと物理アドレスとの対応関係が部分的に変更される。差分テーブル３００には、論物変換テーブル２０２が示す論理アドレスと物理アドレスとの対応関係と、不揮発化処理によって変更された後の論理アドレスと物理アドレスとの最新の対応関係と、の差分に該当する情報が、記録される。
【００５０】
リードコマンドの処理の際には、リードコマンドに含まれる論理アドレスを当該論理アドレスに対応する物理アドレスに変換するアドレス解決処理が実行される。アドレス解決処理では、論物変換テーブル２０２よりも先に、差分テーブル３００が検索される。差分テーブル３００に、変換対象の論理アドレスにかかる対応関係が記録されている場合には、当該対応関係が変換に用いられる。差分テーブル３００に変換対象の論理アドレスにかかる対応関係が記録されていない場合には、ＮＡＮＤメモリ２００に格納された論物変換テーブル２０２が変換に用いられる。
【００５１】
差分テーブル３００が備えるエントリの数は有限である。したがって、不揮発化処理が継続的に実行されることによって、いずれ空きエントリが枯渇する。空きエントリが枯渇すると、それ以上不揮発化処理を実行することが不可能である。よって、不揮発化処理が中断されて、反映処理が実行される。
【００５２】
反映処理では、差分テーブル３００に記録された対応関係のうちの一部または全部が、論物変換テーブル２０２に反映される。反映が完了した対応関係が記録されたエントリは、有効ビットＶＢが操作されることで、有効な状態から無効な状態に遷移せしめられ、これによって、当該エントリは、新たな対応関係が記録可能なエントリ、つまり空きエントリとして見なされる状態になる。反映処理によって空きエントリが生成されることで、不揮発化処理を再開することが可能となる。
【００５３】
このように、空きエントリが枯渇すると、不揮発化処理が中断されて、反映処理が実行され、反映処理が完了するまで不揮発化処理の再開が待たされる。よって、空きエントリが頻繁に枯渇する場合、ライトに関する性能が低下する。
【００５４】
第１の実施形態では、差分テーブル管理装置１４０は、新規の更新通知を受信した際に特定の条件が成立する場合、当該更新通知が示す内容を空きエントリに記録するのではなく、空きエントリではないエントリの内容を更新する。この構成によって、空きエントリが枯渇する頻度を低減し、ライトに関する性能の低下を抑制する。
【００５５】
図５および図６は、第１の実施形態の上記した差分テーブル管理装置１４０の動作の概要を説明するための模式的かつ例示的な図である。
【００５６】
例えば、図５（Ａ）に示されるように、差分テーブル３００のある有効なエントリ（第１エントリＥ１と表記する）に、論理アドレスＬＡ１、物理アドレスＰＡ１、および長さＬ１がすでに記録されている場合を考える。このエントリＥ１に格納された内容は、図５（Ｂ）に示されるように、論理アドレスＬＡ１を始点として長さＬ１の論理アドレス範囲ＬＲ１と、物理アドレスＰＡ１を始点として長さＬ１の物理アドレス範囲ＰＲ１と、の対応関係を示す。
【００５７】
エントリＥ１に上記のような対応関係が記録されている状況において、差分テーブル管理装置１４０が、論理アドレス範囲ＬＲ１に後続する論理アドレス範囲ＬＲ２と、物理アドレス範囲ＰＲ１に後続する物理アドレス範囲ＰＲ２と、の対応関係を示す更新通知を受信した場合、差分テーブル管理装置１４０は、図６（Ａ）に示されるように、第１エントリＥ１に記録された長さＬ１を、長さＬ１と論理アドレス範囲ＬＲ２（または物理アドレス範囲ＰＲ２）の長さＬ２との合計値で更新する。
【００５８】
これによって、更新後のエントリＥ１は、図６（Ｂ）に示されるように、論理アドレス範囲ＬＲ１と論理アドレス範囲ＬＲ２とを連結した論理アドレス範囲（ＬＲ１＋ＬＲ２）と、物理アドレス範囲ＰＲ１と物理アドレス範囲ＰＲ２とを連結した物理アドレス範囲（ＰＲ１＋ＰＲ２）と、の対応関係が記録された状態となる。
【００５９】
このように、第１の実施形態によれば、更新通知が示す、ライトデータが書き込まれた範囲が、差分テーブル３００にすでに対応関係が記録された範囲に論理アドレスおよび物理アドレスの両方の点で後続する、という条件が満たされている場合、当該更新通知が示す対応関係は、空きエントリに記録されるのではなく、既存のエントリの内容を更新する形で差分テーブル３００に記録される。既存のエントリとは、換言すると、対応関係が既に記録された有効なエントリである。
【００６０】
以降では、更新通知が示す範囲が、差分テーブル３００にすでに対応関係が記録された範囲に論理アドレスおよび物理アドレスの両方の点で後続する、という条件が満たされていることを、通知された対応関係は連続性を有する、と表記する。また、更新通知が示す範囲が、差分テーブル３００にすでに対応関係が記録された範囲に論理アドレスおよび物理アドレスの両方の点で連続するという条件が満たされていないことを、通知された対応関係は連続性を有さない、と表記する。
【００６１】
なお、不揮発化装置１２０は、どの論理アドレスも対応付けられていないブロックである空きブロックを入力ブロックとして選択して、当該入力ブロックに物理アドレス順にデータを書き込むことができる。したがって、例えば、２つのライトデータが連続する順番で不揮発化される場合、当該２つのライトデータは、物理アドレスが連続する２つの範囲に格納される。換言すると、不揮発化された順番が連続しない２つのライトデータは、物理アドレスが連続しない２つの範囲に格納される。このことは、通知された対応関係が連続性を有するか否かは、差分テーブル３００のうちの最後に更新されたエントリのみに基づいて判定され得ることを意味する。
【００６２】
そこで、差分テーブル管理装置１４０は、最後に更新されたエントリを記憶し、記憶されたエントリに基づいて連続性の判定を実行する。具体的には、差分テーブル管理装置１４０は、最後に更新されたエントリに関する情報であるテーブル管理情報４００をレジスタ１４２に格納する。そして、差分テーブル管理装置１４０は、通知された対応関係と、テーブル管理情報４００と、に基づいて、通知された対応関係が連続性を有するか否かを判定する。
【００６３】
図７は、第１の実施形態のテーブル管理情報４００の構成を示す模式的かつ例示的な図である。テーブル管理情報４００は、論理アドレスＬＡ＿ＴＡＩＬ＿ＬＡＳＴ、物理アドレスＰＡ＿ＴＡＩＬ＿ＬＡＳＴ、長さＬ＿ＬＡＳＴ、有効／無効情報、および次入力位置情報ＮＥＸＴを含む。
【００６４】
ＬＡ＿ＴＡＩＬ＿ＬＡＳＴは、最後に更新されたエントリが示す論理アドレス範囲の末尾に対応した末尾情報の一例である。具体的には、ＬＡ＿ＴＡＩＬ＿ＬＡＳＴは、例えば、最後に更新されたエントリに記録された論理アドレスＬＡに当該エントリに記録された長さＬを加算して得られる値である。つまり、この例では、ＬＡ＿ＴＡＩＬ＿ＬＡＳＴは、最後に更新されたエントリに記録された対応関係にかかる論理アドレス範囲に後続する論理アドレスを示す。
【００６５】
ＰＡ＿ＴＡＩＬ＿ＬＡＳＴは、最後に更新されたエントリが示す物理アドレス範囲の末尾に対応した末尾情報の一例である。具体的には、ＰＡ＿ＴＡＩＬ＿ＬＡＳＴは、例えば、最後に更新されたエントリに記録された物理アドレスＰＡに当該エントリに記録された長さＬを加算して得られる値である。つまり、この例では、ＰＡ＿ＴＡＩＬ＿ＬＡＳＴは、最後に更新されたエントリに記録された対応関係にかかる物理アドレス範囲に後続する物理アドレスを示す。
【００６６】
Ｌ＿ＬＡＳＴは、最後に更新されたエントリに記録された長さＬである。
【００６７】
差分テーブル管理装置１４０は、更新通知を受信した場合、当該更新通知に含まれる論理アドレス（ＬＡ＿ＨＥＡＤ＿ＮＥＷと表記する）がＬＡ＿ＴＡＩＬ＿ＬＡＳＴと一致し、かつ当該更新通知に含まれる物理アドレス（ＰＡ＿ＨＥＡＤ＿ＮＥＷと表記する）がＰＡ＿ＴＡＩＬ＿ＬＡＳＴと一致するか否かを判定する。ＬＡ＿ＨＥＡＤ＿ＮＥＷとＬＡ＿ＴＡＩＬ＿ＬＡＳＴとが一致し、かつＰＡ＿ＨＥＡＤ＿ＮＥＷとＰＡ＿ＴＡＩＬ＿ＬＡＳＴとが一致する場合、通知された対応関係は連続性を有すると判定できる。ＬＡ＿ＨＥＡＤ＿ＮＥＷとＬＡ＿ＴＡＩＬ＿ＬＡＳＴとが一致しないか、またはＰＡ＿ＨＥＡＤ＿ＮＥＷとＰＡ＿ＴＡＩＬ＿ＬＡＳＴとが一致しない場合、通知された対応関係は連続性を有さないと判定できる。
【００６８】
ＮＥＸＴは、次に対応関係が記録され得る空きエントリを示す。
【００６９】
有効／無効情報は、テーブル管理情報４００の内容が有効であるか無効であるかを示す。有効／無効情報は、無効を示す値が初期値として設定される。差分テーブル３００が更新されると、有効／無効情報は、有効を示す値が設定される。なお、有効／無効情報の設定方法はこれに限定されない。有効／無効情報は、任意のトリガによって、有効もしくは無効を示す値が設定される。
【００７０】
なお、コマンド解析装置１１０、不揮発化装置１２０、リード処理装置１３０、および差分テーブル管理装置１４０のうちの一部または全部は、ＦＰＧＡ（field-programmable  gate  array）やＡＳＩＣ（application  specific  integrated  circuit）などの、ハードウェア回路によって構成され得る。コマンド解析装置１１０、不揮発化装置１２０、リード処理装置１３０、差分テーブル管理装置１４０、および反映装置１５０のうちの一部または全部の機能は、プロセッサがプログラムを実行することによって実現されてもよい。メモリコントローラ１００は、例えばＳｏＣ（System-On-a-Chip）として構成され得る。メモリコントローラ１００は、複数のチップによって構成されてもよい。
【００７１】
また、ＳＲＡＭ１４１、レジスタ１４２、またはこれらの両方は、差分テーブル管理装置１４０の外に設けられてもよい。また、ＳＲＡＭ１４１、レジスタ１４２、またはこれらの両方は、メモリコントローラ１００の外に設けられてもよい。また、バッファメモリ１２１は、不揮発化装置１２０の外に設けられてもよい。また、バッファメモリ１２１は、メモリコントローラ１００の外に設けられてもよい。また、リード処理装置１３０は、バッファメモリを備え得る。バッファメモリ１２１と、リード処理装置１３０が備えるバッファメモリとは、兼用され得る。
【００７２】
続いて、第１の実施形態のメモリシステム１の動作を説明する。
【００７３】
図８は、第１の実施形態のコマンド解析装置１１０の動作を説明するための模式的かつ例示的なフローチャートである。コマンド解析装置１１０は、ホスト２からアクセスコマンドを受信すると（Ｓ１０１）、解析によって、当該アクセスコマンドがライトコマンドであるか否かを判定する（Ｓ１０２）。当該アクセスコマンドがライトコマンドであると判定された場合には（Ｓ１０２：Ｙｅｓ）、コマンド解析装置１１０は、当該ライトコマンドに含まれる論理アドレスおよび当該ライトコマンドによって書き込みが要求されたライトデータを不揮発化装置１２０に送信する（Ｓ１０３）。そして、制御がＳ１０１に移行する。
【００７４】
ホスト２から受信したコマンドがライトコマンドではなくリードコマンドであると判定された場合には（Ｓ１０２：Ｎｏ）、コマンド解析装置１１０は、当該リードコマンドに含まれる論理アドレスをリード処理装置１３０に送信する（Ｓ１０４）。そして、制御がＳ１０１に移行する。
【００７５】
図９は、第１の実施形態のリード処理装置１３０の動作を説明するための模式的かつ例示的なフローチャートである。リード処理装置１３０は、まず、コマンド解析装置１１０から論理アドレスを受信する（Ｓ２０１）。当該論理アドレスは、前述したＳ１０４においてコマンド解析装置１１０が送信した論理アドレスである。本図の説明において、当該論理アドレスを、対象の論理アドレス、と表記する。
【００７６】
Ｓ２０１の後、リード処理装置１３０は、差分テーブル３００を検索することによって、対象の論理アドレスにかかる対応関係が差分テーブル３００に記録されているか否かを判定する（Ｓ２０２）。対象の論理アドレスにかかる対応関係が差分テーブル３００に記録されている場合（Ｓ２０２：Ｙｅｓ）、リード処理装置１３０は、差分テーブル３００に記録されている当該対応関係に基づいて、対象の論理アドレスに対応する物理アドレスを取得する（Ｓ２０３）。
【００７７】
対象の論理アドレスにかかる対応関係が差分テーブル３００に記録されていない場合（Ｓ２０２：Ｎｏ）、リード処理装置１３０は、ＮＡＮＤメモリ２００に格納されている論物変換テーブル２０２を参照することによって、対象の論理アドレスに対応する物理アドレスを取得する（Ｓ２０４）。
【００７８】
なお、メモリコントローラ１００に論物変換テーブル２０２の一部または全部がキャッシュされるキャッシュメモリを有する場合がある。キャッシュメモリに、対象の論理アドレスにかかる対応関係が格納されている場合には、リード処理装置１３０は、キャッシュメモリ内の当該対応関係から対象の論理アドレスに対応する物理アドレスを取得してもよい。
【００７９】
Ｓ２０３またはＳ２０４の後、リード処理装置１３０は、取得した物理アドレスが示すＮＡＮＤメモリ２００内の位置に格納されたユーザデータをリードして、当該ユーザデータをホスト２に転送する（Ｓ２０５）。そして、Ｓ２０１に制御が移行する。
【００８０】
図１０は、第１の実施形態の不揮発化装置１２０の動作を説明するための模式的かつ例示的なフローチャートである。不揮発化装置１２０は、コマンド解析装置１１０から論理アドレスおよびライトデータを受信する（Ｓ３０１）。当該論理アドレスおよび当該ライトデータは、前述したＳ１０３においてコマンド解析装置１１０が送信した論理アドレスおよびライトデータである。
【００８１】
不揮発化装置１２０は、受信したライトデータをバッファメモリ１２１に格納する（Ｓ３０２）。そして、不揮発化処理の実行のトリガ条件が満たされたとき（Ｓ３０３：Ｙｅｓ）、不揮発化装置１２０は、バッファメモリ１２１内のライトデータを不揮発化する（Ｓ３０４）。つまり、不揮発化装置１２０は、バッファメモリ１２１内のライトデータをＮＡＮＤメモリ２００に書き込む。
【００８２】
Ｓ３０４では、不揮発化装置１２０は、入力ブロック内の空き領域の先頭位置にライトデータを書き込む。これによって、ライトデータは、直前に別のライトデータが書き込まれた範囲に物理アドレスの点で後続する位置に書き込まれる。なお、入力ブロック内の空き領域が枯渇した場合には、不揮発化装置１２０は、当該入力ブロックへの新たなデータの書き込みを終了し、新たな入力ブロックを用意し、当該新たな入力ブロックにライトデータの書き込みを再開することができる。
【００８３】
続いて、不揮発化装置１２０は、不揮発化が完了したライトデータにかかる更新通知を生成し、当該更新通知を差分テーブル管理装置１４０に送信する（Ｓ３０５）。そして、制御がＳ３０１に移行する。
【００８４】
更新通知は、ライトデータが位置する論理アドレス範囲の始点の論理アドレスＬＡ＿ＨＥＡＤ＿ＮＥＷと、ライトデータが書き込まれた物理アドレス範囲の始点の物理アドレスＰＡ＿ＨＥＡＤ＿ＮＥＷと、長さＬ＿ＮＥＷと、を含む。論理アドレスＬＡ＿ＨＥＡＤ＿ＮＥＷは、ライトコマンドに含まれた論理アドレスに対応する。Ｌ＿ＮＥＷは、ライトデータのサイズに対応する。
【００８５】
なお、Ｓ３０４では、不揮発化装置１２０は、それぞれ異なるライトコマンドによって書き込みが要求された２以上のライトデータをＮＡＮＤメモリ２００に書き込むことができる。不揮発化装置１２０がそれぞれ異なるライトコマンドによって書き込みが要求された２以上のライトデータをＮＡＮＤメモリ２００に書き込んだ場合、不揮発化装置１２０は、Ｓ３０５では、１つのライトコマンドによって書き込みが要求されたライトデータ毎に更新通知を生成し送信する。
【００８６】
また、ライトデータが２つの入力ブロックに跨がって書き込まれる場合がある。ライトデータが２つの入力ブロックに書き込まれ、当該２つの入力ブロックは物理アドレスの点で不連続である場合には、不揮発化装置１２０は、ライトデータの当該２つの入力ブロックの一に書き込まれた部分と、ライトデータの当該２つの入力ブロックの他に書き込まれた部分と、のそれぞれについて更新通知を生成し送信してもよい。
【００８７】
図１１は、第１の実施形態の差分テーブル管理装置１４０による差分テーブル３００への記録の動作を説明するための模式的かつ例示的なフローチャートである。差分テーブル管理装置１４０は、更新通知を受信すると（Ｓ４０１）、有効／無効情報が有効を示しているか否かを判定する（Ｓ４０２）。
【００８８】
有効／無効情報が有効を示している場合（Ｓ４０２：Ｙｅｓ）、差分テーブル管理装置１４０は、ＬＡ＿ＨＥＡＤ＿ＮＥＷがＬＡ＿ＴＡＩＬ＿ＬＡＳＴと等しいか否かを判定する（Ｓ４０３）。この処理によって、更新通知が示す論理アドレス範囲が、前回に書き込まれたライトデータの論理アドレス範囲に後続するか否かが判定される。
【００８９】
ＬＡ＿ＨＥＡＤ＿ＮＥＷがＬＡ＿ＴＡＩＬ＿ＬＡＳＴと等しい場合（Ｓ４０３：Ｙｅｓ）、つまり、更新通知が示す論理アドレス範囲が前回に書き込まれたライトデータの論理アドレス範囲に後続する場合、差分テーブル管理装置１４０は、さらに、ＰＡ＿ＨＥＡＤ＿ＮＥＷがＰＡ＿ＴＡＩＬ＿ＬＡＳＴと等しいか否かを判定する（Ｓ４０４）。この処理によって、更新通知が示す物理アドレス範囲が、前回に書き込まれたライトデータの物理アドレス範囲に後続するか否かが判定される。
【００９０】
ＰＡ＿ＨＥＡＤ＿ＮＥＷがＰＡ＿ＴＡＩＬ＿ＬＡＳＴと等しい場合（Ｓ４０４：Ｙｅｓ）、つまり、更新通知が示す物理アドレス範囲が前回に書き込まれたライトデータの物理アドレス範囲に後続する場合、ここまでの手順によって、通知された対応関係は連続性を有することが確認できたことになる。よって、差分テーブル管理装置１４０は、前回に更新されたエントリを更新し得るが、その前に、差分テーブル管理装置１４０は、例外条件が満たされているか否かを判定する（Ｓ４０５）。
【００９１】
例外条件は、通知された対応関係が連続性を有する場合において、当該対応関係を空きエントリに記録するための条件である。任意の条件が例外条件として設定され得る。例外条件の一例は、第３の実施形態において説明する。
【００９２】
例外条件が満たされていない場合（Ｓ４０５：Ｎｏ）、差分テーブル管理装置１４０は、通知された対応関係を既存のエントリを更新する形で差分テーブル３００に記録する。具体的には、差分テーブル管理装置１４０は、次入力位置情報ＮＥＸＴが示すエントリの１つ前のエントリに記録された長さを、Ｌ＿ＬＡＳＴとＬ＿ＮＥＷとの合計値で更新する（Ｓ４０６）。なお、Ｓ４０６が実行される前においては、Ｌ＿ＬＡＳＴは、次入力位置情報ＮＥＸＴが示すエントリの１つ前のエントリに記録された長さと等しい。差分テーブル管理装置１４０は、次入力位置情報ＮＥＸＴが示すエントリの１つ前のエントリから長さを読み出して、読み出した長さにＬ＿ＮＥＷを加算することによって、更新後の値を取得してもよい。
【００９３】
続いて、差分テーブル管理装置１４０は、当該次入力位置情報ＮＥＸＴが示すエントリの１つ前のエントリの内容の更新に応じて、テーブル管理情報４００を更新する。具体的には、差分テーブル管理装置１４０は、ＬＡ＿ＴＡＩＬ＿ＬＡＳＴを、ＬＡ＿ＴＡＩＬ＿ＬＡＳＴにＬ＿ＮＥＷを加算して得られる値で更新し（Ｓ４０７）、ＰＡ＿ＴＡＩＬ＿ＬＡＳＴを、ＰＡ＿ＴＡＩＬ＿ＬＡＳＴにＬ＿ＮＥＷを加算して得られる値で更新し（Ｓ４０８）、Ｌ＿ＬＡＳＴをＬ＿ＬＡＳＴにＬ＿ＮＥＷを加算して得られる値で更新する（Ｓ４０９）。これらの処理によって、テーブル管理情報４００は、Ｓ４０６によって更新された内容に対応した内容に更新される。
【００９４】
有効／無効情報が無効を示している場合（Ｓ４０２：Ｎｏ）、ＬＡ＿ＨＥＡＤ＿ＮＥＷがＬＡ＿ＴＡＩＬ＿ＬＡＳＴと等しくない場合（Ｓ４０３：Ｎｏ）、ＰＡ＿ＨＥＡＤ＿ＮＥＷがＰＡ＿ＴＡＩＬ＿ＬＡＳＴと等しくない場合（Ｓ４０４：Ｎｏ）、または例外条件が満たされている場合（Ｓ４０５：Ｙｅｓ）、差分テーブル管理装置１４０は、通知された対応関係を新しいエントリに記録する。具体的には、差分テーブル管理装置１４０は、次入力位置情報ＮＥＸＴが示すエントリに、ＬＡ＿ＨＥＡＤ＿ＮＥＷ、ＰＡ＿ＨＥＡＤ＿ＮＥＷ、Ｌ＿ＮＥＷ、およびＶＢ（有効）を入力する（Ｓ４１０）。
【００９５】
そして、差分テーブル管理装置１４０は、当該新しいエントリへの記録に応じて、テーブル管理情報４００を更新する。具体的には、差分テーブル管理装置１４０は、次入力位置情報ＮＥＸＴを、ＮＥＸＴに１を加算して得られる値で更新し（Ｓ４１１）、ＬＡ＿ＴＡＩＬ＿ＬＡＳＴを、ＬＡ＿ＨＥＡＤ＿ＮＥＷにＬ＿ＮＥＷを加算して得られる値で更新し（Ｓ４１２）、ＰＡ＿ＴＡＩＬ＿ＬＡＳＴを、ＰＡ＿ＨＥＡＤ＿ＮＥＷにＬ＿ＮＥＷを加算して得られる値で更新し（Ｓ４１３）、Ｌ＿ＬＡＳＴをＬ＿ＮＥＷで更新する（Ｓ４１４）。そして、差分テーブル管理装置１４０は、有効／無効情報として有効を示す値を設定する（Ｓ４１５）。これらの処理によって、テーブル管理情報４００は、新しいエントリに記録された内容に対応した内容に更新される。
【００９６】
Ｓ４１０またはＳ４１５の後、制御がＳ４０１に移行する。
【００９７】
図１２は、第１の実施形態の反映装置１５０による反映処理の動作を説明するための模式的かつ例示的なフローチャートである。反映装置１５０は、差分テーブル３００が空きエントリを有する否かを判定する（Ｓ５０１）。差分テーブル３００が空きエントリを有する場合（Ｓ５０１：Ｙｅｓ）、反映装置１５０は、Ｓ５０１を再び実行する。差分テーブル３００が空きエントリを有さない場合（Ｓ５０１：Ｎｏ）、反映装置１５０は、反映処理を実行する（Ｓ５０２）。
【００９８】
Ｓ５０２では、反映装置１５０は、例えば、有効な状態になったタイミングが最も古い１以上のエントリを、反映処理の対象のエントリとして選択する。そして、反映装置１５０は、反映処理の対象のエントリに記録された内容によって、論物変換テーブル２０２を更新する。なお、反映処理の対象のエントリの選択方法は、これに限定されない。反映装置１５０は、任意の方法で反映処理の対象のエントリを選択することができる。
【００９９】
Ｓ５０２に続いて、反映装置１５０は、反映処理が完了したエントリを無効化する（Ｓ５０３）。つまり、反映装置１５０は、反映処理が完了したエントリの有効ビットＶＢとして、無効を示す値を設定する。
【０１００】
Ｓ５０３の後、Ｓ５０１に制御が移行する。
【０１０１】
なお、反映処理の対象として選択されるエントリの数は１に限定されない。例えば、Ｓ５０１の処理においてＮｏと判定された場合、反映装置１５０は、全ての有効なエントリを反映処理の対象のエントリとして選択してもよい。反映装置１５０は、有効ビットＶＢとして有効を示す値が設定された個々のエントリを順次、反映処理の対象のエントリとして設定し、反映処理の対象のエントリとして設定されたエントリに対してＳ５０２とＳ５０３との処理を実行する。これによって、反映装置１５０は、全てのエントリが空きエントリになるまで反映処理を繰り返し実行する。なお、反映装置１５０は、空きエントリの数が所定数以上となるまで、Ｓ５０２とＳ５０３との処理を繰り返し実行してもよい。
【０１０２】
以上述べたように、第１の実施形態によれば、メモリコントローラ１００は、ライトデータの不揮発化の際に、当該ライトデータが位置する範囲が、既に差分テーブル３００のエントリに記録された対応関係にかかる範囲に論理アドレスおよび物理アドレスの両方の点で後続する、という条件が満たされている場合、当該エントリを更新する。そのようなエントリがない場合、メモリコントローラ１００は、ライトデータが位置する範囲にかかる対応関係を空きエントリに記録する。
【０１０３】
これによって、空きエントリの消費速度が低減されるので、反映処理の実行頻度が低減され、その結果、性能の低下が抑制される。つまり、利便性が向上する。
【０１０４】
また、差分テーブル３００のそれぞれに記録され得る対応関係は、長さ情報を含む。メモリコントローラ１００は、更新対象の既存のエントリに記録された長さ情報を更新する。
【０１０５】
これによって、通知された対応関係が空きエントリではなく既に記録された対応関係を更新する形で差分テーブル３００に記録されるので、空きエントリの消費速度が低減される。
【０１０６】
また、メモリコントローラ１００は、最後に更新したエントリを記憶し、当該エントリに記録された範囲に、通知された対応関係にかかる範囲が論理アドレスおよび物理アドレスの両方の点で後続するか否かを判定する。
【０１０７】
これによって、更新すべきエントリを探索する処理を省略することが可能となる。
【０１０８】
なお、メモリコントローラ１００は、差分テーブル３００から上記の条件を満たすエントリを探索するように構成されてもよい。
【０１０９】
また、メモリコントローラ１００は、最後に更新したエントリに記録された対応関係が示す範囲（論理アドレス範囲および物理アドレス範囲）の末尾に対応した末尾情報として、ＬＡ＿ＴＡＩＬ＿ＬＡＳＴおよびＰＡ＿ＴＡＩＬ＿ＬＡＳＴを記憶する。そして、メモリコントローラ１００は、通知された対応関係が連続性を有するか否かを、当該末尾情報に基づいて判定する。
【０１１０】
これによって、メモリコントローラ１００は、通知された対応関係が連続性を有するか否かの判定を簡単に実行することが可能となる。
【０１１１】
なお、末尾情報は上記の例に限定されない。例えば、最後に更新されたエントリに記録された論理アドレスＬＡに、当該エントリに記録された長さＬの加算と１の減算とを実施して得られる値が、論理アドレス範囲にかかる末尾情報として採用され得る。その場合には、当該末尾情報に１を加算して得られる値がＬＡ＿ＨＥＡＤ＿ＮＥＷと等しいか否かに基づいて、更新通知が示す論理アドレス範囲が、前回に書き込まれたライトデータの論理アドレス範囲に後続するか否かが判定される。
【０１１２】
また、最後に更新されたエントリに記録された物理アドレスＰＡに、当該エントリに記録された長さＬの加算と１の減算とを実施して得られる値が、物理アドレス範囲にかかる末尾情報として採用され得る。その場合には、当該町部情報に１を加算して得られる値がＰＡ＿ＨＥＡＤ＿ＮＥＷと等しいか否かに基づいて、更新通知が示す物理アドレス範囲が、前回に書き込まれたライトデータの物理アドレス範囲に後続するか否かが判定される。
【０１１３】
また、メモリコントローラ１００は、所定のトリガ条件が満たされた場合に、反映処理によって、差分テーブル３００が備える複数のエントリのうちの１以上のエントリの内容を論物変換テーブル２０２に反映させ、当該１以上のエントリを、新規に対応関係が記録され得る状態に設定する。
【０１１４】
これによって、空きエントリが生成され、その結果、不揮発化処理を再開することが可能となる。
【０１１５】
なお、以上の説明においては、反映処理は、空きエントリが枯渇されたときに実行された。反映処理の実行のトリガ条件はこれに限定されない。例えば、空きエントリの数が所定のしきい値を下回ることが反映処理の実行のトリガ条件として使用され得る。
【０１１６】
また、メモリコントローラ１００は、不揮発化装置１２０と差分テーブル管理装置１４０とを備える。不揮発化装置１２０は、不揮発化の際に、ライトデータが位置する論理アドレス範囲と当該ライトデータが書き込まれた先の物理アドレス範囲との対応関係を示す更新通知を生成する。差分テーブル管理装置１４０は、通知された対応関係が連続性を有するか否かを判定する。差分テーブル管理装置１４０は、通知された対応関係が連続性を有する場合、当該対応関係を、既存のエントリの内容を更新する形で差分テーブル３００に記録する。
【０１１７】
これによって、空きエントリの消費速度が低減される。
【０１１８】
なお、不揮発化装置１２０は、バッファメモリ１２１に格納されたそれぞれ異なるライトコマンドによって書き込みが要求された２以上のライトデータを一回の不揮発化処理によって不揮発化した場合、１つのライトコマンドによって書き込みが要求されたライトデータ毎に更新通知を生成することができる。
【０１１９】
（第２の実施形態）
メモリシステムが有する論理アドレス空間が複数の部分空間に分割され、各部分空間がそれぞれ異なるホストに提供される場合がある。NVM  Express（登録商標）規格では、このような部分空間は、ネームスペースと称される。また、UFS（Universal  Flash  Storage）規格では、このような部分空間は、LUN（Logical  Unit  Number）と称される。
【０１２０】
第２の実施形態では、一例として、NVM  Express（登録商標）規格が適用された場合について説明する。つまり、第２の実施形態では、メモリシステム１は、複数の部分空間として複数のネームスペースを提供するように構成されている。なお、メモリシステム１は、UFS規格が適用され、複数の部分空間として複数のLUNを提供するように構成されてもよい。
【０１２１】
以降では、第１の実施形態と異なる点について重点的に説明する。第１の実施形態と同じ構成については、説明が省略されるか、または簡略的に説明される。
【０１２２】
図１３および図１４は、第２の実施形態のライトデータの書き込み先を説明するための模式的かつ例示的な図である。
【０１２３】
図１３に示されるように、複数のネームスペース（ＮＳ（０）、ＮＳ（１）、ＮＳ（２）、・・・）を提供する場合、不揮発化装置１２０は、複数の入力ブロック（ＢＬＫ０、ＢＬＫ１、ＢＬＫ２、・・・）を用意する。そして、複数の入力ブロックのそれぞれに複数のネームスペースのうちの１つを一対一に対応付ける。そして、不揮発化装置１２０は、ライトデータをＮＡＮＤメモリ２００に書き込む際、そのライトデータのネームスペースに対応した入力ブロックにそのライトデータを書き込む。これによって、ネームスペース毎に異なる連続領域に各ライトデータが書き込まれることになる。
【０１２４】
図１４は、複数のネームスペースが設定されたメモリシステム１におけるライトデータの書き込み先の物理アドレス範囲を説明するための模式的な図である。図１４の（Ａ）に示されるように、ネームスペースＮＳ（０）を書き込み先として指定するライトコマンドＣ０と、ネームスペースＮＳ（１）を書き込み先として指定するライトコマンドＣ１と、ネームスペースＮＳ（０）を書き込み先として指定するライトコマンドＣ２と、がこの順番で発行されたと仮定する。
【０１２５】
その場合、例えば、ライトコマンドＣ０によって書き込み要求されたライトデータがブロックＢＬＫ０に書き込まれ、次に、ライトコマンドＣ１によって書き込み要求されたライトデータがブロックＢＬＫ１に書き込まれ、最後に、ライトコマンドＣ２によって書き込み要求されたライトデータがブロックＢＬＫ０に書き込まれる。つまり、ライトコマンドＣ０によって書き込み要求されたライトデータと、ライトコマンドＣ２によって書き込み要求されたライトデータと、は、同一のブロックＢＬＫ０に書き込まれ、ライトコマンドＣ１によって書き込み要求されたライトデータは、他のライトコマンドＣ０，Ｃ２によって書き込み要求されたライトデータが書き込まれるブロックＢＬＫ０と異なるブロックＢＬＫ１に書き込まれる。
【０１２６】
その結果、図１４の（Ｂ）に示されるように、ライトコマンドＣ０によって書き込みが要求されたライトデータが書き込まれる範囲と、ライトコマンドＣ２によって書き込みが要求されたライトデータが書き込まれる範囲とは、物理アドレスの点で連続する。また、ライトコマンドＣ１によって書き込みが要求されたライトデータが書き込まれる範囲は、ライトコマンドＣ０によって書き込みが要求されたライトデータが書き込まれる範囲およびライトコマンドＣ２によって書き込みが要求されたライトデータが書き込まれる範囲の何れとも連続しない。
【０１２７】
つまり、ネームスペースＮＳ（０）を書き込み先として指定する各ライトコマンドによって書き込み要求されたライトデータは、物理アドレスが連続する所定の範囲ＰＲ３の先頭から順番に書き込まれる。そして、ネームスペースＮＳ（１）を書き込み先として指定する各ライトコマンドによって書き込み要求されたライトデータは、物理アドレスが連続する所定の範囲ＰＲ４の先頭から順番に書き込まれる。これによって、ネームスペース毎に異なる連続領域に各ライトデータが書き込まれることになる。
【０１２８】
このように、ネームスペース毎に入力ブロックが用意されるので、１つのネームスペースの２つのライトデータが連続してＮＡＮＤメモリ２００に書き込まれる場合、たとえ当該２つのライトデータの書き込みの間に別のネームスペースのライトデータの書き込みが実行されたとしても、当該２つのライトデータが書き込まれる先の物理アドレス範囲は連続する。
【０１２９】
そこで、第２の実施形態では、差分テーブル管理装置１４０は、ネームスペース毎に連続性の判定を実行する。そのための構成として、図１５に示されるように、テーブル管理情報４００は、ネームスペース毎にサブ情報を含む構成を有する。
【０１３０】
各サブ情報は、１つのネームスペースと一対一に対応する。各サブ情報は、論理アドレスＬＡ＿ＴＡＩＬ＿ＬＡＳＴ、物理アドレスＰＡ＿ＴＡＩＬ＿ＬＡＳＴ、長さＬ＿ＬＡＳＴ、有効／無効情報、および現在入力位置情報ＣＵＲＲＥＮＴを備える。
【０１３１】
ＣＵＲＲＥＮＴは、対応するネームスペースに関する最後に更新されたエントリを示す。
【０１３２】
ＬＡ＿ＴＡＩＬ＿ＬＡＳＴは、ＣＵＲＲＥＮＴが示すエントリに記録された論理アドレスＬＡに当該エントリに記録された長さＬを加算して得られる値である。
【０１３３】
ＰＡ＿ＴＡＩＬ＿ＬＡＳＴは、ＣＵＲＲＥＮＴが示すエントリに記録された物理アドレスＰＡに当該エントリに記録された長さＬを加算して得られる値である。
【０１３４】
つまり、第２の実施形態によれば、テーブル管理情報４００は、ネームスペース毎に末尾情報を含んだ構成を有する。
【０１３５】
なお、Ｌ＿ＬＡＳＴは、ＣＵＲＲＥＮＴが示すエントリに記録された長さＬである。
【０１３６】
また、有効／無効情報は、対応するネームスペースに関するサブ情報の内容が有効であるか無効であるかを示す。
【０１３７】
また、テーブル管理情報４００は、次入力位置情報ＮＥＸＴを含む。ＮＥＸＴは、次に対応関係が記録され得る空きエントリを示す。
【０１３８】
図１６は、第２の実施形態のテーブル管理情報４００に含まれるＮＥＸＴと複数のＣＵＲＲＥＮＴとの関係を説明するための模式的かつ例示的な図である。
【０１３９】
本図の例では、差分テーブル３００は、Ｎ個のエントリのうちの＃０から＃Ｘまでのエントリが入力済みとなっており、＃Ｘ＋１から＃Ｎ−１までのエントリが空きエントリとなっている。差分テーブル３００には、ネームスペースを区別することなく対応関係が記録される。そして、各ＣＵＲＲＥＮＴは、対応するネームスペースにかかる最後に更新されたエントリを示す。
【０１４０】
本図の例では、ネームスペースＮＳ（０）にかかるＣＵＲＲＥＮＴによって、ネームスペースＮＳ（０）にかかる最後に更新されたエントリはエントリ＃３であることが示されている。また、ネームスペースＮＳ（１）にかかるＣＵＲＲＥＮＴによって、ネームスペースＮＳ（１）にかかる最後に更新されたエントリはエントリ＃０であることが示されている。また、ネームスペースＮＳ（Ｚ−１）にかかるＣＵＲＲＥＮＴによって、ネームスペースＮＳ（Ｚ−１）にかかる最後に更新されたエントリはエントリ＃Ｘであることが示されている。
【０１４１】
ＮＥＸＴは、空きエントリ（＃Ｘ＋１〜＃Ｎ−１）のうちの先頭のエントリ＃Ｘ＋１を示している。
【０１４２】
図１７は、第２の実施形態の差分テーブル管理装置１４０による差分テーブル３００への記録の動作を説明するための模式的かつ例示的なフローチャートである。差分テーブル管理装置１４０は、更新通知を受信する（Ｓ６０１）。
【０１４３】
Ｓ６０１において差分テーブル管理装置１４０が受信する更新通知は、ライトデータが位置する論理アドレス範囲の始点の論理アドレスＬＡ＿ＨＥＡＤ＿ＮＥＷと、ライトデータが書き込まれた物理アドレス範囲の始点の物理アドレスＰＡ＿ＨＥＡＤ＿ＮＥＷと、長さＬ＿ＮＥＷと、を含む。さらに、更新通知は、書き込み先のネームスペースの識別情報ＮＳを含む。ＮＳは、例えばライトコマンドに含まれている。不揮発化装置１２０は、ライトコマンドに含まれるＮＳを更新通知に記録して、ＮＳが記録された更新通知を差分テーブル管理装置１４０に送信する。
【０１４４】
以降の処理では、テーブル管理情報４００が含む複数のサブ情報のうちの、更新通知に含まれる情報ＮＳによって特定されるネームスペースにかかるサブ情報が使用される。
【０１４５】
Ｓ６０２に続いて、差分テーブル管理装置１４０、つまりネームスペースに対応するサブ情報が含む有効／無効情報が、有効を示しているか否かを判定する（Ｓ６０２）。
【０１４６】
有効／無効情報が有効を示している場合（Ｓ６０２：Ｙｅｓ）、差分テーブル管理装置１４０は、ＬＡ＿ＨＥＡＤ＿ＮＥＷがＬＡ＿ＴＡＩＬ＿ＬＡＳＴと等しいか否かを判定する（Ｓ６０３）。この処理によって、更新通知が示す論理アドレス範囲が、同一のネームスペースにかかる前回に書き込まれたライトデータの論理アドレス範囲に後続するか否かが判定される。
【０１４７】
ＬＡ＿ＨＥＡＤ＿ＮＥＷがＬＡ＿ＴＡＩＬ＿ＬＡＳＴと等しい場合（Ｓ６０３：Ｙｅｓ）、つまり、更新通知が示す論理アドレス範囲が同一のネームスペースにかかる前回に書き込まれたライトデータの論理アドレス範囲に後続する場合、差分テーブル管理装置１４０は、さらに、ＰＡ＿ＨＥＡＤ＿ＮＥＷがＰＡ＿ＴＡＩＬ＿ＬＡＳＴと等しいか否かを判定する（Ｓ６０４）。この処理によって、更新通知が示す物理アドレス範囲が、同一のネームスペースにかかる前回に書き込まれたライトデータの物理アドレス範囲に後続するか否かが判定される。
【０１４８】
ＰＡ＿ＨＥＡＤ＿ＮＥＷがＰＡ＿ＴＡＩＬ＿ＬＡＳＴと等しい場合（Ｓ６０４：Ｙｅｓ）、つまり、更新通知が示す物理アドレス範囲が同一のネームスペースにかかる前回に書き込まれたライトデータの物理アドレス範囲に後続する場合、ここまでの手順によって、通知された対応関係は連続性を有することが確認できたことになる。よって、差分テーブル管理装置１４０は、同一のネームスペースにかかる前回に更新されたエントリ（ＣＵＲＲＥＮＴが示すエントリ）を更新し得るが、その前に、差分テーブル管理装置１４０は、例外条件が満たされているか否かを判定する（Ｓ６０５）。
【０１４９】
例外条件は、通知された対応関係が連続性を有する場合において、当該対応関係を空きエントリに記録するための条件である。任意の条件が例外条件として設定され得る。例外条件の一例は、後述する第３の実施形態において説明する。
【０１５０】
例外条件が満たされていない場合（Ｓ６０５：Ｎｏ）、差分テーブル管理装置１４０は、通知された対応関係を既存のエントリを更新する形で差分テーブル３００に記録する。具体的には、差分テーブル管理装置１４０は、ＣＵＲＲＥＮＴが示すエントリに記録された長さを、Ｌ＿ＬＡＳＴとＬ＿ＮＥＷとの合計値で更新する（Ｓ６０６）。なお、Ｓ６０６が実行される前においては、Ｌ＿ＬＡＳＴは、ＣＵＲＲＥＮＴが示すエントリに記録された長さと等しい。差分テーブル管理装置１４０は、ＣＵＲＲＥＮＴが示すエントリから長さを読み出して、読み出した長さにＬ＿ＮＥＷを加算することによって、更新後の値を取得してもよい。
【０１５１】
続いて、差分テーブル管理装置１４０は、ＣＵＲＲＥＮＴが示すエントリの内容の更新に応じて、サブ情報を更新する。具体的には、差分テーブル管理装置１４０は、ＬＡ＿ＴＡＩＬ＿ＬＡＳＴを、ＬＡ＿ＴＡＩＬ＿ＬＡＳＴにＬ＿ＮＥＷを加算して得られる値で更新し（Ｓ６０７）、ＰＡ＿ＴＡＩＬ＿ＬＡＳＴを、ＰＡ＿ＴＡＩＬ＿ＬＡＳＴにＬ＿ＮＥＷを加算して得られる値で更新し（Ｓ６０８）、Ｌ＿ＬＡＳＴをＬ＿ＬＡＳＴにＬ＿ＮＥＷを加算して得られる値で更新する（Ｓ６０９）。これらの処理によって、サブ情報は、Ｓ６０６によって更新された内容に対応した内容に更新される。
【０１５２】
有効／無効情報が無効を示している場合（Ｓ６０２：Ｎｏ）、ＬＡ＿ＨＥＡＤ＿ＮＥＷがＬＡ＿ＴＡＩＬ＿ＬＡＳＴと等しくない場合（Ｓ６０３：Ｎｏ）、ＰＡ＿ＨＥＡＤ＿ＮＥＷがＰＡ＿ＴＡＩＬ＿ＬＡＳＴと等しくない場合（Ｓ６０４：Ｎｏ）、または例外条件が満たされている場合（Ｓ６０５：Ｙｅｓ）、差分テーブル管理装置１４０は、通知された対応関係を新しいエントリに記録する。具体的には、差分テーブル管理装置１４０は、次入力位置情報ＮＥＸＴが示すエントリに、ＬＡ＿ＨＥＡＤ＿ＮＥＷ、ＰＡ＿ＨＥＡＤ＿ＮＥＷ、Ｌ＿ＮＥＷ、およびＶＢ（有効）を入力する（Ｓ６１１０）。
【０１５３】
そして、差分テーブル管理装置１４０は、当該新しいエントリへの記録に応じて、サブ情報およびＮＥＸＴを更新する。具体的には、差分テーブル管理装置１４０は、ＣＵＲＲＥＮＴにＮＥＸＴが示すエントリＩＤを上書き形式で設定する（Ｓ６１１）。そして、ＮＥＸＴを、ＮＥＸＴに１を加算して得られる値で更新し（Ｓ６１２）、ＬＡ＿ＴＡＩＬ＿ＬＡＳＴを、ＬＡ＿ＨＥＡＤ＿ＮＥＷにＬ＿ＮＥＷを加算して得られる値で更新し（Ｓ６１３）、ＰＡ＿ＴＡＩＬ＿ＬＡＳＴを、ＰＡ＿ＨＥＡＤ＿ＮＥＷにＬ＿ＮＥＷを加算して得られる値で更新し（Ｓ６１４）、Ｌ＿ＬＡＳＴをＬ＿ＮＥＷで更新する（Ｓ６１５）。そして、差分テーブル管理装置１４０は、有効／無効情報として有効を示す値を設定する（Ｓ６１６）。これらの処理によって、サブ情報は、新しいエントリに記録された内容に対応した内容に更新される。
【０１５４】
Ｓ６０９またはＳ６１６の後、制御がＳ６０１に移行する。
【０１５５】
以上述べたように、第２の実施形態によれば、メモリシステム１がホスト２に提供する論理アドレス空間は複数の部分空間（例えばネームスペース）に分割され、メモリコントローラ１００は、部分空間毎にサブ情報を記憶する。
【０１５６】
これによって、部分空間単位で連続性の判定を実行することが可能となる。
【０１５７】
（第３の実施形態）
第３の実施形態では、例外条件について説明する。第３の実施形態は、第１の実施形態および第２の実施形態の何れにも適用され得る。
【０１５８】
さらに、第３の実施形態では、論物変換テーブル２０２は、複数のサブテーブルに分割される。そして、反映処理は、サブテーブル単位で実行される。つまり、反映処理の対象となる対応関係を含むサブテーブルがＮＡＮＤメモリ２００から揮発性メモリ（例えばバッファメモリ１２１）に読み出されて、バッファメモリ１２１上でサブテーブルが更新され、更新後のサブテーブルがＮＡＮＤメモリ２００に書き戻される。
【０１５９】
論理アドレス空間内の所定のサイズ毎に、論物変換テーブル２０２の分割の境界が設けられている。１つの境界と当該１つの境界に隣接する境界との間の上述した所定のサイズを有する空間を、リージョンと表記する。つまり、論理アドレス空間は、複数のリージョンに分割され、論理アドレスと物理アドレスとの対応関係は、リージョン毎に個別に設けられたテーブル（サブテーブル）によって管理される。
【０１６０】
図１８は、第３の実施形態のサブテーブルを説明するための模式的かつ例示的な図である。本図に示されるように、論物変換テーブル２０２は、ルートテーブル２１０と、複数のサブテーブル２１１と、を備える。
【０１６１】
図１８の例によれば、論理アドレス空間は、２ａ個のリージョンに分割されており、各リージョンは、論理アドレスの上位側のａビットによって識別される。ここで、ａは正の整数である。ルートテーブル２１０は、論理アドレスの上位側のａビットを、当該ａビットの情報によって特定されるリージョンにかかるサブテーブルが格納された物理アドレスに対応付ける。例えば、ルートテーブル２１０は、２ａ個のエントリを備え、２ａ個のエントリのそれぞれには、対応するサブテーブル２１１が格納された位置を示す物理アドレスが記録されている。
【０１６２】
さらに、図１８の例によれば、各リージョンは、連続する２ｂ個の論理アドレスを含む。ここで、ｂは正の整数である。各サブテーブル２１１は、対応するリージョン内の連続する２ｂ個の論理アドレスのそれぞれを、物理アドレスに対応付ける。各サブテーブル２１１は、例えば、２ｂ個のエントリを備え、２ｂ個のエントリのそれぞれには、論理アドレスに対応する物理アドレスが記録されている。
【０１６３】
なお、論理アドレスは、一般に、セクタと呼ばれるサイズ毎に与えられる。第３の実施形態では、論理アドレスと物理アドレスとの対応関係は、論理アドレスが連続する複数のセクタの束であるクラスタと呼ばれるサイズ毎に管理される。クラスタのサイズは，リージョンのサイズよりも小さい。以降の説明では、クラスタ単位のデータのことをクラスタと表記する場合がある。
【０１６４】
また、図１８の例によれば、全てのサブテーブル２１１は１つの階層に属する。論物変換テーブル２０２を構成するサブテーブル２１１の集合は、複数階層に階層化された構成を有していてもよい。
【０１６５】
続いて、差分テーブル３００に関する説明を行う。以降では、エントリとは、第１および第２の実施形態と同じく、差分テーブル３００のエントリを指す。
【０１６６】
連続性を有する複数の対応関係が１つのエントリで管理される場合、１つのエントリに記録された対応関係が示す範囲が複数のリージョンを含む可能性がある。その場合、エントリの数と、反映処理の際にＮＡＮＤメモリ２００から読み出すべきサブテーブル２１１の数とが対応しないため、ＮＡＮＤメモリ２００から読み出すべきサブテーブル２１１の数を見積もるなどの処理が反映処理の際に必要となる。バッファメモリ１２１に読み出すことができるサブテーブル２１１の数は、有限であるからである。
【０１６７】
第３の実施形態では、不揮発化装置１２０と差分テーブル管理装置１４０とは、不揮発化されたライトデータが位置する論理アドレス範囲がリージョンの境界を跨ぐ場合、リージョンの境界の前の範囲にかかる対応関係と、リージョンの境界の後の範囲にかかる対応関係と、をそれぞれ異なるエントリに記録するように構成される。これによって、エントリの数とＮＡＮＤメモリ２００から読み出すべきサブテーブル２１１の数とを対応させることが可能である。その結果、ＮＡＮＤメモリ２００から読み出すべきサブテーブル２１１の数を見積もる処理が不要となる。
【０１６８】
図１９は、第３の実施形態のライトコマンドとライトデータの位置およびサイズとの関係の一例を説明するための模式的かつ例示的な図である。本図の例では、クラスタのサイズは、セクタのサイズの８倍であることとする。紙面の右方から紙面の左方に向かう方向は、１つのクラスタに含まれる８つのセクタの論理アドレスの並びに対応する。また、矢印の方向は、ライトデータを受信した時間に対応する。
【０１６９】
そして、図１９の例では、ライトコマンドＣ３、ライトコマンドＣ４、ライトコマンドＣ５、およびライトコマンドＣ６がこの順番で発行されている。ライトコマンドＣ３は、先頭の位置の論理アドレスがＬＡ３であり３２セクタのサイズのライトデータＤ３の書き込みを要求するコマンドである。ライトコマンドＣ４は、先頭の位置の論理アドレスがＬＡ４であり１６セクタのサイズのライトデータＤ４の書き込みを要求するコマンドである。ライトコマンドＣ５は、先頭の位置の論理アドレスがＬＡ５であり８セクタのサイズのライトデータＤ５の書き込みを要求するコマンドである。ライトコマンドＣ６は、先頭の位置の論理アドレスがＬＡ６であり８セクタのサイズのライトデータＤ６の書き込みを要求するコマンドである。
【０１７０】
なお、本図では、各ライトコマンドによって書き込みが要求されたライトデータがクラスタの整数倍のサイズを有していることとしている。各ライトコマンドによって書き込みが要求されたライトデータのサイズはクラスタの整数倍に限定されない。各ライトコマンドによって書き込みが要求されたライトデータは、セクタの整数倍の任意のサイズを有し得る。
【０１７１】
ライトデータＤ３〜Ｄ６の合計のサイズが１ページに相当する場合、ライトデータＤ３〜Ｄ６は、１回の不揮発化処理によって不揮発化される。
【０１７２】
図２０は、第３の実施形態の１回の不揮発化処理によって不揮発化された４つのライトデータの配置の例を説明するための模式的かつ例示的な図である。紙面の右方から紙面の左方に向かう方向は、１つのクラスタに含まれる８つのセクタの物理アドレスの並びに対応する。また、紙面の上方から紙面の下方に向かう方向は、複数のクラスタの物理アドレスの並びに対応する。
【０１７３】
図２０に示されるように、４つのライトデータＤ３〜Ｄ６は、１回の不揮発化処理によって１つのページに詰め込まれる。不揮発化装置１２０は、不揮発化処理の際、４つのライトデータＤ３〜Ｄ６のそれぞれの先頭のクラスタから順番に着目して、着目したクラスタがライトデータの末尾のクラスタであるか否かの判定を行う。また、不揮発化装置１２０は、着目したクラスタがリージョンの末尾のクラスタであるか否かの判定を行う。また、不揮発化装置１２０は、着目したクラスタが不揮発化された４つのライトデータＤ３〜Ｄ６からなる一塊のデータの末尾のクラスタであるか否かの判定を行う。そして、不揮発化装置１２０は、これらの判定の結果に基づくタイミングで、更新通知の生成を行う。具体的には、着目したクラスタがライトデータの末尾のクラスタであると判定された場合、着目したクラスタがリージョンの末尾のクラスタであると判定された場合、または着目したクラスタが不揮発化された４つのライトデータＤ３〜Ｄ６からなる一塊のデータの末尾のクラスタであると判定された場合、不揮発化装置１２０は、更新通知の生成を行う。
【０１７４】
以下に、第３の実施形態のメモリシステム１の具体的な動作を説明する。
【０１７５】
図２１は、第３の実施形態の不揮発化装置１２０の動作を説明するための模式的かつ例示的なフローチャートである。不揮発化装置１２０は、コマンド解析装置１１０から論理アドレスおよびライトデータを受信すると、不揮発化装置１２０は、受信したライトデータをバッファメモリ１２１に格納する（Ｓ７０１）。
【０１７６】
そして、不揮発化装置１２０は、バッファメモリ１２１に格納されたライトデータの量が１ページの量に達したか否かを判定する（Ｓ７０２）。バッファメモリ１２１に格納されたライトデータの量が１ページの量に達することは、不揮発化処理の実行のトリガ条件の一例である。不揮発化処理の実行のトリガ条件はこれに限定されない。
【０１７７】
バッファメモリ１２１に格納されたライトデータの量が１ページの量に達した場合（Ｓ７０２：Ｙｅｓ）、不揮発化装置１２０は、当該１ページの量のライトデータを不揮発化する（Ｓ７０３）。当該１ページの量のライトデータが、それぞれ異なるライトコマンドによって書き込みが要求された複数のライトデータを含む場合、Ｓ７０３では、当該複数のライトデータが不揮発化される。
【０１７８】
続いて、不揮発化装置１２０は、更新通知を生成する通知生成処理を実行する（Ｓ７０４）。なお、更新通知は、論理アドレスＬＡ＿ＨＥＡＤ＿ＮＥＷ、物理アドレスＰＡ＿ＨＥＡＤ＿ＮＥＷ、および長さＬ＿ＮＥＷに加えて、マージフラグを備える。
【０１７９】
マージフラグは、２つの対応関係を１つのエントリに記録するか、または２つの対応関係をそれぞれ異なるエントリに記録するかを示す。ここでは一例として、マージフラグとしてＯＮが設定されていることは、既存のエントリを更新する形で対応関係を記録することが要求されていることを意味することとする。また、マージフラグとしてＯＦＦが設定されていることは、対応関係を新しいエントリに記録することが要求されていることを意味することとする。マージフラグの詳細は、動作の説明において明らかになる。
【０１８０】
不揮発化装置１２０は、生成した更新通知を差分テーブル管理装置１４０に送信する（Ｓ７０５）。そして、制御がＳ７０１に移行する。
【０１８１】
図２２は、第３の実施形態にかかる通知生成処理の動作を説明するための模式的かつ例示的なフローチャートである。
【０１８２】
まず、不揮発化装置１２０は、不揮発化された１ページの量のライトデータから、１つのライトコマンドによって書き込みが要求されたライトデータを選択する（Ｓ８０１）。
【０１８３】
そして、以降の処理では、Ｓ８０１の処理によって選択されたライトデータを構成する１以上のクラスタのうちの、当該ライトデータの末尾、リージョンの末尾、および不揮発化されたデータの最後のクラスタを検出する処理が実行される。以降では、Ｓ８０１の処理によって選択されたライトデータを、対象のライトデータと表記する。
【０１８４】
具体的には、不揮発化装置１２０は、以降のループ処理で使用するループインデックスであるｉを０で初期化する（Ｓ８０２）。そして、不揮発化装置１２０は、ループインデックスｉの値を１だけインクリメントして（Ｓ８０３）、対象のライトデータの先頭からｉ番目のクラスタが対象のライトデータの末尾のクラスタに該当するか否かを判定する（Ｓ８０４）。
【０１８５】
対象のライトデータの先頭からｉ番目のクラスタが対象のライトデータの末尾のクラスタに該当しない場合（Ｓ８０４：Ｎｏ）、不揮発化装置１２０は、対象のライトデータの先頭からｉ番目のクラスタがリージョンの末尾のクラスタに該当するか否かを判定する（Ｓ８０５）。
【０１８６】
なお、クラスタがリージョンの末尾のクラスタに該当するか否かは、当該クラスタの論理アドレスを参照することによって判定され得る。リージョンの境界の論理アドレスは、リージョンのサイズに応じて一意に決まるからである。
【０１８７】
対象のライトデータの先頭からｉ番目のクラスタがリージョンの末尾のクラスタに該当しない場合（Ｓ８０５：Ｎｏ）、不揮発化装置１２０は、さらに、対象のライトデータの先頭からｉ番目のクラスタが、不揮発化が完了したクラスタのうちの最後のクラスタに該当するか否かを判定する（Ｓ８０６）。
【０１８８】
対象のライトデータの先頭からｉ番目のクラスタが当該ライトデータの末尾のクラスタに該当する場合（Ｓ８０４：Ｙｅｓ）、対象のライトデータの先頭からｉ番目のクラスタがリージョンの末尾のクラスタに該当する場合（Ｓ８０５：Ｙｅｓ）、または対象のライトデータの先頭からｉ番目のクラスタが不揮発化が完了したクラスタのうちの最後のクラスタに該当する場合（Ｓ８０６：Ｙｅｓ）、不揮発化装置１２０は、１つの更新通知を生成する（Ｓ８０７）。
【０１８９】
当該更新通知は、論理アドレスＬＡ＿ＨＥＡＤ＿ＮＥＷ、物理アドレスＰＡ＿ＨＥＡＤ＿ＮＥＷ、長さＬ＿ＮＥＷ、およびマージフラグを備える。ここで、ＬＡ＿ＨＥＡＤ＿ＮＥＷは、対象のライトデータの先頭のクラスタの論理アドレスである。ＰＡ＿ＨＥＡＤ＿ＮＥＷは、対象のライトデータの先頭のクラスタが格納された位置を示す物理アドレスである。Ｌ＿ＮＥＷは、対象のライトデータの先頭のクラスタからｉ番目のクラスタまでの合計のサイズである。マージフラグとしては、Ｓ８０７では、任意の値が設定され得る。
【０１９０】
続いて、不揮発化装置１２０は、ＬＡ＿ＨＥＡＤ＿ＮＥＷがリージョンの先頭の論理アドレスに該当するか否かを判定する（Ｓ８０８）。ＬＡ＿ＨＥＡＤ＿ＮＥＷがリージョンの先頭の論理アドレスに該当する場合（Ｓ８０８：Ｙｅｓ）、不揮発化装置１２０は、ＯＦＦを示す値をマージフラグに設定する（Ｓ８０９）。また、ＬＡ＿ＨＥＡＤ＿ＮＥＷがリージョンの先頭の論理アドレスに該当しない場合（Ｓ８０８：Ｎｏ）、不揮発化装置１２０は、ＯＮを示す値をマージフラグに設定する（Ｓ８１０）。
【０１９１】
Ｓ８０９またはＳ８１０の後、通知生成処理の動作が終了する。
【０１９２】
なお、不揮発化された１ページの量のライトデータが、それぞれ異なるライトコマンドによって書き込みが要求された複数のライトデータを含む場合、不揮発化装置１２０は、図２２に示される一連の処理を、それぞれ異なるライトコマンドによって書き込みが要求された複数のライトデータのそれぞれに対して実行する。
【０１９３】
図２３は、第３の実施形態の差分テーブル管理装置１４０による例外条件の判定の動作を説明するための模式的かつ例示的なフローチャートである。
【０１９４】
差分テーブル管理装置１４０は、受信した更新通知が示す対応関係を差分テーブル３００に記録する過程において、通知された対応関係が連続性を有すると判定された場合に、例外条件が満たされているか否かを判定する（例えば図１１のＳ４０５、または図１７のＳ６０５）。
【０１９５】
第３の実施形態では、差分テーブル管理装置１４０は、更新通知に含まれるマージフラグを参照して、当該マージフラグがＯＮを示すか否かを判定する（Ｓ９０１）。当該マージフラグがＯＮを示す場合（Ｓ９０１：Ｙｅｓ）、差分テーブル管理装置１４０は、例外条件が満たされていないと判定する（Ｓ９０２）。当該マージフラグがＯＮを示していない場合（Ｓ９０１：Ｎｏ）、つまり当該マージフラグがＯＦＦを示す場合、差分テーブル管理装置１４０は、例外条件が満たされていると判定する（Ｓ９０３）。Ｓ９０２またはＳ９０３の後、例外条件が満たされているか否かの判定の動作が終了する。
【０１９６】
つまり、更新通知が示す、ライトデータが書き込まれた範囲が、差分テーブル３００にすでに対応関係が記録された範囲に論理アドレスおよび物理アドレスの両方の点で後続する、という条件が満たされている場合であっても、当該ライトデータが書き込まれた範囲の先頭がリージョンの先頭に該当する場合には、差分テーブル管理装置１４０は、当該更新通知が示す対応関係を、空きエントリに記録する。
【０１９７】
更新通知が示す、ライトデータが書き込まれた範囲が、差分テーブル３００にすでに対応関係が記録された範囲に論理アドレスおよび物理アドレスの両方の点で後続する、という条件が満たされている場合でかつ、当該ライトデータが書き込まれた範囲の先頭がリージョンの先頭に該当しない場合には、差分テーブル管理装置１４０は、当該更新通知が示す対応関係を、既存のエントリの内容を更新する形で差分テーブル３００に記録する。
【０１９８】
これによって、リージョンの境界の前の範囲にかかる対応関係と、リージョンの境界の後の範囲にかかる対応関係と、をそれぞれ異なるエントリに記録することが可能となる。
【０１９９】
図２４は、第３の実施形態にかかる反映装置１５０が実行する反映処理の具体例を説明するための模式的かつ例示的なフローチャートである。本図に示される一連の処理は、図１２のＳ５０２において実行される。
【０２００】
まず、反映装置１５０は、反映処理の対象のエントリを選択する（Ｓ１００１）。反映処理の対象のエントリを選択する方法は、特定の方法に限定されない。例えば、反映装置１５０は、有効な状態になったタイミングが最も古いエントリを、反映処理の対象のエントリとして選択することができる。
【０２０１】
続いて、反映装置１５０は、選択されたエントリに対応するリージョン（対象のリージョンと表記する）を特定する（Ｓ１００２）。反映装置１５０は、選択されたエントリが示す論理アドレス範囲を参照することによって、対象のリージョンを特定することができる。
【０２０２】
第３の実施形態では、異なるリージョンにかかる２つの対応関係は、それぞれ異なるエントリに記録されることとしているので、Ｓ１００２では、１つのエントリにつき１つのリージョンが対象のリージョンとして特定される。
【０２０３】
続いて、反映装置１５０は、対象のリージョンに対応する論物変換テーブル２０２（サブテーブル２１１）をＮＡＮＤメモリ２００から読み出して（Ｓ１００３）、読み出されたサブテーブル２１１を更新する（Ｓ１００４）。つまり、反映装置１５０は、読み出されたサブテーブル２１１に対象のエントリの内容を反映させる。
【０２０４】
続いて、反映装置１５０は、更新後のサブテーブル２１１をＮＡＮＤメモリ２００に書き込み（Ｓ１００５）、反映処理が完了する。
【０２０５】
なお、メモリコントローラ１００に論物変換テーブル２０２の一部または全部がキャッシュされるキャッシュメモリを有する場合がある。キャッシュメモリに、対象のリージョンに対応するサブテーブル２１１が格納されている場合には、反映装置１５０は、Ｓ１００３の処理において、キャッシュメモリからサブテーブル２１１を取得してもよい。
【０２０６】
また、反映装置１５０は、更新後のサブテーブル２１１をキャッシュメモリに残しておき、更新後のサブテーブル２１１のＮＡＮＤメモリ２００への書き込みの実行を後回し（postpone）にしてもよい。そして、キャッシュメモリに残されたサブテーブル２１１のＮＡＮＤメモリ２００への書き込みの実行前に、当該サブテーブル２１１の更新が再び必要になった場合には、反映装置１５０は、当該サブテーブル２１１のＮＡＮＤメモリ２００への書き込みの実行の前に、当該サブテーブル２１１をキャッシュメモリから取得して更新してもよい。
【０２０７】
このように、反映装置１５０がキャッシュメモリを利用することによって、ＮＡＮＤメモリ２００からサブテーブル２１１を読み出す処理（Ｓ１００３）の実行頻度、およびＮＡＮＤメモリ２００にサブテーブル２１１を書き込む処理（Ｓ１００５）の実行頻度を、低減することが可能である。
【０２０８】
以上述べたように、第３の実施形態によれば、メモリコントローラ１００は、不揮発化されたライトデータが位置する論理アドレス範囲がリージョンの境界に対応した論理アドレスを跨ぐ場合、当該論理アドレスの前の範囲にかかる対応関係と、当該論理アドレスの後の範囲にかかる対応関係と、をそれぞれ異なるエントリに記録する。
【０２０９】
これによって、エントリの数とＮＡＮＤメモリ２００から読み出すべきサブテーブル２１１の数とを対応させることが可能である。よって、ＮＡＮＤメモリ２００から読み出すべきサブテーブル２１１の数を見積もる処理が不要となる。
【０２１０】
また、メモリコントローラ１００は、反映処理の際に、反映処理の対象の１以上のエントリのそれぞれに対応したサブテーブル２１１を特定し、特定したサブテーブル２１１をＮＡＮＤメモリ２００から読み出す。そして、メモリコントローラ１００は、読み出したサブテーブル２１１を更新し、更新後のサブテーブル２１１をＮＡＮＤメモリ２００に書き込む。
【０２１１】
これによって、反映処理の対象のエントリの数に対応したサブテーブル２１１が更新される。
【０２１２】
また、上記の構成により、不揮発化装置１２０は、不揮発化されたライトデータが位置する論理アドレス範囲がリージョンの境界に対応した論理アドレスを跨ぐ場合、当該論理アドレスの前の範囲にかかる対応関係を示す更新通知と、当該論理アドレスの後の範囲にかかる対応関係を示す更新通知と、を生成するとともに、当該論理アドレスの後の範囲にかかる対応関係を示す更新通知に、マージフラグとしてＯＦＦを設定する。
【０２１３】
マージフラグとしてＯＦＦが設定された場合、差分テーブル管理装置１４０は、例外条件が満たされたと判定し、通知された対応関係を、空きエントリに記録する。つまり、差分テーブル管理装置１４０は、リージョンの境界に対応した論理アドレスの前の範囲にかかる対応関係と、リージョンの境界に対応した論理アドレスの後の範囲にかかる対応関係と、をそれぞれ異なるエントリに記録することが可能となる。
【０２１４】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０２１５】
１  メモリシステム、２  ホスト、１００  メモリコントローラ、１１０  コマンド解析装置、１２０  不揮発化装置、１２１  バッファメモリ、１３０  リード処理装置、１４０  差分テーブル管理装置、１４１  ＳＲＡＭ、１４２  レジスタ、１５０  反映装置、２００  ＮＡＮＤメモリ、２０１  ライトデータ、２０２  論物変換テーブル、２１０  ルートテーブル、２１１  サブテーブル、３００  差分テーブル、４００  テーブル管理情報。
【図１】
2020113187.tif 000003
【図２】
2020113187.tif 000004
【図３】
2020113187.tif 000005
【図４】
2020113187.tif 000006
【図５】
2020113187.tif 000007
【図６】
2020113187.tif 000008
【図７】
2020113187.tif 000009
【図８】
2020113187.tif 000010
【図９】
2020113187.tif 000011
【図１０】
2020113187.tif 000012
【図１１】
2020113187.tif 000013
【図１２】
2020113187.tif 000014
【図１３】
2020113187.tif 000015
【図１４】
2020113187.tif 000016
【図１５】
2020113187.tif 000017
【図１６】
2020113187.tif 000018
【図１７】
2020113187.tif 000019
【図１８】
2020113187.tif 000020
【図１９】
2020113187.tif 000021
【図２０】
2020113187.tif 000022
【図２１】
2020113187.tif 000023
【図２２】
2020113187.tif 000024
【図２３】
2020113187.tif 000025
【図２４】
2020113187.tif 000026