LRU 캐시와 MGLRU — 커널 페이지 회수의 진화
고전 LRU의 동작(승격·퇴출)과 스캔 오염으로 핫 페이지가 쫓겨나는 약점, 그리고 다세대(MGLRU)가 재접근 승격으로 그것을 막는 과정을 실행한다.
1 / 10메모리가 부족하면 커널은 페이지를 쫓아냅니다. 누구를? 'Least Recently Used — 가장 오래 안 쓴 것'이 고전의 답입니다. 용량 4짜리 캐시로 봅니다.
고전 LRU — 목록 하나MGLRU — 세대 여럿 (커널 6.1+)
최근 ←····→ 퇴출 순
인기 페이지 A: 생존 · 초록 = 핫, 노랑 = 일회성 스캔
단계 목록 · 키보드 ←/→ 이동, Space 재생
LRU는 '최근에 쓴 것은 곧 또 쓴다'는 베팅이지만 '한 번 접근'과 '자주 접근'을 구분하지 못한다 — MGLRU는 페이지를 세대로 나누고 재접근만 승격시켜, 스캔이 핫 페이지를 밀어내는 오염을 막는다.
왜 헷갈리는가
"LRU면 충분한데 커널은 왜 갈아엎었나?"가 질문의 핵심이다. 백업·grep·대용량 순차 읽기 한 번이면 LRU 목록이 일회성 페이지로 도배되고, 정작 매일 쓰는 페이지가 디스크로 쫓겨난다(그다음 접근은 페이지 폴트). 데스크톱이 백업 중에 버벅이던 고전적 이유다.
애니메이션이 보여주는 것
LRU 무대: 접근하면 맨 앞, 넘치면 꼬리 퇴출 — 여기까진 완벽하다. 스캔 장면에서 균열이 난다: S1~S4가 목록을 점령하고 핫 페이지 A가 쫓겨난다. LRU의 시야에는 '언제 썼나'만 있고 '몇 번 썼나'가 없기 때문이다.
MGLRU 무대: 페이지가 세대에 속하고, 시간이 지나면 세대째 늙는다. 재접근된 페이지만 젊은 세대로 승격 — 스캔 페이지들은 승격 없이 함께 늙어 자기들끼리 퇴출된다. A는 최신 세대에 남는다. 리눅스 6.1부터 기본이 된 이 구조는 회수 스캔 비용도 줄인다(페이지별 참조 비트 훑기 대신 세대 단위 판단).
커널 밖에서도 같은 문제
스캔 저항은 캐시 설계의 보편 주제다.
- 고전 리눅스도 이미 두 목록(active/inactive)으로 LRU를 근사했다 — MGLRU는 그 2단계를 N세대로 일반화한 것.
- DB 버퍼 풀: PostgreSQL은 클록 스윕+링 버퍼(대량 스캔 격리), MySQL InnoDB는 미드포인트 삽입(새 페이지를 중간에) — 전부 스캔 오염 대책.
- 애플리케이션 캐시: Redis의 LFU 모드, Caffeine의 TinyLFU(빈도 스케치로 입장 심사) — '빈도'를 신호에 더하는 같은 진화.
- 면접 단골 'LRU 캐시 구현'(해시맵+이중 연결 리스트, O(1))은 이 이야기의 출발점일 뿐 — 왜 그것으로 부족한가까지가 진짜 이해다.
기억할 것
- LRU = 최근성만 본다. 그래서 O(1)로 아름답고, 스캔 한 방에 무너진다.
- MGLRU = 세대 + 재접근 승격 — '한 번'과 '자주'가 갈라진다.
- 같은 문제의 답들: active/inactive, LFU, TinyLFU, 미드포인트 삽입.
- 대량 순차 읽기가 서비스 캐시를 비우는 사고 — 원인은 거의 항상 스캔 오염이다.