Managing State (MVCC & Memory)

In a high-performance database, “State” is the enemy of speed. Managing it requires locks, and locks kill concurrency.

If User A is reading a graph to compute a shortest path between two cities, and User B updates a road in the middle of that calculation, what should happen?

1. Locking: User B waits until User A finishes. Safe but slow.
2. Dirty Read: User A sees the half-updated state and crashes. Fast but broken.
3. MVCC: User A sees the old version of the road, while User B writes the new version. Both proceed in parallel.

Samyama implements Multi-Version Concurrency Control (MVCC) with cache-friendly, arena-style storage for nodes and copy-on-write semantics for edges, giving lock-free reads under concurrent writes.

The data model

GraphStore (in src/graph/store.rs) is the single authority for graph state. Two design choices shape everything else:

• The ID is the index. A NodeId is a direct u64 index into the node arena — not a hash key, not a UUID. NodeId(5) means “slot 5”. This is O(1) without hashing and keeps adjacency walks contiguous in memory.
• Topology is separated from properties. The arena holds the structural skeleton (id, label, version chain); property values live in column-oriented storage (ColumnStore) keyed by id. Traversals can scan adjacency lists for millions of edges without ever touching property bytes.

graph TD
    subgraph "GraphStore"
        Nodes["nodes: NodeArena<br/>(versioned slots)"]
        EdgeStore["edge store<br/>(COW, EdgeView)"]
        Outgoing["outgoing: Vec&lt;Vec&lt;EdgeId&gt;&gt;"]
        Incoming["incoming: Vec&lt;Vec&lt;EdgeId&gt;&gt;"]
        NodeCols["node_columns: ColumnStore"]
        EdgeCols["edge_columns: ColumnStore"]
    end

    subgraph "Node version chain"
        V1["v1 (old)"] --> V2["v2"]
        V2 --> V3["v3 (latest)"]
    end

    Nodes -.-> V1

Snapshot Isolation for reads

Each node slot keeps a short version chain. When a query begins, it captures the current MVCC version Vq. To read a node, the engine walks the chain backward until it finds the newest version ≤ Vq. No locks. No coordination with writers. Reads at any concurrency level cost a vector indirection plus a tiny linear scan over recent versions.

Edges follow a complementary pattern: the engine no longer keeps a per-edge in-memory arena. Edges are addressed through EdgeView — a lightweight handle that resolves endpoints and properties on demand from columnar storage and the node-side adjacency lists. Edge updates use copy-on-write: an in-flight update produces a new view; readers continue to see the old one until they advance to a fresh snapshot.

The combination — versioned node arena plus COW edges — keeps steady-state memory close to the data’s information-theoretic minimum and makes reads cache-friendly even under sustained write load.

Isolation levels and write-write conflicts

BEGIN ... COMMIT transactions support two isolation levels:

• Read Committed — each statement sees the latest committed state at statement start. Cheap and the right default for write-heavy workloads.
• Snapshot Isolation — the entire transaction sees the snapshot taken at BEGIN. Concurrent writers to the same node or edge are detected at commit time; the later committer aborts with a write-write conflict and can retry.

Long-running readers don’t block writers and writers don’t block readers; the only synchronization is the conflict check at commit, which touches just the keys that the transaction wrote.

Version GC

Old versions don’t accumulate forever. A background reclaimer drops node versions older than the oldest live snapshot, and the WAL itself is versioned so log replay can reconstruct the right state on restart. The result is bounded memory regardless of write rate.

Columnar properties

graph LR
    subgraph "ColumnStore (per label)"
        Age["age: Vec<i64>"]
        Name["name: Vec<String>"]
        Salary["salary: Vec<f64>"]
    end

    Query[Query Engine] -- "SIMD aggregation" --> Age
    Query -- "Late materialization" --> Name

Property columns are stored once per label, indexed by node id. The query engine reads them only when the user explicitly references them in WHERE or RETURN. The same column layout supports SIMD-friendly aggregation paths (SUM, AVG, COUNT(*) WHERE ...) without per-row dispatch.

Statistics for the optimizer

GraphStore maintains label counts, edge-type counts, and per-property statistics (null fraction, distinct count, selectivity). The cost-based planner consults these to choose join orders, pick between adjacency walks and edge scans, and decide whether to use an index. See Query Optimization for how the planner uses them.

ACID guarantees

CAP trade-off

Samyama’s Raft-based clustering chooses CP — consistency and partition tolerance:

• During a network partition, the minority partition refuses writes.
• Reads from the majority partition remain consistent.
• Availability is sacrificed during partitions in favor of correctness.