Spec 0026 — Optional Entity Keys

Status: Normative v1, reference Dataset/Python/WASM paths (#322 / OQ-88). The default time-series format and existing time anchors are unchanged.

1. Identity and scope

A Dataset MAY enable one typed entity-key namespace on its single Timeline. The key identifies a logical entity; its current anchor is only a physical position. Enabling the namespace does not infer keys from existing scalar ids or claim that historical unkeyed Items have keys. Existing Items remain readable.

Key kind is one of string, bytes, int. Strings are exact UTF-8, without normalization or case folding; bytes are opaque; int is signed i64. Empty strings/bytes are legal. String/byte keys are limited to 4096 bytes. Booleans, floats, null and lossy numeric coercions are not integer keys. Key type cannot change after enabling the namespace.

An entity has a random 16-byte entity_id, stable across supersession, deletion and explicit restoration. Every state change obtains a fresh random 16-byte revision. Revisions are not payload hashes, timestamps or arithmetic counters: an A → B → A content change must not restore an earlier expected token. A derived/async producer must pin the source entity revision it read; matching a time anchor or old content hash is not an expected-revision check.

2. Mandatory wire boundary

Keyed Manifests use tracks.form = "lineage-v4". This is not an OPTIONAL extension of v1/v2 or the encrypted v3 wrapper. Its CLOSED keys are exactly form, active, lineage, edges, backfill_claims; it inherits all v2 graph, claim, canonical ordering and 1 MiB container bounds. v4 additionally requires exactly one Timeline and one registry entry dreamdb.entity_keys, whose value is a 33-byte multihash of the key index. No alias or duplicate occurrence is permitted. v1/v2 MUST NOT carry this critical entry. Readers/writers/collectors that do not support v4 MUST refuse before interpreting or transforming it, never fall back to time-only semantics. Existing v1/v2 bytes are unchanged.

The auxiliary Object is addressed at entity-key-index/<hash>; it is not a Track or a new ObjectKind. Its canonical CBOR map is CLOSED:

{
  "version": 1,
  "timeline": <bstr multihash>,
  "key_kind": "string" | "bytes" | "int",
  "entries": [
    [<typed key>, <bstr(16) entity_id>, <bstr(16) revision>, <u64 anchor>, <bool deleted>],
    ...
  ]
}

Entries are strictly ordered by the unsigned lexicographic canonical CBOR bytes of the key; duplicate keys, entity ids, revisions or anchors are refused. Each tuple has exactly five positions. Kind/type mismatch, malformed token, unknown/missing/duplicate map key, unknown version and noncanonical encoding are refused. An index must name the enclosing Manifest's Timeline. Its maximum canonical size is 16 MiB; v1 has no paging form. Refuse before writing an update that cannot fit, rather than publishing a partial index. This initial reference implementation does not claim a billion-key index or bounded-memory lookup.

The index has no Item payload or downstream Object references; anchors locate data through the Manifest's ordinary field Tracks. timeline identifies the existing Genesis. A collector MUST verify and mark the key index from every retained keyed root, as well as all ordinary Track/tombstone/lineage references. Changing a key index never authorizes reclaiming historical payloads.

3. Operations and optimistic concurrency

get_entity returns no record for a never-created key. Otherwise it returns entity id, revision, last anchor, deletion state, and the live Sample when not deleted. A deleted record remains an explicit state, not a reusable empty slot. Lookup is bound to the handle's immutable Manifest, just like other reads; reopen to observe another writer's publication.

Create requires a never-created key. Upsert/supersede of an existing key requires its exact current revision. Supersede additionally requires a live entity; upsert with the deleted revision explicitly restores it. Delete requires the current live revision and changes both key state and tombstone state. Missing or stale expected revisions are conflicts, not blind last-writer-wins.

Each operation binds one current Ref, validates key/revision and the complete Sample, then publishes the new key index, field Track changes and old-anchor tombstone in one Manifest/Ref compare-and-swap. No intermediate lookup/write publication is visible. On failure the caller's handle remains on its previous state; a CAS race may leave unreachable content-addressed Objects for normal GC. There is no automatic retry that reinterprets a stale expected revision.

New versions use fresh explicit physical anchors, strictly beyond all existing field extents and prior entity positions. v1 keyed reads use the existing nanosecond range API, so anchors are below i64::MAX; refuse exhaustion rather than wrap or round. Old anchors are tombstoned, not overwritten. Historical Manifests retain their old key mapping and values; deletion is logical, not physical erasure. The entity key itself is metadata and is not secretly copied into a scalar field or inferred from a Sample value.

The public entity writer allocates this anchor: a supplied Sample anchor is rejected, not silently replaced. At least one non-constant stored field must be present, so the resulting physical row is observable through normal reads. The token protects the key's physical revision; independent Schema/index maintenance is not a new entity revision or a compare-and-swap on the Schema.

Lineage-v4 does not include the separate Lineage-v3 encryption policy. This revision does not define their combination; unsupported combinations refuse instead of attaching an ignorable policy or key index.

Ordinary append/hot append and anchor-only deletion on a keyed Dataset must refuse: callers use keyed operations so physical mutations cannot leave the key mapping or revision token stale. A batch is not partly converted. Schema evolution/index maintenance may preserve the namespace without changing keys; compaction preserves anchors and values and carries the exact key index.

4. Branches and merge

Fast-forward may preserve an exact keyed Manifest. For v1 key-index union, both sides must carry the same key-index hash (and same key mode); otherwise merge refuses before any publication. In particular two branches creating or changing the same key never resolve by branch order, timestamp, or last-wins. This conservative initial policy also refuses disjoint divergent key updates; it does not claim a key-aware three-way reconciliation algorithm. Operators replay an explicitly chosen update against a newly opened tip with its expected revision. A blind drop of the namespace is not a merge resolution.

5. SDK and evidence boundary

Rust, Python and WASM expose the same enable/get/create/upsert/supersede/delete operations and exact 16-byte revision tokens. Payload validation remains the existing Dataset validation, not a second entity-specific field codec.

The minimum behavioral evidence creates and reads a key, supersedes it while an old Manifest still reads the old revision, deletes it, and rejects stale concurrent or merged duplicate-key changes. Codec evidence distinguishes the canonical key-index form from malformed/duplicate keys. No identity account, authorization, per-subject encryption or selective erasure is implied.