(57)【特許請求の範囲】
【請求項１】
マスターサーバと、複数のスレーブサーバとを有し、前記マスターサーバが、複数のデータを記憶するテーブルを分割することによって前記複数のスレーブサーバのそれぞれに複数の部分テーブルを割り当て、前記複数のスレーブサーバのそれぞれが、前記割り当てられた複数の部分テーブルを、当該複数の部分テーブルのそれぞれへの更新情報を記憶するWALログを用いて管理する分散データストアシステムであって、
前記複数のスレーブサーバのそれぞれは、当該スレーブサーバが管理している複数の部分テーブルのそれぞれを複数のグループのいずれかに分類し、該複数のグループのそれぞれと、前記WALログを複数のファイルに分割することによって生成された、前記複数のグループのそれぞれに属する部分テーブルへの更新情報を記憶する複数の分割WALログのそれぞれとを対応付けるWALログ管理部を有し、
前記マスターサーバは、
前記複数のスレーブサーバのそれぞれに障害が発生したことを検知する障害検知部と、
前記障害検知部にて前記複数のスレーブサーバのいずれかに障害が発生したことが検知されると、当該障害が発生したスレーブサーバの複数の分割WALログのそれぞれを選択し、該選択された分割WALログに対応するグループに属する部分テーブルを管理させるスレーブサーバを、前記複数のスレーブサーバのうち、当該障害が発生したスレーブサーバ以外のスレーブサーバの中からリカバリ用スレーブサーバとして選択するリカバリ要求部と、を有し、
前記複数のスレーブサーバのそれぞれは、前記リカバリ要求部にて当該スレーブサーバが前記リカバリ用スレーブサーバとして選択された場合、前記選択された分割WALログを読み込むことにより、当該選択された分割WALログに対応するグループに属する部分テーブルの管理を開始するリカバリ処理部を有する分散データストアシステム。
【請求項２】
請求項１に記載の分散データストアシステムにおいて、
前記リカバリ要求部は、前記複数のスレーブサーバのそれぞれが管理している部分テーブルの数に応じ、前記複数のスレーブサーバのうち、当該障害が発生したスレーブサーバ以外のスレーブサーバの中から前記リカバリ用スレーブサーバを選択する分散データストアシステム。
【請求項３】
請求項１または請求項２に記載の分散データストアシステムにおいて、
前記マスターサーバは、前記複数のスレーブサーバのそれぞれが管理している部分テーブルの数が、当該複数のスレーブサーバ間で均一化されているかどうかを判定する均一化判定を実行するリバランス部をさらに有し、
前記リバランス部は、前記均一化判定において均一化されていないと判定した場合、前記複数のスレーブサーバの中から、管理している部分テーブルの数が最多のスレーブサーバを最多スレーブサーバとして選択するとともに、管理している部分テーブルの数が最少のスレーブサーバを最少スレーブサーバとして選択し、
前記複数のスレーブサーバのそれぞれは、
前記リバランス部にて当該スレーブサーバが前記最多スレーブサーバとして選択された場合、当該スレーブサーバにて管理している部分テーブルのうちのいずれかを選択し、該選択した部分テーブルを管理対象から除外するアンロード部と、
前記リバランス部にて当該スレーブサーバが前記最少スレーブサーバとして選択された場合、前記管理対象から除外された部分テーブルを、当該スレーブサーバが管理する部分テーブルとするロード部と、をさらに有する分散データストアシステム。
【請求項４】
マスターサーバと、複数のスレーブサーバとを有し、前記マスターサーバが、複数のデータを記憶するテーブルを分割することによって前記複数のスレーブサーバのそれぞれに複数の部分テーブルを割り当て、前記複数のスレーブサーバのそれぞれが、前記割り当てられた複数の部分テーブルを、当該複数の部分テーブルのそれぞれへの更新情報を記憶するWALログを用いて管理する分散データストアシステムにおける障害復旧方法であって、
前記複数のスレーブサーバのそれぞれが、当該スレーブサーバが管理している複数の部分テーブルのそれぞれを複数のグループのいずれかに分類し、該複数のグループのそれぞれと、前記WALログを複数のファイルに分割することによって生成された、前記複数のグループのそれぞれに属する部分テーブルへの更新情報を記憶する複数の分割WALログのそれぞれとを対応付ける処理と、
前記マスターサーバが、前記複数のスレーブサーバのいずれかに障害が発生したことを検知すると、当該障害が発生したスレーブサーバの複数の分割WALログのそれぞれを選択する処理と、
前記マスターサーバが、前記選択された分割WALログに対応するグループに属する部分テーブルを管理させるスレーブサーバを、前記複数のスレーブサーバのうち、当該障害が発生したスレーブサーバ以外のスレーブサーバの中からリカバリ用スレーブサーバとして選択する選択処理と、
前記複数のスレーブサーバのそれぞれが、当該スレーブサーバが前記リカバリ用スレーブサーバとして選択された場合、前記選択された分割WALログを読み込むことにより、当該選択された分割WALログに対応するグループに属する部分テーブルの管理を開始する処理と、を有する障害復旧方法。
【請求項５】
請求項４に記載の障害復旧方法において、
前記選択処理は、前記マスターサーバが、前記複数のスレーブサーバのそれぞれが管理している部分テーブルの数に応じ、前記複数のスレーブサーバのうち、当該障害が発生したスレーブサーバ以外のスレーブサーバの中から前記リカバリ用スレーブサーバを選択する処理である障害復旧方法。
【請求項６】
請求項４または請求項５に記載の障害復旧方法において、
前記マスターサーバが、前記複数のスレーブサーバのそれぞれが管理している部分テーブルの数が、当該複数のスレーブサーバ間で均一化されているかどうかを判定する均一化判定を実行する処理と、
前記マスターサーバが、前記均一化判定において均一化されていないと判定した場合、前記複数のスレーブサーバの中から、管理している部分テーブルの数が最多のスレーブサーバを最多スレーブサーバとして選択するとともに、管理している部分テーブルの数が最少のスレーブサーバを最少スレーブサーバとして選択する処理と、
前記複数のスレーブサーバのそれぞれが、当該スレーブサーバが前記最多スレーブサーバとして選択された場合、当該スレーブサーバにて管理している部分テーブルのうちのいずれかを選択し、該選択した部分テーブルを管理対象から除外する処理と、
前記複数のスレーブサーバのそれぞれが、当該スレーブサーバが前記最少スレーブサーバとして選択された場合、前記管理対象から除外された部分テーブルを、当該スレーブサーバが管理する部分テーブルとする処理と、をさらに有する障害復旧方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、PC(Personal Computer）クラスタ上で動作する分散データストアシステムおよび障害復旧方法に関する。
【背景技術】
【０００２】
分散KeyValueストアシステムの１つであるBigtable（非特許文献１参照）は、分散ファイルシステムGFS（Google File System）（非特許文献２参照）上で複数のデータを記憶しているテーブルを管理する。Bigtableには、以下に示すような特徴がある。
【０００３】
・テーブルを分割することにより、PCクラスタ上の複数のサーバのそれぞれに複数の部分テーブル割り当てる。
【０００４】
・複数のサーバのそれぞれは、割り当てられた複数の部分テーブルへの更新情報を記憶する１つのログ先行書き込み用のログファイル（以降、WAL（Write Ahead Logging）ログという）を用いて、割り当てられた複数の部分テーブルを管理する。
【０００５】
Bigtableと同様のアーキテクチャを採用する分散KeyValueストアシステムとしては、Hbase（非特許文献３参照）や、Hypertable（非特許文献４参照）等が挙げられるが、いずれのアーキテクチャにおいても１つのサーバが有するWALログは１つである。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallarch, M. Burrows, T. Chandra, A. Fikes, and r. E. Gruber, “Bigtable: A Distributed Storage System for Structured Data,” OSDI(2006).
【非特許文献２】S. Ghemawat, H. Gobioff, S.-T. Leung, “The Google File System, ” SOSP(2003).
【非特許文献３】A. Khurana, “HBase,” Hadoop Day(2010).
【非特許文献４】D. Judd, “Hypertable: An Open Source, High Performance, Scalable Database,” OSCON(2008).
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述したBigtableをはじめとする分散KeyValueストアシステムでは、複数のサーバのいずれかに障害が発生した場合、その複数のサーバのうち障害が発生したサーバ以外の１台のサーバが、障害が発生したサーバのWALログを読み出して、自身に読み込ませる。これにより、障害が発生したサーバが管理していた複数の部分テーブルの管理が再開され、分散KeyValueストアシステムが障害から復旧することになる。
【０００８】
ここで、WALログのサイズが大きな場合、そのWALログを読み出して、自身に読み込ませるのには長い時間を要する。従って、分散KeyValueストアシステムが障害から復旧するまでの時間が長くなり、システムの可用性が低くなってしまうという問題点がある。
【０００９】
そのため、Bigtableアーキテクチャでは、複数のサーバのいずれかに障害が発生した場合、その複数のサーバのうち障害が発生したサーバ以外の１台のサーバが、障害が発生したサーバのWALログを読み出して複数のファイルに分割する。以降、この複数のファイルのそれぞれのことを分割WALログという。そして、複数の分割WALログのそれぞれを、相互に異なる複数のサーバのそれぞれに読み込ませることによって障害から復旧するまでの時間を短縮している。
【００１０】
しかしながら、例えば２GB(Giga Byte)程度のサイズのWALログを読み出して複数の分割WALログに分割し、その複数の分割WALログのそれぞれを相互に異なる複数のサーバのそれぞれに読み込ませたとしても、分散KeyValueストアシステムが障害から復旧するまでには１時間程度かかってしまう。
【００１１】
従って、Bigtableアーキテクチャで用いられている上記の手法は、システムの可用性が低くなってしまうという問題点を解決するのに十分な手法とはいえない。
【００１２】
本発明は、高可用性を確保した分散データストアシステムおよび障害復旧方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するために本発明の分散データストアシステムは、マスターサーバと、複数のスレーブサーバとを有し、前記マスターサーバが、複数のデータを記憶するテーブルを分割することによって前記複数のスレーブサーバのそれぞれに複数の部分テーブルを割り当て、前記複数のスレーブサーバのそれぞれが、前記割り当てられた複数の部分テーブルを、当該複数の部分テーブルのそれぞれへの更新情報を記憶するWALログを用いて管理する分散データストアシステムであって、
前記複数のスレーブサーバのそれぞれは、当該スレーブサーバが管理している複数の部分テーブルのそれぞれを複数のグループのいずれかに分類し、該複数のグループのそれぞれと、前記WALログを複数のファイルに分割することによって生成された、前記複数のグループのそれぞれに属する部分テーブルへの更新情報を記憶する複数の分割WALログのそれぞれとを対応付けるWALログ管理部を有し、
前記マスターサーバは、
前記複数のスレーブサーバのそれぞれに障害が発生したことを検知する障害検知部と、
前記障害検知部にて前記複数のスレーブサーバのいずれかに障害が発生したことが検知されると、当該障害が発生したスレーブサーバの複数の分割WALログのそれぞれを選択し、該選択された分割WALログに対応するグループに属する部分テーブルを管理させるスレーブサーバを、前記複数のスレーブサーバのうち、当該障害が発生したスレーブサーバ以外のスレーブサーバの中からリカバリ用スレーブサーバとして選択するリカバリ要求部と、を有し、
前記複数のスレーブサーバのそれぞれは、前記リカバリ要求部にて当該スレーブサーバが前記リカバリ用スレーブサーバとして選択された場合、前記選択された分割WALログを読み込むことにより、当該選択された分割WALログに対応するグループに属する部分テーブルの管理を開始するリカバリ処理部を有する。
【００１４】
また、上記目的を達成するために本発明の障害復旧方法は、マスターサーバと、複数のスレーブサーバとを有し、前記マスターサーバが、複数のデータを記憶するテーブルを分割することによって前記複数のスレーブサーバのそれぞれに複数の部分テーブルを割り当て、前記複数のスレーブサーバのそれぞれが、前記割り当てられた複数の部分テーブルを、当該複数の部分テーブルのそれぞれへの更新情報を記憶するWALログを用いて管理する分散データストアシステムにおける障害復旧方法であって、
前記複数のスレーブサーバのそれぞれが、当該スレーブサーバが管理している複数の部分テーブルのそれぞれを複数のグループのいずれかに分類し、該複数のグループのそれぞれと、前記WALログを複数のファイルに分割することによって生成された、前記複数のグループのそれぞれに属する部分テーブルへの更新情報を記憶する複数の分割WALログのそれぞれとを対応付ける処理と、
前記マスターサーバが、前記複数のスレーブサーバのいずれかに障害が発生したことを検知すると、当該障害が発生したスレーブサーバの複数の分割WALログのそれぞれを選択する処理と、
前記マスターサーバが、前記選択された分割WALログに対応するグループに属する部分テーブルを管理させるスレーブサーバを、前記複数のスレーブサーバのうち、当該障害が発生したスレーブサーバ以外のスレーブサーバの中からリカバリ用スレーブサーバとして選択する選択処理と、
前記複数のスレーブサーバのそれぞれが、当該スレーブサーバが前記リカバリ用スレーブサーバとして選択された場合、前記選択された分割WALログを読み込むことにより、当該選択された分割WALログに対応するグループに属する部分テーブルの管理を開始する処理と、を有する。
【発明の効果】
【００１５】
本発明は以上説明したように構成されているので、複数のスレーブサーバのそれぞれに障害が発生した場合に、その障害が発生したスレーブサーバのWALログを読み込んで分割する必要がない。
【００１６】
従って、分散データストアシステムにおいて高可用性を確保することが可能となる。
【図面の簡単な説明】
【００１７】
【図１】Bigtableのアーキテクチャの構成を説明するための図である。
【図２】Bigtableのアーキテクチャにおける部分テーブルの管理方法を説明するための図である。
【図３】Bigtableのアーキテクチャにおけるリカバリ処理の概要を説明するための図である。
【図４】本発明の分散データストアシステムを適用した分散KeyValueストアシステムの実施の一形態の構成を示すブロック図である。
【図５】図４に示した分散KeyValueストアシステムを構成するサーバの一構成例を示すブロック図であり、（ａ）はマスターサーバの一構成例を示すブロック図、（ｂ）はスレーブサーバの一構成例を示すブロック図である。
【図６】図５（ｂ）に示したWALログ管理部によって複数のグループに分類されたAreaの一例を説明するための図である。
【図７】図４〜図６に示した分散KeyValueストアシステムにおけるリカバリ処理の概要を説明するための図である。
【図８】図５（ｂ）に示したリカバリ処理部によるリカバリ処理の実行後に複数のスレーブサーバのそれぞれが管理するAreaの一例を示す図である。
【図９】図４〜図８に示した分散KeyValueストアシステムにおいて複数のスレーブサーバのそれぞれが起動したときの動作を説明するためのフローチャートである。
【図１０】図４〜図８に示した分散KeyValueストアシステムにおいて複数のスレーブサーバのそれぞれに障害が発生したのを検知する動作を説明するためのフローチャートである。
【図１１】図４〜図８に示した分散KeyValueストアシステムにおいてリカバリ処理を行うときの動作を説明するためのフローチャートであり、（ａ）はマスターサーバの動作を説明するためのフローチャート、（ｂ）は複数のスレーブサーバのそれぞれの動作を説明するためのフローチャートである。
【図１２】図４〜図８に示した分散KeyValueストアシステムにおいて管理するAreaの数を複数のスレーブサーバ間で均一化するときのマスターサーバの動作を説明するためのフローチャートである。
【図１３】図４〜図８に示した分散KeyValueストアシステムにおいて管理するＡｒｅａの数を複数のスレーブサーバ間で均一化するときの複数のスレーブサーバのそれぞれの動作を説明するためのフローチャートであり、（ａ）はアンロード要求を受信したスレーブサーバの動作を説明するためのフローチャート、（ｂ）はロード要求を受信したスレーブサーバの動作を説明するためのフローチャートである。
【発明を実施するための形態】
【００１８】
以下に、本発明の実施の形態について図面を参照して説明するが、その前に、上述したBigtableのアーキテクチャについてさらに詳細に説明する。
【００１９】
図１は、Bigtableのアーキテクチャの構成を説明するための図である。
【００２０】
Bigtableのアーキテクチャは、１つのマスターサーバと、複数のスレーブサーバとから構成される。
【００２１】
図１に示すデーブルＡには、KeyとValueとのペアからなるデータが複数記憶されている。図１では、１つのデータを（Key0,value0）のように表している。なお、テーブルＡは、Keyによってソートされているため、Keyの範囲によって分割することが可能である。
【００２２】
図１は、テーブルＡを分割することにより、複数のスレーブサーバのそれぞれに複数の部分テーブルが割り当てられている状態を示している。
【００２３】
図１に示す例において例えばスレーブサーバＡには、Key0からKey99までの部分テーブルと、Key300からKey399までの部分テーブルとが割り当てられている。複数の部分テーブルのそれぞれを複数のスレーブサーバのうちのどのスレーブサーバに割り当てるかは、マスターサーバによって決定される。
【００２４】
なお、図１では、１００エントリ毎にテーブルＡを分割した場合を一例として示しているが、エントリ数ではなくデータサイズによってテーブルＡを分割することも可能である。
【００２５】
図２は、Bigtableのアーキテクチャにおける部分テーブルの管理方法を説明するための図である。
【００２６】
スレーブサーバＡは、割り当てられた複数の部分テーブルのそれぞれを複数のAreaのそれぞれとして管理している。すなわち、スレーブサーバＡは、複数のAreaのそれぞれを管理している。
【００２７】
複数のAreaのそれぞれは、スレーブサーバＡのメモリ上のバッファ（以降、メモリ上バッファという）と、分散ファイルシステム上のファイルである複数のソート済みKeyValueファイルとからなる。なお、以降、ソート済みKeyValueファイルのことをKVファイルという。
【００２８】
ここでは、スレーブサーバＡは、Area１およびArea２への更新情報を記憶するWALログを用いて、Area１およびArea２を管理しているものとする。
【００２９】
ここで、図２を参照しながら、Area１に新たなデータ(new key, new value)が追加された場合のスレーブサーバＡの動作について説明する。
【００３０】
新たなデータ(new key, new value)が追加された場合のスレーブサーバＡの動作は、以下に示す（１）−（ａ）〜（ｄ）の順番に実行される。なお、図２においてもこの（１）−（ａ）〜（１）−（ｄ）を示している。
【００３１】
（１）−（ａ）スレーブサーバＡは、(new key, new value)をWALログに書き込む。なお、WALログは、分散ファイルシステム上のファイルであり、WALログへの書き込みが成功した場合には永続性が保証される。
【００３２】
（１）−（ｂ）スレーブサーバＡは、(new key, new value)をメモリ上バッファに書き込む。なお、スレーブサーバＡに対して、ユーザから検索要求がされた場合には、メモリ上バッファとKVファイルとを読み込み、検索結果をユーザへ返却する。
【００３３】
（１）−（ｃ）メモリ上バッファのサイズが大きくなった場合(例えば、予め決められた閾値よりも大きな場合)、KVファイルとして分散ファイルシステム上へ書き出しを行う。
【００３４】
上記の（１）−（ｃ）の分散ファイルシステム上への書き出しは、メモリ上バッファのデータを永続化することを目的として実行されるものである。そのため、KVファイルとしての書き出しが成功した時点で、メモリ上バッファのデータは必要なくなる。そのため、スレーブサーバＡは、メモリ上バッファをクリアする。なお、メモリ上バッファのサイズが大きくない場合(例えば、予め決められた閾値以下である場合)、上記の（１）−（ｃ）の動作は実行されない。
【００３５】
次に、Bigtableのアーキテクチャを構成するスレーブサーバに障害が発生した場合の動作について説明する。
【００３６】
Bigtableのアーキテクチャを構成するスレーブサーバに障害が発生した場合、複数のスレーブサーバのうち、障害が発生したスレーブサーバ以外のスレーブサーバは、マスターサーバの指示に従い、障害が発生したスレーブサーバが管理しているAreaを管理することになる。以降、この処理のことをリカバリ処理という。
【００３７】
図３は、Bigtableのアーキテクチャにおけるリカバリ処理の概要を説明するための図である。ここでは、スレーブサーバＡに障害が発生した場合について説明する。
【００３８】
Bigtableアーキテクチャにおいてリカバリ処理は、以下に示す（２）−（ａ）〜（ｆ）の順番に実行される。なお、図３においてもこの（２）−（ａ）〜（ｆ）を示している。
【００３９】
（２）−（ａ）マスターサーバは、スレーブサーバＡに障害が発生したことを検知する。なお、ここでは、スレーブサーバＡは、Area１〜６を管理しているものとする。そのため、WALログには、Area１〜６への更新情報が記憶されている。
【００４０】
（２）−（ｂ）マスターサーバは、リカバリ処理を行う単位にWALログを分割するための分割指示を例えばスレーブサーバＢに対して行う。
【００４１】
（２）−（ｃ）スレーブサーバＢは、マスターサーバからの分割指示に従い、スレーブサーバＡのWALログを読み込み、そのWALログを例えば３つに分割した分割WALログ１〜３を分散ファイルシステム上に生成する。なお、ここでは、分割WALログ１はArea１およびArea４に対応し、WALログ２はArea２およびArea６に対応し、WALログ３はArea３およびArea５に対応しているものとする。
【００４２】
（２）−（ｄ）スレーブサーバＢは、WALログの分割が完了すると、マスターサーバへ分割完了通知を送信する。
【００４３】
（２）−（ｅ）スレーブサーバＢから送信された分割完了通知を受信したマスターサーバは、リカバリ処理を行うスレーブサーバを選択し（ここでは、スレーブサーバＣ〜Ｅが選択されたものとする)、スレーブサーバＣ〜Ｅのそれぞれにリカバリ要求を送信する。
【００４４】
（２）−（ｆ）マスターサーバから送信されたリカバリ要求を受信したスレーブサーバＣ〜Ｅのそれぞれは、分割WALログ１〜３のそれぞれを読み込むことにより、Area１〜６のそれぞれの管理を開始する。ここでは、スレーブサーバＣが分割WALログ１を読み込むことによってArea１およびArea４の管理を開始し、スレーブサーバＤが分割WALログ２を読み込むことによってArea２およびArea６の管理を開始し、スレーブサーバＥが分割WALログ３を読み込むことによってArea３およびArea５の管理を開始するものとする。
【００４５】
ここで、スレーブサーバＡのWALログのサイズを例えば２GB程度とした場合、上記（２）−（ａ）〜（ｆ）が完了するまでに、上述したように１時間程度要することとなる。
【００４６】
ここで、WALログの上限サイズを小さくすることによってリカバリ処理に要する時間を短くすることも考えられる。WALログの上限サイズを小さくした場合、WALログの削除を頻繁に行う必要がある。WALログの削除を行うときには、メモリ上バッファをKVファイルとして分散ファイルシステム上へ書き出す必要がある。
【００４７】
この場合、分散ファイルシステム上への書き出しが小さな単位で大量に行われることになり、リカバリ処理にかかる時間を短縮することができたとしても、検索や更新のトータルスループットが低下することが知られている。これは、分散ファイルシステムがサイズの小さなデータの書き込みや読み出しには向いていないためである。
【００４８】
次に、本発明の実施の形態について説明する。
【００４９】
図４は、本発明の分散データストアシステムを適用した分散KeyValueストアシステムの実施の一形態の構成を示すブロック図である。なお、本実施形態では、上述したBigtableのアーキテクチャに基づいて説明するが、Bigtableのアーキテクチャにおいて既に提供されている機能の説明は原則として省略し、本発明の特徴となる機能について主に説明する。
【００５０】
本実施形態の分散KeyValueストアシステムは図４に示すように、マスターサーバ１０と、マスターサーバと例えばネットワークスイッチによって接続されたスレーブサーバ２０−１〜２０−ｎとを備えている。
【００５１】
本実施形態においてスレーブサーバ２０−１〜２０−ｎのそれぞれは、そのスレーブサーバに割り当てられた複数のArea（部分テーブル）を、ユーザ等によって予め決められた数の複数の分割WALログを用いて管理する。
【００５２】
図５は、図４に示した分散KeyValueストアシステムを構成するサーバの一構成例を示すブロック図であり、（ａ）はマスターサーバ１０の一構成例を示すブロック図、（ｂ）はスレーブサーバ２０−１の一構成例を示すブロック図である。なお、スレーブサーバ２０−２〜２０−ｎも、スレーブサーバ２０−１と同様の構成である。
【００５３】
マスターサーバ１０は図５（ａ）に示すように、スレーブサーバ管理部１１と、障害検知部１２と、リカバリ要求部１３と、リバランス部１４とを備えている。
【００５４】
スレーブサーバ管理部１１は、スレーブサーバ２０−１〜２０−ｎのそれぞれに関する情報を記憶するスレーブサーバ管理リストを備えている。スレーブサーバ管理部１１は、マスターサーバ１０が起動されると、スレーブサーバ管理リストを初期化する。そして、スレーブサーバ管理部１１は、スレーブサーバ２０−１〜２０−ｎのそれぞれから送信された接続要求を受信する。接続要求には、スレーブサーバ２０−１〜２０−ｎのそれぞれを識別するスレーブサーバ識別情報と、そのスレーブサーバのロケーション情報とが含まれている。なお、ロケーション情報は例えば、IP(Internet Protocol)アドレスである。そして、スレーブサーバ管理部１１は、受信した接続要求に含まれるスレーブサーバ識別情報と、ロケーション情報とを対応付けてスレーブサーバ管理リストに記憶させる。また、スレーブサーバ管理部１１は、受信した接続要求の送信元のスレーブサーバに管理させる複数のAreaのそれぞれの最初のkey（Startkey）および最後のkey（Endkey）を含む接続応答をそのスレーブサーバへ送信する。そして、スレーブサーバ管理部１１は、受信した接続要求の送信元のスレーブサーバに管理させる複数のAreaの数を示す管理数情報を、そのスレーブサーバを識別するスレーブサーバ識別情報と対応付けてスレーブサーバ管理リストに記憶させる。
【００５５】
障害検知部１２は、第１の所定時間を計測するための第１のタイマー（不図示）を備えている。障害検知部１２は、第１のタイマーの経過時間が第１の所定時間を超える度に、スレーブサーバ管理リストに記憶されたスレーブサーバ識別情報にて識別されるスレーブサーバへ状態確認要求を送信する。状態確認要求は、スレーブサーバの稼働状態を確認するためのコマンドである。その後、障害検知部１２は、状態確認要求の送信先から送信された状態応答を受信する。そして、障害検知部１２は、受信した状態応答が異常を示している場合、受信した状態応答の送信元のスレーブサーバを識別するスレーブサーバ識別情報に対応するロケーション情報を、スレーブサーバ管理リストから取得する。そして、障害検知部１２は、取得したロケーション情報をリカバリ要求部１３へ出力する。なお、上述した状態確認要求や状態応答確認の処理は、「M. Burrows, “The Chubby Lock Service for Loosely-Coupled Distributed Systems,”OSDI(2006).」に記載されている分散ロックファイルシステムの死活監視機能を利用して行ってもよい。
【００５６】
リカバリ要求部１３は、障害検知部１２から出力されたロケーション情報を受け付ける。次に、リカバリ要求部１３は、予め決められた数の複数の分割WALログのそれぞれを識別する複数の分割WALログ番号のうちのいずれか１つを選択する。例えば、予め決められた数が３である場合、複数の分割WALログのそれぞれは例えば、分割WALログ１、分割WALログ２、分割WALログ３のように識別される。次に、リカバリ要求部１３は、スレーブサーバ管理リストに記憶されたスレーブサーバ識別情報のうち、受け付けたロケーション情報に対応するスレーブサーバ識別情報以外のスレーブサーバ識別情報の中から、対応する管理数情報が示す数が最も少ないスレーブサーバ識別情報を選択する。すなわち、リカバリ要求部１３は、管理しているAreaの数が最も少ないスレーブサーバをリカバリ用スレーブサーバとして選択する。次に、リカバリ要求部１３は、選択した分割WALログ番号と、受け付けたロケーション情報とを含むリカバリ要求を、選択したスレーブサーバ識別情報にて識別されるリカバリ用スレーブサーバへ送信する。そして、リカバリ要求部１３は、選択したスレーブサーバ識別情報に対応する管理数情報が示す数を１つ増加させることにより、スレーブサーバ管理リストを更新する。そして、リカバリ要求部１３は、複数の分割WALログ番号うち未選択の分割WALログ番号を選択し、上述した動作を繰り返し行う。なお、ここでは、リカバリ要求部１３が、対応する管理数情報が示す数が最も少ないスレーブサーバ識別情報を選択する場合について説明したが、それ以外にも、ランダムに選択したり、ラウンドロビンで選択したりしてもよい。
【００５７】
なお、リバランス部１４の構成および動作については後述する。
【００５８】
スレーブサーバ２０−１は図５（ｂ）に示すように、マスターサーバ接続部２１と、WALログ管理部２２と、リカバリ処理部２３と、ロード部２４と、アンロード部２５と、稼働状態確認部２６とを備えている。
【００５９】
スレーブサーバ２０−１〜２０−ｎのそれぞれは、マスターサーバ１０のロケーションを示すマスターサーバロケーション情報を入力として起動され、初期化される。マスターサーバロケーション情報は例えば、ＩＰアドレスや、ＩＰアドレスを記述した分散ファイルシステム上のファイルのパス、ＩＰアドレスが記述された分散ロックシステム上のファイルのパスなどである。分散ロックシステムについては、上述した「M. Burrows, “The Chubby Lock Service for Loosely-Coupled Distributed Systems,”OSDI(2006).」に記載されている。
【００６０】
マスターサーバ接続部２１は、起動の際に入力されたマスターサーバロケーション情報を用いてマスターサーバ１０へ接続要求を送信する。その後、マスターサーバ接続部２１は、マスターサーバ１０から送信された接続応答を受信する。そして、マスターサーバ接続部２１は、受信した接続応答に含まれる複数のStartkeyおよびEndkeyをWALログ管理部２２へ出力する。なお、マスターサーバ１０からは通常、スレーブサーバ２０−１が以前に管理していたAreaを再度管理するように要求される。そのため、マスターサーバ接続部２１は、自身のWALログとKVファイルのインデックス情報等を読み込む。これにより、スレーブサーバ２０−１にて複数のAreaの管理が開始される。
【００６１】
WALログ管理部２２は、マスターサーバ接続部２１から出力された複数のStartkeyおよびEndkeyを受け付ける。そして、WALログ管理部２２は、予め決められた分割WALログの数と、受け付けたStartKeyまたはEndKeyとから、受け付けたStartKeyおよびEndKeyにて示されるAreaが属するグループであるAreaGroupを決定する。つまり、WALログ管理部２２は、スレーブサーバ２０−１に割り当てられた複数のArea（部分テーブル）のそれぞれを複数のグループのいずれかに分類する。具体的には、WALログ管理部２２はまず、StartKeyまたはEndKeyのmd5やsha1などのハッシュ値を算出する。次に、WALログ管理部２２は、算出したハッシュ値を分割WALログの数で除算することで剰余を得る。そして、WALログ管理部２２は、その剰余の整数部分の値に応じ、受け付けたStartKeyおよびEndKeyにて示されるAreaが属するAreaGroupを決定する。
【００６２】
図６は、図５（ｂ）に示したWALログ管理部２２によって複数のグループに分類されたAreaの一例を説明するための図である。
【００６３】
図６に示す例において、スレーブサーバ２０−１は、Area１〜６を管理しているものとし、予め決められた分割WALログの数を３つとしている。
【００６４】
図６に示すように、スレーブサーバ２０−１においてArea１〜６のそれぞれは、Area１とArea４とがAreaGroupＡに属している。同様に、Area２とArea６とがAreaGroupＢに属し、Area３とArea５とがAreaGroupＣに属している。
【００６５】
そして、Area１およびArea４への更新情報は、例えば分割WALログ１に記憶され、Area２およびArea６への更新情報は、例えば分割WALログ２に記憶され、Area３およびArea５への更新情報は、例えば分割WALログ３に記憶される。つまり、複数のAreaGroupのそれぞれと、複数の分割WALログのそれぞれとが１対１に対応している。
【００６６】
なお、ここでは、説明を簡単にするため、AreaGroupの数を３つとしたが、実際には要求されるリカバリ処理の時間に応じてAreaGroupの数を増減することが可能である。
【００６７】
AreaGroupの数をより多くすれば、リカバリ処理に要する時間はより短くなるが、AreaGroupのサイズを大きくしすぎると分割WALログのサイズが大きくなり、同時にオープンされるファイル数が多くなる。この場合、分散ファイルシステムに負荷がかかり、結果として検索や更新のトータルスループットが向上しない。
【００６８】
AreaGroupの数は、分散ファイルシステムにおいて同時にオープンすることが可能なファイル数に応じて決定すればよい。例えば、複数の分割WALログのそれぞれのサイズを４００ＭＢとすれば、リカバリ処理の時間を１０分程度とすることができる。
【００６９】
また、本実施形態において、複数のスレーブサーバのそれぞれが１つのWALログを用いて複数のAreaを管理している場合に想定された分散ファイルシステム上への大量の書き出しは発生しない。
【００７０】
本実施形態では、WALログを複数の分割WALログに予め分割している。そのため、１つの分割WALログに対応するAreaの数は、WALログを予め分割していない場合に、そのWALログに対応するAreaの数に比べて少なくなるからである。
【００７１】
例えば、１つのスレーブサーバが、３０００個のAreaを１個のWALログを用いて管理している場合を考えてみる。この場合、その１個のWALログには、３０００個のAreaのそれぞれへの更新情報が記憶されるため、WALログの削除を行う場合には、多くのメモリ上バッファをKVファイルとして分散ファイルシステム上へ書き出す必要がある。
【００７２】
次に、１つのスレーブサーバが、３０００個のAreaを１６個の分割WALログファイルを用いて管理している場合を考えてみる。この場合、１つの分割WALログを削除する際に、メモリ上バッファをKVファイルとして分散ファイルシステム上へ書き出す対象となるAreaの数は高々２００個となる。従って、１つのスレーブサーバが１つのWALログを用いてAreaを管理している場合に比べ、１つのスレーブサーバが１６個の分割WALログを用いてAreaを管理している場合には小さなKVファイルができにくい。
【００７３】
再度、図５（ｂ）を参照すると、リカバリ処理部２３は、マスターサーバ１０から送信されたリカバリ要求を受信する。そして、リカバリ処理部２３は、受信したリカバリ要求に含まれる分割WALログ番号とロケーション情報とから、分割WALログへのファイルパスを生成する。
【００７４】
リカバリ処理部２３は、分割WALログへのファイルのパスを、例えば以下のようにして生成する。なお、以下に示すファイルのパスにおいてNは、予め決められた分割WALログの数である。
/スレーブサーバのIPアドレス/wallog/1/wal.log
...
/スレーブサーバのIPアドレス/wallog/N/wal.log
そして、リカバリ処理部２３は、生成したファイルパスを用いて分割WALログを読み込み、読み込んだ分割WALログをメモリ上へ展開する。これによりメモリ上バッファが再構築され、新たなAreaの管理が開始されることになる。すなわち、リカバリの対象となったAreaに対する検索や更新が可能となる。
【００７５】
図７は、図４〜図６に示した分散KeyValueストアシステムにおけるリカバリ処理の概要を説明するための図である。ここでは、スレーブサーバ２０−１に障害が発生した場合について説明する。
【００７６】
図４〜図６に示した分散KeyValueストアシステムにおいてリカバリ処理は、以下に示す（３）−（ａ）〜（ｃ）の順番に実行される。なお、図７においてもこの（３）−（ａ）〜（ｃ）を示している。
【００７７】
（３）−（ａ）マスターサーバ１０は、スレーブサーバ２０−１に障害が発生したことを検知する。ここでは、スレーブサーバ２０−１は、Area１〜６を管理しているものとする。そして、分割WALログ１には、Area１およびArea４への更新情報が記憶され、分割WALログ２には、Area２およびArea６への更新情報が記憶され、分割WALログ３には、Area３およびArea５への更新情報が記憶されているものとする。
【００７８】
（３）−（ｂ）マスターサーバ１０は、リカバリ処理を行うスレーブサーバを選択し（ここでは、スレーブサーバ２０−２〜２０−４が選択されたものとする)、スレーブサーバ２０−２〜２０−４のそれぞれにリカバリ要求を送信する。
【００７９】
（３）−（ｃ）マスターサーバ１０から送信されたリカバリ要求を受信したスレーブサーバ２０−２〜２０−４のそれぞれは、分割WALログ１〜３のそれぞれを読み込むことにより、Area１〜６のそれぞれの管理を開始する。ここでは、スレーブサーバ２０−２が分割WALログ１を読み込むことによってArea１およびArea４の管理を開始し、スレーブサーバ２０−３が分割WALログ２を読み込むことによってArea２およびArea６を管理を開始し、スレーブサーバ２０−４が分割WALログ３を読み込むことによってArea３およびArea５の管理を開始するものとする。
【００８０】
このように、図４〜図６に示した分散KeyValueストアシステムにおいては、スレーブサーバに障害が発生した場合に、図３を参照しながら説明した（２）−（ｂ）〜（ｄ）の処理を行う必要がない。
【００８１】
図８は、図５（ｂ）に示したリカバリ処理部２３によるリカバリ処理の実行後に複数のスレーブサーバのそれぞれが管理するAreaの一例を示す図である。なお、図８は、図７を参照しながら説明したリカバリ処理が実行された後の状態を示している。
【００８２】
図８に示すようにスレーブサーバ２０−２〜２０−４は、スレーブサーバ２０−１が管理していたArea１〜６のそれぞれを管理している。
【００８３】
一方、スレーブサーバ２０−５〜２０−ｎは、図７を参照しながら説明したリカバリ処理を実行していないため、スレーブサーバ２０−１が管理していたArea１〜６が管理対象として追加されていない。
【００８４】
つまり、リカバリ処理を実行したかどうかにより、複数のスレーブサーバ間で管理しているAreaの数が不均一になる場合がある。図８においては、管理するAreaの数の差は２であるが、実際には数百程度の差が生じることになる。
【００８５】
ここで、再度、図５（ａ）を参照すると、リバランス部１４は、第２の所定時間を計測するための第２のタイマー（不図示）を備えている。リバランス部１４は、第２のタイマーの経過時間が第２の所定時間が超える度に、スレーブサーバ管理リストに記憶された複数のスレーブサーバ識別情報のそれぞれに対応する管理数情報が示す数が、複数のスレーブサーバ識別情報間で均一化されているかどうかを判定する。すなわち、リバランス部１４は、スレーブサーバ管理リストに記憶された複数のスレーブサーバ識別情報のそれぞれにて識別される複数のスレーブサーバ間で、管理しているAreaの数が均一化されているかどうかを判定する均一化判定を実行する。
【００８６】
均一化判定のロジックとしては、例えば以下の２つが考えられる。以下の説明におけるαおよびβは、本実施形態の分散KeyValueストアシステムのユーザ等が予め決めておく。
【００８７】
・管理しているAreaの数が最大（Ｎ１個とする）のスレーブサーバと、管理しているAreaの数が最小（Ｎ２個とする）のスレーブサーバとにおいて、（Ｎ１−Ｎ２≦α）を満たす場合、リバランス部１４は、均一化されていると判定する。
【００８８】
・管理しているAreaの数が最大（Ｎ３個とする）のスレーブサーバと、管理しているAreaの数が最小（Ｎ４個とする）のスレーブサーバとにおいて、（（Ｎ３／Ｎ４）≦β）を満たす場合、リバランス部１４は、均一化されているものとする。
【００８９】
均一化判定の結果、均一化されていないと判定した場合、リバランス部１４は、対応する管理数情報が示す数が最も多いスレーブサーバ識別情報と、最も少ないスレーブサーバ識別情報とをスレーブサーバ管理リストから選択する。すなわち、リバランス部１４は、管理しているAreaの数が最も多いスレーブサーバを最多スレーブサーバとして選択し、管理しているAreaの数が最も少ないスレーブサーバを最少スレーブサーバとして選択する。そして、リバランス部１４は、対応する管理数情報が示す数が最も多いスレーブサーバ識別情報にて識別される最多スレーブサーバへアンロード要求を送信する。なお、アンロード要求は、スレーブサーバが管理しているAreaのうちのいずれかを管理対象から除外することを要求するためのコマンドである。その後、リバランス部１４は、最多スレーブサーバから送信されたアンロード完了通知を受信する。アンロード完了通知は、Areaを管理対象から除外したことを示す通知であり、管理対象から除外したAreaのKVファイルへのパスを示すパス情報を含む。そして、リバランス部１４は、対応する管理数情報が示す数が最も少ないスレーブサーバ識別情報にて識別される最少スレーブサーバへロード要求を送信する。ロード要求は、新たなAreaの管理を開始させるためのコマンドであり、受信したアンロード完了通知に含まれるパス情報を含む。その後、リバランス部１４は、最少スレーブサーバから送信されたロード完了通知を受信する。ロード完了通知は、新たなAreaの管理を開始したことを示す通知である。そして、リバランス部１４は、最少スレーブサーバを識別するスレーブサーバ識別情報に対応する管理数情報が示す数を１つ増加させ、最多スレーブサーバを識別するスレーブサーバ識別情報に対応する管理数情報が示す数を１つ減少させることにより、スレーブサーバ管理リストを更新する。
【００９０】
再度、図５（ｂ）を参照すると、ロード部２４は、マスターサーバ１０から送信されたロード要求を受信する。そして、ロード部２４は、受信したロード要求に含まれるKVファイルのパス情報から、Areaのインデックス情報等を読み込む。これにより、スレーブサーバ２０−１にて新たなAreaの管理が開始される。そして、ロード部２４は、ロード完了通知をマスターサーバ１０へ送信する。
【００９１】
アンロード部２５は、マスターサーバ１０から送信されたアンロード要求を受信する。そして、アンロード部２５は、スレーブサーバ２０−１が管理しているAreaのうちのいずれか１つを選択する。次に、アンロード部２５は、選択したAreaのメモリ上バッファをKVファイルとして分散ファイルシステム上へ書き出し、スレーブサーバ２０−１による管理対象から、選択したAreaを除外する。そして、アンロード部２５は、選択したAreaのKVファイルのパス情報を含むアンロード完了通知をマスターサーバ１０へ送信する。
【００９２】
なお、アンロード部２５が、スレーブサーバ２０−１にて管理されているAreaのうちのいずれかを選択する方法としては例えば、以下の（ｉ）および（ｉｉ）に示すような方法が挙げられる。
【００９３】
（ｉ）ランダムに１つ選択する。
【００９４】
（ｉｉ）属しているAreaの数が最も多いAreaGroupを選択し、選択したAreaGroupからランダムに１つ選択する。
【００９５】
上記の（ｉ）に示した方法は、新たなAreaが割り当てられた複数のスレーブサーバ間で管理するAreaの数が均一になることを目的としている。
【００９６】
上記の（ｉｉ）は、リカバリフローが繰り返し行われた場合に、一部のAreaGroupのみ、そのサイズが大きくなって、リカバリ処理の時間が長くなるのを回避することを目的としている。
【００９７】
稼働状態確認部２６は、マスターサーバ１０から送信された状態確認要求を受信する。そして、稼働状態確認部２６は、スレーブサーバ２０−１の稼働状態を確認する。確認の結果、スレーブサーバ２０−１の稼働状態が異常である場合、例えばスレーブサーバ２０−１に障害が発生している場合、異常を示す状態応答をマスターサーバ１０へ送信する。一方、確認の結果、スレーブサーバ２０−１の稼働状態が正常である場合、正常を示す状態応答をマスターサーバ１０へ送信する。
【００９８】
以下に、上記のように構成された分散KeyValueストアシステムの動作について説明する。
【００９９】
まず、図４〜図８に示した分散KeyValueストアシステムにおいてスレーブサーバ２０−１〜２０−ｎのそれぞれが起動したときの動作について説明する。
【０１００】
図９は、図４〜図８に示した分散KeyValueストアシステムにおいてスレーブサーバ２０−１〜２０−ｎのそれぞれが起動したときの動作を説明するためのフローチャートである。なお、マスターサーバ１０は既に起動済みであるものとする。
【０１０１】
スレーブサーバ２０−１〜２０−ｎのそれぞれは、マスターサーバロケーション情報を入力として起動され（ステップＳ１）、初期化される（ステップＳ２）。
【０１０２】
次に、マスターサーバ接続部２１は、そのマスターサーバロケーション情報を用いてマスターサーバ１０へ接続要求を送信する（ステップＳ３）。
【０１０３】
スレーブサーバ管理部１１は、スレーブサーバ２０−１〜２０−ｎのそれぞれから送信された接続要求を受信する（ステップＳ４）。
【０１０４】
次に、スレーブサーバ管理部１１は、受信した接続要求に含まれるスレーブサーバ識別情報と、ロケーション情報とを対応付けてスレーブサーバ管理リストに記憶させる（ステップＳ５）。
【０１０５】
そして、スレーブサーバ管理部１１は、受信した接続要求の送信元のスレーブサーバに管理させる複数のAreaのそれぞれのStartkeyおよびEndkeyを含む接続応答を、そのスレーブサーバへ送信する（ステップＳ６）。
【０１０６】
また、スレーブサーバ管理部１１は、受信した接続要求の送信元のスレーブサーバに管理させる複数のAreaの数を示す管理数情報と、そのスレーブサーバを識別するスレーブサーバ識別情報とを対応付けてスレーブサーバ管理リストに記憶させる。
【０１０７】
マスターサーバ接続部２１は、マスターサーバ１０から送信された接続応答を受信する（ステップＳ７）。
【０１０８】
そして、マスターサーバ接続部２１は、自身のWALログとKVファイルのインデックス情報等を読み込む。これにより、Areaの管理が開始される（ステップＳ８）。
【０１０９】
次に、図４〜図８に示した分散KeyValueストアシステムにおいてスレーブサーバ２０−１〜２０−ｎのそれぞれに障害が発生したのを検知する動作について説明する。
【０１１０】
図１０は、図４〜図８に示した分散KeyValueストアシステムにおいてスレーブサーバ２０−１〜２０−ｎのそれぞれに障害が発生したのを検知する動作を説明するためのフローチャートである。
【０１１１】
障害検知部１２は、第１のタイマーをスタートさせる（ステップＳ２１）
次に、障害検知部１２は、第１のタイマーの経過時間が第１の所定時間を超えたかどうかを確認する（ステップＳ２２）。
【０１１２】
ステップＳ２２における確認の結果、第１のタイマーの経過時間が第１の所定時間を超えていない場合、ステップＳ２２の動作へ遷移する。すなわち、障害検知部１２は、第１のタイマーの経過時間が第１の所定時間を超えたかどうかの確認を継続する。
【０１１３】
一方、ステップＳ２２における確認の結果、第１のタイマーの経過時間が第１の所定時間を超えている場合、障害検知部１２は、第１のタイマーをリセットし、再スタートさせる（ステップＳ２３）。
【０１１４】
次に、障害検知部１２は、スレーブ管理リストに記憶されているスレーブサーバ識別情報のうちのいずれか１つを選択する（ステップＳ２４）。
【０１１５】
そして、障害検知部１２は、選択したスレーブサーバ識別情報にて識別されるスレーブサーバへ状態確認要求を送信する（ステップＳ２５）。
【０１１６】
稼働状態確認部２６は、マスターサーバ１０から送信された状態確認要求を受信する（ステップＳ２６）。
【０１１７】
次に、稼働状態確認部２６は、自身が備えられたスレーブサーバの稼働状態を確認する。
【０１１８】
そして、稼働状態確認部２６は、確認した稼働状態に応じた内容の状態応答をマスターサーバ１０へ送信する（ステップＳ２７）。
【０１１９】
障害検知部１２は、スレーブサーバ２０−１から送信された状態応答を受信する（ステップＳ２８）。
【０１２０】
次に、障害検知部１２は、受信した状態応答が正常を示しているかどうかを確認する（ステップＳ２９）。
【０１２１】
ステップＳ２９における確認の結果、受信した状態応答が正常を示している場合、障害検知部１２は、スレーブ管理リストに記憶されているすべてのスレーブサーバ識別情報を選択済みかどうかを確認する（ステップＳ３０）。
【０１２２】
ステップＳ３０における確認の結果、スレーブ管理リストに記憶されているすべてのスレーブサーバ識別情報を選択済みでない場合、障害検知部１２は、スレーブ管理リストに記憶されているスレーブサーバ識別情報のうち未選択のスレーブサーバ識別情報のいずれか１つを選択する（ステップＳ３１）。そして、ステップＳ２５の動作へ遷移する。
【０１２３】
一方、ステップＳ３０における確認の結果、スレーブ管理リストに記憶されているすべてのスレーブサーバ識別情報を選択済みである場合、ステップＳ２２の動作へ遷移する。
【０１２４】
ここで、ステップＳ２９における確認の結果、受信した状態応答が異常を示している場合、障害検知部１２は、選択したスレーブサーバ識別情報に対応するロケーション情報を、スレーブサーバ管理リストから取得する。
【０１２５】
次に、障害検知部１２は、取得したロケーション情報をリカバリ要求部１３へ出力する
（ステップＳ３２）。そして、ステップＳ３０の動作へ遷移する。
【０１２６】
次に、図４〜図８に示した分散KeyValueストアシステムにおいてリカバリ処理を行うときの動作について説明する。
【０１２７】
図１１は、図４〜図８に示した分散KeyValueストアシステムにおいてリカバリ処理を行うときの動作を説明するためのフローチャートであり、（ａ）はマスターサーバ１０の動作を説明するためのフローチャート、（ｂ）はスレーブサーバ２０−１〜２０−ｎのそれぞれの動作を説明するためのフローチャートである。
【０１２８】
まず、図１１（ａ）を参照しながら、マスターサーバ１０の動作について説明する。
【０１２９】
リカバリ要求部１３は、障害検知部１２から出力されたロケーション情報を受け付けたかどうかを確認する（ステップＳ４１）。
【０１３０】
ステップＳ４１における確認の結果、障害検知部１２から出力されたロケーション情報を受け付けていない場合、ステップＳ４１の動作へ遷移する。すなわち、リカバリ要求部１３は、障害検知部１２から出力されたロケーション情報を受け付けたかどうかの確認を継続する。
【０１３１】
一方、ステップＳ４１における確認の結果、障害検知部１２から出力されたロケーション情報を受け付けた場合、リカバリ要求部１３は、予め決められた数の複数の分割WALログのそれぞれを識別する複数の分割WALログ番号のうちのいずれか１つを選択する。（ステップＳ４２）。
【０１３２】
次に、リカバリ要求部１３は、スレーブサーバ管理リストに記憶されたスレーブサーバ識別情報のうち、受け付けたロケーション情報に対応するスレーブサーバ識別情報以外のスレーブサーバ識別情報の中から、対応する管理数情報が示す数が最も少ないスレーブサーバ識別情報を選択する（ステップＳ４３）。
【０１３３】
次に、リカバリ要求部１３は、選択した分割WALログ番号と、受け付けたロケーション情報とを含むリカバリ要求を、選択したスレーブサーバ識別情報にて識別されるリカバリ用スレーブサーバへ送信する（ステップＳ４４）。
【０１３４】
次に、リカバリ要求部１３は、選択したスレーブサーバ識別情報に対応する管理数情報が示す数を１つ増加させることにより、スレーブサーバ管理リストを更新する（ステップＳ４５）。
【０１３５】
次に、リカバリ要求部１３は、予め決められた数の複数の分割WALログのそれぞれを識別する複数の分割WALログ番号のすべてを選択済みかどうかを確認する（ステップＳ４６）。
【０１３６】
ステップＳ４６における確認の結果、予め決められた数の複数の分割WALログのそれぞれを識別する複数の分割WALログ番号のすべてを選択済みである場合、ステップＳ４１の動作へ遷移する。
【０１３７】
一方、ステップＳ４６における確認の結果、予め決められた数の複数の分割WALログのそれぞれを識別する複数の分割WALログ番号のすべてを選択済みでない場合、リカバリ要求部１３は、複数の分割WALログ番号のうち未選択の分割WALログ番号を選択する（ステップＳ４７）。そして、ステップＳ４３の動作へ遷移する。
【０１３８】
次に、図１１（ｂ）を参照しながら、スレーブサーバ２０−１〜２０−ｎのそれぞれの動作について説明する。
【０１３９】
リカバリ処理部２３は、マスターサーバ１０から送信されたリカバリ要求を受信したかどうかを確認する（ステップＳ６１）。
【０１４０】
ステップＳ６１における確認の結果、マスターサーバ１０から送信されたリカバリ要求を受信していない場合、ステップＳ６１の動作へ遷移する。すなわち、リカバリ処理部２３は、マスターサーバ１０から送信されたリカバリ要求を受信したかどうかの確認を継続する。
【０１４１】
一方、ステップＳ６１における確認の結果、マスターサーバ１０から送信されたリカバリ要求を受信した場合、リカバリ処理部２３は、受信したリカバリ要求に含まれる分割WALログ番号とロケーション情報とから、分割WALログへのファイルパスを生成する（ステップＳ６２）。
【０１４２】
次に、リカバリ処理部２３は、生成したファイルバスを用いて分割WALログを読み込む（ステップＳ６３）。
【０１４３】
次に、リカバリ処理部２３は、読み込んだ分割WALログをメモリ上に展開する（ステップＳ６４）。これにより、新たなAreaの管理が開始されることになる。そして、ステップＳ６１の動作へ遷移する。
【０１４４】
次に、図４〜図８に示した分散KeyValueストアシステムにおいて管理するAreaの数を複数のスレーブサーバ間で均一化するときの動作について説明する。
【０１４５】
図１２は、図４〜図８に示した分散KeyValueストアシステムにおいて管理するAreaの数を複数のスレーブサーバ間で均一化するときのマスターサーバ１０の動作を説明するためのフローチャートである。
【０１４６】
また、図１３は、図４〜図８に示した分散KeyValueストアシステムにおいて管理するAreaの数を複数のスレーブサーバ間で均一化するときのスレーブサーバ２０−１〜２０−ｎのそれぞれの動作を説明するためのフローチャートであり、（ａ）はアンロード要求を受信したスレーブサーバの動作を説明するためのフローチャート、（ｂ）はロード要求を受信したスレーブサーバの動作を説明するためのフローチャートである。
【０１４７】
まず、図１２を参照しながら、分散KeyValueストアシステムにおいて管理するAreaの数を複数のスレーブサーバ間で均一化するときのマスターサーバ１０の動作について説明する。
【０１４８】
リバランス部１４は、第２のタイマーをスタートさせる（ステップＳ８１）。
【０１４９】
次に、リバランス部１４は、第２のタイマーの経過時間が第２の所定時間を超えたかどうかを確認する（ステップＳ８２）。
【０１５０】
ステップＳ８２における確認の結果、第２のタイマーの経過時間が第２の所定時間を超えていない場合、ステップＳ８２の動作へ遷移する。すなわち、リバランス部１４は、第２のタイマーの経過時間が第２の所定時間を超えたかどうかの確認を継続する。
【０１５１】
一方、ステップＳ８２における確認の結果、第２のタイマーの経過時間が第２の所定時間を超えている場合、リバランス部１４は、第２のタイマーをリセットし、再スタートさせる（ステップＳ８３）。
【０１５２】
次に、リバランス部１４は、スレーブサーバ管理リストに記憶された複数のスレーブサーバ識別情報のそれぞれに対応する管理数情報が示す数が、複数のスレーブサーバ識別情報間で均一化されているかどうかを判定する（ステップＳ８４）。
【０１５３】
ステップＳ８４における判定の結果、均一化されていると判定された場合、ステップＳ８２の動作へ遷移する。
【０１５４】
一方、ステップＳ８４における判定の結果、均一化されていないと判定された場合、リバランス部１４は、対応する管理数情報が示す数が最も多いスレーブサーバ識別情報と、最も少ないスレーブサーバ識別情報とをスレーブサーバ管理リストから選択する（ステップＳ８５）。
【０１５５】
次に、リバランス部１４は、対応する管理数情報が示す数が最も多いスレーブサーバ識別情報にて識別される最多スレーブサーバへアンロード要求を送信する（ステップＳ８６）。
【０１５６】
次に、リバランス部１４は、アンロード完了通知を受信したかどうかを確認する（ステップＳ８７）。
【０１５７】
ステップＳ８７における確認の結果、アンロード完了通知を受信していない場合、ステップＳ８７の動作へ遷移する。すなわち、リバランス部１４は、アンロード完了通知を受信したかどうかの確認を継続する。
【０１５８】
一方、ステップＳ８７における確認の結果、アンロード完了通知を受信した場合、リバランス部１４は、対応する管理数情報が示す数が最も少ないスレーブサーバ識別情報にて識別される最少スレーブサーバへロード要求を送信する（ステップＳ８８）。
【０１５９】
次に、リバランス部１４は、ロード完了通知を受信したかどうかを確認する（ステップＳ８９）。
【０１６０】
ステップＳ８９における確認の結果、ロード完了通知を受信していない場合、ステップＳ８９の動作へ遷移する。すなわち、リバランス部１４は、ロード完了通知を受信したかどうかの確認を継続する。
【０１６１】
一方、ステップＳ８９における確認の結果、ロード完了通知を受信した場合、最少スレーブサーバを識別するスレーブサーバ識別情報に対応する管理数情報が示す数を１つ増加させ、最多スレーブサーバを識別するスレーブサーバ識別情報に対応する管理数情報が示す数を１つ減少させることにより、スレーブサーバ管理リストを更新する。（ステップＳ９０）。そして、ステップＳ８２の動作へ遷移する。
【０１６２】
次に、図１３（ａ）を参照しながら、アンロード要求を受信したスレーブサーバの動作について説明する。
【０１６３】
アンロード部２５は、マスターサーバ１０から送信されたアンロード要求を受信したかどうかを確認する（ステップＳ１０１）。
【０１６４】
ステップＳ１０１における確認の結果、マスターサーバ１０から送信されたアンロード要求を受信していない場合、ステップＳ１０１の動作へ遷移する。すなわち、アンロード部２５は、マスターサーバ１０から送信されたアンロード要求を受信したかどうかの確認を継続する。
【０１６５】
一方、ステップＳ１０１における確認の結果、マスターサーバ１０から送信されたアンロード要求を受信した場合、アンロード部２５は、当該スレーブサーバにて管理しているAreaのうちのいずれかを選択する（ステップＳ１０２）。
【０１６６】
次に、アンロード部２５は、選択したAreaのメモリ上バッファを分散ファイルシステム上へKVファイルとして書き出す（ステップＳ１０３）。
【０１６７】
そして、アンロード部２５は、選択したAreaのKVファイルのパス情報を含むアンロード完了通知をマスターサーバ１０へ送信する（ステップＳ１０４）。そして、ステップＳ１０１の動作へ遷移する。
【０１６８】
次に、図１３（ｂ）を参照しながら、ロード要求を受信したスレーブサーバの動作について説明する。
【０１６９】
ロード部２４は、マスターサーバ１０から送信されたロード要求を受信したかどうかを確認する（ステップＳ１２１）。
【０１７０】
ステップＳ１２１における確認の結果、マスターサーバ１０から送信されたロード要求を受信していない場合、ステップＳ１２１の動作へ遷移する。すなわち、ロード部２４は、マスターサーバ１０から送信されたロード要求を受信したかどうかの確認を継続する。
【０１７１】
一方、ステップＳ１２１における確認の結果、マスターサーバ１０から送信されたロード要求を受信した場合、ロード部２４は、受信したロード要求に含まれるKVファイルのパス情報から、Areaのインデックス情報等を読み込む（ステップＳ１２２）。これにより、新たなAreaの管理が開始される。
【０１７２】
次に、ロード部２４は、ロード完了通知をマスターサーバ１０へ送信する（ステップＳ１２３）。そして、ステップＳ１２１の動作へ遷移する。
【０１７３】
このように本実施形態において、スレーブサーバ２０−１〜２０−ｎのそれぞれは、当該スレーブサーバが管理している複数の部分テーブルのそれぞれを複数のグループのいずれかに分類し、複数のグループのそれぞれと、WALログを複数のファイルに分割することによって生成された、複数のグループのそれぞれに属する部分テーブルへの更新情報を記憶する複数の分割WALログのそれぞれとを対応付けるWALログ管理部２２を有する。
【０１７４】
また、マスターサーバ１０は、複数のスレーブサーバのそれぞれに障害が発生したことを検知する障害検知部１２を有する。また、マスターサーバ１０は、障害検知部１２にて複数のスレーブサーバのいずれかに障害が発生したことが検知されると、当該障害が発生したスレーブサーバの複数の分割WALログのそれぞれを選択し、選択された分割WALログに対応するグループに属する部分テーブルを管理させるスレーブサーバを、複数のスレーブサーバのうち、当該障害が発生したスレーブサーバ以外のスレーブサーバの中からリカバリ用スレーブサーバとして選択するリカバリ要求部１３を有する。
【０１７５】
そして、スレーブサーバ２０−１〜２０−ｎのそれぞれは、リカバリ要求部１３にて当該スレーブサーバがリカバリ用スレーブサーバとして選択された場合、選択された分割WALログを読み込むことにより、当該選択された分割WALログに対応するグループに属する部分テーブルの管理を開始するリカバリ処理部２３を有する。
【０１７６】
これにより、複数のスレーブサーバのそれぞれに障害が発生した場合に、その障害が発生したスレーブサーバのWALログを読み込んで分割する必要がない。
【０１７７】
従って、分散データストアシステムにおいて高可用性を確保することが可能となる。
【０１７８】
また、本実施形態において、マスターサーバ１０は、複数のスレーブサーバのそれぞれが管理している複数の部分テーブルの数が、当該複数のスレーブサーバ間で均一化されているかどうかを判定する均一化判定を実行するリバランス部１４を有する。
【０１７９】
リバランス部１４は、均一化判定において均一化されていないと判定した場合、複数のスレーブサーバの中から、管理している部分テーブルの数が最多のスレーブサーバを最多スレーブサーバとして選択するとともに、管理している部分テーブルの数が最少のスレーブサーバを最少スレーブサーバとして選択する。
【０１８０】
そして、スレーブサーバ２０−１〜２０−ｎのそれぞれは、リバランス部１４にて当該スレーブサーバが最多スレーブサーバとして選択された場合、当該スレーブサーバにて管理している複数の部分テーブルのうちのいずれかを選択し、選択した部分テーブルを管理対象から除外するアンロード部２５を有する。
【０１８１】
また、スレーブサーバ２０−１〜２０−ｎのそれぞれは、リバランス部１４にて当該スレーブサーバが最少スレーブサーバとして選択された場合、上記の管理対象から除外された部分テーブルを、当該スレーブサーバが管理する部分テーブルとするロード部２４を有する。
【０１８２】
これにより、スレーブサーバ２０−１〜２０−ｎのそれぞれか管理する複数の部分テーブルの数が均一化される。
【０１８３】
従って、検索や更新などのオペレーションに対するスケーラビリティが向上する。また、分散KeyValueストアシステムにおける負荷分散が実現できるとともに、検索や更新などのオペレーションの際に特定のスレーブサーバがボトルネックとなるのを回避することができる。
【符号の説明】
【０１８４】
１０    マスターサーバ
１１    スレーブサーバ管理部
１２    障害検知部
１３    リカバリ要求部
１４    リバランス部
２０−１〜２０−ｎ    スレーブサーバ
２１    マスターサーバ接続部
２２    WALログ管理部
２３    リカバリ処理部
２４    ロード部
２５    アンロード部
２６    稼働状態確認部
【図１】
0005405530.tif 000002
【図２】
0005405530.tif 000003
【図３】
0005405530.tif 000004
【図４】
0005405530.tif 000005
【図５】
0005405530.tif 000006
【図６】
0005405530.tif 000007
【図７】
0005405530.tif 000008
【図８】
0005405530.tif 000009
【図９】
0005405530.tif 000010
【図１０】
0005405530.tif 000011
【図１１】
0005405530.tif 000012
【図１２】
0005405530.tif 000013
【図１３】
0005405530.tif 000014