Design two stores: an append heavy tick archive taking 500,000 writes per second with range scans by (symbol, time), and an order state store taking 50,000 updates per second to a small hot set read by primary key. Choose an LSM tree or a B-tree for each and justify both from the write path.

Design two stores: an append heavy tick archive taking 500,000 writes per second with range scans by (symbol, time), and an order state store taking 50,000 updates per second to a small hot set read by primary key. Choose an LSM tree or a B-tree for each and justify both from the write path.

Approach: Describe what each engine does to the disk on a single write, then match that behaviour against the read pattern and the update pattern each store must serve.

An LSM tree for the tick archive and a B-tree for the order state store. The log structured merge tree buffers writes in a memtable and flushes sorted runs, so every disk write is a sequential write and ingest is bounded by throughput rather than by seek time, which is what 500,000 appends per second requires, and its sorted runs make a range scan by (symbol, time) natural when the key is ordered that way. The cost is read amplification, since a point read may probe several levels, plus a background compaction load competing with ingest. A B-tree performs an in place update of a page plus a log append, so a write is a random page write and ingest is capped far lower, while a point read is a single traversal of about four levels with no merging and the hot set stays resident in the buffer pool. The order state store overwrites the same keys repeatedly, and an LSM would turn each overwrite into a new version that compaction must later reclaim, so 50,000 updates per second generate far more disk work there than a B-tree's update of a cached page. The general trade the two cases show is that an LSM buys write throughput with read cost and background io, and a B-tree does the reverse.

Follow-up: Which engine would you pick if the order state store also needed a scan of every open order by symbol?

Key concepts: log structured merge tree, b-tree in place update, sequential write, read amplification.