IncrementalGraph internal node identifiers
Purpose
This document defines the node-addressing model for IncrementalGraph storage, filesystem snapshots, and the HTTP inspection API.
This model separates three concerns:
NodeKeyis the semantic identity of a concrete node instanceNodeIdentifieris the persisted storage identity of a materialized node- filesystem snapshots and internal storage operate directly on stored identifiers
This document defines the node-addressing model for IncrementalGraph storage, filesystem snapshots, and the HTTP inspection API as implemented.
Terms
- NodeKey: the schema-derived identity of a concrete node instance, based on
(head, args) - NodeIdentifier: the deterministic persisted identifier attached to a materialized node
- graph-state sublevels:
values,freshness,valid,timestamps
Boundary
Public concrete-node operations remain NodeKey-addressed (head + args / NodeKey).
IncrementalGraph is the conversion boundary:
- Public callers and HTTP routes provide semantic keys (
head + args/NodeKey). - At public method entry,
IncrementalGraphresolves toNodeIdentifierimmediately. - All logic below that boundary (storage, recompute, invalidation propagation, migration, sync, render, scan) is identifier-native.
nodeKeyToId(nodeKey) and nodeIdToKey(id) are internal/lower-level translation helpers,
not public IncrementalGraph methods and not HTTP API operations.
Required workflow
Upstream/public workflow stays semantic:
await graph.pull(head, args);
await graph.invalidate(head, args);
Internal workflow converts once at the boundary, then stays identifier-native.
No mixed model is allowed where storage-layer concrete-node operations remain NodeKey-addressed after boundary conversion.
Schema/head APIs
Schema-family APIs may remain head/schema-oriented where they are genuinely schema-level operations rather than concrete-node operations.
Migration API boundary
Migration code is internal storage logic, so migrations are fully NodeIdentifier-addressed.
- Migration callbacks must receive and return concrete-node references as
NodeIdentifiervalues. - Migration-produced
validmust contain onlyNodeIdentifiervalues. - Migration control decisions (
keep,replace,invalidate,create,delete) operate onNodeIdentifier-addressed state, withNodeKeyused only via the lookup bijection when needed for schema/head filtering or inspection.
There is no mixed-mode migration API: NodeKey-addressed migration payloads are out of scope and unsupported.
HTTP inspection API
HTTP concrete-node routes remain head + args based to preserve existing API behavior.
- Route addressing remains semantic (
head + args). - Handlers call the public graph API in semantic form.
- Identifier conversion happens inside
IncrementalGraphat the same boundary as non-HTTP callers. NodeIdentifieris not exposed as required request-addressing for public graph routes.
NodeIdentifier requirements
A NodeIdentifier is a deterministic, globally-namespaced identifier with the
following properties:
- globally and forever unique
- stable for the lifetime of that materialized node in storage
- round-trippable as a nominal type
- suitable for direct use as persisted key content and as a filesystem path segment
- matches
/^[0-9a-z]+-[a-z]{9,}$/(full-string match)
Format
<base36-local-node-index>-<fingerprint>
- The index prefix is a base36 integer (characters
0-9a-z), no padding or alignment. - The fingerprint is a lowercase ASCII string of at least 9 characters (
[a-z]{9,}). - The separator is a single hyphen
-.
Character set
Allowed characters in a NodeIdentifier:
- lowercase ASCII letters
a-z - digits
0-9 - hyphen
-(as separator between index and fingerprint)
No other characters are permitted. In particular, a
NodeIdentifier MUST NOT contain /, \, ., whitespace, control characters, !,
or any other punctuation besides the single separator hyphen.
Format is specification-only
The format regex /^[0-9a-z]+-[a-z]{9,}$/ is a specification invariant only.
Runtime code does not validate the documented format at internal conversion
boundaries. Every identifier in the system originates from makeNodeIdentifier(),
which assembles it from components that are valid by construction (a fingerprint
validated at lifecycle boundaries and a local allocation index). No supported
lifecycle transition introduces externally-sourced identifier strings (see
docs/specs/database-lifecycle.md §4, §5, §11–12), so runtime validation at
internal boundaries would be redundant.
Example values
1-abcdefghi2-abcdefghiz-abcdefghi10-abcdefghi
Allocation
Identifiers are allocated as ${nextIndex.toString(36)}-${fingerprint} where
nextIndex is a monotonic counter starting at 1 and fingerprint is the
machine-local database fingerprint (see docs/specs/incremental-graph-fingerprint.md).
Gaps in the index sequence are acceptable (caused by failed or interleaved
transactions). The last_node_index watermark tracks the largest committed index.
Persisted storage model
All persisted graph state addresses nodes by NodeIdentifier, not by NodeKeyString.
This applies to:
- keys in all graph-state sublevels
- values inside
valid - all migration callback payloads and migration-produced state
- filesystem-rendered snapshots
Graph-state sublevels
values[id] -> ComputedValuefreshness[id] -> Freshnesstimestamps[id] -> TimestampRecordvalid[id] -> NodeIdentifier[]
Storage invariants
- graph-state sublevel keys are
NodeIdentifier valid[id]containsNodeIdentifier[]- validity sets are sorted by
NodeIdentifier(lexicographic), never byNodeKey - render/scan paths use direct identifier path segments
- graph-state path encoding/decoding must not reconstruct
NodeKeyvalues NodeKeyStringmay persist only inside explicit lookup metadata (identifiers_keys_map)
Lookup metadata
The database contains an explicit bijection between the semantic identity and the persisted identity:
nodeKeyToId(nodeKey) -> idnodeIdToKey(id) -> nodeKey
These functions operate on the active representation's global/identifiers_keys_map database value.
NodeKeyString may remain persisted only in this lookup table.
The map is the materialized-node identity table, with a strict invariant:
- contains every materialized node;
- contains only materialized nodes.
Lifecycle rules:
NodeIdentifierallocation happens when a node becomes materialized (not on arbitrary key mention/lookups).nodeKeyToId(nodeKey)is an internal lookup helper and must not allocate for non-materialized nodes.- if
nodeKeyToId(nodeKey)is called for a non-materialized node, it returns missing (or equivalent lookup-miss error/value). - the materialization write path is responsible for atomically inserting both graph-state records and id↔key entry.
- node deletion/de-materialization path is responsible for atomically removing both graph-state records and id↔key entry.
validmay reference only materialized-node identifiers; it must never require lookup entries for non-materialized nodes.- migration/render/scan/sync validation must fail fast if any graph-state id lacks a key entry, or if any key entry exists without materialized graph-state presence.
Allocation and stability
Every materialized node has exactly one NodeIdentifier.
When a concrete NodeKey becomes materialized:
- if it already has an identifier, that identifier is reused
- otherwise a fresh identifier is allocated using the current local node index
and the database fingerprint:
${nextIndex.toString(36)}-${fingerprint} - the new identifier is recorded in both lookup sublevels and the
last_node_indexwatermark is advanced
Recompute, invalidate, cache-hit, and migration-preserve flows keep the existing identifier.
Delete removes:
- all graph-state records keyed by
id nodeKeyToId(nodeKey)nodeIdToKey(id)
Migration preserves identifiers for keep, replace, and invalidate, and
allocates fresh identifiers for create using the same fingerprint/index scheme.
In particular, replace changes the semantic value occurrence without changing
the materialized node's NodeIdentifier; its new Journal ValueId is distinct
from that storage identity. The migration decision semantics are owned by
incremental-graph-journal-migrations.md §11.
last_node_index
The last_node_index watermark (see docs/specs/incremental-graph-last-node-index.md)
is stored at the active replica's global sublevel under the key "last_node_index".
It is a monotonic allocation watermark, not a node count. Gaps are acceptable.
Determinism
valid stores NodeIdentifier[] in ascending lexicographic order of the identifier
string itself.
NodeKey is not consulted when ordering validity lists. All internal
sorting operates on NodeIdentifier values directly.
Bijection cache
The full contents of the lookup table are loaded into RAM and kept synchronized as an in-memory
cache. All lookups between NodeKey and NodeIdentifier go through this cache, not through direct
database reads at call time.
The cache is authoritative for the bijection while the database is open. Writes to the lookup sublevels and updates to the cache are atomic from the perspective of the storage layer.
Filesystem snapshot format
render() and scan() operate on identifier-addressed graph-state paths.
Each graph-state record appears at a direct identifier path, for example:
rendered/r/values/nodeid1
and analogously for the other graph-state sublevels:
rendered/r/freshness/nodeid1rendered/r/valid/nodeid1rendered/r/timestamps/nodeid1
Lookup metadata remains explicit and separate:
- the active representation's
global/identifiers_keys_map
The snapshot format therefore exposes graph-state records directly by identifier and uses the lookup table for semantic readability.
No key↔path conversion
Outside the explicit lookup-metadata table, there must not be any code whose job is to convert concrete node keys to filesystem paths or to reconstruct concrete node keys from filesystem paths.
This prohibition applies to graph-state addressing and covers both:
- dedicated helper functions for
NodeKey ↔ pathconversion used for graph-state files - incidental logic embedded inside render/scan/unification code that reconstructs a
concrete
NodeKeyfrom graph-state path segments or encodes one into graph-state path segments
The following lookup-metadata path is explicitly exempt from this prohibition:
- the active representation's
global/identifiers_keys_map
This path may encode or decode NodeKey values for the sole purpose of reading and
writing the lookup tables. They must not be treated as a general filesystem addressing
scheme for graph-state records.
Accordingly:
- graph-state filesystem paths are direct identifier paths
- scan consumes those direct identifier paths
- render writes those direct identifier paths
- any
NodeKey ↔ pathlogic is limited to the lookup-metadata namespace above
API invariants
- public
IncrementalGraphmethods remain semantic (NodeKey/head + args) pull,invalidate,unsafePull,unsafeInvalidate,getValue,getFreshness, and timestamp/inspection helpers are all semantic at the public boundaryIncrementalGraphconverts toNodeIdentifierimmediately at method entry- concrete-node read/write/recompute/invalidate/delete/inspection/storage operations below that boundary use
NodeIdentifier nodeKeyToId(nodeKey)andnodeIdToKey(id)are internal translation helpers, not public graph-interface methods- HTTP concrete-node routes remain semantic (
head + args) - migration APIs are identifier-based internally
- no mixed model below the boundary is allowed
Invariants
For every materialized node identifier id:
nodeIdToKey(id) = keynodeKeyToId(key) = id- all graph-state records for that node are keyed by
id - every entry inside
valid[id]is a validNodeIdentifier
No persisted graph edge may point directly to a NodeKeyString.
Corruption conditions
The following states are invalid:
nodeKeyToId(key)exists butnodeIdToKey(id)is missingnodeIdToKey(id)exists butnodeKeyToId(key)is missing- lookup entries disagree about each other
- a graph-state record exists for an id with no
nodeIdToKey(id)entry validmentions an unknown id