Traditional virtual-memory research begins with a fixed capacity. When the cache fills, a replacement policy chooses which page to evict, and success is fewer misses or lower access cost. Belady’s offline OPT and miss-ratio curves provide a bound and compare policies across cache sizes.
Datacenter reclamation flips the variables. A server has memory, but the cluster wants to take some from running jobs so another job can be placed. A policy proactively evicts or demotes pages before pressure. The objective is maximum average saved capacity; the constraint is that a performance proxy such as promotion rate or pressure stall time remains below an SLO in each measurement window.
The classical tools no longer answer that question. A policy can produce the same lifetime miss count while concentrating misses into one window that violates the SLO. A fixed cache size cannot express memory changing over time. MDK, the Memory Designer’s Kit, rebuilds the offline bound, curve, and evaluator around proactive variable capacity.
A performance window changes the offline optimum
MDK defines memory saving as bytes reclaimed multiplied by the duration they remain absent. A page evicted immediately after access and not touched for ten minutes contributes more than one evicted shortly before its next access. Promotion rate counts faulting pages relative to unique accessed pages within each time window, reflecting the cost of bringing reclaimed data back.
The offline optimal proactive policy knows future accesses and selects eviction times that maximize total byte-time saved without exceeding the fault budget in any window. It is not Belady OPT. Belady preserves pages to minimize misses given a capacity; MDK’s optimum spends an allowed number of future promotions to free the most capacity for the longest time.
This optimum bounds what any policy can obtain for a trace and SLO definition. The gap between an online policy and the bound shows opportunity but does not make the bound deployable, since it uses future knowledge. A narrow gap can prevent time spent tuning a heuristic whose workload offers little additional reclaimable memory.
Memory Performance Curves replace fixed-size miss curves
A Memory Performance Curve (MPC) maps a policy’s possible parameter settings into average memory saved versus a performance proxy. One point might show memory released at a 1% promotion rate; another permits 2%. A policy dominates another where it saves more memory at the same performance bound.
Unlike a miss-ratio curve, an MPC can use different saving metrics and proxies, provided the policy evaluator defines them. Promotion rate fits compressed-memory or tiering systems. PSI or latency can represent other contracts, though the analytical algorithms require structure and may need simulation for arbitrary metrics.
The curve makes parameter comparison SLO-relative. An age threshold of ten minutes is not intrinsically conservative or aggressive; its promotion outcome depends on workload reuse. Designers can choose a target point and see whether a two-parameter or learned policy improves the frontier rather than reporting one hand-selected setting.
MDK identifies monotonic properties that permit analytical generation. If more aggressive parameter settings include all evictions of less aggressive settings, critical thresholds can be computed per page and outcomes accumulated rather than resimulating every point. A related eviction-time property lets memory savings be reused across settings.
Analytical generation changes the policy-development loop
The evaluation covered Cassandra/YCSB, Memcached with Twitter KV, GraphX PageRank, NGINX media streaming, TaoBench, DjangoBench, FeedSim, and MediaWiki. Traces ranged from 820MB to 160GB and from 11 to 120 minutes.
Generating curves analytically was 12.5 times faster than simulation for NGINX and 208 times faster for FeedSim. Cassandra improved 110 times, TaoBench 82 times, and Memcached 55 times. MPC values differed from simulation by less than 1%, attributed to implementation and discretization rather than a changed metric.
Faster evaluation matters because parameter spaces can contain more than 10,000 pairs. A developer can inspect full frontiers, run sensitivity studies, and reject weak ideas before a kernel implementation. It also reduces the temptation to compare policies at mismatched promotion rates.
The method is offline and trace-dependent. Trace capture itself can perturb workloads or miss unobserved accesses. Analytical speed does not eliminate sampling bias, future-workload drift, or the need for online validation. A curve should include confidence bounds when the trace represents only part of a fleet.
New policies emerge from the curve, not one intuition
MDK evaluates fixed-memory LRU and OPT and several variable-memory policies, including VMIN, AGE, PAW, PACE, an offline proactive optimum, and a learned policy. AGE reclaims a page after a fixed idle period. It is simple but applies one time threshold to pages with different reuse histories.
PAW uses the previous reuse distance as a prediction for the next interval. It can reclaim first-use or long-gap pages earlier, but one prior distance is noisy. PACE combines prior reuse distance with current age. It reclaims when the previous gap exceeds a threshold or the current idle time passes an age threshold, creating a two-dimensional frontier.
Across most promotion-rate ranges, PACE saved 1% to 4% more memory than AGE. GraphX and NGINX contained reuse behavior where selected configurations improved 8% to 10%. The gain is maximum average byte-time, not necessarily a 10% reduction in peak RSS or a 10% increase in job packing; those depend on simultaneous job shapes and scheduler constraints.
A learned policy used six past reuse distances to predict reclaim decisions. MDK’s optimum supplied labels, connecting future-aware analysis to an online classifier. The framework exposes whether learning approaches the offline frontier and which windows produce excess promotions instead of reporting model accuracy disconnected from capacity.
Linux validation reveals proxy and model mismatch
The authors implemented AGE and PAW in Linux with 30-second reclamation periods. One comparison configured an expected 4% promotion threshold. PAW saved 4% more memory than AGE as predicted by the curve, but both achieved an observed promotion rate around 1.5%, well below the expected value.
The mismatch can come from access-bit observation, sampling granularity, timing, page coalescing, or simulator assumptions. It illustrates why an offline MPC is a design tool rather than a deployment guarantee. The same policy code must be validated with online memory, swap, promotion, and application SLO metrics.
Promotion rate is also a proxy. One promoted page may stall a latency-critical request while many prefetchable promotions are harmless. Two applications with equal rates can experience different p99 latency. A production controller needs a calibrated relationship between the proxy and the actual service objective.
Variable page sizes complicate byte savings and faults. A 2MB huge-page promotion counts one event but transfers far more than a 4KB page. Compression ratio and slow-tier latency vary by content. MDK can accept alternative definitions, but policy comparisons must use a metric that prices these differences.
A fleet needs curves by workload class and phase
An MPC built from one trace should not become a universal threshold. Daily cycles, releases, cache warmup, failover, and tenant mix change reuse. Curves should be generated per workload class and important phase, then compared for robust parameter regions rather than one optimal point.
Telemetry should preserve time-window distributions. Average memory saving can hide a period with no reclaimable capacity, and average promotion can hide an SLO-violating burst. Report p50, p95, and worst-window savings and proxy values, plus application latency and job-placement success.
The offline bound can inform capacity planning. If every deployable policy sits close to optimum yet saves little, the workload needs allocation-layout changes, application hints, compression, or more DRAM rather than another eviction heuristic. If the gap is large, MDK can identify traces and parameter regions where policy research will repay effort.
Policy safety also needs hysteresis and rollback. A controller selecting a more aggressive curve point must monitor the live proxy and restore pages or raise the threshold before the application violates its SLO. Cold starts and workload changes should begin from a conservative state until enough reuse history is collected.
Reclamation quality is capacity under a constraint
MDK’s central correction is conceptual. The datacenter is not optimizing a cache inside a box; it is resizing the box around a running service so the cluster can place more work. The quantity to maximize is memory freed over time, and the constraint belongs to every SLO window.
The 12.5-to-208-times evaluation speedup makes full policy frontiers practical. The up-to-10% saving improvement shows that a second signal such as prior reuse can matter, while Linux mismatch shows that offline predictions must be calibrated. The offline optimum is valuable precisely because it separates trace potential, policy quality, and implementation behavior.
Operators evaluating tiered memory should request MPCs or an equivalent saving-versus-SLO frontier rather than one memory-reduction number. A point without its promotion, stall, or latency constraint cannot be compared. MDK provides a common language for that comparison and a way to decide whether a new reclaimer improves the frontier or merely chooses a different risk level.
Source and copyright notice
This article is an editorial analysis by Silicon & Systems. It restates the framework, experiments, and limitations in our own words. No source sentence, table, or figure is reproduced; the figure was created for this article. The paper is available from the USENIX OSDI 2026 presentation page. Copyright remains with the authors, 2026.