(57)【要約】  高速性、信頼性の向上を実現し、スケーラブルに拡張可能な分散ストレージに適用して好適とされるシステム、方法、プログラムを提供する。キーからバリューを得ることができるデータ構成を持ち、書き込み時、キー（Ｋｅｙ）（１０）とバリュー（Ｖａｌｕｅ）（１１）のハッシュ値Ｈａｓｈ（Ｖａｌｕｅ）（１３）の第１の対＜Ｋｅｙ，Ｈａｓｈ（Ｖａｌｕｅ）＞（１２Ａ）と、バリューのハッシュ値とバリューの第２の対＜Ｈａｓｈ（Ｖａｌｕｅ），Ｖａｌｕｅ＞（１２Ｂ）を揮発性の記憶装置にそれぞれ格納しておき、第１の対（１２Ａ）は応答を返す前に、不揮発性の記憶装置に保存し、第２の対（１２Ｂ）は、揮発性の記憶装置に保存しておき、任意のタイミングで前記第１の記憶装置に保存し、キーからバリューを得る読み出し時に、第１の対（１２Ａ）からバリューのハッシュ値を得て第２の対（１２Ｂ）を読み出す処理において、第２の対（１２Ｂ）が存在しないときには、データが正常に格納されなかったものと判断する。
2010114006.tif 000002
【特許請求の範囲】
【請求項１】
キーとバリューを対応させて格納し、キーを検索してバリューを得るキー・バリュー型データストア構成のストレージシステムであって、
キーとバリューの対の書き込み要求に対して、
前記バリューのハッシュ値を計算し、
前記キーと、前記バリューのハッシュ値をそれぞれキーとバリューとする第１の対と、
前記バリューのハッシュ値と、前記バリューをそれぞれキーとバリューとする第２の対と、
をそれぞれ記憶装置に格納し、
読み出し要求に対して、
前記読み出し要求で指定されたキーで前記記憶装置を検索して、前記キーと前記第１の対をなすバリューのハッシュ値を取得し、
取得した前記バリューのハッシュ値で前記記憶装置を検索して、前記バリューのハッシュ値と前記第２の対をなすバリューを取得し、その際、前記バリューのハッシュ値で前記記憶装置を検索した結果、前記バリューのハッシュ値と前記第２の対をなすバリューが前記記憶装置に存在しない場合、前記第１の対が前記記憶装置に正常に保存されなかったものと判断する手段を備えた、ストレージシステム。
【請求項２】
キーとバリューの対の書き込み要求に対して、
前記第１の対と前記第２の対を、揮発性の記憶装置にそれぞれ保存し、
前記第１の対は、前記揮発性の記憶装置への保存とともに又はその後、前記書き込み要求の応答を要求元に返す前に、不揮発性の記憶装置に保存し、
前記第２の対は、前記揮発性の記憶装置への保存とともに又はその後の任意のタイミングで不揮発性の記憶装置に保存する、請求項１記載のストレージシステム。
【請求項３】
読み出し時、
前記キーによる検索の結果、前記キーと前記第１の対をなすバリューのハッシュ値が見つかった場合、次に、前記バリューのハッシュ値をキーとして前記記憶装置を検索して前記第２の対のバリューを取得し、
前記キーと前記第１の対をなすバリューのハッシュ値が見つかり、前記バリューのハッシュ値と前記第２の対をなすバリューが見つかった場合、前記バリューを読み出し結果として返し、
前記キーと前記第１の対をなすバリューのハッシュ値が見つからなかったときには、前記キーに対するバリューが存在しないことを示す情報を返し、
前前記キーと前記第１の対をなすバリューのハッシュ値が見つかり、且つ、前記バリューのハッシュ値と前記第２の対をなすバリューが見つからなかったときは、エラーを返す、請求項１又は２記載のストレージシステム。
【請求項４】
キーとバリューの書き込み時、前記キーと前記バリューのハッシュ値の前記第１の対と、前記バリューのハッシュ値と前記バリューの前記第２の対を、揮発性の記憶装置にそれぞれ格納しておき、
前記第１の対は応答を返す前に、不揮発性の記憶装置に保存し、
前記第２の対は、揮発性の記憶装置に保存しておき、任意のタイミングで不揮発性の記憶装置に保存する手段と、
キーからバリューを得る読み出し時に、前記第１の対からバリューのハッシュ値を得て前記第２の対を読み出す処理において、前記第２の対が存在しないときには、データが正常に格納されなかったと判断する手段を備えた、請求項１記載のストレージシステム。
【請求項５】
データ及びメタデータをオブジェクトとして保存するとオブジェクト識別子を生成し該オブジェクト識別子であるコンテンツアドレスを返し、該コンテンツアドレスを用いてオブジェクトにアクセスするコンテンツアドレスストレージ（ＣＡＳ）を備え、
第１の対をキーとバリューのハッシュ値の対とし、
第２の対を、前記バリューのハッシュ値とバリューの対のかわりに、前記バリューのハッシュ値をキー、前記バリューのコンテンツアドレスをバリューとする対とし、
前記バリューを、前記コンテンツアドレスストレージに保存する、請求項１乃至３のいずれか１項に記載のストレージシステム。
【請求項６】
ネットワークに接続され、請求項１乃至５のいずれか１項記載のストレージシステムを備えたノードを複数有する分散ストレージシステム。
【請求項７】
前記ノードが、書き込み時、キーとバリューを対応させて格納し、読み出し時、キーで検索してバリューを得る複数のキー・バリュー型ストレージサーバと、
キーとバリューの対の書き込み要求を受け、
前記バリューのハッシュ値を計算し、
前記キーと前記バリューのハッシュ値をそれぞれキーとバリューとする第１の対と、
前記バリューのハッシュ値と前記バリューをそれぞれキーとバリューとする第２の対と、
を生成し、
前記第１の対のキーとバリューを対応させて第１のキー・バリュー型ストレージサーバに保存し、
前記第２の対のキーとバリューを対応させて第２のキー・バリュー型ストレージサーバに保存するストレージクライアントと、
を備えた、請求項６記載の分散ストレージシステム。
【請求項８】
前記ストレージクライアントは、キーからバリューを得る読み出し要求を受けると、
前記第１のキー・バリュー型ストレージサーバに対して前記キーで検索して、前記キーと前記第１の対をなす前記バリューのハッシュ値を取得し、
前記第２のキー・バリュー型ストレージサーバに対して前記バリューのハッシュ値で検索して、前記バリューのハッシュ値と前記第２の対をなす前記バリューを取得し、前記検索処理において、前記バリューのハッシュ値と前記バリューの前記第２の対が存在しないときには、前記第１の対が前記第１のキー・バリュー型ストレージサーバに正常に保存されなかったものと判断する、請求項７記載の分散ストレージシステム。
【請求項９】
前記ストレージクライアントは、前記第１、第２の対のキーのハッシュ値に基づき、前記第１、第２の対のキーとバリューを保存する第１、第２のキー・バリュー型ストレージサーバを決定する、請求項７又は８記載の分散ストレージシステム。
【請求項１０】
前記第１のキー・バリュー型ストレージサーバが、第１の揮発性の記憶装置と第１の不揮発性の記憶装置を備え、
前記第２のキー・バリュー型ストレージサーバが、第２の揮発性の記憶装置と第２の不揮発性の記憶装置を備え、
前記第１のキー・バリュー型ストレージサーバは、前記第１の対のキーとバリューを前記第１の揮発性の記憶装置に保存し、
前記第２のキー・バリュー型ストレージサーバは、前記第２の対のキーとバリューを前記第２の揮発性の記憶装置に保存し、
前記第１のキー・バリュー型ストレージサーバは、書き込み要求に対する応答を返す前に、前記第１の対のキーとバリューを前記第１の不揮発性の記憶装置に保存し、
前記第２のキー・バリュー型ストレージサーバは、前記第２の対のキーとバリューを任意のタイミングで、前記第２の不揮発性の記憶装置に保存する、請求項７乃至９のいずれか１項に記載の分散ストレージシステム。
【請求項１１】
前記ストレージクライアントは、キーとバリューの対の書き込み要求を受けて、キーとバリューの対をキャッシュメモリに格納し、
キーからバリューを得る読み出し要求に対して、前記キャッシュメモリに前記キーと、前記キーに対応するバリューが格納されている場合、前記キャッシュメモリから前記キーに対応するバリューを読み出して応答として返す、請求項７乃至９のいずれか１項に記載の分散ストレージシステム。
【請求項１２】
キーとバリューを対応させて格納し、キーを検索してバリューを得るキー・バリュー型ストレージのアクセス方法であって、
キーとバリューの対の書き込み要求に対して、
前記バリューのハッシュ値を計算し、
前記キーと、前記バリューのハッシュ値をそれぞれキー、バリューとする第１の対と、
前記バリューのハッシュ値と、前記バリューをそれぞれキー、バリューとする第２の対と、
をそれぞれ記憶装置に格納し、
読み出し要求に対して、
前記読み出し要求で指定されたキーで前記記憶装置を検索して、前記キーと前記第１の対をなすバリューのハッシュ値を取得し、
取得した前記バリューのハッシュ値で前記記憶装置を検索して、前記バリューのハッシュ値と前記第２の対をなすバリューを取得し、その際、前記バリューのハッシュ値で前記記憶装置を検索した結果、前記バリューのハッシュ値と前記第２の対をなすバリューが前記記憶装置に存在しない場合、前記第１の対が前記記憶装置に正常に保存されなかったものと判断する、ストレージアクセス方法。
【請求項１３】
キーとバリューの対の書き込み要求に対して、
前記第１の対と前記第２の対を、揮発性の記憶装置にそれぞれ保存し、
前記第１の対は、前記揮発性の記憶装置への保存とともに又はその後、前記書き込み要求の応答を要求元に返す前に、不揮発性の記憶装置に保存し、
前記第２の対は、前記揮発性の記憶装置への保存とともに又はその後の任意のタイミングで不揮発性の記憶装置に保存する、請求項１２記載のストレージアクセス方法。
【請求項１４】
キーとバリューを対応させて格納し、キーを検索してバリューを得るキー・バリュー型データストア構成のストレージシステムを構成するコンピュータに、
キーとバリューの対の書き込み要求に対して、
前記バリューのハッシュ値を計算する処理と、
前記キーと、前記バリューのハッシュ値をそれぞれキー、バリューとする第１の対と、
前記バリューのハッシュ値と、前記バリューをそれぞれキー、バリューとする第２の対と、
をそれぞれ記憶装置に格納する処理と、
読み出し要求に対して、
前記読み出し要求で指定されたキーで前記記憶装置を検索して、前記キーと前記第１の対をなすバリューのハッシュ値を取得する処理と、
取得した前記バリューのハッシュ値で前記記憶装置を検索して、前記バリューのハッシュ値と前記第２の対をなすバリューを取得し、その際、前記バリューのハッシュ値で前記記憶装置を検索した結果、前記バリューのハッシュ値と前記第２の対をなすバリューが前記記憶装置に存在しない場合、前記第１の対が前記記憶装置に正常に保存されなかったものと判断する、処理と、
を実行させるプログラム。
【請求項１５】
キーとバリューの対の書き込み要求に対して、
前記第１の対と前記第２の対を、揮発性の記憶装置にそれぞれ保存する処理と、
前記第１の対は、前記揮発性の記憶装置への保存とともに又はその後、前記書き込み要求の応答を要求元に返す前に、不揮発性の記憶装置に保存する処理と、
前記第２の対は、前記揮発性の記憶装置への保存とともに又はその後の任意のタイミングで不揮発性の記憶装置に保存するする処理と、
を前記コンピュータに実行させる請求項１４記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２００９−０８６６３４号（２００９年  ３月３１日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、ストレージシステムと方法とプログラムに関し、特に、キー・バリュー型ストレージに適用して好適なストレージシステムと方法とプログラムに関する。
【背景技術】
【０００２】
ストレージシステムは、様々なタイプのストレージデバイスから構成されている。その理由は、ストレージデバイスはそれぞれ固有の特徴を有しており、システム全体として性能・信頼性を高めるためには各ストレージデバイスの特徴を組み合わせることが有効であるためである。【０００３】
一般的に高速なストレージは小容量で、大容量なストレージは低速であるという特徴がある。これを如何に組み合わせて、大容量で高速且つ高信頼なストレージにするかはストレージシステムの大きなテーマである。【０００４】
高速小容量のストレージとして、例えばＲＡＭ（ランダムアクセスメモリ）等の半導体メモリがあげられる。低速大容量のストレージとして、例えばハードディスク（ＨＤＤ）があげられる。一般に、データはハードディスクに保存される。メモリ（ＲＡＭ）は、ディスクに対してはるかに記憶容量が小さいということと、揮発性（電源が切れるとデータも消える）であることにより、キャッシュ（ディスクキャッシュ）として用いられている。データは、ハードディスクに存在し、ハードディスク上のアドレス（ブロックアドレス）が指定されてＲＥＡＤ／ＷＲＩＴＥアクセスが行われる。ハードディスクの入出力アクセスはメモリに比べて低速であるため、アクセス毎、毎回、ハードディスクにアクセスする場合、処理が遅くなる。そこで、メモリ（ディスクキャッシュ）を間に挟み、一度アクセスしたデータはメモリ上にも置く。これにより、再度、同じアドレスへのアクセスが行われたときには、ハードディスクにはアクセスせず、メモリ（キャッシュ）上のデータを返すことで、高速化を可能としている。これが、キャッシュの原理である。【０００５】
さらに、データの先読みやＷＲＩＴＥ時にシーケンシャルログにするなど、ハードディスクの特性を考慮してなるべくデータアクセスを高速化するような工夫が従来から多く研究され、実用化されている。【０００６】
このように、メモリの容量がハードディスクの容量に比べてはるかに少なく、処理に必要なデータがメモリに対して大きいという前提でストレージシステムは構築されてきた。【０００７】
しかし、昨今、メモリの大容量化により、この前提が変わってきている。例えば、最新の製品では、コモディティなサーバでも、１台当り１００ＧＢ以上のメモリ（ＤＲＡＭ（ダイナミックランダムアクセスメモリ）等）を積めるようになっている。【０００８】
さらに、分散共有メモリ技術により、複数のサーバのメモリをクラスタ間で共有できれば、ＴＢ（テラバイト）オーダーのメモリ容量となり、たいていの処理に対しては十分な容量が確保できる。この状況に呼応し、メモリだけで完結する製品も出てきている。メモリのみで完結するストレージ製品として、例えばＯｒａｃｌｅ社のインメモリ製品「Ｏｒａｃｌｅ  Ｃｏｈｅｒｅｎｃｅ」（オラクルコヒーレンス）、あるいは、オープンソースの「ｍｅｍｃａｃｈｅｄ」（例えば、大手ｗｅｂｓｉｔｅ（ウエッブサイト）で分散メモリキャッシュシステムに使われている）が知られており、更新、検索中にディスクアクセスを行わず高速データ処理を可能とするＯｎ−ｍｅｍｏｒｙ  ＤＢ（メモリＤＢ）も着目されている。これらの製品は、処理に必要なデータは全てメモリ上にあるという前提で、データ処理の高速化を実現している。【０００９】
一方、近時、キー・バリュー型（Ｋｅｙ−Ｖａｌｕｅ）データストアが着目されている（Ａｍａｚｏｎ社の「Ａｍａｚｏｎ  Ｄｙｎａｍｏ」、あるいは「ｍｅｍｃａｃｈｅｄ」等）。キー・バリュー型分散データストアは、メモリマップは共有ではなく、バリューは可変長であり、クライアントサーバモデルが適用可能、分散の仕方はクライアント側で決定する等の特徴をもち、ストレージサーバ間の連携が不要であり、スケーラブルな拡張が容易である等の利点を有する（キー・バリュー型（Ｋｅｙ−Ｖａｌｕｅ）データストアについては、本発明の実施形態に関連して後述される）。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
以下に発明による分析を与える。【００１１】
前述したように、メモリの大容量化に伴い、メモリだけでストレージを作ることも可能になってくる。しかし、ＤＲＡＭ等のメモリは高速アクセスが可能であるが、電源が切れると保持データが失われる揮発性のストレージである。よって、メモリにのみデータを保存しておくのでは、ストレージとして不十分である。【００１２】
永続化を確定するためには、電源が切れてもデータを保持する不揮発ストレージ、例えばハードディスク（ＨＤＤ）にも格納しておく必要がある。しかし、メモリに書き込まれたデータをそのつどハードディスクに保存するとなると、応答時間（アクセス時間）が長時間となる。したがって、メモリだけでストレージを構成し、処理を高速化しようとしても、実はハードディスクにデータを保存するというのでは、メモリだけでストレージを構成したことのメリットがなくなってしまうことになる。【００１３】
そこで、ハードディスクに保存するデータ量を削減するとともに、信頼性を高めることが課題となる。【００１４】
この課題は、ストレージシステムに共通する課題であり、既存のファイルシステムやデータベースの中にも、この課題に取り組んでいるものもある。しかしながら、これらのファイルシステムやデータベースは、前提として、データはハードディスク上にあり、メモリはキャッシュとして位置付けている。このため、ハードディスク上でのデータ配置に工夫を要することになる。また、メモリはキャッシュ（ディスクキャッシュ）として構成されているため、必要に応じて、オンデマンドで、ディスク・アクセスが行われる（例えばキャッシュミスヒット時におけるディスクデータの読み出し、あるいは、データ更新時のライトバック又はライトスルー等）。これらのファイルシステムやデータベースを分散ストレージサーバに適用することを考えた場合、サーバ間での連携等が必要となり、高速化、信頼性を実現しながら、スケーラブルに拡張可能とするシステムの実現は困難である。【００１５】
したがって、本発明の目的は、高速性、信頼性の向上を実現可能とし、スケーラブルに拡張可能な分散ストレージに適用して好適とされるシステム、方法、プログラムを提供することにある
【課題を解決するための手段】
【００１６】
本発明によれば、キーとバリューを対応させて格納し、キーを検索してバリューを得るキー・バリュー型データストア構成のストレージシステムであって、
キーとバリューの対の書き込み要求に対して、
前記バリューのハッシュ値を計算し、
前記キーと、前記バリューのハッシュ値をそれぞれキー、バリューとする第１の対と、
前記バリューのハッシュ値と、前記バリューをそれぞれキー、バリューとする第２の対と、
をそれぞれ記憶装置に格納し、
読み出し要求に対して、
前記読み出し要求で指定されたキーで前記記憶装置を検索して、前記キーと前記第１の対をなすバリューのハッシュ値を取得し、
取得した前記バリューのハッシュ値で前記記憶装置を検索して、前記バリューのハッシュ値と前記第２の対をなすバリューを取得し、その際、前記バリューのハッシュ値で前記記憶装置を検索した結果、前記バリューのハッシュ値と前記第２の対をなすバリューが前記記憶装置に存在しない場合、前記第１の対が前記記憶装置に正常に保存されなかったものと判断する手段を備えた、ストレージシステムが提供される。【００１７】
本発明によれば、キーとバリューを対応させて格納し、キーを検索してバリューを得るキー・バリュー型データストア構成のストレージシステムにおいて、
キーとバリューの対の書き込み要求に対して、
前記バリューのハッシュ値を計算し、
前記キーと、前記バリューのハッシュ値をそれぞれキー、バリューとする第１の対と、
前記バリューのハッシュ値と、前記バリューをそれぞれキー、バリューとする第２の対と、
をそれぞれ記憶装置に格納し、
読み出し要求に対して、
前記読み出し要求で指定されたキーで前記記憶装置を検索して、前記キーと前記第１の対をなすバリューのハッシュ値を取得し、
取得した前記バリューのハッシュ値で前記記憶装置を検索して、前記バリューのハッシュ値と前記第２の対をなすバリューを取得し、その際、前記バリューのハッシュ値で前記記憶装置を検索した結果、前記バリューのハッシュ値と前記第２の対をなすバリューが前記記憶装置に存在しない場合、前記第１の対が前記記憶装置に正常に保存されなかったものと判断する方法が提供される。【００１８】
本発明によれば、キーとバリューを対応させて格納し、キーを検索してバリューを得るキー・バリュー型データストア構成のストレージシステムを構成するコンピュータに、
キーとバリューの対の書き込み要求に対して、
前記バリューのハッシュ値を計算し、
前記キーと、前記バリューのハッシュ値をそれぞれキー、バリューとする第１の対と、
前記バリューのハッシュ値と、前記バリューをそれぞれキー、バリューとする第２の対と、
をそれぞれ記憶装置に格納し、
読み出し要求に対して、
前記読み出し要求で指定されたキーで前記記憶装置を検索して、前記キーと前記第１の対をなすバリューのハッシュ値を取得し、
取得した前記バリューのハッシュ値で前記記憶装置を検索して、前記バリューのハッシュ値と前記第２の対をなすバリューを取得し、その際、前記バリューのハッシュ値で前記記憶装置を検索した結果、前記バリューのハッシュ値と前記第２の対をなすバリューが前記記憶装置に存在しない場合、前記第１の対が前記記憶装置に正常に保存されなかったものと判断する処理を実行させるプログラムが提供される。
【発明の効果】
【００１９】
本発明によれば、高速性、信頼性の向上を実現し、スケーラブルに拡張可能な分散ストレージに適用して好適とされる。
【図面の簡単な説明】
【００２０】
【図１】本発明の一実施形態のシステム構成を示す図である。
【図２】キー・バリュー型ストレージを説明する図である。
【図３】キー・バリュー型ストレージの分散形態を説明する図である。
【図４】本発明の一実施形態におけるキー・バリュー型ストレージを説明する図である。
【図５】本発明の一実施形態における書き込みＰＵＴ（Ｋ、Ｖ）の処理手順を示す流れ図である。
【図６】本発明の一実施形態における読み出しＧＥＴ（Ｋ）の処理手順を示す流れ図である。
【図７】本発明の別の実施形態におけるキー・バリュー型ストレージを説明する図である。
【図８】本発明の一実施形態におけるキー・バリュー型ストレージの分散形態を説明する図である。
【図９】本発明の一実施例の分散ストレージシステムでの書き込みＰＵＴ（Ｋ、Ｖ）を説明する図である。
【図１０】本発明の一実施例の分散ストレージシステムでの読み出しＧＥＴ（Ｋ）を説明する図である。
【発明を実施するための形態】
【００２１】
以下では、本発明の基本原理を説明したのち、実施形態について説明する。本発明においては、データはメモリに格納されていることを前提とする。また本発明において、前述したように、電源オフ時のメモリデータ保持のために、例えば該データをハードディスク（以下、単に、「ディスク」と略記される）に格納しておくが、アクセスに応じて、オンデマンドで、ディスクを読みに行くことはない。本発明に係るストレージシステムは、起動したときに、ディスクから、保存されているデータを読み込み、ＲＡＭ等のメモリに展開する。このように、本発明に係るストレージシステムは、既存のファイルシステムやデータベースとは基本動作が相違している。
【００２２】
また、本発明においては、信頼性を高める方法も既存システムとは相違している。この課題を考える際に、重要な要素となるのがデータモデルである。
【００２３】
本発明においては、メモリにデータが残ることを前提としている。そのため、単一ノードだけでは、メモリ容量が十分とはいえないことから、クラスタ化して、分散共有メモリを構成する。このため、本発明において、データモデルは、分散共有メモリに適したデータモデルである必要がある。
【００２４】
分散共有メモリは、従来より、各種開発されており、例えば、
・アドレスマップを共有する方法や、
・ＭＰＩ（Ｍｅｓｓａｇｅ  Ｐａｓｓｉｎｇ  Ｉｎｔｅｒｆａｃｅ）で通信する方法、
等が知られている。しかし、これらの方法は、ノードが増えていくと性能が飽和する。
【００２５】
これに対して、近年、キー（Ｋｅｙ）とバリュー（Ｖａｌｕｅ）の組を元に、分散共有メモリを実現する方式であるキー・バリュー型（Ｋｅｙ−Ｖａｌｕｅ）ストレージが注目されている。Ｋｅｙ−Ｖａｌｕｅストレージは連想配列とも言われるデータモデルである。Ｋｅｙ−Ｖａｌｕｅストレージは、各アイテム（ＫｅｙとＶａｌｕｅのセット）の関係が独立であるため、分散に適し、ノードが増えても、性能がスケーラブルに拡張し易いというメリットがある。
【００２６】
本発明においては、Ｋｅｙ−Ｖａｌｕｅストレージをデータモデルとして採用し、性能と信頼性の両立を解決する。具体的には、如何にして、メモリ上のデータのうちディスクに同期保存するデータ量を減らすかという課題を解決する。
【００２７】
本発明においては、Ｋｅｙ−Ｖａｌｕｅストレージを、多段の間接参照とし、１段目のバリュー（＝２段目のキーに相当）を、実バリュー（＝２段目のバリュー）のハッシュ値とする。
【００２８】
本発明においては、キーとバリューの対の書き込み要求に対して、バリューのハッシュ値を計算し、キーとバリューのハッシュ値をそれぞれキー、バリューとする第１の対と、バリューのハッシュ値と、バリュー（実バリュー）をそれぞれキー、バリューとする第２の対と、をそれぞれ記憶装置に格納する。読み出し要求に対して、指定されたキーで前記記憶装置を検索して、前記キーと前記第１の対をなすバリューのハッシュ値を取得し、取得した前記バリューのハッシュ値で前記記憶装置を検索して、前記バリューのハッシュ値と前記第２の対をなすバリュー（実バリュー）を取得する。その際、前記バリューのハッシュ値で前記記憶装置を検索した結果、前記バリューのハッシュ値と前記第２の対をなすバリューが前記記憶装置に存在しない場合、前記第１の対が前記記憶装置に正常に保存されなかったものと判断する。
【００２９】
本発明において、分散ストレージシステムは、書き込み時、キーとバリューを対応させて格納し、読み出し時、キーで検索してバリューを得る複数のキー・バリュー型（Ｋｅｙ−Ｖａｌｕｅ）ストレージサーバと、キー・バリュー型（Ｋｅｙ−Ｖａｌｕｅ）ストレージクライアントを備えている。Ｋｅｙ−Ｖａｌｕｅストレージクライアントは、キーとバリューの対の書き込み要求を受け、前記バリューのハッシュ値を計算し、前記キーと前記バリューのハッシュ値をそれぞれキーとバリューとする第１の対と、前記バリューのハッシュ値と前記バリューをそれぞれキーとバリューとする第２の対と、を生成する。Ｋｅｙ−Ｖａｌｕｅストレージクライアントは、前記第１の対のキーとバリューを対応させて第１のＫｅｙ−Ｖａｌｕｅストレージサーバに保存し、前記第２の対のキーとバリューを対応させて第２のＫｅｙ−Ｖａｌｕｅストレージサーバに保存する。
【００３０】
Ｋｅｙ−Ｖａｌｕｅストレージクライアントは、キーからバリューを得る読み出し要求を受けると、前記第１のＫｅｙ−Ｖａｌｕｅストレージサーバを前記キーで検索して、前記キーと前記第１の対をなす前記バリューのハッシュ値を取得し、取得したバリューのハッシュ値をキーとして、前記第２のＫｅｙ−Ｖａｌｕｅストレージサーバを検索して、前記バリューのハッシュ値と前記第２の対をなす前記バリューを取得する。前記検索処理において、前記バリューのハッシュ値と前記バリューの前記第２の対が存在しないときには、前記第１の対が前記第１のＫｅｙ−Ｖａｌｕｅストレージサーバに正常に格納されなかったものと判断する。
【００３１】
本発明において、Ｋｅｙ−Ｖａｌｕｅストレージクライアントは、前記第１、第２の対のキーのハッシュ値に基づき、前記第１、第２の対のキーとバリューを保存する第１、第２のＫｅｙ−Ｖａｌｕｅストレージサーバを決定する。
【００３２】
本発明において、前記第１のＫｅｙ−Ｖａｌｕｅストレージサーバは、第１の揮発性記憶装置（例えばＤＲＡＭ等の半導体メモリ）と第１の不揮発性の記憶装置（例えばハードディスク）を備えている。前記第２のＫｅｙ−Ｖａｌｕｅストレージサーバは、第２の揮発性記憶装置（例えばＤＲＡＭ等の半導体メモリ）と第２の不揮発性の記憶装置（例えばハードディスク）を備えている。前記第１、第２のＫｅｙ−Ｖａｌｕｅストレージサーバは、前記第１、第２の対のキーとバリューを前記第１、第２の揮発性記憶装置にそれぞれ保存する。前記第１のＫｅｙ−Ｖａｌｕｅストレージサーバは、書き込み要求に対する応答を返す前に、前記第１のキーとバリューを前記第１の不揮発性の記憶装置に保存する。前記第２のＫｅｙ−Ｖａｌｕｅストレージサーバは、前記第２の対のキーとバリューを任意のタイミングで前記第２の不揮発性の記憶装置に保存する。
【００３３】
本発明において、Ｋｅｙ−Ｖａｌｕｅストレージクライアントは、キーとバリューの対の書き込み要求を受けて、キーとバリューの対をキャッシュメモリに格納し、キーからバリューを得る読み出し要求に対して、前記キャッシュメモリに前記キーと、前記キーに対応するバリューが格納されている場合（キャッシュヒット時）、前記キャッシュメモリから前記キーに対応するバリューを読み出して応答として返し、キャッシュミスヒット時に、第１、第２のＫｅｙ−Ｖａｌｕｅストレージサーバからの読み出し（ＫｅｙによるＨａｓｈ（Ｖａｌｕｅ）の読み出しと、該読み出したＨａｓｈ（Ｖａｌｕｅ）によるＶａｌｕｅの読み出し）を行う構成としてもよい。
【００３４】
＜実施形態１＞
図１は、本発明の一実施形態のシステム構成を示す図である。図１において、ノード１は、ストレージとして、メモリ２（例えばＲＡＭ）と、ハードディスク（「ディスク」と略記される）３を有する。メモリ２において指定された容量（あるいは領域）が、Ｋｅｙ−Ｖａｌｕｅストレージ用に確保されている。メモリ２において指定された容量（あるいは領域）を、「キー・バリュー型（Ｋｅｙ−Ｖａｌｕｅ）ストレージ用メモリ４」と呼ぶ。Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４は、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５で管理する。なお、Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４を、メモリ２内の設けずに、別構成の半導体メモリで構成してもよいことは勿論である。
【００３５】
Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４にアクセスするアプリケーション６は、Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７を経由してアクセスを行う。アプリケーション６は、メモリ２のＫｅｙ−Ｖａｌｕｅストレージ用メモリ４以外の領域にアクセスする場合、Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７を介さずに、直接、メモリ２にアクセスし、ディスク３へも直接アクセスする。
【００３６】
ノード１が複数ある場合、Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４は、複数ノード１間を相互接続するネットワーク８を介して、複数ノード１間で共有される。
【００３７】
具体的には、Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７が、キーとバリューの対＜Ｋｅｙ、Ｖａｌｕｅ＞のＫｅｙのハッシュ値に基づいて、ターゲットノード１を特定し、ターゲットノード１のＫｅｙ−Ｖａｌｕｅストレージサーバ機能５にネットワーク８を経由してアクセスすることで、分散ストレージが実現される。
【００３８】
Ｋｅｙのハッシュ値からノードを特定するアルゴリズムは、ネットワーク８に接続された全てのノード１のＫｅｙ−Ｖａｌｕｅストレージクライアント機能７により共有される。ただし、共有の仕方は任意である。
【００３９】
次に、本実施形態におけるＫｅｙ−Ｖａｌｕｅストレージについて、図２を参照して説明する。Ｋｅｙ−Ｖａｌｕｅストレージとは、プログラミング言語では連想配列（Ａｓｓｏｓｉａｔｉｖｅ  Ａｒｒａｙ）と言われるものである。
【００４０】
図２（Ａ）において、Ｋｅｙ１０には、任意の文字列が指定可能であり、Ｖａｌｕｅ１１に値（文字列とは限定されない）が格納される。
【００４１】
Ｋｅｙ１０とＶａｌｕｅ１１の対をアイテム１２と呼び、＜Ｋ、Ｖ＞と表記する。Ｋｅｙ−Ｖａｌｕｅにおけるデータ処理命令は、Ｇｅｔ（読み出し）とＰｕｔ（書き込み）がある。
【００４２】
Ｇｅｔは、Ｋｅｙ１０をもとにＶａｌｕｅ１１を得る命令（読み出し命令）である。
【００４３】
Ｐｕｔは、アイテム１２（＝＜Ｋ、Ｖ＞）を格納する命令（書き込み命令）である。すなわち、
Ｇｅｔ（Ｋ）＝Ｖ
Ｐｕｔ（＜Ｋ、Ｖ＞）
と表記できる。
【００４４】
図２（Ｂ）にＫｅｙ−Ｖａｌｕｅの例を示す。＜Ｒｅｄ、Ａｐｐｌｅ＞、＜Ｙｅｌｌｏｗ、Ｏｒａｎｇｅ＞、＜Ｐｉｎｋ、Ｐｅａｃｈ＞の３つのアイテム１２が格納されている。このとき、
Ｇｅｔ（Ｒｅｄ）＝Ａｐｐｌｅ、
Ｇｅｔ（Ｙｅｌｌｏｗ）＝Ｏｒａｎｇｅ、
Ｇｅｔ（Ｐｉｎｋ）＝Ｐｅａｃｈ
となる。
【００４５】
Ｋｅｙ−Ｖａｌｕｅストレージのメリットは、分散したときに性能がスケーラブルに拡張できることである。Ｋｅｙ−Ｖａｌｕｅストレージにおいては、アイテム１２は互いに独立である。すなわち、あるアイテム１２を変更する際に、別のアイテム１２を変更する必要はない。よって、分散したノード１間でデータをやりとりすることは基本的にはない（だだし、ノード障害が起きた場合やノード追加をする場合にはやりとりが発生する）。
【００４６】
分散のアルゴリズムは、Ｋｅｙ１０のハッシュ値を用いるため、複数ノード１間で調整する必要はない。例えば、表形式と比較する。表を列あるいは行により分割して、ノード１に分散配置する。表中のあるセル（カラムとローで特定される）の値を変更するだけであれば、そのデータを持つノード１だけで、処理が閉じる。
【００４７】
しかし、表自体の行を増やす場合、あるいは、列により分散配置している場合には、列のノード１に対して処理をする必要がある。ｎ行×ｍ列の表に対して、ｍ列に対応するｎ個のノードを分散配置している場合、（ｎ＋１）行とした場合、ｍ列のノードはそれぞれ１行増加した分の処理が必要となる。
【００４８】
また、現在のリレーショナルデータベース（ＲＤＢ）では、大きな表を小さな表に分割し（正規化という）、インデックスを作成し、クエリー（Ｑｕｅｒｙ）に対して、効率的に応答できるようにしている。インデックスで分割された小さな表を検索し、小さな表を検索する。このため、一つのデータが複数の表にまたがって存在する。こうなると、ＲＤＢでは、分散配置しても、なかなかスケーラビリティを出すことは難しい。
【００４９】
図３は、本実施形態におけるＫｅｙ−Ｖａｌｕｅストレージにおける分散の例として、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａ〜５Ｄの計４つのノードに対して分散している例を示している。
【００５０】
Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７は、Ｋｅｙ１０のハッシュ値の範囲により、どのＫｅｙ−Ｖａｌｕｅストレージサーバ機能５がアイテム１２（ＫｅｙとＶａｌｕｅのセット）を持っているかを特定し、ターゲットとして特定されたＫｅｙ−Ｖａｌｕｅストレージサーバ機能５に対して、Ｇｅｔ／Ｐｕｔを行う。図３に示す例では、Ｋｅｙのハッシュ関数Ｈａｓｈ（Ｋｅｙ）が０＜Ｈａｓｈ（Ｋｅｙ）≦Ａであれば、アイテム１２（ＫｅｙとＶａｌｕｅのセット）は、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａ（サーバＡ）、Ａ＜Ｈａｓｈ（Ｋｅｙ）≦Ｂであれば、アイテム１２（ＫｅｙとＶａｌｕｅのセット）はＫｅｙ−Ｖａｌｕｅストレージサーバ機能５Ｂ（サーバＢ）、Ｂ＜Ｈａｓｈ（Ｋｅｙ）≦Ｃであれば、アイテム１２（ＫｅｙとＶａｌｕｅのセット）は、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ｃ（サーバＣ）、Ｃ＜Ｈａｓｈ（Ｋｅｙ）≦Ｄであれば、アイテム１２（ＫｅｙとＶａｌｕｅのセット）はＫｅｙ−Ｖａｌｕｅストレージサーバ機能５Ｄ（サーバＤ）に保持されていることになる。
【００５１】
Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７が複数存在する場合でも、Ｋｅｙ１０から対応するＫｅｙ−Ｖａｌｕｅストレージサーバ機能５を特定するハッシュ関数が共有されていればよい。このように、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５は独立しており、互いにデータをやりとりすることはないため、ノード１を増やしていけば性能がスケーラブルに向上する。
【００５２】
前述したように、メモリ２に保存するだけでは信頼性のあるストレージとはいえない。そこで、メモリ２だけでなく、ディスク３にもデータを保存することになる。普通にやるとアイテム１２が変更されるごとに、ディスク３に書き込み、書き込みが確認できてから応答を返す（同期型）。
【００５３】
しかし、これでは、ライトスルー（Ｗｒｉｔｅ−ｔｈｒｏｕｇｈ）キャッシュ（ＣＰＵがメモリに書き込むと同時にキャッシュに書き込み方式）と同じであり、メモリ２を使うメリットが無くなる。
【００５４】
そこで、本実施形態では、図４に模式的に示すように、Ｋｅｙ−Ｖａｌｕｅストレージを２段階の間接参照構成としている。
【００５５】
１段階目のアイテム１２Ａは、Ｋｅｙ１０とＶａｌｕｅ１１のハッシュ値（＝Ｈａｓｈ（Ｖａｌｕｅ）１３と表記する）である（アイテム１２Ａ＝＜Ｋｅｙ，Ｈａｓｈ（Ｖａｌｕｅ）＞）。
【００５６】
２段階目のアイテム１２Ｂは、Ｈａｓｈ（Ｖａｌｕｅ）１３とＶａｌｕｅ１１である（アイテム１２Ｂ＝＜Ｈａｓｈ（Ｖａｌｕｅ），Ｖ＞）。Ｈａｓｈ（Ｖａｌｕｅ）１３は長くても数十バイトの固定長となる。つまり、まとめると以下のようになる。
【００５７】
１段目：＜Ｋｅｙ、Ｈａｓｈ（Ｖａｌｕｅ）＞
２段目：＜Ｈａｓｈ（Ｖａｌｕｅ）、Ｖａｌｕｅ＞
【００５８】
これにより、１段階目のアイテム１２Ａのサイズを小さくすることができる。例えば代表的なハッシュアルゴリズムであるＳＨＡ（Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ）−１は２０バイト長である。多くのストレージではブロックサイズを４Ｋバイトとしているため、ＳＨＡ−１にすると、約２０分の１のサイズになる。
【００５９】
図８は、図４に模式的に示したＫｅｙ−Ｖａｌｕｅストレージにおける２段階の間接参照を、分散ストレージシステムのＫｅｙ−Ｖａｌｕｅストレージサーバと関連させて模式的に示す図である。Ｋｅｙ−ＶａｌｕｅストレージサーバＡは、ハッシュ値Ｈａｓｈ（Ｋｅｙ）によって選択され、１段目：＜Ｋｅｙ、Ｈａｓｈ（Ｖａｌｕｅ）＞を格納する。この場合、＜Ｋｅｙ、Ｈａｓｈ（Ｖａｌｕｅ）＞は、Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４（図１参照）への書き込みに同期して、ディスク３に書き込む（同期レプリケーション）。Ｋｅｙ−ＶａｌｕｅストレージサーバＢは、Ｈａｓｈ（Ｖａｌｕｅ）１３の値によって選択され、２段目：＜Ｈａｓｈ（Ｖａｌｕｅ）、Ｖａｌｕｅ＞をＫｅｙ−Ｖａｌｕｅストレージ用メモリ４への書き込み、ディスク３へは非同期で書き込む（非同期レプリケーション）。
【００６０】
次に、本実施形態における、Ｋｅｙ−Ｖａｌｕｅストレージの２段階間接参照におけるＲＥＡＤ／ＷＲＩＴＥのフローを説明する。図５は、本実施形態におけるＷＲＩＴＥの処理フローを示す流れ図である。
【００６１】
ディスクに格納されるキーＫとバリューＶの対であるアイテム＜Ｋ，Ｖ＞が与えられる、すなわち、ＰＵＴ（Ｋ，Ｖ）命令を受信すると（ステップＳ１）、まず、Ｖからハッシュ計算を行い、Ｈａｓｈ（Ｖ）を求める（ステップＳ２）。
【００６２】
そして、ＰＵＴ（Ｋ，Ｈａｓｈ（Ｖ））、ＰＵＴ（Ｈａｓｈ（Ｖ）、Ｖ）、すなわちアイテム１２Ａ（＜Ｋ、Ｈａｓｈ（Ｖ）＞）と、アイテム１２Ｂ（＜Ｈａｓｈ（Ｖ）、Ｖ＞）をＰｕｔする（ステップＳ３）。アイテム１２Ａ（＜Ｋ、Ｈａｓｈ（Ｖ）＞）と、アイテム１２Ｂ（＜Ｈａｓｈ（Ｖ）、Ｖ＞を、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５（図１参照）のそれぞれのＫｅｙ−Ｖａｌｕｅストレージ用メモリ４へ書き込む。この２つのアイテム１２のＫｅｙ−Ｖａｌｕｅストレージ用メモリ４への格納は並列で行うことができる。アイテム１２Ａ（＜Ｋ、Ｈａｓｈ（Ｖ）＞）は同期方式でディスク３に格納する。
【００６３】
アイテム１２Ａ（＜Ｋ、Ｈａｓｈ（Ｖ）＞）のＰｕｔ応答が返ってきた時点で、書き込み完了応答を返す（ステップＳ４）。アイテム１２Ｂは、ディスク３に非同期に格納する。
【００６４】
図６は、本実施形態におけるＲＥＡＤの処理フローを示す流れ図である。
【００６５】
ＧＥＴ（Ｋ）命令を受信する（ステップＳ１１）、ＧＥＴ（Ｋ）命令を実行し、戻り値をＨａｓｈ（Ｖ）とする（ステップＳ１２）。すなわち読み出し時には、Ｋｅｙ１０からアイテム１２Ａ（＜Ｋ、Ｈａｓｈ（Ｖ）＞）がＧｅｔされる。
【００６６】
アイテム１２Ａ（＜Ｋ、Ｈａｓｈ（Ｖ）＞）が見つかった場合、次にＨａｓｈ（Ｖ）からアイテム１２Ｂ（＜Ｈａｓｈ（Ｖ）、Ｖ＞）をＧｅｔし（Ｇｅｔ（Ｈａｓｈ（Ｖ））を実行）（ステップＳ１４）、戻り値をＶとする（ステップＳ１４）。
【００６７】
アイテム１２Ａ（＜Ｋ、Ｈａｓｈ（Ｖ）＞）が見つからなかったときには、１段目のアイテム１２ＡのＫｅｙに対応するＨａｓｈ（Ｖ）が存在しないことを意味するため、「Ｎｏｔ  Ｆｏｕｎｄ」を返す（ステップＳ１５）。
【００６８】
アイテム１２Ａが見つかり、アイテム１２Ｂ（＜Ｈａｓｈ（Ｖ），Ｖ＞）が見つかったときは（ステップＳ１６のＹ分岐）、Ｖを返す。
【００６９】
アイテム１２Ａが見つかったが、アイテム１２Ｂ（＜Ｈａｓｈ（Ｖ），Ｖ＞）が見つからなかったときは（ステップＳ１６のＮ分岐）、ＷＲＩＴＥの途中段階であるか、なんらかのエラーが発生したことを意味するので、エラーを返す（ステップＳ１８）。
【００７０】
つまり、アイテム１２Ｂ（＜Ｈａｓｈ（Ｖ）、Ｖ＞）の格納に失敗した場合、またはアイテム１２Ｂが格納されるより前にシステム障害が起きた場合には、読み出し時にアイテム１２ＢがＧｅｔできないので、データの書き込みに失敗したことがわかる。
【００７１】
高信頼なストレージにおいて、最も信頼度の高いストレージは、書き込み要求に対して、応答が返ってきた書き込みは、必ず、ストレージの内容に反映されている、というものである。ただし、この確実な反映を、ディスクへの保存によって行った場合、結局は、ディスクの応答時間に制限されることになり、メモリを利用する効果が無くなってしまう。
【００７２】
そこで、メモリ上のデータのディスクへの保存については非同期で行う方法が考えられる。しかし、メモリ上のデータのディスクへの保存を非同期で行うと、ディスクに保存される前に障害が起きた場合に、データがディスクに書き込まれない状態になる。
【００７３】
さらに問題なのは、この状態において、メモリ上のデータのうち、どのデータがディスクに書き込まれなかったのかが判断できない、ということである。つまり、どのデータが正しいのかがわからないということになり、データ全体が信用できないということになる。
【００７４】
これに対して、本実施形態によれば、メモリ上のデータのディスクへの書き込みが正常に行われたか否かを検出することができる。つまり、どのデータが正しいかがわかる。このように、データ本体よりも、はるかにデータ量の小さいハッシュ値をディスクに保存しておくだけで、データの信頼性を高めることができる。
【００７５】
上記した実施形態の具体例を説明する。図９は、本発明の一実施形態のＰｕｔ（Ｋ、Ｖ）命令（上記ＰＵＴ（Ｋ，Ｖ）と等価）を説明する図である。図１０は、本発明の一実施形態のＧｅｔ（Ｋ）命令（上記ＧＥＴ（Ｋ））と等価）を説明する図である。Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７は、キャッシュ管理部７１と、キャッシュメモリ７２と、Ｈａｓｈ計算部７３と、サーバインタフェース（Ｉ／Ｆ）部７４と、サーバ検索部７５を備えている。Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａ、５Ｂは、サーバ管理部５１と、メモリ４と、ハードディスク３を備えている。なお、図９、図１０において、○で囲んだ数字は、以下の処理番号に対応する。
【００７６】
はじめに、Ｐｕｔ命令について説明する。図９を参照すると、
（１）アプリケーション６からＰｕｔ（Ｋ，Ｖ）命令がＫｅｙ−Ｖａｌｕｅストレージクライアント機能７に発行される。
【００７７】
（２）キャッシュ管理部７１は、アプリケーション６からのＰｕｔ（Ｋ，Ｖ）命令を受け取り、キーとバリューの対（アイテム）＜Ｋ，Ｖ＞をキャッシュメモリ７２に格納する。
【００７８】
（３）Ｈａｓｈ計算部７３は、バリューＶのハッシュ値Ｈａｓｈ（Ｖ）を計算し、キャッシュ管理部７１に与える。
【００７９】
（４）キャッシュ管理部７１は、Ｈａｓｈ計算部７３からバリューＶのハッシュ値Ｈａｓｈ（Ｖ）を受け取ると、サーバインタフェース部７４に対して格納指示を出す。キャッシュ管理部７１は、キーとバリューのハッシュ値の対＜Ｋ，Ｈａｓｈ（Ｖ）＞は、同期型のＰｕｔ命令であるＰｕｔｓｙｎｃ（Ｋ，Ｈａｓｈ（Ｖ））、バリューのハッシュ値とバリューの対＜Ｈａｓｈ（Ｖ）、Ｖ＞は、非同期型のＰｕｔ命令であるＰｕｔａｓｙｎｃ（Ｈａｓｈ（Ｖ）、Ｖ）の格納命令を発行する。サーバ検索部７５は、＜Ｋ，Ｈａｓｈ（Ｖ）＞、＜Ｈａｓｈ（Ｖ），Ｖ＞を格納するサーバを検索する。前述したとおり、サーバ検索部７５は、アイテム＜Ｋ，Ｖ＞を保存するサーバを、ハッシュ値Ｈａｓｈ（Ｋ）で特定する。図９の例では、＜Ｋ，Ｈａｓｈ（Ｖ）＞、＜Ｈａｓｈ（Ｖ），Ｖ＞を保存するサーバは、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａ、５Ｂとなる。
【００８０】
（５）サーバインタフェース部７４は、Ｐｕｔｓｙｎｃ（Ｋ，Ｈａｓｈ（Ｖ））を、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａに出力する。また、サーバインタフェース部７４は、Ｐｕｔａｓｙｎｃ（Ｈａｓｈ（Ｖ），Ｖ）を、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ｂに出力する。
【００８１】
（６）同期書き込み命令であるＰｕｔｓｙｎｃ（Ｋ，Ｈａｓｈ（Ｖ））命令を受けたＫｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａのサーバ管理部５１は、Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４と、ディスク３に、＜Ｋ，Ｈａｓｈ（Ｖ）＞を格納する（６−１）。非同期書き込み命令であるＰｕｔａｓｙｎｃ（Ｈａｓｈ（Ｖ），Ｖ）命令を受けたＫｅｙ−Ｖａｌｕｅストレージサーバ機能５Ｂのサーバ管理部５１は、まず、Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４に＜Ｈａｓｈ（Ｖ）、Ｖ＞を格納する（６−２）。ディスク３へは、Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４に格納した＜Ｈａｓｈ（Ｖ）、Ｖ＞を非同期で書き込む（非同期レプリケーション）。
【００８２】
（７）Ｋｅｙ−Ｖａｌｕｅストレージ機能５Ａのサーバ管理部５１は、Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４とディスク３への、＜Ｋ，Ｈａｓｈ（Ｖ）＞の格納が完了すると、Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７のサーバインタフェース部７４に対して、完了応答を返す（７−１）。Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ｂのサーバ管理部５１は、Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４への、＜Ｋ，Ｈａｓｈ（Ｖ）＞の格納が完了すると、Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７のサーバインタフェース部７４に、完了応答を返す（７−２）。
【００８３】
（８）Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７のサーバインタフェース部７４は、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａ、５Ｂから完了応答を受け取ると、キャッシュ管理部７１に格納完了を返す。
【００８４】
（９）サーバインタフェース部７４から格納完了を受けとったキャッシュ管理部７１は、アプリケーション６に格納完了を返す。
【００８５】
次に、Ｇｅｔ（Ｋ）命令について説明する。図１０を参照すると、
（１）アプリケーション６からＧｅｔ（Ｋ）命令がＫｅｙ−Ｖａｌｕｅストレージクライアント機能７に発行される。
【００８６】
（２）キャッシュ管理部７１は、アプリケーション６からのＧｅｔ（Ｋ）命令を受け取り、キャッシュメモリ７２をキーＫで検索する。キャッシュメモリ７２に、キーとバリューの対（アイテム）＜Ｋ，Ｖ＞が存在していれば（キャッシュヒット時）、キャッシュメモリ７２から読み出したバリューＶを応答としてアプリケーション６に返す（Ｋｅｙ−Ｖａｌｕｅストレージ機能５へのアクセスは行われない）。
【００８７】
（３）キャッシュメモリ７２にキーとバリューの対＜Ｋ，Ｖ＞が存在しない場合（キャッシュミスヒット時）、キャッシュ管理部７１は、サーバインタフェース部７４に対して検索指示Ｇｅｔ（Ｋ）を出す。サーバ検索部７５は、キーＫのハッシュ値を計算し、＜Ｋ，Ｖ＞を保持するサーバを、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａと判断し、サーバインタフェース部７４に伝える。
【００８８】
（４）サーバインタフェース部７４は、Ｇｅｔ（Ｋ）を、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａに発行する。
【００８９】
（５）Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａのサーバ管理部５１は、Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４をキーＫで検索し、＜Ｋ，Ｈａｓｈ（Ｖ）＞のＨａｓｈ（Ｖ）を取得する。
【００９０】
（６）Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａのサーバ管理部５１は応答＜Ｋ，Ｈａｓｈ（Ｖ）＞をＫｅｙ−Ｖａｌｕｅストレージクライアント機能７に応答として返す。
【００９１】
（７）Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７のサーバインタフェース部７４は、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ａのサーバ管理部５１から応答＜Ｋ，Ｈａｓｈ（Ｖ）＞を受け取る。サーバ検索部７５は、Ｈａｓｈ（Ｖ）をキーとして、そのハッシュ値Ｈａｓｈ（Ｈａｓｈ（Ｖ））から、＜Ｈａｓｈ（Ｖ）、Ｖ＞を保存するサーバをＫｅｙ−Ｖａｌｕｅストレージサーバ機能５Ｂと特定し、サーバインタフェース部７４に伝える。サーバインタフェース部７４は、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ｂのサーバ管理部５１に対して、Ｇｅｔ（Ｈａｓｈ（Ｖ））命令を発行する。
【００９２】
（８）Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ｂのサーバ管理部５１は、Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ４をキーＨａｓｈ（Ｖ）で検索し、＜Ｈａｓｈ（Ｖ）、Ｖ＞のＶを取得する。
【００９３】
（９）Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ｂのサーバ管理部５１は、応答として＜Ｈａｓｈ（Ｖ）、Ｖ＞をＫｅｙ−Ｖａｌｕｅストレージクライアント機能７に返す。
【００９４】
（１０）Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７のサーバインタフェース部７４は、Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能５Ｂのサーバ管理部５１から応答＜Ｈａｓｈ（Ｖ）、Ｖ＞を受け取ると、キャッシュ管理部７１に応答Ｖを返す。
【００９５】
（１１）Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能７のキャッシュ管理部７１は、サーバインタフェース部７４から応答Ｖを受け取ると、アプリケーション６にＧｅｔ（Ｋ）に対する応答Ｖを返す。キャッシュ管理部７１はキャッシュメモリ７２に、キーＫと取得したバリューＶの対＜Ｋ、Ｖ＞を格納するようにしてもよい。
【００９６】
＜実施形態２＞
本実施形態では、コンテンツアドレスストレージ（Ｃｏｎｔｅｎｔｓ  Ａｄｄｒｅｓｓ  Ｓｔｏｒａｇｅ：ＣＡＳ）を利用する。コンテンツアドレスストレージは、コンテンツアウェアトレージ、コンテンツアーカイブストレージとも呼ばれ、データを、コンテンツ（バイトストリーム）とメタデータからなるオブジェクトとして保存する。その際、オブジェクトを識別するオブジェクトＩＤ（「コンテンツアドレス」という）を生成し、要求元（ユーザ、アプリケーション）に返す。ユーザは、オブジェクトＩＤを使用してオブジェクトの読み出しを行う。特に制限されないが、オブジェクトＩＤはハッシュアルゴリズム（ＳＨＡ−１、ＳＨＡ−２５６）等が用いられる。メタデータは例えばコンテンツの属性情報（例えば生成時刻、保持期間、コンテンツサイズ、コメント等）からなる。
【００９７】
ＣＡＳの場合、コンテンツアドレス（ＣＡ）がハッシュ値の代わりになる。つまり、バリューＶのコンテンツアドレスをＣＡ（Ｖ）とすると、
１段目が＜Ｋ、ＣＡ（Ｖ）＞、
２段目が＜ＣＡ（Ｖ）、Ｖ＞
となる。２段目はＣＡＳそのものである。
【００９８】
しかし、この構成は問題がある。ＣＡはハッシュ値も含むことが多いが、それ以外のフィールドも含んでおり、ＣＡＳにデータを格納すると、ＣＡが返ってくるようになっている。つまり、ＣＡＳの応答が返ってくるまでは、１段目の＜Ｋ、ＣＡ（Ｖ）＞がＰｕｔできないことになる。ＣＡＳは、一般的には、応答時間の早いストレージではない。
【００９９】
そこで、本実施形態では、間接参照をもう１段増やして以下のような構成とする。
１段目：＜Ｋ、Ｈａｓｈ（Ｖ）＞
２段目：＜Ｈａｓｈ（Ｖ）、ＣＡ（Ｖ）＞
３段目：＜ＣＡ（Ｖ）、Ｖ＞  ＝  ＣＡＳ
【０１００】
図７は、本実施形態のアイテム１２の関連を示す図である。図７において、
１段目（＜Ｋｅｙ，Ｈａｓｈ（Ｖａｌｕｅ）＞）がアイテム１２Ａ、
２段目（＜Ｈａｓｈ（Ｖａｌｕｅ），ＣＡ（Ｖａｌｕｅ）＞）がアイテム１２Ｂ、
３段目（＜ＣＡ（Ｖａｌｕｅ），Ｖａｌｕｅ＞）がアイテム１２Ｃ
となる。アイテム１２Ｃは、ＣＡＳである。
【０１０１】
書き込み時には、１段目のアイテム１２Ａ（＜Ｋ、Ｈａｓｈ（Ｖ）＞）を格納した時点で応答を返すことができるため、高速な応答が可能である。
【０１０２】
前記第１の実施形態と同様、２段目と３段目は非同期で格納するが、これらの格納が終わる前に、ディスク等に障害が起きた場合、１段目で得たＨａｓｈ（Ｖ）１３をＫｅｙにしてＧｅｔすると、２段目、もしくは３段目を得ることができないので、データが信頼できないことを検出できる。
【０１０３】
ＣＡＳ構成において、ストレージ内の同じファイルの複数のコピーは保存されない、すなわち、重複保存は行われず保存データ量が削減可能である。
【産業上の利用可能性】
【０１０４】
本発明によれば、スケーラブルに拡張可能な分散ストレージにおいて、メモリの高速性を維持しつつ、信頼性を向上させることができる。【０１０５】
本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。【０１０６】
特に制限されないが、上記本発明、実施形態の全て又は一部は以下のように付記される。
（付記１）
キーとバリューを対応させて格納し、キーを検索してバリューを得るキー・バリュー型データストア構成のストレージシステムであって、
キーとバリューの対の書き込み要求に対して、
前記バリューのハッシュ値を計算し、
前記キーと、前記バリューのハッシュ値をそれぞれキーとバリューとする第１の対と、
前記バリューのハッシュ値と、前記バリューをそれぞれキーとバリューとする第２の対と、
をそれぞれ記憶装置に格納し、
読み出し要求に対して、
前記読み出し要求で指定されたキーで前記記憶装置を検索して、前記キーと前記第１の対をなすバリューのハッシュ値を取得し、
取得した前記バリューのハッシュ値で前記記憶装置を検索して、前記バリューのハッシュ値と前記第２の対をなすバリューを取得し、その際、前記バリューのハッシュ値で前記記憶装置を検索した結果、前記バリューのハッシュ値と前記第２の対をなすバリューが前記記憶装置に存在しない場合、前記第１の対が前記記憶装置に正常に保存されなかったものと判断する手段を備えた、ストレージシステム。
（付記２）
キーとバリューの対の書き込み要求に対して、
前記第１の対と前記第２の対を、揮発性の記憶装置にそれぞれ保存し、
前記第１の対は、前記揮発性の記憶装置への保存とともに又はその後、前記書き込み要求の応答を要求元に返す前に、不揮発性の記憶装置に保存し、
前記第２の対は、前記揮発性の記憶装置への保存とともに又はその後の任意のタイミングで不揮発性の記憶装置に保存する、付記１記載のストレージシステム。
（付記３）
読み出し時、
前記キーによる検索の結果、前記キーと前記第１の対をなすバリューのハッシュ値が見つかった場合、次に、前記バリューのハッシュ値をキーとして前記記憶装置を検索して前記第２の対のバリューを取得し、
前記キーと前記第１の対をなすバリューのハッシュ値が見つかり、前記バリューのハッシュ値と前記第２の対をなすバリューが見つかった場合、前記バリューを読み出し結果として返し、
前記キーと前記第１の対をなすバリューのハッシュ値が見つからなかったときには、前記キーに対するバリューが存在しないことを示す情報を返し、
前前記キーと前記第１の対をなすバリューのハッシュ値が見つかり、且つ、前記バリューのハッシュ値と前記第２の対をなすバリューが見つからなかったときは、エラーを返す、付記１又は２記載のストレージシステム。
（付記４）
キーとバリューを対にして格納し、キーからバリューを得ることができるデータ構成を持ち、
キーとバリューの書き込み時、前記キーと前記バリューのハッシュ値の第１の対と、前記バリューのハッシュ値と前記バリューの第２の対を、揮発性の記憶装置にそれぞれ格納しておき、
前記第１の対は応答を返す前に、不揮発性の記憶装置に保存し、
前記第２の対は、揮発性の記憶装置に保存しておき、任意のタイミングで不揮発性の記憶装置に保存する手段と、
キーからバリューを得る読み出し時に、前記第１の対からバリューのハッシュ値を得て前記第２の対を読み出す処理において、前記第２の対が存在しないときには、データが正常に格納されなかったと判断する手段を備えた、ストレージシステム。
（付記５）
データ及びメタデータをオブジェクトとして保存するとオブジェクト識別子を生成し該オブジェクト識別子であるコンテンツアドレスを返し、該コンテンツアドレスを用いてオブジェクトにアクセスするコンテンツアドレスストレージ（ＣＡＳ）を備え、
第１の対をキーとバリューのハッシュ値の対とし、
第２の対を、前記バリューのハッシュ値とバリューの対のかわりに、前記バリューのハッシュ値をキー、前記バリューのコンテンツアドレスをバリューとする対とし、
前記バリューを、前記コンテンツアドレスストレージに保存する、付記１乃至４のいずれか１に記載のストレージシステム。
（付記６）
ネットワーク接続される複数ノードがそれぞれ、付記１乃至５のいずれか１に記載のストレージシステムを備えた分散ストレージシステム。
（付記７）
書き込み時、キーとバリューを対応させて格納し、読み出し時、キーで検索してバリューを得る複数のキー・バリュー型ストレージサーバと、
キーとバリューの対の書き込み要求を受け、
前記バリューのハッシュ値を計算し、
前記キーと前記バリューのハッシュ値をそれぞれキーとバリューとする第１の対と、
前記バリューのハッシュ値と前記バリューをそれぞれキーとバリューとする第２の対と、
を生成し、
前記第１の対のキーとバリューを対応させて第１のキー・バリュー型ストレージサーバに保存し、
前記第２の対のキーとバリューを対応させて第２のキー・バリュー型ストレージサーバに保存するストレージクライアントと、
を備えた、分散ストレージシステム。
（付記８）
前記ストレージクライアントは、キーからバリューを得る読み出し要求を受けると、
前記第１のキー・バリュー型ストレージサーバに対して前記キーで検索して、前記キーと前記第１の対をなす前記バリューのハッシュ値を取得し、
前記第２のキー・バリュー型ストレージサーバに対して前記バリューのハッシュ値で検索して、前記バリューのハッシュ値と前記第２の対をなす前記バリューを取得し、前記検索処理において、前記バリューのハッシュ値と前記バリューの前記第２の対が存在しないときには、前記第１の対が前記第１のキー・バリュー型ストレージサーバに正常に保存されなかったものと判断する、付記７記載の分散ストレージシステム。
（付記９）
前記ストレージクライアントは、前記第１、第２の対のキーのハッシュ値に基づき、前記第１、第２の対のキーとバリューを保存する第１、第２のキー・バリュー型ストレージサーバを決定する、付記７又は８記載の分散ストレージシステム。
（付記１０）
前記第１のキー・バリュー型ストレージサーバが、第１の揮発性の記憶装置と第１の不揮発性の記憶装置を備え、
前記第２のキー・バリュー型ストレージサーバが、第２の揮発性の記憶装置と第２の不揮発性の記憶装置を備え、
前記第１のキー・バリュー型ストレージサーバは、前記第１の対のキーとバリューを前記第１の揮発性の記憶装置に保存し、
前記第２のキー・バリュー型ストレージサーバは、前記第２の対のキーとバリューを前記第２の揮発性の記憶装置に保存し、
前記第１のキー・バリュー型ストレージサーバは、書き込み要求に対する応答を返す前に、前記第１の対のキーとバリューを前記第１の不揮発性の記憶装置に保存し、
前記第２のキー・バリュー型ストレージサーバは、前記第２の対のキーとバリューを任意のタイミングで、前記第２の不揮発性の記憶装置に保存する、付記７乃至９のいずれか一に記載の分散ストレージシステム。
（付記１１）
前記ストレージクライアントは、キーとバリューの対の書き込み要求を受けて、キーとバリューの対をキャッシュメモリに格納し、
キーからバリューを得る読み出し要求に対して、前記キャッシュメモリに前記キーと、前記キーに対応するバリューが格納されている場合、前記キャッシュメモリから前記キーに対応するバリューを読み出して応答として返す、付記７乃至９のいずれか一に記載の分散ストレージシステム。
（付記１２）
キーとバリューを対応させて格納し、キーを検索してバリューを得るキー・バリュー型ストレージのアクセス方法であって、
キーとバリューの対の書き込み要求に対して、
前記バリューのハッシュ値を計算し、
前記キーと、前記バリューのハッシュ値をそれぞれキー、バリューとする第１の対と、
前記バリューのハッシュ値と、前記バリューをそれぞれキー、バリューとする第２の対と、
をそれぞれ記憶装置に格納し、
読み出し要求に対して、
前記読み出し要求で指定されたキーで前記記憶装置を検索して、前記キーと前記第１の対をなすバリューのハッシュ値を取得し、
取得した前記バリューのハッシュ値で前記記憶装置を検索して、前記バリューのハッシュ値と前記第２の対をなすバリューを取得し、その際、前記バリューのハッシュ値で前記記憶装置を検索した結果、前記バリューのハッシュ値と前記第２の対をなすバリューが前記記憶装置に存在しない場合、前記第１の対が前記記憶装置に正常に保存されなかったものと判断する、ストレージアクセス方法。
（付記１３）
キーとバリューの対の書き込み要求に対して、
前記第１の対と前記第２の対を、揮発性の記憶装置にそれぞれ保存し、
前記第１の対は、前記揮発性の記憶装置への保存とともに又はその後、前記書き込み要求の応答を要求元に返す前に、不揮発性の記憶装置に保存し、
前記第２の対は、前記揮発性の記憶装置への保存とともに又はその後の任意のタイミングで不揮発性の記憶装置に保存する、付記１２記載のストレージアクセス方法。
（付記１４）
読み出し時、前記キーによる検索の結果、前記キーと前記第１の対をなすバリューのハッシュ値が見つかった場合、次に、前記バリューのハッシュ値をキーとして前記記憶装置を検索して前記第２の対のバリューを取得し、
前記キーと前記第１の対をなすバリューのハッシュ値が見つかり、前記バリューのハッシュ値と前記第２の対をなすバリューが見つかった場合、前記バリューを読み出し結果として返し、
前記キーと前記第１の対をなすバリューのハッシュ値が見つからなかったときには、前記キーに対するバリューが存在しないことを示す情報を返し、
前前記キーと前記第１の対をなすバリューのハッシュ値が見つかり、且つ、前記バリューのハッシュ値と前記第２の対をなすバリューが見つからなかったときは、エラーを返す、付記１２又は１３記載のストレージアクセス方法。
（付記１５）
キーとバリューを対にして格納し、キーからバリューを得ることができるデータ構成を持ち、
キーとバリューの書き込み時、前記キーと前記バリューのハッシュ値の第１の対と、前記バリューのハッシュ値と前記バリューの第２の対を揮発性の記憶装置にそれぞれ格納しておき、
前記第１の対は、応答を返す前に、不揮発性の記憶装置に保存し、
前記第２の対は、揮発性の記憶装置に保存しておき、任意のタイミングで不揮発性の記憶装置に保存し、
キーからバリューを得る読み出し処理時に、前記第１の対からバリューのハッシュ値を得て前記第２の対を読み出す処理において、前記第２の対が存在しないときには、データが正常に格納されなかったと判断する、ストレージアクセス方法。
（付記１６）
データ及びメタデータをオブジェクトとして保存するとオブジェクト識別子を生成し該オブジェクト識別子であるコンテンツアドレスを返し、該コンテンツアドレスを用いてオブジェクトにアクセスするコンテンツアドレスストレージ（ＣＡＳ）に、キーとバリューの対の前記バリューを保存し、
第１の対をキーとバリューのハッシュ値の対とし、
第２の対を、前記バリューのハッシュ値とバリューの対のかわりに、前記バリューのハッシュ値をキー、前記バリューのコンテンツアドレスをバリューとする対とする、付記１２乃至１５のいずれか一に記載のストレージアクセス方法。
（付記１７）
アプリケーションからキーとバリューの対の書き込み要求を受けたストレージクライアントは、
前記バリューのハッシュ値を計算し、
前記キーと前記バリューのハッシュ値をそれぞれキーとバリューとする第１の対と、
前記バリューのハッシュ値と前記バリューをそれぞれキーとバリューとする第２の対と、
を生成し、
前記第１の対のキーとバリューを対応させて第１のキー・バリュー型ストレージサーバに保存し、
前記第２の対のキーとバリューを対応させて第２のキー・バリュー型ストレージサーバに保存する、分散ストレージアクセス方法。
（付記１８）
前記ストレージクライアントは、アプリケーションからキーを指定した読み出し要求を受けると、
前記第１のキー・バリュー型ストレージサーバに対して前記キーによる検索を行い、前記キーと前記第１の対をなす前記バリューのハッシュ値を取得し、
前記第２のキー・バリュー型ストレージサーバに対して前記バリューのハッシュ値による検索を行い、前記バリューのハッシュ値と前記第２の対をなす前記バリューを取得する処理を実行し、その際、前記検索処理において、前記バリューのハッシュ値と前記バリューの前記第２の対が存在しないときには、前記第１の対が前記第１のキー・バリュー型ストレージサーバに正常に保存されなかったものと判断する、付記１７記載の分散ストレージアクセス方法。
（付記１９）
前記ストレージクライアントは、前記第１、第２の対のキーのハッシュ値に基づき、前記第１、第２の対のキーとバリューを保存する第１、第２のキー・バリュー型ストレージサーバを決定する、付記１７又は１８記載の分散ストレージアクセス方法。
（付記２０）
前記第１のキー・バリュー型ストレージサーバが、第１の揮発性の記憶装置と第１の不揮発性の記憶装置を備え、
前記第２のキー・バリュー型ストレージサーバが、第２の揮発性の記憶装置と第２の不揮発性の記憶装置を備え、
前記第１、第２のキー・バリュー型ストレージサーバは、
前記第１の対のキーとバリューを前記第１の揮発性の記憶装置に、
前記第２の対のキーとバリューを前記第２の揮発性の記憶装置に、それぞれ保存し、
前記第１のキー・バリュー型ストレージサーバは、書き込み要求に対する応答を返す前に、前記第１の対のキーとバリューを前記第１の不揮発性の記憶装置に保存し、
前記第２のキー・バリュー型ストレージサーバは、前記第２の対のキーとバリューを任意のタイミングで前記第２の不揮発性の記憶装置に保存する、付記１７乃至１９のいずれか一に記載の分散ストレージアクセス方法。
（付記２１）
キーとバリューを対応させて格納し、キーを検索してバリューを得るキー・バリュー型データストア構成のストレージシステムを構成するコンピュータに、
キーとバリューの対の書き込み要求に対して、
前記バリューのハッシュ値を計算する処理と、
前記キーと、前記バリューのハッシュ値をそれぞれキー、バリューとする第１の対と、
前記バリューのハッシュ値と、前記バリューをそれぞれキー、バリューとする第２の対と、
をそれぞれ記憶装置に格納する処理と、
読み出し要求に対して、
前記読み出し要求で指定されたキーで前記記憶装置を検索して、前記キーと前記第１の対をなすバリューのハッシュ値を取得する処理と、
取得した前記バリューのハッシュ値で前記記憶装置を検索して、前記バリューのハッシュ値と前記第２の対をなすバリューを取得し、その際、前記バリューのハッシュ値で前記記憶装置を検索した結果、前記バリューのハッシュ値と前記第２の対をなすバリューが前記記憶装置に存在しない場合、前記第１の対が前記記憶装置に正常に保存されなかったものと判断する、処理と、
を実行させるプログラム。
（付記２２）
キーとバリューの対の書き込み要求に対して、
前記第１の対と前記第２の対を、揮発性の記憶装置にそれぞれ保存する処理と、
前記第１の対は、前記揮発性の記憶装置への保存とともに又はその後、前記書き込み要求の応答を要求元に返す前に、不揮発性の記憶装置に保存する処理と、
前記第２の対は、前記揮発性の記憶装置への保存とともに又はその後の任意のタイミングで不揮発性の記憶装置に保存するする処理と、
を前記コンピュータに実行させる付記２１記載のプログラム。
（付記２３）
読み出し時、
前記キーによる検索の結果、前記キーと前記第１の対をなすバリューのハッシュ値が見つかった場合、次に、前記バリューのハッシュ値をキーとして前記記憶装置を検索して前記第２の対のバリューを取得する処理と、
前記キーと前記第１の対をなすバリューのハッシュ値が見つかり、前記バリューのハッシュ値と前記第２の対をなすバリューが見つかった場合、前記バリューを読み出し結果として返す処理と、
前記キーと前記第１の対をなすバリューのハッシュ値が見つからなかったときには、前記キーに対するバリューが存在しないことを示す情報を返す処理と、
前前記キーと前記第１の対をなすバリューのハッシュ値が見つかり、且つ、前記バリューのハッシュ値と前記第２の対をなすバリューが見つからなかったときは、エラーを返す処理と、
を前記コンピュータに実行させる付記２１又は２２記載のプログラム。
（付記２４）
キーとバリューを対にして格納し、キーからバリューを得ることができるデータ構成を備えたストレージシステムを構成するコンピュータに、
キーとバリューのハッシュ値の第１の対と、
バリューのハッシュ値とバリューの第２の対を格納しておき、
前記第１の対は応答を返す前に、不揮発性の第１の記憶装置に保存し、
前記第２の対は、揮発性の第２の記憶装置に保存しておき、任意のタイミングで前記第１の記憶装置に保存し、
キーからバリューを得る読み出し処理時に、前記第１の対からバリューのハッシュ値を得て前記第２の対を読み出す処理において、前記第２の対が存在しないときには、データが前記第１の記憶装置に正常に格納されなかったと判断する処理を実行させるプログラム。
（付記２５）
データ及びメタデータをオブジェクトとして保存するとオブジェクト識別子を生成し該オブジェクト識別子であるコンテンツアドレスを返し、該コンテンツアドレスを用いてオブジェクトにアクセスするコンテンツアドレスストレージ（ＣＡＳ）に、キーとバリューの対の前記バリューを保存し、
第１の対をキーとバリューのハッシュ値の対とし、
第２の対を、前記バリューのハッシュ値とバリューの対のかわりに、前記バリューのハッシュ値をキー、前記バリューのコンテンツアドレスをバリューとする対とする処理を前記コンピュータに実行させる付記２１乃至２４のいずれか一に記載のプログラム。
【符号の説明】
【０１０７】
１  ノード
２  メモリ
３  ハードディスク（ディスク）
４  Ｋｅｙ−Ｖａｌｕｅストレージ用メモリ
５、５Ａ、５Ｂ、５Ｃ、５Ｄ  Ｋｅｙ−Ｖａｌｕｅストレージサーバ機能
６  アプリケーション
７  Ｋｅｙ−Ｖａｌｕｅストレージクライアント機能
８  ネットワーク
１０  Ｋｅｙ
１１  Ｖａｌｕｅ
１２  アイテム
１２Ａ  アイテム
１２Ｂ  アイテム
１２Ｃ  アイテム
１３  Ｈａｓｈ（Ｖａｌｕｅ）
１４  ＣＡ（Ｖａｌｕｅ）
５１  サーバ管理部
７１  キャッシュ管理部
７２  キャッシュメモリ
７３  Ｈａｓｈ計算部
７４  サーバインタフェース部
７５  サーバ検索部
【図１】
2010114006.tif 000003
【図２】
2010114006.tif 000004
【図３】
2010114006.tif 000005
【図４】
2010114006.tif 000006
【図５】
2010114006.tif 000007
【図６】
2010114006.tif 000008
【図７】
2010114006.tif 000009
【図８】
2010114006.tif 000010
【図９】
2010114006.tif 000011
【図１０】
2010114006.tif 000012
【国際調査報告】
2010114006.tif 000013
2010114006.tif 000014