(57)【特許請求の範囲】
【請求項１】
ホストからＮＡＮＤ型フラッシュメモリに書き込み指令されたデータを一旦保持するためのキャシュメモリを備えたソリッドステートドライブであって、
キャッシュメモリはＮＡＮＤ型フラッシュメモリの１ページの２のｍ乗倍（ｍは０または正の整数）の大きさの物理セグメントの集合体で構成されるものであり、
物理セグメント毎に、当該物理セグメントに書き込まれたデータの上位ＬＢＡ及びグループＬＢＡとＬＲＵ番号とを対応付けて記憶するタグメモリを備え、
ホストからの書き込み指令に係る上位ＬＢＡがタグメモリに記憶されておらず、かつ、キャッシュメモリに空の物理セグメントがある場合には、
１）空の物理セグメントにデータの書き込みを実行し、
２−１）書き込み指令に係るグループＬＢＡがタグメモリに記憶されていない場合には
上記１）にて新たにデータを書き込んだ物理セグメントに対応するＬＲＵ番号を“０”
に設定するとともに、既存の全ての物理セグメントに対応するＬＲＵ番号をそれぞれ一つずつインクリメントして、タグメモリに記憶し、
２−２)書き込み指令に係るグループＬＢＡがタグメモリに記憶されている場合には、書き込み指令に係るグループＬＢＡと同一のグループＬＢＡに対応する既存の物理セグメントに対応するＬＲＵ番号と、上記１）にて新たにデータを書き込んだ物理セグメントに対応するＬＲＵ番号とをともに“０”に設定するとともに、書き込み指令に係るグループＬＢＡと同一のグループＬＢＡに対応する既存の物理セグメントに設定されていたＬＲＵ番号よりも小さいＬＲＵ番号に対応していた物理セグメントがあれば、その物理セグメントに対応するＬＲＵ番号を一つインクリメントして、タグメモリに記憶する、手段を備えたことを特徴とする、ソリッドステートドライブ。
【請求項２】
その時点で最大のＬＲＵ番号に対応する全ての物理セグメントに対して、対応するＬＲＵ番号をキャンセルし、ＬＲＵ番号をキャンセルした全ての物理セグメントのデータをＮＡＮＤ型フラッシュメモリに転送する動作を繰り返し実行する手段をさらに備えたことを特徴とする請求項１に記載のソリッドステートドライブ。
【請求項３】
ホストからＮＡＮＤ型フラッシュメモリに書き込み指令されたデータを一旦保持する、ＮＡＮＤ型フラッシュメモリの１ページの２のｍ乗倍（ｍは０または正の整数）の大きさの物理セグメントの集合体で構成されてなるキャッシュメモリと、物理セグメント毎に当該物理セグメントに書き込まれたデータの上位ＬＢＡ及びグループＬＢＡとＬＲＵ番号とを対応付けて記憶するタグメモリ、とを備えたソリッドステートドライブにおける、ＮＡＮＤ型フラッシュメモリに対するデータ書き込み方法であって、
ホストからの書き込み指令に係る上位ＬＢＡがタグメモリに記憶されておらず、かつ、キャッシュメモリに空の物理セグメントがある場合には、
１）空の物理セグメントにデータの書き込みを実行し、
２−１）書き込み指令に係るグループＬＢＡがタグメモリに記憶されていない場合には
上記１）にて新たにデータを書き込んだ物理セグメントに対応するＬＲＵ番号を“０”
に設定するとともに、既存の全ての物理セグメントに対応するＬＲＵ番号をそれぞれ
一つずつインクリメントして、タグメモリに記憶し、
２−２)書き込み指令に係るグループＬＢＡがタグメモリに記憶されている場合には、書き込み指令に係るグループＬＢＡと同一のグループＬＢＡに対応する既存の物理セグメントに対応するＬＲＵ番号と、上記１）にて新たにデータを書き込んだ物理セグメントに対応するＬＲＵ番号とをともに“０”に設定するとともに、書き込み指令に係るグループＬＢＡと同一のグループＬＢＡに対応する既存の物理セグメントに設定されていたＬＲＵ番号よりも小さいＬＲＵ番号に対応していた物理セグメントがあれば、その物理セグメントに対応するＬＲＵ番号を一つインクリメントして、タグメモリに記憶する、ことを特徴とする、データ書き込み方法。
【請求項４】
その時点で最大のＬＲＵ番号に対応する全ての物理セグメントに対して、対応するＬＲＵ番号をキャンセルし、ＬＲＵ番号をキャンセルした全ての物理セグメントのデータをＮＡＮＤ型フラッシュメモリに転送する動作を繰り返し実行する、ことを特徴とする、請求項３に記載のデータ書き込み方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ホストからＮＡＮＤ型フラッシュメモリに書き込み指令されたデータを一旦保持するためのキャッシュメモリを備えたソリッドステートドライブ及びデータ書き込み方法に関する。
【背景技術】
【０００２】
はじめに、フラッシュメモリに対する従来のデータの書き込み方法について説明する。NAND型フラッシュメモリは、例えば、図１のような構造をとっており、ページ単位でデータの書き込み（プログラム）及び読み出しが実行され、ブロック単位でデータの消去が実行される。図１の例の場合、NAND型フラッシュメモリは８１９２のブロック（物理ブロック）で構成されるとともに、１ブロックは６４ページで構成され、さらに１ページは、ユーザデータ５１２ｂｙｔｅとECC（エラーチェックコード）と管理情報が計１６ｂｙｔｅの、合計５２８ｂｙｔｅを１ECCセクタ（本願では単にセクタという）として計４セクタ有する構成からなっている。
【０００３】
NAND型フラッシュメモリの物理ブロックアドレスは論理ブロックアドレスとの対応関係で管理される。ホストがNAND型フラッシュメモリに対し、データの書き込みやデータの読み出しを実行させる際は、その対象となるアドレスをNAND型フラッシュメモリに対して指定する（ホストが指定するこのアドレスは、一般に“ホストLBA”と称される）。このとき、NAND型フラッシュメモリのコントローラは、ホストLBAをNAND型フラッシュメモリの論理ブロックアドレスと認識し、論理ブロックアドレスと物理ブロックアドレスの対応関係表（本願では、“論理ブロック-物理ブロック変換テーブル”という）を参照してその論理ブロックアドレスに対応するNAND型フラッシュメモリの物理ブロックアドレスを割り出す。そして、その物理ブロックアドレスによって、ホストがその物理ブロックのどのページのどのセクタを基点としてデータの書き込みや読み出しを行うよう指定しているのかを割り出す（図２参照）。尚、ホストからは、ホストLBAとともに、当該書き込みデータサイズ（何セクタ分であるか）が通知される。
【０００４】
ホストからデータの書き込み指令があった場合は、NAND型フラッシュメモリ内の空きブロックに、書き換える必要のないデータとホストから送出された書き換え用データを合成してブロック単位でデータを書き直す必要がある。以下、１２セクタのデータ（ホストLBAを先頭アドレスとして書き込みを行うセクタ数）がホストから書き込み指令された場合の書き込み処理について、順次、図に従って説明する。
【０００５】
図３に示すように、ホストLBAより、データの書き換え開始を実行すべき物理アドレスが、物理ブロックアドレス１（PB１）の４ページ目（P３）の第２番目のセクタ（S１）であると判明したとする。すると、論理ブロックアドレスと対応付けされていない空きブロックを探し（これを「書き込みブロック」という。ここでは第９番目の物理ブロック／EB８を使用するものとする）、これに、データの書き換えを行わないページであるP０からP２までをコピーする（図４参照）。本例の場合、書き換えがＰ３の途中（S１）から開始するので、P３からセクタS0を読み出して、一旦バッファに移す（図５参照）。次に、NANDコマンドプロトコルに従って、前記空きブロック（EB８）の４ページ目（P3）のS０に前記バッファに移したデータをコピーするとともに、ホストから送出された書き込み用データをS１から１１セクタ分書き込む（図６）。最後の１２セクタ目のデータは７ページ目（P６）のS０に書き込まれるべきデータであるが、１ページに満たないデータは書き込みできないので、PB１のP６から、S１からS３までを一旦バッファに移す（図７）。そして、P６のセクタS０に、ホストから送出された１２番目のセクタデータを書き込むとともに、S１からS３には、前記バッファに一旦移してあるデータを移し合成する（図８）。
【０００６】
そして、PB１のP７から最終ページまでのデータをEB８にコピーする（図９）。そしてPB１に書き込まれている全データを消去し、論理ブロック-物理ブロック変換テーブルを更新し、ホストからの一のデータ書き込み指令に対する処理が終了する。
【０００７】
ところで、NAND型フラッシュメモリの場合、ホストから書き込み指令がなされた場合、その都度、NAND型フラシュメモリに対して上記書き込み処理が実行される。このため、書き込み処理に時間が掛かる。さらに、NAND型フラッシュメモリの寿命はデータの書き込みや消去の回数に依存するため、これが頻繁に行われる従来の方法では、NAND型フラッシュメモリの長寿命化を図り難いという問題がある。
【特許文献１】特開２０００−３４９８５３
【特許文献２】特開２００１−２７３７７６
【特許文献３】特開２００６−３２３７３９
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ここにおいて、本発明が解決すべき課題は、より迅速で、NAND型フラッシュメモリやこれを制御するコントローラに掛かる負荷を軽減することのできるキャッシュメモリを備えたソリッドステートドライブ及びデータ書き込み方法を提供することにある。その他の課題は、明細書、図面、特に特許請求の範囲から自ずと明らかとなろう。
【課題を解決するための手段】
【０００９】
上記課題解決のため、本発明は、ホストから書き込み指令されたデータをキャッシュメモリに一旦待避してからNAND型フラッシュメモリに書き込む、キャッシュメモリを備えたソリッドステートドライブ及びデータ書き込み方法を提供する。即ち、ホストとNAND型フラッシュメモリの間にキャッシュメモリを介在させ、ホストから時々刻々送出されてくる書き込み用データを、キャッシュメモリのセグメントに一旦待避させる。これにより、所定論理ブロックに対するホストからのデータ書き込み指令を纏めて処理することができ、NAND型フラッシュメモリやこれを制御するコントローラに過度の負担を掛けることなく、書き込み時間を軽減し、併せてNAND型フラッシュメモリの寿命延長を図ることができる。
【００１０】
さらに具体的には、本願が特許請求の範囲に記載する新規な特徴的構成により、上記課題を解決する。
【００１１】
【００１２】
【００１３】
【００１４】
【００１５】
【００１６】
【００１７】
【００１８】
【００１９】
【００２０】
【００２１】
【００２２】
【００２３】
【００２４】
【００２５】
【００２６】
【００２７】
【００２８】
【００２９】
【００３０】
【００３１】
【発明を実施するための最良の形態】
【００３２】
以下、本発明を実施するための最良の形態について図面を用いて説明するが、本発明は特許請求の範囲内において種々の形態を採ることができ、下記実施形態に限定されないことはいうまでもない。
【００３３】
（フラシュメモリのデータ領域の構成例）
本発明を説明するにあたり、初めに、フラッシュメモリのページ構成例について図１０により説明する。フラッシュメモリは、二値小ブロック、二値大ブロックの他、多値大ブロックがある。二値小ブロックは、１ページが１ECCセクタ、即ち、５１２ｂｙｔｅのデータ領域と１６ｂｙｔｅの冗長領域で構成されるとともに（図１０（ａ））、１ブロックが１６ページ又は３２ページで構成される。二値大ブロックは、例えば１ページが４ECCセクタで構成されるとともに、１ブロックが６４ページで構成される。多値大ブロックも、例えば、１ページが４ECCセクタで構成され得るが（図１０（ｂ））、１ブロックが６４ページ又は１２８ページで構成される。本発明のキャッシュメモリを供えたソリッドステートドライブ及びデータ書き込み方法は、前記二値メモリと多値メモリのいずれにも適用可能であるが、本実施形態例では、特にことわりのない限り、１ページが４ECCセクタで構成されるとともに、１ブロックが６４ページで構成される二値大ブロックを使用する場合について説明する。
【００３４】
（システム構成例）
図１１を用いて、本発明が実施されるシステムの概要について説明する。本発明は、ホスト１と、このホスト１から例えばATAインターフェースで接続されるSSD（ソリッドステートドライブ）２とで構成されるシステムで実施され得る。SSD２は、複数のNAND型フラッシュメモリ２１（以降NAND型フラッシュメモリを単にフラッシュメモリという）と、ホスト１から送出された書き込み用データを一時的に待避するためのキャッシュメモリ２２と、キャッシュメモリ２２に貯蔵されたデータのフラッシュメモリ２１に対する書き込み制御などを行なうメインコントローラ２３とで構成される。このメインコントローラ２３は、ホスト１からフラッシュメモリ２１に記憶されているデータ読み出し指令があった場合はこれをホスト１に送出するための制御も実行する。
【００３５】
キャッシュメモリ２２は、例えばSDRAM（Synchronous DRAM）で構成することができる。フラッシュメモリ２１とメインコントローラ２３は、個別のＩＣで構成してもよいし、ワンパッケージで構成してもよい。SSD２は、ホスト１から物理的に独立した構成であってもよいし、基板タイプで構成し、ホスト１から着脱自在にして、フラッシュメモリ２１の寿命が到来したときは、新品と容易に交換可能な構成にしてもよい。キャッシュメモリ２２は、フラッシュメモリ２１の１ページの２のｍ乗倍（ｍは０又は１より大きい整数）の大きさのセグメントの集合体で構成される（後述する“仮想セグメント”と区別するためにこれを“物理セグメント”という）。フラッシュメモリ２１の１ページが４セクタで構成される場合、１物理セグメントは、4セクタ、8セクタ、16セクタ、３２セクタ、６４セクタ、１２８セクタ、２５６セクタで構成され得るが、後述する本実施形態例では、１物理セグメントが１６セクタで構成されるものとして説明する。各物理セグメントはCPU２３７がアドレスによって管理する。
【００３６】
メインコントローラ２３は、以下の構成要素を含む。即ち、フラッシュメモリ２１へのデータの書き込みや読み出しをNANDプロトコルに基づいて制御するNANDフラッシュコントローラ２３５、ホスト１からATAコマンドに基づき書き込み指令されたデータをSSD２に取り込む際の通信制御を行うATAインターフェース制御部２３１、バス２３２、ATAインターフェース制御部２３１からバス２３２を介してホスト１から送出されたデータをキャッシュメモリ２２に転送する際の物理的制御を行うSDRAMコントローラ２３４、CPU２３７、CPU２３７からの指令に基づき、ホストから送出されたデータをキャッシュメモリ２２に書き込む際の管理やキャッシュメモリ２２のデータをフラッシュメモリ２１側に送出する際の管理を行うキャッシュマネージャ２３６を有する。尚、CPU２３７は、メインコントローラ２３内の上記各ブロックを統括的に管理する。またCPU２３７は、図示しないプログラムコード格納領域を有し、本願発明を実施するコンピュータプログラム（ファームウエア）を記憶している。また、作業領域としてのRAM領域を有している。NANDフラッシュコントローラ２３５は、エラー訂正回路を含み、キャッシュメモリ２２から送出されたデータをフラッシュメモリ２１に書き込む際に、エラー訂正符号を作出し、これをフラッシュメモリ２１の各セクタの冗長領域に書き込む。
【００３７】
キャッシュマネージャ２３６のハードウエア構成を図１２に示す。キャッシュマネージャ２３６は、タグメモリ３１、セクタメモリ３２、タグメモリ検索／更新回路３３、セクタメモリ検索／更新回路３４を有し、レジスタ３０が、バス２３２に接続している。タグメモリ３１は、上位LBA、グループLBA、LRU番号、書き込まれたデータの有効（Valid=1）若しくは無効（Valid=０）の設定、待ち行列（Queue状態）として設定されているか（Lock=１）否か（Lock=０）、Queue値などの情報を記録するためのものである。詳しくは後述する。タグメモリ検索／更新回路３３は、CPU２３７からレジスタ３０を介して送られた指令に従い、タグメモリ３１に対して前記情報の書き込みや更新、さらには設定されている情報の検索を実行する回路であり、専用のハードウエアを用いて構成することができる。セクタメモリ３２には、セクタマップテーブルが用意されている。セクタマップテーブルは、CPU２３７が物理セグメントに書き込まれたデータの状況をリアルタイムで記録及び更新し、その状態を検索するセクタマップを構成するためのものである。セクタマップテーブルはシリアル番号が付されてなる仮想セグメントの集合体で構成され、CPU２３７が当該物理セグメントに書き込まれたデータの状況をセクタ単位で記録する。本願では、仮想セグメントに付される番号を“仮想セグメント番号”と称するものとする。セクタメモリ検索／更新回路３４は、CPU２３７からレジスタ３０を介して送られた指令に従い、セクタマップテーブルに対する記録や更新、並びに検索を実行する回路であり、同様に専用のハードウエアを用いて構成することができる。尚、詳細は後述するが、CPU２３７は、セクタメモリ３２のセクタマップに記録されている情報に基づいて、物理セグメントに書き込まれているデータをフラッシュメモリ２１に転送する。物理セグメントアドレスとそのデータ書き込み状況を記録する仮想セグメントの番号（仮想セグメント番号）は一対一に固定的に対応付けて扱うことができ（図２０参照）、CPU２３７は、この対応関係に基づき、仮想セグメントの記録根拠である物理セグメントから前記データの転送を行う。
【００３８】
（動作説明）
図１3は、タグメモリ３１とセクタメモリ３２に記録される内容を併せてこれを模式的に表したものである。図の右側がセクタマップテーブルであり、左側がタグメモリに記録される内容である。図において、“Seg.”は仮想セグメントを表し、その下に続く数字は、仮想セグメント番号を表す。図示するように、仮想セグメントには、その先頭が“０”から始まるシリアルな仮想セグメント番号が予め設定されている。
【００３９】
一の仮想セグメントは、一の物理セグメントに格納された１６セクタ分のデータの書き込み状況をセクタ単位で記録できるようになっており（１６セクタ対応）、このため仮想セグメントは１６に分割されている。本実施形態例のセクタマップテーブルは、便宜上、１６セクタ対応の仮想セグメントが計１６で構成されるものとして説明する。この場合、セクタマップテーブルは、１物理ブロック分（２５６セクタ）のデータ書き込み状況を記録できることになるが、実際の設計に当たっては、キャッシュメモリ２２のデータ格納領域のすべてのデータ書き込み状況を把握できるように構成する。
【００４０】
（Ａ-１：最初の書き込み）
システムに電源投入後、CPU２３７は、ホスト１から最初に書き込み指令を受けたデータを、物理セグメントアドレス“０”から順に書き込む。そして物理セグメントアドレス“０”におけるデータの書き込み状況は、セクタマップテーブルの仮想セグメント番号“０”から順に記録される。
【００４１】
図１３では、ホストLBAが０ＡＣ３ｈ（ｈは１６進法の表示であることを表す）で１０セクタ分のデータが物理セグメントに書き込まれ、その状況が、仮想セグメント番号“０”に記録されている様子を示している。
【００４２】
本実施形態例の仮想セグメントは１６セクタ対応（１６分割）であるため、ホストLBAの最終桁の値の取り得る範囲と一致するので、CPU２３７はこれと対応させるべく、仮想セグメントのセクタアドレス“３ｈ”から始まって、物理セグメントに書き込まれた１０セクタ分、“データ書き込み済み状態”である旨記録する（この記録は、仮想セグメントの該当するアドレスに、フラグ（ｂｉｔ“１”）を立てることにより行う）。仮想セグメントにおいてグレーで表された箇所は、“データ書き込み済み状態”として記録されたことを表している。
【００４３】
CPUはこれとともに、タグメモリ検索／更新回路３３に指令して、タグメモリ３１のタグテーブルに、仮想セグメント番号“０”のデータに関する上位LBA、グループLBAを記憶する（タグテーブルは、図１３のセクタマップを除いた部分である）。
【００４４】
上位LBAは、仮想セグメントのサイズとホストLBAとより一義的に決定するものであり、仮想セグメントにおける、ホストLBAの位置からみたその仮想セグメントの先頭位置（セクタ）の見かけ上の論理ブロックアドレスである。よってこの場合、ホストLBA（０ＡＣ３ｈ）の上位LBAは、０ＡＣ０ｈとなる。
【００４５】
一方グループLBAは、当該フラッシュメモリの１物理ブロックあたりのセクタ数によって決定する。例えば、１物理ブロックが６４ページ構成で、且つ１ページが４セクタで構成されている場合は、１物理ブロックあたり２５６セクタであるから、ホストLBAの下２桁００ｈからＦＦｈで１論理ブロックを構成し、したがって、この下２桁を除いた値がフラッシュメモリの物理ブロック番号に該当する（但し、論理ブロックと物理ブロックが１対１に対応する場合である）。ホストLBAが上記０ＡＣ３ｈの場合、グループLBAはその先頭の２桁、即ち “OA”となる。
【００４６】
仮想セグメントが３２セクタの場合は、１６セクタサイズの倍のサイズで構成されるため、その上位LBAは、その下２桁が００ｈ、２０ｈ、４０ｈ、６０ｈ、８０ｈ、Ａ０ｈ、Ｃ０ｈ、Ｅ０ｈのいずれかの値をとる（全部で８通り）。
【００４７】
そして、ホストLBAが仮に３BＤ３ｈであるとすると、セクタマップにおいては、上位LBAが３BＣ０ｈで設定される仮想セグメントの先頭から２０番目（Ｆｈ＋３ｈ）がホストLBAに該当し、上述した記録が開始される位置となる。
【００４８】
また、仮想セグメント番号“０”にデータ書き込み状況が記録されると、CPUは前記上位LBA、グループLBAのほか、その仮想セグメントを構成する物理セグメントのデータが有効（“Valid”＝１）である旨設定し、タグメモリ３１のタグテーブルに記憶する。ここで“有効”とは、当該物理セグメントに書き込まれているデータが後にフラッシュメモリに書き込まれるかもしれない有効なデータであり、したがってその仮想セグメントに関してタグメモリに記録されている情報が有効であることを意味する。尚、システムに電源を投入したとき、全セグメントはValid＝０（無効）に初期化される。
【００４９】
またタグテーブルには、Lockという項目がある。Lockは、CPU２３７がそのセグメントに書き込まれているデータをフラッシュメモリへ書き込むことを決定し、該書き込みのための待ち行列（Queue）として設定するときに用いる。即ち、待ち行列として設定するときは、Lock＝１と設定する。Lock＝１と設定されると、その仮想セグメントは、その後、ホストから該仮想セグメントに設定されているのと同じ上位LBAのデータが書き込み指令された場合であっても、CPU２３７は、そのデータをその仮想セグメントを構成する物理セグメントに上書きすることはない。尚、システムに電源を投入したとき、全仮想セグメントはLock＝０に初期化される。
【００５０】
上記の通り、本実施形態例では、１仮想セグメントを１６セクタで構成しているが、物理セグメントサイズに対応して、１仮想セグメントを、３２セクタサイズ（８ページ分）、６４セクタサイズ（１６ページ分）、或いは１２８セクタサイズ（32ページ分）などで構成してもよい。
【００５１】
CPU２３７は、さらに仮想セグメント番号“０”にLRU（Least
Recently Used）番号“０”を設定し、タグメモリ３１のタグテーブルに記憶する。LRU番号は、書き換え対象となるフラッシュメモリの論理ブロックが同一であるデータを記憶している物理セグメントが複数存在する場合、CPUが“同一LRUグループ”として扱うために、これら物理セグメントに対するデータ書き込み状況を記録した複数の仮想セグメントに同一のLRU番号を設定するものである。LRU番号は、“０”から始まり、順に大きい値が設定されるが、グループLBAが同一となるべき他の仮想セグメントが既に存在する場合は、書き込まれた先後を問わず、それら既存の仮想セグメントにも同一のLRU番号が設定され、タグメモリに記憶される。
【００５２】
ホスト１から一の書き込み指令で送出されてきたデータが物理セグメントアドレス“０”に書ききれない場合は、次の空の物理セグメントアドレス“１”に書き込まれる。そして仮想セグメント番号“１”に当該データ書き込み状況が記録される。このとき、仮想セグメント番号“１”の上位LBAは０ＡＤ０ｈとなることが理解できよう。仮想セグメント番号“０”と仮想セグメント番号“１”のグループLBAはともに“０A”で同一のLRU番号が設定される。
【００５３】
ホストLBAが例えば０ＡＥ３ｈで３０セクタ分のデータがキャッシュメモリ２２に書き込まれる場合は、仮想セグメント番号“１”のグループLBAは“０B”であり、仮想セグメント番号“０”とは異なるグループLBAとなるため（フラッシュメモリの異なる論理ブロックに書き込まれるべきデータとなる）、当然異なるLRU番号が設定されることになる。尚、本実施形態例では、特にことわりのない限り、ホストから書き込み指令されたデータを一の物理セグメントに書き込みできる場合について説明する。
【００５４】
（Ａ-２：引き続く書き込み）  
ホストから引き続きデータ書き込み指令があったとき、CPU２３７はタグメモリ検索／更新回路３４に指令して、タグメモリ３１を検索させる。そして、当該書き込み指令されたデータの上位LBAと同一の上位LBAが設定されている仮想セグメントがある場合（検索結果＝hit）は、当該hitした仮想セグメントを構成する物理セグメント群に対してデータを上書きする。その後、その仮想セグメントのLRU番号を“０”に更新して、タグメモリ３１のタグテーブルに記憶する。そして、前記既存の仮想セグメントに設定されていたLRU番号より小さいLRU番号の仮想セグメントが存在すれば、それらの仮想セグメントの各LRU番号をそれぞれ一つだけインクリメントして、タグメモリ３１のタグテーブルに記憶する。
【００５５】
（Ａ-3）
CPU２３７がタグテーブルを検索した結果、当該書き込み指令されたデータの上位LBAと同一の上位LBAが設定されている仮想セグメントが無く（検索結果＝miss）、空の仮想セグメントがある場合は、空の物理セグメントにデータの書き込みを実行し、書き込まれたデータの状況をマップテーブル上の新たな仮想セグメントに記録する。そして、その空の物理セグメントに書き込まれたデータの上位LBAとグループLBAをその仮想セグメント番号と対応付けて、タグメモリ３１のタグテーブルに記憶する。また、データ書込みを行った当該物理セグメントのデータが“有効”である旨設定する。この新たに設定した仮想セグメントのグループLBAと同一のグループLBAの仮想セグメントがない場合は、新たにデータを書き込んだ物理セグメントに対応する仮想セグメントのLRU番号を“０”に設定するとともに、既存の全仮想セグメントのLRU番号をそれぞれ一つずつインクリメントして、これらをタグメモリに記憶する。
【００５６】
また、グループLBAが同一である既存の仮想セグメントがある場合は、新たにデータを書き込んだ物理セグメントに対応する仮想セグメントのLRU番号を前記既存の仮想セグメントに設定されているそれと同一の値に設定した後、前記既存の仮想セグメントとともにLRU番号を“０”に変更し、前記既存の仮想セグメントに設定されていたLRU番号より小さいLRU番号が設定されていた仮想セグメントがあればその仮想セグメントに設定されているLRU番号を一つだけインクリメントして、それぞれタグメモリに記憶する。以上のステップを、物理セグメントに対するデータの書き込みが仮想セグメントの所定のアドレス（閾値）に至るまで実行する。この閾値は、最終の仮想セグメント番号に至る途中に設定してもよいし、最終仮想セグメント番号に設定してもよい。
【００５７】
以上の変遷状態を、図面を用いて説明する。図１４は、図１３に引き続き、さらに物理セグメントアドレス“１”から順にデータの書き込みが実行され、上位LBAが同一の仮想セグメントがないので、仮想セグメント番号“１”、“２”、“３”に、順次データの状況が記録された状態例である。
【００５８】
即ち、仮想セグメント番号“１”にホストLBAが０５１１ｈでデータ長5セクタ分のデータの状況が記録され、続いて、仮想セグメント番号“２”にホストLBAが１３Ｂ５ｈでデータ長１０セクタ分のデータの状況が記録され、さらに仮想セグメント番号“３”にホストLBAが００８Ａｈでデータ長６セクタ分のデータの状況が記録された場合である。仮想セグメント番号“０”乃至仮想セグメント番号“３”に設定されたグループLBA（データ書き換え対象論理ブロック）は互いに異なるので、同一LRUグループを構成することなく、最新にデータが書き込まれた物理セグメントによって構成される仮想セグメントのLRU番号がもっとも小さく、古いものほど大きい値に設定されていることが理解できよう。
【００５９】
図１５は、その後仮想セグメント番号“４”にホストLBAが０５２０ｈで１３セクタ分の最新のデータの状況が記録された状態を示している（Ａ-２）。仮想セグメント番号“１”と仮想セグメント番号“４”の“グループLBA”（データ書き換え対象論理ブロック）が同じであるので、これらは同一LRUグループを構成する。したがって、まず、仮想セグメント番号“４”のLRU番号を、既存のセグメントアドレス“１”のLRU番号“２”に設定してから、両者のLRU番号をともに“０”に更新し（図１５参照）、タグメモリ３１のタグテーブルに記憶する。そして、仮想セグメント番号“１”の更新される前のLRU番号“２”より小さいLRU番号の仮想セグメント（仮想セグメント番号“２”と仮想セグメント番号“３”）は、それぞれそのLRU番号を一つだけインクリメントして、タグメモリ３１のタグテーブルに記憶する。図１５において、仮想セグメント番号“２”のLRU番号“１”を“２”に更新し、仮想セグメント番号“３”のLRU番号“０”を“１”に更新している。さらに図１６に、仮想セグメント番号“５”以下、最終仮想セグメント（仮想セグメント番号“１５”）までデータの状況が記録された状態例を示している。
【００６０】
（A−３：キャッシュメモリ充填後の処理）
CPU２３７が物理セグメントに対するデータの書き込みを仮想セグメントが満杯に至るまで実行すると、CPU２３７はLRU番号が最大値に設定されている仮想セグメント（グループLBAが同一の複数のセグメントがある場合はそれら全部）にLock=1（Queue状態）を設定し、タグメモリ３１に記憶する。これにより、以降この仮想セグメントに対しては、上位LBAがその仮想セグメントのそれと同じデータがホストから送出されても、その仮想セグメントの記録根拠となっている物理セグメントにデータを上書きすることはない。即ち、その物理セグメントのデータの保護が図られる。そして、その最大LRU番号の仮想セグメントに設定されているLRU番号をすべてキャンセルし、新たにQueue値“０”を設定し、これをタグメモリ３１に記憶する。Queueとは待ち行列、即ち、フラッシュメモリに対する書き込みが待ち行列状態になっていることを意味する。CPU２３７は、Queue値の設定された順、即ち、Queue値が小さいものから順に、その仮想セグメントの記録根拠となっている物理セグメントに記憶されているデータをNANDフラッシュコントローラ２３５に対して書き込み指令する。この書き込み指令は、CPU２３７が、当該仮想セグメント番号に係るタグメモリ３１とセクタメモリ３２に記録されているデータの状況に基づき、コマンドを発行して実行する。
【００６１】
図１７は、図１６の状態になった後に、仮想セグメントの記録根拠となっている物理セグメントからのデータの追い出しを実行する場合のタグテーブルの設定状態を表したものである。（本願では、仮想セグメントの記録根拠となっている物理セグメントに記憶されているデータをフラッシュメモリ２１側に転送する処理を、適宜、データの追い出しまたは単に追い出しという）。データの追い出しを実行する際は、図１８に示すように、CPU２３７が、LRU番号が最大の仮想セグメント（仮想セグメント番号“５”と仮想セグメント番号“２”）に、上書き不可のLockを掛け（lock＝１に設定）、さらに両者のLRU番号をキャンセルし、新たにQueue値“０”を設定する。
【００６２】
そして、Queue値“０”に設定した仮想セグメント番号“２”及び仮想セグメント番号“５”に格納されているデータは、CPU２３７によりNANDフラッシュコントローラ２３５に転送され、NANDフラッシュコントローラ２３５によりフラッシュメモリ２１に書き込まれる。フラッシュメモリ２１に対するデータ書き込みの基本手順は、本願の「背景技術」に記載の通りであるが、本発明の場合は、一の空きブロックに、書き換え対象データを構成する複数の物理セグメントのデータを一度に書き込ませることを特徴としている。
【００６３】
まず、書き換え用データ、即ち複数の仮想セグメントの記録根拠となっている物理セグメントのデータを、一の仮想セグメント（実際にはその記録根拠となっている物理セグメント）ごと、コマンドによりNANDフラシュコントローラ２３５に書き込み指令する。するとNANDフラッシュコントローラ２３５は、「背景技術」に記載の通り、所定の空きブロックに、データの書き換えを行わないデータをページ単位でコピーするとともに、転送されてきた書き換え用データをページ単位で書き込む。書き込みがページの途中で開始または終了する場合は、「背景技術」で説明した通り、バッファを利用してページ単位のデータに編成して書き込む。空きブロックにデータの書き込みを完了すると、書き換え対象であった物理ブロックの全データを消去して空きブロックとし、論理ブロック-物理ブロック変換テーブルを書き換える。この方法により、通常であれば、所定の空きブロックに対する複数のデータ書き換え作業が必要となるところ、一度の書き換え作業で済み、書き込み時間を短縮できるとともにブロックの書き換え回数を減らすことができる。従ってフラッシュメモリの延命を図ることができる。図１８は、Queue値“０”が設定された仮想セグメント番号“２”及び仮想セグメント番号“５”を構成する物理セグメント群に書き込まれているデータがフラッシュメモリ２１側に転送されていく様子を模式的に表している。
【００６４】
なお、フラッシュメモリ２１にデータが書き込まれた仮想セグメント番号“２”及び仮想セグメント番号“５”の記録は、転送された段階では当該仮想セグメント上、及びセクタマップ上で消去されない。しかし、このデータは既にフラッシュメモリ２１側に転送済みであるから、CPU２３７は、仮想セグメント番号“２”と仮想セグメント番号“５”の記録が“無効（Valid＝０）”である旨をタグメモリ３１に設定する（図１９）。記録が無効とは、CPU２３７が、その仮想セグメントの記録根拠となっている物理セグメントを空の物理セグメントとして扱ってよいということを意味する。即ち、Valid＝０と設定されている限りは、CPU２３７は、タグメモリ３１に記憶されたまま残っている当該セグメントに係るLock＝１（上書き不可）の設定、上位LBAの値、グループLBAの値のすべてを無効と看做す。また、フラッシュメモリ２１側へのデータの転送が完了すると、その仮想セグメントに設定されていたQueue値は、タグメモリ３１上でキャンセルされる（この段階では、Queue値とLRU番号の両者とも設定されていない状態となる。）
【００６５】
その後、ホストLBA（０４Ｄ４ｈ）が指定されて、５セクタ分のデータの書き込み指令があったとする。CPU２３７は、ここでタグメモリ検索／更新回路３３にタグメモリ３１を再度検索させる。すると、上位LBAが同一の仮想セグメントがないこと、並びに、先ほど追い出しを実行した仮想セグメント番号“２”及び仮想セグメント番号“５”の両者が空きセグメント（“無効（Valid＝０）”）であることをCPU２３７は把握する。今回のホストからの書き込み指令は、空きセグメントへのデータ書き込みを実行する場合であるが、一つの仮想セグメントを構成する物理セグメントへの書き込みで足りるものである。斯かる場合、アドレスの小さい空の物理セグメントからデータを書き込むようにルール化しておけば、CPU２３７は物理セグメント番号“２”に新規なデータを書き込む（図１９）。この場合（追い出し後の新規データの書き込み）、SSD２がホスト１から前記データ書き込み指令を受けると、CPU２３７は、まず、セクタメモリ３２のセクタマップから、仮想セグメント番号“２”に記録されているデータの状況を消去する。すると、ATAインターフェース制御部２３１はCPU２３７の指令に基づき、ホスト１に対して、データ転送OKのステータス信号を送る。そして、ホスト１はそのバッファ（図示せず）に待機させていた書き込み用データを、SSD２側に転送する。ATAインターフェース制御部２３１から転送されてきたデータは、CPU２３７がSDRAMコントローラ２３４をして、仮想セグメント番号“２”の記録根拠となっている物理セグメントに格納させる。
【００６６】
データを格納すると、新たにデータを書き込んだ仮想セグメント番号“２”の記録根拠となっている物理セグメントのデータを“有効（Valid＝１）”に変更し、“Lock＝１”を “Lock＝０（Queue状態ではない）”に変更し、当該仮想セグメントにLRU番号“０”を設定し、また、上位LBAを０４Ｄ０ｈ、グループLBAを“０４”に変更して、それぞれタグメモリ３１に記憶する。さらに、空きセグメントである仮想セグメント番号“５”以外のデータ有効仮想セグメントのLRU番号を一つだけインクリメントし、これらを前記タグメモリに記憶する。図１９にその状態を模式的に表している。
【００６７】
Queue値は、物理セグメントからフラッシュメモリ側へのデータの追い出しの度にその値が一つずつ減算される。このとき、それまでにQueue値を設定した数から、それまでにデータの追い出しを完了しているQueueの数を差し引けば、CPU２３７は、その時点でデータがまだフラッシュメモリ２１に転送完了していない待ち行列状態のQueue数を知ることができる。
【００６８】
物理セグメントからデータの追い出しが実行されてQueue値が設定されるごとにHost-Queue-Pointerと名付けたポインタを１ずつ加算する。フラッシュメモリ２１に対しては、その値の小さいものから順にデータが転送されるが、この転送が完了するごとに、Disk-Queue-Pointerと名付けたポインタを１ずつ加算する。この値は、フラッシュメモリ２１側にデータ転送が完了したQueueの数に相当するので、Host-Queue-Pointerの値からDisk-Queue-Pointerの値を引いた値が、キャッシュメモリからデータの追い出しの完了していないQueueの数となる。CPU２３７は、この追い出しの完了していないQueue数をフラッシュメモリ２１に対するデータの追い出しの制御などに利用してもよい。
【００６９】
（Queue値設定例）
Queue値の設定は上述した通りであるが、前記Queue-Pointer値を利用して、物理セグメントに対するデータの書き込みが仮想セグメントの最終アドレスに至らない段階で、Queue値を複数設定し、追い出し処理を実行してもよい。例えば、システムに電源投入後、キャッシュメモリ２２に対するデータの書き込みが予め定めたセグメント数（閾値）を超えたとき、その時点で最大のLRU番号が設定されている仮想セグメントにQueue値“０”を設定してQueue値“０”を構成する仮想セグメントの物理セグメント群からデータの追い出しを実行する。そして、Queue値“０”の仮想セグメントのデータがフラッシュメモリ２１に書き込み完了する直前に、新たなQueue値“１”を該当する仮想セグメントに設定する（このタイムインターバルは実験値等で経験的に求めればよい）。これを繰り返すことにより、データ転送状態のQueueが常時存在し、転送待ちのQueueを、実質的に、常時一つにすることができる。言い換えれば、前記一のQueueを構成するセグメントのデータがフラッシュメモリに転送完了した段階で、次の転送待ちであったQueueを構成するセグメントのデータをフラッシュメモリに転送開始でき、フラッシュメモリへのデータ転送の無駄な待ち時間をなくすことができる。また、データ転送待ちのQueue（物理セグメント）を最小限にすることができる。
【００７０】
本発明の詳細は上記の通りであるが、ここにその基本手法（骨子）を整理する。
１．システムの電源投入後、先頭のセグメントから順次データを書き込む。
２．フラッシュメモリの書き込み対象ブロックが同一であるセグメントデータを同一
LRUグループとして管理する。
３．データの上書きが可能な場合は優先してこれを実行する。
４．データの上書きができない場合は、空きセグメントにデータを記憶する。
５．データの追い出しは、LRU番号の最も大きいセグメントから順にQueue値を設定し、これに基づきデータの追い出しを実行する。フラッシュメモリへのデータの転送は、タグメモリとセクタマップに記録された情報に基づいて行う。
６．追い出しによって作られた空きセグメントに新たなデータの書き込みを実行する。
７．以上のルーチンを、ホストからのデータ書き込み指令が終了し、キャッシュメモリがすべて空きセグメントになるまで実行する（ホストからのデータ書き込み指令が途絶えると、キャッシュメモリ２２に残っているデータは、CPU２３７が自動的にフラッシュメモリ２１側に転送し書き込みが実行される）。
【図面の簡単な説明】
【００７１】
【図１】NAND型フラッシュメモリのデータ構造例である。
【図２】ホストLBAと物理ブロックの対応関係例である。
【図３】NANDフラッシュメモリにおけるデータ書き換えの概念図である。
【図４】空きブロックへのデータ書き込み手順である（その１）。
【図５】空きブロックへのデータ書き込み手順である（その２）。
【図６】空きブロックへのデータ書き込み手順である（その３）。
【図７】空きブロックへのデータ書き込み手順である（その４）。
【図８】空きブロックへのデータ書き込み手順である（その５）。
【図９】空きブロックへのデータ書き込み手順である（その６）。
【図１０】NAND型フラッシュメモリのページ構成例である。
【図１１】本発明を実施するシステムの構成例である。
【図１２】キャッシュマネージャのハードウエア構成である。
【図１３】タグメモリとセクタマップの内容を模式的に表した第1の状態例である。
【図１４】タグメモリとセクタマップの内容を模式的に表した第2の状態例である。
【図１５】タグメモリとセクタマップの内容を模式的に表した第3の状態例である。
【図１６】タグメモリとセクタマップの内容を模式的に表した第4の状態例である。
【図１７】タグメモリとセクタマップの内容を模式的に表した第5の状態例である。
【図１８】タグメモリとセクタマップの内容を模式的に表した第6の状態例である。
【図１９】タグメモリとセクタマップの内容を模式的に表した第7の状態例である。
【図２０】ホストからNAND型フラッシュメモリへのデータの流れである。
【符号の説明】
【００７２】
１  ホスト
２  SSD
２１  NAND型フラッシュメモリ
２２  キャッシュメモリ
２３  メインコントローラ
３１  タグメモリ
３２  セクタメモリ  
３０  レジスタ  
３３  タグメモリ検索／更新回路
３４  セクタメモリ検索／更新回路
２３１  ATAインターフェース制御部
２３２  バス
２３４  SDRAMコントローラ
２３５  NANDフラッシュコントローラ
２３６  キャッシュマネージャ
２３７  CPU
【図１】
0004315461.tif 000002
【図２】
0004315461.tif 000003
【図３】
0004315461.tif 000004
【図４】
0004315461.tif 000005
【図５】
0004315461.tif 000006
【図６】
0004315461.tif 000007
【図７】
0004315461.tif 000008
【図８】
0004315461.tif 000009
【図９】
0004315461.tif 000010
【図１０】
0004315461.tif 000011
【図１１】
0004315461.tif 000012
【図１２】
0004315461.tif 000013
【図１３】
0004315461.tif 000014
【図１４】
0004315461.tif 000015
【図１５】
0004315461.tif 000016
【図１６】
0004315461.tif 000017
【図１７】
0004315461.tif 000018
【図１８】
0004315461.tif 000019
【図１９】
0004315461.tif 000020
【図２０】
0004315461.tif 000021