축출

축출은 담을 자리가 모자랄 때 이미 들어 있는 것을 골라 내보내는 일입니다. 새로 들어올 것에 자리를 내주려고 합니다. 무엇을 내보낼지 정하는 규칙을 축출 정책이라고 부릅니다.

상세

책장이 꽉 찬 집에 새 책을 사 오면 꽂혀 있던 책 하나를 빼야 합니다. 무엇을 뺄지는 사람이 정합니다.

축출은 담는 곳이 가득 찬 상태에서 이미 들어 있는 항목을 골라 내보내는 동작입니다. 성립하려면 세 가지가 정해져야 합니다. 언제 시작할지, 무엇을 후보로 둘지, 후보 중에서 무엇을 고를지입니다. 이 셋을 묶어 정한 것이 축출 정책입니다.

flowchart TD
    A[새 항목을 넣으려 함] --> B{자리가 있나}
    B -->|있다| C[넣는다]
    B -->|없다| D[내보낼 항목을 고른다]
    D --> E[골라낸 항목을 내보낸다]
    E --> B

넣으려는 순간에 자리를 확인합니다. 모자라면 항목 하나를 골라 내보내고 다시 확인합니다. 자리가 생길 때까지 이 과정을 되풀이합니다.

내보낸 항목이 어떻게 되는지는 그 항목이 복사본인지에 달려 있습니다. 원본이 다른 곳에 남아 있는 복사본이면 그냥 버려도 됩니다. 필요해지면 원본에서 다시 가져오면 됩니다. 원본이 없는 항목이면 버리기 전에 다른 곳으로 옮겨야 합니다.

배경

담는 곳은 크기가 정해져 있습니다. 넣을 것은 계속 들어옵니다. 자리를 늘리는 것으로는 끝이 나지 않습니다. 늘린 만큼 더 들어오면 같은 자리에 다시 서게 됩니다.

가득 찬 다음에 할 수 있는 일은 둘뿐입니다. 새로 들어오는 것을 거절하거나, 이미 들어 있는 것 중 하나를 내보내는 것입니다. 거절하는 쪽을 고르면 담는 곳은 처음 채워진 내용에 묶입니다. 그래서 무엇을 내보낼지 정하는 규칙이 필요해졌습니다.

이 동작에 축출이라는 이름이 붙었습니다. 원문 표기는 eviction 입니다. 자리를 비우려고 이미 들어 있는 것을 내보낸다는 뜻은 어느 자리에서나 같습니다.

갈래

앞에서 짚은 세 가지 결정이 그대로 축입니다. 대부분의 갈래는 마지막 결정에서 갈립니다. 무엇을 보고 내보낼 항목을 고르느냐입니다. 고르는 기준 앞에 후보 범위가 한 번 더 갈립니다. Redis 는 정책 이름의 앞머리로 이 범위를 나눕니다. allkeys 로 시작하면 전체 키가 후보입니다. volatile 로 시작하면 만료 시각이 붙은 키만 후보입니다. 후보에 만료 시각이 붙은 키가 하나도 없으면 volatile 정책들은 아무것도 내보내지 않는 정책처럼 동작합니다.

사용 이력

언제 쓰였는지, 얼마나 자주 쓰였는지를 보고 고릅니다. Redis 의 allkeys-lru 는 LRU(Least Recently Used, 최근 최소 사용) 키를 내보냅니다. allkeys-lfu 는 LFU(Least Frequently Used, 최소 빈도 사용) 키를 내보냅니다. 가장 오래전에 고쳐진 키를 보는 allkeys-lrm 도 있습니다.

브라우저 저장소도 같은 기준을 씁니다. MDN(Mozilla Developer Network) 은 기기의 저장 공간이 모자라는 상황에서 브라우저가 LRU 정책을 쓴다고 적습니다. 가장 오래 안 쓰인 오리진의 데이터를 지웁니다. 저장 공간 압박이 계속되면 그다음으로 오래 안 쓰인 오리진으로 넘어갑니다. 이 축출은 지속 저장으로 표시되지 않은 오리진에만 걸립니다.

리눅스 커널도 회수 대상 폴리오를 LRU 리스트로 추적합니다. 내보낼 수 없는 폴리오는 unevictable 리스트로 따로 빼서 vmscan 에서 감춥니다. 커널 문서는 이 장치가 없을 때의 상황을 적어 뒀습니다. 내보낼 수 없는 페이지가 큰 비중을 차지하면 vmscan 이 내보낼 수 있는 소수를 찾느라 LRU 리스트를 훑는 데 많은 시간을 쓰게 됩니다.

남은 수명

만료 시각이 붙은 키 중에서 남은 TTL(Time To Live, 유효 시간)이 가장 짧은 것을 먼저 내보냅니다. Redis 의 volatile-ttl 이 이 기준입니다. 어차피 곧 사라질 것을 먼저 내보내는 셈입니다.

무작위

사용 이력을 보지 않고 아무거나 고릅니다. Redis 의 allkeys-random 은 전체 키에서, volatile-random 은 만료 시각이 붙은 키에서 무작위로 고릅니다.

자원 압박 신호

항목 하나하나의 이력이 아니라 담는 곳 전체의 상태를 보고 언제 시작할지를 정하는 자리도 있습니다. 쿠버네티스의 kubelet 은 축출 신호를 축출 임계값과 견주어 축출 결정을 내립니다. 축출 신호는 특정 시점의 자원 상태입니다. 축출 임계값은 노드에 남아 있어야 하는 자원의 최소량입니다.

임계값은 두 종류로 갈립니다. 소프트 임계값에는 관리자가 정한 유예 기간이 붙습니다. kubelet 은 유예 기간이 지나기 전까지는 파드를 내보내지 않습니다. 하드 임계값에는 유예 기간이 없습니다. 하드 임계값에 걸리면 kubelet 은 종료에 0초 유예를 씁니다.

쓰기 거절

아무것도 내보내지 않는 것도 정책의 한 자리입니다. Redis 의 noeviction 은 키를 내보내지 않는 대신 데이터를 새로 담는 명령에 에러를 돌려줍니다. 이미 있는 데이터를 읽기만 하는 명령은 그대로 동작합니다. 복제를 쓰는 경우 이 조건은 주 데이터베이스에만 걸립니다.

예시

Redis

maxmemory 100mb

maxmemory 설정 지시자는 캐시 데이터에 쓸 메모리 상한을 정합니다. 위 한 줄은 상한을 100 메가바이트로 둡니다. redis.conf 파일에 적어 시작할 때 넘길 수 있습니다.

클라이언트가 캐시에 데이터를 더 담는 명령을 실행할 때마다 Redis 는 메모리 사용량을 확인합니다. 사용량이 상한보다 크면 고른 축출 정책에 따라 키를 내보냅니다. 전체 사용량이 상한 아래로 돌아올 때까지 계속합니다. 정책으로 allkeys-lru 를 고르면 최근 최소 사용 키부터 나갑니다.

kubelet

memory.available<100Mi      리눅스 노드
memory.available<500Mi      윈도우 노드
nodefs.available<10%
imagefs.available<15%
nodefs.inodesfree<5%        리눅스 노드
imagefs.inodesfree<5%       리눅스 노드

kubelet 의 기본 하드 축출 임계값입니다. 노드에 남은 메모리가 100 메비바이트 아래로 떨어지면 리눅스 노드에서 하드 임계값에 걸립니다. 디스크 쪽은 남은 용량 비율과 남은 아이노드 비율을 각각 봅니다. 하드 임계값이라 유예 기간 없이 파드가 나갑니다.

경계

수명이 다해 사라진 항목도 축출인가. 아닙니다.

Redis 는 두 사건을 다른 이름으로 알립니다. 유효 시간이 붙은 키가 수명이 다해 데이터 집합에서 없어지면 expired 이벤트가 납니다. 메모리를 비우려고 maxmemory 정책에 따라 키가 나가면 evicted 이벤트가 납니다. 둘 다 키가 없어진 사건입니다. 그런데 알림 이름은 갈라져 있습니다.

HTTP(HyperText Transfer Protocol) 캐시를 정한 RFC(Request for Comments) 9111 도 둘을 따로 둡니다. 응답에 아주 먼 만료 시각을 적어 신선도 수명을 길게 잡을 수 있습니다. 그래도 많은 캐시가 그보다 훨씬 일찍 응답을 내보낸다고 적습니다. 수명이 남아 있는데도 나갈 수 있다는 뜻입니다.

가르는 선은 이유입니다. 항목 자신의 수명이 끝나서 없어지면 만료입니다. 자리가 모자라 누군가를 골라야 해서 내보내면 축출입니다.

관련 항목

이것을 고르는 기준이 되는 알고리즘

LRU · LFU · LRM(Least Recently Modified, 최근 최소 수정) · CLOCK · TTL

이것을 실제로 구현·채택한 시스템

Redis · 쿠버네티스 · kubelet · 리눅스 · 커널 · MDN · nginx

이것과 헷갈리는 이웃

만료 · 키스페이스 알림(Keyspace Notifications) · RFC 9111

이것을 촉발하는 자원 임계값

maxmemory · 축출 신호 · 축출 임계값

이것을 실행하는 리눅스 커널 메커니즘

vmscan · 회수(reclaim) · unevictable 리스트

이것이 실제로 내보내는 대상

파드 · 오리진(origin) · 폴리오(folio)