説明

記憶装置のためのストレージアドレス再マッピングのための方法およびシステム

ストレージアドレス再マッピングのための方法およびシステムが開示される。この方法は、クラスタのブロック内の論理アドレスを割当てることと、論理アドレスをストレージアドレス空間内に再マッピングすることとを含み、論理アドレス空間に分散させられているデータの短いランはストレージアドレス空間内のブロックの中に連続的な仕方でマッピングされる。新しいブロックの利用可能な数が所望のしきい値より低下した時には、データを受け取るために利用し得る新しいブロックを作るために、有効なデータおよび陳腐化したデータの両方を有するブロックから有効なデータがフラッシングされる。システムは、ホストファイルシステム、ホストファイルシステムとは別にホスト上に存在するかあるいは埋め込みソリッドステートディスクなどのフラッシュメモリ装置上に存在するプロセッサ実行可能な命令、または、データを論理アドレス空間からストレージアドレス空間内の完全なブロックに連続的な仕方でマッピングするように構成されているフラッシュメモリ装置のバックエンドメモリマネージャを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、一般的には、オペレーティングシステムと記憶装置の間のデータ通信に関する。より具体的には、本願は、再プログラム可能な不揮発性半導体フラッシュメモリなどのメモリシステムと、このメモリが接続されているかあるいは接続可能であるホスト装置との操作に関する。
【背景技術】
【０００２】
在来のフラッシュデータメモリシステムにデータを書き込む時、ホストは、通例、メモリシステムの連続的な仮想アドレス空間の中で一意の論理アドレスをデータのセクタ、クラスタまたは他の単位に割当てる。ホストは、メモリシステムの論理アドレス空間内のアドレスにデータを書き込み、また、それからデータを読み出す。メモリシステムは、そのとき、一般的に、論理アドレス空間と、論理アドレス空間における範囲に対応する固定された論理グループをなしてデータが格納されるメモリの物理的ブロックまたはメタブロックとの間でデータをマッピングする。一般に、各々の固定された論理グループは、メモリシステムの別々の物理的ブロックに格納される。メモリシステムは、論理アドレス空間が物理メモリにどのようにマッピングされているかを追跡するけれども、ホストはこれを知らない。ホストは、そのデータファイルの、論理アドレス空間内のアドレスを追跡するけれども、メモリシステムは、このマッピングについての知識なしで動作する。
【０００３】
このように動作するメモリシステムの１つの欠点は断片化である。例えば、ＮＴＦＳファイルシステムに従って動作するパーソナルコンピュータ（ＰＣ）においてソリッドステートディスク（ＳＳＤ）ドライブに書き込まれているデータは、しばしば、このドライブの論理アドレス空間内の広く分散した位置における短い連続するアドレスランのパターンにより特徴付けられる。ホストにより使用されるファイルシステムが連続する複数のファイルのための新しいデータのために順次アドレスを割当てたとしても、削除されたファイルの気まぐれなパターンは、利用可能な空きメモリ空間の断片化を、それがブロック化単位で新しいファイルデータに割当てられ得ないように、引き起こす。
【０００４】
フラッシュメモリ管理システムは、連続する論理アドレスの１つのブロックを物理アドレスの１つのメタブロックにマッピングすることによって動作しがちである。ホストからのアドレスの短い１つのランが独立して更新される時、そのランを含むアドレスの論理ブロック全体は、単一のメタブロックへのその長期マッピングを維持しなければならない。これは、論理対物理メモリ管理システム内のガーベッジコレクション操作を必要とし、そのとき、論理ブロック内のホストにより更新されない全てのデータは、それを更新されるデータと合併させるために再配置される。これはかなりのオーバーヘッドであって、書き込み速度とメモリの寿命とを厳しく制限することがある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許出願第１０／９１５，０３９号
【特許文献２】米国特許第５，５７０，３１５号
【特許文献３】米国特許第５，７７４，３９７号
【特許文献４】米国特許第６，０４６，９３５号
【特許文献５】米国特許第６，３７３，７４６号
【特許文献６】米国特許第６，４５６，５２８号
【特許文献７】米国特許第６，５２２，５８０号
【特許文献８】米国特許第６，７７１，５３６号
【特許文献９】米国特許第６，７８１，８７７号
【特許文献１０】米国公開特許出願第２００３／０１４７２７８号
【特許文献１１】米国公開特許出願第２００３／０１０９０９３号
【発明の概要】
【０００６】
既知のディスクドライブで使用される磁気メモリと比べてフラッシュメモリが現在持っている書き込みサイクルの限られた数を仮定すれば、短い論理アドレスランおよび断片化の問題を埋め合わせるために、フラッシュメモリを利用するシステムの性能を改善することが望ましい。これを処理するために、記憶装置におけるストレージアドレス再マッピングのための方法およびシステムが開示される。
【０００７】
第１の態様に従って、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法が記述される。この方法は、ホスト論理ブロックアドレス（ＬＢＡ）アドレスと関連付けられたデータを大容量記憶システムにおいてホストシステムから受け取ることを含む。このホストＬＢＡアドレスを受け取るために連続するストレージＬＢＡアドレスの１つのブロックが割当てられ、その連続するストレージＬＢＡアドレスのブロックは陳腐化したデータだけを含む。この方法は、受け取られたデータのためのホストＬＢＡアドレスの各々をその連続するストレージＬＢＡアドレスのブロックに再マッピングすることも含み、各ストレージＬＢＡアドレスは、ホストＬＢＡアドレスに関わらず、受け取られたデータが受け取られた順に、受け取られたデータに連続的な仕方で順次に割当てられる。
【０００８】
第２の態様に従って、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法が記述される。この方法は、ホスト論理ブロックアドレス（ＬＢＡ）アドレスと関連付けられたデータをホストシステム上のファイルシステムから受け取ることを含む。受け取られたホストＬＢＡアドレスは、連続するストレージＬＢＡアドレスの１つのブロックに受け取られた順に再マッピングされ、そしてその連続するストレージＬＢＡアドレスのブロックが完全にプログラムされた後に初めて、割当て時に未記入の容量だけをアドレス指定する連続するストレージＬＢＡアドレスの１つの付加的なブロックが割当てられ、残りの受け取られたホストＬＢＡアドレスはその付加的なブロックに連続的に再マッピングされる。未記入容量だけをアドレス指定する連続的なストレージＬＢＡアドレスの新しいブロックも作成される。
【０００９】
本発明の他の１つの態様において、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法が開示され、この方法は、ホスト論理ブロックアドレス（ＬＢＡ）アドレスと関連付けられたデータを大容量記憶システムにおいてこのホストシステムから受け取ることと、受け取られたホストＬＢＡアドレスを受け取られた順に連続するストレージＬＢＡアドレスの１つのブロックに連続的に再マッピングすることとを含む。この方法は、割当て時に未記入の容量だけをアドレス指定する連続するストレージＬＢＡアドレスの１つの付加的なブロックを割当てることと、連続するストレージＬＢＡアドレスのブロックが完全にプログラムされた時に初めて残りの受け取られたホストＬＢＡアドレスを付加的なブロックに連続的に再マッピングすることとをも含む。さらに、この方法は、ホストＬＢＡアドレスと関連付けられたデータが連続するストレージＬＢＡアドレスに再マッピングされる時に、ホストＬＢＡアドレスをストレージＬＢＡアドレスにマッピングするストレージアドレステーブルを生成することを含む。
【００１０】
他の１つの態様に従って、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法が開示され、この方法は、ホスト論理ブロックアドレス（ＬＢＡ）アドレスと関連付けられたデータを大容量記憶システム上のアプリケーションにおいてホストシステムから受け取ることと、この受け取られたホストＬＢＡアドレスを、連続するストレージＬＢＡアドレスの１つのブロックに、受け取られた順に連続的に再マッピングすることとを含む。この方法は、割当て時に未記入の容量だけをアドレス指定する連続するストレージＬＢＡアドレスの１つの付加的なブロックを割当てることと、連続するストレージＬＢＡアドレスのブロックが完全にプログラムされた時にだけ付加的な受け取られたホストＬＢＡアドレスを付加的なブロックに連続的に再マッピングすることとをさらに含む。有効なデータおよび陳腐化したデータを現在アドレス指定している連続するストレージＬＢＡアドレスの以前に完全にプログラムされたブロックを、以前に受け取られたホストＬＢＡアドレスと関連付けられた新しいデータを受け取る前に識別することと、連続するストレージＬＢＡアドレスの識別された以前に完全にプログラムされたブロックから未記入容量だけをアドレス指定する連続するストレージＬＢＡアドレスの新しいブロックを作成することとも含まれる。
【００１１】
本発明の１つの態様において、大容量記憶メモリシステムが開示され、このシステムは、一緒に消去可能なメモリセルの複数のブロックに配列された再プログラム可能な不揮発性メモリセルと、ホスト論理ブロックアドレス（ＬＢＡ)アドレスでアドレス指定されたホストシステムからのデータを受け取るようになされているインターフェイスと、このインターフェイスと通信するコントローラとを備える。コントローラは、ホストシステムからデータを受け取るために連続するストレージＬＢＡアドレスの１つのブロックを割当てるように構成されると共に、その受け取られたデータのためのホストＬＢＡアドレスの各々を連続するストレージＬＢＡアドレスのブロックに再マッピングするように構成され、また、受け取られたデータと関連付けられたホストＬＢＡアドレスに関わらず、受け取られたデータが受け取られた順に、各々の連続するストレージＬＢＡアドレスを受け取られたデータに順次に割当てるように構成される。
【００１２】
本発明の他の１つの態様に従って、大容量記憶メモリシステムは、一緒に消去可能なメモリセルの複数のブロックに配列された再プログラム可能な不揮発性メモリセルと、ホストシステムからホスト論理ブロックアドレス（ＬＢＡ)フォーマットでアドレス指定されたデータを受け取るようになされているインターフェイスと、このインターフェイスと通信するコントローラとを備える。コントローラは、ホストシステムから大容量記憶システムにおいてホストＬＢＡアドレスと関連付けられたデータを受け取ることと、受け取られたホストＬＢＡアドレスを連続するストレージＬＢＡアドレスの１つのブロックに受け取られた順に連続的に再マッピングすることと、連続するストレージＬＢＡアドレスの、割当て時に未記入の容量だけを含む１つの付加的なブロックを割当てることと、その連続するストレージＬＢＡアドレスのブロックが完全にプログラムされている場合にだけ残りの受け取られたホストＬＢＡアドレスを付加的なブロックに連続的に再マッピングすることとを実行するためのプロセッサ実行可能な命令を含む。プロセッサ実行可能な命令は、有効なデータを含まない連続するストレージＬＢＡアドレスの新しいブロックを作成するための命令も含む。
【００１３】
本発明の他の１つの態様において開示されるように、ホストＬＢＡアドレスと関連付けられたデータをストレージＬＢＡアドレスに再マッピングするための不揮発性大容量記憶システムは、一緒に消去可能なメモリセルの複数のブロックに配列された再プログラム可能な不揮発性メモリセルと、ホストシステムからホストＬＢＡフォーマットでアドレス指定されたデータを受け取るようになされているインターフェイスと、このインターフェイスと通信するコントローラとを備える。コントローラは、受け取られたホストＬＢＡアドレスを、受け取られた順に、連続するストレージＬＢＡアドレスの１つのブロックに連続的に再マッピングし、割当て時に未記入の容量だけをアドレス指定する連続するストレージＬＢＡアドレスの１つの付加的なブロックを割当て、連続するストレージＬＢＡアドレスのブロックが完全にプログラムされている時にだけ付加的な受け取られたホストＬＢＡアドレスを付加的なブロックに連続的に再マッピングするように構成される。コントローラは、ホストＬＢＡアドレスと関連付けられたデータが連続するストレージＬＢＡアドレスに再マッピングされる時にホストＬＢＡアドレスをストレージＬＢＡアドレスにマッピングするストレージアドレステーブルを生成し、ストレージＬＢＡアドレスの複数のブロックの各々のステータスを識別するブロック情報テーブルを生成するようにさらに構成される。
【００１４】
他の１つの態様において、不揮発性大容量記憶システムは、ホストＬＢＡアドレスと関連付けられたデータをホストシステムから大容量記憶システムにおいて受け取るための手段と、ホストＬＢＡアドレスを受け取るために、割当て時に未記入の容量だけと関連付けられた連続するストレージＬＢＡアドレスの１つのブロックを割当てるための手段と、受け取られたデータのためのホストＬＢＡアドレスの各々を連続するストレージＬＢＡアドレスのブロックに再マッピングするための手段とを備え、各ストレージＬＢＡアドレスは、ホストＬＢＡアドレスに関わらず、受け取られたデータが受け取られた順に、受け取られたデータに連続的な仕方で順次に割当てられる。
【００１５】
本発明のさらに他の１つの態様において、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法は、ホストＬＢＡアドレスと関連付けられたデータをホストシステム上のホスト再マッピングモジュールで受け取ることを含む。ホスト再マッピングモジュールは、ホストＬＢＡアドレスを受け取るために、割当て時に未記入の容量だけと関連付けられた連続するストレージＬＢＡアドレスの１つのブロックを割当て、また、受け取られたデータのためのホストＬＢＡアドレスの各々を、連続するストレージＬＢＡアドレスのブロックに、各ストレージＬＢＡアドレスがホストＬＢＡアドレスに関わらず受け取られたデータが受け取られた順に受け取られたデータに連続的な仕方で順次に割当てられるように、再マッピングする。連続するストレージＬＢＡアドレスのブロックに再マッピングされた受け取られたデータと、割当てられたストレージＬＢＡアドレスとはホストシステムから大容量記憶システムに送られる。
【００１６】
他の１つの態様において、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法は、ホスト論理ブロックアドレス（ＬＢＡ)アドレスと関連付けられたデータをホストシステムに存在するホスト再マッピングモジュールで受け取ることと、受け取られたホストＬＢＡアドレスを、受け取られた順に、連続するストレージＬＢＡアドレスの１つのブロックに連続的に再マッピングすることとを含む。割当て時に未記入の容量だけをアドレス指定する連続するストレージＬＢＡアドレスの１つの付加的なブロックが割当てられる。残りの受け取られたホストＬＢＡアドレスは、連続するストレージＬＢＡアドレスのブロックが完全にプログラムされた時にだけ、付加的なブロックに連続的に再マッピングされる。この方法は、陳腐化したデータだけをアドレス指定する連続するストレージＬＢＡアドレスの新しいブロックを作成することと、連続するストレージＬＢＡアドレスのブロックに再マッピングされた受け取られたデータと割当てられたストレージＬＢＡアドレスとをホストシステムから大容量記憶システムに送ることとをさらに含む。
【００１７】
本発明の１つの態様に従って、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法は、ホストＬＢＡアドレスと関連付けられたデータをホストシステム上のホスト再マッピングモジュールにおいて受け取ることと、受け取られたホストＬＢＡアドレスを受け取られた順にホストシステムにおいて連続するストレージＬＢＡアドレスの１つのブロックに連続的に再マッピングすることと、割当て時に未記入の容量だけをアドレス指定する連続するストレージＬＢＡアドレスの１つの付加的なブロックを割当てることと、連続するストレージＬＢＡアドレスのブロックが完全にプログラムされた時にだけ、付加的な受け取られたホストＬＢＡアドレスを付加的なブロックに連続的に再マッピングすることとを含む。この方法は、ホストＬＢＡアドレスと関連付けられているデータが連続するストレージＬＢＡアドレスに再マッピングされる時にホストＬＢＡアドレスをストレージＬＢＡアドレスにマッピングするストレージアドレステーブルをホストシステムにおいて生成することをさらに含む。
【００１８】
本発明の他の１つの態様において、データを再プログラム可能な不揮発性大容量記憶システムに転送するためのホストシステムが開示される。このホストシステムは、大容量記憶装置との通信を可能にするように構成されたインターフェイスと、ホスト再マッピングモジュールからの命令に従ってインターフェイスを介して大容量記憶システムにデータを格納するように構成されたホストプロセッサとを含む。ホスト再マッピングモジュールは、ホストプロセッサに、ホスト論理ブロックアドレス（ＬＢＡ）アドレスと関連付けられたデータをホストシステム上のホスト再マッピングモジュールにおいて受け取らせ、ホストＬＢＡアドレスを受け取るために、割当て時に未記入の容量だけをアドレス指定する連続するストレージＬＢＡアドレスの１つのブロックを割当てさせ、各ストレージＬＢＡアドレスが、ホストＬＢＡアドレスに関わらず受け取られたデータが受け取られた順に、受け取られたデータに連続的な仕方で順次に割当てられるように、受け取られたデータのためのホストＬＢＡアドレスの各々を連続するストレージＬＢＡアドレスのブロックに再マッピングさせ、連続するストレージＬＢＡアドレスのブロックに再マッピングされた受け取られたデータと、割当てられたストレージＬＢＡアドレスとをホストシステムから大容量記憶システムに送らせるためのプロセッサ実行可能な命令を含む。
【００１９】
本発明の他の１つの態様に従って、データを再プログラム可能な不揮発性大容量記憶システムに転送するためのホストシステムが開示される。このホストシステムは、大容量記憶装置との通信を可能にするように構成されたインターフェイスと、ホスト再マッピングモジュールからの命令に従ってデータをインターフェイスを介して大容量記憶システムに格納するように構成されたホストプロセッサとを備える。ホスト再マッピングモジュールは、ホストプロセッサに、ホスト論理ブロックアドレス（ＬＢＡ）アドレスと関連付けられたデータをホスト再マッピングモジュールにおいて受け取らせ、受け取られたホストＬＢＡアドレスを、受け取られた順に、ホストシステムにおいて連続するストレージＬＢＡアドレスの１つのブロックに連続的に再マッピングさせ、割当て時に未記入の容量だけと関連付けられた連続するストレージＬＢＡアドレスの１つの付加的なブロックを割当てさせ、連続するストレージＬＢＡアドレスのブロックが完全にプログラムされた時にだけ付加的な受け取られたホストＬＢＡアドレスを付加的なブロックに連続的に再マッピングさせるためのプロセッサ実行可能な命令を含む。ホスト再マッピングモジュールのプロセッサ実行可能な命令は、ホストプロセッサに、ホストＬＢＡアドレスと関連付けられたデータが連続するストレージＬＢＡアドレスに再マッピングされる時にホストＬＢＡアドレスをストレージＬＢＡアドレスにマッピングするストレージアドレステーブルをホストシステムにおいて生成させるようにも構成される。
【００２０】
本発明の他の１つの態様において、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法は、大容量記憶システムに格納されるべきデータをホストファイルシステムにおいて受け取ることと、受け取られたデータに関連付けるべき連続するホストＬＢＡアドレスの、少なくとも１つの利用可能なホストＬＢＡアドレスを有する、第１のブロックを割当てることと、第１のブロック内の各々の利用可能なホストＬＢＡアドレスを受け取られたデータに関連付けることとを含み、各々の利用可能なホストＬＢＡアドレスは、受け取られたデータに、受け取られたデータが受け取られた順に、順次に割当てられる。この方法は、連続するホストＬＢＡアドレスの第２のブロックを割当てることをさらに含み、その連続するホストＬＢＡアドレスの第２のブロックは少なくとも１つの利用可能なホストＬＢＡアドレスを有し、第２のブロックは、第１のブロック内の少なくとも１つの利用可能なホストＬＢＡアドレスの各々の関連付けの後に初めて割当てられる。
【００２１】
他の１つの態様において、データを再プログラム可能な不揮発性大容量記憶システムに転送するためのホストシステムが開示される。このホストシステムは、大容量記憶装置との通信を可能にするように構成されたインターフェイスと、データをホストメモリからの命令に従ってインターフェイスを介して大容量記憶システムに格納するように構成されたホストプロセッサとを備える。ホストメモリは、プロセッサに、ホストファイルシステムにおいて受け取られたデータと関連付けるべき連続するホストＬＢＡアドレスの第１のブロックを割当てさせ、第１のブロック内の各々の利用可能なホストＬＢＡアドレスを、各々の利用可能なホストＬＢＡアドレスが、受け取られたデータに、受け取られたデータが受け取られた順に、順次に割当てられるように、受け取られたデータに関連付けさせ、受け取られたデータと関連付けるための連続するホストＬＢＡアドレスの第２のブロックを、第１のブロック内の少なくとも１つの利用可能なホストＬＢＡアドレスの各々を関連付けた後に初めて、割当てさせる、ホストファイルシステムを実行するためのプロセッサ実行可能な命令を有する。
【００２２】
他の１つの態様において、データをホストシステムから再プログラム可能な不揮発性大容量記憶システムに転送するためのコンピュータ実行可能な命令を有するコンピュータ可読媒体が開示される。コンピュータ実行可能な命令は、大容量記憶システムに格納されるべきデータをホストファイルシステムにおいて受け取ることと、受け取られたデータと関連付けるべき連続するホストＬＢＡアドレスの第１のブロックを割当てることと、第１のブロック内の各々の利用可能なホストＬＢＡアドレスを、各々の利用可能なホストＬＢＡアドレスが、受け取られたデータに、受け取られたデータが受け取られた順に、順次に割当てられるように、受け取られたデータに関連付けることとをプロセッサに実行させるように構成される。コンピュータ実行可能な命令は、受け取られたデータと関連付けるための連続するホストＬＢＡアドレスの第２のブロックを、第１のブロック内の利用可能なホストＬＢＡアドレスの各々の関連付けの後に初めて、割当てることをプロセッサに実行させるようにも構成される。
【００２３】
本発明のさらに他の１つの態様において、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法は、ホストＬＢＡアドレスと関連付けられたデータを大容量記憶システムにおいてホストシステムから受け取ることを含む。この方法は、受け取られたデータを、ホストＬＢＡアドレスの順に関わらず、受け取られた順に、連続する物理アドレスを有する１つの書き込みブロックの連続する物理アドレスに格納することと、書き込みブロックが完全にプログラムされた時に受け取られたデータを格納する次の書き込みブロックとして、未記入の容量だけを含む連続する物理アドレスの１つのブロックを含む１つの白色ブロックを割当てることと、受け取られたデータのためのホストＬＢＡアドレスを各書き込みブロック内の物理アドレスにマッピングする１つのストレージアドレステーブルを更新することとを含み、ストレージアドレステーブルは物理アドレスの少なくとも１つのブロックにおいて維持される。この方法は１つの新しい白色ブロックを作成することをさらに含み、１つの新しい白色ブロックを作成することは複数のピンク色ブロックから１つのピンク色ブロックを選択することを含み、複数のピンク色ブロックの各々は、有効なデータおよび陳腐化したデータの両方を有する完全にプログラムされた物理アドレスの１つの連続的なブロックであり、選択されたピンク色ブロックはしきい値量未満の有効なデータを有する。選択されたピンク色ブロックからの全ての有効なデータは、その選択されたピンク色ブロックからの全ての有効なデータが再配置されるとその選択されたピンク色ブロックが１つの新しい白色ブロックになるように、１つの再配置ブロックに再配置される。
【００２４】
本発明の１つの態様に従って、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法が開示される。この方法は、ホスト論理ブロックアドレス（ＬＢＡ）アドレスと関連付けられたデータを大容量記憶システムにおいてホストシステムから受け取ることと、受け取られたデータを、ホストＬＢＡアドレスの順に関わらず、受け取られた順に、連続する物理アドレスを有する１つの書き込みブロックの連続する物理アドレスに格納することとを含む。受け取られたデータのためのホストＬＢＡアドレスの１つのランは１つのストレージアドレステーブル（ＳＡＴ）の単一のページの上に物理アドレスの少なくとも２つのランにマッピングされ、ＳＡＴは、大容量記憶システム内の連続する物理アドレスの少なくとも１つのブロックから構成される。
【００２５】
他の１つの態様において、再プログラム可能な不揮発性大容量記憶システムにおいて未記入容量だけを有する連続する物理アドレスのブロックを生成する方法が開示され、大容量記憶システムは、連続する物理アドレスの複数のブロックを有する。この方法は、複数のブロックのうちの、有効なデータおよび陳腐化したデータの両方を有する連続する物理アドレスの１つの完全にプログラムされたブロックを含む各ピンク色ブロックに含まれる有効なデータの量を判定することと、有効なデータの判定された量に基づいてピンク色ブロックのうちの１つを選択することとを含む。この方法は、ピンク色ブロックのうちの選択された１つから有効なデータを１つの再配置ブロック内の連続する物理アドレスにコピーすることをさらに含み、再配置ブロックは、ピンク色ブロックのうちの選択された１つから有効なデータを連続的に再配置するべきところの連続する物理アドレスの１つのブロックを含み、有効なデータは、ピンク色ブロックのうちの選択された１つから有効なデータと関連付けられたホストＬＢＡアドレスに関わらず出現の順にコピーされる。
【００２６】
大容量記憶メモリシステムが本発明の他の１つの態様において開示される。この大容量記憶システムは、一緒に消去可能なメモリセルの複数のブロックに配列された再プログラム可能な不揮発性メモリセルと、ホストＬＢＡアドレスでアドレス指定されたホストシステムからのデータを受け取るようになされているインターフェイスと、このインターフェイスと通信するコントローラとを備える。コントローラは、ホストシステムからデータを受け取るために連続する物理アドレスの第１のブロックを割当て、受け取られたデータのためのホストＬＢＡアドレスの各々をその連続する物理アドレスのブロックにマッピングするように構成され、受け取られたデータは、受け取られたデータと関連付けられたホストＬＢＡアドレスに関わらず、受け取られたデータが受け取られた順に、連続する物理アドレスに順次に書き込まれる。コントローラは、付加的な受け取られるデータを連続的な仕方で受け取るために連続する物理アドレスの第２のブロックを割当てるようにさらに構成され、その連続する物理アドレスの第２のブロックは、割当て時に未記入の容量だけを有し、コントローラは、連続する物理アドレスの第１のブロックを完全に割当てた時に初めてデータを第２のブロックに割当てる。また、コントローラは、ホストＬＢＡアドレス位置と物理アドレス位置とを相関させる相関データを生成し、相関データを大容量記憶メモリシステムにおいて１つのストレージアドレステーブルに格納するようにさらに構成され、相関データは、ホストＬＢＡアドレスの各ランを、ホストＬＢＡアドレスのランと関連付けられたデータに対応する物理アドレスの１つ以上のランにマッピングする。
【００２７】
本発明の他の１つの態様に従って、１つの連続する論理アドレス範囲の中の１つの論理アドレスによってデータが識別される記憶装置の中でデータを移動させる方法が開示される。この方法は、連続する論理アドレス範囲を等しいサイズの論理アドレスの連続するブロックに分割することと、装置に格納された有効なデータに割当てられている少なくとも１つの論理アドレスを含む論理アドレスの１つのブロックを識別することとを含む。この方法は、有効なデータを論理アドレスのブロック内に含まれない少なくとも１つの論理アドレスに再マッピングすることと、有効なデータに割当てられた少なくとも１つの論理アドレスと関連付けられた有効なデータを読み出すことと、識別されたブロックが有効なデータに割当てられたアドレスを含まないように、有効なデータを少なくとも１つの論理アドレスに書き込むこととを含む。
【００２８】
本発明の他の特徴および利点は、以下の図面、詳細な説明および特許請求の範囲を検討すれば明らかとなる。
【図面の簡単な説明】
【００２９】
【図１】不揮発性メモリを有するメモリシステムと接続されたホストを示す。
【図２】図１の不揮発性メモリとして用いられる例示のフラッシュメモリシステムの例示のブロック図である。
【図３】図２のシステムにおいて使用され得るメモリセルアレイの代表的な回路図である。
【図４】図２のシステムの物理メモリ組織の例を示す。
【図５】図４の物理メモリの一部分の拡大図を示す。
【図６】ＬＢＡアドレス空間における割当て済みクラスタおよび空きクラスタの代表的パターンを示す。
【図７】１つの開示される実施例に従うブロックによるクラスタの割当てのパターンを示す。
【図８】装置のメモリマネージャがストレージアドレス指定再マッピング機能を組み入れている、ホストとメモリドライブとの間のストレージアドレス再マッピングの実施例を示す。
【図９】図８に示されているストレージアドレス再マッピングの代わりの実施例を示す。
【図１０】機能がホストに置かれているストレージアドレス再マッピングの実施例を示す。
【図１１】図１０のストレージアドレス再マッピングの代わりの実施例を示す。
【図１２】クラスタのブロックの割当ての状態図である。
【図１３】フラッシュメモリはバイナリパーティションおよびＭＬＣパーティションを含む場合の図１２の状態図の代わりの実施例である。
【図１４】図９および１０の実施例において利用され得るＬＢＡアドレス空間および関連するＤＬＢＡアドレス空間の例である。
【図１５】ホストから受け取られたデータのためのＬＢＡ対ＤＬＢＡマッピングの例を示す。
【図１６】ＤＬＢＡアドレス空間におけるフラッシング操作と、物理アドレス空間内の対応する更新ブロックとを示す。
【図１７】図１６のフラッシング操作に続く第２のフラッシング操作を示す。
【図１８】ホストからのデータを包含するブロックのためのブロックフラッシングプロセスの流れ図である。
【図１９】ホスト論理アドレスが第２の論理アドレス空間に再マッピングされる構成におけるストレージアドレステーブル（ＳＡＴ）階層を示す。
【図２０】論理対論理マッピングを追跡するのに使われるストレージアドレステーブル（ＳＡＴ）書き込みブロックを示す。
【図２１】図２０のＳＡＴテーブルのＳＡＴページで使用されるＬＢＡエントリである。
【図２２】図２０のＳＡＴテーブルのＳＡＴページで使用されるＤＬＢＡエントリである。
【図２３】図２０のＳＡＴテーブルのＳＡＴページで使用されるＳＡＴ索引エントリである。
【図２４】図９および１０のストレージアドレス再マッピング機能において使用されるストレージアドレステーブル変換手続きを示す。
【図２５】ＬＢＡアドレス空間およびＤＬＢＡアドレス空間における４つの時間インスタンスでのデータ書き込み操作の例の図である。
【図２６】ＳＡＴブロック遷移の状態図を示す。
【図２７】ＳＡＴブロックフラッシング順序を決定するためのプロセスの流れ図である。
【図２８】ブロック情報テーブル(ＢＩＴ)書き込みブロックを示す。
【図２９】ホストから受け取られたデータのためのＬＢＡ対物理アドレスのマッピングの例を示す。
【図３０】図２９に示されているデータ分布に基づく物理アドレス空間におけるフラッシング操作を示す。
【図３１】図３０のフラッシング操作に続く第２のフラッシング操作を示す。
【図３２】ホスト論理アドレスのランがデータランの物理アドレスにマッピングされる構成におけるストレージアドレステーブル(ＳＡＴ)階層を示す。
【図３３】論理対物理マッピングを追跡するのに使用されるストレージアドレステーブル（ＳＡＴ）書き込みブロックを示す。
【図３４】図３３のＳＡＴテーブルのＳＡＴページに使用されるＬＢＡエントリである。
【図３５】図３３のＳＡＴテーブルのＳＡＴページに使用されるデータエントリである。
【図３６】図３３のＳＡＴテーブルのＳＡＴページに使用されるＳＡＴ索引エントリである。
【図３７】論理アドレスの完全なブロックがデータランにマッピングされる、図３２〜３６のＳＡＴの代わりの実施形態を示す。
【図３８】図１１の構成を利用するシステムにおけるストレージアドレス再マッピングの実施例を示す。
【発明を実施するための形態】
【００３０】
本発明の種々の態様を実施するために用いるのに適するフラッシュメモリシステムが図１〜６に示されている。図１のホストシステム１は、フラッシュメモリ２にデータを格納し、それからデータを取り出す。フラッシュメモリは、例えばパーソナルコンピュータに据え付けられたソリッドステートディスク（ＳＳＤ）ドライブの形で、ホスト内に埋め込まれ得る。代わりに、メモリ２は、図１に示されているように機械電気コネクタの接合部品３および４を通してホストに取り外し可能に接続されるカードの形であり得る。内部のあるいは埋め込みのＳＳＤドライブとして使用されるように構成されたフラッシュメモリは図１の略図に類似するように見えるかもしれないが、主な違いはホスト内でのメモリシステム２の位置である。ＳＳＤドライブは、回転磁気ディスクドライブに替わるドロップイン取替え品である個別的モジュールの形であり得る。
【００３１】
市販されているＳＳＤドライブの１例は、サンディスク コーポレーションにより製造されている３２ギガバイトＳＳＤである。市販されている取り外し可能なフラッシュメモリカードの例は、コンパクトフラッシュ（ＣＦ）、マルチメディアカード（ＭＭＣ）、セキュアデジタル（ＳＤ）、ミニＳＤ（ｍｉｎｉＳＤ）、メモリスティック、スマートメディア、およびトランスフラッシュカードを含む。これらのカードの各々は、その標準化された仕様に従う独特の機械的および／または電気的インターフェイスを有するけれども、各々に含まれているフラッシュメモリシステムは類似している。これらのカードは全て、本願の譲受人であるサンディスク コーポレーションから入手可能である。サンディス
コーポレーションクは、Ｃｒｕｚｅｒという商標のもとで１系列のフラッシュドライブも提供しり、それらは、ホストのＵＳＢレセプタクルに差し込むことによってホストと接続するためのユニバーサル・シリアル・バス（ＵＳＢ）プラグを有する小型パッケージ内のハンドヘルドメモリシステムである。これらのメモリカードおよびフラッシュドライブの各々は、ホストとインターフェイスしてそれらの中のフラッシュメモリの動作を制御するコントローラを含む。
【００３２】
ＳＳＤ、メモリカードおよびフラッシュドライブを使用することのできるホストシステムは、たくさんあって多様である。それらは、デスクトップあるいはラップトップおよび他の携帯可能なコンピュータなどのパーソナルコンピュータ（ＰＣ）、セルラー電話機、個人用携帯情報端末（ＰＤＡ）、デジタルスチルカメラ、デジタルムービーカメラ、および携帯可能なオーディオプレーヤを含む。携帯可能なメモリカードアプリケーションのために、ホストは１つ以上のタイプのメモリカードまたはフラッシュドライブのための内蔵レセプタクルを含むことができ、あるいはホストはメモリカードを差し込むアダプタを必要とし得る。メモリシステムは、普通はそれ自身のメモリコントローラおよびドライバを包含するけれども、その代わりにメモリが接続されているホストによって実行されるソフトウェアにより制御されるメモリだけのシステムもいくつかある。コントローラを包含するあるメモリシステム、特にホストに埋め込まれているものでは、メモリ、コントローラおよびドライバはしばしば単一の集積回路チップ上に形成される。
【００３３】
図１のホストシステム１は、メモリ２に関する限り、回路およびソフトウェアの組み合わせから構成される２つの主要な部分を有すると見なされ得る。それらは、アプリケーション部分５と、メモリ２とインターフェイスするドライバ部分６とである。ＰＣにおいて、例えば、アプリケーション部分５は、ワードプロセッサ、グラフィックス、制御または他のポピュラーなアプリケーションソフトウェアを実行するプロセッサ９と、ホスト１上のデータを管理するためのファイルシステム１０とを含むことができる。カメラ、セルラー電話機、あるいはその他の、主として単一の機能セットの実行のために専用されるホストシステムでは、アプリケーション部分５は、写真を撮り、また記憶するようにカメラを操作し、電話を掛け、また受け取るようにセルラー電話機を操作するなどするソフトウェアを含む。
【００３４】
図１のメモリシステム２は、フラッシュメモリ７と、データを前後に通過させるためにカードが接続されているホストとインターフェイスし、かつメモリ７を制御する回路８とを含む。コントローラ８は、通例、データプログラムおよび読み出しの間に、ホスト１により使用されるデータの論理アドレスとメモリ７の物理アドレスとの間で変換を行う。
【００３５】
図２を参照すると、図１の不揮発性メモリ２として使用され得る代表的なフラッシュメモリシステムの回路が記載されている。システムコントローラは、普通、システムバス１３を介して１つ以上の集積回路メモリチップと並列に接続された単一の集積回路チップ１１上に実装され、単一のそのようなメモリチップ１５が図２に示されている。図に示されている特定のバス１３は、データを伝える導体の独立のセット１７と、メモリアドレスのためのセット１９と、制御信号およびステータス信号のためのセット２１とを含む。あるいは、導体の単一のセットが、これら３つの機能の間で時分割され得る。さらに、「Ring Bus Structure and It's Use in Flash Memory Systems 」という２００４年８月９日に出願された米国特許出願第１０／９１５，０３９号（特許文献１）に記載されているリングバスなどの、システムバスの他の構成が採用され得る。
【００３６】
代表的なコントローラチップ１１は、インターフェイス回路２５を通してシステムバス１３とインターフェイスするそれ自身の内部バス２３を有する。バスに通常結び付けられている主な機能は、プロセッサ２７（マイクロプロセッサあるいはマイクロコントローラなど）、システムを初期化（「ブート」）するためのコードを包含する読み出し専用メモリ（ＲＯＭ）２９、主としてメモリおよびホストの間で転送されるデータをバッファリングするために使用される読み出し専用メモリ（ＲＡＭ）３１、およびメモリとホストとの間でコントローラを通過するデータのために誤り訂正符号（ＥＣＣ）を計算しチェックする回路３３である。コントローラバス２３は回路３５を通してホストシステムとインターフェイスし、それは、メモリカードに内蔵される図２のシステムの場合には、コネクタ４の一部であるカードの外部接点３７を通して行われる。クロック３９は、コントローラ１１の他のコンポーネントの各々に接続されて、それらにより利用される。
【００３７】
メモリチップ１５も、システムバス１３と接続されている他のものも、多数のサブアレイあるいはプレーンをなすように組織されたメモリセルアレイを含むことができ、２つのそのようなプレーン４１および４３が簡潔さを図るために図に示されているけれども、その代わりにもっと多くの、例えば４個または８個のそのようなプレーンも使用され得る。あるいは、チップ１５のメモリセルアレイは、プレーンをなすように分割されなくてもよい。しかし、そのように分割される場合には、各プレーンは、互いに独立して動作し得るそれ自身の列制御回路４５を有する。回路４５および４７は、システムバス１３のアドレス部分１９からそれぞれのメモリセルアレイのアドレスを受け取り、それらを、それぞれのビット線４９および５１のうちの特定の１つ以上をアドレス指定するために復号する。ワード線５３は、アドレスバス１９で受け取られたアドレスに応じて行制御回路５５を通してアドレス指定される。Ｐウェル電圧制御回路６１および６３と同じく、ソース電圧制御回路５７および５９もそれぞれのプレーンと接続されている。メモリチップ１５がメモリセルの単一のアレイを有し、２つ以上のそのようなチップがシステムに存在するならば、各チップのアレイは、前述した多数のプレーンチップ内のプレーンまたはサブアレイと同様に操作され得る。
【００３８】
データは、システムバス１３のデータ部分１７と接続されているそれぞれのデータ入出力回路６５および６７を通してプレーン４１および４３内へ、またそれらの外へ転送される。回路６５および６７は、それぞれの列制御回路４５および４７を通してプレーンに接続された線６９および７１を通して、それぞれのプレーンのメモリセルにデータをプログラムすると共にメモリセルからデータを読み出すための手段を提供する。
【００３９】
コントローラ１１は、データをプログラムし、データを読み出し、消去し、また種々のハウスキーピング事項を処理するためにメモリチップ１５の動作を制御するけれども、各メモリチップも、そのような機能を実行するためにコントローラ１１からのコマンドを実行する多少の制御回路を含む。インターフェイス回路７３は、システムバス１３の制御およびステータス部分２１に接続されている。コントローラからのコマンドは、これらのコマンドを実行するために他の回路の具体的な制御を提供する状態マシン７５に提供される。制御線７７〜８１は、図２に示されているように、状態マシン７５をこれらの他の回路と接続する。状態マシン７５からのステータス情報は、バス部分２１を介してコントローラ１１に伝送されるべく線８３を介してインターフェイス７３に伝えられる。
【００４０】
メモリセルアレイ４１および４３のＮＡＮＤアーキテクチャが現在好ましいけれども、代わりにＮＯＲなどの他のアーキテクチャも使用され得る。ＮＡＮＤフラッシュメモリと、メモリシステムの一部としてのそれらの動作との例が、米国特許第５，５７０，３１５号（特許文献２）、第５，７７４，３９７号（特許文献３）、第６，０４６，９３５号（特許文献４）、第６，３７３，７４６号（特許文献５）、第６，４５６，５２８号（特許文献６）、第６，５２２，５８０号（特許文献７）、第６，７７１，５３６号（特許文献８）および第６，７８１，８７７号（特許文献９）、ならびに米国公開特許出願第２００３／０１４７２７８号（特許文献１０）を参照することにより得られ得る。ＮＡＮＤアレイの例が、図３の回路図により示され、それは図２のメモリシステムのメモリセルアレイ４１の一部分である。多数のグローバルビット線が設けられるが、説明を簡略化するために図２には４つのそのような線９１〜９４だけが示されている。直列接続された数個のメモリセルストリング９７〜１０４が、これらのビット線のうちの１つと基準電位との間に接続されている。代表としてメモリセルストリング９９を用いると、複数の電荷蓄積メモリセル１０７〜１１０が、ストリングの両端で選択トランジスタ１１１および１１２と直列に接続されている。１つのストリングの選択トランジスタが導通させられると、そのストリングはそのビット線と基準電位との間に接続される。その後、一度にそのストリングの中の１つのメモリセルがプログラムされるかあるいは読み出される。
【００４１】
図３のワード線１１５〜１１８は、それぞれ、メモリセルの数個のストリングの各々の中の１つのメモリセルの電荷蓄積素子を横断して伸び、ゲート１１９および１２０は、ストリングの各端部の選択トランジスタの状態を制御する。共通のワード線および制御ゲート線１１５〜１２０を共有するメモリセルストリングは、一緒に消去されるメモリセルの１つのブロック１２３を形成させられる。セルのこのブロックは、物理的に一度に消去可能な最小数のセルを包含する。１行のメモリセル、すなわちワード線１１５〜１１８のうちの１つに沿うメモリセルは一度にプログラムされる。通例、ＮＡＮＤアレイの行は所定の順序で、この場合には接地または他の共通電位に接続されているストリングの端部に最も近いワード線１１８に沿う行から、プログラムされる。ワード線１１７に沿うメモリセルの行が次にプログラムされ、そしてブロック１２３の全体にわたって、そのようにプログラムされてゆく。ワード線１１５に沿う行は最後にプログラムされる。
【００４２】
第２のブロック１２５は同様であり、そのメモリセルのストリングは第１のブロック１２３のストリングと同じグローバルビット線に接続されているが、ワード線および制御ゲート線の異なるセットを有する。ワード線および制御ゲート線は、行制御回路５５によってそれらの適切な動作電圧へ到達させられる。例えば図２のプレーン１および２など、２つ以上のプレーンまたはサブアレイがシステムに存在するならば、１つのメモリアーキテクチャは、それらの間に伸びる共通ワード線を使用する。代わりに、共通のワード線を共有する３つ以上のプレーンまたはサブアレイが存在し得る。他のメモリアーキテクチャでは、それぞれのプレーンまたはサブアレイのワード線は別々に駆動される。
【００４３】
前に援用されているＮＡＮＤ特許および公開された特許出願のうちのいくつかに記載されているように、メモリシステムは、各々の電荷蓄積素子または領域に２つよりも多くの検出可能なレベルの電荷を蓄積し、これにより１ビットより多くのデータを各々に記憶させるように操作され得る。メモリセルの電荷蓄積素子は、最も一般的には導電性フローティングゲートであるけれども、代わりに、米国公開特許出願第２００３／０１０９０９３号（特許文献１１）に記載されているように、非導電性の誘電体電荷トラッピング材料であり得る。
【００４４】
図４は、以下のさらなる記述において１例として用いられるフラッシュメモリセルアレイ７（図１）の組織を概念的に示す。メモリセルの４つのプレーンまたはサブアレイ１３１〜１３４は、単一の統合メモリセルチップ上に、２チップ上に（各チップ上にプレーンのうちの２つ）、あるいは４つの別々のチップ上に存在し得る。明細な配列は、以下の議論にとっては重要ではない。もちろん、１つのシステム内に他の数のプレーン、例えば１，２，８，１６またはそれ以上が存在し得る。このプレーンは、それぞれのプレーン１３１〜１３４に置かれているブロック１３７，１３８，１３９および１４０などの、長方形により図４に示されているメモリセルのブロックにそれぞれ分割される。各プレーンに数十あるいは数百のブロックが存在し得る。
【００４５】
前述したように、メモリセルのブロックは消去の単位、すなわち物理的に一緒に消去可能な最小数のメモリセルである。しかし、並列性を高めるために、ブロックは、より大きなメタブロック単位で操作される。１つのメタブロックを形成するために各プレーンから１つのブロックが論理的に連結される。１つのメタブロック１４１を形成する４つのブロック１３７〜１４０が示されている。１つのメタブロックの中の全てのセルが通例一緒に消去される。ブロック１４５〜１４８から構成される第２のメタブロック１４３において示されているように、１つのメタブロックを形成するために使用されるブロックは、それらのそれぞれのプレーンの中の同じ相対的位置に限定される必要はない。全てのプレーンを横断するようにメタブロックを延在させるのが普通は好ましいけれども、高いシステム性能を得るために、メモリシステムは、別々のプレーンに存在する１個、２個または３個のブロックのうちのいずれかまたは全てからメタブロックを動的に形成する能力で操作され得る。これは、メタブロックのサイズを、１つのプログラミング操作で格納されるように利用され得るデータの量により厳密に適合させることを可能にする。
【００４６】
次に、個々のブロックは、操作上の目的のために、図５に示されているようにメモリセルのページに分割される。例えば、ブロック１３７〜１４０の各々のメモリセルは、各々８ページＰ０〜Ｐ７に分割される。その代わりとして、各ブロック内のメモリセルの１６ページ、３２ページまたはそれ以上が存在し得る。ページは、１ブロック内でのデータプログラミングおよび読み出しの単位であって、一度にプログラムされるかあるいは読み出される最少量のデータを包含する。図３のＮＡＮＤアーキテクチャでは、１つのページは、１ブロック内の１つのワード線に沿うメモリセルから形成される。しかし、メモリシステムの操作の並列性を高めるために、２つ以上のブロックの中のそのようなページが論理的に連結されてメタページとなることができる。１つのメタページ１５１が図５に示され、４個のブロック１３７〜１４０の各々から１つの物理的ページで形成されている。例えばメタページ１５１は４つのブロックの各々のページＰ２を含むけれども、メタページのページはブロックの各々の中で必ずしも同じ相対的位置を持っていなくてもよい。メタページは、プログラミングの最大単位である。
【００４７】
ホスト１とメモリシステム２との間の、図６に示されている普通の論理インターフェイスは、メモリシステム２に格納され得る全データにアドレスを提供するのに充分な大きさの１つの連続的な論理アドレス空間１６０を利用する。前述したホスト１およびメモリシステム２を参照すると、フラッシュメモリ７に格納されるように定められているデータは、通例、論理ブロックアドレス（ＬＢＡ）フォーマットで受け取られる。ホストアドレス空間は、通例、データのクラスタのインクリメントに分割される。各クラスタは所与のホストシステムにおいてデータの数個のセクタを含むように設計され、およそ４〜６４セクタが代表的である。１つの標準的なセクタは５１２バイトのデータを包含する。図６を参照すると、ＮＴＦＳファイルシステムのための論理アドレス空間１６０における割当て済みクラスタ１６２および空きクラスタ１６４の代表的なパターンが示されている。
【００４８】
図６に示されている論理アドレス空間１６０の断片化を処理するための組織的構造が図７に示されている。本願明細書において記載されているストレージアドレス再マッピングのためのシステムおよび方法は、以下の議論において一般的に「ブロック」と称されるクラスタのブロック１６６を考慮してＬＢＡアドレスを割当てる。書き込み操作は、常にデータを個々のブロック１６６に書き込み、そのブロック１６６を、次の利用可能なブロックに進む前に、データで完全に満たすことによって処理される。以下の記述において、有効なデータで完全に満たされているブロック１６６は赤色ブロック１６８と称され、有効なデータがなくて、従って未記入容量だけを含むブロックは白色ブロック１７０と称される。メモリシステムが「使用後に消去する」タイプの手続きを採用しているならば、白色ブロック１７０内の未記入容量は消去済み状態であり得る。その代わりに、メモリシステムが「使用前に消去する」タイプの手続きを採用しているならば、白色ブロック１７０内の未記入容量は割当て時に消去されなければならない陳腐化したデータからなることができる。完全にプログラムされていて、有効なデータのクラスタ１６２および無効な（陳腐化したとも称される）データのクラスタ１６４の両方を有するブロックはピンク色ブロック１７２と称される。
【００４９】
論理アドレス空間１６０を論理アドレスのブロックを考慮して分割し管理するために、ホストとメモリシステムとはフラッシュメモリにおける物理的ブロックのブロックサイズに関する情報を交換しなければならないことがある。論理ブロックのサイズは好ましくは物理的ブロックと同じサイズであって、この情報は、メモリシステムがホストと接続される時に伝達され得る。この通信は、パワーアップ時にあるいはメモリシステムのホストへの接続時にハンドシェイキング動作として行われるように設定され得る。一実施形態では、ホストは、ブロックサイズおよびアライメント情報を要求する「ドライブ識別(Identify Drive)」クエリをメモリシステムに送ることができ、ブロックサイズは、そのメモリシステムのための個々の物理的ブロックのサイズであり、アライメント情報は、既に各物理的ブロックの一部を占めつつあるかもしれないシステムデータために物理的ブロックの先頭からどれほどのオフセット（あるならば）を考慮に入れなければならないかである。
【００５０】
ドライブ識別コマンドは、レガシーＬＢＡインターフェイスコマンドセットの予備コードとして実現され得る。コマンドは、標準的な通信インターフェイスにおいて予備のコマンドコードあるいは割当てられていないコマンドコードを介してホストからメモリシステムに送られ得る。適切なインターフェイスの例は、ソリッドステートディスクのためのＡＴＡインターフェイス、あるいは、例えばＣＦまたはＳＤメモリカードに使われているものなどのＡＴＡ関連インターフェイスを含む。メモリシステムがブロック情報およびオフセット情報の両方を提供できなければ、ホストはデフォルトのブロックサイズおよびオフセットを想定することができる。メモリシステムがドライブ識別コマンドに対してオフセット情報なしで、ブロックサイズ情報だけで応答するならば、ホストはデフォルトのオフセットを想定することができる。デフォルトのブロックサイズは、いくつかの標準的なブロックサイズのうちのどれであってもよくて、好ましくは、おそらく実際の物理的ブロックサイズであるサイズより大きく設定される。各々の物理的ブロックがホストからのデータを物理的ブロック内の第１のアドレスから開始して受け取れるということが仮定されるように、デフォルトオフセットはゼロオフセットにセットされ得る。ホストが所定の、ＳＳＤなどの内部ドライブに結合されているならば、記憶装置の能力は既に知られていて前もってプログラムされているかもしれないので、ブロックサイズおよびオフセットを決定するこのステップを行う必要はないかもしれない。しかし、たとえ内部ドライブであっても交換され得るので、ホストは、常に記憶装置の能力を確認するように構成され得る。取り外し可能なメモリシステムについて、ホストは、ドライブ識別コマンドまたは類似のメカニズムを通してブロックサイズおよびオフセットを問い合わせることができる。
【００５１】
本願明細書に記載されているクラスの空きブロック１６６を割当て、空きブロックに書き込むためのシステムおよび方法は、いろいろな組み合わせでホストシステムおよびメモリシステムに分配された機能またはハードウェアを含み得る。図８〜１１は、ホスト内のファイルとソリッドステート記憶装置とを含むシステムの階層の中の４つの異なるレベルにおいて、クラスタのブロック割当てを成し遂げるストレージアドレスマッピングまたは再マッピングアルゴリズムが実行され得る仕方の例を示す。
【００５２】
図８および９のアレンジメントは、ストレージアドレスマッピングまたは再マッピング機能が記憶装置１７６，１７８にすっかり含まれる実施形態のものである。これらの始めの２つのアレンジメントでは、記憶装置１７６，１７８はレガシーホスト１７４と協同することができ、ホスト１７４の改変は不要である。逆に、図１０および１１に示されているアレンジメントは、ストレージアドレスマッピングまたは再マッピング機能がホスト１８０，１８２にすっかり含まれる実施形態のものである。これらの後者の２つの実施形態では、ホスト１８０，１８２は、改変を必要としないレガシー記憶装置１８４と協同することができる。
【００５３】
図８の例では、ストレージアドレスマッピングアルゴリズムを記憶装置１７６のメモリマネージメント１７７に統合することができ、ホスト１７４からのＬＢＡアドレスは、物理メモリの第１のブロックが、次のブロックへ進む前にデータで完全に満たされることとなるように、フラッシュメモリ内の物理的ブロックに直接マッピングされる。その代わりに、図９では、ストレージアドレス再マッピングメカニズムが記憶装置１７８において、しかし装置１７８のためのメモリマネージャ１７９とは別に、実現され得る。図９の実施例では、ホスト１７４からの各論理アドレスは、データを完全なブロック１６６を考慮して書き込むという手法を利用して、本願明細書でストレージ論理ブロックアドレス（ストレージＬＢＡ）と称されると共に本願明細書で装置論理ブロックアドレス（ＤＬＢＡ）とも称される第２の論理アドレスに再マッピングされ、その後にメモリマネージャ１７９が、ＤＬＢＡアレンジメントのもとで組織されたデータを物理メモリのブロックに移す。ＤＬＢＡアドレス空間は、１つの物理的メタブロックのものに等しい均一なサイズのＤＬＢＡブロックを単位として組織される。図１０の実施例は、ストレージアドレス再マッピングの機能を記憶装置１８４からホスト１８０上の１つのアプリケーションに移す。この実施例では、ＬＢＡアドレスをＤＬＢＡアドレスにマッピングする機能は図９のものに類似し、主な違いは、変換が記憶装置１８４ではなくてホスト１８０上で行われることである。ホスト１８０は、ホストで生成されたＤＬＢＡアドレス情報と、ＤＬＢＡアドレスに関連付けられたデータとの両方を記憶装置１８４に送る。最後に、ホストオペレーティングシステム１８２自体に埋め込まれたデータ割当てアレンジメントが図１１に示されている。この最後の実施例では、例えばウィンドウズＸＰまたはビスタのオペレーティングシステムの中のＮＴＦＳファイルシステムなどの、ホスト１８２のファイルシステム１８５は、中間の論理アドレスから論理アドレスへの変換を必要とせずにクラスタの完全な論理ブロックを考慮してストレージアドレスを生成するように構成され得る。従って、図１１の実施例は、ＬＢＡアドレスが、最初は、付加的なブロックを満たし始める前に完全なブロックを満たすために生成されるように、改変されたアルゴリズムをホストファイルシステムに含む。
【００５４】
図８〜１１のアレンジメントのいずれにおいても、データを書き込むための唯一の場所として１つの白色ブロック１７０が割当てられ、それは、その書き込みポインタの現在の位置において、データで、それがホストにより提供される順に、順次に満たされる。ストレージアドレスの１つのブロックが有効なデータに完全に割当てられた時、それは赤色ブロック１６８になる。ファイルがホストにより削除されるかあるいはファイルの部分がホストにより更新される時、赤色ブロック１６８内のいくつかのアドレスは最早有効なデータに割当てられていなくなることがあり、従ってそのブロックはピンク色ブロック１７２になる。本願明細書においてより詳しく論じられるように、ホストからデータを受け取るために割当てられる白色ブロック１７０は書き込みブロックと称され、フラッシング操作中にデータを受け入れるために割当てられる白色ブロックは再配置ブロックと称される。いろいろな目的のために複数の書き込みポインタが定められ得る。例えば、いろいろなアプリケーションにおいて論理アドレス空間は、アドレス範囲またはファイルサイズに基づいて複数の連続する範囲に細分され得る。論理アドレス空間の各々の独立している範囲は、ストレージアドレス空間においてそれ自身の書き込みブロックおよび関連する書き込みポインタを有するように構成され得る。論理アドレス空間アドレスランの分割は、ランシーケンスまたはファイルサイズに加えて、データのタイプに基づいて実行され得る。例えば、頻繁に更新されるＮＴＦＳ ＭＦＴテーブルデータを、稀に更新されるデータから分離したいという希望があり得る。
【００５５】
ストレージアドレス再マッピングアルゴリズムは、有効なデータをピンク色ブロック１７２から再配置ポインタとして知られている特別の書き込みポインタへ再配置すること（本願明細書ではフラッシングとも称される）による白色ブロック１７０の作成を管理する。ストレージアドレス空間が前述したように範囲またはファイルサイズにより細分されるならば、ストレージアドレスの各範囲は、それ自身の再配置ブロックおよび関連する再配置ポインタを持ち得る。フラッシング操作は、普通は、ピンク色ブロックを赤色ブロックおよび白色ブロックに変換するために、バックグラウンド操作として実行される。ピンク色ブロックは、その特性に応じてフラッシング操作のために選択される。再び図７を参照すると、１つの実施例では、有効なデータを有するアドレスが少ないほど、そのピンク色ブロックがフラッシングされる時に再配置を必要とするデータが少ないという結果となるので、最少量の有効なデータ（すなわち、図７において最少の陰影付きクラスタ）を有するピンク色ブロックが選択される。従って、図７の例では、ピンク色ブロックＢのほうが有効なデータを有するアドレスをより少なく持っているので、ピンク色ブロックＡに優先してピンク色ブロックＢが選択される。他の実施例では、フラッシング操作のために選択されるピンク色ブロックは、あるしきい値より少ない量の有効なデータと関連付けられているピンク色ブロックのグループのうちの任意の１つであり得る。そのしきい値は、おそらく、ピンク色ブロックの集合全体に含まれる有効なデータの平均量より少ない。その有効なデータのしきい値量またはそれ以下のピンク色ブロックの部分集合が、ホストまたはメモリシステムがピンク色ブロックをそれから選択し得るところのリストにおいて維持され得る。例えば、しきい値要件を現在満たしている確定された数（例えば、１６個）または割合（例えば、３０％）のピンク色ブロックの動的リストが維持され得て、そのリスト中の選択されたピンク色ブロックが絶対最少量の有効なデータを有するか否かに関わらず、そのリストからどのピンク色ブロックでもフラッシングのために選択され得る。メモリシステムまたはホストがそれから選択するところのリストを形成するピンク色ブロックの数または割合は、固定された値またはユーザ選択可能な値であり得る。リストは、格付けされた順序で、利用可能なピンク色ブロックから絶対最少量の有効なデータを有するピンク色ブロックを代表するピンク色ブロックのグループを含むことができ、あるいは単にしきい値要件内に属するピンク色ブロックを含むことができる。
【００５６】
その代わりに、あるいは組み合わされて、特定のピンク色ブロック１７２に付加的な陳腐化したデータを蓄積する計算された確率に基づくピンク色ブロックの選択も行われ得る。さらなる陳腐化したデータがピンク色ブロック１７２に蓄積される確率は、メモリにおいて最も長く存在し続けたデータは最も削除されそうもないという仮定に基づくことができる。従って、再配置ブロックであったピンク色ブロック１７２は、新しいホストデータを有する書き込みブロックであったピンク色ブロック１７２より古くから存在し続けているデータを包含する。フラッシングのためのピンク色ブロック１７２の選択プロセスは、近ごろ再配置ブロックであったピンク色ブロック１７２を先に標的にする。なぜならば、それらは、さらなるデータを削除される可能性が少なく、従ってより少量の付加的な陳腐化したデータが予期され得るからである。より新しいデータのほうが削除されてより多くの陳腐化したデータを作る可能性が大きいという仮定に基づいて、以前書き込みブロックであったピンク色ブロック１７２は後でフラッシングのために選択される。
【００５７】
ストレージアドレス再マッピングアルゴリズムの中でのデータの流れとブロック状態変化のパターンとが図１２に示されている。前述したように、ストレージアドレス再マッピング手法は、クラスタのブロックを考慮してアドレス空間を割当て、クラスタのブロック１６６を、他のクラスタのブロックを割当てる前に、満たし尽くす。これは、ホストからのデータが書き込まれる現在の書き込みブロックとなる１つの白色ブロックを先ず割当てることにより成し遂げられ、ホストからのデータは、それが受け取られた時間に応じて順次に書き込みブロックに書き込まれる（ステップ１８８において）。現在の書き込みブロック内の最後のページが有効なデータで満たされた時には、その現在の書き込みブロックは赤色ブロックとなり（ステップ１９０において）、新しい書き込みブロックが白色ブロックリストから割当てられる。現在の書き込みブロック内のいくつかのページが、その現在の書き込みブロックが完全にプログラムされる前に既に陳腐化していたならば、現在の書き込みブロックはピンク色ブロックに直接遷移し得るということに留意するべきである。この遷移は、明瞭性を得るために、示されていないけれども、それは、書き込みブロックからピンク色ブロックへの矢によって表され得る。
【００５８】
図１２のデータフローの特定の例を再び参照すると、赤色ブロック内の１つ以上のページがＬＢＡランの削除によって陳腐化した時、その赤色ブロックはピンク色ブロックとなる（ステップ１９２において）。ストレージアドレス再マッピングアルゴリズムがより多くの白色ブロックの必要性を検出した時、アルゴリズムは、ピンク色ブロックが白色ブロックになるようにピンク色ブロックから有効なデータを移すフラッシング操作を開始する（ステップ１９４において）。ピンク色ブロックをフラッシングするために、ピンク色ブロックの有効なデータは、再配置ブロックとして指定されていた白色ブロックに順次に再配置される（ステップ１９４および１９６において）。その再配置ブロックが満たされると、それは赤色ブロックになる（ステップ１９８において）。書き込みブロックに関して前に記されたように、再配置ブロックは、その中のいくつかのページが既に陳腐化していたならば、ピンク色ブロックに直接遷移することもできる。この遷移は、明瞭性を得るために、示されていないけれども、図１２において再配置ブロックからピンク色ブロックへの矢によって表され得る。
【００５９】
図１３は、代わりのデータフロー例を示し、この場合にはストレージアドレス再マッピング機能はバイナリパーティション２００およびマルチレベルセル（ＭＬＣ）パーティション２０１を有するフラッシュメモリに付けられている。ＭＬＣパーティション２００におけるブロック状態変化は図１２の場合と同じであるが、バイナリパーティション２００におけるブロック状態変化（ステップ２０２〜２０５における）はＭＬＣパーティション２０１のものとは異なる。バイナリパーティション２００において、ホストから受け取られるデータは、満たされて赤色ブロックになる（２０２において）まで順次書き込まれる書き込みブロックにおいて受け取られる。赤色ブロックのためのページが陳腐化したならば、そのブロックはピンク色ブロックとなる（２０３において）。ピンク色ブロックは、新しい白色ブロックを作るために（２０４において）本願明細書で論じられているようにフラッシングされることができ、それらはその後、バイナリパーティションにおいて新しい書き込みブロックとして割当てられる（２０５において）。しかし、バイナリパーティション２００に存するピンク色ブロックからの有効なデータは、赤色ブロックからの有効なデータと同様にＭＬＣパーティション２０１に送られ得る。
【００６０】
フラッシュメモリ７が分割されて、図１３に示されているように、ホストからデータを受け取るキャッシュとして機能するバイナリパーティション２００とこのバイナリパーティションからデータを受け取る主記憶領域として機能するＭＬＣパーティション２０１とを有する２階層システムとなっているメモリシステム２において、図８〜１１の「ホスト」はバイナリパーティションであり得る。従って、本願明細書で論じられるストレージアドレス再マッピング手法は完全にメモリシステム２の階層の中での操作に関連することができ、システムにおいて前の階層（この例ではバイナリパーティション２００）はホストと見なされ、現在の階層（ここではＭＬＣパーティション２０１）は記憶装置と見なされる。この関係は３以上の階層の構成を有するメモリシステムに拡張され得ることが考えられ、そこでは先行する階層はホストに類似し、現在の階層は記憶装置として扱われる。バイナリパーティションおよびＭＬＣパーティションを利用する他の実施形態では、ホスト１は、先ずバイナリパーティション２００を通過することを必要とせずにＭＬＣパーティション２０１に直接書き込むことができる。
【００６１】
論理から論理への変換、ＬＢＡからＤＬＢＡへの変換が記憶装置（図９）上のアプリケーションまたはホスト（図１０）上のアプリケーションによって実行される、図９および１０に示されているストレージアドレス再マッピングの実施例を参照して、図１２の状態図に従うアドレス操作の詳細な例が図１４〜１７と関連して次に論じられる。システムが図１２により表されるストレージアドレス再マッピングアルゴリズムに従って動作していたと仮定して、所与の時点でのＬＢＡアドレス空間２０８におけるホスト空きクラスタマップとＤＬＢＡアドレス空間２１０における空きクラスタマップとの仮想セクションが図１４に示されているように表され得る。ＬＢＡアドレス空間２０８において、空きクラスタ１６４は本質的にランダムな位置に分散している。ＤＬＢＡアドレス空間２１０において、２つの白色ブロック１７０が利用可能であり、異なる数の陳腐化した（空き）クラスタ１６４を有する３つのピンク色ブロック１７２がある。
【００６２】
ホストは、記憶装置に書き込むデータを次に得た時、ＬＢＡアドレス空間２０８を、それが利用可能である時には常に割当てる。図１５は、ストレージアドレス再マッピングアルゴリズムが、利用可能な白色ブロック１７０のうちの、書き込みブロック２１２になるべき１つをどのように割当てるか、また、各ＬＢＡアドレスが書き込みブロック２１２において利用可能なＤＬＢＡ空間内の連続するクラスタにどのようにマッピングされるかを示す。ＤＬＢＡ空間内の書き込みブロック２１２は、ＬＢＡアドレス位置に関わらず、ＬＢＡアドレスが書かれる順に書き込まれる。この例では、説明を容易にするために、ホストが空きＬＢＡクラスタを使用した時間順序はアドレス順序と同じであると仮定されるけれども、ストレージアドレス再マッピングアルゴリズムは、書き込みブロック２１２内のＤＬＢＡアドレスを、ＬＢＡアドレス番号順に関わらず、ＬＢＡアドレスが使用された時間順に割当てる。データは１つ以上のＤＬＢＡランをなして書き込みブロックに書き込まれる。ＤＬＢＡランは、同じＬＢＡラン内の連続するＬＢＡアドレスにマッピングされた連続するＤＬＢＡアドレスの集合である。ＤＬＢＡランは、ＤＬＢＡアドレス空間２１０内のブロック境界で終結させられなければならない。書き込みブロック２１２が満杯になった時には、１つの白色ブロック１７０が次の書き込みブロック２１２として割当てられる。
【００６３】
ＤＬＢＡブロックはフラッシュメモリの物理アドレス空間内のブロック２１４と整列し、従ってＤＬＢＡブロックサイズと物理アドレスブロックサイズとは同じである。ＤＬＢＡ書き込みブロック２１２におけるアドレスの配列も、物理アドレス空間における対応する更新ブロックの配列と同じである。この対応の故に、一般にガーベッジコレクションと称される別のデータ統合は物理的更新ブロックにおいては全く不要である。普通のガーベッジコレクション操作では、論理アドレスのブロックは、特定の範囲のＬＢＡアドレスを論理ブロックにおいて維持するために一般的に常にリアセンブルされ、それは物理的ブロックにおいても反映される。より具体的には、普通のガーベッジコレクション操作を利用するメモリシステムが特定の物理的ブロック内の１つのセクタに対応する更新された情報のセクタを受け取る時、メモリシステムは、その更新された１つまたは複数のセクタを受け取るために物理メモリ内の１つの更新ブロックを割当て、オリジナルの物理的ブロックからの残りの有効なデータの全てを更新ブロックの残りの部分の中に統合する。このように、標準的なガーベッジコレクションは、特定のＬＢＡアドレス範囲のためのデータのブロックを、その特定のアドレス範囲に対応するデータが常に１つの共通の物理的ブロックの中に統合されるように永続させる。以下でより詳しく論じられるフラッシング操作は、同じアドレス範囲におけるデータの統合を必要としない。その代わりに、本願明細書において開示されるフラッシング操作は、種々の物理的ブロックからのデータの集合であり得るデータの新しいブロックを作るためにアドレスマッピング（図８および１１の実施例）または再マッピング（図９および１０の実施例）を実行し、そこではデータの特定のＬＢＡアドレス範囲は意図的には統合されない。
【００６４】
前述したように、ストレージアドレス再マッピングアルゴリズムは、順次書き込みアルゴリズムが作動するために白色ブロックの充分な供給が利用可能であることを保証するように働く。ストレージアドレス再マッピングアルゴリズムは、データをピンク色ブロックから再配置ブロック２１６として知られる特別の書き込みブロックへフラッシングすることによる白色ブロックの作成を管理する（図１６）。フラッシングのために現在選択されているピンク色ブロックはフラッシングブロックと称される。
【００６５】
ここで図１５〜１６を参照すると、ブロックフラッシングプロセスの図が示されている。ストレージアドレス再マッピングアルゴリズムは、１つの白色ブロックを再配置ブロック２１６として指定し、これに、付加的な白色ブロックを作成するために、選択されたピンク色ブロックからデータがフラッシングされる。フラッシングブロック（図１５のピンク色ブロックＡ）内の、赤色データとも称される有効なデータは、フラッシングブロックを白色ブロック１７０に転換するために、再配置ブロック２１６内の連続するアドレスに再配置される。物理アドレス空間２１８の中の対応する更新ブロック２１４も、フラッシングされるデータを受け入れるように割当てられる。フラッシング操作はＤＬＢＡアドレス空間２１０における統合を既に成し遂げているので、ホストから受け取られる新しいデータのために使用される更新ブロック２１４と同じく、フラッシングされるデータを受け入れるための更新ブロック２１４は、有効なデータを統合するためのガーベッジコレクション操作を全く必要としない。
【００６６】
図１７に示されているように残りのピンク色ブロックから次のフラッシングブロック（図１６のピンク色ブロックＢ）が識別される。最少量の赤色データを有するピンク色ブロックが再びフラッシングブロックとして指定され、ピンク色ブロックの赤色データ（有効なデータ）が、開いている再配置ブロック内の連続する位置に転送される。更新ブロック２１４内の物理アドレスの並列割当ても行われる。再び、再配置ブロック２１６にマッピングされた物理的更新ブロック２１４においてデータ統合は不要である。ピンク色ブロックに対するフラッシング操作は、書き込みブロックとして指定された白色ブロックの消費を補うのに充分な速度で白色ブロックを作るためにバックグラウンド操作として実行される。図１４〜１７の例は、ホストからの新しいデータのために、またピンク色ブロックからの再配置されるデータのために、書き込みブロックおよび再配置ブロックが物理アドレス空間内のそれぞれの別々の更新ブロックと共にどのように別々に維持され得るかを示す。現在の書き込みブロックが完全にプログラムされた時にだけ、ホストから受け取られる新しいデータを関連付けるために新しい書き込みブロックを割当てるプロセスと同様に、新しい再配置ブロックは、好ましくは、前の再配置ブロックが完全にプログラムされた後に初めて割当てられる。新しい再配置ブロックは、割当て時に、好ましくは未記入容量を含むだけである、すなわち何時でも消去できる陳腐化したデータと関連付けられているだけであるか、あるいは既に消去されていて有効なデータをまったく含んでいないかである。
【００６７】
前述した実施形態では、ホストからの新しいデータは、単にホストからの他の新しいデータを受け取る書き込みブロックと関連付けられ、フラッシング操作時にピンク色ブロックからフラッシングされる有効なデータは、単に１つ以上のピンク色ブロックからの有効なデータを包含する再配置ブロックの中へ移される。他の実施例では、新しいデータと再配置されるデータとは、別々の書き込みブロックおよび再配置ブロックを必要とせずに単一の書き込みブロックに転送され得る。前述したように、他の実施形態でフラッシングのためのピンク色ブロックの選択が行われ得て、それらの実施形態では、現在のピンク色ブロックについての平均量などのしきい値より下の量の赤色データと関連付けられたピンク色ブロックのリストからどのピンク色ブロックでも選択され、あるいはピンク色ブロックは利用可能なピンク色ブロックのうちの特定のランキング（ピンク色ブロックと関連付けられた有効なデータの量に基づく）を有するピンク色ブロックからのいずれであってもよい。
【００６８】
フラッシング操作は、それからの「熱い」データが陳腐化されているところのブロックからの割合に「冷たい」データを、同様の割合に冷たいデータを包含する再配置ブロックに再配置する。これは、割合に熱いブロックおよび割合に冷たいブロックの別々の集団を作るという効果を有する。フラッシングされるべきブロックは、常に、最少量のデータを包含する熱いブロックとして選択される。熱いブロックの集団の作成は、再配置されなければならないデータの量を減少させることによって、メモリのストレス要因を低減する。
【００６９】
一実施形態では、フラッシングブロックとして選択されるピンク色ブロックは、最も過疎のピンク色ブロックすなわち最少量の有効なデータを包含するピンク色ブロックであることができて、ホストにより実行される特定の書き込みおよび削除操作に応答して選択されない。このような仕方でのピンク色ブロックのフラッシングブロックとしての選択は、有効なデータの最小限の再配置を伴うブロックフラッシング操作の実行を可能にする。なぜならば、そのように選択されるどのピンク色ブロックも、ホストによるファイルの削除の故に最多数の未割当てデータアドレスを蓄積しているからである。
【００７０】
ピンク色ブロック選択プロセスの一例は、最低数の有効なページまたはクラスタを有するピンク色ブロックの５％の中の任意のピンク色ブロックを選択することであり得る。バックグラウンドプロセスで、最低のページまたはクラスタ総数値を有する１６個のピンク色ブロックのリストが構築される。ピンク色ブロック識別プロセスは、「Ｐ」個のスケジュールされたブロックフラッシング操作により費やされる時間のうちに１サイクルを完成させることができる。フラッシングブロック識別プロセスにおける１つのサイクルが図１８に示されている。白色、ピンク色および他のタイプのＤＬＢＡアドレスブロックのためのブロックアドレスのリストを含むブロック情報テーブル（ＢＩＴ）が、以下でより詳しく記載されているようにストレージアドレス再マッピング機能によって維持されて、前のプロセスサイクル中に識別されたブロックの集合の後でＱ個のピンク色ブロックの次の集合を識別するために読まれる（ステップ２２０において）。ピンク色ブロックの第１の集合は、装置初期化後の第１のプロセスサイクルにおいて識別されるべきである。フラッシングブロックの利用可能性を保証するために、Ｑの値はＰのものより大きくあるべきである。１つの実施例では、Ｑの値は８であり、Ｐは４であり得る。集合中のピンク色ブロックの各々のために有効ページ総数値はゼロにセットされる（ステップ２２２において）。ＬＢＡとＤＬＢＡとの関係を追跡するために維持されるストレージアドレステーブル（ＳＡＴ）ページエントリは、集合中の任意のピンク色ブロックに置かれている有効データページを識別するために一度に一つずつスキャンされる（ステップ２２４において）。ストレージアドレステーブルは以下でより詳しく記載される。有効ページ総数値は適宜にインクリメントされる。全てのＳＡＴページがスキャンされた後、集合中のピンク色ブロックの各々についての有効ページ総数値は低有効ページ総数値のためのリスト中のピンク色ブロックについてのものと対比して評価され、リスト中のブロックは、必要ならば、集合からのブロックにより取って代わられる（ステップ２２６において）。ブロックフラッシング操作の完了後、次のブロックフラッシング操作のために１つのブロックが選択されるべきである。これは、リスト中の最低有効ページ総数値を有するブロックであるべきである。
【００７１】
図１６〜１７に関して記載されているようなブロックフラッシング操作を始める前に、再配置されなければならない有効なＤＬＢＡランの位置を決定するために、選択されたブロックはマッピングされなければならない。これは、ブロックから読み出されるデータの選択されたページのヘッダの中のＬＢＡアドレスと、これらのＬＢＡアドレスのためのＳＡＴエントリとを使用するサーチアルゴリズムにより成し遂げられる。サーチアルゴリズムは、それが徐々に構築する既知の有効なＤＬＢＡランおよび陳腐化したＤＬＢＡランのマップを使用する。有効なＤＬＢＡランは、ＳＡＴエントリがブロックにおけるその存在を明示する時、ブロックマップに加えられる。陳腐化したＤＬＢＡランは、マッピングされるブロック内のデータページヘッダにおけるＬＢＡの１つの範囲のためのＳＡＴエントリが他の１つのブロックにおける有効なＤＬＢＡの存在を明示する時、ブロックマップに加えられる。サーチプロセスは、ブロック内の全ＤＬＢＡアドレスが有効であるか陳腐化しているものとして明瞭にマッピングされるまで続行される。
【００７２】
ブロックフラッシング操作では、前述したブロックマッピングプロセスで識別された有効なＤＬＢＡランの中の全てのページが、選択されたブロックから再配置ブロック内の再配置ポインタに再配置される。再配置されたＤＬＢＡのためのエントリがＳＡＴリストに記録される。有効なＤＬＢＡランおよび陳腐化したＤＬＢＡランについての探索は、図９に示されているアレンジメントの場合にはメモリシステム２のコントローラ８によって実行され、ブロックＤＬＢＡマップは、コントローラと関連付けられているＲＡＭに格納され得る。図１０のアレンジメントに関して、ホストシステム１のＣＰＵが、探索を実行して、結果としてのブロックＤＬＢＡ情報をホストシステムＣＰＵと関連付けられたＲＡＭに格納することができる。
【００７３】
ストレージアドレス再マッピングアルゴリズムは、白色ブロックの数が所定しきい値より下に落ちた時に、データの書き込みのために割当てられ得る使用可能な白色ブロック容量が書き込みブロックへのホストデータの書き込みにより白色ブロック容量が消費されるのと同じ速度で作られることを保証するのに充分な速度でピンク色ブロックに対するフラッシング操作が実行されなければならないという原理に基づいて働く。ホストからのデータを書き込むことにより消費される書き込みブロックの中のページの数は、ブロックフラッシング操作により回復される陳腐化したページの数と釣り合わされなければならない。ブロックフラッシング操作の完了後、次のブロックフラッシング操作のために選択されたピンク色ブロックの中の陳腐化したデータのページの数が、前述したように、ＢＩＴおよびＳＡＴから特定のエントリを読み出すことにより、明らかにされる。次のブロックフラッシング操作は、書き込みブロックへのこの数のデータの有効なページの書き込みの直後に始まるように予定される。
【００７４】
ストレージアドレステーブル
前述したストレージアドレス再マッピングを実行するために、ストレージアドレステーブル（ＳＡＴ）が、ストレージアドレス空間内のデータの位置を追跡するために使用される。ＳＡＴ内の情報は、完全なフラッシュメタブロックに対する連続する更新の一部としても書き込まれる。従って、一つの実施例では、ＳＡＴ情報は、ホストから受け取られるデータのために使用される書き込みブロックとは別でかつフラッシング操作のために使用される再配置ブロックとは別の書き込みブロックに書き込まれる。他の実施例では、ＳＡＴ情報は、異なるグループのブロック（例えば、非ＳＡＴ情報により占められるＭＬＣフラッシュパーティションよりはむしろバイナリフラッシュパーティションの中のブロック）に格納され得る。その代わりに、ＳＡＴおよび非ＳＡＴデータは、同じタイプのフラッシュブロックに格納され得るが、ブロックにより分離される。さらに他の実施形態では、ＳＡＴおよび非ＳＡＴデータは、同じブロック内で混ぜ合わされ得る。
【００７５】
ＳＡＴは、図８〜１０の実施形態には関連するけれども、ホストファイルシステムがデータをアドレスの論理ブロックに順次に書き込むようになっていて第１の論理アドレスから第２の論理アドレスへの変換が不要である図１１とは関連しない。また、次の議論は、図９〜１０のホストおよび記憶装置の構成に関連するホストＬＢＡ空間からＤＬＢＡと称される（ストレージＬＢＡとも称される）第２のＬＢＡ空間への再マッピングに焦点を当てるけれども、この同じＳＡＴ手法が、ホストＬＢＡと関連付けられたデータが中間の論理から論理への変換なしで物理的ブロックに直接マッピングされる図８の実施形態に応用可能である。ＳＡＴ情報は、論じられた実施形態に関わらず、好ましくは記憶装置内のフラッシュメモリに格納される。ホストＬＢＡからＤＬＢＡへの再マッピングがホスト１８０上で行われる図１０の実施形態について、ＳＡＴ情報は記憶装置１８４内のフラッシュメモリに格納されるべく送られる。ストレージアドレス再マッピングアルゴリズムが記憶装置内のメモリマネージャで実行される図８の実施形態について、ＤＬＢＡという用語は、図９〜１０の実施形態で使用される第２の論理アドレス空間を指すよりはむしろフラッシュメモリ７内の物理アドレスを指し、ＤＬＢＡアドレスのブロックは物理メモリにおけるメタブロックを表す。
【００７６】
ストレージアドレステーブル（ＳＡＴ）は、ホストファイルシステムにより割当てられるＬＢＡアドレスをＤＬＢＡアドレスに関連付ける相関情報を含む。より具体的には、ＳＡＴは、ホストファイルシステムによって有効なデータに割当てられたＬＢＡアドレス空間内のアドレスの１つ１つのランとストレージアドレス再マッピングアルゴリズムによって作られたＤＬＢＡアドレス空間２１０内のアドレスの１つ以上のランとの間のマッピングを記録するために使用される。前述したように、システムアドレス空間の単位はＬＢＡであり、ＬＢＡランはホストファイルシステムによって有効なデータに現在割当てられているＬＢＡアドレスの１つの連続的な集合である。ＬＢＡランは、しばしば、未割当てＬＢＡアドレスと境を接するけれども、ＳＡＴデータ構造により必要とされるならばＬＢＡランは複数のより小さなＬＢＡランとして処理され得る。装置アドレス空間の単位はＤＬＢＡであり、ＤＬＢＡランは、同じＬＢＡラン内の連続するＬＢＡアドレスにマッピングされたＤＬＢＡアドレスの１つの連続的な集合である。ＤＬＢＡランは、ＤＬＢＡアドレス空間内のブロック境界で終結させられる。各ＬＢＡランは、ＳＡＴによって１つ以上のＤＬＢＡランにマッピングされる。ＬＢＡランの長さは、それがマッピングされているＤＬＢＡランの累積長さに等しい。
【００７７】
ＬＢＡランのためのＳＡＴエントリは、それがマッピングされている第１のＤＬＢＡランのためのエントリへのリンクを含む。それがまたマッピングされ得る後続のＤＬＢＡランは、このランに接して続く連続するエントリである。ＤＬＢＡランは、それがマッピングされているＬＢＡランの中のそのオフセットアドレスへの、ＬＢＡランの絶対ＬＢＡアドレスへのではない、逆方向リンクを含む。１個のＬＢＡアドレスは、１つのＬＢＡランの中での１つのＬＢＡオフセットとして定義され得る。ＳＡＴは、ＬＢＡランにマッピングされている各ＤＬＢＡランの先頭に対応するＬＢＡオフセットを記録する。従って、１個のＬＢＡアドレスに対応する１個のＤＬＢＡアドレスは、１つのＤＬＢＡランの中での１つのＤＬＢＡオフセットとして識別され得る。ＳＡＴにおけるＬＢＡランは有効なデータのランだけのためのものであり得るけれども、ＳＡＴは、他の実施例では、有効なデータおよび陳腐化したデータの両方のためのＬＢＡランを記憶するようにも構成され得る。
【００７８】
ＳＡＴは、ＳＡＴブロックとして知られるＬＢＡアドレスのブロックの中で実現される。ＳＡＴは、１つの確定された最大数のＳＡＴブロックを含み、１つの確定された最大数の有効なＳＡＴページを包含する。従って、ＳＡＴは、１つの指定された最大数のＳＡＴブロックのために、それが索引付けすることのできる１つの最大数のＤＬＢＡランを有する。１つの最大数のＳＡＴブロックが確定されるけれども、ＳＡＴのエントリの数は、ホストにより割当てられたＬＢＡの断片化に順応するので、ＳＡＴは、最大数まで自動的にスケーラブルである可変サイズテーブルである。従って、ホストが高度に断片化されたＬＢＡを割当てるならば、ＳＡＴは、ホストが断片化の程度のより低いＬＢＡのグループをデータに割当てる場合よりも多くのエントリを含む。従って、ホストＬＢＡの断片化の程度が低くなれば、ＳＡＴのサイズは小さくなる。ＳＡＴは固定された数の論理アドレスをかたくなに追跡し更新するよりはむしろホストＬＢＡアドレスの１つのランを１つのエントリにおいて１つ以上のＤＬＢＡランにマッピングするので、断片化の程度が低ければマッピングするべき別々のランは少なくなり、別々のランが少なければＳＡＴのエントリは少なくなる。
【００７９】
ＳＡＴのラン対ランマッピングアレンジメントの故に、ホストＬＢＡアドレスの１つのランは２つ以上のＤＬＢＡランにマッピングされ、その場合、ホストＬＢＡランは有効なデータに割当てられた連続する論理アドレスの１つの集合であり、ＤＬＢＡ（あるいはストレージＬＢＡ）ランは同じメタブロックの中の、同じホストＬＢＡランにマッピングされているＤＬＢＡアドレスの１つの連続的な集合である。ＳＡＴ索引付けおよびマッピング構造の階層が図１９に示されている。ＬＢＡラン２３０および対応するＤＬＢＡラン２３２が示されている。ＬＢＡ対ＤＬＢＡマッピング情報はＳＡＴページ２３４に包含される。ＬＢＡ対ＳＡＴページ索引付け情報がＳＡＴ索引ページ２３６に包含され、マスターページ索引２３８は、図１０の実施例ではホストプロセッサと関連付けられたＲＡＭに、図８〜９の実施例ではコントローラ８と関連付けられたＲＡＭにキャッシュされる。
【００８０】
ＳＡＴは、普通は複数のＳＡＴブロックを含むけれども、ＳＡＴ情報はＳＡＴ書き込みブロックとして現在指定されている単一のブロックに書き込まれるだけであり得る。他の全てのＳＡＴブロックはすっかり書き込まれ、有効なページおよび陳腐化したページの組み合わせを包含し得る。ＳＡＴページはホストＬＢＡアドレス空間の１つの可変範囲の中の全てのＬＢＡランのためのエントリを、それらがマッピングされている装置アドレス空間内のランのためのエントリと共に包含する。多数のＳＡＴページが存在し得る。ＳＡＴ索引ページは、ホストＬＢＡアドレス空間の１つのより大きな範囲の中の各々の有効なＳＡＴページの位置への１つの索引を含む。少数のＳＡＴ索引ページが存在し、それは通例１である。ＳＡＴ内の情報は、単一のＳＡＴ書き込みブロック内の次の利用可能な位置に更新されたページを再書き込みし、そのページの前のバージョンを陳腐化したものとして扱うことによって改変される。従って、多数の無効なページがＳＡＴ内に存在し得る。ＳＡＴブロックは、ホストデータについて前に記載されたものと類似する、ページを書き込みかつブロックをフラッシングするためのアルゴリズムによって管理される。
【００８１】
ＳＡＴブロック
各ＳＡＴブロックは、ＳＡＴ情報の記憶に専用されるＤＬＢＡアドレスの１つのブロックである。ＳＡＴブロックはテーブルページに分割され、それらに１つのＳＡＴページ２３４またはＳＡＴ索引ページ２３６が書き込まれ得る。ＳＡＴブロックは、有効なＳＡＴページ２３４、有効なＳＡＴ索引ページ２３６および陳腐化したページの任意の組み合わせを包含し得る。図２０を参照すると、サンプルＳＡＴ書き込みブロック２４０が示されている。データは、インクリメンタルなＳＡＴ書き込みポインタ２４２により定められる連続する位置でＳＡＴ書き込みブロック２４０に書き込まれる。データは、ＳＡＴ書き込みブロック２４０として指定されている単一のＳＡＴブロックに書き込まれ得るにすぎない。前に記載されたホストデータ書き込みブロック（例えば、図１５〜１７の２１２）についてと同様に、ＳＡＴ書き込みブロック２４０がすっかり書き込まれた時、１つの白色ブロックが新しいＳＡＴ書き込みブロック２４０として割当てられる。ＳＡＴページ位置は、そのＳＡＴブロックの中でのそのシーケンス番号によりアドレス指定される。
【００８２】
ＳＡＴページ
ＳＡＴページ２３４は、ＳＡＴにおけるマッピング情報の最小の更新可能な単位である。更新されたＳＡＴページ２３４は、ＳＡＴ書き込みポインタ２４２により定められる位置に書き込まれる。ＳＡＴページ２３４はインクリメントするＬＢＡアドレスを有するＬＢＡランの集合についてのマッピング情報を包含するけれども、引き続くＬＢＡランのアドレス同士は連続していなくてもよい。１つのＳＡＴページ２３４内のＬＢＡアドレスの範囲は他のどのＳＡＴページ２３４内のＬＢＡアドレスの範囲とも重なり合わない。ＳＡＴページ２３４はＳＡＴブロックの完全な集合の全体にわたって無制限に分散させられ得る。ＬＢＡアドレスの任意の範囲のためのＳＡＴページ２３４が任意のＳＡＴブロックの中にあり得る。ＳＡＴページ２３４は、索引バッファフィールド２４４、ＬＢＡフィールド２４６、ＤＬＢＡフィールド２４８および制御ポインタ２５０を含み得る。パラメータバックアップエントリは、また、揮発性ＲＡＭに格納されているいくつかのパラメータの値を包含する。
【００８３】
ＳＡＴページ２３４の中のＬＢＡフィールド２４６は、ＬＢＡアドレスの１つの範囲の中で、データ記憶のために割当てられた連続するＬＢＡアドレスのランのためのエントリを包含する。１つのＳＡＴページ２３４がまたがるＬＢＡアドレスの範囲は、他のどのＳＡＴページ２３４がまたがるＬＢＡエントリの範囲とも重なり合わない。ＬＢＡフィールドは可変長のフィールドであって、可変数のＬＢＡエントリを包含する。ＬＢＡフィールド２４６の中に、ＳＡＴページ２３４により索引付けされるＬＢＡアドレスの範囲の中のどのＬＢＡランのためにも１つのＬＢＡエントリ２５２が存在する。１つのＬＢＡランは１つ以上のＤＬＢＡランにマッピングされる。図２１に示されているように、ＬＢＡエントリ２５２は次の情報、すなわち、ラン中の第１のＬＢＡ２５４、セクタ数で表したＬＢＡランの長さ２５６、および、ＬＢＡランがマッピングされている第１のＤＬＢＡランの、同じＳＡＴページ２３４のＤＬＢＡフィールドの中でのＤＬＢＡエントリ番号２５８を含む。
【００８４】
ＳＡＴページ２３４の中のＤＬＢＡフィールド２４８は、同じＳＡＴページ２３４内のＬＢＡフィールドの中のＬＢＡランにマッピングされたＤＬＢＡアドレスの全てのランのためのエントリを包含する。ＤＬＢＡフィールド２４８は、可変長のフィールドであって、可変数のＤＬＢＡエントリ２６０を包含する。ＤＬＢＡフィールド２４８の中で、同じＳＡＴページ２３４のＬＢＡフィールド２４６の中の１つのＬＢＡランにマッピングされているどのＤＬＢＡランについても１つのＤＬＢＡエントリ２６０が存在する。各ＤＬＢＡエントリ２６０は、図２２に示されているように、次の情報、すなわち、ラン内の第１のＤＬＢＡアドレス２６２と、第１のＤＬＢＡアドレスがマッピングされているＬＢＡランにおけるＬＢＡオフセット２６４とを含む。どのＳＡＴページ２３４にもその一部分として書かれるけれども最も最近に書かれたＳＡＴページ２３４においてのみ有効なままであるＳＡＴページ／索引バッファフィールドは、ＳＡＴ索引エントリ２６６を包含する。
【００８５】
ＳＡＴ索引エントリ２６６は、関連するＳＡＴ索引ページ２３６において有効なエントリを現在持っていないＳＡＴ内のどのＳＡＴページ２３４のためにも存在する。ＳＡＴ索引エントリは、ＳＡＴページ２３４が書かれるたびに作成または更新され、関連するＳＡＴ索引ページ２３６が更新される時に削除される。それは、ＳＡＴページ２３４により索引付けされた第１のＬＢＡ２６８、ＳＡＴページ２３４により索引付けされた最後のＬＢＡ２７０、ＳＡＴページ２３４を包含するＳＡＴブロック番号２７２、およびＳＡＴブロック内のＳＡＴページ２３４のページ番号２７４を包含する。ＳＡＴ索引フィールド２７６は、固定された数のＳＡＴ索引エントリ２７８のための容量を有する。この数は、ＳＡＴページ２３４およびＳＡＴ索引ページ２３６が書かれ得る相対的頻度を決定する。１つの実施例では、この固定された数は３２であり得る。
ＳＡＴページフィールドポインタ２５０は、ＬＢＡフィールドの先頭からＤＬＢＡフィールドの先頭までのオフセットを確定する。それはＬＢＡエントリの数としてのオフセット値を包含する。ＳＡＴページ２３４内のパラメータバックアップエントリは、揮発性ＲＡＭに記憶されているパラメータの値を包含する。これらのパラメータ値は、パワーサイクル後にＲＡＭ（図８〜９の実施例ではコントローラ８と関連付けられ、図１０の実施例ではホストＣＰＵと関連付けられる）内の情報の初期化の間に使用される。それらは、最も最近に書かれたＳＡＴページ２３４においてのみ有効である。
【００８６】
ＳＡＴ索引ページ
ＳＡＴ索引ページ２３６の集合は、ＳＡＴ内のどの有効なＳＡＴページ２３４の位置への１つの索引も提供する。個々のＳＡＴ索引ページ２３６は、ＬＢＡアドレスの１つの範囲に関連する有効なＳＡＴページの位置を定めるエントリ２７８を包含する。１つのＳＡＴ索引ページ２３６がまたがるＬＢＡアドレスの範囲は、他のどのＳＡＴ索引ページ２３６がまたがるＬＢＡアドレスの範囲とも重なり合わない。エントリは、それらが関連するＳＡＴページのＬＢＡアドレス範囲値に従って順序付けされる。ＳＡＴ索引ページ２３６は、固定された数のエントリを包含する。ＳＡＴ索引ページ２３６は、ＳＡＴブロックの集合全体にわたって無制限に分散させられ得る。ＬＢＡアドレスの任意の範囲のためのＳＡＴ索引ページ２３６は、任意のＳＡＴブロックの中にあり得る。ＳＡＴ索引ページ２３６は、ＳＡＴ索引フィールドおよびページ索引フィールドを含む。
【００８７】
ＳＡＴ索引フィールド２７６は、ＳＡＴ索引ページ２３６がまたがるＬＢＡアドレス範囲の中の全ての有効なＳＡＴページのためのＳＡＴ索引エントリを包含する。ＳＡＴ索引エントリ２７８は、単一のＳＡＴページ２３４に関連し、次の情報、すなわち、ＳＡＴページ２３４により索引付けされた第１のＬＢＡ、ＳＡＴページ２３４を包含するＳＡＴブロック番号、およびＳＡＴブロック内のＳＡＴページ２３４のページ番号を包含する。ページ索引フィールドは、ＳＡＴ内の全ての有効なＳＡＴ索引ページ２３６のためのページ索引エントリを包含する。１つのページ索引エントリが、ＳＡＴ内のどの有効なＳＡＴ索引ページ２３６のためにも存在し、次の情報、すなわち、ＳＡＴ索引ページにより索引付けされた第１のＬＢＡ、ＳＡＴ索引ページを包含するＳＡＴブロック番号、およびＳＡＴブロックの中のＳＡＴ索引ページのページ番号を包含する。ページ索引エントリは、最も最近に書かれたＳＡＴ索引ページ２３６においてのみ有効である。
【００８８】
一時的ＳＡＴデータ構造
図１９に示されているアドレスマッピングの長期間記憶のためのＳＡＴ階層の一部分ではないけれども、ＳＡＴを更新するための階層的手続きの中で付加的なデータ構造が使用され得る。１つのそのような構造は、ＬＢＡエントリと、ＳＡＴページ２３４にまだ書かれていないＬＢＡランに対する更新操作またはブロックフラッシング操作から生じた新しいアドレスマッピングのための新しいエントリのための対応するＤＬＢＡマッピングとを含むＳＡＴリストである。ＳＡＴリストはＲＡＭ内の揮発性構造であり得る。ＳＡＴリスト内のエントリは、ＳＡＴページ更新中にそれらがＳＡＴページ２３４に書かれる時にクリアされる。
【００８９】
テーブルページ
テーブルページは、ＳＡＴブロック内のＤＬＢＡアドレス空間の固定されたサイズの単位であり、これは１つのＳＡＴページ２３４または１つのＳＡＴ索引ページ２３６を記憶するために使用される。テーブルページの最小サイズは１ページであり、最大サイズは１メタページであり、ここでページおよびメタページは、物理メモリにおけるページおよびメタページに対応するＤＬＢＡアドレス空間の単位である。
ＳＡＴにおけるエントリサイズ
ＳＡＴページ２３４およびＳＡＴ索引ページ２３６の中のエントリのサイズが表１に示されている。
【表１】

【００９０】
アドレス変換
ＳＡＴは、ホストファイルシステムのＬＢＡアドレスに対応するＤＬＢＡアドレスの位置を迅速に突き止めるために有益である。一実施形態では、有効なデータにマッピングされているＬＢＡアドレスだけがＳＡＴに含まれる。ＳＡＴページ２３４は、一ＳＡＴページ２３４から別のＳＡＴページへとＬＢＡ範囲同士が重なり合わないようにＬＢＡ順に配列されるので、所望のデータに向かって迅速に進むために単純なサーチアルゴリズムが使用され得る。このアドレス変換手続きの一例が図２４に示されている。ターゲットＬＢＡ２８０が先ず（ストレージアドレス再マッピングの実施例がそれぞれ図９のように構成されているかまたは図１０のように構成されているかにより）コントローラまたはプロセッサによって受け取られる。他の実施形態では、ＳＡＴが有効なデータおよび陳腐化したデータにマッピングされたＬＢＡアドレスを含んで、データが有効であるかそれとも陳腐化しているかを追跡するということが考慮され得る。
【００９１】
図２４は、アドレス変換手続きを示すほかに、最後に書かれたＳＡＴ索引ページからのページ索引フィールドと最後に書かれたＳＡＴページからの索引バッファフィールドとがどのように構成され得るかも示す。図２４の実施例では、これら２つのフィールドは、記憶装置またはホストのＲＡＭなどの揮発性メモリで一時的に維持される。最後に書かれたＳＡＴ索引ページのページ索引フィールドは、どのＳＡＴ索引ページへのポインタをも含む。索引バッファフィールドは、索引ページにまだ書き込まれていない近ごろ書かれたＳＡＴページのための索引エントリの集合を包含し得る。
【００９２】
対応するＤＬＢＡアドレスとのターゲットＬＢＡアドレスについてのマッピング情報は、そのターゲットアドレスを含む１つの範囲のＬＢＡアドレスについての全マッピング情報を包含する特定のＳＡＴページ２３４において保持される。アドレス変換手続きの第１の段階は、このターゲットＳＡＴページを識別して読むことである。図２４を参照すると、ターゲットＬＢＡのためのＳＡＴ索引エントリが存在するか否かを判定するために、最後に書かれたＳＡＴページの索引バッファフィールドのキャッシュされているバージョンに対して二分探索が実行される（ステップ２８２において）。ターゲットＳＡＴページが近ごろ再書き込みされているけれどもターゲットＳＡＴページの新しい位置を記録したＳＡＴ索引エントリを組み込んだＳＡＴ索引ページがまだ書かれていなければ、１つのエントリが存在する。ターゲットＬＢＡのための索引エントリが発見されたならば、それはターゲットＳＡＴページの位置を定義し、このページが読み出される（ステップ２８４において）。
【００９３】
ステップ２８２でターゲットＬＢＡのためのＳＡＴ索引エントリが発見されなければ、ターゲットＬＢＡのためのＳＡＴ索引エントリの位置を突き止めるために、最後に書かれたＳＡＴ索引ページのページ索引フィールドのキャッシュされたバージョンに対して二分探索が実行される（ステップ２８６において）。ステップ２８６で発見されたターゲットＬＢＡのためのＳＡＴ索引エントリは、ターゲットＬＢＡを包含するＬＢＡアドレス範囲のためのＳＡＴ索引ページの位置を定める。このページが読み出される（ステップ２８８において）。ターゲットＬＢＡのためのＳＡＴ索引エントリの位置を突き止めるために二分探索が実行される（ステップ２９０において）。ターゲットＬＢＡのためのＳＡＴ索引エントリは、ターゲットＳＡＴページの位置を定める。このページが読み出される（ステップ２９２において）。
【００９４】
ターゲットＳＡＴページがステップ２８４またはステップ２９２で読まれた時、ＬＢＡからＤＬＢＡへの変換が次のように実行され得る。ターゲットＬＢＡを組み込んだターゲットＬＢＡランのためのＬＢＡエントリの位置を突き止めるために、ＬＢＡフィールドに対して二分探索が実行される。ターゲットＬＢＡランの中でのターゲットＬＢＡのオフセットが記録される（ステップ２９４において）。フィールドポインタ内の情報は、二分探索のためのＬＢＡフィールドの長さを、また、ＬＢＡフィールドの先頭に対してのＤＬＢＡフィールドの先頭をも定める（ステップ２９６において）。ステップ２９４で発見されたＬＢＡエントリは、ＬＢＡランにマッピングされている第１のＤＬＢＡエントリのＤＬＢＡフィールドの中での位置を定める（ステップ２９８において）。ステップ２９４で判定されたオフセットは、ステップ２９８で位置が突き止められたより多くのＤＬＢＡエントリのうちの１つと共に、ターゲットＤＬＢＡアドレスを判定するために使用される（ステップ３００において）。
【００９５】
他の１つの実施形態では、有効なデータと関連付けられているＬＢＡアドレスの各ランのためにＳＡＴにおいて別々のＬＢＡエントリを生成する代わりに、ＬＢＡアドレスブロックが、各ＬＢＡアドレスブロックがＳＡＴ上の単一のエントリであるように、ＳＡＴにおいてマッピングされ得る。この実施形態では、単なる個々のＬＢＡランよりはむしろＬＢＡアドレス空間内の完全なＬＢＡアドレスブロックがＳＡＴにおいて記録され得る。この実施例におけるＬＢＡエントリは、ＬＢＡアドレスブロックがマッピングされているＤＬＢＡアドレス空間内のＤＬＢＡランの数と、同じＳＡＴページ内の第１のＤＬＢＡランへのポインタとを記録する単一のエントリである。記憶装置に格納されているデータの断片化の程度によって、最低で１つのＤＬＢＡランあるいは最高でＬＢＡアドレスブロック内のクラスタの数までに、１つのＬＢＡアドレスブロックがマッピングされ得る。
【００９６】
ＬＢＡアドレスブロックのための対応するＤＬＢＡエントリは、各ＤＬＢＡランのＤＬＢＡブロックおよびアドレスオフセットの両方およびその対応するＬＢＡオフセットを記録する。有効なデータと関連付けられたＬＢＡランだけが記録される、各ＬＢＡランのために別々のＬＢＡエントリを記録する前に論じられたＳＡＴのバージョンとは違って、ＬＢＡアドレスブロック内の全てのＬＢＡランが記録される。従って、有効なデータに現在割当てられていないＬＢＡアドレスブロック内のＬＢＡランも、有効なデータに割当てられているＬＢＡランと同じく記録される。ＳＡＴページのＤＬＢＡエントリ部分において、ＬＢＡアドレスの割当てられていない集合の先頭を示すＬＢＡオフセットは、ＤＬＢＡアドレス空間内のデフォルト値とペアにされる。このデフォルト値は未割当てアドレスを表す。同じＳＡＴ構造および機能の全体が、図１９〜２０に関して論じられた基本的なＳＡＴ階層と同様に、ＬＢＡアドレスブロックマッピングの実施例に当てはまるけれども、ＳＡＴページは、個々のＬＢＡラン対ＤＬＢＡラン情報よりはむしろＬＢＡアドレスブロック対ＤＬＢＡランのマッピング情報を表す。また、この実施例ではＳＡＴ索引ページは、ＬＢＡアドレスブロック対ＳＡＴページのマッピング情報を記憶する。
【００９７】
ＳＡＴ例
例として、図１９〜２３の個々のＬＢＡラン対ＤＬＢＡランのマッピングを用いる、図９または１０の論理対論理ストレージアドレス再マッピング手法を用いるデータ書き込みプロセスが図２５に示されている。図２５において、ＬＢＡアドレス空間３０２とＤＬＢＡアドレス空間３０４とが時間Ａ〜Ｄについて示されている。時間Ａにおいて、データがホストによって３つの別々のＬＢＡランに、Ｌ１、Ｌ２およびＬ３の順に、書かれる。各データランは、ＬＢＡ空間３０２内で他から分離されている。３つのＬＢＡランは、次に、時間Ａにおいて示されているようにＤＬＢＡアドレス空間内のブロックに、それらが受け取られた時間順に、再マッピングされる。この例は、ＤＬＢＡアドレス空間３０４内のクラスタの第１のブロックが現在の書き込みブロックであったということを仮定している。従って、ＬＢＡアドレスランＬ１はＤＬＢＡアドレスランＤ１と、書き込みブロックとして指定された他の１つの白色ブロックの中のＤ２とに分割される。同様に、Ｄ２の後に続いて、Ｌ２のＬＢＡアドレス空間ランはＤＬＢＡアドレス空間ランＤ３に変換される。最後のＤＬＢＡアドレス空間ランＬ３は、次に、クラスタのブロックをＤＬＢＡアドレス空間ランＤ４で完成させて新しい書き込みブロックをＤＬＢＡアドレス空間ランＤ５で開始させるために使用される。以下の表Ａを参照すると、これまでに記載されたＬＢＡ対ＤＬＢＡ変換は、時間Ａにおいて、各ＬＢＡランにポインタと、ＬＢＡアドレス空間におけるクラスタ長さと、ＤＬＢＡポインタとが与えられているＳＡＴを生じさせる。
【００９８】
ＳＡＴのＤＬＢＡエントリ側に、１つのＬＢＡランに対応する各ＤＬＢＡが記載されている。この例では、単一のＬ１のＬＢＡランがＤＬＢＡアドレス空間内の２つの別々のブロックに分割されているので、２つのＤＬＢＡランがある。各ＤＬＢＡランの後に、第１ＬＢＡクラスタおよびＤＬＢＡマーカーからのオフセットが提供されるように、ＬＢＡオフセット数が提供されている。マーカーＤＬＢＡ２は、ＬＢＡランＬ１の中に５クラスタであるアドレスを有して続いているので、そのオフセットは５である。ＬＢＡ２マーカーおよびＬＢＡ３マーカーは続いてＳＡＴのＬＢＡエントリ側にＬＢＡ順に記載されている。従って、ＤＬＢＡアドレス空間内のデータランはＬ１，Ｌ２およびＬ３に対応し、Ｌ１，Ｌ２およびＬ３はこれらの別々のランが書かれた順序を表すけれども、表のＬＢＡエントリ側はＬＢＡ時間順ではなくてＬＢＡアドレス順に編成されている。
【表Ａ】

【００９９】
再び図２５の、時間Ｂのところを参照すると、付加的なＬＢＡアドレスランＬ４がＬ２に付加されている。ランＬ２およびＬ４は実際には単一のＬＢＡランを形成するけれども、この例では明瞭性を得るために別々に識別される。Ｌ４のためのデータは、部分的に満たされた第３の書き込みブロックにおいてＤ５内の最後のエントリの後にＤＬＢＡアドレスランＤ６として書かれる。表Ｂに示されているように、時間Ｂ後のＳＡＴは、表のＬＢＡエントリ側の末尾に単にＬＢＡ４マーカーを付け加え、ＤＬＢＡエントリ側のＤＬＢＡ７を指す。
【表Ｂ】

【０１００】
図５の時間Ｃのところの活動を参照すると、ホストは、そのデータがＬＢＡアドレスランＬ１およびＬ２に書かれていたところの１つまたは複数のファイルを削除している。ＤＬＢＡアドレス空間３０４において、Ｌ１はＤ１およびＤ２に対応し、Ｌ２はＤ３に対応する。これらのランは今では陳腐化したデータに関連しているので、この例では前は赤色ブロックであった２つのアドレスブロックは今では有効な（赤色）データと陳腐化した（白色）データとの混合の故にピンク色ブロックである。以下の表Ｃに示されているように、ＳＡＴはそれに応じて更新される。有効なＬＢＡランだけが残るように全ての陳腐化したＬＢＡランが除去される。ＬＢＡアドレス空間ランＬ３およびＬ４だけが残るので、ＬＢＡエントリはマーカーＬＢＡ２およびＬＢＡ４および対応するＤＬＢＡポインタを含むだけである。ＳＡＴのＤＬＢＡエントリ側も、有効なデータのために必要とされるＤＬＢＡポインタを含むだけである。
【表Ｃ】

【０１０１】
図２５に示されている時間の最後のスナップショット、時間Ｄにおいて、オリジナルのＬＢＡアドレス空間ランＬ３は、ホストによってＬＢＡアドレス空間Ｌ５のところの情報で部分的に更新されている。対応するＤＬＢＡアドレス空間変換はＤ４およびＤ５の陳腐化した部分に対する変換であって付加的な白色空間が示され、次に、Ｌ５の新しいＬＢＡランがＤＬＢＡアドレス空間内の現在の書き込みブロックの末尾に、ブロックが完成するまで、順次に付加され、そしてＬＢＡアドレス空間ランの残りがＤＬＢＡアドレスに変換され得るように新しい書き込みブロックが識別される。これは、１つの書き込みブロックを完成させるＤＬＢＡランＤ７と、新しい書き込みブロックを開始させるＤ８とを生じさせる。以下の表Ｄを参照すると、表は再び更新されていて、ＬＢＡ空間３０２のＬＢＡ２ポインタは依然としてＤＬＢＡ空間３０４のＤＬＢＡポインタのうちの第１のものを指しているが、ＤＬＢＡエントリ側は、Ｌ３と対応するＤＬＢＡアドレスの残りと対応するＤＬＢＡランを開始させる付加的な３つのＤＬＢＡポインタを含む。ＬＢＡ空間３０２においてＬ４に対して変更は行われていなかったので、ＬＢＡ４と対応する、Ｌ４のためのエントリは、同じままである。図２５の例はクラスタの連続的なブロックを示すように思われるということに留意するべきである。クラスタの連続的なブロックが利用可能であるということはあり得るけれども、ＤＬＢＡアドレス空間のブロック同士が間にある１つ以上のブロックによって分離されるということが予期される。連続的なＤＬＢＡアドレス空間ブロックは、単に説明の便宜のために提供されている。
【表Ｄ】

陳腐化したＳＡＴ情報を削除して新しい白色ブロックを再使用のために作成するために、データのためのＤＬＢＡアドレスブロックについて前に記載されたものと類似するＳＡＴフラッシング方式が実行される。
【０１０２】
ストレージアドレス再マッピングアルゴリズムは、白色ブロックの数が所定しきい値より少なくなった時、書き込みブロックへのホストデータの書き込みにより白色容量が消費されるのと同じ速度で、データ書き込みのために割当てられ得る使用可能な白色容量が作られることを保証するのに充分な速度でピンク色ブロックに対してフラッシング（再配置とも称される）操作が行われなければならないという原理に基づいて作用する。データ書き込みのために割当てられ得る使用可能な白色クラスタ容量は、白色ブロック内の容量に、フラッシング操作中にデータが書き込まれ得る最配置ブロックの中の白色クラスタ容量を加えたものである。
【０１０３】
フラッシング操作のために選択されたピンク色ブロックの白色クラスタ容量が各ピンク色ブロックのｘ％を占めるとすれば、１つのピンク色ブロックに対するフラッシング操作により作られる新しい使用可能な容量は、そのピンク色ブロックから作られる１つの完全な白色ブロックから、そのフラッシングされるブロックからのデータの再配置によって再配置ブロックにおいて消費される一ブロックの（１００−ｘ）％を差し引いたものである。従って、１つのピンク色ブロックに対するフラッシング操作は、１つの白色ブロックのｘ％の新しい使用可能な容量を作る。従って、書かれるホストデータにより満たされる各書き込みブロックについて、フラッシュ操作は１００／ｘ個のピンク色ブロックに対して実行されなければならず、再配置されなければならないデータは（１００−ｘ）／ｘ個のブロックである。従って、プログラムされるセクタの、ホストにより書かれるセクタに対する比は，１＋（１００−ｘ）／ｘとしておおよそ定義される。
【０１０４】
平均的なピンク色ブロックにおける白色クラスタ容量の割合は、使用されている総装置容量の割合と赤色ブロックであるデータを包含するブロックの割合とにより決定される。例えば、装置が８０％満たされていて、データを包含するブロックの３０％が赤色ブロックであるならば、ピンク色ブロックは２６．２％の白色クラスタ容量を含む。装置におけるＬＢＡアドレスにおけるデータ削除の一様でない分布が、いくつかのピンク色ブロックが白色容量の平均％の２倍を有するという結果を生じさせることがありそうである。従って、この例では、フラッシング操作のために選択されるピンク色ブロックは５２．４％白色容量を有することになり、すなわち、ｘ＝５２．４となり、ホストにより書かれるデータのセクタあたりのプログラムされるセクタの比は１．９０となる。
【０１０５】
どのピンク色ブロックをフラッシングするかを決定する時には、それがホストデータピンク色ブロックであってもＳＡＴピンク色ブロックであっても、ストレージアドレス再マッピングアルゴリズムは、ＮＴＦＳにより書かれる＄ｂｉｔｍａｐファイルを監視することによって未割当てアドレスの指定を検出することができる。フラッシング操作は、２つの方法で予定され得る。好ましくは、フラッシング操作は、バックグラウンド操作として働き、従って、ホストデータ書き込み速度が影響を受けないようにＳＳＤまたは他の携帯可能なフラッシュメモリ装置がアイドルである間だけ機能する。その代わりに、フラッシング操作は、ホストがデータを書いている時にアクティブであるフォアグラウンド操作で利用され得る。フラッシング操作がフォアグラウンド操作として構成されるならば、これらの操作は、ホストの活動が生じた時にあるいは「ｆｌｕｓｈ ｃａｃｈｅ（フラッシュキャッシュ）」コマンドがＳＳＤまたは携帯可能なフラッシュメモリ装置の潜在的パワーダウンを意味する時に、自動的にサスペンドさせられ得る。フォアグラウンドおよびバックグラウンドフラッシング操作選択は動的決定であり得て、フォアグラウンド操作は、記憶装置のアイドル状態中に達成され得るよりも高いフラッシング速度が要求される時に実行される。例えば、ホストまたは記憶装置は、記憶装置が満杯になるまで一定のホストデータ書き込み速度を維持するようにフラッシング速度が制御されるように、フォアグラウンドおよびバックグラウンドのフラッシング操作の間でトグルすることができる。フォアグラウンドフラッシング操作は、ホストデータ書き込み操作と交互配置され得る。例えば、ホストインターフェイスで維持されている活動の故に不十分なアイドル時間が利用可能であるならば、ブロックフラッシング操作を実行するためのデータページの再配置はホストコマンドに応じて時々爆発的に装置活動と交互配置され得る。
【０１０６】
ＳＡＴ更新手続き
ＳＡＴデータ構造の中の要素は、表２に示されている階層的手続きを用いて更新される。
【表２】

【０１０７】
表２に記されているように、ＤＬＢＡラン更新を除けば、特定の構造のためのＳＡＴ更新は、ＳＡＴ階層においてより低い階の構造における活動によってトリガされる。ＳＡＴリストは、完全なＤＬＢＡランと関連付けられたデータが書き込みブロックに書かれるたびに更新される。許される最大の数のエントリがＳＡＴリストに存在する時に１つ以上のＳＡＴページが更新される。ＳＡＴページが更新される時、ＳＡＴリストからの１つ以上のエントリがＳＡＴページに付加され、ＳＡＴリストから除去される。ＳＡＴリストが満杯である時に更新されるＳＡＴページはページの数個の異なるグループに分けられることができて、単一の操作で単一のグループが更新されなければならないに過ぎない。これは、ＳＡＴ更新操作がホストからのデータ書き込み操作を遅延させ得る時間を最短にするのを助けることができる。この場合、ＳＡＴリストから更新されたＳＡＴページのグループにコピーされたエントリだけがＳＡＴリストから除去される。更新されたＳＡＴページのグループのサイズは、ホストシステム１のメモリシステム２にアクセスする能力を妨げないポイントにセットされ得る。１つの実施例ではグループサイズは４ＳＡＴページであり得る。
【０１０８】
ＳＡＴ索引バッファフィールドは、最も最近に書かれたＳＡＴページにおいて有効である。それは、ＳＡＴページが書かれるたびに付加的なプログラミングなしで更新される。最後に、許される最大の数のエントリがＳＡＴ索引バッファに存在する時、ＳＡＴ索引ページが更新される。ＳＡＴ索引ページ更新中に、ＳＡＴ索引バッファから１つ以上のエントリがＳＡＴ索引ページに付加されて、ＳＡＴ索引バッファから除去される。ＳＡＴページの更新に関して前に記されたように、更新されなければならないＳＡＴ索引ページをページの数個の異なるグループに分けることができ、単一の操作で単一のグループが更新されなければならないに過ぎない。これは、ＳＡＴ更新操作がホストからのデータ書き込み操作を遅延させ得る時間を最短にする。ＳＡＴ索引バッファから更新されたＳＡＴ索引ページのグループにコピーされたエントリだけがＳＡＴ索引バッファから除去される。更新されるＳＡＴ索引ページのグループのサイズは、１つの実施例では４ページであり得る。
【０１０９】
ＳＡＴページまたはＳＡＴ索引ページがまたがるＬＢＡ範囲の中で必要とされるエントリの数は可変であり、時間と共に変化し得る。従って、ＳＡＴ内のページがオーバーフローしたり、あるいはページの内容が非常に少なくなったりすることは稀なことではない。これらの事態はＳＡＴにおいてページを分割し、また合併するための方式によって処理され得る。
【０１１０】
ＳＡＴページまたはＳＡＴ索引ページの更新中にエントリが付加されるべきであるけれども、その変更を受け入れるために充分な未使用スペースがページにおいて利用できない時には、そのページは２つに分割される。１つの新しいＳＡＴページまたはＳＡＴ索引ページが導入され、以前に満杯になっていたページと新しい空のページとのために、それらを半ば満たすいくつかのエントリを各々に与えるＬＢＡ範囲が決定される。次に両方のページが、可能ならば、単一のプログラミング操作で、書かれる。ページがＳＡＴページである場合、両方のページのためのＳＡＴ索引エントリは、最後に書かれたＳＡＴページの索引バッファフィールドに含まれる。ページがＳＡＴ索引ページである場合、ページ索引エントリは、最後に書かれたＳＡＴ索引ページのページ索引フィールドに含まれる。
【０１１１】
隣接するＬＢＡ範囲を有する２つ以上のＳＡＴページ、または２つのＳＡＴ索引ページの内容が少ない時、それらのページは合併されて単一のページになることができる。合併は、その結果として生じる単一のページが８０％より大きくは満たされない時に、開始される。新しい単一のページのためのＬＢＡ範囲は、別々の合併されるページがまたがる範囲によって定められる。合併されるページ同士がＳＡＴページである場合、新しいページと合併されるページ同士とのためのＳＡＴ索引エントリは、最後に書かれるＳＡＴページの索引バッファフィールドにおいて更新される。ページ同士がＳＡＴ索引ページである場合、ページ索引エントリは、最後に書かれるＳＡＴ索引ページのページ索引フィールドにおいて更新される。
【０１１２】
パワーサイクル後、すなわちパワーが除去され回復された後に、ＲＡＭ内のＳＡＴリストを、それがパワーサイクルの前にそうであったところの状態と正確に同じ状態に復元することが必要である。これは、最後のＳＡＴページ更新以来書かれている付加的なデータを、データヘッダ内のＬＢＡアドレス情報から識別するために全ての書き込みブロックおよび再配置ブロックをスキャンすることによって成し遂げられ得る。最後のＳＡＴページ更新の時のこれらのブロックの位置と、それらの中での書き込みポインタおよび再配置ポインタの位置も、最後に書かれたＳＡＴページの１つのフィールドに記録される。従って、スキャンニングは、これらのポインタの位置から開始されるだけでよい。
【０１１３】
ＳＡＴブロックをフラッシングすること
ＳＡＴブロックをフラッシングするプロセスは、ホストから受け取られたデータについて前に記載されたプロセスと類似するけれども、ＳＡＴブロックだけに作用する。ストレージアドレス再マッピング書き込みおよびフラッシングアルゴリズムによりもたらされるＳＡＴに対する更新は、ＳＡＴブロックを図２６に示されているブロック状態の間で遷移させる。先ず、白色ブロックリストからの白色ブロックがＳＡＴ書き込みブロックとして割当てられる（３１０において）。ＳＡＴ書き込みブロックの最後のページが割当てられた時、ブロックは赤色ＳＡＴブロックになる（３１２において）。その中のいくつかのページが既に陳腐化していればＳＡＴ書き込みブロックがピンク色ＳＡＴブロックへの遷移を行なうということもあり得る。しかし、明瞭性を目的として、その遷移は図２６には示されていない。ＳＡＴページまたはＳＡＴ索引ページが更新される時に赤色ＳＡＴブロックの中の１つ以上のページは陳腐化され、その赤色ＳＡＴブロックはピンク色ＳＡＴブロックになる（３１４において）。選択されたピンク色ＳＡＴブロックに対するフラッシング操作が完了した時、そのピンク色ＳＡＴブロックは白色ブロックになる（３１６において）。
【０１１４】
どのＳＡＴブロックがフラッシング手続きを受けることになるかを選択するプロセスが次に記述される。少数の有効なページまたはクラスタを包含するＳＡＴブロックが、フラッシングされるべき次のＳＡＴブロックとして選択される。ブロックは、最低数の有効なページを有するＳＡＴブロックのうちの５％の中の１つであるべきである。ブロックの選択は、最低の有効ページ総数値を有する１６個のＳＡＴブロックのリストを構築するバックグラウンドプロセスにより成し遂げられ得る。このプロセスは、好ましくは、Ｍ個の予定されたＳＡＴブロックフラッシング操作により費やされる時間のうちに１サイクルを完了するべきである。
【０１１５】
どのＳＡＴブロックを次にフラッシングするかを決定するためのバックグラウンドプロセスの１サイクルのうちに行われる活動の一例が図２７に示されている。先ず、前のプロセスサイクル中に特定されたブロックの集合の後で、次の、Ｎ個のＳＡＴブロックの集合を特定するためにブロック情報テーブル（ＢＩＴ）がスキャンされる（ステップ３１８において）。ＳＡＴブロックの最初の集合は、装置初期化後の第１のプロセスサイクルの間に特定されるべきである。Ｎの値は、そのアプリケーションのために適宜選択されることができて、好ましくは、ＳＡＴフラッシングブロックの利用可能性を保証するためにＭのために選択される値より大きい。一例として、Ｍは４でＮは８であり得る。集合中の各々のＳＡＴブロックのために有効ページ総数値はゼロにセットされる（ステップ３２０において）。次に、集合中の任意のＳＡＴブロックに置かれている有効なＳＡＴ索引ページを識別するために、キャッシュされているページ索引フィールドにおいてページ索引エントリがスキャンされる（ステップ３２２において)。それに応じて有効ページ総数値がインクリメントされる。集合中の任意のＳＡＴブロックに置かれている有効なＳＡＴページを識別するために、各ＳＡＴ索引ページにおいてＳＡＴ索引エントリが順番にスキャンされる（ステップ３２４において）。それに応じて有効ページ総数値がインクリメントされる（ステップ３２６において）。有効ページ総数値を判定するためにページ索引およびＳＡＴ索引ページがスキャンされた後、集合中のＳＡＴブロックの各々についての有効ページ総数値は、低い有効ページ総数値のためのリストの中のＳＡＴブロックについてのものと対比されて評価され、リスト中のブロックは、必要ならば、集合からのブロックと取り替えられる（ステップ３２８において）。ＳＡＴブロックフラッシング操作が予定されるべき時、リスト中の最低有効ページ総数値を有するブロックが選択される。
【０１１６】
ＳＡＴブロックフラッシング操作では、全ての有効なＳＡＴ索引ページおよびＳＡＴページが、選択されたブロックからＳＡＴ書き込みポインタ２４２に再配置される。ページ索引フィールドは、最後に書かれたＳＡＴ索引ページにおいてのみ更新される。ＳＡＴブロックの数がほぼ一定に保たれるために、ＳＡＴページおよびＳＡＴ索引ページに対する更新操作によって消費されるＳＡＴ内のページの数は、ＳＡＴブロックフラッシング操作によって回復される陳腐化したＳＡＴページおよびＳＡＴ索引ページの数と釣り合わされなければならない。次のＳＡＴフラッシング操作のために選択されるＳＡＴブロック内の陳腐化した情報のページの数は、前に図２７に関連して論じられたように決定される。次のＳＡＴブロックフラッシング操作は、前のＳＡＴフラッシング操作以来、情報の同数の有効なページがＳＡＴに書き込まれた時に行われるように予定され得る。
【０１１７】
ブロック情報テーブル（ＢＩＴ）
ブロック情報テーブル（ＢＩＴ）は、白色ブロック、ピンク色ブロック、およびＳＡＴブロックのためにブロックアドレスの別々のリストを記録するために使用される。ＢＩＴ書き込みブロックは、他の全てのＢＩＴブロックが置かれている場所に関する情報を包含する。１つの実施例では、書き込みブロック、再配置ブロックまたはＳＡＴブロックとして割当てられるべきブロックの選択を可能にするために白色ブロックのリストをストレージアドレス再マッピングアルゴリズムおよび関連するシステムが維持することが望ましい。ブロックフラッシング操作の対象となるべきピンク色ブロックおよびＳＡＴブロックの選択を可能にするために、ピンク色ブロックのリストを維持することも望ましい。これらのリストは、その構造がＳＡＴのものを厳密に反映するＢＩＴにおいて維持される。
【０１１８】
ＢＩＴデータ構造
ＢＩＴは、ＢＩＴブロックとして知られているＤＬＢＡアドレスのブロックの中で実現される。ブロックリスト情報はＢＩＴページの中に格納され、「ＤＬＢＡブロック対ＢＩＴページ」索引付け情報はＢＩＴ索引ページの中に格納される。ＢＩＴページおよびＢＩＴ索引ページは、同じＢＩＴブロックの中で任意の順序で混合され得る。ＢＩＴは複数のＢＩＴブロックからなり得るけれども、ＢＩＴ情報は、ＢＩＴ書き込みブロックとして現在指定されている単一のブロックにだけ書き込まれ得るに過ぎない。他の全てのＢＩＴブロックは、先にすっかり書き込まれていて、有効なページおよび陳腐化したページの組み合わせを包含し得る。陳腐化したＢＩＴ情報のページを削除して再利用のための白色ブロックを作るために、前述したＳＡＴブロックのためのものと同一のＢＩＴブロックフラッシング方式が実行される。
【０１１９】
ＢＩＴブロック
図２８に示されているＢＩＴブロックは、ＢＩＴ情報の格納に専用されるＤＬＢＡアドレスのブロックである。それは、ＢＩＴページ３４２およびＢＩＴ索引ページ３４４を包含し得る。ＢＩＴブロックは、有効なＢＩＴページ、有効なＢＩＴ索引ページ、および陳腐化したページの任意の組み合わせを包含し得る。ＢＩＴ情報は、ＢＩＴ書き込みブロック３４０として指定されている単一のＢＩＴブロックに書き込まれ得るにすぎない。ＢＩＴ情報は、ＢＩＴ書き込みブロック３４０において、インクリメンタルなＢＩＴ書き込みポインタ３４６によって定められる連続する位置に書き込まれる。ＢＩＴ書き込みブロック３４０がすっかり書かれた時、１つの白色ブロックが新しいＢＩＴ書き込みブロックとして割当てられる。ＢＩＴを構成するブロックは、それぞれそのＢＩＴブロック位置により識別されるが、それは、それらの、装置におけるブロックの集団の中でのブロックアドレスである。ＢＩＴブロックはテーブルページに分割され、それらの中にＢＩＴページ３４２またはＢＩＴ索引ページ３４４が書き込まれ得る。ＢＩＴページ位置は、そのＢＩＴブロックの中でのそのシーケンス番号によってアドレス指定される。ＢＩＴ情報を、非ＢＩＴ情報からフラッシュメモリの異なるブロックに隔離することができ、非ＢＩＴ情報とは異なるタイプのブロック（例えば、バイナリ対ＭＬＣ）に隔離することができ、あるいは１つのブロックの中で非ＢＩＴ情報と混合することができる。
【０１２０】
ＢＩＴページ３４２は、ＢＩＴにおけるブロックリスト情報の最小更新可能単位である。更新されたＢＩＴページは、ＢＩＴ書き込みポインタ３４６により定められる位置に書き込まれる。ＢＩＴページ３４２は、１つの定められた範囲の中のＤＬＢＡブロックアドレスを有する白色ブロック、ピンク色ブロックおよびＳＡＴブロックのリストを包含するけれども、どのリスト内の引き続くブロックのブロックアドレスも連続している必要はない。ＢＩＴページ内のＤＬＢＡブロックアドレスの範囲は、他のどのＢＩＴページ内のＤＬＢＡブロックアドレスの範囲とも重なり合わない。ＢＩＴページは、ＢＩＴブロックの集合全体にわたって無制限に分散させられ得る。ＤＬＢＡアドレスの任意の範囲のためのＢＩＴページが任意のＢＩＴブロックに存在し得る。ＢＩＴページは、白色ブロックリスト（ＷＢＬ）フィールド３４８、ピンク色ブロックリスト（ＰＢＬ）フィールド３５０、ＳＡＴブロックリスト（ＳＢＬ）フィールド３５２および索引バッファフィールド３５４に加えて、２つの制御ポインタ３５６を含む。パラメータバックアップエントリも、揮発性ＲＡＭに格納されているいくつかのパラメータの値を包含する。
【０１２１】
ＢＩＴページ３４２の中のＷＢＬフィールド３４８は、ＢＩＴページ３４２に関連するＤＬＢＡブロックアドレスの範囲の中で、白色ブロックリスト内のブロックのためのエントリを包含する。ＢＩＴページ３４２がまたがるＤＬＢＡブロックアドレスの範囲は、他のどのＢＩＴページ３４２がまたがるＤＬＢＡブロックアドレスの範囲とも重なり合わない。ＷＢＬフィールド３４８は、可変長のフィールドであって、可変数のＷＢＬエントリを包含する。ＷＢＬフィールドの中で、ＢＩＴページ３４２により索引付けられるＤＬＢＡブロックアドレスの範囲の中のどの白色ブロックについても１つのＷＢＬエントリが存在する。ＷＢＬエントリは、そのブロックのＤＬＢＡアドレスを包含する。
【０１２２】
ＢＩＴページ３４２の中のＰＢＬフィールド３５０は、ＢＩＴページ３４２に関連するＤＬＢＡブロックアドレスの範囲の中で、ピンク色ブロックリスト内のブロックのためのエントリを包含する。ＢＩＴページ３４２がまたがるＤＬＢＡブロックアドレスの範囲は、他のどのＢＩＴページ３４２がまたがるＤＬＢＡブロックアドレスの範囲とも重なり合わない。ＰＢＬフィールド３５０は、可変長のフィールドであって、可変数のＰＢＬエントリを包含する。ＰＢＬフィールド３５０の中で、ＢＩＴページ３４２により索引付けられるＤＬＢＡブロックアドレスの範囲の中のどのピンク色ブロックについても１つのＰＢＬエントリが存在する。ＰＢＬエントリは、そのブロックのＤＬＢＡアドレスを包含する。
【０１２３】
ＢＩＴページの中のＳＢＬ３５２フィールドは、ＢＩＴページ３４２に関連するＤＬＢＡブロックアドレスの範囲の中で、ＳＡＴブロックリスト内のブロックのためのエントリを包含する。ＢＩＴページ３４２がまたがるＤＬＢＡブロックアドレスの範囲は、他のどのＢＩＴページ３４２がまたがるＤＬＢＡブロックアドレスの範囲とも重なり合わない。ＳＢＬフィールド３５２は、可変長のフィールドであって、可変数のＳＢＬエントリを包含する。ＳＢＬフィールド３５２の中で、ＢＩＴページ３５２により索引付けられるＤＬＢＡブロックアドレスの範囲の中のどのＳＡＴブロックについても１つのＳＢＬエントリが存在する。ＳＢＬエントリは、そのブロックのＤＬＢＡアドレスを包含する。
【０１２４】
索引バッファフィールド３５４は、どのＢＩＴページ３４２についてもその一部分として書かれるが、最も最近に書かれたＢＩＴページにおいてのみ有効なままである。ＢＩＴページ３４２の索引バッファフィールド３５４はＢＩＴ索引エントリを包含する。関連するＢＩＴ索引ページ３４４において有効なエントリを現在有しないＢＩＴ内のどのＢＩＴページ３４２についても１つのＢＩＴ索引エントリが存在する。ＢＩＴ索引エントリは、ＢＩＴページ３４２が書かれるたびに作成または更新され、関連するＢＩＴ索引ページ３４４が更新される時に削除される。ＢＩＴ索引エントリは、ＢＩＴページ３４２により索引付けられる範囲の第１のＤＬＢＡブロックアドレスと、ＢＩＴページ３４２により索引付けられる範囲の最後のＤＬＢＡブロックアドレスと、ＢＩＴページ３４２を包含するＢＩＴブロック位置と、ＢＩＴブロック内のＢＩＴページのＢＩＴページ位置とを包含し得る。索引バッファフィールド３５４は、暫定的に３２と定められる、固定された数のＢＩＴ索引エントリのための容量を有する。この数は、ＢＩＴページ３４２およびＢＩＴ索引ページ３４４が書かれ得る相対頻度を決定する。
【０１２５】
ＢＩＴページ３４２の制御ポインタ３５６は、ＷＢＬフィールド３４８の先頭からの、ＰＢＬフィールド３５０の先頭およびＳＢＬフィールド３５２の先頭のオフセットを定める。ＢＩＴページ３４２は、リストエントリの数としてのオフセット値を包含する。
【０１２６】
ＢＩＴ索引ページ
ＢＩＴ索引ページ３４４の集合は、ＢＩＴ内のどの有効なＢＩＴページ３４２の位置にも１つの索引を提供する。個々のＢＩＴ索引ページ３４４は、ＤＬＢＡブロックアドレスの１つの範囲に関連する有効なＢＩＴページの位置を定めるエントリを包含する。ＢＩＴ索引ページがまたがるＤＬＢＡブロックアドレスの範囲は、他のどのＢＩＴ索引ページ３４４がまたがるＤＬＢＡブロックアドレスの範囲とも重なり合わない。エントリは、それらが関連するＢＩＴページ３４２のＤＬＢＡブロックアドレス範囲値に従って順序付けされる。ＢＩＴ索引ページ３４４は、固定された数のエントリを包含する。
【０１２７】
ＢＩＴ索引ページは、ＢＩＴブロックの集合全体にわたって無制限に分散させられ得る。ＤＬＢＡブロックアドレスの任意の範囲のためのＢＩＴ索引ページ３４４が任意のＢＩＴブロックに存在し得る。ＢＩＴ索引ページ３４４は、ＢＩＴ索引フィールド３５８およびページ索引フィールド３６０を含む。ＢＩＴ索引フィールド３５８は、ＢＩＴ索引ページ３４４がまたがるＤＬＢＡブロックアドレス範囲の中の全ての有効なＢＩＴページのためのＢＩＴ索引エントリを包含する。ＢＩＴ索引エントリは、単一のＢＩＴページ３４２に関連し、ＢＩＴページにより索引付けられる第１のＤＬＢＡブロックと、ＢＩＴページを包含するＢＩＴブロック位置と、ＢＩＴブロック内のＢＩＴページのＢＩＴページ位置とを包含し得る。
【０１２８】
ＢＩＴ索引ページ３４４のページ索引フィールド３６０は、ＢＩＴ内の全ての有効なＢＩＴ索引ページのためのページ索引エントリを包含する。１つのＢＩＴページ索引エントリが、ＢＩＴ内のどの有効なＢＩＴ索引ページ３４４のためにも存在し、ＢＩＴ索引ページにより索引付けられる第１のＤＬＢＡブロックと、ＢＩＴ索引ページを包含するＢＩＴブロック位置と、ＢＩＴブロック内のＢＩＴ索引ページのＢＩＴページ位置とを包含し得る。
【０１２９】
ＢＩＴを維持すること
ＢＩＴページ３４２は、ＷＢＬ３４８、ＰＢＬ３５０およびＳＢＬ３５２にエントリを付加するかまたは削除するために更新される。数個のエントリに対する更新をＲＡＭ内のリストに蓄積することができ、そして、リストが１つのパワーサイクル後にＲＡＭに書き戻され得るとすれば、ＢＩＴにおいて単一の操作で実行することができる。ＢＩＴ索引バッファフィールドは、最も最近に書かれたＢＩＴページにおいて有効である。それは、ＢＩＴページが書かれるたびに付加的なプログラミングなしで更新される。ＢＩＴ索引ページが更新される時、ＢＩＴ索引バッファからの１つ以上のエントリがＢＩＴ索引ページに付加され、ＢＩＴ索引バッファから削除される。許容される最大の数のエントリがＢＩＴ索引バッファに存在する時に１つ以上のＢＩＴ索引ページ３４４が更新される。
【０１３０】
ＢＩＴページ３４２またはＢＩＴ索引ページ３４４がまたがるＤＬＢＡブロック範囲の中で必要とされるエントリの数は可変であって、時間と共に変化し得る。従って、ＢＩＴ内のページがオーバーフローしたり、あるいはページの内容が非常に少なくなったりすることは稀なことではない。これらの事態はＢＩＴにおいてページを分割し、また合併するための方式によって処理され得る。
【０１３１】
ＢＩＴページ３４２またはＢＩＴ索引ページ３４４の更新中にエントリが付加されるべきであるけれども、その変更を受け入れるために充分な未使用スペースがページにおいて利用できない時には、そのページは２つに分割される。１つの新しいＢＩＴページ３４２またはＢＩＴ索引ページ３４４が導入され、以前に満杯になっていたページと新しい空のページとのために、それらを半ば満たすいくつかのエントリを各々に与えるＤＬＢＡブロック範囲が決定される。次に両方のページが、可能ならば、単一のプログラミング操作で、書かれる。ページがＢＩＴページ３４２である場合、両方のページのためのＢＩＴ索引エントリが、最後に書かれるＢＩＴページの索引バッファフィールドに含まれる。ページがＢＩＴ索引ページ３４４である場合、ページ索引エントリが、最後に書かれるＢＩＴ索引ページのページ索引フィールドに含まれる。
【０１３２】
逆に、隣接するＤＬＢＡブロック範囲を有する２つ以上のＢＩＴページ３４２、または２つのＢＩＴ索引ページ３４４の内容が少ない時には、それらのページは合併されて単一のページになることができる。合併は、その結果として生じる単一のページが８０％より大きくは満たされない時に開始される。新しい単一のページのためのＤＬＢＡブロック範囲は、別々の合併されるページがまたがる範囲によって定められる。合併されるページがＢＩＴページである場合、新しいページと合併されるページ同士とのためのＢＩＴ索引エントリは、最後に書かれるＢＩＴページの索引バッファフィールドにおいて更新される。ページがＢＩＴ索引ページである場合、ページ索引エントリは、最後に書かれるＢＩＴ索引ページのページ索引フィールドにおいて更新される。
【０１３３】
ＢＩＴブロックをフラッシングすること
ＢＩＴブロックをフラッシングするプロセスは、ＳＡＴブロックについて前に記載されたものを厳密にたどるので、ここでは反復しない。
【０１３４】
制御ブロック
他の実施形態では、ＢＩＴおよびＳＡＴ情報は、同じブロックの異なるページに格納され得る。制御ブロックと称されるこのブロックは、１ページのＳＡＴまたはＢＩＴ情報が制御ブロックにおいて１ページを占めるように構造化され得る。制御ブロックは整数個のページを有するページ単位からなることができ、各ページ単位は、制御ブロックの中でのそのシーケンス番号によってアドレス指定される。ページ単位は、物理メモリにおいて１ページの最小サイズと１メタページの最大サイズとを有することができる。制御ブロックは、有効なＳＡＴページ、ＳＡＴ索引ページ、ＢＩＴページ、ＢＩＴ索引ページ、および陳腐化したページの任意の組み合わせを包含し得る。従って、別々のＳＡＴブロックおよびＢＩＴブロックを有するよりはむしろ、ＳＡＴおよびＢＩＴ情報の両方が同じ１つまたは複数のブロックに格納され得る。前述した別々のＳＡＴ書き込みブロックおよびＢＩＴ書き込みブロックと同様に、制御情報（ＳＡＴまたはＢＩＴ情報）は単一の制御書き込みブロックに書き込まれ得るに過ぎず、制御書き込みポインタは制御データを受け入れるための次の順次位置を特定し、１つの制御書き込みブロックがすっかり書かれた時には１つの書き込みブロックが新しい制御書き込みブロックとして割当てられる。さらに、制御ブロックは、各々、メモリシステム２においてバイナリブロックの集団の中でそのブロックアドレスにより識別され得る。制御ブロックは、前述した分離されているＳＡＴブロックおよびＢＩＴブロックに関して前に記載されたのと同様な仕方で新しい未記入容量を生成するためにフラッシングされることができるが、違いは、１つの制御ブロックのための１つの再配置ブロックが有効なＳＡＴ情報またはＢＩＴ情報に関連するページを受け入れ得るということである。フラッシングされるべき適切なピンク色制御ブロックの選択およびタイミングは、ＳＡＴフラッシングプロセスについて前に記載されたのと同じ仕方で実行され得る。
【０１３５】
ＬＢＡ割当てステータスを監視すること
ストレージアドレス再マッピングアルゴリズムは、ホストにより有効なデータに現在割当てられているホストＬＢＡアドレスだけのためにアドレスマッピング情報を記録する。従って、このマッピング情報を正確に維持するために、クラスタがホストによってデータ記憶から割当て解除される時を決定することが必要である。
【０１３６】
一実施形態では、ホストファイルシステムからのコマンドは、割当て解除されたクラスタに関する情報をストレージアドレス再マッピングアルゴリズムに提供することができる。例えば、マイクロソフト コーポレイションのビスタオペレーティングシステムで使用されるべく「Ｄａｔａｓｅｔ（データセット）」コマンドが提案されている。「ＡＴＡ８−ＡＣＳ２のための被削除データ提案の通知 (Notification of Deleted Data Proposal for ATA8-ACS2)」のための提案がマイクロソフトによりＴ１３に提示されている。この新しいコマンドは、被削除データの通知を提供するように意図されている。単一のコマンドが、２ＧＢまでの陳腐化したデータに相当する、連続するＬＢＡアドレスに存するデータの削除を装置に通知することができる。
【０１３７】
ＮＴＦＳメタデータを解釈すること
トリムコマンドなどのホストファイルシステムコマンドを利用することができなければ、ＬＢＡ割当てステータスを、ＮＴＦＳにより書かれる＄ｂｉｔｍａｐシステムファイルにおける情報変更を追跡することによって監視することができ、ボリューム上の全てのクラスタの割当てステータスのビットマップを包含する。パーソナルコンピュータ（ＰＣ）において＄ｂｉｔｍａｐ変更を追跡する動作の一例が次に論じられる。
【０１３８】
パーティションブートセクタ
パーティションブートセクタは、パーティション上のセクタ０である。バイトオフセット０ｘ３０におけるフィールドは、表３の例のように、マスターファイルテーブル（ＭＦＴ）の先頭のための論理クラスタ番号を包含する。
【表３】

【０１３９】
ＭＦＴにおける＄ｂｉｔｍａｐレコード
＄ｂｉｔｍａｐと称されるシステムファイルは、ボリューム上の全クラスタの割当てステータスのビットマップを包含する。＄ｂｉｔｍａｐファイルのためのレコードは、ＭＦＴにおいてレコード番号６である。ＭＦＴレコードは１，０２４バイトの長さを有する。従って、＄ｂｉｔｍａｐレコードは、ＭＦＴの先頭に関して十進１２セクタのオフセットを有する。前の例では、ＭＦＴはクラスタ０ｘＣ４ＦＤ２、あるいは十進法で８０６８６６から始まるが、それは十進法でセクタ６４５４９２８である。従って、＄ｂｉｔｍａｐファイルレコードは十進法でセクタ６４５４９４０から始まる。
【０１４０】
（記載されている例では）＄ｂｉｔｍａｐレコードの中には次の情報が存在する。バイトオフセット０ｘ１４１から０ｘ１４２までのところのフィールドは、表４の例のように、＄ｂｉｔｍａｐファイルのための第１のデータ属性の、クラスタ数で表される長さを包含する。
【表４】

【０１４１】
バイトオフセット０ｘ１４３から０ｘ１４５までのところのフィールドは、表５の例のように、＄ｂｉｔｍａｐファイルについての第１のデータ属性の先頭のクラスタ番号を包含する。
【表５】

【０１４２】
バイトオフセット０ｘ１４７から０ｘ１４８までのところのフィールドは、表６の例のように、＄ｂｉｔｍａｐファイルについての第２のデータ属性の、クラスタ数で表された長さを包含する。
【表６】

【０１４３】
バイトオフセット０ｘ１４９から０ｘ１４Ｂまでのところのフィールドは、表７の例のように、＄ｂｉｔｍａｐファイルについての第１のデータ属性の先頭と第２のデータ属性の先頭との間のクラスタの数を包含する。
【表７】

【０１４４】
＄ｂｉｔｍａｐファイルのためのデータ属性
＄ｂｉｔｍａｐフィルのためのデータ属性の中のセクタは、ボリューム内の全てのクラスタの割当てステータスのビットマップを、論理クラスタ番号の順に、包含する。「１」は、フィルシステムによって１つのクラスタがデータ記憶に割当てられていることを意味し、「０」は、１つのクラスタが空いていることを意味した。ビットマップ内の各バイトは、８クラスタ、あるいは十進６４セクタの論理範囲に関連する。ビットマップ内の各セクタは、０ｘ１０００（十進４０９６）クラスタ、あるいは０ｘ８０００（十進３２７６８）セクタの論理範囲に関連する。ビットマップ内の各クラスタは０ｘ８０００（十進３２７６８）クラスタ、あるいは０ｘ４００００（十進２６２１４４）セクタの論理範囲に関連する。
【０１４５】
クラスタ割当てステータスを維持すること
ホストからの書き込み操作が＄ｂｉｔｍａｐファイルのためのデータ属性の中のセクタに向けられるたびに、そのセクタの前のバージョンが記憶装置から読み出されなければならず、そのデータが、ホストによって今書かれたばかりのデータと比較されなければならない。「１」状態から「０」状態にトグルしている全てのビットが識別されなければならず、ホストによって割当て解除されているクラスタの対応する論理アドレスが決定されなければならない。提案されているトリムコマンドなどのコマンドが、あるいはＮＴＦＳメタデータの追跡が、ホストによるクラスタ割当て解除があったことを示すたびに、ストレージアドレステーブル（ＳＡＴ）は、指定されたクラスタのためのアドレスの割当て解除を記録するために更新されなければならない。
【０１４６】
論理対物理マッピング
前の議論は、ホストＬＢＡアドレス空間からＤＬＢＡアドレス空間（ストレージＬＢＡ空間とも称される）への、論理対論理マッピングが望ましいストレージアドレス再マッピングの実行に主として焦点を当てている。前に記されたように、マッピングアルゴリズムが図９〜１０のようにそれぞれ記憶装置またはホストの上の別のアプリケーションに組み込まれるよりはむしろ記憶装置のメモリマネージャに組み込まれている図８の実施形態は、ホストＬＢＡからメモリシステム２内の物理アドレスにマッピングする。図８の実施形態では、前に論じられたＤＬＢＡは、中間の論理アドレスであるよりはむしろ置き換えられた物理的メモリアドレスである。図８のアレンジメントにおけるストレージ再マッピングアルゴリズムは、メモリシステム２またはホスト１（それぞれ、図９および１０）上の別のアプリケーションであるよりはむしろメモリシステム２内のメモリコントローラ８の一部である。
【０１４７】
図８の論理対物理マッピングアレンジメントと図９〜１０の論理対論理マッピングアレンジメントとの違いは、図２９〜３２と関連して記され得る。図２９は、論理対物理ストレージアドレス再マッピングアルゴリズムが物理メモリ内の利用可能な白色ブロックのうちの、書き込みブロック４１２になるべき１つをどのように割当てるかを示すとともに、ＬＢＡアドレス空間４０８内の各ＬＢＡアドレスが、書き込みブロック４１２において利用可能な物理アドレス空間４１０内の順次位置にどのようにマッピングされるかを示す。物理アドレス空間４１０内の書き込みブロック４１２は、ＬＢＡアドレス位置に関わらず、ＬＢＡアドレスが受け取られる順に書かれる。この例では、図１５の並列論理対論理マッピングの例の場合と同様に、説明を容易にするために、ホストが空きＬＢＡクラスタを使用した時間順はアドレス順と同じであるということが仮定されるけれども、ストレージアドレス再マッピングアルゴリズムは、書き込みブロック４１２内の物理アドレスを、ＬＢＡアドレス番号順に関わらず、ＬＢＡアドレスが使用される時間順に、割当てる。データは、書き込みブロックにおいて１つ以上のデータランに書き込まれる。データランは、同じＬＢＡラン内の連続するＬＢＡアドレスにマッピングされた連続する物理アドレスの集合である。データランは、物理アドレス空間４１０内のブロック境界で終わる。１つの書き込みブロック４１２が満杯になる時、１つの新しい白色ブロックが次の書き込みブロック４１２として割当てられる。従って、中間の論理アドレスを割当てるよりはむしろ、論理対物理アレンジメントは、入ってくるデータを、それが物理メモリに直接書かれる時に再順序付けする。
【０１４８】
図９〜１０の論理対論理マッピングアレンジメントと同様に、図８の論理対物理アレンジメントのためのストレージアドレス再マッピングアルゴリズムは、シーケンシャルな書き込みアルゴリズムが動作するために充分な白色ブロックの供給が利用可能であることを保証するように作用する。ストレージアドレス再マッピングアルゴリズムは、ピンク色ブロックから再配置ブロック４１６にデータをフラッシングすることによる白色ブロックの作成を管理する（図３０)。フラッシングのために現在選択されているピンク色ブロックはフラッシングブロックと称される。
【０１４９】
図２９〜３０に示されているように、ブロックフラッシングプロセスの図が示されている。ストレージアドレス再マッピングアルゴリズムは１つの白色ブロックを再配置ブロック４１６として指定し、これに、付加的な白色ブロックを作るために、選択されたピンク色ブロックからデータがフラッシングされる。データは、フラッシングブロックを白色ブロック４１８に変換するために、フラッシングブロック（図２９のピンク色ブロックＡ)内の赤色データとも称される有効なデータを包含する位置から、再配置ブロック４１６内の連続するアドレスに再配置される。図３１に示されているように、次の１つのフラッシングブロック（図３０のピンク色ブロックＢ）が、残りのピンク色ブロックから特定される。最少の有効データ（最少数の赤色データ）を有するピンク色ブロック、あるいは平均量より少ない有効データまたはある所定しきい値量未満を現在有するピンク色ブロックのリストから選択された１つのピンク色ブロックが再びフラッシングブロックとして指定され、そのピンク色ブロックの赤色データ（有効データ）は、開いている再配置ブロック４１６内の連続する物理的位置に、有効データがピンク色ブロック内に存在する順に、転送される。ピンク色ブロックに対するフラッシング操作は、書き込みブロックとして指定された白色ブロック４１８の消費を補うために充分な速度で白色ブロック４１８を作るためにバックグラウンド操作として実行される。図２９〜３１の例は、ホストからの新しいデータのため、またピンク色ブロックから再配置されるデータのために、書き込みブロックおよび再配置ブロックがどのようにして別々に維持され得るかを示す。他の実施例では、別々の書き込みブロックおよび再配置ブロックを必要とせずに、新しいデータと再配置されるデータとは単一の書き込みブロックに転送され得る。
【０１５０】
論理対物理再マッピングのためのＳＡＴ
ＳＡＴは、図８の論理対物理アレンジメントのためにも使用される。ＳＡＴは、ここでは、論理対論理ストレージアドレス再マッピングアレンジメントと同じ基本構造を有し、ＤＬＢＡ（ストレージＬＢＡとも称される）アドレス情報はデータランの物理アドレスにより取って代わられる。論理対物理アレンジメントのためのＳＡＴ索引付けおよびマッピング構造の階層が図３２に示されている。ＬＢＡ４３２および対応するデータラン４３０が示されている。ＬＢＡ対物理マッピング情報はＳＡＴページ４３４に包含されている。ＬＢＡ対ＳＡＴページ索引付け情報はＳＡＴ索引ページ４３６に包含され、マスターページ索引４３８は、コントローラ８と関連付けられたＲＡＭにキャッシュされる。ＳＡＴは、複数のＳＡＴブロックを含むことができ、あるいはＳＡＴ書き込みブロックと現在称されている単一のブロックに書き込まれるだけであることができる。他の全てのＳＡＴブロックはすっかり書き込まれ、有効なページと陳腐化したページとの組み合わせを包含し得る。陳腐化したＳＡＴ情報のページを削除して再使用のための白色ブロックを作るために、ホストデータのブロックのためのものと同様の、ＳＡＴブロックフラッシング方式が実行される。
【０１５１】
前に記載された論理対論理ＳＡＴマッピングと同様に、図の論理対物理アレンジメントにおけるＳＡＴは、ＳＡＴのエントリの数がホストにより割当てられたＬＢＡの断片化に順応するので、最大数まで自動的にスケーラブルである可変サイズのテーブルである。従って、ホストが高度に断片化されたＬＢＡを割当てれば、ＳＡＴは、より少なく断片化されたＬＢＡのグループをデータに割当てる場合よりも多くのエントリを含む。従って、ホストＬＢＡの断片化の程度がより低くなれば、ＳＡＴのサイズは小さくなる。断片化の程度が低くなればマッピングするべき別々のランは少なくなり、別々のランが少なくなればＳＡＴのエントリが少なくなる。なぜならば、ＳＡＴは、一定数論理アドレスを厳格に追跡し更新するよりはむしろ、１つのエントリにおいてホストＬＢＡアドレスの１つのランを１つ以上のデータラン（物理アドレスラン）にマッピングするからである。ホストＬＢＡアドレスの１つのランを２つ以上のデータランにマッピングすることができ、ここでホストＬＢＡランは有効なデータに割当てられた連続する論理アドレスの１つの集合であり、データ（または物理アドレス）ランは同じメタブロックの中にあって同じホストＬＢＡランにマッピングされた物理アドレスの１つの連続的な集合である。
【０１５２】
ＳＡＴブロック
各ＳＡＴブロックは、ＳＡＴ情報の格納に専用される物理アドレスの１つのブロックである。ＳＡＴブロックはテーブルページに分割され、その中にＳＡＴページ４３４またはＳＡＴ索引ページ４３６が書き込まれ得る。ＳＡＴブロックは、有効なＳＡＴページ４３４、有効なＳＡＴ索引ページ４３６および陳腐化したページの任意の組み合わせを包含し得る。図３３を参照すると、ＳＡＴ書き込みブロック４４０が示されている。データは、ＳＡＴ書き込みブロック４４０において、インクリメンタルなＳＡＴ書き込みポインタ４４２により定められる順次位置に書き込まれる。データは、ＳＡＴ書き込みブロック４４０として指定されている単一のＳＡＴブロックに書き込まれ得るにすぎない。データは、インクリメンタルなＳＡＴ書き込みポインタ４４２により定められる順次位置としてＳＡＴ書き込みブロック４４０に書き込まれる。前に記載されたホストデータ書き込みブロックの場合と同様に（例えば、図１５〜１７のアイテム２１２）、ＳＡＴ書き込みブロック４４０がすっかり書き込まれると、１つの白色ブロックが新しいＳＡＴ書き込みブロック４４０として割当てられる。ＳＡＴページ位置は、そのＳＡＴブロックの中でのそのシーケンシャルな番号によってアドレス指定される。ＳＡＴブロックを非ＳＡＴ情報のブロックと混ぜ合わせることができ、あるいは、ＳＡＴブロックをバイナリフラッシュブロックなどの１つの特別のタイプのブロックにおいてさらに分離することができる一方で、非ＳＡＴ情報はＭＬＣフラッシュブロックに格納される。他の実施形態では、ＳＡＴ情報を同じブロック内で非ＳＡＴ情報と混ぜることができる。
【０１５３】
ＳＡＴページ
ＳＡＴページ４３４は、ＳＡＴにおけるマッピング情報の最小の更新可能な単位である。更新されたＳＡＴページ４３４は、ＳＡＴ書き込みポインタ４４２により定められる位置に書き込まれる。ＳＡＴページ４３４は、インクリメントするＬＢＡアドレスを有するＬＢＡランの１つの集合のためのマッピング情報を包含するけれども、引き続くＬＢＡラン同士のアドレスは連続していなくてもよい。１つのＳＡＴページ４３４におけるＬＢＡアドレスの範囲は、他のどのＳＡＴページ４３４におけるＬＢＡアドレスの範囲とも重なり合わない。ＳＡＴページ４３４は、ＳＡＴブロックの完全な集合の全体にわたって無制限に分散させられ得る。ＬＢＡアドレスの任意の範囲のためのＳＡＴページ４３４が任意のＳＡＴブロックに存在し得る。ＳＡＴページ４３４は、索引バッファフィールド４４４、ＬＢＡフィールド４４６、データランフィールド４４８および制御ポインタ４５０を含むことができる。パラメータバックアップエントリも、揮発性ＲＡＭに格納されているいくつかのパラメータの値を包含する。
【０１５４】
ＳＡＴページ４３４の中のＬＢＡフィールド４４６は、ＬＢＡアドレスの１つの範囲の中の、データ格納のために割当てられている連続するＬＢＡアドレスのランのためのエントリを包含する。１つのＳＡＴページ４３４がまたがるＬＢＡアドレスの範囲は、他のどのＳＡＴページ４３４がまたがるＬＢＡエントリの範囲とも重なり合わない。ＬＢＡフィールドは、可変長のフィールドであって、可変数のＬＢＡエントリを包含する。ＬＢＡフィールド４４６の中で、ＳＡＴページ４３４により索引付けされたＬＢＡアドレスの範囲中のどのＬＢＡランのためにも１つのＬＢＡエントリ４５２が存在する。１つのＬＢＡランは１つ以上のデータランにマッピングされる。
【０１５５】
図３４〜３６に示されているように、論理対物理アレンジメントにおけるＳＡＴのためのエントリは、いくつかの態様において論理対論理アドレス再マッピングアレンジメントから異なっている。図３４を参照すると、ＬＢＡエントリ４５２は、次の情報、すなわち、それがマッピングされるデータエントリの数４５４と、ＬＢＡランがマッピングされる第１のデータランの、同じＳＡＴページ４３４内のデータフィールド４４８の中での、データエントリ番号４５８とを包含する。
【０１５６】
ＳＡＴページ４３４の中のデータフィールド４４８は、同じＳＡＴページ４３４内のＬＢＡフィールド４４６の中のＬＢＡランにマッピングされているデータアドレスの全てのランのためのエントリを含む。データフィールド４４８は、可変長のフィールドであって、可変数のデータエントリ４６０を包含する。データフィールド４４８の中で、同じＳＡＴページ４３４内のＬＢＡフィールド２４６の中のＬＢＡランにマッピングされているどのデータランのためにも１つのデータエントリ４６０が存在する。各データエントリ４６０は、図３５に示されているように、次の情報、すなわち、ラン内の第１のデータアドレス４６２と、その第１のデータアドレスがマッピングされているＬＢＡランにおけるＬＢＡオフセット４６４とを包含する。どのＳＡＴページ４３４の一部としても書き込まれるけれども、最も最近に書き込まれたＳＡＴページ４３４においてのみ有効なままであるＳＡＴページ／索引バッファフィールドは、ＳＡＴ索引エントリ４６６を包含する。
【０１５７】
関連するＳＡＴ索引ページ４３６において有効なエントリを現在有しないＳＡＴ内のどのＳＡＴページ４３４についても１つのＳＡＴ索引エントリ４６６が存在する。図３６を参照すると、ＳＡＴ索引エントリは、ＳＡＴページ４３４が書き込まれるたびに作成または更新され、関連するＳＡＴ索引ページ４３６が更新される時に削除される。それは、ＳＡＴページ４３４により索引付けされる第１のＬＢＡ４６８と、ＳＡＴページ４３４により索引付けされる最終ＬＢＡ４７０と、ＳＡＴページ４３４を包含するＳＡＴブロック番号４７２と、ＳＡＴブロックの中のＳＡＴページ４３４のページ番号４７４とを包含する。ＳＡＴ索引フィールド４７６は、固定された数のＳＡＴ索引エントリ４６６のための容量を有する。この数は、ＳＡＴページ４３４とＳＡＴ索引ページ４３６とが書き込まれ得る相対頻度を決定する。一つの実施例では、この固定された数は３２であり得る。
【０１５８】
ＳＡＴページフィールドポインタ４５０は、ＬＢＡフィールドの先頭からデータフィールドの先頭までのオフセットを定める。それは、ＬＢＡエントリの数としてのオフセット値を包含する。ＳＡＴページ４３４内のパラメータバックアップエントリは、揮発性ＲＡＭに格納されているパラメータの値を包含する。これらのパラメータ値は、パワーサイクル後、図８〜９の実施例ではコントローラ８と関連付けられたＲＡＭ内の情報の初期化中に使用される。それらは、最も最近に書き込まれたＳＡＴページ４３４においてのみ有効である。
【０１５９】
他の１つの実施形態では、有効なデータと関連付けられたＬＢＡアドレスの各ランのためにＳＡＴにおいて１つの別のＬＢＡエントリを生成する代わりに、各ＬＢＡアドレスブロックがＳＡＴ上の単一のエントリであるようにＬＢＡアドレスブロックがＳＡＴにおいてマッピングされ得る。図３７に示されているように、ＬＢＡアドレス空間内の１つの完全なＬＢＡアドレスブロック４８０がＳＡＴにおいて記録され得る。この実施例におけるＬＢＡエントリ４８２は、ＬＢＡアドレスブロック４８０がマッピングされている物理アドレス空間内のデータランの数４８４と、同じＳＡＴページ内の第１のデータランへのポインタ４８６とを記録した単一のエントリである。ＬＢＡアドレスブロックは、記憶装置に格納されているデータの断片化の程度により、最低で１データランあるいは最高でＬＢＡアドレスブロック内のクラスタの数まで、マッピングされ得る。
【０１６０】
図３７の例では、ＬＢＡアドレスブロック４８０は８個のＬＢＡランを含み、ここで４個のランは有効なデータ（ＬＢＡオフセットＬ１，Ｌ３，Ｌ４およびＬ６から始まる陰影付き部分）に割当てられ、４個のランは未割当てアドレスラン（ＬＢＡオフセット０，Ｌ２，Ｌ５およびＬ７から始まる白色部分）である。ＬＢＡアドレスブロック４８０のための対応するデータエントリ４８８は、物理的ブロックおよびアドレスオフセット（Ｐ１〜Ｐ３）により示されるデータランの物理アドレス４９０を対応するＬＢＡオフセット４９２に関連付ける。有効なデータと関連付けられたＬＢＡランだけが記録される、各ＬＢＡランについて別々の１つのＬＢＡエントリを記録する前に論じられたＳＡＴのバージョンとは違って、ＬＢＡアドレスブロック内のどのＬＢＡランも記録される。従って、有効なデータに現在割当てられていないＬＢＡアドレスブロック４８０内のＬＢＡランが、有効なデータに割当てられているＬＢＡランと同様に記録される。図３７に示されているＳＡＴページのデータエントリ部分４８８において、ＬＢＡアドレスの未割当て集合の先頭を標示するＬＢＡオフセットは、物理アドレス空間における「ＦＦＦＦＦＦＦＦ」値とペアにされる。これは、未割当てアドレスのためのリザーブ値を示すデフォルト十六進数を表す。前に記載された同じ全体としてのＳＡＴ構造および機能が、図３２に関して論じられた基本的なＳＡＴ階層と同じく、ＬＢＡアドレスブロックマッピングの実施例に当てはまるけれども、ＳＡＴページは、個々のＬＢＡラン対データラン情報よりはむしろＬＢＡアドレスブロック対データランマッピング情報を表す。また、ＳＡＴ索引ページは、この実施例ではＬＢＡアドレスブロック対ＳＡＴページマッピング情報を記憶する。
【０１６１】
ＳＡＴ索引ページ
図３４〜３６を再び参照すると、ＳＡＴ索引ページ４３６の集合は、ＳＡＴ内のどの有効なＳＡＴページ４３４の位置に対しても１つの索引を提供する。個々のＳＡＴ索引ページ４３６は、ＬＢＡアドレスの１つの範囲に関連する有効なＳＡＴページの位置を定めるエントリ４６６を包含する。ＳＡＴ索引ページ４３６がまたがるＬＢＡアドレスの範囲は、他のどのＳＡＴ索引ページ４３６がまたがるＬＢＡアドレスの範囲とも重なり合わない。エントリは、それらが関連するＳＡＴページのＬＢＡアドレス範囲値に従って順序付けされる。ＳＡＴ索引ページ４３６は、固定された数のエントリを包含する。ＳＡＴ索引ページ４３６は、ＳＡＴブロックの完全な集合の全体にわたって無制限に分散させられ得る。ＬＢＡアドレスの任意の範囲のためのＳＡＴ索引ページ４３６が任意のＳＡＴブロックに存在し得る。ＳＡＴ索引ページ４３６は、１つのＳＡＴ索引フィールドおよび１つのページ索引フィールドを含む。
【０１６２】
ＳＡＴ索引フィールド４７６は、ＳＡＴ索引ページ４３６がまたがるＬＢＡアドレス範囲の中の全ての有効なＳＡＴページのためのＳＡＴ索引エントリを包含する。ＳＡＴ索引エントリ４６６は、単一のＳＡＴページ４３４に関連し、次の情報、すなわち、ＳＡＴページ４３４により索引付けされる第１のＬＢＡ、ＳＡＴページ４３４を包含するＳＡＴブロック番号、およびＳＡＴブロック内のＳＡＴページ４３４のページ番号を包含する。ページ索引フィールドは、ＳＡＴ内の全ての有効なＳＡＴ索引ページ４３６のためのページ索引エントリを包含する。ページ索引エントリは、ＳＡＴ内のどの有効なＳＡＴ索引ページ４３６のためにも１つ存在して、次の情報、すなわち、ＳＡＴ索引ページにより索引付けされる第１のＬＢＡ、ＳＡＴ索引ページを包含するＳＡＴブロック番号、およびＳＡＴブロックの中のＳＡＴ索引ページのページ番号を包含する。
【０１６３】
一時的ＳＡＴデータ構造
論理対論理ストレージアドレス再マッピングについて記載される一時的ＳＡＴデータ構造は、テーブルページおよびアドレス変換と同様に、物理アドレスが前の検討における論理アドレス（ＤＬＢＡ）への言及に取って代わることを除いて、図８の論理対物理アレンジメントについてと同じである。例えば、図２４のＳＡＴ変換手続きと、図２５および表Ａ〜ＤのＳＡＴ作成および更新の例とは、第２の論理アドレス空間（ＤＬＢＡ）が物理アドレスまたはアドレスランと置き換えられる時に、図８の論理対物理アレンジメントにも当てはまる。同様に、図８の論理対物理アレンジメントは同じＢＩＴ構造を利用するけれども、そこではＢＩＴは論理（ＤＬＢＡ）アドレスよりはむしろ物理アドレスを参照する。
【０１６４】
ホスト論理ブロックアドレスの改変された割当て
図１１の構成はまさにホストファイルシステムの中で図８〜１０の特徴の一部を統合しているけれども、図１１のストレージアドレスマッピングアレンジメントは第１の論理アドレス空間から第２の論理アドレス空間に変換しない。その代わりに、ホストＬＢＡアドレスを割当てる最初のホストファイルシステム方法は、断片化を低減するために改変される。
【０１６５】
図１１のアドレスマッピングは、図８〜１０の構成により作られるものに類似する物理メモリにおけるデータマッピングを作る。クラスタの見地からホストＬＢＡ空間を知っているに過ぎない典型的なホストファイルシステムとは違って、この実施形態のホストファイルシステム１０はメモリシステム２における物理的ブロックのサイズに対応するブロックサイズを知っている。ホストＬＢＡアドレスは、物理メモリブロックに対応する選択されたブロックの中からデータ格納のために割当てられる。選択されたブロックの中に存在する全ての空きクラスタアドレスが順次に割当てられる。マッピングアルゴリズムは、物理メモリにおいて更新ブロックに必要とされるデータ統合の量が最少に保たれることを可能にする。データ格納のための空きクラスタの割当ては、ＬＢＡアドレス空間内でブロックで管理される。ホストファイルシステムは、ブロックを、それらに包含されている空きクラスタの数に従って格付けする。最高数の空きクラスタを有するブロックが次の割当てブロックとして選択される。
【０１６６】
図３８を参照すると、図１１のホストファイルシステム構成で実行され得るアドレスマッピングの例が示されている。図１１の構成により実行されるアドレスマッピングは、ホスト上のホストファイルシステムで行われ、好ましくはホスト１のＣＰＵ９によって実行される。図９および１０の構成の例の場合と同じく、データ格納のための空きクラスタの割当ては、メモリシステムのフラッシュメモリの物理メモリブロックとサイズに関して一致するブロックで管理される。図９〜１０の例とは違って、図１１の構成で実施されるアドレスマッピングは、ホストＬＢＡアドレス空間内の空きクラスタの割当てを管理し、ホストＬＢＡアドレス空間をストレージＬＢＡアドレス空間に再マッピングしない。代わりに、以下に記載されるように、ホストファイルシステムによって実行されるアドレスマッピングアルゴリズムは、ホストＬＢＡアドレスの次のブロックの中のアドレスを割当てる前にホストＬＢＡアドレスの一ブロックの中の利用可能なアドレスを完全に割当てるようにホストＬＢＡアドレス空間内の利用可能なアドレスを利用するために最適化される。
【０１６７】
図３８の例では、ホストＬＢＡアドレス空間４９４内のブロックは、それらに包含される空きクラスタの数に従って格付けされる。図１を参照して、ホストファイルシステム１０がＮＴＦＳファイルシステムであるとすれば、ブロックの格付けは、ホストファイルシステム１０がメモリシステム２に格納し更新するＮＴＦＳ＄ｂｉｔｍａｐファイル内の割当てマップに基づくことができる。ＮＴＦＳ＄ｂｉｔｍａｐファイルから割当てマップを取り出すと、ホストファイルシステム１０は、最高数の空き（陳腐化した）クラスタを有するブロックを次の割当てブロックとして選択する。図３８の例では、ブロック１は、最高数の陳腐化した（従って、空いている）クラスタを包含しているので、割当てブロックとして選択される。陳腐化したクラスタのホストＬＢＡアドレスはブロック１の中からデータに順次に割当てられ、ここで図３８内の矢の各々はホスト１から新しいデータへの利用可能なアドレスの割当てを示す。ブロック１内の全ての空きクラスタが割当てられた時に初めて、ブロック２が次の割当てブロックとして選択される。その後、ブロック２内の空きクラスタのためのアドレスが新しいデータに順次に割当てられる。
【０１６８】
ホストＬＢＡアドレス空間４９４内のアドレスを割当てる順序は、１つのブロック内で最低の利用可能なアドレス値から最高の利用可能なアドレス値への順序であることができ、あるいは１つのブロック内の利用可能なアドレス値の「ラップアラウンド」順であることができる。例えば、図３８のブロック１についてのアドレス値が１から１６までであると仮定すると、そのブロックの中の利用可能なアドレスはアドレス値（左から右へ）３〜５，７〜８，１１〜１３および１５〜１６である。最低から最高までのアドレスの割当ては、アドレス３から開始して各々の利用可能なアドレスを順に割当てることを含む。ラップアラウンド選択肢は、アドレス値３以外の何処かのポイントからアドレスの割当てを開始すること、その最初に選択されたアドレス値から増大する値のアドレスを割当て、その後、現在のホストＬＢＡブロック内の全てのアドレスが割当てられるまでホストＬＢＡブロック内の利用可能なアドレスを最低の利用可能なアドレスから割当て続けることを含む。従って、この例においてブロック１内のアドレス１２が最初に割当てられたならば、アドレス１３，１５〜１６，３〜５，７〜８，および１１が、残りが割当てられる順序である。
【０１６９】
メモリシステム２において（これは、標準的なＬＢＡインターフェイスを使用するいくつかの公知メモリシステムのうちのいずれであってもよい)、割当てられたクラスタアドレスに書き込まれるデータは、ブロック１に対応する物理的更新ブロック４９６に格納される。メモリシステム２は、ブロック２に対応する別の物理的更新ブロック４９８も割当てる。選択された割当てブロックに対応するオリジナルのブロックにおいてなお有効であるデータ５００は、更新ブロックに書き込まれている新しいホストデータ５０２と統合される。フラッシュメモリの物理的ブロック内のページは通例順次にプログラムされるので、この統合は、新しいホストデータが更新ブロックに書き込まれた後に起こり得るか、あるいは、より一般的には、書き込まれつつある新しいホストデータと交互配置された後に起こり得る。ホストＬＢＡブロックのためのデータの、単一のフラッシュブロック内への統合のプロセスは、メモリシステム２のコントローラ８により管理され得る。ホストファイルシステムは最高数の空きクラスタを有するブロックを割当てブロックとして選択するので、統合されるデータの量は最少であるように制御される。しかし、図８〜１０の実施形態に関して論じられたフラッシングプロセス（この場合、１ブロックからフラッシングされる有効なデータが、他のブロックからの異なるアドレス範囲と関連付けられたデータを有することのある再配置ブロックに順次に書き込まれる）とは違って、図１１の割当てプロセスは、１つのブロックのための残っている有効なデータを同じアドレス範囲のための更新済みデータと合併することによってアドレスのブロックが維持されるガーベッジコレクションという結果をもたらす。
【０１７０】
アドレスマッピング割当てアルゴリズムが図１１および３８に示されているようなホストファイルシステム１８５で実行される時、１ブロックの物理メモリにおいて統合されるデータの量は、図８〜１０の実施形態に関して記載されたストレージアドレス再マッピングによって１つの同等のブロックから再配置されるデータの量と同じであり得る。図１１の実施形態ではファイルシステムによって割当てられたホストＬＢＡアドレスの再マッピングは行われないので、この実施例ではＳＡＴは不要である。また、ホストファイルシステムについては通常の慣行であるが、ファイルデータの格納のために割当てられるアドレスは、例えばＮＴＦＳファイルシステムのための＄ＭＦＴファイルあるいはＦＡＴファイルシステムのためのファイルアロケーションテーブル（ＦＡＴ）構造などの、その目的のためのデータ構造に記録される。
【０１７１】
本願明細書で論じられたアドレスマッピングおよび再マッピングシステムおよびその方法の利点は、メモリマネージャのレベルのガーベッジコレクションの減少または除去とフラッシュメモリへの減少したストレスとをおそらく含む。中間のＤＬＢＡアドレスを使用せずに、連続するＬＢＡアドレスのブロックを図８に示されているように単一の物理的ブロックにマッピングするメモリ管理アルゴリズムが使用される時には、物理的ブロックのサイズより小さいＬＢＡアドレスのランにデータが書き込まれる時にガーベッジコレクション操作が必要とされる。そのようなガーベッジコレクションの間に、ＬＢＡブロック内のアドレスを有する全てのデータが同じ物理的ブロックの中に統合される。例えば、書き込まれるファイルの平均サイズが４０ＫＢで物理的ブロックのサイズが４ＭＢである時には、ファイルシステム割当てアルゴリズムと空きクラスタスペースの断片化とが、各ファイルが孤立しているフラグメントとして別々のブロックに書き込まれるという結果をもたらすとすれば、プログラムされるセクタの、ホストにより書き込まれるデータのセクタあたりの比は１００になる。
【０１７２】
在来の論理対物理ブロックマッピングでは、ホストデータのフラグメントが孤立して論理アドレスのブロックに書き込まれるたびにデータのボディがガーベッジコレクション操作の間に再配置されなければならない。ストレージアドレス再マッピングアルゴリズムでは、１つのブロック（論理または物理）が満杯になるまでデータが常に連続するアドレスに書き込まれるので、ガーベッジコレクションは不要である。本願明細書で開示されたストレージアドレス再マッピングにおけるフラッシング操作は、書き込みプロセスによってはトリガされなくて、データが陳腐化されたことに応答してトリガされるだけである。従って、本願明細書に記載されたストレージアドレス再マッピング機能を有するシステムではデータ再配置オーバーヘッドはより低いはずである。他の実施形態では、メモリシステムは、ＬＢＡアドレスの一定の範囲を、ホストＬＢＡアドレスの各範囲の中で前述したストレージアドレス再マッピング手法が適用され得るように、別に維持するように構成され得る。従って、ＬＢＡアドレスの各々の割当てられた範囲はそれ自身の書き込みブロックおよび再配置ブロックを有し、ホストＬＢＡアドレスの１つの特定の割当てられた範囲のための前の書き込みブロックまたは再配置ブロックが完全に書かれた時にホストＬＢＡアドレスのその特定の割当てられた範囲に１つの新しい白色ブロックが書き込みブロックまたは再配置ブロックとして割当てられる。
【０１７３】
ランダムな書き込みアプリケーションにおけるメモリシステムの性能を高めることのできるストレージアドレス再マッピングのためのシステムおよび方法が記載されたが、それらは装置のＬＢＡアドレス空間の関連し合っていない領域にデータの短いバーストを書き込む必要があることにより特徴付けられ、それはパーソナルコンピュータにおいてソリッドステートディスクアプリケーションで経験され得る。開示されたストレージアドレス再マッピングの一定の実施形態では、ホストデータは、ホストにより割当てられた第１の論理アドレスから第２の論理アドレス空間内の連続する論理アドレスのブロックにマッピングされる。アドレスの完全にプログラムされたブロックと関連付けられたデータが陳腐化される時にフラッシング手続きが開示され、最少量の有効なデータを有するかあるいはしきい値量未満の有効なデータを有するピンク色ブロックのグループから１つのピンク色ブロックを選択して、それらのブロック内の有効なデータを、それらのブロックをより多くのデータの書き込みに使用するべくそれらのブロックを解放するために再配置する。再配置されるデータは、ホストにより割当てられた論理アドレスとは無関係に、フラッシングを必要とするブロックの中でそれが存在する順に、再配置ブロックに連続的に書き込まれる。このように、ホストにより割当てられた論理アドレスラン同士をわざわざ統合しないことによってオーバーヘッドが低減され得る。ホストにより割当てられた論理アドレスと第２の論理アドレスとの間のマッピングと、フラッシングによるマッピングのその後の変化とを追跡するためにストレージアドレステーブルが使用される。ホストにより割当てられる論理アドレスが物理アドレスに直接マッピングされる実施形態では、ストレージアドレステーブルはその関係を追跡し、そして例えば特定のブロックが有効なデータおよび陳腐化したデータの両方を有するピンク色ブロックであるかそれとも未記入容量だけを有する白色ブロックであるかを追跡するためにブロック情報テーブルが維持される。
【０１７４】
ＳＡＴは、ホストファイルシステムによって有効なデータに割当てられた論理アドレス空間の中のアドレスのどのランをも、装置アドレス空間（図８のアレンジメントでは物理アドレス空間、図９〜１０のアレンジメントでは論理ストレージアドレス空間）の中のアドレスの１つ以上のランにマッピングする。ホストにより使用される連続的なアドレス空間の可変長さ単位（ＬＢＡラン）が連続的な装置アドレス空間の１つ以上の可変長さ単位にマッピングされる。ラン対ランのアドレスマッピング方式は、固定サイズ単位に基づくマッピング方式と比較して利益を提供し得る。ＳＡＴにおいて必要とされるマッピングエントリの数は、ホストにより書き込まれるデータのランにおけるクラスタの平均数に反比例する。これはＳＡＴデータ構造の数を最小にし、ホストがファイルデータを書き込み、また削除する時にこれらのデータ構造を更新するための平均時間を最小にする。
【０１７５】
従って、前述した詳細な記述は限定的ではなく例証的であると解されるように意図され、また、この発明の精神および範囲を定めるべく意図されているのが、全ての同等物を含む添付の特許請求の範囲であることを理解されるように意図されている。
【特許請求の範囲】
【請求項１】
ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法であって、
ホスト論理ブロックアドレス（ＬＢＡ）アドレスと関連付けられたデータを前記大容量記憶システムにおいて前記ホストシステムから受け取るステップと、
前記ホストＬＢＡアドレスと関連付けられたデータをアドレス指定するために、割当て時に未記入の容量だけをアドレス指定する連続するストレージＬＢＡアドレスの１つのブロックを割当てるステップと、
受け取られたデータのための前記ホストＬＢＡアドレスの各々を前記連続するストレージＬＢＡアドレスのブロックに再マッピングするステップであって、各ストレージＬＢＡアドレスが、前記受け取られたデータが受け取られた順に、前記ホストＬＢＡアドレスに関わらず、連続的な仕方で順次に割当てられる、再マッピングするステップと、
を含む方法。
【請求項２】
請求項１記載の方法において、
付加的な受け取られたデータを連続的な仕方で再マッピングするために連続するストレージＬＢＡアドレスの１つの第２のブロックを割当てるステップをさらに含み、前記連続するストレージＬＢＡアドレスの第２のブロックは割当て時に未記入の容量だけと関連付けられ、前記第２のブロックの割当ては、前記連続するストレージＬＢＡアドレスのブロックを完全に割当てた時に初めて行われる方法。
【請求項３】
請求項１記載の方法において、
連続するストレージＬＢＡアドレスの１つのブロックを割当てるステップは、ホストＬＢＡアドレスの複数の範囲のうちの各々のために連続するストレージＬＢＡアドレスの１つのブロックを割当てるステップを含み、連続するストレージＬＢＡアドレスの各ブロックは割当て時に未記入の容量だけと関連付けられる方法。
【請求項４】
請求項３記載の方法において、
前記再マッピングするステップは、前記ホストＬＢＡアドレスの複数の範囲のうちのそれぞれの１つの中の前記受け取られたデータのための前記ホストＬＢＡアドレスの各々をストレージＬＢＡアドレスのそれぞれの割当てられた１つのブロックに再マッピングするステップを含み、連続するストレージＬＢＡアドレスの１つの割当てられたブロックの中の各ストレージＬＢＡアドレスは、前記複数の範囲のうちのそれぞれの１つに属する受け取られたデータに、前記複数の範囲のうちのそれぞれの１つの中の前記ホストＬＢＡアドレスに関わらず、前記データが受け取られた順に連続的な仕方で順次に割当てられる方法。
【請求項５】
請求項１記載の方法において、
前記連続するストレージＬＢＡアドレスのブロックと関連付けられているデータを前記連続するストレージＬＢＡアドレスのブロックと現在関連付けられているアドレスの１つの物理的ブロックの中の連続する物理アドレス位置に書き込むステップをさらに含む方法。
【請求項６】
請求項１記載の方法において、
前記大容量記憶システムは、前記ホストＬＢＡアドレスと関連付けられたデータを受け取り、前記ホストＬＢＡアドレスを再マッピングし、ガーベッジコレクション操作を開始することなく前記ストレージＬＢＡアドレスと関連付けられているデータを書き込む方法。
【請求項７】
請求項１記載の方法において、
前記再マッピングするステップは、ホストＬＢＡアドレス位置とストレージＬＢＡアドレス位置とを相関させる相関データを生成するステップと、連続するストレージＬＢＡアドレスの１つの第２のブロックにおいてそれぞれの連続するストレージＬＢＡアドレスを前記相関データに割当てるステップとをさらに含む方法。
【請求項８】
請求項７記載の方法において、
前記連続するストレージＬＢＡアドレスのブロックはもっぱら前記ホストシステムからのデータと関連付けられ、前記連続するストレージＬＢＡアドレスの第２のブロックはもっぱら前記相関データと関連付けられる方法。
【請求項９】
請求項１記載の方法において、
前記連続するストレージＬＢＡアドレスのブロックと関連付けられている、ホスト割当て解除済みデータを表す陳腐化したデータを識別するステップと、
前記連続するストレージＬＢＡアドレスのブロックからの有効なデータを連続的に再マッピングするところの連続するストレージＬＢＡアドレスの１つの再配置ブロックを選択するステップと、
前記連続するストレージＬＢＡアドレスのブロックと関連付けられている有効なデータを前記再配置ブロック内の連続するストレージＬＢＡアドレスに再割当てするステップと、
をさらに含む方法。
【請求項１０】
請求項９記載の方法において、
連続するストレージＬＢＡアドレスの１つの付加的なブロックと関連付けられた陳腐化したデータを識別するステップと、
前記連続するストレージＬＢＡアドレスの付加的なブロックからの有効なデータのためのストレージＬＢＡアドレスを前記再配置ブロック内の連続するストレージＬＢＡアドレスに再割当てするステップであって、前記再配置ブロックが満杯である時には、未記入容量だけを有する１つの新しい再配置ブロックが選択され、前記付加的なブロックからの残りの有効なデータは前記新しい再配置ブロック内の連続するストレージＬＢＡアドレスに再割当てされる、再割当てするステップと、
をさらに含む方法。
【請求項１１】
請求項９記載の方法において、
連続するストレージＬＢＡアドレスの前記再配置ブロックは、もっぱら再マッピングされる有効なホストデータと関連付けられる方法。
【請求項１２】
請求項８記載の方法において、
前記連続するストレージＬＢＡアドレスの第２のブロックと関連付けられている陳腐化した相関データを識別するステップと、
前記連続するストレージＬＢＡアドレスの第２のブロックからの有効な相関データを連続的に再マッピングするところの連続するストレージＬＢＡアドレスの１つの再配置ブロックを選択するステップと、
前記連続するストレージＬＢＡアドレスの第２のブロックからの有効な相関データを前記再配置ブロック内の連続するストレージＬＢＡアドレスに再割当てするステップと、
をさらに含む方法。
【請求項１３】
請求項１２記載の方法において、
もっぱら相関データと関連付けられた連続するストレージＬＢＡアドレスの１つの付加的なブロックと関連付けられた陳腐化した相関データを識別するステップと、
有効な相関データのためのストレージＬＢＡアドレスを前記連続するストレージＬＢＡアドレスの付加的なブロックから前記再配置ブロック内の連続するストレージＬＢＡアドレスに再割当てするステップであって、前記再配置ブロックが満杯である時には、未記入容量だけを有する１つの新しい再配置ブロックが選択されて、前記付加的なブロックと関連付けられている残りの有効な相関データは前記新しい再配置ブロック内の連続するストレージＬＢＡアドレスに再割当てされる、再割当てするステップと、
をさらに含む方法。
【請求項１４】
請求項１記載の方法において、
白色ステータスまたはピンク色ステータスを有する連続するストレージＬＢＡアドレスの複数のブロックのステータスを追跡するステップをさらに含み、白色ステータスは未記入容量だけと関連付けられている任意のブロックを特定し、ピンク色ステータスは有効なデータおよび陳腐化したデータの両方と関連付けられている任意のブロックを特定する方法。
【請求項１５】
請求項１記載の方法において、
以前に受け取られたホストＬＢＡアドレスと関連付けられている新しいデータを受け取る前に有効なデータおよび陳腐化したデータを現在アドレス指定している連続するストレージＬＢＡアドレスの以前に完全にプログラムされたブロックを識別するステップと、
その識別された、有効なデータおよび陳腐化したデータを現在アドレス指定している連続するストレージＬＢＡアドレスの以前に完全にプログラムされたブロックから、未記入容量だけをアドレス指定する連続するストレージＬＢＡアドレスの新しいブロックを作るステップと、
をさらに含む方法。
【請求項１６】
請求項１５記載の方法において、
前記連続するストレージＬＢＡアドレスの新しいブロックを作るステップは、
識別された連続するストレージＬＢＡアドレスの以前に満たされたブロックを、各々の以前に満たされたブロックにおいてアドレス指定される陳腐化したデータの量によって格付けするステップと、 前記格付けされた以前に満たされたブロックから有効なデータをその中に連続的に再マッピングするための連続するストレージＬＢＡアドレスの１つの再配置ブロックを選択するステップと、
有効なデータのためのストレージＬＢＡアドレスを、前記格付けされた以前に満たされたブロックのうちの選択された１つから前記再配置ブロック内の連続するストレージＬＢＡアドレスに再マッピングするステップと、
前記再配置ブロックが完全に書き込まれたならば、未記入容量だけをアドレス指定する１つの新しい再配置ブロックを選択するステップと、
を含む方法。
【請求項１７】
請求項１５記載の方法において、
前記連続するストレージＬＢＡアドレスの以前に完全にプログラムされたブロックを識別するステップは、前記大容量記憶装置においてクラスタ割当てマップをスキャンするステップを含む方法。
【請求項１８】
請求項１７記載の方法において、
前記ホストシステムはＮＴＦＳファイルシステムを含み、前記クラスタ割当てマップは＄ｂｉｔｍａｐファイルを含む方法。
【請求項１９】
請求項１５記載の方法において、
前記連続するストレージＬＢＡアドレスの以前に完全にプログラムされたブロックを識別するステップは、ホストシステムコマンドを前記大容量記憶システムにおいて受け取るステップを含み、前記ホストシステムコマンドは陳腐化したデータアドレスを識別する方法。
【請求項２０】
一緒に消去可能なメモリセルの複数のブロックに配列された再プログラム可能な不揮発性メモリセルと、
ホスト論理ブロックアドレス（ＬＢＡ）フォーマットでアドレス指定されるデータをホストシステムから受け取るようになっているインターフェイスと、
前記インターフェイスと通信するコントローラと、を備える不揮発性大容量記憶システムであって、前記コントローラは、
受け取られたホストＬＢＡアドレスを、受け取られた順に、連続するストレージＬＢＡアドレスの１つのブロックに連続的に再マッピングし、
前記連続するストレージＬＢＡアドレスのブロックが満杯である時には、割当て時に未記入容量だけをアドレス指定する連続するストレージＬＢＡアドレスの１つの付加的なブロックを割当てて、付加的な受け取られたホストＬＢＡアドレスを前記付加的なブロックに連続的に再マッピングし、
前記ホストＬＢＡアドレスと関連付けられたデータが連続するストレージＬＢＡアドレスに再マッピングされる時には、ホストＬＢＡアドレスをストレージＬＢＡアドレスにマッピングするストレージアドレステーブル（ＳＡＴ）を生成するように構成される不揮発性大容量記憶システム。
【請求項２１】
請求項２０記載のシステムにおいて、
前記ＳＡＴを生成するために、前記コントローラは、ホストＬＢＡアドレスのストレージＬＢＡアドレスへの連続的な仕方でのマッピングに関連する情報を、前記ＳＡＴに関するデータだけのために指定された連続的なストレージＬＢＡアドレスの１つのブロックに関連付けるように構成されるシステム。
【請求項２２】
請求項２０記載のシステムにおいて、
前記コントローラは、有効なデータを包含しない連続するストレージＬＢＡアドレスの新しいブロックを作るようにさらに構成されるシステム。
【請求項２３】
請求項２２記載のシステムにおいて、
前記コントローラは、連続するストレージＬＢＡアドレスの新しいブロックを作るために、
再マッピングされたホストＬＢＡアドレスと以前に完全に関連付けられて、陳腐化したデータの１つ以上のページを現在アドレス指定しているストレージＬＢＡアドレスのブロックを識別し、
有効なデータのためのアドレスを、１つの第１の識別されたブロックから、前記有効なデータが前記第１の識別されたブロックの中で存在する順に、１つの再配置ブロックの中に連続的な順序で、前記第１の識別されたブロックが有効なデータをアドレス指定しなくなるまで、再配置するようにさらに構成されるシステム。
【図１】
image rotate

【図２】
image rotate

【図３】
image rotate

【図４】
image rotate

【図５】
image rotate

【図６】
image rotate

【図７】
image rotate

【図８】
image rotate

【図９】
image rotate

【図１０】
image rotate

【図１１】
image rotate

【図１２】
image rotate

【図１３】
image rotate

【図１４】
image rotate

【図１５】
image rotate

【図１６】
image rotate

【図１７】
image rotate

【図１８】
image rotate

【図１９】
image rotate

【図２０】
image rotate

【図２１】
image rotate

【図２２】
image rotate

【図２３】
image rotate

【図２４】
image rotate

【図２５】
image rotate

【図２６】
image rotate

【図２７】
image rotate

【図２８】
image rotate

【図２９】
image rotate

【図３０】
image rotate

【図３１】
image rotate

【図３２】
image rotate

【図３３】
image rotate

【図３４】
image rotate

【図３５】
image rotate

【図３６】
image rotate

【図３７】
image rotate

【図３８】
image rotate

【公表番号】特表２０１０−５３２０２３（Ｐ２０１０−５３２０２３Ａ）
【公表日】平成２２年９月３０日（２０１０．９．３０）
【国際特許分類】
【出願番号】特願２０１０−５１１２７５（Ｐ２０１０−５１１２７５）
【出願日】平成２０年６月３日（２００８．６．３）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０６５６３１
【国際公開番号】ＷＯ２００８／１５４２１６
【国際公開日】平成２０年１２月１８日（２００８．１２．１８）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．コンパクトフラッシュ
２．ウィンドウズ
【出願人】（５０６１９７９０１）サンディスク　コーポレイション (175)
【Ｆターム（参考）】

[ Back to top ]