WAL Recovery on Startup

The Logic of Crash Recovery

Upon startup, our database faces one of two scenarios: a clean shutdown or a recovery from a crash. In a clean shutdown, we would have had the chance to serialize the entire, up-to-date HNSW graph to our main data file. In a crash scenario, however, the main data file is likely stale, representing the state of the graph at some point in the past. The WAL, on the other hand, contains all the subsequent insertion operations that were successfully committed to disk.

The recovery process bridges this gap. The core logic is:

1. Load the last known-good state of the graph from the main data file.
2. Read the WAL from beginning to end.
3. For each operation in the WAL, apply it to the in-memory graph.
4. Once all valid log entries are replayed, the in-memory graph is now consistent and up-to-date.

This model is a cornerstone of database engineering. The diagram below shows how a Recovery Manager interacts with both the main data files and the WAL files to restore a consistent state.

The PlanetScale engineering blog provides a great real-world example of this process for their vector index.

Implementing a WAL Reader

To replay the log, we first need to read it. Since our WAL is a simple sequence of binary entries, we can't just read it line by line. We need to implement an iterator that understands our entry format: a WALEntryHeader followed by a payload.

This task is fundamentally about careful, sequential file I/O and deserialization. We will read a chunk of data, interpret it as a struct, use the information in that struct (like entry_size) to read the next chunk, and repeat.

Let's design a function wal_read_next that reads a single complete entry from the file. It will handle reading the header, verifying data integrity with the CRC, and then reading the payload. A failure at any step, such as a mismatched CRC or an incomplete read (a "short read"), signifies corruption or a partially written entry from a crash. In such cases, we must stop, as we cannot trust any subsequent data in the log.

Here is a conceptual implementation of the core recovery loop.

// This function is called at the start of your application
void database_recover(HNSW* hnsw, const char* wal_path) {
    int wal_fd = open(wal_path, O_RDONLY);
    if (wal_fd == -1) {
        if (errno == ENOENT) {
            // No WAL file exists, so no recovery needed.
            // This is a clean start.
            printf("WAL file not found. Skipping recovery.\n");
            return;
        }
        perror("Could not open WAL file for recovery");
        exit(EXIT_FAILURE);
    }

    printf("Starting recovery from WAL...\n");
    int entries_replayed = 0;

    while (1) {
        // 1. Read the header
        WALEntryHeader header;
        ssize_t bytes_read = read(wal_fd, &header, sizeof(WALEntryHeader));

        if (bytes_read == 0) {
            // End of file, we're done.
            break;
        }

        if (bytes_read < sizeof(WALEntryHeader)) {
            // Partial read of a header. The WAL is corrupt or ends here. Stop.
            fprintf(stderr, "WARN: Partial header read. Found corrupt WAL entry. Stopping recovery.\n");
            break;
        }

        // 2. Read the rest of the entry (the payload) into a buffer
        size_t payload_size = header.entry_size - sizeof(WALEntryHeader);
        char payload_buffer[payload_size];
        bytes_read = read(wal_fd, payload_buffer, payload_size);

        if (bytes_read < payload_size) {
            fprintf(stderr, "WARN: Partial payload read. Found corrupt WAL entry. Stopping recovery.\n");
            break;
        }

        // 3. Verify CRC
        // The CRC was calculated over the header (minus crc field) and the payload.
        // Let's construct a temporary buffer to do that.
        size_t content_size = header.entry_size - sizeof(uint32_t);
        char content_buffer[content_size];
        memcpy(content_buffer, ((char*)&header) + sizeof(uint32_t), sizeof(WALEntryHeader) - sizeof(uint32_t));
        memcpy(content_buffer + sizeof(WALEntryHeader) - sizeof(uint32_t), payload_buffer, payload_size);

        uint32_t calculated_crc = crc32(0L, Z_NULL, 0);
        calculated_crc = crc32(calculated_crc, (const Bytef*)content_buffer, content_size);

        if (calculated_crc != header.crc) {
            fprintf(stderr, "WARN: CRC mismatch. Found corrupt WAL entry. Stopping recovery.\n");
            break; // Stop at the first sign of corruption
        }

        // 4. If CRC is valid, replay the operation
        if (header.type == WAL_OP_INSERT) {
            WALInsertPayload* insert_payload = (WALInsertPayload*)payload_buffer;
            float* vector_data = (float*)(payload_buffer + sizeof(WALInsertPayload));
            
            // Replay the insert operation using the internal logic
            // We assume an internal function that doesn't trigger another WAL write
            _internal_hnsw_insert(hnsw, insert_payload->vector_id, vector_data);
            entries_replayed++;
        }
    }

    printf("Recovery complete. Replayed %d entries.\n", entries_replayed);
    close(wal_fd);

    // 5. After successful recovery, truncate the WAL file so it isn't replayed again.
    // We open it again in write mode to truncate.
    wal_fd = open(wal_path, O_WRONLY | O_TRUNC);
    if (wal_fd == -1) {
        perror("Failed to truncate WAL file after recovery");
    } else {
        close(wal_fd);
    }
}

This logic of creating a dedicated iterator to read structured data from a file is a common pattern in systems programming. The article below, though written in Rust, demonstrates an almost identical WALIterator structure for reading entries one by one.

Simulating a Crash to Test Recovery

A recovery routine is meaningless if it hasn't been tested. We need to create a scenario where the database state on disk is inconsistent, forcing the recovery logic to run and prove its correctness.

Here is a recipe for a test program:

1. Setup: Delete any existing database files (db.hnsw, db.wal). Create an empty database and serialize it. This gives us a clean starting point.
2. Insert Data: In a new process, load the database and insert several vectors. These insertions will be written to the WAL.
3. Simulate Crash: Terminate this process without calling the clean shutdown logic that would re-serialize the main graph file. Using kill -9 <pid> on Linux is an effective way to do this, as it gives the process no opportunity to clean up.
4. Recover: Start the database application again. The database_recover function should now find the WAL file from the "crashed" run. It will read the entries and replay them into the in-memory HNSW structure.
5. Verify: After recovery, perform a search for one of the vectors that was inserted before the crash. If the search finds it, the recovery was successful. You should also verify that the WAL file has been truncated, ready for new operations.

The video below, while focusing on a Go implementation, walks through this exact testing process: writing data, purposefully corrupting it (another form of crash simulation), and then running a repair/recovery function to verify that the system can restore itself to a valid state.

Conclusion

Today, you have completed the full durability cycle for our vector database. By implementing a recovery routine, you've ensured that the durable log we created in the previous lesson can be used to restore the system to a consistent state after a crash.

Key Takeaways:

• Recovery Logic: The recovery process loads the last known-good snapshot and replays operations from the WAL to bring the in-memory state up to date.
• Integrity is Paramount: The recovery routine must be robust against data corruption. Using checksums (like CRC32) to validate each log entry is non-negotiable. Recovery must halt at the first invalid entry.
• Idempotency: Replaying the log should be an idempotent operation. If an operation from the WAL is already reflected in the main data file, replaying it should not cause errors. Our simple check of whether the vector ID exists handles this.
• Post-Recovery Cleanup: Once recovery is complete, the WAL must be truncated or archived to prevent its operations from being replayed again on the next startup.

You now have a grasp of one of the most fundamental concepts in reliable, high-performance systems. In the final lesson of this module, we will formalize our testing process by writing a dedicated unit test that automates the crash-and-recover cycle, proving the integrity of our implementation.