Collaboration discuss: Rust Multi-level Cache Library

[xiaguan]

Hey there! 👋

As part of my work, I've been heavily involved in various cache-related projects and have read numerous papers on caching, including many issues surrounding Facebook's cacheLib. After much consideration, I feel it's time for me to contribute to the open-source community.

I've been planning to write a multi-level cache library in Rust for about a month now. However, just as I was about to start coding, someone informed me that this has already been done. Upon closer inspection, it appears that the existing project has made significant progress.

So, I was wondering if there's any possibility for collaboration between us. 🤝 I'd be more than happy to contribute my expertise and insights to help enhance the library further. Perhaps we could explore new features, optimize performance, or tackle any outstanding issues.

I'm open to any ideas you might have! Whether it's pair programming, code reviews, or simply discussing potential improvements, I'm all for it. 💡

Looking forward to hearing your thoughts on this! 😄

[MrCroxx]

Hi @xiaguan , nice to see you here. Thank you for noticing this tiny project. Any contribution to this project is welcomed and appreciated.

I've been planning to write a multi-level cache library in Rust for about a month now.

Could you please share more context about what situation would you like to use a multi-level cache in? Currently, Foyer mostly serves as an alternative to block cache implementation for a LSM-tree. The other features like serving as an efficient small KV cache are still lacking. We can discuss it more if you have the requirements,

Again, welcome to use, discuss, and contribute to Foyer. And enjoy your experience in the open-source community.

[xiaguan]

First ，I've recently been focusing on pingora's memory cache, which utilizes the new TinyUFO(tinylfu + s3fifo) algorithm and compares it with other caching solutions like moka, quick_cache, and lru. Based on this, I believe that our library should offer a wide range of algorithm choices to cater to different use cases and performance requirements.

When it comes to resource management, I suggest leveraging the get-size crate to accurately determine the memory footprint of cached objects. This will enable us to make informed decisions about cache capacity and eviction policies.

For flushing cache data to disk, I propose using the serde for serialization and deserialization. Taking inspiration from cacheLib's design, we can optimize the storage for SSDs based on object sizes. Additionally, we can draw insights from Facebook's Kangaroo paper for efficient disk-based caching.

Lastly, even though the journey may be somewhat long, my goal is to make this crate production-ready.

A simple chinese blog ,https://zhuanlan.zhihu.com/p/688774584

[1a1a11a]

the link is not valid

[MrCroxx]

I believe that our library should offer a wide range of algorithm choices to cater to different use cases and performance requirements.

Agreed that Foyer should give more pre-defined algorithms. However, for different use cases, introducing more algorithms is not enough. For example, small KV case requires the extra memory, and storage overhead must be as small as possible and the performance of IOPS should be optimized.

When it comes to resource management, I suggest leveraging the get-size crate to accurately determine the memory footprint of cached objects. This will enable us to make informed decisions about cache capacity and eviction policies.

That sounds like a good idea. However, I'm not familiar with this crate, which means I need time to investigate how the crate is implemented, how much overhead will it take and what is its performance. After that, we can decide weather to use the crate or get the memory statistics from the memory allocator.

For flushing cache data to disk, I propose using the serde for serialization and deserialization.

I understand that serde is a widely-used crate in the world or Rust and it is convenient for most normal applications. But for a cache system, it needs to deal with more complex encoding and decoding with customized formats and compressions. The most important thing is to optimize the performance (e.g. reduce buffer copy). Taking these into consideration, IMO, serde may not be a good choice. And I have not seen a storage system uses serde for underlying buffers. If there is some, please let me know and we can see if we can do it, too.

Additionally, we can draw insights from Facebook's Kangaroo paper for efficient disk-based caching.

That a good idea. Foyer currently lacks the ability to deal with tiny KV entries efficiently. I think we can try it.

[MrCroxx]

Again, thanks for your great opinions. As an alternative to block cache for LSM-Tree, Foyer is production-ready and is already been used by RisingWave. Hope we can make Foyer move forward!

[MrCroxx]

If you want to get your hands dirty ASAP, you could try to add S3Fifo eviction container for foyer-memory. foyer-memory uses intrusive data structures to deal with the multi-container problem in Rust and shards cache with mutex to handle concurrent requests, which might not fully compatible with the original implementation of S3Fifo. But we can focus the eviction algorithm part to see if it is optimized for some workload. I'll open an issue tomorrow and you can try it if you like.

[xiaguan]

If you want to get your hands dirty ASAP, you could try to add S3Fifo eviction container for foyer-memory. foyer-memory uses intrusive data structures to deal with the multi-container problem in Rust and shards cache with mutex to handle concurrent requests, which might not fully compatible with the original implementation of S3Fifo. But we can focus the eviction algorithm part to see if it is optimized for some workload. I'll open an issue tomorrow and you can try it if you like.

I could try this , since pingora has already impl a high performance one.