Serializing Graph State to Memory-Mapped Files

Why Memory-Map for Writing?

In the previous lesson, we designed our file format with offsets in the header pointing to subsequent data sections. If we were to use traditional file I/O like fwrite, we'd run into a classic chicken-and-egg problem: we need to write the header first, but we don't know the final offsets of the data sections until after we've written them.

By mapping the entire file into our process's virtual address space, we can treat it like one large array in memory. We can write data to any location within that array at any time, which means we can populate the data sections first and then easily jump back to the beginning to fill in the header with the correct final offsets. This avoids multiple lseek and write system calls and simplifies the logic considerably.

The mmap Serialization Workflow

To implement our serialization function, we'll follow a clear, five-step process:

1. Calculate Total Size: First, we must determine the exact total size of the file we need. Since our in-memory graph is complete, we can walk through it and sum up the sizes of the header, all vector data, the node offset table, and the packed graph connection data.
2. Create and Pre-allocate File: Using the calculated size, we'll create a new file and immediately extend it to the required length using open() and ftruncate().
3. Map the File: We will then use mmap() to map this pre-allocated file into our process's memory space, getting back a single pointer to the start of the mapped region.
4. Write Data: We'll use this pointer, along with pointer arithmetic and memcpy, to write our header, vectors, and graph structures directly into the memory region.
5. Clean Up: Finally, we'll use munmap() to unmap the file from our address space and close() the file descriptor. The operating system will handle flushing our in-memory changes to the physical disk.

Let's dive into the specifics of using mmap for writing.

Implementing the serialize Function

Let's build the hnsw_serialize function step-by-step. Its signature will be:
int hnsw_serialize(const HNSW *hnsw, const char *filename);

1. Calculating the Total File Size

We need to iterate through our graph to compute the exact size required for each section.

// Calculate the size of the packed connection data
size_t packed_graph_size = 0;
for (uint64_t i = 0; i < hnsw->num_vectors; ++i) {
    HNSWNode *node = &hnsw->nodes[i];
    packed_graph_size += sizeof(uint8_t); // for max_layer
    for (int l = 0; l <= node->max_layer; ++l) {
        // Size of the connection count + size of the connections themselves
        packed_graph_size += sizeof(uint16_t);
        packed_graph_size += node->connections[l].count * sizeof(uint64_t);
    }
}

// Calculate total file size
size_t vector_data_size = hnsw->num_vectors * hnsw->vector_dim * sizeof(float);
size_t node_offset_table_size = hnsw->num_vectors * sizeof(uint64_t);

size_t total_size = sizeof(HNSWFileHeader) + 
                    vector_data_size + 
                    node_offset_table_size + 
                    packed_graph_size;

This calculation gives us the exact number of bytes we need, allowing us to pre-allocate the file perfectly.

2. & 3. File Creation and Mapping

Now, we use the standard POSIX functions to create, truncate, and map the file.

// Open the file for reading and writing, create if it doesn't exist,
// and truncate it to zero length if it does.
int fd = open(filename, O_RDWR | O_CREAT | O_TRUNC, 0644);
if (fd == -1) {
    perror("open");
    return -1;
}

// Set the file size to our calculated total.
if (ftruncate(fd, total_size) == -1) {
    perror("ftruncate");
    close(fd);
    return -1;
}

// Map the file into memory.
void *map_ptr = mmap(NULL, total_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
if (map_ptr == MAP_FAILED) {
    perror("mmap");
    close(fd);
    return -1;
}

A crucial detail here involves the file descriptor fd. When using MAP_SHARED, the descriptor must remain open for the duration of the mapping. The kernel needs it to manage writing the data back to the file. This is different from MAP_PRIVATE mappings where the descriptor can often be closed immediately.

4. Writing the Data

This is where the direct memory manipulation happens. We'll use a char * as a "write cursor" to keep track of our position in the mapped file.

char *current_ptr = (char *)map_ptr;

// --- Section 1: Write Header (with temporary offsets) ---
HNSWFileHeader header;
// ... initialize header fields like magic, version, dims, etc. ...
header.offset_vectors = sizeof(HNSWFileHeader);
header.offset_graph = header.offset_vectors + vector_data_size;
memcpy(current_ptr, &header, sizeof(HNSWFileHeader));
current_ptr += sizeof(HNSWFileHeader);

// --- Section 2: Write Vector Data ---
char *vector_data_start = current_ptr;
memcpy(vector_data_start, hnsw->vectors_data, vector_data_size);
current_ptr += vector_data_size;

// --- Section 3: Write Graph Data ---
char *graph_data_start = current_ptr;
uint64_t *node_offset_table = (uint64_t *)graph_data_start;
current_ptr += node_offset_table_size; // Skip past the offset table for now

char *packed_data_ptr = current_ptr;
for (uint64_t i = 0; i < hnsw->num_vectors; ++i) {
    // Record the starting offset for this node's packed data
    node_offset_table[i] = (packed_data_ptr - graph_data_start);

    HNSWNode *node = &hnsw->nodes[i];
    
    // Write max_layer
    memcpy(packed_data_ptr, &node->max_layer, sizeof(uint8_t));
    packed_data_ptr += sizeof(uint8_t);

    // Write connections for each layer
    for (int l = 0; l <= node->max_layer; ++l) {
        HNSWNodeLayer *layer = &node->connections[l];
        
        // Write connection count for this layer
        uint16_t count16 = (uint16_t)layer->count;
        memcpy(packed_data_ptr, &count16, sizeof(uint16_t));
        packed_data_ptr += sizeof(uint16_t);

        // Write the actual connection node IDs
        if (layer->count > 0) {
            memcpy(packed_data_ptr, layer->ids, layer->count * sizeof(uint64_t));
            packed_data_ptr += layer->count * sizeof(uint64_t);
        }
    }
}

Notice the logic: we place the node_offset_table first, but we fill it in as we write the packed_data that follows it. This is possible because we have the entire region mapped in memory. The value of node_offset_table[i] is the byte distance from the start of the graph section to the start of node i's connection list.

5. Clean Up

Finally, we ensure our changes are persisted and release the resources.

// The msync call is not strictly necessary on munmap, but can be used
// to explicitly control when data is written to disk. We'll cover it
// in a later lesson. For now, munmap is sufficient.
if (munmap(map_ptr, total_size) == -1) {
    perror("munmap");
}

// Now we can close the file descriptor.
close(fd);

return 0; // Success

Calling munmap signals to the OS that we are done with the memory region. For MAP_SHARED mappings, this is the point where the OS ensures any "dirty" pages (memory pages we've modified) are scheduled to be written to the disk.

Conclusion

In this lesson, you've bridged the gap between your in-memory data structures and a persistent, on-disk file. By leveraging mmap, you've implemented a high-performance serialization routine that aligns perfectly with the low-level, systems-oriented goals of this project.

Key Takeaways:

• Memory-mapped I/O (mmap) is a powerful alternative to traditional read/write calls, especially for structured binary data.
• For writing, mmap requires the PROT_WRITE protection flag and the MAP_SHARED mapping flag to ensure changes are written back to the file.
• The serialization workflow involves calculating the total size, creating and pre-allocating the file with ftruncate, mapping it, writing data using pointer arithmetic, and finally unmapping.
• This approach gives you a "memory-like" interface to the file, simplifying complex write patterns like populating a header with offsets calculated later in the process.

You now have a function to save your work. In the next lesson, we will complete the round trip by implementing the deserialize function. You will see how mmap makes loading our entire database back into memory an almost instantaneous, zero-copy operation.