String Store

String Store

The String Store is a lightweight, append-only, deduplicated UTF-8 subsystem for values such as URLs, property names, and short text. It gives the rest of the database two ways to address a string:

• a compact StrId (u64) — the cheap internal reference, stable within a segment, used inside records;
• a 128-bit StrHash (xxh3-128) — a content hash for dedup, integrity, and cross-segment identity.

Status: implemented (v1) — in-RAM model plus a single on-disk segment.

Design targets

• Minimal footprint, embeddable like SQLite.
• Append-only: stored entries are never rewritten or deleted.
• Built-in deduplication: identical content is stored once.
• Stable identifiers across compaction.
• KISS layout and a small API.
• Seams left for later: block compression, an optional Bloom filter, and routing of long values to a more space-efficient store.

On-disk segment layout

Little-endian throughout.

[Header]                       magic(4) + version(2) + flags(2)        = 8 bytes
[Block 0 | payload | trailer]  payload = concatenated entries,
[Block 1 | payload | trailer]  trailer = [u32 entry offsets][u32 count]
...                            (block opens fresh once it reaches ~64 KiB)
[Block N-1 | ... ]
[BlockDirectory]               [u32 count]{ u64 file_offset, u32 payload_len, u32 entry_count }*
[Footer]                       fixed 40 bytes, read from end of file

Each entry inside a block:

[hash128 (16)] [varint len (LEB128)] [utf8 bytes] [crc32 (4)]

• hash128 — xxh3-128 content hash, for dedup and integrity.
• varint len — LEB128 byte length of the string.
• crc32 — fast per-entry corruption check (crc32fast).

The footer records the block-directory offset and length, the block count, the total entry count, a flags field (compression / Bloom — both 0 in v1), a CRC32 over the directory, and a magic trailer. On open the directory CRC is checked, then every entry's CRC32 and UTF-8 validity are re-verified while the in-RAM id/hash indexes are rebuilt; a bad header, footer, or directory is rejected with an error.

save writes the whole segment to a temporary file and renames it into place, so a crash mid-write cannot corrupt an existing segment.

Rust API

pub type StrId = u64;

#[derive(Clone, Copy, Eq, PartialEq, Hash, Debug)]
pub struct StrHash(pub [u8; 16]);   // xxh3-128, little-endian

impl StringStore {
    pub fn new() -> Self;

    pub fn intern(&mut self, s: &str) -> (StrHash, StrId); // idempotent
    pub fn resolve_id(&self, id: StrId) -> Option<&str>;
    pub fn resolve_hash(&self, h: StrHash) -> Option<&str>;
    pub fn id_of(&self, h: StrHash) -> Option<StrId>;
    pub fn hash_of(&self, id: StrId) -> Option<StrHash>;

    pub fn len(&self) -> usize;
    pub fn is_empty(&self) -> bool;

    pub fn save(&self, path: impl AsRef<Path>) -> io::Result<()>;
    pub fn open(path: impl AsRef<Path>) -> io::Result<Self>;
}

intern is idempotent: re-interning content that is already present returns the existing id and hash without storing a duplicate. It is also the single choke point for future long-value routing (see below).

Block compression (v2)

Block payloads can be compressed. The algorithm is selected when creating the store and written into the header flags field (bits 1–0). The in-memory model is always uncompressed; compression is applied only in save and reversed in open.

// No compression (default)
let store = StringStore::new();

// LZ4 — pure Rust, fast encode/decode, ~2–4× on typical data
let store = StringStore::new().with_compression(Compression::Lz4);

// Zstd — excellent ratio, especially on URI-heavy data
let store = StringStore::new().with_compression(Compression::Zstd);

Compressed block wire format:

[u32 uncompressed_len] [compressed bytes]   ← payload recorded in directory
[u32 entry offsets…]  [u32 count]           ← trailer, always uncompressed

Entry offsets in the trailer always point into the uncompressed payload, so random-access by ID works identically for all algorithms.

Measured ratios on 374 unique mixed strings (English words + ontology URIs):

Algorithm	On-disk size	Ratio
None	15 371 B	1.00×
LZ4 (lz4_flex, pure Rust)	11 984 B	1.28×
Zstd (level 3)	11 388 B	1.35×

Ratios grow with dataset size and string length. URI-heavy data (long repeated namespace prefixes) compresses significantly better than short English words.

Format version 2 adds compression support; version 1 files are still readable by open (treated as uncompressed).

Remaining limitations (intentional seams)

Area	Current behaviour	Future
Bloom filter	Not built; footer flags reserves the bit	Optional per-segment Bloom filter (REQ-21).
Long values	Every string inlined in a block	Divert long strings/blobs to a dedicated store; hooks in at intern (REQ-22).
Persistence	save rewrites the whole segment	Incremental on-disk append (REQ-23).

Verification

Seven unit tests cover dedup, resolve-by-id/hash, missing lookups, empty/Unicode strings, single- and multi-block save/open round-trips, and corruption rejection. See the Test Plan for the requirement-to-test matrix.