Architecture Overview¶

Crystal is a property graph database built as a single Go binary with an embedded-first design. It can run as a standalone server with a REST API or be imported directly as a Go library.

Design Goals¶

• Zero external dependencies for the core engine
• Embedded-first (like SQLite for graphs)
• Suitable for investigation mapping and narrative design workflows
• Simple persistence with crash-safe writes

Storage Model and Capacity¶

Crystal is RAM-resident. The entire graph must fit in memory.

Despite the name, the disk backend is not disk-resident: every vertex, every edge and both adjacency indexes live in Go maps in process memory. Disk is used purely for durability — a write-ahead log and periodic full-graph snapshots. There is no buffer pool, no paging, and no cold tier.

Two consequences follow directly:

• Maximum dataset size is bounded by RAM, not by disk.
• Startup is O(graph) — every start reads the snapshot, replays the WAL and rebuilds the adjacency index in full.

Measured cost at the benchmark's property density (4 properties per vertex, 2 per edge — see test/benchmark/million_edges_test.go):

live heap ≈ 745 B × |V| + 626 B × |E|

Go's garbage collector needs roughly twice the live heap to run comfortably (the 100k-vertex / 1M-edge fixture holds 668 MB live and shows 1.5 GB RSS), so budget RAM at 2× the figure above:

| RAM available to Crystal | Graph at benchmark density (|E| ≈ 10·|V|) | |---|---| | 1 GB | ~76k vertices / ~760k edges | | 4 GB | ~300k vertices / ~3M edges | | 16 GB | ~1.2M vertices / ~12M edges | | 64 GB | ~4.9M vertices / ~49M edges |

Property payload dominates these numbers, not graph structure — measure against your own data rather than assuming this ratio.

Supported envelope for v1: ~1M vertices / ~10M edges on a 16 GB host, scaling linearly with RAM. This is a deliberate decision, not an oversight: see ADR 0001 — Storage model for the rationale, what it rules out, and the conditions under which it should be revisited.

Layer Diagram¶

+---------------------------+
|     Public API (pkg/)     |   Go library interface
+---------------------------+
|     REST API (api/http)   |   HTTP server, handlers, middleware
+---------------------------+
|   Embedded Client (api/)  |   Programmatic access layer
+---------------------------+
|    Query Engine (query/)  |   Fluent query builder, executor
+---------------------------+
|  Traversal (traversal/)   |   BFS, DFS, shortest path, all paths
+---------------------------+
|   Storage Interface (core)|   Storage trait in core/types.go
+-------+----------+--------+
| Memory |   Disk   |  both RAM-resident; disk adds durability
+--------+----------+

Package Structure¶

internal/core/¶

Defines the fundamental types: Vertex, Edge, Properties, Storage interface, and StorageStats. All other packages depend on core; core depends on nothing.

internal/storage/memory/¶

In-memory storage backend using Go maps with sync.RWMutex for concurrent access. Data lives only in process memory. Useful for testing, short-lived sessions, or when persistence is not needed.

internal/storage/disk/¶

File-based persistent storage with Write-Ahead Logging (WAL) for crash safety. The graph itself is held in memory exactly as in the memory backend — this layer adds durability, not capacity (see Storage Model and Capacity).

On-disk layout in the data directory:

• graph.json -- full snapshot of all vertices and edges
• wal.bin -- binary WAL file with framed mutation records

The adjacency index (outEdges / inEdges maps) is rebuilt from the edge list on load, so the on-disk format only stores vertices and edges.

internal/query/¶

Fluent query builder with filtering, pagination, and sorting. The executor resolves queries against the storage backend. Supports three query types:

• Vertex queries: filter by type, labels, properties
• Edge queries: filter by type, properties
• Neighbor queries: multi-hop traversal from a starting vertex

internal/traversal/¶

Graph traversal algorithms:

• BFS: breadth-first search with configurable max depth, direction, and edge type filtering. Also provides shortest path computation.
• DFS: depth-first search with the same configuration. Also provides all-paths enumeration between two vertices.

internal/api/http/¶

HTTP server using only the Go standard library (net/http). Includes:

• A custom pattern-matching router (api/router/)
• Middleware for logging, CORS, and panic recovery
• RESTful handlers for vertices, edges, graph operations, queries, and traversals

internal/api/embedded/¶

Direct programmatic access to all graph operations without going through HTTP. Used by the public pkg/crystal library.

internal/config/¶

JSON-based configuration with environment variable overrides and CLI flag support.

pkg/crystal/¶

The public API surface. External Go projects import this package to use Crystal as an embedded database.

Data Model¶

Crystal uses a property graph model:

• Vertices have an ID, a type string, a set of labels, and a property map.
• Edges have an ID, source/target vertex IDs, a type string, a property map, a directed flag, and an optional weight.
• Properties are map[string]any allowing flexible schema.

Concurrency Model¶

Both storage backends use sync.RWMutex:

• Multiple concurrent reads are allowed
• Writes acquire an exclusive lock
• The HTTP server handles requests concurrently via goroutines

Cancellation¶

Every Storage method that can do unbounded work takes a context.Context, and the query executor and traversal strategies thread the request context all the way down. HTTP handlers pass r.Context(), so a client disconnect stops the work it started.

The context is checked before the lock is taken, so a caller that has already gone away does not first queue behind other work. Traversals check once per dequeued vertex; path enumeration samples every 1024 expansions, sharing the interval with its deadline check.

Close and Stats are the exceptions. Close is cleanup and must be allowed to finish — cancelling it would abandon the final snapshot, which is the opposite of what closing is for. Stats reads a few counters and cannot block.

Scaling Out¶

Operational guidance lives in the Cluster Mode guide; this section covers how it works internally.

Two mechanisms, solving different problems. Neither distributes a single graph across machines — see ADR 0001 for why that is rejected.

Named graphs¶

internal/storage.Manager holds the graphs one process serves. The default graph lives at the data-dir root and named graphs under graphs/<name>/, so an existing single-graph data directory keeps working with no migration.

Every graph-scoped route is registered twice, under /api/v1 and under /api/v1/graphs/:graph. Handlers resolve their store per request from the :graph parameter, which is empty on the unnamespaced form and resolves to the default. That is the whole compatibility story.

Graphs are opened eagerly at startup rather than on first use, because opening is where recovery happens: a graph with a corrupt WAL should fail while an operator is watching, not on the first request that happens to touch it.

Readiness covers every graph. One failing graph takes the instance out of the pool, because it cannot serve the routes addressing that graph and there is no way to depool a subset of an instance's routes.

Replication¶

The WAL is the replication stream. txnCounter doubles as the log sequence number and is durable across restarts — the snapshot records the LSN it covers and replay carries it forward — so a follower's stream position survives a restart on both sides.

A primary exposes three endpoints: status, snapshot (a consistent full copy plus its LSN) and stream (newline-delimited committed transactions after a given LSN, held open and fed by a commit notification rather than polling).

Transactions cross the wire in entity terms, not as raw WAL records. The framing is an internal format that has already changed once, and a stream that leaked it would couple every follower to the primary's on-disk layout.

ApplyReplicated commits under the primary's LSN and skips validation. Both are deliberate: a follower's log has to line up with the primary's, and re-validating would let a follower reject data the primary holds — which is exactly the divergence replication exists to prevent.

Replication is asynchronous, with no consensus and no automatic failover.

Persistence Strategy¶

The disk backend combines Write-Ahead Logging with periodic snapshots for crash-safe persistence.

Write Path¶

Every mutation (PutVertex, DeleteVertex, PutEdge, DeleteEdge) follows this sequence:

1. Acquire write lock
2. Append a binary WAL record to wal.bin and fsync
3. If the WAL append fails, return error without modifying in-memory state
4. Apply the change to in-memory maps
5. Release lock

This guarantees that any acknowledged write is durable on disk before the caller sees success.

On-disk Format Versioning¶

Both files carry a format marker, so a build that cannot read them says so instead of guessing.

wal.bin opens with an 8-byte file header:

[Magic 4B: CF A1 'W' 'L'] [Version 2B] [Reserved 2B]

graph.json carries the equivalent as two top-level fields:

{ "magic": "crystal-snapshot", "format_version": 1, "vertices": [...], "edges": [...] }

An unknown version or foreign magic fails the load with ErrUnsupportedFormat rather than degrading. That is deliberate: a misread snapshot yields an empty or partial graph, and the next checkpoint writes it back over the real data — so an unreadable file must stop startup, not survive it. A JSON snapshot with no magic is accepted as pre-versioning format 0 and rewritten on the next checkpoint; one with neither magic nor a vertices key is rejected, which is what stops an unrelated or truncated file from being read as an empty graph.

The WAL file magic shares its first two bytes with the per-record magic and differs at the third ('W' versus an opcode of 0x01/0x02), which is how a pre-versioning WAL is recognised and replayed rather than rejected. It picks up a header at the next truncation.

WAL Record Format¶

Each WAL record uses a binary frame with integrity checking:

[Magic 2B] [OpType 1B] [EntType 1B] [Flags 1B] [TxnID 8B] [DataLen 4B] [Data NB] [CRC32 4B]

• Magic: 0xCF 0xA1 (corruption sentinel)
• OpType: Put (0x01) or Delete (0x02)
• EntType: Vertex (0x01) or Edge (0x02)
• Data: JSON-encoded entity for Put, raw ID bytes for Delete
• Flags: bit 0 (FlagCommit) marks the final record of a transaction
• TxnID: the transaction the record belongs to
• CRC32: IEEE checksum over all preceding bytes in the record

Point-in-time Reads¶

Storage.View(ctx, fn) runs a callback against a stable view of the graph.

Individual reads take and release the lock per call, so an operation assembled from several of them — any traversal, any query, "edges then their endpoints" — could observe a graph that never existed at any instant: an edge read before a delete, and its endpoint read after. Inside View the read lock is held for the whole callback, so every read sees the same state.

Traversals, queries and neighbour lookups all run inside a view. The traversal strategies and the query executor take a core.Reader rather than a Storage, so the same code runs against either.

Why a callback rather than a view handle. A handle can be forgotten, and a leaked read lock stalls every writer indefinitely. The callback makes the scope impossible to get wrong. The cost is that a long read blocks writers for its duration — bounded, because traversals are capped and cancellable, but real. Do not write from inside a view, and do not nest views.

This is snapshot isolation by exclusion rather than by versioning, which ADR 0001 re-scoped this to: with the whole graph in RAM behind one lock, holding the read lock is what a consistent view means. Versioned reads that let writers proceed during a long traversal would need MVCC, which is a larger change than the problem currently justifies.

Schema Validation¶

Property constraints are optional and per type. A type with no registered schema is unconstrained — the property graph model is schema-optional by design, and requiring a schema for every type would undermine that. Declaring one turns violations into rejected writes.

Schemas are declared in config (schema.vertices, schema.edges) and readable at GET /api/v1/schema.

Validation happens inside core.CheckBatch, alongside the referential checks and before anything is applied. Putting it there rather than at the API edge means every write path is covered by construction — REST, library and batch — and a violation rejects the whole batch instead of half-applying it.

Recovery deliberately does not re-validate. Replay reproduces writes that were already accepted; applying a schema tightened after the fact would silently drop committed data at startup, which is worse than holding entities that no longer satisfy a new constraint.

Referential Integrity¶

Edge writes validate that both endpoints exist, and deleting a vertex cascades to its edges in both directions — inside the same transaction, so a failure later in the batch rolls the cascade back with everything else.

Enforcement on the write path is not sufficient on its own, because recovery does not re-validate: a snapshot or WAL written by an older build is replayed as-is. So the store runs a consistency check after loading and reports what it finds (Store.Recovery().Consistency, and GET /api/v1/graph/consistency).

It reports rather than refuses to start. A dangling edge degrades a traversal rather than destroying anything, and refusing to start would strand data that is already on disk. Repair is explicit: --repair at startup, or POST /api/v1/graph/repair.

Repair rebuilds the adjacency index from the edge list rather than patching it. The index is derived data and the edge list is authoritative, so recomputing fixes orphaned and missing entries in one pass and cannot leave a third inconsistency behind.

Transactions¶

Every write is a transaction. A single Put or Delete is a one-record transaction; Apply(batch) is an n-record one. All of a transaction's records are written with one write and one fsync, and only the last carries FlagCommit.

Recovery buffers records until it sees a commit marker and applies them together. A transaction whose records are present but whose marker is not was interrupted mid-write, and is discarded — applying part of it is exactly the half-applied state batches exist to prevent. Store.Recovery() reports how many records were dropped that way.

A commit flag on the last record rather than a separate commit record keeps the common case (a single write) at exactly one record, and makes "committed" a property of bytes that are already being fsynced rather than of a second write that could itself be torn.

The single-operation storage methods are implemented as one-operation batches, so there is one write path rather than two that can drift apart.

Checkpoint Triggers and WAL Bounds¶

The WAL is only ever shortened by a checkpoint, so the checkpoint triggers are the bound on WAL size — and because the log is replayed record by record at startup, they are also the bound on recovery time.

Either of the first two alone is sufficient. Setting both to zero disables all bounding and the log grows until the disk fills — which was the previous behaviour when checkpointing was off or slow.

The size trigger fires inline, on the write that crosses the threshold, rather than signalling the background checkpointer. That makes the bound hard: a writer faster than the checkpointer would otherwise run past the limit while the checkpoint was still being scheduled. The cost is that one write in every max_wal_bytes pays for a full snapshot, and since checkpointing currently holds the write lock, that write stalls concurrent readers too.

sync_on_write snapshots on every mutation, which makes the log redundant, so it truncates too. It is legacy: the WAL already makes every acknowledged write durable at a fraction of the cost.

Sizing guidance: max_wal_bytes trades disk and startup time against checkpoint frequency. A 64 MiB log replays in well under a second; raising it to gigabytes makes checkpoints rarer but pushes recovery into the tens of seconds.

Checkpointing¶

A background goroutine runs on a configurable interval (flush_interval, default 30s). The store lock is taken twice, briefly, and not held across the serialisation or the IO:

1. Acquire write lock; copy the entity pointers and note where the WAL has reached; release the lock
2. Serialize the graph to JSON — unlocked
3. Write graph.json.tmp, fsync it, atomically rename to graph.json, then fsync the data directory — unlocked
4. Acquire write lock; drop the WAL prefix the snapshot now supersedes, keeping whatever was appended during steps 2–3; release the lock

Step 1 is cheap because stored entities are never mutated in place: every write replaces the map entry with a fresh clone, so a captured pointer keeps describing the state it was captured in. Copying ~1M pointers is a few milliseconds of memcpy against seconds of serialisation.

Step 4 discards a prefix rather than truncating the file, because writes that landed during steps 2–3 are not in the snapshot and must be replayed on top of it. The snapshot describes the graph exactly as of the recorded WAL offset.

Measured on a 40k-vertex graph with a reader running throughout:

A checkpoint is one event among tens of thousands of reads, so p99 is blind to it — the stall lives in the extreme tail, which is exactly where a client notices it.

The size trigger asks the background checkpointer to run rather than checkpointing inline, so an ordinary write no longer pays for a full-graph serialisation. If the writer outpaces the checkpointer and the log reaches twice max_wal_bytes, the write checkpoints inline anyway — the bound stays hard.

Both fsyncs in step 3 are load-bearing. Without the file fsync, a crash after the rename can leave a directory entry pointing at contents that never reached the disk; without the directory fsync, the rename itself may not survive. Either one matters because step 4 discards the WAL immediately afterwards — a snapshot that silently did not land would take the only other copy of the data with it.

Explicit Flush() calls (via API or shutdown) perform the same operation.

Recovery¶

On startup, the disk backend:

1. Loads the last graph.json snapshot (if it exists)
2. Opens the WAL file
3. Replays all valid WAL records on top of the snapshot state
4. Discards a torn trailing record (partial write from a crash), and logs how many records were replayed and how many bytes were dropped
5. Writes a fresh snapshot and truncates the WAL (so recovery cost is paid once)
6. Starts the checkpoint goroutine

Torn Tail vs Corruption¶

These are different events and are handled differently.

A torn tail is a partial record at the very end, the expected result of a crash between the write and its fsync. Nothing acknowledged is lost by dropping it, so recovery continues. The reasons that qualify:

• a short read — the file ran out mid-record, which can only happen at the end
• a checksum failure on a record whose frame ends exactly at EOF
• a zero-filled region running to EOF, which is a torn write that extended the file without flushing its contents

Corruption is a record that fails to parse with readable data behind it. That is never expected, and skipping it is not safe: the records after the damage are real mutations, so replaying only the prefix silently rolls the graph back, and the next checkpoint makes the rollback permanent. Recovery fails with ErrCorruptWAL and the process does not start.

The count of replayed records and discarded bytes is available from Store.Recovery() as well as the log, so a clean restart can be told apart from one that dropped a torn tail.

Durability Guarantees¶

| WAL fills to max_wal_bytes | Write that crosses the line checkpoints inline before returning | | Both triggers disabled | WAL grows unbounded — not a supported configuration |

The sync_on_write option still exists for backward compatibility and triggers a full snapshot on every mutation in addition to the WAL append. It now truncates the WAL afterwards, since the snapshot it just wrote supersedes it.

Future Work¶

The architecture is designed to support:

• In-memory indexing on type, label and property, rebuilt at load (index/)
• MVCC transactions (transaction/)
• A declarative query language with parser and optimizer (query/parser/, query/planner/)
• Graph algorithms (PageRank, community detection, etc.) (algorithm/)
• Transform/enrichment pipelines (transform/)
• Git-like graph versioning with branching and merging (versioning/)
• WebSocket subscriptions for real-time updates
• gRPC and GraphQL API layers