| MDK: Rethinking the data center memory reclamation problem | |
|---|---|
| Author | Shaurya Patel, Suli Yang, Yawen Wang, Kan Wu, Alexandra (Sasha) Fedorova, Margo Seltzer, Kimberly Keeton |
| Conference | 20th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2026) |
| Year | 2026 |
개요
이 논문은 데이터 센터의 proactive Memory reclamation을 전통적 Page replacement와 다른 최적화 문제로 재정의한다. 핵심 결과물은 Memory Designer's Kit (MDK, 메모리 설계 도구 모음)로, Service Level Objective (SLO, 서비스 수준 목표)를 지키면서 평균 메모리 절감량을 최대화하는 정책을 설계·평가하는 오프라인 도구다.
Background
| 구분 | 전통적 page replacement | 데이터 센터 memory reclamation |
|---|---|---|
| 목표와 제약 | 고정된 cache 크기에서 전체 실행의 miss ratio 최소화 | 모든 측정 window의 성능 proxy 한도를 지키면서 평균 메모리 절감량 최대화 |
| 동작 시점 | 메모리 pressure가 발생한 뒤 reactive eviction | 새 job을 배치할 여유를 만들기 위한 proactive reclamation |
| 대표 지표 | 전체 실행에 걸친 cache miss ratio | window별 promotion rate, Pressure Stall Information (PSI, 자원 대기로 손실된 시간 비율), Secondary Tier Access Ratio (STAR, 느린 memory tier 접근 비율) |
| 설계 도구 | Optimal page replacement (OPT)와 Miss Ratio Curve (MRC, miss 비율 곡선) | Optimal Performance Proxy (OPP, 최적 성능 proxy)와 Memory Performance Curve (MPC, 메모리 성능 곡선) |
이 논문이 주로 사용하는 promotion rate는 한 time window에서 발생한 non-compulsory page fault 수를 그 window에서 접근한 unique page 수로 나눈 값이다. Cassandra에서 Yahoo! Cloud Serving Benchmark (YCSB)를 실행한 실험에서는 이 값이 tail latency와 함께 증가했다. 저자들은 이를 trace에서 계산 가능한 SLO proxy로 사용하고, 시간에 따른 평균 메모리 절감량을 최대화한다.
Motivation
Dynamic Random-Access Memory (DRAM) 비용 때문에 서버당 더 많은 job을 수용하는 것은 Total Cost of Ownership (TCO, 총소유비용)과 직결된다. g-swap과 Transparent Memory Offloading (TMO) 같은 시스템은 cold page를 compressed memory, Solid-State Drive (SSD), 또는 Compute Express Link (CXL) 기반의 저렴한 tier로 미리 내보낸다. 이때 절감 공간은 새 job을 배치할 만큼 오래 유지되어야 하고 application SLO도 지켜야 한다.
하지만 기존의 OPT와 VMIN(가변 크기 cache에서 miss를 최소화하는 오프라인 정책)은 전체 miss 수를 줄이더라도 fault를 같은 window에 몰아 promotion-rate 한도를 위반할 수 있다. MRC도 고정 cache 크기와 miss ratio만 다루므로, 시간에 따라 크기가 변하는 reclamation policy를 비교하기 어렵다. 새로운 optimal bound와 비교 곡선이 필요한 이유다.
Importance
이 논문의 가치는 새로운 heuristic 하나보다 정책 설계 문제의 목표와 제약을 뒤집은 것에 있다. 전통적 caching이 “주어진 용량에서 miss를 얼마나 줄일 수 있는가”를 물었다면, MDK는 “각 window의 성능 budget 안에서 메모리를 얼마나 더 내놓을 수 있는가”를 묻는다.
MDK는 이 질문에 맞는 optimal oracle, policy curve, 빠른 curve 생성기를 연결한다. 또한 기존 age-based policy의 개선 여지를 측정하고 oracle의 결정을 practical policy로 옮기는 과정을 보여 주므로, 재사용 가능한 memory-policy 설계 방법론이라는 의미가 있다.
Main Idea
핵심 통찰은 miss의 총량이 아니라 미래의 각 time window가 허용하는 promotion budget을 직접 관리해야 한다는 것이다. 같은 수의 page fault라도 한 window에 집중되면 SLO를 위반한다. 반대로 fault를 여러 window에 분산하면서 page를 가능한 한 일찍 reclaim하면, 성능 한도를 지키면서 메모리 절감 시간을 늘릴 수 있다.
MDK는 이를 MPC, OPP, 두 가지 eviction property, efficient MPC generator로 구현한다. 이 조합은 달성 가능한 upper bound를 보여 주고, 수많은 parameter를 각각 simulation하지 않고 policy의 성능–메모리 tradeoff를 계산한다.
Design
- Memory Performance Curve (MPC, 메모리 성능 곡선): x축은 target promotion rate, y축은 평균 메모리 절감량이다. 동일한 성능 한도에서 policy를 비교하고 원하는 절감량에 필요한 성능 비용을 찾는다. 가능한 지점이 연속적이지 않으므로 선이 아닌 점으로 표시한다.
- Optimal Performance Proxy (OPP, 최적 성능 proxy): 첫 pass에서 window별 unique page 수를 센다. 두 번째 pass에서는 page의 다음 접근 window를 미리 보고, 그 page fault를 추가해도 해당 window의 promotion-rate 한도를 넘지 않을 때 현재 접근 직후 reclaim한다. Page를 가장 일찍 내보내 절감 시간을 최대화하지만, 미래 정보가 필요한 오프라인 oracle이다.
- Eviction properties와 빠른 MPC 생성:
- Eviction decisions property는 aggressive한 setting이 덜 aggressive한 setting의 모든 eviction을 포함한다는 뜻이다. Eviction times property는 그 eviction 시각까지 같다는 더 강한 조건이다.
- 이 포함 관계를 이용하면 eviction을 처음 유발하는 critical parameter만 계산한 뒤 나머지 setting으로 누적할 수 있다. Single-parameter policy는 trace 길이에 대해 linear time에 처리하며, two-parameter policy에는 별도 계산법이 필요하다.
- OPP에서 유도한 practical policies:
- AGE (age-based policy): 마지막 접근 후 일정 시간이 지나야 reclaim하는 기존 방식이다. 안전하지만 늦게 내보내므로 절감 기회를 놓친다.
- Prior Age with Wait (PAW, 과거 접근 간격을 이용하되 잠시 기다리는 정책): 직전 두 접근의 간격이 threshold보다 크고 마지막 접근 후 1분이 지나면 reclaim한다. 반복 pattern에는 유리하지만 과거가 미래를 잘 예측하지 못하면 AGE보다 나쁘다.
- Prior Age and Current Elapsed (PACE, 과거 접근 간격과 현재 idle 시간을 결합한 정책): 과거 접근 간격이 길면 즉시 reclaim하고, 그렇지 않으면 AGE처럼 일정 idle 시간을 기다린다. AGE로 되돌아갈 수 있지만 두 parameter를 workload에 맞게 정해야 한다.
- Learned OPP (L-OPP, 학습형 OPP): OPP의 결정을 정답으로 삼아 미래 정보 없이 reclaim 여부를 예측한다. Model precision이 낮으면 promotion-rate 제약을 지키지 못한다.
Result
MPC의 정확도와 생성 비용
저자들은 데이터 센터 benchmark suite인 CloudSuite와 DCPerf의 8개 workload에서 30초마다 page가 최근 사용됐는지를 나타내는 page-table access bit를 수집했다. Trace는 11–120분, application memory는 820 MB–160 GB 범위였다.
- Single-parameter policy 10개 setting과 PACE 15개 setting을 simulation과 대조했을 때 평균 절대 오차는 1% 이내였다.
- 가장 느린 OPP의 전체 MPC 생성도 0.4–583.2초로, 10개 parameter를 순차 simulation한 기준보다 12.5–208배 빨랐다.
Optimal headroom과 새 policy
- OPP는 모든 workload와 promotion rate에서 가장 높은 평균 메모리 절감량을 보였다. Cassandra에서는 promotion rate 1% 미만에서 약 40%를 절감한 반면, VMIN은 10%까지 허용해도 같은 절감량에 도달하지 못했다. 이는 window budget을 직접 고려하는 결정의 headroom을 보여준다.
- PAW는 access pattern이 예측 가능한 GraphX, NGINX, TaoBench에서 AGE보다 최대 10% 더 많은 메모리를 절감했지만, Memcached와 FeedSim처럼 과거 pattern이 약한 workload에서는 AGE가 크게 앞섰다.
- PACE의 best configuration은 대부분의 workload에서 AGE보다 1–4% 더 절감했고 Cassandra와 GraphX에서는 8–10% 개선했다. 단, 같은 trace로 parameter를 고르고 평가한 maximum-potential 결과이다.
- L-OPP는 DjangoBench와 MediaWiki에서 PAW보다 나았지만, TaoBench와 FeedSim에서는 낮은 예측 정밀도 때문에 promotion rate가 높아졌다. 학습 정책이 성능 제약을 자동으로 지키는 것은 아니다.
Linux end-to-end 검증
Linux 5.10에서 Solid-State Drive (SSD) swap과 30초 reclamation period를 사용해 GraphX PageRank를 실행한 결과다. AGE는 10분간 사용되지 않은 page를, PAW는 직전 두 접근 간격이 2.5분보다 큰 page를 reclaim했다.
| Policy | Swap (GB) | 평균 memory usage (GB) | 실행 시간 (분) |
|---|---|---|---|
| PAW | 0.59 ± 0.75 | 9.11 ± 0.84 | 16.9 |
| AGE | 0.23 ± 0.29 | 9.52 ± 0.27 | 17.1 |
PAW는 성능 저하 없이 AGE보다 약 4% 더 많은 메모리를 절감했다. 그러나 실제 promotion rate는 두 policy 모두 약 1.5%로, 오프라인 MPC에서 의도한 4%와 달랐다. 실행 시간이 원 trace와 달라 window 경계가 바뀐 것이 원인으로 분석된다.
Contribution
- 데이터 센터 reclamation을 모든 window의 성능 proxy 제약 아래 평균 메모리 절감량을 최대화하는 문제로 명시하여 전통적 page replacement와 구분했다.
- MRC에 대응하는 MPC와, promotion-rate budget을 지키는 offline upper bound인 OPP를 제안했다.
- Parameter 사이의 eviction 포함 관계를 정의하고 이를 이용한 linear-time MPC 생성 framework를 구현했다.
- MDK를 이용해 AGE의 headroom을 분석하고 PAW, PACE, L-OPP를 설계했으며, 8개 trace와 GraphX Linux 실행으로 toolkit의 설계 workflow를 사례 검증했다.
Criticisms
- Optimality의 범위: OPP가 optimal이라는 증명은 한 window 안의 접근을 같은 시각으로 보는 access-bit trace 모델에 성립한다. 정확한 접근 시각을 보존하면 OPP가 optimal이 아닌 반례가 있으며, 저자들은 대신 최적해와의 차이가 제한됨을 증명한다.
- 오프라인 정보와 tuning: OPP는 미래 접근이 필요하다. PACE도 평가 trace 자체에서 최적 parameter를 골랐으므로 overfitting 가능성이 있으며, unseen workload를 위한 online tuning은 검증하지 않았다.
- Proxy와 trace의 범위: Promotion rate는 hardware나 memory tier마다 다른 fault 비용을 반영하지 못한다. 또한 30초 access-bit scan은 한 period 안의 반복 접근을 세지 못하며, hugepage를 끈 단일 application trace만 사용했다.
- 제한된 end-to-end 검증: 실제 Linux 검증은 GraphX에서 PAW와 AGE만 비교했다. PACE와 L-OPP는 배포하지 않았고, 목표 promotion rate 4%와 실제 약 1.5%도 어긋났다.
Conclusion
이 연구는 데이터 센터 memory reclamation을 window별 SLO budget을 지키며 reclaim 가능한 메모리를 최대화하는 문제로 재정의한다. MDK는 optimal upper bound를 측정하고 그 통찰을 practical policy로 옮기는 공통 workflow를 제공한다. 다만 실제 활용에는 unseen workload의 online tuning과 더 다양한 성능 proxy 및 배포 환경 검증이 필요하다.