Hadoopのセカンダリソートを避け、より高速に値をソートする方法

Scaling out H2 on Hadoop

HadoopのReduceに渡されるのはキーと値のリストだが、このとき値のリストに含まれる各アイテム(値そのもの)はソートされていない。ソートされていて欲しい場合にはセカンダリソートと呼ばれるテクニックを使うのが定石とされているが、これは実装の面でも概念的な面でもバッドノウハウ的な側面がある。Hadoopには「キーをソートする」機能は実装されている。そこで、値をキーに入れてしまい、このHadoopに備わっている「キーをソートする」機能によって、実質的に値をソートしようというわけだ。

Map/Reduceというのはキーごとにデータを分割して処理する方法なので、「キーに値が入ったら分割がおかしくなるんじゃ?」と思うのは当然である。キーに値が入っていても、分割に影響しないよう、Partitioningクラスを自分で拡張し、分割の基準となる値(本来のキー)には、値の影響が出ないようにするのだ。それでいて、ソートの際に使われる比較(つまりComparator)については、「キーに含まれる値」を使うということである。

上記を読んで少しでも意味がわかっただろうか?分からないのが当然で、つまりセカンダリソートはウ○コだということなのである(w

そこで、Java組み込み型のRDBMSであるH2を利用して、値のソートを行うというテクニックを使う。Reduceの処理において、単純にすべての値をH2データベースに格納する。そして、「select … order by …」で取り出すだけで、ソートは終わる。単純明快、コードも短く、そして驚いたことにパフォーマンスはHadoopのセカンダリソートより速くなる。唯一、H2がまるごとデータを扱うことになるため、そのぶんのディスク領域が追加で必要となる点はデメリットだ。

H2にデータをすべて格納することによって、セカンダリソートを避けることが可能になるだけでなく、ロジックは明快になり、またデータに対して複数回の問い合わせを高速に(これはインデックスが使えるためだ)行うことができるようになる。

下記リンクではHadoop上でH2を使うテクニックについて詳細にまとめたので、ぜひご一読を。

http://www.scutum.jp/information/waf_tech_blog/2013/08/waf-blog-025.html

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s