캐시는 Hit 시 캐시에 있는 정보를 빠르게 반환할 수 있지만, Miss 가 된다면 캐시 접근 후 Disk 나 다른 저장소 등
접근 횟수가 늘어날 수 있다.
따라서 캐시는 자주 참조될 것 같은 데이터 혹은 접근 예정인 데이터가 적절히 배치되어 저장되있어야 더 효율을 발휘한다.
이러한 캐시의 특성상 참조되지 않을 것 같은 정보를 캐시에서 교체하는 방법론을 정리하고자 한다.
아래 3가지는 주로 언급되는 교체 방식이다.
1. FIFO
- 선입선출. 말 그대로 먼저 들어온 것 즉 오래된 것을 교체하는 방식이다. Queue 로 구현 가능하다.
2. LFU (Least Frequntly used)
- 가장 적게 사용된 캐시를 교체하는 방식이다. 카운팅 을 사용해서 구현 가능하다.
3. LRU (Least recently used)
- 가장 최근에 사용하지 않은 캐시를 교체하는 방식이다. 현재 대부분의 시스템에서 채택 중인 방법론이다.
그렇다면 LRU는 어떻게 구현할 수 있을까?
여러 방식이 있겠지만, 시간복잡도 상 현재 시스템에서는 Linked List 와 Hash 를 사용하여 구현한다.
1. 캐시들을 노드로 구현하고 Hash에 해당 노드들을 지정한다.
- 이렇게 하면 캐시 접근 즉 노드 접근 시 시간 복잡도는 O(1) 이 된다.
2. 캐시를 접근 할 때 마다, LinkedList 의 맨 뒤로 보낸다.
- 접근 시간 복잡도 O(1) , 맨 뒤로 보내는 시간 복잡도 또한 O(1) 로 O(1) 의 시간복잡도가 유지 된다.
3. 최대 캐시 페이지의 용량이 넘어간다면, popleft 를 하여 캐시를 제거한다. 이 또한 시간복잡도는 O(1) 이다.
예시코드
간단한 파이썬 예시코드이다.
Hash 와 이중연결리스트를 이용해 어렵지 않게 LRU를 구현할 수 있는 걸 볼 수 있다.
class Node:
def __init__(self, val):
self.val = val
self.next = None
self.prev = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def add(self, node):
if self.head is None:
self.head = node
self.tail = node
return node
# tail에 새 노드를 추가하고 tail 갱신
self.tail.next = node
node.prev = self.tail
self.tail = node
return node
def print_all(self):
cur_node = self.head
while cur_node is not None:
print(cur_node.val, end=' ')
cur_node = cur_node.next
print()
def hit(self, node):
if node == self.tail:
return # 이미 맨 뒤에 있는 경우
# 노드를 현재 위치에서 제거
if node == self.head:
self.head = node.next
self.head.prev = None
else:
node.prev.next = node.next
node.next.prev = node.prev
# tail 뒤에 추가
self.tail.next = node
node.prev = self.tail
node.next = None
self.tail = node
def pop_left(self):
if self.head is None:
return None
node = self.head
self.head = self.head.next
if self.head:
self.head.prev = None
else:
self.tail = None # 리스트가 비면 tail도 None으로
return node
cachePage = LinkedList()
cache_hash = {}
# 캐시에 예시 프로세스들 추가
for i in range(10):
cache_hash[i] = cachePage.add(Node(i))
cachePage.print_all()
"""
출력 결과
0 1 2 3 4 5 6 7 8 9
"""
def hit(id):
try:
node = cache_hash[id]
print("Cache Hit:", node.val)
cachePage.hit(node)
cachePage.print_all()
except KeyError:
print("Cache Miss -> 타 저장소 탐색")
hit(7)
"""
출력 결과
Cache Hit: 7
0 1 2 3 4 5 6 8 9 7
"""
MAX_SIZE = 10
"""
만약 캐시의 Capacity 를 초과하는 경우
"""
# 캐시의 Capacity를 초과하는 경우 처리
def add_to_cache(id):
if id in cache_hash:
hit(id)
return
if len(cache_hash) >= MAX_SIZE:
removed_node = cachePage.pop_left()
if removed_node:
del cache_hash[removed_node.val]
new_node = cachePage.add(Node(id))
cache_hash[id] = new_node
cachePage.print_all()
# 새로운 데이터 추가로 Capacity 초과 테스트
add_to_cache(999)
"""
출력 결과
1 2 3 4 5 6 8 9 7 999
"""
'IT 기술 > CS' 카테고리의 다른 글
[CS] HTTP 의 개념과 구성요소 (3) | 2024.11.15 |
---|