BigQuery の内部実装の変遷について
BigQuery（正確にはそのクエリエンジンである Dremel）の内部実装の変遷をまとめた以下のブログポストおよび論文を読みました。
とても面白い内容で、Twitter にメモをポストしたのですが、後で参照しやすいようにブログにも同じ内容を載せておきます。
BigQuery（正確にはそのクエリエンジンである Dremel）の内部実装の変遷をまとめた論文の解説ブログ。面白かった。https://t.co/s9UaH4MjBS
— south37/Nao Minami (@south37777) December 28, 2020
解説対象の論文は "Dremel: A Decade of Interactive SQL Analysis at Web Scale"。上記ブログポストでは 3 章の Disaggregation と 5 章の Serverless Computing をピックアップして解説していたが、より網羅的に知りたい場合 & 原文を読みたい場合はこちらを読むと良い。https://t.co/XolZ7fMXFY
— south37/Nao Minami (@south37777) December 28, 2020
以下、雑なメモ。まず前提として 2010 年の Dremel についての最初の論文である "Dremel: Interactive Analysis of Web-Scale Datasets" の 6 章 Query Execution は目を通しておくと良い。Dremel が Query をどう実行するかが説明されている。https://t.co/A98EC7oBqE
— south37/Nao Minami (@south37777) 2020年12月28日
Dremel は「巨大なデータに対しての解析 query」である入力 query を「小さなデータに対しての解析 query」の集合に分解する。分解は 2010 年時点では tree の形で行われて、leaf query は storage からデータを読み取る形で実行される。中間 node は「child から集めたデータに対する query」を実行。
— south37/Nao Minami (@south37777) 2020年12月28日
中間 node の挙動は「query の書き換え」として実現される。具体的には、"SELECT A, COUNT(B) FROM T GROUP BY A" は "SELECT A, SUM(c) FROM (R1 UNION ALL ... Rn) GROUP BY A" へと書き換えられる。Ri は child node で query を実行した結果となっている。
— south37/Nao Minami (@south37777) 2020年12月28日
上記の Query Execution の前提がある中で、Dremel が 2010 年時点から進化したポイントがいくつかある。1つは、storage として local storage ではなく GFS （やその後継の Colossus）を利用するようになったこと（= Disaggregated storage）。
— south37/Nao Minami (@south37777) 2020年12月28日
元々 Dremel の server（特に leaf server）は local storage を利用していた。それが GFS を利用するようになり、Dremel の信頼性向上やメンテナンス性向上につながった（fully-managed な GFS を利用することで robustness が向上したり、local disk へのデータロードが不要になったりしたらしい）
— south37/Nao Minami (@south37777) 2020年12月28日
Dremel は join, aggregation, analytic operation のために shuffle という機構を持つが、それも進化したらしい。これは以下の blog post でも説明されてる。shuffle は元々 Map Reduce で導入され、Hadoop, Spark など主要な分散データ処理システムの動作を支える重要な機構https://t.co/ycJwG0aTo4
— south37/Nao Minami (@south37777) 2020年12月28日
2014 年に Dremel の shuffle は進化して、中間データを " distributed transient storage system" に持つようになった（= Disaggregated memory）。これにより、完全な in-memory での query 実行が実現されるようになったらしい。
— south37/Nao Minami (@south37777) 2020年12月28日
新しい shuffle infrastructure は latency 削減や shuffle 対象のデータ量の向上、20%以上の resource cost 削減に繋がった（おそらく、resource utilization が高まったのだと思われる）とのこと。ちなみに、同じ shuffle infrastructure が Google Cloud Dataflow でも使われているらしい。
— south37/Nao Minami (@south37777) 2020年12月28日
また、disaggregated memory shuffle system が利用されるようになったことで、query 実行の compute resource の割り当て（= scheduling）に柔軟性が生まれた。具体的には、shuffle 結果を checkpoint として、動的に worker を preempt 出来るようになったらしい（= Shuffle Persistence Layer）
— south37/Nao Minami (@south37777) 2020年12月28日
また、2010年時点では "fixed execution tree" として実行されていた query が、スケジューラの進化（= "centralized scheduling"）と "shuffle persistence layer" のおかげで「DAG として表現された query plan に対して、柔軟に worker を割り当てる」という形で実行されるようになった。
— south37/Nao Minami (@south37777) 2020年12月28日
まとめると、storage, memory など様々な resource が分離され、それによって compute resource の柔軟な割り当てが可能になった。performance, resource utilization の両面で劇的に進化しており、さらに改善が積み重なっている様子が感じ取られて面白い内容だった。
— south37/Nao Minami (@south37777) 2020年12月28日
上記で言及してない部分で面白い箇所はいっぱいあるので、ぜひ論文をご一読ください！https://t.co/XolZ7fMXFY
— south37/Nao Minami (@south37777) 2020年12月28日
