iqdb_index/index.rs
1//! The [`IndexCore`] and [`Index`] traits.
2//!
3//! [`IndexCore`] is the object-safe operational surface every index exposes;
4//! the engine stores indexes through `Box<dyn IndexCore>`. [`Index`] is the
5//! typed-construction sibling that carries the implementer's associated
6//! `Config` and a `Self`-returning `new` — used where the concrete type is
7//! known, not through `dyn`.
8
9use std::sync::Arc;
10
11use iqdb_types::{DistanceMetric, Hit, Metadata, Result, SearchParams, VectorId};
12
13use crate::stats::IndexStats;
14
15/// The object-safe operational surface of an index.
16///
17/// Every concrete index implements this trait so the engine can hold a
18/// heterogeneous set of indexes as `Box<dyn IndexCore>`. The methods are
19/// the read/write/diagnose surface; construction is a separate concern, in
20/// [`Index`].
21///
22/// ## Required vs. provided
23///
24/// Implementers must define [`insert`](IndexCore::insert),
25/// [`delete`](IndexCore::delete), [`search`](IndexCore::search),
26/// [`len`](IndexCore::len), [`dim`](IndexCore::dim),
27/// [`metric`](IndexCore::metric), [`flush`](IndexCore::flush), and
28/// [`stats`](IndexCore::stats). [`insert_batch`](IndexCore::insert_batch),
29/// [`search_batch`](IndexCore::search_batch), and
30/// [`is_empty`](IndexCore::is_empty) have default implementations and may
31/// be overridden when a vectorized fast path exists.
32///
33/// ## Concurrency contract
34///
35/// Implementers MUST be `Send + Sync` — that bound is on the trait
36/// itself, and the engine relies on it to share `Box<dyn IndexCore>`
37/// across threads inside its per-shard locks. An implementer needs only
38/// to be **single-writer-internal**: the engine guards every concrete
39/// index with an external `RwLock`, so the index sees either many
40/// concurrent shared (`&self`) accesses OR one exclusive (`&mut self`)
41/// access at a time. Indexes therefore do not need their own internal
42/// locking; correctness against `&self` aliasing is enough.
43///
44/// In particular, [`insert`](IndexCore::insert),
45/// [`delete`](IndexCore::delete), and [`flush`](IndexCore::flush) take
46/// `&mut self` and are only ever called while the engine holds the
47/// corresponding shard's write lock; [`search`](IndexCore::search),
48/// [`len`](IndexCore::len), [`is_empty`](IndexCore::is_empty),
49/// [`dim`](IndexCore::dim), [`metric`](IndexCore::metric), and
50/// [`stats`](IndexCore::stats) take `&self` and may be called
51/// concurrently from many threads while the shard's write lock is
52/// unheld.
53///
54/// ## Ordering contract on `Hit.distance`
55///
56/// [`Hit`]'s `distance` is documented as **smaller is nearer**. Four of the
57/// five metrics (Cosine, Euclidean, Manhattan, Hamming) satisfy that
58/// natively. For [`DistanceMetric::DotProduct`], the raw inner product is a
59/// similarity (larger is more similar), so an implementation MUST negate it
60/// at the boundary — store `-dot` in `Hit.distance` — to keep one ordering
61/// invariant across the index family.
62///
63/// ## Deletion contract
64///
65/// [`delete`](IndexCore::delete) is specified by **observable behavior**,
66/// not by a storage mechanism. After `delete(id)`:
67///
68/// - `search` MUST NOT return `id` until a subsequent `insert(id, …)`
69/// succeeds.
70/// - Whether storage is reclaimed immediately, tombstoned, or compacted
71/// later is implementation-defined and surfaced via
72/// [`IndexStats::extra`].
73///
74/// An implementation MAY reject re-inserting a deleted id; if so, it MUST
75/// document that and return [`iqdb_types::IqdbError::Duplicate`].
76///
77/// ## Examples
78///
79/// See the crate-level docs for a runnable mock implementation that
80/// exercises every method of this trait.
81pub trait IndexCore: Send + Sync {
82 /// Insert one vector into the index.
83 ///
84 /// `vector.len()` MUST equal [`dim`](IndexCore::dim); otherwise the
85 /// call returns [`iqdb_types::IqdbError::DimensionMismatch`]. Inserting
86 /// an `id` that is already present returns
87 /// [`iqdb_types::IqdbError::Duplicate`].
88 ///
89 /// `vector` is owned via [`Arc<[f32]>`](std::sync::Arc) so the engine
90 /// can hand the same payload allocation to the index and its
91 /// authoritative record store without copying — the index takes one
92 /// strong reference (no `[f32]` data copy), the record store keeps
93 /// another. Implementers SHOULD store the `Arc` (or a clone) rather than
94 /// allocating a fresh buffer, so the shared-payload guarantee holds.
95 fn insert(
96 &mut self,
97 id: VectorId,
98 vector: Arc<[f32]>,
99 metadata: Option<Metadata>,
100 ) -> Result<()>;
101
102 /// Insert many vectors in a single call.
103 ///
104 /// The default implementation loops over `items` and calls
105 /// [`insert`](IndexCore::insert) for each one. It is **fail-fast**: the
106 /// first error returns immediately, and any inserts that succeeded
107 /// before that point remain in the index. Implementers MAY override
108 /// with a vectorized path; if they do, they SHOULD document whether
109 /// they preserve fail-fast or apply atomically.
110 fn insert_batch(&mut self, items: Vec<(VectorId, Arc<[f32]>, Option<Metadata>)>) -> Result<()> {
111 for (id, vector, metadata) in items {
112 self.insert(id, vector, metadata)?;
113 }
114 Ok(())
115 }
116
117 /// Remove the vector identified by `id` from the search space.
118 ///
119 /// Returns [`iqdb_types::IqdbError::NotFound`] if no vector with that
120 /// `id` is searchable. See the trait-level "Deletion contract" for the
121 /// observable behavior implementations must guarantee.
122 fn delete(&mut self, id: &VectorId) -> Result<()>;
123
124 /// Run a top-`k` similarity search.
125 ///
126 /// Returns up to `params.k` [`Hit`]s ordered best-first (smallest
127 /// `Hit.distance` first; see the trait-level "Ordering contract"). If
128 /// `params.metric` does not match [`metric`](IndexCore::metric),
129 /// implementations return [`iqdb_types::IqdbError::InvalidMetric`]. A
130 /// `query.len()` that does not match [`dim`](IndexCore::dim) returns
131 /// [`iqdb_types::IqdbError::DimensionMismatch`].
132 fn search(&self, query: &[f32], params: &SearchParams) -> Result<Vec<Hit>>;
133
134 /// Run a batch of top-`k` searches with shared `params`.
135 ///
136 /// The default implementation loops over `queries` and calls
137 /// [`search`](IndexCore::search) for each one, preserving input order in
138 /// the returned outer `Vec`. Implementers MAY override with a vectorized
139 /// path.
140 fn search_batch(&self, queries: &[&[f32]], params: &SearchParams) -> Result<Vec<Vec<Hit>>> {
141 let mut out = Vec::with_capacity(queries.len());
142 for query in queries {
143 out.push(self.search(query, params)?);
144 }
145 Ok(out)
146 }
147
148 /// The number of vectors currently searchable in the index.
149 ///
150 /// Excludes tombstoned or otherwise logically-deleted entries.
151 fn len(&self) -> usize;
152
153 /// Returns `true` when the index holds no searchable vectors.
154 ///
155 /// Default implementation: `self.len() == 0`. Implementers MAY override
156 /// if they can answer this faster than counting.
157 fn is_empty(&self) -> bool {
158 self.len() == 0
159 }
160
161 /// The dimensionality of vectors this index was configured for.
162 fn dim(&self) -> usize;
163
164 /// The distance metric this index was configured for.
165 fn metric(&self) -> DistanceMetric;
166
167 /// Flush any pending state to durable storage.
168 ///
169 /// Purely in-memory indexes return `Ok(())` immediately. Indexes that
170 /// buffer writes or persist to disk MUST commit those changes here.
171 fn flush(&mut self) -> Result<()>;
172
173 /// A runtime snapshot of the index's state.
174 ///
175 /// See [`IndexStats`] for the shape; index-specific counters live in
176 /// [`IndexStats::extra`].
177 fn stats(&self) -> IndexStats;
178}
179
180/// Typed construction for an index.
181///
182/// Adds an associated [`Config`](Index::Config) and a `Self`-returning
183/// [`new`](Index::new) to the operational surface from [`IndexCore`]. This
184/// trait is **not object-safe** — that is by design; the engine holds
185/// indexes as `Box<dyn IndexCore>` after they have been constructed
186/// through [`Index::new`].
187///
188/// Every concrete index implements both [`IndexCore`] and `Index`.
189///
190/// ## Examples
191///
192/// See the crate-level docs for a runnable mock that implements both
193/// traits.
194pub trait Index: IndexCore {
195 /// Configuration consumed at construction time.
196 ///
197 /// `Default` lets a caller spin up an index with zero configuration;
198 /// `Clone` lets the engine reuse a config across builds (for example,
199 /// when rebalancing or rebuilding shards).
200 type Config: Default + Clone;
201
202 /// Build a fresh index of `dim` vectors under `metric` with `config`.
203 ///
204 /// Returns [`iqdb_types::IqdbError::InvalidConfig`] when `dim == 0` or
205 /// when `config` does not describe a working index; implementations
206 /// SHOULD reject invalid combinations of `metric` and `config` here
207 /// rather than at first use.
208 fn new(dim: usize, metric: DistanceMetric, config: Self::Config) -> Result<Self>
209 where
210 Self: Sized;
211}