1 - Sites

2009/02/20@Gree KeyVal勉強会
Key (-Value)の
的な
格納手法について
岡野原 大輔
(株) Preferred Infrastructure (PFI)
大学情報
学 研究科コン
ピュータ科学専攻
自己紹介
• Blog http://hillbig.cocolog-nifty.com/
• 興味分野
– データ圧縮、自
語
、全文
、
要するに⇒たくさんのデータが大好き
• Preferred Infrastructure
– Sedue（圧縮全文
）
– Hotate（関連記事レコメンダ）
• 宣伝：今号のWEB+DB Pressに
レコメンド特集！
学
今日の話
• キー格納手法の研究分野では今どんなの
があるのという に つ話
眠くなっちゃうよ
• 簡潔木
– tx:コンパクトなtrie
• ハッシュ関数
– Cuckoo Hash
– bep:最小完全ハッシュ関数
の
• 文字 のキーを
• (キー,値)の
用してい
い
な値を格納したい
– (URL, webページ)
– (メールアドレス, 個人情報)
– (単語, 単語の出現リスト)
• 方法1: 木による格納
– キーに対しtrieなどの木構造を構築し、木の節点、 に値を格納
–
通 頭辞
などできる。 ：http://hillbig*を
など
• 方法2 ハッシュによる格納
– キーでハッシュ値を計算し、それをアドレスとして使い、その
値を参照（または値へのポインタを格納）
⇒これらの操作を可能な
り小さいサイズで
に
う
⇒そんなにメモリに載せちゃダメってのも載せちゃう
実装手法
tx
サイズ
（1≒100MB)
0.46
bep
2.03
bep(キー無し) 0.07
darts
3.62
stl::set
8.86
stl::hash_set 8.18
構築時間
(秒）
lookup
30.5
44.5
44.5
16.7
39.5
32.4
10.3
0.49
0.46
1.25
3.30
0.54
106回, 秒
*common prefix searchなどをサポートしているか
complex
search*
○
×
×
○
○
○
• 実験データは Web 1T 5-gram Version 1 の 1-gram
•キーワード種類数は13588391
•キーワードを全てつなげた時の
は112349445 (約100MB)
•darts: double arrayによりtrieを実装したライブラリ
•stl::set stl::hash_setはC++ STLライブラリ
•tx, bepともに非常にコンパクトにキーを
可能
方法1 木によるキーの格納
キー集合を木構造で
◦ 各枝に文字が付随し、つなげるとキーになる
◦ 値は節点の先に格納
t
e
a
(trie)
i
o
n
木のポインタ表現は1ノードあたり
約96bit必要
e - 親、最初の子、次の兄弟を指す場合
w
n
n
LOUDS表現を 用すると1ノードあた
り約2bitに。木を辿る操作は定数時間
キー : "to", "tea", "ten", "i",
"in", "inn“, and “we”.
tx：木の簡潔表現によるtrieライブラリ
• キー集合をコンパクトに格納し操作可能
– 元のサイズの約1/2で格納
– 10億キーワードでもPC上のメモリに載る
– 値はtxが返すユニークなIDを 用して格納
• 複
•
な操作でも、キーが えても
から２ 。 れて 定してきた
– 「“tx trie で
してください
–
外にも他
、研究 関での 用、
海外の某Webサービス、i-phoneアプリなど く
用されてる
準備：Rank/Select辞書
ビット
に対する簡潔データ構造
• ビット
B[0…n-1]に対し，次の二つの操作
– rankb(B,i) : B[0…i]中のb∈{0,1}の数を返す
– selectb(B,i) : (i+1)番目のb∈{0,1}の位置を返す
•
B
0 1 2 3 4 5 6 7 8 9 10
1011011101 1
rank1(B, 6) = 5 select0(B, 1) = 4
• Rank/Select辞書はビット
の0次経験エントロ
ピーで定数時間で実現可能 実装 などは[Okanohara+ 07]
LOUDS: Level-Ordered Unary Degree Sequence
[Jacobson 89, O’Neil Delpratt 06]
• 木をBFSで辿り，k次のノードを
に k個の’1 ‘と1個の’0’で表す
きがけ
– 先頭にSuper Root S（番人）を追加
– n個の節点からなる順序木にはn個の1, n+1
個の0が出現する。(2n+1) bitでの符号化
– Bi番目の節点とi番目の1, (i+1)番目の0が対応
1
3
2
4
5
6
7
S
8
1
2
3
45 6 7 8
10 110 1110 110 0 0 0 0 0
LOUDS上での操作
• B[i]に対応するノードに対する各操作
– 最初の子 = select0(B, rank1(B,i)-1) + 1
– 最後の子 = select0(B, rank1(B,i)) - 1
–親
= select1(B, rank0(B,i)-1)
2
3
1
S
– 次の兄弟 = i+1
45 6 7 8
10 110 1110 110 0 0 0 0 0
1
3
2
4
5
2
6
7
8
実際確かめてみよう
枝に付随する文字情報，各節点に
付随するデータも
で保存可能
方法2 ハッシュによる格納
• 通常のハッシュ関数を使う衝突が発生
– 衝突を
するのにどれだけ計算 が必要か
分からない
– 新時に複数の場所をロックする必要がある。
絶対危ない
• 面白いハッシュ関数
– Cuckko Hash
– 最小完全ハッシュ関数
– 他多数
Cuckoo Hashing [Page+ 00]*(1/2)
説明のためにオリジナルとはちょっと違います
• キーkの登録をする場合
– 二種類のハッシュ関数h1 h2を用意
– h1(k)とh2(k)を調べ、どちらか空いていたらそこに
– どちらも埋まっていたら、片方のハッシュ関数の
方にあったキーを追い出し、そこに値を格納する
– 追い出されたキーは、自分のもう片方の候補を追
い出し、そこに値を格納する。これを繰り返す
– この操作が一定回数止まらなかったら、新しい
ハッシュ関数を用意し、一からやり直し
k
k1
Cuckoo Hashing (2/2)
• 一から作りなおす確 は非常に
全 の
計算 はキー数の
く、
で えられる
– 登録時間の し計算 は定数
– グラフ中に
がある確 であり、 密に計算可能
または、逃げ場（Stash）をちょっとだけ用意すれば
）をちょっとだけ用意すれば
– または、逃げ場（
作り直さなくても済むことがわかっている
• キーの参照が定数箇所（２か所）の参照で済む
⇔従来のHash関数はどこまで るかわからない
– ディスク上とかにおいてもできる
• 様々なバリエーションがその後も提案
– 三つのhashを使うものや、ハードウェアで実装
bep : 最小完全ハッシュ関数による連想
• 大
キーを
うための連想
– lookupのみサポートしキー順序は保存しない
• 最小完全ハッシュ関数を
用
– キー集合Sに対する完全ハッシュ関数
⇔S中のキー同士は衝突しないことが保障
– Sに対する最小完全ハッシュ関数
⇔ハッシュ関数が完全かつ、ハッシュ値の範囲が
[0, |S|-1] （重複の無い連番を返す）
– 単純なアプローチでは作れない
• n個のキーで
できる確
は n! / nn ≒ e-n
• 先ほどのCuckoo Hash+簡潔データ構造
完全ハッシュ関数の構築手法
[Ziviani+, WADS 07]
• n個のキー k1 k2… knに対し，[0..m-1] (n≦m)
を値域とするPHFを構築する
• 二つの
なハッシュ関数h1, h2を用意
– h1は[0..m/2) に， h2は[m/2 .. m)に写像するよう
なハッシュ関数
• グラフG={V,E}を考える．
– 頂点 V = {0,…,m-1}
– 枝 ei = (h1(ki), h2(ki))
0 1 2 3
(i=1…n)
5 6 2
7
– 2部グラフであり、枝の数はn個 0
3 8
5 6 7 8
4
4
9
完全ハッシュ関数の構築手法 (続)
• 各枝につき，頂点を1つずつ割り当てる
– この時，割り当てた頂点が重複しないように
する．グラフGに
が無いなら可能
–
があったらハッシュを作り直す
– 各頂点vに番号g(v)∈{0,1}を与え，割り当て
られるようにする
• PHF: pは次の通り
g
0
0
0
1 2 3
5 6 2
7
0
3 8
5 6 7 8
4
0
p(k )= hi (k )
i = g (h0 (k )) + g (h1 (k )) mod 2
1
g
1
1
0
1
4
9
0
完全ハッシュ関数から
最小完全ハッシュ関数
• 今回構築したPHFは既にかなり密
– m=1.23n, 値域のうち1/1.23はキー
• rank関数を
用しMPHFにする
– B[0…m-1] : B[i]=1: iにキーがある
p (k )= rank1 ( B, hi (k ))
i = g (h0 (k )) + g (h1 (k )) mod 2
g
1
0
0
0
1 2 3
5 6 2
7
0
3 8
5 6 7 8
4
0
キー k が h0(k)=2 , h1(k)=6の場合
i = g(2)+g(6) = 0+1 = 1
p(k)=6, rank1(B, 6) = 5
g
1
1
0
1
4
9
0
今後の予想
• keyとvalueの相関をとらえて圧縮
– keyが似ているならvalueも似ているはず c.f. xbw
– おそらくkeyでsortしてvalueをその順につけてLZで十分
• より操作の局所性を保障したデータ構造
– よりキャッシュヒット＆ロックの範囲を狭く！
• ライブラリもどんどん出てくるはず
– 研究で手法が提案されてから実用的になるのは1
5
– 有望そう：
圧縮したまま定数時間でランダムアクセス可能
追加・削除・をサポートしたような簡潔データ構造
近似有でデータを格納
– 話せなかったが、単調最小完全ハッシュ関数, Bloomier
Filterも面白いよ