Hadoopはどのように動くのか ─並列・分散システム技術から読み解くHadoop処理系の設計と実装

第12回 複数のプロセスにおける協調動作のための仕組み─コーディネーション

この記事を読むのに必要な時間:およそ 4 分

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と比較してより障害に強い設計になっています。詳細は文献34を参照ください。

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と非常に類似していると考えられます。

※3)
TCPでメッセージを送信することにより,メッセージの到達順序をFIFOにします。

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について,それぞれご紹介いただく予定です。第二部も濃い内容になる予定ですので,引き続きよろしくお願いいたします。

参考文献
[1]G. Coulouris, J. Dollimore, T. Kindberg, G. Blair. "DISTRIBUTED SYSTEMS Concepts and Design", Addison-Wesley, 2012.
[2]J. Gray. "Notes on Data Base Operating Systems" Proc. Operating Systems, An Advanced Course. pp.393-481, 1978.
[3]D. Skeen, M. Stonebraker. "A Formal Model of Crash Recovery in a Distributed System", IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. SE-9, NO. 3, 1983.
[4]J. Gray, L. Lamport. "Consensus on Transaction Commit", ACM Transactions on Database Systems, Volume 31 Issue 1, pp.133-160, 2006.
[5]P. Hunt, M. Konar, F. P. Junqueira, B. Reed. "ZooKeeper: Wait-free coordination for Internet-scale systems", Proc USENIX ATC, 2010.
[6]D. Ongaro, J. Ousterhout, "In Search of an Understandable Consensus Algorithm", Proc USENIX ATC, 2014.
[7]L. Lamport. "The part-time parliament." ACM Transactions on Computer Systems, 16(2), pp.133-169, 1998.
[8]http://blog.cloudera.com/blog/2014/05/how-apache-hadoop-yarn-ha-works/
[9]http://hortonworks.com/blog/namenode-high-availability-in-hdp-2-0/
[10]http://www.slideshare.net/Hadoop_Summit/th-1150a230-asundar

著者プロフィール

山田浩之(やまだひろゆき)

日本アイ・ビー・エム株式会社を経て,ヤフー株式会社にて分散型全文検索エンジンの研究開発に従事。2008年上期未踏IT人材発掘・育成事業において高性能分散型検索エンジンの開発によりスーパークリエータに認定。現在は東京大学生産技術研究所にて高性能並列データ処理系の研究開発に従事。博士(情報理工学)。

著書に『検索エンジン自作入門』。