"ブロックをデータ消去単位とするフラッシュメモリと、前記フラッシュメモリに対するコンパクション処理を実行するコントローラとを具備し、前記コントローラは、使用可能なブロック数及びブロック内の有効データ量に基づいてコンパクション処理対象範囲を動的に設定し、前記コンパクション処理対象範囲から前記コンパクション処理の対象ブロックとして相対的に有効データ量が少ないブロックを検索するコンパクション処理手段を有するデータ記憶装置。前記コンパクション処理手段は、前記コンパクション処理の対象ブロックを検索する条件としてブロック内の有効データ量の閾値を算出し、前記フラッシュメモリの使用可能なブロック数の変動に応じて前記閾値を更新した最新の閾値を算出する閾値算出手段と、前記閾値算出手段から取得した前記最新の閾値に基づいて相対的に有効データ量が少ないブロックを決定し、前記コンパクション処理の対象ブロックとして検索する検索手段とを含む請求項1に記載のデータ記憶装置。前記閾値算出手段は、前記使用可能なブロック数の割合を示す余裕率と前記閾値を算出するための有効データ密度とを対応付けしたテーブル情報を有し、前記テーブル情報を参照し、前記余裕率の変動に応じた前記有効データ密度から前記最新の閾値を算出する請求項2に記載のデータ記憶装置。前記閾値算出手段は、前記閾値を記憶するメモリ手段を有し、前記メモリ手段に記憶した閾値を前記余裕率の変動に応じて更新し、前記検索手段は、前記閾値算出手段から前記メモリ手段に記憶されている最新の閾値を取得し、前記最新の閾値に基づいて前記コンパクション処理の対象ブロックを検索する請求項3に記載のデータ記憶装置。前記閾値算出手段は、前記フラッシュメモリの使用可能なブロック群の平均有効データ量を算出し、当該平均値に基づいて前記最新の閾値を算出する請求項2から請求項4のいずれか1項に記載のデータ記憶装置。前記検索手段は、前記最新の閾値より小さい有効データ量の各ブロックの中で、前記有効データ量の小さい順に所定数のブロックを、前記コンパクション処理の対象ブロックとして選定する請求項2から請求項5のいずれか1項に記載のデータ記憶装置。前記コントローラは、前記コンパクション処理手段により検索されたコンパクション処理の対象ブロックに対して前記コンパクション処理を実行するコンパクション処理実行手段を有し、前記コンパクション処理実行手段は、前記コンパクション処理の対象ブロックから有効データを検索し、前記有効データを他のブロックに書き直す請求項1から請求項6のいずれか1項に記載のデータ記憶装置。前記コンパクション処理実行手段による前記コンパクション処理の完了後に、前記コンパクション処理の対象ブロックを消去処理する手段と、前記消去処理後の対象ブロックをフリーブロックとして管理するブロック管理手段を有する請求項7に記載のデータ記憶装置。ブロックをデータ消去単位とするフラッシュメモリを使用するデータ記憶装置に適用するメモリ制御装置であって、前記フラッシュメモリに対するコンパクション処理を実行するコントローラを具備し、前記コントローラは、使用可能なブロック数及びブロック内の有効データ量に基づいてコンパクション処理対象範囲を動的に設定し、前記コンパクション処理対象範囲から前記コンパクション処理の対象ブロックとして相対的に有効データ量が少ないブロックを検索するコンパクション処理手段を有するメモリ制御装置。前記コンパクション処理手段は、前記コンパクション処理の対象ブロックを検索する条件としてブロック内の有効データ量の閾値を算出し、前記フラッシュメモリの使用可能なブロック数の変動に応じて前記閾値を更新した最新の閾値を算出する閾値算出手段と、前記閾値算出手段から取得した前記最新の閾値に基づいて相対的に有効データ量が少ないブロックを決定し、前記コンパクション処理の対象ブロックとして検索する検索手段とを含む請求項9に記載のメモリ制御装置。ブロックをデータ消去単位とするフラッシュメモリ及び前記フラッシュメモリに対するコンパクション処理を実行するコントローラを含むデータ記憶装置に適用するメモリ制御方法であって、前記コントローラは、使用可能なブロック数及びブロック内の有効データ量に基づいてコンパクション処理対象範囲を動的に設定し、前記コンパクション処理対象範囲から前記コンパクション処理の対象ブロックとして相対的に有効データ量が少ないブロックを検索するメモリ制御方法。コンパクション処理を効果的に行うためには、コンパクション対象ブロックとして、より低密度のブロックを検索することが重要である。コンパクション対象ブロックの検索処理は、コンパクション処理の性能に大きく影響する。従来、有効トラック数別に全ブロックIDを分類する管理テーブルを用いた検索方法が提案されているが、管理テーブルの専用メモリ領域が多く必要となるなど、必ずしも有効な検索処理ではない。本発明の目的は、有効なコンパクション対象ブロックの検索処理を実現することで、コンパクション処理の効率化を図ることができるデータ記憶装置を提供することにある。実施形態によれば、データ記憶装置は、ブロックをデータ消去単位とするフラッシュメモリとコントローラとを具備する。前記コントローラは、前記フラッシュメモリに対するコンパクション処理を実行し、使用可能なブロック数及びブロック内の有効データ量に基づいてコンパクション処理対象範囲を動的に設定し、前記コンパクション処理対象範囲から前記コンパクション処理の対象ブロックとして相対的に有効データ量が少ないブロックを検索するコンパクション処理手段を有する。以下図面を参照して、実施形態を説明する。[データ記憶装置の構成]図1は、実施形態に係るデータ記憶装置の構成を示すブロック図である。図1に示すように、データ記憶装置はSSDsolidstatedriveであり、SSDコントローラ10と、不揮発性メモリのNAND型フラッシュメモリ以下、フラッシュメモリ11とを有する。フラッシュメモリ11はSSDのデータ記憶媒体であり、例えばチャネル単位またはパッケージ単位での外付け接続が可能である。SSDコントローラ10は、フラッシュメモリコントローラ12と、ホストインターフェースホストI/F13と、バッファ管理モジュール14と、バッファメモリDRAM15と、マイクロプロセッサCPU16とを有する。CPU16は、SSDコントローラ10の全体的制御を実行する。DRAM15は、バッファメモリとして動作し、論理/物理アドレスの変換テーブルやホストシステム1から転送されるデータなどを保持する。ホストI/F13は、ホストシステム1とSSDコントローラ10との間で、データ、コマンド、アドレスの転送を制御する。ホストシステム1は、例えばSATASerialATA規格のインターフェースを含むコンピュータなどである。バッファ管理モジュール14はバッファメモリDRAM15を制御し、ホストI/F13とバッファメモリ15間のデータ転送を制御する。また、バッファ管理モジュール14は、フラッシュメモリコントローラ12とバッファメモリ15間のデータ転送を制御する。フラッシュメモリコントローラ12は、入出力インターフェース単にインターフェース20と、メモリアクセスコントローラ21とを含む。インターフェース20は、フラッシュメモリ11とメモリアクセスコントローラ21との間でのデータの入出力、及びフラッシュメモリ11とコンパクションモジュール24との間でのデータの入出力を行なう。メモリアクセスコントローラ21は、インターフェース20を介してフラッシュメモリ11に対するデータの読み出し動作及び書き込み動作を制御する。メモリアクセスコントローラ21は、コントローラ22と、ブロック管理モジュール23と、コンパクションモジュール24とを含む。コントローラ22は、内部バスを介して接続されたブロック管理モジュール23及びコンパクションモジュール24などの各モジュールの動作を制御する。ブロック管理モジュール23は、各ブロックの有効クラスタを管理するテーブルや、フリーブロック未使用の待機状態ブロックなどを管理する管理情報を有し、フラッシュメモリ11の各ブロックを管理する。コンパクションモジュールコンパクションモジュール24は、図2に示すように、ブロック検索モジュール30と、有効クラスタ数閾値算出モジュール以下、閾値算出モジュールと略する場合がある31と、コンパクションブロックリスト管理モジュール以下、ブロックリスト管理モジュールと略する場合がある32と、クラスタ検索モジュール33と、コマンドリスト生成モジュール34と、コマンドリスト投入モジュール35とを有する。ブロック検索モジュール30は、有効データが記録されているアクティブブロック群から、コンパクション対象ブロックの候補を検索する。閾値算出モジュール31は、ブロック検索モジュール30が実行するブロック検索処理での条件として利用する有効クラスタ数の閾値有効クラスタ数閾値と呼ぶを算出する。ブロックリスト管理モジュール32は、コンパクション対象ブロックの候補およびコンパクション処理中のブロックを、それぞれリスト構造により管理する。クラスタ検索モジュール33は、ブロックリスト管理モジュール32により管理されているリスト内で、コンパクション処理中の各ブロックについてリード可能な最小単位であるクラスタ単位での有効データまたは無効データのいずれであるかを判定する。クラスタ検索モジュール33は、クラスタ単位での有効データである有効クラスタを検索する。コマンドリスト生成モジュール34は、クラスタ検索モジュール33により検索された有効クラスタについて、コンパクション処理の要求コマンドコンパクション要求コマンドセットを生成する。コマンドリスト投入モジュール35は、コマンドリスト生成モジュール34から受け取ったコンパクション要求コマンドを、インタフェース20に投入する。これにより、フラッシュメモリ11に対するコンパクション処理が実行される。[コンパクション処理]以下、図3、及び図4から図6のフローチャートを参照して、本実施形態のコンパクション処理を説明する。SSDは、後述するように、ブロック内の記憶領域を有効活用するためにコンパクション処理を実行する図6を参照。本実施形態のコンパクションモジュール24では、図2に示すように、各モジュール30~35が連携して、コンパクション処理を高速かつ効率的に実行する。まず、ブロック検索モジュール30は、図5のフローチャートに示すように、有効データが記録されているアクティブブロック群から、コンパクション対象ブロックの候補を検索する。この場合、コンパクション処理を効果的に行うためには、できるだけ有効クラスタ数の少ない低密度のブロックをコンパクション対象ブロックとして検索する必要がある。ここで、クラスタclusterは、フラッシュメモリ11からデータを読み出す場合の最小アクセス単位である。1クラスタは、例えば1物理ページの半分に対応するデータ量である。マルチチャネル構成のSSDの場合、チャネル数×プレーンplane数の物理ページから論理ページが構成される。従って、有効クラスタはクラスタ単位の有効データである。また、有効クラスタ数CNは、1ブロック内の有効データ量である。ブロック検索モジュール30は、後述するように、コンパクション対象ブロックの候補を検索する場合の条件として、有効クラスタ数CNに係る閾値有効クラスタ数閾値THを使用する。有効クラスタ数閾値THは、閾値算出モジュール31により算出される。以下、図4のフローチャートを参照して、閾値算出モジュール31の処理を説明する。閾値算出モジュール31は、図3に示すように、有効クラスタ数閾値を管理する管理テーブル100を有する。管理テーブル100は、フラッシュメモリ11の記憶容量の余裕率Mと有効クラスタ密度CDとが対応付けられている。余裕率Mは、装置表記容量に対して実際に使用可能な記憶容量の割合である。閾値算出モジュール31は、使用不可のブロックBB:BadBlockの発生したタイミングで、ブロック管理モジュール23からその発生通知を受け付けるブロック400。閾値算出モジュール31は、その発生通知を受け付けると、記憶容量の余裕率Mを算出再計算するブロック401。ここで、余裕率Mは、数式M=MC÷TC×100により算出される。MCは余裕容量であり、ユーザデータの記憶に利用可能な全記憶容量からTCを差し引いた容量である。TCは、フラッシュメモリ11の装置表記容量である。さらに、閾値算出モジュール31は、管理テーブル100を参照して、算出した余裕率Mに対応する有効クラスタ密度CDを算出するブロック402。ここで、1クラスタは、例えば1ページ物理ページの半分に対応するデータ量である。また、1論理ページは例えば32物理ページから構成され、1ブロックは例えば64論理ページ分のデータ量である。これらの関係から、余裕率Mと有効クラスタ密度CDとが対応付けられた情報が、管理テーブル100として予め作成されている。次に、閾値算出モジュール31は、管理テーブル100から算出した有効クラスタ密度CDから有効クラスタ数閾値THを算出するブロック403。有効クラスタ数閾値THは、数式TH=TN×CDにより算出される。TNは、論理ブロックの総クラスタ数である。閾値算出モジュール31は、算出した有効クラスタ数閾値THを内部メモリに記憶する。閾値算出モジュール31は、内部メモリに記憶した前の有効クラスタ数閾値THと、今回算出した現在値とを比較するブロック404。閾値算出モジュール31は、閾値が変化している場合には、内部メモリの既存値を有効クラスタ数閾値THの現在値最新値に更新するブロック405。要するに、閾値算出モジュール31は、フラッシュメモリ11の余裕率の変動に応じて管理テーブル100から対応する有効クラスタ密度CDを求めて、この有効クラスタ密度CDから最新の有効クラスタ数閾値THを算出する。閾値算出モジュール31は、内部メモリの既存値を最新の有効クラスタ数閾値THに更新する。なお、閾値算出モジュール31は、アクティブブロック群の平均有効クラスタ数を算出し、その平均値に基づいて最新の有効クラスタ数閾値THを算出し、内部メモリに記憶してもよい。次に、ブロック検索モジュール30は、図5のフローチャートに示すように、閾値算出モジュール31の内部メモリに格納されている最新の有効クラスタ数閾値THを取得するブロック500。さらに、ブロック検索モジュール30は、各アクティブブロック有効データが記録されているブロックから、有効クラスタ数CNを取得するブロック501。この場合、ブロックモジュール30は、ブロック管理モジュール23から各アクティブブロック毎の有効クラスタ数CNを取得する。ブロック検索モジュール30は、取得した有効クラスタ数CNが0であるブロックを検索すると、当該ブロックをフリーブロック未使用の待機状態ブロックとして解放するための通知をブロック管理モジュール23に行なうブロック502のYES,505。コントローラ21は、当該ブロックに対する消去処理を実行する。ブロック管理モジュール23は、消去処理後のブロックをフリーブロックとして登録する。一方、ブロック検索モジュール30は、有効クラスタ数CNが0でないブロックの場合には、有効クラスタ数CNと有効クラスタ数閾値THとを比較するブロック503。ブロック検索モジュール30は、有効クラスタ数CNが閾値THより少ない場合には、当該有効クラスタ数CNのブロックをコンパクション対象ブロックとして候補リストに登録するブロック504。ブロック検索モジュール30は、所定範囲のアクティブブロックに対する検索処理を繰り返し、閾値THより少ない有効クラスタ数CNのブロックを候補リストに追加していくブロック506。ここで、ブロック検索モジュール30は、有効クラスタ数CNが閾値THより少ないブロックの中で、有効クラスタ数CNの少ない順に所定数のブロックをコンパクション対象ブロックとして選定してもよい。ブロックリスト管理モジュール32は、コンパクション対象ブロックの候補およびコンパクション処理中のブロックを、それぞれリスト構造により管理する。具体的には、ブロックリスト管理モジュール32は、ブロック検索モジュール30により選出されたブロック群のブロックID識別情報をコンパクション対象ブロックの候補としてリスト構造で管理する。なお、ブロックリスト管理モジュール32は、コンパクション対象ブロックの候補リストとしては、目的に応じて例えば3種類のリストを有し、コンパクション対象ブロックを管理する。1種類目のリストは、通常のコンパクション処理用で、選出されたブロックのブロックIDを管理するためのものである。即ち、通常のコンパクション処理では、コントローラ22は、ブロック管理モジュール23により管理しているフリーブロック数を確認し、それが規定数以下であればフリーブロックの枯渇状態を回避するために、ブロック検索モジュール30に対してコンパクション対象ブロックの検索処理を開始させる。また、2種類目のリストは、エラー修復目的のコンパクション処理用である。例えば、コントローラ22は、定期的にリード確認を行い、エラービットが規定値以上多くなったブロックの場合に、退避の目的で当該ブロック内のデータを他のブロックに移動する処理に使用する。このようなコンパクション処理は、パトロールリフレッシュ処理と呼ばれることがある。3種類目のリストは、フラッシュメモリ11の延命のためのウェアレベリングwearleveling目的のコンパクション処理用である。フラッシュメモリ11の寿命は、ブロックの消去回数および消去時間間隔に依存するため、ブロックの疲弊度を平準化する必要がある。このコンパクション処理は、図示しないウェアレベリングモジュールにより、ウェアレベリングが必要と判定された場合に開始される。ブロックリスト管理モジュール32は、コンパクション対象ブロックの候補リストから各目的に応じて優先順位をつけ、コンパクション処理中にコンパクション対象ブロックのリストを生成する。以下、図6のフローチャートを参照して、コンパクション処理を具体的に説明する。クラスタ検索モジュール33は、ブロックリスト管理モジュール32により管理されているリスト内で、各コンパクション対象ブロックについてクラスタ単位での有効データまたは無効データのいずれであるかを判定し、有効データである有効クラスタを検索するブロック600。コマンドリスト生成モジュール34は、クラスタ検索モジュール33により検索された有効クラスタについて、コンパクション処理の要求コマンドコンパクション要求コマンドセットを生成するブロック601。コマンドリスト投入モジュール35は、コマンドリスト生成モジュール34から受け取ったコンパクション要求コマンドを、インターフェース20に投入するブロック602,603。これにより、フラッシュメモリ11に対するコンパクション処理が実行されるブロック604。ここで、コンパクション要求コマンドとは、コンパクション対象ブロックから有効クラスタをリードし、別のブロックに書き直すためのコマンドである。本実施形態では、コマンドリスト生成モジュール34は、ライト可能な最小単位であるページ単位でまとめてコマンド発行を行うものとする。マルチチャネル構成のSSDの場合、例えば、チャネル数-Parity用チャネル-移動先ブロックのNULLブロック数×プレーンplane数×ページ当たりのクラスタ数のクラスタ数個分のコマンドを1セットとして生成する。コンパクション処理が完了すると、コントローラ21は、コンパクション対象ブロックに対する消去処理を実行する。ブロック管理モジュール23は、消去処理後のブロックをフリーブロックとして登録するためのリストを生成するブロック606。以上のように本実施形態によれば、コンパクション処理の実行時にコンパクション対象ブロックを検索する場合に、有効クラスタの少ない低密度ブロックを有効クラスタ数閾値に基づいて判定する。この有効クラスタ数閾値は、フラッシュメモリ11のメモリ容量の余裕率の変動に応じて最新の閾値として更新される。このような本実施形態の検索方法であれば、コンパクション対象ブロックを高速かつ効率的に検索することが可能となり、結果としてコンパクション処理時間の短縮化を実現することができる。即ち、コンパクション対象ブロックを検索する場合に、できるだけ低密度のブロック検索を実現するためには、有効クラスタ数閾値が小さいことが望ましい。しかし一方で、フラッシュメモリ11の余裕率が減少すると、コンパクション対象ブロックの候補を検索することが困難となる。また逆に、余裕をもたせて有効クラスタ数閾値を予め大きめの値に設定した場合には、コンパクション処理の効率が低下する。従って、本実施形態であれば、有効クラスタ数閾値を余裕率の変動に応じて更新することにより、コンパクション対象ブロックを高速かつ効率的に検索することが可能となる。また、コンパクション対象ブロックの検索処理に要する専用メモリ領域として、閾値算出モジュール31が有する有効クラスタ数閾値テーブル及び閾値を記憶するメモリ領域だけである。このため、専用メモリ領域を最小限にすることが可能である。要するに、本実施形態であれば、最小限の専用メモリ領域で、フラッシュメモリの使用状態余裕率に適した効果的なコンパクション対象ブロックの検索処理を実現できる。本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。"