(57)【要約】【課題】各論理セクタアドレス値用のデータブロックおよび複数の予備データブロックを使用して、論理セクタアドレスと対応する物理アドレスとの間のマッピングを維持する方法を提供すること。【解決手段】各論理セクタアドレス値用のデータブロックおよび複数の予備データブロックを使用して、論理セクタアドレスと対応する物理アドレスとの間のマッピングを維持する方法。各データブロックは、直接アドレスフィールドおよび間接アドレスフィールドを含む。論理セクタアドレスにデータが最初に書き込まれたときに、直接アドレスフィールドは、対応する物理アドレスでプログラムされる。その後、同じ論理セクタアドレスにデータが書き込まれるたびに、間接アドレスフィールドが予備データブロックのアドレスでプログラムされ、予備データブロックの直接アドレスフィールドがそのデータの新しい物理アドレスでプログラムされる。【選択図】図１Ａ
2006294061.tif 000002
【特許請求の範囲】
【請求項１】
ホストシステムとともに用いられるデータ記憶システムであって、
該データ記憶システムは、
複数の消去可能なソリッドステートデータ記憶手段（２０）であって、該複数の消去可能なソリッドステートデータ記憶手段の各々は、一意的な物理アドレスによって位置を特定することができ、かつ、一度書き込まれると、再書き込みされる前に消去されなければならない、複数の消去可能なソリッドステートデータ記憶手段（２０）と、
該ホストから受け取られた複数の論理アドレスを該複数の消去可能なソリッドステートデータ記憶手段の対応する複数の物理アドレスにマッピングするルックアップテーブルを記憶する不揮発性のブロック消去可能な記憶手段を含む制御手段（１２、２２）と
を備え、
該制御手段の記憶手段は、複数のデータブロックを含み、該複数の論理アドレスの各々に対してそれぞれのデータブロックが存在し、
該制御手段は、複数の予備データブロックをさらに含み、
各データブロックと各予備データブロックは、直接アドレスフィールド（１４）と間接アドレスフィールド（１６）とを含み、
該制御手段は、
該データ記憶手段に書き込まれるためのデータとともに論理アドレスが該ホストから供給される場合には、該論理アドレスに対応する物理アドレスを用いて該記憶手段の各データブロックの直接アドレスフィールドをプログラムする手段と、
新しいデータが同一の論理アドレスに書き込まれる場合には、使用されていない予備データブロックのアドレスを用いて各データブロックの間接アドレスフィールドをプログラムし、かつ、該同一の論理アドレスに対応する新しい物理アドレスを用いて該予備データブロックの該直接アドレスフィールドをプログラムする手段と
をさらに含む、データ記憶システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ記憶システムに関し、具体的には、書き込まれていない記憶場所にだけデータを書き込むことができ、これによって、記憶されたデータを変更するたびにブロック全体を消去することをしなくてもメモリに記憶された情報を更新することができるメモリ管理方法に関する。本発明の一適用例は、データの主記憶装置にフラッシュメモリを使用し、論理アドレスから物理アドレスへの変換にフラッシュルックアップテーブルを使用するソリッドステートメモリにある。本発明は、フラッシュＥＰＲＯＭセル、カルコゲニドメモリセルおよびフェロオプティックセルなどのいくつかの異なるメモリセルとともに使用することができる。ソリッドステートディスクは、それらを使用しているホストから論理セクタアドレスの形態で（または、ホストからのシリンダ−ヘッド−セクタアドレス指定の変換によって）アドレスを受け取る。この論理セクタアドレス指定は連続的である。論理セクタアドレスは物理セクタアドレスにマップされる。物理セクタアドレスは、物理メモリ内のセクタの順序を定義する。論理セクタは、任意の順序で物理セクタに割り当てることができるため、この変換を、アルゴリズムによって実行することはできず、ある形態のマッピングが必要となる。このマッピングは通常、ルックアップテーブルによって実行される。しかし、ルックアップテーブルも同様にフラッシュメモリセルから構成される場合には、個々のエントリは、ブロック消去によってしか更新することができない。これは非常に能率が悪い。
【背景技術】
【０００２】
近年、ソリッドステートディスク装置の分野に急に活発な動きがある。ラップトップおよびパームトップポータブルコンピュータ、ならびにＰＣＭＣＩＡ規格の出現でこの動きは強まった。フラッシュメモリをメインのデータ記憶装置として使用する際に必要な制御方法に関するいくつかの特許が出願されている。
【０００３】
ＷＯ９４２０９０６はフラッシュファイルシステムに関する。このシステムは、メインフラッシュメモリの書込み可能なブロックに関する情報を記憶するブロック割当てマップを使用する。ブロックを更新するときには、使用していないブロックが見つかるまで割当てマップがスキャンされる。システムのメモリ再生を容易にするために転送ユニットが使用される。転送ユニットは、書き込まれていない消去済みメモリブロックである。古いデータ（古いブロック）を含むメモリブロックのアクティブデータ（現在有効なデータ）は、転送ユニットの同じ記憶場所（新しいブロック）に書き込まれ、古いブロックは消去される。次いで、この古いブロックが転送ユニットになる。ＷＯ９４２０９０６に開示された発明は、ブロック割当てマップの変更を反映させるために、ランダムアクセスメモリを必要とする。本発明は、ランダムアクセスメモリを必要とせず、データ更新の管理に必要な全ての機能を、フラッシュＥＰＲＯＭなどのブロック消去可能な不揮発性メモリ上で実行することができる。
【０００４】
ＥＰ０５９７７０６は、ホストが与えた論理セクタアドレスを半導体メモリの物理アドレスにマップするマップＲＯＭを使用するソリッドステート周辺記憶装置を開示している。半導体メモリの全ての不良セクタのアドレスがマップＲＯＭに記録される。このマッピングを制御するためにマイクロシーケンサが使用される。新しい物理アドレスが必要となったときにマップＲＯＭは更新される。この発明は、フローティングゲートメモリに関する。この特許出願に記載されたマップＲＯＭ更新方法によると、各エントリが独立に更新できるようにマップＲＯＭはバイト単位で消去可能でなければならないので、フラッシュメモリをマップＲＯＭにすることができない。
【０００５】
ＷＯ９５１００８３は、ＣＡＭ（ｃｏｎｔｅｎｔ  ａｄｄｒｅｓｓａｂｌｅ  ｍｅｍｏｒｙ）を使用してフラグフィールドを含むアドレスを探索することを開示している。フラグが特定の値に設定されているアドレスのみが一致するとして探し出されるような方法でアドレスは探索される。アドレスが、古くなったデータを記憶しているときにはそのアドレスのフラグはリセットされる。したがって、有効データを含むアドレスのフラグだけがセットされ、古いデータを含む同じ論理アドレス（だだし物理アドレスは異なる）のフラグはリセットされる。
【発明の開示】
【課題を解決するための手段】
【０００６】
本発明は、固有の物理アドレスによってそれぞれの位置を見つけることが可能な複数のデータ記憶手段と、前記複数のデータ記憶手段の各物理アドレスを対応する複数の論理アドレスに関係づけたルックアップテーブルを記憶した記憶手段を含む制御手段とを備えたデータ記憶システムであって、前記制御手段（１２、２２）が、直接アドレスフィールド（１４）および間接アドレスフィールド（１６）をそれぞれが含む複数の予備データブロックを含み、データが前記論理アドレスに最初に書き込まれたときに、それぞれの直接アドレスフィールドが対応する第二のアドレスでプログラムされ、その後、前記論理アドレスにデータが書き込まれるたびに、間接アドレスフィールドが予備データブロックのアドレスでプログラムされ、前記予備データブロックの直接アドレスフィールドが前記論理アドレスに対応する新しい第二のアドレスでプログラムされるように前記制御手段が構成されていることを特徴とするデータ記憶システムを提供する。
【０００７】
第一のアドレスと対応する第二のアドレスとの間のマッピングを維持する方法であって、前記データブロックがポインタフラグを含む方法。
【０００８】
第一のアドレスと対応する第二のアドレスとの間のマッピングを維持する方法であって、前記ポインタフラグが、前記データブロックの他の部分とは独立に書込み可能である方法。
【０００９】
第一のアドレスと対応する第二のアドレスとの間のマッピングを維持する方法であって、対応するデータブロックの間接アドレスフィールドがプログラムされるまで前記ポインタフラグが消去状態にある方法。
【００１０】
第一のアドレスと対応する第二のアドレスとの間のマッピングを維持する方法であって、ポインタフラグを読み取って、直接アドレスフィールドと間接アドレスフィールドのどちらを読み出すかを判定する方法。
【００１１】
第一のアドレスと対応する第二のアドレスとの間のマッピングを維持する方法であって、所定の条件に達したときにデータブロックがクリーンアップされる方法。
第一のアドレスと対応する第二のアドレスとの間のマッピングを維持する方法であって、使用していないデータブロックの数が所定のしきい値を下まわったときにデータブロックがクリーンアップされる方法。
【００１２】
本発明を、添付図面を参照して例示的な方法で具体的に説明する。
【００１３】
第１Ａ図、第１Ｂ図および第１Ｃ図は、間接アドレスフィールドおよび直接アドレスフィールドを使用した二つのアドレス間の変換の原理を示す図である。
【００１４】
すべてのソリッドステートメモリシステムは、ホストから受け取った論理セクタアドレスを、主記憶装置として使用している特定のソリッドステートメモリ装置をアドレスするのに使用できる物理アドレスに変換しなければならない。したがって、何らかの論理−物理アドレス変換が必要となる。本発明のこの実施形態は、二つのルックアップテーブルを使用して、論理セクタアドレスと対応する物理セクタアドレスの間のマッピングを維持する。本発明の他の実施形態では、テーブルを一つだけ使用する。このテーブルは、前記実施形態の二つのルックアップテーブルと同じ機能を実行する。
【００１５】
第１Ａ図について説明する。各論理セクタアドレス値用のルックアップテーブルエントリ１０は、論理セクタアドレスに一次ルックアップテーブルのオフセットを加えたものに等しいアドレスによって定義される一次ルックアップテーブル１２内の記憶場所に置かれる。
【００１６】
一次ルックアップテーブル１２の各エントリは少なくとも三つのフィールドを含む。第一のフィールドは、メインメモリアドレス１４を、第二のフィールドはリンクアドレス１６をそれぞれ記憶するものであり、第三のフィールドはポインタフラグ１８である。一次ルックアップテーブル１２で使用される各エントリは、メインメモリ２０内のセクタの物理アドレスを直接に指すか、または二次ルックアップテーブル２２への間接的なポインタを提供する。この実施形態では、一次ルックアップテーブルのエントリがメインメモリ２０を指すのか、または二次ルックアップテーブル２２を指すのかを判定する手段は、関連したテーブルエントリのポインタフラグＩＳを読むことである。ポインタフラグ１８が消去されている（第１Ａ図および第１Ｂ図には英字Ｅで示されている）場合には、メインメモリアドレスが有効である。このポインタが消去されていない（第１Ａ図および第１Ｂ図には英字Ｕで示されている）場合には、二次ルックアップテーブルアドレスが有効である。
【００１７】
メインメモリ２０にデータが全く記憶されていない場合を考える。最初にデータが書き込まれるときには、記憶するデータとともに論理セクタアドレスがホストから供給される。このデータは、メインメモリ２０の物理記憶場所２４に記憶され、メインメモリ２０内のこの物理記憶場所２４のアドレスは、ホストから供給された論理セクタアドレスに対応する一次ルックアップテーブル１２のエントリ２６に記憶される。もし後で、このデータがホストによって削除され、新しいデータが、この古いデータと同じ論理セクタアドレスとともに送信された場合には、この新データは、使用されていないメインメモリ記憶場所２８に記憶される（フラッシュメモリでは、一度書き込んでしまうと消去サイクルを必要とするので、以前のメインメモリ記憶場所２４に上書きすることはできない）。次に、一次ルックアップテーブル１２を更新しなければならない。これが第１Ｂ図に示されている。
【００１８】
第１Ｂ図に、ルックアップテーブルを更新して、論理セクタアドレスと新しい物理アドレスの間の正しいマッピングを保証する方法を示す。
【００１９】
一次ルックアップテーブル１２のエントリ２６を、新データ用のメインメモリ内の記憶場所２８のアドレスで更新する必要がある。これは、論理セクタアドレス２６に対応するエントリのポインタフラグを論理０（設定なし）にし、二次ルックアップテーブル２２の使用していないエントリの一つ（以下、二次ルックアップテーブルｘｘｘエントリ３２と称する）にリンクアドレスを書き込むことよって実施される。ポインタフラグはアドレス可能なユニットを占め、消去サイクル以降、書き込まれていないので、ポインタフラグへの書き込みは可能である。ポインタの非活動状態は消去状態（論理１）である。新データが書き込まれた記憶場所のアドレスは、二次ルックアップテーブルｘｘｘエントリ３２のメインメモリアドレスフィールド１４に記憶される。
【００２０】
もし後で、新データがホストによって削除され、別のデータ（以下、最新データと称する）が送信された場合には、この最新データは、メインメモリの別の使用していない記憶場所３４（以下、使用していない最新の記憶場所と称する）に記憶される。これが第１Ｃ図に示されている。一次ルックアップテーブル１２は変更されていないが、二次ルックアップテーブル２２のｘｘｘエントリのポインタフラグ３０が書き込まれて設定なし（論理０）になっており、リンクアドレスフィールドが、二次ルックアップテーブルの使用していないエントリ（以下、二次ルックアップテーブルｙｙｙエントリ３６と称する）を指すように書き込まれている。次いで、使用していない最新の記憶場所のアドレスが、二次ルックアップテーブルｙｙｙエントリ３６のメインメモリフィールド１４に記憶される。このプロセスは、二次ルックアップテーブル２２の使用していないエントリの数が所定の値を下まわるまで継続される。
【００２１】
二次ルックアップテーブル２２がいっぱいになった場合には、クリーンアップ動作が必要となる。一次ルックアップテーブル１２をクリーンアップするときには、情報保護のため、古いルックアップテーブルを消去する前に新しいルックアップテーブルを生成しなければならない。クリーンアップ動作を実行する一つの方法は、一次ルックアップテーブル１２の上または下に少なくとも一つの消去状態の消去可能フラッシュブロックを確保することである。一次ルックアップテーブル１２の一つのエントリを、消去されているブロックにコピーし、次いで、この古いエントリを消去する。各エントリがコピーされるときに、そのエントリ用のメインメモリアドレスフィールド１４が、関連した有効な二次ルックアップテーブルエントリ（ポインタフラグが消去状態にあるエントリ）からコピーされる。その結果、一次ルックアップテーブル１２が一消去ブロック分だけ上または下に移動する。このプロセスが完了すると、二次ルックアップテーブル２２を消去できるようになる。
【００２２】
本発明の他の実施形態では、二つのフィールドのみ、すなわちメインメモリアドレスおよび二次ルックアップテーブルアドレスのみが使用される。二次ルックアップテーブルアドレスが有効データを含む場合には、メインメモリアドレスの代わりにそのアドレスが読み出される。二次ルックアップテーブルアドレスが有効データを含まない場合には、メインメモリアドレスが読み出される。
【図面の簡単な説明】
【００２３】
【図１Ａ】第１Ａ図は、間接アドレスフィールドおよび直接アドレスフィールドを使用した二つのアドレス間の変換の原理を示す図である。
【図１Ｂ】第１Ｂ図は、間接アドレスフィールドおよび直接アドレスフィールドを使用した二つのアドレス間の変換の原理を示す図である。
【図１Ｃ】第１Ｃ図は、間接アドレスフィールドおよび直接アドレスフィールドを使用した二つのアドレス間の変換の原理を示す図である。
【図１Ａ】
2006294061.tif 000003
【図１Ｂ】
2006294061.tif 000004
【図１Ｃ】
2006294061.tif 000005