(57)【要約】【課題】分散Key-Valueストアにおいて、検索性能を向上させつつ、更新性能も向上させる。【解決手段】分散Key-Valueストアの各スレーブサーバ１０においてＭＣ（MajorCompaction）済みKeyValueファイルが作成されたとき、このＭＣ済みKeyValueファイルに含まれる(key,ts,value)群の最新のts（time）の値を分散ロックサーバ２０のタイミングテーブルに登録する。スレーブサーバ１０において検索要求を受け付けたときには、分散ロックサーバ２０からタイミングテーブルを取得し、このタイミングテーブルを参照して、各スレーブサーバ１０のtimeのうち最も古い値（min_t）を取得する。そして、スレーブサーバ１０は、ＭＣ済みKeyValueファイルのうち、このmin_tより前のデータを対象に検索を行う。【選択図】図４
2015222523.tif 000002
【特許請求の範囲】
【請求項１】
KeyとValueからなるデータ群を複数のサーバに分散して管理する分散Key-Valueストアに用いられ、前記データ群を分散して保持するサーバあって、
メインメモリに記憶された前記KeyとValueからなるデータが所定量を超えたとき、前記メインメモリのデータ群をKeyValueファイルにまとめて補助記憶部に移動し、前記メインメモリのデータ群をクリアするファイル作成部と、
前記補助記憶部に記憶されたKeyValueファイルと、前記メインメモリにおける前記データ群とをマージした上で、不要データを削除するMajorCompactionを実行し、前記MajorCompactionにより得られたMajorCompaction済みファイルを前記補助記憶部に記憶するMajorCompaction実行部と、
前記データの検索要求を受け付けたとき、前記MajorCompaction済みファイルを対象として検索を行う検索部とを備えることを特徴とするサーバ。
【請求項２】
前記検索部は、
前記データの検索要求を受け付けたとき、前記サーバごとに、当該サーバにおけるMajorCompaction済みファイルに含まれるデータのうち、最も新しいデータのタイムスタンプの値であるtime値を示したタイミングテーブルを参照して、各サーバのtime値のうち、最も古いtime値を読み出し、前記MajorCompaction済みファイルのデータうち、前記最も古いtime値が示す時刻より前のデータを対象として検索を行うことを特徴とする請求項１に記載のサーバ。
【請求項３】
KeyとValueからなるデータ群を複数のサーバに分散して管理する分散Key-Valueストアに用いられ、前記データ群を分散して保持するサーバが、
メインメモリに記憶された前記KeyとValueからなるデータが所定量を超えたとき、前記メインメモリのデータ群をKeyValueファイルにまとめて補助記憶部に移動し、前記メインメモリのデータ群をクリアするステップと、
前記補助記憶部に記憶されたKeyValueファイルと、前記メインメモリにおける前記データ群とをマージした上で、不要データを削除するMajorCompactionを実行し、前記MajorCompactionにより得られたMajorCompaction済みファイルを前記補助記憶部に記憶するステップと、
前記データの検索要求を受け付けたとき、前記MajorCompaction済みファイルを対象として検索を行うステップとを実行することを特徴とするデータ管理方法。
【請求項４】
KeyとValueからなるデータ群を複数のサーバに分散して管理する分散Key-Valueストアに用いられ、前記データ群を分散して保持するサーバであるコンピュータに、
メインメモリに記憶された前記KeyとValueからなるデータが所定量を超えたとき、前記メインメモリのデータ群をKeyValueファイルにまとめて補助記憶部に移動し、前記メインメモリのデータ群をクリアするステップと、
前記補助記憶部に記憶されたKeyValueファイルと、前記メインメモリにおける前記データ群とをマージした上で、不要データを削除するMajorCompactionを実行し、前記MajorCompactionにより得られたMajorCompaction済みファイルを前記補助記憶部に記憶するステップと、
前記データの検索要求を受け付けたとき、前記MajorCompaction済みファイルを対象として検索を行うステップとを実行させることを特徴とするデータ管理プログラム。
【請求項５】
KeyとValueからなるデータ群を分散して管理するサーバ群と分散ロックサーバとを有する分散Key-Valueストアであって、
前記サーバは、
メインメモリに記憶された前記KeyとValueからなるデータが所定量を超えたとき、前記メインメモリのデータ群をKeyValueファイルにまとめて補助記憶部に移動し、前記メインメモリのデータ群をクリアするファイル作成部と、
前記補助記憶部に記憶されたKeyValueファイルと、前記メインメモリにおける前記データ群とをマージした上で、不要データを削除するMajorCompactionを実行し、前記MajorCompactionにより得られたMajorCompaction済みファイルを前記補助記憶部に記憶するMajorCompaction実行部と、
前記MajorCompaction済みファイルに含まれるデータのうち、最も新しいデータのタイムスタンプの値であるtime値を含むタイミングテーブル更新要求を前記分散ロックサーバへ送信するタイミングテーブル更新要求部と、
前記データの検索要求を受け付けたとき、前記分散ロックサーバから、各サーバのtime値を示したタイミングテーブルを取得し、各サーバのtime値のうち、最も古いtime値を読み出し、前記MajorCompaction済みファイルのデータうち、前記最も古いtime値が示す時刻より前のデータを対象として検索を行う検索部とを備え、
前記分散ロックサーバは、
前記タイミングテーブルを記憶する記憶部と、
前記サーバからタイミングテーブル更新要求を受信したとき、前記タイミングテーブルにおける当該サーバのtime値を、前記タイミングテーブル更新要求に含まれるtime値で更新するタイミングテーブル更新部とを備えることを特徴とする分散Key-Valueストア。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サーバ、データ管理方法、データ管理プログラム、および、分散Key-Valueストアに関する。
【背景技術】
【０００２】
従来、分散Key-Valueストアとして、さまざまなシステムが提案されている。その中の一つであるBigtable（非特許文献１参照）は、分散ファイルシステムGFS（非特許文献２参照）上でテーブルを管理し、以下のような特徴がある。
【０００３】
・テーブルをいくつかの範囲に分割し、クラスタ上のサーバ群で管理する。
・(key,ts,value)の削除や更新、追加といったオペレーションではメインメモリ上に確保した(key,ts,value)を格納するためのバッファへ書き込みを行う。このtsは、タイムスタンプであり、(key,ts,value)が登録された時刻を表している。
・上記のメインメモリ上に確保したバッファが大きくなった場合、分割した範囲ごとにファイルへの書き込みを行い、バッファを解放する。
【０００４】
Bigtableと同様のアーキテクチャを持つ分散Key-Valueストアとしては、Hbase（非特許文献３参照）、Hypertable（非特許文献４参照）等があげられる。
【０００５】
ここでBigtableアーキテクチャを採用するシステムでは、値（value）の追加は(key,ts,value)をメインメモリ上のバッファに格納することによって行われる。更新・削除では既に格納済みの(key,ts,value)は変更されず、更新や削除を意味する新たな(key,ts',value')をメインメモリ上のバッファに追加する。メインメモリ上のバッファ内のデータが所定の容量を超えると(key,ts,value)をkeyでソートされたソート済みKeyValueファイルとしてディスクに保存する。
【０００６】
検索時には、最新の状態を表す(key,ts,value)を取得するため、検索対象となるkeyを含んだディスク上のすべてのソート済みKeyValueファイル群を読み込み、メインメモリ上の(key,ts,value)の集合とマージして、更新・削除により不要となった(key,ts,value)を取り除くことで、最新の(key,ts,value)を返却する。値の追加・更新・削除が所定量起こるごとにソート済みKeyValueファイルが作成され、その度に検索は遅くなっていく。
【０００７】
そのため、Bigtableアーキテクチャを採用するシステムでは自身の管理するKeyValueファイル数が閾値を超えるとMajorCompactionと呼ばれる処理が行われる。MajorCompactionは、すべてのKeyValueファイル群を読み込み、不要な(key,ts,value)ペアを取り除いた新たな(key,ts,value)の集合を新たなソート済みのKeyValueファイルとして書き出す処理である。MajorCompaction直後は、以下の２つの理由から検索を高速に行うことが可能である。
【０００８】
・検索時に複数のソート済みKeyValueファイル群を読み込み、メインメモリ上の(key,ts,value)集合とマージし、不要なデータを除去する必要がない。
・不要なデータが含まれていないため検索時に読み込むファイルサイズが小さい。
【０００９】
したがって、分散Key-Valueストアにおいて検索を高速に行うには、MajorCompactionを実行する頻度を上げる必要がある。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】F.Chang他、Bigtable:  A  Distributed  Storage  System  for  Structured  Data、OSDI、2006
【非特許文献２】S.Ghemawat他、The  Google  File  System、SOSP、2003
【非特許文献３】A.Khurana他、HBase、Hadoop  Day、2010
【非特許文献４】D.Judd、Hypertable:  An  Open  Source,  High  Performance、Scalable  Database、OS-CON、2008
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ここで、MajorCompactionの頻度を上げれば検索性能は向上するが、MajorCompactionは一度にすべてのソート済みKeyValueファイルを読み込み、書き出す必要がある。このため、サーバの処理負荷が大きくなり、MajorCompaction中はそのほかの処理、例えば、データの更新処理の性能が低下するおそれがある。一方、MajorCompactionの頻度を低くすれば検索性能は下がるが、サーバの処理負荷は大きくならないので、更新性能は低下しにくい。つまり、分散Key-Valueストアにおいて、検索性能と更新性能とはトレードオフの関係にある。
【００１２】
そこで、本発明は、前記した問題を解決し、分散Key-Valueストアにおいて、検索性能を向上させつつ、更新性能も向上させることを課題とする。
【課題を解決するための手段】
【００１３】
上述した課題を解決するために、本発明は、KeyとValueからなるデータ群を複数のサーバに分散して管理する分散Key-Valueストアに用いられ、前記データ群を分散して保持するサーバあって、メインメモリに記憶された前記KeyとValueからなるデータが所定量を超えたとき、前記メインメモリのデータ群をKeyValueファイルにまとめて補助記憶部に移動し、前記メインメモリのデータ群をクリアするファイル作成部と、前記補助記憶部に記憶されたKeyValueファイルと、前記メインメモリにおける前記データ群とをマージした上で、不要データを削除するMajorCompactionを実行し、前記MajorCompactionにより得られたMajorCompaction済みファイルを前記補助記憶部に記憶するMajorCompaction実行部と、前記データの検索要求を受け付けたとき、前記MajorCompaction済みファイルを対象として検索を行う検索部とを備えることを特徴とする。
【発明の効果】
【００１４】
本発明によれば、分散Key-Valueストアにおいて、検索性能を向上させつつ、更新性能も向上させることができる。
【図面の簡単な説明】
【００１５】
【図１】図１は、分散Key-Valueストアの一例を示す図である。
【図２】図２は、スレーブサーバの概要を説明する図である。
【図３】図３は、MajorCompactionの概要を説明する図である。
【図４】図４は、スレーブサーバにおける検索の概要を説明する図である。
【図５】図５は、データの一貫性を説明する図である。
【図６】図６は、スレーブサーバの構成を示す図である。
【図７】図７は、分散ロックサーバの構成を示す図である。
【図８】図８は、タイミングテーブルの更新を説明する図である。
【図９】図９は、スレーブサーバにおけるMajorCompaction実行時の処理手順を示す図である。
【図１０】図１０は、スレーブサーバにおける検索時の処理手順を示す図である。
【図１１】図１１は、データ管理プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１６】
以下、本発明を実施するための形態（実施形態）について説明する。本実施形態において、分散Key-ValueストアにBigtableアーキテクチャを用いる場合を例に説明するが、これに限定されない。
【００１７】
（概要）
まず、図１を用いて、本実施形態の分散Key-Valueストアの概要を説明する。分散Key-Valueストアは、マスタサーバ１と複数のスレーブサーバ（サーバ）１０（１０Ａ，１０Ｂ，１０Ｃ）と、分散ロックサーバ２０とを備える。マスタサーバ１は、テーブル（例えば、テーブルＡ）の部分集合（例えば、Area）をどのスレーブサーバ１０へ配置するかを決定する。各スレーブサーバ１０は、テーブル（例えば、テーブルＡ）のデータを、例えば、Area単位で分散して保持する。分散ロックサーバ２０は、分散ロックシステムを備え、各スレーブサーバ１０により読み込みおよび更新可能なタイミングテーブルを保持する。この分散ロックサーバ２０およびタイミングテーブルについては後記する。
【００１８】
図１のテーブルＡは、論理的なテーブルを表しており、複数の(key,ts,value)タプルを備える。このkeyはkey値を示し、tsは(key,ts,value)が登録された時刻を示し、valueはkey値に対応する値を示す。なお、図１に例示するテーブルＡでは、便宜的に１００エントリごとにタブレットを分割しているが、エントリ数ではなく、データサイズにより分割してもよい。テーブルＡは、keyによりソートされているため、keyの範囲によってテーブルを分割することが可能である。分割されたテーブル（Area）は各スレーブサーバ１０に配置される。
【００１９】
例えば、スレーブサーバ１０Ａは、Key1からKey99までのAreaとKey300からKey399までのAreaを管理する。また、スレーブサーバ１０Ｂは、Key100からKey199までのAreaとKey400からKey499までのAreaを管理する。さらに、スレーブサーバ１０Ｃは、Key200からKey299までのAreaとKey500からKey599までのAreaを管理する。
【００２０】
（スレーブサーバの概要）
スレーブサーバ１０は、Areaのデータ（(key,ts,value)）の検索・更新等の処理をユーザ端末（図示省略）等からの要求に従って行う。
【００２１】
なお、スレーブサーバ１０Ａが管理するAreaにはD(Key302,ts10,Value302)が存在している。これは直後の(Key302,ts9,Value302)がユーザ端末によって削除されたことを示している。つまり、BigTableアーキテクチャでは、ユーザ端末からデータ更新や削除が要求された場合、スレーブサーバ１０は既に格納済みの(key,ts,value)タプルを更新するのではなく、更新や削除を意味する新たな(key,ts',value')を追加する。ここで、ユーザ端末からの検索要求があった場合、スレーブサーバ１０は、同一のkeyに関する追加、更新、削除を示す(key,ts,value)の集合から必要な(key,ts,value)のみをユーザ端末に返却する。
【００２２】
図２を用いて、ユーザ端末から(key,ts,value)が追加された場合に、スレーブサーバ１０がどのように(key,ts,value)を管理するかを説明する。ここではスレーブサーバ１０Ａを例に説明する。スレーブサーバ１０Ａは、複数のArea（Area3およびArea0）を管理している。各Areaを構成するデータは、スレーブサーバ１０Ａのメインメモリ１２１上のバッファと、ディスク等の補助記憶部１２２のソート済みKeyValueファイルに存在する。
【００２３】
例えば、（１）ユーザ端末がスレーブサーバ１０Ａに対して、(newkey,tsN,newvalue)を追加した場合、（２）スレーブサーバ１０Ａは、メインメモリ１２１上のバッファへの(newkey,tsN,newvalue)の書き込みを行う。なお、メインメモリ１２１上のバッファは、Areaごとに用意される。
【００２４】
（３）スレーブサーバ１０Ａは、メインメモリ１２１上のバッファが大きくなると（閾値を超えた場合）、ソート済みのKeyValueをファイルに書き出し、メインメモリ１２１上のバッファをクリアする。つまり、スレーブサーバ１０Ａは、バッファのデータ群（(key,ts,value)群）をソートし、補助記憶部１２２のソート済みKeyValueファイルへ書き込む。この書き込みが成功した時点で、メインメモリ１２１上のバッファをクリアする。この処理は、メインメモリ１２１上で一時的に格納されているデータを永続化することが目的である。一方、メインメモリ１２１上のバッファがまだ大きくないとき（閾値を超えない場合）、（３）の書き込みは生じない。なお、スレーブサーバ１０は、ソート済みKeyValueを別ファイルとして書き込んでもよいし、既存のソート済みKeyValueファイルに追記で書き込んでもよい。
【００２５】
また、スレーブサーバ１０は、ソート済みKeyValueファイルの作成のほか、MajorCompactionを行う。
【００２６】
（MajorCompactionの概要）
図３を用いて、MajorCompactionを説明する。図３において、スレーブサーバ１０Ａのメインメモリ１２１上のバッファに、D(Key303,ts10,Value303)が存在している。このような状態で、スレーブサーバ１０Ａがソート済みKeyValueファイルを作成する場合、このD(Key303,ts10,Value303)を実際には削除せず、D(Key303,ts10,Value303)をkeyによりソートした上で、ソート済みKeyValueファイルへ格納する。これは、削除対象となるデータ（例えば、(Key303,ts9,Value303)）は、既にソート済みKeyValueファイルとして永続化されており、全てのソート済みKeyValueファイルを読み込まない限り削除対象となるデータがどこに存在するか分からないためである。
【００２７】
MajorCompactionは、このようにD(key,ts,value)という削除を示すデータが存在した場合に、メインメモリ１２１上のバッファおよび補助記憶部１２２上の全ての(key,ts,value)を読み込み、削除するべき(key,ts,value)を削除した上で新しいファイル（ソート済みKeyValueファイル）を作成する処理である。これにより、スレーブサーバ１０は、既存のソート済みKeyValueファイル群とメインメモリ１２１上の(key,ts,value)を全てまとめた上で、新しいソート済みKeyValueファイル（ＭＣ（MajorCompaction）済みKeyValueファイル）を作成する。そして、スレーブサーバ１０Ａは、既存のソート済みKeyValueファイル群とメインメモリ１２１上の(key,ts,value)を削除する。
【００２８】
スレーブサーバ１０は、ユーザ端末等から検索要求を受け付けたとき、このＭＣ済みKeyValueファイルを対象に検索を行う。
【００２９】
（検索の概要）
図４を用いて、スレーブサーバ１０における検索の概要を説明する。
【００３０】
ここで、検索の概要の説明の前に、分散ロックサーバ２０について簡単に説明しておく。分散ロックサーバ２０は、タイミングテーブルを備える。このタイミングテーブルは、分散Key-Valueストアのスレーブサーバ１０ごとに、当該スレーブサーバ１０が保持するＭＣ済みKeyValueファイル内の最新のデータ(key,ts,value)のtsの値（timeの値）を示した情報である。例えば、図４に示すタイミングテーブルには、スレーブサーバ１０Ａ，１０Ｂ，１０Ｃそれぞれが保持するＭＣ済みKeyValueファイル内の最新のデータのtsの値（timeの値）が格納される。図４に示すタイミングテーブルは、スレーブサーバ１０Ａが保持するArea1のtimeの値は「t4」であり、スレーブサーバ１０Ｂが保持するArea2のtimeの値は「t2」であり、スレーブサーバ１０Ｃが保持するArea3のtimeの値は「t3」であることを示す。
【００３１】
次にスレーブサーバ１０における検索の概要を説明する。ここではスレーブサーバ１０Ａが、ユーザ端末からkey=Key1を条件とする値(value)の検索要求を受け付けた場合を例に説明する。
【００３２】
（１）スレーブサーバ１０Ａがユーザ端末からkey=Key1を検索条件とする値(value)の検索要求を受け付けると、（２）分散ロックサーバ２０に対し、タイミングテーブルの取得要求を行い、（３）分散ロックサーバ２０からタイミングテーブルの返却を受ける。そして、（４）スレーブサーバ１０Ａは、このタイミングテーブルを参照して、Key1に対する値(value)を取得する。具体的には、スレーブサーバ１０Ａは、補助記憶部１２２上のＭＣ済みKeyValueファイルを読み込む。そして、スレーブサーバ１０Ａは、読み込んだＭＣ済みKeyValueファイルに含まれる(key,ts,value)群を、ts＜min(t4,t2,t3)でフィルタした後、key＝Key1でフィルタした値をユーザ端末に返却する。すなわち、スレーブサーバ１０Ａは取得したタイミングテーブルに示されるt4,t2,t3のうち、最小の値（つまり、最も古いtsの値。例えば、t4）を選択する。そして、ＭＣ済みKeyValueファイルに含まれる(key,ts,value)群のうち、選択したts（例えば、t4）未満のtsを持つ(key,ts,value)群の中から、Key1に対応する値（value）を取得してユーザ端末へ返却する。
【００３３】
このようにスレーブサーバ１０はＭＣ済みKeyValueファイルに対して検索処理を行うので、検索を高速に行うことができる。また、このように検索を高速に行えるようにすることで、頻繁にMajorCompactionを行う必要がなくなるので、スレーブサーバ１０における処理負荷を低減できる。
【００３４】
なお、スレーブサーバ１０が、読み込んだＭＣ済みKeyValueファイルに含まれる(key,ts,value)群を検索するとき、タイミングテーブルに示されるtsのうち、ts＜min(t4,t2,t3)となるtsでフィルタリングするのは、全Areaのデータの一貫性を満たすためである。ここでの全Areaのデータの一貫性とは、例えば、ある時刻でデータを検索したときに、当該時刻以前の追加、更新、削除されたデータが、全て検索結果に反映されていることを意味する。
【００３５】
ここで、データの一貫性について、図５を用いて説明する。また、図５におけるts1〜ts5は、ts1＜ts2＜ts3＜ts4＜ts5であるものとする。
【００３６】
図５において、スレーブサーバ１０ＡのArea1で時刻Ｔ１およびＴ４にＭＣ（MajorCompaction）が実行され、このＭＣにより作成されたＭＣ済みKeyValueファイルに含まれる最新のtsは「ts4」であることを示す。また、スレーブサーバ１０ＢのArea2で時刻Ｔ３にＭＣが実行され、このＭＣにより作成されたＭＣ済みKeyValueファイルに含まれる最新のtsは「ts3」であることを示す。さらに、スレーブサーバ１０ＣのArea3で時刻Ｔ２にＭＣが実行され、このＭＣにより作成されたＭＣ済みKeyValueファイルに含まれる最新のtsは「ts2」であることを示す。
【００３７】
例えば、図５のts5にＭＣ済みKeyValueファイルに対する検索が行われると、スレーブサーバ１０ＡのArea1についてts4以降のデータの追加、更新、削除が検索結果に反映されない。また、スレーブサーバ１０ＢのArea2についてもts3以降のデータの追加、更新、削除が検索結果に反映されず、スレーブサーバ１０ＣのArea3についてもts2以降のデータの追加、更新、削除が検索結果に反映されない。つまり、全Areaでのデータの一貫性が満たされない。
【００３８】
このように全Areaでのデータの一貫性が満たされていないと、各Areaの値（value）の集計等を行うとき、ts2〜ts5における値（value）が部分的にしか集計対象にならない。その結果、正確な集計結果を得ることができないという問題が生じる。
【００３９】
そこで、スレーブサーバ１０はＭＣ済みKeyValueファイルからデータ（(key,ts,value)）を検索する際、ts2、ts3、ts4のうち最も古いts（例えば、ts2）よりも前のtsを持つデータ群（(key,ts,value)群）を対象に検索を行う。このようにすることで、全Areaのデータの一貫性を満たすことができる。
【００４０】
（スレーブサーバ）
次に、図６を用いてスレーブサーバ１０の構成を説明する。スレーブサーバ１０は、入出力部１１、記憶部１２、制御部１３を備える。
【００４１】
入出力部１１は、各種データの入出力を司る。この入出力部１１は、例えば、ユーザ端末からのデータの検索、追加、更新、削除等の要求を受け付ける。また、入出力部１１は、ユーザ端末等に検索要求の結果（検索結果）を送信する。
【００４２】
記憶部１２は、メインメモリ１２１と補助記憶部１２２とを備える。メインメモリ１２１は、例えば、ＲＡＭ（Random  Access  Memory）等であり、補助記憶部１２２は、例えば、ハードディスクドライブ等である。
【００４３】
メインメモリ１２１はバッファを備え、このバッファには、例えば、入力された(key,ts,value)群が一時的に記憶される。
【００４４】
補助記憶部１２２は、(key,ts,value)群をkey値でソートしたファイルであるソート済みKeyValueファイルと、ＭＣ済みKeyValueファイルとが記憶される。
【００４５】
制御部１３は、スレーブサーバ１０全体の制御を司る。この制御部１３は、データ管理部１３１と、ソート済みファイル作成部１３２と、MajorCompaction実行部１３３と、タイミングテーブル更新要求部１３４と、タイミングテーブル取得部１３５と、検索部１３６とを備える。
【００４６】
データ管理部１３１は、データの追加、更新、削除等の要求に基づく処理を実行し、処理結果を入出力部１１経由で返す。
【００４７】
ソート済みファイル作成部１３２は、メインメモリ１２１のバッファの(key,ts,value)群をもとにソート済みKeyValueファイルを作成する。例えば、メインメモリ１２１上のバッファが大きくなると（閾値を超えた場合）、ソート済みのKeyValueをファイルに書き出し、メインメモリ１２１上のバッファをクリアする。つまり、バッファのデータ（(key,ts,value)群）をソートし、補助記憶部１２２のソート済みKeyValueファイルへ書き込む。この書き込みが成功した時点で、ソート済みファイル作成部１３２は、メインメモリ１２１上のバッファをクリアする。
【００４８】
MajorCompaction実行部１３３は、メインメモリ１２１上のバッファおよび補助記憶部１２２上の全ての(key,ts,value)を読み込み、削除するべき(key,ts,value)を削除した上で新しいファイル（ソート済みKeyValueファイル）を作成する。つまり、MajorCompaction実行部１３３は、既存のソート済みKeyValueファイル群とメインメモリ１２１上の(key,ts,value)を全てまとめたうえで、ＭＣ（MajorCompaction）済みKeyValueファイルを作成する。そして、MajorCompaction実行部１３３は、既存のソート済みKeyValueファイル群とメインメモリ１２１上の(key,ts,value)を削除する。なお、MajorCompaction実行部１３３は作成したＭＣ済みKeyValueファイルを補助記憶部１２２に格納する際、当該ファイルがMajorCompactionにより作成されたファイルであることを示す識別情報を付して格納する。
【００４９】
タイミングテーブル更新要求部１３４は、MajorCompaction実行部１３３によりMajorCompactionが実行されたとき、ＭＣ済みKeyValueファイルに含まれるデータのうち、最新のtsの値でタイミングテーブルを更新するよう分散ロックサーバ２０に要求する。
【００５０】
タイミングテーブル取得部１３５は、検索部１３６において、検索を行うとき、分散ロックサーバ２０からタイミングテーブルを取得する。
【００５１】
検索部１３６は、ＭＣ済みKeyValueファイルから検索対象のデータを検索する。具体的には、検索部１３６は、検索要求を受け取ると、まず、タイミングテーブル取得部１３５により取得されたタイミングテーブルに示される各スレーブサーバ１０のtimeの値（つまり、当該スレーブサーバ１０のＭＣ済みKeyValueファイルに含まれる最新のtsの値）のうち、最も古いtimeの値を読み出す。そして、検索部１３６は、ＭＣ済みKeyValueファイルから、この読み出したtimeより前の時刻のtsを持つ(key,ts,value)群を選択（フィルタリング）する。そして、検索部１３６はフィルタリングした(key,ts,value)群を対象として、検索要求に示される検索条件を用いた検索を行う。その後、検索部１３６は入出力部１１経由で、検索要求の送信元（例えば、ユーザ端末等）に検索結果を返す。
【００５２】
このようなスレーブサーバ１０によれば、ＭＣ済みKeyValueファイルに対して検索処理を行うので、迅速に検索を行うことができる。また、検索におけるデータの一貫性を保証することができる。さらに、スレーブサーバ１０はＭＣ済みKeyValueファイルに対して検索処理を行うので、頻繁にMajorCompactionを行う必要がなくなり、その結果、スレーブサーバ１０における処理負荷を低減できる。
【００５３】
（分散ロックサーバ）
次に、図７を用いて、分散ロックサーバ２０を説明する。この分散ロックサーバ２０は分散ロックシステムを備え、複数のスレーブサーバ１０からのタイミングテーブルのデータに対しデータの読み込み（取得）や書き込みが行われた場合でも、データの一貫性を保証する。分散ロックシステムは、例えば、Google（登録商標）のChubbyや、そのオープンソース実装であるZookeeper等である。分散ロックサーバ２０は、入出力部２１、記憶部２２、制御部２３を備える。
【００５４】
入出力部２１は、各種データの入出力を司る。この入出力部２１は、例えば、スレーブサーバ１０からのタイミングテーブルの取得要求や更新要求等を受け付ける。また、入出力部２１は、スレーブサーバ１０からタイミングテーブルの取得要求を受け付けたときには、このタミングテーブルを送信する。
【００５５】
記憶部２２は、タイミングテーブルを記憶する。このタイミングテーブルは、前記したとおり、スレーブサーバ１０ごとに、当該スレーブサーバ１０が保持するＭＣ済みKeyValueファイル内のデータ(key,ts,value)の最新のtsの値（timeの値）を示した情報である。
【００５６】
制御部２３は、タイミングテーブル管理部２３１と、タイミングテーブル更新部２３２とを備える。
【００５７】
タイミングテーブル管理部２３１は、入出力部２１経由で、スレーブサーバ１０からタイミングテーブルの取得要求を受信したとき、記憶部２２からタイミングテーブルを読み出し、当該スレーブサーバ１０へ送信（返却）する。
【００５８】
タイミングテーブル更新部２３２は、入出力部２１経由でスレーブサーバ１０からタイミングテーブルの更新要求を受信したとき、この更新要求に基づきタイミングテーブルを更新する。例えば、図８に示すように、（１）スレーブサーバ１０ＡがMajorCompactionを実行し、（２）分散ロックサーバ２０がスレーブサーバ１０ＡからArea1に関するタイミングテーブル更新要求を受信した場合を考える。この場合、（３）分散ロックサーバ２０のタイミングテーブル更新部２３２は、スレーブサーバ１０Ａから、タイミングテーブルにおけるスレーブサーバ１０ＡのArea1のtimeの値を「ts4」に更新せよ、という更新要求を受信すると、これに基づきタイミングテーブルのスレーブサーバ１０ＡのArea1のtimeの値を「ts1」から「ts4」に更新する。
【００５９】
このように分散ロックサーバ２０がタイミングテーブルにより各スレーブサーバ１０におけるＭＣ済みKeyValueファイルに含まれる最新のtsの値（timeの値）を管理することで、全Areaでのデータの一貫性を保証することができる。
【００６０】
（処理手順）
次に、図９を用いて、スレーブサーバ１０のMajorCompactionの実行時の処理手順を説明する。
【００６１】
スレーブサーバ１０のMajorCompaction実行部１３３が入出力部１１経由でMajorCompactionの実行指示の入力を受け付けると（Ｓ１）、補助記憶部１２２上のソート済みKeyValueファイル群およびメインメモリ１２１上の(key,ts,value)群の更新・削除を反映した上で新たなソート済みKeyValueファイル（つまり、ＭＣ済みKeyValueファイル）を作成する（Ｓ２）。作成したＭＣ済みKeyValueファイルは補助記憶部１２２に記憶する。
【００６２】
また、タイミングテーブル更新部２３２は、新たなソート済みKeyValueファイル（ＭＣ済みKeyValueファイル）に含まれる(key,ts,value)群の中で最大となるts（つまり、最新のts）を取得する（Ｓ３）。この取得したtsをts_maxとする。
【００６３】
そして、タイミングテーブル更新部２３２は分散ロックサーバ２０に対し、タイミングテーブルのtimeの値をts_maxで更新する旨のタイミングテーブル更新要求を送信する（Ｓ４）。
【００６４】
このようにしてスレーブサーバ１０からタイミングテーブル更新要求を受信した分散ロックサーバ２０は、受信したタイミングテーブル更新要求に基づき、タイミングテーブルの当該スレーブサーバ１０に関するtimeの値を更新する。
【００６５】
なお、このMajorCompactionは、スレーブサーバ１０にMajorCompactionの実行指示が入力されたときのほか、ソート済みKeyValueファイルの数が所定の閾値を超えたときに実行してもよい。
【００６６】
次に、図１０を用いて、スレーブサーバ１０の検索時の処理手順を説明する。スレーブサーバ１０の検索部１３６が検索要求の入力を受け付けると（Ｓ１１）、タイミングテーブル取得部１３５は分散ロックサーバ２０上のタイミングテーブルを取得し、検索部１３５は、このタイミングテーブルに示される各スレーブサーバ１０のtimeの値の最小値（min_t）を選択する（Ｓ１２）。つまり、検索部１３６は、各スレーブサーバ１０のtimeの値のうち、最も古いtimeの値を選択する。
【００６７】
検索部１３６は、ＭＣ済みKeyValueファイルを読み込み（Ｓ１３）、読み込んだＭＣ済みKeyValueファイルに含まれる(key,ts,value)群からtsがmin_t以上の(key,ts,value)群を取り除いた集合Ｓを求める（Ｓ１４）。つまり、検索部１３６は、ＭＣ済みKeyValueファイルに含まれる(key,ts,value)群をts＜min_tでフィルタする。
【００６８】
Ｓ１４の後、検索部１３６は、Ｓ１４で求めた集合Ｓから検索要求に示される検索条件に合う値（value）を取得し、検索要求の送信元（例えば、ユーザ端末）へ返却する（Ｓ１５）。
【００６９】
このようにスレーブサーバ１０はＭＣ済みKeyValueファイルを対象として検索を行うので検索を高速に行うことができる。また、スレーブサーバ１０は、ＭＣ済みKeyValueファイルから検索を行う際、ＭＣ済みKeyValueファイルに含まれる(key,ts,value)群のうち、tsがmin_t未満の(key,ts,value)群を対象に検索を行うので、全Areaのデータの一貫性を保証できる。
【００７０】
（プログラム）
また、スレーブサーバ１０が実行する処理をコンピュータが実行可能な言語で記述したデータ管理プログラムを作成することもできる。この場合、コンピュータがデータ管理プログラムを実行することにより、上記実施形態と同様の効果を得ることができる。さらに、かかるデータ管理プログラムをコンピュータに読み取り可能な記録媒体に記録して、この記録媒体に記録されたデータ管理プログラムをコンピュータに読み込ませて実行することにより上記実施形態と同様の処理を実現してもよい。以下に、スレーブサーバ１０と同様の機能を実現するコンピュータの一例を説明する。
【００７１】
図１１は、データ管理プログラムを実行するコンピュータを示す図である。図１１に示すように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ（Central  Processing  Unit）１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有する。これらの各部は、バス１０８０によって接続される。
【００７２】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ１０１２を含む。このメモリ１０１０は、メインメモリ１２１に相当する。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。このハードディスクドライブ１０９０は、補助記憶部１２２に相当する。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。ディスクドライブ１１００には、例えば、磁気ディスクや光ディスク等の着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０には、例えば、マウス１１１０およびキーボード１１２０が接続される。ビデオアダプタ１０６０には、例えば、ディスプレイ１１３０が接続される。
【００７３】
ここで、図１１に示すように、ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３およびプログラムデータ１０９４を記憶する。
【００７４】
また、データ管理プログラムは、例えば、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、ハードディスクドライブ１０９０に記憶される。具体的には、上記実施形態で説明したスレーブサーバ１０が実行する各処理が記述されたプログラムモジュールが、ハードディスクドライブ１０９０に記憶される。
【００７５】
また、データ管理プログラムに用いられるデータは、プログラムデータとして、例えば、ハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、ハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して、上述した各手順を実行する。
【００７６】
なお、データ管理プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限られず、例えば、着脱可能な記憶媒体に記憶されて、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、データ管理プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ＬＡＮ（Local  Area  Network）やＷＡＮ（Wide  Area  Network）等のネットワークを介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００７７】
１      マスタサーバ
１０    スレーブサーバ（サーバ）
１１、２１    入出力部
１２、２２    記憶部
１３、２３    制御部
２０    分散ロックサーバ
１２１  メインメモリ
１２２  補助記憶部
１３１  データ管理部
１３２  ソート済みファイル作成部（ファイル作成部）
１３３  MajorCompaction実行部
１３４  タイミングテーブル更新要求部
１３５  タイミングテーブル取得部
１３６  検索部
２３１  タイミングテーブル管理部
２３２  タイミングテーブル更新部
【図１】
2015222523.tif 000003
【図２】
2015222523.tif 000004
【図３】
2015222523.tif 000005
【図４】
2015222523.tif 000006
【図５】
2015222523.tif 000007
【図６】
2015222523.tif 000008
【図７】
2015222523.tif 000009
【図８】
2015222523.tif 000010
【図９】
2015222523.tif 000011
【図１０】
2015222523.tif 000012
【図１１】
2015222523.tif 000013