| 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을 고정 크기 메모리에서 miss를 최소화하는 전통적 Page replacement와 다른 최적화 문제로 재정의하고, 성능 SLO를 지키면서 평균 메모리 절감량을 최대화하는 정책을 설계·평가하기 위한 offline toolkit인 Memory Designer's Kit (MDK)를 제안한다.
Background
| 구분 | 전통적 page replacement | 데이터 센터 memory reclamation |
|---|---|---|
| 목표와 제약 | 고정된 cache 크기에서 전체 실행의 miss ratio 최소화 | 모든 측정 window의 성능 proxy 한도를 지키면서 평균 메모리 절감량 최대화 |
| 동작 시점 | 메모리 pressure가 발생한 뒤 reactive eviction | 새 job을 배치할 여유를 만들기 위한 proactive reclamation |
| 대표 지표 | 전체 실행에 걸친 cache miss ratio | window별 promotion rate, PSI, Secondary Tier Access Ratio (STAR) |
| 설계 도구 | OPT와 MRC | OPP와 MPC |
이 논문이 주로 사용하는 promotion rate는 한 time window에서 발생한 non-compulsory page fault 수를 그 window에서 접근한 unique page 수로 정규화한 값이다. g-swap은 이 값을 2분마다 측정하며, 논문의 Cassandra/YCSB 실험에서는 promotion rate가 window별 tail latency와 함께 증가했다. 따라서 저자들은 이를 trace에서 계산할 수 있는 SLO-aligned proxy로 선택한다. 최적화 목표는 시간에 따른 평균 메모리 절감량이다.
Motivation
DRAM 비용 때문에 서버당 더 많은 job을 수용하는 것은 데이터 센터의 total cost of ownership과 직결된다. 이를 위해 g-swap이나 TMO 같은 시스템은 cold page를 compressed memory, SSD, 또는 CXL 기반의 저렴한 tier로 미리 내보낸다. 이때 절감된 메모리는 cluster scheduler가 새 job을 배치할 만큼 오래 유지되어야 하고, reclamation 때문에 application SLO가 깨져서도 안 된다.
하지만 기존 도구는 이 목적에 맞지 않는다. OPT와 VMIN은 전체 miss 수를 최소화할 수 있어도, 여러 page의 재접근과 fault를 같은 window에 몰아 promotion-rate 한도를 위반할 수 있다. MRC 역시 고정 cache 크기와 miss ratio의 관계를 나타내므로, 시간이 지나며 크기가 변하고 다양한 성능 proxy를 사용하는 reclamation policy를 비교하기 어렵다. 즉, 문제의 목표와 제약이 뒤집혔는데도 policy 설계 workflow에는 이에 대응하는 optimal bound, 비교 곡선, 빠른 탐색법이 없었다.
Importance
이 논문의 연구적 가치는 새로운 reclamation heuristic 하나보다 정책 설계 문제의 좌표계를 바꾼 것에 있다. 전통적 caching 연구가 “주어진 용량에서 miss를 얼마나 줄일 수 있는가”를 물었다면, MDK는 “각 window의 성능 budget 안에서 메모리를 얼마나 더 내놓을 수 있는가”를 묻는다. 이에 맞춰 optimal oracle, policy curve, 이론적 nesting property, curve 생성기를 한 workflow로 제공한다.
또한 optimal policy를 실제 배포 대상으로 제시하는 데 그치지 않고, 기존 AGE policy의 headroom을 정량화하고 그 oracle의 결정을 PAW, PACE, L-OPP로 근사하는 과정을 보인다. 따라서 MDK는 characterization, upper-bound 분석, heuristic 설계, parameter 탐색을 연결하는 memory-policy design methodology로 기억할 가치가 있다.
Main Idea
핵심 통찰은 reclamation policy가 miss의 총량만 보지 말고, 미래의 각 time window가 허용하는 promotion budget을 first-class constraint로 취급해야 한다는 것이다. 같은 수의 page fault라도 한 window에 집중되면 SLO proxy를 위반할 수 있다. 반대로 미래 fault를 여러 window의 budget에 분산하면서 page를 가능한 한 일찍 reclaim하면, 제약을 지키면서 page가 DRAM 밖에 머무는 시간을 최대화할 수 있다.
MDK는 이 통찰을 네 도구로 구체화한다. MPC는 promotion rate와 평균 메모리 절감량의 tradeoff를 보여주고, OPP는 달성 가능한 최적 upper bound를 제공한다. Eviction decisions와 eviction times property는 여러 parameter setting의 결과가 어떻게 포함되는지를 나타내며, efficient MPC generator는 이 구조를 이용해 모든 setting을 각각 simulation하지 않고 trace를 linear time에 처리한다.
Design
- Memory Performance Curve (MPC)
- Local problem: MRC의 cache size–miss ratio 축은 가변 크기 reclamation과 window별 성능 제약을 표현하지 못한다.
- Mechanism: x축에 target performance proxy(논문에서는 promotion rate), y축에 memory optimization goal(평균 메모리 절감량)을 둔다. 가능한 operating point가 연속적이라고 보장할 수 없으므로 선으로 잇지 않고 scatter plot으로 나타낸다.
- 효과와 tradeoff: 동일한 성능 budget에서 policy를 비교하고, 원하는 절감량에 필요한 성능 degradation을 찾을 수 있다. 다만 curve의 의미는 선택한 proxy와 workload trace에 종속된다.
- Optimal Performance Proxy (OPP)
- Local problem: OPT와 VMIN은 미래 fault의 window별 집중을 고려하지 않는다.
- Mechanism: 첫 pass에서 각 window의 unique accessed-page 수를 계산한다. 두 번째 pass에서는 page의 다음 접근 window를 미리 알고, 그 page가 만들 promotion을 추가해도 해당 window의 target rate를 넘지 않을 때 현재 접근 직후 즉시 reclaim한다. 각 미래 window별 예정 promotion 수를 갱신해 budget을 예약한다.
- 효과와 invariant: 허용된 fault slot을 지키면서 page를 가장 이른 시점에 내보내므로 평균 절감량을 최대화한다. Access-bit scan처럼 한 window 안의 접근 시각을 동일하게 취급한 trace에서는 first-difference argument로 optimal임을 보인다. 미래 접근을 요구하므로 OPP 자체는 offline oracle이다.
- Eviction decisions / eviction times properties
- Local problem: parameter마다 policy를 독립 simulation하면 탐색 비용이 크다.
- Mechanism: 더 aggressive한 setting이 덜 aggressive한 setting의 모든 eviction decision을 포함하면 eviction decisions property를 만족한다. 그 eviction들이 같은 시각에도 발생하면 더 강한 eviction times property를 만족한다. 각 접근에는 eviction을 처음 유발하는 least-aggressive critical parameter를 배정한다.
- 효과와 tradeoff: critical setting의 promotion과 saving만 계산한 뒤 더 aggressive한 setting으로 누적할 수 있다. VMIN과 OPP는 두 property를 모두 만족하지만, AGE는 eviction decision만 포함하고 더 aggressive할수록 더 일찍 reclaim하므로 시간 property는 만족하지 않는다.
- Efficient MPC generator
- Local problem: trace마다 수많은 parameter를 simulation하는 방식은 정책 탐색을 느리게 만든다.
- Mechanism: policy가 제공하는 parameter space, aggression order, critical parameter, per-access saving, saving accumulation 함수를 공통 template에 끼운다. Promotion과 saving을 critical parameter에 기록하고 aggression order를 따라 누적하여 전체 MPC를 만든다.
- 효과와 tradeoff: single-parameter policy의 생성은 trace 길이에 대해 linear time이며, 구현된 policy-specific code는 87 LOC 이하였다. 기본 template은 eviction decisions property를 만족하는 single-parameter policy를 대상으로 하며, two-parameter PACE에는 suffix-sum dynamic programming 기반의 약 300 LOC 전용 generator가 필요하다.
- OPP에서 유도한 practical policies
- PAW (Prior Age with Wait): 직전 두 접근 사이의 reuse distance가 threshold P보다 크고 마지막 접근 후 1분이 지나면 reclaim한다. OPP처럼 접근에 가까운 시점에 내보내되 hot page의 즉시 재회수를 막는다. 반복 access pattern에는 유리하지만 과거 reuse distance가 미래를 예측하지 못하면 AGE보다 나쁘다.
- PACE (Prior Age and Current Elapsed): prior reuse distance가 P보다 크면 즉시 reclaim하고, 그렇지 않으면 마지막 접근 뒤 A interval 동안 idle일 때 AGE처럼 reclaim한다. P를 무한대로 두면 AGE로 퇴화하므로 offline 최적 parameter에서는 AGE보다 나쁘지 않지만, 두 parameter를 unseen workload에서 정하는 문제가 남는다.
- L-OPP (Learned OPP): OPP의 2% target 결정을 label로 삼고 page별 최근 reuse distance 6개를 feature로 하는 gradient-boosted tree를 workload별로 학습한다. 미래 정보 없이 oracle을 모방할 가능성을 보이지만, model precision이 낮으면 promotion constraint를 지키지 못한다.
Result
MPC의 정확도와 생성 비용
저자들은 CloudSuite와 DCPerf의 8개 workload(Cassandra, Memcached, GraphX, NGINX, TaoBench, DjangoBench, FeedSim, MediaWiki)에서 30초 주기로 page-table access bit를 scan했다. Trace는 11–120분, application memory는 820 MB–160 GB 범위였다.
- Single-parameter policy의 10개 setting과 PACE의 15개 setting을 simulation과 대조했을 때 모든 MPC의 mean absolute error는 rounding 차이로 인해 1% 이내였다.
- 가장 느린 OPP에서도 모든 parameter의 MPC 생성은 0.4–583.2초가 걸렸고, 10개 parameter를 순차 simulation한 기준보다 12.5–208배 빨랐다. 저자들은 이를 linear-time generator와 quadratic-time simulation의 차이로 설명한다.
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 두 DCPerf workload에서 PAW보다 나았고 DjangoBench에서는 AGE보다 소폭 나았다. 반면 TaoBench와 FeedSim에서는 낮은 offline precision 때문에 높은 promotion rate가 발생해, 학습 기반 정책에서 constraint 준수가 자동으로 보장되지 않음을 보였다.
Linux end-to-end 검증
Linux 5.10에서 SSD swap과 30초 reclamation period를 사용해 GraphX PageRank를 실행한 결과는 다음과 같다. AGE는 10분간 사용되지 않은 page를, PAW는 prior reuse distance가 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% 더 많은 메모리를 절감하여 offline MPC의 방향성은 재현했다. 그러나 실제 promotion rate는 두 policy 모두 약 1.5%로, offline MPC에서 의도한 4%보다 낮았다. 실행 시간이 원 trace와 달라 page access와 reclamation이 속한 window가 바뀐 것이 원인으로 분석된다.
Contribution
- 데이터 센터 reclamation을 모든 window의 성능 proxy 제약 아래 평균 메모리 절감량을 최대화하는 문제로 명시하여 전통적 page replacement와 구분했다.
- MRC에 대응하는 MPC와, promotion-rate budget을 지키는 offline upper bound인 OPP를 제안했다.
- Parameter aggressiveness 사이의 eviction decisions 및 eviction times property를 정의하고 이를 이용한 linear-time MPC 생성 framework를 구현했다.
- MDK를 이용해 AGE의 headroom을 분석하고 PAW, PACE, L-OPP를 설계했으며, 8개 trace와 GraphX Linux 실행으로 toolkit의 설계 workflow를 사례 검증했다.
Criticisms
- Optimality의 적용 범위: OPP의 optimality proof는 access-bit scan trace처럼 한 window 안의 모든 접근이 같은 시각에 발생했다고 보는 모델에 성립한다. Appendix D는 exact timestamp를 보존하면 greedy OPP가 optimal이 아닌 반례를 제시하며, 대신 최적해와의 총 saving gap이 전체 fault budget × window size보다 작음을 보인다. 따라서 “provably optimal”이라는 요약은 trace 시간 모델을 함께 밝혀야 한다.
- Offline oracle와 parameter selection: OPP는 미래 접근을 알고 있어야 한다. PACE 결과도 evaluation trace 자체에서 최적 (P, A)를 골라 얻은 upper bound라 overfitting 가능성이 있으며, unseen trace를 위한 train/test tuning이나 online tuner는 future work다.
- Proxy의 일반성: Promotion rate는 fault cost가 비교적 균일할 때 유용하지만 memory tier와 hardware별 fault latency 차이를 반영하지 못한다. PSI 같은 runtime-dependent metric을 offline MDK에 넣으려면 별도 analytical model이 필요하므로, 다른 metric으로의 일반화는 interface 수준의 주장에 더 가깝다.
- Trace와 workload 범위: 30초 access-bit scan은 한 period 안의 반복 접근을 세지 못하고, 실험은 hugepage를 끈 per-application trace를 사용한다. Frequency-sensitive policy, hugepage 환경, colocated workload 간 간섭에 대한 결론은 직접 검증되지 않았다.
- 제한된 end-to-end 증거: Kernel 검증은 PAW와 AGE를 비교한 GraphX 한 workload에 한정되고, PACE와 L-OPP는 배포하지 않았다. 또한 offline target 4%와 실제 약 1.5% promotion rate가 어긋나므로, MPC 기반 parameter가 online SLO를 얼마나 정확히 제어하는지는 아직 입증되지 않았다.
- 비교 비용의 해석: 12.5–208배 speedup의 simulation baseline은 10개 parameter를 순차 실행한 값이다. 병렬 simulation도 asymptotic cost는 남지만 wall-clock 격차는 줄일 수 있으므로, 수치는 해당 비교 설정과 함께 해석해야 한다.
Conclusion
이 연구는 데이터 센터 memory reclamation을 고정 용량에서 miss를 줄이는 문제가 아니라, window별 SLO proxy budget을 지키며 reclaim 가능한 메모리를 최대화하는 문제로 바라보게 만든다. MDK의 MPC, OPP, nesting properties, efficient generator는 policy의 headroom을 측정하고 oracle의 통찰을 practical heuristic으로 옮기는 공통 workflow를 제공한다. 8개 workload의 offline 결과와 제한적인 Linux 검증은 기존 AGE보다 개선할 여지를 보여주지만, 실제 활용을 위해서는 unseen workload의 online tuning과 더 다양한 performance proxy 및 배포 환경에 대한 검증이 필요하다.