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

foyer_memory/
cache.rs
