Persistent Layer

Persistent Layer

The persistent layer stores the graph's nodes, edges, and properties on disk. It is modular and configuration-driven: a single implementation covers different needs through profiles rather than separate code paths (see General Concepts). The first profile under development is the Small Profile.

Component	Status
Node Store (Option 2, u32 IDs)	Implemented (v1)
Property / Edge Store	Implemented (v1)
Value type encoding	Implemented (v1)
Index (CSR adjacency)	Implemented (v1)

Node Store (implemented)

File format

Little-endian throughout. Direct access by ID: offset = HEADER_LEN + id × 12.

[Header  16 B]   magic(4) + version(2) + flags(2) + record_size(2) + id_bytes(1) + pad(5)
[Record  12 B]*  one record per node, in ID order
[Footer  20 B]   count(8) + flags(4) + crc32(4) + magic(4)

Node record layout (12 bytes)

offset 0  u8   flags      bit7=DEAD, bit6=HAS_IN, bit5=HAS_OUT, bit4=HAS_PROP, bits0-3=subtype
offset 1  u8   reserved
offset 2  u16  reserved
offset 4  u32  type_id    NodeId::MAX = no type (untyped node)
offset 8  u32  first_out  NodeId::MAX = no edges/properties in the property store

NodeId is u32. NodeId::MAX (0xFFFF_FFFF) is the sentinel for "no reference" — ID 0 is a valid node.

On open, the CRC32 of the full record region is verified. A corrupt or unrecognised header/footer is rejected with an error.

Rust API

use mgraphdb::node_store::{NodeFlags, NodeId, NodeRecord, NodeStore, NO_ID};

let mut store = NodeStore::new();

// Class node (plain node used as a type)
let person_class = store.create();

// Instance node typed as Person
let alice = store.create_typed(person_class);

// Update flags when an edge is added later
store.update(alice, NodeRecord {
    flags: NodeFlags::default().set(NodeFlags::HAS_OUT),
    type_id: person_class,
    first_out: 0, // first record ID in property store (TBD)
});

store.tombstone(alice);          // soft delete
store.save("nodes.seg")?;
let loaded = NodeStore::open("nodes.seg")?;

Design notes

• Option 2 of REQ-32 — nodes in a dedicated file, separate from the property/edge store.
• 12 bytes per record keeps the Small Profile file small: 1 M nodes ≈ 12 MB.
• first_out points to the first record in the property store (linked-list head for outgoing edges/properties).
• live_count() counts non-tombstoned records; len() counts all (including dead).

---

Property / Edge Store (implemented)

Edges and properties share a single store. Each record is exactly 16 bytes, giving offset = HEADER_LEN + id × 16 for O(1) access by PropId.

File format

Little-endian throughout.

[Header  16 B]   magic(4) + version(2) + flags(2) + record_size(2) + id_bytes(1) + pad(5)
[Record  16 B]*  one record per property/edge, in PropId order
[Footer  20 B]   count(8) + flags(4) + crc32(4) + magic(4)

Record layout (16 bytes)

byte  0      PropType (u8)    value-type discriminant
byte  1      extra    (u8)    InlineStr: byte length; others: 0
bytes 2-5    key      (u32)   property name / edge predicate NodeId (NO_KEY = unkeyed)
bytes 6-15   data    [10 B]   value payload (see per-type encoding below)

Every record carries a key (NodeId): the property name, or the edge predicate / label. The key is itself a node ("everything is a node", RDF-predicate style) and is optional — NO_KEY (NodeId::MAX) means unkeyed. The value payload is the remaining 10 bytes, so inline strings hold up to 10 UTF-8 bytes; longer strings route to the String Store.

PropType discriminants and encoding

PropType	data encoding
Edge	data[0..4] = end_node (u32)
None	zeros
Bool	data[0] = 0 or 1
I64	data[0..8] = i64 (little-endian)
I128Ref	data[0..8] = StrId → 16-byte integer in String Store
F64	data[0..8] = f64 bit pattern
F128Ref	data[0..8] = StrId → 16-byte float in String Store
Date	data[0..8] = days since 1970-01-01 (i64)
Time	data[0..8] = nanoseconds since midnight (u64)
DateTime	data[0..8] = seconds since Unix epoch (i64)
Duration	data[0..8] = seconds (i64)
Uuid	data[0..8] = StrId → 16-byte UUID in String Store
Hash	data[0..8] = StrId → hash bytes in String Store
Geo	data[0..8] = StrId → lat+lon packed as two f64 values
InlineStr	extra = byte length (0–10), data[0..extra] = UTF-8
StringRef	data[0..8] = StrId → string in String Store
UrlRef	data[0..8] = StrId → URL in String Store

(data is the 10-byte value payload at bytes 6–15; offsets above are relative to it.) Values needing more than 10 bytes (i128, f128, UUID, Geo, hashes, and strings over 10 bytes) are stored in the String Store and referenced by StrId (REQ-37). The linked-list head is in NodeRecord.first_out, so the record needs no next-pointer overhead.

Rust API

use mgraphdb::prop_store::{PropStore, PropRecord, PropValue, NO_KEY};
use mgraphdb::string_store::StrId;

let mut store = PropStore::new();

// Edge labelled `knows` (a NodeId) from the owner → node 1.
let e = store.create(&PropRecord::new(knows, PropValue::Edge { end_node: 1 })).unwrap();

// Property: name = "Alice" (inline, ≤ 10 bytes), keyed by the `name` node.
let p1 = store.create(&PropRecord::new(name, PropValue::InlineStr("Alice".to_owned()))).unwrap();

// Unkeyed property: age = 30
let p2 = store.create(&PropRecord::unkeyed(PropValue::I64(30))).unwrap();

store.save("props.seg")?;
let loaded = PropStore::open("props.seg")?;
let rec = loaded.get(p1).unwrap().unwrap(); // PropRecord { key, value }

Design notes

• 16 bytes per record: 1 M properties ≈ 16 MB.
• Each record holds a 4-byte key (property name / edge predicate) plus a 10-byte value payload; inline strings up to 10 UTF-8 bytes (INLINE_STR_MAX = 10).
• The graph traversal linked list lives in NodeRecord.first_out; there is no next field in the property record itself.

---

Index (CSR adjacency, implemented)

Neither store records which node owns a given edge/property: a PropStore record spends its payload on the key and value, and the Small Profile keeps no per-record next pointer. The owner → records mapping therefore lives in a separate index, built as a compressed-sparse-row (CSR) structure.

CSR is two parallel arrays:

• offsets — node_count + 1 u32 entries. Node n's records are neighbors[offsets[n] .. offsets[n + 1]]. The trailing entry equals the total record count, so the last node needs no special-casing.
• neighbors — every owned PropId, grouped by owner, in insertion order.

A node's neighbours are thus a contiguous slice — cache-friendly and allocation-free to iterate.

The index is a derived view: it can be rebuilt from the stores at any time, held in memory only, or dropped to reclaim space. Because a PropStore record carries no owner, associations are supplied explicitly through IndexBuilder (in practice by the Graph API as it creates edges and properties).

File format (.idx)

[Header   16 B]   magic(4) + version(2) + flags(2) + id_bytes(1) + pad(7)
[offsets  4 B]*   (node_count + 1) u32 entries
[neighbors 4 B]*  edge_count u32 entries (PropIds)
[Footer   24 B]   node_count(8) + edge_count(8) + crc32(4) + magic(4)

On open, the body CRC32 is checked and the offsets are validated as monotonic with a tail equal to edge_count. Magics: MGIS / MGIF.

Rust API

use mgraphdb::index_store::{IndexBuilder, IndexStore};

let mut b = IndexBuilder::new();
b.add(alice, name_prop)     // node `alice` owns property record `name_prop`
 .add(alice, knows_edge)    // ...and an edge
 .add(bob,   age_prop);

let index = b.build(node_store.len())?;

for &pid in index.neighbors(alice) {   // contiguous slice, in insertion order
    let value = prop_store.get(pid)?;
    // ...
}
assert_eq!(index.degree(alice), 2);

index.save("graph.idx")?;
let index = IndexStore::open("graph.idx")?;

Design notes

• Read-optimised. Traversal is a contiguous scan; ideal for whole-graph walks and analytics. Edge insertion/removal needs an array shift or rebuild — acceptable because the index is derived and cheap to regenerate.
• A write-optimised alternative (an in-record next pointer giving O(1) edge insert, in the spirit of Neo4j's index-free adjacency) is a candidate future profile, not part of the Small Profile.

---

Small Profile

The Small Profile optimises for a very small disk and memory footprint; speed-oriented profiles will follow later.

Common to all variants

• Small references. The ID size (e.g. u16) is chosen at creation time, so a small graph can use very little space per reference.
• Fixed-length records. Every element occupies a fixed number of bytes, giving direct access by ID (offset = ID × record size) with no index lookup.
• Three node-storage options:
  • Option 1 — not stored: only the count plus an (in-memory) index.
  • Option 2 — dedicated file: room for status/flags, optionally indexed.
  • Option 3 — inline with data: node and its data live in one file, since many use cases attach data directly to the node.
• Edges and properties share storage. Both live in the property store; an edge records the start node (and the end node in its data), a property records a typed value.

Nodes

In options 2 and 3 the node record can carry more information:

• flags — subtype plus flag bits (tombstone, HAS_IN, HAS_OUT, HAS_PROP).
• type — optional reference to a "class" node.
• out — optional reference to the first edge.
• key — reference to the property / edge ID (for those subtypes).

A representative flags byte:

Bit	Meaning
7	DEAD (tombstone) — high bit makes scans fast
6	HAS_IN
5	HAS_OUT
4	HAS_PROP
0–3	TYPE (0–15)

Edges

Edges and properties are both stored in the property store and share the same record size: a fixed 16 bytes. This size is a deliberate trade-off, driven mainly by the range of property value types (especially strings — see below).

For an edge, the subtype is already known from the node, and the key fields are:

• startID / endID — references to the start and end nodes. Finding edges and properties uses the index.
• option 3 combines the information that options 1/2 keep split.

Properties

A property record is the 16-byte buffer. The 16-byte size comes from a basic statistical look at common word lengths across languages, which lets a single buffer cover a broad range of value types. The type is encoded in the flags (as for nodes).

Value types

The 16-byte buffer is intended to support a range of value types (final scope TBD). XSD names are given only as a familiar reference, not as an RDF commitment.

Type	Notes
STRING	Short UTF-8 inline (up to 10 bytes after the key; longer strings via the String Store) — xsd:string
BOOL	Single boolean, or a packed list of flags — xsd:boolean
INTEGER	up to i128 — xsd:integer
DECIMAL	f64 (8 B) or f128 (16 B) — xsd:decimal / double / float
COMPLEX	two f64 → 16 B
DATE / TIME / DATETIME / DURATION	xsd:date / time / dateTime / dateTimeStamp / duration
UUID	16 bytes — e.g. urn:uuid
HASH	covers MD5-sized hashes
GEO	lat/long, 16 bytes — e.g. geo:wgs84_pos
URL	reference into the String Store (usually too long for 16 B)
TEXT / FILE	reference into a backing store for longer text or files
REF	internal reference (e.g. into the String Store)
VECTOR	reference into an optional vector store (planned)
VERSION / ENUM	TBD — may live at a higher layer

Values too large for the 16-byte buffer (long strings, text, files, URLs) are referenced into the String Store.

See the Requirements page (REQ-30…REQ-46) for the numbered, traceable form of this design.