← Back
Home › Systems › Databases and storage engines

relational-db

relational OLTP database with MVCC transactions

PostgreSQL, MySQL

SystemTechniques · 10Primitives · 33 relational-db Primary-backup replicationdistributed · medium: One node orders all writes and ships them to standbys; the acknowledgement rule (none, one, all) sets what a crash loses, and an external arbiter decides who takes over.›External merge sortsearch-sort · medium: Sort data larger than RAM: write memory-sized sorted runs, then k-way merge them with large sequential buffers; terabytes in one merge pass.›ARIES recoverystorage · medium: Three-pass crash recovery (analysis, redo, undo) for steal/no-force buffer pools; repeats history, then rolls back losers with compensation log records.›Buffer poolstorage · medium: The database's own page cache (frames, page table, pin counts, dirty bits, replacement) so it, not the OS, controls eviction, write order and I/O.›Cardinality estimationstorage · medium: Row-count estimates from histograms, MCVs, sketches and sampling for the optimizerMVCCstorage · medium: Keep timestamped versions of each row so readers see a consistent snapshot without blocking writers; the default concurrency control in modern databases.›Query optimizerstorage · medium: Cost-based plan search: join ordering (DP/greedy), rewrites, access path selectionWrite-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.›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.›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.›Hash joinstorage · low: Build a hash table on the smaller input's join key and probe it with every row of the larger one; the linear-time workhorse for equi-joins.›Recursive-descent parsingcompilers · low: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.›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.›B+ treestorage · low: Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.›Deadlock detectionstorage · low: Find transactions waiting on each other in a cycle (wait-for graph), abort one, or order lock requests so no cycle can form.›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.›Hash aggregationstorage · low: GROUP BY via hash tables with partitioning and spill to diskSlotted pagesstorage · low: Fixed-size page layout for variable-length records, with a slot array growing from the front and data from the back; stable record IDs despite compaction.›Sort-merge joinstorage · low: Sort both inputs on the key, then advance two cursors in lockstep and emit matching runs; cheap on sorted inputs and good for range joins.›Two-phase lockingstorage · low: Transactions take shared/exclusive locks and release none until they stop acquiring; strict 2PL holds them to commit and guarantees serializability.›Volcano iterator modelstorage · low: Open/next/close operator trees and their per-tuple overheadLeasesdistributed · 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.›Health checkingsystems · low: Decide per backend whether to route to it using probes and real-traffic errors, with consecutive-count hysteresis, capped ejection and a panic fallback.›+ 3 more techniques+ 17 more primitives

Similar systems

Share the most building blocks with this one.

embedded-sql 37 %btree-engine 31 %graph-db 28 %document-db 27 %query-engine 22 %