HNSW Graph and Vector Serialization Format Design

Why a Custom Binary Format?

Before we begin, it's fair to ask: why not just use a standard format like JSON, or a library like Protocol Buffers? While those are excellent for many applications, our goals demand more. We are aiming for a format that is:

• Compact: Minimizes disk space.
• Fast to write and read: Low serialization/deserialization overhead.
• Zero-Copy Friendly: Can be loaded into memory (using mmap) and used directly without a separate parsing step that copies data into different structures. This is a cornerstone of high-performance I/O.

These constraints, particularly the zero-copy requirement, lead us down the path of creating a carefully crafted binary layout.

The Anatomy of a Binary File

A robust binary file is not an unstructured blob of data. It has a well-defined anatomy, much like a Portable Executable (PE) file on Windows, which has distinct headers and sections for code, data, and other metadata.

Our file format will be composed of three main parts:

1. A File Header containing "magic numbers" for identification, version information, and crucial metadata.
2. A Vector Data Section for the raw vector floats.
3. A Graph Structure Section that encodes the topology of the HNSW graph.

In a practical implementation, it's also crucial to have a way to identify your file type. A simple "magic number" at the start of the file serves this purpose.

Designing the File Header

The header is the file's table of contents. It's fixed in size and always located at the very beginning of the file. It must contain all the information needed to navigate and interpret the rest of the file.

Here is a proposed C struct for our file header:

#define HNSW_MAGIC "HNSWDB"
#define HNSW_VERSION 1

typedef struct {
    char magic[6];             // Should match HNSW_MAGIC
    uint16_t version;          // File format version
    
    // Core graph/data parameters
    uint64_t num_vectors;      // Total number of vectors
    uint64_t vector_dim;       // Dimension of each vector
    uint64_t M;                // Max connections per layer
    uint64_t ef_construction;  // efConstruction used at build time
    
    // Graph state
    int64_t entry_point_id;    // ID of the entry point node (-1 if none)
    
    // Offsets to major data sections
    uint64_t offset_vectors;   // Byte offset to start of vector data
    uint64_t offset_graph;     // Byte offset to start of graph data
} HNSWFileHeader;

Design Rationale:

• magic & version: The magic string identifies the file, while version allows us to evolve the format in the future while maintaining backwards compatibility, a key principle of good format design.
• Core Parameters: Storing num_vectors, vector_dim, M, etc., in the header allows a loading function to pre-allocate memory and validate that the file is compatible with the library's settings.
• Offsets (offset_vectors, offset_graph): This is the most critical part. Instead of assuming sections start at fixed locations, we store their absolute byte offsets from the beginning of the file. This makes the format flexible. If we later decide to add a new section, we can simply add a new offset to the header without breaking the entire layout.

Laying out the Vector Data

This is the most straightforward part. The vectors are a collection of floating-point numbers. For maximum performance and compatibility with SIMD operations (which you've already implemented), the best way to store this is as a single, contiguous block of floats.

The layout is simply:
[vector_0_dim_0, vector_0_dim_1, ..., vector_N_dim_D]

The total size of this section will be num_vectors * vector_dim * sizeof(float). The offset_vectors in the header will point to the beginning of this block. When we later mmap this file, we can get a direct float* to this data, enabling zero-copy access.

Serializing the Graph Structure

This is the most challenging part. In memory, our graph is a web of pointers. Pointers are memory addresses and are meaningless once written to a file. We must replace pointers with a persistent and location-independent way of identifying nodes. The natural choice is to use each vector's integer index (from 0 to num_vectors - 1) as its unique Node ID.

The primary challenge is that each node has a variable number of connections on a variable number of layers. Storing this efficiently is key. A naive approach might be to use dynamically sized records, but this comes with significant drawbacks.

To heed this advice, we can use a level of indirection: a node offset table. This is a powerful technique for handling variable-sized records in a binary format.

Our graph section will be structured as follows:

1. Node Offset Table: An array of num_vectors 64-bit integers. The i-th entry, node_offsets[i], stores the byte offset (relative to the start of the graph section) where the connection data for node i begins.
2. Packed Connection Data: A contiguous block of all connection data for all nodes, packed one after another.

The structure for a single node's data within this packed block would look like this:

• uint8_t max_layer
• For each layer l from 0 to max_layer:
  • uint16_t num_connections_at_layer_l
  • An array of num_connections_at_layer_l Node IDs (uint64_t[]).

By using the offset table, we can find the start of any node's data in O(1) time. The size of node i's data can be calculated as node_offsets[i+1] - node_offsets[i], allowing us to read exactly the right number of bytes.

The Complete File Layout

Let's assemble these pieces into a complete picture of our binary file format.

This design provides a solid foundation. It's structured, versioned, and, most importantly, designed for performance. By using offsets and storing data in large, contiguous blocks, we set the stage for extremely fast loading via memory mapping, which we will explore in a future lesson.

Conclusion

In this lesson, we have moved from the abstract realm of in-memory data structures to the concrete world of on-disk representation. We designed a complete binary file format for our HNSW database from the ground up.

Key Takeaways:

• A custom binary format is justified when performance, compactness, and zero-copy access are primary goals.
• A robust format begins with a header containing a magic number, version, and critical metadata, including offsets to data sections.
• Pointers cannot be serialized; they must be replaced with location-independent IDs or indices.
• For variable-sized records (like our graph nodes), an offset table provides fast, O(1) random access while allowing data to be packed contiguously.
• The entire layout is designed to be friendly for memory-mapped I/O (mmap), which enables near-instantaneous "loading" and zero-copy access.

You have now designed the blueprint for making our database durable. In the next lesson, you will implement the serialize function that takes our in-memory graph and writes it to a file, strictly following the format we've just designed.