Caffeine: Consider adding segcache traces and simulator

[vlsi]

See https://github.com/thesys-lab/segcache, https://twitter.com/danluu/status/1381687511362138113

/cc @1a1a11a

[1a1a11a]

Thank you! It is exciting to know that people are interested in our work!

I will leave this request to Ben. My feeling is that Segcache is more of a holistic redesign of cache storage instead of a standalone eviction algorithm, so it is not trivial to build a simulator around it. For example, one problem Segcache addresses is memory fragmentation, which cannot be accurately captured in simulators. Interesting enough, Segcache uses a frequency per byte metric in eviction, which is similar to tiny-LFU.

In case people are interested, the traces used in the work is the a subset (the most important clusters) of what we have previously released https://github.com/twitter/cache-trace.

[vlsi]

Thanks for the clarification.
My initial thought was "there are never enough traces", however, then you have 2.8 TB in compressed form, 14 TB uncompressed
Holy cow! 😜

[1a1a11a]

These traces are really valuable for the academia, I have to acknowledge Yao @thinkingfish, who has put in great efforts to release them. As some others have mentioned, even though we have released traces from 54 clusters, there are still some cache usages that are not covered in social network platforms. It would be great if other companies willing to help out on this.

[ben-manes]

Thanks @vlsi and @1a1a11a. I found the paper back in March and very much enjoyed it. It is a pragmatic paper, rather than one on theory, and focuses on the design tradeoffs that best fit Twitter's need. That means exploiting constraints for a simpler design, the cost optimizations needed for Twitter's scale, and implementation techniques. That helps inspire future work, but isn't something we can simulate nor add into our benchmark suite.

We have support for the Twitter traces, which came from a really nice analysis paper. The simulator does not yet support TTL to expire entries, as that was orthogonal to our size analysis. That could certainly be added if someone wanted to research that topic. The paper confirmed all of my knowledge on expiration and social network workloads, which was known by word of mouth rather than a rigorous than analysis.

I don't think there is anything actionable. The main thing is to share our ideas, e.g. that we learn from @1a1a11a and that he knows about how we solved concurrency, expiration, size eviction, and adapting to workloads. There are very different but related concerns of client vs remote caches, so learning from each other can also be a big help to see features migrate (e.g. should a remote cache offer read through?).

We currently support 15 public trace repositories for workload analysis. That has been really helpful to analyze size-based policies. There is a gap in other workloads that might be beneficial for future researchers, like latency-aware policies. Since this is an engineering project, I do try to make whatever we built useful for researchers who can leverage our work for their algorithm ideas and hopefully speed up their analysis loop.

[ben-manes]

Closing but happy to continue discussions online or off.

Just to make sure you're fully aware of our algorithmic choices @1a1a11a, they are summarized in these articles (part 1, part 2, slides). There is a Golang inspired cache that borrowed & confirmed some of our design for a graph db (part 1, part 2). We currently have 5.3M monthly downloads and there have been a few industry experience success stories (atlassian, expedia, linkedin, allegro, amplitude) which offers some additional validation that our approach works in practice in a variety of different workload scenarios. That is mostly to say that while we can't quantify results the like Segcache at Twitter or Cachelib at Facebook can, we have a enough external confirmation that I believe our choices work well in practice. However, the algorithms were very much chosen for our use-case of a Java client-side cache, so other environment may favor different design decisions based on their unique constraints and their platform's strengths / weaknesses.

[1a1a11a]

Hi Ben, this is a great resources to learn about Caffeine and how caching is used! They are really nice! I have not looked closely at Caffeine, but will do soon. Looking forward talking to you!