(57)【要約】  記憶デバイスは、複数の論理領域で構成された記憶媒体に基づく論理空間を上位装置に提供し、各論理領域について、基準データ範囲が記憶媒体に存在する。記憶デバイスは、ライト先論理アドレスが属するライト先論理領域に対応した基準データ範囲から基準データをリードし、基準データである第１データと、ライトデータに基づくデータとライトデータとのいずれかである第２データとの排他的論理和である差分データを作成する。記憶デバイスは、差分データを圧縮することにより圧縮差分データを作成し、圧縮差分データを記憶媒体にライトし、圧縮差分データがライトされた範囲である差分データ範囲をライト先論理領域に関連付ける。
2015128955.tif 000002
【特許請求の範囲】
【請求項１】
上位装置に接続される記憶デバイスであって、
記憶媒体と、
前記記憶媒体に対するＩ／Ｏ（Input/Output）を制御し前記記憶媒体に基づく論理空間を前記上位装置に提供する媒体コントローラと
を有し、
前記論理空間は、複数の論理領域で構成されており、
各論理領域について基準データ範囲が前記記憶媒体に存在し、
前記媒体コントローラは、
ライト先論理アドレスを指定したライトコマンドを前記上位装置から受信し、
前記ライト先論理アドレスが属するライト先論理領域に対応した基準データ範囲から基準データをリードし、
前記基準データである第１データと、前記ライトコマンドに従うライトデータに基づくデータと前記ライトデータとのいずれかである第２データとの排他的論理和である差分データを作成し、
前記差分データを圧縮することにより圧縮差分データを作成し、
前記圧縮差分データを前記記憶媒体にライトし、
前記圧縮差分データがライトされた範囲である差分データ範囲を前記ライト先論理領域に関連付ける、
記憶デバイス。
【請求項２】
前記媒体コントローラは、
前記第２データ又は前記第２データに基づくデータを圧縮することにより圧縮第２データを生成し、
前記圧縮第２データよりも前記圧縮差分データを含んだ第３データが小さければ、前記第３データを含む前記圧縮差分データを前記記憶媒体にライトし、
前記第３データは、前記圧縮差分データ、又は、前記第１データ内の１以上の保証コードであるコード部と前記圧縮差分データとで構成されたデータである、
請求項１記載の記憶デバイス。
【請求項３】
前記媒体コントローラは、前記第３データよりも前記圧縮第２データが小さければ、前記第３データではなく前記圧縮第２データを前記記憶媒体にライトし、
前記媒体コントローラは、前記圧縮第２データを前記記憶媒体にライトする場合、前記ライト先論理領域の基準データ範囲を、前記ライト先論理領域に関連付けられている基準データ範囲から、前記圧縮第２データがライトされた範囲である圧縮第２データ範囲に更新する、
請求項２記載の記憶デバイス。
【請求項４】
前記媒体コントローラは、前記圧縮第２データのサイズが前記第３データのサイズと同じであれば、前記第３データではなく前記圧縮第２データを前記記憶媒体にライトする、
請求項３記載の記憶デバイス。
【請求項５】
前記媒体コントローラは、前記第３データを前記記憶媒体にライトし、且つ、前記ライト先論理領域に既に差分データ範囲が関連付けられている場合、前記ライト先論理領域の差分データ範囲を、前記ライト先論理領域に関連付けられている差分データ範囲から、前記第３データがライトされた範囲である第３データ範囲に更新する、
請求項２記載の記憶デバイス。
【請求項６】
前記記憶媒体は、複数の物理領域で構成されており、物理領域単位でデータの入出力が行われるようになっており、
前記第１データは、物理領域単位の前記基準データであり、
前記第２データは、物理領域単位の前記ライトデータであり、
前記差分データは、物理領域単位の前記基準データと物理領域サイズの前記ライトデータとの排他的論理和である、
請求項１記載の記憶デバイス。
【請求項７】
前記記憶媒体は、複数の物理領域で構成されており、物理領域単位でデータの入出力が行われるようになっており、
前記第１データは、物理領域単位の前記基準データであり、
前記第２データは、物理領域単位の更新後データであり、
物理領域単位の前記更新後データは、
物理領域単位の前記基準データと物理領域単位未満の前記ライトデータとに基づいて生成されたデータ、又は、
物理領域単位の前記基準データと前記ライト先論理領域に関連付けられている前記差分データとの排他的論理和により生成された物理領域単位の更新前データと、物理領域単位未満の前記ライトデータとに基づいて生成されたデータ、
であり、
前記差分データは、物理領域単位の前記基準データと物理領域単位の前記更新後データとの排他的論理和である、
請求項１記載の記憶デバイス。
【請求項８】
前記記憶媒体は、複数の物理領域で構成されており、物理領域単位でデータの入出力が行われるようになっており、
前記ライト先論理領域を含む２以上の論理領域が同一の基準データ範囲に関連付けられており、
前記第１データは、物理領域単位のデータのうちの１以上の保証コード以外のデータ部である基準実データ部であり、
前記第２データは、物理領域単位の前記ライトデータのうちの１以上の保証コード以外のデータ部であるライト実データ部であり、
前記差分データは、前記基準実データ部と前記ライト実データ部との排他的論理和であり、
前記媒体コントローラは、前記圧縮差分データと、物理領域単位の前記ライトデータのうちの１以上の保証コードであるコード部とで構成された第３データを前記記憶媒体にライトする、
請求項１記載の記憶デバイス。
【請求項９】
前記媒体コントローラは、
物理領域単位の前記ライトデータを圧縮することにより圧縮ライトデータを生成し、
前記圧縮ライトデータよりも前記第３データが小さければ、前記第３データを前記記憶媒体にライトし、
前記第３データよりも前記圧縮ライトデータが小さければ、前記第３データではなく前記圧縮ライトデータを前記記憶媒体にライトする、
請求項８記載の記憶デバイス。
【請求項１０】
前記記憶媒体は、複数の物理領域で構成されており、物理領域単位でデータの入出力が行われるようになっており、
前記ライト先論理領域を含む２以上の論理領域が同一の基準データ範囲に関連付けられており、
前記第１データは、物理領域単位のデータのうちの１以上の保証コード以外のデータ部である基準実データ部であり、
前記第２データは、物理領域単位の更新後データであり、
物理領域単位の前記更新後データは、
前記基準実データ部と、前記ライト先論理領域に関連付けられており前記記憶媒体に格納されている１以上の保証コードである格納コード部とで構成されたデータ、又は、
物理領域単位の暫定データと、物理領域単位未満の前記ライトデータとに基づいて生成されたデータ、
であり、
物理領域単位の前記暫定データは、前記基準実データ部と前記ライト先論理領域に関連付けられている前記差分データとの排他的論理和により生成された更新前データと、前記格納コード部とで構成されたデータであり、
前記差分データは、物理領域単位の前記更新後データのうちの１以上の保証コード以外のデータ部である更新後実データ部と、前記基準実データ部との排他的論理和であり、
前記媒体コントローラは、前記圧縮差分データと、物理領域単位の前記更新後データのうちの１以上の保証コードであるコード部とで構成された第３データを前記記憶媒体にライトする、
請求項１記載の記憶デバイス。
【請求項１１】
前記媒体コントローラは、
物理領域単位の前記更新後データを圧縮することにより圧縮更新後データを生成し、
前記圧縮更新後データよりも前記第３データが小さければ、前記第３データを前記記憶媒体にライトし、
前記第３データよりも前記圧縮更新後データが小さければ、前記第３データではなく前記圧縮更新後データを前記記憶媒体にライトする、
請求項１０記載の記憶デバイス。
【請求項１２】
前記媒体コントローラは、前記差分データにおいて所定値の数が所定数以上であれば、前記第３データを前記記憶媒体にライトする、
請求項２記載の記憶デバイス。
【請求項１３】
前記媒体コントローラは、前記差分データが全て所定値で構成されたデータであれば、又は、前記ライトデータが所定パタンのデータであれば、前記圧縮第２データを前記記憶媒体にライトする、
請求項２記載の記憶デバイス。
【請求項１４】
記憶デバイスと、
前記記憶デバイスに対するＩ／Ｏを制御するプロセッサと
を有し、
前記記憶デバイスは、記憶媒体と、前記記憶媒体に対するＩ／Ｏを制御し前記記憶媒体に基づく論理空間を前記プロセッサに提供する媒体コントローラと
を有し、
前記論理空間は、複数の論理領域で構成されており、
各論理領域について基準データ範囲が前記記憶媒体に存在し、
前記媒体コントローラは、
ライト先論理アドレスを指定したライトコマンドを前記プロセッサから受信し、
前記ライト先論理アドレスが属するライト先論理領域に対応した基準データ範囲から基準データをリードし、
前記基準データである第１データと、前記ライトコマンドに従うライトデータに基づくデータと前記ライトデータとのいずれかである第２データとの排他的論理和である差分データを作成し、
前記差分データを圧縮することにより圧縮差分データを作成し、
前記圧縮差分データを前記記憶媒体にライトし、
前記圧縮差分データがライトされた範囲である差分データ範囲を前記ライト先論理領域に関連付ける、
装置。
【請求項１５】
記憶媒体に基づく空間であり複数の論理領域で構成された論理空間を上位装置に提供し、
ライト先論理アドレスを指定したライトコマンドを前記上位装置から受信し、
前記複数の論理領域に対応付けられている複数の基準データ範囲のうちの、前記ライト先論理アドレスが属するライト先論理領域に対応した基準データ範囲から、基準データをリードし、
前記基準データである第１データと、前記ライトコマンドに従うライトデータに基づくデータと前記ライトデータとのいずれかである第２データとの排他的論理和である差分データを作成し、
前記差分データを圧縮することにより圧縮差分データを作成し、
前記圧縮差分データを前記記憶媒体にライトし、
前記圧縮差分データがライトされた範囲である差分データ範囲を前記ライト先論理領域に関連付ける、
記憶制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、記憶制御に関し、例えば、記憶デバイス内の記憶媒体に書き込まれるデータの量を削減するための制御に関する。
【背景技術】
【０００２】
記憶デバイスは、一般に、記憶媒体と、記憶媒体に対するデータのＩ／Ｏ（Input/Output）を制御する媒体コントローラとを有する。記憶デバイスを有する装置として、例えば、ストレージ装置、又は、ストレージ装置にデータのＩ／Ｏを行うホスト装置がある。【０００３】
記憶媒体として、例えば、一括消去可能な不揮発性半導体メモリが開発されている。このような不揮発性半導体メモリとしては、例えば、フラッシュメモリがある。フラッシュメモリ（典型的にはＮＡＮＤ型フラッシュメモリ）は、複数のブロックを有し、各ブロックは、複数のページを有する。ページ単位でデータのＩ／Ｏが行われ、ブロック単位でデータが消去される。消去時間は書込み時間に比べて短い。そこで、フラッシュメモリの記録データ（書込み済のデータ）の更新は、一般に、次のように行われる。すなわち、媒体コントローラが、記録データ（更新前のデータ）をページから読み出し、記録データの少なくとも一部にライト対象データを反映することにより更新データを作成し、更新データを空ページに書き込み、記録データを記憶しているページを無効化（記憶デバイスの上位装置からの参照を不可とする処理）する。そして、媒体コントローラは、空ページが枯渇した場合には、全てが無効ページ（無効化されたページ）となったブロックからデータを消去することにより、無効ページを空ページとする。【０００４】
各ページは、複数（例えば１６個）のセクタを含む。ページ単位で書込みが行われるので、１セクタだけを書き換えるためであってもそのセクタを含む１ページを書き換える必要がある。【０００５】
フラッシュメモリは、一般に、データの消去回数に制限がある。データの書き換えが集中して消去回数が増大したブロックは、データの消去ができなくなり使用不能となってしまう。このため、特定のブロックにデータ消去処理が集中しないようにする必要がある。また、フラッシュメモリでは、ページ内のデータが、時間とともにデータ誤りが増加してしまうため、媒体コントローラは、書き込まれてから一定時間経過したデータを別ページに移動するリフレッシュと呼ばれる動作を行う。【０００６】
このような特性を持つフラッシュメモリにおいては、データの消去時間を短縮させたり、消去回数を低減させたりするために、特許文献１のような重複排除技術を用いることが考えられる。重複排除技術は、上位装置に提供する論理アドレスと実際の記憶領域の物理アドレスとが対応付けて管理されている場合に、重複するデータが格納された複数の論理アドレス空間（例えば論理ページ）を、当該データが格納された１つの物理アドレス空間（例えば物理ページ）に対応付ける技術である。重複排除技術を利用することにより、記憶媒体に書き込まれるデータの量を削減することができ、フラッシュメモリを記憶媒体とする記憶デバイスにおいて、フラッシュメモリの長寿命化を図ることができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特表２０１３−５３２８５３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１の重複排除技術は、重複するデータを持つ複数の論理ページに対して１つの物理ページを割り当てることで、書込み量（フラッシュメモリに書き込まれるデータの量）を低減化する。しかし、それらの論理ページの各々に対してわずかなデータ更新が行われるだけで、各更新先論理ページ内のデータは、重複排除の対象から外れてしまい、各更新先論理ページには、更新データが書き込まれた新たな物理ページが割り当てられることになる。これにより、書込み量が増加する。【０００９】
この種の問題は、重複排除されている論理ページに限られない。例えば、重複排除されていない論理ページについて、その論理ページに対してわずかなデータ更新があっただけで、更新データが新たな物理ページに書き込まれる（つまり、物理ページが新たに消費される）。【００１０】
また、この種の問題は、フラッシュメモリに限らず、消去回数（書き換え回数）に制限のある他種の記憶媒体についても有り得る。【００１１】
本発明の目的は、記憶デバイスの記憶媒体への書込み量を削減することにある。
【課題を解決するための手段】
【００１２】
記憶デバイスは、記憶媒体と、記憶媒体に対するＩ／Ｏを制御し記憶媒体に基づく論理空間を上位装置に提供する媒体コントローラとを有する。論理空間は、複数の論理領域で構成されている。各論理領域について、基準データ範囲が記憶媒体に存在する。媒体コントローラは、ライト先論理アドレスを指定したライトコマンドを上位装置から受信し、ライト先論理アドレスが属するライト先論理領域に対応した基準データ範囲から基準データをリードする。媒体コントローラは、基準データである第１データと、ライトコマンドに従うライトデータに基づくデータとライトデータとのいずれかである第２データとの排他的論理和である差分データを作成する。媒体コントローラは、差分データを圧縮することにより圧縮差分データを作成し、圧縮差分データを記憶媒体にライトし、圧縮差分データがライトされた範囲である差分データ範囲をライト先論理領域に関連付ける。媒体コントローラは、ライト先論理領域と同じ論理領域をリード元としたリードコマンドを上位装置から受信した場合、リード元論理領域に関連付けられている基準データと、リード元論理領域に関連付けられている差分データとを基に、リードコマンドに従うリードデータを復元することができる。
【発明の効果】
【００１３】
記憶デバイス内の記憶媒体の書込み量を削減することができ、以って、記憶媒体の長寿命化を図ることができる。
【図面の簡単な説明】
【００１４】
【図１】図１は、実施例に係るＦＭモジュールの構成を示す。
【図２Ａ】図２Ａは、単独割当ページのためのデータフォーマット（平文状態）を示す。
【図２Ｂ】図２Ｂは、重複割当ページのためのセクタ部フォーマット（平文状態）を示す。
【図２Ｃ】図２Ｃは、重複割当ページのためのコード部フォーマットを示す。
【図３】図３は、フラッシュメモリへのデータライト方法とデータ格納状態の例を示す。
【図４Ａ】図４Ａは、アドレス変換テーブルを示す。
【図４Ｂ】図４Ｂは、重複カウントテーブルを示す。
【図５】図５は、ライトコマンド処理のフローチャートである。
【図６】図６は、単独割当ページに対する全体ライト処理のフローチャートである。
【図７】図７は、単独割当ページに対する部分ライト処理のフローチャートである。
【図８】図８は、重複割当ページに対する全体ライト処理のフローチャートである。
【図９】図９は、重複割当ページに対する部分ライト処理のフローチャートである。
【図１０】図１０は、単独割当ページに対する全体ライト処理の概念図である。
【図１１】図１１は、単独割当ページに対する部分ライト処理の概念図である。
【図１２】図１２は、重複割当ページに対する全体ライト処理の概念図である。
【図１３】図１３は、重複割当ページに対する部分ライト処理の概念図である。
【図１４】図１４は、実施例に係るストレージ装置を有する計算機システムの構成を示す。
【図１５Ａ】図１５Ａは、単独割当ページのユーザデータの２通りの形成方法を示す。
【図１５Ｂ】図１５Ｂは、重複割当ページのユーザデータの２通りの形成方法を示す。
【図１６】図１６は、ホストの構成を示す。
【発明を実施するための形態】
【００１５】
以下、一実施例を説明する。
【００１６】
以下の説明では、「ｋｋｋテーブル」の表現にて情報を説明することがあるが、情報は、テーブル以外のデータ構造で表現されていてもよい。データ構造に依存しないことを示すために「ｋｋｋテーブル」を「ｋｋｋ情報」と呼ぶことができる。
【００１７】
また、以下の説明では、通信インターフェイスデバイスを「Ｉ／Ｆ」と略記することがあり、フラッシュメモリを「ＦＭ」と略記することがある。
【００１８】
以下、実施例に係る記憶デバイスが適用されたＦＭモジュールと、そのＦＭモジュールを有するストレージ装置を説明する。
【００１９】
図１４は、実施例に係るストレージ装置を有する計算機システムの構成を示す。
【００２０】
計算機システムは、ストレージ装置１４００と、ホスト（ホスト計算機）１４２１と、管理計算機１４２０とを有する。ホスト１４２１は、ＳＡＮ（Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）１４１０のような通信ネットワークを介してストレージ装置１４００に接続されてよい。管理計算機１４２０は、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）のような通信ネットワーク（図示せず）を介してストレージ装置１４００に接続されてよい。ホスト１４２１及び管理計算機１４２０は同じ通信ネットワークに接続されてよい。
【００２１】
ストレージ装置１４００は、複数のＦＭモジュール１００と、複数のＦＭモジュール１００に対するＩ／Ｏを制御するストレージコントローラ１４０１とを有する。ストレージコントローラ１４０１は、ホスト１４２１から送信されたコマンドを受信し、そのコマンドを解釈して、ストレージ装置１４００の記憶領域内のデータのリード／ライトを実行する。ストレージ装置１４００は、Ｈ−Ｉ／Ｆ（ホスト１４２１と通信するＩ／Ｆ）１４３１、Ｓ−Ｉ／Ｆ（ＦＭモジュール１００と通信するＩ／Ｆ）１４５１、Ｍ−Ｉ／Ｆ（管理計算機１４２０と通信するＩ／Ｆ）１４３０、メモリ１４４２、及び、それらに接続されたＣＰＵ１４４１を有する。
【００２２】
Ｈ−Ｉ／Ｆ１４３１は、ホスト１４２１からのＩ／Ｏリクエストや制御コマンドなどを受け付けるＩ／Ｆである。Ｓ−Ｉ／Ｆ１４５１は、ＦＭモジュール１００にデータや制御コマンドを送信するＩ／Ｆである。また、Ｍ−Ｉ／Ｆ１４３０は、管理計算機１４２０からの管理や保守に関する制御コマンド等を受け付けるＩ／Ｆである。
【００２３】
ＣＰＵ１４４１は、演算処理装置として機能し、メモリ１４４２に記憶されている各種プログラムや演算パラメータ等にしたがって、ストレージ装置１４００全体の動作を制御する機能を有する。具体的には、例えば、ＣＰＵ１４４１は、ホスト１４２１からのＩ／Ｏリクエスト等に従い、ストレージ装置１４００とホストとの間のユーザデータの入出力（データＩ／Ｏ）を処理し、ＦＭモジュール１００にユーザデータをライトするためのライトコマンドをＦＭモジュール１００に発行したり、ＦＭモジュール１００からユーザデータをリードしたりするためのリードコマンドをＦＭモジュール１００に発行したりする。また、ＣＰＵ１４４１は、ホスト１４２１から受け付けたユーザデータに対して保証コード（後述。）を作成して、ユーザデータに付与する。メモリ１４４２は、各種プログラムや演算パラメータ等の他、管理情報を記憶する。また、メモリ１４４２は、キャッシュメモリ領域を有する。キャッシュメモリ領域は、ＦＭモジュール１００にライトするユーザデータや、ＦＭモジュール１００からリードしたユーザデータを一時的に格納する。なお、本実施例の説明において、「ユーザデータ」とは、ストレージコントローラ１４０１にとっては、主に、ホスト１４２１からのリード／ライトリクエスト（Ｉ／Ｏリクエスト）に従うリード／ライト対象のデータでよく、ＦＭモジュール１００内のＦＭコントローラ１０３（図１参照）にとっては、ストレージコントローラ１４０１からのリード／ライトコマンドに従うリード／ライト対象のデータでよい。
【００２４】
図１４では、ＦＭモジュール１００は６つ備えられている構成としているが、ＦＭモジュール１００の数はかかる例に限定されない。ＦＭモジュール１００の内部構成については、図１を用いて後で詳細に説明する。なお、本実施例では、ＦＭモジュール１００は、ストレージ装置１４００内に存在するが、かかる例に限定されず、ＦＭモジュール１００を、ストレージ装置１４００の外に存在してもよい。
【００２５】
ホスト１４２１は、ＳＡＮ１４１０を介してストレージ装置１４００と接続され、ストレージ装置１４００にデータのリード／ライトリクエスト（Ｉ／Ｏリクエスト）を送信する。また、ホスト１４２１は、例えば、パーソナルコンピュータ、ワークステーション又はメインフレームでよい。ホストとストレージ装置１４００との通信は、例えば、ＳＣＳＩ（Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ）などのブロックプロトコルが用いられてよい。
【００２６】
管理計算機１４２０は、例えば、パーソナルコンピュータや、ワークステーション又はメインフレームでよい。管理計算機１４２０は、ストレージ装置１４００等を管理してよい。
【００２７】
図１４の構成によれば、ＦＭモジュール１００の上位装置は、ストレージコントローラ１４０１である。ＦＭモジュールは、後に図１を参照して説明するように、複数のＦＭチップで構成されたフラッシュメモリ１０５と、フラッシュメモリ１０５に対するＩ／Ｏを制御するＦＭコントローラ１０３とを有する。以下、フラッシュメモリ１０５の特徴と扱い方の一例を説明する。
【００２８】
フラッシュメモリ１０５は、最小消去単位が最小書き込み単位に比べて大きいという特徴を有する。具体的には、例えば、フラッシュメモリ１０５（各ＦＭチップ）は、複数のブロック（物理ブロック）を有し、各ブロックが、複数（例えば２５６個）のページ（物理ページ）を有する。ブロック単位でデータが消去され、ページ単位でデータの読み書きが実行される。ページのサイズは例えば８６４０バイトである。フラッシュメモリ１０５は、その特性上、データを直接上書きすることができない。すなわち、データを書き換える場合、ＦＭコントローラ１０３は、そのデータを含むブロック内に記憶している有効な他のデータを別のブロックに退避させて、元のブロックからデータを消去する。そして、ＦＭコントローラ１０３は、消去したブロックに新しいデータをページ単位で書き込むことにより、データの書き換えを行う。
【００２９】
このように、フラッシュメモリ１０５におけるデータの書き換え処理では、ブロック単位（物理ブロック単位）のデータの消去が伴う。しかしながら、フラッシュメモリ１０５の１ブロック分のデータ消去にかかる時間は、１ページ分のデータを書き込むのに要する時間と比べて長い時間（例えば約１桁分長い時間）がかかる。したがって、１ページ分のデータを書き換えるために毎回１ブロック分のデータ消去を実行すると、フラッシュメモリ１０５のデータ書き換え性能が低下してしまう。フラッシュメモリ１０５からデータを消去する時間を隠ぺいできるアルゴリズムでデータを書き込むことが必要となる。
【００３０】
通常、フラッシュメモリ１０５に対してデータの書き換えを行う場合には、データを書き換えるごとにデータを消去することは行わず、データが記録されていない未使用ページ（空の物理ページ）にデータを追記する方式によってデータの書き換えが行われる。しかし、データの書き換え処理が度重なって実行されると、フラッシュメモリ１０５内の未使用ページが枯渇してしまうため、フラッシュメモリ１０５に書き込まれている無効データ（書き換えた後の旧データなど）を消去して、ページを再利用可能な状態にする必要が生じる。そこで、ＦＭコントローラ１０３は、旧データを含むブロック内の有効なデータのみを別のブロック内の未使用ページにコピーし、コピー元のブロックからデータを消去して未使用ブロックとして再生するブロック再生処理を実行する。この処理は、フラッシュメモリ１０５のデータを高速に書き換えるには必須の処理であり、特に無効データが多くなったブロックが優先的にコピー元のブロックとされる。
【００３１】
一方、フラッシュメモリ１０５の各ブロックは、消去回数に制限がある。例えば、１ブロック当たり１万回までの消去回数が保証される。この場合、データの書き換えが１つのブロックに集中して、当該ブロックの消去回数が保証回数（上限）を超えると、データ消去ができなくなることがあり、そのブロックは以降使用不能となってしまい、使用可能なブロック数が減少するという問題がある。そこで、特定ブロックに対する消去処理が集中しないように、消去回数の多いブロックと少ないブロックの間で格納データを交換するなどして消去回数の平準化処理を行う必要がある。
【００３２】
また、フラッシュメモリ１０５は、一度書き込みしたページについては、データを保持しておくだけでも時間経過とともにデータ誤りが増加していくという特徴を有する。データ誤りによるデータ損失を回避するために、ＦＭコントローラ１０３は、ページに書き込むデータに誤り訂正符号（ＥＣＣ：Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ  Ｃｏｄｅ）に基づくパリティがあらかじめ付加する。ＦＭコントローラ１０３は、書き込み後一定時間を経過したデータを読み出し、データ誤りが少ないうちに当該パリティを用いてそれを訂正して、訂正後のデータを別ページに移動するリフレッシュ処理を行う。なお、この処理を実行する場合にも、ＦＭコントローラ１０３は、消去回数を平準化したり、性能に対する影響を考慮したりする必要がある。
【００３３】
このように、ＦＭコントローラ１０３は、消去時間を隠ぺいしたり消去回数を平準化したりするために、上位装置に提供する論理アドレスと実際の記憶領域の物理アドレスとを動的に対応づけ、データの書き込みの際に論理アドレスから物理アドレスへの変換処理を行う。すなわち、上位装置に提供する論理アドレスとフラッシュメモリ１０５の物理アドレスとの対応を動的にＦＭコントローラ１０３により変更することにより、上位装置は、論理アドレス空間にデータを書き込めばよい。データ書き込み時における未使用ページへの追記に伴う物理アドレスの変更を上位装置が意識しなくてもよいように、ＦＭコントローラ１０３はアドレスを管理する。
【００３４】
さて、フラッシュメモリ１０５を有するＦＭモジュール１００において、論理アドレスと物理アドレスとを対応付けて管理している場合、重複排除技術を適用することが有効である。重複排除技術とは、重複するデータが格納された複数の論理アドレス空間を、当該データが格納された１つの物理アドレス空間に対応付ける技術である。重複排除技術により、フラッシュメモリ１０５の書込み量を削減できる。特に、重複排除技術の適用が有効と考えられるケースとして、フォーマット処理が考えられる。
【００３５】
ストレージコントローラ１４０１は、ＦＭモジュール１００の使用を開始する際に、その異常個所の検知や格納データの初期化を目的として、フォーマット処理を実行する。具体的には、例えば、ストレージコントローラ１４０１は、ＦＭモジュール１００に基づく全記憶領域に、特定の値が連続する単純パタンのデータ（例えば全ビットが「０」のデータであるオールゼロデータ）を書き込む。しかし、フォーマット処理は、フラッシュメモリ１０５のように書き換え回数が制限されている記憶媒体において、不必要に書き換え回数を増加させる。また、フラッシュメモリ１０５は、データの書き換えに対して未使用ページへの追記方式を採用しているため、未使用ページの消費が増えると、処理時間のかかるデータ消去処理を頻繁に実行しなければならない。すなわち、フォーマット処理は、未使用ページが減少させ且つ性能を損なう処理である。そこで、本実施例では、ＦＭモジュール１００に重複排除技術が適用され、それにより、データの書込み量が低減し、以って、フラッシュメモリ１０５の長寿命化が図られる。なお、ＦＭコントローラ１０３は、書込み対象のデータのパタンをチェックすることにより、或いは、ストレージコントローラ１４０１からの通知により（例えば、ストレージコントローラ１４０１からのライトコマンドにフォーマットであることを意味する値が設定されていることにより）、書込み対象のデータがフォーマット処理により書き込まれるデータであることを検出できる。
【００３６】
さらに、ストレージ装置１４００は、ハードウェア障害などによりユーザデータに発生するビット化けや、内部制御エラーなどによって発生する不正アドレスへのユーザデータ書き込みや不正アドレスからのユーザデータ読み込みを検出することができる。そのため、ストレージコントローラ１４０１は、書き込むユーザデータをセクタ単位（例えば１セクタは５１２バイト）に分けて複数のセクタデータで構成し、それぞれに対して所定長さ（例えば１６バイト）の保証コードを付与する。一般に、保証コードは、ＣＰＵ１４４１がユーザデータのビット化けを検出することを目的に各セクタデータから算出されるＣＲＣ（Ｃｙｃｌｉｃ  Ｒｅｄｕｎｄａｎｃｙ  Ｃｈｅｃｋ）を含む。また、保証コードは、ストレージ装置ベンダが自由に設定できるユーザデータの関連情報（以下、メタデータ）を含んでよい。メタデータは、例えば、計算機システムにおけるユーザデータの論理的な格納位置のような情報（具体的には、例えば、論理ボリューム番号や論理セクタアドレスなど）、ユーザデータの更新日時のような情報、及び、ユーザデータの世代番号のような情報のうちの少なくとも１つでよい。なお、論理ボリュームは、ストレージ装置１４００によりホスト１４２１に提供される論理的な記憶デバイスである。ホスト１４２１からのＩ／Ｏリクエストでは、論理ボリュームの論理アドレスが指定される。その論理アドレスに従う領域（論理ボリュームにおける領域）に、１以上のＦＭモジュール１００の各々が提供する１以上の論理ページが対応する。Ｉ／Ｏリクエストで指定されている論理アドレスを基に、ＦＭモジュール１００に送信されるＩ／Ｏコマンドで指定される論理アドレスがストレージコントローラ１４０１により決められる。
【００３７】
保証コードが付与されたセクタデータから構成されるユーザデータに対して重複排除を行う場合、保証コード値がセクタデータ毎に異なるため、セクタデータが同じ値であっても保証コードに差異があるため重複排除を行うことができないという問題が発生することがある。
【００３８】
そこで、ＦＭコントローラ１０３は、重複排除処理を行う際には、まず、保証コードを含むユーザデータから、セクタデータと保証コードとを分離し、セクタデータのみを集めたもの（以下、セクタ部）を重複排除時のデータ共有の対象とし、保証コードのみを集めたもの（以下、コード部）を、セクタ部とは別に管理する。セクタ部及びコード部は、それぞれ独立したものとしてフラッシュメモリ１０５に格納される。なお、重複排除処理を行わないユーザデータについては、セクタ部とコード部への分離は行われずにフラッシュメモリ１０５に格納される。
【００３９】
以下の説明においては、重複排除処理を行うことによって、或る論理ページのためのデータを格納している物理ページのデータが、他の論理ページのためのデータとして共有されている場合、その論理ページを、「重複割当ページ」と呼ぶこととする。また、ある論理ページのためのデータを格納している物理ページのデータが、他のどの論理ページのためのデータとしても共有されていない場合、その論理ページを、「単独割当ページ」と呼ぶこととする。
【００４０】
ＦＭコントローラ１０３は、さらに、フラッシュメモリ１０５に格納するデータを可逆圧縮アルゴリズムによって圧縮することにより、フラッシュメモリ１０５の書込み量を削減する。可逆圧縮アルゴリズムとしては、例えばＬＺ７７アルゴリズムを適用する。このアルゴリズムによれば、例えば、同じ値（例えばゼロ）が長く連続するパタンを多く含むデータについては圧縮によるデータ削減効果が高い。
【００４１】
次に、図１を参照しながら、ＦＭモジュール１００の構成を説明する。
【００４２】
ＦＭモジュール１００は、複数のＦＭチップで構成されたフラッシュメモリ１０５と、フラッシュメモリ１０５に対するリード／ライトを制御するＦＭコントローラ１０３とを有する。ＦＭコントローラ１０３は、上位装置（ストレージコントローラ１４０１）に接続される上位Ｉ／Ｆ１０２、メモリ（例えば揮発性メモリ）の一例であるＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１０６、及び、それらに接続されたコントローラ本体１０１を有する。コントローラ本体１０１は、圧縮伸張回路１０４及びＸＯＲ回路１０７を含む。コントローラ本体１０１は、上位Ｉ／Ｆ１０２、フラッシュメモリ１０５及びＤＲＡＭ１０６を制御するプロセッサ（マイクロプロセッサ）を含んでよい。プロセッサは、上位Ｉ／Ｆ１０２を通じて受信したリード／ライトコマンドを解釈したり、リード／ライトデータを送受信したり、圧縮伸張回路１０４にデータの圧縮／伸張を実行させたり、ＸＯＲ回路１０７に排他的論理和計算を実行させたり、フラッシュメモリ１０５とＤＲＡＭ１０６との間のデータ転送を実行したりできる。
【００４３】
上位Ｉ／Ｆ１０２は、上位装置から発行されたライトコマンドに従うユーザデータを上位装置から受信したり、上位装置から発行されたリードコマンドに従うユーザデータを上位装置に送信したりする。
【００４４】
圧縮伸張回路１０４は、ＦＭコントローラ１０３内にハードウェア（論理回路）として実装された演算器でよく、所定の可逆変換圧縮アルゴリズム（例えばＬＺ７７アルゴリズム）によって、平文（平文状態のデータ）を可逆的に圧縮することにより圧縮データ（圧縮状態のデータ）を作成すしたり、圧縮データを伸張することにより元の平文データを作成したりできる。
【００４５】
ＸＯＲ回路１０７は、ＦＭコントローラ１０３内にハードウェア（論理回路）として実装された演算器でよく、同じサイズの２つのデータの排他的論理和を計算し、それらと同じサイズのデータを作成できる。排他的論理和とは、２つのデータの同じ位置に等しい値があると０を作成し、異なる値があると１を作成する演算である。よって、ＸＯＲ回路１０７に入力される２つのデータがよく似たデータであるほど、作成されるデータはゼロ値が長く連続するパタンが多く含まれるデータとなる。なお、このようなデータは、上記の圧縮アルゴリズムで圧縮することでデータ量を大きく削減することができる。
【００４６】
ＤＲＡＭ１０６は、上位装置から受信したライトデータ（フラッシュメモリ１０５に書き込まれるデータ）、及び、上位装置へ送信するリードデータ（フラッシュメモリ１０５から読み出されたデータ）を一時的に格納する。また、ＤＲＡＭ１０６は、フラッシュメモリ１０５にライトされるデータを一時的に格納するライトバッファとして機能する。また、ＤＲＡＭ１０６は、フラッシュメモリ１０５からリードしたデータを一時的に格納するリードバッファとして機能する。また、ＤＲＡＭ１０６は、圧縮伸張回路１０４により圧縮／伸張するデータの転送元、および、圧縮／伸張の結果データ（圧縮データ／平文データ）の転送先として機能する。また、ＤＲＡＭ１０６は、ＸＯＲ回路１０７により排他的論理和を計算する２つのデータの転送元、および、ＸＯＲ回路１０７による作成結果データの転送先として機能する。
【００４７】
次に、図２Ａ、図２Ｂ、図２Ｃを参照しながら、フラッシュメモリ１０５に書き込まれるデータに適用されるデータフォーマットについて説明する。
【００４８】
図２Ａは、単独割当ページに書き込まれる平文ユーザデータ（平文状態のユーザデータ）のデータフォーマットを示す。
【００４９】
保証コードを含むユーザデータ（Ｄｉ，Ｇｉ）２００は、平文状態で８４４８バイトの長さを持ち、１６個の５１２バイトのセクタデータ（２０１、２０２、２０３、…、２０４）を含み、それぞれに１６バイトの保証コード（２１１、２１２、２１３、…、２１４）が付加されている。
【００５０】
ＦＭコントローラ１０３は、単独割当ページの平文ユーザデータを圧縮し圧縮ユーザデータ（圧縮状態のユーザデータ）をフラッシュメモリ１０５に書き込む。本実施例では、単独割当ページのユーザデータについて２通りの形成方法がある。第１の形成方法によれば、単独割当ページのユーザデータは、ユーザデータそのものであり、第２の形成方法によれば、単独割当ページのユーザデータは、基準データ（８４４８バイト）と差分データ（８４４８バイト）の排他的論理和である。第１の形成方法によれば、ＦＭコントローラ１０３は、ユーザデータそのものを圧縮してフラッシュメモリ１０５に書き込む。第２の形成方法によれば、ＦＭコントローラ１０３は、基準データおよび差分データをそれぞれ圧縮して別々にフラッシュメモリ１０５に書き込む。そのため、ＦＭコントローラ１０３は、第２の形成方法に従うユーザデータを復元するには、フラッシュメモリ１０５から読み出した基準データおよび差分データをそれぞれ圧縮伸張回路１０４により伸張して平文状態に戻し、さらに、平文状態の基準データ及び差分データの排他的論理和データをＸＯＲ回路１０７より作成する必要がある。
【００５１】
図１５Ａは、２通りの形成方法の概念図である。ここでは、第１の形成方法におけるユーザデータそのものも「基準データ」と呼ぶことがある。
【００５２】
本実施例によれば、単独割当ページのユーザデータに第２の形成方法を適用することで、フラッシュメモリ１０５の書込み量を削減できる。その理由を以下に示す。
【００５３】
例えば、更新前のユーザデータと更新後のユーザデータの違いは１００ビット目だけ（１ビットだけ）であるとする。従来技術によれば、違いがわずか１ビットでも、更新前のユーザデータを無効化し、更新後のユーザデータを圧縮してフラッシュメモリ１０５へ格納しなければならない。しかし、本実施例の第２の形成方法によれば、基準データが、更新前のユーザデータであり、差分データが、１００ビット目が１で残り全部のビットが０のデータである。これにより、フラッシュメモリ１０５に更新前のユーザデータが有効データのまま残り、圧縮された差分データが更に有効データとして書き込まれる。このとき、差分データは、ゼロ値が長く連続するパタンを含むデータであるため、圧縮状態の差分データの量は非常に小さくなる。結果として、圧縮された更新後ユーザデータのサイズよりも、圧縮された更新前ユーザデータと圧縮された差分データの合計サイズの方が小さい。
【００５４】
このように、本実施例によれば、更新前後のユーザデータに一致する部分が多い場合に、フラッシュメモリ１０５の書込み量を削減でき、フラッシュメモリ１０５の長寿命化を図ることができる。
【００５５】
一方、図２Ｂは、重複割当ページの平文ユーザデータから分離されたセクタ部である平文セクタ部のデータフォーマットを示す。セクタ部Ｄｊ２２０は、平文状態で８１９２バイトの長さを持ち、１６個の５１２バイトのセクタデータ（２２１、２２２、２２３、…、２２４）で構成される。
【００５６】
図２Ｃは、重複割当ページの平文ユーザデータから分離された平文コード部のデータフォーマットを示す。コード部Ｇｊ２３０は、２５６バイトの長さを持ち、１６個の１６バイトの保証コード（２３１、２３２、２３３、…、２３４）で構成される。
【００５７】
重複割当ページのユーザデータとして、フラッシュメモリ１０５には、図２Ｂのフォーマットに従う平文セクタ部が圧縮されたセクタ部と、図２Ｃのフォーマットに従う平文コード部とが書き込まれる。ＦＭモジュール１００では、重複割当ページのセクタ部について２通りの形成方法がある。第１の形成方法によれば、重複割当ページのセクタ部は、ユーザデータから分離されたセクタ部そのものである。第２の形成方法によれば、基準データ（８１９２バイト）と差分データ（８１９２バイト）の排他的論理和である。第１の形成方法の場合、セクタ部そのものが圧縮されてフラッシュメモリ１０５に書き込まれる。第２の形成方法の場合、基準データおよび差分データがそれぞれ圧縮され別々にフラッシュメモリ１０５に書き込まれる。そのため、セクタ部を復元するには、ＦＭコントローラ１０３は、フラッシュメモリ１０５から読み出した基準データおよび差分データをそれぞれ圧縮伸張回路１０４により伸張し、平文状態の基準データ及び差分データの排他的論理和データをＸＯＲ回路１０７により作成する。ＦＭモジュール１００では、重複割当ページのセクタ部が第１の形成方法に従うセクタ部の場合、セクタ部そのものが複数の論理ページで共有される。すなわち、重複割当ページに割り当てられた物理ページ内のセクタ部が、複数の論理ページ（重複割当ページ）で共有される。一方、重複割当ページのセクタ部が第２の形成方法に従うセクタ部の場合、基準データが、複数の論理ページ（重複割当ページ）で共有され、差分データが、重複割当ページ毎に個別に管理される。なお、重複割当ページのコード部は、どちらの形成方法の場合も、重複割当ページ毎に個別に管理される。図１５Ｂは、例えば、第１の形成方法を適用したユーザデータＡとＤ、第２の形成方法を適用したユーザデータＢとＣが、基準データを共有している様子を示した概念図である。ここでは、第１の形成方法におけるセクタ部そのものも基準データと呼ぶことにする。
【００５８】
本実施例によれば、重複割当ページのセクタ部において、第１の形成方法に加えて第２の形成方法も適用するため、フラッシュメモリ１０５の書込み量を削減することができる。その理由を以下に示す。
【００５９】
例えば、図１５Ｂにおいて、ユーザデータＡのセクタ部とユーザデータＢのセクタ部の違いが１００ビット目だけ（１ビットだけ）であるとする。従来技術（特許文献１も含む）が適用された場合、両者は異なるデータと判断され、重複割当ページとして管理されず、それぞれ別々に圧縮してフラッシュメモリ１０５へ格納される。本実施例では、ユーザデータＢのセクタ部に第２の形成方法が適用されることで、ユーザデータＡのセクタ部が基準データとなり、１００ビット目が１で残り全部のビットが０のデータが差分データＢとなる。これにより、フラッシュメモリ１０５には、圧縮された基準データ（セクタ部）と、圧縮された差分データＢが書き込まれる。このとき、差分データＢはゼロ値が長く連続するパタンを含むデータであるため、サイズは非常に小さくなる。結果として、ユーザデータＡのセクタ部とユーザデータＢのセクタ部を別々に圧縮してフラッシュメモリ１０５へ書き込まれるよりも、書込み量が少なくなる。
【００６０】
このように、本実施例によれば、複数の論理ページのセクタ部が完全に一致する場合のみならず、複数の論理ページのセクタ部に一致する部分が多い場合にも、重複排除を適用することで、フラッシュメモリ１０５の書込み量を削減でき、フラッシュメモリ１０５の長寿命化を図ることができる。
【００６１】
次に、図３を参照しながら、フラッシュメモリ１０５へのデータライト方法を示す。なお、図３において、塗りつぶし（模様）は、データ（ユーザデータ、セクタ部又はコード部）であることを意味し、白塗りは、ダミーデータ（ヌルデータ）であることを意味する。
【００６２】
これまで説明してきたように、ＦＭコントローラ１０３は、図２Ａまたは図２Ｂのデータフォーマットに従う基準データや差分データを、フラッシュメモリ１０５の書込み量を削減するために、圧縮伸張回路１０４により圧縮してからフラッシュメモリ１０５に書き込む。圧縮データのサイズは元の平文データ（平文データの構成）によって様々である。同じ値が連続するパタンを多く含むデータのサイズは圧縮により小さくなるが、ランダムパタンを多く含むデータのサイズは圧縮により大きくなることがある。それらの圧縮データ、および図２Ｃのデータフォーマットに従うコード部は、図３の左側に示すように、フラッシュメモリ１０５へライトされるまでＤＲＡＭ１０６上のライトバッファで一時的に格納される。フラッシュメモリ１０５は、ページ単位でしかライトできないという特徴を持つため、ＦＭコントローラ１０３は、ライトバッファの中の圧縮データを連結して、ページサイズ３１１を超えない最大サイズのデータを作り（連結されたデータの合計がページサイズ３１１に満たない場合は、連結されたデータにダミーデータを連結することでページサイズ３１１のデータを作り）、その作られたデータを、フラッシュメモリ１０５の未使用ページ３０５（例えば、物理ページＰ４）にライトする。ページ単位にデータをライトすることを「ページライト」と呼ぶことがある。ページライトのデータには誤り訂正符号に基づくパリティ（図示せず）が付加される。パリティの書込み先領域を提供するために、フラッシュメモリ１０５の物理ページのサイズ（８６４０バイト）は１つの論理ページのサイズ（８４４８バイト）よりも大きくなっている。
【００６３】
図３の右側には、フラッシュメモリ１０５の物理ページＰ０〜Ｐ３（３０１、３０２、３０３、３０４）に、圧縮データやコード部が格納されている状態の一例を示す。物理ページＰ０には、単独割当ページＬ０及びＬ６のそれぞれの基準データと、重複割当ページＬ４の差分データが格納されている。物理ページＰ１には、重複割当ページＬ１、Ｌ３、Ｌ４及びＬ７が共有する基準データが格納されている。物理ページＰ２には、単独割当ページＬ０の差分データ、及び、単独割当ページＬ５の基準データが格納されている。物理ページＰ３には、重複割当ページＬ１、Ｌ３、Ｌ４及びＬ７のそれぞれのコード部と、単独割当ページＬ２の基準データが格納されている。
【００６４】
次に、図４Ａ、図４Ｂを参照しながら、フラッシュメモリ１０５にユーザデータがどのように格納されているかをＦＭコントローラ１０３が管理するために、ＤＲＡＭ１０６上に作成するアドレス変換テーブルと重複カウントテーブルについて説明する。
【００６５】
図４Ａのアドレス変換テーブル４００は、論理ページ毎に、論理ページアドレス４１０、基準データ格納先４２０、差分フラグ４３０、差分データ格納先４４０、重複フラグ４５０及びコード部アドレス４６０を含んだ情報を保持する。
【００６６】
論理ページアドレス４１０は、論理ページの先頭の論理アドレスである。
【００６７】
基準データ格納先４２０は、基準データを格納する物理アドレスＰｉ［Ｎｉ］（ページアドレスＰｉ、セクタ番号Ｎｉ）と格納セクタサイズを含んだ情報である。
【００６８】
差分フラグ４３０は、差分の有無を表す。論理ページが第１の形成方法を適用した単独割当ページまたは重複割当ページである場合、差分フラグ４３０は「ＯＦＦ」であり（差分無しを意味し）、論理ページが第２の形成方法を適用した単独割当ページまたは重複割当ページである場合、差分フラグ４３０は「ＯＮ」である（差分有りを意味する）。
【００６９】
差分データ格納先４４０は、差分フラグ４３０がＯＮである場合に有効な情報であり、差分データを格納する物理アドレスＰｉ［Ｎｉ］（ページアドレスＰｉ、セクタ番号Ｎｉ）と格納セクタサイズを含む情報である。
【００７０】
重複フラグ４５０は、重複排除技術が適用された論理ページか否かを表す。論理ページが単独割当ページである場合、重複フラグ４５０は「ＯＦＦ」であり（重複排除技術が適用されていないことを意味し）、論理ページが重複割当ページである場合、重複フラグ４５０は「ＯＮ」である（重複排除技術が適用されていることを意味する）。
【００７１】
コード部アドレス４６０は、重複フラグ４５０が「ＯＮ」である場合に有効な情報であり、ユーザデータのコード部を格納する物理アドレスＰｉ［Ｎｉ］（ページアドレスＰｉ、セクタ番号Ｎｉ）を含んだ情報である。なお、コード部のサイズは２５６バイトであり、格納セクタサイズは１で固定となるため、コード部アドレス４６０は、格納セクタサイズは含まないでよい。
【００７２】
なお、図４Ａのアドレス変換テーブル４００は、一例として、図３の右側に示した格納状態に従う情報（例えば論理ページＬ０〜Ｌ７の情報）を保持している。論理ページＬ０は、第２の形成方法を適用している単独割当ページであり、論理ページＬ１、Ｌ３及びＬ７は、それぞれ、第１の形成方法を適用している重複割当ページであり、論理ページＬ２、Ｌ５及びＬ６は、それぞれ、第１の形成方法を適用している単独割当ページであり、論理ページＬ４は、第２の形成方法を適用している重複割当ページである。
【００７３】
図４Ｂの重複カウントテーブル４７０は、複数の重複割当ページによって共有されている基準データ毎に、基準データアドレス４８０及び共有カウント４９０を含んだ情報を保持する。
【００７４】
基準データアドレス４８０は、基準データを格納する物理アドレスＰｉ［Ｎｉ］（ページアドレスＰｉ、セクタ番号Ｎｉ）を含んだ情報である。
【００７５】
共有カウント４９０は、基準データを共有する論理ページ（重複割当ページ）の数を表す。
【００７６】
なお、図４Ｂの重複カウントテーブル４７０は、具体例として、図３の右側に示した格納状態、すなわち、物理ページＰ１のセクタ番号０から格納されている基準データを４個の論理ページＬ１、Ｌ３、Ｌ４及びＬ７が共有していることを表している。
【００７７】
次に、図５を参照しながら、ＦＭモジュール１００が上位装置（ストレージコントローラ１４０１）からのライトコマンドに従いユーザデータを更新する時の処理について説明する。ＦＭモジュール１００のＦＭコントローラ１０３は、フラッシュメモリ１０５の書込み量を小さくするために、この処理によって更新対象ユーザデータの形成方法として最適なものを選択する。
【００７８】
まず、ＦＭコントローラ１０３は、ライトコマンドで指定された論理アドレスＷａが属する論理ページアドレスＬｋを算出する（ステップ５０１）。ＦＭコントローラ１０３は、算出した論理ページアドレスＬｋに対応した重複フラグ４５０が「ＯＦＦ」か「ＯＮ」かを判断する（ステップ５０２）。「ＯＦＦ」（単独割当ページ）ならば、ステップ５０３に遷移し、「ＯＮ」（重複割当ページ）ならば、ステップ５０４に遷移する。
【００７９】
ステップ５０３では、ＦＭコントローラ１０３は、ライトコマンドに従うライトデータのセクタ数がページサイズ（１６セクタ）であるか、それよりも小さいサイズであるかを判断する。ページサイズであるならば、ＦＭコントローラ１０３は、ステップ６００の単独割当ページの全体ライト処理を実行する。さもなくば、ＦＭコントローラ１０３は、ステップ７００の単独割当ページの部分ライト処理を実行する。
【００８０】
ステップ５０４では、ＦＭコントローラ１０３は、ライトコマンドによってライトされるライトデータのセクタ数がページサイズ（１６セクタ）であるか、それよりも小さいサイズであるかを判断する。ページサイズであるならば、ＦＭコントローラ１０３は、ステップ８００の重複割当ページの全体ライト処理を実行する。さもなくば、ＦＭコントローラ１０３は、ステップ９００の重複割当ページの部分ライト処理を実行する。
【００８１】
ここで、図１０〜図１３を用いて、ステップ６００の単独割当ページの全体ライト処理、ステップ７００の単独割当ページの部分ライト処理、ステップ８００の重複割当ページの全体ライト処理、ステップ９００の重複割当ページの部分ライト処理のそれぞれを詳細に説明する。
【００８２】
図１０は、単独割当ページの全体ライト処理を示す。
【００８３】
この処理は、論理ページＬｋのユーザデータをライトデータＷｄに更新する際に、そのユーザデータの新しい形成方法を選択する処理である。すなわち、第１の形成方法を選択して、ライトデータＷｄを新しい基準データとして書き込むか、もしくは第２の形成方法を選択して、現在の基準データを変更せずにライトデータＷｄとの差分データを書き込むかが分かれる。
【００８４】
データ１０１０は、現在の基準データの圧縮データであり、フラッシュメモリ１０５に格納されている。第２の形成方法の差分データを作成するためには、その圧縮データをリードして伸張し、ライトデータＷｄと排他的論理和を計算（１０４０）する必要がある。
【００８５】
データ１０２０は、第１の形成方法のための新しい基準データの圧縮データであり、データ１０３０は、第２の形成方法のための差分データの圧縮データである。ＦＭコントローラ１０３は、フラッシュメモリ１０５へのライトサイズが小さいほうを選ぶ。データ１０２０の方が小さい場合は、ＦＭコントローラ１０３は、データ１０２０をライトして第１の形成方法を選ぶ。データ１０３０の方が小さい場合は、ＦＭコントローラ１０３は、データ１０３０をライトして第２の形成方法を選ぶ。なお、サイズが同じなら、ＦＭコントローラ１０３は、データ１０２０をライトして第１の形成方法を選ぶ。なぜなら、第２の形成方法では、ユーザデータのリード時に基準データと差分データの２つを読み出さなければならず、リード性能が劣るからである。
【００８６】
この処理では、ライトデータＷｄが現在の基準データとよく似たデータパタンであるほど、差分データはゼロ値の連続が多く含まれて小さく圧縮できるため、第２の形成方法の選択が有利になる。
【００８７】
なお、ＦＭコントローラ１０３は、図１０を参照して説明した方法でライトされたライトデータＷｄをリード対象としたリードコマンドを上位装置（ストレージコントローラ１４０１）から受信した場合、アドレス変換テーブル４００を基に、ライトデータＷｄを復元し、ライトデータＷｄをリードデータとして上位装置に送信することができる。復元されたライトデータＷｄは、（１）データ１０２０を伸張することにより生成されたデータであるか、又は、（２）データ１０３０を伸張することにより得られた差分データ（新）とデータ１０１０を伸張することにより得られた基準データとの排他的論理和である。
【００８８】
図１１は、単独割当ページの部分ライト処理を示す。
【００８９】
この処理は、論理ページＬｋのユーザデータの一部をライトデータＷｄで書き換える際に、書き換え後のユーザデータの新しい形成方法を選択する処理である。すなわち、第１の形成方法を選択して、書き換え後のユーザデータを新しい基準データとして書き込むか、もしくは第２の形成方法を選択して、現在の基準データを変更せずに書き換え後のユーザデータとの差分データを書き込むかが分かれる。
【００９０】
データ１１１０は、現在の基準データの圧縮データであり、データ１１２０は、現在の差分データの圧縮データであり、ともにフラッシュメモリ１０５に格納されている。第２の形成方法の差分データを作成するためには以下の処理を行う必要がある。すなわち、ＦＭコントローラ１０３は、データ１１１０及び１１２０をそれぞれリードして伸張し、両者の排他的論理和を計算（１１５０）して現在のユーザデータを作成する。次に、ＦＭコントローラ１０３は、ライトデータＷｄで現在のユーザデータの一部を書き換えて新しいユーザデータを作成し（１１６０）、新しいユーザデータと現在の基準データとの排他的論理和を計算（１１７０）して新しい差分データを作成する。
【００９１】
データ１１３０は、第１の形成方法のための新しい基準データの圧縮データであり、データ１１４０は、第２の形成方法のための差分データの圧縮データある。ＦＭコントローラ１０３は、フラッシュメモリ１０５へのライトサイズが小さいほうを選ぶ。データ１１３０の方が小さい場合は、ＦＭコントローラ１０３は、データ１１３０をライトして第１の形成方法を選ぶ。データ１１４０の方が小さい場合は、ＦＭコントローラ１０３は、データ１１４０をライトして第２の形成方法を選ぶ。なお、サイズが同じなら、ＦＭコントローラ１０３は、データ１１３０をライトして第１の形成方法を選ぶ。なぜなら、第２の形成方法では、ユーザデータのリード時に基準データと差分データの２つを読み出さなければならず、リード性能が劣るからである。
【００９２】
この処理では、ライトデータＷｄのサイズが小さい程（書き換え量が小さい程）、新しい差分データはゼロ値の連続が多く含まれて小さく圧縮できるため、第２の形成方法の選択が有利になる。
【００９３】
なお、ＦＭコントローラ１０３は、図１１を参照して説明した方法でライトされたライトデータＷｄをリード対象としたリードコマンドを上位装置から受信した場合、アドレス変換テーブル４００を基に、ライトデータＷｄを復元し、ライトデータＷｄをリードデータとして上位装置に送信することができる。復元されたライトデータＷｄは、（１）データ１１３０を伸張することにより生成されたデータから抽出された部分データであるか、又は、（２）データ１１４０を伸張することにより得られた差分データ（新）とデータ１１１０を伸張することにより得られた基準データとの排他的論理和から抽出された部分データである。
【００９４】
図１２は、重複割当ページの全体ライト処理を示す。
【００９５】
この処理は、論理ページＬｋのユーザデータをライトデータＷｄに更新する際に、論理ページＬｋの新しいページ種別と、そのユーザデータの新しい形成方法を選択する処理である。すなわち、単独割当ページの第１の形成方法を選択して、ライトデータＷｄを新しい基準データとして書き込むか、もしくは重複割当ページの第２の形成方法を選択して、現在の基準データを変更せずに差分データ（ライトデータＷｄとの差分データ）とコード部とを書き込むかが分かれる。
【００９６】
データ１２１０は、現在の基準データの圧縮データであり、フラッシュメモリ１０５に格納されている。重複割当ページの第２の形成方法の差分データを作成するためには、データ１２１０をリードして伸張し、ライトデータＷｄから分離（１２４０）したセクタ部と排他的論理和を計算（１２５０）する必要がある。
【００９７】
データ１２２０は、単独割当ページの第１の形成方法のための新しい基準データの圧縮データであり、データ１２３０は、重複割当ページの第２の形成方法のための差分データの圧縮データと、ライトデータＷｄから分離（１２５０）したコード部とが連結されたデータである。ＦＭコントローラ１０３は、フラッシュメモリ１０５へのライトサイズが小さいほうを選ぶ。データ１２２０の方が小さい場合は、ＦＭコントローラ１０３は、データ１２２０をライトして単独割当ページの第１の形成方法を選ぶ。データ１２３０の方が小さい場合は、ＦＭコントローラ１０３は、データ１２３０をライトして重複割当ページの第２の形成方法を選ぶ。なお、サイズが同じなら、ＦＭコントローラ１０３は、データ１２２０をライトして単独割当ページの第１の形成方法を選ぶ。なぜなら、重複割当ページの第２の形成方法では、ユーザデータのリード時に基準データと差分データとコード部の３つを読み出さなければならず、リード性能が劣るからである。
【００９８】
この処理では、ライトデータＷｄのセクタ部が現在の基準データとよく似たデータパタンであるほど、差分データはゼロ値の連続が多く含まれて小さく圧縮できるため、重複割当ページの第２の形成方法の選択が有利になる。
【００９９】
なお、ＦＭコントローラ１０３は、図１２を参照して説明した方法でライトされたライトデータＷｄをリード対象としたリードコマンドを上位装置から受信した場合、アドレス変換テーブル４００を基に、ライトデータＷｄを復元し、ライトデータＷｄをリードデータとして上位装置に送信することができる。復元されたライトデータＷｄは、（１）データ１２２０を伸張することにより生成されたデータであるか、又は、（２）データ１２３０における圧縮差分データを伸張することにより得られた差分データ（新）とデータ１２１０を伸張することにより得られた基準データとの排他的論理和と、データ１２３０のうちのコード部（新）とで構成されたデータである。
【０１００】
図１３は、重複割当ページの部分ライト処理を示す。
【０１０１】
この処理は、論理ページＬｋのユーザデータの一部をライトデータＷｄで書き換える際に、論理ページＬｋの新しいページ種別と、書き換え後のユーザデータの新しい形成方法を選択する処理である。すなわち、単独割当ページの第１の形成方法を選択して、書き換え後のユーザデータを新しい基準データとして書き込むか、もしくは重複割当ページの第２の形成方法を選択して、現在の基準データを変更せずに差分データ（書き換え後のユーザデータとの差分データ）とコード部とを書き込むかが分かれる。
【０１０２】
データ１３１０は、現在の基準データの圧縮データであり、データ１３２０は、現在の差分データの圧縮データであり、データ１３３０は、現在のコード部であり、それらはフラッシュメモリ１０５に格納されている。重複割当ページの第２の形成方法の差分データを作成するためには以下の処理を行う必要がある。すなわち、ＦＭコントローラ１０３は、リードしてさらに伸張した、基準データと差分データとの排他的論理和を計算（１３６０）し、その計算（１３６０）により作成された排他的論理和データに、リードしたコード部を合成（１３７０）して現在のユーザデータを作成する。次に、ＦＭコントローラ１０３は、ライトデータＷｄで現在のユーザデータの一部を書き換えて新しいユーザデータを作成し（１３８０）、新しいユーザデータから分離（１３９０）したセクタ部と、現在の基準データとの排他的論理和を計算（１３００）して新しい差分データを作成する。
【０１０３】
データ１３４０は、単独割当ページの第１の形成方法のための新しい基準データの圧縮データであり、データ１３５０は、重複割当ページの第２の形成方法のための差分データの圧縮データと、新しいユーザデータから分離（１３９０）したコード部とが連結されたデータである。ＦＭコントローラ１０３は、フラッシュメモリ１０５へのライトサイズが小さいほうを選ぶ。データ１３４０の方が小さい場合は、ＦＭコントローラ１０３は、データ１３４０をライトして単独割当ページの第１の形成方法を選ぶ。データ１３５０の方が小さい場合は、ＦＭコントローラ１０３は、データ１３５０をライトして重複割当ページの第２の形成方法を選ぶ。なお、サイズが同じなら、ＦＭコントローラ１０３は、データ１３４０をライトして単独割当ページの第１の形成方法を選ぶ。なぜなら、重複割当ページの第２の形成方法では、ユーザデータのリード時に基準データと差分データとコード部の３つを読み出さなければならず、リード性能が劣るからである。
【０１０４】
この処理では、ライトデータＷｄが小さい程（書き換え量が小さい程）、新しい差分データはゼロ値の連続が多く含まれて小さく圧縮できるため、重複割当ページの第２の形成方法の選択が有利になる。
【０１０５】
なお、ＦＭコントローラ１０３は、図１３を参照して説明した方法でライトされたライトデータＷｄをリード対象としたリードコマンドを上位装置から受信した場合、アドレス変換テーブル４００を基に、ライトデータＷｄを復元し、ライトデータＷｄをリードデータとして上位装置に送信することができる。復元されたライトデータＷｄは、（１）データ１３４０を伸張することにより生成されたデータから抽出された部分データであるか、又は、（２）データ１３５０における圧縮差分データを伸張することにより得られた差分データ（新）とデータ１３１０を伸張することにより得られた基準データとの排他的論理和と、データ１３５０のうちのコード部（新）とで構成されたデータから抽出された部分データである。
【０１０６】
ステップ６００の単独割当ページの全体ライト処理の流れについて、図６を参照しながら説明する。なお、以下、説明の冗長を避けるため、ＦＭコントローラ１０３の圧縮伸張回路１０４による圧縮／伸張を、ＦＭコントローラ１０３による圧縮／伸張と説明し、ＦＭコントローラ１０３のＸＯＲ回路１０７による排他的論理和の計算を、ＦＭコントローラ１０３による排他的論理和の計算と説明する。また、ステップ５０１で算出した論理ページアドレスＬｋが属する論理ページを「論理ページＬｋ」と言う。
【０１０７】
まず、ＦＭコントローラ１０３は、ステップ５０１で算出した論理ページアドレスＬｋに対応した基準データ格納先４２０（物理アドレスＰｘ［Ｎｘ］と格納セクタサイズＳｘ）を取得する（ステップ６０１）。ＦＭコントローラ１０３は、その基準データ格納先４２０が表す物理領域から、論理ページＬｋの圧縮基準データ（圧縮されている基準データ）をリードし、その圧縮基準データを伸張することで基準データ（平文状態）を復元する（ステップ６０２）。
【０１０８】
次に、ＦＭコントローラ１０３は、論理ページＬｋの基準データ（ステップ６０２で復元された基準データ）とライトデータＷｄとの排他的論理和を計算することで論理ページＬｋの差分データを作成し、その差分データを圧縮することで圧縮差分データを作成する（ステップ６０３）。
【０１０９】
一方で、ＦＭコントローラ１０３は、ライトデータＷｄを圧縮することで圧縮ライトデータを作成する（ステップ６０４）。
【０１１０】
ＦＭコントローラ１０３は、ステップ６０３の結果データ（圧縮差分データ）のサイズとステップ６０４の結果データ（圧縮ライトデータ）のサイズとを比較し、小さい方を選択してフラッシュメモリ１０５へライトする（ステップ６０５）。なお、サイズが同じならステップ６０４の結果データが選択される。
【０１１１】
ステップ６０３の結果データを選択した場合は、論理ページＬｋのユーザデータは第２の形成方法の適用になるので、ＦＭコントローラ１０３は、論理ページＬｋに対応した差分フラグ４３０を「ＯＮ」に設定し、ステップ６０４の結果データを選択した場合は、論理ページＬｋのユーザデータは第１の形成方法の適用になるので、論理ページＬｋに対応した差分フラグ４３０を「ＯＦＦ」に設定する（ステップ６０６）。
【０１１２】
以上で単独割当ページの全体ライト処理が終わり、図５のステップ５０５に遷移する。
【０１１３】
ステップ７００の単独割当ページの部分ライト処理の流れについて、図７を参照しながら説明する。
【０１１４】
まず、ＦＭコントローラ１０３は、ステップ５０１で算出した論理ページアドレスＬｋに対応した基準データ格納先４２０（物理アドレスＰｘ［Ｎｘ］と格納セクタサイズＳｘ）を取得する（ステップ７０１）。ＦＭコントローラ１０３は、その基準データ格納先４２０が表す物理領域から、論理ページＬｋの圧縮基準データをリードし、その圧縮基準データを伸張することで基準データ（平文状態）を復元する（ステップ７０２）。
【０１１５】
次に、ステップ７０３として、ＦＭコントローラ１０３は、論理ページＬｋに対応した差分フラグ４３０を調べ、「ＯＦＦ」ならばステップ７０４に、「ＯＮ」ならばステップ７０５に遷移する。
【０１１６】
ステップ７０４では、ＦＭコントローラ１０３は、差分データが存在しないので、ステップ７０２の結果データ（復元された基準データ）を論理ページＬｋの現在のユーザデータとし、ステップ７０８に遷移する。
【０１１７】
一方、ステップ７０５では、ＦＭコントローラ１０３は、現在の差分データを得るため、論理ページアドレスＬｋに対応した差分データ格納先４４０（物理アドレスＰｙ［Ｎｙ］と格納セクタサイズＳｙ）を取得する。ＦＭコントローラ１０３は、その差分データ格納先４４０が表す物理領域から、論理ページＬｋの圧縮差分データ（圧縮された差分データ）をリードし、その圧縮差分データを伸張することにより差分データ（平文状態）を復元する（ステップ７０６）。そして、ＦＭコントローラ１０３は、論理ページＬｋの基準データと差分データとの排他的論理和を計算することで論理ページＬｋの現在のユーザデータを作成する（ステップ７０７）。その後、ステップ７０８に遷移する。
【０１１８】
ステップ７０８では、ＦＭコントローラ１０３は、論理ページＬｋの現在のユーザデータにおいて、ライトコマンドで指定されたアドレスＷａの部分をライトデータＷｄで書き換え、論理ページＬｋの新しいユーザデータを作成する。
【０１１９】
次に、ＦＭコントローラ１０３は、論理ページＬｋの現在の基準データと新しいユーザデータとの排他的論理和を計算することで論理ページＬｋの新しい差分データを作成し、その新しい差分データを圧縮することにより圧縮差分データを作成する（ステップ７０９）。
【０１２０】
一方で、ＦＭコントローラ１０３は、論理ページＬｋの新しいユーザデータを圧縮することにより圧縮ユーザデータを作成する（ステップ７１０）。
【０１２１】
ＦＭコントローラ１０３は、ステップ７０９の結果データ（圧縮差分データ）のサイズとステップ７１０の結果データ（圧縮ユーザデータ）のサイズとを比較し、小さい方を選択してフラッシュメモリ１０５へライトする（ステップ７１１）。なお、サイズが同じならステップ７１０の結果データが選択される。
【０１２２】
ステップ７０９の結果データを選択した場合は、論理ページＬｋのユーザデータは第２の形成方法の適用になるので、ＦＭコントローラ１０３は、論理ページアドレスＬｋに対応した差分フラグ４３０を「ＯＮ」に設定し、ステップ７１０の結果データを選択した場合は、論理ページＬｋのユーザデータは第１の形成方法の適用になるので、論理ページアドレスＬｋに対応した差分フラグ４３０を「ＯＦＦ」に設定する（７１２）。
【０１２３】
以上で単独割当ページの部分ライト処理が終わり、図５のステップ５０５に遷移する。
【０１２４】
ステップ８００の重複割当ページの全体ライト処理の流れについて、図８を参照しながら説明する。
【０１２５】
まず、ＦＭコントローラ１０３は、ステップ５０１で算出した論理ページアドレスＬｋに対応した基準データ格納先４２０（物理アドレスＰｘ［Ｎｘ］と格納セクタサイズＳｘ）を取得する（ステップ８０１）。ＦＭコントローラ１０３は、その基準データ格納先４２０が表す物理領域から、論理ページＬｋの圧縮基準データをリードし、その圧縮基準データを伸張することで基準データ（平文状態）を復元する（ステップ８０２）。
【０１２６】
次に、ＦＭコントローラ１０３は、論理ページＬｋの基準データとライトデータＷｄから分離したセクタ部との排他的論理和を計算することにより論理ページＬｋの差分データを作成し、その差分データを圧縮することにより圧縮差分データを作成する（ステップ８０３）。さらに、ＦＭコントローラ１０３は、ライトデータＷｄから分離したコード部を論理ページＬｋの新しいコード部とし（ステップ８０４）、それをステップ８０３の結果データ（圧縮差分データ）に結合する（ステップ８０５）。
【０１２７】
一方で、ＦＭコントローラ１０３は、ライトデータＷｄを圧縮することにより圧縮ライトデータを作成する（ステップ８０６）。
【０１２８】
ＦＭコントローラ１０３は、ステップ８０５の結果データ（圧縮差分データ＋新しいコード部）のサイズとステップ８０６の結果データ（圧縮ライトデータ）のサイズとを比較し、小さい方を選択してフラッシュメモリ１０５へライトする（ステップ８０７）。なお、サイズが同じならステップ８０６の結果データが選択される。
【０１２９】
ステップ８０５の結果データを選択した場合は、論理ページＬｋのユーザデータは第２の形成方法の適用になるので、ＦＭコントローラ１０３は、論理ページアドレスＬｋに対応した差分フラグ４３０を「ＯＮ」に設定し、ステップ８０６の結果データを選択した場合は、論理ページＬｋのユーザデータは第１の形成方法の適用になるので、論理ページアドレスＬｋに対応した差分フラグ４３０を「ＯＦＦ」に設定する（ステップ８０８）。
【０１３０】
以上で重複割当ページの全体ライト処理が終わり、図５のステップ５０９に遷移する。
【０１３１】
ステップ９００の重複割当ページの部分ライト処理の流れについて、図９を参照しながら説明する。
【０１３２】
まず、ＦＭコントローラ１０３は、ステップ５０１で算出した論理ページアドレスＬｋに対応した基準データ格納先４２０（物理アドレスＰｘ［Ｎｘ］と格納セクタサイズＳｘ）を取得する（ステップ９０１）。ＦＭコントローラ１０３は、その基準データ格納先４２０が表す物理領域から、論理ページＬｋの圧縮基準データ（圧縮されている基準データ）をリードし、その圧縮基準データを伸張することで基準データ（平文状態）を復元する（ステップ９０２）。
【０１３３】
次に、ステップ９０３として、ＦＭコントローラ１０３は、論理ページＬｋに対応した差分フラグ４３０を調べ、「ＯＦＦ」ならばステップ９０４に、「ＯＮ」ならばステップ９０６に遷移する。
【０１３４】
ステップ９０４では、ＦＭコントローラ１０３は、論理ページＬｋに対応したコード部アドレス４６０（物理アドレスＰｚ［Ｎｚ］）を取得する。ＦＭコントローラ１０３は、そのコード部アドレス４６０が表す物理領域から、論理ページＬｋの現在のコード部をリードし、そのコード部を、ステップ９０２で得られた基準データと合成して、論理ページＬｋの現在のユーザデータを作成する（ステップ９０５）。その後、ステップ９０９に遷移する。
【０１３５】
一方、ステップ９０６では、ＦＭコントローラ１０３は、現在の差分データとコード部を得るため、論理ページＬｋに対応した差分データ格納先４４０（物理アドレスＰｙ［Ｎｙ］と格納セクタサイズＳｙ）及びコード部アドレス４６０（物理アドレスＰｚ［Ｎｚ］）を取得する。ＦＭコントローラ１０３は、そのた差分データ格納先４４０が表す物理領域から、論理ページＬｋの圧縮差分データをリードし、その圧縮差分データを伸張することにより差分データ（平文状態）を復元する（ステップ９０７）。そして、ＦＭコントローラ１０３は、ステップ９０６で取得されたコード部アドレス４６０（Ｐｚ［Ｎｚ］）が表す物理領域から論理ページＬｋのコード部をリードし、論理ページＬｋの基準データと差分データとの排他的論理和を計算し、その計算結果に、上記リードした論理ページＬｋのコード部を合成することで、論理ページＬｋの現在のユーザデータを作成する（ステップ９０８）。その後、ステップ９０９に遷移する。
【０１３６】
ステップ９０９では、ＦＭコントローラ１０３は、論理ページＬｋの現在のユーザデータにおいて、ライトコマンドで指定されたアドレスＷａの部分をライトデータＷｄで書き換え、論理ページＬｋの新しいユーザデータを作成する。
【０１３７】
次に、ＦＭコントローラ１０３は、論理ページＬｋの現在の基準データと新しいユーザデータのセクタ部との排他的論理和を計算することで論理ページＬｋの新しい差分データを作成し、その差分データを圧縮することにより圧縮差分データを作成する（ステップ９１０）。そして、ＦＭコントローラ１０３は、その結果データ（圧縮差分データ）に、新しいユーザデータから分離したコード部を結合する（ステップ９１１）。
【０１３８】
一方で、ＦＭコントローラ１０３は、論理ページＬｋの新しいユーザデータを圧縮することにより圧縮ユーザデータを作成する（ステップ９１２）。
【０１３９】
ＦＭコントローラ１０３は、ステップ９１１の結果データ（圧縮差分データ＋コード部）のサイズとステップ９１２の結果データ（圧縮ユーザデータ）のサイズとを比較し、小さい方を選択してフラッシュメモリ１０５へライトする（ステップ９１３）。なお、サイズが同じならステップ９１２の結果データが選択される。
【０１４０】
ステップ９１１の結果データを選択した場合は、論理ページＬｋのユーザデータは第２の形成方法の適用になるので、ＦＭコントローラ１０３は、論理ページアドレスＬｋに対応した差分フラグ４３０を「ＯＮ」に設定し、ステップ９１２の結果データを選択した場合は、論理ページＬｋのユーザデータは第１の形成方法の適用になるので、論理ページアドレスＬｋに対応した差分フラグ４３０を「ＯＦＦ」に設定する（ステップ９１４）。
【０１４１】
以上で重複割当ページの部分ライト処理が終わり、図５のステップ５０９に遷移する。
【０１４２】
次に、図５のステップ５０５以降を参照しながら、図６、図７の２つのライト処理の後の処理について説明する。
【０１４３】
ステップ５０５では、ＦＭコントローラ１０３は、単独割当ページの全体ライト処理、部分ライト処理のそれぞれ最後のステップにおいて、論理ページアドレスＬｋの差分フラグ４３０が「ＯＦＦ」に設定されたか「ＯＮ」に設定されたかを調べる。「ＯＦＦ」の場合は、第１の形成方法になったことを意味し、ステップ５０６に遷移する。「ＯＮ」の場合は、第２の形成方法になったことを意味し、ステップ５０８に遷移する。
【０１４４】
ステップ５０６では、ＦＭコントローラ１０３は、論理ページアドレスＬｋに対応した基準データ格納先４２０を、フラッシュメモリ１０５にライトした新しい基準データ（圧縮状態）の物理アドレスと格納セクタサイズに更新する。そして、ＦＭコントローラ１０３は、物理アドレスＰｘ［Ｎｘ］に残された更新前の基準データを無効化する（ステップ５０７）。以上で、ライトコマンド処理が終わる。
【０１４５】
ステップ５０８では、ＦＭコントローラ１０３は、論理ページアドレスＬｋに対応した差分データ格納先４４０を、フラッシュメモリ１０５にライトした新しい差分データ（圧縮状態）の物理アドレスと格納セクタサイズに更新する。ＦＭコントローラ１０３は、物理アドレスＰｙ［Ｎｙ］に更新前の差分データが残されていれば（つまり、ライト処理の前、差分フラグ４３０がＯＮであった場合は）、それを無効化する。以上でライトコマンド処理が終わる。
【０１４６】
次に、図５のステップ５０９以降を参照しながら、図８、図９の２つのライト処理の後の処理について説明する。
【０１４７】
ステップ５０９では、ＦＭコントローラ１０３は、重複割当ページの全体ライト処理、部分ライト処理のそれぞれ最後のステップにおいて、論理ページＬｋの差分フラグ４３０が「ＯＦＦ」に設定されたか「ＯＮ」に設定されたかを調べる。「ＯＦＦ」の場合は、単独割当ページの第１の形成方法になったことを意味し、ステップ５１０に遷移する。「ＯＮ」の場合は、重複割当ページの第２の形成方法になったことを意味し、ステップ５１４に遷移する。
【０１４８】
ステップ５１０では、ＦＭコントローラ１０３は、論理ページアドレスＬｋに対応した基準データ格納先を、フラッシュメモリ１０５にライトした新しい基準データ（圧縮状態）の物理アドレスと格納セクタサイズに更新する。これによって、物理アドレスＰｘ［Ｎｘ］に残された更新前の基準データを共有している論理ページの数は１つ減ることになるので、ＦＭコントローラ１０３は、重複カウントテーブル４７０において、更新前の基準データに対応する共有カウントの値を１つ減算する（ステップ５１１）。さらに、この減算によって共有カウントの値が０になったならば、もう更新前の基準データを利用している論理ページは存在しないことになるので、ＦＭコントローラ１０３は、更新前の基準データを無効化する（ステップ５１２）。そして、ＦＭコントローラ１０３は、論理ページアドレスＬｋに対応した重複フラグ４５０を「ＯＦＦ」に設定することで論理ページＬｋを単独割当ページに変更する（ステップ５１３）。以上でライトコマンド処理が終わる。
【０１４９】
ステップ５１４では、ＦＭコントローラ１０３は、論理ページアドレスＬｋに対応した差分データ格納先４４０を、フラッシュメモリ１０５にライトした新しい差分データ（圧縮状態）の物理アドレスと格納セクタサイズに更新し、論理ページアドレスＬｋに対応したコード部アドレス４６０を、フラッシュメモリ１０５にライトした新しいコード部の物理アドレスに更新し、物理アドレスＰｚ［Ｎｚ］にある更新前のコード部を無効化する。物理アドレスＰｙ［Ｎｙ］に更新前の差分データが残されていれば（つまり、ライト処理の前、差分フラグ４３０が「ＯＮ」であった場合は）、ＦＭコントローラ１０３は、その更新前の差分データも無効化する。以上でライトコマンド処理が終わる。
【０１５０】
上述した実施例によれば、更新前後のユーザデータの差分が少ない場合には、更新前のユーザデータが無効化されて更新後のユーザデータそれ自体が書き込まれるのではなく、更新前後のユーザデータの排他的論理和である差分データが圧縮されたものが書き込まれる傾向にある。これにより、フラッシュメモリ１０５の書込み量を削減でき、フラッシュメモリ１０５の長寿命化を図ることができる。
【０１５１】
また、本実施例では、差分データを排他的論理和で作成する方法が採用されている。この方法は、更新された部分が１つの物理ページ内に数多く散在していても、各々の更新部分の位置を１つ１つ管理する必要がないという特徴がある。これにより、差分に関する管理情報のサイズを小さくできるので、メモリ容量を節約できる効果がある。
【０１５２】
なお、単独割当ページの全体ライト処理６００、単独割当ページの部分ライト処理７００、重複割当ページの全体ライト処理８００、及び、重複割当ページの部分ライト処理９００のうちの少なくとも１つにおいては、幾つかの変形例も可能である。
【０１５３】
第１の変形例では、データ（基準データ及び差分データの少なくとも一方）の圧縮効果がない場合には、データは、平文状態のままフラッシュメモリ１０５にライトされてよい。データが平文状態でライトされれば、そのデータをリードする際に伸張処理の時間が削減できるため、ＦＭモジュール１００のリード応答性能が向上する。
【０１５４】
第２の変形例では、ＸＯＲ回路１０７によって作成された差分データが全てゼロ値（所定ビット値又は所定バイト値）からなるデータの場合、ＦＭコントローラ１０３は、以降の圧縮処理をせず、フラッシュメモリ１０５に差分データをライトせず、論理ページＬｋに対応した差分フラグ４３０を「ＯＦＦ」に設定（差分データを利用しない第１の形成方法を選択）して、すぐにライトコマンド処理を終えてもよい。これにより、フラッシュメモリ１０５の書込み量を削減できる。また、差分データの圧縮処理時間、フラッシュメモリ１０５へのライトの時間も削減でき、ＦＭモジュール１００のライトコマンド処理性能も向上する。
【０１５５】
第３の変形例では、ＸＯＲ回路１０７によって作成された差分データにおける非ゼロ値の数が所定個数以下ならば（つまり更新部分が少なければ）、ＦＭコントローラ１０３は、論理ページＬｋに対応した差分フラグ４３０を「ＯＮ」に設定（差分データを利用する第２の形成方法を選択）して、ユーザデータ（更新データ）の圧縮処理を行うことなくライトコマンド処理を終えてもよい。つまり、圧縮ユーザデータを作成して上述したような比較を行うことなく、ライトコマンド処理が終了してよい。
【０１５６】
第４の変形例では、ユーザデータのセクタ部のサイズが所定サイズ以下ならば（つまり更新部分が少なければ）、ＦＭコントローラ１０３は、論理ページＬｋに対応した差分フラグ４３０を「ＯＮ」に設定（差分データを利用する第２の形成方法を選択）して、ユーザデータ（セクタ部）の圧縮処理を行うことなくライトコマンド処理を終えてもよい。つまり、圧縮ユーザデータを作成して上述したような比較を行うことなく、ライトコマンド処理が終了してよい。
【０１５７】
第５の変形例では、ライトコマンドに従うライトデータがオールゼロなどの固定パタン（例えばフォーマットのためのデータ）ならば、ＦＭコントローラ１０３は、論理ページＬｋに対応した差分フラグ４３０を「ＯＦＦ」に設定（差分データを利用しない第１の形成方法を選択）して、差分データの生成及び圧縮処理を行うことなくライトコマンド処理を終えてもよい。
【０１５８】
以上、幾つかの実施例及び変形例を説明したが、これらは本発明の説明のための例示であって、本発明の範囲をこれらの実施例及び変形例にのみ限定する趣旨ではない。本発明は、他の種々の形態でも実施することが可能である。
【０１５９】
例えば、単独割当ページと重複割当ページの少なくとも一方において、必ずしもデータサイズの比較は行われなくてもよい。例えば、一定回数第２の形成方法が選択された後に第１の形成方法が選択されその後再び一定回数第２の形成方法が選択されるといったことが行われてもよい。
【０１６０】
また、例えば、ＦＭモジュール１００を有する装置は、ストレージ装置１４００に限らず、図１６に示すように、ホスト１４２１であってもよい。例えば、ホスト１４２１（例えばサーバ装置）は、Ｉ／Ｆ１６０４、ＦＭモジュール１００及びそれらに接続されたＣＰＵ１６０２を有してよい（ホスト１４２１は、更に、ＦＭモジュール１００とは別の種類の記憶デバイス（例えばＤＲＡＭ）を有してもよい）。ＦＭモジュール１００の全部又は一部は、ホスト１４２１により入出力されるデータのキャッシュメモリとして利用されてよい。図１６では、ＦＭモジュール１００の上位装置はＣＰＵ１６０２でよい。ホスト１４２１では、キャッシュメモリのデータを頻繁に書き換えるようなアプリケーションを実行することがあるため、フラッシュメモリ１０５の書込み量を削減できる本実施例に従うＦＭモジュール１００は、ホスト１４２１にも有効である。
【符号の説明】
【０１６１】
１００…ＦＭモジュール、１０３…ＦＭコントローラ、１０４…圧縮伸張回路、１０５…フラッシュメモリ、１０６…ＤＲＡＭ、１０７…ＸＯＲ回路
【図１】
2015128955.tif 000003
【図２Ａ】
2015128955.tif 000004
【図２Ｂ】
2015128955.tif 000005
【図２Ｃ】
2015128955.tif 000006
【図３】
2015128955.tif 000007
【図４Ａ】
2015128955.tif 000008
【図４Ｂ】
2015128955.tif 000009
【図５】
2015128955.tif 000010
【図６】
2015128955.tif 000011
【図７】
2015128955.tif 000012
【図８】
2015128955.tif 000013
【図９】
2015128955.tif 000014
【図１０】
2015128955.tif 000015
【図１１】
2015128955.tif 000016
【図１２】
2015128955.tif 000017
【図１３】
2015128955.tif 000018
【図１４】
2015128955.tif 000019
【図１５Ａ】
2015128955.tif 000020
【図１５Ｂ】
2015128955.tif 000021
【図１６】
2015128955.tif 000022
【国際調査報告】
2015128955.tif 000023
2015128955.tif 000024
2015128955.tif 000025
2015128955.tif 000026