[SOSP'25] cache_ext : background (page cache in Linux kernel)

(현재 자유롭게 정리한 것... 이후 가독성 좋게 정리한 버전 올릴 예정)

리눅스 페이지 캐시는
storage (disk) access = disk i/o를 줄여
성능에 기여하는 커널의 기능

리눅스 페이지 캐시는
최근에 접근한 것인지 recency
캐시에서 eviction 된 이후 최근에 다시 필요했는지 refault
를 기반으로 판단하는 단순 휴리스틱한 시스템

리눅스 페이지 캐시의 기본 구조는
active list와  inactive list 이고

처음 들어오면  inactive list,
한 번 더 접근되면 active list,
page cache 부족해서 eviction을 수행해야하면
inactive list의 head부터 제거하는 흐름

기준은 최근에 접근했는가 =최근 접근 여부를 중요함으로 간주

cache pollution은
중요하지 않은 데이터가 cache에 올라와서
hot 데이터가 cache에서 밀려나는 현상

seq access pattern인 scan
db처럼 데이터가 많은 경우 full scan 요청을 수행하거나
로그 전체를 읽거나
ml 데이터를 프리로드하는 것처럼
한 번 접근하고 다시 안 접근하는 데이터가 전부지만
캐시에 다 들어온 경우
정말 캐시에 있어야 하는 핫 데이터들이 모두 eviction 된다

burst, background workload
짧은 시간에 대량 데이터에 접근하는 백그라운드 배치 작업이나
분석 태스크에서는
기존의 워킹 셋을 밀어내기 때문에
cache에 있어야 할 hot 데이터들이 eviction 된다

linux는 최근 접근된 것을 중요하다고 판단하는 메커니즘을 채택하고 있기 때문에
스캔에서 다시 접근하지 않을 데이터도 최근에 접근되었다는 이유로 중요하다고 착각하고 캐시에 올린 것

워킹셋 사이즈가 캐시 사이즈보다 더 큰 경우
페이지가 계속 캐시에 들어왔다가 나가고 다시 들어오며
page fault와 eviction이 반복적으로 일어나는
thrashing이 발생

thrashing은 disk i/o가 폭증하는 상황이므로
scan heavy 워크로드 같은 경우 성능이 급락한다

이 문제를 해결하기 위해
eviction된 페이지의 실제 데이터는 없애고
메타데이터만 남겨두는
shadow entry 가 도입된다

eviction 후 페이지가 다시 들어왔을 때
남겨뒀던 shadow entry를 확인하는데
이때 eviction 이후 다시 요청되기까지의 시간을 의미하는
refault distance 를 계산했을 때

거리가 짧으면
방금 eviction 했는데 또 캐시에 등록되었으니
중요한 페이지를 잘못 eviction한 것

리눅스에서는
refault가 빠르면 inactive를 거치지 않고 바로 active list에
느리면 inactive list에 유지하도록 하는
refault heuristic 방식으로 recency 의 부족함을 보완

하지만 refault heuristic 또한 과거 히스토리만 반영하는 한계 있음

frequency, future reuse, workload 의미 확인 불가

=======
리눅스의 one size fits all 정책은 실패

리눅스의 페이지 캐시는 approximate LRU와 제한적인 refault heuristic에 의존하는 하나의 고정된 정책을 사용하기 때문에 서로 다른 접근 패턴을 가지는 heterogenous한 워크로드를 충분히 반영하지 못함. 각 워크로드마다 optimal policy가 다르지만 단일 정책이 적용되면서 throughput 감소와 latency 증가, cache pollution과 thrashing이 발생함. 이러한 리눅스의 one size fits all 방식은 구조적으로 sub optimal하다고 판단할 수 있음