On-Disk Storage Format

Loading…

On-Disk Storage Format

Relevant source files

• README.md
• assets/storage-layout.png
• simd-r-drive-entry-handle/Cargo.toml
• simd-r-drive-entry-handle/src/entry_metadata.rs
• src/storage_engine.rs
• src/storage_engine/constants.rs
• src/storage_engine/entry_iterator.rs

SIMD R Drive utilizes a high-performance, append-only binary storage format. The layout is specifically engineered for zero-copy memory-mapped access and SIMD-optimized processing by enforcing strict alignment and minimal metadata overhead.

Binary Layout Overview

The storage file consists of a sequence of entries. Every entry is either an Aligned Entry (containing a payload) or a Tombstone (representing a deletion). To ensure that payloads can be cast to typed slices (e.g., &[u64]) without memory copies, the engine enforces a fixed alignment boundary README.md:51-55

Alignment and Padding

The system uses a PAYLOAD_ALIGNMENT of 64 bytes by default src/storage_engine/constants.rs1 This matches typical CPU cacheline sizes, preventing SIMD/vector loads from crossing cacheline boundaries README.md:51-53

When a new entry is written, the engine calculates a pre-pad based on the current file tail: pad = (A - (prev_tail % A)) & (A - 1), where A = PAYLOAD_ALIGNMENT simd-r-drive-entry-handle/src/entry_metadata.rs22 This calculation is implemented in EntryIterator::prepad_len to correctly locate payloads during backward traversal src/storage_engine/entry_iterator.rs:50-53

Entry Structures

1. Aligned Entry (Non-Tombstone)

Sources: simd-r-drive-entry-handle/src/entry_metadata.rs:11-23 src/storage_engine/entry_iterator.rs:86-88

2. Tombstone (Deletion Marker)

Tombstones are treated as special cases. While modern tombstones follow the alignment rules, the EntryIterator maintains backward compatibility for legacy tombstones that do not include a pre-pad src/storage_engine/entry_iterator.rs:92-98 They use a single NULL_BYTE (0x00) as a payload marker src/storage_engine/constants.rs4

Sources: simd-r-drive-entry-handle/src/entry_metadata.rs:25-30 src/storage_engine/constants.rs4 src/storage_engine/entry_iterator.rs:117-119

Metadata Implementation: EntryMetadata

The EntryMetadata struct is the core descriptor for every entry. It is stored immediately following the payload.

Data Structure

The struct uses #[repr(C)] to ensure a stable memory layout for direct deserialization from the memory map simd-r-drive-entry-handle/src/entry_metadata.rs:44-50

Serialization

Metadata is stored using Little-Endian encoding for numeric values simd-r-drive-entry-handle/src/entry_metadata.rs:70-71 The serialize and deserialize functions handle the conversion between the struct and the 20-byte fixed-size array defined by METADATA_SIZE simd-r-drive-entry-handle/src/entry_metadata.rs:75-112

Sources: simd-r-drive-entry-handle/src/entry_metadata.rs:44-112

The Backward-Linked Validation Chain

SIMD R Drive uses a backward-linked chain via the prev_offset field. Unlike traditional linked lists that point to the start of an entry, prev_offset stores the absolute offset of the previous tail simd-r-drive-entry-handle/src/entry_metadata.rs:32-34 This allows the reader to derive the current payload’s start by calculating the pre-pad length relative to that previous tail src/storage_engine/entry_iterator.rs:86-87

Data Flow: Writing and Linking

The following diagram illustrates how the DataStore logic calculates alignment and links the new EntryMetadata.

Entry Writing and Alignment Flow

graph TD
    subgraph "DataStore_Logic"
        ["Start write(key, payload)"] --> ["Get current tail_offset"]
        ["Get current tail_offset"] --> ["Calculate pre-pad via EntryIterator::prepad_len"]
        ["Calculate pre-pad via EntryIterator::prepad_len"] --> ["Compute XXH3 key_hash"]
        ["Compute XXH3 key_hash"] --> ["Compute CRC32C checksum"]
        ["Compute CRC32C checksum"] --> ["Set prev_offset = tail_offset"]
        ["Set prev_offset = tail_offset"] --> ["Construct EntryMetadata"]
end

    subgraph "Disk_Layout"
        ["Construct EntryMetadata"] --> ["Write padding bytes (0..63 bytes)"]
        ["Write padding bytes (0..63 bytes)"] --> ["Write payload bytes"]
        ["Write payload bytes"] --> ["Write serialized EntryMetadata (20 bytes)"]
end

    ["Write serialized EntryMetadata (20 bytes)"] --> ["Update KeyIndexer with metadata_offset"]

Sources: simd-r-drive-entry-handle/src/entry_metadata.rs:11-36 src/storage_engine/entry_iterator.rs:50-53

Integrity and Checksums

Integrity is maintained through the checksum field in EntryMetadata. This is a CRC32C hash of the raw payload bytes simd-r-drive-entry-handle/src/entry_metadata.rs19

Verification Process

The EntryIterator traverses the file backward from a given tail_offset src/storage_engine/entry_iterator.rs:16-17 For each entry, it:

1. Deserializes the 20-byte metadata block using EntryMetadata::deserialize src/storage_engine/entry_iterator.rs:80-81
2. Derives the entry_start by adding the calculated prepad_len to the prev_offset src/storage_engine/entry_iterator.rs:86-87
3. Identifies the entry_end as the start of the metadata block src/storage_engine/entry_iterator.rs89
4. Returns an EntryHandle which can be used to verify the checksum against the mapped payload src/storage_engine/entry_iterator.rs:121-125

Code Entity Mapping: Storage Logic

Sources: simd-r-drive-entry-handle/src/entry_metadata.rs:75-76 src/storage_engine/entry_iterator.rs:21-47 src/storage_engine/entry_iterator.rs:69-126