Documentation
¶
Overview ¶
Package hnsw provides the implementation of the Hierarchical Navigable Small World graph algorithm for efficient approximate nearest neighbor search.
This file defines the min-heap and max-heap data structures used extensively during the graph traversal and construction phases of the HNSW algorithm. OPTIMIZED VERSION: Uses value semantics (no pointers) for CPU Cache locality and zero GC overhead.
Package hnsw provides the implementation of the Hierarchical Navigable Small World (HNSW) graph algorithm for efficient approximate nearest neighbor search.
This package contains the core Index struct and its associated methods for building, searching, and managing the HNSW graph. It supports multiple distance metrics (Euclidean, Cosine), various data precisions (float32, float16, int8 quantization), and concurrent access patterns including batch insertions.
Index ¶
- Constants
- func ValidateDecayModel(model DecayModel) bool
- type ArenaCompactionConfig
- type AutoLinkRule
- type AutoMaintenanceConfig
- type BitSet
- type ConsolidationConfig
- type DecayModel
- type Duration
- type GraphOptimizer
- func (o *GraphOptimizer) GetConfig() AutoMaintenanceConfig
- func (o *GraphOptimizer) Refine() bool
- func (o *GraphOptimizer) RunCycle(forceType string) bool
- func (o *GraphOptimizer) RunTurboRefine()
- func (o *GraphOptimizer) UpdateConfig(cfg AutoMaintenanceConfig)
- func (o *GraphOptimizer) Vacuum() bool
- type Index
- func (h *Index) Add(id string, vector []float32) (uint32, error)
- func (h *Index) AddBatch(objects []types.BatchObject) error
- func (h *Index) AddBatchFast(objects []types.BatchObject) error
- func (h *Index) AddOld(id string, vector []float32) (uint32, error)
- func (h *Index) ArenaForTest() *mmap.VectorArena
- func (h *Index) Close() error
- func (h *Index) ComputeDistanceToVector(nodeID string, query []float32) (float64, error)
- func (h *Index) Delete(id string)
- func (h *Index) EfConstruction() int
- func (h *Index) EntrypointForTest() (uint32, int32)
- func (h *Index) GetAllValidNodeIDs() (*roaring.Bitmap, error)
- func (h *Index) GetArenaDir() string
- func (h *Index) GetArenaState() mmap.ArenaState
- func (h *Index) GetAutoLinks() []AutoLinkRule
- func (h *Index) GetDimension() int
- func (h *Index) GetExternalID(internalID uint32) (string, bool)
- func (h *Index) GetIDsByCursor(startCursor uint32, limit int) ([]string, uint32)
- func (h *Index) GetInfo() (distance.DistanceMetric, int, int, distance.PrecisionType, int, string)
- func (h *Index) GetInfoUnlocked() (distance.DistanceMetric, int, int, distance.PrecisionType, int, string)
- func (h *Index) GetInternalID(externalID string) (uint32, bool)
- func (h *Index) GetInternalIDUnlocked(externalID string) (uint32, bool)
- func (h *Index) GetMaintenanceConfig() AutoMaintenanceConfig
- func (h *Index) GetMemoryConfig() MemoryConfig
- func (h *Index) GetNodeData(externalID string) (types.NodeData, bool)
- func (h *Index) GetParameters() (distance.DistanceMetric, int, int)
- func (h *Index) GetParametersUnlocked() (distance.DistanceMetric, distance.PrecisionType, int, int)
- func (h *Index) IsClosed() bool
- func (h *Index) Iterate(callback func(id string, vector []float32))
- func (h *Index) IterateRaw(callback func(id string, vector interface{}))
- func (h *Index) LoadSnapshotData(nodesMap map[uint32]*Node, extToInt map[string]uint32, counter uint32, ...) error
- func (h *Index) LockNode(id uint32)
- func (h *Index) M() int
- func (h *Index) MaintenanceRun(forceType string) bool
- func (h *Index) MarkClosed()
- func (h *Index) Metric() distance.DistanceMetric
- func (h *Index) NeedsRefine() bool
- func (h *Index) Precision() distance.PrecisionType
- func (h *Index) Quantizer() *distance.Quantizer
- func (h *Index) RLock()
- func (h *Index) RLockNode(id uint32)
- func (h *Index) RUnlock()
- func (h *Index) RUnlockNode(id uint32)
- func (h *Index) RunTurboRefine()
- func (h *Index) SearchWithScores(query []float32, k int, allowList *roaring.Bitmap, efSearch int) []types.SearchResult
- func (h *Index) SetAutoLinks(rules []AutoLinkRule)
- func (h *Index) SetMemoryConfig(cfg MemoryConfig)
- func (h *Index) SetNeedsRefine(val bool)
- func (h *Index) SnapshotData() (map[uint32]*Node, map[string]uint32, uint32, uint32, int, *distance.Quantizer, ...)
- func (h *Index) TextLanguage() string
- func (h *Index) TrainQuantizer(vectors [][]float32)
- func (h *Index) UnlockNode(id uint32)
- func (h *Index) UpdateMaintenanceConfig(cfg AutoMaintenanceConfig)
- func (h *Index) UpdateNodePointer(internalID uint32, newVectorBytes []byte)
- type IndexConfig
- type LayerConfig
- type LinkRequest
- type MemoryConfig
- type Node
Constants ¶
const NumShards = 128
Variables ¶
This section is empty.
Functions ¶
func ValidateDecayModel ¶ added in v0.5.1
func ValidateDecayModel(model DecayModel) bool
ValidateDecayModel checks if the model is supported.
Types ¶
type ArenaCompactionConfig ¶ added in v0.5.1
type ArenaCompactionConfig struct {
// Enabled activates background compaction. Default: true.
Enabled bool `json:"enabled"`
// Interval between compaction checks. Default: 5m.
Interval Duration `json:"interval"`
// Threshold (0.0-1.0) that triggers compaction. Default: 0.3 (30%).
Threshold float64 `json:"threshold"`
// Max vectors to process per cycle. Default: 100.
BatchSize int `json:"batch_size"`
// Delay between batches to avoid saturation. Default: 1ms.
BatchDelay Duration `json:"batch_delay"`
}
ArenaCompactionConfig defines the behavior of arena background compaction.
type AutoLinkRule ¶ added in v0.4.5
type AutoLinkRule struct {
// MetadataField is the key in the metadata map to look for (e.g., "chat_id").
MetadataField string `json:"metadata_field"`
// RelationType is the type of the link to create (e.g., "belongs_to_chat").
RelationType string `json:"relation_type"`
// CreateNode indicates whether to create a "stub" node for the target
// if it doesn't exist. Default should be true for most cases.
CreateNode bool `json:"create_node"`
}
AutoLinkRule defines a rule for automatically creating graph connections based on metadata fields during vector insertion.
type AutoMaintenanceConfig ¶ added in v0.3.0
type AutoMaintenanceConfig struct {
// Vacuum (Cleanup) Settings
// Interval between vacuum checks. Default: 1m.
VacuumInterval Duration `json:"vacuum_interval"`
// Percentage of deleted nodes (0.0-1.0) to trigger vacuum. Default: 0.1 (10%).
DeleteThreshold float64 `json:"delete_threshold"`
// Graph Vacuum Settings
// How often to scan for expired edges (e.g. "1h").
GraphVacuumInterval Duration `json:"graph_vacuum_interval"`
// How long to keep soft-deleted edges (e.g. "720h" = 30 days).
// If 0, history is kept forever (Time Travel).
GraphRetention Duration `json:"graph_retention"`
// Refine (Optimization) Settings
// If true, runs background optimization to improve recall. Default: false.
RefineEnabled bool `json:"refine_enabled"`
// Interval between refinement cycles. Default: 30s.
RefineInterval Duration `json:"refine_interval"`
// Number of nodes to re-process per cycle. Default: 100.
RefineBatchSize int `json:"refine_batch_size"`
// Search breadth during refinement. Higher = better quality but slower.
// If 0, uses the index's efConstruction default.
RefineEfConstruction int `json:"refine_ef_construction"`
// Arena Compaction Settings
// Background compaction for MMAP arena to reclaim freed slots.
ArenaCompaction ArenaCompactionConfig `json:"arena_compaction"`
}
AutoMaintenanceConfig defines the behavior of background tasks per index.
func DefaultMaintenanceConfig ¶ added in v0.3.0
func DefaultMaintenanceConfig() AutoMaintenanceConfig
DefaultMaintenanceConfig returns safe defaults: Vacuum ON, Refine OFF.
type BitSet ¶ added in v0.2.2
type BitSet struct {
// contains filtered or unexported fields
}
func (*BitSet) EnsureCapacity ¶ added in v0.2.2
type ConsolidationConfig ¶ added in v0.5.1
type ConsolidationConfig struct {
// SimilarityThreshold (0.0-1.0) determines how similar memories must be
// to be considered for consolidation. Default: 0.90.
SimilarityThreshold float64 `json:"similarity_threshold"`
// MaxEpisodicAge limits consolidation to memories newer than this duration.
// Default: "168h" (7 days).
MaxEpisodicAge Duration `json:"max_episodic_age"`
}
ConsolidationConfig controls how the Gardener consolidates redundant memories.
type DecayModel ¶ added in v0.5.1
type DecayModel string
DecayModel represents the time decay algorithm for memory relevance scoring.
const ( // DecayExponential is the classic half-life decay: 2^(-age/halfLife) DecayExponential DecayModel = "exponential" // DecayLinear is linear decay: 1.0 - age/halfLife, clamped at 0.0 DecayLinear DecayModel = "linear" // DecayStep is on/off decay: 1.0 if age < halfLife, else 0.0 DecayStep DecayModel = "step" // DecayEbbinghaus is the Ebbinghaus forgetting curve: e^(-age/S) // where S (stability) increases logarithmically with reinforcements DecayEbbinghaus DecayModel = "ebbinghaus" )
type Duration ¶ added in v0.3.0
Duration is a wrapper around time.Duration that supports JSON string parsing (e.g. "1m", "10s").
func (Duration) MarshalJSON ¶ added in v0.3.0
MarshalJSON serializes the duration back to a readable string.
func (*Duration) UnmarshalJSON ¶ added in v0.3.0
UnmarshalJSON implements custom decoding logic. It handles both numbers (nanoseconds) and strings ("10s").
type GraphOptimizer ¶ added in v0.3.0
type GraphOptimizer struct {
// contains filtered or unexported fields
}
GraphOptimizer manages background maintenance tasks.
func NewOptimizer ¶ added in v0.3.0
func NewOptimizer(index *Index, cfg AutoMaintenanceConfig) *GraphOptimizer
func (*GraphOptimizer) GetConfig ¶ added in v0.3.0
func (o *GraphOptimizer) GetConfig() AutoMaintenanceConfig
GetConfig returns the current configuration.
func (*GraphOptimizer) Refine ¶ added in v0.3.0
func (o *GraphOptimizer) Refine() bool
Refine improves the graph quality by re-evaluating neighbors for a batch of nodes. This implementation uses parallel computation with sharded commit for better performance.
func (*GraphOptimizer) RunCycle ¶ added in v0.3.0
func (o *GraphOptimizer) RunCycle(forceType string) bool
RunCycle checks timers and executes tasks. Called by the Engine ticker.
func (*GraphOptimizer) RunTurboRefine ¶ added in v0.5.1
func (o *GraphOptimizer) RunTurboRefine()
RunTurboRefine launches an aggressive, continuous optimization loop. It uses max CPU and huge batches until the entire graph has been re-evaluated. Designed to run immediately after a Fast Bulk Import.
func (*GraphOptimizer) UpdateConfig ¶ added in v0.3.0
func (o *GraphOptimizer) UpdateConfig(cfg AutoMaintenanceConfig)
UpdateConfig updates settings on the fly.
func (*GraphOptimizer) Vacuum ¶ added in v0.3.0
func (o *GraphOptimizer) Vacuum() bool
Vacuum scans for deleted nodes, repairs links pointing to them, and frees memory. This implementation uses an incremental approach to minimize lock contention: Phase 1: Identify deleted nodes (RLock) Phase 2: Repair affected nodes in batches (Lock per batch, released between batches) Phase 3: Final cleanup (Lock)
type Index ¶
type Index struct {
// contains filtered or unexported fields
}
Index represents the hierarchical graph structure.
func New ¶
func New(m int, efConstruction int, metric distance.DistanceMetric, precision distance.PrecisionType, textLang string, arenaDir string) (*Index, error)
New creates and initializes a new HNSW index
func (*Index) Add ¶
Add inserts a new vector into the index. THREAD-SAFE: Uses fine-grained locking to allow concurrent searches during insertion.
func (*Index) AddBatch ¶ added in v0.2.2
func (h *Index) AddBatch(objects []types.BatchObject) error
func (*Index) AddBatchFast ¶ added in v0.5.1
func (h *Index) AddBatchFast(objects []types.BatchObject) error
func (*Index) ArenaForTest ¶ added in v0.6.3
func (h *Index) ArenaForTest() *mmap.VectorArena
ArenaForTest exposes the underlying arena for tests that need to assert on its internal wiring (e.g. whether the compactor is registered, so StopCompactor is not a silent no-op). Not for production use: callers must not hold the reference across Close.
func (*Index) Close ¶ added in v0.5.1
Close safely unmaps the virtual memory and closes file handles. Uses a timeout to prevent deadlock if compactor cannot stop.
func (*Index) ComputeDistanceToVector ¶ added in v0.4.7
ComputeDistanceToVector calculates the distance between an existing node (by ID) and a raw float32 query. It handles necessary conversions (normalization, quantization) internally.
func (*Index) Delete ¶
Delete marks a node as deleted (soft delete). It does not remove the node from the graph to maintain structural stability.
func (*Index) EfConstruction ¶
EfConstruction returns the HNSW efConstruction parameter.
func (*Index) EntrypointForTest ¶ added in v0.6.3
EntrypointForTest exposes the current entry point and max level for tests that need to assert on graph state after recovery or deletion.
func (*Index) GetAllValidNodeIDs ¶ added in v0.5.2
GetAllValidNodeIDs returns a roaring bitmap of all non-deleted internal node IDs. Used for filter operations requiring complement sets (e.g., != operator).
func (*Index) GetArenaDir ¶ added in v0.5.1
func (*Index) GetArenaState ¶ added in v0.5.1
func (h *Index) GetArenaState() mmap.ArenaState
func (*Index) GetAutoLinks ¶ added in v0.4.5
func (h *Index) GetAutoLinks() []AutoLinkRule
GetAutoLinks returns a copy of the current auto-linking rules.
func (*Index) GetDimension ¶ added in v0.4.5
GetDimension returns the vector dimension of the index.
func (*Index) GetExternalID ¶
GetExternalID returns the external string ID associated with an internal uint32 ID
func (*Index) GetIDsByCursor ¶ added in v0.5.1
GetIDsByCursor retrieves a batch of external IDs starting from a specific internal ID. It returns the slice of IDs and the next internal ID to use as a cursor. This is O(limit) and avoids the Deep Paging problem of standard offset iteration.
func (*Index) GetInfo ¶
func (h *Index) GetInfo() (distance.DistanceMetric, int, int, distance.PrecisionType, int, string)
GetInfo returns all public parameters and the state of the index.
func (*Index) GetInfoUnlocked ¶
func (h *Index) GetInfoUnlocked() (distance.DistanceMetric, int, int, distance.PrecisionType, int, string)
GetInfoUnlocked returns index information without acquiring a lock.
func (*Index) GetInternalID ¶
GetInternalID retrieves the internal ID for a given external ID.
func (*Index) GetInternalIDUnlocked ¶
GetInternalIDUnlocked retrieves the internal ID without locking. Caller must ensure safety.
func (*Index) GetMaintenanceConfig ¶ added in v0.3.0
func (h *Index) GetMaintenanceConfig() AutoMaintenanceConfig
func (*Index) GetMemoryConfig ¶ added in v0.4.7
func (h *Index) GetMemoryConfig() MemoryConfig
GetMemoryConfig returns the memory settings.
func (*Index) GetNodeData ¶
GetNodeData retrieves the complete data for a node (decompressed/dequantized) given its external ID.
func (*Index) GetParameters ¶
func (h *Index) GetParameters() (distance.DistanceMetric, int, int)
GetParameters returns the configuration parameters of the index.
func (*Index) GetParametersUnlocked ¶
func (h *Index) GetParametersUnlocked() (distance.DistanceMetric, distance.PrecisionType, int, int)
GetParametersUnlocked returns parameters without a lock.
func (*Index) IsClosed ¶ added in v0.6.1
IsClosed reports whether the index has been closed (or is closing). Useful for external consumers iterating indexes (e.g. snapshot) to skip indexes that are being shut down concurrently.
func (*Index) Iterate ¶
Iterate loops over all non-deleted nodes and passes the external ID and vector (always as []float32) to a callback function.
func (*Index) IterateRaw ¶
IterateRaw iterates over non-deleted nodes and passes the external ID and the RAW vector (as an interface{}) to the callback.
func (*Index) LoadSnapshotData ¶
func (h *Index) LoadSnapshotData( nodesMap map[uint32]*Node, extToInt map[string]uint32, counter uint32, entrypoint uint32, maxLevel int, quantizer *distance.Quantizer, norms []float32, arenaState mmap.ArenaState, savedDim int, ) error
LoadSnapshotData restores the internal state of the index from snapshot data. It expects the index to be empty and the caller to handle locking.
func (*Index) LockNode ¶ added in v0.4.7
LockNode acquires the Write Lock for a specific node's shard.
func (*Index) MaintenanceRun ¶ added in v0.3.0
func (*Index) MarkClosed ¶ added in v0.5.1
func (h *Index) MarkClosed()
MarkClosed sets the closed flag. Used during testing or forced shutdown.
func (*Index) Metric ¶
func (h *Index) Metric() distance.DistanceMetric
Metric returns the distance metric used by the index.
func (*Index) NeedsRefine ¶ added in v0.5.1
NeedsRefine returns true if the index was fast-imported and needs optimization.
func (*Index) Precision ¶
func (h *Index) Precision() distance.PrecisionType
Precision returns the data precision used by the index.
func (*Index) RLock ¶
func (h *Index) RLock()
RLock acquires a read lock on the index. For use by external callers like the DB.
func (*Index) RLockNode ¶ added in v0.4.7
RLockNode acquires the Read Lock for a specific node's shard.
func (*Index) RUnlockNode ¶ added in v0.4.7
RUnlockNode releases the Read Lock.
func (*Index) RunTurboRefine ¶ added in v0.5.1
func (h *Index) RunTurboRefine()
RunTurboRefine triggers the aggressive background optimization.
func (*Index) SearchWithScores ¶
func (h *Index) SearchWithScores(query []float32, k int, allowList *roaring.Bitmap, efSearch int) []types.SearchResult
SearchWithScores finds the K nearest neighbors to a query vector, returning their scores (distances)
func (*Index) SetAutoLinks ¶ added in v0.4.5
func (h *Index) SetAutoLinks(rules []AutoLinkRule)
SetAutoLinks updates the auto-linking rules for the index.
func (*Index) SetMemoryConfig ¶ added in v0.4.7
func (h *Index) SetMemoryConfig(cfg MemoryConfig)
SetMemoryConfig updates the memory settings.
func (*Index) SetNeedsRefine ¶ added in v0.5.1
SetNeedsRefine marks the index as dirty (needing optimization) or clean.
func (*Index) SnapshotData ¶
func (h *Index) SnapshotData() (map[uint32]*Node, map[string]uint32, uint32, uint32, int, *distance.Quantizer, []float32, []AutoLinkRule, MemoryConfig, int)
SnapshotData exports the internal data of the index for persistence. It expects the caller to handle locking.
func (*Index) TextLanguage ¶
TextLanguage returns the language configured for text analysis.
func (*Index) TrainQuantizer ¶
TrainQuantizer trains the index's quantizer on a sample of vectors.
func (*Index) UnlockNode ¶ added in v0.4.7
UnlockNode releases the Write Lock.
func (*Index) UpdateMaintenanceConfig ¶ added in v0.3.0
func (h *Index) UpdateMaintenanceConfig(cfg AutoMaintenanceConfig)
func (*Index) UpdateNodePointer ¶ added in v0.5.1
UpdateNodePointer implements mmap.NodePointerUpdater. This is called by the ArenaCompactor when a vector's physical location changes. We need to update the node's vector pointer to point to the new memory location.
type IndexConfig ¶ added in v0.4.7
type IndexConfig struct {
Metric distance.DistanceMetric
Precision distance.PrecisionType
M int
EfConstruction int
TextLanguage string
// Existing Graph Config
AutoLinks []AutoLinkRule `json:"auto_links,omitempty"`
// NEW: Memory Engine Config
MemoryConfig MemoryConfig `json:"memory_config,omitempty"`
}
IndexConfig holds the configuration parameters for a vector index.
type LayerConfig ¶ added in v0.5.1
type LayerConfig struct {
// DecayHalfLife is the time duration after which a memory's relevance score is halved.
// Example: "72h" (3 days) for episodic, "720h" (30 days) for semantic.
// If 0, the layer has no decay (e.g., procedural memories).
DecayHalfLife Duration `json:"decay_half_life"`
// PinnedByDefault automatically sets _pinned=true for memories in this layer
// unless explicitly overridden by the user. Useful for procedural memories.
PinnedByDefault bool `json:"pinned_by_default"`
// AutoSummarize enables automatic consolidation of redundant memories
// in this layer into higher-level semantic memories.
AutoSummarize bool `json:"auto_summarize"`
// Description is an optional human-readable description of the layer's purpose.
Description string `json:"description,omitempty"`
}
LayerConfig defines the behavior of a specific memory layer (episodic, semantic, procedural).
type LinkRequest ¶ added in v0.2.2
LinkRequest represents a single atomic connection modification operation to be applied to the graph. It is used by the concurrent AddBatch method and can be extended for future graph repair mechanisms.
type MemoryConfig ¶ added in v0.4.7
type MemoryConfig struct {
// Enabled activates time-decay logic via VSearch.
Enabled bool `json:"enabled"`
// DecayModel selects the algorithm for time decay.
// Supported: "exponential" (default), "linear", "step", "ebbinghaus".
DecayModel DecayModel `json:"decay_model"`
// DecayHalfLife is the global time duration after which a memory's relevance score is halved.
// Example: "168h" (7 days). If 0, defaults to a standard value (e.g. 7 days).
// Deprecated: Use Layers for per-layer decay configuration.
DecayHalfLife Duration `json:"decay_half_life"`
// Layers defines per-layer configuration for episodic, semantic, and procedural memories.
// If empty, falls back to global DecayHalfLife for backward compatibility.
Layers map[string]LayerConfig `json:"layers,omitempty"`
// Consolidation controls how the Gardener merges redundant memories.
Consolidation ConsolidationConfig `json:"consolidation,omitempty"`
}
MemoryConfig controls the time-dependent ranking features.
func DefaultMemoryConfig ¶ added in v0.5.1
func DefaultMemoryConfig() MemoryConfig
DefaultMemoryConfig returns a MemoryConfig with sensible defaults for all layers.
type Node ¶
type Node struct {
// Id is the user-facing, external identifier for the vector.
Id string
// InternalID is a unique, memory-efficient identifier used for graph traversal.
InternalID uint32
// Connections is a slice of slices, where the outer index represents the graph layer,
// and the inner slice contains the list of neighbors at that layer.
// Connections[0] holds the neighbors at the base layer (layer 0).
// Neighbor IDs are stored as uint32 for memory efficiency.
// Protected by fine-grained shard locks (shardsMu).
Connections [][]uint32
// Deleted is a flag used for soft deletes, marking the node as removed
// from the graph without physically deleting it.
// Uses atomic.Bool for thread-safe access.
Deleted atomic.Bool
// contains filtered or unexported fields
}
Node represents a single node within the HNSW graph. It contains the vector data, its connections at various layers, and metadata for identification and state.
func (*Node) GetVectorF16 ¶ added in v0.5.1
GetVectorF16 returns the uint16 (float16) vector slice, or nil if not set.
func (*Node) GetVectorF32 ¶ added in v0.5.1
GetVectorF32 returns the float32 vector slice, or nil if not set.
func (*Node) GetVectorI8 ¶ added in v0.5.1
GetVectorI8 returns the int8 vector slice, or nil if not set.