分散ノードの整合性 ～NewSQLへの道～

投稿日: 2020年4月25日 作成者: climb
このエントリーをはてなブックマークに追加
LINEで送る

ザNewSQLへの道シリーズの最終回です。と言うほど深く切り込んできたわけではありません。前々回「ACID原理とCAP定理」という記事でNewSQLが生まれた背景を、前回は「CAP定理の壁」でNewSQLにおけるCAP定理の捉え方をざっと説明しました。要するに、NewSQLが分散システムでConsistency（整合性）を確立してOLTP（オンライン トランザクション処理）をサポートするまでの経緯です。今回は、いかにして分散システムで整合性を保つのか、具体的な方法例を見ていきたいと思います。

複数ノードに分散されたデータベースが、データの更新をコミットするには複数ノード間でのその処理命令に対するコンセンサスが必要です。たとえば、相撲の取り組みに物言いがついたとき、審判委員の親方衆が土俵の真ん中に集まって何やらひそひそ話し合うでしょう。あれを複数ノードでもやらなければなりません。

問題は、土俵がないことです。いや、問題はそこではなくて、仮に集まる土俵があっても、ノードは自分から話し合いません。だから、ノードが集まらず、話し合いもせず、互いに目配せでコンセンサスに至るような仕組みが必要です。人呼んで「コンセンサス アルゴリズム」です。

いちばん有名なコンセンサス アルゴリズムはPaxosで、GoogleのSpannerやAppleのFundationDBに使われているようです。しかし、Paxosは複雑すぎるとかで、つまり、親方衆の目配せが意味深すぎて、下手すると眼球運動を司る筋肉がつって顔面神経痛になり、誤解にもとづくコンセンサスが生まれてしまう可能性もあるので、それを単純化して、よりわかりやすくしたのがRaftです。審判部長がウィンクしたら、あとはみんな従うぐらいに単純です。

この相撲のたとえ、全然うまくないのでやめましょう。

Raftの仕組み

RaftはYogaByteDB、CockroachDB、TiDB、MongoDB、InfluxDBなどに全面的あるいは部分的に使われているらしいです。

Raftをひと言で表すと、各審判員が個々にログ台帳を持っていて、審判部長が「よし、書き込もう」と目配せしたら、全員が一斉に書き込み、個々の台帳を統一させる制度です。あ、このたとえはやめるんでした。以下、審判部長を「リーダー」、審判員を「フォロワー」と表します。

Raftの第一段階は「リーダー選挙（Leader Election）」です。

すべての参加ノードには、リーダー、フォロワー、キャンディデート（リーダー候補）の3種類いずれかの役割を担う可能性があります。みんな最初はフォロワーです。フォロワーは必ずリーダーからの信号を待つことから始めます。この待ち時間には制限が決まっていて、選択期限（Election Timeout）として、ランダムに設定されます。リーダーからの信号を受け取らずに選択期限が切れると、リーダー不在と認識し、自分がリーダーに立候補します。

「制限時間ぎりぎりまで待ったけど、リーダーからは梨の礫だし、しょうがない、俺、リーダーやるわ・・・」

という感じです。積極的なんだか消極的なんだかよくわからないけど、やる気のあるのは良いことです。こうして、他の参加ノードに立候補の意思を伝え、自分への投票を依頼し、自分の票は自分自身に投じます。他のノードの大多数が「あ、そう、じゃあ、お前、リーダーでいいよ」と言ったら、立候補したノードがリーダーに就任します。人格とか実績とかは全然関係ないみたいです。

重要なのは、各ノードが個々にランダム設定の制限時間（Election Timeout）を持っている点です。つまり、みんな積極的なわけでも、やる気に満ちているわけでもなくて、自分の制限時間が来たら（つまり、早い者順で）リーダーに立候補しているだけです。

しかし、このランダム設定の制限時間が偶々同時に切れるということが、まったくあり得ないわけではありません。たとえば、5ノード構成のクラスタで、リーダー ノードがダウンしたら、残りの4ノードがリーダーからの信号を受け取れないまま、誰かの制限時間が最初に切れ、そのノードがリーダーに立候補することになります。ここで、仮に2つのノードが同時に制限時間を迎えたらどうでしょうか。

この場合、両方のノードが自分自身の票と他の1ノードの票を得て、2票vs 2票で並び、決選投票が必要になります。が、Raftではそんな面倒臭いことはしません。リーダーが決まらなければ、リーダー不在のまま、次に時間切れを迎えたノードが立候補するの待ちます。この状況は非常に稀で、1度発生するだけでも珍しいのに、連続する（次の時間切れでも再度リーダーが決まらない）ことはほぼあり得ません。リーダー不在時間が長引くことは、データベースのパフォーマンスを損なうことになりますが、そもそもこのElection Timeoutはミリ秒単位の話です。

ログの同期化（Log Replication）

リーダーが決まったら、次は各ノードのログの同期化です。正確には、同期化ではなく複製（レプリケーション）と呼んでいます。参加ノードが全員、書き込み専用のログを持っていて、リーダーが「よし！書き込め」と言ったら書き込みます。つまり、この部分がデータベースの整合性の肝です。

クライアントから受け取るすべてのリクエスト（処理命令）はリーダー ノードに送られます。もちろん、分散システムのサーバーにおいて、必ずリーダー ノードがクライアントからのリクエストを受け取るとは限りませんが、フォロワー ノードがリクエストを受けた場合は、そのままリーダーに転送すれば済みます。

リーダーはまず、自分のログに処理命令を書き込み、それから各フォロワーに「よし！書き込め」と言います。この段階では、まだクライアントにコミットの完了を伝えません。リーダーがフォロワーの大多数からログ書き込みの確認を受け取ってはじめてコミットが可能となり、リーダーがその結果を各フォロワーとクライアントに伝えます。フォロワーも、リーダーからコミット可の連絡を受けてはじめてコミットを実行に移します。

ログの各書き込みには、その対象期間（＝リーダーの任期、つまりElection Timeoutごとの期間）と連番が付記されます。フォロワーは、リーダーから書き込み指示を受けたときに最高位の連番を確認することが義務付けられていて、それに反する場合は、リーダーに書き込み確認を送り返しません。それによって、リーダーのログと各フォロワーのログが常に一致するように徹底されます。何らかの理由でダウンしていたノードが途中で復帰したりすると、ログの不一致が発生する可能性がありますが、フォロワーには連番最高位の確認義務があるので、誤ったデータがコミットされることはありません。ログの不一致が発生した場合は、リーダーがその不一致ログを持つフォロワーに、一致する点までの全書き込みを送り直し、ログを一致させる仕組みになっています。

さらに、不一致ログを持つフォロワーは絶対にリーダーになれないルールもあります。具体的には、各ノードはリーダーに立候補したキャンディデートから投票の依頼を受けたとき、キャンディデートと自分のログの連番最高位を比べ、自分より低いキャンディデートには投票しません。大多数のノードはリーダー（この場合は前リーダーですが）と一致するログを持っているので、不一致ログのノードは絶対にリーダーになれないことになります。

以上が、分散システムの複数ノードがデータの整合性を保つメカニズムです。もう一度、簡単に要約すると、各ノードが自分のログを管理し、それがリーダー ノードの指示のもとに同期化されるので、データのコミットに対する全ノードのコンセンサスが常に維持される仕組みです。

どうでしょうか、土俵越しに目と目で通じ合う親方衆の阿吽の呼吸を感じ取っていただけたでしょうか？あ、このたとえは不気味だからやめるはずでした。ちなみに、Raftは筏（いかだ）ではなく、Reliable、Replicated、Redundant、Fault-Tolerantの略だそうです。正確には、RaftではなくRRRaft（ラ・ラ・ラフト）だったのですね。ここで、ラ・ラ・ランドを思い出した方は、ラ・ラ・ラ・ラブソングを思い出した筆者とは世代間ギャップがあるので、本文中に差し込まれたくだらない冗談の数々をどうか大目に見てください。

 

 

関連したトピックス

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。