Storage engine & key layout¶

Architecture

Every fact Telha stores, whether a node version, an edge, a vector, or a job, lives at a byte-exact address computed by one module. This page documents that module: the StorageEngine trait, the two backends that implement it, and the composite key layout that makes tenant isolation a property of construction rather than a property of discipline.

Overview & purpose¶

core-engine/src/storage/ is, in its own module doc, "the exclusive location for key encoding." Two problems motivate treating storage as its own layer rather than an implementation detail of the temporal engine:

• Tenant isolation must be true by construction, not by convention. Prefix bloom filters are a performance structure, not a security boundary. Isolation only holds if every read path builds keys through tenant-scoped code and every scan is bounded inside a tenant prefix. Ad-hoc key construction at call sites would make isolation unverifiable.
• "Latest version first" iteration needs a documented inversion rule. RocksDB's comparator sorts bytes ascending. Telha wants the newest version of an entity first. Those two facts are reconciled once, here, by inverting timestamps at encode time, rather than by every caller remembering to sort descending.

The result is a single crate-internal authority (KeyCodec, TenantScope, ScanRange) that every other subsystem (temporal, graph, query, vector, jobs) calls through, and a StorageEngine trait that the rest of the engine talks to without ever seeing a raw byte slice.

Design¶

The StorageEngine / StorageSnapshot abstraction¶

pub trait StorageSnapshot {
    fn get(&self, cf: &str, key: &Key) -> Result<Option<Vec<u8>>, StorageError>;
    fn scan_prefix(&self, cf: &str, range: &ScanRange) -> Result<KvIter<'_>, StorageError>;
}

pub trait StorageEngine: Send + Sync {
    fn get(&self, cf: &str, key: &Key) -> Result<Option<Vec<u8>>, StorageError>;
    fn put(&self, cf: &str, key: &Key, value: &[u8]) -> Result<(), StorageError>;
    fn delete(&self, cf: &str, key: &Key) -> Result<(), StorageError>;
    fn scan_prefix(&self, cf: &str, range: &ScanRange) -> Result<KvIter<'_>, StorageError>;
    fn batch_write(&self, ops: Vec<WriteOp>) -> Result<(), StorageError>;
    fn batch_write_durable(&self, ops: Vec<WriteOp>) -> Result<(), StorageError> { /* default: batch_write */ }
    fn delete_range(&self, cf: &str, range: &ScanRange) -> Result<(), StorageError> { /* default: scan + batch delete */ }
    fn snapshot(&self) -> Result<Box<dyn StorageSnapshot + '_>, StorageError>;
    fn checkpoint(&self, dir: &std::path::Path) -> Result<(), StorageError>;
}

Two deliberate departures from a "generic KV store" shape, both recorded in core-engine/src/storage/engine.rs:

• Keys and scan bounds are typed, never raw bytes. Key and ScanRange are opaque outside the crate; the only way to build one is through KeyCodec or a ScanRange constructor, both of which take a TenantScope as their first argument. This is the ratified deviation from the original PRD trait signature: no public surface anywhere in the engine accepts raw key bytes.
• batch_write_durable exists alongside batch_write. Most writes use the configured storage.sync_writes policy; user-visible destruction events (tombstone cascades) must survive power loss the instant they are acknowledged, so they force a WAL sync regardless of that policy.

StorageSnapshot is deliberately not Send: RocksDB snapshots pin thread-local state, so a snapshot should be held briefly on one task and never carried across an await point that migrates threads.

Why MemoryEngine and a RocksDB backend¶

core-engine/src/storage/memory.rs implements StorageEngine over a BTreeMap per column family behind one RwLock. It exists as the semantic baseline: trivially correct ascending-byte-order scans, atomic batches by construction, and a shared conformance suite (core-engine/src/storage/conformance.rs) that both backends must pass unchanged. MemoryEngine is the fast backend for unit tests across the rest of the codebase; RocksDbEngine is the production backend. The same conformance suite is written to also gate the eventual Phase-4 FoundationDB backend (EPIC-401), so the acceptance bar for "is this a valid StorageEngine implementation" is one shared, executable test module rather than prose.

Why composite keys, not secondary indexes¶

The spec's Alternatives Considered section (§9) rejects the obvious alternatives explicitly:

The chosen design instead pushes every access pattern into the key itself. node_history, valid_time_from, adjacency, tenant_all: each is a ScanRange constructor that derives a [prefix, successor(prefix)) bound directly from a TenantScope plus typed components. There is no secondary index to keep consistent with a primary store beyond the two temporal covering indexes described below, which store the primary key as their value specifically so that validating a hit is a point lookup, never a second scan.

flowchart TB
    CALLERS["callers: temporal, graph, query, vector, jobs<br/>(typed requests only: TenantScope + ids + times)"]
    CODEC["KeyCodec / ScanRange<br/>sole key authority"]
    TRAIT["StorageEngine trait<br/>get / put / delete / scan_prefix / batch_write / snapshot"]
    MEM["MemoryEngine<br/>BTreeMap per CF, one RwLock"]
    ROCKS["RocksDbEngine<br/>prefix_extractor = fixed(32), bloom filters per CF"]
    CFS["13 column families<br/>node_versions, edge_versions, adjacency_out/in,<br/>valid_time_index, tx_time_index, vectors, schema,<br/>sources, spans, traces, jobs, bitmap_index"]

    CALLERS --> CODEC --> TRAIT
    TRAIT --> MEM
    TRAIT --> ROCKS
    MEM --> CFS
    ROCKS --> CFS

Data model¶

Column families¶

core-engine/src/storage/mod.rs defines the CF name constants in pub mod cf and cf::ALL, the array the RocksDB backend opens in order. There are 13 column families as built (the spec's §4 diagram and RocksDB module doc comment describe "12"; bitmap_index was added afterward by the bitmap-predicate-index spec and is the 13th, tracked below in As-built notes).

Primitive encodings¶

All key primitives are normative (spec §5.1) and fixed-width. There are no variable-length components anywhere in v1; a future one would need to be length-prefixed and the spec amended first.

Every tenant-scoped key begins with the 32-byte prefix produced by TenantScope::prefix(): [tenant_id (16)][organization_id (16)].

Byte layouts per column family¶

Every layout below is read directly from core-engine/src/storage/keys.rs (the key_len constants and the KeyCodec encode functions), cross-checked against spec §5.2.

node_versions and edge_versions (identical shape, key_len::NODE_VERSION / EDGE_VERSION, 64 bytes):

[ tenant_id 16 ][ organization_id 16 ][ logical_id 16 ][ inv(valid_time_start) 8 ][ inv(tx_time_start) 8 ]
|<---------------- scope 32 ------------------------>|
                                                        total: 64 bytes

adjacency_out and adjacency_in (identical shape, key_len::ADJACENCY, 88 bytes). For adjacency_out, anchor is the source node and neighbor the destination; reversed for adjacency_in:

[ scope 32 ][ anchor_id 16 ][ edge_type_hash 8 ][ inv(valid_time_start) 8 ][ inv(tx_time_start) 8 ][ neighbor_id 16 ]
                                                                                                       total: 88 bytes

valid_time_index and tx_time_index (identical shape, key_len::TEMPORAL_INDEX, 65 bytes). The CF name tells you which time dimension leads; valid_time_index stores (valid_time_start, tx_time_start) in that order, tx_time_index stores (tx_time_start, valid_time_start):

[ scope 32 ][ inv(primary_time) 8 ][ inv(secondary_time) 8 ][ logical_id 16 ][ kind 1 ]
                                                                                total: 65 bytes

kind is IndexKind::Node = 0x00 or IndexKind::Edge = 0x01, letting one index serve both version CFs. The stored value at each index row is the primary CF key bytes (a covering index), so validating a candidate is a point lookup, never a second scan.

vectors (key_len::VECTOR, 72 bytes):

[ scope 32 ][ node_logical_id 16 ][ embedding_model_id 8 ][ inv(valid_time_start) 8 ][ inv(tx_time_start) 8 ]
                                                                                        total: 72 bytes

schema (key_len::SCHEMA, 48 bytes):

[ scope 32 ][ label_hash 8 ][ inv(tx_time_start) 8 ]
                               total: 48 bytes

The same 48-byte shape hosts a second row family under the reserved system scope: KeyCodec::vector_model_key writes [nil 32][model_id 8][inv(tx_start) 8], the deployment-global embedding-model registry (PR-038). It is unreachable from any tenant scan because the nil prefix only exists via SystemScope.

sources (key_len::SOURCE, 56 bytes):

[ scope 32 ][ source_id 16 ][ inv(tx_time_start) 8 ]
                               total: 56 bytes

Two reserved row shapes reuse this exact 56-byte layout at the sentinel chunk index REDACTION_CHUNK_INDEX = u64::MAX (inv(u64::MAX) == 0, so these rows sort first in their family; real chunk indexes are dense from 0 and can never collide):

• Blob redaction record, KeyCodec::redaction_record_key(scope, blob_id): marks a blob's content address as addressing-only.
• Blocklist row, KeyCodec::blocklist_key(scope, keyed_digest): source_id here is not a real source id but a UUID derived from blake3("telha/blocklist/v1" ‖ keyed_digest)[..16], namespaced so it can never collide with a real blob family (blob ids derive from raw canonical hashes).

spans (key_len::SPAN, 64 bytes). Offsets are non-inverted: spans iterate in document order, not latest-first:

[ scope 32 ][ source_id 16 ][ span_start 8 ][ span_end 8 ]
                               total: 64 bytes

traces (key_len::TRACE, 48 bytes):

[ scope 32 ][ query_id 16 ]
              total: 48 bytes

jobs (key_len::JOB, 58 bytes). created_at is non-inverted, deliberately: FIFO within (state, priority) is wanted, not latest-first:

[ scope 32 ][ state 1 ][ priority 1 ][ created_at 8 ][ job_id 16 ]
                                                        total: 58 bytes

Tenant-scoped jobs use KeyCodec::job_key; system-scoped jobs (queue-wide maintenance, not tied to any tenant) use the crate-internal KeyCodec::system_job_key under SystemScope, producing the identical 58-byte shape with a nil 32-byte prefix.

bitmap_index is not in the original spec (it postdates it; see As-built notes) but is fully keyed through the same KeyCodec/TenantScope discipline. It is the one CF with more than one key shape, discriminated by a kind byte (core-engine/src/storage/keys.rs, bitmap_kind module):

common prefix: [ scope 32 ][ label_hash 8 ][ kind 1 ]

kind = 0x00 ALLOC          [ ...prefix... ]                              total: 41 bytes
kind = 0x01 ID_MAP         [ ...prefix... ][ row_id 4 ]                  total: 45 bytes
kind = 0x02 REV_MAP        [ ...prefix... ][ logical_id 16 ]             total: 57 bytes
kind = 0x03 POSTING        [ ...prefix... ][ property_hash 8 ][ bucket_hash 8 ]  total: 57 bytes
kind = 0x04 PROP_COUNTER   [ ...prefix... ][ property_hash 8 ]           total: 49 bytes

• ALLOC: the monotonic row-id watermark for one (tenant, label).
• ID_MAP: row_id -> logical_id, keyed by the 4-byte big-endian row_id.
• REV_MAP: logical_id -> row_id, the inverse map.
• POSTING: a roaring-bitmap posting list for one (property, value-bucket) pair, where value-bucket is either an equality bucket or one of 16 order-preserving range bands.
• PROP_COUNTER: a per-property distinct-value counter, or the overflow marker u32::MAX once the cap is hit.

Length reference¶

Key codec details¶

TenantScope, SystemScope, and nil-UUID rejection¶

pub struct TenantScope { tenant_id: Uuid, organization_id: Uuid } // fields private

impl TenantScope {
    pub fn new(tenant_id: Uuid, organization_id: Uuid) -> Result<Self, KeyError> {
        if tenant_id.is_nil() || organization_id.is_nil() {
            return Err(KeyError::NilScope);
        }
        Ok(Self { tenant_id, organization_id })
    }
}

pub struct SystemScope(pub(crate) ()); // the ONLY producer of [0u8; 32]

TenantScope::new is the only way to build a scope, and it rejects nil components with KeyError::NilScope. As-built, the fields are private with accessors (tenant_id(), organization_id()), which is a deliberate divergence from the spec's §6 sketch of a struct with public fields: public fields would allow literal construction that bypasses the nil check, defeating the unforgeability guarantee the reserved system namespace depends on. SystemScope is pub(crate)-constructible only (via SystemScope::get), so no external request path (REST auth, gRPC metadata, MCP session) can ever produce the all-zero prefix; the only way into the system namespace is code inside the storage module itself.

A third type, KeyScope, exists purely for decoded output: it carries the tenant and organization UUIDs read out of a key (which may legitimately be nil for system keys) for forensics and validation, and cannot be converted back into a TenantScope or used to build a scan.

ScanRange constructors¶

ScanRange holds private start/end byte vectors and is the only type StorageEngine::scan_prefix accepts. Every public constructor takes a TenantScope and derives both bounds from it, so no caller outside the storage module can construct a range that is not tenant-bounded. As read from core-engine/src/storage/keys.rs, the constructors are:

A handful of constructors are pub(crate) because they either touch the system namespace or exist for internal replay/maintenance paths, not for general callers: system_vector_models, system_vector_model_history, system_jobs_in_state, temporal_index_after, tenant_all_after_entity, from_stored_bounds, prefix_successor, and system_full_cf. These are discussed under Algorithms & invariants below, since each one is an explicit, documented exception to the tenant-confinement rule rather than an oversight.

Algorithms & invariants¶

The 32-byte prefix extractor and bloom filters¶

core-engine/src/storage/rocks.rs configures every column family identically at open time:

fn cf_options(name: &str, cache: &Cache) -> Options {
    let mut block = BlockBasedOptions::default();
    block.set_block_cache(cache);
    block.set_bloom_filter(10.0, false);
    block.set_whole_key_filtering(POINT_LOOKUP_CFS.contains(&name));

    let mut opts = Options::default();
    opts.set_block_based_table_factory(&block);
    opts.set_prefix_extractor(rocksdb::SliceTransform::create_fixed_prefix(SCOPE_LEN)); // 32
    opts.set_memtable_prefix_bloom_ratio(0.1);
    opts
}

SCOPE_LEN is 32: the fixed prefix extractor is exactly the [tenant_id][organization_id] scope, which every key in every CF begins with, tenant-scoped or system-scoped. POINT_LOOKUP_CFS names the three CFs answered mostly by point lookups (node_versions, edge_versions, vectors), which additionally get whole-key bloom filtering; every other CF relies on the prefix bloom alone, since it is scan-heavy (adjacency, the two temporal indexes, bitmap_index, and so on).

Successor and range-safety¶

fn successor(bytes: &[u8]) -> Option<Vec<u8>> {
    let mut out = bytes.to_vec();
    for i in (0..out.len()).rev() {
        if out[i] != 0xFF {
            out[i] += 1;
            out.truncate(i + 1);
            return Some(out);
        }
    }
    None
}

successor() returns the smallest byte string strictly greater than every string starting with bytes, by incrementing the last non-0xFF byte and truncating. ScanRange::within_scope uses it to build the upper bound of every scoped range, and falls back to the successor of the scope itself (not the finer prefix) when the finer prefix's suffix is all 0xFF, so a range's end can never overflow past the tenant's own boundary.

Documented exceptions to tenant confinement¶

A small set of pub(crate) constructors deliberately step outside the per-tenant scan model, each recorded in the spec's changelog as a "system-maintenance exception" rather than a silent gap:

• ScanRange::system_full_cf(): the entire key space of one CF, used only by the job-queue reaper to reclaim expired leases across every tenant without a tenant registry. Never derived from external input.
• ScanRange::from_stored_bounds(start, end): rehydrates a range from bounds this crate previously emitted into a GDPR-erasure replay program; the replay executor independently re-verifies tenant confinement before use.
• ScanRange::tenant_all_after_entity(scope, id) and ScanRange::temporal_index_after(scope, cursor_key): pagination cursor helpers that stay inside one tenant's prefix by construction, rejecting a cursor whose prefix does not match the caller's scope.

Nil-UUID rejection as a security boundary¶

TenantScope::new rejecting nil UUIDs is not just input validation, it is the mechanism that makes the reserved system namespace unforgeable. Because UUIDv7 values are never nil, and tenant provisioning independently rejects nil UUIDs, a real tenant can never collide with the all-zero prefix, and because TenantScope::new itself rejects nil, no code path that authenticates an external caller into a TenantScope can ever produce it either.

Configuration¶

Per the spec (§8), no key-layout element is runtime-configurable. Layout changes require a new spec and a migration plan, because stored keys carry no version byte (stored values do, landing with PR-013): a future key change is a rewrite migration by design, a cost the spec accepts deliberately since key stability underlies every index.

As-built notes¶

From spec §14 (Changelog), reconciled against the code actually in core-engine/src/storage/:

• bitmap_index is a 13th CF added after this spec's v0.1/v0.2/v0.3 entries. The spec's own architecture diagram (§4) and the RocksDB module's doc comment both still say "12 standard column families," but cf::ALL in core-engine/src/storage/mod.rs lists 13, and core-engine/src/storage/bitmap.rs implements a full key family for it under the bitmap-predicate-index spec. Treat "12" in this spec's prose as stale; the code and cf::ALL are the current count.
• v0.2 (2026-07-02): the nil-tenant system namespace was adopted, resolving OQ-3. SystemScope and the unforgeability guards (TenantScope::new nil rejection, pub(crate)-only construction) are present in keys.rs exactly as described.
• v0.3 (2026-07-03): a system-maintenance exception to invariant 4 added ScanRange::system_full_cf, pub(crate), for the job-queue reaper. Present in the code as documented, gated to crate-internal use.
• v0.4 (2026-07-03): the embedding-model registry reuses the 48-byte schema CF shape under the system prefix. KeyCodec::vector_model_key, ScanRange::system_vector_models, and ScanRange::system_vector_model_history all exist in keys.rs exactly as the changelog describes, all pub(crate).
• v0.5 (2026-07-06): the GDPR reserved sources-CF rows (§3.7 addendum) reuse the 56-byte sources shape at REDACTION_CHUNK_INDEX = u64::MAX. KeyCodec::redaction_record_key and KeyCodec::blocklist_key both exist in keys.rs exactly as described, including the blake3-derived, namespaced blocklist id. The corresponding ScanRange::tenant_all reuse and ScanRange::from_stored_bounds crate-internal rehydration are present as well.
• Not directly verifiable in the storage code alone: the spec's success metrics (§12), namely "100% of iterator/scan call sites pass the CI grep-gate," the "3-tenant dataset, zero cross-prefix rows" integration test, and the 24-hour fuzz run, are process and CI claims. The proptest suite that backs the ordering and confinement invariants is present and readable in core-engine/src/storage/keys.rs, but the CI grep-gate itself and the fuzz target live outside core-engine/src/storage/ and were not inspected for this page.
• The spec's §6 API sketch shows TenantScope with public fields; the as-built type has private fields with accessors, a deviation the module doc in keys.rs calls out directly (public fields would allow bypassing the nil check).
• describe_bitmap_key in core-engine/src/storage/keys.rs and the telha debug decode-key forensics path described in spec §7 both exist, dispatched from describe_key in core-engine/src/storage/mod.rs by CF name for every CF including bitmap_index.

Related¶

• The version record model
• Temporal write & read paths
• Global temporal scan
• Tombstone cascade
• Concepts › The tritemporal model