論文紹介: Scalability! But at what COST?

書いた人: @nikezono

概要

データ処理基盤や分散処理基盤に置いて，“スケーラビリティ” という言葉は最も重要視され，執着すらされる概念である．
ノードの台数が増えれば増えるだけ性能が出る，というのが「スケーラビリティ」の理想であり，ノード数に対してリニアな性能曲線を描く処理基盤は素晴らしいとされる．

しかし，実際のところ 絶対的なパフォーマンス はどうだろうか? “スケーラビリティ”を追い求めるためには，並列処理化するためのオーバーヘッドというのは多かれ少なかれかかってくる．”無限にスケールするが，永遠にシングルノード/シングルスレッドの性能を越えられない” 処理基盤というのもあるかもしれない．

この論文では，データ処理基盤の性能を示す指標として新たにCOST: Configuration that Outperforms a Single Threadを定義する．また，これを用いて近年のSOSPやOSDIの論文で提案されたデータ処理基盤をベンチマークし，その絶対的な性能を評価した．

結果として，“無限のスケーラビリティの代わりに，永遠にシングルスレッドの性能を超えることができない” 処理基盤が多く存在するとわかった．

ACM Refs

Frank McSherry, Michael Isard, and Derek G. Murray. 2015.
Scalability! but at what cost?.
In Proceedings of the 15th USENIX conference on Hot Topics in Operating Systems (HOTOS'15), George Candea (Ed.).
USENIX Association, Berkeley, CA, USA, 14-14.

この論文を紹介する理由

どのようなプログラムであっても，その計算タスクの並列化できる限界を超えて並列化を行うことはできない．

また，並列化によって受けられる恩恵というのもプログラムのロジックから決定される(アムダールの法則)．

また，現実の計算機はキャッシュコヒーレンスなどの一貫性を維持するためのプロトコルを有しており，並列化というのは無償で行えるものではない．注意深く扱ったとしても，必ずオーバーヘッドは存在するものである(Universal Scalability Law)．

この観点から言って，過去のコンピュータ市場を支配してきたムーアの法則の夢の続きを見るように，かつて 「CPUの性能は上がり続けるから，新しいマシンに更改すれば性能問題は解決」 と言っていた人々が 「分散システム/メニーコアの時代だから，マシン台数/コア数を追加すれば性能問題は解決」 と現実を読み換えるのは大いに問題がある．

スケールする，ということは，そのために何かの代償を払っている，ということでもある．無限のスケーラビリティは，無限に代償を支払うということでもある．この論文ではこの観点で既存のシステムを説明しており，システム設計について大変考えさせられるものである．

背景

You can have a second computer once you’ve shown you know how to use the first one.
-Paul Barham

プログラムを効率的に並列化する手法はいくつか知られている．
行列の積を取るといった並列性が比較的わかりやすいプログラムから，複雑なSQL文をDAGとして出力して並列実行するなど，多くの実装が世に存在する．

これらのシステムが指向しているものは往々にして”Scalability”であり，それはシステムの台数やコア数を増やした際の性能向上率を指す．

一方で，面白いベンチマークがある．

これはNaiad上で同じ処理を行った結果であり，
System A は並列性が高くなるようシステムやプログラムを最適化したものである．System B は直感的に書いた，最適化していないコードである．

よく論文中で取り上げられるのは図左のグラフで， System AはSystem Bに対してスケーラビリティが高い: つまり，コア数に対する性能向上率が良い ことを示している．

一方で，その実として，絶対的な性能指標(ここではタスク終了までの時間)をプロットしたのが図右である．明らかに，System BはSystem Aより性能が高く，コア数が増大したところではじめて性能が肩を並べる ことがわかる．

このような例は極端な例ではあるが，近年のシステム論文において散見されるものである．

勿論，性能向上が無限に要求されるケースも存在する．この例では，300コア以上の場合にSystem Aの性能がSystem Bのベストケースを上回ることが想定される．そのような性能が要求された時には，System Aのもたらす価値はSystem Bでは成し得ないものとなる．重要なのは システムの性能を評価する指標が足りない ことにある．

ここで本論文では新しい性能指標を提案する． COST: Configuration that Outperforms Sigle Threadは，単一スレッドの性能を上回るために必要なセッティングを示す．これはすなわち並列化にかかるオーバヘッドであり，これが低ければ低いほど，過度の並列化をしない，効率的なシステムであることがわかる．
逆に，無限のCOSTを支払っているーすなわち，シングルスレッドの性能を永遠に上回ることのないーシステムを明らかにすることで，不要な計算能力の浪費を抑える，といった評価も可能となる．

実験

本論文ではグラフ処理を取り上げ，特にページランクの計算とラベル伝播を行うことで評価をしている．

データセットはおよそ4000万ノードと14億エッジからなるTwitterのものと，1億ノードと37億エッジからなるuk-2007-05を使用している．

このデータセットに対して，GraphLabやSparkなどの処理基盤と，グラフのリオーダリングなどの最適化を行ったシングルスレッドの実装を比較し，その性能比較を行う．

PageRankの結果を見る．各基盤のベストのセッティング（コア数）での性能を見ると，

シングルスレッドの性能は効率的であり，これを上回る性能を出すことが出来た処理基盤は少ない．

少なくとも128コアまでのセッティングにおいては，この時点でGraphLabとGraphX以外の処理基盤はシングルスレッドの実装に勝てる状況がない．つまりこれは「無限のCOST」を支払っている，ということである．

ここでPageRankについて，COSTをプロットすると以下のようになる:

縦軸は処理にかかる時間，横軸はコア数である．また，二本の平行線はそれぞれシングルスレッドの実装が出した性能である．Vertex SSDは，データをSSDに書き戻す前提でのグラフのリオーダリングを行うもの．Hilbert RAMはインメモリで全てのグラフを処理する前提でのリオーダリングを行ったものである．

ここで見ると，NaiadはCOST 16，すなわち16コアからシングルスレッドの性能を超える処理基盤であることがわかる．このグラフには描いていないが，GraphLabはコア数512においてシングルスレッド性能を上回るケースを観測しており，COSTは512コアといえる．
GraphXは最適化したシングルスレッド実装(Hilbert RAM)に対して， twitter_rvデータセットでは無限のコストを支払うという結果になった．

結論

実験を通じて，システム論文のベンチマークにおける指標としてCOSTを示した．

無限のL1キャッシュやメモリ容量，無限のCPUクロック周波数などといった概念は机上のものであり，現実には並列計算を行う際にはそのオーバヘッドが必ず存在する．つまりこれはトレードオフである．

このトレードオフをよく理解し，“Scalability” と “efficient use of resources” を区別する ことが非常に重要である．

また，今後のデータ処理基盤の研究や開発においては，これらのCOSTを鑑みることや，より抽象化された言語やクエリを定義することによってこれらのパフォーマンス問題(GC等)を隠蔽することが重要だとしている．

所感

実験に用いたハードウェアについての記述が少ない，図表の説明が少ない，などいくつか読み進めるにあたっての問題はあるものの，この論文の示唆するものは興味深い．

1.Introductionと5.Lesson Learnedの章を読むだけでも，システムについての考え方を変えてくれる良い論文である．

参考資料

が面白い．