LRU

가장 오래 안 쓴 것부터 내보내는 교체 정책(Least Recently Used).

왜 이것이 합리적인가 — 지역성

과거 행동으로 미래를 예측하는 것이다.

시간 지역성 : 최근에 쓴 것은 곧 다시 쓸 가능성이 높다

• (반복문 변수, 자주 조회하는 사용자 정보) 공간 지역성 : 그 근처도 곧 쓸 가능성이 높다

• (배열 순회, 순차 파일 읽기)

시간 지역성에 근거한 것이 LRU다. 오래 안 쓴 것은 앞으로도 안 쓸 것이라 본다.

이론적 최적과의 관계

OPT(최적 교체) 는 "미래에 가장 나중에 쓸 페이지"를 내보낸다. 가장 좋지만 미래를 알아야 해서 구현 불가능하다. LRU는 이 OPT를 과거를 거울 삼아 근사한 것이다.

O(1) 구현 — 해시맵 + 이중 연결 리스트

면접 단골 구현 문제다.

• 해시맵: key → 노드 주소 — (O(1) 탐색)

• 이중 연결 리스트: 최근 사용 순 정렬 — (O(1) 이동·삭제)

  • head(최근) ⇄ [A] ⇄ [B] ⇄ [C] ⇄ tail(오래됨)

• get(B) — → 해시맵으로 B 노드를 즉시 찾음 → 리스트에서 떼어 head로 이동

• put(D) — → 가득 찼으면 tail 노드 제거 → head에 D 추가

왜 이중 연결이어야 하나 — 노드를 리스트 중간에서 떼어내려면 앞 노드를 알아야 한다. 단일 연결이면 앞을 찾는 데 O(n)이 든다.

왜 해시맵이 필요한가 — 리스트만으로는 특정 키를 찾는 데 O(n)이다.

두 자료구조의 약점을 서로 메우는 구조다. 자바에는 LinkedHashMap(capacity, 0.75f, true) 로 내장돼 있다 (세 번째 인자 accessOrder=true가 LRU 동작).

하드웨어에서는 근사만 쓴다

정확한 LRU는 접근할 때마다 순서를 갱신해야 한다. CPU 캐시나 페이지 테이블에서 매 접근마다 이러면 비용이 감당이 안 된다.

클럭 알고리즘(2차 기회) 이 실제로 쓰인다.

페이지마다 참조 비트 1개만 둔다 시곗바늘처럼 돌면서:

• 참조 비트 = 1 → 0으로 바꾸고 지나감 (한 번 더 기회)
• 참조 비트 = 0 → 이 페이지를 내보냄

비트 하나로 "최근에 썼는가"를 근사한다. 훨씬 싸면서 LRU와 비슷하게 동작한다.

LRU가 나쁜 경우 — 순차 스캔 오염

캐시 크기 100, 자주 쓰는 데이터 100개가 들어 있음
→ 배치 작업이 10만 건을 한 번씩 순차 조회
→ 캐시가 배치 데이터로 전부 교체됨 (한 번 쓰고 다시 안 쓸 데이터)
→ 원래 데이터는 전부 밀려남 → 이후 히트율 0%

한 번만 쓰이는 데이터가 자주 쓰이는 데이터를 밀어낸다.

대안

Redis는 allkeys-lru와 allkeys-lfu를 모두 제공한다. 배치가 도는 환경이면 LFU가 낫다.

MySQL InnoDB는 버퍼 풀을 young/old 두 구역으로 나눠(기본 5:3), 새로 읽은 페이지를 old 구간에 넣고 일정 시간 뒤 다시 접근돼야 young으로 올린다. 풀스캔이 버퍼 풀을 통째로 오염시키는 것을 막는 장치다.