(57)【特許請求の範囲】
【請求項１】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムであって、
各前記データ管理装置は、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、
前記レプリカは、
新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、
前記議題内容を作成する議題内容作成部と、
前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、
前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、
を備え、
前記新しいマスタに選定されたレプリカ以外のデータ管理装置は、
前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、
受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より小さい場合、受信した前記情報に対する否定の応答を前記新しいマスタに選定されたレプリカに返信する、または、受信した前記情報を破棄する否定処理部と、
を備える
ことを特徴とする分散データ管理システム。
【請求項２】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムであって、
各前記データ管理装置は、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、
前記レプリカは、
新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、
前記議題内容を作成する議題内容作成部と、
前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、
前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、
を備え、
前記新しいマスタに選定されたレプリカ以外のデータ管理装置は、
前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、
受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号に等しい場合、受信した前記情報に含まれる議題番号と前記記憶部に記憶される議題番号とを比較し、受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号以下のとき、受信した前記情報に含まれる議題番号と議題内容とを記憶する更新処理部、および受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号より大きいとき、前記記憶部において前記受信した前記情報に含まれる議題番号より小さい範囲の議題番号の中で欠番の議題番号に関連付けられた議題内容の再送を前記新しいマスタに選定されたレプリカに要求する再送要求処理部と、
を備える
ことを特徴とする分散データ管理システム。
【請求項３】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムであって、
各前記データ管理装置は、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、
前記レプリカは、
新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、
前記議題内容を作成する議題内容作成部と、
前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、
前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、
を備え、
前記新しいマスタに選定されたレプリカ以外のデータ管理装置は、
前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、
受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より大きい場合、受信した前記情報に含まれる前記選定時議題番号より大きい議題番号の議題内容の取得要求である問い合わせ通知を、自身以外のデータ管理装置に送信し、前記自身以外のデータ管理装置から前記問い合わせ通知に対する応答として、前記選定時議題番号より大きい議題番号の議題内容およびその議題内容の議題番号を受信し、当該受信した応答に含まれる議題内容とその議題内容に付けられた議題番号とを前記記憶部に記憶し、前記記憶部に記憶しているマスタ世代番号を受信した前記情報に含まれるマスタ世代番号に更新する補正処理部と、
を備える
ことを特徴とする分散データ管理システム。
【請求項４】
前記新しいマスタに選定されたレプリカ以外のデータ管理装置の補正処理部は、
前記問い合わせ通知に対する応答に含まれる議題内容とその議題内容に付けられた前記選定時議題番号より大きい議題番号とを前記記憶部に記憶する場合、
前記応答に含まれる議題内容と、その議題内容に付けられた前記選定時議題番号より大きい議題番号と同一の議題番号に付けられた、既に前記記憶部に記憶している議題内容とが異なる場合、当該記憶している議題内容を、前記応答に含まれる議題内容で上書きする
ことを特徴とする請求項３に記載の分散データ管理システム。
【請求項５】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理装置であって、
議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部と、
自身がレプリカから新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、
前記議題内容を作成する議題内容作成部と、
前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、
前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、
前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、
受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より小さい場合、受信した前記情報に対する否定の応答を前記新しいマスタに選定されたレプリカに返信する、または、受信した前記情報を破棄する否定処理部と、
を備える
ことを特徴とするデータ管理装置。
【請求項６】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理装置であって、
議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部と、
自身がレプリカから新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、
前記議題内容を作成する議題内容作成部と、
前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、
前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、
前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、
受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号に等しい場合、受信した前記情報に含まれる議題番号と前記記憶部に記憶される議題番号とを比較し、受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号以下のとき、受信した前記情報に含まれる議題番号と議題内容とを記憶する更新処理部、および受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号より大きいとき、前記記憶部において前記受信した前記情報に含まれる議題番号より小さい範囲の議題番号の中で欠番の議題番号に関連付けられた議題内容の再送を前記新しいマスタに選定されたレプリカに要求する再送要求処理部と、
を備える
ことを特徴とするデータ管理装置。
【請求項７】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理装置であって、
議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部と、
自身がレプリカから新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、
前記議題内容を作成する議題内容作成部と、
前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、
前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、
前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、
受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より大きい場合、受信した前記情報に含まれる前記選定時議題番号より大きい議題番号の議題内容の取得要求である問い合わせ通知を、自身以外のデータ管理装置に送信し、前記自身以外のデータ管理装置から前記問い合わせ通知に対する応答として、前記選定時議題番号より大きい議題番号の議題内容およびその議題内容の議題番号を受信し、当該受信した応答に含まれる議題内容とその議題内容に付けられた議題番号とを前記記憶部に記憶し、前記記憶部に記憶しているマスタ世代番号を受信した前記情報に含まれるマスタ世代番号に更新する補正処理部と、
を備える
ことを特徴とするデータ管理装置。
【請求項８】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理方法であって、
各前記データ管理装置は、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、
前記レプリカは、
新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理、
前記議題内容を作成する議題内容作成処理、
前記議題内容作成処理において新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理、および、
前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理、
を実行し、
前記新しいマスタに選定されたレプリカ以外のデータ管理装置は、
前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理、および、
受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より小さい場合、受信した前記情報に対する否定の応答を前記新しいマスタに選定されたレプリカに返信する、または、受信した前記情報を破棄する否定処理、
を実行する
ことを特徴とするデータ管理方法。
【請求項９】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理方法であって、
各前記データ管理装置は、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、
前記レプリカは、
新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理、
前記議題内容を作成する議題内容作成処理、
前記議題内容作成処理において新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理、および、
前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理、
を実行し、
前記新しいマスタに選定されたレプリカ以外のデータ管理装置は、
前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理、および、
受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号に等しい場合、受信した前記情報に含まれる議題番号と前記記憶部に記憶される議題番号とを比較し、受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号以下のとき、受信した前記情報に含まれる議題番号と議題内容とを記憶する更新処理および受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号より大きいとき、前記記憶部において前記受信した前記情報に含まれる議題番号より小さい範囲の議題番号の中で欠番の議題番号に関連付けられた議題内容の再送を前記新しいマスタに選定されたレプリカに要求する再送要求処理、
を実行する
ことを特徴とするデータ管理方法。
【請求項１０】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理方法であって、
各前記データ管理装置は、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、
前記レプリカは、
新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理、
前記議題内容を作成する議題内容作成処理、
前記議題内容作成処理において新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理、および、
前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理、
を実行し、
前記新しいマスタに選定されたレプリカ以外のデータ管理装置は、
前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理、および、
受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より大きい場合、受信した前記情報に含まれる前記選定時議題番号より大きい議題番号の議題内容の取得要求である問い合わせ通知を、自身以外のデータ管理装置に送信し、前記自身以外のデータ管理装置から前記問い合わせ通知に対する応答として、前記選定時議題番号より大きい議題番号の議題内容およびその議題内容の議題番号を受信し、当該受信した応答に含まれる議題内容とその議題内容に付けられた議題番号とを前記記憶部に記憶し、前記記憶部に記憶しているマスタ世代番号を受信した前記情報に含まれるマスタ世代番号に更新する補正処理、
を実行する
ことを特徴とするデータ管理方法。
【請求項１１】
前記新しいマスタに選定されたレプリカ以外のデータ管理装置は、前記補正処理において、
前記問い合わせ通知に対する応答に含まれる議題内容とその議題内容に付けられた前記選定時議題番号より大きい議題番号とを前記記憶部に記憶する場合、
前記応答に含まれる議題内容と、その議題内容に付けられた前記選定時議題番号より大きい議題番号と同一の議題番号に付けられた、既に前記記憶部に記憶している議題内容とが異なる場合、当該記憶している議題内容を、前記応答に含まれる議題内容で上書きする
ことを特徴とする請求項１０に記載のデータ管理方法
【請求項１２】
請求項８ないし請求項１１のいずれか一項に記載のデータ管理方法を、コンピュータとしてのデータ管理装置に実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のデータ管理装置によって構成され、１台がマスタ、残りのデータ管理装置がマスタと同じデータの状態を保持するレプリカとして動作する分散データ管理システムにおいて、マルチマスタ（複数のマスタが存在する）状態になったときに、新しく選定されたマスタからの情報に基づいて、すべてのデータ管理装置のデータを同じ状態に保持させる技術に関する。
【背景技術】
【０００２】
複数のデータ管理装置の中からマスタを１台選定する手法、または、データ管理装置の保持するデータの状態を同じに揃える手法として、分散調停プロトコルがある。分散調停プロトコルとして、例えば、データベースやファイルシステムに用いられるＰＡＸＯＳのアルゴリズムが知られている（非特許文献１参照）。ＰＡＸＯＳのアルゴリズムを実用に供する場合、ユーザからデータの更新や参照のためにアクセスされるデータ管理装置を１台決定しておき、それをマスタと呼び、マスタ以外のデータ管理装置をレプリカとすることが、一般的に行われている。なお、マスタは、ユーザの処理要求（データの更新または参照に係る要求）を受け付けるとともに、その処理要求に対して応答する。そして、マスタは、マスタにおいて実行されたデータの更新時に用いた更新差分情報をレプリカに送信して、マスタのデータとレプリカのデータとを同じ状態にする。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】L. Lamport，“The part-time parliament”，ACM Transactions on Computer System(TOCS)，Vol.16，Issue 2，1998年5月，p.133-169
【発明の概要】
【発明が解決しようとする課題】
【０００４】
前記したように、ＰＡＸＯＳのアルゴリズムを用いることによって、マスタまたはネットワークに障害が発生したときに、レプリカの中から新しいマスタを選定することができる。例えば、レプリカが新しいマスタの設定を開始するトリガは、マスタから一定周期で出力される自身の生存を示すリースパケットを、レプリカがリースタイム時間以内に受信できなくなったときである。しかし、マスタが正常に動作していても、例えば、ネットワークに障害が発生した場合には、レプリカがリースパケットを受信できないことがある。そして、新しいマスタが選定された後にネットワークが正常に戻った場合、マスタが２つ存在すること（マルチマスタ状態）になってしまう可能性がある。そして、２つのマスタからレプリカに対してデータの更新が実行された場合、２つのマスタから送信された更新差分情報のうち、どちらが先に取得されるかによって、データの状態の整合性が損なわれるという問題が発生する。
【０００５】
そこで、本発明の課題は、前記した問題を解決するために、複数のデータ管理装置によって構成され、１台がマスタ、残りのデータ管理装置がマスタと同じデータの状態を保持するレプリカとして動作する分散データ管理システムにおいて、データ管理装置間を接続するネットワークに障害が発生してマルチマスタ状態になったときに、新しく選定されたマスタからの情報に基づいて、すべてのデータ管理装置のデータを同じ状態に維持させる技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
前記課題を解決するために、本発明は、複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムであって、各前記データ管理装置が、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、前記レプリカが、新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、前記議題内容を作成する議題内容作成部と、前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、を備え、前記新しいマスタに選定されたレプリカ以外のデータ管理装置が、前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より小さい場合、受信した前記情報に対する否定の応答を前記新しいマスタに選定されたレプリカに返信する、または、受信した前記情報を破棄する否定処理部と、を備えることを特徴とする。
【０００７】
また、本発明は、複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムであって、各前記データ管理装置が、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、前記レプリカが、新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、前記議題内容を作成する議題内容作成部と、前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、を備え、前記新しいマスタに選定されたレプリカ以外のデータ管理装置が、前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号に等しい場合、受信した前記情報に含まれる議題番号と前記記憶部に記憶される議題番号とを比較し、受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号以下のとき、受信した前記情報に含まれる議題番号と議題内容とを記憶する更新処理部、および受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号より大きいとき、前記記憶部において前記受信した前記情報に含まれる議題番号より小さい範囲の議題番号の中で欠番の議題番号に関連付けられた議題内容の再送を前記新しいマスタに選定されたレプリカに要求する再送要求処理部と、を備えることを特徴とする。
【０００８】
また、本発明は、複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムであって、各前記データ管理装置が、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、前記レプリカが、新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、前記議題内容を作成する議題内容作成部と、前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、を備え、前記新しいマスタに選定されたレプリカ以外のデータ管理装置が、前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より大きい場合、受信した前記情報に含まれる前記選定時議題番号より大きい議題番号の議題内容の取得要求である問い合わせ通知を、自身以外のデータ管理装置に送信し、前記自身以外のデータ管理装置から前記問い合わせ通知に対する応答として、前記選定時議題番号より大きい議題番号の議題内容およびその議題内容の議題番号を受信し、当該受信した応答に含まれる議題内容とその議題内容に付けられた議題番号とを前記記憶部に記憶し、前記記憶部に記憶しているマスタ世代番号を受信した前記情報に含まれるマスタ世代番号に更新する補正処理部と、を備えることを特徴とする。
【０００９】
また、本発明は、複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理装置であって、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部と、自身がレプリカから新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、前記議題内容を作成する議題内容作成部と、前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より小さい場合、受信した前記情報に対する否定の応答を前記新しいマスタに選定されたレプリカに返信する、または、受信した前記情報を破棄する否定処理部と、を備えることを特徴とする。
【００１０】
また、本発明は、複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理装置であって、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部と、自身がレプリカから新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、前記議題内容を作成する議題内容作成部と、前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号に等しい場合、受信した前記情報に含まれる議題番号と前記記憶部に記憶される議題番号とを比較し、受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号以下のとき、受信した前記情報に含まれる議題番号と議題内容とを記憶する更新処理部、および受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号より大きいとき、前記記憶部において前記受信した前記情報に含まれる議題番号より小さい範囲の議題番号の中で欠番の議題番号に関連付けられた議題内容の再送を前記新しいマスタに選定されたレプリカに要求する再送要求処理部と、を備えることを特徴とする。
【００１１】
また、本発明は、複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理装置であって、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部と、自身がレプリカから新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理部と、前記議題内容を作成する議題内容作成部と、前記議題内容作成部によって新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理部と、前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理部と、前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理部と、受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より大きい場合、受信した前記情報に含まれる前記選定時議題番号より大きい議題番号の議題内容の取得要求である問い合わせ通知を、自身以外のデータ管理装置に送信し、前記自身以外のデータ管理装置から前記問い合わせ通知に対する応答として、前記選定時議題番号より大きい議題番号の議題内容およびその議題内容の議題番号を受信し、当該受信した応答に含まれる議題内容とその議題内容に付けられた議題番号とを前記記憶部に記憶し、前記記憶部に記憶しているマスタ世代番号を受信した前記情報に含まれるマスタ世代番号に更新する補正処理部と、を備えることを特徴とする。
【００１２】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理方法であって、各前記データ管理装置が、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、前記レプリカが、新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理、前記議題内容を作成する議題内容作成処理、前記議題内容作成処理において新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理、および、前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理、を実行し、前記新しいマスタに選定されたレプリカ以外のデータ管理装置が、前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理、および、受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より小さい場合、受信した前記情報に対する否定の応答を前記新しいマスタに選定されたレプリカに返信する、または、受信した前記情報を破棄する否定処理、を実行することを特徴とする。
【００１３】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理方法であって、各前記データ管理装置が、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、前記レプリカが、新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理、前記議題内容を作成する議題内容作成処理、前記議題内容作成処理において新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理、および、前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理、を実行し、前記新しいマスタに選定されたレプリカ以外のデータ管理装置が、前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理、および、受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号に等しい場合、受信した前記情報に含まれる議題番号と前記記憶部に記憶される議題番号とを比較し、受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号以下のとき、受信した前記情報に含まれる議題番号と議題内容とを記憶する更新処理および受信した前記情報に含まれる議題番号が前記記憶部に記憶される議題番号より大きいとき、前記記憶部において前記受信した前記情報に含まれる議題番号より小さい範囲の議題番号の中で欠番の議題番号に関連付けられた議題内容の再送を前記新しいマスタに選定されたレプリカに要求する再送要求処理、を実行することを特徴とする。
【００１４】
複数のデータ管理装置がネットワークを介して相互に通信可能に接続され、前記データ管理装置の中の１台をマスタとし、前記マスタ以外の他のデータ管理装置をマスタと同じデータを保持するレプリカとして動作させる分散データ管理システムにおいて用いられるデータ管理方法であって、各前記データ管理装置が、議題番号と前記議題番号に関連付けられた議題内容と前記マスタのマスタ世代番号と前記マスタを選定したときの議題内容に付けられた議題番号である選定時議題番号とを記憶する記憶部を備えており、前記レプリカが、新しいマスタに選定されたときに、前記記憶部に記憶されたマスタ世代番号を増加するように更新するマスタ世代番号更新処理、前記議題内容を作成する議題内容作成処理、前記議題内容作成処理において新たに作成された議題内容に対して、議題番号を増加するように更新する議題番号更新処理、および、前記更新された議題番号、当該議題番号に関連付けられた議題内容、前記更新されたマスタ世代番号、および前記選定時議題番号を含む情報を、新しいマスタに選定されたレプリカ以外のデータ管理装置に送信する送信処理、を実行し、前記新しいマスタに選定されたレプリカ以外のデータ管理装置が、前記新しいマスタに選定されたレプリカから受信した前記情報に含まれるマスタ世代番号と、前記記憶部に記憶されるマスタ世代番号とを比較する比較処理、および、受信した前記情報に含まれるマスタ世代番号が前記記憶部に記憶されるマスタ世代番号より大きい場合、受信した前記情報に含まれる前記選定時議題番号より大きい議題番号の議題内容の取得要求である問い合わせ通知を、自身以外のデータ管理装置に送信し、前記自身以外のデータ管理装置から前記問い合わせ通知に対する応答として、前記選定時議題番号より大きい議題番号の議題内容およびその議題内容の議題番号を受信し、当該受信した応答に含まれる議題内容とその議題内容に付けられた議題番号とを前記記憶部に記憶し、前記記憶部に記憶しているマスタ世代番号を受信した前記情報に含まれるマスタ世代番号に更新する補正処理、を実行することを特徴とする。
【００１５】
このような構成によれば、新しいマスタとその新しいマスタと競合状態にある旧マスタとが双方ともマスタとして動作するマルチマスタ状態では、新しいマスタがレプリカの中から選定された場合には、新しいマスタは、新しいマスタに選定されたときに、記憶部に記憶されたマスタ世代番号を増加するように更新する。そして、新しいマスタが送信する情報に更新されたマスタ世代番号を含めることによって、レプリカは、マスタ世代番号に基づいて、新しいマスタの情報を識別することが可能となる。そのため、レプリカは、新しいマスタのデータ（特許請求の範囲に記載の議題内容）と同じ状態に、自身のデータを揃えることが可能となる。なお、補正処理部は、旧マスタを選定したときの議題番号から新しいマスタを選定したときの議題番号までの議題内容をすべて揃えるために、旧マスタを選定したときの議題内容に付けた議題番号より大きい議題番号の議題内容を取得する取得要求である問い合わせ通知を、自身以外のデータ管理装置に送信する。そして、補正処理部は、自身以外のデータ管理装置から、問い合わせ通知に対する応答として、旧マスタを選定したときの議題内容に付けた議題番号より大きい議題番号の議題内容およびその議題内容の議題番号を受信し、受信した議題番号と議題内容とを記憶部に記憶することによって、少なくとも、新しいマスタが選定される前までの議題番号と議題内容をすべて揃えることができる。
【００１６】
また、本発明は、分散データ管理システムにおいて、前記新しいマスタに選定されたレプリカ以外のデータ管理装置の補正処理部が、前記問い合わせ通知に対する応答に含まれる議題内容とその議題内容に付けられた前記選定時議題番号より大きい議題番号とを前記記憶部に記憶する場合、前記応答に含まれる議題内容と、その議題内容に付けられた前記選定時議題番号より大きい議題番号と同一の議題番号に付けられた、既に前記記憶部に記憶している議題内容とが異なる場合、当該記憶している議題内容を、前記応答に含まれる議題内容で上書きすることを特徴とする。
【００１７】
また、本発明は、データ管理方法において、前記新しいマスタに選定されたレプリカ以外のデータ管理装置が、前記補正処理において、  前記問い合わせ通知に対する応答に含まれる議題内容とその議題内容に付けられた前記選定時議題番号より大きい議題番号とを前記記憶部に記憶する場合、前記応答に含まれる議題内容と、その議題内容に付けられた前記選定時議題番号より大きい議題番号と同一の議題番号に付けられた、既に前記記憶部に記憶している議題内容とが異なる場合、当該記憶している議題内容を、前記応答に含まれる議題内容で上書きすることを特徴とする。
【００１８】
このような構成によれば、補正処理において、同一の議題番号について、記憶部に記憶している議題内容と応答に含まれる議題内容とが異なる場合に、記憶している議題内容を、応答に含まれる議題内容で上書きすることによって、すべてのデータ管理装置のデータを揃えることが可能となる。
【００１９】
本発明は、前記データ管理方法を、コンピュータとしてのデータ管理装置に実行させるためのプログラムとした。
【００２０】
このようなプログラムをインストールされたコンピュータは、このプログラムに基づいた機能を実現することができる。
【発明の効果】
【００２１】
本発明によれば、複数のデータ管理装置によって構成され、１台がマスタ、残りのデータ管理装置がマスタと同じデータの状態を保持するレプリカとして動作する分散データ管理システムにおいて、マルチマスタ状態になったときに、新しく選定されたマスタからの情報に基づいて、すべてのデータ管理装置のデータを同じ状態に維持させる技術を提供することができる。
【図面の簡単な説明】
【００２２】
【図１】分散データベースシステムの構成を示す図である。
【図２】本実施形態の概要を示す図である。
【図３】本実施形態におけるデータベース装置の構成および機能を示す図である。
【図４】レプリカにおけるマスタ選定処理の流れを示す図である。
【図５】レプリカにおける処理の流れを示す図である。
【図６】補正処理の流れを示す図である。
【発明を実施するための形態】
【００２３】
次に、本発明を実施するための形態（以降「本実施形態」と称す）について、適宜図面を参照しながら詳細に説明する。なお、本実施形態は、データベースシステムやファイルシステムに同様に適用することができる。以下、本実施形態では、データベースシステムの場合について説明する。
【００２４】
（分散データベースシステム）
本実施形態における分散データベースシステム１は、図１に示すように、例えば、５台のデータベース装置１０（１０Ａ，１０Ｂ，１０Ｃ，１０Ｄ，１０Ｅ）とクライアント端末２０とが、ネットワーク３０を介して、通信可能に接続されている。なお、図１では、データベース装置１０は５台記載しているが、３台以上であれば５台以外でも構わない。また、クライアント端末２０は、図１では１台しか記載されていないが、２台以上であっても構わない。なお、データベース装置１０は、特許請求の範囲に記載したデータ管理装置である。
【００２５】
データベース装置１０は、クライアント端末２０からデータベースの更新や参照のための処理要求を受け付けて、その処理要求に応答する１台を決定しておき、以降では、それをマスタと呼び、マスタ以外のデータベース装置１０をレプリカと呼ぶ。図１では、マスタは、データベース装置１０Ａであり、クライアント端末２０との間で処理要求およびその処理要求に対する応答を送受信する。そして、データベース装置１０Ｂ，１０Ｃ，１０Ｄ，１０Ｅは、レプリカとして、レプリカのデータベースをマスタのデータベースと同じ状態に維持するために、データベース同期のための情報をマスタ（データベース装置１０Ａ）との間で送受信する。レプリカの各データベース装置１０Ｂ，１０Ｃ，１０Ｄ，１０Ｅは、マスタに障害が発生したと判定したとき、新しいマスタに選定されるための調停（複数のレプリカの中から１つをマスタに選ぶこと）を開始する。なお、マスタとレプリカとの関係を構成するデータベース装置１０の集合をセルと呼び、このセルを単位として調停が実行される。また、データベース装置１０は、電源投入時には、レプリカとして起動され、調停結果に基づいて、マスタまたはレプリカに決定される。
【００２６】
データベース装置１０は、例えば、計算機やＰＣ（Personal Computer）であって、汎用のＯＳ（Operating System）と、データベースやファイルシステム等のデータ管理のためのプログラムおよび送受した情報を記憶する記憶部とを備えている。クライアント端末２０は、例えば、ＰＣであって、ユーザからの指示をマスタに送信し、その指示に対する応答を、図示しない出力装置等に出力する。また、ネットワーク３０は、インターネットまたはローカルエリアネットワークである。なお、ファイルシステムの場合には、データベース装置１０が記憶装置に相当し、ネットワーク３０が各記憶装置を接続するバスに相当する。
【００２７】
≪概要≫
始めに、本実施形態の概要について、図２を用いて説明する。図２において、縦方向の下に向かって時間が経過するものとする。そして、５台のデータベース装置１０Ａ，１０Ｂ，１０Ｃ，１０Ｄ，１０Ｅの中、データベース装置１０Ａがマスタとして動作し、残りの４台のデータベース装置１０Ｂ，１０Ｃ，１０Ｄ，１０Ｅがレプリカとして動作しているものとする。ここで、データベース装置１０Ａ，１０Ｂとデータベース１０Ｃ，１０Ｄ，１０Ｅとの間で、ネットワーク３０が分断したものとする。なお、以降の説明では、データベース装置１０Ａをマスタ、データベース装置１０Ｂ，１０Ｃ，１０Ｄ，１０ＥをそれぞれレプリカＲ１，Ｒ２，Ｒ３，Ｒ４と称することもある。
【００２８】
マスタは、リースタイムと呼ぶ期間以内に定期的に、自身の生存を示すリースパケットを全レプリカに送信している。レプリカは、リースタイム時間以内に、マスタの送信するリースパケットを受信できなかった場合、分散調停プロトコルを用いて、新たなマスタを選定するためのマスタ調停を開始する。なお、図２では、レプリカＲ４がマスタ調停を開始して、他のデータベース装置１０に対して、データの複製を実行する一例について説明する。
【００２９】
本実施形態における分散調停プロトコルでは、マスタ調停のための調停項目やデータの複製のための調停項目を議題と呼んでいる。そして、議題（議題内容）は、議題番号と共に送信される。なお、議題番号は、セル内でユニークであり、大小比較が可能であり、各データベース装置１０が次の議題を送信するときに、増加して用いられる。また、マスタおよびレプリカは、「新たにマスタが選定され、かつ、その新たに選定されたマスタが旧マスタと異なる場合」に増加する番号（以降、マスタ世代番号と称す）を保持しており、図２では、当初、マスタ世代番号が「２００」であるものとする。
【００３０】
図２に示すように、レプリカＲ４は、ネットワーク分断によって、リースタイム時間以内に、マスタの送信するリースパケットを受信できなかった場合、分散調停プロトコルを用いて、新しいマスタを選定するためのマスタ調停を開始する。マスタ調停では、議題を提案できる提案者を選定するPrepareフェーズ（第１のフェーズ）、提案者が議題を提案するProposeフェーズ（第２のフェーズ）、および決定結果を通知するCommitフェーズ（第３のフェーズ）が実行される。なお、各フェーズで用いられるPrepareメッセージ、Proposeメッセージ、Commitメッセージは、一例としてＰＡＸＯＳでは、Prepare(i,n,v)、Propose(i,n,v)、Commit(i,n,v)として表記される。なお、ｉは議題番号、ｎは優先度、ｖは議題内容を表しており、ＰＡＸＯＳ等のアルゴリズムに準拠して決定されるものとする。優先度ｎは、各データベース装置に予め定めらた優先度であって、セル内でユニークであり、大小比較が可能で、常に、どのデータベース装置が優先されるかの判定に用いられる。本実施形態では、課題を解決するために、変数として、マスタ世代番号ｇおよびマスタが選定されたときの議題番号（マスタを選定したときの議題内容に付けられた議題番号）ｆを新たに追加し、Prepare(g,i,f,n,v)、Propose(g,i,f,n,v)、Commit(g,i,f,n,v)のようにして用いる。マスタが選定されたときの議題番号ｆは、後記するように第２のフェーズで新しいマスタが決定された後、第３のフェーズでその決定結果を通知するCommitメッセージの議題番号である。そして、マスタが選定されたときの議題番号ｆは、後記するように、新しいマスタが選定されたときに、レプリカが既に旧マスタからメッセージを受信してそのメッセージに対応する処理を実行してしまっている場合に、旧マスタを選定したときの議題番号に対応する処理の状態に戻す（アンドゥする）ために用いられる。なお、以降の説明では、説明に必要な変数（ｇ，ｉ，ｆ，ｎ，ｖのいずれか）のみを表記し、説明に不要な変数を省略することとする。
【００３１】
第１のフェーズ（Prepareフェーズ）では、ＰＡＸＯＳ等のアルゴリズムに準拠するように、レプリカＲ４は、Prepare(n)（準備通知）をレプリカＲ４以外の他のデータベース装置１０（以降、単に「他のデータベース装置１０」と称する）に送信する。他のデータベース装置１０は、Prepare(n)を受信したとき、その受信時以前にPrepare(n)を受信していない場合、または、ｎが過去に受信したPrepare(n’)の優先度ｎ’以上の場合、PrepareACK(n)（確認通知）を返信する。また、他のデータベース装置１０は、Prepare(n)を受信したとき、優先度ｎが優先度ｎ’より小さい場合、Prepare(n)を棄却（無視）する、または否定応答PrepareNACKを返信する。なお、他のデータベース装置１０は、既に第２のフェーズのProposeACKを返信済みの過程まで進んでいた場合、「議題内容ｖは既に決定しているので、この議題内容で提案せよ」というPrepareNACK(n,v)を返信する。さらに、他のデータベース装置１０は、既に第３のフェーズのCommitACKを返信済みの過程まで進んでいた場合、決定済みの議題内容ｖを含むCommitACK(n,v)を返信する。そして、レプリカＲ４は、自身を含む過半数のデータベース装置からPrepareACKを受信できたとき、提案者として選定されたことになり、第２のフェーズの処理を開始する。図２では、レプリカＲ４は、自身を含む過半数のデータベース装置１０（１０Ｃ，１０Ｄ、１０Ｅ）からPrepareACKを受信している。
【００３２】
第２のフェーズ（Proposeフェーズ）では、ＰＡＸＯＳ等のアルゴリズムに準拠するように、レプリカＲ４は、議題内容ｖを提案するPropose(n,v)（提案通知）を他のデータベース装置１０に送信する。他のデータベース装置１０は、Propose(n,v)を受信したとき、その受信時以前にPropose(n,v)を受信していない場合、または、優先度ｎが過去に受信したPropose(n’)の優先度ｎ’以上の場合、ProposeACK（確認通知）を返信する。また、他のデータベース装置１０は、優先度ｎが優先度ｎ’より小さい場合、Proposeを棄却（無視）する、またはProposeNACK（否定応答）を返信する。レプリカＲ４は、自身を含め過半数のデータベース装置１０からProposeACKを受信できたとき、議題内容ｖは確定したことになり第３のフェーズの処理を開始する。なお、この時点で、レプリカＲ４は、新しいマスタとして選定されたことが保証（決定）される。そして、レプリカＲ４は、「新たにマスタが選定され、かつ、その新たに選定されたマスタが旧マスタと異なる場合」に該当するため、マスタ世代番号を、それまでのマスタ世代番号「２００」に「１」を増加して、「２０１」とする。仮に、新たにマスタに設定されたデータベース装置１０が、旧マスタと同じであれば、マスタ世代番号は変更しないものとする。
【００３３】
第３のフェーズ（Commitフェーズ）では、レプリカＲ４は、Proposeによって提案された議題内容ｖの決定結果を通知するCommit(n,v)（結果通知）を他のデータベース装置１０に送信する。なお、マスタ調停におけるCommitには、マスタ世代番号（図２では、「２０１」）が重畳される。他のデータベース装置１０は、Commit(n,v)を受信し、マスタ世代番号を更新し、CommitACK(n,v)を返信する。図２では、レプリカＲ４は、自身を含め過半数のデータベース装置１０からCommitACKを受信できたため、マスタとして設定され、クライアント端末２０から処理要求の受付を開始する。このようにして、分散調停プロトコルは、第１〜第３のフェーズを実行する。
【００３４】
そして、この時点で、ネットワークの分断が解消したものとする。この時点とは、例えば、旧マスタはレプリカからリースパケットに対する応答が戻ってこないことによってネットワークの分断を検知することが可能であるが、そのリースパケットに対する応答を受け取る前までの期間内のことである。そして、旧マスタ（データベース装置１０Ａ）からのProposeを用いた議題番号「１００」の提案通知（複製要求）については、（マスタ世代番号ｇ，議題番号ｉ）＝(200,100)が送信情報に格納されて、全レプリカに向けて送信される。また、新しいマスタ（レプリカＲ４）からのProposeを用いた議題番号「１００」の提案通知（複製要求）については、送信情報に（マスタ世代番号ｇ，議題番号ｉ）＝(201,100)が格納されて、他のデータベース装置１０に送信される。すなわち、旧マスタと新しいマスタとが、双方ともマスタとして動作するマルチマスタ状態となる。
【００３５】
そして、レプリカＲ３は、新しいマスタからの送信情報を、旧マスタからの送信情報より先に受信している。そこで、後に受信した送信情報のマスタ世代番号ｇが、先に受信したマスタ世代番号ｇ’より小さい場合には、後に受信した旧マスタからの送信情報を破棄する。また、レプリカＲ２は、新しいマスタからの送信情報を、旧マスタからの送信情報より後に受信している。そこで、後に受信した送信情報のマスタ世代番号ｇが、先に受信したマスタ世代番号ｇ’より大きい場合には、先に受信した旧マスタからの送信情報に基づいて記憶した情報を、その情報を記憶する直前の状態に戻し（アンドゥし）、後に受信した新しいマスタからの送信情報を上書きする。以上、説明したように、自分を含む過半数のデータベース装置１０からProposeACKを受信した時点で、マスタ世代番号ｇを、「新たにマスタが選定され、かつ、その新たに選定されたマスタが旧マスタと異なる場合」に増加することによって、マルチマスタ状態になったときに、新しく選定されたマスタからの情報に基づいて、すべてのデータベース装置１０のデータベースを同じ状態に維持させることができる。
【００３６】
（本実施形態のデータベース装置）
次に、データベース装置１０（１０Ａ，１０Ｂ，１０Ｃ，１０Ｄ，１０Ｅ）の構成および機能について、図３を用いて説明する。図３に示すように、各データベース装置１０は、処理部１１および記憶部１４を備える。処理部１１は、コンピュータのＣＰＵ（Central Processing Unit）とメインメモリとで構成され、記憶部１４に格納されているアプリケーションプログラムをメインメモリに展開して、各機能を具現化する。そして、処理部１１は、図示しない通信部を介して、クライアント端末２０（図１参照）からの処理要求を受け付け、その処理要求に対する応答を返信する。記憶部１４は、キャッシュメモリや二次記憶部等で構成され、各種プログラムや処理部１１の演算結果やデータベース装置１０間で送受信したメッセージを記憶する。
【００３７】
処理部１１は、図３に示すように、分散調停プロトコルの処理を実行する分散調停プロトコル処理部１２とマスタ世代番号に係る処理を実行するマスタ世代番号処理部１３とを備える。分散調停プロトコル処理部１２は、運転状態管理部１２１、基本処理部１２２、ブロック管理部１２３、ログ管理部１２４、および議題管理部１２５を備える。
【００３８】
運転状態管理部１２１は、データベース装置１０の運転状態を管理するモジュールである。運転状態としては、「マスタ動作」、「レプリカ動作」、「それ以外（例えば、調停前、調停中）」等がある。基本処理部１２２は、データベースを管理するために、処理部１１の各部１２１〜１２５間の連携制御を司る。
【００３９】
ブロック管理部１２３は、データベースで管理するテーブルやテーブル内のレコードの内容を固定長のデータ断片（ブロック）として複数管理するモジュールである。ブロックの数は可変である。ブロック管理部１２３は、ブロックの更新完了時に、そのブロックを非同期に記憶部１４の二次記憶部に永続化する。さらに、ブロック管理部１２３は、データベースの検索処理や更新処理の高速化のために、キャッシュメモリにもブロックを記憶する。
【００４０】
ログ管理部１２４は、マスタで発生した事象のログを、記憶部１４に同期的に永続化するモジュールである。ログ管理部１２４は、本実施形態では、特に、分散調停プロトコルの各議題の結果を記憶部１４に記憶する。また、ログ管理部１２４は、議題番号ｉ、マスタ世代番号ｇ、ログ種別、更新差分個数、および更新差分エントリに係るログを記憶部１４に記憶し、また記憶部１４からそれらのログを読み出す。なお、ログとは、議題内容を含むメッセージのことである。例えば、ログ管理部１２４は、コミットログを永続化先（記憶部１４または他のデータベース装置１０）に追記し、また議題番号をキーとして、その議題番号に対応するコミットログを取得する。ここで、議題番号ｉは、新規議題を開始するときに発行される識別子であり、同値判定、大小比較が可能である。マスタ世代番号ｇは、「新たにマスタが選定され、かつ、その新たに選定されたマスタが旧マスタと異なる場合」に増加される。そして、分散調停プロトコルでは、マスタ世代番号ｇと議題番号ｉとが組み合わされて、一意な識別子として用いられる。ログ種別は、ログの種類を識別する情報である。更新差分個数は、あるトランザクション内で更新されたブロックの更新回数である。
【００４１】
更新差分エントリは、更新ブロック識別子、ブロック内オフセット値、更新前イメージ、および更新後イメージを格納している。更新ブロック識別子は、どのブロックが更新されたかを示すブロック識別子である。ブロック内オフセット値は、ブロック内のどの位置が更新されたかを示すブロック内の位置である。更新前イメージは、ブロックを更新前の情報に戻すための情報である。また、更新後イメージは、ブロックを更新後の状態に変更するための情報である。なお、更新前イメージおよび更新後イメージは、ブロックのバイナリイメージのような物理形式で表現したり、関数や操作のような論理形式で表現されたりする。そして、更新前イメージをブロックに適用すると、ブロックが更新前の状態に戻り（ロールバック）、更新後イメージをブロックに適用すると、ブロックが更新後の状態に変更される（コミット）。したがって、ブロックのコミットログ（更新差分情報）を他のデータベース装置１０に適用すれば、他のデータベース装置１０に、テーブルの複製を作成することができる。
【００４２】
議題管理部１２５は、議題調停部１２６を管理し、複数の議題を管理するモジュールである。議題管理部１２５は、最新のマスタ世代番号と、議題番号を保持する。議題調停部１２６は、分散調停プロトコルのプロトコルスタックである。例えば、議題の議題内容ｖをマスタのＩＰアドレスとした場合、マスタの選定に用いることができ、議題内容ｖをコミットログとした場合、唯一のコミットログの確定に用いることができる。議題調停に用いるメッセージとしては、議題を提案できる提案者を選定する第１のフェーズで用いるPrepare(g,i,f,n,v)、提案者が議題を提案する第２のフェーズで用いるPropose(g,i,f,n,v)、決定結果を通知する第３のフェーズで用いるCommit(g,i,f,n,v)、および調停済みの結果を取得するために用いるLearn(g,i,f)がある。ただし、ｇはマスタ世代番号、ｉは議題番号、ｆは新しいマスタが選定されたときの議題番号、ｎは優先度、ｖは議題内容を表す。なお、Learn(i)は、議題番号ｉを指定して、その議題番号ｉに対応する調停済みの結果Commit(n,v)を取得するメッセージである。
【００４３】
マスタ世代番号処理部１３は、マスタ世代番号更新処理部１３１、送信処理部１３２、比較処理部１３３、否定処理部１３４、更新処理部１３５、再送要求処理部１３６、および補正処理部１３７を備える。
【００４４】
マスタ世代番号更新処理部１３１は、レプリカが新しいマスタに選定されたときに、記憶部１４に記憶されたマスタ世代番号を増加するように更新する。送信処理部１３２は、Prepareメッセージ、Proposeメッセージ、Commitメッセージを送信する。
【００４５】
比較処理部１３３は、新しいマスタから受信したメッセージに含まれるマスタ世代番号と、記憶部１４に記憶されるマスタ世代番号とを比較する。否定処理部１３４は、受信したメッセージに対する否定の応答を新しいマスタに返信する、または、受信したメッセージを破棄する。更新処理部１３５は、受信したメッセージに含まれる議題番号と記憶部１４に記憶される議題番号とを比較した結果に基づいて、受信したメッセージに含まれる議題番号が記憶部１４に記憶される議題番号以下のとき、受信したメッセージに含まれる議題番号と議題内容とを記憶する。再送要求処理部１３６は、受信したメッセージに含まれる議題番号と記憶部１４に記憶される議題番号とを比較した結果に基づいて、受信したメッセージに含まれる議題番号が記憶部１４に記憶される議題番号より大きいとき、記憶部１４において受信したメッセージに含まれる議題番号より小さい範囲の議題番号の中で欠番の議題番号に関連付けられた議題内容の再送を新しいマスタに要求する。
【００４６】
補正処理部１３７は、受信したメッセージに含まれるマスタを選定したときの議題内容に付けた議題番号より、大きい議題番号の議題内容の取得要求である問い合わせ通知を、自身以外のデータ管理装置に送信する。また、補正処理部１３７は、自身以外のデータ管理装置から、問い合わせ通知に対する応答として、マスタを選定したときの議題内容に付けた議題番号より大きい議題番号の議題内容およびその議題内容の議題番号を受信し、当該受信した応答に含まれる議題内容とその議題内容に付けられた議題番号とを記憶部１４に記憶し、記憶部１４に記憶しているマスタ世代番号を受信したメッセージに含まれるマスタ世代番号に更新する。
【００４７】
（レプリカにおけるマスタ選定処理）
次に、本実施形態のレプリカにおけるマスタ選定処理の流れについて、図４を用いて説明する（適宜図３参照）。なお、本実施形態では、マスタ調停は、分散調停プロトコルの第１〜第３のフェーズ（Prepare/Propose/Commit）を用いて実行する。
【００４８】
レプリカは、マスタが送信するリースパケットを所定時間（リースタイム時間）以内に受信できなくなったとき、自らマスタ調停を開始する。ステップＳ４０１では、レプリカは、タイマを設定し、タイマ識別子を取得する。具体的には、受信したリースパケットの時刻からリースタイム時間のタイムアウトとなるマスタリースタイムアウト時刻を取得し、タイマにマスタリースタイムアウト時刻後にタイムアウト通知を送信するよう設定し、そのタイマ値を識別するタイマ識別子を取得する。
【００４９】
ステップＳ４０２では、レプリカは、イベント（次のリースパケットまたはタイムアウト通知）を受信するまで待機するイベント待機の状態になる。すなわち、レプリカは、イベントを受信するまで待機し、イベントを受信した場合に、次のステップＳ４０３へ処理を進める。ステップＳ４０３では、レプリカは、リースパケットを受信したか否かを判定する。リースパケットを受信した場合（ステップＳ４０３でＹｅｓ）、ステップＳ４０４では、レプリカは、タイマ識別子で示されるタイマ値を新たなマスタリースタイムアウト時刻に延長する。そして、処理はステップＳ４０２へ戻って、レプリカは、再びイベント待機の状態になる。
【００５０】
ステップＳ４０３においてリースパケットを受信しなかった場合（ステップＳ４０３でＮｏ）、すなわち、タイムアウト通知を受信した場合、ステップＳ４０５では、レプリカは、マスタ調停を開始する、すなわち前記した分散調停プロトコルの第１のフェーズを実行する。具体的には、議題管理部１２５が新規議題を発行する。そして、議題管理部１２５は、議題種別を「マスタ選定」に設定し、議題調停部１２６を介して、Prepare(g,i,v)を他のレプリカに送信する。なお、議題内容ｖは自身のアドレスである。
【００５１】
ステップＳ４０６で、レプリカは、自身を含む過半数のPrepareACKを受信したか否かを判定する。過半数のPrepareACKを受信した場合（ステップＳ４０６でＹｅｓ）、ステップＳ４０７では、レプリカは、第２のフェーズをＰＡＸＯＳ等のアルゴリズムに準拠して実行する。ステップＳ４０８では、レプリカは、自身を含む過半数のProposeACKを受信したか否かを判定する。過半数のProposeACKを受信した場合（ステップＳ４０８でＹｅｓ）、ステップＳ４０９では、レプリカのマスタ世代番号更新処理部１３１（図３参照）は、新しいマスタに選定されるので、記憶部１４に記憶されたマスタ世代番号を増加するように、マスタ世代番号を設定（更新）し、第３のフェーズを実行する。具体的には、レプリカは、受信した過半数のProposeACKに含まれる議題内容ｖが自身のアドレスであった場合、マスタに選定されたことを保証される。そして、レプリカは、記憶部１４に記憶されているマスタ世代番号ｇを、「新たにマスタが選定され、かつ、その新たに選定されたマスタが旧マスタと異なる場合」に増加する。次に、レプリカは、Commitメッセージにマスタ世代番号ｇと自身のアドレスとを含めて、他のデータベース装置１０に送信する。なお、運転状態管理部１２１は、受信した議題内容ｖが自身のアドレスであるかないかに関わらず、新しいマスタのアドレス（ProposeACKに含まれる議題内容ｖ）を、マスタアドレスに設定する。
【００５２】
ステップＳ４１０では、レプリカは、自身を含む過半数のCommitACKを受信したか否かを判定する。過半数のCommitACKを受信した場合（ステップＳ４１０でＹｅｓ）、ステップＳ４１１では、レプリカは、マスタとしての動作を開始する。具体的には、議題調停部１２６がCommitACKを自身を含め過半数のデータベース装置１０から受信したことによって、レプリカは、自身をマスタとして設定する。すなわち、運転状態管理部１２１は、運転状態を「マスタ」に設定する。なお、このステップＳ４１０の時点において、運転状態管理部１２１は、受信した議題内容ｖが自身のアドレスであるかないかに関わらず、新しいマスタのアドレス（ProposeACKに含まれる議題内容ｖ）をマスタアドレスに設定する処理を、前記ステップＳ４０９における同様の処理の代わりに実行しても良い。そして、マスタ選定処理は終了する。なお、ステップＳ４０６でＮｏの場合、ステップＳ４０８でＮｏの場合、またはステップＳ４１０でＮｏの場合、処理はステップＳ４０１へ戻る。
【００５３】
（マスタによるデータの複製処理）
次に、マスタによるデータの複製処理について、マスタが自身の二次記憶部にデータを複製する場合およびマスタがレプリカにデータを複製する場合について説明する（適宜図１，３参照）。
【００５４】
まず、マスタが自身の二次記憶部にデータを複製する場合について説明する。マスタは、クライアント端末２０からトランザクションの開始要求、参照要求、更新要求、トランザクションの終了要求を受け付ける。そして、マスタは、その要求の内容の構文解析を行い、指定されたテーブルを参照して、指定されたレコードをインデクス検索によって抽出し、最終的に要求に対応するブロックの位置を特定する。更新要求の場合、マスタは、トランザクション内では仮更新を行って、トランザクションの完了時（コミット時）に、ログ管理部１２４を介して二次記憶装置への複製を実行する。そして、マスタは、その複製が成功した場合に、ブロックの実更新を行い、ロックの解放を行う。なお、トランザクション完了時には、更新ブロック一覧と各更新ブロックの更新前イメージ、更新後イメージが生成される。
【００５５】
次に、マスタがレプリカにデータを複製する場合について説明する。議題管理部１２５は、新規の複製を実行するために、新規の議題を発行する。次に、ログ管理部１２４は、ログイメージを作成する。そして、議題調停部１２６は、複製の調停を開始する。なお、本実施形態では、第２のフェーズ（Proposeフェーズ）のみを用いて実行される。したがって、議題調停部１２６は、Propose(g,i,v)をレプリカに送信する。ここで、ｇはマスタ世代番号、ｉは議題番号、ｖはログイメージである。
【００５６】
議題調停部１２６は、自身を含め過半数のProposeACKを受信した場合、議題が決定したことをログ管理部１２４に通知する。ログ管理部１２４は、議題調停部１２６からの通知を受信すると、トランザクションコミット成功（ログ書込み成功）と判定して、その判定結果を基本処理部１２２に通知する。そして、基本処理部１２２は、通知を受信すると、トランザクションコミット成功をクライアント端末２０に送信し、トランザクション処理が完結する。
【００５７】
なお、マスタが、所定時間内に、自身を含め過半数のデータベース装置１０からProposeACKを受信できなかった場合、議題調停部１２６は、ログ管理部１２４に、議題を決定できなかったことを通知する。そして、マスタは、ダウンする、または、トランザクションの状態が不安定であることをクライアント端末２０に返信する。
【００５８】
（レプリカにおける処理）
レプリカにおける処理の流れについて、図５を用いて説明する（適宜図３参照）。なお、レプリカは、受信したマスタ世代番号および受信した議題番号を記憶部１４に記憶しているが、以降の説明では、記憶部１４に記憶している中で最大のマスタ世代番号ｇを「記憶部で最大のマスタ世代番号ｇｍ」、および記憶部１４に記憶している中で最大の議題番号ｉを「記憶部で最大の議題番号ｉｍ」と称す。
【００５９】
図５に示す処理の流れは、レプリカがPrepareメッセージ、Proposeメッセージ、Commitメッセージを受信（ログ受信）した場合を表している。ここでは、レプリカが、マスタからPropose(g,i,f,n,v)を受信した場合について説明する。なお、ｇはマスタ世代番号、ｉは議題番号、ｆは新しいマスタが選定されたときの議題番号、ｎは優先度、ｖは議題内容である。ステップＳ５０１では、レプリカの比較処理部１３３は、受信したマスタ世代番号ｇと記憶部で最大のマスタ世代番号ｇｍとの大小を比較する。受信したマスタ世代番号ｇと記憶部で最大のマスタ世代番号ｇｍとが等しい（ｇ＝ｇｍ）場合、ステップＳ５０２では、レプリカは、メッセージがProposeか否かを判定する。
【００６０】
メッセージがProposeである場合（ステップＳ５０２でＹｅｓ）、ステップＳ５０３では、レプリカの更新処理部１３５は、受信した議題番号ｉと記憶部で最大の議題番号ｉｍとを比較する。受信した議題番号ｉが記憶部で最大の議題番号ｉｍ以下（ｉ≦ｉｍ）の場合、ステップＳ５０４では、レプリカの更新処理部１３５は、ログ出力を実行する、すなわち、コミットログを二次記憶部に書き込む。そして、ステップＳ５０５では、レプリカの更新処理部１３５は、ブロック更新を実行して、Proposeの結果が永続化される。ステップＳ５０６では、レプリカは、マスタに対して分散調停プログラムを用いた応答を実行する。具体的には、前記したように、レプリカは、ＰＡＸＯＳ等のアルゴリズムに準拠して、過去にPropose(n,v)を受信していない場合、または、優先度ｎが過去に受信したPropose(n’)の優先度ｎ’以上の場合、ProposeACK（確認通知）を返信し、優先度ｎが優先度ｎ’より小さい場合、受信したProposeを棄却（無視）する、またはProposeNACK（否定応答）を返信する。そして、処理はステップＳ５０１へ戻り、次のログを受信するまで待機する。
【００６１】
ステップＳ５０１で、受信したマスタ世代番号ｇが記憶部で最大のマスタ世代番号ｇｍより大きい（ｇ＞ｇｍ）場合、ステップＳ５０７では、レプリカは、補正処理を実行する。なお、この補正処理の詳細については後記する。また、ステップＳ５０１において、受信したマスタ世代番号ｇが記憶部で最大のマスタ世代番号ｇｍより小さい（ｇ＜ｇｍ）場合、ステップＳ５０８では、レプリカの否定処理部１３４は、否定応答を実行する。具体的には、レプリカの否定処理部１３４は、ProposeNACKを返信する、または、Proposeを棄却（無視）しても良い。そして、ステップＳ５０８の後、処理はステップＳ５０１へ戻る。
【００６２】
また、ステップＳ５０２において、メッセージがProposeでない場合（ステップＳ５０２でＮｏ）、ステップＳ５０９では、レプリカは、分散調停プログラムを用いた応答を実行する。具体的には、レプリカは、受信したPrepareに対しては、前記した第１のフェーズにおける応答を実行する。また、受信したCommitに対しては、前記した第３のフェーズにおける応答を実行する。そして、ステップＳ５０９の後、処理はステップＳ５０１へ戻り、次のログを受信するまで待機する。
【００６３】
また、ステップＳ５０３において、受信した議題番号ｉが記憶部で最大の議題番号ｉｍより大きい場合（ステップＳ５０３でｉ＞ｉｍ）、ステップＳ５１０では、レプリカの再送要求処理部１３６は、再送要求を実行する。なお、受信した議題番号ｉが記憶部で最大の議題番号ｉｍより大きくなる場合とは、ネットワーク３０内の輻輳等によって、到着するメッセージの順番（すなわち、議題番号）が入れ替わる場合のことである。また、再送要求は、具体的には、議題番号ｉの飛び番号を発見したときに、抜けている議題番号ｉの議題内容の再送を、PrepareメッセージまたはLearnメッセージを用いて要求するものである。そして、ステップＳ５１０の後、処理はステップＳ５０１へ戻り、次のログを受信するまで待機する。
【００６４】
次に、補正処理部１３７（図３参照）が実行する補正処理の詳細について、図６を用いて説明する（適宜図３参照）。ステップＳ６０１では、レプリカは、新しいマスタが選定される前の旧マスタから議題内容を補充するために、受信したメッセージに含まれる、マスタ（旧マスタ）が選定された時の議題番号ｆを開始番号として、ｊ＝開始番号＋１を演算し、その結果ｊを議題番号とする。ステップＳ６０２では、レプリカは、Learn(ｊ)を自身以外のデータベース装置１０に送信する。Learn(ｊ)は、議題番号ｊを指定して、その議題番号ｊに対応する調停済みの結果（例えば、Commit(n,v)）を取得するメッセージである。なお、本実施形態では、複製処理の場合には、Proposeメッセージしか用いられないが、自身を含め過半数のProposeACKを受信した場合、議題内容ｉが決定したことになるので、実質的に、調停済みの結果がレプリカに記憶されていることになる。つまり、Learn()によって、その調停済みの結果が取得される。ステップＳ６０３では、レプリカは、値ｖ（議題番号ｊの議題内容）を取得できたか否かを判定する。
【００６５】
値を取得できた場合（ステップＳ６０３でＹｅｓ）、ステップＳ６０４では、レプリカは、議題番号ｊの議題内容が自分のログにあるか否かを判定する。議題番号ｊの議題内容が自分のログにある場合（ステップＳ６０４でＹｅｓ）、レプリカは、議題番号ｊの議題内容と自分のログの議題内容が同一か否かを判定する。議題番号ｊの議題内容と自分のログの議題内容が同一である場合（ステップＳ６０５でＹｅｓ）、レプリカは、議題番号ｊを１増加して（ｊ＝ｊ＋１）、ステップＳ６０２の処理に戻る。
【００６６】
ステップＳ６０４において、議題番号ｊの議題内容が自分のログにない場合（ステップＳ６０４でＮｏ）、レプリカは、取得した値を用いて、ログ出力を行い、ブロック更新し（ステップＳ６０７，Ｓ６０８）、処理をステップＳ６０９へ進める。また、ステップＳ６０５において、議題番号ｊの議題内容と自分のログの議題内容が同一でない場合（ステップＳ６０５でＮｏ）、レプリカは、アンドゥを実行し（ステップＳ６０６）、処理をステップＳ６０７へ進める。なお、「アンドゥ」は、該当する議題番号ｊの議題内容を更新前イメージを用いて書き戻すことを意味する。また、ステップＳ６０３において、値を取得できなかった場合（ステップＳ６０３でＮｏ）、ステップＳ６１０では、レプリカは、マスタ世代番号を受信したマスタ世代番号に更新する。
【００６７】
（実施例）
図２を具体例として、レプリカＲ２，Ｒ３，Ｒ４（データベース装置１０Ｃ，１０Ｄ，１０Ｅ）における本実施形態の処理の流れを説明する（適宜図４，図５、図６参照）。レプリカＲ２，Ｒ３，Ｒ４は、議題番号「９８」まで調停済みであり、マスタ（データベース装置１０Ａ）のマスタ世代番号が「２００」であるものとする。図４に示すように、レプリカＲ４は、ネットワーク３０の分断にともなって、マスタからのリースパケットをリースタイム時間以内に受信できなかったため、マスタ調停を開始する。第１のフェーズ（Prepareフェーズ）では、レプリカＲ４は、新規議題番号「９９」を発行し、Prepare(g,i,n,v)をすべてのデータベース装置１０に送信する。レプリカＲ２，Ｒ３は、図５に示すステップＳ５０１では、受信したマスタ世代番号ｇと記憶部で最大のマスタ世代番号ｇｍとが等しいので、ステップＳ５０２で分散調停プロトコルを用いた応答PrepareACKを、レプリカＲ４へ返信する。
【００６８】
次に、第２のフェーズ（Proposeフェーズ）では、レプリカＲ４は、自分を含め過半数のPrepareACKを受信した場合、Propose(g,i,n,v)をすべてのデータベース装置１０に送信する。レプリカＲ２，Ｒ３は、Propose受信時には、図５に示すように、受信したマスタ世代番号ｇ「２００」が自身の記憶部で最大のマスタ世代番号ｇｍ「２００」と等しいので、処理はステップＳ５０２へ進んで、受信した議題番号ｉと記憶部で最大の議題番号ｉｍとを比較する。受信した議題番号ｉ「９９」は、記憶部で最大の議題番号ｉｍ「９９」に等しいので、処理はＳ５０４へ進んで、ログ出力を実行し、ブロック更新を実行する。このブロック更新によって、Proposeの結果が永続化される。そして、この処理の後、レプリカＲ２，Ｒ３は、ProposeACKをレプリカＲ４に返信する。なお、レプリカＲ４は、この自分を含め過半数のProposeACKを受信した時点で、新しいマスタとして選定されたことが保証される。レプリカＲ４は、新しいマスタとして、「新たにマスタが選定され、かつ、その新たに選定されたマスタが旧マスタと異なる場合」に該当するため、それまでのマスタ世代番号ｇ「２００」に「１」を増加して、マスタ世代番号ｇを「２０１」に設定する。
【００６９】
次に、第３のフェーズ（Commitフェーズ）では、レプリカＲ４（以降、新しいマスタと称することもある）は、マスタ世代番号ｇ「２０１」と、議題番号ｉ「９９」とをCommitメッセージに含めて、すべてのデータベース装置１０に送信する。レプリカＲ２，Ｒ３は、図５に示すように、受信したマスタ世代番号ｇ「２０１」が自身の記憶部で最大のマスタ世代番号ｇｍ「２００」より大きいので、処理はステップＳ５０７へ進み、補正処理を実行する。補正処理では、開始番号が、記憶部１４に記憶部で最大の議題番号ｉｍ「９９」であるので、図６に示すように、議題番号として変数ｊ＝９９＋１＝１００を設定し（ステップＳ６０１）、すべてのデータベース装置１０にLearn(j)を送信する（ステップＳ６０２）。この時点では、議題番号１００は存在しないため、ステップＳ６０３でＮｏとなり、自身のマスタ世代番号ｇを更新する。そして、レプリカＲ２，Ｒ３は、補正処理の後、ステップＳ５０９において、分散調停プロトコルを用いた応答、すなわち、CommitACKをレプリカＲ４に返信する。
【００７０】
レプリカＲ４は、自身を含め過半数のデータベース装置１０からCommitACKを受信できたため、旧マスタの複製要求の失敗が保証されたことを認識し、クライアント端末２０から処理要求の受け付けを開始する。
【００７１】
そして、この時点で、ネットワークの分断が解消されたものとする。レプリカＲ２は、旧マスタから議題番号「１００」のProposeを受信し、次に新しいマスタから議題番号「１００」のProposeを受信する。これらの議題番号は同じであっても、データベースとしては、通常は異なるテーブルの異なるレコードの更新であるため、旧マスタからの更新を取り消して、新しいマスタからの更新を受け付ける必要がある。この場合、図５のステップＳ５０１において、受信したマスタ世代番号ｇ「２０１」は、自身の記憶部で最大のマスタ世代番号ｇｍ「２００」より大きいので、レプリカＲ２は、補正処理（ステップＳ５０７）を実行する。すなわち、レプリカＲ２は、図６のステップＳ６０１において、開始番号が、記憶部で最大の議題番号ｉｍが「９９」であるので、議題番号として変数ｊ＝９９＋１＝１００を設定して、Learn(100)をすべてのデータベース装置１０に送信する。そして、レプリカＲ２は、ステップＳ６０３でＹｅｓ、ステップＳ６０４でＮｏと処理を進めて、先に受信した旧マスタからの議題番号「１００」に関して「アンドゥ（ステップＳ６０６）」を実行する。そして、レプリカＲ２は、ステップＳ６０７，Ｓ６０８を実行して、ステップＳ６０２において取得した新しいマスタからの議題内容について、ログ出力し、ブロック更新する。
【００７２】
また、レプリカＲ３は、新しいマスタの議題番号「１００」のProposeを受信し、次に旧マスタの議題番号「１００」のProposeを受信する。レプリカＲ３は、新しいマスタの議題番号「１００」のProposeを受信した時点で、記憶部で最大のマスタ世代番号ｇｍが「２０１」となっている。そのため、レプリカＲ３は、後から受信した旧マスタの議題番号「１００」のProposeのマスタ世代番号ｇ「２００」に対して、ステップＳ５０１において、受信したマスタ世代番号ｇが記憶部で最大のマスタ世代番号ｇｍより小さいので、処理をステップＳ５０８へ進め、否定応答を実行する。このようにして、議題番号「１００」の調停に関して、データの整合性を保つことができる。
【００７３】
以上、本実施形態の分散データベースシステム１は、複数のデータ管理装置によって構成され、１台がマスタ、残りのデータ管理装置がマスタと同じデータの状態を維持するレプリカとして動作する。この分散データベースシステム１において、データ管理装置間を接続するネットワークに障害が発生してマルチマスタ状態になったときに、マスタ調停が行われて、新しいマスタが選定された場合、新しく選定されたマスタは、「新たにマスタが選定され、かつ、その新たに選定されたマスタが旧マスタと異なる場合」であれば、マスタ世代番号を更新する。そして、レプリカが、旧マスタおよび新しいマスタから同じ議題番号を含む複製に係るProposeを受信した時に、マスタ世代番号の大きい方（新しい方）に基づいて、ログ更新およびブロック更新を行う。このことによって、新しく選定されたマスタからの情報に基づいて、すべてのデータ管理装置のデータを同じ状態に保持させることができる。なお、本実施形態では、リースパケットがリースタイム時間以内に受信できなくなる例として、ネットワークの分断を用いて説明したが、これ以外にも、ネットワーク内でのパケットの遅延や損失等がある。
【００７４】
なお、本実施形態では、マスタのデータをレプリカに複製する場合、Proposeメッセージのみを用いて実行する場合について示した。この処理では、レプリカがProposeを受信したときに、直ちにログ出力およびブロック更新を実行する（図５に示すステップＳ５０４およびＳ５０５参照）ので、データベース更新を早く終わらせることができる。本実施形態の別の処理として、ProposeメッセージとCommitメッセージとを用いても、本実施形態と同様の結果を実現できる。すなわち、レプリカは、Proposeメッセージを受信したときに、一時的にキャッシュメモリ等にログを記憶しておき、Commitメッセージを受信したときに、ログ出力およびブロック更新を実行する。別の処理の場合は、Commitメッセージを受信するまでデータベース更新が完了しないので、本実施形態の場合の方がデータベース更新を早く終わらせることができる。なお、本実施形態では、Proposeメッセージを受信した時点でデータベース更新を行ってしまうので、マルチマスタ状態の古いマスタのデータを先に記憶した後で新しいマスタのデータを受信した場合、ログを上書きするために、アンドゥの処理（図６のステップＳ６０６参照）が必要とされる。このアンドゥの処理は、更新処理を遅くする要因となりうる。しかし、新しいマスタが選定される頻度がそれほど多くない場合には、更新処理に掛かる時間はほとんど増加しない。
【００７５】
なお、本実施形態では、PrepareメッセージおよびProposeメッセージに対する応答としてPrepareACKおよびProposeACKを返信する場合を、受信したメッセージに含まれる優先度ｎが過去に受信した優先度ｎ’以上の場合として記載した。しかし、必ずしも、「以上」に限られることは無く、「より大きい」としても良い。
【００７６】
また、本実施形態において用いる分散調停プロトコルが、ＰＡＸＯＳ等のアルゴリズムに準拠したものである場合、セルを構成するデータ管理装置の台数は、３台以上の奇数台であることが望ましい。
【００７７】
また、本実施形態において、データベース装置１０（図３参照）の各部１１〜１３の処理は、データベース装置１０をコンピュータで実現したときに搭載されるプログラムによって実現されてもよい。このプログラムは、通信回線を介して提供することもできるし、ＣＤ−ＲＯＭ等のコンピュータ読み取り可能な記録媒体に書き込んで配布することも可能である。
【符号の説明】
【００７８】
１      分散データベースシステム（分散データ管理システム）
１０（１０Ａ，１０Ｂ，１０Ｃ、１０Ｄ，１０Ｅ）  データベース装置（データ管理装置）
１１    処理部
１２    分散調停プロトコル処理部
１３    マスタ世代番号処理部
１４    記憶部
３０    ネットワーク
１２１  運転状態管理部
１２２  基本処理部
１２３  ブロック管理部
１２４  ログ管理部
１２５  議題管理部
１２６  議題調停部
１３１  マスタ世代番号更新処理部
１３２  送信処理部
１３３  比較処理部
１３４  否定処理部
１３５  更新処理部
１３６  再送要求処理部
１３７  補正処理部
【図１】
0005416490.tif 000002
【図２】
0005416490.tif 000003
【図３】
0005416490.tif 000004
【図４】
0005416490.tif 000005
【図５】
0005416490.tif 000006
【図６】
0005416490.tif 000007