(57)【特許請求の範囲】
【請求項１】
入力装置から受信したクエリを、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信したクエリに基づき、データの保存、検索を含む処理を実行する複数の前記サーバとを備える条件検索データベースクラスタシステムの条件検索データ保存方法であって、
前記ディスパッチャは、
前記入力装置から前記クエリを受信し、前記受信したクエリの内容を構文解析するステップと、
前記構文解析した結果、前記クエリが新規データの保存要求であると解析した場合に、前記クエリに付された元ファイルからkey値およびvalue値を抽出して、前記key値および前記value値それぞれの分解ファイルを作成するステップと、
前記key値に不連続および連続なハッシュ関数を用いてハッシュ値を計算し、コンシステントハッシュを適用して、前記key値の分解ファイルを保存する複数のサーバを決定するステップと、
前記value値に、不連続または連続なハッシュ関数を用いてハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバを決定するステップと、
前記決定したkey値の分解ファイルを保存するサーバそれぞれに、前記key値を含む前記元ファイルを送信するステップと、
前記決定したvalue値の分解ファイルを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信するステップと、を実行し、
前記key値の分解ファイルを保存するサーバそれぞれは、受信した前記key値を含む前記元ファイルを自身の記憶部に記憶するステップを実行し、
前記value値の分解ファイルを保存するサーバは、受信した前記key値を付した前記value値の分解ファイルを自身の記憶部に記憶するステップを実行し、
さらに、前記ディスパッチャは、
前記value値に、前記value値の分解ファイルを保存するサーバを決定するステップにおいて用いたハッシュ関数とは異なる不連続または連続なハッシュ関数を用いてハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバ以外のサーバを、前記value値の分解ファイルの複製データを保存するサーバに決定するステップと、
前記決定したvalue値の分解ファイルの複製データを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信するステップと、を実行し、
前記value値の分解ファイルの複製データを保存するサーバは、受信した前記key値を付した前記value値の分解ファイルを自身の記憶部に記憶するステップを実行すること
を特徴とする条件検索データ保存方法。
【請求項２】
入力装置から受信したクエリを、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信したクエリに基づき、データの保存、検索を含む処理を実行する複数の前記サーバとを備える条件検索データベースクラスタシステムであって、
前記ディスパッチャは、
前記入力装置から前記クエリを受信し、前記受信したクエリの内容を構文解析する構文解析部と、
前記構文解析した結果、前記クエリが新規データの保存要求であると解析した場合に、前記クエリに付された元ファイルからkey値およびvalue値を抽出して、前記key値および前記value値それぞれの分解ファイルを作成する分解ファイル作成部と、
前記key値に不連続および連続なハッシュ関数を用いてハッシュ値を計算し、コンシステントハッシュを適用して、前記key値の分解ファイルを保存する複数のサーバを決定し、
前記value値に、不連続または連続なハッシュ関数を用いてハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバを決定するハッシュ値計算部と、
前記決定したkey値の分解ファイルを保存するサーバそれぞれに、前記key値を含む前記元ファイルを送信し、
前記決定したvalue値の分解ファイルを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信する保存情報管理部と、を備え、
前記key値の分解ファイルを保存するサーバそれぞれは、記憶部を備えており、
受信した前記key値を含む前記元ファイルを当該記憶部に記憶し、
前記value値の分解ファイルを保存するサーバは、記憶部を備えており、
受信した前記key値を付した前記value値の分解ファイルを当該記憶部に記憶し、
前記ディスパッチャは、
前記ハッシュ値計算部が、前記value値の分解ファイルを保存するサーバを決定する際に用いたハッシュ関数とは異なる不連続または連続なハッシュ関数を用いて、前記value値のハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバ以外のサーバを、前記value値の分解ファイルの複製データを保存するサーバに決定し、
前記保存情報管理部が、前記決定したvalue値の分解ファイルの複製データを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信し、
前記value値の分解ファイルの複製データを保存するサーバは、記憶部を備えており、
受信した前記key値を付した前記value値の分解ファイルを当該記憶部に記憶すること
を特徴とする条件検索データベースクラスタシステム。
【請求項３】
入力装置から受信したクエリを、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信したクエリに基づき、データの保存、検索を含む処理を実行する複数の前記サーバとを備える条件検索データベースクラスタシステムの前記ディスパッチャであって、
前記入力装置から前記クエリを受信し、前記受信したクエリの内容を構文解析する構文解析部と、
前記構文解析した結果、前記クエリが新規データの保存要求であると解析した場合に、前記クエリに付された元ファイルからkey値およびvalue値を抽出して、前記key値および前記value値それぞれの分解ファイルを作成する分解ファイル作成部と、
前記key値に不連続および連続なハッシュ関数を用いてハッシュ値を計算し、コンシステントハッシュを適用して、前記key値の分解ファイルを保存する複数のサーバを決定し、
前記value値に、不連続または連続なハッシュ関数を用いてハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバを決定するハッシュ値計算部と、
前記決定したkey値の分解ファイルを保存するサーバそれぞれに、前記key値を含む前記元ファイルを送信し、
前記決定したvalue値の分解ファイルを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信する保存情報管理部と、を備え、
前記ハッシュ値計算部が、前記value値の分解ファイルを保存するサーバを決定する際に用いたハッシュ関数とは異なる不連続または連続なハッシュ関数を用いて、前記value値のハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバ以外のサーバを、前記value値の分解ファイルの複製データを保存するサーバに決定し、
前記保存情報管理部が、前記決定したvalue値の分解ファイルの複製データを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信すること
を特徴とするディスパッチャ。
【請求項４】
請求項１に記載の条件検索データ保存方法を、コンピュータである前記条件検索データベースクラスタシステムの各装置に実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上に分散配置されるサーバをクラスタ化してデータを格納する分散データベースの技術分野、および、大規模なデータ集合から、所定の条件で所望のデータを取得する検索技術の分野に属する。
【背景技術】
【０００２】
現在広く利用されているデータベース（ＤＢ）として、ＲＤＢ（Relational DataBase）が存在する。このＲＤＢの技術は、Row（行）、Column（列）からなる２次元のテーブル構造でデータを表現し、ＳＱＬ（Structured Query Language）言語等によるクエリに応じて、JOIN（結合）や正規化を実行することで、検索等の処理を実現することができる。但し、ＲＤＢでは、このようなテーブル構造をベースとした処理を行っているため、データの一貫性は保持し易いが、サーバの台数を増加させてスループット等の性能を高めるスケーラビリティの効果を得にくいという特徴がある。
【０００３】
これに対し、スケーラビリティの高い効果を得ることを最大目標としたデータベースの技術として、分散データベース（ＤＢ）が存在する。スケーラビリティを獲得するための方式としては、ＫＶＳ（Key Value Store）が代表的である（非特許文献１参照）。なお、スケーラビリティを重視したデータベース全体をＮｏＳＱＬとして分類こともある。
【０００４】
ＫＶＳでは、ＲＤＢのようにテーブル構造のデータを持つことはせず、検索対象としてkeyを予め設定し、そのkeyに対してハッシュ関数を適用することでＯ(1)若しくはＯ（log(N)）の計算量によるvalue検索を可能とし、上記の特性を得ている。但し、その代償としてＳＱＬレベルの検索や、トランザクション処理の一貫性等が不充分であることが知られている。この問題に関し、近年ＫＶＳの方式であっても、ＲＤＢレベルの検索等の操作を可能とするＮｅｗＳＱＬと分類されるデータベースの研究が進んできている。
【０００５】
特に、keyしか検索対象にできなかったＮｏＳＱＬの特性を解決する手段の１つとして、Multi-Keyの技術が知られている（非特許文献２参照）。この技術は、valueの複数の要素をkey化することにより、検索可能なkeyを柔軟に設定することが可能となる。
【０００６】
また、ＮｏＳＱＬの技術では、基本的にkeyの完全一致でしか検索できない問題がある。これに対し、文字列の前方部分一致や、値の範囲検索を可能する技術として、メタkeyによるタブレットと呼ばれるデータ構造を用いたり、コンシステントハッシュ（Consistent Hashing）において、keyを入力するハッシュ関数を、連続関数としたりする等、様々な手法が存在する。
なお、範囲検索とは、keyが仮に自然数からなるuserIDであるとした場合に、1000＜userID＜2000のユーザを検索するような処理である。この処理は本質的に、文字列の前方部分一致、若しくは後方部分一致と同じ処理内容となる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Giuseppe DeCandia，et al.，“Dynamo: Amazon’s Highly Available Key-value Store,” SOSP’07, October 14-17, 2007, Stevenson, Washington, USA，［online］、［平成23年7月21日検索］、インターネット<http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf>
【非特許文献２】Sudipto Das，et al.，“G-Store: A Scalable Data Store for Transactional Multi key Access in the Cloud,”SoCC’10, June 10-11, 2010, Indianapolis, Indiana, USA，［online］、［平成23年7月21日検索］、インターネット<http://www.cs.uwaterloo.ca/~kdaudjee/courses/cs848/papers/das10.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００８】
前記した非特許文献２に記載のMulti-Keyによりvalueの特定の要素をkey化して検索する方法では、基本的に、元データが配置されたサーバとは別のサーバにデータを複製するか、若しくは、そのデータの位置情報を示すポインタを保持する構成となってしまう。これは、データの配置を決定するハッシュ関数が、入力されるkeyによって、不連続なものと連続なものとが混在することになるためである。つまり、範囲検索を必要としない要素（例えば、ＯＮ／ＯＦＦ等の値、定型的な文字列等）については、不連続なＳＨＡ１（Secure Hash Algorithm 1）等のハッシュ関数が振り分けとして最も性能を出し得る。一方、範囲検索を必要とする要素については、連続なハッシュ関数を用いることにより、検索範囲を限定できる効果がある。よって、それぞれに利点を追求すると、入力されるkeyによって、データの配置を決定するハッシュ関数が異なり、別のサーバにデータを保存することになる。
【０００９】
また、データの複製を作成した場合、そのうちのどれかのデータに更新が発生すると、一貫性を担保するために、その更新を検知する必要がある。Multi-Keyで多くのkeyを設定すると、それだけ一貫性保持にかかるオーバヘッドが大きくなるという問題もある。
【００１０】
さらに、分散データベースでは、一般にデータは複製により冗長化される。コンシステントハッシュを適用している分散データベースでは、例えば、閉じたハッシュ空間において、ハッシュ値が属する領域を担当するサーバの隣の領域を担当しているサーバがその複製を保存する。
【００１１】
よって、keyとして扱う箇所の違いのための複製（key化した検索したいvalueの項目）と、冗長化のための複製とが別々に存在すると、本来１種類のデータに対して、冗長化数×検索パターン数（検索したいvalueの項目）のデータ量を要してしまい、一貫性の保持にかかる時間がさらに長大になるという問題がある。
【００１２】
一方、従来技術における前方部分一致や範囲検索は、基本的にはkeyに対して適用するものであった。しかし、多くのアプリケーションにおいて、範囲検索を行いたい対象は、userID等のkey情報ではなく、keyに紐付けられて格納されている、例えば、学業等の成績や、課金情報等のvalueの要素である。
【００１３】
このvalueの要素に対し、範囲検索を可能とすることは、データ全体の位置を恣意的に操作することになり、keyの検索にも強く影響を与える。従って、実質的にvalueの要素の都合でデータの位置を決定することはできなかった。
【００１４】
また、範囲検索の対象をkeyに絞ったとしても、次のような問題がある。
例えば、コンシステントハッシュを用いる場合には、keyの値を入力として順序関係を崩さない連続なハッシュ関数を使用せざるを得ない。もし、ここでmodulo演算等を含むような不連続関数を適用したとすると、検索対象がハッシュ値の全域になることは免れないため、局所性が排除されることになる。つまり、ある範囲にあるデータを検索するというそもそも局所性を必然とする処理に対して、データ配置自体が局所性を排除してしまっているので、枝刈り等の効率的な手段が介入できる余地のないことを示している。
【００１５】
しかし、局所性の概念は、偏りの排除の概念とは当然トレードオフの関係であり、局所性を活かすような配置（連続関数を用いた配置）とする場合、データのアクセス分布の局所性（偏り）もでてきてしまう。これは、値が異なったとしても、ある特定の範囲のkeyばかり何度も検索するようなアクセス分布を考えた場合では偏りが生じることから自明である。
【００１６】
また、事前に充分keyのアクセス分布を調査しておくことで、この偏りをある程度回避することができる。例えば、key:xに対しアクセス頻度をf(x)で表すと、コンシステントハッシュのハッシュ空間におけるハッシュ値の担当領域をf-1(x)で決定することで実現できる。つまり、アクセス頻度が高いところであれば、担当領域を少なくし、アクセス頻度が少ないところであれば、担当領域を広くすることで、サーバ負荷を均等にすることが可能となる。但し、アクセス分布に変更があった場合に、それに追従して担当領域を変更することは非常に難しく、強引に行えば、その負荷で通常の検索の性能が低下する可能性がある。
【００１７】
このような背景を鑑みて本発明がなされたのであり、本発明は、データの保存総量を抑えた上で、valueの要素（value値）による検索を可能とする、条件検索データ保存方法、条件検索データベースクラスタシステム、ディスパッチャ、およびプログラムを提供することを課題とする。
【課題を解決するための手段】
【００１８】
前記した課題を解決するため、請求項１に記載の発明は、入力装置から受信したクエリを、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信したクエリに基づき、データの保存、検索を含む処理を実行する複数の前記サーバとを備える条件検索データベースクラスタシステムの条件検索データ保存方法であって、前記ディスパッチャが、前記入力装置から前記クエリを受信し、前記受信したクエリの内容を構文解析するステップと、前記構文解析した結果、前記クエリが新規データの保存要求であると解析した場合に、前記クエリに付された元ファイルからkey値およびvalue値を抽出して、前記key値および前記value値それぞれの分解ファイルを作成するステップと、前記key値に不連続および連続なハッシュ関数を用いてハッシュ値を計算し、コンシステントハッシュを適用して、前記key値の分解ファイルを保存する複数のサーバを決定するステップと、前記value値に、不連続または連続なハッシュ関数を用いてハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバを決定するステップと、前記決定したkey値の分解ファイルを保存するサーバそれぞれに、前記key値を含む前記元ファイルを送信するステップと、前記決定したvalue値の分解ファイルを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信するステップと、を実行し、前記key値の分解ファイルを保存するサーバそれぞれが、受信した前記key値を含む前記元ファイルを自身の記憶部に記憶するステップを実行し、前記value値の分解ファイルを保存するサーバが、受信した前記key値を付した前記value値の分解ファイルを自身の記憶部に記憶するステップを実行し、さらに、前記ディスパッチャが、前記value値に、前記value値の分解ファイルを保存するサーバを決定するステップにおいて用いたハッシュ関数とは異なる不連続または連続なハッシュ関数を用いてハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバ以外のサーバを、前記value値の分解ファイルの複製データを保存するサーバに決定するステップと、前記決定したvalue値の分解ファイルの複製データを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信するステップと、を実行し、前記value値の分解ファイルの複製データを保存するサーバが、受信した前記key値を付した前記value値の分解ファイルを自身の記憶部に記憶するステップを実行することを特徴とする条件検索データ保存方法とした。
【００１９】
また、請求項２に記載の発明は、入力装置から受信したクエリを、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信したクエリに基づき、データの保存、検索を含む処理を実行する複数の前記サーバとを備える条件検索データベースクラスタシステムであって、前記ディスパッチャが、前記入力装置から前記クエリを受信し、前記受信したクエリの内容を構文解析する構文解析部と、前記構文解析した結果、前記クエリが新規データの保存要求であると解析した場合に、前記クエリに付された元ファイルからkey値およびvalue値を抽出して、前記key値および前記value値それぞれの分解ファイルを作成する分解ファイル作成部と、前記key値に不連続および連続なハッシュ関数を用いてハッシュ値を計算し、コンシステントハッシュを適用して、前記key値の分解ファイルを保存する複数のサーバを決定し、前記value値に、不連続または連続なハッシュ関数を用いてハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバを決定するハッシュ値計算部と、前記決定したkey値の分解ファイルを保存するサーバそれぞれに、前記key値を含む前記元ファイルを送信し、前記決定したvalue値の分解ファイルを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信する保存情報管理部と、を備え、前記key値の分解ファイルを保存するサーバそれぞれが、記憶部を備えており、受信した前記key値を含む前記元ファイルを当該記憶部に記憶し、前記value値の分解ファイルを保存するサーバが、記憶部を備えており、受信した前記key値を付した前記value値の分解ファイルを当該記憶部に記憶し、前記ディスパッチャは、前記ハッシュ値計算部が、前記value値の分解ファイルを保存するサーバを決定する際に用いたハッシュ関数とは異なる不連続または連続なハッシュ関数を用いて、前記value値のハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバ以外のサーバを、前記value値の分解ファイルの複製データを保存するサーバに決定し、前記保存情報管理部が、前記決定したvalue値の分解ファイルの複製データを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信し、前記value値の分解ファイルの複製データを保存するサーバが、記憶部を備えており、受信した前記key値を付した前記value値の分解ファイルを当該記憶部に記憶することを特徴とする条件検索データベースクラスタシステムとした。
【００２０】
また、請求項３に記載の発明は、入力装置から受信したクエリを、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信したクエリに基づき、データの保存、検索を含む処理を実行する複数の前記サーバとを備える条件検索データベースクラスタシステムの前記ディスパッチャであって、前記入力装置から前記クエリを受信し、前記受信したクエリの内容を構文解析する構文解析部と、前記構文解析した結果、前記クエリが新規データの保存要求であると解析した場合に、前記クエリに付された元ファイルからkey値およびvalue値を抽出して、前記key値および前記value値それぞれの分解ファイルを作成する分解ファイル作成部と、前記key値に不連続および連続なハッシュ関数を用いてハッシュ値を計算し、コンシステントハッシュを適用して、前記key値の分解ファイルを保存する複数のサーバを決定し、前記value値に、不連続または連続なハッシュ関数を用いてハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバを決定するハッシュ値計算部と、前記決定したkey値の分解ファイルを保存するサーバそれぞれに、前記key値を含む前記元ファイルを送信し、前記決定したvalue値の分解ファイルを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信する保存情報管理部と、を備え、前記ハッシュ値計算部が、前記value値の分解ファイルを保存するサーバを決定する際に用いたハッシュ関数とは異なる不連続または連続なハッシュ関数を用いて、前記value値のハッシュ値を計算し、前記コンシステントハッシュを適用して、前記value値の分解ファイルを保存するサーバ以外のサーバを、前記value値の分解ファイルの複製データを保存するサーバに決定し、前記保存情報管理部が、前記決定したvalue値の分解ファイルの複製データを保存するサーバに、前記key値を付した前記value値の分解ファイルを送信することを特徴とするディスパッチャとした。
【００２１】
このように、入力されるクエリに付された元ファイルからkey値とvalue値を抽出して分解ファイルを作成し、データを保存するサーバを不連続または連続なハッシュ関数を用いて決定する。そして、key値については元ファイルのデータをサーバに保存させ、value値については、key値を付した分解ファイルとしてサーバに保存させる。このようにすることで、key値およびvalue値それぞれの一致検索および範囲検索に対応させて、不連続なデータおよび連続なデータそれぞれで各サーバに保存せざるを得ない従来技術に比べ、データの保存総量を抑えた上で、value値による検索を可能とする。
また、このようにすることで、value値の分解ファイルの複製データを、元のvalue値の分解ファイルを記憶するサーバとは別のサーバに記憶させることができる。よって、元のvalue値の分解ファイルを記憶するサーバが故障した場合であっても、value値の分解ファイルの複製データに基づき、value値による検索が可能となる。
【００２６】
請求項４に記載の発明は、請求項１に記載の条件検索データ保存方法を、コンピュータである前記条件検索データベースクラスタシステムの各装置に実行させるためのプログラムとした。
【００２７】
このようなプログラムによれば、請求項１に記載の条件検索データ保存方法を、一般的なコンピュータである前記条件検索データベースクラスタシステムの各装置で実現することができる。
【発明の効果】
【００２８】
本発明によれば、データの保存総量を抑えた上で、valueの要素（value値）による検索を可能とする、条件検索データ保存方法、条件検索データベースクラスタシステム、ディスパッチャ、およびプログラムを提供することができる。
【図面の簡単な説明】
【００２９】
【図１】本実施形態に係る条件検索データベースクラスタシステムを含む全体構成を示す図である。
【図２】本実施形態に係る条件検索データベースクラスタシステムの内部構成を示す図である。
【図３】本実施形態に係るディスパッチャの構成例を示す機能ブロック図である。
【図４】コンシステントハッシュにおける不連続関数と連続関数を説明するための図である。
【図５】冗長度Ｍ＝２の場合において、各サーバに保存されるデータ例を示す図である。
【図６】冗長度Ｍ＝３の場合において、各サーバに保存されるデータ例を示す図である。
【図７】データ検索処理において用いられるデータ例を示す図であり、図７（ａ）はＸＭＬファイルの一例を示し、図７（ｂ）はクエリの例を示す。
【図８】図７（ｂ）に示すクエリにおいて、アクセスされるサーバを説明するための図である。
【図９】本実施形態に係る条件検索データベースクラスタシステムにおいて、複数の検索条件に合致したデータを取得する処理を示すシーケンス図である。
【図１０】本実施形態に係る条件検索データベースクラスタシステムにおいて、新規データを保存する処理を示すシーケンス図である。
【図１１】本実施形態に係る条件検索データベースクラスタシステムにおいて、既存データの更新処理を示すシーケンス図である。
【発明を実施するための形態】
【００３０】
次に、本発明を実施するための形態（以下、「本実施形態」という）における条件検索データベースクラスタシステム１について説明する。
【００３１】
（概要）
まず、本実施形態に係る条件検索データベースクラスタシステム１に分散されて保存されるデータの概要について、図５を参照して説明する。
【００３２】
本実施形態に係る条件検索データベースクラスタシステム１の各サーバ（サーバ＃０〜＃３）には、元ファイルに格納されているkey，valueのデータを、keyおよびvalueの要素毎に分解し、分解ファイルとして格納する。そして、keyの分解ファイルには、元ファイルのデータ全体を格納する。また、valueの分解ファイルには、そのvalueの値（value値）と共に、元ファイルのkeyの値（key値）を保持するようにする。
【００３３】
このような分解ファイルを、各サーバに格納しておくことを前提として、それぞれの分解ファイルに対して、複数種類による検索が可能なように、各分解ファイルを格納するサーバを決定する。
ここでは、図５に示すように、元ファイルのデータとして、keyが１つ（key：a0123）、valueの要素が２つ（value：Name，Location）のデータ形式を扱う場合を例に説明する。また、このデータ形式に対して、以下に示すように、（１）keyの完全一致、（２）keyの範囲検索、（３）valueの１番目の要素の範囲検索、（４）valueの２番目の要素の完全一致を実現可能とする、各サーバへの分解データの配置を決定する。
【００３４】
（１）keyに対する完全一致検索用に、key：ｘに対して不連続なハッシュ関数ｈkey（ｘ）を用いたコンシステントハッシュを適用して、keyを含むデータ全体を格納するサーバを決定する。図５においては、サーバ「＃０」にデータを格納するものとする。なお、keyの完全一致検索では、データ全体を取得することが一般的であるため、このサーバには、元ファイルのデータ全体を格納するようにする。
【００３５】
（２）keyに対する範囲検索用に、key：ｘに対して連続なハッシュ関数ｈrange（ｘ）を用いたコンシステントハッシュを適用して、keyを含むデータ全体を格納するサーバを決定する。図５においては、サーバ「＃１」にデータを格納するものとする。
【００３６】
（３）valueの１番目の要素（Name）の範囲検索のための分解ファイルは、そのvalueの要素：ｙに対して、連続なハッシュ関数ｈname（ｙ）を用いたコンシステントハッシュを適用して格納するサーバを決定する。図５においては、サーバ「＃２」にその分解ファイル（Name：ono）を格納するものとする。このとき、分解ファイルに、keyの値「a0123」を付して格納する。また、例えば、不連続なハッシュ関数ｈlocation（ｙ）によるコンシステントハッシュを適用し、複製データの格納位置をサーバ「＃３」に決定する。
【００３７】
（４）valueの２番目の要素（Location）の完全一致のための分解ファイルは、そのvalueの要素：ｚに対して、不連続なハッシュ関数ｈlocation（ｚ）を用いたコンシステントハッシュを適用して格納するサーバを決定する。図５においては、サーバ「＃３」にその分解ファイル（Location：tokyo）を格納するものとする。このとき、分解ファイルに、keyの値「a0123」を付して格納する。また、例えば、連続なハッシュ関数ｈrange（ｚ）によるコンシステントハッシュを適用し、複製データの格納位置をサーバ「＃２」に決定する。
【００３８】
なお、複製データを格納するサーバを決定するハッシュ関数は、コンフィグ（configuration）により任意のものを選ぶように設定することができる。例えば、（３）のvalueの１番目の要素の範囲検索において、ｈlocation（ｙ）ではなく、ｈkey（ｙ）やｈrange（ｙ）を選択してもよい。また、ハッシュ関数の入力は、keyやタグの識別子を含めて入力するものとする。つまり、key：a0123であれば、「key：a0123」という文字列を入力する。これにより、keyやタグ名それぞれがvalueの値と同一の文字列となったとしても区別が可能である。
【００３９】
図５に示したように元ファイルを各サーバに格納した状態で、本実施形態の条件検索データベースクラスタシステム１のディスパッチャＤは、クエリを受信すると、そのクエリを解析して検索の種類を判別し、適切なハッシュ関数を選択して以下の検索処理を実行する。
【００４０】
（ａ）keyの完全一致検索を示すクエリの場合は、ハッシュ関数ｈkeyでハッシュ値を計算し、コンシステントハッシュを適用して、サーバ位置（そのデータを格納しているサーバ）を確定し（図５ではサーバ「＃０」）データを取得する。
【００４１】
（ｂ）keyの範囲検索の場合は、クエリで示された検索範囲を示す境界のkeyそれぞれの値についてハッシュ関数ｈrangeでハッシュ値を計算し、コンシステントハッシュを適用し、サーバ位置の候補を取得する。続いて、候補となったサーバ（図５ではサーバ「＃１」）の中で、該当するハッシュ値の範囲のデータ集合を取得する。なお、詳細は、後記する図９において説明する。
【００４２】
（ｃ）valueの完全一致検索の場合は、ハッシュ関数ｈlocationでハッシュ値を計算し、コンシステントハッシュを適用して、サーバ位置を確定し（図５ではサーバ「＃３」）keyの値（key値）を取得する。そして、その取得したkeyの値を用いて、（ａ）の処理を行い元ファイルのデータを取得する。
【００４３】
（ｄ）valueの範囲検索の場合は、クエリで示された検索範囲を示す境界のvalueの要素それぞれの値についてハッシュ関数ｈnameでハッシュ値を計算し、コンシステントハッシュを適用し、サーバ位置の候補を取得する。続いて、この候補となったサーバ（図５ではサーバ「＃２」）の中で、該当するハッシュ値の範囲のkeyの値の集合を取得する。そして、その取得したkeyの値の集合を用いて、（ａ）の処理を行い元ファイルのデータ集合を取得する。
【００４４】
（ａ）の検索処理により、key検索による従来と同様の性能を維持することが可能となる。また、（ｃ）の検索処理により、key以外のvalueによっても検索処理を行うことが可能となる。さらに、（ｂ）および（ｄ）の検索処理により、全体検索をすることなく、高速な条件検索が可能となる。
また、key若しくはvalueの要素の複製データを格納することにより、サーバの１つが故障した場合であっても、別のハッシュ関数を用いて、複製データにアクセスできるため、耐障害性も担保することができる。
【００４５】
（本実施形態のシステム構成）
次に、本実施形態に係る条件検索データベースクラスタシステム１について具体的に説明する。
【００４６】
本実施形態に係る条件検索データベースクラスタシステム１は、図１に示すように、ネットワークを介して、外部システム２であるオペレータシステムや、端末３等と接続される。そして、外部システム２や端末３からの入力データ（クエリ）を受け取り、条件検索データベースクラスタシステム１内でデータの保存、更新、検索等を行い、その結果を出力データとして、外部システム２や端末３に送信する。
【００４７】
図２は、本実施形態に係る条件検索データベースクラスタシステム１の内部構成を示す図である。
図２に示すように、本条件検索データベースクラスタシステム１は、ロードバランサＢ（Balancer：各図において「Ｂ」と表記）と、複数のディスパッチャＤ（Dispatcher：各図において「Ｄ」と表記）と、複数のプロセッサＰ（Processor：各図において「Ｐ」と表記）と、複数のストレージＳ(Storage：各図において「Ｓ」と表記）とを含んで構成される。
【００４８】
ロードバランサＢは、入力装置４から入力データを取得し、出力データを出力装置５に送信する。また、ロードバランサＢは、ラウンドロビン等により、入力データを複数のディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）のいずれかに振り分ける。ここで、入力装置４および出力装置５は、図１に示した外部システム２や端末３である。また、本条件検索データベースクラスタシステム１に対する入力データは、例えば、ＳＱＬのクエリやＸＣＡＰ（XML Configuration Access Protocol）のような、データベースからデータを取得するための要求のことである。
【００４９】
各ディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）は、複数のプロセッサＰ（Ｐ１，Ｐ２，Ｐ３）と接続されており、ロードバランサＢから取得した入力データ（クエリ）を、プロセッサＰ（Ｐ１，Ｐ２，Ｐ３）のいずれかに振り分ける。このディスパッチャＤは、入力データを解析し、コンシステントハッシュを適用して複数のハッシュ関数により、データの格納先であるサーバ（プロセッサＰとストレージＳの組）を決定し、その入力データ（クエリ）を送信する。なお、ディスパッチャＤの詳細な構成を処理については、後記する。
【００５０】
プロセッサＰは、複数のディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）と自身が制御するストレージＳと接続されており、ディスパッチャＤから入力データを受信し、その入力データに従い、ストレージＳに新規データを保存したり、既存データを更新したり、データの検索処理をしたりする制御を実行する。また、ストレージＳは、実際にデータを保存する記憶手段であり、ここでは、各データがＸＭＬ（Extensible Markup Language）ファイルで保存されているものとして説明する。なお、本実施形態においては、このプロセッサＰとストレージＳの組を、１つのサーバとして説明する。
【００５１】
＜ディスパッチャＤ＞
次に、本実施形態に係るディスパッチャＤについて詳細に説明する。
図３は、本実施形態に係るディスパッチャＤの構成例を示す機能ブロック図である。
【００５２】
ディスパッチャＤは、ロードバランサＢおよび複数のプロセッサＰ（Ｐ１，Ｐ２，Ｐ３）と通信可能に接続され、ロードバランサＢから取得した入力データ（クエリ）を、プロセッサＰ（Ｐ１，Ｐ２，Ｐ３）に振り分ける装置であり、図３に示すように、制御部１０と、入出力部２０と、メモリ部３０と、記憶部４０とを含んで構成される。
【００５３】
入出力部２０は、ロードバランサＢや、各プロセッサＰ（Ｐ１，Ｐ２，Ｐ３）との間の情報の入出力を行う。例えば、入出力部２０は、ロードバランサＢが送信した入力データ（クエリ）を受信し、各プロセッサＰに対し、その入力データ（クエリ）の送信を行う。また、入出力部２０は、ストレージＳに保存されていたデータ等の検索結果をプロセッサＰから受信し、ロードバランサＢに対して送信する等の処理を行う。
また、この入出力部２０は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。
【００５４】
制御部１０は、ディスパッチャＤ全体の制御を司り、情報受信部１１と、構文解析部１２と、振り分け処理部１３と、情報送信部１４とを含んで構成される。なお、この制御部１０は、例えば、ディスパッチャＤの記憶部４０に格納されたプログラムをＣＰＵ（Central Processing Unit）がメモリ部３０であるＲＡＭ（Random Access Memory）に展開し実行することで実現される。
【００５５】
情報受信部１１は、入出力部２０を介して、ロードバランサＢからの入力データ（クエリ）や、プロセッサＰからの出力データを取得する。
【００５６】
構文解析部１２は、情報受信部１１から入力データ（クエリ）を受け取り、そのクエリの内容を構文解析する。例えば、構文解析部１２は、その入力データ（クエリ）が、ストレージＳに格納されたデータに対する検索要求（GET）であり、（ａ）keyの完全一致検索、（ｂ）keyの範囲検索、（ｃ）valueの完全一致検索、（ｄ）valueの範囲検索のいずれであるかを解析したり、新規のデータの登録要求（PUT）や、既存データの更新要求（UPDATE）等のクエリの内容を解析したりする。
そして、構文解析部１２は、その解析結果を振り分け処理部１３に引き渡す。
【００５７】
振り分け処理部１３は、構文解析部１２から取得した解析結果に基づき、予め設定されたハッシュ関数のうちのいずれかを選択して、コンシステントハッシュを適用し、振り分け先となるサーバ（プロセッサＰおよびストレージＳ）を決定する。この振り分け処理部１３は、分解ファイル作成部１３１と、関数選択部１３２と、複数のハッシュ値計算部１３３（１３３ａ，１３３ｂ，１３３ｃ，１３３ｄ，…）と、保存情報管理部１３４とを備える。
【００５８】
分解ファイル作成部１３１は、構文解析部１２が入力データ（クエリ）の内容を新規データの登録（PUT）であると解析した場合に、その入力データ（クエリ）に付されたＸＭＬファイルのデータを、keyおよびvalueの要素毎に分解し、分解ファイルを作成する。そして、分解ファイル作成部１３１は、作成した分解ファイルを関数選択部１３２に引き渡す。
【００５９】
関数選択部１３２は、構文解析部１２からの解析結果や、分解ファイル作成部１３１からの分解ファイルを受け取り、入力データ（クエリ）の送信先となるサーバを決定するためのハッシュ関数を選択する。例えば、前記した例で説明すると、関数選択部１３２は、構文解析部１２により、keyの完全一致検索を示すクエリの場合は、不連続なハッシュ関数ｈkeyが設定されたハッシュ値計算部１３３ａ（１３３）を選択する。keyの範囲検索を示すクエリの場合は、連続なハッシュ関数ｈrangeが設定されたハッシュ値計算部１３３ｂ（１３３）を選択する。valueの完全一致検索を示すクエリの場合は、不連続なハッシュ関数ｈlocationが設定されたハッシュ値計算部１３３ｃ（１３３）を選択する。また、valueの範囲検索の場合は、連続なハッシュ関数ｈnameが設定されたハッシュ値計算部１３３ｄ（１３３）を選択する。
【００６０】
また、関数選択部１３２は、分解ファイルを分解ファイル作成部１３１から受け取った場合、keyの完全一致検索のためのデータの保存先を決定するために、不連続なハッシュ関数ｈkeyが設定されたハッシュ値計算部１３３ａ（１３３）を選択する。keyの範囲検索のためのデータの保存先を決定するために、連続なハッシュ関数ｈrangeが設定されたハッシュ値計算部１３３ｂ（１３３）を選択する。valueの完全一致検索のためのデータの保存先を決定するために、不連続なハッシュ関数ｈlocationが設定されたハッシュ値計算部１３３ｃ（１３３）を選択する。また、valueの範囲検索のためのデータの保存先を決定するために、連続なハッシュ関数ｈnameが設定されたハッシュ値計算部１３３ｄ（１３３）を選択する。
【００６１】
そして、関数選択部１３２は、冗長化のための複製データを保存するために、さらに、ハッシュ値計算部１３３を選択する。具体的には、関数選択部１３２は、複製データの保存のためコンフィグ等に予め設定されている、データの保存先を決定するために選択したハッシュ値計算部１３３以外のハッシュ値計算部１３３を選択する。そして、そのハッシュ値計算部１３３のハッシュ関数に、同じ値を入力して計算させることにより、複製データの保存先となるサーバを決定させる。
【００６２】
このように、関数選択部１３２は、構文解析部１２による入力データ（クエリ）の解析結果に基づき、その入力データに最適なハッシュ関数を備えるハッシュ値計算部１３３を選択する。
【００６３】
ハッシュ値計算部１３３は、自身に設定されたハッシュ関数を用いて、例えば、記憶部４０に記憶された、各プロセッサＰ（Ｐ１，Ｐ２，Ｐ３，…）のＩＤ（ＩＰアドレス等）のハッシュ値を計算し、閉じたハッシュ空間上に配置しておく。そして、ハッシュ値計算部１３３は、取得した入力データ（クエリ）に含まれる、keyやタグの識別子と、そのkeyの値（key値）やvalueの値（value値）とを、設定したハッシュ関数に入力し、ハッシュ空間上に配置することで、そのデータの保存先となるサーバ（プロセッサＰおよびストレージＳ）を決定する。
【００６４】
なお、ハッシュ値計算部１３３に設定されるハッシュ関数は、図４（ａ）に示すような、通常のハッシュ関数である不連続関数でハッシュ値を計算するものと、図４（ｂ）に示すような、連続関数でハッシュ値を計算するものとが設定される。これは、前記したように、範囲検索を実行する場合には、連続なハッシュ関数を用いることで、入力するデータの値が近いものであれば、同じサーバ若しくは近接したサーバにデータを保存させるようにするためであり、一致検索を実行する場合には、各サーバの負荷分散等を考慮して不連続なハッシュ関数を用いて、担当サーバを均等化させるためである。
【００６５】
そして、この複数のハッシュ値計算部１３３それぞれには、前記したように、例えば、ハッシュ値計算部１３３ａには、keyの完全一致検索のためのデータの保存先を決定するために、不連続なハッシュ関数ｈkeyが設定される。ハッシュ値計算部１３３ｂには、keyの範囲検索のためのデータの保存先を決定するために、連続なハッシュ関数ｈrangeが設定される。ハッシュ値計算部１３３ｃには、valueの完全一致検索のためのデータの保存先を決定するために、不連続なハッシュ関数ｈlocationが設定される。また、ハッシュ値計算部１３３ｄには、valueの範囲検索のためのデータの保存先を決定するために、連続なハッシュ関数ｈnameが設定される。
【００６６】
保存情報管理部１３４は、構文解析部１２が入力データ（クエリ）を構文解析した結果に応じて、各サーバに保存される情報を管理する全体的な制御を行う。
具体的には、保存情報管理部１３４は、ハッシュ値計算部１３３がデータの保存先となるサーバを決定すると、その決定した振り分け先となるサーバに、入力データ（クエリ）を情報送信部１４を介して送信する。
また、保存情報管理部１３４は、各サーバから取得したkeyの値（key情報）に基づき、関数選択部１３２を介して、そのkey情報から元ファイルを保存したサーバを特定し、そのサーバからデータを取得する制御を行う。そして、保存情報管理部１３４は、データの取得要求を示す入力データ（クエリ）の場合に、各サーバから取得したデータを集合し、出力データとしてロードバランサＢに送信する制御を行う。また、データの更新処理を行う場合に、その更新前のデータの複製を保存しているサーバから、その更新前の複製データを削除する等の制御を行う。
【００６７】
情報送信部１４は、振り分け処理部１３が決定した振り分け先となるプロセッサＰに対して、入力データ等を送信したり、入力データ（クエリ）の内容に応じた各サーバへの制御情報等を送信する。また、プロセッサＰから受信したデータ等を、ロードバランサＢへ送信する等の制御を行う。
【００６８】
次に、記憶部４０は、ハードディスクやフラッシュメモリ等の記憶装置からなり、各プロセッサＰのＩＤ（ＩＰアドレス）等を記憶している。
【００６９】
メモリ部３０は、ＲＡＭ等の一次記憶装置からなり、制御部１０によるデータ処理に必要な情報を一時的に記憶している。
【００７０】
≪データ保存方式≫
次に、本実施形態に係る条件検索データベースクラスタシステム１の各サーバに保存されるデータの保存方式について、図５および図６を参照して説明する。図５は保存データの冗長度Ｍ＝２とした場合の例、図６は保存データの冗長度Ｍ＝３とした場合の例を示している。
【００７１】
ここで、本実施形態に係る条件検索データベースクラスタシステム１内の各サーバ（具体的にはストレージＳ）に格納されるデータは、ＸＭＬ形式で格納されるデータを想定し、keyやvalueの要素はタグでそれぞれが区別されるものとする。そして、ディスパッチャＤの振り分け処理部１３（分解ファイル作成部１３１）が、元データのＸＭＬファイルを分解して分解ファイルを作成し、各サーバに格納する。
また、ディスパッチャＤの関数選択部１３２において、それぞれのkeyおよびvalueのタグ毎に、検索に適した配置を実現するハッシュ関数を備えたハッシュ値計算部１３３が選択できるように設定されているものとする。また、keyおよびvalueのタグに対しては、複数の検索の種類によるハッシュ関数が定義される、つまり、複数のハッシュ値計算部１３３が選択されてもよいものである。
【００７２】
図５は、前記したように、key（0123）とvalueのタグ要素（Name，Location）２つから構成されるデータを、サーバ（＃０〜＃３）の４つサーバに保存し、冗長度Ｍ＝２の例を示している。なお、図５に示すＣ（Ｘ）は、コンシステントハッシュによるサーバ位置の算出、つまり、データ保存するサーバの決定処理を示している。
【００７３】
ここでは、keyの不連続なハッシュ関数ｈkey（ｘ）を用いて、サーバ「＃０」が選択され（Ｃ（ｈkey(a0123)）＝０）、元ファイルがサーバ「＃０」に保存される。そして、その元ファイルの複製データを保存するため、keyの連続なハッシュ関数ｈrange（ｘ）を用いて、サーバ「＃１」が選択され（Ｃ（ｈrange(a0123)）＝１）、元ファイルの複製データがサーバ「＃１」に保存される。
【００７４】
また、valueの連続なハッシュ関数ｈname（ｙ）を用いて、valueの１番目の要素ｙの分解ファイルの保存先として、サーバ「＃２」が選択され（Ｃ（ｈname(ono)）＝２）、「Name：ono」と元ファイルのkeyの値「a0123」とがサーバ「＃２」に保存される。そして、この分解ファイルの複製データが、valueの不連続なハッシュ関数ｈlocation（ｙ）を用いて、サーバ「＃３」が選択され（Ｃ（ｈlocation(ono)）＝３）、この分割ファイルの複製データがサーバ「＃３」に保存される。
【００７５】
また、valueの不連続なハッシュ関数ｈlocation（ｚ）を用いて、valueの２番目の要素ｚの分解ファイルの保存先として、サーバ「＃３」が選択され（Ｃ（ｈlocation(tokyo)）＝３）、「Location：tokyo」と元ファイルのkeyの値「a0123」とがサーバ「＃３」に保存される。そして、この分解ファイルの複製データが、keyの連続なハッシュ関数ｈrange（ｚ）を用いて、サーバ「＃２」が選択され（Ｃ（ｈrange(tokyo)）＝２）、この分割ファイルの複製データがサーバ「＃２」に保存される。
【００７６】
この複製データの保存先を決定するためのハッシュ関数は、関数選択部１３２が、コンフィグで設定された情報により決定し、複製データの元となるデータの保存先とは別のサーバに保存される。
【００７７】
図６は、key（0123）とvalueのタグ要素が２つ（Name，Location）から構成されるデータを、サーバ（＃０〜＃６）の７つのサーバに保存し、冗長度Ｍ＝３の例を示している。
【００７８】
図６の例は、サーバ（＃０〜＃３）には、図５におけるサーバ（＃０〜＃３）と同様のデータが保存されており、さらに冗長度を高めるため、次に示す複製データの作成を行っている。
【００７９】
ディスパッチャＤが、元ファイルの複製データをさらに保存させるため、keyの値に対して連続なハッシュ関数ｈname（ｘ）を用いて、サーバ「＃５」を選択し（Ｃ（ｈname(a0123)）＝５）、元ファイルの複製データをサーバ「＃５」に保存させる。
【００８０】
ディスパッチャＤが、valueの１番目の要素の分解ファイルの複製データの保存先として、連続なハッシュ関数ｈrange（ｙ）を用いて、サーバ「＃６」を選択し（Ｃ（ｈrange(ono)）＝６）、この分解ファイルの複製データ「Name：ono」を、keyの値「a0123」とともにサーバ「＃６」に保存させる。
【００８１】
また、ディスパッチャＤが、valueの２番目の要素の分解ファイルの複製データの保存先として、連続なハッシュ関数ｈname（ｚ）を用いて、サーバ「＃４」を選択し（Ｃ（ｈname(tokyo)）＝４）、この分解ファイルの複製データ「Location：tokyo」を、keyの値「a0123」とともにサーバ「＃３」に保存させる。
【００８２】
このようにすることで、keyおよびvalueに対して、それぞれ完全一致検索と範囲検索に対応したデータを別サーバに保存する場合に比べ、保存データのデータ量を抑制することができる。そして、保存データに変更等があった場合に、一貫性を保持するのにかかる時間の増加を防ぐことができる。
【００８３】
≪データ検索処理≫
次に、本実施形態に係る条件検索データベースクラスタシステム１におけるデータ検索処理について、図７および図８を参照して説明する。まず、データ検索処理の概要について説明する。
【００８４】
図７（ａ）は、本条件検索データベースクラスタシステム１で扱うＸＭＬファイルの一例を示している。このＸＭＬファイル（a0123.xml）の例は、key（a0123）とvalueのタグ要素が４つ（name，location，phone，charge）から構成される例を示している。そして、このＸＭＬファイルのデータが保存される条件検索データベースクラスタシステム１に対して、図７（ｂ）に示す条件検索の各クエリが入力データとして送信され、ディスパッチャＤがこのクエリを受信したものとして、どのサーバにアクセスするかの概略を説明する。なお、この例では、図８に示すように、６つのサーバ（「＃０」〜「＃５」）に、keyとvalueの分解ファイルが保存されているものとする。
【００８５】
（Ａ）keyの一致検索：$GET key=a0123
このkeyの一致検索においては、keyの値による不連続なハッシュ関数による計算が実行され、図８の例ではサーバ「＃０」が検索先として選択される。
【００８６】
（Ｂ）keyの範囲検索：$GET key=[a0120,a0125]
このkeyの範囲検索においては、keyの値による連続なハッシュ関数による計算が実行され、図８の例ではサーバ「＃１」が検索先として選択される。
【００８７】
（Ｃ）valueのタグの一致検索：$GET name=ono & location=tokyo
valueのタグ要素の一致検索においては、保存先を決定する連続なハッシュ関数（ｈname）と、保存先を決定する不連続なハッシュ関数（ｈlocation）による計算がそれぞれ実行され、図８の例ではサーバ「＃２」とサーバ「＃３」とが検索先として選択される。
【００８８】
（Ｄ）valueのタグの範囲検索：$GET phone=[0333330000,0333339999]
valueのタグ要素の範囲検索においては、（Ｂ）のように、予め範囲検索可能なように連続なハッシュ関数が定義されていれば、そのハッシュ関数を用いて計算が実行され、図８の例ではサーバ「＃４」が検索先として選択される。なお、このvalueの範囲検索においては、valueの境界の値（ここでは、「0333330000」と「0333339999」）をハッシュ関数に挿入し、サーバ位置を取得する。
【００８９】
（Ｅ）新規にkeyとファイルを保存する場合：$PUT key=a0123 file=a0123.xml
keyにより新規ファイルの格納サーバを決定する場合は、（Ａ）の検索と同様に、図８の例では、サーバ「＃０」が保存先として決定される。
【００９０】
（Ｆ）既存ファイルの特定タグを更新：$UPDATE key=a0123 charge=4000
既存ファイルの特定タグを更新する場合には、既存ファイルのデータが保存された図８の例ではサーバ「＃０」およびサーバ「＃１」にアクセスし、さらに、そのタグを示す連続なハッシュ関数による計算が実行され、図８の例では、その分解ファイルを保存するサーバ「＃５」にアクセスして、データを変更する。
【００９１】
≪入力データ処理≫
次に、本実施形態に係る条件検索データベースクラスタシステム１が入力データとしてクエリ（以下「入力クエリ」という場合がある）を受信した場合の処理を、図９〜図１１を参照して詳細に説明する（適宜図３参照）。図９は、複数の検索条件を組み合わせてデータを取得する例を示し、図１０は、新たなＸＭＬファイルを保存する例を示し、図１１は、既存のデータを更新する例を示している。
【００９２】
（検索条件の組み合わせ処理）
まず、図９を参照して、複数の検索条件に合致したデータを取得する例について説明する。
【００９３】
まず、入力装置４は、入力データとして、「GET location=tokyo & phone=[0333330000，0333339999]」を示す入力クエリを、ロードバランサＢに送信する（ステップＳ１０１）。
次に、ロードバランサＢは、複数のディスパッチャＤのうちの１つをラウンドロビン等で選択し、選択したディスパッチャＤにその入力クエリを送信する（ステップＳ１０２）。
【００９４】
ディスパッチャＤの構文解析部１２は、入力クエリの構文解析を行う（ステップＳ１０３）。
具体的には、構文解析部１２は、その入力クエリが、データの一致検索を示す「location=tokyo」と範囲検索を示す「phone=[0333330000，0333339999]であることを抽出する。そして、その情報を振り分け処理部１３に引き渡す。
【００９５】
次に、振り分け処理部１３の関数選択部１３２は、各データについてハッシュ値計算部１３３を選択し、ハッシュ値を計算させる（ステップＳ１０４）。
具体的には、関数選択部１３２は、「location=tokyo」については、不連続なハッシュ関数ｈlocatonでハッシュ値を計算するハッシュ値計算部１３３を選択し、ハッシュ値計算部１３３が、Ｃ（ｈlocation(tokyo)）＝３、つまりサーバ「＃３」にアクセス先を決定する。また、関数選択部１３２は、連続なハッシュ関数ｈphoneでハッシュ値を計算するハッシュ値計算部１３３を選択し、入力クエリに示される各境界値を入力し、Ｃ（ｈphone(0333330000)）＝１、および、Ｃ（ｈphone(0333339999)）＝３、つまり、サーバ「＃１」〜「＃３」をアクセス先として決定する。
【００９６】
そして、保存情報管理部１３４は、選択されたサーバ「＃３」と、サーバ「＃１」〜「＃３」との両方を含むサーバを対象サーバとし、サーバ「＃１」「＃２」「＃３」を決定する（ステップＳ１０５）。
【００９７】
次に、保存情報管理部１３４は、対象サーバと決定した各サーバに対して、入力クエリを送信する（ステップＳ１０６）。
【００９８】
入力クエリを受信したサーバは、入力クエリの内容を実行しデータ検索を行う。
具体的には、入力クエリを受信したサーバ「＃１」およびサーバ「＃２」は、「phone=[0333330000，0333339999]」の範囲で自身が保持するデータのうち、該当するデータのkeyの値の集合（以下「key集合」というときがある）を取得する（ステップＳ１０７）。そして、サーバ「＃１」は、取得したkey集合をディスパッチャＤに送信する。
【００９９】
また、サーバ「＃３」は、「location=tokyo」でストレージＳ３内に記憶したデータからkey集合を取得する。また、サーバ「＃３」は、「phone=[0333330000，0333339999]」の範囲で自身が保存するデータのうち、該当するデータのkey集合を取得する（ステップＳ１０８）。そして、サーバ「＃３」は、取得した２つのkey集合をディスパッチャＤに送信する。
【０１００】
ディスパッチャＤの関数選択部１３２は、各サーバから受信したkey集合に基づき、そのkey集合の元ファイルのデータを保存したサーバを選択するため、keyの不連続なハッシュ関数でハッシュ値を計算するハッシュ値計算部１３３を選択し、そのkey集合の元ファイルのデータを保存したサーバを選択する（ステップＳ１０９）。そして、保存情報管理部１３４が、元ファイルの取得要求を選択したサーバに送信する。
【０１０１】
元ファイルを保存しているサーバは、keyの値に基づき、元ファイルのデータを取得し（ステップＳ１１０）、ディスパッチャＤに送信する。
【０１０２】
ディスパッチャＤの保存情報管理部１３４は、検索条件に合致する元ファイルのデータを集約すると（ステップＳ１１１）、ロードバランサＢを介して出力装置５に、検索結果を送信する（ステップＳ１１２）。
【０１０３】
（新規データ保存）
次に、図１０を参照して、新たなＸＭＬファイルを保存する例について説明する。ここでは、図７（ａ）に示したＸＭＬファイル（a0123.xml）を保存するものとして説明する。また、複製データの各サーバへの保存については、説明を省略する。
【０１０４】
まず、入力装置４は、入力データとして、「PUT key=a0123 file=a0123.xml」を示す入力クエリを、ロードバランサＢに送信する（ステップＳ２０１）。
次に、ロードバランサＢは，複数のディスパッチャＤのうちの１つをラウンドロビン等で選択し、選択したディスパッチャＤにその入力クエリを送信する（ステップＳ２０２）。
【０１０５】
ディスパッチャＤの構文解析部１２は、入力クエリの構文解析を行う（ステップＳ２０３）。
具体的には、構文解析部１２は、その入力クエリが、新たなファイルの保存を示すものであり、「key=a0123」と、新たなファイルを示す「file=a0123.xml」とを抽出する。そして、その情報を振り分け処理部１３に引き渡す。
【０１０６】
次に、振り分け処理部１３の関数選択部１３２は、ハッシュ値計算部１３３を選択し、ハッシュ値を計算させる（ステップＳ２０４）。
具体的には、関数選択部１３２は、不連続なハッシュ関数ｈkeyでハッシュ値を計算するハッシュ値計算部１３３を選択し、ハッシュ値計算部１３３は、Ｃ（ｈkey(a0123)）＝１、つまりサーバ「＃１」をアクセス先として選択する。
そして、保存情報管理部１３４は、選択されたサーバ「＃１」を対象サーバとして決定する（ステップＳ２０５）。  
【０１０７】
続いて、振り分け処理部１３の分解ファイル作成部１３１は、入力クエリに付されたファイル（a0123.xml）について、タグ毎に分解ファイルを作成する（ステップＳ２０６）。
そして、分解ファイル作成部１３１は、作成した分解ファイルそれぞれを関数選択部１３２に引き渡す。
【０１０８】
次に、関数選択部１３２は、各分解ファイルについてハッシュ値計算部１３３を選択し、ハッシュ値を計算させる（ステップＳ２０７）。
具体的には、関数選択部１３２は、「name」タグについては、連続なハッシュ関数ｈnameでハッシュ値を計算するハッシュ値計算部１３３を選択し、「location」タグについては、不連続なハッシュ関数ｈlocationでハッシュ値を計算するハッシュ値計算部１３３を選択し、「phone」タグについては、連続なハッシュ関数ｈphoneでハッシュ値を計算するハッシュ値計算部１３３を選択し、「charge」タグについては、連続なハッシュ関数ｈchargeでハッシュ値を計算するハッシュ値計算部１３３を選択する。そして、アクセス先となるサーバを選択する。
【０１０９】
そして、保存情報管理部１３４は、入力クエリを選択された対象サーバに送信する。
入力クエリを受信したサーバ「＃１」は、元ファイルを保存する（ステップＳ２０８）。また、入力クエリを受信した対象サーバ（サーバ「＃２」，「＃３」等）は、keyの値とともに、分解ファイルを保存する（ステップＳ２０９）。
【０１１０】
そして、各サーバから保存完了を示す情報を受信すると、ディスパッチャＤは、ロードバランサＢを介して出力装置５に完了通知を送信する（ステップＳ２１０）。
【０１１１】
（データ更新）
図１１を参照して、既存のデータを更新する例について説明する。ここでは、図７（ａ）に示すＸＭＬファイル（a0123.xml）のデータが更新されるものとして説明する。なお、複製データの更新処理については、説明を省略する。
【０１１２】
まず、入力装置４は、入力データとして、「UPDATE key=a123 location=nagoya」を示す入力クエリを、ロードバランサＢに送信する（ステップＳ３０１）。
次に、ロードバランサＢは、複数のディスパッチャＤのうちの１つのラウンドロビン等で選択し、選択したディスパッチャＤにその入力クエリを送信する（ステップＳ３０２）。
【０１１３】
ディスパッチャＤの構文解析部１２は、入力クエリの構文解析を行う（ステップＳ３０３）。
具体的には、構文解析部１２は、その入力クエリが、データの更新を示すものであり、「key=a0123」と、「location=nagoya」とを抽出する。そして、その情報を振り分け処理部１３に引き渡す。
【０１１４】
次に、振り分け処理部１３の関数選択部１３２は、ハッシュ値計算部１３３を選択し、ハッシュ値を計算させる（ステップＳ３０４）。
具体的には、関数選択部１３２は、不連続なハッシュ関数ｈkeyでハッシュ値を計算するハッシュ値計算部１３３を選択し、ハッシュ値計算部１３３は、Ｃ（ｈkey(a0123)）＝１、つまりサーバ「＃１」をアクセス先として選択する。
また、関数選択部１３２は、不連続なハッシュ関数ｈlocationでハッシュ値を計算するハッシュ値計算部１３３を選択し、ハッシュ値計算部１３３は、Ｃ（ｈlocation(nagoya)）＝２、つまりサーバ「＃２」をアクセス先として選択する。
そして、保存情報管理部１３４は、選択されたサーバ「＃１」およびサーバ「＃２」を対象サーバとして決定する（ステップＳ３０５）。
【０１１５】
続いて、保存情報管理部１３４は、入力クエリをサーバ「＃１」に送信する。そして、サーバ「＃１」は、元ファイルのvalueのlocationの値を、「tokyo」から「nagoya」に変更し（ステップＳ３０６）、変更完了通知をディスパッチャＤに送信する。なお、サーバ「＃１」は、この変更完了通知に、変更前の「location=tokyo」の値を含めた変更後の元ファイルを付して送信する。
【０１１６】
次に、分解ファイル作成部１３１は、変更後の元ファイルのvalueの値「location：nagoya」について分解ファイルを作成する（ステップＳ３０７）。そして、保存情報管理部１３４は、分解ファイルを選択された対象サーバであるサーバ「２」に送信する。
【０１１７】
分解ファイルを受信したサーバ「＃２」は、「Location:nagoya」を保存する（ステップＳ３０８）。ここで、分解ファイルを保存するサーバ「＃２」は、keyの値とともに、分解ファイルを保存する。
【０１１８】
次に、ディスパッチャＤの保存情報管理部１３４は、変更前の「location=tokyo」の分解ファイルの保存先を、関数選択部１３２を介して、ハッシュ値計算部１３３を選択することにより取得する（ステップＳ３０９）。
具体的には、関数選択部１３２は、不連続なハッシュ関数ｈlocationでハッシュ値を計算するハッシュ値計算部１３３を選択し、ハッシュ値計算部１３３は、Ｃ（ｈlocation(tokyo)）＝３、つまりサーバ「＃３」を、旧データを保存するアクセス先として選択する。
【０１１９】
続いて、保存情報管理部１３４は、分解ファイルの削除要求をサーバ「＃３」に送信する。そして、サーバ「＃３」は、保存していた「location=tokyo」の分解ファイルを削除し（ステップＳ３１０）、分解ファイルの削除完了の通知をディスパッチャＤに送信する。
【０１２０】
ディスパッチャＤは、サーバ「＃３」から削除完了の通知を受信すると、ロードバランサＢを介して出力装置５に完了通知を送信する（ステップＳ３１１）。
【０１２１】
このようにすることで、本実施形態に係る条件検索データ保存方法、条件検索データベースクラスタシステム１、ディスパッチャＤ、およびプログラムによれば、key値およびvalue値それぞれの一致検索および範囲検索に対応させて、不連続なデータおよび連続なデータそれぞれで各サーバに保存せざるを得ない従来技術に比べ、データの保存総量を抑え上で、value値による一致検索および範囲検索を可能とする。また、value値の分解ファイルの複製データを、元のvalue値の分解ファイルを記憶するサーバとは別のサーバに記憶させることで、冗長化を実現し、元のvalue値の分解ファイルを記憶するサーバが故障した場合であっても、value値の分解ファイルの複製データに基づき、value値による検索が可能となる。
【符号の説明】
【０１２２】
１      条件検索データベースクラスタシステム
２      外部システム
３      端末
４      入力装置
５      出力装置
１０    制御部
１１    情報受信部
１２    構文解析部
１３    振り分け処理部
１４    情報送信部
２０    入出力部
３０    メモリ部
４０    記憶部
１３１  分解ファイル作成部
１３２  関数選択部
１３３  ハッシュ値計算部
１３４  保存情報管理部
Ｂ      ロードバランサ
Ｄ      ディスパッチャ
Ｐ      プロセッサ
Ｓ      ストレージ
【図１】
0005684671.tif 000002
【図２】
0005684671.tif 000003
【図３】
0005684671.tif 000004
【図４】
0005684671.tif 000005
【図５】
0005684671.tif 000006
【図６】
0005684671.tif 000007
【図７】
0005684671.tif 000008
【図８】
0005684671.tif 000009
【図９】
0005684671.tif 000010
【図１０】
0005684671.tif 000011
【図１１】
0005684671.tif 000012