Skip to main content

vvv_engine/
query_store.rs

1//! Immutable query checkpoints, bounded as whole query trees. Lock after operation exclusion.
2use crate::capabilities::{
3    context::{ContextSeed, ContextSession},
4    excerpts::Excerpt,
5    relationships::{RelationshipSeed, RelationshipSession},
6    search::SearchSession,
7};
8use crate::graph::query_snapshot::QuerySnapshot;
9use crate::{Cursor, EngineError, Search, SnapshotId};
10use serde::Serialize;
11use std::collections::{BTreeMap, HashMap};
12use std::hash::BuildHasher;
13use std::sync::Arc;
14use std::time::{Duration, Instant};
15
16#[derive(Debug, Clone, Copy, Serialize, serde::Deserialize, PartialEq, Eq)]
17#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
18pub struct QueryLimits {
19    pub max_queries: usize,
20    pub max_query_bytes: usize,
21    pub max_total_bytes: usize,
22    pub lifetime_seconds: u64,
23}
24impl Default for QueryLimits {
25    fn default() -> Self {
26        Self {
27            max_queries: 16,
28            max_query_bytes: 32 * 1024 * 1024,
29            max_total_bytes: 128 * 1024 * 1024,
30            lifetime_seconds: 600,
31        }
32    }
33}
34
35#[derive(Debug, Serialize)]
36pub(crate) enum QueryData {
37    Search(Search),
38    Context(ContextSeed),
39    Relationships(RelationshipSeed),
40}
41#[derive(Debug, Clone, Serialize)]
42pub(crate) enum Checkpoint {
43    Search(SearchSession),
44    Context(ContextSession),
45    Relationships(RelationshipSession),
46    Excerpt(Excerpt),
47}
48impl Checkpoint {
49    fn kind(&self) -> &'static str {
50        if matches!(self, Self::Excerpt(_)) {
51            "e"
52        } else {
53            "q"
54        }
55    }
56}
57#[derive(Debug, Serialize)]
58pub(crate) struct QueryRoot {
59    pub snapshot: QuerySnapshot,
60    pub identity: SnapshotId,
61    pub data: QueryData,
62    pub revision: u64,
63    #[serde(skip)]
64    pub created: Instant,
65}
66#[derive(Clone)]
67pub(crate) struct Lease {
68    pub id: u64,
69    pub root: Arc<QueryRoot>,
70    pub checkpoint: Checkpoint,
71}
72struct StoredQuery {
73    root: Arc<QueryRoot>,
74    checkpoints: BTreeMap<Cursor, Checkpoint>,
75    created: Instant,
76    used: Instant,
77    bytes: usize,
78}
79pub(crate) struct QueryStore {
80    nonce: String,
81    next: u64,
82    roots: HashMap<u64, StoredQuery>,
83    limits: QueryLimits,
84}
85impl Default for QueryStore {
86    fn default() -> Self {
87        Self {
88            nonce: format!(
89                "{:016x}",
90                std::collections::hash_map::RandomState::new().hash_one("vvv query store")
91            ),
92            next: 0,
93            roots: HashMap::new(),
94            limits: QueryLimits::default(),
95        }
96    }
97}
98impl QueryStore {
99    // Conservative charge includes allocation, map nodes and token overhead. Shared
100    // query data is charged once; checkpoints contain no complete source documents.
101    pub(crate) fn weight(value: &impl Serialize) -> usize {
102        serde_json::to_vec(value)
103            .expect("query state serializes")
104            .len()
105            .saturating_mul(4)
106            .saturating_add(1024)
107    }
108    pub(crate) fn allocate(&mut self) -> u64 {
109        self.next += 1;
110        self.next
111    }
112    pub(crate) fn cursor(&self, id: u64, checkpoint: &Checkpoint) -> Cursor {
113        let digest = blake3::hash(&serde_json::to_vec(checkpoint).expect("checkpoint serializes"));
114        Cursor(format!(
115            "v1.{}.{id:016x}.{}.{}",
116            self.nonce,
117            checkpoint.kind(),
118            digest.to_hex()
119        ))
120    }
121    pub(crate) fn lease(
122        &mut self,
123        cursor: &Cursor,
124        excerpt: bool,
125        revision: u64,
126        now: Instant,
127    ) -> Result<Lease, EngineError> {
128        let parts: Vec<_> = cursor.0.split('.').collect();
129        if parts.len() != 5
130            || parts[0] != "v1"
131            || parts[1].len() != 16
132            || parts[2].len() != 16
133            || parts[4].len() != 64
134            || ![parts[1], parts[2], parts[4]]
135                .iter()
136                .all(|s| s.bytes().all(|c| c.is_ascii_hexdigit()))
137            || !["q", "e"].contains(&parts[3])
138        {
139            return Err(EngineError::InvalidCursor);
140        }
141        if (parts[3] == "e") != excerpt {
142            return Err(EngineError::InvalidCursor);
143        }
144        if parts[1] != self.nonce {
145            return Err(EngineError::CursorExpired);
146        }
147        let id = u64::from_str_radix(parts[2], 16).map_err(|_| EngineError::InvalidCursor)?;
148        self.expire(now);
149        let root = self.roots.get_mut(&id).ok_or(EngineError::CursorExpired)?;
150        if root.root.revision != revision {
151            self.roots.remove(&id);
152            return Err(EngineError::StaleQuery);
153        }
154        let checkpoint = root
155            .checkpoints
156            .get(cursor)
157            .ok_or(EngineError::InvalidCursor)?
158            .clone();
159        root.used = now;
160        Ok(Lease {
161            id,
162            root: root.root.clone(),
163            checkpoint,
164        })
165    }
166    fn expire(&mut self, now: Instant) {
167        let ttl = Duration::from_secs(self.limits.lifetime_seconds);
168        self.roots
169            .retain(|_, root| now.saturating_duration_since(root.created) < ttl);
170    }
171    pub(crate) fn invalidate(&mut self, id: u64) {
172        self.roots.remove(&id);
173    }
174    pub(crate) fn publish(
175        &mut self,
176        id: u64,
177        root: Arc<QueryRoot>,
178        checkpoints: Vec<Checkpoint>,
179        now: Instant,
180    ) -> Result<(), EngineError> {
181        if now.saturating_duration_since(root.created)
182            >= Duration::from_secs(self.limits.lifetime_seconds)
183        {
184            self.invalidate(id);
185            return Err(EngineError::CursorExpired);
186        }
187        if checkpoints.is_empty() {
188            return Ok(());
189        }
190        self.expire(now);
191        let existing = self.roots.get(&id);
192        let mut additions = BTreeMap::new();
193        for checkpoint in checkpoints {
194            let cursor = self.cursor(id, &checkpoint);
195            if existing.is_none_or(|q| !q.checkpoints.contains_key(&cursor)) {
196                additions.insert(cursor, checkpoint);
197            }
198        }
199        let old_bytes = existing.map_or(0, |q| q.bytes);
200        let added_bytes = additions
201            .iter()
202            .map(|(k, v)| Self::weight(&(k, v)))
203            .sum::<usize>()
204            + if existing.is_none() {
205                Self::weight(root.as_ref())
206            } else {
207                0
208            };
209        let bytes = old_bytes.saturating_add(added_bytes);
210        if bytes > self.limits.max_query_bytes || bytes > self.limits.max_total_bytes {
211            return Err(EngineError::RetentionLimit);
212        }
213        while self
214            .roots
215            .values()
216            .map(|q| q.bytes)
217            .sum::<usize>()
218            .saturating_add(added_bytes)
219            > self.limits.max_total_bytes
220            || (!self.roots.contains_key(&id) && self.roots.len() >= self.limits.max_queries)
221        {
222            let oldest = self
223                .roots
224                .iter()
225                .filter(|(other, _)| **other != id)
226                .min_by_key(|(key, q)| (q.used, **key))
227                .map(|(key, _)| *key)
228                .ok_or(EngineError::RetentionLimit)?;
229            self.roots.remove(&oldest);
230        }
231        let entry = self.roots.entry(id).or_insert_with(|| StoredQuery {
232            created: root.created,
233            root,
234            checkpoints: BTreeMap::new(),
235            used: now,
236            bytes: 0,
237        });
238        entry.checkpoints.extend(additions);
239        entry.bytes = bytes;
240        entry.used = now;
241        Ok(())
242    }
243}
244
245#[cfg(test)]
246mod tests {
247    use super::*;
248    struct Fixture {
249        store: QueryStore,
250        root: Arc<QueryRoot>,
251        now: Instant,
252    }
253    impl Fixture {
254        fn new() -> Self {
255            let now = Instant::now();
256            let engine = crate::Engine::new(
257                crate::Workspace::new("/ws", Arc::new(crate::MemoryVfs::new())),
258                crate::Languages::new(),
259            );
260            let (_, snapshot) = QuerySnapshot::capture(&engine).unwrap();
261            let root = Arc::new(QueryRoot {
262                snapshot,
263                identity: crate::ContentId::of("query").into(),
264                data: QueryData::Search(Search {
265                    scope: Default::default(),
266                    query: crate::Query::pattern("x"),
267                    matches: vec![],
268                    skipped: vec![],
269                }),
270                revision: 0,
271                created: now,
272            });
273            Self {
274                store: QueryStore::default(),
275                root,
276                now,
277            }
278        }
279        fn add(&mut self) -> (u64, Cursor) {
280            let id = self.store.allocate();
281            let checkpoint = Checkpoint::Search(SearchSession { next: 1 });
282            let token = self.store.cursor(id, &checkpoint);
283            self.store
284                .publish(id, self.root.clone(), vec![checkpoint], self.now)
285                .unwrap();
286            (id, token)
287        }
288    }
289    #[test]
290    fn fixed_lifetime_is_not_extended_by_reads_or_checkpoint_publication() {
291        let mut f = Fixture::new();
292        let (id, token) = f.add();
293        let later = f.now + Duration::from_secs(599);
294        f.store.lease(&token, false, 0, later).unwrap();
295        f.store
296            .publish(
297                id,
298                f.root.clone(),
299                vec![Checkpoint::Search(SearchSession { next: 2 })],
300                later,
301            )
302            .unwrap();
303        let expired = f.now + Duration::from_secs(600);
304        assert!(matches!(
305            f.store.lease(&token, false, 0, expired),
306            Err(EngineError::CursorExpired)
307        ));
308        assert!(matches!(
309            f.store.publish(
310                id,
311                f.root,
312                vec![Checkpoint::Search(SearchSession { next: 3 })],
313                expired
314            ),
315            Err(EngineError::CursorExpired)
316        ));
317    }
318    #[test]
319    fn lru_evicts_whole_roots_and_replay_does_not_grow_retention() {
320        let mut f = Fixture::new();
321        f.store.limits.max_queries = 2;
322        let (id, token) = f.add();
323        let (_, old) = f.add();
324        let later = f.now + Duration::from_secs(1);
325        f.store.lease(&token, false, 0, later).unwrap();
326        let before = f.store.roots[&id].bytes;
327        f.store
328            .publish(
329                id,
330                f.root.clone(),
331                vec![Checkpoint::Search(SearchSession { next: 1 })],
332                later,
333            )
334            .unwrap();
335        assert_eq!(f.store.roots[&id].bytes, before);
336        f.add();
337        assert!(matches!(
338            f.store.lease(&old, false, 0, later),
339            Err(EngineError::CursorExpired)
340        ));
341        f.store.lease(&token, false, 0, later).unwrap();
342    }
343    #[test]
344    fn failed_admission_keeps_existing_checkpoint_and_bounds_total_bytes() {
345        let mut f = Fixture::new();
346        let (id, token) = f.add();
347        let retained = f.store.roots[&id].bytes;
348        f.store.limits.max_query_bytes = retained;
349        assert!(matches!(
350            f.store.publish(
351                id,
352                f.root.clone(),
353                vec![Checkpoint::Search(SearchSession { next: 2 })],
354                f.now
355            ),
356            Err(EngineError::RetentionLimit)
357        ));
358        assert_eq!(f.store.roots[&id].bytes, retained);
359        f.store.lease(&token, false, 0, f.now).unwrap();
360        f.store.limits.max_total_bytes = retained;
361        let (_, replacement) = f.add();
362        assert!(matches!(
363            f.store.lease(&token, false, 0, f.now),
364            Err(EngineError::CursorExpired)
365        ));
366        f.store.lease(&replacement, false, 0, f.now).unwrap();
367        assert!(f.store.roots.values().map(|q| q.bytes).sum::<usize>() <= retained);
368    }
369}