Divide and Compact: Segment-Oriented Compaction in SlateDB — SlateDB
docs blog discord github ★3.2k
LSMs typically represent all data within a single tree which is compacted over time. Controlling read/write amplification can be challenging when the data model mixes data structures with very different read/write patterns or lifetimes. Index structures, for example, tend to behave very differently from the data they point to. The single tree forces compromise to manage compaction across all structures at once.
Segment-oriented compaction in SlateDB gives you a way to split the dataset into separate trees so that compaction strategies can be tailored to the structure of the data in each tree. It is the swiss army knife which lets you isolate data by read/write frequency, retention policy, caching strategy, or whatever other dimension matters to your application.
This post provides an overview of segment-oriented compaction and how it can be used in your application.
How Compaction Works in SlateDB
SlateDB organizes data into an LSM tree. The LSM tree is divided into two parts: L0 and the sorted runs. The L0 tables are the raw SSTs generated from memtable accumulation during ingest. Over time, the compactor takes L0 tables and rewrites them into sorted runs. We refer to the tables in these layers loosely as L0s and SRs.
╭────────────────────────────────────────────────────────────────────╮
│ ◎ ○ ○ ░░░░░░░░░░░░░░░░░░░░ SlateDB's LSM Tree ░░░░░░░░░░░░░░░░░░░░░│
├────────────────────────────────────────────────────────────────────┤
│ │
│ writes │
│ │ │
│ ▼ │
│ ┌──────────┐ │
│ │ memtable │ in memory │
│ └────┬─────┘ │
│ │ flush │
│ ▼ │
│ L0 ─ raw SSTs from each flush; newest first, key ranges overlap │
│ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │ SST │ │ SST │ │ SST │ │ SST │ │
│ └─────┘ └─────┘ └─────┘ └─────┘ │
│ │ compaction rewrites L0 into sorted runs │
│ ▼ │
│ SORTED RUNS ─ SSTs in sorted order, no overlapping key ranges │
│ SR0 ┌────┬────┬────┐ │
│ │SST │SST │SST │ │
│ └────┴────┴────┘ │
│ SR1 ┌──────┬──────┬──────┬──────┐ │
│ │ SST │ SST │ SST │ SST │ │
│ └──────┴──────┴──────┴──────┘ │
│ │
└────────────────────────────────────────────────────────────────────┘
SlateDB’s LSM tree: L0 holds raw SSTs flushed from the memtable (newest first, ranges may overlap); compaction rewrites them into sorted runs of non-overlapping SSTs.
A compaction scheduler in SlateDB is responsible for selecting which L0s and SRs should be compacted together. Compaction strategies are typically heuristic. We don’t know exactly where keys will exist within the tree, but we can build strategies which optimize for certain tree structures and read/write amplification properties.
SlateDB’s default scheduler is known as “size-tiered” compaction. It works by selecting similarly sized SRs for compaction. The number of size tiers is limited by the size of the dataset. If a dataset is bounded, size-tiered compaction provides an upper bound on write amplification. The final tier is the size of the dataset itself. However, if the dataset grows over time, then write amplification grows as well. Size-tiered compaction is similar to universal compaction in RocksDB.
╭───────────────────────────────────────────────────────────╮
│ ◎ ○ ○ ░░░░░░░░░░░░░░ Size-Tiered Compaction ░░░░░░░░░░░░░░│
├───────────────────────────────────────────────────────────┤
│ │
│ tier 0 ─ L0 SSTs; similarly-sized runs accumulate │
│ ┌──┐ ┌──┐ ┌──┐ ┌──┐ │
│ │██│ │██│ │██│ │██│ │
│ └──┘ └──┘ └──┘ └──┘ │
│ │ merge ~N similar-sized runs into one larger run │
│ ▼ │
│ tier 1 ─ ~N× larger │
│ ┌────────┐ ┌────────┐ │
│ │████████│ │████████│ │
│ └────────┘ └────────┘ │
│ │ merge │
│ ▼ │
│ tier 2 ─ ~N²× larger │
│ ┌──────────────────┐ │
│ │██████████████████│ │
│ └──────────────────┘ │
│ │ merge │
│ ▼ │
│ final tier ≈ size of the whole dataset │
│ ┌────────────────────────────────────┐ │
│ │████████████████████████████████████│ │
│ └────────────────────────────────────┘ │
│ │
└───────────────────────────────────────────────────────────┘
Size-tiered compaction merges similarly-sized runs into a larger run at the next tier. As the dataset grows it adds tiers, and every byte is rewritten once per tier — so write amplification grows with the number of tiers.
More heuristic strategies are possible with a custom compaction scheduler, but we are limited to working within the constraints of the global LSM tree. It is not always straightforward to leverage the structure of the data itself to guide our scheduling. Frequently accessed data may get mixed with infrequently accessed, long-lived data may get mixed with short-lived, often updated data may get mixed with rarely updated, etc. It is up to us to structure the keys and the compaction heuristic as well as we can in order to optimize for our data model and its access patterns.
Where Size-Tiered Compaction Breaks Down
Size-tiered compaction works great for homogeneous data...