Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

W-TinyLFU policy should update the frequency of the key even if it is not in the cache #849

Open
tatsuya6502 opened this issue Jan 26, 2025 · 3 comments · May be fixed by #850
Open

W-TinyLFU policy should update the frequency of the key even if it is not in the cache #849

tatsuya6502 opened this issue Jan 26, 2025 · 3 comments · May be fixed by #850
Labels
bug Something isn't working
Milestone
v0.14

Comments

@tatsuya6502
Copy link

tatsuya6502 commented Jan 26, 2025 •
edited
Loading

Hi.

In the mokabench result moka-rs/mokabench#20 (comment), foyer had lower hit ratio than moka in the same workload.

Cache Size Num Clients Hit Ratio (Higher is better)
Foyer in-memory 100,000 1 9.438
Moka Async 100,000 1 10.439
Foyer in-memory 400,000 1 28.592
Moka Async 400,000 1 42.470
Foyer in-memory 800,000 1 64.728
Moka Async 800,000 1 70.331

I think foyer used the W-TinyLFU policy, and moka used the TinyLFU policy for the benchmark. I believe they should have similar hit ratios for this workload (ARC S3). For the expected results, see this comment moka-rs/moka#446 (comment) having the results from Caffeine Simulator.

I briefly reviewed the foyer code, and found potential errors in the W-TinyLFU policy implementation.

1. The W-TinyLFU policy does not seem to update the frequency of the key if it is not in the cache.

For a cache read, foyer should update the frequency of the key no matter if it is in the cache or not.

foyer/foyer-memory/src/eviction/lfu.rs

Lines 368 to 370 in 92522d3

Op::mutable(|this: &mut Self, record| {
// Update frequency by access.
this.update_frequencies(record.hash());

The inferred type for record is &Arc<Record<Lfu<K, V>>>. This implies the closure will never be called if a Record does not exist in the cache.

2. The W-TinyLFU policy updates the frequency of the key when inserting it into the cache.

It should not update the frequency of the key for cache writes. At least, moka does not do that. The popularity of the key should only be determined when it is requested, not when it is created.

foyer/foyer-memory/src/eviction/lfu.rs

Lines 277 to 287 in 92522d3

fn push(&mut self, record: Arc<Record<Self>>) {
let state = unsafe { &mut *record.state().get() };
strict_assert!(!state.link.is_linked());
strict_assert!(!record.is_in_eviction());
strict_assert_eq!(state.queue, Queue::None);
record.set_in_eviction(true);
state.queue = Queue::Window;
self.increase_queue_weight(Queue::Window, record.weight());
self.update_frequencies(record.hash());

I think fixing 1. will improve the hit ratio of foyer in the mokabench result. So please check and fix it if necessary.
@tatsuya6502 tatsuya6502 mentioned this issue Jan 26, 2025
Open
@MrCroxx
Copy link
Collaborator

MrCroxx commented Jan 27, 2025

Hi, @tatsuya6502 . Thank you for letting me know.

Sorry for the late response. Recently it's the Chinese New Year holiday, I just returned from a vacation in Japan. (Maybe a bit off topic, but I know you are from Japan, the travel experience in Japan is really great.)

Let me try to apply the both suggestions. I'll be back here as soon as I make time for experiments.

Thank you very much for helping. That means a lot. 🥰

@MrCroxx MrCroxx added the bug Something isn't working label Jan 28, 2025
@MrCroxx MrCroxx added this to the v0.14 milestone Jan 28, 2025
@MrCroxx MrCroxx linked a pull request Jan 28, 2025 that will close this issue
Open
3 tasks
@tatsuya6502
Copy link
Author

Hi. Thanks for looking into this.

Sorry for the late response. Recently it's the Chinese New Year holiday, I just returned from a vacation in Japan. (Maybe a bit off topic, but I know you are from Japan, the travel experience in Japan is really great.)

No worries. I am from Tokyo, Japan but currently live in Shanghai with my wife and child, so I knew about the holiday. I am glad to hear that you enjoyed your vacation in Japan! (FYI, my Chinese is really bad because my family speaks Japanese, and I have worked only for American and Japanese companies. I should learn Chinese.)

@MrCroxx
Copy link
Collaborator

MrCroxx commented Jan 28, 2025

No worries. I am from Tokyo, Japan but currently live in Shanghai with my wife and child, so I knew about the holiday. I am glad to hear that you enjoyed your vacation in Japan! (FYI, my Chinese is really bad because my family speaks Japanese, and I have worked only for American and Japanese companies. I should learn Chinese.)

Don't worry at all! I only know Chinese and English as well. I have been to Japan twice, and I visited Tokyo last year. So, I hope to learn Japanese, but learning languages is very difficult for me. 🥲

I am usually in Beijing, and I occasionally go on business trips to Shanghai. I am looking forward to meeting you face-to-face if you don't mind next time.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working
Projects
foyer - Development Roadmap
Status: No status
Milestone
v0.14
Development

Successfully merging a pull request may close this issue.

fix: fix w-TinyLFU frequencies updates foyer-rs/foyer
2 participants
@tatsuya6502 @MrCroxx