foyer_memory/
cache.rs

1// Copyright 2025 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::{any::Any, borrow::Cow, fmt::Debug, future::Future, hash::Hash, ops::Deref, sync::Arc};
16
17use equivalent::Equivalent;
18use foyer_common::{
19    code::{DefaultHasher, HashBuilder, Key, Value},
20    error::Result,
21    event::EventListener,
22    metrics::Metrics,
23    properties::{Age, Hint, Location, Properties, Source},
24    runtime::SingletonHandle,
25};
26use mixtrics::{metrics::BoxedRegistry, registry::noop::NoopMetricsRegistry};
27use pin_project::pin_project;
28use serde::{Deserialize, Serialize};
29
30use crate::{
31    eviction::{
32        fifo::{Fifo, FifoConfig},
33        lfu::{Lfu, LfuConfig},
34        lru::{Lru, LruConfig},
35        s3fifo::{S3Fifo, S3FifoConfig},
36        sieve::{Sieve, SieveConfig},
37    },
38    indexer::hash_table::HashTableIndexer,
39    inflight::{OptionalFetchBuilder, RequiredFetchBuilder},
40    raw::{Filter, RawCache, RawCacheConfig, RawCacheEntry, RawGetOrFetch, Weighter},
41    FetchTarget, Piece, Pipe,
42};
43
44/// Entry properties for in-memory only cache.
45#[derive(Debug, Clone, Default)]
46pub struct CacheProperties {
47    phantom: bool,
48    hint: Hint,
49}
50
51impl CacheProperties {
52    /// Set disposable.
53    fn with_phantom(mut self, phantom: bool) -> Self {
54        self.phantom = phantom;
55        self
56    }
57
58    fn phantom(&self) -> bool {
59        self.phantom
60    }
61
62    /// Set entry hint.
63    pub fn with_hint(mut self, hint: Hint) -> Self {
64        self.hint = hint;
65        self
66    }
67
68    /// Get entry hint.
69    pub fn hint(&self) -> Hint {
70        self.hint
71    }
72}
73
74impl Properties for CacheProperties {
75    fn with_phantom(self, phantom: bool) -> Self {
76        self.with_phantom(phantom)
77    }
78
79    fn phantom(&self) -> Option<bool> {
80        Some(self.phantom())
81    }
82
83    fn with_hint(self, hint: Hint) -> Self {
84        self.with_hint(hint)
85    }
86
87    fn hint(&self) -> Option<Hint> {
88        Some(self.hint())
89    }
90
91    fn with_location(self, _: Location) -> Self {
92        self
93    }
94
95    fn location(&self) -> Option<Location> {
96        None
97    }
98
99    fn with_age(self, _: Age) -> Self {
100        self
101    }
102
103    fn age(&self) -> Option<Age> {
104        None
105    }
106}
107
108macro_rules! define_cache {
109    ($algo:ident) => {
110        paste::paste! {
111            pub type [<$algo Cache>]<K, V, S = DefaultHasher, P = CacheProperties> =
112                RawCache<$algo<K, V, P>, S, HashTableIndexer<$algo<K, V, P>>>;
113            pub type [<$algo CacheEntry>]<K, V, S = DefaultHasher, P = CacheProperties> =
114                RawCacheEntry<$algo<K, V, P>, S, HashTableIndexer<$algo<K, V, P>>>;
115            pub type [<$algo GetOrFetch>]<K, V, S = DefaultHasher, P = CacheProperties> =
116                RawGetOrFetch<$algo<K, V, P>, S, HashTableIndexer<$algo<K, V, P>>>;
117        }
118    };
119}
120
121macro_rules! define_caches {
122    ($($algo:ident),*) => {
123        $(
124            define_cache! { $algo }
125        )*
126    };
127}
128
129// Define all supported cache types.
130//
131// NOTE: Please update the algo list when adding a new eviction algorithm.
132define_caches! { Fifo, S3Fifo, Lru, Lfu, Sieve }
133
134/// A cached entry holder of the in-memory cache.
135#[derive(Debug)]
136pub enum CacheEntry<K, V, S = DefaultHasher, P = CacheProperties>
137where
138    K: Key,
139    V: Value,
140    S: HashBuilder,
141    P: Properties,
142{
143    /// A cached entry holder of the in-memory FIFO cache.
144    Fifo(FifoCacheEntry<K, V, S, P>),
145    /// A cached entry holder of the in-memory S3FIFO cache.
146    S3Fifo(S3FifoCacheEntry<K, V, S, P>),
147    /// A cached entry holder of the in-memory LRU cache.
148    Lru(LruCacheEntry<K, V, S, P>),
149    /// A cached entry holder of the in-memory LFU cache.
150    Lfu(LfuCacheEntry<K, V, S, P>),
151    /// A cached entry holder of the in-memory Sieve cache.
152    Sieve(SieveCacheEntry<K, V, S, P>),
153}
154
155impl<K, V, S, P> Clone for CacheEntry<K, V, S, P>
156where
157    K: Key,
158    V: Value,
159    S: HashBuilder,
160    P: Properties,
161{
162    fn clone(&self) -> Self {
163        match self {
164            Self::Fifo(entry) => Self::Fifo(entry.clone()),
165            Self::Lru(entry) => Self::Lru(entry.clone()),
166            Self::Lfu(entry) => Self::Lfu(entry.clone()),
167            Self::S3Fifo(entry) => Self::S3Fifo(entry.clone()),
168            Self::Sieve(entry) => Self::Sieve(entry.clone()),
169        }
170    }
171}
172
173impl<K, V, S, P> Deref for CacheEntry<K, V, S, P>
174where
175    K: Key,
176    V: Value,
177    S: HashBuilder,
178    P: Properties,
179{
180    type Target = V;
181
182    fn deref(&self) -> &Self::Target {
183        match self {
184            CacheEntry::Fifo(entry) => entry.deref(),
185            CacheEntry::Lru(entry) => entry.deref(),
186            CacheEntry::Lfu(entry) => entry.deref(),
187            CacheEntry::S3Fifo(entry) => entry.deref(),
188            CacheEntry::Sieve(entry) => entry.deref(),
189        }
190    }
191}
192
193impl<K, V, S, P> From<FifoCacheEntry<K, V, S, P>> for CacheEntry<K, V, S, P>
194where
195    K: Key,
196    V: Value,
197    S: HashBuilder,
198    P: Properties,
199{
200    fn from(entry: FifoCacheEntry<K, V, S, P>) -> Self {
201        Self::Fifo(entry)
202    }
203}
204
205impl<K, V, S, P> From<LruCacheEntry<K, V, S, P>> for CacheEntry<K, V, S, P>
206where
207    K: Key,
208    V: Value,
209    S: HashBuilder,
210    P: Properties,
211{
212    fn from(entry: LruCacheEntry<K, V, S, P>) -> Self {
213        Self::Lru(entry)
214    }
215}
216
217impl<K, V, S, P> From<LfuCacheEntry<K, V, S, P>> for CacheEntry<K, V, S, P>
218where
219    K: Key,
220    V: Value,
221    S: HashBuilder,
222    P: Properties,
223{
224    fn from(entry: LfuCacheEntry<K, V, S, P>) -> Self {
225        Self::Lfu(entry)
226    }
227}
228
229impl<K, V, S, P> From<S3FifoCacheEntry<K, V, S, P>> for CacheEntry<K, V, S, P>
230where
231    K: Key,
232    V: Value,
233    S: HashBuilder,
234    P: Properties,
235{
236    fn from(entry: S3FifoCacheEntry<K, V, S, P>) -> Self {
237        Self::S3Fifo(entry)
238    }
239}
240
241impl<K, V, S, P> From<SieveCacheEntry<K, V, S, P>> for CacheEntry<K, V, S, P>
242where
243    K: Key,
244    V: Value,
245    S: HashBuilder,
246    P: Properties,
247{
248    fn from(entry: SieveCacheEntry<K, V, S, P>) -> Self {
249        Self::Sieve(entry)
250    }
251}
252
253impl<K, V, S, P> CacheEntry<K, V, S, P>
254where
255    K: Key,
256    V: Value,
257    S: HashBuilder,
258    P: Properties,
259{
260    /// Key hash of the cached entry.
261    pub fn hash(&self) -> u64 {
262        match self {
263            CacheEntry::Fifo(entry) => entry.hash(),
264            CacheEntry::Lru(entry) => entry.hash(),
265            CacheEntry::Lfu(entry) => entry.hash(),
266            CacheEntry::S3Fifo(entry) => entry.hash(),
267            CacheEntry::Sieve(entry) => entry.hash(),
268        }
269    }
270
271    /// Key of the cached entry.
272    pub fn key(&self) -> &K {
273        match self {
274            CacheEntry::Fifo(entry) => entry.key(),
275            CacheEntry::Lru(entry) => entry.key(),
276            CacheEntry::Lfu(entry) => entry.key(),
277            CacheEntry::S3Fifo(entry) => entry.key(),
278            CacheEntry::Sieve(entry) => entry.key(),
279        }
280    }
281
282    /// Value of the cached entry.
283    pub fn value(&self) -> &V {
284        match self {
285            CacheEntry::Fifo(entry) => entry.value(),
286            CacheEntry::Lru(entry) => entry.value(),
287            CacheEntry::Lfu(entry) => entry.value(),
288            CacheEntry::S3Fifo(entry) => entry.value(),
289            CacheEntry::Sieve(entry) => entry.value(),
290        }
291    }
292
293    /// Properties of the cached entry.
294    pub fn properties(&self) -> &P {
295        match self {
296            CacheEntry::Fifo(entry) => entry.properties(),
297            CacheEntry::Lru(entry) => entry.properties(),
298            CacheEntry::Lfu(entry) => entry.properties(),
299            CacheEntry::S3Fifo(entry) => entry.properties(),
300            CacheEntry::Sieve(entry) => entry.properties(),
301        }
302    }
303
304    /// Weight of the cached entry.
305    pub fn weight(&self) -> usize {
306        match self {
307            CacheEntry::Fifo(entry) => entry.weight(),
308            CacheEntry::Lru(entry) => entry.weight(),
309            CacheEntry::Lfu(entry) => entry.weight(),
310            CacheEntry::S3Fifo(entry) => entry.weight(),
311            CacheEntry::Sieve(entry) => entry.weight(),
312        }
313    }
314
315    /// External reference count of the cached entry.
316    pub fn refs(&self) -> usize {
317        match self {
318            CacheEntry::Fifo(entry) => entry.refs(),
319            CacheEntry::Lru(entry) => entry.refs(),
320            CacheEntry::Lfu(entry) => entry.refs(),
321            CacheEntry::S3Fifo(entry) => entry.refs(),
322            CacheEntry::Sieve(entry) => entry.refs(),
323        }
324    }
325
326    /// If the cached entry is updated and outdated.
327    pub fn is_outdated(&self) -> bool {
328        match self {
329            CacheEntry::Fifo(entry) => entry.is_outdated(),
330            CacheEntry::Lru(entry) => entry.is_outdated(),
331            CacheEntry::Lfu(entry) => entry.is_outdated(),
332            CacheEntry::S3Fifo(entry) => entry.is_outdated(),
333            CacheEntry::Sieve(entry) => entry.is_outdated(),
334        }
335    }
336
337    /// Get the piece of the entry record.
338    #[doc(hidden)]
339    pub fn piece(&self) -> Piece<K, V, P> {
340        match self {
341            CacheEntry::Fifo(entry) => entry.piece(),
342            CacheEntry::Lru(entry) => entry.piece(),
343            CacheEntry::Lfu(entry) => entry.piece(),
344            CacheEntry::S3Fifo(entry) => entry.piece(),
345            CacheEntry::Sieve(entry) => entry.piece(),
346        }
347    }
348
349    /// Get the source of the entry.
350    pub fn source(&self) -> Source {
351        match self {
352            CacheEntry::Fifo(entry) => entry.source(),
353            CacheEntry::Lru(entry) => entry.source(),
354            CacheEntry::Lfu(entry) => entry.source(),
355            CacheEntry::S3Fifo(entry) => entry.source(),
356            CacheEntry::Sieve(entry) => entry.source(),
357        }
358    }
359}
360
361/// Eviction algorithm config.
362#[derive(Debug, Clone, Serialize, Deserialize)]
363pub enum EvictionConfig {
364    /// FIFO eviction algorithm config.
365    Fifo(FifoConfig),
366    /// S3FIFO eviction algorithm config.
367    S3Fifo(S3FifoConfig),
368    /// LRU eviction algorithm config.
369    Lru(LruConfig),
370    /// LFU eviction algorithm config.
371    Lfu(LfuConfig),
372    /// Sieve eviction algorithm config.
373    Sieve(SieveConfig),
374}
375
376impl From<FifoConfig> for EvictionConfig {
377    fn from(value: FifoConfig) -> EvictionConfig {
378        EvictionConfig::Fifo(value)
379    }
380}
381
382impl From<S3FifoConfig> for EvictionConfig {
383    fn from(value: S3FifoConfig) -> EvictionConfig {
384        EvictionConfig::S3Fifo(value)
385    }
386}
387
388impl From<LruConfig> for EvictionConfig {
389    fn from(value: LruConfig) -> EvictionConfig {
390        EvictionConfig::Lru(value)
391    }
392}
393
394impl From<LfuConfig> for EvictionConfig {
395    fn from(value: LfuConfig) -> EvictionConfig {
396        EvictionConfig::Lfu(value)
397    }
398}
399
400impl From<SieveConfig> for EvictionConfig {
401    fn from(value: SieveConfig) -> EvictionConfig {
402        EvictionConfig::Sieve(value)
403    }
404}
405
406/// In-memory cache builder.
407pub struct CacheBuilder<K, V, S>
408where
409    K: Key,
410    V: Value,
411    S: HashBuilder,
412{
413    name: Cow<'static, str>,
414
415    capacity: usize,
416    shards: usize,
417    eviction_config: EvictionConfig,
418
419    hash_builder: S,
420    weighter: Arc<dyn Weighter<K, V>>,
421    filter: Arc<dyn Filter<K, V>>,
422
423    event_listener: Option<Arc<dyn EventListener<Key = K, Value = V>>>,
424
425    registry: BoxedRegistry,
426    metrics: Option<Arc<Metrics>>,
427}
428
429impl<K, V> CacheBuilder<K, V, DefaultHasher>
430where
431    K: Key,
432    V: Value,
433{
434    /// Create a new in-memory cache builder.
435    pub fn new(capacity: usize) -> Self {
436        Self {
437            name: "foyer".into(),
438
439            capacity,
440            shards: 8,
441            eviction_config: LruConfig::default().into(),
442
443            hash_builder: Default::default(),
444            weighter: Arc::new(|_, _| 1),
445            filter: Arc::new(|_, _| true),
446            event_listener: None,
447
448            registry: Box::new(NoopMetricsRegistry),
449            metrics: None,
450        }
451    }
452}
453
454impl<K, V, S> CacheBuilder<K, V, S>
455where
456    K: Key,
457    V: Value,
458    S: HashBuilder,
459{
460    /// Set the name of the foyer in-memory cache instance.
461    ///
462    /// foyer will use the name as the prefix of the metric names.
463    ///
464    /// Default: `foyer`.
465    pub fn with_name(mut self, name: impl Into<Cow<'static, str>>) -> Self {
466        self.name = name.into();
467        self
468    }
469
470    /// Set in-memory cache sharding count. Entries will be distributed to different shards based on their hash.
471    /// Operations on different shard can be parallelized.
472    pub fn with_shards(mut self, shards: usize) -> Self {
473        self.shards = shards;
474        self
475    }
476
477    /// Set in-memory cache eviction algorithm.
478    ///
479    /// The default value is a general-used w-TinyLFU algorithm.
480    pub fn with_eviction_config(mut self, eviction_config: impl Into<EvictionConfig>) -> Self {
481        self.eviction_config = eviction_config.into();
482        self
483    }
484
485    /// Set in-memory cache hash builder.
486    pub fn with_hash_builder<OS>(self, hash_builder: OS) -> CacheBuilder<K, V, OS>
487    where
488        OS: HashBuilder,
489    {
490        CacheBuilder {
491            name: self.name,
492            capacity: self.capacity,
493            shards: self.shards,
494            eviction_config: self.eviction_config,
495            hash_builder,
496            weighter: self.weighter,
497            filter: self.filter,
498            event_listener: self.event_listener,
499            registry: self.registry,
500            metrics: self.metrics,
501        }
502    }
503
504    /// Set in-memory cache weighter.
505    pub fn with_weighter(mut self, weighter: impl Weighter<K, V>) -> Self {
506        self.weighter = Arc::new(weighter);
507        self
508    }
509
510    /// Set the filter for the in-memory cache.
511    ///
512    /// The filter is used to decide whether to admit or reject an entry based on its key and value.
513    ///
514    /// If the filter returns true, the key value can be inserted into the in-memory cache;
515    /// otherwise, the key value cannot be inserted.
516    ///
517    /// To ensure API consistency, the in-memory cache will still return a cache entry,
518    /// but it will not count towards the in-memory cache usage,
519    /// and it will be immediately reclaimed when the cache entry is dropped.
520    pub fn with_filter(mut self, filter: impl Filter<K, V>) -> Self {
521        self.filter = Arc::new(filter);
522        self
523    }
524
525    /// Set event listener.
526    pub fn with_event_listener(mut self, event_listener: Arc<dyn EventListener<Key = K, Value = V>>) -> Self {
527        self.event_listener = Some(event_listener);
528        self
529    }
530
531    /// Set metrics registry.
532    ///
533    /// Default: [`NoopMetricsRegistry`].
534    pub fn with_metrics_registry(mut self, registry: BoxedRegistry) -> CacheBuilder<K, V, S> {
535        self.registry = registry;
536        self
537    }
538
539    /// Set metrics.
540    ///
541    /// Note: `with_metrics` is only supposed to be called by other foyer components.
542    #[doc(hidden)]
543    pub fn with_metrics(mut self, metrics: Arc<Metrics>) -> Self {
544        self.metrics = Some(metrics);
545        self
546    }
547
548    /// Build in-memory cache with the given configuration.
549    pub fn build<P>(self) -> Cache<K, V, S, P>
550    where
551        P: Properties,
552    {
553        if self.capacity < self.shards {
554            tracing::warn!(
555                "The in-memory cache capacity({}) < shards({}).",
556                self.capacity,
557                self.shards
558            );
559        }
560
561        let metrics = self
562            .metrics
563            .unwrap_or_else(|| Arc::new(Metrics::new(self.name, &self.registry)));
564
565        match self.eviction_config {
566            EvictionConfig::Fifo(eviction_config) => Cache::Fifo(Arc::new(RawCache::new(RawCacheConfig {
567                capacity: self.capacity,
568                shards: self.shards,
569                eviction_config,
570                hash_builder: self.hash_builder,
571                weighter: self.weighter,
572                filter: self.filter,
573                event_listener: self.event_listener,
574                metrics,
575            }))),
576            EvictionConfig::S3Fifo(eviction_config) => Cache::S3Fifo(Arc::new(RawCache::new(RawCacheConfig {
577                capacity: self.capacity,
578                shards: self.shards,
579                eviction_config,
580                hash_builder: self.hash_builder,
581                weighter: self.weighter,
582                filter: self.filter,
583                event_listener: self.event_listener,
584                metrics,
585            }))),
586            EvictionConfig::Lru(eviction_config) => Cache::Lru(Arc::new(RawCache::new(RawCacheConfig {
587                capacity: self.capacity,
588                shards: self.shards,
589                eviction_config,
590                hash_builder: self.hash_builder,
591                weighter: self.weighter,
592                filter: self.filter,
593                event_listener: self.event_listener,
594                metrics,
595            }))),
596            EvictionConfig::Lfu(eviction_config) => Cache::Lfu(Arc::new(RawCache::new(RawCacheConfig {
597                capacity: self.capacity,
598                shards: self.shards,
599                eviction_config,
600                hash_builder: self.hash_builder,
601                weighter: self.weighter,
602                filter: self.filter,
603                event_listener: self.event_listener,
604                metrics,
605            }))),
606            EvictionConfig::Sieve(eviction_config) => Cache::Sieve(Arc::new(RawCache::new(RawCacheConfig {
607                capacity: self.capacity,
608                shards: self.shards,
609                eviction_config,
610                hash_builder: self.hash_builder,
611                weighter: self.weighter,
612                filter: self.filter,
613                event_listener: self.event_listener,
614                metrics,
615            }))),
616        }
617    }
618}
619
620/// In-memory cache with plug-and-play algorithms.
621pub enum Cache<K, V, S = DefaultHasher, P = CacheProperties>
622where
623    K: Key,
624    V: Value,
625    S: HashBuilder,
626    P: Properties,
627{
628    /// In-memory FIFO cache.
629    Fifo(Arc<FifoCache<K, V, S, P>>),
630    /// In-memory LRU cache.
631    Lru(Arc<LruCache<K, V, S, P>>),
632    /// In-memory LFU cache.
633    Lfu(Arc<LfuCache<K, V, S, P>>),
634    /// In-memory S3FIFO cache.
635    S3Fifo(Arc<S3FifoCache<K, V, S, P>>),
636    /// In-memory Sieve cache.
637    Sieve(Arc<SieveCache<K, V, S, P>>),
638}
639
640impl<K, V, S, P> Debug for Cache<K, V, S, P>
641where
642    K: Key,
643    V: Value,
644    S: HashBuilder,
645    P: Properties,
646{
647    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
648        match self {
649            Self::Fifo(_) => f.debug_tuple("Cache::FifoCache").finish(),
650            Self::S3Fifo(_) => f.debug_tuple("Cache::S3FifoCache").finish(),
651            Self::Lru(_) => f.debug_tuple("Cache::LruCache").finish(),
652            Self::Lfu(_) => f.debug_tuple("Cache::LfuCache").finish(),
653            Self::Sieve(_) => f.debug_tuple("Cache::SieveCache").finish(),
654        }
655    }
656}
657
658impl<K, V, S, P> Clone for Cache<K, V, S, P>
659where
660    K: Key,
661    V: Value,
662    S: HashBuilder,
663    P: Properties,
664{
665    fn clone(&self) -> Self {
666        match self {
667            Self::Fifo(cache) => Self::Fifo(cache.clone()),
668            Self::S3Fifo(cache) => Self::S3Fifo(cache.clone()),
669            Self::Lru(cache) => Self::Lru(cache.clone()),
670            Self::Lfu(cache) => Self::Lfu(cache.clone()),
671            Self::Sieve(cache) => Self::Sieve(cache.clone()),
672        }
673    }
674}
675
676impl<K, V> Cache<K, V, DefaultHasher, CacheProperties>
677where
678    K: Key,
679    V: Value,
680{
681    /// Create a new in-memory cache builder with capacity.
682    pub fn builder(capacity: usize) -> CacheBuilder<K, V, DefaultHasher> {
683        CacheBuilder::new(capacity)
684    }
685}
686
687impl<K, V, S, P> Cache<K, V, S, P>
688where
689    K: Key,
690    V: Value,
691    S: HashBuilder,
692    P: Properties,
693{
694    /// Update capacity and evict overflowed entries.
695    #[cfg_attr(feature = "tracing", fastrace::trace(name = "foyer::memory::cache::resize"))]
696    pub fn resize(&self, capacity: usize) -> Result<()> {
697        match self {
698            Cache::Fifo(cache) => cache.resize(capacity),
699            Cache::S3Fifo(cache) => cache.resize(capacity),
700            Cache::Lru(cache) => cache.resize(capacity),
701            Cache::Lfu(cache) => cache.resize(capacity),
702            Cache::Sieve(cache) => cache.resize(capacity),
703        }
704    }
705
706    /// Insert cache entry to the in-memory cache.
707    #[cfg_attr(feature = "tracing", fastrace::trace(name = "foyer::memory::cache::insert"))]
708    pub fn insert(&self, key: K, value: V) -> CacheEntry<K, V, S, P> {
709        match self {
710            Cache::Fifo(cache) => cache.insert(key, value).into(),
711            Cache::S3Fifo(cache) => cache.insert(key, value).into(),
712            Cache::Lru(cache) => cache.insert(key, value).into(),
713            Cache::Lfu(cache) => cache.insert(key, value).into(),
714            Cache::Sieve(cache) => cache.insert(key, value).into(),
715        }
716    }
717
718    /// Insert cache entry to the in-memory cache with properties.
719    #[cfg_attr(
720        feature = "tracing",
721        fastrace::trace(name = "foyer::memory::cache::insert_with_properties")
722    )]
723    pub fn insert_with_properties(&self, key: K, value: V, properties: P) -> CacheEntry<K, V, S, P> {
724        match self {
725            Cache::Fifo(cache) => cache.insert_with_properties(key, value, properties).into(),
726            Cache::S3Fifo(cache) => cache.insert_with_properties(key, value, properties).into(),
727            Cache::Lru(cache) => cache.insert_with_properties(key, value, properties).into(),
728            Cache::Lfu(cache) => cache.insert_with_properties(key, value, properties).into(),
729            Cache::Sieve(cache) => cache.insert_with_properties(key, value, properties).into(),
730        }
731    }
732
733    #[doc(hidden)]
734    #[cfg_attr(feature = "tracing", fastrace::trace(name = "foyer::memory::cache::insert_inner"))]
735    pub fn insert_piece(&self, piece: Piece<K, V, P>) -> CacheEntry<K, V, S, P> {
736        match self {
737            Cache::Fifo(cache) => cache.insert_piece(piece).into(),
738            Cache::S3Fifo(cache) => cache.insert_piece(piece).into(),
739            Cache::Lru(cache) => cache.insert_piece(piece).into(),
740            Cache::Lfu(cache) => cache.insert_piece(piece).into(),
741            Cache::Sieve(cache) => cache.insert_piece(piece).into(),
742        }
743    }
744
745    /// Remove a cached entry with the given key from the in-memory cache.
746    #[cfg_attr(feature = "tracing", fastrace::trace(name = "foyer::memory::cache::remove"))]
747    pub fn remove<Q>(&self, key: &Q) -> Option<CacheEntry<K, V, S, P>>
748    where
749        Q: Hash + Equivalent<K> + ?Sized,
750    {
751        match self {
752            Cache::Fifo(cache) => cache.remove(key).map(CacheEntry::from),
753            Cache::S3Fifo(cache) => cache.remove(key).map(CacheEntry::from),
754            Cache::Lru(cache) => cache.remove(key).map(CacheEntry::from),
755            Cache::Lfu(cache) => cache.remove(key).map(CacheEntry::from),
756            Cache::Sieve(cache) => cache.remove(key).map(CacheEntry::from),
757        }
758    }
759
760    /// Get cached entry with the given key from the in-memory cache.
761    #[cfg_attr(feature = "tracing", fastrace::trace(name = "foyer::memory::cache::get"))]
762    pub fn get<Q>(&self, key: &Q) -> Option<CacheEntry<K, V, S, P>>
763    where
764        Q: Hash + Equivalent<K> + ?Sized,
765    {
766        match self {
767            Cache::Fifo(cache) => cache.get(key).map(CacheEntry::from),
768            Cache::S3Fifo(cache) => cache.get(key).map(CacheEntry::from),
769            Cache::Lru(cache) => cache.get(key).map(CacheEntry::from),
770            Cache::Lfu(cache) => cache.get(key).map(CacheEntry::from),
771            Cache::Sieve(cache) => cache.get(key).map(CacheEntry::from),
772        }
773    }
774
775    /// Check if the in-memory cache contains a cached entry with the given key.
776    #[cfg_attr(feature = "tracing", fastrace::trace(name = "foyer::memory::cache::contains"))]
777    pub fn contains<Q>(&self, key: &Q) -> bool
778    where
779        Q: Hash + Equivalent<K> + ?Sized,
780    {
781        match self {
782            Cache::Fifo(cache) => cache.contains(key),
783            Cache::S3Fifo(cache) => cache.contains(key),
784            Cache::Lru(cache) => cache.contains(key),
785            Cache::Lfu(cache) => cache.contains(key),
786            Cache::Sieve(cache) => cache.contains(key),
787        }
788    }
789
790    /// Access the cached entry with the given key but don't return.
791    ///
792    /// Note: This method can be used to update the cache eviction information and order based on the algorithm.
793    #[cfg_attr(feature = "tracing", fastrace::trace(name = "foyer::memory::cache::touch"))]
794    pub fn touch<Q>(&self, key: &Q) -> bool
795    where
796        Q: Hash + Equivalent<K> + ?Sized,
797    {
798        match self {
799            Cache::Fifo(cache) => cache.touch(key),
800            Cache::S3Fifo(cache) => cache.touch(key),
801            Cache::Lru(cache) => cache.touch(key),
802            Cache::Lfu(cache) => cache.touch(key),
803            Cache::Sieve(cache) => cache.touch(key),
804        }
805    }
806
807    /// Clear the in-memory cache.
808    #[cfg_attr(feature = "tracing", fastrace::trace(name = "foyer::memory::cache::clear"))]
809    pub fn clear(&self) {
810        match self {
811            Cache::Fifo(cache) => cache.clear(),
812            Cache::S3Fifo(cache) => cache.clear(),
813            Cache::Lru(cache) => cache.clear(),
814            Cache::Lfu(cache) => cache.clear(),
815            Cache::Sieve(cache) => cache.clear(),
816        }
817    }
818
819    /// Get the capacity of the in-memory cache.
820    pub fn capacity(&self) -> usize {
821        match self {
822            Cache::Fifo(cache) => cache.capacity(),
823            Cache::S3Fifo(cache) => cache.capacity(),
824            Cache::Lru(cache) => cache.capacity(),
825            Cache::Lfu(cache) => cache.capacity(),
826            Cache::Sieve(cache) => cache.capacity(),
827        }
828    }
829
830    /// Get the usage of the in-memory cache.
831    pub fn usage(&self) -> usize {
832        match self {
833            Cache::Fifo(cache) => cache.usage(),
834            Cache::S3Fifo(cache) => cache.usage(),
835            Cache::Lru(cache) => cache.usage(),
836            Cache::Lfu(cache) => cache.usage(),
837            Cache::Sieve(cache) => cache.usage(),
838        }
839    }
840
841    /// Hash the given key with the hash builder of the cache.
842    pub fn hash<Q>(&self, key: &Q) -> u64
843    where
844        Q: Hash + ?Sized,
845    {
846        self.hash_builder().hash_one(key)
847    }
848
849    /// Get the hash builder of the in-memory cache.
850    pub fn hash_builder(&self) -> &Arc<S> {
851        match self {
852            Cache::Fifo(cache) => cache.hash_builder(),
853            Cache::S3Fifo(cache) => cache.hash_builder(),
854            Cache::Lru(cache) => cache.hash_builder(),
855            Cache::Lfu(cache) => cache.hash_builder(),
856            Cache::Sieve(cache) => cache.hash_builder(),
857        }
858    }
859
860    /// Get the shards of the in-memory cache.
861    pub fn shards(&self) -> usize {
862        match self {
863            Cache::Fifo(cache) => cache.shards(),
864            Cache::S3Fifo(cache) => cache.shards(),
865            Cache::Lru(cache) => cache.shards(),
866            Cache::Lfu(cache) => cache.shards(),
867            Cache::Sieve(cache) => cache.shards(),
868        }
869    }
870
871    /// Set the pipe for the hybrid cache.
872    #[doc(hidden)]
873    pub fn set_pipe(&self, pipe: Box<dyn Pipe<Key = K, Value = V, Properties = P>>) {
874        match self {
875            Cache::Fifo(cache) => cache.set_pipe(pipe),
876            Cache::S3Fifo(cache) => cache.set_pipe(pipe),
877            Cache::Lru(cache) => cache.set_pipe(pipe),
878            Cache::Lfu(cache) => cache.set_pipe(pipe),
879            Cache::Sieve(cache) => cache.set_pipe(pipe),
880        }
881    }
882
883    /// Evict all entries from the in-memory cache.
884    ///
885    /// Instead of [`Cache::clear`], [`Cache::evict_all`] will send the evicted pipe to the pipe.
886    /// It is useful when the cache is used as a hybrid cache.
887    pub fn evict_all(&self) {
888        match self {
889            Cache::Fifo(cache) => cache.evict_all(),
890            Cache::S3Fifo(cache) => cache.evict_all(),
891            Cache::Lru(cache) => cache.evict_all(),
892            Cache::Lfu(cache) => cache.evict_all(),
893            Cache::Sieve(cache) => cache.evict_all(),
894        }
895    }
896
897    /// Evict all entries in the cache and offload them into the disk cache via the pipe if needed.
898    ///
899    /// This function obeys the io throttler of the disk cache and make sure all entries will be offloaded.
900    /// Therefore, this function is asynchronous.
901    #[cfg_attr(feature = "tracing", fastrace::trace(name = "foyer::memory::raw::offload"))]
902    pub async fn flush(&self) {
903        match self {
904            Cache::Fifo(cache) => cache.flush().await,
905            Cache::S3Fifo(cache) => cache.flush().await,
906            Cache::Lru(cache) => cache.flush().await,
907            Cache::Lfu(cache) => cache.flush().await,
908            Cache::Sieve(cache) => cache.flush().await,
909        }
910    }
911}
912
913/// A future that is used to get entry value from the remote storage for the in-memory cache.
914#[must_use]
915#[pin_project(project = GetOrFetchProj)]
916pub enum GetOrFetch<K, V, S = DefaultHasher, P = CacheProperties>
917where
918    K: Key,
919    V: Value,
920    S: HashBuilder,
921    P: Properties,
922{
923    /// A future that is used to get entry value from the remote storage for the in-memory FIFO cache.
924    Fifo(#[pin] FifoGetOrFetch<K, V, S, P>),
925    /// A future that is used to get entry value from the remote storage for the in-memory S3FIFO cache.
926    S3Fifo(#[pin] S3FifoGetOrFetch<K, V, S, P>),
927    /// A future that is used to get entry value from the remote storage for the in-memory LRU cache.
928    Lru(#[pin] LruGetOrFetch<K, V, S, P>),
929    /// A future that is used to get entry value from the remote storage for the in-memory LFU cache.
930    Lfu(#[pin] LfuGetOrFetch<K, V, S, P>),
931    /// A future that is used to get entry value from the remote storage for the in-memory sieve cache.
932    Sieve(#[pin] SieveGetOrFetch<K, V, S, P>),
933}
934
935impl<K, V, S, P> Debug for GetOrFetch<K, V, S, P>
936where
937    K: Key,
938    V: Value,
939    S: HashBuilder,
940    P: Properties,
941{
942    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
943        match self {
944            Self::Fifo(raw) => f.debug_tuple("Fifo").field(raw).finish(),
945            Self::S3Fifo(raw) => f.debug_tuple("S3Fifo").field(raw).finish(),
946            Self::Lru(raw) => f.debug_tuple("Lru").field(raw).finish(),
947            Self::Lfu(raw) => f.debug_tuple("Lfu").field(raw).finish(),
948            Self::Sieve(raw) => f.debug_tuple("Sieve").field(raw).finish(),
949        }
950    }
951}
952
953impl<K, V, S, P> From<FifoGetOrFetch<K, V, S, P>> for GetOrFetch<K, V, S, P>
954where
955    K: Key,
956    V: Value,
957    S: HashBuilder,
958    P: Properties,
959{
960    fn from(entry: FifoGetOrFetch<K, V, S, P>) -> Self {
961        Self::Fifo(entry)
962    }
963}
964
965impl<K, V, S, P> From<S3FifoGetOrFetch<K, V, S, P>> for GetOrFetch<K, V, S, P>
966where
967    K: Key,
968    V: Value,
969    S: HashBuilder,
970    P: Properties,
971{
972    fn from(entry: S3FifoGetOrFetch<K, V, S, P>) -> Self {
973        Self::S3Fifo(entry)
974    }
975}
976
977impl<K, V, S, P> From<LruGetOrFetch<K, V, S, P>> for GetOrFetch<K, V, S, P>
978where
979    K: Key,
980    V: Value,
981    S: HashBuilder,
982    P: Properties,
983{
984    fn from(entry: LruGetOrFetch<K, V, S, P>) -> Self {
985        Self::Lru(entry)
986    }
987}
988
989impl<K, V, S, P> From<LfuGetOrFetch<K, V, S, P>> for GetOrFetch<K, V, S, P>
990where
991    K: Key,
992    V: Value,
993    S: HashBuilder,
994    P: Properties,
995{
996    fn from(entry: LfuGetOrFetch<K, V, S, P>) -> Self {
997        Self::Lfu(entry)
998    }
999}
1000
1001impl<K, V, S, P> From<SieveGetOrFetch<K, V, S, P>> for GetOrFetch<K, V, S, P>
1002where
1003    K: Key,
1004    V: Value,
1005    S: HashBuilder,
1006    P: Properties,
1007{
1008    fn from(entry: SieveGetOrFetch<K, V, S, P>) -> Self {
1009        Self::Sieve(entry)
1010    }
1011}
1012
1013impl<K, V, S, P> Future for GetOrFetch<K, V, S, P>
1014where
1015    K: Key + Clone,
1016    V: Value,
1017    S: HashBuilder,
1018    P: Properties,
1019{
1020    type Output = Result<CacheEntry<K, V, S, P>>;
1021
1022    fn poll(self: std::pin::Pin<&mut Self>, cx: &mut std::task::Context<'_>) -> std::task::Poll<Self::Output> {
1023        self.poll_inner(cx)
1024            .map(|res| res.map(|opt| opt.expect("GetOrFetch future resolved to None")))
1025    }
1026}
1027
1028impl<K, V, S, P> GetOrFetch<K, V, S, P>
1029where
1030    K: Key + Clone,
1031    V: Value,
1032    S: HashBuilder,
1033    P: Properties,
1034{
1035    #[doc(hidden)]
1036    #[expect(clippy::type_complexity)]
1037    pub fn poll_inner(
1038        self: std::pin::Pin<&mut Self>,
1039        cx: &mut std::task::Context<'_>,
1040    ) -> std::task::Poll<Result<Option<CacheEntry<K, V, S, P>>>> {
1041        match self.project() {
1042            GetOrFetchProj::Fifo(fut) => fut.poll(cx).map(|res| res.map(|opt| opt.map(CacheEntry::from))),
1043            GetOrFetchProj::S3Fifo(fut) => fut.poll(cx).map(|res| res.map(|opt| opt.map(CacheEntry::from))),
1044            GetOrFetchProj::Lru(fut) => fut.poll(cx).map(|res| res.map(|opt| opt.map(CacheEntry::from))),
1045            GetOrFetchProj::Lfu(fut) => fut.poll(cx).map(|res| res.map(|opt| opt.map(CacheEntry::from))),
1046            GetOrFetchProj::Sieve(fut) => fut.poll(cx).map(|res| res.map(|opt| opt.map(CacheEntry::from))),
1047        }
1048    }
1049
1050    /// Check if the future need to be awaited or can be unwrap at once.
1051    pub fn need_await(&self) -> bool {
1052        match self {
1053            GetOrFetch::Fifo(fut) => fut.need_await(),
1054            GetOrFetch::S3Fifo(fut) => fut.need_await(),
1055            GetOrFetch::Lru(fut) => fut.need_await(),
1056            GetOrFetch::Lfu(fut) => fut.need_await(),
1057            GetOrFetch::Sieve(fut) => fut.need_await(),
1058        }
1059    }
1060
1061    /// Try to unwrap the future if it is already ready.
1062    /// Otherwise, return the original future.
1063    #[expect(clippy::allow_attributes)]
1064    #[allow(clippy::result_large_err)]
1065    pub fn try_unwrap(self) -> std::result::Result<CacheEntry<K, V, S, P>, Self> {
1066        match self {
1067            GetOrFetch::Fifo(fut) => fut.try_unwrap().map(|opt| opt.unwrap().into()).map_err(Self::from),
1068            GetOrFetch::S3Fifo(fut) => fut.try_unwrap().map(|opt| opt.unwrap().into()).map_err(Self::from),
1069            GetOrFetch::Lru(fut) => fut.try_unwrap().map(|opt| opt.unwrap().into()).map_err(Self::from),
1070            GetOrFetch::Lfu(fut) => fut.try_unwrap().map(|opt| opt.unwrap().into()).map_err(Self::from),
1071            GetOrFetch::Sieve(fut) => fut.try_unwrap().map(|opt| opt.unwrap().into()).map_err(Self::from),
1072        }
1073    }
1074}
1075
1076impl<K, V, S, P> Cache<K, V, S, P>
1077where
1078    K: Key,
1079    V: Value,
1080    S: HashBuilder,
1081    P: Properties,
1082{
1083    /// Get the cached entry with the given key from the in-memory cache.
1084    ///
1085    /// Use `fetch` to fetch the cache value from the remote storage on cache miss.
1086    ///
1087    /// The concurrent fetch requests will be deduplicated.
1088    #[cfg_attr(feature = "tracing", fastrace::trace(name = "foyer::memory::cache::get_or_fetch"))]
1089    pub fn get_or_fetch<Q, F, FU, IT, ER>(&self, key: &Q, fetch: F) -> GetOrFetch<K, V, S, P>
1090    where
1091        Q: Hash + Equivalent<K> + ?Sized + ToOwned<Owned = K>,
1092        F: FnOnce() -> FU,
1093        FU: Future<Output = std::result::Result<IT, ER>> + Send + 'static,
1094        IT: Into<FetchTarget<K, V, P>>,
1095        ER: Into<anyhow::Error>,
1096    {
1097        match self {
1098            Cache::Fifo(cache) => GetOrFetch::from(cache.get_or_fetch(key, fetch)),
1099            Cache::Lru(cache) => GetOrFetch::from(cache.get_or_fetch(key, fetch)),
1100            Cache::Lfu(cache) => GetOrFetch::from(cache.get_or_fetch(key, fetch)),
1101            Cache::S3Fifo(cache) => GetOrFetch::from(cache.get_or_fetch(key, fetch)),
1102            Cache::Sieve(cache) => GetOrFetch::from(cache.get_or_fetch(key, fetch)),
1103        }
1104    }
1105
1106    #[doc(hidden)]
1107    #[cfg_attr(
1108        feature = "tracing",
1109        fastrace::trace(name = "foyer::memory::cache::get_or_fetch_inner")
1110    )]
1111    pub fn get_or_fetch_inner<Q, C, FO, FR>(
1112        &self,
1113        key: &Q,
1114        fo: FO,
1115        fr: FR,
1116        ctx: C,
1117        runtime: &SingletonHandle,
1118    ) -> GetOrFetch<K, V, S, P>
1119    where
1120        Q: Hash + Equivalent<K> + ?Sized + ToOwned<Owned = K>,
1121        C: Any + Send + Sync + 'static,
1122        FO: FnOnce() -> Option<OptionalFetchBuilder<K, V, P, C>>,
1123        FR: FnOnce() -> Option<RequiredFetchBuilder<K, V, P, C>>,
1124    {
1125        match self {
1126            Cache::Fifo(cache) => cache.get_or_fetch_inner(key, fo, fr, ctx, runtime).into(),
1127            Cache::Lru(cache) => cache.get_or_fetch_inner(key, fo, fr, ctx, runtime).into(),
1128            Cache::Lfu(cache) => cache.get_or_fetch_inner(key, fo, fr, ctx, runtime).into(),
1129            Cache::S3Fifo(cache) => cache.get_or_fetch_inner(key, fo, fr, ctx, runtime).into(),
1130            Cache::Sieve(cache) => cache.get_or_fetch_inner(key, fo, fr, ctx, runtime).into(),
1131        }
1132    }
1133}
1134
1135#[cfg(test)]
1136mod tests {
1137    use std::{ops::Range, time::Duration};
1138
1139    use foyer_common::error::Error;
1140    use futures_util::future::join_all;
1141    use itertools::Itertools;
1142    use rand::{rngs::StdRng, seq::SliceRandom, Rng, SeedableRng};
1143
1144    use super::*;
1145    use crate::eviction::{fifo::FifoConfig, lfu::LfuConfig, lru::LruConfig, s3fifo::S3FifoConfig};
1146
1147    const CAPACITY: usize = 100;
1148    const SHARDS: usize = 4;
1149    const RANGE: Range<u64> = 0..1000;
1150    const OPS: usize = 10000;
1151    const CONCURRENCY: usize = 8;
1152
1153    fn fifo() -> Cache<u64, u64> {
1154        CacheBuilder::new(CAPACITY)
1155            .with_shards(SHARDS)
1156            .with_eviction_config(FifoConfig {})
1157            .build()
1158    }
1159
1160    fn lru() -> Cache<u64, u64> {
1161        CacheBuilder::new(CAPACITY)
1162            .with_shards(SHARDS)
1163            .with_eviction_config(LruConfig {
1164                high_priority_pool_ratio: 0.1,
1165            })
1166            .build()
1167    }
1168
1169    fn lfu() -> Cache<u64, u64> {
1170        CacheBuilder::new(CAPACITY)
1171            .with_shards(SHARDS)
1172            .with_eviction_config(LfuConfig {
1173                window_capacity_ratio: 0.1,
1174                protected_capacity_ratio: 0.8,
1175                cmsketch_eps: 0.001,
1176                cmsketch_confidence: 0.9,
1177            })
1178            .build()
1179    }
1180
1181    fn s3fifo() -> Cache<u64, u64> {
1182        CacheBuilder::new(CAPACITY)
1183            .with_shards(SHARDS)
1184            .with_eviction_config(S3FifoConfig {
1185                small_queue_capacity_ratio: 0.1,
1186                ghost_queue_capacity_ratio: 10.0,
1187                small_to_main_freq_threshold: 2,
1188            })
1189            .build()
1190    }
1191
1192    fn sieve() -> Cache<u64, u64> {
1193        CacheBuilder::new(CAPACITY)
1194            .with_shards(SHARDS)
1195            .with_eviction_config(SieveConfig {})
1196            .build()
1197    }
1198
1199    fn init_cache(cache: &Cache<u64, u64>, rng: &mut StdRng) {
1200        let mut v = RANGE.collect_vec();
1201        v.shuffle(rng);
1202        for i in v {
1203            cache.insert(i, i);
1204        }
1205    }
1206
1207    async fn operate(cache: &Cache<u64, u64>, rng: &mut StdRng) {
1208        let i = rng.random_range(RANGE);
1209        match rng.random_range(0..=3) {
1210            0 => {
1211                let entry = cache.insert(i, i);
1212                assert_eq!(*entry.key(), i);
1213                assert_eq!(entry.key(), entry.value());
1214            }
1215            1 => {
1216                if let Some(entry) = cache.get(&i) {
1217                    assert_eq!(*entry.key(), i);
1218                    assert_eq!(entry.key(), entry.value());
1219                }
1220            }
1221            2 => {
1222                cache.remove(&i);
1223            }
1224            3 => {
1225                let entry = cache
1226                    .get_or_fetch(&i, || async move {
1227                        tokio::time::sleep(Duration::from_micros(10)).await;
1228                        Ok::<_, Error>(i)
1229                    })
1230                    .await
1231                    .unwrap();
1232                assert_eq!(*entry.key(), i);
1233                assert_eq!(entry.key(), entry.value());
1234            }
1235            _ => unreachable!(),
1236        }
1237    }
1238
1239    async fn case(cache: Cache<u64, u64>) {
1240        let mut rng = StdRng::seed_from_u64(42);
1241
1242        init_cache(&cache, &mut rng);
1243
1244        let handles = (0..CONCURRENCY)
1245            .map(|_| {
1246                let cache = cache.clone();
1247                let mut rng = rng.clone();
1248                tokio::spawn(async move {
1249                    for _ in 0..OPS {
1250                        operate(&cache, &mut rng).await;
1251                    }
1252                })
1253            })
1254            .collect_vec();
1255
1256        join_all(handles).await;
1257    }
1258
1259    #[tokio::test]
1260    async fn test_fifo_cache() {
1261        case(fifo()).await
1262    }
1263
1264    #[tokio::test]
1265    async fn test_lru_cache() {
1266        case(lru()).await
1267    }
1268
1269    #[tokio::test]
1270    async fn test_lfu_cache() {
1271        case(lfu()).await
1272    }
1273
1274    #[tokio::test]
1275    async fn test_s3fifo_cache() {
1276        case(s3fifo()).await
1277    }
1278
1279    #[tokio::test]
1280    async fn test_sieve_cache() {
1281        case(sieve()).await
1282    }
1283}
foyer_memory/cache.rs

foyer_memory/
cache.rs
