昨日に引き続いて分散システムのデザインパターンについて書いていきたい。
だがそれ以前に故障モデルに関する前提を忘れてはならない。人によって様々な方針があるが、個人的には分散システムの世界において意識しなくてはならない故障モデルは4つだと考えている。僕は前回のブログに書いた Replication の本をベースに書いており、少し言葉遣いや定義が他とやや違う点は許して欲しい。また、通信の脱落・遅延とはレイヤーが異なる議論である。
故障モデルの分類
故障が起きないモデル
これは故障が起きない世界を仮定するモデルである。これ自体はプロダクションにそのまま投入できるものではない。だがこの故障モデルを想定しても解けない問題は故障が発生する状況では絶対解けない事が断言できたり、合意プロトコルが正しいかを議論する土台となったり、様々な実用的なアルゴリズムや分散システムの土台となるアルゴリズムが生まれる土壌である。かの有名な2-Phase Commitなんかはトランザクションのコーディネータが１参加者としてトランザクションに加わっている場合に永続故障した場合には復旧不能な状態に陥るため、単純なアルゴリズムとしては基本的には故障を想定していないが(詳細はこちら)、工夫を加える事で現実の問題も対処できるようになる。詳細は追ってデザインパターンとして書くので待ってて欲しい。
Fail-stop故障モデル
これは任意の瞬間にマシンが故障するモデルである。ただし、一度死んだマシンは二度と復活しない（新規マシンとしてまっさらな状態で再参加することはありうる）。マシンが死んだ事は何らかの手段を通じて有限の時間で全ての参加者が知ることができる。その死亡通知は決して誤報となることは無く、覆らない。この故障モデルは現実世界をモデル化するには少々簡単過ぎるが、多くのカジュアルな分散アルゴリズムはこの故障モデルを暗に仮定している事が多い気がする。なので中途半端な知識で分散システムに触ってプロダクションで痛い目を見るのはここが多い。かと言ってこの故障モデルが不要なものかというと全くそんなことはなく、非常に有益なアルゴリズム群のベースラインとなっている。こちらも詳細は追ってデザインパターンとして書くので待ってて欲しい。Split-brain的にシステムの過半数が死んでも、復旧しない故障モデルなのでいわゆる粗忽長屋状態（こんな言い方する人いるのか）になることはない。元々の3 Phase Commitは暗にこの故障モデルを想定している。
Crash-Recover故障モデル
これはマシンが故障したのかただ遅れているだけなのか誰にもわからない故障モデルである。明示的な形でのマシンの故障はただの一度も起きる必要はなく、無限の時間の処理遅延なのか見分けが付かない。必然的にパケットは非同期的に通信され、平気でドロップしたりする事を仮定する事になる（マシンが無限に遅延しうる状況で通信遅延の上限を設定できても意味がないからだ）。もちろんFail-stopより難しい故障モデルである。これは現実の問題を表すのに一番近く、社内の閉じたネットワーク内で素性の知れた検証済みのプログラムのみが走る事を想定するなら手頃である。
ビザンチン故障モデル
これは任意障害等と呼ばれるもので、平たく言うと悪意を持ってアルゴリズムを分析して最悪のタイミングで最悪の誤報が送られる状況を想定しなくてはならない故障モデルである。作為障害・無作為障害の両方が起き、パケットは落ちるわ化けるわ何でもありである。宇宙船の中で動くような、万に一つでもバグったら困るし宇宙線などで頻繁にビットが化けるしという状況を想定してこの障害に耐えるアルゴリズムが研究されている文脈を多く見かける。と思ったが、ファームウェアのバグのように違うレイヤーからの問題でソフトウェアが騙されているパターンなんかは結果的にその狂ったファームウェアを掴んだ参加者は信用できないからシステムから切り離さないといけない、みたいなストーリーはあるようだ。とにかく、僕のブログ記事ではあまり触れない事にする。
分散システムについて語るときは常にどの故障モデルを想定しているのか意識しなくてはならない。最終的にはCrash-recover以上の状況で動く事を目指す事になるとは思うが、それはFail-stopや故障が起きないモデルを仮定してはならない理由にはならない。故障モデルを常に意識するによってどんな故障パターンを見落としているかを効率的に見つける事ができる点が大事である。
デザインパターンというのはただ単に知見を抽象化して貼り合わせたものではなく、今後の拡張時にも大いに役立つ道標となってくれる。シングルトンオブジェクトに対して.clone()を連打するプログラムを書いてしまったら一見して何かおかしいと気づく事ができるだろう。同様にして自分がどんなデザインパターンを利用しているのかを自覚的にすることは今後の設計／実装コストを低減させるのに役に立つ。
分散システムデザインパターン
以下、分散システムデザインパターンと見せかけた僕のポエムが続くので穏やかな気持ちで眺めて欲しい。
Fail-safe First
これは僕が勝手に作った用語である。もっと言うとデザインパターンというよりデザインをしていく際の指針についての指針、メタ指針のようなものである。DRY原則とかKISS原則みたいなものである。既に提唱されているものをどう探せばいいのかわからないので作ってしまった。
何らかのシステムを作るうちに分散システムになってしまうというのは本当に良くある話だが、世の中の良くあるシステムは(特にSIerの文脈でそうなのだが)「正常系を作った後に異常系を作り込む」というのがよくある話である。この作法自体がアンチパターンである。
分散システムを設計する時は、初めに可用性や一貫性をどう保つのか(片方を捨てるという方針はもちろんある)を設計しないと、後付けでそれらを実現するのはほぼ不可能である。正常系を完成させてワンパス通してから異常系のシナリオを網羅してそれぞれの穴を塞ぐツギハギの塊をProductionに持って行っても運用しながらデバッグし続ける未来が待っている。ある程度以上大規模なシステムとなると初めの段階から耐障害を設計する事でしか健全なエンジニアリングは得られない。設計上の選択肢としてシステムの部品として初めからRiakやAuroraのように可用性・一貫性に対する回答を備えたミドルウェアを使うというのも非常に良い考えである。
メンバシップ管理パターン
JubatusはZooKeeperにメンバシップ管理を任せている。メンバシップ管理というのは自分以外のプロセスを発見するという事以上に重大な意味を持っている。ZooKeeperの場合はクライアントが専属のスレッドを立てて定期的にZooKeeper宛にKeepAliveを送り続ける事によって寿命を延命できるエフェメラルノードという物がある。KeepAliveが時間に間に合わなければエフェメラルノードが消失する。Crash-Recover故障モデル上でもZooKeeperは正しく動作するため、ZooKeeper上に保存されているエフェメラルノード上に対外的な自分のマシンの情報を保存する事でメンバシップ管理をすれば、参加者は「エフェメラルノードがある＝生きてる」とみなして通信することができる。これは仮想的にFail-Stop故障モデルを作り上げる事に役立つ。Crash-Recover故障モデルでは他のマシンが死んだのかただ通信が遅延しているのか判断する手段が無いが、エフェメラルノードが消失する程度に通信が遅延している事を持ってして故障とみなすというルールをみんなが運用してしまえば、実際にマシンが生きているかどうかは関係なくFail-Stop故障モデルの「マシンが死んだ事は何らかの手段を通じて有限の時間で全ての参加者が知ることができる。その死亡通知は決して誤報となることは無く、覆らない。」という状況を作り出すことができる。アンチ粗忽長屋である。ただ、このパターンを利用するときはZooKeeperのメンバシップ管理を全ての参加者が盲目的に信じる鉄の掟を徹底して初めて意味をなす。くれぐれもソケットがBroken Pipeしたからと勝手に通信相手候補リストから省くような真似をしてはならない。
Shared Nothing / Shared Everything
データをそれぞれの参加者が持つ場合にどうするかの選択肢。前者は複数のマシンがデータを分担して分割統治的に持って処理を行い、後者は全部のマシンが常に全データを共有する方向のデザインである。
少し考えればわかるが、Shared Nothingにしないとトータルのデータ容量は増えない。RAID1(ミラーリング)では容量が増えないのと同じである。同様に、Shared Everythingにしないと可用性は保てない。RAID0(ストライピング)ではむしろ故障に弱くなるのと同じである。
この議論に関してはまるで毒にも薬にもならないような扱いを受ける事は多いが、新たに分散システムを作る際に「Shared Somethingにしよう！」と言い出しそうになった時にそれは先人の知恵がハッキリと悪手だと忠告してくれる程度の恩恵がある。
例えば、容量の増加と耐故障性の両立をするためには、HDFSのようにデータのチャンクをShared Everything的にn多重化してそれらの群をShared Nothing的に分割統治するのが良いと示してくれる良い指針である*1。分散システムに対して「たくさんあるディスクにガッとやればザッとできるでしょ」的な大雑把な考えしか持ってない人はそこの整理法がわかっていないので分散システムの広大なデザインスペースの中で悪手の沼を延々と彷徨う事になる。例えばもしWinnyのように非構造的な分散システム上で期限内に任意のユーザ処理が終わる何かを実現しろと言われたら、アレはShared NothingともShared Everythingとも容易に分類出来ないのでその上で行う計算の定義が非常に難しい、と例えたらわかってもらえるだろうか。
僕が関わっていたJubatusはShared Everythingの指針を維持しており、高可用性と処理性能の為に分散システムという選択を採用している。Shared Nothingではないので1台のマシンに収まらないサイズの巨大学習モデルを保持する事は出来ないし今後ともそれを可能にする気はない。方針を決めておくと、今後の新機能の実装時などで様々なアーキテクチャ上の選択を迫られた時にも設計上の注意点がハッキリする。
理解しやすく、全体の設計を不必要に複雑化させない指針の一つとして大いに役立ったデザインパターンである。
Idempotentパターン
冪等と呼ばれるパターンである。世の中のほとんどの人には賛成してもらえないかも知れないが、DBのトランザクション機構のチェックポイントの手続きは仮にシングルスレッドだとしても分散・並行システムである。チェックポイントは平たく言うとログに書き込まれた内容を元に永続ストレージ上のB+木等を実際に更新していく処理である。このチェックポイントの処理は作業の途中でサーバが電気的に落とされようとデータを壊してはならず、もっと言うとチェックポイントの作業を始めるときは既に前回チェックポイントの作業中でやりかけのまま電源が抜かれたかも知れない。つまり、電源を抜かれる前の過去のチェックポイントプロセスが任意のタイミングで自分に処理を引き継いだ事になるし、作業途中で自分が電源を抜かれた場合には任意のタイミングで未来のチェックポイントプロセスが作業を再開できなくてはならない。なのでチェックポイント時には何度やっても同じになるように同じ場所に同一の値を上書きしていく事で、未来や過去の自分との衝突を解決している。このようにWAL、チェックポイント、リカバリのベストプラクティスを結合したARIESという手法はこんにちの商用データベースのベースラインとなっている。
これは何もデータベースの中でしか使えない方法ではない。前回ちらっと触れたGoogleのMilWheelはマスタが割り振ったIDで処理パイプラインを走らせ、途中で音信不通になったとマスタが判断した際に別のIDで別の処理パイプラインに同一の処理を実行させるのだが、ナイーブに実装した際に問題になるのが後から立ち上げた処理の結果を死んだと思っていた前のパイプライン処理が古いデータに基づいて上書きしかねないことだ。そこに対しては個別のIDを用いてCompare And Swap*2的に条件付きの書き込みで結果を保存することを処理の受け取り側で保証させる。マスタが別のIDを振った時点で、死んだと思われたプロセスがいつ処理結果を邪悪に上書きしようとしても、IDが合わないのでCompare And Swapにコケてくれる。アンチ粗忽長屋その２である（この喩えは適切なのか？）
冪等性の実現には、大まかには「同一の値で書き直す」か「IDなどでCompare And Swapする」の２つがあるが、容量・速度的な問題が顕在化するまではとりあえず後者を選ぶと良いだろう。
Stateless / Stateful
状態を持つかどうかを決定する指針である。
状態を持たないシステムはスケールしやすいので可能な限り状態を持たなくてはならない役割を持った(=Statefulな)マシンを減らすのは大事な指針である。Webサーバにセッション情報やアプリケーション情報を持たせずにそれぞれmemcachedやMySQLなどに集約させるのは良くある話であり、AmazonのCloud Design Patternでも登場する。これもシステムを拡張する際にここを予め整理しておくと不要な議論（どこまでをアプリケーションサーバにやらせるべきか、など）を大幅に削減できるのでデザインパターンと呼べると思う。
永続ストレージは言うまでもなくStatefulだが、例えば前述の2 Phase Commitなんかはそもそもコーディネータに状態を持たせず、あくまでStatelessに実行させ、Statefulな永続ストレージにトランザクションログを記録出来た事を以ってして永続化するという形で利用すれば、永続ストレージがCrash-Recover故障モデルに耐える限り2 Phase CommitもCrash-Recover上で動く事になる。この設計はGoogleのSpannerで採用されている。一見不可能そうな問題であってもこのように困難を分割する事で解決策が見えてくる。困ったら頭の道具箱から意図的に取り出して検討してみる価値のあるデザインパターンである。
勢いに任せて書いていたらそろそろ6000文字が近くなってきてしまったので今日はこの辺にしようと思う。まだ書きたいデザインパターンはあるのでその5ぐらいまで続けれたらいいな…。
