現在のDremelの実装を解説した論文を読みました

この記事の趣旨

2020年に発表されたBigQueryの元となったGoogle内で利用されている分析向けデータベースであるDremel の実装を解説した論文を読みました。

Dremel: A Decade of Interactive SQL Analysis at Web Scale

著者について

Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, Theo Vassilakisら2010年のDremel発表論文の著者らと、 Hossein Ahmadi, Dan Delorey, Slava Min, Mosha Pasumansky, Jeff ShuteらGoogleで分析ワークロードと分散処理に関わる著者らによる論文。

概要

BigQueryの元となったGoogleのDremelの10年間を振り替えってアーキテクチャについて説明した論文。 Dremelは現代のクラウドネイティブ分析ツールで一般的になっている、計算リソースとストレージの分解、カラムナストレージ、in situデータ分析などを統合した最初のツールである。

手法

SQLの採用
それまでGoogleでは殆どのデータはBigTableなどNoSQLデータベースで管理されていたため、 SQLを用いないデータアクセスが主流であった。しかしトランザクション型ビッグデータシステムにおける、SQLの採用に共ないDremelでもSQLを採用した。
ストレージの分離
初期のDremelはシェアードナッシング方式を取っていたが、Borgへの移行にともない増大するクエリ負荷へ対応するためにストレージをGFSへと切り出した。
メモリの分離
MapReduceのシャッフルのボトルネックを回避するためにDisaggregated Memory Shuffle Systemを採用した。
In situデータ分析への対応
In situデータ分析とはDBMSへのデータロードを必要としないデータ分析のことで、Dremelでは GFSに移行するときにGoogle内で共有のストレージフォーマットを使用することでGoogle内のデータに対応した。加えてGoogle Cloud StorageやGoogle Drive、MySQL、BigTableなどからのデータ取得もフェデレーションとして対応した。
サーバレスアーキテクチャ
分散、フォールトトレラントリスタート、仮想スケジューリングユニットによりマルチテナントかつオンデマンドなリソースを提供可能とし、低価格な利用を可能とした。現在ではサーバレスアーキテクチャを進化させ、集中型スケジューリングやShuffle Persistent Layer、柔軟なDAG実行、動的クエリ実行などを実装することでより優れたサーバレスアーキテクチャを実現した。
ネストデータにおけるカラムナストレージ
Dremelのデータフォーマットはprotobufのため半構造化データをカラムナストレージに保存する必要がある。これはそれぞれのデータフィールドをそれぞれのカラムナストレージに保存することで実現している。
[[32])]
Figure 5

Figure 6

Figure 7
クエリレイテンシの最小化
これまでに説明した手法を適用することでインタラクティブな実行のレイテンシは大きくなる。それを解決するために Dremelではスタンバイサーバプール、マルチレベル実行ツリー、列指向スキーマ表現、CPUとIO負荷のバランス調整、ファイルオペレーションの再利用、保証されたキャパシティ、適合的なクエリスケーリングにより実現している。