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

foyer_memory/
cache.rs
