Compaction Strategies, Tombstones, Bloom Filters, Caches, and Space Amplification

Learning outcomes

AtlasMart deletes an obsolete catalog item, yet an old value later reappears after a replica returns. At the same time, read latency oscillates with compaction and a tiny Bloom filter reports many “maybe” results. These symptoms are connected by LSM lifecycle rules: deletion is represented as data, compaction decides when versions can be reclaimed, probabilistic filters save negative I/O but allow false positives, and caches can conceal the underlying device cost.

1. Compaction policy chooses where background cost appears

Size-tiered / universal-style compaction generally merges similarly sized or time-adjacent runs, often accepting more overlap to reduce some rewriting. Leveled compaction organizes data into levels and constrains overlap beyond the newest level, usually improving read/space behavior while rewriting data across levels. Time-window strategies group time-correlated data so old windows can age out efficiently when updates rarely cross windows. These are families, not interchangeable product settings.

2. A tombstone is a delete that must defeat older values

Immutable files cannot simply erase an old value in place, so a delete is commonly represented by a tombstone: a newer version saying the key is absent. Reads must let that marker shadow older values. Compaction can eventually remove both the tombstone and the values it dominates—but only after the engine can safely conclude no relevant older copy/snapshot/replica may reintroduce the value.

In distributed databases this couples local compaction to repair/replica convergence. If replica A forgets the tombstone while replica B still holds an older live value, B can later stream that value back. Product-specific grace periods are therefore not magical constants; they encode assumptions about repair cadence, outages, backups/snapshots, and topology.

3. Bloom filters answer “definitely absent” or “maybe present”

A Bloom filter is a compact probabilistic membership structure. Inserted keys set several bits. A lookup whose required bits are not all set is definitely absent from that filter's set; if all are set, the key may exist. Collisions create false positives, which cause unnecessary SSTable/index reads. Correctly implemented Bloom filters do not invent a database row; the real file lookup still verifies the key.

False-positive probability depends on bit budget, number of inserted keys, and number of hash functions. More memory can reduce false positives, but filter memory competes with block cache and other metadata.

4. Caches change the path you observe

A hot block/key served from cache can make a poor on-disk layout look fast during a short benchmark. After restart, eviction, tenant contention, or a working-set shift, the same query may hit multiple files and reveal the true amplification. Measure cache hit ratio and cold/warm phases separately; do not compare two engines when one benchmark is warm and the other cold.

5. Wrong approach: purge delete markers on a fixed short timer

Deleting tombstones aggressively to reclaim space can resurrect data if an offline/stale replica later rejoins. The concrete failure is correctness-visible: a catalog item the business deleted becomes readable again. Repair is not “increase compaction”; it is to preserve the delete until the system's convergence/snapshot assumptions make reclamation safe, then verify with reconciliation histories.

6. AtlasMart lab — false positive, cache masking, and tombstone resurrection

import hashlib

class TinyBloom:
    def __init__(self, bits=16, hashes=2):
        self.bits = bits
        self.hashes = hashes
        self.vector = [0] * bits

    def positions(self, key):
        digest = hashlib.sha256(key.encode()).digest()
        return [int.from_bytes(digest[i*4:(i+1)*4], "big") % self.bits for i in range(self.hashes)]

    def add(self, key):
        for p in self.positions(key):
            self.vector[p] = 1

    def might_contain(self, key):
        return all(self.vector[p] for p in self.positions(key))

live = {"sku-1", "sku-2", "sku-3", "sku-4"}
bloom = TinyBloom(bits=12, hashes=2)
for key in live:
    bloom.add(key)
false_positive = next(k for k in [f"sku-{n}" for n in range(5, 200)] if bloom.might_contain(k))
print("Bloom bits:", "".join(map(str, bloom.vector)))
print("known live sku-2 ->", bloom.might_contain("sku-2"))
print("false positive candidate:", false_positive, "->", bloom.might_contain(false_positive))
print("false positive causes extra lookup, not a false row")

# Tombstone lifecycle for product:77.
replica_a = {"product:77": {"version": 3, "kind": "tombstone"}}
replica_b = {"product:77": {"version": 2, "kind": "value", "value": "old-title"}}

# Unsafe: compact A's tombstone away before B has been repaired.
replica_a.pop("product:77")
visible = replica_b["product:77"]["value"] if "product:77" in replica_b else None
print("unsafe early purge -> resurrected value:", visible)

# Safe model: keep tombstone until stale replica receives it, then reclaim later.
replica_a = {"product:77": {"version": 3, "kind": "tombstone"}}
replica_b["product:77"] = dict(replica_a["product:77"])
print("after repair both replicas:", replica_a["product:77"]["kind"], replica_b["product:77"]["kind"])

cache = {}
disk_probes = 0
for _ in range(3):
    key = "sku-2"
    if key in cache:
        source = "cache"
    else:
        disk_probes += 1
        cache[key] = 20
        source = "sstable"
    print("read", key, "from", source)
print("disk probes for three hot reads:", disk_probes)

Bloom bits: 001100101110
known live sku-2 -> True
false positive candidate: sku-11 -> True
false positive causes extra lookup, not a false row
unsafe early purge -> resurrected value: old-title
after repair both replicas: tombstone tombstone
read sku-2 from sstable
read sku-2 from cache
read sku-2 from cache
disk probes for three hot reads: 1

Verification

• The tiny Bloom filter intentionally finds an absent key that returns “maybe”; the subsequent lookup would still confirm absence.
• Dropping A's tombstone while B retains version 2 makes the old value visible again in the toy merge path.
• Propagating the tombstone to B before reclamation preserves deletion.
• The first hot-key read reaches the simulated SSTable; the next two hit cache, illustrating how cache warmth changes measured I/O.

7. Production judgment

Tune compaction from workload lifecycle and measured debt. Monitor pending compaction bytes/tasks, SSTable/file count, tombstone scans, Bloom false-positive rate where exposed, cache hit ratio, disk bandwidth, temporary space, and p99 latency. Never change tombstone reclamation independently of repair/replica outage assumptions.

Bridge to Lesson 5: We now have the components. The final lesson converts them into a disciplined storage-engine choice based on workload and device evidence.

Authoritative references

• Apache Cassandra — Storage Engine — current discussion of SSTables, Bloom filters, compaction, and write amplification
• Apache Cassandra — Compaction — implementation-specific compaction strategy guidance
• RocksDB — Compaction — current implementation example of leveled/universal compaction tradeoffs
• Bloom filter paper — Burton Bloom’s foundational probabilistic membership structure