cachelito_core/async_global_cache.rs
1#[cfg(feature = "stats")]
2use crate::CacheStats;
3use crate::EvictionPolicy;
4use dashmap::DashMap;
5use parking_lot::lock_api::MutexGuard;
6use parking_lot::{Mutex, RawMutex};
7use std::collections::VecDeque;
8
9/// A thread-safe async global cache with configurable eviction policies and TTL support.
10///
11/// This cache is designed specifically for async/await contexts and uses lock-free
12/// concurrent data structures (DashMap) for optimal performance under high concurrency.
13///
14/// # Type Parameters
15///
16/// * `R` - The type of values stored in the cache. Must implement `Clone`.
17///
18/// # Features
19///
20/// - **Lock-free reads/writes**: Uses DashMap for concurrent access without blocking
21/// - **Eviction policies**: FIFO, LRU (default), LFU, ARC, Random, and TLRU
22/// - **FIFO**: First In, First Out - simple and predictable
23/// - **LRU**: Least Recently Used - evicts least recently accessed entries
24/// - **LFU**: Least Frequently Used - evicts least frequently accessed entries
25/// - **ARC**: Adaptive Replacement Cache - hybrid policy combining recency and frequency
26/// - **Random**: Random replacement - O(1) eviction with minimal overhead
27/// - **TLRU**: Time-aware LRU - combines recency, frequency, and age factors
28/// - Customizable with `frequency_weight` parameter
29/// - Formula: `score = frequency^weight × position × age_factor`
30/// - `frequency_weight < 1.0`: Emphasize recency (time-sensitive data)
31/// - `frequency_weight > 1.0`: Emphasize frequency (popular content)
32/// - **Cache limits**: Entry count limits (`limit`) and memory-based limits (`max_memory`)
33/// - **TTL support**: Automatic expiration of entries based on age
34/// - **Statistics**: Optional cache hit/miss tracking (with `stats` feature)
35/// - **Frequency tracking**: For LFU, ARC, and TLRU policies
36/// - **Memory estimation**: Support for memory-based eviction (requires `MemoryEstimator`)
37///
38/// # Cache Entry Structure
39///
40/// Each cache entry is stored as a tuple: `(value, timestamp, frequency)`
41/// - `value`: The cached value of type R
42/// - `timestamp`: Unix timestamp when the entry was created (for TTL and TLRU age factor)
43/// - `frequency`: Access counter for LFU, ARC, and TLRU policies
44///
45/// # Eviction Behavior
46///
47/// When the cache reaches its limit (entry count or memory), entries are evicted according
48/// to the configured policy:
49///
50/// - **FIFO**: Oldest entry (first in order queue) is evicted
51/// - **LRU**: Least recently accessed entry (first in order queue) is evicted
52/// - **LFU**: Entry with lowest frequency counter is evicted
53/// - **ARC**: Entry with lowest score (frequency × position_weight) is evicted
54/// - **Random**: Randomly selected entry is evicted
55/// - **TLRU**: Entry with lowest score (frequency^weight × position × age_factor) is evicted
56///
57/// # Performance Characteristics
58///
59/// - **Get**: O(1) for cache lookup, O(n) for LRU/ARC/TLRU reordering
60/// - **Insert**: O(1) for FIFO/Random, O(n) for LRU/LFU/ARC/TLRU eviction
61/// - **Memory**: O(n) where n is the number of cached entries
62///
63/// # Thread Safety
64///
65/// This structure is fully thread-safe and can be shared across multiple async tasks.
66/// The underlying DashMap provides lock-free concurrent access, while the order queue
67/// uses a Mutex for coordination.
68///
69/// # Examples
70///
71/// ## Basic Usage
72///
73/// ```ignore
74/// use cachelito_core::{AsyncGlobalCache, EvictionPolicy};
75/// use dashmap::DashMap;
76/// use parking_lot::Mutex;
77/// use std::collections::VecDeque;
78///
79/// let cache = DashMap::new();
80/// let order = Mutex::new(VecDeque::new());
81/// let async_cache = AsyncGlobalCache::new(
82/// &cache,
83/// &order,
84/// Some(100), // Max 100 entries
85/// None, // No memory limit
86/// EvictionPolicy::LRU,
87/// Some(60), // 60 second TTL
88/// None, // Default frequency_weight for TLRU
89/// );
90///
91/// // In async context:
92/// if let Some(value) = async_cache.get("key") {
93/// println!("Cache hit: {}", value);
94/// }
95/// ```
96///
97/// ## TLRU with Custom Frequency Weight
98///
99/// ```ignore
100/// use cachelito_core::{AsyncGlobalCache, EvictionPolicy};
101///
102/// // Emphasize frequency over recency (good for popular content)
103/// let async_cache = AsyncGlobalCache::new(
104/// &cache,
105/// &order,
106/// Some(100),
107/// None,
108/// EvictionPolicy::TLRU,
109/// Some(300),
110/// Some(1.5), // frequency_weight > 1.0
111/// );
112///
113/// // Emphasize recency over frequency (good for time-sensitive data)
114/// let async_cache = AsyncGlobalCache::new(
115/// &cache,
116/// &order,
117/// Some(100),
118/// None,
119/// EvictionPolicy::TLRU,
120/// Some(300),
121/// Some(0.3), // frequency_weight < 1.0
122/// );
123/// ```
124///
125/// ## With Memory Limits
126///
127/// ```ignore
128/// use cachelito_core::{AsyncGlobalCache, EvictionPolicy, MemoryEstimator};
129///
130/// let async_cache = AsyncGlobalCache::new(
131/// &cache,
132/// &order,
133/// Some(1000),
134/// Some(100 * 1024 * 1024), // 100MB max
135/// EvictionPolicy::LRU,
136/// Some(300),
137/// None,
138/// );
139///
140/// // Insert with memory tracking (requires MemoryEstimator implementation)
141/// async_cache.insert_with_memory("key", value);
142/// ```
143pub struct AsyncGlobalCache<'a, R: Clone> {
144 /// The underlying DashMap storing cache entries
145 /// Structure: key -> (value, timestamp, frequency)
146 cache: &'a DashMap<String, (R, u64, u64)>,
147
148 /// Order queue for FIFO/LRU eviction tracking
149 order: &'a Mutex<VecDeque<String>>,
150
151 /// Maximum number of entries (None = unlimited)
152 limit: Option<usize>,
153
154 /// Maximum memory size in bytes (None = unlimited)
155 max_memory: Option<usize>,
156
157 /// Eviction policy to use
158 policy: EvictionPolicy,
159
160 /// Time-to-live in seconds (None = no expiration)
161 ttl: Option<u64>,
162
163 /// Frequency weight for TLRU policy (>= 0.0)
164 frequency_weight: Option<f64>,
165
166 /// Window ratio for W-TinyLFU policy (0.01 to 0.99)
167 window_ratio: Option<f64>,
168
169 /// Cache statistics (when stats feature is enabled)
170 #[cfg(feature = "stats")]
171 stats: &'a CacheStats,
172}
173
174impl<'a, R: Clone> AsyncGlobalCache<'a, R> {
175 /// Creates a new `AsyncGlobalCache`.
176 ///
177 /// # Arguments
178 ///
179 /// * `cache` - Reference to the DashMap storing cache entries
180 /// * `order` - Reference to the Mutex-protected eviction order queue
181 /// * `limit` - Optional maximum number of entries (None = unlimited)
182 /// * `max_memory` - Optional maximum memory size in bytes (None = unlimited)
183 /// * `policy` - Eviction policy (FIFO, LRU, LFU, ARC, Random, or TLRU)
184 /// * `ttl` - Optional time-to-live in seconds (None = no expiration)
185 /// * `frequency_weight` - Optional weight factor for frequency in TLRU policy
186 /// - Values < 1.0: Emphasize recency and age
187 /// - Values > 1.0: Emphasize frequency
188 /// - None or 1.0: Balanced approach (default)
189 /// - Only used when policy is TLRU, ignored otherwise
190 ///
191 /// # Examples
192 ///
193 /// ## Basic LRU cache with TTL
194 ///
195 /// ```ignore
196 /// let cache = DashMap::new();
197 /// let order = Mutex::new(VecDeque::new());
198 /// let async_cache = AsyncGlobalCache::new(
199 /// &cache,
200 /// &order,
201 /// Some(1000), // Max 1000 entries
202 /// None, // No memory limit
203 /// EvictionPolicy::LRU, // LRU eviction
204 /// Some(300), // 5 minute TTL
205 /// None, // No frequency_weight (not needed for LRU)
206 /// );
207 /// ```
208 ///
209 /// ## TLRU with memory limit and custom frequency weight
210 ///
211 /// ```ignore
212 /// let async_cache = AsyncGlobalCache::new(
213 /// &cache,
214 /// &order,
215 /// Some(1000),
216 /// Some(100 * 1024 * 1024), // 100MB max
217 /// EvictionPolicy::TLRU, // TLRU eviction
218 /// Some(300), // 5 minute TTL
219 /// Some(1.5), // Emphasize frequency (popular content)
220 /// );
221 /// ```
222 #[cfg(not(feature = "stats"))]
223 pub fn new(
224 cache: &'a DashMap<String, (R, u64, u64)>,
225 order: &'a Mutex<VecDeque<String>>,
226 limit: Option<usize>,
227 max_memory: Option<usize>,
228 policy: EvictionPolicy,
229 ttl: Option<u64>,
230 frequency_weight: Option<f64>,
231 window_ratio: Option<f64>,
232 ) -> Self {
233 Self {
234 cache,
235 order,
236 limit,
237 max_memory,
238 policy,
239 ttl,
240 frequency_weight,
241 window_ratio,
242 }
243 }
244
245 /// Creates a new `AsyncGlobalCache` with statistics support.
246 ///
247 /// This version is available when the `stats` feature is enabled.
248 #[cfg(feature = "stats")]
249 pub fn new(
250 cache: &'a DashMap<String, (R, u64, u64)>,
251 order: &'a Mutex<VecDeque<String>>,
252 limit: Option<usize>,
253 max_memory: Option<usize>,
254 policy: EvictionPolicy,
255 ttl: Option<u64>,
256 frequency_weight: Option<f64>,
257 window_ratio: Option<f64>,
258 stats: &'a CacheStats,
259 ) -> Self {
260 Self {
261 cache,
262 order,
263 limit,
264 max_memory,
265 policy,
266 ttl,
267 frequency_weight,
268 window_ratio,
269 stats,
270 }
271 }
272
273 /// Attempts to retrieve a value from the cache.
274 ///
275 /// This method checks if the key exists, validates TTL expiration,
276 /// updates access patterns based on the eviction policy, and records statistics.
277 ///
278 /// # Arguments
279 ///
280 /// * `key` - The cache key to look up
281 ///
282 /// # Returns
283 ///
284 /// * `Some(R)` - The cached value if found and not expired
285 /// * `None` - If the key doesn't exist or has expired
286 ///
287 /// # Behavior by Policy
288 ///
289 /// - **FIFO**: No updates on cache hit (order remains unchanged)
290 /// - **LRU**: Moves the key to the end of the order queue (most recently used)
291 /// - **LFU**: Increments the frequency counter for the entry
292 /// - **ARC**: Increments frequency counter and updates position in order queue
293 /// - **Random**: No updates on cache hit
294 /// - **TLRU**: Increments frequency counter and updates position in order queue
295 ///
296 /// # TTL Expiration
297 ///
298 /// If a TTL is configured and the entry has expired:
299 /// - The entry is removed from both the cache and order queue
300 /// - A cache miss is recorded (if stats feature is enabled)
301 /// - `None` is returned
302 ///
303 /// # Statistics
304 ///
305 /// When the `stats` feature is enabled:
306 /// - Cache hits are recorded when a valid entry is found
307 /// - Cache misses are recorded when the key doesn't exist or has expired
308 ///
309 /// # Examples
310 ///
311 /// ```ignore
312 /// // Check for cached user
313 /// if let Some(user) = async_cache.get("user:123") {
314 /// println!("Found user: {:?}", user);
315 /// } else {
316 /// println!("Cache miss - need to fetch from database");
317 /// }
318 /// ```
319 ///
320 /// # Performance
321 ///
322 /// - **FIFO, Random**: O(1) - no reordering needed
323 /// - **LRU, ARC, TLRU**: O(n) - requires finding and moving key in order queue
324 /// - **LFU**: O(1) - only increments counter
325 pub fn get(&self, key: &str) -> Option<R> {
326 // Check cache first
327 if let Some(mut entry_ref) = self.cache.get_mut(key) {
328 let now = std::time::SystemTime::now()
329 .duration_since(std::time::UNIX_EPOCH)
330 .unwrap()
331 .as_secs();
332
333 // Check if expired
334 // Use saturating_sub to avoid underflow when system clock moves backwards
335 // Align comparison with sync variant: expire when age >= ttl
336 let is_expired = if let Some(ttl) = self.ttl {
337 let age = now.saturating_sub(entry_ref.1);
338 age >= ttl
339 } else {
340 false
341 };
342
343 if !is_expired {
344 let cached_value = entry_ref.0.clone();
345
346 // Update access patterns based on policy
347 match self.policy {
348 EvictionPolicy::LFU => {
349 // Increment frequency counter
350 entry_ref.2 = entry_ref.2.saturating_add(1);
351 }
352 EvictionPolicy::ARC => {
353 // Increment frequency counter for ARC
354 entry_ref.2 = entry_ref.2.saturating_add(1);
355 // LRU update happens after releasing the entry lock
356 }
357 EvictionPolicy::TLRU => {
358 // Increment frequency counter for TLRU
359 entry_ref.2 = entry_ref.2.saturating_add(1);
360 // LRU update happens after releasing the entry lock
361 }
362 EvictionPolicy::WTinyLFU => {
363 // Simplified W-TinyLFU: Behaves like a hybrid of LRU and LFU
364 // Increment frequency counter
365 entry_ref.2 = entry_ref.2.saturating_add(1);
366 // LRU update happens after releasing the entry lock
367 }
368 EvictionPolicy::LRU => {
369 // LRU update happens after releasing the entry lock
370 }
371 EvictionPolicy::FIFO | EvictionPolicy::Random => {
372 // No update needed
373 }
374 }
375
376 drop(entry_ref);
377
378 // Record cache hit
379 #[cfg(feature = "stats")]
380 self.stats.record_hit();
381
382 // Update LRU order on cache hit (after releasing DashMap lock)
383 if self.limit.is_some()
384 && (self.policy == EvictionPolicy::LRU
385 || self.policy == EvictionPolicy::ARC
386 || self.policy == EvictionPolicy::TLRU)
387 {
388 if self.cache.contains_key(key) {
389 let mut order = self.order.lock();
390 // Double-check after acquiring lock
391 if self.cache.contains_key(key) {
392 order.retain(|k| k != key);
393 order.push_back(key.to_string());
394 }
395 }
396 }
397
398 return Some(cached_value);
399 }
400
401 // Expired - remove and continue
402 drop(entry_ref);
403 self.cache.remove(key);
404
405 // Also remove from order queue to prevent orphaned keys
406 let mut order = self.order.lock();
407 order.retain(|k| k != key);
408 }
409
410 // Record cache miss
411 #[cfg(feature = "stats")]
412 self.stats.record_miss();
413
414 None
415 }
416
417 /// Inserts a value into the cache.
418 ///
419 /// This method handles cache limit enforcement and eviction according to
420 /// the configured policy. If the cache is full, it evicts an entry before
421 /// inserting the new one.
422 ///
423 /// # Arguments
424 ///
425 /// * `key` - The cache key
426 /// * `value` - The value to cache
427 ///
428 /// # Eviction Behavior
429 ///
430 /// - **FIFO**: Evicts the oldest inserted entry (front of queue)
431 /// - **LRU**: Evicts the least recently used entry (front of queue)
432 /// - **LFU**: Evicts the entry with the lowest frequency counter
433 /// - **ARC**: Evicts based on a hybrid score of frequency and recency
434 ///
435 /// # Thread Safety
436 ///
437 /// This method uses locks to ensure consistency between the cache and
438 /// the order queue. The order lock is held during eviction and insertion
439 /// to prevent race conditions.
440 ///
441 /// # Note
442 ///
443 /// This method does NOT require `MemoryEstimator` trait. It only handles entry-count limits.
444 /// If `max_memory` is configured, use `insert_with_memory()` instead, which requires
445 /// the type to implement `MemoryEstimator`.
446 ///
447 /// # Examples
448 ///
449 /// ```ignore
450 /// // Insert a new value
451 /// async_cache.insert("user:123", user_data);
452 ///
453 /// // Update existing value
454 /// async_cache.insert("user:123", updated_user_data);
455 /// ```
456 pub fn insert(&self, key: &str, value: R) {
457 let timestamp = std::time::SystemTime::now()
458 .duration_since(std::time::UNIX_EPOCH)
459 .unwrap()
460 .as_secs();
461
462 let mut order = self.order.lock();
463
464 // Check if another task already inserted this key while we were computing
465 if self.is_already_key_inserted(key, &mut order) {
466 return;
467 }
468
469 // Handle entry-count limits
470 self.handle_entry_limit_eviction(&mut order);
471
472 // Add the new entry to the order queue
473 order.push_back(key.to_string());
474
475 // Insert into cache with frequency initialized to 0
476 self.cache.insert(key.to_string(), (value, timestamp, 0));
477 }
478
479 /// Checks if a key is already present in the cache and updates its position in the eviction order
480 /// if the eviction policy is Least Recently Used (LRU) or Adaptive Replacement Cache (ARC).
481 ///
482 /// # Parameters
483 /// - `key`: A reference to the key being checked as a `&str`.
484 /// - `order`: A mutable reference to a locked `VecDeque<String>` wrapped in a `MutexGuard`.
485 /// This represents the ordered list of keys, used to determine eviction order.
486 ///
487 /// # Returns
488 /// - `true` if the key is already present in the cache and was processed for eviction policy.
489 /// - `false` if the key was not found in the cache.
490 ///
491 /// # Behavior
492 /// 1. If the key exists in the cache:
493 /// - If the eviction policy is `LRU` or `ARC`, the key's position in the eviction list (`order`)
494 /// is updated to reflect that it was recently accessed by removing the old position and appending
495 /// the key to the back of the `VecDeque`.
496 /// - The function returns `true`, indicating the key is already in the cache.
497 /// 2. If the key does not exist in the cache:
498 /// - The function returns `false`, allowing the caller to handle the key insertion.
499 ///
500 /// # Eviction Policies
501 /// - `LRU` (Least Recently Used): Keys recently accessed should stay in the cache,
502 /// and their access order is updated.
503 /// - `ARC` (Adaptive Replacement Cache): Performs similarly to LRU but may enhance
504 /// replacement policies in specific cases.
505 fn is_already_key_inserted(
506 &self,
507 key: &str,
508 order: &mut MutexGuard<RawMutex, VecDeque<String>>,
509 ) -> bool {
510 if self.cache.contains_key(key) {
511 // Key already exists, just update the order if LRU or ARC
512 if self.policy == EvictionPolicy::LRU || self.policy == EvictionPolicy::ARC {
513 order.retain(|k| k != key);
514 order.push_back(key.to_string());
515 }
516 // Don't insert again
517 return true;
518 }
519 false
520 }
521
522 /// Finds the key with minimum frequency for LFU eviction.
523 ///
524 /// # Parameters
525 ///
526 /// * `order` - The order queue to search
527 ///
528 /// # Returns
529 ///
530 /// * `Option<String>` - The key with minimum frequency, or None if not found
531 fn find_min_frequency_key(&self, order: &VecDeque<String>) -> Option<String> {
532 let mut min_freq_key: Option<String> = None;
533 let mut min_freq = u64::MAX;
534
535 for evict_key in order.iter() {
536 if let Some(entry) = self.cache.get(evict_key) {
537 if entry.2 < min_freq {
538 min_freq = entry.2;
539 min_freq_key = Some(evict_key.clone());
540 }
541 }
542 }
543
544 min_freq_key
545 }
546
547 /// Finds the key to evict using ARC (Adaptive Replacement Cache) policy.
548 ///
549 /// ARC uses a hybrid score combining frequency and recency.
550 /// Score = frequency * position_weight (higher position = more recent)
551 ///
552 /// # Parameters
553 ///
554 /// * `order` - The order queue to search
555 ///
556 /// # Returns
557 ///
558 /// * `Option<String>` - The key with lowest score, or None if not found
559 fn find_arc_eviction_key(&self, order: &VecDeque<String>) -> Option<String> {
560 let mut best_evict_key: Option<String> = None;
561 let mut best_score = f64::MAX;
562
563 for (idx, evict_key) in order.iter().enumerate() {
564 if let Some(entry) = self.cache.get(evict_key) {
565 let frequency = entry.2 as f64;
566 let position_weight = (order.len() - idx) as f64;
567 let score = frequency * position_weight;
568
569 if score < best_score {
570 best_score = score;
571 best_evict_key = Some(evict_key.clone());
572 }
573 }
574 }
575
576 best_evict_key
577 }
578
579 /// Finds the key with the lowest TLRU score for eviction.
580 ///
581 /// TLRU (Time-aware Least Recently Used) combines recency, frequency, and age factors
582 /// to determine which entry should be evicted.
583 ///
584 /// Score formula: `frequency^weight × position_weight × age_factor` (when `frequency_weight` is set;
585 /// otherwise `frequency × position_weight × age_factor`)
586 ///
587 /// Where:
588 /// - `frequency`: Access count for the entry
589 /// - `position_weight`: Higher for more recently accessed entries
590 /// - `age_factor`: Decreases as entry approaches TTL expiration (if TTL is set)
591 ///
592 /// # Returns
593 ///
594 /// * `Some(String)` - The key with the lowest TLRU score
595 /// * `None` - If the order queue is empty or no valid entries exist
596 fn find_tlru_eviction_key(&self, order: &VecDeque<String>) -> Option<String> {
597 let mut best_evict_key: Option<String> = None;
598 let mut best_score = f64::MAX;
599
600 let now = std::time::SystemTime::now()
601 .duration_since(std::time::UNIX_EPOCH)
602 .unwrap()
603 .as_secs();
604
605 for (idx, evict_key) in order.iter().enumerate() {
606 if let Some(entry) = self.cache.get(evict_key) {
607 let frequency = entry.2 as f64;
608 let position_weight = (order.len() - idx) as f64;
609
610 // Calculate age factor based on TTL
611 let age_factor = if let Some(ttl_secs) = self.ttl {
612 let entry_timestamp = entry.1;
613 let elapsed = now.saturating_sub(entry_timestamp) as f64;
614 let ttl_f64 = ttl_secs as f64;
615 // Entries close to expiration get lower scores (prioritized for eviction)
616 (1.0 - (elapsed / ttl_f64).min(1.0)).max(0.0)
617 } else {
618 1.0 // No TTL, age doesn't matter
619 };
620
621 // Apply frequency weight if provided
622 let frequency_component = if let Some(weight) = self.frequency_weight {
623 if frequency > 0.0 {
624 frequency.powf(weight)
625 } else {
626 0.0
627 }
628 } else {
629 frequency
630 };
631
632 // Score combines frequency, recency, and age
633 let score = frequency_component * position_weight * age_factor;
634
635 if score < best_score {
636 best_score = score;
637 best_evict_key = Some(evict_key.clone());
638 }
639 }
640 }
641
642 best_evict_key
643 }
644
645 /// Finds the key with minimum frequency in the W-TinyLFU protected segment.
646 ///
647 /// This is a helper method to avoid code duplication when implementing W-TinyLFU eviction.
648 /// The protected segment starts at `window_size` position in the order queue.
649 ///
650 /// # Parameters
651 ///
652 /// * `order` - Iterator over the order queue (already skipped to window_size position)
653 ///
654 /// # Returns
655 ///
656 /// The key with the lowest frequency in the protected segment, or `None` if the segment is empty.
657 fn find_min_frequency_in_protected_segment<'b, I>(&self, order: I) -> Option<String>
658 where
659 I: Iterator<Item = &'b String>,
660 {
661 let mut min_freq = u64::MAX;
662 let mut min_freq_key: Option<String> = None;
663
664 for key in order {
665 if let Some(entry) = self.cache.get(key) {
666 if entry.2 < min_freq {
667 min_freq = entry.2;
668 min_freq_key = Some(key.clone());
669 }
670 }
671 }
672
673 min_freq_key
674 }
675
676 /// Tries to evict an entry from the W-TinyLFU window segment.
677 ///
678 /// The window segment uses FIFO eviction (first entries in the order queue).
679 ///
680 /// # Parameters
681 ///
682 /// * `order` - Mutable reference to the order queue
683 /// * `window_size` - Size of the window segment
684 ///
685 /// # Returns
686 ///
687 /// `true` if an entry was successfully evicted, `false` otherwise.
688 fn try_evict_from_window(&self, order: &mut VecDeque<String>, window_size: usize) -> bool {
689 for i in 0..window_size.min(order.len()) {
690 if let Some(evict_key) = order.get(i) {
691 if self.cache.contains_key(evict_key) {
692 let key_to_remove = evict_key.clone();
693 self.cache.remove(&key_to_remove);
694 order.remove(i);
695 return true;
696 }
697 }
698 }
699 false
700 }
701
702 /// Handles the eviction of entries from the cache to enforce the entry limit based on the eviction policy.
703 ///
704 /// This method ensures that the number of entries in the cache does not exceed the configured limit by removing
705 /// entries based on the specified eviction policy.
706 ///
707 /// # Parameters
708 ///
709 /// * `order` - A mutable reference to the order queue
710 ///
711 /// # Behavior
712 ///
713 /// If the cache's entry limit is exceeded:
714 /// - **LFU**: Evicts the entry with the lowest frequency counter
715 /// - **ARC**: Evicts based on a hybrid score of frequency and recency
716 /// - **FIFO/LRU**: Evicts from the front of the queue
717 fn handle_entry_limit_eviction(&self, order: &mut VecDeque<String>) {
718 if let Some(limit) = self.limit {
719 if self.cache.len() >= limit {
720 match self.policy {
721 EvictionPolicy::LFU => {
722 if let Some(evict_key) = self.find_min_frequency_key(order) {
723 self.cache.remove(&evict_key);
724 order.retain(|k| k != &evict_key);
725 }
726 }
727 EvictionPolicy::ARC => {
728 if let Some(evict_key) = self.find_arc_eviction_key(order) {
729 self.cache.remove(&evict_key);
730 order.retain(|k| k != &evict_key);
731 }
732 }
733 EvictionPolicy::TLRU => {
734 if let Some(evict_key) = self.find_tlru_eviction_key(order) {
735 self.cache.remove(&evict_key);
736 order.retain(|k| k != &evict_key);
737 }
738 }
739 EvictionPolicy::Random => {
740 // O(1) random eviction: select random position and remove directly
741 if !order.is_empty() {
742 let pos = fastrand::usize(..order.len());
743 if let Some(evict_key) = order.remove(pos) {
744 self.cache.remove(&evict_key);
745 }
746 }
747 }
748 EvictionPolicy::FIFO | EvictionPolicy::LRU => {
749 // FIFO and LRU: evict from front of queue
750 while let Some(evict_key) = order.pop_front() {
751 if self.cache.contains_key(&evict_key) {
752 self.cache.remove(&evict_key);
753 break;
754 }
755 // Key doesn't exist in cache (already removed), try next one
756 }
757 }
758 EvictionPolicy::WTinyLFU => {
759 // W-TinyLFU: Window segment (first entries) + Protected segment (rest)
760 let window_ratio = self.window_ratio.unwrap_or(0.20); // Default 20%
761 let window_size = crate::utils::calculate_window_size(limit, window_ratio);
762
763 if order.len() <= window_size {
764 // Everything is in window segment - evict FIFO
765 while let Some(evict_key) = order.pop_front() {
766 if self.cache.contains_key(&evict_key) {
767 self.cache.remove(&evict_key);
768 break;
769 }
770 }
771 } else {
772 // We have both window and protected segments
773 // Try to evict from window first (first window_size entries)
774 let evicted = self.try_evict_from_window(order, window_size);
775
776 // If window eviction failed, evict from protected (LFU)
777 if !evicted {
778 // Protected segment is from window_size to end
779 // Find entry with minimum frequency in protected segment
780 if let Some(evict_key) = self
781 .find_min_frequency_in_protected_segment(
782 order.iter().skip(window_size),
783 )
784 {
785 self.cache.remove(&evict_key);
786 order.retain(|k| k != &evict_key);
787 }
788 }
789 }
790 }
791 }
792 }
793 }
794 }
795
796 /// Returns a reference to the cache statistics.
797 ///
798 /// This method is only available when the `stats` feature is enabled.
799 ///
800 /// # Available Metrics
801 ///
802 /// The returned CacheStats provides:
803 /// - **hits()**: Number of successful cache lookups
804 /// - **misses()**: Number of cache misses (key not found or expired)
805 /// - **hit_rate()**: Ratio of hits to total accesses (0.0 to 1.0)
806 /// - **total_accesses()**: Total number of get operations
807 ///
808 /// # Thread Safety
809 ///
810 /// Statistics use atomic counters (`AtomicU64`) and can be safely accessed
811 /// from multiple async tasks without additional synchronization.
812 ///
813 /// # Examples
814 ///
815 /// ```ignore
816 /// // Get basic statistics
817 /// let stats = async_cache.stats();
818 /// println!("Hits: {}", stats.hits());
819 /// println!("Misses: {}", stats.misses());
820 /// println!("Hit rate: {:.2}%", stats.hit_rate() * 100.0);
821 ///
822 /// // Monitor cache performance
823 /// let total = stats.total_accesses();
824 /// if total > 1000 && stats.hit_rate() < 0.5 {
825 /// println!("Warning: Low cache hit rate");
826 /// }
827 /// ```
828 ///
829 /// # See Also
830 ///
831 /// - [`CacheStats`] - The statistics structure
832 /// - [`crate::stats_registry::get()`] - Access stats by cache name
833 #[cfg(feature = "stats")]
834 pub fn stats(&self) -> &CacheStats {
835 self.stats
836 }
837}
838
839// Separate implementation for types that implement MemoryEstimator
840// This allows memory-based eviction
841impl<'a, R: Clone + crate::MemoryEstimator> AsyncGlobalCache<'a, R> {
842 /// Insert with memory limit support.
843 ///
844 /// This method requires `R` to implement `MemoryEstimator` and handles both
845 /// memory-based and entry-count-based eviction.
846 ///
847 /// Use this method when `max_memory` is configured in the cache.
848 ///
849 /// # Arguments
850 ///
851 /// * `key` - The cache key
852 /// * `value` - The value to cache (must implement `MemoryEstimator`)
853 ///
854 /// # Memory Management
855 ///
856 /// The method calculates the memory footprint of all cached entries and evicts
857 /// entries as needed to stay within the `max_memory` limit. Eviction follows
858 /// the configured policy.
859 ///
860 /// # Safety Check
861 ///
862 /// If the value to be inserted is larger than `max_memory`, the insertion is
863 /// skipped entirely to avoid infinite eviction loops. This ensures the cache
864 /// respects the memory limit even if individual values are very large.
865 ///
866 /// # Eviction Behavior by Policy
867 ///
868 /// When memory limit is exceeded:
869 /// - **FIFO/LRU**: Evicts from front of order queue
870 /// - **LFU**: Evicts entry with lowest frequency
871 /// - **ARC**: Evicts based on hybrid score (frequency × position_weight)
872 /// - **TLRU**: Evicts based on TLRU score (frequency^weight × position × age_factor)
873 /// - **Random**: Evicts randomly selected entry
874 ///
875 /// The eviction loop continues until there's enough memory for the new value.
876 ///
877 /// # Entry Count Limit
878 ///
879 /// After satisfying memory constraints, this method also checks the entry count
880 /// limit (if configured) and evicts additional entries if needed.
881 ///
882 /// # Examples
883 ///
884 /// ```ignore
885 /// use cachelito_core::MemoryEstimator;
886 ///
887 /// // Type must implement MemoryEstimator
888 /// impl MemoryEstimator for MyLargeStruct {
889 /// fn estimate_memory(&self) -> usize {
890 /// std::mem::size_of::<Self>() + self.data.capacity()
891 /// }
892 /// }
893 ///
894 /// // Insert with automatic memory-based eviction
895 /// async_cache.insert_with_memory("large_data", expensive_value);
896 /// ```
897 ///
898 /// # Performance
899 ///
900 /// - **Memory calculation**: O(n) - iterates all entries to sum memory
901 /// - **Eviction**: Varies by policy (see individual policy documentation)
902 /// - May evict multiple entries in one call if memory limit is tight
903 pub fn insert_with_memory(&self, key: &str, value: R) {
904 let timestamp = std::time::SystemTime::now()
905 .duration_since(std::time::UNIX_EPOCH)
906 .unwrap()
907 .as_secs();
908
909 let mut order = self.order.lock();
910
911 // Check if another task already inserted this key while we were computing
912 if self.is_already_key_inserted(key, &mut order) {
913 return;
914 }
915
916 // Check memory limit first (if specified)
917 if let Some(max_mem) = self.max_memory {
918 let value_size = value.estimate_memory();
919
920 // Safety check: if the value itself is larger than max_mem,
921 // we need to handle it to avoid infinite loop
922 if value_size > max_mem {
923 // Value is too large to fit in cache even when empty
924 // We have two options:
925 // 1. Don't cache it at all (skip insertion)
926 // 2. Clear all entries and cache it anyway
927 // We choose option 1 to respect the memory limit
928 return;
929 }
930
931 loop {
932 let current_mem: usize = self
933 .cache
934 .iter()
935 .map(|entry| entry.value().0.estimate_memory())
936 .sum();
937
938 if current_mem + value_size <= max_mem {
939 break;
940 }
941
942 // Need to evict based on policy
943 let evicted = match self.policy {
944 EvictionPolicy::LFU => {
945 if let Some(evict_key) = self.find_min_frequency_key(&*order) {
946 self.cache.remove(&evict_key);
947 order.retain(|k| k != &evict_key);
948 true
949 } else {
950 false
951 }
952 }
953 EvictionPolicy::ARC => {
954 if let Some(evict_key) = self.find_arc_eviction_key(&*order) {
955 self.cache.remove(&evict_key);
956 order.retain(|k| k != &evict_key);
957 true
958 } else {
959 false
960 }
961 }
962 EvictionPolicy::TLRU => {
963 if let Some(evict_key) = self.find_tlru_eviction_key(&*order) {
964 self.cache.remove(&evict_key);
965 order.retain(|k| k != &evict_key);
966 true
967 } else {
968 false
969 }
970 }
971 EvictionPolicy::Random => {
972 // O(1) random eviction: select random position and remove directly
973 if !order.is_empty() {
974 let pos = fastrand::usize(..order.len());
975 if let Some(evict_key) = order.remove(pos) {
976 self.cache.remove(&evict_key);
977 true
978 } else {
979 false
980 }
981 } else {
982 false
983 }
984 }
985 EvictionPolicy::FIFO | EvictionPolicy::LRU => {
986 if let Some(evict_key) = order.pop_front() {
987 self.cache.remove(&evict_key);
988 true
989 } else {
990 false
991 }
992 }
993 EvictionPolicy::WTinyLFU => {
994 // W-TinyLFU: Window segment (first entries) + Protected segment (rest)
995 let window_ratio = self.window_ratio.unwrap_or(0.20); // Default 20%
996 let limit = self.limit.unwrap_or(usize::MAX);
997 let window_size = crate::utils::calculate_window_size(limit, window_ratio);
998
999 if order.len() <= window_size {
1000 // Everything is in window segment - evict FIFO
1001 if let Some(evict_key) = order.pop_front() {
1002 if self.cache.contains_key(&evict_key) {
1003 self.cache.remove(&evict_key);
1004 true
1005 } else {
1006 // Try next key if this one doesn't exist
1007 false
1008 }
1009 } else {
1010 false
1011 }
1012 } else {
1013 // We have both window and protected segments
1014 // Try to evict from window first (first window_size entries)
1015 let evicted = self.try_evict_from_window(&mut order, window_size);
1016
1017 // If window eviction failed, evict from protected (LFU)
1018 if !evicted {
1019 // Protected segment is from window_size to end
1020 // Find entry with minimum frequency in protected segment
1021 if let Some(evict_key) = self
1022 .find_min_frequency_in_protected_segment(
1023 order.iter().skip(window_size),
1024 )
1025 {
1026 self.cache.remove(&evict_key);
1027 order.retain(|k| k != &evict_key);
1028 true
1029 } else {
1030 false
1031 }
1032 } else {
1033 true
1034 }
1035 }
1036 }
1037 };
1038
1039 if !evicted {
1040 break; // Nothing left to evict
1041 }
1042 }
1043 }
1044
1045 // Handle entry-count limits (reuse the same method)
1046 self.handle_entry_limit_eviction(&mut order);
1047
1048 // Add the new entry to the order queue
1049 order.push_back(key.to_string());
1050
1051 // Insert into cache with frequency initialized to 0
1052 self.cache.insert(key.to_string(), (value, timestamp, 0));
1053 }
1054}
1055
1056#[cfg(test)]
1057mod tests {
1058 use super::*;
1059 use std::time::{SystemTime, UNIX_EPOCH};
1060
1061 #[test]
1062 fn test_async_cache_basic() {
1063 let cache = DashMap::new();
1064 let order = Mutex::new(VecDeque::new());
1065
1066 #[cfg(not(feature = "stats"))]
1067 let async_cache =
1068 AsyncGlobalCache::new(&cache, &order, None, None, EvictionPolicy::FIFO, None, None);
1069
1070 #[cfg(feature = "stats")]
1071 let stats = CacheStats::new();
1072 #[cfg(feature = "stats")]
1073 let async_cache = AsyncGlobalCache::new(
1074 &cache,
1075 &order,
1076 None,
1077 None,
1078 EvictionPolicy::FIFO,
1079 None,
1080 None,
1081 None,
1082 &stats,
1083 );
1084
1085 // Test insert and get
1086 async_cache.insert("key1", "value1");
1087 assert_eq!(async_cache.get("key1"), Some("value1"));
1088 assert_eq!(async_cache.get("key2"), None);
1089 }
1090
1091 #[test]
1092 fn test_async_cache_lfu_eviction() {
1093 let cache = DashMap::new();
1094 let order = Mutex::new(VecDeque::new());
1095
1096 #[cfg(not(feature = "stats"))]
1097 let async_cache = AsyncGlobalCache::new(
1098 &cache,
1099 &order,
1100 Some(2),
1101 None,
1102 EvictionPolicy::LFU,
1103 None,
1104 None,
1105 );
1106
1107 #[cfg(feature = "stats")]
1108 let stats = CacheStats::new();
1109 #[cfg(feature = "stats")]
1110 let async_cache = AsyncGlobalCache::new(
1111 &cache,
1112 &order,
1113 Some(2),
1114 None,
1115 EvictionPolicy::LFU,
1116 None,
1117 None,
1118 None,
1119 &stats,
1120 );
1121
1122 // Insert two entries
1123 async_cache.insert("key1", "value1");
1124 async_cache.insert("key2", "value2");
1125
1126 // Access key1 multiple times to increase frequency
1127 for _ in 0..5 {
1128 async_cache.get("key1");
1129 }
1130
1131 // Insert key3 - should evict key2 (lower frequency)
1132 async_cache.insert("key3", "value3");
1133
1134 // key1 should still be cached (high frequency)
1135 assert_eq!(async_cache.get("key1"), Some("value1"));
1136 // key2 should be evicted
1137 assert_eq!(async_cache.get("key2"), None);
1138 // key3 should be cached
1139 assert_eq!(async_cache.get("key3"), Some("value3"));
1140 }
1141
1142 #[test]
1143 fn test_async_cache_ttl_boundary_expires() {
1144 let cache = DashMap::new();
1145 let order = Mutex::new(VecDeque::new());
1146
1147 #[cfg(not(feature = "stats"))]
1148 let async_cache = AsyncGlobalCache::new(
1149 &cache,
1150 &order,
1151 None,
1152 None,
1153 EvictionPolicy::FIFO,
1154 Some(1),
1155 None,
1156 );
1157
1158 #[cfg(feature = "stats")]
1159 let stats = CacheStats::new();
1160 #[cfg(feature = "stats")]
1161 let async_cache = AsyncGlobalCache::new(
1162 &cache,
1163 &order,
1164 None,
1165 None,
1166 EvictionPolicy::FIFO,
1167 Some(1),
1168 None,
1169 None,
1170 &stats,
1171 );
1172
1173 let now = SystemTime::now()
1174 .duration_since(UNIX_EPOCH)
1175 .unwrap()
1176 .as_secs();
1177 // Insert with timestamp exactly 1 second in the past (age == ttl)
1178 cache.insert("k".to_string(), ("v", now.saturating_sub(1), 0));
1179
1180 // With >= comparison, this must be considered expired
1181 assert_eq!(async_cache.get("k"), None);
1182 }
1183
1184 #[test]
1185 fn test_async_cache_clock_moves_backwards_not_expired() {
1186 let cache = DashMap::new();
1187 let order = Mutex::new(VecDeque::new());
1188
1189 #[cfg(not(feature = "stats"))]
1190 let async_cache = AsyncGlobalCache::new(
1191 &cache,
1192 &order,
1193 None,
1194 None,
1195 EvictionPolicy::FIFO,
1196 Some(10),
1197 None,
1198 );
1199
1200 #[cfg(feature = "stats")]
1201 let stats = CacheStats::new();
1202 #[cfg(feature = "stats")]
1203 let async_cache = AsyncGlobalCache::new(
1204 &cache,
1205 &order,
1206 None,
1207 None,
1208 EvictionPolicy::FIFO,
1209 Some(10),
1210 None,
1211 None,
1212 &stats,
1213 );
1214
1215 let now = SystemTime::now()
1216 .duration_since(UNIX_EPOCH)
1217 .unwrap()
1218 .as_secs();
1219 // Insert via the cache API so the 'order' queue is updated as well
1220 async_cache.insert("k", "v");
1221
1222 // Simulate a "future" timestamp (as if the clock moved backwards later)
1223 // Adjust only the timestamp of the already inserted entry
1224 let future_ts = now.saturating_add(100);
1225 if let Some(mut entry) = cache.get_mut("k") {
1226 entry.1 = future_ts;
1227 }
1228
1229 // With saturating_sub, age = 0, which is < ttl => NOT expired
1230 assert_eq!(async_cache.get("k"), Some("v"));
1231
1232 // Verify that the order queue contains the key "k"
1233 assert!(order.lock().contains(&"k".to_string()));
1234 }
1235
1236 // ========== TLRU with frequency_weight tests ==========
1237
1238 #[test]
1239 fn test_tlru_with_low_frequency_weight() {
1240 let cache = DashMap::new();
1241 let order = Mutex::new(VecDeque::new());
1242
1243 #[cfg(not(feature = "stats"))]
1244 let async_cache = AsyncGlobalCache::new(
1245 &cache,
1246 &order,
1247 Some(3),
1248 None,
1249 EvictionPolicy::TLRU,
1250 Some(10),
1251 Some(0.3), // Low weight - emphasizes recency
1252 );
1253
1254 #[cfg(feature = "stats")]
1255 let stats = CacheStats::new();
1256 #[cfg(feature = "stats")]
1257 let async_cache = AsyncGlobalCache::new(
1258 &cache,
1259 &order,
1260 Some(3),
1261 None,
1262 EvictionPolicy::TLRU,
1263 Some(10),
1264 Some(0.3),
1265 None,
1266 &stats,
1267 );
1268
1269 // Fill cache
1270 async_cache.insert("k1", 1);
1271 async_cache.insert("k2", 2);
1272 async_cache.insert("k3", 3);
1273
1274 // Make k1 very frequent
1275 for _ in 0..10 {
1276 let _ = async_cache.get("k1");
1277 }
1278
1279 // Wait a bit to age k1
1280 std::thread::sleep(std::time::Duration::from_millis(100));
1281
1282 // Add new entry (cache is full)
1283 async_cache.insert("k4", 4);
1284
1285 // With low frequency_weight, even frequent entries can be evicted
1286 // if they're older (recency and age matter more)
1287 assert_eq!(async_cache.get("k4"), Some(4));
1288 }
1289
1290 #[test]
1291 fn test_tlru_with_high_frequency_weight() {
1292 let cache = DashMap::new();
1293 let order = Mutex::new(VecDeque::new());
1294
1295 #[cfg(not(feature = "stats"))]
1296 let async_cache = AsyncGlobalCache::new(
1297 &cache,
1298 &order,
1299 Some(3),
1300 None,
1301 EvictionPolicy::TLRU,
1302 Some(10),
1303 Some(1.5), // High weight - emphasizes frequency
1304 );
1305
1306 #[cfg(feature = "stats")]
1307 let stats = CacheStats::new();
1308 #[cfg(feature = "stats")]
1309 let async_cache = AsyncGlobalCache::new(
1310 &cache,
1311 &order,
1312 Some(3),
1313 None,
1314 EvictionPolicy::TLRU,
1315 Some(10),
1316 Some(1.5),
1317 None,
1318 &stats,
1319 );
1320
1321 // Fill cache
1322 async_cache.insert("k1", 1);
1323 async_cache.insert("k2", 2);
1324 async_cache.insert("k3", 3);
1325
1326 // Make k1 very frequent
1327 for _ in 0..10 {
1328 let _ = async_cache.get("k1");
1329 }
1330
1331 // Wait a bit to age k1
1332 std::thread::sleep(std::time::Duration::from_millis(100));
1333
1334 // Add new entry (cache is full)
1335 async_cache.insert("k4", 4);
1336
1337 // With high frequency_weight, frequent entries are protected
1338 // k1 should remain cached despite being older
1339 assert_eq!(async_cache.get("k1"), Some(1));
1340 assert_eq!(async_cache.get("k4"), Some(4));
1341 }
1342
1343 #[test]
1344 fn test_tlru_default_frequency_weight() {
1345 let cache = DashMap::new();
1346 let order = Mutex::new(VecDeque::new());
1347
1348 #[cfg(not(feature = "stats"))]
1349 let async_cache = AsyncGlobalCache::new(
1350 &cache,
1351 &order,
1352 Some(2),
1353 None,
1354 EvictionPolicy::TLRU,
1355 Some(5),
1356 None, // Default weight (balanced)
1357 );
1358
1359 #[cfg(feature = "stats")]
1360 let stats = CacheStats::new();
1361 #[cfg(feature = "stats")]
1362 let async_cache = AsyncGlobalCache::new(
1363 &cache,
1364 &order,
1365 Some(2),
1366 None,
1367 EvictionPolicy::TLRU,
1368 Some(5),
1369 None,
1370 None,
1371 &stats,
1372 );
1373
1374 async_cache.insert("k1", 1);
1375 async_cache.insert("k2", 2);
1376
1377 // Access k1 a few times
1378 for _ in 0..3 {
1379 let _ = async_cache.get("k1");
1380 }
1381
1382 // Add third entry
1383 async_cache.insert("k3", 3);
1384
1385 // With balanced weight, both frequency and recency matter
1386 // k1 has higher frequency, so it should remain
1387 assert_eq!(async_cache.get("k1"), Some(1));
1388 assert_eq!(async_cache.get("k3"), Some(3));
1389 }
1390
1391 #[test]
1392 fn test_tlru_no_ttl_with_frequency_weight() {
1393 let cache = DashMap::new();
1394 let order = Mutex::new(VecDeque::new());
1395
1396 #[cfg(not(feature = "stats"))]
1397 let async_cache = AsyncGlobalCache::new(
1398 &cache,
1399 &order,
1400 Some(3),
1401 None,
1402 EvictionPolicy::TLRU,
1403 None, // No TTL - age_factor will be 1.0
1404 Some(1.5),
1405 );
1406
1407 #[cfg(feature = "stats")]
1408 let stats = CacheStats::new();
1409 #[cfg(feature = "stats")]
1410 let async_cache = AsyncGlobalCache::new(
1411 &cache,
1412 &order,
1413 Some(3),
1414 None,
1415 EvictionPolicy::TLRU,
1416 None,
1417 Some(1.5),
1418 None,
1419 &stats,
1420 );
1421
1422 async_cache.insert("k1", 1);
1423 async_cache.insert("k2", 2);
1424 async_cache.insert("k3", 3);
1425
1426 // Make k1 very frequent
1427 for _ in 0..10 {
1428 let _ = async_cache.get("k1");
1429 }
1430
1431 // Add new entry
1432 async_cache.insert("k4", 4);
1433
1434 // Without TTL, TLRU focuses on frequency and position
1435 // k1 should remain due to high frequency
1436 assert_eq!(async_cache.get("k1"), Some(1));
1437 }
1438
1439 #[test]
1440 fn test_tlru_frequency_weight_comparison() {
1441 // Test that different weights produce different behavior
1442 let cache_low = DashMap::new();
1443 let order_low = Mutex::new(VecDeque::new());
1444 let cache_high = DashMap::new();
1445 let order_high = Mutex::new(VecDeque::new());
1446
1447 #[cfg(not(feature = "stats"))]
1448 let async_cache_low = AsyncGlobalCache::new(
1449 &cache_low,
1450 &order_low,
1451 Some(2),
1452 None,
1453 EvictionPolicy::TLRU,
1454 Some(10),
1455 Some(0.3), // Low weight
1456 );
1457
1458 #[cfg(not(feature = "stats"))]
1459 let async_cache_high = AsyncGlobalCache::new(
1460 &cache_high,
1461 &order_high,
1462 Some(2),
1463 None,
1464 EvictionPolicy::TLRU,
1465 Some(10),
1466 Some(2.0), // High weight
1467 );
1468
1469 #[cfg(feature = "stats")]
1470 let stats_low = CacheStats::new();
1471 #[cfg(feature = "stats")]
1472 let async_cache_low = AsyncGlobalCache::new(
1473 &cache_low,
1474 &order_low,
1475 Some(2),
1476 None,
1477 EvictionPolicy::TLRU,
1478 Some(10),
1479 Some(0.3),
1480 None,
1481 &stats_low,
1482 );
1483
1484 #[cfg(feature = "stats")]
1485 let stats_high = CacheStats::new();
1486 #[cfg(feature = "stats")]
1487 let async_cache_high = AsyncGlobalCache::new(
1488 &cache_high,
1489 &order_high,
1490 Some(2),
1491 None,
1492 EvictionPolicy::TLRU,
1493 Some(10),
1494 Some(2.0),
1495 None,
1496 &stats_high,
1497 );
1498
1499 // Same operations on both caches
1500 async_cache_low.insert("k1", 1);
1501 async_cache_low.insert("k2", 2);
1502 async_cache_high.insert("k1", 1);
1503 async_cache_high.insert("k2", 2);
1504
1505 // Make k1 frequent in both
1506 for _ in 0..5 {
1507 let _ = async_cache_low.get("k1");
1508 let _ = async_cache_high.get("k1");
1509 }
1510
1511 std::thread::sleep(std::time::Duration::from_millis(50));
1512
1513 // Add new entry to both
1514 async_cache_low.insert("k3", 3);
1515 async_cache_high.insert("k3", 3);
1516
1517 // Both should work correctly with their respective weights
1518 assert_eq!(async_cache_low.get("k3"), Some(3));
1519 assert_eq!(async_cache_high.get("k3"), Some(3));
1520 }
1521
1522 #[test]
1523 fn test_tlru_concurrent_with_frequency_weight() {
1524 use std::sync::Arc;
1525 use std::thread;
1526
1527 let cache = Arc::new(DashMap::new());
1528 let order = Arc::new(Mutex::new(VecDeque::new()));
1529
1530 #[cfg(feature = "stats")]
1531 let stats = Arc::new(CacheStats::new());
1532
1533 // Insert initial entries
1534 {
1535 #[cfg(not(feature = "stats"))]
1536 let async_cache = AsyncGlobalCache::new(
1537 &cache,
1538 &order,
1539 Some(10),
1540 None,
1541 EvictionPolicy::TLRU,
1542 Some(10),
1543 Some(1.2), // Slightly emphasize frequency
1544 );
1545
1546 #[cfg(feature = "stats")]
1547 let async_cache = AsyncGlobalCache::new(
1548 &cache,
1549 &order,
1550 Some(10),
1551 None,
1552 EvictionPolicy::TLRU,
1553 Some(10),
1554 Some(1.2),
1555 None,
1556 &stats,
1557 );
1558
1559 async_cache.insert("k1", 1);
1560 async_cache.insert("k2", 2);
1561 }
1562
1563 // Spawn multiple threads accessing the cache
1564 let handles: Vec<_> = (0..5)
1565 .map(|i| {
1566 let cache_clone = Arc::clone(&cache);
1567 let order_clone = Arc::clone(&order);
1568 #[cfg(feature = "stats")]
1569 let stats_clone = Arc::clone(&stats);
1570
1571 thread::spawn(move || {
1572 #[cfg(not(feature = "stats"))]
1573 let async_cache = AsyncGlobalCache::new(
1574 &cache_clone,
1575 &order_clone,
1576 Some(10),
1577 None,
1578 EvictionPolicy::TLRU,
1579 Some(10),
1580 Some(1.2),
1581 );
1582
1583 #[cfg(feature = "stats")]
1584 let async_cache = AsyncGlobalCache::new(
1585 &cache_clone,
1586 &order_clone,
1587 Some(10),
1588 None,
1589 EvictionPolicy::TLRU,
1590 Some(10),
1591 Some(1.2),
1592 None,
1593 &stats_clone,
1594 );
1595
1596 // Access k1 frequently
1597 for _ in 0..3 {
1598 let _ = async_cache.get("k1");
1599 }
1600
1601 // Insert new entry
1602 async_cache.insert(&format!("k{}", i + 3), i + 3);
1603 })
1604 })
1605 .collect();
1606
1607 for handle in handles {
1608 handle.join().unwrap();
1609 }
1610
1611 // k1 should remain cached due to high frequency and frequency_weight > 1.0
1612 #[cfg(not(feature = "stats"))]
1613 let async_cache = AsyncGlobalCache::new(
1614 &cache,
1615 &order,
1616 Some(10),
1617 None,
1618 EvictionPolicy::TLRU,
1619 Some(10),
1620 Some(1.2),
1621 None,
1622 );
1623
1624 #[cfg(feature = "stats")]
1625 let async_cache = AsyncGlobalCache::new(
1626 &cache,
1627 &order,
1628 Some(10),
1629 None,
1630 EvictionPolicy::TLRU,
1631 Some(10),
1632 Some(1.2),
1633 None,
1634 &stats,
1635 );
1636
1637 assert_eq!(async_cache.get("k1"), Some(1));
1638 }
1639
1640 #[test]
1641 fn test_tlru_frequency_weight_edge_cases() {
1642 let cache = DashMap::new();
1643 let order = Mutex::new(VecDeque::new());
1644
1645 #[cfg(not(feature = "stats"))]
1646 let async_cache = AsyncGlobalCache::new(
1647 &cache,
1648 &order,
1649 Some(2),
1650 None,
1651 EvictionPolicy::TLRU,
1652 Some(5),
1653 Some(0.1), // Very low weight
1654 None,
1655 );
1656
1657 #[cfg(feature = "stats")]
1658 let stats = CacheStats::new();
1659 #[cfg(feature = "stats")]
1660 let async_cache = AsyncGlobalCache::new(
1661 &cache,
1662 &order,
1663 Some(2),
1664 None,
1665 EvictionPolicy::TLRU,
1666 Some(5),
1667 Some(0.1),
1668 None,
1669 &stats,
1670 );
1671
1672 async_cache.insert("k1", 1);
1673 async_cache.insert("k2", 2);
1674
1675 // Make k1 extremely frequent
1676 for _ in 0..100 {
1677 let _ = async_cache.get("k1");
1678 }
1679
1680 std::thread::sleep(std::time::Duration::from_millis(50));
1681
1682 // Even with very high frequency, k1 might be evicted with very low weight
1683 async_cache.insert("k3", 3);
1684
1685 // The cache should still work correctly
1686 assert!(async_cache.get("k3").is_some());
1687 }
1688
1689 #[test]
1690 fn test_tlru_frequency_weight_with_lru_pattern() {
1691 let cache = DashMap::new();
1692 let order = Mutex::new(VecDeque::new());
1693
1694 #[cfg(not(feature = "stats"))]
1695 let async_cache = AsyncGlobalCache::new(
1696 &cache,
1697 &order,
1698 Some(3),
1699 None,
1700 EvictionPolicy::TLRU,
1701 Some(10),
1702 Some(1.0), // Weight = 1.0 (linear frequency impact)
1703 None,
1704 );
1705
1706 #[cfg(feature = "stats")]
1707 let stats = CacheStats::new();
1708 #[cfg(feature = "stats")]
1709 let async_cache = AsyncGlobalCache::new(
1710 &cache,
1711 &order,
1712 Some(3),
1713 None,
1714 EvictionPolicy::TLRU,
1715 Some(10),
1716 Some(1.0),
1717 None,
1718 &stats,
1719 );
1720
1721 async_cache.insert("k1", 1);
1722 async_cache.insert("k2", 2);
1723 async_cache.insert("k3", 3);
1724
1725 // Create LRU-like access pattern
1726 let _ = async_cache.get("k1");
1727 let _ = async_cache.get("k2");
1728 let _ = async_cache.get("k1");
1729 let _ = async_cache.get("k2");
1730
1731 // k3 has not been accessed, should be evicted first
1732 async_cache.insert("k4", 4);
1733
1734 assert_eq!(async_cache.get("k1"), Some(1));
1735 assert_eq!(async_cache.get("k2"), Some(2));
1736 assert_eq!(async_cache.get("k4"), Some(4));
1737 // k3 should be evicted (least recently used and zero frequency)
1738 assert_eq!(async_cache.get("k3"), None);
1739 }
1740}