[TIL]캐싱

오늘 포스팅은 자바스크립트로 하는 자료구조와 알고리즘 14장 캐싱을 바탕으로 작성했습니다.

1. 캐싱이란?

캐싱(caching)은 자료를 임시 메모리에 저장하는 과정으로 추후에 해당 자료가 다시 필요할 때 쉽게 해당 자료를 얻을 수 있다.
캐싱의 예로 데이터베이스 시스템이 데이터를 캐싱해 하드 드라이브를 다시 읽는 작업을 피한다. 또한 웹 브라우저가 웹 페이지를 캐싱해 콘텐츠를 다시 다운로드 하는 작업을 피한다.
간단히 이야기 해서 캐싱의 목표는 히트(필요한 항목이 캐시에 존재하는 경우)를 최대화하고 미스(필요한 항목이 캐시에 존재하지 않는 경우)를 최소화 하는 것이다.

2. 캐싱 이해하기

캐시 설계는 다음의 두 가지 요소를 고려한다.

• 시간적 지역성: 최근에 접근한 메모리 위치를 다시 접근할 가능성이 높다
• 공간적 지역성: 최근에 접근한 메모리 위치 주변의 위치를 다시 접근할 가능성이 높다

3. 캐싱 기법

1) LFU 캐싱

LFU 캐싱은 운영체제가 메모리를 관리하기 위해 사용하는 캐싱 알고리즘이다. 운영체제는 어떤 블록이 메모리에서 참조된 횟수를 관리한다. 설계상 캐시가 자신의 한계를 초과하는 경우, 운영체제는 가장 참조 빈도가 낮은 항목을 삭제한다.
LFU 캐시를 가장 쉽게 구현하는 방법은 캐시에 로딩되는 모든 블록에 카운터를 할당한 다음 해당 블록에 대한 참조가 생성될 때마다 카운터를 증가시키는 것이다. 캐시가 한계를 초과하면 운영체제는 가장 카운터가 낮은 블록을 찾아서 캐시에서 제거한다.

LFU 캐싱은 직관적인 방법이지만, 이상적인 접근 방법이 아니다.
특정 블록이 집중적으로 참조된 짧은 시간을 제외한 나머지 시간 동안 더 자주 사용되는 블록이 삭제될 수도 있다. 게다가 신규 항목이 접근 빈도가 낮다는 이유로 캐시에 포함된지 얼마 안돼 삭제될 가능성이 있다. 이러한 문제로 인해 LFU는 잘 사용되지 않는다.

2) LRU 캐싱

LRU 캐싱은 가장 오래된 항목을 먼저 제거하는 캐싱 기법이다. 따라서 교체될 항목은 가장 오래전에 접근한 항목이다. 캐시의 항목에 접근하면 해당 항목은 리스트의 뒤로 이동한다. 캐시에 없는 페이지에 접근하면 가장 앞에 있는 항목이 제거 되고 신규 항목이 리스트의 가장 뒤에 삽입된다.

LRU 알고리즘을 구현하기 위해서는 어떤 노드가 언제 사용 됐는지를 관리해야 한다. 이를 구현하기 위해 LRU 캐시는 이중 연결 리스트와 해시테이블을 사용해 구현된다.

4. 요약

LFU 캐싱은 빈도를 사용해 어떤 노드를 제거해야 할지 결정하기 때문에 좋아보인다. 하지만 대부분의 경우에는 LFU는 LRU에 비해 성능이 떨어진다.
LFU는 특정 시점에 한해 자주 사용된 셩우를 배제하지 못하기 때문이다.
우리가 실제 사용하는 시스템의 동작 방식과 작업량을 고려할 때, LRU가 가장 효과적인 알고리즘이다.