16 ms·
Otter, Fastest Go in-memory cache based on S3-FIFO algorithm
- tedunangst 3y agoI was curious what function was used for hashing (how do you write a generic hash function in go?) and it's pretty disgusting. https://github.com/dolthub/maphash/blob/main/runtime.go https://github.com/dolthub/maphash/blob/main/runtime.go
- lukevp 3y agoCould you provide more context on what’s disgusting? I’m not a go programmer but this looks like it’s just a wrapper around a library called ‘maphash’ and doesn’t do any of the hashing here? This is more of a service wrapper around that lib so that it can have a consistent seed value etc.?
- brabel 3y agoI suppose the use of unsafe pointers liberally is disgusting to some.
- sidlls 3y agoI wouldn't call it disgusting. It's just typical unsafe go code. The named return parameter in `getRuntimeHasher` is irritating, as all such parameters in go code are. If you're going to return values, do so explicitly in the return statement. In go code, seeing `return` at the end of a function does not mean that the function doesn't return any values, and that can lead to harder-to-read code.
- insanitybit 3y ago> It's just typical unsafe go code. But... just to hash something?
- sidlls 3y agoGo has a lot of lower level internal implementations of things that unsafe code like this serves as a thin shim for. It’s an almost zero-cost abstraction to use such a builtin. I’m not saying it’s good: it just is what it is. It’s silly: but so is most of go. I’ve worked with this language for several years now: I don’t like it at all. It presents a facade of simplicity, but has all sorts of hidden issues that affect performance and behavior in surprising ways.
- insanitybit 3y agoI think we're all saying the same thing then.
- tedunangst 3y agoConstructing a map (an opaque type) just so you cast it to a carefully duplicated struct so you can steal the function pointer is kinda nutso. Did you look at the linked code in maphash?
- oooyay 3y agoDisgusting is a word, but I'm guessing you'd say the same about most unsupported feature code (aka unsafe). You can make code like this reliable in the ways it needs to be while still being "unsafe". That's kind of table stakes when you start dabbling in unsupported things.
- tedunangst 3y agoAnd what does this code do to make itself reliable in the event the go authors change the internal structure of a map?
- rad_gruchalski 3y agoNothing. That’s the trade off. What is not clear about “unsafe” in that context?
- tedunangst 3y agoThe part about making it reliable in the ways it needs to be.
- oooyay 3y agoIt's pinned to a Go version and these: https://github.com/dolthub/maphash/blob/main/hasher_test.go https://github.com/dolthub/maphash/blob/main/hasher_test.go
- tedunangst 3y agoThat's annoying, but at least reliable. Thank you.
- falsandtru 3y agohttps://news.ycombinator.com/item?id=36434358 https://news.ycombinator.com/item?id=36434358 Note that S3-FIFO has no loop resistance. Nevertheless, the result that this library is functioning in a loop indicates that some important changes have been made. Also, the result that Ristretto, which has loop resistance, is not functioning in a loop is clearly an anomaly and likely not being measured correctly. Ristretto's benchmark results on S3, DS1, and OLTP differ markedly from the official ones (https://github.com/dgraph-io/ristretto https://github.com/dgraph-io/ristretto). Otter's benchmark results are quite suspicious.
- NovaX 3y agoI think you may be right. The library author said he made many changes because implementing the eviction policy following the paper's design was pretty awful. > First, I tried to implement cache on hash table and lock free queues, as the authors wrote. I was annoyed, s3-fifo was indeed many times faster than lru cache implemented on hash table with global mutex, but still lost to ristretto and theine, which use bp-wrapper techniques. The profiler also showed that it was the eviction policy that was spending the bulk of the time. And I was only able to beat ristretto and theine after rewriting the implementation using bp-wrapper. > In summary, I completely disagree about the scalability advantage of S3-FIFO over the other policies > Though to be honest, what was causing the hit ratio to go down in DS1 I still don't understand https://github.com/Yiling-J/theine-go/issues/29#issuecomment-1841356725 https://github.com/Yiling-J/theine-go/issues/29#issuecomment...
- medler 3y agoCould you share some pointers where I can read more on “loop resistance?” Does that just refer to whether it does well on a looping access pattern?
- senderista 3y agoThe usual phrase is "scan resistance", which is especially important for databases. A pure LRU policy does poorly on scans; LFU does better but performs worse than LRU on other workloads. The original ARC paper[0] has a good discussion of the tradeoffs. [0] https://www.usenix.org/legacy/events/fast03/tech/full_papers/megiddo/megiddo.pdf https://www.usenix.org/legacy/events/fast03/tech/full_papers...
- almost_usual 3y agoPretty much 2Q without the LRU.
- jeffbee 3y agoI never really understood why anyone wants to maintain LRU properties in caches. It doesn't make sense today and it didn't make sense decades ago, either. You do need some rational basis for eviction, but ranking your hot set on every access was always just weird. I am glad this is being fixed in the literature lately.
- 1a1a11a 3y agoThere are some difference, the most notable one is that 2Q evicts all objects from the small queue (does not move to the large LRU).
- tomalaci 3y agoFor a long time Go did not expose their super efficient internal map hashing algorithm that, if possible, would use AES instructions from the processor to hash even faster. That is, they did not expose it as an official API. People usually did some "unsafe" usage to link to that internal hashing function for their own super-fast map implementations. That was changed some time ago. They released official maphash package: https://pkg.go.dev/hash/maphash https://pkg.go.dev/hash/maphash Otter author could probably look into replacing their 3rd party hashing dependency (https://github.com/dolthub/maphash https://github.com/dolthub/maphash) with the official one and knock off an unneeded dependency :)
- tedunangst 3y agohash/maphash isn't a very good replacement if you're trying to hash simple structs, since they still require conversion to byte slice by some means.
- michalmatczuk 3y agoThe issue is Go stdlib does not have parallel hash map. We have https://github.com/puzpuzpuz/xsync#map https://github.com/puzpuzpuz/xsync#map a different Cache line hashmap impl.
- 1f60c 3y agoWhat about https://pkg.go.dev/sync#Map https://pkg.go.dev/sync#Map?
- jasonwatkinspdx 3y agoThe api doc there says why but not fully in depth: > The Map type is optimized for two common use cases: (1) when the entry for a given key is only ever written once but read many times, as in caches that only grow, or (2) when multiple goroutines read, write, and overwrite entries for disjoint sets of keys. In these two cases, use of a Map may significantly reduce lock contention compared to a Go map paired with a separate Mutex or RWMutex. sync#Map works by having two maps internally, one which receives writes and then periodically copies its values to the larger map and clears itself. This works on the two workloads mentioned above. It falls rather flat under write contention. This is by design. syncMap is really intended for maps that are mostly read only.
- hn_throwaway_99 3y agoI didn't know what the S3-FIFO algorithm was. https://s3fifo.com/ https://s3fifo.com/ gives a great overview with some good visuals.
- 1f60c 3y agoThis entire time, I thought it had something to do with Amazon S3.
- mvcalder 3y agoI wrote up this analysis of cache one-hits after reading the FIFO is all you need paper. https://www.polyscale.ai/blog/one-hit-expectation https://www.polyscale.ai/blog/one-hit-expectation
- coxley 3y agoSorry if I missed it, but does Otter do anything special to limit GC-impact when caching lots of references? That's the main selling point for bigcache and freecache.
- maypok86 3y agoNo, and it's not planned (otter tries to avoid additional pressure on gc if possible, but that's not always possible). And I'm extremely frustrated that I had to include bigcache and fastcache in these benchmarks, since many people don't know the differences at all and just focus on performance and other metrics. Especially since bigcache and fastcache will only have an advantage when storing a huge number of items (well over 10 million). So I'll probably just add a P.S. in the README about it.
- coxley 3y agoYeah, they're fundamentally solving different problems. I was confused to see it benchmarking against them in the first place. The number of items isn't the best metric alone, making it harder to demonstrate in a benchmark. I've reaped benefits from bigcache with ~600k-900k items — but there's a lot of eviction, each item is a pointer and can have a bunch of nested references itself. (protobufs)
- neonsunset 3y agoYou may want to vet this as a third-party dependency due to supply chain attack risks.
- mparnisari 3y agoHow does it compare to https://github.com/scalalang2/golang-fifo https://github.com/scalalang2/golang-fifo?
- scalalang 3y agoHi, I made this repo. I'm here to drop my opinions as below. [1] - golang-fifo provides also SIEVE algorithm which is more effieicnt than S3-FIFO under web cache workloads(follows zipf's distribution) [2] - I added otter to my cache benchmark. It shows less efficiency than mine. I'm not sure why this happens. See results here: https://github.com/scalalang2/go-cache-benchmark https://github.com/scalalang2/go-cache-benchmark [3] - If the behavior of the two algorithms is the same, they should produce similar results. but they shows different results. - Otter is faster with more concurrency, but misses more stuff (shows less hit/rate).
- maypok86 3y agoIn fact, to say that sieve is better is fundamentally wrong. 1. You only test the hit ratio on a synthetic zipf distribution and claim an advantage without saying a word about the problems (which there are). 2. Checking implementation speed looks very questionable on such benchmarks, because you spend a huge amount of CPU time on synchronization and item generation. 3. Your implementation has at least three problems that otter doesn't: worst case O(n) time complexity of the eviction policy, disgusting scalability, also golang-fifo simply doesn't have as many features as otter, and adding each of them will only slow golang-fifo down even more. 4. Yes, when increasing contention otter sacrifices 1-2 percent (I'll have to see if I can reduce this loss) hit ratio to maintain response speed, but that's what caffeine, ristretto and other famous cache libraries do, because in this case it's more important to maintain scalability than to keep hundreds of goroutines waiting for a mutex to unlock. 5- This structure looks highly questionable to support ghost queue: https://github.com/scalalang2/golang-fifo/blob/main/s3fifo/bucket_table.go#L5 https://github.com/scalalang2/golang-fifo/blob/main/s3fifo/b.... You are wasting a very large number of bytes just to maintain an item footprint.
- 3y ago
- hknmtt 3y agoI never understood this cost nonsense. TTL is the only thing that makes any sense to me. And implementation is trivial. All these caches are just a map underneath anyway, pointing to some data somewhere in memory. That's about it. Not much else to it.
- klabb3 3y agoI don’t have any practical experience but if I were to guess it’s relatively easy for a developer to estimate a cost of retrieval in terms of CPU/time or something, which can let the cache make smarter predictions about eviction depending on access patterns. Typically, a longer chained primary db call could be higher cost than say a quick lookup in a local kv store. That said, perhaps those should simply be different caches instead. TTL doesn’t say anything about eviction among objects that are still live, no? For that you need an eviction policy.
- hknmtt 3y ago> TTL doesn’t say anything about eviction among objects that are still live, no? TTL IS eviction policy. You just store a timestamp along the value. When you access it, you check the timestamp and if it is stale, you delete it and return not found error(or whatever not found should return). And you have a simple bg worker that scans the cache periodically and deletes these stale entries to free up the memory. This is the basis for all caches. You can add cost on top of this as yet another eviction policy but that only adds another worker to scan the cache for items to purge and you have to store the cost along with the entry so you are increasing the each entry by at least 4 bytes, if we're talking uint32. Not to mention that for this eviction policy, you need sorted cache because you need to know where the cut off for cost is. Walking the entire cache to purge expired TTL entries is one thing, but keeping ordered cache is a whole another thing.
- klabb3 3y agoWhat I mean is that when cache is full you need an eviction policy, like LRU for instance. If everything fits in memory there’s not much to discuss, yes then TTL with periodic scan is reasonable, yes.
- jhoechtl 3y agoI always thought Go as a GC'ed language is unsuitable as a caching instrument?