← Back
Home › Systems › Databases and storage engines

lsm-engine

embedded LSM key-value storage engine

RocksDB, LevelDB

SystemTechniques · 3Primitives · 17 lsm-engine LSM compactionstorage · medium: Compaction policies (leveled, tiered, time-window, FIFO) decide which sorted files to merge and when, trading write, read and space amplification and purging tombstones.›LSM-treestorage · medium: Buffer writes in memory, flush them as immutable sorted files and merge in the background; turns random writes into sequential I/O.›MVCCstorage · medium: Keep timestamped versions of each row so readers see a consistent snapshot without blocking writers; the default concurrency control in modern databases.›Bloom filterdata-structures · low: Bit array answering "definitely not present" or "probably present" in about 10 bits per key for 1 % false positives; inserts are cheap, deletes impossible.›K way mergesearch-sort · low: Merge k sorted streams with a heap or loser tree (merging iterators)Sstablestorage · low: Sorted string table: data blocks with restart points, index, filter and footerLZ4compression · low: Byte-aligned LZ77 with no entropy stage; compresses at hundreds of MB/s and decompresses at several GB/s per core, for when speed beats ratio.›Prefix compressioncompression · low: Front coding / shared-prefix truncation of sorted keys in blocks and index pagesZstandard (zstd)compression · low: LZ77 plus Huffman and FSE entropy coding, with levels from LZ4-like speed to xz-like ratio, all decoding at about 1-2 GB/s.›Skip listdata-structures · low: Sorted linked list with random express lanes; O(log n) search, simple inserts, and easy lock-free or single-writer concurrent reads.›CRC32C checksumshardware-os · low: The Castagnoli CRC-32 with dedicated instructions on x86 (SSE4.2) and ARMv8. It is the standard fast integrity check for storage blocks, logs and network frames.›fsync, O_DSYNC and O_DIRECThardware-os · low: What fsync, fdatasync, O_DSYNC, O_DIRECT and F_FULLFSYNC really guarantee on Linux and macOS, and the exact call sequences for crash-safe files.›Bulk loadingstorage · low: Build an index bottom-up from sorted input (SST ingest, B-tree bulk load) instead of point insertsGroup commitstorage · low: Let concurrent committers share one log write and fsync; throughput grows with concurrency while each commit still waits at most about two fsyncs.›Lsm merge operatorstorage · low: Store read-modify-write operands (counters, appends) and fold them at read/compaction timeWrite-ahead logstorage · low: Append each change to a checksummed sequential log and fsync it before touching data pages; the basis of crash durability in nearly every database.›LRU and CLOCKsystems · low: LRU evicts the least recently used entry via hash map plus linked list; CLOCK approximates it with a reference bit, so hits take no lock.›Token bucketsystems · low: A bucket of up to b tokens refilled at rate r; requests spend tokens, enforcing an average rate while allowing bursts of b.›Futex-based mutexconcurrency · low: A mutex that is one atomic word in user space and enters the kernel (futex wait/wake) only under contention; how std and glibc locks work.›+ 1 more primitives

Similar systems

Share the most building blocks with this one.

wide-column 52 %btree-engine 26 %event-store 25 %position-db 22 %document-db 21 %