はじめに

前回は，分散システム技術を基本とする耐障害性のための仕組みとして，レプリケーションとロギングについて述べました。今回は，分散システムにおいて複数のプロセスが協調して動作するための仕組みであるコーディネーションについて，その概要を説明します。

コーディネーションとは

並列データ処理系におけるコーディネーションは，複数のプロセス間において，協調して動作をする，または，同意を取るための技術です。すなわち，コーディネーションを行うことにより，並列データ処理系における複数のプロセスが同じ目的（もしくは値）を共有し，各々がその目的のもとで何らかの処理を実行できるようになります。当該技術は，たとえば，複数のプロセスにおける状態やレプリカ間の値の一貫性を保つために用いられます。

コーディネーションにおいては，多くの場合，次のことを前提として議論されるため，特に明示的に言及しない限り，本連載においても同様の前提を想定して説明をすることとします。

• 任意のプロセスがクラッシュしうる。ただし，ビザンチン故障（※1）は想定しない
• メッセージの送信にかかる時間は有限だが上限がない。すなわち，分散システムモデルにおける非同期システム（Asynchronous System）を想定する
• 複数のプロセス間においては，固定的なマスタ／スレーブの関係は存在しない

コーディネーションには，おおまかに分類すると，次の4種類が存在します。

• 分散排他制御（Distributed Mutual Exclusion）
• 選挙（Election／Leader Election）
• グループ通信（Group Communication／Multicast）
• コンセンサス（Consensus）

分散排他制御は，その名のとおり，分散環境で排他制御を行う（ロックを取る）ことであり，すなわち，クリティカルセクションに入るプロセスを選択することです。選挙は，リーダ選挙とも呼ばれ，ある特定の作業を行うためのリーダプロセスを選択することです。分散排他制御は，ロックを取るリーダプロセスを選んでいると見ると，選挙の特殊系であると見ることもできます。

また，グループ通信は，あるプロセスがほかの全プロセスにメッセージを送信することであり，いわゆる，マルチキャストです。コンセンサスは，あるプロセスが値の提案者となり，ほかのプロセスがその値に同意をして，全体で1つの値を決定することです。グループ通信とコンセンサスはほぼ同等のものであると考えられています。

これらのコーディネーションにおいては，それぞれ適切な用途が存在しますが，必ずしも用途が限定されているわけではありません。たとえば，グループ通信やコンセンサスにおいては，複数のプロセス間で同じ値で同意したいという場合に用いられることが一般的ですが，任意のプロセスが任意の値を提案できるため，たとえばいずれかのプロセスを代表プロセスとして提案することにより，分散排他制御や選挙の目的で用いることも可能です。

今回は，汎用性が高いコーディネーションの方法であり，幅広い用途で用いられているコンセンサスについて，もう少し深堀りしてみたいと思います。

※1）

ビザンチン故障は，プロセスの動作において仮定をおかない故障です。すなわち，ビザンチン故障状態であるプロセスは任意の動作を実行する可能性があり，たとえば，要求に対して不正または一貫しない応答を返します。

コンセンサスアルゴリズム

代表的なコンセンサスアルゴリズムである，2相コミット，ZAB，Raft，Paxosについて，それらの概要を説明します。それぞれの特性を明確にすべく，初めに，分散システムにおける順序（ordering）について整理します。

準備（分散システムにおける順序について）

コンセンサスにおいては，複数のプロセス間でメッセージをやりとりするものであり，受信側のプロセスでメッセージがどのような順序で到達するか，もしくは，どのような順序で値の同意を取るか，が重要なポイントの1つであると考えられています。この順序を表す性質として，分散システムにおいては，おもに次の3つが定義されています。

FIFO ordering

受信側において，送信側のメッセージ送信順序でメッセージが到達する性質

Causal ordering

あるメッセージが別のメッセージの前に送られた場合，当該メッセージ間には因果関係があるとし，受信側では当該因果関係が保たれるようにメッセージが到達する性質

Total ordering

あるプロセスであるメッセージが別のメッセージより前に到達した場合，すべてのプロセスにおいてその順序でメッセージが到達する性質

補足すると，FIFO orderingはプロセスごとの因果関係（Causality）のみを保証する性質であり，Causal orderingはプロセス間の因果関係も保証する性質であると言えます。すなわち，Causal ordringであればかならずFIFO orderingです。たとえば，Causal orderingにおいては，プロセスA，B，Cがあり，プロセスAが全員にメッセージαを送り，プロセスCはメッセージαを受信した後に，全員にメッセージβを送る場合，メッセージαとメッセージβには潜在的な因果関係があるとして，全プロセスには当該因果関係が保たれるようにメッセージが到達します。Total orderingはすべてのプロセスにおいてメッセージの到達順序が同一であることを保証する性質です。Totalというとほかのorderingを包含しそうな名前ではありますが，FIFO orderingともCausal orderingとも限りません。

コンセンサスを用いるアプリケーションにおいては，当該コンセンサスが保証する順序を前提に，アプリケーションロジックを記述します。すなわち，orderingの制約が強ければ強いほど，一般的には，より簡潔にアプリケーションを記述することができると考えられ，たとえば，FIFOかつCausalかつTotalであるコンセンサスを用いる場合は，Totalのみを保証するコンセンサスを用いる場合と比較して，アプリケーションを非常にシンプルに記述できる場合があります。