CryptoPatrick / code

Code · Databases

graph_mvcc

Multiversion concurrency control for a graph: transactions with snapshot isolation over nodes and edges.

Rust ~930 lines · 14 tests Prototype (v0.2)

What it is

Databases let many transactions run at once without reading each other’s half-finished changes. Multiversion concurrency control (MVCC) does this by keeping several versions of each record: every transaction sees a consistent snapshot from the moment it started, and writes become visible only on commit.

graph_mvcc applies that idea to a graph. Nodes and edges are created inside transactions, edges carry a type, and a transaction either commits all its changes or rolls them all back. I wrote about the design in MVCC 101.

Using it

use graph_mvcc::Graph;

fn main() {
    let mut graph = Graph::new();
    let mut tx = graph.start_transaction();

    let a = graph.add_node(&mut tx);
    let b = graph.add_node(&mut tx);
    graph.add_edge(&mut tx, &a, &b, "CONNECTS".to_string()).unwrap();

    graph.commit_transaction(&tx).unwrap();   // or rollback_transaction
}

Ideas for using it

  • Learn isolation by experiment. Start two transactions, change the same edge in both, and see which commit wins and why.
  • Undoable graph edits. An editor for diagrams or knowledge graphs where a whole multi-step change can be rolled back.
  • A base for a toy graph database. Add persistence and a query language on top.

Status

Prototype: single-threaded and deterministic, which makes behaviour easy to reason about but means it is not a concurrent database yet. Not for production use.