あなたの知らないハッシュテーブルの世界

40.5K Views

April 12, 23

スライド概要

profile-image

分散システムとかデータベースとかロックフリーとかが好きです。

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

あなたの知らない ハッシュテーブルの世界 @kumagi

2.

データの集合を扱いたい C B A データの集合

3.

素直な実装 • 配列に順番に入れて記憶 – 配列の中を走り回って探したり消したり加えたり G L C AB CD E F GH I J K

4.

遅い • 要素数が増えてくると大変なことになる • 要素数nに対しO(n)の計算量 – 入れれば入れるほど遅くなる C

5.

閑話休題 • ただの配列の方が速い事は実は意外とある – この話はまた今度

6.

お待ちかねハッシュテーブル • まずハッシュ関数から • ハッシュ関数とは – 値を入れると数字を一つ出してくれる関数 – 同じ値を入れたときに同じ数字が出てこれば良し – 値はダブっても気にしない a b c a ハッシュ関数 92 33 12 92

7.

お待ちかねハッシュテーブル • ハッシュ関数の結果を配列の索引に使うだけ – 値が大き過ぎたら剰余の値を使う – 配列がどこまで大きくなっても労力はハッシュ関数一回 find S • いろんなところで insert F delete F 大活躍 • データベース ハッシュ関数 • PerlやRubyや Pythonの{} 3 5 3 • もちろん貴方 F S のPCの中でも

8.

違うキーの値が被ったらどうするの? • ここからが本題 • 単純な解「広い所に移せばスッカスカになるよ!」 – その操作自体は遅い • 「リハッシュ」と呼ぶ N 引っ越し 既に埋まってる… C F BK U T G 入れる! N C B U G F K うわっメモリ食い過ぎ… T

9.

解決策 • リハッシュを最小限にしたい • 解決策はOpenAddressingとClosedAddressing • もちろんそれぞれお話しします

10.

ClosedAddressing • 別名OpenHash。もしくはChainHash • ポインタで繋ぎハッシュの衝突を解決 • よくC言語の教科書とかに載ってる :ポインタ S K I Z G P

11.

OpenAddressing • 別名ClosedHash。←超紛らわしい • 一つの配列の中に全要素を入れる – ぶつかったら隣の場所にinsertし直す S K I Z GP IとKでハッシュ値が衝突したので 隣に入れた

12.

OpenAddressingとClosedAddressing • 平たく言うと、数珠つなぎにするかしないか – 下の図の K と I の処理に注目 • 同じハッシュ関数を使った仮定 Closed Addressing Open Addressing S S K I Z G P KI Z GP •衝突したら別の場所に入 れるのがOpen Addressing •衝突したとき数珠つなぎに するのがClosed Addressing

13.

OpenAddressingの衝突回避手法 • ハッシュ値が衝突した場合の処理 – 設計方針によって変わる Liner Probing AB CDE F ±1, 2, 4, 8, 16… G E C ABD Quadratic Probing H F Double Hashing Hash(x), Hash(Hash(x)), Hash(Hash(Hash(x))).. D B A E C

14.

OpenとClosedでどう違うの? • 速度が違う – キャッシュに当たるかどうかは重要な問題 Closed Addressing Open Addressing S S K Z K I Z GP G P I ポインタを使う≒キャッシュミスする

15.

キャッシュミス? • メインメモリは遅いので、CPUは使うデータとその 前後を自動で手近に置くようにできている 数クロック CPU L1キャッシュ データ+命令で64KB 10数クロック L2キャッシュ 200クロック以上 メインメモリ 数MB

16.

キャッシュミス? • キャッシュ内に無いデータへのアクセスは遅い CPU G S K Z I メインメモリ P

17.

OpenとClosedのどっちが良いの? • ポインタを使うと遅くなるならポインタを使わない OpenAddressingが最強では? • とくにLinearProbingはキャッシュに当たりまくるので 最強に見える AB CDE F キャッシュミス少ない! • 確かに速いけど欠点がいくつかある

18.

OpenAddressingの欠点 • クラスタリング現象と削除回りの挙動 – こんな感じに特定の部分が高密度で埋まるとHop数ばか り増えて遅い – 具体的にはホップ数が一定数を超える場合にリハッシュ AB CDE F • Google Dense HashはQuadratic Probing(1, 2, 4, 8, 16..) • こっちの方がクラスタリング現象にいくらか強い • ソースにはいろんなパターンを試した形跡がある

19.

OpenAddressingでの問題:データ削除 • 削除はどうするのか • 実はそのまま消すと困る AT C Insert(A); Insert(T); Insert(C); Find(C); ←OK Delete(T); Find(C); ←Not Found?

20.

OpenAddressingでの削除操作 • 完全に消す代わりに削除済みマークを付ける – 挿入時には空スロットとして扱って上書きする – 検索時には何かが入ってると見なしてまたぐ – TombStone(墓石)とも言う AT C 削除マーキング Insert(A); Insert(T); Insert(C); Find(C); ←OK Delete(T); Find(C); ←OK!

21.

削除が増えると • 性能が極端に落ちる。 – 前述のクラスタリングとセットだと目も当てれない • 墓石地獄状態! ふぇええ… Find(G); DF S AT CEZ P Zしか入ってない • 使ってるうちに使い物にならなくなるので、定期的にリハッシュ などで整理してやらないといけない • Google Dense Hashなどにも搭載されている Z スッキリ!

22.

ここまでのまとめ Closed Addressing Open Addressing S S K Z K I Z GP G P I • クセがなく使いやすい • 遅い • 性能は安定している • 扱いにコツが必要 • 速い • だんだん遅くなる

23.

速度特性 • 遅延をグラフに描くとこんな感じ – 英語Wikipediaのページから抜粋 遅 い 密度

24.

メモリの視点から見ると Closed Addressing Open Addressing S S K Z K I Z GP G P I • ポインタの分大きい • オブジェクトが小さい 場合無駄が多い • 比較的無駄は少ない • 空きバケットの分の 無駄はある • 空きを減らすとクラス タリングしてしまう

25.

閑話休題 • 身近な実装はどうなっているのか? Open Addressing Closed Addressing S K S Z GP I Closed Addressing S K I Z GP KI Z GP

26.

Memcached • • • • • なぜClosedAddressing? 可変長構造体を使って巨大データを扱っている 拡張時の性能スパイクを抑えるための工夫に見える Chainの平均長が1.5を超えたらRehash Memcachedのキモい所は他にもあるけどまた今度 可変長(~GB級) Info Key Info Key Value Value

27.

少し脱線 • Cuckoo Hashing(カッコウハッシュ) – 2001年に論文の出た比較的新しい手法 – 検索が高速なOpenAddressing • 2つの配列と2つの異なるハッシュ関数を使う – 配列とハッシュ関数は1対1対応 – 挿入済みならどちらかの配列に入っている – 検索は2つのハッシュ関数で2つの配列を見れば良い • 最悪2回の探索で不在がわかる H1 Z K P H1(Z) == 2 Find(Z) H2 S H2(Z) == 0 G I

28.

Cuckoo Hashing • 検索は最大2箇所を見れば良いだけなので高速 • 面白いのは挿入操作 H1 D Z K P Insert(D) H2 S G I • 衝突した場合はカッコウの習性のように他の要素 を蹴り出す • 検索で見つけられるようもうひとつの配列へ

29.

Insert操作の注意 • 無限ループするかも・・・! – 蹴り出し回数に上限を設けて回避 • 上限に至ったらリハッシュする戦略 ふぇぇ・・・ H1 Z K P Insert(U) H2 S G I – 密度が50%を超えると急激にパフォーマンスが落ちる

30.

どれが良いのよ? 比較項目 ClosedAddressing OpenAddressing CuckooHashing 検索コスト チェイン長で制限可 工夫しないと辛い 2回 キャッシュミス 多い 少ない 少ない メモリの無駄 ポインタ分無駄 高効率 50%までしか使用不可 管理 特になし たまに整理 特になし 挿入コスト ポインタ繋ぐだけ 空きスロットの探索必須 無限ループの危機 • 検索コストが簡単に見積もれてキャッシュミスが少なく てメモリに無駄が少なくて整理が要らなくて挿入コストを 調整できるハッシュ無いかなー?

31.

そこでHopscotch! OpenAddressingのキャッシュヒット力と ClosedAddressingの使いやすさを両立する 新しいハッシュテーブル!

32.

What is Hopscotch? • いわゆる「けんけんぱ」 • 飛び方を決めてその通りに 飛ぶ遊び • 名前かっこいい!

33.

メモリレイアウト • Hop情報が同じ配列に並ぶ • この情報は1word幅(4 or 8byte)

34.

データ構造 • 配列上の全バケットがデータの他にHop情報を持つ – Hop情報は物理的には1ワード幅のビット列 • 図では大きさの都合上8bitということに – ここから隣のどのバケットに、本来ここに入るべきだったア イテムが置かれているかを示す • 探すときはその通りにHop Scotch! 1word アイテム 1 1 0 0 1 0 1 0

35.

検索 • チェインハッシュで言うところのこれと状態は同じ – どちらもハッシュが衝突して複数のアイテムがぶら下がっ ている – メモリに連続している分、Hopscotchのほうがキャッシュ ヒット率が高い アイテム A アイテム B アイテム 10100000 同じ A B

36.

検索 • 普通のHashmapと同様にスロットを検索する • 目的スロットのHop情報を見て、位置に対応するデータを順番に調べて いき目的のものを見つける • 1wordのbit数分の比較を行えば検索の成功or失敗を決定できる – 比較回数はO(1)で済む アイテム 1 1 0 0 1 0 1 0 A B C D 4つbitが立っていたので比較4回

37.

挿入 • Linear Probing同様に空のスロットを探す Hopに追記 アイテム 1 1 0 0 1 0 1 10 アイテム 01101000 あった!

38.

挿入 • それすら埋まっていたら? • 別に定めた上限以下のスロット数まで配列を舐めながら、 アイテムが入っていない空バケットが無いかを探す – 無いならさすがにテーブルを拡張して全部再配置してやり直し アイテム 11001011 アイテム 01101000 アイテム アイテム 10110000 あった! 01010010 • 押し出してでも場所を作るという点で少しCuckoo Hashing的 • ただしコストは上限で調整可能の上、事前に

39.

挿入 • 見つけたらHop情報を書き換えながら左へと持っ てくる • これで挿入できる アイテム 1 1 01 0 1 0 1 1 アイテム 00 1101001 0 アイテム アイテム 10 0 1 1 0 0 0 01 0 10 01 1 0 0 1 0

40.

ベンチマーク • 論文からグラフを抜粋 • 密度が上がっても速度が低下しにくい Hopscotch Cuckoo Linear Probing Chained

41.

おいCuckoo…

42.

作ってみた • http://github.com/kumagi/nanahan • 9割ぐらいの密度になっても平然と動く!

43.

追試ベンチマーク • Hopscotch速い Hopscotch

44.

比較 比較項目 Closed Open Cuckoo Hopscotch 検索コスト チェイン長 で制限可 工夫しないと辛 い 2回 調整可 キャッシュミス 多い 少ない 少ない 少ない メモリの無駄 ポインタ分 高効率 50%までしか使用不可 Hop情報 管理 特になし たまに整理必須 特になし 特になし 挿入コスト チェインを 可変 舐めるだけ 無限ループの危機 調整可 • それぞれの弱点を補った感じ

45.

ぶっちゃけ • 速いHashtableがC++で欲しくなったら何使う? • 僕ならgoogle_sparse_hashとgoogle_dense_hash を使い分ける – どっちもstd::tr1::unordered_mapとほぼ一緒 • DenseはNULL値を明示的に設定する必要がある – Sparseはメモリ効率↑速度↓ – Denseはメモリ効率↓速度↑ • Denseは反則級に速いけど多分pod型しか使え ない – 詳しい話が聞きたい人は懇親会で

46.

このあと話そうと思うもの • Java.util.concurrent.ConcurrentHashmap • Lock-free Hashmap 3種 – Cliff Click – High-scale Lib – Split-Ordered List – 日立謹製Lock-free Hashtable • Concurrent Hopscotch Hashing

47.

Java.util.concurrent.ConcurrentHashmap • みんな大好きDoug Leaの傑作データ構造 • Java5から標準ライブラリ入り • スレッドセーフで奥様も安心! A B C ストライプロック Lock Lock Lock D H Q P J • 以後ではロックは省略 K

48.

Java.util.concurrent.ConcurrentHashmap • JVMのいい所を最大限生かす構成 • 検索がWait-free、その代わり削除が遅い Final Volatile A B C D H Q P J K つまり書き換え 不可

49.

j.u.c.ConcurrentHashmapの検索 • 検索時はVolatileなスロット情報を読む – その後はFinalしかないのでうまく行けば自分のL1キャッ シュがSステートになって凄く良く当たる • 見つからない場合にはロックを取って再度探索する ことで「検索失敗」を線形化する – ややこしいので割愛 A 最初の参照 解決だけ Volatile B C D H Q P J K

50.

j.u.c.ConcurrentHashmapの挿入 • Lockを取って先頭に継ぎ足す – CASでも良かったけど検索・削除・リハッシュとの兼合い • Volatile部分しか書き換えないので安心 Insert(Z); Z A B C D H Q P J K

51.

j.u.c.ConcurrentHashmapの削除 • ロックを取ってから部分的に作り直す – Finalなので書き換えられない • ReadCopyUpdate(RCU的)で、JVMのGCのお陰で動く A B C D Delete(K); H Q Q P J K Qを複製

52.

リハッシュ? • 全部のロック取るだけです

53.

どれぐらいロック取るの? • ロックの個数は可変で環境に合わせた物を選ぶ • 30CPUでは64ロックが最適だったという例↓

54.

メモリ使用率 ____ ) /⌒ ⌒\ ) 空のConcurrentHashmapはどれだけメモリ使うの? /( ●) (●) \ )/⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y / ::::::⌒(__人__)⌒::::: \ | |r┬-| | \ `ー'´ / ノ \ /´ ヽ カ | l l||l 从人 l||l l||l 从人 l||l カ タ ヽ -一''''''"~~``'ー--、 -一'''''''ー-、. タ ヽ ____(⌒)(⌒)⌒) ) (⌒_(⌒)⌒)⌒)) ┌┬┬┐┌┬┬┬┐┌┬┬┬┐┌┬┬┬┐

55.

メモリ使用量 ______ /::::::─三三─\ /:::::::: ( ○)三(○)\ |::::::::::::::::::::(__人__):::: | _____ \::::::::: |r┬-| ,/ .| | ノ:::::::: `ー'´ \ | | 1.7KB

56.

メモリ使用量 ______ /:υ::─ニjjニ─ヾ /:::li|.:( ○)三 (○)\ (:::||!.:υ::::: (__人__)):::: i| ____ 俺はそれを100K個作ったら )::::::::::::: |r┬-| li::::/ | | 170MB持って行かれた /::::::::::::::: `ー ' ::::::ヽ | |

57.

メモリ使用量 • 呪いは大きい • JRuby…大丈夫かな…

58.

Lock-free Hashmap 3種 •Cliff Click – High-scale Lib •Split-Ordered List •日立謹製Lock-free Hashtable

59.

High-Scale lib • そもそもDr.Cliff Clickって誰? – HotSpot JVMの中の人 • 今はベンチャー企業のco-founder – (0xdataという会社で、H2OというHDFS+R言語なソフト作ってる Q.世の中は動的型付けとか関数型とか 話題ですがどの言語が勝つと思います か? CliffClick. ステートマシンだ、ステートマ シンを上手く書ける言語が勝つ。ステー トマシンには本質的にスケーラビリティ がある。 Q.は、はぁ・・・

60.

High-Scale lib • 基本はOpenAddressing • KeyとValueを配列の奇数・偶数に並べることで キャッシュミスを削減 – ひとつのKey Value Pairがひとつのステートマシン • ステートマシンをCASで回して保存・検索・削除 – TombStoneによる墓石地獄は恐らく回避不能 ステートマシン K V K V K V K V K V K V K V V V

61.

そのステートマシンの詳細 • CASを用いて状態遷移する • ・・・?

62.

State MachineでのHashmap • テーブルのExtendは1CASでは終わらないので、 テーブル拡大中というステートを定義する – そのステートを見かけたら他のスレッドも手伝う • 詳しいこと書いてなさ杉で勘弁して欲しい KVKVKVKV T K V K V K V K VK V K V K V V V

63.

High-Scale lib • Javaで実装されててCassandraでも使われてる – J.u.c.ConcurrentHashmapよりは遙かにメモリ効率が良い(た ぶんそれがCassandraでの採用理由 • JVMの中の人が作ったJavaライブラリとか胸熱 • 有志がC言語に移植したバージョンもある。 – もともとGCにべったりな構成なのでメモリ管理回りも実装し直 してて大変そう – Jdybnisさんに感謝!(最近活動を見ないけど • ただしアロケータやハザードポインタまで密結合してるので利用には 注意が必要 • すごいと思うんだけど何故かあまり注目されてない

64.

Split-Ordered Listの前に… • ベースとなっているのがLinear Hashing Litwin[VLDB’80] – その説明から Split=0 Split=1 サイズ4 TS ZK Split=2 サイズ5 TS ZKB サイズ6 T ZKB S リハッシュ B I リハッシュ I I •2^k + Splitのサイズの論理的なハッシュテーブルサイズ •バケットを探す時はSplitと大小比較して適切なバケットを選ぶ •Splitの値をインクリメンタルに増加させる事でExtendにかかるリ ハッシュの負荷を細切れして馴らせる事ができる •遅延がスパイクしにくくなるのでGUIの裏などでよく使われる

65.

Linear Hashing • 一度にリハッシュするバケットはひとつで良いし、リハッシュ結果が 飛んでくるバケットも2つしかない – 4で割り切れる値を8で割ったら、割り切れるか4余るかの2つしかない原理 • もっというと、ハッシュ値の昇順で並べておけばポインタの繋ぎ変 え1回で拡張が済む – ん、それCAS使えばLock-freeにいけるんじゃね?←この発想から発展 サイズ4 Hash(T)%8==0 Hash(B)%8==4 サイズ5 TS ZK TS ZK B B I I 繋ぎ変え1回!

66.

そしてLock-freeへ? ( ^o^)<LinearHashingで拡張は簡単っぽい ( ˘⊖˘)。o(待てよ…ポインタの繋ぎ変えとSplit値のインクリ メントと古いポインタの削除の3つはどう線形化できるん だ?) | 論文| ┗(☋` )┓三調べてみよう ( ◠‿◠ )☛そこに気がつくとは…生かしてはおけぬ······· ▂▅▇█▓▒░(’ω’)░▒▓█▇▅▂うわあああああああああ Concurrentにやるのは まだ自明ではない

67.

Split-Ordered List • 詳しくは冬のLock-free祭りの資料参照 – に、逃げてないもん

68.

閑話休題 • LHlf: lock-free Linear Hashing[Donghui PPoPP’12] – MSのJim Gray Labの研究 – 主なアイデア:Linear Hashingの物理テーブル拡大の重い から2段階の間接参照にすればいいよね • え、それSplit-Ordered Listでもやってるじゃん… – 拡大だけじゃなくて縮退もできるよ! • それはLinear Hashingならそんなに驚くことじゃないよね… – ハザードポインタでメモリ守ってね!必要なメモリは5ポイ ンタね!Pass The Buck使っても良いよ! • 何でそこだけそんな具体的なん? – テーブル・セグメント・バケット・ノードがそれぞれステート マシンを構成しててCASで回すよ! • フルペーパーで詳しく聞かせてもらおうか(今回はPoster Paper)

69.

日立謹製Lock-free hashtable • 2011年に出た論文 – 国内のロックフリー論文でテンション上がった

70.

日立謹製Lock-free hashtable • 日立もデータベース作ってるので多分その部品 • C言語とかで動かすにはGCに頼れないのでオブジェ クトの参照カウンタをスロットに埋め込んだ • あとはCASで何とかしてる(ステートマシンを回す) • 論文の最後に実装コードがまるっと載ってる • ベンチマークがやや胡散臭い – 比較対象が微妙 • Wait-freeの実装パターンについて少し誤解している – 飢餓状態の救援は再帰的である必要は無い – Wait-freeに関してはAlex KoganのPPoPP2012のが面白い • テーブルのExtendについて考察も実装も無い

71.

日立製Lock-free hash • どうせなら木構造してれば「この木何の木Lockfree」っていじれたのに・・・ • テーブル拡張について書いてないの本当に大丈 夫かな・・・

72.

Concurrent Hopscotch Hashing • Hopscotch Hashingの各バケットにロックを付けて concurrentにできるよ – しかも検索はWait-freeにできるよ – え?Extendは全部ロック取るだけだよ • 挿入、削除はLockを取って普通に線形化 Lock アイテム 10100000 A B

73.

Concurrent Hopscotch Hashing • Wait-freeな検索 – ロックを取らずに探索する – 探索の前後でhop情報が書き換わってたらやり直し – やり直し回数がkを超えたら左から右へ全部舐める • 挿入で移動が発生する場合もデータは左から右へ蹴り出される ので左から右へ舐めれば確実 – やり直しk回+左から右への全舐め1回というステップ数上 限が証明可能なのでWait-free Lock アイテム 00 10000 101 A B 失敗したけど もう一回

74.

興味のある分野 • Log-Structured-MergeなHashtable面白そう • Nanahan へのパッチお待ちしております • ConcurrentなHashtableをC++で作るとして欲しい 仕様と可能な妥協の洗い出し手伝ってくれる人 募集中 • Rubyのデータ構造をOpenAddressingにしてみる のは少し楽しそう • そういえばJubatusというOSSがオススメらしいで すよ

75.

Jubatus! • PFIとNTTが一緒に作ってる OSS(LGPL) • オンライン機械学習の数少な いOSS実装 • スパム・年齢・性別推定、線 形回帰、多次元近傍探索、 グラフDBっぽい処理などなど モリモリ追加実装 • 気軽に質問ください! Jubatus 開発チームの一人 @slaさん