[Cache] 캐시 동작과 캐시 교체 정책

캐시 Cache

 

 캐시는 데이터나 값을 미리 복사해 놓는 임시 장소입니다. 캐시에 데이터를 미리 복사해 놓으면, 계산이나 접근 시간 없이 더 빠른 속도로 데이터에 접근할 수 있습니다.

 

 

캐시 교체 정책 비교

 

 캐시에 모든 데이터를 다 담아둘 수 없기 때문에, 캐시의 크기가 제한되고 그에 따라 캐시가 대체되어야 합니다. 캐시 교체 알고리즘에 따라 어떤 파일을 버리고 새로운 캐시를 저장할지 결정하는 것이 캐시 교체 알고리즘입니다.

 

종류

1. FIFO(First in First Out)

 - 가장 먼저 들어간 캐시를 교체.

2. LFU(Least Frequently Used)

 - 사용 횟수가 가장 적은 캐시를 교체.

3. LRU(Least Recently Used)

 - 가장 오랫동안 사용되지 않은 것 교체

 

 

LRU(Least Recently Used) 캐시 동작 방식

 

 가장 오랫동안 사용되지 않은 파일을 교체하는 정책으로, Doubly Linked List와 HashMap으로 구현됩니다.

 

Doubly Linked List

 Doubly Linked List는 새로 추가되면 Tail에 추가되므로, Head에 가까울수록 오래 사용되지 않은 캐시이고 크기가 부족하면 Head의 캐시를 지우고 Tail에 새로운 캐시를 붙여 저장합니다.

 LRU에서는 맨 앞에 있는 캐시를 지우고, 맨 뒤에 추가하는 동작만 구현되면 되므로 탐색에 대한 시간 복잡도가 O(1)이 됩니다.

 

HashMap

 HashMap 자체는 Key와 Value로 구성되어 캐시와 달리 교체에 대한 별도의 정책이 없습니다.

 또한, 해싱(Hashing)을 사용하기 때문에 데이터의 검색이 빠르게 처리됩니다. 키가 중복저장 되지 않으므로, LRU에서 실제 데이터를 캐시에서 불러오는데 시간 복잡도가 O(1)이 됩니다

 

 

LRU 캐시 구현

 

 간단한 형태의 LRU 캐시를 구현해 보았습니다. Kotlin으로 간단하게 사용할 DoublyLinkedList와 Node를 구현하고, MutableMap이 HashMap으로 구현되어 있으므로 이를 이용해 데이터를 저장합니다.

 

<코드 추가 예정>