JP2011519095A - マルチバンク記憶装置のためのストレージアドレス再マッピングのための方法およびシステム - Google Patents

Abstract

マルチバンクメモリにおけるストレージアドレス再マッピングのための方法およびシステムが開示される。この方法は、クラスタのブロックの中の論理アドレスを割り当てることと、論理アドレスをストレージアドレス空間内に再マッピングすることとを含み、論理アドレス空間内に分散しているホストデータの短いランはストレージアドレス空間においてメガブロックの中に連続的にマッピングされる。各バンクにおいて独立に、特定のバンク内で利用可能な新しいブロックの数が所望しきい値未満まで減ったとき、マルチバンクメモリの各バンクにおいてデータを受け取るために利用し得る新しいブロックを作るために、有効なデータおよび使用済データの両方を有するブロックからそれぞれのバンクの中で有効なデータがフラッシングされる。

Description

本発明は、一般的にはオペレーティングシステムと記憶装置との間のデータ通信に関する。より具体的には、本発明は、マルチバンク再プログラム可能な不揮発性半導体フラッシュメモリなどのメモリシステムと、メモリが接続されているかあるいは接続可能であるホスト装置との操作に関する。

従来のフラッシュデータメモリシステムにデータを書き込むとき、ホストは、通例、メモリシステムの連続的な仮想アドレス空間の中のセクタ、クラスタまたは他のデータユニットに一意の論理アドレスを割り当てる。ホストは、メモリシステムの論理アドレス空間の中のアドレスにデータを書き込み、アドレスからデータを読み出す。そのとき、メモリシステムは、一般に、論理アドレス空間と、データが論理アドレス空間内の範囲に対応する固定された論理グループを構成して格納されるメモリの物理的ブロックまたはメタブロックとの間でデータをマッピングする。一般に、各々の固定された論理グループはメモリシステムの別々の物理的ブロックに格納される。メモリシステムは、論理アドレス空間が物理メモリにどのようにマッピングされるかを追跡するけれども、ホストはこれを知らない。ホストは、論理アドレス空間の中のそれ自身のデータファイルのアドレスを追跡するけれども、メモリシステムはこのマッピングについての情報なしで動作する。

このように動作するメモリシステムの欠点は断片化である。例えば、ＮＴＦＳファイルシステムにしたがって動作するパーソナルコンピュータ（ＰＣ）においてソリッドステートディスク（ＳＳＤ）ドライブに書き込まれたデータは、ドライブの論理アドレス空間の中の広く分布する位置に存在する連続するアドレスの短いランのパターンにより特徴付けられることが多い。ホストにより使用されるファイルシステムが、連続するファイルについて新しいデータのために順次アドレスを割り当てたとしても、削除されるファイルの気まぐれなパターンに起因して、利用可能な空きメモリ空間が新しいファイルデータのためにブロック化ユニットをなして割り当てられ得ないような利用可能な空きメモリ空間の断片化が生じる。

フラッシュメモリマネージメントシステムは、連続する論理アドレスのブロックを物理アドレスのブロックにマッピングすることによって動作しがちである。ホストからのアドレスの短いランが独立して更新されるとき、そのランを含むアドレスの論理ブロック全体が、単一のブロックへのそれ自身の長期マッピングを維持しなければならない。これは論理対物理メモリマネージメントシステムの中でのガーベッジコレクション操作を必要とし、その操作で、論理ブロック内のホストにより更新されない全てのデータは、更新されるデータとそれとを統合するために再配置される。データが、マルチバンクシステムを構成する別々のフラッシュメモリバンクにおける格納されたブロックであり得るマルチバンクフラッシュメモリシステムにおいて、統合プロセスは大規模になることがある。これはかなりのオーバーヘッドであり、書き込み速度およびメモリ寿命を厳しく制限するかもしれない。

米国特許第５，５７０，３１５号 米国特許第５，７７４，３９７号 米国特許第６，０４６，９３５号 米国特許第６，３７３，７４６号 米国特許第６，４５６，５２８号 米国特許第６，５２２，５８０号 米国特許第６，７７１，５３６号 米国特許第６，７８１，８７７号 米国公開特許出願第２００３／０１４７２７８号 米国公開特許出願第２００３／０１０９０９３号 米国特許出願第１２／０３６，０１４号

マルチバンクメモリシステムにおける改良されたメモリ管理に対する需要に対処するために、本願明細書において方法が開示される。第１の実施形態にしたがって、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法が開示される。この方法は、ホストシステムにより割り当てられたホスト論理ブロックアドレス（ＬＢＡ）アドレスと関連付けられたデータを受け取ることと、ホストＬＢＡアドレスと関連付けられているデータをアドレス指定するための連続的ストレージＬＢＡアドレスのメガブロックを割り当てることとを含み、連続的ストレージＬＢＡアドレスのメガブロックは、大容量記憶システム内のメモリセルの複数のバンクの各々の中のメモリセルの少なくとも１つのブロックを含み、割り当て時に未書き込み容量だけをアドレス指定する。受け取られたデータのためのホストＬＢＡアドレスの各々について、連続的ストレージＬＢＡアドレスのメガブロックへの再マッピングが行われ、各ストレージＬＢＡアドレスは、受け取られたデータに対して、ホストＬＢＡアドレスに関わらず、受け取られたデータが受け取られた順に連続的に順次に割り当てられる。さらに、複数のバンクのうちの第１のものの中のブロックは複数のバンクのうちの第２のものの中のブロックとは独立にフラッシングされ、第１のバンク内のブロックをフラッシングすることは、有効なデータのためのホストＬＢＡアドレスを第１のバンク内のブロックのストレージＬＢＡアドレスから第１の再配置ブロック内の連続的ストレージＬＢＡアドレスに再割り当てすることを含み、第２のバンク内のブロックをフラッシングすることは、有効なデータのためのホストＬＢＡアドレスを第２のバンク内のブロックのストレージＬＢＡアドレスから第２の再配置ブロック内の連続的ストレージＬＢＡアドレスに再割り当てすることを含む。

他の実施形態にしたがって、ホストシステムと再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法が提供され、大容量記憶システムはメモリセルの複数のバンクを有し、複数のバンクの各々は、一緒に消去可能なメモリセルのブロックとして構成されている。この方法は、受け取られたホストデータのためのホスト論理ブロックアドレス（ＬＢＡ）アドレスをストレージＬＢＡアドレスのメガブロックに再マッピングすることを含み、ストレージＬＢＡアドレスのメガブロックはメモリセルの複数のバンクの各々の中にメモリセルの少なくとも１つのブロックを有する。受け取られたデータのためのホストＬＢＡアドレスは、ホストＬＢＡアドレスに関わらずデータが受信された順にメガブロック内でメガページ順にストレージＬＢＡアドレスに連続的に割り当てられ、各メガページはメガブロックのブロックの各々についてメタページを含む。この方法は、バンクの各々において独立にフラッシング操作を実行することを含む。フラッシング操作は、有効なデータのためのホストＬＢＡアドレスを特定のバンク内のブロックのストレージＬＢＡアドレスから特定のバンクの中の再配置ブロック内の連続的ストレージＬＢＡアドレスに再割り当てすることを含む。
本発明の他の特徴および利点は、次の図面、詳細な説明および特許請求の範囲を検討すれば明らかとなる。

マルチバンク不揮発性メモリを有するメモリシステムと接続されたホストを示す。 図１のマルチバンク不揮発性メモリに用いられるフラッシュメモリシステムコントローラの例のブロック図の例である。 図１に示されているフラッシュメモリバンクのうちの１つとして適切な１つのフラッシュメモリバンクの例である。 図３のメモリバンクに使用され得るメモリセルアレイの代表的な回路図である。 図３のメモリバンクの物理的メモリ構成の例を示す。 図５の物理的メモリの一部分の拡大図を示す。 図１のマルチバンクメモリ内の複数のバンクの物理的メモリ構成を示す。 ホストＬＢＡアドレス空間における割り当て済みクラスタおよび空きクラスタの典型的なパターンを示す。 １つの開示された実施例に従うブロックによるクラスタの割り当てのパターンを示す。 メモリシステムのメモリマネージャがストレージアドレス指定再マッピング機能を組み入れている場合のホストとメモリシステムとの間でのストレージアドレス再マッピングの実施例を示す。 図１０に示されているストレージアドレス再マッピングの代替の実施例を示す。 機能がホストに置かれている場合のストレージアドレス再マッピングの実施例を示す。 図１０〜１２のシステムに用いられるマルチバンク書き込みアルゴリズムの流れ図である。 メモリシステムの個々のバンクの中でのクラスタのブロックの割り当ての状態図である。 マルチバンクメモリシステムの各バンクに独立に加えられ得るフラッシング操作の流れ図である。 メガブロックにおけるＤＬＢＡラン分布を示す。 図１６のＤＬＢＡラン分布のためのメガブロック書き込みプロシージャおよびストレージアドレステーブル生成を示す。 図１６のメガブロック内のブロックがフラッシングされた後のＤＬＢＡランの再配列例を示す。 マルチバンクメモリにおける１つのバンクのＤＬＢＡアドレス空間におけるフラッシング操作と、そのバンクのための物理アドレス空間における対応する更新ブロックとを示す。 図１９のバンクのＤＬＢＡ空間における第２のフラッシング操作を示す。 フラッシング操作のためのピンク色ブロック選択プロセスの流れ図である。 ホスト論理アドレスが第２の論理アドレス空間に再マッピングされる構成におけるストレージアドレステーブル（ＳＡＴ）階層を示す。 論理対論理マッピングを追跡するのに使用されるストレージアドレステーブル（ＳＡＴ）書き込みブロックを示す。 図２３のＳＡＴテーブルのＳＡＴページに用いられるＬＢＡエントリである。 図２３のＳＡＴテーブルのＳＡＴページに用いられるＤＬＢＡエントリである。 図２３のＳＡＴテーブルのＳＡＴページに用いられるＳＡＴ索引エントリである。 図１１および１２のストレージアドレス再マッピングの実施例に用いられるストレージアドレステーブル変換プロシージャを示す。 ＳＡＴブロック遷移の状態図を示す。 ＳＡＴブロックのフラッシング順序を決定するためのプロセスの流れ図である。 ブロック情報テーブル（ＢＩＴ）書き込みブロックを示す。 メガブロックにおけるＤＬＢＡラン分布を示す。 論理アドレスの完全なメガブロックがＤＬＢＡランにマッピングされるＳＡＴの実施形態を示す。 ＬＢＡアドレスのためのアドレスフォーマットの例を示す。

本発明の諸態様を実施するために用いるのに適するフラッシュメモリシステムが図１〜７に示されている。図１のホストシステム１００は、メモリシステム１０２にデータを格納し、メモリシステムからデータを取り出す。メモリシステムは、パーソナルコンピュータにインストールされたソリッドステートディスク（ＳＳＤ）ドライブの形などの、ホストに組み込まれたフラッシュメモリであり得る。代わりに、メモリシステム１０２は、図１に示されている機械的電気的コネクタの接合部品１０３および１０４を通してホストに取り外し可能に接続されるカードの形であり得る。内部のあるいは組み込みのＳＳＤドライブとして用いられるべく構成されたフラッシュメモリは図１の略図に類似して見えるかもしれないが、主な違いは、ホスト内のメモリシステム１０２の位置である。ＳＳＤドライブは、回転式磁気ディスクドライブのドロップイン代替品（完全互換品）である別々のモジュールの形であり得る。

商業的に入手可能なＳＳＤドライブの一例は、サンディスク コーポレイションにより製造されている３２ギガバイトＳＳＤである。商業的に入手可能な取り外し可能のフラッシュメモリカードの例は、コンパクトフラッシュ（ＣＦ）、マルチメディアカード（ＭＭＣ）、セキュアデジタル（ＳＤ）、ミニＳＤ、メモリスティック、スマートメディアおよびトランスフラッシュカードを含む。これらのカードの各々は、その標準化された仕様に従う独特の機械的および／または電気的インターフェイスを有するけれども、各々に含まれるフラッシュメモリシステムは類似している。これらのカードは、全て、本願の譲受人であるサンディスク コーポレイションから入手可能である。サンディスク コーポレイションは、そのＣｒｕｚｅｒ（クルーザー）という登録商標のもとで一系列のフラッシュドライブも提供し、それらは、ホストのＵＳＢレセプタクルに差し込むことによってホストと接続されるユニバーサルシリアルバス（ＵＳＢ）プラグを有する小型パッケージ内のハンドヘルドのメモリシステムである。これらのメモリカードおよびフラッシュドライブの各々は、ホストとインターフェイスしてそれらの中のフラッシュメモリの動作を制御するコントローラを含む。

ＳＳＤ、メモリカードおよびフラッシュドライブを使用することのできるホストシステムは多数あって多様である。それらは、デスクトップまたはラップトップおよび他の携帯用コンピュータなどのパーソナルコンピュータ（ＰＣ）、セルラー電話、個人用携帯情報端末（ＰＤＡ）、デジタルスチルカメラ、デジタルムービーカメラおよび携帯用オーディオプレーヤを含む。携帯用メモリカードアプリケーションのために、ホストは１つ以上のタイプのメモリカードまたはフラッシュドライブのための内蔵型レセプタクルを含むこともあるし、あるいはホストはメモリカードが差し込まれるアダプタを必要とすることもある。メモリシステムは普通それ自身のメモリコントローラおよびドライバを含むが、代わりに、メモリが接続されたホストにより実行されるソフトウェアによって制御されるメモリオンリーのシステムもある。コントローラを含むあるメモリシステム、特にホストに組み込まれるものでは、メモリ、コントローラおよびドライバはしばしば単一の集積回路チップ上に形成される。

図１のホストシステム１００は、メモリ１０２に関する限り、回路とソフトウェアとの組み合わせから成る２つの主要部分を有すると見られ得る。それらは、アプリケーション部分１０５と、メモリ１０２とインターフェイスするドライバ部分１０６とである。例えばＰＣでは、アプリケーション部分１０５は、ワードプロセッシング、グラフィクス、制御または他のポピュラーなアプリケーションソフトウェアを実行するプロセッサ１０９と、ホスト１００上のデータを管理するためのファイルシステム１１０とを含むことができる。カメラ、セルラー電話あるいは他の、単一セットの機能を実行するために主として専用されるホストシステムでは、アプリケーション部分１０５は、写真を撮って記憶するようにカメラを操作したり、電話をかけたり受けたりするようにセルラー電話を操作したりなどするソフトウェアを含む。

図１のメモリシステム１０２は、マルチバンクフラッシュメモリ１０７などの不揮発性メモリと、メモリシステム１０２が接続されているホスト１００とデータをやり取りするためにインターフェイスすると共にメモリ１０７を制御するコントローラ回路１０８とを含むことができる。コントローラ１０８は、データプログラミングおよび読み出し中に、ホスト１００により使用されるデータの論理アドレスとマルチバンクフラッシュメモリ１０７の物理アドレスとの間の変換を行うことができる。マルチバンクフラッシュメモリ１０７は任意の数のメモリバンクを含むことができ、ここでは４つのメモリバンク１０７Ａ〜１０７Ｄが単に実例として示されている。

図２を参照すると、システムコントローラ１０８は、特定用途向け集積回路（ＡＳＩＣ）などの単一の集積回路チップ上に実装され得る。コントローラ１０８のプロセッサ２０６は、マルチバンクフラッシュメモリ１０７内のそれぞれのバンク１０７Ａ〜１０７Ｄの各々のためのＩ／Ｏポートを有するメモリインターフェイス２０４を介してそれぞれのメモリバンク１０７Ａ〜１０７Ｄの各々と別々に通信することのできるマルチスレッドプロセッサとして構成され得る。コントローラ１０８は内部クロック２１８を含むことができる。プロセッサ２０６は、内部データバス２０２を介して誤り訂正符号（ＥＣＣ）モジュール２１４、ＲＡＭバッファ２１２、ホストインターフェイス２１６、およびブートコードＲＯＭ２１０と通信する。

図３の単一バンク１０７Ａの図を参照すると、マルチバンクフラッシュメモリ１０７内の各バンクは１つ以上の集積回路チップから成ることができ、各チップは複数のサブアレイまたはプレーンに構成されたメモリセルのアレイを含むことができる。２つのそのようなプレーン３１０および３１２が簡略化して図に示されているけれども、その代わりに４個または８個などのより多くのそのようなプレーンを使用してもよい。あるいは、メモリバンクのメモリセルアレイはプレーンに分割されないかもしれない。しかし、そのように分割されるならば、各プレーンは、互いに独立に動作し得るそれ自身の列制御回路３１４および３１６を有する。回路３１４および３１６は、それらのそれぞれのメモリセルアレイのアドレスをシステムバス３０２のアドレス部分３０６から受け取って、それぞれのビット線３１８および３２０のうちの特定の１つ以上をアドレス指定するためにそれらを復号する。ワード線３２２は、アドレスバス１９で受け取られるアドレスに応答して行制御回路３２４を通してアドレス指定される。ソース電圧制御回路３２６および３２８も、ｐウェル電圧制御回路３３０および３３２と同じく、それぞれのプレーンと接続されている。バンク１０７Ａがメモリセルの単一のアレイを有するメモリチップの形であるならば、そして２つ以上のそのようなチップがシステム内に存在するならば、各チップのアレイは前述したマルチプレーンチップの中のプレーンまたはサブアレイと同様に操作され得る。各バンク１０７Ａ〜１０７Ｄは、諸機能がコントローラ１０８によって独立に同時にあるいは非同期に制御され得るように構成される。例えば、第１のバンクは、第２のバンクがデータを読み出している間、データを書き込むように命令され得る。

データは、システムバス３０２のデータ部分３０４と接続されているそれぞれのデータ入出力回路３３４および３３６を通してプレーン３１０および３１２内へ、およびプレーン外へ転送される。回路３３４および３３６は、それぞれの列制御回路３１４および３１６を通してプレーンに接続されているライン３３８および３４０を通して、データをメモリセル内にプログラムすると共にそれらのそれぞれのプレーンのメモリセルからデータを読み出すことに配慮している。

コントローラ１０８内のプロセッサ２０６は、データをプログラムし、データを読み出し、消去し、さらに種々のハウスキーピング事項を処理するために各バンク１０７Ａ〜１０７Ｄ内のメモリチップの動作を制御するけれども、各メモリチップも、そのような機能を実行するためのコントローラ１０８からのコマンドを実行するある制御回路を含む。インターフェイス回路３４２は、システムバス３０２の制御およびステータス部分３０８に接続されている。コントローラ１０８からのコマンドは状態マシン３４４に提供され、これはその後、これらのコマンドを実行するために他の回路の具体的な制御を提供する。制御線３４６〜３５４は、状態マシン３４４を、図３に示されているようにこれらの他の回路に接続する。状態マシン３４４からのステータス情報は、バス部分３０８を介してコントローラ１０８へ送信されるべく線３５６を介してインターフェイス３４２に伝えられる。

以下でメモリセルアレイ３１０および３１２のＮＡＮＤアーキテクチャが論じられるけれども、ＮＯＲなどの他のアーキテクチャが代わりに使用されてもよい。米国特許第５，５７０，３１５号（特許文献１）、第５，７７４，３９７号（特許文献２）、第６，０４６，９３５号（特許文献３）、第６，３７３，７４６号（特許文献４）、第６，４５６，５２８号（特許文献５）、第６，５２２，５８０号（特許文献６）、第６，７７１，５３６号（特許文献７）および第６，７８１，８７７号（特許文献８）ならびに米国公開特許出願第２００３／０１４７２７８号（特許文献９）を参照することによってＮＡＮＤフラッシュメモリおよびメモリシステムの一部としてのそれらの動作の例が得られる。一例であるＮＡＮＤアレイが図４の回路図により図に示され、これは、図３のメモリシステムのメモリセルアレイ３１０の一部分である。多数のグローバルビット線が設けられ、説明を簡単にするためにそのような線４０２〜４０８が４つだけ図４に示されている。これらのビット線のうちの１つと基準電位との間に、直列接続されているメモリセルストリング４１０〜４２４がいくつか接続されている。メモリセルストリング４１４を代表として用いると、複数の電荷蓄積メモリセル４２６〜４３２が、ストリングの両端の選択トランジスタ４３４および４３６と直列に接続されている。ストリングの選択トランジスタが導通させられると、ストリングはそのビット線と基準電位との間に接続される。その後、そのストリングの中のメモリセルが一度に１つずつプログラムまたは読み出しされる。

図４のワード線４３８〜４４４はメモリセルのいくつかのストリングのうちの各々の中の１つのメモリセルの電荷蓄積素子を横断してそれぞれ延び、ゲート４４６および４５０はストリングの各端の選択トランジスタの状態を制御する。共通のワード線およびコントロールゲート線４３８〜４５０を共有するメモリセルストリングは、一緒に消去されるメモリセルのブロック４５２を形成させられる。セルのこのブロックは、一度に物理的に消去可能な最小数のセルを含む。ワード線４３８〜４４４のうちの１つに沿う１行のメモリセルが一度にプログラムされる。通例、ＮＡＮＤアレイの行は、この場合には接地または他の共通電位に接続されているストリングの端に最も近いワード線４４４に沿う行から始まる、所定の順序でプログラムされる。ワード線４４２に沿うメモリセルの行が次にプログラムされるなどして、ブロック４５２全体にわたってプログラムが行われる。ワード線４３８に沿う行は最後にプログラムされる。

第２のブロック４５４は同様であって、そのメモリセルのストリングは、第１のブロック４５２のストリングと同じグローバルビット線に接続されているけれどもワード線およびコントロールゲート線の異なるセットを有する。ワード線およびコントロールゲート線は、行制御回路３２４によってそれらの適切な動作電圧まで駆動される。図３のプレーン１および２など、システムに２つ以上のプレーンまたはサブアレイが存在すれば、１つのメモリアーキテクチャは、それらの間で延びる共通のワード線を使用する。代わりに、共通のワード線を共有する３つ以上のプレーンまたはサブアレイがあり得る。他のメモリアーキテクチャでは、個々のプレーンまたはサブアレイのワード線は別々に駆動される。

前に援用されているＮＡＮＤ特許および公開された特許出願のうちのいくつかに記載されているように、メモリシステムは、各々の電荷蓄積素子または領域に２つより多い検出可能な電荷のレベルを記憶させ、それによって各々に１ビットより多いデータを記憶させるように操作され得る。メモリセルの電荷蓄積素子は、非常に一般的には伝導性フローティングゲートであるけれども、その代わりに、米国公開特許出願第２００３／０１０９０９３号（特許文献１０）に記載されているように、非伝導性誘電体電荷トラッピング材料であってもよい。

図５は、以下のさらなる記述において例として用いられるマルチバンクフラッシュメモリ１０７（図１）の１つのバンク１０７Ａの構成を概念的に示す。メモリセルの４つのプレーンまたはサブアレイ５０２〜５０８は、単一の統合メモリセルチップ上に、２つのチップ上に（各チップ上にプレーンのうちの２つ）あるいは４つの別々のチップ上に存在し得る。具体的な構成は、以下の論議には重要でない。もちろん、１、２、８、１６あるいはそれ以上などの他の数のプレーンがシステム内に存在し得る。プレーンは、それぞれのプレーン５０２〜５０８内に位置するブロック５１０、５１２、５１４および５１６などの長方形により図５に示されているメモリセルのブロックにそれぞれ分割されている。各プレーン内に数十または数百のブロックが存在し得る。

前に言及されたように、メモリセルのブロックは、消去の単位、物理的に一緒に消去可能な最小数のメモリセルである。しかし、並列性を高めるために、ブロックはより大きなメタブロック単位で操作される。各プレーンからの１ブロックが１つのメタブロックを形成するように互いに論理的にリンクされる。４つのブロック５１０〜５１６は１つのメタブロック５１８を形成して示されている。メタブロック内のセルの全てが通例一緒に消去される。メタブロックを形成するために使用されるブロックは、ブロック５２２〜５２８から成る第２のメタブロック５２０において示されているように、それぞれのプレーンの中の同じ相対位置に限定されなくてもよい。全プレーンにわたってメタブロックを広げるのが普通は好ましいけれども、システム性能を高めるために、メモリシステムは異なるプレーン内の１、２または３ブロックのいずれかまたは全部からメタブロックを動的に形成する能力を用いて操作され得る。これにより、メタブロックのサイズを、１プログラミング操作で記憶させるのに使用できるデータの量により厳密に調和させることが可能となる。

一方、個々のブロックは、操作の目的のために、図６に示されているようにメモリセルのページに分割される。例えば、ブロック５１０〜５１６の各々のメモリセルは、各々８ページＰ０〜Ｐ７に分割されている。代わりに、各ブロック内にメモリセルの１６、３２あるいはそれ以上のページがあってもよい。ページは、ブロックの中でのデータのプログラミングおよび読み出しの単位であって、一度にプログラムされるかまたは読み出される最少量のデータを含む。図３のＮＡＮＤアーキテクチャでは、１ページは１ブロック内の１ワード線に沿うメモリセルから形成される。しかし、メモリシステムの動作並列性を高めるために、２以上のブロックの中のそのようなページが論理的にリンクされてメタページにされ得る。メタページ６０２が図６に示され、４つのブロック５１０〜５１６の各々からの１物理ページから形成されている。例えば、メタページ６０２は４ブロックの各々のページＰ２を含むけれども、メタページのページは必ずしも各ブロック内の同じ相対位置を持っていなくてもよい。バンク内で、メタページはプログラミングの最大単位である。

前述したように、図５〜６は、マルチバンクメモリ１０７の１つのメモリバンク１０７Ａに存在し得るメモリセル構成の一実施形態を示す。一実施形態では、各バンク１０７Ａ〜１０７Ｄのための個々のメモリセル構成に関わらず、メモリシステム１０２は好ましくはメガブロックというプログラミングの最大単位を有するように構成され、メガブロックは、メモリバンクが単一プレーン構成に整えられているならばマルチバンクメモリ内の各バンクの少なくとも１ブロックにまたがるか、あるいは、メモリバンクが複数プレーン構成に整えられているならばマルチバンクフラッシュメモリ１０７内の各バンクの１メタブロックにまたがる。以下の論議では、記述を明瞭にするために、各バンクはメタブロックの列として構成されていると仮定される。図７を参照すると、示されている各列は、前に論じられたメタブロック５１８、５２０などのメタブロック７０２のバンク１０７Ａ〜１０７Ｄを表す。メガブロック７０４は各バンク１０７Ａ〜１０７Ｄ内の少なくとも１つのメタブロック７０２を含み、各メタブロック７０２は複数のメタページ７０６に分割されている。図７において特定されているメガブロック７０４は各バンク１０７Ａ〜１０７Ｄ内の同じ相対的物理的位置にメタブロック７０２を示しているけれども、メガブロック７０４を形成するために使用されるメタブロック７０２は同じ相対的物理的位置に限定されなくてもよい。さらに、本願明細書で言及されるとき、メガページ７０８は、メガブロック７０４内のメタブロック７０２の各々からのメタページ７０６を指す。メモリバンク１０７Ａ〜１０７Ｄは、それぞれ同様に整えられてもよいし、あるいは互いに異なるメモリセル配列を持ってもよい。例えば、バンクは、バイナリ（単層セル、すなわちＳＬＣ）フラッシュの第１のバンクと多層セル（ＭＬＣ）フラッシュの他のバンクを持つなどして、種々のメモリ技術を使用することができる。さらに別の実施形態では、通常バンクブロックで必要となるデータの移動を伴わずにメガページの属性を更新できるように第１のバンクを再書き込み可能な不揮発性フラッシュとして製造することができて、残りのバンクは標準的フラッシュ（例えば、バイナリフラッシュまたは多層セルフラッシュ）を使用することができる。

次に、図８を参照すると、ホスト１００とメモリシステム１０２との間の共通論理インターフェイスは、メモリシステム１０２に格納され得るデータ全てのためにアドレスを提供するために充分に大きい連続的論理アドレス空間８００を利用する。前述したホスト１００およびメモリシステム１０２を参照すると、マルチバンクフラッシュメモリ１０７に格納されるべきデータは、通例、ホスト論理ブロックアドレス（ＬＢＡ）フォーマットで受け取られる。このホストアドレス空間８００は、通例、データのクラスタのインクリメントに分割されている。各クラスタはデータの数個のセクタを包含するように所与のホストシステムにおいて設計することができ、およそ４〜６４セクタが一般的である。標準的セクタは５１２バイトのデータを包含する。図８を参照すると、ＮＴＦＳファイルシステムのための論理アドレス空間８００における割り当て済みクラスタ（陰影付き）８０２と空きクラスタ（陰影なし）８０４との代表的なパターンが示されている。

図８に見られる論理アドレス空間８００の断片化を処理するための組織的構造が図９に示されている。本願明細書に記載されているストレージアドレス再マッピングのためのシステムおよび方法は、以下の論議において一般的に「ブロック」と称されるクラスタ９００のメタブロックという項においてＬＢＡアドレスを割り当てる。以下の記述において、有効なデータで完全に満たされているブロック９００は赤色ブロック９０２と称され、有効なデータを持っていなくて、したがって未書き込み容量だけを包含するブロックは白色ブロック９０４と称される。白色ブロック９０４内の未書き込み容量は、メモリシステム１０２が「使用後消去」型のプロシージャを採用しているならば、消去済み状態であり得る。あるいは、メモリシステム１０２が「使用前消去」型のプロシージャを採用しているならば、白色ブロック９０４内の未書き込み容量は、割り当て時に消去されなければならない使用済データから成り得る。完全にプログラムされていてデータの有効なクラスタ８０２とデータの無効な（使用済みとも言われる）クラスタ８０４との両方を有するブロックはピンク色ブロック９０６と称される。本願明細書においてより詳細に論じられるように、各バンク１０７Ａ〜１０７Ｄ内の少なくとも１つの白色ブロック９０４から構成されるメガブロック７０４は、ホストからデータを受け取るために割り当てられ、書き込みメガブロックと称される。

以下で記述されるマルチバンク書き込みアルゴリズムおよびフラッシング技術の実施例は、ホスト１００およびメモリシステム１０２の構成に応じて変化し得る。図１０〜１２は、ホストおよびメモリシステムの間での再マッピング機能のいくつかの構成を示す。図１０〜１１の構成は、ストレージアドレス再マッピング（ＳＴＡＲ：storage address re-mapping）機能が完全にメモリシステム１００４、１１０２に包含される実施形態を表す。これら始めの２つの構成では、メモリシステム１００４、１１０２は、ホスト１００２での改変を必要とせずにレガシーホスト１００２と協動することができる。逆に、図１２に示されている構成は、ストレージアドレス再マッピング機能が完全にホスト１２０２に包含される実施形態のものである。この後者の実施形態では、ホスト１２０２は、改変を必要としないレガシーストレージ装置１２０４と協動することができる。ＳＴＡＲ書き込み機能の図１０〜１２の各構成において実施例がさまざまであるのに加えて、以下でより詳しく記述されるフラッシング操作も様々である。単一バンクメモリにおける書き込みおよびフラッシングのためのフラッシュブロック管理方式の例が、その全体が本願明細書において参照により援用されている２００８年２月２２日に出願された同時係属中の米国特許出願第１２／０３６，０１４号（特許文献１１）に記載されている。

図１０の例では、ストレージアドレスマッピングアルゴリズムはストレージ装置１００４の各バンクのメモリ管理１００６に統合されることができ、物理メモリの第１のメガブロックが次のメガブロックに進む前にデータで完全に満たされるようにホスト１００２からのＬＢＡアドレスはマルチバンクフラッシュメモリ内の物理的ブロックに直接マッピングされる。その代わりに、図１１では、ストレージアドレス再マッピングメカニズムは、ストレージ装置１１０２上の、装置１１０２の各バンクのためのメモリマネージャ１１０４とは別のアプリケーションにおいて、実現され得る。図１１の実施例では、ホスト１００２からの各論理アドレスは、ホストからのデータを完全なメガブロックという項に書き込む技術を利用して、本願明細書においてストレージ論理ブロックアドレス（ストレージＬＢＡ）と称され、さらに本願明細書において装置論理ブロックアドレス（ＤＬＢＡ：device logical block address）とも称される第２の論理アドレスに再マッピングされ、その後、メモリマネージャ１１０４は、ＤＬＢＡ配列のもとで組織されたデータをそれぞれのバンクのための物理メモリのブロックに移す。ＤＬＢＡアドレス空間は、物理的メタブロックのものに等しい均一なサイズのＤＬＢＡブロックとして構造化される。

図１２の実施例は、ストレージアドレス再マッピングの機能をストレージ装置１２０４からホスト１２０２上のアプリケーションに移す。この実施例では、ＬＢＡアドレスをＤＬＢＡアドレスにマッピングする機能は図１１のものと類似し、主な違いは、変換が記憶装置１２０４ではなくてホスト１２０２上で行われることである。その後、ホスト１２０２は、ホストにおいて生成されたＤＬＢＡアドレス情報と、ＤＬＢＡアドレスに関連付けられたデータとの両方を記憶装置１２０４に送る。図１２の実施例のために論理アドレス空間８００を論理アドレスのブロックという項に分割して管理するために、ホストとメモリシステムとはフラッシュメモリ内の物理的ブロックのブロックサイズに関する情報を交換しなければならないかもしれない。論理ブロックのサイズは好ましくは物理的ブロックと同じサイズであり、この情報は、メモリシステムがホストと接続されるときに伝えられ得る。この通信は、パワーアップ時あるいはメモリシステムのホストへの接続時にハンドシェーク動作として行われるようにセットアップされてもよい。一実施形態では、ホストは、ブロックサイズおよびアライメント情報を要求して「識別ドライブ」クエリをメモリシステムに送ることができ、ブロックサイズは、その特定のメモリシステムのための個々の物理的ブロックのサイズであり、アライメント情報は、各物理的ブロックの一部を既に占めているかもしれないシステムデータのために物理的ブロックの先頭から、あるならば、どれだけのオフセットが考慮されなければならないかである。

識別ドライブコマンドは、レガシーＬＢＡインターフェイスコマンドセットにおいて予備のコードとして実現され得る。コマンドは、標準的通信インターフェイスにおいて予備のあるいは未割り当てのコマンドコードを介してホストからメモリシステムへ送られ得る。適切なインターフェイスの例は、ソリッドステートディスクのためのＡＴＡインターフェイス、あるいは、例えばＣＦまたはＳＤメモリカードに用いられるものなどのＡＴＡ関連インターフェイスを含む。メモリシステムがブロックサイズおよびオフセット情報の両方を提供できなければ、ホストはデフォルトのブロックサイズおよびオフセットを仮定することができる。メモリシステムが識別ドライブコマンドに対してオフセット情報なしでブロックサイズ情報だけで答えたならば、ホストはデフォルトのオフセットを仮定することができる。デフォルトのブロックサイズは、いくつかの標準的ブロックサイズのうちのどれであってもよく、好ましくは、現実の物理的ブロックサイズらしいものよりは大きくセットされる。各物理的ブロックが物理的ブロック内の第１のアドレスからホストからのデータを受け取り始めることができると仮定されるように、デフォルトのオフセットはゼロオフセットにセットされ得る。ホストがＳＳＤなどの所定の内部ドライブに結合されているならば、記憶装置の能力は既に知られていて前もってプログラムされているかもしれないので、ブロックサイズおよびオフセットを判定するこのステップを行う必要はないかもしれない。しかし、内部ドライブも交換されることがあるので、ホストは、記憶装置能力を常に確かめるように構成され得る。取り外し可能なメモリシステムのためには、ホストは、識別ドライブコマンドまたは類似のメカニズムを通してブロックサイズおよびオフセットについて常にたずねることができる。

マルチバンクメガブロック書き込みアルゴリズム
図１３に示されている一実施形態にしたがって、マルチバンクメモリにおいてホストデータ書き込み動作を管理する方法は、ホストファイルシステム１１０から、図８に関して前述したホストＬＢＡフォーマットでホストデータを受け取ることを含む（１３０２において）。ホストデータが受け取られると、データは、現在開いている書き込みメガブロック内の現在開いているメガページにホストデータをホストＬＢＡ順序に関わらずそれが受け取られた順に書き込むことによって、ストレージアドレスに再マッピングされる（１３０４において）。以下でより詳しく論じられるように、オリジナルのホストＬＢＡアドレスの、マルチバンクメモリ１０７内の現在のアドレスへのマッピングを追跡するために、ホストデータがマルチバンクメモリ１０７内のメガブロックに書き込まれるとストレージアドレステーブル（ＳＡＴ）が更新される（１３０６において）。各メガページ７０８は次のメガページへの書き込みの前に完全に書き込まれ、新しいメガブロック７０４は、好ましくは、現在の書き込みメガブロックが完全に書き込まれた後に初めてさらなるホストデータを受け取るために割り当てられる（１３０８、１３１０および１３１２において）。現在のメガブロック７０４内の次のメガページ７０８が利用可能であれば、その次のメガページ７０８の先頭に書き込みポインタがセットされ（１３１４において）、ホストデータはメガページの各メタページ内の連続するストレージアドレスに、１バンクずつ、受け取られた順に、再マッピングされ続ける。ホストデータ書き込みアルゴリズムがマルチバンクメモリシステム１０７全体に対してメガブロックレベルでメガページ順に実行されている間、メモリシステム１０２内のバンク１０７Ａ〜１０７Ｄの各々に対してフラッシングアルゴリズムが独立に適用される（１３１６において）。フラッシングアルゴリズムは、以下で詳しく説明されるように、各バンクの中に、ホストデータ書き込みのためまたは他の記憶ニーズのために、新しいメガブロックで使用する新しい白色ブロックを作る。前に単一の書き込みメガブロックについて論じられたけれども、バンク１０７Ａ〜１０７Ｄが適宜に分割されるならば複数の書き込みメガブロックが実現され得る。

ストレージアドレス再マッピングアルゴリズムの一実施例に従う各バンク１０７Ａ〜１０７Ｄの中でのデータの流れとブロック状態変化のパターンとが図１４に示されている。現在の書き込みブロック内の最後のページが有効なデータで満たされると、現在の書き込みブロックは赤色ブロックになり（ステップ１４０４において）、新しい書き込みブロックが次のメガブロック７０４の一部となるべく白色ブロックリストから割り当てられる（ステップ１４０４において）。現在の書き込みブロックが完全にプログラムされる前に現在の書き込みブロックの中のいくつかのページが使用済みとなったならば、現在の書き込みブロックは完全にプログラムされたときにピンク色ブロックへの直接遷移も行い得るということに留意するべきである。この遷移を、明瞭性を目的として、示されていないけれども、書き込みブロックからピンク色ブロックへの矢によって表すことができる。

図１４のデータフローの特定の例を再び参照すると、赤色ブロックの中の１つ以上のページが後にＬＢＡランの削除によって使用済みとなると、その赤色ブロックはピンク色ブロックになる（ステップ１４０６において）。バンクにおいてより多くの白色ブロックが必要であることをストレージアドレス再マッピングアルゴリズムが検出すると、アルゴリズムは、そのピンク色ブロックが白色ブロックになるようにピンク色ブロックから有効なデータを移すために、他のバンクにおいてアクティブであるかもしれない他のフラッシングアルゴリズムから独立して、バンクの中でフラッシング操作を開始する（ステップ１４０８において）。ピンク色ブロックをフラッシングするために、ピンク色ブロックの有効なデータは、再配置ブロックとして指定されている白色ブロックへ出現の順に順次再配置される（ステップ１４１０において）。その再配置ブロックは、いったん満たされれば、赤色ブロックになる（ステップ１４１２において）。前に書き込みブロックに関して言及したように、再配置ブロックは、完全にプログラムされるまでに既にその中の何ページかが使用済みとなっていたならば、ピンク色ブロックへの直接遷移を行うこともできる。この遷移を、明瞭性を目的として、示されていないけれども、図１４において再配置ブロックからピンク色ブロックへの矢によって表すことができる。

前に言及したように、ホストデータをメモリシステム１０２に書き込むとき、図１３のマルチバンク書き込みアルゴリズムは、メガブロックという項でアドレス空間を割り当ててメガブロック全体をメガページ順に満たす。したがって、図１４は単一のバンクを説明しているので、ホストからのデータは任意の所与のバンクにおいて書き込みブロックで、そのバンクの書き込みブロック内の１つのメタページが満たされるまで受け取られ、その後、そのバンク内の書き込みブロックにおいて他のメタページが利用できるかもしれないけれども、次のメタページ量のホストデータはメガページ内、すなわちマルチバンクフラッシュメモリ１０７内の次のバンクの書き込みブロック内の、次のメタページに書き込まれるということが理解されるべきである。このように、メモリの１つのバンク内にある所与の書き込みブロックは、ホストが提供するホストデータのＮメタページごとにホストデータの１メタページというパターンを受け取り、ここでＮはマルチバンクフラッシュメモリ１０７内のバンクの数である。この系統的ホストデータ書き込みシーケンスとは対照的に、前に言及したＳＡＴなどの、メモリシステム１０２の中で生成された情報、あるいはバンク内に新しい白色ブロックを作るためにフラッシング操作の一部分として再配置されるピンク色ブロックからの有効なデータは、バンク内のそれぞれの個々の書き込みブロックに完全に書き込まれる。

マルチバンクフラッシング操作
ストレージアドレス再マッピングアルゴリズムのある実施形態は、有効なデータの、ピンク色ブロック９０６から再配置ポインタとして知られている特別の書き込みポインタへの、本願明細書においてフラッシングとも称される再配置を行うことによって、白色ブロック９０４の作成を管理する。ストレージアドレス空間が前述したように範囲あるいはファイルサイズによって細分化されるならば、ストレージアドレスの各範囲はそれ自身の再配置ブロックおよび関連する再配置ポインタを持つことができる。図１５を参照すると、マルチバンクフラッシュメモリのためのフラッシング操作の実施形態は、各バンク１０７Ａ〜１０７Ｄのために別々にかつ独立して、充分な数の白色ブロックがあるかどうかを追跡することを含む（１５０２において）。この判定は、バンク内に現在存在する白色ブロックの総数に基づいて行うこともできるし、あるいはバンク内で白色ブロックが消費されつつある速度に基づいて行うこともできる。充分な数の白色ブロックがあるならば、フラッシング操作は不要であってバンクは次の書き込み操作を待つことができる（１５０４において）。白色ブロックの数が不十分であると判定されたならば、以下のようにバンクのために維持されているピンク色ブロックリストからバンク内のピンク色ブロックが選択される（１５０６において）。バンク内の現在の再配置ブロックが満杯でなければ、有効なデータが、選択されたピンク色ブロックからピンク色ブロック内での出現の順に再配置ブロック内の連続する位置へコピーされる（１５０８、１５１０において）。一実施形態では、再配置ブロックが完全にプログラムされているときにだけ、同じバンクから他の白色ブロックが次の再配置ブロックとして割り当てられる（１５１２において）。さらに、一実施形態では、選択されたピンク色ブロックからの有効なデータだけが、そのピンク色ブロックがコピーされていない有効なデータを依然として包含している間、再配置ブロックにコピーされる（１５１４において）。マルチバンクフラッシュメモリ１０７において、１つの特定のバンク内のピンク色ブロック９０６の中の有効なデータは同じバンク内の再配置ブロックにフラッシングされるだけであるように、フラッシング操作はそれぞれのバンク１０７Ａ〜１０７Ｄの中で独立に実行され、かつそれぞれのバンク１０７Ａ〜１０７Ｄの中に完全に包含されるということを、図１５に示されているフラッシング操作は表している。フラッシング操作は、通常、ピンク色ブロックを白色ブロックに変換するために、バックグラウンド操作として実行される。

ピンク色ブロック９０６は、その特性に応じてフラッシング操作のために選択される。一実施形態では、ピンク色ブロックのリストはマルチバンクフラッシュメモリ１０７内の各バンク１０７Ａ〜１０７Ｄのために独立に維持される。図９を再び参照すると、一実施例では、有効なデータを有するアドレスが少なければ、その特定のピンク色ブロックがフラッシングされるときに再配置を必要とするデータは少ないので、最少量の有効なデータ（すなわち、図９において最小数の陰影付きクラスタ）を有するピンク色ブロックが選択される。したがって、図９の例では、ピンク色ブロックＢのほうがより少数の有効なデータを伴うアドレスを有するので、ピンク色ブロックＡではなくてピンク色ブロックＢのほうが選択される。他の実施例では、フラッシング操作のために選択されるピンク色ブロックは、あるしきい値量より少ない有効なデータと関連付けられているピンク色ブロックのグループのうちのいずれであってもよい。そのしきい値は、ピンク色ブロックのセット全体に包含される有効なデータの平均量未満であってよい。そのしきい値量あるいはそれ未満の有効なデータのピンク色ブロックのサブセットを、ホストまたはメモリシステムがピンク色ブロックを選択できるリストにおいて維持することができる。例えば、しきい値要件を現在満たしているピンク色ブロックのうちの所定の数（例えば、１６）あるいはパーセンテージ（例えば、３０％）のピンク色ブロックの動的リストを維持することができ、そのリスト中の選択されるピンク色ブロックが絶対最少量の有効なデータを有するかどうかを考慮せずにそのリストからフラッシングのためにどのピンク色ブロックでも選択され得る。各バンクにおけるリストを形成する、メモリシステムまたはホストが選択するピンク色ブロックの数またはパーセンテージは、固定された値あるいはユーザにより選択可能な値であり得る。リストは、使用可能なピンク色ブロックからの絶対最少量の有効なデータを有するピンク色ブロックをランク付けされた順に表すピンク色ブロックのグループを含むこともできるし、あるいは単にしきい値要件の範囲内にあるピンク色ブロックを含むこともできる。

その代わりに、あるいは組み合わされて、ピンク色ブロックの選択は、特定のピンク色ブロック９０６にさらなる使用済データを蓄積する計算された確率に基づいて行われてもよい。ピンク色ブロック９０６にさらなる使用済データが蓄積される確率は、メモリにおいて最も長く存在し続けているデータは最も削除されそうもないという仮定に基づくことができる。再配置ブロックであったピンク色ブロック９０６は、新しいホストデータを有する書き込みブロックであったピンク色ブロック９０６より古くから存在し続けているデータを含み得る。フラッシングのためのピンク色ブロック９０６の選択プロセスは、始めに、近ごろ再配置ブロックであったピンク色ブロック９０６を標的にし得る。それは、それらがさらにデータを削除される見込みがより低く、したがってより少量の使用済データの追加が期待され得るからである。以前は書き込みブロックであったピンク色ブロック９０６は、より新しいデータが削除される見込みがより高く、したがってより多くの使用済データを作る見込みがより高いという仮定に基づいて後にフラッシングのために選択される。

メガブロック書き込みプロセスのより具体的な例が図１６〜１７に示されている。この例では、図１１のシステム構成が使用されると仮定され、ホストＬＢＡアドレスは、メモリシステム１０２内のコントローラ１０８により実行されるアプリケーションにおいてＤＬＢＡアドレスとも称される中間ストレージＬＢＡアドレスに変換される。図１６に示されているように、６個のメタページ（Ｐ１〜Ｐ６）を各々有するメタブロック１６０２を有する４バンクメモリ内の開いている書き込みメガブロック１６００は、図１７に示されているＬＢＡラン１７０２のためのＬＢＡアドレスと関連付けられる。マルチバンクメモリ１０７への書き込みの順序は、第１の開いているメタページ（バンク２内のＰ２）から始まってメガページの残りに沿って左から右へ順に続く（バンク３内のＰ２、その次にバンク４内のＰ２）。コントローラは、ＬＢＡラン１７０２の入ってくるＬＢＡアドレスが、それらが受け取られた順に、各メタページに関連付けられている連続するＤＬＢＡアドレスに再マッピングされて、次のメタページへ移る前にメタページ全体がプログラムされるように、ＬＢＡアドレスをメガページ内のそれぞれのメタページへルーティングする。ＬＢＡラン１７０２は、次のメガページと関連付けられているＤＬＢＡアドレスに再マッピングされ続ける（連続して、バンク１〜４の各々のメタページＰ３）。その後、ＬＢＡラン１７０２の最後の部分は、バンク１およびバンク２内のメタページＰ４と関連付けられているＤＬＢＡアドレスに連続的に再マッピングされる。

コントローラ１０８により管理される書き込みアルゴリズムは、メガブロック１６００内の次のメガページへ進む前に１メガページ分のＬＢＡアドレス指定されたホストデータをバンクの各々に順次分配することによってメガブロック１６００に順に書き込むけれども、単一のラン１７０２のための各バンク内の不連続的ＬＢＡアドレスの集合は、各バンクによって、この例では図１６〜１７においてＤＬＢＡランＡ１〜Ａ４として特定されるＤＬＢＡランとして管理される。ＬＢＡアドレスから各バンク内のＤＬＢＡアドレスへのマッピングは、メモリにおいて維持されるマルチバンクフラッシュメモリ１０７のためのストレージアドレステーブル（ＳＡＴ）１７０４において追跡される。図１７に示されているＳＡＴ１７０４のバージョンは、有効なデータを包含する各ＬＢＡランを関連するＤＬＢＡランにマッピングする。ＳＡＴ１７０４内のＬＢＡエントリ１７０６は、ラン内の第１のＬＢＡアドレスと、ランの長さと、ＬＢＡラン１７０２にマッピングされた第１のＤＬＢＡラン（ＤＬＢＡランＡ１）のＤＬＢＡアドレスおよびバンク識別子とを含む。対応するＤＬＢＡエントリ１７０８は、ＤＬＢＡランの第１のＤＬＢＡアドレスおよびバンク番号と、第１のＤＬＢＡアドレスがマッピングされるＬＢＡラン１７０２内のＬＢＡアドレスオフセットとを有する第１のＤＬＢＡエントリ１７１０を含み、それは、第１のＤＬＢＡエントリ１７１０の場合にはゼロであり、所与のＬＢＡラン１７０２のためのその後の全てのＤＬＢＡエントリでは非ゼロ値である。

ＬＢＡラン１７０２と関連付けられたデータがＤＬＢＡアドレスに再マッピングされて、ＤＬＢＡアドレスと関連付けられているメガブロック１６００内の物理アドレス位置に書き込まれた後、１つ以上のその後のＬＢＡランが再マッピングされてメガブロック１６００内の残りの未書き込み容量（バンク３および４内のＰ４と整列しているメガページの残りと、Ｐ５およびＰ６とそれぞれ整列しているメガページ）に書き込まれる。メガブロック１６００などのメガブロックが完全にプログラムされた後、コントローラはメガブロックを最早追跡しなくて、メガブロック１６００内の各ブロック１６０２〜１６０８はその後それらのそれぞれのバンクにおいて実行される独立のフラッシング操作によって管理される。オリジナルのメガブロック１６００のブロック１６０２〜１６０８は、それぞれ使用済データの蓄積に起因してピンク色ブロックになると、関連していない再配置ブロックへ独立にフラッシングされ得る。図１８は、ＤＬＢＡランＡ１〜Ａ４がどのようにそれぞれのバンク内での独立のフラッシング操作によって新しいブロック１８０２〜１８０８へ移され得るかを示す。ＤＬＢＡランＡ１〜Ａ４と関連付けられているデータの残存は、当然、そのデータが有効なデータでブロック１６００内の他のデータが使用済みでそれぞれのフラッシング操作を誘発したということを仮定している。さらに、ブロック１８０２〜１８０８は、参照を容易にすると共に図１６のメガブロック内でのＤＬＢＡランＡ１〜Ａ４のそれぞれの元の相対ページアライメントに関してのあり得る移動を説明するために、図１８において、互いに隣接して示されているけれども、それぞれのフラッシング操作後ブロック１８０２〜１８０８は各バンクにおいて異なる物理的または相対的な位置に配置されそうである。

メモリシステム上のコントローラ１０８またはホスト１００上のプロセッサ１０９によって実行されるアプリケーションによって論理−論理、ＬＢＡ−ＤＬＢＡ変換が実行される図１１および１２に示されているストレージアドレス再マッピングの実施例を参照し、図１４の状態図に従うアドレス操作の例が図８〜９および１９〜２０を参照して以下で論じられる。システムは図１５によって表されるストレージアドレス再マッピングアルゴリズムにしたがって動作してきたと仮定すると、ＬＢＡアドレス空間（図８）では、空きクラスタ８０４は本質的にランダムな位置に分散されている。所与のバンクのためのＤＬＢＡアドレス空間では（図９）、２つの白色ブロック９０４が使用可能であり、異なる数の使用済（空き）クラスタ８０４を有する３つのピンク色ブロック９０６がある。

ホストは、ストレージ装置に書き込むべきデータを次に得ると、使用可能な任意の場所のＬＢＡアドレス空間を割り当てる。図１９は、ストレージアドレス再マッピングアルゴリズムが、どのように図９の白色ブロック９０４などの使用可能な白色ブロックのうちの１つをより大きなメガブロックの一部である書き込みブロック１９０４とするべく割り当てるかを示すと共に、各ＬＢＡアドレスが書き込みブロック１９０４内の使用可能なＤＬＢＡ空間内の連続的クラスタにどのようにマッピングされるかを示す。ＤＬＢＡ空間内の書き込みブロック１９０４は、ＬＢＡアドレス位置に関わらずに、ＬＢＡアドレスが書き込まれた順に、前に論じられたメガブロック書き込みパターンにしたがって書き込まれる。バンクに適用されるストレージアドレス再マッピングアルゴリズムは、ＬＢＡアドレス番号順に関わらず、ＬＢＡアドレスが受け取られた時間順に書き込みブロック１９０４内のＤＬＢＡアドレスを割り当てる。データは、書き込みブロックにおいて１つ以上のＤＬＢＡランをなして書き込まれる。ＤＬＢＡランは、同じＬＢＡラン内の連続するＬＢＡアドレスにマッピングされた連続するＤＬＢＡアドレスのセットである。ＤＬＢＡランは、ＤＬＢＡアドレス空間１９０２においてブロック境界（これはバンク境界である）で終わらなければならない。書き込みブロック１９０４が満杯になると、白色ブロック９０４が次の書き込みブロック１９０４として割り当てられる。

各バンクにおいて、ＤＬＢＡブロックはフラッシュメモリ１０７の物理アドレス空間内のブロック１９０６で整列し、したがってＤＬＢＡブロックサイズと物理アドレスブロックサイズとは同じである。さらに、ＤＬＢＡ書き込みブロック１９０４におけるアドレスの配列は、物理アドレス空間における対応する更新ブロック１９０６の配列と同じである。この対応により、一般にガーベッジコレクションと称される別のデータ統合は物理的更新ブロックにおいて決して必要とされない。一般的なガーベッジコレクション操作では、論理アドレスのブロックは、論理ブロックにおいてＬＢＡアドレスの特定の範囲を維持するために一般的に常に再組み立てされ、それは物理的ブロックにおいても反映される。より具体的には、一般的ガーベッジコレクション操作を利用するメモリシステムが特定の物理的ブロック内のセクタに対応する情報の更新されたセクタを受け取ると、メモリシステムは、その更新された１つまたは複数のセクタを受け取るために物理メモリ内の更新ブロックを割り当て、その後残っている有効なデータの全部を元の物理的ブロックから更新ブロックの残りの中へ統合する。このように、標準的ガーベッジコレクションは、特定のＬＢＡアドレス範囲のためのデータのブロックを、その特定のアドレス範囲に対応するデータが常に共通の物理的ブロックの中に統合されるように、永続させる。本願明細書において論じられるフラッシング操作は、同じアドレス範囲内のデータの統合を必要としない。代わりに、フラッシング操作は、種々の物理的ブロックからのデータの集合であり得るデータの新しいブロックを作るためにアドレスマッピングを実行し、データの特定のＬＢＡアドレス範囲が意図的に統合されることはない。

前述したように、充分な供給量の白色ブロックが確実に利用可能であるように、ストレージアドレス再マッピングアルゴリズムは各バンク１０７Ａ〜１０７Ｄにおいて独立に動作する。ストレージアドレス再マッピングアルゴリズムは、データをピンク色ブロックから再配置ブロック１９０８として知られる特別の書き込みブロックへフラッシングすることによって白色ブロックの作成を管理する（図１９）。フラッシングされるべく現在選択されているピンク色ブロックはフラッシングブロックと称される。

次に、図１９〜２０を順に参照すると、所与のバンクのためのブロックフラッシングプロセスの図が示されている。図１１の実施例において各バンク１０７Ａ〜１０７Ｄのために独立にコントローラ１０８によって実行されるストレージアドレス再マッピングアルゴリズムは、白色ブロックを再配置ブロック１９０８として指定し、これに、さらなる白色ブロックを作成するために同じバンク内の選択されたピンク色ブロックからデータがフラッシングされる。図１９に示されているように、フラッシングブロック（図９のピンク色ブロックＡ）内の、赤色データとも称される有効なデータは、フラッシングブロックを白色ブロック９０４に変換するために、再配置ブロック１９０８内の連続するアドレスへ再配置される。物理アドレス空間１９１０内の対応する更新ブロック１９０６も、フラッシングされるデータを受け取るために割り当てられる。ホストから受け取られる新しいデータのために使用される更新ブロック１９０６の場合と同じく、フラッシングされるデータを受け取るための更新ブロック１９０６は、フラッシング操作がＤＬＢＡアドレス空間１９０２における統合を既に成し遂げているので、有効なデータを統合するためのガーベッジコレクション操作を決して必要としない。

図２０に示されているように、残りのピンク色ブロックから次のフラッシングブロック（図１９のピンク色ブロックＢ）が特定される。最も少ない赤色データを有するピンク色ブロックが再びフラッシングブロックとして指定され、ピンク色ブロックの赤色データ（有効なデータ）は、開いている再配置ブロック内の連続する位置へ転送される。更新ブロック１９０６における物理アドレスの並行する割り当ても行われる。再び、再配置ブロック１９０８にマッピングされた物理的更新ブロック１９０６において、データ統合は必要とされない。ピンク色ブロックに対するフラッシング操作は、書き込みブロックとして指定されている白色ブロックの消費を補うのに充分な速度で白色ブロックを作るためにバックグラウンド操作として実行される。図８〜９および１９〜２０の例は、ホストからの新しいデータのためおよびピンク色ブロックから再配置されるデータのために、物理アドレス空間内のそれぞれの別々の更新ブロックと共に、書き込みブロックおよび再配置ブロックがどのように別々に維持され得るかを示している。現在のメガブロックが完全にプログラムされたときに初めてメガブロックの一部として動作する新しい書き込みブロックを割り当ててホストから受け取られた新しいデータを関連付けるプロセスと同様に、新しい再配置ブロックは、好ましくは、前の再配置ブロックが完全にプログラムされた後に初めて割り当てられる。新しい再配置ブロックは、好ましくは、割り当て時に、未書き込み容量を包含するだけである、すなわち、いつでも消去できる使用済データと関連付けられているだけであるか、あるいは既に消去されていて有効なデータを全く包含していないかである。

前述した実施形態では、ホストからの新しいデータはホストからの他の新しいデータを受け取るだけの書き込みブロックと関連付けられ、フラッシング操作でピンク色ブロックからフラッシングされる有効なデータは、特定のバンク内の、そのバンクのための１つ以上のピンク色ブロックからの有効なデータを包含するだけの再配置ブロックの中へ移される。前述したように、他の実施形態でフラッシングされるピンク色ブロックの選択を行うことができ、その場合には、現在のピンク色ブロックについての平均量などのしきい値を下回る量の赤色データと関連付けられているピンク色ブロックのリストから任意のピンク色ブロックを選択することができ、あるいはそのピンク色ブロックは、使用可能なピンク色ブロックのうちの（ピンク色ブロックと関連付けられている有効データの量に基づく）特定の順位を有するピンク色ブロックのうちのどれであってもよい。

フラッシング操作は「熱い」データが使用済みにされたブロックから割合に「冷たい」データを、同様に割合に「冷たい」データを包含する再配置ブロックへ再配置する。これは、割合に「熱い」ブロックおよび割合に「冷たい」ブロックの別々の集団を作るという効果を有する。フラッシングされるべきブロックは、常に、最少量のデータを包含する「熱い」ブロックとして選択される。「熱い」ブロックの集団を作れば、再配置されなければならないデータの量が減ることにより、メモリのストレス要因が減少する。

一実施形態では、フラッシングブロックとして選択されるピンク色ブロックは、内容が最もまばらなピンク色ブロック、すなわち、最少量の有効なデータを包含するピンク色ブロックであってよくて、ホストにより実行される特定の書き込みおよび消去操作に応答して選択されるのではない。このようにして行われるピンク色ブロックのフラッシングブロックとしての選択は、最小限の有効データ再配置でブロックフラッシング操作を行うことを可能にする。それは、そのように選択されるどのピンク色ブロックも、ホストによるファイルの削除に起因して最大限の数の未割り当てデータアドレスを蓄積しているからである。

ピンク色ブロック選択プロセスの一例は、最低数の有効ページまたはクラスタを有する５％のピンク色ブロックのうちの任意のピンク色ブロックを選択することである。バックグラウンド処理で、最低のページまたはクラスタ総数値を有する１６個のピンク色ブロックのリストが作られる。ピンク色ブロック特定プロセスは、「Ｐ」個のスケジュールされたブロックフラッシング操作により費やされる時間のうちに１サイクルを完了することができる。フラッシングブロック特定プロセスにおける１サイクルが図２１に示されている。白色、ピンクおよび他のタイプのＤＬＢＡアドレスブロックについてのブロックアドレスのリストを包含するブロック情報テーブル（ＢＩＴ）が、以下でより詳しく記述されるように、各バンク１０７Ａ〜１０７Ｂのためにストレージアドレス再マッピング機能によって別々に維持され、前のプロセスサイクルの間に特定されたブロックのセットの後にＱ個のピンク色ブロックの次のセットを特定するために読み出される（ステップ２１０２において）。各バンクのために独立に、装置初期化後の第１のプロセスサイクルでピンク色ブロックの第１のセットが特定されるべきである。フラッシングブロックの利用可能性を保証するために、Ｑの値はＰのものより大であるべきである。一実施例では、Ｑの値は８でＰは４であり得る。有効ページ総数値はセット中のピンク色ブロックの各々のためにゼロにセットされる（ステップ２１０４において）。セット中のどのピンクブロックの中に位置する有効データページをも特定するために、ＬＢＡおよびＤＬＢＡの関係を追跡するために維持されるストレージアドレステーブル（ＳＡＴ）ページエントリが一度に１つずつスキャンされる（ステップ２１０６において）。ストレージアドレステーブルは以下でより詳しく記述される。有効ページ総数値は、それに応じてインクリメントされる。全てのＳＡＴページがスキャンされた後、セット中のピンク色ブロックの各々についての有効ページ総数値は、低有効ページ総数値を求めてリスト中のピンク色ブロックについてのものと対照して評価され、必要ならばリスト中のブロックはセットからのブロックにより取って代わられる（ステップ２１０８において）。ブロックフラッシング操作の完了後、次のブロックフラッシング操作のために次のブロックが選択されるべきである。これは、リスト中の最低有効ページ総数値を有するブロックであるべきである。

図１９〜２０に関して記述したような、特定のバンク１０７Ａ〜１０７Ｄにおけるブロックフラッシング操作を開始する前に、再配置されなければならない有効なＤＬＢＡランの位置を判定するために、選択されたブロックはマッピングされなければならない。これは、ブロックから読み出されるデータの選択されたページのヘッダ内のＬＢＡアドレスと、これらのＬＢＡアドレスについてのＳＡＴエントリとを使用するサーチアルゴリズムによって成し遂げられる。サーチアルゴリズムは、それ自身が徐々に構築する既知の有効なおよび使用済みとなったＤＬＢＡランのマップを使用する。有効なＤＬＢＡランは、ＳＡＴエントリがブロックにおけるその存在を明示していると、ブロックマップに加えられる。使用済みとなったＤＬＢＡランは、マッピングされるブロック内のデータページヘッダ内のＬＢＡの範囲についてのＳＡＴエントリが他のブロックにおける有効なＤＬＢＡの存在を明示しているとき、ブロックマップに加えられる。サーチプロセスは、ブロック内の全てのＤＬＢＡアドレスが有効または使用済として明白にマッピングされるまで続く。

ブロックフラッシング操作では、前述したブロックマッピングプロセスで特定された有効なＤＬＢＡランの中の全てのページが、選択されたピンク色ブロックから同じバンク内の再配置ブロック内の再配置ポインタへ再配置される。再配置されたＤＬＢＡについてのエントリがＳＡＴリストにおいて記録される。有効なおよび使用済みとなったＤＬＢＡランのためのサーチは、図１１に示されている構成の場合にはメモリシステム１０２のコントローラ１０８によって実行され、ブロックＤＬＢＡマップはコントローラと関連付けられたＲＡＭに格納され得る。図１２の構成では、ホストシステム１００に存するＣＰＵ１０９がサーチを実行し、その結果として得られたブロックＤＬＢＡ情報をホストシステムＣＰＵと関連付けられているＲＡＭに格納することができる。

マルチバンクメモリ構成のためのストレージアドレス再マッピングアルゴリズムは、特定のバンク内の白色ブロックの数が所定しきい値未満にまで減ると、書き込みブロックにおけるホストデータの書き込みにより白色ブロック容量が消費されるのと同じ速度でデータ書き込みのために割り当てられ得る使用可能な白色ブロック容量が作られることを保証するのに充分な速度でそのバンクにおいてピンク色ブロックに対するフラッシング操作が行われなければならないという原理にしたがって動作する。ホストからのデータを書き込むことによって消費される書き込みブロック内のページの数は、ブロックフラッシング操作によって回復される使用済ページの数と釣り合わされなければならない。ブロックフラッシング操作の完了後、前述したように、ＢＩＴおよびＳＡＴから特定のエントリを読み出すことによって、次のブロックフラッシング操作のために選択されたピンク色ブロック内の使用済データのページの数が判定される。次のブロックフラッシング操作は、データのこの数の有効ページを書き込みブロックに書き込んだ直後に始まるようにスケジュールされ得る。さらに、フラッシング操作を開始するためのしきい値は各バンクのために異なっていてもよい。例えば、ある１つのバンク内のピンク色ブロックの有効データの平均量に基づいてしきい値がトリガされれば全てのバンクにおいてほぼ同じ速度で白色ブロックが作成され得るように、フラッシングのためのしきい値はバンク内で再配置されるべきデータの量に基づいて適応的であり得る。

ストレージアドレステーブル
前述したストレージアドレス再マッピングを実行するために、図１７に関して一般的に記述したものなどのストレージアドレステーブル（ＳＡＴ）１７０４が、ストレージアドレス空間内のデータの位置を追跡するために使用される。ＳＡＴ内の情報は、順次更新の一部として完全なフラッシュメタブロックにも書き込まれる。したがって、一実施例では、ＳＡＴ情報は、ホストから受け取られるデータのために使用される書き込みブロックとは別であり、かつフラッシング操作に使用される再配置ブロックとも異なる書き込みブロックに書き込まれる。他の実施例では、ＳＡＴ情報は、ブロック、例えば、非ＳＡＴ情報により占められるＭＬＣフラッシュパーティションではないバイナリフラッシュパーティション内のブロックの異なるグループに格納され得る。あるいは、ＳＡＴデータと非ＳＡＴデータとは同じタイプのフラッシュブロックに、ブロックを単位として分離されて、格納され得る。さらに他の実施形態では、ＳＡＴデータと非ＳＡＴデータとは同じブロック内で混ぜ合わされ得る。ＳＡＴ１７０４はマルチバンクメモリ１０７内の全てのバンク１０７Ａ〜１０７Ｄのための単一のテーブルであることができ、他の実施形態では各バンクは、その特定のバンク内の情報をマッピングするだけの独立のＳＡＴを維持することができる。

ＳＡＴは、図１０〜１２の実施形態の各々に関連する。さらに、以下の論議はホストＬＢＡから図１１〜１２のホストおよびメモリシステム構成に関連するＤＬＢＡと呼ばれる第２のＬＢＡ空間（ストレージＬＢＡとも称される）への再マッピングに焦点を当てるけれども、その同じＳＡＴ手法が、ホストＬＢＡアドレスに関連付けられたデータが中間の論理対論理変換を伴わずに物理的ブロックに直接マッピングされる図１０の実施形態に適用可能である。ＳＡＴ情報は、論じられる実施形態に関わらず、好ましくは記憶装置内のフラッシュメモリに格納される。ホストＬＢＡからＤＬＢＡへの再マッピングがホスト１２０２において行われる図１２の実施形態では、ＳＡＴ情報はメモリシステム１２０４のフラッシュメモリに格納されるべく送られる。ストレージアドレス再マッピングアルゴリズムがメモリシステムの中のメモリマネージャにおいて実行される図１０の実施形態では、ＤＬＢＡという用語は、図１１〜１２の実施形態で使用される第２の論理アドレス空間ではなくてフラッシュメモリ１０７内の物理アドレスを指し、ＤＬＢＡアドレスのブロックは物理メモリ内のメタブロックを表す。

ストレージアドレステーブル（ＳＡＴ）は、ホストファイルシステムによって割り当てられたＬＢＡアドレスをＤＬＢＡアドレスに関連付ける相関情報を含む。より具体的には、ＳＡＴは、ホストファイルシステムによって有効なデータに割り当てられたＬＢＡアドレス空間の中のアドレスの全ランの各々と、ストレージアドレス再マッピングアルゴリズムによって作成されたＤＬＢＡアドレス空間の中のアドレスの１つ以上のランとの間のマッピングを記録するために使用される。前述したように、システムアドレス空間の単位はＬＢＡであり、ＬＢＡランは、ホストファイルシステムによって有効なデータに現在割り当てられているＬＢＡアドレスの連続的セットである。ＬＢＡランはしばしば未割り当てＬＢＡアドレスと接するけれども、ＳＡＴデータ構造により必要とされるならばＬＢＡランは複数のより小さなＬＢＡランとして管理され得る。装置アドレス空間の単位はＤＬＢＡであり、ＤＬＢＡランは、同じＬＢＡランの中の連続するＬＢＡアドレスにマッピングされているＤＬＢＡアドレスの連続的セットである。ＤＬＢＡランは、ＤＬＢＡアドレス空間の中のブロック境界で終わらせられる。各ＬＢＡランは、ＳＡＴによって１つ以上のＤＬＢＡランにマッピングされる。ＬＢＡランの長さは、それがマッピングされているＤＬＢＡランの累積長さに等しい。

ＬＢＡランのためのＳＡＴエントリは、それがマッピングされている第１のＤＬＢＡランと、ＤＬＢＡランが置かれているバンクとのためのエントリへのリンクを包含する。それがさらにマッピングされ得るその後のＤＬＢＡランは、このランに直接続く連続するエントリである。ＤＬＢＡランは、ＬＢＡランの絶対ＬＢＡアドレスへのではなくて、それがマッピングされているＬＢＡランの中のもののオフセットアドレスへの逆方向リンクを包含する。個々のＬＢＡアドレスは、ＬＢＡランの中でのＬＢＡオフセットとして明示され得る。ＳＡＴは、ＬＢＡランにマッピングされている各ＤＬＢＡランの先頭に対応するＬＢＡオフセットを記録する。したがって、個々のＬＢＡアドレスに対応する個々のＤＬＢＡアドレスは、ＤＬＢＡランの中のＤＬＢＡオフセットとして特定され得る。ＳＡＴ内のＬＢＡランは有効なデータのランだけのためのものであり得るけれども、他の実施例では、ＳＡＴは有効なデータおよび使用済みとなったデータの両方のためのＬＢＡランを記憶するようにも構成されてもよい。

ＳＡＴは、ＳＡＴブロックとして知られるＬＢＡアドレスのブロックの中に実現され得る。ＳＡＴは、所定の最大数のＳＡＴブロックを含み、所定の最大数の有効なＳＡＴページを包含する。したがって、ＳＡＴは、指定された最大数のＳＡＴブロックについて、それ自身が索引付けできる最大数のＤＬＢＡランを有する。一実施形態では、最大数のＳＡＴブロックが定義されるけれども、ＳＡＴのエントリの数はホストにより割り当てられたＬＢＡの断片化に順応するので、ＳＡＴは最大数まで自動的にスケーラブルな可変サイズのテーブルである。したがって、ホストが非常に断片化したＬＢＡを割り当てれば、ＳＡＴは、断片化の程度がより低いＬＢＡのグループをデータに割り当てる場合より多いエントリを含む。したがって、ホストＬＢＡの断片化の程度がより低くなれば、ＳＡＴのサイズは小さくなる。断片化の程度が低ければマッピングするべき別々のランが少なくなり、別々のランが少なければＳＡＴのエントリは少なくなる。それは、ＳＡＴは、固定された数の論理アドレスを厳格に追跡し更新するのではなくてエントリにおいてホストＬＢＡアドレスのランを１つ以上のＤＬＢＡランにマッピングするからである。

図１７のＳＡＴのＬＢＡラン対ＤＬＢＡランのマッピング構成に起因して、ホストＬＢＡアドレスの１つのランを２つ以上のＤＬＢＡランにマッピングすることができ、ここでホストＬＢＡランは有効なデータに割り当てられている連続する論理アドレスのセットであり、ＤＬＢＡ（あるいはストレージＬＢＡ）ランは同じメタブロックの中にあって同じホストＬＢＡランにマッピングされているＤＬＢＡアドレスの連続的セットである。ＳＡＴ索引付けおよびマッピング構造の階層が図２２に示されている。ＬＢＡラン２２０４および対応するＤＬＢＡラン２２０２が示されている。ＬＢＡ対ＤＬＢＡマッピング情報はＳＡＴページ２２０６に包含されている。ＬＢＡ対ＳＡＴページ索引付け情報はＳＡＴ索引ページ２２０８に包含され、マスタページ索引２２１０は、図１２の実施例ではホストプロセッサと関連するＲＡＭに、図１０〜１１の実施例ではコントローラ１０８と関連するＲＡＭ２１２にキャッシュされる。

ＳＡＴは通常複数のＳＡＴブロックを含むけれども、ＳＡＴ情報はＳＡＴ書き込みブロックと現在指し示されている単一のブロックに書き込まれ得るだけである。他の全てのＳＡＴブロックは完全に書き込まれていて、有効なページおよび使用済ページの組み合わせを包含し得る。ＳＡＴページは、ホストＬＢＡアドレス空間の１つの可変範囲内の全てのＬＢＡランのためのエントリを、それらがマッピングされている装置アドレス空間内のランのためのエントリと共に包含する。多数のＳＡＴページが存在し得る。ＳＡＴ索引ページは、ホストＬＢＡアドレス空間のより大きな範囲の中の全ての有効なＳＡＴページの位置への索引を包含する。少数のＳＡＴ索引ページが存在し、それは通例１である。ＳＡＴ内の情報は、単一のＳＡＴ書き込みブロック内の次の使用可能な位置に更新済みページを再書き込みしてページの前のバージョンを使用済みとして扱うことによって改変される。したがって、ＳＡＴ内に多数の無効なページが存在し得る。ＳＡＴブロックは、ＳＡＴページがメガブロックにではなくて１つのバンク内の個々のブロックに書き込まれるということと、ピンク色ＳＡＴブロックからの有効なデータが別の再配置ブロックではなくて現在のＳＡＴ書き込みブロックにコピーされるということとを除いてホストデータについて前述したものと類似する、ページを書き込みブロックをフラッシングするためのアルゴリズムによって、管理される。

各ＳＡＴブロックは、ＳＡＴ情報の格納に専用されるＤＬＢＡアドレスのブロックである。ＳＡＴブロックはテーブルページに分割され、それらにＳＡＴページ２２０６またはＳＡＴ索引ページ２２０８を書き込むことができる。ＳＡＴブロックは、有効なＳＡＴページ２２０６、有効なＳＡＴ索引ページ２２０８および使用済ページの任意の組み合わせを包含することができる。図２３を参照すると、サンプルであるＳＡＴ書き込みブロック２３００が示されている。データは、ＳＡＴ書き込みブロック２３００内の、インクリメントなＳＡＴ書き込みポインタ２３０２によって定められる連続する位置に書き込まれる。データは、ＳＡＴ書き込みブロック２３００として指定されている単一のＳＡＴブロックに書き込まれ得るだけである。前述したホストデータ書き込みブロックの場合と同様に、ＳＡＴ書き込みブロック２３００が完全に書き込まれて初めて１つの白色ブロックが新しいＳＡＴ書き込みブロック２３００として割り当てられる。ＳＡＴページ位置は、そのＳＡＴブロックの中でのもののシーケンス番号によってアドレス指定される。全てのバンクのために単一のＳＡＴが維持される１つの実施形態では、コントローラは、新しいＳＡＴ白色ブロックを割り当てるためにどのバンク１０７Ａ〜１０７Ｄを使用するかを交互に選択することができる。このようにして、ＳＡＴを格納するために１つのバンクを不均衡に使用することを避けることができる。

ＳＡＴページ
ＳＡＴページ２２０６は、ＳＡＴにおけるマッピング情報の最小更新可能単位である。更新済みＳＡＴページ２２０６はＳＡＴ書き込みポインタ２３０２により定められる位置に書き込まれる。ＳＡＴページ２２０６は、インクリメントするＬＢＡアドレスを有するＬＢＡランのセットについてのマッピング情報を包含するけれども、引き続くＬＢＡランのアドレスは連続していなくてもよい。ＳＡＴページ２２０６内のＬＢＡアドレスの範囲は他のどのＳＡＴページ２２０６内のＬＢＡアドレスの範囲とも重なり合わない。ＳＡＴページ２２０６は、ＳＡＴブロックの完全なセットの全体にわたって無制限に分散され得る。ＬＢＡアドレスの任意の範囲についてのＳＡＴページ２２０６が任意のＳＡＴブロック内にあってよい。ＳＡＴページ２２０６は、索引バッファフィールド２３０４と、ＬＢＡフィールド２３０６と、ＤＬＢＡフィールド２３０８と制御ポインタ２３１０とを含むことができる。パラメータバックアップエントリも、揮発性ＲＡＭに格納されているいくつかのパラメータの値を包含する。

ＳＡＴページ２２０６内のＬＢＡフィールド２３０６は、ＬＢＡアドレスのある範囲の中で、データ格納のために割り当てられている連続するＬＢＡアドレスのランのためのエントリを包含する。ＳＡＴページ２２０６がまたがるＬＢＡアドレスの範囲は、他のどのＳＡＴページ２２０６がまたがるＬＢＡエントリの範囲とも重なり合わない。ＬＢＡフィールドは、可変長のフィールドであって、可変数のＬＢＡエントリを包含する。ＬＢＡフィールド２３０６の中に、ＳＡＴページ２２０６により索引付けされるＬＢＡアドレスの範囲の中のどのＬＢＡランのためにもＬＢＡエントリ２３１２が存在する。ＬＢＡランは、１つ以上のＤＬＢＡランにマッピングされる。図２４に示されているように、ＬＢＡエントリ２３１２は、次の情報、すなわち、ランの中の第１のＬＢＡ２４０２と、セクタ数で表したＬＢＡランの長さ２４０４と、ＬＢＡランがマッピングされている第１のＤＬＢＡランの、同じＳＡＴページ２２０６内のＤＬＢＡフィールドの中での、ＤＬＢＡエントリ番号およびバンク番号２４０６とを含む。

ＳＡＴページ２２０６の中のＤＬＢＡフィールド２３０８は、同じＳＡＴページ２２０６内のＬＢＡフィールドの中のＬＢＡランにマッピングされたＤＬＢＡアドレスの全てのランのためのエントリを包含する。ＤＬＢＡフィールド２３０８は、可変長であって、可変数のＤＬＢＡエントリ２３１４を包含する。ＤＬＢＡフィールド２３０８の中で、同じＳＡＴページ２２０６のＬＢＡフィールド２３０６の中のＬＢＡランにマッピングされているどのＤＬＢＡランについてもＤＬＢＡエントリ２３１４が存在する。各ＤＬＢＡエントリ２３１４は、図２５に示されているように、次の情報、すなわち、ラン内の第１のＤＬＢＡアドレス２５０２と、第１のＤＬＢＡアドレスがマッピングされているＬＢＡランにおけるＬＢＡオフセット２５０４とを含む。全てのＳＡＴページ２２０６の各々の一部分として書き込まれるけれども最も最近に書き込まれたＳＡＴページ２２０６においてのみ有効なままであるＳＡＴページ／索引バッファフィールドは、ＳＡＴ索引エントリ２３１６を包含する。マルチバンクメモリ１０７のために単一のＳＡＴが維持される実施形態において、ラン内の第１のＤＬＢＡのエントリ２５０２にバンク番号も含まれる。各バンクにおいて別々のＳＡＴが維持される代わりの実施形態では、出発ＤＬＢＡアドレスが既にバンク特有であるから、ＤＬＢＡエントリ２３１４においてバンク情報は不要である。

図２６に示されているＳＡＴ索引エントリ２３１６は、関連するＳＡＴ索引ページ２２０８内に有効なエントリを現在持っていないＳＡＴ内のどのＳＡＴページ２２０６のためにも存在する。ＳＡＴ索引エントリは、ＳＡＴページ２２０６が書き込まれるたびに作成または更新され、関連するＳＡＴ索引ページ２２０８が更新されると削除される。それは、ＳＡＴページ２２０６により索引付けされる第１のＬＢＡ２６０２と、ＳＡＴページ２２０６により索引付けされる最後のＬＢＡ２６０４と、ＳＡＴページ２２０６を包含するＳＡＴブロック番号およびバンク番号２６０８と、ＳＡＴブロックの中のＳＡＴページ２２０６のページ番号２６１０とを包含する。ＳＡＴ索引フィールド２３１８は、固定された数のＳＡＴ索引エントリ２３２０のための容量を有する。この数は、ＳＡＴページ２２０６およびＳＡＴ索引ページ２２０８が書き込まれ得る相対頻度を決定する。一実施例では、この固定された数は３２であり得る。

ＳＡＴページのフィールドポインタ２３１０は、ＬＢＡフィールドの先頭からＤＬＢＡフィールドの先頭までのオフセットを定める。それは、ＬＢＡエントリの数としてのオフセット値を包含する。ＳＡＴページ２２０６内のパラメータバックアップエントリは、揮発性ＲＡＭに格納されているパラメータの値を包含する。これらのパラメータ値は、パワーサイクル後に（図８〜９の実施例ではコントローラ１０８と関連付けられ、図１０の実施例ではホストＣＰＵと関連付けられている）ＲＡＭ内の情報の初期化中に使用される。それらは、最も最近に書き込まれたＳＡＴページ２２０６においてのみ有効である。

ＳＡＴ索引ページ
ＳＡＴ索引ページ２２０８のセットは、ＳＡＴ内のどの有効なＳＡＴページ２２０６の位置への索引をも提供する。個々のＳＡＴ索引ページ２２０８は、１つの範囲のＬＢＡアドレスに関連する有効なＳＡＴページの位置を定めるエントリ２３２０を包含する。ＳＡＴ索引ページ２２０８がまたがるＬＢＡアドレスの範囲は、他のどのＳＡＴ索引ページ２２０８がまたがるＬＢＡアドレスの範囲とも重なり合わない。エントリは、それらが関連するＳＡＴページのＬＢＡアドレス範囲値にしたがって整理される。ＳＡＴ索引ページ２２０８は、固定された数のエントリを包含する。ＳＡＴ索引ページ２２０８は、ＳＡＴブロックの完全なセットの全体にわたって無制限に分散され得る。任意の範囲のＬＢＡアドレスのためのＳＡＴ索引ページ２２０８が任意のＳＡＴブロック内にあってよい。ＳＡＴ索引ページ２２０８は、ＳＡＴ索引フィールドとページ索引フィールドとを含む。

ＳＡＴ索引フィールド２３１８は、ＳＡＴ索引ページ２２０８がまたがるＬＢＡアドレス範囲の中の全ての有効なＳＡＴページのためのＳＡＴ索引エントリを包含する。ＳＡＴ索引エントリ２３２０は、単一のＳＡＴページ２２０６に関連し、次の情報、すなわち、ＳＡＴページ２２０６により索引付けされる第１のＬＢＡと、ＳＡＴページ２２０６を包含するＳＡＴブロック番号と、ＳＡＴブロックの中のＳＡＴページ２２０６のページ番号とを包含する。ページ索引フィールドは、ＳＡＴ内の全ての有効なＳＡＴ索引ページ２２０８のためのページ索引エントリを包含する。ページ索引エントリは、ＳＡＴ内のどの有効なＳＡＴ索引ページ２２０８のためにも存在し、次の情報、すなわち、ＳＡＴ索引ページによって索引付けされる第１のＬＢＡと、ＳＡＴ索引ページを包含するＳＡＴブロック番号と、ＳＡＴブロックの中のＳＡＴ索引ページのページ番号とを包含する。ページ索引エントリは、最も最近に書き込まれたＳＡＴ索引ページ２２０８においてのみ有効である。

一時的なＳＡＴデータ構造
図２２に示されているアドレスマッピングの長期記憶のためのＳＡＴ階層の一部ではないけれども、ＳＡＴを更新するための階層的プロシージャの中で追加のデータ構造が使用され得る。１つのそのような構造は、ＬＢＡエントリと、ＳＡＴページ２２０６にまだ書き込まれていないＬＢＡランに対する更新操作またはブロックフラッシング操作から生じた新しいアドレスマッピングのための新しいエントリのための対応するＤＬＢＡマッピングとを含むＳＡＴリストである。ＳＡＴリストはＲＡＭ内の揮発性構造であり得る。ＳＡＴリスト内のエントリは、ＳＡＴページ更新中にそれらがＳＡＴページ２２０６に書き込まれると、クリアされる。

テーブルページ
テーブルページは、ＳＡＴブロック内のＤＬＢＡアドレス空間の固定されたサイズの単位であり、これは１つのＳＡＴページ２２０６または１つのＳＡＴ索引ページ２２０８を記憶するために使用される。テーブルページの最小サイズは１ページであり、最大サイズは１メタページであり、ここでページおよびメタページは、各バンク１０７Ａ〜１０７Ｄのための物理メモリにおけるページおよびメタページに対応するＤＬＢＡアドレス空間の単位である。

ＳＡＴにおけるエントリのサイズ
ＳＡＴページ２２０６およびＳＡＴ索引ページ２２０８の中のエントリのサイズが表１に示されている。

アドレス変換
ＳＡＴは、ホストファイルシステムのＬＢＡアドレスに対応するＤＬＢＡアドレスを迅速に突き止めるために有益である。一実施形態では、有効なデータにマッピングされているＬＢＡアドレスだけがＳＡＴに含まれる。ＳＡＴページ２２０６は、１ＳＡＴページ２２０６から別のＳＡＴページへとＬＢＡ範囲同士が重なり合わないようにＬＢＡ順に配列されるので、所望のデータに向かって迅速に進むために単純なサーチアルゴリズムが使用され得る。このアドレス変換プロシージャの一例が図２７に示されている。ターゲットＬＢＡ２７０２がまず（ストレージアドレス再マッピングの実施例がそれぞれ図１１のように構成されているかまたは図１２のように構成されているかにより）コントローラまたはプロセッサによって受け取られる。他の実施形態では、ＳＡＴが有効なデータおよび使用済みとなったデータにマッピングされたＬＢＡアドレスを含んで、データが有効であるのかそれとも使用済みとなっているのかを追跡するということが考慮され得る。

図２７は、アドレス変換プロシージャを示すほかに、最後に書き込まれたＳＡＴ索引ページからのページ索引フィールドと最後に書き込まれたＳＡＴページからの索引バッファフィールドとがどのように構成され得るかも示す。図２７の実施例では、これら２つのフィールドは、ストレージ装置またはホストのＲＡＭなどの揮発性メモリで一時的に維持される。最後に書き込まれたＳＡＴ索引ページのページ索引フィールドは、どのＳＡＴ索引ページへのポインタをも含む。索引バッファフィールドは、索引ページにまだ書き込まれていない最近書き込まれたＳＡＴページのための索引エントリのセットを包含し得る。

対応するＤＬＢＡアドレスとのターゲットＬＢＡアドレスについてのマッピング情報は、そのターゲットアドレスを含む１つの範囲のＬＢＡアドレスについての全マッピング情報を包含する特定のＳＡＴページ２２０６において保持される。アドレス変換プロシージャの第１の段階は、このターゲットＳＡＴページを識別して読むことである。図２７を参照すると、ターゲットＬＢＡのためのＳＡＴ索引エントリが存在するか否かを判定するために、最後に書き込まれたＳＡＴページの索引バッファフィールドのキャッシュされているバージョンに対して二分探索が実行される（ステップ２７０４において）。ターゲットＳＡＴページが最近再書き込みされているけれどもターゲットＳＡＴページの新しい位置を記録したＳＡＴ索引エントリを組み込んだＳＡＴ索引ページがまだ書き込まれていなければ、１つのエントリが存在する。ターゲットＬＢＡのためのＳＡＴ索引エントリが発見されたならば、それはターゲットＳＡＴページの位置を定義し、このページが読み出される（ステップ２７０６において）。

ステップ２７０４でターゲットＬＢＡのためのＳＡＴ索引エントリが発見されなければ、ターゲットＬＢＡのためのＳＡＴ索引エントリの位置を突き止めるために、最後に書き込まれたＳＡＴ索引ページのページ索引フィールドのキャッシュされたバージョンに対して二分探索が実行される（ステップ２７０８において）。ステップ２７０８で発見されたターゲットＬＢＡのためのＳＡＴ索引エントリは、ターゲットＬＢＡを包含するＬＢＡアドレス範囲のためのＳＡＴ索引ページの位置を定める。このページが読み出される（ステップ２７１０において）。ターゲットＬＢＡのためのＳＡＴ索引エントリの位置を突き止めるために二分探索が実行される（ステップ２７１２において）。ターゲットＬＢＡのためのＳＡＴ索引エントリは、ターゲットＳＡＴページの位置を定める。このページが読み出される（ステップ２７１４において）。

ターゲットＳＡＴページがステップ２７０６またはステップ２７１４で読まれると、ＬＢＡからＤＬＢＡへの変換が次のように実行され得る。ターゲットＬＢＡを組み込んだターゲットＬＢＡランのためのＬＢＡエントリの位置を突き止めるために、ＬＢＡフィールドに対して二分探索が実行される。ターゲットＬＢＡランの中でのターゲットＬＢＡのオフセットが記録される（ステップ２７１６において）。フィールドポインタ内の情報は、二分探索のためのＬＢＡフィールドの長さ、さらにＬＢＡフィールドの先頭に対してのＤＬＢＡフィールドの先頭をも定める（ステップ２７１８において）。ステップ２７１６で発見されたＬＢＡエントリは、ＬＢＡランにマッピングされている第１のＤＬＢＡエントリのＤＬＢＡフィールドの中での位置を定める（ステップ２７２０において）。ステップ２７１６で判定されたオフセットは、ステップ２７２０で位置が突き止められたより多くのＤＬＢＡエントリのうちの１つと共に、ターゲットＤＬＢＡアドレスを判定するために使用される（ステップ２７２２において）。

ストレージアドレス再マッピングアルゴリズムは、白色ブロックの数が所定のしきい値未満にまで減ると、書き込みブロックにおけるホストデータの書き込みにより白色容量が消費されるのと同じ速度でデータ書き込みのために割り当てられ得る使用可能な白色容量が作られることを保証するのに充分な速度でピンク色ブロックに対するフラッシング（再配置とも称される）操作が行われなければならないという原理にしたがって動作する。データ書き込みのために割り当てられ得る使用可能な白色クラスタ容量は、白色ブロック内の容量に加えて、フラッシング操作中にデータが書き込まれ得る再配置ブロックの中の白色クラスタ容量である。

フラッシング操作のために選択されたピンク色ブロック内の白色クラスタ容量が各ピンク色ブロックのｘ％を占めるならば、１つのピンク色ブロックに対するフラッシング操作によって作られる新しい使用可能な容量は、そのピンク色ブロックから作られる１つの完全な白色ブロックからそのフラッシングされるブロックからのデータの再配置によって再配置ブロックにおいて消費される１ブロックを差し引いた（１００−ｘ）パーセンテージである。したがって、１つのピンク色ブロックに対するフラッシング操作は、１白色ブロックのｘ％の新しい使用可能な容量を作る。したがって、書き込まれるホストデータにより満たされる各書き込みブロックのために、１００／ｘ個のピンク色ブロックに対してフラッシング操作が実行されなければならず、再配置されなければならないデータは（１００−ｘ）／ｘブロックである。したがって、プログラムされたセクタの、ホストにより書き込まれたセクタに対する比は、およそ１＋（１００−ｘ）／ｘとして定義される。

１つの平均的ピンク色ブロックにおける白色クラスタ容量のパーセンテージは、使用されている総装置容量のパーセンテージと、赤色ブロックであるデータを包含しているブロックのパーセンテージとにより決定される。例えば、装置が８０％満たされ、データを包含するブロックの３０％が赤色ブロックであるならば、ピンク色ブロックは２６．２％白色クラスタ容量を含む。装置内のＬＢＡアドレスでのデータ削除の分布が不均一であれば、あるピンク色ブロックが白色容量の平均％の２倍を有するという結果になりそうである。したがって、この例では、フラッシング操作のために選択されるピンク色ブロックは５２．４％白色容量を有し、すなわちｘ＝５２．４であり、ホストにより書き込まれたデータのセクタあたりのプログラムされたセクタの比は１．９０になる。

どのピンク色ブロックをフラッシングするかを決定するときには、それがホストデータピンク色ブロックであろうとＳＡＴピンク色ブロックであろうと、ストレージアドレス再マッピングアルゴリズムは、ＮＴＦＳにより書き込まれる＄ｂｉｔｍａｐファイルを監視することによって未割り当てアドレスの指示を検出することができる。フラッシング操作は２つの仕方でスケジュールされ得る。好ましくは、フラッシング操作は、バックグラウンド操作として動作し、したがって、ＳＳＤまたは他の携帯可能なフラッシュ記憶装置がアイドルでホストデータ書き込み速度が影響を受けない間に限って機能する。あるいは、フラッシング操作は、ホストがデータを書き込んでいるときにアクティブであるフォアグラウンド操作で利用されてもよい。フラッシング操作がフォアグラウンド操作として構成されるならば、これらの操作は、ホストアクティビティが発生したとき、あるいは「フラッシュキャッシュ」コマンドがＳＳＤまたは携帯可能なフラッシュ記憶装置の潜在的なパワーダウンを示すときに、自動的にサスペンドされ得る。フォアグラウンドおよびバックグラウンドフラッシング操作選択は動的決定であってよく、記憶装置がアイドル状態である間に達成され得るよりも高いフラッシング速度が必要とされるときにはフォアグラウンド操作が行われる。例えば、記憶装置が満杯になるまで一定のホストデータ書き込み速度を維持するようにフラッシング速度が制御されるようにホストまたは記憶装置はフォアグラウンドフラッシング操作およびバックグラウンドフラッシング操作の間でトグルすることができる。フォアグラウンドフラッシング操作は、ホストデータ書き込み操作と交互配置され得る。例えば、ホストインターフェイスでアクティビティが続けられているために充分なアイドル時間が利用できなければ、ブロックフラッシング操作を実行するためのデータページの再配置は、ホストコマンドに応答して短いバーストをなして装置アクティビティと交互配置され得る。

ＳＡＴ更新手続き
ＳＡＴデータ構造の中の要素は、表２に示されている階層的プロシージャを用いて更新される。

表２に書き留められているように、ＤＬＢＡラン更新を除いて、特定の構造のためのＳＡＴ更新は、ＳＡＴ階層の中のより下位の構造におけるアクティビティによってトリガされる。ＳＡＴリストは、完全なＤＬＢＡランと関連するデータが書き込みブロックに書き込まれるたびに更新される。最大許容数のエントリがＳＡＴリストに存在するときに１つ以上のＳＡＴページが更新される。ＳＡＴページが更新されるとき、ＳＡＴリストからの１つ以上のエントリがＳＡＴページに加えられ、ＳＡＴリストから除去される。ＳＡＴリストが満杯であるときに更新されるＳＡＴページを、ページのいくつかの異なるグループに分割することができ、単一のグループだけが単一の操作で更新されなければならない。これは、ＳＡＴ更新操作がホストからのデータ書き込み操作を遅らせるかもしれない時間を最小にするのに役立ち得る。この場合、ＳＡＴリストから、更新されたＳＡＴページのグループにコピーされるエントリだけがＳＡＴリストから除去される。更新されるＳＡＴページのグループのサイズは、ホストシステム１００のメモリシステム１０２にアクセスする能力を妨げないポイントにセットされ得る。１つの実施例では、グループサイズは４ＳＡＴページであり得る。

ＳＡＴ索引バッファフィールドは、最も最近に書き込まれたＳＡＴページにおいて有効である。それは、ＳＡＴページが書き込まれるたびに、さらなるプログラミングなしで更新される。最後に、最大許容数のエントリがＳＡＴ索引バッファに存在するとき、ＳＡＴ索引ページが更新される。ＳＡＴ索引ページ更新中、ＳＡＴ索引バッファからの１つ以上のエントリがＳＡＴ索引ページに加えられ、ＳＡＴ索引バッファから除去される。ＳＡＴページ更新に関して前に書き留められたように、更新されなければならないＳＡＴ索引ページをページのいくつかの異なるグループに分割することができ、単一のグループだけが単一の操作で更新されなければならない。これは、ＳＡＴ更新操作がホストからのデータ書き込み操作を遅らせるかもしれない時間を最小にする。ＳＡＴ索引バッファから更新されたＳＡＴ索引ページのグループにコピーされるエントリだけが、ＳＡＴ索引バッファから除去される。更新されたＳＡＴ索引ページのグループのサイズは、一実施例では４ページであり得る。

ＳＡＴページまたはＳＡＴ索引ページがまたがるＬＢＡ範囲の中で必要とされるエントリの数は可変であって、時間と共に変化し得る。したがって、ＳＡＴ内のページがオーバーフローしたり、あるいはページの内容が非常にまばらになったりするのは稀なことではない。これらの事態は、ＳＡＴ内のページを分割し結合するための方式によって管理され得る。

ＳＡＴページまたはＳＡＴ索引ページの更新中にエントリが加えられなければならないけれどもページにおいてその変化のために利用し得る未使用スペースが不十分であるときには、そのページは２つに分割される。１つの新しいＳＡＴページまたはＳＡＴ索引ページが導入され、以前満杯であったページと新しい空のページとのために、それらを半分満杯にするいくつかのエントリを各々に与えるＬＢＡ範囲が判定される。その後、可能ならば単一のプログラミング操作で、両方のページが書き込まれる。ページがＳＡＴページである場合には、両方のページのためのＳＡＴ索引エントリは、最後に書き込まれるＳＡＴページ内の索引バッファフィールドに含まれる。ページがＳＡＴ索引ページである場合には、ページ索引エントリは、最後に書き込まれるＳＡＴ索引ページ内のページ索引フィールドに含まれる。

隣接するＬＢＡ範囲を伴う２つ以上のＳＡＴページまたは２つのＳＡＴ索引ページの内容がまばらであるときには、ページは結合されて単一のページにされ得る。結合は、その結果としての単一のページが８０％未満で満杯となるときに開始される。新しい単一のページのためのＬＢＡ範囲は、別々の結合されるページがまたがる範囲により定められる。結合されるページがＳＡＴページである場合には、新しいページと結合されるページとのためのＳＡＴ索引エントリは、最後に書き込まれるＳＡＴページ内の索引バッファフィールドにおいて更新される。ページがＳＡＴ索引ページである場合には、ページ索引エントリは、最後に書き込まれるＳＡＴ索引ページ内のページ索引フィールドにおいて更新される。

パワーサイクル後、すなわち電力が除去され回復された後、ＳＡＴリストを、それがパワーサイクル前にあったのと正確に同じ状態に、ＲＡＭにおいて再構築する必要がある。これは、データヘッダ内のＬＢＡアドレス情報から、最後のＳＡＴページ更新以来書き込まれた追加データを特定するために全ての書き込みブロックおよび再配置ブロックをスキャンすることによって成し遂げられ得る。最後のＳＡＴページ更新時におけるこれらのブロックの位置と、それらの中の書き込みポインタおよび再配置ポインタの位置とも、最後に書き込まれたＳＡＴページ内のフィールドに記録される。したがって、スキャンは単にこれらのポインタの位置から開始されればよい。

ＳＡＴブロックをフラッシングすること
ＳＡＴブロックをフラッシングするプロセスは、ホストから受け取られるデータについて前述したプロセスと類似するけれども、ＳＡＴブロックだけに作用する。ストレージアドレス再マッピング書き込みおよびフラッシングアルゴリズムによって引き起こされるＳＡＴに対する更新は、ＳＡＴブロックを図２８に示されているブロック状態間で遷移させる。始めに、次のＳＡＴブロックを受け取るように現在指定されているバンクのための白色ブロックリストから１つの白色ブロックがＳＡＴ書き込みブロックとして割り当てられる（２８０２において）。ＳＡＴ書き込みブロック内の最後のページが割り当てられると、ブロックは赤色ＳＡＴブロックになる（２８０４において）。ＳＡＴ書き込みブロックは、その中のいくつかのページが既に使用済みとなっていたならば、ピンク色ＳＡＴブロックへの遷移を行ない得る。しかし、明瞭性を目的として、その遷移は図２８には示されていない。ＳＡＴページまたはＳＡＴ索引ページが更新されると赤色ＳＡＴブロックの中の１つ以上のページが使用済みとなり、赤色ＳＡＴブロックはピンク色ＳＡＴブロックになる（２８０６において）。再配置されるデータのためにだけ指定されている特別の書き込みブロックへ有効なデータが移される、ホストデータを包含するピンク色ブロックのフラッシング操作とは違って、ピンク色ＳＡＴブロックのためのフラッシング操作は、有効なＳＡＴデータを現在のＳＡＴ書き込みブロックへ単に再配置する。選択されたピンク色ＳＡＴブロックに対するフラッシング操作が完了すると、そのピンク色ＳＡＴブロックは白色ブロックになる（２８０８において）。ＳＡＴピンク色ブロックは、好ましくは、同じバンク１０７Ａ〜１０７Ｄ内のＳＡＴ書き込みブロックへフラッシングされる。

次に、どのＳＡＴブロックがフラッシングプロシージャを受けるかを選択するプロセスを記述する。少数の有効なページまたはクラスタを包含するＳＡＴブロックが、フラッシングされるべき次のＳＡＴブロックとして選択される。ブロックは、その特定バンク内のＳＡＴブロックのうちの最小数の有効なページを有するＳＡＴブロックのうちの５％の中の１つであるべきである。ブロックの選択は、各バンクにおいて最小の有効ページ総数値を有する１６個のＳＡＴブロックのリストを構築するバックグラウンドプロセスによって成し遂げられ得る。このプロセスは、好ましくは、Ｍ個のスケジュールされたＳＡＴブロックフラッシング操作に費やされる時間のうちに１サイクルを終えるべきである。

次に、どのＳＡＴブロックをフラッシングするかを決定するためのバックグラウンドプロセスの１サイクルで行われるアクティビティの例が図２９に示されている。まず、前のプロセスサイクルの間に特定されたブロックのセットに次ぐ、それぞれのバンク内のＮ個のＳＡＴブロックの次のセットを特定するために、各バンクのためのブロック情報テーブル（ＢＩＴ）がスキャンされる（ステップ２９０２において）。装置初期化後の第１のプロセスサイクルにおいてＳＡＴブロックの第１のセットが特定されるべきである。Ｎの値は、その特定のアプリケーションのために適宜選択されてよく、好ましくは、ＳＡＴフラッシングブロックの利用可能性を保証するためにＭのために選択される値より大きい。一例として、Ｍは４であり、Ｎは８であり得る。セット中の各ＳＡＴブロックについて有効ページ総数値がゼロにセットされる（ステップ２９０４において）。その後、セット中のいずれかのＳＡＴブロック内に位置する有効なＳＡＴ索引ページを特定するために、キャッシュされているページ索引フィールドにおいてページ索引エントリがスキャンされる（ステップ２９０６において）。それに応じて有効ページ総数値がインクリメントされる。セット中のいずれかのＳＡＴブロック内に位置する有効なＳＡＴページを特定するために、ＳＡＴ索引エントリが各ＳＡＴ索引ページにおいて順にスキャンされる（ステップ２９０８において）。それに応じて有効ページ総数値がインクリメントされる（ステップ２９１０において）。有効ページ総数値を判定するためにページ索引およびＳＡＴ索引ページがスキャンされた後、セット中のＳＡＴブロックの各々についての有効ページ総数値は、低有効ページ総数値を求めてリスト中のＳＡＴブロックについてのものと対照して評価され、必要ならばリスト中のブロックはセットからのブロックにより取って代わられる（ステップ２９１２において）。ＳＡＴブロックフラッシング操作がスケジュールされるべきであるときには、リスト中の最低有効ページ総数値を有するブロックが選択される。

ＳＡＴブロックフラッシング操作において、全ての有効なＳＡＴ索引ページおよびＳＡＴページが、選択されたブロックから、それぞれのバンク内のＳＡＴ書き込みブロック２３００のＳＡＴ書き込みポインタ２３０２へ再配置される。ページ索引フィールドは、最後に書き込まれるＳＡＴ索引ページにおいてだけ更新される。ＳＡＴブロックの数がほぼ一定に保たれるためには、ＳＡＴページおよびＳＡＴ索引ページに対する更新操作によって消費されるＳＡＴ内のページの数は、ＳＡＴブロックフラッシング操作によって回復される使用済みとなったＳＡＴページおよびＳＡＴ索引ページの数と釣り合わされなければならない。次のＳＡＴフラッシング操作のために選択されたＳＡＴブロック内の使用済みとなった情報のページの数は、前に図２９に関して論じられたように判定される。次のＳＡＴブロックフラッシング操作は、前のＳＡＴフラッシング操作以後にＳＡＴに同数の有効情報ページが書き込まれたときに行われるようにスケジュールされ得る。さらに、コントローラ１０８は、各ブロックについて独立に、ＳＡＴデータのピンク色ブロックをフラッシングするかあるいはホストデータのピンク色ブロックをフラッシングするかを、ピンク色ブロック内の有効なデータの量に基づいてあるいは１つ以上の他のパラメータに基づいて選択することができる。

ブロック情報テーブル（ＢＩＴ）
ブロック情報テーブル（ＢＩＴ）は、白色ブロック、ピンク色ブロック、およびＳＡＴブロックのためにブロックアドレスの別々のリストを記録するために使用される。マルチブロックメモリでは、各バンク１０７Ａ〜１０７Ｄにおいて別々のＢＩＴが維持される。ＢＩＴ書き込みブロックは、同じバンク内の他の全てのＢＩＴブロックがどこに位置するかに関する情報を包含する。一実施例では、ストレージアドレス再マッピングアルゴリズムおよび関連するシステムは、書き込みブロック、再配置ブロックまたはＳＡＴブロックとして割り当てられるべきブロックの選択を可能にするために白色ブロックのリストを維持するのが望ましい。各バンクにおいてブロックフラッシング操作の対象となるべきピンク色ブロックおよびＳＡＴブロックの選択を可能にするために、ピンク色ブロックのリストを維持することも望ましい。これらのリストは、その構造がＳＡＴのものを厳密に反映するＢＩＴにおいて維持される。一実施形態では、各バンク１０７Ａ〜１０７Ｄにおいて別々のＢＩＴが維持され記憶される。他の１つの実施形態では、ＢＩＴは、バンクにより索引付けされる情報を有する単一のテーブルであり得る。

ＢＩＴデータ構造
各バンク内のＢＩＴは、ＢＩＴブロックとして知られるＤＬＢＡアドレスのブロックの中で実現される。ブロックリスト情報がＢＩＴページの中に格納され、「ＤＬＢＡブロック対ＢＩＴページ」索引付け情報がＢＩＴ索引ページの中に格納される。ＢＩＴページおよびＢＩＴ索引ページは、同じＢＩＴブロックの中で任意の順序で混合されてよい。ＢＩＴは複数のＢＩＴブロックから成ることができるが、ＢＩＴ情報はＢＩＴ書き込みブロックとして現在指定されている単一のブロックに書き込まれ得るだけである。他の全てのＢＩＴブロックは、以前に完全に書き込まれていて、有効なページおよび使用済ページの組み合わせを包含し得る。使用済ＢＩＴ情報のページを削除して再使用される白色ブロックを作るために前述したＳＡＴブロックのためのものと同一のＢＩＴブロックフラッシング方式が実行される。

ＢＩＴブロック
図３０に示されているＢＩＴブロックは、ＢＩＴ情報の格納に専用されるＤＬＢＡアドレスのブロックである。ＢＩＴページ３００２とＢＩＴ索引ページ３００４とを含むことができる。ＢＩＴブロックは、有効なＢＩＴページ、有効なＢＩＴ索引ページ、および使用済ページの任意の組み合わせを包含することができる。ＢＩＴ情報は、ＢＩＴ書き込みブロック３０００として指定されている単一のＢＩＴブロックに書き込まれ得るだけである。ＢＩＴ情報は、ＢＩＴ書き込みブロック３０００において、インクリメントなＢＩＴ書き込みポインタ３００６により定められる順次の位置に書き込まれる。ＢＩＴ書き込みブロック３０００が完全に書き込まれると、１つの白色ブロックが新しいＢＩＴ書き込みブロックとして割り当てられる。ＢＩＴを構成するブロックは、それらのＢＩＴブロック位置によってそれぞれ特定され、装置内のブロックの集団の中でのそれらのブロックアドレスである。ＢＩＴブロックはテーブルページに分割され、それらにＢＩＴページ３００２またはＢＩＴ索引ページ３００４が書き込まれ得る。ＢＩＴページ位置は、そのＢＩＴブロックの中でのもののシーケンス番号によってアドレス指定される。ＢＩＴ情報を、フラッシュメモリの異なるブロック内で非ＢＩＴ情報と分離することができ、非ＢＩＴ情報とは異なるタイプのブロック（例えば、バイナリとＭＬＣ）へ分離することができたり、あるいは１つのブロック内で非ＢＩＴ情報と混合することができたりする。

ＢＩＴページ３００２は、ＢＩＴにおけるブロックリスト情報の最小更新可能単位である。更新されたＢＩＴページは、ＢＩＴ書き込みポインタ３００６によって定められる位置に書き込まれる。ＢＩＴページ３００２は、定められた範囲の中のＤＬＢＡブロックアドレスを有する白色ブロック、ピンク色ブロックおよびＳＡＴブロックのリストを包含するけれども、どのリスト中の引き続くブロックのブロックアドレスも連続的でなくてもよい。ＢＩＴページ内のＤＬＢＡブロックアドレスの範囲は、他のどのＢＩＴページ内のＤＬＢＡブロックアドレスの範囲とも重なり合わない。ＢＩＴページは、ＢＩＴブロックの完全なセットの全体にわたって無制限に分散され得る。ＤＬＢＡアドレスのどの範囲のためのＢＩＴページも、どのＢＩＴブロック内にあってもよい。ＢＩＴページは、白色ブロックリスト（ＷＢＬ）フィールド３００８、ピンク色ブロックリスト（ＰＢＬ）フィールド３０１０、ＳＡＴブロックリスト（ＳＢＬ）フィールド３０１２および索引バッファフィールド３０１４を含むとともに、さらに２つの制御ポインタ３０１６をも含む。パラメータバックアップエントリも、揮発性ＲＡＭに格納されているいくつかのパラメータの値を含む。

ＢＩＴページ３００２内のＷＢＬフィールド３００８は、ＢＩＴページ３００２に関連するＤＬＢＡブロックアドレスの範囲の中の、白色ブロックリスト内のブロックのためのエントリを包含する。ＢＩＴページ３００２がまたがるＤＬＢＡブロックアドレスの範囲は、他のどのＢＩＴページ３００２がまたがるＤＬＢＡブロックアドレスの範囲とも重なり合わない。ＷＢＬフィールド３００８は、可変長のフィールドであって、可変数のＷＢＬエントリを包含する。ＷＢＬフィールドの中に、ＢＩＴページ３００２により索引付けされるＤＬＢＡブロックアドレスの範囲の中のどの白色ブロックについてもＷＢＬエントリが存在する。ＷＢＬエントリは、ブロックのＤＬＢＡアドレスを包含する。

ＢＩＴページ３００２内のＰＢＬフィールド３０１０は、ＢＩＴページ３００２に関連するＤＬＢＡブロックアドレスの範囲の中の、ピンク色ブロックリスト内のブロックのためのエントリを包含する。ＢＩＴページ３００２がまたがるＤＬＢＡブロックアドレスの範囲は、他のどのＢＩＴページ３００２がまたがるＤＬＢＡブロックアドレスの範囲とも重なり合わない。ＰＢＬフィールド３０１０は、可変長のフィールドであって、可変数のＰＢＬエントリを包含する。ＰＢＬフィールド３０１０の中に、ＢＩＴページ３００２により索引付けされるＤＬＢＡブロックアドレスの範囲の中のどのピンク色ブロックについてもＰＢＬエントリが存在する。ＰＢＬエントリは、ブロックのＤＬＢＡアドレスを包含する。

ＢＩＴページ内のＳＢＬフィールド３０１２は、ＢＩＴページ３００２に関連するＤＬＢＡブロックアドレスの範囲の中の、ＳＡＴブロックリスト内のブロックのためのエントリを包含する。ＢＩＴページ３００２がまたがるＤＬＢＡブロックアドレスの範囲は、他のどのＢＩＴページ３００２がまたがるＤＬＢＡブロックアドレスの範囲とも重なり合わない。ＳＢＬフィールド３０１２は、可変長のフィールドであって、可変数のＳＢＬエントリを包含する。ＳＢＬフィールド３０１２の中に、ＢＩＴページ３００２により索引付けされるＤＬＢＡブロックアドレスの範囲の中のどのＳＡＴブロックについてもＳＢＬエントリが存在する。ＳＢＬエントリは、ブロックのＤＬＢＡアドレスを包含する。

索引バッファフィールド３０１４は、全てのＢＩＴページ３００２の一部として書き込まれるけれども、最も最近に書き込まれたＢＩＴページにおいてのみ有効なままである。ＢＩＴページ３００２の索引バッファフィールド３０１４は、ＢＩＴ索引エントリを包含する。関連するＢＩＴ索引ページ３００４内に有効なエントリを現在有しないＢＩＴ内のどのＢＩＴページ３００２についてもＢＩＴ索引エントリが存在する。ＢＩＴ索引エントリは、ＢＩＴページ３００２が書き込まれるたびに作成または更新され、関連するＢＩＴ索引ページ３００４が更新されると削除される。ＢＩＴ索引エントリは、ＢＩＴページ３００２によって索引付けされる範囲の第１のＤＬＢＡブロックアドレスと、ＢＩＴページ３００２によって索引付けされる範囲の最後のＤＬＢＡブロックアドレスと、ＢＩＴページ３００２を包含するＢＩＴブロック位置と、ＢＩＴブロックの中のＢＩＴページのＢＩＴページ位置とを含むことができる。索引バッファフィールド３０１４は、仮に３２と定められる固定された数のＢＩＴ索引エントリのための容量を有する。この数は、ＢＩＴページ３００２およびＢＩＴ索引ページ３００４が書き込まれ得る相対頻度を決定する。
ＢＩＴページ３００２の制御ポインタ３０１６は、ＰＢＬフィールド３０１０の先頭およびＳＢＬフィールド３０１２の先頭の、ＷＢＬフィールド３００８の先頭からのオフセットを定める。ＢＩＴページ３００２は、リストエントリの数としてのオフセット値を包含する。

ＢＩＴ索引ページ
ＢＩＴ索引ページ３００４のセットは、ＢＩＴ内の全ての有効なＢＩＴページ３００２の位置への索引を提供する。個々のＢＩＴ索引ページ３００４は、ＤＬＢＡブロックアドレスの１つの範囲に関連する有効なＢＩＴページの位置を定めるエントリを包含する。ＢＩＴ索引ページがまたがるＤＬＢＡブロックアドレスの範囲は、他のどのＢＩＴ索引ページ３００４がまたがるＤＬＢＡブロックアドレスの範囲とも重なり合わない。エントリは、それらが関連するＢＩＴページ３００２のＤＬＢＡブロックアドレス範囲値にしたがって整理される。ＢＩＴ索引ページ３００４は、固定された数のエントリを包含する。

ＢＩＴ索引ページは、ＢＩＴブロックの完全なセットの全体にわたって無制限に分散され得る。ＤＬＢＡブロックアドレスのどの範囲のためのＢＩＴ索引ページ３００４も、どのＢＩＴブロック内にあってもよい。ＢＩＴ索引ページ３００４は、ＢＩＴ索引フィールド３０１８およびページ索引フィールド３０２０を含む。ＢＩＴ索引フィールド３０１８は、ＢＩＴ索引ページ３００４がまたがるＤＬＢＡブロックアドレス範囲の中の全ての有効なＢＩＴページのためのＢＩＴ索引エントリを含む。ＢＩＴ索引エントリは、単一のＢＩＴページ３００２に関連し、ＢＩＴページにより索引付けされる第１のＤＬＢＡブロックと、ＢＩＴページを包含するＢＩＴブロック位置と、ＢＩＴブロックの中のＢＩＴページのＢＩＴページ位置とを含むことができる。

ＢＩＴ索引ページ３００４のページ索引フィールド３０２０は、ＢＩＴ内の全ての有効なＢＩＴ索引ページのためのページ索引エントリを包含する。ＢＩＴページ索引エントリは、ＢＩＴ内のどの有効なＢＩＴ索引ページ３００４のためにも存在し、ＢＩＴ索引ページにより索引付けされる第１のＤＬＢＡブロックと、ＢＩＴ索引ページを包含するＢＩＴブロック位置と、ＢＩＴブロックの中のＢＩＴ索引ページのＢＩＴページ位置とを含むことができる。

ＢＩＴを維持すること
ＢＩＴページ３００２は、ＷＢＬ３００８、ＰＢＬ３０１０およびＳＢＬ３０１２にエントリを加え、あるいはこれらからエントリを削除するために更新される。数個のエントリに対する更新がＲＡＭ内のリストに、そのリストがパワーサイクル後にＲＡＭに回復され得るということを条件として、蓄積されてＢＩＴにおいて単一の操作で実行され得る。ＢＩＴ索引バッファフィールドは、最も最近に書き込まれたＢＩＴページにおいて有効である。ＢＩＴページが書き込まれるたびに付加的なプログラミングなしで更新される。ＢＩＴ索引ページが更新されるとき、ＢＩＴ索引バッファからの１つ以上のエントリがＢＩＴ索引ページに加えられ、ＢＩＴ索引バッファから除去される。最大許容数のエントリがＢＩＴ索引バッファ内に存在するときには１つ以上のＢＩＴ索引ページ３００４が更新される。

ＢＩＴページ３００２またはＢＩＴ索引ページ３００４がまたがるＤＬＢＡブロック範囲の中に必要とされるエントリの数は可変であって、時間と共に変化し得る。したがって、ＢＩＴ内のページがオーバーフローしたり、あるいはページの内容が非常にまばらになったりするのは稀なことではない。これらの事態は、ＢＩＴ内のページを分割し結合するための方式によって管理され得る。

ＢＩＴページ３００２またはＢＩＴ索引ページ３００４の更新中にエントリが加えられなければならないけれどもページにおいてその変化のために利用し得る未使用スペースが不十分であるときには、そのページは２つに分割される。１つの新しいＢＩＴページ３００２またはＢＩＴ索引ページ３００４が導入され、以前満杯であったページと新しい空のページとのために、それらを半分満杯にするいくつかのエントリを各々に与えるＤＬＢＡブロック範囲が判定される。その後、可能ならば単一のプログラミング操作で、両方のページが書き込まれる。ページがＢＩＴページ３００２である場合には、両方のページのためのＢＩＴ索引エントリは、最後に書き込まれるＢＩＴページ内の索引バッファフィールドに含まれる。ページがＢＩＴ索引ページ３００４である場合には、ページ索引エントリは、最後に書き込まれるＢＩＴ索引ページ内のページ索引フィールドに含まれる。

逆に、隣接するＤＬＢＡブロック範囲を有する２つ以上のＢＩＴページ３００２、あるいは２つのＢＩＴ索引ページ３００４の内容がまばらであるときには、ページは結合されて単一のページとされ得る。結合は、結果として生じる単一のページが８０％満たされるに過ぎないときに開始される。新しい単一のページのためのＤＬＢＡブロック範囲は、別々の結合されるページがまたがる範囲により定められる。結合されるページがＢＩＴページである場合には、新しいページおよび結合されるページのためのＢＩＴ索引エントリは、最後に書き込まれるＢＩＴページ内の索引バッファフィールドにおいて更新される。ページがＢＩＴ索引ページである場合には、ページ索引エントリは、最後に書き込まれるＢＩＴ索引ページ内のページ索引フィールドにおいて更新される。

ＢＩＴブロックをフラッシングすること
ＢＩＴブロックをフラッシングするプロセスは、ＳＡＴブロックについて前に記載したプロセスに厳密に従い、ここでは繰り返されない。

制御ブロック
他の実施形態では、ＢＩＴおよびＳＡＴ情報は同じブロックの異なるページに格納され得る。制御ブロックと称されるこのブロックは、１ページのＳＡＴまたはＢＩＴ情報が制御ブロック内の１ページを占めるように構造化され得る。制御ブロックは、整数個のページを有するページユニットから成ることができ、各ページユニットは制御ブロックの中でのそれ自身のシーケンス番号によりアドレス指定される。ページユニットは、物理メモリにおいて１ページの最小サイズおよび１メタページの最大サイズを有することができる。制御ブロックは、有効なＳＡＴページ、ＳＡＴ索引ページ、ＢＩＴページ、ＢＩＴ索引ページ、および使用済ページの任意の組み合わせを包含することができる。したがって、別々のＳＡＴおよびＢＩＴブロックを持つのではなくて、ＳＡＴおよびＢＩＴ情報の両方を同じ１つのまたは複数のブロックに格納することができる。前述した別々のＳＡＴおよびＢＩＴ書き込みブロックの場合と同じく、制御情報（ＳＡＴまたはＢＩＴ情報）を単一の制御書き込みブロックに書き込むことができるに過ぎず、制御書き込みポインタは制御データを受け取るための次の順次位置を特定し、制御書き込みブロックが完全に書き込まれると１つの書き込みブロックが新しい制御書き込みブロックとして割り当てられる。さらに、制御ブロックは、それぞれ、メモリシステム１０２内のバイナリブロックの集団の中でそれら自身のブロックアドレスによって特定され得る。制御ブロックは、前述した分離されているＳＡＴおよびＢＩＴブロックについて記載されたのと同じ仕方で新しい未書き込み容量を生成するためにフラッシングされ得るけれども、制御ブロックのための再配置ブロックが有効なＳＡＴまたはＢＩＴ情報に関連するページを受け入れ得るという違いがある。フラッシングのための適切なピンク色制御ブロックの選択およびタイミングはＳＡＴフラッシングプロセスについて前述したのと同じ仕方で実行され得る。

ＬＢＡ割り当てステータスを監視すること
ストレージアドレス再マッピングアルゴリズムは、ホストによって有効なデータに現在割り当てられているホストＬＢＡアドレスだけのためにアドレスマッピング情報を記録する。したがって、このマッピング情報を正確に維持するために、クラスタがホストによってデータ記憶から割り当て解除されたときを判定する必要がある。

一実施形態では、ホストファイルシステムからのコマンドが、割り当て解除されたクラスタに関する情報をストレージアドレス再マッピングアルゴリズムに提供することができる。例えば、「データセット」コマンドが、マイクロソフト コーポレイションのビスタ（Ｖｉｓｔａ）オペレーティングシステムに用いられるように提案されている。「ＡＴＡ８−ＡＣＳ２についての削除済みデータ通知提案（Notification of Deleted Data Proposal for ATA8-ACS2)」についての提案が、マイクロソフトによりＴ１３に提出されている。この新しいコマンドは、削除済みデータの通知を提供するように意図されている。単一のコマンドが、２ＧＢに及ぶ使用済データを表す、連続するＬＢＡアドレスにおけるデータの削除を装置に知らせることができる。

ＮＴＦＳメタデータを解釈すること
トリムコマンドなどのホストファイルシステムコマンドが利用できなければ、ＬＢＡ割り当てステータスを、ＮＴＦＳにより書き込まれる＄ｂｉｔｍａｐシステムファイルにおける情報変化を追跡することによって監視することができ、ボリューム上の全てのクラスタの割り当てステータスのビットマップを包含する。パーソナルコンピュータ（ＰＣ）において＄ｂｉｔｍａｐ変化を追跡する一例が以下で論じられる。

パーティションブートセクタ
パーティションブートセクタは、パーティション上のセクタ０である。バイトオフセット０ｘ３０におけるフィールドは、表３への例の場合のように、マスタファイルテーブル（ＭＦＴ）の先頭のための論理クラスタ番号を包含する。

ＭＦＴにおける＄ｂｉｔｍａｐ記録
＄ｂｉｔｍａｐと称されるシステムファイルは、ボリューム上の全てのクラスタの割り当てステータスのビットマップを包含する。＄ｂｉｔｍａｐファイルのための記録は、ＭＦＴ内の記録番号６である。ＭＦＴ記録は１，０２４バイトの長さを有する。したがって、＄ｂｉｔｍａｐ記録はＭＦＴの先頭に関して十進１２セクタのオフセットを有する。前の例では、ＭＦＴはクラスタ０ｘＣ４ＦＤ２、すなわち十進８０６８６６から始まり、セクタ十進６４５４９２８である。したがって、＄ｂｉｔｍａｐファイル記録はセクタ十進６４５４９４０から始まる。

（記述されている例において）次の情報は＄ｂｉｔｍａｐ記録の中に存在する。表４の例のように、バイトオフセット０ｘ１４１から０ｘ１４２までのところのフィールドは、＄ｂｉｔｍａｐファイルについての、第１のデータ属性のクラスタ単位の長さを包含する。

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

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

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

＄ｂｉｔｍａｐファイルについてのデータ属性
＄ｂｉｔｍａｐファイルについてのデータ属性の中のセクタは、論理クラスタ番号の順に、ボリューム内の全てのクラスタの割り当てステータスのビットマップを包含する。「１」はフィルシステムによってクラスタがデータ格納のために割り当てられていることを表し、「０」はクラスタが空いていることを表した。ビットマップ内の各バイトは、８クラスタまたは６４十進セクタの論理範囲に関連する。ビットマップ内の各セクタは、０ｘ１，０００（十進４０９６）クラスタまたは０ｘ８，０００（十進３２７６８）セクタの論理範囲に関連する。ビットマップ内の各クラスタは、０ｘ８，０００（十進３２７６８）クラスタまたは０ｘ４０，０００（十進２６２１４４）セクタの論理範囲に関連する。

クラスタ割り当てステータスを維持すること
ホストからの書き込み操作が＄ｂｉｔｍａｐファイルについてのデータ属性の中のセクタに向けられるたびに、セクタの前のバージョンがストレージ装置から読み出されて、そのデータがホストによりちょうど書き込まれたばかりのデータと比較されなければならない。「１」状態から「０」状態へトグルした全てのビットが特定されなければならず、ホストによって割り当て解除されたクラスタの対応する論理アドレスが判定されなければならない。提案されたトリムコマンドなどのコマンドまたはＮＴＦＳメタデータ追跡が、ホストによるクラスタ割り当て解除があったことを示すたびに、ストレージアドレステーブル（ＳＡＴ）は、指定されたクラスタについてのアドレスの割り当て解除を記録するために更新されなければならない。

ＬＢＡアドレスのブロック全体のＤＬＢＡランへのＳＡＴマッピング
図１７に示されているＤＬＢＡアドレスのランへの有効なホストＬＢＡランだけのマッピングとは対照的に、ＳＡＴを作る代わりの方法が図３１〜３２に示され、ここではＬＢＡアドレスのメガブロックの中の全てのＬＢＡアドレスが、ＬＢＡアドレスが有効なデータと関連付けられているかいないかに関わらず、マッピングされる。有効なデータと関連付けられているＬＢＡアドレスの各ランのために別々のＬＢＡエントリをＳＡＴにおいて作る代わりに、各ＬＢＡアドレスメガブロックがＳＡＴ上で単一のエントリであるようにＬＢＡアドレスのメガブロックがＳＡＴにおいてマッピングされ得る。

図３１を参照すると、ＤＬＢＡ空間内のメガブロック３１０２が示され、単一の連続的ＬＢＡランがメガブロックにおいてＤＬＢＡ空間にマッピングされている。説明を簡単にするために、メガブロック３１０２は第１のメガページ３１０４の冒頭（バンク１および２のＰ１）に使用済データを含むと仮定される。ＬＢＡアドレスの１つの連続的ラン（図３２を参照）が、前述したように１バンクあたりに１メタページずつ全バンクに渡ってＬＢＡランを「ストライピング」するメガページ順に、メタページＰ１、バンク３から始まってメタページＰ３、バンク３まで、ＤＬＢＡアドレスにマッピングされている。図３１においてメガブロックの残りは使用済データを包含している。図に示されているように、各バンクは垂直に示されているそれ自身のＤＬＢＡラン（ＤＬＢＡランＢ１〜Ｂ４）を包含し、それは、（この図では水平の）メガページ書き込みアルゴリズムが連続的ＬＢＡアドレスの各々の引き続くメガページに沿っているために、それぞれのバンクでＤＬＢＡランのメタページ間でＬＢＡアドレスにおいては不連続である。図３２を参照すると、ＬＢＡアドレス空間３２０２のメガブロックは１つの連続的ＬＢＡラン３２０４を示し、これは、メタページにより分割されていて、図３１に示されているＤＬＢＡランおよびＤＬＢＡランの中のページで標識付けされている。したがって、ＬＢＡラン３２０４内の第１のメタページはＤＬＢＡランＢ１、第１のメタページ（バンク３）にマッピングされ、次にＬＢＡラン３２０４の次のメタページはＤＬＢＡランＢ２、ページ１（バンク４）にマッピングされるなどである。

図３２に示されているように、ＬＢＡアドレス空間内の完全なＬＢＡアドレスメガブロックは、ＳＡＴ内の単一のＬＢＡエントリ３２０６として記録され得る。この実施例におけるＬＢＡエントリ３２０６は、ＬＢＡアドレスメガブロックがマッピングされるＤＬＢＡランの数と、同じＳＡＴページ内の第１のＤＬＢＡエントリへのポインタ３２０８とを記録する。ＬＢＡアドレスメガブロックは、記憶装置に格納されているデータの断片化の程度に応じて、最大でＬＢＡアドレスメガブロック内のクラスの数までマッピングされ得る。

図３２の例では、ＬＢＡアドレスメガブロックは６個のＬＢＡランを含み、４個のランは有効なデータに割り当てられ（ＬＢＡオフセットＬ１〜Ｌ９から始まる陰影部分）、２個のランは未割り当てアドレスランである（ＬＢＡオフセット０およびＬ１０から始まる白色部分）。ＬＢＡアドレスメガブロックのための対応するＤＬＢＡエントリ３２１０は、ＤＬＢＡブロックによって示されるＤＬＢＡランのＤＬＢＡアドレス、アドレスオフセット（Ｐ１〜Ｐ３）および長さを対応するＬＢＡオフセットに関連付ける。各ＬＢＡランのための別々のＬＢＡエントリを記録し、有効なデータと関連付けられているＬＢＡランだけを記録する、図１７に関して前に論じられたＳＡＴのバージョンとは違って、ＬＢＡアドレスメガブロック内の全てのＬＢＡランが記録される。したがって、有効なデータに現在割り当てられていないＬＢＡアドレスブロック４８０内のＬＢＡランも、有効なデータに割り当てられているＬＢＡランも、記録される。図３２に示されているＳＡＴページのＤＬＢＡエントリ部分３２１０において、ＬＢＡアドレスの未割り当てセットの先頭を示すＬＢＡオフセットは、ＤＬＢＡアドレス空間内の「ＦＦＦＦＦＦＦＦ」値と対にされる。これは、未割り当てアドレスのためのリザーブ値を示すデフォルト十六進数を表す。前述した同じ総ＳＡＴ構造および機能も、図２２に関して論じられた基本的ＳＡＴ階層も、ＬＢＡアドレスメガブロックマッピングの実施例に当てはまるけれども、ＳＡＴページは、個別ＬＢＡラン対ＤＬＢＡラン情報ではなくてＬＢＡアドレスメガブロック対ＤＬＢＡランマッピング情報を表す。さらに、ＳＡＴ索引ページは、この実施例では、ＬＢＡアドレスブロック対ＳＡＴページマッピング情報を記憶する。

図３３を参照すると、サンプルであるＬＢＡアドレスフォーマット３３００が示されている。アドレスフォーマット３３００は３２ビットの長さとして示されているが、いくつかのアドレス長のうちのいずれも使用され得る。最下位ビットをメモリシステム１０２内のコントローラ１０８によってメタページにおけるＬＢＡアドレス３３０２に関連するものとして扱うことができ、アドレスの中の次のビットをバンク識別子３３０４を表すものとして扱うことができる。４個のバンク１０７Ａ〜１０７Ｄがある前述した例では、これはアドレスのうちの２ビットであり得る。次のビットをデータが関連付けられるべきメガブロック内のページ３３０６として扱うことができ、最後のビットをメガブロック識別子３３０８として解釈することもできる。一実施形態では、本願明細書で論じられたメガブロック書き込みアルゴリズムにおいて各バンク内でＬＢＡアドレスをインターリーブすることになるけれども、ＤＬＢＡアドレスがバンクの中で連続的であり得るように、コントローラはバンク識別子３３０４のビットを取り去ることができる。図３１とメガブロック書き込みアルゴリズムとを再び参照すれば、このことをより良く理解できるはずである。ホストデータがメモリシステム１０２に書き込まれるときに、現在の書き込みメガブロックの第１の利用可能な部分がバンク３のメタページＰ１であれば、アドレスがＰ１、バンク３へ、次に、Ｐ１、バンク３が完全に書き込まれた後にＰ１、バンク４へ、再マッピングされてゆくときにコントローラ１０８はバンク識別子ビットを除去する。書き込みアルゴリズムがホストデータをメガブロックの次のメガページ（バンク順に、バンク１〜４の各々の中のＰ２）の全体にわたって連続的にストライピングし続けてゆくとき、同じアドレス手続きが適用され得る。これは、各々の連続的ページを見たときにバンク内で左から右へ垂直下方へ各バンク内で連続的ＤＬＢＡアドレス指定が行われるという結果をもたらす。図１７および３２のＳＡＴバージョンは、データが記憶装置から正確に読み出され得るけれども、各バンク内のホストデータに対するフラッシング操作が各ブロックおよびバンク内の連続的ＤＬＢＡアドレスで管理され得るように、バンク情報を追跡する。

前の論議は、主として、ホストＬＢＡアドレス空間からＤＬＢＡアドレス空間（ストレージＬＢＡアドレス空間とも称される）への論理対論理マッピングが望ましいストレージアドレス再マッピングの実施例に焦点を合わせている。この論理対論理マッピングは、図１１および１２の構成に利用され得る。ＤＬＢＡアドレスに再マッピングされているホストデータおよびストレージ装置生成データ（例えば、ＳＡＴおよびＢＩＴ）は、ＤＬＢＡアドレス空間内のメタブロックに現在対応するそれぞれのバンクの中のメタブロックの物理アドレスに書き込まれる。本願明細書においてグループアドレステーブルあるいはＧＡＴと称されるこのテーブルは、ＤＬＢＡアドレス空間内の全ての論理ブロックについて１つずつのエントリを有すると共に１メタブロックの物理的ブロック粒状度を有する固定サイズのテーブルであり得る。一実施形態では、各バンク内の物理的ブロックへの論理ブロックマッピングが追跡され得るように各バンク１０７Ａ〜１０７Ｄはそれ自身のＧＡＴを有する。

論理対物理マッピング
前述したように、図１０の実施形態では、ストレージアドレス再マッピング（ＳＴＡＲ）アルゴリズムは、図１１〜１２の場合のようにそれぞれ記憶装置またはホスト上の別のアプリケーションにではなくて記憶装置のメモリマネージャに組み込まれている。コントローラ１０８は、ホストデータをホストＬＢＡからメモリシステム１０２内の各バンク１０７Ａ〜１０７Ｄ内の物理アドレスへ直接マッピングする。図１０の実施形態では、前に論じられたＤＬＢＡアドレスは、中間のＤＬＢＡ（ストレージＬＢＡ）アドレスではなくて物理メモリアドレスにより取って代わられ、ＳＡＴにおいて、ＤＬＢＡランはデータランにより取って代わられる。各バンクを横切るメガページに沿って「ストライプ」を成して物理アドレスのメガブロックにホストデータを書き込む動作は、物理的ブロックの各バンクのための独立のピンク色ブロック選択およびフラッシングと同じく、同じままである。図１０の論理対物理の実施形態は、前に論じられたＤＬＢＡアドレスおよびＤＬＢＡランの代わりに物理アドレスおよび物理的データランに関して同じＳＡＴおよびＢＩＴ（または制御）メタブロック構造も含む。図１０の構成におけるストレージ再マッピングアルゴリズムは、メモリシステム１０２またはホスト１００（それぞれ図１１および１２）上の別のアプリケーションではなくてメモリシステム１０２内のメモリコントローラ１０８の一部である。

従来の論理対物理ブロックマッピングでは、ホストデータの断片が論理アドレスのブロックに孤立して書き込まれるたびにガーベッジコレクション操作の間にデータの塊が再配置されなければならない。ストレージアドレス再マッピングアルゴリズムでは、データは常に（論理または物理的）ブロックが満たされるまで順次アドレスに書き込まれるので、ガーベッジコレクションは不要である。本願明細書で開示されたストレージアドレス再マッピングにおいて、フラッシング操作は書き込みプロセスによってはトリガされなくて、データが使用済みとなったことに応答してトリガされるだけである。したがって、本願明細書に記述されたストレージアドレス再マッピング機能を有するシステムにおいて、データ再配置オーバーヘッドは少ないはずである。フラッシング操作が最少量あるいは少なくともあるしきい値量未満の、有効なデータを有するピンク色ブロックのほうへ偏らされることと、別々のバンクが独立にフラッシング可能であることとの組み合わせを、再配置されなければならない有効なデータの量および関連するオーバーヘッドを減らすためにさらに役立てることができる。

パーソナルコンピュータにおいてソリッドステートディスクアプリケーションで経験されることのある、装置のＬＢＡアドレス空間内の関連性のないエリアにデータの短いバーストを書き込む必要があることを特徴とするランダム書き込みアプリケーションにおいてメモリシステムの性能を高めることのできる、マルチバンクメモリにおけるストレージアドレス再マッピングのためのシステムおよび方法が記述された。開示されたストレージアドレス再マッピングのある実施形態では、ホストデータは、ホストによって割り当てられた第１の論理アドレスから第２の論理アドレス空間内の連続する論理アドレスのメタブロックを有するメガブロックにマッピングされる。アドレスが完全にプログラムされたブロックと関連するデータが使用済みとなると、フラッシング手続きが開示され、各バンクについて独立に、最少量の有効なデータを有するかあるいはしきい値量未満の有効なデータを有するピンク色ブロックのグループからピンク色ブロックを選択して、それらのブロックの中の有効なデータを、それらのブロックをさらなるデータ書き込みのために使用するべく解放するために、再配置する。バンク内のピンク色ブロックの中の有効なデータは、同じバンク内の再配置ブロックへ、ホストによって割り当てられた論理アドレスに関わらず、選択されたピンク色ブロックの中でそれが出現する順に、連続的に書き込まれる。このように、ホストによって割り当てられた論理アドレスランを故意に統合しないことによってオーバーヘッドが低減され得る。ホストによって割り当てられた論理アドレスと第２の論理アドレスとの間のマッピングおよび関連するバンクも、フラッシングに起因するマッピングの爾後の変化も追跡するために、ストレージアドレステーブルが使用される。ホストによって割り当てられた論理アドレスが物理アドレスに直接マッピングされる実施形態では、ストレージアドレステーブルがその関係を追跡し、例えば特定のブロックが有効データおよび使用済データの両方を有するピンク色ブロックであるのか未書き込み容量だけを有する白色ブロックであるのかを追跡するために、ブロック情報テーブルが維持される。

したがって、以上の詳しい記述は限定をするものではなくて説明をするものと見なされるべきであることと、本発明の趣旨および範囲を定めるべく意図されているものは全ての同等物を含む添付の特許請求の範囲であることが理解されるべきであることとが意図されている。

Claims (18)

1. ホストシステムと、一緒に消去可能なメモリセルのブロックとして各々構成されているメモリセルの複数のバンクを有する再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法であって、
   前記ホストシステムにより割り当てられたホスト論理ブロックアドレス（ＬＢＡ）アドレスと関連付けられたデータを受け取るステップと、
   前記ホストＬＢＡアドレスと関連付けられたデータをアドレス指定するために連続的ストレージＬＢＡアドレスのメガブロックを割り当てるステップであって、連続的ストレージＬＢＡアドレスの前記メガブロックは、メモリセルの複数のバンクの各々の中のメモリセルの少なくとも１つのブロックを含むと共に割り当て時に未書き込み容量だけをアドレス指定する、割り当てるステップと、
   受け取られたデータのための前記ホストＬＢＡアドレスの各々を連続的ストレージＬＢＡアドレスのメガブロックに再マッピングするステップであって、各ストレージＬＢＡアドレスは、前記ホストＬＢＡアドレスに関わらず受け取られたデータが受け取られた順に受け取られたデータに連続的に順次割り当てられる、再マッピングするステップと、
   複数のバンクのうちの第１のバンクの中のブロックを複数のバンクのうちの第２のバンクの中のブロックをフラッシングすることとは独立にフラッシングするステップであって、前記第１のバンクの中のブロックをフラッシングすることは、有効なデータのためのホストＬＢＡアドレスを前記第１のバンクの中のブロックのストレージＬＢＡアドレスから第１の再配置ブロックの中の連続的ストレージＬＢＡアドレスへ再割り当てすることを含み、前記第２のバンクの中のブロックをフラッシングすることは、有効なデータのためのホストＬＢＡアドレスを前記第２のバンクの中のブロックのストレージＬＢＡアドレスから第２の再配置ブロックの中の連続的ストレージＬＢＡアドレスへ再割り当てすることを含む、フラッシングするステップと、
   を含む方法。
2. 請求項１記載の方法において、
   前記第１のバンクの中のブロックをフラッシングすることは、有効なデータのためのホストＬＢＡアドレスを前記第１のバンクの中のブロックのストレージＬＢＡアドレスから前記第１のバンクの中の再配置ブロックだけへ再割り当てすることをさらに含み、前記第２のブロックをフラッシングすることは、有効なデータのためのホストＬＢＡアドレスを前記第２のバンクの中のブロックのストレージＬＢＡアドレスから前記第２のバンクの中の再配置ブロックだけへ再割り当てすることを含む方法。
3. 請求項２記載の方法において、
   前記第１のバンクの中の連続的ストレージＬＢＡアドレスのブロックを新しい再配置ブロックとして割り当てるステップをさらに含み、連続的ストレージＬＢＡアドレスの前記新しい再配置ブロックは割り当て時に未書き込み容量だけと関連付けられ、前記新しい再配置ブロックの割り当ては、前記第１のバンクにおいて再配置ブロックの中のストレージＬＢＡアドレスを完全に割り当てたときにだけ行われる方法。
4. 請求項１記載の方法において、
   前記受け取られたデータのためのホストＬＢＡアドレスの各々を連続的ストレージＬＢＡアドレスのメガブロックへ再マッピングするステップは、ストレージＬＢＡアドレスを前記メガブロックのためのメガページ順にホストＬＢＡアドレスと関連付けることを含み、前記メガページは前記メガブロックの各ブロックの中のメタページを含む方法。
5. 請求項１記載の方法において、
   複数のバンクの各々のためにホストＬＢＡアドレスのストレージＬＢＡアドレスに対する関係を特定する相関情報を単一のストレージアドレステーブルに記録するステップをさらに含む方法。
6. 請求項５記載の方法において、
   前記相関情報は、有効なデータと関連付けられているホストＬＢＡアドレスのランと、ホストＬＢＡアドレスのランにマッピングされているストレージＬＢＡアドレスとだけを含む方法。
7. 請求項５記載の方法において、
   前記相関情報は、ホストＬＢＡアドレスのメガブロックの中の全てのホストＬＢＡアドレスのためのマッピング情報を含む方法。
8. 請求項５記載の方法において、
   前記単一のストレージアドレステーブルは少なくとも１つのストレージアドレステーブルブロックを含み、前のストレージアドレステーブル書き込みブロックが相関情報に完全に割り当てられたときに、割り当て時に未書き込み容量だけと関連付けられている新しいストレージアドレステーブル書き込みブロックを割り当てるステップをさらに含む方法。
9. 請求項８記載の方法において、
   前記前のストレージアドレステーブル書き込みブロックを包含するバンク以外のバンクにおいて前記新しいストレージアドレステーブル書き込みブロックを割り当てるステップをさらに含む方法。
10. ホストシステムと、一緒に消去可能なメモリセルのブロックとして各々構成されているメモリセルの複数のバンクを有する再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法であって、
    受け取られたホストデータのためのホスト論理ブロックアドレス（ＬＢＡ）アドレスをストレージＬＢＡアドレスのメガブロックに再マッピングするステップであって、ストレージＬＢＡアドレスの前記メガブロックはメモリセルの複数のバンクの各々の中のメモリセルの少なくとも１つのブロックを含み、受け取られたデータのためのホストＬＢＡアドレスは前記メガブロックの中でメガページ順にストレージＬＢＡアドレスに連続的に割り当てられ、各メガページは、前記ホストＬＢＡアドレスに関わらず受け取られたデータが受け取られた順に、前記メガブロックのブロックの各々の中のメタページを含む、再マッピングするステップと、
    複数のバンクの各々においてフラッシング操作を独立に実行するステップであって、前記フラッシング操作は、有効なデータのためのホストＬＢＡアドレスを特定のバンクの中のブロックのストレージＬＢＡアドレスから前記特定のバンクの中の再配置ブロックの中の連続的ストレージＬＢＡアドレスへ再割り当てする、フラッシング操作を独立に実行するステップと、
    を含む方法。
11. 請求項１０記載の方法において、
    複数のバンクの各々の中のピンク色ブロックを特定するステップであって、各ピンク色ブロックは、有効なデータと使用済データとの両方と関連付けられているストレージＬＢＡアドレスの完全に書き込まれたブロックを含む、特定するステップと、
    各バンクについて、前記バンクの中の特定されたピンク色ブロックのうちの１つを次のフラッシング操作のために独立に選択するステップと、
    をさらに含む方法。
12. 請求項１１記載の方法において、
    複数のバンクの各々においてブロック情報テーブルを維持するステップをさらに含み、バンクのための前記ブロック情報テーブルは、そのバンクの中のピンク色ブロックのリストを含む方法。
13. 請求項１０記載の方法において、
    前記フラッシング操作を独立に実行するステップは、複数のバンクのうちの１つのバンクにおいては第１のしきい値に基づいて、複数のバンクのうちの第２のバンクにおいては第２のしきい値に基づいて、フラッシング操作を開始することを含む方法。
14. 請求項１０記載の方法において、
    複数のバンクの各々のためにホストＬＢＡアドレスのストレージＬＢＡアドレスに対する関係を特定する相関情報を単一のストレージアドレステーブルに記録するステップをさらに含む方法。
15. 請求項１４記載の方法において、
    前記相関情報は、有効なデータと関連付けられているホストＬＢＡアドレスのランと、ホストＬＢＡアドレスのランにマッピングされているストレージＬＢＡアドレスとだけを含む方法。
16. 請求項１４記載の方法において、
    前記相関情報は、ホストＬＢＡアドレスのメガブロックの中の全てのホストＬＢＡアドレスのためのマッピング情報を含む方法。
17. 請求項１４記載の方法において、
    前記単一のストレージアドレステーブルは少なくとも１つのストレージアドレステーブルブロックを含み、前のストレージアドレステーブル書き込みブロックが相関情報に完全に割り当てられたときに、割り当て時に未書き込み容量だけと関連付けられている新しいストレージアドレステーブル書き込みブロックを割り当てるステップをさらに含む方法。
18. 請求項１７記載の方法において、
    前記前のストレージアドレステーブル書き込みブロックを包含するバンク以外のバンクにおいて前記新しいストレージアドレステーブル書き込みブロックを割り当てるステップをさらに含む方法。

Images