LRU とブルームフィルタを作って測る

目標

LRUキャッシュをO(1)で自分で作り、偏ったアクセス記録でFIFOとヒット数を比較し、1回走査するスキャンがキャッシュを汚染する場面を数字で測ります。続いて、ブルームフィルタのサイズを式で選び、固定されたハッシュのルールでフィルタを作って偽陽性率を測ったあと、フィルタをキャッシュの前に置くとDB問い合わせが何回減るかを計算します。

なぜ重要なのか

キャッシュポリシーは「次に何が来るか」についての仮定であり、その仮定がアクセスの形と合うときにだけ、ヒット率が上がります。LRUとFIFOは、getで順序を更新するかどうかの1点だけが違いますが、その1行を忘れたコードは、エラーなしで動きながらヒット数だけが減ります。ブルームフィルタは「確実にない」ことだけを約束する構造なので、偽陰性が1つでも出たら使えないものになり、偽陽性率は分母を間違えると実際よりよく見えます。そのためこのラボの採点ツールは、書いた数字だけを見るのではなく、あなたのクラスと関数を、用意された素材ではない入力で再実行して、基準の実装と突き合わせます。

用意するもの

/opt/fixtures/svccs/lrubloom/の下にあります。読み取り専用で使ってください。すべてのテキストファイルは、1行に1つのキーです。

trace.txt       치우친 분포의 접근 기록 20,000줄
scan.txt        뜨거운 키를 두드리는 1구간 → 한 번씩만 읽는 키가 지나가는 스캔 → 다시 뜨거운 키(3구간)
scan_meta.json  capacity · phase1_len · scan_len · phase3_len · hot_keys(뜨거운 키 목록)
members.txt     블룸 필터에 넣을 '있는 키'
queries.txt     있는 키와 없는 키를 섞은 질의
requests.txt    '이 사용자가 있나' 조회 기록(없는 키가 많고 같은 키가 되풀이된다)
params.json     capacities(4단계 용량 목록) · target_fpr(목표 거짓 양성률) · pipeline_capacity(8단계 용량)

このコードブロックの韓国語の説明は、順に、trace.txtは偏った分布のアクセス記録20,000行、scan.txtはホットなキーを叩く区間1、1回ずつしか読まれないキーが通過するスキャン、再びホットなキーが来る区間3でできていること、scan_meta.jsonにはcapacity・phase1_len・scan_len・phase3_len・hot_keys(ホットなキーのリスト)が入っていること、members.txtはブルームフィルタに入れる存在するキー、queries.txtは存在するキーと存在しないキーを混ぜたクエリ、requests.txtは「このユーザーはいるか」の問い合わせの記録(存在しないキーが多く、同じキーが繰り返される)、params.jsonにはcapacities(ステップ4の容量のリスト)・target_fpr(目標の偽陽性率)・pipeline_capacity(ステップ8の容量)が入っていること、を述べています。

ステップ

1. /root/svccs/lrubloom/trace_stats.jsonに、trace.txtのaccesses(全体の行数)、distinct(異なるキーの数)、top10_share(もっとも多く出てきたキー10個のアクセス数の合計÷全体、小数第4位で丸める)を書きます。
2. /root/svccs/lrubloom/lrubloom.pyにLRUCache(capacity)を作成します。get(key)は値またはNoneを返し、ヒットしたらそのキーをもっとも最近の位置へ移します。put(key, value)は、すでにあるキーなら値を変えてもっとも最近の位置へ移し、個数がcapacityを超えたら、もっとも長く使っていないキーを1つ捨てます。keys()は、長く使っていないものから最近のものの順のリスト、len(cache)は個数です。
3. 同じファイルにrun_trace(policy, capacity, trace)を作成します。policyが"lru"ならLRUCacheを使い、キーごとに、get(key)がNoneでなければヒット、そうでなければミスと数えて、put(key, 1)します。{"hits": 정수, "misses": 정수}を返します(韓国語で「整数」を意味する語です)。採点ツールは、容量40,000と400で12万行の記録を実行して、かかった時間を比較します。get/putがO(1)である必要があります。
4. 同じファイルにFIFOCache(capacity)を作成し(getは順序を変えず、すでにあるキーのputは値だけを変える)、run_traceが"fifo"も受け付けるようにします。params.jsonのcapacitiesごとにtrace.txtを実行し、/root/svccs/lrubloom/hits.jsonに、capacities・lru_hits・fifo_hits・lru_hit_rate・fifo_hit_rate(ヒット÷全アクセス、小数第4位)のリストを書きます。
5. scan.txtを、scan_meta.jsonのcapacityでLRUCacheに、ステップ3と同じルールで流します。区間1の後にキャッシュに残ったホットなキーの数、スキャンの後に残った数、区間3のミスの数、そしてスキャンを除いて区間1 → 区間3だけを流したときの区間3のミスの数を、/root/svccs/lrubloom/scan.jsonに、capacity・hot_resident_before_scan・hot_resident_after_scan・phase3_misses・phase3_misses_without_scanとして書きます。
6. 同じファイルにsizing(n, p)を作成します。m = ceil(n·ln(1/p) / (ln 2)²)、k = max(1, round(m/n·ln 2))、bits_per_key = round(m/n, 2)、expected_fpr = round((1 − e^(−k·n/m))^k, 5)で、{"n","p","m","k","bits_per_key","expected_fpr"}を返します。members.txtの行数とparams.jsonのtarget_fprを使って、/root/svccs/lrubloom/sizing.jsonを作成します。
7. 同じファイルにBloomFilter(m, k)を作成します。メソッドはindexes(key)・add(key)・might_contain(key)・to_bytes()です。ハッシュのルールは、下の「ハッシュのルール」のとおりです。sizing.jsonのmとkを使ってmembers.txtをすべて入れ、queries.txtを問い合わせて、/root/svccs/lrubloom/bloom.jsonに、m・k・queries・true_negatives(存在しないキーのクエリ数)・false_positives・false_negatives・fpr(false_positives÷true_negatives、小数第5位)・bits_set(立っているビットの数)を書きます。
8. 同じファイルにpipeline(members, requests, m, k, capacity)を作成し、その結果を/root/svccs/lrubloom/pipeline.jsonに書きます(requests.txt、sizing.jsonのmとk、params.jsonのpipeline_capacity)。ルールは、下の「問い合わせのルール」のとおりです。

ハッシュのルール

d  = hashlib.sha256(key.encode("utf-8")).digest()
h1 = int.from_bytes(d[0:8], "big")
h2 = int.from_bytes(d[8:16], "big") | 1
i 번째 위치 = (h1 + i*h2) mod m        (i = 0, 1, …, k-1)
비트 j 는 바이트 j // 8 의 (1 << (j % 8)) 자리. to_bytes() 길이는 ceil(m/8)

このコードブロックの韓国語の説明は、順に、i番目の位置は(h1 + i*h2) mod mであり(iは0からk-1まで)、ビットjはバイトj // 8の(1 << (j % 8))の位置にあり、to_bytes()の長さはceil(m/8)であること、を述べています。

問い合わせのルール

LRU 만:   키마다 cache.get(key) 가 None 이면 DB 조회 +1, cache.put(key, key 가 members 에 있나)
          (없는 키도 False 로 캐시된다 — 부정 캐시)
블룸+LRU: 필터가 '없다' 면 아무것도 안 한다. 아니면 위와 같고, 그 DB 조회가 없는 키였으면
          db_calls_false_positive +1
돌려줄 것: requests, db_calls_lru_only, db_calls_with_bloom,
          db_calls_saved(= lru_only − with_bloom), db_calls_false_positive

このコードブロックの韓国語の説明は、順に、LRUのみの場合は、キーごとにcache.getがNoneならDB問い合わせを1増やしてcache.put(key, keyがmembersにあるか)を行うこと(存在しないキーもFalseとしてキャッシュされ、これが否定キャッシュであること)、ブルーム+LRUの場合は、フィルタが「ない」と言えば何もせず、そうでなければ上と同じで、そのDB問い合わせが存在しないキーだったらdb_calls_false_positiveを1増やすこと、返す値はrequests、db_calls_lru_only、db_calls_with_bloom、db_calls_saved(= lru_only − with_bloom)、db_calls_false_positiveであること、を述べています。

参考

• 採点ツールはlrubloom.pyを読み込みます。ファイルを読んで結果を作るコードは、if __name__ == "__main__":の下か、別のスクリプトに置いてください。
• OrderedDict.move_to_end(key)とpopitem(last=False)を使うと、LRUを短く書けます。リスト(list)のremoveで順序を管理すると、ステップ3の時間の検査で不合格になります。
• よくある間違い: getで順序を更新しないLRU(事実上のFIFO)、あふれたときに今入れたキーを捨てること、偽陽性率を全クエリ数で割ること。
• 出力物はセッションが終わると消えます。必要なら別に保管してください。

アクセス記録がどれだけ偏っているか

trace.txtの全体の行数・異なるキーの数・上位10個のキーのシェアを、/root/svccs/lrubloom/trace_stats.jsonにaccesses・distinct・top10_shareとして書いてください。

collections.Counterのmost_common(10)が上位10個を返します。top10_shareは、そのアクセス数の合計を全体の行数で割った値です。分布が偏っているほど、小さなキャッシュでもヒットが多く出ます。

LRUキャッシュを作る

/root/svccs/lrubloom/lrubloom.pyにLRUCache(capacity)を作成してください。get・put・keys・lenを持ちます。採点ツールがクラスを読み込み、ランダムな操作数千件で基準の実装と突き合わせます。

LRUは、getのヒットも「最近の使用」として扱います。OrderedDictなら、move_to_end(key)で末尾へ移し、あふれたらpopitem(last=False)で先頭を捨てます。keys()は先頭(もっとも長く使っていないもの)から並べます。

run_traceとO(1)の確認

lrubloom.pyにrun_trace(policy, capacity, trace)を作成し、{"hits", "misses"}を返してください。採点ツールが、変形した記録でヒット数を突き合わせ、容量400と40,000で12万行を実行した時間を比較します。

ヒットは、getがNoneでないときで、ミスならput(key, 1)します。容量を100倍にしたのに時間が数倍に増えるなら、どこかにリストを走査する操作(list.remove、pop(0)、min)があるということです。

FIFOとヒット数の比較

lrubloom.pyにFIFOCacheを作成し、run_traceが"fifo"も受け付けるようにしてください。params.jsonのcapacitiesごとにtrace.txtを実行し、/root/svccs/lrubloom/hits.jsonにcapacities・lru_hits・fifo_hits・lru_hit_rate・fifo_hit_rateを書いてください。

FIFOは、入ってきた順序だけで捨てます。getと、すでにあるキーのputは、順序を変えません。同じ容量でLRUのヒットがFIFOより多くないなら、LRUのgetをもう一度見直してください。

1回走査するスキャンがキャッシュを汚染する

scan.txtをscan_meta.jsonのcapacityでLRUCacheに流して、/root/svccs/lrubloom/scan.jsonにcapacity・hot_resident_before_scan・hot_resident_after_scan・phase3_misses・phase3_misses_without_scanを書いてください。

区間の境界は、phase1_lenとscan_lenで区切ります。スキャンの後に生き残ったホットなキーも、区間3で再び呼ばれたキーが入ってくるときに押し出されることがあるため、ミスの数は「押し出された個数」より大きくなることがあります。スキャンを除く場合は、新しいキャッシュで、区間1と区間3だけを流します。

nとpからmとkを選ぶ

lrubloom.pyにsizing(n, p)を作成し、members.txtの行数とparams.jsonのtarget_fprを使って、/root/svccs/lrubloom/sizing.jsonを作成してください。採点ツールは、別のnとpでもsizingを呼び出します。

対数の底を確認してください。log2(1/p) / ln 2は、ln(1/p) / (ln 2)²と同じです。math.logは自然対数です。kは、丸めた後に1より小さければ1にします。

ブルームフィルタと偽陽性率

lrubloom.pyに、ハッシュのルールどおりBloomFilter(m, k)を作成してください。sizing.jsonのmとkを使ってmembers.txtを入れ、queries.txtを問い合わせて、/root/svccs/lrubloom/bloom.jsonを書いてください。採点ツールは、別のキーの集合でフィルタを作り、ビット配列をバイト単位で突き合わせます。

入れたキーにmight_containがFalseを返すなら、偽陰性です。addとmight_containが同じindexesを使っているかを確認してください。h2に| 1を付け忘れたり、バイト順をlittleにしたりすると、ビット配列が変わります。fprの分母は、存在しないキーのクエリ数です。

ブルームフィルタが節約したDB問い合わせ

lrubloom.pyに、問い合わせのルールどおりpipeline(members, requests, m, k, capacity)を作成し、requests.txt・sizing.json・pipeline_capacityを使って、/root/svccs/lrubloom/pipeline.jsonを作成してください。採点ツールは、別のキーの集合と問い合わせの記録でも、pipelineを呼び出します。

LRUだけの場合は、存在しないキーもFalseとしてキャッシュされます。ブルーム+LRUでは、フィルタが「ない」と判断したリクエストはキャッシュにも入れないので、キャッシュの場所が、存在するキーにより多く回ります。減ったDB問い合わせは、除外されたリクエスト数とは等しくありません。