(57)【特許請求の範囲】
【請求項１】
ｋｅｙと前記ｋｅｙに対応するｖａｌｕｅの組であるｋｅｙ−ｖａｌｕｅ型データを含むｋｅｙ−ｖａｌｕｅストアを備えたシステムにおいて、
前記ｋｅｙ−ｖａｌｕｅ型データを含むｋｅｙ−ｖａｌｕｅストアを格納する不揮発性メモリと、
前記ｋｅｙの入力に対して、前記ｋｅｙに基づいて前記ｋｅｙ−ｖａｌｕｅ型データが記憶された論理アドレスを生成するアドレス生成部と、
前記論理アドレスを物理アドレスに変換し、前記物理アドレスに基づいて前記不揮発性メモリから前記ｖａｌｕｅを出力するコントローラと、
を具備することを特徴とするシステム。
【請求項２】
ｋｅｙと前記ｋｅｙに対応するｖａｌｕｅの組であるｋｅｙ−ｖａｌｕｅ型データを含むｋｅｙ−ｖａｌｕｅストアを備えたシステムにおいて、
前記ｋｅｙ−ｖａｌｕｅ型データを含むｋｅｙ−ｖａｌｕｅストアを格納する不揮発性メモリと、
前記ｋｅｙの入力に対して、前記ｋｅｙに基づいて前記ｋｅｙ−ｖａｌｕｅ型データが記憶された論理アドレスを生成するアドレス生成部と、
前記論理アドレスに基づいて、前記不揮発性メモリから前記ｋｅｙに対応するｖａｌｕｅを出力するコントローラと、
を具備し、
前記ｋｅｙ−ｖａｌｕｅ型データの記憶場所が、前記論理アドレスと、前記不揮発性メモリにおける物理アドレスとを対応付ける変換テーブルで管理されることを特徴とするシステム。
【請求項３】
前記アドレス生成部は、ハッシュ関数を用いて、前記ｋｅｙから前記論理アドレスを生成することを特徴とする請求項１または２に記載のシステム。
【請求項４】
前記アドレス生成部は前記コントローラに含まれ、前記コントローラはハッシュ関数を用いて、前記ｋｅｙから前記論理アドレスを生成することを特徴とする請求項１に記載のシステム。
【請求項５】
前記コントローラは、前記ｋｅｙ−ｖａｌｕｅ型データにアクセスするためのダイレクトメモリアクセスコントローラをさらに具備することを特徴とする請求項１または４に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、ホストシステムによりアクセスされる、ｋｅｙ−ｖａｌｕｅストア方式を有するメモリシステムに関する。
【背景技術】
【０００２】
一般的なホストシステム、例えばコンピュータシステムが備えるストレージ装置として、磁気式のハードディスクドライブ（ＨＤＤ）や不揮発性半導体メモリを搭載する固体ドライブ（ＳＳＤ）などがある。ＳＳＤはストレージに分類されるが、規模と機能が拡張されたメモリシステムともいえる。
【０００３】
メモリシステムは、例えば、インターフェースと、第１のメモリブロックと、第２のメモリブロックと、コントローラから構成される。第１のメモリブロックはデータとしてのファイルを格納し、第２のメモリブロックはデータ書き込み／読み出し時におけるバッファメモリである。第１のメモリブロックは、第２のメモリブロックよりも、不揮発・大容量であるがアクセス速度が遅い。第２のメモリブロックは、インターフェースの通信速度と、第１のメモリブロックの書き込み／読み出し速度との速度差を補うために使用される。例えば、第１のメモリブロックは不揮発性のフラッシュメモリであり、第２のメモリブロックは揮発性のＤＲＡＭもしくはＳＲＡＭである。このような従来のストレージ型のメモリシステムでは、アドレス指定によるデータ書き込み／読み出し機能を実現するための構成をとっている。
【０００４】
一方、メモリシステムに保存されている、あるテキストに関連付けられた別のテキストや、バイナリファイルにおける特定のビットパターン、動画ファイルにおける特定パターン、音声ファイルにおける特徴的な音声パターンなどのデータを効率的に取り出すためには、データ指定によるデータ読み出し機能を持たせることが望ましい。このため、通常のデータ保存のみならず、データに関連付けられたメタデータを付属させて保存しておき、所望のデータを得るためにメタデータを参照する方法が用いられる。
【０００５】
メタデータの管理方法としては、大きく二つに分けられ、表形式のデータベース型と、１対１にデータが対応したｋｅｙ−ｖａｌｕｅ ｓｔｏｒｅ(ＫＶＳ)方式とがある。ＫＶＳ方式では、検索要求としてｋｅｙが与えられると、それに対応付けられていたｖａｌｕｅが出力される。
【０００６】
従来システムでＫＶＳ方式を実現するには、メモリシステム内に格納されたデータの管理や複数のメタデータを、ホストシステムの主記憶装置（ＤＲＡＭ）にデータを展開した上で、中央演算装置（ＣＰＵ）を使用して演算を施した後に再びストレージからデータを読み出して照合するという、繰り返しのデータ入出力処理を実施している。
【０００７】
従来システムでのｋｅｙ−ｖａｌｕｅ ｓｔｏｒｅ（ＫＶＳ）方式とその問題点を説明する。
【０００８】
従来型ＳＳＤでＫＶＳ方式を実現する場合、データはファイルとして保存され、データに付属するｋｅｙ−ｖａｌｕｅ型データ（あるいはｋｅｙ−ｖａｌｕｅペア）のメタデータもまたファイルとして保存されている。すなわち、ｋｅｙ−ｖａｌｕｅストア方式を実現しているのはファイルシステム以上の上位システムであって、ＯＳに実装されたファイルシステムあるいはアプリケーションである。
【０００９】
この場合、汎用的なハードウェア構成でｋｅｙ−ｖａｌｕストア方式を実現できるという利点はあるものの、メタデータの取り扱いが通常のデータと同じであるため、メタデータの読み出し／書き込みあるいは検索操作は、ホストシステムがメタデータファイルをメインメモリ（例えば、ＤＲＡＭ）に読み出してから扱うことになる。これにより、例えば以下のような少なくとも３つの問題点が生じる。
【００１０】
第１に、ファイルアクセス性能が低下する。一般的に、メインメモリのサイズはＳＳＤと比較して小さいため、メインメモリサイズよりも大きなメタデータファイルは一度に取り扱うことができない。このため、メタデータファイルは、例えばｋｅｙ毎に分割化しておき、扱い易いサイズのメタデータファイルを必要に応じてメインメモリに読み出してから利用することになる。必要なｋｅｙ−ｖａｌｕｅが得られるまでこの過程が繰り返され、メタデータファイルの数に応じたファイルアクセスがＳＳＤに対して発生するため、ＳＳＤのファイルアクセス速度が、メタデータ読み出し要求の速度よりも遅い場合、ホストシステムおよびローカルシステム（メモリシステム）の全体を律速してしまう。
【００１１】
第２に、ＣＰＵの負荷が増大する。メタデータの作成、管理、照合（検索）はすべてＣＰＵによって処理されるため、メタデータ処理の間、ＣＰＵに負荷が生じる。特に、メタデータはデータに対応して作成されているため、データを更新した際には、対応するメタデータをメタデータファイルの中から探し出して更新する必要がある。また、メタデータを検索する仕組みもＣＰＵでソフトウェアアルゴリズムを駆使して行わねばならないため、結局ＣＰＵはメタデータ管理のための負荷を新たに生じることになる。
【００１２】
第３に、バスあるいはインターフェースへの負荷が増大する。第１、第２の問題点の結果、ホストシステムとローカルシステム（メモリシステム）との間はメタデータ情報が頻繁に行き来することになり、バス及びインターフェース部のトラフィックが増大する。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００５−２０９２１４号公報
【特許文献２】特許第４１６７３５９号
【発明の概要】
【発明が解決しようとする課題】
【００１４】
メタデータに対する操作要求をｋｅｙ−ｖａｌｕｅストア方式によって効率的かつ高速に処理することができるメモリシステムを提供する。
【課題を解決するための手段】
【００１５】
一実施態様のメモリシステムは、ｋｅｙと前記ｋｅｙに対応するｖａｌｕｅの組であるｋｅｙ−ｖａｌｕｅ型データを含むｋｅｙ−ｖａｌｕｅストア方式を備えたメモリシステムにおいて、データを記憶するデータ領域と、前記ｋｅｙ−ｖａｌｕｅ型データを含むメタデータファイルとを格納する第１のメモリと、前記第１のメモリに対してアドレス指定による書き込み及び読み出しを実行すると共に、前記ｋｅｙ−ｖａｌｕｅ型データに対する処理を実行するコントローラとを具備することを特徴とする。
【図面の簡単な説明】
【００１６】
【図１】第１のメモリブロック内の実データ領域とメタデータテーブルとの関係、及びｋｅｙ−ｖａｌｕeストア方式の仕組みを模式的に示す図である。
【図２】図１における要素と集合の関係を示す図である。
【図３Ａ】ｋｅｙ−ｖａｌｕｅストア方式における具体的な処理手順を示すフローチャートである。
【図３Ｂ】ｋｅｙ−ｖａｌｕｅストア方式における具体的な処理手順を示すフローチャートである。
【図３Ｃ】ｋｅｙ−ｖａｌｕｅストア方式における具体的な処理手順を示すフローチャートである。
【図３Ｄ】ｋｅｙ−ｖａｌｕｅストア方式における具体的な処理手順を示すフローチャートである。
【図４】第１実施形態のメモリシステムのハードウェア構成を示すブロック図である。
【図５】第２実施形態のメモリシステムのハードウェア構成を示すブロック図である。
【図６】第３実施形態のメモリシステムのハードウェア構成を示すブロック図である。
【図７】第４実施形態のメモリシステムのハードウェア構成を示すブロック図である。
【図８】第５実施形態のメモリシステムのハードウェア構成を示すブロック図である。
【図９】第６実施形態のメモリシステムのハードウェア構成を示すブロック図である。
【図１０】第７実施形態のメモリシステムのハードウェア構成を示すブロック図である。
【図１１】第８実施形態のメモリシステムのハードウェア構成を示すブロック図である。
【図１２】変形例１の実データ領域とメタデータテーブルとを模式的に示す図である。
【図１３】変形例２の実データ領域とメタデータテーブルとを模式的に示す図である。
【図１４】変形例３の実データ領域とメタデータテーブルとを模式的に示す図である。
【図１５】変形例３のｋｅｙ−ｖａｌｕeストア方式の他の実現方法を模式的に示す図である。
【図１６】変形例４の実データ領域とメタデータテーブルとを模式的に示す図である。
【発明を実施するための形態】
【００１７】
以下の説明において、略同一の機能及び構成を有する構成要素については、同一符号を付し、重複説明は必要な場合にのみ行う。
【００１８】
メモリシステムに保存されるメタデータがｋｅｙ−ｖａｌｕｅストア方式で保存される。そのｋｅｙ−ｖａｌｕｅ型データの効率的な保存方法と構成を与えるための実施形態を、図を用いながら説明する。
【００１９】
＜メタデータテーブルとｋｅｙ−ｖａｌｕｅストア方式＞
まず、本実施形態の基本原理となるメタデータテーブルとｋｅｙ−ｖａｌｕｅストア方式について述べる。
【００２０】
図１は、第１のメモリブロック内の実データ領域とメタデータテーブルとの関係、及びｋｅｙ−ｖａｌｕeストア方式の仕組みを模式的に示している。なお、数値や記号は説明のために用いられており、実施形態とは必ずしも対応していない。
【００２１】
図１に示すように、メモリアクセス可能な物理アドレス空間内には、アドレス指定の実データ領域（実アドレス空間）１６１と、メタデータテーブル１６２が存在している。実データ領域１６１は、従来概念でいうところの論理アドレス空間にそのまま対応する。メタデータテーブル１６２は、メモリシステム側が適宜用いるデータ領域であるため、ユーザーまたはクライアントが通常利用では明示的にアクセスすることはしない。ただし、システムへのテストコマンドとしては明示的にアクセスすることも許可される。ユーザーは基本的にインターフェースコマンドを用いてメモリシステムに対し、実データあるいはメタデータを操作する要求を投げかけ、メモリシステムは内部で処理した結果、返答としての信号あるいはデータをユーザー（ホストシステム）へ返す。
【００２２】
メモリシステムは、論理アドレスを物理アドレスに変換するための論理アドレス−物理アドレス変換テーブルの中で、実データ領域１６１とメタデータテーブル１６２の格納領域を区別する。メタデータテーブル１６２内のメタデータアドレスは、必要に応じて作られるため、ｋｅｙ−ｖａｌｕｅ型データの作成要求がなければ第１のメモリブロック内に存在しない場合も有り得る。
【００２３】
このように、本実施形態のメモリシステムでのメタデータテーブル１６２の記憶容量は固定されて設置されているわけではなく、ｋｅｙ−ｖａｌｕｅストア方式に基づく要求に応じて任意に可変（拡張あるいは縮小）されて存在できるものである。このため、ユーザーはメタデータを任意に扱いつつ、アクセス可能な物理メモリ空間が最大効率で利用可能となる。極端に言えば、メタデータをまったく扱わない場合も取り得る。この場合、物理メモリ空間が最大限に利用できる。
【００２４】
逆に、メタデータを十分活用した場合は、実データ領域１６１と同サイズ以上にメタデータテーブル１６２を拡大する場合もあり得る。この場合でも、メタデータの管理はメモリシステム（ローカルシステム）側の仕事なので、ホストシステム側はメタデータの管理から開放されている。従って、ユーザー（ホストシステム側）は通常利用においてメタデータの管理を意識する必要はなくなる。
【００２５】
メタデータテーブル１６２にはｋｅｙ−ｖａｌｕｅペアが保存されているが、データの実態は実データ領域（実アドレス空間）１６１に存在する。
【００２６】
本実施形態でのメタデータテーブル１６２と実データ領域１６１の実データとの関係について、ｋｅｙ−ｖａｌｕｅストア方式によるデータ取り出しの具体例を示して説明する。
【００２７】
ｋｅｙ−ｖａｌｕｅストア（ＫＶＳ）方式とは、キー（ｋｅｙ）と値（ｖａｌｕｅ）の組を書き込み、キーを指定することで値を読み出せるデータベース管理方式のことを意味する。ＫＶＳ方式は、ネットワーク越しに使われる例が多いが、データの格納先はどこかのローカルのメモリあるいはストレージシステムであることは間違いない。メタデータといえども実データアドレス空間内に格納されている。
【００２８】
データは、通常、保存されているメモリの先頭アドレスを指定することで読み出される。ここで、データをファイルと言い替えても良い。ファイルシステムによっては、実データアドレス空間が、例えば５１２バイトのセクタ単位で管理される。あるいは、ファイルシステムを限定する必要がなければ、例えばＮＡＮＤフラッシュメモリの読み出し／書き込みのページサイズである、４ＫＢや８ＫＢ単位などで管理されても良い。
【００２９】
図１に示す実データ領域１６１には、概念的に実アドレスに対応したファイル（データ）の保存の様子を示している。例えば、＆００１の実データアドレスにファイルa-file.txtのファイルＩＤである％a-file.txtが保存され、＆００２に“This is a book”というファイル内容が保存されているとする。実際は、実データアドレスはバイト単位で管理されるのが一般的なため、＆００１と＆００２のように連続するのは特殊な例である。
【００３０】
図１に示すメタデータテーブル１６２には、保存されたｋｅｙ−ｖａｌｕｅペアが示されている。ｋｅｙはデータファイルから抽出されたもので、検索対象の要素あるいは集合である。この例ではｋｅｙは集合であり、＆００１と＆０１１という要素を含む。Ｖａｌｕｅはｋｅｙが見つかったときに返される値である。この例では“book”という単語を含むデータファイルのファイルＩＤの集合を、実データアドレス空間のアドレスの形でｖａｌｕｅとして格納している。
【００３１】
図１中の手順に従って説明すると、
（i）ｋｅｙをｅｎｔｒｙとして入力し、メタデータテーブルからｖａｌｕｅを探す。
【００３２】
（ii）見つかったｋｅｙに対応するｖａｌｕｅは、ｋｅｙが所属する集合を保存する実データアドレスなので、その実データアドレスを参照する。
【００３３】
（iii）参照された実データアドレスに書かれたデータを出力する。
【００３４】
となる。
【００３５】
このような実データアドレスとメタデータテーブルの関係、およびｋｅｙ−ｖａｌｕｅペアの関係は、図２（ａ）及び図２（ｂ）に示すような、要素と集合の関係となっている。
【００３６】
すなわち、通常のファイルでは、図２（ｂ）に示すように、例えば“a-file.txt”というファイル名のファイルが集合であり、“This is a book”というテキストデータのそれぞれの単語が要素である。ファイルＩＤも１つの要素である。
【００３７】
一方、メタデータテーブル（メタデータアドレス空間）に置かれた場合、図２（ａ）に示すように、集合と要素の関係が逆転して整理し直された形態をとり得る。すなわち、「転置」の関係に変換されている。“book”という集合の中には、“a-file.txt”、“b-file.txt”というファイル名が要素として保存されることになる。ｋｅｙ−ｖａｌｕｅ型データでは、この整理し直された集合名（“book”）を検索し、その要素（“a-file.txt”、“b-file.txt”）を求めていることになる。これは、一般に、全文検索で実行されている転置ファイルの作成と、検索手順そのものであって、ｋｅｙ−ｖａｌｕｅ型データの実用上の一例といえる。
【００３８】
転置ファイルとは、全文検索機能の実現法の一つである転置インデックス法で用いられる検索のための索引ファイルである。転置インデックス法では、コンテンツ毎にそのコンテンツを含むファイルのリストを格納する転置ファイルと呼ばれる索引データファイルを予め作成し、ファイルの追加／削除の都度あるいは定期的にまとめて、転置ファイルの内容を更新する。コンテンツの検索要求に対しては、その検索対象のコンテンツに対応する転置ファイルの内容を検索結果として出力すればよい。そのため、全文検索の都度、すべてのファイルの内容を調べる必要がない。従って、検索を高速化できる。転置ファイルは、ｋｅｙ−ｖａｌｕｅ型データの１つの用例であって、本実施形態はこれに限定しないことに注意すべきである。
【００３９】
＜ｋｅｙ−ｖａｌｕｅストア方式のコマンド＞
ホストシステムからは、メモリシステムのホストインターフェースに対し、ｋｅｙ−ｖａｌｕｅストア要求のための次のコマンドが与えられる。
【００４０】
ｋｅｙ−ｖａｌｕｅストア方式に基づく要求のためのコマンドは、ｋｅｙに関連付けられた新たな集合（ｖａｌｕｅ）を登録するコマンド（ＰＵＴ）、あるｋｅｙに関連付けられた集合（ｖａｌｕｅ）に新たな要素（ｖａｌｕｅ）を追加するコマンド（ＷＲＩＴＥ）、ｋｅｙに関連付けられた集合（ｖａｌｕｅ）の要素をバッファに格納しそのサイズを返すコマンド（ＧＥＴ）、バッファに格納されている要素（ｖａｌｕｅ）を読み出すコマンド（ＲＥＡＤ）、を含む。
【００４１】
コマンド名称は適宜変更されても良く、ｋｅｙ−ｖａｌｕｅストア方式に基づく要求のために新たなコマンドが追加されても良い。例えば、集合（ｋｅｙ）に属する要素（ｖａｌｕｅ）を整理するためのコマンドや、メタデータテーブル内の集合（ｋｅｙ）の並び替えや、要素（ｖａｌｕｅ）同士の比較、などを命令するコマンドである。
【００４２】
本実施形態では、コマンド要求に従い、メタデータテーブルと実データ領域の連携がメモリシステム内で行われる。上記コマンドを用いた場合の、ｋｅｙ−ｖａｌｕｅ型データの追加、検索などの具体的な手順を図３Ａ〜図３Ｄのフローチャートに示す。
【００４３】
（１）新たなｋｅｙ−ｖａｌｕｅ型データを登録する場合（ＰＵＴ）、図３Ａに示すように、まず、そのｋｅｙがメタデータテーブルにすでに存在しているかを検索する（ステップＳ１，Ｓ２）。ｋｅｙが見つかれば、出力にエラーを返す、すなわち、ｋｅｙが既に存在していることを返信して終了する（ステップＳ３）。
【００４４】
一方、ｋｅｙが見つからなければ、ｖａｌｕｅの処理に進む。ｖａｌｕｅが実データ領域（実データアドレス）に保存されているかを検索する（ステップＳ４）。そのｋｅｙ−ｖａｌｕｅ型データの登録時点で、ｖａｌｕｅが実データ領域に保存されていなければ、ｖａｌｕｅを実データ領域に追加する（ステップＳ５）。ｖａｌｕｅが保存されていれば、そのままｋｅｙをメタデータテーブルに保存し、そのｋｅｙにｖａｌｕｅの実データアドレスを関連付けて登録する（ステップＳ６）。
【００４５】
メモリシステム内で論理アドレス−物理アドレス変換テーブルが管理されている場合、管理している機能回路に対してメタデータテーブルの更新を通知する（ステップＳ７）。最後に、ｖａｌｕｅの実データサイズを出力して終了する（ステップＳ８）。
【００４６】
（２）既にあるｋｅｙに対し、新たなｖａｌｕｅを追加する場合（ＷＲＩＴＥ）、図３Ｂに示すように、まず、そのｋｅｙがメタデータテーブルに存在しているかを検索する（ステップＳ１１，Ｓ１２）。ｋｅｙが見つからなければ、出力に、例えば、size=0を返してｋｅｙが存在しないことを通知する（ステップＳ１３）。
【００４７】
一方、ｋｅｙが見つかれば、ｋｅｙに対応するｖａｌｕｅに保存された実データアドレスが指定する格納場所を参照し（ステップＳ１４）、その格納場所に新たなｖａｌｕｅを追加する。まず、ｖａｌｕｅの格納場所に空きがあるかを調べる（ステップＳ１５）。ｖａｌｕｅの格納場所に空きがない場合、別のｖａｌｕｅの実データアドレスへジャンプするためのポインタを格納する（ステップＳ１６）。続いて、そのアドレスが指定する格納場所に新たなｖａｌｕｅを追加する（ステップＳ１７）。
【００４８】
ｖａｌｕｅの格納場所に空きがある場合は、ｖａｌｕｅの実データアドレスの空いている格納場所に新たなｖａｌｕｅを追加する（ステップＳ１７）。最後に、ｖａｌｕｅの実データサイズを出力して終了する（ステップＳ１８）。
【００４９】
（３）ｋｅｙに関連付けられた集合（ｖａｌｕｅ）を得る場合（ＧＥＴ）、図３Ｃに示すように、まず、そのｋｅｙがメタデータテーブルに存在しているかを検索する（ステップＳ２１，Ｓ２２）。ｋｅｙが見つからなければ、出力に、例えば、size=0を返してｋｅｙが存在しないことを通知する（ステップＳ２３）。
【００５０】
一方、ｋｅｙが見つかれば、ｋｅｙに対応するｖａｌｕｅに保存された実データアドレスが指定する格納場所を参照する（ステップＳ２４）。そして、その実データアドレスの格納場所に記憶されたｖａｌｕｅを読み出してバッファメモリあるいはレジスタメモリに格納する（ステップＳ２５）。最後に、ｖａｌｕｅの実データサイズを出力して終了する（ステップＳ２６）。
【００５１】
（４）バッファメモリ（あるいは、レジスタメモリ）に格納されている集合（ｖａｌｕｅ）の要素を出力させる場合（ＲＥＡＤ）、図３Ｄに示すように、集合（ｖａｌｕｅ）の要素が格納されたバッファメモリ内の保管場所を参照する（ステップＳ３１）。そして、集合（ｖａｌｕｅ）の要素があるか否かを調べる（ステップＳ３２）。集合（ｖａｌｕｅ）の要素が見つからなければ、出力に、例えば、S=NULLを返して集合（ｖａｌｕｅ）の要素が存在しないことを通知する（ステップＳ３３）。
【００５２】
一方、集合（ｖａｌｕｅ）の要素が見つかれば、指定されたサイズ分に対応する集合（ｖａｌｕｅ）の要素を読み出す（ステップＳ３４）。続いて、読み出した集合（ｖａｌｕｅ）の要素を出力して終了する（ステップＳ３５）。ここでは、サイズ指定によって要素を読み出す例を示したが、実際にはバッファメモリの場所を特定して読み出しても良い。
【００５３】
なお（３）の手順において、ホストシステムにｖａｌｕｅの実データアドレスの先頭アドレスを返すという場合も有り得る。これは、この手順の後にはたいてい次の（４）の手順が行われることになるので、ｖａｌｕｅの実データを読み出すのに都合が良いからである。どう定義するかはコマンドセットの定義に依存していて、本出願ではｋｅｙ−ｖａｌｕｅストア方式の手順を説明するために具体的なコマンドセットを用いて説明しているので、これに限定されない。他の手順も同様に前記説明に限定されるものではない。
【００５４】
メモリシステムが、Ｈａｓｈ−ＣＡＭを用いている場合は、ｋｅｙとｖａｌｕｅが一致していない場合、すなわちｋｅｙとｖａｌｕｅが関連付けられたものでない場合があり得る。なお、Ｈａｓｈ−ＣＡＭについては後で詳述する。
【００５５】
このため、Ｈａｓｈ−ＣＡＭの場合は、メタデータテーブル内でｋｅｙを検索する手順において、ｋｅｙに対応付けられたｖａｌｕｅを参照し、実データとｋｅｙが一致しているか判別する手順が加わる。一致していなければ、Ｈａｓｈ−ＣＡＭでのｋｅｙ−ｖａｌｕｅストア方式のアドレス管理ルール（例えば、隣のアドレスを調べる）に従って、別のｋｅｙ範囲のメタデータアドレスに指定して検索しなおす。
【００５６】
なお、実際の手順やコマンドはこれに限定されない。例えば、実際の運用で、複数のｋｅｙが見つかった場合には、一度フラグを立てておいてまとめてｖａｌｕｅを読むなど、方法にバリエーションを持たせることができる。
【００５７】
さらに上述したように、例えば、集合（ｋｅｙ）に属する要素（ｖａｌｕｅ）を整理するためのコマンドや、メタデータテーブル内の集合（ｋｅｙ）の並び替えや、要素（ｖａｌｕｅ）同士の比較などを命令するコマンドに対する手順があり得る。
【００５８】
なお、ｋｅｙとｖａｌｕｅは、一方が集合で他方が要素、またはその逆の関係を取り得る。あるいは、１対１に対応するものであるため、両者ともに集合、または、要素ということもあり得る。
【００５９】
本実施形態においては、ホストインターフェースあるいは、それを介してローカルコントローラやメモリコントローラなどが上記検索コマンドを受け付けて、ｋｅｙ−ｖａｌｕｅストア方式の一連の処理を実行することができる。また、メモリシステム内のローカルコントローラあるいはメモリコントローラにダイレクトメモリアクセスコントローラ（ＤＭＡＣ：Direct Memory Access Controller）が備わった構成をとることができ、この場合、メモリシステムが主体的にｋｅｙ−ｖａｌｕｅストア方式の動作を制御することが可能である。場合によってはメモリシステム外の別のメモリ（例えばホストシステムのメインメモリ）に主体的にアクセスすることが可能である。
【００６０】
以下では、本実施形態の具体的なハードウェア構成について、適宜、図を用いて説明する。
【００６１】
［第１の実施形態］
第１実施形態のメモリシステムのハードウェア構成について説明する。
【００６２】
図４は、第１実施形態のメモリシステムのハードウェア構成を示すブロック図である。
【００６３】
図示するように、メモリシステム（またはローカルシステム）１０は、ホストインターフェース１１、ローカルコントローラ１２、メモリコントローラ（あるいはチップコントローラ）１３、固定長データ生成器１４、レジスタメモリ（あるいはキャッシュメモリ、ページレジスタ、Ｒ／Ｗレジスタ、ページキャッシュなどとも呼ばれる）１５、及び第１のメモリブロック１６を備える。
【００６４】
メモリシステム１０のホストインターフェース１１には、例えば、ＡＭＢＡ、ＳＡＴＡ、ＰＣＩe、ＵＳＢなどのバスを介してホストシステムが接続されている。ホストシステムは、ＣＰＵ１０１及びメインメモリ１０２を有する。
【００６５】
第１のメモリブロック１６は、実データ領域１６１と、実データ領域１６１から抽出したメタデータテーブル１６２を格納する。このメタデータテーブル１６２は、ｋｅｙ−ｖａｌｕｅ型データを有する。
【００６６】
メタデータテーブル１６２におけるｋｅｙ−ｖａｌｕｅ型データは、データに関連付けられたメタデータとしてのｋｅｙと、関連付けられたデータの実データアドレスの先頭アドレス（ｖａｌｕｅ）を、リストとして格納する。このｋｅｙ−ｖａｌｕｅ型データを用いて、例えば、上述した転置ファイルなどを構成することができる。
【００６７】
第１のメモリブロック１６には、例えば、不揮発性半導体メモリの１つであるＮＡＮＤフラッシュメモリが用いられる。ＮＡＮＤフラッシュメモリは、１つのチップでもよいし、記憶容量を増大させるため複数のチップで構成されていても良い。なお、第１のメモリブロック１６には、その他、記憶不揮発性を有する固体チップＬＳＩであれば、例えば、ＭＲＡＭ(Magnetic Random Access Memory)やＲｅＲＡＭ(Resistive Random Access Memory)も用いることができるが、これらに限定されるものではない。
【００６８】
ホストインターフェース１１は、ホストシステムからアドレス指定による通常のデータ操作要求、すなわちデータ書き込み及び読み出しの要求と、メタデータテーブル１６２内のｋｅｙ−ｖａｌｕｅストア型データへの書き込み及び読み出しの要求を受け付けることができる。
【００６９】
第１のメモリブロック１６への書き込み及び読み出し要求は、メモリコントローラ１３で受け付けられ、制御される。さらに、メモリコントローラ１３と第１のメモリブロック１６との間には、固定長データ生成器１４とレジスタメモリ１５が接続されている。レジスタメモリ１５は、ページレジスタ、Ｒ／Ｗレジスタ、ページキャッシュなどとも呼ばれるが、書き込みあるいは読み出しを行う際に、一時的に記憶領域として使用される。特に、このレジスタメモリ１５には演算機能が備わっており、一般的にＮＡＮＤフラッシュメモリの多値動作を制御するために用いられ、本実施形態でも同様に用いられる。
【００７０】
本実施形態では、第１のメモリブロック１６に対しｋｅｙ−ｖａｌｕｅ型データの書き込み及び読み出しを行うために用いられる固定長データ生成器１４、例えばハッシュ生成器を備えていることを特徴とする。ハッシュ生成器は、ｋｅｙの入力に対して、ｋｅｙ−ｖａｌｕｅ型データが記憶されたアドレスを取得するアドレス取得回路として機能する。ここで、ハッシュ生成器は、ハッシュ関数を生成する機能を有する電子回路と見なして良いが、専用回路を用いてもよいし、あるいは汎用演算回路にハッシュ関数アルゴリズムを入力したものを用いても良い。
【００７１】
ハッシュ生成器により生成されたハッシュ値（アドレス）は衝突する可能性がある。メモリコントローラ１３は、ハッシュ値の衝突後の処理のための比較回路やアドレス管理回路を備える。固定長データ生成器（ハッシュ生成器）１４とアドレス管理回路を用いたデータ格納・検索方法については後述する。なおここでは、メモリコントローラ１３と固定長データ生成器１４が個別に形成された例を示したが、メモリコントローラ１３が固定長データ生成器１４を含んでいてもよい。
【００７２】
さらに、本実施形態の構成として、ホストインターフェース１１と第１のメモリブロック１６の相互の信号送受信を制御するためにローカルコントローラ１２を備える。ローカルコントローラ１２は、第１のメモリブロック１６から出力されたデータに対するエラー訂正符号復号（ＥＣＣ）回路を備えることができる。なお、ＥＣＣ回路は、メモリコントローラ１３に備わっていればローカルコントローラ１２に備える必要はない。
【００７３】
また、ローカルコントローラ１２は、第１のメモリブロック１６の論理アドレスを物理アドレスに変換する、論理アドレス−物理アドレス変換テーブルを管理する機能を備えることができる。これによりローカルコントローラ１２は、実データ領域１６１及びメタデータテーブル１６２と論理アドレスとの対応を管理することができる。すなわち、ローカルコントローラ１２は、論理アドレス−物理アドレス変換テーブルの中で、実データ領域１６１とメタデータテーブル１６２の記憶領域を区別する。このため、第１のメモリブロック１６内おいて、実データ領域１６１とメタデータテーブル１６２の記憶領域は分離されている必要はなく、混在していてもよい。
【００７４】
これら処理のために、第２のメモリブロックをローカルコントローラ１２の内部に含むことができる。あるいは、ローカルコントローラ１２の外部にバス線を介して第２のメモリブロックを接続しても良い。
【００７５】
第２のメモリブロックの存在は従来型のＳＳＤであれば自明であるが、仮に第２のメモリブロックが存在しなくとも、本実施形態の最小構成を示す上では必ずしも不都合とならないため、図４では第２のメモリブロックを図示していない。ただし、ローカルコントローラ１２が第２のメモリブロックを利用できるのであれば、メタデータテーブルを第１のメモリブロック１６から第２のメモリブロック内へ読み出して参照することができる。
【００７６】
なお、第２のメモリブロックは、ホストインターフェース１１の通信速度と、第１のメモリブロック１６のアクセス速度との速度差を補うためにも使用される。このため、第２のメモリブロックには、第１のメモリブロック１６に比べて、揮発・小容量であるがアクセス速度が速いものが用いられる。
【００７７】
例えば、第２のメモリブロックには、揮発性のＤＲＡＭもしくはＳＲＡＭが用いられる。あるいは、同等の速度と容量が得られれば、不揮発性ＲＡＭ（Random Access Memory）、例えば、ＭＲＡＭ（磁気抵抗変化膜ＲＡＭ）、ＲｅＲＡＭ（抵抗変化膜ＲＡＭ）、ＦｅＲＡＭ（強誘電体膜ＲＡＭ）、ＰＣＲＡＭ（相変化膜ＲＡＭ）などを用いてもよい。第１のメモリブロック１６にフラッシュメモリを用いたメモリシステムであれば、ローカルコントローラ１２、第２のメモリブロック、論理アドレス−物理アドレス変換テーブルを用いて、ウェアレベリング機能を備えるのが一般的であり、本実施形態でこれを用いても良い。
【００７８】
＜ハッシュ関数を用いたデータ格納・検索方法＞
本実施形態の固定長データ生成器（ハッシュ生成器）１４とアドレス管理回路を用いたデータ格納・検索方法について説明する。アドレス管理回路は、メモリコントローラ１３に備えられており、ハッシュ値（アドレス）の衝突を回避する処理を行う。
【００７９】
本実施形態は、ハッシュ生成器を備えているため、任意長ビットデータをハッシュ関数によって固定長ビットデータに変換することができる。ここでは、この機能を用いて、ハッシュ生成器が、任意長ビットデータのメタデータから、固定長ビットデータのメタデータアドレスを生成する例を示す。
【００８０】
ハッシュ関数としては、なるべく均一かつ疎な暗号学的ハッシュ関数が好ましい。例えば、ＳＨＡ−１(Secure Hash Algorithm-1)、ＳＨＡ−２(Secure Hash Algorithm-2)、ＭＤ４(MessageDigest4)、ＭＤ５(MessageDigest5)などを使用する。
【００８１】
ハッシュ生成器は、与えられた任意長の<key>を、ハッシュ関数に従って固定長ビットのビット列をhash(<key>)のように得て、さらに所望のビット長(BitLength)に短縮する機能を有する。例えば、次式の除算機能を有する。
【００８２】
<key ID>= hash(<key>) mod BitLength
あるいは、単純に、生成された固定長ビットのビット列の先頭から所望の長さの分だけを切り取って使用しても良い。
【００８３】
このように生成されたｋｅｙＩＤの長さを、メタデータテーブルのアドレス長と等しくしておけば、そのままメタデータテーブルのアドレスとして利用できる。例えば図１において、メタデータテーブルにおけるｋｅｙ−ｖａｌｕｅ型データで説明すると、ハッシュ生成器による“book”の固定長ビットデータの生成（以下、hash(“book”)と記す）の結果が００１であれば、メタデータテーブルの＄００１番地は“book”というｋｅｙに対応する。この＄００１番地には対応するｖａｌｕｅが保存されている。
【００８４】
同様に“Blue”の場合もhash(“Blue”)の結果が００２であれば、＄００２のメタデータアドレスに対応するｖａｌｕｅが保存される、という要領でｋｅｙとｖａｌｕｅを格納していく。
【００８５】
ｋｅｙを検索したい時には、例えば“book”の場合、そのハッシュ関数の出力値（ハッシュ値）である００１は、その値がそのまま格納場所のメタデータアドレスなので、直接そのアドレスを参照すれば良い。このような、ハッシュ関数とメモリアドレスの対応を活用したデータ参照方法をＨａｓｈ−ＣＡＭと呼ぶ。
【００８６】
Ｈａｓｈ−ＣＡＭでは、できるだけ疎なハッシュ関数を用いたとしても、確率論的にハッシュ値（アドレス）が衝突する可能性はゼロにはならない。実用上、ハッシュ値の衝突の可能性を減らす最も単純かつ有効な方法は、十分に大きなメモリ空間を用意することである。実際には、メモリサイズは制限されているため衝突は起こりえる。そこで衝突後の処理機能を備えるために、次の機能を持つ比較回路とアドレス管理回路を備えることで解決できる。比較回路は、ハッシュ値が衝突したとき、ｖａｌｕｅの中を参照してデータを取り出し、取り出したデータとそのｋｅｙとが一致するか否か比較・照合する。アドレス管理回路は、取り出したデータとそのｋｅｙとが一致するとき、ハッシュ値（アドレス）を変更する。
【００８７】
例えば、上記に加えて別のｋｅｙとして“note”を格納するとき、hash(“note”)の結果も００１になってしまったとする。その場合は、すでに＄００１は“book”に使用されているので、別のメタデータアドレスにジャンプする必要がある。そこで例えば、１つ隣のメタデータアドレスへ移動、すなわちアドレスをインクリメントする。図１の例で説明すると、＄００１が衝突したため、＄００２が空いているか調べる。しかし、＄００２もhash(“Blue”)によってすでに使用されているので、さらに次の番地＄００３を調べる。その結果、＄００３が空き番地であれば、そこに“note”に対応するｖａｌｕｅを格納する。
【００８８】
この方法を用いると、ハッシュ値が衝突した場合でもデータの格納は可能となる。ただし、ｋｅｙ−ｖａｌｕｅ型データの検索には工夫が必要である。“note”を検索する場合には、hash(“note”)が００１になると、＄００１のメタデータアドレスを参照するが、すでに格納されていた“book”のｖａｌｕｅが誤って得られてしまう。
【００８９】
そこで、必ずｋｅｙとｖａｌｕｅの対応が正しいかどうか照合する必要がある。“book”のｖａｌｕｅは実データアドレスの＆１０１であるため、＆１０１を参照してデータを読み出す。その先頭データには[book]が保存されているので、“note”のｋｅｙ−ｖａｌｕｅペアではないことが判明する。従って、“note”のｋｅｙ−ｖａｌｕｅペアを探し当てるために、次のメタデータアドレスの＄００２も同様に照合し、“note”のｋｅｙ−ｖａｌｕｅペアではないことが判明する。結果として、次のメタデータアドレスの＄００３が正しいｋｅｙ−ｖａｌｕｅペアであることが判明する。このように、ハッシュ値が衝突した場合でもｋｅｙ−ｖａｌｕｅ型データの検索は可能となる。
【００９０】
なお、実データ部の[book]、[Blue]、[note]はｋｅｙの照合さえできれば良いので、実質的には、bookをbo、BlueをBl、noteをnoというように先頭の数バイト分を切り取って固定長で用いても良い。ただし、この場合も固定長にした場合に衝突の可能性がゼロではなくなるので注意が必要である。
【００９１】
上記では衝突後にアドレスをインクリメントする方法を用いたが、後述する変形例で示されているように、本実施形態を用いれば、ｋｅｙすなわちアドレスが衝突していても、それに対応するｖａｌｕｅから実データアドレスを参照できるため、実データアドレス内にｋｅｙ自体を格納していき、照合するという方式も用いることができる。この場合でも、検索エントリーとしてのｋｅｙと、実データ内のｋｅｙとの照合は必要である。Ｈａｓｈ−ＣＡＭとしてのアドレス管理回路も必要である。従って、方式は多少異なるものの、前述したＨａｓｈ−ＣＡＭと同じ構成で考えれば良い。
【００９２】
以上のように、ハッシュ生成器を用いてハッシュ値（アドレス）を生成し、さらにアドレス管理回路によりハッシュ値の衝突回避の手順をメタデータの保存に加えることにより、メモリシステム１０内で効率的にｋｅｙ−ｖａｌｕｅストア方式を実現することができる。
【００９３】
本実施形態では、Ｈａｓｈ−ＣＡＭを実現するために、ハードウェア機能（固定長データ生成器）を備え、さらに固定長データ（アドレス）の衝突を回避する回路をメモリコントローラ１３が備えている。ここで、ハードウェア機能（固定長データ生成器）はメモリコントローラ１３に備わっていてもよく、その際のｋｅｙ−ｖａｌｕｅ型データの格納は、レジスタメモリ１５内で行われても良いし、直接、第１のメモリブロック１６に対して行われても良い。
【００９４】
なお、上記構成においてｋｅｙ−ｖａｌｕｅストア方式による機能が損なわれなければ、論理アドレス−物理アドレス変換テーブルの一時保存、及びウェアレベリング処理は、メモリシステム１０内部で行うことに限定せず、ホストシステムがＣＰＵとメインメモリを駆使して行っても良い。また、メモリシステム１０が主体的にｋｅｙ−ｖａｌｕｅストア方式を行うために、ダイレクトメモリアクセスコントローラ（ＤＭＡＣ）を備えていても良い。
【００９５】
本実施形態では、各機能ブロック間はバス線で繋がれている。基本的にはメモリシステム内で高速かつ効率的なバス線配置を取られることが望ましいが、例えばチップインターフェース規格と外部インターフェース規格の相違などで、２種類以上のバス線がメモリシステム内で用いられていても良い。
【００９６】
本実施形態よれば、データに関連付けられたメタデータに対するｋｅｙ−ｖａｌｕｅ型データにより、メモリシステムからデータを取り出す処理を簡素かつ高速に行うことができ、かつ、ユーザーはメタデータを任意に扱いつつ、アクセス可能な物理メモリ空間が最大効率で利用可能となるメモリシステムを提供することができる。すなわち、メタデータに対する操作要求をメモリシステムが受け付け、メモリシステム内部のｋｅｙ−ｖａｌｕｅストア方式によって効率的かつ高速に処理し、出力することができるメモリシステムを提供できる。
【００９７】
［第２実施形態］
本実施形態は、第１実施形態とハードウェア構成の一部が異なり、ｋｅｙ照合専用メモリ空間を有するハードウェアＣＡＭを備える。
【００９８】
図５は、第２実施形態のメモリシステムのハードウェア構成を示すブロック図である。  
メモリコントローラ１３は、ローカルコントローラ１２と第１のメモリブロック１６との間の相互の信号送受信を制御する。また、第１のメモリブロック１６に対する書き込み／読み出し時のためのレジスタメモリ１５を有している。検索要求をこのレジスタメモリ１５に一時的に保存し、読み出しの一致判定を行うことができる。バイト単位での並列読み出しと一致判定を行い、任意長の検索データに関しては逐次処理を行うことで一致判定が可能である。
【００９９】
本実施形態では、図５に示すように、メモリコントローラ１３からアクセス可能な位置にコンテンツ連想メモリ（ＣＡＭ：Content-Addressable Memory）２４が配置されている。コンテンツ連想メモリ（ＣＡＭ）とは、アドレスの入力に対してそのアドレスが指定するデータを出力する通常メモリとは異なり、検索データの入力に対して、その検索データと全ての格納データとの一致・不一致の比較演算を同時並列に行い、一致した格納データのアドレスを出力する機能を持つ高速検索用途の特殊メモリである。ここでは、ＣＡＭ２４は、ｋｅｙの入力に対して、ｋｅｙ−ｖａｌｕｅ型データが記憶されたアドレスを取得するアドレス取得回路として機能する。また、ＣＡＭは、データの一致検索に対して、一致データの有無を“Match Flag”として出力することができる。本実施形態では、ＣＡＭ２４はこれらの機能を実現するための電子回路で実現されているため、ハードウェアＣＡＭと呼んでいる。
【０１００】
このハードウェアＣＡＭは、レジスタメモリ１５に直結されていて、メモリコントローラ１３とレジスタメモリ１５との間に配置されている。なおここでは、メモリコントローラ１３とＣＡＭ２４が個別に形成された例を示したが、メモリコントローラ１３がＣＡＭ２４を含んでいてもよい。
【０１０１】
さらに、第１のメモリブロック１６はＲＡＭ（random access memory）であるため、ＣＡＭ２４と第１のメモリブロック１６によりＣＡＭ−ＲＡＭとして機能する。ＣＡＭ−ＲＡＭとは、前述したＣＡＭ２４でアドレスを出力させ、アドレス指定アクセスのＲＡＭでデータを出力させるように組み合わせたシステムである。ＣＡＭの１つのエントリとＲＡＭの１つのエントリとが一対一対応するように、ＣＡＭのアドレスデコーダとＲＡＭのアドレスエンコーダが設計されている。
【０１０２】
本実施形態において、ｋｅｙをＣＡＭ２４に格納し、それに対応する値（ｖａｌｕｅ）の組を第１のメモリブロック１６に保存すること、あるいは、第１のメモリブロック１６から値（ｖａｌｕｅ）をレジスタメモリ１５に読み出して、ＲＡＭ部として保存することにより、ＣＡＭ−ＲＡＭとして機能する。
【０１０３】
ハードウェアＣＡＭを用いるには、第１のメモリブロック１６内からメタデータテーブルがレジスタメモリ１５に転送されている必要がある。このようなＣＡＭ−ＲＡＭを用いれば、第１実施形態におけるＨａｓｈ−ＣＡＭのような、アドレスの衝突が原理的に起こらない。
【０１０４】
従って、ｋｅｙとｖａｌｕｅの照合手続きと検索やり直しが発生することがないため、検索がより高速になる。また、Ｈａｓｈ−ＣＡＭでは衝突回避の手段として、メタデータアドレスに余裕を持たせる場合が多いが、ハードウェアＣＡＭの場合は衝突が無いためＣＡＭ２４を効率良く利用することができる。
【０１０５】
本実施形態では、ＣＡＭ２４がｋｅｙ−ｖａｌｕｅ型データのｋｅｙ検索にのみ用いられるため、ＣＡＭがデータ入出力のページレジスタ（レジスタメモリ）に接続されていることにより、第１のメモリブロックの物理アドレス空間を、ｋｅｙ−ｖａｌｕｅ型データのために一部占有させることなく、最大限に利用することが可能となる。その他の構成及び効果は前述した第１実施形態と同様である。
【０１０６】
［第３の実施形態］
本実施形態は、第２実施形態と同様に、ｋｅｙ照合専用メモリ空間を有するハードウェアＣＡＭを備えるが、第１のメモリブロック１６がハードウェアＣＡＭを備えている。
【０１０７】
図６は、第３実施形態のメモリシステムのハードウェア構成を示すブロック図である。  
図示するように、第１のメモリブロック１６は、実データ領域１６１、及びメタデータテーブルを格納するＣＡＭ−ＲＡＭ１６３を有する。ＣＡＭ−ＲＡＭの使われ方は、第２実施形態と同様であるが、本実施形態においては、第１のメモリブロック１６の一部がＣＡＭ専用のアドレス空間である。このため、メタデータテーブルのｋｅｙを第１のメモリブロック１６の外へ移動させることなく、直接保存されているｋｅｙの検索が可能となる。
【０１０８】
また、第１のメモリブロック１６の記憶セル部に対する照合データの与え方を工夫することで、完全並列検索を行うことが可能である。例えば、第１のメモリブロック１６がＮＡＮＤフラッシュメモリで構成されている場合、ＣＡＭ部に使用する領域は、すべてのゲートに同時に検索データとしての入力を与えられるように、読み出し回路を構成しておく。これにより、検索がヒットしたＮＡＮＤストリングのみ出力が検知されるようにでき、その出力とＲＡＭ部のページアドレスを対応させておけば、ＣＡＭ−ＲＡＭが実現される。その他の構成及び効果は前述した第１実施形態と同様である。
【０１０９】
［第４の実施形態］
本実施形態は、第１実施形態と同様に、固定長データ生成器（例えば、ハッシュ生成器）を備えるが、第１実施形態とは固定長データ生成器の設置場所が異なり、ローカルコントローラ１２が固定長データ生成器１４を備えている。
【０１１０】
図７は、第４実施形態のメモリシステムのハードウェア構成を示すブロック図である。  
図示するように、固定長データ生成器１４はローカルコントローラ１２内に配置されている。必ずしも、固定長データ生成器１４とローカルコントローラ１２とは、物理的に同チップ内にある必要は無い。ローカルコントローラ１２が他の機能ブロックと比べて容易に、固定長データ生成器１４にアクセス可能な位置にあれば良い。
【０１１１】
ローカルコントローラ１２は、第２のメモリブロックとしてのバッファメモリ１２１を含む。このため、ローカルコントローラ１２は、第１のメモリブロック１６より読み出した論理アドレス−物理アドレス変換テーブルをバッファメモリ１２１内に格納して、論理アドレス−物理アドレス変換を行うことができる。同様に、ＮＡＮＤフラッシュのウェアレベリング処理を行うこともできる。さらに、ローカルコントローラ１２は、メタデータテーブル１６２と論理アドレスの対応を管理することができる。
【０１１２】
本実施形態の特徴として、固定長データ生成器１４がローカルコントローラ１２内にあるため、論理アドレス−物理アドレス変換の際に、ｋｅｙのハッシュ値化とｖａｌｕｅへの対応付け、すなわちメタデータテーブル１６２のｋｅｙ−ｖａｌｕｅ型データの作成がローカルコントローラ１２内で効率的に行うことができる。
【０１１３】
本実施形態では、Ｈａｓｈ−ＣＡＭを第２のメモリブロックであるバッファメモリ１２１で行う方法、第１のメモリブロック１６で行う方法の２通りを用いることができる。後者は実施形態１と同様なので説明を省略し、前者について以下説明する。
【０１１４】
メタデータテーブルを作成する際には、第１のメモリブロック１６からデータを読み出してバッファメモリ１２１内に格納してハッシュ値化する。Ｈａｓｈ−ＣＡＭをバッファメモリ１２１内で行うので、メタデータアドレスはバッファメモリ１２１の物理アドレスに対応させておく。
【０１１５】
作成したメタデータテーブルは第１のメモリブロック１６に書き戻すか、第２のメモリブロックであるバッファメモリ１２１に保持しておく。これにより、メタデータテーブルに対してｋｅｙ−ｖａｌｕｅ型データの参照を行うことができる。
【０１１６】
メタデータテーブルがバッファメモリ１２１のサイズに比べて小さい場合は、第１のメモリブロック１６よりも高速なバッファメモリ１２１内でｋｅｙ−ｖａｌｕｅ型データの参照を行うことができるため、検索がより高速になる。
【０１１７】
さらに、バッファメモリ１２１が不揮発性のＲＡＭの場合は、メタデータを第１のメモリブロック１６に書き戻すことなく、メモリシステムの電源をオフにすることができる。再び電源をオンにした後でも、メタデータテーブルはバッファメモリ１２１に保存されているので、第１のメモリブロック１６から読み出す処理は必要ない。このため、結果として全体的な速度向上が得られる。その他の構成及び効果は前述した第１実施形態と同様である。
【０１１８】
本実施形態では、Ｈａｓｈ−ＣＡＭに必要な機能がローカルコントローラ付近に備わっているが、必ずしもＨａｓｈ−ＣＡＭはバッファメモリに対して行われる必要はなく、第１実施形態と同様に第１のメモリブロックに対して行われても良い。メタデータテーブルが小さい場合はバッファメモリテーブルにすべて読み出してからＨａｓｈ−ＣＡＭを行う方が高速だが、メタデータテーブルがバッファメモリサイズよりも大きい場合、直接第１のメモリブロックに対してＨａｓｈ−ＣＡＭ動作を行った方が高速になる場合もある。
【０１１９】
［第５の実施形態］
本実施形態は、第４実施形態と同様に、第２のメモリブロックであるバッファメモリ１２１でｋｅｙ−ｖａｌｕｅ型データの参照を行うが、ローカルコントローラ１２がハードウェアＣＡＭを備えている。
【０１２０】
図８は、第５実施形態のメモリシステムのハードウェア構成を示すブロック図である。  
図示するように、バッファメモリ１２１にＣＡＭ１２２が接続されている。図ではバッファメモリ１２１とＣＡＭ１２２とが区別して書かれているが、これらが物理的に結合していても良い。
【０１２１】
ＣＡＭ１２２の出力（ヒット信号）はバッファメモリ１２１の一部分（例えば、半分程度のメモリ容量）と直接接続されており、ＣＡＭ１２２とバッファメモリ１２１の一部分とでＣＡＭ−ＲＡＭが構成されている。このため、データ（コンテンツ）指定によるデータの読み出しが可能となっている。
【０１２２】
ハードウェアＣＡＭ１２２を用いることで、Ｈａｓｈ−ＣＡＭのようなアドレスの衝突が原理的に起こらない。このため、ｋｅｙとｖａｌｕｅの照合手続きと検索やり直しが発生することがないので、検索がより高速になる。
【０１２３】
さらに、バッファメモリ１２１はアクセス性能が高い反面、メモリ容量が第１のメモリブロック１６よりも小さいので、効率的なメモリ空間の運用が求められる。本実施形態では、ＣＡＭ１２２を追加することにより、バッファメモリ１２１のメモリ空間は最大効率で利用可能となる。その他の構成及び効果は前述した第２実施形態と同様である。
【０１２４】
［第６の実施形態］
本実施形態は、第１実施形態とほぼ同様のハードウェア構成を取るが、メモリシステム１０内にローカルコントローラが存在しない点で異なる。
【０１２５】
図９は、第６実施形態のメモリシステムのハードウェア構成を示すブロック図である。  
図示するように、ホストインターフェース１１が直接、メモリコントローラ１３へ接続されている。
【０１２６】
ｋｅｙ−ｖａｌｕｅストア方式の実現方法は第１実施形態と同様であるが、論理アドレス−物理アドレス変換テーブルの取り扱いが異なる。ローカルコントローラおよび第２のメモリブロックがメモリシステム１０内に存在しないため、論理アドレス−物理アドレス変換テーブルは、第１のメモリブロック１６から読み出されて、メモリシステム１０の外部、例えばメインメモリ１０２内で取り扱われる。
【０１２７】
Ｈａｓｈ−ＣＡＭは第１実施形態と同様にメモリコントローラ１３内で固定長データ生成器１４を駆使して行われるため、メタデータテーブル１６２でのｋｅｙ−ｖａｌｕｅ型データの格納はメモリシステム１０内で行われる。ｋｅｙ−ｖａｌｕｅ型データだけではなく、メタデータテーブル１６２の変更点もホストシステムに返され、論理アドレス−物理アドレス変換テーブルに反映された後に、適宜、第１のメモリブロック１６へ書き戻される。
【０１２８】
本実施形態では、メモリシステム１０内部にバッファメモリやローカルコントローラを持たず、機能を簡素化しているため、メモリシステム自体はコンパクトになる。
【０１２９】
なお、メモリシステム１０が主体的にｋｅｙ−ｖａｌｕｅストア方式を実行するために、ダイレクトメモリアクセスコントローラ（ＤＭＡＣ）を備え、メモリシステム１０とメインメモリ１０２との間のデータ転送をＤＭＡＣが制御しても良い。その他の構成及び効果は前述した第１実施形態と同様である。
【０１３０】
［第７の実施形態］
本実施形態は、第２実施形態とほぼ同様のハードウェア構成を取るが、メモリシステム１０内にローカルコントローラが存在しない点で異なる。
【０１３１】
図１０は、第７実施形態のメモリシステムのハードウェア構成を示すブロック図である。  
ハードウェアＣＡＭによるｋｅｙ−ｖａｌｕｅストア方式の実現方法は第２実施形態と同様であり、ローカルコントローラがないことによる機能の特徴は第６の実施形態と同様であるため、説明を省略する。
【０１３２】
［第８の実施形態］
本実施形態は、第３実施形態とほぼ同様のハードウェア構成を取るが、メモリシステム１０内にローカルコントローラが存在しない点で異なる。
【０１３３】
図１１は、第８実施形態のメモリシステムのハードウェア構成を示すブロック図である。  
ＣＡＭ−ＲＡＭによるｋｅｙ−ｖａｌｕｅストア方式の実現方法は第３の実施形態と同様であり、ローカルコントローラがないことによる機能の特徴は第６実施形態と同様であるため、説明を省略する。
【０１３４】
以上のように、本実施形態では、ｋｅｙ−ｖａｌｕｅストア方式の仕組みをメタデータとそのテーブル、及び検索器としてのハッシュ生成器（Ｈａｓｈ−ＣＡＭ）、ハードウェアＣＡＭ（ＣＡＭ−ＲＡＭ）で実現する。
【０１３５】
前述した第１から第８実施形態を用いて、ｋｅｙ−ｖａｌｕｅストア方式が実現される場合、さらに、以下のような変形例を取ることが可能であり、以下に具体的に示す。なお、本出願の本旨としては変形例よりも上記実施形態が優先的に解釈される。
【０１３６】
［変形例１］
図１２は、変形例１における第１のメモリブロック１６内の実データ領域１６１とメタデータテーブル１６２との関係、及びｋｅｙ−ｖａｌｕeストア方式の仕組みを模式的に示す図である。
【０１３７】
図１２に示す実データ領域１６１では、実データアドレスに、データファイルと、そのファイルに対応するファイル名あるいはファイルＩＤと、ファイルから抽出したｋｅｙと、ｋｅｙが格納されたメタデータアドレスとが格納されている。このような保存の方法は、ホストシステムからの命令で行うことができるほか、メモリシステム１０に予めｋｅｙ抽出機能とメタデータアドレス割り当て機能が備わっていれば実現できる。
【０１３８】
メタデータテーブル１６２には、実データアドレスにファイルを保存する際に抽出されたｋｅｙと、ｋｅｙに対応するｖａｌｕｅとして、ｋｅｙが存在する実データアドレスと、ｋｅｙと関連付けられる別のｋｅｙ−ｖａｌｕｅ型データが保存されたメタデータアドレスとが保存されている。
【０１３９】
このようなアドレス管理により、ローカルコントローラ１２あるいはメモリコントローラ１３がｋｅｙ検索要求を指示したとき、メモリコントローラ１３はメタデータアドレスからｋｅｙを検索する。
【０１４０】
例えば、“book”を含むファイル名を得たいとき、まずメタデータアドレスから“book”を検索する。“book”はメタデータアドレス＄００２に格納されている。このメタデータアドレス＄００２から、ｖａｌｕｅとして実アドレスの＆００１、＆００２と、メタデータアドレスの＄０１１、＄０１２が得られる。
【０１４１】
ここで、検索結果として実アドレスを返すことができる。さらに、ｖａｌｕｅのメタデータアドレスをたどることで、“book”が所属する集合名をたどることができる。例えば、＄０１１では、“a-file.txt”というｋｅｙとそれに対するｖａｌｕｅの実データアドレス、メタデータアドレスを得ることができる。
【０１４２】
このように、メタデータテーブル１６２を連続してたどり、検索結果として求めていた値（実データ）を得ることができる。本変形例では、メタデータテーブルに存在するのはｋｅｙのみであって、実際のｋｅｙは実データ領域１６１の実アドレスに格納されている。
【０１４３】
［変形例２］
図１３は、変形例２における第１のメモリブロック１６内の実データ領域１６１とメタデータテーブル１６２との関係、及びｋｅｙ−ｖａｌｕeストア方式の仕組みを模式的に示す図である。
【０１４４】
図１３に示す実データ領域１６１では、実データアドレスに、ファイルと、そのファイルに対応するファイル名あるいはファイルＩＤが格納されている。メタデータテーブル１６２には、ファイルから抽出されたｋｅｙと、それに対応するｖａｌｕｅとしてのｋｅｙが存在する実アドレスと、ｋｅｙに関連付けられた別集合あるいは要素を保存するメタデータアドレスが格納されている。
【０１４５】
変形例１と同様に、ローカルコントローラ１２あるいはメモリコントローラ１３がｋｅｙ検索要求を指示したとき、メモリコントローラ１３はメタデータアドレスからｋｅｙを検索する。
【０１４６】
例えば、“book”を含むファイル名を得たいとき、まずメタデータアドレスから“book”を検索する。“book”はメタデータアドレス＄００２に格納されている。このメタデータアドレス＄００２から、ｖａｌｕｅとして実データアドレスの＆０１１と、メタデータアドレスの＄０１１、＄０１２が得られる。
【０１４７】
ここで、実データアドレスは“book”が所属するファイルの保管場所ではなく、ｋｅｙの実データアドレス中の保存場所を示している。一方、ｖａｌｕｅのメタデータアドレスは“book”が所属する集合を示す。このため、メタデータアドレスをたどり、＄０１１、＄０１２のそれぞれのｖａｌｕｅの実データアドレスが得られて、これらを検索結果として返すか、あるいは実データアドレスをたどって＆００１、＆００２のデータを返すことになる。変形例２は、変形例１よりも実データ領域（実アドレス空間）１６１の一つのアドレスあたりのデータ量が少ないという利点がある。
【０１４８】
［変形例３］
図１４は、変形例３における第１のメモリブロック１６内の実データ領域１６１とメタデータテーブル１６２との関係、及びｋｅｙ−ｖａｌｕeストア方式の仕組みを模式的に示す図である。
【０１４９】
本変形例では、メタデータの実態が実データ領域１６１の実データアドレスに保管されていることを示す。
【０１５０】
図１４に示す実データ領域１６１では、実データアドレスに、ファイルと、そのファイルに対応するファイル名あるいはファイルＩＤと、さらにｋｅｙのメタデータアドレスとが格納されている。
【０１５１】
メタデータテーブル１６２では、メタデータアドレスに、ファイルから抽出されたｋｅｙと、それに対応するｖａｌｕｅとしてのｋｅｙが存在する実データアドレスが格納されている。また、メタデータアドレスに対応する物理アドレスが示されている。
【０１５２】
このように、メタデータアドレスが実データアドレスと別の物理アドレス空間に割り当てられている場合、メタデータアドレスと物理アドレスの対応表は第１のメモリブロック１６に保存されており、メモリシステム（ローカルシステム）あるいはホストシステムがその対応表を呼び出して使用する。
【０１５３】
また、メタデータテーブル内のｋｅｙ検索の方法と、連続したアドレスにｖａｌｕｅが保管されている例を示す。
【０１５４】
メタデータテーブル１６２内のｋｅｙ−ｖａｌｕｅ型データは、図１５に示すように、実現することも可能である。メタデータアドレス空間は、第１のメモリブロック１６の特定の物理アドレス空間に対応しているものとする。連続したメタデータアドレスの被検索領域を、Ｓｌｏｔという単位で区切るものとする。Ｓｌｏｔ内の先頭領域にはｋｅｙが格納されている。
【０１５５】
図１５に示す例では、“ｐｅｎ”というｋｅｙを検索する。ｋｅｙは一文字ずつメモリコントローラ１３が与え、Ｓｌｏｔ全体を検索する。この例でのｋｅｙ検索の仕組みには、実施形態で示したメモリコントローラ１３、レジスタメモリ１５におけるハードウェアＣＡＭが用いられる。
【０１５６】
“ｐｅｎ”のうち最初の“ｐ”が得られたＳｌｏｔは、一致フラグを立てておき、そのＳｌｏｔは次に“e”を検索する。連続してヒットした場合、同様にフラグを立てて次を検索するという操作を継続する。そうして、図１５では、＃００３と＃１０２でｋｅｙの一致が得られ、そのＳｌｏｔでそのまま連続して読み出すとｖａｌｕｅが得られる。ｋｅｙとｖａｌｕｅの区切りには、制御コードが挿入されているので区別できるものとする。
【０１５７】
また、これを拡張すると、don‘t care マスクビットを与えた検索を行うこともできる。
【０１５８】
［変形例４］
本変形例では、固定長のｋｅｙを格納したｋｅｙ−ｖａｌｕｅ型データと、それによる全文検索を例として示す。
【０１５９】
固定長ビットの必要性は、検索方式に依存する。全文検索方式は（１）逐次検索、（２）索引検索の２つに大別される。さらに、索引作成（インデクシング）の方法で分類でき、（ａ）形態素解析、（ｂ）Ｎ−ｇｒａｍ、（ｃ）接尾辞法、が知られている。
【０１６０】
これらのうち、形態素解析は、予め用意された辞書内に存在する単語を抽出する方法である。Ｎ−ｇｒａｍは、辞書を用意する必要がなく、単語をＮ個の要素に分割し、任意の文字列が検索できる。例えば検索対象の集合をＳとすると、Ｓの分割の仕方が１文字ずつならｕｎｉ−ｇｒａｍ、２文字ずつならｂｉ−ｇｒａｍ、Ｎ文字ずつならＮ−ｇｒａｍとなる。例えば、Ｓ＝ｉｎｎｏｖａｔｉｏｎを分解すると、ｂｉ−ｇｒａｍなら、その分割要素（トークン）がａｔ, ｉｎ, ｉｏ, ｎｎ, ｎｏ, ｎ, ｏｎ, ｏｖ, ｔｉ, ｖａ となる。接尾辞法は、任意長を扱うが索引ファイルの圧縮に向いている。
【０１６１】
図１６に示す実データ領域１６１では、実データアドレスに、ファイルと、そのファイルに対応するファイル名あるいはファイルＩＤとが格納されている。メタデータテーブル１６２では、メタデータアドレスに、ファイルからＮ−ｇｒａｍ方式で抽出されたｋｅｙが格納されている。
【０１６２】
この例では、メタデータのｋｅｙは、実データアドレスに保存されている“ｉｎｎｏｖａｔｉｏｎ”から分解抽出したｂｉ−ｇｒａｍである。ｋｅｙに対応するｖａｌｕｅとして実アドレスが示され、ｂｉ−ｇｒａｍでファイルから抽出された際のファイル中の出現位置（ｐｏｓｉｔｉｏｎ）がペアで格納されている。ｂｉ−ｇｒａｍでの検索は、ｋｅｙを検索したあとはｋｅｙの出現回数でソートし、そのファイル中の位置情報を比較して連続したキーワードであることを確認し、所望の検索語の集合を求める。
【０１６３】
ここで、ｋｅｙが固定長であるため、そのままハッシュ化してｋｅｙ−ｖａｌｕｅ型データを構成することができる。図１６の例では、“ａｔ”、“ｉｎ”、がその順でメタデータアドレスにそれぞれ格納されている。実際は、Ｎ−ｇｒａｍトークンを、ＡＳＣＩＩやＵＴＦ−６などのコードにてビット列で表し、それを短縮してメタデータアドレスとしても良い。
【０１６４】
このように、本実施形態によるｋｅｙ−ｖａｌｕｅストア方式は固定長を扱うＮ−ｇｒａｍと相性が良く、高速なインデクシングに向いている。全文検索では、検索は速いがインデクシングに時間がかる。インデクシングは、要素と集合であるメタデータテーブルを適宜読み出し、追加・更新・削除が必要な要素の検索と、その集合の編集を行う。このため、ファイルアクセスが頻発することになるため、本実施形態のメモリシステムを用いることで、メモリシステム内での効率的なｋｅｙ−ｖａｌｕｅストア方式の実現によって、ホストシステムに負荷をかけず、高速にインデクシングを行うことも可能となる。
【０１６５】
本実施形態においては、メモリシステムにおけるｋｅｙ−ｖａｌｕｅストア方式の有用性を示す例として、度々、全文検索の手順で説明したが、本実施形態は必ずしも全文検索に特化した技術ではない。
【０１６６】
本実施形態は、メモリシステムにデータを格納する際の、メタデータを効率的に管理するために、ｋｅｙ−ｖａｌｕｅストア方式の仕組みとその具体的構成を提供するものである。
【０１６７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１６８】
１０…メモリシステム（またはローカルシステム）、１１…ホストインターフェース、１２…ローカルコントローラ、１３…メモリコントローラ（あるいはチップコントローラ）、１４…固定長データ生成器、１５…レジスタメモリ（あるいはキャッシュメモリ）、１６…第１のメモリブロック、２４…コンテンツ連想メモリ（ＣＡＭ）、１０１…ＣＰＵ、１０２…メインメモリ、１２１…バッファメモリ、１２２…ＣＡＭ−ＲＡＭ、１６１…実データ領域（実アドレス空間）、１６２…メタデータテーブル、１６３…ＣＡＭ−ＲＡＭ。
【図１】
0005646775.tif 000002
【図２】
0005646775.tif 000003
【図３Ａ】
0005646775.tif 000004
【図３Ｂ】
0005646775.tif 000005
【図３Ｃ】
0005646775.tif 000006
【図３Ｄ】
0005646775.tif 000007
【図４】
0005646775.tif 000008
【図５】
0005646775.tif 000009
【図６】
0005646775.tif 000010
【図７】
0005646775.tif 000011
【図８】
0005646775.tif 000012
【図９】
0005646775.tif 000013
【図１０】
0005646775.tif 000014
【図１１】
0005646775.tif 000015
【図１２】
0005646775.tif 000016
【図１３】
0005646775.tif 000017
【図１４】
0005646775.tif 000018
【図１５】
0005646775.tif 000019
【図１６】
0005646775.tif 000020