Skip to note
Pull the chain, or press here

No. 04Storage

SSTable compaction

Tidying up also creates work. Rude.

Published

An SSTable is a sorted file of records. As more files accumulate, newer values can coexist with older versions. Compaction merges selected data into new files; its strategy decides which work to do now and which work to leave for later.

Try it: same records, different tidy-up bill

Same records. Different tidy-up bill.

Leveled, then Read c

Merged run (8)

  1. a@1
  2. b@3
  3. c@1
  4. d@2
  5. e@3
  6. f@1
  7. g@1
  8. h@1

Read cc = v1

Records read
12
Records written
8
Entries retained
8 in 1 run
Runs checked for c
1

Numbers describe this toy workload only.

Leveled rewrote the base too: more writing now, one run to check later.

Tiered, then Read c

Base run (8)

  1. a@1
  2. b@1
  3. c@1
  4. d@1
  5. e@1
  6. f@1
  7. g@1
  8. h@1

Merged small runs (3)

  1. b@3
  2. d@2
  3. e@3

Read cc = v1

Records read
4
Records written
3
Entries retained
11 in 2 runs
Runs checked for c
2

Numbers describe this toy workload only.

Tiered left the base alone: less writing now, two runs that may hold c.

One simplified merge step, no Bloom filters, no benchmark timing. The numbers describe this fixture only.

Why?

Both strategies keep the newest version of every key, so reads return the same answers. They differ in when they pay: leveled rewrites overlapping data now to keep few runs; tiered defers that and leaves more runs for reads and space to cope with.

In broad terms, leveled compaction keeps tighter organisation and tends to control read and space costs, while rewriting overlapping data. Tiered compaction lets more sorted runs coexist and can reduce rewriting, at the expense of other costs. Actual engines add policy details; L0 is particularly good at ruining an overly tidy diagram.

Try both strategies on the same toy records. Look at records rewritten, entries retained and candidate runs checked. Both must still return the same latest values.

There isn't a universal winner hiding behind the animation. The useful question is which bill your workload can afford. Moving the mess is still a strategy; pretending the mess disappeared is a bug.

Sources