(57)【特許請求の範囲】
【請求項１】
プライマリ突き合わせサーバに対してフォールトトレランスを提供する方法であって、前記プライマリ突き合わせサーバは、前記プライマリ突き合わせサーバによる処理の完了に依存して、第１のトランザクションをその受信に対応して処理し、それに基づく第１のプライマリ結果を生成するように動作していて、前記第１のトランザクションは第１の型式と第２の型式のうちの一方である、プライマリ突き合わせサーバに対するフォールトトレランスを提供する方法において、
前記プライマリ突き合わせサーバの前記第１のトランザクションの受信の後に、当該プライマリ突き合わせサーバが前記第１のプライマリ結果を生成する可能性が低いと判定し、それに基づき、当該プライマリ突き合わせサーバが前記動作を完了するのを阻止する段階と、
前記プライマリ突き合わせサーバが前記第１のプライマリ結果を生成した後に、当該プライマリ突き合わせサーバによって受信されている前記第１のトランザクションの第１のコピーを処理し、それに基づく第１のバックアップ結果を生成するように動作する第１のバックアップ突き合わせサーバを提供する段階と、
前記プライマリ突き合わせサーバによって、前記第１のトランザクションが前記第１の型式であると判定し、それに基づき、前記プライマリ突き合わせサーバによる前記動作の完了とは独立に、当該第１のトランザクションを処理し、それに基づく前記第１のプライマリ結果を生成する段階と、
前記プライマリ突き合わせサーバによって、前記第１のトランザクションが前記第２の型式であると判定し、それに基づき、前記プライマリ突き合わせサーバによる前記動作の完了を条件として、当該第１のトランザクションを処理し、それに基づく前記第１のプライマリ結果を生成する段階と、を含んでいる方法。
【請求項２】
前記判定する段階は、更に、前記阻止する段階に先立って、前記動作の完了が妨げられていることを理由に前記プライマリ突き合わせサーバが前記第１のプライマリ結果を生成する可能性が低いと判定し、それに基づき、代わりのやり方で前記動作を完了させる段階を含んでいる、請求項１に記載の方法。
【請求項３】
前記プライマリ突き合わせサーバは、ソフトウェアアプリケーション、プロセッサ、又はそれらの組合せを備えている、請求項１に記載の方法。
【請求項４】
前記阻止する段階は、更に、前記プライマリ突き合わせサーバに自己終了させる段階を含んでいる、請求項１に記載の方法。
【請求項５】
前記第１のトランザクションは、着信してくるトレーダー注文、注文取り消し、又はそれらの組合せを含んでいる、請求項１に記載の方法。
【請求項６】
プライマリ突き合わせサーバに対してフォールトトレランスを提供するためのシステムであって、前記プライマリ突き合わせサーバは、前記プライマリ突き合わせサーバによる処理の完了に依存して、第１のトランザクションをその受信に対応して処理し、それに基づく第１のプライマリ結果を生成するように動作していて、プライマリ突き合わせサーバに対するフォールトトレランスを提供するためのシステムにおいて、
前記プライマリ突き合わせサーバに連結されていて、当該プライマリ突き合わせサーバの前記第１のトランザクションの受信の後に、当該プライマリ突き合わせサーバが前記第１のプライマリ結果を生成する可能性が低いと判定し、それに基づき、当該プライマリ突き合わせサーバが前記動作を完了するのを阻止するように動作する障害検出部と、
前記プライマリ突き合わせサーバが前記第１のプライマリ結果を生成した後に、当該プライマリ突き合わせサーバによって受信されている前記第１のトランザクションの第１のコピーを処理し、それに基づく第１のバックアップ結果を生成するように動作する第１のバックアップ突き合わせサーバと、を備えており、
前記第１のトランザクションは、第１の型式か第２の型式の一方であり、前記プライマリ突き合わせサーバは、更に、
前記第１のトランザクションが前記第１の型式であると判定し、それに基づき、前記プライマリ突き合わせサーバによる前記動作の完了とは独立に、当該第１のトランザクションを処理し、それに基づく前記第１のプライマリ結果を生成するように、及び
前記第１のトランザクションが前記第２の型式であると判定し、それに基づき、前記プライマリ突き合わせサーバによる前記動作の完了を条件として、当該第１のトランザクションを処理し、それに基づく前記第１のプライマリ結果を生成するように、動作する、システム。
【請求項７】
前記障害検出部は、更に、前記阻止に先立って、前記動作の完了が妨げられていることを理由に前記プライマリ突き合わせサーバが前記第１のプライマリ結果を生成する可能性が低いと判定し、それに基づき、代わりのやり方で前記動作を完了させるように動作する、請求項６に記載のシステム。
【請求項８】
前記プライマリ突き合わせサーバは、ソフトウェアアプリケーション、プロセッサ、又はそれらの組合せを備えている、請求項６に記載のシステム。
【請求項９】
前記障害検出部は、更に、前記プライマリ突き合わせサーバに自己終了させるように動作する、請求項６に記載のシステム。
【請求項１０】
前記第１のトランザクションは、着信してくるトレーダー注文、注文取り消し、又はそれらの組合せを含んでいる、請求項６に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、３７Ｃ．Ｆ．Ｒ．第１．５３条（ｂ）の下に、２００８年８月８日出願の米国特許出願第１２／１８８，４７４号（弁理士事件番号第４６７２／６９０号）で現在の米国特許第 号の一部継続出願であり、前記は３７Ｃ．Ｆ．Ｒ．第１．５３条（ｂ）の下に、２００６年８月１１日出願の米国特許出願の第１１／５０２，８５１号（弁理士事件番号第４６７２／５８４号）で現在の米国特許第 号の継続出願であり、上記各特許出願の開示全体をこれにより参考文献として援用する。
【背景技術】
【０００２】
フォールトトレランス（Ｆａｕｌｔ  Ｔｏｌｅｒａｎｃｅ（耐障害性））は、概して、システムのエラーのある状態をエラーが検出されるや直ちに覆い隠すか又は当該状態から回復する能力をいう。フォールトトレランスは、概して、ミッションクリティカルとされるシステム／アプリケーションには必須である。ミッションクリティカルとは、概して、何らかの欠くことのできない動作であって、その重要不可欠な機能の遂行中には干渉も妥協もシャットダウンも寛容され得ない動作をいい、例えば、通常の業務時間中に故障することがあってはならない何らかのコンピュータプロセスがそうである。例示としてのミッションクリティカル環境には、業務上の基幹的なプロセスの制御、金融、保健、安全、及び保安が含まれる。これらの環境は、概して、それらのコア機能を妥協してでも紛失や破損を起こさせてはならないデータを監視、記憶、サポート、及び通信している。
【０００３】
フォールトトレランスが欠かせない１つの例示としての環境は、金融市場であり、具体的には、電子金融取引所である。電子取引所を実装しているシステムは、注文を受信して突き合わせたり別のやり方で取引を完結させ、そうしてマーケットプレースを実施させて、その中で交換が円滑化されるようにしている。市場の安定性、信頼性、及び受容性を確約するには、一貫性のある高信頼度の動作が重要不可欠である。
【０００４】
フォールトトレラントとは、概して、或る構成要素が故障した時に、バックアップ構成要素又はバックアップ手続きが取って代わり、サービスの損失を実質的に殆ど或いは一切生じさせないように設計されているコンピュータシステム又は構成要素を表す。フォールトトレランスは、ソフトウェアを用いて提供されていることもあればハードウェアに組み込んだり或いは何らかの組合せにより提供されていることもある。例えば、ソフトウェア実装では、オペレーティングシステムは、プログラマーがトランザクション内の所定のポイントで重要不可欠なデータを「チェックポイント処理」できるようにするインターフェースを提供していることもある。ハードウェア実装では、プログラマーは、機械のフォールトトレラント能に気付いている必要はない。例えば、ハードウェアレベルでは、フォールトトレランスはそれぞれのハードディスク構成要素を重複化することによって実現させることができ、例えば、ディスクをミラーリングするとか、複数のプロセッサを一体に「ロックステップ」して正確性を期すためにそれらの出力を比較するなどがある。異常が起こったら、障害のある構成要素が判定され、サービスから外されるが、機械はいつも通りに機能し続ける。
【０００５】
要求されるフォールトトレランスのレベルは、一般的に、システムの諸要件の必要性に従って定義され、即ち、エラー時の受容可能な挙動である、例えばエラーは検出されて訂正されなくてはならないかそれとも検出されるだけでよいかとか、その様なアクションはどれほど素早くとられなくてはならないかといった様な挙動を明確に記している規格の必要性に従って定義される。
【０００６】
フォールトトレランスをシステムに提供する１つの方法は、システムの重要不可欠な構成要素のうち１つ又はそれ以上に冗長性を加えることである。冗長とは、コンピュータ又はネットワークシステムの構成要素、例えばファン、ハードディスクドライブ、サーバ、オペレーティングシステム、スイッチ、及び／又は通信リンクなどが、プライマリリソースが万一故障した場合にそれらをバックアップするためにインストールされていることを表す。この目的でよく使用されているのは３つの型式の冗長スキームであり、即ち：
ワン・フォー・Ｎ（１：Ｎ）―アクティブ構成要素Ｎ個毎に１つの待機構成要素がある。
ワン・フォー・ワン（１：１）―アクティブ構成要素それぞれに１つの待機構成要素がある。
ワン・プラス・ワン（１＋１）―ワン・フォー・ワンスキームに似ているが、但し、ワン・プラス・ワンの場合、トラフィックはアクティブ構成要素と待機構成要素の両方の側で同時に伝送される。（トラフィックは通常待機側では無視される。）ワン・プラス・ワン式冗長性の一例に、リンク故障によってデータトラフィックの喪失が引き起こされるのを回避する１＋１  ＳＯＮＥＴ／ＳＤＨ  ＡＰＳスキームがある。
【０００７】
処理用構成要素のための冗長的な動作を提供する場合、冗長論理の結果を比較してどの構成要素が正確かを選抜するのに投票の論理が使用されることがある。例えば、トリプルモード冗長性では、３つの冗長構成要素が提供されていて、１つの構成要素の結果が、互いに整合している他の２つと整合できなかったなら、最終結果は、整合している２つの構成要素の結果ということになる。
【０００８】
冗長システムのよく知られている例に、独立ディスク冗長アレイ（ｒｅｄｕｎｄａｎｔ  ａｒｒａｙ  ｏｆ  ｉｎｄｅｐｅｎｄｅｎｔ  ｄｉｓｋｓ）（「ＲＡＩＤ」）がある。ＲＡＩＤ（本来は、安価ディスク冗長アレイ（ｒｅｄｕｎｄａｎｔ  ａｒｒａｙ  ｏｆ  ｉｎｅｘｐｅｎｓｉｖｅ  ｄｉｓｋｓ））は、同一データを、複数のハードディスク上の異なった場所に（ひいては冗長的に）記憶する一方法である。データを複数のディスクに置くことにより、Ｉ／Ｏ（入力／出力）動作は均衡の取れたやり方でオーバーラップされ、性能が改善される。ディスクの複数化で平均障害間隔（ＭＴＢＦ）が増すことから、データを冗長的に記憶することはフォールトトレランスをも向上させる。ＲＡＩＤは、オペレーティングシステムには単一の論理ハードディスクであるように見える。ＲＡＩＤは、ディスクストライピングという技法を採用しており、この技法には、それぞれのドライブのストレージ空間を、１セクター（５１２バイト）から数メガバイトにも上る範囲の単位へ区分化することが伴う。全てのディスクのストライプがインターリーブされ、順にアドレス指定される。医用画像又は他の科学的画像の様な膨大な記録が記憶されるシングルユーザーシステムでは、ストライプは、概して、小さく（おそらくは５１２バイトに）なるように設定されており、そうすれば、単一記録が全てのディスクに行き渡り、全てのディスクを同時に読み出すことによって素早くアクセスすることができる。マルチユーザーシステムでは、性能を高めるには、典型サイズ又は最大サイズの記録を保持するのに十分に広いストライプを確立することが要件となる。これにより、ドライブを跨ぐディスクＩ／Ｏオーバーラップが可能になる。
【０００９】
少なくとも９つの型式のＲＡＩＤに加え非冗長アレイ（ＲＡＩＤ−０）があり、即ち：
ＲＡＩＤ−０：この技法は、ストライピングを有するがデータの冗長性はない。最大性能を提供するが、フォールトトレランスは提供しない。
ＲＡＩＤ−１：この型式は、ディスクミラーリングとしても知られており、データのストレージを重複させる少なくとも２つのドライブから成る。ストライピングはない。どちらのディスクも同時に読み出されるので読み出し性能が改善される。書き込み性能は、単一のディスクストレージの場合と同じである。ＲＡＩＤ−１は、マルチユーザーシステムでは最大性能と最大フォールトトレランスを提供する。
ＲＡＩＤ−２：この型式は、ディスクを跨ぐストライピングを使用しており、幾つかのディスクは、エラーチェック及び訂正（ＥＣＣ）情報を記憶している。ＲＡＩＤ−３に勝る利点はない。
ＲＡＩＤ−３：この型式は、ストライピングを使用し、１つのドライブをパリティ情報記憶の専用にしている。組み込まれているエラーチェック（ＥＣＣ）情報が、エラーを検出するのに使用される。データ回復は、その他のドライブに記録されている情報の排他的ＯＲ（ＸＯＲ）を計算することによって達成される。Ｉ／Ｏ動作は全てのドライブを同時にアドレス指定するので、ＲＡＩＤ−３ではＩ／Ｏはオーバーラップされ得ない。この理由から、ＲＡＩＤ−３は長記録アプリケーションを備えたシングルユーザーシステムに最適である。
ＲＡＩＤ−４：この型式は大ストライプを使用しており、ということは記録をどの単一ドライブからも読み出すことができることを意味する。これにより、読み出し動作にＩ／Ｏオーバーラップを活用できるようになる。書き込み動作は全てパリティドライブを更新しなければならないので、Ｉ／Ｏオーバーラップは実施できない。ＲＡＩＤ−４は、ＲＡＩＤ−５に勝る利点を提供しない。
ＲＡＩＤ−５：この型式は、回転式パリティアレイを含み、ひいては、ＲＡＩＤ−４での書き込み制限の解消を図っている。その結果、全ての読み出し及び書き込み動作をオーバーラップさせることができる。ＲＡＩＤ−５は、パリティ情報を記憶するが、冗長データを記憶しない（しかし、パリティ情報をデータを再構築するのに使用することができる）。ＲＡＩＤ−５は、アレイにつき少なくとも３つ通常は５つのディスクを必要とする。それは、性能が重大不可欠というわけではないか或いは書き込み動作を殆どしないマルチユーザーシステムに最適である。
ＲＡＩＤ−６：この型式は、ＲＡＩＤ−５に似ているが、異なったドライブを跨いで分散させた第２のパリティスキームを含んでおり、よって、極めて高いフォールトトレランス及びドライブ故障トレランスがもたらされる。
ＲＡＩＤ−７：この型式は、コントローラとしてのリアルタイム組み込みオペレーティングシステム、高速バスを介したキャッシング、及びスタンドアローンコンピュータの他の特性を含んでいる。
ＲＡＩＤ−１０：ＲＡＩＤ−０とＲＡＩＤ−１の組合せは、しばしば、ＲＡＩＤ−１０と呼称されており、ＲＡＩＤ−１より高い性能をもたらすが、コストはずっと高くなる。２つの下位型式があり、即ち：ＲＡＩＤ−０＋１では、データは、複数のディスクに跨るストライプとして編纂され、次いで、ストライプ化されたディスクセットがミラーリングされる。ＲＡＩＤ−１＋０では、データがミラーリングされ、ミラーがストライプ化される。
ＲＡＩＤ−５０（又はＲＡＩＤ−５＋０）：この型式は、一連なりのＲＡＩＤ−５群から成り、データ保護を縮減することなくＲＡＩＤ−５の性能を改善するべく、ＲＡＩＤ−０様式でストライプ化されている。
ＲＡＩＤ−５３（又はＲＡＩＤ−５＋３）：この型式は、ＲＡＩＤ−３の仮想ディスクブロックにストライピングを（ＲＡＩＤ−０様式で）使用している。これは、ＲＡＩＤ−３より高い性能をもたらすが、コストはずっと高くなる。
ＲＡＩＤ−Ｓ（パリティＲＡＩＤとしても知られている）：これは、ＥＭＣ  Ｓｙｍｍｅｔｒｉｘによるストライプ化パリティＲＡＩＤのための代わりの独自開発された方法であって、現在の機器ではもう使用されていない方法である。ＲＡＩＤ−５に似ている様に見えるが、一部の性能強化並びにディスクアレイに高速ディスクキャッシュを有することから来る増強が図られている。
【００１０】
ＲＡＩＤと似て、ＲＡＩＮ（チャネル結合、独立ノード冗長アレイ、独立ノード高信頼度アレイ、又は独立ノードランダムアレイとも呼ばれる）は、ネットワークトポロジーにおいて複数のインターフェース及び冗長ストレージと接続されているノードのクラスタである。ＲＡＩＮは、フォールトトレランスを上げるのに使用される。それは、ディスクアレイを跨ぐ代わりにノードに跨るＲＡＩＤの実装である。ＲＡＩＮは、ローカルエリアネットワーク（ＬＡＮ）又はワイドエリアネットワーク（ＷＡＮ）で複数のノードが故障した場合にも、完全自動式データ回復を提供することができる。ブラウザベースの集中型安全管理インターフェースは、単一の場所からの監視と構成を容易にする。ＲＡＩＮクラスタ内に存在し得るノードの数には制限がない。ネットワークのダウンタイムを被ることなく、新しいノードを追加したり整備を実施したりすることができる。ＲＡＩＮは、米国のカリフォルニア工科大学（Ｃａｌｔｅｃｈ）とジェット推進研究所（ＪＰＬ）と国防総省国防高等研究業務局（ＤＡＲＰＡ）での外部空間におけるコンピューティングのための研究プロジェクトで案出されたものである。研究者らは、既成の構成要素を使用して構築することのできるデータストレージの分散コンピューティングモデルを考察していた。
【００１１】
ＲＡＩＮの着想は、ＲＡＩＤ（独立ディスク冗長アレイ）技術から来ている。ＲＡＩＤは、データを単一のシステム内のハードドライブのセットの中で区分化する。ＲＡＩＮは、ストレージ空間をネットワーク内の複数のノードに跨って区分化する。ストレージの区分化はディスクストライピングと呼ばれる。ＲＡＩＮの様々な独自開発バージョンに対し幾つかの特許が付与されている。
【００１２】
データベースでは、そして処理システム、特に、処理又はトランザクション遂行を継続しながら状態を記憶又は累算する処理状態把握型処理システムでは、冗長性は、プライマリ構成要素が故障した場合に冗長要素がいつでも引き継げるように冗長構成要素がプライマリ構成要素と同期されることを確約するという追加の複雑性を生じさせる。
【００１３】
ホットスタンドバイ（ＨＳ）は、データベースサーバシステムのスムーズなフェイルオーバーをサポートする機構であり、システムの可用性、即ち、必要となったときに所望のサービスを提供する能力を、主システムが利用できなくなったときにいつでも引き継げる第２サーバシステムによって維持する機構である。ホットスタンドバイ複製スキームでは、サーバは、通常、２つの異なった役割を有しており、その第１がプライマリサーバであり、第２はセカンダリ（バックアップ、スレーブ）サーバである。ホットスタンドバイ構成は、セカンダリデータベースが、自動的に、プライマリデータベースのミラーイメージを維持する方策を提供している。セカンダリサーバ側のセカンダリデータベースは、通常、読み出し専用型式であり、それはプライマリサーバのプライマリデータベースと論理的に同一である。万一、プライマリサーバに故障が起こった場合、セカンダリサーバが引き継いで新たなプライマリサーバの役割を引き受けることができる。
【００１４】
データベースを保有するコンピュータシステムで高い可用性を実現するための方法は幾つかある。継続的ホットスタンドバイを実施する１つの既知のやり方は、システム全体、即ち、データベースとデータベースを使用しているアプリケーションと、をミラーリングすることである。システムの全ての動作は、システムのどちら側のアプリケーションでも遂行される。アプリケーションは、それぞれのトランザクションを自身のデータベースに書き込むので、両方のシステムは常に完全に同期化されている。アプリケーション及びアプリケーションそれぞれのデータベースが相互に同期していることを確約するため、概して、アプリケーションチェックポインティングと呼ばれる機構が使用されている。動作の各実行後には、アプリケーションは、何らかの手段により、他方のアプリケーションが同じ動作を実行したことを裏付ける。言い換えれば、セカンダリアプリケーションと関係付けられているセカンダリデータベースは、プライマリのデータベースとアプリケーションを精密にミラーリングする。アプリケーション処理を含めあらゆるものがフォールトトレラントでなければならないリアルタイムアプリケーションにとっては、アプリケーションレベルのミラーリングは賢い選択である。
【００１５】
プライマリのプロセスは、実際には、作業を遂行し、そしてチェックポインティング技法を使用して、周期的に、バックアップのプロセスをプライマリのプロセスと同期させる。先行技術による既知のチェックポインティング技法を用いた場合、プライマリはプライマリプロセスの状態の変更についての情報を含んだメッセージをバックアップのプロセスへ送る。各チェックポイントの直後は、プライマリのプロセスとバックアップのプロセスは同じ状態にある。
【００１６】
先行技術による他の既知のチェックポインティング方法では、状態を変更させる動作（例えば書き込み動作など）と状態を変更させない動作（例えば読み出し動作など）の間の区別はなされず、全ての動作がバックアッププロセスへチェックポイント処理される。その様なシステムは、米国特許第４，５９０，５５４号（Ｇｌａｚｅｒ−−Ｐａｒａｌｌｅｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍｓ）に示されており、そこでは、プライマリへの全ての入力はメッセージを介して提供され、プライマリへ送られた全てのメッセージはセカンダリ又はバックアップに対して利用できるようにされ、基本的には、バックアップにプライマリのメッセージを「聴取」させている。別のその様なシステムが、米国特許第５，３６３，５０３号（Ｇｌｅｅｓｏｎ−−Ｕｎｉｓｙｓ  Ｃｏｒｐｏｒａｔｉｏｎ）に記載されているが、そこでは、チェックポインティングは、米国特許第４，５９０，５５４号に記載の通りに提供されている。
【００１７】
米国特許第４，２２８，４９６号（Ｋａｔｚｍａｎ−−Ｔａｎｄｅｍ  Ｃｏｍｐｕｔｅｒｓ）に示されている様な他の先行技術は、プライマリが、メッセージを受信し、当該メッセージを処理し、データを生成することを記載している。生成されたデータは、プライマリのデータ空間に記憶され、それによってプライマリのデータ空間を変更させる。プライマリのデータ空間に変更があると、データ空間のチェックポインティング動作がバックアップに対し利用できるようにされる。よって、プライマリのデータ空間をバックアップのデータ空間にコピーすることが頻発し、膨大な量の時間とメモリがプライマリの状態をバックアップに転送するために使用される。それは、プライマリが故障したときにサービスの中断を招くことにもなろう。その様なチェックポインティング方法のオーバーヘッドは、性能上の計り知れない不利益を抱えるものである。
【００１８】
他の先行技術の例では、プライマリの状態で前回の更新以来変更のあった部分だけを更新することが試みられているが、それらは複雑なメモリ及びデータ管理スキームを使用する。米国特許第５，６２１，８８５号（Ｄｅｌ  Ｖｉｇｎａ−−Ｔａｎｄｅｍ  Ｃｏｍｐｕｔｅｒｓ）に示されている他の例では、フォールトトレラント実行時間サポート層（即ち、アプリケーションプログラムとオペレーティングシステムの間のインターフェース）の上で実行しているプライマリとバックアップは、メモリに常駐し、記載されているフォールトトレランスモデルで使用されているプライマリのＣＰＵとバックアップのＣＰＵの両方によってアクセスできる。プライマリとバックアップのプロセスは、それらが同じコードを含んでいるので、同じ計算を遂行する。
【００１９】
米国特許第６，９５４，８７７号は、プライマリコンピュータ側のプロセスの故障があった場合に、中断なくバックアップコンピュータ側のプロセスが引き継ぐことができるように、プライマリのプロセスをバックアップのプロセスへチェックポイント処理するためのシステム及び方法を開示している。加えて、ソフトウェア又は機器の異なったバージョンへの更新は中断なく行われる。サービスインスタンスの状態を変更させる外部からの要求又はメッセージのみをチェックポイント処理できるようにし、それによって、オーバーヘッド及び性能上の不利益を低減できる、軽量チェックポイントティング方法が開示されている。
【００２０】
具体的には、コンピューティングシステムが、フォールトトレラントサービスのチェックポインティングのための機構を提供している。サービスは、プロセスペアを使用することによってフォールトトレラントとなり、即ち、プライマリのプロセスが公式に作業を遂行する一方で１つ又はそれ以上のバックアップのプロセスが故障時に使用することのできる論理的等価物を提供する。プライマリとバックアップは、何れの所与の時点でも論理的に等価となることは可能であるが、内部的に物理面で、即ちそれらの実装に、相違があるかもしれない。
【００２１】
アプリケーションチェックポインティング機構は実装するのが困難なタスクであることから、その実装にはアプリケーションプログラマーからの多くの作業が要求される。ホットスタンドバイ複製動作を処理するための別の方法は、プライマリサーバで実行されているトランザクションの動作のトランザクションログを作成し、当該ログをセカンダリサーバへ転送し、当該セカンダリサーバ側で転送されたトランザクションログを連続的に実行させることである。このログは、トランザクション内のデータの処理及び操作の結果として挿入、削除、又は更新された全てのデータ項目の記録である。データは、どちらかのデータベースでコミットさせるには、その前に両方のデータベースに書き込まれる必要がある。これにより、確実に、プライマリサーバがコミット成功の確認をクライアントアプリケーションへ送る前にデータを安全にセカンダリサーバに記憶させることができる。この種のデータミラーリングシステムの一例が、米国特許第６，３２４，６５４号に記載されており、そこでは「ローカルコンピュータシステム上のプライマリミラーデーモンは、書き込みログデバイス（冗長データストレージ又は冗長メモリデバイス）のデータ更新を監視し、ネットワークを介して、データをそれが記憶されたのと同じ順序でリモートコンピュータシステムの受手側であるリモートミラーデーモンへ送給し、するとミラーデバイスへのデータ更新がコミットされる。故障回復の局面では、これらのプライマリとセカンダリ側のミラーデーモンが、ログをセカンダリノードへ送り、そこでログはそれがプライマリノードにあるかのごとくに実行される。複製された動作がセカンダリノードで連続的に実行されるので、それが処理速度を下げ、ひいては全体性能を低下させる。
【００２２】
データベースフォールトトレランスを実現するための更に別の機構は、２つのデータベースへのアプリケーション接続を持つというものである。アプリケーションがアプリケーション機能を実行するときはいつでも、当該アプリケーションは、両方のサーバに対する関連データの変更をコミットする。確実にトランザクションが両方のデータベースでコミットされるようにするため、アプリケーションは、概して、両データベースでのトランザクション成功を確約するのに所謂２相コミットプロトコルを使用する必要がある。トランザクションがどちらかのデータベースで失敗した場合は、他方のデータベースでも失敗を強いられる。２相コミットプロトコルの使用は、アプリケーション内で行われる必要があり、そのためアプリケーションコードは更に複雑化する。その上、トランザクションの分散化は性能上の問題を引き起こす極めてざらな要因源であり、というのも、両方のデータベースがトランザクションのコミットを確認するより前にトランザクションを完了させることはできないからである。このシナリオでは、エラー状況からの回復も非常に困難となろう。
【００２３】
ホットスタンドバイ複製動作を処理するための更に別のやり方は、トランザクションの行を、それらがプライマリノード側でコミットされた後にセカンダリノードへコピーするというものである。この方法は、単なるコピー手続きであって、トランザクションは連続的にセカンダリノードで実行される。この方法は、非同期データ複製として知られている。この方法は、リアルタイムのデータベースミラーリングにいつも適しているとは限らず、というのも、プライマリデータベースからセカンダリデータベースへのフェイルオーバーが起こったときに、プライマリデータベースの全てのトランザクションがセカンダリデータベースではまだ実行されていないかもしれないからである。
【００２４】
多くのデータベースサーバは、効率的な方式で、同時発生トランザクションを並行して実行する能力がある。例えば、サーバは、マルチプロセッサコンピュータの異なったプロセッサ上で異なったトランザクションを実行することができる。この様に、データベースサーバの処理パワーは、プロセッサをコンピュータに加えることによってスケールアップさせることができる。更に、トランザクションを並行に実行すれば、大きな表にインデックスを作成してゆくといった様な連続的に実行される長期実行型トランザクションのブロッキング効果を回避できる。データベースの完全性を確約するためには、ロッキング又はデータバージョンニングといった様な幾つかの同時性制御方法を使用して、トランザクション間で共有されるデータへのアクセスを管理させる必要がある。２つのトランザクションが同一データ項目へ同時に書き込みアクセスしようとした場合で、バージョンニング式の同時性制御が使用されている場合には、サーバは、どちらでもよいが、「同時性対立」エラーをトランザクションのうちの一方へ返し、アプリケーションは、当該トランザクションの実行を後で再度試みる必要がある。ロッキング式の同時性制御が使用されている場合は、サーバは、ロックされたリソースが解除されるまで、トランザクションのうちの一方を待たせる。しかしながら、このシナリオでは、２つのトランザクションがリソースを互いからロックし合うというデッドロック状態が起こる可能性があり、デッドロック状態をクリアするには、トランザクションのうちの一方をキルしなければならない。アプリケーションは、キルされたトランザクションを実行しようとするなら、例えばトランザクションの実行を再度試みることにより、エラーに対処しなくてはならない。
【００２５】
先行技術で知られているこれらの同時性制御方法は、クライアントアプリケーションの同時発生オンライントランザクションを管理するホットスタンドバイデータベース構成のプライマリサーバで使用するのに適しているが、それらは、システムのセカンダリサーバでは適用できない。これは、セカンダリサーバでは、同時性対立エラー状態に適切に対処できる方策がないことから、同時性対立エラーは許容され得ないためである。適切なホットスタンドバイ同時性制御方法が存在しないせいで、先行技術の複製型ホットスタンドバイでは、動作は、セカンダリノードでは実質的に連続形式で実行されている。動作を並行して実行させることができないので、セカンダリサーバの性能を、データ完全性及びトランザクションの一貫性に問題を生じさせることなく改善するのは難しい。本質的には、トランザクションを並行して実行できるようにする機構であって、但しトランザクションが過早に開始されないこと、且つトランザクションが、依存するトランザクションが開始される前にコミットされることを確約する機構が必要である。
【００２６】
米国特許第６，９７８，３９６号は、プライマリサーバ起源のトランザクション動作であってデータを並行してセカンダリサーバに複製するのに使用されるトランザクション動作を実行する機構を開示しており、セカンダリサーバで同時発生動作又は並行動作を実行して冗長性、回復、及びトランザクション伝播を図ることに関している。本開示によれば、セカンダリサーバで並行動作が実行されることで、性能及び可用性、そしてトランザクション順序と出力についてトランザクション動作の起源であるプライマリサーバとの一致を維持する仕方が改善される。特定の規則のセットが確定されている。特定の規則は、プライマリサーバでのそれぞれのトランザクションに添付される「第１タイムスタンプ」及び「第２タイムスタンプ」を根拠に定義されており、規則は「タイムスタンプ判定基準」を形成している。トランザクションがこのタイムスタンプ判定基準に合致したら、それは、セカンダリサーバ内の同じ判定基準に合致した他のトランザクションと並行に、トランザクションの順序と出力を誤りのないように維持する特定の規則に設定されている命令に従って実行されることになる。
【００２７】
拝察される様に、複雑な処理システムにフォールトトレランスを実装するには、プライマリ構成要素が故障した場合にバックアップ構成要素がいつでも引き継げるように、確実に、冗長構成要素がプライマリ構成要素と同期化されるようにするのに複雑な論理を必要とする。
【特許文献１】米国特許出願第１２／１８８，４７４号
【特許文献２】米国特許出願第１１／５０２，８５１号
【特許文献３】米国特許第４，５９０，５５４号
【特許文献４】米国特許第５，３６３，５０３号
【特許文献５】米国特許第４，２２８，４９６号
【特許文献６】米国特許第５，６２１，８８５号
【特許文献７】米国特許第６，９５４，８７７号
【特許文献８】米国特許第６，３２４，６５４号
【特許文献９】米国特許第６，９７８，３９６号
【発明の概要】
【発明が解決しようとする課題】
【００２８】
以上より、確実に、冗長構成要素がファイルされたプライマリ構成要素をいつでも引き継げるようにすることに関連する複雑さを低減するフォールトトレランスを提供するための簡易な機構が必要とされている。
【図面の簡単な説明】
【００２９】
【図１】１つの実施形態による図５のフォールトトレラントシステムの動作を示す流れ図を描いている。
【００３０】
【図２】１つの実施形態による図５のフォールトトレラントシステムと共に使用するための或るデータベースの動作を示す流れ図を描いている。
【００３１】
【図３】図５のフォールトトレラントシステムの動作を示す更に詳細な流れ図を描いている。
【００３２】
【図４】図５のフォールトトレラントシステムの動作を示す更に詳細な流れ図を描いている。
【００３３】
【図５】実施形態による或るフォールトトレラントシステムのブロック線図を描いている。
【００３４】
【図６】或る代わりの実施形態によるフォールトトレラントシステムのブロック線図を描いている。
【００３５】
【図７】図６のフォールトトレラントシステムの更に詳細なブロック線図を描いている。
【００３６】
【図８】図６のフォールトトレラントシステムの代わりの更に詳細なブロック線図を描いている。
【００３７】
【図９】図６のフォールトトレラントシステムの動作を実演する更に詳細なブロック線図を描いている。
【００３８】
【図１０Ａ】図６のフォールトトレラントシステムと共に使用するための或るデータベースの例示としての動作を描いている。
【図１０Ｂ】図１０Ａと共に、図６のフォールトトレラントシステムと共に使用するための或るデータベースの例示としての動作を描いている。
【００３９】
【図１１Ａ】図６のフォールトトレラントシステムによって利用される例示としてのデータ構造を描いている。
【図１１Ｂ】図１１Ａと共に、図６のフォールトトレラントシステムによって利用される例示としてのデータ構造を描いている。
【図１１Ｃ】図１１Ａ及び図１１Ｂと共に、図６のフォールトトレラントシステムによって利用される例示としてのデータ構造を描いている。
【発明を実施するための形態】
【００４０】
開示されている実施形態は、プロセス、スレッド、アプリケーション、プロセッサなどの様なプライマリインスタンスのためのフォールトトレランス動作であって、プライマリインスタンス内の動作を、但しそれらの動作がプライマリインスタンス内で首尾よく完了した後に限って、ミラーリングするアクティブなコピーキャットインスタンス、別称バックアップインスタンスを使用してフォールトトレラント動作を提供することに関する。開示されているフォールトトレラント論理は、プライマリインスタンスの入力及び出力を監視し、それらの入力を、或る所与の入力が処理されてしまえば、バックアップインスタンスへゲーティングする。次いで、誤りのない動作を裏付けるために、バックアップインスタンスの出力がプライマリインスタンスの出力と比較される。開示されている実施形態は、更に、障害状況時にバックアップインスタンスがプライマリインスタンスを引き継げるようにするフォールトトレラントフェイルオーバー機構に関しており、そこでは、プライマリインスタンスとバックアップインスタンスは緩く連結されており、即ち、それらは互いのことを又はそれらがフォールトトレラント環境で動作しているということに気付いている必要はない。よって、プライマリインスタンスは、フォールトトレラント機構と対話するように特定的に設計される必要もプログラムされる必要もない。代わりに、プライマリインスタンスは、特定の基本的な動作指針を固守するように、そしてそうすることができなくなったときは自身をシャットダウンさせるように設計されてさえいればよい。プライマリインスタンスの能力を外部から制御してその動作指針を首尾よく固守させることによって、開示されている実施形態のフォールトトレラント機構は、エラー条件を見分け、プライマリインスタンスからバックアップインスタンスへ簡単にフェイルオーバーさせることができる。
【００４１】
係属中の特許請求の範囲での使い方を明確にし、これにより公に告知するに当たり、「＜Ａ＞、＜Ｂ＞、…及び＜Ｎ＞のうちの少なくとも１つ」又は「＜Ａ＞、＜Ｂ＞、…＜Ｎ＞のうちのの少なくとも１つ又はそれらの組合せ」という語句は、出願人によって、同出願人によるそれとは反対の明示的な断定がない限り最も広範な意味に定義されるものとして、以上又は以下の如何なる他の黙示されている定義に優先し、Ａ、Ｂ、…及びＮを備える群から選択される１つ又はそれ以上の要素、即ち要素Ａ、Ｂ、…又はＮのうちの１つ又はそれ以上から成る何らかの組合せを意味するものと定義され、そこには何れか１つの要素単独又は何れか１つの要素が他の要素のうちの１つ又はそれ以上との組合せが含まれ、掲載されていない追加の要素との組合せも含まれ得る。
【００４２】
図５は、１つの実施形態によるフォールトトレラントシステム５００のブロック線図を描いている。システム５００は、プライマリインスタンス５０２とバックアップインスタンス５０４を含んでおり、バックアップインスタンス５０４は、プライマリインスタンス５０２の実質的な写しである。プライマリインスタンス５０２は、プロセッサ上で実行されているソフトウェアアプリケーション、プロセス、スレッド、プロセッサ、又は、１つ又はそれ以上の処理用要素やサーバなどから成るか又はそれらの上で実行されている（単数又は複数の）他のハードウェア又はソフトウェア構成要素を含むことができる。バックアップインスタンス５０４は、プライマリインスタンス５０２の別建てインスタンス化物又はプライマリインスタンス５０２の写しを含み、同じか又は異なった１つ又はそれ以上の処理用要素、（単数又は複数のサーバ）、論理区画などから成るか又はそれらの上で実行されているものとすることができる。プライマリインスタンス５０２及びバックアップインスタンス５０４の特質が、それらがソフトウェア、ハードウェア、又はそれらの組合せである故に実装依存性であること、そしてここに記載されているフォールトトレラント機構は、概してそこに適用できるということを理解しておきたい。１つの実施形態では、プライマリインスタンス５０２は、１つ又はそれ以上のプロセッサ又は処理用コアを有するサーバ又はサーバの論理区画上で実行されるマルチスレッド型ソフトウェアプロセスのインスタンス化物である。バックアップインスタンス５０４は、同じ地理的区域に置かれているかそうでないかを問わず、同様の型式の別建て論理区画又は別建てサーバ上で実行される前記と同じマルチスレッド型ソフトウェアプロセスの別建てインスタンス化物である。概して、プライマリインスタンス５０２は、それがプログラムされている目的の業務又は他の機能を遂行するように動作する。例えば、プライマリインスタンス５０２は、取引注文の様な注文を受信し、それらの注文を、取引所の取引用エンティティの間で取引が完結されるように突き合わせる、金融取引所のための突き合わせサーバであってもよい。説明してゆくが、プライマリインスタンス５０２の実質的な写しであるバックアップインスタンス５０４は、基本的に、プログラムされている同じ業務又は他の機能を遂行する。事実上、プライマリインスタンス５０２とバックアップインスタンス５０４は緩く連結されている。緩い連結とは、データをやり取りしている２つ又はそれ以上のコンピュータシステムの間の弾力的な関係を表す。各々のトランザクション終了時にそれらシステムの要求物が明示になり、相手方についての推測は殆ど生じない。
【００４３】
プライマリインスタンス５０２は、プライマリインスタンス５０２によって遂行されている（単数又は複数の）機能に関連するトランザクションデータを記憶する目的で供されているデータベース５０６と連結されている。ここで、「〜と連結されている」という語句は、直接的に接続されていること、又は間接的に１つ又はそれ以上の媒介構成要素を介して接続されていることを意味するものと定義される。その様な媒介構成要素には、ハードウェアベースとソフトウェアベースの両方の構成要素が含まれるであろう。説明してゆくが、プライマリインスタンス５０２は、その（単数又は複数の）機能に従って処理するためにそれが受信した各入力について、データベース５０６を用いてトランザクションを完了して始めて、入力に対応して応答又は確認の様な出力を生成し送信することができるようにプログラムされている。プライマリインスタンス５０２がデータベーストランザクションを完了することができなければ、それは、内部的に停止し自らをシャットダウンさせる。１つの例示としての実施形態では、プライマリインスタンス５０２は、データベース５０６内の表への受信された入力それぞれに関して、規制又は監査関連データの様なデータのログを取らなくてはならない。
【００４４】
トランザクションは、概して、要求を満たすことを目的とする、またデータベースの完全性を確約するための、単位として取り扱われる一連の情報交換及び関連作業（例えば、データベース更新）をいう。トランザクションを完了させデータベースの変更を永久化させるために、トランザクションは丸ごと完了させなければならない。或る典型的なトランザクションには、顧客から電話が入り顧客担当者がコンピュータに入力するカタログ商品注文がある。注文のトランザクションには、在庫管理データベースをチェックする段階と、当該物品が在庫として在ることを確認する段階と、発注する段階と、発注がなされた事実と予定出荷時間を確認する段階を伴う。これを単一のトランザクションとして見るのであれば、トランザクションが成功しデータベースが実際に当該の新規注文を反映するように変更される前に、全ての段階を完了させなければならない。トランザクションが首尾よく完了する前に何かが起これば、データベースへの何れの変更も、それらを元に戻せるように、経過追跡されなくてはならない。
【００４５】
トランザクションの一部であるイベントのシーケンスを管理する又は見張るプログラムは、時に、トランザクションマネジャ又はトランザクションモニターと呼ばれる。１つの実施形態では、トランザクションは、構造化問い合わせ言語（Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ）、標準的なデータベースユーザーインターフェース及びプログラミングインターフェースによってサポートされている。トランザクションが首尾よく完了した場合、データベースの変更はコミットされたと言われ、トランザクションが完了しなかった場合、変更はロールバックされ、即ち、データベーストランザクションが失敗したと判定された場合は途中まで完了していたデータベース変更は元に戻される。ＩＢＭの顧客情報管理システム（Ｃｕｓｔｏｍｅｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｃｏｎｔｒｏｌ  Ｓｙｓｔｅｍ）製品では、トランザクションは、トランザクション要求の特定の型式から生じるアプリケーションデータ処理の一単位である。ＣＩＣＳでは、コンピュータオペレータ又はユーザーによる特定のトランザクション要求のインスタンスはタスクと呼ばれる。コミットは、コンピューティングシステムでのトランザクションへの対処の一環として既に開始されてしまっているデータベース変更が首尾よく完了した場合の最終段階である。
【００４６】
１つの実施形態では、データベース５０６は、「ＡＣＩＤ」準拠データベースである。ＡＣＩＤ（原子性（Ａｔｏｍｉｃｉｔｙ）、一貫性（Ｃｏｎｓｉｓｔｅｎｃｙ）、孤立性（Ｉｓｏｌａｔｉｏｎ）、及び耐久性（Ｄｕｒａｂｉｌｉｔｙ））は頭文字であり、トランザクションマネジャによる何れのトランザクションに対しても確約されるべき当該４大属性が分かるように、そして覚えられるようにするための記憶術的な工夫である。それらの属性は、即ち：
−原子性。２件又はそれ以上の個々の情報が係わるトランザクションでは、全件がコミットされるか１件もコミットされないかのどちらか。
−一貫性。トランザクションは、データの新たな有効状態を作成するか、或いは何らかの故障が起こった場合は全てのデータをトランザクションが開始された前の状態に戻すかのどちらかである。
−孤立性。進行中でまだコミットされていないトランザクションは、それ以外のトランザクションから孤立させておかなければならない。
−耐久性。コミットされたデータは、故障及びシステム再始動の時でさえ、データをその誤りのない状態で利用できるようにシステムによって保存される。
ＡＣＩＤの概念は、ＩＳＯ／ＩＥＣ  １００２６−１：１９９２、Ｓｅｃｔｉｏｎ４に記載されている。これらの属性のそれぞれは、ベンチマークに照らし測ることができる。しかしながら、総じて、トランザクションマネジャ又はモニターは、ＡＣＩＤ概念を実現するように設計されている。分散型システムでは、ＡＣＩＤを実現する１つのやり方は、２相コミット（「２ＰＣ」）を使用することであり、それにより、確実に、全ての関与サイトがトランザクション完了をコミットするか、どれもコミットせずトランザクションがロールバックされるか、になるはずである。
【００４７】
以上に論じた様に、プライマリインスタンス５０２は、更に、それが受信するそれぞれの入力について１つ又はそれ以上の応答／出力及び／又は確認通知を生成するように動作する。以下に説明してゆくが、プライマリインスタンス５０２がデータベース５０６との外部トランザクションを完了させることに依存していること、そしてプライマリインスタンス５０２が受信されたそれぞれの入力についてそれが首尾よく処理されたことを確認する少なくとも１つの応答又は出力を生成するように動作することを、本明細書に記載されている本開示のフォールトトレラント機構は、障害を検出し必要ならバックアップインスタンス５０４にフェイルオーバーするのに利用している。開示されている実施形態は、開示されている機能性を達成するために、何れの動作的に依存する外部トランザクションを利用してもよいし、プライマリインスタンス５０２の所与の入力が処理されたことを確認する何れの表示子を利用してもよいものと理解しておきたい。
【００４８】
システム５００は、フォールトトレラント論理５１４を更に含んでいる。フォールトトレラント論理５１４の構成要素についてはそれらの機能性に関連付けて説明してゆくが、機能性については１つの実施形態による図５のフォールトトレラントシステムの動作を示す流れ図を描く図１−図４に示している。フォールトトレラント論理５１４は、ハードウェア、ソフトウェア、又はそれらの組合せに実装することができ、更に、プライマリインスタンス５０２及びバックアップインスタンス５０４並びにデータベース５０６と対話し且つここに記載されている機能性を実装するコンピュータプログラム論理、プロセス、スレッド、又はそれらの組合せを含むことができる。フォールトトレラント論理５１４は、プライマリインスタンス５０２及び／又はバックアップインスタンス５０４と同じ論理区画、サーバ、又はプロセス上で実行されていてもよいし、プライマリインスタンス５０２及び／又はバックアップインスタンス５０４とネットワーク又は他の相互接続の様な適した手段を介して相互接続されている別建てのサーバ又はプロセッサ上で実行されていてもよい。
【００４９】
具体的には、フォールトトレラント論理５１４は、ネットワーク５０８とバックアップインスタンス５０４への入力との間に連結されている入力受信部５１８と、プライマリインスタンス５０２、入力受信部５１８、及びデータベース５０６の出力と連結されているプライマリ故障検出論理５１６と、ネットワーク５０８（図示せず）及び出力突き合わせ論理５３０と連結されているバックアップ故障検出論理５２８と、を含んでいる。入力受信部５１８は、プライマリインスタンス５０２によってネットワーク５０８から受信されているはずの（単数又は複数の）入力のコピーを受信する。無論、プライマリインスタンス５０２で通信又はネットワークの故障があれば、フォールトトレラント論理５１４による（単数又は複数の）入力の受信は障害を検出することになり、これについては以下に説明してゆく。説明している様に、入力受信部５１８は、（単数又は複数の）入力を緩衝記憶し、それらをバックアップインスタンス５０４へゲーティングする。プライマリ故障検出論理５１６は、プライマリインスタンス５０２の（単数又は複数の）出力を監視し、説明している様に、プライマリインスタンス５０２が故障してしまったかどうかを判定する。プライマリ故障検出論理５１６がプライマリインスタンス５０２は故障してしまったと判定すれば、プライマリ故障検出論理５１６は、更にプライマリインスタンス５０２をシャットダウンさせてバックアップインスタンス５０４へフェイルオーバーするように行動し、プライマリインスタンス５０２が処理し損ねた未処理の（単数又は複数の）入力があるかどうかを判定し、次いで、バックアップインスタンス５０４に通常の動作をプライマリインスタンス５０２から引き継がせる。バックアップ故障検出論理５２８は、所与の（単数又は複数の）入力についてプライマリインスタンス５０２とバックアップインスタンス５０４の両方の（単数又は複数の）出力を監視し、それらが整合しているか否かを判定する。１つの実施形態では、不整合であれば、バックアップインスタンス５０４に障害有り、がトリガされる。或る代わりの実施形態では、不整合であれば、ここに説明されている様にプライマリインスタンス５０２からバックアップインスタンス５０４へのフェイルオーバーがトリガされる。バックアップ故障検出論理５２８は、更に、バックアップインスタンス５０４のネットワーク接続性をチェックし、バックアップインスタンス５０４のネットワーク接続性が故障してしまったと判定されたときには、バックアップインスタンス５０４に障害有りと判定する。
【００５０】
システム５００の動作中、（単数又は複数の）入力は、例えばネットワーク５０８を介して、プライマリインスタンス５０２によって受信されるか、又は少なくともプライマリインスタンス５０２へ送信される。（単数又は複数の）入力は、同様にネットワーク５０８と連結されている他のエンティティから受信されるか又は他のエンティティによって送信されていることもあろうし、（単数又は複数の）入力はプライマリインスタンス５０２自体によって生成されていることもあろう。説明してゆくが、フォールトトレラント論理５１４は、更に、プライマリインスタンス５０２に向けて、プライマリインスタンス５０２が正しく動作しているか否かを判定するために（単数又は複数の）入力を生成することもある。ネットワーク５０８は、１つ又はそれ以上の入力バス、公衆又は私用の有線又は無線ネットワーク、又はそれらの組合せを含み、更に機密保護又は認証プロトコルはもとよりエラー検出及び訂正プロトコルを特徴としていてもよい。１つの実施形態では、ネットワーク５０８は、ＴＣＰ／ＩＰプロトコルスイートを実装している。何れのネットワークプロトコル及び通信技術を、開示されている実施形態と共に使用してもよいものと理解しておきたい。（単数又は複数の）入力のコピーは、同様に、フォールトトレラント論理５１４の入力受信部５１８にも受信されるが、その受信は、想定されているプライマリインスタンス５０２による当該入力の受信と実質的に同時に起こってもよいであろうし、実装に応じてその受容可能な限界内で起こってもよいであろう。１つの実施形態では、入力は、ネットワーク５０８上を、プライマリインスタンス５０２とフォールトトレラント論理５１４の両方へ同報通信（ｍｕｌｔｉｃａｓｔ）される。同報通信は、ネットワーク上の単一の送信側と複数の受信側の間の通信である。多数の入力をプライマリインスタンス５０２とフォールトトレラント論理５１４へ同報通信することができ、そしてネットワーク５０８の実装のせいで、（単数又は複数の）入力はそれらがプライマリインスタンス５０２によって受信されたのと異なった順序及び／又は異なった時間にフォールトトレラント論理５１４によって受信されるかもしれないことを理解しておきたい。１つの実施形態では、ネットワーク５０８は、金融取引所によって使用されている取引用エンジンの突き合わせサーバの注文エントリバスを含んでいる。（単数又は複数の）入力の受信の順序はどうでもよい、というのが開示されている実施形態の特徴である。説明してゆくが、フォールトトレラント論理５１４によって受信された（単数又は複数の）入力は、入力受信部５１８によって緩衝記憶され、フォールトトレラント論理５１４の制御下にバックアップインスタンス５０４へゲーティングされる。以下により詳細に説明してゆくが、このやり方では、フォールトトレラント論理５１４は、プライマリインスタンス５０２との同期化を確約するべくバックアップインスタンス５０４を取り囲んでいるが、バックアップインスタンス５０４は自身にとって外部のフォールトトレラント論理５１４に気付いている必要はない。
【００５１】
図１に示されている様に、通常の動作条件下で、（単数又は複数の）入力（ブロック１０２）がネットワーク５０８を介してプライマリインスタンス５０２によって受信される（ブロック１０６）と、プライマリインスタンス５０２は、当該（単数又は複数の）入力を、自身のプログラムされている機能に従って処理し、例えば、トレーダーの注文入力を、金融取引所における取引が完結されるように突き合わせる。処理の完了時又は処理中、プライマリインスタンス５０２はデータベース５０６相手に、例えば（単数又は複数の）入力の受信及び／又は処理に関連する監査データ又はトランザクションデータの様な入力関連データを記憶させるべく、トランザクションを行おうとするが、それについては、１つの実施形態による図５のフォールトトレラントシステムと共に使用するためのデータベースの動作を示す流れ図を描いている図２（ブロック２０２、２０４）に更に詳細に示している。データベース５０６とのトランザクションが制約違反以外の理由で失敗した場合（図２に図示せず）、プライマリインスタンス５０２はトランザクションをそれが成功するまで又は連続失敗の閾値が発現するまで再試行する。データベーストランザクションが成功すれば（図２のブロック２０６、２０８）、プライマリインスタンス５０２は、そのプログラム機能によって指示される通り、１つ又はそれ以上の応答／出力及び／又は確認通知を生成して、例えば（単数又は複数の）入力の起源元へ、送信する。例えば、プライマリインスタンス５０２が突き合わせサーバであるなら、（単数又は複数の）入力は取引注文を含んでいるであろうし、それに対する（単数又は複数の）応答は注文が受信されたことの確認通知や取引実行の確認を含んでいるであろう。プライマリインスタンス５０２の出力は、その意図された受信先へ送信されることに加えて、フォールトトレラント論理５１４の突き合わせ論理５３２にもコピーされる。突き合わせ論理５３２は、バッファ５２４とコンパレータ５２６を含んでいる。バッファ５２４は、所与の（単数又は複数の）の入力について、プライマリインスタンス５０２の（単数又は複数の）出力を、バックアップインスタンス５０４の対応する（単数又は複数の）出力がバックアップインスタンスによって送信されるまで保持する。次いで、所与の（単数又は複数の）入力についてのプライマリインスタンス５０２及びバックアップインスタンス５０４の（単数又は複数の）出力がコンパレータ５２６によって比較され、その結果がバックアップ故障検出論理５２８へ報告される。コンパレータ５２６は、比較される出力同士が完全整合か実質的整合かを判定していてもよいものと理解しておきたい。更に、コンパレータは、（単数又は複数の）出力の一部分、ハッシュ値、又はチェックサム、或いはそれらの組合せを比較するだけでもよい。
【００５２】
１つの実施形態では、プライマリインスタンス５０２は、時間的な機能性を実装しており、即ち、入力に対する機能を現在時刻の様な時間パラメータに基づいて遂行する。例えば、プライマリインスタンス５０２は、入力が生成された時間を入力がプライマリインスタンス５０２に到達する時間と比較してもよい。所与の入力が注文を表している場合、この機能性は、注文が失効しているかどうかを判定するのに利用することができるであろう。図５に示されている様に、プライマリインスタンス５０２はクロック入力５５０を含んでおり、当該クロック入力は、クロック回路又は時間の表示を提供するように動作する他のデバイスの様なクロック５４８に連結されている。バックアップインスタンス５０４も、クロック入力５５２を特徴としており、当該クロック入力は同様に、入力のコピーに対して特定の時間的機能を遂行するために時間入力を受信する。しかしながら、他の箇所で指摘した様に、バックアップインスタンス５０４は、必ずやプライマリインスタンス５０２より遅い時間に入力を処理する。バックアップインスタンス５０４が同様に現在時刻を入力として使用したとしても、プライマリインスタンス５０２と同じ結果には終わらないであろう。それ故、プライマリインスタンス５０２がその処理を完了し、それに基づく出力結果を生成したら、出力にはその処理に使用された特定の時間を表現しているデータが含まれている。このデータは、次いで、入力受信部５１８によって抽出され、対応する入力と併せてバックアップインスタンスのクロック入力５５２に提供されるので、実際の時間がずっと後であっても、バックアップインスタンス５０２にはプライマリインスタンス５０２によって使用されたのと等価の時間データが提供されることになる。この時間データは、絶対時間又は相対若しくは経過期間として規定されるものと理解しておきたい。これにより、確実に、バックアップインスタンスは時間ベースの機能に関して同じ結果を正確に作製するようになる。
【００５３】
データベース５０６のトランザクションが制約違反のせいで失敗すれば（図２のブロック２０６、２１０）、プライマリインスタンス５０２は、故障状態に入る（ブロック１１４）。以下に更に詳細に説明してゆくが、フォールトトレラント論理５１４は、制約違反がデータベース５０６によってプライマリインスタンス５０２に返されるように強いて、無理やりプライマリインスタンス５０２を故障状態に追い込むことができる。これは、障害状況でバックアップインスタンス５０４が引き継ぐことができるようにプライマリインスタンス５０２を無効にする目的で行われるものであって、事実上、プライマリインスタンス自身の内部の障害対処機構を活用している。プライマリインスタンス５０２によるデータベーストランザクションへの応答に制約違反を生じさせることは、プライマリインスタンス５０２が動作的に依存する外部トランザクションを完了するのを妨害又は阻止するための機構の一例であり、他のその様な機構も利用でき、それらはプライマリインスタンス５０２の実装に依存するものであることを理解しておきたい。更に、プライマリインスタンス５０２は、例えば、プロセスをキルしたり実行中のサーバからパワーを抜くなどして外部から終了させることもできるであろうが、強制的にプライマリインスタンス５０２を自己終了又はフェイルソフトさせれば、退き際をよりクリーンにすることができ、即ち、プライマリインスタンス５０２によって使用されているリソース、例えば割り当てられたメモリ、レジスタ、スタックスペースなどはオペレーティングシステムに復帰させることができ、コミットされていないトランザクション又は解決されていないトランザクションの様な何らかの曖昧状態は解消される。更に、プライマリインスタンスを通信又は対話から単純に切り離すのではなくて、強制的にプライマリインスタンス５０２を故障させることにより、プライマリインスタンス５０２によるリソースの継続消費と他のプロセスへの後効果などを軽減することができる。更に、制約違反をプライマリインスタンス５０２へ返すことを利用することにより、プライマリインスタンス５０２は、既知のポイントに停止されること、及び／又は少なくとも外部的には既知の状態に停止されることが保証され、故障より前にプライマリインスタンスによって処理されていた、順序付けされた入力のセットは、プライマリインスタンス５０２が手の届かない状態或いはそれ以外に一貫性のない状態になったとしても、フォールトトレラント論理５１４によって知られるか又は発見されることが保証される。
【００５４】
或る代わりの実施形態では、入力又はトランザクションは、それらの完了が重要不可欠であるか否かに基づいて差別化させることができる。具体的には、データベース動作の間での差別化、即ち、その完了を待つべきである動作と、「インフライト」即ち進行している間も他の処理を継続させることのできる動作、例えばその間にもメッセージを顧客に返したりできる動作との間の差別化を可能にする機能性が提供されていてもよい。例えば、拒絶された注文を持続させることには、３つの呼び出し、即ち、フォールトトレランス表へ１つ（メッセージシーケンス、メッセージ毎に１つ）、注文履歴表へ１つ、そして注文表へ１つ、が伴う。第１の呼び出しだけは待たれる必要がある。エンジンが、メッセージへの応答を送った後に、但し注文及び注文履歴呼び出しを首尾よく持続させるより前に故障するということになった場合、その影響は１つの拒絶された注文のログが取られなくなるというものである。これは、それほど重要ではないと考えられており、そこで、我々は、どの持続性動作が業務上重要性を有しているかを故障に関する我々のポリシーに照らして判定することにより、多くのデータベーストランザクションを、往復に要する時間から救い出すことができるはずである。これは、注文を観察してみると一目瞭然である。グッドティルキャンセル（ＧＴＣ：Ｇｏｏｄ  Ｔｉｌｌ  Ｃａｎｃｅｌ（取り消しまで有効））注文とグッドティルデート（ＧＴＤ：Ｇｏｏｄ  Ｔｉｌｌ  Ｄａｔｅ（指定日まで有効））注文は、取引所又はエンジンの故障とは無関係に実効性のあることが保証される注文である。結果として、我々は、メッセージへの返答に先んじてそれらが持続されていることを保証しなくてはならない。ＣＭＥポリシーにより、デイ（Ｄａｙ：当日限り有効）注文と当日のＧＴＣ注文（他のＧＴＣ注文やＧＴＤ注文は適用外）は、取引所の故障に関して除外されており、我々はそれらを待つ必要はない。このため、プライマリインスタンス５０２／バックアップインスタンス５０４は、２つの異なった入力型式の間で、出力を生成する前にデータベース動作が完了していなければならないものと、データベース動作が完了している必要はなく、ひいては完了前に出力が生成されてもよいものとを区別するように実装される。図１に示されている様に、トランザクション記憶の試行（ブロック１１０、１２６）と並行して、待機を要しないそれらの入力については、処理は、データベース５０６が記憶の完了を報告する（ブロック１１２、１１４、１２８、１３０）のを待つことなく、確認／応答の送信（ブロック１１６、１３２）を進めることができる。プライマリインスタンス５０２及びバックアップインスタンス５０４は、データベース５０６動作の完了に依存するトランザクションと依存しないトランザクションを識別するように適切にプログラムされているものと理解しておきたい。
【００５５】
フォールトトレラント論理５１６は、プライマリインスタンス５０２を実際にシャットダウンする必要はないが、プライマリインスタンス５０２が外界へそれ以上動作を送って、引き継ごうとしているバックアップインスタンス５０４との対立を生じさせたりしないように保証することだけはどうしても必要であることが理解されるであろう。具体的にいうと、開示されている実施形態では、フォールトトレラント論理５１６は、プライマリインスタンス５０２に接触を取れない、キルさせられない、又はそれ以外に直接影響を与えられないという最悪時シナリオを想定している。プライマリインスタンス５０２がデータベーストランザクションの様な動作的に依存する外部動作を完了させることを封じることにより、バックアップインスタンス５０４が、ネットワークから完全に切り離されてしまったプライマリインスタンス５０２を、当該プライマリインスタンスに接触を取ったりプライマリインスタンスを何らかのやり方で直接つついたりしなくても、引き継げることが保証される。データベースのブロックアウトが完了してしまえば、バックアップインスタンス５０４にとっては、プライマリインスタンス５０２自身が不応答状態のままであるかどうかとか、プライマリインスタンス自身が終了するかどうかとかはどうでもよいことであるが、とはいえ、プライマリインスタンス５０２は、制約違反を介してブロックアウトを見極めればやはりシャットダウンするものであり、それは今や無用なプロセスではあっても、情報のログを取ることと秩序だったシャットダウンにより、プロセスを監視しているものが故障に気付き適切に再起動のステップを取れるようになる。
【００５６】
以上に説明した様に、（単数又は複数の）入力、即ちそれらのコピー、はフォールトトレラント論理５１８の入力受信部５１８によっても受信される（ブロック１０４）。入力受信部５１８は、受信された（単数又は複数の）入力を、例えば受信順に、緩衝記憶し、それらの（単数又は複数の）入力を処理のためにバックアップインスタンス５０４へゲーティングする。具体的には、所与の入力、例えば、ｎ、ｎ−１、ｎ−ｙなどについて、入力受信部５１８は、プライマリインスタンス５０２の（単数又は複数の）出力を監視して、次に続いて受信される（単数又は複数の）入力、例えば、ｎ＋１、＋２、＋ｘに対応する（単数又は複数の）出力がプライマリインスタンス５０２によって何時送信されるかを判定する（ブロック１１８）。これが起こったとき、入力受信部５１８は、所与の先行の（単数又は複数の）入力の１つ又はそれ以上、例えば、（ｎ＋ｘ）−ｙを、処理のためにバックアップインスタンス５０４へ送る（ブロック１２０）。この様にして、バックアップインスタンス５０４は、常に、プライマリインスタンス５０２に遅れて歩調を合わせながら処理している。更に、次に続けて受信される入力についての出力の受信は、１つの実施形態では、バックアップインスタンス５０４による処理を待っている入力がプライマリインスタンス５０２によって現在処理中であること又は既に首尾よく処理されたことの裏付けになる。バックアップインスタンス５０４は、次いで、（単数又は複数の）入力を、プライマリインスタンス５０２と同じ方式（以上に説明済み）で処理する（ブロック１２２、１２４、１２６、１２８、１３９、１３２）。しかしながら、プライマリインスタンス５０２が正常に動作していて、障害が検出されていない状況では、バックアップインスタンス５０４は、データベース５０６との対話が阻止されていて、代わりに、成功したデータベーストランザクションの結果を模倣してバックアップインスタンス５０４へ返すデータベース模倣論理５３０と対話している。或る代わりの実施形態では、バックアップインスタンス５０４は、データベース５０６との対話を試みないようにプログラムされており、その結果、データベース模倣論理５３０の必要性はなくなる。更に、バックアップインスタンス５０４の（単数又は複数の）出力が、突き合わせ論理５３２へ提供されて、それらがプライマリインスタンス５０２の対応する（単数又は複数の）出力と整合しているかどうかが判定される間、バックアップインスタンス５０４は、（単数又は複数の）出力を他のエンティティへ通信してしまいプライマリインスタンス５０２の正常な動作に干渉してしまうことのないようにされている。ゲーティング論理５２０、５２２は、フォールトトレラント論理５１４の制御下に、プライマリインスタンス５０２かバックアップインスタンス５０４がその（単数又は複数の）出力を外部エンティティへ、例えばネットワーク５１２を介して、送信することを許可されるかどうかを、故障が検出されているかどうかなどに基づいて制御する。
【００５７】
プライマリインスタンス５０２とバックアップインスタンス５０４が正常に動作し続けている限り、即ち（単数又は複数の）入力を処理し必要な出力を生成している限り、システム５００は、説明した通りに動作する。
【００５８】
図３は、図５のフォールトトレラントシステム５００の動作、特にプライマリ故障検出論理５１６とバックアップ故障検出論理５２８の動作を、障害状況を検出し対処するための監視に関して示している、更に詳細な流れ図を描いている。図３に示している様に、プライマリ故障検出論理５１６とバックアップ故障検出論理５２８は、複数のプロセス／イベントループ／流れ、及び／又はスレッドを実装しており、それらは、イベントを監視し、それらのイベントに基づいて又はそれらのイベントの欠如に基づいて、所望のフォールトトレラント活動を実装するアクションをトリガする。上記の機能性を実装するのに使用されるプロセスやスレッドなどの数、それらの実行が並行であるか連続か、監視対象のイベントの性質、及び所与のイベント又はイベントの欠如に対応して取られるアクションは、実装依存性であるということ、具体的にいうと、どんなイベント、条件、又はそれらの組合せが障害と定義され、どんなイベント、条件、又はそれらの組合せが正常動作状態と定義されているかに依存していることを理解しておきたい。フォールトトレラント論理５１４、具体的には、プライマリ故障検出論理５１６とバックアップ故障検出論理５２８を、プライマリインスタンス５０２又はバックアップインスタンス５０４のどちらかが障害していると判明させるために満たさなければならない例示としてのイベント及び条件のセット並びにそれに関して取られる例示としてのアクションのセットに関連付けて説明してゆく。それに関する条件及びアクションについては、開示されている実施形態の範囲内で実装することのできるものが他にもあるものと理解しておきたい。
【００５９】
説明してゆくが、障害が何も検出されていない限り、システム５００は、正常動作状態に留っており、プライマリインスタンス５０２は動作し、バックアップインスタンス５０４はプライマリインスタンス５０２に歩調を合わせて遅行している（ブロック３０２）。図４に示されている様に、正常動作状態の下では、バックアップインスタンス５０４の（単数又は複数の）出力は通信されることを差し止められ、一方でプライマリインスタンス５０２の（単数又は複数の）出力は、ゲーティング論理５２０、５２２によって、外部エンティティへ、例えばネットワーク５１２を介して、通信されることが許容されている。更に、バックアップインスタンス５０４のデータベース５０６へのアクセスは封じられており、バックアップインスタンス５０４のデータベーストランザクションの完了成功はデータベース模倣論理５３０によって模倣されるか、又は代わりに、バックアップインスタンス５０４はデータベース５０６と対話しないようにプログラムされている。
【００６０】
プロセスの流れの反復は、クロック、カウンタ、イベント、又は他のトリガによって確定することができるものであって、その所与の反復の都度、プライマリインスタンス５０２が出力を送信したか否かについて判定が下される（ブロック３０４）。１つ又はそれ以上の出力が受信されていれば、以上に説明した様に、出力が他の先行して受信されている入力に続けて受信された１つ又はそれ以上の入力に対応しているかどうかが判定され（ブロック１１８）、そうなら、先行して受信されている他の入力はプライマリインスタンス５０２によって処理されているはずであり、従って、次いで処理のためにバックアップインスタンス５０４へ送られることになる（ブロック１２０）。更に、受信された（単数又は複数の）出力は、バックアップインスタンス５０４からの対応する（単数又は複数の）出力の受信を持つ間も緩衝記憶される（ブロック３２４、３０６）。対応する（単数又は複数の）出力がバックアップインスタンス５０４から受信されると、それらは、プライマリインスタンス５０２の（単数又は複数の）出力と比較される（ブロック１３６）。それらが整合すると、処理は継続する。それらが整合しない場合、１つの実施形態では、バックアップインスタンス５０４に障害有りと判定され、バックアップインスタンス５０４は故障状態に入れられる（ブロック１３８）。代わりのやり方では、プライマリインスタンス５０２とバックアップインスタンス５０４の対応する（単数又は複数の）出力同士の不整合は、プライマリインスタンス５０２の故障を反映しているものと判定され、ここに記載されているフェイルオーバー機構がトリガされる。
【００６１】
プライマリインスタンス５０２からの出力がなければ、次に、出力が最後にプライマリインスタンスから検出されてから、閾値タイムアウトを経過又は超過したかどうかが判定される。１つの実施形態では、ここに記載されているイベント／プロセスの流れの全てによって使用されるものとしてのグローバルなタイムアウト閾値が定義されており、それらの比較動作で同閾値又はその倍数を利用することができる。代わりに、それぞれの特定のプロセス毎に別建ての閾値が定義されていてもよい。本実施形態では、タイムアウト閾値の何倍かの間、例えば閾値の１０倍の間に、何も出力がプライマリインスタンス５０２から受信されていなければ（ブロック３０８）、フォールトトレラント論理５１４はプライマリインスタンス５０２へのハートビート入力を生成するが、この入力は以上に説明した様にバックアップインスタンス５０４へもコピーされ、そしてここに記載の機構をトリガしてプライマリインスタンス５０２からの何らかの形式の出力を強要する。これにより、フォールトトレラント論理５１４は、プライマリインスタンス５０２からの活動の欠如は、故障が原因なのか、或いは、例えば処理されるべき入力がないといった理に適ったものなのかを見極めることができる。ハートビート入力は、フォールトトレラント論理５１４にもその他の受信入力同様に受信され、プライマリインスタンス５０２が実際に故障してしまったかどうかを判定するためのここに記載の他の障害検出プロセスをトリガすることになる。
【００６２】
更に、プライマリインスタンス５０２から何も出力が受信されていないと判定されたとき、プライマリインスタンス５０２が故障してしまったと結論付けるのに、或る条件のセットが、連続（図示）又は並行に又は何か他の論理的配列でチェックされる。代わりの実施形態では、プライマリインスタンス５０２の故障という結論は、他の論理手段によるか又は他の条件及び／又はイベントに基づいて到達されてもよい。例示としての実施形態では、チェックされる条件には、おそらくは或る入力がプライマリインスタンス５０２によって受信されていることが、当該入力がフォールトトレラント論理５１４によって受信されていることから判断でき、出力の生成が待たれていると判定すること（ブロック３１２）が含まれる。繰り返すが、プライマリインスタンス５０２への入力がない場合には、理に適ったこととして、プライマリインスタンスからの出力はないことになる。加えて、出力を待っている入力がある場合は、入力の古さが判定され、定義されている閾値古さと比較される（ブロック３１４）。入力が閾値古さより古い場合、障害無しと判定されることになる。これは、システム５００の始動中に受信される入力の様な、場合により実装とプライマリインスタンス５０２側の負荷によっては起こることが予想され得る取りこぼしを被った入力が、バックアップインスタンス５０４によって処理されることを防止し、フェイルオーバー条件を発動させるのを防ぐ。このチェックは、システム５００の障害に対する寛容レベルについて実装に従って受容可能と思われるレベルに適合するように特別仕様化することができ、例えば、受容可能な閾値古さを調節してもよいであろうし、その様な障害の頻度を測定して受容可能な閾値に照らして比較してもよいであろう。エラー又は障害を断じて寛容できないシステム５００では、このチェックは実装できないかもしれない。
【００６３】
更に、先行の出力はプライマリインスタンス５０２から受信されているかどうかが判定されるが、そのことはプライマリインスタンスが過去に機能していたことの証であり、システム５００を最初に始動させたときに障害条件が確定してしまうのを防ぐ（ブロック３１６）。ここでもやはり、障害を寛容し得ないシステム５００では、このチェックは実装できないかもしれない。これらの条件には合致するが、閾値タイムアウトの半分又は何分の一かしか経過していない場合（ブロック３１８、３２０）は、フォールトトレラント論理５１４及び／又はバックアップインスタンス５０４のネットワーク接続性がチェックされる。１つの実施形態では、ピング信号がフォールトトレラント論理５１４又はその上で実行中のサーバからプライマリインスタンス５０２又はその上で実行中のサーバの様な受信側へ送られており、例えば、ピングユーティリティ／プロセスを使用して、ネットワーク接続性の状態を判定するように設計された試験通信が送信されてもよい。処理が継続している間、別建てのプロセッサが、ネットワーク接続性がうまくいっている証しとなるピングへの応答を待つ（ブロック３１６）。何も応答が受信されなければ、ネットワーク接続性の喪失が推定されるため、バックアップインスタンス５０４は故障状態に入れられる。閾値タイムアウトを超過していて他の条件の全てに合致した場合は、プライマリインスタンス５０２の故障が確定する（ブロック３０２）。
【００６４】
図４に示されている様に、プライマリインスタンス５０２の故障が確定する（ブロック４０２）と、プライマリインスタンス５０２は、バックアップインスタンス５０４にフェイルオーバーされる。具体的には、プライマリインスタンス５０２の出力は、ゲーティング論理５２０によって通信されることを差し止められるか又は別のやり方で阻害され、一方でバックアップインスタンス５０４の出力はゲーティング論理５２２によって通信されることが許可される。加えて、バックアップインスタンス５０４は、データベース５０６とのトランザクション遂行を許可される。次いで、プライマリ故障検出論理５１６はブロッキングデータをデータベース５０６の中へ記憶する。ブロッキングデータは、プライマリインスタンス５０２が同様に記憶させることを試みるはずのストレージを占めるように構成されている。プライマリインスタンス５０２がマルチスレッド化されている１つの実施形態では、プライマリ故障検出論理５１６は、Ｎ個の非同期書き込みスレッドのブロックアウトに対処することができ、書き込みスレッドは順繰りに書き込んでいなくてもよいし、継続的に書き込んでいてもよい（故障時に跳び越えた先のブロックに書き込もうとするなど）。プライマリインスタンス５０２がなおアクティブであり入力を処理しようとしているなら、ブロッキングデータがデータベース５０６に制約違反をプライマリインスタンス５０２に返すように仕向けることになる。説明した様に、制約違反は、強制的にプライマリインスタンス５０２に自己停止させるはずである。プライマリインスタンス５０２が封じられてしまえば、フォールトトレラント論理５１４は、入力受信部５１８によって受信された入力で未処理のままになっている入力を分析し、且つデータベース５０６を分析して故障より前のプライマリインスタンス５０２の最終アクションを判定することによって、どの入力が処理される必要があるかを確定する（ブロック４１０）。次いで、これらの入力はバックアップインスタンス５０４へ送られて処理される（ブロック４１２）。するとバックアップインスタンスによる通常の処理が開始される（ブロック４１４）。
【００６５】
１つの実施形態では、バックアップインスタンス５０４が故障した場合、バックインスタンス５０４は故障したプライマリインスタンス５０２を引き継げないようにされる。更に、故障したバックアップインスタンス５０４を引き継ぐべく、別のバックアップインスタンス５０４が始動される。プライマリインスタンス５０２又はバックアップインスタンス５０４の何れかの故障の場合、警報が、他の監視用プログラム又はプロセスに送信されるか、或いはそれらに介入の必要性を警報する監視スタッフに送信される。
【００６６】
プライマリインスタンス５０２が正常に動作している間はプライマリインスタンス５０２に遅れてついて行っていれば、バックアップインスタンス５０４は、プライマリインスタンス５０２と同期を保つことについて気を患わせることなく、故障したプライマリインスタンス５０２によって終えられていない何らかの処理を解決することができる。動作時、開示されているフォールトトレラント論理５１４は、プライマリインスタンス５０２が動作を完全に停止したときに、又は処理を継続しているが正しい（単数又は複数の）出力を送り損ねたときに、又は所与の（単数又は複数の）入力についてのプライマリインスタンス５０２とバックアップインスタンス５０４の対応する（単数又は複数の）出力が整合し損ねたときに、故障を検出する。
【００６７】
１つの実施形態では、図６に示されている様に、プライマリインスタンス５０２とバックアップインスタンス５０４は、シカゴ・マーカンタイル取引所によって利用されているファルコン商取引エンジン（Ｆａｌｃｏｎ  Ｔｒａｄｉｎｇ  Ｅｎｇｉｎｅ）６００の様な、金融取引所の商取引エンジン６００のための突き合わせエンジンのインスタンスである。突き合わせエンジン６０２とデータベース６０４は、冗長ペアになって実行されている。本システムは、何れの単一の突き合わせエンジン６０２Ａ、６０２Ｂ、又はデータベースサーバについても、取引活動を中断させることなく、それを停止させることができる。ファルコン突き合わせエンジンのフォールトトレランスは、ここに説明されているカスタムアーキテクチャによってアプリケーションレベルで対処される。
【００６８】
突き合わせエンジン６０２は、上に説明されている様に、ペアになったプライマリ／バックアップ構成で実行するように設計されている。個々のファルコン突き合わせエンジン６０２Ａ、６０２Ｂそれぞれは、緩く連結されたスレッドのセットを備える１つのプロセスである。完成された突き合わせエンジンプロセスの機能性は、これらのスレッド間で下位分割されている。このおかげで、物理的に別建てのプロセッサに対する作業の並列化が簡単になり、より費用の安いハードウェアを使用できるようになる。
【００６９】
図７と図８は、図６のフォールトトレラントシステムの更に詳細なブロック線図を描いている。突き合わせ構成要素６０２は、ファルコンエンジンの最高権威である。それは、注文の受け入れと突き合わせを行い、更に、ファルコンエンジン内のインライン限定のトランザクションの持続性を制御する。突き合わせ構成要素６０２は、気配値要求（ｒｅｑｕｅｓｔ  ｆｏｒ  ｑｕｏｔｅｓ）と、入って来る注文と、注文の取り消しを、ファルコン・ゲートウェイから受け入れることになる。それは、応答と取引実行を、市場データ構成要素とファルコンゲートウェイの両方へ発送することになる。構成と管理の呼び出し全ては、突き合わせ構成要素６０２を通し、ゲートウェイ経由で、例えば、Ｊａｖａ（登録商標）メッセージングサービス（「ＪＭＳ」）を使用して送られる。突き合わせ構成要素６０２は、管理と構成の情報全てを、他の構成要素へ、ファルコン内部メッセージマネジャを介して通信する。
【００７０】
それぞれのファルコンインスタンス６０２Ａ、６０２Ｂは、いつでも着信してくる注文を受け入れられるようになる前に、特定のエンジン状態を経ることになる。突き合わせ構成要素６０２は、エンジン状態に対する最高権威であり、それぞれのファルコン突き合わせエンジンサーバのその他全ての構成要素を制御する。市場スケジュールは、管理（Ａｄｍｉｎ）データベースに記憶され、突き合わせサーバへ通信される（始動時、及び実行時間中には取引カレンダー更新を介す）。次に状態の変更が構成要素内でスケジュールされ、突き合わせ構成要素により起動される。状態の変更が起きた後、この情報は残りの構成要素へ管理オペレーション（ＡｄｍｉｎＯｐｅｒａｔｉｏｎ）メッセージを介して送られる。管理サーバは、更に、突き合わせサーバの現在の状態を、管理オペレーションを送ることによって変更することもできる。管理上の管理オペレーション呼び出しは全て、ゲートウェイ構成要素によって受信され、突き合わせ構成要素へ送られる。突き合わせ構成要素が管理オペレーションを確認したら、全ての他の構成要素は同じ方式で応答する。
【００７１】
突き合わせ構成要素６０２の主要な実行経路は、単一のスレッドである。このスレッドは、メッセージを、内部メッセージバスから引き取り、それらを処理し、応答を発送する。結果として、マッチスレッドではどの所与の時点でも１つのオペレーションしか進行していない。データベースの持続性に関しては、多くのスレッドを非同期的に使用することができ、注文は後で記憶し直される。「ブロック」のサイズは、データベーススレッドの＃＊データベースバッチサイズに等しいものとして、上述されているプライマリ故障検出論理５１６は、Ｎ個の非同期書き込みスレッドのブロックアウトに対処することができ、書き込みスレッドは順繰りに書き込んでいなくてもよいし、継続的に書き込んでいてもよい（故障時に跳び越えた先のブロックに書き込もうとするなど）。
【００７２】
突き合わせスレッドの所与の注文控元帳について、単一の割り付けアルゴリズムと、構成可能なオーバーレイ量がある。着信してくる注文は、順々に、先ずそれぞれのオーバーレイへ回され、次に割り付けアルゴリズムへ回される。それぞれのオーバーレイと割り付けアルゴリズムは、次に、適切な充填を生成する。当該注文が上記のそれぞれを通過してしまえば、残り（仮にあった場合）が控元帳に載せられ、充填メッセージが送られる。ファルコン１．５には、着信してくる注文の注文割り付けを制御するオーバーレイが２つある―Ｌｅａｄ  Ｍａｒｋｅｔ  Ｍａｋｅｒ（値付け先導役）（「ＬＭＭ」）とＴＯＰ（トップ）（Ｍｉｎ（最小）／Ｍａｘ（最大））である。ＬＭＭでは、一部の特定のユーザーからの注文は、１つ１つの着信してくる注文について、例えばｘ％の優遇割り付けが受けられる。優遇割り付けの見返りとして、それらのユーザーは、多くの市場について気配値を提示し流動性をもたらすことに同意する。ＴＯＰでは、市場の動向を変える〔より良い値での最初の注文〕が、同価格でそれに参加している他の注文に勝って優遇割り付けを受けられる。ＭｉｎとＭａｘは、或る注文についてそれがどれほどのＭＩＮサイズでなくてはならないかということとそれがトップ状態を失う前にどれほどのＭＡＸ割り付けを受けることができるかを確定する修飾子である。控元帳は、オーバーレイを全て或いは一部備えた構成とすることもできるし、オーバーレイを全く備えない構成とすることもできる。
【００７３】
突き合わせスレッドは、時限イベント（例えば、グループを開く／グループを閉じる）を発動しない。代わりに、これらのイベントは、専用スレッドによって発動される。当該イベントが発動されると、それは、メッセージに変換され、その他のメッセージと同じ様に突き合わせスレッドの待ち行列に載せられる。結果として、それらはその他のメッセージと同じ様に１度に１つずつ処理される。
【００７４】
ファルコン内でデータを持続させる理由は、回復と規制と監視（オペレーションスタッフによる）の３つしかない。このデータのうちの一部は、トランザクション式にインラインのディスクへ書き込まれる必要がある。これは、トランザクションを完了させている間、突き合わせサーバは応答の送発を遅らせなくてはならないことを意味する。
【００７５】
更に、業務特定データ及びシステム特定データの１つ又はそれ以上のログが維持されている。これらのログは、トランザクション式ではなく、ローカルディスクに常駐している。業務特定ログはファルコンが生成する全ての業務情報を収容し、システムログはシステム管理人のために相応化されたファルコン技術情報を収容している。
【００７６】
説明した様に、ファルコンアーキテクチャは、プライマリサーバ６０２Ａ（インスタンス）と、活動的に実行するバックアップサーバ６０２Ｂ（インスタンス）で構成されることになる。バックアップ６０２Ｂは、プライマリの状態を正確に複製し、且つサービスのあからさまな中断なしに合理的に短い時間内にフェイルオーバーする能力を有することになろう。
【００７７】
バックアップがフェイルオーバーするのに掛かる最大遅延は、７−１０秒となろう。時間はもっと短縮できるかもしれないが、偽陽性故障検出を防ぐ最適な設定の知見に基づき決定するとこうなる。フェイルオーバー時間は、構成可能なパラメータということになろう。
【００７８】
本システムは、重複メッセージについてそれらを重複可能とマーキングせずに送ることは決してない。本システムは、重複可能とマーキングされて送り出されるメッセージの数を限定しなくてはならない。本システムは、フェイルオーバーによって引き起こされたときに重複可能を送信するだけであって、正常動作中は、何も生成されることはない。
【００７９】
ファルコンフォールトトレランスは、以上に説明した様に、アクティブ／コピーキャットと呼ばれる概念に基づいている。このシステムでは、バックアップ６０２Ｂとプライマリ６０２Ａは、注文エントリバス６０６からの入力メッセージを聴取する。１つの実施形態では、注文エントリバス６０６は論理構成要素であり、複数の注文エントリバス６０６があってもよい。更に、バックアップ６０２Ｂは、プライマリ６０２Ａからの応答メッセージを聴取する。所与の入力への応答と、次に受信された入力への応答と、が受信されると、バックアップ６０２Ｂは、次いで、同じ入力を処理することによりプライマリ６０２Ａをコピーし、当該プライマリ応答を自身の出力と比較する。バックアップサーバ６０２Ｂは、出力メッセージ発行とデータベース６０４への書き込み以外は、プライマリサーバと同じアクションを行う。アクティブ／コピーキャットを働かせるために、メッセージングインフラストラクチュアに関し以下の要件が存在しており、即ち：
・ファルコンによって送信される全てのメッセージは送信元及び単調増加式のシーケンス番号（送信元であるファルコンサーバ別）とによって固有に識別されることになる。これが、イベントシーケンス番号であり、ファルコンインスタンスに固有である。
・全ての入力メッセージは、固有に識別されなければならない。
・ファルコンのプライマリ６０２Ａによって発行される全ての出力メッセージは、どのメッセージに対してそれが応答したのかを示す表示を有することになる。こうして、バックアップ６０２Ｂは、応答を生じさせることになった入力メッセージを識別することができる。
・ファルコンのプライマリ６０２Ａによって発行される全ての出力メッセージは、現在の出力をもたらした入力メッセージの前にどの入力メッセージが処理されたかを示す表示を有することになる（例えば、入力メッセージ２への全ての応答は、前のフィールドにメッセージ１を有することになる）。
【００８０】
プライマリモードでは、フォールトトレランス特定クラスは使用されない。プライマリ６０２Ａは、バックアップ６０２Ｂが存在しているか否かに気付いていず、即ち、バックアップ６０２Ｂを実行させる必要があるということは一切要件とはなっておらず、バックアップは、どんな場合にも送信されることになるトラフィックを受動的に聴取するものである。結果として、説明されているフォールトトレランスの実装は、プライマリの実行されているインスタンスへは性能上何ら影響を及ぼさない。
【００８１】
バックアップ６０２Ｂでは、実際のコピーキャット論理チェックは、フォールトトレラント（「ＦＴ」）メッセージマネジャにより行われる。これらのオブジェクトは、システムの業務論理構成要素（ゲートウェイ、市場データ、及び突き合わせサーバ）に、各々のプライマリ状態／バックアップ状態に殆ど無頓着でいられる。ゲートウェイ及び市場データは、始動時に限って各々の状態に気付いていればよく、そうすれば、それらは正しいＦＴメッセージマネジャをインスタンス化することができる。突き合わせサーバは、データベースへの書き込みを有効／無効にするために状態に気付いている必要がある。状態とは無関係に、それぞれの構成要素は、通常通りメッセージを送受信し、即ち、バックアップモードでは、構成要素のＦＴメッセージマネジャが入って来るメッセージを順序付けることと出力メッセージを差し止めることは責務である。
【００８２】
ＦＴメッセージマネジャは、注文エントリ用に１つと市場データ用に１つのＦＴポリシーオブジェクトによって制御されている。
【００８３】
本実施形態では、以下のパラメータが構成でき、即ち：
−フォールトトレランス故障タイムアウト（ＦａｕｌｔＴｏｌｅｒａｎｃｅＦａｉｌｕｒｅＴｉｍｅｏｕｔ）―フェイルオーバー条件が存在しているというイベントの時にフェイルオーバーするまでにバックアップはどれほど長く待たなくてはならないかということ。
−フォールトトレランス入力メッセージ失効（ＦａｕｌｔＴｏｌｅｒａｎｃｅＩｎｐｕｔＭｅｓｓａｇｅＥｘｐｉｒａｔｉｏｎ）―メッセージについてそれがどれほど古ければフェイルオーバーをもたらさないかということ。万一フェイルオーバーしても、これらのメッセージは、エンジンへ転送されない。
−フォールトトレランスＭＭ受信トピック（ＦａｕｌｔＴｏｌｅｒａｎｃｅＭＭＲｅｃｅｉｖｅＴｏｐｉｃ）―ＦＴポンオン（ｐｏｎｇ  ｏｎ）を受信するトピック。
−フォールトトレランスＭＭ送信トピック（ＦａｕｌｔＴｏｌｅｒａｎｃｅＭＭＳｅｎｄＴｏｐｉｃ）―ＦＴピングオン（ｐｉｎｇ  ｏｎ）を送信するトピック。空値／空白であれば、ピングは成功であると推測される。
−フォールトトレランスハートビートインターバル（ＦａｕｌｔＴｏｌｅｒａｎｃｅＨｅａｒｔｂｅａｔＩｎｔｅｒｖａｌ）―活動なし期間の持続中、バックアップが入力を生成してそれをプライマリへ送り、プライマリがまだ活動しているかどうかを判定する前に、どれほど待たなくてはならないかということ。
【００８４】
注文エントリフォールトトレラントポリシーオブジェクトには、入力メッセージを、確実にそれらメッセージがプライマリ６０２Ａと同じ順序で処理されるように並べ替える責任がある。それは、また、プライマリの出力がバックアップの出力と整合していることの妥当性確認を行い、必要があればフェイルオーバーを起動させる。バックアップファルコン６０２Ｂの全ての入力ソースは、各々のメッセージを注文エントリＦＴポリシーへ送る。これは、管理サーバ、他の注文エントリゲートウェイ、及び内部ファルコンタイマーイベントを含んでいる。結果として、全ての入力イベントは、プライマリによって処理されるのと同じ順序に並べ替えられることになる。
【００８５】
正常なオペレーション中のメッセージの流れは、次の通りであり、即ち：
１．メッセージが送信元から受信され、入力の待ち行列に入れられる。
２．１つ又はそれ以上の出力メッセージが、入力メッセージに応答したプライマリファルコンインスタンス６０２Ａから受信される。
３．次の入力メッセージについての１つの出力メッセージが、プライマリファルコンインスタンス６０２Ａから受信される。
４．当該メッセージは、プライマリ６０２Ａが前の入力メッセージを首尾よく処理したことの証であるので、先の入力はバックアップサーバ６０２Ｂへ処理のために転送される。
【００８６】
フェイルオーバーは、以下の場合の全てが真であるときに起動され、即ち：
−故障タイムアウトの間プライマリ６０２Ａの応答が何も受信されていない。これは、プライマリ６０２Ａがバックアップ６０２Ｂに話しかけていないことを示している。
−プライマリ６０２Ａによって応答されていない少なくとも１つの入力がある。これは、プライマリ６０２Ａに応答を要求しているメッセージがあることを示している。
−当該入力は、構成できる秒数より古くない。これは、繁忙な市場で稼働中のプライマリ６０２Ａによって出力が１つ取りこぼされたからといって、プライマリ６０２Ａがメッセージを処理している限りは、確実に、その様な取りこぼされた出力が当日の更に後刻にフェイルオーバーを招くことのないようにする。
−当該入力は、バックアップ６０２Ｂが最初にプライマリから聴取した後の少なくとも１つの故障タイムアウトを経て受信された。これは、確実に、プライマリが始動している最中にバックアップ６０２Ｂによって受信されたメッセージがフェイルオーバーを招くことのないようにする。
−故障タイムアウトが半分失効していて、以上の条件の全てが真である場合、バックアップは、自身のネットワーク接続性を裏付けるべく、例えば管理サーバ及び／又は他の注文エントリゲートウェイなどへ、ピングを起こすことになる。故障タイムアウトが全部失効してしまうと、仮に当該ピングが成功であった場合、バックアップ６０２Ｂはフェイルオーバーを起動させることになる。ピングが成功しなかった場合は、バックアップは、先を行くプライマリ６０２Ａを引き継ぐことができないという状態を入力することになる。
【００８７】
バックアップ６０２Ｂは、それが作製する出力をプライマリ６０２Ａによって受信された応答と比較する。比較が不合格であれば、バックアップ６０２Ｂは、先を行くプライマリ６０２Ａを引き継ぐことができないという状態を入力することになる。タイムスタンプフィールドとチェックサムフィールドを除く全てのＦＩＸメッセージフィールドは、プライマリ６０２Ａとバックアップ６０２Ｂの両方によってハッシュされそれらのハッシュが比較される。メッセージに何らかの差異があれば、バックアップ６０２Ｂは、それに着目し、先を行くプライマリ６０２Ａを引き継ごうと試みることはしない。全ての重要なイベントは、適切なログレベルでログを取られる。
【００８８】
市場の活動が低調な期間中に故障を検出するためには、バックアップ６０２Ｂは、それが１０＊故障タイムアウトの様な構成できる期間の間にプライマリ６０２Ａからの聴取がなければ、入力メッセージを生成することになる。入力メッセージは、プライマリ６０２Ａとバックアップ６０２Ｂの両方へユーザーからの何れかの入力と同じ方式で送られる。入力メッセージにはエンジンへの影響はないが、それはプライマリ６０２Ａからの出力メッセージを生成し、同メッセージはバックアップ６０２Ｂによって読み出され処理される。正味効果は、バックアップ６０２Ｂが、プライマリに絡むどんな故障をも、ユーザー入力がフェイルオーバーをトリガするのを待つまでもなく合理的な時間枠内で発見できるようになる、というものである。
【００８９】
開示されている突き合わせエンジンは、注文控元帳の移設、即ち実行中のプライマリサーバ６０２Ａから新しく始動されたバックアップ６０２Ｂへコピーするプロセスを、プライマリを停止させることなく行えるようにする。控元帳の移設は、バックアップサーバ６０２Ｂが始動するときはいつでも、移設させるべき実効性のある控元帳の有無にかかわらず、使用される。起きているプライマリサーバ６０２Ａがなければ、バックアップ６０２Ｂは、起きているプライマリサーバが存在するのを待って完全に始動することになる。
【００９０】
開示されている実施形態は、同時に実行するバックアップインスタンス５４０が幾つであってもそれらをサポートし、万一、故障が起こったなら、それらのうちの何れか１つが使用されることになるものと理解しておきたい。更に、追加のバックアップインスタンス５４０は、監査、例えばトレーダーの挙動のリアルタイム監査や環境試験を提供するとか、監視を有効にするという様な他の目的に、プライマリインスタンス５０２に影響を与えることなく、利用することもできる。これらのインスタンス５４０は、プライマリインスタンス５０２をバックアップするという目的では頼りにされていないインスタンスであって、つまりは非引き継ぎバックアップであるインスタンス５４０については、常に１メッセージ遅れという要件は緩和されてもよい。主バックアップインスタンス５４０は、部分的な出力をもたらしかねない失敗したメッセージを再処理することができなければならないので、１メッセージ遅れに留まらなくてはならないが、代わりの目的に使用される他のバックアップインスタンス５４０は、必ずしも当該の失敗したメッセージを処理し直す必要はなく、それらはメッセージをプライマリが受信したのと同じ順序で処理しさえすればよく、即ち、それらはプライマリが失敗したメッセージの処理を完了したことを知る必要はなく、プライマリがそれを処理し始めたことを知ってさえいればよいわけである。
【００９１】
バックアップ６０２Ｂが始動すると、それは、自身の構成をファルコン管理サーバから得る。バックアップは、次いで、プライマリサーバ６０２Ａへ、それが活動しているかどうかをチェックするメッセージを送り、応答を待つ。起こり得る状況として２つの状況があり、即ち、プライマリ６０２Ａは、起きていれば、直ちに応答するであろう。そうでなければ、プライマリ６０２Ａは、始動挙動の一環として、始動に関するメッセージを送信する。このメッセージは応答として扱われ、バックアップ６０２Ｂにはプライマリ６０２Ａが起きていることが知られる。
【００９２】
プライマリ６０２Ａ確認のメッセージが受信されると、バックアップ６０２Ｂは、それが自身の構成ファイルをＦＡＳから受信して以来どれほどの時間が経過しているかを見るためにチェックする。３秒より長く経過していたなら、バックアップは、構成をＦＡＳから取得し直す。これは、ＦＡＳがエンジン構成への変更を、バックアップ６０２Ｂが自身の構成ファイルをダウンロードした後に但しプライマリ６０２Ａが自身の構成ファイルをダウンロードする前に行うリスクを最小限にするのに役立つ。仮にこれが起こったなら、バックアップ６０２Ｂは始動時にこれを検出し、直ちに故障することになる。よって、構成ファイルを取得し直すことで、意図的な「迅速故障」の場合が最少化される。
【００９３】
このプロセスに続いて、バックアップは、状態要求メッセージをプライマリ６０２Ａへ送る。プライマリ６０２Ａは、全ての変更可能な状態−データベースシーケンス番号、未処理の注文、ホスト注文番号（「ＨＯＮ」）、ホスト取引番号（「ＨＴＮ」）など、を有する状態総和応答で応答する。バックアップ６０２Ｂが、この情報を受信し、適用すると、いつでもバックアップとして機能を果たせる状態になる。このプロセス中に管理サーバの変更が適用されるリスクを完全に排除するために、バックアップ６０２Ｂは、プライマリがＦＡＳから受信した最新のシーケンス番号を、それが構成オブジェクト内でＦＡＳから受信したものと比較する。シーケンス番号が相違するというリスクは極僅かではあるが、実際に相違があれば、それは、構成の受信と総和状態の受信の間の数秒の間に管理サーバからのユーザーが起こした構成変更のあったことを示す。この条件が検出されれば、バックアップ６０２Ｂは、シャットダウンするので、再始動させて、控元帳移設を再試行しなければならず、即ち、それは、持続性エラー状態（上では「迅速故障」と呼称）を示すものではない。
【００９４】
バックアップ６０２Ｂは、一旦起き上がると、全てのソース（他の注文エントリゲートウェイ管理サーバ、内部タイマーイベント）からの入力を待ち行列に入れるが、最初のプライマリ応答メッセージの受信後、１つの故障タイムアウトが経過するまでは、プライマリ６０２Ａの故障を検出しようと試みることはしない。当該時間前にメッセージが受信されなければ、フェイルオーバーが引き起こされる。
【００９５】
プライマリ６０２Ａの始動はかなり単純である。プライマリ６０２Ａは、自身の構成をファルコン管理サーバからダウンロードし、メッセージを共有のエンジンバスに載せて送り、そこにそれ以外のプライマリエンジンがあるかどうかを判定する。プライマリ６０２Ａは、応答を受信したなら、シャットダウンする。応答を受信しなければ、プライマリ６０２Ａは、通常通り始動し、始動したことを示すメッセージを送る。
【００９６】
市場データフォールトトレラントポリシーには、バックアップ６０２Ｂからの市場データメッセージの出力を差し止める以外の役割はない。それは、妥当性確認もチェックも行わなければ、プライマリ６０２Ａからの市場データ給送に加入もしない。全ての重要なイベントは、適切なログレベルでログを取られる。
【００９７】
フェイルオーバー条件の妥当性確認プロセスは、以下の機能を遂行し、即ち：
１）フェイルオーバータイムアウトの１／２が過ぎるのを待つ。この時間中にプライマリ６０２Ａからの適切な応答メッセージが着信すれば、フェイルオーバーは必要ない。
２）「ピング」メッセージを、注文エントリ６０６バスを介して他の注文エントリゲートウェイへ送り、返答を聴取する。
３）フェイルオーバータイムアウトの１／２が過ぎるのを待つ。この時間中にプライマリ６０２Ａからの適切な応答メッセージが着信すれば、フェイルオーバーは必要ない。
４）ピング応答が、注文エントリバス６０６を介して受信されると、次いで、バックアップ６０２Ａはフェイルオーバーすることになる。受信されなければ、バックアップ６０２Ａは、フェイルオーバーせず、代わりに、警報を監視に発送する。
【００９８】
プライマリモードへの切替プロセスは、以下の機能を遂行し、即ち：
１）バックアップは、プライマリ６０２Ａをデータベースから締め出す。これはＭＳＧ ＳＥＱ ＴＡＢＬＥに「ブロッキング」値を入力することによって実現される。プライマリ６０２Ａは、これらの数値を書き込もうと試みたときに、結果として生じた制約違反を、バックアップ６０２Ｂの引き継ぎであると翻訳する（図１０参照）。
２）バックアップ６０２Ｂは、「プライマリ停止」のメッセージをファルコン管理サーバへ送る。
３）ファルコン管理サーバは、カリフォルニア州パオアルト所在のＴｉｂｃｏ，Ｉｎｃ．が普及させたメッセージングプロトコルであるティブコ（Ｔｉｂｃｏ）の様なメッセージングプロトコルを使って、「プライマリ停止」のメッセージを、故障するプライマリ６０２Ａへ送る。
４）プライマリ６０２Ａは沈黙する。
５）バックアップ６０２Ｂは、プライマリ６０２Ａの状態を査定し、何であれプライマリ６０２Ａが止めた順序付けの写しを取る。これは、直近に転送された入力メッセージをキーとして使用してデータベースに問い合わすことによって行われ、即ち、データベースは、プライマリ６０２Ａによって書き込まれた何らかの後続メッセージの順序を返すことになる。時間ベースの入力処理を実装している実施形態では、バックアップ６０２Ｂには、更に、プライマリ６０２Ａの状態を完全に複製するために、処理された入力の処理時間／タイムスタンプが必要となるであろう。
６）バックアップ６０２Ｂは、プライマリ６０２Ａとして引き継ぐ。
７）バックアップ６０２Ｂは、入力メッセージを突き合わせサーバの中へ、プライマリ６０２Ａがそれらを処理したのと同じ順序で転送する。入力がまだ受信されていなければ、入力を待つ。これらのメッセージから生じた出力は、重複可能（「ｐｏｓｄｕｐ」）として送られる。プライマリ６０２Ａによって書き込まれなかったメッセージがメッセージタイムアウトパラメータより古かったなら、それは、突き合わせサーバの中へ転送されることはない。代わりに、それは廃棄され、当該効果に対するメッセージがログを取られることになる。
８）バックアップ６０２Ｂは、これより、プライマリ６０２Ａとして行動し、全ての入力メッセージをプライマリ６０２Ａの中へ送り、出力を、市場データバスと注文エントリバス６０６の両方へ送る。
【００９９】
故障については以下の場合が検出される：
１．プライマリ６０２Ａは、故障してしまい、メッセージを送信していない。この場合には、或る特定の入力メッセージについて部分出力が受信されるか又は何の出力も受信されず、後続の入力メッセージについては出力は何も受信されない。この場合には、バックアップ６０２Ｂが、自身がまだ接続されていること、そしてプライマリ６０２Ａに故障があることを確認したなら、バックアップ６０２Ｂはフェイルオーバープロセスを起動させることになる。
結果：フェイルオーバー
２．バス又はネットワーク問題が起こり、プライマリ６０２Ａは入力を受信すること又は出力を送信することができなくなる。この場合には、プライマリ６０２Ａは、通信を無効にされ、フェイルオーバーが上記の様に進められる。
結果：フェイルオーバー
３．プライマリ６０２Ａが、自身のネットワークインターフェース、データベース６０４、又はハードウェアに絡む問題を発見した。この場合には、プライマリ６０２Ａは沈黙し、フェイルオーバーが上記の様に進められる。
結果：フェイルオーバー
４．オペレーションスタッフは、ファルコン管理サーバからフェイルオーバーを起動させる。この場合には、フェイルオーバーは、フェイルオーバータイムアウトを待つ必要なしに直ちに起こることになる。
結果：フェイルオーバー
５．ネットワーク状況のせいで、プライマリ６０２Ａが入力メッセージを受信できなくなる。この場合には、バックアップ６０２Ｂは、入力メッセージを受信するが、当該メッセージに関連する如何なる応答もプライマリ６０２Ａから受信することなく、タイムアウトが失効することになる。繁忙な市場では、プライマリ６０２Ａが応答を送っている限り、この事態がフェイルオーバーを起動させることはない。閑散とした市場では、フェイルオーバーが起動されることになろう。
結果：フェイルオーバー又は正常
６．ネットワーク状況のせいで、プライマリ６０２Ａとバックアップ６０２Ｂの間で、所与の入力についての応答メッセージの一部喪失が引き起こされる。この場合には、所与の入力メッセージについて（全部ではなく）一部の出力メッセージが受信され、後続の入力について少なくとも１つの応答が受信される。バックアップ６０２Ｂは、応答中のフィールドと前のフィールドの組合せを使用することによって、プライマリ６０２Ａによって処理されたメッセージのシーケンスを確定することができる。出力の不等はＦＴメッセージマネジャがこれに着目する。
結果：正常
７．バス又はネットワーク問題が起こり、バックアップ６０２Ｂが入力又はプライマリ６０２Ａの応答を受信できなくなる。この場合には、バックアップ６０２Ｂは、フェイルオーバータイムの１／２の時点でピングを試みることになる。ピングが失敗すれば、バックアップ６０２Ｂは引き継ごうと試みることはしない。
結果：バックアップは停止。再始動されるか又は新たなバックアップが始動される。
８．ネットワーク状況のせいで、プライマリ６０２Ａとバックアップ６０２Ｂの間で所与の入力についての応答メッセージが全て失われる事態が引き起こされ、２つ以上の応答メッセージが送信されたと推測される。この場合には、所与の入力メッセージについての全ての出力メッセージは、プライマリ６０２Ａとバックアップ６０２Ｂの間で取りこぼされ、後続の入力についての少なくとも１つの応答が受信される。バックアップ６０２Ｂは、前のメッセージ表示子を使用しても、出力メッセージの脱落中にどれほどの入力メッセージがプライマリによって処理されたかを知りようがない。結果として、バックアップ６０２Ｂは、自身がプライマリ６０２Ａと同じシーケンスでメッセージを処理していると確信することがもはやできない。
結果：バックアップは停止されなくてはならない。再始動されるか又は新たなバックアップが始動される。
９．ネットワーク状況のせいで、バックアップ６０２Ｂが入力メッセージを受信できなくなる。この場合には、バックアップ６０２Ｂは、自身が受信しなかった入力メッセージに応答しているメッセージを受信することになる。
結果：バックアップは停止されなくてはならない。再始動されるか又は新たなバックアップが始動される。
１０．プライマリ６０２Ａからの出力メッセージとバックアップ６０２Ｂからの出力メッセージが相違する。この場合には、プライマリがバックアップより多くの応答メッセージを生成したか又は内容が異なっているかのどちらかである。エラーがログを取られ、高優先順位で報告され、するとバックアップはもはやバックアップとして行動できなくなる。
結果：バックアップは停止されなくてはならない。再始動されるか又は新たなバックアップが始動される。
１１．ＦＡＩＬＵＲＥ ＴＩＭＥＯＵＴの下に回復可能なデータベースエラー。バックアップ６０２Ｂはフェイルオーバーに備えるが、プライマリ６０２Ａは、バックアップ６０２Ｂが引き継ぎを終える前は、書き込むことができるであろう。
結果：正常
１２．ＦＡＩＬＵＲＥ ＴＩＭＥＯＵＴの下に回復不可能なデータベースエラー。プライマリ６０２Ａは、故障タイムアウトに反応しなくなり、バックアップ６０２Ｂが引き継ごうと試みることになる。バックアップ６０２Ｂは直ちに引き継ぐことはできないであろうが、データベースが回復され次第、バックアップはプライマリ６０２Ａを締め出し、プライマリ６０２Ａの役割を引き受ける。
結果：フェイルオーバー
【０１００】
別の実施形態では、故障したデータベース５０６に対処し、その様な故障のせいで、ここに記載されているフォールトトレラント機構が、完璧に機能しているプライマリインスタンス５０２からフェイルオーバーすることのないようにする機構が提供されている。データベース５０６自体が、故障又は遅延のシングルポイントとなっている場合もある（例えば、１つの実施形態では、データベース５０６は、オラクル（Ｏｒａｃｌｅ）ＲＡＣを使って実装されており、オラクルＲＡＣは、場合により、内部故障後に再構成している間は何秒間もトランザクションを遅延させることがある）。図５に示されている様に、データベース切替機構５４４が提供されている。動作時、プライマリインスタンス５０２は、自身がデータベースからの応答を、その厳密な値は実装依存性であるＸ秒という時間内に得ていないと判定すれば、プライマリインスタンス５０２が完璧に正常であるにもかかわらずバックアップインスタンス５０４がいま正に引き継ぎに入ろうとしていると認識する。プライマリインスタンス５０２は、次いで、バックアップインスタンス５０４との会話を開始し、待機データベース５４２への切替を調整することができる。この切替は市場の中断なしに行われ、フェイルオーバープロセスとの調整が図られなくてはならない、というのも、データベースはどのインスタンスをプライマリインスタンスにするかの決定者であるために、データベース切替中はフェイルオーバーを無効にしておかなくてはならないからである。データベース切替が完了すれば、フェイルオーバーは、再度有効にされる。
【０１０１】
図９は、図６のフォールトトレラントシステムの動作を実演する更に詳細なブロック線図を描いている。
【０１０２】
バックアップ６０２Ｂは、「ブロッキング」データをメッセージシーケンス表に書き込むことによって、プライマリ６０２Ａを締め出し、それにより「プライマリ暴走」を阻止する。プライマリ６０２Ａは、メッセージの送信については、当該メッセージと関連付けられている入力が持続させられるまで送出することができないので、バックアップ６０２Ｂには、ブロッキングデータより前に書き込まれたメッセージしかプライマリ６０２Ａによって送信され得ないことが分かっている。
【０１０３】
図１０は、図６のフォールトトレラントシステムと共に使用するためのデータベース６０４の例示としての動作を描いている。
【０１０４】
図１１は、図６のフォールトトレラントシステムによって利用される例示としてのデータ構造であって、注文履歴及び取引データの完全性データを提供するデータ構造を描いている。
【０１０５】
引き継ぎ中のバックアップ６０２Ｂは、これより自身がデータベース内でプライマリ６０２Ａとなることをマークした後、データベースに、入力メッセージ識別子ついて、当該バックアップがプライマリの処理を逃したかもしれない識別子を（バックアップが見た直近の入力ＩＤを表明することによって）求める。バックアップ６０２Ｂは、次いで、それらの入力を、プライマリ６０２Ａがそれらを処理したのと同じシーケンスで実行することになる。データベースにはバックアップが問い合わせた入力ＩＤ後に入力された全ての注文は無効である（そして、引き継ぎ中のバックアップによって再生されることになる）ことが分かっているため、データベース手続きは、それらのエントリを、注文履歴表から別の「フェイルオーバー注文履歴」表へと、取引表から別の「フェイルオーバー取引」表へと、移す。この様にして、注文履歴表と取引表は、照会のための一貫性が維持され、なお且つ何が起こったかについての完全な記録を保持する。
・アプリケーションフェイルオーバー中のデータを再生する。
・バックアップエンジンが、メッセージを、プライマリと同じ順序で処理する。
・フェイルオーバーイベントの時、バックアップは直近の既知のメッセージを識別する。メッセージは、注文表と取引表の１つ１つの入来記録にタグ付けされているＭＳＧ ＳＥＱによって識別される。
・ＤＢは、直近の既知のメッセージ後にプライマリによって書き込まれた全ての注文と取引のデータを拾う。
・データを、注文表と取引表からフェイルオーバー表へ移す。
・プライマリデータがフェイルオーバー表へ移されることで、どのデータも失われない。
バックアップエンジン処理の妥当性確認
争議の裁定
規制の必要性の充足
に有用である。
・バックアップ（これよりプライマリ）が徹底して再生データを実際に挿入するので、更新は必要ない。
・ＦＡＳは、常に、情報に対して一貫した所見が得られる。
【０１０６】
ｉ．実施例
【表１】
0005528526.tif 000002
【０１０７】
例えば：
・入力１、２、５、３、４、６が、プライマリによって受信される。
・入力２、１、５、４、６、３が、バックアップによって受信される。
・プライマリは、入力１、２、５、３、４を処理し、プライマリのデータベースに書き込む。
・バックアップは、１、２、５についてプライマリの出力を受信する。バックアップはそれらを処理する。
・その後、バックアップは、プライマリＮＩＣ故障のせいでタイムアウトを超過しても何も受信しない。
・バックアップは、引き継ぐことを決意する。
・バックアップは、プライマリをデータベースからブロックアウトする。
・バックアップは、プライマリが入力５の後に処理した入力を要求する。
・データベースは、入力３及び４から生じるデータを、注文履歴表から注文オーバーラップ表へ、取引表から取引オーバーラップ表へ移す。
・データベースは、入力ＩＤ３と４を返す。
・今やプライマリとなったバックアップは、プライマリとして３と４を処理し、データをデータベースに書き込む。
・今やプライマリとなったバックアップは、３と４についてｐｏｓ−ｄｕｐであるとするメッセージを発送する。
・今やプライマリとなったバックアップは、プライマリとして、これより６を処理する。
【０１０８】
以上の詳細な説明は、従って、限定を課すのではなく説明を目的とすると考えられるべきであり、本発明の精神及び範囲を定義することを意図しているものは、付随の特許請求の範囲で並びにあらゆる等価物であることを理解されたい。
【符号の説明】
【０１０９】
５００  フォールトトレラントシステム
５０２  プライマリインスタンス
５０４  バックアップインスタンス
５０６  データベース
５０８、５１２  ネットワーク
５１４  フォールトトレラント論理
５１６  プライマリ故障検出論理
５１８  入力受信部
５２０、５２２  ゲーティング論理
５２４  バッファ
５２６  コンパレータ
５２８  バックアップ故障検出論理
５３０  出力突き合わせ論理
５３０  データベース模倣論理
５３２  突き合わせ論理
５４２  待機データベース
５４４  データベース切替機構
５４８  クロック
５５０  クロック入力
６００  金融取引所の商取引エンジン
６０２  突き合わせエンジンクラスタ
６０２Ａ  プライマリサーバ、プライマリ
６０２Ｂ  バックアップサーバ、バックアップ
６０４  データベースクラスタ
６０６  注文エントリバス
【図１】
0005528526.tif 000003
【図２】
0005528526.tif 000004
【図３】
0005528526.tif 000005
【図４】
0005528526.tif 000006
【図５】
0005528526.tif 000007
【図６】
0005528526.tif 000008
【図７】
0005528526.tif 000009
【図８】
0005528526.tif 000010
【図９】
0005528526.tif 000011
【図１０Ａ】
0005528526.tif 000012
【図１０Ｂ】
0005528526.tif 000013
【図１１Ａ】
0005528526.tif 000014
【図１１Ｂ】
0005528526.tif 000015
【図１１Ｃ】
0005528526.tif 000016