LsM-treeiswidely usedinproduction systemsAPACHGoogleBigTableHBASEDTANLBSTMUEUROcassandraRocksDBMariaDBlevelDBb
LSM-tree is widely used in production systems 6 RocksDB
Why Log-structured merge-tree(LSM-tree)?B+treeInsert2.5- In-placeupdateseekRandoml/Os-Lowwritethroughput2.5dddad,LSM-treewrites- Log-structuredupdate-Merge/compactionforsortingDRAM-Sequentiall/OsHDDmerges-Highwritethroughput
Why Log-structured merge-tree (LSM-tree)? • B+ tree – In-place update – Random I/Os – Low write throughput • LSM-tree – Log-structure for sequential I/O – Merge for sorting – Batched I/O operations – High write throughput 7 2.5 d2 ’ seek Insert 2.5 • LSM-tree – Log-structured update – Merge/compaction for sorting – Sequential I/Os – High write throughput 7 writes merges HDD DRAM
8SQLite Experiences of LSM-tree by Richard HippLog StructuredMerge(LSM)BadGood-Slowerreads.FasterwritesBackgroundmergeReduced writeprocessamplificationMorespaceondisk-Linearwrites.Greatercomplexity.LessSSDwear
SQLite Experiences of LSM-tree by Richard Hipp 8
AbuffercacheproblemreportedbyCassandrain2014CASSANDRA-6916-readoaC*2.1 beta1 vs beta2110,000effective caching100,00090,00080.00070,00060.00050,00warmingup40.00030,00020,000disenabled caching10,000250t5o20010060Total operation time (seconds)*https://www.datastax.com/dev/blog/compaction-improvements-in-cassandra-219
A buffer cache problem reported by Cassandra in 2014 9 *https://www.datastax.com/dev/blog/compaction-improvements-in-cassandra-21 warming up effective caching disenabled caching
BasicFunctionsofBufferCacheBuffer cache is in DRAM or other fast devicesData entries in buffer cache refer to disk blocks (page)Cache the frequently read disk blocks for reuseBuffer cache.disk2a10
Basic Functions of Buffer Cache • Buffer cache is in DRAM or other fast devices • Data entries in buffer cache refer to disk blocks (page) • Cache the frequently read disk blocks for reuse 10 b c a disk Buffer cache a c b