Efficient Compactions between Storage Tiers with PrismDB

Storage now comes in two incompatible flavours — one costing 25 times more per byte and reading 65 times faster, the other cheap enough to hold everything but able to survive only about a thousand writes per cell — and databases are built for one or the other; PrismDB (Princeton and Columbia) builds for both at once, and the hard part turns out to be that the background job which keeps the cheap tier tidy and the job which keeps hot data on the fast tier are the same job, pulling in opposite directions.

Why this problem is worth solving

The data structure everyone uses embeds an assumption that one of these tiers violates.

And the quantity that decides whether a tiered design is viable is easy to make worse by accident.

What people did before, and where it broke

• Run everything on the fast tier. Straightforward and fast. Where it broke. Twenty-five times the cost per byte. And the measured gain is far smaller than the hardware difference suggests — 65 times lower read latency yields only 2.2 times more throughput, because once the storage is that fast the system becomes processor-bound.
• Run everything on cheap dense flash. What datacenters largely do. Where it broke. The system spends 36 percent of its processor time waiting on input and output, and the drive’s endurance becomes a planning constraint rather than a footnote.
• Map the upper levels of the tree to the fast tier and the lower ones to flash. The natural way to retrofit tiering onto an existing store, used by more than one published system. Where it broke. Levels are organised by how recently data was written, not by how often it is read, so the fast tier fills with recent-but-unpopular data. Measured here, 42 percent of reads still go to the slow tier.
• Treat the fast tier as an extra layer of cache below memory. The other common retrofit. Where it broke. It is a read cache and not a write cache, so every write still goes to flash, and it has to drag frequently-updated objects back up from flash. It consistently underperforms the level-mapping approach.
• Migrate whole files between tiers based on how popular they are. A published system does exactly this. Where it broke. A file holds thousands of small objects of wildly different popularity, so file granularity cannot separate hot from cold in a datacenter key-value workload.
• Just pin the hot objects to the fast tier. The obvious fix, and the paper implements it as a baseline. Where it broke. It offers little or no advantage, because the reads gained by serving more from the fast tier are cancelled by the extra compaction that pinning causes — which is the tension the rest of the paper is about.

How PrismDB moves data between tiers

The idea

A tiered store is not a store with a cache bolted on, because the fast tier wants a different data structure. The measurements that motivate the redesign are more interesting than the redesign itself. Putting 11 percent of a database on the fast tier costs $0.34 per gigabyte against$0.31 for conventional flash and recovers throughput to within 23 percent of an all-fast configuration — so tiering plainly works, and the question is why it does not work better. Two numbers answer it. The tiered system spends 54 percent of its processor time on background compaction, and much of that is spent sorting, which exists purely because flash wants long sequential writes and buys nothing on a device that updates small records in place. And 42 percent of reads still come from the slow tier, because the levels of the tree are organised by how recently something was written rather than how often it is read. Both are consequences of a structure designed for one kind of device being asked to span two. Hence the hybrid layout: unsorted size-bucketed slots on the fast tier, a sorted log on the slow one. Rebuilding a key-value store around the fact that storage devices no longer form a clean hierarchy is the same premise as the heterogeneous storage work covered elsewhere on this site.

The background job has two purposes and they fight, in a way that can be written down. This is the paper’s actual contribution and it is a genuinely nice piece of reasoning. Compaction must free space on the fast tier so new writes have somewhere to go, and it must keep popular objects there so the tier functions as a cache. Doing more of the second makes the first more expensive, and the mechanism is not obvious: if you retain most of what you encounter, the objects you do evict are scattered thinly across the key space, so merging them into the sorted flash files touches many more files than a dense batch would, multiplying the write amplification on precisely the device whose endurance you were trying to protect. The response is to borrow the cost-benefit analysis that log-structured filesystems use to choose which segment to clean, and redefine both halves for two tiers. Benefit becomes the summed coldness of a key range’s objects, coldness being the inverse of the access counter. Cost becomes flash traffic per migrated object, which rises as the fraction retained rises — the tension made arithmetic. The highest ratio wins. Deciding what to demote to the slow tier by measuring how hot each item actually is, rather than by structural position, is the same principle as the tiered memory placement work covered elsewhere on this site.

The exact algorithm is too slow to run, and the paper ships the approximation and says so. Precisely scoring every candidate key range gives an average compaction time of 25 seconds, which is unusable when compaction is already the bottleneck. Summarising each range into a small bucket of counters and bitmaps, then sampling eight candidates rather than examining all of them, brings that to 1.7 seconds — close to picking at random — while producing nearly the same total flash write traffic as the exact version. The paper states plainly that every subsequent mention of the algorithm refers to the approximation. That candour continues into a limitations section that names three real problems: write-heavy workloads at high request rates will wear out cheap flash regardless, scan performance is worse than the baselines for want of a prefetcher, and objects under 128 bytes trigger heavy read amplification because compacting one of them still reads a full four kilobyte page. That last one is visible in the results — on one production trace, the system merely ties the baseline. Depending on the operating system’s page cache and then finding its granularity is the wrong shape for your access pattern is the same discovery as the prefetching work covered elsewhere on this site.

Choosing what to evict

The partition is shared-nothing — one thread handles client requests for its slice of the key space and one handles compaction, coordinating through a single lock. Because most requests are now served from memory or the fast tier, the bottleneck has moved from storage to the processor, which is why minimising coordination matters.

Why it works

• Sorting is a concession to flash, not a universal good. Long sequential writes suit flash and small in-place updates suit the fast tier → so maintaining sorted order everywhere spends over half the processor budget on work one tier does not need → and storing the fast tier as unsorted size-bucketed slots removes that cost entirely.
• Recency and popularity are different orderings. A conventional tree places data by how recently it was written → so the fast tier fills with recent but unread objects and 42 percent of reads still fall through → whereas an explicit popularity counter places by how often data is actually touched.
• Retaining more makes eviction sparser and therefore costlier. Pinning most of what a compaction encounters leaves an eviction set scattered thinly across the key space → so merging it touches far more sorted files than a dense batch would → which multiplies write amplification on the very device whose endurance is scarcest.
• The trade-off can be scored rather than guessed. Log-structured filesystems already choose what to clean by benefit over cost → so redefining benefit as summed coldness and cost as flash traffic per migrated object gives a single comparable number → and picking the highest ratio balances the two purposes automatically instead of by a tuned constant.
• A cheap approximation preserves the ranking that matters. Scoring every candidate exactly takes 25 seconds per compaction, which is unusable when compaction is the bottleneck → so summarising ranges into small buckets and sampling eight of them costs 1.7 seconds → and produces nearly the same flash traffic, because the ranking only has to be roughly right.

What it costs (trade-offs and scope)

• The algorithm that is evaluated is not the algorithm that is derived. The exact scoring takes 25 seconds per compaction; the shipped version summarises and samples, reaching 1.7 seconds. The paper says outright that all later references mean the approximation, and shows the flash traffic is nearly identical — but the analytical model motivates a method that is not run.
• Cheap flash endurance is a deployment constraint, not a solved problem. The authors analyse three production workloads and find most are read-dominated enough for the drive to survive three to five years, but say a high-rate write workload will wear it out sooner and should be provisioned with higher-endurance flash instead.
• Tiny objects are a genuine weakness. Compacting a single object on the fast tier still reads a four kilobyte page, so objects under 128 bytes cause heavy read amplification and pollute the operating system page cache. On one production trace with 102 byte objects, throughput merely matches the baseline. The fix, an application-level page cache, is unimplemented.
• Scan performance is worse than the baselines. Stated in the limitations, attributed to the absence of a sophisticated prefetcher.
• The popularity threshold has no automatic setting. The best value differs by workload — higher for read-dominated, lower for write-dominated — and choosing it dynamically is left as future work.
• The tracker covers a fraction of keys. Only the most recently accessed 10 to 20 percent are tracked at all; everything else is treated as maximally cold, which is a reasonable default and also a systematic bias toward eviction.
• Comparisons required restricting a baseline. One competing system was limited to a different fast-to-slow ratio for fairness, and another candidate baseline was excluded after the conventional store outperformed it in the authors’ testing.
• Scaling stops at the core count. Throughput grows with partitions up to ten, which equals the cores allocated in the experiment.
• A single machine, one object size by default. Thirty-two cores with eight clients restricted to ten cores, one kilobyte objects in most experiments, and a single default ratio between the tiers.

The evaluation

Check yourself

Sources

The paper is “Efficient Compactions between Storage Tiers with PrismDB” by Ashwini Raina, Jianan Lu, Asaf Cidon and Michael J. Freedman, at Princeton University and Columbia University, published at ASPLOS 2023 Volume 3, pages 179-193, DOI 10.1145/3582016.3582052. It is open access under a Creative Commons Attribution licence.

This explainer is written from the full text, read from the authors’ copy on arXiv (2008.02352), the published version being unavailable through an automated fetch. Everything above comes from the paper’s own sections 2 through 8: the comparison of the two storage technologies on cost, latency and endurance; the three stated design goals for a tiered store; the single-tier and multi-tier measurements showing 65 times lower read latency yielding only 2.2 times more throughput, 36 percent of processor time in input-output wait on flash, 54 percent spent on compaction in the tiered configuration, and 42 percent of reads still served from the slow tier; the survey of prior approaches, both embedding fast storage into the tree and treating it as extra cache, with the reasons each falls short; the section 4 hybrid layout of size-bucketed slots on the fast tier and sorted files on flash, the memory-resident index covering only fast-tier objects, and the clock-based tracker covering only recently accessed keys with a mapper enforcing a retention threshold against a shifting distribution; the section 5 statement of the tension between reclaiming space and pinning hot data, including the sparse key range argument for why pinning raises write amplification, the adaptation of log-cleaning cost-benefit analysis with coldness-based benefit and flash-traffic-based cost, the resulting formula, and the approximation using bucket summaries and sampling that reduces average compaction time from 25 seconds to 1.7; the section 6 implementation details including reference counting and the compaction filter; and the section 7 evaluation across cloud benchmark workloads, production traces, component studies of promotion and retention threshold, scaling behaviour, drive lifetime analysis, and the limitations the authors state.