CSE Roadmap

Common tier · about 2 hours · 5 parts

Part 5 of 5 · 4 min read

Exercises

Easy

Easy 1: Name the problem checkpoints solve (15 minutes)

State, in one sentence, the problem checkpoints exist to solve.

Done when: recovery time growing without bound as the log grows, without a recent safe starting point, is correctly described.

Hint

Recovery time growing without bound over a database's lifetime, since there would be no recent, safe starting point to replay from.

Easy 2: Name what a checkpoint does (15 minutes)

State what a checkpoint does to the buffer pool's dirty pages.

Done when: flushing every dirty page to disk, then recording that fact in the log, is correctly described.

Hint

It flushes every dirty page in the buffer pool to disk, then records that fact as a log entry.

Easy 3: Name what recovery can skip after a checkpoint (15 minutes)

State which log entries recovery needs to consider after finding the most recent checkpoint.

Done when: only entries from the most recent checkpoint onward, skipping everything before it, is correctly named.

Hint

Only log entries from the most recent checkpoint onward; everything before it can be skipped.

Medium

Medium 1: Compare recovery time with and without a checkpoint (25 minutes)

A database crashes five minutes after its most recent checkpoint. Compare how much log recovery needs to replay in this case versus a database with no checkpointing at all that has been running for five years.

Done when: the checkpointed database needing only five minutes of log replayed, versus the non-checkpointed database potentially needing its entire five-year history replayed, is correctly contrasted.

Hint

The checkpointed database needs only about five minutes of log replayed; the non-checkpointed database could need its entire five-year history replayed in the worst case.

Medium 2: Explain the cost checkpointing itself imposes (25 minutes)

Explain what cost a checkpoint imposes during normal operation, separate from its recovery benefit.

Done when: the real I/O cost of flushing every dirty page to disk, which can briefly affect ongoing transaction performance, is correctly described.

Hint

Flushing every dirty page takes real disk I/O, which can briefly slow down ongoing transactions while the checkpoint is happening.

Medium 3: Choose a reasonable checkpoint frequency for a stated workload (30 minutes)

A system has very strict uptime requirements, meaning recovery time after any crash must be kept as short as possible, and can tolerate brief, regular I/O overhead. Decide whether this system should checkpoint more frequently or less frequently, and explain why.

Done when: more frequent checkpointing is correctly chosen, citing the priority on short recovery time and the system's stated tolerance for the resulting regular I/O overhead.

Hint

More frequent checkpointing, since the system prioritizes short recovery time and has explicitly stated it can tolerate the resulting regular I/O overhead.

Hard

Hard 1: Explain why flushing dirty pages, specifically, is what makes a checkpoint safe (30 minutes)

Explain why a checkpoint specifically needs to flush dirty pages to disk, rather than simply writing a log entry claiming a safe point exists without actually flushing anything.

Done when: the explanation correctly notes that the safety of skipping everything before the checkpoint depends on those changes genuinely already being reflected on disk; merely claiming so without actually flushing would leave real, unflushed changes that recovery would incorrectly skip, breaking durability.

Hint

The safety of skipping everything before the checkpoint depends on those changes actually being on disk already; merely recording a claim without flushing would leave real unflushed changes that recovery would wrongly skip, breaking the durability guarantee the checkpoint is supposed to provide.

Hard 2: Explain why a very long-running transaction complicates checkpointing (35 minutes)

Explain why a transaction that has been running, uncommitted, since well before the most recent checkpoint complicates how simply recovery can rely on that checkpoint alone.

Done when: the explanation correctly notes that this transaction's changes might be reflected in flushed, dirty pages at checkpoint time despite never having committed, meaning recovery may still need information from before the checkpoint to correctly undo this specific transaction, rather than being able to ignore everything before the checkpoint unconditionally.

Hint

This transaction's in-progress changes might already be reflected in pages flushed at checkpoint time, despite never having committed, so recovery may still need log information from before the checkpoint to correctly undo it, rather than safely ignoring everything before the checkpoint without exception.

Hard 3: Design a checkpoint policy for a workload with occasional traffic spikes (40 minutes)

A system experiences predictable, scheduled traffic spikes at certain times of day, outside of which traffic is light. Propose how checkpoint timing might be chosen to minimize the real-world impact of this trade-off.

Done when: a reasonable policy is proposed, such as scheduling checkpoints to occur during the light-traffic periods and avoiding them during known traffic spikes, reducing the chance that a checkpoint's I/O cost compounds with an already-heavy load, while still checkpointing often enough overall to keep recovery time bounded.

Hint

A reasonable policy schedules checkpoints during known light-traffic periods and avoids triggering them during predictable traffic spikes, reducing the chance of compounding checkpoint I/O cost with an already-heavy load, while still checkpointing often enough overall to keep worst-case recovery time bounded.