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

foyer_memory/
cache.rs
