JP7237782B2 - ストレージシステム及びその制御方法 - Google Patents

Description

本実施形態は、ストレージシステム及びその制御方法に関する。

データベースの構築に利用されるデータ管理方式の一例として、ＫＶＳ（Key Value Store）方式が知られている。

特開２０１７－１８２２６７号公報

本実施形態は、不揮発性メモリに記憶されているデータの中から所望のデータを高速に検索可能とすることを目的とする。

本実施形態によれば、ストレージシステムは、プロセッサと、ストレージデバイスと、第１のメモリとを含む。ストレージデバイスは、プロセッサから受信した検索キーに基づいて、検索キーに対応するバリューを検索する。第１のメモリは、バリューを含むデータの位置情報を検索するために用いられる検索情報を記憶する。ストレージデバイスは、データを記憶する不揮発性メモリと、不揮発性メモリを制御するコントロール回路と、コントロール回路により不揮発性メモリより高速にアクセス可能な第２のメモリとを含む。プロセッサは、検索キーと検索情報とに基づいて、位置情報を検索し、位置情報と検索キーとをコントロール回路へ送信し、コントロール回路は、位置情報と検索キーとに基づいて、不揮発性メモリからデータの少なくとも一部をリードし、データの少なくとも一部を第２のメモリに記憶させ、データの少なくとも一部の中から検索キーに対応するバリューを検索し、バリューをプロセッサへ送信する。

第１の実施形態に係るストレージシステムの一例を示すブロック図。 第１の実施形態に係るストレージシステムで管理される木構造を持つデータの一例を示すデータ構造図。 第１の実施形態に係るストレージシステムの起動時の処理の一例を示すフローチャート。 第１の実施形態に係るストレージシステムによって実行されるキーバリュー検索処理の一例を示すフローチャート。 第１の実施形態に係る不揮発性メモリの構成の一例を示すブロック図。 第１の実施形態に係るページデータのデータ構造におけるノードとノード番号との関係の表現例を示す図。 第１の実施形態に係るページデータのデータ構造におけるノードとバリューとの関係の表現例を示す図。 第１の実施形態に係るページデータのデータ構造における親子の関係を持つノードの表現例を示す図。 第１の実施形態に係るページデータのデータ構造における兄弟の関係を持つノードの表現例を示す図。 第１の実施形態に係るページデータの一例をグラフで表現したデータ構造図。 第１の実施形態に係るページ内検索回路の処理の一例を示すフローチャート。 第２の実施形態に係るストレージシステムの一例を示すブロック図。 第２の実施形態に係るコントローラ回路と不揮発性メモリとにより実行される処理の一例を示すフローチャート。 第２の実施形態に係る部分ページリード回路及び部分ページ内検索回路の処理の一例を示すフローチャート。

まず、本実施形態の概要を説明する。
本実施形態に係るストレージシステムは、プロセッサと、メモリと、少なくとも１つのストレージデバイスとを備える。

プロセッサは、メモリに対してストレージデバイスよりも高速にアクセス可能である。

ストレージデバイスは、ＫＶＳ方式ストレージシステムであり、コントロール回路と、不揮発性メモリと、バッファメモリとを備える。

ストレージシステムは、データを不揮発性メモリとメモリとに分散配置する。具体的には、ストレージシステムは、各種のキーとバリューとのペアを含むデータを不揮発性メモリに記憶させる。さらに、ストレージシステムは、検索対象のキー（以下、検索キーと称する）と当該検索キーに対応するバリューとのペアを含むデータの位置情報を検索するために用いられる検索情報をメモリに記憶させる。

プロセッサは、検索キーとメモリに記憶されている検索情報とに基づいて、不揮発性メモリにおける検索キーとバリューとのペアを含むデータの位置情報を検索する。

コントロール回路は、プロセッサによって検索された位置情報に基づいて、不揮発性メモリから検索キーとバリューとのペアを含むデータの少なくとも一部をリードし、データの少なくとも一部をバッファメモリに記憶させる。

そして、コントロール回路は、バッファメモリに記憶されているデータの少なくとも一部の中から検索キーに対応するバリューを検索し、検索されたバリューに対して各種の処理を実行し、バリューをプロセッサへ送信する。

このように、本実施形態に係るストレージシステムは、検索キーに対応するバリューを検索するための処理をプロセッサとコントロール回路とに分散させることで、高速なデータ検索を実現し、高ＩＯＰＳ（Input/Output Per Second）を実現する。

本実施形態に係るストレージシステムに備えられるストレージデバイスは、例えばＳＳＤ（Solid State Drive）などのメモリシステムであるとする。しかしながら、本実施形態に係るストレージシステムと同様の機能は、例えばＨＤＤ（Hard Disk Drive）、ＵＳＢ（Universal Serial Bus）メモリ、メモリカード、ハードディスクドライブとＳＳＤとを含むハイブリッド型ストレージシステム、光ディスクデバイスなど様々な種類のストレージデバイスに適用可能である。

本実施形態において、ストレージシステムは、ＫＶＳ方式ストレージシステムである場合を例として説明する。しかしながら、例えば、保存したいデータに対して、当該データに対応する一意の標識を設定し、この保存したいデータと標識とをペアで記憶する他の様々なデータベースシステムに対して、本実施形態に係るストレージシステムと同様の構成及び機能を適用可能である。

以下、図面を参照して、本実施形態について具体的に説明する。なお、以下の説明において、実質的に同一の構成要素及び機能については、同一符号を付し、必要に応じて説明を行う。以下の説明において、例として挙げる数値は好ましい数値であり、本実施形態はこれらの数値に制限されない。

（第１の実施形態）
図１は、第１の実施形態に係るストレージシステム１の一例を示すブロック図である。

ストレージシステム１は、例えば、リレーショナルデータベースシステムである。ストレージシステム１は、インタフェース部２と、プロセッサ３と、メモリ４と、データ転送バス５と、ストレージデバイスＳＤ１～ＳＤｋとを備える。ストレージシステム１が備えるストレージデバイスの数は、１以上であればよい。

ストレージデバイスＳＤ１は、インタフェース回路６と、コントロール回路７と、伝送路８と、バッファメモリ９と、不揮発性メモリ１０とを備える。

インタフェース部２は、キーバリュー検索時に、例えばクライアント１００などの外部装置から検索キーを含むリードリクエストを受信し、受信したリードリクエストをプロセッサ３へ送信する。

プロセッサ３は、例えばＣＰＵ（Centrol Prosessing Unit）であるが、例えばマイクロプロセッサなどでもよい。プロセッサ３は、複数のストレージデバイスＳＤ１～ＳＤｋを制御するコントローラとしてもよい。

プロセッサ３は、ストレージシステム１の起動時に、不揮発性メモリ１０から、伝送路８、コントロール回路７、インタフェース回路６、データ転送バス５経由で、ＫＶＳにしたがって管理される木構造のデータＤ中のルートノード及びブランチノード（すなわち、非リーフノード）をリードし、ルートノード及びブランチノードを含みリーフノードを含まない検索情報１１をメモリ４に記憶させる。ＫＶＳの木構造のデータＤに関しては図２を用いて後で説明する。

メモリ４は、プロセッサ３がストレージデバイスＳＤ１よりも高速にアクセス可能なメモリであり、例えばＤＲＡＭ（Dynamic Rondom Access Memory）又はＳＲＡＭ（Static Rondom Access Memory）などであり、例えばメインメモリとして使用される。

プロセッサ３は、キーバリュー検索時に、クライアント１００からインタフェース部２経由で受信したリードリクエストに基づいてメモリ４の検索情報１１を参照し、リードリクエストに含まれている検索キーと検索情報１１とに基づいて、検索キーに対応するバリューを記憶しているページ（すなわち、リーフノード）の位置情報を検索する。そして、プロセッサ３は、検索されたページの位置情報と検索キーとを含むリードリクエストを、データ転送バス５経由でストレージデバイスＳＤ１へ送信する。

プロセッサ３は、キーバリュー検索の結果であるバリュー（検索キーに対応するデータ）を一時記憶するため内部メモリ１２を備える。内部メモリ１２は、例えばＤＲＡＭ又はＳＲＡＭなどでもよい。

プロセッサ３内に備えられる内部メモリ１２は、例えば、プロセッサ３によりメインメモリとして利用されるメモリ４よりも高速にアクセス可能であり、低遅延であるとする。内部メモリ１２は、例えば、メモリ４よりも広帯域の周波数で使用可能とする。
なお、メモリ４と内部メモリ１２とは、１つのメモリに統合されてもよい。

プロセッサ３は、送信したリードリクエストの応答でありストレージデバイスＳＤ１からデータ転送バス５経由で受信したバリューを、内部メモリ１２に記憶させる。より具体的には、ストレージデバイスＳＤ１に備えられているデータ転送回路１７が、ストレージデバイスＳＤ１に備えられているバッファメモリ９に記憶されているバリューをプロセッサ３に備えられている内部メモリ１２へ転送する。

プロセッサ３の内部バス（図示せず）とデータ転送バス５との間の帯域幅は、データ転送バス５の帯域幅より広いとしてもよい。プロセッサ３の内部バスとデータ転送バス５との間のデータ転送速度は、例えば４０ギガバイト／秒程度としてもよい。

第１の実施形態において、データ転送バス５におけるデータ転送で使用される帯域幅は、コントロール回路７と不揮発性メモリ１０との間の伝送路８におけるデータ転送で使用される帯域幅よりも狭い。データ転送バス５の帯域幅と伝送路８の帯域幅との比は、例えば１：８から１：８００までのいずれかであるとし、例えば１：５００程度であるとしてもよい。

ストレージデバイスＳＤ１のインタフェース回路６は、プロセッサ３からデータ転送バス５経由で受信したリードリクエストを、コントロール回路７へ送信する。

コントロール回路７は、ストレージサブシステムであり、ページリード回路１３と、ページ内検索回路１４と、エラー訂正回路１５と、伸長回路１６と、データ転送回路１７とを備える。コントロール回路７は、例えば、ＦＰＧＡ（Field Programmable Gate Array）でもよい。コントロール回路７におけるページリード回路１３と、ページ内検索回路１４と、エラー訂正回路１５と、伸長回路１６と、データ転送回路１７とのうちの少なくとも１つの機能は、例えばファームウェアなどのソフトウェアを例えばプロセッサとして動作するコントロール回路７により実行することで実現してもよい。

ページリード回路１３は、インタフェース回路６によって受信されたリードリクエストに含まれているページの位置情報に基づいて、不揮発性メモリ１０の当該位置情報の示す位置に記憶されているページ単位のデータ（以下、ページデータと称する）に対するリードコマンドを、不揮発性メモリ１０へ送信し、リードコマンドに応じて不揮発性メモリ１０からリードされたページデータＰ１をバッファメモリ９に記憶させる。第１の実施形態において、ページサイズは、例えば３．５～４．５キロバイトの間であり、例えばおよそ４キロバイト程度もしくはそれ以上としてもよい。

ページ内検索回路１４は、バッファメモリ９に記憶されているページデータＰ１の中から検索キーに対応するバリューを検索する。ここで、検索キーに対応するバリューは、リードされたページデータＰ１の一部分であるとする。このページ内検索回路１４によってページデータＰ１内のバリューを検索する具体的な処理は、図６乃至図１１を用いて後で説明する。

エラー訂正回路１５は、ページ内検索回路１４によって検索されたバリューに対してエラー訂正処理を実行し、エラー訂正されたバリューをバッファメモリ９に記憶させる。なお、エラー訂正回路１５は、ページデータＰ１の一部でありページ内検索回路１４によって検索されたバリューを含む部分データに対してエラー訂正処理を実行し、エラー訂正されたバリューを含む部分データをバッファメモリ９に記憶させるとしてもよい。

伸長回路１６は、ページ内検索回路１４によって検索され圧縮されているバリューを伸長し、伸長されたバリューをバッファメモリ９に記憶させる。なお、ページデータＰ１は、圧縮されている部分と圧縮されていない部分とを含むとしてもよく、この場合、伸長回路１６は、圧縮されている部分に対して伸長を行い、圧縮されていない部分に対しては伸長を行わない。また、伸長回路１６は、ページデータＰ１の一部でありページ内検索回路１４によって検索された圧縮されているバリューを含む部分データを伸長し、伸長されたバリューを含む部分データをバッファメモリ９に記憶させるとしてもよい。

エラー訂正回路１５及び伸長回路１６は、バッファメモリ９を作業用メモリとして用いてバリューに対する処理を実行してもよい。

データ転送回路１７は、リードリクエストの応答でありバッファメモリ９に記憶されているエラー訂正及び伸長されたバリューを、インタフェース回路６及びデータ転送バス５経由でプロセッサ３の内部メモリ１２へ転送する。なお、データ転送回路１７は、バッファメモリ９に記憶されている複数のバリューをまとめてプロセッサ３の内部メモリ１２へ転送してもよい。これにより、ストレージデバイスＳＤ１とプロセッサ３との間のデータ転送回数を削減することができ、ストレージデバイスＳＤ１とプロセッサ３との間で所定のサイズのデータを効率的に転送させることができる。

データ転送回路１７は、例えばＤＭＡ（Direct Memory Access）転送を実現するＤＭＡＣ（Direct Memory Access Controller）としてもよい。第１の実施形態において、データ転送回路１７によってバッファメモリ９からインタフェース回路６及びデータ転送バス５経由で内部メモリ１２へ転送されるデータのサイズは、例えば、ページデータＰ１より小さい５１２バイトに削減されるとする。また、データ転送回路１７の性能は、例えば４メガＩＯＰＳであるとする。

伝送路８は、コントロール回路７と不揮発性メモリ１０との間をデータ転送可能に接続する。

バッファメモリ９は、例えば、コントロール回路７が不揮発性メモリ１０よりも高速にアクセス可能なメモリであり、例えばＤＲＡＭ、ＳＲＡＭ、ラッチ回路、又は、レジスタなどで構成されてもよい。バッファメモリ９は、リードリクエストに応じて不揮発性メモリ１０からリードされたページデータＰ１を一時的に記憶する。バッファメモリ９は、上記のように、バリューに対する各種処理の作業用メモリとして使用され得る。

不揮発性メモリ１０は、ルートノードと、ブランチノードと、リーフノードとを含むデータＤを記憶する。不揮発性メモリ１０に記憶されているルートノード及びブランチノードは、検索情報１１として、ストレージシステム１の起動時に、例えば、伝送路８、コントロール回路７、インタフェース回路６、データ転送バス５、プロセッサ３経由で、メモリ４にキャッシュされてもよい。具体的には、不揮発性メモリ１０に記憶されているルートノード及びブランチノードは、ストレージシステム１の起動時に、例えば、一旦バッファメモリ９に記憶され、このバッファメモリ９からデータ転送回路１７により、インタフェース回路６、データ転送バス５経由で内部メモリ１２へ転送されてもよい。

不揮発性メモリ１０は、例えばＮＡＮＤ型フラッシュメモリとするが、ＮＯＲ型フラッシュメモリ、ＭＲＡＭ（Magnetoresistive Random Access Memory：磁気抵抗メモリ）、ＰＲＡＭ（Phasechange Random Access Memory：相変化メモリ）、ＲｅＲＡＭ（Resistive Random Access Memory：抵抗変化型メモリ）、ＦｅＲＡＭ（Ferroelectric Random Access Memory）など他の不揮発性半導体メモリでもよい。不揮発性メモリ１０は、１以上のメモリチップを含むとしてもよい。例えば、不揮発性メモリ１０は、磁気メモリ、３次元構造の半導体メモリなどでもよい。また、不揮発性メモリ１０に代えて、あるいは不揮発性メモリ１０とともに、磁気ディスク、光ディスク、その他の記録媒体が用いられてもよい。

不揮発性メモリ１０に対するデータのリード及びライトは、ページと呼ばれる単位で実行され得る。不揮発性メモリ１０に対するデータのイレーズは、ブロックと呼ばれる単位で実行され得る。ブロックの１単位は、複数のページを含む。不揮発性メモリ１０に対するデータのリード及びライトが複数のページ単位で、イレーズが複数のブロック単位で、それぞれ実行されてもよい。

第１の実施形態において、不揮発性メモリ１０は、例えば、４～８メガＩＯＰＳ、３２ギガバイト／秒の性能を持ち、高ＩＯＰＳであるとしてもよい。

図２は、第１の実施形態に係るストレージシステム１で管理される木構造を持つデータＤの一例を示すデータ構造図である。

この図２のデータＤでは、キーと、ページ番号と、バリューとがＢ＋木構造により管理されている。キーはＫ、ページ番号はＰ、バリューはＶと表現されている。しかしながら、Ｂ＋木構造に代えて、例えばＢ木構造、２分木構造、多分木構造などのような他のデータ構造が適用されてもよい。

データＤは、ルートノードＮ０と、ルートノードＮ０より下層の複数のブランチノードＮ１～Ｎ６と、複数のブランチノードＮ１～Ｎ６より下層の複数のリーフノードＮ７～Ｎ９とを含む木構造を持つ。木構造は、複数の階層を持つ。図２の１つのノードは、ページデータに相当し、例えば、およそ４キロバイトのサイズとしてもよい。ページデータは、所定の範囲ごとにエラー訂正コードを含み、エラー訂正回路１５は、ページデータ内の所定の範囲ごとにエラー訂正可能とする。

データＤにおいて、複数のキーはソートされており、同じページデータ内には、類似のキーが配置される。なお、第１の実施形態において、類似のキーとは、複数のキーの間で先頭部分の文字が共通することを意味している。複数のキーをソートした場合に、類似のキーは近い順番に位置する。

ルートノードＮ０は、複数の階層のうちの最上層のノードであり、親ノードを持たず、子ノードを持つ。

リーフノードＮ７～Ｎ９は、複数の階層のうちの最下層のノードであり、子ノードを持たず、親ノードを持つ。

第１の実施形態において、データＤは、ルートノードＮ０とリーフノードＮ７～Ｎ９との間に、１階層以上のブランチノードＮ１～Ｎ６を含む。

なお、ルートノードとリーフノードとの間のブランチノードは省略されてもよい。この場合、ルートノードの子ノードがリーフノードとなり、リーフノードの親ノードがルートノードとなる。

ルートノードＮ０は、キーとページ番号とのペアを複数含む。ルートノードＮ０に含まれている各ページ番号は、ルートノードＮ０の子ノードであるブランチノードＮ１～Ｎ３のページ位置を示す位置情報である。

ブランチノードＮ１～Ｎ６のそれぞれは、キーとページ番号とのペアを複数含む。ブランチノードＮ１～Ｎ６に含まれている各ページ番号は、子ノードである他のブランチノード又はリーフノードのページ位置を示す位置情報である。

リーフノードＮ７～Ｎ９のそれぞれは、キーとバリューとのペアを複数含む。

第１の実施形態において、ストレージシステム１の起動時には、ルートノードＮ０からブランチノードＮ１～Ｎ６までが検索情報１１としてメモリ４に記憶される。プロセッサ３は、キーバリュー検索時に、検索キーと検索情報１１とに基づいて、検索キーを含むリーフノードの位置情報を検索する。

第１の実施形態において、木構造のデータＤのどの部分を検索情報１１としてメモリ４に記憶させるかは適宜変更可能であるが、リーフノードＮ７～Ｎ９は検索情報１１に含まれないとする。例えば、ルートノードとブランチノードの一部とが、検索情報１１としてメモリ４に記憶されてもよい。

第１の実施形態において、キーを可変長とし、バリューを固定長としてもよい。第１の実施形態において、キーを例えば平均３２バイトとし、バリューを例えば６４ビットとしてもよい。

図３は、第１の実施形態に係るストレージシステム１の起動時の処理の一例を示すフローチャートである。

ステップＳ３０１において、プロセッサ３は、不揮発性メモリ１０に記憶されているデータＤのうちのルートノード及びブランチノードを含み、リーフノードを含まない検索情報１１のリードリクエストを、データ転送バス５経由でストレージデバイスＳＤ１へ送信する。

ステップＳ３０２において、ストレージデバイスＳＤ１におけるページリード回路１３は、プロセッサ３からデータ転送バス５及びインタフェース回路６経由で、リードリクエストを受信する。

ステップＳ３０３において、ページリード回路１３は、リードリクエストに基づいて、不揮発性メモリ１０から伝送路８経由でルートノード及びブランチノードを含む検索情報１１をリードし、検索情報１１をバッファメモリ９に記憶させる。ルートノード及びブランチノードのそれぞれは、例えばページ単位でリードされる。

ステップＳ３０４において、エラー訂正回路１５は、バッファメモリ９に記憶されている検索情報１１に対するエラー訂正を実行する。

ステップＳ３０５において、伸長回路１６は、バッファメモリ９に記憶されている圧縮されている検索情報１１を伸長する。

ステップＳ３０６において、データ転送回路１７は、バッファメモリ９に記憶されておりエラー訂正及び伸長された検索情報１１を、インタフェース回路６及びデータ転送バス５経由でプロセッサ３の内部メモリ１２へ転送する。

ステップＳ３０７において、プロセッサ３は、ストレージデバイスＳＤ１からデータ転送バス５経由で検索情報１１を受信し、検索情報１１を内部メモリ１２に記憶させる。

ステップＳ３０８において、プロセッサ３は、内部メモリ１２に記憶された検索情報１１を、メモリ４に記憶させる。

図４は、第１の実施形態に係るストレージシステム１によって実行されるキーバリュー検索処理の一例を示すフローチャートである。

ステップＳ４０１において、プロセッサ３は、クライアント１００からインタフェース部２経由で、検索キーを含むリードリクエストを受信する。

ステップＳ４０２において、プロセッサ３は、メモリ４に記憶されている検索情報１１を参照し、検索情報１１とリードリクエストに含まれている検索キーとに基づいて、検索キーに対応するバリューを含むリーフノードの位置情報を検索する。

ステップＳ４０３において、プロセッサ３は、検索された位置情報と検索キーとを含むリードリクエストを、データ転送バス５経由でストレージデバイスＳＤ１へ送信する。

ステップＳ４０４において、ストレージデバイスＳＤ１におけるページリード回路１３は、プロセッサ３からデータ転送バス５及びインタフェース回路６経由で、リードリクエストを受信する。

ステップＳ４０５において、ページリード回路１３は、リードリクエストに基づいて、リードコマンドを伝送路８経由で不揮発性メモリ１０へ送信し、不揮発性メモリ１０から伝送路８経由で検索キーと当該検索キーに対応するバリューとを含むページデータ（すなわちリーフノード）Ｐ１をリードし、リードしたページデータＰ１をバッファメモリ９に記憶させる。

ステップＳ４０６において、ページ内検索回路１４は、バッファメモリ９に記憶されているページデータＰ１の一部である検索キーに対応するバリューを検索し、検索されたバリューをバッファメモリ９に記憶させる。

ステップＳ４０７において、エラー訂正回路１５は、バッファメモリ９に記憶されているバリュー又はバリューを含む部分データに対するエラー訂正を実行する。

ステップＳ４０８において、伸長回路１６は、バッファメモリ９に記憶されている圧縮されているバリュー又はバリューを含む部分データを伸長する。

ステップＳ４０９において、データ転送回路１７は、バッファメモリ９に記憶されておりエラー訂正及び伸長されたバリューを、インタフェース回路６及びデータ転送バス５経由でプロセッサ３の内部メモリ１２へ転送する。

ステップＳ４１０において、プロセッサ３は、ストレージデバイスＳＤ１からデータ転送バス５経由でバリューを受信し、受信したバリューを内部メモリ１２に記憶させる。

ステップＳ４１１において、プロセッサ３は、内部メモリ１２に記憶されているバリューをインタフェース部２経由でクライアント１００へ送信する。

図５は、第１の実施形態に係る不揮発性メモリ１０の構成の一例を示すブロック図である。

第１の実施形態において、不揮発性メモリ１０はＮＡＮＤ型フラッシュメモリを備える半導体記憶装置とする。

不揮発性メモリ１０は、例えば、入出力回路２６と、レジスタセット１８と、ロジックコントローラ１９と、シーケンサ２０と、レディ／ビジー制御回路２１と、電圧生成回路２２と、メモリセルアレイ２３と、ロウデコーダモジュール２４と、センスアンプモジュール２５とを含む。

入出力回路２６は、例えば８ビット幅の入出力信号Ｉ／Ｏ１～Ｉ／Ｏ８を、伝送路８を介してコントロール回路７との間で送受信する。入出力信号は、データＤＡＴ、ステータス情報ＳＴＳ、アドレス情報ＡＤＤ、コマンドＣＭＤ等を含み得る。また、入出力回路２６は、センスアンプモジュール２５との間でデータＤＡＴを送受信する。

レジスタセット１８は、例えば、ステータスレジスタ１８Ａ、アドレスレジスタ１８Ｂ、及びコマンドレジスタ１８Ｃを含む。ステータスレジスタ１８Ａ、アドレスレジスタ１８Ｂ、及びコマンドレジスタ１８Ｃは、それぞれステータス情報ＳＴＳ、アドレス情報ＡＤＤ、及びコマンドＣＭＤを記憶する。

ステータス情報ＳＴＳは、例えばシーケンサ２０の動作状態に基づいて更新される。また、ステータス情報ＳＴＳは、コントロール回路７からの指示に基づいてステータスレジスタ１８Ａから入出力回路２６に転送され、コントロール回路７に出力される。アドレス情報ＡＤＤは、入出力回路２６からアドレスレジスタ１８Ｂに転送され、例えばチップアドレス、ブロックアドレス、ページアドレス、カラムアドレス等を含み得る。コマンドＣＭＤは、入出力回路２６からコマンドレジスタ１８Ｃに転送され、不揮発性メモリ１０の各種動作に関する命令を含む。

ロジックコントローラ１９は、コントロール回路７から受信した制御信号に基づいて、入出力回路２６及びシーケンサ２０のそれぞれを制御する。このような制御信号としては、例えばチップイネーブル信号ＣＥｎ、コマンドラッチイネーブル信号ＣＬＥ、アドレスラッチイネーブル信号ＡＬＥ、ライトイネーブル信号ＷＥｎ、リードイネーブル信号ＲＥｎ、及びライトプロテクト信号ＷＰｎが使用される。

チップイネーブル信号ＣＥｎは、不揮発性メモリ１０をイネーブルにするための信号である。コマンドラッチイネーブル信号ＣＬＥは、受け取った入出力信号がコマンドＣＭＤであることを入出力回路２６に通知するための信号である。アドレスラッチイネーブル信号ＡＬＥは、受け取った入出力信号がアドレス情報ＡＤＤであることを入出力回路２６に通知するための信号である。ライトイネーブル信号ＷＥｎは、入出力信号の入力を入出力回路２６に命令するための信号である。リードイネーブル信号ＲＥｎは、入出力信号の出力を入出力回路２６に命令するための信号である。ライトプロテクト信号ＷＰｎは、電源のオンオフ時に不揮発性メモリ１０を保護状態にするための信号である。

シーケンサ２０は、不揮発性メモリ１０全体の動作を制御する。例えば、シーケンサ２０は、コマンドレジスタ１８Ｃに保持されたコマンドＣＭＤと、アドレスレジスタ１８Ｂに保持されたアドレス情報ＡＤＤとに基づいて、リード処理、ライト処理、イレーズ処理等を実行する。

レディ／ビジー制御回路２１は、シーケンサ２０の動作状態に基づいて、レディ／ビジー信号ＲＢｎを生成する。レディ／ビジー信号ＲＢｎは、不揮発性メモリ１０がレディ状態であるかビジー状態であるかを、伝送路８経由でコントロール回路７に通知するための信号である。第１の実施形態において“レディ状態”は、不揮発性メモリ１０がコントロール回路７からの命令を受け付ける状態であることを示し、“ビジー状態”は、不揮発性メモリ１０がコントロール回路７からの命令を受け付けない状態であることを示す。

電圧生成回路２２は、リード処理、ライト処理、イレーズ処理等で使用される電圧を生成する。そして、電圧生成回路２２は、生成した電圧をメモリセルアレイ２３、ロウデコーダモジュール２４、及びセンスアンプモジュール２５に供給する。

メモリセルアレイ２３は、複数のブロックＢＬＫ０～ＢＬＫｎ（ｎは１以上の整数）を含む。ブロックは、データを不揮発に記憶することが可能な複数のメモリセルトランジスタの集合であり、例えばデータの消去単位として使用される。また、メモリセルアレイ２３には、複数のビット線ＢＬ０～ＢＬｍ（ｍは１以上の整数）と、複数のワード線ＷＬと、ソース線ＣＥＬＳＲＣと、ウェル線とが設けられる。例えば、ソース線ＣＥＬＳＲＣには、電圧生成回路２２によって電圧が印加される。各メモリセルトランジスタは、１本のビット線ＢＬと１本のワード線ＷＬとに関連付けられている。

ロウデコーダモジュール２４は、ブロックアドレスに基づいて、各種処理を実行するブロックを選択する。そして、ロウデコーダモジュール２４は、電圧生成回路２２から供給された電圧を、選択したブロック内の各種配線に転送する。また、ロウデコーダモジュール２４は、例えば複数のロウデコーダＲＤ０～ＲＤｎを含んでいる。ロウデコーダＲＤ０～ＲＤｎは、それぞれブロックＢＬＫ０～ＢＬＫｎに関連付けられている。

センスアンプモジュール２５は、リード処理において、メモリセルアレイ２３からデータをリードし、当該リードデータを入出力回路２６に転送する。また、センスアンプモジュール２５は、ライト処理において、入出力回路２６から受け取ったデータに基づいて、ビット線ＢＬに所望の電圧を印加する。例えば、センスアンプモジュール２５は、複数のセンスアンプユニットＳＡＵ０～ＳＡＵｍを含む。センスアンプユニットＳＡＵ０～ＳＡＵｍは、それぞれビット線ＢＬ０～ＢＬｍに関連付けられている。

センスアンプユニットＳＡＵ０～ＳＡＵｍのそれぞれは、例えばセンスアンプ部ＳＡ及びラッチ回路ＳＤＬ，ＡＤＬ，ＢＤＬ，ＸＤＬを含む。

以下では、説明を簡略化するため、センスアンプユニットＳＡＵ０を用いて説明を行う。しかしながら、センスアンプユニットＳＡＵ１～ＳＡＵｍについてもセンスアンプユニットＳＡＵ０と同様である。

センスアンプユニットＳＡＵ０のセンスアンプ部ＳＡは、例えばリード処理において、対応するビット線ＢＬ０の電圧に基づいて、リードデータが“０”であるか“１”であるかを判断する。言い換えると、センスアンプ部ＳＡは、対応するビット線ＢＬ０にリードされたデータをセンスして、選択されたメモリセルの記憶するデータを判断する。ラッチ回路ＳＤＬ，ＡＤＬ，ＢＤＬ，ＸＤＬのそれぞれは、リードデータ及びライトデータ等を一時的に記憶する。ラッチ回路ＸＤＬは、センスアンプユニットＳＡＵ０と入出力回路２６との間のデータＤＡＴの送受信に使用され得る。

以下で、ページデータＰ１内におけるキーとバリューとのペアの関連付け方式の例を説明する。

第１の実施形態において、キーは文字列であるとする。ページデータＰ１内では、文字列が複数の文字に分解され、各文字がノードとして管理される。ページデータＰ１内で、バリューは、ノードに関係付けられる。

図６は、第１の実施形態に係るページデータＰ１のデータ構造におけるノードｎとノード番号ｉとの関係の表現例を示す図である。

この図６で示されるノードｎは、Ｘという文字を持つ。Ｘという文字は、キーの一部を構成する。ノードｎには、ノード番号ｉが付されている。第１の実施形態において、処理get_node_char(i)は、ノード番号ｉを指定してノードｎが持つ文字Ｘを取得するための処理であるとする。ページ内検索回路１４は、処理get_node_char(i)を実行した場合に、ノード番号ｉのノードｎが持つ文字Ｘを取得する。

図７は、第１の実施形態に係るページデータＰ１のデータ構造におけるノードｎとバリューＶとの関係の表現例を示す図である。

この図７で示されるノードｎには、ノード番号ｉが付されている。ノード番号ｉのノードｎは、バリューＶと関係付けられている。第１の実施形態において、処理get_node_value(i)は、ノード番号ｉを指定してノードｎに関係付けられているバリューＶを取得するための処理であるとする。ページ内検索回路１４は、処理get_node_value(i)を実行した場合に、ノード番号ｉのノードｎに関連付けられているバリューＶを取得する。

図８は、第１の実施形態に係るページデータＰ１のデータ構造における親子の関係を持つノードｎｐ，ｎｃの表現例を示す図である。図８において、横方向の矢印の元にありノード番号ｉが付されているノードｎｐが親ノードである。横方向の矢印の先にありノード番号ｊが付されているノードｎｃが子ノードである。第１の実施形態において、処理get_child_node(i)は、指定されたノード番号ｉのノードｎｐに対する子ノードｎｃのノード番号ｊを取得するための処理であるとする。ページ内検索回路１４は、処理get_child_node(i)を実行した場合に、ノード番号ｉのノードｎｐに対する子ノードｎｃのノード番号ｊを取得する。

図９は、第１の実施形態に係るページデータＰ１のデータ構造における兄弟の関係を持つノードｎｂ１，ｎｂ２の表現例を示す図である。図９において、縦方向の矢印の元にありノード番号ｉが付されているノードｎｂ１が兄ノードである。縦方向の矢印の先にありノード番号ｊが付されているノードｎｂ２が弟ノードである。第１の実施形態において、処理get_next_node(i)は、指定されたノード番号ｉのノードｎｂ１に対する弟ノードｎｂ２のノード番号ｊを取得するための処理であるとする。ページ内検索回路１４は、処理get_next_node(i)を実行した場合に、ノード番号ｉのノードｎｂ１に対する弟ノードｎｂ２のノード番号ｊを取得する。

図１０は、第１の実施形態に係るページデータＰ１の一例をグラフで表現したデータ構造図である。図１０は、上記図６乃至図９で説明したノードの関係を用いて表現されている。

ページデータＰ１は、ページデータＰ１に含まれている複数のキーを分解して得られる複数の要素に基づいて木構造を形成し、複数の要素に対してページデータＰ１に含まれている複数のバリューを関係付けたデータ構造を持つ。上記のように、図１０では、複数のキーは文字列であり、この文字列が文字に分解されている例を示している。

ノードｎ０～ｎ６のそれぞれには、ノード番号０～６が付されている。

ノード番号０のノードｎ０は、キーの一部分に相当するＡという文字を持つ。

ノード番号１のノードｎ１は、ノード番号０のノードｎ０の子ノードである。ノード番号１のノードｎ１は、キーの一部分であるＡという文字を持つ。このノードｎ１は、バリューＶ０と関係付けられている。

ノード番号２のノードｎ２は、ノード番号１のノードｎ１の子ノードである。ノード番号２のノードｎ２は、キーの一部分であるＡという文字を持つ。このノードｎ２は、バリューＶ１と関係付けられている。

ノード番号３のノードｎ３は、ノード番号２のノードｎ２の弟ノードである。ノード番号３のノードｎ３は、キーの一部分であるＢという文字を持つ。このノードｎ２は、バリューＶ２と関係付けられている。

ノード番号４のノードｎ４は、ノード番号１のノードｎ１の弟ノードである。ノード番号４のノードｎ４は、キーの一部分であるＢという文字を持つ。

ノード番号５のノードｎ５は、ノード番号４のノードｎ４の子ノードである。ノード番号５のノードｎ５は、キーの一部分であるＢという文字を持つ。このノードｎ５は、バリューＶ３と関係付けられている。

ノード番号６のノードｎ６は、ノード番号５のノードｎ５の弟ノードである。ノード番号６のノードｎ６は、キーの一部分であるＣという文字を持つ。このノードｎ６は、バリューＶ４と関係付けられている。

ページ内検索回路１４は、検索キーに基づいて図１０のようなデータ構造を持つページデータＰ１を探索することにより、キーＡＡに対応するバリューＶ０を取得可能であり、キーＡＡＡに対応するバリューＶ１を取得可能であり、キーＡＡＢに対応するバリューＶ２を取得可能であり、キーＡＢＢに対応するバリューＶ３を取得可能であり、キーＡＢＣに対応するバリューＶ４を取得可能である。

第１の実施形態において、Ｂ＋木構造を構成するページデータＰ１は、ソートされた複数のキーの一部を含む。同じページデータＰ１内に含まれる複数のキーは類似な内容の順で配列される。ページデータＰ１内に含まれる複数のキーを、バイト単位の２分木で表現し、複数のキーの共通する部分を共有させてシリアル化することにより、１つのキーを表現するために必要となるデータサイズを、例えば８バイト程度に圧縮可能である。この場合、バリューを８バイトとすると、キーとバリューとのペアは１６バイト程度となり、４キロバイトのページデータＰ１は、およそ２５６個程度のキーとバリューとのペアを格納することができる。そして、例えば、木構造を持つページデータＰ１の６４バイト単位にエラー訂正コードを付与することで、ページデータＰ１のうち必要な部分のみをエラー訂正することができる。

図１１は、第１の実施形態に係るページ内検索回路１４の処理の一例を示すフローチャートである。

この図１１において、処理get_1st_char()は、検索キーの最初の文字を取得するための処理である。

処理get_next_char()は、検索キーの次の文字を取得するための処理である。

処理get_node_char(pos)は、先で説明したように、ノード番号ｐｏｓのノードが持つ文字を取得するための処理である。

処理get_next_node(pos)は、先で説明したように、ノード番号ｐｏｓのノードに対する弟ノードのノード番号を取得するための処理である。

処理get_child_node(pos)は、先で説明したように、ノード番号ｐｏｓのノードに対する子ノードのノード番号を取得するための処理である。

処理get_node_value(pos)は、先で説明したように、ノード番号ｐｏｓのノードに関連付けられているバリューを取得するための処理である。

ステップＳ１１０１において、ページ内検索回路１４は、変数ｐｏｓに初期値ゼロを設定し、処理get_1st_char()を実行して得られた検索キーの最初の文字を変数ｃ０に設定する。

ステップＳ１１０２において、ページ内検索回路１４は、処理get_node_char(pos)を実行して得られた文字を変数ｃ１に設定する。

ステップＳ１１０３において、ページ内検索回路１４は、変数ｃ０と変数ｃ１とが同じか否かを判断する。

ステップＳ１１０３において変数ｃ０と変数ｃ１とが同じではないと判断された場合、ステップＳ１１０４において、ページ内検索回路１４は、処理get_next_node(pos)を実行して得られた文字を変数ｐｏｓに設定する。その後、処理は、ステップＳ１１０２に移動する。

ステップＳ１１０３において変数ｃ０と変数ｃ１とが同じと判断された場合、ステップＳ１１０５において、ページ内検索回路１４は、変数ｃ０が検索キーの終端か否かを判断する。

ステップＳ１１０５において変数ｃ０が終端ではないと判断された場合、ステップＳ１１０６において、ページ内検索回路１４は、処理get_child_node(pos)を実行して得られた文字を変数ｐｏｓに設定し、処理get_next_char()を実行して得られた検索キーの次の文字を変数Ｃ０に設定する。その後処理は、ステップＳ１１０２に移動する。

ステップＳ１１０５において変数ｃ０が終端であると判断された場合、ステップＳ１１０７において、ページ内検索回路１４は、処理get_node_value(pos)を実行して得られたバリューを、検索キーに対応するバリューとして取得する。

なお、ページ内検索回路１４は、一致検索を行うとしてもよく、昇順・逆順走査による読み出しを行うとしてもよい。

以上説明した第１の実施形態に係るストレージシステム１においては、検索キーを含むリーフノードの位置情報の検索をプロセッサ３により実行し、リーフノード内における検索キーに対応するバリューの検索をコントロール回路７により実行する。このように、検索をプロセッサ３とコントロール回路７とで分散し、検索を２段階で行うことにより、不揮発性メモリ１０に記憶されている大量のデータＤの中から所望のバリューを高速に検索することができる。

第１の実施形態に係るストレージシステム１は、インデックステーブルを用いるリレーショナルデータベースなどに適用可能である。リレーショナルデータベースでは、例えば６４ビットなどのような小さいサイズのバリューが利用される場合がある。第１の実施形態では、このようにバリューのサイズが比較的小さい場合に、数十メガＩＯＰＳ以上の高い検索性能を実現することができる。

第１の実施形態においては、キーバリュー検索時に、ルートノードとブランチノードとを含みリーフノードを含まない検索情報１１がメモリ４に記憶される。このように、リーフノードがメモリ４に記憶されないことにより、メモリ４の使用量を削減することができる。例えば、比較例のデータベースシステムとして、キーバリュー検索時に、木構造のデータＤに含まれるバリューが不揮発性メモリ１０に記憶され、木構造のデータＤのうちバリューを除く他のデータがメモリ４に記憶されるデータベースシステムを考える。この比較例のデータベースシステムでは、第１の実施形態に係るストレージシステム１よりも、メモリ４に記憶される検索情報の木構造の階層が１階層多くなる。メモリ４に記憶される検索情報が第１の実施形態よりも１階層多い比較例のデータベースシステムでは、第１の実施形態に係るストレージシステム１よりも、メモリ４に記憶される検索情報のデータ量が例えば１００倍程度に増える場合がある。このように、第１の実施形態に係るストレージシステム１は、メモリ４の利用量を比較例のデータベースシステムのおよそ１／１００とすることが可能になる。

第１の実施形態においては、プロセッサ３よりも不揮発性メモリ１０に近い位置に備えられたコントロール回路７が、ページデータＰ１内の検索キーに対応するバリューを検索するページ内検索回路１４を備える。コントロール回路７のページ内検索回路１４がページデータＰ１内の検索キーに対応するバリューを検索することによって、コントロール回路７のデータ転送回路１７は、ページデータＰ１全体ではなく、検索されたバリューを含む必要なデータのみをバッファメモリ９からインタフェース回路６及びデータ転送バス５経由でプロセッサ３の内部メモリ１２へ転送可能である。このため、不要なデータがプロセッサ３とストレージデバイスＳＤ１との間で転送されることを防止することができ、プロセッサ３とストレージデバイスＳＤ１との間のデータ転送で必要となる帯域幅及びデータ転送量を削減することができ、ＩＯＰＳを向上させることができる。第１の実施形態においては、データ転送バス５のデータ転送速度を、例えば、１６ギガバイト／秒（４メガＩＯＰＳ×４キロバイト）から３２メガバイト／秒（４メガＩＯＰＳ×８バイト）に下げても、１つのストレージデバイスＳＤ１あたり４メガＩＯＰＳ以上のデータ転送が可能になる。

第１の実施形態においては、プロセッサ３ではなくコントロール回路７により、不揮発性メモリ１０からリードされたページデータＰ１の中から検索キーに対応するバリューが検索される。このように特定の処理をプロセッサ３ではないコントロール回路７で実行することにより、プロセッサ３の処理負荷を軽減させることができ、例えばＩＯＰＳなどのようなストレージシステム１全体の性能を向上させることができる。また、コントロール回路７により、ページデータＰ１の一部分であるバリューに対してエラー訂正及び伸長が実行されるため、ページデータＰ１全体に対してエラー訂正及び伸長を実行する場合よりも、エラー訂正及び伸長の処理負荷を軽減させることができ、コントロール回路７の電力効率を向上させることができる。なお、第１の実施形態において、コントロール回路７は、検索結果であるバリューを含むページデータＰ１の一部に対して、エラー訂正及び伸長を実行してもよく、この場合でも処理負荷を軽減させることができ、コントロール回路７の電力効率を向上させることができる。

第１の実施形態においては、例えば、ページデータＰ１内でのバリューの検索、検索されたバリュー又はバリューを含む部分データに対するエラー訂正及び伸長などの処理をプロセッサ３よりも消費電力が小さいコントロール回路７で実行するため、ストレージシステム１の電力効率を向上させることができる。

第１の実施形態において、不揮発性メモリ１０は、例えば、１０メガＩＯＰＳ以上であり、ページサイズは４キロバイト程度であるとする。この場合、不揮発性メモリ１０からリードされたページデータＰ１がそのままコントロール回路７からインタフェース回路６及びデータ転送バス５経由でプロセッサ３へ転送されると、プロセッサ３内の内部バスとデータ転送バス５との間のデータ転送が圧迫される場合がある。しかしながら、第１の実施形態においては、ページデータＰ１の一部分であり検索キーに対応するバリューが検索され、当該バリューがコントロール回路７からインタフェース回路６及びデータ転送バス５経由でプロセッサ３へ転送されるため、プロセッサ３内の内部バスとデータ転送バス５との間のデータ転送が圧迫されることを防止することができる。

第１の実施形態に係るストレージシステム１が複数のストレージデバイスＳＤ１～ＳＤｋを備えている場合、複数のストレージデバイスＳＤ１～ＳＤｋのそれぞれに備えられているコントロール回路７が並列に上記の処理を実行可能である。このため、複数のストレージデバイスＳＤ１～ＳＤｋの数が多くなっても、プロセッサ３の負荷増加を抑制することができる。

第１の実施形態においては、バッファメモリ９に記憶されている複数のバリューをまとめてバッファメモリ９から、インタフェース回路６及びデータ転送バス５経由でプロセッサ３の内部メモリ１２へ転送可能である。これにより、ストレージデバイスＳＤ１とプロセッサ３との間のデータ転送回数を削減することができ、ストレージデバイスＳＤ１とプロセッサ３との間で所定のサイズのデータを効率的に転送させることができる。

第１の実施形態においては、ページデータＰ１内の複数のキーを２分木で表現し、シリアル化することにより、１つのキーを表現するために必要なデータサイズを圧縮可能であり、ページデータＰ１内により多くのキーとバリューとのペアを格納させることができる。

（第２の実施形態）
第２の実施形態は、上記第１の実施形態の変形例である。

図１２は、第２の実施形態に係るストレージシステム１Ａの構成の一例を示すブロック図である。

ストレージシステム１Ａは、ストレージデバイスＳＤＡ１～ＳＤＡｋを備えるが、その他の構成要素は、上記第１の実施形態で説明したストレージシステム１と同様である。第２の実施形態では、ストレージデバイスＳＤＡ１を主に説明し、他のストレージデバイスＳＤＡ２～ＳＤＡｋに関する説明は省略する。

ストレージデバイスＳＤＡ１は、インタフェース回路６、コントロール回路７Ａ、第１のバッファメモリ９Ａ、複数の不揮発性メモリ１０Ａ１～１０Ａｎを備える。

上記第１の実施形態では、不揮発性メモリ１０から伝送路８経由でコントローラ回路７へページデータＰ１が転送され、ページデータＰ１がバッファメモリ９に記憶されている。

これに対して、第２の実施形態では、ページデータＰ１の一部分である部分ページデータＰＰ１，ＰＰ２が、不揮発性メモリ１０Ａ１から伝送路８経由でコントローラ回路７へ転送され、部分ページデータＰＰ１，ＰＰ２が第１のバッファメモリ９Ａに記憶される。

まず、コントロール回路７Ａを説明する。

コントロール回路７Ａは、部分ページリード回路１３Ａと部分ページ内検索回路１４Ａとを含む。さらに、コントロール回路７Ａは、上記第１の実施形態で説明したエラー訂正回路１５、伸長回路１６、データ転送回路１７を備えるが、図１２では簡略化のため省略している。

コントロール回路７Ａは、例えば、ＦＰＧＡでもよい。コントロール回路７Ａにおける部分ページリード回路１３Ａと、部分ページ内検索回路１４Ａとのうちの少なくとも１つの機能は、例えばファームウェアなどのソフトウェアを例えばプロセッサとして動作するコントロール回路７Ａにより実行することで実現してもよい。

部分ページリード回路１３Ａと部分ページ内検索回路１４Ａとのうちの少なくとも一部は、コントロール回路７Ａと異なる構成要素により実現されてもよい。

部分ページリード回路１３Ａは、インタフェース回路６によって受信されたリードリクエストに基づいて、リードリクエストに対応するページデータＰ１のうちの所定の部分である部分ページデータＰＰ１をリードするための初期部分リードコマンドを、伝送路８経由で不揮発性メモリ１０Ａ１へ送信する。

部分ページデータＰＰ１は、ページデータＰ１の先頭部分のデータとしてもよく、他の部分のデータとしてもよい。第２の実施形態において、部分ページデータＰＰ１は、木構造の一部であり、ページデータＰ１のどの位置にどのキーが配置されているかを推測可能な情報を含む。

そして、部分ページリード回路１３Ａは、初期部分リードコマンドに応じて不揮発性メモリ１０Ａ１によって得られた部分ページデータＰＰ１を受信し、受信した部分ページデータＰＰ１を第１のバッファメモリ９Ａに記憶させる。

なお、部分ページリード回路１３Ａは、初期部分リードコマンドに代えてページデータＰ１に対するリードコマンドを、伝送路８経由で不揮発性メモリ１０Ａ１へ送信してもよい。この場合、不揮発性メモリ１０Ａ１は、受信したリードコマンドにしたがってページデータＰ１における部分ページデータＰＰ１を、伝送路８経由でコントロール回路７Ａへ送信する。そして、部分ページリード回路１３Ａは、リードコマンドに応じて不揮発性メモリ１０Ａ１から伝送路８経由で部分ページデータＰＰ１を受信し、受信した部分ページデータＰＰ１を第１のバッファメモリ９Ａに記憶させる。

部分ページ内検索回路１４Ａは、第１のバッファメモリ９Ａに記憶されている部分ページデータＰＰ１の中に検索キーが含まれているか否かを判断する。

部分ページ内検索回路１４Ａは、部分ページデータＰＰ１の中に検索キーが含まれている場合に、検索キーに対応するバリューを検索する。

部分ページ内検索回路１４Ａは、部分ページデータＰＰ１の中に検索キーが含まれていない場合、部分ページデータＰＰ１に基づいて、ページデータＰ１のうち検索キーが含まれていると推測される部分ページデータＰＰ２を求める。

部分ページリード回路１３Ａは、部分ページデータＰＰ２をリードするための部分リードコマンドを、伝送路８経由で不揮発性メモリ１０Ａ１へ送信する。

そして、部分ページリード回路１３Ａは、部分リードコマンドに応じて不揮発性メモリ１０Ａ１から伝送路８経由で部分ページデータＰＰ２を受信し、受信した部分ページデータＰＰ２を第１のバッファメモリ９Ａに記憶させる。

部分ページ内検索回路１４Ａは、第１のバッファメモリ９Ａに記憶されている部分ページデータＰＰ２の中に検索キーが含まれているか否かを判断する。

部分ページ内検索回路１４Ａは、部分ページデータＰＰ２の中に検索キーが含まれている場合に、検索キーに対応するバリューを検索する。

部分ページリード回路１３Ａ及び部分ページ内検索回路１４Ａは、検索キーを含む部分ページデータを不揮発性メモリ１０Ａ１から伝送路８経由で受信するまで、上記と同様の、部分リードコマンドの送信、部分リードコマンドに対応する部分ページデータの受信、部分ページデータに検索キーが含まれているか否かの判断、を繰り返す。

コントロール回路７Ａに備えられており図１２では省略されているデータ転送回路１７は、検索キーに対応するバリューを、インタフェース回路６及びデータ転送バス５経由でプロセッサ３へ送信する。

次に、不揮発性メモリ１０Ａ１を説明する。

不揮発性メモリ１０Ａ１は、入出力回路２６、第２のバッファメモリ２７、シーケンサ２０Ａ、メモリチップＣＰを備える。なお、図１２において、不揮発性メモリ１０Ａ１の他の構成要素は、説明を簡略化するために省略しているが、上記図５で説明した不揮発性メモリ１０と同様の構成要素を適宜備えるとしてもよい。不揮発性メモリ１０Ａ１は、複数のメモリチップＣＰを備えるとしてもよい。１つのメモリチップＣＰは、上記図５で説明したメモリセルアレイ２３を１以上含むとしてもよい。不揮発性メモリ１０Ａ１は、１チップにより形成されてもよい。不揮発性メモリ１０Ａ１に備えられる入出力回路２６、第２のバッファメモリ２７、シーケンサ２０Ａ、メモリチップＣＰは、同一の半導体基板上に形成されてもよい。

第２のバッファメモリ２７は、上記図５で説明したレジスタセット１８、ラッチ回路ＳＤＬ，ＡＤＬ，ＢＤＬ，ＸＤＬとしてもよい。

シーケンサ２０Ａは、上記第１の実施形態で説明したシーケンサ２０の機能を実行可能であり、さらに、部分ページ処理回路２９を備える。

部分ページ処理回路２９は、シーケンサ２０Ａと異なる構成要素により実現されてもよく、例えばロジックコントローラ１９などの他の構成要素に組み込まれていてもよい。

部分ページ処理回路２９は、コントロール回路７Ａから伝送路８及び入出力回路２６経由で初期部分リードコマンド又はリードコマンドを受信する。

部分ページ処理回路２９は、受信した初期部分リードコマンド又はリードコマンドに応じて、メモリチップＣＰから初期部分リードコマンド又はリードコマンドに対応するページデータＰ１をリードし、ページデータＰ１を第２のバッファメモリ２７に記憶させる。

そして、部分ページ処理回路２９は、ページデータＰ１に含まれている部分ページデータＰＰ１を、入出力回路２６及びデータ転送バス８経由でコントロール回路７Ａへ送信する。

また、部分ページ処理回路２９は、検索キーが含まれていると推測される部分ページデータＰＰ２に対応する部分リードコマンドを、コントロール回路７Ａから伝送路８及び入出力回路２６経由で受信する。

部分ページ処理回路２９は、第２のバッファメモリ２７に記憶されているページデータＰ１のうち、受信した部分リードコマンドに対応する部分ページデータＰＰ２を、入出力回路２６及びデータ転送バス８経由でコントロール回路７Ａへ送信する。

図１３は、第２の実施形態に係るコントローラ回路７Ａと不揮発性メモリ１０Ａ１とにより実行される処理の一例を示すフローチャートである。

ステップＳ１３０１において、部分ページリード回路１３Ａは、リードリクエストを、プロセッサ３からデータ転送バス５及びインタフェース回路６経由で受信する。

ステップＳ１３０２において、部分ページリード回路１３Ａは、受信されたリードリクエストに基づいて、リードリクエストに対応するページデータＰ１のうちの部分ページデータＰＰ１をリードするための初期部分リードコマンドを、伝送路８経由で不揮発性メモリ１０Ａ１へ送信する。

ステップＳ１３０３において、部分ページ処理回路２９は、コントロール回路７Ａから伝送路８及び入出力回路２６経由で初期部分リードコマンドを受信する。

ステップＳ１３０４において、部分ページ処理回路２９は、受信した初期部分リードコマンドに応じて、メモリチップＣＰから初期部分リードコマンドに対応するページデータＰ１をリードし、リードしたページデータＰ１を第２のバッファメモリ２７に記憶させる。

ステップＳ１３０５において、部分ページ処理回路２９は、ページデータＰ１に含まれている部分ページデータＰＰ１を、入出力回路２６及び伝送路８経由でコントロール回路７Ａへ送信する。

ステップＳ１３０６において、部分ページリード回路１３Ａは、不揮発性メモリ１０Ａ１から伝送路８経由で部分ページデータＰＰ１を受信し、第１のバッファメモリ９Ａに記憶させる。

ステップＳ１３０７において、部分ページ内検索回路１４Ａは、第１のバッファメモリ９Ａに記憶されている部分ページデータＰＰ１の中の検索キーを検索する。

ステップＳ１３０８において、部分ページ内検索回路１４Ａは、部分ページデータＰＰ１の中に検索キーが含まれているか否かを判断する。

部分ページデータＰＰ１の中に検索キーが含まれていない場合、ステップＳ１３０９において、部分ページ内検索回路１４Ａは、部分ページデータＰＰ１に基づいて、ページデータＰ１のうち検索キーが含まれていると推測される部分ページデータＰＰ２を求める。

ステップＳ１３１０において、部分ページ内検索回路１４Ａは、部分ページデータＰＰ２をリードするための部分リードコマンドを、伝送路８経由で不揮発性メモリ１０Ａ１へ送信する。

ステップＳ１３１１において、部分ページ処理回路２９は、部分ページデータＰＰ２をリードするための部分リードコマンドを、コントロール回路７Ａから伝送路８及び入出力回路２６経由で受信する。

ステップＳ１３１２において、部分ページ処理回路２９は、第２のバッファメモリ２７に記憶されているページデータＰ１のうち、部分リードコマンドに対応する部分ページデータＰＰ２を、入出力回路２６及び伝送路８経由でコントロール回路７Ａへ送信する。その後、処理は、ステップＳ１３０６へ移動し、部分ページデータＰＰ２に対してステップＳ１３０６からステップＳ１３０８の処理が実行される。

上記ステップＳ１３０８において、部分ページデータＰＰ１又はＰＰ２の中に検索キーが含まれていると判断された場合、ステップＳ１３１３において、部分ページ内検索回路１４Ａは、当該検索キーに対応するバリューを検索する。

ステップＳ１３１４において、データ転送回路１７は、検索キーに対応するバリューを、インタフェース回路６及びデータ転送バス５経由でプロセッサ３へ送信する。

図１４は、第２の実施形態に係る部分ページリード回路１３Ａ及び部分ページ内検索回路１４Ａの処理の一例を示すフローチャートである。

ステップＳ１４０１は部分ページ内検索回路１３Ａによって実行され、その処理内容は上記ステップＳ１１０１と同様である。

ステップＳ１４０２において、部分ページリード回路１３Ａは、変数ｐｏｓに対応するノードを含む部分ページデータが不揮発性メモリ１０Ａ１から伝送路８及びコントロール回路７Ａ経由で第１のバッファメモリ９Ａへ転送済みか否か判断する。

ステップＳ１４０２で転送済みと判断された場合、処理は、ステップＳ１４０４へ移動する。

ステップＳ１４０２で転送済みではないと判断された場合、ステップＳ１４０３において、部分ページリード回路１３Ａは、変数ｐｏｓに対応するノードを含む部分ページデータの部分ページリードコマンドを、伝送路８経由で不揮発性メモリ１０Ａ１へ送信する。そして、部分ページリード回路１３Ａは、部分ページリードコマンドの応答として、変数ｐｏｓに対応するノードを含む部分ページデータを、不揮発性メモリ１０Ａ１から伝送路８経由で受信し、受信した部分ページデータを第１のバッファメモリ９Ａに記憶させる。

ステップＳ１４０４からステップＳ１４０９は部分ページ内検索回路１３Ａによって実行され、その処理内容は上記ステップＳ１１０２からステップＳ１１０７と同様である。

以上説明した第２の実施形態においては、不揮発性メモリ１０Ａ１から伝送路８経由でコントロール回路７Ａへ部分ページデータＰＰ１，ＰＰ２が送信される。これにより、第２の実施形態においては、上記第１の実施形態と比較して、伝送路８を用いて転送されるデータ量を削減することができ、伝送路８で使用可能な帯域幅が限られている場合であってもより多くのデータに対する検索を実行可能である。また、第２の実施形態においては、伝送路８の負荷を下げることにより消費電力を削減することができる。

第２の実施形態においては、コントロール回路７Ａ及び伝送路８に対して接続可能な不揮発性メモリ１０Ａ１～１０Ａｍの台数を増加させることができ、ストレージデバイスＳＤＡ１の記憶容量を大きくすることができる。

（第３の実施形態）
第３の実施形態においては、上記第１の実施形態に係るストレージシステム１に適用される性能と、その性能によって得られる効果の例を説明する。

ストレージシステム１は、例えば、不揮発性メモリ１０からページデータがリードされる単位時間あたり（例えば秒）のデータ量が、データ転送バス５からプロセッサ３へ転送可能な単位時間あたりのデータ量の１０％以上であるとする。

この場合において、ストレージシステム１は、ストレージデバイスＳＤ１からデータ転送バス５へ転送される単位時間あたりのデータ量を、不揮発性メモリ１０からページデータがリードされる単位時間あたりのデータ量の１／１６以下に削減可能である。

例えば、不揮発性メモリ１０からページデータがリードされる単位時間あたりのデータ量が、データ転送バス５からプロセッサ３へ転送可能な単位時間あたりのデータ量の１０％以上の場合、リードされた全ページデータを、ストレージデバイスＳＤ１からデータ転送バス５経由でプロセッサ３に送信すると、データ転送バス５に対する負荷がストレージシステム１の性能に与える影響が大きくなる。例えば、データ転送バス５に対して１０台以上のストレージデバイスＳＤ１～ＳＤｋが使用されると、データ転送バス５からプロセッサ３へ転送可能なデータ量の１００％が不揮発性メモリ１０からリードされることになり、データ量を削減することが必要になる場合がある。

これに対して、ストレージシステム１は、データ転送バス５の負荷を下げることができ、ストレージシステム１の性能が低下することを防ぐことができる。また、ストレージシステム１においては、データ転送バス５のデータ転送量が削減されることにより、消費電力を削減することができる。

なお、上記の第１の実施形態に係るストレージシステム１に対する性能の説明は、第２の実施形態に係るストレージシステム１Ａに対しても同様である。

（第４の実施形態）
第４の実施形態においては、上記第２の実施形態に係るストレージシステム１Ａに適用される性能と、その性能によって得られる効果の例を説明する。

ストレージシステム１Ａは、例えば、不揮発性メモリ１０からページデータがリードされる単位時間あたりのデータ量が、データ転送バス５からプロセッサ３へ転送可能な単位時間あたりのデータ量の１０％以上であるとする。

この場合において、ストレージシステム１Ａは、不揮発性メモリ１０Ａ１においてリードされるページデータのデータ量に対して不揮発性メモリ１０Ａ１から伝送路８へ送出されるデータのデータ量を１／４以下に削減可能である。

このようなストレージシステム１Ａにおいては、上記第３の実施形態で説明したストレージシステム１と同様に、データ転送バス５の負荷を削減することができる。

さらに、ストレージシステム１Ａにおいては、伝送路８で使用される帯域幅が限られている場合であっても、多くのデータに対する検索を実行することができる。

加えて、ストレージシステム１Ａにおいては、伝送路８の負荷も削減することができ、消費電力を削減することができる。

本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

１，１Ａ…ストレージシステム、２…インタフェース部、３…プロセッサ、４…メモリ、５…データ転送バス、ＳＤ１～ＳＤｋ，ＳＤＡ１～ＳＤＡｋ…ストレージデバイス、６…インタフェース回路、７，７Ａ…コントロール回路、８…伝送路、９…バッファメモリ、１０，１０Ａ１～１０Ａｍ…不揮発性メモリ、１１…検索情報、１２…内部メモリ、１３…ページリード回路、１４…ページ内検索回路、１５…エラー訂正回路、１６…伸長回路、１７…データ転送回路、Ｐ１…ページデータ、ＰＰ１，ＰＰ２…部分ページデータ、９Ａ…第１のバッファメモリ、１３Ａ…部分ページリード部、１４Ａ…部分ページ内検索回路、２０Ａ…シーケンサ、２７…第２のバッファメモリ、２９…部分ページ処理回路。

Claims (10)

1. プロセッサと、
   前記プロセッサから受信した検索キーに基づいて、前記検索キーに対応するバリューを検索するストレージデバイスと、
   前記バリューを含むデータの位置情報を検索するために用いられる検索情報を記憶する第１のメモリと、
   を具備し、
   前記ストレージデバイスは、
   前記データを記憶する不揮発性メモリと、
   前記不揮発性メモリを制御するコントロール回路と、
   前記コントロール回路により前記不揮発性メモリより高速にアクセス可能な第２のメモリと、
   を具備し、
   前記プロセッサは、前記検索キーと前記検索情報とに基づいて、前記位置情報を検索し、前記位置情報と前記検索キーとを前記コントロール回路へ送信し、
   前記コントロール回路は、前記位置情報と前記検索キーとに基づいて、前記不揮発性メモリから前記データの少なくとも一部をリードし、前記データの少なくとも一部を前記第２のメモリに記憶させ、前記データの少なくとも一部の中から前記検索キーに対応する前記バリューを検索し、前記バリューを前記プロセッサへ送信する、
   ストレージシステム。
2. 前記不揮発性メモリは、ルートノードと、前記ルートノードより下層の複数のブランチノードと、前記複数のブランチノードより下層の複数のリーフノードとを含む木構造を持つデータを記憶し、
   前記ルートノードは、キーとブランチノードの位置情報とのペアを複数含み、
   前記複数のブランチノードのそれぞれは、キーとリーフノードの位置情報とのペアを複数含み、
   前記複数のリーフノードのそれぞれは、キーとバリューとのペアを複数含み、
   前記検索情報は、前記ルートノードと前記複数のブランチノードの少なくとも一部とを含み、前記リーフノードを含まない、
   請求項１のストレージシステム。
3. 前記コントロール回路は、前記検索キーに対応する前記バリュー、又は、前記データのうち前記バリューを含む部分に対して、エラー訂正と伸長とのうちの少なくとも一方を実行する、
   請求項１又は請求項２のストレージシステム。
4. 前記データは、前記データに含まれている複数のキーを分解して得られる複数の要素に基づいて木構造を形成し、前記複数の要素に対して前記データに含まれている複数のバリューを関係付けたデータ構造を持ち、
   前記コントロール回路は、前記検索キーに基づいて、前記データの少なくとも一部を探索し、前記検索キーに対応する前記バリューを検索する、
   請求項１乃至請求項３のいずれか１項のストレージシステム。
5. 前記プロセッサと前記コントロール回路との間のデータ転送に用いられるデータ転送バスと、
   前記コントロール回路と前記不揮発性メモリとの間のデータ転送に用いられる伝送路と、
   をさらに具備し、
   前記データ転送バスにおける前記データ転送で使用される帯域幅は、前記伝送路における前記データ転送で使用される帯域幅より狭い、
   請求項１乃至請求項４のいずれか１項のストレージシステム。
6. 前記コントロール回路は、前記データの一部である第１の部分データを、前記不揮発性メモリから受信し、前記第１の部分データに前記検索キーが含まれていない場合に、前記データの一部であり前記第１の部分データとは異なる第２の部分データを受信する、請求項１乃至請求項５のいずれか１項のストレージシステム。
7. 前記コントロール回路は、前記第１の部分データに基づいて、前記データ内のどの位置にどのキーが配置されているかを推測可能であり、
   前記コントロール回路は、前記第１の部分データに前記検索キーが含まれていない場合に、前記第１の部分データに基づいて、前記第２の部分データを求める、
   請求項６のストレージシステム。
8. 前記コントロール回路は、前記データの一部である部分データを前記不揮発性メモリからリードする場合に、部分データリードコマンドを、前記不揮発性メモリに送信し、
   前記不揮発性メモリは、前記部分データリードコマンドを受信した場合に、前記不揮発性メモリに備えられているメモリチップからリードされた前記データのうちの前記部分データを、前記コントロール回路へ送信する、
   請求項６又は請求項７のストレージシステム。
9. 前記不揮発性メモリは、ルートノードと、前記ルートノードより下層の複数のブランチノードと、前記複数のブランチノードより下層の複数のリーフノードとを含む木構造を持つデータを記憶し、
   前記ルートノードは、キーとブランチノードの位置情報とのペアを複数含み、
   前記複数のブランチノードのそれぞれは、キーとリーフノードの位置情報とのペアを複数含み、
   前記複数のリーフノードのそれぞれは、キーとバリューとのペアを複数含み、
   前記プロセッサは、前記ストレージシステムの起動時に、前記ルートノードと前記複数のブランチノードとをリードするためのリードリクエストを前記ストレージデバイスへ送信し、
   前記ストレージデバイスは、前記リードリクエストに対して、前記不揮発性メモリに記憶されている前記ルートノードと前記複数のブランチノードとをリードし、前記リードしたルートノードと前記リードした複数のブランチノードとを前記プロセッサへ送信し、
   前記プロセッサは、前記ストレージデバイスから送信された前記ルートノードと前記複数のブランチノードとを前記検索情報として前記第１のメモリに記憶させる、
   請求項１のストレージシステム。
10. プロセッサと、第１のメモリと、不揮発性メモリ及び第２のメモリを備えるストレージデバイスと、を具備するストレージシステムの制御方法であって、
    前記プロセッサにより検索キーを指定するリードリクエストを受信し、
    前記プロセッサにより前記受信したリードリクエストで指定された前記検索キーと、前記第１のメモリに記憶されている検索情報とに基づいて、前記検索キーとバリューとのペアを含む第１のデータの前記不揮発性メモリにおける位置情報を検索し、
    前記プロセッサにより前記位置情報と前記検索キーとを前記ストレージデバイスへ送信し、
    前記ストレージデバイスにより前記位置情報と前記検索キーとに基づいて、前記不揮発性メモリから前記第１のデータの少なくとも一部である第２データをリードし、前記第２のデータを前記第２のメモリに記憶し、
    前記ストレージデバイスにより前記第２のメモリに記憶された前記第２のデータから前記検索キーに対応する前記バリューを検索し、
    前記ストレージデバイスにより前記検索されたバリューを前記プロセッサへ送信し、
    前記プロセッサにより前記検索されたバリューを前記受信したリードリクエストに対する応答として送信する、
    制御方法。

Images