Storage Engines and Index Mechanics

Storage Engines and Index Mechanics

A storage choice must serve the required reads, writes and recovery contract under finite disk and memory budgets. “SQL versus NoSQL” does not explain how an engine finds a key, makes an acknowledgement durable, handles old versions or recovers after a crash. Connect the data model to physical work before adding replicas or shards.

Start with one access pattern

This original exercise stores tenant-scoped delivery records and serves a page of failed deliveries ordered by creation time and unique ID. A query's filtering, ordering and selected columns determine useful access paths. An index that finds candidate IDs is not automatically an index that can answer every requested field without extra I/O.

These are conceptual building blocks, not a claim that all products implement identical structures. PostgreSQL heap/index/WAL behavior and RocksDB run/compaction behavior need their own settings and version-specific documentation.

Work an ordered index traversal

Choose an ascending composite key (tenant_id, state, created_at, delivery_id) for this exercise. Tenant/state form an equality prefix; time/ID bound and order the range. After cursor (T1, failed, 100, D2), the next eligible rows have a lexicographically larger time/ID within that tenant/state. An ID tie-break prevents equal timestamps from making the page boundary ambiguous.

(T1, failed, 100, D1)
(T1, failed, 100, D2)  <- previous page ends here
(T1, failed, 100, D3)  <- next candidate
(T1, failed, 101, D4)
(T1, sent,   100, D5)  <- outside requested state
(T2, failed, 100, D6)  <- outside tenant

In a toy tree with 100 entries per leaf and fanout 100, one million entries require about 10,000 leaves, 100 internal pages and one root: three page levels along a root-to-leaf path. This ignores fill factor, key sizes, headers, splits and cached pages. A range scan also visits the leaves containing the selected range and may fetch separate table pages. Do not present “three levels” as three guaranteed physical I/Os or a latency benchmark.

Random versus append-oriented keys change page locality and split pressure. Extra indexes add write/storage maintenance. The best query plan depends on distribution, selectivity, visibility and actual measured I/O. The lesson's index is not automatically optimal for every tenant's skew or every status filter.

Make acknowledgement and recovery concrete

A write changes logical state and must preserve the engine's required recovery evidence before durable success. In a WAL design, data pages can lag while durable log records permit crash recovery. A transaction can also produce records that never become committed; replay must follow the engine's transaction/recovery rules rather than blindly treating every record as a successful business action.

Original model: checkpoint K has value 10. Transaction X records value 20 and a durable commit, but its data page has not been written when the process crashes. Recovery returns 20 from the committed history. Transaction Y records value 30 but no durable commit; the model must not return 30 as a committed result. Replaying the same eligible position twice must not apply another business increment.

Read the diagram

This simplified model exposes the acknowledgement boundary; real WAL recovery is engine-specific.

View full sizeOpen original

Storage Engines and Index Mechanics

Reset viewClose

Storage Engines and Index Mechanics

A checkpoint reduces recovery work under the engine's protocol; it is not necessarily an independent backup. Checkpoint timing trades background writes and recovery work, and archive/replication consumers may still require older logs. Removing log files merely because local pages are current can break replication or PITR. Recovery also needs compatible artifacts/configuration, encryption keys and an intact required log sequence.

Follow an LSM-style read and update

An LSM-style engine commonly writes to log/memory state, flushes sorted immutable runs and later merges runs. A read resolves the newest visible version across eligible sources; it cannot return the first key found in an arbitrarily older run. Bloom filters can avoid some unnecessary point-read probes but do not establish authorization, transaction order or the correct result by themselves.

Original record history for key K:

If compaction discards the sequence-8 tombstone while an older run still contains K/4, a latest read can resurrect old data. If it removes K/4 while a sequence-7 snapshot still needs it, the snapshot breaks. Reclaim only when the engine's snapshot/history/overlap and any replication/repair requirements permit it. The toy tests retain all history while a snapshot exists; that is a conservative demonstration, not a compaction algorithm recommendation.

Quantify amplification and disk headroom

At 10 MB/s logical ingress and 30 MB/s measured engine writes under a specified measurement boundary, write amplification is 3. State whether WAL, replicas, indexes and device-level effects are included. Comparing a ratio that includes replicated bytes to one that excludes them is misleading.

Read amplification asks how much work is needed per useful result; space amplification compares occupied storage with the chosen logical-live baseline. Compaction can reduce read/space cost while creating additional writes and transient space demand. Different run layouts and compaction strategies choose different trade-offs; “LSM makes writes cheap” omits this background bill.

Suppose a device budget leaves 20 MB/s for engine write work after other workloads and the workload's write amplification is 3. Sustained logical ingress of 10 MB/s needs roughly 30 MB/s at that boundary, so debt accumulates unless capacity, work per event or admission changes. Adding application workers can accelerate the overload.

For an illustrative compaction producing 200 GB of new output while old input remains referenced, a disk with 150 GB free cannot safely assume immediate deletion of the inputs will make it fit. Reserve operational and failure headroom, throttle/pause admission or choose an eligible bounded job. Real engines can stream or divide tasks, but that capability must be verified rather than invented during planning.

Build and change indexes safely

Before an index build/rebuild, inventory lock behavior, temporary space, live write maintenance, transaction age, replica lag and rollback conditions. Build a new generation when required, validate its query semantics and concurrent-change handling, then switch readers under an explicit policy. A successful file build is not evidence that deletes, ACL filters or newest source versions were included.

For a database-native online/concurrent operation, use that product's documented restrictions. A secondary index can accelerate a lookup while still being an asynchronous projection in another system. An index response cannot replace the owner for a last-seat mutation or current privacy decision.

Corruption and restore are part of the design

Checksums can detect a damaged block; they cannot reconstruct lost bytes without another valid source or redundancy scheme. Keep independently protected, tested backups and the log history required for the selected restore point. Restore into an isolated environment, verify representative records/constraints and application behavior, then reconcile external effects and derived indexes. A backup that cannot be decrypted or interpreted by available software is not a usable recovery path.

Observe write stalls, compaction debt, free-space runway, cache behavior, query work per result, long-lived snapshots, WAL/archive lag and restore duration. Track a user-visible objective alongside those internals. The choice between a B-tree-oriented baseline and an LSM-oriented engine should follow this workload and operational burden, not a blanket brand preference.

Check your understanding

Question: Does a three-level index guarantee exactly three physical reads for a page of full records?

Question: May compaction drop a tombstone because the key is currently absent while an older run remains?

Question: X's commit is durable but its page was not flushed; Y has no durable commit. What should the simplified recovered state show?

Transfer exercise and scoring

For Database Indexing, Cassandra and Distributed Blob Store, explain the access path, durable acknowledgement, version/delete retention, amplification budget and tested restore path. Score one point for each concrete mechanism. Show one failure that adding another replica does not repair.

Prerequisites: Data Modeling, Replication, Durability and Failover and SLOs, Observability and Capacity.

Primary references and scope

• PostgreSQL WAL introduction for its log-before-data recovery principle.
• RocksDB overview and Cassandra storage engine for product-specific run/compaction context.

The rows, tree dimensions, recovery states and budgets above are original examples. Repository checks do not implement a production B-tree, WAL, compactor, storage benchmark or backup integration.