これまでプログラミングモデルのプの字もなかったので申し訳程度にプログラミングモデルの話をする。 分散して特定のアプリを動かしたいだけなら、例えばbitcoinをマイニングするASICクラスタに対して特定のプログラミングモデルは必要とされない。そのように、行いたいタスク抜きにプログラミングモデルを語る事はできない。
HPC（ハイパフォーマンスコンピューティング）系のワークロードは古くからMPIがデファクトとなっている。
MPIでのプログラミング
MPIというのは「Message Passing Interface」の略でSmalltalkなどの文脈で語るいわゆるメッセージパッシングとは哲学というかレイヤーが違う。こいつは 配列を引数に取る関数の形で1:1, 1:N, N:Nの通信の典型的なパターン(1:Nなら例えば `MPI_Broadcast` とか)をインタフェースとして定義しており、ユーザはMPICH2などのMPI実装の上で集合通信のマニュアルを読みながら配列のブロックを相互にぶつけあうプログラムを書く。書いている時のデバッグはマルチスレッドのデバッグのような感じであるが、明示的に通信を書かなくてはならず集合通信以外の例えば`MPI_SEND`などの使い勝手はTCPソケットと大差ない。大学生の頃に課題で書いたが、二度と書きたくないと思わせるには充分な代物であった。何故スパコンの文脈でこれがデファクトになっているかというと、何より最後の一滴までパフォーマンスを絞れる余地があるからである。超高性能の為に高いお金を出している世界だからソフトウェアのレイヤーでも性能のためなら手間を惜しまない世界である。それとMPIはあくまでInterfaceなのでその裏の実装は自由である。例えば`MP_Broadcast`は単一のノードが持ったデータを他のノードに投げつけるというインタフェースさえ守っていれば、個々のノードにTCPで一つ一つ送っても良いし、配信ツリーを作ってLog N回分の通信レイテンシでN台に配布しても良いし、おそらくIPv6マルチキャストを使っても構わない。個別のスパコン環境に合わせて集合通信の実装を最適化する余地もあるのでラックやネットワークトポロジに依存した高速化を注入しても良い。これはつまり、一度MPIの仕様に沿ったプログラムを書いてしまえば、プログラムを他のMPI実装の最新スパコンに引っ越した時もその最新スパコンのトポロジにとっての最適な集合通信の恩恵を受けれるメリットがある（世の中そううまく行くものでも無いが）。
なお、耐障害という観点においてはMPIそのものは何もサポートしない。あくまでMessage PassingのInterfaceだからだ。だから大規模なプログラムを走らせるときは短時間なら落ちない事を天に祈るか、定期的にチェックポイント的に計算経過を保存する処理を実装するというのが常套である。大規模化する程に全部のマシンが健康で居てくれる期待時間は減るのでMPI上で長時間の処理を行うのは大変になる。
ここからは主観だが、MPIは並列コンピューティング用の道具としては高性能を出せるがカジュアルな分散環境向けのプログラミングモデルとして優れているとは思えない。 莫大なコストを掛けてIPC(Instruction per Cycle)を限界まで高めたいという需要ばかりがプログラミングではない。とは言え分散プログラミングモデルの文脈でMessage Passingというキーワードを出し古典を引っ張りまわすならMPIの事は無視できないはずだが、件のYahoo!のブログ記事ではMessage Passingという文字列が分散システムの文脈で共有メモリと対照的に表現されており誤解を招きやすいなと感じたのでここに思ってた違和感を吐き出した。
ディスク帯域を束ねる話
HadoopやSparkを始めとする今どきの分散フレームワークはどちらかというとボトルネックがストレージに集中した現代の課題を解決するのが主眼という趣きがある。典型的にはここ30年でHDDの容量は10000倍以上になった*1がスピードは一番速いシーケンシャルリード速度でさえ4倍程度*2にしかなっていない。
そのようにCPUから見たHDD内データの距離が相対的に遠くなり続けているコンピュータの発展の方向に対して複数台のマシン上でディスク帯域を束ねることでソフトウェアのレイヤーから解決を図っている。HadoopやSparkはHDFSのような Shared Nothing かつ Shared Everything な分散ストレージから並列して読み出す事によって、コンピュータの歴史上ここ30年かけて4倍にしかならなかったディスクヘッドのシーク速度を束ねて台数分の性能を出すことを可能にした。スパコンのようにIPCを絞り出す事は目的ではないが（そもそもメモリ帯域などがネックになるから）CPUを正しくサチらせるには一台のマシンにディスクを沢山積んで並列読み出しする戦略を取ることになる。１台のHDDのシーケンシャルリードはおよそ100MB/sで、それによって1コアが3000秒でタスク全体を終えるとして、それを1分以内で終わらせたいなら50倍速にする必要がある。大雑把に見て50倍のHDDと50コアのCPUを用意する事になり、調達できる中でコスパが良いマシン例えば8コアCPUを1つ積んだサーバを8台で64コア、それぞれに8台のHDDをぶら下げる事で64台から並列読み出しをすればマージンを取って間に合う、というようなキャパシティプランニングをする*3。ボトルネックの場所が違うので、スパコンの世界とは考え方が違って面白い。
更にMapReduceの貢献としては、状態を全てHDFS側に持たせる事で各ワーカは状態を持たず、HDFSから読んで処理してまたHDFSに放り込むというスタイルを強制する事で耐障害性を汎用的な形で実現した。デザインパターン的には Stateful/Stateless が効いている。HDFSは追記型のデータストアなので仮に結果がおかしくても元データは壊れないので、気が済むまでやり直せばいい。
分散システムとストレージとレプリケーションの話をするなら商用HDFSクローンことMapRが良いアプローチを取っている。これに関してはそのうち書いていく。
共有メモリとハードウェアの話
ハードウェアのレイヤーで共有メモリを実現する話をするなら、1枚のCPUチップ上であってもコア数が一定数を超えたらUSL(この投稿シリーズのその１参照)の法則に従ってキャッシュコヒーレンスを保つトラフィックが足を引っ張るようになるため性能に限界が出てくる。そのため並列プログラミングの文脈において、共有メモリ型の高速化が効くコア数には限界がある。
このあたりの話は以下の記事が最高にうまくまとまっていておすすめである。ムーアの法則からスループットコンピューティングにクラウドコンピューティング、キャッシュコヒーレントを諦めたアーキテクチャ、ダークシリコン問題などが一本のストーリーに綺麗に収まっており大変エキサイティングだ。
上のサイトにも一部含まれているが、ハイパフォーマンスを目指す程にキャッシュコヒーレンシを諦める例はいくつも出てくる。
- Azul Systemsは、Javaを実行するアプライアンスVega3というシステムを販売している。54コアのキャッシュコヒーレントなチップを16つ、非常に弱いメモリモデルで接続し()、JVMのレイヤーでJMM(Java Memory Model)を守るように必要に応じて同期命令を自動で挟み込む事でユーザには一貫性がJMMレベルで守られているように見える状態を作った。このあたりの資料は本当に面白い。
- DECのAlphaというCPUは僕の知っている中で一番メモリモデルが弱い。僕の理解が正しければ、メモリバリア抜きにはロックフリー線形リストすら辿れない(カジュアルに使っている分にはユーザは気づきもしないだろうが)。でも並行プログラムを書く際に、Alphaに合わせて例えばRCUのポインタ参照時にメモリバリアを挟むC++プログラムをユーザが書くと、ポインタを辿った時点でそのポインタが指す最新データを読む事(dependency-chain)を自然に期待できるARMなどでは不必要なメモリバリアを挿入することになりペナルティがかかるので、そういったCPU環境では無視されるstd::memory_order_consumeなどというややこしいコンパイラレベルメモリバリアがC++11仕様に盛り込まれたりしている。
- Heulett Packard EnterpriseのThe Machineは光インターコネクトで接続された個々のノードはPrivateな揮発メモリ空間を持ち共有しない（不揮発メモリは別）。個々のノードに乗っているCPUは「SoC」と強調された表現をしており、個々のシステムは独立しているということになる。
- PS3にも乗っているCell B.E.は個々のSPEというコアがスクラッチパッドメモリを個々に専有しており、キャッシュコヒーレンシは保たれない。プログラマが明示的に転送する必要がある。プログラミングが大変であることで悪名高かったが結局フレームワークなどで解決されたのだろうか…。
キャッシュコヒーレンシは物理制約の問題があるので、それを諦めるとすると何らかの形でユーザのレイヤーまで影響が突き抜けてくる。Azul SystemsのようにJVM等のミドルウェアのレイヤーでそれを吸収してくれる方法はスマートだが、これはJMMというx86CPUより若干ゆるいメモリモデルをユーザに強制しているためでもある*4。
ここからは僕のポエムになるけれど、そもそも共有メモリという抽象化レイヤー自体が並列システムには適しても分散システムには向いていない。部分故障に耐えるにはどこかで複製を作らなくてはならないが、複製をあまり低いレイヤーで実現すると通信コストが支配的になってしまうからだ。例えば複数の物理マシン上の仮想マシンが同じ状態を取るように同期しながらまるで一台のマシンのように見えるように頑張らせる試みはいくつか行われてきた。実装として具体名を挙げるならRemusとかCOLOとかKemariとかである。
Remus: High Availability via Asynchronous Virtual Machine Replication | USENIX
Kemari: virtual machine synchronization for fault tolerance
透過的に複数のVMの状態を同期することで、仮に物理マシンが物理故障してもIPアドレスどころかTCPセッションすら引き継いで対外的には故障したことすら観測出来なくする技術だ。
これは何の気なしに書いたプログラムが勝手に「壊れないマシン」で動く事になるので分散システムの問題を仮想マシンが吸収してくれてハッピーに見えるが世の中そう甘くない。パフォーマンスのペナルティが厳しい事がこれらの研究の共通の課題で、いかに同期タイミングを端折るかが新規性ポイントになっている。論文のEvaluationやConclutionの章を流し読むに、世界中のサーバをそれに置き換えるべきと言える程度のペナルティでは済んでいないようだ。何よりも世界中のサーバでそれを動かしたら利用可能な計算機リソースが半分以下になる。もちろんこれが無用というつもりは無く、例えば 故障が起きない故障モデル を仮定した状態を前提にしないと動かないシステムをどれだけコストをかけてでもHA(High Available)にしたいというのなら有力な選択肢の一つとなりうるだろう*5。とはいえ、どんなアプリケーションを耐故障にしたいのかというモチベーションが既に決まっているのであれば、そのアプリケーションを表すステートマシンとメッセージを定義して、State Machine Replicationアプローチで耐故障にするほうが、物理レイヤーから全部耐故障にするより遥かに筋の良い実装が出来上がる可能性が高い。
「分散システムの抱える混沌（故障）を、共有メモリでも仮想マシンでもなく、どのレイヤーで吸収すべきか」という課題に対する今のところの僕の考えは「ミドルウェアより上」である。ユーザから見えるレイヤーで、例えばSQLとかHTTPなAPIとかで個別にエラーハンドリングするしかない。その粒度は荒ければ荒いほど、ユーザとの間の契約の間での解釈の余地が増え、分割統治・高速化の工夫を取り入れる事ができるようになる。このあたりの事はその１にも出した kuenishi さんのブログにもまとまっている。
いくつかの分散システム上での処理の記述方法を挙げているが、宣言的な記述をユーザに強制させる事でその背景で起きる故障を隠蔽するという点で共通点がある。Yahooの某記事はSparkの事を共有メモリ型だと分類していたが、それは誤った単純化であり、Sparkの偉い所はRDDで障害耐性を確保した上での再実行と永続性確保のバランスのとり方であって、共有されているかどうかは問題ではない。
引き続き、ここからMapReduceからのストリーム処理からの、僕が今注目しているDataFlow計算モデルに至るまでを少し書きたいのだけれど、もうそろそろ5000文字に達しようとしているので次回にする。レプリケーション戦略などについては更にその後。
*1:1986年頃には100MB程度のHDDさえ高価だったが今では1TBさえお小遣いで買える
*2:UltraATAが33MB/sなのに対しSASの15k回転のHDDさえもシーケンシャル130MB/sec出れば速い方
*3:もっと言うとチャンクの設定とかいろいろありそうだけど僕はここの専門ではないので深追いはしていない
*4:そして緩いメモリモデルへの理解とデバッグそのものが人間の脳にはやさしくない。JMMはその中ではだいぶマシな方だがそれでも事故が多かったとCliff Click博士はどこかで見た資料に書いていた
*5:特に、例えば政治上の理由で改変できないアプリケーションをなんとしても商用環境で走らせてその上とんでもなく高いSLAを要求されている、とか
