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

+31

No comments posted yet

Comments

Slide 1

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

Slide 2

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

Slide 3

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

Slide 4

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

Slide 5

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

Slide 6

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

Slide 7

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

Slide 8

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

Slide 9

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

Slide 10

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

Slide 11

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

Slide 12

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

Slide 13

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

Slide 14

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

Slide 15

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

Slide 16

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

Slide 17

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

Slide 18

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

Slide 19

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

Slide 20

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

Slide 21

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

Slide 22

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

Slide 23

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

Slide 24

閑話休題 身近な実装はどうなっているのか?

Slide 25

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

Slide 26

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

Slide 27

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

Slide 28

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

Slide 29

どれが良いのよ? 検索コストが簡単に見積もれてキャッシュミスが少なくてメモリに無駄が少なくて整理が要らなくて挿入コストを調整できるハッシュ無いかなー?

Slide 30

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

Slide 31

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

Slide 32

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

Slide 33

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

Slide 34

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

Slide 35

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

Slide 36

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

Slide 37

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

Slide 38

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

Slide 39

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

Slide 40

おいCuckoo…

Slide 41

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

Slide 42

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

Slide 43

比較 それぞれの弱点を補った感じ

Slide 44

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

Slide 45

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

Slide 46

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

Slide 47

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

Slide 48

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

Slide 49

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

Slide 50

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

Slide 51

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

Slide 52

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

Slide 53

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

Slide 54

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

Slide 55

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

Slide 56

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

Slide 57

さぁみんなお待ちかねLock-free Lock-free Hashmap 3種 Cliff Click – High-scale Lib Split-Ordered List 日立謹製Lock-free Hashtable

Slide 58

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

Slide 59

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

Slide 60

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

Slide 61

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

Slide 62

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

Slide 63

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

Slide 64

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

Slide 65

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

Slide 66

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

Slide 67

閑話休題 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)

Slide 68

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

Slide 69

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

Slide 70

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

Slide 71

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

Summary: ハッシュテーブルについて簡単なサーベイ発表

Tags: hashtable datastructure concurrent algorithm

URL: