WIP【備忘録】DBの論文を読む : 大規模データフローエンジン

そろそろデータベースに関するちゃんとした基礎知識をつけたいという思いがあるので、Readings in Database Systems, 5th Edition を読んでいこうと思う。
URL: http://www.redbook.io/index.html

この本は、DBに関する古典的な論文から、近年の特に重要な論文まで、章ごとに短い解説とともに紹介されている。

今回は Ch5 大規模なデータフローエンジン を読む。

紹介された論文
- 解説を読んだ
論文１について
- Abstract
- 感想とメモ
論文2について
- Abstract
- 感想とメモ

紹介された論文

MapReduce: Simplified Data Processing on Large Clusters. OSDI, 2004.
- 大規模分散処理技術であるMapReduceの考え方と実装
DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language. OSDI, 2008.
- Dryadという大規模分散処理技術をプログラマが使いやすいように設計されたインターフェース(拡張言語環境)

解説を読んだ

この章の解説では、MapReduceとそれに続く大規模なデータ処理システムは「過去10年間のデータ管理における多くの開発の中で最も破壊的で最も物議を醸しているものの1つ」としたうえで、従来のDWHとの類似点や重要な違い、そしてこれらの傾向について説明している。

MapReduceの出現は少なくとも３つのインパクトを残したらしい。

スキーマの柔軟性
- 従来のDWHと違い、クリーン/ダーティかに関係なく任意に構造化されたデータを処理できる
インターフェースの柔軟性
- SQLやUDF(ユーザー定義関数)
アーキテクチャの柔軟性
- RDBMSに対するよくある批判の一つに「アーキテクチャが緊密に結合されている」というものがあった
- 対照的に、Hadoopエコシステムはボトムアップ開発の結果としてDWHを一連のモジュールとして効果的に構築できた

要約すると、今日の分散データ管理インフラストラクチャの主要なテーマは「柔軟性と不均一性」らしい。　　ここら辺、正直あまりイメージついていない。論文読んだらわかるのかな。

ちなみに、MapReduce自体は「短命」だったらしい。考え方だけが残ったということかな？
確かにインターフェースとしてのMapReduceはあまり見ない気がする。

実際、MapReduceは大規模な適用性をもつアーキテクチャではなく、２つの問題があったとのこと。

In effect Map-Reduce suffers from the following two problems:

It is inappropriate as a platform on which to build data warehouse products. There is no interface inside any commercial data warehouse product which looks like Map-Reduce, and for good reason. Hence, DBMSs do not want this sort of platform.

It is inappropriate as a platform on which to build distributed applications. Not only is the Map-Reduce interface not flexible enough for distributed applications but also a message passing system that uses the file system is way too slow to be interesting.

出典 Red Book, 5th

論文１について

MapReduceについては、ネット上のリソースが豊富にあるので、良さげなリンクをまとめるに留める。

Abstract

TODO: 今度書く

感想とメモ

MapReduceの講義ノート: Czech Technical University ... MapReduceとHadoopについてわかりやすく纏まっている。
MapReduce論文つまみ食い ... MapReduceの論文のサマリ。
MapReduceの基礎... MapReduce周辺の技術の詳解やMapReduceによる実装例が豊富。
MapReduceの講義スライド

論文2について

Abstract

DryadLINQは、大規模な分散コンピューティングのための新しいプログラミングモデルを実現するシステムおよび言語拡張セットだ。
- LINQ +
  - 強力に型付けされた.NETオブジェクトの表現力豊かなデータモデルを採用
  - データセットに対する汎用的な命令/宣言的操作を従来の高級言語内でサポート
- Dryad
  - DAGで表現された実行計画, 静的/動的最適化
DryadLINQプログラムは、データセットに対して副作用のない変換を行うLINQ式で構成された逐次プログラムであり、標準的な.NET開発ツールを使用して記述およびデバッグが可能。
DryadLINQシステムは、プログラムのデータ並列部分を自動的かつ透過的に分散実行計画に変換し、Dryadの実行環境に渡す。
この論文ではDrydLINQのコンパイラとランタイムの実装を解説した後、いくつかの実験結果を示している。
- 240台のコンピュータと960枚のディスクで構成されたクラスタで1012byteのデータをソートする汎用プログラムを319秒で実行できた
- 代表的なアプリケーションについて、ジョブに使うコンピュータの数に対して実行時間をほぼ直線的にスケーリングできた

感想とメモ

この章でDryadLINQが選ばれた理由は優れたインターフェースであるので、そこをメインでメモっていこうと思う。

DryadLINQとは

MS公式でDryadLINQは以下のように説明されている。

DryadLINQは、大規模なPCクラスターで実行される大規模なデータ並列アプリケーションを作成するためのシンプルで強力かつエレガントなプログラミング環境です。 DryadLINQの目標は、大規模なコンピューティングクラスターでの分散コンピューティングをすべてのプログラマーにとって十分にシンプルにすることです。出典: DryadLINQ

ざっくり言うと、DryadLINQは「Dryad」を「LINQ」を用いて使えるようにした環境だ。
では、「Dryad」「LINQ」とはそれぞれどんなものなのか。

Dryad ... MS社の提供する大規模分散処理技術。MapReduceに対抗するもの。
LINQ ... クエリ機能を C# 言語 (および Visual Basic や場合によってその他の .NET 言語) に直接統合する一連の技術。 NINQは統合言語クエリ(Language-Integrated Query)の略。

LINQについては以下の記事が詳しい。
はじめてのLINQ

dryadLINQのインターフェース

では、具体的にはどのようにクエリを記述できるのだろうか。
dryadlinqの論文にある記述例を引用する。

// 例 格納コーパス内の各クエリの最上位の結果を計算する

// SQL-style syntax to join two input sets: 
// scoreTriples and staticRank 
var adjustedScoreTriples = 
    from d in scoreTriples
    join r in staticRank on d.docID equals r.key 
    select new QueryScoreDocIDTriple(d, r); 
var rankedQueries = 
    from s in adjustedScoreTriples 
    group s by s.query into g 
    select TakeTopQueryResults(g); 
    
// Object-oriented syntax for the above join 
var adjustedScoreTriples = 
    scoreTriples.Join(staticRank,
    d => d.docID, r => r.key, 
    (d, r) => new QueryScoreDocIDTriple(d, r)); 
var groupedQueries = 
    adjustedScoreTriples.GroupBy(s => s.query); 
var rankedQueries = 
    groupedQueries.Select( g => TakeTopQueryResults(g));

なんかすごくsparkっぽいな。
MapReduceのプログラミングモデルも手軽に書くことができる。

public static MapReduce(// returns set of Rs 
    source, // set of Ts 
    mapper, // function from T → Ms 
    keySelector, // function from M → K 
    reducer // function from (K,Ms) → Rs 
) { 
    var mapped = source.SelectMany(mapper); 
    var groups = mapped.GroupBy(keySelector); 
    return groups.SelectMany(reducer); 
}

もう少し詳しく仕様を見ていく。
論文では以下のデータ型が紹介されていた。

IEnumerable<T> ... LINQ collectionの基本型であり、T型のオブジェクトの抽象的なデータセット。iterator interfaceでアクセスできる。
IQueryable<T> ... IEnumerable<T>の派生型。 LINQ 演算子によって構成された(評価されていない)式を表す。
DryadTable<T> ... IQueryable<T>の派生型。DryadLINQの計算の入出力。schema等のメタデータも含む場合もある。

これらの特徴は以下。

一般に、ユーザはIEnumerable<T>の具体的な型(具象型)を気にする必要がない
DryadLINQは全てのLINQ式でIQueryableオブジェクトを構成し、結果が必要になるまで評価を遅延させる。そして結果が必要になった段階でIQueryableのexpression graphを最適化し実行する。
DryadTable<T>の派生型は分散ファイルシステムやNTFS ファイルのコレクション、および SQL テーブルのセットなど、基礎となるストレージプロバイダをサポートする。

入出力の例

var input = GetTable("file://in.tbl"); 
var result = MainProgram(input, ...); 
var output = ToDryadTable(result, "file://out.tbl");

その他、DryadLINQは以下の特徴を持つ。
- LINQ式は強く型付けされているものの、糖衣構文によってユーザがそれを気にしないように工夫されている。
- 分散実行するには、DryadLINQの式の中で呼び出されるすべての関数が副作用のないものでなければならない。 - 再帰や反復を含むアルゴリズムの記述がしやすい。(これは参考リンク先にあるk-meansのアルゴリズム実装例で確認できる)

その他、DryadLINQでk-meansやDT等のアルゴリズムを実装する方法については以下のスライドに記載がある。 https://slideplayer.com/slide/6660936/

インターフェースに関してはこれでおしまいなので、残りは興味がある人だけ...

DryadLINQの仕組み

アーキテクチャとフロー

まずは、Dryadのアーキテクチャについて確認しておこう。

f:id:sereronnrot:20210831233610p:plain
出典: [1]

Dryadのジョブはjob managerによって一元的に管理される。具体的には以下のようなタスクに対して責任を負う。

データフローグラフ(DAG)の初期化
クラスタのプロセスをスケジューリング
フォールトレランスの提供(プロセスの再実行など)
jobグラフの動的な変形

計算をDAGとして表現しているのはMapReduceとの大きな違いの一つか。
MapReduceより表現力が高そう。

次に、全体のフローを確認する。

f:id:sereronnrot:20210831233633p:plain
出典: [1]

はええ。。

コンパイラに関するあれこれ

フローの(3)Compileに関していくつかメモしておく。
DryadLINQはLINQ式を受け取ると、まずはそれを実行計画のグラフ(EPG)に変換する。
ここで、EPGはノードが演算子であり、エッジはその入出力を表す。

RryadLINQは「静的最適化」と「動的最適化」の両方を行う。
まず、静的最適化の殆どはディスクとネットワークI/Oを削減することに重点を置いているらしい。最適化の例としては以下。 - パイプライン化 ... 1つのプロセスで複数の演算子を実行する。 - 冗長性の排除 ... 不要なハッシュまたは範囲分割を削除する。 - Eager Aggregation ... データセットの再パーティショニングはコストがかかるので、可能な限りダウンストリームの集約をパーティション化演算子の前に移動させる。
- I/Oの削減 ... 可能な場合、一時データをファイルに永続化する代わりに、DryadのTCPパイプとメモリ内FIFOチャネルを使用する。

次に動的最適化だが、これは実行中のジョブから情報を取得し、グラフを動的に変換することを指す。
具体的な話は論文参照。

最適化の図を最後に載せる。最初に静的最適化された後、動的最適化が行われている。

f:id:sereronnrot:20210831233706p:plain
出典: [1]