Documentation
¶
Overview ¶
Package label provides a Roaring-bitmap-backed inverted index from label identifiers to the NodeIDs that carry them.
The index is the substrate for label-filtered queries such as "find every node with label Person and label Active": each label is represented by a 64-bit Roaring bitmap, and compound queries are answered via bitmap intersection / union, which Roaring implements with run-length and array-bitmap hybrids.
Index is safe for concurrent use; Index documents the full contract, including the lock order every code path in this package obeys.
Scope, and why lpg uses the unscoped constructor ¶
Index.Scope is consulted in exactly one place — Index.Apply — and Apply runs only through the index.Manager fan-out. No Index is ever registered with a Manager in this module: index.Manager.CreateIndex is the sole writer of the subscriber registry, and every production call site registers a btree or hash index. The only two Index values in the module are lpg's nodeIdx and edgeIdx, which lpg maintains by calling Add and Remove directly.
So lpg builds BOTH with NewIndex, the edge index included, because on a directly-driven index the scope field is never read. NewNodeIndex and NewEdgeIndex exist for a caller that does register an Index as a index.Subscriber; there is no such caller today.
A caller that becomes one should know that the two scopes are not equally well served. index.OpAddEdgeLabel is constructed and delivered in production, but index.OpRemoveEdgeLabel is constructed nowhere, so a registered ScopeEdge index would take every edge-label addition and never a removal, accumulating postings for labels that no longer apply. ScopeNode has both halves of its event stream; ScopeEdge, today, has one.
The scoped surface, the range operations and the serialized form are exercised by the `label-index-scoped` simulator scenario (internal/sim/label_index_scoped.go).
Index ¶
- type Index
- func (i *Index) Add(label uint32, node graph.NodeID)
- func (i *Index) AddRange(label uint32, fromNode, toNode graph.NodeID)
- func (i *Index) Apply(c index.Change)
- func (i *Index) BitmapShared(label uint32) *roaring64.Bitmap
- func (i *Index) Count(label uint32) uint64
- func (i *Index) Deserialize(r io.Reader) error
- func (i *Index) Has(label uint32, node graph.NodeID) bool
- func (i *Index) Intersect(labels ...uint32) *roaring64.Bitmap
- func (i *Index) IntersectCardinality(labels ...uint32) (uint64, bool)
- func (*Index) Kind() string
- func (i *Index) Remove(label uint32, node graph.NodeID)
- func (i *Index) RemoveRange(label uint32, fromNode, toNode graph.NodeID)
- func (i *Index) Scan(label uint32) []graph.NodeID
- func (i *Index) Scope() Scope
- func (i *Index) Serialize(w io.Writer) error
- func (i *Index) Union(labels ...uint32) *roaring64.Bitmap
- type Scope
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Index ¶
type Index struct {
// contains filtered or unexported fields
}
Index maps label identifiers (uint32) to the set of NodeIDs that carry them. Different LabelID namespaces (vertices, edges) should use distinct Index instances.
Each label's node set is held as an index.NodeSet: a sparse label carried by one or a handful of nodes stays in the inline small-set tier (no per-label roaring overhead), while a dense label — one built via Index.AddRange over a contiguous NodeID band, or grown past the small-set threshold — is a roaring64.Bitmap with its run-container optimality intact. Promotion to the bitmap tier is one-way, so a dense label can never be mis-tiered as a small set (sprint 206, #1585).
Concurrency ¶
Index is safe for concurrent use by any number of goroutines, for every exported operation, with no external synchronisation.
There are two lock levels. The SPINE lock (Index.mu) guards the label→entry map's structure: it is taken shared to look a label up and exclusively to create or drop one. Each label's [entry] then carries its OWN lock guarding that label's node set. So two writers touching different labels never contend, and a reader of one label never blocks a writer of another. Before rmp #2685 a single index-wide RWMutex guarded everything, and it held 98.66% of all mutex delay on a mixed read/write workload at 8 goroutines.
Lock order — SPINE before ENTRY, never the reverse ¶
A goroutine may acquire Index.mu and then an entry.mu. It must NEVER acquire Index.mu while holding any entry.mu. Every path in this file obeys it:
- lookup, and therefore every read and every mutation of an existing label, releases Index.mu before touching entry.mu at all.
- mutate's creation path, reap, and Deserialize take Index.mu first and entry.mu second.
- mutate detects a stale entry through the entry's own dead flag rather than by re-reading the spine, so it never needs the spine while holding an entry lock. See [entry.dead] for the deadlock this avoids.
Two entry locks are held at once in exactly one place, Index.IntersectCardinality, and it acquires them in ASCENDING LABEL ID order. An entry is reachable under exactly one label id for its whole life, so label id is a total order over the entries and the wait-for graph cannot contain a cycle.
What the per-label locks cost: multi-label reads are no longer one image ¶
Index.Intersect, Index.Union, Index.IntersectCardinality and Index.Serialize sample each label under that label's own lock, so their answer is assembled from per-label images taken at slightly different instants rather than from one image of the whole index. A single index-wide image is not obtainable from a design whose writers do not take an index-wide lock; that is precisely the trade this geometry makes.
This is a property of the raw index only. It was never a transactional guarantee: even under the old index-wide lock, Add(L1, n) and Add(L2, n) were two separate critical sections, so a concurrent Intersect(L1, L2) could already land between the two halves of one logical write. Snapshot-correct answers come from the MVCC layer above — graph/lpg's LabelBitmapAsOf and LabelsBitmapAsOf re-check every suspect node against the versioned label bag and existence record — not from the atomicity of a single index read.
Example ¶
ExampleIndex shows membership queries on the label bitmap index: add NodeIDs under a label, test single-node membership with Has, count the carriers, and Scan the full member set in ascending NodeID order.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/label"
)
// Interned label identifiers used by the examples below. A real graph
// obtains these from its lpg.LabelID registry; here they are constants.
const labelPerson = uint32(1)
func main() {
idx := label.NewNodeIndex()
idx.Add(labelPerson, graph.NodeID(1))
idx.Add(labelPerson, graph.NodeID(2))
idx.Add(labelPerson, graph.NodeID(3))
fmt.Println("node 2 is Person:", idx.Has(labelPerson, graph.NodeID(2)))
fmt.Println("node 9 is Person:", idx.Has(labelPerson, graph.NodeID(9)))
fmt.Println("Person count:", idx.Count(labelPerson))
fmt.Println("Person members:", idx.Scan(labelPerson))
}
Output: node 2 is Person: true node 9 is Person: false Person count: 3 Person members: [1 2 3]
func NewEdgeIndex ¶
func NewEdgeIndex() *Index
NewEdgeIndex returns an empty index that listens for edge-label changes when registered with a index.Manager.
It has no caller in this module, and the package documentation records why, together with the caveat that index.OpRemoveEdgeLabel is not currently emitted anywhere in production.
The returned Index is safe for concurrent use.
func NewIndex ¶
func NewIndex() *Index
NewIndex returns an empty index in ScopeNode — equivalent to NewNodeIndex. Existing callers that pre-date the scope field keep this constructor as the default.
The returned Index is safe for concurrent use.
func NewNodeIndex ¶
func NewNodeIndex() *Index
NewNodeIndex returns an empty index that listens for node-label changes when registered with a index.Manager.
The returned Index is safe for concurrent use.
func (*Index) Add ¶
Add records that node carries label.
Safe for concurrent use. It contends only with other operations on the SAME label, plus the brief shared spine lookup.
func (*Index) AddRange ¶
AddRange records that all nodes in [fromNode, toNode] (inclusive) carry label. It uses roaring64.Bitmap.AddRange which represents dense ranges in O(1) space, making bulk ingestion of contiguous NodeID bands efficient. An interval naming no ids leaves no entry behind, mirroring RemoveRange.
Safe for concurrent use.
func (*Index) Apply ¶
Apply dispatches the change to the underlying bitmaps when the change kind matches the index's Scope. Other ops are ignored (the manager fans every change to every subscriber; per-subscriber filtering is the subscriber's responsibility).
Safe for concurrent use; it delegates to Add and Remove.
func (*Index) BitmapShared ¶ added in v0.15.0
BitmapShared returns the NodeIDs carrying label as a bitmap the caller MUST NOT MUTATE, and MUST NOT assume is its own.
It is the single-label read that Index.Intersect pays a clone for. Intersect hands back a caller-owned bitmap, so it copies the live one on every call; this returns a SHARED IMMUTABLE IMAGE instead, built once and reused by every reader until the label is next written.
The contract, stated as sharply as it can be ¶
Mutating the result corrupts what every other concurrent reader of this label sees, silently and without a race report, because the object is shared BY DESIGN and no lock guards it. A caller that needs to mutate must Clone first, or call Index.Intersect, which never shares.
Reading it, by contrast, needs no lock and no coordination at all, for as long as the caller likes: the image is written exactly once, when it is built, and is never written again — a later write to the label REPLACES the entry's image rather than editing it ([Index.mutate] drops it; see [entry.image]).
What it costs, and what it stops costing ¶
One image per label is retained until the label is next written, instead of one clone per read that lives until the reader drops it. Under concurrency that is fewer live bytes, not more: k simultaneous scans of one label used to hold k clones and now share one image.
The cold path — the first read of a label, and the first after each write — still builds an image, so a workload that alternates read and write on the SAME label pays what Intersect paid. A read-mostly label pays it once.
It is an image of ONE INSTANT, and the caller may rely on that ¶
The image is fixed at the moment this call observes the entry, and nothing moves it afterwards. A caller that needs its answer pinned between two other observations — graph/lpg's snapshot correction samples the churn set on both sides of exactly this instant — gets the same guarantee the clone gave it, and may Clone the image later without the copy drifting: the object cannot have changed in between.
An unknown label yields a fresh empty bitmap, matching Index.Intersect.
Safe for concurrent use.
func (*Index) Count ¶
Count returns the number of NodeIDs that carry label.
Safe for concurrent use.
func (*Index) Deserialize ¶
Deserialize replaces the receiver's state with the contents of r. On any structural problem, truncated payload, or CRC mismatch the function returns a wrapped index.ErrIndexCorrupted and the receiver is restored to the pre-call state.
The implementation reads the whole payload into a buffer, validates the trailing CRC32C against the prefix, then re-parses the prefix to populate the bitmaps. This costs one extra pass over the data but keeps the corruption-detection contract simple and lets the reader reject malformed inputs before any state mutation.
Safe for concurrent use. The whole spine is swapped under the SPINE write lock, and every displaced entry is marked dead under its own lock first (lock order SPINE then ENTRY, one entry at a time), so a mutation that is in flight against a displaced entry retries against the new spine instead of writing into a detached one.
func (*Index) Intersect ¶
Intersect returns a fresh Roaring bitmap containing the NodeIDs that carry every supplied label. Calling with no labels returns the empty bitmap.
Safe for concurrent use. Each label is sampled under its own entry read lock, one at a time; see Index for what that means for the consistency of a multi-label answer.
Example ¶
ExampleIndex_Intersect shows compound label queries via bitmap set operations. Intersect answers "every node carrying all of these labels"; Union answers "every node carrying any of them".
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/label"
)
// Interned label identifiers used by the examples below. A real graph
// obtains these from its lpg.LabelID registry; here they are constants.
const (
labelPerson = uint32(1)
labelActive = uint32(2)
)
func main() {
idx := label.NewNodeIndex()
for _, n := range []graph.NodeID{1, 2, 3} {
idx.Add(labelPerson, n)
}
for _, n := range []graph.NodeID{2, 3, 4} {
idx.Add(labelActive, n)
}
both := idx.Intersect(labelPerson, labelActive)
either := idx.Union(labelPerson, labelActive)
fmt.Println("Person AND Active:", both.ToArray())
fmt.Println("Person OR Active:", either.ToArray())
}
Output: Person AND Active: [2 3] Person OR Active: [1 2 3 4]
func (*Index) IntersectCardinality ¶ added in v0.11.0
IntersectCardinality returns the EXACT number of NodeIDs carrying every supplied label, without materialising the intersection and — in the common case — without allocating at all.
It exists because the size of an intersection is a planner DECISION input, and paying for the answer defeats the purpose of asking. [Intersect] must clone the first label's live bitmap to hand the caller an owned result; a planner that only wants the count would pay that clone for nothing. Measured: gating a multi-label plan through Intersect cost +85.8% B/op on a query the gate then DECLINED, because two bitmaps were materialised purely to be counted.
roaring64.AndCardinality walks the two container arrays by key with skips and accumulates per-container intersection counts, touching no allocation. For the pairwise case this therefore runs directly against the LIVE bitmaps under the two labels' entry read locks. Three or more labels have no k-way cardinality primitive, so the pairwise count over the first two is returned; that is an UPPER bound on the k-way result (|L₁ ∩ … ∩ L_k| ≤ |L₁ ∩ L₂|), which is what a conservative gate needs — pass the two smallest labels to make it tight.
A label absent from the index makes the intersection empty, so the result is 0. Fewer than two labels reports (0, false): there is no intersection to size, and the caller must not read the count as authoritative.
Safe for concurrent use. This is the only operation in the package that holds two entry locks at once; it takes them in ascending LABEL ID order, which Index explains is a total order over entries and therefore deadlock-free. The two labels are sampled under their own locks rather than under one index-wide lock, so the answer is not a single consistent image of the whole index; Index documents why that was never a transactional guarantee.
func (*Index) Kind ¶
Kind returns "label" — satisfies index.Subscriber.
Safe for concurrent use; it takes no lock and reads no state.
func (*Index) Remove ¶
Remove records that node no longer carries label. No-op if absent. A label whose last member is removed loses its entry entirely.
Safe for concurrent use.
func (*Index) RemoveRange ¶
RemoveRange records that all nodes in [fromNode, toNode] (inclusive) no longer carry label. Emptied labels lose their entry so the map does not grow unboundedly after bulk-remove operations.
Safe for concurrent use.
func (*Index) Scan ¶
Scan returns the sorted slice of NodeIDs that carry label. Returns nil when label has no entries.
Safe for concurrent use. The result is a fresh slice the caller owns.
func (*Index) Scope ¶
Scope reports which label-event kind the index observes via Index.Apply. It has no effect on an index that is driven by direct Add and Remove calls rather than registered with a index.Manager, which is every index in this module; see the package documentation.
The scope is fixed at construction, so Scope is safe for concurrent use and takes no lock.
func (*Index) Serialize ¶
Serialize writes the index's per-label bitmaps to w in the format documented in docs/persistence.md. The on-disk layout is:
uint32 magic ('SLBI')
uint32 formatVersion
uint32 labelCount
repeat labelCount times:
uint32 labelID
uint64 bitmapLen
[bitmapLen]byte bitmap (Roaring native binary format)
uint32 crc32c (covers every byte above, little-endian)
Safe for concurrent use. Serialize holds the SPINE read lock for the whole emission, which is required for the format itself: labelCount is written up front and must match the number of entries that follow, so no label may be created or reaped mid-emission. Each label's bytes are then read under that label's own entry read lock. A concurrent writer touching an EXISTING label can therefore land between two entries, so the image is per-label consistent rather than index-wide consistent; see Index. Callers needing a whole-index point-in-time image must quiesce writers themselves.
The returned error wraps the underlying I/O failure verbatim; the caller treats short writes the same as any other I/O error.
type Scope ¶
type Scope uint8
Scope tags whether the index observes node-label or edge-label changes when registered with index.Manager. The two scopes share a common bitmap shape so the on-disk format is identical.
Scope is an immutable value type and is safe for concurrent use.
const ( // ScopeNode listens for [index.OpAddNodeLabel] / [index.OpRemoveNodeLabel] // when the index is registered with a [index.Manager]. It is the // default; callers building an unregistered index can ignore the // scope entirely. ScopeNode Scope = iota + 1 // ScopeEdge listens for [index.OpAddEdgeLabel] / [index.OpRemoveEdgeLabel]. // Edge bitmaps are keyed by the source NodeID, mirroring the LPG // convention exposed by [lpg.Graph.EdgeIndex]. ScopeEdge )
Scope values for NewNodeIndex / NewEdgeIndex.
Source Files