Dremel

gistfile1.txt

本稿は以下のURLで公開されているGoogleのDremel論文の個人的な日本語訳である。
http://research.google.com/pubs/pub36632.html
本稿から受けたいかなる損害も責任はとりません。

Dremel: Webスケールデータセットのインタラクティブ分析

Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer,
Shiva Shivakumar, Matt Tolton, Theo Vassilakis

ABSTRACT
Dremelはリードオンリーのネストされたデータを分析するためのスケーラブルでインタラクティブなアドホッククエリシステムです。複数のレベルの実行木の組み合わせと列指向データレイアウトによって、数秒のうちに一兆行を超えるテーブルをまたぐ集約クエリを実行することが出来ます。システムはGoogleに数千のユーザを持ち、数千のCPUとペタバイトのデータにスケールしています。本ペーパーではDremelのアーキテクチャと実装、そしてMapReduceに基づくコンピューティングをいかにして補完するかを説明します。私達はネストされたレコードのためのこれ迄に無い新たな列指向ストレージを提示し、システムの数千ノードインスタンスでの実験を論じます。

1. INTRODUCTION
大規模な分析データの処理は、少なくとも低コストストレージが膨大なビジネスクリティカルデータの収集を可能にしたことによらず、Web企業と業界全体に広く普及しています。このデータをアナリストやエンジニアの手によって簡単に投入することはますます重要になっています。インタラクティブな応答時間は多くの場合データ探査、モニタリング、オンライン顧客サポート、迅速なプロトタイピング、データパイプラインのデバッグやその他の作業を異なる性質のものにします。
インタラクティブなデータ分析の大規模な実行は高い並列度を要求します。例として、現在の一般的なディスクを用いて圧縮された1テラバイトのデータを1秒以内に読み取るには1万個のディスクが必要です。同じくして、CPUに負担のかかるクエリを数秒以内に完了するには数千個のコアの上での実行が必要になる場合があります。Googleでは大規模な並列コンピューティングは一般的なマシンの共有クラスタが用いられています。[5] このクラスタは典型的に、リソースを共有し、ワークロードが幅広く変化する分散アプリケーションを多数ホストしていて、異なる性能のハードウェアをもつ機器上で実行されます。分散アプリケーション内の個々のワーカーは他のワーカーと比較して与えられたタスクを実行するのに多くの時間がかかるか、障害やクラスタ管理システムの割り込みが原因でタスクが完了しません。故に落伍者や障害に対応することは高速実行と耐障害性を実現することに不可欠です。[10]
Webや科学計算で利用されるデータは多くの場合非リレーショナルです。したがって、柔軟なデータモデルがこれからの領域では不可欠です。プログラミング言語で使われるデータ構造、分散システムで交換されるメッセージ、構造化ドキュメント等はネストされた表現に当然適しています。そんなデータをWebスケールで正規化と再結合することは通常敷居が高いものです。Googleで処理された[21]大半の構造化データや他の有名なWeb企業の報じたものがネストされたデータモデルの背後にあります。
このペーパーは一般的なマシン群上で共有された非常に大きなデータセットのインタラクティブ分析をサポートするDremelと呼ばれるシステムについて記述します。
従来のデータベースとは異なり、Dremelはネストされたデータをその場で操作する事が可能です。
その場でというのは、まさにその場所でデータにアクセスする事ができることを意味します。たとえば分散ファイルシステム(GFS[14]のような)もしくはその他のストレージレイヤ(例えばBigtable[8])です。Dremelはそんな通常はMapReduce(MR[12])ジョブの結果を必要とするデータを横断してクエリを実行できますが、実行時間はごく僅かです。DremelはMRを置き換える意図はなく、多くの場合、MRパイプラインの出力を分析したり、より巨大で迅速なコンピュータ処理の迅速なプロトタイプ向けに関連して使用されます。
Dremelは2006年から商用利用されていて、Google内に数千のユーザを持ちます。複数のDremelインスタンス群は10から1000に及ぶ広範囲で社内にデプロイされていています。システム利用例としては

・クロールされたWeb文書の分析。
・Android Marketのアプリケーションのためのインストールデータトラッキング。
・Google製品のためのクラッシュレポーティング。
・Google BooksからのOCR結果。
・スパム分析。
・Google Mapsのマップタイルのデバッグ。
・管理されたBigtableインスタンスのタブレットマイグレーション。
・Googleの分散ビルドシステムのテスト実行結果。
・数百から数千のディスクのためのディスクIO統計。
・Googleデータセンターで実行されるジョブのためのリソースモニタリング。
・Googleのコードベースで使用している記号と依存関係。

です。
DremelはWeb検索と並列DBMSのアイディアを基にしています。第一に、そのアーキテクチャは分散検索エンジンで使われる提供木の概念を拝借します[11]。まさにWeb検索のリクエストのように、クエリはプッシュダウンツリーを取得し、各ステップで書き換えられます。クエリの結果はツリーのより低レベルから受け取った応答を集約したものの集合です。第二に、Dremelはアドホッククエリを表現するための高次のSQLライクな言語を提供します。PigやHiveのようなレイヤー群とは対照的に、クエリをMapReduceジョブに変換することなく自然に実行します。最後に、そして重要なのは、Dremelは二次記憶装置からの読み込みデータを減らすことと、より低い圧縮によってCPUコストを削減することが可能な分割ストレージ表現を使います。カラムストアが採用されているのはリレーショナルデータを分析するためですが[1]、我々の知る限りではネストされたデータまで拡張されませんでした。我々が提供する列指向ストレージフォーマットはMapReduce、Swazall[20]、そしてFlumeJava[7]を含むGoogleの多くのデータ処理ツールのサポートを受けています。
本稿では以下の寄稿を行います。
・新たなネストされたデータのための列志向ストレージフォーマットを説明し、ネストされたレコードを列に分割し再構築するアルゴリズムを提示します(第4節)。
・Dremelのクエリ言語と実行の概要を説明します。どちらも、列ストライプネストされたデータに効率的に動作するように設計されており、ネストされたレコードの再構築を必要としません(第5節)。
・Web検索システムで使用される実行ツリーはデータベース処理に適用可能なことを示し、効率的に集約クエリに応答するためのその利点を説明します。
・1000-4000ノード上で動作するシステムインスタンス上で実施された1兆レコード、数テラバイトのデータセットでの実験結果を示します(第7節)。

本稿は次のように構成されます。第2節ではDremelが如何にして他のデータ管理ツールと連携してデータ分析の為に使われるかを説明します。データモデルは第3節で示されます。先にリストされた主題は第4-8節で網羅されます。関連する成果は第9節で議論されます。第10節はまとめです。