kumagi 読書リスト - 昏論会ウィキ - atwiki（アットウィキ）

Fast Hash Table Lookup Using Extended Bloom Filter: An Aid to Network Processing

読む理由：高速ハッシュテーブルと言われたら読まないわけには

ハッシュテーブルの出来の良し悪しでルーティング速度が大きく変わる。 embedded memory technologyという不穏な文字が見える。コネクションのステート管理にも便利。パケットの分類にも使うよ→僕にはどうでもいい MD5やsha-1は高速に計算できない。 -- kumagi (2011-03-06 14:31:08)
既に入ってるアイテム群に基づいて新しいハッシュ関数を手に入れる方法が提案されている。もちろん新しいハッシュ関数にすげ替えるときはアイテム全部再配置する必要がある。[25,20] ハッシュ関数を複数用意して、衝突したらもう片方を使う手法もある。[6]ハッシュテーブルとハッシュ関数の複数ペアを用いて、衝突したらもう片方に保存するという手法。それぞれのテーブル操作がパラレルに行えて、それぞれのテーブルサイズを縮小できる。 -- kumagi (2011-03-06 14:31:19)
d-random schemeというモノもあって、一つのテーブルに複数のハッシュ関数を用意し、それぞれの複数ハッシュ関数で計算したのち一番空いてるバケットに放り込む。[3] 亜種でd-leftなんてのもIPルックアップに使う。[27]の2-leftを一般化したモノで、パケットをd個に分割してそれぞれをハッシュし、一番空いてるバケットを使う。（複数候補があったら一番左の物）d-randomより速いらしい。 -- kumagi (2011-03-06 14:31:27)
この論文の手法も大まかにこれらに似ては居るが、大きな違いは検索時に複数のバケットをほじくり返さないことだ（な、なんだってー！？）別チップなメモリに置いた複数のバケットを探索する代わりにcounting bloom filterを参照する。 -- kumagi (2011-03-06 14:31:39)
bloom filterをキャッシュに乗せておけば存在の有無だけは高速に分かるが、検索速度は未だ予測不能だ。しかし我々の方法では拡張bloom filterから得られる情報を最大限利用して完全一致の検索性能を向上させる。(マジっすか -- kumagi (2011-03-06 14:31:56)
Basic Fast Hash Table(BFHT)という簡単な物を定義して、そこを叩き上げていく形で説明する。ハッシュ関数をk個用意して、n個挿入されたらn*k個挿入される。一つのアイテムがk個にレプリケーションされて見るからに効率悪そう。各バケットに入ってる量をカウントしてて、検索時は全部のビットが0で無いことをチェック。これは基本的なbloom filterの挙動ですね。何が嬉しいかっていうとcounting bloom filter程度ならチップに載るからoff-chipなアクセスを削減できること。見れば見るほど組み込み系っぽいお話。 -- kumagi (2011-03-06 17:10:45)
counting bloom filterを使うのは、ハッシュテーブルを手繰るときにchainが短ければ短いほど良いのでカウント値が一番低いものを探せば少ないオフチップアクセス(=最短のチェイン)で目標に辿りつけるからだ。カウント値が一緒だったらアドレスが小さいほうを選ぶ（オンチップなキャッシュでcounting bloom filterをどうにかすると言っても、頻繁にコヒーレンスを取らせる事になるので微妙だ。でもメモリアクセスよりは遥かに速いのか。） -- kumagi (2011-03-06 17:11:00)
削除はカウンタのデクリメントと、全部のリストからの消去を行う。で、この方法だと最短チェイン内以外でのリストは永久にアクセスされなくて無駄なので、それを刈り込んだPruned Fast Hash Table(PFHT)を提案する。これは無駄なチェイン要素の枝刈を行う物だが、ポイントとしては枝刈によってチェインが短くなってもカウンタを一切減らさない事だ。よってカウンタは通常実際のチェイン長より大きくなるが、カウンタが一番小さいところを探索すれば良いので見つからないということは起こりえない。 -- kumagi (2011-03-06 17:11:13)
そしてこの方法の欠点は、一度枝狩りを行ったらそこに追加で要素を加えるのが難しくなることだ。追加や削除を行うと、カウンタを増減せざるを得ないので、どの最小カウンタにチェインを繋げるかを再びフロムスクラッチで再構成する必要がある。それだと効率が悪すぎるので一個インサートするたびにインクリメントした全部のカウンタのあるバケットを全部再計算する事になる。再計算とは言ってもカウンタ値は加算した後据え置きで良い点に注意。 -- kumagi (2011-03-06 17:11:28)
そして鬼門なのは削除の方でカウンタが1減るとそっちが最小になるアイテムがどれなのか網羅する方法は無い、つまり本当にフロムスクラッチで計算しなおす必要があって、ルーターはオフラインのBFHTっぽい物を維持することになる。これの実装はなんか複雑なので読み飛ばす。面白いのは「バケットが偏った場合に、そこのカウンタの値をわざと増やしてリバランスを行う」事により、検索側にも迷惑をかけずに平均チェイン長を1に近づけられること。 -- kumagi (2011-03-06 17:11:42)
削除が低速で高コスト過ぎるので、PFHTよりずっと低コストでありながらBFHTよりずっと高メモリ効率なSFHTを提案する（これ本題！） -- kumagi (2011-03-06 17:11:54)
shared fast hash tableの略で、複数のバケットが同一のポインタを指すという画期的な形してる。 -- kumagi (2011-03-06 17:12:40)
複数のバケットが同一のノードを指すようにし、新しく挿入するときはターゲットとなる全部のバケットの最後尾のポインタが新ノードを指すようにしてやる事で、少ないメモリ消費で削除の効率を高める事ができる。PFHTよりは遅いが削除コストが劇的に減ってるところがポイント。 -- kumagi (2011-03-06 18:07:00)
どこかのバケットから、カウンタと同じ回数までのイタレーションによって削除はできるのだから、バケットごとにbloom filterのカウント値までの間イタレーションを行って存在しなかったら諦める。（←この方法の削除だと、他の人から見てイタレーションでsegmentaiton faultする大惨事になるんじゃ…。 -- kumagi (2011-03-06 18:07:16)
ともかく削除コストはPFHTより遥かに軽くなった。 -- kumagi (2011-03-06 18:07:33)
削除は多重に冗長化されたチェインが途切れるだけなので、到達可能性は阻害されないようだ。でも、削除後のポインタをnullにする事をしなくても、countingの数を上限としてイタレーションするので、大丈夫っぽい雰囲気。 -- kumagi (2011-03-06 18:57:06)
挿入するときにカウンタ値よりもリスト長が長くなった場合、先頭にprependする事で一貫性を保つ。その場合、同一のアイテムが複数個出来ることになる。削除するときはチェイン長に関わらずリストの全体から対象物を削除する必要がある。 -- kumagi (2011-03-06 18:57:17)
（C++的には、全バケットをスキャンしながらdelete対象のリストを作成して、バケットから到達不能な所にリストを構成して、スキャン完了後に全部deleteする形にしたほうがよさそう。リストから抜き出す処理はいつだって鬼門） -- kumagi (2011-03-06 18:57:27)

Towards a Scalable Non-Blocking Coding Style（論文ではない

読む理由：ステートマシン万能説を唱える彼の頭の中を少しでも知りたい！

non blockingとは？→単一のスレッドを止めることが全体の進行を妨げないこと。砕けた表現するとロック使うなよ！って話 x86でも8コア、SunのRockなら64コア,Azulの768なら768コア(!?)アムダールの法則により、これからもLockの立場は危うくなり続けることだろう。 -- kumagi (2011-03-06 20:13:54)
読み出し性能はガンガンスケールするが、書き出しの場合は書込みごとに1キャッシュミスか1メモリバスの速度に律速される。複数のCPUが同じ場所に書きこむ事を辞めさせたほうがいい。カウンタの共有や単一ロックは原則禁止。R/Wロックは高速そうに見えて100CPU以上だと窒息する（もう100CPUあれば良くないか…？） -- kumagi (2011-03-06 20:14:08)
必要なのは全体の情報を保存するarrayと、FSM、そしてアルゴリズムを複数のFSMステップから構成する事だ。CASの失敗は値の更新を意味し、つまり全体の進行を意味する。じゃあその配列はどれだけ大きければいいのか→答えは無い。というか配列は成長する前提で配列こそStateMachineで管理するべき（うわぁGCが必要そう…） -- kumagi (2011-03-06 20:14:19)
BitVector（std::vector<bool>のような物）を例に挙げる。コピー時にヘルパスレッドが立ち上がる（！？） HashTableへの応用を考える。キーとバリューはどちらもnullで始まり、偶数番目のスロットにはkey,奇数番目にはvalueが入る。valueは時々「墓標」の役割も果たす。 -- kumagi (2011-03-06 20:14:28)
Azulの768CPU環境では線形スケールした。10million/s以上の更新頻度下で1billionのread/secを達成した。ソースコードはHigh-scale-lib参照。 -- kumagi (2011-03-06 20:14:39)
なるほど。わからん。 -- kumagi (2011-03-06 20:22:24)
Nearly FIFOにも使える。複数の短いQueueを用意しておいて、その中からランダムに使う。満タンもしくは空っぽで有るかどうかを調べるには全部をスキャンする必要があるが、忙しい時のcontentionが劇的に減るのでオススメ。これはlockしててもいい。StripeQueueと呼ぶ。 -- kumagi (2011-03-06 20:22:37)
まだ実装中なのでご期待あれ、きっとスケールするよ:) -- kumagi (2011-03-06 20:22:54)