(57)【特許請求の範囲】
【請求項１】
記憶領域を提供するフラッシュメモリと、前記記憶領域に対するデータの書き込み及び読み出しを制御するコントローラと、前記記憶領域に書き込むデータを一時的に記憶するバッファメモリと、を含むストレージ装置であって、
前記コントローラは、
前記フラッシュメモリへのアクセス性能に基づいて、第１可逆圧縮方式と第２可逆圧縮方式の一方を選択し、
前記選択した一方によってデータを圧縮して前記記憶領域に書き込むことを決定し、
前記第１可逆圧縮方式は、前記第２可逆圧縮方式より圧縮率が小さく、かつ前記第２可逆圧縮方式より圧縮速度が低く、
前記記憶領域へのデータの書き込み要求を受信し、
前記書き込み要求の受信時における前記バッファメモリの空き領域の大きさに基づいて、前記一方を選択する、ストレージ装置。
【請求項２】
請求項１に記載のストレージ装置であって、
前記コントローラは、前記バッファメモリの空き領域が大きいほど、前記第１可逆圧縮方式を高い割合で前記一方として選択する、ストレージ装置。
【請求項３】
請求項１に記載のストレージ装置であって、
前記コントローラは、
前記バッファメモリの空きエントリ数が所定値以上の場合、第１割合で前記第１可逆圧縮方式を前記一方として選択し、
前記第１割合に前記第１可逆圧縮方式の圧縮速度を掛けた積と、１から前記第１割合を引いた差に前記第２可逆圧縮方式の圧縮速度を掛けた積と、の和は、所定の目標書き込み速度を超えている、ストレージ装置。
【請求項４】
記憶領域を提供するフラッシュメモリと、前記記憶領域に対するデータの書き込み及び読み出しを制御するコントローラと、前記記憶領域に書き込むデータを一時的に記憶するバッファメモリと、を含むストレージ装置であって、
前記コントローラは、
前記フラッシュメモリへのアクセス性能に基づいて、第１可逆圧縮方式と第２可逆圧縮方式の一方を選択し、
前記選択した一方によってデータを圧縮して前記記憶領域に書き込むことを決定し、
前記第１可逆圧縮方式は、前記第２可逆圧縮方式より圧縮率が小さく、かつ前記第２可逆圧縮方式より圧縮速度が低く、
前記記憶領域は、前記第１可逆圧縮方式又は前記第２可逆圧縮方式の一方で圧縮された第１データを保持し、
前記第１可逆圧縮方式は、前記第２可逆圧縮方式より伸張速度が低く、
前記コントローラは、
前記記憶領域に格納されたデータを読み出す速度に基づいて、前記第１データを前記記憶領域から読み出して伸張し他方で圧縮して前記記憶領域に格納する圧縮方式変更、を行うか否かを決定する、ストレージ装置。
【請求項５】
請求項４に記載のストレージ装置であって、
前記コントローラは、
前記記憶領域に格納されたデータを読み出す平均速度が所定の目標読み出し速度以上であるか否かの判定を実行し、
前記判定の結果に基づいて、前記圧縮方式変更を行うか否かを決定する、ストレージ装置。
【請求項６】
請求項５に記載のストレージ装置であって、
前記一方は、前記第２可逆圧縮方式であり、
前記コントローラは、前記判定において前記平均速度が前記目標読み出し速度以上であると判定した場合、前記圧縮方式変更を行う、ストレージ装置。
【請求項７】
請求項５に記載のストレージ装置であって、
前記一方は、前記第１可逆圧縮方式であり、
前記コントローラは、前記判定において前記平均速度が前記目標読み出し速度未満であると判定した場合、
前記圧縮方式変更を行った場合における伸張速度の改善度及び圧縮率の悪化度に基づいて、前記圧縮方式変更を行うか否かを決定する、ストレージ装置。
【請求項８】
請求項４に記載のストレージ装置であって、
前記コントローラは、
前記第１データの他の記憶領域への移動の際に前記圧縮方式変更を行うか否かを決定し、
前記圧縮方式変更を行うと決定した場合、前記移動の実行時に前記圧縮方式変更を行う、ストレージ装置。
【請求項９】
請求項８に記載のストレージ装置であって、
前記コントローラは、
前記第１データが記憶された記憶領域に対するリフレッシュ又はリクラメーションが実行される際に、前記圧縮方式変更を行うか否かを決定し、
前記圧縮方式変更を行うと決定した場合、前記リフレッシュ又は前記リクラメーションの実行時に前記圧縮方式変更を行う、ストレージ装置。
【請求項１０】
記憶領域を提供するフラッシュメモリと、前記記憶領域に書き込むデータを一時的に記憶するバッファメモリと、を含むストレージ装置、の制御方法であって、
前記フラッシュメモリへのアクセス性能に基づいて、第１可逆圧縮方式と第２可逆圧縮方式の一方を選択し、
前記選択した一方によってデータを圧縮して前記記憶領域に書き込むことを決定し、
前記第１可逆圧縮方式は、前記第２可逆圧縮方式より圧縮率が小さく、かつ前記第２可逆圧縮方式より圧縮速度が低く、
前記記憶領域へのデータの書き込み要求を受信し、
前記書き込み要求の受信時における前記バッファメモリの空き領域の大きさに基づいて、前記一方を選択する、制御方法。
【請求項１１】
請求項１０に記載の制御方法であって、
前記バッファメモリの空き領域が大きいほど、前記第１可逆圧縮方式を高い割合で前記一方として選択する、制御方法。
【請求項１２】
請求項１０に記載の制御方法であって、
前記バッファメモリの空きエントリ数が所定値以上の場合、第１割合で前記第１可逆圧縮方式を前記一方として選択し、
前記第１割合に前記第１可逆圧縮方式の圧縮速度を掛けた積と、１から前記第１割合を引いた差に前記第２可逆圧縮方式の圧縮速度を掛けた積と、の和は、所定の目標書き込み速度を超えている、制御方法。
【請求項１３】
記憶領域を提供するフラッシュメモリと、前記記憶領域に書き込むデータを一時的に記憶するバッファメモリと、を含むストレージ装置、の制御方法であって、
前記フラッシュメモリへのアクセス性能に基づいて、第１可逆圧縮方式と第２可逆圧縮方式の一方を選択し、
前記選択した一方によってデータを圧縮して前記記憶領域に書き込むことを決定し、
前記第１可逆圧縮方式は、前記第２可逆圧縮方式より圧縮率が小さく、かつ前記第２可逆圧縮方式より圧縮速度が低く、
前記記憶領域は、前記第１可逆圧縮方式又は前記第２可逆圧縮方式の一方で圧縮された第１データを保持し、
前記第１可逆圧縮方式は、前記第２可逆圧縮方式より伸張速度が低く、
前記制御方法は、前記記憶領域に格納されたデータを読み出す速度に基づいて、前記第１データを前記記憶領域から読み出して伸張し他方で圧縮して前記記憶領域に格納する圧縮方式変更、を行うか否かを決定する、制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージ装置及びストレージ装置の制御方法に関する。
【背景技術】
【０００２】
従来、例えば、磁気ディスクや光ディスク等のランダムアクセスが可能な不揮発性記憶媒体がストレージ装置のデータ記憶媒体として用いられている。特に最近では、小型ディスクドライブを多数備えるストレージ装置が主流となっている。【０００３】
また、近年の半導体技術の進歩に伴って、一括消去可能な不揮発性半導体メモリが開発されている。このような不揮発性半導体メモリとしては、例えば、フラッシュメモリを例示できる。フラッシュメモリを記憶媒体とするストレージ装置は、小型ディスクドライブを多数備えるストレージ装置に比べて、省電力であったり、アクセス時間等が高速であったりすると考えられている。【０００４】
一方、フラッシュメモリブロックの消去回数には限度（寿命）がある。寿命に達したブロックは消去に失敗し、以後の消去ができなくなる。そのブロック内のページは未書き込みページにすることができない。すなわち、寿命到達ブロック数が増えるにつれて、未書込みページの枯渇が解消できなくなり、いずれストレージ装置は使用不能となる。【０００５】
フラッシュメモリを長期間使用できるようにするには、フラッシュメモリのブロック消去頻度を低減させ、寿命到達を遅らせる必要がある。つまり、未書き込みページが消費される速度を低下するために、フラッシュメモリに書くべきデータ量を削減することが求められる。【０００６】
本技術分野の背景技術として国際公開第２０１５／１２８９５５号がある。この公報には、「記憶デバイスは、複数の論理領域で構成された記憶媒体に基づく論理空間を上位装置に提供し、各論理領域について、基準データ範囲が記憶媒体に存在する。記憶デバイスは、ライト先論理アドレスが属するライト先論理領域に対応した基準データ範囲から基準データをリードし、基準データである第１データと、ライトデータに基づくデータとライトデータとのいずれかである第２データとの排他的論理和である差分データを作成する。記憶デバイスは、差分データを圧縮することにより圧縮差分データを作成し、圧縮差分データを記憶媒体にライトし、圧縮差分データがライトされた範囲である差分データ範囲をライト先論理領域に関連付ける。」と記載されている（要約参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】国際公開第２０１５／１２８９５５号
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１に記載の技術のようにデータ圧縮する技術においては、できるだけ圧縮率（圧縮後サイズを圧縮前サイズで割った値）を小さくできることが望ましい。圧縮率が小さいほどフラッシュメモリへの格納データ量を削減することができるからである。しかし、圧縮率を小さくできる圧縮方式は、圧縮しにくいデータに対して、圧縮処理や伸張処理の速度が遅くなる問題がある。圧縮処理や伸張処理の速度が遅くなると、ストレージ装置のライト性能やリード性能も遅くなる。そのため、特許文献１に記載の技術のように、従来は、どのようなデータに対しても圧縮処理や伸張処理の速度が十分速い代わりに圧縮率が比較的大きくなる圧縮方式を適用していた。【０００９】
そこで、本発明の一態様は、フラッシュメモリへのデータ書き込み速度及びフラッシュメモリからのデータ読み出し速度を保証しつつ、フラッシュメモリが保持するデータの圧縮率を小さくし、ひいてはフラッシュメモリの長寿命化を図ることを目的とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するために本発明の一態様は以下の構成を採用する。記憶領域を提供するフラッシュメモリと、前記記憶領域に対するデータの書き込み及び読み出しを制御するコントローラと、前記記憶領域に書き込むデータを一時的に記憶するバッファメモリと、を含むストレージ装置であって、前記コントローラは、前記フラッシュメモリへのアクセス性能に基づいて、第１可逆圧縮方式と第２可逆圧縮方式の一方を選択し、前記選択した一方によってデータを圧縮して前記記憶領域に書き込むことを決定し、前記第１可逆圧縮方式は、前記第２可逆圧縮方式より圧縮率が小さく、かつ前記第２可逆圧縮方式より圧縮速度が低い、ストレージ装置。
【発明の効果】
【００１１】
本発明の一態様は、フラッシュメモリへのデータ書き込み速度及びフラッシュメモリからのデータ読み出し速度を保証しつつ、フラッシュメモリが保持するデータの圧縮率を小さくし、ひいてはフラッシュメモリの長寿命化を図ることができる。【００１２】
上記した以外の課題、構成、及び効果は、以下の実施形態の説明により明らかにされる。
【図面の簡単な説明】
【００１３】
【図１】実施例１におけるフラッシュメモリモジュールの動作の概要例を示す説明図である。
【図２】実施例１におけるフラッシュメモリモジュールを搭載した計算機システムの構成例を示すブロック図である。
【図３】実施例１におけるフラッシュメモリモジュールの構成例を示すブロック図である。
【図４】実施例１における２つの圧縮方式の特性の比較結果の一例である。
【図５】実施例１におけるリクラメーション動作の一例を示す説明図である。
【図６】実施例１におけるライトバッファの使い方の一例を示す説明図である。
【図７】実施例１における配分比テーブルの一例である。
【図８】実施例１におけるライト／リードコマンド処理の一例を示すフローチャートである。
【図９Ａ】実施例１における変更評価テーブルの一例である。
【図９Ｂ】実施例１におけるフラッシュメモリに格納されたデータの平均リード性能を算出する原理の一例を示すグラフである。
【図１０】実施例１におけるリクラメーション処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１４】
図１は、本実施形態のＦＭ（フラッシュメモリ）モジュールの動作の概要例を示す説明図である。本実施形態のＦＭモジュール１００は、例えば、記憶領域を提供するフラッシュメモリ１０７と、記憶領域に対するデータの書き込み及び制御するメモリコントローラ１０３と、記憶領域に書き込むデータを一時的に記憶するバッファメモリとして機能するＤＲＡＭ１０６と、を含む。メモリコントローラ１０３は、例えば、第１可逆圧縮方式によるデータの圧縮及び伸張を実行する第１圧縮伸張回路１０４と、第２可逆圧縮方式によるデータの圧縮及び伸張を実行する第２圧縮伸張回路１０５と、を含む。第１可逆圧縮方式は、第２可逆圧縮方式より圧縮率が小さく、かつ第２可逆圧縮方式より圧縮速度及び伸張速度が低い。
【００１５】
メモリコントローラ１０３は、フラッシュメモリ１０７にデータを書き込む際に、フラッシュメモリ１０７へのアクセス性能に基づいて、第１可逆圧縮方式と第２可逆圧縮方式の一方を選択して、選択した一方によってデータを圧縮してフラッシュメモリ１０７の記憶領域に書き込む。
【００１６】
具体的には、例えば、メモリコントローラ１０３は、上位装置からデータの書き込み要求を受信した際に、バッファメモリの空き領域の大きさをチェックする。メモリコントローラ１０３は、例えば、バッファメモリの空き領域が大きいほど、第１可逆圧縮方式を高い割合で選択する。これにより、メモリコントローラ１０３は、フラッシュメモリ１０７へのデータ書き込み速度を保証しつつ、フラッシュメモリ１０７が保持するデータの圧縮率を小さくすることができる。
【００１７】
また、例えば、メモリコントローラ１０３は、フラッシュメモリ１０７に既に第１可逆圧縮方式又は第２可逆圧縮方式の一方で圧縮された第１データが書き込まれている場合において、フラッシュメモリ１０７に書き込まれているデータの読み出し速度に基づいて、第１データを伸張して他方の圧縮方式で圧縮してフラッシュメモリ１０７の記憶領域に再度書き込む圧縮方式変更、を実行するか否かを決定する。
【００１８】
第１データが第１可逆圧縮方式で圧縮されている場合、メモリコントローラ１０３は、例えば、フラッシュメモリ１０７に書き込まれているデータの平均読み出し速度が所定値未満であり、かつ圧縮方式変更を行った場合における伸張速度の改善度を、圧縮方式変更を行った場合における圧縮率の悪化度で割った商、である改善コストが所定の条件を満たすと判定すれば、圧縮方式変更を実行することを決定する。
【００１９】
また、第１データが第２可逆圧縮方式で圧縮されている場合、メモリコントローラ１０３は、例えば、フラッシュメモリ１０７に書き込まれているデータの平均読み出し速度が所定値以上であると判定すれば、圧縮方式変更を実行することを決定する。
【００２０】
これにより、メモリコントローラ１０３は、フラッシュメモリ１０７からのデータ読み出し速度を保証しつつ、フラッシュメモリ１０７が保持するデータの圧縮率を小さくすることができる。
【実施例１】
【００２１】
［１］本発明を適用するストレージシステムの構成
図２は、計算機システムの構成例を示すブロック図である。計算機システムは、例えば、ストレージ装置９００と、第１のホスト９２１と、第２のホスト９２２（以降、第１のホスト９２１及び第２のホスト９２２を総称して単にホストと呼ぶ。）と、管理端末９２０と、ＳＡＮ（Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）９１０と、を含む。【００２２】
ストレージ装置９００は、ホストから送信されたコマンドを解釈して、ストレージ装置９００の記憶領域内のデータのリード／ライトを実行する。ストレージ装置９００は、例えば、第１のホストＩ／Ｆ（Ｉｎｔｅｒｆａｃｅ）９３１、第２のホストＩ／Ｆ９３２（以降、第１のホストＩ／Ｆ９３１及び第２のホストＩ／Ｆ９３２を総称して単にホストＩ／Ｆと呼ぶ。）、第１のストレージＩ／Ｆ９５１及び第２のストレージＩ／Ｆ９５２（以降、第１のストレージＩ／Ｆ９５１及び第２のストレージＩ／Ｆ９５２を総称して単にストレージＩ／Ｆと称する。）、保守Ｉ／Ｆ９３０、ＣＰＵ９４１、メモリ９４２、コネクタ９６１〜９６４、及びフラッシュメモリモジュール（以降、ＦＭモジュールとも称する。）１００を含む。【００２３】
ホストＩ／Ｆは、ホストからのデータや制御コマンドなどを受け付けるインタフェースである。また、ストレージＩ／Ｆは、ＦＭモジュール１００にデータや制御コマンドを送信するインタフェースである。また、保守Ｉ／Ｆ９３０は、管理端末９２０に接続され、管理端末９２０からの管理や保守に関する制御コマンド等を受け付けるインタフェースである。【００２４】
ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）９４１は、プロセッサを含み、演算処理装置として機能し、メモリ９４２に記憶されている各種プログラムや演算パラメータ等にしたがって、ストレージ装置９００全体の動作を制御する機能を有する。具体的に、ＣＰＵ９４１は、例えば、ストレージ装置９００とホストとの間のユーザデータの入出力（データＩ／Ｏ）を処理し、ＦＭモジュール１００にユーザデータをライトするためのライトコマンドをＦＭモジュール１００に発行したり、ＦＭモジュール１００からユーザデータをリードするためのリードコマンドをＦＭモジュール１００に発行したりする。【００２５】
メモリ９４２は、例えば、各種プログラムや演算パラメータ等の他、制御情報や管理情報、また、ＦＭモジュール１００にライトするユーザデータや、ＦＭモジュール１００からリードしたユーザデータを一時的に格納する。【００２６】
図２は、ストレージ装置９００にＦＭモジュール１００が６つ備えられている構成例を示しているが、ＦＭモジュール１００の数はかかる例に限定されない。ＦＭモジュール１００は、コネクタ９６１〜９６４を介してストレージＩ／Ｆと接続される。また、コネクタ９６１〜９６４を介してホストから受け付けられたデータ及び各制御コマンドがＦＭモジュール１００に書き込まれる。ＦＭモジュール１００の構成例については、図３を用いて後述する。なお、本実施形態では、ＦＭモジュール１００をストレージ装置９００と一体とした構成としているが、かかる例に限定されず、ＦＭモジュール１００をストレージ装置９００とは別体の装置であってもよい。【００２７】
ホストは、ＳＡＮを介してストレージ装置９００と接続され、ストレージ装置９００にデータのリード／ライト要求を送信する。また、ホストは、例えば、ＣＰＵ及びメモリ等の情報処理資源を備えたコンピュータ装置であって、例えば、パーソナルコンピュータ、ワークステーション、又はメインフレームなどである。ホストとストレージ装置９００との通信において、例えば、ＳＣＳＩ（Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ）などのブロックプロトコルが用いられる。また、ホストは、例えば、キーボード、スイッチやポインティングデバイス、マイクロフォン等の情報入力装置と、モニタディスプレイやスピーカ等の情報出力装置とを含む。【００２８】
管理端末９２０は、ＣＰＵ及びメモリ等の情報処理資源を備えたコンピュータ装置であって、例えば、パーソナルコンピュータ、ワークステーション、又はメインフレームなどである。ＣＰＵは、演算処理装置として機能し、メモリに記憶されているプログラムや演算パラメータ等にしたがって、管理端末９２０の動作を制御する。また、管理端末９２０は、例えば、キーボード、スイッチやポインティングデバイス、マイクロフォン等の情報入力装置と、モニタディスプレイやスピーカ等の情報出力装置と、を含み、オペレータ等の入力に応じてストレージ装置９００等を管理する装置である。【００２９】
図２では、ホスト及びＦＭモジュール１００を接続するコネクタは２つずつ示されている例が記載されているが、その数はかかる例に限定されない。同様に、各コネクタ及びインタフェースの規格は特定のものに限定されない。例えば、ＳＡＮ９１０に適用される代表的な規格として、ＦＣ（Ｆｉｂｒｅ  Ｃｈａｎｎｅｌ）、ＳＣＳＩ、ｉＳＣＳＩ（ｉｎｔｅｒｎｅｔ  Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ）、ＳＡＳ（Ｓｅｒｉａｌ  Ａｔｔａｃｈｅｄ  ＳＣＳＩ）などを例示できる。なお、計算機システムはＳＡＮ９１０を含まなくてもよく、計算機システムにおけるホストとＦＭモジュール１００との接続形態は、ＤＡＳ（Ｄｉｒｅｃｔ  Ａｔｔａｃｈｅｄ  Ｓｔｏｒａｇｅ）であってもよい。【００３０】
［２］フラッシュメモリの特徴と扱い方
次に、ＦＭモジュール１００の記憶媒体であるフラッシュメモリの特徴と扱い方について説明する。フラッシュメモリは、データを書き込んでから長い時間が経つと、データ誤りが徐々に増加し、誤り訂正符号（ＥＣＣ）を用いても訂正できなくなってしまう。そこで、データを書き込んでから一定時間が経過したページからデータを読み出して誤りを訂正し、別の未書き込みページに移動し、元のデータを記録しているページを無効化する。この動作はリフレッシュと呼ばれる。【００３１】
データ書き換えやリフレッシュ動作に伴って未書込みページは減っていく。フラッシュメモリは未書き込みページを作るために消去と呼ばれる動作をサポートする。未書込みページが枯渇した場合には、ブロック内のページを全て無効化された状態にし、当該ブロックを消去して新たな未書込みページを生成する。この動作はリクラメーションと呼ばれる。【００３２】
フラッシュメモリは、最小消去単位が最小書き込み単位に比べて大きいという特徴を有する。具体的に、フラッシュメモリにおいては、１つのブロック内に複数（例えば５１２個）のページが設けられており、ブロック単位でデータが消去され、ページ単位でデータの読み書きが実行される。ページのサイズは例えば１６ＫＢバイトである。フラッシュメモリは、多数のページ（例えば１００万個）を含み、各ページにはアドレスが付されている。【００３３】
フラッシュメモリは、ページに記録されたデータを直接的に上書きすることができないという特徴を有する。ページに記録されたデータを書き換える場合、当該ページを含むブロック内に記憶している有効な他のデータを別のブロックに退避させて、元のブロックを消去する。そして、消去したブロックに新しいデータをページ単位で書き込むことによりデータの書き換えを行う。【００３４】
このように、フラッシュメモリにおけるデータの書き換え処理では、ブロック単位のデータの消去が伴う。しかしながら、フラッシュメモリの１ブロック分のデータ消去にかかる時間は、１ページ分のデータを書き込むのに要する時間と比べて長い時間がかかる。したがって、１ページ分のデータを書き換えるために毎回１ブロック分のデータ消去を実行すると、フラッシュメモリのデータ書き換え性能が低下してしまう。つまり、データが記録されていないブロックが常に存在する状態を維持するために、フラッシュメモリからのデータの消去が、例えば、ホストからのリード／ライト要求のいずれに対する処理も実行していないポストプロセス時に実行されることが望ましい。【００３５】
通常、フラッシュメモリに対してデータの書き換えを行う場合には、データを書き換えるごとにブロックのデータを消去することは行われない。通常、データが記録されていない未使用のページにデータを追記し、書き換え前のデータを記録しているページを無効化（ホスト等の上位装置からの参照を不可とする処理）する方法が採用される。つまり、ホスト等の上位装置からストレージ装置９００にアクセスするためのデータ参照アドレスと、そのデータを記録するページのアドレスとの対応関係は動的に変化する。【００３６】
しかし、データの書き換え処理が度重なって実行されると、フラッシュメモリ内の未使用領域が枯渇してしまうため、フラッシュメモリに書き込まれている無効データ（書き換えた後の旧データなど）を消去して、記憶領域を再利用可能な状態にする必要が生じる。そこで、旧データを含むブロック内の有効なデータのみを未使用領域にコピーし、コピー元のブロックを消去して未使用領域として再生するブロック再生処理を実行する。この処理はリクラメーションと呼ばれ、フラッシュメモリのデータを高速に書き換えるには必須の処理であり、特に無効データが多くなったブロックを優先して実行される。【００３７】
一方、フラッシュメモリは、ブロックを消去する回数に制限があるという特徴を有する。例えば、１ブロック当たり３０００回までの消去回数が保証される。この場合、データの書き換えが１つのブロックに集中して、当該ブロックの消去回数が保証回数を超えると、データ消去ができなくなることがあり、そのブロックは以降使用不能となってしまい、使用可能なブロック数が減少するという問題がある。そこで、特定ブロックに対する消去処理が集中しないように、消去回数の多いブロックから少ないブロックに格納データを移動するなどして消去回数の平準化処理を行う必要がある。【００３８】
また、フラッシュメモリは、一度書き込みしたページについては、データを保持しておくだけでも時間経過とともにデータエラーが増加していくという特徴を有する。データエラーによるデータ損失を回避するために、記録するデータには誤り訂正符号（ＥＣＣ：Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ  Ｃｏｄｅ）に基づくパリティがあらかじめ付加されている。書き込み後一定時間を経過したデータを読み出し、データエラーが少ないうちに当該パリティを用いてそれを訂正して、訂正後のデータを別ページに移動するリフレッシュ処理が行われる。なお、この処理が実行される場合にも、消去回数を平準化したり、性能に対する影響を考慮したりする必要がある。【００３９】
このように、フラッシュメモリを記憶媒体として用いる場合には、データが記録されていないブロックが常に存在する状態を維持するために、また、消去回数を平準化したりするために、上位装置に提供する論理アドレスと実際の記憶領域の物理アドレスとを動的に対応づけ、データの書き込みの際に論理アドレスから物理アドレスへの変換処理を行う。すなわち、上位装置に提供する論理アドレスと記憶領域上の物理アドレスとの対応を逐次変更することにより、上位装置は、論理アドレス空間にデータを書き込めばよく、データ書き込み時における未使用領域への追記に伴う物理アドレスの変更を意識しなくてもよいように管理する。【００４０】
［３］本発明を適用するＦＭモジュールの構成
図３は、ＦＭモジュール１００の構成例を示すブロック図である。ＦＭモジュール１００は、例えば、ストレージＩ／Ｆ１０２、メモリコントローラ１０３、複数のチップを含む１以上のＮＡＮＤ型フラッシュメモリ（以降、ＦＭまたはフラッシュメモリとも称する。）１０７、及び揮発性のメモリであるＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１０６を含む。メモリコントローラ１０３は、例えば、第１圧縮伸張回路１０４と第２圧縮伸張回路１０５とを含む。【００４１】
メモリコントローラ１０３は、例えば、マイクロプロセッサを含み、ストレージＩ／Ｆ１０２、フラッシュメモリ１０７、及びＤＲＡＭ１０６と接続される。マイクロプロセッサは、例えば、ストレージＩ／Ｆ１０２を介して受信したリード／ライトコマンドの内容解釈、リード／ライトデータの送受信、第１圧縮伸張回路１０４及び第２圧縮伸張回路１０５を用いたデータの圧縮及び伸張、並びにフラッシュメモリ１０７とＤＲＡＭ１０６との間のデータ転送等を実行する。【００４２】
ストレージＩ／Ｆ１０２は外部の装置等と接続するためのインタフェース機構であり、外部から発行されたライトコマンドによってユーザデータを外部から受信したり、外部から発行されたリードコマンドによってユーザデータを外部に送信したりする。【００４３】
ＦＭモジュール１００は、フラッシュメモリに格納するデータを可逆圧縮技術によって圧縮することにより、フラッシュメモリへの書き込みデータ量を削減する。本実施例では、ＦＭモジュール１００は、ＧＺＩＰ方式とＬＺ７７方式の２種類の可逆圧縮方式を用いる例を説明する。両方式の特徴は次章で説明する。【００４４】
第１圧縮伸張回路１０４は、例えば、メモリコントローラ１０３内にハードウェア（論理回路）として実装された演算器である。第１圧縮伸張回路１０４は、フラッシュメモリ１０７に格納するデータ量を削減するため、ＧＺＩＰ方式によって平文状態のデータを可逆的に圧縮し、圧縮状態のデータを生成する。また、第１圧縮伸張回路１０４は、ＧＺＩＰ方式によって圧縮されたデータを伸張して、元の平文状態のデータを生成する。【００４５】
第２圧縮伸張回路１０５は、例えば、メモリコントローラ１０３内にハードウェア（論理回路）として実装された演算器である。第２圧縮伸張回路１０５は、フラッシュメモリ１０７に格納するデータ量を削減するため、ＬＺ７７方式によって平文状態のデータを可逆的に圧縮し、圧縮状態のデータを生成する。また、第２圧縮伸張回路１０５は、ＬＺ７７方式によって圧縮されたデータを伸張して、元の平文状態のデータを生成する。【００４６】
ＤＲＡＭ１０６は、外部から受信したライトデータを一時的に格納する。また、外部へ送信するリードデータを一時的に格納する。また、ＤＲＡＭ１０６は、フラッシュメモリ１０７にライトするデータを一時的に格納するライトバッファとして機能する。また、ＤＲＡＭ１０６は、フラッシュメモリ１０７からリードしたデータを一時的に格納するリードバッファとして機能する。また、ＤＲＡＭ１０６は、第１圧縮伸張回路１０４及び第２圧縮伸張回路１０５により圧縮及び伸張するデータの転送元、並びに圧縮及び伸張の結果データの転送先として機能する。【００４７】
［４］２つの圧縮方式の特徴と性能特性
ＦＭモジュール１００の第２圧縮伸張回路１０５に適用されるＬＺ７７方式（以下、第２方式とも呼ぶ）は、１９７７年にレンペル（Ｌｅｍｐｅｌ）及びジフ（Ｚｉｖ）によって開発された、最も基本的な可逆データ圧縮方式である。ＬＺ７７方式の原理はスライド辞書型圧縮である。ＬＺ７７方式は、圧縮対象の文字列ストリームの先頭から末尾に向かってポインタを移動させる。ＬＺ７７方式は、その際に、ポインタから先頭方向の所定範囲（スライド辞書）の中で、そのポインタから始まる文字列に最も長く一致するものを探す。そして、ＬＺ７７方式は、その文字列をコピー記号に変換することでデータ量を減らしていく。コピー記号とは、スライド辞書上の距離Ｊとコピー長さＬを（Ｌ，Ｊ）と記号化したものである。【００４８】
例えば、文字列ストリーム「ＡＢＣＤＥＢＣＤＡＥＣＤＥＢＢ」がＬＺ７７方式を用いて圧縮された場合、圧縮後の文字列ストリームはコピー記号を用いて、「ＡＢＣＤＥ（３，４）ＡＥ（４，８）Ｂ」と表される。「ＢＣＤ」の３文字、及び「ＣＤＥＢ」の４文字がそれぞれコピー記号（３，４）、（４，８）に変換されている。このような変換により、Ｌ個分の文字情報量がＬとＪの２数値の情報量に減ることでデータ量が減少する。つまり、文字列のコピー長さＬが長いほどデータ量の削減量が多い。ＬＺ７７方式は、圧縮も伸張も原理が簡単で、パイプライン化された論理回路として実装できるため、データパタンによらず一定のスループットで処理することができ、圧縮及び伸張処理の性能は安定している。【００４９】
一方、ＦＭモジュール１００の第１圧縮伸張回路１０４に適用されるＧＺＩＰ方式（以下、第１方式とも呼ぶ）は、ＬＺ７７方式にハフマン（Ｈｕｆｆｍａｎ）符号化を組み合わせて、さらにデータ量を削減できるようにした可逆データ圧縮方式である。ハフマン符号化は、文字や記号の出現頻度によって異なる長さの符号を割り当てる。すなわち、ハフマン符号化は、出現頻度が多いものほど短い符号に、出現頻度が少ないものほど長い符号に変換する。例えば、ある文字列ストリームにおける各文字の出現頻度がＡ＝２、Ｂ＝５、Ｃ＝３、Ｄ＝１、Ｅ＝１である場合、２進数を用いてハフマン符号化により、当該各文字がＡ＝１１０、Ｂ＝０、Ｃ＝１０、Ｄ＝１１１０、Ｅ＝１１１１と置換される。【００５０】
つまり、上述の例では、出現頻度が最大のＢが１ビットで符号化され、出現頻度が最小のＤとＥが４ビットで符号化される。符号化する前の文字列ストリームには５種類の文字Ａ〜Ｅが含まれ、５種類の文字は３ビット（８通り）で表現でき、かつ出現頻度の合計は１２回（＝２回＋５回＋３回＋１回＋１回）なので、符号化前の文字列ストリームのデータ量は、３ビット×１２回＝３６ビットだった。ハフマン符号化の結果、文字列ストリームのデータ量は、３ビット×２回＋１ビット×５回＋２ビット×３回＋４ビット×１回＋４ビット×１回＝２５ビットに減ることが分かる。【００５１】
本実施形態において、圧縮率とは圧縮後サイズと圧縮前サイズで割った値である。圧縮率１００％は圧縮が全くできなかったことを意味する。ＧＺＩＰ方式は、ハフマン符号化を加えたことによりＬＺ７７方式に比べて圧縮率をより小さくできる。しかし、ハフマン符号化は、入力データの内容全てに対して出現頻度の統計をとり終わるまで変換処理を開始できないため、入力データ量が多いほど処理時間が長くなるという短所がある。【００５２】
したがって、ＧＺＩＰ方式の前半部分のＬＺ７７圧縮においてよく圧縮できた場合は、後半部分のハフマン符号化への入力データ量が少ないため処理時間が短くなる（すなわちスループットが高くなる）が、前半部分のＬＺ７７圧縮においてあまり圧縮できなかった場合は、後半部分のハフマン符号化への入力データ量が多いため処理時間が長くなる（すなわちスループットが低くなる）。【００５３】
ＧＺＩＰ方式の伸張処理で、ハフマン符号化データをＬＺ７７圧縮データに戻す復号処理においても同様の性能特性が見られる。すなわち、よく圧縮できた場合は、復号処理すべきデータ量が少なく、処理時間が短くなる（すなわちスループットが高くなる）が、あまり圧縮できなかった場合は、復号処理すべきデータ量が多く、処理時間が長くなる（すなわちスループットが低くなる）。【００５４】
図４は、第１方式と第２方式それぞれの特性を示すテーブルである。列２１０は第１方式でのデータ圧縮率を示す。図４の例では、簡単のため、列２１０は、第１方式で圧縮したデータの圧縮率を２０％の幅で５つのレンジに分けて示す。圧縮率が小さいものほど、よく圧縮できたことを意味する。【００５５】
列２２０は、第１方式の各圧縮率レンジについて、第１方式で圧縮した時の平均圧縮スループット性能、及び第１方式で伸張した時の平均伸張スループット性能を示す。第１方式の圧縮率が２０％以下のレンジでは圧縮スループット性能が２．６ＧＢ／ｓ以上あるが、第１方式の圧縮率が８０％を超えるレンジでは圧縮スループット性能が１．０ＧＢ／ｓまで低下する。【００５６】
圧縮しにくいデータがたくさん記録されると、この圧縮・伸張スループット性能が、ＦＭモジュール１００のデータライト・リードのスループット性能に悪影響を与える。つまり、ライト性能は平均圧縮スループット性能までしか上がらず、リード性能は平均伸張スループット性能までしか上がらない。【００５７】
以下、例えば、ＦＭモジュール１００の目標ライト性能が１．５ＧＢ／ｓ、目標リード性能が２．２ＧＢ／ｓである場合を想定する。ＦＭモジュール１００の目標ライト性能及び目標リード性能は、例えば、予め定められている。例えば、読み書きするデータの大半が圧縮率４０％を超えるような状況においては、リード性能が目標を達成できなくなる。さらに、読み書きするデータの大半が圧縮率６０％を超えるような状況においては、リード性能もライト性能も目標を達成できなくなる。【００５８】
列２３０は、第１方式の各圧縮率レンジについて、当該圧縮率に対応する圧縮前データが第２方式で圧縮された場合に、第１方式で圧縮された場合と比較して圧縮率が平均してどれだけ悪化するかを示す。図４の例では、第１方式の圧縮率が４１〜６０％のレンジの圧縮前データが第２方式で圧縮された場合、圧縮率は第１方式で圧縮された場合と比較して、平均＋３．３％悪化する。【００５９】
列２４０は、第１方式の各圧縮率レンジについて、当該圧縮率に対応する圧縮前データが第２方式で圧縮された場合の平均圧縮スループット性能と、当該圧縮率に対応する圧縮前データが第２方式で圧縮されたデータを第２方式で伸張した時の平均伸張スループット性能と、を示す。図４の例では、第２方式で圧縮されたデータは、圧縮率に関わらず、圧縮・伸張スループット性能が２．６ＧＢ／ｓ程度になる。従って、読み書きするデータの大半が圧縮率６０％を超えるような状況でも、第２方式を適用すれば、ＦＭモジュール１００のライト・リード性能は目標を達成できる。【００６０】
［５］リクラメーション動作の基本
次に、図５を参照して、ＦＭモジュール１００が行うリクラメーション動作の例を示し、フラッシュメモリ１０７内の未書き込みページを増やす方法を示す。図５中のアルファベットは個々の論理データ、括弧内の数字は各論理データの世代番号を示す。例えば、Ａ（１）はＡ（０）が１回更新されたデータを意味する。同一アルファベットのデータの中で、括弧内の数字が最大のものが最新データであり、それ以外は旧データ、つまり無効データである。例えば、Ｃ（３）は最新データであり、Ｃ（０）〜Ｃ（２）は無効データである。【００６１】
リクラメーション前のブロック群３００及びリクラメーション後のブロック群３４０は、それぞれはフラッシュメモリ１０７内のブロック３１０、ブロック３２０、及びブロック３３０からなる。リクラメーション前のブロック群３００において、全てのページが未書き込みであるブロックはブロック３３０だけである。ブロック３１０の記録データのうち、Ａ（１）とＢ（１）は最新データであるが、Ａ（０）、Ｂ（０）、Ｃ（０）、Ｄ（０）は旧データである。【００６２】
メモリコントローラ１０３が、リクラメーション処理において、Ａ（１）とＢ（１）をブロック３３０に移動することにより、ブロック３１０の記録データは全て無効データ（格納しておく必要がないデータ）となる。また、リクラメーション前のブロック群３００において、ブロック３２０の記録データのうち、Ｃ（３）とＤ（２）とＥ（０）は最新データであるが、Ｃ（１）とＣ（２）とＤ（１）は旧データである。【００６３】
メモリコントローラ１０３がＣ（３）とＤ（２）とＥ（０）をブロック３３０に移動することにより、ブロック３２０の記録データは全て無効データ（格納しておく必要がないデータ）となる。最後に、メモリコントローラ１０３は、ブロック３１０、３２０を消去することで、リクラメーション後のブロック群３４０では、全てのページが未書き込みのブロックは２つに増える。【００６４】
［６］ライトバッファ状態監視に基づくライト性能保証
本実施例のＦＭモジュール１００は、ＤＲＡＭ１０６上のライトバッファの使用状態を監視し、当該使用状態に基づいてライト性能が目標以上になることを保証する。以下、その原理を説明する。【００６５】
まず、図６を参照して、ＦＭモジュール１００内のＤＲＡＭ１０６に存在するライトバッファの使い方の一例を説明する。ＤＲＡＭ１０６は、ライトデータを一時的に保持するためのライトバッファ４００を含む。ＦＭモジュール１００がホストからライトデータを受信すると、当該ライトデータはライトバッファ４００の空き領域４２０に入り、当該空き領域４２０は使用領域４１０になる。【００６６】
ライトデータは第１圧縮伸張回路１０４又は第２圧縮伸張回路１０５によって圧縮されるために読み出される。圧縮処理が終わると、圧縮されたライトデータは再び元の使用領域４１０に書き戻される。その圧縮されたライトデータはフラッシュメモリ１０７内の未書き込みページにライトされる。このライトが完了すると、当該ライトデータが使っていた使用領域４１０は開放され、再び空き領域４２０として扱われる。【００６７】
上述の処理において、空き領域４２０が使用領域４１０に変わる速さよりも、使用領域４１０が空き領域４２０に戻る速さが速い場合は、ライトバッファの空き領域４２０が枯渇することはない。しかし、第１圧縮伸張回路１０４による圧縮処理性能がライトデータの受信スループットよりも遅くなると、空き領域４２０が使用領域４１０に変わる速さよりも、使用領域４１０が空き領域４２０に戻る速さが遅くなり、徐々にライトバッファの空き領域４２０が減っていき、やがて枯渇する。【００６８】
そうなると、ライトバッファがライトデータを受け入れる速度（ＦＭモジュール１００のライトスループット性能）が、第１圧縮伸張回路１０４による圧縮処理性能まで低下する。例えば、圧縮率が８０％を超えるようなデータばかりがライトされる場合、図４に示したように第１圧縮伸張回路１０４による圧縮処理性能は１．０ＧＢ／ｓになる。このような場合、ライトバッファの空き領域４２０がやがて枯渇し、ＦＭモジュール１００のライトスループット性能は１．０ＧＢ／ｓまで低下する。つまり、ライトスループット性能が上述の目標ライト性能１．５ＧＢ／ｓを下回ることになる。本実施例のＦＭモジュール１００は、この問題を解決するため、ライトバッファ状態監視の基づくライト性能保証を行う。【００６９】
図７を参照しながら、ＦＭモジュール１００がライト性能保証を行う処理について説明する。図７は、第１方式と第２方式との配分比を示す配分比テーブルの一例である。配分比テーブル５００は、例えば、メモリコントローラ１０３内にプログラムの一部として予め記述されている。【００７０】
メモリコントローラ１０３は、例えば、ライトバッファ４００の空き領域４２０のエントリ数がいくつあるかを常時監視する。配分比テーブル５００は、ライトバッファ４００の空きエントリ数に応じて、第１方式で圧縮されるライトデータの割合と、第２方式で圧縮されるライトデータの割合とを定める。【００７１】
図４に示したように、第２方式による圧縮処理性能は圧縮率に関わらず２．５ＧＢ／ｓ以上あるため、目標ライト性能１．５ＧＢ／ｓを上回る。つまり、メモリコントローラ１０３が第２方式を用いてライトデータを圧縮することにより、徐々にライトバッファの空き領域４２０が増えていき、ライト性能を上げる効果がある。【００７２】
配分比テーブル５００の列５１０の１行目のように、空きエントリ数が２０以上あるときは、メモリコントローラ１０３はライトバッファの空き領域４２０が枯渇していない（余裕がある）と判断して、ライトデータの全て（１００％）を第１方式で圧縮することを選択する。しかし、メモリコントローラ１０３が全てのライトデータを第１方式で圧縮していると、圧縮率が高いデータばかりがライトされた場合に、空きエントリ数が減っていき、やがて２０を下回る。そうなると、メモリコントローラ１０３は配分比テーブル５００の列５１０の２〜５行目に従って、空きエントリ数が少なくなるほどに、第２方式で圧縮するライトデータの割合を大きくしていく。【００７３】
例えば、配分比テーブル５００の４行目のように、空きエントリ数が５〜９になった場合、メモリコントローラ１０３は、次々に受信するライトデータ群に適用する圧縮方式を以下のような規則で変化させることで、第１方式に２５％、第２方式に７５％の割合でライトデータを配分する。具体的には、例えば、メモリコントローラ１０３は、第１方式を用いた圧縮を１回、第２方式を用いた圧縮を３回、という処理を順に繰り返すことにより、第１方式に２５％、第２方式に７５％の割合でライトデータを配分することができる。【００７４】
また、配分比テーブル５００の５行目に示すように、空きエントリ数が４以下になった場合は、メモリコントローラ１０３は、ライトバッファの空き領域４２０が枯渇していると判断して、ライトデータの全て（１００％）を第２方式で圧縮して、ライト性能の改善効果を最大化することを選択する。【００７５】
以上のように、ＦＭモジュール１００は、ライト性能が目標を下回らない限り、より圧縮率を小さくすることができる第１方式でライトデータを圧縮してフラッシュメモリ１０７に格納する。したがって、第２方式の圧縮しか適用しない従来のフラッシュメモリを搭載したストレージ装置に比べて、本実施例のフラッシュメモリ１０７を搭載したストレージ装置９００は、格納するデータ量をより削減することができる。【００７６】
なお、図７の配分比テーブル５００の例に示した配分比は一例である。図４の例において、第１方式における最低の圧縮処理性能は１．０ＧＢ／ｓであり、第２方式における最低の圧縮処理性能は２．５ＧＢ／ｓである。第１方式と第２方式とを用いた圧縮処理性能がライト性能の目標が上回っていれば、ライトバッファの空き領域４２０は増えていく。つまり、１．０ｘ＋２．５（１−ｘ）＞１．５を満たすｘが第１方式の配分比であれば（即ち第２方式の配分比は１−ｘ）、ライトバッファの空き領域４２０は増えていく。従って、配分比テーブル５００において、ライトバッファ空きエントリ数が所定数を下回った場合における第１方式の配分比が、上述の不等式を満たすｘであればよい。また、ライトバッファ空きエントリ数が多いほど、第１方式の配分比が大きいことが望ましい。【００７７】
［７］ライト・リードコマンドの処理方法
次に、図８を参照して、ＦＭモジュール１００が外部からのライト・リードコマンドを処理する手順の一例について説明する。この手順は、上記のライト性能保証処理を含む。【００７８】
まず、メモリコントローラ１０３は、ホストからコマンドを受信する（６０１）。メモリコントローラ１０３は、そのコマンドがライトコマンドかリードコマンドかを判断し（６０２）、ライトコマンドである場合ステップ６１０に、リードコマンドである場合ステップ６２０に遷移する。ステップ６１０〜６１８はライトコマンド処理、ステップ６２０〜６２８はリードコマンド処理である。【００７９】
まず、ライトコマンド処理について説明する。メモリコントローラ１０３は、ライトバッファ４００の空き領域４２０の１つにライトデータを受信し、その場所を使用領域４１０として扱う（６１０）。メモリコントローラ１０３は、ライトバッファ４００の空きエントリ数を取得する（６１１）。ライトバッファ４００の空きエントリ数は、フラッシュメモリ１０７のアクセス性能の一例である。メモリコントローラ１０３は、配分比テーブル５００から、取得したエントリ数に対応する圧縮方式を選択する（６１２）。【００８０】
メモリコントローラ１０３は、ステップ６１２において第１方式を選択した場合は、第１圧縮伸張回路１０４を用いて圧縮を行い（６１３）、ステップ６１５に遷移する。なお、ステップ６１３において、メモリコントローラ１０３は、圧縮前のデータサイズと圧縮後のデータサイズとから圧縮率を算出し、後述する変更評価テーブルの対応するカウント値をインクリメントする。【００８１】
メモリコントローラ１０３は、ステップ６１２において第２方式を選択した場合は、第２圧縮伸張回路１０５を用いて圧縮を行い（６１４）、ステップ６１５に遷移する。なお、メモリコントローラ１０３は、ステップ６１４において、後述する変更評価テーブルの不明欄のカウント値をインクリメントする。メモリコントローラ１０３は、圧縮データをライトバッファ４００の使用領域４１０に戻す（６１５）。そして、この圧縮データをフラッシュメモリ１０７内の未書き込みページにライトする（６１６）。【００８２】
メモリコントローラ１０３は、ステップ６１６のライトが完了したら、ライトバッファ４００の使用領域４１０を開放することにより、当該領域を空き領域４２０に戻す（６１７）。最後に、メモリコントローラ１０３は、ホストがライトコマンドで指定したライト論理アドレスに、フラッシュメモリ１０７内のデータ格納先ページのアドレスを対応付ける（６１８）。なお、メモリコントローラ１０３は、例えば、ＤＲＡＭ１０６上にアドレス変換テーブルを作成して、当該対応付けを変換テーブルに登録する。なお、メモリコントローラ１０３は、例えば、フラッシュメモリ１０７に格納した圧縮データが第１方式、第２方式のどちらで圧縮されたものであるかを示す情報も、格納先ページアドレスとともに変換テーブルに登録しておく。以上で、ライトコマンド処理を完了する。【００８３】
続いて、リードコマンド処理について説明する。メモリコントローラ１０３は、ホストがリードコマンドで指定したリード論理アドレスを、ＤＲＡＭ１０６上のアドレス変換テーブルにおいて対応付けられたフラッシュメモリ１０７内のデータ格納先ページのアドレスに変換する（６２０）。メモリコントローラ１０３は、フラッシュメモリ１０７内の、変換後のページアドレスが示すページから圧縮データを読み出す（６２１）。【００８４】
メモリコントローラ１０３は、読み出した圧縮データをＤＲＡＭ１０６内のリードバッファの１つに格納する（６２２）。メモリコントローラ１０３は、アドレス変換テーブルを用いて、読み出した圧縮データが第１方式又は第２方式のどちらの方式で圧縮がされたか判定する（６２３）。【００８５】
メモリコントローラ１０３は、読み出したデータが第１方式で圧縮されたとステップ６２３において判定した場合、第１圧縮伸張回路１０４を用いて当該データの伸張を行い（６２４）、ステップ６２６に遷移する。メモリコントローラ１０３は、読み出したデータが第２方式で圧縮されたとステップ６２３において判定した場合、第２圧縮伸張回路１０５を用いて当該データの伸張を行い（６２５）、ステップ６２６に遷移する。【００８６】
メモリコントローラ１０３は、伸張したデータ（即ち圧縮する前の状態のデータ）をリードバッファに戻す（６２６）。メモリコントローラ１０３は、伸張したデータをリードコマンドの応答データとしてホストに送信する（６２７）。最後に、伸張したデータが使用していたリードバッファの１つを開放する（６２８）。以上で、リードコマンド処理が完了する。【００８７】
［８］圧縮方式変更によるリード性能保証
本実施例のＦＭモジュール１００は、フラッシュメモリ１０７に格納された圧縮データのうち、第１方式で圧縮されたデータを第２方式で圧縮しなおすことによって、リード性能が目標以上になることを保証する。以下、図９Ａ及び図９Ｂを参照してその原理を説明する。【００８８】
図９Ａは変更評価テーブルの一例である。変更評価テーブル７００は、フラッシュメモリ１０７に格納されたデータの圧縮方式を第１方式から第２方式に変更することによる影響を評価するために、メモリコントローラ１０３が管理するテーブルである。変更評価テーブル７００は、例えばＤＲＡＭ１０６に格納されている。【００８９】
変更評価テーブル７００の列７１０は、第１方式で圧縮したデータの圧縮率を２０％の幅で５つのレンジに分けていることを示す。前述した通り圧縮率が小さいものほど、よく圧縮できたことを意味する。【００９０】
列７２０の２種類のカウント値は、第１方式の各圧縮率レンジについて、当該レンジ内の圧縮率に該当する圧縮データがフラッシュメモリ１０７内にいくつあるかを示すカウント値７２１と、当該レンジ内の圧縮率に該当する圧縮データのうち第２方式で圧縮しなおされた（方式変更された）ものがいくつあるかを示すカウント値７２２である。これらのカウント値はデータライトや圧縮方式変更によって増減する。【００９１】
例えば、第１方式での圧縮率３０％の格納データが第１方式での圧縮率７０％のデータに更新されたとすると、カウント値７２１の２１〜４０％レンジの値は１減算され、カウント値７２１の６１〜８０％レンジの値は１加算される。また、例えば、第１方式での圧縮率９０％の格納データが第２方式で圧縮しなおされたとすると、カウント値７２１の値は変化せず、カウント値７２２の８１〜１００％レンジの値は１加算される。【００９２】
列７２５は、第１方式の各圧縮率レンジについて、第１方式で伸張した時の平均伸張スループット性能を示す。つまり、列７２５は、図４の列２２０に含まれる伸張処理性能の列と同じ情報を保持する。列７２６は、第２方式の各圧縮率レンジについて、第２方式で伸張した時の平均伸張スループット性能を示す。つまり、列７２６は、図４の列２４０に含まれる伸張処理性能の列と同じ情報を保持する。【００９３】
列７３０は、第１方式の各圧縮率レンジについて、そのデータを第２方式で圧縮しなおされた場合に、第１方式で圧縮された場合と比較して圧縮率が平均してどれだけ悪化するかを示す。つまり、列７３０は、図４の列２３０と同じ情報を保持する。【００９４】
列７４０は、第１方式の各圧縮率レンジについて、そのデータを第２方式で圧縮しなおした場合に、伸張処理性能が平均してどれだけ改善するかを示す。つまり、列７４０は、列７２６の値から列７２５の値を引いた差を示す。例えば、第１方式での圧縮率が６１〜８０％レンジのデータが第２方式で圧縮しなおされたとすると、当該データの伸張性能は１．２ＧＢ／ｓから２．６ＧＢ／ｓに改善するため、列７４０の対応するセルは＋１．４ＧＢ／ｓという値を保持する。【００９５】
列７５０は、第１方式の各圧縮率レンジについて、そのデータを第２方式で圧縮しなおすことにより伸張性能を１ＧＢ／ｓだけ改善させると、圧縮率が平均してどれだけ悪化するかを示す指標を保持する。以下、この指標を改善コストと呼ぶ。改善コストは、各レンジにおいて、列７３０の値を列７４０の値を割った商である。【００９６】
図９Ａの例では、第１方式での圧縮率が４１〜６０％レンジのデータを第２方式で圧縮しなおして１ＧＢ／ｓ改善させようとすると、圧縮率は平均して＋５．５％悪化することを示す。なお、第１方式での圧縮率が１〜２０％レンジのデータは第２方式で圧縮しなおすとかえってリード性能が悪化するので、改善コストは評価できない。従って、列７５０の当該レンジに対応するセルには、例えばｎｕｌｌ値が格納されている。改善コストが小さい圧縮率レンジのデータほど、当該データが第２方式で圧縮しなおされた場合における、リード性能を改善することに伴う格納データ量の増加、が少なくてすむことを意味する。【００９７】
図９Ｂのグラフ７６０は、メモリコントローラ１０３が、フラッシュメモリ１０７に格納されたデータの平均リード性能７７０（すなわち平均伸張性能）を算出する原理の一例を示している。メモリコントローラ１０３は、例えば、グラフ７６０において、横方向に各圧縮率レンジの列７２０が示すカウント値、縦方向に各圧縮率レンジの平均伸張性能をとり、各圧縮率レンジについて形成される長方形７８０〜７８５の面積の合計を算出し、算出した合計をカウント値の合計で割ることで、平均リード性能７７０を算出する。【００９８】
長方形７８０は圧縮率１〜２０％レンジ、長方形７８１は圧縮率２１〜４０％レンジ、長方形７８２は圧縮率４１〜６０％レンジ、長方形７８３は圧縮率６１〜８０％レンジ、長方形７８４は圧縮率８１〜１００％レンジに対応する。内部に斜線が描かれた長方形７８５は、圧縮率８１〜１００％レンジのデータの一部を、第２方式で圧縮しなおしたことによる伸張性能の改善分に対応する。【００９９】
メモリコントローラ１０３は、例えば、グラフ７６０から算出した平均リード性能が目標リード性能である２．２ＧＢ／ｓ（又は目標リード性能に所定のマージンを加えた値）を下回ったと判定した場合に、第１方式で圧縮されたデータの一部を第２方式で圧縮しなおす。メモリコントローラ１０３が当該一部のデータをどのように選択するかについては後述する。メモリコントローラ１０３が一部のデータの圧縮方式を変更することによって、グラフ７６０の長方形７８５のような伸張性能改善に対応する面積が増えるので、平均リード性能７７０を改善し、目標２．２ＧＢ／ｓを下回らないことを保証することができる。【０１００】
以上のように、ＦＭモジュール１００は、例えば、リード性能が目標を下回らない限り、より圧縮率を小さくすることができる第１方式でライトデータを圧縮してフラッシュメモリ１０７に格納する。したがって、第２方式しか用いないＦＭモジュールに比べて、本実施例のＦＭモジュール１００は、格納データ量をより削減することができる。【０１０１】
［９］リード性能保証の下で圧縮率を最小化するリクラメーション動作
上述したように、ＦＭモジュール１００のライト性能を保証するため、メモリコントローラ１０３は、一部のライトデータを第２方式で圧縮してフラッシュメモリ１０７に格納することがある。図４で示したように第２方式で圧縮されたデータを読み出して伸張する際のスループット性能は２．６ＧＢ／ｓである。【０１０２】
ＦＭモジュール１００の平均リード性能が目標の２．２ＧＢ／ｓを大きく上回っていれば、ＦＭモジュール１００は、これらのデータを必ずしも第２方式で圧縮した状態で格納しつづけなくてもよく、より圧縮率を小さくできる第１方式で圧縮しなおし、データ量を削減したほうがよい。そこで、本実施例のＦＭモジュール１００は、平均リード性能が２．２ＧＢ／ｓを上回っている限り、フラッシュメモリ１０７に第２方式で圧縮されているデータをリクラメーション時に第１方式で圧縮しなおして別のブロックに移動する操作を行う。【０１０３】
また、図９Ａ及び図９Ｂを用いて説明したように、平均リード性能が目標リード性能である２．２ＧＢ／ｓに近い場合には、ＦＭモジュール１００は、平均リード性能が目標リード性能を下回らないことを保証するため、第１方式で圧縮された格納データのうち、例えば、改善コストが最も小さい圧縮率レンジのデータを、リクラメーション時に第２方式で圧縮しなおして別のブロックに移動する操作を行う。【０１０４】
図１０は、ＦＭモジュール１００によるリクラメーション動作の一例を示すフローチャートである。ＦＭモジュール１００は、これにより、リード性能保証の下で格納データの圧縮率を最小化することが可能となる。【０１０５】
メモリコントローラ１０３は、未書き込みページを増やす必要があると判断すると、フラッシュメモリ１０７において無効データが最も多いブロックＸを選択する（８０１）。メモリコントローラ１０３は、ブロックＸ内の全ての有効データ（最新の論理データ）を書き込むための十分な未書き込みページを含むブロックＹを選択する（８０２）。【０１０６】
メモリコントローラ１０３は、ブロックＸ内の有効データの１つを、例えばランダムに選択して、読み出す（８０３）。メモリコントローラ１０３は、例えば、グラフ７６０を用いて説明した方法に従って平均リード性能７７０を算出する（８０４）。平均リード性能７７０は、フラッシュメモリ１０７のアクセス性能の一例である。メモリコントローラ１０３は、算出した平均リード性能７７０の値が所定値よりも高いか否かを判定する（８０５）。当該所定値は、目標リード性能２．２ＧＢ／ｓであってもよいし、平均リード性能が目標リード性能を下回る可能性を減らすために、目標リード性能にマージンが加えられた値（即ち、２．２ＧＢ／ｓ超の値）であってもよい。【０１０７】
メモリコントローラ１０３は、平均リード性能７７０の値が所定値以上であると判定した場合（８０５：ＹＥＳ）、圧縮率を小さくできる第１方式への変更を行うためにステップ８０６に遷移する。なお、メモリコントローラ１０３は、平均リード性能７７０の値が所定値以上であると判定した場合（８０５：ＹＥＳ）、ステップ８０９に遷移してもよい。【０１０８】
一方、メモリコントローラ１０３は、平均リード性能７７０の値が所定値よりも低いと判定した場合（８０５：ＮＯ）、リード性能を改善できる第２方式への変更を行うためにステップ８１３に遷移する。【０１０９】
メモリコントローラ１０３は、ＤＲＡＭ１０６上のアドレス変換テーブルを参照して、ステップ８０３でブロックＸから読み出した有効データの圧縮方式が第２方式か否かを判定する（８０６）。メモリコントローラ１０３は、当該有効データの圧縮方式が第２方式であると判定した場合（８０６：ＹＥＳ）、当該有効データを第２圧縮伸張回路１０５で伸張し、第１圧縮伸張回路１０４で圧縮する（８０７）。メモリコントローラ１０３は、変更評価テーブル７００の当該有効データに対応する列７２０のカウント値を更新し（８０８）、ステップ８０９に遷移する。【０１１０】
一方、メモリコントローラ１０３は、ステップ８０６で当該有効データの圧縮方式が第２方式でないと判定した場合（８０６：ＮＯ）、すでに当該有効データは第１方式で圧縮されているため、ステップ８０９に遷移する。メモリコントローラ１０３は、ブロックＹの未書き込みページに、第１方式で圧縮された有効データをライトする（８０９）。【０１１１】
一方、ステップ８１３では、メモリコントローラ１０３は、ＤＲＡＭ１０６上のアドレス変換テーブルを参照して、ブロックＸから読み出した有効データの圧縮方式が第１方式であるか否かを判定する（８１３）。メモリコントローラ１０３は、当該有効データの圧縮方式が第１方式でないと判定した場合（８１３：ＮＯ）、すでに当該データは第２方式で圧縮されているため、ステップ８０９に遷移する。【０１１２】
一方、メモリコントローラ１０３は、当該有効データの圧縮方式が第１方式であると判定した場合（８１３：ＹＥＳ）、例えば、変更評価テーブル７００において列７５０における改善コストが最小になる圧縮率レンジを調査する（８１４）。メモリコントローラ１０３は、例えば、当該有効データの圧縮率が、ステップ８１４で判明した最小の改善コストのレンジに属するか否かを判定する（８１５）。メモリコントローラ１０３は、当該有効データの圧縮率が当該レンジに属していないと判定した場合（８１５：ＮＯ）、圧縮方式の変更に伴う圧縮率悪化度が大きいので、圧縮方式変更をせずにステップ８０９に遷移する。【０１１３】
一方、メモリコントローラ１０３は、ステップ８１５で、当該有効データの圧縮率が当該レンジに属すると判定した場合（８１５：ＹＥＳ）、当該有効データを第１圧縮伸張回路１０４で伸張し、第２圧縮伸張回路１０５で圧縮する（８１６）。メモリコントローラ１０３は、変更評価テーブル７００の当該有効データに対応する列７２０のカウント値を更新し（８１７）、ステップ８０９に遷移する。【０１１４】
メモリコントローラ１０３はステップ８０９では、ブロックＹの未書き込みページに、第２方式で圧縮された有効データをライトする（８０９）。続いて、メモリコントローラ１０３は、ブロックＸ内にある当該有効データを無効化する（８１０）。そして、メモリコントローラ１０３は、ブロックＸ内にまだ有効データがあるか否かを判定する（８１１）。メモリコントローラ１０３は、ブロックＸ内に有効データがあると判定した場合（８１１：ＹＥＳ）、ステップ８０３に戻る。メモリコントローラ１０３は、ブロックＸ内に有効データがないと判定した場合（８１１：ＮＯ）、ブロックＸ内のデータは全て無効データであるため、ブロックＸを消去する（８１２）。【０１１５】
このように、本実施例のＦＭモジュール１００は、フラッシュメモリ１０７の未書き込みページの数を増やすリクラメーション動作での有効データ移動を利用して、リード性能保証の下で格納データの圧縮率を最小化することができる。【０１１６】
なお、メモリコントローラ１０３は、ステップ８０７やステップ８１６において圧縮方式を変更した際に、圧縮率が実際どれだけ変化したかを調べ、変化量に基づいて変更評価テーブル７００の列７３０の悪化度及び列７５０の改善コストを更新してもよい。これにより、メモリコントローラ１０３は、格納データの圧縮率をより小さくすることができる。【０１１７】
なお、ステップ８１４において、メモリコントローラ１０３は、例えば、列７５０における改善コストが小さい順に所定個数の圧縮率レンジを選択してもよいし、列７５０における改善コストが所定の第１閾値以下である全ての圧縮率レンジを選択してもよい。また、ステップ８１４において、メモリコントローラ１０３は、例えば、平均リード性能が所定の閾値未満であるか否かを判定してもよく、平均リード性能が所定の第２閾値以下であると判定した場合、列７５０における改善コストが正の値である全ての圧縮率レンジを選択してもよい。これらの場合において、メモリコントローラ１０３は、ステップ８１５において、当該有効データの圧縮率が選択した圧縮率レンジに属しているか否かを判定する。なお、第２閾値は、目標リード性能より小さい値である。
【実施例２】
【０１１８】
［１０］その他の実施例
実施例１はＦＭモジュール１００をストレージ装置９００へ適用する例を説明したが、本実施例では、実施例１のＦＭモジュール１００を一時的な記憶領域（キャッシュメモリ）として利用するサーバ装置などにも適用してもよい。キャッシュメモリのヒット率を向上してサーバ装置のデータアクセス時間を短縮するには、ＦＭモジュール１００の物理データ格納量を削減して、仮想的により多くの論理データを格納できるようにすることが重要であるため、実施例１のＦＭモジュール１００を当該サーバ装置に適用することは効果的である。【０１１９】
また、本実施形態では、ＦＭモジュール１００が、リクラメーション動作を利用して、リード性能保証の下で格納データの圧縮率を最小化する圧縮方式変更処理を行う例を説明したが、当該処理はリクラメーション動作時以外に実行されてもよい。具体的には、例えば、ＦＭモジュール１００は、リフレッシュ動作で行われる有効データの移動を利用して、圧縮方式変更処理を行うこともできる。フラッシュメモリは、データを書き込んでから長い時間が経つと、データ誤りが徐々に増加し、誤り訂正符号を用いても訂正できなくなってしまう。リフレッシュ動作とは、これを防ぐために、データを書き込んでから一定時間が経過したページからデータを読み出して誤りを訂正し、別の未書き込みページに移動し、元のデータを記録しているページを無効化する動作である。【０１２０】
リフレッシュ動作を利用した圧縮方式変更処理によりもたらされるデータ削減とリード性能保証の効果は、上記のリクラメーション動作を利用した圧縮方式変更処理による効果と同様である。本実施形態のＦＭモジュール１００は、圧縮方式変更処理をリクラメーション動作やリフレッシュ動作と同時に行うことで、圧縮方式変更を行うためだけにフラッシュメモリへの書き込み回数を余計に増やさないですむ。なお、圧縮率を小さくすることで、フラッシュメモリの書き込み回数を減らし、ストレージ装置の超寿命化を図ることができるため、本実施形態のように圧縮方式変更のためだけにフラッシュメモリへの余計な書き込み回数を増やさないことが望ましい。【０１２１】
なお、本発明は上記した実施例に限定されるものではなく、様々な変形例が含まれる。例えば、上記した実施例は本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施例の構成の一部を他の実施例の構成に置き換えることも可能であり、また、ある実施例の構成に他の実施例の構成を加えることも可能である。また、各実施例の構成の一部について、他の構成の追加・削除・置換をすることが可能である。【０１２２】
また、上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行することによりソフトウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等の記録装置、または、ＩＣカード、ＳＤカード、ＤＶＤ等の記録媒体に置くことができる。【０１２３】
また、制御線や情報線は説明上必要と考えられるものを示しており、製品上必ずしも全ての制御線や情報線を示しているとは限らない。実際には殆ど全ての構成が相互に接続されていると考えてもよい。
【図１】
0006692448.tif 000002
【図２】
0006692448.tif 000003
【図３】
0006692448.tif 000004
【図４】
0006692448.tif 000005
【図５】
0006692448.tif 000006
【図６】
0006692448.tif 000007
【図７】
0006692448.tif 000008
【図８】
0006692448.tif 000009
【図９Ａ】
0006692448.tif 000010
【図９Ｂ】
0006692448.tif 000011
【図１０】
0006692448.tif 000012