271. 캐시 교체 알고리즘 (Replacement Policy)

핵심 인사이트 (3줄 요약)

  1. 본질: 캐시 교체 알고리즘은 캐시 메모리(또는 특정 세트)가 100% 꽉 차서 더 이상 새 데이터를 넣을 빈 공간이 없을 때, **"누구를 희생양으로 쫓아내야 다음번 적중률(Hit Ratio) 타격을 최소화할 수 있을까?"**를 결정하는 통계적 생존 게임의 룰이다.
  2. 가치: 프로그램의 '시간적 지역성(Temporal Locality)'이라는 인간의 코딩 습관을 통계적으로 신뢰하여, 완벽한 미래(OPT)를 알 수 없는 기계가 한정된 자원 속에서 최적의 결정을 내리도록 돕는 하드웨어 인공지능의 시초격이다.
  3. 융합: 하드웨어 캐시(L1/L2)뿐만 아니라, 운영체제의 가상 메모리 페이지 교체(Page Replacement), 데이터베이스의 버퍼 풀(Buffer Pool), 웹 브라우저의 CDN 캐싱까지 IT 전반의 모든 병목 구간에서 동일한 철학으로 동작하는 프랙탈(Fractal) 개념이다.

Ⅰ. 개요 및 필요성

  • 개념: 캐시 교체 정책은 캐시에 새로운 블록(데이터)을 적재해야 하는데 남은 공간이 없을 경우, 기존에 상주하던 블록 중 하나를 선택하여 메인 메모리로 방출(Eviction)하고 그 자리를 확보하는 규칙 체계다.

  • 필요성: 만약 캐시가 꽉 찼다고 해서 아무 데이터나 랜덤(Random)으로 쫓아내면 어떻게 될까? 하필 다음 클럭에 CPU가 바로 써야 할 가장 중요한 반복문(Loop) 변수를 쫓아냈다면, CPU는 즉시 캐시 미스(Miss Penalty 100ns)를 맞고 시스템이 마비된다. 따라서 캐시는 "앞으로 가장 오랫동안 안 쓸 것 같은 데이터"를 귀신같이 솎아내어 버림으로써 적중률 99%를 강제로 수호해야 할 생존의 의무가 있다.

  • 💡 비유: 스마트폰의 저장 용량이 100% 꽉 차서 새로운 게임을 깔 수 없을 때, **"내일 또 할 것 같은 인생 게임은 남겨두고, 다운받은 지 1년 넘게 한 번도 안 켠 고전 게임을 먼저 삭제하자"**라고 판단하는 뇌의 의사결정 과정과 완벽히 똑같습니다.

  • 등장 배경: 캐시의 매핑 방식 중 1-Way(직접 매핑)는 지정석이라 꽉 차면 묻지도 따지지도 않고 기존 데이터를 쫓아내므로 교체 알고리즘이 필요 없다. 하지만 N-Way 세트 연관 매핑과 완전 연관 매핑이 표준이 되면서, 4개의 Way(방) 중 누구를 방 빼게 할지 선택해야 하는 고민이 생겨났다. 이를 해결하기 위해 수학자 벨라디의 최소 최적 모델을 거쳐 LRU(Least Recently Used)라는 황금률이 정착되었다.

┌──────────────────────────────────────────────────────────────┐
│           캐시 꽉 참! 누구를 쫓아낼 것인가? (교체 알고리즘 비교 도식)      │
├──────────────────────────────────────────────────────────────┤
...

- **📢 섹션 요약 비유**: 냉장고(캐시)가 꽉 찼을 때, 어제 마트에 사 온 우유(최근 사용)는 버리지 않고, 구석에 1년 동안 처박혀 손도 안 댄 유자청(LRU, 가장 오랫동안 안 씀)을 제일 먼저 쓰레기통에 버리는 아주 합리적인 주부의 살림꾼 지혜입니다.

---

## Ⅱ. 아키텍처 및 핵심 원리

### LRU (Least Recently Used)의 완벽함과 하드웨어적 구현 한계

LRU는 "가장 오랫동안 사용되지 않은" 블록을 쫓아낸다. 이론적으로는 완벽하지만, 물리적인 반도체 회로로 구현할 때는 피가 마르는 제약이 따른다.
- **구현의 어려움**: 4-Way 캐시만 되어도, 4개의 방이 쓰일 때마다 순위(Rank)를 매번 1등부터 4등까지 재정렬해야 한다. CPU가 1클럭 만에 1번 방을 건드리면, 1번 방을 1등으로 올리고 나머지 방의 카운터를 다 깎는 로직이 들어가야 한다.
- **Pseudo-LRU (가상 LRU)의 등장**: Way가 8개, 16개로 늘어나면 완벽한 LRU 순위를 매기는 회로 자체가 너무 느려져서 오히려 캐시 속도를 잡아먹는다. 그래서 인텔과 AMD는 **Tree PLRU (Tree Pseudo-LRU)**라는 트리 구조의 1비트 스위치를 써서 대충 "어느 쪽이 오래됐더라?" 하고 뭉뚱그려 추적하는 가벼운 알고리즘을 사용한다. 완벽한 LRU보다 구현이 수십 배 싸고 빠르면서도 성능은 LRU의 95%를 따라간다.

### 캐시 오염 (Cache Pollution)과 방어막
LRU의 치명적 약점은 **'순차적 풀 스캔(Full Scan)'**에 한 방에 털린다는 것이다. 바이러스 검사 프로그램이 100GB짜리 하드디스크를 순서대로 한 번씩만 쫙 읽는다면 이 데이터들은 두 번 다시 쓰이지 않을 쓰레기 데이터들이다. 하지만 LRU 알고리즘은 이 쓰레기들을 캐시에 가득 채우고, 정작 내일 당장 필요한 '운영체제 핵심 파일'을 오래됐다는 이유로 캐시 밖으로 쫓아내 버린다. 이를 캐시 오염이라 하며, 최신 CPU들은 데이터를 훔쳐보는 **스레드 모니터(MRU/LIP)**를 통해 "얘는 풀 스캔하는 놈이네?"라고 판단하면 캐시에 아예 안 넣고 바이패스(Bypass)시키는 꼼수 하드웨어를 탑재하고 있다.

- **📢 섹션 요약 비유**: 단골손님(자주 쓰는 데이터)들을 위해 VIP 라운지(캐시)를 비워둬야 하는데, 갑자기 단체 관광객(풀 스캔 데이터) 1,000명이 한 번 구경하러 들어와서는 VIP들을 다 내쫓아버리는 사태가 바로 캐시 오염입니다. 입구 컷을 잘해야 합니다.

---

## Ⅲ. 비교 및 연결

### 주요 교체 알고리즘 (Replacement Policies) 트레이드오프

| 알고리즘 | 교체 기준 | 장점 (Pros) | 단점 (Cons) | 적용 분야 |
|:---|:---|:---|:---|:---|
| **OPT** | 미래에 가장 늦게 쓰일 블록 | 이론상 미스율 최저 | 미래를 알 수 없어 **구현 절대 불가** | 알고리즘 성능 평가 벤치마크 기준점 |
| **FIFO** | 가장 먼저 들어온 늙은 블록 | 큐로 구현해 하드웨어 초간단 | 자주 쓰는 데이터도 늙었다고 쫓아냄 | 단순 버퍼, 아주 작은 임베디드 |
| **LRU** | 가장 오랫동안 안 쓴 블록 | **시간적 지역성 완벽 반영, 적중률 최고** | Way가 늘어나면 하드웨어 카운터 갱신 비용 폭증 | **CPU L1/L2 캐시, OS 페이징 (표준)** |
| **LFU** | 참조 횟수가 가장 적은 블록 | 장기적인 핫 데이터 보호 가능 | 반짝 인기 끌고 버려진 데이터가 평생 안 쫓겨남 | 웹 브라우저 캐시, CDN 엣지 서버 |
| **Random**| 주사위 굴려서 무작위 쫓아냄| 오버헤드 0, 전력 소모 0, 의외로 쏠림 방어 | 운 나쁘면 최고 핵심 데이터가 날아감 | ARM 계열 하위 캐시, 시뮬레이션용 |

### 벨라디의 모순 (Bélády's Anomaly)
FIFO 알고리즘을 쓸 때 발생하는 현상이다. 상식적으로 캐시 방을 3개에서 4개로 늘려주면 캐시 미스가 줄어들거나 같아야 한다. 그런데 FIFO를 쓰면 캐시 방을 늘려줬는데 오히려 캐시 미스가 더 늘어나는 미친 수학적 역전 현상이 터진다. 이 현상 때문에 FIFO는 메인스트림 교체 정책에서 영구 퇴출당했으며, LRU나 스택 알고리즘 계열만이 캐시 크기를 키웠을 때 성능 향상을 100% 보장하는 안전한 모델로 살아남았다.

- **📢 섹션 요약 비유**: FIFO는 군대에서 "짬(기수)이 제일 높은 사람 무조건 전역!"시키는 룰입니다. 짬이 높아도 군대 핵심 간부(자주 쓰는 변수)라면 전역시키면 안 되는데 무식하게 쫓아내니 부대가 마비됩니다. 그래서 LRU처럼 "짬이 아니라, 최근에 일 안 한 사람부터 쫓아내는" 성과제가 필요한 것입니다.

---

## Ⅳ. 실무 적용 및 기술사 판단

### 실무 시나리오

1. **데이터베이스(DBMS) 버퍼 풀(Buffer Pool)의 변형 LRU 최적화**
   MySQL InnoDB 엔진에서 풀 스캔 쿼리가 돌 때마다 전체 메모리 버퍼가 다 날아가는(캐시 오염) 현상 방어. MySQL 등 엔터프라이즈 DB는 순수 LRU를 절대 쓰지 않는다. **Midpoint Insertion Strategy (변형 LRU)**를 사용한다. 새로운 데이터가 캐시에 들어올 때 LRU 리스트의 맨 앞(MRU)에 넣지 않고, 전체 리스트의 5/8 지점에 찌그러뜨려 넣는다. 만약 이 데이터가 정말 중요해서 한 번 더 불리면 그때 1등으로 올려주고, 풀 스캔용 쓰레기 데이터라면 한 번 읽히고 다시 안 불려서 자연스럽게 꼬리(LRU)로 밀려나 초고속으로 방출된다.

2. **Redis 인메모리 캐시 서버(Maxmemory-policy) 튜닝**
   사용자 세션을 저장하는 Redis 서버 메모리가 100% 꽉 차서 OOM 에러로 서버가 죽어버리는 현상. 레디스 아키텍트는 캐시가 꽉 찼을 때 어떤 키(Key)를 버릴지 교체 알고리즘 정책(`maxmemory-policy`)을 명시해야 한다. `allkeys-lru`는 전체 키 중 가장 오래 안 쓴 것을 버린다. `volatile-lru`는 TTL이 설정된 키 중에서만 오래 안 쓴 것을 버린다. `allkeys-random`은 하드웨어 리소스가 부족할 때 무식하게 랜덤으로 버려서 오버헤드를 막는다.

3. **하드웨어 캐시 구조 (ARM vs x86)에 따른 코드 성능 차이**
   특정 영상 처리 알고리즘이 인텔 CPU에서는 쌩쌩 날아다니는데, 저전력 ARM 프로세서에서는 프레임이 심각하게 끊기는 현상. 두 프로세서의 L1/L2 캐시 교체 알고리즘 차이일 확률이 높다. 인텔/AMD는 덩치가 커서 정교한 Tree-PLRU 알고리즘을 칩에 박아 넣어 시간적 지역성을 기가 막히게 추적하지만, 구형 ARM이나 초저전력 임베디드 칩은 전기를 아끼려고 가끔 **Random(랜덤) 교체 정책**이나 단순 FIFO를 쓴다. 프로그래머가 인텔의 LRU 성능만 믿고 워킹셋을 꽉꽉 채워놓는 코드를 짰다 하더라도, ARM의 Random 정책이 핵심 변수를 재수 없게 날려버리면 스톨이 터진다.

### 안티패턴
- **단일 스레드에서의 거대 배열 순환 반복**: 배열 크기가 캐시 용량(예: L2 1MB)보다 아주 약간 더 큰 1.1MB라고 치자. 루프문이 처음부터 끝까지 반복될 때, LRU 정책의 최악의 저주가 시작된다. 앞부분 데이터를 캐시에 넣다가 1MB를 꽉 채운 후, 나머지 0.1MB를 넣기 위해 가장 앞부분 데이터를 쫓아낸다. 다음 루프 시작 시 앞부분 데이터가 또 필요한데 방금 쫓겨나서 없다. 이 현상이 무한 반복되며 적중률이 0%로 수렴한다(캐시 스래싱). 반드시 배열을 0.5MB씩 잘라서 도는 타일링(Loop Tiling)이 필수적이다.

- **📢 섹션 요약 비유**: LRU 알고리즘의 최대 약점은 '엄청나게 긴 회전초밥 레일'입니다. 내 배가 10접시 분량인데 회전초밥 레일 위에는 11접시가 돌고 있습니다. 첫 번째 접시를 먹으려고 손을 뻗는 순간 방금 버린 접시라 무조건 새 접시를 기다려야 하는 영원한 엇갈림의 고통이 발생합니다.

---

## Ⅴ. 기대효과 및 결론

### 기술 진화와 미래 전망
- **머신러닝 기반 캐시 교체**: 전통적인 LRU는 과거의 이력만 본다. 최신 인텔 프로세서에서는 프로그램의 분기 궤적과 메모리 접근 패턴을 작은 뉴럴 네트워크(Perceptron)로 학습하여, "이 주소 패턴은 다음에 꼭 부를 놈이야!"라고 인공지능이 개입해 방출 순위를 강제로 조작하는 스마트 교체 기법이 상용화 단계에 와 있다.
- **DIP (Dynamic Insertion Policy)**: 어떤 프로그램은 LRU가 잘 맞고, 어떤 프로그램은 LRU가 독이 된다. 그래서 칩 내부에 두 가지 정책을 모니터링하는 작은 듀얼 카운터를 달고, 현재 돌고 있는 소프트웨어 성향에 맞춰 실시간으로 캐시 교체 알고리즘의 성격을 스스로 스위칭하는 융합 하드웨어가 서버 시장을 지배하고 있다.

### 결론
캐시 교체 알고리즘은 무한한 데이터 욕망을 유한한 반도체 면적 안에 욱여넣어야 하는 컴퓨터 공학의 철학적 결론이다. 우리는 모든 것을 기억할 수 없기에 필연적으로 망각(Eviction)을 택해야만 한다. LRU 알고리즘의 위대함은 "우리의 미래는 과거에 가장 많이, 자주 썼던 것들에 의해 결정된다"는 인간 세계의 시간적 지역성을 반도체 회로로 완벽하게 구현해 냈다는 점에 있다.

- **📢 섹션 요약 비유**: 캐시 교체 알고리즘은 회사의 구조조정 명단 작성과 같습니다. 회사가 어려워져 누군가를 내보내야 할 때, 가장 최근에 실적을 낸 에이스(MRU)는 남기고, 과거부터 지금까지 오랫동안 성과가 없던 직원(LRU)을 먼저 내보내는 것이 회사의 생존을 지키는 가장 확실한 원칙입니다.

---

### 📌 관련 개념 맵

| 개념 명칭 | 관계 및 시너지 설명 |
|:---|:---|
| **시간적 지역성** | 한 번 쓰인 데이터가 조만간 다시 쓰일 것이라는 특성으로, LRU 알고리즘이 성립할 수 있는 근본적인 통계적 신앙. |
| **세트 연관 매핑** | 특정 세트 안의 4~8개 방 사이에서 교체 대상을 골라야 하는 환경을 제공하여, 전체 탐색의 구현 비용을 깎아줌. |
| **캐시 스래싱** | 캐시 용량보다 약간 더 큰 데이터 덩어리를 순환할 때, LRU 정책과 맞물려 매 클럭마다 데이터가 쫓겨나는 시스템 정지 현상. |
| **적중률** | 캐시 교체 알고리즘이 얼마나 똑똑하게 희생양을 선택했는가를 증명하는 궁극적인 성적표. |
| **워킹 셋** | 프로세스가 현재 활발하게 참조하고 있어 캐시에서 절대로 교체당하면 안 되는 핵심 데이터 덩어리. |

---

### 👶 어린이를 위한 3줄 비유 설명
1. 내 장난감 상자에는 장난감이 딱 4개만 들어가요. 만약 5번째 새 장난감을 넣으려면, 상자 안의 4개 중 1개는 무조건 버려야 해요.
2. 이때 아무거나 눈 감고 버리는 게 아니라, "어? 이 로봇은 내가 한 달 동안 쳐다보지도 않았네?" 하고 가장 오랫동안 안 갖고 논 장난감(LRU)을 골라서 버려요.
3. 방금까지 놀았던 인형은 놔두고 옛날 장난감을 버리는 똑똑한 규칙 덕분에, 다음번에도 장난감 상자에서 가장 좋아하는 장난감을 1초 만에 찾을 수 있답니다!