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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

少し脱線 • 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

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

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

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

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

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

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

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

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

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

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

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

挿入 • 見つけたら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

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

おいCuckoo…

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

• http://github.com/kumagi/nanahan

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

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

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

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

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

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

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

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

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

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

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

メモリ使用率 ＿＿＿_ ） ／⌒ ⌒＼ ) 空のConcurrentHashmapはどれだけメモリ使うの？ ／（ ●） （●） ＼ )／⌒Y⌒Y⌒Ｙ⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Ｙ⌒Y⌒Y ／ ::::::⌒（__人__）⌒::::: ＼ | |r┬-| | ＼ `ー'´ ／ ノ ＼ ／´ ヽ カ | ｌ l||l 从人 l||l l||l 从人 l||l カ タ ヽ -一''''''"~~｀`'ー--､ -一'''''''ー-､. タ ヽ ＿＿＿＿(⌒)(⌒)⌒) ) (⌒＿(⌒)⌒)⌒)) ┌┬┬┐┌┬┬┬┐┌┬┬┬┐┌┬┬┬┐

メモリ使用量 ＿＿＿＿__ ／::::::─三三─＼ ／:::::::: （ ○）三（○）＼ |::::::::::::::::::::（__人__）:::: | ＿＿＿＿＿ ＼::::::::: |r┬-| ,／ .| | ノ:::::::: `ー'´ ＼ | | 1.7KB

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

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

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

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

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

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

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

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

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の裏などでよく使われる

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回！

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

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

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

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

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

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

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

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

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

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