Recommended
Recommended
More Related Content
What's hot
What's hot (20)
Similar to Sparkのクエリ処理系と周辺の話題
Similar to Sparkのクエリ処理系と周辺の話題 (20)
More from Takeshi Yamamuro
More from Takeshi Yamamuro (20)
Sparkのクエリ処理系と周辺の話題
- 1. Copyright©2016 NTT corp. All Rights Reserved. 2016.12.22 Takeshi Yamamuro@ NTT SIC Sparkのクエリ処理理系と周辺の話題
- 2. 2Copyright©2016 NTT corp. All Rights Reserved. ⾃自⼰己紹介
- 3. 3Copyright©2016 NTT corp. All Rights Reserved. • MapReduceを⼀一般化した処理理モデルを基にした分散並 列列処理理のためのフレームワーク • DataFrame/Dataset API上に様々なワークロード向 けのライブラリを提供（Unified Engine） Sparkとは？ (クエリ最適化を担当) (クエリ実行を担当)
- 4. 4Copyright©2016 NTT corp. All Rights Reserved. • 不不変で並列列実⾏行行可能な分散コレクションで，Sparkにお ける唯⼀一のデータ操作のためのAPIを実装 Spark RDD -‐‑‒ Resilient Distributed Dataset val data = Array(1, 2, 3, 4, 5) // Scalaのローカルコレクション val dataRdd = sc.parallelize(data) // 分散コレクション（RDD）へ変換 val result = dataRdd.map(_ + 1) // RDDに対する操作を定義 .fiter( _ % 2 == 0) .reduce(_ + _)
- 5. 5Copyright©2016 NTT corp. All Rights Reserved. • DataFrameはスキーマありの不不変な分散コレクション • 実際はDataFrame=Dataset[Row] Spark DataFrame/Dataset 引用: https://databricks.com/blog/ 2016/07/14/a-tale-of-three-apache- spark-apis-rdds-dataframes-and- datasets.html
- 6. 6Copyright©2016 NTT corp. All Rights Reserved. Sparkの最近の基本⽅方針 引用: http://www.slideshare.net/databricks/structuring- spark-dataframes-datasets-and-streaming
- 7. 7Copyright©2016 NTT corp. All Rights Reserved. Sparkの最近の基本⽅方針 引用: http://www.slideshare.net/databricks/structuring- spark-dataframes-datasets-and-streaming
- 8. 8Copyright©2016 NTT corp. All Rights Reserved. Sparkの動作概要 • ユーザが記述したコードをDriver Programとして実 ⾏行行し、Sparkの最⼩小実⾏行行単位のTaskに分解し， Worker Node上に起動されたExecutorに割り当てる ことで分散並列列処理理を実現 引用: Cluster Overview, http://spark.apache.org/docs/2.0.0/cluster-overview.html
- 9. 9Copyright©2016 NTT corp. All Rights Reserved. • 今年年の7⽉月末にv2.0が正式にリリース • v2.xのリリースはAPIの安定化を中⼼心に開発４ヶ⽉月＋ QA１ヶ⽉月ペースを計画 • 今後開発が予定されている注⽬目機能はコストベース最適 化（w/Huawei）やCPU最適化など Sparkの過去のリリースと今後の⽅方向性 2012 2013 2014 2015 2016 2017 起源となる 論文（RDD）発表 Apache Incubator に登録 ApacheのTop-level プロジェクトに v1.0 v1.1 v1.2 v1.3 v1.4 v1.5 v1.6 v2.0 v2.1 v2.2 2016.12.22現在 未リリースv0.6 v0.7 v0.8 v0.9 DataFrame APIsの導入 限定的なコード生成の サポート Dataset APIsの導入 コード生成の 正式サポート
- 10. 10Copyright©2016 NTT corp. All Rights Reserved. • Catalystが関係モデルに従ったルールベースの最適化 を⾏行行い実⾏行行プラン⽊木（実⾏行行計画）を構築、⽊木の中から コード⽣生成可能な部分⽊木をjavaのコードに変換＆コン パイルしてから実⾏行行を開始 現在のSpark内部のクエリ処理理 Parser & Analyzer Optimizer Executor 結果 従来の（関係）データベースの クエリ処理 統計情報 入力データの分布を 近似したデータ SQL Join Scan Filter Scan Project 論理木 SortMergeJoin Filter Sort 実行プラン木Project カタログ データベースに関する メタデータ - DSLの構文チェック - カタログを用いた型や名前などのチェック - 経験則に基づいたルールベースの書き換え - プラン木の列挙（Joinの並び替えや実行アルゴリズム の列挙）とCPU/IOのコストを考慮した選択 - 行単位のIteratorを用いたインタープリタ方式 の処理（Volcano-style） Project IndexScan SeqScan
- 11. 11Copyright©2016 NTT corp. All Rights Reserved. • Catalystが関係モデルに従ったルールベースの最適化 を⾏行行い実⾏行行プラン⽊木（実⾏行行計画）を構築、⽊木の中から コード⽣生成可能な部分⽊木をjavaのコードに変換＆コン パイルしてから実⾏行行を開始 現在のSpark内部のクエリ処理理 Parser & Analyzer Optimizer(Catalyst) Executor(RDD) 結果 Sparkのクエリ処理 SQL/DataFrame/Dataset カタログ データベースに関する メタデータ - 経験則に基づいたルールベースの書き換え SortMergeJoin Filter Sort プラン木 Project Project IndexScan SeqScan Codegen GeneratedPlan GeneratedPlan GeneratedPlan 最終的な実行プラン木 - コード生成に対応した部分木を探索、等価な javaコードを生成、コンパイル - 行単位のIteratorを用いたインタープリタ方式 の処理（Volcano-style）
- 12. 12Copyright©2016 NTT corp. All Rights Reserved. • 実⾏行行プラン⽊木の各ノードは、その⼦子ノードが返すレコー ドを処理理するIteratorとして表現 • 故に実⾏行行プラン⽊木はIteratorの連鎖と⾒見見なせる • 問題: 性能への⾼高いオーバヘッド • 繰り返しの仮想関数nextの呼び出し • コンパイラによる最適化の余地が限りなく少ない Volcano-‐‑‒styleの処理理と問題点 実行プラン木のFilterノードの実装例 next next next
- 13. 13Copyright©2016 NTT corp. All Rights Reserved. 実⾏行行プラン⽊木のコード⽣生成の⽬目的 • 1. 仮想関数呼び出しの除去 • 2. 中間データがレジスタに残りやすい処理理 • 3. コンパイラによる最適化の享受 • Loop unrolling • データ並列列化（SIMD命令令の利利活⽤用）による⾼高速化 • 共通部分式除去など レジスタに残りやすく、データ並列化しやすそう コード生成
- 14. 14Copyright©2016 NTT corp. All Rights Reserved. • SparkはProduce-‐‑‒Consumeモデル*１に基づいて実装 されたCode Templateベースのコード⽣生成 • コード⽣生成をサポートするプラン⽊木の各ノードにproduceと consumeのIFを実装することでコード⽣生成を実現 • SortやFilterは各ノードが持つCode Templateを⽤用いて、等 価な処理理をjavaのコード（⽂文字列列）として返却 • 部分⽊木から⽣生成されたjavaのコードを軽量量な組み込み コンパイラjanino*2を⽤用いてコンパイル • BufferedRowIteratorというIteratorと同様のIFを持つ抽象ク ラスを派⽣生してコードが⽣生成されるため、コンパイルしてイン スタンス化した後はIteratorとして扱う Sparkにおけるコード⽣生成の実装 *1 Neumann先生の“Efficiently compiling efficient query plans for modern hardware”の論文内で提案（2011） *2 http://janino-compiler.github.io/janino/
- 15. 15Copyright©2016 NTT corp. All Rights Reserved. • コード⽣生成をサポートする実⾏行行プラン⽊木の各ノードに以 下を満たすproduceとconsumeを実装 • produce: ⼊入⼒力力レコード⽣生成を依頼（⼦子のproduceを呼ぶ）， 部分⽊木の葉葉であれば親のconsumeに⽣生成したレコードを渡す • consume:受け取ったレコードに各ノードの処理理を適⽤用して， 親のconsumeに渡す Produce-‐‑‒Consumeモデル
- 16. 16Copyright©2016 NTT corp. All Rights Reserved. Produce-‐‑‒Consumeモデル consume () コード生成フロー概要 consume () consume () produce() produce() produce() doCodeGen() γ π σ - γ.produce: γ.child.produce() - γ.consume: print “count += 1” - π.produce: π.child.produce() - π.consume: π.parent.consume() - σ.produce: σ.child.produce() - σ.consume: print “if (ss_item_sk == 1000) { ${σ.parent.consume()} }” - scan.produce: print “for (ss_item_sk in store_sales) { ${scan.parent.consume()} }”
- 17. 17Copyright©2016 NTT corp. All Rights Reserved. • doCodeGen()を呼ぶと以下のコードブロックを⽣生成 Produce-‐‑‒Consumeモデル
- 18. 18Copyright©2016 NTT corp. All Rights Reserved. • Sparkの実⾏行行プラン⽊木の各ノードはSparkPlanという 抽象クラスを派⽣生させて実装 • SparkPlanのexecute関数（前述のnext関数相当）の戻り値は RDD[InternalRow*1]で、RDDは各Workerノード上では Iteratorとして表現されている • コード⽣生成をサポートするノードはCodegenSupport というtrait*2をmixinする Sparkのコード⽣生成の実装概要 *1 レコードの内部表現 *2 ここではjava8のinterfaceに近い何かと思ってもらって良い trait CodegenSupport with SparkPlan { ... protected def doProduce(ctx: CodegenContext): String def doConsume(ctx: CodegenContext, input: Seq[ExprCode], row: ExprCode): String = { throw new UnsupportedOperationException } }
- 19. 19Copyright©2016 NTT corp. All Rights Reserved. • コード⽣生成可能な部分⽊木を発⾒見見すると部分⽊木の最上位に WholeStageCodegenExec（とInputAdapter）と いうノードを挿⼊入、これが部分⽊木のコード⽣生成、コンパ イル、実⾏行行を仲介 Sparkのコード⽣生成の実装概要 WholeStageCodegenExec InputAdapter コード生成する部分木 生成されたコードと実行プランの間で 入力データを仲介するノード
- 20. 20Copyright©2016 NTT corp. All Rights Reserved. • コード⽣生成可能な部分⽊木を発⾒見見すると部分⽊木の最上位に WholeStageCodegenExec（とInputAdapter）と いうノードを挿⼊入、これが部分⽊木のコード⽣生成、コンパ イル、実⾏行行を仲介 Sparkのコード⽣生成の実装概要 WholeStageCodegenExec InputAdapter コード生成する部分木 doCodeGen() produce() produce() produce() produce() consume() consume() consume() consume() class GeneratedIterator extends RowBufferedIteraotr { ... protected void processNext() throws IOException { ... } } 生成されたjavaのコード
- 21. 21Copyright©2016 NTT corp. All Rights Reserved. • Sparkの⽣生成したコードを確認 • 各エントリの先頭にʼ’*ʼ’が付いている場合はコード⽣生成による最 適化が適⽤用されていることを⽰示している 具体例例）Sparkのコード⽣生成 scala> import org.apache.spark.sql.execution.debug._ scala> val df = sql("SELECT sqrt(a) FROM test WHERE b = 1”) scala> df.explain == Physical Plan == *Project [SQRT(cast(_1#2 as double)) AS SQRT(CAST(a AS DOUBLE))#18] +- *Filter (_2#3 = 1) +- LocalTableScan [_1#2, _2#3] scala> df.debugCodegen
- 22. 22Copyright©2016 NTT corp. All Rights Reserved. Sparkが内部で生成したコード
- 23. 23Copyright©2016 NTT corp. All Rights Reserved. • ノードを跨いだコード⽣生成の最適化が困難 • 例例えばAggregateノード→Joinノードという部分⽊木があった場 合に、JoinとAggregateを合成して最適なコードを⽣生成するこ とができれば冗⻑⾧長的な計算（実体化）を除去できる • メンテナンス性が低い • ⾔言わずもがな・・・ • 処理理系に含まれる他のデータ構造を含めたコード⽣生成 （⽊木構造やハッシュ表を含めた展開）が困難 • 現状のSparkでも、集約ノード⾃自体はコード⽣生成しているが集 約処理理に使うハッシュ表の操作はコード⽣生成できていない Code Templateベースのコード⽣生成の⾮非難
- 24. 24Copyright©2016 NTT corp. All Rights Reserved. • ⾼高度度な組み込みコンパイラ基盤を活⽤用することでCode Templateベースのコード⽣生成での問題を解決 • Y. Klonatos et al., “Building Efficient Query Engines in a High-‐‑‒Level Language”, VLDB, 2014 • EPFL（スイス連邦⼯工科⼤大）とOracleの共同研究で、2014年年の VLDBのBest Paperの１つ • 実⾏行行プラン⽊木からコードを直接⽣生成するのではなく、よ り最適化できる中間表現を設計することで解決 • A. Shaikhha et al., “How to Architect a Query Compiler”, SIGMOD, 2016 • 上記のEPFLと同じ研究グループによる提案 コード⽣生成のNext Step – 研究動向 contʼ’d
- 25. 25Copyright©2016 NTT corp. All Rights Reserved. • グラフ処理理、機械学習、SQLなどの異異なる処理理を統⼀一し て表現出来る中間表現を定め、ランタイム中に複数の異異 なる中間表現を結合＆最適化して性能を改善 • S. Palkar et al., “Weld: A Common Runtime for High Performance Data Analytics”, CIDR, 2017 • AuthorのメンバにSpark RDDを提案したMatei⽒氏 コード⽣生成のNext Step – 研究動向