Deserializing Graphs from Files

The "Zero-Copy" Read with mmap

When loading large files, traditional methods like fread involve multiple steps: the operating system reads data from the disk into a kernel-space buffer, and then your program must copy that data from the kernel buffer into your user-space variables. For a multi-gigabyte index file, this copy is pure overhead.

Memory mapping for reading elegantly sidesteps this. By mapping a file into your process's virtual address space, you get a pointer to the file's contents. The OS's virtual memory manager handles loading pages from the file into physical RAM on-demand as you access them. This is the same highly optimized mechanism it uses for memory swapping. The result is that you don't need to issue explicit read calls or perform a bulk copy; the data is simply there when you need it.

From Offsets to Pointers: Pointer Swizzling

Our serialized file contains data, but it doesn't contain pointers. Memory addresses are ephemeral; a pointer to a data structure at address 0x7ffc... in one program run will be at a completely different address the next time. Storing raw pointers to a file is meaningless.

In the last lesson, we solved this by "unswizzling" our pointers. Instead of storing memory addresses for neighbor connections, we stored their stable uint64_t node indices. Now, during loading, we must perform the reverse operation: pointer swizzling. We will read these indices and use them to reconstruct the navigable graph structure.

Fortunately, our in-memory HNSWNode design already stores neighbor connections as an array of indices (uint64_t* ids), not raw pointers (HNSWNode**). This simplifies our swizzling process immensely. We don't need a complex secondary step to resolve IDs to pointers; we just need to load the IDs into the correct in-memory structures. The "swizzle" to a real pointer happens dynamically during graph traversal whenever we access &hnsw->nodes[neighbor_id].

Implementing the hnsw_deserialize Function

Let's walk through the implementation of our loading function. Its signature will be HNSW* hnsw_deserialize(const char *filename);. It will return a pointer to a newly allocated and fully initialized HNSW struct, or NULL on failure.

1. Open and Map the File

First, we open the file read-only, get its size, and map it into memory.

#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

HNSW* hnsw_deserialize(const char *filename) {
    int fd = open(filename, O_RDONLY);
    if (fd == -1) {
        perror("open");
        return NULL;
    }

    struct stat sb;
    if (fstat(fd, &sb) == -1) {
        perror("fstat");
        close(fd);
        return NULL;
    }
    size_t file_size = sb.st_size;

    // Map the file for reading.
    // PROT_READ: We only need to read from the map.
    // MAP_PRIVATE: Changes are not written back. This is a private copy-on-write mapping.
    void *map_ptr = mmap(NULL, file_size, PROT_READ, MAP_PRIVATE, fd, 0);

    // The file descriptor can be closed immediately after a private mapping is created.
    close(fd);

    if (map_ptr == MAP_FAILED) {
        perror("mmap");
        return NULL;
    }
    
    // ... rest of the function ...
}

Note the use of MAP_PRIVATE. Unlike the serialization step where we needed MAP_SHARED to propagate our writes, here we are only reading. MAP_PRIVATE tells the OS that we don't intend to modify the underlying file, which is safer and allows us to close the file descriptor right away.

2. Validate Header and Allocate Memory

Next, we validate the file header and, if it's correct, allocate the necessary memory for our live HNSW struct and its internal data pools.

    // Cast the start of the map to our header struct
    HNSWFileHeader *header = (HNSWFileHeader *)map_ptr;

    // Basic validation
    if (header->magic != HNSW_MAGIC || header->version != HNSW_VERSION) {
        fprintf(stderr, "Error: Invalid file format or version.\n");
        munmap(map_ptr, file_size);
        return NULL;
    }

    // Allocate the HNSW struct and its associated memory pools
    // (This would call the init functions we built in earlier modules)
    HNSW *hnsw = hnsw_create(header->vector_dim, header->M, header->ef_construction, header->num_vectors);
    if (!hnsw) {
        munmap(map_ptr, file_size);
        return NULL;
    }
    
    // Manually set num_vectors and entry_point as they are already known
    hnsw->num_vectors = header->num_vectors;
    hnsw->entry_point_id = header->entry_point_id;

3. Copy Vector Data

The vector data is stored as a single, contiguous block in the file. We can copy it into our vector memory pool with a single memcpy.

    // Get a pointer to the start of the vector data in the mapped file
    void *vector_data_ptr = (char *)map_ptr + header->offset_vectors;

    // Calculate total size of vector data
    size_t vector_data_size = hnsw->num_vectors * hnsw->vector_dim * sizeof(float);
    
    // Bulk copy into our allocated vector memory
    memcpy(hnsw->vectors_data, vector_data_ptr, vector_data_size);

This is extremely fast. Because the file is memory-mapped, the memcpy triggers the OS to page in the required data from disk directly into our destination buffer.

4. Reconstruct the Graph Structure

This is the swizzling step. We iterate through each node, find its corresponding data in the mapped file, and use it to populate the connections in our in-memory HNSWNode structs.

    // Pointer to the beginning of the graph data section in the file
    char *graph_data_ptr = (char *)map_ptr + header->offset_graph;
    
    // The node offset table is at the start of this section
    uint64_t *node_offset_table = (uint64_t *)graph_data_ptr;

    for (uint64_t i = 0; i < hnsw->num_vectors; ++i) {
        HNSWNode *node = &hnsw->nodes[i];
        
        // Find the start of this node's data in the file using the offset table
        char *packed_node_ptr = graph_data_ptr + node_offset_table[i];

        // 1. Read the max_layer for this node
        node->max_layer = *((uint8_t *)packed_node_ptr);
        packed_node_ptr += sizeof(uint8_t);
        
        // 2. Read the connections for each layer
        for (int l = 0; l <= node->max_layer; ++l) {
            HNSWNodeLayer *layer = &node->connections[l];

            // Read the number of connections on this layer
            uint16_t count = *((uint16_t *)packed_node_ptr);
            packed_node_ptr += sizeof(uint16_t);

            layer->count = count;
            
            if (count > 0) {
                // Allocate space for the connection IDs in our memory arena
                layer->ids = arena_alloc(&hnsw->arena, count * sizeof(uint64_t));
                // NOTE: Here you should check for allocation failure.
                
                // Copy the block of neighbor IDs from the file to our new array
                memcpy(layer->ids, packed_node_ptr, count * sizeof(uint64_t));
                packed_node_ptr += count * sizeof(uint64_t);
            } else {
                layer->ids = NULL;
            }
        }
    }

This process effectively rebuilds the entire graph linkage. The choice to serialize the graph structure directly pays huge dividends here. The alternative would be to re-insert every vector one-by-one, re-running the expensive search and neighbor selection process for millions of items.

5. Final Cleanup

Finally, unmap the file and return the completed HNSW object.

    // We are done with the memory-mapped file, so we can release it.
    if (munmap(map_ptr, file_size) == -1) {
        perror("munmap");
        // The HNSW object is still valid, but this is an issue.
        // For robustness, you might want to free hnsw and return NULL.
    }

    return hnsw; // Success!

Conclusion

You have now implemented the full cycle of persistence for your vector database. By using mmap for both writing and reading, you've created a highly efficient mechanism for saving and loading the entire graph structure. This is a hallmark of high-performance, systems-level engineering.

Key Takeaways:

• Deserialization with mmap: Using mmap with PROT_READ and MAP_PRIVATE provides a "zero-copy" way to access file data, letting the OS efficiently page data into memory on demand.
• Pointer Swizzling: You transformed on-disk, position-independent data (node indices) back into a live, navigable in-memory data structure.
• Reconstruction vs. Rebuilding: Loading the pre-computed graph structure is orders of magnitude faster than rebuilding the index from scratch, a critical feature for any practical database.
• Data Validation: Checking file headers (magic numbers, versions) is a simple but crucial step for building robust systems that can handle corrupted or incompatible files.

With both serialization and deserialization complete, our database is becoming durable. However, there's a lingering question: what happens if the application crashes in the middle of an insertion, after the graph is partially modified but before it's serialized again? The database would be left in an inconsistent state. In our next lesson, we will address this by implementing a Write-Ahead Log (WAL), a standard database technique to ensure atomicity and recover from crashes.