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 알고리즘의 동작 방식

  1. 데이터 요청 처리

캐시에 데이터가 요청되면 다음 과정을 거친다:

  • 캐시 히트(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'}")

9 reference

Date: 2025-03-04 Tue 00:00

Author: Younghwan Nam

Created: 2025-04-23 Wed 18:00

Emacs 27.2 (Org mode 9.4.4)

Validate