JP6034183B2 - 半導体記憶装置 - Google Patents

Description

本発明の実施形態は、半導体記憶装置に関する。

一般的なホストシステム、例えばコンピュータシステムが備えるストレージ装置として磁気式のハードディスクドライブ（ＨＤＤ）や、ＮＡＮＤフラッシュメモリのような不揮発性半導体メモリを搭載する固体ドライブ（ＳＳＤ）や、埋め込みＮＡＮＤフラッシュメモリなどがある。ＳＳＤや埋め込みＮＡＮＤフラッシュメモリはストレージに分類されるが、規模が拡張されたメモリシステムともいえる。

このようなメモリシステムでは、例えばインタフェースと、第１のメモリブロックと、第２のメモリブロックと、コントローラとから構成される。第１のメモリブロックはデータを格納し、第２のメモリブロックはデータの書き込み／読み出し時のバッファメモリである。

特許第４６７２７４２号公報

従来システムとして、ＳＳＤを想定して説明する。本明細書において、ＳＳＤは広い意味でのＮＡＮＤフラッシュベースの固体メモリによるストレージを意味し、組み込みＮＡＮＤフラッシュメモリシステムも含まれる。ＮＡＮＤフラッシュメモリは、書き込みがページ単位であるため、細かい単位のデータ書き込み要求（ページサイズ未満のデータの書き込み要求）が多くなった場合に、ＮＡＮＤフラッシュメモリに多くの空き領域が発生し、利用効率が低下するという問題がある。

本発明が解決しようとする課題は、データの書き込み先に無駄な空き領域が発生することを防止可能な半導体記憶装置を提供することである。

実施形態の半導体記憶装置は、第１記憶部と、第２記憶部と、書き込み制御部とを備える。第１記憶部は、ホスト装置から供給されるデータを含む情報を記憶する。第２記憶部は、第１記憶部からのデータの読み出しに用いられた論理アドレスを記憶する。書き込み制御部は、ホスト装置から第１記憶部に対する書き込みが要求されたデータのサイズが閾値未満の場合は、第２記憶部に記憶された論理アドレスをデータに付加して、第１記憶部に書き込む制御を行う。

本発明の概要を説明するための概念図。 第１実施形態の半導体記憶装置のハードウェア構成例を示す図。 第１実施形態のデバイスコントローラの機能構成例を示す図。 第１実施形態の第２記憶部の構成例を示す図。 第１実施形態のメモリコントローラの機能構成例を示す図。 第１実施形態の書き込み制御部による制御の一例を示す図。 第１実施形態の読み出し制御部による制御の一例を示す図。 変形例の半導体記憶装置のハードウェア構成例を示す図。 第２実施形態のデバイスコントローラの機能構成例を示す図。 第２実施形態の第２記憶部の構成例を示す図。 第２実施形態の第２書き込み制御部による制御の一例を示す図。 第１実施形態の検索制御部による制御の一例を示す図。

本発明に係る半導体記憶装置の実施の形態を説明する前に、本発明の概要を説明する。ここでは、ホスト装置から供給されるデータを記憶する第１記憶部は、ＮＡＮＤフラッシュメモリで構成される場合を例に挙げて説明する。ＮＡＮＤフラッシュメモリのページサイズ（例えば８ＫＢ）に比べて、検索メモリが扱うタグのようなメタデータのサイズは小さい。このため、タグのようなページサイズ未満のデータをＮＡＮＤフラッシュメモリに書き込む場合、その書き込みの際にＮＡＮＤフラッシュメモリに確保される１ページ分の記憶領域に空き領域が生じる。

実際、パーソナルコンピュータやモバイルフォンでのＮＡＮＤフラッシュメモリのユースケースの解析結果から、４ＫＢ以下の細かいデータが高い頻度で書き込まれていることが知られている。ここで、データの読み書きのユースケースを考慮すると、書き込まれるデータは、直近に読み出されていたデータと関係性を有する可能性が高い。例えばパーソナルコンピュータで、ドキュメントファイルを開きながらプレゼンテーションファイルを開いて、そのプレゼンテーションファイルを更新して保存する場合を想定する。その後、そのプレゼンテーションファイルを読むときに、ドキュメントファイルも読む可能性があるので、データを書くときは直近に読まれていたデータとの関連付けを記憶しておくと、その書き込まれたデータが読み出されるときに、効率的にその関連付けも引き出すことができる。

ＮＡＮＤフラッシュメモリのようなページ単位で読み書きが行われるメモリと、他のＲＡＭとの本質的な差に基づく有意な差は、ＮＡＮＤフラッシュメモリが大容量化に適していたとしても、ページ単位で書くために、ユースケースによっては容量を十分に活かせない可能性があることである。

本発明は、以上の点に着目し、ページの空き領域に、少しでも読み出し時に価値のある情報を書き込んでおくことが、メモリシステムの実運用での速度向上に有用であることを見出したことを特徴の一つとする。図１に示すように、本発明は、ＮＡＮＤフラッシュメモリに対する書き込みが要求されたデータ（以下、「書き込み対象データ」と呼ぶ場合がある）のサイズが、書き込み単位のサイズを示すページサイズ未満の場合（より具体的には、書き込み対象データのページ充当率が閾値（例えば５０％）未満の場合）は、データの読み出しに用いられたアドレス（例えば論理アドレスまたはキーアドレス）の履歴が保存された不図示のバッファメモリ（請求項の「第２記憶部」に対応）から直近のアドレスを読み出し、その読み出したアドレスを書き込み対象データに付加して、ページの冗長部以外の領域に空き領域が発生しないようにする。そして、ページの冗長部には、所定の冗長情報（例えば書き込みが要求されたデータに対してホスト装置から指定された論理アドレス、ＥＣＣ、パリティー、アドレス個数等）を追記して、ＮＡＮＤフラッシュメモリに書き込む。

その後、ＮＡＮＤフラッシュメモリに書き込まれた書き込み対象データの読み出しが要求された場合、書き込み対象データとともに、書き込み時に付加されたアドレスも読み出される。そして、読み出されたアドレスに対応するデータをＮＡＮＤフラッシュメモリから読み出してバッファメモリに保持しておく（つまり、先読みを行っておく）ことで、先読みされたデータの読み出し要求があった場合に、ＮＡＮＤフラッシュメモリにアクセスすることなくデータをホスト装置へ送ることができるので、書き込み対象データとの相関が強いデータを効率良く読み出すことができる。

以下、添付図面を参照しながら、本発明に係る半導体記憶装置の実施形態を詳細に説明する。

（第１実施形態）
図２は、第１実施形態の半導体記憶装置であるデバイス１００およびホスト装置２００のハードウェア構成の一例を示すブロック図である。図２に示すように、ホスト装置２００は、ＣＰＵ２０１と、メインメモリ２０２と、デバイス１００と接続するためのインタフェース部２０３とを備え、これらは、バス２０４を介して相互に接続されている。

デバイス１００は、コントローラチップ１１０と、第１記憶部１２０とを備える。コントローラチップ１１０は、ホストインタフェース部１１１と、デバイスコントローラ１１２と、第２記憶部１１３と、メモリコントローラ１１４とを備え、これらは、バス１１５を介して相互に接続されている。デバイス１００内では、高速かつ効率的なバス線配置が取られることが望ましい。一方、例えばインタフェース規格と外部インタフェース規格の相違などで、２種類以上のバス線がデバイス１００内で用いられていてもよい。

また、図１の例では、第１記憶部１２０は、メモリコントローラ１１４を介してコントローラチップ１１０と接続される。第１記憶部１２０は、ホスト装置２００から供給されるデータ（見方を変えれば、ホスト装置２００が利用するデータ）を記憶可能な装置である。本実施形態では、第１記憶部１２０は、ＮＡＮＤフラッシュメモリで構成されるが、これに限られるものではない。また、第１記憶部１２０は、記憶容量を増大させるため複数のチップで構成されていてもよい。第１記憶部１２０は、これに限定されるものではなく、記憶不揮発性を有する半導体メモリであればあらゆる記憶媒体を適用できる。例えば、第１記憶部１２０として、ＭＲＡＭ（Magnetoresistive Random Access Memory）やＲｅＲＡＭ（Resistance Random Access Memory）やＦｅＲＡＭ（Ferroelectric Random Access Memory）やＰＣＲＡＭ（Phase-Change Random Access Memory）などの不揮発性メモリを用いてもよい。

ホスト装置２００（インタフェース部２０３）は、例えばＡＭＢＡ（Advanced Microcontroller Bus Architecture）、などの外部バス３００を介して、デバイス１００側のホストインタフェース部１１１に接続される。例えばホストインタフェース部１１１は、ＳＡＴＡ（Serial Advanced Technology Attachment）、ＰＣＩ Ｅｘｐｒｅｓｓ、ｅＭＭＣ（embedded MMC）、ＵＦＳ（(Universal Flash Storage)）および、ＵＳＢ（Universal Serial Bus）などを適宜選択する。

ホストインタフェース部１１１は、デバイス１００の上位装置であるホスト装置２００からの要求を受け付けることができる。例えばホストインタフェース部１１１は、第１記憶部１２０に対するデータの書き込みを要求する書き込み要求や、第１記憶部１２０からのデータの読み出しを要求する読み出し要求をホスト装置２００から受け付けることができる。この例では、書き込み要求は、書き込みの実行を要求する情報と、書き込みを要求するデータと、プログラム上の仮想空間アドレスのうち、その書き込みを要求するデータが割り当てられる場所を示す論理アドレスとを含んで構成される。一方、読み出し要求は、読み出しの実行を要求する情報と、プログラム上の仮想空間アドレスのうち、読み出しを要求するデータが割り当てられる場所を示す論理アドレスとを含んで構成される。上記論理アドレスは、ホスト装置２００によって指定される。

デバイスコントローラ１１２は、ホストインタフェース部１１１で受け付けたホスト装置２００からの要求に応じて、第１記憶部１２０に対するデータの書き込みや第１記憶部１２０からのデータの読み出しを制御する制御装置である。デバイスコントローラ１１２の詳細な機能については後述する。

第２記憶部１１３は、第１記憶部１２０に比べて小容量であるが、第１記憶部１２０に比べて、書き換え／読み出し耐性が高いメモリである。第２記憶部１１３は、デバイスコントローラ１１２や後述のメモリコントローラ１１４による各種の演算結果を記憶しておくための作業領域を有する。また、第２記憶部１１３は、データの読み出しに用いられた論理アドレスの履歴（読み出し済みのデータに対応する論理アドレスの履歴）を記憶する領域を有する。第２記憶部１１３の詳細な内容については後述する。なお、第２記憶部１１３は、電源が遮断されても第２記憶部１１３に記憶されたデータが失われないための不揮発性を有していてもよい。例えば第１記憶部１２０がＮＡＮＤフラッシュメモリのとき、第２記憶部１１３は、ＭＲＡＭ、ＰＣＲＡＭ、ＲｅＲＡＭ、ＦｅＲＡＭなどで構成され得る。

メモリコントローラ１１４は、デバイスコントローラ１１２の制御の下、ホスト装置２００から供給されるデータを第１記憶部１２０に書き込む、または、第１記憶部１２０に格納されたデータを読み出す機能を有するハードウェアモジュールである。メモリコントローラ１１４の詳細な機能については後述する。

次に、デバイスコントローラ１１２の詳細な機能について説明する。図３は、デバイスコントローラ１１２の機能構成例を示すブロック図である。図３に示すように、デバイスコントローラ１１２は、受付部１０１と、書き込み制御部１０２と、読み出し制御部１０３とを有する。受付部１０１は、ホスト装置２００からの要求を受け付ける。

書き込み制御部１０２は、受付部１０１で書き込み要求を受け付けた場合、書き込みが要求されたデータ（書き込み要求に含まれるデータ、以下、「書き込み対象データ」と呼ぶ場合がある）を含む情報を、第１記憶部１２０に書き込む制御（以下、「書き込み制御」と呼ぶ場合がある）を行う。後述するように、書き込み制御の対象となる情報には、所定の冗長情報のほか、書き込み対象データに付加された論理アドレスが含まれる場合もある。本実施形態では、書き込み制御部１０２は、書き込みの実行を命令する書き込みコマンドを生成し、生成した書き込みコマンドに対して、書き込み対象データを含む情報（書き込み制御の対象となる情報）と、第１記憶部１２０のうち、書き込み対象データが書き込まれる領域を示す物理アドレスとを付加してメモリコントローラ１１４へ伝達する。なお、第１記憶部１２０に対するデータや冗長情報を含む情報の書き込みは、論理アドレスとは無関係に、ページの昇順に行なわれる。

ここで、書き込み制御部１０２は、書き込み対象データのサイズが閾値未満の場合は、第２記憶部１１３に記憶された論理アドレス（データの読み出しに用いられた論理アドレス）を書き込み対象データに付加して、第１記憶部１２０に書き込む制御を行う。より具体的には、書き込み制御部１０２は、書き込み対象データのサイズが、書き込み単位を示すページサイズ未満の場合は、第２記憶部１１３に記憶された論理アドレスを書き込み対象データに付加して、第１記憶部１２０に書き込む制御を行う。さらに言えば、書き込み制御部１０２は、書き込み対象データのページ充当率（ページサイズのうち書き込み対象データが占める割合）が５０％未満の場合は、ページの冗長部以外の領域に空き領域が発生しないよう、第２記憶部１１３に記憶された論理アドレスを書き込み対象データに付加するとともに、少なくとも、書き込み対象データの長さを特定可能な情報を示すオフセットを冗長部に追記して、第１記憶部１２０に書き込む制御を行う。この場合、書き込み制御の対象となる情報は、サイズが閾値未満の書き込み対象データと、その書き込み対象データに付加された論理アドレスと、冗長部に記載された冗長情報（少なくともオフセットを含む）とを含んで構成される。

さらに、書き込み制御部１０２は、書き込み制御を行うたびに、ホスト装置２００により指定される論理アドレスと、第１記憶部１２０内の位置を示す物理アドレスとの対応関係を示す論物変換情報を更新する制御を行う。より具体的には、書き込み制御部１０２は、書き込み制御を行うたびに、ホスト装置２００から受け付けた書き込み要求に含まれる論理アドレスと、第１記憶部１２０のうち書き込み対象データを書き込む位置（領域）を示す物理アドレスとを対応付けて、新たに論物変換情報に追加する制御を行う。この例では、論物変換情報はテーブル形式のデータ構造であり、本体は第１記憶部１２０に格納されるが、論物変換が行われるときは、第２記憶部１１３に読み出されて使われる。以下の説明では、本実施形態における論物変換情報を、「論物変換テーブル」と呼ぶ（「Ｌ２Ｐテーブル」と呼ぶ場合もある）。本実施形態では、論物変換テーブルの内容は、書き込み制御部１０２による書き込み制御が行われるたびに更新される。

次に、読み出し制御部１０３の機能を説明する。読み出し制御部１０３は、受付部１０１で読み出し要求を受け付けた場合、論物変換テーブルを参照して、読み出し要求に含まれる論理アドレスに対応付けられた物理アドレスを特定し（論物変換を行い）、特定した物理アドレスが示す位置に格納された情報を読み出す制御（以下、「第１の読み出し制御」と呼ぶ場合がある）を行う。本実施形態では、読み出し制御部１０３は、メモリコントローラ１１４に対して読み出しの実行を命令する読み出しコマンドを生成し、その生成した読み出しコマンドに対して、上述の論物変換により得た物理アドレスを付加してメモリコントローラ１１４へ伝達する。そして、読み出し制御部１０３は、読み出しコマンドに対する応答として、メモリコントローラ１１４が第１記憶部１２０から読み出した情報を受け取ることができる。

読み出し制御部１０３は、第１の読み出し制御により読み出した情報の中に、書き込み制御部１０２によってデータに付加された論理アドレスが含まれていた場合は、論物変換テーブルを参照して、書き込み制御部１０２によってデータに付加された論理アドレスに対応する物理アドレスを特定する。本実施形態では、読み出し制御部１０３は、第１の読み出し制御により読み出した情報に含まれるオフセットを参照して、データ長が閾値未満であると判断した場合（この例では、データ長のページ充当率が５０％未満であると判断した場合）、読み出した情報のデータおよび冗長部以外の部分から、書き込み時にデータに付加された論理アドレスを取得する。そして、読み出し制御部１０３は、論物変換テーブルを参照して、取得した論理アドレスに対応する物理アドレスを特定する。

読み出し制御部１０３は、第１記憶部１２０のうち、以上のようにして特定した物理アドレスが示す位置に格納された情報を読み出す制御（以下、「第２の読み出し制御」と呼ぶ場合がある）を行う。本実施形態では、読み出し制御部１０３は、メモリコントローラ１１４に対して読み出しの実行を命令する読み出しコマンドを生成し、生成した読み出しコマンドに対して、以上のようにして特定した物理アドレスを付加してメモリコントローラ１１４へ伝達する。読み出し制御部１０３は、読み出しコマンドに対する応答として、メモリコントローラ１１４が第１記憶部１２０から読み出した情報を受け取ることができる。そして、読み出し制御部１０３は、第２の読み出し制御により読み出した情報に含まれるデータと論理アドレスとを対応付けて第２記憶部１１３に記憶させる制御を行う。

したがって、第２の読み出し制御が行われるたびに、第２記憶部１１３には、第２の読み出し制御に用いられた論理アドレスと、データとが対応付けられて記憶されていく。以下の説明では、第２記憶部１１３に記憶された、第２の読み出し制御に用いられた論理アドレスと、その論理アドレスに対応付けられたデータとの組をキャッシュデータと呼ぶ場合がある。

読み出し制御部１０３は、受付部１０１で受け付けた読み出し要求に含まれる論理アドレスと一致する論理アドレスと、データとが対応付けられて第２記憶部１１３に記憶されている場合は、読み出し要求に含まれる論理アドレスと一致する論理アドレスに対応付けられたデータを第２記憶部１１３から読み出す第３の読み出し制御を行う。つまり、第２記憶部１１３に記憶された１以上のキャッシュデータの中に、読み出し要求に含まれる論理アドレスと一致する論理アドレスを含むキャッシュデータが存在する場合は、読み出し制御部１０３は、そのキャッシュデータに含まれるデータを読み出す制御を行う。この場合、読み出し制御部１０３は、第１記憶部１２０からデータを読み出す制御を行う必要が無いので、読み出し速度の向上が図られる。

また、読み出し制御部１０３は、第１の読み出し制御を行うたびに、少なくとも、その第１の読み出し制御に用いた論理アドレスを第２記憶部１１３に記憶させる制御を行う。例えば読み出し制御部１０３は、第２記憶部１１３（例えば後述の第３記憶部１３０）の容量の範囲内において、第１の読み出し制御に用いた論理アドレスと、第１の読み出し制御により読み出したデータとを対応付けて第２記憶部１１３に記憶させることもできる。

さらに、読み出し制御部１０３は、第１の読み出し制御または第２の読み出し制御に用いた論理アドレスを第２記憶部１１３に記憶させる場合、第１記憶部１２０からの情報の読み出しが行われた時間（時刻）を示す時間情報を対応付けて記憶させる。したがって、本実施形態では、第２記憶部１１３は、第１の読み出し制御または第２の読み出し制御に用いられた論理アドレスごとに、読み出しが行われた時間（第１の読み出し制御または第２の読み出し制御が行われた時間）を示す時間情報を対応付けて記憶する。第２記憶部１１３のより詳細な内容については後述する。

ここで、前述の書き込み制御部１０２は、書き込み対象データのサイズが閾値未満の場合は、第２記憶部１１３に記憶された論理アドレスの中から、その書き込み対象データの書き込みが要求されたとき（書き込み要求を受け付けたとき）よりも前の所定期間内における読み出しに用いられた論理アドレスを選択して書き込み対象データに付加する。より具体的には、書き込み制御部１０２は、書き込み対象データのサイズが閾値未満の場合は、第２記憶部１１３に記憶された論理アドレスの中から、上記所定期間内に含まれる時間を示す時間情報に対応する論理アドレスを選択して書き込み対象データに付加する。

さらに詳述すれば、以下のとおりである。本実施形態では、図４に示すように、第２記憶部１１３は、第３記憶部１３０と第４記憶部１４０とを備える。第３記憶部１３０は、第１の読み出し制御に用いられた論理アドレスごとに、第１の読み出し制御による読み出しが行われた時間を示す時間情報を対応付けて記憶する。第４記憶部１４０は、第２の読み出し制御に用いられた論理アドレスごとに、第２の読み出し制御により読み出されたデータと、第２の読み出し制御による読み出しが行われた時間を示す時間情報とを対応付けて記憶する。そして、書き込み制御部１０２は、書き込み対象データのサイズが閾値未満の場合は、第３記憶部１３０および第４記憶部１４０の各々に記憶された論理アドレスの中から、所定期間内に含まれる時間を示す時間情報に対応する論理アドレス（第１の読み出し制御に用いられた論理アドレスでもよいし、第２の読み出し制御に用いられた論理アドレスでもよい）を選択して、書き込み対象データに付加する。

なお、上記所定期間は任意に設定可能であり、例えば受付部１０１がホスト装置２００からの書き込み要求を受け付けた時点を示す書込み要求時点よりも予め定められた時間だけ前の時点から、書込み要求時点までの期間を、所定期間として設定することもできる。

また、上記所定期間の長さは任意に設定可能であるが、例えば、デバイス１００の電源がＯＮになってからの読み出しに用いられた論理アドレスの履歴を保存しておいたとしても、ページサイズ未満の書き込み対象データ（書き込みが要求されたデータ）を書き込む際に、あまりにも離れた時間における読み出しに用いられた論理アドレスを、その書き込み対象データに付け足して書き込んでも、相関が小さくなり、十分な先読み効果が得られないおそれがある。具体例としては、スマートフォンの場合、一日に扱われる時間は統計的に５０分以下が多いため、書き込みを行うとき（例えば書き込み要求時点）から５０分以下の間隔で読み出されたデータならば、その書き込みを行うデータとの相関が強いと考えることができる。したがって、書き込みを行うときから５０分以下の間隔で読み出されたデータに対応する論理アドレスを、書き込み対象データに付加して書き込んでおけば、書き込み対象データとの相関が強いデータを効率よく読み出すことができる。また、例えばＰＣの場合、一日に扱われる時間は３時間未満が統計的に過半数を占めるため、間隔が３時間未満の間隔で読み出されたデータに対応する論理アドレスを、ページサイズ未満の書き込み対象データに付加して書き込んでおくことにより、その書き込み対象データとの相関が強いデータを効率よく読み出すことができる。

また、例えば書き込み制御部１０２は、書き込み制御を行うたびに、書き込み要求に含まれる論理アドレスと、書き込み制御による書き込みが行われた時間（時刻）を示す時間情報とを対応付けて第３記憶部１３０に記憶させる制御を行うこともできる。この場合、直前の書き込みが行われた時点（例えば受付部１０１が直前の書き込み要求を受け付けた時点）から、最新の書き込みが行われる時点までの期間を、所定期間として設定することもできる。

本実施形態では、デバイスコントローラ１１２は、例えばＣＰＵ等を含んで構成され、ＣＰＵが不図示のＲＯＭ等に格納されたプログラムを実行することにより、上述の受付部１０１、書き込み制御部１０２、および、読み出し制御部１０３の各々の機能が実現されるが、これに限らず、例えば上述の受付部１０１、書き込み制御部１０２、および、読み出し制御部１０３のうちの少なくとも一部が専用のハードウェア回路で実現されてもよい。

次に、メモリコントローラ１１４の機能について説明する。図５は、メモリコントローラ１１４の機能構成例を示すブロック図である。図５に示すように、メモリコントローラ１１４は、コマンド受信部１０４と、訂正部１０５と、書き込み部１０６と、読み出し部１０７とを有する。

コマンド受信部１０４は、デバイスコントローラ１１２から送信されるコマンド（書き込みコマンドまたは読み出しコマンド）を受信する。訂正部１０５は、コマンド受信部１０４で受信した書き込みコマンドに付加された情報（書き込み制御部１０２による書き込み制御の対象となる情報）の符号化処理を行う。この例では、訂正部１０５は、第１記憶部１２０に対する書き込みを行うべき情報に対して、ビットの誤り訂正処理（ＥＣＣ処理）を行うための冗長情報（データビットの偶奇性を利用する場合、パリティーと呼ぶ）を付加する処理を行う。また、訂正部１０５は、後述の読み出し部１０７により第１記憶部１２０から読み出された情報に対する誤り訂正処理（ＥＣＣ処理）を行う。ここでは、第２記憶部１１３は、訂正部１０５による符号化処理の作業領域を更に有する。また、第２記憶部１１３は、訂正部１０５による誤り訂正処理の作業領域を更に有する。つまり、第２記憶部１１３は、訂正部１０５による符号化処理および誤り訂正処理のワークメモリとしても機能する。

書き込み部１０６は、コマンド受信部１０４で受信した書き込みコマンドに従って、第１記憶部１２０に対する情報の書き込みを行う。より具体的には、書き込み部１０６は、第１記憶部１２０のうち、書き込みコマンドに付加された物理アドレスが示す領域に対して、訂正部１０５によって符号化された情報を書き込む。また、読み出し部１０７は、コマンド受信部１０４で受信した読み出しコマンドに従って、第１記憶部１２０からの情報の読み出しを行う。より具体的には、読み出し部１０７は、第１記憶部１２０のうち、読み出しコマンドに付加された物理アドレスが示す領域に格納された情報を読み出す。読み出し部１０７によって読み出された情報は、訂正部１０５による誤り訂正処理によって復号され、復号された情報が、読み出しコマンドに対する応答として、デバイスコントローラ１１２（読み出し制御部１０３）へ送られる。

本実施形態では、メモリコントローラ１１４は、ハードウェアモジュールで構成され、上述のコマンド受信部１０４、訂正部１０５、書き込み部１０６、および、読み出し部１０７の各々は、専用のハードウェア回路で実現されるが、これに限らず、例えばメモリコントローラ１１４がＣＰＵ等を含んで構成され、ＣＰＵが不図示のＲＯＭ等に格納されたプログラムを実行することにより、上述のコマンド受信部１０４、訂正部１０５、書き込み部１０６、および、読み出し部１０７のうちの少なくとも一部の機能が実現される形態であってもよい。

次に、図６を参照しながら、前述の書き込み制御部１０２による制御の一例を説明する。図６は、書き込み制御部１０２による制御の一例を示すフローチャートである。この例では、ホスト装置２００からの書き込み要求を受付部１０１で受け付けたことを前提として説明する。図６に示すように、書き込み制御部１０２は、書き込み要求に含まれるデータ（書き込み対象データ）のサイズが閾値未満であるか否かを確認する（ステップＳ１）。上述したように、本実施形態では、書き込み込み制御部１０２は、書き込み対象データのページ充当率が５０％未満であるか否かを確認する。書き込み対象データのサイズが閾値以上であると判断した場合（ステップＳ１：ＮＯ）、処理は、後述のステップＳ６に移行する。

上述のステップＳ１において、書き込み対象データのサイズが閾値未満であると判断した場合（ステップＳ１：ＹＥＳ）、書き込み制御部１０２は、空き領域のサイズを算出する（ステップＳ２）。次に、書き込み制御部１０２は、算出した空き領域のサイズが閾値以上であるか否かを確認する（ステップＳ３）。この閾値は、空き領域のサイズが、少なくとも１つの論理アドレスのサイズ以上であるか否かを判定可能な値に設定される。算出した空き領域のサイズが閾値未満であると判断した場合（ステップＳ３：ＮＯ）、処理は、後述のステップＳ６に移行する。

一方、算出した空き領域のサイズが閾値以上であると判断した場合（ステップＳ３：ＹＥＳ）、書き込み制御部１０２は、第２記憶部１１３に記憶された論理アドレスの中から、所定期間内に含まれる時間を示す時間情報に対応する論理アドレスを取得（選択）する（ステップＳ４）。本実施形態では、書き込み制御部１０２は、第３記憶部１３０および第４記憶部１４０の各々に記憶された論理アドレスの中から、所定期間内に含まれる時間を示す時間情報に対応する論理アドレスを、算出した空き領域のサイズを超えないよう、時間が早いものから順に選択する。

次に、書き込み制御部１０２は、ステップＳ４で選択した１以上の論理アドレスを、書き込み対象データに付加する（ステップＳ５）。次に、書き込み制御部１０２は、受付部１０１で受け付けた書き込み要求に含まれる論理アドレスと、書き込み対象データのデータ長を特定可能なオフセットとを、書き込み単位のページサイズのうち冗長部分の領域を示す冗長部に追記する（ステップＳ６）。次に、書き込み制御部１０２は、メモリコントローラ１１４に対する書き込みの実行を命令する書き込みコマンドを生成し、生成した書き込みコマンドに対して、書き込み制御の対象となる情報と、第１記憶部１２０のうち書き込み対象データを書き込む位置を示す物理アドレスとを付加してメモリコントローラ１１４へ送信する（ステップＳ７）。そして、書き込み制御部１０２からの書き込みコマンドを受信したメモリコントローラ１１４は、受信した書き込みコマンドに従って、第１記憶部１２０に対する情報の書き込みを行う。メモリコントローラ１１４は、受信した書き込みコマンドに従った書き込みが完了すると、書き込みコマンドに対する応答として、書き込みが完了したことを示す通知情報を書き込み制御部１０２へ送信する。これにより、書き込み制御部１０２は、書き込みが完了したことを知ることができる。

次に、書き込み制御部１０２は、論物変換テーブル（Ｌ２Ｐテーブル）を更新する（ステップＳ８）。上述したように、本実施形態では、書き込み制御部１０２は、受付部１０１で受け付けた書き込み要求に含まれる論理アドレスと、第１記憶部１２０のうち書き込み対象データを書き込む位置を示す物理アドレスとを対応付けて、新たに論物変換テーブルに追加する制御を行う。

次に、図７を参照しながら、前述の読み出し制御部１０３による制御の一例を説明する。図７は、読み出し制御部１０３による制御の一例を示すフローチャートである。この例では、ホスト装置２００からの読み出し要求を受付部１０１で受け付けたことを前提として説明する。図７に示すように、まず、読み出し制御部１０３は、読み出し要求に含まれる論理アドレスと一致する論理アドレスと、データとが対応付けられて第２記憶部１１３に記憶されているか否かを確認する（ステップＳ１０）。上述したように、本実施形態では、読み出し制御部１０３は、読み出し要求に含まれる論理アドレスを含むキャッシュデータが第４記憶部１４０に記憶されているか否かを確認する。

上述のステップＳ１０において、読み出し要求に含まれる論理アドレスと一致する論理アドレスと、データとが対応付けられて第２記憶部１１３に記憶されていると判断した場合（ステップＳ１０：ＹＥＳ）、つまり、読み出し要求に含まれる論理アドレスを含むキャッシュデータが第４記憶部１４０に存在すると判断した場合、読み出し制御部１０３は、読み出し要求に含まれる論理アドレスと一致する論理アドレスに対応付けられたデータを第２記憶部１１３から読み出し、読み出したデータを、読み出し要求に対する応答としてホスト装置２００へ送信する（ステップＳ１１）。以上のステップＳ１１の内容が、第３の読み出し制御に相当する。一方、上述のステップＳ１０において、読み出し要求に含まれる論理アドレスと一致する論理アドレスと、データとが対応付けられて第２記憶部１１３に記憶されていないと判断した場合（ステップＳ１０：ＮＯ）、つまり、読み出し要求に含まれる論理アドレスを含むキャッシュデータが第４記憶部１４０に存在しないと判断した場合、処理は、ステップＳ１２に移行する。

ステップＳ１２において、読み出し制御部１０３は、論物変換テーブルを参照して、読み出し要求に含まれる論理アドレスに対応する物理アドレスを特定する（ステップＳ１２）。次に、読み出し制御部１０３は、メモリコントローラ１１４に対して読み出しの実行を命令する読み出しコマンドを生成し、生成した読み出しコマンドに対して、ステップＳ１２で特定した物理アドレスを付加してメモリコントローラ１１４へ送信する（ステップＳ１３）。読み出しコマンドを受信したメモリコントローラ１１４は、受信した読み出しコマンドに従って、第１記憶部１２０から情報を読み出し、読み出した情報を読み出し制御部１０３へ送信する。つまり、読み出し制御部１０３は、読み出しコマンドに対する応答として、メモリコントローラ１１４により読み出された情報を受信する（ステップＳ１４）。

以上のステップＳ１２〜ステップＳ１４の内容が、第１の読み出し制御に相当する。次に、読み出し制御部１０３は、第１の読み出し制御により読み出した情報に含まれるオフセットを参照して、データ長が閾値未満であるか否かを確認する（ステップＳ１５）。上述したように、本実施形態では、読み出し制御部１０３は、データ長のページ充当率が５０％未満であるか否かを確認する。データ長が閾値以上であると判断した場合（ステップＳ１５：ＮＯ）、読み出し制御部１０３は、第１の読み出し制御により読み出した情報に含まれるデータを、読み出し要求に対する応答としてホスト装置２００へ送信する（ステップＳ１６）。

一方、上述のステップＳ１５において、データ長が閾値未満であると判断した場合（ステップＳ１５：ＹＥＳ）、読み出し制御部１０３は、第１の読み出し制御により読み出した情報のうち、データと冗長部以外の部分から、書き込み時にデータに付加された論理アドレスを取得する（ステップＳ１７）。また、本実施形態では、ステップＳ１７の処理と並行して、読み出し制御部１０３は、第１の読み出し制御により読み出した情報に含まれる、閾値未満のサイズのデータを、読み出し要求に対する応答としてホスト装置２００へ送信することもできる。なお、これに限らず、第１の読み出し制御により読み出した情報に含まれる、閾値未満のサイズのデータをホスト装置２００へ送信するタイミングは任意に変更可能である。

次に、読み出し制御部１０３は、論物変換テーブルを参照して、ステップＳ１７で取得した１以上の論理アドレスごとに、論理アドレスに対応する物理アドレスを特定する（ステップＳ１８）。次に、読み出し制御部１０３は、メモリコントローラ１１４に対して読み出しの実行を命令する読み出しコマンドを生成し、生成した読み出しコマンドに対して、ステップＳ１８で特定した物理アドレスを付加してメモリコントローラ１１４へ送信する（ステップＳ１９）。読み出しコマンドを受信したメモリコントローラ１１４は、受信した読み出しコマンドに従って、第１記憶部１２０から情報を読み出し、読み出した情報を読み出し制御部１０３へ送信する。つまり、読み出し制御部１０３は、読み出しコマンドに対する応答として、メモリコントローラ１１４により読み出された情報を受信する（ステップＳ２０）。

以上のステップＳ１７〜ステップＳ２０の内容が、第２の読み出し制御に相当する。ステップＳ２０の後、読み出し制御部１０３は、メモリコントローラ１１４から受信した情報（第２の読み出し制御により読み出した情報）に含まれるデータと、論理アドレスとを対応付けて第２記憶部１１３（第４記憶部１４０）に記憶させる制御を行う（ステップＳ２１）。これにより、第４記憶部１４０には、先読みのキャッシュデータが新たに追加されることになる。

以上に説明したように、本実施形態では、書き込み対象データのサイズが閾値未満の場合は、読み出しに用いられた論理アドレス（読み出し済みのデータに対応する論理アドレス）が当該書き込み対象データに付加されて第１記憶部１２０に書き込まれるので、データの書き込み先である第１記憶部１２０内に無駄な空き領域が発生することを防止できる。

また、本実施形態では、閾値未満のサイズの書き込み対象データに付加される論理アドレスとしては、書き込み対象データの書き込みが要求された時よりも前の所定期間内における読み出しに用いられた論理アドレスが採用される。そして、閾値未満のサイズの書き込み対象データが第１記憶部１２０に書き込まれた後、その書き込み対象データの読み出しが要求された場合は、その書き込み対象データとともに、書き込み時に付加された論理アドレスも読み出される。そして、その読み出された論理アドレスに対応するデータが第１記憶部１２０から読み出され（先読みされ）、論理アドレスと対応付けられたキャッシュデータとして第２記憶部１１３に保持されるので、先読みされたデータの読み出し要求があった場合は、第１記憶部１２０にアクセスすることなく、要求されたデータをホスト装置２００に送ることができる。したがって、本実施形態によれば、第１記憶部１２０内に無駄な空き領域が発生することを防止しつつ書き込み対象データとの相関が強いデータを効率良く読み出すことができるという有利な効果を達成できる。

（第１実施形態の変形例１）
例えば先読みのキャッシュデータに含まれる論理アドレスは、閾値未満のサイズの書き込み対象データに付加されない形態であってもよい。この場合、第４記憶部１４０は、時間情報を保持する必要が無いので、少なくとも、第２の読み出し制御に用いられた論理アドレスと、第２の読み出し制御により読み出されたデータとを対応付けて記憶するものであればよい。そして、書き込み制御部１０２は、書き込み対象データのサイズが閾値未満の場合は、第３記憶部１３０に記憶された論理アドレスの中から、所定期間内に含まれる時間を示す時間情報に対応する論理アドレスを選択して書き込み対象データに付加する制御を行う。

（第１実施形態の変形例２）
例えば第３記憶部１３０は、ＦＩＦＯ（Ｆｉｒｓｔ−Ｉｎ−Ｆｉｒｓｔ−Ｏｕｔ）方式のメモリで構成されてもよい。つまり、論理アドレスの蓄積量が第３記憶部１３０の容量を超える場合、古い論理アドレスから順番に削除されていくという具合である。

（第１実施形態の変形例３）
例えばデバイスコントローラ１１２やメモリコントローラ１１４による各種の演算結果を記憶しておくための作業領域を十分に確保するために、図８に示すように、第２記憶部１１３とは別に（コントローラチップ１１０とは別に）バッファメモリ１５０が設けられる形態であってもよい。図８の例では、バッファメモリ１５０は、コントローラチップ１１０内のバス１１５に接続されている。例えば第２記憶部１１３がＳＲＡＭで構成され、バッファメモリ１５０がＤＲＡＭで構成される場合、ＳＲＡＭの方がＤＲＡＭよりもアクセス速度（読み出し／書き込み速度）が速いため、第１記憶部１２０に格納されている論物変換テーブルを、一旦、バッファメモリ１５０に移しておき、その一部を、第２記憶部１１３へ移して利用することもできる。

（第２実施形態）
次に、第２実施形態について説明する。上述の第１実施形態と共通する部分については、同一の符号を付して適宜に説明を省略する。第２実施形態の半導体記憶装置は、第１実施形態で説明した書き込み／読み出しの機能に加えて、検索機能を有する。以下、第２実施形態の半導体記憶装置の説明の前に、検索方式と方法を説明する。

半導体記憶装置に保存されている、あるテキストに関連付けられた別のテキスト、バイナリファイルにおける特定のビットパターン、動画ファイルにおける特定パターン、および、音声ファイルにおける特徴的な音声パターンなどのデータを効率的に取り出すためには、データを指定したデータ読み出し機能を持たせることが望ましい。このため、データに関連付けられたメタデータを付属させて保存しておき、所望のデータを得るためにメタデータを参照する方法が用いられる。メタデータの管理方法の１つとして、１対１または１対多にデータが対応するＫＶＳ（ｋｅｙ−ｖａｌｕｅ ｓｔｏｒｅ（キーバリューストア））が存在する。ＫＶＳでは、検索要求としてキー（ｋｅｙ）が与えられると、それに対応付けられるバリュー（ｖａｌｕｅ）が出力される。

第２実施形態の半導体記憶装置は、ＫＶＳデータ（キーバリュー情報）を、アドレス変換テーブルによって効率的かつ高速に処理する。このアドレス変換テーブルを、Ｋ２Ｐテーブルと呼び、キーから得た固定長アドレス（キーアドレス）と物理アドレスの変換テーブルである。以下、ＫＶＳデータを取り出す処理の具体例を説明する。一般的にＫＶＳとは、キー（ｋｅｙ）と値（ｖａｌｕｅ）の組を書き込み、キーを指定することで値を読み出せるデータベース管理方式を意味する。一般的にはネットワーク越しに使われる例が多い。データの格納先は、いずれかのローカルのメモリまたはストレージシステムであることは間違いない。

通常、データは、保存されているメモリの先頭アドレスとデータ長を指定することで読み出される。データアドレスは、ホストシステムのＯＳやファイルシステムによって、例えば５１２バイトのセクタ単位で管理される。または、ファイルシステムを限定する必要がなければ、例えばＮＡＮＤフラッシュメモリの読み出し／書き込みページサイズに合わせて、４ＫＢや８ＫＢ単位で管理されてもよい。

最も単純な検索手順は、以下の（１）〜（３）のようになる。
（１）キーをＨａｓｈ関数などにより固定長データへ変換し、その固定長データを使用可能なメモリのアドレスに変換して固定長アドレスを得る。変換した固定長アドレスをキーアドレスとする。
（２）ＮＡＮＤフラッシュメモリ内に保存されているＫ２Ｐテーブルを参照し、物理アドレスを得る。
（３）物理アドレスのデータを読み、メモリシステム外へ出力する。
このような実データアドレスとＫＶＳデータの関係、および、キーとバリューの関係は、要素と集合の関係となっている。すなわち、通常のファイルでは、例えば「ａ−ｆｉｌｅ．ｔｘｔ」というファイル名のファイルが集合であり、そのファイルの中身に「Ｔｈｉｓ ｉｓ a ｂｏｏｋ」というテキストデータがあれば、そのそれぞれの単語が要素である。

一方、キーバリューではメタデータアドレス空間に置かれた場合、集合と要素の関係が逆転して整理し直されている。すなわち、「転置」の関係に変換して保存することができる。例えば「ｂｏｏｋ」という集合の中には、「ａ−ｆｉｌｅ．ｔｘｔ」、「ｂ−ｆｉｌｅ．ｔｘｔ」というファイル名が要素として保存されることになる。キーバリューでは、この整理しなおされた集合名（「ｂｏｏｋ」）を検索し、その要素（「ａ−ｆｉｌｅ．ｔｘｔ」、「ｂ−ｆｉｌｅ．ｔｘｔ」）を求めていることになる。これは一般に全文検索で実行されている転置ファイル作成、および、検索手順そのものであって、キーバリューの実用上の一例といえる。

以上のようなＫ２ＰによるＫＶＳ方式の検索ストレージを製造するには、検索要求を受けて蓄えるための不揮発バッファメモリを備えることが望ましい。また、上記のようにＫ２ＰテーブルはＮＡＮＤフラッシュメモリから読み出され、バッファメモリに展開されるので、そのバッファメモリは不揮発である方が急な電源遮断に備えるためには望ましい。実用上の検索要求は単一であることは稀であり、複数の検索結果がデバイス内で処理される。このため検索演算、すなわちＡＮＤ、ＯＲ、ＮＯＴ等の集合演算を効率的に行うための高速な不揮発バッファメモリを備えることが望ましい。検索要求は、不揮発バッファ内でデータ処理が終わるまで確実に保存されていなければならないので、長期信頼性を有する不揮発メモリが望ましい。

以下、第２実施形態の半導体記憶装置の具体的な内容を説明する。基本的な構成は、第１実施形態に係るデバイス１００の構成と同様であるので、検索機能に関する部分を中心に説明する。

図９は、第２実施形態のデバイスコントローラ２１０の機能構成例を示すブロック図であり、検索機能に関する部分のみを例示している。図９に示すように、デバイスコントローラ２１０は、受付部２１１と、第２書き込み制御部２１２と、検索制御部２１３とを有する。この例では、第２書き込み制御部２１２は、請求項１１の「書き込み制御部」に対応している。

第２実施形態の第２記憶部２２０は、第１記憶部１２０に記憶されたデータのうち、ホスト装置２００から指定されたキーに対応するデータを検索するのに用いられたキーアドレスを記憶する。第２記憶部２２０の詳細な内容については後述する。

第２実施形態のメモリコントローラ２５０は、第１実施形態と同様に、デバイスコントローラ２１０の制御の下、第１記憶部１２０に対する情報の書き込みや読み出しを実行する。メモリコントローラ２５０の機能は、第１実施形態とほぼ同様であるため、ここでは詳細な説明を省略する。

図９に戻り、デバイスコントローラ２１０の機能を説明する。受付部２１１は、ホスト装置２００からの要求を受け付ける。ここでは、受付部２１１は、データと、当該データに関連付けられたメタデータを示すキーとの組の書き込みを要求するキーバリュー書き込み要求、指定のキーに対応付けられたデータの検索を要求する検索要求、検索結果を絞り込むための集合演算条件などを受け付ける。キーバリュー書き込み要求は、書き込みの実行を要求する情報と、キーとデータの組（キ―バリューのセット）とを含んで構成され、検索要求は、検索の実行を要求する情報と、ホスト装置２００により指定されたキーとを含んで構成される。

次に、第２書き込み制御部２１２の機能を説明する。受付部２１１でキーバリュー書き込み要求を受け付けた場合、第２書き込み制御部２１２は、キーバリュー書き込み要求に含まれるキーを、ハッシュ化して、固定長のデータから構成されるキーアドレスに変換する。そして、書き込み制御部２１２は、キーバリュー書き込み要求に含まれるデータ（以下、「書き込み対象バリューデータ」と呼ぶ場合がある）を含む情報を、第１記憶部１２０に書き込む制御（以下、「第２書き込み制御」と呼ぶ場合がある）を行う。後述するように、第２書き込み制御の対象となる情報には、所定の冗長情報のほか、書き込み対象バリューデータに付加されたキーアドレスが含まれる場合もある。第２実施形態では、第２書き込み制御部２１２は、書き込みの実行を命令する書き込みコマンドを生成し、生成した書き込みコマンドに対して、書き込み対象バリューデータを含む情報（第２書き込み制御の対象となる情報）と、第１記憶部１２０のうち、書き込み対象バリューデータが書き込まれる領域を示す物理アドレスとを付加してメモリコントローラ２５０へ伝達する。

ここで、第２書き込み制御部２１２は、書き込み対象バリューデータのサイズが閾値未満の場合は、第２記憶部２２０に記憶されたキーアドレス（ホスト装置２００から指定されたキーに関連するデータの検索に用いられたキーアドレス）を書き込み対象バリューデータに付加して、第１記憶部１２０に書き込む制御を行う。第２実施形態では、第２書き込み制御部１０２は、書き込み対象バリューデータのページ充当率が５０％未満の場合は、ページの冗長部以外の領域に空き領域が発生しないよう、第２記憶部２２０に記憶されたキーアドレスを書き込み対象バリューデータに付加するとともに、少なくとも、書き込み対象バリューデータの長さを特定可能な情報を示すオフセットを冗長部に追記して、第１記憶部１２０に書き込む制御を行う。この場合、第２書き込み制御の対象となる情報は、サイズが閾値未満の書き込み対象バリューデータと、その書き込み対象バリューデータに付加されたキーアドレスと、冗長部に記載された冗長情報（少なくともオフセットを含む）とを含んで構成される。

さらに、第２書き込み制御部２１２は、第２書き込み制御を行うたびに、ホスト装置２００から指定されるキーを変換して得られるキーアドレスと、第１記憶部１２０内の位置を示す物理アドレスとの対応関係を示すアドレス変換情報（以下、「Ｋ２Ｐテーブル」と呼ぶ場合がある）を更新する制御を行う。より具体的には、第２書き込み制御部２１２は、第２書き込み制御を行うたびに、ホスト装置２００から受け付けたキーバリュー書き込み要求に含まれるキーを変換して得られたキーアドレスと、第１記憶部１２０のうち書き込み対象バリューデータを書き込む位置を示す物理アドレスとを対応付けて、新たにＫ２Ｐテーブルに追加する制御を行う。この例では、Ｋ２Ｐテーブル本体は第１記憶部１２０に格納されるが、アドレス変換（Ｋ２Ｐ変換）が行われるときは、第２記憶部２２０に読み出されて使われる。Ｋ２Ｐテーブルの内容は、第２書き込み制御部２１２による第２書き込み制御が行われるたびに更新される。

次に、検索制御部２１３の機能を説明する。受付部２１１で検索要求を受け付けた場合、検索制御部２１３は、検索要求に含まれるキーを、ハッシュ化して、固定長のデータから構成されるキーアドレスに変換する。そして、Ｋ２Ｐテーブルを参照して、そのキーアドレスに対応付けられた物理アドレスを特定し（Ｋ２Ｐ変換を行い）、特定した物理アドレスが示す位置に格納された情報を読み出す制御（以下、「第１の検索制御」と呼ぶ場合がある）を行う。本実施形態では、検索制御部２１３は、メモリコントローラ２５０に対して検索の実行を命令する検索コマンドを生成し、その生成した検索コマンドに対して、上述のＫ２Ｐ変換により得た物理アドレスを付加してメモリコントローラ２５０へ伝達する。そして、検索制御部２１３は、検索コマンドに対する応答として、メモリコントローラ２５０が第１記憶部１２０から読み出した情報を受け取ることができる。

また、例えばホスト装置２００から、複数の検索要求とともに集合演算条件を受け付けていた場合、検索制御部２１３は、検索要求の各々に含まれるキーを変換して得たキーアドレスを用いて第１記憶部１２０から読み出した情報に含まれるデータの集合に対して、受け付けた集合演算条件に従った集合演算を行い、検索結果を絞り込むこともできる。なお、例えばこの集合演算を行う機能が、デバイスコントローラ２１０ではなくてメモリコントローラ２５０に搭載される形態であってもよい。

検索制御部２１３は、第１の検索制御により読み出された情報の中に、第２書き込み制御部２１２によってデータに付加されたキーアドレスが含まれていた場合は、Ｋ２Ｐテーブルを参照して、第２書き込み制御部２１２によってデータに付加されたキーアドレスに対応する物理アドレスを特定する。本実施形態では、検索制御部２１３は、第１の検索制御により読み出された情報に含まれるオフセットを参照して、データ長が閾値未満であると判断した場合、その第１の検索制御により読み出された情報のうち、データと冗長部以外の部分から、書き込み時にデータに付加されたキーアドレスを取得する。そして、検索制御部２１３は、Ｋ２Ｐテーブルを参照して、取得したキーアドレスに対応する物理アドレスを特定する。

検索制御部２１３は、第１記憶部１２０のうち、以上のようにして特定した物理アドレスが示す位置に格納された情報を読み出す制御（以下、「第２の検索制御」と呼ぶ場合がある）を行う。本実施形態では、検索制御部２１３は、メモリコントローラ２５０に対して検索の実行を命令する検索コマンドを生成し、生成した検索コマンドに対して、以上のようにして特定した物理アドレスを付加してメモリコントローラ２５０へ伝達する。検索制御部２１３は、検索コマンドに対する応答として、メモリコントローラ２５０が第１記憶部１２０から読み出した情報を受け取ることができる。そして、検索制御部２１３は、以上の第２の検索制御により読み出した情報に含まれるデータとキーアドレスとを対応付けて第２記憶部２２０に記憶させる制御を行う。

したがって、第２の検索制御が行われるたびに、第２記憶部２２０には、第２の検索制御に用いられたキーアドレスと、データとが対応付けられた検索キャッシュデータが記憶されていく。

検索制御部２１３は、受付部２１１で受け付けた検索要求に含まれるキーを変換して得たキーアドレスと一致するキーアドレスを含む検索キャッシュデータが第２記憶部２２０に存在する場合は、検索要求に含まれるキーを変換して得たキーアドレスを含む検索キャッシュデータに含まれるデータを読み出す制御を行う。この場合、検索制御部２１３は、第１記憶部１２０からデータを読み出す制御を行う必要が無いので、読み出し速度の向上が図られる。

また、検索制御部２１３は、第１の検索制御を行うたびに、少なくとも、その第１の検索制御に用いたキーアドレスを第２記憶部２２０に記憶させる制御を行う。

さらに、検索制御部２１３は、第１の検索制御または第２の検索制御に用いたキーアドレスを第２記憶部２２０に記憶させる場合、第１記憶部１２０からの情報の読み出しが行われた時間（時刻）を示す時間情報を対応付けて記憶させる。したがって、第２記憶部２２０は、第１の検索制御または第２の検索制御に用いられたキーアドレスごとに、読み出しが行われた時間を示す時間情報を対応付けて記憶する。第２記憶部２２０のより詳細な内容については後述する。

ここで、前述の書き込み制御部２１２は、書き込み対象バリューデータのサイズが閾値未満の場合は、第２記憶部２２０に記憶されたキーアドレスの中から、書き込み対象バリューデータの書き込みが要求されたときよりも前の所定期間内における検索に用いられたキーアドレスを選択して書き込み対象バリューデータに付加する。

さらに詳述すれば、以下のとおりである。図１０は、第２記憶部２２０の構成例を示す図であり、検索機能に関する部分のみを例示している。図１０に示すように、第２記憶部２２０は、第５記憶部２３０と第６記憶部２４０とを備える。第５記憶部２３０は、第１の検索制御に用いられたキーアドレスごとに、第１の検索制御による読み出しが行われた時間を示す時間情報を対応付けて記憶する。第６記憶部２４０は、第２の検索制御に用いられたキーアドレスごとに、第２の検索制御により読み出されたデータと、第２の検索制御による読み出しが行われた時間を示す時間情報とを対応付けて記憶する。そして、書き込み制御部２１２は、書き込み対象バリューデータのサイズが閾値未満の場合は、第５記憶部２３０および第６記憶部２４０の各々に記憶されたキーアドレスの中から、所定期間内に含まれる時間を示す時間情報に対応するキーアドレスを選択してデータに付加する。なお、これに限らず、例えば先読みの検索キャッシュデータに含まれるキーアドレス（第６記憶部２４０に記憶されたキーアドレス）は、閾値未満のサイズの書き込み対象バリューデータに付加されない形態であってもよい。

次に、図１１を参照しながら、第２書き込み制御部２１２による制御の一例を説明する。図１１は、第２書き込み制御部２１２による制御の一例を示すフローチャートである。この例では、ホスト装置２００からのキーバリュー書き込み要求を受付部２１１で受け付けたことを前提として説明する。図１１に示すように、第２書き込み制御部２１２は、受付部２１１で受け付けたキーバリュー書き込み要求に含まれるデータ（書き込み対象バリューデータ）のサイズが閾値未満であるか否かを確認する（ステップＳ３０）。この例では、第２書き込み込み制御部２１２は、書き込み対象バリューデータのページ充当率が５０％未満であるか否かを確認する。書き込み対象バリューデータのサイズが閾値以上であると判断した場合（ステップＳ３０：ＮＯ）、処理は、後述のステップＳ３５に移行する。

上述のステップＳ３０において、書き込み対象バリューデータのサイズが閾値未満であると判断した場合（ステップＳ３０：ＹＥＳ）、第２書き込み制御部２１２は、空き領域のサイズを算出する（ステップＳ３１）。次に、第２書き込み制御部２１２は、算出した空き領域のサイズが閾値以上であるか否かを確認する（ステップＳ３２）。この閾値は、空き領域のサイズが、少なくとも１つのキーアドレスのサイズ以上であるか否かを判定可能な値に設定される。算出した空き領域のサイズが閾値未満であると判断した場合（ステップＳ３２：ＮＯ）、処理は、後述のステップＳ３５に移行する。

一方、算出した空き領域のサイズが閾値以上であると判断した場合（ステップＳ３２：ＹＥＳ）、第２書き込み制御部２１２は、第２記憶部２２０に記憶されたキーアドレスの中から、所定期間内に含まれる時間を示す時間情報に対応するキーアドレスを取得（選択）する（ステップＳ３３）。

次に、第２書き込み制御部２１２は、ステップＳ３３で選択した１以上のキーアドレスを、書き込み対象バリューデータに付加する（ステップＳ３４）。次に、第２書き込み制御部２１２は、受付部２１１で受け付けたキーバリュー書き込み要求に含まれるキーを変換して得たキーアドレスと、書き込み対象バリューデータのデータ長を特定可能なオフセットとを冗長部に追記する（ステップＳ３５）。次に、第２書き込み制御部２１２は、メモリコントローラ２５０に対する書き込みの実行を命令する書き込みコマンドを生成し、生成した書き込みコマンドに対して、第２書き込み制御の対象となる情報と、第１記憶部１２０のうち書き込み対象バリューデータを書き込む位置を示す物理アドレスとを付加してメモリコントローラ２５０へ送信する（ステップＳ３６）。そして、第２書き込み制御部２１２からの書き込みコマンドを受信したメモリコントローラ２５０は、受信した書き込みコマンドに従って、第１記憶部１２０に対する情報の書き込みを行う。

次に、第２書き込み制御部２１２は、Ｋ２Ｐテーブルを更新する（ステップＳ３７）。上述したように、第２実施形態では、第２書き込み制御部２１２は、受付部２１１で受け付けたキーバリュー書き込み要求に含まれるキーを変換して得たキーアドレスと、第１記憶部１２０のうち書き込み対象バリューデータを書き込む位置を示す物理アドレスとを対応付けて、新たにＫ２Ｐテーブルに追加する制御を行う。

次に、図１２を参照しながら、検索制御部２１３による制御の一例を説明する。図１２は、検索制御部２１３による制御の一例を示すフローチャートである。この例では、ホスト装置２００から、複数の検索要求とともに、検索結果を絞り込むための集合演算条件を受け付けたことを前提として説明する。図１２に示すように、まず、検索制御部２１３は、検索要求に含まれるキーを変換して得たキーアドレスを含む検索キャッシュデータが第２記憶部２２０（第６記憶部２４０）に記憶されているか否かを確認する（ステップＳ４０）。

上述のステップＳ４０において、検索要求に含まれるキーを変換して得たキーアドレスを含む検索キャッシュデータが第２記憶部２２０に記憶されていると判断した場合（ステップＳ４０：ＹＥＳ）、検索制御部２１３は、その検索キャッシュデータに含まれるデータを第２記憶部２２０から読み出す。ここで、受付部２１１で集合演算条件を受け付けていない場合（つまり、単発の検索要求の場合）、検索制御部２１３は、第２記憶部２２０から読み出したデータを、検索要求に対する応答としてホスト装置２００へ送信して処理を終了する。ただし、この例では、複数の検索要求とともに集合演算条件を受付部２１１で受け付けていることを前提とするので、処理は、後述のステップＳ４５に移行する。

一方、上述のステップＳ４０において、検索要求に含まれるキーを変換して得たキーアドレスを含む検索キャッシュデータが第２記憶部２２０に記憶されていないと判断した場合（ステップＳ４０：ＮＯ）、処理は、ステップＳ４１に移行する。ステップＳ４１において、検索制御部２１３は、Ｋ２Ｐテーブルを参照して、検索要求に含まれるキーを変換して得たキーアドレスに対応する物理アドレスを特定する（ステップＳ４１）。次に、検索制御部２１３は、メモリコントローラ２５０に対して検索の実行を命令する検索コマンドを生成し、生成した検索コマンドに対して、ステップＳ４１で特定した物理アドレスを付加してメモリコントローラ２５０へ送信する（ステップＳ４２）。検索コマンドを受信したメモリコントローラ２５０は、受信した検索コマンドに従って、第１記憶部１２０から情報を読み出し、読み出した情報を検索制御部２１３へ送信する。つまり、検索制御部２１３は、検索コマンドに対する応答として、メモリコントローラ２５０により読み出された情報を受信する（ステップＳ４３）。

以上のステップＳ４１〜ステップＳ４３の内容が、第１の検索制御に相当する。次に、検索制御部２１３は、第１の検索制御により読み出した情報に含まれるオフセットを参照して、データ長が閾値未満であるか否かを確認する（ステップＳ４４）。仮に、受付部２１１で集合演算条件を受け付けていなければ（単発の検索要求であれば）、検索制御部２１３は、データ長が閾値以上であると判断した場合（ステップＳ４４：ＮＯ）、第１の検索制御により読み出した情報に含まれるデータを、検索要求に対する応答としてホスト装置２００へ送信して処理を終了する。ただし、この例では、複数の検索要求とともに集合演算条件を受付部２１１で受け付けていることを前提とするので、処理は、ステップＳ４５に移行する。ステップＳ４５において、検索制御部２１３は、複数の検索要求の各々に含まれるキーを変換して得たキーアドレスを用いて読み出された情報に含まれるデータの集合に対して、受け付けた集合演算条件に従った集合演算を行い、検索結果を絞り込む。そして、集合演算によって絞り込まれた検索結果を、検索要求に対する応答としてホスト装置２００へ送信し（ステップＳ４６）、処理を終了する。

一方、上述のステップＳ４４において、データ長が閾値未満であると判断した場合（ステップＳ４４：ＹＥＳ）、検索制御部２１３は、第１の検索制御により読み出した情報のうち、データと冗長部以外の部分から、書き込み時にデータに付加されたキーアドレスを取得する（ステップＳ４７）。また、本実施形態では、ステップＳ４７の処理と並行して、検索制御部２１３は、第１の検索制御により読み出した情報に含まれる、閾値未満のサイズのデータを用いて、上述のステップＳ４５の処理（集合演算処理）を行うこともできる。なお、例えば受付部２１１で集合演算条件を受け付けていなければ（単発の検索要求であれば）、検索制御部２１３は、第１の検索制御により読み出した情報に含まれる、閾値未満のサイズのデータを、検索要求に対する応答としてホスト装置２００へ送信して処理を終了する。

次に、検索制御部２１３は、Ｋ２Ｐテーブルを参照して、ステップＳ４７で取得した１以上のキーアドレスごとに、キーアドレスに対応する物理アドレスを特定する（ステップＳ４８）。次に、検索制御部２１３は、メモリコントローラ２５０に対して検索の実行を命令する検索コマンドを生成し、生成した検索コマンドに対して、ステップＳ４８で特定した物理アドレスを付加してメモリコントローラ２５０へ送信する（ステップＳ４９）。検索コマンドを受信したメモリコントローラ２５０は、受信した検索コマンドに従って、第１記憶部１２０から情報を読み出し、読み出した情報を検索制御部２１３へ送信する。つまり、検索制御部２１３は、検索コマンドに対する応答として、メモリコントローラ２５０により読み出された情報を受信する（ステップＳ５０）。

以上のステップＳ４７〜ステップＳ５０の内容が、第２の検索制御に相当する。ステップＳ５０の後、検索制御部２１３は、メモリコントローラ２５０から受信した情報（第２の検索制御により読み出した情報）に含まれるデータと、キーアドレスとを対応付けて第２記憶部２２０（第６記憶部２４０）に記憶させる制御を行う（ステップＳ５１）。これにより、第６記憶部２４０には、先読みの検索キャッシュデータが新たに追加されることになる。

以上、本発明の実施形態を説明したが、上述の各実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。なお、上述の各実施形態および変形例は任意に組み合わせることもできる。

また、上述の各実施形態のデバイスコントローラ（１１２、２１０）が実行するプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するようにしてもよい。また、上述の各実施形態のデバイスコントローラ（１１２、２１０）が実行するプログラムを、インターネット等のネットワーク経由で提供または配布するようにしてもよい。また、各実施形態のデバイスコントローラ（１１２、２１０）が実行するプログラムを、ＲＯＭ等の不揮発性の記録媒体に予め組み込んで提供するようにしてもよい。

１００ デバイス
１０１ 受付部
１０２ 書き込み制御部
１０３ 読み出し制御部
１０４ コマンド受信部
１０５ 訂正部
１０６ 書き込み部
１０７ 読み出し部
１１０ コントローラチップ
１１１ ホストインタフェース部
１１２ デバイスコントローラ
１１３ 第２記憶部
１１４ メモリコントローラ
１２０ 第１記憶部
１３０ 第３記憶部
１４０ 第４記憶部
１５０ バッファメモリ
２００ ホスト装置
２１０ デバイスコントローラ
２１１ 受付部
２１２ 第２書き込み制御部
２１３ 検索制御部
２２０ 第２記憶部
２３０ 第５記憶部
２４０ 第６記憶部
２５０ メモリコントローラ
３００ 外部バス

Claims (11)

1. ホスト装置から供給されるデータを記憶する第１記憶部と、
   前記第１記憶部からの前記データの読み出しに用いられた論理アドレスを記憶する第２記憶部と、
   前記ホスト装置から前記第１記憶部に対する書き込みが要求された前記データのサイズが閾値未満の場合は、前記第２記憶部に記憶された前記論理アドレスを前記データに付加して、前記第１記憶部に書き込む制御を行う書き込み制御部と、を備える、
   半導体記憶装置。
2. 前記ホスト装置からの、前記第１記憶部に対する前記データの読み出しを要求する読み出し要求を受け付ける受付部と、
   前記受付部で前記読み出し要求を受け付けた場合、前記第１記憶部内の位置を示す物理アドレスと、前記論理アドレスとの対応関係を示す論物変換情報を参照して、前記読み出し要求に含まれる前記論理アドレスに対応する前記物理アドレスを特定し、特定した前記物理アドレスが示す位置に格納された、前記データを含む情報を読み出す第１の読み出し制御を行う読み出し制御部と、を備える、
   請求項１に記載の半導体記憶装置。
3. 前記読み出し制御部は、前記第１の読み出し制御により読み出した前記情報の中に、前記書き込み制御部によって前記データに付加された前記論理アドレスが含まれていた場合は、前記データに付加された前記論理アドレスに対応する前記物理アドレスが示す位置に格納された前記情報を読み出す第２の読み出し制御を行い、前記第２の読み出し制御により読み出した前記情報に含まれる前記データと、前記論理アドレスとを対応付けて前記第２記憶部に記憶させる制御を行う、
   請求項２に記載の半導体記憶装置。
4. 前記読み出し制御部は、前記受付部で受け付けた前記読み出し要求に含まれる前記論理アドレスと一致する前記論理アドレスと、前記データとが対応付けられて前記第２記憶部に記憶されている場合は、前記読み出し要求に含まれる前記論理アドレスと一致する前記論理アドレスに対応付けられた前記データを前記第２記憶部から読み出す第３の読み出し制御を行う、
   請求項３に記載の半導体記憶装置。
5. 前記読み出し制御部は、前記第１の読み出し制御を行うたびに、少なくとも、前記第１の読み出し制御に用いた前記論理アドレスを前記第２記憶部に記憶させる制御を行う、
   請求項２ないし請求項４に記載の半導体記憶装置。
6. 前記書き込み制御部は、書き込みが要求された前記データのサイズが前記閾値未満の場合は、前記第２記憶部に記憶された前記論理アドレスの中から、前記書き込みが要求されたときよりも前の所定期間内における読み出しに用いられた前記論理アドレスを選択して前記データに付加する、
   請求項３に記載の半導体記憶装置。
7. 前記第２記憶部は、前記論理アドレスごとに、前記第１記憶部からの前記情報の読み出しが行われた時間を示す時間情報を対応付けて記憶し、
   前記書き込み制御部は、書き込みが要求された前記データのサイズが前記閾値未満の場合は、前記第２記憶部に記憶された前記論理アドレスの中から、前記所定期間内に含まれる時間を示す前記時間情報に対応する前記論理アドレスを選択して前記データに付加する、
   請求項６に記載の半導体記憶装置。
8. 前記第２記憶部は、
   前記第１の読み出し制御に用いられた前記論理アドレスと、前記第１の読み出し制御による読み出しが行われた時間を示す前記時間情報とを対応付けて記憶する第３記憶部と、
   前記第２の読み出し制御に用いられた前記論理アドレスと、前記第２の読み出し制御により読み出された前記データと、前記第２の読み出し制御による読み出しが行われた時間を示す前記時間情報とを対応付けて記憶する第４記憶部と、を有し、
   前記書き込み制御部は、書き込みが要求された前記データのサイズが前記閾値未満の場合は、前記第３記憶部および前記第４記憶部に記憶された前記論理アドレスの中から、前記所定期間内に含まれる時間を示す前記時間情報に対応する前記論理アドレスを選択して前記データに付加する、
   請求項７に記載の半導体記憶装置。
9. 前記第２記憶部は、
   前記第１の読み出し制御に用いられた前記論理アドレスと、前記第１の読み出し制御による読み出しが行われた時間を示す前記時間情報とを対応付けて記憶する第３記憶部と、
   前記第２の読み出し制御に用いられた前記論理アドレスと、前記第２の読み出し制御により読み出された前記データとを対応付けて記憶する第４記憶部と、を有し、
   前記書き込み制御部は、書き込みが要求された前記データのサイズが前記閾値未満の場合は、前記第３記憶部に記憶された前記論理アドレスの中から、前記所定期間内に含まれる時間を示す前記時間情報に対応する前記論理アドレスを選択して前記データに付加する、
   請求項７に記載の半導体記憶装置。
10. 前記第３記憶部は、ＦＩＦＯ方式のメモリである、
    請求項８または請求項９に記載の半導体記憶装置。
11. ホスト装置から供給されるデータを記憶する第１記憶部と、
    前記第１記憶部に記憶された前記データの中から、前記ホスト装置から指定されたキーに対応する前記データを検索するのに用いられたキーアドレスを記憶する第２記憶部と、
    前記ホスト装置から前記第１記憶部に対する書き込みが要求された前記データのサイズが閾値未満の場合は、前記第２記憶部に記憶された前記キーアドレスを前記データに付加して、前記第１記憶部に書き込む制御を行う書き込み制御部と、を備える、
    半導体記憶装置。

Images