JPWO2015029139A1 - データベースシステム、プログラムおよびデータ処理方法 - Google Patents

Abstract

データベースシステムは、データベースを記憶する複数のノードを備える。複数のノードは、互いに通信をして何れか１つのノードを管理装置として選任する。管理装置は、第１割当部と第２割当部とを有する。第１割当部は、複数のノードのそれぞれの状況の変更に応じて、データ集合を記憶してデータ集合へのアクセス要求を受け付ける第１ノード、および、データ集合を記憶して第１ノードのバックアップとなる第２ノードを割り当てて、複数のノードのそれぞれに割り当てに応じた動作を指示する。第２割当部は、複数のノードの状況と、第１ノードおよび第２ノードの割り当て状況の変更に応じて、第１ノードまたは第２ノードの候補となる第３ノードを割り当てて、複数のノードのそれぞれに対して、第３ノードに第１ノードまたは第２ノードとして動作させるための準備を指示する。

Description

本発明の実施形態は、データベースシステム、プログラムおよびデータ処理方法に関する。

（シェアードナッシング型データベース）
従来より、シェアードナッシング型のデータベースシステムが知られている。シェアードナッシング型のデータベースシステムは、互いがネットワークで接続された複数のデータベースノードを備える。

複数のデータベースノードのそれぞれは、プロセッサ、メモリおよびストレージ等のリソースを個別に有するコンピュータである。シェアードナッシング型のデータベースシステムは、データベースノード毎にリソースが完全に分離されているので、データベースノード間でアクセス競合が発生しない。従って、シェアードナッシング型のデータベースシステムは、データベースノードを増やすことにより性能を線形に向上させることができる。すなわち、シェアードナッシング型のデータベースシステムは、データベースノードを追加するスケールアウトが効率良く実現できるシステムである。

（パーティショニング）
シェアードナッシング型のデータベースシステムでは、パーティショニングと呼ばれる技術を適用できる。パーティショニングは、データベースを複数に分割し、分割したそれぞれのデータ集合（パーティションと呼ばれる。）を複数のデータベースノードに分散して記憶させる技術である。パーティショニングを適用したシェアードナッシング型のデータベースシステムは、それぞれのデータベースノードに記憶させるデータ集合を小さくできるので、クライアントからのアクセスを複数のデータベースノードに分散させることができる。

（シャーディング）
データベース技術の一つに、シャーディングと呼ばれる技術がある。シャーディングは、データをより小さなデータに分割し、複数のデータベースノードに自動的に分散して保存する技術である。シャーディングは、シェアードナッシング型のデータベースシステムのパーティショニングと類似した技術である。

（分散キーバリュー型データベース）
また、キーバリュー型データベースが知られている。キーバリュー型データベースは、プログラミング言語の連想配列またはＭａｐと同様にキーとバリューとのペアからなる単純なデータモデルに基づくデータベースである。また、キーバリュー型データベースをキーによりシャーディングすることで分散化した分散キーバリュー型データベースも知られている。

キーバリュー型データベースは、データモデルが単純であるので、シャーディングおよびパーティショニングの処理が容易である。また、分散キーバリュー型データベースは、複数のキーバリュー型データベースノードを使って、単一のキーバリュー型データベースノードでは対応できないような大規模なデータ集合を処理することができる。従って、分散キーバリュー型データベースを、複数のデータベースノードを備えるシェアードナッシング型のデータベースシステムに適用することにより、スケールアウトが可能な大規模なデータベースシステムを実現することができる。

さらに、このような分散キーバリュー型データベースを適用したシェアードナッシング型のデータベースシステム（以下、スケールアウト型データベースシステムと呼ぶ）は、複数のデータベースノードに均等にデータを配置することにより、クライアントからのアクセスを分散させて、全体としてスループットおよびレスポンスを向上させることができる。

特開２００９−１５７７８５号公報 特開２００５−１９６６０２号公報

"MongoDB Manual Contents"、[Online]、１０ｇｅｎ、[平成２５年１月１８日検索]、インターネット<URL:http://docs.mongodb.org/manual/contents/>

ところで、スケールアウト型データベースシステムでは、データの複製（レプリカ）を他のデータベースノードに記憶させるレプリケーションと呼ばれる技術が適用される。スケールアウト型データベースシステムは、レプリケーションを行うことで、あるデータベースノードに障害が生じたとしても、レプリカを記憶したデータベースノードを用いてサービスを継続することができる。データのレプリカを記憶するデータベースノードの個数を冗長度と呼ぶ。スケールアウト型データベースシステムでは、例えば冗長度として２個または３個が設定される。

ここで、スケールアウト型データベースシステムは、データベースノードに障害が発生し、障害が発生したデータベースノードを切り離すと、予め設定した値よりも冗長度が低下する。スケールアウト型データベースシステムは、冗長度が低下したまま長時間を稼動し続けると、更なるデータベースノードの障害が発生したときにシステム全体の動作停止または広範囲のデータ損失が発生する可能性が高くなる。このため、スケールアウト型データベースシステムでは、データベースノードに障害が発生した後に、新たなデーベースノードを追加し、追加されたデータベースノードにレプリカを記憶させて冗長度を元に戻す仕組みが必要である。

また、スケールアウト型データベースシステムでは、データの配置によっては、記憶するデータ量がデータベースノード間で不均衡となる場合がある。また、スケールアウト型データベースシステムでは、データの配置によっては、クライアントからのアクセス量がデータベースノード間で不均衡となる場合がある。

このようなデータ配置の不均衡が大きくなると、スケールアウト型データベースシステムでは、データ量の多いデータベースノードまたはクライアントからのアクセスのデータベースノードでの処理時間が相対的に長くなる。スケールアウト型データベースシステムは、クライアントからのアクセスを分散させることがメリットの一つであるので、このようなデータ配置の不均衡によりメリットが失われてしまう。

以上のような冗長度の低下およびデータ配置の不均衡を解決するために、スケールアウト型データベースシステムは、データ配置に不均衡が生じた時点で複数のデータベースノードへのデータの再配置処理をしなければならない。

しかしながら、従来のデータベースシステムでは、このような再配置処理を、サービスを停止した状態で実施しなければならなかった。また、従来のデータベースシステムでは、データの再配置処理の負荷が非常に高いので、効率良く処理を実行しなければ著しく処理効率を悪化させてしまっていた。また、データベースシステムは、このような再配置処理を実行するために、管理装置として機能するノードを適切に選出しなければならない。

実施形態に係るデータベースシステムは、データベースを記憶する複数のノードを備える。前記複数のノードは、互いに通信をして何れか１つのノードを管理装置として選任する。前記管理装置は、第１割当部と、第２割当部と、を有する。前記第１割当部は、前記複数のノードのそれぞれの状況の変更に応じて、データ集合を記憶して前記データ集合へのアクセス要求を受け付ける第１ノード、および、前記データ集合を記憶して前記第１ノードのバックアップとなる第２ノードを割り当てて、前記複数のノードのそれぞれに割り当てに応じた動作を指示する。前記第２割当部は、前記複数のノードの状況と、前記第１ノードおよび前記第２ノードの割り当て状況の変更に応じて、前記第１ノードまたは前記第２ノードの候補となる第３ノードを割り当てて、前記複数のノードのそれぞれに対して、前記第３ノードに前記第１ノードまたは前記第２ノードとして動作させるための準備を指示する。前記複数のノードのそれぞれは、前記第１ノードまたは前記第２ノードのデータ集合を、前記第３ノードに送信する転送部を有する。

図１は、実施形態に係るデータベースシステムのハードウェア構成を示す図である。 図２は、実施形態に係るデータベースシステムの機能構成を示す図である。 図３は、データ保持表の一例を示す図である。 図４は、現役割表の一例を示す図である。 図５は、次役割表の一例を示す図である。 図６は、目標役割表の一例を示す図である。 図７は、データストア部に記憶されているデータ集合の一例を示す図である。 図８は、レプリケーション処理を説明するための図である。 図９は、短期同期処理を説明するための図である。 図１０は、長期同期処理を説明するための図である。 図１１は、ノードに割り当てられる役割の遷移を示す図である。 図１２は、管理装置のクラスタ管理部の処理フローを示す図である。 図１３は、管理装置の第１割当部による次役割表の算出処理のフローを示す図である。 図１４は、管理装置の第２割当部による目標役割表の算出処理のフローを示す図である。 図１５は、ノードのアクセス処理部の処理フローを示す図である。 図１６は、ノードのノード管理部の処理フローを示す図である。 図１７は、ノードの転送部の処理フローを示す図である。 図１８は、管理装置を選任するための第１の処理フローを示す図である。 図１９は、第１の処理フローを実行する複数のノードの第１の状態を示す図である。 図２０は、第１の処理フローを実行する複数のノードの第２の状態を示す図である。 図２１は、第１の処理フローを実行する複数のノードの第３の状態を示す図である。 図２２は、第１の処理フローを実行する複数のノードの第４の状態を示す図である。 図２３は、第１の処理フローを実行する複数のノードの第５の状態を示す図である。 図２４は、第１の処理フローを実行する複数のノードの第６の状態を示す図である。 図２５は、管理装置を選任するための第２の処理フローを示す図である。 図２６は、第２の処理フローを実行する複数のノードの第１の状態を示す図である。 図２７は、第２の処理フローを実行する複数のノードの第２の状態を示す図である。 図２８は、第２の処理フローを実行する複数のノードの第３の状態を示す図である。 図２９は、第２の処理フローを実行する複数のノードの第４の状態を示す図である。 図３０は、第２の処理フローを実行する複数のノードの第５の状態を示す図である。 図３１は、３つのパーティション＃１〜＃３のそれぞれに対して、オーナーおよびバックアップとなるノードを割り当てた場合の、ノード３０−Ａからノード３０−Ｃのそれぞれの状態を示す図である。 図３２は、図３１の状態からノード３０−Ｃに障害が発生したことに応じて短期同期処理を実行した後の、ノード３０−Ａからノード３０−Ｃのそれぞれの状態を示す図である。 図３３は、図３２の状態から実行される長期同期処理の一例を示す図である。 図３４は、図３３の長期同期処理が完了したことに応じて短期同期処理を実行した後の、ノード３０−Ａからノード３０−Ｃのそれぞれの状態を示す図である。 図３５は、図３４の状態からノード３０−Ｄを追加した場合の、ノード３０−Ａからノード３０−Ｄのそれぞれの状態を示す図である。 図３６は、図３５の状態から実行される長期同期処理の一例を示す図である。 図３７は、図３６の長期同期処理が完了したことに応じて短期同期処理を実行した後の、ノード３０−Ａからノード３０−Ｄのそれぞれの状態を示す図である。

図１は、実施形態に係るデータベースシステム１０のハードウェア構成を示す図である。データベースシステム１０は、外部のコンピュータであるクライアントからデータベースに対するアクセス要求（例えば、参照、更新または登録）をネットワークを介して受信し、受信したアクセス要求に応じた処理を実行する。

データベースシステム１０は、複数のノード３０を備える。複数のノード３０は、ネットワークを介して互いに接続される。

データベースシステム１０は、一例として、分散キーバリュー型データベースをシェアードナッシング型のデータベースに適用したスケールアウトが可能なデータベースシステムである。このようなデータベースシステム１０は、複数のノード３０にデータ集合が分散されているが、外部のコンピュータであるクライアントから巨大な一つのデータベースとしてアクセスされる。

複数のノード３０のそれぞれは、互いにハードウェア的に独立したコンピュータである。複数のノード３０のそれぞれは、クライアントからのアクセス要求を独立に受け付け、アクセス要求に応じた処理を独立にすることができる。

複数のノード３０のそれぞれは、一例として、ＣＰＵ（Central Processing Unit）１２、メモリ１３、通信Ｉ／Ｆ１４およびストレージＩ／Ｆ１５を有する。また、複数のノード３０のそれぞれは、ストレージＩ／Ｆ１５を介して外部記憶装置１６に接続される。なお、外部記憶装置１６は、ノード３０の内部に設けられていてもよい。

データベースシステム１０は、データベースを複数のパーティションに分割して記憶する。パーティションの数は、予め定められている。データベースを分割する方法は、予め定められた方法であれば、どのような方法であってもよい。

複数のノード３０のそれぞれは、複数のパーティションのそれぞれ毎に、オーナーとしての役割を担うか、バックアップとしての役割を担うか、または、オーナーおよびバックアップの何れの役割も担わないかが割り当てられる。

オーナーは、対応するパーティションのデータ集合を記憶して、対応するパーティションのデータ集合へのクライアントからのアクセス要求を受け付けて処理する。また、バックアップは、対応するパーティションのデータ集合を記憶して、例えばオーナーに障害が発生したときに、代わってオーナーの役割を担えるように、オーナーをバックアップする。なお、オーナーおよびバックアップと呼ばずに、マスターおよびスレーブと呼ばれる場合もある。

また、複数のノード３０は、互いに通信をして何れか１つのノード３０を管理装置２０として選任する。選任された１つのノード３０は、管理装置２０として機能する。なお、選任されたノード３０は、通常の動作も同時に実行する。すなわち、選任されたノード３０は、クライアントからのアクセス要求を受け付けてアクセス要求に応じた処理も、同時に実行する。

複数のノード３０は、例えば、データベースの起動時に所定のアルゴリズムで１つの管理装置２０を選任する。また、複数のノード３０は、既に選任されていたノード３０が障害により管理装置２０として機能できなくなった場合に、所定のアルゴリズムで新たなノード３０を管理装置２０として選任する。管理装置２０を選任するアルゴリズムの一例については、図１８から図３０を参照して更に説明する。

なお、図面および説明において、管理装置２０を、ノード３０とは分離して図示したり説明したりする場合もあるが、管理装置２０として機能するコンピュータは、同時に何れか１つのノード３０としても機能している。

管理装置２０は、複数のノード３０を管理する。管理装置２０は、一例として、複数のパーティションのそれぞれ毎に、オーナーとするノード３０およびバックアップとするノード３０を割り当てる。

この場合において、管理装置２０は、何れかのノード３０の故障によっても可能な限りデータベースが復元されるように冗長度を予め定められた範囲で持たせるように、バックアップとするノード３０を割り当てる。さらに、管理装置２０は、データベースに含まれるデータ集合が複数のノード３０に分散して配置されるように、オーナーおよびバックアップとするノード３０を割り当てる。

このようなデータベースシステム１０は、複数のノード３０のうち何れかのノード３０に障害が発生した場合には、障害が発生したノード３０を切り離すことができる。また、データベースシステム１０は、新たにノード３０を追加して、データベースの性能を向上させることができる。

図２は、実施形態に係るデータベースシステム１０の機能構成を示す図である。

管理装置２０は、表記憶部２１と、第１割当部２２と、第２割当部２３と、クラスタ管理部２４とを有する。第１割当部２２、第２割当部２３およびクラスタ管理部２４は、管理装置２０のＣＰＵ１２がプログラムを実行することにより実現される。また、第１割当部２２、第２割当部２３およびクラスタ管理部２４は、一部または全部がハードウェア回路で実現されてもよい。また、表記憶部２１は、管理装置２０のメモリ１３または外部記憶装置１６により実現される。

表記憶部２１は、複数のパーティションのそれぞれに対する複数のノード３０のそれぞれの役割を定めるための４つの表を記憶する。４つの表のそれぞれは、テーブル形式のデータであってもよいし、テーブル形式以外のデータであってもよい。

具体的には、表記憶部２１は、データ保持表、現役割表、次役割表および目標役割表を記憶する。

データ保持表は、複数のパーティションのそれぞれに対する、複数のノード３０のそれぞれのタイムスタンプを格納する。タイムスタンプは、対応するノード３０が記憶している対応するパーティションのデータ集合の更新履歴を表す。タイムスタンプは、一例として、データ集合が更新される毎にインクリメントされる値である。従って、あるパーティションにおけるタイムスタンプの最も大きいノード３０は、そのパーティションの最新のデータ集合を記憶しているノード３０であることを意味する。

なお、データベースのサイズが時間とともに増加していく場合、データ保持表は、タイムスタンプに代えて、対応するノード３０が記憶している対応するパーティションのデータ集合のサイズまたはデータ数等を格納してもよい。

データ保持表は、一例として、図３に示されるように、行によりノード３０が特定され、列によりパーティションが特定される。この場合、データ保持表は、行および列が直交するそれぞれのセルに、その行により特定されるノード３０が記憶している、その列により特定されるパーティションのデータ集合のタイムスタンプを格納する。

現役割表は、複数のパーティションのそれぞれに対する、複数のノード３０のそれぞれに割り当てられたデータベースでの役割を格納する。具体的には、現役割表は、複数のパーティションのそれぞれに対して、複数のノード３０のそれぞれがオーナーとして割り当てられているか、バックアップとして割り当てられているか、または、オーナーとしてもバックアップとしても割り当てられていないかを格納する。

現役割表は、一例として、図４に示されるように、行によりノード３０が特定され、列によりパーティションが特定される。この場合、現役割表は、行および列が直交する位置のそれぞれのセルに、その列により特定されるパーティションに対する、その行により特定されるノード３０に割り当てられた役割を格納する。なお、図面には、オーナーとしての役割が割り当てられていることを“ＯＷＮＥＲ”または“Ｏ”と記載し、バックアップとしての役割が割り当てられていることを“ＢＡＣＫＵＰ”または“Ｂ”を記載し、オーナーにもバックアップにも割り当てられていないことを“Ｎｏｎｅ”または“Ｎ”を記載し若しくは空白とする。

次役割表は、複数のパーティションのそれぞれに対する、複数のノード３０のそれぞれに次に割り当てられる役割を格納する。すなわち、次役割表は、複数のパーティションのそれぞれに対して、複数のノード３０のそれぞれが、次に、オーナーとして割り当てられているか、バックアップとして割り当てられているか、または、オーナーとしてもバックアップとしても割り当てられていないかを格納する。次役割表は、例えばノード３０に障害が発生したり新たなノード３０が追加されたりした場合等に、現役割表と置き換えられる表である。

次役割表は、一例として、図５に示されるように、行によりノード３０が特定され、列によりパーティションが特定される。この場合、次役割表は、行および列が直交する位置のそれぞれのセルに、その列により特定されるパーティションに対する、その行により特定されるノード３０に割り当てられた次の役割を格納する。

目標役割表は、複数のパーティションのそれぞれに対する、複数のノード３０のそれぞれに割り当てられたバックアップの候補としての役割を格納する。バックアップの候補は、将来、そのパーティションに対して、そのノード３０がオーナーまたはバックアップとしての役割を担うための準備をする役割である。なお、本実施形態の説明では、役割の名称を「バックアップの候補」としているが、バックアップの候補に割り当てられたノード３０が、将来、オーナーとなってもよい。

目標役割表は、一例として、図６に示されるように、行によりノード３０が特定され、列によりパーティションが特定される。この場合、目標役割表は、行および列が直交する位置のそれぞれのセルに、その列により特定されるパーティションに対する、その行により特定されるノード３０に割り当てられたバックアップの候補としての役割を格納する。なお、図面には、バックアップの候補としての役割が割り当てられている場合には“ＭＩＤ−ＢＡＣＫＵＰ”または“Ｍ”を記載し、バックアップの候補として割り当てられていない場合には空白とする。

第１割当部２２は、複数のノード３０のそれぞれの状況の変更に応じて、複数のパーティションのそれぞれに対して、オーナーとなるノード３０、および、バックアップとなるノード３０を割り当てる。また、例えば、複数のノード３０のうちの何れかのノード３０で障害が発生した場合、第１割当部２２は、障害が発生したノード３０を除いてオーナーおよびバックアップとなるノード３０を再度割り当てる。

また、新たなノード３０が追加された場合、第１割当部２２は、複数のパーティションのそれぞれに対して、新たなノード３０を含めてオーナーおよびバックアップとなるノード３０を再度割り当てる。また、バックアップの候補として割り当てられたノード３０へのデータ集合の送信が完了したことによりオーナーまたはバックアップとなることができるノード３０が新たに発生した場合、第１割当部２２は、複数のパーティションのそれぞれに対してオーナーおよびバックアップとなるノード３０を再度割り当てる。

ここで、第１割当部２２は、複数のパーティションの全てに対して、少なくともオーナーが存在するように、オーナーおよびバックアップとなるノード３０を割り当てる。これにより、第１割当部２２は、少なくともデータベースを機能させることができる。

また、第１割当部２２は、少なくともデータベースを機能させることを条件として、予め定められた範囲内の冗長度を有するように、複数のパーティションのそれぞれに対してオーナーおよびバックアップとなるノード３０を割り当てる。これにより、第１割当部２２は、何れかのノード３０に障害が発生しても、少なくともデータベースを機能させることができる可能性を高くすることができる。

また、第１割当部２２は、少なくともデータベースを機能させ且つ予め定められた範囲内の冗長度を有する条件として、オーナーおよびバックアップが複数のノード３０のそれぞれに分散するように、複数のパーティションのそれぞれに対してオーナーおよびバックアップとなるノード３０を割り当てる。これにより、第１割当部２２は、複数のノード３０のそれぞれの処理の負荷を均等とすることができる。

なお、本例においては、第１割当部２２は、次役割表を計算することにより、オーナーおよびバックアップとなるノード３０を割り当てる。第１割当部２２による次役割表の算出方法の一例については、図１３を参照して後で説明する。

第２割当部２３は、複数のノード３０の状況および現割当表により割り当てられるオーナーおよびバックアップの割り当て状況の変更に応じて、複数のパーティションのそれぞれに対して、バックアップの候補となるノード３０を割り当てる。また、例えば複数のノード３０のうちの何れかのノード３０で障害が発生した場合、第２割当部２３は、障害が発生したノード３０を除いてバックアップの候補となるノード３０を再度割り当てる。また、例えば、新たなノード３０が追加された場合、第２割当部２３は、複数のパーティションのそれぞれに対して、新たなノード３０を含めてバックアップの候補となるノード３０を再度割り当てる。

ここで、第２割当部２３は、将来において予め定められた範囲内の冗長度を有するように、複数のパーティションのそれぞれに対してバックアップの候補となるノード３０を割り当てる。これにより、第２割当部２３は、将来において何れかのノード３０に障害が発生しても、少なくともデータベースを機能させることができる可能性を高くすることができる。

また、第２割当部２３は、将来においてオーナーおよびバックアップが複数のノード３０のそれぞれに分散して割り当てられるように、複数のパーティションのそれぞれに対してバックアップの候補となるノード３０を割り当てる。これにより、第２割当部２３は、将来において複数のノード３０のそれぞれの処理の負荷を均等とすることができる。

なお、本例においては、第２割当部２３は、目標役割表を計算することにより、バックアップの候補となるノード３０を割り当てる。第２割当部２３による目標役割表の算出方法の一例については、図１４を参照して後で説明する。

クラスタ管理部２４は、複数のノード３０のそれぞれとネットワークを介してメッセージをやり取りして、複数のノード３０のそれぞれを管理する。例えば、クラスタ管理部２４は、一定時間毎に、ハートビートと呼ばれるメッセージを複数のノード３０のそれぞれとやり取りする。そして、クラスタ管理部２４は、ハートビートの返信の有無によって、障害が発生したノード３０を特定する。

また、クラスタ管理部２４は、定期的に、複数のノード３０のそれぞれからデータ保持表を受信する。そして、クラスタ管理部２４は、全てのノード３０から受信したデータ保持表をまとめて表記憶部２１に記憶させる。また、クラスタ管理部２４は、データ保持表が受信できたか否かによって、障害が発生したノード３０を特定する。

また、クラスタ管理部２４は、起動時に、第１割当部２２に次役割表を算出させ、算出させた次役割表を複数のノード３０のそれぞれに配布することにより複数のノード３０のそれぞれに割り当てに応じた動作を指示する。また、クラスタ管理部２４は、定期的に、第１割当部２２に次役割表を算出させる。そして、クラスタ管理部２４は、算出させた次役割表が現役割表から変化した場合、算出させた次役割表を複数のノード３０のそれぞれに配布することにより複数のノード３０のそれぞれに割り当てに応じた動作を指示する。そして、クラスタ管理部２４は、次役割表を配布後、表記憶部２１に記憶されている現役割表を、次役割表の内容に更新する。

例えば、何れかのノード３０に障害が発生した場合、新たなノード３０の追加があった場合、または、候補として割り当てられたノード３０へのデータ集合の送信が完了してバックアップとして割り当て可能なノード３０が発生した場合、第１割当部２２は、算出した次役割表が現役割表から変化する。従って、クラスタ管理部２４は、このような場合、次役割表を複数のノード３０のそれぞれに配布する。

また、クラスタ管理部２４は、定期的に、第２割当部２３に目標役割表を算出させ、算出した目標役割表を複数のノード３０のそれぞれに配布する。クラスタ管理部２４は、目標役割表を配布することにより、複数のノード３０のそれぞれに対して、候補として割り当てられたノード３０にオーナーまたはバックアップとして動作させるための準備を指示する。なお、クラスタ管理部２４は、次役割表と目標役割表とを異なる周期で算出させる。

複数のノード３０のそれぞれは、データストア部３１と、表記憶部３２と、アクセス処理部３３と、ノード管理部３４と、転送部３５とを有する。アクセス処理部３３、ノード管理部３４および転送部３５は、ノード３０のＣＰＵ１２がプログラムを実行することにより実現される。また、アクセス処理部３３、ノード管理部３４および転送部３５は、一部または全部がハードウェア回路で実現されてもよい。データストア部３１および表記憶部３２は、ノード３０のメモリ１３または外部記憶装置１６により実現される。

データストア部３１は、データベースを分割した複数のパーティションのうち、自ノードが現役割表によりオーナーまたはバックアップに割り当てられたパーティションのデータ集合を記憶する。例えば、図７に示されるように、３つに分割されたパーティション＃１〜＃３のうち、自ノードが、パーティション＃１に対してオーナーに割り当てられ、パーティション＃３に対してバックアップに割り当てられているとする。この場合、データストア部３１は、パーティション＃１およびパーティション＃３のデータ集合を記憶する。

また、ノード３０は、目標役割表によりバックアップの候補に割り当てられたパーティションについては、そのパーティションのオーナーに割り当てられたノード３０からデータ集合を受信する。データストア部３１は、自ノードが目標役割表によりバックアップの候補に割り当てられたパーティションのデータ集合における、オーナーのノード３０から受信済みの一部または全部を記憶する。

表記憶部３２は、データ保持表の自ノードに対応する部分を記憶する。また、表記憶部３２は、現役割表、次役割表および目標役割表を記憶する。現役割表は、次役割表を受信した場合、次役割表の内容に書き換えられる。目標役割表は、定期的に受信する目標役割表が変化した場合には、変化後の内容に書き換えられる。

アクセス処理部３３は、クライアントからのアクセス要求をネットワークを介して受信する。そして、アクセス処理部３３は、複数のパーティションのそれぞれに対して、現役割表により自ノードに対して割り当てられた役割に応じた処理を実行する。

具体的には、アクセス処理部３３は、現役割表によりオーナーとして割り当てられたパーティションに対するクライアントからのアクセス要求を受け付けて、そのアクセス要求に応じた処理を実行する。アクセス処理部３３は、一例として、参照要求を受け付けた場合には、そのパーティションのデータ集合の中の対応するデータを読み出してクライアントに送信する。また、アクセス処理部３３は、一例として、更新要求を受け付けた場合には、そのパーティションのデータ集合の対応するデータを更新する。また、アクセス処理部３３は、一例として、登録要求を受け付けた場合には、そのパーティションのデータ集合に新たなデータを登録する。

なお、アクセス処理部３３は、一連のアクセス要求を含むトランザクションを受け付けてもよい。この場合、アクセス処理部３３は、クライアントからの一連のアクセス要求をトランザクション処理により実行する。

また、アクセス処理部３３は、更新要求および登録要求を処理した場合には、現役割表によりそのパーティションについてバックアップに割り当てられたノード３０との間でレプリケーション処理を実行する。レプリケーション処理とは、バックアップに割り当てられたノード３０に、オーナーに割り当てられたノード３０に記憶されているデータ集合のレプリカ（複製）を生成するための処理である。

具体的には、図８に示されるように、アクセス処理部３３は、自ノードがオーナーに割り当てられたパーティションに対する更新または登録の要求を受け付けた場合、同一のアクセス要求をバックアップとして割り当てられた他のノード３０へと送信する。そして、他のノード３０のアクセス処理部３３は、バックアップとして割り当てられたパーティションに対する、オーナーとして割り当てられたノード３０から更新または登録の要求を受け付けて、その要求に応じた更新または登録の処理を実行する。

アクセス処理部３３は、このようなレプリケーション処理をすることにより、オーナーとして割り当てられたノード３０とバックアップとして割り当てられたノード３０との間で、データ集合の同期を取ることができる。

なお、オーナーとして割り当てられたノード３０のアクセス処理部３３は、レプリケーション処理を実行する場合において、一連のアクセス要求を含むトランザクションを送信してもよい。この場合、バックアップとして割り当てられたノード３０のアクセス処理部３３は、レプリケーション処理をトランザクション処理により実行する。

また、アクセス処理部３３は、更新要求および登録要求を処理した場合には、表記憶部３２に記憶されたデータ保持表の対応するパーティションのタイムスタンプを更新する。

ノード管理部３４は、管理装置２０のクラスタ管理部２４とネットワークを介してメッセージをやり取りする。ノード管理部３４は、クラスタ管理部２４からハートビートと呼ばれるメッセージを受信したことに応じて、自ノードに障害が発生していければ応答メッセージを送信する。また、ノード管理部３４は、定期的に、表記憶部３２に記憶されているデータ保持表をクラスタ管理部２４へと送信する。

また、ノード管理部３４は、クラスタ管理部２４から次役割表を受信し、受信した次役割表を表記憶部３２に記憶させる。そして、次役割表を受信した場合には、ノード管理部３４は、図９に示されるように、次役割表により割り当てられた役割で複数のノード３０のそれぞれを動作させるためにクライアントからのアクセス要求に応じた処理を一時的に中断して行う同期処理である、短期同期処理を実行する。

具体的には、ノード管理部３４は、複数のパーティションのそれぞれに対して、次役割表により示された役割で複数のノード３０のそれぞれを動作させるために、アクセス処理部３３にレプリケーション処理と同様の処理を実行させる。これにより、ノード管理部３４は、複数のパーティションのそれぞれに対して、オーナーとして割り当てられたノード３０とバックアップとして割り当てられたノード３０との間のデータ集合の同期を取ることができる。そして、データ集合の同期をとった後に、ノード管理部３４は、アクセス処理部３３に、現役割表を次役割表の内容に書き換えて、複数のパーティションのそれぞれに対する次役割表により割り当てられた新たな役割に応じた処理を実行させる。

そして、ノード管理部３４は、短期同期処理が完了すると、現役割表の内容を次役割表の内容に更新する。以後、アクセス処理部３３は、クライアントからのアクセス要求を受け付けることができる。

また、ノード管理部３４は、クラスタ管理部２４から目標役割表を定期的に受信し、受信した目標役割表を表記憶部３２に記憶させる。

転送部３５は、図１０に示されるように、目標役割表により割り当てられた役割で複数のノード３０のそれぞれを動作させるためにクライアントからのアクセス要求に対する処理を中断させずに行う同期処理である、長期同期処理を実行する。具体的には、転送部３５は、自ノードが現役割表によりオーナーとして割り当てられたパーティションのデータ集合を、目標役割表によりバックアップの候補として割り当てられており且つ現役割表によりオーナーにもバックアップにも割り当てられていない他のノード３０に、アクセス要求に対する処理を中断させずに送信する。また、転送部３５は、自ノードが目標役割表によりバックアップの候補として割り当てられており且つ現役割表によりオーナーにもバックアップにも割り当てられていないパーティションのデータ集合を、現役割表によりオーナーとして割り当てられた他のノード３０から、アクセス要求に対する処理を中断させずに受信する。

転送部３５は、このような長期同期処理を実行することにより、オーナーに割り当てられたノード３０に記憶されたデータ集合のレプリカを、オーナーまたはバックアップに割り当てられていないノード３０に記憶させることができる。これにより、転送部３５は、長期同期処理が完了した後において、オーナーまたはバックアップとなることができるノード３０を新たに生成することができる。

ここで、長期同期処理を実行する場合において、転送部３５は、オーナーに割り当てられたパーティションのデータ集合を、アクセス処理部３３によるトランザクションの実行を妨害しないバックグラウンドで、バックアップの候補として割り当てられたノード３０に送信する。また、転送部３５は、バックアップの候補として割り当てられたパーティションのデータ集合を、バックグラウンドで、オーナーに割り当てられたノード３０から受信する。なお、バックグラウンドでの処理とは、一例として、ノード３０が複数のＣＰＵ１２を備える場合にはトランザクション処理を実行していない一部のＣＰＵ１２を用いて実行する処理である。また、バックグラウンドでの処理とは、一例として、ＣＰＵ１２が時分割処理をしている場合にはＣＰＵ１２がトランザクション処理を実行していない一部の時間帯で実行する処理である。これにより、転送部３５は、クライアントからのアクセス要求に対する応答速度等の低下を招くことなく、長期同期処理を実行することができる。

また、転送部３５は、現役割表で自ノードがバックアップに割り当てられたパーティションのデータ集合を、目標役割表によりバックアップの候補に割り当てられており且つオーナーにもバックアップにも割り当てられていない他のノード３０に対して送信してもよい。この場合、転送部３５は、他のノード３０から同一のデータ集合が送信されていないことを条件として処理をする。

図１１は、ノード３０に割り当てられる役割の遷移を示す図である。ノード３０は、複数のパーティションのそれぞれに対して、“オーナー”、“バックアップ”または“バックアップの候補”が割り当てられた状態、または、何れの役割も割り当てられていない“無し”状態のいずれかに遷移する。

ノード３０は、“無し”状態と“オーナー”状態との間を、短期同期処理により相互に遷移する。また、ノード３０は、“オーナー”状態と“バックアップ”状態との間を、短期同期処理により相互に遷移する。また、ノード３０は、“バックアップ”状態から“無し”状態へと、短期同期処理により遷移する。

また、ノード３０は、“無し”状態と“バックアップの候補”状態との間を、長期同期処理により相互に遷移する。そして、ノード３０は、“バックアップの候補”状態から“バックアップ”状態へと、短期同期処理により遷移する。

図１２は、管理装置２０のクラスタ管理部２４の処理フローを示す図である。クラスタ管理部２４は、以下のステップＳ１１１〜ステップＳ１４２の処理を実行する。

まず、ステップＳ１１１において、クラスタ管理部２４は、データ保持表の受信イベント、第１の定周期イベントまたは第２の定周期イベントを検出する。データ保持表の受信イベントは、複数のノード３０のそれぞれから送信されたデータ保持表をクラスタ管理部２４が受信した場合に発生する。第１の定周期イベントおよび第２の定周期イベントは、それぞれ定期的に発生する。ただし、第１の定周期イベントと第２の定周期イベントとの発生間隔は、互いに異なる。

クラスタ管理部２４は、データ保持表の受信イベントを検出した場合には、処理をステップＳ１２１に進める。クラスタ管理部２４は、第１の定周期イベントを検出した場合には、処理をステップＳ１３１に進める。クラスタ管理部２４は、第２の定周期イベントを検出した場合には、処理をステップＳ１４１に進める。

データ保持表の受信イベントを検出した場合、ステップＳ１２１において、クラスタ管理部２４は、起動してから最初のデータ保持表の受信イベントであるか否かを判断する。

起動してから最初のデータ保持表の受信イベントである場合（ステップＳ１２１のＹｅｓ）、クラスタ管理部２４は、処理をステップＳ１２２に進める。ステップＳ１２２において、クラスタ管理部２４は、受信したデータ保持表を表記憶部２１に登録する。

続いて、ステップＳ１２３において、クラスタ管理部２４は、次役割表を第１割当部２２に算出させる。なお、第１割当部２２による次役割表の算出処理については、図１３を参照して説明する。

続いて、ステップＳ１２４において、クラスタ管理部２４は、算出した次役割表を複数のノード３０のそれぞれに配布する。そして、クラスタ管理部２４は、ステップＳ１２４の処理を終えると、処理をステップＳ１１１に戻す。

また、起動してから最初のデータ保持表の受信イベントではない場合（ステップＳ１２１のＮｏ）、ステップＳ１２５において、クラスタ管理部２４は、表記憶部２１のデータ保持表を更新する。そして、クラスタ管理部２４は、ステップＳ１２５の処理を終えると、処理をステップＳ１１１に戻す。

一方、第１の定周期イベントを検出した場合、ステップＳ１３１において、クラスタ管理部２４は、前回の第１の定周期イベントから今回の第１の定周期イベントまでの間に、複数のノード３０の全てからデータ保持表が受信できたか否かを判断する。クラスタ管理部２４は、複数のノード３０の全てからデータ保持表を受信できた場合（ステップＳ１３１のＹｅｓ）、処理をステップＳ１３４に進める。クラスタ管理部２４は、何れかのノード３０からデータ保持表を受信できなかった場合（ステップＳ１３１のＮｏ）、処理をステップＳ１３２に進める。

ステップＳ１３２において、クラスタ管理部２４は、データ保持表を受信できなかったノード３０をデータベースシステム１０から切り離す処理を行う。続いて、ステップＳ１３３において、クラスタ管理部２４は、切り離したノード３０の内容をデータ保持表から削除して、データ保持表を更新する。クラスタ管理部２４は、ステップＳ１３３の処理を終えると、処理をステップＳ１３４に進める。

ステップＳ１３４において、クラスタ管理部２４は、次役割表を第１割当部２２に算出させる。なお、第１割当部２２による次役割表の算出処理については、図１３を参照して説明する。

続いて、ステップＳ１３５において、クラスタ管理部２４は、次役割表が変化したか否かを判断する。例えば、障害が発生したノード３０を切り離した場合、新たなノード３０が追加された場合、または、長期同期処理が完了してバックアップとして割り当てられるノード３０が変更する場合に、次役割表が変化する。

次役割表が変化していない場合（ステップＳ１３５のＮｏ）、クラスタ管理部２４は、処理をステップＳ１１１に戻す。次役割表が変化した場合（ステップＳ１３５のＹｅｓ）、ステップＳ１３６において、クラスタ管理部２４は、変化後の次役割表を複数のノード３０のそれぞれに配布する。そして、クラスタ管理部２４は、ステップＳ１３６の処理を終えると、処理をステップＳ１１１に戻す。

また、一方、第２の定周期イベントを検出した場合、ステップＳ１４１において、クラスタ管理部２４は、目標役割表を第２割当部２３に算出させる。なお、第２割当部２３による目標役割表の算出処理については、図１４を参照して説明する。

続いて、ステップＳ１４２において、クラスタ管理部２４は、算出した目標役割表を複数のノード３０のそれぞれに配布する。そして、クラスタ管理部２４は、ステップＳ１４２の処理を終えると、処理をステップＳ１１１に戻す。

図１３は、管理装置２０の第１割当部２２による次役割表の算出処理のフローを示す図である。第１割当部２２は、図１２のステップＳ１２３およびステップＳ１３４でクラスタ管理部２４に呼び出されて、以下のステップＳ２１１〜ステップＳ２２０の処理を実行する。

まず、ステップＳ２１１において、第１割当部２２は、次役割表を初期化する。このとき、第１割当部２２は、次役割表の複数のノード３０のそれぞれをデータ保持表のノード３０に対応付ける。これにより、第１割当部２２は、障害発生により切り離されたノード３０および新たに追加されたノード３０を、次役割表に反映することができる。

続いて、ステップＳ２１２とステップＳ２２０の間において、第１割当部２２は、パーティション毎にループ処理を実行する。例えば、第１割当部２２は、データベースを第１から第３のパーティションに分割する場合には、第１のパーティション、第２のパーティションおよび第３のパーティションのそれぞれを対象として、ステップＳ２１２からステップＳ２２０の処理を実行する。

パーティション毎のループ処理内では、まず、ステップＳ２１３において、第１割当部２２は、対象のパーティションについて、データ保持表で最大のタイムスタンプを有するノード３０の集合を選択する。本例において、タイムスタンプは、対象のパーティションのデータ集合が更新される毎に１ずつインクリメントされる値である。従って、ステップＳ２１３では、第１割当部２２は、対象のパーティションについて、最新のデータ集合を記憶しているノード３０の集合を選択することができる。

続いて、ステップＳ２１４において、第１割当部２２は、ステップＳ２１３で選択したノード３０の集合の中から、次役割表でオーナーおよびバックアップとして割り当てられたパーティションの数が最も少ない１つのノード３０を選択して、選択したノード３０をオーナーとして割り当てる。これにより、第１割当部２２は、最新のデータ集合を記憶しているノード３０の集合のうち負荷の最も小さいノード３０をオーナーとして割り当てることができる。

なお、オーナーおよびバックアップとして割り当てられたパーティションの数が最も少ないノード３０が複数個存在する場合には、第１割当部２２は、演算能力の高いノード３０を演算能力の低いノード３０よりも優先的にオーナーとして割り当ててもよい。これに代えて、第１割当部２２は、アクセス要求を受け付ける数が少ないノード３０をアクセス要求を受け付ける数が多いノード３０よりも優先的にオーナーとして割り当ててもよい。

続いて、ステップＳ２１５において、第１割当部２２は、対象のパーティションについて、オーナーとして割り当てたノード３０を除いて、最大のタイムスタンプからの差が一定の範囲内のタイムスタンプを有するノード３０の集合を選択する。これにより、第１割当部２２は、対象のパーティションについて、最新のデータ集合または最新のデータ集合に比較的近いデータ集合を記憶しているノード３０の集合を選択することができる。

続いて、ステップＳ２１６とステップＳ２１９との間において、第１割当部２２は、レプリケーションの数分、ループ処理を実行する。ここで、レプリケーションの数とは、オーナーに割り当てられたノード３０との間でレプリケーション処理が可能な最大のノード３０の数をいう。すなわち、レプリケーションの数は、割り当てが可能なバックアップの数と同一である。

レプリケーションの数分のループ処理内では、まず、ステップＳ２１７において、第１割当部２２は、ステップＳ２１５で選択したノード３０の集合の中に、バックアップとして割り当て可能なノード３０が存在するか否かを判断する。バックアップとして割り当て可能なノード３０が存在する場合（ステップＳ２１７のＹｅｓ）、第１割当部２２は、処理をステップＳ２１８に進める。

バックアップとして割り当て可能なノード３０が無い場合（ステップＳ２１７のＮｏ）、第１割当部２２は、レプリケーションの数分のループ処理を強制的に抜けて、処理をステップＳ２２０に進める。すなわち、従って、第１割当部２２は、バックアップが存在しなかったり、バックアップの数がレプリケーションの数未満であったりする次役割表を算出する場合もある。

ステップＳ２１８において、第１割当部２２は、ステップＳ２１５で選択したノード３０の集合の中から、次役割表でオーナーおよびバックアップとして割り当てられたパーティションの数が最も少ないノード３０を、バックアップとして割り当てる。これにより、第１割当部２２は、最新のデータ集合または最新のデータ集合に近いデータを記憶しているノード３０の集合のうち負荷の小さい順にバックアップとするノード３０を割り当てることができる。

なお、オーナーおよびバックアップとして割り当てられたパーティションの数が最も少ないノード３０が複数個存在する場合には、第１割当部２２は、演算能力の高いノード３０を演算能力の低いノード３０よりも優先的にバックアップとして割り当ててもよい。これに代えて、第１割当部２２は、アクセス要求を受け付ける数が少ないノード３０をアクセス要求を受け付ける数が多いノード３０よりも優先的にバックアップとして割り当ててもよい。

そして、第１割当部２２は、選択したノード３０の集合からバックアップとして割り当てたノード３０を除いて、処理をステップＳ２１９に進める。ステップＳ２１９において、第１割当部２２は、ステップＳ２１６からステップＳ２１９までの処理回数が、レプリケーションの数より少ない場合には処理をステップＳ２１６に戻し、レプリケーションの数に一致した場合には処理をステップＳ２２０に進める。

続いて、ステップＳ２２０において、第１割当部２２は、ステップＳ２１２からステップＳ２２０までの処理を全てのパーティションに対して実行していない場合には、処理をステップＳ２１６に戻す。そして、第１割当部２２は、ステップＳ２１２からステップＳ２２０までの処理を全てのパーティションに対して実行した場合には、次役割表の算出を終了して本フローを抜ける。

以上のように第１割当部２２によれば、複数のパーティションの全てに対してオーナーとなるノード３０を割り当てることにより、少なくともデータベースを機能させることができる。これとともに、第１割当部２２によれば、可能な限りバックアップとなるノード３０を割り当てることによりデータベースの冗長度を担保することができる。さらに、第１割当部２２によれば、より負荷の小さいノード３０から順にオーナーおよびバックアップとなるノード３０を割り当てることにより、複数のノード３０のそれぞれの負荷を均等にすることができる。

図１４は、管理装置２０の第２割当部２３による目標役割表の算出処理のフローを示す図である。第２割当部２３は、図１２のステップＳ１４１でクラスタ管理部２４に呼び出されて、以下のステップＳ３１１〜ステップＳ３２４の処理を実行する。

まず、ステップＳ３１１において、第２割当部２３は、目標役割表を初期化する。このとき、第２割当部２３は、目標役割表の複数のノード３０のそれぞれをデータ保持表のノード３０に対応付ける。これにより、第２割当部２３は、障害発生により切り離されたノード３０および新たに追加されたノード３０を、目標役割表に反映することができる。

続いて、ステップＳ３１２において、第２割当部２３は、現役割表のパーティションを、割り当てられたオーナーおよびバックアップの合計数で昇順にソートする。これにより、第２割当部２３は、バックアップとして割り当てられたノード３０が少ないパーティションから順に、バックアップの候補を割り当てることができる。すなわち、第２割当部２３は、現役割表において、冗長度の少ないパーティションから順に、バックアップの候補となるノード３０を割り当てることができる。

続いて、ステップＳ３１３において、第２割当部２３は、複数のノード３０のそれぞれに対応する負荷値を初期化する。負荷値は、ノード３０にバックアップの候補の役割を割り当てたことに応じて増加する値である。第２割当部２３は、一例として、それぞれの負荷値を“０”に初期化する。

続いて、ステップＳ３１４とステップＳ３２４の間において、第２割当部２３は、パーティション毎にループ処理を実行する。この場合において、第２割当部２３は、ステップＳ３１２で並べ替えられた現役割表のパーティションの順で対象のパーティションを選択して、ループ処理を実行する。

パーティション毎のループ処理内では、まず、ステップＳ３１５において、第２割当部２３は、対象のパーティションについて、データ保持表で最大のタイムスタンプのノード３０を選択する。

続いて、ステップＳ３１６において、第２割当部２３は、現役割表のノード３０を、値Ｖで降順にソートする。ここで、値Ｖは、オーナーとして割り当てられたノード３０については“＋１”、バックアップとして割り当てられたノード３０については“＋１”、および、最大のタイムスタンプのノード３０については“＋１”とされる値である。従って、オーナーでも無く、バックアップでもなく且つタイムスタンプも最大でないノード３０の値Ｖは、“０”となる。

これにより、第２割当部２３は、オーナーおよびバックアップとして割り当てられたノード３０または最新のデータ集合を記憶するノード３０を先に、バックアップの候補となるノード３０として割り当てることができる。

なお、値Ｖが同一のノード３０が複数個並んでいる場合には、第２割当部２３は、演算能力の高いノード３０が先にバックアップの候補となるように上位に配置する。これにより、第２割当部２３は、演算能力の高いノード３０が演算能力の低いノード３０よりも優先的にオーナーまたはバックアップとなるように、バックアップの候補となるノード３０を割り当てることができる。これに代えて、第２割当部２３は、アクセス要求を受け付ける数が少ないノード３０が先にバックアップの候補となるように上位に配置してもよい。これにより、第２割当部２３は、アクセス要求を受け付ける数が少ないノード３０がアクセス要求を受け付ける数が多いノード３０よりも優先的にオーナーまたはバックアップとなるように、バックアップの候補となるノード３０を割り当てることができる。

続いて、ステップＳ３１７において、第２割当部２３は、定数である上限重みＭＬＯＡＤを下記の式（１）により算出する。
ＭＬＯＡＤ＝｛パーティションの数×（レプリケーション数＋１）＋（ノード数−１）｝÷ノード数 …（１）

ここで、（レプリケーション数＋１）は、１つのパーティションに対して割り当てること可能な、オーナーおよびバックアップの最大数を表す。このような、上限重みＭＬＯＡＤは、１つのノード３０にバックアップの候補として割り当てられることができる数の上限の基準を表す。

続いて、ステップＳ３１８とステップＳ３２３の間において、第２割当部２３は、ノード３０毎にループ処理を実行する。この場合において、第２割当部２３は、ステップＳ３１６で並べ替えられた現役割表の順序で対象のノード３０を選択して、ループ処理を実行する。

ノード３０毎のループ処理内では、まず、ステップＳ３１９において、第２割当部２３は、（レプリケーションの数＋１）個分のノード３０に、バックアップの候補となるノード３０を割り当てたか否かを判断する。（レプリケーションの数＋１）個分のノード３０にバックアップの候補を割り当てた場合には（ステップＳ３１９のＹｅｓ）、処理をステップＳ３２４に進める。この場合、第２割当部２３は、対象のパーティションに対してバックアップの候補となるノード３０を最大数割り当ている。

第２割当部２３は、（レプリケーションの数＋１）個分のノード３０にバックアップの候補を割り当てていない場合には（ステップＳ３１９のＮｏ）、処理をステップＳ３２０に進める。

ステップＳ３２０において、第２割当部２３は、対象となるノード３０の負荷値が、上限重みＭＬＯＡＤより小さいかを判断する。対象となるノード３０の負荷値が上限重みＭＬＯＡＤより小さい場合には（ステップＳ３２０のＹｅｓ）、第２割当部２３は、処理をステップＳ３２１に進める。

対象となるノード３０の負荷値が上限重みＭＬＯＡＤ以上の場合には（ステップＳ３２０のＮｏ）、第２割当部２３は、処理をステップＳ３２３に進める。これにより、第２割当部２３は、ある一つのノード３０にバックアップの候補としての役割を基準値以上割り当てた場合には、そのノード３０をこれ以上バックアップの候補として割り当てることを回避することができる。この結果、第２割当部２３は、複数のノード３０にバックアップの候補としての役割を分散して割り当てることができる。

ステップＳ３２１において、第２割当部２３は、対象のパーティションに対して対象のノード３０をバックアップの候補として割り当てる。続いて、ステップＳ３２２において、第２割当部２３は、対象のノード３０の負荷値に“１”を加算することにより更新する。これにより、第２割当部２３は、候補として割り当てられる毎にノード３０の負荷値を１ずつ増加させることができる。第２割当部２３は、ステップＳ３２２の処理を終えると、処理をステップＳ３２３に進める。

続いて、ステップＳ３２３において、第２割当部２３は、ステップＳ３１８からステップＳ３２３までの処理を複数のノード３０の全てに対して実行していない場合には、処理をステップＳ３１８に戻す。また、第２割当部２３は、ステップＳ３１８からステップＳ２２３までの処理を複数のノード３０の全てに対して実行した場合には、処理をステップＳ３２４に進める。

続いて、ステップＳ３２４において、第２割当部２３は、ステップＳ３１４からステップＳ３２４までの処理を複数のパーティションの全てに対して実行していない場合には、処理をステップＳ３１４に戻す。そして、第２割当部２３は、ステップＳ３１４からステップＳ３２４までの処理を複数のパーティションの全てに対して実行した場合には、目標役割表の算出を終了して本フローを抜ける。

以上のように第２割当部２３によれば、冗長度の少ない（すなわち、割り当てられたバックアップの数が少ない）パーティションから順に、バックアップの候補を割り当てるので、効率良くデータベースの冗長度を確保することができる。さらに、第２割当部２３によれば、割り当てたバックアップの候補の数が基準値以上となったノード３０に対してさらにバックアップの候補を割り当てないので、複数のノード３０に分散してバックアップの候補を割り当てることができる。

図１５は、ノード３０のアクセス処理部３３の処理フローを示す図である。アクセス処理部３３は、以下のステップＳ４１１〜ステップＳ４３３の処理を実行する。

まず、ステップＳ４１１において、アクセス処理部３３は、クライアントからの要求受信イベントまたはレプリケーション処理による要求受信イベントを検出する。クライアントからの要求受信イベントは、データベースに対するアクセス要求をクライアントからネットワークを介して受信した場合に発生する。レプリケーション処理による要求受信イベントは、レプリケーション処理による更新要求または登録要求を、オーナーとなる他のノード３０からネットワークを介して受信した場合に発生する。

アクセス処理部３３は、クライアントからの要求受信イベントを検出した場合には、処理をステップＳ４２１に進める。アクセス処理部３３は、レプリケーション処理による要求受信イベントを検出した場合には、処理をステップＳ４３１に進める。

クライアントからの要求受信イベントを検出した場合、ステップＳ４２１において、アクセス処理部３３は、クライアントからのアクセス要求に示される要求先のパーティションの番号を例えば計算して取得する。続いて、ステップＳ４２２において、アクセス処理部３３は、要求先のパーティションに対して自ノードがオーナーに割り当てられているか否かを現役割表を参照して判断する。

要求先のパーティションに対して自ノードがオーナーに割り当てられていない場合には（ステップＳ４２２のＮｏ）、ステップＳ４２３において、アクセス処理部３３は、クライアントにオーナーに割り当てられたノード３０の番号を通知して、処理をステップＳ４１１に戻す。

要求先のパーティションに対して自ノードがオーナーに割り当てられている場合には（ステップＳ４２２のＹｅｓ）、ステップＳ４２４において、アクセス処理部３３は、アクセス要求のタイプが、参照であるか、更新または登録であるかを判断する。

アクセス要求のタイプが参照である場合には（ステップＳ４２４の参照）、ステップＳ４２５において、アクセス処理部３３は、参照要求のあったデータをデータストア部３１から読み出してクライアントに送信し、処理をステップＳ４１１に戻す。

アクセス要求のタイプが更新または登録である場合には（ステップＳ４２４の更新／登録）、ステップＳ４２６において、要求先のパーティションに対してバックアップとして割り当てられた他のノード３０との間でレプリケーション処理を実行する。すなわち、アクセス処理部３３は、クライアントから受信した更新または登録の要求と同一のアクセス要求をバックアップとして割り当てられたノード３０へと送信する。

レプリケーション処理が完了すると、続いて、ステップＳ４２７において、アクセス処理部３３は、クライアントから送信された更新または登録要求に従って、データストア部３１に記憶されているデータの更新またはデータストア部３１に新たなデータの登録をする。続いて、ステップＳ４２８において、アクセス処理部３３は、データ保持表のタイムスタンプを１インクリメントすることにより更新し、処理をステップＳ４１１に戻す。

一方、アクセス処理部３３は、レプリケーション処理による要求受信イベントを検出した場合、ステップＳ４３１において、オーナーとなるノード３０から送信された更新または登録要求に従って、データストア部３１に記憶されているデータの更新またはデータストア部３１に新たなデータの登録をする。続いて、ステップＳ４３２において、アクセス処理部３３は、データ保持表のタイムスタンプを１インクリメントすることにより更新する。続いて、ステップＳ４３３において、アクセス処理部３３は、登録または更新が完了したことをオーナーに通知して、処理をステップＳ４１１に戻す。

なお、アクセス処理部３３は、ステップＳ４２５およびステップＳ４２８において、一連のアクセス要求を含むトランザクションをクライアントから受け付けて、クライアントからのアクセス要求に応じたトランザクション処理を実行してもよい。また、アクセス処理部３３は、ステップＳ４２６において、レプリケーション処理により更新または登録の要求を送信する場合、バックアップとして割り当てられたノード３０に一連のアクセス要求を含むトランザクションを送信してもよい。また、アクセス処理部３３は、ステップＳ４３１において、一連のアクセス要求を含むトランザクションをオーナーとなるノード３０から受け付けて、オーナーとなるノード３０からのアクセス要求に応じたトランザクション処理を実行してもよい。

図１６は、ノード３０のノード管理部３４の処理フローを示す図である。ノード管理部３４は、以下のステップＳ５１１〜ステップＳ５４１の処理を実行する。

まず、ステップＳ５１１において、ノード管理部３４は、第３の定周期イベント、次役割表の受信イベントまたは目標役割表の受信イベントを検出する。第３の定周期イベントは、定期的に発生する。次役割表の受信イベントは、次役割表をノード管理部３４が受信した場合に発生する。目標役割表の受信イベントは、目標役割表をノード管理部３４が受信した場合に発生する。

ノード管理部３４は、第３の定周期イベントを検出した場合には、処理をステップＳ５２１に進める。ノード管理部３４は、次役割表の受信イベントを検出した場合には、処理をステップＳ５３１に進める。ノード管理部３４は、目標役割表の受信イベントを検出した場合には、処理をステップＳ５４１に進める。

第３の定周期イベントを検出した場合、ステップＳ５２１において、ノード管理部３４は、表記憶部３２に記憶されているデータ保持表を管理装置２０のクラスタ管理部２４に送信する。そして、ノード管理部３４は、処理をステップＳ５１１に戻す。

次役割表の受信イベントを検出した場合、ステップＳ５３１において、ノード管理部３４は、アクセス処理部３３がトランザクションを実行中であれば、処理を中断させる。続いて、ステップＳ５３２において、ノード管理部３４は、受信した次役割表に従って、短期同期処理を実行する。

具体的には、ノード管理部３４は、複数のパーティションのそれぞれに対して、オーナーとなるノード３０とバックアップとなるノード３０との間において記憶しているデータ集合に相違がある場合には、アクセス処理部３３にレプリケーション処理と同様の処理を実行させる。これにより、ノード管理部３４は、複数のパーティションのそれぞれに対して、オーナーとして割り当てられたノード３０とバックアップとして割り当てられたノード３０との間の同期を取ることができる。そして、ノード管理部３４は、複数のパーティションのそれぞれに対して、次役割表により割り当てられた新たな役割（オーナーおよびバックアップ）に応じた処理をアクセス処理部３３に実行させる。

短期同期処理が完了すると、続いて、ステップＳ５３３において、ノード管理部３４は、現役割表を、次役割表の内容に書き換える。これにより、アクセス処理部３３は、クライアントからのアクセス要求を受け付けることができる。

続いて、ステップＳ５３４において、ノード管理部３４は、中断してトランザクションを再開させる。そして、ノード管理部３４は、処理をステップＳ５１１に戻す。

目標役割表の受信イベントを検出した場合、ステップＳ５４１において、ノード管理部３４は、表記憶部３２に記憶されている目標役割表を更新する。そして、ノード管理部３４は、処理をステップＳ５１１に戻す。

図１７は、ノード３０の転送部３５の処理フローを示す図である。転送部３５は、以下のステップＳ６１１〜ステップＳ６１８の処理、および、ステップＳ６２１〜ステップＳ６２２の処理を実行する。

まず、ステップＳ６１１において、転送部３５は、ＣＰＵ１２の負荷が予め定められた基準値より大きいか否かを判断する。負荷が基準値より大きい場合（ステップＳ６１１のＹｅｓ）、ステップＳ６１２において、転送部３５は、一定時間スリープしてから、処理をステップＳ６１１に戻す。

負荷が基準値以下である場合（ステップＳ６１１のＮｏ）、ステップＳ６１３において、転送部３５は、現役割表と目標役割表との間の差を検出する。続いて、ステップＳ６１４において、転送部３５は、現役割表と目標役割表との間に差があるか否かを判断する。

現役割表と目標役割表との間に差が無い場合（ステップＳ６１４のＮｏ）、ステップＳ６１５において、転送部３５は、現役割表、次役割表および目標役割表の何れにも自ノードに役割が割り当てられていないパーティションがあれば、そのデータ集合を消去する。そして、転送部３５は、ステップＳ６１５の処理の後、処理をステップＳ６１１に戻す。

現役割表と目標役割表との間に差がある場合（ステップＳ６１４のＹｅｓ）、ステップＳ６１６において、転送部３５は、現役割表で自ノードがオーナーのパーティションについて、目標役割表ではバックアップの候補であり且つ現役割表ではオーナーでもバックアップでもない他のノード３０を検出する。

続いて、ステップＳ６１７において、転送部３５は、目標役割表ではバックアップの候補であり、現役割表ではオーナーでもバックアップでもない他のノード３０が存在するか否かを判断する。存在しない場合（ステップＳ６１７のＮｏ）、転送部３５は、処理をステップＳ６１１に戻す。

存在する場合（ステップＳ６１７のＹｅｓ）、ステップＳ６１８において、転送部３５は、クライアントからのアクセス要求に対する処理を中断させずに、長期同期処理を開始する。具体的には、転送部３５は、現役割表で自ノードがオーナーに割り当てられたパーティションについて、目標役割表によりバックアップの候補に割り当てられており且つ現役割表によりオーナーにもバックアップにも割り当てられていない他のノード３０に対して、そのパーティションのデータ集合を送信する。この場合に、転送部３５は、データ集合をアクセス処理部３３によるトランザクションの実行を妨害しないバックグラウンドで送信する。これにより、転送部３５は、クライアントからのアクセス要求に対する応答速度等の低下を招くことなく、長期同期処理を実行することができる。

そして、転送部３５は、ステップＳ６１８の処理を終了すると、処理をステップＳ６１１に戻す。

一方、目標役割表によりバックアップの候補に割り当てられており且つ現役割表によりオーナーにもバックアップにも割り当てられていないパーティションを有する他のノード３０の転送部３５は、以下のステップＳ６２１およびステップＳ６２２の処理を実行する。

ステップＳ６２１において、転送部３５は、クライアントからのアクセス要求に対する処理を中断させずに、長期同期処理を開始する。具体的には、転送部３５は、目標役割表によりバックアップの候補に割り当てられており且つ現役割表によりオーナーにもバックアップにも割り当てられていないパーティションについて、オーナーに割り当てられたノード３０からデータ集合を受信する。この場合に、転送部３５は、データ集合をアクセス処理部３３によるトランザクションの実行を妨害しないバックグラウンドで受信する。

続いて、ステップＳ６２２において、転送部３５は、データ保持表を更新する。長期同期処理が完了すると、オーナーとなるノード３０に記憶されているデータ集合のレプリカが記憶されるので、転送部３５は、データ保持表を更新することにより、そのパーティションのタイムスタンプを、オーナーのデータ保持表のタイムスタンプと一致させることができる。そして、転送部３５は、ステップＳ６２２の処理を終えると、転送部３５は、本フローを終了する。

以上のように転送部３５によれば、バックアップの候補として割り当てられたノード３０にオーナーとして割り当てられたノード３０のデータ集合のレプリカを生成するので、オーナーまたはバックアップとなることができるノード３０を新たに発生させることができる。

図１８は、管理装置２０を選任するための第１の処理フローを示す図である。複数のノード３０のそれぞれは、データベースの起動時、または、管理装置２０からのハートビートが受信できなくなった場合（すなわち、管理装置２０に障害が発生した場合）に、図１８に示す第１の処理フローを実行する。なお、図１８に示す第１の処理フローは、ブリーアルゴリズムとも呼ばれる。

第１の処理フローを実行する前提として、複数のノード３０のそれぞれは、固有の数値（ＩＤ値）を有している。ＩＤ値は、例えば、そのノード３０の起動開始時刻とネットワークのポート番号とを合成した値である。また、第１の処理フローを実行する前提として、複数のノード３０のそれぞれは、他のノード３０のＩＤ値を知っている。

まず、ステップＳ７１１において、ノード３０は、自分より大きいＩＤ値を有する全てのノード３０のそれぞれに、Ｅｌｅｃｔｉｏｎメッセージを送信する。Ｅｌｅｃｔｉｏｎメッセージは、他のノード３０に選挙を通知するメッセージである。Ｅｌｅｃｔｉｏｎメッセージには、送信したノード３０のＩＤ値が含まれる。

続いて、ステップＳ７１２において、ノード３０は、送信したＥｌｅｃｔｉｏｎメッセージに対するＡｎｓｗｅｒメッセージを受信したか否かを判断する。Ａｎｓｗｅｒメッセージを受信した場合には（ステップＳ７１２のＹｅｓ）、ノード３０は、処理をステップＳ７１３に進める。ステップＳ７１３において、ノード３０は、何れかのノード３０からＣｏｏｒｄｉｎａｔｏｒメッセージを受信するまで処理を待機する。Ｃｏｏｒｄｉｎａｔｏｒメッセージは、Ｅｌｅｃｔｉｏｎメッセージで通知された選挙に勝利したことを通知するメッセージである。すなわち、Ｃｏｏｒｄｉｎａｔｏｒメッセージは、管理装置２０として機能することを宣言するメッセージである。ノード３０は、Ｃｏｏｒｄｉｎａｔｏｒメッセージを受信すると（ステップＳ７１３のＹｅｓ）、本フローを終了する。

一方、Ａｎｓｗｅｒメッセージを受信しなかった場合には（ステップＳ７１２のＮｏ）、ノード３０は、処理をステップＳ７１４に進める。ステップＳ７１４において、ノード３０は、何れかのノード３０からＥｌｅｃｔｉｏｎメッセージを受信したか否かを判断する。Ｅｌｅｃｔｉｏｎメッセージを受信した場合には（ステップＳ７１４のＹｅｓ）、ステップＳ７１５において、ノード３０は、Ｅｌｅｃｔｉｏｎメッセージの送信元のノード３０に、Ａｎｓｗｅｒメッセージを返信する。そして、ノード３０は、ステップＳ７１５の処理を終えると、処理をステップＳ７１４に戻して、ステップＳ７１４とステップＳ７１５の処理を繰り返す。

Ｅｌｅｃｔｉｏｎメッセージを受信しなかった場合（例えば、他のノード３０からＥｌｅｃｔｉｏｎメッセージを一定時間受信しなかった場合）（ステップＳ７１４のＮｏ）、ノード３０は、処理をステップＳ７１６に進める。ステップＳ７１６において、ノード３０は、他の全てのノード３０に対してＣｏｏｒｄｉｎａｔｏｒメッセージを送信して、自分が管理装置２０として機能をすることを宣言する。そして、ステップＳ７１７において、ノード３０は、管理装置２０としての動作を開始し、本フローを終了する。

複数のノード３０のそれぞれが以上の第１の処理フローを実行することにより、正常に動作している複数のノード３０のうちの最も大きいＩＤ値を有するノード３０が、管理装置２０として機能する。すなわち、複数のノード３０は、正常に動作している最も大きいＩＤ値を有するノード３０を、管理装置２０として選任することができる。

図１９から図２４は、０から５までのＩＤ値を有する６個のノード３０が、第１の処理フローを実行して管理装置２０を選任する場合の具体的な状態の遷移を示す図である。なお、図１９から図２４では、ノード３０を円で示し、円内の数値がそのノード３０のＩＤ値を示す。

まず、これまでに、ＩＤ値＝５のノード３０が管理装置２０として選任されていたが、ＩＤ値＝５のノード３０が障害により管理装置２０として機能できなくなったとする。この場合、ＩＤ値＝０からＩＤ値＝５のノード３０のそれぞれは、第１の処理フローを実行する。例えば、ＩＤ値＝０のノード３０は、第１の処理フローを実行して、図１９に示すように、自分より大きいＩＤ値を有するそれぞれのノード３０（ＩＤ値＝１、ＩＤ値＝２、ＩＤ値＝３、ＩＤ値＝４およびＩＤ値＝５のノード３０）にＥｌｅｃｔｉｏｎメッセージを送信する。

ＩＤ値＝０のノード３０からＥｌｅｃｔｉｏｎメッセージを受信したノード３０（ＩＤ値＝１、ＩＤ値＝２、ＩＤ値＝３およびＩＤ値＝４のノード３０）は、図２０に示すように、ＡｎｓｗｅｒメッセージをＩＤ値＝０のノード３０に返信する。従って、ＩＤ値＝０のノード３０は、Ａｎｓｗｅｒメッセージを受信したので、管理装置２０として機能せずに、何れかのノード３０からＣｏｏｒｄｉｎａｔｏｒメッセージを受信するまで処理を待機する。なお、ＩＤ値＝５のノード３０は、動作していないため、Ａｎｓｗｅｒメッセージを返信できない。

また、例えば、ＩＤ値＝３のノード３０は、第１の処理フローを実行して、図２１に示すように、自分より大きいＩＤ値を有するノード３０（ＩＤ値＝４およびＩＤ値＝５のノード３０）にＥｌｅｃｔｉｏｎメッセージを送信する。

ＩＤ値＝３のノード３０からＥｌｅｃｔｉｏｎメッセージを受信したノード３０（ＩＤ値＝４のノード３０）は、図２２に示すように、ＡｎｓｗｅｒメッセージをＩＤ値＝３のノード３０に返信する。従って、ＩＤ値＝３のノード３０は、Ａｎｓｗｅｒメッセージを受信したので、管理装置２０として機能せずに、何れかのノード３０からＣｏｏｒｄｉｎａｔｏｒメッセージを受信するまで処理を待機する。

同様に、例えば、ＩＤ値＝４のノード３０は、第１の処理フローを実行して、図２３に示すように、自分より大きいＩＤ値を有するノード３０（ＩＤ値＝５のノード３０）にＥｌｅｃｔｉｏｎメッセージを送信する。

これに対して、ＩＤ値＝５のノード３０は、障害が発生しており、Ａｎｓｗｅｒメッセージを返信できない。従って、ＩＤ値＝４のノード３０は、何れのノード３０からもＡｎｓｗｅｒメッセージを受信しない。そこで、ＩＤ値＝４のノード３０は、図２４に示すように、自分が選挙に勝利して管理装置２０として機能をすることを宣言するため、他の全てのノード３０にＣｏｏｄｉｎａｔｏｒメッセージを送信する。そして、ＩＤ値＝４のノード３０は、以後、管理装置２０としての動作を開始する。

以上のように、複数のノード３０は、それぞれが第１の処理フローを実行することにより、正常に動作している最も大きいＩＤ値を有するノード３０を、管理装置２０として選任することができる。

図２５は、管理装置２０を選任するための第２の処理フローを示す。複数のノード３０のそれぞれは、図１８に示した第１の処理フローに代えて、図２５に示す第２の処理フローを実行してもよい。複数のノード３０のそれぞれが第２の処理フローを実行する前提条件は、第１の処理フローと同様である。

まず、ステップＳ７２１において、ノード３０は、自分の存在を表すメッセージをブロードキャストする。このメッセージには、送信元のノード３０のＩＤ値と、送信元のノード３０の部下のノード３０のＩＤ値の集合が含まれる。

また、メッセージをブロードキャストするとともに、ノード３０は、他のノード３０からブロードキャストされたメッセージを受信する。ノード３０は、メッセージを受信する毎に、ステップＳ７２２とステップＳ７２５との間のループ処理を実行する。

ループ処理内では、ステップＳ７２３において、ノード３０は、受信したメッセージに含まれる送信元のノード３０のＩＤ値が、自分が有するＩＤ値より小さいかを判断する。受信したメッセージに含まれるＩＤ値が、自分が有するＩＤ値より小さい場合には（ステップＳ７２３のＹｅｓ）、ノード３０は、メッセージの送信元のノード３０、および、その送信元のノード３０の部下のノード３０の集合を、自分の部下に登録する。

ノード３０は、ループ処理を開始してから予め定められた期間が経過するまでは、ループ処理（ステップＳ７２２〜ステップＳ７２５の間の処理）を、メッセージを受信する毎に繰り返し実行する。そして、ノード３０は、予め定められた期間が経過した場合には、ループ処理を抜けて、処理をステップＳ７２７に進める。

なお、ノード３０は、ステップＳ７２３の判断処理において、受信したメッセージに含まれるＩＤ値が、自分のＩＤ値より小さくないと判断した場合には（ステップＳ７２３のＮｏ）、ループ処理を抜けて処理をステップＳ７２６に進める。ステップＳ７２６において、ノード３０は、これまでに自分の部下に登録しているノード３０があれば、登録を放棄する。ノード３０は、ステップＳ７２６の処理を終えると、処理をステップＳ７２７に進める。

ステップＳ７２７において、ノード３０は、登録している部下を、他のノード３０のそれぞれに通知する。そして、ノード３０は、全体のノード３０のうちの過半数以上のノード３０を、部下に登録している場合、管理装置２０としての動作を開始し、本フローを終了する。また、ノード３０は、全体のノード３０の過半数以上のノード３０を部下に登録していない場合には、管理装置２０として機能することを辞退し、本フローを終了する。

複数のノード３０のそれぞれが以上の第２の処理フローを実行することにより、正常に動作している複数のノード３０のうちの最も大きいＩＤ値を有するノード３０が、管理装置２０として機能する。すなわち、複数のノード３０は、正常に動作している最も大きいＩＤ値を有するノード３０を、管理装置２０として選任することができる。

図２６から図３０は、０から５までのＩＤ値を有する６個のノード３０が、第２の処理フローを実行して管理装置２０を選任する場合の具体的な状態の遷移を示す図である。なお、図２６から図３０では、ノード３０を円で示し、円内の数値がそのノード３０のＩＤ値を示す。

まず、これまでに、ＩＤ値＝５のノード３０が管理装置２０として選任されていたが、ＩＤ値＝５のノード３０が障害により管理装置２０として機能できなくなったとする。そして、この場合、ＩＤ値＝０〜ＩＤ値＝４のそれぞれのノード３０は、第２の処理フローの実行を開始する。

ＩＤ値＝０のノード３０は、図２６に示すように、メッセージをブロードキャストする。ＩＤ値＝１、２、３、４のノード３０のそれぞれは、ＩＤ値＝０のノード３０からメッセージを受信する。この場合、ＩＤ値＝１、２、３、４のノード３０のそれぞれは、ＩＤ値＝０のノード３０を部下に登録する。

続いて、ＩＤ値＝１のノード３０は、図２７に示すように、メッセージをブロードキャストする。ＩＤ値＝０、２、３、４のノード３０のそれぞれは、ＩＤ値＝１のノード３０からメッセージを受信する。この場合、ＩＤ値＝２、３、４のノード３０のそれぞれは、ＩＤ値＝１のノード３０を部下に追加登録する。これに対して、ＩＤ値＝０のノード３０は、部下を放棄し、以後、メッセージを受信しても部下を登録しない。

続いて、ＩＤ値＝２のノード３０は、図２８に示すように、メッセージをブロードキャストする。ＩＤ値＝０、１、３、４のノード３０のそれぞれは、ＩＤ値＝２のノード３０からメッセージを受信する。この場合、ＩＤ値＝３、４のノード３０のそれぞれは、ＩＤ値＝２のノード３０を部下に追加登録する。これに対して、ＩＤ値＝１のノード３０は、部下を放棄し、以後、メッセージを受信しても部下を登録しない。

続いて、ＩＤ値＝３のノード３０は、図２９に示すように、メッセージをブロードキャストする。ＩＤ値＝０、１、２、４のノード３０のそれぞれは、ＩＤ値＝３のノード３０からメッセージを受信する。この場合、ＩＤ値＝４のノード３０は、ＩＤ値＝３のノード３０を部下に追加登録する。これに対して、ＩＤ値＝２のノード３０は、部下を放棄し、以後、メッセージを受信しても部下を登録しない。

続いて、ＩＤ値＝４のノード３０は、図３０に示すように、メッセージをブロードキャストする。ＩＤ値＝０、１、２、３のノード３０のそれぞれは、ＩＤ値＝４のノード３０からメッセージを受信する。この場合、ＩＤ値＝３のノード３０は、部下を放棄し、以後、メッセージを受信しても部下を登録しない。

以上の処理により、ＩＤ値＝４のノード３０が、過半数の部下を登録する。この結果、ＩＤ値＝４のノード３０が、管理装置２０として動作を開始する。

以上のように、複数のノード３０は、それぞれが第２の処理フローを実行することにより、正常に動作している最も大きいＩＤ値を有するノード３０を、管理装置２０として選任することができる。なお、複数のノード３０のそれぞれは、以上の処理フローに限らず、他のアルゴリズムに従って管理装置２０として機能するノード３０を選任してもよい。

図３１〜図３７を参照して、データベースシステム１０の動作例を説明する。図３１は、３つのパーティション＃１〜＃３のそれぞれに対して、オーナーおよびバックアップとなるノード３０を割り当てた場合の、ノード３０−Ａからノード３０−Ｃのそれぞれの状態を示す図である。

本例では、図３１の現役割表に示されるように、パーティション＃１に対して、オーナーにノード３０−Ａが割り当てられ、バックアップにノード３０−Ｂが割り当てられる。また、パーティション＃２に対して、オーナーにノード３０−Ｂが割り当てられ、バックアップにノード３０−Ｃが割り当てられる。また、パーティション＃３に対して、オーナーにノード３０−Ｃが割り当てられ、バックアップにノード３０−Ａが割り当てられる。

ノード３０−Ａおよびノード３０−Ｂは、パーティション＃１に対するレプリケーション処理をトランザクションにより実行している。この結果、図３１のデータ保持表に示されるように、パーティション＃１のタイムスタンプは、ノード３０−Ａおよびノード３０−Ｂで同一値となる。

また、ノード３０−Ｂおよびノード３０−Ｃは、パーティション＃２に対するレプリケーション処理をトランザクションにより実行している。この結果、図３１のデータ保持表に示されるように、パーティション＃２のタイムスタンプは、ノード３０−Ｂおよびノード３０−Ｃで同一値となる。

また、ノード３０−Ｃおよびノード３０−Ａは、パーティション＃３に対するレプリケーション処理をトランザクションにより実行している。この結果、図３１のデータ保持表に示されるように、パーティション＃３のタイムスタンプは、ノード３０−Ｃおよびノード３０−Ａで同一値となる。

図３２は、図３１の状態からノード３０−Ｃに障害が発生したことに応じて短期同期処理を実行した後の、ノード３０−Ａからノード３０−Ｃのそれぞれの状態を示す図である。管理装置２０のクラスタ管理部２４は、図３１の状態からノード３０−Ｃからデータ保持表を検出することができず、ノード３０−Ｃに障害が発生したことを検出したとする。

複数のノード３０のうちの何れかのノード３０で障害が発生した場合、管理装置２０のクラスタ管理部２４は、障害が発生したノード３０を切り離すとともに、第１割当部２２に次役割表を計算させる。

クラスタ管理部２４からの呼び出しに応じて、第１割当部２２は、障害の発生したノード３０を除いてオーナーおよびバックアップとなるノード３０を再度割り当てて、次役割表を生成する。この場合に、第１割当部２２は、少なくともデータベースを機能させるべく、複数のパーティションのそれぞれに対して少なくともオーナーが存在するようにノード３０を割り当てる。例えば、第１割当部２２は、オーナーであったノード３０に障害が発生した場合には、バックアップであったノード３０をオーナーに割り当てる。さらに、第１割当部２２は、よりデータベースの冗長度を高めるべく、複数のパーティションのそれぞれに対して可能な限りバックアップが存在するようにノード３０を割り当てる。

本例では、再割り当ての結果、図３２の次役割表に示されるように、パーティション＃１に対して、オーナーにノード３０−Ａが割り当てられ、バックアップにノード３０−Ｂが割り当てられる。また、パーティション＃２に対して、オーナーにノード３０−Ｂが割り当てられる。また、パーティション＃３に対して、オーナーにノード３０−Ａが割り当てられる。

そして、クラスタ管理部２４は、次役割表をノード３０−Ａおよびノード３０−Ｂに配布する。ノード３０−Ａおよびノード３０−Ｂのそれぞれのノード管理部３４は、次役割表を受信すると短期同期処理を実行するとともに、現役割表の内容を次役割表の内容に書き換える。これにより、ノード３０−Ａおよびノード３０−Ｂのそれぞれは、新たに割り当てられた役割に応じた処理を実行することができる。

図３３は、図３２の状態から実行される長期同期処理の一例を示す図である。また、管理装置２０のクラスタ管理部２４は、障害が発生したノード３０−Ｃを切り離した場合、第２割当部２３に目標役割表を計算させる。

クラスタ管理部２４からの呼び出しに応じて、第２割当部２３は、障害が発生したノード３０を除いてバックアップの候補となるノード３０を再度割り当てて、目標役割表を生成する。この場合に、第２割当部２３は、データベースの冗長度を高めるべく、複数のパーティションのそれぞれに対して、少なくともオーナーおよびバックアップが存在するように候補となるノード３０を割り当てる。

図３２の状態では、パーティション＃２およびパーティション＃３に対するバックアップのノード３０が存在しない。従って、第２割当部２３は、パーティション＃２に対するバックアップの候補としてノード３０−Ａを割り当て、パーティション＃３に対するバックアップの候補としてノード３０−Ｂを割り当てる。

なお、本例では、第２割当部２３は、現役割表により既にオーナーおよびバックアップとして割り当てられているノード３０も、バックアップの候補として割り当てる。このため、図３３の目標役割表に示されるように、パーティション＃１〜＃３のそれぞれに対して、ノード３０−Ａおよびノード３０−Ｂの両者がバックアップの候補として割り当てられる。

そして、クラスタ管理部２４は、目標役割表をノード３０−Ａおよびノード３０−Ｂに配布する。ノード３０−Ａおよびノード３０−Ｂのそれぞれの転送部３５は、現役割表と目標役割表の差の部分に対して長期同期処理を実行する。すなわち、ノード３０−Ｂの転送部３５は、パーティション＃２のデータ集合をバックグラウンドでノード３０−Ａに送信する。また、ノード３０−Ａの転送部３５は、パーティション＃３のデータ集合をバックグラウンドでノード３０−Ｂに送信する。

なお、このとき、転送部３５は、クライアントからのアクセス要求に対する処理を中断させずに、長期同期処理を実行する。

長期同期処理が完了すると、ノード３０−Ａは、パーティション＃２のデータ集合のレプリカを記憶することができる。さらに、図３３のデータ保持表に示されるように、このときのパーティション＃２のタイムスタンプは、ノード３０−Ａおよびノード３０−Ｂで同一値となる。

また、ノード３０−Ｂは、パーティション＃３のデータ集合のレプリカを記憶することができる。さらに、図３３のデータ保持表に示されるように、パーティション＃３のタイムスタンプは、ノード３０−Ａおよびノード３０−Ｂで同一値となる。

図３４は、図３３の長期同期処理が完了したことに応じて短期同期処理を実行した後の、ノード３０−Ａからノード３０−Ｃのそれぞれの状態を示す図である。管理装置２０のクラスタ管理部２４は、定期的に第１割当部２２を呼び出して次役割表を計算させる。

長期同期処理が完了した後にクラスタ管理部２４から呼び出された場合、第１割当部２２は、複数のパーティションのそれぞれに対して、長期同期処理により生成されたレプリカを利用してより冗長度が高まるように、オーナーおよびバックアップとなるノード３０を再度割り当てる。

本例では、図３４の次役割表に示されるように、パーティション＃１に対して、オーナーとしてノード３０−Ａが割り当てられ、バックアップとしてノード３０−Ｂが割り当てられる。また、パーティション＃２に対して、オーナーとしてノード３０−Ｂが割り当てられ、バックアップとしてノード３０−Ａが割り当てられる。また、パーティション＃３に対して、オーナーとしてノード３０−Ａが割り当てられ、バックアップとしてノード３０−Ｂが割り当てられる。

そして、クラスタ管理部２４は、次役割表をノード３０−Ａおよびノード３０−Ｂに配布する。ノード３０−Ａおよびノード３０−Ｂのそれぞれのノード管理部３４は、次役割表を受信すると短期同期処理を実行するとともに、現役割表の内容を次役割表の内容に書き換える。これにより、ノード３０−Ａおよびノード３０−Ｂのそれぞれは、新たに割り当てられた役割に応じた処理を実行することができる。

図３５は、図３４の状態からノード３０−Ｄを追加した場合の、ノード３０−Ａからノード３０−Ｄのそれぞれの状態を示す図である。管理装置２０のクラスタ管理部２４は、例えば図３４の状態からノード３０−Ｄが新たに追加されたことを検出したとする。

クラスタ管理部２４は、図３５のデータ保持表に示されるように、ノード３０−Ｄを追加したデータ保持表を生成する。第１割当部２２は、データ保持表にノード３０−Ｄが追加されたことに応じて、ノード３０−Ｄが追加された次役割表を生成する。

もっとも、ノード３０−Ｄは、データ集合を記憶していない。従って、第１割当部２２は、ノード３０−Ｄが追加された直後では、オーナーおよびバックアップの割り当てを変更しない。

図３６は、図３５の状態から実行される長期同期処理の一例を示す図である。新たなノード３０が追加された場合、第２割当部２３は、複数のパーティションのそれぞれに対して、新たなノード３０を含めてバックアップの候補となるノード３０を再度割り当てる。この場合、第２割当部２３は、割り当てられたオーナーおよびバックアップの数の差がノード３０間で予め定められた値の範囲内となるように、複数のパーティションのそれぞれに対して、バックアップの候補となるノード３０を割り当てる。

本例では、再割り当ての結果、図３６の目標役割表に示されるように、パーティション＃１に対して、ノード３０−Ａおよびノード３０−Ｂがバックアップの候補として割り当てられる。また、パーティション＃２に対して、ノード３０−Ｂおよびノード３０−Ｄがバックアップの候補として割り当てられる。また、パーティション＃３に対して、ノード３０−Ａおよびノード３０−Ｄがバックアップの候補として割り当てられる。

そして、クラスタ管理部２４は、目標役割表をノード３０−Ａ、ノード３０−Ｂおよびノード３０−Ｄに配布する。ノード３０−Ａ、ノード３０−Ｂおよびノード３０−Ｄのそれぞれの転送部３５は、現役割表と目標役割表の差の部分に対して長期同期処理を実行する。

すなわち、ノード３０−Ｂの転送部３５は、パーティション＃２のデータ集合をバックグラウンドでノード３０−Ｄに送信する。また、ノード３０−Ａの転送部３５は、パーティション＃３のデータ集合をバックグラウンドでノード３０−Ｄに送信する。なお、このとき、転送部３５は、クライアントからのアクセス要求に対する処理を中断せずに長期同期処理を実行する。

この結果、ノード３０−Ｄは、パーティション＃２のデータ集合のレプリカを記憶することができる。さらに、図３６のデータ保持表に示されるように、パーティション＃２のタイムスタンプは、ノード３０−Ｂおよびノード３０−Ｄで同一値となる。

また、ノード３０−Ｄは、パーティション＃３のデータ集合のレプリカを記憶することができる。さらに、図３６のデータ保持表に示されるように、パーティション＃３のタイムスタンプは、ノード３０−Ａおよびノード３０−Ｄで同一値となる。

図３７は、図３６の長期同期処理が完了したことに応じて短期同期処理を実行した後の、ノード３０−Ａからノード３０−Ｄのそれぞれの状態を示す図である。長期同期処理が完了した後にクラスタ管理部２４から呼び出された場合、第１割当部２２は、複数のパーティションのそれぞれに対して、長期同期処理により生成されたレプリカを利用してよりノード３０間の負荷が均等となるように、オーナーおよびバックアップとなるノード３０を再度割り当てる。

本例では、再割り当ての結果、図３７の次役割表に示されるように、パーティション＃１に対して、オーナーとしてノード３０−Ａが割り当てられ、バックアップとしてノード３０−Ｂが割り当てられる。また、パーティション＃２に対して、オーナーとしてノード３０−Ｂが割り当てられ、バックアップとしてノード３０−Ｄが割り当てられる。また、パーティション＃３に対して、オーナーとしてノード３０−Ａが割り当てられ、バックアップとしてノード３０−Ｄが割り当てられる。

そして、クラスタ管理部２４は、次役割表をノード３０−Ａ、ノード３０−Ｂおよびノード３０−Ｄに配布する。ノード３０−Ａ、ノード３０−Ｂおよびノード３０−Ｄのそれぞれのノード管理部３４は、次役割表を受信すると短期同期処理を実行するとともに、現役割表の内容を次役割表の内容に書き換える。これにより、ノード３０−Ａ、ノード３０−Ｂおよびノード３０−Ｄのそれぞれは、新たに割り当てられた役割に応じた処理を実行することができる。

以上のように、本実施形態に係るデータベースシステム１０によれば、バックアップの候補となるノード３０を割り当ててオーナーとなるノード３０から候補となるノード３０へとデータ集合の転送をするので、データベースに冗長度を持たせ且つノード３０の処理の負荷を均等することができる。さらに、データベースシステム１０によれば、このような処理をクライアントからのアクセス要求に対する処理を中断させずに実行することができるので、ノード３０を切り離したりノード３０を新たに追加したりした場合にも、システムを停止させずにデータの再配置をすることができる。

また、本実施形態の管理装置２０およびノード３０で実行されるプログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。

また、本実施形態の管理装置２０およびノード３０で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施形態の管理装置２０およびノード３０で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。

また、本実施形態の管理装置２０およびノード３０プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。

本実施形態の管理装置２０で実行されるプログラムは、上述した各部（表記憶部２１、第１割当部２２、第２割当部２３およびクラスタ管理部２４）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ（プロセッサ）が上記記憶媒体からプログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、表記憶部２１、第１割当部２２、第２割当部２３およびクラスタ管理部２４が主記憶装置上に生成されるようになっている。

また、本実施形態のノード３０で実行されるプログラムは、上述した各部（データストア部３１、表記憶部３２、アクセス処理部３３、ノード管理部３４および転送部３５）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ（プロセッサ）が上記記憶媒体からプログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、データストア部３１、表記憶部３２、アクセス処理部３３、ノード管理部３４および転送部３５が主記憶装置上に生成されるようになっている。

本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。

１０ データベースシステム
１２ ＣＰＵ
１３ メモリ
１４ 通信Ｉ／Ｆ
１５ ストレージＩ／Ｆ
１６ 外部記憶装置
２０ 管理装置
２１ 表記憶部
２２ 第１割当部
２３ 第２割当部
２４ クラスタ管理部
３０ ノード
３１ データストア部
３２ 表記憶部
３３ アクセス処理部
３４ ノード管理部
３５ 転送部

Claims (6)

1. データベースを記憶する複数のノードを備えるデータベースシステムであって、
   前記複数のノードは、互いに通信をして何れか１つのノードを管理装置として選任し、
   前記管理装置は、
   前記複数のノードのそれぞれの状況の変更に応じて、データ集合を記憶して前記データ集合へのアクセス要求を受け付ける第１ノード、および、前記データ集合を記憶して前記第１ノードのバックアップとなる第２ノードを割り当てて、前記複数のノードのそれぞれに割り当てに応じた動作を指示する第１割当部と、
   前記複数のノードの状況と、前記第１ノードおよび前記第２ノードの割り当て状況の変更に応じて、前記第１ノードまたは前記第２ノードの候補となる第３ノードを割り当てて、前記複数のノードのそれぞれに対して、前記第３ノードに前記第１ノードまたは前記第２ノードとして動作させるための準備を指示する第２割当部と、
   を有し、
   前記複数のノードのそれぞれは、
   前記第１ノードまたは前記第２ノードのデータ集合を、前記第３ノードに送信する転送部、
   を有する
   データベースシステム。
2. 前記複数のノードは、前記データベースを複数のパーティションに分割して記憶し、
   前記第１割当部は、前記複数のパーティションのそれぞれに対して、前記第１ノードおよび前記第２ノードを割り当て、
   前記第２割当部は、前記複数のパーティションのそれぞれに対して、前記第３ノードを割り当てる
   請求項１に記載のデータベースシステム。
3. 前記第１割当部は、複数のパーティションのそれぞれに対して、前記複数のノードのそれぞれが前記第１ノードか前記第２ノードかを示す第１テーブルを生成し、前記第１テーブルを前記複数のノードのそれぞれに配布することにより割り当てに応じた動作を指示し、
   前記第２割当部は、複数のパーティションのそれぞれに対して、前記複数のノードのそれぞれが前記第３ノードかを示す第２テーブルを生成し、前記第２テーブルを前記複数のノードのそれぞれに配布することにより前記準備を指示する
   請求項２に記載のデータベースシステム。
4. 請求項１に記載のデータベースシステムに備えられるノード。
5. 請求項１に記載のデータベースシステムに備えられるノードとしてコンピュータを機能させるためのプログラム。
6. データベースを記憶する複数のノードを備えるデータベースシステムにおけるデータ処理方法であって、
   前記複数のノードが、互いに通信をして何れか１つのノードを管理装置として選任するステップを実行し、
   前記管理装置が、
   前記複数のノードのそれぞれの状況の変更に応じて、データ集合を記憶して前記データ集合へのアクセス要求を受け付ける第１ノード、および、前記データ集合を記憶して前記第１ノードのバックアップとなる第２ノードを割り当てて、前記複数のノードのそれぞれに割り当てに応じた動作を指示する第１割当ステップと、
   前記複数のノードの状況と、前記第１ノードおよび前記第２ノードの割り当て状況の変更に応じて、前記第１ノードまたは前記第２ノードの候補となる第３ノードを割り当てて、前記複数のノードのそれぞれに対して、前記第３ノードに前記第１ノードまたは前記第２ノードとして動作させるための準備を指示する第２割当ステップと、
   を実行し、
   前記複数のノードのそれぞれが、前記第１ノードまたは前記第２ノードのデータ集合を、前記第３ノードに送信する転送ステップを実行する
   データ処理方法。

Images