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

foyer_memory/
cache.rs
