(57)【要約】【課題】任意の論理アドレスに任意の長さのデータを書き込むことができるメモリシステムを実現する。【解決手段】実施形態によれば、メモリシステムは、第１のデータが書き込まれるべき第１の論理アドレスと第１のデータの長さとを指定する書き込み要求をホストから受信する。メモリシステムは、第１のデータを不揮発性メモリに書き込み、第１のデータが書き込まれた不揮発性メモリ上の物理記憶位置を示す第１の物理アドレスと、第１のデータの長さとを、第１の論理アドレスに対応する論理物理アドレス変換テーブルのエントリに格納する。メモリシステムは、第１の論理アドレスを指定する読み出し要求を受信した場合、前記論理物理アドレス変換テーブルから前記第１の物理アドレスと前記長さとを取得し、前記不揮発性メモリから前記第１のデータを読み出す。【選択図】図２
2019020788.tif 000002
【特許請求の範囲】
【請求項１】
ホストに接続可能なメモリシステムであって、
不揮発性メモリと、
前記不揮発性メモリに電気的に接続され、前記不揮発性メモリを制御するように構成されたコントローラとを具備し、
前記コントローラは、
複数の論理アドレスに対応する複数のエントリを含む論理物理アドレス変換テーブルを管理し、
第１のデータが書き込まれるべき第１の論理アドレスと前記第１のデータの長さとを指定する書き込み要求を前記ホストから受信し、
前記第１のデータを前記不揮発性メモリに書き込み、
前記第１のデータが書き込まれた前記不揮発性メモリ上の物理記憶位置を示す第１の物理アドレスと、前記第１のデータの前記長さとを、前記第１の論理アドレスに対応する前記論理物理アドレス変換テーブルのエントリに格納し、
前記第１の論理アドレスを指定する読み出し要求を前記ホストから受信した場合、前記論理物理アドレス変換テーブルから前記第１の物理アドレスと前記長さとを取得し、前記取得した第１の物理アドレスと前記取得した長さとに基づいて、前記不揮発性メモリから前記第１のデータを読み出すように構成されている、メモリシステム。
【請求項２】
前記不揮発性メモリ上の前記物理記憶位置は、前記不揮発性メモリ内のブロック番号と、ブロック内の位置とによって表される請求項１記載のメモリシステム。
【請求項３】
前記不揮発性メモリ上の前記物理記憶位置は、前記不揮発性メモリ内のブロック番号と、ブロック内のページ番号と、ページ内の位置とによって表される請求項１記載のメモリシステム。
【請求項４】
前記第１のデータは、一つの論理アドレスに対応するデータの長さが可変である可変長データである請求項１記載のメモリシステム。
【請求項５】
前記第１のデータに含まれる第１のデータ部分が前記不揮発性メモリ内の第１のブロックに書き込まれ、前記第１のデータに含まれる第２のデータ部分が前記不揮発性メモリ内の第２のブロックに書き込まれた場合、前記コントローラは、前記第１のデータ部分が書き込まれた前記第１のブロック上の物理記憶位置を示す第１の物理アドレスと、前記第１のデータ部分の長さと、前記第２のデータ部分が書き込まれた前記第２のブロック上の物理記憶位置を示す第２の物理アドレスと、前記第２のデータ部分の長さとを、前記第１の論理アドレスに対応する前記論理物理アドレス変換テーブルのエントリに格納する請求項１記載のメモリシステム。
【請求項６】
不揮発性メモリを制御する制御方法であって、
複数の論理アドレスに対応する複数のエントリを含む論理物理アドレス変換テーブルを管理することと、
第１のデータが書き込まれるべき第１の論理アドレスと前記第１のデータの長さとを指定する書き込み要求をホストから受信することと、
前記第１のデータを前記不揮発性メモリに書き込み、
前記第１のデータが書き込まれた前記不揮発性メモリ上の物理記憶位置を示す第１の物理アドレスと、前記第１のデータの前記長さとを、前記第１の論理アドレスに対応する前記論理物理アドレス変換テーブルのエントリに格納することと、
前記第１の論理アドレスを指定する読み出し要求を前記ホストから受信した場合、前記論理物理アドレス変換テーブルから前記第１の物理アドレスと前記長さとを取得し、前記取得した第１の物理アドレスと前記取得した長さとに基づいて、前記不揮発性メモリから前記第１のデータを読み出すこととを具備する制御方法。
【請求項７】
前記不揮発性メモリ上の前記物理記憶位置は、前記不揮発性メモリ内のブロック番号と、ブロック内の位置とによって表される請求項６記載の制御方法。
【請求項８】
前記不揮発性メモリ上の前記物理記憶位置は、前記不揮発性メモリ内のブロック番号と、ブロック内のページ番号と、ページ内の位置とによって表される請求項６記載の制御方法。
【請求項９】
前記第１のデータは、一つの論理アドレスに対応するデータの長さが可変である可変長データである請求項６記載の制御方法。
【請求項１０】
前記第１のデータに含まれる第１のデータ部分が前記不揮発性メモリ内の第１のブロックに書き込まれ、前記第１のデータに含まれる第２のデータ部分が前記不揮発性メモリ内の第２のブロックに書き込まれた場合、前記第１のデータ部分が書き込まれた前記第１のブロック上の物理記憶位置を示す第１の物理アドレスと、前記第１のデータ部分の長さと、前記第２のデータ部分が書き込まれた前記第２のブロック上の物理記憶位置を示す第２の物理アドレスと、前記第２のデータ部分の長さとを、前記第１の論理アドレスに対応する前記論理物理アドレス変換テーブルのエントリに格納することをさらに具備する請求項６記載の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、不揮発性メモリを制御する技術に関する。
【背景技術】
【０００２】
近年、様々な情報処理装置のメインストレージとして、不揮発性メモリを備えるメモリシステムが広く利用されている。このようなメモリシステムの一つとして、ＮＡＮＤフラッシュ技術ベースのソリッドステートドライブ（ＳＳＤ）が知られている。
【０００３】
ＳＳＤのようなメモリシステムにおいては、論理アドレスを不揮発性メモリの物理アドレスに変換するためのアドレス変換が、アドレス変換テーブルを使用して実行される。
【０００４】
通常のアドレス変換テーブルにおいては、論理アドレスそれぞれに対応する物理アドレスそれぞれが管理される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１６−２１２７１３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、通常のＳＳＤにおいては、一つの論理アドレスに対応するデータは固定長であり、任意の論理アドレスに任意の長さのデータを書き込むことはできない。
【０００７】
本発明が解決しようとする課題は、任意の論理アドレスに任意の長さのデータを書き込むことができるメモリシステムおよび制御方法を提供することである。
【課題を解決するための手段】
【０００８】
実施形態によれば、ホストに接続可能なメモリシステムは、不揮発性メモリと、前記不揮発性メモリに電気的に接続され、前記不揮発性メモリを制御するように構成されたコントローラとを具備する。前記コントローラは、複数の論理アドレスに対応する複数のエントリを含む論理物理アドレス変換テーブルを管理する。前記コントローラは、第１のデータが書き込まれるべき第１の論理アドレスと前記第１のデータの長さとを指定する書き込み要求を前記ホストから受信する。前記コントローラは、前記第１のデータを前記不揮発性メモリに書き込み、前記第１のデータが書き込まれた前記不揮発性メモリ上の物理記憶位置を示す第１の物理アドレスと、前記第１のデータの前記長さとを、前記第１の論理アドレスに対応する前記論理物理アドレス変換テーブルのエントリに格納する。前記コントローラは、前記第１の論理アドレスを指定する読み出し要求を前記ホストから受信した場合、前記論理物理アドレス変換テーブルから前記第１の物理アドレスと前記長さとを取得し、前記取得した第１の物理アドレスと前記取得した長さとに基づいて、前記不揮発性メモリから前記第１のデータを読み出す。
【図面の簡単な説明】
【０００９】
【図１】実施形態に係るメモリシステムの構成例を示すブロック図。
【図２】同実施形態のメモリシステムによって管理される可変長ルックアップテーブルの構成例を示す図。
【図３】固定長ルックアップテーブルの構成例を示す図。
【図４】同実施形態のメモリシステムに適用される、可変長データ用の書き込み要求の例を示す図。
【図５】同実施形態のメモリシステムに適用される、可変長データ用の読み出し要求の例を示す図。
【図６】同実施形態のメモリシステムによって実行される書き込み動作の手順を示すシーケンス図。
【図７】同実施形態のメモリシステムによって管理される、フリーブロックプールとアクティブブロックプールと書き込み先ブロックとの関係を示す図。
【図８】同実施形態のメモリシステムによって管理される可変長ルックアップテーブルの別の構成例を示す図。
【図９】同実施形態のメモリシステムによって実行される読み出し動作の手順を示すシーケンス図。
【図１０】同実施形態のメモリシステムによって管理される可変長ルックアップテーブルのさらに別の構成例を示す図。
【図１１】同実施形態のメモリシステムによって管理される階層ルックアップテーブル（マルチレベル・ルックアップテーブル）の構成例を示す図。
【図１２】同実施形態のメモリシステムのハードウェア構成例を示すブロック図。
【図１３】同実施形態のメモリシステム内のＮＡＮＤインタフェースと複数のＮＡＮＤ型フラッシュメモリチップとの関係を示すブロック図。
【図１４】同実施形態のメモリシステムにおいて使用される論理ブロック（スーパーブロック）の構成例を示す図。
【図１５】同実施形態のメモリシステムの不揮発性メモリを論理的に分割することによって得られる複数の領域を説明するための図。
【図１６】同実施形態のメモリシステム内の複数の領域とこれら領域に対応する論理アドレス空間とこれら領域に対応するルックアップテーブルとの関係を示すブロック図。
【発明を実施するための形態】
【００１０】
以下、図面を参照して、実施形態を説明する。  
【００１１】
まず、図１を参照して、実施形態に係るメモリシステムを含む情報処理システム１の構成を説明する。
【００１２】
このメモリシステムは、不揮発性メモリにデータを書き込み、不揮発性メモリからデータを読み込むように構成された半導体ストレージデバイスである。このメモリシステムは、例えば、ＮＡＮＤ型フラッシュメモリを備えたソリッドステートドライブ（ＳＳＤ）３として実現されている。
【００１３】
情報処理システム１は、ホスト（ホストデバイス）２と、ＳＳＤ３とを含む。ホスト２は、ＳＳＤ３をアクセスする情報処理装置（コンピューティングデバイス）である。ホスト２は、様々なユーザのアプリケーションプログラムを実行するサーバ計算機であってもよいし、パーソナルコンピュータであってもよい。ＳＳＤ３は、ホスト２として機能する情報処理装置のメインストレージとして使用され得る。ＳＳＤ３は、この情報処理装置に内蔵されてもよいし、この情報処理装置にケーブルまたはネットワークを介して接続されてもよい。
【００１４】
ホスト２とＳＳＤ３とを相互接続するためのインタフェースとしては、ＳＣＳＩ、Ｓｅｒｉａｌ  Ａｔｔａｃｈｅｄ  ＳＣＳＩ（ＳＡＳ）、ＡＴＡ、Ｓｅｒｉａｌ  ＡＴＡ（ＳＡＴＡ）、ＰＣＩ  Ｅｘｐｒｅｓｓ（ＰＣＩｅ）、Ｅｔｈｅｒｎｅｔ（登録商標）、Ｆｉｂｒｅ  ｃｈａｎｎｅｌ、ＮＶＭ  Ｅｘｐｒｅｓｓ（ＮＶＭｅ）（登録商標）等を使用し得る。
【００１５】
ホスト２は、可変長データ読み書き部１０１を含む。可変長データ読み書き部１０１は、ホスト２（例えば、サーバ計算機）上で動作するソフトウェアとして実現されてもよい。例えば、ＳＳＤ３をファイルの格納またはブロックデバイスのデータの格納に利用するケースにおいては、可変長データ読み書き部１０１は、ホスト２によって実行されるオペレーティングシステムの一部として実現されてもよいし、ホスト２によって実行されるデバイスドライバの一部として実現されてもよい。あるいは、可変長データ読み書き部１０１は、特定のアプリケーションプログラムの一部として実現されていてもよい。
【００１６】
ＳＳＤ３は、コントローラ４および不揮発性メモリ（ＮＡＮＤ型フラッシュメモリ）５を備える。コントローラ４は、ＮＡＮＤ型フラッシュメモリ５を制御するメモリコントローラであり、例えば、システムＬＳＩと称される回路（「制御回路」、または「処理回路」とも称される）によって実現されてもよい。
【００１７】
さらに、ＳＳＤ３は、ランダムアクセスメモリ（ＲＡＭ）６も備えている。ＲＡＭ６は、コントローラ４に接続されたＤＲＡＭであってもよいし、コントローラ４に内蔵されたＳＲＡＭであってもよい。
【００１８】
コントローラ４は、ホスト要求処理部２１と、可変長ルックアップテーブル（ＬＵＴ）管理部２２を備える。ホスト要求処理部２１および可変長ＬＵＴ管理部２２の各々は、コントローラ４内のＣＰＵによって実行されるファームウェアによって実現されてもよい。あるいは、ホスト要求処理部２１および可変長ＬＵＴ管理部２２の各々の全部または一部は、コントローラ４内のハードウェアによって実現されてもよい。
【００１９】
ＮＡＮＤ型フラッシュメモリ５の領域（記憶領域）それぞれは、データ領域５Ａと管理領域５Ｂとに大別される。データ領域５Ａは、ホスト２からのデータ（ユーザデータ）を格納するための領域である。管理領域５Ｂは、ＳＳＤ３の動作を管理するための管理情報を格納するための領域である。管理情報の例には、可変長ルックアップテーブル（ＬＵＴ）３２が含まれる。
【００２０】
この可変長ＬＵＴ３２は、複数の論理アドレスに対応する複数のエントリを含む論理物理アドレス変換テーブルであり、複数の論理アドレスそれぞれとＮＡＮＤ型フラッシュメモリ５上の物理アドレスそれぞれとの間の対応関係を管理するために使用される。この可変長ＬＵＴ３２は、ＮＡＮＤ型フラッシュメモリ５の管理領域５Ｂ内に格納されている。可変長ＬＵＴ３２へのリード／ライトアクセスを高速に実行するために、可変長ＬＵＴ３２の全部または一部の複製が、ＲＡＭ６にキャッシュ（論理物理アドレス変換テーブルキャッシュ）として置かれてもよい。ＲＡＭ６の領域の他の一部は、ライトデータを一時的に格納するためのライトバッファ３１として利用されてもよい。
【００２１】
書き込み順序に制限のある不揮発メモリであるＮＡＮＤ型フラッシュメモリ５に効率的に書き込みを行なうためには、ホスト２によって指定される論理記憶位置（論理アドレス）とＮＡＮＤ型フラッシュメモリ５上の物理記憶位置（物理アドレス）との対応関係を動的に変更する必要がある。そのため、一般的には、論理アドレスそれぞれと物理アドレスそれぞれとの対応関係がルックアップテーブル（論理物理アドレス変換テーブル）と呼ばれるテーブルによって管理されている。データ書き込み時には、ルックアップテーブルが更新されて、データが書き込まれたＮＡＮＤ型フラッシュメモリ５上の物理記憶位置（物理アドレス）が、ホストによって指定された論理アドレスに関連づけられる。データ読み出し時には、ルックアップテーブルが参照され、これによってリードされるべきデータが格納されているＮＡＮＤ型フラッシュメモリ５上の物理記憶位置（物理アドレス）がルックアップテーブルから取得される。論理アドレスとしては、例えば、論理ブロックアドレス（ＬＢＡ）が使用される。
【００２２】
通常のルックアップテーブルは、固定長の単位（たとえば４ＫＢの単位）でＬＢＡそれぞれと物理アドレスそれぞれとの対応関係を管理する。これは、既存のＳＳＤは、ハードディスクの固定長のセクタに由来するＬＢＡをインタフェースとして提供しているためである。このため、既存のＳＳＤでは、一つのＬＢＡに対応する論理記憶位置に書き込可能なデータは固定長データに限られる。固定長データとは、一つの論理アドレスに対応するデータの長さが固定のデータを意味する。例えば、一つの論理アドレス（例えば一つのＬＢＡ）が固定長（例えば４Ｋバイト）の論理セクタを示す場合には、このＬＢＡに対応する論理記憶位置に書き込可能なデータはこの固定サイズ（例えば４Ｋバイト）を有する固定長データに限られる。ユーザが一つの論理アドレスに固定サイズのデータ、つまり固定長データ、を記録したい場合はこのインタフェースで充分である。
【００２３】
しかし、可変長データを取り扱うシステムにおいては、ホストは、可変長データを固定長データに変換する処理や、どの可変長データがどの固定長データ内のどの位置に記録されているかを示すメタデータを管理する処理などを行うことが必要となる。
【００２４】
可変長データとは、一つの論理アドレスに対応するデータの長さが可変であるデータを意味する。
【００２５】
例えば、キー・バリュー・ストア・システムでは、ｖａｌｕｅの長さは可変である。また、ホストがデータを圧縮し、圧縮されたデータをＳＳＤに格納するケースにおいては、圧縮されたデータの長さは、その圧縮率によって可変長になる。ＳＳＤが圧縮機能を有する場合も、同様に、圧縮されたデータの長さは可変長になる。
【００２６】
そのため、これらのシステムでは、ホストは、（１）大きな可変長データを複数の固定長データ（複数のブロックデータ）に分割する処理、（２）小さい可変長データを複数個まとめことによって、あるいは小さい可変長データにダミーデータを付加することによって、小さい可変長データを固定長データに変換する処理、（３）どの可変長データをどの固定長データのどの位置に記録したかを示すメタデータを別途管理する処理、といった煩雑な処理を行なう必要が生じる。
【００２７】
また、通常のファイルシステムにおいても、ファイルのサイズはファイル毎に異なるため、上述の複雑な処理を実行することが必要とされる。
【００２８】
これら処理によって、（１）ホストのＣＰＵの処理時間の増加、（２）メタデータの読み書きによるメモリアクセス時間の増加、（３）メタデータ／ダミーデータの書き込みによるメモリリソースの消費量の増加、（４）メモリリソースの消費量の増加によるライトアンプリフィケーションの増加、（５）ライトアンプリフィケーションの増加によるＳＳＤの寿命の減少、といった非効率が生じる。
【００２９】
本実施形態では、ＳＳＤ３は、ＮＡＮＤ型フラッシュメモリ５上のどの物理記憶位置からどれだけの長さのデータを格納したかを可変長ＬＵＴ３２に格納し、これによって任意の論理アドレスに任意の長さのデータを格納することを可能にする。換言すれば、可変長ＬＵＴ３２は、ある論理アドレスに対応するＳＳＤ３内の論理記憶位置に、ホスト２によって指定される任意のデータ長に対応するサイズを有する物理記憶領域を割り当てることを可能にする。これにより、固定長データよりも小さい可変長データを書き込む場合であっても、この可変長データにダミーデータを付加することによってこの可変長データを固定長データに変換する処理を実行することなく、この可変長データを任意の論理アドレスに書き込むことができる。したがって、ＮＡＮＤ型フラッシュメモリ５においては、データの格納に必要な物理記憶領域のみを割り当てることが可能となる。
【００３０】
一般には、もし可変長データをこのような形式で格納するストレージシステムを実現したならば、あるＬＢＡに対応する以前のデータ（古いデータ）とこのＬＢＡに対応する新データ（更新データ）のサイズが異なる場合に、（１）以前のデータが格納されていた領域に新データが入りきれない、（２）以前のデータが格納されていた領域の一部に空きが生じる、という問題が生じる。そのため、通常のファイルシステムでは、前述の煩雑な処理によって、ライトデータを複数の固定長データに分割し、これら複数の固定長データをストレージに格納することが多い。
【００３１】
しかし、ＮＡＮＤ型フラッシュメモリ５においては、データはＮＡＮＤ型フラッシュメモリ５内のブロックの先頭からしか書けない。このため、データの更新時には、古いデータを元の物理記憶位置に置き去りにして新データを別の物理記憶位置に書き込み、さらに、必要に応じてガベージコレクションによって古いデータを消去する、という制御が行われる。このため、ＮＡＮＤ型フラッシュメモリ５にデータを書き込むＳＳＤにおいては、（１）以前のデータが格納されていた領域に新データが入りきれない、（２）以前のデータが格納されていた領域の一部に空きが生じる、という上記の問題は、そもそも生じない。このことは、書き込み順序に制限のある不揮発メモリを使用して可変長データを管理するシステムに独自の特長であるといえる。
【００３２】
図１の情報処理システム１においては、ホスト２の可変長データ読み書き部１０１は、可変長データの書き込みまたは読み出しをＳＳＤ３に要求する。上述したように、可変長データは、一つの論理アドレスに対応するデータの長さが可変であるデータを意味する。可変長データ用の書き込み要求は、データ（ライトデータ）が書き込まれるべき論理アドレスと、このライトデータの長さ（つまり、この論理アドレスに書き込まれるべきデータの長さ）とを指定する。可変長データ用の読み出し要求は、読み出すべきデータの論理アドレスのみを指定すればよい。
【００３３】
ＳＳＤ３においては、コントローラ４のホスト要求処理部２１は、書き込み要求をホスト２から受信する。ホスト要求処理部２１は、ホスト２から受信したライトデータ（可変長データＤｘ）をＮＡＮＤ型フラッシュメモリ５に書き込む。
【００３４】
より詳しくは、ホスト要求処理部２１は、ＮＡＮＤ型フラッシュメモリ５のフリーブロック群から割り当てられた現在の書き込み先ブロックにライトデータ（可変長データＤｘ）を書き込む。
【００３５】
そして、ホスト要求処理部２１は、可変長ＬＵＴ管理部２２と共同して、ライトデータ（可変長データＤｘ）が書き込まれたＮＡＮＤ型フラッシュメモリ５上の物理記憶位置を示す物理アドレスと、書き込み要求によって指定されたデータ長（ライトデータの長さ）とを、書き込み要求によって指定された論理アドレスに対応する可変長ＬＵＴ３２内のエントリに格納する。
【００３６】
この論理アドレスを指定する読み出し要求をホスト２から受信した場合、ホスト要求処理部２１は、可変長ＬＵＴ３２から、可変長データＤｘが格納されているＮＡＮＤ型フラッシュメモリ５上の物理記憶位置を示す物理アドレスと、可変長データＤｘのデータ長とを取得する。可変長データＤｘが格納されている物理記憶位置は、可変長データＤｘが格納されているＮＡＮＤ型フラッシュメモリ５内の領域の開始位置である。ホスト要求処理部２１は、取得した物理アドレスと取得したデータ長とに基づいて、ＮＡＮＤ型フラッシュメモリ５から可変長データＤｘを読み出し、読み出した可変長データＤｘをホスト２に返す。
【００３７】
図２は、可変長ＬＵＴ３２の構成例を示す。
【００３８】
可変長ＬＵＴ３２は、論理アドレス（例えば、ここでは、ＬＢＡ０−ＬＢＡｍａｘ）の個数分の複数のＬＵＴエントリを有する。複数のＬＵＴエントリは、複数のＬＢＡにそれぞれ関連づけられている、各ＬＵＴエントリは、データが格納されたＮＡＮＤ型フラッシュメモリ５上の位置（物理記憶位置）を管理するための位置フィールドと、このデータの長さを管理するための長さフィールドとを含んでいてもよい。
【００３９】
ＮＡＮＤ型フラッシュメモリ５上の位置は、ブロック番号とブロック内の位置とを示す物理アドレス（ＰＢＡ）によって表されてもよい。ブロック番号は、このデータが書き込まれたＮＡＮＤ型フラッシュメモリ５内のブロックを示す。ブロック内の位置は、このデータが書き込まれたこのブロック内の位置（ブロック内のオフセット位置）を示す。
【００４０】
ブロック内の位置は、このブロックの先頭からこのブロック内のこの位置までのバイト数によって表されてもよい。これにより、ブロック内の位置をバイト単位の小さい粒度で管理でき、この結果、ＮＡＮＤ型フラッシュメモリ５に密にデータを配置することが可能となる。もちろん、ＬＵＴエントリに格納することが必要なデータ量を減らすために、ブロック内の位置を例えば２５６バイト単位のような粒度で管理してもよい。
【００４１】
あるいは、ＮＡＮＤ型フラッシュメモリ５上の位置は、ブロック番号とブロック内のページ番号とページ内の位置とを示す物理アドレス（ＰＢＡ）によって表されてもよい。ブロック内のページ番号は、このデータが書き込まれた最初のページを示す。ページ内の位置は、このデータが書き込まれたこのページ内の位置（ページ内のオフセット位置）を示す。
【００４２】
ページ内の位置は、このページの先頭からこのページ内のこの位置までのバイト数によって表されてもよい。これにより、ＮＡＮＤ型フラッシュメモリ５に密にデータを配置することが可能となる。もちろん、ＬＵＴエントリに格納することが必要なデータ量を減らすために、ページ内の位置を例えば２５６バイト単位のような粒度で管理してもよい。
【００４３】
データが書き込まれていない論理アドレスに対応するＬＵＴエントリにおいては、あらかじめ定められた定数（ｎｕｌｌ）が位置として格納されてもよい。
【００４４】
書き込みも要求によって指定されるデータの長さも、バイト数によって表されてもよいし、２５６バイト単位のような単位で表されてもよい。
【００４５】
図２に示されているように、ＬＢＡ９に対応する可変長データＤ１１がブロックＢＬＫ１の先頭から始まる領域に書き込まれた場合には、ＬＢＡ９に対応するＬＵＴエントリには、ブロックＢＬＫ１の先頭位置Ｘ１を示す物理アドレス（ＰＢＡ）と、可変長データＤ１１の長さ（ここでは、長さは“５”として示されている）とが格納される。
【００４６】
ＬＢＡ０に対応する可変長データＤ１２がブロックＢＬＫ１の位置Ｘ２から始まる領域に書き込まれた場合には、ＬＢＡ０に対応するＬＵＴエントリには、位置Ｘ２を示す物理アドレス（ＰＢＡ）と、可変長データＤ１２の長さ（ここでは、長さは“７”として示されている）とが格納される。位置Ｘ２は、位置Ｘ１に可変長データＤ１１の長さを加えることによって得られるブロックＢＬＫ１内の位置であってもよい。
【００４７】
ＬＢＡ１２に対応する可変長データＤ１３がブロックＢＬＫ１の位置Ｘ３から始まる領域に書き込まれた場合には、ＬＢＡ１２に対応するＬＵＴエントリには、位置Ｘ３を示す物理アドレスと、可変長データＤ１３の長さ（ここでは、長さは“２”として示されている）とが格納される。位置Ｘ３は、位置Ｘ２に可変長データＤ１２の長さを加えることによって得られるブロックＢＬＫ１内の位置であってもよい。
【００４８】
ＬＢＡ３に対応する可変長データＤ２１がブロックＢＬＫ２の先頭から始まる領域に書き込まれた場合には、ＬＢＡ３に対応するＬＵＴエントリには、ブロックＢＬＫ２の先頭位置Ｙ１を示す物理アドレスと、可変長データＤ２１の長さ（ここでは、長さは“３”として示されている）とが格納される。
【００４９】
ＬＢＡ７に対応する可変長データＤ２２がブロックＢＬＫ２の位置Ｙ２から始まる領域に書き込まれた場合には、ＬＢＡ７に対応するＬＵＴエントリには、ブロックＢＬＫ２の位置Ｙ２を示す物理アドレスと、可変長データＤ２２の長さ（ここでは、長さは“９”として示されている）とが格納される。
【００５０】
可変長ＬＵＴ３２は、階層化された複数のテーブルを含む多段アドレス変換テーブル（階層ＬＵＴ）によって実現されてもよい。この場合、可変長ＬＵＴ３２全体を格納するたに必要な領域をＮＡＮＤ型フラッシュメモリ５上またはＲＡＭ６上に確保するのではなく、データが実際に格納されている論理アドレス範囲に対応する可変長ＬＵＴ３２内のテーブルデータ部それぞれを格納するのに必要な領域のみをＮＡＮＤ型フラッシュメモリ５上またはＲＡＭ６上に確保することが可能となる。よって、データが格納されていない論理アドレス範囲に対応するアドレス変換情報を格納するための物理リソースを割り当てることが不要となる。よって、キー・バリュー・ストアのように可変長データが疎にしか配置されないシステムにおいては、階層ＬＵＴを使う利点が特に大きい。
【００５１】
一般には、可変長データに加えて固定長データの読み書きも行ないたいことが多い。このため、ＳＳＤ３全体を一つのＬＵＴで管理せず、複数のＬＵＴを設け、固定長ＬＵＴと可変長ＬＵＴを混在させてもよい。ＳＳＤ３は、マルチネームスペースコントロール機能を有していてもよい。マルチネームスペースコントロール機能は、一つのストレージデバイスを複数のドライブであるかのように扱うことを可能にするために、ＳＳＤ３に複数の論理アドレス空間（ＬＢＡ空間）を割り当てることを可能にする。複数のネームスペースは互いに独立した複数のＳＳＤ（複数の仮想ＳＳＤ）であるかのように機能することができる。ホスト２があるネームスペースの作成をＳＳＤ３に要求する際に、ホスト２は、作成すべきネームスペースのタイプ（固定長データを扱うためのタイプ＃１−ネームスペース、または可変長データを扱うためのタイプ＃２−ネームスペース）を指定してもよい。
【００５２】
ＳＳＤ３においては、複数のネームスペースに対応する複数のＬＵＴが管理される。可変長データを扱うための各タイプ＃２−ネームスペースのためのＬＵＴは、可変長ＬＵＴ３２によって実現される。固定長データを扱うための各タイプ＃１−ネームスペースのためのＬＵＴは、図３に示す固定長ＬＵＴ３３によって実現される。
【００５３】
タイプ＃１−ネームスペースにおいては、一つのＬＢＡに対応する論理記憶位置に格納可能なデータ長は固定である。図３では、一つのＬＢＡに対応する論理記憶位置に格納可能なデータ長が４Ｋバイト（４ＫＢ）である場合が想定されている。
【００５４】
図３に示されているように、固定長ＬＵＴ３３は、論理アドレス（例えば、ここでは、ＬＢＡ０−ＬＢＡｍａｘ）の個数分の複数のＬＵＴエントリを有する。複数のＬＵＴエントリは、複数のＬＢＡにそれぞれ関連づけられている、各ＬＵＴエントリには、データが格納されたＮＡＮＤ型フラッシュメモリ５上の位置（物理アドレス（ＰＢＡ））が格納される。
【００５５】
固定長ＬＵＴ３３で管理されるＮＡＮＤ型フラッシュメモリ５上の位置（物理記憶位置）それぞれは、４Ｋバイト境界に整合された位置である。
【００５６】
ＬＢＡ９に対応する４ＫＢデータがブロックＢＬＫ１１の先頭から始まる４ＫＢ領域に書き込まれた場合には、ＬＢＡ９に対応するＬＵＴエントリには、ブロックＢＬＫ１１の先頭位置Ｘ１１を示す物理アドレスが格納される。
【００５７】
ＬＢＡ０に対応する４ＫＢデータがブロックＢＬＫ１１の位置Ｘ１２から始まる４ＫＢ領域に書き込まれた場合には、ＬＢＡ０に対応するＬＵＴエントリには、位置Ｘ１２を示す物理アドレスが格納される。
【００５８】
ＬＢＡ１２に対応する４ＫＢデータがブロックＢＬＫ１１の位置Ｘ１３から始まる４ＫＢ領域に書き込まれた場合には、ＬＢＡ１２に対応するＬＵＴエントリには、位置Ｘ１３を示す物理アドレスが格納される。
【００５９】
ＬＢＡ３に対応する４ＫＢデータがブロックＢＬＫ１２の先頭から始まる４ＫＢ領域に書き込まれた場合には、ＬＢＡ３対応するＬＵＴエントリには、ブロックＢＬＫ１２の先頭位置Ｙ１１を示す物理アドレスが格納される。
【００６０】
ＬＢＡ７に対応する４ＫＢデータがブロックＢＬＫ１２の位置Ｙ１２から始まる４ＫＢ領域に書き込まれた場合には、ＬＢＡ７対応するＬＵＴエントリには、ブロックＢＬＫ１２の位置Ｙ１２を示す物理アドレスが格納される。
【００６１】
図４は、通常の書き込み要求（通常のライトコマンド）と可変長データ用の書き込み要求（可変長データ用のライトコマンド）を示す。
【００６２】
通常のライトコマンドは、論理アドレス当たりのデータの長さが固定されている固定長データの書き込みをＳＳＤ３に要求する。
【００６３】
図４の上部に示されているように、通常のライトコマンドは、開始ＬＢＡを指定するパラメータと、論理セクタの数を指定するパラメータとを含む。開始ＬＢＡは、書き込まれるべき最初の論理セクタのアドレスである。論理セクタの数は、書き込まれるべき論理セクタの数、つまりライトデータに対応するＬＢＡの数を示す。ホスト２がＳＳＤ３に送出可能なライトデータのサイズは、固定長（例えば４ＫＢ）の倍数に限られる。
【００６４】
可変長データ用のライトコマンドは、論理アドレス当たりのデータの長さが可変である可変長データの書き込みをＳＳＤ３に要求する。
【００６５】
図４の下部に示されているように、可変長データ用のライトコマンドは、論理アドレスを指定するパラメータと、データ長を指定するパラメータとを含む。論理アドレスは、データ（可変長データ）が書き込まれるべき一つの論理記憶位置（可変長論理記憶位置）のアドレスである。データ長は、一つの論理記憶位置に書き込まれるべきデータの長さを示す。このデータ長は、固定長データの長さ（例えば４ＫＢ）よりも細かい単位、例えば、バイト単位、または２５６バイト単位のような単位、で指定可能である。
【００６６】
図５は、通常の読み出し要求（通常のリードコマンド）と可変長データ用の読み出し要求（可変長データ用のリードコマンド）を示す。
【００６７】
通常のリードコマンドは、論理アドレス当たりのデータの長さが固定されている固定長データの読み出しをＳＳＤ３に要求する。
【００６８】
図５の上部に示されているように、通常のリードコマンドは、開始ＬＢＡを指定するパラメータと、論理セクタの数を指定するパラメータとを含む。開始ＬＢＡは、リードされるべき最初の論理セクタのアドレスである。論理セクタの数は、リードされるべき論理セクタの数、つまりリードされるべきデータに対応するＬＢＡの数を示す。ホスト２がＳＳＤ３からリード可能なデータのサイズは、固定長（例えば４ＫＢ）の倍数に限られる。
【００６９】
可変長データ用のリードコマンドは、論理アドレス当たりのデータの長さが可変である可変長データの読み出しをＳＳＤ３に要求する。
【００７０】
図５の下部に示されているように、可変長データ用のリードコマンドは、論理アドレス（例えばＬＢＡ）を指定するパラメータを含む。論理アドレス（例えばＬＢＡ）は、データ（可変長データ）がリードされるべき一つの論理記憶位置（可変長論理記憶位置）のアドレスである。この一つの論理記憶位置に格納されている可変長データ（このデータの長さは、可変長ＬＵＴ３２によって管理されている）が、ＮＡＮＤ型フラッシュメモリ５から読み出される。
【００７１】
可変長データ用の書き込み要求および可変長データ用の読み出し要求としては、NVMeやSCSIなどの既存のプロトコルで規定されているライトコマンドおよびリードコマンドを拡張した新たな拡張ライトコマンドおよび新たな拡張リードコマンドを利用してもよい。あるいは、可変長データ用の書き込み要求および可変長データ用の読み出し要求のために独自のプロトコルを定義してもよい。
【００７２】
図６のシーケンス図は、書き込み動作の手順を示す。
【００７３】
ホスト２が可変長データの書き込みを行うことを望む場合、可変長データ読み書き部１０１は、ライトデータ（可変長データ）が書き込まれるべき論理アドレスとこのライトデータの長さ（データ長）とを指定する可変長データ用の書き込み要求を、ＳＳＤ３に送信する。この書き込み要求は、ライトデータをさらに含んでいてもよいし、あるいは、ライトデータの代わりに、このライトデータが存在するホストメモリ（ホスト２内のメモリ）上の位置を示すパラメータのみをさらに含んでいてもよい。
【００７４】
ＳＳＤ３のホスト要求処理部２１がこの可変長データ用の書き込み要求をホスト２から受信した時、ホスト要求処理部２１は、論理アドレスと、データ長と、ライトデータとをライトバッファ３１に書き込む（ステップＳ１１）。そして、ホスト要求処理部２１は、この書き込み要求に対する処理が正常に行われたか否かを示す返り値を含むコマンド完了のレスポンスをホスト２に返す。
【００７５】
その後、適切なタイミングで（例えば、ライトバッファ３１が書き込むべきデータで満たされた時、書き込み要求が受信された後に一定時間が経過した時、または、ＮＡＮＤ型フラッシュメモリ５に未書き込みのデータをＮＡＮＤ型フラッシュメモリ５に書き込むことを要求するフラッシュコマンドをホスト２から受信した時、など）、ホスト要求処理部２１は、ライトバッファ３１のライトデータをＮＡＮＤ型フラッシュメモリ５のデータ領域５Ａに書き込む（ステップＳ１２）。ステップＳ１２では、ライトデータは、現在の書き込み先ブロック内の次の利用可能物理記憶位置から始まる領域に書き込まれる。
【００７６】
現在の書き込み先ブロック内の次の利用可能物理記憶位置は、可変長ＬＵＴ管理部２２によって管理されてもよい。可変長ＬＵＴ管理部２２は、現在の書き込み先ブロックの先頭から順にデータが配置されるように、ライトデータが書き込まれるべき物理記憶位置を決める。ライトデータの長さが現在の書き込み先ブロックの残りの利用可能領域の容量よりも大きい場合は、ＮＡＮＤ型フラッシュメモリ５内のフリーブロック群から一つのフリーブロックが選択され、この選択されたフリーブロックが新たな書き込み先ブロックとして割り当てられる。ステップＳ１２では、ホスト要求処理部２１は、書き込み要求によって指定された論理アドレスおよびデータ長を可変長ＬＵＴ管理部２２に通知して、ライトデータを書き込むべきＮＡＮＤ型フラッシュメモリ５上の物理記憶位置を可変長ＬＵＴ管理部２２から得てもよい。
【００７７】
次いで、ライトデータが書き込まれたＮＡＮＤ型フラッシュメモリ５上の物理記憶位置を示す物理アドレスとライトデータの長さとをＬＵＴエントリに格納する処理が実行される（ステップＳ１３）。この処理は、可変長ＬＵＴ管理部２２によって実行されてもよい。
【００７８】
なお、ステップＳ１１の処理の直後にコマンド完了のレスポンスをホスト２に返す代わりに、ステップＳ１３の処理の直後にコマンド完了のレスポンスをホスト２に返してもよい。
【００７９】
また、書き込み先ブロックを無駄なく使いたい場合や、一つのブロックの容量よりも大きなライトデータ（可変長データ）の書き込みに対応したい場合は、複数のブロックにまたがってライトデータ（可変長データ）を書き込むことができるように、可変長ＬＵＴ３２の一つのＬＵＴエントリに複数の位置と複数の長さを格納してもよい。
【００８０】
また、既に可変長データが書かれている論理アドレスに新たな可変長データが上書きされた場合は、以前の可変長データは無効化される。フリーブロックの数がある個数以下に低下したならば、無効化データの量が多い幾つかのブロックに対してガベージコレクション（ＧＣ）が施される。ＧＣでは、無効化データの量が多いこれらブロック（ＧＣソースブロック）内の有効データのみがＧＣデスティネーションブロック（フリーブロック）にコピーされ、これによってこれらＧＣソースブロックがフリーブロックとなる。
【００８１】
図７は、フリーブロックプールとアクティブブロックプールと書き込み先ブロックとのの関係を示す。
【００８２】
図７は、ＳＳＤ３のコントローラ４によって管理される、アクティブブロックプール５１とフリーブロックプール５２と書き込み先ブロックとの関係を示す。
【００８３】
各ブロックの状態は、有効データを格納しているアクティブブロックと、有効データを格納していないフリーブロックとに大別される。アクティブブロックである各ブロックは、アクティブブロックプール５１と称されるリストによって管理される。一方、フリーブロックである各ブロックは、フリーブロックプール５２と称されるリストによって管理される。
【００８４】
本実施形態では、コントローラ４は、フリーブロックプール５２から選択された一つのブロック（フリーブロック）を、ホスト２から受信されたライトデータが書き込まれるべき書き込み先ブロックとして割り当てる。この場合、コントローラ４は、まず、選択されたブロック（フリーブロック）に対する消去動作を実行し、これによってこのブロックを、書き込み可能な消去状態にする。現在の書き込み先ブロックの全体がホスト２からのライトデータで満たされると、コントローラ４は、現在の書き込み先ブロックをアクティブブロックプール５１に移動し、フリーブロックプール５２から新たな一つのブロック（フリーブロック）を新たな書き込み先ブロックとして割り当てる。
【００８５】
アクティブブロックプール５１内のあるブロック内の全ての有効データが、データ更新、アンマップ、ガベージコレクション、等によって無効化されると、コントローラ４は、このブロックをフリーブロックプール５２に移動する。
【００８６】
図８は、可変長ＬＵＴ３２の別の構成例を示す。
【００８７】
この可変長ＬＵＴ３２は、各ＬＵＴエントリに、複数の位置と複数の長さを格納できるように構成されている。図８では、あるデータ（可変長データ）を２つのブロックにまたがって書き込むことを可能にするために各ＬＵＴエントリに２つの位置と２つの長さとを格納することができる可変長ＬＵＴ３２の構成が例示されている。なお、各ＬＵＴエントリに格納される位置と長さのペアの数は、２に限定されず、３以上であってもよい。
【００８８】
ＬＢＡ９に対応する可変長データＤ１００がブロックＢＬＫ１の先頭から始まる領域に書き込まれた場合には、ＬＢＡ９に対応するＬＵＴエントリには、ブロックＢＬＫ１の先頭位置Ｘ１を示す物理アドレスと、可変長データＤ１００の長さ（ここでは、長さは“５”として示されている）とが格納される。
【００８９】
ＬＢＡ０に対応する可変長データＤ１０１の長さがブロックＢＬＫ１の残り領域のサイズがよりも大きい場合には、可変長データＤ１０１の一部（可変長データＤ１０１Ａ）のみがブロックＢＬＫ１の位置Ｘ２から始まる領域に書き込まれる。この場合、ＬＢＡ０に対応するＬＵＴエントリには、位置Ｘ２を示す物理アドレスと、可変長データＤ１０１Ａの長さ（ここでは、長さは“１２”として示されている）とが格納される。可変長データＤ１０１の残り部（可変長データＤ１０１Ｂ）は、別のブロックＢＬＫ２に書き込まれる。可変長データＤ１０１ＢがブロックＢＬＫ２の先頭から始まる領域に書き込まれた場合には、ＬＢＡ０に対応するＬＵＴエントリには、さらに、ブロックＢＬＫ２の先頭位置Ｙ１を示す物理アドレスと、可変長データＤ１０１Ｂの長さ（ここでは、長さは“３”として示されている）とが格納される。
【００９０】
すなわち、ホスト要求処理部２１は、まず、書き込み要求によって指定された可変長データＤ１０１の長さとブロックＢＬＫ１の残り領域のサイズとを比較する。ブロックＢＬＫ１は、現在の書き込み先ブロックである。可変長データＤ１０１の長さがブロックＢＬＫ１の残り領域のサイズを超えるならば、ホスト要求処理部２１は、可変長データＤ１０１を可変長データＤ１０１Ａと可変長データＤ１０１Ｂとに分割する。可変長データＤ１０１Ａは、ブロックＢＬＫ１の残り領域のサイズに対応するデータ長を有するデータである。可変長データＤ１０１Ｂは、可変長データＤ１０１内の残りのデータである。ホスト要求処理部２１は、可変長データＤ１０１ＡをブロックＢＬＫ１に書き込み、そして可変長データＤ１０１Ｂを、新たな書き込み先ブロックとして割り当てられたブロックＢＬＫ２に書き込む。そして、ホスト要求処理部２１は、可変長ＬＵＴ３２を更新して、可変長データＤ１０１Ａが書き込まれた位置（物理記憶位置）Ｘ２を示す物理アドレスと、可変長データＤ１０１Ａの長さと、可変長データＤ１０１Ａが書き込まれた位置（物理記憶位置）Ｙ１を示す物理アドレスと、可変長データＤ１０１Ｂの長さとを、ＬＢＡ０に対応するＬＵＴエントリに格納する。
【００９１】
ＬＢＡ０を指定する読み出し要求を受信したならば、ホスト要求処理部２１は、可変長ＬＵＴ３２から、可変長データＤ１０１Ａが格納されている位置Ｘ１を示す物理アドレスと、可変長データＤ１０１Ａの長さと、可変長データＤ１０１Ｂが格納されている位置Ｙ１を示す物理アドレスと、可変長データＤ１０１Ｂの長さとを取得する。そして、ホスト要求処理部２１は、可変長データＤ１０１Ａおよび可変長データＤ１０１ＢをブロックＢＬＫ１およびブロックＢＬＫ２からそれぞれ読み出し、可変長データＤ１０１Ａおよび可変長データＤ１０１Ｂを結合することによってデータＤ１０１を再生成し、この再生成したデータＤ１０１をホスト２に返す。
【００９２】
図９のシーケンス図は、読み出し動作の手順を示す。
【００９３】
ホスト２が可変長データの読み出しを行うことを望む場合、可変長データ読み書き部１０１は、この可変長データに対応する論理アドレスを指定する読み出し要求を、ＳＳＤ３に送信する。
【００９４】
ＳＳＤ３のホスト要求処理部２１がこの可変長データ用の読み出し要求をホスト２から受信した時、ホスト要求処理部２１は、可変長ＬＵＴ３２を参照して、読み出し要求によって指定される論理アドレスに対応するＬＵＴエントリから、ＮＡＮＤ型フラッシュメモリ５上の位置（物理記憶位置）を示す物理アドレスとこの可変長データの長さとを取得する（ステップＳ２１）。ステップＳ２１では、ホスト要求処理部２１は、読み出し要求によって指定される論理アドレスを可変長ＬＵＴ管理部２２に送り、これによってＮＡＮＤ型フラッシュメモリ５上の位置とリードすべきデータ長とを可変長ＬＵＴ管理部２２に問い合わせてもよい。
【００９５】
ホスト要求処理部２１は、取得された物理アドレスと取得されたデータ長とに基づいて、ＮＡＮＤ型フラッシュメモリ５からデータを読み出す（ステップＳ２２）。ステップＳ２２では、ホスト要求処理部２１は、取得された物理アドレスと取得されたデータ長とによって指定されるＮＡＮＤ型フラッシュメモリ５上の領域に格納されているデータをＮＡＮＤ型フラッシュメモリ５から読み出す。
【００９６】
そして、ホスト要求処理部２１は、読み出したデータと、データ長と、コマンド完了のレスポンスとを、ホスト２に返す。
【００９７】
図１０は、可変長ルックアップテーブル３２のさらに別の構成例を示す。
【００９８】
図１０の可変長ＬＵＴ３２においては、ＳＳＤ３の論理記憶位置を示す論理アドレスとして、キー・バリュー・ストアのキーが利用される。ホスト２からＳＳＤ３に送信される書き込み要求／読み出し要求に含まれる論理アドレスは、あるキーを示す。
【００９９】
可変長ＬＵＴ３２の各ＬＵＴエントリは、ホスト２によって指定されたキーを管理するためのキーフィールドと、このキーに対応する可変長データ（バリューのみ、またはキー・バリューペア）が格納されたＮＡＮＤ型フラッシュメモリ５上の位置（物理記憶位置）を管理するための位置フィールドと、この可変長データの長さを管理するための長さフィールドとを含んでいる。
【０１００】
キー“ＤＤＤ”に対応する可変長データＤ１１がブロックＢＬＫ１の先頭から始まる領域に書き込まれた場合には、あるＬＵＴエントリには、キー“ＤＤＤ”と、ブロックＢＬＫ１の先頭位置Ｘ１を示す物理アドレスと、可変長データＤ１１の長さ（ここでは、長さは“５”として示されている）とが格納される。
【０１０１】
キー“ＡＡＡ”に対応する可変長データＤ１２がブロックＢＬＫ１の位置Ｘ２から始まる領域に書き込まれた場合には、あるＬＵＴエントリには、キー“ＡＡＡ”と、位置Ｘ２を示す物理アドレスと、可変長データＤ１２の長さ（ここでは、長さは“７”として示されている）とが格納される。
【０１０２】
キー“ＸＸＸ”に対応する可変長データＤ１３がブロックＢＬＫ１の位置Ｘ３から始まる領域に書き込まれた場合には、あるＬＵＴエントリには、キー“ＸＸＸ”と、位置Ｘ３を示す物理アドレスと、可変長データＤ１３の長さ（ここでは、長さは“２”として示されている）とが格納される。
【０１０３】
キー“ＢＢＢ”に対応する可変長データＤ２１がブロックＢＬＫ２の先頭から始まる領域に書き込まれた場合には、あるＬＵＴエントリには、キー“ＢＢＢ”と、ブロックＢＬＫ２の先頭位置Ｙ１を示す物理アドレスと、可変長データＤ２１の長さ（ここでは、長さは“３”として示されている）とが格納される。
【０１０４】
キー“ＣＣＣ”に対応する可変長データＤ２２がブロックＢＬＫ２の位置Ｙ２から始まる領域に書き込まれた場合には、あるＬＵＴエントリには、キー“ＣＣＣ”と、ブロックＢＬＫ２の位置Ｙ２を示す物理アドレスと、可変長データＤ２２の長さ（ここでは、長さは“９”として示されている）とが格納される。
【０１０５】
図１０の可変長ＬＵＴ３２を利用するケースにおいては、読み出し要求または書き込み要求に含まれるキーに基づいて、このキーに対応するＬＵＴエントリが検索される。そして、検索されたＬＵＴエントリが参照または更新される。データ書き込み時においては、書き込み要求に含まれるキーに対応するＬＵＴエントリが存在しないならば、このキーに対応する可変長データが書き込まれたＮＡＮＤ型フラッシュメモリ５の物理記憶位置を示す物理アドレス、およびこの可変長データの長さは、未使用のＬＵＴエントリに格納される。
【０１０６】
図１１は、階層ルックアップテーブル（マルチレベル・ルックアップテーブル）の構成例を示す。
【０１０７】
図１１の階層ルックアップテーブルは、階層化された複数のテーブルを含む。これら複数のテーブルは、マルチステージの論理物理アドレス変換のために使用される。階層ルックアップテーブルに含まれるテーブルの数は、論理物理アドレス変換のためのステージの数に対応する。階層ルックアップテーブルに含まれるテーブルの数は、２つであってもよいし（アドレス変換のステージの数が２）、３つであってもよいし（アドレス変換のステージの数が３）、４つ以上であってもよい（アドレス変換のステージの数が４以上）。
【０１０８】
例えば、階層ルックアップテーブルは、３ステージのアドレス変換によって論理アドレスを物理アドレスに変換する３レベルアドレス変換テーブルであってもよい。この場合、階層ルックアップテーブルは、３ステージのアドレス変換でそれぞれ使用される階層化された３つのテーブル、つまり、レベル１テーブル（Ｌ１テーブル）７３、レベル２テーブル（Ｌ２テーブル）７２、およびレベル３テーブル（Ｌ３テーブル）７１を含んでいてもよい。
【０１０９】
Ｌ３テーブル７１は、論理アドレスそれぞれに対応する複数のＬＵＴエントリを含むアドレス変換テーブルである。このＬ３テーブル７１は、複数のデータ部（データ部＃０、データ部＃１、…データ部＃１２８、…）を含んでいる。換言すれば、Ｌ３テーブル７１は、これら複数のデータ部（データ部＃０、データ部＃１、…データ部＃１２８、…）に分割されている。これらデータ部は、同じ固定のサイズを有する。
【０１１０】
Ｌ３テーブル７１の一つのデータ部（テーブルデータ部）は、例えば、１２８個のＬＵＴエントリ（つまり、１２８個の物理アドレス、および１２８個のデータ長）を含むことができる。つまり、Ｌ３テーブル７１においては、一つのＬＵＴエントリによって１つのＬＢＡがカバーされる。
【０１１１】
Ｌ３テーブル７１のデータ部（データ部＃０、データ部＃１、…データ部＃１２８、…）それぞれが格納されているＮＡＮＤ型フラッシュメモリ５上の位置は、Ｌ２テーブル７２によって個別に管理される。
【０１１２】
Ｌ２テーブル７２も、各々がＬ３テーブル７１の各データ部と同じ固定サイズを有する複数のデータ部（データ部＃０、データ部＃１、…データ部＃１２８、…）を含んでいる。換言すれば、Ｌ２テーブル７２は、これら複数のデータ部（データ部＃０、データ部＃１、…データ部＃１２８、…）に分割されている。
【０１１３】
Ｌ２テーブル７２のこれらデータ部の各々は、複数のＬＵＴエントリ、例えば１２８個のＬＵＴエントリを含む。各ＬＵＴエントリは、Ｌ３テーブル７１内のある一つのデータ部が格納されているＮＡＮＤ型フラッシュメモリ５上の位置を示す。つまり、Ｌ２テーブル７２においては、一つのＬＵＴエントリによって１２８個のＬＢＡがカバーされる。
【０１１４】
Ｌ２テーブル７２のデータ部（データ部＃０、データ部＃１、…データ部＃１２８、…）それぞれが格納されているＮＡＮＤメモリ５上の位置は、Ｌ１テーブル７３によって個別に管理される。
【０１１５】
Ｌ１テーブル７３も、各々がＬ３テーブル７１の各データ部と同じ固定サイズを有する複数のデータ部（データ部＃０、データ部＃１、…）を含んでいる。換言すれば、Ｌ１テーブル７３は、これら複数のデータ部（データ部＃０、データ部＃１、…）に分割されている。
【０１１６】
Ｌ１テーブル７３のこれらデータ部の各々は、複数のＬＵＴエントリ、例えば１２８個のＬＵＴエントリを含んでいる。各ＬＵＴエントリは、Ｌ２テーブル７２内のある一つのデータ部が格納されているＮＡＮＤ型フラッシュメモリ５上の位置を示す。つまり、Ｌ１テーブル７３においては、一つのＬＵＴエントリによって１２８２個のＬＢＡがカバーされる。
【０１１７】
Ｌ１テーブル７３のデータ部（データ部＃０、データ部＃１、…）それぞれが格納されているＮＡＮＤメモリ５上の位置は、ルートテーブル７４と称されるシステム管理情報によって管理される。ルートテーブル７４は、例えば、ＳＳＤ３が電源供給を受けたときにＮＡＮＤ型フラッシュメモリ５からＲＡＭ６にロードされてもよく、以降、ＲＡＭ６上に常時維持されてもよい。
【０１１８】
ルートテーブル７４は、複数のエントリを含んでいてもよい。各エントリは、Ｌ１テーブル７３内のある一つのデータ部が格納されているＮＡＮＤ型フラッシュメモリ５上の位置を示す。
【０１１９】
変換対象の論理アドレスは、４つのサブフィールド、つまりサブフィールド２００Ａ、サブフィールド２００Ｂ、サブフィールド２００Ｃ、サブフィールド２００Ｄに分割される。
【０１２０】
次に、図１１の階層ルックアップテーブルを使用して実行される論理物理アドレス変換処理の概要を説明する。ここでは、説明を簡単にするために、各テーブルがＮＡＮＤ型フラシュメモリ５からリードされる場合を想定する。
【０１２１】
＜最初のステージの論理物理アドレス変換＞
最初に、変換対象の論理アドレス内のサブフィールド２００Ａを使用してルートテーブル７４が参照され、これによってＬ１テーブル７３内の特定のデータ部の物理アドレス（ＮＡＮＤ型フラッシュメモリ５上の位置）が得られる。この物理アドレスに基づいて、Ｌ３テーブル７３の特定のデータ部がＮＡＮＤ型フラッシュメモリ５からリードされる。
【０１２２】
そして、サブフィールド２００Ｂを使用して、Ｌ１テーブル７３内のこの特定のデータ部が参照され、これによってＬ１テーブル７３内のこの特定のデータ部から一つのエントリが選択される。この選択されたエントリには、Ｌ２テーブル７２内の一つのデータ部の物理アドレス（ＮＡＮＤ型フラッシュメモリ５上の位置）が格納されている。この物理アドレスに基づいて、Ｌ２テーブル７２のこのデータ部がＮＡＮＤ型フラッシュメモリ５からリードされる。
【０１２３】
＜次のステージの論理物理アドレス変換＞
次いで、変換対象の論理アドレス内のサブフィールド２００Ｃを使用してＬ２テーブル７２のこのデータ部が参照され、これによってＬ２テーブル７２内のこのデータ部から一つのエントリが選択される。この選択されたエントリには、Ｌ３テーブル７１内の一つのデータ部の物理アドレス（ＮＡＮＤ型フラッシュメモリ５上の位置）が格納されている。この物理アドレスに基づいて、Ｌ３テーブル７１のこのデータ部がＮＡＮＤ型フラッシュメモリ５からリードされる。
【０１２４】
＜最後のステージのアドレス変換＞
次いで、サブフィールド２００Ｄを使用してＬ３テーブル７１内のこのデータ部が参照され、これによってＬ３テーブル７１内のこのデータ部から一つのエントリが選択される。この選択されたエントリには、読み出し要求内の論理アドレスによって指定される可変長データが格納されているＮＡＮＤ型フラッシュメモリ５上の位置を示す物理アドレスと、この可変長データの長さが格納されている。この物理アドレスと長さとに基づいて、この可変長データがＮＡＮＤ型フラッシュメモリ５から読み出される。
【０１２５】
この階層ルックアップテーブルの構成は、この階層ルックアップテーブルを格納するための記憶領域のサイズを減少することができる。なぜなら、実際に物理アドレスと長さとが格納されているデータ部それぞれに対応する記憶領域のみをＮＡＮＤ型フラッシュメモリ５またはＲＡＭ６上に確保すればよいからである。
【０１２６】
図１２は、ＳＳＤ３のハードウェア構成例を示す。
【０１２７】
ＳＳＤ３は、コントローラ４ＡおよびＮＡＮＤ型フラッシュメモリ５を備える。ＳＳＤ３は、ランダムアクセスメモリ、例えば、ＤＲＡＭ６Ａも備えていてもよい。
【０１２８】
ＮＡＮＤ型フラッシュメモリ５は、マトリクス状に配置された複数のメモリセルを含むメモリセルアレイを含む。ＮＡＮＤ型フラッシュメモリ５は、２次元構造のＮＡＮＤ型フラッシュメモリであってもよいし、３次元構造のＮＡＮＤ型フラッシュメモリであってもよい。
【０１２９】
ＮＡＮＤ型フラッシュメモリ５のメモリセルアレイは、複数のブロックＢＬＫ０〜ＢＬＫｍ−１を含む。ブロックＢＬＫ０〜ＢＬＫｍ−１の各々は多数のページ（ここではページＰ０〜Ｐｎ−１）によって編成される。ブロックＢＬＫ０〜ＢＬＫｍ−１は、消去単位として機能する。ブロックは、「物理ブロック」、または「消去ブロック」と称されることもある。ページＰ０〜Ｐｎ−１の各々は、同一ワード線に接続された複数のメモリセルを含む。ページＰ０〜Ｐｎ−１は、データ書き込み動作およびデータ読み込み動作の単位である。
【０１３０】
コントローラ４Ａは、ＮＡＮＤ型フラッシュメモリ５を制御するＬＳＩである。コントローラ４Ａは、Ｔｏｇｇｌｅ、Ｏｐｅｎ  ＮＡＮＤ  Ｆｌａｓｈ  Ｉｎｔｅｒｆａｃｅ（ＯＮＦＩ）のようなＮＡＮＤインタフェース１３を介して、ＮＡＮＤ型フラッシュメモリ５に電気的に接続されている。ＮＡＮＤインタフェース１３は、ＮＡＮＤ型フラッシュメモリ５を制御するＮＡＮＤ制御回路として機能する。
【０１３１】
ＮＡＮＤ型フラッシュメモリ５は、図１３に示すように、複数のＮＡＮＤ型フラッシュメモリチップ（ダイ）を含む。個々のＮＡＮＤ型フラッシュメモリチップは独立して動作可能である。このため、ＮＡＮＤ型フラッシュメモリチップは、並列動作可能な単位として機能する。図１３においては、ＮＡＮＤインタフェース１３に１６個のチャンネルＣｈ．１〜Ｃｈ．１６が接続されており、１６個のチャンネルＣｈ．１〜Ｃｈ．１６の各々に２つのＮＡＮＤ型フラッシュメモリチップが接続されている場合が例示されている。この場合、チャンネルＣｈ．１〜Ｃｈ．１６に接続された１６個のＮＡＮＤ型フラッシュメモリチップ＃１〜＃１６がバンク＃０として編成されてもよく、またチャンネルＣｈ．１〜Ｃｈ．１６に接続された残りの１６個のＮＡＮＤ型フラッシュメモリチップ＃１７〜＃３２がバンク＃１として編成されてもよい。バンクは、複数のメモリモジュールをバンクインタリーブによって並列動作させるための単位として機能する。図１３の構成例においては、１６チャンネルと、２つのバンクを使用したバンクインタリーブとによって、最大３２個のＮＡＮＤ型フラッシュメモリチップを並列動作させることができる。
【０１３２】
コントローラ４Ａは、複数のブロックを一つの大きな単位（「論理ブロック」または「スーパーブロック」として参照される）にグループ化する。例えば、一つの論理ブロックは、これに限定されないが、ＮＡＮＤ型フラッシュメモリチップ＃１〜＃３２から一つずつ選択される計３２個のブロックを含んでいてもよい。図１３においては、ハッチングによって示されるブロックそれぞれは、ある一つの論理ブロックに含まれるブロック（物理ブロック）を表している。各ＮＡＮＤ型フラッシュメモリチップは、チャンネル番号およびバンク番号によって識別可能である。また、各ブロック（物理ブロック）は、物理ブロック番号によって識別可能である。
【０１３３】
なお、ＮＡＮＤ型フラッシュメモリチップ＃１〜＃３２の各々はマルチプレーン構成を有していてもよい。例えば、ＮＡＮＤ型フラッシュメモリチップ＃１〜＃３２の各々が、２つのプレーンを含むマルチプレーン構成を有する場合には、一つの論理ブロックは、ＮＡＮＤ型フラッシュメモリチップ＃１〜＃３２に対応する６４個のプレーンから一つずつ選択される計６４個のブロックを含んでいてもよい。
【０１３４】
ここで、図１４に示すように、ある一つの論理ブロックが、３２個のブロック（ＮＡＮＤ型フラッシュメモリチップ＃１内のブロックＢｌｋ２、ＮＡＮＤ型フラッシュメモリチップ＃２内のブロックＢｌｋ３、ＮＡＮＤ型フラッシュメモリチップ＃３内のブロックＢｌｋ７、ＮＡＮＤ型フラッシュメモリチップ＃４内のブロックＢｌｋ４、ＮＡＮＤ型フラッシュメモリチップ＃５内のブロックＢｌｋ６、…ＮＡＮＤ型フラッシュメモリチップ＃３２内のブロックＢｌｋ３）を含む場合を想定する。
【０１３５】
この論理ブロックへのデータ書き込みにおいては、コントローラ４Ａは、ＮＡＮＤ型フラッシュメモリチップ＃１内のブロックＢｌｋ２のページ０、ＮＡＮＤ型フラッシュメモリチップ＃２内のブロックＢｌｋ３のページ０、ＮＡＮＤ型フラッシュメモリチップ＃３内のブロックＢｌｋ７のページ０、ＮＡＮＤ型フラッシュメモリチップ＃４内のブロックＢｌｋ４のページ０、ＮＡＮＤ型フラッシュメモリチップ＃５内のブロックＢｌｋ６のページ０、…ＮＡＮＤ型フラッシュメモリチップ＃３２内のブロックＢｌｋ３のページ０という順序でデータを書き込んでもよい。これにより、最大３２ページへのデータ書き込みを並列に実行することができる。また、この論理ブロックからのデータ読み込みにおいても、最大で３２ページからのデータ読み込みを並列に実行することができる。
【０１３６】
各ＬＵＴエントリによって管理される物理記憶位置は、論理ブロック番号、ブロック番号（物理ブロック）番号、ブロック内の位置によって表されてもよいし、論理ブロック番号、ブロック番号（物理ブロック）番号、ページ番号、ページ内の位置によって表されてもよいし、論理ブロック番号、論理ブロック内の位置によって表されてもよい。
【０１３７】
次に、図１２のコントローラ４Ａの構成について説明する。
【０１３８】
コントローラ４Ａは、ＮＡＮＤ型フラッシュメモリ５のデータ管理およびブロック管理を実行するように構成されたフラッシュトランスレーション層（ＦＴＬ）として機能してもよい。このＦＴＬによって実行されるデータ管理には、（１）論理アドレスそれぞれとＮＡＮＤ型フラッシュメモリ５の物理アドレスそれぞれとの間の対応関係を示すマッピング情報の管理、（２）ページ単位のリード／ライトとブロック単位の消去動作とを隠蔽するための処理、等が含まれる。論理アドレスは、ＳＳＤ３をアドレス指定するためにホスト２によって使用されるアドレスである。この論理アドレスとしては、ＬＢＡ（logical block address(addressing)）が使用され得る。
【０１３９】
論理アドレスそれぞれと物理アドレスそれぞれとの間のマッピングの管理は、可変長ＬＵＴ３２を用いて実行される。コントローラ４Ａは、可変長ＬＵＴ３２を使用して、論理アドレスそれぞれと物理アドレスそれぞれとの間のマッピングを管理する。可変長ＬＵＴ３２は、ＳＳＤ３の電源オン時にＮＡＮＤ型フラッシュメモリ５からＤＲＡＭ６Ａにロードされてもよい。
【０１４０】
ページへのデータ書き込みは、１消去サイクル当たり１回のみ可能である。このため、コントローラ４Ａは、ある論理アドレスに対応する更新データを、この論理アドレスに対応する以前のデータが格納されている物理記憶位置ではなく、別の物理記憶位置に書き込む。そして、コントローラ４は、可変長ＬＵＴ３２を更新してこの論理アドレスをこの別の物理記憶位置に関連付けると共に、以前のデータを無効化する。
【０１４１】
ブロック管理には、バッドブロックの管理と、ウェアレベリングと、ガベージコレクション等が含まれる。ウェアレベリングは、ブロック（物理ブロック）それぞれの消耗を均一化するための動作である。ガベージコレクションは、データを書き込むことが可能なフリーブロックの個数を増やすため、有効データと無効データとが混在する幾つかの対象ブロック内の有効データを別のブロック（例えばフリーブロック）にコピーする。ここで、有効データとは、可変長ＬＵＴ３２から参照されているデータ(すなわち論理アドレスから最新のデータとして紐付けられているデータ)であって、後にホスト２からリードされる可能性があるデータを意味する。無効データとは、もはやホスト２からリードされる可能性が無いデータを意味する。例えば、ある論理アドレスに関連付けられているデータは有効データであり、どの論理アドレスにも関連付けられていないデータは無効データである。
【０１４２】
そして、コントローラ４は、ルックアップテーブル（ＬＵＴ）３２を更新して、コピーされた有効データの論理アドレスそれぞれをコピー先物理アドレスにマッピングする。有効データが別のブロックにコピーされることによって無効データのみになったブロックはフリーブロックとして解放される。これによって、このブロックはその消去後に再利用することが可能となる。
【０１４３】
コントローラ４Ａは、ホストインタフェース１１、ＣＰＵ１２、ＮＡＮＤインタフェース１３、ＤＲＡＭインタフェース１４等を含んでもよい。これらＣＰＵ１２、ＮＡＮＤインタフェース１３、ＤＲＡＭインタフェース１４は、バス１０を介して相互接続されていてもよい。
【０１４４】
ホストインタフェース１１は、ホスト２から様々なコマンドを受信する。これらコマンドには、可変長データ用のライトコマンド、可変長データ用のリードコマンドも含まれる。
【０１４５】
ＣＰＵ１２は、ホストインタフェース１１、ＮＡＮＤインタフェース１３、およびＤＲＡＭインタフェース１４を制御するように構成されたプロセッサである。ＣＰＵ１２は、ＳＳＤ３の電源オンに応答して、ＮＡＮＤ型フラッシュメモリ５に格納されている制御プログラム（ファームウェア）をＤＲＡＭ６上にロードし、このファームウェアを実行することによって様々な処理を行う。このＣＰＵ１２は、例えば、上述のＦＴＬの処理に加え、ホスト２からの様々なコマンドを処理するためのコマンド処理等を実行することができる。ＣＰＵ１２の動作は、ＣＰＵ１２によって実行される上述のファームウェアによって制御される。なお、ＦＴＬ処理およびコマンド処理の一部または全部は、コントローラ４内の専用ハードウェアによって実行してもよい。
【０１４６】
ＣＰＵ１２は、ホスト要求処理部２１Ａ、可変長ＬＵＴ管理部２２Ａ、ネームスペース管理部２３Ａとして機能することができる。
【０１４７】
ホスト要求処理部２１Ａは、図１のホスト要求処理部２１によって実行される処理と同じ処理を実行する。可変長ＬＵＴ管理部２２Ａは、図１の可変長ＬＵＴ管理部２２によって実行される処理と同じ処理を実行する。
【０１４８】
ネームスペース管理部２３Ａは、上述のマルチネームスペースコントロール機能を実行する。ネームスペース管理部２３Ａは、固定長データを扱うためのタイプ＃１−ネームスペース、および可変長データを扱うためのタイプ＃２−ネームスペースを作成することができる。タイプ＃１−ネームスペース用の論理物理アドレス変換は、固定長ＬＵＴ３３を使用して実行される。タイプ＃２−ネームスペースの論理物理アドレス変換は、可変長ＬＵＴ３２を使用して実行される。
【０１４９】
ＤＲＡＭインタフェース１４は、ＤＲＡＭ６をアクセス制御するように構成されたＤＲＡＭコントローラである。ＤＲＡＭ６の記憶領域は、ライトバッファ（ＷＢ）３１、ＬＵＴ３２、３３を格納するために利用される。
【０１５０】
次に、ホスト２の構成について説明する。
【０１５１】
ホスト２は、様々なプログラムを実行する情報処理装置である。情報処理装置によって実行されるプログラムには、アプリケーションソフトウェアレイヤ４１、オペレーティングシステム（ＯＳ）４２、デバイスドライバ４３等が含まれる。
【０１５２】
一般に知られているように、オペレーティングシステム（ＯＳ）４２は、ホスト２全体を管理し、ホスト２内のハードウェアを制御し、アプリケーションがハードウェアおよびＳＳＤ３を使用することを可能にするための制御を実行するように構成されたソフトウェアである。
【０１５３】
様々なアプリケーションソフトウェアスレッドがアプリケーションソフトウェアレイヤ４１上で走る。アプリケーションソフトウェアスレッドの例としては、クライアントソフトウェア、データベースソフトウェア、仮想マシン等がある。
【０１５４】
アプリケーションソフトウェアレイヤ４１がリードコマンドまたはライトコマンドのようなリクエストをＳＳＤ３に送出することが必要な時、アプリケーションソフトウェアレイヤ４１は、ＯＳ４２にそのリクエストを送出する。ＯＳ４２はそのリクエストをデバイスドライバ４３に送出する。デバイスドライバ４３は、そのリクエストを、コマンド（リードコマンド、ライトコマンド等）にトランスレートする。デバイスドライバ４３は、コマンドを、ＳＳＤ３に送出する。ＳＳＤ３からのレスポンスが受信された際、デバイスドライバ４３は、そのレスポンスをＯＳ４２に送出する。ＯＳ４２は、そのレスポンスをアプリケーションソフトウェアレイヤ４１に送出する。
【０１５５】
デバイスドライバ４３の可変長データ読み書き部１０１Ａは、図１の可変長データ読み書き部１０１と同じ処理を実行する。
【０１５６】
図１５は、コントローラ４Ａによって管理される複数の領域を示す。
【０１５７】
コントローラ４Ａは、ＮＡＮＤ型フラッシュメモリ５内の複数の領域、つまり領域＃１、領域＃２、…領域＃３１、領域＃３２、領域＃３３を管理する。各領域は、ネームスペースによって実現することができる。各ネームスペースは、ＮＡＮＤ型フラッシュメモリ５内の一種の領域（記憶領域）であり、論理アドレス空間（ＬＢＡ空間）が割り当てられる。個々のネームスペースは、これらネームスペースの識別子によって識別される。各領域がネームスペースによって実現された場合、各領域には、ＬＢＡ範囲（ＬＢＡ０〜ＬＢＡｎ−１）が割り当てられる。ＬＢＡ範囲のサイズ（つまりＬＢＡの数）は、領域（ネームスペース）毎に可変である。各ＬＢＡ範囲は、ＬＢＡ０から始まる。
【０１５８】
例えば、領域＃１（ネームスペースＮＳ＃１）、領域＃２（ネームスペースＮＳ＃２）、…の各々は、可変長データを格納するために使用されてもよい。また、領域＃３１（ネームスペースＮＳ＃３１）、領域＃３２（ネームスペースＮＳ＃３２）、領域＃３３（ネームスペースＮＳ＃３３）の各々は、固定長データを格納するために使用されてもよい。
【０１５９】
図１６は、複数の領域とこれら領域に対応する論理アドレス空間（ＬＢＡ空間）とこれら領域に対応するルックアップテーブルとの関係を示す。
【０１６０】
ネームスペースＮＳ＃１に対応する領域＃１には、０〜ｎ−１の論理アドレス空間（ＬＢＡ空間）Ａ１が割り当てられている。ネームスペースＮＳ＃２に対応する領域＃２には、０〜ｎ−１の論理アドレス空間（ＬＢＡ空間）Ａ２が割り当てられている。ネームスペースＮＳ＃３１に対応する領域＃３１には、０〜ｎ−１の論理アドレス空間（ＬＢＡ空間）Ａ３１が割り当てられている。ネームスペースＮＳ＃３２に対応する領域＃３２には、０〜ｎ−１の論理アドレス空間（ＬＢＡ空間）Ａ３２が割り当てられている。ネームスペースＮＳ＃３３に対応する領域＃３３には、０〜ｎ−１の論理アドレス空間（ＬＢＡ空間）Ａ３３が割り当てられている。
【０１６１】
本実施形態では、ルックアップテーブルＬＵＴは、領域毎に、つまりネームスペース毎に分割されている。つまり、領域＃１（ＮＳ＃１）のための論理物理アドレス変換は可変長ＬＵＴ＃２を使用して実行され、領域＃２（ＮＳ＃２）のための論理物理アドレス変換は可変長ＬＵＴ＃２を使用して実行される。また、領域＃３１（ＮＳ＃３１）のための論理物理アドレス変換は固定長ＬＵＴ＃３１を使用して実行され、領域＃３２（ＮＳ＃３２）のための論理物理アドレス変換は固定長ＬＵＴ＃３２を使用して実行され、領域＃３３（ＮＳ＃３３）のための論理物理アドレス変換は固定長ＬＵＴ＃３３を使用して実行される。
【０１６２】
領域＃１（ＮＳ＃１）および領域＃２（ＮＳ＃２）の各々においては、任意の論理アドレスに任意の長さのデータを書き込むことができる。
【０１６３】
以上説明したように、本実施形態によれば、ＳＳＤ３は、ＮＡＮＤ型フラッシュメモリ５上のどの物理記憶位置からどれだけの長さのデータを格納したかを可変長ＬＵＴ３２に格納し、これによって任意の論理アドレスに対応する論理記憶位置に任意の長さのデータを格納することを可能にする。換言すれば、可変長ＬＵＴ３２は、ある論理アドレスに対応するＳＳＤ３内の論理記憶位置に、ホスト２によって指定される任意のデータ長に対応するサイズを有する物理記憶領域を割り当てることを可能にする。
【０１６４】
よって、（１）ホストのＣＰＵの処理時間の増加、（２）メタデータの読み書きによるメモリアクセス時間の増加、（３）メタデータ／ダミーデータの書き込みによるメモリリソースの消費量の増加、（４）メモリリソースの消費量の増加によるライトアンプリフィケーションの増加、（５）ライトアンプリフィケーションの増加によるＳＳＤの寿命の減少、といった非効率を解消することが可能となる。
【０１６５】
なお、本実施形態では、不揮発性メモリとしてＮＡＮＤ型フラッシュメモリを例示した。しかし、本実施形態の機能は、例えば、ＭＲＡＭ（Ｍａｇｎｅｔｏｒｅｓｉｓｔｉｖｅ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＰＲＡＭ（Ｐｈａｓｅ  ｃｈａｎｇｅ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＲｅＲＡＭ（Ｒｅｓｉｓｔｉｖｅ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、又は、ＦｅＲＡＭ（Ｆｅｒｒｏｅｌｅｃｔｒｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）のような他の様々な不揮発性メモリにも適用できる。
【０１６６】
また、ＳＳＤ３は、ストレージアレイ内に設けられる複数のＳＳＤの一つとして利用されてもよい。ストレージアレイは、サーバ計算機のような情報処理装置にケーブルまたはネットワークを介して接続されてもよい、ストレージアレイは、このストレージアレイ内の複数のＳＳＤを制御するコントローラを含む。ＳＳＤ３がストレージアレイに適用された場合には、このストレージアレイのコントローラが、ＳＳＤ３のホスト２として機能してもよい。
【０１６７】
また、各ＬＵＴエントリに固定長データ／可変長データを示すフラグを格納するためのフィールドを追加してもよい。これにより、一つのＬＵＴで、固定長データの読み書きと、固定長データの読み書きとを制御することがきる。
【０１６８】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１６９】
２…ホスト、３…ＳＳＤ、４、４Ａ…コントローラ、５…ＮＡＮＤ型フラッシュメモリ、２１、２１Ａ…ホスト要求処理部、２２、２２Ａ…可変長ＬＵＴ管理部、３２…可変長ＬＵＴ。
【図１】
2019020788.tif 000003
【図２】
2019020788.tif 000004
【図３】
2019020788.tif 000005
【図４】
2019020788.tif 000006
【図５】
2019020788.tif 000007
【図６】
2019020788.tif 000008
【図７】
2019020788.tif 000009
【図８】
2019020788.tif 000010
【図９】
2019020788.tif 000011
【図１０】
2019020788.tif 000012
【図１１】
2019020788.tif 000013
【図１２】
2019020788.tif 000014
【図１３】
2019020788.tif 000015
【図１４】
2019020788.tif 000016
【図１５】
2019020788.tif 000017
【図１６】
2019020788.tif 000018