Comments (1)
Hi. Sorry for the late reply, and thank you for the request. Your idea seems feasible to me.
Before we talk about your idea, let me explain how Moka cache works today.
When cache's capacity is exceeded, there are two timings when entry can be evicted:
- Right after the insertion: An entry can be evicted by the historic LFU (Least Frequently Used) filter.
- This filter prevents unpopular key to get into the cache.
- Some time after the insertion: An entry can be evicted after dropping off from the LRU (Least Recently Used) queue.
Please see the TinyLFU diagram in this section of the wiki page.
TinyLFU policy may not work very well for certain access patterns. I wonder if you are hitting this problem. The access pattern is like the followings:
- Inserting an entry whose key has never been accessed before.
- But once inserted, the key will be accessed often for a while.
While the cache has enough capacity, everything will be okay because new entries will be admitted anyway. After the admission, they will be accessed so they will build up popularity. However, once the cache becomes full, this will become a problem. New entries will not be admitted because their keys were never accessed before; they are less popular than the old ones. They will be evicted immediately after the insertion.
In the future, we will upgrade TinyLFU to W-TinyLFU, which has an admission LRU window in front of the LFU filter. W-TinyLFU will work better for the access pattern above because the LRU window will help the new entries to build up the popularity.
If you are hitting this problem, W-TinyLFU will mitigate it. W-TinyLFU will work automatically for all users; no need to set the callback. So I wonder which one we should implement first: W-TinyLFU? or your conditional eviction idea?
One could argue that W-TinyLFU still does not guarantee that an entry is not evicted while it is alive. (e.g. the entry has very long life)
If we implement your idea, we could add two pending eviction queues to the cache: one for 1., and another for 2. If the callback returned false
on an entry, that entry will be added to one of these queues and kept in the cache.
Also, there are other cases when entry will be removed from a cache, so we need to decide what to do for such cases:
- An entry can be expired when TTL (time-to-live) or TTI (time-to-idle) timer exceeded:
- With the current spec, get operation never returns expired entry.
- Should the callback prevent the entry from expiring?
- We could add a config flag to the cache builder to customize this behavior.
- An entry can be replaced by another
insert
on the same key:- With the current spec,
insert
always succeeds and replaces the old entry.insert
has no return value; no way to tell wheninsert
is failed.
- So, should we keep the current
insert
behavior by ignoring the callback? - Note that one can use
get_with
to avoid replacing an existing entry.
- With the current spec,
- An entry can be invalidated by
invalidate
,invalidate_all
, etc.:- With the current spec,
invalidate
etc. always succeeds and removes the entry.invalidate
has no return value; no way to tell wheninvalidate
is failed.
- So, should we keep the current
invalidate
behavior by ignoring the callback?
- With the current spec,
from moka.
Related Issues (20)
- Try `seize` as a replacement of `crossbeam-epoch`? HOT 4
- Refactoring: Cache policy implementations HOT 2
- Do not swallow the panic when the eviction listener is panicked
- Crash in iOS HOT 3
- Unable to use moka when miri testing HOT 3
- Inefficient size aware eviction when inserting new entries with larger size HOT 3
- Consider switching to TinyUFO HOT 2
- Pending `run_pending_tasks` may cause busy loop in `schedule_write_op` HOT 14
- Miri errors on the `timer_wheel` module. (Miri v0.1.0 8b2459c1 2024-04-09) HOT 1
- CI: Kani verifier v0.49.0 uses Rust `nightly-2024-03-29`, which cannot compile `[email protected]` HOT 2
- Should Moka work in WASM? HOT 2
- Size Aware Eviction: First-In-First-Out, or evicting largest items first? HOT 2
- Latest triomphe update breaks MSRV
- The `once_cell` dependency should be optional
- Update Key With One Evaluation of the `init` Future HOT 12
- Feature Request: Alternative compute API that skips if other thread/async task is already computing for the key
- Locking `triomphe` is the wrong approach to preserving MSRV HOT 2
- CI: Run Linux arm64 tests only once a week on `arm1.small` instance at AWS CodeBuild
- Use SIEVE as underlying LRU?
- Unexpected behavior with LRU HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from moka.