単語と文字の話

海野 裕也
リサーチャー

2011-05-29 22:01:28

4月からPFIで働いてます。海野です。
今日は単語の話をします。読み物的な話なので軽く読んでください。

続きを読む »

最近の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は実現できるのか? これについてはまた紹介します。

乱択アルゴリズム紹介(最小カット)

oxy
エンジニア

2011-05-14 18:13:20

吉田です。今日も引き続き有名な乱択アルゴリズムということで最小カット問題に対する乱択アルゴリズムを紹介したいと思います。ネタが無くなるということは無いのですが、有名かつ簡単なものとなると、そろそろ終わりが近くなってきているかもしれません。
続きを読む »

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

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