Skip to main content

uqa_execution/row_locks/
retry_cache.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Work-memory-bounded committed-row override store for tuple-local row-lock rechecks. One instance exists per SQL statement; every locking scope of the statement shares it so repeated occurrences of one changed tuple fetch the committed override exactly once.
8
9use parking_lot::Mutex;
10use rusqlite::OptionalExtension;
11use std::collections::HashMap;
12use std::sync::Arc;
13use tempfile::TempDir;
14use uqa_core::Value;
15use uqa_sql::SQLError;
16use uqa_storage::{DocumentMetadata, StoredDocument};
17
18pub trait CommittedRowSource {
19    fn get_committed_document(
20        &self,
21        table: &str,
22        doc_id: uqa_core::DocId,
23    ) -> Result<Option<StoredDocument>, SQLError>;
24}
25
26pub struct RowLockRetryCache {
27    state: Mutex<RetryCacheState>,
28    row_locks: Arc<crate::row_locks::RowLockManager>,
29    _change_observation: crate::row_locks::RowChangeObservation,
30    snapshot_baseline: Mutex<crate::row_locks::RowChangeBaseline>,
31}
32
33struct RetryCacheState {
34    budget_bytes: usize,
35    memory_bytes: usize,
36    memory: HashMap<Vec<u8>, Vec<u8>>,
37    disk: Option<DiskRetryCache>,
38}
39
40struct DiskRetryCache {
41    connection: rusqlite::Connection,
42    _directory: TempDir,
43}
44
45/// Latest committed image of one row selected under a pending row lock. A primary-key rewrite surfaces the successor identity so the recheck can lock and return the row the blocker moved the tuple to.
46#[derive(Clone)]
47pub enum RetryRowOverride {
48    Deleted,
49    Present {
50        doc_id: uqa_core::DocId,
51        document: StoredDocument,
52    },
53}
54
55impl RowLockRetryCache {
56    pub fn new(
57        budget_bytes: usize,
58        row_locks: Arc<crate::row_locks::RowLockManager>,
59        snapshot_baseline: crate::row_locks::RowChangeBaseline,
60    ) -> Self {
61        let change_observation = row_locks.begin_change_observation();
62        Self {
63            state: Mutex::new(RetryCacheState {
64                budget_bytes: budget_bytes.max(1),
65                memory_bytes: 0,
66                memory: HashMap::new(),
67                disk: None,
68            }),
69            row_locks,
70            _change_observation: change_observation,
71            snapshot_baseline: Mutex::new(snapshot_baseline),
72        }
73    }
74
75    pub fn set_snapshot_baseline(&self, baseline: crate::row_locks::RowChangeBaseline) {
76        *self.snapshot_baseline.lock() = baseline;
77    }
78
79    /// Report whether another transaction committed a change to `doc_id` that conflicts with the requested lock strength after this statement's snapshot, following primary-key rewrites to the final target identity. `PostgreSQL` 18 does not recheck a `FOR KEY SHARE` candidate after a compatible non-key update, so compatible mutation strengths return `None` here.
80    pub fn conflicting_change_target_since_snapshot(
81        &self,
82        table: &str,
83        doc_id: uqa_core::DocId,
84        strength: uqa_sql::ast::LockStrength,
85    ) -> Result<crate::row_locks::RowChangeTarget, SQLError> {
86        let baseline = self.snapshot_baseline.lock().clone();
87        self.row_locks
88            .conflicting_change_target_after(table, doc_id, &baseline, strength)
89    }
90
91    /// Fetch the latest committed image for a changed candidate row, memoized per (table, original doc id, lock strength) across duplicate occurrences in the statement. Different strengths cannot share an image because a non-key update may proceed after `FOR KEY SHARE` but conflict with a stronger later scope.
92    pub fn committed_override(
93        &self,
94        source: &dyn CommittedRowSource,
95        table: &str,
96        original_doc_id: uqa_core::DocId,
97        target_doc_id: uqa_core::DocId,
98        strength: uqa_sql::ast::LockStrength,
99    ) -> Result<RetryRowOverride, SQLError> {
100        let key = retry_row_key(table, original_doc_id, strength);
101        if let Some(value) = self.lookup(&key)? {
102            return decode_override(&value);
103        }
104        let document = source.get_committed_document(table, target_doc_id)?;
105        let row_override = match document {
106            Some(document) => RetryRowOverride::Present {
107                doc_id: target_doc_id,
108                document,
109            },
110            None => RetryRowOverride::Deleted,
111        };
112        self.insert(key, &encode_override(&row_override)?)?;
113        Ok(row_override)
114    }
115
116    fn lookup(&self, key: &[u8]) -> Result<Option<Value>, SQLError> {
117        let state = self.state.lock();
118        let encoded = if let Some(disk) = state.disk.as_ref() {
119            disk.lookup(key)?
120        } else {
121            state.memory.get(key).cloned()
122        };
123        encoded.map(|encoded| decode_value(&encoded)).transpose()
124    }
125
126    fn insert(&self, key: Vec<u8>, value: &Value) -> Result<(), SQLError> {
127        let encoded = encode_value(value)?;
128        let mut state = self.state.lock();
129        if let Some(disk) = state.disk.as_mut() {
130            return disk.insert(&key, &encoded);
131        }
132        if state.memory.contains_key(&key) {
133            return Ok(());
134        }
135        let entry_bytes = key
136            .len()
137            .checked_add(encoded.len())
138            .ok_or_else(|| SQLError::Internal("row-lock retry cache entry size overflow".into()))?;
139        let would_exceed = state
140            .memory_bytes
141            .checked_add(entry_bytes)
142            .is_none_or(|bytes| bytes > state.budget_bytes);
143        if would_exceed {
144            state.migrate_to_disk()?;
145            return state
146                .disk
147                .as_mut()
148                .ok_or_else(|| SQLError::Internal("row-lock retry cache spill is absent".into()))?
149                .insert(&key, &encoded);
150        }
151        state.memory_bytes += entry_bytes;
152        state.memory.insert(key, encoded);
153        Ok(())
154    }
155}
156
157fn encode_override(row_override: &RetryRowOverride) -> Result<Value, SQLError> {
158    Ok(match row_override {
159        RetryRowOverride::Deleted => Value::List(vec![Value::Bool(false)]),
160        RetryRowOverride::Present { doc_id, document } => {
161            let doc_id = i64::try_from(*doc_id).map_err(|_| {
162                SQLError::Internal(format!(
163                    "row-lock retry override doc id {doc_id} exceeds the storable range"
164                ))
165            })?;
166            Value::List(vec![
167                Value::Bool(true),
168                Value::Int(doc_id),
169                Value::Map(document.fields().clone()),
170                document
171                    .metadata()
172                    .tuple_xmin()
173                    .map_or(Value::Null, |xmin| Value::Int(i64::from(xmin))),
174            ])
175        }
176    })
177}
178
179fn decode_override(value: &Value) -> Result<RetryRowOverride, SQLError> {
180    match value {
181        Value::List(values) if matches!(values.as_slice(), [Value::Bool(false)]) => {
182            Ok(RetryRowOverride::Deleted)
183        }
184        Value::List(values) => match values.as_slice() {
185            [Value::Bool(true), Value::Int(doc_id), Value::Map(document), tuple_xmin]
186                if *doc_id >= 0 =>
187            {
188                let metadata = match tuple_xmin {
189                    Value::Null => DocumentMetadata::default(),
190                    Value::Int(xmin) => {
191                        let xmin = u32::try_from(*xmin).map_err(|_| {
192                            SQLError::Internal(
193                                "row-lock retry row has an invalid tuple xmin".into(),
194                            )
195                        })?;
196                        DocumentMetadata::with_tuple_xmin(xmin)
197                    }
198                    _ => {
199                        return Err(SQLError::Internal(
200                            "row-lock retry row has an invalid tuple xmin".into(),
201                        ));
202                    }
203                };
204                Ok(RetryRowOverride::Present {
205                    doc_id: *doc_id as uqa_core::DocId,
206                    document: StoredDocument::with_metadata(document.clone(), metadata),
207                })
208            }
209            _ => Err(SQLError::Internal(
210                "row-lock retry row has an invalid cache payload".into(),
211            )),
212        },
213        _ => Err(SQLError::Internal(
214            "row-lock retry row has an invalid cache payload".into(),
215        )),
216    }
217}
218
219fn retry_row_key(
220    table: &str,
221    doc_id: uqa_core::DocId,
222    strength: uqa_sql::ast::LockStrength,
223) -> Vec<u8> {
224    let mut key = Vec::with_capacity(32 + table.len());
225    key.extend_from_slice(b"\0uqa-retry-row\0");
226    key.extend_from_slice(&(table.len() as u64).to_be_bytes());
227    key.extend_from_slice(table.as_bytes());
228    key.extend_from_slice(&doc_id.to_be_bytes());
229    key.push(match strength {
230        uqa_sql::ast::LockStrength::ForKeyShare => 0,
231        uqa_sql::ast::LockStrength::ForShare => 1,
232        uqa_sql::ast::LockStrength::ForNoKeyUpdate => 2,
233        uqa_sql::ast::LockStrength::ForUpdate => 3,
234    });
235    key
236}
237
238impl RetryCacheState {
239    fn migrate_to_disk(&mut self) -> Result<(), SQLError> {
240        if self.disk.is_some() {
241            return Ok(());
242        }
243        self.migrate_into_disk(DiskRetryCache::new()?)
244    }
245
246    fn migrate_into_disk(&mut self, mut disk: DiskRetryCache) -> Result<(), SQLError> {
247        disk.insert_all(&self.memory)?;
248        self.memory.clear();
249        self.memory_bytes = 0;
250        self.disk = Some(disk);
251        Ok(())
252    }
253}
254
255impl DiskRetryCache {
256    fn new() -> Result<Self, SQLError> {
257        let directory = tempfile::Builder::new()
258            .prefix("uqa-row-lock-retry-")
259            .tempdir()
260            .map_err(|error| {
261                SQLError::Internal(format!("create row-lock retry cache directory: {error}"))
262            })?;
263        let connection = crate::temporary_database::open(&directory.path().join("cache.sqlite"))
264            .map_err(|error| SQLError::Internal(format!("open row-lock retry cache: {error}")))?;
265        connection
266            .execute_batch(
267                "PRAGMA journal_mode=OFF; PRAGMA synchronous=OFF; CREATE TABLE retry_cache (cache_key BLOB PRIMARY KEY, cache_value BLOB NOT NULL) WITHOUT ROWID",
268            )
269            .map_err(|error| {
270                SQLError::Internal(format!("initialize row-lock retry cache: {error}"))
271            })?;
272        Ok(Self {
273            connection,
274            _directory: directory,
275        })
276    }
277
278    fn lookup(&self, key: &[u8]) -> Result<Option<Vec<u8>>, SQLError> {
279        self.connection
280            .query_row(
281                "SELECT cache_value FROM retry_cache WHERE cache_key = ?1",
282                [key],
283                |row| row.get(0),
284            )
285            .optional()
286            .map_err(|error| SQLError::Internal(format!("read row-lock retry cache: {error}")))
287    }
288
289    fn insert(&mut self, key: &[u8], value: &[u8]) -> Result<(), SQLError> {
290        self.connection
291            .execute(
292                "INSERT OR IGNORE INTO retry_cache(cache_key, cache_value) VALUES (?1, ?2)",
293                (key, value),
294            )
295            .map_err(|error| SQLError::Internal(format!("write row-lock retry cache: {error}")))?;
296        Ok(())
297    }
298
299    fn insert_all(&mut self, entries: &HashMap<Vec<u8>, Vec<u8>>) -> Result<(), SQLError> {
300        let transaction = self.connection.transaction().map_err(|error| {
301            SQLError::Internal(format!("begin row-lock retry cache spill: {error}"))
302        })?;
303        {
304            let mut statement = transaction
305                .prepare(
306                    "INSERT OR IGNORE INTO retry_cache(cache_key, cache_value) VALUES (?1, ?2)",
307                )
308                .map_err(|error| {
309                    SQLError::Internal(format!("prepare row-lock retry cache spill: {error}"))
310                })?;
311            for (key, value) in entries {
312                statement.execute((key, value)).map_err(|error| {
313                    SQLError::Internal(format!("spill row-lock retry cache entry: {error}"))
314                })?;
315            }
316        }
317        transaction.commit().map_err(|error| {
318            SQLError::Internal(format!("commit row-lock retry cache spill: {error}"))
319        })
320    }
321}
322
323fn encode_value(value: &Value) -> Result<Vec<u8>, SQLError> {
324    let mut encoded = Vec::new();
325    ciborium::ser::into_writer(value, &mut encoded).map_err(|error| {
326        SQLError::Internal(format!("encode row-lock retry override value: {error}"))
327    })?;
328    Ok(encoded)
329}
330
331fn decode_value(encoded: &[u8]) -> Result<Value, SQLError> {
332    ciborium::de::from_reader(encoded).map_err(|error| {
333        SQLError::Internal(format!("decode row-lock retry override value: {error}"))
334    })
335}
336
337#[cfg(test)]
338mod tests {
339    use super::*;
340
341    fn cache_directory(disk: &DiskRetryCache) -> std::path::PathBuf {
342        std::path::Path::new(disk.connection.path().expect("persistent retry cache"))
343            .parent()
344            .expect("private cache directory")
345            .to_path_buf()
346    }
347
348    #[test]
349    fn failed_retry_cache_migration_preserves_memory_entries() {
350        let key = b"row".to_vec();
351        let value = b"value".to_vec();
352        let mut state = RetryCacheState {
353            budget_bytes: 1,
354            memory_bytes: key.len() + value.len(),
355            memory: HashMap::from([(key.clone(), value.clone())]),
356            disk: None,
357        };
358        let disk = DiskRetryCache::new().unwrap();
359        let path = cache_directory(&disk);
360        disk.connection
361            .execute("DROP TABLE retry_cache", [])
362            .unwrap();
363
364        assert!(state.migrate_into_disk(disk).is_err());
365        assert_eq!(state.memory.get(&key), Some(&value));
366        assert_eq!(state.memory_bytes, key.len() + value.len());
367        assert!(state.disk.is_none());
368        assert!(!path.exists());
369    }
370
371    #[cfg(not(target_os = "emscripten"))]
372    #[test]
373    fn committed_retry_images_are_encrypted_and_removed_with_the_owner() {
374        const SECRET: &[u8] = b"private-committed-row-retry-secret-marker";
375        let mut disk = DiskRetryCache::new().unwrap();
376        let path = cache_directory(&disk);
377        disk.insert_all(&HashMap::from([(b"row".to_vec(), SECRET.to_vec())]))
378            .unwrap();
379        assert_eq!(disk.lookup(b"row").unwrap().as_deref(), Some(SECRET));
380        for entry in std::fs::read_dir(&path).unwrap() {
381            let bytes = std::fs::read(entry.unwrap().path()).unwrap();
382            assert!(!bytes.windows(SECRET.len()).any(|bytes| bytes == SECRET));
383        }
384        drop(disk);
385        assert!(!path.exists());
386    }
387}