SIGMOD 2013 勉強会 Research 1: Data Analytics

Presentation on theme: "SIGMOD 2013 勉強会 Research 1: Data Analytics"— Presentation transcript:

1 SIGMOD 2013 勉強会 Research 1: Data Analytics
Shoji Nishimura NEC, Titech

2 Cumulon: Optimizaing Statistical Data Analysis in the Cloud
Botong Huang, Shivnath Babu, Jun Yang Duke University Summary 行列ベースのデータ分析をMapReduce上で実現 データベース的な自動実行プランニングで、物理的な実行やシステムコンフィグレーションも決定 AWS上で実行するときのコスト（金額）も最小化

3 行列演算の高速化 テンプレートベースの論理的な計画→物理的な計画マッピング Map-OnlyなMapReduceタスクとして行列演算を実現
既存の行列演算 on MapReduceは、Reduce演算が必要 → 中間データ生成・転送が性能ネック 本質的にBLASライブラリにおける行列演算の仕方と変わらないので、ここでは割愛

4 コストベースの最適化 実行完了時間の制約のもと、配備計画のコストが最小となるものを見つける タスクの完了時間の見積り ジョブの完了時間
AWSの費用モデル：使用台数×稼働時間×単価 タスクの完了時間の見積り 事前に典型的な例のベンチマークをとっておく 計算時間：タイルサイズの行列演算 ネットワークI/O時間：read/write性能 ジョブの完了時間 平均実行時間×（タスク数/スロット数） に正規分布のゆらぎを組み込んだもの

5 実行計画の探索戦略 クラスタサイズを決める クラスタスイッチングなしの計画を探索 クラスタスイッチングありの計画を探索
マシンタイプごと、ジョブ完了時間制約を 満たしうる最低必要なクラスタサイズを求める クラスタスイッチングなしの計画を探索 上記のサイズ制約のもと、費用が最も少なくなる構成を選ぶ クラスタスイッチングありの計画を探索 Dominateな演算ステップに絞って、クラスタスイッチしたプランを探索

6 性能評価 実験１：マシンタイプと計画と、その費用 【図表は論文より引用】 マシンタイプ、 プランによってコストは変わる
実験２：２種類の異なる演算ステップからなるジョブの実行 プランを途中で変えるとよい例 1448秒短縮 $2.03安い

7 Parallel Analytics as a Service
Petrie Wong, Zhian He, Eric Lo The Hong Kong Polytechnic University Summary マルチテナント型の超並列データベースシステム(MPPDB)を提案 すべてのテナントに対して、高い性能SLAを達成

8 解決しようとしている問題 低いownership costで、数1000規模のテナントに対して、MPPDBを提供
稼働率を高く保ちつつ、かつ、高い性能SLA遵守率を達成 実現のための鍵は、アクティブなテナント率が１０％程度という報告[20]

9 提案システムのモデル グループ０ 全テナントが利用するデータは、 全グループに複製（冗長度A） 端数は グループ１ グループ０へ
ジョブ割り当て方法 １．グループ０から空いているグループへ 　　テナントのジョブを割り当て 　　（どのグループでもサーブ可能） ２．どれも開いていなければ、 　　グループ０で並行実行 グループA-1 テナントの最大要求サーバ台数

10 このモデルの課題 どのグループでも、テナントの要求を答えられるが、テナント数が多いと、SLAを遵守できるようにするにはグループ数も多数用意する必要がある。 例：テナント数5000、平均稼働率10％なら、500に近いグループ数が必要 グループ数＝データの複製数なので、多すぎるのは困り者 →テナントをグルーピングして複製数を抑制

11 テナントのグルーピング（1/2） 【図は論文より引用】 Largest Item Vector Bin Packing Problem with Fuzzy Capacityと等価 (NP-Hard問題) P%以上の確率でアクティブテナント数がR以下 例: P=90%, R=3 ⇒ {T1,T4,T5,T6}

12 テナントのグルーピング(2/2) 【図は論文より引用】 詰めやすいテナントから詰める ６ ５ ４ ３ ２

13 性能評価 FFDというビンパッキングアルゴリズムと比較 サーバ数の削減効果は高い 一方で、ジョブを詰め込むため、実行時間は長い
【図は論文より引用】 FFDというビンパッキングアルゴリズムと比較 サーバ数の削減効果は高い 一方で、ジョブを詰め込むため、実行時間は長い

14 Shark: SQL and Rich Analytics at Scale
Reynold S Xin, Josh Rosen, Matei Zaharia, Michael J Franklin, Scott Shenker, Ion Stoica UC Berkeley Summary SQLと機械学習の実行を可能とするシステムを提案 Sparkに機能追加し、特にSQLの実行を高速化 Hadoopベースの実装に比べ、SQLおよび機械学習の実行が１００倍くらい高速化を達成

15 Mr. Oyamadaによる解説音声 をお楽しみください。