Implementing a Write-Ahead Log (WAL)

The "Why" of Write-Ahead Logging

At its heart, a WAL decouples the acknowledgment of an operation from the complex and potentially slow process of updating main data structures. Instead of waiting to modify the HNSW graph and then serialize the whole thing to disk, we perform a very fast, sequential write to a separate log file.

This process provides two major benefits:

1. Durability: It ensures that once an operation is logged and acknowledged, it will not be lost, even in the event of a crash.
2. Performance: Appending to a log file is a sequential disk operation, which is significantly faster than the random I/O patterns that might be required to update complex data files on disk. This allows the system to confirm writes to the client very quickly.

The following diagram provides an excellent high-level overview of this flow. A transaction (like our vector insertion) is first written to a WAL buffer and flushed to the WAL file on disk. Only after this flush is complete is the operation acknowledged. The actual data files are updated later, often in the background.

To understand the core concept more deeply, let's watch a short segment from Arpit Bhayani.

Durability is Not Free: The Role of fsync

You might think that writing to a file using standard library functions like fwrite or fprintf makes the data safe. However, modern operating systems heavily buffer disk I/O for performance. When your program issues a write, the OS typically copies the data to an in-memory kernel buffer and returns immediately, planning to write the data to the physical disk later at a more convenient time. If a power failure or kernel panic occurs before this happens, the data in that buffer is lost forever.

To build a truly durable system, we need to explicitly tell the OS: "Take the data for this file and write it to the physical storage device now. Do not return until it is verifiably safe." In the POSIX world, this is accomplished with the fsync system call.

#include <unistd.h>
int fsync(int fd);

Calling fsync on a file descriptor fd flushes all of its buffered data to the underlying device. It is a blocking call and can be relatively slow, as it may involve physical disk seeks and writes. However, its successful completion is our guarantee of durability.

Designing Our WAL

For our vector database, the primary operation we need to make durable is vector insertion. Let's design the data structures for our log.

1. The Log Entry

Each record in our WAL file needs to contain all the information necessary to reconstruct an insertion operation during recovery. A good design is to have a fixed-size header followed by variable-size data.

#include <stdint.h>

// Define the types of operations our WAL can log. For now, just INSERT.
typedef enum {
    WAL_OP_INSERT = 1,
} WALOperationType;

// The header for every entry in the WAL.
// We use __attribute__((packed)) to ensure no padding is added by the compiler,
// giving us direct control over the on-disk layout.
typedef struct __attribute__((packed)) {
    uint32_t crc;         // CRC32 checksum of the rest of the entry (type + payload).
    uint64_t entry_size;  // Total size of the entry (header + payload).
    WALOperationType type;    // The type of operation.
} WALEntryHeader;

// The specific payload for an INSERT operation.
typedef struct __attribute__((packed)) {
    uint64_t vector_id;   // The ID of the vector being inserted.
    // The vector data will immediately follow this struct in the file.
} WALInsertPayload;

• crc: A checksum, like CRC32, is vital. When we read the log back during recovery, we can re-calculate the checksum and compare it to the stored value. If they don't match, the entry is corrupt (e.g., due to a partial write during a crash), and we know to discard it.
• entry_size: Storing the size of each entry is crucial. It allows a reader to easily find the beginning of the next entry by simply skipping entry_size bytes forward, even without understanding the entry's contents.
• type: An enum to identify the operation. This makes the WAL extensible for future operations like DELETE or UPDATE.
• WALInsertPayload: The specific data for the operation. For an insert, this is the vector's ID. The actual floating-point vector data will be written immediately after this payload structure.

This design is inspired by common database practices. The GitHub Gist below shows a similar C++ implementation that you can review for another perspective.

2. The Log File

The WAL itself will be a single file on disk (e.g., db.wal). We will simply append serialized log entries to the end of this file. The structure will look like this:

[Entry 1 Header | Entry 1 Payload | ... | Entry N Header | Entry N Payload]

Implementing the WAL Append

Now, let's integrate this into our hnsw_insert workflow. The core idea is to wrap the HNSW modification in a function that first performs the durable WAL write.

The new hnsw_insert function will look like this:

int hnsw_insert(HNSW* hnsw, uint64_t id, float* vector) {
    // Step 1: Write the operation to the Write-Ahead Log and ensure it's on disk.
    if (wal_append_insert(hnsw->wal_fd, id, vector, hnsw->vector_dim) != 0) {
        fprintf(stderr, "Failed to write to WAL. Aborting insert.\n");
        return -1;
    }

    // Step 2: ONLY after the WAL write is confirmed, proceed with the
    // in-memory graph modification.
    // ... (existing HNSW insertion logic) ...

    return 0;
}

The magic happens inside wal_append_insert. Here is a step-by-step implementation guide.

#include <unistd.h>   // For write, fsync
#include <fcntl.h>    // For open
#include <string.h>   // For memcpy
#include <zlib.h>     // For crc32

int wal_append_insert(int wal_fd, uint64_t id, const float* vector, uint32_t dim) {
    // 1. Calculate sizes and prepare the payload
    size_t vector_data_size = dim * sizeof(float);
    size_t payload_size = sizeof(WALInsertPayload) + vector_data_size;
    size_t total_entry_size = sizeof(WALEntryHeader) + payload_size;

    // 2. Allocate a temporary buffer for the whole entry
    char buffer[total_entry_size];
    char* ptr = buffer;

    // 3. Construct the entry in the buffer (Header first, but CRC last)
    WALEntryHeader* header = (WALEntryHeader*)ptr;
    header->entry_size = total_entry_size;
    header->type = WAL_OP_INSERT;
    ptr += sizeof(WALEntryHeader);

    WALInsertPayload* payload_header = (WALInsertPayload*)ptr;
    payload_header->vector_id = id;
    ptr += sizeof(WALInsertPayload);

    memcpy(ptr, vector, vector_data_size);

    // 4. Calculate CRC on the entry *without* the CRC field itself
    // crc32 takes an initial value, a buffer, and its length.
    header->crc = crc32(0L, Z_NULL, 0); // Initialize
    header->crc = crc32(header->crc, (const Bytef*)buffer + sizeof(uint32_t), total_entry_size - sizeof(uint32_t));

    // 5. Write the entire buffer to the file descriptor
    // A single `write` is more efficient and more atomic than multiple smaller writes.
    if (write(wal_fd, buffer, total_entry_size) != total_entry_size) {
        perror("write to wal failed");
        return -1;
    }

    // 6. Force the write to physical disk. THIS IS THE CRITICAL STEP.
    if (fsync(wal_fd) != 0) {
        perror("fsync of wal failed");
        return -1;
    }

    return 0; // Success! The operation is durable.
}

This implementation follows the principles of high-performance systems. We prepare the entire entry in an in-memory buffer and issue a single write call to the kernel, which is more efficient than many small writes. The final fsync call is our contract with the OS that this data is now safe.

For more advanced insights into high-performance WAL implementation, the AutoMQ blog has a great article. While it discusses Java and raw devices, its core principles on batching, alignment, and data structures are highly relevant.

Conclusion

In this lesson, you have designed and laid out the implementation for a Write-Ahead Log, a cornerstone of database durability. By logging the intent of an operation to a durable file before executing it, we protect our system against data loss from unexpected crashes.

Key Takeaways:

• WAL Principle: Log changes to a durable, append-only file before applying them to the main data structures.
• True Durability: Standard file writes are buffered by the OS. The fsync() system call is necessary to force data to be physically written to disk, providing a guarantee against data loss on crash.
• Log Entry Design: A robust log entry includes a checksum (like CRC32) for integrity verification, its total size for easy traversal, the operation type, and the operation-specific payload.
• Integrated Workflow: The WAL is not a standalone component; it must be integrated into the data modification path, acting as a gatekeeper that ensures durability before allowing in-memory structures to be changed.

With this logging mechanism in place, our database can now survive a crash. But a log is useless without a way to read it. In our next lesson, we will complete the picture by implementing the recovery routine. This process will run on startup, read the WAL, and replay any logged operations that haven't yet been incorporated into the main serialized graph file, restoring the database to a perfectly consistent state.