Paxosと分散コーディネーションエンジン(DConE)

分散環境でのActive-Active複製を可能にするDConEの紹介です。Paxosを拡張して、WAN環境でも情報の一貫性が保障されるようになっています。
1. Paxosについて
Leslie Lamportが提案した信頼性の低いプロセッサから構成されるネットワークにおいての合意の問題を解決するためのプロトコルの集合。Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年でした。
PaxosアルゴリズムではState Machine(状態機械)が分散システムの各ノードにインストールされ、トランザクションの順序を保障します。State MachineはProposers、Acceptors、Learnersのいずれかの役割を果たす。Paxosアルゴリズムでは以下の3つのフェーズがコンセンサスの取れるまで繰り返されます。①CoordinatorになるNodeが選択され②トランザクションProposeがブロードキャストされ、受け取ったノードはAcceptするかReject③関連するノードの過半数がAcceptすれば、コミットメッセージがブロードキャストされトランザクションを実行。プロポーザル番号は一意となるようにします。

2. DConE(Distribution Coordination Engine)についてスライド1
DConEはPaxosをWANでも使えるように拡張したものです。DConEの主な構成要素は図の通りです。実際の動きを簡単に説明します。
アプリケーションの書き込みトランザクションが発生すると当該ノードのProposal ManagerはLocal Sequence Number(LSN)を付与したProposalを生成し、障害発生に備え、セーブします(Proposal Log)。次にAgreement Managerは保持しているGlobal Sequence Number(GSN)をIncrementしたAgreement Memberを決定します。GSNは全てのNodeでAcceptされた最後のProposalの番号です。このAgreement Memberにより当該トランザクションに関するコンセンサスをすべてのノードに対して取ることを試みます。このデータもAgreement Logとしてセーブされ、障害時にはProposal Logと一緒に回復処理に使われます。
過半数がAcceptすれば、Agreement NumberがそれらのノードのGSNになります。コンセンサスに達するとDConEはトランザクションをLocking Managerに渡します。Proposalを発行したNodeはGSNの合意は待ちますが、他のノードのトランザクションの完了を待つことはありません。以下、DConEの特長を説明します。

2.1 ローカルな順序の保持(米国特許#8364633)
DConEは性能向上のため、並列してコンセンサスの処理を行います。このため、ノード内でアプリが求める順序がGSNを決める際に逆転してしまう可能性があります。ノード内の順序を決めるためのLSN(Local Sequence Number)とネットワークで接続されたノードでのGSN(Global Sequence Number)の2つによりトランザクションの順番を決定します。ネットワークはLANでもWANでも対応可能です。

2.2 Locking Scheduler
Locking SchedulerはGlobal Orderは意識しません。ローカルキューに従ってトランザクションの処理をします。アプリとのインターフェースはDConE は持っておらず、Locking Schedulerが面倒をみます。Locking Schedulerという名前ですがロックのスケジュールをする訳ではなく、言ってみれば、Database Schedulerのような振る舞いをする訳です。

2.3 性能・スケーラビィリティの向上
DConEは大規模なWAN環境でもPaxosアルゴリズムが動くような強化をしています。主なものは以下です。

・Paxosは多数決論理で動く訳ですが、オプションで決め方が選べます。あるノード(Singleton)のみがプロポーザルのレスポンスをするような設定が可能です。一番多くユーザが使っているところをSingletonノードにすることでWANのトラフィックを下げることができます。リージョンで多数決論理を動かすことでFollow the Sunのようなことも可能です。また偶数ノードの場合はTie Breakerを決めることで対応できます。
・複数のプロポーザルの処理を並行して行うこともできます。Agreement Number取得の際に発生する衝突による性能劣化への対処もされています。新しいノードの追加・既存ノードの削除も動的に行えます。
・ディスク・メモリ上にセーブされたState Machineの情報をいつまで保持すべきかは、安全性とリソース使用率のバランスをとるのに苦労するところです。一定間隔でノード同士がメッセージをやり取りすることで解決しています。

2.3 自動バックアップとリカバリ
Active-Activeの複製により全てのノードのホットバックアップが取られます。あるノードにネットワーク障害が起きてもリードだけは可能としています。ライトは禁止されSplit Brainにより情報不一致が発生することを避けています。CAP定理によればC(Consistency)、A(Availability)、P(Partition-Tolerance)の3つを同時に満たすことはできません。DConEはCとAを優先するような設計思想となっています。
障害が復旧すれば、DConEが障害の期間中にAgreeされたトランザクションをAgreementログ、Proposal Logより自動的に復旧します。

3. 終わりに
以上、大まかな説明ですが、詳しくはDConEのWhitepaperを参照ください。
http://www.wandisco.com/system/files/documentation/WANdisco_DConE_White_Paper.pdf

avatar

About Kenji Ogawa (小川 研之)

WANdisco社で2013年11月より日本での事業を展開中。 以前は、NECで国産メインフレーム、Unix、ミドルウェアの開発に従事。その後、シリコンバレーのベンチャー企業開拓、パートナーマネージメント、インドでのオフショア開発に従事。

0 Responses to “Paxosと分散コーディネーションエンジン(DConE)”


  • No Comments

Leave a Reply