(57)【要約】      （修正有）【課題】コンパクション処理の完了までの時間を短縮化し、ホストに対するライトレイテンシを保証できるメモリ制御装置を提供する。【解決手段】コンパクションコントローラ４３は、フラッシュメモリに対するコンパクション処理を制御し、検索部と、検索中止判断部と、コンパクションリード処理部と、コンパクションライト処理部とを含む。検索部はリード・ライトコントローラにより有効データを読み出す対象であるコンパクション元ブロックから有効データを検索する。検索中止判断部は検索部による検索処理量が上限値を超える場合に検索部の検索処理を中止する。コンパクションリード処理部はリード・ライトコントローラを介して検索部により検索された有効データをコンパクション元ブロックから読み出す。コンパクションライト処理部はコンパクションリード処理部により読み出された有効データを所定のデータ量単位でコンパクション先ブロックに書き込む。【選択図】図１
2013196646.tif 000002
【特許請求の範囲】
【請求項１】
フラッシュメモリに対するデータの読み出し、書き込みを制御するリード・ライトコントローラと、
前記フラッシュメモリに対するコンパクション処理を制御するコンパクションコントローラとを具備し、
前記コンパクションコントローラは、
コンパクション処理対象であるコンパクション元ブロックから有効データを検索する検索部と、
前記検索部による検索処理量が上限値を超える場合に、前記検索部の検索処理を中止する検索中止判断部と、
前記リード・ライトコントローラを介して、前記検索部により検索された前記有効データを前記コンパクション元ブロックから読み出すコンパクションリード処理部と、
前記コンパクションリード処理部により読み出された有効データを所定のデータ量単位でコンパクション先ブロックに書き込むコンパクションライト処理部と
を有するメモリ制御装置。
【請求項２】
前記コンパクションコントローラは、
前記検索中止判断部により前記検索処理が中止されて、前記コンパクション先ブロックに書き込む有効データが前記データ量単位を満たさない場合に、前記データ量単位を満たすようにデータ制御処理を実行するデータ制御処理部を含む請求項１に記載のメモリ制御装置。
【請求項３】
前記データ制御処理部は、
前記コンパクション元ブロックから読み出された有効データと共に前記データ量単位を満たすだけのダミーデータを追加する請求項２に記載のメモリ制御装置。
【請求項４】
前記データ制御処理部は、
前記検索中止判断部により前記検索処理が中止されたときに、前記コンパクション先ブロックに書き込むコンパクションライト処理を中断し、
前記コンパクション元ブロックから読み出される有効データが前記データ量単位を満たすまで有効データをバッファメモリに蓄積する請求項２に記載のメモリ制御装置。
【請求項５】
前記検索処理量は、検索対象のコンパクション元ブロック数、検索対象の有効データの前記データ量単位に相当する論理ページのページ数あるいは検索処理時間のいずれかである請求項１から４のいずれか１項に記載のメモリ制御装置。
【請求項６】
前記コンパクションコントローラは、
前記フラッシュメモリに対してホストからの書き込み要求に応じてデータ書き込むホスト書き込み処理と前記コンパクションライト処理とをペアとする処理の進行比率に基づいて前記コンパクション処理を実行する請求項１から５のいずれか１項に記載のメモリ制御装置。
【請求項７】
前記上限値は、
前記進行比率に基づいたホストからの書き込み要求に対する応答上限時間に基づいて設定される値である請求項６に記載のメモリ制御装置。
【請求項８】
前記有効データは有効クラスタ単位であり、
前記データ量単位は論理ページ単位である請求項１から４のいずれか１項に記載のメモリ制御装置。
【請求項９】
ブロックを消去単位とするフラッシュメモリと、
前記フラッシュメモリに対するデータの読み出し、書き込みを実行するリード・ライトコントローラと、
前記フラッシュメモリに対するコンパクション処理を制御するコンパクションコントローラとを具備し、
前記コンパクションコントローラは、
コンパクション処理対象であるコンパクション元ブロックから有効データを検索する検索部と、
前記検索部による検索処理量が上限値を超える場合に、前記検索部の検索処理を中止する検索中止判断部と、
前記リード・ライトコントローラを介して、前記検索部により検索された前記有効データを前記コンパクション元ブロックから読み出すコンパクションリード処理部と、
前記コンパクションリード処理部により読み出された有効データを所定のデータ量単位でコンパクション先ブロックに書き込むコンパクションライト処理部と
を有するデータ記憶装置。
【請求項１０】
前記コンパクションコントローラは、
前記検索中止判断部により前記検索処理が中止されて、前記コンパクション先ブロックに書き込む有効データが前記データ量単位を満たさない場合に、前記データ量単位を満たすようにデータ制御処理を実行するデータ制御処理部を含む請求項９に記載のデータ記憶装置。
【請求項１１】
前記データ制御処理部は、
前記コンパクション元ブロックから読み出された有効データと共に前記データ量単位を満たすだけのダミーデータを追加する請求項１０に記載のデータ記憶装置。
【請求項１２】
前記データ制御処理部は、
前記検索中止判断部により前記検索処理が中止されたときに、前記コンパクション先ブロックに書き込むコンパクションライト処理を中断し、
前記コンパクション元ブロックから読み出される有効データが前記データ量単位を満たすまで有効データをバッファメモリに蓄積する請求項１０に記載のデータ記憶装置。
【請求項１３】
ブロックを消去単位とするフラッシュメモリを有するデータ記憶装置に適用するメモリ制御方法であって、
前記フラッシュメモリに対するコンパクション処理を制御する場合に、コンパクション処理対象であるコンパクション元ブロックから有効データを検索する処理と、
前記検索処理の検索処理量が上限値を超える場合に、前記検索処理を中止する処理と、
前記検索処理により検索された前記有効データを前記コンパクション元ブロックから読み出すコンパクションリード処理と、
前記コンパクションリード処理により読み出された有効データを所定のデータ量単位でコンパクション先ブロックに書き込むコンパクションライト処理と
を実行するメモリ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、不揮発性メモリのメモリ制御装置、データ記憶装置、及びメモリ制御方法に関する。
【背景技術】
【０００２】
近年、データ記憶装置として、書き換え可能な不揮発性メモリであるNAND型フラッシュメモリ（以下、単にフラッシュメモリと表記する場合がある）を使用するＳＳＤ（solid state drive）の開発が推進されている。フラッシュメモリは、データの書き込み単位がページ単位であるのに対して、データの消去単位がブロック単位である。また、書き換え対象の記憶領域に対しては、書き換え前に消去処理が必要となる。
【０００３】
このようなフラッシュメモリの特性から、ＳＳＤでは、フラッシュメモリに対するデータの書き換えが進むと、無効なデータ（最新でないデータ）によりブロック内は有効データを格納できない記憶領域の割合が増大する。このため、ＳＳＤは、ブロック内の記憶領域を有効活用するために、コンパクション（compaction）処理を実行する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−２１１２１９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
コンパクション処理においては、コンパクション元ブロックおよびその有効データ（例えばクラスタ単位）を検索する検索処理時間がＳＳＤの動作性能に大きく影響する。このため、当該検索処理時間を短縮化するための種々の技術が提案されている。
【０００６】
しかしながら、コンパクション元ブロックの中には、有効データが極端に少ない状態（疎密度の状態）のブロックが発生することが起こり得る。このような場合、検索処理時間を短縮化することは困難であり、コンパクション処理の完了までの時間が増大する可能性が高くなる。このため、ＳＳＤは、ホストに対するコマンド応答の上限時間要求（ライトレイテンシ:write latency）を保証できなくなるという課題がある。
【０００７】
本発明の目的は、コンパクション処理の完了までの時間を短縮化し、ホストに対するライトレイテンシを保証できるメモリ制御装置を提供することにある。
【課題を解決するための手段】
【０００８】
実施形態によれば、メモリ制御装置は、リード・ライトコントローラと、コンパクションコントローラとを具備する。リード・ライトコントローラは、ブロックを消去単位とするフラッシュメモリに対するデータの読み出し、書き込みを実行する。コンパクションコントローラは、フラッシュメモリに対するコンパクション処理を制御し、検索部と、検索中止判断部と、コンパクションリード処理部と、コンパクションライト処理部とを含む。検索部は、リード・ライトコントローラにより有効データを読み出す対象であるコンパクション元ブロックから有効データを検索する。検索中止判断部は、検索部による検索処理量が上限値を超える場合に前記検索部の検索処理を中止する。コンパクションリード処理部は、リード・ライトコントローラを介して検索部により検索された有効データをコンパクション元ブロックから読み出す。コンパクションライト処理部は、コンパクションリード処理部により読み出された有効データを所定のデータ量単位でコンパクション先ブロックに書き込む。
【図面の簡単な説明】
【０００９】
【図１】実施形態に関するＳＳＤの構成を説明するためのブロック図。
【図２】実施形態に関するコンパクション処理の概要を説明するための図。
【図３】実施形態に関するコンパクション処理を説明するためのフローチャート。
【図４】実施形態に関するコンパクション処理の進行比率を説明するための図。
【図５】実施形態に関するコンパクション処理を説明するためのフローチャート。
【図６】実施形態の変形例に関するコンパクション処理を説明するためのフローチャート。
【発明を実施するための形態】
【００１０】
以下図面を参照して、実施形態を説明する。
【００１１】
［データ記憶装置の構成］
図１に示すように、実施形態に係るデータ記憶装置は、ＳＳＤ（solid state drive）１であり、データ記憶媒体として不揮発性メモリのNAND型フラッシュメモリ（以下、フラッシュメモリ）６を有する。フラッシュメモリ６は、複数のメモリチップ１００〜１３１がチャネルｃｈ０〜ｃｈ７とバンク（Bank）０〜３と呼ぶ行列構成でグループ化されている。さらに、各メモリチップ１００〜１３１はそれぞれ、複数の物理ブロックから構成されている。物理ブロックは、フラッシュメモリ６内で独立して消去可能な最小の物理的記憶領域単位である。ＳＳＤ１は、ＳＳＤ１の内部で複数の物理ブロックを論理ブロックとして管理する。論理ブロックはＳＳＤ１のデータ消去単位である。本実施形態では、論理ブロックを、単に「ブロック」と称する。
【００１２】
ＳＳＤ１は、フラッシュメモリ６を制御するＳＳＤコントローラ１０を含む。ＳＳＤコントローラ１０は、ホストインターフェース部２と、データバッファ３と、メイン制御部４と、メモリコントローラ５とを有する。
【００１３】
ホストインターフェース部２は、ホストとＳＳＤ１との間で、データ、コマンド、アドレスの転送を制御する。ここで、ホストは、例えばＳＡＴＡ（Serial ATA）規格のインターフェースを含むコンピュータなどである。データバッファ３は、例えばＤＲＡＭ（Dynamic Random Access Memory）、又はＳＲＡＭ(Static Random Access Memory)からなるバッファメモリである。ホストインターフェース部２は、ホストから転送されるデータをデータバッファ３に格納する。また、ホストインターフェース部２は、ホストから転送されるコマンドやアドレスをメイン制御部４に転送する。
【００１４】
データバッファ３は、書き込みバッファ領域（ＷＢ領域）３１とコンパクションバッファ領域（ＣＢ領域）３２とを有する。ＷＢ領域３１は、ホストから転送される書き込みデータ（ユーザデータ）を格納する。ＣＢ領域３２は、後述するコンパクション処理時の書き込みデータ（有効データ）を格納する。なお、データバッファ３は、論理／物理アドレスの変換テーブルを格納する領域を含む場合もある。
【００１５】
メイン制御部４は、例えばマイクロプロセッサ（ＭＰＵ）からなり、ＳＳＤコントローラ１０の全体的制御を実行する。メイン制御部４は、書き込み/読み出しコントローラ４１と、ブロック管理部４２と、コンパクションコントローラ４３とを含む。
【００１６】
書き込み／読み出しコントローラ４１は、ホストインターフェース部２からホストからのリード・ライトコマンドに応じて、読み出し処理と書き込み処理の制御を実行する。また、書き込み／読み出しコントローラ４１は、コンパクションコントローラ４３からのコンパクション処理用のライトコマンドに応じて、フラッシュメモリ６に対して書き込み順序などの書き込み処理の制御を実行する。ブロック管理部４２は、フラッシュメモリ６の各ブロック（ここでは論理ブロック）の有効クラスタを管理するテーブルやフリーブロック（未使用の待機状態ブロック）を管理する管理情報などを有する。
【００１７】
コンパクションコントローラ４３は、後述するコンパクション処理を制御する制御部であり、コンパクション元ブロックの検索処理、ブロック内の有効クラスタの検索処理、有効クラスタ検索カウント処理、有効クラスタ検索処理の中止判定処理及びコンパクションコマンドのリストを生成するなどの処理を実行する。コンパクションコントローラ４３は、有効クラスタ検索処理カウンタ４３1と有効クラスタ打ち切り判定部４３２を備える。コンパクションコマンドは、後述するように、コンパクションリード処理を実行するためのリードコマンド及びコンパクションライト処理をするためのライトコマンドである。
【００１８】
メモリコントローラ５は、チャネルｃｈ０〜ｃｈ７毎の複数のNANDコントローラ５０〜５７を有し、書き込み／読み出しコントローラ４１からのコマンドに応じてフラッシュメモリ６に対する読み出し処理または書き込み処理を実行する。NANDコントローラ５０〜５７はそれぞれ、チャネルｃｈ０〜ｃｈ７毎のメモリチップ１００〜１３１に対して並列に読み出し処理または書き込み処理を実行する。本実施形態では、メモリコントローラ５は、コンパクションコントローラ４３と連携する書き込み／読み出しコントローラ４１からのコマンドに応じて、フラッシュメモリ６に対するコンパクション処理時の読み出し処理（コンパクションリード処理）または書き込み処理（コンパクションライト処理）を実行する。
【００１９】
［コンパクション処理］
先ず、図２を参照してコンパクション処理の基本的概要を説明する。
【００２０】
前述したように、ＳＳＤ１は、フラッシュメモリ６の各ブロックにおいて、有効データの記憶領域が低密度になったブロック内の記憶領域を有効活用するために、コンパクション処理を実行する。
【００２１】
図２に示すように、コンパクションコントローラ４３は、フラッシュメモリ６からコンパクション元ブロック２０Ａ、２０Ｂ（便宜的に２個の論理ブロックとする）を検索するコンパクション元ブロックの検索処理を実行する。コンパクション元ブロックとは、有効データが記録されているアクティブブロックの中で、有効データ（最新データ）の記憶領域が低密度になったコンパクション処理対象ブロックである。
【００２２】
コンパクションコントローラ４３は、ブロック管理部４２からアクティブブロックのリスト情報および各ブロックの有効クラスタを管理するテーブルから、コンパクション元ブロックの候補を設定するための情報を取得する。この場合、コンパクション処理を効果的に行うためには、できるだけ有効クラスタ数の少ない低密度のブロックをコンパクション元ブロックとして検索することが望ましい。
【００２３】
ここで、クラスタ（cluster）は、フラッシュメモリ６からデータを読み出す場合の最小アクセス単位である。各ブロック２０Ａ、２０Ｂは、複数の論理ページ（Ｐ０〜Ｐ２）からなる。各論理ページは複数のクラスタから構成される。有効クラスタはクラスタ単位の有効データである。また、有効クラスタ数（ＣＮ）は、１ブロック内の有効データ量である。
【００２４】
図２に示すように、コンパクションコントローラ４３は有効クラスタを管理するテーブルを参照して、検索されたコンパクション元ブロック２０Ａ、２０Ｂから有効クラスタ２１Ａ，２１Ｂを検索する検索処理を実行する。当該テーブルには、有効クラスタと無効データからなる無効クラスタとを識別するためのログ情報が設定されている。
【００２５】
メモリコントローラ５は、コンパクションコントローラ４３と連携する書き込み／読み出しコントローラ４１からのコマンドに応じて、各コンパクション元ブロック２０Ａ、２０Ｂから有効クラスタ２１Ａ，２１Ｂを読み出すコンパクションリード処理を実行する。さらに、メモリコントローラ５は、各コンパクション元ブロック２０Ａ、２０Ｂから読み出した有効クラスタ２１Ａ，２１Ｂを、コンパクション先ブロック２０Ｃに書き込むコンパクションライト処理を実行する。
【００２６】
コンパクション先ブロック２０Ｃは、ブロック管理部４２で管理されているフリーブロック（書き込み可能な空きブロック）のリストから選出される。以上のようなコンパクション処理により、コンパクション元ブロック２０Ａ、２０Ｂから有効クラスタ（クラスタ単位の有効データ）２１Ａ，２１Ｂを収集して、コンパクション先ブロック２０Ｃに書き直すことになる。この書き直し処理後に、コンパクション元ブロック２０Ａ、２０Ｂに対する消去処理を実行することにより、コンパクション元ブロック２０Ａ、２０Ｂをフリーブロックとして再利用できる。
【００２７】
次に、図３のフローチャート、図４及び図５を参照して、本実施形態のコンパクション処理を具体的に説明する。
【００２８】
先ず、ＳＳＤ１は、ホストからの書き込み要求に応じてフラッシュメモリ６に対するユーザデータの書き込みに伴って、有効データの記憶領域が低密度となる疎密度なブロックが増加すると、フリーブロックを確保するためにコンパクション処理を実行する。
【００２９】
この場合、コンパクションコントローラ４３は、適切なタイミングでコンパクション処理を開始し、コンパクションライト処理を完了する必要がある。書き込み／読み出しコントローラ４１はコンパクションコントローラ４３と連携し、ホストからのライトコマンドによるユーザデータの書き込み処理（以下、ホスト書き込み処理と称す）の合間にコンパクションライト処理を実行する。
【００３０】
この場合、コンパクションコントローラ４３は書き込み／読み出しコントローラ４１に対して、コンパクション処理の進行比率に基づいてコンパクションコマンドを発行する。書き込み／読み出しコントローラ４１は、コンパクションコントローラ４３からのコンパクションコマンドに応じて、ホストからのライトコマンドとスケジューリングした上でコンパクションライト処理を実行するためのライトコマンドを発行し、メモリコントローラ５に出力する。コンパクション処理の進行比率は、ホスト書き込み処理とコンパクションライト処理をペアとした場合に、それらの処理対象の論理ページ数の比率（ギア比：gear rate）である。
【００３１】
具体的には、論理ページ数（論理ページアドレスＰ０〜Ｐ２）の比率とは、図４（Ａ）に示すフリーブロック４０Ａに対するホスト書き込み処理の論理ページ数（１ページ）と、図４（Ｂ）に示すフリーブロック４０Ｂに対するコンパクションライト処理の論理ページ数（Ｎページ、ここではＮ=2）との比率である。書き込み／読み出しコントローラ４１はコンパクションコマンドに応じて、ホスト書き込み処理とコンパクションライト処理の各論理ページ数の比率が例えば１：２になるように、両者のフラッシュメモリ６に対する書込み順序を制御する。
【００３２】
図５に示すように、コンパクションコントローラ４３は、コンパクション元ブロック５０Ａ、５０Ｂ（便宜的に２個の論理ブロックとする）を検索するコンパクション元ブロックの検索処理を実行する。この場合、前述したように、コンパクションコントローラ４３は、ブロック管理部４２からアクティブブロックのリスト情報および各ブロックの有効クラスタを管理するテーブルから、コンパクション元ブロックの候補を設定するための情報を取得する。
【００３３】
次に、図３に示すように、コンパクションコントローラ４３は有効クラスタを管理するテーブルを参照して、検索されたコンパクション元ブロック５０Ａ、５０Ｂから有効クラスタ５１Ａ，５１Ｂを検索する検索処理を開始する（ブロック３００）。
【００３４】
検索処理の開始時に、コンパクションコントローラ４３は、有効クラスタの検索処理用カウンタである有効クラスタ検索処理カウンタ４３１を初期化する。この有効クラスタ検索処理カウンタ４３１は、コンパクションコマンドの発行単位で、有効クラスタ検索処理の検索処理量を測定する。具体的には、検索処理量は、コンパクション元ブロック数、論理ページ数または検索処理時間のいずれかである。この場合、論理ページ数の検索処理量とは、有効クラスタを検索する際の有効クラスタ数を論理ページ数に換算した量である。１論理ページは、例えば２クラスタ分に相当する。ここで、前述したように、コンパクションコマンドの発行は、コンパクション処理の進行比率に基づいて行なわれる。
【００３５】
コンパクションコントローラ４３の有効クラスタ打ち切り判定部４３２は、測定された検索処理量（カウンタ値）と予め設定された上限値とを比較して、検索処理量が上限値を超えているか否かを判定する（ブロック３０１）。ここで、上限値は、例えばホストに対するコマンド応答の上限時間要求（ライトレイテンシ）に基づいて設定される値である。このコマンド応答の上限時間は、前述したようなコンパクション処理の進行比率を前提として設定されている。コンパクションコントローラ４３は、有効クラスタ打ち切り判定部４３２の判定結果が上限値を超えていない場合には、通常のコンパクション処理に移行する（ブロック３０１のＮＯ）。
【００３６】
図５に示すように、コンパクションコントローラ４３は、有効クラスタを管理するテーブルを参照して、検索されたコンパクション元ブロック５０Ａ、５０Ｂから有効クラスタ５１Ａ，５１Ｂを検索する（ブロック３０２）。前述したように、当該テーブルには、有効クラスタと無効データからなる無効クラスタとを識別するためのログ情報が設定されている。コンパクションコントローラ４３の有効クラスタ検索処理カウンタ４３１は、検索した有効クラスタ数（ＣＮ）をカウントし、カウント値（ＣＮ）を例えば内部レジスタに保持する（ブロック３０３のＹＥＳ、３０４）。
【００３７】
次に、コンパクションコントローラ４３は、検出された有効クラスタ５１Ａ，５１Ｂをコンパクション元ブロック５０Ａ、５０Ｂから読み出すコンパクションリード処理を実行する（ブロック３０５）。具体的には、コンパクションコントローラ４３は、検出された有効クラスタ５１Ａ，５１Ｂについて、コンパクションリード処理を要求するコンパクションコマンドを生成する。書き込み／読み出しコントローラ４１は、当該コンパクションコマンドからリードコマンドを発行し、メモリコントローラ５に出力する。これにより、メモリコントローラ５は、各コンパクション元ブロック５０Ａ、５０Ｂから有効クラスタ５１Ａ，５１Ｂを読み出して、データバッファ３のＣＢ領域３２に格納する。
【００３８】
コンパクションコントローラ４３は、コンパクションリード処理により読み出される有効クラスタの有効クラスタ数（ＣＮ）がコンパクション処理の論理ページ単位（ＰＮ）分になるまで（ＣＮ＝ＰＮ）、コンパクションリード処理までの処理を繰り返す（ブロック３０６のＮＯ）。コンパクションコントローラ４３は、ＣＢ領域３２に論理ページに含まれる全クラスタの有効クラスタが格納されると、コンパクションライト処理を要求するコンパクションコマンドを生成する（ブロック３０６のＹＥＳ）。
【００３９】
書き込み／読み出しコントローラ４１は、当該コンパクションコマンドから論理ページ単位でライトコマンドを発行し、メモリコントローラ５に出力する。これにより、メモリコントローラ５は、データバッファ３のＣＢ領域３２から読み出した論理ページに含まれる全クラスタの有効クラスタを、コンパクション先ブロック５０Ｃに書き込むコンパクションライト処理を実行する（ブロック３０７）。具体的には、図５に示すように、例えばＣＢ領域３２内から論理ページに含まれる全クラスタ（論理ページアドレスＰ１）の有効クラスタをコンパクション先ブロック５０Ｃに書き込む。
【００４０】
一方、コンパクションコントローラ４３は、有効クラスタ打ち切り判定部４３２の判定結果によりコンパクションリード処理を含む一連の有効クラスタ検索処理の検索処理量が上限値を超えている場合、当該検索処理を中止する（ブロックブロック３０１のＹＥＳ、３０８）。ここで、前述したように、検索処理量は、例えばコンパクション元ブロック数、論理ページ数または検索処理時間である。
【００４１】
コンパクションコントローラ４３は、検索処理を中止すると、検出された有効クラスタ数が論理ページに含まれる全クラスタに満たない場合は、ダミーデータ（例えばオール０）ＤＤを書き込む（NULL Padding）ためのコンパクションコマンドを生成する（ブロック３１０）。書き込み／読み出しコントローラ４１は、当該コンパクションコマンドに応じて、図５に示すように、論理ページに含まれる全クラスタに満たないＣＢ領域３２の領域５３（論理ページアドレスＰ０）にダミーデータＤＤを書き込む。この後、書き込み／読み出しコントローラ４１は、論理ページ単位でライトコマンドを発行し、メモリコントローラ５に出力する。
【００４２】
メモリコントローラ５は、データバッファ３のＣＢ領域３２から読み出した論理ページに含まれる全クラスタの有効クラスタを、コンパクション先ブロック５０Ｃに書き込むコンパクションライト処理を実行する（ブロック３０７）。具体的には、図５に示すように、例えばＣＢ領域３２内から論理ページに含まれる全クラスタ（論理ページアドレスＰ０）の有効クラスタ及びダミーデータＤＤをコンパクション先ブロック５０Ｃに書き込む。コンパクションコントローラ４３は、コンパクション処理対象の論理ページ数分の処理が完了するまで、一連の処理を繰り返す（ブロック３０９）。
【００４３】
以上のようにして本実施形態によれば、コンパクション元ブロックから有効クラスタを収集して、コンパクション先ブロックに書き直すコンパクション処理を実行することができる。このため、コンパクション元ブロックを消去することにより、書き込み可能なフリーブロックを増加することができる。
【００４４】
さらに、本実施形態のコンパクション処理であれば、有効クラスタ検索処理を実行している場合に、例えば検索処理時間が上限値を超えると、当該検索処理を中止する。上限値はホストに対するコマンド応答上限時間に基づいて設定されるため、検索処理時間を制限することにより、その要求（ライトレイテンシ）を保証できることになる。この場合、検索処理を中止すると、コンパクションリード処理により読み出された有効クラスタ数が論理ページに含まれる全クラスタに満たない状態が発生することがある。本実施形態では、論理ページに含まれる全クラスタに満たない容量だけダミーデータＤＤを書き込む（NULL Padding）ことにより、コンパクション先ブロックに書き直すコンパクション処理を確実に完了することができる。
【００４５】
なお、本実施形態において、コンパクション元ブロックから有効データを検索する場合、有効クラスタ単位での検索処理が行われるが、これに限ることなく、例えば論理ページ単位でもよい。
【００４６】
［変形例］
図６は、本実施形態の変形例に関するコンパクション処理を説明するためのフローチャートである。本変形例においても、ＳＳＤ１の構成は図１に示すものと同様であるため、詳細な説明を省略する。
【００４７】
本変形例は、検索処理を中止した場合に、ダミーデータＤＤを書き込む処理を含むコンパクションライト処理を実行せずに、コンパクションリード処理により読み出された有効クラスタ数が論理ページに含まれる全クラスタまでデータバッファ３のＣＢ領域３２に格納するまで待機する処理方法である。以下、図６のフローチャートを参照して具体的に説明する。
【００４８】
先ず、ブロック６００〜６０５までの処理は、図３に示す３００〜３０５までの処理と同様である。即ち、コンパクションコントローラ４３は、検索されたコンパクション元ブロックから有効クラスタを検索する検索処理を開始する（ブロック６００）。コンパクションコントローラ４３は、測定された検索処理量（カウンタ値）と予め設定された上限値とを比較して、検索処理量が上限値を超えているか否かを判定する（ブロック６０１）。コンパクションコントローラ４３は、判定結果が上限値を超えていない場合には、通常のコンパクション処理に移行する（ブロック６０１のＮＯ）。
【００４９】
コンパクションコントローラ４３は、検索されたコンパクション元ブロックから有効クラスタを検索する（ブロック６０２）。コンパクションコントローラ４３は、検索した有効クラスタ数（ＣＮ）をカウントし、カウント値（ＣＮ）を例えば内部レジスタに保持する（ブロック６０３のＹＥＳ、６０４）。次に、コンパクションコントローラ４３は、検出された有効クラスタをコンパクション元ブロックから読み出すコンパクションリード処理を実行する（ブロック６０５）。
【００５０】
即ち、メモリコントローラ５は、各コンパクション元ブロックから有効クラスタを読み出して、データバッファ３のＣＢ領域３２に格納する（ブロック６０６）。コンパクションコントローラ４３は、コンパクションリード処理により読み出される有効クラスタの有効クラスタ数（ＣＮ）がコンパクション処理の論理ページ単位（ＰＮ）分になるまで（ＣＮ＝ＰＮ）、コンパクションリード処理までの処理を繰り返す（ブロック６０７のＮＯ）。コンパクションコントローラ４３は、ＣＢ領域３２に論理ページに含まれる全クラスタの有効クラスタが格納されると、コンパクションライト処理を要求するコンパクションコマンドを生成する（ブロック６０７のＹＥＳ）。メモリコントローラ５は、データバッファ３のＣＢ領域３２から読み出した論理ページに含まれる全クラスタの有効クラスタを、コンパクション先ブロック５０Ｃに書き込むコンパクションライト処理を実行する（ブロック３０７）。
【００５１】
一方、コンパクションコントローラ４３は、有効クラスタ検索処理の検索処理量が上限値を超えている場合、当該検索処理を中止する（ブロックブロック６０１のＹＥＳ、６０９）。ここで、コンパクションコントローラ４３は、検索処理を中止すると、コンパクションライト処理を実行しない。この場合、ＳＳＤコントローラ１０は、ホスト書き込み処理を先行して実行する。これにより、ＳＳＤ１のデータ書き込み性能を保証することが可能である。コンパクションコントローラ４３は、コンパクション処理対象の論理ページ数分の処理が完了するまで、一連の処理を繰り返す（ブロック６１０）。
【００５２】
この場合、コンパクションリード処理により、ＣＢ領域３２には読み出された有効クラスタが蓄積される（ブロック６０６）。コンパクションコントローラ４３は、ＣＢ領域３２に論理ページに含まれる全クラスタの有効クラスタが格納されると、コンパクションライト処理を要求するコンパクションコマンドを生成する（ブロック６０７のＹＥＳ）。これにより、メモリコントローラ５は、データバッファ３のＣＢ領域３２から読み出した論理ページに含まれる全クラスタの有効クラスタを、コンパクション先ブロックに書き込むコンパクションライト処理を実行する。従って、検索処理を中止した場合に、コンパクションリード処理により有効クラスタが論理ページに含まれる全クラスタまでＣＢ領域３２に格納されるまで待機することにより、コンパクション先ブロックに書き直すコンパクション処理を確実に完了することができる。
【００５３】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００５４】
１…ＳＳＤ（solid state drive）、２…ホストインターフェース部
３…データバッファ、４…メイン制御部、５…メモリコントローラ
６…NAND型フラッシュメモリ（フラッシュメモリ）
３１…書き込みバッファ領域（ＷＢ領域）
３２…コンパクションバッファ領域（ＣＢ領域）
４１…書き込み／読み出しコントローラ
４２…ブロック管理部、４３…コンパクションコントローラ
【図１】
2013196646.tif 000003
【図２】
2013196646.tif 000004
【図３】
2013196646.tif 000005
【図４】
2013196646.tif 000006
【図５】
2013196646.tif 000007
【図６】
2013196646.tif 000008