はじめに
前回 は、分散システム技術を基本とする耐障害性のための仕組みとして、レプリケーションとロギングについて述べました。今回は、分散システムにおいて複数のプロセスが協調して動作するための仕組みであるコーディネーションについて、その概要を説明します。
コーディネーションとは
並列データ処理系におけるコーディネーションは、複数のプロセス間において、協調して動作をする、または、同意を取るための技術です。すなわち、コーディネーションを行うことにより、並列データ処理系における複数のプロセスが同じ目的（もしくは値）を共有し、各々がその目的のもとで何らかの処理を実行できるようになります。当該技術は、たとえば、複数のプロセスにおける状態やレプリカ間の値の一貫性を保つために用いられます。
コーディネーションにおいては、多くの場合、次のことを前提として議論されるため、特に明示的に言及しない限り、本連載においても同様の前提を想定して説明をすることとします。
任意のプロセスがクラッシュしうる。ただし、ビザンチン故障[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のみを保証するコンセンサスを用いる場合と比較して、アプリケーションを非常にシンプルに記述できる場合があります。
2相コミット（Two-Phase Commit）
2相コミット（2 Phase Commitまたは2PC：［2 ］ ）は、Jim Gray博士によって提案された最も基本的なコンセンサスアルゴリズムの1つであり、複数のプロセスをまたいだ分散トランザクションにおいて、原子性（Atomicity）を実現するための方法として広く用いられています。
2PCは、その名のとおり、2つのフェーズから構成されており、フェーズ1において、コーディネータと称されるトランザクションの（一時的な）管理プロセスが、コホートまたはリソースマネジャと称されるトランザクションの実行プロセス群に対してPrepareメッセージを送り、フェーズ2において、すべてのコホートからCommit可能であるという応答を受け取ると、すべてのコホートにCommitメッセージを送り、当該トランザクションをCommitします。一方、少なくとも1つのコホートからコミット可能でないという応答を受け取ると、すべてにスレーブにAbortメッセージを送り、当該トランザクションをAbortします。
2PCそのもの自体はいかなるorderingも保証しません。ただし、分散トランザクションをGlobally Serializableに実行できるのであれば、当然、Total orderingが保証されることとなります。なお、元来の2PCは、障害に対しては必ずしも強い設計ではありません。たとえば、2PCの実行中にコーディネータがクラッシュした場合は、当該トランザクションはブロックされてしまいます。また、コホートの一部が2PCの実行中にクラッシュした場合は、Commitに至ることができない場合があります。加えて、同意をとる値も2値（Commit or Abort）だけなので、コンセンサスの特殊系と見る方が正しいかもしれません[2] 。
[2] 3 Phase Commit（3PC）や、Paxos-CommitなるPaxos（後述）を応用した2PCも存在します。これらは2PCと比較してより障害に強い設計になっています。詳細は文献［3 ］［ 4 ］を参照ください。
ZAB
ZAB（［ 5 ］ ）はYahoo!によって開発されたコーディネーションエンジンであるZookeeperにおいて用いられているコンセンサスアルゴリズムです。
ZABにおいてコンセンサスをとる場合は、まず、選挙により値を提案するProposerを選択します。次に、Proposerが、提案を受け取るFollowerに対して、2PCと類似の方法で任意の値を提案（送信）します。このとき、定足数（一般的には過半数）からその値でコミット可能であるというメッセージを受け取ることができれば、Proposerは当該提案をコミットします。
ZABにおける重要なポイントは、選挙において常に定足数からの承認を必要とすることにより、Proposerが常に1つのみ存在することを保証し、当該Proposerからの提案をFIFOにすることで[3] 、提案の到達におけるorderingをFIFOかつCausalかつTotalにしている点です。
ZABに類似したコンセンサスアルゴリズムとして、スタンフォード大学で提案されたRaft（［ 6 ］ ）があります。Raftは、メッセージ数の削減などの種々の効率的な仕組みが提案されているものの、本質的な発想や仕組みはZABと非常に類似していると考えられます。
PAXOS
PAXOS（［ 7 ］ ）はLeslie Lamport博士により提案された初期のコンセンサスアルゴリズムであり、現在、最も広く使われているものの1つです。PAXOSのプロトコルは、ZABと類似しているものの、Proposerは複数の場合であっても動作するものであるため、ZABと比較すると汎用性が高いですが、その反面、少し複雑な仕組みです。PAXOSにおけるメッセージの到達は、Total orderingを保証しますが、複数のProposerが同時に存在しうるため、Causal／FIFO orderingは保証しません。
Hadoopなどのデータ処理系で用いられているコンセンサス
Hadoopにおいて用いられる分散ファイルシステムのHDFSにおいては、ファイルのメタデータを管理するNameNodeの可用性向上のために、NameNodeを複数台構成にし、それらへの更新をStrong ConsistentにするためにZookeeperを用います（［ 8 ］ ） 。また、Hadoopにおけるリソース管理プラットフォームであるYARN（MRv2）のResource Managerにおいても、その高可用性を実現するために、Zookeeperを用いたメタデータの冗長管理を行います（［ 9 ］ ） 。商用版Hadoopを提供するWANdiscoにおいては、複数のレプリカにおける更新をPaxosの改良版を用いてStrong Consistentにしているようです（［ 10 ］ ） 。
まとめ
今回は複数のプロセスで協調して動作するための仕組みであるコーディネーションについて、その概要を説明しました。コーディネーションは分散システムのメイントピックの1つでもあり、非常に深い技術ですので、詳細においては参考文献に挙げた教科書などを参照してください。
今回で第一部は終了です。ここまでお読みいただきありがとうございました。少し駆け足だったかもしれませんが、「 Hadoopなどのデータ処理系の内部に対する理解が深まった」と少しでも多くの読者が感じてくれたとしたら非常に幸いです。次回からは第二部に入っていきますので、引き続きよろしくお願い致します。
第二部について
第一部においては、並列データベースにおいて研究・開発されてきた並列データ処理アルゴリズムや分散システムにおける基本技術をトップダウン的に解説し、Hadoopなどで当該技術が実際にどう用いられているかを補足してきました。第二部では、実際の並列データ処理系の設計や実装を具体的に紹介し、たとえば、前半に紹介した基本技術がどのような設計方針で利活用されているかをボトムアップ的に見ていく予定です。
実際の処理系の内容においては、各処理系の専門家に語っていただくほうがより良いと思いますので、第二部は次の4人の専門家にバトンタッチすることとしました。前半は、Hadoopコミッタである小沢健史さんにより、Hadoop MapReduce、YARN、Tezについて、中盤は、Cloudera社の矢野智聡さん、嶋内翔さんにより、Impalaについて、後半は、Sparkコミッタである猿田浩輔さんにより、Sparkについて、それぞれご紹介いただく予定です。第二部も濃い内容になる予定ですので、引き続きよろしくお願いいたします。
