LFU (Least Frequently Used) 페이지 교체

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

본질: LFU (Least Frequently Used)는 메모리가 꽉 차서 페이지를 교체할 때, "최근에 언제 썼는가(시간)"가 아니라 "과거부터 지금까지 총 몇 번이나 쓰였는가(빈도수)"를 따져 가장 적게 사용된 페이지를 쫓아내는 통계 기반 알고리즘이다.

가치: 한 번 쓱 지나가며 엄청난 양의 메모리를 읽고 버리는 스캔 작업(Sequential Scan)이 들어왔을 때 기존 캐시가 싹 다 밀려버리는 LRU의 치명적 약점(Cache Pollution)을 완벽하게 방어해 내는 '단골손님 보호' 철학을 지닌다.

융합: 하지만 과거의 영광(높은 참조 횟수)에 취해 현재는 쓰이지 않는 페이지가 메모리에 영원히 박제되는 문제와 O(log N)의 관리 오버헤드 탓에, 현대에는 LFU와 LRU의 장점만 섞은 W-TinyLFU (Caffeine Cache 등) 같은 하이브리드 아키텍처로 진화하여 실무 캐시 엔진을 평정했다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: 페이지마다 **'참조 횟수(Reference Count)'**를 기록하는 카운터를 두고, 페이지 폴트가 발생하여 누군가를 버려야 할 때 이 카운터 값이 가장 작은 녀석을 골라 희생양(Victim)으로 삼는 알고리즘이다.
필요성: LRU는 훌륭했지만 "딱 한 번 불렸더라도 방금 불린 놈을 VIP 대접한다"는 맹점이 있었다. 만약 바이러스 백신이 하드디스크의 10GB짜리 쓰레기 파일들을 한 번씩 쭉 스캔하면, LRU는 이걸 "최신 트렌드"라 착각하고, 내가 매일 100번씩 쓰던 크롬 브라우저 캐시를 바닥으로 쫓아내 버렸다. "어제 한 번 온 손님 때문에 10년 단골을 쫓아내는" 이 바보짓을 막기 위해 '빈도(Frequency)'라는 새로운 평가 잣대가 필요했다.
💡 비유: 식당 매니저가 **'어제 딱 한 번 와서 밥 먹은 손님(LRU가 살려두는 놈)'**을 내쫓고, 어제는 안 왔지만 **'지난 10년간 매일 점심을 먹고 간 단골손님(LFU가 살려두는 놈)'**의 지정석을 끝까지 지켜주는 완벽한 멤버십 관리 정책과 같다.
등장 배경: 1970년대 데이터베이스와 파일 시스템의 버퍼 풀(Buffer Pool) 관리가 고도화되면서, 특정 데이터 블록(인덱스 루트 노드 등)은 프로그램 시작부터 끝까지 수만 번 참조된다는 사실이 밝혀졌다. 이런 VIP 데이터를 절대로 스왑 아웃(Swap-out)시키지 않기 위한 락(Lock-in)의 개념으로 빈도수 기반 교체 이론이 탄생했다.

  [LRU의 맹점(Cache Pollution)과 LFU의 철벽 방어 시뮬레이션]

  [ 상황: 램 프레임 3칸. 현재 'A(100번 불림)', 'B(50번)', 'C(30번)' 꽉 차 있음 ]
  
  ▶ 갑자기 쓰레기 데이터 X, Y, Z 가 딱 1번씩만 참조되며 들어옴!

  [ ❌ LRU (최근 사용 우선) 의 멍청한 판단 ]
  1. X 들어옴 ─▶ 제일 예전에 쓴 C 버림 ─▶ 램 상태: [A, B, X]
  2. Y 들어옴 ─▶ 그다음 예전에 쓴 B 버림 ─▶ 램 상태: [A, X, Y]
  3. Z 들어옴 ─▶ 제일 예전에 쓴 A 버림 ─▶ 램 상태: [X, Y, Z]
  🚨 결과: 100번, 50번 쓰이던 특급 단골 A, B가 다 쫓겨나고 1번씩 쓴 쓰레기로 램이 도배됨! (캐시 오염)

  [ ✅ LFU (빈도수 최우선) 의 철벽 방어 ]
  1. X(1번) 들어옴 ─▶ C(30번) 버릴까? 안돼! C가 더 많이 불렸어! X 너 그냥 나가!
  2. Y(1번) 들어옴 ─▶ B(50번), C(30번)? Y 너 나가!
  3. Z(1번) 들어옴 ─▶ A(100번)? Z 너 나가!
  ✅ 결과: 스쳐 지나가는 쓰레기 데이터들은 램에 정착하지 못하고 바로 튕겨 나감. 단골 완벽 보호!

[다이어그램 해설] LFU는 "빈도수"라는 막강한 기득권(권력)을 형성한다. 이 권력을 쌓은 데이터는 어지간한 신규 데이터의 도전을 다 씹어먹고 캐시 상단에 영구 박제된다. 이는 백업(Backup)이나 풀 스캔(Full Scan) 쿼리가 돌 때 캐시 메모리가 초토화되는 것을 막아주는 최고의 방패막이다.

📢 섹션 요약 비유: 100번 클릭해서 키워놓은 만렙 기사(단골 데이터)와 방금 막 생성한 1레벨 초보(스캔 데이터)가 파티에 있습니다. LRU는 "방금 로그인한 초보가 더 중요해!"라며 만렙 기사를 파티에서 쫓아내는 멍청한 마스터입니다. LFU는 철저히 레벨(클릭 횟수)만 보고 1레벨들을 가차 없이 추방하는 냉혹한 길드장입니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

LFU의 두 가지 구현 방식과 치명적 약점

LFU를 소프트웨어로 짜려면 페이지마다 int count 변수를 둬야 한다. 그리고 이 count를 기준으로 줄을 세워야 하는데 여기서 알고리즘의 비극이 시작된다.

1. 카운터(Counter) 기반 힙(Min-Heap) 정렬 오버헤드

count가 가장 작은 놈을 $O(1)$에 찾으려면 최소 힙(Min-Heap)이나 이진 탐색 트리를 써야 한다.
메모리를 한 번 읽을 때마다 $O(\log N)$의 속도로 트리를 재정렬해야 한다.
현실: CPU 캐시나 OS 메모리 스케줄러는 나노초 단위로 움직이는데, 매번 트리를 뒤집는 오버헤드는 100% 시스템 스래싱(Thrashing)을 유발한다.

2. 과거의 영광 (Historical Baggage) 문제

어떤 페이지가 프로그램 시작 직후 5분 동안 for 루프에 걸려 10,000번 참조되었다.
5분 뒤 이 페이지는 수명을 다해 프로그램 끝날 때까지 다신 안 쓰인다.
결과: 하지만 이 녀석의 카운트는 이미 '10,000'이라는 넘사벽 스펙을 찍었기 때문에, 새로 들어온 진짜 필요한 페이지(카운트 1, 2)들을 다 짓밟고 메모리에 영원히 시체처럼 남아서(박제) 램을 낭비한다.

Aging (노화) 기법을 통한 LFU의 심폐소생술

과거의 영광에 취해 안 나가는 고인물들을 치우기 위해 고안된 기법이다.

원리: 주기적으로(예: 1초마다) 모든 페이지의 참조 카운트 값을 절반으로 깎아버린다 (Bit Shift Right: count >>= 1).
효과: 1만 번을 찍은 고인물도 시간이 지나면 5천, 2천5백, 1천으로 점수가 팍팍 깎인다. 결국 최근에 계속 참조되어 점수를 올리는 '젊은 피(Recent Frequency)'들에게 자리를 내어주게 된다.
📢 섹션 요약 비유: 왕년에 1만 골을 넣은 은퇴한 전설의 스트라이커(과거의 영광)가 과거 기록만 믿고 주전 자리를 차지해 신인들이 못 뛰는 상황입니다. 감독(OS)은 매년 모든 선수의 통산 골 기록을 반 토막(Aging) 내버리는 규정을 만들어서, 최근에 꾸준히 골을 넣는 선수만이 주전을 유지할 수 있게 고인물을 쳐냅니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

LRU (최근성) vs LFU (빈도수) 의 철학 전쟁

운영체제와 캐시 프레임워크를 만들 때 아키텍트를 가장 괴롭히는 선택지다.

특성	LRU (Least Recently Used)	LFU (Least Frequently Used)
평가 기준	"언제 마지막으로 썼는가?" (Time-based)	"지금까지 몇 번 썼는가?" (Count-based)
방어력 (스캔 공격)	❌ 최약체. 풀 스캔 돌면 캐시 다 털림.	✅ 최강. 한 번 스친 쓰레기들은 바로 버려짐.
적응력 (트렌드 변화)	✅ 최고. 옛날 데이터는 뒤로 바로 밀려남.	❌ 최악. 옛날에 많이 불린 놈이 안 나가고 버팀.
구현 오버헤드	적음 (단순 Linked List 포인터 스왑)	매우 큼 (Min-Heap 정렬 필요)
현대적 사용처	OS 커널의 페이지 교체 (Clock 알고리즘으로 우회)	백엔드 In-Memory 캐시 서버 (Redis 등)

이 두 철학은 완벽하게 서로의 약점을 찌른다. LRU는 새로운 변화에 유연하지만 사기꾼(스캔)에 약하고, LFU는 사기꾼은 100% 막아내지만 변화에 둔감한 꼰대다.

하이브리드의 탄생: LRFU와 W-TinyLFU

현대 컴퓨터 공학은 이 둘 중 하나를 고르는 짓을 그만두고 아예 합쳐버렸다.

LRFU: 큐를 두 개로 나눈다. 방금 들어온 놈들은 LRU 큐에 넣고, 거기서 여러 번 살아남아 증명된 놈들만 LFU 큐로 승진시킨다.
W-TinyLFU: 자바 진영의 최강 캐시 라이브러리인 Caffeine Cache가 쓰는 궁극의 엔진. 블룸 필터(Bloom Filter)의 변종인 Count-Min Sketch를 써서 1바이트도 안 되는 메모리로 수백만 건의 빈도수를 추적하며, 최근성(Window)과 빈도수(Frequency)를 동시에 평가해 99%의 히트율을 뽑아낸다.
📢 섹션 요약 비유: LRU는 '유행(트렌드)'이고, LFU는 '누적 판매량(스테디셀러)'입니다. 음원 차트를 짤 때 유행만 반영하면 사재기(스캔 공격)에 차트가 오염되고, 누적 판매량만 반영하면 10년 전 조용필 노래가 평생 1등을 합니다. 두 개를 절묘하게 섞은 '빌보드 핫 100 (W-TinyLFU)'이 진짜 대중의 마음을 반영하는 것입니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

Redis의 allkeys-lfu 정책 (Redis 4.0 이후 도입):
- 과거 Redis는 LRU만 지원했다. 하지만 사용자들이 "가끔 도는 배치 작업 때문에 메인 배너 캐시가 날아간다!"라고 아우성쳤다.
- 아키텍처 혁신: Redis 제작자는 LFU의 힙(Heap) 정렬 오버헤드를 없애기 위해, 객체 헤더의 24비트 공간에 8비트는 빈도수(Logarithmic 카운터), 16비트는 최근 접근 시간(Aging용)을 때려 박았다.
- 실무 효과: 완벽한 LFU가 아니라 "대충 빈도를 세면서, 시간 지나면 알아서 값이 깎이는(Decay)" 확률적 LFU를 구현했다. 덕분에 메모리나 CPU 오버헤드 0%로 스캔 공격을 완벽히 방어하는 allkeys-lfu 모드가 탄생하여 현대 캐시 아키텍처의 표준이 되었다.
CDN(Content Delivery Network)의 엣지 서버 캐싱: 전 세계로 동영상을 쏘는 AWS CloudFront나 Cloudflare의 엣지 노드는 용량이 꽉 차면 누굴 지울까?
- 실무 판단: 동영상은 크기가 GB 단위다. 한 번 잘못 지우면 오리진(Origin) 서버에서 다시 가져오는 네트워크 비용이 수천만 원이다.
- 아키텍트 결단: 이때는 무조건 **LFU 기반의 변형 알고리즘(LFU-DA 등)**을 쓴다. 한 번 조회된 듣보잡 영상은 바로 디스크에서 날리고, 하루에 1만 번 조회되는 방탄소년단 뮤직비디오(High Frequency)는 램 최상단에 영구 박제시켜 글로벌 트래픽 비용을 극한으로 후려친다.

  ┌──────────────────────────────────────────────────────────────────────────┐
  │     백엔드 아키텍트의 캐시 교체 정책(Eviction) 설계 가이드라인           │
  ├──────────────────────────────────────────────────────────────────────────┤
  │                                                                          │
  │   [질문 1] 데이터의 생명 주기가 극단적으로 짧고 유행을 타는가?           │
  │     (예: 뉴스 피드 최신 글, 실시간 주식 호가)                            │
  │          ├─ [예] ─▶ ✅ LRU (Least Recently Used) 선택                    │
  │          │                                                               │
  │          └─ [아니오]                                                     │
  │                 │                                                        │
  │   [질문 2] 소수의 '스타 데이터(전역 설정, 랭킹)'가 트래픽의 90%를 먹는가?│
  │          ├─ [예] ─▶ ✅ LFU (Least Frequently Used) 선택                  │
  │          │             (스캔 공격에 스타 데이터가 썰리는 걸 절대 방어)   │
  │          │                                                               │
  │          └─ [모르겠다 / 섞여 있다]                                       │
  │                 │                                                        │
  │                 ▼ ✅ W-TinyLFU (Caffeine Cache) 선택                     │
  │             "알아서 최근 유행과 누적 단골을 다 챙겨주마!"                │
  │             (현재 Java 진영 Spring Boot의 기본 캐시 엔진임)              │
  └──────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] "OS 커널은 왜 LFU를 안 쓸까?" OS가 관리하는 페이지는 코드와 지역 변수 쪼가리들이라 빈도를 세는 게 무의미하고 너무 무겁기 때문이다. 반면 **애플리케이션(User Space) 레벨의 '객체 캐싱(Object Caching)'**에서는 LFU가 제왕이다. 아키텍트는 OS의 한계와 애플리케이션의 강점을 명확히 구분하여 알고리즘을 차용해야 한다.

📢 섹션 요약 비유: OS 커널의 페이징(LRU)은 '편의점 알바생'입니다. 물건이 너무 많고 빨리 팔리니 그냥 방금 팔린 걸 앞에 채워 넣는 게 최고입니다. 하지만 백엔드 서버의 캐시(LFU)는 '명품관 매니저'입니다. 물건 하나하나의 가치가 크기 때문에, 누가 얼마나 자주 사 가는지 고객 장부(빈도수)를 철저히 기록해서 VIP만 챙겨야 이윤이 남습니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

LFU 철학을 캐시 시스템에 적용하면, 악의적인 크롤링 봇이나 백그라운드 전체 스캔 작업이 유발하는 캐시 오염(Cache Pollution)을 원천 차단하여, 실제 유저들이 가장 많이 찾는 핵심 데이터(Hot Data)의 램 상주율을 100% 방어해 낼 수 있다.

결론 및 미래 전망

LFU는 "참조 횟수를 센다"는 가장 직관적이고 강력한 무기를 가졌음에도, O(log N)이라는 힙 정렬의 무거움과 고인물 박제라는 한계 때문에 한동안 LRU의 그늘에 가려져 있었다. 하지만 데이터가 돈이 되는 빅데이터 시대가 오며 "누가 진성 단골(Hot Key)인가?"를 가려내는 기술의 가치가 급상승했다. 현대의 컴퓨터 과학은 LFU의 무거운 힙(Heap) 정렬을 버리고, 빅데이터 알고리즘인 스케치(Sketch, 확률적 자료구조) 기법을 도입하여 단 몇 비트(Bit)만으로 1억 개의 데이터 빈도수를 오차율 1% 미만으로 추적해 내는 기적을 이뤄냈다. LFU는 죽은 것이 아니라, 빅데이터 통계학의 옷을 입고 현대 클라우드 캐시의 심장으로 화려하게 부활했다.

📢 섹션 요약 비유: 과거의 LFU는 매장 입구에 서서 손님 1만 명의 이름을 장부에 정자로 꾹꾹 눌러쓰다(오버헤드 폭발) 쓰러진 바보였습니다. 현대의 LFU(Caffeine 등)는 그냥 손님이 지나갈 때마다 지문 인식기(Sketch 알고리즘)로 0.01초 만에 틱틱 찍고 통계만 내는 최첨단 AI 매니저로 환골탈태했습니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
페이지 교체 (Page Replacement)	메모리가 꽉 찼을 때 LFU가 칼을 들고 "누구 죽일까?" 고민하는 근본적인 원인 무대다.
LRU (Least Recently Used)	LFU의 영원한 라이벌. 빈도수를 무시하고 오직 '방금 쓴 놈'만 편애하다 스캔 공격에 털리는 친구다.
캐시 오염 (Cache Pollution)	LRU를 쓸 때 스캔 작업 한 번에 램의 단골 데이터가 싹 다 증발해 버리는, LFU가 막고자 하는 최악의 현상이다.
노화 (Aging)	LFU의 약점인 '과거의 영광(고인물)'을 끌어내리기 위해 주기적으로 카운터를 반 토막 내는 필수 보완 기술이다.
W-TinyLFU (Caffeine Cache)	LRU의 적응력과 LFU의 방어력을 융합하고, 메모리 사용량을 비트 단위로 압축한 현대 자바 진영의 캐시 끝판왕이다.

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

장난감 상자에 자리가 없어서 하나를 버려야 해요. LRU는 "어제 산 팽이 냅두고, 작년부터 매일 만지던 로봇을 버리자(오래전에 만졌으니)"라고 해요.
하지만 LFU는 "안돼! 팽이는 어제 한 번 만진 게 다지만, 로봇은 1년 동안 1,000번이나 갖고 놀았어! 팽이를 버려!"라고 똑똑하게 따져요.
이렇게 단순히 언제 만졌는지가 아니라, **지금까지 몇 번이나 사랑해 줬는지(빈도수)**를 세어서 가장 인기 없는 장난감을 버리는 방법이랍니다!