LRU 캐시 개념

캐시는 가져오거나 계산하는 데 비용이 큰 데이터의 사본을 더 작고 빠른 곳에 보관해 두었다가, 같은 데이터를 다시 요청받으면 빠르게 돌려주는 장치입니다. 빠른 저장 공간은 작기 때문에 캐시는 결국 가득 차고, 무엇을 버릴지 정해야 합니다. 이때 쓰는 규칙을 교체 정책(eviction policy)이라고 하며, LRU(Least Recently Used, 가장 오래전에 사용한 항목 제거)는 가장 널리 가르치고 쓰는 정책입니다. 이 장에서는 용어를 정리하고, LRU를 다른 정책과 비교하고, 어떤 상황에 맞는지 살펴봅니다.

캐시가 하는 일

캐시는 언제나 더 느린 무언가의 앞에 놓입니다. CPU 캐시는 메인 메모리 앞에, 운영체제의 페이지 캐시는 디스크 앞에, Redis는 데이터베이스 앞에, CDN은 원본 서버 앞에 있습니다. 조회한 데이터가 캐시에 있으면 적중(hit), 느린 원본까지 가야 하면 실패(miss) 라고 합니다. 전체 조회 가운데 적중한 비율이 적중률(hit ratio) 이며, 캐시를 둘 가치가 있는지는 이 숫자로 판단합니다.

가장 단순한 캐시는 메모이제이션(memoization)에 쓰는 딕셔너리입니다. 아무것도 버리지 않으므로 가능한 키의 수가 적을 때만 안전합니다.

import time

slow_calls = 0

def slow_square(n):
    global slow_calls
    slow_calls += 1
    time.sleep(0.01)          # 네트워크 호출이라고 가정합니다
    return n * n

memo = {}

def cached_square(n):
    if n in memo:             # 적중
        return memo[n]
    memo[n] = slow_square(n)  # 실패: 계산하고 기억합니다
    return memo[n]

for n in [3, 4, 3, 3, 4, 5]:
    cached_square(n)
print(slow_calls)             # 실패 3번, 적중 3번

교체 정책이 필요한 이유

실제 캐시에는 용량(capacity) 이 있습니다. 항목 수일 수도, 바이트 수나 메모리 페이지 수일 수도 있습니다. 캐시가 가득 찬 상태에서 새 항목이 들어오면 기존 항목 하나를 제거(evict) 해야 합니다. 좋은 정책은 곧 다시 쓰일 가능성이 가장 낮은 항목을 고릅니다. 미래는 알 수 없으므로 모든 정책은 과거를 근거로 한 추측입니다.

TTL(Time To Live)은 다른 정책과 다른 질문에 답합니다. "가득 찼을 때 무엇을 버릴까"가 아니라 "데이터를 얼마 동안 믿을 수 있을까"입니다. 실제 시스템은 TTL을 LRU나 LFU와 함께 쓰는 경우가 많습니다.

FIFO 캐시는 순서 있는 딕셔너리로 쉽게 만들 수 있습니다. 삽입 순서가 곧 제거 순서이고, 조회해도 순서가 바뀌지 않습니다.

from collections import OrderedDict

class FIFOCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        return self.data.get(key)        # 읽어도 순서는 그대로입니다

    def put(self, key, value):
        if key not in self.data and len(self.data) >= self.capacity:
            self.data.popitem(last=False)  # 가장 먼저 넣은 항목 제거
        self.data[key] = value

fifo = FIFOCache(2)
fifo.put("a", 1); fifo.put("b", 2)
fifo.get("a")
fifo.put("c", 3)                         # 방금 읽었는데도 "a"가 제거됩니다
print(list(fifo.data))                   # ['b', 'c']

LRU의 아이디어

LRU는 시간 지역성(temporal locality), 즉 최근에 쓴 데이터는 곧 다시 쓰일 가능성이 높다는 성질에 기대어 있습니다. 항목을 최근 사용 순서(recency) 로 정렬해 두고, 조회나 저장에 성공할 때마다 그 항목을 "가장 최근" 쪽으로 옮깁니다. 공간이 필요하면 "가장 오래전" 쪽 끝의 항목을 제거합니다. FIFO와의 차이는 읽기가 항목을 새로 고친다는 점 하나뿐이지만, 이 차이 덕분에 캐시가 프로그램이나 사용자, 서비스의 현재 작업 집합을 따라가게 됩니다.

Python은 LRU 캐시를 데코레이터로 제공하므로, 정책이 동작하는 모습을 가장 빨리 확인할 수 있습니다.

from functools import lru_cache

@lru_cache(maxsize=2)
def load(key):
    print("loading", key)
    return key.upper()

load("a"); load("b")
load("a")                 # 적중: "a"가 가장 최근이 됩니다
load("c")                 # 가득 참: 가장 오래전에 쓴 "b" 제거
load("b")                 # 다시 실패: "loading b" 출력
print(load.cache_info())  # CacheInfo(hits=1, misses=4, maxsize=2, currsize=2)

용어

• 용량(capacity): 캐시가 담을 수 있는 최대 항목 수(또는 바이트 수)입니다.
• 적중 / 실패(hit / miss): 조회에 캐시가 답했는지 여부입니다.
• 제거(eviction): 새 항목의 자리를 만들려고 기존 항목을 빼는 일입니다.
• 무효화(invalidation): 원본 데이터가 바뀌어 캐시 항목을 지우거나 고치는 일입니다.
• 작업 집합(working set): 지금 이 순간 실제로 쓰이고 있는 키의 집합입니다.
• 캐시 오염(cache pollution): 다시 읽히지 않을 데이터가 쓸모 있는 항목을 밀어내는 현상으로, 한 번만 하는 전체 스캔이 대표적인 원인입니다.

LRU가 맞는 경우와 맞지 않는 경우

LRU는 접근이 움직이는 인기 키 집합에 몰릴 때 잘 맞습니다. 사용자 세션, 최근 본 페이지, 최근 연 파일이 그런 예입니다. 반대로 두 가지 상황에서는 약합니다. 첫째, 캐시보다 큰 순차 스캔은 모든 항목을 밀어내고 다시 쓰이지 않을 항목만 남깁니다. 둘째, 오랫동안 꾸준히 인기 있지만 일회성 키의 흐름보다 덜 자주 접근되는 키가 있다면 LFU나 2Q, ARC, W-TinyLFU 같은 혼합 정책이 더 잘 지켜 줍니다. 그래서 실무 시스템은 교과서 그대로의 LRU보다 LRU 변형을 쓰는 경우가 많습니다.

정리

• 캐시는 약간의 빠른 메모리로 느린 작업을 줄이며, 효과는 적중률로 잽니다.
• 가득 찬 캐시에는 FIFO, LRU, LFU, Random 같은 교체 정책이 필요하고, 흔히 TTL과 함께 씁니다.
• LRU는 가장 오랫동안 쓰이지 않은 항목을 제거하며 시간 지역성을 전제로 합니다.
• 순차 스캔과 장기적인 인기 항목이 약점이라서 실무에서는 LRU 변형을 많이 씁니다.