Scaling HNSWs (antirez.com)

Redis core developer summarizes advanced lessons from implementing HNSW (Hierarchical Navigable Small World) graphs as a first-class Redis Vector Set. Rather than an intro, the post focuses on practical scaling: memory is the main bottleneck (many neighbor pointers, multiple levels, and high‑dim float vectors), so the author adopted per-vector 8‑bit quantization (scale each vector by its max absolute component, map to signed int8 −127..127). This yields ~4× vector size reduction and similar recall in real workloads; dot products are accumulated in int32 and rescaled by (range_a/127)*(range_b/127). Binary quantization is also supported for inherently binary data, while full precision remains optional for cases needing it. On speed and concurrency, the implementation is fully threaded: read-heavy greedy searches are parallelized and writes are split into a read-candidate phase and a short commit phase with locks to allow concurrent inserts safely. To avoid revisiting nodes without global hash sets, each node stores an array visited_epoch[HNSW_MAX_THREADS], one epoch counter per thread — a deliberate space/time tradeoff. The author enforces bidirectional links to enable correct deletions and memory reclamation (addressing a common gap in HNSW implementations) and considers pointer compression for future work. Result: production Redis Vector Sets achieve ~50k ops/sec on real workloads, and the write-up urges ML/DS researchers to explore HNSW variants (flat layers, level selection tweaks) beyond the original paper’s design.