## Design a Write-Ahead Log Writer with Batch Writes Design the low-level behavior of a write-ahead log writer that accepts records from concurrent callers and persists them in batches. The exact record format, durability acknowledgement, storage API, and batch atomicity are not supplied, so define them before choosing synchronization and I/O behavior. ### Part 1 — Define Ordering and Durability Specify what an append means, when it is acknowledged, and what recovery may observe after a crash. #### What This Part Should Cover - A monotonic log position or sequence assigned under a documented ordering rule. - The distinction among copying into memory, writing to the operating system, and reaching durable storage. - Whether a batch is atomic, whether a durable prefix is acceptable, and how callers learn the result. - The relationship between WAL durability and applying the corresponding state change. ```hint Name the acknowledgement boundary “Written” is ambiguous until the contract says whether data reached a process buffer, the kernel, or durable media. ``` ### Part 2 — Frame Records and Form Batches Design the in-memory queue, batch trigger, on-disk framing, and group-commit path. #### What This Part Should Cover - Lengths, versions, sequence information, and checksums needed to parse records safely. - Maximum batch bytes, maximum record count, and maximum wait time. - One owner for file position and flush ordering, or another synchronization design with equivalent guarantees. - Result delivery to every caller whose record joined a batch. ```hint Make one component own append order If several threads assign offsets and issue writes independently, completion order can disagree with the order recovery expects. ``` ### Part 3 — Recover from Partial Writes and Crashes Explain startup scanning and how the writer distinguishes a valid prefix, a torn tail, and corruption in previously acknowledged data. #### What This Part Should Cover - Validation of record boundaries, checksums, and sequence continuity. - A safe response to a truncated final record or incomplete batch. - A stricter response to corruption before the recoverable tail. - Reopening the file at the correct append position without reusing log positions. ```hint Treat the tail differently from the middle A crash can plausibly leave the final write incomplete; silently skipping corruption inside an acknowledged prefix can conceal data loss. ``` ### Part 4 — Handle Load and Failure Address backpressure, slow storage, flush failures, shutdown, and verification of the concurrency contract. #### What This Part Should Cover - Bounded queue memory and an explicit overload policy. - Timeouts and error propagation without acknowledging uncertain durability as success. - Graceful shutdown that stops admission and resolves every accepted append. - Metrics and tests for batch size, queue delay, write latency, flush latency, short writes, crashes, and concurrent appends. ```hint Preserve uncertainty After an I/O timeout or process failure, the correct state may be unknown; converting that state into a clean success or clean retry can duplicate or lose logical work. ``` ### What a Strong Answer Covers - A precise ordering and durability contract. - Deterministic record framing and single-owner group commit. - Recovery that accepts only a valid prefix and handles an incomplete tail safely. - Bounded resource use, honest failure propagation, and crash-oriented tests. ### Follow-up Questions 1. How does group commit change latency and throughput as load varies? 2. What should happen to callers when `fsync` succeeds but the process crashes before delivering acknowledgements? 3. How would segment rotation preserve sequence and recovery guarantees? 4. Which guarantee would you relax first for a workload that tolerates limited data loss?