← Back
Home › Systems › Databases and storage engines

wide-column

wide-column store

Bigtable, HBase

SystemTechniques · 5Primitives · 17 wide-column Multi-Paxosdistributed · medium: Paxos run once per log slot with a stable leader that skips phase 1; the foundation of Chubby, Spanner and much production consensus.›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.›State-machine snapshotsdistributed · medium: Periodically save the state a log has produced at index i so the log prefix can be deleted; recovery and catch-up become load snapshot plus replay suffix.›Leasesdistributed · low: A lock that expires on its own: bounded-time ownership that survives crashes and partitions, given bounded clock drift and fencing tokens on writes.›Write-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.›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.›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 pagesRange partitioningdistributed · low: Cut the sorted key space into contiguous half-open ranges kept in a boundary map; split hot or big ranges, merge small ones, move ranges between nodes.›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.›Group 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.›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.›K way mergesearch-sort · low: Merge k sorted streams with a heap or loser tree (merging iterators)Copy-on-write forkhardware-os · low: fork() gives the child the parent's whole address space by sharing pages read-only and copying one only when someone writes it; vfork and posix_spawn skip even that.›Copy on write snapshotsstorage · low: Point-in-time snapshots by sharing pages/extents and copying only on writeFutex-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.›Fencing tokensdistributed · low: A number that grows with every lock grant and is checked by the protected resource, so a paused ex-holder's late write is rejected.›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.›+ 1 more primitives

Similar systems

Share the most building blocks with this one.

lsm-engine 52 %coordination-store 26 %btree-engine 25 %distributed-kv 25 %document-db 25 %

In-house systems

Named systems of this kind at large companies, with their paper or write-up.

BigtableAlphabet