캐시의 지역성 원리에 대해 설명해주세요

면접용 답변

캐시는 프로그램이 데이터를 접근하는 지역성 원리를 기반으로 동작하고, 시간 지역성과 공간 지역성으로 나뉩니다.시간 지역성은 최근에 접근한 데이터가 다시 접근될 가능성이 높다는 것을 의미하고, 공간 지역성은 인접한 데이터가 곧 접근될 가능성이 높다는 것을 뜻합니다.

개념 정리

캐시란?

• 주 기억장치보다 접근 속도가 빠른 작은 저장 공간

• 자주 사용하는 데이터를 임시로 저장해서 성능을 높인다.

• CPU 캐시, 디스크 캐시, 웹 캐시 등 다양한 형태가 존재한다.

캐시의 지역성 원리

지역성 종류	설명
시간 지역성	최근에 접근된 데이터는 가까운 미래에 다시 접근될 가능성이 높다.
공간 지역성	현재 접근한 데이터의 근처에 저장된 데이터도 곧 접근될 가능성이 높다.

예시

- 시간 지역성: 반복문에서 같은 변수를 여러 번 참조
- 공간 지역성: 배열을 순차적으로 탐색할 때 인접한 메모리 접근

중요성

• 캐시 메모리는 지역성 원리를 기반으로 동작한다.

• 자주 접근하는 데이터를 빠르게 제공해서 성능을 향상시킬 수 있다.

• 다양한 컴퓨팅 환경에서 광범위하게 사용된다. (ex. CPU 캐시, 데이터베이스, 브라우저)

  • DB: 자주 조회되는 결과를 Redis 같은 인메모리 캐시에 저장한다.

  • 브라우저: 이미지, 스크립트를 로컬 캐시에 저장해 페이지 로딩 속도를 높인다.

  • CPU: 자주 실행되는 루프나 함수의 명령어가 L1 캐시에 유지된다.

지역성 원리를 활용한 캐시 전략 예시

전략	설명
Prefetching	공간 지역성을 활용해 인접 데이터를 미리 가져온다.
LRU (Least Recently Used)	시간 지역성을 활용해 가장 오래 사용하지 않은 데이터를 제거한다.

꼬리 질문

• 캐시 미스가 발생하는 경우 어떤 현상이 발생하고, 이를 줄이기 위한 방법에는 어떤 것이 있을까요?

• 코드 관점에서 시간/공간 지역성을 높이려면 어떤 방식으로 작성하면 좋을까요?

• 공간 지역성이 낮은 데이터 구조의 예시로는 어떤 것이 있을까요?