Design a Write-Ahead Log Writer with Batch Writes

Problem Statement

In distributed storage engines and databases, synchronous disk I/O (fsync) for every incoming transaction creates severe write bottlenecks. To achieve high write throughput while maintaining ACID durability guarantees, engines rely on a Write-Ahead Log (WAL) that combines monotonic ordering, group commit (batching), and checksummed framing.

Design and implement a concurrent WALWriter that allows multiple producer threads to append byte records concurrently while a background worker flushes and syncs them to persistent storage in bounded batches.

Record Framing

Every record on disk must be framed as follows:

• length: 4 bytes (unsigned big-endian int), representing the payload size N
• lsn: 8 bytes (unsigned big-endian int), monotonically increasing log sequence number (0-indexed)
• crc32: 4 bytes (unsigned big-endian int), CRC-32 checksum calculated over the payload
• payload: N bytes of raw data

Component Requirements

1. Concurrent Appends: append(payload: bytes) -> Future[int]

   • Assigns the next sequential 64-bit LSN immediately upon ingestion.
   • Appends to an in-memory batch buffer without blocking other writers.
   • Returns a future/promise that resolves to the assigned LSN only after the batch containing this record is persisted to disk and os.fsync (or equivalent) has completed.
   • Applies backpressure: if total buffered uncommitted records exceed max_uncommitted_records, append must block until space is available.

2. Group Commit Flush Criteria:

   • Flush immediately if buffered batch size exceeds max_batch_bytes.
   • Flush if max_delay_ms has elapsed since the earliest buffered write in the current batch.

3. Recovery: recover(path: str) -> list[tuple[int, bytes]]

   • Scans the log file from the beginning, validating framing, record length, and CRC-32.
   • Stops reading at the first corrupted record or incomplete tail write (torn write). Records prior to the torn tail are returned. Any corrupted tail must be cleanly truncated.

4. Graceful Shutdown: close()

   • Flushes and syncs all buffered writes, resolves pending futures, and closes file handles.

Interface

from concurrent.futures import Future
from typing import List, Tuple

class WALWriter:
    def __init__(self, file_path: str, max_batch_bytes: int = 64 * 1024, max_delay_ms: float = 10.0, max_uncommitted_records: int = 10000):
        pass

    def append(self, payload: bytes) -> Future: # Resolves to int (LSN)
        pass

    def close(self) -> None:
        pass

    @classmethod
    def recover(cls, file_path: str) -> List[Tuple[int, bytes]]:
        pass

Constraints

• 0 <= len(payload) <= 16 * 1024 * 1024 (16 MiB max record size).
• Must handle concurrent calls from arbitrary numbers of worker threads safely without data corruption or interleaving bytes.
• Durability acknowledgment must never be signaled early: futures cannot resolve before fsync completes.