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).

v1 limitations (intentional seams)

Area	v1 behaviour	Future
Block payload	Uncompressed	Optional compression, signalled by footer flags (REQ-20).
Bloom filter	Not built	Optional per-segment Bloom filter, footer-flagged (REQ-21).
Long values	Every string inlined in a block	Divert long strings/blobs to a more space-efficient 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.