読者です 読者をやめる 読者になる 読者になる

Software Transactional Memo

STM関係のことをメモっていこうと思います。

分散プログラミングモデルおよびデザインパターンの考察 その2

前回の記事では

  • 分散システムのデザインパターンと銘打っておきながら並列・並行システムの分野の話からクラウド環境へとこじつける事を「分散システム」と呼んだ事。
  • システム全体を決定づけるわけでもない通信パターン上の選択肢の一部を切り出してシステムの本質のように呼んだ事。
  • プログラミングモデルと言いながらプログラミングモデルの話が一切出なかった事。

のうち一番上についてしか書かなかったので次に真ん中の項目についての話をする。物事を分類する際の一般論としては MECE であることが好まれるがYahoo!の記事はレイヤーも目的も様々な物を一緒くたに語っており、取り繕おうにも議論の空間があやふやなので何に対して網羅的なのかも議論ができない。「マスターやワーカーというのは役割の議論であり通信パターンの議論ではない」「Producer-Consumerはデータフローの一種と呼べないのか?」「データフローは通信のデザインパターンではなく処理をソフトウェアパイプライン上で並列化させる方法の一種に過ぎないのではないか」などなど言いたい事はあるが、このYahoo!の分類法はすぐ下の表の中で星取表を作るために逆算して捻り出したものに過ぎないのではないかと想像するので深追いするのは控える事にする。

通信パターンの分類

こういうのは新しく分類法を作っても微妙なねじれ関係にあるような物が次々と発明されてレイヤーが混線した議論になりがちである。特殊なミドルウェアが出てくるたびに頭を捻り直すよりは、通信パターンを網羅するために通信レイヤーだけで頑張っているミドルウェアの実例から学ぶのが良いと思う。具体的には ZeroMQ のドキュメントが割と網羅的にあれこれ書いている。 

ØMQ - The Guide - ØMQ - The Guide

結構長いので全部に目を通す必要はないが、メッセージングのパターンに関しては以下のものを組み込みでサポートしていると書いてある。

  • Request-reply, which connects a set of clients to a set of services. This is a remote procedure call and task distribution pattern.
  • Pub-sub, which connects a set of publishers to a set of subscribers. This is a data distribution pattern.
  • Pipeline, which connects nodes in a fan-out/fan-in pattern that can have multiple steps and loops. This is a parallel task distribution and collection pattern.
  • Exclusive pair, which connects two sockets exclusively. This is a pattern for connecting two threads in a process, not to be confused with "normal" pairs of sockets.

 

当然ながらこれが全てと断言できる根拠にはならないが、ZeroMQは通信レイヤーでは年季の入ったライブラリなので通信のパターンについては上下のレイヤーに食い込まない範囲でよく考えられているし、自分で考えても通信のレイヤーで思いつく事はひと通りすべてやっていると感じている。解きたい問題に対して通信のレイヤーで適用するアプローチを選ぶ場合、上記の中のどれかでカタがつくと思ってまず間違いないだろう。コンセントのオスメスのようにどちらかが通信を要求するか、もしくはメス-メスコネクタのように両方向からの要求を受け取るかといった通信の方向性による分類、それと同一の通信が分配されるのか複製されるのかといった分類を考えるとZeroMQの整理はよく出来ていると感じる。

それとPub-Subは複数のSubscriberが同一のメッセージの複製を購読しうるというのが単なるキューイングとの最大の差なのだが(だからこそpublishという1対1っぽくない単語をわざわざ使っている)Yahoo!の記事では

この中で、受信方法が通知方式となり、コンシューマ側で通知のフィルタ設定ができる場合には、出版購読(Publish-Subscribe)パターンとなります。 

などと書かれており、これではPub-Subがフィルタとpush通知付きのQueueと見分けが付かないのも残念なところである。

分散システムのデザインパターンにおける前提

分散システムでのデザインパターンという物が求められている割にオブジェクト指向などでよく見るようなデザインパターンが定義されている様子が無いのは、そもそも分散システムと呼んだ際に前提とする条件にバリエーションが多すぎるためである。

分散システムに関して記述した本なら洋書で良い物がいくつもあるが、難しそうなリストで威嚇するのは有益ではないので自分が読んだ中でおすすめしたい物でいうと

www.amazon.co.jp

この本が良かった。とはいえこの本から得た自分の知識は遅かれ早かれこのブログにも書いていくのでこの本を読む気力がわかない人も待っていて欲しい。

そして、分散システムについて日本語で説明している物でいうならこの記事がおすすめである。

postd.cc

先ほどの本はこの記事のプレゼン中でも紹介されている。

分散システムにおける前提条件について、例えばメッセージが同期/非同期だとか故障が起きない/起きても検知できる/検知すらできない/むしろ悪意を持っているだとか様々なバリエーションがある。

ミッションクリティカルな世界を相手にするなら最悪な状況をベースラインに考えるべきなのだが、最悪中の最悪の状況だとシステムに参加したすべてのプロセスがデタラメに動いて破綻させようとしてくる事になるし、その状況ではどんな頑健なアルゴリズムも動きようがない*1。世の中のビザンチン故障は上のブログで書かれているように

www.amazon.com

通常は戦う必要はないと書かれている。僕はこの考えに賛成であり、あまり真面目にこの分野を追いかけてはいない。

故障したかどうかわからないCrash-failureとかCrash-recoverとか呼ばれる(文献によって方言がある)故障モデル設定は現実の問題に近いが、それでもこの故障モデルに対処することを目的としたアルゴリズムはRaftやPaxosのように効率という点に於いてはあまり優れていない。確かに有用だが現実の問題すべてを解決する銀の弾丸ではない。

現実の分散システムがどのように対処しているかというと、故障を検知でき故障したら復旧しないというFail-Stop故障モデルを仮定した上で、発見の難しい(ある程度の規模にならないと顕在化しない)バグに関しては目を瞑り、起きた順に穴を塞いでいるというのが実情のように見える。例えばSplit brainという故障パターンはシステムを二分する故障であり、それわざと発生させた後で復旧させその挙動をテストするJepsen Testという物を様々な分散システムに対して行っているのが以下のブログの記事リストである

Jepsen

面白いぐらいに様々なデータストアが故障に対処できていない事がわかる。EtcdやConsulやZooKeeperやRiakはさすがといったところであるが。ほとんどのシステムが対処できていないのはそもそもSplit brain後に復旧するというのはFail-Stop故障モデルでは起き得ない状況であるためFail-Stop故障モデルを前提とした解決策では対処できないのである。論文を読んで実装しても前提条件が異なれば問題を解決できない。

現在の人類の最先端の一つであるGoogleでどうしているかというと、PaxosのようにCrash-Recover故障モデルに耐えるアルゴリズムをコアに据え(Chubby)、そいつに分散システムとしての調停や一貫性の拠り所としての役目を与え、スケールさせたいシステム自体は様々な工夫を駆使してリトライや複製を管理している。問題のパターンも対策も無数にあるので一概な事は言えないが、例えば

MillWheel: Fault-Tolerant Stream Processing at Internet Scale

はストリーム処理の起点と終点でのみシステムのマスタが一貫性管理を行って処理全体としての冪等性を実現し、処理前データと処理済みデータをBigTableのような分散永続ストレージで保護する。それによって個々の処理ステップでの複製の作成を回避しながらも全体としてはCrash-Recover故障モデルに耐えるように設計してある。こういう解決策は広く一般に安易に展開できるものではないが、様々な前例に組み込まれる工夫をデザインパターンを抽出していく事で組み立てる事が可能であると考えている。デザインパターンを探していく行為は将来のより良い分散システムの設計時により良い指針を与えてくれるものであり有益かも知れない。

ここまででおよそ4000文字も書いてしまったので、詳細のデザインパターンについてはまた次の投稿で書いていく。

*1:むしろ、そんな偉大なアルゴリズムが存在するなら今この現実世界も現在進行形でその未知で偉大な耐故障アルゴリズムによって何らかの目的を達成しようとしている最中である