diff --git a/foyer-common/src/code.rs b/foyer-common/src/code.rs index 0b222964..6d725c08 100644 --- a/foyer-common/src/code.rs +++ b/foyer-common/src/code.rs @@ -22,6 +22,10 @@ pub trait Value: Send + Sync + 'static {} impl Key for T {} impl Value for T {} +/// Context trait for the in-memory cache. +pub trait Context: Send + Sync + 'static {} +impl Context for T {} + /// Hash builder trait. pub trait HashBuilder: BuildHasher + Send + Sync + 'static {} impl HashBuilder for T where T: BuildHasher + Send + Sync + 'static {} diff --git a/foyer-memory/src/eviction/fifo.rs b/foyer-memory/src/eviction/fifo.rs index 2d2ede1b..99b7989a 100644 --- a/foyer-memory/src/eviction/fifo.rs +++ b/foyer-memory/src/eviction/fifo.rs @@ -14,7 +14,7 @@ use std::{mem::offset_of, sync::Arc}; -use foyer_common::code::{Key, Value}; +use foyer_common::code::{Context, Key, Value}; use intrusive_collections::{intrusive_adapter, LinkedList, LinkedListAtomicLink}; use serde::{Deserialize, Serialize}; @@ -50,24 +50,27 @@ pub struct FifoState { link: LinkedListAtomicLink, } -intrusive_adapter! { Adapter = Arc>>: Record> { ?offset = Record::>::STATE_OFFSET + offset_of!(FifoState, link) => LinkedListAtomicLink } where K: Key, V: Value } +intrusive_adapter! { Adapter = Arc>>: Record> { ?offset = Record::>::STATE_OFFSET + offset_of!(FifoState, link) => LinkedListAtomicLink } where K: Key, V: Value, C: Context } -pub struct Fifo +pub struct Fifo where K: Key, V: Value, + C: Context, { - queue: LinkedList>, + queue: LinkedList>, } -impl Eviction for Fifo +impl Eviction for Fifo where K: Key, V: Value, + C: Context, { type Config = FifoConfig; type Key = K; type Value = V; + type Context = C; type Hint = FifoHint; type State = FifoState; @@ -118,7 +121,7 @@ pub mod tests { record::Data, }; - impl Dump for Fifo + impl Dump for Fifo where K: Key + Clone, V: Value + Clone, @@ -138,7 +141,7 @@ pub mod tests { } } - type TestFifo = Fifo; + type TestFifo = Fifo; #[test] fn test_fifo() { diff --git a/foyer-memory/src/eviction/lfu.rs b/foyer-memory/src/eviction/lfu.rs index dd72d879..7efcebe7 100644 --- a/foyer-memory/src/eviction/lfu.rs +++ b/foyer-memory/src/eviction/lfu.rs @@ -16,7 +16,7 @@ use std::{mem::offset_of, sync::Arc}; use cmsketch::CMSketchU16; use foyer_common::{ - code::{Key, Value}, + code::{Context, Key, Value}, strict_assert, strict_assert_eq, strict_assert_ne, }; use intrusive_collections::{intrusive_adapter, LinkedList, LinkedListAtomicLink}; @@ -103,7 +103,7 @@ pub struct LfuState { queue: Queue, } -intrusive_adapter! { Adapter = Arc>>: Record> { ?offset = Record::>::STATE_OFFSET + offset_of!(LfuState, link) => LinkedListAtomicLink } where K: Key, V: Value } +intrusive_adapter! { Adapter = Arc>>: Record> { ?offset = Record::>::STATE_OFFSET + offset_of!(LfuState, link) => LinkedListAtomicLink } where K: Key, V: Value, C: Context } /// This implementation is inspired by [Caffeine](https://github.com/ben-manes/caffeine) under Apache License 2.0 /// @@ -117,14 +117,15 @@ intrusive_adapter! { Adapter = Arc>>: Record> { /// /// When evicting, the entry with a lower frequency from `window` or `probation` will be evicted first, then from /// `protected`. -pub struct Lfu +pub struct Lfu where K: Key, V: Value, + C: Context, { - window: LinkedList>, - probation: LinkedList>, - protected: LinkedList>, + window: LinkedList>, + probation: LinkedList>, + protected: LinkedList>, window_weight: usize, probation_weight: usize, @@ -142,10 +143,11 @@ where config: LfuConfig, } -impl Lfu +impl Lfu where K: Key, V: Value, + C: Context, { fn increase_queue_weight(&mut self, queue: Queue, weight: usize) { match queue { @@ -175,14 +177,16 @@ where } } -impl Eviction for Lfu +impl Eviction for Lfu where K: Key, V: Value, + C: Context, { type Config = LfuConfig; type Key = K; type Value = V; + type Context = C; type Hint = LfuHint; type State = LfuState; @@ -428,7 +432,7 @@ mod tests { record::Data, }; - impl Dump for Lfu + impl Dump for Lfu where K: Key + Clone, V: Value + Clone, @@ -470,7 +474,7 @@ mod tests { } } - type TestLfu = Lfu; + type TestLfu = Lfu; #[test] fn test_lfu() { diff --git a/foyer-memory/src/eviction/lru.rs b/foyer-memory/src/eviction/lru.rs index 17496e3b..7934c79e 100644 --- a/foyer-memory/src/eviction/lru.rs +++ b/foyer-memory/src/eviction/lru.rs @@ -15,7 +15,7 @@ use std::{mem::offset_of, sync::Arc}; use foyer_common::{ - code::{Key, Value}, + code::{Context, Key, Value}, strict_assert, }; use intrusive_collections::{intrusive_adapter, LinkedList, LinkedListAtomicLink}; @@ -88,16 +88,17 @@ pub struct LruState { is_pinned: bool, } -intrusive_adapter! { Adapter = Arc>>: Record> { ?offset = Record::>::STATE_OFFSET + offset_of!(LruState, link) => LinkedListAtomicLink } where K: Key, V: Value } +intrusive_adapter! { Adapter = Arc>>: Record> { ?offset = Record::>::STATE_OFFSET + offset_of!(LruState, link) => LinkedListAtomicLink } where K: Key, V: Value, C: Context } -pub struct Lru +pub struct Lru where K: Key, V: Value, + C: Context, { - high_priority_list: LinkedList>, - list: LinkedList>, - pin_list: LinkedList>, + high_priority_list: LinkedList>, + list: LinkedList>, + pin_list: LinkedList>, high_priority_weight: usize, high_priority_weight_capacity: usize, @@ -105,10 +106,11 @@ where config: LruConfig, } -impl Lru +impl Lru where K: Key, V: Value, + C: Context, { fn may_overflow_high_priority_pool(&mut self) { while self.high_priority_weight > self.high_priority_weight_capacity { @@ -125,14 +127,16 @@ where } } -impl Eviction for Lru +impl Eviction for Lru where K: Key, V: Value, + C: Context, { type Config = LruConfig; type Key = K; type Value = V; + type Context = C; type Hint = LruHint; type State = LruState; @@ -333,7 +337,7 @@ pub mod tests { record::Data, }; - impl Dump for Lru + impl Dump for Lru where K: Key + Clone, V: Value + Clone, @@ -375,7 +379,7 @@ pub mod tests { } } - type TestLru = Lru; + type TestLru = Lru; #[test] fn test_lru() { diff --git a/foyer-memory/src/eviction/mod.rs b/foyer-memory/src/eviction/mod.rs index 4f351de4..c9868330 100644 --- a/foyer-memory/src/eviction/mod.rs +++ b/foyer-memory/src/eviction/mod.rs @@ -14,7 +14,7 @@ use std::sync::Arc; -use foyer_common::code::{Key, Value}; +use foyer_common::code::{Context, Key, Value}; use serde::{de::DeserializeOwned, Serialize}; use crate::{ @@ -92,6 +92,8 @@ pub trait Eviction: Send + Sync + 'static + Sized { type Key: Key; /// Cache value. Generally, it is supposed to be a generic type of the implementation. type Value: Value; + /// Cache context. Generally, it is supposed to be a generic type of the implementation. + type Context: Context; /// Hint for a cache entry. Can be used to support priority at the entry granularity. type Hint: Hint; /// State for a cache entry. Mutable state for maintaining the cache eviction algorithm implementation. diff --git a/foyer-memory/src/eviction/s3fifo.rs b/foyer-memory/src/eviction/s3fifo.rs index 566265ae..33c99de0 100644 --- a/foyer-memory/src/eviction/s3fifo.rs +++ b/foyer-memory/src/eviction/s3fifo.rs @@ -22,7 +22,7 @@ use std::{ }; use foyer_common::{ - code::{Key, Value}, + code::{Context, Key, Value}, strict_assert, strict_assert_eq, }; use intrusive_collections::{intrusive_adapter, LinkedList, LinkedListAtomicLink}; @@ -118,16 +118,17 @@ impl S3FifoState { } } -intrusive_adapter! { Adapter = Arc>>: Record> { ?offset = Record::>::STATE_OFFSET + offset_of!(S3FifoState, link) => LinkedListAtomicLink } where K: Key, V: Value } +intrusive_adapter! { Adapter = Arc>>: Record> { ?offset = Record::>::STATE_OFFSET + offset_of!(S3FifoState, link) => LinkedListAtomicLink } where K: Key, V: Value, C: Context } -pub struct S3Fifo +pub struct S3Fifo where K: Key, V: Value, + C: Context, { ghost_queue: GhostQueue, - small_queue: LinkedList>, - main_queue: LinkedList>, + small_queue: LinkedList>, + main_queue: LinkedList>, small_weight_capacity: usize, @@ -139,12 +140,13 @@ where config: S3FifoConfig, } -impl S3Fifo +impl S3Fifo where K: Key, V: Value, + C: Context, { - fn evict(&mut self) -> Option>>> { + fn evict(&mut self) -> Option>>> { // TODO(MrCroxx): Use `let_chains` here after it is stable. if self.small_weight > self.small_weight_capacity { if let Some(record) = self.evict_small() { @@ -158,7 +160,7 @@ where } #[expect(clippy::never_loop)] - fn evict_small_force(&mut self) -> Option>>> { + fn evict_small_force(&mut self) -> Option>>> { while let Some(record) = self.small_queue.pop_front() { let state = unsafe { &mut *record.state().get() }; state.queue = Queue::None; @@ -169,7 +171,7 @@ where None } - fn evict_small(&mut self) -> Option>>> { + fn evict_small(&mut self) -> Option>>> { while let Some(record) = self.small_queue.pop_front() { let state = unsafe { &mut *record.state().get() }; if state.frequency() >= self.small_to_main_freq_threshold { @@ -190,7 +192,7 @@ where None } - fn evict_main(&mut self) -> Option>>> { + fn evict_main(&mut self) -> Option>>> { while let Some(record) = self.main_queue.pop_front() { let state = unsafe { &mut *record.state().get() }; if state.dec_frequency() > 0 { @@ -205,14 +207,16 @@ where } } -impl Eviction for S3Fifo +impl Eviction for S3Fifo where K: Key, V: Value, + C: Context, { type Config = S3FifoConfig; type Key = K; type Value = V; + type Context = C; type Hint = S3FifoHint; type State = S3FifoState; @@ -396,7 +400,7 @@ mod tests { record::Data, }; - impl Dump for S3Fifo + impl Dump for S3Fifo where K: Key + Clone, V: Value + Clone, @@ -429,7 +433,7 @@ mod tests { } } - type TestS3Fifo = S3Fifo; + type TestS3Fifo = S3Fifo; fn assert_frequencies(rs: &[Arc>], range: Range, count: u8) { rs[range] diff --git a/foyer-memory/src/record.rs b/foyer-memory/src/record.rs index 64caefd0..f367281a 100644 --- a/foyer-memory/src/record.rs +++ b/foyer-memory/src/record.rs @@ -62,6 +62,7 @@ where pub hash: u64, pub weight: usize, pub location: CacheLocation, + pub context: E::Context, } /// [`Record`] holds the information of the cached entry.