LRU 캐시의 동작 원리

LRU 캐시는 두 질문에 빨리 답해야 합니다. "이 키가 캐시에 있는가?"와 "가장 오래전에 쓴 키는 무엇인가?"입니다. 고전적인 자료 구조 하나로는 두 질문 모두에 상수 시간으로 답할 수 없으므로, 표준 설계는 두 구조를 함께 씁니다. 조회에는 해시 맵을, 사용 순서에는 이중 연결 리스트를 씁니다. 이 장에서는 이 설계를 단계별로 살펴보고 작은 예제로 추적해 봅니다.

함께 움직이는 두 구조

• 해시 맵은 키를 리스트 안의 노드에 연결하므로, 항목을 찾는 데 평균 O(1)이 걸립니다.
• 이중 연결 리스트는 항목을 최근 사용 순서로 유지합니다. 앞쪽(head 바로 다음)이 가장 최근에 쓴 항목이고, 뒤쪽(tail 바로 앞)이 가장 오래전에 쓴 항목입니다.
• 각 노드는 값과 함께 키도 저장합니다. 제거할 때는 맨 뒤 노드만 손에 있으므로, 맵에서 지우려면 그 노드의 키가 필요합니다.
• 리스트가 이중 연결인 이유는 중간 노드를 떼어 낼 때 앞 노드가 필요하기 때문입니다. prev와 next 포인터가 있으면 떼어 내기가 O(1)입니다.
• 보초(sentinel) 노드 head와 tail은 데이터를 담지 않습니다. 빈 리스트나 첫 노드, 마지막 노드에 대한 특수한 경우를 모두 없애 줍니다.

head <-> [C] <-> [B] <-> [A] <-> tail
         가장 최근        가장 오래전

map: { A: 노드 A, B: 노드 B, C: 노드 C }

연산

get(key)는 맵에서 키를 찾습니다. 없으면 -1이나 None 같은 약속된 값을 돌려줍니다. 있으면 노드를 리스트에서 떼어 head 바로 뒤에 다시 넣고 값을 돌려줍니다.

put(key, value)는 먼저 맵을 확인합니다. 키가 이미 있으면 값을 바꾸고 적중 때와 똑같이 노드를 맨 앞으로 옮깁니다. 키가 없고 캐시가 가득 찼다면 tail 바로 앞의 노드를 떼어 내고 그 키를 맵에서 지운 다음, 새 노드를 만들어 head 뒤에 넣고 맵에 등록합니다.

포인터 작업은 모두 두 도우미 함수로 정리됩니다. 둘 다 정해진 개수의 포인터만 바꾸므로 두 연산이 모두 O(1)입니다.

def unlink(node):
    # A <-> node <-> B  를  A <-> B  로
    node.prev.next = node.next
    node.next.prev = node.prev

def push_front(head, node):
    # head <-> X  를  head <-> node <-> X  로
    node.prev = head
    node.next = head.next
    head.next.prev = node
    head.next = node

노드를 맨 앞으로 옮기는 일은 unlink(node) 다음에 push_front(head, node)를 부르는 것이고, 제거는 unlink(tail.prev)와 맵 삭제를 함께 하는 것입니다.

용량 3으로 추적하기

리스트는 가장 최근부터 가장 오래전 순서로 적습니다.

핵심은 5단계입니다. A가 가장 먼저 들어왔으므로 FIFO 캐시라면 A를 제거했을 것입니다. 하지만 4단계에서 A를 읽었기 때문에 LRU는 B를 제거합니다. 6단계는 실패가 아무것도 바꾸지 않는다는 점을, 7단계는 값 갱신도 사용으로 친다는 점을 보여 줍니다.

추적 결과 재현하기

추적이 맞는지 확인하는 가장 빠른 방법은 OrderedDict로 짧게 시뮬레이션해 보는 것입니다. OrderedDict는 필요한 두 기본 동작인 move_to_end와 popitem(last=False)를 이미 제공합니다.

from collections import OrderedDict

def run(capacity, ops):
    cache = OrderedDict()            # 처음 = 가장 오래전, 끝 = 가장 최근
    for op, key, *value in ops:
        result = "-"
        if op == "get":
            if key in cache:
                cache.move_to_end(key)
                result = cache[key]
            else:
                result = -1
        else:
            if key in cache:
                cache.move_to_end(key)
            elif len(cache) >= capacity:
                cache.popitem(last=False)
            cache[key] = value[0]
        order = ", ".join(reversed(cache))  # 가장 최근부터
        print(f"{op}({key}) -> {result}: {order}")

run(3, [("put", "A", 1), ("put", "B", 2), ("put", "C", 3), ("get", "A"),
        ("put", "D", 4), ("get", "B"), ("put", "C", 30), ("put", "E", 5), ("get", "D")])

마지막 줄에 get(D) -> 4: D, E, C가 출력되어 표와 일치합니다.

자주 하는 실수

• get에서 노드를 옮기지 않는 실수입니다. 그러면 캐시가 FIFO처럼 동작합니다.
• put이 기존 키를 갱신할 때 노드를 옮기지 않는 실수입니다.
• 키가 이미 있는지 확인하기 전에 제거부터 하는 실수입니다. 가득 찬 캐시에서 기존 키를 갱신할 때는 아무것도 제거하면 안 됩니다.
• 리스트에서만 노드를 빼고 맵에서는 지우지 않는(또는 그 반대) 실수입니다. 두 구조는 언제나 같은 키 집합을 가리켜야 합니다.

정리

• 맵은 O(1) 조회를, 이중 연결 리스트는 O(1) 순서 변경과 제거를 맡습니다.
• 보초 head와 tail이 특수한 경우를 없애고, 노드에 키를 저장해 두어야 제거할 때 맵도 정리할 수 있습니다.
• 적중과 갱신은 항목을 맨 앞으로 옮기고, 실패는 아무것도 바꾸지 않으며, 제거는 tail 바로 앞 노드를 뺍니다.