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

한국어 원문으로 표시합니다.

목표

LRU 캐시를 O(1) 로 직접 만들어 치우친 접근 기록에서 FIFO 와 적중 수를 비교하고, 한 번 훑는 스캔이 캐시를 오염시키는 장면을 숫자로 잽니다. 이어서 블룸 필터의 크기를 식으로 고르고, 못박은 해시 규칙으로 필터를 만들어 거짓 양성률을 잰 뒤, 필터를 캐시 앞에 두면 DB 조회가 몇 번 줄어드는지 계산합니다.

왜 중요한가

캐시 정책은 '다음에 무엇이 올까' 에 대한 가정이고, 그 가정이 접근 모양과 맞을 때만 적중률이 오릅니다. 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 를 돌려 /root/svccs/lrubloom/hits.json 에 capacities·lru_hits·fifo_hits·lru_hit_rate·fifo_hit_rate(적중 ÷ 전체 접근, 넷째 자리) 목록을 적습니다.
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 으로 적습니다.
같은 파일에 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 를 물어 /root/svccs/lrubloom/bloom.json 에 m·k·queries·true_negatives(없는 키 질의 수)·false_positives·false_negatives·fpr(false_positives ÷ true_negatives, 다섯째 자리)·bits_set(켜진 비트 수)을 적습니다.
같은 파일에 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개 키의 몫을 /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 을 다시 보세요.

한 번 훑는 스캔이 캐시를 오염시킨다

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 조회는 걸러진 요청 수와 같지 않습니다.