foyer_storage/engine/block/
eviction.rs

1// Copyright 2026 foyer Project Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::{
16    collections::{HashSet, VecDeque},
17    fmt::Debug,
18    sync::atomic::Ordering,
19};
20
21use foyer_common::strict_assert;
22use itertools::Itertools;
23
24use crate::engine::block::manager::{Block, BlockId};
25
26/// Eviction related information for eviction picker to make decisions.
27#[derive(Debug)]
28pub struct EvictionInfo<'a> {
29    /// All blocks in the disk cache.
30    pub blocks: &'a [Block],
31    /// Evictable blocks.
32    pub evictable: &'a HashSet<BlockId>,
33    /// Clean blocks counts.
34    pub clean: usize,
35}
36
37/// The eviction picker for the disk cache.
38pub trait EvictionPicker: Send + Sync + 'static + Debug {
39    /// Init the eviction picker with information.
40    #[expect(unused_variables)]
41    fn init(&mut self, blocks: &[BlockId], block_size: usize) {}
42
43    /// Pick a block to evict.
44    ///
45    /// `pick` can return `None` if no block can be picked based on its rules, and the next picker will be used.
46    ///
47    /// If no picker picks a block, the disk cache will pick randomly pick one.
48    fn pick(&mut self, info: EvictionInfo<'_>) -> Option<BlockId>;
49
50    /// Notify the picker that a block is ready to pick.
51    fn on_block_evictable(&mut self, info: EvictionInfo<'_>, block: BlockId);
52
53    /// Notify the picker that a block is evicted.
54    fn on_block_evict(&mut self, info: EvictionInfo<'_>, block: BlockId);
55}
56
57/// A picker that pick block to eviction with a FIFO behavior.
58#[derive(Debug)]
59pub struct FifoPicker {
60    queue: VecDeque<BlockId>,
61    blocks: usize,
62    probations: usize,
63    probation_ratio: f64,
64}
65
66impl Default for FifoPicker {
67    fn default() -> Self {
68        Self::new(0.1)
69    }
70}
71
72impl FifoPicker {
73    /// Create a new [`FifoPicker`] with the given `probation_ratio` (0.0 ~ 1.0).
74    ///
75    /// The `probation_ratio` is the ratio of blocks that will be marked as probation.
76    /// The blocks that are marked as probation will be evicted first.
77    ///
78    /// The default value is 0.1.
79    pub fn new(probation_ratio: f64) -> Self {
80        assert!(
81            (0.0..=1.0).contains(&probation_ratio),
82            "probation ratio {probation_ratio} must be in [0.0, 1.0]"
83        );
84        Self {
85            queue: VecDeque::new(),
86            blocks: 0,
87            probations: 0,
88            probation_ratio,
89        }
90    }
91}
92
93impl FifoPicker {
94    fn mark_probation(&self, info: EvictionInfo<'_>) {
95        let marks = self.probations.saturating_sub(info.clean);
96        self.queue.iter().take(marks).for_each(|rid| {
97            if info.evictable.contains(rid) {
98                info.blocks[*rid as usize]
99                    .statistics()
100                    .probation
101                    .store(true, Ordering::Relaxed);
102                tracing::trace!(rid, "[fifo picker]: mark probation");
103            }
104        });
105    }
106}
107
108impl EvictionPicker for FifoPicker {
109    fn init(&mut self, blocks: &[BlockId], _: usize) {
110        self.blocks = blocks.len();
111        let probations = (self.blocks as f64 * self.probation_ratio).floor() as usize;
112        self.probations = probations.clamp(0, self.blocks);
113    }
114
115    fn pick(&mut self, info: EvictionInfo<'_>) -> Option<BlockId> {
116        tracing::trace!(evictable = ?info.evictable, clean = info.clean, queue = ?self.queue, "[fifo picker]: pick");
117        self.mark_probation(info);
118        let candidate = self.queue.front().copied();
119        tracing::trace!("[fifo picker]: pick {candidate:?}");
120        candidate
121    }
122
123    fn on_block_evictable(&mut self, _: EvictionInfo<'_>, block: BlockId) {
124        tracing::trace!(queue = ?self.queue, "[fifo picker]: {block} is evictable");
125        self.queue.push_back(block);
126    }
127
128    fn on_block_evict(&mut self, _: EvictionInfo<'_>, block: BlockId) {
129        tracing::trace!(queue = ?self.queue, "[fifo picker]: {block} is evicted");
130        let index = self.queue.iter().position(|r| r == &block).unwrap();
131        self.queue.remove(index);
132    }
133}
134
135/// Evict the block with the largest invalid data ratio.
136///
137/// If the largest invalid data ratio is less than the threshold, no reblockgion will be picked.
138#[derive(Debug)]
139pub struct InvalidRatioPicker {
140    threshold: f64,
141    block_size: usize,
142}
143
144impl InvalidRatioPicker {
145    /// Create [`InvalidRatioPicker`] with the given `threshold` (0.0 ~ 1.0).
146    pub fn new(threshold: f64) -> Self {
147        let ratio = threshold.clamp(0.0, 1.0);
148        Self {
149            threshold: ratio,
150            block_size: 0,
151        }
152    }
153}
154
155impl EvictionPicker for InvalidRatioPicker {
156    fn init(&mut self, _: &[BlockId], block_size: usize) {
157        self.block_size = block_size;
158    }
159
160    fn pick(&mut self, info: EvictionInfo<'_>) -> Option<BlockId> {
161        strict_assert!(self.block_size > 0);
162
163        let mut data = info
164            .evictable
165            .iter()
166            .map(|rid| {
167                (
168                    *rid,
169                    info.blocks[*rid as usize].statistics().invalid.load(Ordering::Relaxed),
170                )
171            })
172            .collect_vec();
173        data.sort_by_key(|(_, invalid)| *invalid);
174
175        let (rid, invalid) = data.last().copied()?;
176        if (invalid as f64 / self.block_size as f64) < self.threshold {
177            return None;
178        }
179        tracing::trace!("[invalid ratio picker]: pick {rid:?}");
180        Some(rid)
181    }
182
183    fn on_block_evictable(&mut self, _: EvictionInfo<'_>, block: BlockId) {
184        tracing::trace!("[invalid ratio picker]: {block} is evictable");
185    }
186
187    fn on_block_evict(&mut self, _: EvictionInfo<'_>, block: BlockId) {
188        tracing::trace!("[invalid ratio picker]: {block} is evicted");
189    }
190}
191
192#[cfg(test)]
193mod tests {
194    use std::{collections::HashSet, sync::Arc};
195
196    use foyer_common::spawn::Spawner;
197    use itertools::Itertools;
198
199    use super::*;
200    use crate::{
201        engine::block::manager::Block,
202        io::{device::noop::NoopPartition, engine::IoEngineBuildContext},
203        IoEngineConfig, NoopIoEngineConfig,
204    };
205
206    #[test_log::test(tokio::test)]
207    async fn test_fifo_picker() {
208        let mut picker = FifoPicker::new(0.1);
209        let mock_io_engine = NoopIoEngineConfig
210            .boxed()
211            .build(IoEngineBuildContext {
212                spawner: Spawner::current(),
213            })
214            .await
215            .unwrap();
216
217        let blocks = (0..10)
218            .map(|rid| Block::new_for_test(rid, Arc::<NoopPartition>::default(), mock_io_engine.clone()))
219            .collect_vec();
220        let mut evictable = HashSet::new();
221
222        fn info<'a>(blocks: &'a [Block], evictable: &'a HashSet<BlockId>, dirty: usize) -> EvictionInfo<'a> {
223            EvictionInfo {
224                blocks,
225                evictable,
226                clean: blocks.len() - evictable.len() - dirty,
227            }
228        }
229
230        fn check(block: &[Block], probations: impl IntoIterator<Item = BlockId>) {
231            let probations = probations.into_iter().collect::<HashSet<_>>();
232            for rid in 0..block.len() as BlockId {
233                if probations.contains(&rid) {
234                    assert!(
235                        block[rid as usize].statistics().probation.load(Ordering::Relaxed),
236                        "probations {probations:?}, assert {rid} is probation failed"
237                    );
238                } else {
239                    assert!(
240                        !block[rid as usize].statistics().probation.load(Ordering::Relaxed),
241                        "probations {probations:?}, assert {rid} is not probation failed"
242                    );
243                }
244            }
245        }
246
247        picker.init(&(0..10).collect_vec(), 0);
248
249        // mark 0..10 evictable in order
250        (0..10).for_each(|i| {
251            evictable.insert(i as _);
252            picker.on_block_evictable(info(&blocks, &evictable, 0), i);
253        });
254
255        // evict 0, mark 0 probation.
256        assert_eq!(picker.pick(info(&blocks, &evictable, 0)), Some(0));
257        check(&blocks, [0]);
258        evictable.remove(&0);
259        picker.on_block_evict(info(&blocks, &evictable, 1), 0);
260
261        // evict 1, with 1 dirty block, mark 1 probation.
262        assert_eq!(picker.pick(info(&blocks, &evictable, 1)), Some(1));
263        check(&blocks, [0, 1]);
264        evictable.remove(&1);
265        picker.on_block_evict(info(&blocks, &evictable, 2), 1);
266
267        // evict 2 with 1 dirty block, mark no block probation.
268        assert_eq!(picker.pick(info(&blocks, &evictable, 1)), Some(2));
269        check(&blocks, [0, 1]);
270        evictable.remove(&2);
271        picker.on_block_evict(info(&blocks, &evictable, 2), 2);
272
273        picker.on_block_evict(info(&blocks, &evictable, 3), 3);
274        evictable.remove(&3);
275        picker.on_block_evict(info(&blocks, &evictable, 4), 5);
276        evictable.remove(&5);
277        picker.on_block_evict(info(&blocks, &evictable, 5), 7);
278        evictable.remove(&7);
279        picker.on_block_evict(info(&blocks, &evictable, 6), 9);
280        evictable.remove(&9);
281
282        picker.on_block_evict(info(&blocks, &evictable, 7), 4);
283        evictable.remove(&4);
284        picker.on_block_evict(info(&blocks, &evictable, 8), 6);
285        evictable.remove(&6);
286        picker.on_block_evict(info(&blocks, &evictable, 9), 8);
287        evictable.remove(&8);
288    }
289
290    #[test_log::test(tokio::test)]
291    async fn test_invalid_ratio_picker() {
292        let mut picker = InvalidRatioPicker::new(0.5);
293        picker.init(&(0..10).collect_vec(), 10);
294
295        let mock_io_engine = NoopIoEngineConfig
296            .boxed()
297            .build(IoEngineBuildContext {
298                spawner: Spawner::current(),
299            })
300            .await
301            .unwrap();
302
303        let blocks = (0..10)
304            .map(|rid| Block::new_for_test(rid, Arc::<NoopPartition>::default(), mock_io_engine.clone()))
305            .collect_vec();
306        let mut evictable = HashSet::new();
307
308        (0..10).for_each(|i| {
309            blocks[i].statistics().invalid.fetch_add(i as _, Ordering::Relaxed);
310            evictable.insert(i as BlockId);
311        });
312
313        fn info<'a>(blocks: &'a [Block], evictable: &'a HashSet<BlockId>) -> EvictionInfo<'a> {
314            EvictionInfo {
315                blocks,
316                evictable,
317                clean: blocks.len() - evictable.len(),
318            }
319        }
320
321        assert_eq!(picker.pick(info(&blocks, &evictable)), Some(9));
322
323        assert_eq!(picker.pick(info(&blocks, &evictable)), Some(9));
324        evictable.remove(&9);
325        assert_eq!(picker.pick(info(&blocks, &evictable)), Some(8));
326        evictable.remove(&8);
327        assert_eq!(picker.pick(info(&blocks, &evictable)), Some(7));
328        evictable.remove(&7);
329        assert_eq!(picker.pick(info(&blocks, &evictable)), Some(6));
330        evictable.remove(&6);
331        assert_eq!(picker.pick(info(&blocks, &evictable)), Some(5));
332        evictable.remove(&5);
333
334        assert_eq!(picker.pick(info(&blocks, &evictable)), None);
335        assert_eq!(picker.pick(info(&blocks, &evictable)), None);
336    }
337}
foyer_storage/engine/block/eviction.rs

foyer_storage/engine/block/
eviction.rs
