Benchmark Your Key-Value Store

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