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

  1. 본질: LRU (Least Recently Used)는 캐시가 가득 찼을 때 가장 오래 전에 참조된 블록을 내보내는 교체 정책으로, 시간적 지역성 (Temporal Locality)을 가장 직접적으로 이용한다.
  2. 가치: 최근에 쓴 데이터가 다시 쓰일 가능성이 높다는 경험칙을 하드웨어 정책으로 바꾸어, 같은 캐시 용량에서도 높은 적중률과 예측 가능한 성능을 만든다.
  3. 판단 포인트: 이론적으로는 강력하지만 고연관 캐시에서 완전한 LRU를 구현하는 비용이 크므로, 실제 설계에서는 Pseudo-LRU (Pseudo Least Recently Used), CLOCK (Clock), TinyLFU (Tiny Least Frequently Used) 같은 근사·혼합 정책까지 함께 판단해야 한다.

Ⅰ. 개요 및 필요성

LRU (Least Recently Used)는 제한된 캐시 공간에서 교체 대상을 고를 때, 가장 오랫동안 사용되지 않은 데이터를 희생시키는 정책이다. 이 규칙은 "방금 쓴 것은 곧 다시 쓸 가능성이 높다"는 시간적 지역성 (Temporal Locality)에 기대고 있다. 중앙처리장치인 CPU (Central Processing Unit) 캐시, 운영체제의 페이지 교체, 데이터베이스 버퍼 풀처럼 저장 공간은 작고 재참조 비용은 큰 곳일수록 이 발상이 중요해진다.

이 정책이 필요한 이유는 캐시 미스 한 번의 대가가 매우 크기 때문이다. L1 캐시에서 끝날 접근이 메인 메모리까지 내려가면 수십~수백 사이클을 잃고, 페이지 캐시나 디스크 버퍼에서는 지연이 더 커진다. 따라서 교체 정책은 단순한 정리 규칙이 아니라, 어떤 데이터를 가까운 곳에 남길지 결정하는 성능 전략이다.

다음 그림은 LRU가 보는 핵심 판단 축이 "사용 빈도"가 아니라 "최근성"임을 보여준다.

┌──────────────────────────────────────────────────────────────┐
│        Recency-based eviction: 가장 오래 안 쓴 것을 제거     │
├──────────────────────────────────────────────────────────────┤
│ Time ───────────────────────────────────────────────────▶    │
│                                                              │
│ Access order:   D      B      A      C      B      A         │
│                    older                         newer        │
│                                                              │
│ Current rank:  LRU ── D ── C ── B ── A ── MRU                │
│                    eviction candidate        keep nearby      │
└──────────────────────────────────────────────────────────────┘

핵심은 LRU가 미래를 모르는 대신, 최근 접근 이력을 가장 믿을 만한 힌트로 사용한다는 점이다. 무작위 교체는 방금 다시 쓸 데이터를 버릴 수 있고, 단순 선입선출은 오래 들어왔지만 계속 필요한 데이터를 놓칠 수 있다. LRU는 이런 비합리성을 줄여 캐시를 "가장 최근의 작업 맥락"에 맞춰 유지한다.

  • 📢 섹션 요약 비유: 책상이 꽉 찼을 때 LRU는 어제까지 보던 책은 남기고, 몇 달째 손도 안 댄 책부터 치우는 방식이다. 공부 중인 흐름을 이어 가려면 오래 묵은 책보다 방금 보던 책이 더 중요하기 때문이다.

Ⅱ. 아키텍처 및 핵심 원리

LRU는 보통 세트 연관 캐시 (Set-Associative Cache) 안에서 "같은 세트에 들어온 후보들 중 누구를 내보낼지"를 결정한다. 즉, 주소가 어느 세트로 들어갈지는 인덱스로 정해지고, 그 세트 내부의 여러 way 중 희생 대상을 고를 때 LRU 정보가 쓰인다. 그래서 LRU의 실체는 "캐시 전체의 하나의 줄 세우기"가 아니라, 세트마다 유지하는 최근성 순서 정보에 가깝다.

동작은 단순하다. 읽기 또는 쓰기 hit가 발생하면 해당 블록을 MRU (Most Recently Used) 위치로 올리고, 그보다 최근성이 낮은 블록들의 순위를 한 칸씩 뒤로 민다. miss가 발생하면 가장 뒤에 있는 LRU 블록을 교체하고, 새 블록을 가장 앞에 둔다. 이 순서 관리를 어떻게 구현하느냐가 성능과 회로 복잡도를 가른다.

구현 방식원리장점부담
정확한 LRU모든 way의 상대적 순서를 추적적중률 판단이 직관적연관도 증가 시 상태 수와 갱신 비용 증가
카운터 기반 근사최근 접근 시 age/priority 값 갱신구현 개념이 단순비교기와 갱신 로직 부담
Tree Pseudo-LRU이진 트리 비트로 덜 최근인 쪽을 가리킴빠르고 면적이 작음정확한 LRU와 다를 수 있음

아래 그림은 4-way 세트에서 LRU 순서가 어떻게 갱신되는지 보여준다.

┌──────────────────────────────────────────────────────────────┐
│           4-way set example: hit/miss마다 recency 갱신       │
├──────────────────────────────────────────────────────────────┤
│ Before access                                                 │
│ MRU                                                     LRU  │
│ [Way1:A] ── [Way3:C] ── [Way0:D] ── [Way2:B]                 │
│                                                              │
│ Access = Way0:D (hit)                                        │
│                                                              │
│ After reorder                                                │
│ [Way0:D] ── [Way1:A] ── [Way3:C] ── [Way2:B]                 │
│                                         ▲                    │
│                              next eviction candidate         │
│                                                              │
│ Miss = X  => evict Way2:B, insert X as MRU                   │
└──────────────────────────────────────────────────────────────┘

문제는 연관도 (Associativity)가 올라갈수록 정확한 LRU의 비용도 커진다는 점이다. 2-way나 4-way에서는 비교적 단순하지만, 8-way 이상에서는 모든 접근마다 순위 정보를 빠르게 갱신해야 하므로 배선, 비교기, 전력 소모, 임계 경로 부담이 커진다. 그래서 실제 CPU 캐시는 LRU의 철학은 유지하되, 구현은 Pseudo-LRU 같은 근사 정책으로 타협하는 경우가 많다.

또한 LRU는 "최근성"을 잘 보지만 "앞으로 다시 안 쓸 순차 스트림"은 잘 구별하지 못한다. 캐시보다 큰 배열을 한 번씩 쭉 읽으면 새 데이터가 계속 MRU가 되면서 기존 유용한 데이터가 밀려나고, 이것이 캐시 오염 (Cache Pollution)과 스래싱 (Thrashing)으로 이어진다. 즉, LRU는 강력하지만 워크로드의 패턴까지 자동으로 이해하는 만능 정책은 아니다.

  • 📢 섹션 요약 비유: LRU는 식당 냉장고의 맨 앞칸을 "방금 쓴 재료"에게 주는 규칙과 같다. 그런데 손님이 한 번만 찾고 다시는 안 올 재료를 계속 들여오면, 자주 쓰는 양념까지 뒤로 밀려나 냉장고가 어수선해질 수 있다.

Ⅲ. 비교 및 연결

LRU를 제대로 이해하려면 다른 교체 정책과의 경계를 봐야 한다. FIFO (First-In, First-Out)는 들어온 순서만 보므로 오래전에 들어왔지만 지금도 자주 쓰는 데이터를 보호하지 못한다. LFU (Least Frequently Used)는 누적 사용 횟수를 보므로 장기 인기 데이터에는 강하지만, 한때 많이 쓰였으나 지금은 식은 데이터를 오래 붙잡는 문제가 있다. LRU는 이 둘 사이에서 "현재 작업 맥락"을 가장 잘 반영하는 정책이다.

정책기준강점약점잘 맞는 상황
FIFO (First-In, First-Out)들어온 순서구현이 매우 단순최근 반복 접근 반영 부족단순 큐형 버퍼
LRU (Least Recently Used)마지막 사용 시점시간적 지역성 반영 우수순차 스캔에 약함일반 목적 캐시
LFU (Least Frequently Used)누적 사용 빈도장기 인기 데이터 보존오래된 인기의 잔존 문제장수 키가 많은 캐시
Random무작위하드웨어 비용 최소성능 예측성 낮음초저비용 하드웨어
CLOCK참조 비트 기반 근사 LRU운영체제 구현 효율적정확한 순위 정보 부족페이지 교체

LRU는 이론적으로도 의미가 있다. LRU는 스택 알고리즘 (Stack Algorithm)에 속하므로, 같은 접근열에서 캐시 크기를 키우면 더 작은 캐시의 내용이 더 큰 캐시의 부분집합처럼 유지된다. 그래서 FIFO에서 나타날 수 있는 벨라디의 모순 (Bélády's Anomaly), 즉 캐시를 늘렸는데 미스가 더 많아지는 현상을 피할 수 있다. 이 성질은 설계자가 용량 증가 효과를 비교적 예측 가능하게 바라보게 만든다.

연결 개념도 분명하다. LRU는 시간적 지역성과 직접 연결되고, 세트 연관도는 LRU를 적용할 후보 범위를 정한다. 운영체제에서는 LRU를 그대로 쓰기보다 CLOCK이나 Second-Chance로 근사하고, 데이터베이스와 애플리케이션 캐시에서는 2Q, ARC (Adaptive Replacement Cache), TinyLFU처럼 최근성과 빈도를 혼합해 LRU의 약점을 보완한다. 즉 LRU는 종착점이 아니라, 현대 캐시 정책들의 기준선이 되는 출발점이다.

  • 📢 섹션 요약 비유: FIFO가 줄 선 순서만 보고 사람을 내보내는 규칙이라면, LRU는 "요즘 이 가게를 얼마나 최근에 찾았는가"를 보는 단골 관리다. LFU는 평생 방문 횟수만 세기 때문에, 예전에만 자주 왔던 손님을 계속 VIP로 착각할 수 있다.

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

실무에서 LRU를 쓸지 말지는 "최근성이 실제 재사용을 잘 예측하는가"로 판단해야 한다. 웹 애플리케이션 세션 캐시, 인덱스 페이지, 반복 루프 중심의 CPU 작업처럼 같은 데이터가 짧은 시간 안에 다시 등장하는 환경에서는 LRU가 높은 적중률을 만든다. 반면 로그 풀스캔, 대용량 백업 읽기, 스트리밍처럼 데이터가 한 번 지나가고 끝나는 접근에서는 LRU가 기존 hot data를 밀어내어 오히려 손해를 만들 수 있다.

실무 판단 포인트

  1. CPU 캐시: 4-way 이하에서는 비교적 단순한 LRU 또는 근사 LRU가 유효하지만, 8-way 이상 고속 캐시에서는 히트 시간 증가가 더 치명적일 수 있어 Tree Pseudo-LRU가 흔하다.
  2. 운영체제 페이지 교체: 정확한 LRU를 매 접근마다 갱신하면 오버헤드가 커서, 참조 비트와 원형 포인터를 쓰는 CLOCK이 더 현실적이다.
  3. 데이터베이스 버퍼 풀: 대형 스캔이 잦다면 midpoint insertion, scan resistance, hot/cold 분리 같은 보완 장치가 필요하다.
  4. 애플리케이션 캐시: 동시성이 높으면 연결 리스트 기반 순수 LRU가 락 경합을 만들 수 있으므로 Caffeine의 Window TinyLFU 같은 현대적 구현을 검토하는 편이 낫다.

피해야 할 안티패턴

  • "LRU니까 무조건 최적"이라고 가정하고 순차 스캔 워크로드를 그대로 캐시에 태우는 설계
  • 고연관 하드웨어 캐시에 정확한 LRU를 넣다가 오히려 히트 지연시간을 늘리는 설계
  • 빈도 정보가 중요한 장기 캐시에서 최근성만 보고 오래 유지돼야 할 핵심 키를 밀어내는 설계

기술사 답안에서는 이 한 문장이 중요하다. LRU는 일반 목적 기준선으로 훌륭하지만, 고속 하드웨어에서는 근사 구현이 필요하고, 스캔성 워크로드에서는 보완 정책 없이 쓰면 캐시 오염이 심해질 수 있다. 즉 채택 여부는 알고리즘 이름이 아니라 접근 패턴과 구현 비용의 균형으로 결정해야 한다.

  • 📢 섹션 요약 비유: LRU는 평소 손님 흐름을 잘 아는 점장과 같지만, 관광버스가 한 번 들렀다 가는 날까지 평소 규칙만 고집하면 단골 손님 자리가 사라질 수 있다. 그래서 큰 가게일수록 예외 규칙과 보조 장치를 함께 둔다.

Ⅴ. 기대효과 및 결론

LRU의 가장 큰 효과는 캐시를 현재 실행 중인 작업의 맥락에 맞춰 동적으로 정렬해 준다는 점이다. 그 결과 평균 메모리 접근 시간 (Average Memory Access Time)을 낮추고, 같은 용량으로도 체감 성능을 높이며, 교체 이유를 설명하기 쉬운 예측 가능한 동작을 제공한다. 설계자 입장에서는 "무엇을 남기고 무엇을 버렸는가"를 직관적으로 설명할 수 있어 분석과 튜닝에도 유리하다.

하지만 한계도 분명하다. 최근에 썼다고 해서 반드시 다시 쓰는 것은 아니며, 대규모 순차 접근은 LRU를 손쉽게 속인다. 또한 정확한 LRU는 연관도와 동시성이 커질수록 구현비용이 증가하므로, 실제 시스템은 근사 정책이나 혼합 정책으로 이동하고 있다.

결국 LRU는 "과거의 가장 가까운 흔적을 미래 예측의 근거로 삼는 정책"으로 기억하면 된다. 완벽한 미래 예측은 못 하지만, 일반적인 프로그램의 지역성을 가장 단순하고 강력하게 활용하는 기본선이다. 그래서 현대 시스템은 LRU를 버린 것이 아니라, LRU를 중심축으로 두고 더 싸고 더 똑똑한 변형으로 진화해 왔다.

  • 📢 섹션 요약 비유: LRU는 가방이 꽉 찼을 때 최근에 자주 꺼내 쓴 물건은 손닿는 곳에 두고, 오래 안 쓴 물건부터 빼는 습관과 같다. 아주 똑똑한 여행자는 여기에 "이번 여행에서 정말 다시 쓸까?"까지 한 번 더 생각해 가방을 꾸린다.

📌 관련 개념 맵

개념연결 포인트
시간적 지역성 (Temporal Locality)LRU가 성립하는 가장 직접적인 전제다. 최근 접근이 재접근 가능성을 높인다는 경험칙이 정책의 근거가 된다.
세트 연관 캐시 (Set-Associative Cache)LRU는 보통 세트 내부의 victim 선택 규칙으로 적용된다. 연관도가 커질수록 구현 난도가 높아진다.
Pseudo-LRU정확한 LRU의 비용을 줄이기 위한 대표적 하드웨어 근사 기법이다. 빠른 hit time 유지가 목표다.
캐시 오염 (Cache Pollution)순차 스캔처럼 다시 쓰지 않을 데이터가 hot data를 밀어내면 LRU의 약점이 드러난다.
CLOCK / TinyLFU운영체제나 소프트웨어 캐시에서 LRU의 현실적 대안 또는 보완책으로 쓰이는 정책들이다.

📈 관련 키워드 및 발전 흐름도

시간적 지역성 (Temporal Locality)
        │
        ▼
LRU (Least Recently Used)
        │
        ├──▶ 정확한 순서 추적 LRU
        │
        ├──▶ Pseudo-LRU / CLOCK
        │
        └──▶ ARC · TinyLFU · Scan-resistant cache

이 흐름은 "최근성 활용"에서 출발해, 하드웨어 비용 절감과 워크로드 적응성을 높이는 방향으로 교체 정책이 발전했음을 보여준다.

👶 어린이를 위한 3줄 비유 설명

  1. 장난감 상자에 새 장난감을 넣어야 하는데 자리가 없으면, 가장 오래 안 가지고 논 장난감부터 꺼내는 게 LRU예요.
  2. 어제 가지고 논 장난감은 오늘도 또 가지고 놀 가능성이 높으니까 상자 안에 남겨 두는 거예요.
  3. 그런데 한 번만 보고 끝날 장난감을 계속 넣으면 자주 놀던 장난감이 밀려날 수 있어서, 똑똑한 상자는 상황에 따라 다른 규칙도 같이 써요.