#![forbid(unsafe_code)]
use crate::error::{Error, Result};
use crate::traits::VectorIndexEngine;
use crate::vector::{DistanceMetric, QuantizedVector8, cosine_distance, euclidean_distance};
use parking_lot::{Mutex, RwLock};
use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque};
use std::sync::Arc;
#[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)]
pub struct PagedNodeRecord {
pub id: u64,
pub vector: Vec<f32>,
pub quantized: Option<QuantizedVector8>,
pub neighbors_l0: Vec<u64>,
}
impl PagedNodeRecord {
pub fn to_bytes(&self) -> Result<Vec<u8>> {
serde_json::to_vec(self).map_err(|e| Error::Serialization(e.to_string()))
}
pub fn from_bytes(bytes: &[u8]) -> Result<Self> {
serde_json::from_slice(bytes).map_err(|e| Error::Serialization(e.to_string()))
}
}
#[derive(Debug, Default)]
struct LruState {
cache: HashMap<u64, PagedNodeRecord>,
lru_queue: VecDeque<u64>,
}
impl LruState {
fn touch(&mut self, id: u64) {
if let Some(pos) = self.lru_queue.iter().position(|&x| x == id) {
self.lru_queue.remove(pos);
}
self.lru_queue.push_back(id);
}
fn insert_cache(&mut self, id: u64, record: PagedNodeRecord, capacity: usize) {
if self.cache.len() >= capacity {
if let Some(evicted_id) = self.lru_queue.pop_front() {
self.cache.remove(&evicted_id);
}
}
self.cache.insert(id, record);
self.lru_queue.push_back(id);
}
}
#[derive(Debug, Clone)]
pub struct PagedVectorStore {
lru: Arc<Mutex<LruState>>,
capacity: usize,
disk_pages: Arc<RwLock<HashMap<u64, Vec<u8>>>>,
}
impl PagedVectorStore {
pub fn new(capacity: usize) -> Self {
Self {
lru: Arc::new(Mutex::new(LruState::default())),
capacity: capacity.max(16),
disk_pages: Arc::new(RwLock::new(HashMap::new())),
}
}
pub fn get(&self, id: u64) -> Option<PagedNodeRecord> {
{
let mut lru = self.lru.lock();
if let Some(rec) = lru.cache.get(&id) {
let rec = rec.clone();
lru.touch(id);
return Some(rec);
}
}
let disk_opt = self.disk_pages.read().get(&id).cloned();
if let Some(bytes) = disk_opt {
if let Ok(rec) = PagedNodeRecord::from_bytes(&bytes) {
let mut lru = self.lru.lock();
lru.insert_cache(id, rec.clone(), self.capacity);
return Some(rec);
}
}
None
}
pub fn put(&self, record: PagedNodeRecord) -> Result<()> {
let id = record.id;
let bytes = record.to_bytes()?;
self.disk_pages.write().insert(id, bytes);
self.lru.lock().insert_cache(id, record, self.capacity);
Ok(())
}
pub fn remove(&self, id: u64) {
self.lru.lock().cache.remove(&id);
self.disk_pages.write().remove(&id);
}
pub fn len(&self) -> usize {
self.disk_pages.read().len()
}
pub fn is_empty(&self) -> bool {
self.disk_pages.read().is_empty()
}
pub fn has_node(&self, id: u64) -> bool {
if self.lru.lock().cache.contains_key(&id) {
return true;
}
self.disk_pages.read().contains_key(&id)
}
pub fn dump_pages(&self) -> Vec<(u64, Vec<u8>)> {
self.disk_pages
.read()
.iter()
.map(|(&k, v)| (k, v.clone()))
.collect()
}
pub fn load_page(&self, id: u64, bytes: Vec<u8>) {
self.disk_pages.write().insert(id, bytes);
}
}
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct PagedHnswHeader {
pub dimensions: usize,
pub metric: DistanceMetric,
pub m: usize,
pub m0: usize,
pub ef_construction: usize,
pub ef_search: usize,
pub entry_point: Option<u64>,
pub max_level: usize,
pub ml: f64,
pub upper_layers: HashMap<u64, Vec<Vec<u64>>>,
pub count: usize,
}
#[derive(Debug, Clone)]
pub struct PagedHnswIndex {
pub dimensions: usize,
pub metric: DistanceMetric,
pub m: usize,
pub m0: usize,
pub ef_construction: usize,
pub ef_search: usize,
pub entry_point: Option<u64>,
pub max_level: usize,
pub ml: f64,
pub upper_layers: HashMap<u64, Vec<Vec<u64>>>,
pub store: PagedVectorStore,
rng_state: u64,
}
impl PagedHnswIndex {
pub fn export_header(&self) -> PagedHnswHeader {
PagedHnswHeader {
dimensions: self.dimensions,
metric: self.metric,
m: self.m,
m0: self.m0,
ef_construction: self.ef_construction,
ef_search: self.ef_search,
entry_point: self.entry_point,
max_level: self.max_level,
ml: self.ml,
upper_layers: self.upper_layers.clone(),
count: self.len(),
}
}
pub fn import_header(header: PagedHnswHeader, store: PagedVectorStore) -> Self {
Self {
dimensions: header.dimensions,
metric: header.metric,
m: header.m,
m0: header.m0,
ef_construction: header.ef_construction,
ef_search: header.ef_search,
entry_point: header.entry_point,
max_level: header.max_level,
ml: header.ml,
upper_layers: header.upper_layers,
store,
rng_state: 0x9e3779b97f4a7c15,
}
}
pub fn new(dimensions: usize, metric: DistanceMetric, cache_capacity: usize) -> Self {
let m = 16;
let m0 = 32;
let ef_construction = 64;
let ef_search = 32;
let ml = 1.0 / (m as f64).ln();
Self {
dimensions,
metric,
m,
m0,
ef_construction,
ef_search,
entry_point: None,
max_level: 0,
ml,
upper_layers: HashMap::new(),
store: PagedVectorStore::new(cache_capacity),
rng_state: 0x9e3779b97f4a7c15,
}
}
fn next_random_f64(&mut self) -> f64 {
self.rng_state = self
.rng_state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
let x = self.rng_state >> 11;
(x as f64) / ((1u64 << 53) as f64)
}
fn random_level(&mut self) -> usize {
let r = self.next_random_f64().max(1e-9);
((-r.ln() * self.ml) as usize).min(16)
}
fn distance(&self, a: &[f32], b: &[f32]) -> f32 {
match self.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();
-dot
}
}
}
pub fn insert(&mut self, id: u64, vector: Vec<f32>) -> Result<()> {
if vector.len() != self.dimensions {
return Err(Error::DimensionMismatch(self.dimensions, vector.len()));
}
let level = self.random_level();
if self.entry_point.is_none() {
let record = PagedNodeRecord {
id,
vector,
quantized: None,
neighbors_l0: Vec::new(),
};
self.store.put(record)?;
self.entry_point = Some(id);
self.max_level = level;
if level > 0 {
self.upper_layers.insert(id, vec![Vec::new(); level]);
}
return Ok(());
}
let entry = self.entry_point.ok_or_else(|| {
Error::Corrupted(
"HNSW entry_point is None during insert — index state is corrupted".into(),
)
})?;
let mut curr_obj = entry;
if self.max_level > level {
for lc in (level + 1..=self.max_level).rev() {
let mut changed = true;
while changed {
changed = false;
let curr_vec = self
.store
.get(curr_obj)
.map(|n| n.vector)
.unwrap_or_default();
let mut curr_dist = self.distance(&vector, &curr_vec);
let upper_neighbors = self
.upper_layers
.get(&curr_obj)
.and_then(|layers| layers.get(lc - 1))
.cloned()
.unwrap_or_default();
for neighbor_id in upper_neighbors {
if let Some(neighbor) = self.store.get(neighbor_id) {
let dist = self.distance(&vector, &neighbor.vector);
if dist < curr_dist {
curr_dist = dist;
curr_obj = neighbor_id;
changed = true;
}
}
}
}
}
}
let mut neighbors_l0 = Vec::new();
if let Some(entry_node) = self.store.get(curr_obj) {
let mut candidates = Vec::new();
candidates.push((curr_obj, self.distance(&vector, &entry_node.vector)));
for &n_id in &entry_node.neighbors_l0 {
if let Some(n) = self.store.get(n_id) {
candidates.push((n_id, self.distance(&vector, &n.vector)));
}
}
candidates.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal));
neighbors_l0 = candidates.into_iter().take(self.m0).map(|c| c.0).collect();
}
for &n_id in &neighbors_l0 {
if let Some(mut neighbor) = self.store.get(n_id) {
if !neighbor.neighbors_l0.contains(&id) {
neighbor.neighbors_l0.push(id);
if neighbor.neighbors_l0.len() > self.m0 {
neighbor.neighbors_l0.truncate(self.m0);
}
self.store.put(neighbor)?;
}
}
}
let record = PagedNodeRecord {
id,
vector,
quantized: None,
neighbors_l0,
};
self.store.put(record)?;
if level > 0 {
self.upper_layers.insert(id, vec![Vec::new(); level]);
}
if level > self.max_level {
self.max_level = level;
self.entry_point = Some(id);
}
Ok(())
}
pub fn search(&self, query: &[f32], top_k: usize) -> Result<Vec<(u64, f32)>> {
if query.len() != self.dimensions {
return Err(Error::DimensionMismatch(self.dimensions, query.len()));
}
let entry = match self.entry_point {
Some(ep) => ep,
None => return Ok(Vec::new()),
};
let mut curr_obj = entry;
for lc in (1..=self.max_level).rev() {
let mut changed = true;
while changed {
changed = false;
let curr_vec = self
.store
.get(curr_obj)
.map(|n| n.vector)
.unwrap_or_default();
let mut curr_dist = self.distance(query, &curr_vec);
let upper_neighbors = self
.upper_layers
.get(&curr_obj)
.and_then(|layers| layers.get(lc - 1))
.cloned()
.unwrap_or_default();
for neighbor_id in upper_neighbors {
if let Some(neighbor) = self.store.get(neighbor_id) {
let dist = self.distance(query, &neighbor.vector);
if dist < curr_dist {
curr_dist = dist;
curr_obj = neighbor_id;
changed = true;
}
}
}
}
}
let mut visited = HashSet::new();
let mut candidates = BinaryHeap::new();
let mut top_candidates = BinaryHeap::new();
if let Some(entry_node) = self.store.get(curr_obj) {
let dist = self.distance(query, &entry_node.vector);
visited.insert(curr_obj);
candidates.push(MinCandidate {
id: curr_obj,
distance: dist,
});
top_candidates.push(MaxCandidate {
id: curr_obj,
distance: dist,
});
}
while let Some(candidate) = candidates.pop() {
let furthest_dist = top_candidates
.peek()
.map(|c| c.distance)
.unwrap_or(f32::MAX);
if candidate.distance > furthest_dist && top_candidates.len() >= self.ef_search {
break;
}
let neighbors = self
.store
.get(candidate.id)
.map(|n| n.neighbors_l0)
.unwrap_or_default();
for neighbor_id in neighbors {
if visited.insert(neighbor_id) {
if let Some(neighbor) = self.store.get(neighbor_id) {
let dist = self.distance(query, &neighbor.vector);
if dist < furthest_dist || top_candidates.len() < self.ef_search {
candidates.push(MinCandidate {
id: neighbor_id,
distance: dist,
});
top_candidates.push(MaxCandidate {
id: neighbor_id,
distance: dist,
});
if top_candidates.len() > self.ef_search {
top_candidates.pop();
}
}
}
}
}
}
let mut results: Vec<(u64, f32)> = top_candidates
.into_iter()
.map(|c| (c.id, c.distance))
.collect();
results.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal));
results.truncate(top_k);
Ok(results)
}
pub fn len(&self) -> usize {
self.store.len()
}
pub fn is_empty(&self) -> bool {
self.store.is_empty()
}
pub fn remove(&mut self, id: u64) -> Result<bool> {
self.store.remove(id);
self.upper_layers.remove(&id);
Ok(true)
}
}
impl VectorIndexEngine for PagedHnswIndex {
fn insert_vector(&mut self, id: u64, vector: &[f32]) -> Result<()> {
self.insert(id, vector.to_vec())
}
fn search_knn(
&self,
query: &[f32],
k: usize,
_metric: DistanceMetric,
) -> Result<Vec<(u64, f32)>> {
self.search(query, k)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_paged_hnsw_basic() {
let mut index = PagedHnswIndex::new(4, DistanceMetric::Cosine, 32);
index.insert(1, vec![1.0, 0.0, 0.0, 0.0]).unwrap();
index.insert(2, vec![0.0, 1.0, 0.0, 0.0]).unwrap();
index.insert(3, vec![0.9, 0.1, 0.0, 0.0]).unwrap();
assert_eq!(index.len(), 3);
let results = index.search(&[1.0, 0.0, 0.0, 0.0], 2).unwrap();
assert_eq!(results.len(), 2);
assert_eq!(results[0].0, 1);
assert_eq!(results[1].0, 3);
}
}