keytrie

package
v1.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 28, 2026 License: AGPL-3.0 Imports: 9 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func MatchGlob 

func MatchGlob(s, pattern string) bool

MatchGlob matches a string against a Redis-style glob pattern using O(n*m) algorithm. This avoids exponential backtracking on pathological patterns like "a*a*a*...*b".

Types

type Critbit 

type Critbit[T any] struct {
	// contains filtered or unexported fields
}

Critbit is a crit-bit trie for storing string keys, generic over the per-leaf payload type T (see critNode).

func NewCritbit 

func NewCritbit[T any]() *Critbit[T]

NewCritbit creates a new crit-bit trie with leaf payload type T.

func (*Critbit[T]) ArenaBytes 

func (c *Critbit[T]) ArenaBytes() int64

ArenaBytes returns the combined slot-array footprint of the leaf and internal arenas. Append-only growth means this tracks the high-water mark of allocated nodes and only drops when a whole chunk is reclaimed — so it is the direct measure of trie-skeleton memory, distinct from the vertex pool's effect bytes.

func (*Critbit[T]) Close 

func (c *Critbit[T]) Close() error

func (*Critbit[T]) Closed 

func (c *Critbit[T]) Closed() bool

Closed reports whether Close has been called. Mutations on a closed trie fail unconditionally, so CAS retry loops must check this to avoid spinning forever during shutdown.

func (*Critbit[T]) Contains 

func (c *Critbit[T]) Contains(key string) *TipSet

Contains checks if a key exists and returns its TipSet. Returns nil if the key doesn't exist or is deleted.

func (*Critbit[T]) Delete 

func (c *Critbit[T]) Delete(key string, old *TipSet) bool

func (*Critbit[T]) DeleteAndSnapshot 

func (c *Critbit[T]) DeleteAndSnapshot(key string, old *TipSet) *TipSet

DeleteAndSnapshot removes a key only if its current tips match old (CAS). Returns the previous tip set on success, nil on failure.

func (*Critbit[T]) EvictBatch 

func (c *Critbit[T]) EvictBatch(want int) int

EvictBatch sweeps the leaf arena once and reclaims up to want leaves, so the scan cost is amortized across many evictions — this is what lets the memory governor drain under heavy write load instead of paying a full sweep per key.

It evicts the LRU `want` of the cold (freq <= k) leaves in the window: keeping the *oldest* cold leaves means a just-written key (high lastAccess) is spared, preserving read-your-writes. If the window holds no cold leaf, it falls back — once — to reclaiming the oldest ghost (already-evicted dead weight pinning a chunk), then to evicting the LRU protected leaf. Returns the count reclaimed.

func (*Critbit[T]) EvictBounded 

func (c *Critbit[T]) EvictBounded(maxScan int) bool

EvictBounded evicts a single leaf (or reclaims one ghost). It is a thin wrapper over EvictBatch for one-at-a-time callers and tests; maxScan is ignored (EvictBatch sizes its own window). Returns true if it reclaimed anything.

func (*Critbit[T]) EvictK 

func (c *Critbit[T]) EvictK() float64

EvictBounded runs one bounded eviction sweep. It samples at most maxScan leaves by random root-to-leaf descent, selects the least-recently-used unprotected (freq <= k) leaf among them — falling back to the overall LRU sample when every candidate is protected — soft-deletes it, and notifies the consumer. Returns true if a leaf was evicted.

Latency is bounded by maxScan regardless of keyspace size, and victim quality doesn't depend on key-order locality: the samples are spread across the keyspace the way CloxCache's hash-distributed slot scan was, so the LRU of the sample tracks the global LRU rather than the LRU of a lexicographic neighborhood. EvictK returns the current protected-frequency eviction threshold (the adaptive SLRU promotion bar maybeAdaptK tunes). It is the trie's analogue of CloxCache's per-shard k; telemetry reports it as average_k. Returns the default threshold until the eviction hooks are installed and adaptation runs.

func (*Critbit[T]) EvictStats 

func (c *Critbit[T]) EvictStats() EvictStats

EvictStats snapshots the adaptive policy's internals. Lock-free reads of the same atomics maybeAdaptK uses; the snapshot is not transactionally consistent across fields, which is fine for telemetry.

func (*Critbit[T]) FirstWithPrefix 

func (c *Critbit[T]) FirstWithPrefix(prefix string, claim bool) (string, bool, ReleaseClaimFunc)

func (*Critbit[T]) GetHeadHint 

func (c *Critbit[T]) GetHeadHint(prefix string) string

func (*Critbit[T]) GetTailHint 

func (c *Critbit[T]) GetTailHint(prefix string) string

func (*Critbit[T]) Insert 

func (c *Critbit[T]) Insert(key string, old *TipSet, new *TipSet) (*TipSet, bool)

Insert attempts to store a TipSet for the given key using CAS.

For new keys (old is nil): CAS retry loop for tree structural insertion. For existing keys: single CAS comparing old to the current pointer.

On success: returns (nil, true). On CAS failure: returns (currentTips, false) — the conflicting tip set.

func (*Critbit[T]) Keys 

func (c *Critbit[T]) Keys() []string

func (*Critbit[T]) LastWithPrefix 

func (c *Critbit[T]) LastWithPrefix(prefix string, claim bool) (string, bool, ReleaseClaimFunc)

func (*Critbit[T]) LoadData 

func (c *Critbit[T]) LoadData(key string) *T

LoadData returns the existing leaf payload without installing one. Like Contains, it is a lock-free, stale-tolerant read: compaction leaves relocated husk payloads intact, so a reader that captured the old leaf still observes the same *T. A successful lookup records the access for eviction policy.

func (*Critbit[T]) LoadOrStoreData 

func (c *Critbit[T]) LoadOrStoreData(key string, def *T) (*T, bool)

LoadOrStoreData returns the leaf payload for key, installing def if none is present yet (CAS, so concurrent callers agree on a single payload). Returns (nil, false) if the key is missing/deleted. The bool reports whether an existing payload was loaded (true) rather than def being stored (false).

Locating the payload counts as an access: it bumps the leaf's frequency and last-access stamp, which is the signal the eviction policy learns from. The read path (reconstruct) calls this on every read, hit or miss.

The install CAS runs under the reap read-lock like every other leaf-field mutation: compaction (write lock) relocates leaves, and a CAS landing on a relocated husk would be silently lost.

func (*Critbit[T]) MatchPattern 

func (c *Critbit[T]) MatchPattern(pattern string) []string

func (*Critbit[T]) NextWithPrefix 

func (c *Critbit[T]) NextWithPrefix(prefix, after string, claim bool) (string, bool, ReleaseClaimFunc)

func (*Critbit[T]) Pin 

func (c *Critbit[T]) Pin(key string) bool

Pin adds a dynamic do-not-evict hold on key's live leaf, reporting whether one was taken (false: no live leaf — nothing to protect). Taken under the reap read lock, writer discipline: chunk compaction copies leaf fields under the write lock, so a hold can never land on a husk the copy already left.

func (*Critbit[T]) PrevWithPrefix 

func (c *Critbit[T]) PrevWithPrefix(prefix, before string, claim bool) (string, bool, ReleaseClaimFunc)

func (*Critbit[T]) Range 

func (c *Critbit[T]) Range(fn func(key string) bool)

func (*Critbit[T]) RangeFrom 

func (c *Critbit[T]) RangeFrom(after string, fn func(key string) bool)

func (*Critbit[T]) RangePrefix 

func (c *Critbit[T]) RangePrefix(prefix string, fn func(key string) bool)

func (*Critbit[T]) RemoveTips 

func (c *Critbit[T]) RemoveTips(key string, refs []EffectRef)

RemoveTips drops refs from key's tip set (CAS retry). The CAS runs under the reap read-lock like every other leaf-field mutation: compaction (write lock) relocates leaves, and a CAS landing on a relocated husk would be silently lost. The delta fires outside the lock (the hook may re-enter the trie).

func (*Critbit[T]) SetDecayInterval 

func (c *Critbit[T]) SetDecayInterval(n int)

SetDecayInterval overrides the eviction-driven frequency decay cadence: n > 0 sets reclaims-per-step, n <= 0 disables decay entirely. Call at setup; the default auto-scales with the live-leaf count (see decayIntervalNow).

func (*Critbit[T]) SetEvictHooks 

func (c *Critbit[T]) SetEvictHooks(decider func(key string) bool, notify func(key string, tips []EffectRef, data *T), pressure func() bool)

SetEvictHooks installs the consumer callbacks the eviction sweep uses. decider vetoes a key as an eviction victim (return false to pin it, e.g. system keys). notify fires after a victim leaf is soft-deleted, handing the consumer the dropped key's tips and leaf payload so it can release refs and tear down (e.g. unsubscribe). pressure reports whether the consumer is currently over its eviction target — the instantaneous condition that gates graduation counting in bumpAccess (see underPressure). All three run without any trie lock the consumer could re-enter; keep them prompt.

decider must be installed before any Insert: the sweep reads each leaf's pin verdict (critNode.pinned) cached at creation, so a leaf written before the decider exists would carry the default (unpinned) verdict. The memory governor installs the hooks inside NewEngine, before any write, so this holds.

func (*Critbit[T]) SetHeadHint 

func (c *Critbit[T]) SetHeadHint(prefix string, key string)

func (*Critbit[T]) SetRefDelta 

func (c *Critbit[T]) SetRefDelta(fn func(added, removed []EffectRef, droppedData *T))

SetRefDelta installs the per-tip refcount hook, fired on every leaf tip-set transition (insert, remove, delete, eviction). See the refDelta field.

func (*Critbit[T]) SetTailHint 

func (c *Critbit[T]) SetTailHint(prefix string, key string)

func (*Critbit[T]) Size 

func (c *Critbit[T]) Size() int64

func (*Critbit[T]) Snapshot 

func (c *Critbit[T]) Snapshot() KeyIndex

Snapshot returns a frozen copy of the index. The new Critbit is independent — mutations to either copy don't affect the other. TipSets are immutable so only pointers are copied. Leaf payloads (T) are NOT copied: a snapshot is a tip-only view used for SSI reads. O(n) in key count.

func (*Critbit[T]) TryClaimKey 

func (c *Critbit[T]) TryClaimKey(key string) (exists bool, release ReleaseClaimFunc)

func (*Critbit[T]) Unpin 

func (c *Critbit[T]) Unpin(key string) bool

Unpin releases one dynamic hold on key's live leaf. A missing or deleted leaf is a no-op (the key was explicitly deleted or the index flushed while held — the hold died with the leaf). A negative count on a live leaf is an unpin without a matching pin: a protocol bug that would let the sweep evict a key another holder still protects, so it panics like a refcount underflow.

type EffectRef 

type EffectRef = [2]uint64

EffectRef is a (nodeID, offset) pair identifying an effect globally.

type EvictStats 

type EvictStats struct {
	K                  int32   // current protected-freq threshold
	GraduationRate     float64 // ReachedProtected / (EvictedUnprotected+EvictedProtected)
	RateLow            float64 // learned threshold below which k decreases
	RateHigh           float64 // learned threshold above which k increases
	EvictedUnprotected uint64  // windowed: victims with freq <= k (cold, expected)
	EvictedProtected   uint64  // windowed: victims with freq > k (forced — pressure too high)
	ReachedProtected   uint64  // windowed: leaves that graduated past k
	WindowHitRate      float64 // current adapt-window hit rate (self-tuning gradient input)
	GhostCount         int64   // ghosts retained for warm restart
}

EvictStats is a point-in-time snapshot of the adaptive eviction policy's internal state, for telemetry. The counters (EvictedUnprotected/Protected, ReachedProtected) are windowed — maybeAdaptK halves them periodically — so they reflect recent behaviour, not lifetime totals. GraduationRate is the quantity that actually drives k: when it exceeds RateHigh, k rises; below RateLow, k falls.

type KeyIndex 

type KeyIndex interface {
	// Insert attempts to store a TipSet for the given key using CAS.
	// old is the expected current TipSet (nil for new keys).
	// On success: returns (nil, true).
	// On CAS failure: returns (currentTips, false).
	Insert(key string, old *TipSet, new *TipSet) (*TipSet, bool)

	// Delete removes a key only if its current tips match old (CAS).
	// Returns true if the key was deleted.
	Delete(key string, old *TipSet) bool

	// DeleteAndSnapshot removes a key only if its current tips match old
	// (CAS), returning the previous tip set on success. Returns nil if
	// the key did not exist, was already deleted, or tips changed since
	// old was read.
	DeleteAndSnapshot(key string, old *TipSet) *TipSet

	// Contains checks if a key exists and returns its TipSet.
	// Returns nil if key doesn't exist.
	Contains(key string) *TipSet

	// RemoveTips atomically removes the given refs from a key's TipSet.
	// Safe to call concurrently — uses CAS internally. No-op if the key
	// doesn't exist or the refs aren't present.
	RemoveTips(key string, refs []EffectRef)

	// Size returns the number of keys.
	Size() int64

	// Range iterates over all keys in lexicographic order.
	Range(fn func(key string) bool)

	// RangeFrom iterates over keys in lexicographic order starting after `after`.
	// If after is empty, iterates from the beginning (same as Range).
	RangeFrom(after string, fn func(key string) bool)

	// RangePrefix iterates over all keys with the given prefix.
	RangePrefix(prefix string, fn func(key string) bool)

	// Keys returns all keys.
	Keys() []string

	// MatchPattern returns all keys matching a Redis-style glob pattern.
	MatchPattern(pattern string) []string

	// FirstWithPrefix finds the lexicographically smallest key with the given prefix.
	FirstWithPrefix(prefix string, claim bool) (string, bool, ReleaseClaimFunc)

	// LastWithPrefix finds the lexicographically largest key with the given prefix.
	LastWithPrefix(prefix string, claim bool) (string, bool, ReleaseClaimFunc)

	// NextWithPrefix finds the next key after 'after' with the given prefix.
	NextWithPrefix(prefix, after string, claim bool) (string, bool, ReleaseClaimFunc)

	// PrevWithPrefix finds the previous key before 'before' with the given prefix.
	PrevWithPrefix(prefix, before string, claim bool) (string, bool, ReleaseClaimFunc)

	// TryClaimKey attempts to claim a key for exclusive access.
	TryClaimKey(key string) (exists bool, release ReleaseClaimFunc)

	// GetHeadHint returns the head key hint for a prefix.
	GetHeadHint(prefix string) string

	// SetHeadHint sets the head key hint for a prefix.
	SetHeadHint(prefix string, key string)

	// GetTailHint returns the tail key hint for a prefix.
	GetTailHint(prefix string) string

	// SetTailHint sets the tail key hint for a prefix.
	SetTailHint(prefix string, key string)

	// Snapshot returns a point-in-time copy of the index as a new KeyIndex.
	// TipSets are immutable, so only pointers are copied. Preserves all
	// critbit properties (prefix ranges, ordered iteration).
	Snapshot() KeyIndex

	// Close releases any resources held by the index.
	Close() error
}

KeyIndex is the common interface for key indexing implementations.

func New 

func New() KeyIndex

New creates a new critbit tree with no leaf payload (plain tip index). Consumers that attach per-key leaf data use NewCritbit[T] directly.

type ReleaseClaimFunc 

type ReleaseClaimFunc func()

ReleaseClaimFunc is a function that releases a claimed key.

type TipSet 

type TipSet struct {
	// contains filtered or unexported fields
}

TipSet holds an immutable set of effect references representing concurrent branch tips for a key. Once created, a TipSet is never modified — all mutations produce a new TipSet (copy-on-write).

func NewTipSet 

func NewTipSet(refs ...EffectRef) *TipSet

NewTipSet creates a new TipSet from the given refs, deduplicating them.

func (*TipSet) Contains 

func (ts *TipSet) Contains(ref EffectRef) bool

Contains reports whether the tip set contains the given ref.

func (*TipSet) ContainsAll 

func (ts *TipSet) ContainsAll(refs []EffectRef) bool

ContainsAll reports whether the tip set contains all of the given refs.

func (*TipSet) Len 

func (ts *TipSet) Len() int

Len returns the number of tips.

func (*TipSet) Single 

func (ts *TipSet) Single() (EffectRef, bool)

Single returns the single ref if this tip set has exactly one tip, plus a boolean.

func (*TipSet) Tips 

func (ts *TipSet) Tips() []EffectRef

Tips returns the refs in this tip set.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.