Efficient cache for gigabytes of data written in Go
github.com
github.com
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/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
}
I can find a reference to a similarly named `Sum64` function in 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.
[1] https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo...
[2] https://softwareengineering.stackexchange.com/questions/4955...
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.
This property makes BigCache what is known as a "Direct-mapped cache"[0]. A direct mapped cache does lead to a worse cache hit rate, but it does make determining whether there is a cache hit or miss a lot faster. I would need to see benchmarks to tell which is better in practice.
[0] https://en.wikipedia.org/wiki/Cache_placement_policies#Direc...
Seems like this would always be undesirable behavior for a cache?
It is definitely being advertised as a map-like structure, key goes in, bytes come out...
Update:
Yes, that appears to be the strategy in shard.go.
if entryKey := readKeyFromEntry(wrappedEntry); key != entryKey {
s.lock.RUnlock()
s.collision()
if s.isVerbose {
s.logger.Printf("Collision detected. Both %q and %q have the same hash %x", key, entryKey, hashedKey)
}
return nil, ErrEntryNotFound
}
> 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.
This is how every hash table acts by default in almost every language I've used. If a key already exists in the hash, the value is overwritten. I think the only exception was in Java and you had to use a specific hash object to get the effect you are stating.
Imagine a naïve hash-function, h(x), that simply mods x by 10.
Now, let's insert (key, value) pairs (20, twenti), (3, three), and (30, thirty) into the table in succession.
h(20) = 20 mod 10 = 0
(20, twenti) is inserted at empty slot, table[0]
h(3) = 3 mod 10 = 3
(3, three) is inserted at empty slot, table[3]
h(30) = 30 mod 10 = 0
Conflict. (30, thirty) which is not equal to (20, twenti) will be hashed to the same slot, table[0], as the latter.
Historically, hash-tables have resolved these conflicts via open-addressing or linear-chaining.
And, let's say we now insert (20, twenty).
h(20) = 20 mod 10 = 0
Update. Inserting (20, twenty) at table[0] is not a conflict since the key, 20, of the existing entry at table[0], (20, twenti), and of the incoming entry, (20, twenty), are equal.
In BigCache's case, if I'm right, all conflicts are updates.
Of course BigCache is faster than the builtin map -- they are completely different kinds of hash table.
As malisp explains in a comment above, BigCache is a "direct mapped cache".
Each key can live in two slots, using two different hash algorithms. If it’s not in the first it’ll be in the second. I can’t speak to the quality of their math. And of course a lot of theory for hash tables is based on the quality of the hash. The empirical evidence has often failed to support the theory.
If not, Michael Mitzenmacher is known to research a lot on hashing algorithms, may be you would find it was one of his papers? https://dblp.uni-trier.de/pers/hd/m/Mitzenmacher:Michael
Also see: https://danluu.com/2choices-eviction/
This is worth a read: https://blog.dgraph.io/post/introducing-ristretto-high-perf-...
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.
"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.
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.
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.
There are valid criticisms of Redis but this is shitty and vindictive. You should be ashamed.
Further: the Redis take on display in that comment is pretty mainstream – very much including the statement about Sanfilippo's obstinacy – among systems developers. Even if you're an advocate for Redis, it's good to at least see the brief its detractors bring against it.
If that's ^^ unsubstantive drama to you, and the thing it's responding to isn't, calibrate your sensors because they're off.
I knew my post would be controversial, but I certainly wasn't expecting that the main complaint leveled is that I'm supposed to ignore he and his community's prior transgressions because remembering them is "vindictive."
That’s a heafty claim. It is certainly more complicated to write a network complication in C vs a higher level language like Go, but by no means a bad idea in terms of outcome.
A bigger issue may be the QPS that a cache generates, as you tend to check large quantities of values against it. So the network round trip to Redis isn’t ideal, and you may get into a situation where it’s single threaded nature becomes a bottleneck if your values are large (tho generally Redis is memory or network bounded, not CPU).
It is dangerous to write network connected applications in C. This is not a hefty claim, it's well understood in the industry and most major tech firms avoid writing new software this way.
> A bigger issue may be the QPS that a cache generates, as you tend to check large quantities of values against it. So the network round trip to Redis isn’t ideal, and you may get into a situation where it’s single threaded nature becomes a bottleneck if your values are large (tho generally Redis is memory or network bounded, not CPU).
For most modern deployment models of Redis, I do not think that this is correct. Redis tends to be run locally with API responders, and as such the RTT will be lost in the noise that most web frameworks introduce. Surely if there is a big RTT that is a problem, but that's not a Redis-specific problem (although the consistent tcp connections with potentially sparse usage it prefers may add knock on effects in this condition).
Does your blanket statement apply to C++ and other C derivatives as well? If so, we lose MySQL, Oracle SQL, MS SQL. Basically every database written more than a decade ago.
From what I can tell general consensus seems to be that all of those systems are pretty stable and not dangerous because of their language choice.
Yes, actually. And in fact, both Redis and Memcached have been implicated in both security issues and their policy misconfigurarions have lead to widespread DDoS attacks.
As for Postgres, I think most of the industry has finally stopped directly connecting postgres to the public internet. It took many years to get any of these projects as stable as they are, and all have had major security issues in that path.
You should expect those problems if you start a new project in C, with roughly the same lifecycle. Even if you play it in fast forward (say, 25% faster) you're still in for years of major security and stability issues.
This seems ill considered in 2019.
> Does your blanket statement apply to C++ and other C derivatives as well? If so, we lose MySQL, Oracle SQL, MS SQL. Basically every database written more than a decade ago.
No, although you really need to stick to the libraries to make C++ safe. Bare pointer handling and falling back on C-like semantics is dangerous.
> From what I can tell general consensus seems to be that all of those systems are pretty stable and not dangerous because of their language choice.
I'm not sure how we'd directly measure it. Most folks I know trust Memcached slightly more than Redis because its smaller, but consider both to be risky and best when not directly connected to the public internet, as is common with MySQL and Postgres.
Pretty much _all_ backend software is 'dangerous' when connected to the public internet.
It's fairly rare for anything other than say HTTP(S) and SSH to be exposed unless absolutely necessary.
It's not like it's difficult to cock up authentication in Rust, for example.
Yes, software security is hard. That's why you shouldn't make it harder by using a language that has tons of undefined behavior unless you have to.
I ask this because I’ve run into a problem with this in the past.
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
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.
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.
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?