Skip to main content

spacedb_vector/
index.rs

1//! The on-node vector index — *query embedding in, top-k out, corpus stays*.
2//!
3//! The index holds the corpus: `(id, embedding)` entries that **never leave the
4//! node**. A [`search`](VectorIndex::search) takes a query embedding and returns
5//! only the top-k [`Match`]es — ids and similarity scores. The return type makes
6//! the privacy property structural: there is no way to read a stored vector back
7//! out of a search; the most an authorized caller learns is *which* items are
8//! near their query and *how* near.
9//!
10//! ## Algorithm
11//!
12//! S3 ships an **exact flat k-NN** search (scan every entry, rank, truncate). For
13//! a home-scale corpus that is correct and fast, and — unlike an approximate
14//! index — has perfect recall. Sub-linear ANN (HNSW / IVF-flat) is an optimization
15//! for very large corpora behind the same [`VectorIndex`] surface, deferred until
16//! corpus size demands it.
17
18use std::cmp::Ordering;
19use std::collections::HashMap;
20use std::hash::{BuildHasherDefault, Hasher};
21
22use crate::error::{VectorError, VectorResult};
23
24/// How similarity is measured. `search` always returns the highest-scoring
25/// entries, so every metric is oriented "higher = more similar".
26#[derive(Clone, Copy, Debug, PartialEq, Eq)]
27pub enum Metric {
28    /// Cosine similarity in `[-1, 1]` (1 = identical direction). Magnitude-invariant.
29    Cosine,
30    /// Raw dot product (higher = more aligned and larger).
31    Dot,
32    /// Negative Euclidean distance (0 = identical, more negative = farther).
33    Euclidean,
34}
35
36impl Metric {
37    /// Score `entry` against query `a`, whose norm is `na`. Norms only feed
38    /// Cosine: the query's is taken once per search and each entry's once at
39    /// insert, rather than both on every comparison — the same arithmetic in
40    /// the same order, so the same bits.
41    fn score(&self, a: &[f32], na: f32, entry: &Entry) -> f32 {
42        let b = &entry.vector;
43        match self {
44            Metric::Cosine => {
45                let nb = entry.norm;
46                if na == 0.0 || nb == 0.0 {
47                    0.0
48                } else {
49                    dot(a, b) / (na * nb)
50                }
51            }
52            Metric::Dot => dot(a, b),
53            Metric::Euclidean => -l2(a, b),
54        }
55    }
56
57    /// The norm a vector carries for this metric (only Cosine reads it).
58    fn norm_of(&self, v: &[f32]) -> f32 {
59        match self {
60            Metric::Cosine => norm(v),
61            Metric::Dot | Metric::Euclidean => 0.0,
62        }
63    }
64}
65
66/// A search hit: which entry, and how similar. **No vector is returned** — the
67/// corpus stays on the node.
68#[derive(Clone, Debug, PartialEq)]
69pub struct Match {
70    pub id: String,
71    pub score: f32,
72}
73
74struct Entry {
75    id: String,
76    vector: Vec<f32>,
77    /// `Metric::norm_of(vector)` for the index's metric.
78    norm: f32,
79}
80
81/// An on-node embedding index.
82pub struct VectorIndex {
83    dim: usize,
84    metric: Metric,
85    entries: Vec<Entry>,
86    /// Where each id sits in `entries`, so an insert finds an existing id
87    /// without comparing it against every stored id (a bulk load was O(n^2)).
88    /// Hashed with FNV-1a: ids are the index owner's own names, not an
89    /// attacker's keys, and SipHash on every insert was 5% of a bulk load.
90    positions: HashMap<String, usize, BuildHasherDefault<IdHasher>>,
91}
92
93/// FNV-1a over an id's bytes.
94#[derive(Default)]
95struct IdHasher(u64);
96
97impl Hasher for IdHasher {
98    fn write(&mut self, bytes: &[u8]) {
99        let mut h = if self.0 == 0 { 0xcbf2_9ce4_8422_2325 } else { self.0 };
100        for &b in bytes {
101            h = (h ^ b as u64).wrapping_mul(0x0000_0100_0000_01b3);
102        }
103        self.0 = h;
104    }
105
106    fn finish(&self) -> u64 {
107        self.0
108    }
109}
110
111impl VectorIndex {
112    /// A new `dim`-dimensional index ranked by `metric`.
113    pub fn new(dim: usize, metric: Metric) -> Self {
114        Self {
115            dim,
116            metric,
117            entries: Vec::new(),
118            positions: HashMap::default(),
119        }
120    }
121
122    pub fn dim(&self) -> usize {
123        self.dim
124    }
125
126    pub fn len(&self) -> usize {
127        self.entries.len()
128    }
129
130    pub fn is_empty(&self) -> bool {
131        self.entries.is_empty()
132    }
133
134    /// Insert (or replace) the embedding for `id`. Errors on a dimension mismatch.
135    pub fn insert(&mut self, id: impl Into<String>, vector: Vec<f32>) -> VectorResult<()> {
136        if vector.len() != self.dim {
137            return Err(VectorError::DimMismatch {
138                expected: self.dim,
139                got: vector.len(),
140            });
141        }
142        let id = id.into();
143        let norm = self.metric.norm_of(&vector);
144        if let Some(&at) = self.positions.get(&id) {
145            let existing = &mut self.entries[at];
146            existing.vector = vector;
147            existing.norm = norm;
148        } else {
149            self.positions.insert(id.clone(), self.entries.len());
150            self.entries.push(Entry { id, vector, norm });
151        }
152        Ok(())
153    }
154
155    /// Remove `id`. Returns whether it was present.
156    pub fn remove(&mut self, id: &str) -> bool {
157        let Some(at) = self.positions.remove(id) else {
158            return false;
159        };
160        // Order-preserving, as `retain` was; every later entry moves down one.
161        self.entries.remove(at);
162        for entry in &self.entries[at..] {
163            if let Some(p) = self.positions.get_mut(&entry.id) {
164                *p -= 1;
165            }
166        }
167        true
168    }
169
170    /// Return the top-`k` entries nearest to `query`, highest score first. Ties
171    /// break by id for deterministic (corroboratable) results. Errors on a
172    /// dimension mismatch.
173    pub fn search(&self, query: &[f32], k: usize) -> VectorResult<Vec<Match>> {
174        if query.len() != self.dim {
175            return Err(VectorError::DimMismatch {
176                expected: self.dim,
177                got: query.len(),
178            });
179        }
180        let query_norm = self.metric.norm_of(query);
181        // Rank (score, position) pairs; an id is cloned only for the k returned.
182        let mut scored: Vec<(f32, usize)> = self
183            .entries
184            .iter()
185            .enumerate()
186            .map(|(at, e)| (self.metric.score(query, query_norm, e), at))
187            .collect();
188        let rank = |a: &(f32, usize), b: &(f32, usize)| {
189            b.0.partial_cmp(&a.0)
190                .unwrap_or(Ordering::Equal)
191                .then_with(|| self.entries[a.1].id.cmp(&self.entries[b.1].id))
192        };
193        // Ids are unique, so without NaN `rank` is a strict total order and
194        // selecting the top k then sorting only those gives exactly the full
195        // sort's first k. A NaN score breaks that order; keep the full sort then.
196        if k < scored.len() && !scored.iter().any(|(s, _)| s.is_nan()) {
197            if k > 0 {
198                scored.select_nth_unstable_by(k - 1, rank);
199            }
200            scored.truncate(k);
201        }
202        scored.sort_by(rank);
203        scored.truncate(k);
204        Ok(scored
205            .into_iter()
206            .map(|(score, at)| Match {
207                id: self.entries[at].id.clone(),
208                score,
209            })
210            .collect())
211    }
212}
213
214/// Lanes of the fixed-width partial sums below. A serial f32 sum is a
215/// dependency chain the compiler may not reassociate, so it runs one
216/// multiply-add per element; eight independent accumulators, combined in a
217/// fixed order, let it vectorize. The split is a constant, not the machine's
218/// vector width, so every host computes the same bits.
219const LANES: usize = 8;
220
221/// `acc` folded in a fixed tree order, then the scalar tail.
222#[inline]
223fn fold(acc: [f32; LANES], tail: f32) -> f32 {
224    ((acc[0] + acc[4]) + (acc[2] + acc[6])) + ((acc[1] + acc[5]) + (acc[3] + acc[7])) + tail
225}
226
227fn dot(a: &[f32], b: &[f32]) -> f32 {
228    let mut acc = [0f32; LANES];
229    let (ca, ra) = a.as_chunks::<LANES>();
230    let (cb, rb) = b.as_chunks::<LANES>();
231    for (x, y) in ca.iter().zip(cb) {
232        for l in 0..LANES {
233            acc[l] += x[l] * y[l];
234        }
235    }
236    let tail = ra.iter().zip(rb).fold(0f32, |s, (x, y)| s + x * y);
237    fold(acc, tail)
238}
239
240/// The one-multiply-add-per-element form `dot` replaced; the test oracle.
241#[cfg(test)]
242fn dot_serial(a: &[f32], b: &[f32]) -> f32 {
243    a.iter().zip(b).map(|(x, y)| x * y).sum()
244}
245
246fn norm(a: &[f32]) -> f32 {
247    dot(a, a).sqrt()
248}
249
250fn l2(a: &[f32], b: &[f32]) -> f32 {
251    let mut acc = [0f32; LANES];
252    let (ca, ra) = a.as_chunks::<LANES>();
253    let (cb, rb) = b.as_chunks::<LANES>();
254    for (x, y) in ca.iter().zip(cb) {
255        for l in 0..LANES {
256            let d = x[l] - y[l];
257            acc[l] += d * d;
258        }
259    }
260    let tail = ra.iter().zip(rb).fold(0f32, |s, (x, y)| {
261        let d = x - y;
262        s + d * d
263    });
264    fold(acc, tail).sqrt()
265}
266
267#[cfg(test)]
268mod accumulator_tests {
269    use super::*;
270
271    fn vectors(n: usize, dim: usize, seed: u64) -> Vec<Vec<f32>> {
272        let mut s = seed | 1;
273        let mut next = move || {
274            s ^= s << 13;
275            s ^= s >> 7;
276            s ^= s << 17;
277            ((s >> 40) as f32 / (1u64 << 24) as f32) - 0.5
278        };
279        (0..n).map(|_| (0..dim).map(|_| next()).collect()).collect()
280    }
281
282    #[test]
283    fn dot_matches_serial_within_tolerance_at_every_tail() {
284        for dim in [1, 7, 8, 9, 15, 16, 64, 65, 100] {
285            let vs = vectors(2, dim, dim as u64);
286            let (a, b) = (&vs[0], &vs[1]);
287            let fast = dot(a, b);
288            let slow = dot_serial(a, b);
289            let scale = slow.abs().max(1e-3);
290            assert!((fast - slow).abs() / scale < 1e-4, "dim {dim}: {fast} vs {slow}");
291        }
292    }
293
294    #[test]
295    fn top_k_sets_agree_with_serial_scoring() {
296        // The ranking an index returns under each metric must pick the same
297        // ids as serial scoring would, bar exact near-ties (none in this data).
298        let dim = 64;
299        let corpus = vectors(500, dim, 3);
300        let queries = vectors(5, dim, 11);
301        for metric in [Metric::Cosine, Metric::Dot, Metric::Euclidean] {
302            let mut index = VectorIndex::new(dim, metric);
303            for (i, v) in corpus.iter().enumerate() {
304                index.insert(format!("v{i}"), v.clone()).unwrap();
305            }
306            for q in &queries {
307                let fast: Vec<String> = index.search(q, 10).unwrap().into_iter().map(|m| m.id).collect();
308                let mut slow: Vec<(f32, usize)> = corpus
309                    .iter()
310                    .enumerate()
311                    .map(|(i, v)| {
312                        let s = match metric {
313                            Metric::Cosine => {
314                                dot_serial(q, v) / (dot_serial(q, q).sqrt() * dot_serial(v, v).sqrt())
315                            }
316                            Metric::Dot => dot_serial(q, v),
317                            Metric::Euclidean => -q
318                                .iter()
319                                .zip(v)
320                                .map(|(x, y)| (x - y) * (x - y))
321                                .sum::<f32>()
322                                .sqrt(),
323                        };
324                        (s, i)
325                    })
326                    .collect();
327                slow.sort_by(|a, b| b.0.partial_cmp(&a.0).unwrap());
328                let slow: Vec<String> = slow.iter().take(10).map(|(_, i)| format!("v{i}")).collect();
329                let mut fs = fast.clone();
330                let mut ss = slow.clone();
331                fs.sort();
332                ss.sort();
333                assert_eq!(fs, ss, "{metric:?}");
334            }
335        }
336    }
337}