캐시 교체 정책에 관해서

Cache가 뭔데? 왜 하는데?

데이터나 값을 미리 저장해 두는 임시 장소이다.
굳이 이걸 미리 저장해 두는 이유는, 동일한 계산의 결과값이 필요할 때에 추가적인 결과 없이 미리 캐싱해둔 데이터들을 가져오면 더 빠르게 가져올 수 있고 어플리케이션에 부하가 덜 걸리기 때문이다.

캐시 교체 알고리즘

• FIFO(First In First Out)
  • 선입선출 - 먼저 입력된 캐시 순서대로 교체된다.
• LFU(Least Frequently Used)
  • 사용 횟수가 가장 적은 캐시를 교체한다.
• LRU(Least Recently Used)
  • 가장 오랫동안 사용되지 않은 캐시를 교체한다.

LRU 알고리즘에 대해서

나머지는 대충 어떤 방식인지 알겠고, 딱봐도 잘 안쓰일것같다.

단점을 보면

• FIFO
  • 많이 쓰이는 데이터가 먼저 들어온 경우 그냥 없어져 버림
• LFU
  • 얼마 전까지는 안쓰이다가 갑작스럽게 많이 쓰일 수 있는 데이터인데 사용 횟수가 적으면 없어짐

그래서 LRU가 자주 쓰인다고 한다.
이 LRU의 가장 오랫동안 사용되지 않은 캐시 교체 방법에 대해 기술한다.

1. 새로운 데이터가 들어온 경우
   • 캐시에 넣기
   • 캐시가 가득차 있는 경우 가장 오래된 데이터를 제거하고 넣는다.
2. 이미 존재하는 데이터가 들어온 경우
   • 해당 데이터를 사용한 뒤에 가장 최근 데이터 위치로 보낸다.

그걸 어떻게 하는건지?

• Double Linked List

이름 그대로 Linked List가 2개 있는 친구이다.
이 Linked List에 관해서는 해당 글을 참조해서 공부해 보자.

그래서 암튼 이 Linked List를 사용하여 구현한다고 해보자.
Head ----- Tail 으로 생각했을 때, 최근 사용 데이터가 Head에 들어가고 가장 오래된 데이터가 Tail에 위치한다.

그래서 이제 새로운 데이터를 집어넣을 때에는 Head에 넣어준다.
이후에 캐시에서 어떤 데이터를 사용한 경우, 이녀석의 위치를 다시 Head쪽으로 이동시켜 주면 된다.