Cache: 지역성을 이용해 메모리 접근 속도 격차를 줄이는 계층 구조
CPU와 메인 메모리 사이의 속도 차이를 완화하기 위해 존재하는 캐시 메모리의 동작 원리를 다룬다. 시간 지역성과 공간 지역성이 왜 캐시 적중률을 높이는지, 캐시 라인과 연관 매핑 방식이 어떻게 동작하는지 설명한다. CPU 캐시부터 애플리케이션 레벨 캐싱까지 개념이 확장되는 과정도 함께 짚는다.
1. 개념
캐시(Cache)는 CPU와 메인 메모리(DRAM) 사이의 속도 격차를 줄이기 위해 존재하는 작고 빠른 저장 장치다. CPU 레지스터 접근 속도는 1 사이클 수준이지만 메인 메모리 접근은 보통 100~300 사이클 이상 걸린다. 이 간극을 메우기 위해 SRAM 기반의 L1, L2, L3 캐시가 CPU와 메모리 사이에 계층적으로 배치된다.
캐시는 최근에 사용했거나 곧 사용될 가능성이 높은 데이터를 미리 저장해두는 방식으로 동작한다. 이때 데이터는 바이트 단위가 아니라 캐시 라인(cache line) 단위로 저장되며, 대부분의 x86/ARM 아키텍처에서 캐시 라인 크기는 64바이트다.
2. 왜 사용하는가
CPU 클럭 속도는 지난 수십 년간 크게 향상되었지만 메모리 접근 지연시간(latency)은 그만큼 줄어들지 않았다. 이 격차를 "메모리 벽(memory wall)"이라고 부른다. 캐시가 없다면 CPU는 매 명령마다 메인 메모리를 기다려야 하므로 연산 능력을 제대로 활용할 수 없다.
캐시는 다음 두 가지 지역성(locality) 원리를 기반으로 이 문제를 해결한다.
- 시간 지역성(temporal locality): 한 번 접근한 데이터는 가까운 미래에 다시 접근될 가능성이 높다.
- 공간 지역성(spatial locality): 어떤 주소에 접근했다면 그 주변 주소도 곧 접근될 가능성이 높다.
이 두 원리 덕분에 실제 프로그램은 무작위로 메모리에 접근하지 않고 특정 패턴을 반복하며, 캐시는 이 패턴을 이용해 적중률(hit rate)을 높인다.
3. 동작 원리
캐시 계층 구조
일반적인 현대 CPU는 다음과 같은 계층을 가진다.
| 계층 | 용량(대략) | 접근 지연시간(대략) | 공유 범위 | |---|---|---|---| | L1 (I/D 분리) | 32~64KB | 4~5 사이클 | 코어 전용 | | L2 | 256KB~1MB | 10~20 사이클 | 코어 전용 또는 일부 공유 | | L3 | 8~32MB | 30~70 사이클 | 여러 코어 공유 | | 메인 메모리(DRAM) | GB 단위 | 100~300 사이클 | 전체 시스템 |
정확한 수치는 CPU 세대와 제조사에 따라 달라지므로 위 표는 대략적인 범위로 이해해야 한다.
캐시 미스의 종류
- 필수 미스(compulsory miss): 처음 접근하는 데이터라서 캐시에 없는 경우.
- 용량 미스(capacity miss): 캐시 용량이 작아서 필요한 데이터를 모두 담지 못하는 경우.
- 충돌 미스(conflict miss): 캐시 매핑 방식의 제약으로 다른 데이터가 같은 위치를 두고 경쟁하는 경우.
매핑 방식
캐시는 메모리 주소를 캐시 라인에 매핑할 때 세 가지 방식 중 하나를 쓴다.
- 직접 매핑(direct mapped): 각 메모리 블록이 캐시의 정확히 한 위치에만 매핑된다. 구현이 단순하지만 충돌 미스가 잦다.
- 완전 연관 매핑(fully associative): 어떤 캐시 라인에도 저장될 수 있다. 충돌 미스는 줄지만 검색 비용이 크다.
- N-way 연관 매핑(set associative): 위 두 방식의 절충안으로, 실제 CPU 캐시 대부분이 이 방식을 쓴다(예: 8-way L2 캐시).
캐시 친화적 접근 패턴
배열을 순회할 때 메모리 주소 순서대로 접근하면 공간 지역성을 활용해 캐시 적중률이 높아진다. 반대로 큰 보폭(stride)으로 건너뛰며 접근하면 매번 새로운 캐시 라인을 불러와야 하므로 미스가 늘어난다.
4. 코드 예제
2차원 배열을 행 우선(row-major)으로 순회하는 것과 열 우선으로 순회하는 것의 차이를 Python으로 확인한다. Python의 리스트는 C 배열처럼 메모리에 연속 배치되지 않지만, NumPy 배열은 실제로 연속된 메모리 블록을 사용하므로 이 차이를 관찰할 수 있다.
import numpy as np
import time
N = 4000
matrix = np.random.rand(N, N)
# 행 우선 순회: 메모리 상에서 연속된 주소를 순서대로 접근 (캐시 친화적)
start = time.perf_counter()
total = 0.0
for i in range(N):
for j in range(N):
total += matrix[i, j]
row_major_time = time.perf_counter() - start
# 열 우선 순회: 매 접근마다 큰 보폭으로 건너뜀 (캐시 비친화적)
start = time.perf_counter()
total = 0.0
for j in range(N):
for i in range(N):
total += matrix[i, j]
col_major_time = time.perf_counter() - start
print(f"행 우선 순회 시간: {row_major_time:.4f}초")
print(f"열 우선 순회 시간: {col_major_time:.4f}초")이 코드는 Python 인터프리터 오버헤드 때문에 절대 실행 시간 자체는 캐시 효과보다 훨씬 크지만, 상대적으로 열 우선 순회가 행 우선 순회보다 느리게 나오는 경향은 관찰할 수 있다. C나 Rust처럼 인터프리터 오버헤드가 없는 언어에서는 이 차이가 훨씬 뚜렷하게 나타난다.
5. 시간 복잡도 또는 성능 특성
캐시 자체는 알고리즘의 점근적 시간 복잡도(예: O(n), O(log n))를 바꾸지 않는다. 하지만 동일한 빅오 표기법의 알고리즘이라도 캐시 적중률에 따라 실제 실행 시간(wall-clock time)은 수 배에서 수십 배까지 차이 날 수 있다.
예를 들어 이진 탐색 트리(BST)는 O(log n) 탐색을 제공하지만 노드가 메모리 여기저기 흩어져 있어 캐시 미스가 잦다. 반면 캐시 친화적으로 설계된 B-트리는 노드 하나에 여러 키를 담아 캐시 라인을 최대한 활용하므로, 이론적 복잡도는 비슷해도 실제 성능은 훨씬 우수하다. 이것이 데이터베이스 인덱스가 이진 트리가 아니라 B-트리 계열을 쓰는 이유 중 하나다.
6. 실무 사용 사례
- CPU 캐시 관점: 반복문에서 다차원 배열을 순회할 때는 메모리 배치 순서(행 우선인지 열 우선인지)에 맞춰 순회 순서를 정하면 성능이 개선된다.
- 자료구조 선택: 연결 리스트(linked list)보다 배열 기반 자료구조(동적 배열, 예: Python list, C++ vector)가 캐시 지역성 면에서 유리한 경우가 많다.
- 데이터베이스: B-트리 인덱스, 페이지 단위 I/O, 버퍼 풀(buffer pool)은 모두 캐시 지역성을 극대화하려는 설계다.
- 애플리케이션 레벨 캐싱: Redis나 Memcached 같은 인메모리 캐시는 CPU 캐시와 동일한 철학, 즉 "자주 쓰는 데이터를 빠른 저장소에 미리 둔다"는 원리를 애플리케이션 계층으로 확장한 것이다.
- 컴파일러 최적화: 루프 타일링(loop tiling), 루프 순서 변경 같은 최적화 기법은 모두 캐시 적중률을 높이기 위한 것이다.
7. 주의할 점
- 캐시는 자동으로 동작하는 하드웨어 메커니즘이므로 프로그래머가 직접 캐시 라인을 제어할 수는 없다. 다만 데이터 배치와 접근 패턴을 설계함으로써 간접적으로 영향을 줄 수 있다.
- 거짓 공유(false sharing) 문제에 주의해야 한다. 서로 다른 스레드가 각각 다른 변수를 수정하더라도 그 변수들이 같은 캐시 라인에 있으면, 캐시 일관성 프로토콜(cache coherence protocol) 때문에 불필요한 캐시 무효화가 반복되어 성능이 크게 떨어진다.
- 멀티스레드 환경에서 L1/L2 캐시는 코어별로 독립적이고 L3는 공유되는 경우가 많으므로, 코어 간 데이터 공유가 잦은 워크로드는 L3 캐시 크기와 지연시간을 고려해야 한다.
- 마이크로벤치마크로 캐시 효과를 측정할 때는 JIT 컴파일, 분기 예측, OS 스케줄링 등 다른 요인이 섞여 결과가 왜곡될 수 있으므로 해석에 주의해야 한다.
8. 핵심 정리
캐시는 시간 지역성과 공간 지역성을 이용해 CPU와 메인 메모리 사이의 속도 격차를 줄이는 계층적 저장 장치다. 캐시 라인 단위로 데이터를 저장하고 N-way 연관 매핑 방식으로 주소를 배치하며, 필수/용량/충돌 미스라는 세 가지 원인으로 성능이 좌우된다. 알고리즘의 점근적 복잡도만으로는 설명되지 않는 실제 성능 차이는 대부분 캐시 지역성에서 비롯되며, 이 원리는 CPU 캐시뿐 아니라 데이터베이스 인덱스나 Redis 같은 애플리케이션 레벨 캐싱 설계에도 그대로 적용된다.