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

FSST — future third algorithm

FSST (Fast Static Symbol Table) is a string-specific compression algorithm used in analytical databases (DuckDB, Lance). Its key property is random access: a single string can be decompressed using only the block's symbol table, without reading the rest of the block.

Two Rust crates exist today:

Crate	Status	Verdict
fsst v7 (Lance)	Production-ready, 1.2 M downloads, actively maintained	Not usable here — API is Arrow-coupled (OffsetSizeTrait); requires arrow-array as a hard dependency, contradicting REQ-50.
jdb_fsst v0.1	Arrow-free API (train(&[impl AsRef<[u8]>])), bilingual codebase	Too early — 67 total downloads; no community validation.

The random-access advantage of FSST does not apply to the current architecture because open already decompresses every block fully into RAM. It becomes compelling when lazy decompression is implemented (REQ-24): decompress only the requested entry on each resolve_id call, keeping cold blocks on disk. At that point FSST should be reconsidered as a third Compression variant — either via a matured jdb_fsst, or a thin in-tree wrapper (~500 lines).

Both existing implementations require a minimum input of 32 KB to train a symbol table; each block's symbol table (2313 bytes) must be stored as a per-block prefix in the segment file, which will require a format change.

Remaining limitations (intentional seams)

Area	Current behaviour	Future (REQ)
Lazy decompression	Full block decompressed into RAM on open	On-demand per-entry decompression; unlocks FSST and low-memory operation (REQ-24).
FSST compression	Not implemented	Add as third algorithm after lazy decompression; revisit crate landscape (REQ-25).
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.