apache / apache/datafusion

Decoupling Cache and Eviction Strategies

Open
#18,405 4 comments 1 reaction 0 assignees View on GitHub
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

Currently for a given Cache like `DefaultFilesMetadataCache`, all the Cache Storage and Retrieval mechanisms are tightly coupled with Eviction Strategy.

```
struct DefaultFilesMetadataCacheState {
lru_queue: LruQueue)>,
memory_limit: usize,
memory_used: usize,
cache_hits: HashMap,
}
```

For any change in Eviction Policy strategy, we would have to end up implementing a new DataStructure having its' own implementation of Cache Accessing methods.

### Proposed Flow:
Instead, we can decouple the Cache Data Structure and the Eviction Strategies by doing something similar as below:
```
pub struct CustomMetadataCache {
/// (DashMap-based, already thread-safe)
inner_cache: DashMap,
/// The eviction policy (thread-safe)
eviction_strategy: Arc>>,
.
.
.
.
```

Accompanied by a pluggable Cache Strategy which would be listening to events from Cache-Storage and accordingly select items of eviction
```
// Core trait for cache eviction strategy
pub trait EvictionStrategy: Send + Sync {
/// Called when a cache entry is accessed
fn on_access(&mut self, key: &str, size: usize);

/// Called when a cache entry is inserted
fn on_insert(&mut self, key: &str, size: usize);

/// Called when a cache entry is removed
fn on_remove(&mut self, key: &str);

/// Select entries for eviction to reach target size
/// Returns keys to evict, ordered by eviction priority
fn select_for_eviction(&self, target_size: usize) -> Vec;

/// Reset policy state
fn clear(&mut self);

/// Get the name of this strategy
fn strategy_name(&self) -> &'static str;
}
```

Benefits

- Separation of Concerns: Cache storage logic is independent of eviction policy
- Strategy Hot-Swapping: Change eviction strategies without recompiling the cache
- Multiple Implementations: Support LRU, LFU, FIFO, ARC, LIRS, or custom strategies out-of-the-box
- Per-Cache Policies and Code Re-usability: Different cache instances can use different strategies
- Reduced Duplication: Eliminate duplicated cache access code across implementations

@alamb @nuno-faria

Contributor guide

Open the contributing guide

Research direction

Start by locating DefaultFilesMetadataCache and DefaultFilesMetadataCacheState, then trace how cache storage, retrieval, and eviction currently interact. Compare that flow with the proposed EvictionStrategy interface and determine the project’s existing cache access points. Done should mean storage and eviction policy are separable without duplicating cache access logic, with the existing behavior preserved.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.