geohashim

atlas-graph-db

A graph database written from scratch in TypeScript: an embedded engine with a write-ahead log, crash recovery and atomic transactions, a Cypher-like query language called AQL, a multi-user server and a web explorer.

It was built to learn how a database really works, and that meant making one come back correctly after a crash. Durability came first: the log, then snapshots, then recovery tested by killing the process mid-write. Indexes, traversals, graph algorithms and AQL were built on top of something that already survived that.

View on GitHub Design spec

Plays the six stages below in order, about 55 seconds. Scroll or press Esc to stop.

Language
TypeScript on Node.js 22 or later
Tests
686 passing: 468 Vitest, 218 web app
Engine
From scratch, one runtime dependency (MessagePack)
Server
Fastify, argon2id, a WebSocket change feed
Explorer
Angular 20, a Canvas2D graph
License
MIT
# a script written for this page, calling the public API node scripts/commit.mjs transact -> {"txId":1} 222 wal-000001.log frame @0: length=214 crc32=0x00f7902d

Real output, trimmed where marked. Commit and Recover are scripts written for this page that call the library's public API; they are not in the repo. Query is the repo's own compiled server, driven with curl on localhost.

1Parse the query, then pick where to start

AQL goes through a hand-written lexer and a recursive-descent parser, then a planner. The planner starts each pattern at its cheapest node: an index seek when an equality hits an index, otherwise a scan of the label with the fewest nodes.

  • Reads stop here and run against committed state. A write statement goes on to stage 2 as one transaction, so any error rolls the whole statement back.
  • Errors carry a code, a line, a column and a caret under the problem.
  • Runtime guards raise TIMEOUT or ROW_LIMIT instead of returning a quietly cut result.

The plan changes when an index appears

QueryEXPLAIN MATCH (p:Person {name: 'Ada Lovelace'})-[:KNOWS]->(f:Person) RETURN f.name

  1. Projectf.name
  2. Expandp to f, KNOWS, outgoing, f is a Person
  3. Filterp.name = 'Ada Lovelace'
  4. LabelScanevery Personest. cost 24
  5. IndexSeekPerson.name = 'Ada Lovelace'est. cost 1
Estimated start cost24
executeQuery(db, "CREATE INDEX ON :Person(name)")(0 rows; stats {"rowsExamined":0,"elapsedMs":13})
executeQuery(db, "MATCH (p:Person RETURN p.name")AqlError PARSE_ERROR: expected ")", found "RETURN" at line 1, column 17MATCH (p:Person RETURN p.name ^
Real EXPLAIN output from executeQuery on the repo's bundled science-history dataset (500 nodes, 1,196 edges), run by a script written for this page that calls the public API. The plan is drawn from its JSON; the parse error is verbatim from the same run.

2Stage every change in memory

A transaction is a synchronous callback that stages ops in a list. Nothing touches the graph or the disk while it runs, so throwing the list away is the whole rollback.

  • References are checked against the transaction's own view: an edge to a missing node, or deleting a node that still has edges, fails at once.
  • Unique constraints are checked against the batch's final state, before a byte is written.
  • An async callback is refused. Ops staged after the log write would leave memory and disk disagreeing.
  • Rejected transactions still use up node ids in that process. After a restart, numbering resumes from the highest id in the log.

Five transactions that never reach the log

Log file
268 bytes
Graph
2 nodes, 1 edge

    The good commit got node id 8: ids 3 to 7 went to rejected transactions. After a reopen, the next id was 9.

    Error lines and byte counts are real output of a script written for this page that calls db.transact, with a unique index on Person.name and one committed transaction holding Ada Lovelace, Charles Babbage and a KNOWS edge. Callbacks are shortened to what they did.

    3Write one record, fsync, then say yes

    The staged ops get the next transaction id and become one record: an 8-byte header holding the payload's length and a CRC-32, then the MessagePack payload. There is no begin or commit marker. A transaction is atomic because it is one checked record.

    The caller hears yes only after the record is written and fsynced. If the write or the fsync fails, the commit is rejected, and the log writer refuses everything after it until the database is reopened, so nothing can be acknowledged behind a damaged record.

    A failed fsync is the hard case. The bytes may already be in the file, so a commit rejected at that step can be there after a restart. Its outcome is unknown, not rolled back. The server always runs with an fsync on every commit.

    Three commits, one record each

    1. EncodeMessagePack payload
    2. FrameLength and CRC-32
    3. WriteAppend to the log
    4. fsyncForce it to disk
    5. YesThe txId returns
    6. ApplyStage 4, only now
    Next record-- -- -- ---- -- -- --header: length, then CRC-32, little-endian
    8-byte headerWritten, not yet fsyncedfsyncedRejected
    Log file
    0 bytes
    Graph
    0 nodes

    Header bytes, sizes and log lines are real output of a script written for this page that commits these three transactions through the public API; its log file is byte-identical to the one damaged in stage 6. The failure modes inject a fault by replacing the log file's write or fsync once at runtime; their lines are that script's real output.

    ClearedThe record is in the log and fsynced. Only now does the transaction change the graph that readers and subscribers see.

    4Apply it, then tell subscribers

    Only after the append resolves does the batch touch the in-memory graph, its adjacency lists and its indexes. The batch object that was logged is the one applied, so memory and disk can't drift apart. Then the change feed emits it, and the server forwards it over WebSocket.

    • Short reads take no locks and always see whole committed transactions.
    • Long reads and graph algorithms take a read lease that holds the write queue, so they see one point in time.
    • Commits go through one queue, one at a time, each with its own fsync: 200 commits fired at once still made 200 fsyncs.

    One commit, millisecond by millisecond

      Graph
      0 nodes, 0 edges
      Log file
      0 bytes
      fsyncs
      0
      Real output of a script written for this page; it wraps the log writer at runtime only to print when its append resolves. Times are one run on a laptop; the order and counts were the same in all four runs.

      5Fold the log into a snapshot

      Replaying a long log is slow, so once it passes 64 MiB, or on request, the database writes a snapshot of the whole graph and starts a new log segment.

      • Inside the write queue: close the log, open the next segment, encode the graph to memory. Writes pause for this part.
      • Outside it: write a temporary file, fsync it, rename it, fsync the directory, then delete what the snapshot covers.
      • A crash at any step leaves something recovery can use: a stray temporary file is deleted on open, and a segment the snapshot already covers is ignored, then removed.

      The data directory across one checkpoint

      data/

      • wal-000001.log349 B
      • snapshot-000001.bin390 B
      • wal-000002.log0 B
      openDatabase(dir)reopen: 31.4 ms, stats={"nodeCount":5,"edgeCount":0}, indexes=[{"kind":"property","label":"Person","property":"born"}]lookupRange Person.born 1790..1800 -> Charles Babbage, Michael Faraday
      File names, sizes and the reopen lines are real output of a script written for this page that calls db.checkpoint(). Blocks inside a log file count its records; they are not drawn to scale.

      6Recover whole transactions, nothing else

      On open, the database loads the newest snapshot, then replays newer log records in order. Each record's length and CRC must check out, and transaction ids must follow on without a gap.

      • A short or corrupt record at the end of the last segment is a torn write. The file is cut back to the last whole record, with a warning.
      • A gap in transaction ids, or damage in an earlier segment, is refused outright with WAL_CORRUPT.
      • The repo's crash test kills a writer five times at random moments and checks for whole transactions only, and at least everything that was acknowledged.

      The rule has a cost. A flipped bit in the middle of the last segment looks just like a torn tail, so recovery also drops the intact records after it, with only a warning.

      Five kills, then four damaged logs

      SIGKILL at a random moment, then reopen

        Every run came back as whole transactions, two nodes and one edge each, and every run recovered one more than the writer had reported: a commit already in the log when the kill landed.

        A closed log, damaged by hand, then reopened Illustrative input

        Kill runs are real output of a script written for this page, modelled on the repo's crash test, with default settings. The damaged logs start from the three-record log in stage 3, closed, then cut, extended, flipped or spliced by hand before a real openDatabase. Warning and error lines are verbatim.

        Measured at the capacity point

        The design spec set its targets before any code: 1 million nodes and 5 million edges, recovery under 30 seconds, under 8 GB of heap. These figures were re-run for this page on one laptop (macOS, 12 cores, 18 GB, Node 26) with the repo's own synthetic generator and seed. Each reopen ran in a fresh process.

        Recovery, both ways

        Time to reopen the full graph, against the 30-second budget.

        From a snapshot13.4 s
        Whole log replayed19.0 s

        Two clean runs each, within 0.1 s of each other; one earlier replay, taken while the laptop was swapping, took 47 s. The repo's benchmark times the snapshot path only. Replaying a 425 MB log of 600 transactions also fits, and day to day the 64 MiB checkpoint keeps the log far shorter.

        Memory, after recovery

        Heap after a fresh reopen and a forced GC, against the 8 GB budget.

        After log replay1.9 GB
        After snapshot load2.2 GB

        1,918 MB and 2,214 MB, about a quarter of the budget, held in plain JavaScript maps and sets with edge types interned to small integers.

        One fsync per commit

        200 single-node commits, fired at once through transact:

        200 commits200 fsyncs

        The log writer can share one fsync between appends, but each transaction waits for its own before the next starts. Bulk loads go fast by putting many ops in one transaction instead; the benchmark uses 10,000. On this laptop that meant about 340 to 390 small commits a second.

        686 tests, durability first

        468 Vitest tests across the six packages and 218 Angular tests for the explorer, all passing. The engine's suite does what a crash would: it kills processes, tears records and replays logs.

          Weighted toward what fails silently

          • Crash: a child writer is killed with SIGKILL five times at random moments after its first durable commit; recovery must hold whole transactions only, at least everything acknowledged, and the index. On failure the test keeps the data directory as evidence.
          • Property-based: 25 runs of up to 60 random actions with a snapshot every 2 KiB, then a reopen that must keep every invariant, the same counts and the same index definitions.
          • The log: torn final records, bad CRCs, short writes, and the writer stopping after a failed or partial write so nothing is acknowledged behind it.
          • Transactions: a rollback persists nothing, ids are never reused across a reopen, async callbacks are refused before any write, and a gap in transaction ids refuses to open.
          • Constraints and queries: unique constraints with same-batch index changes, the parser and planner, MERGE, and write statements that roll back whole.
          • Server: auth, the permission matrix, problem-details errors, the audit log and WebSocket subscriptions.

          CI runs the build, type checks, lint, a format check and both suites on Node 22. Five Playwright end-to-end tests in apps/web/e2e run separately with pnpm e2e:web, not in CI.

          Deliberately missing

          Clustering and replication
          One node. The design spec rules out horizontal scaling for v1.
          Graphs bigger than memory
          The graph lives in RAM and durability lives on disk. Tens of millions of elements would need compact typed-array layouts, deferred on purpose.
          Concurrent writers
          One write queue, so there are no write conflicts to resolve and no MVCC.
          Snapshots with no pause
          A checkpoint pauses writes while it encodes the graph. JavaScript has no cheap copy-on-write fork, so that is out of scope.
          A strict open mode
          A damaged tail is cut back with a warning today. An error code is reserved for refusing to open instead.

          Run it

          git clone https://github.com/ahmed-hashim-pro/atlas-graph-db.git
cd atlas-graph-db

# Explorer and API on http://localhost:4848
export ATLAS_SECRET=$(openssl rand -base64 32)
export ATLAS_ADMIN_USER=admin
export ATLAS_ADMIN_PASSWORD=change-me-please
docker compose up --build

# Or build and test it locally
pnpm install
pnpm build && pnpm lint && pnpm test

          One container serves the API and the explorer from the same origin, with the data directory on a mounted volume. The packages are not published to npm; the engine can be used directly from the workspace.