前回はGoogleの大量の情報をどのように保存・管理しているかという、分散ストレージについて解説した。今回は、それらのデータをどのように加工しているかといった、分散データ処理についてみていく。
１ MapReduce—分散処理のための基盤技術
MapReduceは、多数のマシンで効率的にデータ処理を行うためのしくみである。この技術により、大量のデータを分散して加工することが可能になった。
キーと値でデータ処理を表現する
MapReduceとは、MapとReduceという２つの方法を組み合わせてデータ処理を行う技術である。Mapとは、ひとまとまりのデータを受け取って新しいデータを生成していくプロセスである。Reduceは、Mapによって作られたデータをまとめて（統合）、最終的に手に入れたい結果を作り上げるプロセスである。著書では、転置インデックスを作ることが例として示されている。
MapReduceでできること
転置インデックスの作成以外にも、様々なことが可能になる。例えばカウンタ、分散grep（ファイルから特定の文字列を含んだ行を見つけるプログラム）、分散ソート（並び替え）、逆リンクリスト（リンク元のリスト）、Webページの完全なインデックス生成、ライブラリ化といったものである。
多数のワーカーによる共同作業
MapReduceでは、「マスタ」と「ワーカー」という２つのサーバが登場する。マスタはMapReduce全体の動作を管理し、ワーカーに仕事を割り振る。ワーカーはマスタの要求に従って、MapもしくはReduceのいずれかを実行するという役割を持つ。
３つのステップで処理が進む
「Map処理」「シャッフル」「Reduce処理」といった手順で処理が進む（詳細はMap Reduce 〜入門編：仕組みの理解とアルゴリズムデザイン〜）。
高速化には工夫が必要
MapReduceを高い性能で実行するために、様々な工夫がなされている。ここでは以下の５つを紹介する。
- システム構成（クラスタ構成）
- 分散パラメータ（MとR）
- ローカリティ（局所性：狭い空間でできる限りのことを行う）
- Work Queue（負荷分散）
- バックアップタスク（同処理を複数マシンで同時実行）
実行過程には波がある
MapReduceの過程には２つの波がある。それは、すべてのMapが終わるまではReduceを実行できないというものと、Mapが終わってReduceが順に始まって次のピークを迎えるというものである。
壊れたときにはやり直せばいい
MapReduceにおける故障対策は、マスタにおいては処理の時間も短いため、特に対策は不必要である（もし故障した場合再度やり直す）。ワーカーにおいては、Map処理では別のワーカーによってすべてやり直される。Reduce処理では、出力はGFSに書き込まれるためやり直す必要はない。ただし、Reduceが完了する前に障害が起きたときには、別のワーカーでやり直す必要がある。
驚きの読み込み性能
MapReduceの性能面として、ここでは「分散grep」と「分散ソート」の性能を紹介する。
分散grepの性能は、数十秒程度の初期化時間がかかるものの、ピーク時には30GB/秒（＝240Gbps）というスピードでデータ処理を行うことができる（DVD1枚分のデータ（4.7GB）を0.2秒あれば調べ終わる速さ）。
分散ソートの性能は、Mapにおいて入力データをすべて出力するため、中間ファイルやシャッフルの手間が大きくなる。著書では通常の測定結果、バックアップタスクがないときの結果、ワーカーに障害を発生させたときの結果が載せられている。
２ Sawzall—手軽に分散処理するための専用言語
Sawzallは、分散データ処理を手軽に行うために開発された新しいプログラミング言語である（ドメイン固有言語：DSL）。データの統計やログの解析と行ったよくある処理を、ごく簡単な記述によって実行することができる。
スクリプト言語のようなプログラム
SawzallはGFSとMapReduceを基盤とする言語で、それが動く仕組みはMapReduceと変わらない。Sawzallでは、Mapに相当する処理を「フィルタ」、Reduceに相当するものを「アグリゲータ」と呼ぶ。開発者はフィルタを自由に記述できる一方で、アグリゲータは既存のものしか利用できない。逆に言うと、単にフィルタを書くだけで分散処理を実行できる。
副作用をもたらすことのない言語仕様
Sawzallの文法として、データ型（int、float、string）、プロトコルバッファ（１回に読み込まれるデータであるレコードの書式を統一すること）、式と文（if、when）、フィルタの中に閉じた世界（emit）などが挙げられている。
標準で用意されるアグリゲータ
以下の５つのほか、パーセンタイル（百分位数）などを求めるquantile、重複を省いたデータの数を概算するuniqueなどが用意されている。
- collection
- sample
- sum
- maximum
- top
より実際的なプログラム例
以下の４つの例が挙げられている。
- 平均値と分散を求める
- PageRankの高いWebページを見つける
- 地域ごとのアクセス数を計測する
- 実行結果の連結
エラーは無視することも可能
エラーを避けるためには、述語defを次のように用いる。
loc: Location = locationinfo(log_record.ip);
# locが得られたときにだけ処理を続ける
if (def(loc)) {
emit queries_per_degree[int(loc.lat)][int(loc.lon)] <- 1;
}
内部的にキーが生成されている
Sawzallはどのように実現されているのかというと、アグリゲータごとに異なるキーを自動的に作り出しているようである。
スムーズにスケールする実行性能
Sawzallは、マシンの台数が増えるのに合わせて実行時間は短くなる。
最後に
本稿では、Googleがどのようにして大規模なデータ処理を行っているかについて取り上げた。MapReduceは、とりわけGFSの入力ファイルと組み合わせると高い性能を発揮する。Sawzallを使うと、分散処理はもっと手軽になることがわかった。
両方の技術も負荷分散や障害対策について考えられており、マシンの台数を増やせば増やすほど性能が向上する。これによって開発者は分散処理の問題から解放されて、データをどのように処理するかという問題解決に専念することができるのである。
次回はGoogleの運用コストについてまとめる。
 |
