maypok86
Joined 2 years ago
Joined 2 years ago
1. I don't really see how the API is simpler. ccache has tons of methods like `GetsPerPromote`, `PercentToPrune`, `Buckets`, `PromoteBuffer`, `DeleteBuffer`. How is a user supposed to know what values to set here? Honestly, even with all the time I've spent digging through cache implementations, I don't fully understand what should be configured there. Otter simply doesn't need any of these - you just specify the maximum size and the cache works.
2. Numerous methods like `tracking` and `promote` are again unnecessary for otter. Just `getIfPresent` and `set`/`setIfAbsent` and you're good to go.
3. The lack of loading and refreshing features seems like a significant drawback, as they typically provide major benefits for slow data sources.
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.
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/
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.
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. 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...
Otter v2 has been almost completely reworked since its first release to provide a richer API and new features while maintaining high performance.
Key Improvements:
- Completely rethought API for greater flexibility.
- Added the ability to create a cache with any combination of features.
- Added loading and refreshing features.
- Added entry pinning.
- Replaced eviction policy with adaptive W-TinyLFU, enabling Otter to achieve one of the highest hit rates across all workloads.
- Added HashDoS protection against potential attacks.
- The task scheduling mechanism has been completely reworked, allowing users to manage it themselves when needed.
- Added more efficient write buffer.
- Added auto-configurable lossy read buffer.
- Optimized hash table.
- Test coverage increased to 97%
I hope this library will prove useful to some of you! :)
2. It's a bit non-obvious here. Caffeine does not lose a single insert, update, delete operation and moreover, keeps track of their correct execution with fantastic scrupulosity. Also the loss of some reads is inherent in many eviction policies. And caffeine's lossy buffers also have a great ability: the number of these buffers is automatically adjusted at runtime based on contention, which minimizes losses.
3. I specifically mentioned here that it's not the same, but it is possible to design a load that will force as many xadd operations as possible and as few load operations as possible. But in principle you can ignore this point, as it is rather artificial.
4. Here I rather mean that all features should live in the lock-free model or somehow be separately integrated into the architecture (which only complicates things). Plus, for example, a person wants to modify the eviction policy a bit, for example, by adding the lfu part to it and then it's not clear how to do it.
1. Yes, S3-FIFO can be implemented using lock-free queues, but the problem is that each write to a filled cache using this design will cause a large number of additional atomic operations not friendly to the processor's cache, while bp-wrapper on the contrary amortizes this load. And reading with frequency update on hot entries can have a bad effect on performance. In many ways this is exactly what the last posts in my discussion with Ben are about (not really about this, but the current problem with otter read speed is caused by a similar problem). https://github.com/Yiling-J/theine-go/issues/29#issuecomment...
2. But the main problem for me is not even that. Lock-free queues work fine as long as you only need to support Get and Set operations, but as soon as you want to add features to your cache, the complexity of the implementation starts to increase, and some features are very hard to add to such a structure. Also, improving the eviction policy is under a big question mark, because not only do you have to think about how to improve the eviction policy, but also how to avoid locks while doing so or how not to slow down the implementation with your improvements. BP-Wrapper has no such problems at all, allows you to use any eviction policy and focus on improving different parts of your cache independently of each other.
And about lock-free queues I don't agree, what they do with the implementation can be seen on the example of theine Reads 100% graph in the otter repository, if it wasn't there, it would be equal in speed to ristretto. And the BP-Wrapper technique actually has a huge engineering plus: it allows you to focus on optimizing different components of the system individually and easily make changes to the eviction policy that lock-free queues can't give to the developer.
`Weigher` is also likely clear from its doc. Many developers are at least familiar with this concept from other languages or libraries like ristretto and ttlcache.
`GetEntryQuietly` retrieves the cache entry for a key without any side effects - it doesn't update statistics or influence eviction policies (unlike `GetEntry`). I genuinely think this is reasonably clear.
I'm completely baffled why `SetRefreshableAfter` made this list. If you understand refreshing, it's obviously just `SetTTL` but for the refresh policy.
Honestly, I mostly disagree about the options being unclear. I suspect `Executor` is the only one that might confuse users after reading the docs, and it's mainly for testing anyway. My core complaint is the first point in my comment - tuning the cache requires deep understanding of its internals. Take ristretto's `NumCounters` parameter: users don't understand it and often just set it to `maxCost * 10` like the README example. But this completely breaks when using custom per-entry costs (like byte sizes).
But as I mentioned when reviewing sturdyc, it probably comes down to personal preference.