9 ms·
Efficient cache for gigabytes of data written in Go
- reinhardt1053 7y agoBlog post that describes the implementation: https://allegro.tech/2016/03/writing-fast-cache-service-in-go.html https://allegro.tech/2016/03/writing-fast-cache-service-in-g...
- shepardrtc 7y agoThis is very cool. But why didn't they just go with Redis? Their blog stated that this requirement: "be very fast even with millions of entries" wasn't met by Redis, but I have a very hard time believing that.
- Eikon 7y agoThere’s no network latency involved as it’s an in memory, embedded database. Also, max throughput here is ultimately a sum of how fast the memory allocator is and memory bandwidth which, even with a poor implementation would be orders of magnitude more than what you can do with standard NICs and Linux kernel networking stack. Moreover, as a consequence, far less context switching is involved.
- Znafon 7y agoI thought it was possible to embed Redis.
- Eikon 7y agoPossible don’t mean ubiquitous. You get no support and plenty headaches when you start to do that sort of weird, unsupported things with a product.
- shepardrtc 7y agoAhh I missed the part about the network. That makes much more sense, then.
- Exuma 7y agoCan you explain why redis require extra network time?
- shepardrtc 7y agoIts just time to transfer across the network, whereas this project is in-memory with the program that's calling it.
- stevekemp 7y agoThey do discount networked solutions, but then talk about making HTTP-calls with JSON payloads. Or was that just for testing?
- harshvladha 7y agothey mentioned in the introduction only. "we decided to give up external caches like Redis, Memcached or Couchbase mainly because of additional time needed on the network" reason: additional time needed on the network. there are many scenarios in which you will want to consider in-mem cache of the application, one scenario is very low latency requirements.
- dingribanda 7y agoPer the article, Redis requires a network call to the redis server. They wanted an in memory cache. Not sure how would you keep the per machine in memory cache in synch without change propagation to all the machines. This looks like a simple TTL cache.
- tobz 7y agoAgreed. Others have mentioned that the article calls out ignoring traditional in-memory cache daemons because of the additional network time, but with a targeted p50 response time (of their HTTP service fronting all of this), and caches like Redis and memcached being able to respond in hundreds of microseconds... it does feel like they didn't actually run the numbers. The other natural alternative would simply be to run Redis/memcached and colocate this HTTP service on the same box. Now your "network latency" component is almost entirely negligible, and you've deferred the work of managing memory to applications _designed_ around doing so.
- KirinDave 7y agoBecause Redis is... problematic? 1. Redis has a lot of functionality that a simple cache client doesn't need. 2. Redis's connection model can lead to complications. 3. Redis's to-disk checkpointing in practice uses a lot of memory. 4. Redis's poorly chosen default settings have cost the industry an uncounted but large sum of money. 5. Redis is written in C. That's a bad idea for a networked application. 6. Redis's creator is a person who doesn't deserve our support. He's constantly combative with experts who have give him good advice about how to improve Redis because he has a vision of "simplicity" which translates to "what I already understand." Redis is a decent choice if you need all of its features. It's got a wide spectrum. But, if you don't need ALL of them, then pick a simpler and better designed system.
- sagichmal 7y ago> Redis's creator is a person who doesn't deserve our support. There are valid criticisms of Redis but this is shitty and vindictive. You should be ashamed.
- KirinDave 7y agoI'm neither vindictive nor ashamed that I am pointing out Antirez argued passionately and publicly for the right to say "master and slave is a term of art and I will keep using it." I'm also not ashamed of pointing out that Redis as a project is famous for hand waving away redis problems.
- gigatexal 7y agoNone of these projects or exercises are futile: something is learned in the process, and the language gets pushed into new areas, algorithms get proved out etc but it seems that Go is becoming the next hammer and every problem in the problem set has become a nail. Personally I would have just stuck with Redis
- todd3834 7y agoMy understanding is that global variables in Go are not garbage collected. Is that true? If so then is this not creating the cache struct as a global var and therefore this cache will never be garbage collected? https://github.com/allegro/bigcache/blob/master/server/server.go https://github.com/allegro/bigcache/blob/master/server/serve... I ask this because I’ve run into a problem with this in the past.
- hu3 7y agoThe struct pointer itself wont be GC'd. It's intentional as the cache should be up for as long as the server process runs. However, that struct contains data that can and will be GC'd once no longer used. This is the type of the variable: https://github.com/allegro/bigcache/blob/master/bigcache.go https://github.com/allegro/bigcache/blob/master/bigcache.go
- lainga 7y agoThe mantra I'm always told around slices is "Don't keep pointer slices. Don't keep pointer slices." Because the entire thing will fail escape analysis and go onto the heap. But it's OK in this case, right? Because, as you say, the BigCache (including the []*cacheShard) is allocated once; never gets GC'd; and it's around forever.
- KirinDave 7y agoCaches keep data, they don't delete them. It makes sense that a low latency cache would always keep the root of its cache structure in memory.
- thephyber 7y ago> Caches keep data, they don't delete them. To be accurate, caches both keep and delete data. In fact, deleting data is a pretty important function of most caches as the nature of a cache is a fast lookup, not an infinite store.
- 7y ago
- deckarep 7y agoI have not used this package but there is another one for Go called freecache that offers a similar solution. The primary benefit of such solutions is that if you have a Go service where you want to rely on the local caching of data, using a package like this can significantly reduce GC scan pressure removing the work that Go needs to do when analyzing pointer data sitting on the heap. Why does this help? Instead of keeping millions upon millions of items alive on the heap (leading to Go having to scan all such data) you can instead serialize/deserialize the data in a solution like this with usually minimal overhead. Storing your cached data in a solution like this suddenly gets rid of the need to have live pointers of data on the heap. This is because your data is now stored as []byte slice somewhere in the Cache data structure that this code uses. Finally, since packages like BigCache/Freecache are built with only a very small handful of heap objects the Go runtime performance can now go back to what it does best which is spending most of its time in your application logic. If anyone has any doubts of this approach try it out...we saw dramatic differences with using a package like this vs a naive map of pointer based data or vs something like Hashicorps LRU datastructure. The last service we applied this model changed CPU profile from running at around 900% to 400%. That was a big win in my book and practically cut our cluster size in half.
- gfs 7y ago> Storing your cached data in a solution like this suddenly gets rid of the need to have live pointers of data on the heap. So if I understand this correctly, Go does not do any recursive scanning of structures? Each unique bit of data owns it data for as long as it needs to?
- deckarep 7y agoNot quite, the difference here is that instead of storing live objects on the heap you would need to serialize them into a byte slice. You then hand that to the cache library and it would find a place to copy those bytes and store them on your behalf. This means your object now just becomes data belonging to the cache and sits somewhere on the libraries internal data-structure.
- erik_seaberg 7y ago
- merlincorey 7y ago> BigCache does not handle collisions. When new item is inserted and it's hash collides with previously stored item, new item overwrites previously stored value. I'm not sure what hashing algorithm it is using, but this seems like a pretty undesirable property. The code for the hash function is found here: https://github.com/allegro/bigcache/blob/f64abe8f4fe2f5769bd9bef5a2944a83ea673e7e/fnv.go#L19-L28 https://github.com/allegro/bigcache/blob/f64abe8f4fe2f5769bd... // Sum64 gets the string and returns its uint64 hash value. func (f fnv64a) Sum64(key string) uint64 { var hash uint64 = offset64 for i := 0; i < len(key); i++ { hash ^= uint64(key[i]) hash *= prime64 } return hash } The referenced `offset64` is `14695981039346656037` and the `prime64` is `1099511628211`. I can find a reference to a similarly named `Sum64` function in https://godoc.org/blainsmith.com/go/seahash#Sum64 https://godoc.org/blainsmith.com/go/seahash#Sum64 which indicates SeaHash is a non-cryptographic hash function and further considers `Sum64` to be a checksum function. I'm guessing there's a lot more collisions possible here than otherwise expected.
- meritt 7y agoIt's using FNV-1a [1] which is indeed a non-cryptographic hash function and is a perfectly suitable choice for a hash table [2]. The goals are speed and low chance of collision, not security. [1] https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1a_hash https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo... [2] https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed https://softwareengineering.stackexchange.com/questions/4955...
- merlincorey 7y agoThank you for identifying the hash function in specific - that makes sense why it was in `fnv.go`! My point is more to do with the fact that BigCache does not handle collisions at all, whereas the built in Go `map` almost certainly does. Essentially, I can imagine that a Jepsen-like test would reveal that BigCache loses some percentage of writes (dependent on the data, of course). Whether or not that is a problem depends entirely on your use case, of course.
- cyri 7y agoHave a look at, also in Go written, https://github.com/dgraph-io/ristretto https://github.com/dgraph-io/ristretto which out performs bigcache and freecache (see the colourful graphics)
- SergeAx 7y agoAlas, Ristretto implements an eventual consistency.
- mrjn 7y agoFeel free to file an issue if that's a concern -- if enough people feel the same way we could provide an option to "synchronous consistency". It wasn't one in the use cases we looked at.
- SergeAx 7y agoIt would be a significant performance tradeoff, if I understand correctly. So there's no point, there are enough ACID in-memory databases in the world)
- mrjn 7y agoMost likely not a performance tradeoff. For every Get and Set, we do lookups anyway. Caffeine, for comparison, always sets the key-value, and then if the key doesn't get admitted due to policy, deletes it later.
- mrjn 7y ago(author of Ristretto here) Yeah, I'm surprised not enough people here are talking about Ristretto. It was actually designed with knowledge of the existing Go caches, to deal with their limitations -- based on multiple papers and Caffeine [1], popular in Java world. In particular, achieving higher hit ratios while avoiding contention caused by heavy concurrent access. This is worth a read: https://blog.dgraph.io/post/introducing-ristretto-high-perf-go-cache/ https://blog.dgraph.io/post/introducing-ristretto-high-perf-... [1]: https://github.com/ben-manes/caffeine https://github.com/ben-manes/caffeine
- correct_horse 7y agoAll I can think of when I hear about Go now is garbage collector ballast, a hack for which Go has no proper solution see https://blog.twitch.tv/en/2019/04/10/go-memory-ballast-how-i-learnt-to-stop-worrying-and-love-the-heap-26c2462549a2/ https://blog.twitch.tv/en/2019/04/10/go-memory-ballast-how-i... and https://github.com/golang/go/issues/23044 https://github.com/golang/go/issues/23044
- deleted 7y ago[deleted]
- awestroke 7y agoThat's insane. My impression of Go keeps getting worse.