(57)【要約】【課題】KeyValueストアに用いられるサーバに障害が発生した場合のリカバリ時間を短縮しつつ、検索時間を短縮する。【解決手段】サーバは、バッファ領域に書き込まれた（key,value）の集合である（key,value）群のデータ量が所定の閾値を超えたとき、バッファ領域に書き込まれた（key,value）群をファイルへ書き出す。このとき、サーバは、バッファ領域に書き込まれた（key,value）群を、メインメモリ上に確保されたキャッシュ領域に移動させ、その後、バッファ領域を解放する。そして、サーバがkeyを含む検索要求を受け付けたとき、キャッシュ領域から当該keyを含む（key,value）を検索し、キャッシュ領域に当該keyを含む（key,value）がないとき、ファイルからkeyを含む（key,value）を検索する。【選択図】図１
2014229036.tif 000002
【特許請求の範囲】
【請求項１】
メインメモリ上に、ＷＡＬ（Write Ahead Logging）ログを備え、前記ＷＡＬログに、KeyValueストアに用いられる（key,value）の削除、変更、または、追加を示すオペレーションの書き込みが成功すると、前記（key,value）を、前記メインメモリ上のバッファ領域へ書き込む情報処理装置であって、
前記バッファ領域に書き込まれた前記（key,value）の集合である（key,value）群のデータ量が所定の閾値を超えたとき、
前記バッファ領域に書き込まれた（key,value）群をファイルへ書き出すファイル作成部と、
前記バッファ領域に書き込まれた（key,value）群を、前記メインメモリ上に確保されたキャッシュ領域に移動させるキャッシュ作成部と、
前記（key,value）群のファイルへの書き出し、および、前記キャッシュ領域への移動完了後、前記バッファ領域を解放するバッファ解放部と、
前記keyを含む検索要求を受け付けたとき、
前記キャッシュ領域から前記keyを含む（key,value）を検索し、前記キャッシュ領域に前記keyを含む（key,value）がないとき、前記ファイルから前記keyを含む（key,value）を検索する検索部とを備えることを特徴とする情報処理装置。
【請求項２】
前記キャッシュ領域の前記（key,value）群のデータ量が、所定のデータ量を超えたとき、前記キャッシュ領域の前記（key,value）群のうち、前記検索の時刻または作成時刻の古い（key,value）群から優先的に削除するキャッシュ削除部をさらに備えることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記バッファ領域に書き込まれた前記（key,value）群のデータ量が所定の閾値を超えた場合において、前記バッファ領域に書き込まれた前記（key,value）群に、前記（key,value）の削除を示す情報が含まれていたとき、
前記ファイル作成部は、
前記バッファ領域に書き込まれた（key,value）群をファイルへ書き出す際、前記ファイル内から削除の対象の（key,value）を削除した新たなファイルを作成し、
前記キャッシュ作成部は、
前記バッファ領域に書き込まれた（key,value）群のうち、削除の対象の（key,value）を削除した（key,value）群を、前記キャッシュ領域に移動させることを特徴とする請求項１または請求項２に記載の情報処理装置。
【請求項４】
前記キャッシュ作成部は、
前記バッファ領域に書き込まれた（key,value）群を、前記キャッシュ領域に移動させるとき、
前記（key,value）群のうち、現在時刻から、過去所定時間分までの間に、更新、または、追加された前記（key,value）群を移動させることを特徴とする請求項１ないし請求項３のいずれか１項に記載の情報処理装置。
【請求項５】
前記検索部は、
前記検索要求が、検索の対象である（key,value）の作成時刻の範囲をさらに含むとき、前記キャッシュ領域、および、前記ファイルから、前記keyを含み、かつ、前記作成時刻の範囲に作成された（key,value）を検索する請求項１ないし請求項４のいずれか１項に記載の情報処理装置。
【請求項６】
メインメモリ上に、ＷＡＬ（Write Ahead Logging）ログを備え、前記ＷＡＬログに、KeyValueストアに用いられる（key,value）の削除、変更、または、追加を示すオペレーションの書き込みが成功すると、前記（key,value）を、前記メインメモリ上のバッファ領域へ書き込む情報処理装置を用いた情報処理方法であって、
前記情報処理装置が、
前記バッファ領域に書き込まれた前記（key,value）の集合である（key,value）群のデータ量が所定の閾値を超えたとき、
前記バッファ領域に書き込まれた（key,value）群をファイルへ書き出すファイル作成ステップと、
前記バッファ領域に書き込まれた（key,value）群を、前記メインメモリ上に確保されたキャッシュ領域に移動させるキャッシュ作成ステップと、
前記（key,value）群のファイルへの書き出し、および、前記キャッシュ領域への移動完了後、前記バッファ領域を解放するバッファ解放ステップと、
前記keyを含む検索要求を受け付けたとき、
前記キャッシュ領域からkeyを含む（key,value）を検索し、前記キャッシュ領域に前記keyを含む（key,value）がないとき、前記ファイルから前記keyを含む（key,value）を検索する検索ステップとを実行することを特徴とする情報処理方法。
【請求項７】
メインメモリ上に、ＷＡＬ（Write Ahead Logging）ログを備え、前記ＷＡＬログに、KeyValueストアに用いられる（key,value）の削除、変更、または、追加を示すオペレーションの書き込みが成功すると、前記（key,value）を、前記メインメモリ上のバッファ領域へ書き込むための情報処理プログラムであって、
前記バッファ領域に書き込まれた前記（key,value）の集合である（key,ts,value）群のデータ量が所定の閾値を超えたとき、
前記バッファ領域に書き込まれた（key,value）群をファイルへ書き出すファイル作成ステップと、
前記バッファ領域に書き込まれた（key,value）群を、前記メインメモリ上に確保されたキャッシュ領域に移動させるキャッシュ作成ステップと、
前記（key,value）群のファイルへの書き出し、および、前記キャッシュ領域への移動完了後、前記バッファ領域を解放するバッファ解放ステップと、
前記keyを含む検索要求を受け付けたとき、
前記キャッシュ領域からkeyを含む（key,value）を検索し、前記キャッシュ領域に前記keyを含む（key,value）がないとき、前記ファイルから前記keyを含む（key,value）を検索する検索ステップとをコンピュータに実行させるための情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、および、情報処理プログラムに関する。
【背景技術】
【０００２】
近年、BigTable（非特許文献１参照）等の様々なKeyValueストア技術が提案されている。例えば、BigTableは、ファイルシステム（非特許文献２参照）上で（key,value）のテーブルを管理し、以下のような特徴を持つ。
【０００３】
（１）（key,value）のテーブルをいくつかの範囲に分割し、クラスタ上のサーバ群で管理する。
（２）各サーバでは、ログ先行書き込み用ログファイル(以下、ＷＡＬログとする)を一つ有する。ＷＡＬログは、書き込み要求に対して永続性を担保する。
（３）各サーバは、（key,value）の削除、更新、追加といったオペレーションのＷＡＬログへの書き込みが成功すると、メインメモリ上に確保した（key,value）を格納するためのメインメモリ上のバッファ領域へ書き込みを行う。この時点で、書き込まれた（key,value）は参照可能となる。
（４）上記のメインメモリ上に確保したバッファ領域のデータ量が大きくなった場合、各サーバは、分割した範囲ごとにファイルへ書き込みを行い、バッファ領域を解放する。このように、各サーバは、メインメモリ上のバッファ領域をファイルに書きこんだ時点で、そのバッファ領域を解放することで、ＷＡＬログの肥大化を防いでいる。
【０００４】
このＷＡＬログは、バッファ領域に（key,value）が存在する間、サーバに障害が発生した場合であってもリカバリを可能とするために存在している。例えば、リカバリを依頼されたサーバは、ＷＡＬログを用いて、更新された（key,value）をサーバ上のメインメモリ上のバッファのデータに読み込むことで、更新された（key,value）の復旧を行う。
【０００５】
一般的にサーバのメインメモリ上のバッファ領域が大きければ、ＷＡＬログも大きくなる。そして、ＷＡＬログが肥大化すると、サーバの障害発生後、リカバリ時にメインメモリバッファに展開する為に読み込むデータ量が多くなるため、リカバリ時間が増大してしまう。しかし一方で、メインメモリ上のバッファ領域が大きければ、検索要求受信時にメインメモリ上のバッファを検索し、結果を返却できるため、検索時間を短縮できるというメリットもある。
【０００６】
ここで、リカバリ時間を短縮するため、予めサーバのメインメモリ上のバッファ領域を小さくしておくことも考えられる。しかし、バッファ領域を小さくしてしまうと、サーバは、検索要求受信時に、メインメモリ上のバッファから結果を返却できないこともあり、検索時間が増加してしまう可能性がある。
【０００７】
このような問題を解決するため、ブロックキャッシュという技術がある。このブロックキャッシュは、サーバのメインメモリ上のバッファとは別にキャッシュ領域を準備し、サーバがハードディスク等からブロック（複数の（key,value）のかたまり）をメインメモリ上に読み込んだときには、このブロックをキャッシュとしてメインメモリ上に記憶する。そして、サーバは、次回の検索において、同一ブロックへの読み込み要求がなされた場合、キャッシュ上に存在するブロックを利用する。このようにすることで、サーバにおけるリカバリ時間をある程度短縮しつつ、検索時間を短縮することができる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】F.Chang他、「Bigtable:A Distributed Storage System for Structured Data」、OSDI、2006
【非特許文献２】S. Ghemawat他、「The Google File System」、SOSP、2003
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、前記したブロックキャッシュにおいて、キャッシュ上に存在するブロックは、少なくとも一度はディスクＩ／Ｏが発生したブロックである。このため、サーバが、一度もハードディスクから読み出されたことのないデータの検索要求を受け付けたときには、ハードディスク等からデータを読み込む必要があり、検索時間は必ずしも短縮しない。
【００１０】
そこで、本発明は、前記した問題を解決し、KeyValueストアに用いられるサーバに障害が発生した場合のリカバリ時間を短縮しつつ、検索時間も短縮することを課題とする。
【課題を解決するための手段】
【００１１】
前記した課題を解決するため、本発明の情報処理装置は、メインメモリ上に、ＷＡＬ（Write Ahead Logging）ログを備え、前記ＷＡＬログに、KeyValueストアに用いられる（key,value）の削除、変更、または、追加を示すオペレーションの書き込みが成功すると、前記（key,value）を、前記メインメモリ上のバッファ領域へ書き込む情報処理装置であって、前記バッファ領域に書き込まれた前記（key,value）の集合である（key,value）群のデータ量が所定の閾値を超えたとき、前記バッファ領域に書き込まれた（key,value）群をファイルへ書き出すファイル作成部と、前記バッファ領域に書き込まれた（key,value）群を、前記メインメモリ上に確保されたキャッシュ領域に移動させるキャッシュ作成部と、前記（key,value）群のファイルへの書き出し、および、前記キャッシュ領域への移動完了後、前記バッファ領域を解放するバッファ解放部と、前記keyを含む検索要求を受け付けたとき、前記キャッシュ領域から前記keyを含む（key,value）を検索し、前記キャッシュ領域に前記keyを含む（key,value）がないとき、前記ファイルから前記keyを含む（key,value）を検索する検索部とを備える。
【発明の効果】
【００１２】
本発明によれば、KeyValueストアに用いられるサーバに障害が発生した場合のリカバリ時間を短縮しつつ、検索時間も短縮することができる。
【図面の簡単な説明】
【００１３】
【図１】図１は、第１の実施形態のサーバの概要を説明する図である。
【図２】図２は、サーバの機能構成図である。
【図３】図３は、バッファ領域に（key,ts,value）の削除に関する情報が含まれていた場合におけるファイル作成手順例を説明する図である。
【図４】図４は、サーバの処理手順を説明する図である。
【図５】図５は、図４のＳ１６の処理を詳細に説明する図である。
【図６】図６は、図５のＳ１６４を詳細に説明する図である。
【図７】図７は、サーバが、外部から（key,ts,value）のテーブルの検索要求を受け付けたときの処理手順を説明する図である。
【図８】図８は、第２の実施形態のキャッシュ作成部の処理手順を説明する図である。
【図９】図９は、第２の実施形態のサーバにおけるキャッシュの例を示す図である。
【図１０】図１０は、検索部の処理手順を説明する図である。
【図１１】図１１は、分散KeyValueストアにおけるサーバを例示した図である。
【図１２】図１２は、情報処理プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１４】
［第１の実施形態］
［概要］
以下、本発明の実施形態を第１の実施形態および第２の実施形態に分けて説明する。まず、図１を用いて第１の実施形態の情報処理装置（サーバ）の概要を説明する。図１は、第１の実施形態のサーバの概要を説明する図である。
【００１５】
このサーバ１０は、KeyValueストアに用いられるサーバであり、（key,ts,value）のテーブルを記憶する。なお、本実施形態において、（key,ts,value）のテーブルの内容は、一時的にメインメモリ上のバッファ領域に格納され、その後、ファイルに書き出される。なお、ここではテーブルを構成するデータは、（key,ts,value）である場合を例に説明するが、少なくとも（key,value）を含めばよく、ts（タイムスタンプ値、（key,value）の作成時刻を示す情報）を含まないデータであってもよい。また、サーバ１０が書き出すファイルは、ソート済みKeyValueファイルである場合を例に説明するが、これに限定されない。
【００１６】
サーバ１０は、外部装置からの指示に基づき（key,ts,value）のテーブルに対し（key,ts,value）の追加、削除、更新を行う。また、サーバ１０は、外部からkeyを含む検索要求を受信すると、（key,ts,value）のテーブルにおいて、当該Keyを持つ値を検索して、その検索結果を返す。
【００１７】
さらに、このサーバ１０は、ログ先行書き込み用ログファイル(以下、ＷＡＬログとする)を有する。ＷＡＬログは、（key,ts,value）のテーブルに対する、追加、削除、更新等の変更内容を示す情報であり、（key,ts,value）のテーブルの実際の変更前に書き込まれる。そして、サーバ１０に障害が発生したとき、サーバ１０は、メインメモリのバッファ領域上にある更新された（key,value）を読み込み、ＷＡＬログを用いて、更新データの復旧を行う。このサーバ１０は、メインメモリ上に、バッファ領域とキャッシュ領域とを備える。
【００１８】
このようなサーバ１０が、（１）ユーザの端末装置等から、(newkey,tsN,newvalue)の追加指示を受け付けた場合、サーバ１０は、（２）追加指示の内容のＷＡＬログへの書き込みを行う。その後、(３)メインメモリ上のバッファ領域へ(newkey,tsN,newvalue)の書き込みを行う。そして、（４）メインメモリ上のバッファが大きくなると(つまり、バッファ領域のデータ量が所定の閾値を超えた場合)、サーバ１０は、バッファ領域のデータ（（key,ts,value）群）をファイルに書き出す。例えば、サーバ１０は、バッファ領域の（key,ts,value）群を、keyの値でソートし、ソート済みKeyValueファイル１へ書き込む。
【００１９】
また、（５）サーバ１０は、バッファ領域のデータをメインメモリ上に確保したキャッシュ領域へ移動する。そして、（６）サーバ１０は、メインメモリ上のバッファ領域のデータをクリアする。
【００２０】
その後、（７）サーバ１０が、keyを含む検索要求を受信したとき、まず、メインメモリ上のキャッシュ領域を検索し、（８）次に、補助記憶部上のファイルを検索する。つまり、サーバ１０は、keyを含む検索要求を受信したとき、まず、メインメモリ上のキャッシュ領域からkeyを含む（key,ts,value）を検索し、キャッシュ領域に当該keyを含む（key,ts,value）がなければ、補助記憶部上のソート済みKeyValueファイルからkeyを含む（key,ts,value）を検索する。
【００２１】
このように、サーバ１０は、メインメモリ上のバッファ領域のデータが大きくなると、ファイルへの書き込みを行い、バッファ領域のデータをクリアする。これにより、ＷＡＬログの肥大化を抑制でき、サーバ１０に障害が発生した場合のリカバリ時間を短縮できる。また、サーバ１０が、バッファ領域のデータをクリアする前に、バッファ領域の（key,ts,value）群をキャッシュ領域に移動しておく。そして、サーバ１０が、検索要求を受信した場合、まず、メインメモリ上のキャッシュ領域を検索する。これにより、サーバ１０における検索時間を短縮できる。
【００２２】
［構成］
次に、図２を用いて、サーバ１０の構成を説明する。図２は、サーバの機能構成図である。サーバ１０は、図２に示すように、補助記憶部１１、メインメモリ１２、制御部１３、および、入出力インタフェース１４を備える。
【００２３】
補助記憶部１１は、ＷＡＬログと、ソート済みKeyValueファイルとを記憶する。ＷＡＬログは、前記したとおり、サーバ１０の（key,ts,value）のテーブルに対する、追加、削除、更新等の変更内容を示す情報であり、（key,ts,value）のテーブルの実際の変更前に書き込まれる。そして、このＷＡＬログは、サーバ１０に障害が発生したとき、リカバリ部１３７（後記）が、更新データの復旧を行う際に参照される。
【００２４】
ソート済みKeyValueファイルは、（key,ts,value）のテーブルを格納するファイルである。このソート済みKeyValueファイルは、例えば、バッファ領域の（key,ts,value）群を、keyの値でソートしたファイルである。
【００２５】
メインメモリ１２は、バッファ領域と、キャッシュ領域とを備える。バッファ領域は、当該サーバ１０において受け付けた（key,ts,value）のテーブルに対する、追加、削除、更新内容を示す情報（実際には（key,ts,value）群で示されるデータ）を一時的に格納する領域である。
【００２６】
キャッシュ領域は、バッファ領域にあった（key,ts,value）群を一時的に格納する領域である。このキャッシュ領域の（key,ts,value）群は、検索部１３４（後記）がKeyを含む検索要求を受け付けたときに、検索される。
【００２７】
制御部１３は、サーバ１０全体の制御を司り、データ書き込み部１３０と、ファイル作成部１３１と、キャッシュ作成部１３２と、バッファ解放部１３３と、検索部１３４と、キャッシュ削除部１３５と、最大キャッシュサイズ登録部１３６と、リカバリ部１３７とを備える。キャッシュ作成部１３２ａ、および、キャッシュ保持期間登録部１３８は装備する場合と、装備しない場合とがあり、装備する場合については、第２の実施形態で述べる。
【００２８】
データ書き込み部１３０は、入出力インタフェース１４経由で、（key,ts,value）のテーブルに対する、削除、変更、または、追加等の更新内容を示す情報の入力を受け付けると、この情報をＷＡＬログへ書き込む。そして、データ書き込み部１３０は、ＷＡＬログへの書き込みが成功すると、この更新内容を示す（key,ts,value）を、メインメモリ１２上のバッファ領域へ書き込む。つまり、データ書き込み部１３０は、（key,ts,value）の削除、変更、または、追加を示すオペレーションをＷＡＬログへ書き込み、この書き込みが成功すると、このオペレーションの内容をメインメモリ１２上のバッファ領域へ書き込む。
【００２９】
ファイル作成部１３１は、メインメモリ１２上のバッファ領域に書き込まれた（key,ts,value）群のデータ量が所定の閾値を超えた場合、この（key,ts,value）群をファイルへ書き出す。例えば、ファイル作成部１３１は、メインメモリ１２上のバッファ領域に書き込まれた（key,ts,value）群のデータ量が所定の閾値を超えた場合、この（key,ts,value）群をKeyの値でソートして、ソート済みKeyValueファイルを作成し、補助記憶部１１へ格納する。
【００３０】
なお、このバッファ領域に書き込まれた（key,ts,value）群に、（key,ts,value）の削除に関する情報が含まれていた場合、このバッファ領域に書き込まれた（key,ts,value）群と、すべてのソート済みKeyValueファイルを読み込み、削除すべき（key,ts,value）を削除した上で新しいソート済みKeyValueファイルを作成する。
【００３１】
図３は、バッファ領域に（key,ts,value）の削除に関する情報が含まれていた場合におけるファイル作成手順例を説明する図である。例えば、図３に示すように、バッファ領域の（key,ts,value）群に（key,ts,value）の削除に関する情報であるＤ（key303,ts13,value303）が含まれていた場合、まず、ファイル作成部１３１は、（１）全ての（key,ts,value）ペアを読み込み、削除するべき（key,ts,value）を削除した上で新しいファイルを作成する。つまり、ファイル作成部１３１は、メインメモリ１２のバッファ領域の（key,ts,value）および補助記憶部１１のソート済みKeyValueファイル１，２，…，を読み込み、（key303,ts13,value303）を削除した上でソート済みKeyValueファイルnewを作成する。その後、ファイル作成部１３１は、（２）既存のファイルとメインメモリ１２上の（key,ts,value）を削除する。つまり、ファイル作成部１３１は、ソート済みKeyValueファイル１，２，…，と、バッファ領域の（key,ts,value）群を削除する。
【００３２】
このようにすることで、ファイル作成部１３１は、（key,ts,value）の削除を、（key,ts,value）のテーブルへ反映させることができる。
【００３３】
図２のキャッシュ作成部１３２は、メインメモリ１２上のバッファ領域に書き込まれた（key,ts,value）群のデータ量が所定の閾値を超え、ファイル作成部１３１によりバッファ領域の（key,ts,value）群がソート済みKeyValueファイルへ書き出されるとき、バッファ領域の（key,ts,value）群を、キャッシュとしてメインメモリ１２のキャッシュ領域に移動させる。なお、前記したファイル作成部１３１により、（key,ts,value）の削除が行われ、新たなソート済みKeyValueファイルへ書き出されるときは、削除対象の（key,ts,value）が削除された（key,ts,value）群を、キャッシュとしてメインメモリ１２のキャッシュ領域に移動する。
【００３４】
バッファ解放部１３３は、バッファ領域の（key,ts,value）群の、ファイルへの書き出し、および、キャッシュ領域への移動完了後、バッファ領域を解放する。つまり、バッファ領域のデータをクリアして、他のデータを書き込み可能な状態にする。
【００３５】
検索部１３４は、keyを含む検索要求を受け付けたとき、まず、メインメモリ１２のキャッシュ領域から当該keyを含むキャッシュを検索する。ここで、当該keyを持つ（key,ts,value）を含むキャッシュがあれば、このキャッシュの（key,ts,value）群からの検索結果を、検索要求の送信元へ返す。一方、キャッシュ領域に、当該keyを持つ（key,ts,value）を含むキャッシュがなければ、ソート済みKeyValueファイルから当該keyを持つ（key,ts,value）を検索し、検索結果を検索要求の送信元へ返す。なお、この検索部１３４は、キャッシュ領域のキャッシュを検索したとき、検索でヒットしたキャッシュに、このときの検索時刻を示す情報を付与しておく。詳細は後記するが、キャッシュに付与された検索時刻を示す情報は、キャッシュ削除部１３５が、削除対象のキャッシュを選択する際に参照される。
【００３６】
キャッシュ削除部１３５は、キャッシュ領域のデータ量が、所定のデータ量（最大キャッシュサイズＡ）を超えたとき、キャッシュ領域のキャッシュのうち、検索時刻の古いキャッシュから優先的に削除する。
【００３７】
最大キャッシュサイズ登録部１３６は、入出力インタフェース１４経由で、キャッシュ削除部１３５が用いる最大キャッシュサイズＡの登録を受け付ける。受け付けた最大キャッシュサイズＡは、メインメモリ１２に格納する。
【００３８】
リカバリ部１３７は、サーバ１０に障害等が発生したとき、メインメモリ１２のバッファ領域の（key,ts,value）を読み込み、ＷＡＬログを用いて、データの復旧を行う。例えば、サーバ１０において更新データの入力を受け付けたが、障害等により、バッファ領域の更新データが、ソート済みKeyValueファイルに反映されていないとき、リカバリ部１３７は、メインメモリ１２のバッファ領域のデータと、ＷＡＬログとを用いて、更新データを復旧し、必要に応じてソート済みKeyValueファイルへ反映させる。
【００３９】
入出力インタフェース１４は、当該サーバ１０へのデータ入力およびデータ出力を司るインタフェースである。例えば、入出力インタフェース１４は、外部装置から、このサーバ１０の（key,ts,value）のテーブルに対する、追加、削除、更新内容を示す情報、（key,ts,value）のテーブルの検索要求、メインメモリ１２の最大キャッシュサイズＡ、当該サーバ１０への設定情報等の情報の入力を受け付けると、これらの情報を制御部１３へ渡す。また、入出力インタフェース１４は、制御部１３から出力された検索結果等を外部装置等へ出力する。
【００４０】
［処理手順］
次に、図４を用いて、サーバ１０の処理手順を説明する。なお、事前にサーバ１０の最大キャッシュサイズ登録部１３６において、最大キャッシュサイズＡの登録を受け付け、メインメモリ１２に格納しておくものとする。図４は、サーバの処理手順を説明する図である。
【００４１】
まず、サーバ１０のデータ書き込み部１３０は、入出力インタフェース１４経由で、（key,ts,value）のテーブルに対する、削除、変更、または、追加等の更新情報の入力を受け付けると（Ｓ１１）、この情報をＷＡＬログへ書き込む（Ｓ１２）。また、データ書き込み部１３０は、当該情報をメインメモリ１２上のバッファ領域へも書き込む（Ｓ１３）。
【００４２】
Ｓ１３の後、ファイル作成部１３１は、メインメモリ１２上のバッファ領域のデータ量が所定の閾値を超えた場合（Ｓ１４のＹｅｓ）、バッファ領域の（key,ts,value）群をファイルへ書き出す（Ｓ１５）。例えば、ファイル作成部１３１は、メインメモリ１２上のバッファ領域に書き込まれた（key,ts,value）群をKeyの値でソートしてソート済みKeyValueファイルを作成し、補助記憶部１１に格納する。
【００４３】
一方、メインメモリ１２上のバッファ領域のデータ量が所定の閾値以下の場合（Ｓ１４のＮｏ）、Ｓ１１へ戻る。
【００４４】
また、Ｓ１５の後、サーバ１０のキャッシュ作成部１３２は、バッファ領域の（key,ts,value）群を、キャッシュとしてメインメモリ１２のキャッシュ領域に移動させる（Ｓ１６）。このＳ１６の処理の詳細は後記する。
【００４５】
Ｓ１６の後、バッファ解放部１３３は、バッファの解放を行う（Ｓ１７）。つまり、バッファ解放部１３３は、バッファ領域の（key,ts,value）群をクリアし、データを書き込み可能な状態にし、処理を終了する。
【００４６】
次に、図５を用いて、図４のＳ１６の処理を詳細に説明する。図５は、図４のＳ１６の処理を詳細に説明する図である。
【００４７】
図４のＳ１５の後、サーバ１０のキャッシュ作成部１３２は、メインメモリ１２上のバッファをキャッシュ領域に移動する（Ｓ１６１）。つまり、キャッシュ作成部１３２は、バッファ領域の（key,ts,value）群を、キャッシュとしてメインメモリ１２のキャッシュ領域に移動する。
【００４８】
Ｓ１６１の後、キャッシュ作成部１３２は、現時点で利用しているキャッシュサイズＢに、移動したバッファサイズを追加する（Ｓ１６２）。つまり、キャッシュ作成部１３２は、バッファ領域からキャッシュ領域へ移動した（key,ts,value）群のデータ量をキャッシュサイズＢに加算する。
【００４９】
そして、キャッシュ作成部１３２は、Ｓ１６２で追加したキャッシュサイズＢが最大キャッシュサイズＡを超えているか否かを判断し、Ｓ１６２で追加したキャッシュサイズＢが最大キャッシュサイズＡを超えていると判断したとき（Ｓ１６３のＹｅｓ）、キャッシュ削除部１３５は、キャッシュ削除を行う（Ｓ１６４）。そして、Ｓ１６の処理を終了する。Ｓ１６４の処理の詳細は後記する。
【００５０】
一方、キャッシュ作成部１３２は、Ｓ１６２で追加したキャッシュサイズＢが最大キャッシュサイズＡを超えていないと判断したとき（Ｓ１６３のＮｏ）、Ｓ１６の処理を終了する。
【００５１】
次に、図６を用いて、図５のＳ１６４を詳細に説明する。図６は、図５のＳ１６４を詳細に説明する図である。
【００５２】
図５のＳ１６３でＹｅｓだったとき、キャッシュ削除部１３５は、キャッシュ領域の全キャッシュの中から、検索時刻が最も古いものを選択し、メインメモリ１２上から解放する（Ｓ１６４１）。Ｓ１６４１の後、キャッシュ削除部１３５は、キャッシュサイズＢから、解放したキャッシュのデータ分のサイズを削減し（Ｓ１６４２）、キャッシュサイズＢが最大キャッシュサイズＡを超えているか否かを判断し（Ｓ１６４３）、キャッシュサイズＢが最大キャッシュサイズＡを超えていなければ（Ｓ１６４３のＮｏ）、Ｓ１６４の処理を終了する。一方、キャッシュ削除後も、キャッシュサイズＢが最大キャッシュサイズＡを超えていれば（Ｓ１６４３のＹｅｓ）、Ｓ１６４１へ戻り、キャッシュ削除部１３５は、さらにキャッシュ領域のキャッシュの削除を行う。
【００５３】
このように、キャッシュ削除部１３５は、キャッシュ領域のキャッシュの占めるデータ量が、最大キャッシュサイズＡ以下となるよう、検索時刻が最も古いキャッシュから順に削除する。これにより、メインメモリ１２上の限られたキャッシュ領域上には比較的最近に検索された（key,ts,value）が乗ることになる。なお、サーバ１０の受け付ける検索要求は、比較的最近作成された（key,ts,value）に関する検索要求が多い場合、サーバ１０がキャッシュ領域に比較的最近に検索された（key,ts,value）を乗せるようにすることで、検索時間を短縮できる可能性を高めることができる。
【００５４】
次に、図７を用いて、サーバ１０が、外部から（key,ts,value）のテーブルの検索要求を受け付けたときの処理手順を説明する。図７は、サーバが、外部から（key,ts,value）のテーブルの検索要求を受け付けたときの処理手順を説明する図である。
【００５５】
まず、サーバ１０の検索部１３４は、keyを含む検索要求を受け付けると（Ｓ２１）、まず、キャッシュ領域に当該keyを含むキャッシュが存在するか否かを判断する（Ｓ２２）。ここで、検索部１３４は、キャッシュ領域に当該keyを含むキャッシュが存在するとき（Ｓ２２のＹｅｓ）、ソート済みKeyValueファイルの代わりに当該キャッシュを検索する（Ｓ２３）。そして、検索部１３４は、キャッシュから得られた当該keyを含む（key,ts,value）を検索結果として返す。一方、検索部１３４は、キャッシュ領域に当該keyを含むキャッシュが存在しないとき（Ｓ２２のＮｏ）、ソート済みKeyValueファイルを検索する（Ｓ２４）。そして、検索部１３４は、ソート済みKeyValueファイルから得られた当該keyを含む（key,ts,value）を検索結果として返す。
【００５６】
つまり、サーバ１０は、キャッシュ領域に検索対象の（key,ts,value）が存在すれば、このキャッシュ領域の（key,ts,value）を返すので、（key,ts,value）の検索時間を短縮できる可能性が高くなる。特に、サーバ１０が、比較的最近に（key,ts,value）のテーブルに追加されたり、検索されたりした（key,ts,value）に関する検索要求を受信することが多い場合、（key,ts,value）の検索時間を短縮できる可能性はさらに高くなる。
【００５７】
なお、第１の実施形態において、キャッシュ削除部１３５がキャッシュ削除をするとき、キャッシュのうち、検索時刻が古いものから優先的に削除することとしたが、これに限定されない。例えば、キャッシュ削除部１３５は、キャッシュに含まれる（key,ts,value）群のうち、tsの値が古い（key,ts,value）から優先的に削除するようにしてもよい。
【００５８】
［第２の実施形態］
次に、本発明の第２の実施形態を説明する。第１の実施形態と同じ構成、同じ処理については説明を省略する。第２の実施形態のサーバ１０ａは、バッファ領域の（key,ts,value）群をキャッシュ領域へ移動させるとき、このバッファ領域の（key,ts,value）群のうち、現在時刻から過去所定時間分の（key,ts,value）群をキャッシュ領域へ移動させることを特徴とする。
【００５９】
［構成］
この第２の実施形態のサーバ１０ａは、図２の破線で示すキャッシュ保持期間登録部１３８をさらに備える。また、サーバ１０ａは、キャッシュ作成部１３２に代えて、キャッシュ作成部１３２ａを備える。
【００６０】
キャッシュ保持期間登録部１３８は、入出力インタフェース１４経由で、キャッシュ保持期間の入力を受け付ける。このキャッシュ保持期間Ｔは、メインメモリ１２上に格納される。
【００６１】
キャッシュ作成部１３２ａは、メインメモリ１２上のバッファ領域の（key,ts,value）群をキャッシュ領域に移動するとき、バッファ領域の（key,ts,value）群のうち、tsの値が（現在時刻−キャッシュ保持期間＝時刻Ｔ）である（key,ts,value）群を選択し、移動する。
【００６２】
［処理手順］
このようなキャッシュ作成部１３２ａの処理手順を、図８を用いて説明する。図８は、第２の実施形態のキャッシュ作成部の処理手順を説明する図である。なお、サーバ１０ａは、事前に、キャッシュ保持期間登録部１３８により、入出力インタフェース１４経由で、キャッシュ保持期間の入力を受け付けておくものとする。
【００６３】
まず、キャッシュ作成部１３２ａは、メインメモリ１２上のバッファ領域に書き込まれた（key,ts,value）群のデータ量が所定の閾値を超え、ファイル作成部１３１によりバッファ領域の（key,ts,value）群がソート済みKeyValueファイルへ書き出されるとき、バッファ領域の（key,ts,value）群のtsを取得する。また、キャッシュ作成部１３２ａは、（現在時刻−キャッシュ保持期間）をＴと置く（Ｓ３１）。
【００６４】
Ｓ３１の後、キャッシュ作成部１３２ａは、Ｓ３１で取得したtsについて、Ｔ＜tsであるか否かを判断し（Ｓ３２）、Ｔ＜tsであるとき（Ｓ３２のＹｅｓ）、すなわち、tsの示す時刻が時刻Ｔより後であるとき、当該tsを持つ（key,ts,value）群をキャッシュ領域のキャッシュとして移動し（Ｓ３３）、Ｓ３４へ進む。一方、Ｔ＜ｔｓでないとき（Ｓ３２のＮｏ）は、Ｓ３４へ進む。
【００６５】
Ｓ３４において、キャッシュ作成部１３２ａは、バッファ領域の（key,ts,value）群のうち未処理の（key,ts,value）があれば（Ｓ３４のＮｏ）、Ｓ３１へ戻り、バッファ領域の（key,ts,value）群をすべて処理したときには（Ｓ３４のＹｅｓ）、Ｓ３５へ進む。このＳ３５以降の処理は、前記した図５のＳ１６３以降の処理と同様なので詳細な説明を省略するが、キャッシュ削除部１３５は、現時点で利用しているキャッシュサイズＢが最大キャッシュサイズＡを超えたとき（Ｓ３６のＹｅｓ）、Ｓ３７において、キャッシュ領域のキャッシュから、tsの値が最も古い（key,ts,value）を含むキャッシュを削除する。
【００６６】
このようにすることで、キャッシュ領域には、tsの値が比較的新しい（key,ts,value）群が乗ることになる。よって、サーバ１０ａの受け付ける検索要求が、比較的最近作成された（key,ts,value）に関する検索要求が多い場合、キャッシュ領域にtsの値が比較的新しい（key,ts,value）群が乗ることで、サーバ１０ａにおける検索時間を短縮できる可能性は高くなる。
【００６７】
この第２の実施形態のサーバ１０ａの効果を、図９を参照しながら詳細に説明する。図９は、第２の実施形態のサーバにおけるキャッシュの例を示す図である。ここではキャッシュ領域上にキャッシュ１〜キャッシュ４の４つのキャッシュが乗る場合を例に説明する。
【００６８】
図９における横軸は、tsの値を示す。実線の囲みは、第２の実施形態のサーバ１０ａにおける各キャッシュを構成する（key,ts,value）群を示し、破線の囲みは、キャッシュ１〜キャッシュ４の元となったバッファ領域の（key,ts,value）群を示す。つまり、図９の各囲みにおける右端の値は、その（key,ts,value）群の中で最も新しいtsの値を示し、各囲みにおける左端の値は、その（key,ts,value）群の中で最も古いtsの値を示す。例えば、符号９１〜９４に示す（key,ts,value）群をすべてがキャッシュとしてキャッシュ領域に乗った後、キャッシュ削除部１３５が、tsの値の最も古い、符号９３に示す（key,ts,value）群を削除してしまうと、tsの値が比較的新しい（key,ts,value）も削除してしまい、検索時にキャッシュ領域上でヒットしない可能性が出てくる。
【００６９】
しかし、サーバ１０ａのキャッシュ作成部１３２ａは、バッファ領域の（key,ts,value）群のうち、（現在時刻−キャッシュ保持期間）＜tsである（key,ts,value）群を選択して、キャッシュ領域に乗せる。これにより、キャッシュ領域におけるキャッシュのメモリ使用量を短縮でき、かつ、tsの値が比較的新しい（key,ts,value）群が占める割合を高くすることができる。つまり、限られたキャッシュ領域上にヒットする可能性の高いデータを乗せることができる。
【００７０】
［その他の実施形態］
また、サーバ１０，１０ａの検索部１３４が受け付ける検索要求は、keyのみならず、検索の対象であるtsの範囲（タイムスタンプ区間）を含んでいてもよい。この場合、検索部１３４は、受け付けた検索要求に示される範囲のtsの値を持つ（key,ts,value）を、キャッシュ領域、および、ファイルから検索する。
【００７１】
この検索部１３４の処理手順を、図１０を用いて説明する。図１０は、検索部の処理手順を説明する図である。検索部１３４は、keyおよびタイムスタンプ区間を含む検索要求を受け付けると（Ｓ４１）、キャッシュ領域に、当該keyを含むキャッシュ（（key,ts,value）群）が存在し（Ｓ４２のＹｅｓ）、かつ、当該キャッシュのtsが、当該タイムスタンプ区間に含まれる場合（Ｓ４３のＹｅｓ）、Ｓ４４へ進む。Ｓ４４は、図７のＳ２３と同様なので説明を省略する。
【００７２】
一方、キャッシュ領域に、当該keyを含むキャッシュが存在しない（Ｓ４２のＮｏ）、または、当該キャッシュのtsが、当該タイムスタンプ区間に含まれない（Ｓ４３のＮｏ）場合、Ｓ４５へ進む。Ｓ４５は、図７のＳ２４と同様なので説明を省略する。
【００７３】
このようにすることで、サーバ１０，１０ａは、タイムスタンプ区間が指示された検索要求についても検索結果を返すことができる。
【００７４】
なお、前記したサーバ１０，１０ａを分散KeyValueストアのシステムに用いてもよい。この場合、サーバ１０，１０ａが保持する（key,ts,value）のテーブルは、分散KeyValueストアにおいて、元のテーブルを分割したテーブルである。図１１は、分散KeyValueストアにおけるサーバを例示した図である。
【００７５】
例えば、図１１に示すように、システムが、マスタサーバ（サーバ１０Ｄ）と、複数のスレーブサーバ（サーバ１０Ａ，１０Ｂ，１０Ｃ）とにより構成される場合を考える。このような場合において、サーバ１０Ａ，１０Ｂ，１０Ｃそれぞれが保持する（key,ts,value）のテーブルは、元のテーブルＡを複数のエリアに分割したテーブルである。例えば、サーバ１０Ａは、エリア０，３の（key,ts,value）のテーブルを保持し、サーバ１０Ｂは、エリア１，４の（key,ts,value）のテーブルを保持する。そして、サーバ１０Ｄは、（key,ts,value）の削除、変更、追加、検索等の要求を受け付けると、その（key,ts,value）を含むエリアの（key,ts,value）のテーブルを保持するスレーブサーバ（サーバ１０Ａ，１０Ｂ，１０Ｃ）へ、その要求を転送する。そして、サーバ１０Ａ，１０Ｂ，１０Ｃは、前記した各実施形態で述べた処理と同様の処理を実行し、その実行結果を、サーバ１０Ｄへ返す。
【００７６】
［プログラム］
前記したサーバ１０，１０ａが実行する処理をコンピュータが実行可能な言語で記述したプログラム（情報処理プログラム）で実現することもできる。この場合、コンピュータがプログラムを実行することにより、上記実施形態と同様の効果を得ることができる。さらに、かかるプログラムをコンピュータで読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませて実行することにより前記した実施形態と同様の処理を実現してもよい。以下に、サーバ１０，１０ａと同様の機能を実現する情報処理プログラムを実行するコンピュータの一例を説明する。
【００７７】
図１２は、情報処理プログラムを実行するコンピュータを示す図である。図１２に例示するように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有し、これらの各部はバス１０８０によって接続される。
【００７８】
メモリ１０１０は、図１２に例示するように、ＲＯＭ（Read  Only  Memory）１０１１及びＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、図１２に例示するように、ハードディスクドライブ１０３１に接続される。ディスクドライブインタフェース１０４０は、図１２に例示するように、ディスクドライブ１０４１に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１０４１に挿入される。シリアルポートインタフェース１０５０は、図１２に例示するように、例えばマウス１０５１、キーボード１０５２に接続される。ビデオアダプタ１０６０は、図１２に例示するように、例えばディスプレイ１０６１に接続される。 
【００７９】
ここで、図１２に例示するように、ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、上記のプログラムは、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、例えばハードディスクドライブ１０３１に記憶される。 
【００８０】
また、上記実施の形態で説明した各種データは、プログラムデータとして、例えばメモリ１０１０やハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出し、制御部１３の各部の機能を実現する。
【００８１】
なお、プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１０４１等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００８２】
１０，１０ａ    サーバ（情報処理装置）
１１    補助記憶部
１２    メインメモリ
１３    制御部
１４    入出力インタフェース
１３０  データ書き込み部
１３１  ファイル作成部
１３２，１３２ａ  キャッシュ作成部
１３３  バッファ解放部
１３４  検索部
１３５  キャッシュ削除部
１３６  最大キャッシュサイズ登録部
１３７  リカバリ部
１３８  キャッシュ保持期間登録部
【図１】
2014229036.tif 000003
【図２】
2014229036.tif 000004
【図３】
2014229036.tif 000005
【図４】
2014229036.tif 000006
【図５】
2014229036.tif 000007
【図６】
2014229036.tif 000008
【図７】
2014229036.tif 000009
【図８】
2014229036.tif 000010
【図９】
2014229036.tif 000011
【図１０】
2014229036.tif 000012
【図１１】
2014229036.tif 000013
【図１２】
2014229036.tif 000014