게임 프로그래머 관점에서는 LRU Cache를 “자주 쓰는 게임 데이터를 빠르게 재사용하기 위한 캐시 관리 전략”으로 이해하면 편합니다. CPU 캐시 자체보다는, 실제 게임 코드에서 리소스·오브젝트·계산 결과 등을 제한된 메모리 안에서 관리하는 패턴으로 보는 게 더 실용적입니다.
1. LRU Cache 왜 필요한가?
게임에서는 같은 데이터를 반복해서 사용하는 경우가 많습니다.
예를 들어:
- 텍스처 / 메시 / 사운드 리소스
- 최근 방문한 맵이나 청크 데이터
- UI 이미지
- NPC 관련 데이터
- 서버에서 받아온 유저 정보
- 경로 탐색 결과
- 셰이더나 머티리얼 데이터
- 계산 비용이 큰 연산 결과
이런 데이터를 필요할 때마다 디스크에서 다시 로딩하거나 새로 계산하면 비용이 큽니다.
그래서 한 번 사용한 데이터를 일정량 메모리에 보관해 두고 다시 사용할 수 있도록 하는데, 이게 애플리케이션 수준의 Cache입니다.
문제는 메모리가 무한하지 않다는 것입니다.
따라서 캐시가 가득 차면 어떤 데이터를 버릴지 결정해야 하는데, LRU는
“가장 오랫동안 사용하지 않은 데이터부터 버리자.”
라는 정책입니다.
2. 게임 상황으로 생각해보기
오픈월드 게임에서 플레이어 주변의 맵 청크를 캐싱한다고 생각해봅시다.
현재 캐시에 다음 지역이 들어 있다고 가정합니다.
최근 사용
↓
[마을] → [숲] → [던전] → [해변]
↑
가장 오래됨플레이어가 최근에 마을과 숲을 돌아다녔고, 해변은 오래전에 방문했다고 합시다.
캐시가 가득 찬 상태에서 새로운 설산 지역 데이터를 로드해야 한다면 LRU는
[해변] 제거후
[설산] → [마을] → [숲] → [던전]처럼 관리할 수 있습니다.
그리고 플레이어가 다시 숲을 방문했다면 숲은 최근 사용 데이터가 됩니다.
[숲] → [설산] → [마을] → [던전]즉, 접근할 때마다 데이터의 최근 사용 순서가 변경됩니다.
3. 게임 프로그래밍에서 중요한 핵심
LRU Cache의 핵심 연산은 크게 두 가지입니다.
Get(Key)
Put(Key, Value)Get
데이터가 존재하면 반환하면서 해당 데이터를 가장 최근에 사용한 데이터(MRU) 로 변경합니다.
Before
A → B → C → D
Get(C)
After
C → A → B → D여기서 D가 가장 오래 사용되지 않은 데이터입니다.
Put
새로운 데이터를 넣습니다.
공간이 남아 있다면 그냥 추가합니다.
E → A → B → C하지만 캐시가 가득 찼다면 LRU 데이터부터 제거합니다.
A → B → C → D
↑
LRU
Put(E)
E → A → B → C
Key = (A, B)
Value = A에서 B까지 가는 Path즉 이런 느낌이야.
Put((A, B), path);예를 들어:
Key
(A, B)
Value
[A → C → D → B]이런 식이지.
캐시 내부를 단순화하면:
(A, B) → Path1
(C, D) → Path2
(E, F) → Path3
다만 실제 LRU 구현에서는 HashMap의 Value가 Linked List의 Node를 가리키는 경우가 많아서 여기서 헷갈릴 수 있어.
예를 들면 내부 구현은 이렇게 될 수 있어:
Dictionary<PathKey, LinkedListNode<CacheEntry>> map;여기서는 Dictionary 관점에서 보면:
Key = (A, B)
Value = LinkedList의 Node 참조그리고 그 Node 안에 실제 Path가 들어 있어.
class CacheEntry
{
public PathKey Key;
public Path Path;
}그래서 구조를 펼치면:
Dictionary
(A,B) ───────┐
▼
[Node]
│
├─ Key = (A,B)
└─ Path = A→C→D→B이 Node가 Linked List에도 들어가 있어.
MRU LRU
↓ ↓
[(A,B)] ↔ [(C,D)] ↔ [(E,F)]즉 두 레벨로 생각하면 안 헷갈려.
4. 왜 Double Linked List를 사용하는가?
LRU의 핵심은
데이터를 최근 사용 순서대로 정렬하는 것
입니다.
Double Linked List를 사용하면 노드를 중간에서 빼거나 앞에 다시 붙이는 작업을 O(1)에 할 수 있습니다.
Head Tail
MRU LRU
↓ ↓
[A] ⇄ [B] ⇄ [C] ⇄ [D]- Head : 가장 최근에 사용한 데이터
- Tail : 가장 오래 사용하지 않은 데이터
C를 사용했다면:
[C] ⇄ [A] ⇄ [B] ⇄ [D]
↑ ↑
MRU LRU이때 링크만 변경하면 되므로 빠르게 처리할 수 있습니다.
5. 그런데 Linked List만 사용하면 부족하다
게임 프로그래머 입장에서 이 부분이 꽤 중요합니다.
Linked List만 사용하면 특정 데이터를 찾기 위해 처음부터 검색해야 합니다.
A → B → C → D → E → ...C가 있는지 찾으려면 최악의 경우 O(N)입니다.
그래서 일반적인 LRU Cache 구현은
Hash Table + Doubly Linked List조합을 사용합니다.
구조는 대략 다음과 같습니다.
HashMap
────────────────────
"Orc" → Node C
"Knight" → Node A
"Dragon" → Node D
────────────────────
│
▼
Doubly Linked List
MRU LRU
↓ ↓
[A] ⇄ [C] ⇄ [B] ⇄ [D]HashMap을 이용하면 원하는 노드를 O(1) 평균 시간에 찾을 수 있고, Linked List로 최근 사용 순서를 O(1)에 변경할 수 있습니다.
따라서 평균적으로:
| 캐시 검색 | O(1) |
| 캐시 데이터 접근 | O(1) |
| 최근 사용 순서 변경 | O(1) |
| LRU 제거 | O(1) |
| 새로운 데이터 추가 | O(1) |
이것이 LRU Cache 구현에서 HashMap + Doubly Linked List 조합이 자주 등장하는 이유입니다.
6. 게임에서 어디에 사용할 수 있는가?
게임 개발에서는 특히 비싼 작업의 결과를 다시 사용할 가능성이 있을 때 활용할 수 있습니다.
예를 들어 맵 스트리밍 시스템을 생각할 수 있습니다.
Player 이동
↓
Map Chunk 요청
↓
LRU Cache 조회
/ \
Hit Miss
↓ ↓
바로 사용 Disk / Server Load
↓
Cache 저장최근 방문했던 지역으로 플레이어가 돌아온다면 디스크에서 다시 불러오는 대신 캐시 데이터를 사용할 수 있습니다.
또 다른 예시는 경로 탐색입니다.
Path Find
Start = A
End = B같은 경로 탐색 요청이 반복된다면
(A, B) → Path Result를 캐싱할 수 있습니다.
PathCache
(A,B) → Path1
(A,C) → Path2
(B,D) → Path3캐시가 가득 차면 오래 사용하지 않은 Path 결과를 제거합니다.
다만 게임에서는 맵이나 장애물이 실시간으로 변경될 수 있기 때문에 캐시 무효화(Cache Invalidation) 문제도 같이 고려해야 합니다.
Cache Invalidation은 쉽게 말하면:
캐시에 저장해둔 값이 더 이상 현재 게임 상태와 맞지 않을 때, 그 캐시를 폐기하거나 갱신하는 것
이야.
예를 들어 경로 탐색 결과를 캐싱했다고 해보자.
Start = A
End = B
Cache:
(A, B) → Path1처음에는 맵 상태가 이랬어.
A ─────── B그래서 Path1이 직선 경로였다고 하자.
그런데 게임 도중 갑자기 벽이 생겼어.
A ── X ── B
벽문제는 캐시에 아직도 예전 경로가 남아 있다는 거야.
Cache:
(A, B) → 기존 Path1이 상태에서 다시 Get(A, B)를 하면 캐시 히트가 발생해.
Cache Hit!
→ 기존 Path1 반환그런데 그 경로는 이제 벽을 뚫고 지나가는 잘못된 데이터야.
이게 바로 캐시 무효화 문제가 발생하는 대표적인 사례야.
왜 LRU만으로는 해결이 안 되나?
LRU는 이런 것만 판단해.
"이 데이터가 최근에 사용됐는가?"즉:
A → B → C → D
MRU LRU최근에 많이 쓰인 데이터를 유지할 뿐이지,
"이 데이터가 아직 유효한가?"는 판단하지 않아.
그래서 오래된 데이터가 최근에 계속 접근되고 있다면 오히려 캐시에 계속 살아남을 수도 있어.
예를 들어:
맵 변경 발생
↓
기존 Path가 잘못된 값이 됨
↓
하지만 계속 Get(Path)
↓
MRU로 계속 이동
↓
절대 제거되지 않음이런 상황도 가능해.
따라서:
LRU
= 언제 버릴지 결정
Cache Invalidation
= 데이터가 아직 맞는 값인지 결정서로 다른 문제야.
게임에서는 어떤 경우에 발생할까?
대표적으로 Path Finding Cache가 있어.
예를 들어:
PathCache[(Start, End)] = Path;를 저장했다고 하자.
그런데 게임에서 다음과 같은 일이 발생할 수 있어.
문이 닫힘
벽 생성
다리 파괴
오브젝트 이동
지형 변경
NavMesh 변경그러면 기존 경로는 잘못될 수 있어.
Before
A ───────── B
After
A ───█───── B
↑
장애물따라서 장애물이 변경되는 순간 관련 캐시를 지워줘야 해.
PathCache.erase(key);이게 가장 단순한 명시적 무효화야.
다른 예: 맵 청크 캐시
오픈월드 게임에서 청크를 캐싱한다고 해보자.
ChunkCache
(10, 20) → ForestChunk
(11, 20) → VillageChunk
(12, 20) → RiverChunk플레이어가 (11, 20) 지역의 건물을 파괴했다고 해보자.
서버나 실제 월드 데이터는:
VillageChunk
건물 있음 → 건물 없음으로 바뀌었는데 캐시에는 여전히 예전 상태가 있을 수 있어.
Cache
건물 있음
World
건물 없음이 상태를 보통 stale cache, 즉 오래되어 현실과 맞지 않는 캐시라고 해.
그래서 변경 시점에:
InvalidateChunk(11, 20);같이 캐시를 제거하거나 갱신해야 해.
그럼 어떻게 무효화하지?
게임에서는 몇 가지 방법을 많이 써.
1. 변경될 때 바로 제거
가장 직관적인 방식이야.
void OnObstacleAdded(...)
{
pathCache.Clear();
}장애물이 추가되면 경로 캐시 전체를 삭제하는 식.
장점은 아주 단순하고 안전해.
단점은:
경로 하나 변경
↓
모든 캐시 삭제
↓
다시 계산 엄청 많이 발생할 수 있다는 거야.
그래서 규모가 커지면 비효율적일 수 있어.
2. 영향을 받은 데이터만 제거
좀 더 정교하게 만들 수도 있어.
예를 들어 장애물이 (10, 10) 타일에 생겼다면:
그 타일을 지나가는 Path만 무효화하는 거야.
Cache:
Path A → 영향을 받음 → 삭제
Path B → 영향 없음 → 유지
Path C → 영향을 받음 → 삭제이 방식은 캐시 효율이 훨씬 좋아.
하지만 대신:
어떤 캐시가 어떤 월드 데이터에 의존하고 있는가?
를 추적해야 해서 구현 복잡도가 올라가.
3. Version을 두는 방식
게임 프로그래밍에서는 이 방식도 꽤 깔끔해.
예를 들어 NavMesh에 버전 값을 둔다고 하자.
int NavMeshVersion = 10;Path를 캐싱할 때 같이 저장해.
struct CachedPath
{
Path path;
int navMeshVersion;
};그러면:
Cache Path Version = 10
Current NavMesh Version = 10
→ Valid그런데 장애물이 변경되면:
NavMeshVersion++;해서:
Current Version = 11이 돼.
이제 캐시를 조회하면:
Cache Version = 10
Current Version = 11
→ Invalid이므로 다시 계산하는 거야.
코드 느낌으로 보면:
C#
Dictionary를 사용한다고 해보자.
class CachedPath
{
public Path Path { get; set; }
public int NavMeshVersion { get; set; }
}캐시는:
Dictionary<(Node start, Node end), CachedPath> cache = new();이렇게 만들 수 있어.
그럼 GetPath()는 대충:
Path GetPath(Node start, Node end)
{
if (cache.TryGetValue((start, end), out CachedPath cached))
{
if (cached.NavMeshVersion == NavMeshVersion)
{
return cached.Path;
}
}
Path newPath = CalculatePath(start, end);
cache[(start, end)] = new CachedPath
{
Path = newPath,
NavMeshVersion = NavMeshVersion
};
return newPath;
}
특히:
cache.TryGetValue(...)를 많이 써.
핵심 흐름은 이거야.
경로 요청
↓
캐시에 있나?
↓
있으면 버전이 최신인가?
↓
최신이면 캐시 반환
↓
아니면 새로 계산
↓
캐시에 저장
↓
반환이 방식이 좋은 이유는 일일이 캐시를 찾아서 삭제하지 않아도 된다는 점이야.
<NavMeshVersion은 "이 캐시가 현재 맵 상태를 기준으로 만들어진 게 맞는지" 확인하는 유효성 검사 값이다.>
캐시가 없거나 오래됐다면 새로 계산
Path newPath = CalculatePath(start, end);여기서 실제 길찾기 알고리즘이 동작하는 거야.
예를 들어:
AStar(start, end);같은 무거운 연산이라고 보면 돼.
Cache Hit
→ CalculatePath 안 함
Cache Miss
→ CalculatePath 실행
Cache는 있지만 Version 불일치
→ CalculatePath 실행
논리적으로는 이런 데이터가 들어가는 셈이야.
Key
(A, B)
Value
Path = 새로 계산한 경로
Version = 현재 NavMeshVersion예를 들어:
(A, B)
→ Path1
→ Version 6그러면 다음에 다시
GetPath(A, B);를 호출했을 때 맵 버전이 아직 6이면 계산할 필요가 없어.
TTL 방식도 있음
웹이나 서버 캐시에서 굉장히 많이 사용하는 방식인데 게임에서도 사용할 수 있어.
TTL은 Time To Live야.
"이 캐시는 5초 동안만 믿는다."예를 들어:
CachedData
{
Value value;
float expireTime;
};저장할 때:
expireTime = CurrentTime + 5.0f;조회할 때:
if (CurrentTime < expireTime)
{
return cache;
}5초가 지나면:
Expired
→ 다시 계산하는 거야.
다만 실시간 경로처럼 정확성이 매우 중요하면 TTL만 쓰기에는 위험할 수 있어.
벽이 생긴 직후부터 TTL 만료까지 5초 동안 잘못된 경로를 사용할 수도 있으니까.
Dirty Flag도 게임에서 많이 쓰는 개념이야
예를 들어:
bool isDirty = false;캐시와 관련된 데이터가 변경되면:
isDirty = true;를 설정해.
그리고 다음 조회 시:
if (isDirty)
{
Recalculate();
isDirty = false;
}이렇게 하는 거야.
예를 들어 UI에서:
Player Gold = 100
UI Cache:
"Gold: 100"플레이어가 돈을 얻으면:
Gold = 150그 순간 UI 텍스트를 바로 다시 계산하는 대신:
goldUI.isDirty = true;해놓고 다음 UI 업데이트 때:
Gold: 150으로 갱신할 수 있어.
이것도 넓은 의미에서 캐시 무효화 패턴이라고 볼 수 있어.
게임 프로그래머 입장에서 제일 중요한 구분
이렇게 기억하면 좋아.
LRU Cache
↓
메모리가 부족할 때
"뭘 버릴까?"반면:
Cache Invalidation
↓
원본 데이터가 변경됐을 때
"이 캐시를 아직 믿어도 되나?"즉 두 문제는 독립적이야.
실제 캐시는 보통 둘 다 가지고 있어.
Cache Entry
│
├─ Key
├─ Value
├─ Last Used Time ← LRU
├─ Version ← Invalidation
├─ Expire Time ← TTL
└─ Dirty Flag ← Invalidation게임 예제로 하나로 묶으면 이런 구조가 돼.
struct CachedPath
{
Path path;
int navMeshVersion; // 유효성 검사
uint64_t lastUsedFrame; // LRU
};조회할 때:
GetPath(A, B)하면:
1. Cache에 존재하는가?
↓
Yes
↓
2. NavMesh Version이 같은가?
↓
Yes
↓
3. 캐시 사용
↓
4. MRU로 이동Version이 다르면:
Cache Hit은 했지만
데이터는 Invalid
↓
기존 데이터 폐기
↓
Path 다시 계산
↓
Cache 갱신즉 "캐시에 있다"와 "사용 가능한 캐시다"는 같은 말이 아니다라는 게 핵심이야.
게임 프로그래머 관점에서 이걸 딱 한 문장으로 정리하면:
캐시 무효화는 게임의 실제 상태가 변경되었을 때, 과거 상태를 기반으로 저장된 캐시를 더 이상 사용하지 않도록 만드는 과정이다.
그리고 실무에서는 보통 LRU + Versioning/Dirty Flag 조합을 이해해두면 꽤 많은 캐시 시스템을 이해하기 쉬워져.
- Version: 여러 캐시가 하나의 공통 상태에 의존할 때 좋음
- Dirty Flag: 특정 객체나 특정 캐시 하나가 바뀌었는지만 보면 될 때 좋음.
버전 체크는 “지금 당장 전체 캐시를 순회해서 잘못된 항목을 찾고 삭제하는 비용”을 없애주는 방식이라고 보면 돼.
다만 주의할 점은, 이렇게 하면 오래된 캐시가 메모리에는 계속 남아 있을 수 있다는 거야. 그래서 실제 구현에서는 나중에 LRU eviction이나 주기적 정리로 메모리까지 같이 회수해주는 경우가 많아.
주기적 정리는 완전히 정해진 보편적 기준은 없고 꽤 많이 경험과 프로파일링에 의존해. 다만 그냥 감으로만 정하는 건 아니고, 몇 가지 실전 기준이 있어.
보통은 이런 걸 봐:
예를 들어 경로 캐시가 500MB까지 커졌는데 그중 300MB가 이미 구버전이면, 그건 정리 압박이 큰 상태야.
그래서 실무에서는 보통 시간 기준보다 메모리 기준을 더 신뢰해.
또 프레임 게임에서는 한 번에 전부 지우기보다:
이번 프레임 20개
다음 프레임 20개
다음 프레임 20개처럼 나눠서 정리하는 경우도 많아. GC나 컨테이너 재배치, destructor 비용 때문에 한 프레임에 몰아서 처리하면 hitch가 생길 수 있으니까.
그래서 정리 기준을 잡을 때는 보통 이렇게 가면 좋아:
1. 최대 메모리 예산 정함
2. 캐시 hit/miss 측정
3. invalid entry 비율 측정
4. 프레임 타임 spike 확인
5. 실제 플레이 패턴 보고 threshold 조정즉,
알고리즘 선택은 이론으로 시작하고, 정리 주기와 임계값은 프로파일링으로 튜닝한다
그리고 한 가지 더 중요한 포인트는 “주기적으로 정리한다”가 꼭 시간 기반이라는 뜻은 아니다라는 거야. 실제로는:
매 10초마다 정리보다
메모리 80% 넘으면 정리
invalid entry가 일정 수 넘으면 정리
로딩 화면에서 정리
씬 전환 시 정리
idle frame에 조금씩 정리이런 이벤트/상태 기반이 더 자연스러운 경우가 많아.
한마디로 정리하면:
명확한 만능 숫자는 없고, 메모리 예산 + 재계산 비용 + 프레임 안정성 + 실제 플레이 패턴을 기준으로 프로파일링해서 정한다.
7. 게임 개발에서 주의할 점
LRU가 항상 최고의 선택은 아닙니다.
LRU의 기본 가정은
최근에 사용한 데이터라면 가까운 미래에도 다시 사용할 가능성이 높다.
입니다.
즉, 시간적 지역성(Temporal Locality) 을 이용합니다.
게임에서도 이 가정이 잘 맞는 상황이 많습니다.
예를 들어 플레이어가
마을 → 숲 → 던전 → 숲 → 마을처럼 최근 방문했던 지역을 다시 방문한다면 LRU가 효과적입니다.
반면 다음처럼 데이터를 한 번씩 순차적으로 사용하는 경우에는:
A → B → C → D → E → F → G → H이전 데이터가 다시 사용되지 않으므로 캐시 효율이 떨어집니다.
또한 실제 게임 엔진에서는 단순히 항목 개수만 가지고 캐시 용량을 결정해서는 안 되는 경우도 많습니다.
Texture A = 4 MB
Texture B = 200 MB
Texture C = 8 MB모두 한 개의 항목이지만 메모리 크기는 전혀 다르기 때문입니다.
그래서 실제 리소스 캐시에서는
MaxCacheSize = 2GB;
CurrentCacheSize = ...처럼 메모리 사용량을 기준으로 eviction(내쫓는)을 수행하는 방식도 많이 고려하게 됩니다.
한 줄로 정리
게임 프로그래머 기준으로 LRU Cache를 정리하면:
제한된 메모리 안에서 최근에 사용한 게임 데이터를 유지하고, 공간이 부족하면 가장 오랫동안 사용하지 않은 데이터를 제거하는 캐시 관리 방식이다.
그리고 구현 측면에서는 이것만 기억해도 좋습니다.
LRU Cache
│
├─ HashMap
│ └─ 데이터 빠르게 찾기 → O(1)
│
└─ Doubly Linked List
└─ 최근 사용 순서 관리 → O(1)
Head = Most Recently Used (MRU)
Tail = Least Recently Used (LRU)특히 “Double Linked List만 구현하면 LRU Cache다”가 아니라, 실전에서는 보통 HashMap까지 결합해야 조회와 교체를 모두 O(1)로 만들 수 있다는 점이 핵심입니다.