Entry Iterator and Compaction

Loading…

Entry Iterator and Compaction

Relevant source files

• experiments/simd-r-drive-ws-server/src/main.rs
• simd-r-drive-entry-handle/Cargo.toml
• simd-r-drive-entry-handle/src/entry_metadata.rs
• src/storage_engine.rs
• src/storage_engine/entry_iterator.rs
• tests/compaction_tests.rs
• tests/streaming_tests.rs

This section describes the mechanisms for traversing the append-only storage and reclaiming space. Because the DataStore never modifies data in place, the EntryIterator must navigate a chain of historical versions to find live data, while the compaction process periodically rewrites the file to remove stale entries and tombstones.

Entry Iterator

The EntryIterator is responsible for traversing the memory-mapped storage file in reverse chronological order (newest to oldest). This reverse traversal is critical because it allows the iterator to identify the most recent version of a key first.

Traversal Logic

The iterator follows a backward-linked chain using the prev_offset field stored in each entry’s EntryMetadata src/storage_engine/entry_iterator.rs:12-13

1. Initialization : Starts at the current tail_offset of the file and initializes a HashSet with a high-performance Xxh3BuildHasher src/storage_engine/entry_iterator.rs:41-47
2. Metadata Extraction : At each step, it reads the EntryMetadata located immediately before the current cursor. The metadata size is fixed at METADATA_SIZE (20 bytes) src/storage_engine/entry_iterator.rs:76-81
3. Deduplication : It maintains a seen_keys HashSet to track key hashes already encountered. If a hash is already in the set, the entry is skipped via a recursive call to next(), ensuring only the latest version is yielded src/storage_engine/entry_iterator.rs:110-112
4. Tombstone Handling : If an entry consists of a single NULL_BYTE, it is identified as a deleted record and skipped src/storage_engine/entry_iterator.rs:117-119
5. Termination : The iterator stops when the cursor reaches a position smaller than METADATA_SIZE or when the memory map is empty src/storage_engine/entry_iterator.rs:71-73

Entry Iterator Data Flow

The following diagram illustrates how the EntryIterator transforms raw file offsets into unique EntryHandle items.

Diagram: EntryIterator Traversal Flow

graph TD
    subgraph "File Space (Mmap)"
        [E3_Entry_N_Newest] --> [E2_Entry_N_Minus_1]
        [E2_Entry_N_Minus_1] --> [E1_Entry_N_Minus_2_Oldest]
    end

    subgraph "EntryIterator_Entity [src/storage_engine/entry_iterator.rs]"
        [CURSOR_tail_offset]
        [SEEN_keys_HashSet]
        [NEXT_fn_next]
    end

    [CURSOR_tail_offset] -- "points to tail" --> [E3_Entry_N_Newest]
    [NEXT_fn_next] -- "deserialize_metadata" --> [E3_Entry_N_Newest]
    [E3_Entry_N_Newest] -- "metadata.prev_offset" --> [CURSOR_tail_offset]
    
    [NEXT_fn_next] -- "check metadata.key_hash" --> [SEEN_keys_HashSet]
    [SEEN_keys_HashSet] -- "new hash?" --> [Yield_EntryHandle]
    [SEEN_keys_HashSet] -- "existing hash?" --> [Skip_Recurse_next]

    [Yield_EntryHandle] -- "populate" --> [EntryHandle_Entity]

Sources: src/storage_engine/entry_iterator.rs:21-25 src/storage_engine/entry_iterator.rs:69-126 simd-r-drive-entry-handle/src/entry_metadata.rs:46-50

Compaction Process

Compaction is the mechanism for reclaiming disk space in the append-only architecture. It works by creating a new version of the storage file containing only the “live” (most recent and non-deleted) entries.

Implementation Details

The DataStore::compact() method performs the following steps:

1. Identify Live Entries : It utilizes the EntryIterator to scan the file from the end to the beginning src/storage_engine/entry_iterator.rs:12-13
2. Filter : The iterator automatically filters out older versions of keys and entries marked with tombstones (single NULL_BYTE) src/storage_engine/entry_iterator.rs:18-19
3. Rewrite : The live entries are written to a temporary file. During this process, only the latest version of each key is persisted tests/compaction_tests.rs:136-138
4. Atomic Swap : Once the rewrite is complete, the temporary file replaces the original storage file, and the KeyIndexer is rebuilt to point to the new offsets tests/compaction_tests.rs:152-154

Compaction State Transition

This diagram maps the high-level compaction logic to the internal functions and components involved.

Diagram: Compaction Logic Mapping

graph LR
    subgraph "DataStore_Engine [src/storage_engine/data_store.rs]"
        [compact_fn]
        [EntryIterator_new]
        [DataStoreWriter_write]
    end

    subgraph "Storage_State"
        [OLD_File_Stale_Deleted]
        [NEW_File_Live_Only]
        [KeyIndexer_Entity]
    end

    [compact_fn] -- "initializes" --> [EntryIterator_new]
    [EntryIterator_new] -- "scans backward" --> [OLD_File_Stale_Deleted]
    [EntryIterator_new] -- "yields live EntryHandle" --> [compact_fn]
    [compact_fn] -- "appends to temp" --> [DataStoreWriter_write]
    [DataStoreWriter_write] -- "persists" --> [NEW_File_Live_Only]
    [compact_fn] -- "rebuilds index" --> [KeyIndexer_Entity]
    [KeyIndexer_Entity] -- "maps hashes to new offsets" --> [NEW_File_Live_Only]

Sources: src/storage_engine/entry_iterator.rs:21-25 src/storage_engine.rs:4-5 src/storage_engine/entry_iterator.rs:41-47 tests/compaction_tests.rs:136-138 tests/compaction_tests.rs:152-154

Key Implementation Details

Metadata and Alignment

During iteration, the EntryIterator must account for PAYLOAD_ALIGNMENT (64 bytes) src/storage_engine/entry_iterator.rs:50-51 It uses prepad_len to calculate the padding added during the write phase to ensure the payload was correctly aligned src/storage_engine/entry_iterator.rs:50-53

Tombstones and Legacy Support

A deletion is recorded by appending a new entry with the target key but a payload consisting of a single 0x00 (NULL_BYTE) src/storage_engine/entry_iterator.rs:117-119

The EntryIterator handles two cases for tombstones:

1. Aligned Tombstones : Standard entries following the alignment rules where the payload start is derived from the prev_tail plus padding src/storage_engine/entry_iterator.rs:86-87
2. Legacy Tombstones : Unaligned single-byte entries used in older versions of the format, identified by checking if the entry_end is exactly one byte ahead of prev_tail and contains a NULL_BYTE src/storage_engine/entry_iterator.rs:92-98

Parallel Iteration

When the parallel feature is enabled, the storage engine supports par_iter_entries(), which allows Rayon-based parallel processing of entries while maintaining the same deduplication and tombstone-skipping guarantees as the sequential iterator. This is verified through comprehensive testing of parallel access patterns tests/compaction_tests.rs:1-178

Sources: src/storage_engine/entry_iterator.rs:1-127 simd-r-drive-entry-handle/src/entry_metadata.rs:9-38 tests/compaction_tests.rs:118-120 tests/streaming_tests.rs:1-105