#![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};
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>,
}
const PAGED_NODE_MAGIC: &[u8; 4] = b"PHN1";
impl PagedNodeRecord {
pub fn to_bytes(&self) -> Result<Vec<u8>> {
let mut out = Vec::with_capacity(
24 + self.vector.len() * 4
+ self
.quantized
.as_ref()
.map_or(0, |q| 16 + q.quantized.len())
+ self.neighbors_l0.len() * 8,
);
out.extend_from_slice(PAGED_NODE_MAGIC);
out.extend_from_slice(&self.id.to_le_bytes());
out.extend_from_slice(&(self.vector.len() as u32).to_le_bytes());
for &v in &self.vector {
out.extend_from_slice(&v.to_le_bytes());
}
match &self.quantized {
Some(q) => {
out.push(1);
out.extend_from_slice(&q.min_val.to_le_bytes());
out.extend_from_slice(&q.max_val.to_le_bytes());
out.extend_from_slice(&q.step.to_le_bytes());
out.extend_from_slice(&(q.quantized.len() as u32).to_le_bytes());
out.extend_from_slice(&q.quantized);
}
None => out.push(0),
}
out.extend_from_slice(&(self.neighbors_l0.len() as u32).to_le_bytes());
for &n in &self.neighbors_l0 {
out.extend_from_slice(&n.to_le_bytes());
}
Ok(out)
}
pub fn from_bytes(bytes: &[u8]) -> Result<Self> {
if !bytes.starts_with(PAGED_NODE_MAGIC) {
return serde_json::from_slice(bytes).map_err(|e| Error::Serialization(e.to_string()));
}
let corrupt = |m: &str| Error::Serialization(format!("Corrupted PagedNodeRecord: {m}"));
if bytes.len() < 16 {
return Err(corrupt("truncated header"));
}
let id = u64::from_le_bytes(bytes[4..12].try_into().map_err(|_| corrupt("id"))?);
let vec_len =
u32::from_le_bytes(bytes[12..16].try_into().map_err(|_| corrupt("vec_len"))?) as usize;
let mut pos = 16usize;
let vec_bytes_end = pos
.checked_add(vec_len.saturating_mul(4))
.ok_or_else(|| corrupt("vec_len overflow"))?;
if vec_bytes_end > bytes.len() {
return Err(corrupt("truncated vector"));
}
let mut vector = Vec::with_capacity(vec_len);
for i in 0..vec_len {
let off = pos + i * 4;
vector.push(f32::from_le_bytes([
bytes[off],
bytes[off + 1],
bytes[off + 2],
bytes[off + 3],
]));
}
pos = vec_bytes_end;
let has_q = *bytes.get(pos).ok_or_else(|| corrupt("quantized flag"))?;
pos += 1;
let quantized = if has_q == 1 {
if pos + 16 > bytes.len() {
return Err(corrupt("truncated sq8 header"));
}
let min_val =
f32::from_le_bytes([bytes[pos], bytes[pos + 1], bytes[pos + 2], bytes[pos + 3]]);
let max_val = f32::from_le_bytes([
bytes[pos + 4],
bytes[pos + 5],
bytes[pos + 6],
bytes[pos + 7],
]);
let step = f32::from_le_bytes([
bytes[pos + 8],
bytes[pos + 9],
bytes[pos + 10],
bytes[pos + 11],
]);
let qlen = u32::from_le_bytes([
bytes[pos + 12],
bytes[pos + 13],
bytes[pos + 14],
bytes[pos + 15],
]) as usize;
pos += 16;
let qend = pos
.checked_add(qlen)
.ok_or_else(|| corrupt("qlen overflow"))?;
let qbytes = bytes
.get(pos..qend)
.ok_or_else(|| corrupt("truncated sq8"))?;
pos = qend;
Some(crate::vector::QuantizedVector8 {
quantized: qbytes.to_vec(),
min_val,
max_val,
step,
})
} else if has_q == 0 {
None
} else {
return Err(corrupt("invalid quantized flag"));
};
if pos + 4 > bytes.len() {
return Err(corrupt("truncated neighbors len"));
}
let nlen = u32::from_le_bytes([bytes[pos], bytes[pos + 1], bytes[pos + 2], bytes[pos + 3]])
as usize;
pos += 4;
let nend = pos
.checked_add(nlen.saturating_mul(8))
.ok_or_else(|| corrupt("neighbors overflow"))?;
if nend != bytes.len() {
return Err(corrupt("neighbors size mismatch"));
}
let mut neighbors_l0 = Vec::with_capacity(nlen);
for i in 0..nlen {
let off = pos + i * 8;
neighbors_l0.push(u64::from_le_bytes([
bytes[off],
bytes[off + 1],
bytes[off + 2],
bytes[off + 3],
bytes[off + 4],
bytes[off + 5],
bytes[off + 6],
bytes[off + 7],
]));
}
Ok(Self {
id,
vector,
quantized,
neighbors_l0,
})
}
}
#[derive(Debug)]
struct LruEntry {
record: PagedNodeRecord,
prev: Option<u64>,
next: Option<u64>,
}
#[derive(Debug, Default)]
struct LruState {
entries: HashMap<u64, LruEntry>,
head: Option<u64>,
tail: Option<u64>,
}
impl LruState {
fn contains_key(&self, id: &u64) -> bool {
self.entries.contains_key(id)
}
fn detach(&mut self, id: u64) -> Option<(Option<u64>, Option<u64>)> {
let entry = self.entries.get(&id)?;
let prev = entry.prev;
let next = entry.next;
if let Some(p) = prev {
if let Some(pe) = self.entries.get_mut(&p) {
pe.next = next;
}
} else {
self.head = next;
}
if let Some(n) = next {
if let Some(ne) = self.entries.get_mut(&n) {
ne.prev = prev;
}
} else {
self.tail = prev;
}
if let Some(e) = self.entries.get_mut(&id) {
e.prev = None;
e.next = None;
}
Some((prev, next))
}
fn attach_tail(&mut self, id: u64) {
let old_tail = self.tail;
if let Some(e) = self.entries.get_mut(&id) {
e.prev = old_tail;
e.next = None;
}
if let Some(t) = old_tail {
if let Some(te) = self.entries.get_mut(&t) {
te.next = Some(id);
}
} else {
self.head = Some(id);
}
self.tail = Some(id);
}
fn touch(&mut self, id: u64) {
if self.tail == Some(id) || !self.entries.contains_key(&id) {
return;
}
self.detach(id);
self.attach_tail(id);
}
fn remove(&mut self, id: u64) {
if self.entries.contains_key(&id) {
self.detach(id);
self.entries.remove(&id);
}
}
fn insert_cache(&mut self, id: u64, record: PagedNodeRecord, capacity: usize) {
if let Some(existing) = self.entries.get_mut(&id) {
existing.record = record;
self.touch(id);
return;
}
if self.entries.len() >= capacity
&& let Some(evicted_id) = self.head
{
self.remove(evicted_id);
}
self.entries.insert(
id,
LruEntry {
record,
prev: None,
next: None,
},
);
self.attach_tail(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.entries.get(&id).map(|e| e.record.clone()) {
lru.touch(id);
return Some(rec);
}
}
let disk_opt = self.disk_pages.read().get(&id).cloned();
if let Some(bytes) = disk_opt
&& 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().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().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)
&& !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)
&& 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);
}
}