Loading page…
Master the fundamental concepts of storage fundamentals through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksA database page write is not durable until bytes reach non-volatile media. fsync on a file descriptor blocks until prior writes for that file are stored. Crash-safe protocols write the log first, sync it, then write data pages so recovery can replay incomplete updates.
Append WAL record, fsync WAL, modify data page, optionally fsync data. On crash after WAL sync, recovery reapplies committed work.
cLoading…
fdatasync skips inode metadata when safeKeep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.
You will simulate ordered writes and show which steps survive a crash at each point. This exercise asks you to implement the WAL-first sync protocol in the starter simulation.
One database update changes two pages: data page 5, and index page 2, which points at it. Writes go to the OS page cache first. A write is durable only once an fsync that comes after it has finished. Until then a crash may keep or lose that write, in any combination, because the OS reorders write-back.
Compare three ways of doing the update:
| Strategy | Steps | fsyncs |
|---|---|---|
| A (unsafe) | write index page 2; write data page 5 | 0 |
| B (ordered) | write data page 5; fsync; write index page 2; fsync | 2 |
| C (WAL) | append log: page 5, then page 2; fsync log; write data page 5; write index page 2 | 1 |
Simulate a crash after the first K steps, and judge the worst case. The update is inconsistent when the new index can survive while the new data is not yet durable: the index then points to garbage. If the log record is durable (C after its fsync), recovery replays it and the result is consistent whatever happened to the pages.
Group commit is why WAL wins: n transactions need 2n fsyncs with B and n with C, but only one when C batches their log records into one fsync.
Commands until the end of input:
A K, B K or C K: run that strategy and crash after K steps. A K larger than the number of steps means the whole update finished.group N: the fsync counts for N transactions.For a strategy, strategy B, crash after 1 of 4 steps, then each step numbered, with (not reached) after steps past the crash:
cLoading…
then the verdict:
recovery: replay log -> data and index rewritten and consistent=yesworst case: index page 2 survives, data page 5 is lost and consistent=no (index points to garbage)consistent=yesand finally fsyncs=N, the strategy's total fsync count, including steps not reached.
For group N: group of 10 transactions: B=20 fsyncs, C=10 fsyncs, C with group commit=1 fsync.