실무 속의 LRU

LRU나 그에 가까운 정책은 컴퓨터 시스템의 모든 층에서 돌아갑니다. 이 장에서는 그 층들을 차례로 살펴보고, 실제로 가져다 쓸 라이브러리와 캐시 버그 대부분을 일으키는 함정을 정리합니다.

하드웨어, 운영체제, 데이터베이스

• CPU 캐시는 작은 집합(set) 안에서 제거할 줄을 고릅니다. 진짜 LRU는 하드웨어에 필요한 상태가 너무 많아서, CPU는 보통 tree-PLRU 같은 의사 LRU(pseudo-LRU)를 씁니다.
• 운영체제 페이지 캐시: Linux는 파일 페이지를 active 리스트와 inactive 리스트로 관리합니다. 두 번 접근해야 active로 올라가므로 한 번뿐인 스캔이 인기 페이지를 밀어내지 못합니다. 2Q나 CLOCK과 비슷한 발상의 LRU 근사입니다.
• 데이터베이스 버퍼 풀: MySQL InnoDB는 중간 지점 삽입(midpoint insertion)을 쓰는 LRU 리스트를 사용해, 새 페이지를 먼저 "old" 구간에 넣으므로 전체 테이블 스캔이 인기 구간을 비우지 못합니다. PostgreSQL은 또 다른 근사인 clock-sweep을 씁니다.

Redis 제거 정책

Redis가 maxmemory에 도달하면 maxmemory-policy 설정이 무엇을 제거할지 정합니다. noeviction, allkeys-lru, volatile-lru, allkeys-lfu, volatile-lfu, allkeys-random, volatile-random, volatile-ttl 등이 있으며, volatile- 정책은 만료 시간이 설정된 키만 대상으로 합니다. Redis는 전역 연결 리스트를 두지 않고, 키 몇 개를 표본으로 뽑아(maxmemory-samples, 기본 5) 그중 가장 오래된 키를 제거하는 방식으로 LRU를 근사합니다.

redis-cli CONFIG SET maxmemory 256mb
redis-cli CONFIG SET maxmemory-policy allkeys-lru

CDN과 브라우저

CDN 에지 서버도 디스크와 메모리가 한정되어 있어서, 드물게 요청되는 객체를 보통 LRU와 비슷한 정책으로 제거하고 Cache-Control: max-age의 TTL과 함께 씁니다. 브라우저의 HTTP 캐시도 디스크 할당량에 이르면 가장 오래전에 쓴 항목부터 지웁니다.

라이브러리

Python의 functools.lru_cache는 크기 제한이 있는 LRU로 함수를 메모이제이션합니다. 무제한 캐시는 maxsize=None(또는 functools.cache), 1과 1.0을 따로 캐시하려면 typed=True, 무효화에는 cache_clear()를 씁니다.

Java의 LinkedHashMap은 두 가지만 바꾸면 LRU 캐시가 됩니다. accessOrder = true를 넘겨 get이 항목을 맨 뒤로 옮기게 하고, removeEldestEntry를 재정의합니다.

import java.util.LinkedHashMap;
import java.util.Map;

class LruMap<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LruMap(int capacity) {
        super(16, 0.75f, true);            // true = 접근 순서
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;          // 삽입할 때마다 넘치면 제거
    }
}

운영 환경의 Java 서비스에서는 만료와 동시성까지 갖춘 Caffeine(W-TinyLFU) 같은 라이브러리가 대개 더 낫습니다. Node.js에서는 lru-cache 패키지가 같은 역할을 합니다.

스레드 안전성

LRU 캐시에서는 읽기도 쓰기입니다. get이 리스트 순서를 바꾸기 때문입니다. 두 스레드가 동시에 노드를 옮기면 포인터가 망가질 수 있으므로 읽기-쓰기 잠금으로는 해결되지 않습니다. 가장 단순한 방법은 모든 연산을 잠금 하나로 감싸는 것이고, 경합이 심하면 캐시를 여러 조각(shard)으로 나눠 조각마다 잠금을 둡니다.

import threading
from collections import OrderedDict

class ThreadSafeLRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()
        self.lock = threading.Lock()

    def get(self, key, default=None):
        with self.lock:
            if key not in self.data:
                return default
            self.data.move_to_end(key)
            return self.data[key]

    def put(self, key, value):
        with self.lock:
            self.data[key] = value
            self.data.move_to_end(key)
            if len(self.data) > self.capacity:
                self.data.popitem(last=False)

functools.lru_cache는 여러 스레드에서도 내부 구조를 일관되게 유지하지만, 같은 키로 동시에 호출하면 감싼 함수가 두 번 이상 실행될 수 있습니다.

캐시 무효화의 함정

• 낡은 데이터: 원본을 고친 뒤에는 캐시 사본을 지우거나 고칩니다. TTL을 두면 실수가 있어도 저절로 회복됩니다.
• 캐시 쇄도(cache stampede): 인기 키가 만료되는 순간 많은 요청이 함께 실패해 데이터베이스로 몰립니다. 키별 잠금, 요청 합치기, 약간씩 다른 TTL로 막습니다.
• 변경 가능한 캐시 값: 모든 호출자에게 같은 리스트나 딕셔너리를 돌려주면 한 호출자가 바꾼 내용이 다른 호출자에게 보입니다.
• 불완전한 키: 결과가 사용자, 언어, 옵션에 따라 달라진다면 그 값도 키에 들어가야 합니다.
• 크기 제한 없는 캐시: 제거가 없는 딕셔너리 "캐시"는 메모리 누수입니다. 메서드에 lru_cache를 붙이면 self도 계속 살아 있습니다.

from functools import lru_cache

@lru_cache(maxsize=128)
def settings(user_id):
    return {"theme": "light", "user": user_id}

s = settings(1)
s["theme"] = "dark"                 # 캐시된 객체를 바꿉니다
print(settings(1)["theme"])         # dark: 모든 호출자에게 뜻밖의 결과

@lru_cache(maxsize=128)
def settings_safe(user_id):
    return ("light", user_id)       # 바꿀 수 없는 값

정리

• LRU와 그 근사(의사 LRU, CLOCK, 표본 추출, 중간 지점 삽입)는 CPU, 커널, 데이터베이스, Redis, CDN, 브라우저에서 돌아갑니다.
• 직접 만들기보다 OrderedDict, lru_cache, LinkedHashMap, Caffeine, lru-cache 같은 라이브러리를 먼저 씁니다.
• 읽기를 포함한 모든 연산을 잠그고, 무효화는 처음부터 설계합니다.

더 읽을거리

• Cache replacement policies (Wikipedia)
• functools.lru_cache (Python docs)
• collections.OrderedDict (Python docs)
• LinkedHashMap (Java SE docs)
• Key eviction (Redis docs)
• Map (MDN)