읽고 나면 진짜 쉬워지는 자료 구조 - 11. 캐시

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

🔖 11.1 캐시 소개

용어 정리

• 메모리 계층에 따른 속도와 공간 크기에 대한 trade-off가 알고리즘의 성능에 어떤 영향을 미치는지 이해하는 것이 중요하다.

• 캐시는 우리보다 한 걸음 앞에서 비싼(데이터를 읽는 데에 더 많은 시간이 걸리는) 데이터에 접근한다.

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

• 데이터를 캐시에서 찾는 경우를 hit 이라고 부른다.

• 캐시가 hit되면 탐색을 멈추고 더 비싼 저장소를 호출하는 일을 피할 수 있다.

• 참고로 데이터를 캐시에서 찾을 수 없는 경우를 miss 라고 부른다.

다양한 캐시 방법

• 어떤 데이터를 교체할지 결정하기 위해 다양한 만료 전략을 사용한다.

• 데이터에 얼마나 자주 접근했는지 세어보는 방법,

• 가까운 미래에 데이터를 다시 사용할지 예측하는 방법 등이 있다.

🔖 LRU 만료와 캐시

LRU

• LRU는 최근에 사용한 정보를 캐시에 유지한다.

• LRU 캐시는 캐시 사용 시 우리가 직면하는 trade-off 유형을 잘 보여주는 방식이다.

• 이 캐시 전략의 직관적인 아이디어는 최근에 필요했던 정보에 다시 접근할 가능성이 높다는 것이다.

• 예를 들어, 같은 페이지 집합에 계속 접근한다면 이들 페이지의 변하지 않는 요소들을 지역적으로 저장하면 유리하다.

• 캐시가 가득 차면 가장 오래 전에 사용한 항목을 제거해 공간을 확보한다.

LRU 캐시 구축하기

• LRU 전략을 이용한 캐시는 임의의 원소를 찾는 직업과, 최근에 사용하지 않은 원소를 찾는 두 가지 작업을 지원해야 한다.

• 그리고 이 두 작업을 모두 빠르게 수행할 수 있어야 한다.

• 캐시의 목적은 데이터를 읽는 연산을 가속시키는 것이기 때문이다.

• 해시 테이블과 큐를 이용해 LRU 캐시를 만들 수 있다.

🔖 11.3 다른 만료 전략들

MRU 전략, LFU 전략

• MRU(Most Recently Used), LFU(Least Frequently Used)

• 앞서 소개한 LRU는 특정 캐시 아이템들 사이에서 공통 사용 패턴이 집중적으로 보이며, 캐시된 원소의 분포가 시간이 지남에 따라 변할 것으로 예상될 때 좋은 만료 전략이다.

• 이와 비교해 MRU 만료 전략은 반복 빈도가 낮은 항목에는 좋은 접근일 수 있다.

• 그리고 LFU 전략은 마지막으로 원소에 접근한 시점을 고려하는 대신, 전체 접근 횟수를 추적할 수 있다. 이 방법은 캐시된 항목들이 안정적으로 유지되는 경우에 유리하다.