The question this layer answers
How is data modeled, stored, queried, protected, and recovered?
Durable, queryable state. This layer connects Pages, Indexes, Query planners, Transactions, Storage engines to the rest of the computing stack.
Data structure and transaction answer different questions
A database must locate information efficiently and keep its promises through concurrency and failure. An index helps answer “where is the row?” A transaction helps answer “which changes become visible and durable together?” Adding an index does not prevent an application race by itself.
For a library, distinguish a book title from its physical copies. A title has descriptive information; each copy has a unique identifier and its own availability. A reservation references a copy and a reader. Storing a single available flag on the title loses the distinction between several copies and makes the invariant harder to state.
Make the check and change one database operation
An illustrative SQL pattern is:
UPDATE copies
SET reserved_by = :reader_id
WHERE id = :copy_id AND reserved_by IS NULL;
Inspect the affected-row count: one row means this statement claimed an available copy; zero means it did not. Authenticate and authorize the caller separately. If other rows must change with this update, enclose the whole operation in a transaction and handle errors. Exact locking, isolation, and retry behavior depend on the database and transaction mode.
Compare that with reading availability in one unprotected request and updating in another. Two callers may both read “available” before either writes. A correct schema, constraint, or atomic conditional update lets the database arbitrate competing claims at the shared boundary.
Reason about crashes with a deliberately small log model
Assume a teaching system never writes uncommitted data pages to durable storage, records intended changes in a durable log, and acknowledges commit only after the required log records and commit record are durable. Pages may be written later. On recovery, committed changes can be replayed; transactions without a durable commit record are ignored.
| Crash point | Recovery conclusion |
|---|
| Before durable commit record | Transaction is not committed in this model |
| After durable commit, before data pages | Replay committed changes |
| After durable commit, before response | Transaction committed; client may be uncertain |
Real recovery systems may also need undo, checkpoints, page identifiers, and explicit durability guarantees from storage. The model is useful because its assumptions are visible. Do not infer that every database implements this exact algorithm.
Atomicity is not the whole isolation story
Atomicity concerns grouping changes; isolation constrains interactions among concurrent transactions. Two individually atomic transactions can still violate a cross-row rule at an insufficient isolation level. Serializable execution aims for behavior equivalent to some serial ordering, and applications must be prepared to retry transactions that are rejected to preserve that guarantee.
Practice: in the lab, label which facts the server knows and which facts the client knows after a crash. A committed transaction and an uncertain caller can exist simultaneously. That distinction leads directly to reliable network retry design.
Free Databases & data systems lessons
Storage layout and indexes from first principles
Storage engines group records into pages because devices and caches transfer blocks efficiently. A buffer manager keeps useful pages in memory. A heap file offers simple placement; a B-tree keeps keys ordered with balanced, page-sized nodes; a log-structured design turns updates into sequential writes and later compaction.
An index entry commonly stores the indexed key plus a row locator or primary key. A lookup reads index pages, finds candidate entries, and may fetch table pages to retrieve unindexed columns. A covering index includes everything the query needs, avoiding those extra lookups at the cost of a larger index and heavier writes.
Plans, cardinality, joins, and execution
The planner rewrites expressions, estimates row counts and selectivity from statistics, and compares access paths and join orders with a cost model. Execution operators form a tree or pipeline: scans produce rows, filters discard them, joins combine them, and aggregates reduce them. A wrong cardinality estimate can make a disastrous plan look cheap.
An indexed nested loop can be excellent when the outer side is small and each inner lookup is selective. A hash join can scan both inputs and match through an in-memory hash table, often better for large equality joins. If the build side spills, memory and I/O change the tradeoff.
Isolation, locking, MVCC, and invariants
Atomicity makes its writes take effect together or not at all. Isolation constrains what concurrent transactions can observe. Locks prevent conflicting access by waiting; multiversion concurrency control lets readers use snapshots while writers create versions. Neither automatically protects a business invariant unless operations and isolation are designed for it.
A reader can see the committed database as of a logical point while a writer creates a newer version. This avoids many read–write conflicts, but old versions must remain while any relevant snapshot can need them. Long transactions can therefore retain storage and delay cleanup.
Logging, recovery, replication, and failure boundaries
With write-ahead logging, relevant log records reach the durability boundary before changed data pages do. After a crash, recovery replays committed work and removes or ignores incomplete work according to the engine’s protocol. Replication creates additional copies, but acknowledgement policy decides which failures those copies can survive without losing accepted writes.
Three asynchronous replicas may all lag an acknowledged primary. A primary failure can therefore lose accepted writes despite four total copies. Quorum or synchronous acknowledgement strengthens that boundary but adds latency and may reduce availability during partitions. The product must choose consciously.
Predict duplicates, missing values, joins, and grouping before optimizing a query.
Separate facts without losing the ability to reconstruct them.
Follow reads and writes through two different indexing strategies.
Manage the boundary between database pages in memory and durable storage.
Choose a physical plan by counting pages and predicting intermediate results.
Distinguish a consistent-looking snapshot from a serial transaction history.
Explain which bytes must survive each crash boundary.
Separate copying data from distributing ownership.
Practice lab: Recover a committed transfer
About 35 minutes. Understand durable versus volatile storage and concurrent operations. A transaction groups changes under stated atomicity and isolation guarantees.
Accounts A and B start at 100 and 50. Transaction T transfers 30 from A to B. Use a simplified redo-only system: uncommitted changes stay out of data pages; a durable log records new values and COMMIT(T). Assume storage honours flush requests. The invariant is A + B = 150.
- Show log records for the transfer and the required order before acknowledging success.
- Recover after a crash with no durable COMMIT, then after a crash with durable COMMIT but stale data pages.
- Two transactions both read A = 100 and each authorise an 80-unit withdrawal. Explain why atomicity of each transaction alone does not prevent overspending.
Hint
The simplified recovery rule is to replay committed new values and ignore incomplete transactions. Real engines may also need undo and checkpoints.
Worked solution
Record T:A=70 and T:B=80, then COMMIT(T); flush the required log before acknowledging success. With no durable commit and no uncommitted data pages, recovery retains A=100, B=50. With durable commit, replay both new values to get A=70, B=80 even if data pages were stale or partially updated. Both preserve the sum. This is a specified redo-only model, not a universal recovery algorithm. Independent atomic withdrawals can still act on stale observations. Use a conditional update under the database’s concurrency guarantees or an appropriate serializable transaction with retry handling to enforce the balance rule.
- Place acknowledgment after the durability boundary.
- Recover both crash cases without a half-transfer.
- Distinguish atomicity from isolation and retry aborted transactions correctly.
Change one assumption
If a replica acknowledges before receiving the durable log, explain what a failover could lose. Name the durability promise before deciding whether that is acceptable.
Query, isolate, and recover the same data
Specify the rows and failure model before choosing an index or isolation level. Work through concrete results and schedules.
1. Evaluate and repair · allow 35 minutes
Bags, NULL, and a disappearing outer join
Customers are (1,Ada),(2,Bo),(3,Cy). Orders are (10,1,20),(11,1,NULL),(12,2,5), with columns (order_id,customer_id,total). Predict rows from a LEFT JOIN followed by WHERE orders.total>10. Repair the query to retain every customer while matching only orders above 10. Then compute COUNT(*), COUNT(order_id), COUNT(total), and SUM(total) per customer for the unrestricted LEFT JOIN. Explain the effect of a duplicate order row.
Get a starting hint
WHERE is applied after the outer join. COUNT(expression) excludes NULL; COUNT(*) counts the null-extended row.
Compare your reasoning with the worked solution
Filtering after the join leaves only Ada with order 10: the predicate is false for total 5 and unknown for NULL, including Cy's null-extended row. Put AND o.total > 10 in the ON condition to keep Ada with order 10 plus Bo and Cy with null order fields.
For the unrestricted join, Ada has COUNT(*)=2, COUNT(order_id)=2, COUNT(total)=1, SUM(total)=20. Bo has 1,1,1,5. Cy has 1,0,0,NULL. SUM over no non-NULL inputs is NULL, so use COALESCE only if the application's meaning genuinely calls for zero. SQL normally preserves duplicate rows: duplicating order 10 increases Ada's counts to 3,3,2 and sum to 40. A primary key on order_id would reject that duplicate rather than silently fixing aggregate semantics. Join multiplicity, constraints, and NULL behavior are separate parts of the query contract.
Check your reasoning
- Distinguish ON filtering from WHERE filtering.
- Compute all four aggregates, including Cy.
- Explain why constraints matter to multiplicity.
2. Dependency reasoning · allow 40 minutes
A decomposition that does not invent enrollments
R(student,course,instructor,office) has dependencies course→instructor and instructor→office. Assume students can take many courses and each course has one instructor. Find a candidate key. Explain an update anomaly. Decompose into Enrollment(student,course), Course(course,instructor), Instructor(instructor,office). Prove this decomposition is lossless under the dependencies. Would splitting into StudentCourse(student,course) and StudentInstructor(student,instructor,office) be safe? Give a counterexample.
Get a starting hint
Use the common attribute as a key on one side at each lossless binary split. For the bad split, give one student two courses with different instructors.
Compare your reasoning with the worked solution
The key is (student,course): course determines instructor and then office, while neither student nor course alone determines all attributes. Repeating an instructor's office across enrollment rows permits inconsistent office updates. First split Instructor from R on instructor; the shared attribute determines every attribute of Instructor. Then split Course from Enrollment on course; course determines Course. Each step is lossless and the dependencies can be checked in their own tables.
For the proposed bad split, let one student S take C1 taught by I1 in O1 and C2 taught by I2 in O2. Joining the two projections on student combines both courses with both instructors, yielding four rows instead of two, including spurious (S,C1,I2,O2) and (S,C2,I1,O1). A projection can preserve all original values yet lose which values belonged together. Losslessness is about reconstructing exactly the original legal relation; dependency preservation is a different property. The good design also needs primary and foreign keys to enforce the intended relationships in an implementation.
Check your reasoning
- Compute a minimal key.
- Use dependencies to justify each join.
- Show the two spurious rows in the unsafe design.
3. Estimate and stress-test · allow 45 minutes
Choose the access path with its actual costs
A relation occupies 1,000 pages. A B+ tree lookup costs three uncached index-page reads; each matching record may require a separate data-page read. Estimate I/O for a predicate matching 10 records and one matching 800 records under this pessimistic unclustered model, versus a full scan. Ignore extra index-leaf scans in this simplified estimate. Join R=100 pages with S=1,000 pages using B=12 buffer pages and block nested loops. Compute cost with either outer relation. Explain how caching, clustering, an LSM tree, and an incorrect cardinality estimate can change the choice.
Get a starting hint
For block nested loops reserve one page for the inner scan and one for output: cost is outer + ceil(outer/(B−2)) × inner. Avoid treating a toy I/O model as a latency benchmark.
Compare your reasoning with the worked solution
The index estimates are 3+10=13 and 3+800=803 page reads, versus 1,000 sequential reads for a scan. The latter comparison does not prove the index is faster: random reads may cost more, and some matching records can share data pages. Cached upper tree levels and clustered records reduce index I/O. For block nested loops, R outer costs 100+ceil(100/10)×1,000=10,100 reads. S outer costs 1,000+ceil(1,000/10)×100=11,000 reads.
An LSM design can turn many updates into sequential writes but adds compaction and may search multiple runs; Bloom filters reject many absent keys but cannot prove a positive match. Buffer reuse changes physical I/O without changing logical accesses. Underestimating output cardinality can select many random lookups where a scan or hash join would be cheaper. Test plans with measured cardinalities, warm and cold cache conditions, write load, and tail latency. These estimates intentionally omit CPU, extra index-leaf scans, output cost beyond the reserved buffer, parallelism, and storage-device behavior.
Check your reasoning
- Use ten outer-block pages, not twelve.
- Calculate both join orientations.
- Separate estimated page reads from observed response time.
4. Schedule and repair · allow 40 minutes
Two valid decisions that violate one invariant
Doctors A and B are both on call. The invariant requires at least one on-call doctor. Each transaction reads both rows and, if the other doctor is on call, sets its own row off call. Construct a snapshot-isolation execution that violates the invariant without a same-row write conflict. Draw the read/write dependency cycle. Give two valid repairs and explain what the application must do after an aborted transaction.
Get a starting hint
Each transaction reads a value that the other later changes. Protect the decision predicate, not only the row being updated.
Compare your reasoning with the worked solution
T_A and T_B take snapshots with A=true and B=true. T_A reads B=true and writes A=false; T_B reads A=true and writes B=false. Since they write different rows, snapshot isolation may allow both commits, leaving nobody on call. T_A's read of B is invalidated by T_B, giving a read/write anti-dependency T_A→T_B. The symmetric read gives T_B→T_A, so there is a cycle inconsistent with any serial order.
One repair is a serializable transaction mode that detects or prevents this anomaly, with retries of the entire transaction after serialization failure. Another is to update a shared guard/version row in every transaction that makes this decision. Under snapshot isolation with same-row write-conflict detection, concurrent transactions then conflict on that row, and the loser must retry the whole transaction from a new snapshot. Merely locking an unchanged guard row is insufficient when a transaction retains an earlier snapshot. A lock-based alternative needs a documented policy that obtains the relevant locks before the decision snapshot and reads fresh state. Merely locking each transaction's own row leaves the cross-row predicate unprotected. Retry must start with fresh reads; replaying only the final UPDATE repeats a decision made from invalid evidence. Bound retries and distinguish contention from permanent business-rule rejection. Isolation names vary by database, so verify the actual engine's documented behavior.
Check your reasoning
- Show distinct writes and both anti-dependencies.
- Protect the cross-row invariant.
- Retry the whole decision from a fresh transaction.
5. Crash analysis · allow 45 minutes
Committed data, durable evidence, and a stale replica
A transaction changes page P from value 7 to 9. Its redo log record has LSN 40 and its commit record LSN 41. The page initially has pageLSN 30. Assume crash-atomic log records, reliable flush acknowledgments, a log protocol that makes records durable in LSN order, and redo-only recovery with no uncommitted data pages written. Analyze crashes: before the commit record at LSN 41 is durable, after durable commit but before page flush, and after page flush. Why must the log be durable before its page? A replica has applied only LSN 38 when a client reads immediately after commit. Design a read-your-writes contract and state its availability trade-off.
Get a starting hint
Separate the commit acknowledgment from the page write. An LSN is useful only with a defined lineage and a replication protocol that preserves it.
Compare your reasoning with the worked solution
Before durable commit, the transaction must not have been acknowledged as durable; recovery can omit it under the stated no-uncommitted-page model. After LSN 41 is durable but P is still at pageLSN 30, replay record 40 to set P=9 and pageLSN=40. After the page has been durably written, replay can skip it because pageLSN≥40. Redo must be idempotent: setting the recorded value or using pageLSN is safer than blindly adding two again. Writing the page before its supporting log risks a persistent state whose recovery history is absent. Real systems with steal policies also need undo or another way to exclude uncommitted changes; this simplified model does not cover them.
Return a commit position or session token and route subsequent reads to the leader or to a replica proven to have applied at least that position in the same history. A replica at 38 cannot yet satisfy a token requiring 41. Waiting, routing elsewhere, or returning a clear unavailable result preserves the contract; returning stale data does not. During a partition, guaranteeing fresh reads can reduce availability. The token alone does not solve divergent histories or unsafe failover.
Check your reasoning
- Distinguish log durability, commit, and page persistence.
- Make replay safe to repeat.
- Specify what happens when no replica can meet the session token.
Study the underlying methods
Section project: Implement a recoverable append-only key-value store
6 to 8 hours. Build a small persistent store to study record framing, indexing, and recovery. Inputs are PUT(key,value), DELETE(key), and GET(key), where keys and values are UTF-8 strings with documented length limits. Maintain an in-memory index rebuilt from an append-only binary log. Each record should contain a length field, operation payload, and checksum so recovery can distinguish a complete valid record from a truncated or corrupted tail. Specify byte order and exactly which bytes the checksum covers. A successful mutation appends its record, flushes user-space buffers, and calls fsync before reporting success. State that this is a simplified durability model subject to filesystem and hardware guarantees. On startup, replay only the valid prefix, report the first invalid offset, and reject or explicitly truncate the suffix according to one documented policy. Use Python standard-library struct, json, zlib, and file operations. Produce a command-line tool, format specification, and crash-test report that truncates logs at every byte boundary in a small fixture. Do not claim that checksums provide authentication or that this exercise implements transactional SQL. Do not scan past a damaged record hoping to recognize later plausible bytes. Explain why trusting only a verified prefix provides a simpler recovery argument than guessing how to resynchronize an untrusted stream.
Milestones
- Define the binary record format, bounds, checksum rule, and recovery policy.
- Implement append, read, delete tombstones, and index reconstruction.
- Implement bounded recovery that rejects impossible lengths before allocating large buffers.
- Generate truncation and byte-corruption fixtures and compare recovered states.
- Document acknowledgement timing and the limits of the durability model.
Acceptance criteria
- After restart, GET returns the most recent complete valid PUT unless a later valid DELETE removed the key.
- Truncating a fixture at every byte offset recovers exactly the prefix of complete valid records preceding that offset.
- A fixture with a single-bit payload corruption is detected by checksum verification and its record is never applied.
- An impossible record length is rejected without allocating memory proportional to the untrusted length.
- Recovery reports the byte offset of the first invalid record and follows the documented suffix policy consistently.
- Mutation acknowledgement occurs only after the configured flush and fsync calls complete successfully.
Add compaction into a new file followed by an atomic replacement, and enumerate crash points to explain which old or new file remains authoritative.
Practise Databases & data systems free →