We don’t want to round trip to a network endpoint in the ideal path, but we run multiple instances of our monolith and we want a shared cache tier for efficiency.
Could you add a bit more to the “distributed cache” concept without a “network endpoint”? Would this mean running multiple processes of the same binary with a shared memory cache on a single system?
If so, that’s not how I’d normally think of a distributed cache. When I think of a distributed cache, I’m thinking of multiple instances, likely (but not necessarily) running on multiple nodes. So, I’m having a bit of a disconnect…
Much of the complexity of caching comes from trying to work well all workloads. If the workload is known, I think in many cases a specialized simpler cache can outperform some of these libraries.
Just wanted to say thanks for such a good write-up and the great work on Otter over the years. We've used Ristretto since the beginning of building SpiceDB and have been watching a lot of the progress in this space over time. We've carved out an interface for our cache usage a while back so that we could experiment with Theine, but it just hasn't been a priority. Some of these new features are exciting enough that I could justify an evaluation for Otter v2.
Another major for on-heap caches that wasn't mentioned their portability: for us that matters because they can compile to WebAssembly.
I benchmarked ccache for throughput [1], memory consumption [2], and hit rate [3]. For hit rate simulations, I used golang-lru's LRU implementation, though I doubt a correct LRU implementation would show meaningful hit rate differences.
Note that otter's simulator results were repeatedly compared against both W-TinyLFU's (Caffeine) and S3-FIFO's (Libcachesim) simulators, showing nearly identical results with differences within hundredths of a percent.
I've barely touched Go in over a decade, but if I did, I'd probably still use ccache if I didn't need cutting edge (because I think the API is simple), but not if I needed something at huge scale.
When I wrote ccache, there were two specific features that we wanted that weren't readily available:
- Javing both a key and a subkey, so that you can delete either by key or key+subkey (what ccache calls LayeredCache).
- Having items cached that other parts of the system also have a long-living reference to, so there's not much point in evicting them (what ccache calls Tracking and is just a separate ARC mechanism that overrides the eviction logic).
It also supports caching based on arbitrary item size (rather than just a count of items), but I don't remember if that was common back then.
I've always thought that this, and a few other smaller features, make it a little bloated. Each cached item carries a lot of information (1). I'm surprised that, in the linked benchmark, the memory usage isn't embarrassing.
I'm not sure that having a singl goroutine do a lot of the heavy-lifting, to minimize locks, is a great idea. It has a lot of drawbacks, and if I was to start over again, I'd really want to benchmark it to see if it's worth it (I suspect that, under heavy write loads, it might perform worse).
The one feature that I do like, that I think most LRU's should implement, is to have a [configurable] # of gets before an item is promoted. This not only reduces the need for locking, it also adds some frequency bias to evictions.
Fun Fact: My goto interview question was to implement a cache. It was always rewarding to see people make the leap from using a single data structure (a dictionary) to using two (dictionary + linked list) to achieve a goal. It's not a way most of us are trained to think of data structures, which I think is a shame.
I'm the author of Theine (both Go and Python). I actually started with the Python version, using Ristretto as a reference implementation, including its hit ratio benchmarks. Naturally, I had to run Ristretto's benchmark first to ensure it was working correctly, which is how I discovered the issue in the first place. After completing the Python version, I moved on to develop the Go version of Theine, which focus on better hit ratio than Ristretto.
Recently, I refactored both the Go and Python versions to adopt Caffeine’s adaptive algorithm for improved hit ratio performance. But now that Otter v2 has switched to adaptive W-TinyLFU approach and more closely aligned with Caffeine’s implementation, I’m considering focusing more on the Python version.
This feels like a good time to do so: the Python community is actively working toward free-threading, and once the GIL is no longer a bottleneck, larger machines and multi-threads will become more viable. Then a high-performance, free-threading compatible caching libraries in Python will be important.
I'm glad I saw this article. I've been wanting a library like Guava/Caffeine to consider Go to feel more like a real language, but I wasn't aware of the last few years of developments. I am interested in this and I hope my team (and adjacent Go teams) will be too.
I've been using Otter for ~2(?) years, and it's a good time. This post made me realize we should upgrade to v2, as we've had a craving for async refresh.
Thanks to maypok86 for their dedication. The long comment threads on Ristretto issues are endlessly informative and entertaining. ;)
13 comments
[ 5.4 ms ] story [ 38.3 ms ] threadWe don’t want to round trip to a network endpoint in the ideal path, but we run multiple instances of our monolith and we want a shared cache tier for efficiency.
Any architecture/library recommendations?
If so, that’s not how I’d normally think of a distributed cache. When I think of a distributed cache, I’m thinking of multiple instances, likely (but not necessarily) running on multiple nodes. So, I’m having a bit of a disconnect…
Another major for on-heap caches that wasn't mentioned their portability: for us that matters because they can compile to WebAssembly.
How do you compare to ccache as this is my go to cache library. Well the need is mostly on high traffic endpoints, so LRU it's.
Note that otter's simulator results were repeatedly compared against both W-TinyLFU's (Caffeine) and S3-FIFO's (Libcachesim) simulators, showing nearly identical results with differences within hundredths of a percent.
[1]: https://maypok86.github.io/otter/performance/throughput/
[2]: https://maypok86.github.io/otter/performance/memory-consumpt...
[3]: https://maypok86.github.io/otter/performance/hit-ratio/
I've barely touched Go in over a decade, but if I did, I'd probably still use ccache if I didn't need cutting edge (because I think the API is simple), but not if I needed something at huge scale.
When I wrote ccache, there were two specific features that we wanted that weren't readily available:
- Javing both a key and a subkey, so that you can delete either by key or key+subkey (what ccache calls LayeredCache).
- Having items cached that other parts of the system also have a long-living reference to, so there's not much point in evicting them (what ccache calls Tracking and is just a separate ARC mechanism that overrides the eviction logic).
It also supports caching based on arbitrary item size (rather than just a count of items), but I don't remember if that was common back then.
I've always thought that this, and a few other smaller features, make it a little bloated. Each cached item carries a lot of information (1). I'm surprised that, in the linked benchmark, the memory usage isn't embarrassing.
I'm not sure that having a singl goroutine do a lot of the heavy-lifting, to minimize locks, is a great idea. It has a lot of drawbacks, and if I was to start over again, I'd really want to benchmark it to see if it's worth it (I suspect that, under heavy write loads, it might perform worse).
The one feature that I do like, that I think most LRU's should implement, is to have a [configurable] # of gets before an item is promoted. This not only reduces the need for locking, it also adds some frequency bias to evictions.
Fun Fact: My goto interview question was to implement a cache. It was always rewarding to see people make the leap from using a single data structure (a dictionary) to using two (dictionary + linked list) to achieve a goal. It's not a way most of us are trained to think of data structures, which I think is a shame.
(1) https://github.com/karlseguin/ccache/blob/master/item.go#L22
Recently, I refactored both the Go and Python versions to adopt Caffeine’s adaptive algorithm for improved hit ratio performance. But now that Otter v2 has switched to adaptive W-TinyLFU approach and more closely aligned with Caffeine’s implementation, I’m considering focusing more on the Python version.
This feels like a good time to do so: the Python community is actively working toward free-threading, and once the GIL is no longer a bottleneck, larger machines and multi-threads will become more viable. Then a high-performance, free-threading compatible caching libraries in Python will be important.
Out of curiosity, has any benchmarking been done to compare Otter etc vs things like (localhost/Unix socket) Redis?
Thanks to maypok86 for their dedication. The long comment threads on Ristretto issues are endlessly informative and entertaining. ;)