> 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.
// 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 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.
It'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.
While caches and maps share many of the same underlying properties, they serve very different purposes. Caches generally come with configurable size limits, eviction policies, and collision handling (overwriting is a simple solution). They are in no way designed to be durable data storage mechanisms.
Haven't looked at the full implementation of BigCache, but typically, a cache would fetch the object and key from the data structure. If the full key doesn't match the requested key, then the cache will respond that the key is not in the cache. The calling function would then figure out whether to replenish the cache or not.
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
}
so there is no risk of returning the wrong data for a key.
Ah OK, that's good, just was reading too much into this section in the README:
> 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.
> My point is more to do with the fact that BigCache does not handle collisions at all
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.
It's a pity they use a fixed offset basis for FNV-1a. For many non-persistent use cases it's perfectly valid to use a randomized offset basis. This makes it harder for external parties to come up with keys that would cause a high collision rate.
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.
No, what BigCache does isn't what hash tables do to resolve conflicts and the JDK Maps absolutely do not overwrite value upon collision of unequal keys.
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.
I recall reading a paper, maybe ten years back, about a collision handling algorithm that was far simpler than any I’d seen before. The paper claimed that double hashing avoided unresolvable collisions in most cases without chaining or any of the additional overhead (especially on deletes) of cuckoo hashing or any of the alternatives.
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.
Thank you for breaking this down -- since the author compared BigCache to the built in `map`, this collision behavior is precisely what brought on my line of thinking.
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".
(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.
Feel 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.
It 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)
Most 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.
This 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.
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.
There’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.
Per 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.
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.
Actually the main thing about simplicity is having an ego small enough that you don't need to show, in your code / design, everything you are capable of understanding, if less is already enough. The fact I understand strong consistency does not mean this is a good design choice for Redis. Actually who followed certain advices provided by experts, now closed the doors of their business in the database area. You can't be hostage of your users.
> Redis is written in C. That's a bad idea for a networked application.
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).
> 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.
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).
So Memcached, Redis, and Postgres are all dangerous to use because they are written in C?
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.
> Memcached, Redis, and Postgres are all dangerous to use because they are written in C?
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.
On this KirinDave is absolutely correct. Those systems are stable in spite of the language choice; anyone seeking to do similar work today would be professionally negligent to choose C.
I don't love the way the previous comment is written, but it's substantive. This is just drama; it distills the worst possible reading from the parent comment and tries to fix that meaning for the rest of the thread, which is exactly the opposite of what the guidelines ask you to do.
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.
I agree that Sanfilippo can be obstinate. "Redis' creator doesn't deserve our support" is a shitty and vindictive conclusion to come to from that obstinance.
If that's ^^ unsubstantive drama to you, and the thing it's responding to isn't, calibrate your sensors because they're off.
I don't really understand why this is so traumatic to say. There are lots of people doing amazing things. Maybe we can look at projects run by people who don't disregard good technical advice for years out of what they themselves have called pride.
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."
You disagree with it. That's fine. But people are allowed to say that things are or aren't worthy of support. Ironically, what they shouldn't do is call them "shitty and vindictive", which that comment didn't do.
Actually the comment is not substantive. Not telling what is the configuration that creates problems, not telling what's wrong about the Redis connection handling, not comparing Redis fork based persistence with the alternative in memory systems have, and so forth, is a exactly the hand waving the OP accuses of doing. Very short not detailed criticisms of systems are actually FUD because in complex systems the devil is in the details.
If it's the only think you criticize about him, then I guess he is worth of support. There is nothing wrong with this terminology unless you can prove otherwise.
Weird, I didn't mention it on the first post. I had 6 specific criticisms, 5 of which were technical.
If anything, this is an example of how the Redis community has actors that pop up trying to distract from direct criticism.
I'm being downvoted and flagged despite my post being substantive, on topic, and in direct response to a question. There are valid reasons not to use Redis.
My 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/serve...
I ask this because I’ve run into a problem with this in the past.
The 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.
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.
This is of course a glib statement, but in general cached have specific (often configurable) eviction policies, so we would expect to see the root of the cache held perpetually anyways.
None 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
I 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.
> 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?
Not 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.
People considering this should benchmark both options. Constantly deserializing everything you need has a predictable but very high cost, often worse for throughput than a well-tuned GC.
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...
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 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.