Googleの並列ログ解析向け言語「Sawzall」が公開されたので使ってみた

preferred

2010-11-09 20:52:55

最近光麺にハマっている太田です。

グーグル、分散処理のためにデザインされた言語「Sawzall」をオープンソースで公開 ? Publickeyで紹介されている、並列ログ解析向け言語「Sawzall」を試してみました。動かし方のドキュメントが少なかったので、紹介エントリを書いてみます。

Sawzallについては、5年前に論文が発表されており一部概要を知ることは出来ましたが、先日実装がオープンソースで公開されました。論文の第一著者はUNIXやPlan9の開発者で知られるRob Pike氏です。

MapReduceのOSS実装として「Hadoop」が良く知られていますが、Hadoop向けの言語としてはHiveやPig等が有名です。

  • Hive: MapReduce向けのSQLインターフェース環境 (by Facebook)
  • Pig: データストリーム指向言語 (by Yahoo!)

Sawzallとは?

Sawzallは一言で言うと、大規模なログデータから統計解析するための言語です。Sawzallの構文は、覚えやすいように意図的にC言語に似せて作られています。

しかし、C言語と異なり大量のデータを並列で処理するために1つ大きな制約がかかっています。それは、「全体のログを扱うのではなく、ログの1レコードに対する処理を記述する」という点です。

例えばRubyでログデータを処理するためには、以下のような処理が必要です。

open("log.txt").each_line { |record|
  # 各recordに対する処理を記述
}

しかし、Sawzallではeachの中の各recordに対する処理のみを記述します。外側のレコードに対するループは言語環境によって自動的に行われます。

これにより、大量のレコードを並列分散して処理出来るようになります。より具体的には、MapReduceフレームワーク上で処理実行する事が出来るようになります。

では具体的にSawzallのプログラムを記述して行きます。

例1: Hello World

まずはHello Worldの例です。

emit stdout <- "Hello World!"

プログラムの実行には、szlコマンドを使用します。

$ szl hello.szl
Hello World!

例2: ワードカウント処理

次にMapReduceプログラムではHello Worldのような存在のワードカウント処理を行なってみます。以下のようなテキストファイルを用意し、ファイル内で各単語が何回出現したのかをカウントしてみます。

$ cat input.txt
foo foo foo
hoge hoge
fuga fuga
kzk

集計プログラムは以下のようになります。

fields: array of string = sawzall(string(input), "[^ tn]+");
wc: table sum[word: string] of int;
for (i: int = 0; i < len(fields); i++) {
  s: string = fields[i];
  emit wc[s] <- 1;
}

少し複雑ですが一行ずつ解説していきます。

1行目

Sawzallでは”input”というシンボルが予約語になっており、プログラムの入力が渡されます。通常は入力ファイルの1行がバイト列で入っています。

ここではsawzall関数を用い、空白・タブ文字・改行で分割を行い、それをfieldsに代入しています。たとえば一行目は”foo foo foo”なので、1行目処理時には fields は [“foo”, “foo”, “foo”] の3要素の文字列配列になります。

注意したいのは、ここに記述しているのは1レコードに対する処理だということです。複数レコード(この場合は複数行)に対するループは、sawzall側で自動的にループを回してくれます。

2行目

2行目では、”table”を定義しています。tableとは、最終的な出力をaggregation(まとめ上げる)ための機能です。この場合は、”sum”タイプのテーブルを使用しています。他にもmaximum, minimum, top, unique等、様々なtableが用意されており良く有る集計処理のパターン化が行われています。

この行では、文字列(word)をテーブルのキーとし、それぞれのエントリは一つのint値を持っておりその値は足されるというテーブルを定義しています。”足される”の意味は後の行で分かります。

3 – 6行目

3-6行目ではループを回し各単語について処理を行っています。emit関数で先ほど定義したテーブルに対するデータの挿入を行っています。

プログラムを処理すると、以下のような順番でemitが行われます。

$ szl wc.szl input.txt
emit wc["foo"] <- 1;
emit wc["foo"] <- 1;
emit wc["foo"] <- 1;
emit wc["hoge"] <- 1;
emit wc["hoge"] <- 1;
emit wc["fuga"] <- 1;
emit wc["fuga"] <- 1;
emit wc["kzk"] <- 1;

第二引数に入力ファイルを渡すとデフォルトではemitのログが出力されます。しかし、ここで最終的に欲しい結果はテーブルwcの集計結果です。その場合は以下のように –table_output オプションを指定します。

$ szl wc.szl input.txt --table_output wc
wc[fuga] = 2
wc[kzk] = 1
wc[foo] = 3
wc[hoge] = 2

出力を見てみると、各単語が出現した回数がカウント出来ているのが分かります。またemit時に1を入れましたが、こちらが足し合わされているのが分かります。

例3: 上位検索クエリ算出処理

ワードカウントだけだと面白く無いので、手元に有る検索ログデータを使用して、一番検索されている単語を出す処理を書いてみました。検索ログのフォーマットは以下のようになっています。日時と実際の検索クエリがタブで区切られています。

$ cat qlog.txt
[2010-01-30 02:00:39] 黒子のバスケ
[2010-01-30 02:00:39] 黒子のバスケ
[2010-01-30 02:00:39] 黒子のバスケ
[2010-01-30 02:00:40] ワンピース
[2010-01-30 02:00:40] ワンピース
[2010-01-30 02:00:40] ナルト

ここから各検索語のカウントを行なうプログラムは以下のようになります。

topwords: table top(30) of word: string weight count: int;
fields: array of string = saw(string(input), skip `[`, `[0-9-]+`, skip `[ t]+`, `[0-9-:]+`, skip `[ t]+`, `([^ t])+`);
if (len(fields) >= 3) {
  s: string = fields[2];
  emit topwords <- s weight 1;
}

最初の行はtopwordsというテーブルの定義です。今回はtopタイプのテーブルを用いています。このテーブルを用いると、上位N件データを出すことが出来ます。

2行目はsaw関数と正規表現を用いて地道にレコードをフィールドに分割しています。その後topwordsテーブルに、単語を重み1でemitしていきます。emitの履歴を見ると以下のようになります。

$ szl qrank.szl qlog.txt
emit topwords <- "黒子のバスケ" weight 1;
emit topwords <- "黒子のバスケ" weight 1;
emit topwords <- "黒子のバスケ" weight 1;
emit topwords <- "ワンピース" weight 1;
emit topwords <- "ワンピース" weight 1;
emit topwords <- "ナルト" weight 1;

最終的にtopwordsを出力すると以下に様になります。検索回数が多い順に並んでいるのが分かります。

$ szl qrank.szl qlog.txt --table_output topwords
topwords[] = 黒子のバスケ, 3, 0
topwords[] = ワンピース, 2, 0
topwords[] = ナルト, 1, 0

まとめ

Sawzallは並列ログ解析の為の言語です。C++/JavaでMapReduceプログラムを書くのに比べて非常に短い行数で処理を記述出来ます。速度は論文にC++の場合の約1/10と書いてありました。

Adhocな解析を多々行う場合には非常に便利と思われますが、現状公開されているsawzall処理系ではMapReduceによる並列/分散処理を行なう事が出来ません。

が、ソースを読んでみた所Hadoopには意外と簡単に繋ぎこめそうでしたので今後に期待です。個人的にはPigよりC言語に近く書きやすいのと、日付周り・テーブル周りの機能が豊富なのが良いなと思いました。

より詳しく触ってみたい方は、ドキュメントとソース中に含まれるサンプルコードが参考になるかと思います。

C++の行列ライブラリ Eigenの紹介

岡野原 大輔

2010-11-09 15:17:40

C++で行列計算をする場合に便利なライブラリEigenを紹介したいと思います。

ベクトル・行列演算は知っているからEigenの使い方だけを教えてくれというかたは最初の章は読み飛ばしてください。

多くの統計処理がベクトル・行列演算を用いるとコンパクトに表すことが知られています。ちょっと複雑そうにみえる問題も整理してみるとベクトル・行列演算で書ける場合が多いです。(ベクトル・行列という言葉に抵抗がある方はそれぞれを単に配列、配列の配列とでも思ってもらえればいいでしょう)。ベクトルの内積は\(u^T v = u_1 v_1 + u_2 v_2 + \ldots +\)として求められ、ベクトルのノルムは自分自身のベクトルとの内積の平方根、\(|u| = \sqrt{ u^T u} \)として求められます(以降ベクトルは全て列ベクトルを指すとします)。

例えば、あるユーザーの商品の購買履歴は、\(i\)番目の商品を買っていたら\(u_i=1\)、そうでなければ\(u_i=0\)であるようなベクトル\(u\)で表せます。二人のユーザー\(u, v\)の購買履歴が似ているかどうかは共通の商品を多く買っているかどうかで判断できるので、二つのベクトルの間の角度がどれだけ小さいか、つまりコサイン距離\(cos(u, v) = u^Tv/|u||v|\)で測ることが多いです。

また機械学習の多くも行列演算で表すことができます。入力\(x \in R^m\)から出力\(y \in \{1,2,\ldots, k\}\)を推定する多クラス分類器\(f(x)\)をパーセプトロンを使って学習する場合を考えてみます。モデルパラメータとしてm行k列の重み行列\(A\)を用意します。そしてi行目の値のみ1で他が全て0であるようなベクトルをe_iとしたとき、入力\(x\)に対する推定結果は\(f(x) = \arg \max_y x^TAe_y\)と表せます。また訓練データ\((x, y)\)が与えられた時の学習則は\(A := A + x(e_y – e_{f(x)})^T\)となります。

Eigenは行列・ベクトル演算をC++から簡単に使えるようにしたライブラリでありLGPL version3またはGPL version2のdual licenseで公開されています。最初、二人で始められたプロジェクトですが現在では数十人の開発者によって進められており、年内に大幅な性能向上がされたEigen3.0の正式版がリリースされる予定になっています。

Eigenの特徴について、公式ホームページから文言を借りて説明します。

  • 多用途
    固定、可変サイズの行列、密行列、疎行列のサポート、列/行方向のデータ格納、線形方程式solver、幾何、クオータニオンのサポート、 複素数など様々な成分値のサポート
  • 高速
    Expression templatesを利用することにより、遅延評価を行い全体最適化を行うと同時に中間データ生成を極力押さえる。SSEなどベクトル演算が利用可能な場合は積極的に利用。不要な動的メモリ確保の除去、コスト評価した上でのループアンローリング、キャッシュ向けに最適化。
  • 洗練されたAPI
    擬似コードをそのままコードとして書けるよう直感的なAPI

  • 多くのコンパイラをサポート
    GCC , MSVC, ICC, MinGW, Sun Compilerなどで利用可能

Eigenの性能は有名な行列ライブラリBLASやその亜種に匹敵するほど優秀です(ベンチマーク)。また、わざわざ行列で表現する必要がないように思える、簡単なベクトルの足し算、内積などの演算でもCで直に書くより、Eigenを使ったほうがSSEなどのベクトル化をしてくれるので数倍高速になる場合が多く、利用する価値があります。

Eigenを実際に利用している分野はロボット、CG、ゲームなど多岐にわたり、Googleも機械学習やコンピュータビジョンで利用しいるそうです(公式ページより

ではさっそく使ってみましょう。Eigenはテンプレートライブラリ、つまりヘッダファイルだけからなるので、ダウンロードしてきたヘッダファイルをソースからインクルードするだけで利用することができます。以降の例はEigen 3.0-beta2を利用した場合を想定しています。

まず、Eigenを利用するにはEigen/Coreを読み込んでおけば大抵の場合OKです。様々な種類の行列が利用できますが、ここでは動的サイズでfloat成分値である行列MatrixXfを使った例を示してみます。

以下のように行列の演算は大体そのまま思った通りにかけます(サイズが合わない演算の場合はコンパイルエラーになります。)

#inlcude <Eigen/Core>
using namespace Eigen;
....
MatrixXf X(100, 200);             // 100行200列の行列
MatrixXf Y(200, 50);              // 200行50列の行列
X(11,22) = 333;                   // 11行22列目に333を代入
...色々処理
MatrixXf A = X * Y;               // X*Yの結果をZに代入

MatrixXf Z = MatrixXf::Zero(100, 50); // 零行列で初期化
...色々処理
MatrixXf B = 1.5 * X * Y + 3.0 * Z; 
// X*Yなどの中間要素をつくらず直接Bに計算結果が代入

MatrixXfを使う上でちょっと注意しなければならないのは、std:vectorとは違って成分値が0初期化されないということです。0初期化したい場合は例にあるようにMatrixXf::Zero(rows, cols)を利用して初期化します。

また、行列の様々な部分行列を取り出す方法も充実しています。行、列を指定するrow(i), col(j)はもちろん、ベクトルを対角行列に変換するasDiagonal()、成分ごとの操作を行うcwise()などもあり、ほしいと思った機能は大抵揃っています。もちろんこれらの操作を組み合わせた後の全体最適化はEigenが勝手にやってくれます。

疎行列、つまり多くの成分が0であるような行列を扱う場合にはEigen/Sparseをインクルードし、SMatrixXfを利用します。疎行列は購買履歴や自然言語情報、画像解析(Bag of visual words)など、いろいろな場面ででてきます。

SMatrixXfでは、成分値が0でない場所と、その成分値のペアを格納するため、0でない成分数に比例した分だけしかメモリを使用せず、また演算も速いという特徴があります。このため数百万行、数百万列といった大規模行列も疎行列であれば高速に扱えます。しかし密行列と違って各成分に自由にアクセスできませんので通常のMatrixと比べて機能は制限されています。また、成分値の設定の仕方が前から順番に設定する方法のみが効率的にサポートされてます(これは疎行列を実装したことある人なら大体わかるとは思いますが)

#include <Eigen/Sparse>
using namespace Eigen;
...
SMatrixXf S(100, 200);
A.reserve(200);                 // 非零成分数を大体指定.
                  // サイズが少ない場合は適当に確保してくれる
for (int i = 0; i < 100; ++i){
  A.startVec(i);                 // i行目の成分をこれから設定する宣言
  A.insertBack(i, 10) = 5;       // i行10列目の成分値を5に設定
  A.insertBack(i, i*2) = 7;      // i行i*2列目の成分に7を設定
}
A.finalize();
MatrixXf X (300, 100);
MatrixXf Y = X * A;              // 行列演算は大体普通にできる

より詳しい使い方は
チュートリアル(英語)が充実していますのでそちらを参考にしてみてください。

また、私が先日公開した大規模行列向け特異値分解ライブラリredsvdもEigenを利用していますので参考にしてみてください。redsvd src

Eigenはまだ発展途上です。最善の手法をまだ使ってない場合も多いですし(すごい勢いで次々実装されていますが)、APIも安定していないです。が、これまで紹介してきたメリットは非常に大きく、試してみる価値はあると思います。是非使ってみてください。