HNSW: Hierarchical Navigable Small World Graph

A Go implementation of the HNSW (Hierarchical Navigable Small World) algorithm for approximate nearest neighbor search with full persistence and crash recovery.

This implementation provides an efficient vector similarity search index with several key features:

• Bidirectional graph links with strategies to ensure connectivity even when neighbors are at capacity
• Vector normalization on insert, making cosine similarity equivalent to dot product
• Quantization support (Q8 and binary) for reduced memory usage and faster distance calculations
• True element deletion with automatic graph reconnection
• Full persistence with Write-Ahead Logging (WAL) for durability and crash recovery
• Batch transaction support for improved write throughput
• Concurrent read support with up to 128 simultaneous search threads

// Create index with:
//   - 128-dimensional vectors
//   - M=16 connections per node (typical: 8-64)
//   - File path for persistence
//   - Q8 quantization (4x compression)
index, err := hnsw.NewHNSW(128, 16, "myindex.hnsw", hnsw.QuantQ8)
if err != nil {
    log.Fatal(err)
}
defer index.Close()

Quantization options:

• QuantQ8: 8-bit quantization (4x compression, minimal accuracy loss)
• QuantBin: Binary quantization (32x compression, higher accuracy loss)

Single insert with auto-commit:

vector := make([]float32, 128)
// ... fill vector with data ...

// Insert with:
//   - vector: float32 slice (will be normalized)
//   - id: unique ID (use 0 for auto-generated)
//   - value: optional metadata
//   - ef: search quality parameter (200 is default)
node, err := index.Insert(vector, 0, "metadata", 200)
if err != nil {
    log.Fatal(err)
}
fmt.Printf("Inserted node ID: %d\n", node.ID)

Batch inserts with explicit transaction (10-50x faster):

txn, err := index.Begin()
if err != nil {
    log.Fatal(err)
}
defer txn.Rollback() // Cleanup on error

insertedIDs := make([]uint64, 0, 1000)

for i := 0; i < 1000; i++ {
    node, err := txn.Insert(vectors[i], 0, metadata[i], 200)
    if err != nil {
        return err // Auto-rollback via defer
    }
    insertedIDs = append(insertedIDs, node.ID)
}

// Make all changes durable
if err := txn.Commit(); err != nil {
    log.Fatal(err)
}

fmt.Printf("Inserted %d vectors with IDs: %v\n", len(insertedIDs), insertedIDs)

Note: Transactions provide crash recovery and batched WAL writes, but do not provide true ACID isolation. Uncommitted changes are visible to concurrent readers immediately.

query := make([]float32, 128)
// ... fill query vector ...

// Search for k=10 nearest neighbors with ef=50
// ef controls search quality: higher = more accurate but slower
// Typical values: 50-200, must be >= k
nodes, distances, err := index.Search(query, 10, 50)
if err != nil {
    log.Fatal(err)
}

for i, node := range nodes {
    fmt.Printf("Result %d: ID=%d, distance=%.4f, value=%v\n",
        i, node.ID, distances[i], node.Value)
}

Distance metric: Cosine distance in range [0, 2]

• 0: Identical vectors (same direction)
• 1: Orthogonal vectors
• 2: Opposite vectors (opposite directions)

// Delete by node ID with auto-commit
err := txn.Delete(nodeID)

// Or in a transaction
txn, _ := index.Begin()
txn.Delete(nodeID)
txn.Commit()

// Save index to disk (checkpoint WAL)
if err := index.Flush(); err != nil {
    log.Fatal(err)
}

// Load from disk (includes WAL recovery)
index, err := hnsw.LoadHNSW("myindex.hnsw")
if err != nil {
    log.Fatal(err)
}
defer index.Close()

cursor := index.NewCursor()
defer cursor.Close()

for node := cursor.Next(); node != nil; node = cursor.Next() {
    fmt.Printf("Node %d: level=%d, value=%v\n",
        node.ID, node.Level, node.Value)
}

HNSW constructs a multi-layer graph where each layer is a proximity graph with decreasing density at higher layers. Search starts at the highest (sparsest) layer and descends to layer 0 (densest layer) for final refinement.

Nodes are assigned a random level using exponential decay:

P(level > L) = HNSW_P^L where HNSW_P = 0.25

This creates a skip-list-like structure:

• Layer 0: All nodes (densest connectivity)
• Layer 1: ~25% of nodes
• Layer 2: ~6.25% of nodes
• Etc.

Each node has up to M connections at higher layers and 2M connections at layer 0.

The search uses greedy best-first traversal:

1. Start at the entry point (highest level node)
2. For each layer from top to target:
   • Maintain a priority queue of candidates (ordered by distance)
   • Maintain a result set of best nodes found (size = ef)
   • Explore neighbors of closest unvisited candidate
   • Early termination: stop when closest candidate is farther than worst result
3. At layer 0, use larger ef value for final refinement
4. Return top k results

Visited tracking uses per-thread epochs to avoid clearing between searches:

• Each thread has a slot (0-127) with an epoch counter
• Nodes track visited epoch per thread slot
• Epoch increments before each search, invalidating old visits

Inserting a new node:

1. Normalize the vector (L2 norm = 1)
2. Quantize based on configuration (Q8 or binary)
3. Assign random level using exponential decay
4. Search from top layer to target level (ef=1) to find entry point
5. For each layer from target to 0:
   • Search with larger ef to find candidate neighbors
   • Select best neighbors using diversity-aware selection
   • Establish bidirectional links
6. Update entry point if new node has highest level

Neighbor selection balances link quality, diversity, and connectivity using a three-level aggressiveness strategy:

Level 0 (default):

• Diversity check: Only link if new neighbor isn't too close to existing neighbors
• Only replace links in full neighbors if dropped node remains well-connected (>M/2 links)
• Produces highest quality graph

Level 1 (moderate):

• Disables diversity checks
• Allows dropping nodes with >M/4 connections
• Used when new node has too few links after level 0

Level 2 (aggressive):

• When replacement would over-disconnect a node:
  • Searches for a better-connected node to drop instead
  • If none found, reallocates neighbor's link array to add capacity
• Used when new node has very few links (<M/4) after level 1

This ensures even poorly positioned nodes get adequate connectivity.

Deletion is true removal, not marking as deleted:

1. Remove all bidirectional links to the node
2. Remove from linked list and update entry point if necessary
3. Reconnect orphaned neighbors among themselves

The reconnection algorithm uses a scoring system:

score[i,j] = W1 * (2 - dist) + W2 * ((avg_i + avg_j) / 2)

Where:

• W1 = 0.7 (immediate quality weight)
• W2 = 0.3 (future potential weight)
• avg_i, avg_j = average distances to other candidates

This balances immediate connection quality with preserving good future pairing options. Nodes are greedily paired by best score. Unpaired nodes search the broader graph for connections.

All vectors are normalized on insert, then quantized:

Q8 (8-bit) Quantization:

• Finds max absolute value (range) in normalized vector
• Scales [-range, +range] to [-127, +127]
• Distance computed in integer domain, scaled once at end
• 4x memory reduction with minimal accuracy loss

Binary Quantization:

• Each dimension becomes 1 bit: positive (1) or negative/zero (0)
• Packed into uint64 words (64 dimensions per word)
• Distance via XOR + popcount (Hamming distance)
• 32x memory reduction with higher accuracy loss

Distance metrics normalized to [0, 2] range for consistency.

Read concurrency (up to 128 threads):

• Per-thread slot locks (lock-free fast path via TryLock)
• Single global read lock for index structure
• Per-thread epoch counters prevent visited-tracking conflicts
• Epoch incremented on slot reuse (>128 concurrent readers)

Write operations (inserts, deletes):

• Acquire global write lock
• All modifications atomic from reader perspective
• Increment version counter for optimistic concurrency (future use)

All modifications are logged to a WAL for crash recovery and durability:

1. Write operations create frames in WAL (logged after in-memory modification)
2. Commit frame written and fsynced to disk
3. Changes are now durable and survive crashes
4. Checkpoint merges WAL into main database files and truncates WAL

Important: The WAL provides crash recovery and durability, but in-memory modifications happen immediately. Uncommitted changes are visible to concurrent readers. This is not full ACID isolation. See ACID.md for details.

WAL structure:

• Header: Magic "HWAL", version, page size, checksums, salt values
• Frames: Sequential records with header + data + CRC64 checksum
• Transaction markers: FRAME_COMMIT or FRAME_ABORT flags

Frame types:

• PAGE_NODE: Node structure (ID, level, links)
• PAGE_VECTOR: Quantized vector data
• PAGE_META: Index metadata (entry point, max level)
• PAGE_FREELIST: Deleted node tracking

On LoadHNSW:

1. Load index structure from .meta and .vec files
2. Open and validate WAL file
3. Scan WAL to identify committed vs aborted transactions
4. Build map of WAL nodes (first pass)
5. Resolve link pointers between nodes (second pass)
6. Integrate WAL nodes into loaded index
7. Apply deletions (third pass)

Uncommitted transactions are automatically discarded.

What transactions provide:

• Durability: Committed changes survive crashes via WAL + fsync
• Crash Recovery: WAL replay restores committed transactions after restart
• Batching: Multiple operations in one transaction amortize fsync cost (10-50x faster)
• Single-operation Atomicity: Each Insert/Delete is atomic within the index structure

What transactions do NOT provide:

• Atomicity: In-memory modifications happen immediately, before WAL write
• Isolation: Uncommitted changes visible to concurrent readers immediately
• Rollback capability: Rollback only prevents WAL commit, doesn't undo in-memory changes
• Multi-operation atomicity: Partial transaction results may be visible mid-transaction

Use transactions for:

• Batch loading vectors (significant performance improvement)
• Ensuring committed writes survive crashes
• Grouping related operations for durability

Don't rely on transactions for:

• Hiding uncommitted changes from readers (not isolated)
• Rolling back failed operations (doesn't undo in-memory state)
• True ACID semantics (see ACID.md and ACID_PERFORMANCE_IMPACT.md for details)

Three files per index:

[Header]
  Magic:    "HNSW" (4 bytes)
  Version:  uint32 (4 bytes) - SerializationVersion = 2

[Index Metadata]
  VectorDim:     uint32 - Dimensionality of vectors
  M:             uint32 - Connections per node
  MaxLevel:      uint32 - Highest level in graph
  NodeCount:     uint64 - Total nodes
  LastID:        uint64 - Last assigned node ID
  QuantType:     uint32 - Quantization type (0=None, 1=Q8, 2=Bin)
  EntryPointID:  uint64 - Entry node ID (0 if nil)

[For each node]
  NodeID:        uint64 - Unique node identifier
  Level:         uint32 - Max level for this node
  QuantsRange:   float32 - Q8 quantization range
  L2Norm:        float32 - Original L2 norm
  VecSize:       uint32 - Vector length

  [For each layer 0..Level]
    NumLinks:    uint32 - Number of links at this layer
    LinkIDs:     []uint64 - Array of linked node IDs (NumLinks elements)

Sequential binary data for all quantized vectors:

For Q8 quantization:

[For each node]
  Vector: []int8 - One int8 per dimension

For Binary quantization:

[For each node]
  Vector: []uint64 - Packed bits, (dim+63)/64 words

[WAL Header] (36 bytes)
  Magic:    "HWAL" (4 bytes)
  Version:  uint32 - WAL format version = 1
  PageSize: uint32 - Page size in bytes (4096)
  Checksum: uint64 - Header CRC64
  Salt1:    uint32 - Random salt (changes on checkpoint)
  Salt2:    uint32 - Random salt (changes on checkpoint)
  Reserved: 8 bytes

[Frames - repeated]
  [Frame Header] (24 bytes)
    FrameNum:  uint64 - Sequential frame number
    TxnID:     uint64 - Transaction ID
    PageType:  uint8 - PAGE_NODE, PAGE_VECTOR, PAGE_META, PAGE_FREELIST
    Flags:     uint8 - FRAME_COMMIT, FRAME_ABORT
    PageSize:  uint32 - Size of page data
    Reserved:  2 bytes

  [Frame Data]
    Data:      []byte - Serialized node/vector/metadata (PageSize bytes)

  [Frame Checksum]
    Checksum:  uint64 - CRC64(Salt1 + Salt2 + FrameHeader + Data)

Frames are appended sequentially. Checksum includes salts to detect WAL/database mismatch. Incomplete frames at EOF are ignored during recovery.

WAL behavior controlled by WALConfig:

type WALConfig struct {
    WALEnabled        bool   // Enable WAL mode
    WALAutoCheckpoint int    // Checkpoint after N frames (default: 1000)
    WALSyncMode       string // "OFF", "NORMAL", "FULL" (default: "FULL")
    PageSize          int    // Page size in bytes (default: 4096)
    ChecksumEnabled   bool   // Verify checksums (default: true)
    FsyncEnabled      bool   // Call fsync on commit (default: true)
}

Time Complexity:

• Insert: O(log N) expected, O(N) worst case
• Search: O(log N) expected, O(N) worst case
• Delete: O(M * log N) expected

Space Complexity:

• Memory: O(N * M * D) where D is dimension
• With Q8: ~(M * sizeof(pointer) + D) bytes per node
• With Binary: ~(M * sizeof(pointer) + D/32) bytes per node

Tuning Parameters:

• M: Higher = better recall, more memory, slower inserts (8-64)
• ef_construction: Higher = better graph quality, slower inserts (100-400)
• ef_search: Higher = better recall, slower search (50-200)

// Get index statistics
stats := index.Stats()
fmt.Printf("Nodes: %d, MaxLevel: %d, AvgConnections: %.2f\n",
    stats.NodeCount, stats.MaxLevel, stats.AvgConnections)

// Validate graph structure (checks bidirectional links)
if err := index.Validate(); err != nil {
    log.Printf("Validation failed: %v", err)
}

1. Vector dimensionality must be specified at creation and cannot change
2. Maximum 128 concurrent readers (additional readers will block)
3. QuantNone (no quantization) is not implemented
4. No built-in support for filtered searches
5. No support for vector updates (must delete + reinsert)

Based on the paper: "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs" by Yu. A. Malkov and D. A. Yashunin IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018