273. LFU (Least Frequently Used)

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

본질: LFU (Least Frequently Used)는 캐시 공간이 꽉 차서 데이터를 쫓아내야 할 때, **"과거에 가장 적은 횟수로 불렸던(참조 빈도가 가장 낮은) 데이터가 미래에도 가장 안 쓰일 것이다"**라고 판단하여 희생양으로 삼는 교체 알고리즘이다.

가치: 시간만 따지는 LRU와 달리 **'장기적인 인기도'**를 카운팅하기 때문에, 한 번 반짝 쓰이고 버려지는 일회성 데이터(캐시 오염)에 의해 진짜 핵심 VIP 데이터가 밀려나는 억울한 현상을 완벽하게 방어한다.

융합: 참조 횟수를 무한정 기록해야 하는 하드웨어 오버헤드와 과거 데이터가 자리를 독점하는 '적폐' 문제 때문에 CPU 캐시보다는 CDN, 웹 프록시, 인메모리 DB 등 소프트웨어 기반 대용량 캐시에서 주로 사용된다.

Ⅰ. 개요 및 필요성

개념: LFU는 '최소 빈도 사용' 알고리즘으로, 캐시 내의 모든 데이터 블록에 각각 '호출 횟수'라는 꼬리표를 달아두고, CPU가 찾을 때마다 이 숫자를 1씩 올린다. 새로운 공간이 필요할 때는 이 누적 숫자가 가장 낮은(가장 인기 없는) 블록을 방출한다.
필요성: LRU(가장 오래 안 쓴 놈 방출)의 맹점을 보완하기 위함이다. 1만 번 호출된 초특급 VIP 데이터라도, 단 한 번의 대용량 파일 복사(풀 스캔)가 쓱 지나가면 '오래전에 쓰였다'는 이유로 캐시 밖으로 쫓겨나는 참사가 벌어진다. LFU는 언제 썼느냐가 아니라 **"지금까지 얼마나 우리 시스템에 기여했느냐(충성도)"**를 기준으로 데이터를 평가하여 진짜 핫(Hot) 데이터를 지켜낸다.
💡 비유: LRU가 "최근 한 달간 안 온 손님은 VIP에서 강등!"시키는 무자비한 최근 실적주의라면, LFU는 **"최근에 좀 뜸했더라도 지난 10년간 우리 가게를 1,000번 넘게 찾아준 단골손님은 끝까지 대접하자"**는 누적 마일리지 우대 정책과 같습니다.
등장 배경: 하드웨어 설계 초기에는 완벽한 적중률을 위해 LFU가 연구되었으나, 카운터 회로의 복잡도 문제로 실리콘 캐시에서는 외면받았다. 하지만 인터넷 시대가 열리며 소프트웨어로 캐시를 통제하는 CDN이나 Redis 같은 시스템에서, 콘텐츠의 '인기도'를 기반으로 한 캐싱이 압도적인 효율을 내면서 화려하게 부활했다.

┌──────────────────────────────────────────────────────────────┐
│           LFU (Least Frequently Used)의 데이터 교체 프로세스 도식            │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│ [ 상황: 4칸짜리 캐시, 데이터마다 누적 호출 횟수(Freq)가 기록됨 ]       │
│                                                              │
│ @현재 캐시 상태 :                                               │
│  [ Data A (50번) ]  [ Data B (2번) ]  [ Data C (99번) ]  [ Data D (1번) ] │
│                                                        ▲             │
│                                                     (이놈이 LFU)      │
│ [ 새로운 데이터 'E' 적재 시도 ]                                     │
│  1. "누가 제일 인기 없냐?" -> 누적 1번 호출된 "Data D" 확인.        │
│  2. Data D를 캐시에서 즉시 방출(Eviction)하고 퇴출시킴.              │
│  3. 빈자리에 Data E를 넣고 카운터를 1로 세팅함.                      │
│                                                              │
│ * 핵심 원리: "한 번 뜨내기는 영원한 뜨내기다." 데이터의 체급을 따지는 방식.  │
└──────────────────────────────────────────────────────────────┘

[다이어그램 해설] LFU의 위력은 '축적된 숫자'에서 나온다. 위 그림에서 Data C는 비록 10분 동안 한 번도 안 쓰였더라도, 과거에 쌓아온 '99번'이라는 압도적인 훈장 덕분에 캐시에서 보호받는다. 반면 Data D는 방금 막 1초 전에 들어왔더라도 누적 횟수가 1번뿐이라면, LFU는 "넌 반짝 인기일 뿐이야"라며 가차 없이 버린다. 이것이 일회성 쓰레기 데이터로부터 캐시의 성역을 지키는 LFU의 강력한 뚝심이다.

📢 섹션 요약 비유: 도서관 서가를 정리할 때, 어제 어떤 학생이 한 번 펼쳐본 이름 모를 전공서적보다는, 10년 동안 1만 번 대출된 '해리포터' 소설책을 무조건 입구 쪽 제일 좋은 자리에 계속 놔두는 것과 같습니다.

Ⅱ. 아키텍처 및 핵심 원리

LFU의 하드웨어적 한계: 카운터 오버헤드

LFU가 CPU L1/L2 캐시 같은 초고속 하드웨어에 쓰이지 못하는 치명적 이유다.

물리적 공간 낭비: 캐시의 모든 라인마다 참조 횟수를 기록할 '가산기(Adder)'와 '저장용 SRAM'을 별도로 만들어야 한다. 만약 데이터가 100만 번 불리면 카운터 비트만으로도 엄청난 칩 면적을 잡아먹는다.
연산 지연: 데이터를 읽을 때마다 카운터를 올리고 전체를 비교해서 최솟값을 찾아내는 회로가 너무 복잡해, CPU의 5GHz 클럭 속도를 도저히 따라갈 수 없다. (그래서 LFU는 주로 소프트웨어 캐시에서만 쓴다.)

LFU의 고질병: 과거의 망령 (Stale Data)

LFU의 가장 큰 논리적 약점은 **'변화에 둔감하다'**는 것이다.

프로그램 초기에만 10,000번 쓰이고 두 번 다시 안 쓰이는 '초기화 변수'가 있다고 치자.
이 변수는 10,000점이라는 높은 점수 방패를 두르고 캐시 한복판을 영원히 점거한다(적폐).
정작 지금 막 열심히 일을 시작한 '현재의 핵심 변수'들은 점수가 1, 2, 3점부터 시작하므로, 억울하게 계속 캐시에서 쫓겨나는 스래싱(Thrashing) 현상이 발생한다.
📢 섹션 요약 비유: 20년 전 빌보드 차트 1위를 10주 연속으로 했던 옛날 가수가 누적 점수가 높다는 이유만으로 음악 방송 무대를 영원히 차지하고, 정작 지금 전 세계에서 난리 난 신인 아이돌은 점수가 낮아 무대에 못 서는 불공평한 상황과 같습니다.

Ⅲ. 비교 및 연결

LRU vs LFU의 결정적 차이

비교 항목	LRU (최근 최소 사용)	LFU (최소 빈도 사용)	아키텍처적 통찰
판단 기준	최근성 (Recency)	빈도성 (Frequency)	시간 vs 횟수
강점	변화하는 트렌드에 민감함	일회성 데이터(오염)에 강함	적응력 vs 뚝심
약점	풀 스캔 시 캐시 초토화	과거 데이터의 알박기 (적폐)	오염 vs 적폐
구현 비용	낮음 (비트 스위치로 가능)	매우 높음 (거대 카운터 필수)	하드웨어 vs 소프트웨어
주 사용처	CPU 하드웨어 캐시, OS	CDN, 인메모리 DB, 웹 프록시	속도 vs 효율

보완 기법: LFU with Aging (노화 알고리즘)

LFU의 '적폐' 문제를 해결하기 위해 현대 아키텍처는 **'망각'**을 도입했다. 주기적으로 모든 데이터의 카운터 값을 비트 시프트 연산(>> 1)으로 반토막 내버리는 것이다. 이렇게 하면 10,000점이었던 과거 데이터도 시간이 지나면 5,000 -> 2,500 -> 1,250점으로 점차 힘을 잃고 결국 퇴출된다. 이를 통해 과거와 현재의 균형을 맞춘다.

📢 섹션 요약 비유: 사람을 평가할 때 "최근 실적만 보는 것"은 정이 없고, "평생 실적만 보는 것"은 고인 물을 만듭니다. 가장 좋은 방법은 "누적 실적을 보되, 옛날 실적은 시간이 지날수록 점수를 깎아주는" 합리적인 인사 평가 시스템입니다.

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

실무 시나리오

Redis 인메모리 캐시 정책 튜닝 사용자 추천 시스템의 Redis 서버 메모리가 가득 차서 OOM이 발생할 때. 만약 우리 앱이 '특정 베스트셀러 100개'에 조회가 80% 몰리는 구조(파레토 법칙)라면, 아키텍트는 maxmemory-policy를 allkeys-lfu로 설정해야 한다. LFU는 어쩌다 한 번 검색된 수백만 개의 쩌리 데이터를 가차 없이 버리고, 효자 상품 100개를 철통 같이 보호하여 시스템 전체 응답 속도를 수호한다.
글로벌 CDN의 비디오 캐싱 전략 넷플릭스 같은 서비스에서 어제 개봉한 신작 영화(LRU 1등)와 10년째 전국민이 보는 스테디셀러 애니메이션(LFU 1등) 중 무엇을 남길 것인가? 신작 영화는 며칠 뒤면 인기가 식지만, 애니메이션은 매일 수만 명이 본다. CDN 실무자는 객체의 조회 빈도를 최우선으로 하는 LFU 기반 로직을 사용하여 비싼 국제 회선 대역폭 낭비를 최소화한다.
소프트웨어 캐시 라이브러리의 진화 (W-TinyLFU) 현대 고성능 자바 캐시의 표준인 Caffeine 캐시는 순수 LRU나 LFU를 쓰지 않는다. 카운터 오버헤드를 줄이기 위해 블룸 필터(Count-Min Sketch)라는 확률적 구조로 횟수를 압축 기록하고, 최근성(LRU)과 빈도성(LFU)을 절묘하게 섞은 Window TinyLFU 알고리즘을 쓴다. 실무자는 바퀴를 재발명하지 말고 이 검증된 하이브리드 라이브러리를 가져다 써야 한다.

안티패턴

운영체제 페이지 교체에 순수 LFU 적용: 윈도우나 리눅스 커널의 페이지 교체 데몬에 무지성으로 LFU를 적용하는 행위. 시스템 부팅 시 잠깐 쓰였던 수만 개의 라이브러리들이 막대한 누적 빈도 때문에 절대 램에서 안 나가고 자리를 차지하여, 정작 지금 실행 중인 게임이나 크롬 브라우저가 쓸 메모리를 다 뺏어버리는 대참사를 초래한다.
📢 섹션 요약 비유: LFU 식당은 단골을 우대합니다. 하지만 20년 전에 100번 왔던 손님을 위해 지금도 예약석을 비워두는 것은 멍청한 짓입니다. 1달 동안 안 오면 단골 포인트를 소멸시키는 '마일리지 유효기간(Aging)' 정책을 반드시 섞어 써야 합니다.

Ⅴ. 기대효과 및 결론

기술 진화와 미래 전망

AI 기반 적응형 캐시 (ARC): 이제는 LFU냐 LRU냐를 고민하지 않는다. 워크로드의 성격(순차형 vs 반복형)을 하드웨어가 실시간으로 분석하여, LRU 리스트와 LFU 리스트의 크기 비율을 동적으로 조절하는 ARC (Adaptive Replacement Cache) 기술이 엔터프라이즈 스토리지의 글로벌 표준으로 자리 잡았다.
확률적 카운팅: 메모리 낭비를 줄이기 위해 정확한 조회수 대신 "아마 이 정도일 것"이라고 짐작하는 확률적 알고리즘(HyperLogLog 등)이 LFU와 결합하여 대규모 분산 캐시의 효율을 높이고 있다.

결론

LFU(Least Frequently Used)는 "많이 사랑받은 데이터가 결국 시스템을 구원한다"는 빈도주의 통계학의 결정체다. 비록 트랜지스터를 아껴야 했던 CPU 코어의 가혹한 환경에서는 LRU에 패배했지만, 용량의 제약이 풀리고 정교한 소프트웨어 알고리즘을 소화할 수 있는 현대의 분산 시스템과 클라우드 환경에서 가장 강력한 가치 수호자로 화려하게 부활했다.

📢 섹션 요약 비유: 단거리 100m 달리기(CPU 캐시)에서는 출발이 제일 빠른 선수(LRU)가 이기지만, 42km 마라톤(대용량 데이터 시스템)에서는 꾸준한 폐활량(LFU)을 가진 선수가 결국 승리하는 법입니다.

📌 관련 개념 맵

개념 명칭	관계 및 시너지 설명
캐시 오염	LRU의 최대 천적이자, LFU가 태어난 명분이 된 데이터 편중 현상.
LRU	LFU와 대척점에 있는 시간 중심 알고리즘으로, 현대 하드웨어 캐시의 표준.
에이징	LFU의 '적폐' 단점을 해결하기 위해 카운터를 주기적으로 깎아내는 기술.
ARC	LRU와 LFU의 장점을 실시간으로 섞어 최적의 적중률을 내는 하이브리드 제왕.
Count-Min Sketch	수억 개의 데이터 빈도를 아주 작은 메모리로 오차 없이 기록하는 LFU용 압축 장부.

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

장난감 상자가 꽉 찼을 때 장난감을 버리는 방법 중 'LFU'는 "내가 지금까지 몇 번이나 가지고 놀았지?" 하고 횟수를 세어보는 거예요.
어제 처음 사서 딱 한 번 만져본 로봇보다는, 옛날에 샀지만 1,000번이나 조립하며 놀았던 소중한 레고를 상자에 남겨두는 방식이죠.
이렇게 하면 잠깐 호기심에 한 번 만지고 안 쓰는 유행 장난감들 때문에, 진짜 내가 제일 좋아하는 단골 장난감이 상자에서 쫓겨나는 슬픈 일을 막을 수 있답니다!