Adaptive Replacement Cache(ARC)
Table of Contents
1 동기
O(1) LRU 캐시 알고리즘을 보다가 더 좋은 알고리즘이 있을까 두리번거리다가 찾은 알고리즘이다. O(1) LRU 는 아주 간단하면서도 강력한 알고리즘이다. 하지만 그렇다고 범용적으로 사용할 수는 없다. LRU는 많은 경우 효과적이지만, 특정 워크로드(예: 순차적으로 데이터를 읽는 패턴)에서는 캐시를 효율적으로 활용하지 못하는 단점이 있다. 이런 경우에 사용할 수 있는 알고리즘이 바로 ARC 알고리즘이다.
2 개요
ARC는 IBM Almaden 연구 센터에서 개발된 캐싱 알고리즘으로, 캐시 메모리를 효율적으로 관리하여 성능향상을 도모했다. 데이터가 얼마나 최근에 사용되었는지(최근성)와 얼마나 자주 사용되었는지(빈도)를 모두 고려하여 동적으로 조정된다.
ARC는 캐시를 두 개의 주요 리스트(T1과 T2)와 두 개의 가상 리스트(B1과 B2)로 관리하며, 워크로드의 패턴에 따라 캐시 크기를 동적으로 조정한다. 이를 통해 LRU보다 더 나은 성능을 제공하며, 다양한 환경에 적응할 수 있는 유연성을 갖추고 있다.
또한 흥미로운 점이 PostgreSQL 도 이 알고리즘의 성능을 보고 채택을 했었으나, IBM이 특허를 취하면서 알고리즘을 변경했다. 변경된 알고리즘도 나중에 알아보도록 하자.
3 대충 작동 방식
ARC는 네 가지 주요 리스트를 사용한다:
- T1 (최근 사용): 최근에 한 번만 사용된 데이터를 저장
- T2 (자주 사용): 두 번 이상 사용된 데이터(즉, 자주 사용되는 데이터)를 저장
- B1 (T1의 고스트 리스트): T1에서 제거된 데이터를 추적하는 가상 리스트(실제 데이터를 저장하지 않음).
- B2 (T2의 고스트 리스트): T1에서 제거된 데이터를 추적하는 가상 리스트(실제 데이터를 저장하지 않음).
여기서 T1과 T2는 실제 캐시 메모리에 데이터를 저장하며, 캐시 크기의 합(T1 + T2)은 전체 캐시 용량으로 제한된다. 반면, B1과 B2는 과거에 캐시에서 제거된 데이터를 기록하는 역할만 하며, 실제 메모리에 데이터를 저장하지 않는다.
4 ARC의 핵심 아이디어
ARC의 핵심은 T1과 T2의 크기를 동적으로 조정하여 워크로드의 패턴에 적응하는 것이다.
예를 들어:
- 단기적으로 자주 접근되는 데이터가 많다면 T1의 크기를 늘리고,
- 장기적으로 자주 사용되는 데이터가 많다면 T2의 크기를 늘린다.
이 적응 메커니즘은 B1과 B2의 히트 수를 기반으로 작동하며, 이를 통해 ARC는 LRU보다 더 효율적으로 캐시를 관리할 수 있다.
(결국 T1, T2 의 크기를 B1, B2의 히트수로 조정한다!)
5 ARC 알고리즘의 동작 방식
- 데이터 요청 처리
캐시에 데이터가 요청되면 다음 과정을 거친다:
- 캐시 히트(Cache Hit): 요청된 데이터가 T1 또는 T2에 있는 경우
- 데이터를 T2로 이동시킨다. (데이터가 두 번 이상 사용되었음을 의미)
- T1에 있던 데이터라면 T1에서 제거되고 T2로 옮겨진다.
- 캐시 미스(Cache Miss): 요청된 데이터가 T1 또는 T2에 없는 경우
- 데이터를 캐시에 추가해야 하며, 추가 과정은 아래에서 설명.
- 캐시 미스 시 데이터 추가
캐시 미스가 발생하면 데이터를 캐시에 추가하는데, 이때 B1과 B2의 상태에 따라 처리 방식이 달라진다:
- 데이터가 B1에 있는 경우:
- T1의 크기를 증가시켜 단기 접근 패턴에 더 많은 공간을 할당.
- 요청된 데이터를 T2에 추가. (B1에 있었다는 것은 이전에 한 번 사용된 적이 있음을 의미)
- 데이터가 B2에 있는 경우:
- T2의 크기를 증가시켜 자주 사용되는 데이터에 더 많은 공간을 할당.
- 요청된 데이터를 T2에 추가.
- 데이터가 B1이나 B2에 없는 경우:
- 새로운 데이터로 간주하고 T1에 추가.
- 캐시가 가득 찬 경우 교체
캐시 용량이 가득 차면 데이터를 제거해야 한다.
이때 T1과 T2의 크기와 상태에 따라 교체가 결정된다:
- T1의 크기가 특정 임계값 이상인 경우:
- T1에서 가장 오래된 데이터를 제거하고, 제거된 데이터를 B1에 추가.
- T1의 크기가 임계값 미만인 경우:
- T2에서 가장 오래된 데이터를 제거하고, 제거된 데이터를 B2에 추가.
- 적응 메커니즘
ARC는 B1과 B2의 히트 수를 모니터링하여 T1과 T2의 크기를 동적으로 조정한다:
- B1에서 히트가 발생하면 T1의 크기를 증가시킨다. (단기 접근 패턴이 중요하다는 신호)
- B2에서 히트가 발생하면 T2의 크기를 증가시킨다. (장기 접근 패턴이 중요하다는 신호)
이 과정을 통해 ARC는 워크로드의 변화에 따라 캐시를 최적화한다.
6 ARC 알고리즘의 장단점
장점
- 적응성: 다양한 워크로드 패턴에 동적으로 대응할 수 있다.
- 성능: LRU보다 더 나은 캐시 히트율을 제공하며, 특히 패턴이 복잡한 환경에서 강점을 보인다.
- 구현 용이성: 복잡도가 상대적으로 낮아 실제 시스템에 적용하기 쉽다.
단점
- 메모리 사용량: B1과 B2 가상 리스트를 유지해야 하므로 LRU보다 메모리를 더 사용할 수 있다.
- 특정 워크로드에서의 한계: 일부 단순한 워크로드에서는 LRU와 성능 차이가 크지 않을 수 있다.
7 활용 사례
- 데이터베이스: 쿼리 결과나 자주 접근되는 데이터를 캐싱하여 처리 속도를 높인다.
- 웹 서버: 자주 요청되는 웹 페이지를 캐시에 저장하여 응답 시간을 단축한다.
- 파일 시스템: 자주 읽히는 파일 데이터를 캐싱하여 I/O 성능을 개선한다.
특히, 워크로드 패턴이 다양하거나 예측하기 어려운 환경에서 ARC의 적응성이 큰 장점으로 작용한다.
8 소스코드
from collections import deque class ARC: def __init__(self, cache_size): """캐시를 초기화합니다.""" self.cache_size = cache_size # 캐시 크기 self.p = 0 # T1의 최대 크기를 조정하는 매개변수 self.T1 = deque() # 최근 사용된 페이지 (LRU) self.T2 = deque() # 자주 사용된 페이지 (LRU) self.B1 = deque() # T1에서 제거된 페이지의 고스트 리스트 self.B2 = deque() # T2에서 제거된 페이지의 고스트 리스트 self.cache = {} # 페이지와 해당 리스트를 매핑하는 딕셔너리 def _replace(self, page): """캐시가 가득 찼을 때 페이지를 교체합니다.""" if self.T1 and ((page in self.B2 and len(self.T1) == self.p) or (len(self.T1) > self.p)): old = self.T1.pop() # T1에서 제거 self.B1.append(old) # B1으로 이동 del self.cache[old] else: old = self.T2.pop() # T2에서 제거 self.B2.append(old) # B2로 이동 del self.cache[old] def request(self, page): """페이지 요청을 처리하고 캐시를 업데이트합니다.""" # Case 1: 페이지가 T1에 있는 경우 if page in self.T1: self.T1.remove(page) self.T2.appendleft(page) # T2로 이동 self.cache[page] = ('T2', self.T2) return True # 캐시 히트 # Case 2: 페이지가 T2에 있는 경우 if page in self.T2: self.T2.remove(page) self.T2.appendleft(page) # T2에서 최신으로 갱신 return True # 캐시 히트 # Case 3: 페이지가 B1에 있는 경우 if page in self.B1: self.p = min(self.cache_size, self.p + max(len(self.B2) / len(self.B1), 1)) # p 증가 self._replace(page) self.B1.remove(page) self.T2.appendleft(page) # T2로 이동 self.cache[page] = ('T2', self.T2) return False # 캐시 미스 # Case 4: 페이지가 B2에 있는 경우 if page in self.B2: self.p = max(0, self.p - max(len(self.B1) / len(self.B2), 1)) # p 감소 self._replace(page) self.B2.remove(page) self.T2.appendleft(page) # T2로 이동 self.cache[page] = ('T2', self.T2) return False # 캐시 미스 # Case 5: 페이지가 캐시에 없는 경우 if len(self.T1) + len(self.T2) == self.cache_size: if len(self.T1) < self.cache_size: self.B1.popleft() # B1에서 제거 self._replace(page) else: old = self.T1.pop() # T1에서 제거 del self.cache[old] self.B1.append(old) # B1으로 이동 else: total = len(self.T1) + len(self.B1) + len(self.T2) + len(self.B2) if total >= self.cache_size: if total == 2 * self.cache_size: self.B2.popleft() # B2에서 제거 self._replace(page) self.T1.appendleft(page) # T1에 추가 self.cache[page] = ('T1', self.T1) return False # 캐시 미스 # 사용 예시 if __name__ == "__main__": cache = ARC(4) # 캐시 크기 4로 초기화 requests = [1, 2, 3, 1, 4, 5, 2, 6] # 페이지 요청 시퀀스 for req in requests: hit = cache.request(req) print(f"Request {req}: {'Hit' if hit else 'Miss'}")