Storage Engines experimental

Storage Engines How a database actually works, the capstone: B-trees and LSM trees, the write-ahead log, MVCC and the buffer pool. On-disk structures. On-disk structures. Compare B-trees and LSM trees.. Explain the read/write trade-off between B-trees and LSM trees, and select the appropriate structure for a stated workload profile.. Pages, B-trees, LSM trees, Read/write trade-offs Pages Every storage engine is, underneath, a translator between a byte-addressable API (get(key), put(key, value), scan(lo, hi)) and a block-addressable disk. The unit of that translation is the page: typically 4 KiB to 16 KiB, chosen to match filesystem blocks and, historically, disk sector geometry. Pages are the atomic unit of I/O: the engine never reads or writes less than a page, because the operating system (OS) and the drive won't either. A page holds a header (page id, log sequence number (LSN), checksum, free-space pointer), a slot array for variable-length records, and the record payloads themselves, usually growing toward each other from opposite ends of the page. Fixed page size is what makes free-list management, buffer-pool addressing, and checksum placement tractable; it is also why a single record larger than a page requires overflow pages or out-of-line storage. B-trees A B-tree (in practice almost always a B+-tree) keeps all keys and values in leaf pages, chained in sorted order via sibling pointers, with internal pages holding only separator keys and child pointers. Every leaf is the same distance from the root, so lookup is O(log_B n) page reads where B is the branching factor; with B in the low hundreds, a multi-billion-row table has a tree height of 3-4. The defining trait is in-place update: a write finds the target leaf and modifies it directly, which means a single logical write can touch a page that lives anywhere on disk, and pages fragment and split under insert pressure, requiring occasional rebalancing. B-trees are read-optimized: point lookups and range scans both cost roughly the height of the tree, with no need to consult multiple versions of the data. LSM trees A log-structured merge (LSM) tree inverts the trade-off. Writes land first in an in-memory sorted structure (a memtable, often a skip list), which is also appended to a write-ahead log (WAL) for durability, and are never modified on disk in place. When the memtable fills, it is flushed as an immutable sorted file (an SSTable) to disk. Reads must therefore potentially check the memtable and multiple SSTables across multiple levels, from newest to oldest, until a key is found or exhausted: this is read amplification. Background compaction merges SSTables to bound the number of files a read must touch and to reclaim space from deleted/overwritten keys, at the cost of write amplification: a byte written by the user may be rewritten several times as it moves through compaction levels (leveled compaction: ~10x typical; size-tiered: lower write amp, higher space and read amp). Read/write trade-offs The comparison reduces to where you pay the cost of maintaining sorted order. B-trees pay it immediately and randomly, at write time, in place. LSM trees defer and batch it, paying it later and sequentially, via compaction. Consequently, B-trees suit workloads dominated by random point reads and updates (online transaction processing (OLTP) with hot small working sets that fit the buffer pool), because a read is deterministic in cost and writes to random keys don't need to be re-sorted. LSM trees suit write-heavy and append-like workloads (time series, event logs, ingestion pipelines) because writes are always sequential (append to memtable/WAL, sequential SSTable flush), at the expense of read amplification and CPU spent on compaction. Bloom filters per SSTable mitigate LSM read amplification for point lookups on absent keys; a well-tuned LSM (e.g., RocksDB) can still beat a B-tree on write throughput by an order of magnitude while giving up some read latency and steady-state CPU to background compaction. Compaction strategies Leveled compaction organizes SSTables into levels of exponentially increasing size, merging a file from one level into the overlapping files of the next whenever a level exceeds its size threshold, which bounds the number of files a read must check but multiplies write amplification since each byte is rewritten roughly once per level it passes through. Size-tiered compaction instead merges same-sized files together only once enough of them accumulate, producing lower write amplification at the cost of more files, and therefore more read amplification, sitting at any given level between merges. Neither strategy dominates the other unconditionally; the choice is itself a workload decision, trading write cost against read cost exactly as this module's broader B-tree versus LSM discussion does one level up. Real-world engine choices Production systems rarely pick one structure in isolation from the workload it will actually serve: PostgreSQL and MySQL's InnoDB, both B-tree-based, dominate general-purpose transactional workloads where point lookups and range scans on a hot working set are common; RocksDB and Cassandra, both LSM-based, dominate write-heavy and time-series workloads where sustained ingestion throughput matters more than worst-case read latency. Some systems hedge by offering both as pluggable storage engines behind the same query interface, letting an operator choose per table based on that table's specific access pattern rather than committing the whole database to one trade-off, which is itself an acknowledgment that no single structure is right for every workload a real system will encounter. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Durability: the WAL. Durability: the WAL. Design a write-ahead log.. Explain the write-ahead-log durability rule and the ARIES three-pass recovery protocol, and design a checkpoint strategy that bounds recovery time.. Crash recovery, Write-ahead logging, Checkpoints, fsync semantics Write-ahead logging The write-ahead log rule is simple to state and easy to violate: before any change to a page is allowed to reach durable storage, a log record describing that change must already be durable. The log is an append-only sequence of records, each carrying at minimum a log sequence number (LSN), the transaction id, the page id modified, and enough information to redo (and, depending on design, undo) the change. Because the log is append-only and sequential, writing it is cheap even on spinning media, which is precisely why engines defer the expensive random writes to data pages and let the buffer pool flush them lazily: durability is bought on the log, not on the data file. Every data page, in turn, stores the LSN of the last log record that modified it, which is the hinge the recovery protocol turns on. Crash recovery The canonical protocol (Algorithm for Recovery and Isolation Exploiting Semantics (ARIES), as used by nearly every serious engine) recovers in three passes. Analysis scans the log forward from the last checkpoint to reconstruct the set of transactions that were active at crash time and the set of pages that may have been dirty, without touching the data files. Redo then replays history: starting from the earliest LSN found relevant in analysis, every logged change whose LSN is greater than the current page's stored LSN is reapplied, repainting the database to exactly the state it was in at the instant of the crash, including the effects of transactions that later abort. This is essential and non-obvious: redo does not distinguish committed from uncommitted work, because reconstructing an unambiguous past state is a prerequisite to correctly undoing anything. Undo then walks backward and rolls back every transaction that was not committed at crash time, itself writing compensating log records (CLRs) so that if a second crash happens mid-undo, recovery never repeats an undo action. Checkpoints A log that is never trimmed grows without bound and makes analysis/redo scan an ever-larger prefix of history. A checkpoint records, at some LSN, the current set of dirty pages and active transactions (a fuzzy checkpoint does this without blocking new writes, tolerating a slightly stale snapshot because analysis will correct it from later log records). Once a checkpoint is durable and all pages dirtied before it are flushed, log records prior to it are no longer needed for redo and can be archived or discarded, bounding recovery time to work proportional to activity since the last checkpoint, not since the database was created. fsync semantics None of this matters if durability claims are not backed by an actual barrier against volatile caches. A write() call returns once bytes are in the OS page cache; only fsync() (or fdatasync, or O_DIRECT|O_SYNC) forces the operating system (OS) to hand the kernel buffer to the storage device, and, critically, and often mishandled, the device must itself not silently cache the write in a volatile disk buffer that a power loss would erase. Group commit exploits the fact that fsync latency is roughly constant regardless of bytes flushed: batching several transactions' log records into one fsync call amortizes the fixed cost across many commits, trading a few milliseconds of added commit latency for an order-of-magnitude gain in commit throughput. A transaction may only report success to its caller after its commit log record's fsync has returned; skip this and you have a cache, not a database. Torn pages and checksums A page write that is interrupted partway, by a power loss or an OS crash mid-write, can leave a page on disk that is neither the old version nor the new one but a torn mixture of both, since a page is typically larger than the atomic write guarantee most storage hardware actually provides. Engines defend against this with a page checksum computed over the whole page and verified on every read, catching a torn page immediately rather than letting corrupted data silently propagate into a query result, and some engines additionally log a full-page image the first time a page is modified after a checkpoint specifically so that a torn page can be reconstructed from the log rather than merely detected. Backup and point-in-time recovery A write-ahead log that is archived rather than discarded after each checkpoint enables point-in-time recovery: starting from a base backup taken at some past instant, replaying the archived log forward reconstructs the database as it existed at any later instant covered by the archive, including the moment just before an accidental deletion or a bad schema migration. This is a different guarantee from crash recovery, which restores the database to its last consistent state automatically; point-in-time recovery is a deliberate operator action that depends entirely on the log archive and the base backup both having been retained and verified as restorable well before they are ever actually needed. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Concurrency: MVCC. Concurrency: MVCC. Implement multi-version concurrency control.. Explain how MVCC constructs a transaction snapshot, and identify a write-skew anomaly that snapshot isolation permits but serializability would prevent.. Snapshots, Versions, Garbage collection, Isolation from MVCC Snapshots Multi-version concurrency control (MVCC)'s central move is to stop making readers and writers fight over the same physical copy of a row. Instead, every transaction is assigned a logical timestamp (often simply a monotonically increasing transaction id or a hybrid logical clock) at the moment it begins, and that timestamp defines its snapshot: the set of versions visible to it, namely the latest version of each row committed before the transaction started, ignoring anything committed later. Constructing a snapshot cheaply is the whole trick: rather than copying data, the engine keeps a compact record of which transaction ids were in-flight (not yet committed) at snapshot time, and a version is visible if its creating transaction committed before the snapshot and is not in that in-flight set. Versions Each row is stored not as a single value but as a chain of versions, each tagged with the transaction id (or timestamp) that created it and, once superseded, the id that deleted/replaced it. A write never overwrites a version in place; it inserts a new version and links it to the previous one (Postgres stores successive versions as separate heap tuples chained by ctid-like pointers; other engines keep an explicit undo/version chain separate from the primary data, reconstructing old versions on demand by replaying undo records). A reader walks the chain from the newest version backward until it finds the newest one visible to its snapshot. This is what makes MVCC's headline property possible: readers never block writers and writers never block readers, because a reader consulting an old version and a writer creating a new version touch different physical records. Garbage collection Versions are not free. Every update leaves behind an old version that is dead weight the instant no active snapshot can still see it, i.e., once no in-flight transaction has a snapshot timestamp older than the version's superseding commit. A vacuum, or garbage collection (GC), process must periodically compute the oldest snapshot still active across all transactions (the watermark) and reclaim every version older than it. Failure to do this promptly is the classic MVCC pathology: a single long-running transaction (a reporting query left open for hours, or a forgotten idle connection holding a snapshot) pins the watermark, and the version chain for hot rows grows unbounded, degrading every subsequent read that must walk past dozens or thousands of dead versions to find the visible one: table bloat and query slowdown that looks like an unrelated performance bug until traced to snapshot pinning. Isolation from MVCC MVCC directly implements snapshot isolation: all reads within a transaction see one consistent point-in-time view, so no read ever observes a torn intermediate state and repeated reads of the same row within a transaction are stable. Snapshot isolation is not, however, full serializability: it permits the write skew anomaly, where two transactions each read overlapping data, each independently satisfy an invariant given what they saw, and both commit, but the combined result violates the invariant (the canonical example: two on-call doctors each check that at least one other doctor is on call before taking themselves off; both see the other as on call and both go off duty). Serializable snapshot isolation (SSI), as implemented in Postgres's SERIALIZABLE level, detects these dangerous read-write conflict cycles at commit time and aborts one transaction, recovering serializability at the cost of occasional aborts under contention. Deadlock versus write skew A deadlock and a write-skew anomaly are easy to conflate but structurally different: a deadlock is a cycle of transactions each waiting on a lock held by the next, detected and resolved by aborting one participant before either commits, while write skew is a cycle of logical dependency between transactions that never actually wait on each other or take conflicting locks, and both commit successfully before the resulting inconsistency becomes visible. This is precisely why locking alone does not prevent write skew: each transaction in the on-call example reads a row it never writes and writes a row the other transaction never touches, so no lock conflict ever occurs, and only a mechanism aware of the logical read-write dependency, such as serializable snapshot isolation's conflict detection, can catch it. Vacuum tuning in practice An under-tuned vacuum process, one that runs too infrequently or is starved of I/O bandwidth relative to the rate dead versions accumulate, lets table bloat grow faster than it is reclaimed, degrading every scan that must walk past accumulating dead versions to find the current one. Operators tune this by monitoring the gap between the oldest active snapshot and the current transaction id, alerting when that gap grows unusually large, since a large gap is the direct symptom of exactly the long-running-transaction pathology this module's garbage-collection material warns about, and by scheduling vacuum aggressively enough that it keeps pace with the write rate rather than treating it as a low-priority background task. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Buffer pool and capstone. Buffer pool and capstone. Manage the buffer pool; assemble the engine.. Explain buffer-pool eviction policies and their failure modes, and design an I/O batching strategy that preserves the WAL-before-data-page invariant.. Buffer pool, Eviction, I/O batching, Putting it together Buffer pool Every structure covered so far (B-tree nodes, log-structured merge (LSM) SSTable blocks, write-ahead log (WAL) segments, version chains) ultimately resolves to pages read from and written to disk, and re-reading a page from disk on every access would make even a well-designed engine unusably slow. The buffer pool is a fixed-size in-memory cache of pages, addressed by page id through a hash table (or similar index) that maps page id to a frame. A page fetch first checks the buffer pool; on a hit, it returns the frame directly with no I/O; on a miss, it selects a victim frame, writes it back to disk if dirty, reads the requested page into the freed frame, and updates the index. Every access takes a pin (reference count) on the frame for its duration so that eviction logic never reclaims a page mid-use, and pages are marked dirty on any in-memory modification so the eviction path knows whether a write-back is required before reuse. Eviction With a pool smaller than the working set, the eviction policy determines the hit rate, and naive least recently used (LRU) eviction is a well-known trap for database workloads: a single large sequential scan (a full-table scan or an ETL job) floods the pool with pages used exactly once, evicting the actually-hot working set that recurring transactional queries depend on: this is sequential flooding. Real engines use scan-resistant policies: least recently used, K-th reference (LRU-K) tracks the K-th most recent access rather than the most recent, so a page touched once during a scan doesn't look 'recently used'; the clock algorithm approximates LRU cheaply with a reference bit and a sweeping hand; 2Q and adaptive replacement cache (ARC) maintain separate recency and frequency queues and adaptively balance between them. The right choice is workload-dependent, but the failure mode to design against is always the same: don't let one query's access pattern evict another query's steady-state working set. I/O batching A buffer pool that issues one syscall per page is leaving throughput on the table. Read-ahead detects sequential access patterns (as in a range scan or an extract-transform-load (ETL) job, or a compaction merge) and issues larger batched reads before they're requested, hiding latency behind computation. On the write side, the pool defers dirty-page write-back to a background flush thread rather than synchronously writing on every modification (durability is instead guaranteed by the WAL, per BEDROCK-LO-02: the page can be behind the log because redo can always reconstruct it), and that flush thread coalesces writes to adjacent pages into larger sequential I/Os wherever the underlying allocation makes it possible, and throttles itself against a checkpoint target so recovery time stays bounded. Putting it together A minimal storage engine is the composition of every module in this course, in dependency order: a page abstraction and either a B-tree or an LSM tree (BEDROCK-LO-01) built on top of a buffer pool (this module) for in-memory page access, guarded by a write-ahead log (WAL, this course's learning objective (LO) 2) so that buffer-pool pages can safely lag durable state, with row versions and a transaction manager (this course's LO 3) layered on top so concurrent transactions get correct isolation without blocking each other. The dependency direction matters for correctness, not just architecture diagrams: the buffer pool must never evict a dirty page whose WAL record hasn't reached disk (the WAL-before-data-page invariant), and the transaction manager must never let a reader see a version whose creating transaction's commit record isn't itself durable. Assembling these into one engine and subjecting it to concurrent load plus injected crashes is the only real test that the individual pieces were built with the right invariants, not just the right APIs. Direct I/O and the buffer pool Some engines bypass the operating system (OS) page cache entirely for data-file I/O, using O_DIRECT to read and write straight to and from the storage device, on the reasoning that a database-managed buffer pool already knows far more about page access patterns than a generic OS cache can infer, and double caching the same page in both the OS cache and the buffer pool wastes memory without improving hit rate. The trade-off is that direct I/O forfeits the OS's own read-ahead and write coalescing, so an engine choosing this path must implement its own equivalents, exactly the read-ahead and write-coalescing behaviour this module describes, rather than relying on the kernel to provide them implicitly. Crash-consistent write-back Writing back a dirty page is not simply a performance operation; it must preserve the WAL-before-data-page invariant even under a crash mid-write-back, which is why the flush thread checks a page's stored log sequence number (LSN) against the durable log position before allowing the write-back to proceed, refusing to flush a page whose corresponding log record has not yet reached disk. A flush thread that ignored this ordering could write a data page reflecting a change whose log record was subsequently lost to a crash, leaving the data file ahead of the log rather than behind it, which is precisely the state the recovery protocol in this course's earlier module assumes can never happen. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/)