实现并测量 LRU 与布隆过滤器

目标

亲手以 O(1) 实现 LRU 缓存，在偏斜的访问记录上与 FIFO 比较命中数，并用数字测出一次性扫描污染缓存的情形。接着用公式选定布隆过滤器的大小，按规定好的哈希规则构建过滤器并测出假阳性率，再计算把过滤器放在缓存前面，数据库查询能少几次。

为什么重要

缓存策略是对“接下来会来什么”的假设，只有当这个假设与访问模式相符时，命中率才会提高。LRU 与 FIFO 只有一点不同，就是 get 时是否更新顺序，而漏掉这一行的代码会毫无报错地运行，只是命中数变少。布隆过滤器是只承诺“一定没有”的结构，所以只要出现一次假阴性，它就成了不能用的东西；而假阳性率如果分母取错，会比实际看起来更好。因此本实验的评分器不只看你写下的数字，而是把你的类和函数放到不在材料里的输入上重新运行，与参考实现对照。

材料

位于 /opt/fixtures/svccs/lrubloom/ 之下。只读取，不要修改。所有文本文件都是每行一个键。

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단계 용량)

步骤

在 /root/svccs/lrubloom/trace_stats.json 中写入 trace.txt 的 accesses（总行数）、distinct（互不相同的键数）、top10_share（出现次数最多的 10 个键的访问数之和 ÷ 总数，四舍五入到小数点后四位）。
在 /root/svccs/lrubloom/lrubloom.py 中编写 LRUCache(capacity)。get(key) 返回值或 None，命中时把该键移到最近的位置。put(key, value) 对已有的键更新值并移到最近，当个数超过 capacity 时丢弃最久没用的一个键。keys() 返回按从最久没用到最近的顺序排列的列表，len(cache) 是个数。
在同一个文件里编写 run_trace(policy, capacity, trace)。当 policy 为 "lru" 时使用 LRUCache，对每个键，如果 get(key) 不是 None 就计为命中，否则计为未命中，并执行 put(key, 1)。返回 {"hits": 정수, "misses": 정수}（占位符均为整数）。评分器会在容量 40,000 和 400 下运行 12 万行的记录，并比较耗时——get/put 必须是 O(1)。
在同一个文件里编写 FIFOCache(capacity)（get 不改变顺序，对已有键的 put 只改变值），并让 run_trace 也能接收 "fifo"。对 params.json 的 capacities 中的每个容量运行 trace.txt，把 capacities、lru_hits、fifo_hits、lru_hit_rate、fifo_hit_rate（命中 ÷ 全部访问，保留四位小数）的列表写入 /root/svccs/lrubloom/hits.json。
把 scan.txt 按与第 3 步相同的规则，用 scan_meta.json 的 capacity 送入 LRUCache。把第 1 阶段之后缓存中残留的热点键数、扫描之后残留的数量、第 3 阶段的未命中数，以及去掉扫描、只送入第 1 阶段 → 第 3 阶段时第 3 阶段的未命中数，分别以 capacity、hot_resident_before_scan、hot_resident_after_scan、phase3_misses、phase3_misses_without_scan 写入 /root/svccs/lrubloom/scan.json。
在同一个文件里编写 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。
在同一个文件里编写 BloomFilter(m, k)。方法有 indexes(key)、add(key)、might_contain(key)、to_bytes()。哈希规则完全按下面的“哈希规则”。用 sizing.json 的 m、k 把 members.txt 全部加入，再查询 queries.txt，把 m、k、queries、true_negatives（不存在的键的查询数）、false_positives、false_negatives、fpr（false_positives ÷ true_negatives，保留五位小数）、bits_set（被置位的比特数）写入 /root/svccs/lrubloom/bloom.json。
在同一个文件里编写 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)

查询规则

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

参考

评分器会导入 lrubloom.py。读取文件并生成结果的代码，请放在 if __name__ == "__main__": 之下或单独的脚本里。
用 OrderedDict.move_to_end(key) 和 popitem(last=False) 可以把 LRU 写得很短。如果用列表（list）的 remove 来管理顺序，就会在第 3 步的时间检查中不合格。
常见错误：get 时不更新顺序的 LRU（实际上是 FIFO）；溢出时把刚放进去的键丢掉；把假阳性率除以总查询数。
产出会在会话结束后消失。需要的话请另行保存。

访问记录偏斜到什么程度

把 trace.txt 的总行数、互不相同的键数、前 10 个键所占的份额，以 accesses、distinct、top10_share 的形式写入 /root/svccs/lrubloom/trace_stats.json。

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，把 capacities、lru_hits、fifo_hits、lru_hit_rate、fifo_hit_rate 写入 /root/svccs/lrubloom/hits.json。

FIFO 只按进入的顺序丢弃——get 以及对已有键的 put 都不改变顺序。如果同样容量下 LRU 的命中不比 FIFO 多，请重新检查 LRU 的 get。

一次性扫描会污染缓存

把 scan.txt 按 scan_meta.json 的 capacity 送入 LRUCache，把 capacity、hot_resident_before_scan、hot_resident_after_scan、phase3_misses、phase3_misses_without_scan 写入 /root/svccs/lrubloom/scan.json。

阶段边界按 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 的分母是不存在的键的查询数。

布隆过滤器省下的数据库查询

在 lrubloom.py 中按查询规则编写 pipeline(members, requests, m, k, capacity)，并用 requests.txt、sizing.json、pipeline_capacity 生成 /root/svccs/lrubloom/pipeline.json。评分器还会用别的键集合和查询记录来调用 pipeline。

只有 LRU 时，不存在的键也会以 False 缓存下来。在布隆+LRU 中，过滤器判定“没有”的请求也不会放进缓存，所以有缓存位置的键能分到更多——减少的数据库查询数，并不等于被过滤掉的请求数。