> [!abstract] 概要 > Dremelは、読み取り専用のネストデータを分析するためのスケーラブルで対話的なアドホッククエリシステムである。多段の実行木とカラム型データレイアウトを組み合わせることで、兆行規模のテーブルに対する集計クエリを数秒で実行できる。このシステムは数千のCPUと数ペタバイトのデータに対してスケールし、Google内で数千人のユーザーを抱えている。本論文ではDremelのアーキテクチャと実装を説明し、MapReduceをどのように補完するかを述べる。我々はネストされたレコードのための新しいカラム型ストレージ表現を提示し、数千ノード規模のシステムインスタンスでの実験について論じる。 ## 論文情報 - タイトル: Dremel: Interactive Analysis of Web-Scale Datasets - 著者: Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, Theo Vassilakis(全員 Google, Inc. 所属) - 媒体: Proceedings of the VLDB Endowment, Vol. 3, No. 1(第36回 International Conference on Very Large Data Bases, 2010年9月13-17日、シンガポール) - コード公開: なし(Google社内プロジェクト。名称の "Dremel" は高速動作を特徴とする電動工具ブランドから借用したものであり、本文脚注で言及される) ## 概要 Dremelは、GFS(Google File System)やBigtableのような分散ストレージ層上のデータを「in situ」(その場)で対話的に分析するシステムである。従来MapReduceの一連のジョブを要していた分析を、桁違いに短い実行時間で処理できる。ウェブ検索エンジンの多段サービス木(serving tree)というアーキテクチャと、SQLライクな高階クエリ言語、そしてネストデータに対応したカラム型ストレージという3つの要素を組み合わせている点が特徴であり、2006年から社内で本番稼働し、クロールされたウェブ文書の分析、Android Marketのインストールデータ追跡、Google製品のクラッシュレポート、Google BooksのOCR結果分析、スパム分析、Google Mapsのタイルデバッグなど多岐にわたる用途で使われている(Source: Introduction §1)。 **Figure 1: レコード指向とカラム指向のネストデータ表現** ![[_attachments/dremel-vldb2010/fig01-record-vs-columnar.png]] (Figure 1. スキーマ木(A, B, C, D, E)上でr1・r2という2レコードを、record-oriented(各レコードのフィールドが連続して並ぶ)とcolumn-oriented(同じフィールドA.B.C等の値が全レコードにわたり連続して並ぶ)の2通りで格納した様子を対比する図。ネストデータでも列指向格納により特定フィールドだけを他フィールドを読まずに取得できるという、本論文の核となる着想を示す。Source: Figure 1) ## 問題設定 - **入力**: 分散ファイルシステム(GFSなど)や他のストレージ層(Bigtableなど)に置かれた、強く型付けされたネストレコード(Protocol Buffers由来のデータモデル)。ロード処理を経ずに「in situ」でアクセスする。 - **出力**: SQLライクな言語で表現された集計クエリの結果。結果自体もネスト構造を持ちうる。 - **前提条件**: レコードは読み取り専用(read-only)。ジョイン・インデックス・更新は本論文のスコープ外とされ、将来課題として言及されるのみ(Source: §6冒頭)。 - **必要なデータ規模**: 数千CPU・数ペタバイトのデータ、兆行規模のテーブル(実験では最大105TB・1兆行超のテーブルを扱う、Figure 8)。 ## 提案手法 ### アーキテクチャ - **多段サービス木(serving tree)**: ルートサーバがクエリを受け取り、テーブルを構成するタブレット(水平パーティション)を特定してクエリを書き換え、下位レベルへルーティングする。中間サーバも同様に書き換えを繰り返し、最終的にリーフサーバがタブレットを並列スキャンする。上位に戻る過程で各レベルが部分結果を並列集約する(Figure 7、Source: §6 Tree architecture)。このツリー構造はウェブ検索エンジンのサービス木の概念を借用したものである(Source: §1)。 - **クエリディスパッチャ**: 優先度に基づくスケジューリングと負荷分散、ストラグラー(処理が遅いサーバやタブレットレプリカ)への対処を担う。処理単位は「スロット」(リーフサーバ上の実行スレッド)であり、タブレットのヒストグラムを監視して遅いタブレットを別サーバへ再割り当てする(Source: §6 Query dispatcher)。 - **走査完了率パラメータ**: スキャンすべきタブレットの最小割合(例: 98%)を指定でき、100%より低い値に設定することで実行を大幅に高速化できる(Source: §6 Query dispatcher)。 **Figure 7: システムアーキテクチャとサーバノード内の実行** ![[_attachments/dremel-vldb2010/fig07-system-architecture.png]] (Figure 7. クライアント→ルートサーバ→中間サーバ群→リーフサーバ群(ローカルストレージ持ち)→ストレージ層(GFSなど)という多段サービス木の全体構成と、各サーバノード内部のクエリ実行木(演算子が並行して値を上下にやり取りする様子)を示す図。ウェブ検索の多段サービス木の概念をDB集計クエリへ応用した本論文のアーキテクチャの核心を表す。Source: Figure 7) ### アルゴリズム/手法の詳細(ネストカラムナストレージ) - **repetition level(繰り返しレベル)**: 反復フィールドの値がスキーマ木のどのフィールドで繰り返したかを示す整数。フィールドパス上の反復フィールドの数だけレベルが取りうる範囲を持ち、レベル0は新しいレコードの開始を意味する(Source: §4.1 Repetition levels)。 - **definition level(定義レベル)**: あるフィールドパス上でオプショナル・反復フィールドのうち実際にいくつまでが定義されているかを示す整数。NULLは明示的に格納せず、定義レベルから導出される(Source: §4.1 Definition levels)。図2のスキーマと図3の列ストライプ表現(DocId・Name.Url・Links.Forward・Links.Backward・Name.Language.Code・Name.Language.Countryの各カラムがrepetition/definition levelとともに格納される様子)がこの符号化を具体的に示す。 **Figure 2: サンプルレコードとそのスキーマ** ![[_attachments/dremel-vldb2010/fig02-schema-and-sample-records.png]] (Figure 2. `message Document`スキーマ(必須のDocId、オプショナルなLinks.Forward/Backwardの反復リスト、Name.Language.Code/Countryの反復グループを含むNameの反復リスト)と、それに準拠する2つのサンプルレコードr1・r2。以降のrepetition/definition level算出やFSM組み立ての説明で一貫して参照される例。Source: Figure 2) **Figure 3: 列ストライプ表現(repetition level・definition level付き)** ![[_attachments/dremel-vldb2010/fig03-column-striped-representation.png]] (Figure 3. Figure 2のr1・r2をDocId・Name.Url・Links.Forward・Links.Backward・Name.Language.Code・Name.Language.Countryの6カラムに分解し、各値にrepetition level(r)とdefinition level(d)を付与して格納した様子。例えばName.Language.Countryの2番目の値はNULL・d=2であり、「Name.Languageは存在するがCountryは定義されていない」という構造情報をNULL値自体の定義レベルとして保持する。Source: Figure 3) - **フィールドライタの木構造による分解(DissectRecord)**: 入力スキーマと同型のフィールドライタ木を構築し、各ライタは自分自身のデータを持つときだけ更新される(親の状態を無条件に下位へ伝播しない)。子ライタはバージョン番号を使って親のレベルに遅延同期する。Appendix A(Figure 16)に疑似コードがある。 - **有限状態機械によるレコード組み立て(AssembleRecord)**: 選択されたフィールドの読み取り位置に対応する状態を持つFSMを構築し、各フィールドリーダの次のrepetition levelを見て次の遷移先を決定する。取得するフィールドの部分集合に応じてFSMを簡略化でき、必要なフィールドだけを持つより安価な組み立てが可能になる(Figure 4・Figure 5、Appendix B/C、Source: §4.3 Record Assembly)。 - **カラム型入力上でのレコード組み立てを回避したクエリ評価**: select-project-aggregateクエリはfetchLevelとselectLevelという2変数でリーダを同期させ、レコード組み立てを完全にバイパスして評価される(Figure 19、Appendix D、Source: §6 Tree architecture 末尾)。 ### 実装上の工夫 - 各カラムはブロック単位で格納され、ブロックには圧縮済みフィールド値とrepetition/definition levelが含まれる。定義レベルがフィールドパス上のオプショナル・反復フィールド数より小さければNULLと判定できるため、NULLを明示的に格納しない。常に定義済みのフィールドには定義レベルを格納せず、定義レベル0が反復レベル0を含意する場合は反復レベルも省略する(Source: §4.1 Encoding)。 - レベルはビット列としてパックされ、必要最小限のビット数(例: 最大定義レベルが3なら2ビット)のみを使う(Source: §4.1 Encoding)。 - リーフサーバはストライプのブロックを非同期に先読みし、読み取り先読みキャッシュのヒット率は典型的に95%に達する。タブレットは通常3重レプリケーションされ、あるレプリカにアクセスできない場合は別のレプリカへフォールバックする(Source: §6 Query dispatcher)。 ## 新規性 - 列指向ストレージはリレーショナルデータの分析には既に採用されていたが(Source: 参考文献[1] Abadi et al., VLDB 2009)、本論文はこれをネストデータモデルへ拡張した最初の事例であると主張する。既存のXML列指向表現であるXMillはすべてのフィールドの構造をまとめて格納する圧縮ツールであり、カラムの選択的取得向けには設計されていない点で異なる(Source: §9 Related Work)。 - Pig・HiveのようなレイヤはクエリをMRジョブへ変換して実行するのに対し、DremelはSQLライクな高階言語のクエリをMRへ変換せずネイティブに実行する(Source: §1)。 - クエリ言語はネストデータへのアクセス時に再構造化(restructuring)を要求しない設計であり、この点はXQueryやオブジェクト指向クエリ言語(ネストしたforループやコンストラクタを要する)と対照的である。Colby(SIGMOD Rec. 1989)のアイデアを基盤とするが、その実用実装は著者らの知る限り存在しなかった(Source: §9 Related Work)。 - 並列DBMSを数千ノード規模までスケールさせた公開研究や産業事例は、著者らの知る限り本論文以前には存在しない(Source: §9 Related Work)。 ## 実験設定 - **実験環境**: 2つのデータセンターで、他の多数のアプリケーションと共有される通常業務運用中のシステムインスタンス上で実施(Source: §7冒頭)。 - **データセット**: Figure 8に示す5つの実テーブル(T1〜T5)。件数は40億〜1兆超、圧縮済みサイズは13TB〜105TB、フィールド数は30〜1200、レプリケーション係数は3重(T5のみ2重)。無圧縮・非レプリケーションでは合計約1ペタバイトに相当する(Source: §7冒頭)。 - **比較対象**: 同一データに対するMapReduce実行(Sawzallプログラムによるrecord-oriented実行およびcolumnar実行)とDremelのネイティブ実行を比較。ローカルディスク単体でのカラム型 vs レコード型ストレージの読み取り性能も比較(Source: §7 Local disk、MR and Dremel)。 - **評価指標**: 実行時間(秒)、読み取りデータ量(GB/TB)、処理タブレット数の分布(ヒストグラム)、クエリ応答時間の分布(対数スケール)。 ## 実験結果 - **ローカルディスク読み取り(Figure 9)**: 300K行のT1断片(圧縮カラム形式で約375MB)を対象に、読み取るフィールド数を1〜10まで変化させた実験。カラム型ストレージは少数カラムのみ読む場合に約1桁高速。レコード組み立てとパース処理はそれぞれ実行時間を最大で倍増させるほど高コストである(Source: §7 Local disk)。 - **MRとDremelの比較(Figure 10)**: 3000ワーカーのMRジョブ2種(record-oriented・columnar)と3000ノードのDremelインスタンスでQ1(全レコードの平均単語数)を実行。DremelとMR-on-columnsは約0.5TBの圧縮カラムデータのみを読むのに対し、MR-on-recordsは87TB読む。MRはrecord-orientedからcolumnarへの変更だけで1桁(時間→分)、Dremelの使用でさらに1桁(分→秒)高速化する(Source: §7 MR and Dremel)。 - **サービス木の段数(Figure 11)**: T2上の2つのGROUP BYクエリ(Q2・Q3)を2〜4段のツリー構成(1:2900、1:100:2900、1:10:100:2900)で実行。少数のグループを返すQ2は3段でほぼ頭打ちだが、110万件のドメインを返すQ3は段数を増やすことで実行時間が半減する。2段構成ではQ3はルートサーバが数千ノードからの結果をほぼ逐次集約する必要がありグラフ外に外れる(Source: §7 Serving tree topology)。 - **タブレット単位ヒストグラム(Figure 12)**: Q2・Q3実行時、99%のタブレットがそれぞれ1秒・2秒以内に処理される(Source: §7 Per-tablet histograms)。 - **レコード内集計(Q4)**: T3(70TB)に対しa.b.c.dとa.b.p.q.rの合計を比較するクエリを、カラムストライピングにより13GBのみ読んで15秒で完了する。ネストのサポートなしにT3上でこのクエリを実行するのは非常に高コストになると述べられている(Source: §7 Within-record aggregation)。 - **スケーラビリティ(Figure 13)**: 1兆行のT4上でtop-20クエリQ5を1000〜4000ノードの4構成で実行。総CPU時間はほぼ一定(約30万秒)のまま、ユーザー体感時間はノード数増加にほぼ線形に減少する(Source: §7 Scalability)。 - **ストラグラー(Figure 14)**: 2重レプリケーションのT5上でQ6(1TB超読み取り)を実行すると、99%のタブレットは5秒以内で処理される一方、一部のタブレットが著しく長くかかり、2500ノードシステムでのクエリ応答時間を1分未満から数分へ悪化させる(Source: §7 Stragglers)。 - **月次ワークロード(Figure 15)**: あるDremelシステムの典型的な月次ワークロードでは大半のクエリが10秒未満で処理される。一部のクエリは共有クラスタ上で秒間1000億レコード近いスキャンスループットを達成する(Source: §8 Observations)。 **Figure 9: ローカルディスク読み取り時の性能内訳(T1の30万行断片)** ![[_attachments/dremel-vldb2010/fig09-perf-breakdown-local-disk.png]] (Figure 9. columnsからのread+decompress(a)・assemble records(b)・parse as objects(c)、recordsからのread+decompress(d)・parse as objects(e)の5系列を、読み取るフィールド数(横軸1〜10)に対する所要時間(縦軸、秒)として示す図。カラム型は少数フィールド読み取り時に約1桁高速だが、フィールド数増加とともにレコード型との差は縮小する。Source: Figure 9) **Figure 10: MRとDremelの実行比較(3000ノード、850億レコード)** ![[_attachments/dremel-vldb2010/fig10-mr-vs-dremel-execution.png]] (Figure 10. MR-records・MR-columns・Dremelの3構成の実行時間(対数スケール、秒)を棒グラフで比較。MR-recordsが約4000秒、MR-columnsが約600秒、Dremelが約20秒であり、record→columnar変換とMR→Dremel切り替えの双方で約1桁ずつ短縮する。Source: Figure 10) ## 考察 - MapReduceとDremelは競合ではなく補完関係にあると位置づけられる。DremelはMRパイプラインの出力を対話的に分析したり、大規模な計算を素早くプロトタイピングしたりする用途に使われ、MR自体を置き換えるものではない(Source: §1、§10)。 - カラム型データの利点はMRにも及ぶ(MR-on-columnsがMR-on-recordsを1桁上回る)ため、著者らは「カラム型ストレージはDBMSに限らずMRのようなrecord-orientedツールにも恩恵をもたらす」と観察している(Source: §8 Observations)。 - レコード組み立てとパースは高コストであるため、クエリ処理層以外のソフトウェア層もカラム指向データを直接消費できるよう最適化する必要があると著者らは指摘する(Source: §8 Observations)。 - 精度と引き換えに速度を許容できる場合、走査完了率パラメータによりクエリを早期終了してもデータの大部分は見られる、というトレードオフが強調される(Source: §8 Observations、§6 Query dispatcher)。 - ウェブスケールデータセットの大部分は高速にスキャンできるが、最後の数パーセントを厳しい時間制約内に収めることは依然として難しい、とストラグラー実験(Figure 14)を踏まえて総括される(Source: §8 Observations)。 ## 強み / 弱点・課題 - **強み**: 兆行規模・数十〜百テラバイト級のデータに対して秒単位の対話的応答を実現する。既存のカラム型ストレージの利点(選択的I/O・高圧縮率)をネストデータモデルへ損失なく拡張した。数千ノードまでほぼ線形にスケールすることを実データで示した(Figure 13)。コードベースはC++・Java・Pythonで10万行未満と比較的小さい(Source: §8末尾)。 - **弱点・課題**: 本論文は読み取り専用システムに限定して議論しており、ジョイン・インデックス・更新は将来課題として明示的にスコープ外とされる(Source: §6冒頭、§10)。クエリ言語も形式的な定義は行われず、雰囲気を示すのみである(Source: §5冒頭)。ストラグラー(処理の遅いタブレット)は依然としてテールレイテンシを悪化させる要因であり、特に低レプリケーション係数(2重)のテーブルで顕著である(Figure 14)。record-wiseストレージがcolumnarを上回るクロスオーバー点(読み取るフィールド数)はデータセットやレコード組み立ての要否に依存し、単純な閾値では説明できない(Source: §7 Local disk)。