graphcache

func (ContribID) IsZero ¶

func (c ContribID) IsZero() bool

IsZero reports whether c is the zero ContribID. Zero means "no identity" and disables dedup on the write path.

func (*GraphCache[S, T]) AddEdge ¶

func (c *GraphCache[S, T]) AddEdge(tail, head S, w float32)

func (*GraphCache[S, T]) AddEdgeWithExpiration ¶

func (c *GraphCache[S, T]) AddEdgeWithExpiration(tail, head S, w float32, expiration time.Time)

func (*GraphCache[S, T]) AddEdgeWithExpirationContrib ¶

func (c *GraphCache[S, T]) AddEdgeWithExpirationContrib(tail, head S, w float32, expiration time.Time, contribID ContribID) bool

AddEdgeWithExpirationContrib is the dedup-aware additive write used by the replication apply path (#182). A non-zero contribID makes the call idempotent: re-applying the same mutation (e.g. on peer reconnect or duplicate stream delivery) leaves the stored weight unchanged. A zero contribID falls through to ordinary additive semantics, which is the local non-replicated path. Returns applied=true when the contribution was recorded; false means dedup suppressed an already-stored contribution with the same ID.

func (*GraphCache[S, T]) AddEdgeWithExpirationContribHLC ¶

func (c *GraphCache[S, T]) AddEdgeWithExpirationContribHLC(tail, head S, w float32, expiration time.Time, contribID ContribID, ts hlc.Timestamp) bool

AddEdgeWithExpirationContribHLC is the tombstone-aware sibling of AddEdgeWithExpirationContrib used by the replication apply path (#183). When a live edge tombstone exists for (tail, head) whose HLC is strictly newer than ts the contribution is dropped and false is returned, preventing a late Add* from resurrecting a freshly-deleted edge. Otherwise behaviour matches AddEdgeWithExpirationContrib, including ContribID-based dedup. A successful apply clears any existing tombstone for the edge.

func (*GraphCache[S, T]) AddEdgeWithTTL ¶

func (c *GraphCache[S, T]) AddEdgeWithTTL(tail, head S, w float32, ttl time.Duration)

func (*GraphCache[S, T]) AddEdgesWithExpiration ¶

func (c *GraphCache[S, T]) AddEdgesWithExpiration(items []EdgeItem[S])

AddEdgesWithExpiration additively writes every supplied edge under a single write lock, auto-creating endpoint vertices on demand (matching the per-edge AddEdgeWithExpiration invariant). Concurrent readers see either the pre-batch or the post-batch state.

Each item's ContribID is honored: a non-zero id deduplicates the contribution (see AddEdgesWithExpirationContrib). Leaving ContribID at its zero value — the default — keeps the legacy non-idempotent additive path.

func (*GraphCache[S, T]) AddEdgesWithExpirationContrib ¶

func (c *GraphCache[S, T]) AddEdgesWithExpirationContrib(items []EdgeItem[S]) (effective []float32, deduped int)

AddEdgesWithExpirationContrib is the dedup-aware batch sibling of AddEdgesWithExpiration. It applies the whole batch under a single write lock and returns, index-aligned with items, the post-apply LIVE weight sum for each edge (#897), plus the number of items that were deduplicated — i.e. whose non-zero ContribID matched a live contribution already stored on the (tail, head) edge, so no weight was added. Items with a zero ContribID always apply (legacy additive semantics) and never count as deduped.

effective[i] is the edge's live weight sum after this batch's contribution was folded in, compacted against a single `now` sampled once for the whole batch (matching #838's single-clock-read pattern). On a dedup no-op it is the current live sum, so a client can read back the running total of a windowed counter without a second round-trip. It is a serving-node local view: under active replication a peer may hold contributions not yet streamed in, so treat it as a fast local estimate, not a cluster-wide total.

The dedup guarantee mirrors the per-edge AddEdgeWithExpirationContrib used by the replication apply path (#182): replaying a batch with the same ContribIDs leaves the stored weights unchanged. This is what lets a client-supplied idempotency key make AddEdge(s) safe to retry (#588).

func (*GraphCache[S, T]) AddEdgesWithExpirationContribHLC ¶ added in v0.9.0

func (c *GraphCache[S, T]) AddEdgesWithExpirationContribHLC(items []EdgeItem[S], ts hlc.Timestamp) (effective []float32, deduped int)

AddEdgesWithExpirationContribHLC is the tombstone-aware, single-lock batch sibling of AddEdgesWithExpirationContrib used by the LOCAL write path when replication is enabled. Additive merge already converges via ContribID set semantics regardless of delivery order, so the ts is NOT compared against a per-edge write watermark; it is consulted ONLY against the edge tombstone so a contribution whose ts is strictly older than a delete is dropped on the origin exactly as it is on every peer. Items whose ts loses to the tombstone are skipped and counted as deduped=false (they applied nothing); items with a matching live ContribID are deduped as in the non-HLC variant. Returns, index-aligned with items, the post-apply LIVE weight sum for each edge (#897) plus the number of items that added no weight (tombstone-dropped or ContribID-deduped). A tombstone-dropped item applied nothing, but its effective entry still reports the edge's current live sum — matching the ContribID-deduped path — so a genuinely nonzero live weight (e.g. from a newer contribution that re-created the edge) is never misreported as 0 (#918).

func (*GraphCache[S, T]) CountByPrefix ¶

func (c *GraphCache[S, T]) CountByPrefix(prefix string) int

CountByPrefix returns the number of LIVE vertices whose projected key starts with prefix. It walks the prefix index and counts only keys the vertex cache still resolves as live, so an entry that has expired but not yet been flushed is excluded — the count therefore equals len(ScanByPrefix(prefix)) and the number of live primary vertices matching prefix, independent of GC timing (#752). Returns 0 when the index has not been enabled.

func (*GraphCache[S, T]) DeleteByPrefix ¶

func (c *GraphCache[S, T]) DeleteByPrefix(ctx context.Context, prefix string, limit int) int

DeleteByPrefix removes every vertex whose projected key starts with prefix and returns the number of vertices deleted. limit caps the number of deletions in a single call; pass 0 (or a negative value) to delete the entire matching set. When the index has not been enabled, DeleteByPrefix returns 0 without touching the cache.

Deletion routes the whole matched set through a single vertices.DeleteMany, so the OnEvict / refcount / radix-removal chain runs once for the batch rather than once per key (#738). Edges incident to a deleted vertex are NOT removed eagerly here — they will be reclaimed by the next dangling-edge flush, matching the existing DeleteVertex contract.

func (*GraphCache[S, T]) DeleteByPrefixHLC ¶

func (c *GraphCache[S, T]) DeleteByPrefixHLC(ctx context.Context, prefix string, limit uint32, ts hlc.Timestamp, expiration time.Time) (int, error)

DeleteByPrefixHLC is the tombstone-aware sibling of DeleteByPrefix: every vertex whose projected key matches prefix receives a tombstone stamped at ts/expiration. Returns the number of vertices actually deleted (matching DeleteByPrefix). limit==0 means unlimited.

func (*GraphCache[S, T]) DeleteEdge ¶

func (c *GraphCache[S, T]) DeleteEdge(tail, head S) bool

DeleteEdge removes the (tail, head) edge and returns whether it was present.

func (*GraphCache[S, T]) DeleteEdgeHLC ¶

func (c *GraphCache[S, T]) DeleteEdgeHLC(tail, head S, ts hlc.Timestamp, expiration time.Time) bool

DeleteEdgeHLC removes the (tail, head) edge and stamps a tombstone. See DeleteVertexHLC for the late-replay rationale.

func (*GraphCache[S, T]) DeleteEdges ¶

func (c *GraphCache[S, T]) DeleteEdges(keys []EdgeKey[S]) int

DeleteEdges removes every supplied edge under a single write lock and returns the count of edges that were actually present. Concurrent readers observe either the pre-batch or the post-batch state.

func (*GraphCache[S, T]) DeleteEdgesByPrefix ¶ added in v0.16.0

func (c *GraphCache[S, T]) DeleteEdgesByPrefix(ctx context.Context, tailPrefix, headPrefix string, limit int) int

DeleteEdgesByPrefix removes every live edge whose tail projected key starts with tailPrefix AND whose head projected key starts with headPrefix, up to limit edges (limit <= 0 means unbounded), and returns the number of edges actually deleted.

The matching (tail, head) pairs are collected into a snapshot and deleted under a single c.mu.Lock, so concurrent readers observe either the pre- or post-batch state. Victims are gathered BEFORE any deletion so the walk never mutates the structures it is iterating — the same collect-then-delete discipline DeleteByPrefix uses on the vertex side.

The core method imposes no "at least one prefix non-empty" rule: both empty deletes every edge up to limit, which direct core callers may legitimately want. The service layer rejects the whole-graph wipe before calling in.

func (*GraphCache[S, T]) DeleteEdgesByPrefixHLC ¶ added in v0.16.0

func (c *GraphCache[S, T]) DeleteEdgesByPrefixHLC(ctx context.Context, tailPrefix, headPrefix string, limit int, ts hlc.Timestamp, expiration time.Time) (int, error)

DeleteEdgesByPrefixHLC is the tombstone-aware sibling of DeleteEdgesByPrefix used by the LOCAL write path when replication is enabled: every matching edge receives a tombstone stamped at ts/expiration so a late-replayed Add from a peer is resolved by last-writer-wins rather than silently resurrecting the edge (mirrors DeleteEdgesHLC / DeleteByPrefixHLC). Returns the number of edges actually deleted, matching DeleteEdgesByPrefix, and any ctx error observed mid-collection.

func (*GraphCache[S, T]) DeleteEdgesHLC ¶

func (c *GraphCache[S, T]) DeleteEdgesHLC(keys []EdgeKey[S], ts hlc.Timestamp, expiration time.Time) int

DeleteEdgesHLC is the batch sibling of DeleteEdgeHLC.

func (*GraphCache[S, T]) DeleteVertex ¶

func (c *GraphCache[S, T]) DeleteVertex(key S) bool

DeleteVertex removes the vertex (by key) and returns whether it was present.

func (*GraphCache[S, T]) DeleteVertexHLC ¶

func (c *GraphCache[S, T]) DeleteVertexHLC(key S, ts hlc.Timestamp, expiration time.Time) bool

DeleteVertexHLC removes the vertex and stamps a tombstone so a late Put*/Add* with an HLC strictly older than ts is rejected for the duration of expiration. Returns whether the vertex was present at call time. Edges of the vertex are NOT tombstoned by this call — they are still GC'd via the dangling sweep when their endpoints disappear, but a late AddEdge that re-creates an endpoint can still reappear. Callers that need full subgraph fencing should pair this with DeleteEdgesHLC for the relevant (tail, head) pairs.

func (*GraphCache[S, T]) DeleteVertices ¶

func (c *GraphCache[S, T]) DeleteVertices(keys []S) int

DeleteVertices removes every supplied vertex under a single write lock and returns the count of keys that were actually present (and therefore deleted). Concurrent readers observe either the pre-batch or the post-batch state. Vertex-owned side indexes (dict refs, prefix radix, search postings) are cleaned in one pass via the batch eviction hook so a large delete pays one acquisition per index instead of one per key (#738).

func (*GraphCache[S, T]) DeleteVerticesHLC ¶

func (c *GraphCache[S, T]) DeleteVerticesHLC(keys []S, ts hlc.Timestamp, expiration time.Time) int

DeleteVerticesHLC is the batch sibling of DeleteVertexHLC. Every key receives a tombstone, including ones not present in the live cache — this is intentional so a Delete-before-Add race is still resolved by LWW once the (out-of-order) Add arrives.

func (*GraphCache[S, T]) EdgeCount ¶

func (c *GraphCache[S, T]) EdgeCount() int

EdgeCount returns the live (tail, head) edge count under an RLock. Like VertexCount it is intended for periodic gauge sampling, not hot paths.

func (*GraphCache[S, T]) EnablePrefixIndex ¶

func (c *GraphCache[S, T]) EnablePrefixIndex(extract func(S) string)

EnablePrefixIndex turns on the optional prefix index, projecting each key S through extract to obtain the string used by ScanByPrefix / CountByPrefix / DeleteByPrefix. It must be called before any vertex is stored; calling it on a non-empty cache panics so the caller cannot silently observe an index that disagrees with point reads. extract must not be nil.

EnablePrefixIndex is intentionally separate from the constructor:

• GraphCache is generic over S comparable, but prefix semantics are well-defined only for string-like keys. Lifting the constraint into the signature would force every caller (including those that never want prefix scans) to thread a projection through;
• opt-in keeps the put / evict hot paths free of any radix work for the existing string-keyed deployments that have not migrated.

func (*GraphCache[S, T]) EnableSearchIndex ¶

func (c *GraphCache[S, T]) EnableSearchIndex(extract func(T) search.Document, opts ...SearchIndexOption)

EnableSearchIndex turns on the optional content-search index, projecting each stored value T into the search.Document that gets indexed (for example the vertex's string value). Like EnablePrefixIndex it must be called before any vertex is stored, is idempotent, and panics on a non-empty cache so the caller cannot silently observe an index that disagrees with point reads. extract must not be nil. By default the index records positional postings for phrase and proximity queries; pass WithoutSearchPositions to build the leaner position-free index (#908).

Once enabled, the index is kept in perfect lockstep with the vertex lifecycle: every put (including overwrites) re-indexes the value, and eviction — Delete, DeleteMany, Clear, and TTL Flush — drops the key through the shared SetOnEvictMany hook, so entries decay together with the vertices they describe. The index is a third opt-in secondary structure alongside the prefix index; when it is left disabled the put / evict hot paths pay only a nil check.

func (*GraphCache[S, T]) GCSweepBacklog ¶ added in v0.11.0

func (c *GraphCache[S, T]) GCSweepBacklog() int

GCSweepBacklog reports how many tail buckets remain in the current incremental sweep cycle (#744) — those not yet visited by flush(). It is 0 when the incremental sweep is disabled or a cycle has just completed, and lets operators see when bounded cleanup is falling behind the write rate.

func (*GraphCache[S, T]) GetEdgeDetail ¶

func (c *GraphCache[S, T]) GetEdgeDetail(tail, head S) (float32, time.Time, bool)

GetEdgeDetail returns the current edge weight together with the latest contribution expiration. The expiration is the moment after which the edge is guaranteed to have decayed to zero. When no edge exists, ok is false.

Like GetWeight it is a lock-free point read (see edges.getDetail): it does not take GraphCache.mu and may observe either the pre- or post-write state under a concurrent edge mutation, but it never resolves a recycled endpoint id to an unrelated edge. The edge is hidden unless both endpoint vertices are still live, so a dangling edge to a deleted or expired-but-not-flushed vertex is reported as absent (#750).

func (*GraphCache[S, T]) GetVertex ¶

func (c *GraphCache[S, T]) GetVertex(key S) (T, bool)

GetVertex returns the live value stored for key. It is a point read that does not take GraphCache.mu: the inner vertex cache has its own RWMutex and hides expired entries, so a point lookup needs no aggregate-lock consistency with the prefix/search/edge indexes. Dropping c.mu here keeps hot reads from serializing behind unrelated writes, long scans, and GC (#740). A read may race a concurrent Put/Delete on the same key and observe either the pre- or post-write state, which is the existing point-read contract.

func (*GraphCache[S, T]) GetWeight ¶

func (c *GraphCache[S, T]) GetWeight(tail, head S) (float32, bool)

GetWeight returns the additive weight of the (tail, head) edge. Like GetVertex it is a lock-free point read: edges.get pins both endpoint ids (closing the dictionary ABA hazard) and reads the edge map under the edgeCache's own lock, so GraphCache.mu is not required (#740).

The edge is hidden (ok=false) unless both endpoint vertices are still live, so a dangling edge whose tail or head was deleted or expired but not yet swept is reported as absent (#750). The endpoint check reads the vertex cache under its own lock, after the edge read, so GetWeight stays free of GraphCache.mu.

func (*GraphCache[S, T]) LocalCommunity ¶ added in v0.15.0

func (c *GraphCache[S, T]) LocalCommunity(seed S, maxSize int, alpha, epsilon float64, weighting EdgeWeighting, keep func(S) bool) (*graph.Graph[S, T], map[S]map[S]time.Time)

LocalCommunity is the context-free convenience wrapper over LocalCommunityContext using context.Background(). See that method for the full contract.

func (*GraphCache[S, T]) LocalCommunityContext ¶ added in v0.15.0

func (c *GraphCache[S, T]) LocalCommunityContext(ctx context.Context, seed S, maxSize int, alpha, epsilon float64, weighting EdgeWeighting, keep func(S) bool) (*graph.Graph[S, T], map[S]map[S]time.Time, error)

LocalCommunityContext extracts the conductance-optimal local community around seed (#845): PageRank-Nibble — the shared ACL forward-push followed by a sweep cut. Vertices touched by the push are ordered by p(v)/d_w(v) descending (d_w = weighted out-degree after the weighting transform; sinks use a degree floor of 1; ties broken by ascending key order for determinism, with the seed always first) and the prefix minimising the directed weighted out-volume conductance is selected:

phi(S) = cut(S) / min(vol(S), volTouched − vol(S))

maintained incrementally from out-adjacency alone. The volume universe is the touched set — the subgraph the push localised — which keeps the sweep O(touched·log touched + edges(touched)) instead of scanning the whole graph; edges leaving the touched set still count toward cut(S).

maxSize caps the prefix length (the wire max_size — an UPPER BOUND, not an exact count: the sweep stops at the conductance minimum, which may come earlier). Degenerate sweeps (fewer than 3 touched vertices, or a monotone conductance profile with no interior minimum) fall back to top-maxSize by PPR mass, so selection degrades to the PPR arm's behaviour.

Output contract — unlike the PPR relevance star, structure is preserved: the result is the INDUCED SUBGRAPH on the selected set: every member's live value plus every live edge among members with its weight and expiration, in the same (graph, expirations) shape as NeighborWithExpirationsContext. Edge weights carry the SAME weighting transform the sweep used, consistent with the BFS family: WeightingRaw (the default) returns the verbatim stored weight, so the structure- preserving view is unchanged; WeightingTFIDF/WeightingBM25 return the re-scored weight — which is also what a subsequent Reduction reduces over, so the tree honours the weighting. An unknown seed yields an empty graph.

func (*GraphCache[S, T]) Neighbor ¶

func (c *GraphCache[S, T]) Neighbor(seed S, step int, k int, weighting EdgeWeighting, selectSmallest bool, keep func(S) bool) *graph.Graph[S, T]

Neighbor walks the graph from seed and returns the visited subgraph. The per-hop top-k pruning keeps the k largest-weight edges when selectSmallest is false and the k smallest-weight edges when it is true (#560) — the caller picks the direction that matches its Objective so a cost-minimiser is not handed the costliest edges. weighting re-scores edge weights BEFORE the directional top/bottom-k selection (#800).

keep is an optional frontier predicate (nil = accept all): a candidate head is expanded into the result only when keep(head) is true. It is applied at frontier materialisation, BEFORE scoring and the directional top/bottom-k prune, so top-k selects the k best *accepted* neighbours per hop. The seed is the anchor exemption — it is always retained and never passed through keep. Because the next-hop frontier is derived from the surviving edges, a matching vertex reachable only through a rejected "bridge" is not reached (induced-subgraph semantics). core stays generic: keep is just a predicate over S; the concrete prefix/string logic lives in the caller.

func (*GraphCache[S, T]) NeighborContext ¶

func (c *GraphCache[S, T]) NeighborContext(ctx context.Context, seed S, step int, k int, weighting EdgeWeighting, selectSmallest bool, keep func(S) bool) (*graph.Graph[S, T], error)

NeighborContext is the context-aware variant of Neighbor. It returns ctx.Err() as soon as the context is cancelled or its deadline has expired — checked between BFS expansion steps — so handlers can short-circuit large traversals when the caller has given up. keep is the optional frontier predicate documented on Neighbor (nil = accept all).

func (*GraphCache[S, T]) NeighborWithExpirationsContext ¶

func (c *GraphCache[S, T]) NeighborWithExpirationsContext(ctx context.Context, seed S, step int, k int, weighting EdgeWeighting, selectSmallest bool, keep func(S) bool) (*graph.Graph[S, T], map[S]map[S]time.Time, error)

NeighborWithExpirationsContext returns the same subgraph as NeighborContext together with a parallel expirations map keyed by (tail, head). Both are computed under a single RLock so handlers can compose responses without re-acquiring the cache lock per edge.

The expirations map only contains entries for edges that ended up in the returned graph; a missing or zero value means the edge has no known expiration. keep is the optional frontier predicate documented on Neighbor (nil = accept all).

func (*GraphCache[S, T]) PersonalizedPageRank ¶ added in v0.14.0

func (c *GraphCache[S, T]) PersonalizedPageRank(seed S, topN int, alpha, epsilon float64, weighting EdgeWeighting, keep func(S) bool) *graph.Graph[S, T]

PersonalizedPageRank is the context-free convenience wrapper over PersonalizedPageRankContext using context.Background(). See that method for the full contract.

func (*GraphCache[S, T]) PersonalizedPageRankContext ¶ added in v0.14.0

func (c *GraphCache[S, T]) PersonalizedPageRankContext(ctx context.Context, seed S, topN int, alpha, epsilon float64, weighting EdgeWeighting, keep func(S) bool) (*graph.Graph[S, T], error)

PersonalizedPageRankContext ranks vertices by their Personalized PageRank (a.k.a. Random-Walk-with-Restart) relevance to seed and returns a relevance star: a graph whose seed→v edge weight is π[v], the stationary mass a seed-anchored random surfer accumulates on v. It replaces the greedy, per-hop Top(k) walk of Neighbor* with a single global, seed-relative score (#801), so a vertex reached via many paths outranks one reached via a single weak path, and a globally popular hub is discounted relative to this seed.

It is computed by local forward-push (Andersen–Chung–Lang): residual mass is pushed only through vertices whose residual exceeds eps·deg, touching O(1/(alpha·eps)) vertices independent of |V|/|E|. alpha is the restart probability (locality knob: higher = tighter, seed-proximate); epsilon the residual threshold (smaller = more accurate, more work). Non-positive or out-of-range alpha/epsilon fall back to DefaultPPRAlpha / DefaultPPREpsilon.

weighting transforms each transition affinity BEFORE row-normalization (raw / tfidf / bm25, via the shared scoreEdge kernel) so BM25-weighted PPR composes for free. keep is the optional frontier predicate (#601): a head is only walked into (and ranked) when keep(head) is true; the seed is the anchor exemption. ctx is polled every pprCtxCheckInterval pushes and returns ctx.Err() when cancelled. topN caps the ranked vertices returned (the request k); topN <= 0 returns every vertex with positive mass. An unknown seed yields an empty graph (the seed vertex alone is never emitted without neighbours).

func (*GraphCache[S, T]) PutEdgeWithExpiration ¶

func (c *GraphCache[S, T]) PutEdgeWithExpiration(tail, head S, w float32, expiration time.Time)

PutEdgeWithExpiration atomically replaces the (tail, head) edge weight. AddEdgeWithExpiration is additive (Add semantics) so a naive "DeleteEdge + AddEdgeWithExpiration" sequence performed by callers exposes a window in which concurrent GetEdge readers observe a spurious NotFound. PutEdgeWithExpiration takes the write lock once and performs the delete + add under the same lock, restoring atomicity for the idempotent Put semantics.

func (*GraphCache[S, T]) PutEdgeWithExpirationHLC ¶

func (c *GraphCache[S, T]) PutEdgeWithExpirationHLC(tail, head S, w float32, expiration time.Time, ts hlc.Timestamp) bool

PutEdgeWithExpirationHLC is the LWW-aware sibling of PutEdgeWithExpiration used by the replication apply path. Returns applied=false when the stored edge's last accepted HLC is strictly newer than ts. Endpoint vertices are auto-created (matching PutEdgeWithExpiration) regardless of the LWW outcome, unless an edge tombstone rejects the write before storage is touched.

func (*GraphCache[S, T]) PutEdgesWithExpiration ¶

func (c *GraphCache[S, T]) PutEdgesWithExpiration(items []EdgeItem[S])

PutEdgesWithExpiration replaces every supplied edge atomically under a single write lock. Each (tail, head) pair is deleted and re-added so the resulting weight is exactly the supplied weight — matching PutEdgeWithExpiration semantics for each item in the batch.

func (*GraphCache[S, T]) PutEdgesWithExpirationHLC ¶ added in v0.9.0

func (c *GraphCache[S, T]) PutEdgesWithExpirationHLC(items []EdgeItem[S], ts hlc.Timestamp) (rejected int)

PutEdgesWithExpiration used by the LOCAL write path when replication is enabled. Like PutVerticesWithExpirationHLC it stamps every edge with the originating mutation's ts so PutEdge resolves as an LWW-Register on (tail, head) across replicas rather than diverging when two origins write the same edge concurrently. Endpoint vertices are auto-created regardless of the per-edge LWW outcome (matching PutEdgeWithExpirationHLC) so traversal always sees the endpoints.

Returns the number of items REJECTED by the tombstone fence or by the per-edge LWW watermark inside the storage layer — exactly the set the singular PutEdgeWithExpirationHLC reports as applied=false — so the replication apply path (#840) can fire its clamp-reject metric once per rejected item with unchanged meaning. ContribID dedup never contributes here (that is AddEdgesWithExpirationContribHLC's separate count).

func (*GraphCache[S, T]) PutVertex ¶

func (c *GraphCache[S, T]) PutVertex(key S, value T)

func (*GraphCache[S, T]) PutVertexWithExpiration ¶

func (c *GraphCache[S, T]) PutVertexWithExpiration(key S, value T, expiration time.Time)

func (*GraphCache[S, T]) PutVertexWithExpirationHLC ¶

func (c *GraphCache[S, T]) PutVertexWithExpirationHLC(key S, value T, expiration time.Time, ts hlc.Timestamp) bool

PutVertexWithExpirationHLC is the LWW-aware sibling of PutVertexWithExpiration used by the replication apply path. When the stored HLC for key is strictly newer than ts the call is a no-op and returns applied=false. A zero ts always applies and is recorded as the zero watermark (nothing can be strictly older than it). Local writers continue to use PutVertexWithExpiration; this helper is intentionally narrow to the replicated path so non-replicated workloads pay nothing.

func (*GraphCache[S, T]) PutVertexWithExpirationIfAbsent ¶ added in v0.16.0

func (c *GraphCache[S, T]) PutVertexWithExpirationIfAbsent(key S, value T, expiration time.Time) bool

PutVertexWithExpirationIfAbsent writes the vertex only when no live vertex exists at key (SET NX, #896). It returns true when the write was applied and false when it was skipped — either because an existing live vertex blocked it (the stored value and expiration are left untouched) or because the vertex was born expired and discarded (#918). Liveness follows the live-visibility rule (#750): an expired-but-uncollected vertex does not block the write. The existence check and the store happen under the same write lock, so two racing if-absent writers cannot both observe "absent" and both write.

func (*GraphCache[S, T]) PutVertexWithTTL ¶

func (c *GraphCache[S, T]) PutVertexWithTTL(key S, value T, ttl time.Duration)

func (*GraphCache[S, T]) PutVerticesWithExpiration ¶

func (c *GraphCache[S, T]) PutVerticesWithExpiration(items []VertexItem[S, T])

PutVerticesWithExpiration writes every supplied vertex under a single write lock. Concurrent readers observe either the pre-batch or the post-batch state — never an intermediate snapshot where some keys are present and others are not.

Search-document analysis (tokenization) for the whole batch runs BEFORE the lock is taken (see prepareSearchDocs) so the expensive per-vertex work never serializes other writers behind the aggregate graph lock; only the cheap store + postings mutation happens under c.mu (#739).

func (*GraphCache[S, T]) PutVerticesWithExpirationHLC ¶ added in v0.9.0

func (c *GraphCache[S, T]) PutVerticesWithExpirationHLC(items []VertexItem[S, T], ts hlc.Timestamp) (rejected int)

PutVerticesWithExpirationHLC is the LWW-aware, single-lock batch sibling of PutVerticesWithExpiration used by the LOCAL write path when replication is enabled. Every item is stamped with the SAME ts — the HLC the originating mutation is logged under — so the origin's own writes participate in last-writer-wins on equal footing with the values its peers apply from its mutation log.

This closes a convergence hole: when the local path used the non-HLC PutVerticesWithExpiration it stored a value WITHOUT recording a vertexHLC watermark, so a concurrently-written OLDER value replayed from a peer would clobber the origin's newer value on the origin (the incoming write saw no watermark to lose to) while every other replica kept the newer value — permanent divergence for the same key. Stamping the watermark here makes PutVertex an LWW-Register on every replica, exactly as docs/replication.md specifies ("Higher HLC wins; same HLC ⇒ higher origin ID wins").

Per item the usual guards apply: a write whose ts is strictly older than the key's tombstone, or strictly older than the key's stored vertexHLC, is skipped. Born-expired items follow the same dead-on-arrival handling as PutVerticesWithExpiration (the entry is removed, not stored) so the #698 high-water optimisation is preserved; the watermark is still recorded so a later strictly-older write cannot resurrect the key.

Returns the number of items REJECTED by those guards — tombstone fence or LWW watermark — exactly the set the singular PutVertexWithExpirationHLC reports as applied=false. Born-expired items are applied (dead on arrival, watermark recorded) and are NOT counted, and nothing else contributes, so the replication apply path (#840) can fire its clamp-reject metric once per rejected item with the same meaning the per-item loop had.

func (*GraphCache[S, T]) PutVerticesWithExpirationIfAbsent ¶ added in v0.16.0

func (c *GraphCache[S, T]) PutVerticesWithExpirationIfAbsent(items []VertexItem[S, T]) (written int, skipped []S)

PutVerticesWithExpirationIfAbsent writes each vertex only when no live vertex exists at its key (SET NX semantics, #896). It returns the number of vertices actually written and, in request order, the keys skipped because a live vertex already existed. A vertex whose expiration is already past is discarded and counted as neither written nor skipped (#918). Liveness follows the live-visibility rule (#750): an expired-but-uncollected vertex does not block its write. The whole batch commits under a single write lock, so the existence check and store are atomic per key; within one batch a key's first accepted write makes it live, so a later duplicate of that key is reported as skipped.

func (*GraphCache[S, T]) PutVerticesWithExpirationIfAbsentHLC ¶ added in v0.16.0

func (c *GraphCache[S, T]) PutVerticesWithExpirationIfAbsentHLC(items []VertexItem[S, T], ts hlc.Timestamp) (writtenIdx []int, skipped []S)

PutVerticesWithExpirationIfAbsentHLC is the replication-aware sibling of PutVerticesWithExpirationIfAbsent used by the LOCAL write path when replication is enabled (#896). Like the non-HLC variant it writes each key only when no live vertex exists there, but it additionally stamps every accepted write with the originating mutation's ts (and clears any tombstone) so the origin participates in last-writer-wins on equal footing with peers — the same discipline PutVerticesWithExpirationHLC uses. A key whose write is forbidden by the causal fence (a strictly newer delete/put watermark) is reported as skipped rather than resurrected.

It returns the indices of items that passed the absence check AND were actually stored (in request order) so the caller can both count them and replicate only that live subset as an unconditional LWW put, and the keys skipped because a live vertex already existed. A born-expired item is discarded and appears in neither slice (#918). Two concurrent if-absent writers on different nodes can both report their write as accepted locally; the replicated unconditional puts then converge via higher-HLC-wins (documented best-effort, like Redis SETNX with async replicas).

func (*GraphCache[S, T]) ScanByPrefix ¶

func (c *GraphCache[S, T]) ScanByPrefix(ctx context.Context, prefix string, fn func(projected string, key S, value T) bool) bool

ScanByPrefix iterates every live vertex whose projected key starts with prefix, in lexicographic order, invoking fn for each one. fn may return false to stop the walk early; iteration also stops when ctx is cancelled. The boolean return is fn's last verdict (true means the caller exhausted the result set without asking to stop).

Consistency: ScanByPrefix takes a point-in-time snapshot of the matching (projected, key, value) triples under c.mu.RLock and then releases the lock BEFORE invoking fn. As a result fn is free to call back into any GraphCache method (including writers) without deadlock, at the cost of possibly observing keys whose live state has since changed \u2014 the snapshot itself is consistent, but the cache may have moved on by the time fn runs. Callers that need to react to the live state should re-fetch via GetVertex inside fn.

Releasing the lock before fn runs also avoids the sync.RWMutex-reentrancy hazard: a concurrent writer queued on c.mu would otherwise block any nested RLock from the visitor's goroutine (Go's RWMutex forbids recursive read-locking when a writer is waiting), which previously deadlocked callers whose fn touched the cache. See #202.

If the prefix index has not been enabled (see EnablePrefixIndex), ScanByPrefix returns false immediately and invokes fn zero times. The boolean is true if the prefix index is enabled and the walk completed without fn requesting a stop.

Vertices whose TTL has already expired but which have not yet been flushed are skipped at snapshot time \u2014 ScanByPrefix returns the same set of vertices a matching sequence of GetVertex calls under the snapshot lock would have returned.

fn receives both the projected string key (the prefix-index view) and the original S key (the cache view). For S = string they coincide; for other S the projection is intentionally lossy and the original key is the one suitable for downstream GraphCache calls.

func (*GraphCache[S, T]) ScanByPrefixPage ¶ added in v0.15.0

func (c *GraphCache[S, T]) ScanByPrefixPage(ctx context.Context, prefix, after string, limit int, desc bool, fn func(projected string, key S, value T) bool) (more, ok bool)

ScanByPrefixPage is the paged form of ScanByPrefix (#836): it visits only live vertices whose projected key starts with prefix AND sorts strictly after `after` (ascending) or strictly before it (descending, #898), and collects at most limit of them (limit <= 0 means unbounded, i.e. exactly ScanByPrefix). The radix walk SEEKS past `after` instead of re-walking and discarding everything before the cursor, and collection stops one row past the page boundary, so a resumed page costs O(depth + page) instead of O(everything matching prefix) in both time and buffered memory.

desc selects the key order: false walks ascending (the historical default), true walks descending so a caller can read the newest N of a timestamp-ordered keyspace as one bounded page. In descending mode `after` is the previous page's last (smallest) key and the walk resumes strictly below it; an empty `after` starts from the high end of the prefix range.

more reports whether at least one further matching key exists beyond the returned page — the signal a paginating caller uses to mint a next cursor without a second walk. ok mirrors ScanByPrefix's return: false when the prefix index is disabled, ctx was cancelled, or fn stopped early. Locking and consistency semantics are unchanged from ScanByPrefix: rows are collected into a point-in-time snapshot under c.mu.RLock and fn runs after the lock is released.

func (*GraphCache[S, T]) ScanEdgesByPrefix ¶

func (c *GraphCache[S, T]) ScanEdgesByPrefix(
	ctx context.Context,
	tailPrefix, headPrefix string,
	fn func(tailProjected string, tail S, headProjected string, head S, weight float32, expiration time.Time) bool,
) bool

ScanEdgesByPrefix iterates every live edge whose tail projected key starts with tailPrefix AND whose head projected key starts with headPrefix, in ascending (tail, head) order, invoking fn for each one. Either prefix may be empty to disable the corresponding filter (both empty scans every edge).

fn may return false to stop the walk early; iteration also stops when ctx is cancelled. The boolean return is fn's last verdict — true means the caller exhausted the matching set without asking to stop.

Implementation: the walk reuses the vertex-side prefix index for the tail dimension. Every edge endpoint is auto-created as a vertex on insert (see AddEdgeWithExpiration / PutEdgeWithExpiration), so the radix already covers all live tails. For each matching tail the head dimension is served by a per-tail head radix (Issue #167) when available — see scanTailHeadsFast — or falls back to the v1 materialise-and-sort path (scanTailHeadsFallback) when the head index is disabled. The two paths emit identical (tailProj, headProj) sets for any given graph state.

Locking contract mirrors ScanByPrefix (#742): the matching edge rows are collected into a point-in-time snapshot under c.mu.RLock, the lock is released, and only THEN is fn invoked per row. Because fn runs after the lock is dropped, a slow visitor no longer starves writers for the whole scan, and fn MAY call back into GraphCache (including write methods) without risking sync.RWMutex reentrancy. The tradeoff is that fn observes a consistent snapshot taken at collection time, not necessarily the latest state after the lock was released, and an unbounded scan buffers one row per matching edge — callers that need to bound memory should scope the scan with prefixes or page at the service layer.

Returns false when the prefix index is not enabled, when ctx is cancelled, or when fn requested an early stop; true on a clean exhaustion of the matching set.

func (*GraphCache[S, T]) ScanEdgesByPrefixPage ¶ added in v0.15.0

func (c *GraphCache[S, T]) ScanEdgesByPrefixPage(
	ctx context.Context,
	tailPrefix, headPrefix, afterTail, afterHead string,
	limit int,
	fn func(tailProjected string, tail S, headProjected string, head S, weight float32, expiration time.Time) bool,
) (more, ok bool)

ScanEdgesByPrefixPage is the paged form of ScanEdgesByPrefix (#836): it resumes strictly after the (afterTail, afterHead) pair — seeking the tail radix to afterTail (inclusive, because that tail's remaining heads may still qualify) and, WITHIN the resume tail only, seeking heads strictly past afterHead — and buffers at most limit rows plus one sentinel (limit <= 0 means unbounded, i.e. exactly ScanEdgesByPrefix). A resumed page therefore costs O(depth + page) instead of O(every matching edge), and per-call buffering is bounded by the page size instead of the whole matching set.

more reports whether at least one further matching edge exists past the returned page; ok mirrors ScanEdgesByPrefix (false on disabled index, ctx cancellation, or fn early-stop). Locking/consistency semantics are unchanged: rows are collected under one c.mu.RLock, fn runs off-lock.

func (*GraphCache[S, T]) SearchIndexStats ¶ added in v0.9.0

func (c *GraphCache[S, T]) SearchIndexStats() (terms, docs int)

SearchIndexStats returns the current number of distinct terms and indexed documents in the optional search index. Both values are 0 when the search index is disabled. Safe for concurrent use; intended for Prometheus gauge sampling.

func (*GraphCache[S, T]) SearchVertices ¶

func (c *GraphCache[S, T]) SearchVertices(query string, limit int, keyPrefix string) []search.Result[S]

SearchVertices returns up to limit keys whose indexed content matches query, ranked most-relevant first by BM25. An empty or unanalyzable query, a disabled index, or limit <= 0 returns nil. A non-empty keyPrefix scopes the results to a namespace, keeping only keys whose projection (the same one the prefix index uses) starts with keyPrefix.

Consistency mirrors ScanByPrefix: a hit is returned only when the vertex is still live, so a vertex whose TTL has expired but which has not yet been flushed is skipped — the returned set matches what a matching sequence of GetVertex calls under the snapshot lock would surface. Because matching is the index's boolean OR over the query terms, limit is applied after the liveness and prefix filters so a full page of live, in-scope hits is returned whenever one exists.

func (*GraphCache[S, T]) SearchVerticesMatch ¶ added in v0.16.0

func (c *GraphCache[S, T]) SearchVerticesMatch(query string, limit int, keyPrefix string, opts search.MatchOptions, phrase bool) []search.Result[S]

SearchVerticesMatch is SearchVertices with explicit relevance options (#892): opts selects the match mode and prefix/fuzzy term expansion, and phrase requires the query's word terms to occur adjacently, in order. phrase takes precedence over opts.Mode — a phrase query is served by the index's phrase search. SearchVertices is exactly SearchVerticesMatch with the zero MatchOptions and phrase == false (the default OR-union). Liveness and prefix scoping are identical, and the bounded top-k selection still pushes them into the accept callback so a broad query never materialises its whole match set.

func (*GraphCache[S, T]) SetGCEdgeBudget ¶ added in v0.11.0

func (c *GraphCache[S, T]) SetGCEdgeBudget(n int)

SetGCEdgeBudget bounds how many tail buckets the GC edge sweep walks per Watch tick (#744). A positive n caps each tick at n tails, spreading a large O(E) sweep across multiple ticks to bound the c.mu.Lock pause; the sweep carries a cursor across ticks so every tail is still reclaimed within bounded time. n <= 0 (the default) restores the full single-tick sweep and clears any in-flight cursor. Safe for concurrent use; takes effect on the next tick.

func (*GraphCache[S, T]) SetGCHooks ¶

func (c *GraphCache[S, T]) SetGCHooks(onExpire func(kind string, n int), onGCDuration func(d time.Duration))

SetGCHooks installs optional observability callbacks invoked from Watch after every GC tick. Either argument may be nil. Hooks must not call back into the cache (re-entrant locking would deadlock). Safe for concurrent use.

func (*GraphCache[S, T]) SnapshotEdges ¶

func (c *GraphCache[S, T]) SnapshotEdges() []SnapshotEdge[S]

SnapshotEdges returns a materialised snapshot of every live edge in the cache, preserving the per-contribution weight decomposition. Taken under a READ lock since #843 (see SnapshotVertices); the returned slice is independent of the cache. Edges whose every contribution has decayed are skipped (they would otherwise show up as ghost entries with zero total weight).

Memory cost is O(E + sum of bucket sizes); same scope rationale as SnapshotVertices.

func (*GraphCache[S, T]) SnapshotGraph ¶ added in v0.8.0

func (c *GraphCache[S, T]) SnapshotGraph() GraphSnapshot[S, T]

SnapshotGraph returns a materialised whole-graph snapshot — every live vertex and edge — taken under a SINGLE continuous lock pass, so the vertex and edge sides reflect the same instant. Calling SnapshotVertices and SnapshotEdges separately locks twice and can observe a vertex/edge set that never co-existed; SnapshotGraph closes that window, which is what a whole-graph backup/restore needs.

Since #843 the pass holds c.mu as a READ lock: every mutator that can change the vertex or edge SETS takes c.mu.Lock, so set-level point-in-time consistency is identical to the historical write-lock pass — while concurrent readers keep serving. The one non-excluded writer is the lock-free hot-edge weight append (tryAddExistingEdgeContrib), which never held c.mu under the old write lock either: it cannot change the edge set, and per-bucket atomicity is provided by the weight's own mutex, so the race surface is unchanged.

The returned slices are independent of the cache and safe to iterate without further locking. Expired vertices and fully-decayed edges are skipped, identical to the single-kind methods. Memory cost is O(live vertices + live edges); like the single-kind snapshots it is intended for bounded, infrequent operations (backup, replication bootstrap), not hot read paths.

func (*GraphCache[S, T]) SnapshotVertices ¶

func (c *GraphCache[S, T]) SnapshotVertices() []SnapshotVertex[S, T]

SnapshotVertices returns a materialised snapshot of every live vertex in the cache. Since #843 the snapshot is taken under a READ lock: expired-but-unflushed entries are FILTERED (Range skips them) rather than physically flushed, so concurrent readers — point reads, scans, traversals — keep making progress while a backup or replication bootstrap materialises the graph. Physical reclamation of expired entries belongs solely to the GC tick. The returned slice is independent of the cache and safe to iterate without further locking.

Memory cost is O(N) in the live vertex count — the API is intended for replication bootstrap (#184), which is a bounded, infrequent operation. Hot read paths should keep using GetVertex.

func (*GraphCache[S, T]) TopVerticesByDegree ¶ added in v0.16.0

func (c *GraphCache[S, T]) TopVerticesByDegree(prefix string, k int, dir DegreeDirection, weighted bool) []DegreeEntry[S]

TopVerticesByDegree ranks the live vertices whose projected key starts with prefix by their degree in the requested direction and returns the top k in descending order of the ranking metric (WeightedDegree when weighted is true, else Degree). It answers the cold-start "which vertices under this namespace are most connected?" question without shipping the subgraph to the client (#900).

Live-visibility (#750): only live vertices are candidates, and an edge counts only when BOTH endpoints are live and the edge has not fully decayed to zero.

Consistency (#920): the OUT-only walk visits just the candidates' out-edges and runs entirely under the read lock, so it observes a point-in-time snapshot. IN/BOTH has no reverse (head->tails) index and must consider every edge bucket; to avoid holding the aggregate read lock for that O(E) pass — and stalling every writer for its duration — it collects the candidate-incident bucket references under the lock, releases it, and reads the weights afterwards. The IN/BOTH result is therefore a best-effort snapshot: an edge added or deleted while the weights are being read may be partially reflected. Like GetServerStatus counts these are advisory, not transactional.

Selection uses a size-k bounded min-heap (pq.SortableMap.Top, the #127 pattern), so peak memory over the ranking metric is O(k) rather than O(candidates). Accumulation working memory is O(candidates) — one value-typed accumulator per candidate, no per-candidate heap allocation — plus, for IN/BOTH, O(candidate-incident edges) transient bucket references held across the unlocked read. k <= 0 returns nil. Candidates with a zero degree remain eligible, so they surface only when fewer than k vertices under the prefix carry any live incident edge. Ties at the k-th boundary are broken arbitrarily; the returned slice is otherwise sorted by the ranking metric descending (callers that need a total order should apply a key tie-break).

The prefix index must be enabled (EnablePrefixIndex); otherwise the method returns nil.

func (*GraphCache[S, T]) VertexCount ¶

func (c *GraphCache[S, T]) VertexCount() int

VertexCount returns the live vertex count under an RLock. Intended for Prometheus gauges that sample the cache periodically.

func (*GraphCache[S, T]) VertexHLCCount ¶ added in v0.9.0

func (c *GraphCache[S, T]) VertexHLCCount() int

VertexHLCCount returns the number of entries in the per-key LWW watermark map (vertexHLC). Under a healthy workload this equals the number of distinct vertex keys ever touched by the replication apply path and should track the live vertex count after a full GC sweep. A value that grows without bound across GC ticks is a leak signal (see issue #700). Returns 0 when the map has never been initialised (no replicated writes have arrived yet).

func (*GraphCache[S, T]) VertexHLCHighWater ¶ added in v0.10.0

func (c *GraphCache[S, T]) VertexHLCHighWater() int

VertexHLCHighWater returns the largest number of vertexHLC entries ever observed at the start of a GC sweep — the per-cycle peak before stale watermarks are drained. Unlike VertexHLCCount (which reports the current, post-sweep len and therefore reads low right after a drain), this value is monotonic non-decreasing and records the all-time churn peak. It used to also proxy the map's retained bucket-array heap (Go never shrinks a map after delete), but sweepStaleVertexHLCLocked now reallocates the map after a large drain, so a high VertexHLCHighWater no longer implies pinned heap — it is a historical confirm-the-phenomenon signal for the ttl_churn leak gate (#700/#719/#727). Returns 0 when no sweep has run yet. Safe for concurrent use; intended for Prometheus gauge sampling.

func (*GraphCache[S, T]) Watch ¶

func (c *GraphCache[S, T]) Watch(ctx context.Context, interval time.Duration)