LRU Trusts Recency; a Bloom Filter Is Only Sure About 'No'

한 줄 요약

캐시는 '곧 다시 쓸 것' 을 맞히는 내기이고, LRU 는 "방금 쓴 것을 곧 또 쓴다" 에 겁니다. 블룸 필터는 반대로 "확실히 없다" 만 약속하는 대신 아주 적은 비트로 집합을 들고 다닙니다. 둘 다 무엇을 믿는 구조인지 알고 써야 숫자가 기대대로 나옵니다.

왜 이게 필요했나

느린 저장소 앞에 빠른 저장소를 두는 순간 질문이 두 개 생깁니다. 자리가 모자라면 무엇을 버리나. 그리고 애초에 없는 것을 찾으러 느린 쪽까지 가야 하나.

첫 질문의 교과서 답이 LRU(least recently used)입니다. functools.lru_cache 문서는 LRU 캐시가 "가장 최근 호출이 다가올 호출을 가장 잘 예측할 때" 가장 잘 동작한다고 적고, 날마다 바뀌는 뉴스 서버의 인기 기사를 예로 듭니다. 거꾸로 말하면 그 가정이 깨지는 접근 — 전체 키를 한 번 훑는 배치나 백필 — 에서는 LRU 가 두 번 다시 안 올 키를 '가장 최근' 으로 모시느라 정작 자주 쓰는 키를 내보냅니다. Cache replacement policies 항목은 이것을 cache pollution 이라고 부릅니다.

두 번째 질문이 블룸 필터의 자리입니다. 가입 여부 확인, 이미 본 URL 거르기, 없는 키로 두드리는 봇 요청처럼 답이 대부분 "없다" 인 조회는 음성 결과까지 캐시에 넣어도 키 공간이 넓으면 금방 밀려납니다. Broder·Mitzenmacher 의 서베이 Network Applications of Bloom Filters: A Survey(Internet Mathematics 1권 4호)는 이것을 '블룸 필터 원칙' 으로 정리합니다 — 목록이나 집합을 쓰는데 공간이 귀하고, 거짓 양성의 영향을 줄일 수 있다면 블룸 필터를 고려하라.

어떻게 동작하나

LRU 를 O(1) 로. 필요한 연산은 셋입니다. 키로 찾기, '방금 썼다' 로 표시하기, 가장 오래 안 쓴 것 버리기. 해시 테이블이 첫째를, 이중 연결 리스트가 나머지 둘을 상수 시간에 합니다(노드를 떼어 맨 뒤에 붙이고, 맨 앞을 떼어 냅니다). 파이썬에서는 OrderedDict 가 이 조합을 이미 갖고 있습니다. 문서는 OrderedDict 가 재정렬 연산에 강하도록 설계되어 여러 종류의 LRU 캐시를 만들기에 알맞다고 적고, move_to_end(key)(없는 키면 KeyError)와 popitem(last=False)(FIFO 순서로 꺼냄)를 줍니다.

연산	LRU	FIFO
get 적중	맨 뒤(가장 최근)로 옮긴다	그대로 둔다
있는 키에 put	값 갱신 + 맨 뒤로	값만 갱신
넘쳤을 때	맨 앞(가장 오래 안 쓴 것) 제거	맨 앞(가장 먼저 들어온 것) 제거

표의 첫 줄 하나가 두 정책 차이의 거의 전부입니다. 그래서 get 에서 최근성 갱신을 빠뜨린 LRU 는 이름만 LRU 인 FIFO 가 되고, 적중 수가 조용히 줄어듭니다. 목록(list)으로 순서를 관리하면 remove 가 O(n) 이라 용량이 커질수록 느려지는데, 작은 시험에서는 드러나지 않습니다.

현실의 캐시가 정확한 LRU 인 것도 아닙니다. Redis 의 eviction 문서는 Redis 가 키 몇 개를 무작위로 골라 그중 가장 오래 안 쓴 것을 버리는 근사를 쓰며, 진짜 LRU 는 메모리가 더 들기 때문이라고 설명합니다(표본 수는 maxmemory-samples).

블룸 필터. m 비트 배열과 해시 k 개로 됩니다. 넣을 때 k 자리를 1 로 켜고, 물을 때 k 자리가 전부 1 이면 "있을지도", 하나라도 0 이면 "확실히 없다" 입니다. 켠 비트는 끄지 않으므로 넣은 키에 대해 거짓 음성은 없습니다. 서베이 2.1절의 계산으로 n 개를 넣은 뒤의 거짓 양성률은 약 (1 − e^(−kn/m))^k 이고, m 과 n 이 정해지면 k = (m/n)·ln 2 에서 가장 작아집니다. 2.2절은 목표 거짓 양성률 p 에 필요한 비트를 m ≈ n·log2(1/p) / ln 2 로 적습니다. 예시로 n = 1,000, p = 1% 면 m 은 약 9,586 비트(1.2KB 남짓), k 는 7 입니다.

k 개의 독립 해시를 따로 구할 필요도 없습니다. Kirsch·Mitzenmacher 의 Less Hashing, Same Performance(2008)는 두 해시 h1, h2 로 g_i(x) = h1(x) + i·h2(x) 를 만들어 써도 점근적 거짓 양성률이 나빠지지 않음을 보였습니다. 이 실습은 hashlib 의 sha256 다이제스트(32바이트)에서 h1, h2 를 뽑습니다. 내장 hash() 를 쓰지 않는 이유는 PYTHONHASHSEED 문서대로 문자열 해시의 시드가 기본으로 무작위라서, 다른 프로세스가 만든 필터를 같은 규칙으로 읽을 수 없기 때문입니다.

거짓 양성률을 잴 때 분모는 진짜로 없는 키에 대한 질의 수입니다. 전체 질의로 나누면 있는 키의 비율만큼 값이 작아져 필터가 실제보다 좋아 보입니다.

현장에서 만나는 모습

ClickHouse 의 skip index 가운데 bloom_filter 는 허용 거짓 양성률 하나를 인자로 받고(기본 0.025), 문서는 거짓 양성이 불필요한 블록 몇 개를 더 읽는 것뿐이라 큰 문제가 아니라고 적습니다. 'ClickHouse — 열 지향 분석 DB 를 속까지' 코스가 실제 그래뉼 수로 그 장면을 보여 줍니다. 만료·eviction 정책 선택과 cache-aside 는 'Redis 와 캐싱' 코스가, 같은 지역성 논리가 CPU 캐시 계층에서 어떻게 나타나는지는 '컴퓨터 구조' 코스가 다룹니다. 이 모듈은 그 밑의 자료구조를 직접 만들고 숫자로 확인하는 자리입니다.

다음 실습에서 할 것

치우친 접근 기록으로 LRU 와 FIFO 의 적중 수를 용량별로 재고, 한 번 훑는 스캔이 뜨거운 키를 몇 개 밀어내는지 셉니다. 이어서 식으로 m 과 k 를 고르고, 못박은 해시 규칙으로 블룸 필터를 만들어 거짓 양성률을 잰 뒤, 필터를 LRU 앞에 두면 DB 조회가 몇 번 줄어드는지 계산합니다.