[250302] LFU Cache

1. LRU의 한계 이해하기
2. LFU의 메커니즘
3. LRU와 LFU 비교
- 3.1. 최근성(recency) vs 빈도(frequency):
- 3.2. 특정 워크로드에서의 장점
4. 코드 예시
- 4.1. 구조 설명
5. 결론

1 LRU의 한계 이해하기

LRU는 캐시에서 가장 최근에 사용되지 않은 항목을 제거하는 알고리즘. 일반적으로 많은 상황에서 효과적이지만, 특정 패턴에서는 비효율적. 특히 라운드 로빈(round-robin)

라운드 로빈 패턴의 예시: 캐시 크기가 3이고, 항목 A, B, C, D가 순차적으로 반복해서 접근된다고 가정하자.

LRU는 다음과 같이 동작:

A 추가 → 캐시: [A]
B 추가 → 캐시: [A, B]
C 추가 → 캐시: [A, B, C]
D 추가 → 캐시: [B, C, D] (A 제거)
A 다시 접근 → 캐시: [C, D, A] (B 제거)

이 과정이 반복되면, 캐시는 계속해서 항목을 교체하게 되고, =캐시 미스(cache miss)=가 빈번하게 발생. 즉, LRU는 최근에 사용된 순서만 고려하기 때문에, 자주 사용되는 항목이더라도 최근에 접근되지 않았다면 제거될 수 있음.

2 LFU의 메커니즘

LFU는 가장 덜 자주 사용된(Least Frequently Used) 항목을 제거하는 방식으로 동작. 이를 위해 각 항목의 **접근 빈도(frequency)**를 추적하며, 캐시가 가득 찼을 때 빈도가 가장 낮은 항목을 제거.

LFU의 동작 예시: 같은 캐시 크기 3으로 A, B, C, D를 처리한다고 가정하되, A가 더 자주 접근된다고 해보자.

A 추가 → 캐시: [A], 빈도: {A: 1}
B 추가 → 캐시: [A, B], 빈도: {A: 1, B: 1}
C 추가 → 캐시: [A, B, C], 빈도: {A: 1, B: 1, C: 1}
A 다시 접근 → 캐시: [A, B, C], 빈도: {A: 2, B: 1, C: 1}
D 추가 → 캐시: [A, C, D], 빈도: {A: 2, C: 1, D: 1} (B 제거)

여기서 LFU는 빈도가 가장 낮은 B를 제거하고, 자주 접근되는 A를 유지. 이는 LRU와 달리 빈도 기반으로 동작하기 때문.

3 LRU와 LFU 비교

3.1 최근성(recency) vs 빈도(frequency):

LRU는 최근에 사용된 시간만 고려하므로, 자주 사용되는 항목이더라도 최근에 접근되지 않으면 제거될 수 있습니다.
LFU는 접근 빈도를 기준으로 판단하므로, 자주 사용되는 항목을 캐시에 오래 유지할 수 있습니다.

3.2 특정 워크로드에서의 장점

라운드 로빈처럼 모든 항목이 고르게 접근되는 경우보다는, 특정 항목이 반복적으로 자주 접근되는 워크로드에서 LFU가 더 효율적입니다. 예를 들어, 웹사이트에서 인기 있는 페이지 몇 개가 자주 요청되는 경우, LFU는 이를 캐시에 유지하여 캐시 히트율을 높입니다.

4 코드 예시

O(log N) 시간 복잡도의 LFU는 일반적으로 =min-heap=(최소 힙)과 해시 테이블을 사용하여 구현.
=min-heap=은 항목의 사용 빈도(frequency)를 기준으로 정렬되며, 가장 낮은 빈도를 가진 항목(LFU)을 빠르게 찾을 수 있음.
그러나 heap 연산(삽입, 삭제, 재정렬)이 O(log N) 복잡도를 가지므로 전체 연산 시간도 O(log N) 복잡도를 가짐.

4.1 구조 설명

데이터 구조:

heapq (Python의 최소 힙 구현)를 사용하여 빈도와 키를 관리.
해시 테이블(cache와 freq)로 키와 값, 빈도를 빠르게 조회.

시간 복잡도:

삽입(put): O(log N) - heap에 새 항목 추가 및 재정렬.
조회(get): O(log N) - heap에서 항목 찾고 빈도 증가 후 재정렬.
삭제(_evict): O(log N) - heap에서 최소 빈도 항목 제거 및 재정렬.

한계: 대규모 데이터셋에서 성능이 O(1) 구현보다 느릴 수 있음.

import heapq
from collections import defaultdict

class LFUCache:
    def __init__(self, capacity):
	self.capacity = capacity
	self.cache = {}  # 키-값 저장 (key -> value)
	self.freq = {}  # 키-빈도 저장 (key -> frequency)
	self.heap = []  # (frequency, key) 튜플로 구성된 최소 힙
	self.freq_count = defaultdict(int)  # 빈도별 카운트 (빈도 -> 개수)

    def get(self, key):
	if key not in self.cache:
	    return -1
	# 빈도 증가
	old_freq = self.freq[key]
	self.freq_count[old_freq] -= 1
	new_freq = old_freq + 1
	self.freq[key] = new_freq
	self.freq_count[new_freq] += 1
	# heap에서 기존 항목 제거 및 새 항목 추가
	heapq.heappush(self.heap, (new_freq, key))
	# 최소 빈도 유지
	while self.heap and (self.freq_count[self.heap[0][0]] == 0 or self.heap[0][1] not in self.cache):
	    heapq.heappop(self.heap)
	return self.cache[key]

    def put(self, key, value):
	if self.capacity <= 0:
	    return
	if key in self.cache:
	    self.cache[key] = value
	    self.get(key)  # 빈도 증가
	    return
	if len(self.cache) >= self.capacity:
	    self._evict()
	self.cache[key] = value
	self.freq[key] = 1
	self.freq_count[1] += 1
	heapq.heappush(self.heap, (1, key))
	# 최소 빈도 유지
	while self.heap and (self.freq_count[self.heap[0][0]] == 0 or self.heap[0][1] not in self.cache):
	    heapq.heappop(self.heap)

    def _evict(self):
	# 최소 빈도 항목 제거
	while self.heap:
	    freq, key = heapq.heappop(self.heap)
	    if self.freq_count[freq] > 0 and key in self.cache:
		self.freq_count[freq] -= 1
		del self.cache[key]
		del self.freq[key]
		break

# 사용 예시
lfu = LFUCache(2)
lfu.put(1, 1)  # 캐시: {1: 1}, 빈도: {1: 1}
lfu.put(2, 2)  # 캐시: {1: 1, 2: 2}, 빈도: {1: 1, 2: 1}
print(lfu.get(1))  # 출력: 1, 빈도: {1: 2, 2: 1}
lfu.put(3, 3)  # 캐시: {1: 1, 3: 3}, 빈도: {1: 2, 3: 1} (빈도 1인 2 제거)
print(lfu.get(2))  # 출력: -1
print(lfu.get(1))  # 출력: 1

5 결론

LFU는 LRU의 한계를 극복하기 위해 빈도를 기준으로 캐시 항목을 관리. 특히 자주 사용되는 항목이 반복적으로 접근되는 상황에서 LRU보다 더 나은 성능을 발휘. 하지만 구현이 더 복잡하고, 모든 상황에서 LRU보다 우수한 것은 아니므로, 사용 환경과 워크로드를 고려해 적절히 선택해야함.

이렇게 LFU는 LRU가 해결하지 못하는 문제를 효과적으로 보완하며, 특정 시나리오에서 캐시 효율성을 극대화할 수 있는 강력한 대안이 된다.