LRU

자리가 모자랄 때 무엇을 버릴지 고르는 절차입니다. 가장 오래 안 쓰인 것을 버립니다. 넣는 것은 지금까지의 접근 순서와 캐시가 담을 수 있는 양입니다. 나오는 것은 다음에 버릴 항목입니다.

상세

LRU 는 Least Recently Used 의 줄임말입니다. 가장 오래 안 쓰인 항목을 버리는 절차입니다. 캐시에 새 값을 넣어야 하는데 자리가 없을 때, 마지막으로 쓰인 지 가장 오래된 항목을 골라 버립니다. 이 고르는 일을 축출이라 부릅니다.

무엇이 "가장 오래 안 쓰인 것" 인지는 마지막 접근 시각이 정합니다. 항목마다 마지막으로 접근된 때를 남겨 두고, 그때부터 지금까지 흐른 시간이 가장 긴 항목이 버릴 대상입니다. 그래서 무엇을 접근으로 셀지가 곧 축출 순서를 정합니다. 접근을 세는 기준(읽기만 셀지, 쓰기도 셀지, 어떤 경로를 거친 접근인지)은 구현마다 다를 수 있습니다.

이 절차는 가정 위에 서 있습니다. 최근에 쓰인 것이 곧 또 쓰이리라는 가정입니다. 접근 패턴은 시간 지역성을 보이는 것과 보이지 않는 것으로 나뉩니다. 접근 분포가 이 가정과 어긋나면(예: 골고루 흩어진 접근, 또는 한 번 훑고 마는 대량 접근) 이 절차가 잘 다루지 못하는 접근이 늘어납니다.

복잡도

n 은 캐시에 들어 있는 항목 수입니다.

상수 시간은 자료구조 두 개를 겹쳐야 나옵니다. 해시 표와, 모든 항목을 관통하는 이중 연결 리스트입니다. 해시 표가 "이 키가 어디 있나" 를 상수 시간에 답하고, 이중 연결 리스트가 "가장 오래된 것이 무엇인가" 를 훑지 않고 답합니다. 둘 중 하나가 없으면 어느 한쪽이 전체를 훑는 일이 됩니다.

공간은 항목마다 붙습니다. 리스트가 모든 항목을 관통하므로 링크가 항목 수만큼 생깁니다.

정확한 순서를 포기하면 비용의 축이 바뀝니다. 마지막 접근 시각을 전부 비교하는 대신 표본을 뽑아 그중 가장 오래된 것을 버리는 근사 방식도 있습니다. 그러면 축출 한 번의 비용이 n 이 아니라 표본 수에 비례합니다. 정확도와 비용이 맞바꿈됩니다.

예시

Redis 의 maxmemory-policy

maxmemory-policy allkeys-lru
maxmemory-samples 5

첫 줄이 메모리 상한에 닿았을 때 무엇을 버릴지 정합니다. allkeys-lru 는 모든 키를 대상으로 가장 오래 안 쓰인 키를 버립니다. volatile-lru 는 만료가 붙은 키로 대상을 좁힙니다. 기본값은 noeviction 이라 아무것도 버리지 않고 쓰기 명령에 오류를 돌려줍니다. 둘째 줄이 축출 한 번에 검사할 표본 수입니다. 기본값 5 가 충분히 쓸 만한 결과를 낸다고 문서가 적습니다. 10 은 참 LRU 에 아주 가깝게 근사하지만 CPU(Central Processing Unit, 중앙처리장치)를 더 씁니다. 3 은 검사를 덜 하고 정확도도 덜합니다. 최대값은 64 입니다.

memcached 의 HOT · WARM · COLD

-o lru_maintainer 를 켜면 LRU 하나가 셋으로 갈립니다. 새 항목은 HOT 으로 들어옵니다. 두 번 이상 맞은 항목을 활성으로 봅니다. 갱신은 항목이 리스트 바닥에 닿을 때만 일어납니다. HOT 에서 활성이면 WARM 으로 옮기고, WARM 에서 활성이면 WARM 에 남습니다. COLD 에서 활성인 항목은 곧바로 WARM 으로 옮깁니다. HOT 과 WARM 은 그 슬랩 클래스가 쓸 수 있는 메모리의 N 퍼센트로 상한이 걸립니다. COLD 는 기본적으로 상한이 없습니다. 백그라운드 스레드가 한도에 닿을 때마다 항목을 리스트 사이로 옮깁니다.

리눅스 커널의 페이지 회수 리스트

커널의 unevictable LRU 문서는 익명과 파일, 활성과 비활성으로 갈린 LRU 순서 리스트들을 이야기합니다. multi-gen LRU 는 이 자리에 세대를 둡니다. 세대 하나가 접근 최근성이 비슷한 페이지 무리를 나타냅니다. 문서는 memcg LRU 의 젊은 세대와 늙은 세대를 활성 리스트와 비활성 리스트에 빗댑니다. max_seq 가 올라가면 승격이 일어나고, 그것이 활성화에 해당합니다.

nginx 의 캐시 관리자

캐시 관리자 프로세스가 max_size 로 정한 최대 크기와 min_free 로 정한 최소 여유 공간을 지켜봅니다. 크기를 넘거나 여유 공간이 모자라면 가장 오래 안 쓰인 데이터를 지웁니다. 한 번에 다 지우지 않습니다. manager_files · manager_threshold · manager_sleep 가 정한 반복 단위로 지웁니다. 한 반복에서 지우는 항목은 기본 100 개를 넘지 않습니다. inactive 로 정한 시간 동안 접근되지 않은 데이터는 신선도와 무관하게 캐시에서 제거됩니다. 기본값은 10분입니다.

같은 서버의 인증서 캐시에도 같은 이름이 나옵니다. proxy_ssl_certificate_cache 의 max 가 캐시에 담을 원소의 최대 개수를 정하고, 넘치면 가장 오래 안 쓰인 원소가 제거됩니다.

Java 의 LinkedHashMap

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
   return size() > MAX_ENTRIES;
}

removeEldestEntry 는 put 과 putAll 이 새 항목을 넣은 뒤에 호출됩니다. 참을 돌려주면 가장 오래된 항목을 지웁니다. 이 재정의는 판이 100 개까지 자라게 두고, 그 뒤로는 새 항목이 들어올 때마다 가장 오래된 항목을 지워 100 개를 유지합니다. 접근 순서로 도는 판을 만드는 생성자가 따로 있고, 문서는 그런 판이 LRU 캐시를 만드는 데 잘 맞는다고 적습니다.

동작

flowchart TD
    A[접근] --> B{캐시에 있나}
    B -- 있음 --> C[값을 돌려주고 최근 쓴 자리로 옮긴다]
    B -- 없음 --> D[원본에서 가져와 넣는다]
    D --> E{한도를 넘었나}
    E -- 넘음 --> F[가장 오래 안 쓰인 항목을 버린다]
    F --> E
    E -- 안 넘음 --> G[끝]
    C --> G

찾는 값이 캐시에 있으면 그 값을 돌려줍니다. 그리고 그 항목을 가장 최근에 쓴 자리로 옮깁니다. 이 옮김이 다음 축출 대상을 바꿉니다. 없으면 원본에서 가져와 캐시에 넣습니다.

넣고 나서 한도를 봅니다. Redis 는 클라이언트가 캐시에 데이터를 더하는 명령을 실행할 때마다 메모리 사용량을 확인합니다. 한도보다 크면 정책에 따라 키를 버립니다. 사용량이 한도 아래로 돌아올 때까지 버립니다. 그림에서 버림 뒤에 다시 한도 검사로 돌아오는 화살표가 그 되풀이입니다. 한 명령이 많은 데이터를 더하면 한도를 한동안 크게 넘길 수도 있습니다.

칸 수로 한도를 두는 자리도 같은 모양입니다. Java 는 put 뒤에 removeEldestEntry 를 불러 참이면 가장 오래된 항목을 지웁니다. memcached 는 항목을 리스트 바닥에서 꺼내 회수하거나 축출합니다.

갱신을 미루는 변형이 있습니다. memcached 는 -o lru_maintainer 를 켜면 LRU 갱신을 항목이 리스트 바닥에 닿는 순간까지 미룹니다. 접근할 때마다 자리를 옮기지 않습니다. 리눅스 커널도 접근 순간에 리스트를 고치지 않습니다. 노화와 축출이라는 두 절차가 따로 돌면서 닫힌 고리를 이룹니다.

대가

정확한 순서를 유지하려면 읽기에서도 자료구조를 고쳐야 합니다. 읽기가 쓰기가 됩니다. 그 자리에 잠금이 붙습니다. memcached 문서는 새 LRU 에서 대부분의 항목 읽기에 LRU 잠금을 더는 쓰지 않게 됐다고 적습니다. 잠금이 남는 자리는 주로 저장과 백그라운드 스레드입니다. 이것을 지연을 줄이는 부수 목표로 적어 둡니다. 커널 문서도 세대를 넘는 이동이 LRU 잠금을 요구한다고 적습니다.

그래서 제품들이 정확한 LRU 에서 물러섭니다. Redis 는 근사한다고 문서에 적고, 그 이유로 정확한 구현이 메모리를 더 쓴다는 점을 듭니다. 설정 파일 주석도 LRU · LFU(Least Frequently Used, 최소 빈도 사용) · LRM(Least Recently Modified, 최근 최소 수정) · 최소 TTL(Time To Live, 생존 시간)이 정밀한 알고리즘이 아니라 근사 무작위 알고리즘으로 구현돼 있다고 적습니다. 메모리를 아끼려는 선택입니다. 대신 결과가 확률적이 됩니다. 이론상의 구현이라면 오래된 키 중 앞의 절반이 만료되리라 기대하는데, Redis 의 것은 오래된 키를 확률적으로만 만료시킵니다.

표본 수는 양쪽으로 값을 치릅니다. 늘리면 참 LRU 에 가까워지지만 CPU 를 더 씁니다. 줄이면 검사가 줄고 정확도도 줄어듭니다. Redis 문서는 표본을 10 으로 올려 보고 캐시 미스 비율이 달라지는지 확인해 보라고 적습니다. 다만 멱법칙 접근 패턴을 쓴 시뮬레이션에서는 참 LRU 와 Redis 근사의 차이가 미미하거나 없었다고 적습니다. 애플리케이션 입장에서는 사실상 동등하다고도 적습니다.

한 번 훑고 마는 대량 접근이 순서를 통째로 밀어냅니다. 다시 안 쓰일 항목들이 방금 접근됐다는 이유만으로 앞자리를 차지합니다. memcached 는 세그먼트를 나눈 첫째 목표가 활성 항목을 훑기로부터 더 잘 보호하는 것이라고 적습니다. 다시 맞지 않는 항목은 HOT 을 지나 COLD 를 거쳐 바닥으로 흘러나갑니다. 커널은 시간 지역성을 보이지 않는 접근 패턴을 따로 두고, VM_SEQ_READ 와 VM_RAND_READ 가 붙은 접근을 예외로 다룹니다. 활성과 비활성을 가른 리스트, 세대, HOT · WARM · COLD 는 모두 이 대가를 덜려고 순수한 LRU 에서 벗어난 구조입니다.

리스트가 길어지면 훑는 일 자체가 부담이 됩니다. 커널 문서는 축출할 수 없는 folio 가 리스트에 많이 섞인 상황을 듭니다. 128GB 메모리의 x86_64 노드 하나에 4k 페이지가 3천2백만 개 넘게 있습니다. 이 중 큰 비율이 축출 불가면 vmscan 이 축출 가능한 적은 수를 찾느라 리스트를 훑는 데 많은 시간을 씁니다. 모든 CPU 가 몇 시간에서 며칠 동안 vmscan 에 100 퍼센트를 쓰고 시스템이 전혀 응답하지 않는 상황까지 관측됐다고 적습니다.

마지막으로 이 절차는 모델이지 보장이 아닙니다. Redis 문서는 LRU 를 앞으로의 접근 가능성을 예측하는 모델이라고 부릅니다. 접근 분포가 이 모델과 어긋나면 가장 오래 안 쓰인 것이 곧 가장 안 쓰일 것이라는 전제가 무너집니다. 그때는 축출이 매번 다시 필요해질 항목을 버립니다.

관련 항목

LRU 를 이루는 구성 요소

해시 표 · 이중 연결 리스트

LRU 가 속하는 상위 분류

축출

LRU 와 자리를 두고 겨루는 축출 방식

LFU · LRM · TTL

LRU 의 하위 종류

Multi-Gen LRU · Unevictable LRU · 세그먼트 · HOT · WARM · COLD

LRU 를 실제로 구현한 사례

Redis · memcached · nginx · LinkedHashMap · 커널 · InnoDB 버퍼 풀

LRU 축출을 관리하는 프로세스

캐시 관리자 · vmscan · 노화 · 승격

커널 LRU 훑기가 부딪히는 규모

folio · x86 · 노드

LRU 가 기대는 접근 분포 가정

시간 지역성 · 멱법칙 · 파레토 법칙

LRU 가 치르는 비용

잠금 · 지연 · 캐시 미스 · CPU

LRU 기준과 맞세워지는 캐시 성질

신선도