[HN Gopher] Otter, Fastest Go in-memory cache based on S3-FIFO a...
___________________________________________________________________
Otter, Fastest Go in-memory cache based on S3-FIFO algorithm
Author : rickette
Score : 122 points
Date : 2023-12-23 15:49 UTC (7 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| tedunangst wrote:
| I 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
| lukevp wrote:
| Could 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 wrote:
| I suppose the use of unsafe pointers liberally is disgusting
| to some.
| sidlls wrote:
| I 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 wrote:
| > It's just typical unsafe go code.
|
| But... just to hash something?
| sidlls wrote:
| Go 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 wrote:
| I think we're all saying the same thing then.
| tedunangst wrote:
| Constructing 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 wrote:
| Disgusting 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 wrote:
| And what does this code do to make itself reliable in the
| event the go authors change the internal structure of a map?
| rad_gruchalski wrote:
| Nothing. That's the trade off. What is not clear about
| "unsafe" in that context?
| tedunangst wrote:
| The part about making it reliable in the ways it needs to
| be.
| oooyay wrote:
| It's pinned to a Go version and these: https://github.com
| /dolthub/maphash/blob/main/hasher_test.go
| falsandtru wrote:
| 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). Otter's benchmark
| results are quite suspicious.
| NovaX wrote:
| I 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...
| medler wrote:
| Could 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 wrote:
| The 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_pap
| ers...
| falsandtru wrote:
| Scan resistance and loop resistance are completely
| different. They are also distinguished in the papers. Note
| that ARC has scan resistance but no loop resistance.
| medler wrote:
| None of the papers linked above or linked in the GitHub
| repo mention "loop resistance."
| senderista wrote:
| Not _completely_ different; they 're both sequential
| access patterns and equivalent whenever the loop size
| exceeds cache size.
| falsandtru wrote:
| Not equivalent completely. Scan is a one-time access, so
| it never hits in scanning. Loop is multi-time accesses,
| so it can get many hits in looping if it has loop
| resistance. No hits on scan resistance in looping. Over.
| falsandtru wrote:
| Sometimes referred to as tolerance. There is no established
| terminology, so the only way to find out is to use scan or
| loop as keywords.
| someplaceguy wrote:
| So why did you say S3-FIFO has no loop resistance (or loop
| tolerance)?
| falsandtru wrote:
| There is an established benchmark for testing loop
| resistance (GLI, Loop). S3-FIFO has not passed this test.
| And I have already confirmed that S3-FIFO does not pass
| the test.
| someplaceguy wrote:
| The design of S3-FIFO seems to imply it should handle all
| loops less than 90% of the cache size pretty well,
| perhaps even up to 100%.
|
| Did you figure out why it did not pass the test? Was
| there a bug in the implementation, perhaps?
|
| Also, where can I find the benchmark you speak of? My web
| search did not find anything.
| falsandtru wrote:
| My implementation is reviewed and linked from the
| official S3-FIFO page.
|
| https://s3fifo.com
|
| A benchmark is as follows.
|
| https://github.com/ben-manes/caffeine/wiki/Efficiency
|
| I can't deal with you any longer. Over.
| NovaX wrote:
| /u/someplaceguy,
|
| Those LIRS traces, along with many others, available at
| this page [1]. I did a cursory review using their traces
| using Caffeine's and the author's simulators to avoid
| bias or a mistaken implementation. In their target
| workloads Caffeine was on par or better [2]. I have not
| seen anything novel in this or their previous works and
| find their claims to be easily disproven, so I have not
| implement this policy in Caffeine simulator yet.
|
| [1]: https://github.com/ben-manes/caffeine/wiki/Simulator
|
| [2]:
| https://github.com/1a1a11a/libCacheSim/discussions/20
| someplaceguy wrote:
| S3-FIFO has scan resistance. What do you mean by "loop
| resistance" and why do you say S3-FIFO doesn't have it?
| almost_usual wrote:
| Pretty much 2Q without the LRU.
| jeffbee wrote:
| I 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.
| tomalaci wrote:
| For 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
|
| Otter author could probably look into replacing their 3rd party
| hashing dependency (https://github.com/dolthub/maphash) with the
| official one and knock off an unneeded dependency :)
| tedunangst wrote:
| hash/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.
| Thaxll wrote:
| Hash functions all work on bytes sequence or string, hashing
| a struct/class/object is a different use case.
| michalmatczuk wrote:
| The issue is Go stdlib does not have parallel hash map.
|
| We have https://github.com/puzpuzpuz/xsync#map a different Cache
| line hashmap impl.
| 1f60c wrote:
| What about https://pkg.go.dev/sync#Map?
| mvcalder wrote:
| I 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
| hn_throwaway_99 wrote:
| I didn't know what the S3-FIFO algorithm was. https://s3fifo.com/
| gives a great overview with some good visuals.
| 1f60c wrote:
| This entire time, I thought it had something to do with Amazon
| S3.
| coxley wrote:
| Sorry 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.
| neonsunset wrote:
| You may want to vet this as a third-party dependency due to
| supply chain attack risks.
___________________________________________________________________
(page generated 2023-12-23 23:00 UTC)