これまで2回の記事にわたり、いかにして質の高い分散システム作ることができるのかについて説明してきた。
ブロックチェーンを形作る分散システムにおけるノード間の同期
https://medium.com/mold-project/%E5%90%8C%E6%9C%9F-d34eeea599ec
ブロックチェーンを形作る分散システムにおける一貫性と複製
分散システムは、高いスケーラビリティ、局所性、可用性を実現するために不可欠な概念である。しかしその一方で、クライアンから見た場合にシステム全体が首尾一貫した単一のものに見えるためには多くの工夫が必要となる。加えて、完全な特徴をもつ分散システムの構築はほとんど不可能と言われており、アプリケーションによってどの性能を重視するべきか選択する必要がある。
これら分散システムの特性を述べてきたと同時に、高い性能を持つブロックチェーンの特徴的な性質についても述べてきた。最後にフォールトトレランス性についてまとめることで、ブロックチェーンが秘めるさらなる大きな潜在性について探ると共に、Tendermint等、各先進的なプロジェクトの考察を通してMOLDが目指すべきシステムを包括的に説明していきたい。
1.はじめに（フォールトトレラント性の概要と全体の流れ）
単一システムと異なり、分散システムは部分的な障害が生じる。単一システムの全体的な障害では、システム全体がダウンしがちである。他方、部分的障害では、全体的な性能に深刻な影響を与えることなく、部分的な障害から回復しつつシステムが稼働し続けることができる。
本記事では、フォールトトレラント性、つまりシステムの一部が故障しても処理を続けられるような性質について以下の順に説明していく。
- どのような性質を持つことがフォールトトレラントとなるか
- 障害にはどのようなものがあり、どのように分類できるか
- 分散システムにおいて実際にどのようにフォールトトレラント性が実現されているか
- 通信上における障害について
- プロセスの回復力を高める”高信頼マルチキャスト”
- 分散コミット問題について
2.フォールトトレラント性とは
フォールトトレラント性
フォールトトレラント性は以下のように定義できる
故障が発生してもそれらに耐えてサービスを継続する性質
また、フォールトトレラント性のあるシステムは、高信頼システムと呼ばれる場合があり、高信頼システムの要素（信頼度）は以下の四つに分けられる。
故障モデル
分散システム内のプロセスに対する代表的な故障は以下の4つである。
**オミッション＝欠落
通信リンクに対する故障も同様に定義される。
ビザンチン故障は、例えば偽のメッセージの配送なども起こり得るため最もタチが悪い。
故障は、冗長性によって隠蔽できる。これは、例えば哺乳類が二つの目、耳、肺を持っていることを考えるとわかりやすい。これらの分散された器官が一部故障しても、故障を隠したままシステムを利用できる。これは物理冗長性と呼ばれる。冗長性には、情報冗長性、時間冗長性、物理冗長性の三つがある。
3.プロセスの回復力
フォールトトランス性の説明に引き続き、どのようにしてフォールトトレランス性が実現されているかを考察する。
プロセスの多重化/複製
典型的な方法は、プロセスの多重化である。グループの中に同一なプロセスを複数作成（複製）することを多重化という。分散システムにおける多重化により、部分的な故障時にも正常なプロセスによるサービスの提供が可能となる。複製されたプロセスをレプリカと呼ぶ。
前回の一貫性に関する記事においても述べたが、（https://medium.com/mold-project/consistency-e3e0fe41358d)
多重化（複製）のアプローチには、以下の二つがある。
- プライマリベースプロトコル（受動的多重化, primary-based protocol）
- 重複書き込みプロトコル（能動的多重化, repilicated-write protocol）
前者では、クライアントからのメッセージに対する処理は主レプリカのみが行い、他のレプリカは主プロセスのバックアップを行う。レプリカ間での処理結果の不一致が発生せず、通信機能の実装がより容易である一方で、主レプリカの故障に対し選択アルゴリズムが必要であり、その処理はある程度複雑である。
後者では、全てのレプリカがクライアントからのメッセージを受け取り処理を行う。この時、メッセージに基づく処理に関して全順序性と原子性の二つの性質が必要となる。そのため、原子マルチキャストというより複雑な通信機能を要する。
kフォールトトレラント性
能動的多重化（重複書き込みシステム）に置いて、k個のコンポーネントが故障しても、正常に動くことを、kフォールトトレラント性を持つという。ビザンチン故障を持つ場合、kフォールトトラント性を持つには、最低2k+1個のプロセスが必要。
原子マルチキャスト問題
上記の多重化モデルの前提として、全ての要求が全てのサーバーに同じ順序で到着するという条件がある。これはアトミックマルチキャスト問題と呼ばれる。これについては5章でより詳しく取り上げる。
プロセス間の合意
プロセス間の合意問題は分散システムにフォールトトレラント性を持たせる上で基礎的かつ重要である。分散合意アルゴリズムの目的は、故障していないプロセス同士がある課題に対して有限回のステップで合意にいたることであり、代表的なものにビザンチン将軍問題がある。
ビザンチン将軍問題
k個の故障プロセスを持つシステムにおいて、2k+1個以上の正常プロセスが存在し、全体としてN=< 3k+1個のプロセスがある場合にのみ合意は達成される。つまり、合意は3分の2より多いプロセスが正しく動作している場合にのみ可能。（それより少ないと、故障したプロセスに欺かれている可能性がある。）
補足：フォルトトレランス性で必要となる正常なノード数について
多くのプロトコルで、ビザンチン障害のノードの最大許容数は、1/3と言われている。以下、その理由を簡単に説明する。
全体ノード数をN、ビザンチンなノードをF、正常にコンセンサスをとるのに必要なノード数をTとおく。
例えば、N-Fの正常なノードが同数に別れたとし、その数を以下のように表す。
N−F / 2
Fのビザンチンなノードは、勝手な振る舞いをするので、正常にコンセンサスをとるためには、以下の式を満たすことが必要。
T > N−F/2+F ⋯①
また、Fのビザンチンなノードが全てオフラインになっている場合を考えると、他の正常なノードによりコンセンサスを取れるので、以下の式が成り立つ。
N−F ≧ T⋯②
①・②より、
N−F > N−F/2+F
∴F < N3
以上より、全体のノードのうち、ビザンチンなノードが1/3より少ない時、コンセンサスを正常にとることができる。
4.高信頼クライアントサーバ間通信
ここまで、分散システム内のプロセス に関するフォールトトランス性について議論し、多重化について学んだ。この章では、通信リンクに関するフォールトトランス性の導入について議論する。
P2P通信
分散システムにおける通信の基本は、1つのプロセスと別の1つのプロセスを繋ぐポイントツーポイント通信（1対1の通信）がある。
TCP
TCP：高信頼な通信を可能とするポイントツーポイント通信
TCPは、シーケンス番号、タイマ、チェックサム、確認応答、再送制御、輻輳制御などの仕組みを持つ。例えば、メッセージの欠落によるオミッション故障は、TCPのシーケンス番号を含む確認応答とそれに基づく再送制御により対処可能である。
故障がある場合のRPC（遠隔手続き呼び出し）
RPCの目的は、ローカルな手続き呼び出しの形により、通信部分を意識することなくプロセス間通信を実現できることである。RPCを使った分散システムで起こりうる障害は以下の5つである。
- クライアントがサーバの位置を特定できない場合。
- クライアントからサーバへの要求メッセージが喪失した場合。
- サーバが要求を受けた後にクラッシュした場合。
- サーバからクライアントへの応答メッセージが喪失した場合。
- クライアントで要求メッセージ送信後に障害が起きた場合。
それぞれへの対処方法として、例外処理やタイマ（制限時間）を設けるといったやり方がある。
5.高信頼グループ間通信
前章で1対1の通信に注目したが、ここでは1対多のマルチキャスト通信の高信頼化について説明する。分散システムでは、互いのサーバに順序も含めてメッセージを漏れなく送付されることが重要となる。
故障がない場合の高信頼マルチキャスト
順番通りにメッセージを各メンバに配送することを考える。
送信者はまずマルチキャストメッセージを手元の履歴用メモリに保存する。また、送信者は受信者から送信確認通知（ACK）を受信する。ACKには、送信が完了した最後のメッセージ識別子を入れて返送させる。メッセージの消失などで、期待する識別子の入ったACKを受信できなかった場合、送信者はメッセージを再送する。
故障がある場合の高信頼マルチキャスト
分散システムにおいてあるプロセスが故障した場合、二つの保証が重要である。
- 送信者からのメッセージが全プロセスに配送されるか、まったく配送されないかのいずれかを保証する。
- 送信者からのメッセージが全てのプロセスに対し同じ順序で配送される保証。
分散システムにおいて、「あるプロセス」ではなく
“メッセージ配送中の「送信者」が故障した場合に、そのメッセージが残り全てのプロセスに配送されるか、あるいは無視される”という性質をもった高信頼マルチキャストは仮想同期と呼ばれる。
また、仮想同期であり、かつ、全順序によりメッセージ配送を行う通信を、原子マルチキャストと呼ばれる。
仮想同期の実装例の一つとしてIsisがある。Isisでは、メッセージmを全てのメンバが受信したとわかるまで、プロセスにmを保持・転送させる
補足：アトミック性(Atomicity)とは（Wikipediaより）
トランザクションに含まれるタスクが全て実行されるか、あるいは全く実行されないことを保証する性質をいう。日本語ではアトミック性または原子性、不可分性とも呼ばれる（不可分操作）。 口座Aから口座Bに対し1万円送金する場合を考えたとき、送金操作は次の2操作によって行われる。
口座Aの残高から1万円を引く
口座Bの残高に1万円を加える
原子性が保証されるとは、上の操作1、2が全て行われるか、あるいは全く行われないことを指す。どちらか片方だけが実行された場合、銀行全体の預金残高に矛盾が発生してしまう。
6.分散コミット
原子マルチキャスト問題を一般化した問題は分散コミット問題と呼ばれる。
原子コミット
異なるサイト状のプロセスが一貫してコミット（commit）あるいはアボート（abort）と判断するような必要があるが、このような処理を原子コミットと呼ぶ。
6–1. 2相コミット
2相コミット（Two-Phase Commit Protocol : 2PC）は、原子コミットを実現する代表的な方式である。名前の通り、各フェーズは2つのステップから成り、以下のように構成されている。
（フェーズ1【投票フェーズ】）
コーディネータは、VOTE_REQUESTメッセージを全ての参加者に送る
VOTE_REQUEST メッセージを受信した参加者は、コーディネータに対し、そのトランザクションをコミット可能ならVOTE_COMMIメッセージを送り、アボートする必要があるならVOTE_ABORTメッセージを送って投票する。
（フェーズ2【コミットフェーズ】）
3. コーディネータは全ての参加者から投票を集める。全ての投票がCOMMITだった場合、自らもコミットし、参加者全員にGLOBAL_COMMITメッセージを送る。一人でもABORTがいればトランザクションの破棄を決定し、GLOBAL_ABORTメッセージを送る。
4. 参加者は、コーディネータからのメッセージを待ち、GLOBAL_COMMITならローカルでコミットし、GLOBAL_ABORTならトランザクションを破棄する。
全体を通して、コーディネータと参加者は以下のように状態遷移する。
SKEEN, D “Nonblocking Commit Protocols.” Proc. SIGMOD Int’l Conf. on Management Of Data. ACM, 1981
ブロッキングコミットプロトコル
上記の2相コミットプロトコルでは大きな問題が存在する。フェーズ3においてコーディネータが故障し、全ての参加者がコーディネータからのメッセージを待ち続ける状態になってしまった時。、参加者は最終的に取るべき動作の決定を協調的に行うことができないというものである。このことから、2相コミットはブロッキングコミットプロトコルと言われる。
実際には2相コミットにおけるブロッキング自体が滅多に起こらないため、さほど利用されないが、ブロッキングを避けるための解決策として、3相コミットプロトコルが考案されている。
6–2. 3相コミット
3相コミットプロトコルは、2相コミットプロトコルと異なり、以下の二つの条件を満たす。これら二つの条件がブロッキングのないコミットプロトコルにとって必要十分であることが [Skeen and Stonebraker, 1983] によって示されている。
COMMIT状態またはABORT状態に直接遷移するような状態は存在しない。
最終決定をする可能性がなくCOMMIT状態に遷移するような状態は存在しない。
SKEEN, D. and STONEBRAKER, M “A Formal Model of Crash Recovery in a Distributed System.” IEEE Trans. Softw. Eng., Mar. 1983
具体的には、2相コミットの二つのフェーズの間にPRECOMMIT状態を設けている。
全体を通して、参加者とコーディネータは以下のように状態遷移する。
2相コミットとの大きな違いは、全てのプロセスは、INIT（初期）、ABORT、PRECOMMIT状態のいずれかに復帰するという点である。READY状態に留まり続けることがないため、残っているプロセスは必ず最終的な決定に至り、ノンブロッキングプロトコルとして作動することができるのである。
３相コミットは、概念の提示にすぎず、コーディネーターの故障が起きても正しく作動するような仕組みはまだ存在していなかった。しかし、ブロックチェーンの登場後、その歴史が大きく動くことになる。Tendermintプロジェクトは、ブロックチェーンに3相コミットを採用することでブロッキングプロトコルを実現している。その詳細は、本記事の最後に説明することにする。
7. ブロックチェーンにおけるフォールトトレラント性
最後に、以上のことを踏まえて、分散システムであるブロックチェーンにおけるフォールトトレラント性についても言及していく。
7–1. ブロックチェーンのフォールトトレラント性
ブロックチェーンのフォールトトレラント性は高い。２章で分類した四つの高信頼性を元に、ブロックチェーンの性質について詳しく見ていこう。
ブロックチェーンは、そのシステムが機能を停止ししてしまう時間や回数は少ない。特にビットコインネットワークでは、ゼロダウンタイムを実現し、一部のノードが故障していても正常に作動し続けているという点で、稀に見る高い可用性と信頼性があるといえる。次に安全性に関してだが、システムが正常に稼働していない時、ブロックチェーンネットワークでは、”トランザクションが処理されず詰まってしまう”、”ネットワーク内のノード間で情報が共有されずフォークしてしまう”といった問題が生じると考えられる。後者の問題は、大きな不具合に繋がってしまう可能性が高い。保守性に関してだが、ビットコインのようなパブリック型のブロックチェーンはコミュニティが分裂しやすく、故障からの回復は難しいといえる。ビットコインネットワークは回復の必要がないほど高い可用性と信頼性があったという点で高く評価できるが、保守性を持たせたいならばプライベートチェーンやコンソーシアムチェーンの選択を考慮すべきである。
またブロックチェーンは、最も対処が難しいとされているビザンチン故障問題に関しても有効な解決策を提示しているという点で大変意義深い。具体的には、PoWなどに代表されるコンセンサスアルゴリズムである。PoWによって、マイナーに、ネットワークを破壊するような行動よりむしろ維持・貢献した方が得をするようなインセンティブ構造をゲーム理論に基づいたアルゴリズムによって形成することで、ビザンチン将軍問題に対応しており、ハードフォークといった新しい問題が生じていることには留意すべきだが、一定の成功を収めていると言える。他には、Hyperledgerで採用されているPBFTもリーダーノードが投票確認を行うことによって高いビザンチンフォールトトレラント性を実現している。
7–2. ブロックチェーンにおけるプロセスの回復力
フォールトトランス性の説明に引き続き、どのようにしてフォールトトレランス性が実現されているかを考察する。
まず、プロセスの多重化のアプローチには以下の二つがあった。
- プライマリベースプロトコル（受動的多重化, primary-based protocol）
- 重複書き込みプロトコル（能動的多重化, repilicated-write protocol）
1のプライマリベースプロトコルを採用しているもので代表的なものは、PoWコンセンサスアルゴリズムに基づくブロックチェーンである。PoWの場合、プライマリベースの中でも特にローカル書き込みプロトコルの仕様となっている。排他制御・リーダー選出アルゴリズムとしてのPoWの元、ハッシュ値の0がn桁続くようなナンス値を一番最初に見つることに成功したマイナーがプライマリサーバとしてブロックを追加する権利を得る。ただし、プライマリサーバとなる権利をもつノードが同時に現れたとき、ブロックチェーンはフォークしてしまう。
一方、2の重複書き込みプロトコルを採用しているもので代表的なものは、PBFTに基づくブロックチェーンである。Tendermintをはじめ各種PBFTベースのコンセンサスアルゴリズムは、各データの更新を最初に責任を持って実行するプライマリサーバを持たず、参加ノード全てが同期間に書き込み操作を行える。つまり、PBFT型の一貫性プロトコルは、重複書き込みタイプの、アクティブ複製プロトコルに近いといえる。
これら一貫性プロトコルの詳細は、分散システムにおける一貫性についての記事（https://medium.com/mold-project/consistency-e3e0fe41358d )でより詳細にまとめてある。
7–3. ブロックチェーンの高信頼通信
ブロックチェーンのプロセスについて言及してきたが、今度は通信リンクに着目してみる。
ブロックチェーンでは、ネットワークに参加する各ノードはP2P通信を行ってデータを共有している。また、リーダー選出アルゴリズムによって選ばれたプライマリなサーバーは、例えばナンスを見つけた際、新しく追加するブロックの情報を各参加ノードに共有するためにマルチキャストを行う。この時、通信リンクやノードに故障が起きた場合を考えると、仮想同期であり、かつ、全順序によりメッセージ配送を行うような、原子マルチキャストを実現させることが重要になる。
では、原子マルチキャスト問題や、分散コミット問題は、ブロックチェーンではどのように解決されているだろうか。
ビットコインのようなPoWを採用したパブリックチェーンにおいて、原子マルチキャストは実現していない。そのため、頻繁にフォークが生じ得る。時間経過と共に各ノードがデータを正しく共有していくため、一貫性が確立されていくものの、ブロックにトランザクションが格納されることを確認するのに10分以上の時間を要する。
ここで、Tendermintコンセンサスアルゴリズムに注目したい。一般に、原子コミットを実現する方法として2相コミットがあり、その改善版としての3相コミット方式が提言されていたが、どちらも不完全なものだった。そこで、Tendermintはブロックチェーンと3相コミット方式を融合し、ラウンドロビン方式の下、ノードにある制約を加えることで原子コミットを実現した。このエキサイティングで新しい分散コミット問題へのアプローチ方法は次章で説明したい。
7–4. Tendermintにおける分散コミット（革新的な3相コミットモデル）
まず、Tendermintは、PBFT型である。Hyperledgerでは、リーダーとなるバリデーターは常に同一のプロセスであるが、Tendermintはリーダー選出アルゴリズムを有し、ラウンドロビン方式によって決定論的にリーダーが決められる。リーダーは、mempoolに格納されているトランザクションをまとめて次のブロックを提案する。この提案を持って、Tendermintコンセンサスは3相コミットを実施し、原子マルチキャストを実現する。Tendermintコンセンサスアルゴリズムは、大きく分けて三つの状態に分けることができる。
- Propose
ステーク量を基準としたリーダー選出アルゴリズムによってラウンドロビン方式で決定論的に選ばれたバリデータセットによるブロックの提案。投票の開始。 - PRE-VOTE
提案されたブロックに対する１度目の投票。2/3以上の賛成が得られればすぐに次のステップに移行するが、集まるまでは制限時間まで待ち状態となる。この制限時間があるため、Tendermintは部分的非同期なコンセンサスアルゴリズムであるといえる。また、この投票アルゴリズムは1/3kフォールトトレランス性を持つ。（3章参照） - PRE-COMMIT
PRE=VOTEで2/3以上の賛成が集まったブロックに対する2度目の投票。この時以下に述べるように、2/3以上の投票が集まらなかった場合の処置がTendermintのスマートな部分である。
6章で述べたように、3相コミットは、PRECOMMITフェーズを設けることで、以下の条件を満たせればブロッキングプロトコルを実現することができた。
- COMMIT状態またはABORT状態に直接遷移するような状態がない
- 最終決定をする可能性がなくCOMMIT状態に遷移するような状態は存在しない。
Tendermintでは、2回目の投票フェーズであるPre-Commitにおいて投票したバリデータはロックされ、ロックされたブロックもしくはPre-Voteで2/3以上の投票を得たブロックにしか投票できない。このロックするという処置のために、上記の2つの条件が満たされる。つまり、各バリデータがPre-Commitで投票できるのは常に一つのブロックに限られることになるため、フォークしない仕組みを実現しているのである。
言い換えれば、「Tendermintコンセンサスは、ブロックを追加するというオペレーションがネットワーク内の全てのノードにおいて行われるか、あるいはどのノードも全く行わないかを保証し、ファイナリティを実現した次世代型コンセンサスプロトコルである」といえる。
Tendermint Documents “https://tendermint.readthedocs.io/en/master/introduction.html"
— — — — — — — — — — — — — — — -
Cosmos Gaming Hub Project(旧MOLD Project)
CEO & Co-Founder
朝野 巧己
全てのゲーム愛好家に最高のエンターテイメントを届けるために
