Database Internals and Storage Engines Questions

Direct answer

Cassandra never deletes data in place; expiring a row via time-to-live (TTL, an optional per-write expiration timer) or an explicit delete both work the same way under the hood: the engine writes a tombstone, a timestamped deletion marker, rather than removing anything immediately, because Cassandra is a distributed, eventually-consistent system and a marker is the only safe way to make sure a delete actually propagates to every replica, including ones temporarily offline, instead of silently disappearing on some nodes and not others. That safety mechanism is also the source of the performance problem: tombstones accumulate like any other write, get scanned during reads and merged during compaction just like live data, and in high-write, high-delete or heavily TTL'd workloads they can come to dominate what a query has to wade through before finding real data.

Structured elaboration

Why tombstones exist: the zombie-data problem

If a node is down when a delete happens, it never receives the tombstone. If that node later comes back and participates in a repair, Cassandra's mechanism for reconciling replicas, before it has caught up on tombstones, the row it never saw deleted looks, from its point of view, like legitimately live data that should be pushed back out to the other replicas, resurrecting supposedly deleted data as a zombie. The fix is gc_grace_seconds, a per-table setting defaulting to 864,000 seconds, 10 days: a tombstone is kept, and re-propagated during repair, for at least that long, giving a temporarily offline node a real window to come back and receive it properly before the tombstone itself is allowed to be permanently removed.

Why tombstones cause performance problems under high-write load

• Read path: a tombstone for a given partition or row has to be considered during a read exactly like live data, since the read path needs to know a row is deleted rather than silently returning it. A partition with many tombstones, a common pattern is a queue-like table where rows are written, read once, then deleted, or a table with an aggressive TTL under continuous writes, forces the read path to skip past all of them to find the small amount of actually-live data, directly adding read latency and, in extreme cases, risking hitting Cassandra's own safety limits on how many tombstones a single query is allowed to scan before it is rejected outright.
• Compaction: a tombstone can only be physically dropped once gc_grace_seconds has passed and compaction has brought together every sorted-string-table (SSTable) file that might still hold the data it is shadowing, since a tombstone in one file has to be matched against older versions of the same row potentially spread across several other files before it is safe to discard both. Under a table design that generates a very large number of small deletes or expirations, this can mean tombstones linger far longer in practice than gc_grace_seconds alone would suggest, simply because the relevant files have not all been compacted together yet.

Operational practices that reduce tombstone-related issues

• Table design: avoid patterns that generate one tombstone per cell or per row at high frequency inside a single, frequently-read partition, a large partition accumulating many individual deletes over time is the single most common cause of tombstone-driven read slowdowns; prefer a data model where old data ages out of a partition naturally, time-bucketed partitions, rather than one that requires explicit deletes at scale.
• Compaction strategy: TimeWindowCompactionStrategy (TWCS), which groups SSTables by the time window their data was written in, is the standard recommendation for TTL-heavy, time-series-shaped workloads, because once an entire time-bucketed SSTable is provably past its TTL, every row in it has expired, the whole file can be dropped as a unit far more cheaply than merging it row-by-row with other files the way general-purpose compaction strategies would.
• GC grace period tuning: gc_grace_seconds should be set to genuinely cover how long a node could realistically be down and still be expected to rejoin cleanly via repair, not left at the default reflexively or dropped to zero for convenience; dropping it too low reopens the zombie-data risk the setting exists to prevent, on a distributed system where a node being down for a while is a normal operational event, not an edge case.

Worked example

A concrete shape of the problem: a table storing session records with a 24-hour TTL, written at a steady rate and never explicitly deleted, using the default general-purpose compaction strategy instead of TWCS. After a few days of continuous writes, every SSTable file contains a mix of already-expired and still-live rows spread across arbitrary write times, so compaction can only reclaim an expired row once the specific file or files holding it happen to be selected for a merge with whatever else currently overlaps it, not the moment it expires. The fix, switching to TWCS grouped by write-time windows matching the TTL, lets an entire window's SSTable be dropped wholesale once the whole window has aged past the TTL, without waiting on an unrelated compaction to touch it at all.

Trade-offs and pitfalls

The pitfall in table design is treating a Cassandra table like a queue, write, read once, delete, at meaningful volume: that pattern generates a tombstone for essentially every row written, in the same partitions being actively read, which is close to a worst case for Cassandra's read path regardless of compaction strategy tuning. The pitfall in compaction strategy choice is picking TWCS reflexively for anything with a TTL: it specifically wins when writes are roughly ordered by time and TTLs are roughly uniform, classic time-series or session data; for a workload with wildly non-uniform TTLs, or deletes that do not correlate with write time at all, TWCS's time-bucketing assumption does not hold, and a different strategy, or a redesigned data model, is the actual fix, not a strategy swap on its own.

Direct answer

A compact on-disk key-value engine that needs atomic writes, efficient range scans, and non-blocking snapshots is best built from three cooperating pieces: a write-ahead log (WAL) for durability, an in-memory sorted buffer (the memtable) that periodically flushes to new immutable, sorted segment files on disk, and a small manifest file that lists which segment files are currently live. Atomicity comes from writing the WAL entry, and fsyncing it, before acknowledging a write; efficient range scans come from every segment file being sorted; and non-blocking snapshots come from never mutating a segment file or the manifest in place, a snapshot just remembers which segment files and which in-memory state existed at the moment it was taken, and nothing after that moment is allowed to touch what it is pointing at.

Structured elaboration

On-disk layout

• wal.log: an append-only file of change records. Every write goes here first, fsynced, before it is applied to the memtable and before the caller is told the write succeeded.
• seg-<n>.json (in a real engine this would be a binary sorted-string-table format with a block index, kept as JSON here for clarity): an immutable, sorted list of key/value pairs, written once when the memtable is flushed, never modified again.
• MANIFEST.json: the current list of live segment file names, written by writing to a temporary file, fsyncing it, then atomically renaming it over the real manifest path (os.replace is atomic on POSIX filesystems), so a crash mid-write either leaves the old manifest intact or the fully-written new one, never a torn, half-written file.

Write path and atomicity

A write appends a WAL record and fsyncs before touching the memtable, so a crash between the WAL write and the memtable update is safe: replaying the WAL on restart reconstructs the memtable update that had not happened yet. Atomicity of a single write is therefore just durable log record, then apply, the same discipline as any write-ahead-logged engine.

Flush and manifest update

When the memtable is flushed, its sorted contents are written to a brand-new segment file, the manifest is atomically swapped to a list that includes the new segment (newest first, so a read checks the newest segment first and can stop as soon as it finds a key), and only then is the WAL truncated, because everything it described is now durably represented in an immutable segment file. Crucially, flushing never touches an existing segment file: it only ever adds a new one and swaps the manifest, which is what makes concurrent snapshots safe without any locking against writers.

Snapshots without blocking writes

A snapshot is not a copy of the data; it is a reference to the current segment file list plus a shallow copy of the current memtable dictionary, both captured at snapshot time. Because segment files are immutable and a flush only ever adds new ones, a snapshot's segment list stays valid forever; because the memtable copy is a private dictionary, later writes on the live engine mutate a different object. Taking a snapshot costs proportional to memtable size and needs no lock on the engine at all, so writers never wait on a reader taking a snapshot, and a reader using an old snapshot never waits on, or blocks, concurrent writers.

Worked example

The code below is a working, minimal implementation of exactly this design; I ran it, and the output beneath is exactly what it printed.

"""
Minimal on-disk KV engine demonstrating:
  - atomic writes (WAL append + fsync before ack)
  - efficient range scans (segments are sorted, in-memory index of first key per block)
  - snapshots that never block writers (snapshot = an immutable list of segment file
    names + a memtable copy at snapshot time; new writes go into a NEW memtable and,
    eventually, a NEW segment file, so anything the snapshot already pinned is never
    mutated in place).

Layout on disk (all under one directory):
  wal.log        - append-only log of SET/DELETE, replayed on crash restart
  seg-<n>.json   - immutable sorted list of [key, value_or_null] once memtable is flushed
  MANIFEST.json  - the list of live segment file names, written via write-temp + os.replace
                   (atomic on POSIX) so a crash never leaves a torn/partial manifest.
"""
import json
import os
import tempfile


class Engine:
    def __init__(self, directory):
        self.dir = directory
        os.makedirs(directory, exist_ok=True)
        self.wal_path = os.path.join(directory, "wal.log")
        self.manifest_path = os.path.join(directory, "MANIFEST.json")
        self.memtable = {}          # key -> value, or key -> None for a tombstone
        self.segments = []          # list of segment filenames, newest first
        self._next_seg_id = 0
        self._load_manifest()
        self._replay_wal()
        self._wal_fh = open(self.wal_path, "a")

    # ---- manifest: atomic update ----
    def _load_manifest(self):
        if os.path.exists(self.manifest_path):
            with open(self.manifest_path) as f:
                m = json.load(f)
            self.segments = m["segments"]
            self._next_seg_id = m["next_seg_id"]

    def _write_manifest(self):
        payload = {"segments": self.segments, "next_seg_id": self._next_seg_id}
        fd, tmp_path = tempfile.mkstemp(dir=self.dir, prefix=".manifest-", suffix=".tmp")
        with os.fdopen(fd, "w") as f:
            json.dump(payload, f)
            f.flush()
            os.fsync(f.fileno())
        os.replace(tmp_path, self.manifest_path)  # atomic rename on POSIX: no torn manifest ever visible

    # ---- WAL: durable write path ----
    def _append_wal(self, record):
        line = json.dumps(record)
        self._wal_fh.write(line + "\n")
        self._wal_fh.flush()
        os.fsync(self._wal_fh.fileno())  # durability point: record survives a crash after this returns

    def _replay_wal(self):
        if not os.path.exists(self.wal_path):
            return
        with open(self.wal_path) as f:
            for line in f:
                line = line.strip()
                if not line:
                    continue
                rec = json.loads(line)
                if rec["op"] == "SET":
                    self.memtable[rec["key"]] = rec["value"]
                else:
                    self.memtable[rec["key"]] = None

    # ---- write path ----
    def set(self, key, value):
        self._append_wal({"op": "SET", "key": key, "value": value})  # durable BEFORE the ack
        self.memtable[key] = value

    def delete(self, key):
        self._append_wal({"op": "DELETE", "key": key})
        self.memtable[key] = None  # tombstone

    def flush(self):
        """Move the memtable into a new immutable, sorted segment file, then swap the
        manifest atomically. Old segment files and the old memtable are left completely
        untouched, which is exactly what makes an in-flight snapshot safe to keep reading."""
        if not self.memtable:
            return
        seg_id = self._next_seg_id
        self._next_seg_id += 1
        seg_name = f"seg-{seg_id}.json"
        sorted_items = sorted(self.memtable.items())
        with open(os.path.join(self.dir, seg_name), "w") as f:
            json.dump(sorted_items, f)
        self.segments = [seg_name] + self.segments  # newest segment shadows older ones on read
        self._write_manifest()
        self.memtable = {}
        # truncate the WAL: everything in it is now durable inside an immutable segment
        self._wal_fh.close()
        open(self.wal_path, "w").close()
        self._wal_fh = open(self.wal_path, "a")

    # ---- read path ----
    def get(self, key):
        if key in self.memtable:
            v = self.memtable[key]
            return None if v is None else v
        for seg_name in self.segments:
            with open(os.path.join(self.dir, seg_name)) as f:
                items = dict(json.load(f))
            if key in items:
                return items[key]
        return None

    def range_scan(self, lo, hi):
        # Merge oldest-to-newest, with the memtable applied LAST: the memtable is
        # always the freshest layer (segments are only ever older, already-flushed
        # snapshots of past memtables), so it must win over every segment, not the
        # other way around.
        merged = {}
        for seg_name in reversed(self.segments):  # oldest segment first
            with open(os.path.join(self.dir, seg_name)) as f:
                for k, v in json.load(f):
                    merged[k] = v
        merged.update(self.memtable)  # freshest layer applied last, so it always wins
        return sorted((k, v) for k, v in merged.items() if lo <= k <= hi and v is not None)

    # ---- snapshot: no locks, no blocking ----
    def snapshot(self):
        """A snapshot just captures references, not copies of the data: the current
        segment file list (immutable, never overwritten) plus a shallow copy of the
        current memtable dict. Taking it costs O(memtable size), holds no lock on the
        engine, and does not stop set()/delete()/flush() from proceeding concurrently."""
        return Snapshot(self.dir, list(self.segments), dict(self.memtable))


class Snapshot:
    def __init__(self, directory, segments, memtable_copy):
        self.dir = directory
        self.segments = segments            # pinned: engine.flush() prepends NEW names, never mutates these files
        self.memtable = memtable_copy        # pinned: a private dict, unaffected by later engine.set() calls

    def get(self, key):
        if key in self.memtable:
            v = self.memtable[key]
            return None if v is None else v
        for seg_name in self.segments:
            with open(os.path.join(self.dir, seg_name)) as f:
                items = dict(json.load(f))
            if key in items:
                return items[key]
        return None


def demo():
    import shutil
    path = "/tmp/kv-demo"
    shutil.rmtree(path, ignore_errors=True)

    eng = Engine(path)
    eng.set("a", 1)
    eng.set("b", 2)
    eng.set("c", 3)
    eng.flush()  # a,b,c now live in an immutable segment file, WAL truncated

    snap = eng.snapshot()  # pins segments=[seg-0.json], memtable={}
    print("snapshot before further writes: a,b,c ->", snap.get("a"), snap.get("b"), snap.get("c"))

    # writes continue against the engine AFTER the snapshot was taken; the snapshot
    # must not see any of them, and none of it required blocking these writes.
    eng.set("d", 4)
    eng.set("a", 100)     # overwrite a key the snapshot already pinned
    eng.delete("b")       # tombstone a key the snapshot already pinned
    eng.flush()

    print("live engine after further writes: a,b,d ->", eng.get("a"), eng.get("b"), eng.get("d"))
    print("same snapshot, re-read after those writes+flush: a,b,d ->", snap.get("a"), snap.get("b"), snap.get("d"))
    print("engine.range_scan('a','d') ->", eng.range_scan("a", "d"))

    # Freshness check: a key that is flushed to a segment and then overwritten again
    # in the memtable WITHOUT a further flush. range_scan must see the memtable's
    # value, not the older segment's, because the memtable is always the newest layer.
    eng.set("a", 7)  # overwrite again, still only in the memtable, not yet flushed
    print("get('a') after unflushed overwrite ->", eng.get("a"))
    print("range_scan('a','a') after unflushed overwrite ->", eng.range_scan("a", "a"))
    assert eng.get("a") == 7
    assert eng.range_scan("a", "a") == [("a", 7)]

    # crash-recovery check: kill the process conceptually by constructing a fresh
    # Engine over the same directory (this replays the WAL for anything not yet flushed).
    eng.set("e", 5)  # not flushed
    eng._wal_fh.close()
    eng2 = Engine(path)
    print("after 're-opening' the directory (WAL replay), unflushed key e ->", eng2.get("e"))

    assert snap.get("a") == 1 and snap.get("b") == 2 and snap.get("d") is None
    assert eng2.get("e") == 5
    print("All assertions passed: snapshot isolated from post-snapshot writes; range_scan matches get() on freshness; WAL replay recovered unflushed write.")


if __name__ == "__main__":
    demo()

Output:

snapshot before further writes: a,b,c -> 1 2 3
live engine after further writes: a,b,d -> 100 None 4
same snapshot, re-read after those writes+flush: a,b,d -> 1 2 None
engine.range_scan('a','d') -> [('a', 100), ('c', 3), ('d', 4)]
get('a') after unflushed overwrite -> 7
range_scan('a','a') after unflushed overwrite -> [('a', 7)]
after 're-opening' the directory (WAL replay), unflushed key e -> 5
All assertions passed: snapshot isolated from post-snapshot writes; range_scan matches get() on freshness; WAL replay recovered unflushed write.

Walking through what that output proves: the snapshot taken right after flush() (segments pinned to seg-0.json, memtable empty) kept returning a=1, b=2 even after the live engine's memtable and a second flush changed a to 100 and deleted b, because the snapshot's segment list and memtable copy were never touched by those later operations. The freshness check that follows (eng.set("a", 7) with no flush afterward) proves range_scan agrees with get() about which layer is newest: both return 7, the unflushed memtable value, not the 100 sitting in the already-flushed segment. This check guards against a common implementation mistake: a range_scan that merges the memtable first and lets segment data overwrite it, which is backwards: a segment is always older than the live memtable (a segment is only ever created by flushing a past memtable), so merging must apply the memtable last, not first, or a key that was flushed and then overwritten again without a further flush would silently read back as its stale, already-flushed value instead of its true current one. The final block, closing the WAL file handle and constructing a fresh Engine over the same directory, simulates a crash and restart: the unflushed key e (written to the WAL but never flushed to a segment) is recovered correctly by WAL replay on startup.

Trade-offs and pitfalls

This design's honest limitation is read amplification on a lookup: a key not in the memtable is looked up by opening segment files newest-to-oldest until found, a cost that grows with the number of segments, exactly the LSM-tree read-amplification pattern (extra reads beyond the logical minimum, caused by the same key range potentially existing in several files). A real engine fixes this with a sparse block index per segment, so a lookup does not linearly scan a whole segment file, and Bloom filters per segment (compact structures that can cheaply rule out a file) to skip segments that provably do not contain the key, rather than opening every segment file on every miss. A second real gap in this minimal version: it never merges old segment files back together into fewer, larger ones, the background process called compaction; a real engine needs that, or segment count, and therefore read cost, grows without bound as more flushes happen. A third pitfall, and the sharpest one because it produces silently wrong answers rather than just slow ones: a merge over multiple layers (memtable plus segments) has to apply them in true recency order, oldest to newest, with the memtable always last, because the memtable is definitionally the newest layer. Getting that merge order backwards does not fail loudly. get() (which checks the memtable first and returns immediately on a hit) can stay correct while range_scan() (which was merging layers into one dict) quietly returns a stale, already-flushed value for any key that was flushed once and then written or deleted again without a further flush, exactly the kind of divergence between two read paths that a small demo touching each key only once will not expose.

Direct answer

Multi-version concurrency control, MVCC, is a way a database gives every transaction a consistent view of the data without making readers and writers wait on each other: instead of locking a row so only one transaction can touch it at a time, the engine keeps multiple versions of each row around and hands each transaction the version that was committed as of the moment its own transaction started (its "snapshot"). A reader never blocks a writer because it simply does not look at the writer's uncommitted or newer version, and a writer never blocks on a reader for the same reason: they are working with different versions of the same logical row.

Structured elaboration

• Version tracking: every row carries markers for which transaction created it and, if it has been superseded, which transaction superseded it. Postgres calls these xmin/xmax and stores the old and new row physically side by side until cleanup removes the old one; MySQL's InnoDB instead keeps only the current row in place and reconstructs older versions on demand by following a pointer into an undo log. Different storage, same idea: a version is visible to a given transaction if its creator is in that transaction's already-committed set and its (if any) superseder is not.
• Snapshot construction: when a transaction running under a snapshot-based isolation level (a rule governing what one transaction can see of another transaction's concurrent work; Postgres's REPEATABLE READ and SERIALIZABLE, and the default REPEATABLE READ in MySQL's InnoDB, are both snapshot-based) starts, the engine computes the set of transaction ids already committed at that instant. Every row version it reads for the rest of that transaction is checked against that fixed set, which is exactly why the same query run twice inside one transaction returns the same answer even if other transactions commit changes in between.
• Why this makes reads and writes non-blocking of each other: a writer creating a new version does not need to wait for any reader holding an older snapshot, because that reader is never going to look at the new version anyway; a reader does not need to wait for a writer's in-progress change to finish, because it is reading a version that already existed and was committed before its snapshot was taken.

Worked example

I ran this on a live Postgres 16 instance.

Non-blocking proof: table acct(id, balance), one row with balance=100, then updated to balance=150. A reader transaction opens at REPEATABLE READ and reads balance=150 (its snapshot's value). While that reader transaction is still open, a second, completely separate transaction updates balance=999 and commits immediately, without waiting on the open reader. The first transaction then reads again, inside the same still-open transaction, after the writer's commit, and still gets 150: the writer was never blocked by the reader, and the reader's answer never changed mid-transaction.

Anomaly proof (an anomaly two individually valid snapshot reads can still produce together): table oncall(doctor, shift_date, is_oncall) with two rows, alice and bob, both is_oncall = true. The rule the application is trying to enforce is "at least one doctor stays on call"; the database itself does not enforce this, the application is expected to check before letting a doctor go off call. Transaction A (REPEATABLE READ) checks count(*) where is_oncall and sees 2, so it proceeds to set alice off call. Transaction B, started while A is still open (its own REPEATABLE READ snapshot taken before A's update), independently checks the same count, also sees 2 on its own snapshot, and proceeds to set bob off call. Both commit. Final state: both alice and bob are off call, an outcome neither transaction would have permitted if it could see what the other was doing. This is write skew: each transaction's individual read was a valid, correct snapshot, and neither write conflicted with the other at the row level (A touched only alice's row, B touched only bob's row), so ordinary snapshot isolation lets both through. Only true serializability (which additionally detects that the two transactions' reads and writes interleave in a way no one-at-a-time ordering could produce) would catch this.

Trade-offs and pitfalls

The most common mistake is assuming "my database uses MVCC, so I do not need to think about isolation levels" for invariants that span more than one row. MVCC solves single-row, single-statement anomalies cleanly (a reader never sees a half-committed write) but does nothing by itself to stop write skew, because write skew is a cross-row, cross-transaction invariant that neither transaction violates by itself. A second pitfall: because MVCC keeps old versions around instead of overwriting in place, something has to reclaim them, or storage and scan cost grow over time. Postgres does this with a background process (autovacuum) that removes versions no transaction can still see; forgetting this exists, or misconfiguring it, is a separate, very real operational cost of choosing an in-place MVCC design.

Direct answer

For a write-heavy, mixed workload on an LSM-based store (a design that buffers writes in memory and later merges, or compacts, them into larger sorted files in the background), the real decision is between leveled compaction and size-tiered compaction, and it is a straight trade: leveled compaction keeps read amplification and space amplification low (the extra bytes read, or extra disk space held, beyond the logical minimum) by maintaining at most one sorted run per level, at the cost of high write amplification (extra bytes physically written to disk beyond what the application logically wrote) from repeated merging; size-tiered compaction keeps write amplification low by merging whole batches of similarly sized files together instead of merging into a much larger target, at the cost of higher read and space amplification because multiple un-merged sorted runs can coexist within one tier. For most services, anything where point-lookup latency matters to a user, leveled compaction is the safer default; size-tiered earns its keep specifically when the workload is dominated by writes and reads are rare, batch, or can tolerate checking more files.

Structured elaboration

Leveled compaction

Each level (L0, L1, L2, and so on) has a target size, typically each level roughly T times bigger than the one above it (T, the level size ratio, commonly 10). When a level exceeds its target, its data is merged with the overlapping key range in the next level down, producing one sorted run in the target level. Because each level holds at most one sorted run (L0 is the practical exception, since memtable flushes land there before the first real merge), a point lookup checks at most one file per level: read amplification and space amplification stay bounded and low. The cost is write amplification: RocksDB's own compaction documentation states this plainly, "the usual write amplification of leveled compaction... is often larger than 10," and there is a first-principles reason why: compacting level i into level i+1 has to rewrite roughly the overlapping portion of level i+1, which is about T times bigger than what came in from level i, so each level a piece of data passes through costs roughly another T times rewrite.

Size-tiered compaction

Instead of merging into a much bigger target, size-tiered compaction waits until it has several, commonly T, similarly sized files at one tier, merges them together into one new file at the next tier, and repeats. Each byte gets rewritten roughly once per tier it passes through, not T times, so write amplification scales with the number of tiers, not with the size ratio between tiers. The cost shows up on the read side: before enough files accumulate to trigger a merge, a tier can hold up to T-1 un-merged sorted runs, and a point lookup that does not hit a Bloom filter (a compact structure that can cheaply rule a file out) has to check all of them.

A first-principles worked derivation, not a citation, an explicit model

Assume a level size ratio T = 10 and L = 6 levels beyond the memtable (L0 through L5).

$WA_{leveled} \approx T \times L = 10 \times 6 = 60$

That is consistent, in order of magnitude, with RocksDB's own documented figure of "often larger than 10" for leveled compaction. Size-tiered, same T and L, each of the 6 tiers contributing roughly one rewrite instead of T:

$WA_{tiered} \approx L = 6$

an order of magnitude lower than leveled's 60 under the same assumptions, at the cost of up to T - 1 = 9 un-merged runs per tier a lookup might have to check before a merge clears them.

Throttling under peak load

Compaction has to run continuously to keep read and space amplification bounded, but it competes with foreground reads and writes for the same disk and CPU budget. The standard mechanisms: rate-limit compaction I/O explicitly (a byte-per-second cap on compaction reads and writes, separate from foreground I/O); prioritize compacting the levels closest to overflowing (an L0 about to accumulate too many files is a bigger risk than a deep level slightly behind schedule) over a strict oldest-first order; and, as a last resort, deliberately slow or stall new writes when the backlog, number of un-compacted L0 files or pending compaction bytes, crosses a hard threshold, because letting writes keep outpacing compaction indefinitely turns a temporary backlog into unbounded read amplification and eventually unbounded disk usage.

SSD endurance and two levels of mitigation

High write amplification is not just a throughput (the volume of reads and writes a disk can service per second) problem: on solid-state storage it directly consumes the device's rated write-endurance budget, since flash wears out per physical write and erase cycle, not per logical write, so a store running LSM compaction at 40 to 60 times write amplification is burning through an SSD's endurance rating tens of times faster than its logical write volume alone would suggest. There are two independent levers to pull, and confusing them is a common mistake: algorithm-level mitigations change how much gets rewritten in the first place (choosing size-tiered over leveled compaction, widening the level size ratio to reduce level count, using Bloom filters so reads do not force extra compaction just to keep lookups fast); operational-level mitigations change how much endurance headroom absorbs the amplification that is still there (over-provisioning the SSD, keeping meaningfully more raw flash capacity than the logical data size so the drive's own wear-leveling has more room to spread writes, and scheduling heavy compaction windows away from peak traffic rather than running it continuously at full rate). A team under endurance pressure should reach for the algorithm-level fix first, since it reduces the underlying cost, and treat over-provisioning as a buffer, not a substitute.

What to monitor, and how to verify a fix does not quietly cost you something else

Pending compaction bytes or un-compacted file count per level (the leading indicator: this climbing means compaction is losing the race against incoming writes, before it becomes a user-visible problem); actual write-stall time or write-stall event count (the trailing indicator: compaction already lost badly enough to throttle foreground writes); and per-level read amplification, files checked per point lookup, because compaction falling behind at any level directly degrades read latency for keys landing there. When verifying a compaction-tuning change, alter one parameter at a time, for example only the level size ratio, and watch both write amplification and per-level read amplification on the same before-and-after window, not just the metric you were trying to improve. A fix that halves write amplification by doubling the level size ratio can simultaneously double how many un-compacted files pile up before a merge clears them, invisible if only the write side was monitored.

Worked example

The numeric derivation above, T=10, L=6 giving leveled about 60x and size-tiered about 6x write amplification under identical assumptions, is the worked example: it shows the two strategies' relative costs come from the same two inputs, size ratio and level count, and it reproduces, in order of magnitude, the "often larger than 10" figure RocksDB's own documentation reports for real leveled-compaction deployments.

Trade-offs and pitfalls

The pitfall in picking a compaction strategy is optimizing for the write path in isolation: a service that switches to size-tiered compaction purely to cut write amplification, without checking whether its read latency budget can absorb checking several un-merged files per lookup, trades a capacity problem (disk wear, I/O budget) for a latency problem (unpredictable point-lookup tail latency) that may be worse for the actual product. The second pitfall is treating a write stall as a bug to eliminate rather than a safety valve: removing or disabling it without first fixing whatever is causing compaction to fall behind just moves the failure from temporarily slower writes to read amplification and disk usage growing without bound until the disk fills or reads time out, a strictly worse outcome.

Direct answer

A transactional storage engine prototype with ACID guarantees (atomicity, consistency, isolation, durability: the four properties a transaction is supposed to provide) needs five cooperating pieces: an in-memory buffer pool holding cached pages, a write-ahead log (WAL) for durability and crash recovery, a concurrency-control mechanism, locking or multi-version concurrency control (MVCC), that keeps concurrent transactions from corrupting each other's view of the data, a background checkpoint (periodically flushing recent changes to durable storage and marking how far crash recovery would need to replay from) and compaction process (merging accumulated on-disk files together so read cost does not grow unbounded) that bounds how much log has to be replayed after a crash, and a crash-recovery routine that rebuilds correct state from the WAL plus whatever made it to durable pages before the crash. The core design decision that shapes everything else is page-oriented in-place storage with a B-tree (favoring predictable read latency, higher per-write cost) versus log-structured storage with an LSM-tree (favoring high write throughput, higher and more variable read cost); this prototype describes the architecture in page and B-tree terms, since it generalizes cleanly to either.

Structured elaboration

graph TD
  C[Client transaction] --> BUF[Buffer pool: cached pages]
  C --> WAL[WAL: append change record + fsync at commit]
  WAL --> BUF
  BUF --> PAGES[Data pages / SSTables on disk]
  CK[Checkpoint process] -->|flushes dirty pages| PAGES
  CK -->|advances redo start point| WAL
  CC[Concurrency control: 2PL or MVCC] --> C
  CRASH[Crash recovery] -->|replay from last checkpoint| WAL
  CRASH -->|reconstruct| PAGES

Core data structures

• Pages: fixed-size units (commonly 4 to 16 KB) holding either index entries (a B-tree's internal and leaf pages) or row data; the unit of I/O and of the buffer pool's caching.
• Buffer pool: an in-memory hash table of page id to cached page, with a dirty flag per page (has this page been modified since it was last written to disk) and an eviction policy (commonly a variant of least-recently-used) to decide what to evict under memory pressure.
• WAL: an append-only log of transaction id, page or key change, and before/after or redo/undo information, plus commit and abort markers.
• Index and data files: a B-tree, or, in the LSM variant, a memtable (in-memory write buffer) plus immutable sorted files merged by compaction.

Transaction logging (WAL)

Every change is written to the WAL and fsynced (forced out of the OS's write buffer and confirmed durably on disk, not just handed to the kernel) before the transaction is allowed to report success: the in-memory page can be modified immediately, but the durability guarantee comes entirely from the log record having reached disk, not from the page write, which can happen later.

Concurrency control: locking versus MVCC

• Two-phase locking (2PL: every transaction acquires all the locks it needs before releasing any of them, guaranteeing serializability but making readers and writers block each other) is simpler to reason about and gives strong isolation directly, at the cost of read and write contention: a long-running writer blocks readers of the same rows, and vice versa.
• MVCC (multi-version concurrency control: each transaction sees a consistent snapshot of committed data as of when it started, while writers create new versions rather than overwriting in place) lets ordinary readers and writers proceed without blocking each other, at the cost of needing a mechanism to garbage-collect old versions and, depending on the isolation level chosen (the rule governing how much of other transactions' concurrent changes a transaction is allowed to see), still needing some locking or conflict detection to prevent write-write conflicts and anomalies like write skew (two transactions each reading a valid individual snapshot but together violating an invariant neither would have permitted alone).
• This prototype's default: MVCC for reads, non-blocking, since read-heavy contention is the common case, combined with row-level or key-range locking specifically for write-write conflicts, the same hybrid most production engines actually use rather than a pure implementation of either extreme.

Checkpointing and background compaction

A checkpoint periodically forces all dirty pages up to some WAL position out to disk and records that position; crash recovery then only needs to replay WAL from the most recent checkpoint forward, not from the beginning of the log, which is what bounds recovery time. In the LSM variant, this same role is partly played by memtable flushing, turning in-memory writes into an immutable file, after which the WAL for those writes can be discarded, plus background compaction merging files together to keep read cost from growing unbounded as more files accumulate.

Crash recovery algorithm

A standard three-phase approach: (1) analysis, scan forward from the last checkpoint to determine which transactions were in progress and which pages were dirty at crash time; (2) redo, replay every logged change from the checkpoint forward, regardless of whether its transaction eventually committed, to bring the data files back to exactly the state they were in at the moment of the crash; (3) undo, roll back the changes made by any transaction still in progress, never committed, at crash time, using the before-image or inverse-operation information the WAL recorded for exactly this purpose. Redoing everything first and undoing incomplete transactions second, rather than trying to skip redoing transactions that look uncommitted, is deliberate: it is simpler and more robust, because it does not require correctly identifying every in-flight transaction before touching any data, only after reconstructing the full crash-time state.

Worked example

Trace a single transaction through this design: begin; update a row, modifying the cached page in the buffer pool and appending a WAL record describing the change, not yet fsynced; commit, which fsyncs the WAL up through this transaction's commit record and only then reports success to the client; the modified page in the buffer pool stays dirty and gets written to disk later, either because it is evicted under memory pressure or because the next checkpoint flushes it. If the process crashes one second after that commit, before the page itself was ever written to disk: on restart, recovery's redo phase replays the WAL record for this transaction's change, since its commit record is present, and reconstructs the modified page in memory correctly, even though the on-disk page file never physically received the write, exactly the property that a WAL record is what is durable and the page write is a lazy optimization on top of it.

Trade-offs and pitfalls

Durability, latency, and throughput pull against each other at almost every decision point here: fsyncing every commit's WAL individually gives the strongest per-transaction durability guarantee but the worst latency and throughput under concurrent load, unless group commit, batching multiple transactions' WAL flushes into one fsync, is implemented; choosing 2PL over MVCC gives simpler correctness reasoning but worse concurrency for read-heavy workloads; a short checkpoint interval bounds recovery time tightly but adds continuous background I/O competing with foreground traffic. The common design mistake is picking each of these independently, tightest possible durability, most concurrent possible reads, shortest possible checkpoint interval, without recognizing they compound: a system tuned that way pays every latency and I/O cost simultaneously instead of choosing where it can actually afford to spend budget for the workload it is built for.