Crate graph_r 

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); 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.

Design tenets

• Zero-copy reads. The base snapshot is an mmapped, checksummed, sectioned file; lookups binary-search fixed-width records in place.
• Readers never block. Snapshots pin a generation lock-free; writers (any number, across processes) take turns appending to a WAL under a commit-scoped lock and publish into an append-only overlay; compaction swaps generations under readers without pausing them.
• Lifetimes over Arc. Snapshot, NodeRef, hits, and iterators are borrow guards tied to the Store; nothing is reference-counted.
• Determinism. Compaction is byte-reproducible; ranking, communities, and query output are fully ordered with explicit tie-breaks.
• References, never bodies. Nodes hold compact lookup metadata (title, snippet, anchors, freshness); document bodies and dense vectors stay in link-r or at the source URL. Lookups answer with URLs + anchors, which is what keeps repeat token spend near zero.

Quick start

The link-r ingest path is link-r’s graph feature (link_r::bridge), and object-store mirroring is objstore-r’s mirror feature; both build on this crate’s core, so none of them is a dependency here:

uu-graph-r = "0.5"
uu-link-r = { version = "0.4", features = ["graph"] }

Re-exports

pub use error::Error;

pub use error::Result;

pub use key::EdgeType;

pub use key::NodeId;

pub use key::SegKey;

pub use key::UrlKey;

pub use query::Anchor;

pub use query::Hit;

pub use query::QueryOpts;

pub use query::TokenBudget;

pub use snapshot::DueItem;

pub use snapshot::NodeRef;

pub use snapshot::SegRef;

pub use snapshot::Snapshot;

pub use store::CommitLock;

pub use store::Config;

pub use store::Durability;

pub use store::Store;

pub use traverse::Direction;

pub use traverse::EdgeRef;

pub use traverse::Hop;

pub use traverse::LendingIterator;

pub use traverse::Neighbors;

pub use traverse::Walk;

pub use ttl::Outcome;

pub use ttl::TtlConfig;

pub use writer::DocRecord;

pub use writer::SegmentRecord;

pub use writer::Touch;

pub use writer::Txn;

pub use writer::Writer;

Modules

bytesio

Little-endian byte codec shared by the base and WAL formats. All readers return Error::Format rather than panicking on truncated or hostile input, and every length-driven preallocation is capped by Reader::remaining — the two rules the fuzz targets enforce.

container

A checksummed, sectioned, 64-aligned file container: the one on-disk framing behind graph-r’s base snapshot and every dependant’s images.

error

Error taxonomy. Decoders return Error::Format (or Error::Version for a well-formed file of another format version) rather than panicking on any malformed input — the property the fuzz targets enforce — and every concurrency- or lock-related refusal has its own variant so callers can distinguish “retry later” from “corrupt file”.

format

On-disk formats. Two files, one discipline:

fsio

File primitives shared by the store, the mirror and dependants: atomic replacement, the cross-process writer lock, and the millisecond clock. Safe std only — the lock is File::try_lock (flock on unix, LockFileEx on Windows), which every platform releases when the process dies.

hash

The crate’s single hash family (xxh3), exposed so dependants key and fingerprint with exactly the function behind crate::UrlKey, section checksums and file trailers — one family across graph-r, link-r and their users, no second hashing crate. Thin wrappers: the underlying crate is an implementation detail and never appears in this API.

key

Identity types. The durable foreign key everywhere is UrlKey — the 64-bit xxh3 of a canonical URL, byte-compatible with link-r’s key of the same name — because link-r’s internal document ids are unstable across removals. NodeIds here are dense per-snapshot indices assigned at compaction; they are stable within one base generation and never persisted across it, exactly link-r’s DocId philosophy.

mmap

Zero-copy read-only images (feature mmap). Read-only images for zero-copy readers: a memory-mapped file, or bytes already in memory (an object fetched from storage) served in place. The crate’s single unsafe island (#![deny(unsafe_code)] at the root; this module opts out locally).

prelude

Convenient single-line import of the working set.

query

Local lookups that answer with references — URL + anchor + snippet — inside a token budget, never with document bodies. The recipe:

rank

Importance, computed at compaction and persisted in the Ranks section: PageRank over crawl Link edges (damping 0.85, fixed 20 iterations, f64 accumulation in ascending node order — bit-stable on a platform), reported as a percentile in permille. Degree < 2 nodes are floored to 0 so leaf noise never tops a ranking.

snapshot

Read views. A Snapshot pins one base generation plus the overlay ops committed before it was taken; everything it returns — node refs, edge refs, hits, due items — borrows either the mmap or the overlay arena, so reads are zero-copy and never invalidated by concurrent commits.

store

The store: a directory holding graph.base (immutable snapshot), graph.wal (append-only op log) and graph.lock (commit exclusion).

text

The text rules every index shares: tokenization, case folding, char n-grams, stopwords and the token estimate behind budgets. One implementation for graph-r’s lexicon, link-r’s BM25 and embedder, and their users — a query term and an indexed term always agree. Allocation-free apart from the case-folding of non-lowercase tokens.

traverse

Zero-alloc traversal. LendingIterator is the crate’s GAT seam: each step lends a view tied to the iterator’s borrow, so implementations are free to reuse internal state per step without allocating — and future sources that materialize per-step stay possible behind the same trait.

ttl

Adaptive freshness. Every document node carries a revalidation interval that grows geometrically while the source is observed unchanged and is cut sharply when it changes — integer math with explicit clamps, so replay and tests are bit-deterministic. Important nodes (percentile PageRank) are checked more often via a permille bias on the effective interval.

writer

Writers and transactions. Mutations are staged as WAL ops, made durable on Writer::commit (commit lock → catch up → encode → append → fsync per policy → unlock), then published into the current generation’s overlay where new snapshots see them immediately. Freshness math runs here, at touch time, and the computed state travels inside the op — replay never re-derives policy. Txn is the serializable form: the lock is held from its read view to its append.