案例库 · 工程与运营 · 技术决策 · 1996-2010s
这条还没译成中文，下面是英文原文。
The LSM-tree made randomly-written databases cheap by never updating in place
O'Neil's log-structured merge tree buffered writes and merged them, turning billions of random disk writes into big sequential ones.
O'Neil · LevelDB · RocksDB
那一手
Maintaining an index in place costs a random disk read plus a random disk write per insert, and on a large index the leaf page is touched too rarely to stay cached. The result is very expensive as writes grow.
The log-structured merge tree (LSM-tree) by O'Neil, Cheng, Gawlick and O'Neil in 1996 changes the shape: writes land in memory, then are flushed to disk as large sorted components that are merged in the background. This amortizes the cost of indexing an insert by the batching factor of the merge.
The insight became the storage engine for LevelDB, RocksDB, Cassandra, HBase and Bigtable: write fast, merge lazily, and pay with extra read amplification and occasional compaction.
为什么管用
- Disk seeks are expensive per byte, so doing one large sequential write per batch is far cheaper than many small random writes.
- Batching many new records into a single merged block spreads the arm cost across them.
- Keeping C0 in memory removes the immediate write and lets the flush happen in bulk.
- The trade is a read that may check several components, which became acceptable when storage got fast.
可以搬走什么
When the cost is a random operation, reshape the work into big sequential chunks merged in the background, and pay where you mind it least.
后来呢
The LSM-tree became the storage shape underneath LevelDB, RocksDB, Cassandra, HBase and Google's Bigtable, and it reshaped how write-heavy databases were built, though its read and write trade-offs have to be re-derived as hardware changes.
资料来源
- The Log-Structured Merge-Tree (O'Neil et al., 1996) — Annotated, with the Original PDF
- LSM-Trees Explained — Memtable, SSTables, Compaction, RocksDB
发现哪里写错了？告诉我们。