同名の某記事について。僕がタイトルから想像する期待を、なんだか意外な方向に裏切ってくれた記事であった。批判するだけではよくないので、同じタイトルで僕ならどういう話になるか…という話をしよう。絵のない長文だ覚悟して読め(ΦωΦ)ﾌﾌﾌ…。
分散プログラミングモデル
プログラミングモデルとはなんであろうか。
…CもJavaもMPIも登場していない1972年の論文を持ってこられてそれがオリジナルだみたいなこと言われてもえー…って感じで、Flynnの1972年の論文は並列計算やHPCの方面へ非常に大きな影響を与えていると思う。ただしそれはCPU内の話であって、時代が進むと共にたとえば牧野先生の日記「並列計算機のプログラミングモデル」で書かれているような議論につながるといえば繋がるには繋がるが、このレベルで計算を並列化する議論にしか応用できない。せいぜい、プログラミングモデルとひとくちにいっても様々な階層があって、» ヘテロジニアスとメニーコアのプログラミング・モデルで書かれているように
大規模な並列計算機資源を利用するための重大な課題は、システム・ソフトウェア・スタックによって効率的な実装を可能にしながら、ノード内のハードウェア資源の全てを利用するために、必要とされる並列性のレベルの実現を促進するような、プログラミング・モデルの提供である。ノード・レベルの並列モデルには、CPUとSMPのための、pthreads、C++11 threads、Boost thread libraryのようなスレッド・プリミティブ、NVIDIA専用のCUDAやオープン・スタンダードOpenCLのような、アクセラレーター用の低水準のもの、高水準でディレクティブに基づくOpenMPとGPUアクセラレーターのサポートから始まったOpenACC、Windows上でのC++開発環境であるMicrosoft Visual C++による並列プログラミング、他には、Cilkplus、TBB、vectorプリミティブのような選択肢がある。
といえる程度だ。スレッドやセマフォといったもう一段抽象化したプリミティブも組み合わせて様々なやりかたがあって、それらをある程度網羅していないとプログラミングモデルを論じたことにはならない。さらにいえば、こういった並列計算とかHPCといった枠組みをナイーブに分散システムの世界に持ってくることはできない。
そもそも分散システムと並列計算の世界は似たようでいて全く違う問題を解いている。分散プログラミングモデルといったときに、この「分散」はどちらの意味か確認した方がよい。一般に分散システムというとNancy LynchのMITの講義で取り上げられているような、異なる故障単位をいかに並べてコンピューターとして協調動作させるか、もっというと合意するか、故障耐性をどう保障するかという問題の定義とその解法のことを指す。計算のパフォーマンスの話にはならない *1 。なのでSIMDの話とかはほとんど関係ない。
そしてこれは、通信が非同期である、さまざまな故障が起きるといった点で並列計算の世界とは根本的に違う。並列計算の世界では基本的に「この命令は何クロックで完了する」「CPU内のどこかのモジュールで故障があったら丸ごと落ちる」「他のノードが死んたらX秒以内に検出できる」といったことを前提にできて、非同期性や故障に関してはかなり問題を単純できている（と思う、詳しいことはちょっと分からないです識者求む）。ところが分散システムの研究では、そういった非同期性と故障の双方が起こりうる世界でどうやってシステム全体の正しさを保証するかという問題に取り組む。
また、共有メモリモデルが分散システムの世界で出てくることはほとんどない。わたしが知ってる唯一のよい例はOracle RACのvotingなのだけど、それも実際はRAIDのディスクアレイ上にデータがのるので、ディスクアレイの中では基本的に同じ問題があって、それはハードウェアとかファームウェアの中で問題が解かれているわけだ（故障や非同期性の問題はある程度緩和できると思うけど）。なぜ共有メモリモデルの話がほとんどないかというと、クラウド的分散システムの世界ではShared Nothingが大前提だからだ。そもそも共有ナンたらがなくてコスパの高いPCサーバーを横に並べて構築するのが基本なわけで、非同期なメッセージパッシングを故障しうるノード間で実施するのが大前提。というわけで、共有メモリかメッセージパッシングのどちらに分類できるか、という議論には意味がない。
これがどうプログラミングモデルに影響するかって？並列計算とかふつうのプログラミング言語の世界だと、プログラムが最初から最後まで順番に進めばそれで終わりで、その中で関数型とかオブジェクト指向といった言語仕様の設計から、どうやってCache Obviousなコードを表現するかとか、並列で動くCPU間の通信をどう効率化するかといったことが問題になる。…が、そもそも通信相手が生きてるかどうかも不明なので、通信が届いているかどうか、いつになった返事がくるか、それどころか、もしかしたら先方での処理は終わってて返事が通信路で詰まっているのかもしれない。もしかしたら自分だけ仲間はずれで、他のノードはみんな仲良く協調してるかもしれない。そういうときにどういう風に動作すればよいかは自明じゃない。
よくある話だと、Master-slaveなアーキテクチャを組んでるときにMasterがStop-the-worldなGCをして固まってたらSlaveはMasterが死んだと思って自動的にMasterに昇格するんだけど、同じタイミングでMasterのGCが終わってMasterが2人いてそれぞれが矛盾する動作をして…といったときには、いわゆる並列計算の世界のアルゴリズムを持ち込んでも問題は解けない。
この辺りの文献をよくまとめている記事がReadings in distributed systemsだったり、PWLのdistributed systemsのディレクトリだったりする。
プログラミングモデルについては2通りの話がある。ここまで述べたような、分散システムを下から作るためのプログラミングモデルと、分散システムの上で計算を表現するためのプログラミングモデルだ。
前者はUCBのグループがここ10年くらい先端を走っていて、 Overlog, Datalog, Bloom, Boom といったいろんなプログラミングモデルとその実装を出している。これらの言語は非同期性、メッセージの到達遅延、Interleaving、ブロードキャストなどを上手く記述できるようになっているらしい。で、 Dedalus *2 の最後に載っているサーベイはこのあたりのプログラミングモデルをよく網羅していると思う。この流れは実用化にうまくたどり着いていないけど、成功してほしいなあ。。。なぜなら、近年の実用的な分散システムのソフトウェアはほとんどが Java, C++, Go といったパフォーマンスの高い言語または処理系で実装されているためである。運用ノウハウも沢山あるし、多少苦労しても細部（特に非同期やIOまわり）をうまく設計、実装するためには仕方がないというのが実情かな。
後者は、Strong Consistencyが保障されるような場所だったら、みんなが知ってるように特別なプログラミングモデルはあまりなくて
- MapReduceやSparkのように、APIに合わせてコードを抽象化
- SawzallやPigのようなベタ書き独自言語
- Hive, Impala などNewSQLやSQL-like言語
- CEPとかストリーム処理のCQL
で処理を記述することがほとんどだ。問題を分割統治して、分割と統治をどういうプリミティブで見せるかが腕の見せどころになる。これらの始祖は全てMapReduceと言って差し支えないくらいで、耐故障性と性能の両立を冪等性＆投機実行で力技で解決できることを示したのは本当にすごいと思う。上がわの言語とかのプログラミングモデルが、宣言的な言語仕様だったり、冪等性に気をつけるように強制するのはこのためだ。分散システムとプログラミングモデルが関係するのはここだと思う。SIMDがどうとかはほとんど関係なくて、それよりもいかに分散システムの下回り（非同期、効率性、耐故障性）を上手く抽象化したり隠蔽できるかどうかがコツだ。もうちょっというと、バッチ系のSQL-familyとリアルタイム系のCQL-familyが統合されようとしてるのが最近の流れで、 ClouderaとGoogleの協業なんかは関係者は固唾を呑んでウォッチしているはずだ。
このあたりが私の知っている分散プログラミングモデルなのだが、 はてはて…
（たぶん分散システムの）デザインパターン
うーん、こっちの話は…ひとくちに分散といっても、スケールアウトするための分散と可用性を確保するための分散でやることが多少違うんだけど…とりあえずそれ以前の話として。ちなみに↑の話は後者ね。
ハコを線で結んでポンチ絵を書くときはだいたいハコがサーバーとかノードとかプロセスで、線はそれらをつなぐ通信路だったり実際の通信の実態だったりするわけだが、その通信の実体は大きくみっつに分けられる。
- 相手が生きてるかどうか知るための死活監視を担うメンバーシップ系の通信
- 実際の分散システムがなす仕事のためのデータをやり取りする通信
- 実際の分散システムがなす仕事のためのコントロール系の命令をやり取りする通信
これら通信が描くトポロジーは、同じ場合もあるし全然違う場合もある。たとえばHBaseなんかは、メンバーシップ系通信は全部ZooKeeper経由で、データのやり取りはRegionサーバー同士でしかおきない。コントロール系の命令はMasterとRegionサーバー間でしか起きない *3 。マルバツ表作って分類するのは結構だけど、現実はもっと複雑で中身を個別に論じないと分からないと思うんだよね。Kafkaは、いわゆるメッセージキュー的な仕事をするけど、メンバーシップ系の話はZooKeeper抜きにはやっていけない。 SparkもScalaでデータフローを記述できるようになってるけど、ステージ毎のRDD配置の流れは自明じゃない（最適化の余地がある）はずだし、全体を管理するMasterとWorkerに分かれている。だいたいMesosだってMasterとWorkerに分かれるけど死活監視とかメタデータ置き場にはZooKeeperを使っているし…このあたりの複雑さをうまくパターン化するのは難しいので、無理にパターン化するとしても個別に実例つけないと説得力はあまりない。
で、データをやりとりする通信のところはパフォーマンスに大きく影響するので、いくつかパターンがある。
- Push型: データを送る方が、受け取る方のバッファに書き込む
- Pull型: データを受け取る方が、準備ができたら送る方のバッファから取り出す
それぞれ Pros/Consがあって、一般的にはたとえば前者だとレイテンシは向上するけどうまく制御しないと受け取る側のバッファがすぐ溢れるし、後者だとその逆になって受け取る方が詰まったらさあタイヘン…でさらにバルクでやり取りするかどうかでスループットとレイテンシのトレードオフがある。到達性保証の選択肢も At least once / At most once / Exactly once があって、耐障害性も考えると設計の複雑さとパフォーマンスと保証レベルとのトレードオフになって、上側のアプリも含めてどう設計するか、どれを採用するかというのがこれまた腕の見せどころになる。このあたり正解はなくて、それは古橋くんのブログ記事を見るとゥゲゲゲ奥が深いっすね…みたいな話になる。
あとデザインパターンとしては、Consistent Hashingを使って水平分散するパターンと、真面目に連続したキーを使ってシャーディングするパターンの二通りがあって、スケールアウトする系のシステムはだいたいどっちかに分類できる（両方できるヤツもいる）。いわゆるP2P系といわれるシステムは前者が多い。そういうの関係なく適当に配置するやつもいる。MesosとかHDFSとか、主キーみたいなのがないヤツがそれに相当する。
ちなみにRiakはどうなってるかというと…あれ、誰もきいてないかorz
まとめ
よくまとまっているとはお世辞にも言えないが、分散システムにおけるプログラミングモデルと、分散システムのデザインパターンの概要を解説した。プログラミングモデルは、分散システムを構築するためのものと、分散システム上でのデータ処理とかを記述するためのものに大きく分かれる。前者の知識は非常にニッチなもので、我々が専らよく触れるのはこれからは後者になるだろう。分散システムのデザインパターンは、まあハコと線と表だけで分かるもんじゃねーと思うなあ難しいし正解はないなあ、という話でした。
（追記）SOJのこちらの質問もウォッチしておきたいところ
*1: 計算量の話はあまり出ない
*2: http://db.cs.berkeley.edu/papers/datalog2011-dedalus.pdf
*3:基本設計はそうなはずで、最近なんか変わってたら教えて下さい
