use std::fs;
use std::io::ErrorKind;
use std::path::{Path, PathBuf};
use std::sync::{Arc, PoisonError, RwLock, RwLockReadGuard, RwLockWriteGuard};
use anyhow::{Context, Result, anyhow};
use usearch::{Index, IndexOptions, MetricKind, ScalarKind};
use crate::sealed::{self, SealError, SealKeys};
pub const EMBEDDING_DIM: usize = 384;
const INITIAL_CAPACITY: usize = 1024;
#[derive(Clone, Copy, PartialEq, Eq)]
enum VectorMode {
ReadWrite,
View,
Loaded,
Shared,
}
pub struct VectorIndex {
index: Arc<RwLock<Index>>,
path: PathBuf,
mode: VectorMode,
scalar_kind: ScalarKind,
seal: Option<SealKeys>,
}
fn new_index(scalar_kind: ScalarKind) -> Result<Index> {
let options = IndexOptions {
dimensions: EMBEDDING_DIM,
metric: MetricKind::Cos,
quantization: scalar_kind,
..IndexOptions::default()
};
Index::new(&options).map_err(|e| anyhow!("creating usearch index: {e}"))
}
fn reserved_index(scalar_kind: ScalarKind) -> Result<Index> {
let index = new_index(scalar_kind)?;
index
.reserve(INITIAL_CAPACITY)
.map_err(|e| anyhow!("reserving usearch capacity: {e}"))?;
Ok(index)
}
fn check_on_disk_kind(path: &Path, path_str: &str, expected: ScalarKind) -> Result<()> {
check_kind(path, read_on_disk_kind(path, path_str)?, expected)
}
fn check_kind(path: &Path, actual: ScalarKind, expected: ScalarKind) -> Result<()> {
if actual != expected {
return Err(anyhow!(
"vector index at {} was written as {:?} but is being opened as {:?}",
path.display(),
actual,
expected
));
}
Ok(())
}
const KEY_TABLE_SLOTS_PER_BUCKET: usize = 64;
const KEY_TABLE_BUCKET_HEADER_BYTES: usize = 2 * size_of::<u64>();
const KEY_TABLE_ENTRY_BYTES: usize =
(size_of::<u64>() + size_of::<u32>()).next_multiple_of(align_of::<u64>());
fn key_table_bytes(capacity: usize) -> usize {
if capacity == 0 {
return 0;
}
let slots = (capacity * 3).div_ceil(2).next_power_of_two();
let buckets = slots.div_ceil(KEY_TABLE_SLOTS_PER_BUCKET);
buckets * (KEY_TABLE_SLOTS_PER_BUCKET * KEY_TABLE_ENTRY_BYTES + KEY_TABLE_BUCKET_HEADER_BYTES)
}
fn read_on_disk_kind(path: &Path, path_str: &str) -> Result<ScalarKind> {
refuse_sealed(path)?;
Ok(Index::metadata(path_str)
.map_err(|e| anyhow!("reading usearch header at {}: {e}", path.display()))?
.quantization)
}
fn refuse_sealed(path: &Path) -> Result<()> {
if sealed::sealed_key_id(path)?.is_some() {
return Err(anyhow::Error::new(SealError::KeyRequired).context(format!(
"vector index at {} is sealed and was opened without keys",
path.display()
)));
}
Ok(())
}
fn file_name(path: &Path) -> Result<&str> {
path.file_name()
.and_then(|n| n.to_str())
.with_context(|| format!("{} has no utf-8 file name", path.display()))
}
fn load_keyed(path: &Path, scalar_kind: ScalarKind, keys: &SealKeys) -> Result<Index> {
let bytes = sealed::read_file(path, Some(keys), file_name(path)?)?;
let actual = Index::metadata_from_buffer(&bytes)
.map_err(|e| anyhow!("reading usearch header at {}: {e}", path.display()))?
.quantization;
check_kind(path, actual, scalar_kind)?;
let index = new_index(scalar_kind)?;
index
.load_from_buffer(&bytes)
.map_err(|e| anyhow!("loading usearch index from {}: {e}", path.display()))?;
Ok(index)
}
fn remove_stale_tmp_files(path: &Path) -> Result<()> {
let Some(dir) = path.parent() else {
return Ok(());
};
let name = file_name(path)?;
let entries = match fs::read_dir(dir) {
Ok(entries) => entries,
Err(e) if e.kind() == ErrorKind::NotFound => return Ok(()),
Err(e) => return Err(e).with_context(|| format!("listing {}", dir.display())),
};
for entry in entries {
let entry = entry?;
let Some(entry_name) = entry.file_name().to_str().map(str::to_owned) else {
continue;
};
let Some(rest) = entry_name.strip_prefix(name) else {
continue;
};
if rest == ".tmp" || sealed::is_tmp_name(rest) {
fs::remove_file(entry.path())
.with_context(|| format!("removing {}", entry.path().display()))?;
}
}
Ok(())
}
impl VectorIndex {
pub fn on_disk_kind(path: &Path) -> Result<Option<ScalarKind>> {
if !path.exists() {
return Ok(None);
}
let path_str = path.to_str().context("vector index path is not utf-8")?;
read_on_disk_kind(path, path_str).map(Some)
}
fn with_index(
index: Index,
path: &Path,
mode: VectorMode,
scalar_kind: ScalarKind,
seal: Option<SealKeys>,
) -> Self {
Self {
index: Arc::new(RwLock::new(index)),
path: path.to_path_buf(),
mode,
scalar_kind,
seal,
}
}
pub fn open_with_kind(path: &Path, scalar_kind: ScalarKind) -> Result<Self> {
let path_str = path.to_str().context("vector index path is not utf-8")?;
let index = if path.exists() {
check_on_disk_kind(path, path_str, scalar_kind)?;
let index = new_index(scalar_kind)?;
index
.load(path_str)
.map_err(|e| anyhow!("loading usearch index from {path_str}: {e}"))?;
index
} else {
reserved_index(scalar_kind)?
};
Ok(Self::with_index(
index,
path,
VectorMode::ReadWrite,
scalar_kind,
None,
))
}
pub fn open_with_kind_keyed(
path: &Path,
scalar_kind: ScalarKind,
keys: &SealKeys,
) -> Result<Self> {
remove_stale_tmp_files(path)?;
let index = if path.exists() {
load_keyed(path, scalar_kind, keys)?
} else {
reserved_index(scalar_kind)?
};
Ok(Self::with_index(
index,
path,
VectorMode::ReadWrite,
scalar_kind,
Some(keys.clone()),
))
}
pub fn open_view_with_kind(path: &Path, scalar_kind: ScalarKind) -> Result<Self> {
if !path.exists() {
return Err(anyhow!(
"vector index view: {} does not exist",
path.display()
));
}
let path_str = path.to_str().context("vector index path is not utf-8")?;
check_on_disk_kind(path, path_str, scalar_kind)?;
let index = new_index(scalar_kind)?;
index
.view(path_str)
.map_err(|e| anyhow!("viewing usearch index at {path_str}: {e}"))?;
Ok(Self::with_index(
index,
path,
VectorMode::View,
scalar_kind,
None,
))
}
pub fn empty_view_with_kind(path: &Path, scalar_kind: ScalarKind) -> Result<Self> {
Ok(Self::with_index(
new_index(scalar_kind)?,
path,
VectorMode::View,
scalar_kind,
None,
))
}
pub fn open_loaded_with_kind(
path: &Path,
scalar_kind: ScalarKind,
keys: &SealKeys,
) -> Result<Self> {
if !path.exists() {
return Err(anyhow!("vector index: {} does not exist", path.display()));
}
Ok(Self::with_index(
load_keyed(path, scalar_kind, keys)?,
path,
VectorMode::Loaded,
scalar_kind,
Some(keys.clone()),
))
}
pub fn empty_loaded_with_kind(
path: &Path,
scalar_kind: ScalarKind,
keys: &SealKeys,
) -> Result<Self> {
Ok(Self::with_index(
new_index(scalar_kind)?,
path,
VectorMode::Loaded,
scalar_kind,
Some(keys.clone()),
))
}
pub fn shared_reader(&self) -> Self {
Self {
index: Arc::clone(&self.index),
path: self.path.clone(),
mode: VectorMode::Shared,
scalar_kind: self.scalar_kind,
seal: self.seal.clone(),
}
}
pub fn detached(&self) -> Result<Self> {
self.require_writable()?;
Ok(Self::with_index(
reserved_index(self.scalar_kind)?,
&self.path,
VectorMode::ReadWrite,
self.scalar_kind,
self.seal.clone(),
))
}
pub fn has_shared_readers(&self) -> bool {
Arc::strong_count(&self.index) > 1
}
pub fn adopt(&mut self, fresh: VectorIndex) -> Result<()> {
self.require_writable()?;
let index = Arc::try_unwrap(fresh.index)
.map_err(|_| anyhow!("an index with shared readers cannot be adopted"))?
.into_inner()
.unwrap_or_else(PoisonError::into_inner);
*self.write() = index;
Ok(())
}
pub fn set_seal_keys(&mut self, keys: SealKeys) {
self.seal = Some(keys);
}
pub fn scalar_kind(&self) -> ScalarKind {
self.scalar_kind
}
fn read(&self) -> RwLockReadGuard<'_, Index> {
self.index.read().unwrap_or_else(PoisonError::into_inner)
}
fn write(&self) -> RwLockWriteGuard<'_, Index> {
self.index.write().unwrap_or_else(PoisonError::into_inner)
}
fn require_writable(&self) -> Result<()> {
match self.mode {
VectorMode::ReadWrite => Ok(()),
VectorMode::View | VectorMode::Loaded | VectorMode::Shared => Err(anyhow!(
"vector index at {} is read-only; mutation is not permitted",
self.path.display()
)),
}
}
pub fn upsert(&mut self, key: u64, embedding: &[f32]) -> Result<()> {
self.require_writable()?;
self.ensure_capacity(1)?;
let index = self.read();
index
.remove(key)
.map_err(|e| anyhow!("removing key {key}: {e}"))?;
index
.add(key, embedding)
.map_err(|e| anyhow!("adding key {key}: {e}"))?;
Ok(())
}
pub fn remove(&mut self, key: u64) -> Result<()> {
self.require_writable()?;
self.read()
.remove(key)
.map_err(|e| anyhow!("removing key {key}: {e}"))?;
Ok(())
}
pub fn search(&self, query: &[f32], k: usize) -> Result<Vec<(u64, f32)>> {
let matches = self
.read()
.search(query, k)
.map_err(|e| anyhow!("usearch search: {e}"))?;
Ok(matches
.keys
.iter()
.zip(matches.distances.iter())
.map(|(key, distance)| (*key, 1.0 - *distance))
.collect())
}
pub fn len(&self) -> usize {
self.read().size()
}
pub fn memory_usage(&self) -> usize {
self.read().memory_usage()
}
pub(crate) fn anonymous_bytes(&self) -> u64 {
if self.mode == VectorMode::Shared {
return 0;
}
let index = self.read();
let stats = index.memory_stats();
let arenas = index
.memory_usage()
.saturating_sub(stats.graph_reserved)
.saturating_sub(stats.vectors_reserved);
let capacity = index.capacity();
let vector_pointers = capacity * size_of::<*const u8>();
(arenas + key_table_bytes(capacity) + vector_pointers) as u64
}
pub fn save(&self) -> Result<()> {
self.require_writable()?;
match &self.seal {
Some(keys) => self.save_sealed(keys),
None => self.save_plain(),
}
}
fn save_plain(&self) -> Result<()> {
let tmp_path = self.path.with_extension("usearch.tmp");
let tmp_str = tmp_path
.to_str()
.context("vector index tmp path is not utf-8")?;
self.read()
.save(tmp_str)
.map_err(|e| anyhow!("saving usearch index to {tmp_str}: {e}"))?;
let tmp_file = std::fs::File::open(&tmp_path)
.with_context(|| format!("reopening {} to fsync", tmp_path.display()))?;
tmp_file
.sync_all()
.with_context(|| format!("fsyncing {}", tmp_path.display()))?;
drop(tmp_file);
std::fs::rename(&tmp_path, &self.path).with_context(|| {
format!("renaming {} to {}", tmp_path.display(), self.path.display())
})?;
Ok(())
}
fn save_sealed(&self, keys: &SealKeys) -> Result<()> {
let bytes = {
let index = self.read();
let mut bytes = vec![0u8; index.serialized_length()];
index
.save_to_buffer(&mut bytes)
.map_err(|e| anyhow!("serializing usearch index: {e}"))?;
bytes
};
sealed::write_file(&self.path, Some(keys), file_name(&self.path)?, &bytes)
}
pub fn reload_view(&mut self) -> Result<()> {
match self.mode {
VectorMode::View => {
refuse_sealed(&self.path)?;
let path_str = self
.path
.to_str()
.context("vector index path is not utf-8")?;
self.write()
.view(path_str)
.map_err(|e| anyhow!("reloading usearch view at {path_str}: {e}"))?;
}
VectorMode::Loaded => {
let keys = self
.seal
.as_ref()
.context("a loaded vector index holds its keys")?;
let fresh = load_keyed(&self.path, self.scalar_kind, keys)?;
*self.write() = fresh;
}
VectorMode::ReadWrite | VectorMode::Shared => {}
}
Ok(())
}
fn ensure_capacity(&self, extra: usize) -> Result<()> {
let (needed, capacity) = {
let index = self.read();
(index.size() + extra, index.capacity())
};
if needed > capacity {
self.write()
.reserve((needed * 2).max(INITIAL_CAPACITY))
.map_err(|e| anyhow!("growing usearch capacity: {e}"))?;
}
Ok(())
}
#[cfg(test)]
fn contains(&self, key: u64) -> bool {
self.read().contains(key)
}
}
#[cfg(test)]
mod tests {
use super::*;
use tempfile::tempdir;
fn unit_vector(hot: usize) -> Vec<f32> {
let mut v = vec![0.0f32; EMBEDDING_DIM];
v[hot] = 1.0;
v
}
#[test]
fn key_table_bytes_follow_the_capacity_usearch_reports() {
assert_eq!(key_table_bytes(0), 0);
assert_eq!(key_table_bytes(1), 64 * 16 + 16);
let index = new_index(ScalarKind::F32).unwrap();
index.reserve(INITIAL_CAPACITY).unwrap();
assert!(index.capacity() >= INITIAL_CAPACITY);
assert_eq!(
key_table_bytes(index.capacity()),
key_table_bytes(INITIAL_CAPACITY)
);
}
#[test]
fn anonymous_bytes_leave_out_the_unfaulted_arena_tail() {
let dir = tempdir().unwrap();
let mut idx =
VectorIndex::open_with_kind(&dir.path().join("vectors.usearch"), ScalarKind::F32)
.unwrap();
idx.upsert(0, &unit_vector(0)).unwrap();
assert!(
idx.memory_usage() >= 4 << 20,
"one vector maps a whole arena"
);
assert!(
idx.anonymous_bytes() < 1 << 20,
"only the touched head of the arena is resident: {}",
idx.anonymous_bytes()
);
assert!(idx.anonymous_bytes() as usize >= EMBEDDING_DIM * 4);
}
#[test]
fn f32_index_writes_and_reads_back() {
let dir = tempdir().unwrap();
let path = dir.path().join("vectors.usearch");
let mut idx = VectorIndex::open_with_kind(&path, ScalarKind::F32).unwrap();
assert_eq!(idx.scalar_kind(), ScalarKind::F32);
for i in 0..5u64 {
idx.upsert(i, &unit_vector(i as usize)).unwrap();
}
idx.save().unwrap();
let reopened = VectorIndex::open_with_kind(&path, ScalarKind::F32).unwrap();
assert_eq!(reopened.scalar_kind(), ScalarKind::F32);
let hits = reopened.search(&unit_vector(2), 1).unwrap();
assert_eq!(hits[0].0, 2);
let viewed = VectorIndex::open_view_with_kind(&path, ScalarKind::F32).unwrap();
let hits = viewed.search(&unit_vector(3), 1).unwrap();
assert_eq!(hits[0].0, 3);
}
#[test]
fn opening_f32_file_as_a_different_kind_errors_instead_of_corrupting() {
let dir = tempdir().unwrap();
let path = dir.path().join("vectors.usearch");
let mut idx = VectorIndex::open_with_kind(&path, ScalarKind::F32).unwrap();
idx.upsert(0, &unit_vector(0)).unwrap();
idx.save().unwrap();
let err = VectorIndex::open_with_kind(&path, ScalarKind::I8)
.err()
.expect("opening an F32 file as I8 must error");
assert!(err.to_string().contains("F32"), "error was: {err}");
let err = VectorIndex::open_view_with_kind(&path, ScalarKind::F16)
.err()
.expect("viewing an F32 file as F16 must error");
assert!(err.to_string().contains("F32"), "error was: {err}");
}
#[test]
fn i8_and_f16_kinds_round_trip() {
for kind in [ScalarKind::I8, ScalarKind::F16] {
let dir = tempdir().unwrap();
let path = dir.path().join("vectors.usearch");
let mut idx = VectorIndex::open_with_kind(&path, kind).unwrap();
for i in 0..5u64 {
idx.upsert(i, &unit_vector(i as usize)).unwrap();
}
idx.save().unwrap();
let viewed = VectorIndex::open_view_with_kind(&path, kind).unwrap();
let hits = viewed.search(&unit_vector(4), 1).unwrap();
assert_eq!(hits[0].0, 4, "kind {kind:?} lost the nearest match");
}
}
fn keys(byte: u8) -> SealKeys {
SealKeys::single(
crate::sealed::SealKey::from_bytes(crate::keys::KeyGuard::new([byte; 32])).unwrap(),
)
}
fn spread_vector(key: u64) -> Vec<f32> {
let mut v: Vec<f32> = (0..EMBEDDING_DIM)
.map(|j| ((key as usize * 31 + j * 17) % 97) as f32 - 48.0)
.collect();
v[key as usize % EMBEDDING_DIM] += 500.0;
v
}
#[test]
fn a_shared_reader_searches_while_the_writer_adds_and_grows() {
const ADDED: u64 = 5_000;
let dir = tempdir().unwrap();
let mut writer =
VectorIndex::open_with_kind(&dir.path().join("vectors.usearch"), ScalarKind::F32)
.unwrap();
let initial_capacity = writer.read().capacity();
let reader = writer.shared_reader();
let stop = Arc::new(std::sync::atomic::AtomicBool::new(false));
let (done_tx, done_rx) = std::sync::mpsc::channel();
let searcher = {
let stop = Arc::clone(&stop);
std::thread::spawn(move || {
let mut searches = 0u64;
let mut outcome = Ok(());
while !stop.load(std::sync::atomic::Ordering::Acquire) {
if let Err(e) = reader.search(&spread_vector(searches % ADDED), 10) {
outcome = Err(format!("{e:#}"));
break;
}
searches += 1;
}
let _ = done_tx.send((outcome, searches));
})
};
for key in 0..ADDED {
writer.upsert(key, &spread_vector(key)).unwrap();
}
stop.store(true, std::sync::atomic::Ordering::Release);
let (outcome, searches) = done_rx
.recv_timeout(std::time::Duration::from_secs(60))
.expect("the searching thread did not stop within 60 s");
searcher.join().unwrap();
outcome.unwrap();
assert!(searches > 0, "no search ran beside the adds");
assert!(
writer.read().capacity() >= 4 * initial_capacity,
"the adds never grew the index more than once"
);
assert_eq!(writer.len(), ADDED as usize);
for key in 0..ADDED {
assert!(writer.contains(key), "key {key} was lost");
}
}
fn random_vector(seed: u64) -> Vec<f32> {
use rand::{Rng, SeedableRng};
let mut rng = rand::rngs::StdRng::seed_from_u64(seed);
(0..EMBEDDING_DIM)
.map(|_| rng.random_range(-1.0f32..1.0))
.collect()
}
#[test]
fn shared_readers_search_while_the_writer_updates_and_removes() {
const KEYS: u64 = 2_000;
let dir = tempdir().unwrap();
let mut writer =
VectorIndex::open_with_kind(&dir.path().join("vectors.usearch"), ScalarKind::F32)
.unwrap();
for key in 0..KEYS {
writer.upsert(key, &random_vector(key)).unwrap();
}
let stop = Arc::new(std::sync::atomic::AtomicBool::new(false));
let (done_tx, done_rx) = std::sync::mpsc::channel();
let searchers: Vec<_> = (0..2u64)
.map(|offset| {
let reader = writer.shared_reader();
let stop = Arc::clone(&stop);
let done_tx = done_tx.clone();
std::thread::spawn(move || {
let mut searches = 0u64;
let mut outcome = Ok(());
while !stop.load(std::sync::atomic::Ordering::Acquire) {
let probe = random_vector((searches * 7 + offset) % (2 * KEYS));
if let Err(e) = reader.search(&probe, 10) {
outcome = Err(format!("{e:#}"));
break;
}
searches += 1;
}
let _ = done_tx.send((outcome, searches));
})
})
.collect();
drop(done_tx);
for key in 0..KEYS {
if key % 3 == 0 {
writer.remove(key).unwrap();
} else {
writer.upsert(key, &random_vector(key + KEYS)).unwrap();
}
}
stop.store(true, std::sync::atomic::Ordering::Release);
for _ in 0..2 {
let (outcome, searches) = done_rx
.recv_timeout(std::time::Duration::from_secs(60))
.expect("a searching thread did not stop within 60 s");
outcome.unwrap();
assert!(searches > 0, "no search ran beside the updates");
}
for searcher in searchers {
searcher.join().unwrap();
}
for key in 0..KEYS {
assert_eq!(writer.contains(key), key % 3 != 0, "key {key}");
}
for key in (1..KEYS).filter(|k| k % 3 != 0).step_by(97) {
let hits = writer.search(&random_vector(key + KEYS), 10).unwrap();
assert!(
hits.iter().any(|(hit, _)| *hit == key),
"the update of key {key} was lost: {hits:?}"
);
}
}
#[test]
fn a_sealed_vector_file_round_trips_and_refuses_unkeyed_opens() {
let dir = tempdir().unwrap();
let path = dir.path().join("vectors.usearch");
let mut idx = VectorIndex::open_with_kind_keyed(&path, ScalarKind::F32, &keys(1)).unwrap();
for i in 0..5u64 {
idx.upsert(i, &unit_vector(i as usize)).unwrap();
}
idx.save().unwrap();
assert!(crate::sealed::sealed_key_id(&path).unwrap().is_some());
let reopened = VectorIndex::open_with_kind_keyed(&path, ScalarKind::F32, &keys(1)).unwrap();
assert_eq!(reopened.search(&unit_vector(2), 1).unwrap()[0].0, 2);
let loaded = VectorIndex::open_loaded_with_kind(&path, ScalarKind::F32, &keys(1)).unwrap();
assert_eq!(loaded.search(&unit_vector(3), 1).unwrap()[0].0, 3);
for err in [
VectorIndex::on_disk_kind(&path).err(),
VectorIndex::open_with_kind(&path, ScalarKind::F32).err(),
VectorIndex::open_view_with_kind(&path, ScalarKind::F32).err(),
] {
let err = err.expect("a sealed file must not open without its key");
assert_eq!(
crate::sealed::seal_error(&err),
Some(&SealError::KeyRequired),
"error was: {err:#}"
);
}
let err = VectorIndex::open_with_kind_keyed(&path, ScalarKind::I8, &keys(1))
.err()
.expect("opening a sealed F32 file as I8 must error");
assert!(err.to_string().contains("F32"), "error was: {err}");
}
#[test]
fn a_keyed_open_removes_the_temporary_files_a_killed_save_left() {
let dir = tempdir().unwrap();
let path = dir.path().join("vectors.usearch");
let plain_tmp = dir.path().join("vectors.usearch.tmp");
let sealed_tmp = dir.path().join("vectors.usearch.seal-tmp.0123456789abcdef");
let other = dir.path().join("chunks.usearch.tmp");
for p in [&plain_tmp, &sealed_tmp, &other] {
fs::write(p, b"leftover").unwrap();
}
VectorIndex::open_with_kind_keyed(&path, ScalarKind::F32, &keys(1)).unwrap();
assert!(!plain_tmp.exists());
assert!(!sealed_tmp.exists());
assert!(other.exists(), "another index's file was removed");
}
}