CSE Roadmap

Common tier · about 3 hours · 8 parts

Part 7 of 8 · 4 min read

Choosing between them

A rule of thumb and the questions that decide which engine suits a workload.

Choosing between them

Think of a delivery depot. One kind of depot sorts each parcel into its exact shelf on arrival. It is slower to receive, but any parcel is found at once. Another stacks arrivals quickly and sorts in the quiet hours. It receives fast, but finding a parcel can mean checking several stacks.

The book gives the rule of thumb: LSM-trees are typically faster for writes, and B-trees are thought to be faster for reads. Reads on an LSM-tree check several structures. It also warns that benchmarks are often inconclusive and depend on the workload, so a real test with your own data is the only reliable comparison.

Advantages of LSM-trees, from the book: higher write throughput, sometimes lower write amplification, sequential writes, better compression and less fragmentation.

Advantages of B-trees, from the book:

  • Predictable response times, with no background compaction competing for the disk.
  • Each key lives in exactly one place. This suits transactions, since in many relational databases isolation is done with locks on key ranges, and in a B-tree those locks attach directly to the tree.
  • Maturity: B-trees have been in use since 1970 and remain the standard index structure in almost all relational databases.
Question Leaning
Heavy writes, such as logs, events and time series LSM-tree
Mostly reads and point lookups with moderate writes B-tree
Strict latency at the 99th percentile B-tree
Need for strong transactions on ranges B-tree
Data larger than memory with high write volume LSM-tree
Disk wears out quickly under heavy writes LSM-tree, with care

Typical products:

Engine Products that use it
B-tree PostgreSQL, MySQL (InnoDB), SQL Server, Oracle, LMDB
LSM-tree Cassandra, HBase, RocksDB, LevelDB, parts of Lucene

A worked example. A system stores 50,000 events a second, each 200 bytes, and reads them mostly by user and time range.

  • Write volume: 50,000 × 200 = 10,000,000 bytes per second = 10 MB per second.
  • With a B-tree, each insert is a random page write: 50,000 random writes a second, with write amplification of about 40 (section 3). Disk writes: 10 MB × 40 = 400 MB per second. That is heavy.
  • With an LSM-tree and a write amplification of 10: 10 MB × 10 = 100 MB per second, mostly sequential.
  • The LSM-tree gives about four times less disk write volume (400 ÷ 100), and sequential access. So a wide-column store on an LSM engine is a natural fit, as module 1 suggested.

Ending on the book's caution: there is no quick rule for which engine is better, and testing with the real workload is worth the time.

Interview angle

Answer in your head first, then open it.

Why is Cassandra good at writes?

It uses an LSM engine. A write is a log append and a memory insert, with sorted files merged later. Name the cost: read work across files and compaction load.

Why does a relational database keep a write-ahead log?

The page changes of a B-tree touch several pages, and a crash could leave the tree broken. The log is replayed to repair it.

What is write amplification?

The extra disk writes caused by logs, page rewrites and compaction. It limits write throughput and wears out SSDs.

How do you check whether a key exists quickly in an LSM-tree?

A Bloom filter for each file, so most files are skipped.

Check yourself:

  • Which design suits predictable latency better, and why?
  • Why is an LSM-tree a good fit for a stream of 50,000 events a second?

Words you will meet

Word Plain meaning
Storage engine The part that lays out and finds data on disk
Page A fixed-size block, traditionally 4 KB
B-tree A tree of pages that keeps keys sorted
Branching factor The number of children a page points to
Leaf page The bottom level that holds the keys
Page split Dividing a full page in two
Write-ahead log (WAL) An append-only file written before the pages change
Copy-on-write Writing a changed page to a new place instead of overwriting
LSM-tree Log-structured merge-tree: memtable plus sorted files
Memtable A sorted in-memory table of the newest writes
SSTable A sorted file of key-value pairs
Compaction Merging files and dropping old values
Tombstone A marker that records a delete
Bloom filter A small structure that says a key is definitely absent, or maybe present
Write amplification Disk bytes written per application byte
Sequential, random write Adding at the end, or writing far from the last place