(57)【要約】  フラッシュ消去可能なブロックに編成されている不揮発性メモリはブロックへ書き込む前に初めに論理グループにステージングすることによってホスト書き込みからデータを受け取る。各論理グループは、順序論理アドレスの所定のセットからのデータを包含し、ブロックより小さい固定されたサイズを有する。論理グループの全体はホストの論理アドレス空間を順序付けられた論理アドレスの重なり合わないサブレンジに分割することによって得られ、各論理グループは、少なくとも１ページの最小サイズと、少なくとも２論理グループを１ブロックにはめ込む、ホスト書き込みの代表的なサイズより１桁上までの最大サイズとにより定められる範囲の中の所定サイズを有する。このようにして、大きな論理グループを操作することに起因する過度のガーベッジコレクションが回避され、キャッシングＲＡＭのサイズを最小にするために、アドレス空間が小さくされる。
2014513850.tif 000002
【特許請求の範囲】
【請求項１】
ホストからのデータを不揮発性メモリに蓄積する方法であって、
前記不揮発性メモリを一緒に消去可能なメモリセルのブロックに編成するステップであって、各ブロックは複数のページを蓄積するためのものであり、各ページはデータの所定数の論理単位に並行してアクセスするためのものであり、各論理単位は前記ホストにより割り当てられた論理アドレスを有するステップと、
前記ホストの論理アドレス空間を順序付けられた論理アドレスの重なり合わないサブレンジに分割することによって複数の論理グループを定義するステップであって、各論理グループは少なくとも１ページの最小サイズと少なくとも２論理グループを１ブロックにはめ込む最大サイズとにより定められる範囲の中の所定サイズを有するステップと、
個々のホスト書き込みをバッファリングするステップと、
個々のホスト書き込みを１論理グループずつステージングするステップと、
ステージングされたどの論理グループをも前記不揮発性メモリに蓄積するステップと、
を含む方法。
【請求項２】
請求項１記載の方法において、
最大サイズは、ホスト書き込みのサイズより１桁まで大きい方法。
【請求項３】
請求項１記載の方法において、
前記ページは、３２〜６４キロバイトの間のサイズを有する方法。
【請求項４】
請求項１記載の方法において、
前記論理グループは、１〜４ページの範囲から選択されたサイズを有する方法。
【請求項５】
請求項１記載の方法において、
前記不揮発性メモリをＳＬＣ部分およびＭＬＣ部分に分割するステップであって、前記ＳＬＣ部分のメモリセルは各々１ビットのデータを蓄積し、前記ＭＬＣ部分のメモリセルは各々１ビットより多いデータを蓄積するステップをさらに含み、
前記バッファリングするステップと前記ステージングするステップは、前記ＳＬＣ部分で行われる方法。
【請求項６】
請求項５記載の方法において、
前記ＳＬＣ部分に蓄積されているデータを前記ＭＬＣ部分にコピーするステップをさらに含む方法。
【請求項７】
請求項６記載の方法において、
前記ＳＬＣ部分においてブロックのプールでアクティブなストレージを提供するステップをさらに含み、
前記ＳＬＣ部分に蓄積されているデータを前記ＭＬＣ部分にコピーするステップは、前記プールが満杯になったことに応答する方法。
【請求項８】
請求項５記載の方法において、
前記ＳＬＣ部分に第１のレイヤおよび第２のレイヤを設けるステップをさらに含み、
前記バッファリングするステップと前記ステージングするステップは、前記ＳＬＣ部分の第１のレイヤで行われる方法。
【請求項９】
請求項８記載の方法において、
前記バッファリングするステップと前記ステージングするステップは、論理アドレスによりアドレス指定可能なホスト書き込みのデータの短いフラグメントに関係する方法。
【請求項１０】
請求項８記載の方法において、
前記蓄積するステップは、前記ＳＬＣ部分の第２のレイヤで行われる方法。
【請求項１１】
不揮発性メモリであって、
一緒に消去可能なメモリセルのブロックに編成されたメモリアレイであって、各ブロックは複数のページを蓄積するためのものであり、各ページはデータの所定数の論理単位に並行してアクセスするためのものであり、各論理単位はホストにより割り当てられた論理アドレスを有するメモリアレイと、
前記ホストの論理アドレス空間を順序付けられた論理アドレスの重なり合わないサブレンジに分割することによって複数の論理グループを定義するメモリ構造であって、各論理グループは少なくとも１ページの最小サイズと少なくとも２論理グループを１ブロックにはめ込む最大サイズとにより定められる範囲の中の所定サイズを有するメモリ構造と、
個々のホスト書き込みをバッファリングするバッファと、
状態マシンであって、
個々のホスト書き込みを１論理グループずつステージングし、かつ
どのステージングされた論理グループをも前記不揮発性メモリに蓄積することを含む操作を制御する状態マシンと、
を備える不揮発性メモリ。
【請求項１２】
請求項１１記載の不揮発性メモリにおいて、
最大サイズは、ホスト書き込みのサイズより１桁まで大きい不揮発性メモリ。
【請求項１３】
請求項１１記載の不揮発性メモリにおいて、
ページは、３２〜６４キロバイトの間のサイズを有する不揮発性メモリ。
【請求項１４】
請求項１１記載の不揮発性メモリにおいて、
前記論理グループは、１〜４ページの範囲から選択されたサイズを有する不揮発性メモリ。
【請求項１５】
請求項１１記載の不揮発性メモリにおいて、
前記不揮発性メモリはＳＬＣ部分およびＭＬＣ部分を有し、前記ＳＬＣ部分のメモリセルは各々１ビットのデータを蓄積し、前記ＭＬＣ部分のメモリセルは各々１ビットより多いデータを蓄積し、
前記状態マシンは、前記ＳＬＣ部分で前記バッファリングする操作と前記ステージングする操作を制御する不揮発性メモリ。
【請求項１６】
請求項１５記載の不揮発性メモリにおいて、
前記状態マシンは、前記ＳＬＣ部分に蓄積されているデータの前記ＭＬＣ部分へのコピーを制御する不揮発性メモリ。
【請求項１７】
請求項１６記載の不揮発性メモリにおいて、
前記ＳＬＣにおけるブロックのプールでのアクティブなストレージをさらに備え、
前記状態マシンが前記ＳＬＣ部分に蓄積されているデータの前記ＭＬＣ部分へのコピーを制御することは、前記プールが満杯になったことに応答する不揮発性メモリ。
【請求項１８】
請求項１５記載の不揮発性メモリにおいて、
前記ＳＬＣ部分に第１のレイヤおよび第２のレイヤをさらに備え、
前記状態マシンは、前記ＳＬＣ部分の第１のレイヤで前記バッファリングする操作と前記ステージングする操作を制御する不揮発性メモリ。
【請求項１９】
請求項１８記載の不揮発性メモリにおいて、
前記バッファリングする操作と前記ステージングする操作は、論理アドレスによりアドレス指定可能なホスト書き込みのデータの短いフラグメントに関係する不揮発性メモリ。
【請求項２０】
請求項１８記載の不揮発性メモリにおいて、
前記状態マシンは、前記ＳＬＣ部分の第２のレイヤで前記蓄積する操作を制御する不揮発性メモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体フラッシュメモリのような再プログラム可能な不揮発性メモリシステムの操作に関し、特にメモリパーティションの階層的レイヤにおけるデータの効率的蓄積に関する。
【背景技術】
【０００２】
電荷を不揮発性に蓄積することのできる、特に小型のファクタカードとして実装されたＥＥＰＲＯＭおよびフラッシュＥＥＰＲＯＭの形のソリッドステートメモリは、種々のモバイルおよびハンドヘルド型装置、特に情報機器および消費者電子製品において好んで使われるストレージとなっている。同じくソリッドステートメモリであるＲＡＭ（ランダムアクセスメモリ）とは違って、フラッシュメモリは不揮発性であって、電源がオフにされた後でも、そこに蓄積されたデータを保持する。さらに、ＲＯＭ（読み出し専用メモリ）とは違って、フラッシュメモリはディスクストレージ装置と同様に書き換えが可能である。コストが高いにもかかわらず、フラッシュメモリは大量記憶用途にますます使われつつある。より最近に、ソリッドステートディスク（「ＳＳＤ」）の形のフラッシュメモリは、携帯用コンピュータおよび固定位置設備においてハードディスクに取って代わりはじめている。ハードディスクおよびフロッピーディスク（登録商標）のような回転磁気媒体に基づく在来の大容量ストレージは、モバイルおよびハンドヘルド環境のためには不適切である。その理由は、ディスクドライブはかさばりがちであり、機械的故障を起こしがちであり、高い待ち時間要件および高い電力要件を有することにある。これらの望ましくない属性がるが故に、ディスクベースのストレージはたいていのモバイルおよび携帯用途において実用的でない。一方、埋め込み型および取り外し可能なカードまたはＳＳＤの形のフラッシュメモリは、サイズが小さく、消費電力が少なく、高速で信頼性が高いという特徴があるが故に、モバイルおよびハンドヘルド型環境に理想的に適している。
【０００３】
フラッシュＥＥＰＲＯＭは、消去可能であって、そのメモリセルに新しいデータを書き込める、すなわち「プログラム」できるという点でＥＥＰＲＯＭ（電気的に消去可能でプログラム可能な読み出し専用メモリ）と同様なものである。その両方が、ソース領域およびドレイン領域の間で半導体基板内のチャネル領域の上に位置する、電界効果トランジスタ構造内の導電性フローティング（無接続）ゲートを利用する。次に、フローティングゲートの上にコントロールゲートが設けられる。トランジスタのしきい値電圧特性は、フローティングゲートに保持される電荷の量により制御される。すなわち、フローティングゲート上の電荷の所与のレベルについて、トランジスタがそのソース領域およびドレイン領域間の導通を許すべく「オン」にされる前にコントロールゲートに加えられなければならない対応する電圧（しきい値）がある。特に、フラッシュＥＥＰＲＯＭのようなフラッシュメモリは、メモリセルのブロック全体を同時に消去することを可能にする。
【０００４】
フローティングゲートは、或る範囲の電荷を保持することができ、従って或るしきい値電圧ウィンドウ内の任意のしきい値電圧レベルにプログラムされ得る。しきい値電圧ウィンドウのサイズはデバイスの最低および最高しきい値レベルにより定められ、それはフローティングゲートにプログラムされ得る電荷の範囲に対応する。しきい値ウィンドウは、一般的に、メモリデバイスの特性、動作条件および履歴に依存する。ウィンドウ内の各々の識別可能で、分解可能なしきい値電圧レベルの範囲は、原理的に、セルの一定のメモリ状態を指定するために使用され得る。
【０００５】
現在の商用製品は、単一ビットのデータまたは１ビットより多いデータを蓄積するようにフラッシュＥＥＰＲＯＭアレイの各ストレージを構成する。シングルレベルセル（ＳＬＣ）メモリは、バイナリモードで動作することによって各セルが１ビットのデータを蓄積し、単一の基準レベルが各ストレージのしきい値レベルの２つの範囲を区別する。
【０００６】
トランジスタのしきい値レベルは、そのストレージに蓄積される電荷レベルの範囲に対応する。メモリアレイのサイズを小さくすることに加えて、各ストレージトランジスタで１ビットより多いデータを蓄積することによってそのようなメモリアレイのデータ蓄積密度をさらに高めることが趨勢となっている。マルチレベルセル（ＭＬＣ）メモリは、マルチレベルモードで動作することによって各セルが１ビットより多いデータを蓄積し、２つ以上の基準レベルが各ストレージのしきい値レベルの２より多い範囲を区別する。例えば、商用フラッシュメモリ製品は、現在、４状態（ストレージあたりに２ビットのデータ）あるいは８状態（ストレージあたりに３ビットのデータ）あるいはストレージあたりに１６状態（ストレージあたりに４ビットのデータ）で動作する。各ストレージメモリトランジスタは、トランジスタがその中で実用的に動作させられ得るしきい値電圧の一定の総範囲（ウィンドウ）を有し、その範囲は、範囲について定められた状態の数と、その状態が互いから明確に区別され得るための状態間のマージンとに分割される。明らかに、メモリセルがより多くのビットを蓄積するように構成されるほど、メモリセルがその中で動作しなければならないエラーのマージンが小さくなる。
【０００７】
メモリセルとして役立つトランジスタは、通例、２つのメカニズムのうちの一方で「プログラム済み」状態にプログラムされる。「ホットエレクトロン注入」では、ドレインに印加された高電圧が電子を基板チャネル領域を横切らせて加速する。同時に、コントロールゲートに印加された高電圧がホットエレクトロンを薄いゲート誘電体を通してフローティングゲートへ引っ張る。「トンネル注入」では、基板に関して高電圧がコントロールゲートに印加される。このようにして、電子が基板から中間のフローティングゲートへ引っ張られる。メモリセルの最初に消去された電荷蓄積ユニットにメモリ状態を変えるように電子を注入することによってメモリに書き込むことを記述するために「プログラム」という用語が歴史的に使用されているけれども、用語は今では「書き込む」あるいは「記録する」などのもっとありふれた用語と交換可能に使用されている。
【０００８】
メモリデバイスは、幾つかのメカニズムによって消去され得る。ＥＥＰＲＯＭでは、薄い酸化物を通って基板チャネル領域へトンネリングするように（すなわち、ファウラー−ノルドハイムのトンネリング）フローティングゲート内の電子を誘導するためにコントロールゲートに関して高電圧を基板に印加することにより、メモリセルは電気的に消去可能である。通例、ＥＥＰＲＯＭはバイトごとに消去可能である。フラッシュＥＥＰＲＯＭでは、メモリは、全体を一斉にあるいは一度に１つ以上の最小の消去可能なブロックずつ、電気的に消去可能であり、最小の消去可能ブロックは１つ以上のセクタから成ることができ、各セクタは５１２バイト以上のデータを蓄積することができる。
【０００９】
メモリデバイスは、通例、カードに搭載され得る１つ以上のメモリチップを含む。各メモリチップは、デコーダおよび消去回路、書き込み回路および読み出し回路などの周辺回路によりサポートされるメモリセルのアレイを含む。より精巧なメモリデバイスは、インテリジェントでより高レベルのメモリ操作およびインターフェイスを行うコントローラを伴っている。最近、ＳＳＤの形のメモリデバイスが標準的なハードディスクのフォームファクタとして商業的に提供されつつある。
【００１０】
今日使用されている商業的に成功した不揮発性ソリッドステートメモリデバイスが数多くある。それらのメモリデバイスがフラッシュＥＥＰＲＯＭであってもよく、あるいは他の種類の不揮発性メモリセルを採用することもできる。フラッシュメモリおよびシステムの例並びにそれらを製造する方法が、米国特許第５，０７０，０３２号（特許文献１）、第５，０９５，３４４号（特許文献２）、第５，３１５，５４１号（特許文献３）、第５，３４３，０６３号（特許文献４）、並びに第５，６６１，０５３号（特許文献５）、第５，３１３，４２１号（特許文献６）、および第６，２２２，７６２号（特許文献７）に記載されている。特に、ＮＡＮＤストリング構造を有するフラッシュメモリデバイスが、米国特許第５，５７０，３１５号（特許文献８）、第５，９０３，４９５号（特許文献９）、第６，０４６，９３５号（特許文献１０）に記載されている。
【００１１】
不揮発性メモリデバイスは、電荷を蓄積するための誘電体層を有するメモリセルからも製造される。前述した導電性フローティングゲート素子の代わりに、誘電体層が使用される。誘電体ストレージを利用するそのようなメモリデバイスは、Eitan et al., "NROM: A Novel Localized Trapping, 2-Bit Nonvolatile Memory Cell," IEEE Electron Device Letters, vol. 21, no. 11, November 2000, pp. 543-545（非特許文献１）に記述されている。ＯＮＯ誘電体層はソース拡散およびドレイン拡散の間のチャネルを横断して広がる。一方の１データビットのための電荷はドレインに隣接して誘電体層に局在させられ、もう一方のデータビットのための電荷はソースに隣接して誘電体層に局在させられる。例えば、米国特許第５，７６８，１９２号（特許文献１１）および第６，０１１，７２５号（特許文献１２）には、２つの二酸化ケイ素層の間に挟まれたトラッピング誘電体を有する不揮発性メモリセルが開示されている。多状態データ蓄積は、誘電体の中の空間的に分離されている電荷蓄積領域のバイナリ状態を別々に読み出すことによって実行される。
【００１２】
フラッシュメモリ特性および動向
フラッシュメモリは、在来のディスクストレージまたはＲＡＭとは全く違うようにふるまう。第１に、フラッシュメモリに蓄積されている現存するデータは、単に上書きされることによってはアップデートされ得ない。各セルは、新たな書き込みがセルで行われ得る前に、最初に消去されなければならない。従って、アップデートは、常に、新しく空いている位置に書き込まれる。性能を高めるために、データをページごとにアクセスするように１グループのセルが並行して操作される。アップデートされたページを新しい位置に書き込ませることによってデータのページがアップデートされるとき、廃棄されるページは無効かつ使用済みにされて、ストレージを散らかす不要データとなり、廃棄されるページが占有しているスペースを解放するために結局は一掃される。
【００１３】
アップデートの管理と無効なものを廃棄することは、フラッシュメモリのブロック構造により複雑化される。フラッシュメモリを消去することと消去性能を高めることは割合に時間がかかり、メモリは、メモリセルのブロック全体が一緒に同時に消去される消去ブロックに編成される。ブロックは一般的に数個のページを含む。データは１ページずつブロックに蓄積されるので、結局、そのデータの一部は使用済みになる。このことは、スペースをふさぐ多くの不要データをブロックが包含することになるということを意味する。しかし、ブロックは１つの単位として消去され得るに過ぎないので、ブロックとともに不要データが消去される前に、ブロック内の有効なデータは初めに回収されて他のブロックにコピーされなければならない。この操作は一般にガーベッジコレクションと呼ばれ、フラッシュメモリのブロック構造のオーバーヘッドである。ブロックがより大きいほど、ガーベッジコレクションのためにより多くの時間が必要となる。同様に、ブロック内のデータがより頻繁にアップデートされるほど、ブロックはより頻繁にガーベッジコレクションされなければならない。ガーベッジコレクションは好ましくは書き込み操作中のようにフォアグラウンドで行われる。これは明らかに書き込み速度を悪化させる。
【００１４】
フラッシュメモリの初期の用途は、主として、携帯可能なホストのために音楽およびビデオファイルのようなメディアファイルを蓄積するための用途である。これらのファイルは、メモリを１ブロックずつ満たしてゆくシーケンシャルな論理アドレスの長いデータランでありがちである。これらのデータは、本質的に永久保存されるものであって、あまりアップデートされるものではない。従って、これらのタイプのデータのためにはブロック構造が良く働き、ガーベッジコレクションする必要はめったにないので書き込み中のパフォーマンスヒットはほとんどない。データは規則的なシーケンシャルアドレス性であるので、論理アドレス範囲を論理グループに分割することができ、各論理グループは、１論理グループのデータが１ブロック内にきちんとおさまるという意味において消去ブロックと整列させられる。このようにして、所与の論理アドレスを有するページは、ページが属する論理グループをどのブロックが蓄積しているかによって突き止められ得るので、アドレス指定グラニュラリティは主としてページとしてブロックレベルにある。論理グループは、その論理アドレスが順次に並んでいる自己索引付け式にブロックに蓄積されるので、ページは速やかに突き止められ得る。
【００１５】
論理グループを実現するブロック管理システムは、通例、論理グループをページレベルでトラッキングすることによってアップデートおよび非シーケンシャルな書き込みを処理する。システムはページレベルのトラッキングのために所定量のリソースを割り当て、このことは、非シーケンシャルまたは使用済みのデータを有する論理グループの数を限定することを明らかにする。一般的に、アップデートを受けるとき、規則的なブロックのうちの幾つかは使用済みデータを包含し、それらを追跡するためにもリソースの一部が消費される。割り当てを上回ると、非シーケンシャルまたは使用済みのデータを有する選択されたブロックはシーケンシャルな順序の規則的なブロックに戻される。このことは、最新のアップデートに伴ってシーケンシャルな順序で新しいブロックに書き換えることにより成し遂げられる。しかし、再配置はパフォーマンスヒットを強いる。そのようなシステムは、ブロックレベルでトラッキングされているそのような規則的なブロックを主として維持し、幾つかのランダムな書き込みだけをページレベルでトラッキングすることに資するデータをホストが書き込む場合には、良く働く。従って、ブロック境界に整列させられる論理グループを実現することにより、アドレステーブルは大幅に簡素化され小さくされる。
【００１６】
しかし、論理グループを実現するブロック管理システムは、ホストが主として短くて非シーケンシャルなデータを書き込むと、あまり最適ではなくなり始める。このタイプの書き込みパターンは、パーソナルコンピュータあるいはスマートモバイルデバイスからの用途では一般的である。フラッシュメモリを使用するソリッドステートディスク（ＳＳＤ）は、その低電力、速度および丈夫さの故に、ディスクストレージにとって魅力的な代替品である。長いシーケンシャルな書き込みの代わりに、フラッシュメモリは今では主として短いランダムな書き込みを処理しなくてはならない。初めは、空きスペースが見つかって、そこにデータを書き込める間は、性能は悪くならない。しかし、絶えず使用され頻繁にアップデートされると、ページトラッキングのための所定のリソースはついには使い尽くされてしまう。その時点で、次の書き込みはブロックの再配置を伴わなければならないかもしれないので、パフォーマンスは大ヒットをとり得る。ブロックがより大きいほど、ブロックの再配置を行うためにより長い時間がかかるようになる。さらに、大きなブロックと短くて非シーケンシャルなデータは、ブロック内の論理グループに無効なデータをより頻繁に包含させてページアドレス指定リソースをより早く消費させ、従って再配置をより頻繁に行わせる。
【００１７】
ブロックサイズはメモリ技術の各々の新しい世代とともに幾何学的に大きくなりがちであるので、大きなブロックサイズに伴う問題は単にブロックサイズを小さくすることによっては容易に解決され得ない。回路の集積高度化に伴って、より多くのメモリセルが同じダイに収容されつつある。列の数と行の数で測られるブロックサイズは幾何学的に大きくなる。これは、ＮＡＮＤタイプのメモリの場合、特にそうである。メモリはＮＡＮＤストリングのアレイであり、各ストリングはメモリセルのデイジーチェーンであって、最小消去ブロックはそのようなＮＡＮＤストリングの１つの行によって形成されなければならない。ＮＡＮＤストリングが３２個のセルを有するとすれば、ブロックは３２行のセルを包含する。ＮＡＮＤストリング内のメモリセルの数は各世代に伴っても増大するので、ブロックサイズは列方向にかつ行方向に増大する。
【００１８】
ブロックサイズは、物理的なメモリ構造により規定され、現在の世代において４ＭＢの大きさである。一方、パーソナルコンピュータのオペレーティングシステムは、通例、５１２ｋＢのサイズで論理セクタを割り当て、しばしば４ｋＢ単位で論理セクタのクラスタとしてページを書き込む。従って、ブロックおよびページに対応する論理グループのアドレス指定グラニュラリティには大きなミスマッチがある。論理グループ方式では、ブロックにとっての理想的な状況は、何も書き込まれないか、あるいは有効なデータの論理グループ全体でブロックが順に満たされることである。いずれの場合にも断片化はなくて、ガーベッジコレクションあるいは再配置の必要はない。大きなブロックに対する短いランダムな書き込みの場合、ブロックは非常に急速に非理想的となり、ついには再配置を必要とするようになる。これは、同じページが書き込まれてその後に１回以上再コピーされなければならない（「書き込み増幅」とも呼ばれる）かも知れないので、効率の悪い書き込みと同等なものである。
【００１９】
短いランダムな書き込みに適する代わりの、在来のアドレス指定アプローチは、論理グループを用いずに、全てのページを、それがブロックに書き込まれているときに、独立にトラッキングすることである。蓄積されているデータを規則的な論理グループとしてブロックで維持する代わりに、各ページがどのブロックにブロック内でどれほどのオフセットで蓄積されているかに関してトラッキングされる。従って、このページアドレス指定方式では、グループ内のデータをシーケンシャルな論理アドレスの順序で蓄積したり、あるいは維持したりする負担はない。しかし、ページアドレス指定方式は、論理グループアドレス方式のものよりはるかに大きいアドレステーブルを有する。例えば、１ブロック内に１，０００ページがあるとすれば、ページアドレス指定方式のためのアドレステーブルはほぼ２〜３桁大きい。
【００２０】
ページアドレス指定方式は、はるかに大きなアドレステーブルによってペナルティを強いる。実際、より多くのシステムリソースと、メモリコントローラと協働する割合に大きなＲＡＭとを必要とする。アドレステーブルを普通はフラッシュメモリで維持するけれども、それは、より高速なアクセスを提供するために動作中にコントローラＲＡＭにキャッシュされるからである。現行の技術は、高々２〜４ＭＢのＲＡＭをコントローラチップ上に製造することを可能にする。これはページアドレス指定方式を使用するシステムのためには不十分であり、追加の外部ＲＡＭチップが必要になる。外部ＲＡＭチップをサポートするための追加のピン配列およびインターフェイス回路はコストを著しく増大させる。
【００２１】
４ｋＢなどの非常に小さい単位を有するアドレス指定グラニュラリティに伴う他の１つの問題は、それが断片化したデータを作り出すことであり、そのデータは、読み出しおよびデータコピー（アップデートに起因する）の間に最大の並列性が達成不可能であるほどにブロック間に散在させられる。さらに、小さなアップデートが１つ以上のブロック全体のコピーをなおトリガーし得るのでコピーの量が増大する。
【００２２】
従って、前述した不利益および問題に悩まされることなく大ブロックへの短いランダムな書き込みにより特徴づけられるデータアクセスを効率よく処理し得る不揮発性メモリを提供する必要がある。
【先行技術文献】
【特許文献】
【００２３】
【特許文献１】米国特許第５，０７０，０３２号
【特許文献２】米国特許第５，０９５，３４４号
【特許文献３】米国特許第５，３１５，５４１号
【特許文献４】米国特許第５，３４３，０６３号
【特許文献５】米国特許第５，６６１，０５３号
【特許文献６】米国特許第５，３１３，４２１号
【特許文献７】米国特許第６，２２２，７６２号
【特許文献８】米国特許第５，５７０，３１５号
【特許文献９】米国特許第５，９０３，４９５号
【特許文献１０】米国特許第６，０４６，９３５号
【特許文献１１】米国特許第５，７６８，１９２号
【特許文献１２】米国特許第６，０１１，７２５号
【特許文献１３】米国特許出願公開第２０１０／０１７２１８０号
【特許文献１４】米国特許出願公開第２００５／０１４４５１６号
【特許文献１５】米国特許第７，１３９，８６４号
【特許文献１６】米国特許出願第１２／６４２，５８４号
【特許文献１７】米国特許第７，６３３，７９９号
【非特許文献】
【００２４】
【非特許文献１】Eitan et al., "NROM: A Novel Localized Trapping, 2-Bit Nonvolatile Memory Cell," IEEE Electron Device Letters, vol. 21, no. 11, November 2000, pp. 543-545
【発明の概要】
【００２５】
小さな論理グループを使用するブロック管理
本発明の１つの態様に従って、ブロックがデータの複数の論理グループを蓄積するようにホストからの順序付けられている論理アドレス範囲が論理グループに分割されるブロック管理システムを有する不揮発性メモリが提供される。各論理グループは、少なくともホスト書き込みのサイズと同じ桁から一桁上までの範囲を有するサイズであるけれども、少なくとも、メモリによりサポートされる最大並列性の読み出しまたは書き込みの単位であるページまたはメタページのサイズを有するものである。論理グループのサイズを消去ブロックのサイズと切り離し、ホスト書き込みのサイズおよび性質により適合するサイズとすることにより、論理グループは、アドレス指定を簡素化するとともに、性能に大きな影響を与える過度の書き換えをトリガーすることなく限定されたシステムリソースを節約するという利益をもたらす。
【００２６】
従って、ブロックのサイズと整列する論理グループのサイズの代わりに、ガーベッジコレクションおよび書き換えを最小化するために、論理グループのサイズは代表的なホスト書き込みのグラニュラリティと一致するように設定される。集積回路の密度が高まるにつれて、各ブロックはデータの１つではなくて複数の論理ブロックを保持するようになる。実際、ホスト書き込みは１論理グループずつバッファリングおよびステージングされ、論理グループは次いでブロックに書き込まれる。
【００２７】
好ましい実現形態では、メモリは、ＳＬＣ部分およびＭＬＣ部分に分割され、第１、第２および第３の操作および機能レイヤを含む。第１および第２のレイヤはＳＬＣ部分で動作する。第３のレイヤはＭＬＣ部分で動作する。第１のレイヤは、ホストからの書き込みデータを初めに蓄積して、各論理グループを第２のレイヤまたは第３のレイヤに再配置する前にデータを１論理グループずつステージングするためのものである。第２のレイヤは、ホストデータを論理グループレベルで蓄積するためのＳＬＣブロックのプールにおけるアクティブな蓄積を提供する。プールが満杯になると、最少の潜在的な書き換えを伴う論理グループを、より高い密度で蓄積する第３のレイヤへ追い立てることによって、より多くの空間が作られる。
【００２８】
本質的に、第２のレイヤは、断片化したおよび中間サイズのホスト書き込みが到着する高速ＳＬＣストレージ領域を提供する。第２のレイヤがなくて、データがアクセスされる前にデータをＭＬＣストレージの第３のレイヤへ伝送するために第１のレイヤが本質的にＦＩＦＯとして動作する従来のシステムとは違って、この第２のレイヤはユーザデータの作業セットを高速ＳＬＣストレージ領域に維持する。
このようにして、ユーザデータのアクティブなセットがより高速のＳＬＣメモリで優先的に維持され、ＳＬＣメモリで容量がなくなったときだけ、ＭＬＣメモリで蓄積するのにより適している選択された論理グループがＭＬＣメモリへ追い立てられる。
より小さなサイズの論理グループの実現は、過度の書き換えをトリガーせず、同時に、より小さなアドレステーブルを使用することを可能にするという利益を有する。このことは、高価な外部ＲＡＭを必要とせずに、アドレステーブルをコントローラチップに統合されているＲＡＭにキャッシュするように十分にコンパクトなサイズであるという利益を有する。
【００２９】
本発明のさらなる特徴および利点を本発明の好ましい実施形態についての以下の記述から理解することができ、この記述は添付図面と関連して考慮されるべきである。
【図面の簡単な説明】
【００３０】
【図１】本発明の特徴が具体化されているメモリデバイスと通信するホストを示す。
【図２】並行して感知またはプログラムされる、例えばＮＡＮＤ構成に編成されたメモリセルのページを示す。
【図３】消去可能なブロックに編成されたメモリアレイの例を概略的に示す。
【図４】複数のアレイを有するメモリチップと最大並列性のための操作を概略的に示す。
【図５】高度の並列性を有するメモリ構造を概略的に示す。
【図６】各セルが２つの可能な状態のうちの一方にあるセルの集団を有するバイナリメモリを示す。
【図７】各セルが８個の可能な状態のうちの１つにあるセルの集団を有する多状態メモリを示す。
【図８】本発明を実施するのに適する物理的メモリアーキテクチャの例を示す。
【図９】２レイヤデータストレージシステムにおけるＳＬＣ部分およびＭＬＣ部分の間のデータ経路を概略的に示す。
【図１０】図９に示されているＳＬＣレイヤをより詳しく示す。
【図１１】本発明に従うブロック管理システムのメモリ編成におけるページを示す。
【図１２】ブロック管理システムにおける論理グループを示す。
【図１３Ａ】複数の論理グループからのデータを収容する消去ブロックを示す。
【図１３Ｂ】ホスト書き込みを小さな論理グループによって不揮発性メモリに蓄積する方式を示す流れ図である。
【図１４】本発明に従う異なるメモリパーティションでブロックおよびページを管理するためのシステムアーキテクチャを示す。
【図１５】図１４に示されている第２のレイヤをより詳しく示す。
【図１６】「ホット」論理グループの場合についての論理グループの「温度」ソーティングを示す。
【図１７】「コールド」論理グループの場合についての論理グループの「温度」ソーティングを示す。
【図１８】異なるタイプの書き込みが書き込みの知覚される温度に従ってどのようにインタラクティブにソートされるかを示す。
【図１９】メモリストレージおよび操作のための温度ソーティングの方式を示す流れ図である。
【図２０】論理グループレベルでの温度ソーティングの方式を示す流れ図である。
【図２１】ブロックレベルでの温度ソーティングの方式を示す流れ図である。
【発明を実施するための形態】
【００３１】
メモリシステム
図１は、本発明の特徴が具体化されているメモリデバイスと通信するホストを示す。ホスト８０は通例、メモリデバイス９０に蓄積されるべきデータを送るか、あるいはメモリデバイス９０を読み出すことによってデータを取り出す。メモリデバイス９０はメモリコントローラ１０２により管理される１つ以上のメモリチップ１００を含む。メモリチップ１００はメモリセルのメモリアレイ２００を含み、各セルは、複数ビットのデータを蓄積するためのマルチレベルセル（「ＭＬＣ」）として構成されるとともに、１ビットのデータを蓄積するためのシングルレベルセル（「ＳＬＣ」）として構成され得る。メモリチップは、行デコーダおよび列デコーダ、センスモジュール、データラッチ並びにＩ／Ｏ回路などの周辺回路２０４も含む。オンチップ制御回路１１０は、各チップの低レベルメモリ操作を制御する。制御回路１１０は、メモリアレイ２００に対してメモリ操作を行うために周辺回路と協働するオンチップコントローラである。制御回路１１０は通例、データバス２３１並びに制御およびアドレスバス１１１を介してメモリ操作のチップレベル制御を提供するために状態マシン１１２を含む。
【００３２】
多くの実施例において、ホスト８０はメモリコントローラ１０２を介してメモリチップ１００と通信しインタラクトする。コントローラ１０２は、メモリチップと協働し、高レベルのメモリ操作を制御して管理する。ファームウェア６０は、コントローラ１０２の機能を実行するためのコードを提供する。エラー訂正コード（「ＥＣＣ」）プロセッサ６２は、メモリデバイスの動作中にＥＣＣを処理する。
【００３３】
例えば、ホスト書き込み時に、ホスト１０は、ホストのオペレーティングシステムのファイルシステムから割り当てられた論理セクタ単位でメモリアレイ２００に書き込まれるべきデータを送る。コントローラで実装されたメモリブロック管理システムは、セクタをステージングするとともにセクタをメモリアレイの物理的構造にマッピングし蓄積する。好ましいブロック管理システムが、その全体が本願明細書において参照により援用されている、米国特許出願公開第２０１０／０１７２１８０号（特許文献１３）に開示されている。
【００３４】
物理的メモリアーキテクチャ
読み出しおよびプログラミング性能を改善するために、アレイ中の複数の電荷蓄積素子またはメモリトランジスタが並行して読み出されるかまたはプログラムされる。従って、１「ページ」のメモリ素子が一緒に読み出されるかまたはプログラムされる。現存するメモリアーキテクチャでは、行は通例、数個のインターリーブされたページを包含するか、あるいは１ページを構成することができる。ページの全メモリ素子が一緒に読み出されるかまたはプログラムされる。
【００３５】
図２は、並行して感知されるかまたはプログラムされる、例えばＮＡＮＤ構成に編成されたメモリセルのページを示す。図２は、本質的に、図１のメモリアレイ２００内のＮＡＮＤストリング５０のバンクを示す。ページ６０などの「ページ」は、並行して感知されるかまたはプログラムされ得るメモリセルのグループである。これは、周辺回路においてセンスアンプの対応するページ２１０によって成し遂げられる。感知された結果は、データラッチ２２０の対応するセットにラッチされる。各センスアンプは、ビット線３６を介してＮＡＮＤストリング５０などのＮＡＮＤストリングに結合され得る。例えば、ページ６０は、１つの行に沿っていて、共通にワード線ＷＬ３に接続されたページのセルのコントロールゲートに印加された感知電圧により感知される。各列に沿って、セル１０などの各セルは、ビット線３６を介して１つのセンスアンプによりアクセス可能である。データラッチ２２０内のデータは、データＩ／Ｏバス２３１を介してメモリコントローラ１０２からまたはメモリコントローラ１０２へトグルされる。
前に言及したページは、物理的ページのメモリセルまたはセンスアンプである。文脈により、各セルがマルチビットデータを蓄積する場合、各物理的ページは複数のデータページを有する。
【００３６】
ＮＡＮＤストリング５０は、それぞれ両端にソース端子およびドレイン端子を形成するべくメモリトランジスタのソースおよびドレインによりデイジーチェーン接続された一連のメモリトランジスタ１０である。選択トランジスタＳ１、Ｓ２の対は、それぞれＮＡＮＤストリングのソース端子およびドレイン端子を介してのメモリトランジスタチェーンの外部への接続を制御する。メモリアレイにおいて、ソース選択トランジスタＳ１がオンにされると、ソース端子はソース線３４に結合される。同様に、ドレイン選択トランジスタＳ２がオンにされると、ＮＡＮＤストリングのドレイン端子はメモリアレイのビット線３６に結合される。チェーン内の各メモリトランジスタ１０は、メモリセルとして動作する。メモリセルは、意図されたメモリ状態を表すように所与の量の電荷を蓄積する電荷蓄積素子２０を有する。各メモリトランジスタのコントロールゲートは、読み出し操作および書き込み操作に対する制御を可能にする。ＮＡＮＤストリングの行の対応するメモリトランジスタのコントロールゲートは全て同じワード線（ＷＬ０、ＷＬ１・・・など）に接続されている。同様に、選択トランジスタＳ１、Ｓ２の各々のコントロールゲート（それぞれ選択線ＳＧＳおよびＳＧＤを介してアクセスされる）は、それぞれ選択トランジスタのソース端子およびドレイン端子を介してのＮＡＮＤストリングへの制御アクセスを提供する。
【００３７】
消去ブロック
フラッシュメモリと他のタイプのメモリとの１つの重要な差異は、セルが消去済み状態からプログラムされなければならないことである。すなわち、フローティングゲートが初めに電荷を空にしなければならない。その後、プログラミングにより逆に所望量の電荷をフローティングゲートに加える。プログラミングは、よりプログラムされた状態からより少なくプログラムされた状態へ移るようにフローティングゲートから電荷の一部を除去することをサポートしていない。このことは、アップデートデータが既存のデータを上書きすることができず、前もって書き込まれていない位置に書き込まれなければならないということを意味する。
【００３８】
さらに、消去とはフローティングゲートから全ての電荷を空にすることであって、一般にかなりの時間を要する。この理由から、消去を１セルずつあるいは１ページずつ行うのでさえ、煩わしくて低速である。実際には、メモリセルのアレイはメモリセルの多数のブロックに分割されている。フラッシュＥＥＰＲＯＭシステムの場合に普通であるように、ブロックは消去の単位である。すなわち、各ブロックは、一緒に消去される最小数のメモリセルを包含する。
【００３９】
図３は、消去可能なブロックを成して編成されたメモリアレイの例を概略的に示す。電荷蓄積メモリデバイスのプログラミングは、より多くの電荷を電荷蓄積メモリデバイスの電荷蓄積素子に加えるという結果をもたらし得るだけである。従って、プログラミング操作前に、メモリセルの電荷蓄積素子内に存在する電荷を除去（あるいは消去）しなければならない。ＥＥＰＲＯＭなどの不揮発性メモリは、セルのアレイ２００全体、あるいはアレイのセルの有意なグループが電気的に一緒に（すなわち、即座に）消去されるときには、「フラッシュ」ＥＥＰＲＯＭと称される。いったん消去されると、そのグループのセルを再プログラムすることができる。一緒に消去可能なセルのグループは１つ以上のアドレス指定可能な消去単位３００から成り得る。消去単位またはブロック３００は通例、１ページ以上のデータを蓄積し、ページはプログラミングおよび読み出しの最小単位であるけれども、単一の操作で２ページ以上がプログラムされるかまたは読み出され得る。各ページは通例１セクタ以上のデータを蓄積し、セクタのサイズはホストシステムにより定められる。一例は、磁気ディスクドライブに関して確立されている標準に従う５１２バイトのユーザデータのセクタと、ユーザデータおよび／またはユーザデータが蓄積されているブロックとに関する或るバイト数のオーバーヘッド情報である。
【００４０】
図３に示されている例では、メモリアレイ２００内の個々のメモリセルは、ＷＬ０〜ＷＬｙなどのワード線４２とＢＬ０〜ＢＬｘなどのビット線３６とによりアクセス可能である。メモリは、消去ブロック０、１・・・ｍなどの消去ブロックに編成されている。ＮＡＮＤストリング５０（図２を参照）が１６個のメモリセルを包含しているとすれば、アレイ内のＮＡＮＤストリングの第１のバンクは選択線４４とＷＬ０〜ＷＬ１５などのワード線４２とによりアクセス可能となる。消去ブロック０は、一緒に消去されるＮＡＮＤストリングの第１のバンクの全メモリセルを有するように編成される。メモリアーキテクチャでは、２バンク以上のＮＡＮＤストリングが一緒に消去され得る。
【００４１】
メタページおよびメタブロック編成での向上した並列性
図４は、複数のアレイを有するメモリチップと最大並列性のための操作とを概略的に示す。例えば、メモリチップは２つのダイ（ダイ１およびダイ２）を有して製造される。各ダイは２つのメモリプレーンを包含する。例えば、ダイ１はメモリプレーン１およびメモリプレーン２を包含し、ダイ２はメモリプレーン３およびメモリプレーン４を包含する。各メモリプレーンは複数のブロックを包含し、各ブロックは複数のページを包含する。例えば、メモリプレーン１はブロック１を含み、ブロック１はページＰ１を含む。
【００４２】
ブロック１〜４などのブロックは各々、図３に示されているブロック３００などの、メモリプレーン内のメモリアレイの物理的アーキテクチャにより定められる最小消去単位（ＭＥＵ）である。同様に、Ｐ１〜Ｐ４などのページは各々、並行して動作する読み出し／書き込み回路数により定められる最小読み出し／書き込み単位である。
プログラミング速度および消去速度を最大化するために、複数のＭＥＵ内に位置する複数のページの情報が並行してプログラムされるとともに複数のＭＥＵが並行して消去されるように構成することによりなるべく高度に並列性が利用される。
【００４３】
図５は、高度の並列性を有するメモリ構造を概略的に示す。例えば、ページＰ１〜Ｐ４は、システムレベルにおいて読み出しまたは書き込みの最小単位として操作される「メタページ」として互いにリンクされる。同様に、ブロック１〜４は、システムレベルにおいて消去の最小単位として操作される「メタブロック」として互いにリンクされる。フラッシュメモリの物理的アドレス空間をメタブロックのセットとして扱い、メタブロックは消去の最小単位である。本願明細書の中では、「メタブロック」（例えば、３００−４）および「ブロック」３００という用語は、媒体管理のためのシステムレベルでの消去の最小単位を定義するために同義的に使用され、「最小消去単位」（すなわち、ＭＥＵ）という用語はフラッシュメモリの消去の最小単位を示すために使用される。同様に、「メタページ」（例えば６０−４）および「ページ」６０という用語は、ページがシステムレベルにおいてより高度の並列性を有するメタページに構成され得るという理解を伴って同義的に使用される。
【００４４】
図４は、１つのメモリチップ内の複数のプレーンからメモリ構造を集めることによってより高度の並列性が達成され得ることを示しているけれども、他の実施形態ではプレーンは２つ以上のメモリチップに分散させられ得ることを理解するべきである。
ＭＥＵをリンクおよび再リンクしてメタブロックとすることが、その全体が本願明細書において参照により援用されている、米国特許出願公開第２００５／０１４４５１６号および（特許文献１４）米国特許第７，１３９，８６４号（特許文献１５）においても開示されている。
【００４５】
バイナリ（ＳＬＣ）およびマルチレベル（ＭＬＣ）メモリセルの例
前述したように、不揮発性メモリの一例は、各々そのチャネル領域およびコントロールゲートの間に電荷蓄積層を有する電界効果トランジスタのアレイから形成される。電荷蓄積層またはユニットは、各電界効果トランジスタのために或る範囲のしきい値電圧を生じさせる或る範囲の電荷を蓄積することができる。可能なしきい値電圧の範囲は１つのしきい値ウィンドウにわたる。しきい値ウィンドウがしきい値電圧の複数のサブレンジまたはゾーンに分割されたとき、各々の分解可能なゾーンは、１つのメモリセル用のために異なるメモリ状態を表すために使用される。複数のメモリ状態は１つ以上のバイナリビットによりコード化され得る。
【００４６】
図６は、各々２つの可能な状態のうちの一方にあるセルの集団を有するバイナリメモリを示す。各メモリセルのしきい値ウィンドウは単一の区分レベルによって２つの識別可能なゾーンに分割される。図６（０）に示されているように、読み出し中、セルのしきい値レベルがどのゾーンの中にあるかを判定するために下側ゾーンと上側ゾーンとの間の読み出し区分レベルｒＶ1 が使用される。セルは、そのしきい値が下側ゾーン内に位置する場合には「消去済み」状態にあり、そのしきい値が上側ゾーン内に位置する場合には「プログラム済み」状態にある。図６（１）は、メモリの全セルが初めに「消去済み」状態にあることを示す。図６（２）は、セルのうちの幾つかが「プログラム済み」状態にプログラムされることを示す。メモリ状態をコード化するために１ビットまたはバイナリコードが使用される。例えば、ビット値「１」は「消去済み」状態を表し、「０」は「プログラム済み」状態を表す。通例、プログラミングは１つ以上のプログラミング電圧パルスの印加によって行われる。各パルス後、セルは、しきい値がベリファイ区分レベルｖＶ1 を越えて移動したかをベリファイするために感知される。このようなメモリセル分割を有するメモリは、「バイナリ」メモリまたはシングルレベルセル（ＳＬＣ）メモリと称される。バイナリまたはＳＬＣメモリは、しきい値ウィンドウ全体が２つのゾーンにより占められるに過ぎないので広いエラーマージンで動作するということが分かる。
【００４７】
図７は、各セルが８個の可能な状態のうちの１つにあるセルの集団を有する多状態メモリを示す。各メモリセルのしきい値ウィンドウは、少なくとも７個の区分レベルによって８個の識別可能なゾーンに分割されている。図７（０）に示されているように、読み出し中、セルのしきい値レベルがどのゾーンにあるかを判定するために読み出し区分レベルｒＶ1 〜ｒＶ7 が使用される。セルは、そのしきい値が最低のゾーン内に位置する場合には「消去済み」状態にあり、そのしきい値が上のほうのゾーン内に位置する場合には複数の「プログラム済み」状態のうちの１つにある。図７（１）は、メモリの全セルが初めに「消去済み」状態にあることを示す。図７（２）は、セルのうちの幾つかが「プログラム済み」状態にプログラムされることを示す。この８個の状態の各々を表すために下位ビット、中央ビットおよび上位ビットを有する３ビットコードが使用され得る。例えば、「０」、「１」、「２」、「３」、「４」、「５」、「６」および「７」状態はそれぞれ「１１１」、「０１１」、「００１」、「１０１」、「１００」、「０００」、「０１０」および「１１０」により表される。通例、プログラミングは１つ以上のプログラミング電圧パルスの印加により行われる。各パルス後、ベリファイ区分レベルｖＶ1 〜ｖＶ7 のうちの１つである基準を超えてしきい値が移動したかをベリファイするためにセルは感知される。このようなメモリセル分割を有するメモリは「多状態」メモリまたはマルチレベルセル（「ＭＬＣ」）と称される。数プログラミング方法は、フローティングゲート間摂動を緩和するために、セルがそのターゲット状態へプログラムされる前に複数のプログラミングパスを使用する。
同様に、４ビットコードを蓄積するメモリは、１６個の状態の各々を表す下位、第１の中央、第２の中央および上位ビットを有する。しきい値ウィンドウは少なくとも１５個の区分レベルによって１６個の識別可能なゾーンに区分される。
【００４８】
メモリの有限なしきい値ウィンドウがより多くの領域に分割されるにつれて、プログラミングおよび読み出しのための分解能は必然的により細かくなる。従って、分割されたゾーンがより少ないメモリのエラーマージンと比べて多状態またはＭＬＣメモリは必然的により狭いエラーマージンで動作する。換言すれば、エラー率は各セルに蓄積されるビットの数とともに増大する。一般に、エラー率はしきい値ウィンドウ内の分割されたゾーンの数とともに増大する。
【００４９】
耐久性は、フラッシュメモリに伴う、フラッシュメモリの使用寿命を限定する他の１つの問題である。全てのプログラミング／消去サイクルで、いくらかのトンネリング電子がフローティングゲートとチャネル領域との間の誘電体に捉えられ、そのことがしきい値ウィンドウを狭くするという結果をもたらす。このことは結局、プログラミングエラーおよび読み出しエラーをもたらす。ＭＬＣメモリはエラーに関してより低い許容誤差を有するので、ＭＬＣメモリはＳＬＣメモリに比べてより低い耐久性も有する。
【００５０】
ＳＬＣ部分およびＭＬＣ部分に分割されたメモリ
図８は、本発明を実施するのに適する物理的メモリアーキテクチャの例を示す。メモリセルのアレイ２００（図１を参照）は第１の部分４１０および第２の部分４２０に分割される。第２の部分４２０は、各セルが複数ビットのデータを蓄積する高密度ストレージとして構成されたメモリセルを有する。第１の部分４１０は、各セルが第２の部分のビット数より少ない数のビットを蓄積する低密度ストレージとして構成されたメモリセルを有する。例えば、第１の部分４１０内のメモリセルは、各々１ビットのデータを蓄積するＳＬＣメモリとして構成される。第２の部分４２０内のメモリセルは、各々２ビットのデータを蓄積するＭＬＣメモリとして構成される。セルあたりに１ビットのデータを蓄積する第１の部分はＤ１とも称され、セルあたりに２ビットのデータを蓄積する第２の部分はＤ２と称される。前の議論の見地から、第１の部分は、第２の部分のものと比べてより高い速度、ずっと広いエラーマージンおよびより大きな耐久性で動作する。
Ｄ１（１ビット）およびＤ３（３ビット）部分などの２部分に分割されたメモリが、その全体が本願明細書において参照により援用されている、２００９年１２月１８日に出願された米国特許出願第１２／６４２，５８４号（特許文献１６）に開示されている。
【００５１】
図９は、２レイヤデータストレージシステムにおけるＳＬＣ部分およびＭＬＣ部分間のデータ経路を概略的に示す。第１のレイヤは、入来データのための主入力バッファであって、ＭＬＣ部分４２０と比べてより高速／より高い耐久性／より高いコストのメモリであるＮＡＮＤメモリのＳＬＣ部分４１０に作用する。第２のレイヤは、主データアーカイブストレージであって、より低速／より低い耐久性／より低コストのメモリであるＭＬＣ部分に作用する。
【００５２】
このようなシステムにおける主な操作が、図９において以下のように分類されている。
１．ＳＬＣ部分へのホストデータまたは制御データ書き込み
２．部分的使用済みＳＬＣブロックを回収するためのＳＬＣ部分の中でのデータコピー（別名「圧縮」）
３．ＭＬＣ部分へのホストデータ直接書き込み（普通は長いシーケンシャルな書き込みのために使用される）
４．ＳＬＣからＭＬＣ部分へのデータ移動（別名「折り畳み」）
５．ＭＬＣブロック回収のためのＭＬＣ部分の中でのデータコピー（別名「圧縮」）
前述した構造は、主として種々のアドレス指定方式およびアドレス指定可能なデータ単位のグラニュラリティの使用に関連する他の多くの追加のフィーチャを伴って構築され得る。
【００５３】
図１０は、図９に示されているＳＬＣレイヤをより詳しく示す。ＳＬＣレイヤの代表的な構造（前述した図表を参照）は、複数のブロック、普通は１つの書き込み／アップデートブロックとブロック回収中にコピーされるデータのための１つの再配置／圧縮ブロックと（あるいはこれらを結合してもよい）を使用する。以下の主要ルールが普通適用される。
１．ブロックは、ブロックがプログラムされた順に従ってチェーン内でリンクされる。
２．もっとも古くにプログラムされたブロックがＳＬＣ移動／折り畳みブロックとして選択され、ブロックからデータがＭＬＣ書き込みブロックへ移動／折り畳まれ得る。
３．最少量の有効データを有するブロックがＳＬＣ回収ブロックとして選択され、ブロックから有効データが、チェーンの頭に結合するＳＬＣ再配置ブロックへ再配置される。
４．データ移動／折り畳みまたはブロック回収の操作が完了すると同時にＳＬＣ移動ブロックまたはＳＬＣ再配置ブロックがＳＬＣ空ブロックリストに加えられる。
【００５４】
これに加えて、２レイヤ構造は、実際には、例えばＲＡＭ、あるいは第３のタイプのＮＶＭなどのより多くのタイプのメモリがある場合には、３つ以上のレイヤであり得る。
さらに、各「メモリ」レイヤには、同じく「レイヤ」と称される異なるデータ処理を伴う複数のサブシステムが存在し得る。
ＮＡＮＤメモリに基づく従来技術のシステムは普通、次のストレージハイアラーキを有する。ＳＬＣパーティションは、バイナリキャッシュおよびバイナリアップデートブロックを実現するためのＳＬＣブロックを有する。
【００５５】
バイナリキャッシュは一部あるいは全てのデータのために使用される。データは、１または８（４ＫＢ）セクタの細かいグラニュラリティでバイナリキャッシュに蓄積される。通例、バイナリキャッシュは、ページの小さくてランダムなフラグメントをキャッシュするために使用される。フラグメントはその後バイナリアップデートブロックへ追い立てられる。
バイナリアップデートブロックは、データのほとんどを論理グループの単位でマッピングする。各論理グループは、ＳＬＣブロックに対応するサイズを有する。それ故、１つのバイナリブロックは、ページが論理アドレスのシーケンシャルな順序でその中に存在する１つまでの論理グループを蓄積することができる。このレイヤがクラスタベースのシステムには存在しないのは、これらのシステムでは全てのバイナリブロックがバイナリキャッシュとして使用されるからである。
ＭＬＣパーティションは、ＳＬＣブロックより高い密度でデータを蓄積するためのＭＬＣブロックを有する。通例、データは１ＭＬＣブロックずつ蓄積される。従って、Ｄ１およびＤ３パーティションを有するメモリでは、３つのＳＬＣブロックが１つのＭＬＣブロックへ折り畳まれる（再配置される）。
【００５６】
バイナリキャッシュからＳＬＣアップデートブロックおよびＭＬＣブロックへのデータの追い立ては、最旧書き込み (Least-Recently-Written) ベースに基づく。データの大部分（例外は、バイナリキャッシュ内にあるときにアップデートされるデータである）が初めにＳＬＣブロックに行くのでＳＬＣブロックがほとんどＦＩＦＯバッファとして働くという、全てのシステムにおける問題である。その後、全てのデータがＭＬＣブロックへ行く。ＳＬＣ部分およびＭＬＣ部分の両方において、（完全アドレス指定単位を作る）パディングに起因して、あるいはブロックを圧縮して使用済み空間を回収するために、データは何回もコピーされ得る。ストレスファクタ（別名書き込み増幅 (Write Amplification)）は高くて、ＳＬＣブロックパーティションおよびＭＬＣブロックパーティションの両方に適用される。ＳＬＣ内のデータはＭＬＣにも割り当てられ（二重割り当て）、このことが、二重割り当て (double-budgeting) に起因してシステムにおけるブロックの所要数を増大させる。
【００５７】
一般に従来技術のシステムでは、主要なアプローチはより細かいグラニュラリティの単位を使用することであり、このことはハイエンドの処理と大きなＲＡＭ要件とを想定し、余分のコストおよび電力消費を付け加える。
さらに、４ＫＢなどの非常に小さい単位は、データが断片化されてブロック間に甚だしく散在させられるので読み出しおよびデータコピー（アップデートによる）時の最大並列性が達成できないという問題を生じさせる。さらに、小さなアップデートが１つまたは複数のブロック全体のコピーをトリガーすることがあるのでコピーの量が増大する。
【００５８】
動作に基づくメモリパーティションにおける選択的配布を伴う小論理グループを用いるブロック管理システム
小論理グループ
本発明は、前述した問題、特に書き込み増幅を増大させるＳＬＣブロックの望ましくないＦＩＦＯバッファ挙動、並列性を低下させるデータの断片化、大きなＲＡＭと大電力を必要とする大強度の処理、効率が悪くて不経済なＳＬＣブロックにおけるデータのための重複容量割り当てに対処するアーキテクチャを有する。
【００５９】
本発明の１つの態様に従って、ブロック管理システムを有する不揮発性メモリが提供され、ブロック管理システムにおいて、ホストからの順序付き論理アドレス範囲が複数の論理グループに分割され、ブロックはデータの複数の論理グループを蓄積する。各論理グループは、少なくともホスト書き込みのサイズと同じ桁から一桁上までの範囲を有するサイズのものであるが、少なくとも、メモリによりサポートされる最大並列性の読み出しまたは書き込みの単位であるページまたはメタページのサイズを有するものである。論理グループのサイズを消去ブロックのサイズから切り離し、ホスト書き込みのサイズおよび性質とよりコンパチブルなサイズとすることにより、論理グループは、性能に強い影響を及ぼす過度の書き換えをトリガーすることなくアドレス指定を簡素化するとともに限定されたシステムリソースを節約するという利益をもたらす。
【００６０】
より小さなサイズの論理グループの実現は、過度の書き換えをトリガーしないと同時により小さなアドレステーブルの使用を可能にするという利益を有する。このことは、アドレステーブルが高価な外部ＲＡＭを必要とすることなくコントローラチップ上に統合されているＲＡＭにキャッシュされるように十分にコンパクトなサイズであるという利益を有する。
【００６１】
図１１は、本発明に従うブロック管理システムのメモリ編成におけるページを示す。本質的に、ホストは、それらの論理アドレス（ＬＢＡ）により識別されるデータの単位を書き込む。メモリは、データの論理ページ６２に並行して作用する。ページ６２は数個のＬＢＡのためのデータを保持することができる。例えば、各ページはＭ単位のＬＢＡからのデータを保持し、ページ（Ｐａｇｅ（ＬＰ0 ））はＬＢＡ0 からＬＢＡM-1 までのデータで満たされ得る。メモリアーキテクチャに依存して、ページは、メモリプレーン内の読み出し／書き込み回路の対応するグループによりサービスされ得る少なくとも１グループのセル／データである。好ましい実施形態では、ページは、最大の並列性を達成するために図５に関連して記述したメタページである。例えば、メタページは３２〜６４ｋＢまでのサイズである。４ｋＢのホスト書き込みクラスタでは、メタページは８〜１６クラスタを保持し得る。
【００６２】
図１２は、ブロック管理システムにおける論理グループを示す。アドレス指定を簡素化するために、各ページ６２を独立にトラッキングする代わりに、１グループのページが１つの単位としてトラッキングされる。本質的に、ホストシステムの論理アドレス指定された空間は複数の論理グループ３５０に分割され、各グループはＬＢＡまたは論理ページ番号の１つの範囲により定められる論理アドレス空間のサブセットである。例えば、論理グループＬＧ０は論理ページ番号ＬＰ0 〜ＬＰN-1 を有するＮ個の論理ページから構成され、次の論理グループＬＧ１は論理ページ番号ＬＰN 〜ＮＰ2N-1を有するＮ個の論理ページから構成されるなどである。
【００６３】
論理グループ３５０は、その中のページが自己索引付けされるようにその論理ページ番号がシーケンシャルな順序となってメモリに蓄積される。このようにして、論理グループ内のページ６２のためのアドレス指定は、ページレベルの代わりに論理グループレベルで単に追跡することによる。しかし、論理グループ内のページがアップデートされるにつれて、無効なページにより占められる空間を回収するためにガーベッジコレクションが行われなければならなくなる。従来技術のシステムでは、論理グループは消去ブロックのサイズと並ぶサイズを有する。このようにして、消去ブロックに対するガーベッジコレクションは、単に論理グループの有効なデータを回収して論理グループ全体を１つの新しいブロックに書き換えることである。
【００６４】
図１３Ａは、複数の論理グループからのデータを収容した消去ブロックを示す。従来技術のシステムとは違って、論理グループ３５０のサイズは消去ブロックのサイズから切り離されていて、消去ブロックと同じサイズではない。論理グループ３５０は、ホスト書き込みのサイズおよび性質とよりコンパチブルとなるようにサイズが小さくされている。ＳＬＣ部分４１０内のブロック３１０（これは好ましくはメタブロックである）はｐ個の論理グループのためのデータを収容することができる。例えば、ＳＬＣブロックは次の論理グループ（ＬＧ０、ＬＧ１、ＬＧ２、ＬＧ１’・・・）などを蓄積し、ここでＬＧ１’はＬＧ１のアップデート済みバージョンである。
論理グループを使用することにより、アドレス指定は強さが減じて、メモリコントローラと協働する高価なオフチップＲＡＭを必要とせずにシステムリソースに対する需要を減少させる。
【００６５】
しかし、消去ブロックのサイズがどの世代のフラッシュメモリでも増大するので、論理グループをブロックと整列させる従来技術のアプローチは短くてランダムなホスト書き込みのために最適化されていないシステムをもたらす。このタイプのホスト書き込みパターンは、デスクトップコンピュータおよびラップトップコンピュータ並びにスマートモバイルデバイスの下のアプリケーションでは一般的である。頻繁なアップデートおよびシーケンシャルでない書き込みにより特徴づけられるこれらのデータパターンは、論理グループのシーケンシャルな順序を維持するためにメモリのより頻繁な書き換えを引き起こしがちである。換言すれば、従来の論理グループのサイズは、かなりの量の書き込み増幅を引き起こし、性能を低下させ、メモリを早く摩耗させる。
【００６６】
メモリはＳＬＣ部分４１０とＭＬＣ部分４２０とに分割されている。従って、各論理グループは、少なくともホスト書き込みの単位のサイズと同じ桁から一桁上までの範囲へサイズを低減されるけれども、少なくとも、メモリによりサポートされる最大並列性の読み出しまたは書き込みの単位であるメタページのサイズを有するものである。これは、頻繁にアップデートされるかあるいはシーケンシャルでないデータパターンのために最適化され、過度の書き換えをトリガーしない。例えば、論理グループは４メタページを有し得る。メタページが８〜１６ホストクラスタを保持するとすれば、論理グループは３２〜６４クラスタを保持し得る。同時に、論理グループのサイズは、コントローラチップが外部ＲＡＭと協働しなくてもよいようにアドレス指定リソースに対する要求を軽減する目的のためのトレードオフとして、公正に大きくされ得る。
【００６７】
図１３Ｂは、小さな論理グループによってホスト書き込みを不揮発性メモリに蓄積する方式を示す流れ図である。
ステップ５００：不揮発性メモリを１つの単位として消去可能なメモリセルのブロックに編成し、各ブロックは複数のページを蓄積するためのものであり、各ページはデータの所定数の論理単位に並行してアクセスするためのものであり、各論理単位はホストにより割り当てられた１つの論理アドレスを有する。
ステップ５１０：ホストの論理アドレス空間を順序付けられた論理アドレスの重なり合わないサブレンジに分割することにより複数の論理グループを定義し、各論理グループは少なくとも１ページの最小サイズと少なくとも２つの論理グループを１つのブロックにはめ込む最大サイズとにより定められる範囲の中の所定サイズを有する。
ステップ５２０：個々のホスト書き込みをバッファリングする。
ステップ５３０：その個々のホスト書き込みを１論理グループずつステージングする。
ステップ５４０：どのステージングされた論理グループをも不揮発性メモリに蓄積する。
ステップ５５０：終了
【００６８】
１つの好ましい実現形態では、メモリはＳＬＣ部分およびＭＬＣ部分に分割され、第１、第２および第３の操作および機能レイヤを含む。第１および第２のレイヤはＳＬＣ部分で動作する。第３のレイヤはＭＬＣ部分で動作する。第１のレイヤは、ホストからの書き込みデータを初めに蓄積し、各論理グループを第２のレイヤまたは第３のレイヤへ再配置する前にデータを１論理グループずつステージングするためのものである。第２のレイヤは、ホストデータを論理グループレベルで蓄積するためにＳＬＣブロックのプールにおけるアクティブな蓄積を提供する。プールが満杯であるときに、最少の潜在的書き換えを伴う論理グループを、より高い密度で蓄積する第３のレイヤへ追い立てることによって、より多くの空間が作られる。
このようにしてユーザデータのアクティブなセットがより高速のＳＬＣメモリにおいて優先的に維持され、ＳＬＣメモリで容量がなくなったときだけＭＬＣメモリで蓄積されるのにより適する選択された論理グループがＭＬＣメモリへ追い立てられる。
【００６９】
図１４は、本発明に従って異なるメモリパーティションでブロックおよびページを管理するためのシステムアーキテクチャを示す。メモリアレイ内のブロックおよびページはブロック管理システムにより管理され、ブロック管理システムはファームウェア６０としてメモリコントローラ１０２（図１を参照）に存在する。
【００７０】
メモリはＳＬＣ部分４１０およびＭＬＣ部分４２０に分割されている。ブロック管理システムは、第１のフラグメントキャッシュレイヤ４１２、第２の論理グループソーティングレイヤ４１４および第３のコールド論理グループアーカイブレイヤ４２２を実装する。これらは操作および機能レイヤである。始めの２つのレイヤ４１２および４１４はＳＬＣ部分４１０で動作し、第３のレイヤ４２１はＭＬＣ部分４２０で動作する。
【００７１】
第１のフラグメントキャッシュレイヤ４１２は、ＳＬＣ部分４１０のバイナリブロック３１０に作用し、初めにホストからのデータを蓄積して、各論理グループをＭＬＣ部分４２０へ再配置する前にメタページを１論理グループずつステージングするためのものである。ステージングは、データを集めて論理グループ全体とすることである。そのように集めることは、ホスト書き込みのフラグメントからのものであるか、あるいは不揮発性メモリに既に蓄積されている現存データとの結合でのパディングによることができる。ＳＬＣ部分４１０は２つの構造（常駐バイナリゾーン４０２およびバイナリキャッシュ４０４）を含む。バイナリキャッシュ４０４は主として細かいアドレス指定単位（セクタ）を伴う短いフラグメントのためのストレージであり、ここでデータをＳＬＣブロック３１０またはＭＬＣブロック３２０へ移動する／追い立てることができる。常駐バイナリゾーン４０２は、短いアップデートを伴う既知の頻繁にアップデートされるエリア、通例ＮＴＦＳまたは他のファイルシステムテーブルのデータだけのために取っておかれる。
【００７２】
第２の論理グループソーティングレイヤ４１４は、データをＳＬＣアップデート／蓄積ブロック３１０のプールに１論理グループずつ蓄積する。このプールへの書き込みは、ホスト書き込みあるいはガーベッジコレクションに起因する書き換えから生じる。ホストデータが主として短いフラグメントのものであるならば、ホストデータは、第１のレイヤから第２のレイヤ４１４へ追い立てられる前に初めに第１のレイヤ４１２でキャッシュされる。ホストデータがあまり断片化されていなくて（中間サイズ）完全な論理グループを得ることができる場合には、ホストデータは第２のレイヤ４１４へ直接書き込まれる。
【００７３】
本質的に、第２のレイヤ４１４は、断片化した中間サイズのホスト書き込みが到着する高速ＳＬＣストレージエリアを提供する。第２のレイヤがなくて、第１のレイヤ４１２がデータにアクセスすることができるより前にデータをＭＬＣ部分４２０内の第３のレイヤ４２２へ輸送するＦＩＦＯとして本質的に動作する従来システムとは違って、この第２のレイヤ４１４は高速ＳＬＣ部分４１０でユーザデータの作業セットを維持する。
従って、ＳＬＣアップデート／蓄積ブロックのプールが満たされてゆくときにユーザは高性能書き込みを経験する。プールが満杯であるときにだけシステムは空間を作るために幾つかの論理グループを第３のレイヤ（ＭＬＣ）へ移動させる。
【００７４】
ホット／コールド論理グループのソーティング
フラッシュ消去可能なブロックに編成された不揮発性メモリはデータの各単位に割り当てられている温度に従ってデータの単位をソートし、その場合、より高い温度は、データのその単位がガーベッジコレクション操作に起因して後に書き換えを受ける確率がより高いことを示す。データの単位は、ホスト書き込みあるいは再配置操作から生じる。データは、温度に依存して、ＳＬＣおよびＭＬＣなどの異なるストレージ部分あるいは異なる操作ストリームに蓄積されるべく、ソートされる。一般的に、温度ソーティング手法はＳＬＣ部分でもＭＬＣ部分でも動作可能である。このことは、書き換えを最小限にするために同様の温度のデータをその温度に適する仕方で処理することを可能にする。データの単位の例は論理グループおよびブロックを含む。
【００７５】
１つの好ましい実現形態では、メモリはＳＬＣ部分およびＭＬＣ部分に分割され、第１、第２および第３の操作および機能レイヤを含む。第１および第２のレイヤはＳＬＣ部分で動作する。第３のレイヤはＭＬＣ部分で動作する。第１のレイヤは、ホストからの書き込みデータを初めに蓄積して、各論理グループを第２のレイヤまたは第３のレイヤに再配置する前にデータを１論理グループずつステージングするためのものである。第２のレイヤは、ホストデータを論理グループレベルで蓄積するためのＳＬＣブロックのプールにおけるアクティブな蓄積を提供する。プールが満杯になると、最少の潜在的書き換えを伴う論理グループをより高い密度で蓄積する第３のレイヤへ追い立てることによって、より多くの空間が作られる。
【００７６】
第２のレイヤ内の各論理グループは、それがガーベッジコレクションに起因して将来書き換えさせられる可能性により順位付けされる。有限の範囲からの温度が各論理グループに割り当てられ、最もコールドな論理グループは最初に第３のレイヤへ追い立てられる。順位付け基準は、論理グループが経験しているアップデートの率と、アップデートとアップデートとの間に論理グループが存続する時間の長さとを含む。第２のメモリレイヤから第３のメモリレイヤへ再配置された論理グループは第３のメモリレイヤにおいてアクセスされる。第２のメモリレイヤにとどまっている論理グループは第２のメモリレイヤで直接アクセスされる。
【００７７】
図１５は、図１４に示されている第２のレイヤをより詳しく示す。論理グループを蓄積するためにバイナリブロック３１０のプールが設けられる。各ブロック３１０が満たされてその中の論理グループのうちの幾つかがアップデートされるとき、ブロックはガーベッジコレクションされなければならない。ブロック内の有効な論理グループは１つの新しいブロックへ再配置される。プール内の論理グループは、その「温度」に従ってソートされる。
【００７８】
第３のレイヤ４２２へ移動させられるべき論理グループは、論理グループの「温度」に従って選択される。第２のレイヤ４１４は、論理グループを論理グループがどれだけ書き換えを必要としそうかにより順位付けしソートするための便宜をも提供する。論理グループは、頻繁にアップデートされていて短くてランダムなホスト書き込みから生じたデータを論理グループが包含するとき、論理グループがより多くのガーベッジコレクションに起因してより多くの書き換えを必要とするであろうから、「ホット」であると考えられる。逆に、論理グループは、稀にしかアップデートされなくて長いシーケンシャルなホスト書き込みであるデータを論理グループが包含するときに、論理グループが書き換えをほとんどあるいはまったく必要とせずに割合に変化がないままであるので、「コールド」であると考えられる。１つの「温度」順位付け基準は、論理グループが経験しつつあるアップデートの率である。
【００７９】
従って、第２のレイヤ４１４内のＳＬＣブロックプールが満杯になると、最もコールドな温度を有する論理グループが優先的に第３のレイヤ４２２内のＭＬＣプールへ追い立てられる。
第２のレイヤ４１４から第３のレイヤ４２２へ再配置された論理グループは第３のレイヤ４２２においてアクセスされる。第２のレイヤ４１４にとどまっている論理グループは、第２のレイヤ４１４でアクセスされ続ける。
【００８０】
アクティブにアップデートされる論理グループとあまりアクティブにはアップデートされない論理グループとのソーティングおよび識別は、第１のレイヤ４１２および第２のレイヤ４１４がＳＬＣメモリ部分４１０で動作し、第３のレイヤ４２２がＭＬＣ部分４２０で動作するときには、重要である。アクティブな論理グループをＳＬＣメモリで作業セットとして維持してアクティブでない論理グループをＭＬＣメモリへ移動させることにより、論理グループへのアップデートがあるときの論理グループの書き換えはＭＬＣメモリにおいて最少化される。このことは、論理グループが受ける書き換えの総数を最少化する。
【００８１】
第３のレイヤ４２２は、第２のレイヤから追い立てられた最もコールドな論理グループをより高い密度（ＭＬＣ）で蓄積する。このプロセスは、ＳＬＣデータをＭＬＣデータへ「折り畳むこと」とも称される。
ホットな論理グループとコールドな論理グループとをソートしてよりホットな論理グループを第２のレイヤにとどめておくことは、ユーザがより高速でより耐久性のあるＳＬＣメモリにおいてこれらの潜在的に性能に影響されるデータにアクセスすることを可能にする。
ソーティング方式は論理グループのレベルでのソーティングに関して記述されているけれども、本発明はフラグメントレベルでのソーティングあるいはブロックレベルでのソーティングなど、他のデータ単位のレベルでのソーティングにも等しく適用可能である。
【００８２】
従来技術のシステムによれば、バイナリキャッシュからＳＬＣアップデートブロックへ、およびＭＬＣブロックへのデータの追い立ては、ブロックレベルに適用される最旧書き込みベースに基づく。ことのことは、データがどれだけ前にホストによってプログラムされたかという事実にかかわらず（ブロックは圧縮に起因して最近にプログラムされたけれども古くてコールドなデータを包含しているということがあり得る）、追い立てが実際には最旧プログラム済みブロックに基づくということを意味する。
さらに、追い立てはしばしば操作効率基準に基づき（特にバイナリキャッシュにおいて）、個々の操作の増大する効果に焦点を当て、例えば論理グループ追い立ては大概の空の空間を生じさせる。
【００８３】
前述した全ての場合における問題は、ホストアップデートパターン、例えばアップデートの頻度や、どれだけ前にデータが書き込まれたかということさえも、考慮しないことである。結果として、すぐにアクセスされそうなデータがアーカイブされることがある。
米国特許第７，６３３，７９９号（特許文献１７）には、ＬＲＵ、書き込みおよび読み出しコマンドによるヒット率などの種々のデータアクセスパターン基準の使用が開示されている。しかし、従来技術は、例えば選択を効率的にし、同時に過度の処理を回避すること、ＲＡＭおよび制御アップデート要件などのデータストレージシステムで機能させる具体的で実際的な方法を教示していない。
【００８４】
本発明におけるアプローチは、書き込み増幅を最小にしようとすることである。書き込み増幅は、システム内のどこかでの将来の書き込みにより引き起こされる。書き込み増幅は、アクティブ（ホット）なデータと非アクティブ（コールド）なデータとが１つの物理的ブロック内に混在しているというコロケーション (co-location)により引き起こされる。ホットなデータとコールドなデータとがブロック内に混在していると、そのブロック内のデータを結局他のブロックへ再配置するかあるいは書き換えしなければならなくなる。ブロックが大きくなるにつれて、アクティブな領域と非アクティブな領域とを近接させて保つことはますます挑戦的なものとなる。
本発明は、ストレージの次のレイヤへ追い立てる／アーカイブするのに最も良いデータを検出するようにデータをソートする実際的な方法のコレクションを提供する。この方法は主として既知の原理を使用し、具体的にはアクセスパターンおよび履歴を分析することに基づいて行う。焦点は、データのソーティングを実際的にすることである。
【００８５】
主な方法は、以下を含む。
１．個々のフラグメントに「温度」値を割り当てることによってアドレス指定可能なデータ単位（論理グループ）の相対的アクティブさを順位付けする。温度値は、データ自体とともにあるいは別のテーブルに、またはアドレス指定エントリとともに、蓄積され得る。温度値自体は以下に基づくことができる。
ａ）データフラグメント／単位のための最旧書き込み（ホストによる）基準
ｂ）最新ヒット（アクセス、例えば読み出し）率
ｃ）データフラグメント長さ（データが短いほど、それだけデータはすぐにヒットされそうである）
ｄ）データの古さのインジケータとしてのデータのためのブロック圧縮コピーの数
ｅ）最善の結果をもたらすａ）およびｂ）およびｃ）の組み合わせ
２．温度値「低下」を提供する。例えば、長時間にわたって測定されると、ヒット率は下がり、そのことにより温度が低下することになる。このことは、有用な温度の有限な範囲を定義することを可能にするとともに方法の使用を実際的にする。温度は以下の方法によって下げられる。
ａ）温度の限定されたダイナミックレンジの中で作業する（例えば、３ビットの温度の場合には、０＝非常にコールド、７＝非常にホット）。極端にコールドな場合には０値を超えないように温度をバイアスさせ、極端にホットな場合には７を超えないように温度を飽和させる。換言すれば、あるポイント以後は全ての極端な場合が同じ値（０または７）を有する。
ｂ）値の過度の飽和および精度の喪失を避けるためにフラグメント／単位のための温度値の値を均す。換言すれば、最大有効度の領域の中で限定されたダイナミックレンジを使用する。
３．ブロックレベル温度基準を使用する。この基準では「温度」はフラグメントまたは論理グループのレベルではなくてブロックレベルでトラッキングされる。２つの主な場合は、
ａ）「温度」を明示的にトラッキングすることと、
ｂ）データ古さまたはホット／コールドの程度によってブロックリスト中のブロックをソートすることによる暗黙のトラッキングと、を含む。
【００８６】
一実施形態では、温度のソーティングは論理グループのレベルにある。最もコールドな論理グループは、第２のレイヤから第３のレイヤへ最初に追い立てられるものである。追い立てられるべき論理グループのための基準は、以下のものを含む。
１．タイムスタンプ（ＴＳ）。温度は、論理グループのタイムスタンプ値として決定される。タイムスタンプは、その論理グループが最後に書き込まれたのは何時であるかを示す。論理グループが最後に書き込まれてからの経過時間が長いほど、温度はよりコールドである。実際には限定されたＴＳ範囲を使用し、最大ＴＳ値を超える非常に古い論理グループは全て同じ最コールド温度を有すると見なされる。ＴＳの利点は、ＴＳがアクセスパターン変化に対して最速のレスポンスを有することである。欠点は、ＴＳは前歴を全く提供しないことである。
【００８７】
タイムスタンプを使用することの例は、第２のレイヤのバイナリブロックプール内の各論理グループのために１１ビットのタイムスタンプを使用することである。プールに論理グループが書き込まれるときに、１つのオプションは０という初期タイムスタンプ値を割り当てることである（バイアス＝０）。これは、書き込まれるデータが長いシーケンシャルなデータであるときには適切であり得る。他の１つのオプションは、Ｘという値を持つことである（バイアス＝Ｘ）。これは未知のタイプのデータのためには適切であり、Ｘはタイムスタンプ範囲の中央にセットされ得る。プールへの論理グループの書き込みがあるたびにその書き込まれる論理グループのタイムスタンプは初期値にセットされ、プール内に現存する論理グループのタイムスタンプは１インクリメントされる。論理グループのためのタイムスタンプは圧縮中には変化しない。このようにして、タイムスタンプは、プール内の論理グループの各々がどれほど前に書き込まれたかという相対的尺度を提供する。
【００８８】
２．基本的書き込みカウント。温度は、論理グループの書き込みカウントとして決定される。書き込みカウントは、論理グループが何回書き込まれたかあるいはアップデートの頻度を示す。例えば、論理グループの１つの新たなアップデートのときに書き込みカウントはインクリメントされる。書き込みカウントの利点は、書き込みカウントが履歴情報を維持することである。欠点は、書き込みカウントが古いホットな論理グループを「粘着性 (sticky) 」にし得ることである。
【００８９】
３．タイムスタンプおよび書き込みカウントの関数としての温度。初期温度値Ｘは、論理グループが最初に書き込まれるときに０および最大値の間にある。この値は論理グループが再び書き込まれると（書き込みカウントの場合と同じく）インクリメントされるので、方法は最近により多くの回数書き込まれた論理グループにバイアスを加える。値は、全ての論理グループについての平均値が１高まるときにデクリメントされる（タイムスタンプのおおよそのＭＳＢとして）。
【００９０】
タイムスタンプおよび書き込みカウントの関数としての３ビット温度の割り当ての例は以下の通りである。
論理グループが書き込まれるとき、論理グループは０と最大値７との間の温度Ｘを有する。論理グループが再び書き込まれると、（書き込みカウントの場合と同じく）温度は１インクリメントされる。温度は以下の状況下でデクリメントされる。
１．頂部で飽和することがあることから、全論理グループについての平均温度が１高まるとき（このことは集団を均すのに役立つ）
２．追い立てるべき論理グループＬＧＴ＝０が十分に存在しないとき
３．平均値がしきい値（例えば、最大値／２）より高まるとき
４．０のものと最大値のものとの比を均すため
【００９１】
論理グループがホストによってアップデートされてバイナリキャッシュまたはアップデートブロックのうちの１つ（同じアップデートブロック内の先に書き込まれていた論理グループの完成時に）に書き込まれるたびに、論理グループに次のＬＧＴ値が割り当てられる。
−シーケンシャルなストリームに書き込まれるどの論理グループも０の最低ＬＧＴ値を割り当てられる。
−アドレスジャンプなしでの短い書き込みによるシーケンシャルな連続的書き込みを除いて、論理グループが（マスターインデックスによりアドレス指定される）アクティブバイナリセット内にあるならば、ＬＧＴ値は１インクリメントされるか、またはどれが最高であっても、最高コールドＬＧＴ＝３にセットされる。ＬＧＴ値は、７の最高コールド値を超えることができない。
−論理グループがアクティブなバイナリセット内に存在しない場合（マスターインデックスによってアドレス指定されない場合）には、最高コールドＬＧＴ＝３の初期ＬＧＴ値が割り当てられる。
【００９２】
論理グループが再配置ブロックのうちの１つに書き込まれるときに、論理グループに最低コールド＝０のデフォルトＬＧＴ値が割り当てられる。
論理グループがバイナリキャッシュから再配置ブロックのうちの１つへ追い立てられるときに、論理グループに最高コールド＝３のＬＧＴ値が割り当てられる。
ＬＧＴ＝０を有する論理グループだけがＭＬＣブロックへ追い立てられ折り畳まれることができる。折り畳まれるべき論理グループが十分になければ、全てのＬＧＴがデクリメントされるべきである。
【００９３】
図１６は、「ホットな」論理グループの場合についての論理グループの「温度」ソーティングを示す。ＬＧ温度はアップデート頻度と古さとの複合関数である。アクティブバイナリ作業セット（ＡＢＷＳ）は、第２のレイヤ内のＳＬＣブロックのプールである。アクティブバイナリ作業セットはホット論理グループおよびブロックの短いリストを表し、そこでＬＧＴ（論理グループ温度）値が追跡される。
【００９４】
ソーティングは、論理グループについてのＬＧＴ（論理グループ温度）値に基づいて行われる。ＬＧＴ値は、アクティブなバイナリセットを作る、マスターインデックスにより現在アドレス指定される限定された数の論理グループのために蓄積される。マスターインデックスは、第２のレイヤのＳＬＣプール内の全ての論理グループをリストするテーブルである。各ＬＧＴは３ビットのサイズであって、０（最もコールド）〜７（最もホット）までの範囲を有する。
【００９５】
全ストリーム中の全論理グループがソーティングを受けるけれども、アクティブバイナリセット（マスターインデックスにより現在アドレス指定されるもの）内のバイナリブロック（アップデートブロック、再配置ブロック、あるいは閉鎖ブロックに蓄積されている）に書き込まれた論理グループだけが所与の時にソートされ、ＬＧＴ値はマスターインデックスに蓄積される。
ＧＡＴを介してアドレス指定される論理グループ（非アクティブバイナリセット内のバイナリブロックおよびＭＬＣブロック）は、等しく「非常にコールド」と見なされ、デフォルトで０の最低ＬＧＴ値を有すると見なされる。ＧＡＴは、論理グループとブロックとの間のマッピングを追跡するルックアップテーブルである。
【００９６】
最初は、ＭＬＣブロック内に存在する所与の論理グループがアップデートされる。従って、この論理グループについての温度はゼロから高まる。この論理グループが近い将来にどのくらいアクティブになるかは不明であるから、論理グループには中間値温度が割り当てられ、ＬＧＴ＝３である。分かる通り、論理グループはすぐにもう５回アップデートされる。各アップデートヒットで、温度ＬＧＴは１インクリメントされ、インクリメントは温度をＬＧＴ＝７の最大値へ至らせる。その後、論理グループに対するそれ以上のアップデートはなかったので、ＬＧＴはＬＧＴ＝７のままである。このポイントで、バイナリプールが満杯であることが分かってＬＧＴ＝０を有する論理グループのセットがＭＬＣレイヤへ追い立てられる（折り畳まれる）。その論理グループのセットの出発はプールの平均温度を高め、従ってＳＬＣプールに残っている全論理グループの温度は１デクリメントされ、所与の論理グループは今やＬＧＴ＝６を有する。所与の論理グループに対するアップデートがない時間がしばらく続いたのちに、もう１つの折り畳みが生じ、そのことは所与の論理グループのＬＧＴを５へデクリメントする。このポイントで、所与の論理グループは高い温度を有し、ＳＬＣプール内に「住み」続ける。
【００９７】
図１７は、「コールド」論理グループの場合について論理グループの「温度」ソーティングを示す。この場合、第３のＭＬＣレイヤに存在する論理グループがアップデートされて第２のＳＬＣレイヤ内のバイナリプールへ戻される。それ以上のアップデートがないままバイナリプールに位置した後、温度は下がってＬＧＴ＝０に戻る。プールが満杯で幾つかの論理グループを追い立てる必要があるときには、所与の論理グループは第３のＭＬＣレイヤへ折り畳まれて戻される。
【００９８】
他の１つの実施形態では、ソーティングはブロックレベルで行われ得る。これは、その温度を個別に追跡するべき論理グループがプール内にあまりに多くある場合には、１つの代わりのアプローチである。代わりに、温度はブロックレベルで追跡され、ブロック内の全論理グループは、あたかも全グループが同じ温度を持っているかのごとくに扱われる。この場合、ソーティングオプションには以下のものが含まれる。
【００９９】
１．同じバイナリブロック内の論理グループについて同じタイムスタンプ（明示的なブロックレベルＴＳ）−模するべき
−各バイナリブロックがブロックのために書き込まれた全論理グループについて同じＴＳを有する。
−ホットデータおよびコールドデータをブロック単位でソートする。
−ＴＳ＝現在のブロックＴＳ。現在のブロックＴＳは、各々の新しいデータアップデートブロック閉鎖の後にインクリメントする。
−圧縮中、ＴＳはソースブロック内のＴＳに基づいて近似される。
−例えば、タイムスタンプＴＳは８ビットである（圧縮されたＴＳ＝第１の圧縮ソースの最大ＴＳ）か、あるいは６ビットであり得る（圧縮ブロックのために平均ＴＳを追跡する）
−コールドデータをバイアスさせることができる（ＴＳ＝現在のＴＳ−バイアス）が、底においてではなく、オプションはバイアス＝０またはバイアス＝Ｘである。
【０１００】
２．ホット−コールドデータのバイナリブロックソーティング（ブロックレベルＴＳの暗黙の実装）−模する必要なし
−各バイナリブロックは新データアップデートブロックのために時間割り付け順でＵＢ情報においてリストされる。ブロックのために書き込まれた全論理グループについてＴＳが同じであることと同等である。
−圧縮中、リストにおける新しいブロックの位置はおおよそソースブロック位置に従って選択される。換言すれば、新しいブロックはソースブロックとおおよそ同じ温度を有する。
−圧縮中、ＴＳはソースブロック内のＴＳに基づいて近似される。
−リストの末尾にあるブロックからの論理グループが追い立てられる。
−利点は、余分のレコード、オーバーフロー、インクリメントなどを持たないことである。さらに、単一のテーブルレコードがなくて、まったくアップデートできない複数のＢＣＩ（バイナリキャッシュインデックス）があるバイナリキャッシュのためには非常によい。欠点は、ブロックレコードを再ソートするためにデータコピーを必要とすることである。
【０１０１】
前述した原理は、不揮発性であるかあるいは混合であり得るデータストレージの２以上のレイヤを有するシステムに適用される。同じ規則が、バイナリキャッシュサブシステムまたはアップデートブロックなどの、レイヤのうちの１つにおける特定タイプのストレージに適用され得る。
この解決策の利点は、システム性能影響が最小化され、コントローラＲＡＭ空間の増大がないことである。
【０１０２】
ＬＧＴによりホット／コールドデータを分けるためのブロックストリーム
他の１つの実施形態では、データの単位は、各操作ストリーム内のブロックが同様の温度のデータを包含するだけであるようにデータの単位の温度に応じて異なるブロックストリームにソートされる。目標は、なるべく直ぐにかつあらゆる機会をとらえて、ホットデータをコールドデータから分離することである。ホットデータとコールドデータとは異なる使用済み度およびガーベッジコレクション／再配置スケジュールを有する。例えば、ホットデータはより速く使用済みとなり、より頻繁なガーベッジコレクション／書き換えを必要とする。コールドデータがホットデータと混ぜ合わされなければ、コールドデータは不必要な書き換えを被らない。おそらく、ホットデータは１つのブロックから他のブロックへのコールドデータの再配置をトリガーすることなく使用済みとなり、コールドブロック内のコールドデータはホットデータに起因する圧縮／再配置なしでコールドブロック内に留まる。
一例は、第２のレイヤ内のバイナリブロックのプールに入るホスト書き込みがなるべく早く異なるブロックストリームにソートされることである。他の１つの例は、再配置操作から生じるデータ単位である。
【０１０３】
図１８は、いろいろなタイプの書き込みがどのようにしてそれらの知覚される温度に応じてインタラクティブにブロックストリームにソートされるかを示す。ソーティングは入来データに関して第２のレイヤでソースに適用されるとともに、圧縮によって別々のホット／コールドブロックへ移動させられるデータに適用される。
一般に、メモリパーティション内には、示されているように種々のソースにより生成された種々のタイプのデータストリームが存在し得る。その種々のタイプのデータストリームの各々の中のデータ書き込みは、前述した温度によりソートされ得るそれ自身のアップデート頻度およびランダムさを有する。
【０１０４】
バイナリブロックプールにおいて、ブロックは、ＬＧＴ＞３の論理グループを蓄積するための「ホット」ブロックあるいはＬＧＴ＝＜３の「コールド」ブロックと称される。温度は、書き込みパターンを観察した後にその場で決定される。例えば、論理グループがバイナリブロックプールに初めて書き込まれるとき、論理グループの温度は不明であるのでＬＧＴ＝３（前の３ビット例として、０および７の間）の中間温度を割り当てられる。論理グループはクールと称されるブロックに書き込まれる。次の書き込みが論理グループのアップデートである場合には、ストリームはホットであると見なされ、アップデートされた論理グループはホットな論理グループを蓄積するための異なるバイナリブロックに書き込まれる。
一方、連続する書き込みがシーケンシャルであるならば、ストリームはコールドと見なされ、連続する論理グループは全て、第１の書き込みを包含するコールドバイナリブロックに書き込まれる。
【０１０５】
連続する書き込みがシーケンシャルであって、そのトレンドが所定期間にわたって続いたならば、ストリームは一連の長いシーケンシャルな書き込みと見なされて、直接またはバイナリブロックプールを介してＭＬＣ部分へ折り畳まれるべく管理される。その直接の場合には、ストリームは、識別されるとすぐにバイパスモードになる。コールドブロックあるいはホットブロックの中でさえ孤立しているシーケンシャルなストリームの先頭は結局再配置される。
前述した種々のデータストリームはユーザにより作られ得るので、ユーザ論理パーティションから生じ得る。パーティション内の書き込みストリームのうちの幾つかは再配置操作からも作られることがある。
【０１０６】
パーティション
一般に、ユーザパーティション、ＯＳ（オペレーティングシステム）パーティションおよび「粘着性の」バイナリパーティションなどの種々の論理パーティションが、それぞれ異なるタイプのデータストリームのそのもの自身の混合物を伴って、或るものは所定の温度を伴って、維持され得る。例えば、ＯＳパーティションでは、システムデータは断片化していて急速に変化すると分かっているので、温度を決定する必要さえない。ＯＳパーティションは単にホットな温度を割り当てられてホットブロックに蓄積される。その中にあるデータがバイナリＳＬＣ部分に留まるように予定されている「粘着性の」パーティションにも同じことが当てはまる。従って、「粘着性の」パーティションのデータストリームは常に「ホット」であって、ホットブロックに蓄積される。
【０１０７】
ＬＢＡによってデータをパーティションに分ける。ブロックは異なるパーティションからのデータを持たないことを意味する。仮定は、異なるパーティション内のデータは異なるアプリケーション（例えば、１つにおけるＯＳ、そして他の１つにおけるユーザ）により書き込まれるということであり、これらの書き込みはしばしばインターリーブしない。例えばＯＳが多くのコマンドを書き込むことができるとすれば、ユーザは多くを書き込むけれども、大量のインターリーブはない。種々のパーティションからの書き込みを異なるブロックへ分けることにより、例えばＯＳ書き込みによりトリガーされるユーザデータの圧縮／再配置およびその逆が低減される。
【０１０８】
ブロックおよび論理グループは、パーティション境界なしでのＬＧＴによるソーティングを受ける。このことは、パーティションあたりに幾つかの閉じたブロックを割り当てる必要はなくてブロックが要求に応じて分配されることを意味する。例えば、ＯＳパーティションがアクティブであってユーザパーティションがアクティブでないとすれば、全てのユーザパーティションの論理グループがコールド状態にソートされてＭＬＣ部分へ折り畳まれるので、閉じられているアップデートブロックが最大で全てＯＳパーティションに割り当てられ得る。
【０１０９】
ストリームあたり複数のアップデートブロックのためのサポート
ストリームからの書き込みは複数のブロックに蓄積され得る。第１の論理グループが第１のブロックに部分的に書き込まれて、次に別の、第２の論理グループの書き込みが続くたびに、その第２の論理グループは、後続の書き込みが第１の論理グループを完成させる不完全なデータを供給するだろうという期待のもとに第２のブロックに書き込まれる。このことは断片化を減少させる。所定数までのアップデートブロックがこの目的のために同時に開かれ得る。それを超えると、不完全な論理グループは不完全なデータをパディングすることによって完成させられる。
【０１１０】
図１９は、メモリストレージおよび操作のための温度ソーティングの方式を示す流れ図である。
ステップ６００：不揮発性メモリを一緒に消去可能なメモリセルのブロックに編成する。
ステップ６１０：温度を割り当てることによってデータの各単位を順位付けし、より高い温度は、そのデータ単位がガーベッジコレクション操作に起因して後に書き換えを受ける確率がより高いことを示す。
ステップ６２０：データ単位の温度に依存する仕方でデータ単位に対する操作を行う。
ステップ６３０：終了
【０１１１】
図２０は、論理グループレベルでの温度ソーティングの方式を示す流れ図である。
ステップ７００：不揮発性メモリを一緒に消去可能なメモリセルのブロックに編成する。
ステップ７１０：不揮発性メモリをＳＬＣ部分およびＭＬＣ部分に分割し、ＳＬＣ部分内のメモリセルは各々１ビットのデータを蓄積し、ＭＬＣ部分内のメモリセルは各々１ビットより多いデータを蓄積する。
ステップ７２０：ホストの論理アドレス空間を順序付けられた論理アドレスの重なり合わないサブレンジに分割することにより複数の論理グループを設け、論理グループは複数の論理グループが１つのブロックにはまり込むサイズを有する。
ステップ７３０：ＳＬＣ部分の各ブロックにデータを１論理グループずつ蓄積する。
ステップ７４０：ＳＬＣ部分に蓄積されている各論理グループを温度により順位付けし、より高い温度は、その論理グループがガーベッジコレクション操作に起因して後に書き換えを受ける確率がより高いことを示す。
ステップ７５０：ＳＬＣ部分の空間を解放する要求に応答して、最もコールドな温度の論理グループをＳＬＣ部分からＭＬＣ部分へ優先的に再配置する。
ステップ７６０：終了。
【０１１２】
図２１は、ブロックレベルでの温度ソーティングの方式を示す流れ図である。
ステップ８００：不揮発性メモリを一緒に消去可能なメモリセルのブロックに編成する。
ステップ８１０：不揮発性メモリをＳＬＣ部分およびＭＬＣ部分に分割し、ＳＬＣ部分のメモリセルは各々１ビットのデータを蓄積し、ＭＬＣ部分のメモリセルは各々１ビットより多いデータを蓄積する。
ステップ８２０：ＳＬＣ部分の各ブロックを温度により順位付けし、より高い温度は、そのブロックがガーベッジコレクション操作に起因して後に書き換えを受ける確率がより高いことを示す。
ステップ８３０：ＳＬＣ部分の空間を解放する要求に応答して、最もコールドな温度のブロック内のデータをＳＬＣ部分からＭＬＣ部分へ優先的に再配置する。
ステップ８４０：終了。
【０１１３】
本発明の種々の態様を或る実施形態に関して記述してきたけれども、本発明が添付されている特許請求の範囲の全範囲内での保護に値することが分かる。
【図１】
2014513850.tif 000003
【図２】
2014513850.tif 000004
【図３】
2014513850.tif 000005
【図４】
2014513850.tif 000006
【図５】
2014513850.tif 000007
【図６】
2014513850.tif 000008
【図７】
2014513850.tif 000009
【図８】
2014513850.tif 000010
【図９】
2014513850.tif 000011
【図１０】
2014513850.tif 000012
【図１１】
2014513850.tif 000013
【図１２】
2014513850.tif 000014
【図１３Ａ】
2014513850.tif 000015
【図１３Ｂ】
2014513850.tif 000016
【図１４】
2014513850.tif 000017
【図１５】
2014513850.tif 000018
【図１６】
2014513850.tif 000019
【図１７】
2014513850.tif 000020
【図１８−１】
2014513850.tif 000021
【図１８−２】
2014513850.tif 000022
【図１９】
2014513850.tif 000023
【図２０】
2014513850.tif 000024
【図２１】
2014513850.tif 000025
【国際調査報告】
2014513850.tif 000026
2014513850.tif 000027
2014513850.tif 000028