[CS] 캐시 교체 방법론 및 구현 방법

 

캐시는 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 
"""