LSM compaction: leveled against tiered

How it behaves

One input on the horizontal axis, the others held fixed.

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

• 1 MB → 1 GB with g = 100 → 1.5 rewrites (3 with g = 10)

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

• Core Data Structures

  How do we choose a data structure when the real cost is set by the hardware, not by Big-O?

  $$L={\log }_T(N/M);\text{leveled }T\times L\text{ write, }L\text{ read};\text{tiered }L\text{ write, }T\times L\text{ read}$$

  Read it in place →

• Table & Storage Maintenance

  Who pays for the gap between the order data arrives in and the order it is read in: the writer, every reader, or a background job, and what is the break-even?

  $${\log }_g\left(\frac{s_{\text{target}}}{s_{\text{initial}}}\right)\text{rewrites per byte}$$

  g (growth factor) = $T$ · s_target / s_initial = $N/M$

  Read it in place →