Coverage Report

Created: 2025-10-29 07:05

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/rust/registry/src/index.crates.io-1949cf8c6b5b557f/moka-0.12.10/src/policy.rs
Line
Count
Source
1
use std::{
2
    fmt,
3
    sync::Arc,
4
    time::{Duration, Instant},
5
};
6
7
#[derive(Clone, Debug)]
8
/// The policy of a cache.
9
pub struct Policy {
10
    max_capacity: Option<u64>,
11
    num_segments: usize,
12
    time_to_live: Option<Duration>,
13
    time_to_idle: Option<Duration>,
14
}
15
16
impl Policy {
17
0
    pub(crate) fn new(
18
0
        max_capacity: Option<u64>,
19
0
        num_segments: usize,
20
0
        time_to_live: Option<Duration>,
21
0
        time_to_idle: Option<Duration>,
22
0
    ) -> Self {
23
0
        Self {
24
0
            max_capacity,
25
0
            num_segments,
26
0
            time_to_live,
27
0
            time_to_idle,
28
0
        }
29
0
    }
30
31
    /// Returns the `max_capacity` of the cache.
32
0
    pub fn max_capacity(&self) -> Option<u64> {
33
0
        self.max_capacity
34
0
    }
35
36
    #[cfg(feature = "sync")]
37
0
    pub(crate) fn set_max_capacity(&mut self, capacity: Option<u64>) {
38
0
        self.max_capacity = capacity;
39
0
    }
40
41
    /// Returns the number of internal segments of the cache.
42
0
    pub fn num_segments(&self) -> usize {
43
0
        self.num_segments
44
0
    }
45
46
    #[cfg(feature = "sync")]
47
0
    pub(crate) fn set_num_segments(&mut self, num: usize) {
48
0
        self.num_segments = num;
49
0
    }
50
51
    /// Returns the `time_to_live` of the cache.
52
0
    pub fn time_to_live(&self) -> Option<Duration> {
53
0
        self.time_to_live
54
0
    }
55
56
    /// Returns the `time_to_idle` of the cache.
57
0
    pub fn time_to_idle(&self) -> Option<Duration> {
58
0
        self.time_to_idle
59
0
    }
60
}
61
62
/// The eviction (and admission) policy of a cache.
63
///
64
/// When the cache is full, the eviction/admission policy is used to determine which
65
/// items should be admitted to the cache and which cached items should be evicted.
66
/// The choice of a policy will directly affect the performance (hit rate) of the
67
/// cache.
68
///
69
/// The following policies are available:
70
///
71
/// - **TinyLFU** (default):
72
///   - Suitable for most workloads.
73
///   - TinyLFU combines the LRU eviction policy and an admission policy based on the
74
///     historical popularity of keys.
75
///   - Note that it tracks not only the keys currently in the cache, but all hit and
76
///     missed keys. The data structure used to _estimate_ the popularity of keys is
77
///     a modified Count-Min Sketch, which has a very low memory footprint (thus the
78
///     name "tiny").
79
/// - **LRU**:
80
///   - Suitable for some workloads with strong recency bias, such as streaming data
81
///     processing.
82
///
83
/// LFU stands for Least Frequently Used. LRU stands for Least Recently Used.
84
///
85
/// Use associate function [`EvictionPolicy::tiny_lfu`](#method.tiny_lfu) or
86
/// [`EvictionPolicy::lru`](#method.lru) to obtain an instance of `EvictionPolicy`.
87
#[derive(Clone, Default)]
88
pub struct EvictionPolicy {
89
    pub(crate) config: EvictionPolicyConfig,
90
}
91
92
impl EvictionPolicy {
93
    /// Returns the TinyLFU policy, which is suitable for most workloads.
94
    ///
95
    /// TinyLFU is a combination of the LRU eviction policy and the admission policy
96
    /// based on the historical popularity of keys.
97
    ///
98
    /// Note that it tracks not only the keys currently in the cache, but all hit and
99
    /// missed keys. The data structure used to _estimate_ the popularity of keys is
100
    /// a modified Count-Min Sketch, which has a very low memory footprint (thus the
101
    /// name "tiny").
102
0
    pub fn tiny_lfu() -> Self {
103
0
        Self {
104
0
            config: EvictionPolicyConfig::TinyLfu,
105
0
        }
106
0
    }
107
108
    /// Returns the LRU policy.
109
    ///
110
    /// Suitable for some workloads with strong recency bias, such as streaming data
111
    /// processing.
112
0
    pub fn lru() -> Self {
113
0
        Self {
114
0
            config: EvictionPolicyConfig::Lru,
115
0
        }
116
0
    }
117
}
118
119
impl fmt::Debug for EvictionPolicy {
120
0
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
121
0
        match self.config {
122
0
            EvictionPolicyConfig::TinyLfu => write!(f, "EvictionPolicy::TinyLfu"),
123
0
            EvictionPolicyConfig::Lru => write!(f, "EvictionPolicy::Lru"),
124
        }
125
0
    }
126
}
127
128
#[derive(Clone, Debug, PartialEq, Eq)]
129
pub(crate) enum EvictionPolicyConfig {
130
    TinyLfu,
131
    Lru,
132
}
133
134
impl Default for EvictionPolicyConfig {
135
0
    fn default() -> Self {
136
0
        Self::TinyLfu
137
0
    }
138
}
139
140
/// Calculates when cache entries expire. A single expiration time is retained on
141
/// each entry so that the lifetime of an entry may be extended or reduced by
142
/// subsequent evaluations.
143
///
144
/// `Expiry` trait provides three methods. They specify the expiration time of an
145
/// entry by returning a `Some(duration)` until the entry expires:
146
///
147
/// - [`expire_after_create`](#method.expire_after_create) &mdash; Returns the
148
///   duration (or none) after the entry's creation.
149
/// - [`expire_after_read`](#method.expire_after_read) &mdash; Returns the duration
150
///   (or none)  after its last read.
151
/// - [`expire_after_update`](#method.expire_after_update) &mdash; Returns the
152
///   duration (or none)  after its last update.
153
///
154
/// The default implementations are provided that return `None` (no expiration) or
155
/// `current_duration: Option<Instant>` (not modify the current expiration time).
156
/// Override some of them as you need.
157
///
158
pub trait Expiry<K, V> {
159
    /// Specifies that the entry should be automatically removed from the cache once
160
    /// the duration has elapsed after the entry's creation. This method is called
161
    /// for cache write methods such as `insert` and `get_with` but only when the key
162
    /// was not present in the cache.
163
    ///
164
    /// # Parameters
165
    ///
166
    /// - `key` &mdash; A reference to the key of the entry.
167
    /// - `value` &mdash; A reference to the value of the entry.
168
    /// - `created_at` &mdash; The time when this entry was inserted.
169
    ///
170
    /// # Return value
171
    ///
172
    /// The returned `Option<Duration>` is used to set the expiration time of the
173
    /// entry.
174
    ///
175
    /// - Returning `Some(duration)` &mdash; The expiration time is set to
176
    ///   `created_at + duration`.
177
    /// - Returning `None` &mdash; The expiration time is cleared (no expiration).
178
    ///   - This is the value that the default implementation returns.
179
    ///
180
    /// # Notes on `time_to_live` and `time_to_idle` policies
181
    ///
182
    /// When the cache is configured with `time_to_live` and/or `time_to_idle`
183
    /// policies, the entry will be evicted after the earliest of the expiration time
184
    /// returned by this expiry, the `time_to_live` and `time_to_idle` policies.
185
    #[allow(unused_variables)]
186
0
    fn expire_after_create(&self, key: &K, value: &V, created_at: Instant) -> Option<Duration> {
187
0
        None
188
0
    }
189
190
    /// Specifies that the entry should be automatically removed from the cache once
191
    /// the duration has elapsed after its last read. This method is called for cache
192
    /// read methods such as `get` and `get_with` but only when the key is present in
193
    /// the cache.
194
    ///
195
    /// # Parameters
196
    ///
197
    /// - `key` &mdash; A reference to the key of the entry.
198
    /// - `value` &mdash; A reference to the value of the entry.
199
    /// - `read_at` &mdash; The time when this entry was read.
200
    /// - `duration_until_expiry` &mdash; The remaining duration until the entry
201
    ///   expires. (Calculated by `expiration_time - read_at`)
202
    /// - `last_modified_at` &mdash; The time when this entry was created or updated.
203
    ///
204
    /// # Return value
205
    ///
206
    /// The returned `Option<Duration>` is used to set the expiration time of the
207
    /// entry.
208
    ///
209
    /// - Returning `Some(duration)` &mdash; The expiration time is set to
210
    ///   `read_at + duration`.
211
    /// - Returning `None` &mdash; The expiration time is cleared (no expiration).
212
    /// - Returning `duration_until_expiry` will not modify the expiration time.
213
    ///   - This is the value that the default implementation returns.
214
    ///
215
    /// # Notes on `time_to_live` and `time_to_idle` policies
216
    ///
217
    /// When the cache is configured with `time_to_live` and/or `time_to_idle`
218
    /// policies, then:
219
    ///
220
    /// - The entry will be evicted after the earliest of the expiration time
221
    ///   returned by this expiry, the `time_to_live` and `time_to_idle` policies.
222
    /// - The `duration_until_expiry` takes in account the `time_to_live` and
223
    ///   `time_to_idle` policies.
224
    #[allow(unused_variables)]
225
0
    fn expire_after_read(
226
0
        &self,
227
0
        key: &K,
228
0
        value: &V,
229
0
        read_at: Instant,
230
0
        duration_until_expiry: Option<Duration>,
231
0
        last_modified_at: Instant,
232
0
    ) -> Option<Duration> {
233
0
        duration_until_expiry
234
0
    }
Unexecuted instantiation: <hickory_resolver::dns_lru::LruValueExpiry as moka::policy::Expiry<hickory_proto::op::query::Query, hickory_resolver::dns_lru::LruValue>>::expire_after_read
Unexecuted instantiation: <_ as moka::policy::Expiry<_, _>>::expire_after_read
235
236
    /// Specifies that the entry should be automatically removed from the cache once
237
    /// the duration has elapsed after the replacement of its value. This method is
238
    /// called for cache write methods such as `insert` but only when the key is
239
    /// already present in the cache.
240
    ///
241
    /// # Parameters
242
    ///
243
    /// - `key` &mdash; A reference to the key of the entry.
244
    /// - `value` &mdash; A reference to the value of the entry.
245
    /// - `updated_at` &mdash; The time when this entry was updated.
246
    /// - `duration_until_expiry` &mdash; The remaining duration until the entry
247
    ///   expires. (Calculated by `expiration_time - updated_at`)
248
    ///
249
    /// # Return value
250
    ///
251
    /// The returned `Option<Duration>` is used to set the expiration time of the
252
    /// entry.
253
    ///
254
    /// - Returning `Some(duration)` &mdash; The expiration time is set to
255
    ///   `updated_at + duration`.
256
    /// - Returning `None` &mdash; The expiration time is cleared (no expiration).
257
    /// - Returning `duration_until_expiry` will not modify the expiration time.
258
    ///   - This is the value that the default implementation returns.
259
    ///
260
    /// # Notes on `time_to_live` and `time_to_idle` policies
261
    ///
262
    /// When the cache is configured with `time_to_live` and/or `time_to_idle`
263
    /// policies, then:
264
    ///
265
    /// - The entry will be evicted after the earliest of the expiration time
266
    ///   returned by this expiry, the `time_to_live` and `time_to_idle` policies.
267
    /// - The `duration_until_expiry` takes in account the `time_to_live` and
268
    ///   `time_to_idle` policies.
269
    #[allow(unused_variables)]
270
0
    fn expire_after_update(
271
0
        &self,
272
0
        key: &K,
273
0
        value: &V,
274
0
        updated_at: Instant,
275
0
        duration_until_expiry: Option<Duration>,
276
0
    ) -> Option<Duration> {
277
0
        duration_until_expiry
278
0
    }
279
}
280
281
pub(crate) struct ExpirationPolicy<K, V> {
282
    time_to_live: Option<Duration>,
283
    time_to_idle: Option<Duration>,
284
    expiry: Option<Arc<dyn Expiry<K, V> + Send + Sync + 'static>>,
285
}
286
287
impl<K, V> Default for ExpirationPolicy<K, V> {
288
0
    fn default() -> Self {
289
0
        Self {
290
0
            time_to_live: None,
291
0
            time_to_idle: None,
292
0
            expiry: None,
293
0
        }
294
0
    }
Unexecuted instantiation: <moka::policy::ExpirationPolicy<hickory_proto::op::query::Query, hickory_resolver::dns_lru::LruValue> as core::default::Default>::default
Unexecuted instantiation: <moka::policy::ExpirationPolicy<_, _> as core::default::Default>::default
295
}
296
297
impl<K, V> Clone for ExpirationPolicy<K, V> {
298
0
    fn clone(&self) -> Self {
299
0
        Self {
300
0
            time_to_live: self.time_to_live,
301
0
            time_to_idle: self.time_to_idle,
302
0
            expiry: self.expiry.clone(),
303
0
        }
304
0
    }
305
}
306
307
impl<K, V> ExpirationPolicy<K, V> {
308
    #[cfg(test)]
309
    pub(crate) fn new(
310
        time_to_live: Option<Duration>,
311
        time_to_idle: Option<Duration>,
312
        expiry: Option<Arc<dyn Expiry<K, V> + Send + Sync + 'static>>,
313
    ) -> Self {
314
        Self {
315
            time_to_live,
316
            time_to_idle,
317
            expiry,
318
        }
319
    }
320
321
    /// Returns the `time_to_live` of the cache.
322
0
    pub(crate) fn time_to_live(&self) -> Option<Duration> {
323
0
        self.time_to_live
324
0
    }
Unexecuted instantiation: <moka::policy::ExpirationPolicy<hickory_proto::op::query::Query, hickory_resolver::dns_lru::LruValue>>::time_to_live
Unexecuted instantiation: <moka::policy::ExpirationPolicy<_, _>>::time_to_live
325
326
0
    pub(crate) fn set_time_to_live(&mut self, duration: Duration) {
327
0
        self.time_to_live = Some(duration);
328
0
    }
329
330
    /// Returns the `time_to_idle` of the cache.
331
0
    pub(crate) fn time_to_idle(&self) -> Option<Duration> {
332
0
        self.time_to_idle
333
0
    }
Unexecuted instantiation: <moka::policy::ExpirationPolicy<hickory_proto::op::query::Query, hickory_resolver::dns_lru::LruValue>>::time_to_idle
Unexecuted instantiation: <moka::policy::ExpirationPolicy<_, _>>::time_to_idle
334
335
0
    pub(crate) fn set_time_to_idle(&mut self, duration: Duration) {
336
0
        self.time_to_idle = Some(duration);
337
0
    }
338
339
0
    pub(crate) fn expiry(&self) -> Option<Arc<dyn Expiry<K, V> + Send + Sync + 'static>> {
340
0
        self.expiry.clone()
341
0
    }
Unexecuted instantiation: <moka::policy::ExpirationPolicy<hickory_proto::op::query::Query, hickory_resolver::dns_lru::LruValue>>::expiry
Unexecuted instantiation: <moka::policy::ExpirationPolicy<_, _>>::expiry
342
343
0
    pub(crate) fn set_expiry(&mut self, expiry: Arc<dyn Expiry<K, V> + Send + Sync + 'static>) {
344
0
        self.expiry = Some(expiry);
345
0
    }
Unexecuted instantiation: <moka::policy::ExpirationPolicy<hickory_proto::op::query::Query, hickory_resolver::dns_lru::LruValue>>::set_expiry
Unexecuted instantiation: <moka::policy::ExpirationPolicy<_, _>>::set_expiry
346
}
347
348
#[cfg(test)]
349
pub(crate) mod test_utils {
350
    use std::sync::atomic::{AtomicU8, Ordering};
351
352
    #[derive(Default)]
353
    pub(crate) struct ExpiryCallCounters {
354
        expected_creations: AtomicU8,
355
        expected_reads: AtomicU8,
356
        expected_updates: AtomicU8,
357
        actual_creations: AtomicU8,
358
        actual_reads: AtomicU8,
359
        actual_updates: AtomicU8,
360
    }
361
362
    impl ExpiryCallCounters {
363
        pub(crate) fn incl_expected_creations(&self) {
364
            self.expected_creations.fetch_add(1, Ordering::Relaxed);
365
        }
366
367
        pub(crate) fn incl_expected_reads(&self) {
368
            self.expected_reads.fetch_add(1, Ordering::Relaxed);
369
        }
370
371
        pub(crate) fn incl_expected_updates(&self) {
372
            self.expected_updates.fetch_add(1, Ordering::Relaxed);
373
        }
374
375
        pub(crate) fn incl_actual_creations(&self) {
376
            self.actual_creations.fetch_add(1, Ordering::Relaxed);
377
        }
378
379
        pub(crate) fn incl_actual_reads(&self) {
380
            self.actual_reads.fetch_add(1, Ordering::Relaxed);
381
        }
382
383
        pub(crate) fn incl_actual_updates(&self) {
384
            self.actual_updates.fetch_add(1, Ordering::Relaxed);
385
        }
386
387
        pub(crate) fn verify(&self) {
388
            assert_eq!(
389
                self.expected_creations.load(Ordering::Relaxed),
390
                self.actual_creations.load(Ordering::Relaxed),
391
                "expected_creations != actual_creations"
392
            );
393
            assert_eq!(
394
                self.expected_reads.load(Ordering::Relaxed),
395
                self.actual_reads.load(Ordering::Relaxed),
396
                "expected_reads != actual_reads"
397
            );
398
            assert_eq!(
399
                self.expected_updates.load(Ordering::Relaxed),
400
                self.actual_updates.load(Ordering::Relaxed),
401
                "expected_updates != actual_updates"
402
            );
403
        }
404
    }
405
}