Spec: Composite Key Layout & Tenant-Scoped Key Encoding¶

File: .ai/specs/core-engine/2026-07-02-composite-key-layout.md Status: Draft — for peer review before PR-011 opens Owners: Storage lane Related: PR-011 (key codec), PR-012 (RocksDB engine), PR-016 (secondary indexes), PR-017 (adjacency), F1 resolution

1. Overview¶

Defines the exact byte layout of every RocksDB key in Telha Core, the encoding rules that make byte order equal logical order, and the API surface (KeyCodec, TenantScope, ScanRange) that is the only legal way to construct keys or scan bounds anywhere in the codebase. This spec is the normative source for F1: tenant isolation true-by-construction.

2. Problem Statement¶

Tenant isolation, temporal ordering, and traversal performance all depend on key bytes. Prefix bloom filters are a performance structure, not a security boundary — isolation holds only if every read path constructs 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. Additionally, "latest version first" iteration requires timestamps to sort descending under RocksDB's ascending byte comparator, which demands a documented inversion rule applied identically everywhere.

3. Proposed Solution¶

A single core-engine/src/storage/keys.rs module exports:

• TenantScope { tenant_id: Uuid, organization_id: Uuid } — the mandatory first parameter of every codec function; serializes to a fixed 32-byte prefix.
• KeyCodec — pure encode/decode functions, one pair per column family. All raw-byte constructors are pub(crate) within the storage module only.
• ScanRange — the only way to obtain iterator bounds. Every constructor derives [prefix, successor(prefix)) from a TenantScope plus typed components; there is no public API accepting raw start/end bytes.

Enforcement layers: (a) visibility (pub(crate)), (b) CI grep-gate rejecting raw_iterator/iterator( outside src/storage (PR-003 commit 4), (c) proptest invariants that every generated ScanRange lies within its tenant prefix, (d) cargo-fuzz target on the decoder.

3.7 GDPR erasure reserved sources-CF rows (addendum, PR-081)¶

The gdpr-erasure spec (2026-07-02) reserves two new row shapes in the sources CF, both reusing the existing 56-byte SOURCE key shape [scope][id][inv txStart 8] with the reserved slot REDACTION_CHUNK_INDEX = u64::MAX (so inv(u64::MAX) = 0 sorts them FIRST within their family; real canonical-text chunk indexes are dense from 0 and can never collide):

• Blob redaction record at (scope, blob_id, u64::MAX) — KeyCodec::redaction_record_key. Value: {ranges, ledger_entry_ids, post_redaction_hash, original_hash_retired, deleted}. Marks the blob's content address as addressing-only (gdpr-erasure §3.2).
• Blocklist row at (scope, derived_id, u64::MAX) — KeyCodec::blocklist_key, where derived_id is a UUID from blake3("telha/blocklist/v1" ‖ keyed_digest)[..16] under a dedicated namespace so it can never collide with a real blob family (blob ids derive from raw canonical hashes). Value: the keyed-digest blocklist row (gdpr-erasure §3.4).

Verification scan under the §5.3 system-maintenance exception. The gdpr-erasure verification scan (§3.8) runs one whole-tenant-prefix pass per CF via ScanRange::tenant_all (already tenant-bounded), and the restore-replay executor rehydrates program-recorded scan bounds via a crate-internal ScanRange::from_stored_bounds that re-checks tenant confinement before use — the same reaper-class exception recorded for the job reaper and the retention whole-store discovery scan. No new externally reachable raw-bounds surface.

4. Architecture¶

callers (temporal, graph, query, jobs, vector)
        │  typed requests only (TenantScope + ids + times)
        ▼
KeyCodec / ScanRange  ←— sole key authority (this spec)
        ▼
StorageEngine trait (get / scan_prefix / batch_write)
        ▼
RocksDbEngine (prefix extractor = 32 bytes, bloom filters per CF)

5. Data Models¶

5.1 Primitive encodings (normative)¶

All keys begin with the 32-byte tenant prefix: [tenant_id (16)][organization_id (16)].

Reserved system namespace (OQ-3, ratified 2026-07-02): the all-zero prefix [0u8; 32] is the system/nil-tenant scope, used for system-level entries (initially: system jobs in the jobs CF). Properties: fixed-width guarantees preserved; system rows sort deterministically to the absolute head of each CF (fast system-job polling via a single bounded scan from the zero prefix); zero parsing exceptions. Guards: (a) UUIDv7 values are never nil, and tenant provisioning must additionally reject nil UUIDs explicitly, so collision with a real tenant is impossible; (b) the nil scope is unforgeable externally — TenantScope::new() rejects nil components, auth middleware can never resolve any API key or gRPC token to the nil scope, and only the internal SystemScope constructor (pub(crate) in the storage module) can produce it. Without guard (b), the system namespace would be an escalation target.

5.2 Key layouts per column family¶

node_versions     [32B scope][logicalId 16][inv(validTimeStart) 8][inv(txTimeStart) 8]                       = 64B
edge_versions     [32B scope][edgeLogicalId 16][inv(validTimeStart) 8][inv(txTimeStart) 8]                   = 64B
adjacency_out     [32B scope][fromId 16][edgeTypeHash 8][inv(validTimeStart) 8][inv(txTimeStart) 8][toId 16] = 88B
adjacency_in      [32B scope][toId 16][edgeTypeHash 8][inv(validTimeStart) 8][inv(txTimeStart) 8][fromId 16] = 88B
valid_time_index  [32B scope][inv(validTimeStart) 8][inv(txTimeStart) 8][logicalId 16][kind 1]               = 65B
tx_time_index     [32B scope][inv(txTimeStart) 8][inv(validTimeStart) 8][logicalId 16][kind 1]               = 65B
vectors           [32B scope][nodeLogicalId 16][embeddingModelId 8][inv(validTimeStart) 8][inv(txTimeStart) 8] = 72B
schema            [32B scope][labelHash 8][inv(txTimeStart) 8]                                               = 48B
sources           [32B scope][sourceId 16][inv(txTimeStart) 8]                                               = 56B
spans             [32B scope][sourceId 16][spanStart 8][spanEnd 8]                                           = 64B
traces            [32B scope][queryId 16]                                                                    = 48B
jobs              [32B scope][state 1][priority 1][createdAt 8][jobId 16]                                    = 58B

Notes: - kind byte in secondary indexes distinguishes node (0x00) vs edge (0x01) entries so one index serves both version CFs. - Secondary-index values are the primary-CF key (covering index) — validation is a point lookup, never a scan. - jobs uses non-inverted createdAt: FIFO within (state, priority) is wanted, not latest-first. - All keys are fixed-width. No variable-length components exist in v1; if one ever becomes necessary it must be length-prefixed and this spec amended first.

5.3 Ordering invariants (tested by proptest in PR-011)¶

1. Encode is injective; decode(encode(x)) == x for all valid inputs.
2. For fixed (scope, logicalId): later validTimeStart sorts strictly earlier (latest-first).
3. Tie on validTimeStart: later txTimeStart sorts earlier.
4. Every ScanRange satisfies scope_prefix ⊑ start and end == successor_within_prefix(start-component); no range may cross the 32-byte prefix boundary.
5. successor() handles the all-0xFF carry case by tightening to the exact prefix upper bound (never overflowing into the next tenant).

6. API Contracts¶

pub struct TenantScope { pub tenant_id: Uuid, pub organization_id: Uuid }
// TenantScope::new() returns Err(KeyError::NilScope) if either component is nil.

pub(crate) struct SystemScope;   // the ONLY producer of the [0u8;32] prefix; not constructible outside storage

impl KeyCodec {
    pub fn node_version_key(s: &TenantScope, id: Uuid, valid_start: Ts, tx_start: Ts) -> Key;
    pub fn node_prefix(s: &TenantScope, id: Uuid) -> ScanRange;                 // entity-scoped history
    pub fn valid_time_from(s: &TenantScope, t: Ts) -> ScanRange;                // global "valid at T" scan start
    pub fn adjacency_out_prefix(s: &TenantScope, from: Uuid, ty: Option<EdgeTypeHash>) -> ScanRange;
    // ... one constructor per legal access pattern; NO raw-bytes constructor is public
}

pub struct ScanRange { /* fields private; consumed only by StorageEngine::scan_prefix */ }

Decoding failures return KeyError::{WrongLength, BadUuid, UnknownKind} — never panic (fuzz-enforced).

7. UI/UX¶

Not applicable (internal). Debug tooling: telha debug decode-key <cf> <hex> CLI subcommand renders any key human-readably; ships in PR-011 for operator forensics.

8. Configuration¶

• RocksDB per-CF: prefix_extractor = fixed(32), memtable_prefix_bloom_size_ratio = 0.1, whole-key bloom off on scan-heavy CFs (adjacency, indexes), on for point-lookup CFs (versions, vectors).
• No key-layout element is runtime-configurable. Layout changes require a new spec + migration plan (Section 11).

9. Alternatives Considered¶

• Little-endian timestamps — rejected: byte order would not equal numeric order; every scan would need a custom comparator.
• String/hex UUIDs — rejected: 2.2× key size, breaks fixed-width guarantees.
• Custom RocksDB comparator for descending time — rejected in favor of inversion: comparators complicate tooling, backups, and any future FoundationDB backend (EPIC-401), which has no pluggable comparator.
• Per-tenant column families or DBs — rejected for v1: unbounded CF count harms compaction and memory; prefix isolation + F1 enforcement achieves the guarantee. Revisit for noisy-neighbor isolation in EPIC-403.
• Hashed tenant prefix (siphash of tenant+org) — rejected: destroys the ability to range-scan a tenant's data for export/GDPR erasure workflows.

10. Implementation Approach¶

PR-011 commits 1–6 as planned: spec (this file) → TenantScope → KeyCodec → ScanRange → proptest suite → fuzz target. PR-012 consumes the codec; no other PR may touch key bytes.

11. Migration Path¶

Greenfield — no live data. Forward-compatibility: stored values carry a version byte (PR-013); stored keys do not, so any future key change is a rewrite migration by design. That cost is accepted deliberately: key stability is the foundation of every index.

12. Success Metrics¶

• 100% of iterator/scan call sites pass the CI grep-gate (zero exemptions).
• Proptest ordering invariants (§5.3) green across ≥10⁶ generated cases in CI.
• Fuzz decoder: 24h run, zero panics.
• Tenant-isolation integration test (PR-012 commit 7): 3-tenant dataset, zero cross-prefix rows returned across the full access-pattern matrix.
• Nil-scope unreachability test: no external request path (REST auth, gRPC metadata, MCP session) can produce a read or write under the [0u8;32] prefix; system-job polling reads it via SystemScope only.

13. Open Questions¶

• OQ-1: Should edge_type_hash be widened to 16 bytes if the collision registry ever fires in practice? (Current stance: 8B xxh3 + fail-loud registry is sufficient; revisit on first collision.)
• OQ-2: GDPR erasure vs append-only immutability — physical deletion of a tenant prefix (range-delete) is compatible with this layout, but the erasure procedure needs its own spec before GA.
• OQ-3: Does jobs belong under tenant scope, or should system-level jobs use a reserved nil-tenant prefix? Resolved 2026-07-02: reserved all-zero [0u8;32] system namespace adopted — see §5.1 for semantics and the unforgeability guards. PR-030's job-queue spec inherits this.

14. Changelog¶

• 2026-07-06 — v0.5: GDPR reserved sources-CF rows (§3.7 addendum, PR-081): the blob redaction record and the erased-content blocklist row both reuse the 56-byte SOURCE shape at reserved chunk index u64::MAX (redaction_record_key, blocklist_key); blocklist ids are namespaced (blake3("telha/blocklist/v1"‖keyed_digest)) so they never collide with a real blob family. The verification scan runs under the §5.3 system-maintenance exception (whole-tenant-prefix passes via tenant_all; replay rehydrates program bounds via crate-internal from_stored_bounds with a tenant-confinement re-check). No new external raw-bounds surface; OQ-2's "erasure needs its own spec" is now answered by the gdpr-erasure spec.

• 2026-07-03 — v0.4: second nil-namespace use (PR-038): the embedding-model registry stores deployment-global, tx-versioned rows in the schema CF under the system prefix ([nil 32][modelId 8][inv tx 8], the same 48-byte shape as tenant schema rows; modelId = xxh3("vector_model/"+name)). Constructors (vector_model_key, system_vector_models, system_vector_model_history) are pub(crate) and reachable only from the registry ops and the telha vector CLI — no external request path. Tenant scans cannot reach the nil prefix (§5.3 invariants unchanged).

• 2026-07-03 — v0.3: system-maintenance exception to §5.3 invariant 4: the job-queue reaper (PR-030) sweeps expired leases across all tenants via a crate-internal full-CF ScanRange constructor (system_full_cf, pub(crate), jobs CF maintenance + future GDPR-erasure class operations only). No external request path can construct or influence it; every tenant-scoped constructor remains bound by the §5.3 invariants and the property tests.

• 2026-07-02 — v0.2: OQ-3 resolved — nil-tenant system namespace [0u8;32] adopted with unforgeability guards (SystemScope internal-only, nil rejection in TenantScope::new() and tenant provisioning); nil-scope unreachability added to success metrics. PR-012 unblocked.

• 2026-07-02 — v0.1 initial draft for peer review (implements F1 ratified resolution).