(57)【特許請求の範囲】
【請求項１】
少なくとも１つのマスタプロセッサと複数のスレーブプロセッサとからなるシステムにおいて、前記少なくとも１つのマスタプロセッサか前記複数のスレーブプロセッサのいずれか１つに関連する障害状態を補償する方法であって、前記プロセッサの各々は前記プロセッサと関連するデータベースにアクセスし前記データベースを制御するものであり、前記方法は、
ａ．前記プロセッサの各々で最後に完了したデータベース更新トランザクションを記録するステップと、
ｂ．前記少なくとも１つのマスタプロセッサによって生成された所定数のデータベース更新トランザクションのステップを記録するために、前記少なくとも１つのマスタプロセッサと関連するジャーナルを作成するステップと、
ｃ．前記ジャーナルにデータベース更新トランザクションの前記ステップを記録するステップと、
ｄ．複数の第１タイマを作成するステップとからなり、前記複数のスレーブプロセッサの各々が前記複数の第１タイマの少なくとも１つと関連し、さらに、
ｅ．複数の第２タイマを作成するステップとからなり、前記複数のスレーブプロセッサの各々が前記複数の第２タイマの少なくとも１つと関連し、さらに、
ｆ．更新トランザクションの開始時に、前記更新トランザクションを受信した前記複数のスレーブプロセッサの各々と関連する前記第１タイマをスタートさせるステップと、
ｇ．更新トランザクションの終了時に、前記更新トランザクションを受信した前記複数のスレーブプロセッサから前記少なくとも１つのマスタプロセッサへ所定のメッセージを送信するステップと、
ｈ．更新トランザクションのあるステップを受信し、そして前記更新トランザクションの次のステップを受信した後に、前記更新トランザクションを受信した前記複数のスレーブプロセッサの各々と関連する前記第１タイマをリセットするステップと、
ｉ．前記所定のメッセージが前記少なくとも１つのマスタプロセッサへ送信されるときに、前記所定のメッセージを送信した前記複数のスレーブプロセッサの各々と関連する第２タイマをスタートさせるステップと、
ｊ．前記複数のスレーブプロセッサのいずれか１つが故障した場合、
Ａ．以前に故障したプロセッサの最後のデータベース更新の後のすべてのデータベース更新トランザクションを前記ジャーナルから前記故障したプロセッサへコピーするステップと、
ｋ．前記少なくとも１つのマスタプロセッサが故障した場合、
Ａ．前記複数の第２タイマの少なくとも１つの満期の前に、前記複数の第１タイマの少なくとも１つの満期を検出し、その後、
１．満期になった前記第１タイマと関連する前記スレーブプロセッサが現在の更新トランザクションをアボートするステップと、
２．満期になった前記第１タイマと関連する前記スレーブプロセッサがアボートメッセージを他の全てのスレーブプロセッサへ送信し、前記アボートメッセージを受信した前記他の全てのスレーブプロセッサは前記現在の更新トランザクションをアボートするステップと、
Ｂ．前記複数の第２タイマの少なくとも１つの満期を検出し、その後、満期となった前記第２タイマと関連するスレーブプロセッサは前記現在の更新トランザクションをコミットするステップとからなることを特徴とする方法。
【請求項２】
前記ステップｉはさらに、前記複数のスレーブプロセッサの第１のものと関連する前記複数の第１タイマの少なくとも１つを無効にするステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記ステップｂは、前記マスタプロセッサによって生成されるデータベース更新トランザクションのステップを記録する巡回バッファを作成するステップを含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記ジャーナルはステップａからステップｋまでの間更新されることを特徴とする請求項１に記載の方法。
【請求項５】
前記故障したプロセッサがスレーブプロセッサであり、前記故障したスレーブプロセッサが回復した後に他のデータベースと整合させるために、
ｌ．前記ステップａは、前記複数の第１タイマからの第１タイマによって確立された第１タイマウインドウの間、分散ネットワークに位置する各プロセッサで最後に完了したデータベース更新トランザクションの記録を記録するステップを含み、前記複数の第１タイマからの第１タイマはスレーブプロセッサの各々と関連し、
ｍ．前記ステップｂは、スレーブプロセッサの各々と関連する第２タイマによって確立された第２タイマウインドウの間、前記マスタプロセッサによって生成されたデータベース更新トランザクションのステップを記録する、分散ネットワークに位置する前記マスタプロセッサと関連するジャーナルを作成するステップを含み、前記第２タイマは前記複数の第２タイマからのものであり、そして、
ｎ．分散ネットワークに位置する故障したスレーブプロセッサの回復に応動して、以前故障したスレーブプロセッサの最後のデータベース更新の後のすべてのデータベース更新トランザクションを前記ジャーナルから前記故障したプロセッサへコピーするステップを含み、そして
ｏ．最後のデータベース更新の後のすべてのデータベース更新トランザクションで、前記故障したスレーブプロセッサと関連するデータベースを更新するステップを含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記ステップｍは、前記マスタプロセッサによって生成されるデータベース更新トランザクションのステップを記録する巡回バッファを作成するステップを含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記巡回バッファはステップｌからステップｏまでの間更新されることを特徴とする請求項６に記載の方法。
【請求項８】
前記ステップｌは、最後のデータベース更新トランザクションの番号を記録するステップをさらに含むことを特徴とする請求項５に記載の方法。
【請求項９】
前記ステップｌは、最後のデータベース更新トランザクションの完全なコピーを記録するステップをさらに含むことを特徴とする請求項５に記載の方法。
【請求項１０】
前記ステップｌは、最後のデータベース更新トランザクションの日付を記録するステップをさらに含むことを特徴とする請求項５に記載の方法。
【請求項１１】
前記ステップｌは、最後のデータベース更新トランザクションの時刻を記録するステップをさらに含むことを特徴とする請求項５に記載の方法。
【請求項１２】
前記ステップｌからｏまでの間に生じたデータベース更新トランザクションを前記故障したスレーブプロセッサにコピーするステップをさらに含むことを特徴とする請求項５に記載の方法。
【請求項１３】
ｐ．あるプロセッサをバックアップマスタプロセッサに指定するステップと、
ｑ．前記バックアップマスタプロセッサと関連するジャーナルを作成するステップと、
ｒ．前記バックアップマスタプロセッサと関連するジャーナルに、前記マスタプロセッサと関連するジャーナルに記録されている情報を記録するステップとをさらに有することを特徴とする請求項５に記載の方法。
【請求項１４】
前記少なくとも１つのマスタプロセッサの故障後に更新トランザクションを完了するために、
前記ステップｆの後、前記ステップｇの前に、前記現在の更新トランザクションの受信に応動して、前記複数のスレーブプロセッサの第１のものから前記少なくとも１つのマスタプロセッサへコミット投票メッセージを送信するステップと、
前記メッセージを送信した前記複数のスレーブプロセッサのいずれか１つと関連する前記複数の第１タイマと前記複数の第２タイマとの少なくとも１つを開始するステップと、
前記複数の第１タイマと前記複数の第２タイマの少なくとも１つの満期に応答するステップとからなることを特徴とする請求項１に記載の方法。
【請求項１５】
前記複数の第１タイマと前記複数の第２タイマの少なくとも１つの満期に応答するステップは、前記現在の更新トランザクションをコミットするステップをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記複数のタイマの少なくとも１つの満期の前に、前記複数のスレーブプロセッサのいずれか１つからアボートメッセージを受信するステップと、
前記アボートメッセージを受信した前記複数のスレーブプロセッサのいずれか１つが前記現在の更新トランザクションをアボートするステップとをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１７】
前記アボートメッセージを受信した前記複数のスレーブプロセッサのいずれか１つが前記複数のスレーブプロセッサへアボートメッセージを送信するステップをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１８】
前記少なくとも１つマスタプロセッサに関連する故障状態を補償し、そして前記少なくとも１つのマスタプロセッサの故障の後に更新トランザクションを完了するために、
前記ステップｇは、現在の更新トランザクションの終了時に、所定のメッセージを前記複数のスレーブプロセッサのいずれか１つから前記少なくとも１つのマスタプロセッサへ送信するステップを含み、
前記ステップｉは、前記所定のメッセージを前記少なくとも１つのマスタプロセッサへ送信した前記複数のスレーブプロセッサの少なくとも１つと関連する前記複数の第２タイマのいずれかをスタートさせるステップを含み、そして、
前記ステップｋのＡは、前記複数の第１タイマのいずれかまたは前記複数の第２タイマのいずれかの満期を検出するステップを含むことを特徴とする請求項１に記載の方法。
【請求項１９】
前記ステップｋのＡは、前記複数の第１のタイマのいずれかまたは前記複数の第２のタイマのいずれかの満期を検出し、その後、前記複数のタイマの少なくとも１つの満期が前記複数の第２のタイマの少なくとも１つの満期よりも前であるときには、前記現在の更新トランザクションをアボートするステップを含むことを特徴とする請求項１８に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、フォールトトレラント分散データベースシステムにおいてトランザクションを完了する方法および装置に関する。
【０００２】
【従来の技術】
分散データベースシステムとは、一般に、複数の別個の相互に通信するデータベースを有するシステムのことである。記憶されているデータの少なくとも一部は、複数のデータベースコピーにおいて同一である。従って、共通のデータがデータベースコピーのうちの１つで変更されたときには、データベースシステム全体でデータベースの一致を保つために、同じ変更を他のすべてのデータベースコピーで行わなければならない。通常の状況では、データベース変更はマスタデータベースコントローラによって行われる。データベースマスタコントローラは、自己のデータベースコピーに対する変更を行い、ネットワークを構成する他のデータベースコピーへの更新を制御する責任がある。しかし、データベースコピーまたはそのコピーをデータベースマスタコントローラに接続するリンクのいずれかに生じた障害がデータベースの全部または一部への送信あるいは変更を妨げると問題が生じる。
【０００３】
分散データベースネットワーク内では、情報はトランザクションによって個々のデータベースに入力される。データベース「トランザクション」とは、ユーザが制御する（またはマスタデータベースが制御する）データベースアクションの系列であって、「開始ステップ」および「終了ステップ」の両方によってマークされたものである。開始ステップと終了ステップの間のデータベースアクションが、データベースを更新するステップあるいはアクションを構成する。終了ステップは、コミットまたはアボート（中断）のいずれかであることが可能である。コミットは、前の更新トランザクションを実行する命令であり、データベースを変更する。アボートは、前の更新トランザクションを無効にする命令である。各プロセッサで生じる可能性のあるトランザクションには、コールドトランザクションおよびホットトランザクションという２種類のトランザクションがある。コールドトランザクションは、既に完了しており、故障したデータベースプロセッサの回復期間中にのみ使用されるトランザクションである。ホットトランザクションは、完了または中断していない進行中のトランザクションである。
【０００４】
通信産業における分散データベースは高度の可用性とともに高い信頼性が必要である。さらに、このようなシステムはフォールトトレラントでもなければならない。すなわち、あるデータベースコピーの障害がシステム全体をダウンさせてはならない。（米国における）８００番サービス（日本におけるフリーダイヤルに相当）のような情報へのアクセスの例に見られるように、通信産業はこの点で非常に要求の厳しいものである。発呼があった場合、データベースへの問合せとその問合せに対応する番号の回答の間の応答時間は素早くしかも信頼性が高い必要がある。応答遅延は、呼設定の遅延を生じ、顧客の不満足を生じる結果となる。
【０００５】
分散データベースシステムでは、データベース同期は通常「２相コミット」というアルゴリズムで行われる。２相コミットは、「コーディネータ」、「マスタ」あるいはコントローラと呼ばれる１つのデータベースコピーと、「パティシパント」、「スレーブ」ノード（コピー）と呼ばれる分散データベースシステム内の他のすべてのコピーとで実行される。２相コミットアルゴリズムは次のように動作する。
【０００６】
第１相。コーディネータは、ネットワークを通じてすべてのパティシパントへ、１つまたは複数のデータベースレコードの更新のようなトランザクションをコミットするよう要求するメッセージを送る。データベースパティシパントが故障している場合、または、停止している（利用可能でない）場合には、コーディネータに対して、そのトランザクションをコミットする用意ができていないことを示すメッセージにより応答しなければならない。パティシパントが故障により応答することができない場合、「ノットレディ(not ready)」応答がコーディネータによって仮定される。コーディネータは、第２相に入る前に、すべてのパティシパントからの応答を受信するのを待機する。
【０００７】
第２相。すべてのデータベースパティシパントが正しく応答した場合、コーディネータはすべてのデータベースパティシパントへ「コミット」メッセージ（コマンド）をブロードキャストし、パティシパントがトランザクションをコミットするようにする。いずれかのパティシパントが、故障を示すメッセージで応答した場合または応答することができない場合、コーディネータはすべてのパティシパントへアボートメッセージをブロードキャストする。
【０００８】
マスタは、２相コミットのためにアクティブで利用可能なパティシパントのステータスを知るため、アクティブで利用可能なデータベースプロセッサの動的リスト（「定数(quorum)」という。）を保持する。この動的リストは、どのデータベースプロセッサがアクティブで利用可能であり、従って更新トランザクションを受け取ることが可能であるかを判定するためにマスタによって使用される。データベースプロセッサは、このリストにある場合、トランザクションを正しくコミットすることができると仮定される。
【０００９】
【発明が解決しようとする課題】
本発明の目的は、マスタデータベースプロセッサの故障のために正常に完了しなかったトランザクションを適切に完了させる分散データベースシステムを実現することである。トランザクションの完了が、新たなマスタによる指令なしで、しかも、トランザクションをもとに戻したり再実行したりすることなく行われれば望ましい。
【００１０】
本発明のもう１つの目的は、故障していないすべてのパティシパントが外部からの調整なしで自動的に障害回復を実行し、失敗したトランザクションのクリーンアップ処理に伴う遅延をなくすことができるような分散データベースシステムを実現することである。さらに、故障したパティシパントは、再同期期間中に行われているトランザクションを中断することなく故障していない部分に再同期して新たなトランザクションに加わることが可能であるようにする。
【００１１】
【課題を解決するための手段】
本発明の１つの特徴によれば、上記の目的は、１つまたは複数のデータベースパティシパントが故障したかも知れないために故障した分散データベースシステムにおいてデータベーストランザクションを完了する方法および装置を実現することにより達成される。マスタデータベースプロセッサが故障した場合、故障していないすべてのパティシパントは、マスタデータベースプロセッサのサービス復帰または置換までの間は、トランザクションをコミットするかまたはトランザクションをアボートするかのいずれかである。トランザクションの進行中または進行中のトランザクションがない間のいずれかに、スレーブプロセッサのうちの１つが故障した場合、故障したスレーブプロセッサは、故障していない他のスレーブプロセッサに影響を及ぼすことなく全体に再同期することができる。故障したプロセッサがサービスに復帰するときには、故障したプロセッサは、マスタデータベースプロセッサとの連絡を断っていた間に更新されたスレーブプロセッサと一致するように更新することができる。
【００１２】
一実施例では、本発明は、各スレーブプロセッサに１対のタイマを設ける。第１のタイマは、更新トランザクションの開始ステップがそのスレーブプロセッサによって受信されたときにスタートする。第２のタイマは、そのスレーブがトランザクションをコミットする準備ができたときにスタートする。第１のタイマは、更新トランザクションの各ステップを受信した後にリセットされる。第１のタイマが、更新トランザクションの次のステップを受信する前に「タイムアウト」すなわち満期になった場合、そのスレーブプロセッサは現在のトランザクションをアボートする。更新トランザクションの完了後、マスタデータベースプロセッサは、スレーブプロセッサがデータベース更新トランザクションをコミットすることができるかどうかを問い合わせるコミット要求(request to commit)メッセージをスレーブプロセッサに対して発行する。このコミット要求メッセージに対する、各スレーブプロセッサによるコミット投票(vote to commit)メッセージが、各スレーブプロセッサの第２のタイマをトリガする。コミット要求メッセージがマスタプロセッサからスレーブプロセッサへ送られた後、新たなトランザクションが受信されるまで、第１のタイマは無効にされる。第２のタイマが「タイムアウト」した場合、そのスレーブプロセッサはトランザクションをコミットする。
【００１３】
スレーブプロセッサの第１のタイマが「タイムアウト」した場合、そのスレーブプロセッサは現在のトランザクションをアボートし、グローバルアボートメッセージをすべてのスレーブプロセッサへ送る。グローバルアボートメッセージを受信したことに応答して、グローバルアボートメッセージを受信したスレーブプロセッサも現在のトランザクションをアボートし、自己のグローバルアボートメッセージをすべてのスレーブプロセッサへ送信する。その結果、すべてのスレーブプロセッサは現在のトランザクションをアボートし、プロセッサのネットワークは同一の状態になる。
【００１４】
好ましい実施例では、マスタデータベースプロセッサによって実行される各更新トランザクションの記録がジャーナルあるいはログとしてマスタデータベースプロセッサによって管理される。このジャーナルあるいはログは、好ましくは、巡回キューまたはバッファである。ジャーナル内の古い記録は最終的に最新の更新トランザクションで上書きされる。各スレーブプロセッサも、そのスレーブプロセッサが正しくコミットすることができた少なくとも最近のデータベース更新トランザクションの記録を管理する。
【００１５】
高信頼性データベースシステムでは、１つのスレーブプロセッサが故障するかあるいはそれとの通信が失われると、故障したデータベースコピーの停止中に、稼働中の他のデータベースコピーが更新される可能性がある。最終的に、故障したスレーブプロセッサがサービスに復帰すると、その直後には、ネットワーク全体の他のデータベースコピーでカレントになっているデータを有していない可能性がある。前に損失したデータベースコピーを更新するため、そのスレーブプロセッサが停止中に実行されたトランザクションのジャーナル（ログ）を用いて、その故障したスレーブプロセッサが実行できなかったトランザクションを再作成する。各スレーブプロセッサは、最後に完了した最近のトランザクションの識別を追跡（記録）している。この最終完了トランザクションの記録から、マスタプロセッサおよび故障したプロセッサは、マスタ内のジャーナルに記録されている完了トランザクションを用いて、自己を他のプロセッサに再同期させる。
【００１６】
トランザクションおよび順序識別子ならびに関連するデータはジャーナルに入力される。これらの識別子に基づいて、パティシパントは、次に期待されるタスクが何であるかを、そのタスクの性質を知ることを必要とせずに判定することができる。故障が補正された後、故障していたパティシパントは、ジャーナルから、実行することができなかった最初のトランザクションを要求し、その後、その最初の未実行トランザクションに続くトランザクションを要求する。パティシパントは、すべての未実行トランザクションを実行した後、ネットワークに再加入し、新たなトランザクションを受け取ることができる。
【００１７】
【発明の実施の形態】
図１に、マスタプロセッサ１０２と少なくとも１つのバックアップマスタプロセッサ１０４を含むプロセッサの分散ネットワーク１００を示す。図１はまた、いくつかのスレーブ（パティシパント）プロセッサ１０６、１０８および１１０も示している。各プロセッサ１０２、１０４、１０６、１０８および１１０は、図示のように、これらのプロセッサのそれぞれに対応するデータベース１１２、１１４、１１６、１１８および１２０を制御する。１１２、１１４、１１６、１１８および１２０のデータベースレコードは、例えば、ディスクレコードからなる（テープなどの磁気媒体にも記憶可能であり、あるいは、ランダムアクセスメモリに記録することも可能である）。各データベース１１２、１１４、１１６、１１８および１２０は同じデータを含む。また、各プロセッサ１０２、１０４、１０６、１０８および１１０は、高速データ相互接続１４０を通じて互いに通信する。高速データ相互接続１４０は、例えば、Ethernetネットワークなどの適当なデータリンクからなり、これによりデータは図１の各プロセッサどうしの間で交換される。図１の分散プロセッサネットワーク１００は例えば電話交換ネットワークで用いることが可能である。その場合、各プロセッサ１０２、１０４、１０６、１０８および１１０は呼処理を行う。あるいは、分散プロセッサネットワーク１００は、航空機予約システムや銀行処理記録のような他のアプリケーションでも使用可能であるが、これらに限定されない。
【００１８】
データベース１１２、１１４、１１６、１１８および１２０は、顧客レコード、電話番号、航空機フライト予約スケジュールなどを含む。動作時には、各プロセッサは対応するデータベースにアクセスしてトランザクションを処理する必要があり、ほとんどのアプリケーションでは、各データベース１１２、１１４、１１６、１１８および１２０が分散プロセッサネットワーク１００内の他のデータベースの正確なコピーであることが要求される。
【００１９】
トランザクションがデータベースプロセッサ１０２、１０４、１０６、１０８および１１０によって処理されると、各データベースコピーが互いに同一であることを保証するためにデータベースコピー１１２、１１４、１１６、１１８および１２０は更新される必要が生じる。
【００２０】
マスタデータベースプロセッサ１０２は、データベースコピー１１４、１１６、１１８および１２０を更新する。データベースコピー１１６、１１８および１２０で更新される必要のある１つのデータベース内のデータベース記録は、マスタデータベースプロセッサが、更新レコードを各データベースコピー１１２、１１４、１１６、１１８および１２０へ送信することによって更新される。マスタデータベースプロセッサは、各スレーブ（パティシパント）プロセッサ１０６、１０８および１１０に対して、各スレーブ（パティシパント）プロセッサが更新を受け入れる準備ができているかどうかを判定するよう質問する。その後、マスタデータベースプロセッサは、更新されるべきレコードをスレーブ（パティシパント）プロセッサ１０６、１０８および１１０にコピーし、これらのスレーブ（パティシパント）プロセッサにコピーが送られた後、これらのスレーブ（パティシパント）プロセッサは、マスタプロセッサ１０２によって、更新が正しく完了したかどうかを調べるよう質問される。
【００２１】
［故障したスレーブプロセッサの再同期］
１つまたは複数のスレーブ（パティシパント）プロセッサが故障した場合、マスタプロセッサ１０２は、それに対応するデータベースコピーを更新することができない。例えば、スレーブデータベースプロセッサ１０６が故障した場合、データベースコピー１１６への更新を行うことができない。この故障したプロセッサが最終的にサービスに復帰して障害から回復すると、そのデータベースは、故障して停止中にマスタによって更新されたかも知れない他のデータベースコピーと一致するように更新する必要が生じる。
【００２２】
ここで故障（障害）という用語は、データベースプロセッサ１０６、１０８および１１０がデータベース更新トランザクションを受け取ることができないプロセッサ状態のことである。故障は、何らかの条件によりデータベースプロセッサ１０６、１０８および１１０が、分散プロセッサネットワーク１００に再加入する前に回復を必要とする状態に入ることを余儀なくされた場合に起こる。定義により、故障とは、データベースプロセッサ１０６、１０８および１１０が故障のときには定数(quorum)のアクティブなメンバであったことを意味する。
【００２３】
故障したプロセッサが回復（サービスに復帰）した後にその故障したプロセッサのデータベースを更新する（同期させる）方法は、各スレーブ（パティシパント）プロセッサが故障前に完了することができた最後のデータベース更新を記録していることを必要とする。各データベースプロセッサ１０６、１０８、１１０ならびに１０２および１０４は、そのプロセッサによって正しく寒行された最後のデータベース更新の何らかの指標を記録している必要がある。このような最終完了レコードの指標は、例えば、マスタプロセッサ１０２の指示のもとに最後に完了した更新を識別するために任意に割り当てられた番号であって、プロセッサのランダムアクセスメモリ（ＲＡＭ）や、ディスクなどの媒体のファイルあるいはその一部として、またはその他のデータの読み書きが可能な適当なデバイスに記憶される。あるいは、各プロセッサは、最終稿新トランザクションの完全なレコードを保持することも可能である。
【００２４】
マスタデータベースプロセッサ１０２、およびバックアッププロセッサ１０４内には、それぞれ、ジャーナル（ログ）１２２および１２４が保持される。これは、マスタプロセッサ１０２によって実行され正しく完了したデータベース更新トランザクションのステップの記録である。このジャーナルは、データベース更新トランザクションのステップを記録する。
【００２５】
好ましい実施例では、データベース更新ジャーナル１２２および１２４はそれぞれ巡回バッファであり、データベース更新トランザクションが順次記憶される。当業者には認識される通りの巡回バッファの特性により、最終的に、古いデータベース更新記録は最近の更新トランザクションで上書きされる。
【００２６】
あるいは、データベース更新ジャーナルは、ＦＩＦＯまたはＬＩＦＯバッファとして構成されることも可能である。これらも、当業者には認識される通り、マスタプロセッサ１０２によって完了されたトランザクションを記録する別の方法である。
【００２７】
故障したプロセッサの回復後、対応するデータベースコピーの更新（再同期）は、故障していたプロセッサがマスタプロセッサ１０２に最後に正しく完了したデータベース更新の識別（指標）を通知することによって実現される。図１には、各データベースプロセッサ１０６、１０８および１１０内に、最終完了データベース更新トランザクションの適当な指標を記憶するデータ記憶要素１２６、１２８および１３０も示されている。故障していたプロセッサからのこの情報を用いれば、マスタプロセッサ１０２は、その後に、ジャーナルから、故障していたデータベースプロセッサによって最後に正しく完了されたデータベース更新の後に起きたデータベース更新トランザクションの完全なレコードをコピーすればよい。
【００２８】
当業者には認識されるように、マスタデータベースプロセッサ１０２によるジャーナル記録の更新は、マスタデータベースプロセッサがデータベース更新トランザクションのレコードを故障していたプロセッサへコピーするときに行うことが可能である。このようにして、マスタデータベースプロセッサ１０２は、例えば、故障したプロセッサ１０６、１０８および１１０に、故障していたプロセッサがオンラインに復帰する過程で要求されたデータベース更新レコードをコピーすることができる。
【００２９】
データベースレコード１１２、１１４、１１６、１１８および１２０は、例えば、ディスクレコードからなる（テープなどの磁気媒体にも記憶可能であり、あるいは、ランダムアクセスメモリに記録することも可能である）。同様に、ジャーナル１２２および１２４は、ディスクレコード、テープレコードとして保持することも可能であり、あるいは、プロセッサのランダムアクセスメモリに記憶することも可能である。当業者には認識されるように、データベースプロセッサ１０２、１０４、１０６、１０８および１１０は適当なコンピュータとすることが可能である。
【００３０】
［マスタプロセッサの故障］
トランザクションの進行中または２相コミットの間にマスタデータベースプロセッサ１０２が故障した場合、未完了のトランザクションに対する適切な処置をしなければならない。そうでない場合、分散データベースネットワークは、不確定な状態になる。例えば、スレーブデータベースプロセッサ１０６はマスタデータベースプロセッサ１０２での問題を認識していない可能性があり、その場合、更新トランザクションのコミットに進んでしまう。データはデータベース１１６にコミットされる。しかし、スレーブデータベースプロセッサ１０８がマスタデータベースプロセッサ１０２での問題を認識していると、更新トランザクションをアボートしてしまう。データベース１１６にコミットされたデータはデータベース１１８にはコミットされない。従って、データベース１１６に含まれるデータはデータベース１１８に含まれるデータと異なることになる。これを不確定状態という。分散プロセッサネットワーク１００では、ネットワークが正しく動作するにはデータベース１１２、１１４、１１６、１１８および１２０が同じデータを含まなければならないからである。
【００３１】
マスタデータベースプロセッサ１０２の故障からの回復方法は、データベースプロセッサ１０４、１０６、１０８および１１０が更新トランザクションに関して同一の状態になることを必要とする。すなわち、すべてのデータベースプロセッサがそのトランザクションをコミットするか、あるいは、すべてのデータベースプロセッサがそのトランザクションをアボートしなければならない。従来技術に対する改良として、トランザクション処理は、新たなマスタの指令なしに、しかも、トランザクションを再実行したりもとに戻したりすることなく、実現される。
【００３２】
図２に示すように、データベースプロセッサ１１０には２個のタイマがある。各データベースの第１のタイマはトランザクションステップタイマ１５２である。トランザクションステップタイマ１５２は、特定の長さ（タイマウィンドウという。）に設定される。トランザクションステップタイマ１５２は、データベース更新トランザクションが受信されたときにスタートする。データベースプロセッサ１１０がタイマウィンドウ内に更新トランザクションの各ステップを受信しない場合（すなわち、トランザクションの終了ステップを受信しない場合）、データベースプロセッサは自動的にそのトランザクションをアボートする。トランザクションステップタイマ１５２は、トランザクションのステップが受信されるごとにリセットされる。さらに、トランザクションステップタイマ１５２は、データベースプロセッサ１１０が、マスタデータベースプロセッサ１０２からコミット要求メッセージを受信した場合に無効にされる。
【００３３】
データベースプロセッサ１１０の第２のタイマは自動コミットタイマ１５０である。データベースプロセッサ１１０がトランザクションをコミットすることを承認（投票）するとき、コミット投票メッセージがマスタデータベースプロセッサ１０２へ送られる。自動コミットタイマ１５０は、コミット投票メッセージが送られるときにスタートする。データベースプロセッサは、２相コミット手続きにおいてトランザクションをコミットすることに投票した場合、データベースプロセッサがアボートメッセージを受け取らない限り、自動コミットタイマ１５０が満期になるとそのトランザクションを自動的にコミットする。
【００３４】
本発明のもう１つの特徴は、グローバルアボートメッセージングシステムである。データベースプロセッサ１０４、１０６、１０８、または１１０のいずれかがトランザクションをアボートした場合、そのデータベースプロセッサは、アボートが生じたことを他のすべてのプロセッサが知るように、アボートメッセージをブロードキャストする。アボートメッセージの受信により、データベースプロセッサはトランザクションをアボートすることを強制される。場合によっては、アボートメッセージの受信は個々のデータベースプロセッサにとって必要でも有用でもないこともある。その場合、アボートメッセージは捨てられる。
【００３５】
例えば、データベースプロセッサ１１０がトランザクションをアボートした場合、グローバルアボートメッセージがデータベースプロセッサ１１０からデータベースプロセッサ１０２、１０４、１０６、および１０８へ送られる。データベースプロセッサ１０２、１０４、１０６、および１０８は、グローバルアボートメッセージを受信し、トランザクションをアボートする。また、データベースプロセッサ１０６が独立にトランザクションをアボートすることを決定した場合、データベースプロセッサ１０６によって受信されたアボートメッセージは重複しており、捨てられる。
【００３６】
トランザクションステップタイマ１５２のタイマウィンドウは、トランザクションステップタイマ１５２が自動コミットタイマ１５０より短くなるような適当な長さに設計することができる。そうすると、いくつかのデータベースプロセッサがコミットすることに投票し、いくつかのデータベースプロセッサがアボートすることを決定した場合、トランザクションステップタイマ１５２は満期となり、アボートするデータベースプロセッサはタイムアウトとなってグローバルアボートメッセージを送信する。コミットすることに投票し従ってそれぞれの自動コミットタイマが進行しているデータベースプロセッサはグローバルアボートメッセージを受信し、それぞれの自動コミットタイマをキャンセルすることになる。データベースプロセッサ１０２、１０４、１０６、１０８、および１１０はアボートし、すべてのデータベースは同一の状態になる。
【００３７】
本発明が対処する２つのマスタ故障状態がある。すなわち、マスタデータベースプロセッサ１０２がトランザクションの進行中に故障する場合と、マスタデータベースプロセッサ１０２が２相コミット中に故障する場合である。
【００３８】
第１の状態では、マスタデータベースプロセッサ１０２は、トランザクションの進行中に、すなわち、トランザクションにおけるあるステップが進行中であるがデータベースプロセッサ１０４、１０６、１０８、および１１０がトランザクションをコミットすることに投票する前に、故障する。マスタデータベースプロセッサ１０２がこの時点で故障した場合、データベースプロセッサ１０４、１０６、１０８および１１０のトランザクションステップタイマは満期（タイムアウト）になる。トランザクションステップタイマのタイムアウトに応答して、データベースプロセッサ１０４、１０６、１０８および１１０はトランザクションをアボートする。
【００３９】
第２の状態では、マスタデータベースプロセッサ１０２は２相コミット中に故障する。この時点で、データベースプロセッサ１０４、１０６、１０８および１１０は更新トランザクションの終了ステップを受信しているか、または、マスタがコミット要求メッセージを送信しておりデータベースプロセッサ１０４、１０６、１０８および１１０がマスタデータベースプロセッサ１０２へコミット投票メッセージを送る準備ができている状態である。データベースプロセッサ１０４、１０６、１０８および１１０がが更新トランザクションの終了ステップを受信した後には３つの可能なシナリオがある。
【００４０】
第１の場合として、データベースプロセッサ１０４、１０６、１０８および１１０のいずれも、マスタデータベースプロセッサ１０２が故障する前にトランザクションをコミットすることに投票していない場合がある。一例として、データベースプロセッサ１０４、１０６、１０８および１１０が更新トランザクションの最終ステップを受信した後、各プロセッサがコミットすることができるかどうかを質問するメッセージをマスタデータベースプロセッサ１０２が送信する前に、マスタデータベースプロセッサ１０２が故障する場合である。このシナリオでは、すべてのデータベースプロセッサがタイムアウトする。トランザクションステップタイマが依然としてアクティブであり、すべてのデータベースプロセッサがトランザクションをアボートすることになるからである。トランザクションステップタイマは、対応するデータベースプロセッサがコミット要求メッセージを受信した後に無効にされる。
【００４１】
第２の場合として、データベースプロセッサ１０４、１０６、１０８および１１０がコミットをすることに投票した後、マスタが故障する場合がある。このシナリオでは、すべてのデータベースプロセッサの自動コミットタイマがタイムアウトし、すべてのデータベースプロセッサはトランザクションをコミットすることになる。
【００４２】
第３の場合は、例えば、データベースプロセッサ１０４および１０６がトランザクションをコミットすることに投票し、データベースプロセッサ１０８および１１０がアボートすることに決定した場合である。上記のグローバルアボートメッセージングシステムのもとで、アボートするデータベースプロセッサはコミットするデータベースプロセッサよりも早くタイムアウトし、コミットするデータベースプロセッサがトランザクションをコミットする前にグローバルアボートメッセージを受信するようになっている。従って、すべてのデータベースプロセッサはトランザクションをアボートし、データベース１１２、１１４、１１６、１１８および１２０は同一のままとなる。
【００４３】
図３、図４、図５、図６、図７および図８は、故障していないすべてのパティシパントが外部からの調整なしで自動的に障害回復を行い更新トランザクションを完了することを可能にする方法のさまざまな特徴を示す流れ図である。プロセスを完全に理解するためには、マスタデータベースプロセッサ１０２、バックアップマスタデータベースプロセッサ１０４、ならびにスレーブデータベースプロセッサ１０６、１０８および１１０は、さまざまなアルゴリズムが以下に列挙されるステップを実行するようにプログラムされていることを理解することが重要である。
【００４４】
図３および図４において、ステップ２１０で、マスタデータベースプロセッサ１０２（図３には示さない）のジャーナル１２２（図１および図２ならびに上記参照）が作成される。ステップ２２０で、データベース更新トランザクションのステップがジャーナル１２２に記録される。ステップ２３０および２４０で、図示のように、各スレーブデータベースプロセッサ１０６、１０８および１１０の２個のタイマが作成される。ステップ２５０で、スレーブプロセッサ１０６、１０８および１１０は、データベース更新トランザクションの最初が受信されたかどうかを問い合わせる。この問合せは、スレーブデータベースプロセッサがデータベース更新トランザクションを受信するまで連続ループで継続される。ステップ２６０で、データベース更新トランザクションを受信したスレーブプロセッサの第１タイマがスタートする。
【００４５】
ステップ２７０で、データベース更新トランザクションを受信したスレーブプロセッサは、データベース更新トランザクションの次のステップが受信されたかどうかを問い合わせる。データベース更新トランザクションの次のステップが受信された場合、ステップ２８０で、第１タイマはリセットされてリスタートし、ステップ２７０で、データベース更新トランザクションを受信したスレーブプロセッサは再び、次のステップを受信したかどうかを問い合わせる。ステップ２７０においてデータベース更新トランザクションの次の部分が受信されていない場合、ステップ２９０で、データベースは、コミット要求メッセージがマスタデータベースプロセッサ１０２から受信されたかどうかを問い合わせる。コミット要求メッセージが受信されていない場合、ステップ３００で、スレーブプロセッサは、第１タイマが満期になったかどうかを問い合わせる。第１タイマが満期でない場合、ステップ２７０で、スレーブプロセッサは、データベース更新トランザクションの次のステップが受信されたかどうかを問い合わせる。第１タイマが満期になった場合、スレーブプロセッサは、ステップ３１０で、トランザクションをアボートし、ステップ３２０で、グローバルアボートメッセージを他のすべてのスレーブプロセッサへ送る。スレーブプロセッサは、新たなデータベース更新トランザクションを受け取ることができる状態となるため、ステップ２５０に復帰する。
【００４６】
ステップ２９０で、コミット要求メッセージがマスタデータベースプロセッサ１０２から受信されている場合、ステップ３３０で、第１タイマがキャンセルされる。ステップ３４０で、スレーブプロセッサはコミット投票メッセージをマスタデータベースプロセッサ１０２へ送る。ステップ３３０で、コミット投票メッセージを送信したスレーブプロセッサの第２タイマがスタートする。第２タイマのスタート後、ステップ３６０で、対応するスレーブプロセッサは、第２タイマが満期になったかどうかを問い合わせる。第２タイマが満期になった場合、ステップ３７０で、データベース更新トランザクションがコミットされる。ステップ３８０で、適当なスレーブデータベースプロセッサが、最後にコミットされたデータベース更新トランザクションの指標を記録し、新たなデータベース更新トランザクションの開始を受信する準備ができる。
【００４７】
第２タイマが満期でない場合、ステップ３９０で、スレーブデータベースプロセッサは、アボートメッセージが受信されているかどうかを問い合わせる。アボートメッセージが受信されていない場合、ステップ３６０で、スレーブデータベースプロセッサは再び、第２タイマが満期になったかどうかを問い合わせる。アボートメッセージが受信されている場合、スレーブデータベースプロセッサは、ステップ３９５で、データベース更新トランザクションをアボートし、ステップ３９７で、すべてのスレーブプロセッサへグローバルアボートメッセージを送る。データベース更新トランザクションをアボートしたスレーブプロセッサは、新たなデータベース更新トランザクションを受信する準備ができる。
【００４８】
図５は、故障したスレーブプロセッサの障害回復の流れ図である。ステップ４１０で、マスタデータベースプロセッサ１０２（図５には示さない。）のジャーナル１２２（図１および図２ならびに上記参照）が作成された後、ステップ４２０で、データベース更新トランザクションのステップがジャーナル１２２に記録される。ステップ４３０で、スレーブデータベースプロセッサ１０６、１０８および１１０は、各プロセッサでコミットされた最後に完了したデータベース更新トランザクションの指標を記録する。ステップ４５０で、スレーブプロセッサ１０６、１０８または１１０の故障がある場合、その故障以後のすべてのデータベース更新トランザクションがジャーナルから適当な故障したプロセッサにコピーされる。
【００４９】
図６は、トランザクションステップタイマ１５２（図２および上記参照）の一般的動作の流れ図である。ステップ５１０で、第１タイマが作成されスレーブプロセッサに割り当てられると、ステップ５２０で、スレーブプロセッサは、更新トランザクションが受信されたかどうかを問い合わせる。データベース更新トランザクションが受信されていない場合、アルゴリズムはループし、再び、データベース更新トランザクションが受信されたかどうかを問い合わせる。データベース更新トランザクションがスレーブプロセッサによって受信されている場合、ステップ５３０で、データベース更新トランザクションを受信したスレーブプロセッサの第１タイマがスタートする。その後、ステップ５４０で、スレーブデータベースプロセッサは、第１タイマが満期になったかどうかを問い合わせる。第１タイマが満期になった場合、ステップ５５０で、データベース更新トランザクションはアボートされ、ステップ５６０で、グローバルアボートメッセージがすべてのスレーブプロセッサへ送られる。第１タイマが満期でない場合、ステップ５７０で、スレーブデータベースプロセッサは、データベース更新トランザクションの一部が受信されているかどうかを問い合わせる。受信されていない場合、ステップ５４０で、スレーブデータベースプロセッサは再び、第１タイマが満期になったかどうかを問い合わせる。データベース更新トランザクションの一部が受信されている場合、ステップ５８０で、第１タイマはリセットされ、さらに、第１タイマはリスタートされる。
【００５０】
図７は、自動コミットタイマ１５０（図２および上記参照）の一般的動作の流れ図である。ステップ６１０で、タイマが作成された後、ステップ６２０で、スレーブデータベースプロセッサは、データベース更新トランザクションを受信したかどうかを問い合わせる。データベース更新トランザクションが受信されていないという応答であるたびに、アルゴリズムはループし、データベース更新トランザクションが受信されたかどうかの問合せを継続する。データベース更新トランザクションが受信された場合、スレーブデータベースプロセッサは、ある時点で、マスタデータベースプロセッサ１０２（図７には示していない。）からコミット要求メッセージを受け取る。コミット要求メッセージを受信した後、ステップ６４０で、スレーブデータベースプロセッサは、マスタデータベースプロセッサ１０２へコミット投票メッセージを送る。ステップ６５０で、コミット投票メッセージを送信したスレーブプロセッサのタイマがスタートする。その後、ステップ６６０で、スレーブデータベースプロセッサは、タイマが満期になったかどうかを問い合わせる。タイマが満期になった場合、ステップ６７０で、データベース更新トランザクションがコミットされる。タイマが満期でない場合、ステップ６８０で、スレーブデータベースプロセッサは、グローバルアボートメッセージが受信されたかどうかを問い合わせる。グローバルアボートメッセージが受信されていない場合、アルゴリズムはループし、ステップ６５０で再び、タイマが満期になったかどうかを問い合わせる。ステップ６８０においてグローバルアボートメッセージが受信されている場合、スレーブデータベースプロセッサは、ステップ６９０で、データベース更新トランザクションをアボートし、ステップ６９５で、グローバルアボートメッセージをすべてのスレーブプロセッサへ送る。データベース更新トランザクションをアボートしスレーブプロセッサは、新たなデータベース更新トランザクションを受け取る準備が整う。
【００５１】
図８は、自動コミットタイマ１５０とトランザクションステップタイマ１５２（いずれも図２および上記参照）の間の調整の概略を示す流れ図である。ステップ７１０で、各タイマが作成され、ステップ７２０で、各スレーブプロセッサに割り当てられると、ステップ７３０で、各スレーブデータベースプロセッサは、データベース更新トランザクションの開始が受信されたかどうかを問い合わせる。データベース更新トランザクションの開始が受信されていない場合、アルゴリズムはループし、再び、データベース更新トランザクションの開始が受信されたかどうかを問い合わせる。データベース更新トランザクションの開始が受信されている場合、ステップ７４０で、データベース更新トランザクションの開始を受信したスレーブプロセッサのトランザクションステップタイマがスタートする。ステップ７５０で、スレーブプロセッサは、第１タイマが満期になったかどうかを問い合わせる。第１タイマが満期でない場合、ステップ７６０で、スレーブデータベースプロセッサは、コミット要求メッセージがマスタデータベースプロセッサ１０２（図８には示していない。）から受信されたかどうかを問い合わせる。コミット要求メッセージが受信されていない場合、ステップ７７０で、スレーブデータベースプロセッサは、データベース更新トランザクションの一部が受信されたかどうかを問い合わせる。受信されていない場合、ステップ７５０で、スレーブデータベースプロセッサは、第１タイマが満期になったかどうかを問い合わせる。データベース更新トランザクションの一部が受信されている場合、トランザクションステップタイマはリセットされリスタートされる。
【００５２】
コミット要求メッセージがマスタデータベースプロセッサ１０２から受信されている場合、ステップ８１０で、トランザクションステップタイマが無効にされる。ステップ８２０で、スレーブデータベースプロセッサは、マスタデータベースプロセッサ１０２へコミット投票メッセージを送る。ステップ８３０で、コミット投票メッセージを送信したスレーブプロセッサの第２タイマがスタートする。ステップ８４０で、スレーブデータベースプロセッサは、第２タイマが満期になっているかどうかを問い合わせる。第２タイマが満期である場合、ステップ８５０で、スレーブデータベースプロセッサは、データベース更新トランザクションをコミットする。スレーブプロセッサは、新たなデータベース更新トランザクションを受け取る準備が整う。第２タイマが満期でない場合、ステップ８６０で、スレーブデータベースプロセッサは、アボートメッセージが受信されているかどうかを問い合わせる。アボートメッセージが受信されている場合、スレーブデータベースプロセッサは、ステップ８７０で、データベース更新トランザクションをアボートし、ステップ８８０で、他のすべてのスレーブプロセッサへグローバルアボートメッセージを送る。スレーブデータベースプロセッサは、新たなデータベース更新トランザクションを受け取る準備が整う。
【００５３】
【発明の効果】
以上述べたごとく、本発明によれば、接続されたデータベースプロセッサのネットワークは、マスタデータベースプロセッサまたはいずれかのスレーブプロセッサの故障に対処することが可能となり、それにより、故障状態を修復するために処理機能を妨げることを必要とすることがなくなる。回復すなわち再同期のプロセスは、ネットワーク環境において進行中の処理とは独立に行われるため、ネットワークの信頼性が増大するとともに、故障から回復するシステムの休止時間が短縮される。
【図面の簡単な説明】
【図１】分散データベースシステムの概略ブロック図である。
【図２】マスタデータベースプロセッサおよびスレーブデータベースプロセッサの概略ブロック図である。
【図３】故障していないすべてのパティシパントが外部からの調整なしで自動的に障害回復を行い更新トランザクションを完了することを可能にする方法のさまざまな特徴を示す流れ図である。
【図４】故障していないすべてのパティシパントが外部からの調整なしで自動的に障害回復を行い更新トランザクションを完了することを可能にする方法のさまざまな特徴を示す流れ図である。
【図５】故障したスレーブプロセッサの障害回復の流れ図である。
【図６】トランザクションステップタイマの一般的動作の流れ図である。
【図７】自動コミットタイマの一般的動作の流れ図である。
【図８】自動コミットタイマとトランザクションステップタイマの間の調整の概略を示す流れ図である。
【符号の説明】
１００  分散プロセッサネットワーク
１０２  マスタデータベースプロセッサ
１０４  バックアップマスタデータベースプロセッサ
１０６  スレーブデータベースプロセッサ
１０８  スレーブデータベースプロセッサ
１１０  スレーブデータベースプロセッサ
１１２  データベース
１１４  データベース
１１６  データベース
１１８  データベース
１２０  データベース
１２２  ジャーナル
１２４  ジャーナル
１２６  データ記憶要素
１２８  データ記憶要素
１３０  データ記憶要素
１４０  高速データ相互接続
１５０  自動コミットタイマ
１５２  トランザクションステップタイマ
【図１】
0003822381.tif 000002
【図２】
0003822381.tif 000003
【図３】
0003822381.tif 000004
【図４】
0003822381.tif 000005
【図５】
0003822381.tif 000006
【図６】
0003822381.tif 000007
【図７】
0003822381.tif 000008
【図８】
0003822381.tif 000009