Key Indexer and Hashing

Loading…

Key Indexer and Hashing

Relevant source files

• experiments/bindings/python-ws-client/pyproject.toml
• src/storage_engine/digest.rs
• src/storage_engine/digest/compute_hash.rs
• src/storage_engine/key_indexer.rs
• src/utils/namespace_hasher.rs
• tests/hash_stability_tests.rs
• tests/namespace_hasher_tests.rs

The KeyIndexer is the primary in-memory data structure used to map 64-bit key hashes to their corresponding physical locations within the append-only data file. To maintain a low memory footprint while providing high reliability, it employs a packed bit scheme that combines file offsets with collision-detection fingerprints.

Hashing Implementation

The system relies on XXH3 , a high-performance non-cryptographic hash function, to generate 64-bit identifiers for keys. XXH3 is chosen for its SIMD optimization (AVX2, NEON) and excellent distribution properties src/storage_engine/digest/compute_hash.rs:3-9

Core Hashing Functions

• compute_hash(key:&[u8]) -> u64: Computes a single 64-bit hash using xxh3_64 src/storage_engine/digest/compute_hash.rs:25-27
• compute_hash_batch(keys:&[&[u8]]) -> Vec<u64>: Optimizes batch operations by pre-allocating the results vector and iterating through keys to minimize high-level API overhead and lock contention src/storage_engine/digest/compute_hash.rs:64-77
• Xxh3BuildHasher : A custom hasher implementation used by the internal HashMap to ensure the index itself benefits from XXH3 performance src/storage_engine/key_indexer.rs58 src/storage_engine/digest/xxh3_build_hasher.rs:21-30
• Xxh3Hasher : Implements the Hasher trait by wrapping xxh3_64 for use in standard library collections src/storage_engine/digest/xxh3_build_hasher.rs:6-18

Hash Stability

The project maintains strict hash stability to ensure that data written to disk remains accessible across dependency updates. Hardcoded mapping tests (e.g., alice → 0x4da10dd61a0116b0) guard against regressions in the xxhash-rust crate or its feature flags tests/hash_stability_tests.rs:1-33 Batch stability is also verified to ensure compute_hash_batch results match individual compute_hash calls tests/hash_stability_tests.rs:58-65

NamespaceHasher

The NamespaceHasher provides a mechanism to scope keys within logical domains (e.g., “users” vs “sessions”). It generates a 16-byte namespaced key by concatenating two 8-byte XXH3 hashes:

1. The hash of the namespace prefix src/utils/namespace_hasher.rs:33-37
2. The hash of the individual key src/utils/namespace_hasher.rs:56-62

This ensures that different namespaces do not generate overlapping keys, even if the underlying keys are identical src/utils/namespace_hasher.rs:45-48 Stability tests enforce specific 16-byte outputs for known namespace/key combinations tests/hash_stability_tests.rs:77-100

Sources: src/storage_engine/digest/compute_hash.rs:1-77 src/utils/namespace_hasher.rs:1-66 src/storage_engine/digest/xxh3_build_hasher.rs:1-30 src/storage_engine/digest.rs:1-8 tests/hash_stability_tests.rs:1-108

KeyIndexer Architecture

The KeyIndexer manages a HashMap<u64, u64, Xxh3BuildHasher> where the key is the 64-bit XXH3 hash and the value is a packed u64 containing both the file offset and a collision tag src/storage_engine/key_indexer.rs:56-59

Packed Value Format

To save memory, the 64-bit value is split into two segments:

• Tag (16 bits) : The upper 16 bits of the original key hash (TAG_BITS = 16). This serves as a fingerprint to detect if two different keys produced the same 64-bit hash src/storage_engine/key_indexer.rs:9-12
• Offset (48 bits) : The lower 48 bits represent the absolute file offset (OFFSET_MASK). This allows for a maximum file size of 256 TiB src/storage_engine/key_indexer.rs:15-45

Collision Detection Logic

During lookups or inserts, the system re-derives the 16-bit tag from the key hash src/storage_engine/key_indexer.rs136 If an entry exists but the stored tag does not match the new tag, a hash collision is detected, and the operation is rejected with an error src/storage_engine/key_indexer.rs:145-148

Data Flow: Key to Offset

The following diagram illustrates how a raw byte key is transformed into a physical file offset through the indexing layer.

Key Translation and Indexing Flow

graph TD
    subgraph "NaturalLanguageSpace"
        A["User Key (e.g., 'my_data')"]
end

    subgraph "CodeEntitySpace:src/storage_engine/"
        B["compute_hash(key)"]
C["KeyIndexer::tag_from_hash(u64)"]
D["KeyIndexer::pack(tag, offset)"]
E["KeyIndexer.index: HashMap<u64, u64, Xxh3BuildHasher>"]
end

 
   A -->|&[u8]| B
 
   B -->|u64 Hash| C
 
   B -->|u64 Hash| E
 
   C -->|u16 Tag| D
 
   D -->|u64 Packed| E
 
   E -->|lookup/insert| F["File Offset (48-bit)"]

Sources: src/storage_engine/key_indexer.rs:9-59 src/storage_engine/key_indexer.rs:135-160

KeyIndexer Operations

Index Initialization

During DataStore::open(), the KeyIndexer::build function performs a reverse scan of the storage file. It starts from the tail_offset and follows the prev_offset pointers in EntryMetadata src/storage_engine/key_indexer.rs:98-105 Because it scans newest-to-oldest, it only indexes the most recent version of any given key hash by tracking seen hashes src/storage_engine/key_indexer.rs:108-115

Insertion and Updates

The insert method handles both new keys and updates to existing ones:

1. Unpack : If the hash exists, it unpacks the stored value to retrieve the tag src/storage_engine/key_indexer.rs:141-142
2. Verify : It compares the new_tag with the stored_tag src/storage_engine/key_indexer.rs145
3. Commit : If they match, the new packed value (new tag + new offset) is stored src/storage_engine/key_indexer.rs151

Mapping Component Relationships

The following diagram maps the logical hashing components to their implementation structs and functions.

Hashing and Indexing Component Map

graph LR
    subgraph "LogicalFunction"
        H["Hashing"]
I["Indexing"]
N["Namespacing"]
end

    subgraph "ImplementationEntities"
        CH["compute_hash()"]
KI["struct KeyIndexer"]
NH["struct NamespaceHasher"]
XBH["struct Xxh3BuildHasher"]
end

    H --- CH
    H --- XBH
    I --- KI
    N --- NH
 
   KI -.->|uses| XBH
 
   NH -.->|calls| CH

Summary of KeyIndexer Methods

Sources: src/storage_engine/key_indexer.rs:61-200 src/utils/namespace_hasher.rs:17-65