JP4362549B1 - Gradual garbage collection - Google Patents
Gradual garbage collectionDownload PDFInfo
- Publication number
- JP4362549B1 JP4362549B1JP2009522934AJP2009522934AJP4362549B1JP 4362549 B1JP4362549 B1JP 4362549B1JP 2009522934 AJP2009522934 AJP 2009522934AJP 2009522934 AJP2009522934 AJP 2009522934AJP 4362549 B1JP4362549 B1JP 4362549B1
- Authority
- JP
- Japan
- Prior art keywords
- block
- data
- garbage collection
- write
- volatile memory
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Classifications
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
- G06F12/023—Free address space management
- G06F12/0238—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
- G06F12/0246—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory in block erasable memory, e.g. flash memory
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
- G06F13/10—Program control for peripheral devices
- G—PHYSICS
- G11—INFORMATION STORAGE
- G11C—STATIC STORES
- G11C16/00—Erasable programmable read-only memories
- G11C16/02—Erasable programmable read-only memories electrically programmable
- G11C16/06—Auxiliary circuits, e.g. for writing into memory
- G11C16/10—Programming or data input circuits
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
- G06F2212/72—Details relating to flash memory management
- G06F2212/7203—Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
- G06F2212/72—Details relating to flash memory management
- G06F2212/7205—Cleaning, compaction, garbage collection, erase control
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Memory System (AREA)
- Read Only Memory (AREA)
- Techniques For Improving Reliability Of Storages (AREA)
Abstract
Translated fromJapaneseDescription
Translated fromJapanese本発明は、一般的にはメモリ動作に関し、特に段階的ガーベッジコレクション動作を実行する方法およびシステムに関する。 The present invention relates generally to memory operations, and more particularly to a method and system for performing a stepped garbage collection operation.
不揮発性メモリ記憶システムでは、メモリに格納されているデータのブロックは、メモリの記憶容量を再生利用するために定期的にガーベッジコレクション（すなわち、圧縮または整理統合）される。代表的なガーベッジコレクション動作では、ブロックからの有効なデータが他のブロックにコピーされる。有効なデータが転送された後、オリジナルブロックは記憶容量を提供するために消去される。現在、書き込み動作は、不揮発性メモリ記憶システムをトリガしてガーベッジコレクション動作を実行させることができる。ホストは、書き込み動作の実行のために一定量の時間を許し、（トリガされたならば）ガーベッジコレクションを含む。例えば、セキュアデジタルプロトコルは、その時間量を２５０ミリ秒に制限する。不揮発性メモリ記憶システムが書き込み動作においてこの一定量の時間を越えれば、タイムアウトエラーに帰着する可能性がある。 In a non-volatile memory storage system, blocks of data stored in memory are periodically garbage collected (ie, compressed or consolidated) to reclaim the memory capacity of the memory. In a typical garbage collection operation, valid data from a block is copied to another block. After valid data is transferred, the original block is erased to provide storage capacity. Currently, a write operation can trigger a non-volatile memory storage system to perform a garbage collection operation. The host allows a certain amount of time to perform the write operation and includes garbage collection (if triggered). For example, secure digital protocols limit that amount of time to 250 milliseconds. If the non-volatile memory storage system exceeds this certain amount of time in a write operation, it may result in a timeout error.
メモリブロックのサイズは、増大する容量、より高度の並列性、およびダイサイズのスケーリングに起因して大きくなってきている。従って、より多くのデータが転送されるので書き込み動作の実行により長い時間がかかるようになっている。従って、ガーベッジコレクション動作は、書き込み動作に割り当てられた一定量の時間を容易に超える可能性がある。その結果として、ガーベッジコレクション動作を実行するための時間の量がその一定量の時間を超えるときにタイムアウトエラーを防止する必要がある。 Memory block sizes are becoming larger due to increasing capacity, higher parallelism, and die size scaling. Therefore, since more data is transferred, it takes longer time to execute the write operation. Thus, a garbage collection operation can easily exceed a certain amount of time assigned to a write operation. As a result, timeout errors need to be prevented when the amount of time for performing a garbage collection operation exceeds that fixed amount of time.
本発明の種々の実施形態は、段階的ガーベッジコレクションの方法および／またはシステムを提供する。実施形態が、方法、回路、システム、あるいは装置を含む多くの仕方で実現され得ることが理解されるべきである。本発明のいくつかの実施形態が以下に記載される。 Various embodiments of the present invention provide a method and / or system for staged garbage collection. It is to be understood that the embodiments can be implemented in many ways, including a method, circuit, system, or apparatus. Several embodiments of the invention are described below.
本発明の１つの実施形態に従って、不揮発性メモリ記憶システムを動作させる方法が提供される。この方法では、データを書き込むために書き込みコマンドが受け取られる。書き込みコマンドには、書き込みコマンドの実行を完了させるためのタイムアウト期間が割り当てられる。このタイムアウト期間内に、ガーベッジコレクション動作の一部が実行される。書き込みコマンドに関連付けられたデータは、不揮発性メモリ記憶システムに関連付けられたバッファに書き込まれる。 In accordance with one embodiment of the present invention, a method for operating a non-volatile memory storage system is provided. In this method, a write command is received to write data. The write command is assigned a timeout period for completing execution of the write command. During this timeout period, part of the garbage collection operation is performed. Data associated with the write command is written to a buffer associated with the non-volatile memory storage system.
本発明の他の実施形態および利点は、本発明の原理を例を挙げて示す添付図面と関連して考慮される以下の詳細な記述から明らかである。 Other embodiments and advantages of the present invention will become apparent from the following detailed description considered in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.
本発明は、添付図面と関連する以下の詳細な記述によって容易に理解されるであろう。同様の参照数字は同様の構造要素を示す。 The present invention will be readily understood by the following detailed description in conjunction with the accompanying drawings. Like reference numerals indicate like structural elements.
添付図面と共に１つ以上の実施形態の詳細な記述が以下に提供される。この詳細な記述は、そのような実施形態と関連して提供されるけれども、特定の実施形態に限定されない。範囲は特許請求の範囲のみにより限定され、多くの変形例、改変、および同等物が含まれる。完全な理解を提供するために以下の記述において多くの特定の細部が明らかにされる。これらの細部は例示を目的として提供され、記述された実施形態はこれらの細部の一部または全部を用いずに特許請求の範囲に従って実現され得る。明瞭性を目的として、記述を不必要に分かりにくくしないように、実施形態に関連する技術分野で知られている技術的事項は詳しくは記述されていない。 A detailed description of one or more embodiments is provided below along with the accompanying drawings. This detailed description is provided in connection with such embodiments, but is not limited to any particular embodiment. The scope is limited only by the claims and includes many variations, modifications, and equivalents. In the following description, numerous specific details are set forth in order to provide a thorough understanding. These details are provided for the purpose of example, and the described embodiments may be implemented according to the claims without some or all of these details. For the purpose of clarity, technical material that is known in the technical fields related to the embodiments has not been described in detail so that the description is not unnecessarily obscured.
ここに記載されている実施形態は、段階的ガーベッジコレクションの方法および／またはシステムを提供する。一般的に、ガーベッジ動作は複数の段階に分割され得る。ガーベッジコレクション動作の段階（あるいは部分）は、複数のタイムアウト期間にわたって実行され得る。１つの実施形態では、以下でより詳しく説明されるように、ガーベッジコレクション動作の一部分は１タイムアウト期間内に実行され、書き込みコマンドから受け取られるデータはバッファに格納され得る。 The embodiments described herein provide a method and / or system for staged garbage collection. In general, the garbage operation can be divided into multiple stages. The stage (or portion) of the garbage collection operation may be performed over multiple timeout periods. In one embodiment, as described in more detail below, a portion of the garbage collection operation may be performed within one timeout period and data received from a write command may be stored in a buffer.
図１は、本発明の１つの実施形態に従う、不揮発性メモリ記憶システムの例の簡略ブロック図である。ホストシステム（例えば、デスクトップコンピュータ、オーディオプレーヤ、デジタルカメラ、および他の計算装置）は、不揮発性メモリ記憶システム１０２にデータを書き込み、またそこからデータを読み出すことができる。不揮発性メモリ記憶システム１０２は、ホストに組み込まれるか、あるいはホストに取り外し可能に接続され得る。図１に示されているように、不揮発性メモリ記憶システム１０２は、メモリ１１８と通信するメモリコントローラ１１０を含む。一般に、メモリコントローラ１１０はメモリ１１８の動作を制御する。動作の例は、データを書き込む（あるいはプログラムする）動作、データを読み出す動作、データを消去する動作、データをベリファイする動作、ガーベッジコレクション動作を処理する動作、および他の動作を含む。メモリコントローラ１１０はホストインターフェイス１０４を通してシステムバス１２６とインターフェイスするバス１２４を含み、メモリコントローラはメモリインターフェイス１０８を通してメモリ１１８とインターフェイスする。ホストインターフェイス１０４、プロセッサ１０６（例えば、マイクロプロセッサ、マイクロコントローラ、および他のプロセッサ）、メモリインターフェイス１０８、ランダムアクセスメモリ（ＲＡＭ）１１２、誤り訂正符号（ＥＣＣ）回路１１４、および読み出し専用メモリ（ＲＯＭ）１１６は、バス１２４を通して通信する。ＲＯＭ１１６は、メモリ１１８の動作を制御するためのプログラム命令を含む記憶システムファームウェアを記憶することができる。プロセッサ１０６は、ＲＯＭ１１６からロードされたプログラム命令を実行するように構成される。記憶システムファームウェアはＲＡＭ１１２に一時的にロードされ、そして付加的に、ＲＡＭはホストとメモリ１１８との間で転送されるデータをバッファリングするために使用され得る。ＥＣＣ回路１１４は、ホストとメモリ１１８との間でメモリコントローラ１１０を通るエラーがないかを調べる。エラーが発見されたならば、ＥＣＣ回路１１４は数個のエラービットを訂正することができ、その個数は使用されるＥＣＣアルゴリズムによる。 FIG. 1 is a simplified block diagram of an example non-volatile memory storage system, according to one embodiment of the present invention. Host systems (eg, desktop computers, audio players, digital cameras, and other computing devices) can write data to and read data from the non-volatile
メモリ１１８は、アレイロジック１２０、不揮発性メモリセルアレイ１２２、およびメモリセルアレイ１２３を含むことができる。不揮発性メモリセルアレイ１２２は、いろいろな不揮発性メモリ構造および技術を含むことができる。不揮発性メモリ技術の例として、フラッシュメモリ（例えば、ＮＡＮＤ、ＮＯＲ、マルチレベルセル（ＭＬＣ）、分割ビット線ＮＯＲ（ＤＩＮＯＲ）、ＡＮＤ、大容量結合比（ＨｉＣＲ）、非対称無接点トランジスタ（ＡＣＴ）、他のフラッシュメモリ）、消去可能でプログラム可能な読み出し専用メモリ（ＥＰＲＯＭ）、電気的に消去可能でプログラム可能な読み出し専用メモリ（ＥＥＰＲＯＭ）、読み出し専用メモリ（ＲＯＭ）、一回だけプログラム可能なメモリ（ＯＴＰ）、および他のメモリ技術を含むことができる。 The
１つの実施形態では、メモリ１１８は、付加的に、バッファを記憶するように構成されるメモリセルアレイ１２３を含むことができる。バッファは、段階的ガーベッジコレクション動作においてデータを記憶するように構成される。以下でより詳しく説明されるように、段階的ガーベッジコレクション動作では、書き込みコマンドから受け取られた新しいデータがバッファに格納され得る。本発明の実施形態に従って、バッファはＲＡＭ１１２および／または不揮発性メモリセルアレイ１２２に置かれてもよいということが理解されるべきである。不揮発性メモリセルアレイ１２２と同様に、メモリセルアレイ１２３はいろいろなメモリ構造および技術を含むことができる。メモリセルアレイ１２３はバッファリング動作のために構成されるので、メモリセルアレイは不揮発性メモリアレイ１２２より高速で、より経済的で、かつより信頼できる異なるメモリ構造を組み入れることができる。 In one embodiment, the
アレイロジック１２０は、メモリコントローラ１１０を不揮発性メモリセルアレイ１２２およびメモリセルアレイ１２３とインターフェイスさせ、そして、例えばアドレス指定、データ転送およびセンシング、および他のサポートを不揮発性メモリセルアレイおよびメモリセルアレイに提供することができる。不揮発性メモリセルアレイ１２２およびメモリセルアレイ１２３をサポートするために、アレイロジック１２０は行デコーダ、列デコーダ、電荷ポンプ、ワード線電圧発生器、ページバッファ、入出力バッファ、アドレスバッファ、および他の回路を含むことができる。
図２は、メモリセルアレイのプレーンへの編成の簡略ブロック図である。１つ以上のメモリセルアレイは、複数のプレーンまたはサブアレイに分割され得る。図２の例では、１つのメモリセルアレイが４つのプレーン２０２〜２０５に分割されている。１，２，８，１６，あるいはそれ以上など、他の数のプレーンが不揮発性メモリ記憶システムに存在し得ることが理解されるべきである。各プレーン２０２，２０３，２０４，または２０５は、それぞれのプレーン２０２〜２０５内に位置するブロック２１０〜２１３および２２０〜２２３のようなメモリセルのブロックに分割され得る。メモリセルのブロックは、物理的に一緒に消去可能な最小数のメモリセルである。並列性を高めるために、ブロックはより大きなメタブロック単位で操作され、その場合各プレーン２０２，２０３，２０４，または２０５からの１ブロックが互いに論理的にリンクされて１つのメタブロックを形成する。例えば、４つのブロック２１０〜２１３が互いに論理的にリンクされて１つのメタブロックを形成することができる。さらに、メタブロックを形成するために使用されるブロックは、プレーン２０２〜２０５のようなそれぞれのプレーン内のいろいろな位置からのブロックであり得る。例えば、それぞれのプレーン２０２〜２０５内のいろいろな位置からの４つのブロック２２０〜２２３は、論理的に互いにリンクされて他の１つのメタブロックを形成することができる。メタブロックは不揮発性メモリ記憶システム内の４つの論理プレーン２０２〜２０５の全てにわたって広がることができ、あるいは不揮発性メモリ記憶システムは１つ以上の異なるプレーン内の１つ以上のブロックから動的にメタブロックを形成することができる。 FIG. 2 is a simplified block diagram of the organization of the memory cell array into planes. One or more memory cell arrays may be divided into a plurality of planes or subarrays. In the example of FIG. 2, one memory cell array is divided into four
図３は、メモリセルのページの簡略ブロック図である。ブロック２１０〜２１３のような各々のブロックは、メモリセルのページにさらに分割されている。図３に示されているように、各ブロック２１０，２１１，２１２，あるいは２１３は８ページＰ０〜Ｐ７に分割されている。代わりに、各ブロック２１０，２１１，２１２，あるいは２１３の中にメモリセルの１６ページ、３２ページ、あるいはもっと多くのページがあり得る。不揮発性メモリ記憶システムの動作並列性を高めるために、２つ以上のブロックの中のページが論理的にリンクされてメタページにされてもよい。例えば、４つのブロック２１０〜２１３の各々からの、Ｐ１のような１つずつのページでメタページが形成され得る。メタページは不揮発性メモリ記憶システム内の全てのプレーンにわたって広がることができ、あるいは不揮発性メモリ記憶システムは１つ以上の異なるプレーン内の１つ以上の別々のブロック内の１つ以上のページからメタページを動的に形成することができる。 FIG. 3 is a simplified block diagram of a page of memory cells. Each block, such as blocks 210-213, is further divided into pages of memory cells. As shown in FIG. 3, each
図４は、メモリセルのセクタの簡略ブロック図である。ページは１つ以上のセクタにさらに分割され得る。各ページ内のデータの量は、整数個の１つ以上のセクタのデータであることができ、各セクタは５１２バイトのデータを記憶することができる。図４は、２つのセクタ４０２および４０４に分割されたページ４０１を示す。各セクタ４０２または４０４は、５１２バイトのサイズであり得るデータ４０６と、データに関連付けられたオーバーヘッドデータ４０５とを含む。オーバーヘッドデータ４０５のサイズは１６バイトであることができ、例えば、プログラミング中にデータ４０６から計算されたＥＣＣと、データに関連付けられた論理アドレスと、ブロックが消去され再プログラムされた総回数と、制御フラグと、動作電圧レベルと、データに関連付けられた他の情報とを記憶することができる。 FIG. 4 is a simplified block diagram of a sector of a memory cell. A page may be further divided into one or more sectors. The amount of data in each page can be an integer number of one or more sectors of data, and each sector can store 512 bytes of data. FIG. 4 shows a page 401 that is divided into two sectors 402 and 404. Each sector 402 or 404 includes
図５は、ホストと不揮発性メモリ記憶システムとの間の論理インターフェイスの簡略ブロック図である。連続的論理アドレス空間５１２はメモリに格納され得るデータのためにアドレスを提供する。ホストに見られる論理アドレス空間５１２は、データのクラスタのインクリメントに分割され得る。各クラスタは、例えば４セクタと６４セクタとの間の数個のセクタのデータを含むことができる。 FIG. 5 is a simplified block diagram of a logical interface between a host and a non-volatile memory storage system. The continuous logical address space 512 provides addresses for data that can be stored in memory. The logical address space 512 seen by the host can be divided into increments of clusters of data. Each cluster may contain several sectors of data, for example between 4 and 64 sectors.
図５に示されているように、ホスト上で実行されるアプリケーションプログラムは３つのデータファイル１，２，および３を作る。ファイル１，２，および３は、データの順序集合であることができて、一意の名前または他のリファレンスにより識別される。ホストは、他のファイルに既に配置されていない論理アドレス空間をファイル１に割り当てる。ここで、ファイル１は１つの連続的範囲の利用可能な論理アドレスを割り当てられているように示されている。 As shown in FIG. 5, the application program executed on the host creates three
ホストがファイル１の後にファイル２を作るとき、ホストは論理アドレス空間５１２の中の２つの異なる範囲の連続的アドレスを同様に割り当てる。ホストは、ファイル１,２，または３のようなファイルに連続的な論理アドレスを割り当てることはできず、既に他のファイルに割り当てられている論理アドレス範囲の間の論理アドレスのフラグメントを割り当てることができる。図５の例は、前にファイル１および２および他のデータに割り当てられていなかった論理アドレス空間５１２の中の１つの不連続的なアドレス範囲が他の１つのファイル３に割り当てられることを示している。 When the host creates
ホストはファイル割り当てテーブル（ＦＡＴ）を維持することによって論理アドレス空間５１２を追跡することができ、ここで変換によりファイル１〜３のような種々のデータファイルにホストによって割り当てられた論理アドレスが維持される。ホストはファイル１〜３を、不揮発性メモリ記憶システムがファイルを格納した物理的位置によってではなくて、それらの論理アドレスにより、参照する。一方、不揮発性メモリ記憶システムは、データが書き込まれている論理アドレスの部分によってファイル１〜３を参照するのであって、ファイルに割り当てられた論理アドレスによってファイルを参照するのではない。不揮発性メモリ記憶システムは、ホストにより提供された論理アドレスを、ホストからのデータが格納されるメモリセルアレイ５０２内の一意の物理アドレスに変換する。ブロック５０４は、これらの論理アドレス−物理アドレス変換のテーブルを表し、これは不揮発性メモリ記憶システムにより維持される。 The host can track the logical address space 512 by maintaining a file allocation table (FAT), where the translation maintains the logical addresses assigned by the host to various data files such as files 1-3. The The host references files 1-3 by their logical addresses, not by the physical location where the non-volatile memory storage system stored the files. On the other hand, the nonvolatile memory storage system refers to the
図６は、本発明の１つの実施形態に従う、段階的ガーベッジコレクションのための動作の概略のフローチャート図である。特定のホスト論理アドレスに格納されたデータはオリジナルの格納されているデータが陳腐化したときに新しいデータで上書きされ得るということが理解されるべきである。不揮発性メモリ記憶システムは、これに応じて、その新しいデータを更新ブロックに書き込み、そしてその新しいデータが格納された新しい物理的ブロックを特定するためにこれらの論理アドレスについて論理アドレス−物理アドレステーブルを変更する。これらの論理アドレスに存するオリジナルデータを含むブロックはその後消去され、付加的なデータの格納のために利用可能にされる。そのような消去は、書き込み動作の前に実行され得る。その結果として、メモリコントローラは、所与の論理アドレスに存するデータが新データが同じ論理アドレスに書き込まれた後にホストによって陳腐化あるいは無効にされたことを知る。従って、メモリの多数のブロックがある期間にわたって無効のデータを記憶しているということがあり得る。 FIG. 6 is a schematic flowchart diagram of operations for staged garbage collection, in accordance with one embodiment of the present invention. It should be understood that data stored at a particular host logical address can be overwritten with new data when the original stored data becomes obsolete. In response, the non-volatile memory storage system writes the new data to the update block and creates a logical address-physical address table for these logical addresses to identify the new physical block where the new data is stored. change. The block containing the original data present at these logical addresses is then erased and made available for storing additional data. Such erasure can be performed before the write operation. As a result, the memory controller knows that the data residing at a given logical address has been stale or invalidated by the host after the new data has been written to the same logical address. Thus, it is possible that many blocks of memory have stored invalid data over a period of time.
ブロックおよびメタブロックのサイズは増大しつつあり、この増大は、個々のデータ書込みの大きな部分が、１つのメタブロックの記憶容量より少ない、また多くの場合に１つのブロックのものよりも少ない量のデータを格納するという結果をもたらす。不揮発性メモリ記憶システムは、新しいデータを消去済みプールメタブロックに向け得るので、そのような向け方はブロックまたはメタブロックの部分が満たされないという結果をもたらし得る。新データが他の１つのメタブロックに格納されているあるデータの更新であるならば、他の１つのメタブロックからのデータの、新データメタページのものに連続する論理アドレスを有する残りの有効なメタページも新しいメタブロックに論理アドレス順にコピーされる。旧メタブロックは、他の有効なデータメタページを保つことができる。従って、個々のメタブロックのあるメタページのデータが陳腐化あるいは無効化され、同じ論理アドレスが異なるメタブロックに書き込まれて新データに取って代わられ得る。 The size of blocks and metablocks is increasing and this increase is due to the fact that a large portion of each data write is less than the storage capacity of one metablock and often less than that of one block. Resulting in storing data. Since non-volatile memory storage systems can direct new data to the erased pool metablock, such orientation can result in the block or portion of the metablock not being filled. If the new data is an update of some data stored in one other metablock, the remaining valid with the logical address consecutive to that of the new data metapage of the data from the other one metablock Metapages are also copied to the new metablock in logical address order. Old metablocks can hold other valid data metapages. Thus, the data on a metapage with individual metablocks can become obsolete or invalidated, and the same logical address can be written into different metablocks to replace the new data.
論理アドレス空間にデータを格納するための充分な物理メモリ空間を維持するために、そのようなデータは定期的にガーベッジコレクション（すなわち、圧縮または整理統合）され得る。一般に、ガーベッジコレクション動作は、ブロックから有効なデータを読み出してその有効なデータを新しいブロックに書き込むことを含み、その過程で無効なデータを無視する。例えば、図５のブロック図では、新データファイル３の作成は旧データファイル３を陳腐化する。旧データファイル３は、旧データファイル３により使用されていた物理容量を再生利用するために、消去され得る。しかし、そのような消去動作は、ファイル２と旧ファイル３とが同じ物理的ブロックに格納されていたならば、ガーベッジコレクション動作をトリガする。 In order to maintain sufficient physical memory space for storing data in the logical address space, such data can be periodically garbage collected (ie, compressed or consolidated). In general, a garbage collection operation includes reading valid data from a block and writing the valid data to a new block, ignoring invalid data in the process. For example, in the block diagram of FIG. 5, the creation of the new data file 3 makes the
図６に戻って、不揮発性メモリ記憶システムは、書き込みコマンドに割り当てられたタイムアウト期間の中でガーベッジコレクション動作を実行することができる。ガーベッジコレクション動作が１タイムアウト期間内に完了され得なければ、本発明の１つの実施形態に従って、その１つのガーベッジコレクション動作は数個の異なる段階（または部分）に分割され得る。ここで、不揮発性メモリ記憶システムは、複数の書き込みコマンドに割り当てられたタイムアウト期間を用いてガーベッジコレクション動作の部分を実行する。換言すれば、不揮発性メモリ記憶システムは、１つのガーベッジコレクション動作の部分を実行するために、複数の書き込みコマンドに割り当てられたタイムアウト期間を利用する。 Returning to FIG. 6, the non-volatile memory storage system may perform a garbage collection operation within the timeout period assigned to the write command. If a garbage collection operation cannot be completed within one timeout period, that one garbage collection operation can be divided into several different stages (or portions) according to one embodiment of the present invention. Here, the non-volatile memory storage system performs a portion of the garbage collection operation using a timeout period assigned to a plurality of write commands. In other words, the non-volatile memory storage system utilizes a timeout period assigned to multiple write commands to perform a portion of one garbage collection operation.
図６に示されているように、新しいデータを書き込む書き込みコマンドが動作６０２で受け取られる。本願明細書で使用される“新しいデータ”という用語は、メモリに書き込まれるべき書き込みコマンドから不揮発性メモリ記憶システムにより受け取られるデータとして定義される。書き込みコマンドには、書き込みコマンドの実行を完了させるためのタイムアウト期間が割り当てられる。換言すれば、タイムアウト期間は、書き込みコマンドの実行のために割り当てられた期間である。割り当てられるタイムアウト期間の一例は２５０ミリ秒である。書き込みコマンドは、シングルセクタ書き込みコマンドまたはマルチセクタ書き込みコマンドであり得る。以下でより詳しく説明されるように、シングルセクタ書き込みコマンドでは、新しいデータは単一セクタとしてメモリ中のランダムなアドレスに書き込まれ得る。マルチセクタ書き込みコマンドでは、連続的な論理アドレスを有する新しいデータの複数のセクタがメモリに書き込まれる。 As shown in FIG. 6, a write command to write new data is received at
１つのガーベッジコレクション動作がタイムアウト期間内に完了され得なければ、動作６０４に示されているように、ガーベッジコレクション動作の一部分が書き込みコマンドに割り当てられたタイムアウト期間内に実行される。ガーベッジコレクションの残りの部分は、後のタイムアウト期間に完了させられ得る。例えば、図７は、本発明の１つの実施形態に従う、複数の部分７８０および７８１に分割された１つのガーベッジコレクション動作の例の簡略ブロック図を示す。図７に示されているように、不揮発性メモリ記憶システムは、マルチセクタ書き込みコマンド７０４を受け取り、その後に新しいデータの複数のセクタ７６０〜７６２がメモリに格納されるべく受け取られる。データの各セクタ７６０，７６１，または７６２が受け取られた後にビジー信号７０２がアサートされる。不揮発性メモリ記憶システムは書き込みコマンドの実行を許すためにビジー信号７０２をアサートするが、それは（必要ならば）ガーベッジコレクション動作と他の動作とを含むことができる。ホストは、ビジー信号７０２がアサートされているときには他のコマンドまたは追加のデータを不揮発性メモリ記憶システムに送らない。ホストは書き込みコマンドの実行のために限られた一定量の時間（すなわち、タイムアウト期間７５０〜７５２）を与えるので、不揮発性メモリ記憶システムはデータの各セクタ７６０，７６１，または７６２が受け取られた後に限られた量の時間にわたってビジー信号７０２をアサートすることができる。ビジー信号がタイムアウト期間７５０，７５１，または７５２より長くアクティブであり続ければ、ホストは書き込みコマンドを反復するかあるいはプロセスをアボートすることができる。従って、不揮発性メモリ記憶システムは、タイムアウト期間７５０，７５１，または７５２より長くビジー信号７０２をアサートすることはできない。データの複数のセクタ７６０〜７６２の書き込みの完了後のビジー信号７０２の解除は、ホストが不揮発性メモリ記憶システムとさらに通信することを可能にする。 If one garbage collection operation cannot be completed within the timeout period, a portion of the garbage collection operation is performed within the timeout period assigned to the write command, as shown in operation 604. The remainder of the garbage collection can be completed at a later timeout period. For example, FIG. 7 shows a simplified block diagram of an example of a single garbage collection operation divided into a plurality of portions 780 and 781, in accordance with one embodiment of the present invention. As shown in FIG. 7, the non-volatile memory storage system receives a
図７をなお参照すると、ガーベッジコレクションの部分７８０および７８１は複数のタイムアウト期間７５０〜７５２の間に割り当てられ得る。換言すれば、不揮発性メモリ記憶システムは、１つのガーベッジコレクション動作の各部分７８０または７８１を実行するために各タイムアウト期間７５０，７５１，または７５２を利用することができる。例えば、１つのガーベッジコレクションの第１の部分７８０は第１のタイムアウト期間７５０の間に実行される。ここで、有効なデータの部分が第１のタイムアウト期間７５０中に１ブロックから他の１ブロックにコピーされ得る。第２のタイムアウト期間７５１において、第１のタイムアウト期間に開始された前のガーベッジコレクション動作が続けられる。不揮発性メモリ記憶システムは、前のガーベッジコレクションが完了するまで、タイムアウト期間７５１の間に前のガーベッジコレクション動作の第２の部分７８１を実行する。前のガーベッジコレクションは、有効なデータの残りの部分または最後の部分を１ブロックから他の１ブロックにコピーすることによって完了させられ得る。前のガーベッジコレクション動作が第２のタイムアウト期間７５１内に完了させられ得なければ、不揮発性メモリ記憶システムはガーベッジコレクション動作を完了させるために、第３のタイムアウト期間７５２のような後のタイムアウト期間を使用することができる。マルチセクタ書き込みコマンド７０４の終わりに、不揮発性メモリ記憶システムは、ストップコマンド７０６が受け取られた後に、データの全てのセクタ７６０〜７６２がメモリセルアレイに書き込まれるまでビジー信号をアサートすることができる。図７はマルチセクタ書き込みコマンドに関連する動作を示しているということに留意するべきである。以下でより詳しく説明されるように、実行されるガーベッジコレクション動作は、シングルセクタ書き込みコマンドとマルチセクタ書き込みコマンドとについては異なり得る。例えば、以下でより詳しく説明されるように、新しいデータを格納するために使用されるバッファのタイプは、受け取られた書き込みコマンドがシングルセクタ書き込みコマンドであるのか、それともマルチセクタ書き込みコマンドであるのかによる。 Still referring to FIG. 7, garbage collection portions 780 and 781 may be allocated during a plurality of timeout periods 750-752. In other words, the non-volatile memory storage system can utilize each
図６に戻って、ガーベッジコレクション動作の一部分がタイムアウト期間内に実行された後、動作６０６で、書き込み動作から受け取られた新しいデータは不揮発性メモリ記憶システムに関連付けられたバッファに格納され得る。１つの実施形態では、バッファは不揮発性メモリセルアレイ（例えば、図１に示されている不揮発性メモリアレイ１２２）に関連付けられたデータ構造であり得る。データ構造の例は、書き込みバッファブロックのような不揮発性メモリセルアレイのブロックを含み、これは以下でより詳しく記載される。他の１つの実施形態では、バッファは揮発性メモリセルアレイのブロックであり得る。例えば、新しいデータは、不揮発性メモリ記憶システムに関連付けられたＲＡＭ（例えば、図１に示されているＲＡＭ１１２）に置かれたブロックに格納され得る。さらに他の１つの実施形態では、前に論じられたように、新しいデータは別のメモリセルアレイ（例えば、図１に示されているメモリセルアレイ１２３）に置かれたブロックに格納され得る。 Returning to FIG. 6, after a portion of the garbage collection operation is performed within the timeout period, at operation 606 new data received from the write operation may be stored in a buffer associated with the non-volatile memory storage system. In one embodiment, the buffer may be a data structure associated with a non-volatile memory cell array (eg, non-volatile memory array 122 shown in FIG. 1). Examples of data structures include non-volatile memory cell array blocks, such as write buffer blocks, which are described in more detail below. In another embodiment, the buffer may be a block of a volatile memory cell array. For example, new data may be stored in blocks located in RAM (eg,
図８は、本発明の１つの実施形態に従う、段階的ガーベッジコレクションを実行するための詳細な動作のフローチャート図である。図８に示されているように、新しいデータをメモリに書き込むために書き込みコマンドが動作８０２で受け取られる。１つの実施形態では、書き込みコマンドはシングルセクタ書き込みコマンドである。ある環境では、以下でより詳しく説明されるように、他の１つの実施形態に従って、書き込みコマンドはマルチセクタ書き込みコマンドでもあり得る。書き込みコマンドが受け取られた後、不揮発性メモリ記憶システムは動作８０４でビジー信号をアサートする。 FIG. 8 is a flowchart diagram of detailed operations for performing tiered garbage collection, according to one embodiment of the present invention. As shown in FIG. 8, a write command is received at
書き込みコマンドが実行される前に、動作８０６でガーベッジコレクション期間の間にガーベッジコレクション動作の一部分が実行される。例えば、１つの実施形態では、１つ以上のブロックがガーベッジコレクション動作のために選択される。その１つ以上のブロックは有効なデータおよび／または無効なデータを含み得る。有効なデータは、ガーベッジコレクション期間中に第２のブロックにコピーされる。ガーベッジコレクション動作に割り当てられたガーベッジコレクション期間と、コピーされるべき有効なデータの量とにより、有効なデータの全部または有効なデータの一部分が第２のブロックにコピーされる。ガーベッジコレクション動作のために割り当てられたガーベッジコレクション期間は、
ガーベッジコレクション期間＝タイムアウト期間−Ｔｐｒｏｇ
と表現することができ、ここでタイムアウト期間は、前に論じられたように、固定された、限られた期間である。Ｔｐｒｏｇは、新しいデータをメモリに（例えば、バッファに）書き込むことに関連付けられた最大プログラミング時間であるか、あるいは不揮発性メモリ記憶システムが新しいデータをメモリに書き込むために必要とする最大時間である。その結果として、１つの実施形態では、不揮発性メモリ記憶システムは、有効なデータを１つ以上のブロックから第２のブロックにコピーするための時間の量を追跡する。不揮発性メモリ記憶システムは、時間がガーベッジコレクション期間を超える前にコピーをやめる。A portion of the garbage collection operation is performed during the garbage collection period at
Garbage collection period = timeout period-Tprog
Where the timeout period is a fixed, limited period as previously discussed. Tprog is the maximum programming time associated with writing new data to memory (eg, to a buffer) or the maximum time that a non-volatile memory storage system needs to write new data to memory. As a result, in one embodiment, the non-volatile memory storage system tracks the amount of time to copy valid data from one or more blocks to the second block. Non-volatile memory storage systems cease copying before the time exceeds the garbage collection period.
ガーベッジコレクション動作がガーベッジコレクション期間により完了させられ得なければ、書き込みコマンドに関連付けられた新しいデータは動作８１０で書き込みバッファブロックに書き込まれ得る。不揮発性メモリ記憶システムは、ガーベッジコレクション動作の前に、間に、または後に、新しいデータを書き込みバッファブロックに書き込むことができる。以下でより詳しく説明されるように、ガーベッジコレクション動作が完了すると直ぐに新しいデータは書き込みバッファブロックから更新ブロックにコピーされ得る。書き込みバッファブロックは不揮発性メモリ記憶システムによってメモリ内に維持される。一般に、書き込みバッファブロックは、不揮発性メモリ記憶システムにおいて新しいデータをバッファリングする。１つの実施形態では、書き込みバッファブロックは複数の論理アドレスにわたって広がる。他の１つの実施形態では、書き込みバッファブロックは１つの論理アドレス空間全体にわたって広がる。論理アドレス空間全体にわたって広がることで、書き込みバッファブロックは、不揮発性メモリ記憶システム全体にわたって全ての論理アドレスと論理アドレスの全てのグループ（すなわち、全ての論理グループ）に書き込まれようとしているデータを記憶することができる。換言すれば、複数の異なる論理グループと関連付けられた新しいデータが書き込みバッファブロックに格納され得る。論理グループは、メタブロックのサイズと同等であり得るサイズを有する論理アドレスのグループである。新しいデータは、順次にあるいは非順次に（すなわち、カオス的またはランダムな順序で）書き込みバッファブロックに書き込まれ得る。以下でより詳しく説明されるように、書き込みバッファブロックに書き込まれた新しいデータは後に他のブロック（例えば、更新ブロック）にコピーされるので、書き込みバッファブロックは一時的バッファとして役立つ。本願明細書で使用される“書き込みバッファブロッククリーニング”という用語は、書き込みバッファブロックに格納された新しいデータが他のブロックにコピーされることを意味する。 If the garbage collection operation cannot be completed by the garbage collection period, new data associated with the write command can be written to the write buffer block at
１つの実施形態では不揮発性メモリ記憶システムが書き込みバッファブロックを段階的ガーベッジコレクション動作のために使用するということに留意するべきである。従って、書き込みバッファブロックは最も更新された新しいデータを記憶していないかもしれない。その結果として、新しいデータが後の読み出し動作で読み出されるならば、不揮発性メモリ記憶システムは、更新ブロックに格納されている新しいデータと書き込みバッファブロックに格納されている新しいデータとのどちらが最も新たに更新されたものであるかを調べる。読み出し動作は、その後、最も新たに更新された新しいデータにアクセスして戻す。他の１つの実施形態では、不揮発性メモリ記憶システムは、非段階的ガーベッジコレクション動作および段階的ガーベッジコレクション動作の両方のために書き込みバッファブロックを使用することができる。ここでは、書き込みバッファブロックは全ての書き込み動作のために使用される。換言すれば、非段階的ガーベッジコレクションおよび段階的ガーベッジコレクション動作からの新しいデータが書き込みバッファブロックに書き込まれる。従って、書き込みバッファブロックは、書き込みキャッシュのように動作し、従って最も新たに更新された新しいデータを包含する。 It should be noted that in one embodiment, the non-volatile memory storage system uses write buffer blocks for phased garbage collection operations. Thus, the write buffer block may not store the most updated new data. As a result, if new data is read in a later read operation, the non-volatile memory storage system is the most recent of the new data stored in the update block and the new data stored in the write buffer block. Check if it has been updated. A read operation then accesses and returns the most recently updated new data. In another embodiment, the non-volatile memory storage system may use a write buffer block for both non-staged garbage collection operations and staged garbage collection operations. Here, the write buffer block is used for all write operations. In other words, new data from non-staged garbage collection and staged garbage collection operations is written to the write buffer block. Thus, the write buffer block behaves like a write cache and thus contains the most recently updated new data.
書き込みバッファブロックに関連付けられたインデックス情報は、別のデータ構造に、あるいは書き込みバッファブロック自体の一部として、格納され得る。そのデータ構造はメモリコントローラのＲＡＭに格納され得る。データ構造に格納されたインデックス情報は、書き込みバッファブロックに格納されたデータのトラッキングおよびアクセスを可能にする。インデックス情報は、例えば、書き込みバッファブロック内の位置への論理アドレスのマップまたは書き込みバッファブロックの有効な索引へのポインタを含むことができる。索引情報は、更新ブロックが閉じられた後あるいは書き込みバッファブロックへの数個の更新の後に、更新され得る。以下でより詳しく説明されるように、１つの実施形態では、書き込みバッファブロックはセクタレベルの索引のために構成され得る。他の１つの実施形態では、書き込みバッファブロックはページ境界索引のために構成され得る。書き込みバッファブロックは、満杯時に圧縮されることもできる。例えば、書き込みバッファブロックに格納されている有効なデータは新しいブロックにコピーされ、それは新しい書き込みバッファブロックとして参照されるべきあり、陳腐なエントリを有する既存の書き込みバッファブロックは消去される。本願明細書で使用される“書き込みバッファ圧縮”という用語は、書き込みバッファブロックに格納されている有効なデータが圧縮されることを意味する。 Index information associated with the write buffer block may be stored in a separate data structure or as part of the write buffer block itself. The data structure can be stored in the RAM of the memory controller. The index information stored in the data structure allows tracking and access of data stored in the write buffer block. The index information can include, for example, a logical address map to a location in the write buffer block or a pointer to a valid index of the write buffer block. The index information can be updated after the update block is closed or after several updates to the write buffer block. As described in more detail below, in one embodiment, the write buffer block may be configured for a sector level index. In another embodiment, the write buffer block may be configured for a page boundary index. Write buffer blocks can also be compressed when full. For example, valid data stored in a write buffer block is copied to a new block, which should be referred to as a new write buffer block, and an existing write buffer block with stale entries is erased. As used herein, the term “write buffer compression” means that valid data stored in a write buffer block is compressed.
図８をなお参照すると、新しいデータが書き込みバッファブロックに書き込まれ、かつガーベッジコレクション動作がガーベッジコレクション期間中に実行された後、不揮発性メモリ記憶システムは動作８１２でタイムアウト期間の前にビジー信号を解除する。従って、１つのガーベッジコレクション動作または１つのガーベッジコレクション動作の一部分を含む書き込みコマンドを実行するための合計時間はタイムアウト期間を越えない。タイムアウト期間内にガーベッジコレクション動作の一部分が実行されるのであれば、残りの部分は後のタイムアウト期間で完了させられる。ガーベッジコレクション動作が完了すると、ガーベッジコレクションされた１つ以上のブロックが消去されて付加的なデータの格納のために利用可能にされる。 Still referring to FIG. 8, after new data is written to the write buffer block and a garbage collection operation is performed during the garbage collection period, the non-volatile memory storage system releases the busy signal before the timeout period at operation 812. To do. Thus, the total time for executing a write command that includes one garbage collection operation or a portion of one garbage collection operation does not exceed the timeout period. If a portion of the garbage collection operation is performed within the timeout period, the remaining portion is completed in a later timeout period. When the garbage collection operation is complete, one or more garbage collected blocks are erased and made available for storing additional data.
図９Ａおよび９Ｂは、本発明の実施形態に従う、段階的にガーベッジコレクションされる順次更新ブロックを伴うメモリブロックの簡略ブロック図である。図９Ａに示されているように、オリジナルのブロックＡ９８０と、関連する順次更新ブロックＡ９８２とがガーベッジコレクションのために選択される。一般に、書き込みコマンドから受け取られたデータは更新ブロックに書き込まれ得る。その中でデータが更新される各々の論理グループのために更新ブロックとして専用のメタブロックが割り当てられ得る。データの論理セクタは論理的に連続するセクタのセットを含む論理グループに格納されるということに留意するべきである。更新ブロックは、データを順次にあるいはカオス的順序で（すなわち、非順次に）受け入れるように管理され得る。順次更新ブロックＡ９８２のような順次更新ブロックは、全ての有効なセクタが現在同じメタブロックに置かれている論理グループにおいて１つ以上の物理ページを満たすデータを書き込むために書き込みコマンドがホストから受け取られたときに割り当てられるメタブロックであるということが理解されるべきである。順次更新ブロックに書き込まれるデータのセクタは、セクタがオリジナルブロックに書き込まれている対応する論理セクタに取って代わるように論理的にアドレス指定されて順次に書き込まれる。この論理グループの中の更新されるセクタは、順次更新ブロックが閉じられるかあるいはカオス的更新ブロックに変換されるまで、この順次更新ブロックに書き込まれ得る。順次更新ブロックは順次更新ブロックの最後の物理セクタ位置が書き込みされたときに閉じられたと見なされるということに留意するべきである。換言すれば、順次更新ブロックの閉鎖は、ホストにより書き込まれるかあるいはオリジナルブロックからコピーされる更新されるセクタデータによって順次更新ブロックが完全に満たされることに起因し得る。以下でより詳しく説明されるように、カオス的更新ブロックは、ホストにより書き込まれるデータのセクタが、更新される論理グループ内の前に書き込まれたデータのセクタに論理的に連続していないときに順次更新ブロックからの変換によって作られ得る。 9A and 9B are simplified block diagrams of a memory block with sequential update blocks that are garbage collected in stages, in accordance with an embodiment of the present invention. As shown in FIG. 9A, the original block A980 and the associated sequential update block A982 are selected for garbage collection. In general, data received from a write command can be written to an update block. A dedicated metablock can be assigned as an update block for each logical group in which data is updated. It should be noted that the logical sectors of data are stored in a logical group that includes a set of logically contiguous sectors. Update blocks may be managed to accept data sequentially or in chaotic order (ie, non-sequentially). A sequential update block, such as sequential update block A982, receives a write command from the host to write data that fills one or more physical pages in a logical group where all valid sectors are currently located in the same metablock. It should be understood that this is a metablock that is assigned at the time. Sectors of data that are written to sequential update blocks are written logically with sequential addressing so that the sector replaces the corresponding logical sector written to the original block. Updated sectors in this logical group can be written to this sequential update block until the sequential update block is closed or converted to a chaotic update block. It should be noted that a sequential update block is considered closed when the last physical sector position of the sequential update block is written. In other words, the closure of the sequential update block may be due to the sequential update block being completely filled with updated sector data written by the host or copied from the original block. As described in more detail below, a chaotic update block is used when a sector of data written by the host is not logically contiguous with a sector of previously written data in the logical group being updated. It can be made by conversion from a sequential update block.
オリジナルブロックＡ９８０は無効なデータと有効なデータとを含むことができ、図９Ａではそれぞれハッチパターンおよびドットパターンで表されている。オリジナルブロックＡ９８０からコピーされた有効なデータに加えて、順次更新ブロックＡ９８２はガーベッジコレクション動作の前に順次更新ブロックＡに書き込まれた既存のデータ９８１を付加的に含むということに留意するべきである。新しいデータ９８３を書き込む書き込みコマンドが受け取られたとき、書き込みコマンドは順次更新ブロックＡ９８２の閉鎖を誘発し得るが、それは１種のガーベッジコレクション動作である。なぜならば、それは新しいデータが開いている更新ブロックを持っていない論理グループと関連付けられるかあるいは新しいデータがガーベッジコレクション動作を引き起こすからである。不揮発性メモリ記憶システムはビジー信号をアサートし、その後、第１のガーベッジコレクション期間９７０に達するまで有効なデータをオリジナルブロックＡ９８０から順次更新ブロックＡ９８２にコピーする。コピー中、不揮発性メモリ記憶システムは時間を追跡し、不揮発性メモリ記憶システムは第１のガーベッジコレクション期間９７０を超える前にコピー動作をやめる。図９Ａに示されているように、オリジナルブロックＡ９８０に有効なデータがなお残っているので、ガーベッジコレクション動作はガーベッジコレクション期間９７０内に完了させられ得ない。その結果として、有効なデータの部分が順次更新ブロックＡ９８２にコピーされた後、新しいデータ９８３は、第１のタイムアウト期間に達する前に許された残っている時間内に書き込みバッファブロック９０８に書き込まれる。 The
図９Ｂは、ガーベッジコレクション動作の残りの部分が第２のタイムアウト期間内に完了させられ得ることを示す。ここで、新しいデータ９８４を書き込む第２の書き込みコマンドが第１の書き込みコマンドの後に受け取られる。その結果として、第２の書き込みコマンドに第２のタイムアウト期間が割り当てられる。第２のタイムアウト期間の間に、残りの有効なデータがオリジナルブロックＡ９８０から順次更新ブロックＡ９８２にコピーされる。この例では、残っている有効なデータの全体（または有効なデータの最後の部分）が第２のガーベッジコレクション期間９７２内に順次更新ブロックＡ９８２にコピーされ得る。従って、ガーベッジコレクション動作は第２のタイムアウト期間内に完了させられ得る。順次更新ブロックＡ９８２は満杯にされているので、順次更新ブロックＡは新しいオリジナルブロックＡ９８５または非更新ブロックに変換される。ガーベッジコレクション動作はこの第２のタイムアウト期間内に完了させられるので、オリジナルブロックＡ９８０は消去され、付加的なデータの格納に利用可能にされ得る。オリジナルブロックＡ９８０が消去された後、更新ブロックＣ９８６が割り当てられ、第２の書き込みコマンドから受け取られた新しいデータ９８４は新たに割り当てられた更新ブロックＣに書き込まれる。更新ブロックＣ９８６は新しいオリジナルブロックＡ９８５に関連付けられるかもしれないしあるいは関連付けられないかもしれないということに留意するべきである。 FIG. 9B shows that the remaining portion of the garbage collection operation can be completed within the second timeout period. Here, a second write command for writing
第２のタイムアウト期間内にガーベッジコレクションが完了した後、第２のタイムアウト期間内に利用可能な時間があれば、不揮発性メモリ記憶システムは書き込みバッファブロッククリーニング動作を行うことができる。書き込みバッファブロック９０８は、書き込みバッファブロックに書き込まれた新しいデータ９８３のような新しいデータが後に他のブロック（例えば、更新されたブロックＣ９８６）にコピーされるので、一時的バッファとして役立つ。図９Ｂの例では、第２のタイムアウト期間内に書き込みバッファブロッククリーニング動作のための時間がある。書き込みバッファブロック９０８に格納されている新しいデータ９８３は、新しいデータ９８４と同じ論理グループの中にある。従って、新しいデータ９８３は、ガーベッジコレクション動作の完了後に更新ブロックＣ９８６にコピーされる。書き込みバッファブロック９０８に格納されている新しいデータ９８３は無効としてマークされ、従って、書き込みバッファブロック内の付加的なスペースは付加的な新しいデータの格納のために利用可能にされ得る。書き込みバッファブロッククリーニング動作は全てのガーベッジコレクションの完了後に実行されるわけではないかもしれないということに留意するべきである。書き込みバッファブロッククリーニングのタイミングは以下でより詳しく説明される。 After garbage collection is completed within the second timeout period, the non-volatile memory storage system can perform a write buffer block cleaning operation if there is time available within the second timeout period. Write
図１０Ａ〜１０Ｅは、本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。図１０Ａに示されているように、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４がガーベッジコレクションのために選択される。一般に、カオス的更新ブロックＡ９０４のようなカオス的更新ブロックは、データのセクタが１つの論理グループ内でランダムな順序で、個々のセクタの任意の反復を伴って、更新されることを可能にする。カオス的更新ブロックは、ホストにより書き込まれるデータのセクタが、更新される論理グループ内の前に書き込まれたデータのセクタに論理的に連続していないときに順次更新ブロックからの変換によって作成され得る。この論理グループにおいてその後に更新される全てのデータのセクタは、グループ内でのそれらの論理セクタアドレスが何であっても、カオス的更新ブロック内の次の利用可能なセクタ位置に書き込まれる。 10A-10E are simplified block diagrams of memory blocks with chaotic update blocks that are garbage collected in stages, in accordance with an embodiment of the present invention. As shown in FIG. 10A, an original block A902 and a chaotic update block A904 are selected for garbage collection. In general, a chaotic update block, such as chaotic update block A904, allows sectors of data to be updated in random order within a logical group, with arbitrary repetitions of individual sectors. . A chaotic update block can be created by conversion from a sequential update block when the sector of data written by the host is not logically contiguous to the sector of previously written data in the logical group being updated. . All sectors of data subsequently updated in this logical group are written to the next available sector location in the chaotic update block whatever their logical sector address in the group.
ここで、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４は、図１０Ａにおいてハッチパターンおよびドットパターンでそれぞれ表される無効なデータおよび有効なデータを含む。新しいデータ９０１を書き込む書き込みコマンドが受け取られたとき、不揮発性メモリ記憶システムはビジー信号をアサートし、その後、第１のガーベッジコレクション期間９５０に達するまで有効なデータをオリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４から新しいブロックＡ９０６にコピーする。コピー中、不揮発性メモリ記憶システムは時間を追跡し、不揮発性メモリ記憶システムは第１のガーベッジコレクション期間９５０を超える前にコピー動作をやめる。図１０Ａに示されているように、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４に有効なデータがなお残っているので、ガーベッジコレクション動作は第１のガーベッジコレクション期間９５０内に完了させられ得ない。その結果として、有効なデータの部分が新しいブロックＡ９０６にコピーされた後、ガーベッジコレクション動作が始まる前に受け取られた新しいデータ９０１は第１のタイムアウト期間に達する前に書き込みバッファブロック９０８に書き込まれる。 Here, the original block A902 and the chaotic update block A904 include invalid data and valid data respectively represented by a hatch pattern and a dot pattern in FIG. 10A. When a write command to write
図１０Ｂは、その次のタイムアウト期間におけるガーベッジコレクション動作の続きを示す。ここで、第１の書き込みコマンドの後に第２の書き込みコマンドが受け取られ、第２のタイムアウト期間が第２の書き込みコマンドに割り当てられる。第２のタイムアウト期間の間に、残りの有効なデータが、第２のガーベッジコレクション期間９５１に達するまでオリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４から新しいブロックＡ９０６にコピーされる。図１０Ｂに示されているように、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４に有効なデータがなお残っているので、ガーベッジコレクション動作は第２のガーベッジコレクション期間９５１内に完了させられ得ない。従って、有効なデータの部分が新しいブロックＡ９０６にコピーされた後、ガーベッジコレクション動作が始まる前に受け取られた新しいデータ９０５は書き込みバッファブロック９０８に書き込まれる。 FIG. 10B shows the continuation of the garbage collection operation in the next timeout period. Here, a second write command is received after the first write command, and a second timeout period is assigned to the second write command. During the second timeout period, the remaining valid data is copied from the original block A902 and the chaotic update block A904 to the new block A906 until the second
図１０Ｃは、ガーベッジコレクション動作の残りの部分が第３のタイムアウト期間内に完了させられ得ることを示す。第２の書き込みコマンド後に第３の書き込みコマンドが受け取られる。その結果として、第３のタイムアウト期間が第３の書き込みコマンドに割り当てられる。第３のタイムアウト期間の間に、残りの有効なデータがオリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４から新しいブロックＡ９０６にコピーされる。ここで、全ての残りの有効なデータ（あるいは有効なデータの最後の部分）が第３のガーベッジコレクション期間９５３内に新しいブロックＡ９０６にコピーされ得る。従って、ガーベッジコレクション動作は第３のタイムアウト期間内に完了させられ得る。ガーベッジコレクション動作がこの第３のタイムアウト期間に完了させられるので、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４は消去されて付加的なデータの格納のために利用可能にされ得る。オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４が消去された後、新しい更新ブロックＢ９６２が割り当てられ、第３の書き込みコマンドから受け取られた新しいデータ９０９は新たに割り当てられた更新ブロックＢに書き込まれる。新しいデータ９０９は書き込みバッファブロック９０８に書き込まれないが、それは、ガーベッジコレクション動作が完了して、その次のタイムアウト期間まで新しいデータをバッファリングする必要がないからである。この例では、書き込みバッファブロッククリーニング動作が実行され、その動作で、新しいデータ９０１，９０５，および９０９が同じ論理グループに属すると仮定して、書き込みバッファブロック９０８に格納されている新しいデータ９０１および９０５が更新ブロックＢ９６２にコピーされる。 FIG. 10C shows that the remaining portion of the garbage collection operation can be completed within the third timeout period. A third write command is received after the second write command. As a result, a third timeout period is assigned to the third write command. During the third timeout period, the remaining valid data is copied from the original block A902 and the chaotic update block A904 to the new block A906. Here, all remaining valid data (or the last part of valid data) can be copied to the new block A 906 within the third garbage collection period 953. Thus, the garbage collection operation can be completed within the third timeout period. Since the garbage collection operation is completed during this third timeout period, the original block A902 and the chaotic update block A904 can be erased and made available for storing additional data. After the original block A902 and the chaotic update block A904 are erased, a new update block B962 is allocated and
図１０Ｄは、第４のタイムアウト期間中に行われる他の１つのガーベッジコレクション動作を示す。図１０Ｄに示されているように、オリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２がガーベッジコレクションのために選択される。カオス的更新ブロックに変換されている更新ブロックＢ９６２は、第１、第２、および第３の書き込みコマンドに関連する新しいデータ９０１，９０５，および９０９を含む。第４の書き込みコマンドが受け取られたとき、不揮発性メモリ記憶システムはビジー信号をアサートし、その後に有効なデータをオリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２から新しいブロックＢ９６４にコピーする。図１０Ｄに示されているように、有効なデータがオリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２になお残っているので、ガーベッジコレクション動作は第４のガーベッジコレクション期間９５２内に完了させられ得ない。有効なデータの部分が新しいブロックＢ９６４にコピーされた後、第４の書き込みコマンドから受け取られた新しいデータ９０３は書き込みバッファブロック９０８に書き込まれる。 FIG. 10D shows another garbage collection operation that occurs during the fourth timeout period. As shown in FIG. 10D, original block B960 and chaotic update block B962 are selected for garbage collection. Update block B962, which has been converted to a chaotic update block, includes
図１０Ｅは、図１０Ｄのガーベッジコレクション動作の残りの部分が第５のタイムアウト期間に完了させられ得ることを示す。第４の書き込みコマンド後に第５の書き込みコマンドが受け取られる。その結果として、第５のタイムアウト期間が第５の書き込みコマンドに割り当てられる。第５のタイムアウト期間の間に、残りの有効なデータがオリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２から新しいブロックＢ９６４にコピーされる。ここで、全ての残りの有効なデータ（あるいは有効なデータの最後の部分）が第５のガーベッジコレクション期間９５３内に新しいブロックＢ９６４にコピーされ得る。従って、始めに第４のタイムアウト期間中に実行されたガーベッジコレクション動作は第５のタイムアウト期間内に完了させられ得る。ガーベッジコレクション動作がこの第５のタイムアウト期間に完了させられるので、オリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２は消去されて、付加的なデータの格納のために利用可能にされる。オリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２が消去された後、更新ブロックＣ９６５が割り当てられ、第５の書き込みコマンドから受け取られた新しいデータ９０７は新たに割り当てられた更新ブロックＣに書き込まれる。更新ブロックＣ９６５は新しいブロックＢ９６４に関連付けられるかもしれないしあるいは関連付けられないかもしれないということに留意するべきである。ここで、書き込みバッファブロッククリーニング動作が実行され、従って、新しいデータ９０３および新しいデータ９０７が同じ論理グループに属すると仮定して、書き込みバッファブロック９０８に格納されている新しいデータ９０３は更新ブロックＣ９６５にコピーされる。 FIG. 10E shows that the remaining portion of the garbage collection operation of FIG. 10D can be completed in the fifth timeout period. A fifth write command is received after the fourth write command. As a result, a fifth timeout period is assigned to the fifth write command. During the fifth timeout period, the remaining valid data is copied from the original block B960 and the chaotic update block B962 to the new block B964. Here, all the remaining valid data (or the last part of the valid data) can be copied to the
図１１は、本発明の１つの実施形態に従う、書き込みバッファブロックへのアクセスを最適化する動作のフローチャート図である。書き込みバッファブロックの維持は、あるオーバーヘッドを導入する。オーバーヘッドを減少させるために、１つの実施形態では、書き込みバッファブロックへの書き込みが最小にされ得る。図１１に示されているように、動作１００２で書き込みコマンドが受け取られる。その後、不揮発性メモリ記憶システムは動作１００４で実行時間を推定する。実行時間は、書き込みコマンドを実行する期間である。書き込みコマンドの実行は、例えば、新しいデータをメモリにプログラムする（すなわち、書き込む）ことと、ガーベッジコレクション動作を実行することと、他の動作の実行とを含み得る。例えば、実行時間は、有効なデータを１つ以上のブロックから他の１つのブロックにコピーするための期間と新しいデータを書き込む期間とを含み得る。 FIG. 11 is a flowchart diagram of operations for optimizing access to a write buffer block, in accordance with one embodiment of the present invention. Maintaining the write buffer block introduces some overhead. To reduce overhead, in one embodiment, writing to the write buffer block can be minimized. As shown in FIG. 11, at
不揮発性メモリ記憶システムは、実行時間を即時に推定する。不揮発性メモリ記憶システムは、種々のパラメータに基づいて実行時間を推定することができる。パラメータの例として、ガーベッジコレクションのタイプ（例えば、ブロック閉鎖、整理統合、圧縮、および他のタイプ）、ガーベッジコレクションされるべきブロック（例えば、更新ブロックおよび他のブロック）に格納されている有効なデータの量、不揮発性メモリ記憶システムに関連するプログラミング時間、ガーベッジコレクションされるブロックのサイズ（例えば、メタブロックのサイズ）、プレパディング(pre-padding) が必要か否か、プレパディングされるべきデータの量、パイプライニング、キャッシング、周波数設定、プログラム破損、および他のパラメータを含む。実行時間を推定する１つの例では、最初の１つ以上のブロックは１２ページの有効なデータを含み、その１２ページの有効なデータが１つの第２のブロックにコピーされる。不揮発性メモリ記憶システムは、１２ページの有効なデータを読み出すために不揮発性メモリ記憶システムが必要とする時間の量とその有効なデータを第２のブロックに書き込むために不揮発性メモリ記憶システムが必要とする時間の量とを加えることによって実行時間を推定することができる。 Non-volatile memory storage systems estimate the execution time immediately. Non-volatile memory storage systems can estimate execution time based on various parameters. Examples of parameters include the type of garbage collection (eg, block closure, consolidation, compression, and other types), valid data stored in the blocks that are to be garbage collected (eg, update blocks and other blocks) Amount of data, programming time associated with the non-volatile memory storage system, size of garbage collected blocks (eg, metablock size), whether pre-padding is required, Includes quantity, pipelining, caching, frequency settings, program corruption, and other parameters. In one example of estimating execution time, the first one or more blocks contain 12 pages of valid data, and the 12 pages of valid data are copied into one second block. A non-volatile memory storage system requires an amount of time required by the non-volatile memory storage system to read 12 pages of valid data and a non-volatile memory storage system to write the valid data to the second block The execution time can be estimated by adding the amount of time.
不揮発性メモリ記憶システムが実行時間を推定した後、その実行時間は動作１００６でタイムアウト期間と比較される。動作１００８に示されているように、その推定された実行時間がタイムアウト期間より短ければあるいは動作がタイムアウト期間内に完了させられ得るならば、ガーベッジコレクション動作が、引き起こされたならば、実行されてタイムアウト期間内に完了させられ、新しいデータが更新ブロックに書き込まれる。一方、動作１０１０に示されているように、推定された実行時間がタイムアウト期間を超える（すなわち、タイムアウト期間より大きいかあるいはタイムアウト期間に等しい）ならば、新しいデータは書き込みバッファブロックに書き込まれ、割り当てられたガーベッジコレクション期間は、書き込みバッファブロッククリーニングのためにあるいはガーベッジコレクション動作（引き起こされたならば）の一部分を実行するために使用され得る。１つの実施形態では、以下でより詳しく説明されるように、書き込みバッファブロッククリーニングは、タイムアウト期間内に残っている時間の間に、書き込みバッファブロック内の第１の有効なエントリから始まることができる。推定された実行時間がタイムアウト期間を超えるときに書き込みバッファブロックに書き込むことによって、書き込みバッファブロックへの書き込みはより少数となり、従って、書き込みバッファブロックを維持することに関連するオーバーヘッドは低減され得る。 After the non-volatile memory storage system estimates the execution time, the execution time is compared to a timeout period at
書き込みバッファブロック−ページ境界索引付け
１つの実施形態では、書き込みバッファブロックは複数のページを含むように構成され、書き込みバッファブロック内の各ページは索引付けされる。書き込みバッファブロックの各ページは、１セクタ以上の新しいデータを記憶するように構成される。従って、１ポインタが１ページを指すかあるいは参照し、１ページ内の複数のセクタは１ポインタにより参照され得るが、それは、ポインタが１つのページを指すのであってページ内の複数のセクタを指すのではないからである。ここで、同じメタページに属する新しいデータのセクタは、書き込みバッファブロックの同じメタページに書き込まれる。しかし、別々のメタページに属する新しいデータのセクタは書き込みバッファブロックの別々のメタページに書き込まれる。例えば、第１の書き込みコマンドに関連付けられた新しいデータの第１のセクタは書き込みバッファブロックの第１のページに書き込まれる。その後、新しいデータの第２のセクタが第２の書き込みコマンドから受け取られる。その新しいデータの第２のセクタが新しいデータの第１、第２と同じメタページに属するならば、第２のセクタは書き込みバッファブロックの第１のページに書き込まれる。一方、新しいデータの第２のセクタが別のメタページに属するならば、第２のセクタは書き込みバッファブロックの別のメタページに書き込まれる。Write Buffer Block-Page Boundary Indexing In one embodiment, the write buffer block is configured to include multiple pages, and each page in the write buffer block is indexed. Each page of the write buffer block is configured to store new data of one sector or more. Thus, a pointer points to or references a page, and multiple sectors within a page can be referenced by a pointer, but it points to a page and points to multiple sectors within the page. Because it is not. Here, sectors of new data belonging to the same metapage are written to the same metapage of the write buffer block. However, sectors of new data belonging to different metapages are written to different metapages of the write buffer block. For example, the first sector of new data associated with the first write command is written to the first page of the write buffer block. Thereafter, a second sector of new data is received from the second write command. If the second sector of the new data belongs to the same metapage as the first and second of the new data, the second sector is written to the first page of the write buffer block. On the other hand, if the second sector of new data belongs to another metapage, the second sector is written to another metapage of the write buffer block.
書き込みバッファブロック−セクタレベル索引付け
他の１つの実施形態では、書き込みバッファブロックは複数のセクタを含むように構成され、書き込みバッファブロック内の１つ以上のセクタは索引付けされ得る。例えば、１ポインタが複数のセクタ（例えば、４セクタ）を指すかあるいは参照することができる。他の１つの例では、１ポインタが１セクタを指すかあるいは参照することができる。書き込みバッファブロック内の各セクタが索引付けされる例では、新しいデータは書き込みバッファブロックの単一のセクタに書き込まれる。他の１つの書き込みコマンドに関連付けられたその次の新しいデータは書き込みバッファブロック内の次の利用可能なセクタに書き込まれる。例えば、複数の書き込みコマンドからの新しいデータのセクタは、書き込みバッファブロック内の同じページの別々のセクタに書き込まれ得る。従って、書き込みバッファブロックは複数のセクタを含むように構成されることができ、各セクタは新しいデータの１つのセクタを記憶するように構成される。Write Buffer Block—Sector Level Indexing In another embodiment, the write buffer block is configured to include multiple sectors, and one or more sectors in the write buffer block may be indexed. For example, one pointer can point to or refer to a plurality of sectors (eg, four sectors). In another example, one pointer can point to or reference one sector. In the example where each sector in the write buffer block is indexed, new data is written to a single sector of the write buffer block. The next new data associated with one other write command is written to the next available sector in the write buffer block. For example, new data sectors from multiple write commands may be written to separate sectors on the same page in the write buffer block. Thus, the write buffer block can be configured to include multiple sectors, with each sector configured to store one sector of new data.
タイムアウトエラーなしでシングルセクタ書き込みを持続させるために、不揮発性メモリ記憶システムは、割り当てられたセクタが不揮発性メモリ記憶システムのメタブロックの総数より多いように数個のセクタを書き込みバッファブロックに割り当てることができる。書き込みバッファブロックが複数のメタブロックで構成され得るということが理解されるべきである。書き込みバッファブロックに割り当てられるセクタの数を計算するために、例えば、書き込みバッファブロックを構成するメタブロックの数Ｍは、
M=M1+(M1*M2)/(Metablock_Size-M2) (1.0)
と定義することができ、“Metablock_Size"は“メタブロックサイズ”を意味し、ここで、
M1=RoundUp.to.Nearest.Integer[(N-1)*(Total.Number.of.Metablocks.in.System)/(Mtablock_Size)]
であり、ここで“RoundUp.to.Nearest.Integer"は“最近の整数への切り上げ”を意味し、“Total.Number.of.Metablocks.in.System"は“システム内のメタブロックの総数”を意味し、
M2=RoundUp.to.Nearest.Integer[(N*Tgc)/(N*TO-Tgc)]
であり、
N=RoundDown.to.Nearest.Integer[(Tgc+TO)/TO]
であり、ここで“RoundDown.to.Nearest.Integer"は“最近の整数への切り下げ”を意味し、TOはタイムアウト期間であり、Tgc は１つの完全なガーベッジコレクション動作を実行するための時間である。書き込みバッファブロックに割り当てられるセクタの総数は、
セクタの総数=M*Metablock_Size （１．２）
として定義されることができ、ここでＭは方程式１．０で定義され、“Metablock_Size"は、５１２セクタ／メタブロック、１，０２４セクタ／メタブロック、２，０４８セクタ／メタブロックあるいは他のサイズのようなセクタ数で表した各メタブロックのサイズである。一般に、方程式１．０および１．２は、書き込みバッファブロックに割り当てられるセクタの総数を不揮発性メモリ記憶システム内のメタブロックの総数より大きく定義する。メタブロックの総数に加えて、方程式１．０は、書き込みバッファブロックに関連するオーバーヘッドを維持するための１つ以上のメタブロック（またはセクタ）（以降、“オーバーヘッドメタブロック”または“オーバーヘッドセクタ”）を割り当てる。例えば、オーバーヘッドメタブロックの数を定める方程式１．０の部分は(M1*M2)/(Metablock_size-M2) であり、ここでオーバーヘッドセクタはオーバーヘッドブロックをメタブロックサイズと乗じることによって計算され得る。In order to persist single sector writes without timeout errors, the non-volatile memory storage system allocates several sectors to the write buffer block so that the allocated sectors are greater than the total number of meta-blocks in the non-volatile memory storage system Can do. It should be understood that a write buffer block can be composed of multiple metablocks. In order to calculate the number of sectors allocated to the write buffer block, for example, the number M of metablocks constituting the write buffer block is:
M = M1 + (M1 * M2) / (Metablock_Size-M2) (1.0)
“Metablock_Size” means “metablock size”, where
M1 = RoundUp.to.Nearest.Integer [(N-1) * (Total.Number.of.Metablocks.in.System) / (Mtablock_Size)]
Where “RoundUp.to.Nearest.Integer” means “rounded up to the nearest integer” and “Total.Number.of.Metablocks.in.System” means “total number of metablocks in the system” Means
M2 = RoundUp.to.Nearest.Integer [(N * Tgc) / (N * TO-Tgc)]
And
N = RoundDown.to.Nearest.Integer [(Tgc + TO) / TO]
Where “RoundDown.to.Nearest.Integer” means “round down to the nearest integer”, TO is the timeout period, and Tgc is the time to perform one complete garbage collection operation. is there. The total number of sectors allocated to the write buffer block is
Total number of sectors = M * Metablock_Size (1.2)
Where M is defined by Equation 1.0 and “Metablock_Size” is 512 sectors / metablock, 1,024 sectors / metablock, 2,048 sectors / metablock or other size Is the size of each metablock expressed in sectors. In general, equations 1.0 and 1.2 define the total number of sectors allocated to the write buffer block to be greater than the total number of metablocks in the non-volatile memory storage system. In addition to the total number of metablocks, Equation 1.0 provides one or more metablocks (or sectors) to maintain overhead associated with write buffer blocks (hereinafter “overhead metablocks” or “overhead sectors”). Assign. For example, the part of Equation 1.0 that defines the number of overhead metablocks is (M1 * M2) / (Metablock_size-M2), where the overhead sector can be calculated by multiplying the overhead block by the metablock size.
方程式１．２で定められる数のセクタを書き込みバッファブロックに割り当てることにより、連続的でランダムなシングルセクタ書き込みという最悪の場合のシナリオにおいてもタイムアウトエラーが回避され得る。タイムアウトエラーは、書き込みバッファブロックが満杯でガーベッジコレクション動作が完了させられ得ないときに生じ得る。最悪の場合のシナリオは、各シングルセクタ書き込みコマンドが別々の論理グループに書き込み、これによりどの書き込みでも１つの完全なガーベッジコレクション動作を引き起こすときに、生じる。この悪い場合のシナリオでは、セクタが蓄積されて書き込みバッファブロックに書き込まれる。この悪い場合のシナリオは、全てのタイムアウト期間で新しいデータの単一のセクタが書き込みバッファブロックに書き込まれると共に不揮発性メモリ記憶システムが１つの完全なガーベッジコレクション動作を実行するために必要な全ての時間（Ｔｇｃ）で１セクタが無効とマークされるかのように見られ得る。さらに、書き込みバッファブロックが満たされるかあるいは満杯であるとき、書き込みバッファブロックは、新しいセクタが受け取られるけれども書き込みバッファブロッククリーニング動作が実行され得ないように、圧縮される。従って、１つの悪い場合のシナリオでは、ガーベッジコレクション期間がタイムアウト期間より大きいときには書き込みバッファブロックは空にされるより速く満たされる。 By assigning the number of sectors defined in Equation 1.2 to the write buffer block, timeout errors can be avoided even in the worst case scenario of continuous random single sector writes. A timeout error can occur when the write buffer block is full and the garbage collection operation cannot be completed. The worst case scenario occurs when each single sector write command writes to a separate logical group, which causes every write to cause one complete garbage collection operation. In this bad scenario, sectors are accumulated and written to the write buffer block. This bad case scenario is that a single sector of new data is written to the write buffer block at all timeout periods and all the time required for the non-volatile memory storage system to perform one complete garbage collection operation. It can be seen as if one sector is marked invalid at (Tgc). Further, when the write buffer block is full or full, the write buffer block is compressed such that a new sector is received but a write buffer block cleaning operation cannot be performed. Thus, in one bad case scenario, the write buffer block fills faster than it is emptied when the garbage collection period is greater than the timeout period.
しかし、書き込みバッファブロック内の複数のセクタが同じ論理グループに属するならば、１ガーベッジコレクション動作中に全てのセクタが整理統合され得る。充分なメタブロックＭを書き込みバッファブロックに割り当てることにより、不揮発性メモリ記憶システム内のメタブロックの総数より多くのセクタ（またはエントリ）が書き込みバッファブロックに存在することになり、従って、複数の有効なセクタが書き込みバッファブロックに書き込まれている論理グループが存在することになる。書き込みバッファブロックの１つのセクタがガーベッジコレクションされるあるいは整理統合されるとき、同じ論理グループに属する全てのセクタが１つの新しい更新ブロックに整理統合され、書き込みバッファブロックにおいて無効とマークされる。従って、書き込みバッファブロックを空にする速度は充填速度より大きくなり、これにより書き込みバッファブロックが満杯であるかあるいは満たされることを防止する。従って、前述した最悪の場合のシナリオについてもタイムアウトエラーの発生が防止され得るように、所与の全てのＴｇｃについて、不揮発性メモリ記憶システムは不揮発性メモリ記憶システム内のメタブロックの総数より大きい数のセクタを書き込みバッファブロックに割り当てる。 However, if multiple sectors in the write buffer block belong to the same logical group, all sectors can be consolidated during one garbage collection operation. By allocating enough metablocks M to the write buffer block, there will be more sectors (or entries) in the write buffer block than the total number of metablocks in the non-volatile memory storage system, and thus multiple valid There will be a logical group in which sectors are written to the write buffer block. When one sector of a write buffer block is garbage collected or consolidated, all sectors belonging to the same logical group are consolidated into one new update block and marked invalid in the write buffer block. Thus, the rate at which the write buffer block is emptied is greater than the fill rate, thereby preventing the write buffer block from being full or filled. Thus, for a given Tgc, the non-volatile memory storage system is a number greater than the total number of metablocks in the non-volatile memory storage system so that timeout errors can be prevented even in the worst case scenario described above. Are allocated to the write buffer block.
図１２は、本発明の１つの実施形態に従う、新しいデータをスクラッチパッドブロックに一時的に格納するための動作のフローチャート図である。不揮発性メモリ記憶システムがマルチレベルバッファリングまたは複数のバッファレベルを持つことができ、それがマルチレベルキャッシングの思想と類似し得るということが理解されるべきである。この実施形態では、書き込みバッファブロックは、多数のバッファレベルのうちの１つに関連付けられ得る。複数バッファレベルでは、新しいデータを書き込みバッファブロックに直ぐに書き込む代わりに、新しいデータは、書き込みバッファブロックに書き込まれる前に一時的に他の１つのバッファレベルに格納され得る。書き込みバッファブロックのバッファレベルと異なるバッファレベルでの新しいデータの一時的格納は、段階的ガーベッジコレクション動作における書き込みバッファブロックの使用に関連する複雑さ、オーバーヘッド、および待ち時間を低減することができる。バッファの１つの例はスクラッチパッドブロックである。スクラッチパッドブロックは、書き込みバッファブロックとは異なるバッファレベルに関連付けられ得る。例えば、スクラッチパッドブロックは第１のバッファレベルとして使用され、書き込みバッファブロックは第２のバッファレベルとして使用され得る。前に論じられたように、シングルセクタ索引付けでは、複数の書き込みコマンドからの新しいデータのセクタは、書き込みバッファブロック内の同じページの別々のセクタに書き込まれ得る。不揮発性メモリ記憶システムは部分的なページをプログラムできないかもしれないので、本発明の１つの実施形態に従って、新しいデータは、書き込みバッファブロックに転送される前に、スクラッチパッドブロックのような第１のバッファレベルに一時的に格納され得る。スクラッチパッドブロックはデータ更新ブロックの１つの形であって、その中では関連する１つの論理グループ内の論理セクタがランダムな順序で任意の量の反復を伴って更新され得る。スクラッチパッドブロックは、意図された論理セクタが終了したりあるいは物理ページ境界を越えたりしない書き込みコマンドにより作られる。スクラッチパッドブロックは部分的物理ページに相当するデータを包含することができるけれども部分的プログラム済みページデータは許されない。スクラッチパッドブロックは、不揮発性メモリ記憶システム内の各更新ブロックのために１つの有効なページのデータを保持することができる。不揮発性メモリ記憶システムは、例えば、８個の更新ブロックを割り当てられることができ、従って、スクラッチパッドブロックは９個の有効なページのデータを記憶することができる。 FIG. 12 is a flowchart diagram of operations for temporarily storing new data in a scratch pad block, in accordance with one embodiment of the present invention. It should be understood that a non-volatile memory storage system can have multi-level buffering or multiple buffer levels, which can be similar to the idea of multi-level caching. In this embodiment, the write buffer block may be associated with one of a number of buffer levels. At the multiple buffer level, instead of writing new data immediately to the write buffer block, the new data can be temporarily stored in one other buffer level before being written to the write buffer block. Temporary storage of new data at a buffer level different from the buffer level of the write buffer block can reduce the complexity, overhead, and latency associated with using the write buffer block in a stepwise garbage collection operation. One example of a buffer is a scratch pad block. The scratch pad block may be associated with a different buffer level than the write buffer block. For example, the scratch pad block may be used as the first buffer level and the write buffer block may be used as the second buffer level. As discussed previously, in single sector indexing, sectors of new data from multiple write commands can be written to separate sectors on the same page in the write buffer block. Since the non-volatile memory storage system may not be able to program partial pages, in accordance with one embodiment of the present invention, new data is transferred to the first buffer pad block before being transferred to the write buffer block. It can be temporarily stored at the buffer level. A scratchpad block is a form of data update block in which logical sectors within an associated logical group can be updated in random order with any amount of repetition. A scratch pad block is created by a write command that does not terminate the intended logical sector or cross a physical page boundary. Although the scratchpad block can contain data corresponding to partial physical pages, partial programmed page data is not allowed. The scratch pad block can hold one valid page of data for each update block in the non-volatile memory storage system. A non-volatile memory storage system can be allocated, for example, 8 update blocks, and thus the scratchpad block can store 9 valid pages of data.
図１２に示されているように、書き込みコマンドから受け取られた新しいデータは始めに動作１１０２でスクラッチパッドブロックに書き込まれる。スクラッチパッドブロックは複数のページを含むことができ、各ページは複数のセクタを含む。新しいデータはスクラッチパッドブロックのセクタにコピーされる。動作１１０４で、新しいデータは、その後、書き込みバッファブロックに関連付けられているスクラッチパッドブロック内の１つのページが満杯であるとき、スクラッチパッドブロックから書き込みバッファブロックにコピーされる。従って、不揮発性メモリ記憶システムは、スクラッチパッドブロック内のページのセクタを、ページの全てのセクタが種々の書き込みコマンドからの新しいデータで満たされるまで、蓄積する。不揮発性メモリ記憶システムは、その後、そのページ全体(例えば、８セクタの新しいデータ)をスクラッチパッドブロックから書き込みバッファブロックに１プログラム動作でコピーする。書き込みバッファブロックはスクラッチパッドブロックより大きくてより多くの有効なデータを収容し得るので、スクラッチパッドブロックはより少量のガーベッジコレクションされるべきデータを有する。従って、スクラッチパッドブロックのガーベッジコレクションは書き込みバッファブロックのガーベッジコレクションより高速である。その結果として、新しいデータをスクラッチパッドブロックを経由して書き込みバッファブロックに書き込む動作は、新しいデータを書き込みバッファブロックに直接書き込む動作より速い。 As shown in FIG. 12, new data received from a write command is first written to the scratch pad block at
オーディオ／ビデオデータ
不揮発性メモリ記憶システムに格納されているオーディオ／ビデオファイル（以降、“オーディオ／ビデオデータ”）に関連付けられたデータにアクセスするホストは、他のデータと比べて所定の速度でオーディオ／ビデオデータを書き込む必要があるかもしれない。ホストがオーディオ／ビデオデータを不揮発性メモリ記憶システムにおよび／または不揮発性メモリ記憶システムからストリーミングするとき、ストリームに割り当てられる帯域幅は、所定の速度と一致するかあるいはそれを超える。オーディオ／ビデオデータのアクセス中に行われるガーベッジコレクション動作は、オーディオ／ビデオデータの書き込み性能を低下させることがある。従って、１つの実施形態では、マルチセクタ書き込みコマンドがオーディオ／ビデオデータに関連付けられていないかあるいはマルチセクタ書き込みコマンドがオーディオ／ビデオ書き込みの始まりにあるときには段階的ガーベッジコレクションが行われる。Audio / video data A host accessing data associated with an audio / video file (hereinafter “audio / video data”) stored in a non-volatile memory storage system is capable of audio at a predetermined rate relative to other data. / You may need to write video data. When a host streams audio / video data to and / or from a non-volatile memory storage system, the bandwidth allocated to the stream matches or exceeds a predetermined rate. A garbage collection operation performed during the access of the audio / video data may deteriorate the writing performance of the audio / video data. Thus, in one embodiment, gradual garbage collection occurs when a multi-sector write command is not associated with audio / video data or when the multi-sector write command is at the beginning of an audio / video write.
オーディオ／ビデオデータを他のデータから区別するために、１つの実施形態では、不揮発性メモリ記憶システムは、マルチセクタ書き込みコマンドに関連付けられたターゲット論理アドレスを参照することができる。オーディオ／ビデオデータは順次に書き込まれるので、逆方向ジャンプ(backwards jump)として解釈されるターゲット論理アドレスは、新しいデータがオーディオ／ビデオデータ（あるいはオーディオ／ビデオデータの始まり）ではないことを示すことができる。他の１つの実施形態では、不揮発性メモリ記憶システムは、新しいデータに関連付けられたセクタの数を参照することによってもオーディオ／ビデオデータを他のデータから区別することができる。オーディオ／ビデオデータは、記録単位(recording unit)と称される単位で格納され得る。オーディオ／ビデオデータに関連付けられる最小の記録単位の長さは３２セクタであり得る。従って、３２セクタの整数倍ではない新しいデータに関連付けられたセクタの数は、その新しいデータがオーディオ／ビデオデータではないことを示すことができる。記録単位に整列しないか、あるいは記録単位の始まりから始まらない受け取られた新しいデータも、その新しいデータがオーディオ／ビデオデータではないことを示すことができる。 In order to distinguish audio / video data from other data, in one embodiment, the non-volatile memory storage system can reference a target logical address associated with a multi-sector write command. Since audio / video data is written sequentially, the target logical address interpreted as a backwards jump may indicate that the new data is not audio / video data (or the beginning of audio / video data). it can. In another embodiment, the non-volatile memory storage system can also distinguish audio / video data from other data by referring to the number of sectors associated with the new data. Audio / video data may be stored in units called recording units. The minimum recording unit length associated with audio / video data may be 32 sectors. Thus, the number of sectors associated with new data that is not an integer multiple of 32 sectors can indicate that the new data is not audio / video data. New data received that does not align with the recording unit or does not start from the beginning of the recording unit can also indicate that the new data is not audio / video data.
その結果として、次の条件、すなわち（１）マルチセクタ書き込みコマンドがガーベッジコレクション動作を引き起こす、（２）ターゲット論理アドレスが逆方向ジャンプとして解釈される、（３）ターゲット論理アドレスが記録単位境界と整列させられていない、（４）新しいデータに関連付けられたセクタの数が３２の整数倍でなければ、ストップコマンドが受け取られた（すなわち、マルチセクタ書き込みコマンドの終わり）後、という条件のうちの１つが当てはまるならば、段階的ガーベッジコレクションが実行され得る。 As a result, the following conditions are met: (1) Multi-sector write command causes garbage collection operation, (2) Target logical address is interpreted as backward jump, (3) Target logical address is aligned with recording unit boundary One of the conditions: (4) after the stop command is received (ie, at the end of the multi-sector write command), if (4) the number of sectors associated with the new data is not an integer multiple of 32 If one is true, a stepwise garbage collection can be performed.
シングルセクタ書き込み
図１３は、本発明の１つの実施形態に従う、シングルセクタ書き込みコマンドに関連付けられた不揮発性メモリ記憶システム動作のフローチャート図である。新しいデータは、メモリセルアレイ全体の中でランダムなアドレスにシングルセクタとして書き込まれ得る。ホストアクティビティとカードフラグメンテーションとにより、ホストは複数のセクタを有する長いファイルをシングルセクタ書き込みコマンドを用いてランダムな位置に書き込むことができる。限られた数の割り当てられた更新ブロックがあるので、これらのシングルセクタ書き込みは、更新ブロックを速やかに用いることができ、これにより、その後の書き込み動作のためにブロックをクリアするガーベッジコレクション動作を実行するように不揮発性メモリ記憶システムを促すことができる。Single Sector Write FIG. 13 is a flowchart diagram of non-volatile memory storage system operation associated with a single sector write command, according to one embodiment of the invention. New data can be written as a single sector at random addresses within the entire memory cell array. Host activity and card fragmentation allows the host to write long files with multiple sectors to random locations using a single sector write command. Since there is a limited number of allocated update blocks, these single sector writes can use the update block quickly, thereby performing a garbage collection operation that clears the block for subsequent write operations. Can encourage non-volatile memory storage systems.
図１３に示されているように、シングルセクタ書き込みコマンドが動作１２０２で受け取られる。その後、そのシングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こすか否かについて動作１２０４で判定が行われる。そのシングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こさなければ、新しいデータは動作１２２０でメモリに書き込まれる。しかし、シングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こすならば、ペンディングしている段階的ガーベッジコレクション(すなわち、既に始まっているけれども、ガーベッジコレクションが完了させられ得ないために段階的に実行されたガーベッジコレクション動作)があるか否かについて他の１つの判定が動作１２０６で行われる。段階的ガーベッジコレクションがあるならば、動作１２０８でその段階的ガーベッジコレクション動作が続行される。換言すれば、前のガーベッジコレクション動作からの残りの部分が続行される。動作１２１０に示されているように、ガーベッジコレクション期間（例えば、タイムアウト期間とプログラミング時間との差）まであるいは段階的ガーベッジコレクションが完了させられるまで、段階的ガーベッジコレクション動作が実行される。 As shown in FIG. 13, a single sector write command is received at
段階的ガーベッジコレクション動作がガーベッジコレクション期間内に完了させられ得なければ、新しいデータは動作１２１８で書き込みバッファブロックに書き込まれる。ガーベッジコレクション期間に達していないかあるいは段階的ガーベッジコレクション動作がガーベッジコレクション期間の前に完了させられ得たならば、段階的ガーベッジコレクション動作を完了させた後であっても、シングルセクタ書き込みコマンドがなおガーベッジコレクション動作を引き起こすか否かについての他の１つの判定が動作１２１２で行われる。シングルセクタ書き込みコマンドがガーベッジコレクションを引き起こさなければ、新しいデータが動作１２２０でメモリに書き込まれる。一方、シングルセクタ書き込みコマンドがガーベッジコレクションを引き起こすならば、動作１２１６に示されているガーベッジコレクション期間まで動作１２１４でガーベッジコレクション動作が実行される。ガーベッジコレクション動作がガーベッジコレクション期間までに完了させられ得なければ、新しいデータは動作１２１８で書き込みバッファブロックに書き込まれる。そうでなければ、新しいデータは動作１２２０でメモリに書き込まれる。段階的ガーベッジコレクションがあってかつ現在の書き込みコマンドもガーベッジコレクション動作を引き起こすならば、動作１２１６に示されているガーベッジコレクション期間は動作１２１０に示されているガーベッジコレクション期間の続きであるということに留意するべきである。従って、段階的ガーベッジコレクションがあってかつ現在のシングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こすならば、両方の動作が総ガーベッジコレクション期間内に完了させられる。換言すれば、動作１２０８に示されている段階的ガーベッジコレクション動作と動作１２１４に示されているガーベッジコレクション動作との両方のために割り当てられる実行時間は、例えば、タイムアウト期間とプログラミング時間との差である。 If the staged garbage collection operation cannot be completed within the garbage collection period, new data is written to the write buffer block at
新しいデータが動作１２２０でメモリに書き込まれた後、書き込みバッファブロックに有効なエントリがあるか否かについて、またタイムアウト期間に達しているか否かについて、動作１２２４で判定が行われる。書き込みバッファブロックに有効なエントリがないかあるいはタイムアウト期間に達しているならば、動作は終了する。一方、有効なエントリがあってかつタイムアウト期間に達していなければ、書き込みバッファブロッククリーニング動作が動作１２２６でタイムアウト期間まで実行される。書き込みバッファブロック圧縮動作も、この期間中にタイムアウト期間まで実行され得る。 After new data is written to memory at operation 1220, a determination is made at
マルチセクタ書き込み
図１４は、本発明の１つの実施形態に従う、マルチセクタ書き込みコマンドに関連付けられた不揮発性メモリ記憶システム動作のフローチャート図である。メモリセルアレイに書き込まれる大抵の新しいデータは、連続した順次論理アドレス空間を占める大きなデータファイルである。ホストアクティビティにより、ホストは大きなデータファイルをマルチセクタ書き込みコマンドを用いて書き込むことができる。そのような新しいデータは、複数のタイムアウト期間を有する新しいデータの複数のセクタを含む。図７は、マルチセクタ書き込みコマンドの例を示す。一般に、複数のタイムアウト期間が利用可能なので、新しいデータは、書き込みバッファブロックの代わりに、割り当てられた更新ブロックに書き込まれ得る。従って、ガーベッジコレクションは、普通は、マルチセクタ書き込みコマンドに割り当てられた複数のタイムアウト期間内に完了させられ得るので、書き込みバッファブロックは普通は複数の書き込みコマンドで使用されない。Multi-Sector Write FIG. 14 is a flowchart diagram of non-volatile memory storage system operation associated with a multi-sector write command, according to one embodiment of the invention. Most new data written to the memory cell array is a large data file that occupies a continuous sequential logical address space. Host activity allows the host to write large data files using multi-sector write commands. Such new data includes multiple sectors of new data having multiple timeout periods. FIG. 7 shows an example of a multi-sector write command. In general, since multiple timeout periods are available, new data can be written to the allocated update block instead of the write buffer block. Thus, the write buffer block is normally not used for multiple write commands because garbage collection can normally be completed within multiple timeout periods assigned to multi-sector write commands.
図１４に示されているように、マルチセクタ書き込みコマンドが動作１３０２で受け取られる。その後、動作１３０４で、新しいデータのセクタは格納され（あるいはバッファリングされ）、必要ならばガーベッジコレクション動作が実行され得る。ここで、複数のタイムアウト期間がマルチセクタ書き込みコマンドに割り当てられ、１ガーベッジコレクション動作は普通はマルチセクタ書き込みコマンドの終わりまでに完了させられ得るので、不揮発性メモリ記憶システムは書き込みバッファブロックを利用しないかもしれない。従って、書き込みバッファブロックの代わりに、不揮発性メモリ記憶システムは、新しいデータを不揮発性メモリ記憶システムに関連付けられているＲＡＭに、あるいは不揮発性メモリ記憶システムに関連付けられている他のメモリに格納することができるのと同時に、割り当てられたタイムアウト期間を用いてガーベッジコレクション動作を実行するために新しいデータのセクタとセクタとの間にビジー信号をアサートする。 As shown in FIG. 14, a multi-sector write command is received at
ホストセクタがバッファリングされた後、新しいデータのＮ個未満のセクタが受け取られたのか否かについて動作１３０６で判定が行われる。前に論じられたように、ガーベッジコレクション動作は、普通は、マルチセクタ書き込み動作に割り当てられた複数のタイムアウト期間内に完了させられ得るので、マルチセクタ書き込みコマンドに関連付けられた新しいデータは書き込みバッファブロックに書き込まれないかもしれない。しかし、１つの実施形態では、ガーベッジコレクション動作を完了させるために充分なタイムアウト期間が割り当てられなければ、書き込みバッファブロックがマルチセクタ書き込みコマンドで使用され得る。従って、ガーベッジコレクション動作が引き起こされるか否かに関わらず、
N=round-down to nearest integer [(Tgc+TO)/TO] （２．０）
として定義された新しいデータの少なくともＮ個のセクタを伴うマルチセクタ書き込みコマンドが書き込みバッファブロックにではなくて更新ブロックに直接書き込まれ得る。ここで“round-down to nearest integer" は、“最近の整数への切り捨て”を意味する。方程式２．０は、書き込みコマンドがシングルセクタ書き込みコマンドであるときあるいは不揮発性メモリ記憶システムがマルチセクタ書き込みコマンドで新しいデータのＮ個未満のセクタを受け取ったときに、新しいデータが書き込みバッファブロックに書き込まれることを示す。After the host sector is buffered, a determination is made at
N = round-down to nearest integer [(Tgc + TO) / TO] （2.0）
A multi-sector write command with at least N sectors of new data defined as can be written directly to the update block rather than to the write buffer block. Here “round-down to nearest integer” means “round down to the nearest integer”. Equation 2.0 shows that new data is written to the write buffer block when the write command is a single sector write command or when the non-volatile memory storage system receives less than N sectors of new data with a multi-sector write command. Indicates that
なお図１４を参照すると、Ｎ個未満のセクタが受け取られたならば、不揮発性メモリ記憶システムは、図１３に示されているシングルセクタ書き込みコマンド動作に従ってマルチセクタ書き込みコマンドを操作する。しかし、新しいデータのＮ個より多くのセクタが受け取られたならば、書き込みバッファブロッククリーニング動作が実行され得るか否かについて動作１３１０で判定が行われる。例えば、動作１３０２で受け取られた新しいデータがガーベッジコレクションを引き起こさなかったならば、あるいは新しいデータが割り当てられたガーベッジコレクション期間の前に完了させられたガーベッジコレクションを引き起こしたのであれば、書き込みバッファブロッククリーニング動作が実行され得る。しかし、新しいデータが記録単位境界に整列させられているならば、新しいデータはオーディオ／ビデオデータであるかもしれないので、書き込みバッファブロックリーニングは実行されない。書き込みバッファブロッククリーニング動作が実行され得なければ、新しいデータは動作１３１４でメモリに書き込まれる。書き込みバッファブロッククリーニング動作が実行され得るならば、マルチセクタ書き込みコマンド実行中に不揮発性メモリ記憶システムによりアサートされた合計のビジー期間がＴｇｃ−Ｔｐｒｏｇになるまで、動作１３１２で段階的ガーベッジコレクション動作および書き込みバッファブロッククリーニング動作が実行される。その後、新しいデータは動作１３１４で不揮発性メモリセルアレイに書き込まれる。この実施形態では、動作１３１２に示されている書き込みバッファブロッククリーニングは、Ｔｇｃ−Ｔｐｒｏｇの期間まで、４タイムアウト期間、５タイムアウト期間、および他の期間などのいろいろな期間の間にマルチセクタ書き込みコマンドから受け取られた始めの数個のセクタの中間（例えば、第２のセクタと第３のセクタとの間）に、実行され得る。 Still referring to FIG. 14, if less than N sectors are received, the non-volatile memory storage system operates the multi-sector write command according to the single sector write command operation shown in FIG. However, if more than N sectors of new data have been received, a determination is made at
書き込みコマンドが実行された後、新しいデータが３２セクタの整数倍であるか否かについて動作１３１６で判定が行われる。新しいデータが３２セクタの整数倍であれば、新しいデータはオーディオ／ビデオ関連であるかも知れず、動作は終了する。一方、新しいデータが３２セクタの整数倍でなければ、動作１３１８で、書き込みバッファブロック内に有効なエントリがあるか否かについて、またタイムアウト期間に達しているか否かについて、判定が行われる。有効なエントリが書き込みバッファブロック内にないかあるいはタイムアウト期間に達していれば、動作は終了する。一方、有効なエントリがあってかつタイムアウト期間に達していなければ、動作１３２０でタイムアウト期間まで書き込みバッファブロッククリーニング動作が実行される。 After the write command is executed, a determination is made at
前述した実施形態は、段階的ガーベッジコレクションのための方法および／またはシステムを提供する。ガーベッジコレクション動作は複数の段階に分割されることができ、その複数の段階は複数のタイムアウト期間にわたって実行される。ガーベッジコレクション動作を分割することにより、ガーベッジコレクション動作の各段階はタイムアウト期間内に完了させられることができ、これによりタイムアウトエラーを防止する。 The embodiments described above provide a method and / or system for staged garbage collection. The garbage collection operation can be divided into multiple stages, which are performed over multiple timeout periods. By dividing the garbage collection operation, each stage of the garbage collection operation can be completed within the timeout period, thereby preventing timeout errors.
前述した実施形態は明確な理解を目的としてある程度詳細に記載されているけれども、実施形態は提示された細目に限定されない。実施形態を実現する多くの代わりの方法がある。従って、開示された実施形態は実例となるものであって制限するものではないと見なされるべきであり、実施形態は本願明細書で与えられた細目に限定されるべきではなくて、添付されている特許請求の範囲の範囲および同等物の中で改変され得る。特許請求の範囲で明示的に述べられていない限り、特許請求の範囲において要素および／または動作は動作の特定の順序を示唆しない。 Although the foregoing embodiments have been described in some detail for purposes of clarity of understanding, the embodiments are not limited to the details presented. There are many alternative ways of implementing the embodiments. Accordingly, the disclosed embodiments are to be considered as illustrative and not restrictive, and the embodiments should not be limited to the details provided herein, but are appended. Modifications may be made within the scope and equivalents of the following claims. Unless explicitly stated in the claims, elements and / or actions do not imply a particular order of operation in the claims.
Claims (8)
Translated fromJapanese複数のデータを書き込む書き込みコマンドを受け取るステップであって、前記書き込みコマンドが前記書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられるステップと、
ビジー信号をアサートするステップと、
ガーベッジコレクション期間の間に複数の有効なデータの一部分を不揮発性メモリの１つ以上の第１のブロックから不揮発性メモリの第２のブロックにコピーするステップと、
複数の論理アドレスにわたって広がるように構成された不揮発性メモリの第３のブロックに前記複数のデータを書き込むステップと、
前記タイムアウト期間の前に前記ビジー信号を解除するステップと、
を含む方法。A method of operating a non-volatile memory storage system, comprising:
Receiving a write command for writing a plurality of data, wherein the write command is assigned a timeout period for completing execution of the write command;
Asserting a busy signal;
A step of copying the second blockof the nonvolatile memory portion of the plurality of valid data from one or more first blocksof the nonvolatile memory during the garbage collection time period,
Writing the plurality of data to a third block ofnon-volatile memory configured to span across a plurality of logical addresses;
Releasing the busy signal before the timeout period;
Including methods.
前記複数の有効なデータの一部分をコピーするステップは、
前記複数の有効なデータの一部分を１つ以上の第１のブロックから第２のブロックにコピーするステップのための時間を追跡するステップと、
前記時間が前記ガーベッジコレクション期間を超える前に前記複数の有効なデータの一部分をコピーするステップを止めるステップと、
を含む方法。The method of claim 1, wherein
Copying a portion of the plurality of valid data,
Tracking a time for copying a portion of the plurality of valid data from one or more first blocks to a second block;
Stopping copying a portion of the plurality of valid data before the time exceeds the garbage collection period;
Including methods.
前記複数の有効なデータの一部分をコピーするステップおよび前記複数のデータを第３のブロックに書き込むステップの前に前記書き込みコマンドの実行のための実行時間を推定するステップをさらに含み、
前記実行時間が前記タイムアウト期間を越える場合、前記複数の有効なデータの一部分がコピーされかつ前記複数のデータが前記第３のブロックに書き込まれる方法。The method of claim 1, wherein
Copying a portion of the plurality of valid data and writing an execution time for execution of the write command before writing the plurality of data to a third block;
A method in which a portion of the plurality of valid data is copied and the plurality of data is written to the third block if the execution time exceeds the timeout period.
前記複数のデータを書き込むステップは、
前記複数のデータをスクラッチパッドブロックに書き込むステップと、
前記複数のデータを前記スクラッチパッドブロックから前記第３のブロックにコピーするステップと、
を含む方法。The method of claim 1, wherein
The step of writing the plurality of data includes:
Writing the plurality of data into a scratchpad block;
Copying the plurality of data from the scratch pad block to the third block;
Including methods.
前記複数のデータを書き込むステップは、
前記複数のデータを第１のバッファレベルに書き込むステップと、
前記複数のデータを前記第１のバッファレベルから前記第３のブロックにコピーするステップであって、前記第３のブロックが第２のバッファレベルに関連付けられるステップと、
を含む方法。The method of claim 1, wherein
The step of writing the plurality of data includes:
Writing the plurality of data to a first buffer level;
Copying the plurality of data from the first buffer level to the third block, wherein the third block is associated with a second buffer level;
Including methods.
前記ガーベッジコレクション期間は、前記タイムアウト期間と前記複数のデータを書き込むステップに関連付けられたプログラミング時間との差である方法。The method of claim 1, wherein
The garbage collection period is a difference between the timeout period and a programming time associated with writing the plurality of data.
前記第３のブロックは、書き込みバッファブロックである方法。The method of claim 1, wherein
The method wherein the third block is a write buffer block.
前記第３のブロックは、論理アドレス空間全体にわたって広がるように構成される方法。The method of claim 1, wherein
The method wherein the third block is configured to span the entire logical address space.
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US11/499,598US7451265B2 (en) | 2006-08-04 | 2006-08-04 | Non-volatile memory storage systems for phased garbage collection |
| US11/499,606US7444461B2 (en) | 2006-08-04 | 2006-08-04 | Methods for phased garbage collection |
| PCT/US2007/073891WO2008019218A2 (en) | 2006-08-04 | 2007-07-19 | Phased garbage collection |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP4362549B1true JP4362549B1 (en) | 2009-11-11 |
| JP2009545819A JP2009545819A (en) | 2009-12-24 |
Family
ID=39033552
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2009522934AExpired - Fee RelatedJP4362549B1 (en) | 2006-08-04 | 2007-07-19 | Gradual garbage collection |
Country Status (4)
| Country | Link |
|---|---|
| JP (1) | JP4362549B1 (en) |
| KR (1) | KR100922308B1 (en) |
| TW (1) | TWI343522B (en) |
| WO (1) | WO2008019218A2 (en) |
Families Citing this family (19)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4498426B2 (en) | 2008-03-01 | 2010-07-07 | 株式会社東芝 | Memory system |
| FR2950462A1 (en)* | 2009-09-21 | 2011-03-25 | St Microelectronics Rousset | Data writing and reading method for e.g. flash memory in chip card, involves reading wear counter from temporary information structure after metadata page is erased, incrementing read counter, and programming incremented counter in page |
| EP2299363B1 (en) | 2009-09-21 | 2013-01-09 | STMicroelectronics (Rousset) SAS | Method for levelling the wear in a non-volatile memory |
| US8417876B2 (en)* | 2010-06-23 | 2013-04-09 | Sandisk Technologies Inc. | Use of guard bands and phased maintenance operations to avoid exceeding maximum latency requirements in non-volatile memory systems |
| US8683148B2 (en) | 2010-06-30 | 2014-03-25 | Sandisk Il Ltd. | Status indication when a maintenance operation is to be performed at a memory device |
| JP2014132505A (en)* | 2010-12-16 | 2014-07-17 | Toshiba Corp | Memory system |
| JP5535128B2 (en) | 2010-12-16 | 2014-07-02 | 株式会社東芝 | Memory system |
| KR101157763B1 (en)* | 2010-12-27 | 2012-06-25 | 서울시립대학교 산학협력단 | Variable space page mapping method and apparatus for flash memory device with trim command processing |
| US9710326B2 (en) | 2014-07-28 | 2017-07-18 | SK Hynix Inc. | Encoder by-pass with scrambler |
| JP6320318B2 (en)* | 2015-02-17 | 2018-05-09 | 東芝メモリ株式会社 | Storage device and information processing system including storage device |
| US9990304B2 (en)* | 2015-11-13 | 2018-06-05 | Samsung Electronics Co., Ltd | Multimode storage management system |
| US11126544B2 (en) | 2016-12-14 | 2021-09-21 | Via Technologies, Inc. | Method and apparatus for efficient garbage collection based on access probability of data |
| TWI631460B (en)* | 2017-05-19 | 2018-08-01 | 群聯電子股份有限公司 | Data reading method, memory control circuit unit and memory storage device |
| KR102529710B1 (en)* | 2018-02-19 | 2023-05-09 | 에스케이하이닉스 주식회사 | Memory system and operation method thereof |
| KR102750797B1 (en)* | 2018-07-31 | 2025-01-09 | 에스케이하이닉스 주식회사 | Apparatus and method for performing garbage collection to predicting required time |
| US11281578B2 (en) | 2019-08-20 | 2022-03-22 | Micron Technology, Inc. | Garbage collection in a memory sub-system during a low battery state |
| US11726869B2 (en) | 2019-08-20 | 2023-08-15 | Micron Technology, Inc. | Performing error control operation on memory component for garbage collection |
| US11282567B2 (en) | 2019-08-20 | 2022-03-22 | Micron Technology, Inc. | Sequential SLC read optimization |
| US11281392B2 (en) | 2019-08-28 | 2022-03-22 | Micron Technology, Inc. | Garbage collection in a memory component using an adjusted parameter |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100528973B1 (en) | 2003-11-05 | 2005-11-16 | 한국전자통신연구원 | Apparatus and method for garbage collection |
| US7315917B2 (en) | 2005-01-20 | 2008-01-01 | Sandisk Corporation | Scheduling of housekeeping operations in flash memory systems |
- 2007
- 2007-07-19KRKR1020097004476Apatent/KR100922308B1/ennot_activeExpired - Fee Related
- 2007-07-19JPJP2009522934Apatent/JP4362549B1/ennot_activeExpired - Fee Related
- 2007-07-19WOPCT/US2007/073891patent/WO2008019218A2/enactiveApplication Filing
- 2007-07-23TWTW096126798Apatent/TWI343522B/ennot_activeIP Right Cessation
Also Published As
| Publication number | Publication date |
|---|---|
| KR20090053901A (en) | 2009-05-28 |
| TWI343522B (en) | 2011-06-11 |
| JP2009545819A (en) | 2009-12-24 |
| WO2008019218A2 (en) | 2008-02-14 |
| TW200825738A (en) | 2008-06-16 |
| KR100922308B1 (en) | 2009-10-21 |
| WO2008019218A3 (en) | 2008-09-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4362549B1 (en) | Gradual garbage collection | |
| US7444461B2 (en) | Methods for phased garbage collection | |
| US7451265B2 (en) | Non-volatile memory storage systems for phased garbage collection | |
| US7444462B2 (en) | Methods for phased garbage collection using phased garbage collection block or scratch pad block as a buffer | |
| US7441071B2 (en) | Memory systems for phased garbage collection using phased garbage collection block or scratch pad block as a buffer | |
| Hu et al. | Write amplification analysis in flash-based solid state drives | |
| US7464216B2 (en) | Method for phased garbage collection with state indicators | |
| US7444463B2 (en) | System for phased garbage collection with state indicators | |
| JP4931810B2 (en) | FAT analysis for optimized sequential cluster management | |
| US7987332B2 (en) | Methods for storing memory operations in a queue | |
| JP5571691B2 (en) | Maintaining mapping address tables in storage | |
| JP5728672B2 (en) | Hybrid memory management | |
| JP2021128582A (en) | Memory system and control method | |
| US20070016721A1 (en) | Flash file system power-up by using sequential sector allocation | |
| US20080162787A1 (en) | System for block relinking | |
| CN100501868C (en) | Implementation method of file system based on NAND Flash memory | |
| US20080235480A1 (en) | Systems for storing memory operations in a queue | |
| US20080235489A1 (en) | Systems for forcing an update block to remain sequential | |
| US20130103889A1 (en) | Page-buffer management of non-volatile memory-based mass storage devices | |
| US8341375B2 (en) | Methods for conversion of update blocks based on association with host file management data structures | |
| US11556249B2 (en) | Delaying random data relocation for reducing write amplification in storage devices | |
| US20080162612A1 (en) | Method for block relinking | |
| KR20160139864A (en) | Non-volatile memory system | |
| US7904670B2 (en) | Methods for conversion of update blocks based on comparison with a threshold size | |
| TWI380303B (en) | Methods for storing memory operations in a queue |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) | Free format text:JAPANESE INTERMEDIATE CODE: A01 | |
| A61 | First payment of annual fees (during grant procedure) | Free format text:JAPANESE INTERMEDIATE CODE: A61 Effective date:20090817 | |
| R150 | Certificate of patent or registration of utility model | Ref document number:4362549 Country of ref document:JP Free format text:JAPANESE INTERMEDIATE CODE: R150 Free format text:JAPANESE INTERMEDIATE CODE: R150 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20120821 Year of fee payment:3 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20120821 Year of fee payment:3 | |
| S111 | Request for change of ownership or part of ownership | Free format text:JAPANESE INTERMEDIATE CODE: R313113 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20120821 Year of fee payment:3 | |
| R360 | Written notification for declining of transfer of rights | Free format text:JAPANESE INTERMEDIATE CODE: R360 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20120821 Year of fee payment:3 | |
| R370 | Written measure of declining of transfer procedure | Free format text:JAPANESE INTERMEDIATE CODE: R370 | |
| S111 | Request for change of ownership or part of ownership | Free format text:JAPANESE INTERMEDIATE CODE: R313113 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20120821 Year of fee payment:3 | |
| R350 | Written notification of registration of transfer | Free format text:JAPANESE INTERMEDIATE CODE: R350 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20120821 Year of fee payment:3 | |
| FPAY | Renewal fee payment (event date is renewal date of database) | Free format text:PAYMENT UNTIL: 20130821 Year of fee payment:4 | |
| R250 | Receipt of annual fees | Free format text:JAPANESE INTERMEDIATE CODE: R250 | |
| R250 | Receipt of annual fees | Free format text:JAPANESE INTERMEDIATE CODE: R250 | |
| R250 | Receipt of annual fees | Free format text:JAPANESE INTERMEDIATE CODE: R250 | |
| R250 | Receipt of annual fees | Free format text:JAPANESE INTERMEDIATE CODE: R250 | |
| S533 | Written request for registration of change of name | Free format text:JAPANESE INTERMEDIATE CODE: R313533 | |
| R250 | Receipt of annual fees | Free format text:JAPANESE INTERMEDIATE CODE: R250 | |
| R350 | Written notification of registration of transfer | Free format text:JAPANESE INTERMEDIATE CODE: R350 | |
| R250 | Receipt of annual fees | Free format text:JAPANESE INTERMEDIATE CODE: R250 | |
| R250 | Receipt of annual fees | Free format text:JAPANESE INTERMEDIATE CODE: R250 | |
| LAPS | Cancellation because of no payment of annual fees |