LRU 캐시란? 동작 원리, 코드, 시간 복잡도

LRU 캐시가 해결하는 문제

캐시는 데이터베이스 쿼리, 웹 요청, 비싼 계산처럼 느린 작업의 결과를 보관해 같은 요청에 빠르게 답합니다. 메모리는 한정되어 있으므로 캐시가 가득 차면 무엇을 버릴지 정해야 합니다. LRU는 최근에 쓴 데이터는 곧 다시 쓰일 것이고 오랫동안 건드리지 않은 데이터는 아마 쓰이지 않을 것이라는 가정을 따릅니다. 이 가정은 많은 실제 워크로드에서 잘 맞아서, LRU와 그 근사 방식이 CPU 캐시, 운영 체제의 페이지 캐시, 데이터베이스, 웹 서버, CDN에 쓰입니다.

핵심 아이디어: 함께 일하는 두 자료구조

두 가지가 빨라야 합니다. 키를 찾는 것, 그리고 어떤 키가 가장 오래 사용되지 않았는지 아는 것입니다. 해시 맵만으로는 순서가 없고, 리스트만으로는 검색이 느립니다. 둘을 합치면 두 가지를 모두 해냅니다.

get(key)에서는 맵에서 노드를 찾아 맨 앞으로 옮기고 값을 반환합니다. put(key, value)에서는 노드를 갱신하거나 새로 만들어 맨 앞에 두고, 용량을 넘었다면 맨 뒤 노드를 제거하면서 맵에서 그 키도 삭제합니다.

용량이 2인 예제

처음부터 만드는 파이썬 구현

센티널 head·tail 노드를 두면 빈 리스트에 대한 특수 처리가 사라집니다. 모든 실제 노드는 항상 앞과 뒤에 노드가 있기 때문입니다.

class Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()   # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if key in self.map:
            self._unlink(self.map[key])
        node = self.map[key] = Node(key, value)
        self._push_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]

cache = LRUCache(2)
cache.put(1, "a")
cache.put(2, "b")
print(cache.get(1))   # a
cache.put(3, "c")     # evicts key 2
print(cache.get(2))   # None
cache.put(1, "A")
cache.put(4, "d")     # evicts key 3
print(cache.get(3), cache.get(1), cache.get(4))  # None A d

OrderedDict로 만드는 짧은 버전

collections.OrderedDict는 그 자체가 해시 맵과 이중 연결 리스트의 결합이며, move_to_end와 popitem(last=False)는 O(1)입니다. 그래서 LRU 캐시를 객체로 만들어야 할 때 파이썬다운 선택입니다.

from collections import OrderedDict

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

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # mark as most recent
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # drop least recent

c = LRU(2)
c.put("x", 1)
c.put("y", 2)
c.get("x")
c.put("z", 3)
print(list(c.data))  # ['x', 'z']

functools.lru_cache로 함수 결과 캐싱하기

함수의 반환값을 캐싱하려면 functools.lru_cache 데코레이터를 사용하세요. 인자는 딕셔너리 키가 되므로 해시 가능해야 합니다. cache_info()는 히트 수, 미스 수, 현재 크기를 보여 줍니다.

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(80))           # 23416728348467685
print(fib.cache_info())
# CacheInfo(hits=78, misses=81, maxsize=128, currsize=81)

maxsize=None은 크기 제한이 없는 캐시가 되며, functools.cache(파이썬 3.9 이상)가 하는 일이 바로 이것입니다. 비우려면 fib.cache_clear()를 호출하세요.

시간 복잡도와 공간 복잡도

변형, 실수, LRU를 쓸 때

• LFU(least frequently used)는 접근 횟수가 가장 적은 항목을 제거합니다. 인기 있는 항목을 일회성 스캔으로부터 보호하지만 더 복잡합니다.
• 근사 LRU: Redis 같은 시스템은 정확한 리스트를 유지하는 대신 키 몇 개를 샘플링해 그중 가장 오래된 것을 제거하여 메모리를 아낍니다.
• TTL 캐시는 정해진 시간이 지나면 항목을 만료시키며, 크기 제한과 함께 쓰는 경우가 많습니다.
• get이나 기존 키의 put에서 항목을 맨 앞으로 옮기는 것을 잊으면 LRU가 FIFO가 되어 버립니다.
• 제거한 키를 해시 맵에서 삭제하는 것을 잊으면 쓸모없는 항목이 남아 메모리가 샙니다.
• 스레드 간에 LRU 캐시를 공유하려면 연산마다 락이 필요합니다. functools.lru_cache는 여러 스레드에서 호출해도 안전합니다.

최근 사용이 미래 사용을 예측할 때 LRU는 좋은 기본값입니다. 한 번뿐인 대규모 스캔이 자주 쓰는 데이터를 밀어내는 경우에는 성능이 떨어지며, 그런 워크로드에는 LFU나 스캔 내성이 있는 정책이 유리합니다. 연산이 O(1)인 LRU 캐시 설계는 해시 맵과 연결 리스트를 함께 시험하기 때문에 코딩 면접에서 가장 흔한 문제 중 하나이기도 합니다.