graph-r

An embedded, persistent knowledge graph that acts as the durable backend for link-r: link-r acquires and ranks (crawl, extract, hybrid search over a possibly in-memory index); graph-r remembers and serves (historical graph, adaptive freshness, token-budgeted local lookups). The two share one foreign key — the 64-bit xxh3 of a canonical URL — so a link-r index can be absorbed and then discarded while every lookup keeps resolving.

The point: answer "where is the resource that explains X?" locally, with a URL and a heading anchor, inside a token budget — instead of re-crawling, re-searching, or shipping page bodies to a model on every question.

Install

Division of responsibilities

Quick start (with link-r)

uu-graph-r = "0.6"
uu-link-r = { version = "0.4", features = ["graph"] }   # the crawl → graph bridge

# async fn demo() -> Result<(), Box<dyn std::error::Error>> {
use graph_r::{Config, QueryOpts, Store};

let store = Store::create("kb", Config::default())?;
let mut index = link_r::LinkIndex::in_memory()?;   // link-r stays in memory

// 1. Crawl once, absorb into the durable graph.
let report = index.update("https://docs.example.com/").run().await?;
link_r::bridge::ingest_update(&store, &index, &report)?;

// 2. Look things up locally — URLs + anchors, never bodies.
let snap = store.snapshot();
for hit in snap.query("install on linux", &QueryOpts::default()) {
    println!("{}  {}", hit.url, hit.anchor.map_or("", |a| a.label));
}

// 3. Later: revalidate exactly what the graph says is due (304s are free).
let due = link_r::bridge::due_urls(&store, graph_r::fsio::now_ms(), 64);
if !due.is_empty() {
    let report = index.refresh().urls(due.iter()).ttl(std::time::Duration::ZERO).run().await?;
    link_r::bridge::ingest_refresh(&store, &index, &report)?;
}
# Ok(()) }

Without link-r, graph-r is a standalone embedded graph store: feed it DocRecord/SegmentRecords from any source through Store::writer().

One knowledge base: graph-r + link-r on object storage (link-r feature kb)

use link_r::kb::{KnowledgeBase, LookupOpts, WriterOptions};

let gcs = objstore_r::Gcs::new("my-bucket", objstore_r::token::Adc::discover()?, Default::default())?;

// Writer (one instance, lease-fenced): conditional crawl -> bridge -> publish.
let mut kb = KnowledgeBase::writer(&gcs, "kb/docs", tmpfs_dir, embedder, WriterOptions::new("instance-7")).await?;
kb.sync_crawl(link_r::HttpFetcher::new(link_r::AnonymousAuth)?, "https://docs.example.com/", |c| c.depth(3)).await?;
kb.refresh_due(&fetcher, graph_r::fsio::now_ms(), 256).await?;   // adaptive freshness

// Replicas (any number, no disk): hydrate in place, refresh cheaply, look up locally.
let mut replica = KnowledgeBase::replica(&gcs, "kb/docs", embedder).await?.expect("published");
replica.refresh().await?;
for hit in replica.lookup("install on linux", &LookupOpts::default()).await? {
    println!("{} {:?}", hit.url, hit.anchor);   // URL + heading anchor, never the body
}

Measured on a live bucket: replica hydration ~80 ms, unchanged refresh ~27 ms (two concurrent metadata requests), fused lookup ~0.2 ms. At 1 000 pages in memory: hydration 1 ms, fused lookup 0.6 ms, graph query 0.09 ms.

Durable on object storage (objstore-r feature mirror)

objstore-r's mirror module keeps a store directory in sync with Google Cloud Storage (or a local directory, or memory). graph-r itself is untouched: the mirror moves its files byte for byte, so a stateless instance can keep the store on tmpfs and still lose nothing.

use objstore_r::mirror::Mirror;

let objects = objstore_r::Gcs::new("my-bucket", objstore_r::token::Adc::discover()?, Default::default())?;
let mirror = Mirror::new(&objects, "kb/runbooks")?;

mirror.pull_into(dir).await?;                 // rebuild graph.base + graph.wal (verified)
let store = graph_r::Store::open(dir)?;       // the unchanged API
mirror.acquire_lease("instance-7", 60_000).await?;
// ... writer.commit() as usual ...
mirror.publish(&store).await?;                // ships only the new log records

Remote layout: HEAD (a checksummed manifest, compare-and-swap only), base/{generation}.base, and wal/{generation}/{start}-{end}.seg. A second writer publishing from the same state is fenced; replicas follow with refresh_into (one metadata request when nothing changed). For flat commit latency, Store::set_compact_inline(false) plus Store::compaction_due() move compaction off the commit path.

What's inside

• Storage: two files. graph.base — an immutable, mmapped, checksummed, sectioned snapshot (fixed-width sorted node records, CSR edges, label heap, lexicon + delta-varint postings, ranks) read zero-copy; graph.wal — an append-only log of one checksummed record per transaction. Compaction folds both into a new byte-reproducible base via atomic rename.
• Atomic transactions: a commit or a transact block is one record — one write, one fsync. A crash mid-append leaves a torn record that replay ignores and the next committer cuts off: that transaction is absent whole, every earlier one present. In memory too, a commit, a catch-up and a replay each publish whole records, so no snapshot and no other process ever sees part of a transaction. A record whose checksum holds but whose contents break a rule is Error::Corrupt (with its offset) and is never cut: cutting it would silently drop every later commit.
• Zero-copy log: the log is read once at open and served in place — the bytes a commit wrote, or a catch-up read, are the overlay, never decoded into owned ops; strings come back as &str over validated bytes. A steady-state commit allocates nothing after staging; opening 10k ops allocates about what opening 1k does.
• Concurrency: any number of snapshot readers and any number of writers, in one process or many. Opening takes no lock; each commit takes a cross-process flock only around its append, catches up with other writers' records first, and gives up with Error::Locked past Config::lock_wait (or at once, via Store::try_transact). Store::transact holds the lock from its read view to its single append, so a read-modify-write is serializable across processes. Snapshots are borrow guards over a pinned generation — readers never block on commits or on the lock, and compaction swaps generations under them. No Arc, no async runtime, one unsafe island (mmap).
• Freshness: every document carries an adaptive revalidation interval — grown 1.5× per unchanged check, cut 4× on change, clamped, biased by importance — and due() emits the work list, with stored ETags for conditional revalidation.
• Structure: deterministic PageRank at compaction, fused into lookups.
• Lookups: IDF-weighted tiered lexical scoring (exact/prefix/substring), per-term seed guarantees, hub-refusing bounded BFS, importance fusion, and seeds-first rendering that stops inside a token budget. Results are URLs + segment anchors (byte_range when known) — never content.
• Segments: sub-document anchors (heading path, depth, byte range, importance) keyed stably by heading, so a re-crawl keeps their identity.
• Lineage: containment, value derivation (exact copies flagged) and row conditions as typed edges with reverse adjacency; one allocation-free walk up, down or both ways; large per-node attributes (SQL text, types, provenance), numbered or named.

Format versions and upgrading

A store is refused, never rewritten, by a build that does not read its format: every opener returns Error::Version { found, supported } (Python FormatVersionError with .found and .supported) before anything is written, and the files stay byte-identical.

The base carries the version bump as well as the log (its layout is unchanged): every release reads the base first, so an older writer refuses a 0.6 store there, before it could take an empty log for its own. There is no in-place upgrade, and no mixing 0.5 and 0.6 writers on one store: drain, then rebuild — stop the old writers, read out what you need with the release that wrote the store, and re-ingest with 0.6 (a crawl cache or metadata store simply regenerates). 0.6.0 also supersedes a 0.5.x defect: a commit that failed after its append could reuse sequence numbers, after which the store no longer opened (wal sequence regression).

Features

The link-r ingest path is link-r's graph feature, object-store publishing is objstore-r's mirror feature, and both together are link-r's kb feature: graph-r's core depends on neither, so the four crates form no cycle.

Future document types (pdf, xml, …) arrive as feature-gated link-r extractors and flow through link-r's bridge unchanged — the DocRecord/SegmentRecord seam is the stable extension point. No harness coupling anywhere: this is a plain Rust library, embeddable in any runtime.

Testing

cargo test (unit + hermetic lifecycle), cargo test --test proptest_model (model-based agreement through compaction/reopen, byte-reproducibility, a log cut at any byte holding exactly the first k transactions), cargo test --test multi_writer (writers as real processes: no snapshot holds part of another process's transaction, a crash mid-append loses that transaction whole), cargo test --test alloc_count (counted allocations: open, fold, commit), cargo test --test concurrency (8 readers under a compacting writer), cargo bench (criterion, including read-latency-under-write and log replay), cargo +nightly fuzz run <target> (every decoder: arbitrary bytes must produce a typed error, never a panic or an over-allocation; plus crash cuts and two writers), and scripts/xver (a released 0.5.1 must refuse a 0.6 store and leave it untouched).

Python

The same loop, one class, from PyPI (pip install uu-graph-r, then import graph_r; Python >= 3.12, one abi3 wheel per platform):

import graph_r

store = graph_r.Store.open_or_create("kb")
store.sync("https://docs.example.com/", depth=2)   # crawl -> absorb -> compact
for hit in store.query("install on linux"):
    print(hit.url, hit.anchor.label if hit.anchor else "")

sync seeds a fresh in-memory link-r index from the graph's stored validators, so a re-sync of an unchanged site transfers zero bodies — from a cold start included. The index is discarded when the call returns; bodies and vectors never outlive it. Safe from any thread (asyncio.to_thread works); blocking calls detach from the interpreter. See bindings/python/graph_r.pyi for the full surface (add/touch for non-crawl producers, due, related, pin, remove, compact).

License

Dual-licensed:

• AGPL-3.0-or-later for open-source use. See LICENSE.
• Commercial, for use in proprietary or closed-source software without the AGPL's copyleft requirements. Contact spicyzhug@gmail.com.

Copyright (c) 2024-2026 Lituus-io. All rights reserved.