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)
- Statistics for metrics HOT 3
- `get_with` deadlock HOT 13
- `.blocking().invalidate(key)` doesn't trigger eviction listener HOT 1
- RUSTSEC-2020-0168: mach is unmaintained HOT 2
- Can the eviction strategy be configured? HOT 8
- Upgrade the cache policy from TinyLFU to W-TinyLFU
- Bump the MSRV to 1.60
- optionally_try_get_with in moka::future::Cache HOT 1
- feature request: remove method HOT 2
- Use `std::thread::available_parallelism()` instead of `num_cpus` dependency
- Eviction listener not always called. HOT 2
- Cache housekeeper can panic (seen after 50M+ insertions) HOT 4
- CI: Miri test causes a complie error with Rust nightly-2023-05-27 HOT 2
- Implement Serialize trait for debugging webserver? HOT 2
- Data race found by `miri test` HOT 9
- CI: Enable Miri tests on `moka::cht::*` modules
- Memory corruption observed when using Moka v0.9.6 HOT 15
- unbounded capacity? HOT 2
- Possibility of using async runtime tasks instead of thread pools HOT 10
- oom caused after use #234's statistics record code HOT 4
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.