LFU (Least Frequently Used) 알고리즘

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

본질: LFU(Least Frequently Used) 페이지 교체 알고리즘은 램(RAM)에 빈 공간이 없을 때, 과거부터 현재까지 가장 적게 참조된(호출된 횟수가 제일 적은) 페이지를 "앞으로도 안 쓸 잉여 데이터"로 간주하고 디스크로 쫓아내는 빈도(Frequency) 기반의 타겟팅 기법이다.

가치: "자주 불리는 놈은 핵심 코어 변수다"라는 상식적이고 강력한 장기적 통계 논리를 바탕으로 하며, 주기적으로 뺑글뺑글 도는 고정된 루프 패턴이나 캐시 DB 환경에서 가장 합리적인 생존 곡선을 그려낸다.

융합(한계): 하지만 초반에만 미친 듯이 불리고 나중엔 평생 안 쓰이는 초기화 코드(Init)가 램에 영원히 알박기하는 '과거의 망령' 오류를 피할 수 없어, 카운트를 주기적으로 반토막 내는 에이징(Aging) 기법과 융합해야만 실무에 간신히 써먹을 수 있는 2군 알고리즘이다.

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

개념: 페이지마다 Count(호출 횟수)라는 정수형 꼬리표를 달아둔다. CPU가 해당 페이지를 읽거나 쓸 때마다 하드웨어나 OS가 이 카운트를 1씩 덧셈(+)한다. 램이 꽉 차서 희생양을 찾아야 할 때, OS는 램에 있는 모든 페이지의 카운트 숫자를 쭉 훑어보고 가장 숫자(빈도)가 작은 페이지를 가차 없이 스왑 디스크로 던져버린다.
필요성: LRU(최근 최소 사용)는 훌륭했지만 맹점이 있었다. 내가 평생 매일 100번씩 쓰던 핵심 문서 A가 있는데, 방금 지나가던 똥개(순차 스캔 프로세스)가 쓰레기 문서 B를 단 한 번 터치했다는 이유로 B가 '최근 사용' 타이틀을 달고 램에 남아 내 소중한 A를 밖으로 내쫓는 어이없는 일이 벌어졌다(Cache Pollution). "야, 방금 한 번 터치된 게 뭐가 중요해? 지금까지 쌓아온 '조회수(단골 지표)'를 봐야 진짜 쓸모 있는 놈을 고르지!"라는 아주 합리적이고 자본주의적인 누적 통계 철학이 LFU를 낳았다.
💡 비유: LFU는 백화점의 누적 매출액 기반 VIP 강등 시스템과 같다. LRU가 "어제 와서 양말 한 켤레 산 뜨내기손님"에게 VIP 주차장을 내어주고 "10년 동안 100억을 썼지만 어제 하루 안 온 회장님"을 쫓아내는 방식이라면, LFU는 철저하게 **"이 손님이 우리 백화점에 지금까지 돈(카운트)을 얼마나 썼는가?"**를 누적 계산하여 주차장을 배정한다. 아무리 어제 안 왔어도 누적 100억이면 절대 안 쫓겨나는, 단골 우대의 끝판왕이다.
등장 배경 및 카운팅의 한계 노출:
1. LRU 캐시 오염의 극복: 한 번 읽고 버리는 스캔 작업에 램 전체가 털리는 현상을 막기 위해 빈도수 개념이 제안됨.
2. 하드웨어 덧셈기의 부재: 매 클럭마다 메모리 1장씩 카운트를 +1 하려면 MMU에 엄청난 덧셈기 회로와 비트 공간이 필요해 하드웨어 벤더가 거부함.
3. 과거의 망령 (알박기 현상): 한때 잘 나갔던 데이터가 평생 램을 차지하는 논리적 맹점이 터지며 범용 OS 커널에서 버림받음.

┌──────────────────────────────────────────────────────────────────────────┐
│        LFU의 치명적 맹점: 초기화 코드 알박기 (Phase Transition)          │
├──────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│ [ 프로그램 실행 시나리오: Init() 함수 -> Main() 무한 루프 ]              │
│                                                                          │
│ ▶ 1. 프로그램 켜짐 (0초 ~ 1초)                                           │
│   - 로딩 화면을 그리는 `Init() 페이지`가 10,000번 호출됨.                │
│   - Init 페이지의 카운트: 10000 🚀 (가장 높은 권력)                      │
│                                                                          │
│ ▶ 2. 본 게임 시작 (1초 ~ 10시간)                                         │
│   - 캐릭터가 뛰노는 `Main() 페이지`가 램에 들어옴.                       │
│   - 게임 1분 경과, Main 페이지 카운트: 500                               │
│   - 갑자기 램이 모자라서 누굴 쫓아낼지 LFU 알고리즘 발동!                │
│                                                                          │
│ [ 💀 LFU의 바보 같은 사형 선고 ]                                         │
│   OS: "Init()은 카운트가 1만이고, Main()은 500이네. Main 너 죽어!"       │
│                                                                          │
│ ✅ 비극적 결과: Init()은 게임 끝날 때까지 평생 다신 안 부르는 찌꺼기인데,│
│    과거의 화려했던 카운트(10000)를 무기로 램 1열에 평생 알박기를 함.     │
│    정작 지금 0.1초마다 계속 써야 하는 Main()은 쫓겨나서 게임이 멈춤.     │
└──────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 현상을 전문 용어로 '페이즈 트랜지션(Phase Transition, 국면 전환) 적응 실패'라고 부른다. 프로그램은 로딩 페이즈, 사냥 페이즈, 보스전 페이즈 등 국면이 계속 바뀐다. LFU는 이 과거의 낡은 계급장(카운트)을 영원히 숭배하기 때문에, 현재 페이즈에 필요한 신흥 세력(카운트가 낮은 새 페이지)들을 무참히 학살해 버려 시스템을 뇌사 상태로 몰고 간다.

📢 섹션 요약 비유: 왕년에 잘 나갔던 90년대 아이돌(Init 함수)이 누적 음반 판매량(카운트)이 높다는 이유로 현재 음악방송 1위 자리를 영원히 독차지하고 방을 안 빼서, 지금 한창 뜨고 있는 괴물 신인(Main 함수)들이 방송에 아예 나오지도 못하고 쫓겨나는(Page Fault) 최악의 고인물 생태계입니다.

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

MFU (Most Frequently Used) - 역발상의 미학

LFU의 단점(초기 찌꺼기 알박기)에 열받은 일부 공학자들은, 홧김에 완전히 반대되는 기괴한 알고리즘을 툭 던졌다. 그것이 **MFU(가장 많이 불린 놈을 죽이자)**다.

논리: "카운트가 가장 작다는 것은, 방금 막 램에 올라와서 이제부터 본격적으로 쓰일 싱싱한 놈이라는 뜻이다! 그러니까 카운트 적은 놈은 무조건 살려두고, 차라리 카운트가 미친 듯이 높은 놈(다 단물 빠진 놈)을 죽이자!"
결과: 이론적으론 그럴싸하지만, 실제로 돌려보면 미친 듯이 많이 쓰이는 핵심 코어 반복문(for 루프)을 사살해 버려 시스템이 그 자리에서 멈춰버린다. 결국 MFU나 LFU나 둘 다 순수 LRU(최근 사용 기반)의 발끝에도 못 미치는 성적을 내며 교과서의 실험적 챕터로만 남게 되었다.

하드웨어 오버헤드의 장벽 (O(N) 갱신)

LFU가 멸종한 결정적 이유는 '과거의 망령' 때문만이 아니다. 하드웨어가 못 버텼다.

램을 1바이트 읽을 때마다 64비트 정수형 덧셈기(Adder)가 카운트를 +1 쳐야 한다.
카운트 변수가 램 페이지 테이블에 있으니, 메모리 한 번 읽으려고 장부에 덧셈하러 램을 한 번 더 써야(Write) 하는 끔찍한 성능 낭비가 터진다.
쫓아낼 놈을 찾을 때도, 누가 가장 숫자가 적은지(Min 값) 찾으려면 400만 개의 배열을 몽땅 스캔해야 한다.
트랜지스터와 클럭을 목숨처럼 아끼는 인텔/ARM 하드웨어 설계자 입장에서, 단 1비트의 스위치(참조 비트)만으로 해결되는 Clock(근사 LRU)을 두고 이 무거운 LFU 덧셈 회로를 CPU에 넣어줄 이유가 단 하나도 없었다.
📢 섹션 요약 비유: 도서관에서 책이 얼마나 많이 빌려 갔는지(LFU) 확인하려고 모든 책 100만 권 뒤에 바를 정(정)자를 매번 연필로 그려 넣으려니 사서가 과로사합니다. 그래서 그냥 "최근 한 달 내에 빌려 간 적 있음/없음(1비트)" 딱지만 붙여서 관리하는 게 훨씬 속 편하고 빠른 겁니다.

Ⅲ. 융합 비교 및 다각도 분석

비교 1: LRU (시간 중심) vs LFU (빈도 중심)

캐시 아키텍처의 영원한 맞수다. 결국 시간(Time)이 빈도(Frequency)를 이겼다.

비교 척도	LRU (Least Recently Used)	LFU (Least Frequently Used)
심판 기준	"언제" 마지막으로 썼는가? (Recency)	"몇 번"이나 썼는가? (Frequency)
국면 전환(Phase)	과거 쓰레기를 0.1초 만에 바로 손절함 (최상)	과거 누적 카운트에 발목 잡혀 손절 못 함 (최악)
캐시 오염 방어	스캔 공격에 취약 (한 번 터치에 VIP 됨)	스캔 공격에 강함 (한 번 터치된 건 바로 쫓아냄)
하드웨어 구현	1비트(Clock)로 근사치 퉁치기 쉬움	매번 덧셈을 누적해야 해서 회로가 너무 무거움

LFU의 구원자: 에이징 (Aging) 기법과의 융합

LFU의 '고인물 알박기' 문제를 해결하기 위해, 소프트웨어 공학자들은 **에이징(Aging, 나이 먹기)**이라는 흑마술을 LFU의 카운터에 접목시켰다.

원리: OS가 1초마다 램을 스캔하면서, 모든 페이지의 카운트 값을 무조건 절반으로 나누기(/2, Right Shift 연산) 해버린다.
Init() 함수가 초반에 카운트 10,000을 찍었더라도, 1초 뒤엔 5,000, 2초 뒤엔 2,500, 10초 뒤엔 거의 0으로 쪼그라든다.
반면 Main() 함수는 계속 불리므로 깎이는 와중에도 계속 +100씩 더해져 높은 카운트를 유지한다.
결과: 과거의 영광(카운트)이 시간의 흐름에 따라 서서히 부식되어 사라진다. 이 Aging 기법 덕분에 LFU는 극적인 환골탈태를 이루며 캐시 시스템 실무에 간신히 명함을 내밀 수 있게 되었다. (자세한 에이징은 다음 키워드에서 서술).

┌──────────┬────────────┬────────────┬───────────────────────────────────┐
│ 알고리즘   │ 1번 터치된 놈 │ 1만 번 터치된 놈│ 시간이 흘렀을 때        │
├──────────┼────────────┼────────────┼───────────────────────────────────┤
│ 순수 LRU  │ VIP석 직행  │ 안 쓰면 즉시 버림│ 과거 기억 완전 리셋       │
│ 순수 LFU  │ 즉시 쓰레기통 │ 영원히 알박기 생존│ 과거 망령에 시스템 마비│
│ 에이징 LFU│ 즉시 쓰레기통 │ 천천히 깎여서 버림│ 완벽한 중용의 달성     │
└──────────┴────────────┴────────────┴───────────────────────────────────┘

[매트릭스 해설] 순수 LFU는 단점이 명확해서 실무에서 절대 쓰이지 않는다. 우리가 면접이나 아키텍처 문서에서 "LFU를 씁니다"라고 말할 때는, 100% 무조건 이 'Aging이 가미된 쇠퇴형 LFU'를 의미하는 것이다.

📢 섹션 요약 비유: 평생 모은 재산(카운트)을 영원히 인정해 주면 부자들은 일 안 하고(알박기) 놀고먹습니다(순수 LFU). 그래서 정부(OS)가 매년 재산의 절반을 세금(Aging)으로 뜯어가 버립니다. 그러면 왕년의 부자도 돈이 깎여 쫓겨나지 않기 위해 다시 뼈 빠지게 일(현재의 참조)을 해야만 살아남는 완벽한 자본주의 세금 제도의 완성입니다.

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

실무 시나리오: Redis 4.0 이후의 LFU 캐시 정책 도입

운영체제 커널(메인 램)에서는 LFU가 멸종했지만, Redis 같은 인메모리 캐시 데이터베이스에서는 이야기가 완전히 다르다.

LRU의 패배: 넷플릭스 썸네일을 캐싱할 때 LRU를 쓰면, 아무도 안 보는 비인기 영화 썸네일을 누군가 실수로 1번 클릭했다는 이유로(Hit), 1억 명이 매일 보는 '오징어 게임' 썸네일을 쫓아내고 1열을 차지하는 캐시 오염(Cache Pollution)이 터진다.
Redis 4.0의 LFU 등판:
- Redis는 이 캐시 오염을 막기 위해 4.0 버전부터 volatile-lfu, allkeys-lru 옵션을 전격 도입했다.
- 8비트(0~255)짜리 초경량 카운터를 달아놓고 빈도수를 잰다. 아무리 최근에 1번 불렸어도 카운트가 1이므로, 카운트가 255인 '오징어 게임' 썸네일 앞에서는 명함도 못 내밀고 방을 빼야 한다.
에이징(Decay) 파라미터 튜닝:
- 알박기를 막기 위해 Redis.conf에 lfu-decay-time (기본값 1분)이라는 세팅을 열어두었다.
- 1분이 지날 때마다 조회수 카운트를 깎아내려, 유행이 지난 옛날 명작이 램을 영원히 독식하는 걸 강제로 막아낸다. 백엔드 엔지니어의 가장 화려한 캐시 튜닝 기술이다.

W-TinyLFU (Caffeine Cache의 흑마술)

자바(Java) 백엔드 생태계에서 가장 유명한 로컬 캐시 라이브러리인 Caffeine Cache는 LFU와 LRU를 끔찍하게 섞어버린 W-TinyLFU 알고리즘을 쓴다. 새로 들어온 뜨내기(LRU)와 오랫동안 버틴 단골(LFU)을 필터 큐에서 싸움 붙여, 빈도수가 압도적인 놈만 메인 램에 남기고 나머지는 가차 없이 쳐내는 현존 인류 최고의 캐시 교체 적중률(99%+)을 보여주는 알고리즘이다. 하드웨어의 제약이 없는 유저 랜드(User-space) 애플리케이션에서는 이처럼 빈도수(LFU) 기반의 통계적 튜닝이 성능의 끝판왕으로 군림하고 있다.

📢 섹션 요약 비유: 멜론이나 유튜브 알고리즘(실무 캐시)이 "방금 막 올라온 1회 재생 신곡(LRU)"을 메인에 안 띄우고, "누적 1억 번 재생된 차트 1위 곡(LFU)"을 메인에 고정하는 이유와 같습니다. 단, 철 지난 벚꽃엔딩이 한여름에도 1위를 차지하는 알박기를 막기 위해 발매일이 지나면 점수를 깎아내리는(에이징) 로직이 반드시 필요합니다.

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

정량/정성 기대효과

구분	내용
캐시 스캔 오염 원천 방어	대용량 배치(Batch) 작업이 램을 한 번 쓱 훑고 지나가더라도, 카운트가 낮아 기존 핵심 캐시 데이터를 절대 밀어내지 못함
스테디셀러 데이터 보호	0.1초 단위의 최근성(Recency)은 밀려도 하루 종일 꾸준히 불리는 코어 데이터베이스 인덱스가 램에서 쫓겨나지 않게 철통 방어
User-Space 캐시 혁명	하드웨어 MMU를 벗어난 Redis, Memcached, CDN 환경에서 가장 합리적인 트래픽 예측 지표(조회수)로 활약

결론 및 미래 전망

LFU (Least Frequently Used) 알고리즘은 "자주 찾는 것이 귀한 것이다"라는 자본주의의 절대 진리를 메모리 관리에 이식한 직관적인 모델이다. 초창기 운영체제 학자들은 하드웨어 덧셈기의 부재와 초기화 코드의 영구 알박기(망령) 현상에 질려 이 알고리즘을 매몰차게 버렸고, 그 왕관을 1비트로 퉁치는 가벼운 LRU 근사(Clock)에 넘겨주었다. 그러나 시대가 흘러 메모리 용량이 테라바이트로 팽창하고 웹 캐시 히트율 1%가 수억 원의 서버비를 좌우하는 빅데이터 시대가 열리자, 소프트웨어 엔지니어들은 에이징(Aging)이라는 약을 발라 LFU를 무덤에서 파내어 웹/캐시 생태계의 제왕으로 부활시켰다. 램을 직접 다루는 OS 커널 레벨에선 영원히 버려진 돌멩이겠지만, 애플리케이션과 클라우드 아키텍처 위에서는 데이터를 다루는 가장 정밀하고 강력한 무기로 끝없이 진화해 나갈 것이다.

📢 섹션 요약 비유: "누적 조회수 1억 회(LFU)"라는 지표는 인간의 마음을 가장 잘 나타내는 절대 지표입니다. 옛날엔 그 조회수를 매번 노트에 적느라 팔이 부러져서(하드웨어 오버헤드) 포기했지만, 지금은 서버 메모리가 빵빵하고 컴퓨터가 알아서 세어주니(애플리케이션 캐시) 이보다 더 확실하고 돈이 되는 캐시 선별법은 없는 것입니다.

📌 관련 개념 맵 (Knowledge Graph)

LRU (Least Recently Used) | LFU의 가장 강력한 라이벌로, 빈도(조회수)를 무시하고 오직 최근 접속 시간만 맹신하여 고인물 알박기를 없앤 알고리즘
에이징 (Aging) | LFU의 치명적 단점인 '과거 찌꺼기의 높은 카운트'를 시간의 흐름에 따라 반토막 내어 깎아버리는 필수 융합 마법
MFU (Most Frequently Used) | LFU의 반대 개념. 많이 쓰인 건 단물이 빠졌을 테니 죽이자는 이상한 힙스터 역발상 알고리즘 (실무 폐기됨)
Cache Pollution (캐시 오염) | 한 번 쓱 읽고 버리는 스캔 파일이 램에 들어와 기존 VIP 데이터를 몽땅 쫓아내는 테러로, LFU가 이를 가장 잘 막아냄
Redis maxmemory-policy | OS 바깥의 실무 백엔드 환경에서 LFU 철학이 가장 훌륭하게 작동하며 세계를 지배하고 있는 인메모리 캐시 세팅

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

LFU 알고리즘이 뭔가요? 장난감 상자를 비울 때, "태어나서 지금까지 제일 적게 가지고 논(조회수가 낮은) 비인기 장난감"을 골라 버리는 룰이에요.
뭐가 문제인가요? 아기 때 10,000번 만지고 초등학생 된 이후론 한 번도 안 본 '딸랑이'가 조회수가 높다는 이유로 상자 명당을 평생 차지하는 어이없는 일(알박기)이 생겨요.
그럼 어떻게 고치나요? 엄마가 1년이 지날 때마다 모든 장난감의 조회수 기록을 반으로 깎아버려요(에이징). 그러면 옛날에만 많이 놀았던 딸랑이 기록이 0으로 줄어들어 시원하게 버릴 수 있답니다!