線形識別器でカーネルトリックを使う方法

preferred

2011-09-05 16:01:47

WEB+DB PRESS Vol.64に「作って学ぶ日本語入力」という特集記事を書かせていただきました。徳永です。全国の書店で発売中ですので、ぜひみなさんお買い求めください。(宣伝)

さて今回は、線形識別器でカーネルを使うのと同じ効果を得るための手法を紹介したいと思います。

続きを読む »

最近傍探索2011

岡野原 大輔

2011-08-05 19:25:57

こんにちは、二台目のmbaを買うのをためらっている岡野原です。

アイテム集合に対し、与えられたアイテムと似ているアイテムを求める、という近傍探索問題は古典的な問題でありながら、現在でも多くの改善がされています。特に言語情報、画像情報、行動履歴情報、生物情報、購買情報などありとあらゆるデータが高次元中の点として表現されるようになってきており、こうしたデータの最近傍探索は広い分野で応用範囲がある技術になっています。

アイテムが低次元(例えば2, 3次元)の場合はkd木や最近だとwavelet木を使う方法がありますが、今回扱うケースは各アイテムが高次元(数百万次元)中の点であったり、アイテム間の距離のみが定義されている場合(カーネル関数など)です。アイテム数は数万から数億ぐらいを想定しています。

最近傍探索問題はいくつかありますが、例えばk近傍グラフ構築問題では、

「アイテム集合X = x1, x2, …, xnと、それらのアイテム間の距離が与えられた時、全てのアイテムxにそれぞれについて、それらから最も近いk個のアイテム(k近傍リスト)、kNN(x)を求めよ」

となり、近傍列挙問題では

「アイテム集合X = x1, x2, …, xnと、それらのアイテム間の距離が与えられた時、距離がt以下のアイテムペアを全て列挙せよ」

といった形になります。

この問題に対する自明で最も単純な方法は、全てのアイテムについて、他のアイテム全ての距離を計算し、最小k個を求める方法です。この場合、距離計算はn^2/2回行う必要があり、アイテム数が数百〜数千ぐらいまでしかスケールしません。

この問題に対しては、アイテム一つずつ近傍探索するのではなく、全てのアイテムの近傍探索をまとめて解くことで、高速に求めることが出来る方法がいくつか存在します。今回はそのなかでも実用的で新しいアイディアに基づいているものをいくつか紹介します。

Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures

PDF
W. Dong, M. Charikar, and K. Li, WWW 2011

なぜ誰も思いつかなかったのか(ルーターのMST決定とかで見たような)というほど単純なアイディアで近傍探索を高速に求めるアルゴリズムです。
このアルゴリズムの基本アイディアは、「近傍の近傍は近傍になりやすい」ということです。それぞれのアイテムが自分の現状の近傍リストを持ち、近傍の近傍に今のリストに入っているアイテムより近いものがないかを調べて、近傍リストを逐次的に改善していきます。

各アイテムxについて、そのk個の近傍アイテムをB[x]で表すことにします。逆に、アイテムxを近傍だとしているアイテムの集合をR[x]とします。B[x]は常にk個なのに対し、R[x]はk個とは限らないことに注意してください。また、B[x]とR[x]の和集合をU[x]とします。

はじめに、各アイテムxについて、B[x]をX中のランダムなk個で適当に決めます。次に、各点xについて、その近傍の近傍、つまり、U[x]の中から一つアイテムyを選び、さらにU[y]の中の各アイテムzについて、それが自分の今持っている近傍リスト中のアイテムより近いかどうかをチェックし、近ければ近傍リストを更新します。これを収束するまで繰り返します。

この方法は近傍リストを逐次的、Greedyに更新していくので、kNNの最急降下法という説明が論文ではなされています。

基本的なアイディアはここまでなのですが、改良ポイントが四点あります。

一つ目がlocal joinです。先程のような更新方法をとる場合、近傍の近傍でループを回すとメモリアクセスに局所性がありません。例えば、a – b で aとbが近傍ということを表すと、先ほどは a – b – cの関係にある時、aを固定してループを回して、cがaの近傍に入るかというのをチェックしています。local joinでは bを固定して、bの近傍二つa, cをとってきて、それらがそれぞれ自分の近傍リストを更新できるかどうかをチェックするようにします。こうすることによって、計算量自体はかわりませんが、メモリアクセスの局所性が増し(各アイテムの近傍リストを二重ループするだけ)、高速化することができます。

二つ目がincremental searchです。近傍リストは後半になってくると収束して殆ど更新されなくなってきます。そこで、近傍リストに新しく入ったかどうかを各アイテム毎にフラグとして持っておき、local joinで調べるときには少なくとも片方が新しく入った場合だけチェックをするようにします。

三つ目がsamplingです。local joinの時に実際に全部をチェックするのではなく、適当にサンプルしたものだけをチェックするようにします。次回のサンプリングでは前回サンプリングされなかったものを選ぶようになります。近いのであれば、どれかの近傍には入っているので、全部調べるのは冗長という考えにもとづいています。

四つ目はEarly Terminationです。収束してきたら、近傍リストの改善は少なくなってくるので、適当なところでやめてしまいます。

実験では画像データや言語データなどいくつか試していますが大体傾向は同じです。iteration回数はどの場合でも4,〜5回程度で収束し、その時の再現率が9割前後(本当の近傍のうち9割程度見つかる)、データ数nに対する計算量は 多くのデータでO(n^1.14)です。
このアルゴリズムでは逐次的に近傍リストを更新していくのでアイテムの追加や削除、更新についても効率的にサポートできそうです。

結果で気になるのはデータの種類や量によらず計算量のオーダーが常に同じ(小数点第2位まであう)だということです。近傍グラフの性質がスモールネットワークのように一定以上の量になると法則が現れてくるのでしょうか。

今後の改善の余地があるとすれば、理論的な解析をするのと、更新にランダム性をいれたりMCMCのような枠組みをいれることで局所最適ではなく大域最適な結果が見つかるようにできるかということです。

Scaling Up All Pairs Similarity Search

pdf
R. J. Bayardo, Y. Ma, and R. Srikant, WWW 2007

次に紹介する方法は各アイテムが疎で高次元な特徴ベクトルの場合に向けての方法です。先程の方法では結果は近似でしたが、今回の方法は正確な結果を返します。
話を簡単にするために距離がcos類似度(高ければ高いほどよい)の場合であり、各特徴ベクトルのL2ノルムが1に正規化されているとします。また、cos類似度が閾値tを超えたものだけを見つけたいとします。
#そうでない場合については論文を参照してください。

このような特徴ベクトルが疎で、内積ベースで距離を計算する場合にまず考えられることは、情報検索のように各特徴毎に、それが発火したデータと、特徴値を保存した転置ファイルを構築し、それを利用して内積を計算する方法です。しかし、この転置ファイルを利用する方法には問題が三つあります。
一つ目は、そのまま計算してしまうと(x, y)と(y, x)の二つの類似度の計算をしてしまうという問題、二つ目は全部のデータを読み込んで、それに対して転置ファイルを構築した後でしか結果を出せないという問題、三つ目は転置ファイル自身が元のデータと同じサイズだけ必要で作業領域量が大きいことです。これらを解決していきます。

まず最初の改善では、初めに転置ファイルを作るのではなく、データを順番に調べていって、その時に一緒に転置ファイルも作っていく方法です。データをx1, x2, …, xk-1までみていった時、ここまでのデータに対する転置ファイルを構築します。そして、xkを調べるときには(x1, xk), (x2, xk), …, (xk-1, xk)の類似度が閾値より大きかどうかをチェックします。これにより、対称部分の計算の重複がなくなりますし、また、データ全体を読み込まなくても結果を返すことができます。

二つ目の改善では、転置ファイルを全て作らずに関係しそうなところだけを作る方法です。特徴毎に発火数に大きな偏りがあることをうまく利用し、転置ファイルには珍しい特徴だけが含まれるようにします。アイテムxについての転置ファイルを構築する際には、xの発火している特徴を、転置ファイル中でのエントリ数が多いものから順番に調べるようにします。次に値bに現在みてきた特徴と、他のアイテム全てのうち特徴値が一番大きいものを計算したときの内積を保存します。そして、閾値がtの時 b < tの間は転置ファイルに登録せず、元のデータに登録しておき、b >= t になった時から転置ファイルに登録するようにします。

これらの改良により、転置ファイルは、実際に閾値tを超える可能性がある場合のみ転置ファイルに入るようにあります。そして、転置ファイルにひっかかって類似度を計算するときには、転置ファイルによって計算された分にくわえ、残されたアイテムからの類似度計算部分を調べます。転置ファイルのエントリ数が大きいものから小さいものに順に調べているので、大部分の転置ファイルをつくらずにすむようになり、使用容量の大幅な削減と計算時間の削減が達成できます。

三つ目の改善では、データを、それが持つ特徴値の最大値が大きい順番に並び替えます。そして、転置ファイルを作る時と、それを利用して閾値がtを超えるものを調べる両方の時に枝刈りを行います。これにより、転置ファイルが作る量と、実際に候補が出る量の両方が大幅に減らすことができます。

またこの他にも、特徴ベクトルがbit列である場合や、距離がcos類似度ではない場合向けの最適化も紹介しています。

これらの最適化を適用することで何も最適化を施さない場合と比べて数倍から数十倍、他の手法(例えばLSHを使う場合)などと比べても数倍の高速化が達成できたと報告しています。

その他

この他にも、注目すべきトピックがいくつかありますので要点だけ述べておきます。

“Hashing with Graphs

W. Liu et. al, ICML 2011 pdf

アイテムの集合からアンカーポイントと呼ばれる少数の点を選んだ後に、各アイテムをそれから一番近いk個のアンカーポイントが張るsimplex上で表します。そして、アイテムaとアイテムbの間の近さを、aから関係する各アンカーポイント、そしてそれらのアンカーポイントからbへの近さをあわせて測るようにします。このように作られた行列はいくつも良い性質があって、例えば隣接情報は非常に疎に表せることができますし、またグラフラプラシアンなどを高速に求められるという特徴があります。この論文では、グラフラプラシアンを使った符号化に注目していましたが、アンカーグラフの方はいろいろな用途に使えそうです。

詳しく知りたい方はbeamさんによる解説や、nokunoさんによる解説をどうぞ

Kernel-based similarity search in massive graph databases with wavelet trees

Y. Tabei, K. Tsuda, SDM 2011 pdf

k個以上の共通要素を持つアイテムを求める問題をwavelet木を使うことで高速に求めています。wavelet木を利用することで、アイテム数に依存せず共通要素を調べることができます。
これまではほぼ全探索しかできなかったgraph向けの近傍探索を非常に大規模にこなすことができるようになっています。

田部井さんによる解説もどうぞ。

STL風に使えるマップ型コンテナの紹介と性能比較

preferred

2011-07-20 09:47:36

最近スマートフォンに乗り換えました。徳永です。

C++は世に数あるプログラミング言語の中では比較的メモリを食わない方ですが、それでもメモリ使用量が問題となる場合はあります。そのような場合の対処方法はいくつか有りますが、手軽に選択できる方法として、今日はSTLのmapやunordered_mapと同じ感じで使えるデータ構造をいくつか紹介したい思います。

続きを読む »

MapReduce以外の分散処理基盤BSP, Piccolo, Sparkの紹介

preferred

2011-06-17 14:32:34

どうも,実は今年から開発チームにjoinしていた中川です.可愛い犬の写真がなかったので,可愛いマスコットの画像を貼っておきます.

最近MapReduceとかその実装であるHadoopとかをよく聞くようになりました.これはつまり,それだけ大量のデータをなんとか処理したいという要望があるからだと思います.しかし当たり前ですが,MapReduceは銀の弾丸ではありません.

ということで,最近気になっているMapReduceとは違ったアプローチを取っている分散処理基盤について,社内のTechTalkで話した内容を簡単にまとめて紹介したいと思います. 続きを読む »

最近のtrieの話(xbwなど)

岡野原 大輔

2011-05-20 19:24:32

岡野原です。
ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。
今回はtrie(トライ)の最近の話をしたいと思います。
trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS(Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。
trieは図にあるように、木構造で各枝に文字が付随しており、根から葉へのパス上に付随する文字をつなげた文字が各キーに対応します。
同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下にある葉を全て列挙するだけです。hashはこの操作を効率的に行うことはできません。同様に辞書式順序でxよりも大きく、yよりも小さいキーを全て列挙するといったこともtrieは効率的に実現できますが、hashだとできません。
trieの大きな問題点として、木構造を格納する必要があり作業領域量が大きいという問題がありました。そのまま木構造を素直にポインタベースで実装してしまうと、元のキー集合に対しその数倍の作業領域量を必要とする場合も少なくありません。
この問題は簡潔木を利用することで解決できます。このアイディアを実装したものがtx, uxなどです。私もお世話になっているGoogle IMEもtxのクローンであるrxを利用することで大規模辞書を効率的に管理しています。
木構造を圧縮すると、元のキーをそのまま格納するよりも小さく格納できるようになり、データ圧縮としても利用することができます。trieでは文字列の先頭部分(接頭辞、prefixと呼びます)を一つのパスとして表現することができるためです。しかも、通常のデータ圧縮とは違って、データ全体を復元しなくてもあるキーのみを復元するということができます。
簡潔木を利用したtrieについての情報は既にある程度広まってきているので、今回は簡潔木を利用しないtrieの最新情報についていくつか紹介します。

XBWを利用したtrie

[1] “Structuring labeld trees for optimal succinctness, and beyond”, P. Ferragina, and et. al. FOCS 2005
[2] “Succinct Dictionary Matching With No Slowdown”, D. Belazzougui, CPM 2010
[3] “Faster Compressed Dictionary Matching”, W. K. Hon, and et. al. SPIRE 2010

ラベル付木に対する簡潔データ構造であるxbwは[1]により最初に紹介されました。その後[2], [3]の論文で、さらにxbwはシンプルになり高速化されています。

xbwについて簡単に説明します。

ノードから根に向かって辿った時の文字列をつなげた文字を、そのノードのreverse prefix pathと呼ぶことにします。次に全ノードをreverse prefix pathの辞書式順序でソートします。複数のノードが同じreverse prefix pathを持つ場合がありますが(trieの場合は無いが)、その時は木中の幅優先探索の順序順で順番を決定するとします。最後に各ノードの子に付随する文字をその順に格納します。これがxbwです。先ほどのtrieの場合の例を以下の図に示します。列reverse prefix pathは各ノードから根に向かうパスであり、末尾は特殊文字$がつけてあります。この$は他のどの文字よりも小さいとします。列childrenにそれぞれのノードに対応する子に付随する文字を格納します。ここで#とあるのはそこが終端ノードであることを示しています。この#は他のどの文字よりも大きいとします。children内部での順序は関係ありませんので集合で表すことにします。例えばchildren[1] = {t, i, w}, children[3] = {a, n}です。

結論を先に言うと、このchildrenの列だけを使って先程のtrieを完全に表現することができます(reverse prefix pathはいらない)。

実際に節点をchildrenの情報だけを使って辿ってみましょう。

rank(i, c)をchildren[1…i-1]中に含まれる文字cの出現数と定義します。また、C(c)を全てのchildren中で”c”より小さい文字の出現個数とします。例えばこの図の例ですとですとC(a)=0, C(e)=2, C(i)=4…となります。
まず、図中の根のノードに着目してみます。先程の表では、i=1となります。ここからラベル”t”を辿った場合、次に行くべきノードのreverse prefix pathは”t$”です。このノードは”t”で始まるreverse prefix pathを持つノードの中では最小のはずです。よって”t$”を持つノードはC(t)+1 = 10となります。

では、次にこのノードからラベル”e”を辿るとすると、その節点は”et$”をreverse prefix pathとして持つはずです。”e”で始まるreverse prefix pathを持つノードの数は、children[1…9]の中で”e”を持っている数に一致します。なので、”et$”に対応するノードの番号はC(e)+rank(10, e)+1=3となります。

このように、現在iの位置にいる時に文字cを辿った先のノード番号は

C(c)+rank(i, c)+1

として求められます。C(i, c)+1は文字”c”から始まるreverse prefix pathを持つノードが始まる添字番号であり、rank(i, c)はその中での順番です。

既にお気づきの方も多いと思いますが、これはBWT (Burrows Wheeler Transform, BlockSorting) におけるLF-mappingと同じ考えです。bwt(block sorting)は一本鎖のパスからなる木に対するxbwであり、xbwはbwtの自然な拡張になっています。

さて、このchildrenのテーブルをどのように効率的に格納し、rankを高速に求められるかが問題です。BWTの場合はここが文字列になっていたため、wavelet treeを利用することができました。今回は各位置に複数の文字が存在します。[1]では、ビットベクターと組み合わせることによって、集合を文字列にしてしまい、文字列に対するrank操作の問題に還元しました。[2], [3]では、各文字ごとに、転置ファイルのようにその位置に文字cが出現したかどうかをbit vectorで記録し、bit vectorに対するrank操作としてこれを実現します。どちらも、trieに対するk次経験エントロピーに漸近するサイズで格納できるということが示されています。

さらに、[3]では、このxbwを利用してAC法が実現できることが示されています。

木を潰したtrie

[4] “On searching compressed string collections cache-obliviously”, P. Ferragina, and. et. al. PODS 2008
もう一つ面白いtrieがFerraginaらによって提案されています。
論文にはcache-obliviouslyとありますが、注目すべきはcentroid path decompositionです。従来のtrieは遷移するノード数分だけランダムアクセスが発生しており問題になっていました。特にデータをディスクなどに格納している場合、アクセス回数が操作時間に直結するために問題になります。centroid path decompositionは元々の木を縦方向にぐしゃっとつぶします。
イメージだけでも掴んでもらうために、図を論文から借りてきました。左側の元のtrieの太い線に対応するpathをぐしゃっと一つのノードに潰します。このpathの付随するノードは、このpathの左上から順に右上まで反時計回りの順に大小関係が決まります。そのノードにはheavy pathのラベル列と、そのパスから分岐しているノードが何文字目からどのどの文字で分岐しているかの情報を記録しておきます。この情報により潰した後でも木を辿ることができます。
実際どのようにして潰すpathを決めるかについて説明します。
各ノードについて、その子の中で、最も子孫の葉の数が多い子を、そのノードのheavy childと呼びます。次に、各ノードについて、そのノードから葉までheavy childrenのみを辿っていくpathをheavy pathと呼びます。これを利用したcentroid path decompositionは次のように実行されます。まず最初に根に対応するheavy pathをたどってそのpathを一つのノードに潰します。次にそのpathから分岐して伸びている各ノードについて再帰的に同じようにheavy pathを辿って、そのpathを一つのノードに潰すというのを繰り返します。
この操作により、キーの種類数がK、文字種類数がSの時、木の高さは高々 O(log K)個になり、平均して O(log K / log S)個になります。どんなに高い木でもその順序関係を損なうことなく、木の高さを減らすことができ、アクセス回数を減らすことができます。
各節点での分岐数は増えるため、各節点での計算量は増えますが、アクセス回数が減らせることによりメリットは大きい場合が多いです。
この木に対する簡潔データ構造も論文中に提案されています。

Weak Prefix Search

[5] “Fast prefix search in little space, with applications”, D. Belazzougui, and et. al. ESA 2010
最後に紹介するのがweak prefix searchをサポートしたtrieです。
クエリ文字列pに対し、そのクエリ文字列が辞書中のどれかのキーの接頭辞である場合、そのキーの辞書中の辞書式順序の順位を返す操作をweak prefix searchと呼びます。
もし、クエリ文字列が辞書中のどれかのキーの接頭辞で無い場合、結果は保証せずランダムになります。
よって、weak prefix searchはbloom filterのようにone sided errorを許したデータ構造です。例えば、キー集合が{abc, abef, bcde}の時、abcに対しては1, abeを入力したら2、abcdeならランダムな値が返ってきます。
これまでもweak prefix searchを備えたデータ構造はString B-tree (blind  trie)などがこうした機能を有していました。
weak prefix searchは従来のtrieよりも弱い操作です(従来のtrieであれば、無い場合は無いと返すことができる)が、その分作業領域量は少なく抑えることができます。この論文では、
この問題を解くために必要なデータ構造は、従来のキーを格納するよりはるかに少ない作業領域量だけあればよいことを示しました。具体的にはキーの数がK、キーの平均長がLの時、必要な作業領域料はO(K log L)ビットになります。従来だとK Lビット だったのと比べると大きな違いです。
この論文ではz-fast trieを改良したHollow z-fast prefix trieとrange locatorを組み合わせてweak prefix searchを実現します。2-fattest numberなどいろいろ面白いアイディアを利用しています。

最後に

これまで話してきたtrieは実はいずれも動的なキーの追加・削除をサポートせず、前もって与えられたキー集合を扱っていました。
キーの追加・削除をサポートした上で、データをコンパクトに保ちつつ、高速な操作を実現するようなtrieは実現できるのか? これについてはまた紹介します。

分散データベース「HBase」の安定運用を目指して

preferred

2011-05-09 10:47:18

1年経ってiPhone4の電池がヘタってきた、太田です。

指数関数的にエントリ数が少なくなってきた本ブログですがw、景気付けのためにエントリを投稿したいと思います!本日はHBaseについてです。

Linux と Hadoop と HBase と ZooKeeper に詳しいあなた!あなたがターゲットです。

HBaseとは?

HBaseとは、HDFS (Hadoop Distributed File System)上に構築された分散データベースです。大量の非常に細かいデータをリアルタイムに読み書き出来るのが特徴です。最近ではFacebook Messageの基盤技術として使用された事で注目を集めています。

保存されたデータはHDFS上に保存され、HDFSの仕組みによってレプリケーションされるため安全にデータを保持することが出来ます。

また、MapReduceとも非常に相性が良く、保存されたデータに対してバッチ処理を行なうことが出来ます。リアルタイムにデータを入出力しながら、分散でバッチ処理も出来るようになります。

これを検証するために、弊社ではTwitterのデータをリアルタイムにストリーミングで保存しながら解析するシステムを作ってみました。が、HBaseは色々と敷居が高くハマりどころも多かったので、そこで色々と試している結果をblogで紹介したいと思います。

OSのセットアップ

HBaseのセットアップの前に、OS (Linux) の設定を正しく行なうことが重要です。

最大ファイルディスクリプタ数

HBaseのノードでは1プロセスから大量のファイル/ソケットをopenする可能性が有るため、最大ファイルディスクリプタ数を上げておく必要があります。/etc/security/limits.confに以下の記述を追加して下さい。

root soft nofile 65536
root hard nofile 65536
* soft nofile 65536
* hard nofile 65536

一旦ログアウトして再度ログインし、ulimit -nコマンドで65536と表示されていればokです。

カーネルパラメータ

以下のパラメータを指定します。kernel.panic* 系でカーネルパニックが有った際に、マシンが自動リブートされるようにします。

vm.swappiness = 0で、メモリがスワップアウトされにくくします。HBaseの各ノードは大量のメモリを消費しますので、それらがディスクに追い出されにくい様にします。

net.* で、ネットワーク関連のバッファを増やしています。

kernel.panic_on_oops = 1
kernel.panic = 1
vm.swappiness = 0
net.core.rmem_max = 16777216
net.core.wmem_max = 16777216
net.ipv4.tcp_rmem = 4096 87380 16777216
net.ipv4.tcp_wmem = 4096 65536 16777216

ネットワークドライバのアップデート

大量のデータを転送するジョブを走らせると、以下のようにパケットドロップが大量に発生するという問題が起こりました。ifconfigで、droppedパケットが出ていないか確認します。

[root@hdp10 ~]# /sbin/ifconfig
eth0      Link encap:Ethernet  HWaddr 90:FB:A6:DD:2D:90
          inet addr:192.168.0.60  Bcast:192.168.0.255  Mask:255.255.255.0
          inet6 addr: fe80::92fb:a6ff:fedd:2d90/64 Scope:Link
          UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1
          RX packets:661312053 errors:0 dropped:14045 overruns:0 frame:0
          TX packets:760148388 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:1000
          RX bytes:913845944363 (851.0 GiB)  TX bytes:1043952570747 (972.2 GiB)
          Interrupt:169 Memory:b1a00000-b1a20000

余りに数が多くて不可思議な場合は、ネットワークドライバのアップデートで解消される可能性が有ります。

今回は、ネットワークドライバにe1000eを使用していたので、そちらをアップデートしました。こちらのblogが参考になります。

ntpdのセットアップ

ntpdをセットアップし、ノードの時刻が常に正しくなっているようにして下さい。

HBase本体は時刻がズレていても動作は正しく行えるように書かれているはずですが、不可解なバグの原因やログの検証時にかなり不便なので必ず設定して下さい。

Javaのセットアップ

なるべく新しめのJDKを使用します。必ず Oracle 純正の JDK を使用してください。 OpenJDK, GCJ は避けるようにします。

Hadoopのセットアップ

Hadoopのセットアップを行います。今回はCDH3u0 (Cloudera Distribution for Hadoop, Update 0)を使用しました。HadoopのバージョンとHBaseのバージョンはかなりシビアに合わせないといけないので、CDHを利用するのがおすすめです。

dfs.datanode.max.xceiversの設定

hdfs-site.xmlで、dfs.datanode.max.xceiversの値を増加させます。datanodeには、region serverから大量のコネクションを張られる可能性が有るために、この設定が必要です。

  <property>
    <name>dfs.datanode.max.xcievers</name>
    <value>3072</value>
  </property>

ZooKeeperの設定

ZooKeeper専用ノードの検討

HBaseを入出力に使用するMapReduceジョブを動作させると、必ずZooKeeperへのコネクションがはられます。これが失敗すると、何も始まりません。

始め、ノードをけちってTaskTracker/DataNodeと同居させていたのですが、I/O負荷が上がるとOSのレスポンスが悪くなり、ZooKeeperへのコネクションが同時に切断されまくるという問題が起こりました。

安定稼働には、負荷の低いノードに同居させるか、専用ノードを用意するのがベターです。

maxClientCnxnsの設定

zoo.cfgで、maxClientCnxnsを設定します。こちらは、1ノードからのZooKeeperの最大コネクション数の設定です。デフォルトでは10に設定されています。

つまり、デフォルトでは1ノードから10並列以上繋げない事になります。MapReduceを使用した際には簡単に上限を超えてしまいますので、少し大きめの値を指定しておきます。

# max number of client connections from the same node
maxClientCnxns=128

zoo.cfgの全ノードへの設置

zoo.cfgを全ノードの/etc/zookeeper/zoo.cfgに配備します。

HBaseのセットアップ

ついにHBaseのセットアップです。

RegionServerへのメモリの割当

RegionServerへは出来る限りメモリを割り当てます。ただし、MapReduceを行う場合には、タスクが使用するメモリも計算にいれておく必要があります。もし必要以上にメモリを食ってしまうと、OSのOOM KillerによってデーモンがKillされてしまう場合があります。

メモリの設定はhbase-env.shで行います。

# The maximum amount of heap to use, in MB. Default is 1000.
export HBASE_HEAPSIZE=16384

MSLABの有効化

最近までのHBaseには、(特に大量のメモリを割り当てている場合)非常に時間のかかるGCが走ってRegion Serverが停止したように見えてしまう問題がありました。

これを解決するために、mslabという仕組みが導入されたのでそちらを有効化します。hbase-site.xmlに以下の設定を追加します。

  <property>
    <name>hbase.hregion.memstore.mslab.enabled</name>
    <value>true</value>
  </property>
  <property>
    <name>hbase.hregion.memstore.mslab.chunksize</name>
    <value>2097152</value>
  </property>

mslabについては、こちらの記事を参考にして下さい。

/etc/hbase/conf/を全台に配置

/etc/hbase/conf/以下のファイルを全台に配置します。

HBaseを利用したMapReduceプログラムのポイント

HBaseを利用したMapReduceプログラムは、以下のようになります。TableMapReduceUtilを使用して InputFormat, OutputFormat を設定します。

zoo.cfg, /etc/hbase/conf/をクラスパスに追加

/etc/zookeeper/zoo.cfg, /etc/hbase/conf/をクラスパスに追加する事で、zookeeper/hbaseの設定ファイルを見つけてくれるようです。

意味不明なシステムなので、明示的にconf.addResourceで追加した方が良いかもしれません。

hbase.client.scanner.cachingの設定

ここで、hbase.client.scanner.cachingというパラメーターが非常に重要になります。

conf.set("hbase.client.scanner.caching", "1024");

HBaseを入力にしたMapReduceでは、Scannerを用いてキーバリューペアにシーケンシャルにアクセスします。この時、デフォルトでは1ペア毎にRPCリクエストを発行してペアを取得します。

hbase.client.scanner.cachingを1024にすると、1回のリクエスト1024個のペアをバッチで取ってくるため、非常に高速化されます。

手動リージョンスプリット

MapReduceプログラムを走らせていると、他のMapTaskと比較して100倍程度の時間がかかるTaskが有りました。このおかげでジョブの実行時間が非常に伸びてしまいます。

この場合は、そのタスクの担当しているリージョンを特定し、手動でsplitすることで細かいサイズに分けることが出来ます。何故、100倍もサイズが偏るのかはまだ謎です。

$ hbase shell
hbase(main):001:0> split "twitter,43264430598914048,1302178394984.bb056008b2c069ad88ace728bcf0d757."
0 row(s) in 0.7930 seconds

肥大化したリージョンの特定方法は、時間の掛かっているタスクのログを心の目で見るか、JRubyでスクリプトを書いてみて特定します。

まとめ

HBaseは容量・用法に合わせて正しくセットアップしましょう。リアルタイムにデータを入れながら大規模データを解析出来るのは非常に嬉しいのですが、その反面、運用ノウハウはまだまだ必要そうです。

他にも使用されている方がいらっしゃいましたら、是非是非、フィードバックお待ちしています。

分散並列環境における機械学習

岡野原 大輔

2011-02-24 14:17:27

もうすぐ春ですね。花粉さえ飛ばなければ最高なのに。岡野原です。

先日、Hadoop Conference Japan 2011で、”MapReduceによる大規模データを利用した機械学習”というタイトルで発表しました。

発表内容は三部構成になっています。

最初に、機械学習の基本と、それがMapReduceとどのような関係にあるかを紹介しました。その中でHadoop上で動く機械学習ライブラリMahoutの簡単な紹介をしました。

次に、機械学習の最前線ではどのような問題が解かれているかを紹介し、グラフィカルモデルの例、一般の最適化(教師付き学習におけるパラメータ学習)の分散並列化についての話題をしました。

最後に、MapReduceの補完として使えるようなシステムの例としてdremelを紹介しました。このシステムはMapReduceがバッチ型処理で、全データが処理対象の場合が得意なのに対し、一部のデータのみを参照して簡単な解析をする場合のアドホッククエリが得意なシステムです。このシステムについては登場の時からずっと興味を持っており、いろいろな発展形が考えられると思います。基本的に検索索引と構造は似ているので、そのあたりでの技術の交流ができそうですし、機械学習の高速推論とか新しい問題でも使えそうです。

また先週は、これと関連する形でT-PRIMAL 公開勉強会 NIPS2010読む会で、LCCC2010のワークショップでの発表を紹介しました。上の資料と使い回しの部分が多いのですが、より数式とか機械学習の部分とか突っ込んだ内容になっていますので興味のある方はこちらも参考にしてください。またスライドでは略証しかありませんがIterative Parameter Mixtureの収束証明とかは元論文のを追って見てみると面白いと思います。

LCCC2010:Learning on Cores, Clusters and Cloudsの解説

私自身、1台の限られたリソース上でいかに高速化し効率的に処理をするかが好きで分散並列に興味を持ったのは遅めだったのですが、この世界はこの世界でいろいろやることがあって面白いです。
もしこれらのスライドで少しでも興味を持つ人が増えていただければ幸いです。

MinHashによる高速な類似検索

岡野原 大輔

2011-02-02 17:08:17

年が明けてもう一ヶ月経ちましたね.岡野原です.

今日はMinHashと呼ばれる手法を紹介します.これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている).

続きを読む »