木の分散並列処理のためのHadoop MapReduceプログラムを公開しました

Scala Hadoop

LennMars/TreeReduction · GitHub

一般にプログラムの分散並列化は非常に困難な作業であるのはよく知られたことです。比較的容易な分散並列化手段を提供するための手法の一つとして、あるパターンに属する計算のみを対象とし、ユーザには計算の具体的な内容を決定する関数を書いてもらい、並列化に関してはライブラリが面倒を見る、というアプローチが挙げられます。MapReduceはこのアプローチに基づいて一定の成功を収めているプログラミングモデルであり、この記事で紹介するプログラムは、MapReduceが(改行で区切られたテキストといった形の)リスト構造に関する並列化手法であるのに対し、木構造に関するそれの実装であると大雑把には言えます。

木はリストよりも複雑なデータ構造で、木に対する計算をたった一つのパターンにまとめるというのは非現実的です。複数の計算パターンを、最終的に行いたい計算からそれらへのマップが容易であり、かつ効率のよい並列化が可能なように選ばなければなりません。CiteSeerX — Parallel Implementation of Tree Skeletonsはそのような(木スケルトンと呼ばれる)計算パターンの定義と共有メモリ型並列計算機向けの実装を与えた初期の研究です。分散版の初期の研究で日本語で読みやすい文献としてはhttp://takeichi.dyndns.org/attachments/4E-1.pdf(PDF)などを。本プログラムは木スケルトンのうちreduceのみを実装しています。どのような実装をしているかはREADMEに載せた参考文献を眺めれば大体感じがつかめるでしょう。

型treeと関数reduce(の逐次版)はOCamlで書くと次のようなものです。

type 'a tree = Node of 'a * 'a tree list

let rec reduce f ( + ) ( * ) eta (Node(x,tn)) = (* ( * ) is associative operator and eta is its identity *)
    match tn with
          | [] -> f x
          | _ ->
            let children = List.map (reduce f ( + ) ( * ) eta) tn in
            x + (List.fold_left ( * ) eta children)

Nodeの第一の要素はノードの値、第二の要素は子のリストです。reduceはこの再帰的なデータ構造に対するある種の「自然な」再帰関数と言えます。

実際にreduceを使って何が出来るのか見てみましょう。ここでは各ノードに整数が与えられた木について「任意の葉を選んで根からその葉までのパスに現れる値を全て足しあわせて得られる値のうち最も大きいもの」を計算することを考えます(回りくどい表現になっているのはパスを計算するわけではないことを強調するためですが、パスも計算するようにユーザプログラムを書き換えるのは容易です)。この計算をMaxPathSumと呼びましょう。MaxPathSumの結果は全てのノードの値に依存するためその並列プログラムは自明ではありませんが、reduceに属していることに気付くと、

let maxPathSum = reduce identity ( + ) max min_int

と書くことができます。これを今回のHadoopプログラム用に書きなおしたのがhttps://github.com/LennMars/TreeReduction/blob/master/main/src/main/scala/reduce/MaxPathSumReduce.scalaです。ユーザは同様にAbstractReduceを継承したクラスを書くことにより容易に目的の並列プログラムを得ることができます。これは極めて簡単な例ですが、例えば木スケルトンでXPathが実現できることは既に示されているhttp://takeichi.dyndns.org/attachments/05075.pdf(PDF)、と言えば応用範囲の広さが分かるでしょう(そこまで実装するのにはまだ結構かかりますし性能が出るかも未知数ですが)。

ちなみに実装はすべてScalaを使っています。Javaでやっていたら途中で気力が尽きていたと思います。Scalaよく出来てますね。パフォーマンスについては、データが手元にないのですが人にやってもらった実験では1GB程度の小さな入力でも100台で50倍程度の速度向上が出たそうです。計算の内容によりますが現実に扱いたくなる規模の入力であればもっとよくスケールするでしょう。Hadoopよく出来てますね。