05_out_of_core

Example 05 — Out-of-core PageRank (Tier 2)

What it demonstrates

GoGraph's Tier 2 external-memory storage: build a directed graph, persist its CSR adjacency to disk in the csrfile binary format, re-open it by mmap'ing the file and reinterpreting its aligned sections as typed slices in place (no parse, no heap copy), apply a SEQUENTIAL access hint, and run semi-external PageRank that keeps only the rank vector in RAM while streaming the adjacency from the mapped file each iteration. The headline evidence is the out-of-core footprint advantage: the on-disk adjacency dwarfs the resident heap.

Domain / scenario

A directed, scale-free hyperlink graph — the canonical PageRank domain — generated by Price's model (directed preferential attachment, de Solla Price, 1965/1976). Nodes arrive in id order; each new node emits -out-degree out-links, choosing each target with probability proportional to the target's current in-degree plus a small attractiveness constant (the in-degree exponent is gamma_in = 2 + attractiveness/out-degree). This produces a heavy-tailed in-degree distribution: a few early-arriving nodes accrue most of the incoming links and become high-PageRank authorities, while the bulk hold near-uniform low rank.

That separation is what makes the result meaningful: the top-k highest-PageRank node ids are a stable, reportable fact — unlike a uniform ring, whose PageRank is flat and has no ranking to report. Fixing -seed fixes the data shape, and therefore the top-k, exactly.

How to run

go run ./examples/05_out_of_core                       # small deterministic default
go run ./examples/05_out_of_core -nodes 1000000 -out-degree 8  # observable-scale run

Scale and flags

The default builds and ranks in milliseconds (well under the 60 s short-test budget). At one million nodes with eight out-links each, the on-disk csrfile is on the order of ~69 MiB while the resident rank vector is only ~8 MiB — roughly a 9× footprint advantage, and it widens with scale.

Expected output

The csrfile is written under an os.MkdirTemp directory whose absolute path varies per run; that path is intentionally kept out of stdout, so the fact lines below are byte-stable for the default -seed.

config.nodes=5000
config.out_degree=4
config.attractiveness=1
config.top_k=10
config.seed=7
csr.order=5000
csr.size=19990
pagerank.top0=197
pagerank.top1=164
pagerank.top2=7
pagerank.top3=230
pagerank.top4=131
pagerank.top5=32
pagerank.top6=98
pagerank.top7=65
pagerank.top8=172
pagerank.top9=56

The # -prefixed telemetry lines vary per run and per machine and are never pinned by the test. A representative sample (default scale):

# disk.csrfile=196.32 KiB
# mem.rank_vector=40.00 KiB
# ooc.disk_over_rank_vector=4.9x
# mmap.elapsed=137µs
# pagerank.iterations=26
# pagerank.elapsed=1.53ms

Evidence it collects

This is an out-of-core example, so it reports (from the evidence taxonomy in docs/examples-standard.md):

• On-disk size vs live heap — # disk.csrfile, # mem.rank_vector, # mem.heap_alloc, and the derived # ooc.disk_over_rank_vector ratio. This is the headline figure: scale -nodes up and watch the on-disk adjacency outgrow the resident rank vector, since the working set is bounded by the vertex count, not the edge count.
• mmap wall-clock — # mmap.elapsed: re-attaching the on-disk graph is near-instant because the file is mapped, not read into the heap.
• PageRank query wall-clock — # pagerank.elapsed and # pagerank.iterations: the cost of streaming the mapped adjacency to convergence.

The deterministic facts (csr.order, csr.size, and the pagerank.topN authority ids) prove the computation actually ran over the mapped region and stay stable for a fixed seed.

Key APIs

• graph/adjlist.New / AdjList.AddEdge — build the mutable directed graph.
• graph/csr.BuildFromAdjList — freeze the builder into an immutable Tier 1 in-memory CSR snapshot.
• store/csrfile.WriteToFile — persist the CSR atomically as a Tier 2 on-disk file.
• store/csrfile.Open / Reader.SetHint — mmap the file read-only and hint the OS about the access pattern (AccessSequential).
• search/extern.PageRankCtx / extern.DefaultPageRankOptions — semi-external, context-aware PageRank over the mmap-backed reader; only the rank vector lives in RAM.

Further reading

• store/csrfile — the Tier 2 on-disk CSR format and mmap-backed reader
• search/extern — semi-external graph algorithms over a csrfile.Reader
• graph/csr — the immutable Tier 1 in-memory CSR snapshot
• Example 18 — out-of-core pipeline — CSV ingest plus Tier 2 BFS and PageRank
• Example 26 — social scale bench — the reference end state for the examples standard
• docs/examples-standard.md — the standard every example follows