Efficient Vector Data Storage Design

The Philosophy of a Custom Binary Format

Before we start arranging bytes, it's important to understand why we are designing our own format instead of using a standard one like JSON or Protocol Buffers. Your interest in low-level, high-performance systems points directly to the answer. As the author of "Creating my own bespoke binary format" notes, custom formats are justified when you have hard constraints.

Our memory-mapped approach directly targets the "zero-copy" goal. The file layout we design today will be optimized for compactness and the ability to randomly access any vector without parsing the entire file.

The Anatomy of Our File: Header and Data

Most binary file formats, from executable files like ELF to image formats like PNG, follow a common pattern: a header at the beginning, followed by one or more data blocks. The header acts as a table of contents, describing the structure and contents of the rest of the file.

Our file will adopt a similar structure:

1. A single, fixed-size header containing all the necessary metadata.
2. A single, contiguous data block containing all the vector components.

Let's design the header first. It's the entry point to our database, so it must contain everything needed to interpret the data. We can define it as a C struct.

#define DB_MAGIC 0x56444230 // "VDB0"
#define MAX_DIMS 2048

// Enum for the distance metric
typedef enum {
    EUCLIDEAN,
    COSINE,
} Metric;

// The main header for the database file
typedef struct {
    uint32_t magic;           // Magic number to identify the file type
    uint32_t version;         // Version of the file format
    
    uint64_t vector_count;    // Number of vectors currently stored
    uint64_t vector_capacity; // Maximum number of vectors the file can hold
    uint16_t dimension;       // Dimension of the vectors
    Metric metric;            // Distance metric used for the index

    uint64_t data_offset;     // Byte offset from the start of the file to the vector data
    // Add padding to ensure the header is a multiple of 64 bytes for alignment
    char _padding[24]; 
} DbHeader; // Total size: 64 bytes

Let's break down these fields:

• magic and version: Essential for validation. They allow our program to quickly check if it's opening the correct file type and version.
• vector_count and vector_capacity: These track the current usage and total size of our database.
• dimension and metric: These define the properties of the vectors themselves, crucial for distance calculations.
• data_offset: This is a key field. It's the byte offset from the beginning of the file to where the vector data begins. This provides flexibility, allowing us to change the header size in future versions without breaking the file structure.
• _padding: We add padding to make the total header size a clean power of two (64 bytes). This ensures that the data block following it can start on a well-aligned memory address, which is critical for performance.

This header-with-offsets pattern is common. The following article discusses a similar approach for a 3D mesh format.

Struct of Arrays (SoA): Optimizing for Cache and SIMD

Now for the most important design decision regarding the data block: how do we lay out the vectors? Given your background in systems engineering, you'll appreciate the distinction between an Array of Structs (AoS) and a Struct of Arrays (SoA).

• AoS: struct { float components[128]; } vectors[1000];
  • Here, all components of a single vector are contiguous in memory.
• SoA: float all_components[128 * 1000];
  • Here, all components of all vectors are stored in one massive, contiguous array. Vector 0 is all_components[0..127], Vector 1 is all_components[128..255], and so on.

For our purpose—performing sequential scans and SIMD calculations—the Struct of Arrays (SoA) layout is far superior. When we scan the database to find the nearest neighbors, we will read large, contiguous blocks of memory. This pattern is extremely friendly to the CPU's prefetcher and caches, minimizing latency from RAM access. Furthermore, loading data into SIMD registers is most efficient from a single, tightly packed array.

The Apache Arrow project, a standard for in-memory columnar data, uses this exact principle.

We will adopt a simple SoA layout. Our data block will be one giant array of floats. To access the i-th vector, we perform simple pointer arithmetic: start_of_data_block + i * dimension.

The Complete File Layout

Combining these ideas, our final file layout will look like this:

1. DbHeader (64 bytes): Our metadata header, located at the very start of the file.
2. Vector Data (Variable size): The SoA block containing all vector components. It starts at the data_offset specified in the header.

Visually, the memory-mapped region looks like this:

+--------------------------------+
| DbHeader (64 bytes)            |  <- mapped_region
+--------------------------------+
| Vector Data Block              |  <- mapped_region + header.data_offset
| (capacity * dimension * 4)     |
|                                |
|                                |
| ...                            |
+--------------------------------+

When our program mmaps the file, it gets a void* pointer. The access logic becomes straightforward:

// Assume 'mapped_region' is the void* from mmap
DbHeader* header = (DbHeader*)mapped_region;

// Get a pointer to the start of the vector data
float* vector_data = (float*)((char*)mapped_region + header->data_offset);

// Access the 10th vector (0-indexed)
int i = 9;
float* vector_i = vector_data + (i * header->dimension);

// Now vector_i is a pointer to the first component of the 10th vector.
// We can pass it to our SIMD distance functions.

This design is simple, efficient, and achieves our zero-copy goal. We can read metadata or any vector's data by directly dereferencing pointers, without any intermediate copies or parsing steps.

An Analogy: The ELF Format

This design pattern of using headers to describe data layouts that are then mapped into memory might feel familiar. It is, in fact, the same fundamental principle used by the operating system's program loader when it runs an executable file.

The Executable and Linkable Format (ELF), standard on Linux, consists of an ELF header and several program headers. Each program header describes a segment of the file (e.g., the executable code .text or initialized data .data), specifying its location in the file, its size, and where it should be mapped into virtual memory. When you run a program, the kernel reads these headers and uses mmap to place the segments into your process's address space.

Our DbHeader serves the same role as the ELF headers. It describes our single "vector data" segment, telling our code where to find it within the memory-mapped file.

Conclusion

In this lesson, we have designed a robust and high-performance file layout for our vector database. By defining a clear structure for our memory-mapped file, we have set the stage for all future operations.

Here are the key takeaways, which echo the best practices for designing binary formats:

• Start with a Header: A fixed-size header containing metadata like magic numbers, version, and data dimensions is the file's entry point.
• Use the Struct of Arrays (SoA) Pattern: Storing vector data in one large, contiguous array is optimal for cache performance during sequential scans and for loading data into SIMD registers.
• Use Offsets for Flexibility: Storing the byte offset to the data block in the header makes the format more extensible for future additions.
• Ensure Alignment: Deliberately padding the header and aligning data blocks is crucial for maximizing hardware performance.
• Avoid Dynamic Sizing: For our core vector data, every vector has the same fixed dimension. This makes indexing via pointer arithmetic trivial and extremely fast, a key advantage over formats that require parsing to find elements.

We have established the blueprint for our on-disk database. In the next lesson, we will bring this design to life by implementing the functions to write vector data directly into this newly structured, memory-mapped region.