HybridTier: an Adaptive and Lightweight CXL-Memory Tiering System

Kevin Song, Jiacheng Yang, Zixuan Wang, Jishen Zhao, Sihang Liu and Gennady Pekhimenko

Cheap expansion memory attached over CXL is slower than local DRAM, so a tiering system must keep hot pages local — but the standard way of scoring hotness is one decaying counter per page, and one number cannot both capture a long-term distribution and react quickly to change; HybridTier (Toronto, UCSD, Waterloo) keeps two counters per page decaying at different rates, and shrinks the bookkeeping from gigabytes to megabytes by storing the counts in a counting bloom filter, on the argument that being off by one about a very hot page changes nothing.

The argument in one glance

Problem

Servers need more memory than DRAM can affordably supply

Memory is already 37 percent of the cost of a datacentre rack by one operator report, density growth has slowed, and a chassis only holds so many modules. Expansion memory over the CXL interconnect is cheaper and denser, but adds 50 to 100 nanoseconds of latency and delivers a fraction of local bandwidth.
What people did

Count accesses per page and keep the hottest ones local

A tiering system samples memory accesses, keeps a counter per page, builds a histogram, and computes the threshold that fills the fast tier with exactly the hottest pages. Counters are kept fresh by halving all of them every so often.
Why it fell short

The freshness knob trades away the accuracy it depends on

An average containing history lags: a page that goes cold keeps a high score for minutes. Halving more often fixes the lag and ruins the histogram, because pages no longer accumulate enough accesses to be ranked. Meanwhile the per-page counters reach gigabytes and their updates take a measurable share of the whole system cache misses.
This paper's idea

Keep two counters that decay at different rates, and store them approximately

One number cannot answer both questions, so keep two — a slow one for the long-run distribution and a fast one for recent intensity — and let the migration policy read both. Then note that exact counts are unnecessary, and replace the per-page table with a fixed-size probabilistic filter sized to the fast tier rather than to all of memory.

Why this problem is worth solving

The new memory is real, cheap, and slower.

Compute Express Link is an industry-standard interconnect running over the physical layer of PCIe. Memory attached through it is byte-addressable and directly usable by the processor through ordinary allocation interfaces, which is what separates it from a storage tier — no rewriting, no explicit transfers. What it costs is distance: roughly 50 to 100 nanoseconds of additional latency and between a fifth and seven tenths of local bandwidth per channel. That makes a server into two tiers of memory rather than one, and turns performance into a placement question: keep the hot pages in local DRAM, push the cold ones out, and move pages between the two as the workload changes. The prize is capacity per dollar; the difficulty is that nothing tells the system which pages are hot.

The standard way of measuring heat has a built-in conflict.

Counting accesses per page works until the counts grow stale, so tiering systems periodically cool them by dividing every counter by two — cheap, since it is a bit shift — which makes each score an exponentially weighted average of the recent past. The cooling period is a tuning knob, and it points in two directions at once. Cool rarely and the scores carry a lot of history, which ranks pages against each other well but means a page that stops being accessed keeps a high score long after it has gone cold. Cool often and scores track the present, but no page accumulates enough counts for the ranking to be meaningful. In one measurement here, a page last accessed at the ten-minute mark is still not classified as cold until minute nineteen.

What people did before, and where it broke

Rank pages by a decaying access count. The strongest prior approach: sample accesses in hardware, keep a counter per page, build a histogram, and derive the exact hotness threshold that fills the fast tier. Where it broke. The cooling that keeps counters fresh makes them lagging indicators, so adapting to a shifted distribution took roughly 1400 seconds in one experiment against an ideal of about 400.
Cool more often to react faster. The obvious remedy, and the knob prior work already exposes. Where it broke. Shortening the period degrades the histogram itself, because hot and warm pages no longer accumulate enough accesses to be distinguished, so the system reacts quickly to a distribution it now measures badly.
Use recency instead of frequency. Systems that promote on how recently a page faulted avoid the staleness problem entirely, since a recency signal is fresh by construction, and they need far less state. Where it broke. A single recent access to a cold page looks identical to a genuinely hot one. The consequence is worse than inaccuracy: the misclassified pages occupy fast-tier space, so real hot pages cannot be promoted, and the system that should adapt fastest instead adapts slowest.
Borrow a hybrid caching algorithm. Classical policies that maintain separate structures for items seen once and items seen repeatedly are designed for exactly this recency-versus-frequency tension. Where it broke. They record that an item was seen more than once without recording how often, which cannot distinguish hot from warm — and warm-versus-hot is the whole question when the fast tier is small.
Blend recency and frequency into one weighted score. A well-known family of policies does this, with a decay factor sliding between the two extremes. Where it broke. Collapsing both into a single number means the decay factor buys accuracy in one at the cost of the other. The spectrum is the problem, not the position on it.
The gap. Every design carries one number per page and then argues about how fast it should decay. And all of them pay per-page metadata proportional to total memory — 16 bytes for each 4-kilobyte page in one system, which on a one-terabyte server is 3.9 gigabytes, against roughly 400 megabytes for the entire Linux kernel at boot.

How two counters replace one lagging average

From one decaying score to two counters and a probabilistic table

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

The trade-off everyone was tuning was an artefact of using one number. For years the argument in this area has been about where to sit on a spectrum: cool the counters rarely and you rank pages well but react slowly, cool them often and you react quickly but rank badly, and the blended recency-frequency policies parameterise exactly the same dilemma with a decay factor. What makes the dilemma real is that a single score is being asked two different questions — which pages deserve the scarce fast tier, and which pages just changed — and those questions have different natural timescales. Keeping two counters with different cooling periods dissolves it, at the cost of one extra small counter per page. The finding that makes this more than tidy engineering is the one about why recency-based systems adapt slowly despite being fresh by construction: they promote cold pages that happen to have been touched, those pages then occupy the fast tier, and genuinely hot pages have nowhere to go. Accuracy turns out to be a prerequisite for adaptiveness, not an alternative to it. A mechanism that looks helpful while quietly consuming the resource that is actually scarce is the same trap the fleet prefetching work covered elsewhere on this site describes, where prefetchers tuned on benchmarks with free bandwidth are deployed where bandwidth is the scarcest thing on the machine.

Exactness was never the requirement, and dropping it changes what the metadata costs. A hash table of access counts guarantees that a lookup returns what was last written, and pays for that guarantee with memory proportional to the number of pages inserted — billions of them on a large server. But the guarantee is not what tiering needs. If a very hot page counter reads one or two low, the page is still above the threshold and the decision is unchanged; the count only matters where it sits near the boundary, and the measurements here show a filter agreeing with an exact table on more than 99.6 percent of migration decisions. A counting bloom filter replaces per-page allocation with a fixed-size shared array in which pages collide and corrupt each other, and two consequences follow that matter more than the raw compression. The array is sized by the fast tier rather than by total memory, so it grows with the resource being managed rather than with the resource being expanded. And the counters are four bits, capped at fifteen, because pages at the cap all belong in fast memory and need not be distinguished. Trading a bounded, tunable inaccuracy for a table that fits in the memory you can spare is the same bargain the learned flash translation work covered elsewhere on this site makes when it approximates an address mapping to reclaim the scarce DRAM inside an SSD.

The bookkeeping was competing with the workload for cache, not just for memory. This is the observation the paper says prior work overlooked, and it is the one with the most immediate consequence. Every sampled access triggers a lookup in a structure far larger than the last-level cache — a multi-level page table walk in one system, a chain of pointer dereferences in another — and the tiering thread therefore generates cache misses that evict the application own data. Measured on a cache-sensitive workload, the tiering activity of the strongest baseline accounts for 9 percent of level-one misses and 18 percent of last-level misses with regular pages. The filter helps twice over: at four bits it fits the counts for at least 32 pages in a cache line where the baseline fits four, and it is a single-level structure that deliberately tolerates collisions instead of chasing pointers to resolve them. Then the blocked variant confines all of a page counters to one line, which turns out to matter more than the compression — the plain filter cuts misses by 12 to 36 percent and the blocked one by a further 31 to 72. Discovering that the apparatus for observing a program has become a significant part of what the program is competing against is the same reckoning the value profiling work covered elsewhere on this site reports when its instrumentation costs run into the hundreds of times.

Following one page as it turns hot and then cold

What happens to a single 4-kilobyte page over several minutes

The runtime is a userspace thread linked into the application at load time. Nothing here requires recompiling the workload or changing the kernel.

Step 1 of 5

A sampled access arrives and updates both filters

The processor sampling hardware delivers a stream of accessed virtual addresses. For each one, the runtime hashes the page into the frequency filter and the momentum filter and increments the smallest counters it finds in each.

Four hash functions per filter, all landing in one cache line. The momentum filter is allocated 128 times less memory than the frequency filter, because its rapid cooling keeps most of its counts at zero.

Why it works

Two questions with different timescales need two answers. Which pages deserve the fast tier is a question about accumulated history, while which pages just changed is a question about the last few seconds → and a single decaying score must pick one cooling period and therefore serve one of them badly → so two counters with different periods remove a trade-off that prior work could only slide along.
Being wrong about which pages are hot is itself a failure to adapt. A recency signal is fresh by construction and ought to react instantly → but promoting cold pages that were merely touched fills the fast tier with them, leaving no room for pages that genuinely turned hot → which is why the system with the freshest signal measures as the slowest to adapt, and why accuracy has to come first.
A count only matters near the threshold. Exact structures pay memory per page to guarantee a lookup returns what was written → but a hot page misread by one or two is still ranked hot and produces the same decision, with disagreement confined to pages sitting on the boundary → so a probabilistic filter with collisions matches an exact table on more than 99.6 percent of migrations.
Metadata should scale with the tier being managed, not the memory being expanded. A per-page table grows with total capacity, which is precisely the quantity that cheap expansion memory is meant to increase → whereas a filter only has to distinguish pages that could plausibly be promoted, so it is sized by the fast tier → giving 7.8 times less metadata at a small fast tier, though only 2.0 times at a large one.
Where the counters sit decides the cache cost, not how many there are. Every sampled access means a lookup, and a structure larger than the last-level cache turns each into evictions of application data → so packing counts eight times more densely per line and confining a page counters to a single line attacks the misses directly → cutting tiering-induced misses by 1.7 to 3.5 times and the tiering share of total misses from 9 and 18 percent down to about 5.

What it costs (trade-offs and scope)

The headline idea is inert on half the workloads. The momentum tracker improves the two cache and gradient-boosting workloads by 8.5 percent and does essentially nothing for the three graph workloads, because their hot sets already fit in the fast tier — 94 percent of pages in one graph are never accessed at all, leaving 20 gigabytes of warm data for a 64-gigabyte fast tier. The contribution matters exactly when the fast tier is genuinely contended.
The margin over the strongest baseline is modest. Against the recency-based kernel mechanism, the geometric mean improvement is 11 percent. The larger figures — 29 percent, 40 percent, 50 percent — are against a frequency-based system and against two classical caching policies that the authors implemented themselves as tiering systems, with a known handicap: both promote on first sight, which the paper identifies as too aggressive.
CXL is emulated by a remote socket. As in the prior work it compares against, the slow tier is a remote NUMA node, tuned to 124 nanoseconds idle latency and 34 gigabytes per second to resemble a measured device. No real CXL hardware is involved.
The metadata advantage shrinks as the fast tier grows, from 7.8 times at a one-to-sixteen ratio to 2.0 times at one-to-four, because the filter scales with fast-tier size while the baseline scales with total memory. Extrapolated toward balanced tiers, the advantage would largely disappear.
The four-bit cap already has an exception in the evaluated set. The justification is that under three percent of pages reach a count of fifteen — except on the social-graph workload, where 25 gigabytes of pages do. The remedy offered is widening the counters, which gives back the memory and cache savings.
Several parameters are set empirically and one workload is sensitive to them. The momentum threshold is fixed at three by measurement, with performance degrading below it; the second-chance revisit interval is a minute; the filter parameters were chosen because they worked across the evaluated set. Users are told they may tune them.
The stated remedy for scanning workloads costs the property the system exists for. Applications that touch each page once are handled by raising the momentum threshold, which the paper acknowledges reduces adaptiveness — the exact capability the two-counter design was built to provide.
The cost illustration is rhetoric, not measurement. The claim that the metadata saved is worth 31.8 million dollars a year comes from pricing it as small cloud instances across a hypothetical hundred thousand servers.
Scope is one process. It is a per-application userspace runtime; multi-tenant and co-located tiering is sketched as a central coordinator over per-process instances and not built.
Demotion scans the address space linearly through the proc filesystem to find cold pages, and that cost is not separately quantified even though the paper is otherwise careful about tiering overheads.
The blocked filter trades a higher collision rate for its locality, accepted on the evidence that the performance is better.
The ceiling is close and known. Against a configuration using only fast memory, the system is 14, 9 and 6 percent slower at the three tier ratios, which bounds how much any better policy could win.

The evaluation

Three ways to decide which pages deserve the fast tier

Property	One decaying frequency counter	A recency signal	Two counters plus a probabilistic table
How well the hot set is identified
How fast it follows a shifted distribution
Metadata memory
Share of system cache misses caused by tiering		Not the reported bottleneck
Overall performance

Six large-memory workloads from 150 to 335 gigabytes — an in-memory cache, three graph analytics kernels, two scientific benchmarks, a database and gradient boosting — on a two-socket server with the slow tier fixed at 512 gigabytes and fast-to-slow ratios of one to sixteen, eight and four.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The most important number is not in the abstract: the momentum tracker, which is the paper central idea, improves two of the six workloads by 8.5 percent and does essentially nothing for the three graph benchmarks, because their hot sets already fit in the fast tier. It earns its place exactly when fast memory is contended, which is a real and common condition but not a universal one. The margin against the strongest baseline is likewise modest — 11 percent on geometric mean against the recency-based kernel mechanism, with the larger 40 and 50 percent figures measured against classical caching policies the authors implemented themselves and identified as too aggressive at promotion. No real CXL hardware appears anywhere; the slow tier is a remote socket tuned to resemble a measured device, which is standard practice in this area and still an emulation. The metadata advantage is a function of the tier ratio, falling from 7.8 times to 2.0 as the fast tier grows, and would keep falling. The four-bit counter cap is justified by pages rarely reaching fifteen, with one evaluated workload already excepted at 25 gigabytes. Several parameters — the momentum threshold, the second-chance interval, the filter sizing — are empirical, with users invited to tune them, and the offered handling for scan-like access patterns is to raise the threshold, which trades away the adaptiveness the design exists to provide. The cost figure of 31.8 million dollars a year is a pricing exercise over hypothetical servers rather than a measurement. And the scope is a single process, with multi-tenant operation sketched rather than built.

Background

Why memory tiering became urgent

The pressure here is economic before it is technical. Memory is reported at 37 percent of the cost of a rack, DRAM density growth has slowed since the last decade, and a server chassis physically holds a limited number of modules — so the only ways to give an application more memory are to buy an expensive amount of it, or to attach something cheaper and slower and manage the difference. CXL makes the second option viable in a way that earlier attempts did not, because the expansion memory is byte-addressable and usable through ordinary allocation, so the application needs no changes at all. That relocates the entire problem onto the question of which pages are hot, which is old and unsolved, and gives it a new shape: the decision must be made continuously, cheaply, and without the application knowing. The identification-and-migration cost is what most work in this area attacks — the CXL page migration work covered elsewhere on this site observes that doing it by scanning page tables or catching faults burns processor time on both counts. What this paper adds to that framing is the observation that the tiering machinery competes with the workload not only for cycles and memory but for cache, which is easy to miss because it appears as the application running slower rather than as any line item in the tiering system own accounting.

If you remember only three things

1. Tiering systems score each page with a single decaying counter, which forces a false choice: cool rarely and rank pages well but react to change slowly, cool often and react quickly but rank badly. Two counters with different cooling periods dissolve the trade-off, because the long-run distribution and recent intensity are different questions with different natural timescales.
2. Recency-based systems that ought to adapt instantly turn out to adapt slowest, because they promote cold pages that happened to be touched, and those pages then occupy the fast-tier space that genuinely hot pages need — so accuracy about the hot set is a prerequisite for adaptiveness rather than an alternative to it.
3. Exact per-page counts are not required, since a hot page misread by one or two produces the same decision; a counting bloom filter sized to the fast tier instead of to total memory matches an exact table on more than 99.6 percent of migrations, cuts metadata from 0.39 percent of memory to as little as 0.05, and — with all of a page counters confined to one cache line — cuts the tiering share of system cache misses from 9 and 18 percent down to about 5.

Check yourself

Check your understanding

1. Why can a single decaying access counter not serve a tiering system well?
2. Why does the system with the freshest signal adapt the slowest?
3. What makes it safe to store access counts in a structure where pages collide?
4. Which limitation of the results deserves the most attention?

Sources

The paper is “HybridTier: an Adaptive and Lightweight CXL-Memory Tiering System” by Kevin Song, Jiacheng Yang, Zixuan Wang, Jishen Zhao, Sihang Liu and Gennady Pekhimenko, published at ASPLOS 2025, pages 112-128, DOI 10.1145/3676642.3736119. The authors are at the University of Toronto and the Vector Institute, the University of California San Diego, and the University of Waterloo.

This explainer is written from the full arXiv text, arXiv:2312.04789. Everything above comes from the paper’s own sections: the background on CXL and its latency and bandwidth characteristics, and on the skewed but rapidly shifting hotness distributions reported by two large operators and measured here on graph analytics and gradient boosting; the analysis of prior systems against three stated requirements, covering the histogram-based frequency approach and its cooling mechanism, the demonstration that shortening the cooling period trades adaptiveness against distribution accuracy, the measurement of adaptation time after an induced distribution change, and the argument that recency-based systems adapt slowest because mispromoted cold pages consume fast-tier capacity; the two overhead analyses, giving per-page metadata as a fraction of total memory with its server-scale extrapolation, and the measured share of system cache misses attributable to tiering under both regular and huge pages; the design covering the frequency and momentum counters and the four-case promotion and demotion policy with its second-chance rule, the counting bloom filter with its sizing formula and parameters, the four-bit counter cap and its justification, the separate sizing of the momentum filter, the blocked filter variant and its locality guarantee, the batched promotion and watermark-driven demotion, and the huge-page mode; the implementation as a userspace runtime linked at load time; the methodology covering the emulated slow tier, the five baselines including two the authors built, and the six workloads; and the evaluation covering regular and huge-page performance across three tier ratios, the comparison against an all-fast-memory upper bound, the adaptation-time and metadata tables, the cache-miss breakdown separating the plain and blocked filter contributions, the ablation isolating the momentum tracker, the filter accuracy measurement against an exact table, and the momentum threshold sensitivity study.