use crate::error::{Error, Result};
use crate::traits::VectorIndexEngine;
use crate::vector::{DistanceMetric, cosine_distance, euclidean_distance};
use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashSet};
#[derive(Debug, Clone, PartialEq)]
struct MinCandidate {
id: u64,
distance: f32,
}
impl Eq for MinCandidate {}
impl Ord for MinCandidate {
fn cmp(&self, other: &Self) -> Ordering {
other
.distance
.partial_cmp(&self.distance)
.unwrap_or(Ordering::Equal)
}
}
impl PartialOrd for MinCandidate {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
#[derive(Debug, Clone, PartialEq)]
struct MaxCandidate {
id: u64,
distance: f32,
}
impl Eq for MaxCandidate {}
impl Ord for MaxCandidate {
fn cmp(&self, other: &Self) -> Ordering {
self.distance
.partial_cmp(&other.distance)
.unwrap_or(Ordering::Equal)
}
}
impl PartialOrd for MaxCandidate {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize, PartialEq)]
pub struct HnswConfig {
pub m: usize,
pub m0: usize,
pub ef_construction: usize,
pub ef_search: usize,
pub quantize_sq8: bool,
}
impl Default for HnswConfig {
fn default() -> Self {
Self {
m: 16,
m0: 32,
ef_construction: 64,
ef_search: 32,
quantize_sq8: false,
}
}
}
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct HnswNode {
pub id: u64,
pub vector: Vec<f32>,
pub top_layer: usize,
pub layer_neighbors: Vec<Vec<u64>>,
#[serde(default)]
pub quantized: Option<crate::vector::QuantizedVector8>,
}
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct HnswSnapshot {
pub dimensions: usize,
pub metric: DistanceMetric,
pub config: HnswConfig,
pub entry_point: Option<u64>,
pub max_level: usize,
pub nodes: Vec<HnswNode>,
pub tombstones: Vec<u64>,
}
#[derive(Debug, Clone)]
pub struct HnswIndex {
pub dimensions: usize,
pub metric: DistanceMetric,
pub m: usize,
pub m0: usize,
pub ef_construction: usize,
pub ef_search: usize,
pub config: HnswConfig,
pub entry_point: Option<u64>,
pub max_level: usize,
pub ml: f64,
pub nodes: std::collections::HashMap<u64, HnswNode>,
pub tombstones: HashSet<u64>,
pub rng_state: u64,
}
impl HnswIndex {
pub fn new(dimensions: usize, metric: DistanceMetric) -> Self {
let seed = web_time::SystemTime::now()
.duration_since(web_time::UNIX_EPOCH)
.map(|d| d.as_nanos() as u64)
.unwrap_or(0x9e3779b97f4a7c15);
Self::with_config_and_seed(dimensions, metric, HnswConfig::default(), seed)
}
pub fn with_seed(dimensions: usize, metric: DistanceMetric, seed: u64) -> Self {
Self::with_config_and_seed(dimensions, metric, HnswConfig::default(), seed)
}
pub fn with_config(dimensions: usize, metric: DistanceMetric, config: HnswConfig) -> Self {
let seed = web_time::SystemTime::now()
.duration_since(web_time::UNIX_EPOCH)
.map(|d| d.as_nanos() as u64)
.unwrap_or(0x9e3779b97f4a7c15);
Self::with_config_and_seed(dimensions, metric, config, seed)
}
pub fn with_config_and_seed(
dimensions: usize,
metric: DistanceMetric,
config: HnswConfig,
seed: u64,
) -> Self {
let m = config.m.max(2);
let m0 = config.m0.max(2);
let ef_construction = config.ef_construction.max(m);
let ef_search = config.ef_search.max(1);
let ml = 1.0 / (m as f64).ln();
Self {
dimensions,
metric,
m,
m0,
ef_construction,
ef_search,
config,
entry_point: None,
max_level: 0,
ml,
nodes: std::collections::HashMap::new(),
tombstones: HashSet::new(),
rng_state: if seed == 0 { 0xdeadbeefcafebabe } else { seed },
}
}
pub fn with_params(
dimensions: usize,
metric: DistanceMetric,
m: usize,
ef_construction: usize,
ef_search: usize,
quantize_sq8: bool,
) -> Self {
let config = HnswConfig {
m,
m0: m * 2,
ef_construction,
ef_search,
quantize_sq8,
};
Self::with_config(dimensions, metric, config)
}
pub fn export_snapshot(&self) -> HnswSnapshot {
HnswSnapshot {
dimensions: self.dimensions,
metric: self.metric,
config: self.config.clone(),
entry_point: self.entry_point,
max_level: self.max_level,
nodes: self.nodes.values().cloned().collect(),
tombstones: self.tombstones.iter().copied().collect(),
}
}
pub fn import_snapshot(snapshot: HnswSnapshot) -> Self {
let m = snapshot.config.m.max(2);
let m0 = snapshot.config.m0.max(2);
let ml = 1.0 / (m as f64).ln();
let mut nodes = std::collections::HashMap::new();
for node in snapshot.nodes {
nodes.insert(node.id, node);
}
let tombstones = snapshot.tombstones.into_iter().collect();
Self {
dimensions: snapshot.dimensions,
metric: snapshot.metric,
m,
m0,
ef_construction: snapshot.config.ef_construction,
ef_search: snapshot.config.ef_search,
config: snapshot.config,
entry_point: snapshot.entry_point,
max_level: snapshot.max_level,
ml,
nodes,
tombstones,
rng_state: 0xdeadbeefcafebabe,
}
}
#[inline]
pub fn compute_node_distance(
&self,
query: &[f32],
node: &HnswNode,
metric: DistanceMetric,
) -> f32 {
if let Some(ref q) = node.quantized {
match metric {
DistanceMetric::Cosine => q.asymmetric_cosine_distance(query),
DistanceMetric::Euclidean => q.asymmetric_l2_distance_squared(query).sqrt(),
DistanceMetric::DotProduct => {
let dot = q.asymmetric_dot_product(query);
if dot.is_finite() { -dot } else { f32::MAX }
}
}
} else {
self.distance_with_metric(query, &node.vector, metric)
}
}
#[inline]
pub fn distance(&self, a: &[f32], b: &[f32]) -> f32 {
self.distance_with_metric(a, b, self.metric)
}
#[inline]
pub fn distance_with_metric(&self, a: &[f32], b: &[f32], metric: DistanceMetric) -> f32 {
match metric {
DistanceMetric::Cosine => cosine_distance(a, b),
DistanceMetric::Euclidean => euclidean_distance(a, b),
DistanceMetric::DotProduct => {
let dot: f32 = a.iter().zip(b.iter()).map(|(x, y)| x * y).sum();
if dot.is_finite() { -dot } else { f32::MAX }
}
}
}
pub fn len(&self) -> usize {
self.nodes.len().saturating_sub(self.tombstones.len())
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn mark_deleted(&mut self, id: u64) -> bool {
if self.nodes.contains_key(&id) {
self.tombstones.insert(id)
} else {
false
}
}
pub fn is_deleted(&self, id: u64) -> bool {
self.tombstones.contains(&id)
}
pub fn rebuild(&mut self) -> Result<usize> {
let removed = self.tombstones.len();
let config = HnswConfig {
m: self.m,
m0: self.m0,
ef_construction: self.ef_construction,
ef_search: self.ef_search,
..self.config.clone()
};
let mut rebuilt =
Self::with_config_and_seed(self.dimensions, self.metric, config, self.rng_state);
let mut active: Vec<_> = self
.nodes
.values()
.filter(|node| !self.tombstones.contains(&node.id))
.collect();
active.sort_by_key(|node| node.id);
for node in active {
rebuilt.insert_vector(node.id, &node.vector)?;
}
*self = rebuilt;
Ok(removed)
}
pub fn vacuum(&mut self) -> usize {
if self.tombstones.is_empty() {
return 0;
}
self.rebuild().unwrap_or(0)
}
pub fn remove_vector(&mut self, id: u64) -> bool {
if self.nodes.remove(&id).is_some() {
self.tombstones.remove(&id);
for node in self.nodes.values_mut() {
for neighbors in node.layer_neighbors.iter_mut() {
neighbors.retain(|&nid| nid != id);
}
}
if self.entry_point == Some(id) {
let mut best_ep = None;
let mut best_level = 0;
for (&nid, node) in &self.nodes {
if best_ep.is_none() || node.top_layer > best_level {
best_ep = Some(nid);
best_level = node.top_layer;
}
}
self.entry_point = best_ep;
self.max_level = best_level;
}
true
} else {
false
}
}
pub fn next_random_f64(&mut self) -> f64 {
self.rng_state = self.rng_state.wrapping_add(0x9e3779b97f4a7c15);
let mut z = self.rng_state;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
let r = z ^ (z >> 31);
let val = (r as f64) / (u64::MAX as f64);
val.clamp(0.0000001, 0.9999999)
}
fn random_level(&mut self) -> usize {
let rand_val = self.next_random_f64();
let level = (-rand_val.ln() * self.ml).floor() as usize;
level.min(16)
}
fn search_layer(
&self,
query: &[f32],
entry_points: &[u64],
ef: usize,
layer: usize,
) -> Vec<(u64, f32)> {
self.search_layer_with_metric(query, entry_points, ef, layer, self.metric)
}
fn search_layer_with_metric(
&self,
query: &[f32],
entry_points: &[u64],
ef: usize,
layer: usize,
metric: DistanceMetric,
) -> Vec<(u64, f32)> {
let mut visited: HashSet<u64> = entry_points.iter().copied().collect();
let mut candidates = BinaryHeap::new(); let mut nearest = BinaryHeap::new();
for &ep in entry_points {
if let Some(node) = self.nodes.get(&ep) {
let dist = self.compute_node_distance(query, node, metric);
candidates.push(MinCandidate {
id: ep,
distance: dist,
});
nearest.push(MaxCandidate {
id: ep,
distance: dist,
});
}
}
while let Some(curr) = candidates.pop() {
let furthest_dist = nearest.peek().map(|c| c.distance).unwrap_or(f32::MAX);
if curr.distance > furthest_dist && nearest.len() >= ef {
break;
}
if let Some(node) = self.nodes.get(&curr.id)
&& layer < node.layer_neighbors.len()
{
for &neighbor_id in &node.layer_neighbors[layer] {
if visited.insert(neighbor_id)
&& let Some(neighbor) = self.nodes.get(&neighbor_id)
{
let dist = self.compute_node_distance(query, neighbor, metric);
if dist < furthest_dist || nearest.len() < ef {
candidates.push(MinCandidate {
id: neighbor_id,
distance: dist,
});
nearest.push(MaxCandidate {
id: neighbor_id,
distance: dist,
});
if nearest.len() > ef {
nearest.pop(); }
}
}
}
}
}
let mut sorted: Vec<(u64, f32)> = nearest.into_iter().map(|c| (c.id, c.distance)).collect();
sorted.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal));
sorted
}
fn diverse_neighbors(
&self,
candidates: &[(u64, f32)],
limit: usize,
inserted: Option<(u64, &[f32])>,
) -> Vec<u64> {
if candidates.len() <= limit {
return candidates.iter().map(|(id, _)| *id).collect();
}
let vector = |id: u64| -> Option<&[f32]> {
if let Some((new_id, new_vector)) = inserted
&& new_id == id
{
return Some(new_vector);
}
self.nodes.get(&id).map(|node| node.vector.as_slice())
};
let mut selected = Vec::with_capacity(limit);
let mut pruned = Vec::new();
for &(id, anchor_distance) in candidates {
let Some(candidate) = vector(id) else {
continue;
};
let redundant = selected.iter().any(|neighbor| {
vector(*neighbor)
.is_some_and(|other| self.distance(candidate, other) < anchor_distance)
});
if !redundant {
selected.push(id);
if selected.len() == limit {
break;
}
} else {
pruned.push(id);
}
}
selected.extend(pruned.into_iter().take(limit - selected.len()));
selected
}
pub fn search_knn_filtered(
&self,
query: &[f32],
k: usize,
metric: DistanceMetric,
filter: Option<&std::collections::HashSet<u64>>,
) -> Result<Vec<(u64, f32)>> {
self.search_knn_where(
query,
k,
metric,
(filter, false),
|_| true,
self.nodes.len(),
)
}
pub(crate) fn search_knn_where(
&self,
query: &[f32],
k: usize,
metric: DistanceMetric,
filter_options: (Option<&HashSet<u64>>, bool),
accept: impl Fn(u64) -> bool,
max_ef: usize,
) -> Result<Vec<(u64, f32)>> {
let (filter, filter_active) = filter_options;
if query.len() != self.dimensions {
return Err(Error::DimensionMismatch(self.dimensions, query.len()));
}
if query.iter().any(|value| !value.is_finite()) {
return Err(Error::ConstraintViolation(
"Query vector components must be finite".into(),
));
}
if k == 0 || self.nodes.is_empty() {
return Ok(Vec::new());
}
if let Some(allowed) = filter
&& allowed.len() <= self.ef_search.max(k)
{
let mut matches: Vec<_> = allowed
.iter()
.filter(|id| !self.tombstones.contains(id))
.filter(|id| accept(**id))
.filter_map(|id| {
self.nodes
.get(id)
.map(|node| (*id, self.compute_node_distance(query, node, metric)))
})
.collect();
matches.sort_by(|a, b| a.1.total_cmp(&b.1).then_with(|| a.0.cmp(&b.0)));
matches.truncate(k);
return Ok(matches);
}
let mut curr_entry = match self.entry_point {
Some(ep) => ep,
None => return Ok(Vec::new()),
};
for l in (1..=self.max_level).rev() {
let mut changed = true;
while changed {
changed = false;
if let Some(curr_node) = self.nodes.get(&curr_entry) {
let curr_dist = self.compute_node_distance(query, curr_node, metric);
if l < curr_node.layer_neighbors.len() {
for &neighbor_id in &curr_node.layer_neighbors[l] {
if let Some(neighbor) = self.nodes.get(&neighbor_id) {
let dist = self.compute_node_distance(query, neighbor, metric);
if dist < curr_dist {
curr_entry = neighbor_id;
changed = true;
break;
}
}
}
}
}
}
}
let ef_multiplier = if filter.is_some() || filter_active {
4
} else {
1
};
let ef_cap = max_ef.max(k).min(self.nodes.len());
let mut ef = self
.ef_search
.max(k)
.saturating_mul(ef_multiplier)
.min(ef_cap);
loop {
let candidates = self.search_layer_with_metric(query, &[curr_entry], ef, 0, metric);
let results: Vec<_> = candidates
.into_iter()
.filter(|(id, _)| {
!self.tombstones.contains(id)
&& filter.is_none_or(|allowed| allowed.contains(id))
&& accept(*id)
})
.take(k)
.collect();
if results.len() >= k.min(self.len()) || ef >= ef_cap {
return Ok(results);
}
ef = ef.saturating_mul(2).min(ef_cap);
}
}
pub fn search_knn(
&self,
query: &[f32],
k: usize,
metric: DistanceMetric,
) -> Result<Vec<(u64, f32)>> {
self.search_knn_filtered(query, k, metric, None)
}
}
impl VectorIndexEngine for HnswIndex {
fn insert_vector(&mut self, id: u64, vector: &[f32]) -> Result<()> {
if vector.len() != self.dimensions {
return Err(Error::DimensionMismatch(self.dimensions, vector.len()));
}
if vector.iter().any(|value| !value.is_finite()) {
return Err(Error::ConstraintViolation(
"Vector components must be finite".into(),
));
}
if self.nodes.contains_key(&id) {
self.remove_vector(id);
}
let node_level = self.random_level();
let mut layer_neighbors = vec![Vec::new(); node_level + 1];
if let Some(mut curr_entry) = self.entry_point {
let curr_max_level = self.max_level;
if curr_max_level > node_level {
for l in (node_level + 1..=curr_max_level).rev() {
let mut changed = true;
while changed {
changed = false;
if let Some(curr_node) = self.nodes.get(&curr_entry) {
let curr_dist =
self.compute_node_distance(vector, curr_node, self.metric);
if l < curr_node.layer_neighbors.len() {
for &neighbor_id in &curr_node.layer_neighbors[l] {
if let Some(neighbor) = self.nodes.get(&neighbor_id) {
let dist = self.compute_node_distance(
vector,
neighbor,
self.metric,
);
if dist < curr_dist {
curr_entry = neighbor_id;
changed = true;
break;
}
}
}
}
}
}
}
}
let mut ep = vec![curr_entry];
for l in (0..=node_level.min(curr_max_level)).rev() {
let candidates = self.search_layer(vector, &ep, self.ef_construction, l);
let max_neighbors = if l == 0 { self.m0 } else { self.m };
let neighbor_ids = self.diverse_neighbors(&candidates, max_neighbors, None);
layer_neighbors[l] = neighbor_ids.clone();
for &nid in &neighbor_ids {
let Some(neighbor_node) = self.nodes.get(&nid) else {
continue;
};
if l >= neighbor_node.layer_neighbors.len() {
continue;
}
let mut connections = neighbor_node.layer_neighbors[l].clone();
connections.push(id);
if connections.len() > max_neighbors {
let anchor = &neighbor_node.vector;
let mut ranked: Vec<_> = connections
.into_iter()
.filter_map(|candidate| {
let candidate_vector = if candidate == id {
vector
} else {
&self.nodes.get(&candidate)?.vector
};
Some((candidate, self.distance(anchor, candidate_vector)))
})
.collect();
ranked.sort_by(|a, b| a.1.total_cmp(&b.1).then_with(|| a.0.cmp(&b.0)));
connections =
self.diverse_neighbors(&ranked, max_neighbors, Some((id, vector)));
}
self.nodes
.get_mut(&nid)
.expect("existing neighbor")
.layer_neighbors[l] = connections;
}
ep = candidates
.into_iter()
.map(|(candidate, _)| candidate)
.collect();
}
if node_level > self.max_level {
self.max_level = node_level;
self.entry_point = Some(id);
}
} else {
self.entry_point = Some(id);
self.max_level = node_level;
}
let quantized = if self.config.quantize_sq8 {
Some(crate::vector::QuantizedVector8::quantize(vector))
} else {
None
};
let node = HnswNode {
id,
vector: vector.to_vec(),
top_layer: node_level,
layer_neighbors,
quantized,
};
self.nodes.insert(id, node);
Ok(())
}
fn search_knn(
&self,
query: &[f32],
k: usize,
metric: DistanceMetric,
) -> Result<Vec<(u64, f32)>> {
self.search_knn_filtered(query, k, metric, None)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_hnsw_knn_search() {
let mut index = HnswIndex::new(3, DistanceMetric::Cosine);
let v1 = vec![1.0, 0.0, 0.0];
let v2 = vec![0.0, 1.0, 0.0];
let v3 = vec![0.0, 0.0, 1.0];
let v4 = vec![0.95, 0.05, 0.0];
index.insert_vector(1, &v1).expect("Insert v1");
index.insert_vector(2, &v2).expect("Insert v2");
index.insert_vector(3, &v3).expect("Insert v3");
index.insert_vector(4, &v4).expect("Insert v4");
assert_eq!(index.len(), 4);
let query = vec![0.98, 0.02, 0.0];
let neighbors = index
.search_knn(&query, 2, DistanceMetric::Cosine)
.expect("KNN search");
assert_eq!(neighbors.len(), 2);
let top_ids: Vec<u64> = neighbors.iter().map(|(id, _)| *id).collect();
assert!(
top_ids.contains(&1) && top_ids.contains(&4),
"Expected [1, 4] in top 2, got {:?}",
top_ids
);
}
#[test]
fn test_hnsw_tombstone_and_vacuum() {
let mut index = HnswIndex::new(3, DistanceMetric::Cosine);
let v1 = vec![1.0, 0.0, 0.0];
let v2 = vec![0.98, 0.02, 0.0];
let v3 = vec![0.0, 1.0, 0.0];
index.insert_vector(1, &v1).expect("Insert v1");
index.insert_vector(2, &v2).expect("Insert v2");
index.insert_vector(3, &v3).expect("Insert v3");
assert_eq!(index.len(), 3);
assert!(index.mark_deleted(1));
assert!(index.is_deleted(1));
assert_eq!(index.len(), 2);
let query = vec![1.0, 0.0, 0.0];
let results = index
.search_knn(&query, 2, DistanceMetric::Cosine)
.expect("KNN search");
assert_eq!(results[0].0, 2); assert!(!results.iter().any(|(id, _)| *id == 1));
let purged = index.vacuum();
assert_eq!(purged, 1);
assert_eq!(index.len(), 2);
assert!(!index.nodes.contains_key(&1));
}
#[test]
fn test_hnsw_random_level_logarithmic_distribution() {
let mut index = HnswIndex::with_seed(3, DistanceMetric::Cosine, 42);
let mut level_counts = [0usize; 17];
for _ in 0..1000 {
let level = index.random_level();
assert!(level <= 16);
level_counts[level] += 1;
}
assert!(level_counts[0] > level_counts[1], "Level 0 must dominate");
assert!(level_counts[1] >= level_counts[2]);
let higher_levels: usize = level_counts[3..].iter().sum();
assert!(higher_levels < level_counts[0]);
}
}