273. LFU (Least Frequently Used)

핵심 인사이트 (3줄)

본질: LFU (Least Frequently Used)는 캐시가 가득 찼을 때 가장 적게 참조된 항목을 내보내는 정책으로, "최근성"보다 "누적 인기"를 더 중요하게 본다.

가치: 반복 조회되는 소수의 핵심 데이터가 있는 워크로드에서는 LRU (Least Recently Used)보다 캐시 오염에 강해 적중률을 안정적으로 높일 수 있다.

판단 포인트: 다만 과거 인기 데이터가 오래 남는 고착 현상과 카운터 관리 비용이 크므로, 순수 LFU보다 Aging, TinyLFU 같은 보완형으로 이해하는 것이 실무적이다.

Ⅰ. 개요 및 필요성

LFU (Least Frequently Used)는 캐시 교체 정책 중 하나로, 저장 공간이 부족할 때 누적 참조 횟수가 가장 낮은 블록이나 객체를 희생 대상으로 선택하는 방식이다. 핵심 가정은 단순하다. 지금까지 거의 호출되지 않은 데이터는 앞으로도 덜 쓰일 가능성이 높다는 것이다.

이 정책이 필요한 이유는 모든 워크로드가 최근성만으로 설명되지 않기 때문이다. 예를 들어 CPU 바깥의 웹 캐시, 콘텐츠 전송 네트워크, 추천 시스템 캐시에서는 일부 인기 객체가 오랜 기간 반복 호출된다. 이때 LRU는 대량 순차 접근이 한 번 지나가도 기존 인기 객체를 밀어낼 수 있지만, LFU는 장기적으로 많이 쓰인 데이터를 보호해 캐시 오염을 줄인다.

즉 LFU는 "방금 썼는가"보다 "계속 사랑받는가"를 묻는 정책이다. 그래서 짧은 순간의 접근 패턴보다 장기 빈도 분포가 중요한 환경에서 의미가 크다. 반대로 패턴 변화가 빠른 환경에서는 과거 실적이 현재 판단을 왜곡할 수 있어 주의가 필요하다.

📢 섹션 요약 비유: LFU는 서점의 베스트셀러 진열대와 같다. 어제 잠깐 누가 집어 본 책보다, 한 달 내내 꾸준히 많이 팔린 책을 앞줄에 남겨 두는 방식이다.

Ⅱ. 아키텍처 및 핵심 원리

LFU의 동작은 단순한 듯 보이지만, 실제로는 조회 기록, 최솟값 탐색, 동률 처리, 노화 보정이 함께 엮인다. 캐시 엔트리마다 참조 횟수 카운터를 두고, 히트가 발생할 때마다 그 값을 증가시킨다. 미스가 발생해 공간이 필요하면 가장 작은 카운터를 가진 엔트리를 제거한다. 동률일 때는 보통 오래된 항목을 함께 제거하도록 LRU 보조 규칙을 붙인다.

아래 그림은 LFU가 교체 대상을 고르는 흐름을 요약한 것이다.

┌──────────────────────────────────────────────────────────────────────┐
│                  LFU 교체 판단 흐름: 빈도 기반 선택                 │
├──────────────────────────────────────────────────────────────────────┤
│ 캐시 조회                                                            │
│   │                                                                  │
│   ├─ Hit ───────────────▶ 해당 엔트리 freq = freq + 1               │
│   │                                                                  │
│   └─ Miss ─▶ 빈 공간 존재? ── Yes ─▶ 새 엔트리 적재, freq = 1       │
│                    │                                                 │
│                    No                                                │
│                    ▼                                                 │
│           최소 freq 엔트리 집합 선택                                 │
│                    │                                                 │
│          동률이면 LRU 기준으로 1개 결정                              │
│                    │                                                 │
│                    ▼                                                 │
│             희생 엔트리 제거 후 신규 적재                            │
└──────────────────────────────────────────────────────────────────────┘

이 구조의 설계 포인트는 다음과 같다.

요소	역할	설계상 의미
빈도 카운터	각 엔트리의 참조 횟수 기록	정확할수록 유리하지만 메모리 오버헤드 증가
최소 빈도 추적	희생 후보 탐색	빠르게 찾으려면 별도 버킷/리스트 구조 필요
동률 해소 규칙	동일 빈도 엔트리 중 선택	LFU 단독보다 LFU+LRU가 흔함
Aging	오래된 빈도 점수 감쇠	과거 인기의 영구 고착 방지

하드웨어 관점에서 순수 LFU가 CPU 1차 캐시 같은 초저지연 영역에 잘 안 쓰이는 이유도 여기서 나온다. 참조할 때마다 카운터를 갱신해야 하고, 교체 시에는 최소 빈도를 빠르게 찾아야 하므로 구현 복잡도와 지연이 커진다. 그래서 LFU는 보통 소프트웨어 캐시나 대용량 메모리 계층에서 더 현실적이며, 하드웨어 캐시에서는 근사 정책이나 단순 정책이 선호된다.

📢 섹션 요약 비유: LFU는 놀이공원 인기 놀이기구 운영표와 같다. 탑승 횟수를 계속 세다가 자리가 부족해지면 가장 손님이 적은 시설부터 정리하는 방식이다.

Ⅲ. 비교 및 연결

LFU를 제대로 이해하려면 LRU, FIFO (First In First Out), 그리고 LFU의 보완형을 함께 봐야 한다. 각 정책은 "미래 사용을 무엇으로 예측할 것인가"에 대한 서로 다른 철학을 가진다. LRU는 최근 접근을, FIFO는 들어온 순서를, LFU는 누적 빈도를 기준으로 삼는다.

항목	LFU	LRU	FIFO
예측 기준	많이 쓰인 데이터는 계속 쓰일 것	최근에 쓴 데이터는 곧 다시 쓸 것	먼저 들어온 데이터부터 교체
강점	장기 인기 데이터 보호	변화하는 패턴 추적에 강함	구현이 단순함
약점	과거 데이터 고착, 카운터 비용	순차 스캔에 약함	사용 패턴 반영이 약함
적합 환경	인기 편중이 큰 객체 캐시	일반적 메모리/페이지 캐시	단순 버퍼 관리

특히 LFU와 LRU의 차이는 시간 축 vs 빈도 축의 차이다. 예를 들어 영상 플랫폼에서 오래도록 반복 시청되는 인기 콘텐츠는 LFU가 잘 지킨다. 반면 실시간 분석처럼 매 분 데이터 분포가 바뀌는 시스템에서는 예전 인기 데이터가 의미를 잃기 쉬워 LRU 쪽이 더 민첩하다.

이 한계를 줄이기 위해 실무에서는 순수 LFU 대신 변형 정책을 많이 쓴다. Aging은 시간이 지날수록 빈도 점수를 깎아 현재성을 회복한다. TinyLFU는 작은 확률 자료구조로 빈도를 근사해 메모리 비용을 줄인다. Window TinyLFU는 최근성 구간과 빈도 구간을 나눠 두 기준을 함께 활용한다.

📢 섹션 요약 비유: LFU와 LRU의 차이는 반 친구 대표를 뽑는 기준과 같다. LFU는 "지금까지 가장 많은 표를 받은 학생"을, LRU는 "최근 분위기에서 가장 주목받는 학생"을 더 믿는다.

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

실무에서 LFU는 "이론적으로 더 똑똑한가"보다 "내 워크로드가 빈도 중심인가"로 판단해야 한다. 예를 들어 상품 조회, 인기 영상, 자주 읽히는 프로필처럼 상위 소수 객체에 트래픽이 집중되는 구조라면 LFU 계열이 유리하다. 반대로 세션 데이터처럼 최근성 자체가 가치인 데이터는 LFU보다 LRU 계열이 더 자연스럽다.

설계 시 확인할 판단 기준은 다음과 같다.

접근 편중도: 상위 소수 키가 전체 조회의 큰 비중을 차지하는가?
패턴 변동 속도: 어제 인기였던 데이터가 오늘도 인기일 가능성이 높은가?
구현 비용 허용 여부: 빈도 카운트 저장과 유지 비용을 감당할 수 있는가?
노화 필요성: 과거 인기 데이터가 자리를 독점하면 장애가 되는가?

대표적인 적용 예는 Redis의 allkeys-lfu, 웹 프록시 캐시, CDN 객체 캐시다. 이런 환경에서는 캐시 용량이 수 기가바이트에서 수십 기가바이트에 이르고, 객체 단위로 교체가 이뤄지므로 하드웨어 캐시보다 정책 구현 유연성이 높다. 이때 순수 LFU보다 에이징 계수나 샘플링을 섞어야, 한때만 인기 있던 객체가 끝없이 남는 문제를 막을 수 있다.

안티패턴도 분명하다. 패턴 변화가 매우 빠른 실시간 데이터에 LFU를 그대로 적용하면 예전 인기 키가 공간을 오래 점유해 현재 필요한 데이터를 밀어낼 수 있다. 따라서 기술사 답안에서는 "LFU 채택"만 쓰지 말고, Aging 포함 여부와 LRU 혼합 여부까지 함께 제시해야 설계 판단으로 인정받는다.

📢 섹션 요약 비유: LFU를 쓰는 일은 단골손님 우대 정책을 만드는 것과 같다. 단골이 많은 가게에는 효과적이지만, 유행이 매주 바뀌는 팝업스토어라면 옛날 마일리지만 믿고 좌석을 배정하면 안 된다.

Ⅴ. 기대효과 및 결론

LFU의 기대효과는 분명하다. 인기 편중이 뚜렷한 환경에서는 장기 히트 데이터를 안정적으로 보존해 적중률, 응답속도, 원본 저장소 부하 감소 효과를 동시에 얻을 수 있다. 특히 네트워크 왕복 지연이 큰 환경에서는 캐시 적중률 몇 퍼센트 차이만으로도 체감 성능이 크게 달라진다.

하지만 LFU는 "많이 쓰인 적이 있다"는 사실을 지나치게 신뢰하는 정책이기도 하다. 그래서 시간 변화에 둔감하고, 구현이 단순하지 않으며, 작은 캐시나 초고속 하드웨어에는 부담이 된다. 이 한계 때문에 현대 시스템은 순수 LFU를 교과서적 기준점으로 두고, 실제 구현에서는 근사 LFU나 혼합 정책으로 이동하고 있다.

정리하면 LFU는 빈도 중심 워크로드를 위한 정책으로 기억하는 것이 가장 정확하다. 언제나 최고의 교체 정책이 아니라, "인기 분포가 오래 유지되는가?"라는 질문에 답이 예라면 강력해지는 선택지다.

📢 섹션 요약 비유: LFU는 오래 사랑받는 노래를 남기는 플레이리스트 관리자와 같다. 다만 유행곡이 자주 바뀌는 시장에서는 예전 히트곡만 붙잡지 않도록 순위를 주기적으로 다시 계산해야 한다.

📌 관련 개념 맵

개념	연결 포인트
캐시 교체 정책 (Cache Replacement Policy)	제한된 캐시 공간에서 어떤 항목을 제거할지 결정하는 상위 개념
LRU (Least Recently Used)	LFU와 가장 자주 비교되는 시간 기반 정책
캐시 오염 (Cache Pollution)	일회성 대량 접근이 유용한 데이터를 밀어내는 현상으로 LFU의 등장 이유
Aging	LFU의 고착 문제를 완화하기 위해 오래된 빈도 점수를 감쇠하는 기법
TinyLFU	근사 빈도 추정으로 LFU의 메모리 비용을 줄인 실무형 변형

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

단순 교체 정책
    │
    ▼
FIFO (First In First Out) · Random Replacement
    │
    ▼
LRU (Least Recently Used)
    │
    ▼
LFU (Least Frequently Used)
    │
    ├─▶ Aging 적용 LFU
    │
    ▼
TinyLFU · Window TinyLFU

이 흐름은 교체 정책이 단순 순서 기반에서 최근성 기반, 다시 빈도 기반으로 확장되고, 이후에는 비용 문제를 줄이는 근사·혼합형으로 진화했음을 보여준다.

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

장난감 상자가 꽉 찼을 때 LFU는 "지금까지 제일 적게 갖고 논 장난감"을 먼저 꺼내요.
자주 갖고 노는 레고는 오래됐어도 상자에 남고, 한 번만 만져 본 장난감은 먼저 나가요.
하지만 옛날에만 많이 놀고 지금은 안 노는 장난감도 있으니, 가끔 점수를 다시 매겨 줘야 해요.