fujimap: 簡潔な連想配列

博論終わったので仕事の合間にfujimapというライブラリを作ってみました。

fujimap project

fujimapは作業領域が非常に小さい連想配列で、文字列からなるKeyを利用して、整数値もしくは文字列からなるValueを登録・参照することができるライブラリです。

今巷では大規模なKey Value Stroe (KVS)が流行っていますがFujimapは一台のマシンのメモリ上で動作することを想定して作成されています．Fujimapの特徴は必要な作業領域量が非常に小さいことです．キー自体を明示的に保存しないため、作業領域は値を格納するのに必要なサイズと、許容するfalse positive（後述）にのみ依存します。

例えば、google N-gramのunigramの約1300万キーワードとそれらの頻度の対数を記録する場合、false positiveを気にしないなら、一キーワードあたり約4bit（全部で7MB、もともと136MB)で格納できます。C++ std::mapの約1/100です。メモリが10GBある場合、同じようなデータなら200億 Key/Valuesぐらいを高速に操作できます。

fujimapではKeyを明示的に格納しません。それでも登録したKeyに対しては正しい値を常に返します．それに対して、登録されていないKeyに対してはユーザーが設定した確率で誤り、NOTFOUNDが返らずにランダムな値が返ってきてしまいます（false positive rate, 偽陽率）．Bloom Filterのようにfalse positive側のみにエラーをゆるし情報理論的限界を破っています．

fujimapが必要とするサイズと偽陽率はトレードオフの関係にありfpLenと呼ばれるパラメータで設定できます．1KeyあたりfpLen bitのオーバーヘッドで偽陽率は2^{-fpLen}となります．例えば、1keyあたり10bitのオーバーヘッドで2^{10}分の1、つまり約0.1%の確率で登録されていないKeyに対しても、NOTFOUNDではなく、何らかの値が返ってしまいます．

これはKeyがどのような文字列からなる場合でも同様になりたちます．例えば，Keyの長さが1KBのように長い場合でも、その格納に必要なBit数はfpLenと値のみで決まります．

いくつかの実験結果は先ほどのページに乗せてあります．
先ほどのGoogle N-gramの例では

1keyあたりに必要なbit数
std::map 573 bit
tx 35.4 bit (keyの保存に29.4 bit , 値の保存に6bit）
fujimap 4.4 bit

であり、構築時間、参照時間はstd::mapとほぼ同じです

これらの実験結果やAPIなど詳細についてはプロジェクトページをみてください。

説明や使用例、アプリケーションなどは随時追加していきます。

注意点として、fujimapでは一応、動的な追加、変更が一応C++ APIではサポートされているのですが、それらの命令を使った途端に先ほどの偽陽率や登録したキーには必ず正しい結果が返ってくるという保障がなくなります。このあたりについてはきれいに説明できないので使う必要がないなら極力使わないようにしてください。どうしたらきれいに外から使えるかまだ考え中です。

--
Fujimapの内部はいくつかの研究を元にしたものに実装的な工夫を追加しています．
Fujimapの基本的なアイディアは最小完全ハッシュ関数と同様のもので、N個のKeyに対し衝突しない[0,N-1]の値を割り当てる手法を値を格納する方法に拡張しています．

まず、FujimapでKey kを格納する場合R個（R=2,3など）のハッシュ関数での値h1(k), h2(k),... hr(k)を求めます．次に、ビット配列Bから、これらの排他的論理輪の値を求めます v = B[h1(k)...] ^ B[h2(k)...] ^ B[hr(k)...];　このvがkに対応する値です．

値は擬陽性をチェックする部分（fpLen bit）と、それ以降の実際の値を格納する部分からなります．キーkに対し、先ほどのハッシュ関数とは異なるハッシュ関数でkに対するsignatureを求めておき、先ほどのvの先頭fpLen bitがsignaretueと一致する場合は、それが実際の値、そうでない場合は登録されていないKeyということでNOTFOUNDを返すようにします。

fpLen bit以降の値は実際の値を固定bit長のBinary符号、もしくはGamma符号で格納しています．

登録されている全てのキーに対し、上のように操作して正しく動作するようにB中ビット値を決定する問題は連立方程式の問題となります．この問題は最小完全ハッシュ関数を決定するのと同様に、キー集合とそれらの依存関係からハイパーグラフを構築し、そのハイパーグラフ中から次数が１である頂点とそれにつながっている枝を順にのぞいていき、次にこの順番と逆に各bitの値をgreedyに決定していくことによりキーに比例する時間で決定できます。

非常に大規模なキー集合を扱う場合、構築に必要な作業領域が大きくくなってしまう問題が生じます．そのため、Fujimapでは最初にKeyの集合を簡単なハッシュ関数を利用していくつかのブロックにわけておきます。そして各ブロック内部で先ほどの手法を利用してキーと値を結び付けます．各ブロックのサイズをディスクの１ブロックと同程度にすることにより、ディスクアクセスを生じる場合でもシーク回数が一回でできるようなデコードも実現可能です．

--
fujimapの開発にあたり、開発環境をいろいろ変えています

ビルドシステムにautomakeから変更しwafを使っています（隣の隣の席の田中さんによるwaf解説)
ものすごく速くて色がついて怪しいautomakeの黒魔術を使わなくて便利です。まだいまいちわかっていなくて例をちょっと変えたものしかつかっていないけど。

あと、google code projectをフル活用。あとdoxygenからgoogle project wikiに変換するやつがうまく動けば、いいんだけど、どうも動く動かない

--
ちなみにライブラリの名前は博論書きの時にお世話になった富士そばに由来しています。天玉が好きです。