Build and Measure an LRU and a Bloom Filter

Goal

You will build an LRU cache in O(1) yourself, compare its hit count with FIFO on a skewed access trace, and measure with numbers how a one-pass scan pollutes the cache. Then you will choose the size of a Bloom filter with a formula, build the filter with a pinned hash rule and measure its false positive rate, and then calculate how many DB lookups are saved when the filter is placed in front of the cache.

Why it matters

A cache policy is an assumption about "what comes next," and the hit rate goes up only when that assumption matches the access shape. LRU and FIFO differ in just one thing, whether get updates the order, and code that forgets that one line runs without errors while only the hit count drops. A Bloom filter is a structure that promises only "definitely not present," so if even one false negative appears it becomes unusable, and if you take the wrong denominator, the false positive rate looks better than it really is. So the grader of this lab does not look only at the numbers you wrote; it runs your classes and functions again on inputs that are not the materials and compares them with the reference implementation.

Materials

They are under /opt/fixtures/svccs/lrubloom/. Only read them. Every text file has one key per line.

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

Steps

1. In /root/svccs/lrubloom/trace_stats.json, write the following for trace.txt: accesses (the total number of lines), distinct (the number of distinct keys), and top10_share (the sum of the access counts of the 10 most frequent keys ÷ the total, rounded to four decimal places).
2. In /root/svccs/lrubloom/lrubloom.py, create LRUCache(capacity). get(key) returns the value or None, and on a hit it moves that key to the most recent position. put(key, value) updates the value and moves it to the most recent position if the key exists, and if the count exceeds capacity it discards the one least recently used key. keys() is a list ordered from least recently used to most recent, and len(cache) is the count.
3. In the same file, create run_trace(policy, capacity, trace). If policy is "lru", use an LRUCache; for each key, count it as a hit if get(key) is not None and otherwise as a miss, and then put(key, 1). It returns {"hits": 정수, "misses": 정수} (both values are integers). The grader runs a 120,000-line trace at capacities 40,000 and 400 and compares the elapsed times; get/put must be O(1).
4. In the same file, create FIFOCache(capacity) (get does not change the order, and put on an existing key changes only the value) and make run_trace accept "fifo" too. For each capacity listed in params.json under capacities, run trace.txt, and in /root/svccs/lrubloom/hits.json write the lists capacities·lru_hits·fifo_hits·lru_hit_rate·fifo_hit_rate (hits ÷ total accesses, to four decimal places).
5. Stream scan.txt into an LRUCache with the capacity from scan_meta.json, using the same rules as step 3. Record the number of hot keys remaining in the cache after phase 1, the number remaining after the scan, the number of misses in phase 3, and the number of misses in phase 3 when you stream only phase 1 → phase 3 without the scan, in /root/svccs/lrubloom/scan.json as capacity·hot_resident_before_scan·hot_resident_after_scan·phase3_misses·phase3_misses_without_scan.
6. In the same file, create sizing(n, p). It computes m = ceil(n·ln(1/p) / (ln 2)²), k = max(1, round(m/n·ln 2)), bits_per_key = round(m/n, 2), and expected_fpr = round((1 − e^(−k·n/m))^k, 5), and returns {"n","p","m","k","bits_per_key","expected_fpr"}. From the number of lines in members.txt and the value that params.json holds under target_fpr, build /root/svccs/lrubloom/sizing.json.
7. In the same file, create BloomFilter(m, k). The methods are indexes(key)·add(key)·might_contain(key)·to_bytes(). The hash rule is exactly the "Hash rule" below. With the m and k from sizing.json, add all of members.txt, query queries.txt, and in /root/svccs/lrubloom/bloom.json write m·k·queries·true_negatives (the number of queries for absent keys)·false_positives·false_negatives·fpr (false_positives ÷ true_negatives, to five decimal places)·bits_set (the number of bits turned on).
8. In the same file, create pipeline(members, requests, m, k, capacity), and write its result to /root/svccs/lrubloom/pipeline.json (using requests.txt, the m·k of sizing.json, and, from params.json, the pipeline_capacity value). The rule is exactly the "Lookup rule" below.

Hash rule

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)

Lookup rule

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

Notes

• The grader imports lrubloom.py. Put code that reads files and produces results under if __name__ == "__main__": or in a separate script.
• You can write LRU briefly with OrderedDict.move_to_end(key) and popitem(last=False). If you manage the order with the remove of a list, you will fail the time check in step 3.
• Common mistakes: an LRU that does not update the order in get (effectively a FIFO), discarding the key you just inserted on overflow, and dividing the false positive rate by the total number of queries.
• The outputs disappear when the session ends. Keep them elsewhere if you need them.

How skewed is the access trace

Write the total number of lines in trace.txt, the number of distinct keys, and the share of the top 10 keys to /root/svccs/lrubloom/trace_stats.json as accesses, distinct, and top10_share.

most_common(10) of collections.Counter gives the top 10. top10_share is the sum of their access counts divided by the total number of lines. The more skewed the distribution, the more hits even a small cache gets.

Build an LRU cache

Create LRUCache(capacity) in /root/svccs/lrubloom/lrubloom.py: get, put, keys, len. The grader imports the class and compares it with the reference implementation over thousands of random operations.

LRU counts a get hit as "recent use" too. With an OrderedDict, move it to the end with move_to_end(key), and on overflow discard the front with popitem(last=False). keys() starts from the front (the least recently used).

run_trace and checking O(1)

Create run_trace(policy, capacity, trace) in lrubloom.py and return {"hits", "misses"}. The grader compares the hit counts on variant traces and compares the time of running 120,000 lines at capacities 400 and 40,000.

A hit is when get is not None, and on a miss you put(key, 1). If you raise the capacity 100 times and the time grows by some multiple, there is an operation somewhere that scans a list (list.remove, pop(0), min).

Compare hit counts with FIFO

Create FIFOCache in lrubloom.py and make run_trace accept "fifo" too. For each capacity in params.json, run trace.txt and write capacities, lru_hits, fifo_hits, lru_hit_rate, and fifo_hit_rate to /root/svccs/lrubloom/hits.json.

FIFO discards only by order of arrival: get and put on an existing key do not change the order. If LRU hits are not greater than FIFO at the same capacity, look at the get of your LRU again.

A one-pass scan pollutes the cache

Stream scan.txt into an LRUCache with the capacity from scan_meta.json, and write capacity, hot_resident_before_scan, hot_resident_after_scan, phase3_misses, and phase3_misses_without_scan to /root/svccs/lrubloom/scan.json.

Cut the phase boundaries with phase1_len and scan_len. The hot keys that survived the scan can also be pushed out when keys called again in phase 3 come in, so the miss count can be greater than the "number pushed out." For the case without the scan, stream only phases 1 and 3 into a fresh cache.

Choose m and k from n and p

Create sizing(n, p) in lrubloom.py, and build /root/svccs/lrubloom/sizing.json from the number of lines in members.txt and target_fpr in params.json. The grader calls sizing with other n and p as well.

Check the base of the logarithm. log2(1/p) / ln 2 equals ln(1/p) / (ln 2)². math.log is the natural logarithm. k is 1 if it is less than 1 after rounding.

The Bloom filter and its false positive rate

Create BloomFilter(m, k) in lrubloom.py following the hash rule. Add members.txt with the m and k from sizing.json, query queries.txt, and write /root/svccs/lrubloom/bloom.json. The grader builds filters from other key sets and compares the bit arrays byte by byte.

If might_contain returns False for a key you added, that is a false negative; check that add and might_contain use the same indexes. If you forget | 1 on h2 or use little byte order, the bit array differs. The denominator of fpr is the number of queries for absent keys.

The DB lookups the Bloom filter saved

Create pipeline(members, requests, m, k, capacity) in lrubloom.py following the lookup rule, and build /root/svccs/lrubloom/pipeline.json from requests.txt, sizing.json, and pipeline_capacity. The grader calls pipeline with other key sets and request logs as well.

With LRU only, absent keys are cached as False too. With Bloom+LRU, requests the filter says are "not present" are not put into the cache either, so more cache space goes to keys that belong there; the reduction in DB lookups is not the same as the number of filtered requests.