(57)【特許請求の範囲】
【請求項１】
受け付けられた第１のキーと、不揮発性メモリから読み出された第２のキーとを比較する第１の比較部と、
前記第１の比較部による第１の比較結果に基づいて誤り訂正可能か判断する判断部と、
前記判断部によって誤り訂正可能と判断された場合に、前記第２のキーに対して誤り訂正を実行する訂正部と、
前記第１のキーと、前記訂正部によって誤り訂正された前記第２のキーとを比較する第２の比較部と、
前記第２の比較部による第２の比較結果が整合する場合に、前記不揮発性メモリにおいて前記第２のキーに対応付けられているデータを読み出す検索部と、
を具備する検索装置。
【請求項２】
前記第１の比較部は、前記判断部によって誤り訂正可能でないと判断された場合に、又は、前記第２の比較結果が整合しない場合に、前記第１のキーと、前記不揮発性メモリから読み出された次の第２のキーとを比較し、
前記判断部は、前記第１のキーと前記次の第２のキーとの比較結果に基づいて誤り訂正可能か判断し、
前記訂正部は、前記第１のキーと前記次の第２のキーとの比較結果に基づいて誤り訂正可能と判断された場合に、前記次の第２のキーに対して前記誤り訂正を実行し、
前記第２の比較部は、前記第１のキーと、前記訂正部によって誤り訂正された前記次の第２のキーとを比較し、
前記検索部は、前記第１のキーと前記誤り訂正された次の第２のキーとが整合する場合に、前記不揮発性メモリにおいて前記次の第２のキーに対応付けられているデータを読み出す、
請求項１に記載の検索装置。
【請求項３】
前記第１の比較部は、前記第１のキーと前記第２のキーとに基づいてハミング距離を算出し、
前記判断部は、前記ハミング距離が誤り訂正可能な範囲か判断する、
請求項１又は請求項２に記載の検索装置。
【請求項４】
前記不揮発性メモリから前記第１のキーに対応する全ての候補キーが読み出されたが前記不揮発性メモリから前記第１のキーに対応するデータが読み出されなかった場合に、前記第１のキーに対応する前記データが前記不揮発性メモリにないことを示す信号を外部に送信する送信部をさらに具備する、請求項１乃至請求項３のいずれか１項に記載の検索装置。
【請求項５】
前記訂正部は、前記検索部によって読み出された前記データを誤り訂正する、請求項１乃至請求項４のいずれか１項に記載の検索装置。
【請求項６】
前記訂正部は、ＥＣＣ（Error Correcting Code）に基づいて前記第２のキーを誤り訂正する、請求項１乃至請求項５のいずれか１項に記載の検索装置。
【請求項７】
前記第１の比較部は、前記不揮発性メモリに対する書き込み及び読み出しを制御するメモリコントローラに備えられている、請求項１乃至請求項６のいずれか１項に記載の検索装置。
【請求項８】
前記第１の比較部は、前記不揮発性メモリに備えられる、請求項１乃至請求項７のいずれか１項に記載の検索装置。
【請求項９】
前記検索部はキー・バリュー型検索を実行する、請求項１乃至請求項８のいずれか１項に記載の検索装置。
【請求項１０】
前記不揮発性メモリは、ＮＡＮＤ型フラッシュメモリである、請求項１乃至請求項９のいずれか１項に記載の検索装置。
【請求項１１】
受け付けられた第１のキーが不揮発性メモリから読み出された第２のキーの誤り訂正可能な範囲内か判断する判断部と、
前記第１のキーが前記第２のキーの誤り訂正可能な範囲内と判断された場合に、前記第２のキーに対して誤り訂正を実行する訂正部と、
前記第１のキーと、誤り訂正された前記第２のキーとが整合する場合に、前記不揮発性メモリにおいて前記第２のキーに対応付けられているデータを読み出す検索部と、
を具備する検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、検索装置に関する。
【背景技術】
【０００２】
キー・バリュー型検索を実行するメモリ装置においては、検索時間の短縮が求められる。そのため、キー・バリュー型検索を実行するメモリ装置として、高速にアクセス可能なソリッドステートドライブ（ＳＳＤ）が用いられる。ＳＳＤは、例えば、ＮＡＮＤ型フラッシュメモリなどのような不揮発性メモリを備える。ＮＡＮＤ型フラッシュメモリは、複数のブロック（物理ブロック）を備える。複数のブロックは、ワード線とビット線との交点に配置される複数のメモリセルを含む。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１２−８６５１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本実施形態は、検索時間を短縮可能な検索装置を提供する。
【課題を解決するための手段】
【０００５】
本実施形態によれば、検索装置は、第１の比較部と、判断部と、第２の比較部と、検索部とを含む。第１の比較部は、受け付けられた第１のキーと、不揮発性メモリから読み出された第２のキーとを比較する。判断部は、第１の比較部による第１の比較結果に基づいて誤り訂正可能か判断する。訂正部は、判断部によって誤り訂正可能と判断された場合に、第２のキーに対して誤り訂正を実行する。第２の比較部は、第１のキーと、訂正部によって誤り訂正された第２のキーとを比較する。検索部は、第２の比較部による第２の比較結果が整合する場合に、不揮発性メモリにおいて第２のキーに対応付けられているデータを読み出す。
【図面の簡単な説明】
【０００６】
【図１】第１の実施形態に係るメモリ装置を備える情報処理システムの一例を示すブロック図。
【図２】第１の実施形態に係るメモリ装置の処理の一例を示すフローチャート。
【図３】第１の実施形態に係る読み出されたキーを格納するメモリと比較部と不揮発性メモリとの関係の一例を示す回路図。
【図４】第２の実施形態に係るメモリ装置を備える情報処理システムの一例を示すブロック図。
【図５】第２の実施形態に係る比較部と不揮発性メモリのメモリセルとの関係の一例を示す回路図。
【図６】第３の実施形態に係る情報処理システムの詳細構成の一例を示すブロック図。
【図７】第３の実施形態に係るストレージシステムの一例を示す斜視図。
【発明を実施するための形態】
【０００７】
以下、図面を参照して実施形態について説明する。以下の説明において、略同一の機能及び構成要素については、同一符号を付し、重複説明は必要な場合にのみ行う。
【０００８】
［第１の実施形態］
本実施形態においては、メモリ装置に備えられている検索装置について説明する。メモリ装置は、不揮発性メモリを備えている。
【０００９】
本実施形態において、不揮発性メモリはＮＡＮＤ型フラッシュメモリであり、メモリ装置は、ＳＳＤの場合について説明する。しかしながら、不揮発性メモリは、ＮＯＲ型フラッシュメモリ、ＭＲＡＭ（Magnetoresistive Random access memory：磁気抵抗メモリ）、ＰＲＡＭ（Phase change Random access memory：相変化メモリ）、ＲｅＲＡＭ（Resistive Random access memory：抵抗変化型メモリ）、ＦｅＲＡＭ（Ferroelectric Random Access Memory）などの不揮発性メモリでもよい。また、メモリ装置の一部又は全部は、ハードディスクドライブ（ＨＤＤ）でもよい。
【００１０】
本実施形態において、不揮発性メモリから読み出されたデータには誤りが含まれる場合があるとする。
【００１１】
本実施形態において、アクセスとは、記憶装置へデータを書き込むこと、及び、記憶装置からデータを読み出すことの双方を意味する。
【００１２】
図１は、本実施形態に係るＳＳＤを備える情報処理システムの一例を示すブロック図である。
【００１３】
情報処理システム１は、情報処理装置２とメモリ装置の一例であるＳＳＤ３とを含む。情報処理装置２は、ＳＳＤ３に対応するホスト装置でもよい。
【００１４】
情報処理装置２は、ＳＳＤ３にキーＫI（第１のキー）を送信し、ＳＳＤ３から、キーＫIに対応するデータ（以下、バリューという）ＶC、又は、キーＫIに対応するバリューがＳＳＤ３の不揮発性メモリ９にないことを示す信号Ｓを受信する。
【００１５】
ＳＳＤ３は、情報処理装置２からキーＫIを受信し、キーＫIに対応するバリューＶC又は信号Ｓを情報処理装置２へ送信する。ＳＳＤ３は、情報処理装置２に内蔵されてもよく、情報処理装置２とＳＳＤ３とは、ネットワークなどを経由して通信可能に接続されてもよい。
【００１６】
ＳＳＤ３は、Ｉ／Ｏインタフェース４、プロセッサ５、メモリ６、誤り訂正部７、メモリコントローラ８、不揮発性メモリ９を備える。
【００１７】
Ｉ／Ｏインタフェース４は、例えば情報処理装置２などのような外部装置との間で、データ、情報、信号、コマンドなどの送信及び受信を行う。
【００１８】
プロセッサ５は、プロセッサ５内のメモリに格納されているプログラム、メモリ６に格納されているプログラム、又は、不揮発性メモリ９に格納されているプログラムを実行することにより、受信部５１、読み出し部５２、判断部５３、比較部５４、検索部５５、送信部５６として機能する。
【００１９】
本実施形態において、プロセッサ５を、受信部５１、読み出し部５２、判断部５３、比較部（第２の比較部）５４、検索部５５、送信部５６として機能させるためのプログラムは、例えば、ミドルウェア、ファームウェア、アプリケーションプログラム、又は、オペレーティングシステム（ＯＳ）でもよい。本実施形態において、受信部５１、読み出し部５２、判断部５３、比較部５４、検索部５５、送信部５６のうちの一部又は全部は、ハードウェアにより実装されてもよい。
【００２０】
メモリ６は、例えばプロセッサ５による処理対象のプログラム、データ、情報などを格納し、作業用メモリとして利用される。メモリ６は、例えばＤＲＡＭ（Dynamic Random Access Memory）又はＳＲＡＭ（Static Random Access Memory）などのような揮発性メモリでもよく、不揮発性メモリでもよい。
【００２１】
メモリコントローラ８は、不揮発性メモリ９に対するアクセスを制御する。本実施形態において、メモリコントローラ８は、メモリ８１、比較部８２を備える。メモリコントローラ８に備えられている比較部８２の一部又は全部は、ハードウェアで実装されてもよく、又は、ソフトウェアで実装されてもよい。比較部８２は、メモリコントローラ８の外に配置されてもよく、例えば不揮発性メモリ９に備えられてもよい。
【００２２】
不揮発性メモリ９は、候補キーであるキーＫ1，Ｋ2，…，ＫNと、キーＫ1，Ｋ2，…，ＫNのそれぞれに対応付けられているアドレスＡ1，バリューＶ2，…，アドレスＡNと、アドレスＡ1，…，アドレスＡNによって示される位置に配置されているバリューＶ1，…，ＶNを格納する。
【００２３】
本実施形態において、キーＫ1，ＫNは、アドレスＡ1，ＡNを用いてバリューＶ1，ＶNを参照可能である。キーＫ2は、アドレスを用いることなく、直接的にバリューＶ2を参照可能である。
【００２４】
受信部５１は、情報処理装置２からＩ／Ｏインタフェース４経由でキーＫIを受信し、受信されたキーＫIをメモリ６に書き込む。
【００２５】
本実施形態においては、キーＫIは、外部の情報処理装置２からＳＳＤ３によって受信されたキーとしている。しかしながら、キーＫIは、ＳＳＤ３の内部の処理によって発生されたキーであり、受信部５１は、そのＳＳＤ３の内部の処理によって発生されたキーを受け付ける受付部であってもよい。
【００２６】
読み出し部５２は、候補キーのうちの未確認のキーをメモリコントローラ８を用いて不揮発性メモリ９から読み出し、読み出されたキーＫR（第２のキー）をメモリ８１に書き込む。読み出し部５２は、例えば２分探索に基づいて候補キーから未確認のキーを読み出す。
【００２７】
メモリ８１は、例えば、レジスタ又はバッファであり、不揮発性メモリ９から読み出されたキーＫRを格納する。
【００２８】
比較部（第１の比較部）８２は、メモリ６に書き込まれている受信されたキーＫIと、メモリ８１における読み出されたキーＫRとを読み出す。そして、比較部８２は、キーＫIとキーＫRとを比較する。例えば、比較部８２は、キーＫIの各ビットの情報とキーＫRの各ビットの情報とを比較し、異なるビット数を加算することによりハミング距離を算出する。ここで、ハミング距離とは、長さの等しい２つの２元符号列（情報）において、対応する位置にある成分（情報）の対のうち、互いに異なる成分の数に相当する。
【００２９】
本実施形態においては、キーＫIとキーＫRとの類似度をハミング距離で表現する場合を例として説明する。しかしながら、キーＫIとキーＫRとの類似度は、例えばコサイン距離又はユークリッド距離などを用いるなど、各種の手法に基づいて判断されてもよい。
【００３０】
判断部５３は、比較部８２による比較結果（第１の比較結果）に基づいて誤り訂正可能か判断する。換言すれば、判定部５３は、比較部８２による比較結果が誤り訂正可能であることを示すか否か判断する。例えば、判定部５３は、キーＫIがキーＫRの誤り訂正可能な範囲内か否かを、ハミング距離が誤り訂正可能な範囲内であるか否かに基づいて判断する。
【００３１】
ここで、訂正可能とは、キーＫR又はデータに生じた誤りが、誤り訂正部７で用いられる誤り訂正の誤り訂正能力の範囲内であることをいう。例えば、キーＫIとキーＫRとのハミング距離が誤り訂正部７の訂正能力を示す値以下の場合に、判断部５３は、キーＫIとキーＫRとのハミング距離が訂正可能な範囲内であると判断する。
【００３２】
比較部８２による比較結果に基づいて誤り訂正可能であると判断された場合、誤り訂正部７は、メモリ８１における読み出されたキーＫRに対して誤り訂正を実行し、訂正されたキーＫCをメモリ６に書き込む。誤り訂正部７で用いられる誤り訂正としては、例えば、ブロック符号に基づく誤り訂正、又は、畳み込み符号に基づく誤り訂正など、各種の方法が適用可能である。
【００３３】
比較部５４は、メモリ６から受信されたキーＫIと訂正されたキーＫCとを読み出し、キーＫIとキーＫCとを比較し、整合するか判断する。
【００３４】
本実施形態において、整合とは、完全一致のみに限定されるものではない。整合とは、例えば所定の範囲内における一致（部分一致）などのように、ある程度近似していればよい。例えば、整合とは、あいまい検索によって抽出すべきと判断される場合を含むとしてもよい。ここで、あいまい検索とは、検索条件が完全に一致しない対象を一定の条件の下で抽出する検索方法である。
【００３５】
例えば、比較部５４は、キーＫIの各ビットの情報とキーＫCの各ビットの情報とを比較し、異なるビット数が所定の数以下である場合に、キーＫIとキーＫCとが整合すると判断してもよい。例えば、比較部５４は、キーＫIの各ビットの情報とキーＫCの各ビットの情報とを比較し、同一のビット数が所定の数以上である場合に、キーＫIとキーＫCとが整合すると判断してもよい。
【００３６】
検索部５５は、比較部５４による比較結果（第２の比較結果）が整合する場合に、メモリコントローラ８を経由して、不揮発性メモリ９において読み出されたキーＫRに対応付けられているバリューを読み出す。例えば、検索部５５は、キー・バリュー型検索を実行する。
【００３７】
誤り訂正部７は、検索部５５によって読み出されたバリューに対して誤り訂正を実行し、訂正されたバリューＶCをメモリ６に書き込む。誤り訂正部７の一部又は全部は、ハードウェアで実装されてもよく、又は、ソフトウェアで実装されてもよい。例えば、誤り訂正部７は、プロセッサ５に含まれていてもよく、メモリコントローラ８に含まれていてもよい。
【００３８】
送信部５６は、メモリ６からバリューＶCを読み出し、バリューＶCをＩ／Ｏインタフェース４経由で情報処理装置２に送信する。
【００３９】
上記の比較部８２による比較結果に基づいて誤り訂正可能でないと判断された場合、又は、上記の比較部５４による比較結果が整合しない場合に、読み出し部５２は、不揮発性メモリ９の候補キーのうち未だ読み出されていない次のキーを読み出し、読み出された次のキーＫRをメモリ８１に書き込む。
【００４０】
そして、比較部８２は、メモリ６における受信されたキーＫIと、メモリ８１における読み出された次のキーＫRとを比較する。
【００４１】
読み出し部５２によってキーＫIに対応する全ての候補キーが不揮発性メモリ９から読み出されたが、検索部５５によって不揮発性メモリ９からバリューが読み出されなかった場合、送信部５６は、キーＫIに対応するバリューが不揮発性メモリ９に書き込まれていないことを示す信号Ｓを、Ｉ／Ｏインタフェース４経由で情報処理装置２に送信する。
【００４２】
例えば、信号Ｓは、キーＫIに対してヒットしたバリューがゼロ件であったことを示す信号などのように、キーＫIに対して適当な検索結果が得られなかったことを意味する信号である。
【００４３】
図２は、本実施形態に係るＳＳＤ３の処理の一例を示すフローチャートである。
【００４４】
ステップＳ２０１において、受信部５１は、情報処理装置２から、Ｉ／Ｏインタフェース４経由で、キーＫIを受信し、受信されたキーＫIをメモリ６に書き込む。
【００４５】
ステップＳ２０２において、読み出し部５２は、不揮発性メモリ９から候補キーのうちの未確認のキーを読み出し、読み出されたキーＫRをメモリ８１に書き込む。
【００４６】
ステップＳ２０３において、比較部８２は、メモリ６における受信されたキーＫIと、メモリ８１における読み出されたキーＫRとを比較する。
【００４７】
ステップＳ２０４において、判断部５３は、比較部８２による比較結果に基づいて誤り訂正可能であるか判断する。
【００４８】
比較部８２による比較結果に基づいて誤り訂正可能でないと判断された場合、処理はステップＳ２１１に移動する。
【００４９】
比較部８２による比較結果に基づいて誤り訂正可能であると判断された場合、ステップＳ２０５において、誤り訂正部７は、不揮発性メモリ９から読み出されメモリ８１に書き込まれたキーＫRに対して誤り訂正を実行し、訂正されたキーＫCをメモリ６に書き込む。
【００５０】
比較部５４は、ステップＳ２０６において、メモリ６における受信されたキーＫIと訂正されたキーＫCとを比較し、ステップＳ２０７において、キーＫIとキーＫCとが整合するかを判断する。
【００５１】
キーＫIとキーＫCとが整合しない場合、処理はステップＳ２１１に移動する。
【００５２】
キーＫIとキーＫCとが整合する場合、ステップＳ２０８において、検索部５５は、メモリコントローラ８を経由して、不揮発性メモリ９において読み出されたキーＫRに対応付けられているバリューを読み出す。
【００５３】
ステップＳ２０９において、誤り訂正部７は、検索部５５によって読み出されたバリューに対して誤り訂正を実行し、訂正されたバリューＶCをメモリ６に書き込む。
【００５４】
ステップＳ２１０において、送信部５６は、メモリ６から訂正されたバリューＶCを読み出し、バリューＶCをＩ／Ｏインタフェース４経由で情報処理装置２に送信し、処理は終了する。
【００５５】
上記のステップＳ２０４で比較部８２による比較結果に基づいて誤り訂正可能でないと判断された場合、又は、上記のステップＳ２０７でキーＫIとキーＫCとが整合しないと判断された場合、ステップＳ２１１において、読み出し部５２は、不揮発性メモリ９に書き込まれている全ての候補キーが読み出されたか否か判断する。
【００５６】
全ての候補キーが読み出されていない場合、処理はステップＳ２０２に移動し、読み出し部５２は、不揮発性メモリ９から次のキーを読み出し、読み出された次のキーＫRをメモリ８１に書き込む。その後、上記と同様の処理が実行される。
【００５７】
上記のステップＳ２１１において全ての候補キーが読み出されたと判断された場合、ステップＳ２１２において、送信部５６は、キーＫIに対応するバリューが不揮発性メモリ９に書き込まれていないことを示す信号Ｓを、Ｉ／Ｏインタフェース４経由で情報処理装置２に送信する。
【００５８】
図３は、本実施形態に係る読み出されたキーＫRを格納するメモリ８１と比較部８２と不揮発性メモリ９との関係の一例を示す回路図である。
【００５９】
不揮発性メモリ９は、データを格納するための複数のメモリセル１０１と、複数のメモリセル１０１から読み出されたデータに関する信号を増幅する複数の増幅器１０２とを含む。
【００６０】
メモリセル１０１は、不揮発性メモリ９において、情報を格納するための最小単位の回路であり、ワード線とビット線の交点に配置される。本実施形態においては、メモリセル１０１からデータが読み出される場合を例示しているが、例えば、不揮発性メモリ９がＨＤＤなどの場合には、セクタに格納されている情報が読み出される。このように、不揮発性メモリの種別に応じて、データが格納及び読み出される対象は異なる。
【００６１】
不揮発性メモリ９から読み出されたキーＫRデータは、メモリ８１に書き込まれる。
【００６２】
比較部８２は、例えば、ＸＯＲ（排他的論理和）回路、又は、一致回路を含む。比較部８２は、受信されたキーＫIと読み出されたメモリＫRとの比較結果を出力する。
【００６３】
本実施形態において、複数のメモリセル１０１から読み出されたＫRに関する信号は、読み出されたＫRをメモリ８１に格納可能なレベルになるように、複数の増幅器１０２によって増幅される。比較部８２の第１の入力端子は、メモリ８１に格納されているＫRに関する情報（例えばビットの情報）を順次入力する。比較部８２の第２の入力端子は、キーＫIに関する情報（例えばビットの情報）を順次入力する。そして、比較部８２は、第１の入力端子に入力されたＫRに関する情報と第２の入力端子に入力されたキーＫIに関する情報とを比較し、比較結果を出力する。なお、比較部８２の第１及び第２の入力端子に入力される情報は、２値の情報に限られず、多値情報でもよい。
【００６４】
以上説明した本実施形態の効果について説明する。
【００６５】
例えば不揮発性メモリ９から読み出されたキーＫRに誤りが含まれる場合があるとする。比較例では、不揮発性メモリ９からキーＫRが読み出されるたびに誤り訂正が実行され、訂正されたキーＫCと受信されたキーＫRとが比較されるとする。この比較例では、キーＫRに対して実行される誤り訂正の実行回数が多くなり、検索に時間がかかり、ＳＳＤ３の消費電力が大きくなる。
【００６６】
これに対して、本実施形態においては、まず、受信されたキーＫIと不揮発性メモリ９から読み出されたキーＫRとが比較される。次に、比較結果が誤り訂正可能な範囲の場合に、不揮発性メモリ９から読み出されたキーＫRに対して誤り訂正が実行され、比較結果が誤り訂正可能な範囲でないことを示す場合に、不揮発性メモリ９から次の候補のキーＫRが読み出され、同様の処理が繰り返される。
【００６７】
これにより、本実施形態においては、不揮発性メモリ９から読み出されたキーＫRに対する誤り訂正の実行回数を減少させることができ、検索時間を短縮化することができ、キー・バリュー型検索を効率的に実行することができ、ＳＳＤ３の消費電力を低下させることができる。
【００６８】
本実施形態においては、検索の一例としてキー・バリュー型検索が説明されている。しかしながら、検索は、少なくとも、受け付けられたキー、情報、データ、又は、信号に関連するデータを抽出可能であればよい。例えば、複数のキーに対応するデータが抽出される場合にも本実施形態を同様に適用可能である。
【００６９】
［第２の実施形態］
本実施形態においては、上記第１の実施形態の変形例について説明する。本実施形態では、受信されたキーＫIと読み出されたキーＫRとを比較する比較部が不揮発性メモリに備えられている。
【００７０】
図４は、本実施形態に係るＳＳＤを備える情報処理システムの一例を示すブロック図である。
【００７１】
情報処理システム１Ａは、情報処理装置２とＳＳＤ３Ａとを備える。ＳＳＤ３Ａのメモリコントローラ８Ａは、上記第１の実施形態に係るメモリ８１と比較部８２とを備えなくてもよい。
【００７２】
不揮発性メモリ９Ａは、受信されたキーＫRと読み出されたキーＫRとを比較する比較部９１を備える。
【００７３】
図５は、本実施形態に係る比較部９１と不揮発性メモリ９Ａのメモリセル１０１との関係の一例を示す回路図である。
【００７４】
不揮発性メモリ９Ａは、データを格納するための複数のメモリセル１０１と、複数のメモリセル１０１から読み出されたデータに関する信号を増幅する複数の増幅器１０２とを含む。
【００７５】
不揮発性メモリ９Ａに組み込まれている比較部９１は、読み出されたキーＫRと受信されたキーＫIとを比較し、比較結果を出力する。比較部９１は、例えば、ＸＯＲ（排他的論理和）回路、又は、一致回路を含む。
【００７６】
本実施形態において、比較部９１は、複数の比較回路９１１を備える。複数のメモリセル１０１から読み出されたＫRに関する情報は、複数の増幅器１０２によって比較回路９１１で比較可能なレベルになるように、増幅される。複数の比較回路９１１の第１の入力端子は、複数の増幅器１０２によって増幅されたＫRに関する情報（例えばビットの情報）を入力する。複数の比較回路９１１の第２の入力端子は、キーＫIに関する情報（例えばビットの情報）を入力する。そして、複数の比較回路９１１は、第１の入力端子に入力されたＫRに関する情報と第２の入力端子に入力されたキーＫIに関する情報とを比較し、比較結果を出力する。なお、複数の比較回路９１１の第１及び第２の入力端子に入力される情報は、２値の情報に限られず、多値情報でもよい。
【００７７】
以上説明した本実施形態においては、不揮発性メモリ９Ａに組み込まれている比較部９１を用いてキー・バリュー型検索を効率化することができ、上記第１の実施形態と同様の効果を得ることができる。本実施形態においては、メモリコントローラ８Ａの変更を少なくすることができる。
【００７８】
［第３の実施形態］
本実施形態においては、上記第１及び第２の実施形態で説明した情報処理システム１，１Ａの詳細構成について説明する。
【００７９】
図６は、本実施形態に係る情報処理システムの詳細構成の一例を示すブロック図である。
【００８０】
情報処理システム１Ｂは、情報処理装置２とメモリシステム３Ｂとを含む。
【００８１】
本実施形態に係るメモリシステム３Ｂは、キーＫIに基づいてバリューＶCを読み出し可能であり、さらに、論理アドレスに基づいてデータを読み出し可能であるとする。
【００８２】
上記第１及び第２の実施形態に係るＳＳＤ３，３Ａは、メモリシステム３Ｂに対応する。
【００８３】
ＳＳＤ３，３Ａのプロセッサ５は、ＣＰＵ４３Ｆ，４３Ｂに対応する。
【００８４】
Ｉ／Ｏインタフェース４は、ホストインタフェース４１及びホストインタフェースコントローラ４２に対応する。
【００８５】
メモリ６は、ＤＲＡＭ４７に対応する。
【００８６】
誤り訂正部７は、ＥＣＣ（誤り訂正部）４９に対応する。
【００８７】
メモリコントローラ８，８Ａは、ＮＡＮＤＣ（NAND Controller）５０に対応する。
【００８８】
不揮発性メモリ９，９Ａは、不揮発性メモリ９Ｂに対応する。
【００８９】
情報処理装置２は、ホスト装置として機能する。
【００９０】
メモリシステム３Ｂのコントローラ１１は、フロントエンド４Ｆと、バックエンド４Ｂとを備える。
【００９１】
フロントエンド（ホスト通信部）４Ｆは、ホストインタフェース４１、ホストインタフェースコントローラ４２、暗号化／復号化部（Advanced Encryption Standard (AES)）４４、及びＣＰＵ４３Ｆを備える。
【００９２】
ホストインタフェース４１は、情報処理装置２との間で、要求（書き込みコマンド、読み出しコマンド、消去コマンドなど）、ＬＢＡ（Logical Block Addressing）、データ、キーＫI、バリューＶC、信号Ｓなどを通信する。
【００９３】
ホストインタフェースコントローラ（制御部）４２は、ＣＰＵ４３Ｆの制御に基づいて、上記ホストインタフェース４１の通信を制御する。
【００９４】
暗号化／復号化部４４は、データ書き込み動作において、ホストインタフェースコントローラ４２から送信される書き込みデータ（平文）を暗号化する。暗号化／復号化部４４は、データ読み出し動作において、バックエンド４ＢのリードバッファＲＢから送信される暗号化された読み出しデータを復号化する。なお、この暗号化／復号化部４４を介さずに、書き込みデータ及び読み出しデータを送信することも、必要に応じて可能である。
【００９５】
ＣＰＵ４３Ｆは、フロントエンド４Ｆの上記各構成４１，４２，４４を制御し、フロントエンド４Ｆの全体の動作を制御する。
【００９６】
バックエンド（メモリ通信部）４Ｂは、ライトバッファＷＢ、リードバッファＲＢ、ＬＵＴ部４５、ＤＤＲＣ４６、ＤＲＡＭ４７、ＤＭＡＣ４８、ＥＣＣ４９、ランダマイザＲＺ、ＮＡＮＤＣ５０、及びＣＰＵ４３Ｂを備える。
【００９７】
ライトバッファ（ライトデータ転送部）ＷＢは、情報処理装置２から送信された書き込みデータを一時的に格納する。具体的には、ライトバッファＷＢは、当該書き込みデータが不揮発性メモリ９Ｂに適した所定のデータサイズになるまで、一時的にデータを格納する。
【００９８】
リードバッファ（リードデータ転送部）ＲＢは、不揮発性メモリ９Ｂから読み出された読み出しデータを一時的に格納する。具体的には、リードバッファＲＢにおいて、読み出しデータは、情報処理装置２に適した順序（情報処理装置２が指定した論理アドレスＬＢＡの順序）になるように並び替えられる。
【００９９】
ＬＵＴ４５は、論理アドレスＬＢＡを物理アドレスＰＢＡ（Physical Block Addressing）に変換するためのデータである。
【０１００】
ＤＤＲＣ４６は、ＤＲＡＭ４７におけるＤＤＲ（Double Data Rate）を制御する。
【０１０１】
ＤＲＡＭ４７は、例えば、ＬＵＴ４５を格納する揮発性のメモリである。
【０１０２】
ＤＭＡＣ（Direct Memory Access Controller）４８は、内部バスＩＢを介して、書き込みデータや読み出しデータなどを転送する。図６においては１つのＤＭＡＣ４８が図示されているが、コントローラ１１は、２以上のＤＭＡＣ４８を備えるとしてもよい。ＤＭＡＣ４８は、必要に応じて、コントローラ１１内の様々な位置に設定される。
【０１０３】
ＥＣＣ４９は、ライトバッファＷＢから送信される書き込みデータにＥＣＣ（Error Correcting Code）を付加する。ＥＣＣ４９は、リードバッファＲＢに送信する際に、付加したＥＣＣを用いて、不揮発性メモリ９Ｂから読み出した読み出しデータを必要に応じて訂正する。
【０１０４】
ランダマイザＲＺ（又はスクランブラ）は、データ書き込み動作の際に、書き込みデータが不揮発性メモリ９Ｂの特定のページ又はワード線方向などに偏らないように、書き込みデータを分散させる。このように、書き込みデータを分散させることで、書き込み回数を平準化でき、不揮発性メモリ９ＢのメモリセルＭＣのセル寿命を長期化できる。そのため、不揮発性メモリ９Ｂの信頼性を向上できる。また、データ読み出し動作の際に、不揮発性メモリ９Ｂから読み出された読み出しデータはランダマイザＲＺを通過する。
【０１０５】
ＮＡＮＤＣ５０は、所定の速度の要求を満たすため、複数のチャンネル（ここでは、４つのチャンネルＣＨ０〜ＣＨ３）を用いて、並列に不揮発性メモリ９Ｂにアクセスする。
【０１０６】
ＣＰＵ４３Ｂは、バックエンド４Ｂの上記各構成（４５〜５０，ＲＺ）を制御し、バックエンド４Ｂの全体の動作を制御する。
【０１０７】
なお、図６に示したコントローラ１１の構成は例示であり、この構成に限定されることはない。
【０１０８】
図７は、本実施形態に係るストレージシステムの一例を示す斜視図である。
【０１０９】
ストレージシステム１００は、ＳＳＤとしてのメモリシステム３Ｂを備える。
【０１１０】
メモリシステム３Ｂは、例えば比較的小型のモジュールである。なお、メモリシステム３Ｂの大きさ及び寸法は、種々の大きさのものに適宜変更可能である。
【０１１１】
また、メモリシステム３Ｂは、例えば、企業（エンタープライズ）で運用されるデータセンター又はクラウドコンピューティングシステムにおいて、サーバのような情報処理装置２に装着されて使用可能である。そのため、メモリシステム３Ｂは、エンタープライズ用ＳＳＤ（ｅＳＳＤ）であってもよい。
【０１１２】
メモリシステム３Ｂは、例えば上方に開口した複数のコネクタ（例えばスロット）１２を備える。各コネクタ１２は、例えばＳＡＳ（Serial Attached SCSI）コネクタ等である。このＳＡＳコネクタによれば、情報処理装置２と各メモリシステム３Ｂとが互いに高速通信を行うことが可能である。なお、これに限られず、各コネクタ１２は、例えば、ＰＣＩｅ（PCI Express）又はＮＶＭｅ（NVM Express）等であってもよい。
【０１１３】
複数のメモリシステム３Ｂは、情報処理装置２のコネクタ１２にそれぞれ装着され、略垂直方向に起立した姿勢で互いに並べて支持される。このような構成によれば、複数のメモリシステム３Ｂをコンパクトに纏めて実装可能であり、メモリシステム３Ｂの小型化を図ることができる。さらに、本実施形態に係るメモリシステム３Ｂの各形状は、２．５型のＳＦＦ（Small Form Factor)である。このような形状により、メモリシステム３Ｂは、エンタープライズ用ＨＤＤ（ｅＨＤＤ）と互換形状（コンパチ形状）を図ることができ、ｅＨＤＤとの容易なシステム互換性を実現することができる。
【０１１４】
なお、メモリシステム３Ｂは、エンタープライズ用に限られない。例えば、メモリシステム３Ｂは、ノートブック型ポータブルコンピュータ又はタブレット型端末のようなコンシューマ用の電子機器の記憶媒体としても適用可能である。
【０１１５】
以上説明したように、本実施形態で説明した構成を持つ情報処理システム１Ｂ及びストレージシステム１００においては、大容量の記憶に、上記第１及び第２の実施形態と同様の効果を得ることができる。
【０１１６】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１１７】
１…情報処理システム、２…情報処理装置、３…ＳＳＤ、４…Ｉ／Ｏインタフェース、５…プロセッサ、５１…受信部、５２…読み出し部、５３…判断部、５４…比較部、５５…検索部、５６…送信部、６…メモリ、７…誤り訂正部、８，８Ａ…メモリコントローラ、８１…メモリ、９，９Ａ…不揮発性メモリ、ＫI，ＫR，ＫC，Ｋ1〜ＫN…キー、Ｖ1〜ＶN，ＶC…バリュー、Ａ1〜ＡN…アドレス、８２，９１…比較部、９１１…比較回路、１０１…メモリセル、１０２…増幅器。
【図１】
0006297000.tif 000002
【図２】
0006297000.tif 000003
【図３】
0006297000.tif 000004
【図４】
0006297000.tif 000005
【図５】
0006297000.tif 000006
【図６】
0006297000.tif 000007
【図７】
0006297000.tif 000008