캐시(cache)는 데이터 접근 비용을 줄이기 위해 일부 데이터를 계산이 이뤄지는 곳에서 더 가까운 위치에 저장하는 자료구조.

• 데이터 접근 비용은 알고리즘 효율성에 있어서 중요한 요소.
• 지역적(local) 데이터

11.1 캐시 소개

모든 데이터 저장소가 동등하지 않다.

• CPU 자체의 메모리(레지스터나 지역적 캐시)는 믿을 수 없을 만큼 빠르지만 매우 제한된 양의 데이터만 저장할 수 있다.
• 컴퓨터의 램은 더 큰 공간을 제공하지만 속도는 CPU 레지스터나 내부 캐시보다 느리다.
• 하드 드라이브는 램보다 크지만 램보다 느리다.
• 네트워크 호출을 통해 전체 인터넷과 같은 거대한 저장소에 접근할 수 있지만 그에 상응하는 오버헤드가 발생한다.

캐시는 우리보다 한 걸음 앞에서 비싼 데이터에 접근한다. 원격 서버를 호출하거나 지역 하드 드라이브에 접근하기 전에, 캐시에 지역적으로 데이터가 저장되어 있는지 검사한다.

• 데이터를 캐시에서 찾은 경우 캐시 적중(hit)이라고 부른다.
  • 캐시가 적중하면 탐색을 멈추고 더 비싼 저장소를 호출하는 일을 피할 수 있다.
• 데이터를 캐시에서 찾을 수 없는 경우를 캐시 실패(miss)라고 부른다.

제공할 메모리 용량이 클수록 속도가 느려지는 것이 캐시의 기본적인 트레이드 오프 관계

캐시가 가득 차면 어떤 데이터를 유지하고 어떤 데이터를 교체할지 결정해야 한다.

• 교체된 데이터를 캐시에는 ‘만료된 데이터’라고 부른다.

11.2 LRU 만료와 캐시