20_concurrent_reads

Example 20 — Concurrent reads over an immutable CSR

What it demonstrates

The lock-free read contract of a frozen csr.CSR: once a graph is snapshotted into an immutable CSR, any number of goroutines may traverse it simultaneously with zero synchronisation on the snapshot itself. A pool of worker goroutines runs the same mixed read workload — Dijkstra, BFS, and PageRank — concurrently over one shared CSR, and the example measures how read throughput scales with the worker count while proving that every concurrent read returns the same answer as a single-threaded read.

It also certifies GoGraph's intra-query parallel algorithm variants: search.WCCParallel, search.CountTrianglesParallel, and centrality.BetweennessParallel are each run against their serial counterparts and asserted to produce the same result — exactly for the canonical partition and integer counts, and within a tiny floating-point tolerance for betweenness (whose parallel reduction sums pair-dependencies in a different order). The measured serial-vs-parallel speedup is reported as telemetry. Cross-query safety (many readers, one snapshot) and intra-query parallel correctness are the two halves of the concurrency story.

Every PageRank call of a run shares one centrality.PageRankBudget of GOMAXPROCS worker slots, passed through PageRankOptions.Budget. PageRank parallelises internally once a graph reaches its parallel threshold, so without a budget each concurrent reader would start its own GOMAXPROCS-sized worker pool: N readers would run N × GOMAXPROCS PageRank workers that park on the per-iteration barrier. With the shared budget the readers together never run more than GOMAXPROCS PageRank workers; a reader that finds fewer than two free slots runs PageRank single-threaded on its own goroutine instead of waiting. The example demonstrates the caller-side wiring of that budget and shows it leaves every answer unchanged.

By default the read sweep is capped at GOMAXPROCS; pass -cap-to-cpus=false to drive the reliability mandate's high-concurrency levels (64/256/1024 readers over one immutable snapshot), which the lock-free contract must survive regardless of the core count.

Domain / scenario

A Barabási-Albert preferential-attachment network — the canonical model of a social / web graph, where a few high-degree hubs dominate and the degree distribution is heavy-tailed. The seeded generator builds it single-threaded so the RNG draws in a fixed order:

• It starts from a connected path core of seed-core nodes.
• Each subsequent node attaches attach edges to existing nodes chosen with probability proportional to their current degree (the standard repeated-node-list method), rejecting self-loops and parallel targets.
• Every edge carries an integer weight in [1, weight-max].

Because every new node attaches to the already-connected component, the graph is connected by construction — so BFS reaches every node and its reach count is a constant. The hub structure gives PageRank a well-separated top-k, and the high-degree fan-out makes each read do real CPU work. Integer weights keep Dijkstra free of NaN/Inf concerns and make distance sums exact.

The graph is built once into a mutable adjlist, then frozen into a single csr.CSR snapshot that every worker reads. The CSR is never mutated after it is built, so the readers need no lock on it. The only shared mutable state is per-level bookkeeping (an atomic read counter and an atomic mismatch flag) — never the snapshot.

How to run

go run ./examples/20_concurrent_reads                          # small deterministic default
go run ./examples/20_concurrent_reads -nodes 200000 -attach 8 -workers 16  # observable-scale run

Scale and flags

The sweep climbs worker counts 1, 2, 4, 8, … up to -workers, capped at GOMAXPROCS unless -cap-to-cpus=false. The default completes in well under a second; the large run does enough work per read for the scaling curve to be clearly observable.

Expected output

The deterministic fact lines below are stable for a fixed -seed. The # -prefixed telemetry lines (heap, throughput, durations) vary per run and per machine and are never pinned by the test.

config.nodes=4000
config.attach=4
config.seed_core=8
config.weight_max=10
config.iterations=16
config.top_k=10
config.seed=1
nodes.count=4000
edges.directed=31950
# mem.heap_alloc=755.83 KiB
# mem.heap_growth=552.22 KiB
# mem.num_gc=2
# pagerank.budget.capacity=10
ref.dijkstra_dist=17
ref.bfs_reached=4000
ref.pagerank_topk=[230,7,73,65,15,213,32,205,139,165]
# scale.workers_1.reads=16
# scale.workers_1.elapsed=27.229ms
# scale.workers_1.throughput=588 reads/s
# scale.workers_1.pagerank_budget_in_use=0
# scale.workers_2.throughput=1124 reads/s
# scale.workers_4.throughput=1638 reads/s
# scale.workers_8.throughput=2312 reads/s
parallel.wcc_matches_serial=true
parallel.triangles_matches_serial=true
parallel.betweenness_matches_serial=true
# parallel.betweenness.speedup=6.37x
reads.agree=true

ref.bfs_reached equals nodes.count (the graph is connected), ref.dijkstra_dist and ref.pagerank_topk are reproducible for the seed, and reads.agree=true is the headline correctness fact: every concurrent read at every worker count returned the same answer as the single-threaded reference.

Evidence it collects

This is a concurrency example, so it reports (per the taxonomy in docs/examples-standard.md):

• Aggregate throughput — reads/s of the mixed workload at each level.
• Per-worker-count scaling — the identical workload run at 1, 2, 4, 8 … workers. Throughput that climbs with the worker count shows the read path admits genuine parallelism — no global lock serialises the readers — but the curve is a performance observation, not the proof of lock-freedom (the correctness evidence below is). Its ceiling is set by memory bandwidth and the machine's core mix: the mixed workload, and especially its PageRank component, is largely memory-bound, so on a bandwidth-limited or hybrid performance/efficiency-core CPU the curve typically flattens well before the worker count reaches GOMAXPROCS rather than scaling linearly. Scale -nodes/-attach up to do more work per read and the climb extends further before it saturates.
• PageRank worker budget — # pagerank.budget.capacity is the number of worker slots shared by every PageRank call (GOMAXPROCS), and # scale.workers_N.pagerank_budget_in_use is the number of slots still held after level N has joined. It is 0 at every level: each PageRank run returns its slots on every exit path.
• Live heap — one immutable snapshot is shared, not copied per worker, so the heap does not grow with the worker count.

The correctness evidence — reads.agree=true plus the constant ref.* facts — is the proof that the lock-free read path is sound: many concurrent readers compute exactly what one reader computes.

Key APIs

• graph/adjlist.New / AdjList.AddEdge — build the mutable weighted graph, one directed relationship per edge.
• graph/adjlist.AdjList.Mapper — resolve node values to stable NodeIDs for the fixed source/target.
• graph/csr.BuildFromAdjList / CSR.BuildSymmetric — freeze the builder into an immutable CSR snapshot and project it to the symmetric (undirected) snapshot, the shared read surface for all goroutines.
• search.Dijkstra — single-source shortest paths; safe to call concurrently on a snapshot CSR.
• search.BFS — breadth-first traversal with a visit callback; allocation-free on the hot path after the first call.
• search/centrality.PageRank / DefaultPageRankOptions — power-iteration PageRank, safe to invoke from any number of goroutines on a snapshot CSR.
• search/centrality.NewPageRankBudget / PageRankOptions.Budget / PageRankBudget.InUse — one caller-owned pool of PageRank worker slots that bounds the parallel workers of all concurrent PageRank calls together.
• search.WCCParallel / search.CountTrianglesParallel / search/centrality.BetweennessParallelCtx — intra-query parallel variants, each cross-checked here against its serial counterpart over the same snapshot.

Further reading

• graph/csr — the immutable CSR snapshot and its concurrent-read contract
• search — Dijkstra and BFS package documentation
• search/centrality — PageRank and other centrality measures
• Example 01 — basic shortest paths — the single-threaded build-snapshot-query flow this example parallelises
• Example 08 — PageRank — PageRank in isolation
• Example 26 — social scale bench — the reference end-state example this one follows
• docs/examples-standard.md — the standard every example follows