1. 캐싱이란?
캐싱: 자료를 임시 메모리에 저장하는 과정
장점: 해당 자료가 다시 필요할 때 쉽게 얻을 수 있다.
사용 예시:
- DB 시스템이 데이터를 캐싱해 하드 드라이브를 다시 읽는 작업을 피한다.
- 웹 브라우저가 웹 페이지를 캐싱해 콘텐츠를 다시 다운로드하는 작업을 피한다.
캐싱 사용의 목표: 히트 최대화, 미스 최소화
캐시는 시간적 지역성과 공간적 지역성을 고려하여 설계된다.
- 시간적 지역성 (temporal locality): 최근에 접근한 메모리 위치를 다시 접근할 가능성이 높다.
- 공간적 지역성 (spatial locality): 최근에 접근한 메모리 위치 주변의 위치를 다시 접근할 가능성이 높다.
2. 캐싱 알고리즘
1) 최적의 캐싱 알고리즘
캐시에서 향후에 가장 나중에 사용될 부분을 -> 신규로 삽입하고자 하는 항목으로 교체하는 캐싱 알고리즘
이를 위해서 향후에 각 항목을 몇 번이나 접근할 것인지 계산해야 한다. 그러나 미래를 정확히 계산하기란 거의 불가능하기 때문에 구현도 거의 불가능하다.
2) LFU 캐싱 (최소 빈도 사용 캐싱)
운영체제가 어떤 블록이 메모리에서 참조된 횟수를 관리하고, 캐시의 크기를 초과하는 경우 운영체제가 참조 빈도가 가장 낮은 항목을 삭제한다.
LFU 캐시를 가장 쉽게 구현하는 방법은 캐시에 로딩되는 모든 블록에 카운터를 할당하고, 해당 블록에 대한 참조가 생성될 때마다 카운터를 증가시키는 것이다.
이 알고리즘의 단점은 단시간에 집중적으로 한 블록이 사용된다면, 나머지 시간동안 더 자주 사용될 다른 블록이 삭제될 가능성이 있다는 것이다. 더하여 신규 항목의 접근 빈도가 낮다는 이유로 캐시에 포함된 지 얼마 안되어 삭제될 수도 있다.
이런 단점 때문에 일부 하이브리드 시스템 (모바일 키보드 앱)을 제외하고는 LFU 알고리즘은 잘 사용되지 않는다.
LFU 캐시
LFU 캐시는 이중 연결 리스트를 사용한다. 따라서 O(1) 시간에 항목을 제거한다. 이를 위해 LFU의 이중 연결 노드에 freqCount 속성을 두어 노드의 접근 및 설정 빈도를 측정한다.
LFU 캐시에는 keys와 freq라는 두 개의 해시 테이블이 있다.
keys는 이중 연결 리스트의 각 노드를 저장한다. freq의 키는 빈도를 나타내고, 각 value는 이중 연결 리스트의 항목이다.
이 알고리즘에서 삽입은 헤드에서만 일어나고, 제거는 테일에서만 일어난다.
LFU의 set
- 신규 항목 삽입
- 캐시에 여유가 있다면: freq의 이중 연결 리스트에 삽입- 캐시가 가득 찼다면: 이중 연결 리스트의 테일 항목이 삭제된 후, 신규 항목 삽입
- 예전 항목의 교체 (항목이 이미 캐시에 존재할 경우)
- 해당 노드를 리스트의 헤드로 이동하고, 최소 빈도 변수인 minFreq를 증가하여 어떤 항목을 제거할 지 계산한다.
LFU의 get
캐시가 O(1) 시간에 현재 노드를 반환한 다음 접근 카운터를 증가시켜야 한다.
- get할 항목이 캐시에 존재하지 않을 경우: return null
- get할 항목이 캐시에 존재할 경우: 해당 항목의 빈도 증가, 해당 항목은 연결 리스트의 헤드로 이동, 최소 빈도 변수인 minFreq 수정
3) LRU 캐싱 (가장 오래전 사용 캐싱)
가장 오래된 항목을 먼저 제거하는 캐싱 알고리즘. (이중 연결 리스트와 해시 테이블을 사용해 구현)
캐시의 항목에 접근하면 해당 항목은 리스트의 뒤로 이동한다. (리스트의 마지막이 최신이다.)
캐시에 없는 페이지에 접근하면, 가장 앞에 있는 항목(가장 오래된 항목)이 제거되고, 신규 항목이 리스트의 마지막에 삽입된다.
새로운 자료가 추가될 때마다 헤드가 위로 이동되고, 리스트의 크기가 초과되면 가장 오래된 자료가 제거된다.
어떤 노드가 언제 사용됐는지를 관리하는 것이 LRU 알고리즘의 핵심이다.
LRU 캐시는 capacity 매개변수를 전달함으로써 초기화한다. (capacity는 캐시에 허용되는 노드의 개수를 정의함.) 또한, 삽입은 tail에서만 이루어진다.
LRU의 set
- LRU 캐시의 keys 속성을 사용해 해당 노드를 저장한다.
LRU의 get
- get이 호출될 때마다 해당 노드를 리스트의 헤드로 이동시킨다. (헤드에는 가장 오래된 노드가 저장되는 거 아닌가?)
캐시의 용량이 초과된 경우 테일로부터 가장 먼 노드를 제거한다. (헤드?)
