Documentation
¶
Overview ¶
Package rungraph builds the run graph's CSR projection: the second surface of [ADR-0404], never mixed with the structural starmap and never authoritative.
The run graph is a forest. Millions of components of about thirty nodes each — an element instance and the scopes, boundary events and race groups around it — with an average degree of 4.8. That topology is what decides the layout: there is nothing deep to traverse, so a whole-graph pass is millions of independent tiny walks, and what makes those walks affordable is not cleverness but locality.
Three rules from the record are in this code rather than in prose around it:
- **The projection is disposable.** It is never a source of truth, never backed up, and a lost or stale one is rebuilt. That is what keeps it from being the second store ADR-0179 refused.
- **The build is all-or-nothing.** A partially built CSR answers wrongly in a way no reader can see, so a failed build returns nothing at all and leaves whatever projection already existed in place.
- **Ordinals are the scan position.** See BuildOrdinals.
[ADR-0404]: ../docs/adr/0404-the-whole-graph-can-be-walked.md
Index ¶
- type Axis
- type Cell
- type Cloud
- type Drift
- type Follower
- type Graph
- type Log
- type Membership
- func (m *Membership) Count() int
- func (m *Membership) Labels() []uint32
- func (m *Membership) Len() int
- func (m *Membership) Members(key uint64) []uint64
- func (m *Membership) Of(key uint64) (component uint64, ok bool)
- func (m *Membership) SameComponent(a, b uint64) bool
- func (m *Membership) Size(key uint64) int
- type Ordinals
- type Source
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Axis ¶
type Axis uint8
Axis is what a cloud groups by. ADR-0404 §5 names five dimensions the nodes "already carry" — definition, element, worker, incident state, time bucket — and measured against model.ElementInstanceValue the node carries two of them, plus the BPMN element type as a refinement of the second. Those three are here. The other three are a join and a per-node array of 4 bytes — 420 MB at 110 M nodes, the same budget unit whose doubling §5's membership decision refused — so they are a cost for the record to weigh rather than a default to ship.
The zero value is not an axis: a cloud grouped by whatever a switch's default happens to be would report a density over something the caller did not ask for.
const ( // ByDefinition groups by ProcessDefKey: how much of the graph belongs to each // deployed process definition. ByDefinition Axis = iota + 1 // ByElement groups by an element *within* its definition. ElementId is an index into // the compiled graph rather than a global identifier, so the definition is part of the // cell: without it, element 1 of two processes would be one cell describing neither. ByElement // ByElementType groups by BpmnElementType — how much of the graph is service tasks, // how much is timers, and so on, across every definition. ByElementType )
type Cell ¶
Cell is one group of a cloud and the number of nodes in it. Which fields are meaningful follows from the cloud's axis: ByDefinition sets Definition, ByElement sets Definition and Element, ByElementType sets ElementType. The rest stay zero rather than being filled with a value that would read as a claim.
type Cloud ¶
Cloud is a density: cells with counts, the axis they are cells of, and the log position the count is true as of.
**It is an aggregation, not a clustering** (§5), and the consequence is what makes the cloud affordable where the walk is not: a group-by is not a graph operation. It costs one scan of the store and a map sized by the number of *cells*, so it needs no ordinal map, no CSR and no union-find — none of the 2,448 MB the structure costs at 110 M nodes, and none of §9's budget. An installation whose whole-graph walk §9 refuses can still be drawn as a cloud.
Axis and Position are fields rather than documentation because §5's own rendering rule forbids a picture that cannot say what it is dense *in* and *as of when*, and a renderer cannot add either honestly if the number does not carry them.
func BuildCloud ¶
BuildCloud counts the live element instances of src into cells of the given axis.
It reads the position first, so a source that cannot say when its snapshot is true fails before the scan rather than producing a density nobody can date. A scan that fails part-way is an error and not a thin cloud: a count is plausible at every size, so a partial one has nothing in the shape of its answer to say it is wrong.
func (*Cloud) Cells ¶
Cells returns the cloud's cells in ascending order of definition, element and element type. The order is imposed rather than inherited: a Go map iterates randomly, and a cloud whose cells reshuffle between rebuilds breaks the same promise §5 kept by choosing components over a Louvain partition — that a saved view keeps its meaning.
type Drift ¶
type Drift struct {
Position uint64 // the seed's position: what the projection reflects
Durable uint64 // the durable watermark the measurement stopped at
Arrived uint64 // element instances activated since the seed
Departed uint64 // element instances completed or terminated since the seed
Gap bool // records between the seed and the log's start are gone
}
Drift is how far a projection has fallen behind the log since it was seeded, measured in **node-set changes** rather than in records. A busy installation writes far more variables, jobs and timers than element instances, so a record count would overstate staleness by orders of magnitude and call for rebuilds nothing needed.
Position is the projection's own position — what it is true as of. Durable is how far durability reached when the drift was last measured. The two together are the interval the counts describe.
func (Drift) Changes ¶
Changes is the drift as one number: every node the projection does not have, plus every node it has and reality does not. Both directions count, because either makes the picture wrong.
func (Drift) RebuildDue ¶
RebuildDue reports whether a projection of nodes nodes should be rebuilt rather than kept, given a threshold expressed as a fraction of its size.
The threshold is relative on purpose: a thousand changes are nothing to a hundred-million-node projection and everything to one of two thousand, so an absolute number would be wrong at one end of the range or the other — the same reason §9's budget is stated in bytes rather than in nodes. Two cases are answered before the arithmetic: a gap cannot be caught up from at all, and any change at all against an empty projection makes it wrong, where a fraction of zero is not a number.
type Follower ¶
type Follower struct {
// contains filtered or unexported fields
}
Follower measures a projection's drift from the durable log. It is the second half of ADR-0404 §4 — *"kept current from the tailer"* — and what "kept current" can mean here is decided by the structure rather than by preference. An increment can add and cannot remove:
- a completing element instance is *deleted* from state (engine/apply.go, on IntentCompleted and IntentTerminated), so in any steady-state installation the node set shrinks as fast as it grows;
- the CSR is packed and undirected, so one new edge has to be inserted into *both* endpoints' adjacency lists, one of which is in the middle of a two-gigabyte array;
- union-find merges incrementally by design and cannot un-merge, so a removed edge cannot be undone without the component pass running again.
So the follower does not mutate the graph. It counts how far the node set has drifted since the seed and lets that number decide when a rebuild is due (Drift.RebuildDue) — which keeps the projection exactly as of its position, the one property every consumer needs (§5) and the one an in-place mutation would destroy.
A Follower is not safe for concurrent use: drive it from one goroutine, off the processing loop, one Follower.Follow at a time.
func NewFollower ¶
NewFollower returns a Follower measuring drift from a projection seeded at the given log position.
func (*Follower) Follow ¶
Follow reads the log up to durable — the caller's statement of how far durability reaches, the state store's LastAppliedPosition — and returns the drift accumulated since the seed. It is cumulative: the number is the distance from the seed, not from the previous call, because that is the number a rebuild threshold is about.
Two properties are load-bearing and cost nothing:
**It starts at the seed's position without seeking.** A wal.Cursor cannot be constructed — its fields are unexported and there is no seek — so the first read starts at whatever cursor the log gives out and every record at or below the position already counted is skipped. That is the same re-derivation the OpenSearch exporter does from its high-water mark, and it costs a header decode per record rather than an application.
**It is therefore idempotent under re-delivery.** A cursor is valid within one process run and a restart resumes from genesis by design (ADR-0114), so a follower is going to be handed records it has already seen. Skipping by position means it cannot double-count them, and a failed read — whose cursor must not be adopted — simply re-reads.
A record whose position is more than one past what has been counted means the records in between are gone: positions are a dense monotonic sequence (one counter, incremented once per event in engine/context.go), so compaction (ADR-0131) is the only thing that removes them and nothing can supply them again. Follow reports that as Drift.Gap and keeps counting what it can see: a caller deciding what to do wants to know how much it is missing even when the answer is "rebuild".
On an error nothing is advanced — neither the cursor nor the counts — so the next call re-reads the interval rather than skipping records it never saw.
type Graph ¶
type Graph struct {
// Ordinals is the map the arrays below are indexed by. Held rather than passed
// alongside, because an offsets array and an ordinal map from different builds are a
// graph whose every answer is plausible and wrong.
Ordinals *Ordinals
// Offsets has (n+1) entries: node i's neighbours are Targets[Offsets[i]:Offsets[i+1]].
// The extra entry is what makes the last node's slice expressible without a special
// case, and it is present even at n=0.
Offsets []uint32
// Targets holds every edge **twice**, once in each endpoint's list. An undirected CSR
// is what impact analysis needs: "what does this reach" and "what reaches this" are
// both asked, and a one-directional store answers only one of them. This doubling is
// what corrected the record's own size table upward — 2 × m, not m.
Targets []uint32
// Edges counts edges, not entries in Targets. len(Targets) is 2 × Edges.
Edges int
}
Graph is the CSR projection: an offset per node and a concatenated array of neighbour ordinals (ADR-0404 §2). Two flat, pointer-free arrays, which is exactly what lets §10 decide *where* they live — heap, or mmapped files — without changing anything about the structure or the walk.
func Build ¶
Build projects the source into a CSR.
Three passes over the view, which is the honest cost and not an oversight. The ordinals have to be complete before any edge can be counted, because an edge's far endpoint may have a higher key than the element that names it; and the offsets have to be complete before any target can be placed, because CSR is a packed layout with no room to grow a list. Count-then-fill is what every CSR build does, here and in Neo4j's GDS.
It returns (nil, err) on any failure, never a partial graph — see the package comment.
func (*Graph) Components ¶
Components labels every node with its connected component, in one pass over the CSR by union-find (ADR-0404 §5). The run graph is a forest of millions of small components, so "what is this element connected to" becomes a label lookup afterwards rather than a walk — which is what Graph.Membership is over this array.
This comment used to say the pass *is* the instance-family decomposition, repeating §5. W2's acceptance measurement on engine-written state disproved it: two service tasks on parallel top-level branches of one instance share only the process instance as a parent, and a process instance is not an element instance, so nothing joins them and one instance becomes two components (rungraph/component_test.go). A component is the **reference-connected** group, which is the grouping impact analysis wants; the instance grouping is a field on the element instance and needs none of this.
The return is one label per ordinal, and the label is the smallest ordinal in the component. That choice is not cosmetic: it makes the label stable under a rebuild that sees the same graph, and it makes a component's label the start of its ordinal range wherever the locality §10 relies on actually holds.
Path halving plus union by smaller label, which is what keeps this linear enough to run over a hundred million nodes without a second structure. Rank is deliberately not tracked: the label has to be the minimum ordinal, so the union direction is already determined and a rank array would only fight it.
func (*Graph) Follower ¶
Follower returns a Follower measuring g's drift from log. The seed is g's own position, which is why a graph has to state one (see Graph.Position).
func (*Graph) Locality ¶
Locality measures the property ADR-0404 §10 rests on: that a component's nodes are contiguous in ordinal space, so its adjacency lists are contiguous in Targets and a walk of one component reads sequential pages.
Span is (max ordinal − min ordinal + 1) summed over components, divided by the node count. 1.0 is perfect — every component occupies an unbroken ordinal range. 2.0 means components are interleaved two deep, and a large number means the ordinals carry no locality at all and §10's mmap dial would be paying the 74× scattered-read penalty its own measurement found.
It is a method rather than a test helper because the claim is a property of the built graph and an operator choosing where the CSR lives has the same question a test does.
func (*Graph) Membership ¶
func (g *Graph) Membership() *Membership
Membership runs the membership pass and returns the lookup surface over it.
It holds the label array Graph.Components returned rather than building an index of its own, and that is a budget decision rather than laziness. ADR-0404 §2 budgets *one* union-find array — 420 MB at 110 million nodes — and Components already flattens it so a lookup is a single read. A Membership that grouped members by component for O(1) enumeration would add a second array of the same size, doubling the structure the record sized.
What that costs is enumeration: Membership.Members scans instead of slicing. The trade is the right way round because of which query has to be cheap *at that size*. §9 makes the narrow scope the entry and the whole graph the exception, so enumerating a component happens on a graph of thousands of nodes, where a scan is free; while the lookup — the query that runs at whole-graph scale — is O(1) already. Paying 420 MB to make the rare query faster on the rare graph is the wrong purchase, and it is one nobody could take back later.
func (*Graph) Neighbours ¶
Neighbours is node ord's adjacency list. The slice aliases Targets: a walk reads it and does not own it.
func (*Graph) Position ¶
Position is the log position this projection is as of: the highest position folded into the snapshot it was seeded from (§4). It is what a tailer resumes at, and what a picture drawn from this graph has to name as its "as of" (§5).
Read through the ordinal map rather than copied beside it, for the reason the map itself is held rather than passed alongside: two fields that can disagree are a graph whose every answer is plausible and wrong.
type Log ¶
type Log interface {
Read(from wal.Cursor, fn func(data []byte) (stop bool, err error)) (wal.Cursor, error)
}
Log is the part of wal.Tailer a follower uses: durable records forward from a cursor, with the option to stop. It is an interface so the follower can be driven by a log in a test without a WAL directory, and so nothing in this package holds the writing wal.Log (invariant I3).
type Membership ¶
type Membership struct {
// contains filtered or unexported fields
}
Membership answers which component a node belongs to.
A component's *name* is the key of its smallest ordinal. That is W1's label choice used for what it was chosen for: the smallest ordinal is stable under a rebuild that sees the same graph, so a component keeps its name across rebuilds and a saved view (§9) keeps its meaning.
Two kinds of question live here and they cost different things, which the method comments state rather than leave to be discovered:
- **Lookups.** Membership.Of and Membership.SameComponent are a binary search over the ordinal map and one array read. Nothing touches the CSR. This is the query §5 promises as a lookup, and the one an impact analysis asks a million times.
- **Passes.** Membership.Members, Membership.Size and Membership.Count read the whole label array once. They are O(n) and say so.
func (*Membership) Count ¶
func (m *Membership) Count() int
Count is how many components the graph decomposes into. One pass and no allocation: a node is its component's representative exactly when its label is its own ordinal, which holds because the label is the smallest ordinal in the component.
func (*Membership) Labels ¶
func (m *Membership) Labels() []uint32
Labels is the raw label-per-ordinal array, for a caller doing its own pass over it — the cloud's group-by (§5) is one. It aliases the membership's own array: a caller that writes to it changes what every lookup here answers.
func (*Membership) Len ¶
func (m *Membership) Len() int
Len is how many nodes the membership covers.
func (*Membership) Members ¶
func (m *Membership) Members(key uint64) []uint64
Members is every member key of the component this key belongs to, in ascending key order — nil for a key the graph does not hold.
One pass over the label array, for the reason Graph.Membership gives. Ascending key order comes free: ordinals are the scan position of an ascending scan, so ascending ordinal *is* ascending key, and the caller's next move — showing the members, or reading them back out of the store — wants an order it did not have to impose.
Deliberately not derived from the component's ordinal range. W1 measured that a component occupies a contiguous range only when instances arrive sequentially; under concurrent arrival the span grows with the concurrency, so a range-based answer would be right on a quiet installation and silently wrong on a busy one.
func (*Membership) Of ¶
func (m *Membership) Of(key uint64) (component uint64, ok bool)
Of is the component of the node with this key: a binary search and one array read, touching no part of the CSR. ok is false for a key the graph does not hold, which includes every key written after the snapshot the graph was built from.
func (*Membership) SameComponent ¶
func (m *Membership) SameComponent(a, b uint64) bool
SameComponent reports whether two keys are reference-connected — the question an impact analysis asks, answered by two lookups and no walk.
A key the graph does not hold is in no component, so it is not in another key's component and not in another absent key's either. Answering true for two unknown keys would be the worse failure: an analysis over stale keys would report the whole estate as related.
func (*Membership) Size ¶
func (m *Membership) Size(key uint64) int
Size is how many members the component has, counted without building the list. It is what a cloud asks per component, and an allocation per component is what §9's budget cannot afford at whole-graph scale. 0 for a key the graph does not hold.
type Ordinals ¶
type Ordinals struct {
// Position is the log position the snapshot these keys came from was as of (§4). The
// map is the persisted half of the projection, so it is the half that has to record
// when it is true: one persisted at an unknown position cannot be reconciled with a
// log, and a tailer could only resume from genesis.
Position uint64
// contains filtered or unexported fields
}
Ordinals is the persisted key→ordinal map ADR-0404 §3 requires.
It is the sorted key array and nothing else: the ordinal *is* the index. That removes the second structure a hash map would be — one that has to be kept consistent with the keys and rebuilt identically on every restart — and it makes the inverse free, which matters because a walk's result is ordinals and a reader needs keys.
§3 insists the map is persisted rather than rederived: without that, every restart renumbers every node and any saved finding, exported picture or bookmarked walk refers to nothing. A flat ascending uint64 array is the persistable shape, and it is also the mmap-able one §10's dial wants.
func BuildOrdinals ¶
BuildOrdinals assigns an ordinal to every element instance, in key order.
"In key order" is the whole point and it costs nothing here. Keys are written big-endian (`state/keys.go`, appendBE64), so a prefix scan of the column family arrives ascending and the ordinal is simply the scan position. What that buys is §10's locality: keys are minted in increasing order, so one instance's element instances are numerically close, so a component's nodes are contiguous in ordinal space, so its adjacency lists are contiguous in the targets array. A walk of one component then reads a few sequential pages instead of scattering — and §10's measurement is why that is worth designing for rather than hoping for: a scattered read under a memory cap, without MADV_RANDOM, ran 74× slower than a sequential one.
Because the whole property rests on the scan being ascending, this refuses a scan that is not. A descending or unordered stream would produce a map whose binary search is wrong and whose ordinals carry no locality, and it would do so silently.
func (*Ordinals) Key ¶
Key is the inverse. It panics on an out-of-range ordinal, which is a programming error rather than a data condition: every ordinal in a graph came from this map.
func (*Ordinals) Ordinal ¶
Ordinal is the dense id for a key, and reports whether the key is a node at all. The second return is not ceremony: three of the four references on an element instance can name something that is not in this graph, and an edge invented for one of those would land on an unrelated node.
type Source ¶
type Source interface {
ActiveElementInstances(fn func(key uint64, v *model.ElementInstanceValue) error) error
// LastAppliedPosition is the log position the snapshot is as of — the highest position
// folded into the state it shows. §4 keeps the projection current "from the tailer,
// starting at the snapshot's position", so a source that cannot say which position that
// is cannot seed a projection anybody could resume from; and §5 forbids a picture that
// cannot say as of when it is true. It is part of the interface rather than an optional
// assertion for that reason: a graph claiming "as of 0" would be indistinguishable from
// one genuinely at genesis, and a claim nobody can check is worse than no claim.
LastAppliedPosition() (uint64, error)
}
Source is the consistent view a build reads from: ADR-0404 §4 seeds from a snapshot of the state store rather than from genesis, because the exporter's cursor is valid only within one process run and a compacted log no longer holds genesis at all (ADR-0131).
`*state.ReadView` satisfies this, which is the intended caller: take the view on the run loop that owns the store, build off the loop, close the view when the build is done (ADR-0239, ADR-0382). The interface is narrow on purpose — a builder that could reach the live store would be a builder that could read two halves of different states.
Source Files