Tiered or Leveled? Why Not Both; Building Amethyst.

Suchitra Shankar — Thu, 11 Jun 2026 17:31:36 +0000

What if your storage engine could "understand" the incoming workload and switch its compaction strategy accordingly at runtime?

When building a database engine, you are typically forced to choose between optimizing for reads or optimizing for writes. Yet real workloads rarely stay the same.

So why do we still treat compaction as a static decision in a world where almost every other system component adapts at runtime?

We decided we didn't want to pick.

Enter Amethyst.

Amethyst is a lightweight, adaptive Log-Structured Merge (LSM) tree prototype built to dynamically switch compaction behavior at the segment level based on observed runtime workloads.

1. What is an LSM?

Amethyst is built on a Log-Structured Merge tree (LSM tree). To understand our approach, let's look at the diagram below, which shows the architecture of a typical LSM-based storage engine.

At a high level, an LSM tree achieves high write throughput by converting random writes into sequential disk operations. Incoming updates are first buffered in memory inside a MemTable. To ensure durability, every update is also appended to a Write-Ahead Log (WAL) before being acknowledged.

Once the MemTable reaches a size threshold, it is flushed to disk as an immutable Sorted String Table (SSTable). Over time, these SSTables accumulate across the storage hierarchy.

To prevent the number of files from growing indefinitely and to keep read performance under control, the storage engine periodically merges SSTables in the background through a process known as compaction.

This compaction process is the heart of every LSM tree, and it is precisely the component Amethyst seeks to make adaptive.

2. Compaction Policies

Most storage engines rely on a single compaction policy chosen when the database is initialized.

The first option is Leveled Compaction. Here, the storage hierarchy is divided into levels, each with a fixed capacity. SSTables within a level are kept non-overlapping, allowing lookups to quickly narrow down where a key might exist. This significantly reduces read amplification and improves lookup performance.

The downside is write amplification. To maintain these non-overlapping levels, the database must repeatedly rewrite data as it moves through the storage hierarchy. The result is excellent read performance at the cost of additional write overhead.

The second option is Tiered Compaction. Instead of enforcing strict non-overlapping levels, multiple SSTables are allowed to coexist within the same level. The database waits until a collection of similarly sized SSTables accumulates before merging them into a larger run.

This dramatically reduces write amplification because compactions occur less frequently and data is rewritten fewer times. However, the tradeoff appears during reads. Since multiple runs may contain overlapping key ranges, lookups often need to search several SSTables before finding the requested key.

For decades, storage engines have forced developers to make a permanent compromise between these two approaches.

The problem is that real-world workloads are rarely static.

A database might spend the morning ingesting large batches of data, making a write-optimized tiered layout ideal. Later, that same database might transition to serving read-heavy analytical queries, where a leveled layout would provide significantly better lookup performance.

Static compaction policies cannot adapt to these workload shifts. Once a strategy is chosen, the database remains locked into that decision, even when workload characteristics change dramatically.

This raises an obvious question: why should every part of the database be forced to use the same compaction strategy?

3. Observations

If you look across a modern software stack, systems are adapting continuously.

TCP congestion control dynamically adjusts its window in response to network conditions. Dynamic schedulers rebalance resources as demand shifts. Adaptive caching policies such as ARC continuously balance recency against frequency, while autoscaling systems provision infrastructure based on real-time load signals.

Yet, for some reason, compaction policy in most storage engines remains entirely static.

Once a database chooses between tiered and leveled compaction, that decision often remains fixed for the lifetime of the system, regardless of how dramatically the workload changes.

Back in 2018, database expert Mark Callaghan posed a simple but compelling question:

"Tiered or leveled compaction, why not both via adaptive compaction?"

That question became the foundation for Amethyst.

4. Building Amethyst

The observation was simple: workloads change, but compaction policies do not.

Turning that idea into a working storage engine was significantly harder.

An adaptive compaction system must answer three fundamental questions:

What should adapt?
How should workload shifts be detected?
How can adaptation occur without introducing more overhead than it removes?

Existing approaches often operate at a coarse granularity, making decisions for an entire database or an entire level at once. While this simplifies management, it also makes adaptation expensive and slow to react.

We wanted to explore a different direction.

Rather than treating the database as a single unit, Amethyst treats individual segments as independently adaptable entities. Each segment continuously observes its own workload characteristics and can make localized compaction decisions without requiring the rest of the system to change.

This design allows different regions of the same LSM tree to exhibit different behaviors simultaneously. Segments experiencing heavy write traffic can remain optimized for ingestion, while segments serving read-heavy workloads can gradually migrate toward layouts optimized for lookup performance.

In other words, different parts of the same database can follow different compaction strategies at the same time.

Once we committed to segment-level adaptation, the rest of the architecture began to fall into place.

5. Design Decisions

When we sat down to architect Amethyst, we had to ensure our adaptation mechanics wouldn't introduce more overhead than they solved.

The biggest problem we noticed with prior adaptive systems is that they try to change the state of the entire database, or even an entire level, all at once. Amethyst shifts this granularity by making the SSTable, along with its associated metadata, the fundamental unit of adaptation. We call this unit a segment.

By giving each segment its own metadata tracking structure, including MinKey, MaxKey, Strategy Tags, and physical I/O counters, the database can make localized decisions instead of applying a single policy globally.

However, runtime adaptation inherently risks thrashing: burning CPU cycles and disk I/O by constantly rewriting data as workloads fluctuate. We mitigated this by designing our finite state machine (FSM) with asymmetric trigger thresholds governed by Exponential Moving Averages (EMAs).

Write pressure is sudden and tends to degrade performance if left unaddressed, so the FSM aggressively transitions a segment to Tiered Compaction after just ten logged write operations. Conversely, read patterns are highly volatile. To prevent short-lived read spikes from triggering an expensive leveled merge, the FSM requires a sustained signal of 500 read operations before committing to a state change.

We also designed the compaction background thread to perform localized multi-way merges. Only the flagged segment and its immediate overlapping neighbors are read into memory and rewritten. Because SSTables are immutable, background ingestion and user read queries can continue concurrently without interruption.

For this initial proof of concept, we implemented both Tiered and Leveled Compaction ourselves within the same Go codebase. This eliminated confounding variables and ensured that we were measuring the architectural merit of the adaptation logic itself, rather than differences between independent implementations.

6. The math

Adaptive systems are only useful if they can correctly identify when conditions have changed.

This immediately raises a difficult question: how does a storage engine know when a workload has shifted from being write-heavy to read-heavy, or vice versa?

A naive approach would be to continuously scan historical workload data and perform expensive analysis. While this may produce accurate classifications, it also introduces significant runtime overhead. Since one of the design goals of Amethyst was to remain lightweight, we needed a simpler mechanism.

We ultimately settled on tracking a small set of workload signals and smoothing them using Exponential Moving Averages (EMAs). Unlike simple averages, EMAs place greater weight on recent observations while still retaining some historical context. This allowed the system to react to workload shifts without overreacting to short-lived spikes.

For each segment, Amethyst continuously tracks metrics: read frequency, write frequency, and compaction activity. These metrics are updated incrementally as operations occur, allowing the system to maintain an evolving view of segment behavior with minimal overhead.

The decision engine then evaluates these smoothed metrics against predefined thresholds. Segments that exhibit sustained write-heavy behavior are gradually steered toward tiered compaction, while segments experiencing sustained read pressure are moved toward leveled compaction.

An important design consideration was avoiding oscillation. If policy changes occur too aggressively, segments can repeatedly switch between strategies in response to transient workload fluctuations. This not only wastes resources but can also degrade overall performance.

To address this, Amethyst introduces hysteresis into its decision process. Policy transitions require persistent evidence that a workload has changed, rather than reacting immediately to every short-term variation. In practice, this significantly improves stability and prevents unnecessary switching.

The result is a lightweight adaptation mechanism that requires no offline training, forecasting, or complex optimization models. Instead, the system continuously observes its own workload and makes local decisions using a small amount of runtime state.

The mathematics behind Amethyst is intentionally simple. The objective was never to build the most sophisticated prediction model possible. The objective was to determine whether lightweight workload estimation alone could enable effective adaptive compaction.

The results suggest that, at least for the workloads we evaluated, the answer is yes.

7. Results

The primary goal of Amethyst was not to outperform every existing compaction strategy in every workload. If a workload remains perfectly stable, a carefully chosen static policy will often perform extremely well.

Instead, our goal was to determine whether a storage engine could adapt to changing workload characteristics at runtime and benefit from doing so.

To evaluate this, we benchmarked Amethyst against static Leveled and Tiered compaction configurations across a variety of workload mixes. We focused particularly on workloads whose read/write ratios changed over time, since these are precisely the scenarios where a single static policy becomes difficult to justify.

The results were encouraging.

Across the evaluated workloads, Amethyst achieved throughput improvements of up to 2.2× compared to static compaction strategies.

More importantly, these improvements appeared in workloads that experienced meaningful shifts in behavior during execution. During write-heavy phases, the system naturally favored tiered-style behavior to minimize write amplification. As read intensity increased, segments gradually transitioned toward leveled layouts, improving lookup efficiency and reducing read amplification.

This adaptive behavior allowed the system to avoid committing permanently to either extreme.

Perhaps the most interesting result was that adaptation could be achieved using relatively lightweight runtime signals. Amethyst does not require offline tuning, workload forecasting, or complex analytical optimization models. Instead, it relies on continuously observed workload statistics and local segment-level decisions.

Of course, the gains were not universal. In workloads that remained highly stable, static policies often remained competitive. This was expected. Amethyst was designed specifically for environments where workload characteristics evolve over time, and the results suggest that adaptive compaction is most beneficial in exactly those situations.

Overall, the evaluation provided evidence that segment-level runtime policy selection is both practical and effective. While there is significant room for improvement in future versions, the results validate the central hypothesis that motivated the project:

A storage engine does not necessarily need to commit to a single compaction strategy for its entire lifetime.

8. Things We Got Wrong (And What's Next)

Like most research projects, Amethyst did not emerge fully formed. Many of our initial assumptions turned out to be incomplete, naive, or simply incorrect.

Full disclosure: we built this prototype entirely on our own, without a formal research advisor. That meant a lot of early trial and error. When we hit a wall trying to figure out the right benchmarking metrics, Mark Callaghan's insights were a huge help in getting us unstuck. But for the overarching design, we were largely figuring things out as we went.

Since we were building this architecture completely from the ground up, we had to make several deliberate trade-offs. Here is a look at what we left out of the first version, and exactly what we plan to tackle next.

Space Amplification

Right now, our space amplification is quite high at 8.57×.

While this would be unacceptable for a production database, it is not a fundamental flaw of adaptive compaction. Garbage collection was intentionally left out of the prototype to keep our benchmarking clean and isolate the behavior of the adaptation FSM.

Now that we have validated the read and write performance improvements, one of our immediate priorities is implementing a proper background reclamation thread to bring space amplification down to more practical levels.

Workload Characterization

We relied on simple Exponential Moving Averages (EMAs) to detect workload shifts. The approach is lightweight, easy to reason about, and performed surprisingly well during evaluation.

However, collecting and maintaining workload statistics still consumes CPU cycles. As we move toward more realistic workloads, reducing the overhead of metric collection will become increasingly important.

We are also interested in exploring more predictive workload characterization techniques, including probabilistic models that can anticipate workload shifts instead of simply reacting to them.

Parallel Compaction

Amethyst currently executes compaction using a single background thread.

This simplified implementation helped us isolate the behavior of the adaptation logic, but it also leaves significant performance on the table. Modern storage engines aggressively parallelize compaction work, and Amethyst should be no exception.

Parallel compaction is one of the first major architectural improvements we plan to investigate in future versions.

Bloom Filters

One deliberate omission from V1 was Bloom filters.

We wanted to measure how much read amplification could be reduced through adaptive compaction alone, without relying on standard read optimizations to mask underlying inefficiencies.

Now that the adaptive baseline has been established, the next step is integrating dynamic, Monkey-style Bloom filter allocation on a per-segment basis. This will allow us to further improve lookup performance while preserving the adaptive behavior of the system.

Amethyst v1 was designed as a proof of concept rather than a production-ready database. The goal was to answer a simple question: can lightweight runtime workload estimation make adaptive compaction practical?

The answer appears to be yes.

The next challenge is turning that proof of concept into a more complete storage engine.

9. Open Questions

While the initial results are encouraging, Amethyst is far from a finished system. In many ways, the most interesting questions only emerged after the prototype was built and evaluated.

Granularity

One obvious question is granularity.

Amethyst currently performs adaptation at the segment level, but there is no guarantee that this is the optimal unit of decision making. Could adaptation become even more fine-grained? Or would the additional complexity outweigh any potential gains?

Workload Characterization

Another open problem is workload characterization.

The current system relies on a relatively small set of runtime signals combined with lightweight smoothing techniques. This was a deliberate design choice to keep overhead low. However, it remains unclear which workload characteristics are truly the most predictive.

Are there additional signals we should be collecting? Are there better ways to distinguish temporary workload fluctuations from genuine behavioral shifts?

Decision Making

The decision engine itself also leaves considerable room for exploration.

Amethyst currently relies on threshold-based policy transitions. While simple and effective, this approach may not always produce optimal decisions. More sophisticated probabilistic models, reinforcement learning approaches, or analytical cost models could potentially improve adaptation quality, though likely at the cost of additional complexity and runtime overhead.

Scaling the System

There are also important systems questions that remain unanswered.

How does adaptive compaction behave under significantly larger datasets? How does it interact with production features such as Bloom filters, background garbage collection, and parallel compaction threads? Do the benefits persist at scale, or do new bottlenecks emerge?

Beyond Compaction

Finally, there is a broader question that motivated the project from the beginning.

Most modern systems continuously adapt to changing conditions, yet storage engine compaction policies are still largely configured as static choices. If adaptation proves practical at the segment level, are there other storage engine decisions that should become adaptive as well?

We do not yet have answers to these questions.

However, they represent the directions we are most excited to explore as Amethyst continues to evolve.

10. Closing Thoughts

Amethyst began with a simple question:

Why do storage engines force us to choose a single compaction strategy?

The deeper we explored LSM trees, the more that choice seemed at odds with the reality of modern workloads. Systems adapt to changing conditions at nearly every layer of the stack, yet compaction policy often remains a static decision made long before the workload is fully understood.

This project was our attempt to challenge that assumption.

The result was Amethyst: a lightweight adaptive LSM-tree prototype capable of selecting compaction behavior at the segment level using runtime workload signals. While the system is still far from production-ready, the results demonstrate that adaptive compaction can be practical, lightweight, and effective under changing workload conditions.

More importantly, the project reinforced a lesson that applies far beyond storage engines. Many systems problems are not constrained by a lack of solutions, but by assumptions that have gone unquestioned for years. Sometimes progress comes not from inventing something entirely new, but from revisiting an old tradeoff and asking whether it is still necessary.

We do not believe Amethyst is the final answer to adaptive compaction. However, we hope it contributes to the broader discussion around adaptive storage systems and encourages others to continue exploring the space.

If you would like to learn more, the paper, source code, and presentation materials are linked below. We would be happy to hear your thoughts, questions, criticisms, or ideas for future directions.

Resources

Paper: Adaptive Compaction in LSM-Based Storage Systems
Code: Amethyst GitHub Repository

Contact

Suchitra Shankar: suchitrashankar07@gmail.com
Nilin Rose: nilinrose1@gmail.com

DEV Community: Suchitra Shankar

Tiered or Leveled? Why Not Both; Building Amethyst.

1. What is an LSM?

2. Compaction Policies

3. Observations

4. Building Amethyst

5. Design Decisions

6. The math

7. Results

8. Things We Got Wrong (And What's Next)

Space Amplification

Workload Characterization

Parallel Compaction

Bloom Filters

9. Open Questions

Granularity

Workload Characterization

Decision Making

Scaling the System

Beyond Compaction

10. Closing Thoughts

Resources

Contact