LFU

LFU 는 캐시에서 버릴 항목을 골라 줍니다. 지금까지 가장 적게 쓰인 항목이 그 대상입니다. 자주 찾는 값은 오래 남습니다. 어쩌다 한 번 찾은 값은 먼저 나갑니다.

쉽고 빠른 이해

캐시가 꽉 차면 쓰인 횟수가 가장 적은 항목을 골라 버립니다. 상품 정보를 담는 캐시라면 하루 종일 조회되는 인기 상품은 남습니다. 한 번 조회되고 만 상품이 먼저 나갑니다.

캐시는 작아서 모든 값을 담지 못합니다. 곧 다시 찾을 값을 버리면 느린 데이터베이스까지 다시 다녀와야 합니다. 인기가 오래 이어지는 값이라면, 지금까지 쓰인 횟수가 다음에도 쓰일지를 잘 알려 줍니다.

1. 항목마다 쓰인 횟수를 붙여 둡니다
2. 항목을 읽을 때마다 그 횟수를 하나 올립니다
3. 캐시가 꽉 차면 횟수가 가장 작은 항목을 버리고 새 항목을 넣습니다

대가가 있습니다. 예전에 많이 쓰였던 값은 지금 안 쓰여도 횟수가 커서 오래 버팁니다. 새로 들어온 값은 횟수가 작아 금방 밀려납니다.

상세

LFU(Least Frequently Used, 최소 빈도 사용)는 캐시가 가득 찼을 때 버릴 항목을 고르는 절차입니다. 캐시는 느린 원본 앞에 두는 작은 저장소입니다. 곧 다시 찾을 값을 버리면 그 값을 원본에서 다시 가져와야 합니다. 그래서 무엇을 버리느냐가 캐시의 쓸모를 가릅니다. LFU 는 지금까지 쓰인 횟수가 가장 적은 항목을 버립니다.

이 절은 LFU 가 횟수를 어떻게 세는지부터 봅니다. 칸 셋짜리 작은 캐시에 접근을 차례로 흘려 보내며 무엇이 버려지는지 따라갑니다. 이어서 버릴 항목을 빨리 고르는 구조와, 횟수만 보는 탓에 생기는 약점을 봅니다.

횟수를 세고 버리는 규칙

항목마다 사용 횟수를 하나씩 붙입니다. 새 항목은 캐시에 들어올 때 횟수 1 로 시작합니다. 그 뒤로 캐시에서 그 항목을 읽을 때마다 횟수가 하나씩 오릅니다.

찾는 값이 캐시에 있으면 적중이라고 부릅니다. 없으면 캐시 미스입니다. 한 번의 접근은 이 둘에 따라 아래처럼 갈립니다.

flowchart TD
    A["접근"] --> B{"캐시에 있나"}
    B -- "있음 · 적중" --> C["값을 돌려주고 횟수를 하나 올린다"]
    B -- "없음 · 캐시 미스" --> D{"캐시가 가득 찼나"}
    D -- "찼음" --> E["횟수가 가장 작은 항목을 버린다"]
    D -- "안 찼음" --> F["원본에서 가져와 횟수 1 로 넣는다"]
    E --> F

적중이면 횟수만 오르고 끝납니다. 캐시 미스면 원본에서 값을 가져와 넣습니다. 넣을 공간이 없으면 먼저 횟수가 가장 작은 항목을 버립니다. 이렇게 항목을 골라 내보내는 일을 축출이라고 부릅니다.

가장 작은 횟수를 가진 항목이 여럿일 때도 있습니다. 그중 무엇을 버릴지는 구현이 정합니다. 흔히 그중 가장 오래 안 쓰인 항목을 버립니다.

칸 셋짜리 캐시의 접근 기록

칸이 셋인 캐시에 A, A, A, B, C, B, D 순서로 접근이 온다고 합시다. 아래 표의 괄호 안 숫자가 그 항목의 사용 횟수입니다.

일곱째 접근에서 캐시가 가득 찼습니다. 횟수가 가장 작은 C 가 나가고 D 가 들어옵니다. 세 번 쓰인 A 는 남습니다.

같은 접근을 LRU(Least Recently Used, 최근 최소 사용)에 흘리면 결과가 달라집니다. LRU 는 마지막으로 쓰인 지 가장 오래된 항목을 버립니다. 일곱째 접근 직전에 A 는 셋째, C 는 다섯째, B 는 여섯째에 마지막으로 쓰였습니다. 그래서 LRU 는 가장 많이 쓰인 A 를 버립니다.

버릴 항목을 상수 시간에 고르는 구조

규칙은 간단해도 매번 가장 작은 횟수를 찾는 일은 공짜가 아닙니다. 이 소절은 쉬운 방법 둘의 비용부터 봅니다. 이어서 모든 연산을 상수 시간에 끝내는 구조로 넘어갑니다. 상수 시간은 항목이 아무리 많아도 한 번에 드는 시간이 일정하다는 뜻입니다.

가장 쉬운 방법은 버릴 때마다 모든 항목의 횟수를 훑는 것입니다. 항목이 n 개면 한 번 버릴 때 n 개를 다 봅니다. 시간이 항목 수에 비례한다는 뜻으로 이것을 O(n) 이라고 적습니다.

힙을 쓰면 나아집니다. 힙은 가장 작은 값을 늘 꼭대기에 두는 트리라서 꼭대기를 꺼내는 데 O(log n) 이 듭니다. O(log n) 은 항목이 두 배로 늘 때 드는 시간이 한 단계씩만 는다는 뜻입니다.

그런데 읽을 때마다 횟수가 바뀝니다. 그때마다 그 항목이 트리 안에서 다시 제자리를 찾아 줘야 하므로 읽기에도 O(log n) 이 붙습니다.

상수 시간 구조는 두 가지를 겹칩니다. 첫째는 키로 항목을 바로 찾는 해시테이블입니다. 해시테이블은 키에서 계산한 값으로 저장 칸을 곧장 정하므로, 항목이 많아도 훑지 않고 찾습니다. 이 저장 칸이 버킷입니다.

둘째는 횟수마다 따로 둔 줄입니다. 같은 횟수를 가진 항목끼리 한 줄에 묶습니다. 그리고 가장 작은 횟수가 몇인지를 값 하나로 따로 적어 둡니다. 축출할 때 그 값이 가리키는 줄로 곧장 가려는 것입니다.

flowchart TD
    MIN["가장 작은 횟수 값 · 1"] --> 줄1
    subgraph 줄1["횟수 1 줄"]
        P1["P · 오래된 끝"] --- Q1["Q · 새로 붙은 끝"]
    end
    subgraph 줄2["횟수 2 줄"]
        R1["R"]
    end
    subgraph 줄3["횟수 3 줄"]
        S1["S · 오래된 끝"] --- T1["T · 새로 붙은 끝"]
    end
    줄1 -- "횟수가 오르면" --> 줄2
    줄2 -- "횟수가 오르면" --> 줄3

그림은 앞 표와 다른 예입니다. 항목 다섯(P~T)이 횟수별 줄 셋에 나뉘어 있고, 가장 작은 횟수 값 1 이 횟수 1 줄을 가리킵니다. 줄 사이 화살표는 항목의 횟수가 하나 오를 때 옮겨 가는 방향입니다.

줄 안에서는 새로 들어온 항목을 「새로 붙은 끝」에 붙입니다. 그러면 반대쪽 「오래된 끝」에 그 횟수에서 가장 오래 안 쓰인 항목이 남습니다. 앞에서 본 동률 규칙이 이 순서로 저절로 지켜집니다.

각 줄은 이중 연결 리스트로 만듭니다. 이중 연결 리스트는 항목마다 앞과 뒤를 가리키는 연결이 있는 목록입니다. 그래서 줄 가운데 있는 항목도 훑지 않고 바로 떼어 옮길 수 있습니다.

네 연산의 비용은 아래와 같습니다. 표의 O(1) 은 상수 시간을 적는 표기입니다. 해시테이블로 항목을 찾은 뒤에는 줄에서 떼고 붙이는 일만 남습니다.

최악이 O(n) 인 연산은 해시테이블을 거치는 둘입니다. 키가 한 버킷으로 몰리면 그 버킷에 든 항목을 끝까지 훑어야 합니다. 줄 쪽 연산은 떼고 붙이기뿐이라 언제나 상수 시간입니다.

횟수를 올리다 원래 줄이 비는 경우가 있습니다. 그 줄이 가장 작은 횟수의 줄이었다면 가장 작은 횟수 값을 하나 올립니다. 옮긴 항목이 바로 한 칸 위 줄로 갔으니, 이제 그 줄이 가장 작은 횟수의 줄입니다. 새 항목을 넣으면 가장 작은 횟수 값은 1 로 돌아갑니다.

공간은 항목 수에 비례합니다. 항목마다 횟수 하나와 앞뒤 연결 둘이 붙습니다. 해시테이블도 항목 수만큼 칸을 씁니다.

지난 인기에 묶이는 약점

LFU 의 횟수는 오르기만 합니다. 한때 많이 쓰였던 항목은 지금 아무도 안 찾아도 큰 횟수를 들고 캐시에 남습니다. 어제의 톱기사가 오늘도 뉴스 캐시를 차지하는 식입니다.

같은 문제의 반대편에는 새 항목이 있습니다. 새 항목은 횟수 1 로 들어옵니다. 곧 인기를 얻을 값이어도 횟수를 쌓기 전에 다음 새 항목이 오면 가장 먼저 밀려납니다.

둘이 겹치면 캐시가 쓸모없는 항목으로 찹니다. 이렇게 다시 안 찾을 항목이 공간을 차지해 적중이 줄어드는 현상을 캐시 오염이라고 부릅니다.

오래된 횟수를 깎는 방법

흔한 처방은 횟수에 나이를 먹이는 것입니다. 일정한 시간마다 모든 항목의 횟수를 절반으로 줄이는 식입니다. 그러면 옛날에 쌓은 횟수는 점점 작아집니다. 최근에 쌓은 횟수가 더 큰 몫을 합니다. 이 방식을 에이징(aging)이라고 부릅니다.

다른 처방은 세는 기간을 좁히는 것입니다. 최근 일정 구간에 들어온 접근만 셉니다. 둘 다 LFU 에 최근성(얼마나 최근에 쓰였나)을 조금 섞는 일입니다. 얼마나 섞을지는 깎는 주기와 구간 길이가 정합니다.

처음부터 최근성과 빈도를 함께 보도록 만든 교체 알고리즘도 있습니다. ARC(Adaptive Replacement Cache)와 2Q 가 그 예입니다.

LRU 와의 비교

두 방식은 과거의 어떤 증거를 믿느냐가 다릅니다. LRU 는 얼마나 최근에 쓰였나를 봅니다. LFU 는 얼마나 자주 쓰였나를 봅니다. 아래 표는 그 차이를 다섯 줄로 나눠 봅니다.

넷째 줄이 고르는 기준이 됩니다. 한 번씩만 훑는 대량 접근은 보고서 배치처럼 목록 전체를 한 번씩 읽고 지나가는 작업입니다. LFU 에서는 이런 항목이 횟수 1 로 들어오므로 오래 쌓인 항목을 못 밀어냅니다.

잘 맞는 데이터와 안 맞는 데이터

LFU 는 인기 순위가 오래 유지되는 데이터에 맞습니다. 쇼핑몰의 상품 이미지나 자주 읽는 설정값처럼 찾는 값의 순위가 잘 안 바뀌는 경우입니다. 이런 데서는 가끔 뜸해지는 인기 항목을 지켜 주는 것이 캐시 적중률을 올립니다. 캐시 적중률은 요청 가운데 캐시에서 바로 답한 비율입니다.

인기가 빨리 바뀌는 데이터에는 맞지 않습니다. 뉴스나 실시간 피드처럼 어제의 인기가 오늘 쓸모없어지는 경우입니다. 이때는 LRU 나 에이징을 붙인 LFU 가 새 인기를 더 빨리 따라갑니다.

횟수를 들고 다니는 비용도 있습니다. 항목마다 횟수를 저장해야 합니다. 읽을 때마다 그 항목을 다른 줄로 옮기므로 읽기가 곧 쓰기가 됩니다. 여러 스레드가 함께 읽는 캐시라면 그 옮김을 잠금으로 지켜야 합니다.

관련 항목

LFU 가 속하는 상위 분류

축출 · 캐시 교체 정책 · 페이지 교체 알고리즘 · 캐싱 · 캐시 · 메모이제이션

LFU 와 겨루는 다른 축출 정책

LRU · MRU · FIFO 축출 · CLOCK · LRM · TTL · 무작위 축출 · 벨라디 알고리즘

최근성과 빈도를 섞은 교체 알고리즘

ARC · LRU-K · 2Q · LIRS · TinyLFU · W-TinyLFU

LFU 를 구현하는 자료구조

해시테이블 · 이중 연결 리스트 · 연결 리스트 · 힙 · 최소 힙 · 카운트-민 스케치

LFU 가 기대는 접근 패턴

시간 지역성 · 참조 지역성 · 지프의 법칙 · 워킹 셋 · 핫 키

LFU 의 결과를 재는 지표

캐시 적중률 · 캐시 적중 · 캐시 미스 · 캐시 오염