quill_sql/utils/cache/
window_lfu.rs

1use super::Replacer; // 引入定义的 trait
2use crate::buffer::FrameId;
3use crate::error::{QuillSQLError, QuillSQLResult};
4use std::collections::HashMap;
5use std::time::{Duration, Instant}; // 使用真实时间
6
7const DEFAULT_WINDOW_DURATION: Duration = Duration::from_secs(10); // 默认窗口10秒
8
9#[derive(Debug, Clone)]
10struct WindowLFUNode {
11    frequency: u64,
12    last_access_time: Instant,
13    is_evictable: bool,
14}
15
16impl WindowLFUNode {
17    fn new() -> Self {
18        Self {
19            frequency: 1, // 初始频率为1
20            last_access_time: Instant::now(),
21            is_evictable: false, // 初始不可淘汰
22        }
23    }
24}
25
26#[derive(Debug)]
27pub struct WindowLFUReplacer {
28    node_store: HashMap<FrameId, WindowLFUNode>,
29    capacity: usize,
30    current_size: usize, // 可淘汰 frame 的数量
31    window_duration: Duration,
32}
33
34// --- 实现 Replacer Trait ---
35
36impl Replacer for WindowLFUReplacer {
37    fn new(capacity: usize) -> Self {
38        Self::with_window(capacity, DEFAULT_WINDOW_DURATION)
39    }
40
41    fn record_access(&mut self, frame_id: FrameId) -> QuillSQLResult<()> {
42        let now = Instant::now();
43        if let Some(node) = self.node_store.get_mut(&frame_id) {
44            node.frequency += 1;
45            node.last_access_time = now;
46        } else {
47            // BufferManager 应该保证在调用 record_access 前已确保有空间
48            if self.node_store.len() >= self.capacity {
49                // 通常不应在这里失败，BPM 应该先调用 evict
50                return Err(QuillSQLError::Internal(format!(
51                    "WindowLFU capacity {} reached when accessing new frame {}",
52                    self.capacity, frame_id
53                )));
54            }
55            self.node_store.insert(frame_id, WindowLFUNode::new());
56            // 新加入的 frame 初始 pin_count > 0，所以不可淘汰，current_size 不变
57        }
58        Ok(())
59    }
60
61    fn evict(&mut self) -> Option<FrameId> {
62        if self.current_size == 0 {
63            return None;
64        }
65
66        let now = Instant::now();
67        let mut victim_frame = None;
68        // 使用 Option<(u64, Instant)> 来存储优先级 (有效频率, 最后访问时间)
69        // 有效频率越小越优先，时间越早越优先
70        let mut min_priority: Option<(u64, Instant)> = None;
71
72        for (&frame_id, node) in self.node_store.iter() {
73            if !node.is_evictable {
74                continue;
75            }
76
77            let effective_frequency =
78                if now.duration_since(node.last_access_time) <= self.window_duration {
79                    // 在窗口内，使用原始频率
80                    node.frequency
81                } else {
82                    // 超出窗口，频率视为最低 (0)
83                    0
84                };
85
86            let current_priority = (effective_frequency, node.last_access_time);
87
88            match min_priority {
89                None => {
90                    min_priority = Some(current_priority);
91                    victim_frame = Some(frame_id);
92                }
93                Some(min_p) => {
94                    // 比较优先级：先比频率（越小越优先），再比时间（越早越优先）
95                    if effective_frequency < min_p.0
96                        || (effective_frequency == min_p.0 && node.last_access_time < min_p.1)
97                    {
98                        min_priority = Some(current_priority);
99                        victim_frame = Some(frame_id);
100                    }
101                }
102            }
103        }
104
105        if let Some(victim_id) = victim_frame {
106            self.remove(victim_id); // remove 会处理 node_store 和 current_size
107            Some(victim_id)
108        } else {
109            None // 没有找到可驱逐的 frame
110        }
111    }
112
113    fn set_evictable(&mut self, frame_id: FrameId, set_evictable: bool) -> QuillSQLResult<()> {
114        if let Some(node) = self.node_store.get_mut(&frame_id) {
115            let was_evictable = node.is_evictable;
116            node.is_evictable = set_evictable;
117            if set_evictable && !was_evictable {
118                self.current_size += 1;
119            } else if !set_evictable && was_evictable {
120                // 检查确保 current_size 不会小于 0
121                if self.current_size > 0 {
122                    self.current_size -= 1;
123                } else {
124                    // Log warning or handle error: trying to decrease size below zero
125                    eprintln!("Warning: Attempted to decrease WindowLFUReplacer size below zero for frame {}", frame_id);
126                }
127            }
128            Ok(())
129        } else {
130            Err(QuillSQLError::Internal(format!(
131                "Frame {} not found in WindowLFUReplacer::set_evictable",
132                frame_id
133            )))
134        }
135    }
136
137    fn remove(&mut self, frame_id: FrameId) {
138        if let Some(node) = self.node_store.remove(&frame_id) {
139            if node.is_evictable {
140                if self.current_size > 0 {
141                    self.current_size -= 1;
142                } else {
143                    eprintln!("Warning: Attempted to decrease WindowLFUReplacer size below zero during remove for frame {}", frame_id);
144                }
145            }
146        }
147    }
148
149    fn size(&self) -> usize {
150        self.current_size
151    }
152}
153
154// --- Window-LFU 特定方法 ---
155impl WindowLFUReplacer {
156    /// 创建带有指定窗口大小的 Replacer
157    pub fn with_window(capacity: usize, window_duration: Duration) -> Self {
158        Self {
159            node_store: HashMap::with_capacity(capacity),
160            capacity,
161            current_size: 0,
162            window_duration,
163        }
164    }
165}
166
167// --- 测试用例 ---
168#[cfg(test)]
169mod tests {
170    use super::*;
171    use std::thread::sleep;
172
173    #[test]
174    fn test_window_lfu_basic_eviction() {
175        let mut replacer = WindowLFUReplacer::new(3);
176
177        replacer.record_access(1).unwrap(); // freq=1, time=t0
178        replacer.record_access(2).unwrap(); // freq=1, time=t1
179        replacer.record_access(3).unwrap(); // freq=1, time=t2
180
181        replacer.set_evictable(1, true).unwrap();
182        replacer.set_evictable(2, true).unwrap();
183        replacer.set_evictable(3, true).unwrap();
184        assert_eq!(replacer.size(), 3);
185
186        // Frame 1 最先访问，频率相同，应首先被驱逐
187        assert_eq!(replacer.evict(), Some(1));
188        assert_eq!(replacer.size(), 2);
189
190        // Frame 2 其次
191        assert_eq!(replacer.evict(), Some(2));
192        assert_eq!(replacer.size(), 1);
193
194        // Frame 3 最后
195        assert_eq!(replacer.evict(), Some(3));
196        assert_eq!(replacer.size(), 0);
197
198        assert_eq!(replacer.evict(), None);
199    }
200
201    #[test]
202    fn test_window_lfu_frequency_effect() {
203        let mut replacer = WindowLFUReplacer::new(3);
204
205        replacer.record_access(1).unwrap(); // freq=1
206        replacer.record_access(2).unwrap(); // freq=1
207        replacer.record_access(3).unwrap(); // freq=1
208
209        replacer.record_access(1).unwrap(); // freq=2
210        replacer.record_access(1).unwrap(); // freq=3
211        replacer.record_access(2).unwrap(); // freq=2
212
213        replacer.set_evictable(1, true).unwrap();
214        replacer.set_evictable(2, true).unwrap();
215        replacer.set_evictable(3, true).unwrap();
216
217        // Frame 3 频率最低 (1)，应首先被驱逐
218        assert_eq!(replacer.evict(), Some(3));
219        // Frame 2 频率其次 (2)
220        assert_eq!(replacer.evict(), Some(2));
221        // Frame 1 频率最高 (3)
222        assert_eq!(replacer.evict(), Some(1));
223    }
224
225    #[test]
226    fn test_window_lfu_window_effect() {
227        // 使用较小的窗口时间进行测试
228        let window = Duration::from_millis(50);
229        let mut replacer = WindowLFUReplacer::with_window(3, window);
230
231        replacer.record_access(1).unwrap(); // freq=1, time=t0
232        sleep(window / 2);
233        replacer.record_access(2).unwrap(); // freq=1, time=t1 (in window)
234        replacer.record_access(2).unwrap(); // freq=2, time=t2 (in window)
235
236        replacer.set_evictable(1, true).unwrap();
237        replacer.set_evictable(2, true).unwrap();
238
239        // 等待超过窗口时间
240        sleep(window * 2);
241
242        replacer.record_access(3).unwrap(); // freq=1, time=t3 (now frame 1 and 2 are out of window)
243        replacer.set_evictable(3, true).unwrap();
244
245        // Frame 1 和 2 都超出了窗口，频率视为 0
246        // Frame 1 的 last_access_time 最早，应该被驱逐
247        assert_eq!(replacer.evict(), Some(1));
248
249        // Frame 2 其次 (超出窗口)
250        assert_eq!(replacer.evict(), Some(2));
251
252        // Frame 3 在窗口内
253        assert_eq!(replacer.evict(), Some(3));
254    }
255
256    #[test]
257    fn test_window_lfu_set_evictable() {
258        let mut replacer = WindowLFUReplacer::new(3);
259
260        replacer.record_access(1).unwrap();
261        replacer.record_access(2).unwrap();
262        replacer.record_access(3).unwrap();
263
264        replacer.set_evictable(1, true).unwrap();
265        replacer.set_evictable(3, true).unwrap();
266        assert_eq!(replacer.size(), 2);
267
268        // Frame 2 不可淘汰，Frame 1 先访问，被驱逐
269        assert_eq!(replacer.evict(), Some(1));
270        assert_eq!(replacer.size(), 1);
271
272        // 使 Frame 2 可淘汰，Frame 3 不可淘汰
273        replacer.set_evictable(2, true).unwrap();
274        replacer.set_evictable(3, false).unwrap();
275        assert_eq!(replacer.size(), 1);
276
277        // 只能驱逐 Frame 2
278        assert_eq!(replacer.evict(), Some(2));
279        assert_eq!(replacer.size(), 0);
280    }
281
282    #[test]
283    fn test_window_lfu_remove() {
284        let mut replacer = WindowLFUReplacer::new(3);
285        replacer.record_access(1).unwrap();
286        replacer.record_access(2).unwrap();
287        replacer.set_evictable(1, true).unwrap();
288        replacer.set_evictable(2, true).unwrap();
289        assert_eq!(replacer.size(), 2);
290
291        replacer.remove(1); // 移除可淘汰的 frame 1
292        assert_eq!(replacer.size(), 1);
293        assert!(replacer.node_store.get(&1).is_none());
294
295        replacer.record_access(3).unwrap(); // 添加 frame 3，初始不可淘汰
296        assert_eq!(replacer.size(), 1); // size 不变
297
298        replacer.remove(3); // 移除不可淘汰的 frame 3
299        assert_eq!(replacer.size(), 1); // size 不变
300        assert!(replacer.node_store.get(&3).is_none());
301
302        assert_eq!(replacer.evict(), Some(2)); // 只能淘汰 frame 2
303    }
304
305    #[test]
306    fn test_window_lfu_capacity() {
307        let mut replacer = WindowLFUReplacer::new(2);
308        replacer.record_access(1).unwrap();
309        replacer.record_access(2).unwrap();
310        replacer.set_evictable(1, true).unwrap();
311        replacer.set_evictable(2, true).unwrap();
312
313        // 尝试访问超出容量的 frame，应该失败（或由 BPM 处理）
314        // 这里我们测试 record_access 在容量满时的行为 (假设它会报错)
315        assert!(replacer.record_access(3).is_err());
316
317        // 驱逐一个
318        assert_eq!(replacer.evict(), Some(1));
319
320        // 现在可以访问了 (假设 BPM 调用 record_access)
321        replacer.record_access(3).unwrap();
322        replacer.set_evictable(3, true).unwrap();
323        assert_eq!(replacer.size(), 2);
324        assert!(replacer.node_store.contains_key(&3));
325    }
326}
quill_sql/utils/cache/window_lfu.rs

quill_sql/utils/cache/
window_lfu.rs
