Benchmark Your Key-Value Store

Measure LSM Tradeoffs

LSM tuning knobs include memtable size, bloom bits per key, compaction style, and block cache. RocksDB benchmarks report write amplification, read amplification, and p99 latency together because optimizing one metric often hurts another.

Workload Dimensions

Sequential write, random read, mixed read/write, and range scan. Track bytes written per user byte inserted.

c
Loading…

Warm up before timing steady-state compaction
Compare size-tiered vs leveled compaction policies
Plot latency histograms, not just averages
Document hardware: SSD vs HDD changes winners

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will run a modeled or implemented KV workload and print throughput plus amplification metrics. This exercise requires interpreting one tradeoff between write amplification and read latency.

Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.

Write a C program that models and benchmarks an LSM tree configuration.

Requirements:

Define an LSM configuration:
- memtable_size_mb = 4
- sstable_size_mb = 4
- num_levels = 4
- level_size_multiplier = 10 (each level is 10x larger than previous)
- bloom_filter_bits_per_key = 10
Calculate:
- Level capacities: L0=4MB, L1=40MB, L2=400MB, L3=4000MB
- Total capacity = sum of all levels
- Write amplification (leveled): approximately level_size_multiplier * (num_levels - 1) = 30
- Write amplification (size-tiered): approximately num_levels = 4
- Read amplification (leveled): at most num_levels = 4 (one SSTable per level)
- Read amplification (size-tiered): approximately num_sstables at L0 + 1 per lower level
- Bloom filter false positive rate: (0.6185)^(bits_per_key) for optimal k
Print the LSM configuration and level capacities
Print amplification metrics for both compaction strategies
Calculate how many SSTables exist at each level when full
Print a recommendation: which strategy to use for write-heavy vs read-heavy workloads
Model a workload: 1 million 1KB writes. Calculate total bytes written to disk for each strategy

Measure LSM Tradeoffs

Workload Dimensions

Sequential write, random read, mixed read/write, and range scan. Track bytes written per user byte inserted.

c
Loading…

Warm up before timing steady-state compaction
Compare size-tiered vs leveled compaction policies
Plot latency histograms, not just averages
Document hardware: SSD vs HDD changes winners

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will run a modeled or implemented KV workload and print throughput plus amplification metrics. This exercise requires interpreting one tradeoff between write amplification and read latency.

Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.

Write a C program that models and benchmarks an LSM tree configuration.

Requirements:

Define an LSM configuration:
- memtable_size_mb = 4
- sstable_size_mb = 4
- num_levels = 4
- level_size_multiplier = 10 (each level is 10x larger than previous)
- bloom_filter_bits_per_key = 10
Calculate:
- Level capacities: L0=4MB, L1=40MB, L2=400MB, L3=4000MB
- Total capacity = sum of all levels
- Write amplification (leveled): approximately level_size_multiplier * (num_levels - 1) = 30
- Write amplification (size-tiered): approximately num_levels = 4
- Read amplification (leveled): at most num_levels = 4 (one SSTable per level)
- Read amplification (size-tiered): approximately num_sstables at L0 + 1 per lower level
- Bloom filter false positive rate: (0.6185)^(bits_per_key) for optimal k
Print the LSM configuration and level capacities
Print amplification metrics for both compaction strategies
Calculate how many SSTables exist at each level when full
Print a recommendation: which strategy to use for write-heavy vs read-heavy workloads
Model a workload: 1 million 1KB writes. Calculate total bytes written to disk for each strategy

Topic Overview

Measure LSM Tradeoffs

Workload Dimensions

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

Benchmark Your Key-Value Store

Topic Overview

Measure LSM Tradeoffs

Workload Dimensions

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source