[250302] LRU Cache

1. LRU Cache란?
2. 소스코드
3. 코드 설명
4. LRU가 적합한 경우
5. LRU가 부적합한 경우
6. 한계 극복 방안
7. 결론

1 LRU Cache란?

LRU(Least Recently Used) Cache는 가장 최근에 사용되지 않은 데이터를 제거하는 캐시 eviction 정책을 사용한다.

O(1) 시간 복잡도를 달성하기 위해 이중연결리스트와 해시맵을 사용한다.

2 소스코드

class Node:
    def __init__(self, key, value):
	self.key = key
	self.value = value
	self.prev = None  # 이전 노드
	self.next = None  # 다음 노드

class LRUCache:
    def __init__(self, capacity):
	self.capacity = capacity  # 캐시 용량
	self.cache = {}  # key -> Node 매핑
	# 더미 헤드와 테일로 이중 연결 리스트 관리
	self.head = Node(0, 0)  # 더미 헤드
	self.tail = Node(0, 0)  # 더미 테일
	self.head.next = self.tail
	self.tail.prev = self.head

    def _remove(self, node):
	"""이중 연결 리스트에서 노드 제거"""
	node.prev.next = node.next
	node.next.prev = node.prev

    def _add(self, node):
	"""노드를 헤드 바로 다음에 추가 (가장 최근 사용)"""
	node.prev = self.head
	node.next = self.head.next
	self.head.next.prev = node
	self.head.next = node

    def get(self, key):
	"""키에 해당하는 값 반환"""
	if key in self.cache:
	    node = self.cache[key]
	    self._remove(node)  # 기존 위치에서 제거
	    self._add(node)     # 가장 최근 사용 위치로 이동
	    return node.value
	return -1

    def put(self, key, value):
	"""키-값 쌍 추가 또는 업데이트"""
	if self.capacity == 0:
	    return

	if key in self.cache:
	    self._remove(self.cache[key])  # 기존 노드 제거
	elif len(self.cache) >= self.capacity:
	    # 캐시가 가득 찼을 때 가장 오래된 항목 제거
	    lru_node = self.tail.prev
	    self._remove(lru_node)
	    del self.cache[lru_node.key]

	# 새 노드 추가
	new_node = Node(key, value)
	self._add(new_node)
	self.cache[key] = new_node

# 사용 예시
lru = LRUCache(2)
lru.put(1, 1)    # 캐시: {1=1}
lru.put(2, 2)    # 캐시: {1=1, 2=2}
print(lru.get(1))  # 출력: 1 (1이 최근 사용됨)
lru.put(3, 3)    # 2 제거, 캐시: {1=1, 3=3}
print(lru.get(2))  # 출력: -1
print(lru.get(1))  # 출력: 1
lru.put(4, 4)    # 3 제거, 캐시: {1=1, 4=4}
print(lru.get(3))  # 출력: -1
print(lru.get(4))  # 출력: 4

3 코드 설명

클래스 구조

Node:

캐시 항목을 나타냅니다.
속성: key, value, prev, next (이중 연결 리스트 포인터).

LRUCache:

LRU 캐시의 전체 로직을 관리합니다.
주요 속성:
- capacity: 최대 용량.
- cache: 키로 노드를 빠르게 찾기 위한 해시 맵.
- head, tail: 이중 연결 리스트의 더미 노드.

주요 메서드

_remove(self, node): 노드를 이중 연결 리스트에서 제거.
_add(self, node): 노드를 리스트의 가장 앞(최근 사용 위치)에 추가.
get(self, key): 키에 해당하는 값을 반환하고, 해당 노드를 최근 사용 위치로 이동.
put(self, key, value): 키-값 쌍을 추가하거나 업데이트하며, 캐시가 가득 차면 가장 오래된 항목을 제거.

시간 복잡도

get: O(1) - 해시 맵으로 노드 찾기 및 리스트 이동 모두 상수 시간.
put: O(1) - 삽입, 제거, 업데이트 모두 상수 시간.

4 LRU가 적합한 경우

LRU는 "최근에 사용된 데이터가 앞으로도 사용될 가능성이 높다"는 시간적 지역성(Temporal Locality) 원칙을 기반으로 동작합니다. 따라서 다음과 같은 상황에서 적합.

시간적 지역성이 강한 작업
- 사용 사례: 웹 브라우저의 캐시, 데이터베이스 쿼리 캐시, 운영체제 페이지 캐시.
- 이유: 사용자가 최근에 방문한 웹 페이지나 최근에 실행한 쿼리는 다시 사용될 가능성이 높음. LRU는 이러한 최근 데이터를 유지하고 오래된 데이터를 제거하여 효율성을 높임.
짧은 시간 내 반복 접근 패턴
- 사용 사례: 스트리밍 서비스의 버퍼링, 실시간 로그 분석.
- 이유: 특정 데이터(예: 최근 재생된 비디오 프레임)가 짧은 시간 동안 반복적으로 접근될 때, LRU는 이를 캐시에 유지하여 빠른 접근을 보장.
고정된 데이터셋 크기에서의 효율성
- 사용 사례: 메모리 제한이 있는 임베디드 시스템, 소규모 캐시.
- 이유: LRU는 캐시 크기가 작아도 최근 사용된 데이터를 우선적으로 유지하므로, 제한된 리소스 환경에서 효율적.
단순하고 빠른 구현이 필요한 경우
- 사용 사례: 프로토타이핑, 성능 최적화가 중요한 애플리케이션.
- 이유: LRU는 LFU보다 구현이 간단하고 모든 연산이 O(1)에 수행되므로, 빠른 개발과 실행 속도가 필요한 환경에 적합.

5 LRU가 부적합한 경우

라운드 로빈 패턴: 데이터가 순차적으로 한 번씩만 사용된다면, 모든 항목이 계속 교체되어 캐시 적중률이 떨어짐(LFU가 더 적합).
빈도 기반 우선순위: 자주 사용되지만 최근에 사용되지 않은 데이터가 제거될 수 있음(LFU가 더 유리).

6 한계 극복 방안

LFU(Least Frequently Used): 자주 사용되지 않는 데이터를 제거하여 라운드 로빈 패턴이나 빈도 기반 데이터에 더 적합.
2Q 또는 ARC(Adaptive Replacement Cache): LRU와 LFU의 장점을 결합하여 시간적/빈도적 지역성을 모두 고려.
SLRU(Segmented LRU): 캐시를 최근 사용/오래된 사용으로 세분화하여 성능을 개선.
캐싱 라이브러리 활용: Redis, Memcached와 같은 라이브러리는 LRU를 기반으로 최적화된 알고리즘을 제공.

7 결론

LRU는 최근 사용 패턴이 중요한 환경에서 강력하며, 구현이 간단하고 모든 연산이 O(1)로 빠름. 반면, LFU는 사용 빈도를 기준으로 데이터를 유지하므로, 자주 사용되는 데이터를 장기적으로 보존해야 하는 경우에 더 적합.