IIJ社における分散DB技術「ddd」（2）
はじめに
IIJでは大量のデータを蓄積・処理するために、distributed database daemon（以降ddd）と呼ぶ独自の分散システムを開発しました。今回は、データを分散処理するためにdddで使用している技術であるMapReduceについて説明します。
MapReduceはもともとGoogleで考案された、大規模分散データ処理のためのフレームワークで、データをmapとreduceの二段階に分けて処理することからその名前がついています。
GoogleのMapReduceのソースコードは公開されていませんが、仕組みに関する論文が発表されています（P3参考文献[1]）。今では、その論文を元にHadoop MapReduce[2]など類似の機能を持ったオープンソースの実装がいくつか出てきています。
なお、MapReduce自体は分散処理フレームワークであり、データベースそのものではありません。しかし、GreenplumやAster Dataのように、データベースにMapReduceの機能を搭載するところも現れてきており、今後はデータベースの重要な機能の一部になっていく可能性があります。
MapReduceの概要
MapReduceは、大きく分けて、データを抽出するmapフェーズと、mapされた情報を集約するreduceフェーズの 2つのフェーズにわかれます（図1）。
MapReduceの処理単位をジョブと言いますが、1つのジョブは多数のmapタスクとreduceタスクに分解され、できるかぎり別々のノードで並列に実行されます。dddでは、第3回の説明（http://thinkit.co.jp/article/1030/2/）の通り、ストレージ部分は分散キーバリューストアとなっています。MapReduceジョブはキー単位にmapタスクに分解され、各mapタスクはキーに対応するデータを保持しているノードに対して割り当てられます。
まず、mapフェーズでは、分散ストレージのデータの中から必要な情報を抽出し、後の処理がしやすい形に変換します。
各mapタスクの結果は、一定の規則に基づいてreduceを実行するノードに振り分けられ、reduceタスクはその結果を集約します。集約した結果は分散ストレージに書き出すか、またはジョブをリクエストしたクライアントに返します。
この流れは、分散処理であることを除けばUnixでのフィルタやパイプラインによる処理に似ています。mapフェーズは、入力データからgrepやcutコマンドなどで抽出することに相当し、reduceフェーズはそれをパイプライン経由で受け取って、sortしてuniq -cすることなどに例えることができるでしょう。
実際、Hadoop MapReduceには、標準入出力を介してMapReduceのデータをやりとりするHadoop Streamingという機能があり、dddにも同等の機能を実装しています。
mapやreduceを行うプログラムは、mapperあるいはreducerと呼び、利用者が記述することになります。GoogleのMapReduceではmapperやreducerをC++で記述しますが、Google独自のSawzallという並列処理言語も使われているようです。
dddやHadoopでは、標準入出力を介してデータをやりとりできるため、mapperやreducerは任意の言語で書くことができます。mapper, reducer共に、事前に全ノードに配ってインストールしておいても良いですし、MapReduceジョブ実行時に配布することも可能です。
MapReduceの良いところは、利用者はmapperやreducerという逐次的処理を行うプログラムを書くだけで、簡単に分散処理を実現できることです。多数のノードに多数のタスクを割り当て、必要なノード間でデータを受け渡すといった面倒な部分はMapReduceのフレームワークが全部面倒をみてくれるのです。
