Preview: KV-Stores and Databases
summary
Compares LSM trees and unclustered-index logs by showing when moving data helps: LSM compactions improve read locality at the cost of write amplification from merging SSTables, while unclustered logs avoid compaction and get near-1× write amplification when the index fits in memory but need garbage collection later. On concurrency, memtable is a hotspot but compactions amortize locking; cuckoo hashing causes long lock chains when kicking items, whereas a power-of-two-choice design with 64-slot buckets removes kicking and on a 67M-insert benchmark across 1–8 threads achieves 7.3× vs 5.1× scaling (better insert throughput), queries scale similarly.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:44Spatial locality
- 2:57Data granularity
- 4:17Data structural question
- 4:57Log structure merge tree
- 7:07Unclustered index
- 9:14Concurrency
- 10:54Rights
- 12:28Cuckoo Hash Table
- 17:45Outro
related talks
34mWhat We Talk About When We Talk About Disk IO
39mAn Introduction to B-trees and LSM-trees for DEVs and DevOps
21mMatrixKV: Reducing Write Stalls and Write Amplification in LSM-tree Based KV Stores
05mExploring Data Deduplication in LSM Tree-based Key-Value Stores (Work-in-Progress Report)
35mQuestioning Database Claims: Design Patterns of Storage Engine
52mHow shit works: Databases
13mClosing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware...
39mDissecting the Humble LSM Tree and SSTable