Documentation
¶
Overview ¶
Package hash provides a sharded hash index from arbitrary comparable property values to the set of NodeIDs that carry them, represented as a 64-bit Roaring bitmap.
The structure answers exact-match property predicates (for example "every node where email == 'x@y.com'") in O(1) average time. For range predicates use the B+ tree index in package github.com/FlavioCFOliveira/GoGraph/graph/index/btree (Sprint 2, T19).
Index is safe for concurrent use by any number of goroutines with no external synchronisation; Index documents the full contract, including the lock geometry and the lock order every code path in this package obeys. Every READ path is lock-free: a shard's value-to-entry table is an open-addressed array of atomically published slots, so a reader only issues loads. Keys are distributed over the shards by maphash.Comparable of the key itself, so a shard holds an arbitrary subset of the key space rather than a graph.NodeID band; the same hash also drives the probe within the shard, so a lookup hashes the key once.
Index ¶
- type Binding
- type Index
- func (i *Index[V]) Apply(c index.Change)
- func (i *Index[V]) ApplyResolved(c index.Change, current any, eligible bool)
- func (i *Index[V]) BoundNode() (label, property string, ok bool)
- func (i *Index[V]) Cardinality(value V) uint64
- func (i *Index[V]) Contains(value V, node graph.NodeID) bool
- func (i *Index[V]) Delete(value V, node graph.NodeID)
- func (i *Index[V]) Deserialize(r io.Reader) error
- func (i *Index[V]) DistinctValues() uint64
- func (i *Index[V]) Insert(value V, node graph.NodeID)
- func (*Index[V]) Kind() string
- func (i *Index[V]) Lookup(value V) *roaring64.Bitmap
- func (i *Index[V]) LookupAppend(value V, dst []uint64) []uint64
- func (i *Index[V]) Serialize(w io.Writer) error
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Binding ¶ added in v0.3.0
type Binding[V comparable] struct { // Project converts a Change.OldValue / Change.NewValue payload to // the index key type. ok is false when the payload is absent or // not indexable (wrong kind), in which case the event is skipped // for that direction. Project func(v any) (V, bool) // Eligible reports whether the node should currently be present in // the index: it must be live (not deleted) and carry the bound // label, evaluated against the graph's final state. Eligible func(node graph.NodeID) bool // CurrentValue returns the node's current value for the bound // property, projected to the key type. ok is false when the node // is not live, lacks the property, or the value is not indexable. // It is consulted on label add/remove events, which carry no // property payload. CurrentValue func(node graph.NodeID) (V, bool) // Label and Property are the source names behind PropertyID and // LabelID. They let a query planner match the index against a // (label, property) predicate without access to the registries. Label, Property string // PropertyID is the interned property-key identifier this index // covers. Property changes whose Change.Property differs are // ignored. PropertyID uint32 // LabelID is the interned label identifier this index is scoped // to. Label changes whose Change.Label differs are ignored. Note // that interned IDs start at zero, so this field alone cannot mark // an unscoped binding; bindings are always label-scoped. LabelID uint32 }
Binding ties an Index to a single (label, property) pair of a live node graph. A bound index (see NewBound) maintains itself from the index.Manager change fan-out: property writes insert/delete typed keys, and label add/remove events attach/detach a node's current value. An unbound index (see New) ignores the fan-out entirely and is maintained by explicit Index.Insert / Index.Delete calls.
The identifier fields carry interned IDs from the owning graph's registries; the callbacks close over the graph so this package stays free of a dependency on any concrete graph implementation. Because changes are fanned out at commit time — after the transaction's mutations were applied eagerly to the graph — the callbacks observe the transaction's FINAL state, which is exactly the state the index must converge to.
type Index ¶
type Index[V comparable] struct { // contains filtered or unexported fields }
Index maps property values of type V to the NodeIDs that carry them.
Concurrency ¶
Index is safe for concurrent use by any number of goroutines, for every exported operation, with no external synchronisation.
There is ONE lock level and two lock-free levels.
The SPINE — a shard's value→entry table — is read with NO LOCK AT ALL since rmp #2699: it is an open-addressed table of atomically published slots, so a reader only issues loads (see [hashShard]). Its WRITER mutex, hashShard.w, is taken solely to create, revive or tombstone a key, and readers never touch it. Each value's [entry] then carries its OWN lock, which serialises WRITERS of that value against each other. So two writers touching different values never contend, and a reader never takes a lock any writer of another value holds.
Above that, each entry publishes its posting list WITHOUT a lock. A reader starts from one atomic word, [entry.meta], which carries the tier tag and — on the two tiers a wide equality index is mostly made of, an EMPTY posting list and a SINGLETON one — the entire image. Those reads finish there: no pointer to chase, no heap object to have been allocated, no lock. A wider list is an immutable [snapshot] behind one atomic pointer, read with NO LOCK AT ALL while it is immutable; only a bitmap-tier snapshot, whose bitmap a writer mutates in place, sends the reader through the entry read lock. The meta constants define the encoding, [snapshot] states the invariant that makes the lock-free read safe, and the five states a lock-free reader can observe — including the demotion window — are enumerated on [entry].
What the geometry costs in MEMORY, and what round three gave back ¶
Retained heap per distinct indexed value, measured as HeapAlloc after two forced collections with the index live, against the pre-#2692 baseline:
tier BASE round 2 round 3 round 3 vs BASE singleton, 200k keys 35.06 B 95.76 B 71.76 B +104.7% small, 20k x 4 ids 109.80 B 167.20 B 167.20 B + 52.3% bitmap, 2k x 40 ids 413.50 B 478.00 B 478.00 B + 15.6%
Medians of 5 interleaved rounds per arm, the three arms running byte- identical benchmark code; the spread within an arm was at most 0.01 B/key, so these figures are not close calls.
Round two's bill was a near-constant +58 to +65 B per key — an *entry (48 B in its size class) plus a *snapshot (24 B) where the baseline held an index.NodeSet by value inside the shard map. It looks catastrophic only on singletons, because their payload is the smallest, and singletons are what a wide index is made of: at 10 000 000 distinct values the three arms are 351 MB, 958 MB and 718 MB. Round three takes the snapshot off the empty and singleton tiers, which is where the bill actually lands, and gives back exactly its 24 bytes; it leaves the wider tiers byte for byte as round two left them, because their images still need a heap object and a lock they still take.
BenchmarkIndex_DistinctKeyFootprint is the measurement, per tier. It is per TIER because an aggregate hid this: a constant per-key overhead is a small fraction of a wide posting list and a catastrophe for a singleton, so an average belongs to no tier and buries the only one that matters.
And what it cost in THROUGHPUT: nothing, measured twice ¶
Round three was expected to be throughput-neutral, because the tier each key reaches decides which path it takes (see [entry.mu]) and no key changed tier. Measured against round two, interleaved, on a host at loadavg ~2 of 10 cores:
sweep 1 (n=8) sweep 2 (n=6) SeekSingleton/Append -3.71% p=0.000 -4.32% p=0.002 SeekSingleton/Bitmap -1.61% p=0.009 -1.78% p=0.009 CardinalityInlineTier/Spread -5.19% p=0.000 -5.38% p=0.002 CardinalityInlineTier/Hot ~ p=0.555 ~ p=0.240 LookupHot +1.26% p=0.000 ~ p=0.370
The three improvements are the inline tags earning their keep: a singleton read now resolves out of one word in one cache line instead of chasing a pointer into a second, which shows up most on the cold-line Spread shape.
LookupHot is reported as NO REPRODUCIBLE CHANGE, not as +1.26%. It reads a ~488-id bitmap-tier key, so it pays one extra atomic load — of a word in the same cache line as the pointer it then loads — and the first sweep called that 0.33 ns significant while the second, on code identical in codegen, could not distinguish it at all. Two sweeps that disagree at p=0.000 and p=0.370 mean the effect is inside the run-to-run variation, and a single sweep's p-value did not capture it. Allocation counts are unchanged on every read path.
Before rmp #2692 a single RWMutex per shard guarded both the map and every set inside it. Measured on the `index-hash-rw` contention workload (90% Index.Cardinality / 10% Index.Insert, 100 000 int64 keys) at 1024 goroutines: Index.Insert held 98.17% of all mutex delay, readers PARKED on the shard RWMutex for 40.7% of total block delay, and the read lock cost ~6.5x more CPU than the read it protected (RLock 4.52 s + RUnlock 0.97 s against 0.85 s of actual work). Roughly 75% of all CPU in the run was futex park/unpark. A ceiling probe put the available win at 1.26x at concurrency 1 rising to 7.90x at 1024.
Round two left the shard RWMutex in place for the map probe alone, and rmp #2699 measured what that cost: at 8 goroutines sync/atomic.(*Int32).Add was 24.50% of all CPU, with pprof -peek attributing 100% of it to RLock, RUnlock and Unlock, against 2.8% for the same word at ONE goroutine — so the other ~22 points were cache-coherence traffic and nothing else. Round three replaced the map with the open-addressed table described on [hashShard], and the read paths now take no lock at all.
Lock order — SHARD WRITER before ENTRY, never the reverse ¶
A goroutine may acquire a shard's w and then an entry.mu. It must NEVER acquire a shard's w while holding any entry.mu. Every path in this file obeys it:
- Index.Lookup, Index.LookupAppend, Index.Cardinality and Index.Contains take NO shard lock at all, so they cannot participate in an inversion. They touch entry.mu only when the value's snapshot is a shared bitmap-tier one.
- Index.Insert's creation path, [hashShard.reap] and Index.Deserialize take the shard writer lock first and entry.mu second.
- Index.Insert and Index.Delete detect a stale entry through the entry's own dead flag rather than by re-reading the shard table, so they never need the shard writer lock while holding an entry lock. See [entry.dead] for the deadlock that avoids.
No operation in this package holds two entry locks at once, and no operation holds two shard writer locks at once.
Removing the reader side of the spine STRICTLY WEAKENS the deadlock surface: a lock that is never taken cannot be taken out of order, so the one-way order above now constrains writers alone.
What the per-entry locks cost: a multi-value read is no longer one image ¶
Index.DistinctValues answers from the per-shard non-empty counters, and Index.Serialize walks each shard's published table taking, for a bitmap-tier value, that entry's own lock. Their answer is therefore assembled from images taken at slightly different instants rather than from one image of the whole index. That was already true across shards before rmp #2692 — writers have never taken an index-wide lock — and it is why Index.Deserialize is confined to engine construction by its caller; see cypher/index_hydration.go.
Since rmp #2699 removed the spine read lock, Serialize's image is assembled per SLOT rather than per SHARD: a key created part-way through one shard's walk may or may not appear, where before the walk excluded creations in that shard for its duration. See Index.Serialize for why that stays inside the contract the method already published.
A Index.Delete that empties a value's set is now TWO critical sections — the removal under the entry lock, then the reap under the shard writer lock — where it used to be one. A concurrent reader can therefore observe the value present in the table with an empty set. Index.DistinctValues is defined not to count such an entry, because a caller depends on its zero (cypher.hashIndexKind, rmp #1983); every other read path answers the same for an empty entry as for an absent one.
Example ¶
ExampleIndex shows a hash index answering an exact-match property predicate: insert (value, NodeID) pairs keyed by a string property, then read back the NodeID set carrying one exact value.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/hash"
)
func main() {
// An index over a string "email domain" property.
idx := hash.New[string]()
idx.Insert("example.com", graph.NodeID(1))
idx.Insert("example.org", graph.NodeID(2))
idx.Insert("example.com", graph.NodeID(3))
// Lookup answers "every node where domain == example.com".
bm := idx.Lookup("example.com")
fmt.Println("example.com nodes:", bm.ToArray())
fmt.Println("example.com cardinality:", idx.Cardinality("example.com"))
fmt.Println("distinct domains:", idx.DistinctValues())
}
Output: example.com nodes: [1 3] example.com cardinality: 2 distinct domains: 2
func New ¶
func New[V comparable]() *Index[V]
New returns an empty hash index.
The returned Index is safe for concurrent use.
func NewBound ¶ added in v0.3.0
func NewBound[V comparable](b Binding[V]) (*Index[V], error)
NewBound returns an empty hash index bound to b. Unlike New, the returned index has a functional Index.Apply: it subscribes to the node property and label changes selected by b and keeps itself consistent with the graph. Returns an error when b is missing its Label, Property, or any of the three callbacks.
func (*Index[V]) Apply ¶
Apply maintains a bound index (see NewBound) from the index.Manager change fan-out; it is a no-op for an unbound index (see New), which cannot reliably interpret arbitrary index.Change values without the caller-supplied binding (property key + value-type coercion).
For a bound index the rules are, per change:
- SetNodeProperty on the bound property: the old value (when present and projectable) is deleted unconditionally, and the new value is inserted when the node is eligible in the graph's final state. The unconditional old-value delete is what clears a stale entry even when a label removal in the same batch is replayed before the property change.
- DelNodeProperty on the bound property: the old value is deleted.
- Add/RemoveNodeLabel on the bound label: the node's CURRENT property value is inserted / deleted. Because changes are applied at commit time the current value is the transaction's final value, so an interleaved property change in the same batch converges to the same final state regardless of replay order.
Apply is idempotent (bitmap add/remove) and safe for concurrent use with readers. Edge changes and changes for other properties/labels are ignored.
What makes CONCURRENT Apply calls safe, restated (rmp #2345) ¶
This used to say "writers are serialised upstream by the engine's single-writer transaction contract". THAT IS FALSE since rmp #2320: commitUnderBarrier runs under a SHARED hold, so two transactions flush their index buffers concurrently and two Apply calls can interleave.
It is nonetheless sound, and the reason is worth stating because it is not the one that was written down. Each mutation is made under the target value's own entry lock (Index.Insert, Index.Delete), so no individual add or remove can tear. Since rmp #2692 that lock is per VALUE rather than per shard, which narrows what two concurrent Apply calls contend on but changes nothing about the tearing argument: a single add or remove is still one critical section. What serialisation would additionally buy is atomicity of the DELETE-then-INSERT pair in the OpSetNodeProperty arm — and the only interleaving that could strand a stale entry is two transactions writing the SAME node's bound property, which the substrate REFUSES: graph/lpg's property write path takes a write-write conflict check against the node's version-chain head (graph/lpg/property.go), so one of the two aborts and never reaches its Apply at all.
So the ordering guarantee comes from conflict detection on the object, not from exclusion on the writers. If that check is ever narrowed, this comment is the one to revisit.
On recovery from a corrupted snapshot, the index is left empty; callers re-populate via Index.Insert from the live LPG.
func (*Index[V]) ApplyResolved ¶ added in v0.14.1
ApplyResolved applies a change RECORDED DURING THIS INDEX'S BUILD, taking the node state from the recording instead of reading it back off the graph — index.ResolvedApplier. It satisfies that interface, and carries the same idempotence and concurrency properties as Index.Apply, whose rules it shares verbatim through [Index.applyBound].
current is the node's raw property value as of the recording; it is projected through the binding's own Project, so exactly the values Apply would index are indexed here. eligible is the recorded eligibility verdict.
A no-op for an unbound index, for the same reason Index.Apply is.
func (*Index[V]) BoundNode ¶ added in v0.3.0
BoundNode returns the (label, property) pair this index is bound to, with ok reporting whether the index is bound at all. Query planners use it to decide whether the index may serve a predicate: a bound index covers exactly its (label, property) pair, while an unbound index carries no coverage metadata.
func (*Index[V]) Cardinality ¶
Cardinality returns the number of NodeIDs associated with value. It is exposed for query planners to choose between index lookup and full-scan plans.
Safe for concurrent use, and this is the read the spine geometry exists for. Round two (rmp #2692) stopped a concurrent Index.Insert on any OTHER value in the same shard from parking this caller; round three (rmp #2699) removed the shard lock from this path altogether, so the probe issues loads only and generates no cache-coherence traffic. See [hashShard].
func (*Index[V]) Contains ¶
Contains reports whether node is in the set associated with value. Faster than Lookup when only existence matters.
Safe for concurrent use, and it takes NO SHARD LOCK: the spine probe is lock-free (rmp #2699), so this read blocks no writer of any value at all, up to the bitmap-tier entry lock below.
Example ¶
ExampleIndex_Contains shows the point-membership query: Contains reports whether one specific NodeID carries a given value, without materialising the whole NodeID set.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/hash"
)
func main() {
idx := hash.New[int]()
idx.Insert(404, graph.NodeID(7))
fmt.Println("node 7 has 404:", idx.Contains(404, graph.NodeID(7)))
fmt.Println("node 8 has 404:", idx.Contains(404, graph.NodeID(8)))
// Delete removes one membership; the value disappears once its last
// NodeID is gone.
idx.Delete(404, graph.NodeID(7))
fmt.Println("node 7 has 404 after delete:", idx.Contains(404, graph.NodeID(7)))
}
Output: node 7 has 404: true node 8 has 404: false node 7 has 404 after delete: false
func (*Index[V]) Delete ¶
Delete removes node from the set associated with value. No-op if absent or if value is a NaN (see Index.Insert for the rationale).
Removing the LAST NodeID under a value drops the value's key entirely, so a completed Delete leaves Index.DistinctValues and Index.Serialize with no trace of it. The removal and the key drop are two critical sections rather than one; see Index for what a concurrent reader can observe in between.
Safe for concurrent use.
func (*Index[V]) Deserialize ¶
Deserialize replaces the receiver's state with the contents of r. Returns index.ErrIndexCorrupted on structural or CRC errors and index.ErrIndexValueTypeUnsupported when V cannot be decoded.
Concurrency: shard-by-shard, deliberately NOT atomic across shards ¶
The replacement is applied one shard at a time under that shard's write lock, so a concurrent reader can observe a half-replaced index. That is a documented property this package's caller DEPENDS ON, not an oversight: cypher confines every hydration to engine construction, before the index.Manager the planner reads is published to any other goroutine, and panics on a later attempt rather than degrading silently (cypher/index_hydration.go, errHydrationAfterPublish). Making this atomic across shards would make that comment and its guard wrong; making it less atomic would break the per-shard consistency each reader does rely on.
Within a shard the swap is safe against an in-flight mutator: every displaced entry is marked dead under its OWN lock, while the shard writer lock is held (the permitted SHARD-WRITER-then-ENTRY order), so a mutator parked on a displaced entry learns it is stale and retries against the new map instead of writing into an entry nothing will ever read again. Marking every displaced entry also drains those in-flight mutations before the non-empty counter is restated, which is what makes the restated count exact.
index deserialize: header + per-entry decode + per-step bounds checks
func (*Index[V]) DistinctValues ¶
DistinctValues returns the number of distinct values currently indexed — that is, the number of keys whose NodeID set is NON-EMPTY. Exposed for cardinality estimation by the query planner.
Why non-empty rather than "keys in the table" ¶
Index.Delete removes the last NodeID under the entry lock and drops the key under the shard writer lock, in that order, so a key can transiently be present with an empty set (see Index). This method must not count it: cypher.hashIndexKind reads DistinctValues() == 0 as the authoritative "this string hash index holds no data" test, and a false non-zero would pin a parameter compared against that property to String and reject an integer parameter with a spurious ParamTypeError — rmp #1983, the regression that guard exists to prevent. So the count is maintained per shard on the empty <-> non-empty transition (see hashShard.nonEmpty) rather than read off map length.
It follows that a payload deserialised with a zero-length posting list — which Index.Serialize never writes, so only a crafted or corrupt image can carry one — installs a key this method does not count.
Cost and consistency ¶
It sums shardCount atomic loads: O(shardCount), independent of how many values are indexed, and it takes NO lock at all. The sum is assembled shard by shard, so it is a per-shard snapshot rather than one image of the whole index; a value moved between two shards' counts by concurrent writers may be counted once, or not at all, but never twice.
Safe for concurrent use.
func (*Index[V]) Insert ¶
Insert records that node carries the given value. Insert is a no-op when value is a float32 or float64 NaN: Go equality is language-fixed (NaN != NaN), so a NaN key can never be looked up or deleted; skipping it prevents unbounded accumulation (task #1408).
Safe for concurrent use. It contends only with other operations on the SAME value: the shard lookup that precedes it takes no lock at all. Creating a value not yet in the index additionally takes that shard's WRITER lock for the publication alone.
The retry loop exists because an entry can be reaped or displaced between the shard lookup and the entry lock. It terminates: the next iteration either misses the table, and creates a fresh entry under the shard writer lock which no concurrent reaper can drop before this call has published and filled it (reap needs the entry lock the creator still holds, and refuses a non-empty set), or finds a live entry and writes into it.
The loop body is written out here and again in Index.Delete rather than driven through a shared mutate(fn func(*entry)) helper, as graph/index/label does. The reason is legibility of the lock protocol, NOT allocation: the protocol is what deadlocked when this geometry was first built in the label index, so each acquisition and release is spelled out at the site that performs it instead of living behind a callback. The two bodies also differ in substance — Insert creates, Delete reaps, and they move the shard's non-empty counter in opposite directions off different return values.
The allocation argument for the duplication was MEASURED AND REFUTED: a closure passed to a helper that only calls it does not escape, so the label-style helper is allocation-free too (both read 0 allocs/op via testing.AllocsPerRun). Do not re-justify this shape on allocation grounds.
func (*Index[V]) Kind ¶
Kind returns "hash" — satisfies index.Subscriber.
func (*Index[V]) Lookup ¶
Lookup returns a clone of the Roaring bitmap of NodeIDs that carry the given value, or an empty bitmap when the value is unknown or is a NaN (see Index.Insert for the rationale). Clone avoids returning the live bitmap to the caller, which could otherwise be mutated by concurrent writers. Safe for concurrent use, and it takes NO SHARD LOCK: the spine probe is lock-free (rmp #2699), so this read blocks no writer of any value at all, up to the bitmap-tier entry lock below.
func (*Index[V]) LookupAppend ¶ added in v0.6.0
LookupAppend appends the NodeIDs carrying value to dst in strictly ascending order and returns the extended slice, draining the posting list clone-free: out of the entry's meta word alone for a singleton, out of an immutable image for a small list, and under the value's entry read lock only for a bitmap-tier one. It is the allocation-light alternative to Index.Lookup for callers that iterate the result once — the dominant equality index-seek shape: a singleton or small posting list yields its ids with no heap allocation when dst has spare capacity, where Lookup would materialise (or clone) a full roaring bitmap plus an iterator. A NaN key or an unknown value appends nothing. The appended ids are an independent snapshot, so the caller may iterate them after the lock is released, exactly as with the cloned bitmap Lookup returns.
Safe for concurrent use, and it takes NO SHARD LOCK: the spine probe is lock-free (rmp #2699), so this read blocks no writer of any value at all, up to the bitmap-tier entry lock below.
func (*Index[V]) Serialize ¶
Serialize writes every (value, NodeID-set) pair currently in the index to w in the format documented in docs/persistence.md:
uint32 magic ('SHSH')
uint32 formatVersion
uint64 entryCount
repeat entryCount times:
uint32 valueLen
[valueLen]byte value (kind-specific encoding)
uint64 idCount
[idCount]uint64 NodeIDs (sorted ascending)
uint32 crc32c (little-endian, covers every byte above)
Returns index.ErrIndexValueTypeUnsupported when V is not one of the documented supported types.
Safe for concurrent use. Serialize holds one shard's read lock at a time and, within it, each value's entry read lock — no shard lock is taken at all (see Index). The image is therefore per-shard consistent rather than index-wide consistent; callers needing a whole-index point-in-time image must quiesce writers themselves. That was already true before the per-entry geometry, because no writer has ever taken an index-wide lock.
Source Files