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

Software Transactional Memo

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

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

Yahooの技術者が書いたブログ

techblog.yahoo.co.jp

が悪い方向に期待を裏切ってくれたのに対し、 @kuenishi さんがまとまった文章

kuenishi.hatenadiary.jp

を書いていたので、僕も2番煎じぐらいでまとまった文章を書く。
始めに断っておくと、分散システムというのはまだまだ事例を集めていくフェーズを抜けきっておらず、体系立った大統一理論的な分類法は確立していない。ここに書くのは、これまでの分散システム事例やこれからの分散システム事例を分類していく際にその性質をカテゴライズする一助となれば良いな、程度の文章なのであまり真に受けないで欲しい。

なぜYahooの記事が期待はずれなのか

人によって意見はあるとは思うが、個人的に感じたのは以下の3つ。

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

 

分散システムとは何なのか

学術的な共通見解があるわけではないが、僕はどこかで見かけた「部分的に故障しても動くシステム」の事を分散システムと呼ぶ分類法を推したい。

「故障を正しく検知してシステムから切り離して系統の安定性を確保する機構」というのはプログラミングモデルなど関係なしに、体系立った論理を必要とする。

単一のマシンからUSBメモリを引き抜くにしても、抜かれた事を検知して動作中の読み書きを諦めさせる挙動は充分に分散システムと呼べる。何万台もの物理的に分散した場所で複雑な並列計算を行っていても、1つでもパケットや計算機が脱落したらシステム全体が破綻するならそれは分散システムではなくてただの壊れやすいシステムだ。

エンタープライズな領域では1台のマシンの中でも複数刺さったCPUのうち一つくらい壊れてもシステムは稼働を続ける事ができたりするし 

タンデムコンピューターズ - Wikipedia

地理分散もIP通信も無くてもこういう仕組みを作るには分散システムとしての設計が必須である。

少し話がずれるが部分的に故障しても動く、と言い出すと世の中にはこのような事例もあったりする

F15片翼で帰還 - YouTube

こういう話は単純に多重化すれば解決するというほど簡単ではなく

Aviation Now/航空の現代

米国運輸安全委員会(NTSB)のレポートによると、エンジン故障に起因する事故が起こった場合、双発機の重傷者や死者は単発機の4倍になるという。

のように、素人的な直感ではエンジンは多いほうが壊れにくそうだが実際にはうまくその多重度を活かせる設計になっていないとむしろ危険であったりして面白い世界である。

僕は戦闘機に関しては素人だが、最新鋭の戦闘機F-35の設計にもいろんな形で分散システムのノウハウが詰め込まれていても不思議ではない。

Yahoo!のブログでは「分散システムの目標は、各プロセスが協調して目的を達成する事です」などと素頓狂な事が書いてあるが、目的の達成が目標であるという文章の無意味さには書いていて気づかなかったのだろうか。

人間が分散システムをわざわざ構成する理由は知っている範囲だと2つしか無い

  1. 小さなシステムでは達成不能なパフォーマンスを実現するため(性能)
  2. 個々のコンピュータで故障が発生しても動き続けて欲しいため(耐故障)

何か新しい技術が出てきても、この2つの軸の上でマッピングすればおおよその立ち位置がわかると考えている。

共有メモリ・メッセージパッシングとは何なのか

共有メモリやメッセージパッシングという分類法は複数の処理の主体(プロセスでもスレッドでもアクターでも良い)が情報を共有する際に用いる手段の事を主に並列コンピューティング(スパコンなど)の分野で用いる用語であり、Parallel Programmingとかのキーワードと一緒によく比較対象とされる。共有メモリというと、複数のプロセスなどから共通のメモリ空間が見えている物であり、そのメモリ空間上で排他や調停を適切に行いプログラムを作る必要がある物を抽象的にそう呼び、メッセージパッシングというと個々のプロセスは全く別のメモリ空間を見ているが専用の手段を用いる事で情報交換を行って協調するシステム、の事である。

一般にメッセージパッシングはメッセージの形で情報をやりとりする抽象的なレイヤーが挟まるため、ただのキャッシュコヒーレント上で目的を達成する共有メモリと比較して性能を出しにくいという欠点がある。一方、一貫性のある共有メモリとして実現できるシステムはキャッシュコヒーレントの物理的な事情でCPUの規模に制約がある。

数式で表すと、有名なアムダールの法則はNをCPU数、αを並列化できない処理の割合とした時に、性能C(N)は

C(N)=N/(1 + α(N-1))

で表される。これはαの値の高さに応じて性能の増加が頭打ちになるのが早くなりマルチコアの恩恵を得られない事を示している。

そしてこれを拡張したUniversal Scalability Law(USL)と呼ばれる物は、ここにキャッシュコヒーレントに掛かるコストを表す係数βを足しあわせて

C(N)=N/(1 + α((N-1) + βN(N-1)))

という形をしている。これはβにNが二乗で掛かっている事から分かるように、βが大きくなるほどにマルチコア化の恩恵が飽和どころかマイナス方向に働く事を示している。

分かりやすい図があったので引用するとf:id:kumagi:20160222113552p:plain

出典: How to Quantify Scalability

が直感的だと思う。マルチコア化もキャッシュコヒーレントの前ではむしろ性能の足を引っ張る事を図示している。これはNUMAを初めとする大規模システムでのキャッシュコヒーレンシの物理的限界を示唆する。この詳細に興味がある人は

www.amazon.co.jp

という本で詳細が書かれているらしい(USLの提唱者が書いた本である)。

キャッシュコヒーレントが物理的に問題になってくるNUMAシステムに於いても、既に共有メモリでなくメッセージパッシングの形にしたほうが性能が出るケースが既にあるらしく以下の論文のパフォーマンスのページだけでもチラッと見てみると良いと思う。

blogs.oracle.com

NUMAシステムが普通に市販されている現在の世界ではNUMA的な共有メモリモデルはデファクトの一つでしか無いが、一つのマザーボード複数のCPUを載せる事自体が研究フェーズだった時代では様々な方式が検討されていた。その頃の論文を引っ張り出して共有メモリとメッセージパッシングを語るのは考古学的には無意味では無いが、Yahoo!のブログの人が言う温故知新とは違うだろうと思っている。例えるなら、近代の銃撃戦を議論するというのに銃の火薬の装填法について火縄銃のように手作業で詰め込むタイプと現在のように薬莢に火薬と弾頭がパッケージングされたタイプとでどちらが良いか等と論じ始めたようなものだろうか。そういうのは温故知新とは呼ばない。

現在のNUMAシステムだって物理レイヤーの話をするならば個々のメモリはそれぞれ個別のメモリ空間を持っておりシステムがオフセットを与える事で重なりのない広大なメモリ空間をOSに見せており、その裏側ではIntelならQPI、AMDならHyperTransportといったインターコネクト技術を用いて仮想的に統一されたアドレス空間を実現している。つまりハードウェア設計者からしてみればNUMAというシステムはインターコネクト上でメッセージパッシング的に情報をやりとりさせて実現した物とも言えるわけで「NUMAは共有メモリ!」というのはあくまでソフトウェア側からの一方的な眺めでしかない。いわんやミドルウェアのレイヤーで共有メモリだのメッセージパッシングだのの分類法に振り回されていては分散システムとしての議論を見失ってしまう。

もっと言うと「仮想的に統一されたアドレス空間」という言葉だけを無邪気に横展開してよいのならDNSやらIPアドレスだって同一の名前空間複数台のマシンで分割統治して仮想的に一つの名前空間を見せている。これをアドレス空間と考えてメッセージパッシングなり共有メモリといった方法で分類を試みることの筋違いさは伝わるだろうか。

長くなったのでこの辺で一旦投稿する。(3000文字も書いてしまった…)

 

Updates.

@katsyoshi さんから指摘があった箇所を修正 s/対故障/耐故障/