featherdb_mvcc/
wait_graph.rs

1//! Wait-for graph for deadlock detection
2//!
3//! Implements a directed graph where edges represent wait-for relationships between
4//! transactions. Used to detect cycles (deadlocks) using depth-first search.
5
6use featherdb_core::TransactionId;
7use std::collections::{HashMap, HashSet};
8
9/// Wait-for graph for deadlock detection
10///
11/// Tracks which transactions are waiting for which other transactions.
12/// Used to detect cycles (deadlocks) in the wait graph.
13pub struct WaitGraph {
14    /// Adjacency list: waiter -> set of holders it's waiting for
15    edges: HashMap<TransactionId, HashSet<TransactionId>>,
16}
17
18impl WaitGraph {
19    /// Create a new empty wait graph
20    pub fn new() -> Self {
21        Self {
22            edges: HashMap::new(),
23        }
24    }
25
26    /// Record that `waiter` is waiting for `holder` to release a lock
27    pub fn add_wait(&mut self, waiter: TransactionId, holder: TransactionId) {
28        self.edges.entry(waiter).or_default().insert(holder);
29    }
30
31    /// Remove all wait edges involving this transaction (when it commits/aborts)
32    pub fn remove_transaction(&mut self, txn: TransactionId) {
33        // Remove as waiter
34        self.edges.remove(&txn);
35        // Remove as holder from all waiters
36        for holders in self.edges.values_mut() {
37            holders.remove(&txn);
38        }
39    }
40
41    /// Detect if there's a cycle in the wait graph
42    /// Returns Some(cycle) if deadlock detected, where cycle is the list of txn IDs in the cycle
43    pub fn detect_cycle(&self) -> Option<Vec<TransactionId>> {
44        // DFS-based cycle detection
45        let mut visited = HashSet::new();
46        let mut rec_stack = HashSet::new();
47        let mut path = Vec::new();
48
49        for &start in self.edges.keys() {
50            if !visited.contains(&start) {
51                if let Some(cycle) =
52                    self.dfs_find_cycle(start, &mut visited, &mut rec_stack, &mut path)
53                {
54                    return Some(cycle);
55                }
56            }
57        }
58        None
59    }
60
61    fn dfs_find_cycle(
62        &self,
63        node: TransactionId,
64        visited: &mut HashSet<TransactionId>,
65        rec_stack: &mut HashSet<TransactionId>,
66        path: &mut Vec<TransactionId>,
67    ) -> Option<Vec<TransactionId>> {
68        visited.insert(node);
69        rec_stack.insert(node);
70        path.push(node);
71
72        if let Some(neighbors) = self.edges.get(&node) {
73            for &neighbor in neighbors {
74                if !visited.contains(&neighbor) {
75                    if let Some(cycle) = self.dfs_find_cycle(neighbor, visited, rec_stack, path) {
76                        return Some(cycle);
77                    }
78                } else if rec_stack.contains(&neighbor) {
79                    // Found cycle - extract it from path
80                    let cycle_start = path.iter().position(|&x| x == neighbor).unwrap();
81                    return Some(path[cycle_start..].to_vec());
82                }
83            }
84        }
85
86        path.pop();
87        rec_stack.remove(&node);
88        None
89    }
90
91    /// Select a victim transaction to abort (youngest = highest ID)
92    pub fn select_victim(&self, cycle: &[TransactionId]) -> TransactionId {
93        *cycle.iter().max().unwrap()
94    }
95}
96
97impl Default for WaitGraph {
98    fn default() -> Self {
99        Self::new()
100    }
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    #[test]
108    fn test_no_cycle() {
109        let mut graph = WaitGraph::new();
110        graph.add_wait(TransactionId(1), TransactionId(2));
111        graph.add_wait(TransactionId(2), TransactionId(3));
112
113        assert!(graph.detect_cycle().is_none());
114    }
115
116    #[test]
117    fn test_simple_cycle() {
118        let mut graph = WaitGraph::new();
119        // A→B, B→A deadlock
120        graph.add_wait(TransactionId(1), TransactionId(2));
121        graph.add_wait(TransactionId(2), TransactionId(1));
122
123        let cycle = graph.detect_cycle();
124        assert!(cycle.is_some());
125        let cycle = cycle.unwrap();
126        assert_eq!(cycle.len(), 2);
127        assert!(cycle.contains(&TransactionId(1)));
128        assert!(cycle.contains(&TransactionId(2)));
129    }
130
131    #[test]
132    fn test_complex_cycle() {
133        let mut graph = WaitGraph::new();
134        // A→B→C→A deadlock
135        graph.add_wait(TransactionId(1), TransactionId(2));
136        graph.add_wait(TransactionId(2), TransactionId(3));
137        graph.add_wait(TransactionId(3), TransactionId(1));
138
139        let cycle = graph.detect_cycle();
140        assert!(cycle.is_some());
141        let cycle = cycle.unwrap();
142        assert_eq!(cycle.len(), 3);
143        assert!(cycle.contains(&TransactionId(1)));
144        assert!(cycle.contains(&TransactionId(2)));
145        assert!(cycle.contains(&TransactionId(3)));
146    }
147
148    #[test]
149    fn test_remove_transaction() {
150        let mut graph = WaitGraph::new();
151        // Create a cycle: A→B→A
152        graph.add_wait(TransactionId(1), TransactionId(2));
153        graph.add_wait(TransactionId(2), TransactionId(1));
154
155        // Verify cycle exists
156        assert!(graph.detect_cycle().is_some());
157
158        // Remove one transaction
159        graph.remove_transaction(TransactionId(1));
160
161        // Cycle should be broken
162        assert!(graph.detect_cycle().is_none());
163    }
164
165    #[test]
166    fn test_remove_transaction_breaks_cycle() {
167        let mut graph = WaitGraph::new();
168        // Create a 3-node cycle: A→B→C→A
169        graph.add_wait(TransactionId(1), TransactionId(2));
170        graph.add_wait(TransactionId(2), TransactionId(3));
171        graph.add_wait(TransactionId(3), TransactionId(1));
172
173        // Verify cycle exists
174        assert!(graph.detect_cycle().is_some());
175
176        // Remove middle transaction
177        graph.remove_transaction(TransactionId(2));
178
179        // Cycle should be broken
180        assert!(graph.detect_cycle().is_none());
181    }
182
183    #[test]
184    fn test_victim_selection() {
185        let graph = WaitGraph::new();
186
187        // Test with simple cycle
188        let cycle = vec![TransactionId(1), TransactionId(2)];
189        assert_eq!(graph.select_victim(&cycle), TransactionId(2));
190
191        // Test with complex cycle - youngest (highest ID) should be selected
192        let cycle = vec![TransactionId(5), TransactionId(10), TransactionId(3)];
193        assert_eq!(graph.select_victim(&cycle), TransactionId(10));
194    }
195
196    #[test]
197    fn test_victim_selection_youngest() {
198        let graph = WaitGraph::new();
199
200        // Youngest transaction (highest ID) is selected as victim
201        let cycle = vec![TransactionId(100), TransactionId(200), TransactionId(150)];
202        assert_eq!(graph.select_victim(&cycle), TransactionId(200));
203    }
204
205    #[test]
206    fn test_multiple_waiters() {
207        let mut graph = WaitGraph::new();
208        // Multiple transactions waiting for the same holder
209        graph.add_wait(TransactionId(1), TransactionId(3));
210        graph.add_wait(TransactionId(2), TransactionId(3));
211
212        // No cycle
213        assert!(graph.detect_cycle().is_none());
214
215        // Add edge that creates cycle
216        graph.add_wait(TransactionId(3), TransactionId(1));
217
218        // Now there should be a cycle
219        assert!(graph.detect_cycle().is_some());
220    }
221
222    #[test]
223    fn test_remove_holder_from_multiple_waiters() {
224        let mut graph = WaitGraph::new();
225        // Multiple transactions waiting for the same holder
226        graph.add_wait(TransactionId(1), TransactionId(3));
227        graph.add_wait(TransactionId(2), TransactionId(3));
228        graph.add_wait(TransactionId(3), TransactionId(1));
229
230        // Verify cycle exists
231        assert!(graph.detect_cycle().is_some());
232
233        // Remove the holder
234        graph.remove_transaction(TransactionId(3));
235
236        // Should remove txn 3 as waiter AND as holder from txn 1 and 2
237        assert!(graph.detect_cycle().is_none());
238    }
239
240    #[test]
241    fn test_empty_graph() {
242        let graph = WaitGraph::new();
243        assert!(graph.detect_cycle().is_none());
244    }
245
246    #[test]
247    fn test_single_node() {
248        let mut graph = WaitGraph::new();
249        // Single transaction waiting for itself (self-deadlock)
250        graph.add_wait(TransactionId(1), TransactionId(1));
251
252        let cycle = graph.detect_cycle();
253        assert!(cycle.is_some());
254        let cycle = cycle.unwrap();
255        assert_eq!(cycle.len(), 1);
256        assert_eq!(cycle[0], TransactionId(1));
257    }
258
259    #[test]
260    fn test_multiple_disconnected_cycles() {
261        let mut graph = WaitGraph::new();
262        // First cycle: 1→2→1
263        graph.add_wait(TransactionId(1), TransactionId(2));
264        graph.add_wait(TransactionId(2), TransactionId(1));
265
266        // Second disconnected cycle: 3→4→3
267        graph.add_wait(TransactionId(3), TransactionId(4));
268        graph.add_wait(TransactionId(4), TransactionId(3));
269
270        // Should detect at least one cycle
271        assert!(graph.detect_cycle().is_some());
272    }
273
274    #[test]
275    fn test_long_chain_no_cycle() {
276        let mut graph = WaitGraph::new();
277        // Long chain without cycle: 1→2→3→4→5
278        graph.add_wait(TransactionId(1), TransactionId(2));
279        graph.add_wait(TransactionId(2), TransactionId(3));
280        graph.add_wait(TransactionId(3), TransactionId(4));
281        graph.add_wait(TransactionId(4), TransactionId(5));
282
283        assert!(graph.detect_cycle().is_none());
284    }
285
286    #[test]
287    fn test_diamond_pattern_no_cycle() {
288        let mut graph = WaitGraph::new();
289        // Diamond pattern without cycle:
290        //   1→2→4
291        //   1→3→4
292        graph.add_wait(TransactionId(1), TransactionId(2));
293        graph.add_wait(TransactionId(1), TransactionId(3));
294        graph.add_wait(TransactionId(2), TransactionId(4));
295        graph.add_wait(TransactionId(3), TransactionId(4));
296
297        assert!(graph.detect_cycle().is_none());
298    }
299}
featherdb_mvcc/wait_graph.rs

featherdb_mvcc/
wait_graph.rs
