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.
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 actually modified SpiceDB to inject a groupcache and Redis cache implementation. My PoC was trying to build a leopard index that could materialize tuples into Redis and then serve them via the dispatch API. I found it easier to just use the aforementioned cache interface and have it delegate to Redis.
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.
To be honest, I'm not sure I can recommend anything specific here.
1. How much data do you have and how many entries? If you have lots of data with very small records, you might need an off-heap based cache solution. The only ready-made implementation I know is Olric [1].
2. If you can use an on-heap cache, you might want to look at groupcache [2]. It's not "blazingly-fast", but it's battle-tested. Potential drawbacks include LRU eviction and lack of generics (meaning extra GC pressure from using `interface{}` for keys/values). It's also barely maintained, though you can find active forks on GitHub.
3. You could implement your own solution, though I doubt you'd want to go that route. Architecturally, segcache [3] looks interesting.
perhaps a NATS server colocated on each monolith server (or even embedded in your app, if it is written in golang, meaning that all communication is in-process) and use NATS KV?
Or if you just want it all to be in-memory, perhaps use some other non-distributed caching library and do the replication via NATS? Im sure there's lots of gotchas with something like that, but Marmot is an example of doing SQLite replication via NATS Jetstream
Hm, without more details on the use case and assuming no "round trip to a network" means everything is running on a single host I see a couple of options:
1) Shared memory - use a cache/key-value lib which allows you to swap the backend to some shmem implementation
2) File-system based - managing concurrent writes is the challenge here, maybe best to use something battle tested (sqlite was mentioned in a sibling)
3) Local sockets - not strictly "no network", but at least no inter-node communication. Start valkey/redis and talk to it via local socket?
Would be interested in the actual use case though, if the monolith is written in anything even slightly modern the language/runtime should give you primitives to parallelize over cores without worrying about something like this at all... And when it comes to horizontal scaling with multiple nodes there is no avoiding networking anyway.
Since you mention no network endpoint, I assume it's on a single server. If so, have you considered SQLite? Assuming your cache is not massive, the file is likely to end up in Filesystem cache so most of reads will come from memory and writes on modern SSD will be fine as well.
It's easy to understand system with well battle tested library and getting rid of cache is easy, delete the file.
EDIT: I will say for most use cases, the database cache is probably plenty. Don't add power until you really need it.
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…
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.
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.
What exactly do you mean by a "more specialized simple cache"? Just a map, mutex and LRU/LFU/ARC as eviction policies?
1. Even using sync.RWMutex and specialized policies won't really help you outperform a well-implemented BP-Wrapper in terms of latency/throughput.
2. I've never seen cases where W-TinyLFU loses more than 2-3% hit rate compared to simpler eviction policies. But most simple policies are vulnerable to attacks and can drop your hit rate by dozens of percentage points under workload variations. Even ignoring adversarial workloads, you'd still need to guess which specific policy gives you those extra few percentage points. I question the very premise of this approach.
3. When it comes to loading and refreshing, writing a correct implementation is non-trivial. After implementing it, I'm not sure the cache could still be called "simple". And at the very least, refreshing can reduce end-to-end latency by orders of magnitude.
You're correct on all points. I should not have used the word "outperform" and should have said a simple cache could be sufficient. If for example you know you have more than enough memory to cache all items you receive in 60 seconds and items strictly expire after 60 seconds, then a sync.RWMutex with optional lock striping is going to work just fine. You don't need to reach for one of these libraries in that case (and I have seen developers do that, and at that point the risk becomes misconfiguration/misuse of a complex library).
No, what do you want to verify? Any network calls make Redis significantly slower than an on-heap cache. I'd even argue these are tools for different purposes and don't compare well directly.
A common pattern, for example, is using on-heap caches together with off-heap caches/dedicated cache servers (like Redis) in L1/L2/Lx model. Here, the on-heap cache serves as the service's first line of defense, protecting slower, larger caches/databases from excessive load.
Yes, I assume that otter etc are vastly faster, but I suspect there's people who are not aware of that and, consequently, don't have such a layered approach. So, the idea was to show how much faster to further promote adoption of such tools.
And, to clarify, I was only thinking about localhost/Unix sockets to mostly eliminate network latency. Anything external to the server would obviously be incomparably slower.
I also suppose that it would be perhaps even more interesting/useful to compare the speed of these in-memory caches to Golang caches/kv stores that have disk persistence, and perhaps even also things like sqlite. Obviously the type of "disk" would matter significantly, with nvme being closer in perf (and probably sufficient for most applications).
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 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.
No, I haven't looked into it, but the combination of "lock-free" and "S3-FIFO" raises some red flags for me :)
I don't quite understand the specific rationale for replacing segmented LRU with S3-FIFO. If I remember correctly, even the original authors stated it doesn't provide significant benefits [1].
Regarding TinyUFO - are you using lock-free queues? Has the algorithmic complexity of TinyLFU changed? (In the base version, S3-FIFO is O(n)). How easy is it to add new features? With lock-free queues, even implementing a decent expiration policy becomes a major challenge.
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.
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 actually modified SpiceDB to inject a groupcache and Redis cache implementation. My PoC was trying to build a leopard index that could materialize tuples into Redis and then serve them via the dispatch API. I found it easier to just use the aforementioned cache interface and have it delegate to Redis.
We’re looking for a distributed Go cache.
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.
Any architecture/library recommendations?
To be honest, I'm not sure I can recommend anything specific here.
1. How much data do you have and how many entries? If you have lots of data with very small records, you might need an off-heap based cache solution. The only ready-made implementation I know is Olric [1].
2. If you can use an on-heap cache, you might want to look at groupcache [2]. It's not "blazingly-fast", but it's battle-tested. Potential drawbacks include LRU eviction and lack of generics (meaning extra GC pressure from using `interface{}` for keys/values). It's also barely maintained, though you can find active forks on GitHub.
3. You could implement your own solution, though I doubt you'd want to go that route. Architecturally, segcache [3] looks interesting.
[1]: https://github.com/olric-data/olric
[2]: https://github.com/golang/groupcache
[3]: https://www.usenix.org/conference/nsdi21/presentation/yang-j...
groupcache[https://github.com/golang/groupcache] has been around for some time now.
It's very limited in scope, but if it solves your needs it would be the way to go.
perhaps a NATS server colocated on each monolith server (or even embedded in your app, if it is written in golang, meaning that all communication is in-process) and use NATS KV?
Or if you just want it all to be in-memory, perhaps use some other non-distributed caching library and do the replication via NATS? Im sure there's lots of gotchas with something like that, but Marmot is an example of doing SQLite replication via NATS Jetstream
edit: actually, you can set jetstream/kv to be in-memory rather than file persistence. So, it could do the job of olric or rolling your own distributed kv via nats. https://docs.nats.io/nats-concepts/jetstream/streams#storage...
Hm, without more details on the use case and assuming no "round trip to a network" means everything is running on a single host I see a couple of options:
1) Shared memory - use a cache/key-value lib which allows you to swap the backend to some shmem implementation
2) File-system based - managing concurrent writes is the challenge here, maybe best to use something battle tested (sqlite was mentioned in a sibling)
3) Local sockets - not strictly "no network", but at least no inter-node communication. Start valkey/redis and talk to it via local socket?
Would be interested in the actual use case though, if the monolith is written in anything even slightly modern the language/runtime should give you primitives to parallelize over cores without worrying about something like this at all... And when it comes to horizontal scaling with multiple nodes there is no avoiding networking anyway.
Since you mention no network endpoint, I assume it's on a single server. If so, have you considered SQLite? Assuming your cache is not massive, the file is likely to end up in Filesystem cache so most of reads will come from memory and writes on modern SSD will be fine as well.
It's easy to understand system with well battle tested library and getting rid of cache is easy, delete the file.
EDIT: I will say for most use cases, the database cache is probably plenty. Don't add power until you really need it.
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…
It can't be shared without networking so I am not sure what you mean. Are you sure you need it to be shared?
LRU in memory backed by shared Elasticache.
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.
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.
What exactly do you mean by a "more specialized simple cache"? Just a map, mutex and LRU/LFU/ARC as eviction policies?
1. Even using sync.RWMutex and specialized policies won't really help you outperform a well-implemented BP-Wrapper in terms of latency/throughput.
2. I've never seen cases where W-TinyLFU loses more than 2-3% hit rate compared to simpler eviction policies. But most simple policies are vulnerable to attacks and can drop your hit rate by dozens of percentage points under workload variations. Even ignoring adversarial workloads, you'd still need to guess which specific policy gives you those extra few percentage points. I question the very premise of this approach.
3. When it comes to loading and refreshing, writing a correct implementation is non-trivial. After implementing it, I'm not sure the cache could still be called "simple". And at the very least, refreshing can reduce end-to-end latency by orders of magnitude.
You're correct on all points. I should not have used the word "outperform" and should have said a simple cache could be sufficient. If for example you know you have more than enough memory to cache all items you receive in 60 seconds and items strictly expire after 60 seconds, then a sync.RWMutex with optional lock striping is going to work just fine. You don't need to reach for one of these libraries in that case (and I have seen developers do that, and at that point the risk becomes misconfiguration/misuse of a complex library).
Yeah, I basically agree with that.
Thanks for the great writeup.
Out of curiosity, has any benchmarking been done to compare Otter etc vs things like (localhost/Unix socket) Redis?
No, what do you want to verify? Any network calls make Redis significantly slower than an on-heap cache. I'd even argue these are tools for different purposes and don't compare well directly.
A common pattern, for example, is using on-heap caches together with off-heap caches/dedicated cache servers (like Redis) in L1/L2/Lx model. Here, the on-heap cache serves as the service's first line of defense, protecting slower, larger caches/databases from excessive load.
Yes, I assume that otter etc are vastly faster, but I suspect there's people who are not aware of that and, consequently, don't have such a layered approach. So, the idea was to show how much faster to further promote adoption of such tools.
And, to clarify, I was only thinking about localhost/Unix sockets to mostly eliminate network latency. Anything external to the server would obviously be incomparably slower.
I also suppose that it would be perhaps even more interesting/useful to compare the speed of these in-memory caches to Golang caches/kv stores that have disk persistence, and perhaps even also things like sqlite. Obviously the type of "disk" would matter significantly, with nvme being closer in perf (and probably sufficient for most applications).
Anyway, it was just a thought.
Enjoyed the article.
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.
Author of ccache here.
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
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.
[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/
on S3-FIFO being problematic, have you looked into TinyUFO? (part of cloudflare/pingora)
No, I haven't looked into it, but the combination of "lock-free" and "S3-FIFO" raises some red flags for me :)
I don't quite understand the specific rationale for replacing segmented LRU with S3-FIFO. If I remember correctly, even the original authors stated it doesn't provide significant benefits [1].
Regarding TinyUFO - are you using lock-free queues? Has the algorithmic complexity of TinyLFU changed? (In the base version, S3-FIFO is O(n)). How easy is it to add new features? With lock-free queues, even implementing a decent expiration policy becomes a major challenge.
[1]: https://github.com/Yiling-J/theine/issues/21