# When using \`string\` as keys, there could be hash collisions, and thus \`Get\` could return the wrong data **URL:** \ **Category:** Issues\ **Tags:** ristretto, status:accepted, kind:bug, priority:p1\ **Created:** [July 30, 2019, 5:29pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705 "2019-07-30T17:29:39Z")\ **Posts on this page:** 14\ **Page:** 1
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [July 30, 2019, 5:29pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/1 "2019-07-30T17:29:39Z")
**Moved from GitHub [ristretto/30](https://github.com/dgraph-io/ristretto/issues/30)** _Posted by_ [cipriancraciun](https://github.com/cipriancraciun): _This is more a “design question” than an actual “issue”, however given its implications I think it is an important question which impacts either the design or the usage constraints._ Given that the `KeyToHash` (1) function supports `string` (and `[]byte`), and it returns `uint64`, it is possible that there are hash collisions. However the `cache.Get` (2) method doesn’t check if the found entry (if any) actually has the given key. (In fact the `store` doesn’t even support storing the key.) (1) [ristretto/z.go at master · dgraph-io/ristretto · GitHub](https://github.com/dgraph-io/ristretto/blob/master/z/z.go#L20) (2) [ristretto/cache.go at master · dgraph-io/ristretto · GitHub](https://github.com/dgraph-io/ristretto/blob/master/cache.go#L83) ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [July 30, 2019, 6:09pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/2 "2019-07-30T18:09:16Z")
[manishrjain](https://github.com/manishrjain) _commented_ : Yes. We decided to use uint64 knowing that that leaves us open to collisions to avoid paying for significant memory overhead with large keys. The idea is that, if this becomes a problem, we’ll add another hashing technique (or allow a way to do so in general), which we can use to ascertain if the key is correct or not. If there’s a collision, we immediately evict the key from the cache. Also, we’re just going to assume that the chances of a second hash (different algorithm) colliding is too low to be handled. ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [July 30, 2019, 6:46pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/3 "2019-07-30T18:46:00Z")
[cipriancraciun](https://github.com/cipriancraciun) _commented_ : (The statements bellow take into account that you use only a single 64bit hash function.) Granted that by using an AES based hashing algorithm, the chance of a collision given **exactly two entries** is 2^63 (not 64 due to the “birthday effect”). However quoting from [Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) on Wikipedia article (the probability table section), it would take only 200 million different keys to get a 0.1% chance for a collision (these keys don’t necessarily have to be all stored at the same time). * * * However by adding a second 64 bits hash function, you’re basically using now a “compound” 128 bits hash, which means that from a practical point of view you can just do the following: - instead of using AES to generate the hash, use SHA (one of the SHA functions in the family that are hardware accelerated and provides at least 192 bits); - use the first 64 bits of the hash as you are doing now to establish a “slot”; - use the remaining 128 bits to store besides the the actual data; I think will provide a much better collision “margin”, and will increase the current storage requirements by only 16 bytes. ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [July 30, 2019, 8:14pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/4 "2019-07-30T20:14:05Z")
[manishrjain](https://github.com/manishrjain) _commented_ : AESHash is supported by go runtime, and it does 64 bytes key in 5ns on my laptop. If we can find an SHA implementation which can give us this kind of performance, we can quickly switch. ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [July 30, 2019, 8:52pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/5 "2019-07-30T20:52:38Z")
[cipriancraciun](https://github.com/cipriancraciun) _commented_ : > […] we can quickly switch. But are you considering doing this “switch”? (I.e. introducing a way to check that `Get` returns the data for the “actual” key? Where “actual” means with a high degree of probability.) Regarding the 192 bit hash function, one could always use the same `aeshash` function with three different “keys” (“seeds”), which practically would increase the hash time by a factor of 3. ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [July 30, 2019, 9:11pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/6 "2019-07-30T21:11:20Z")
[manishrjain](https://github.com/manishrjain) _commented_ : I think doing it twice should be enough (128 bits), using the second one for detecting conflict. ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [July 30, 2019, 9:28pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/7 "2019-07-30T21:28:48Z")
[cipriancraciun](https://github.com/cipriancraciun) _commented_ : I’m no mathematician / cryptographer but for me, given the following two conditions, it should do the trick: - use the mentioned 128 bit hash (split in the two 64 bit hashes); - provided that one doesn’t keep the values for “too much”; I would define “too much” as: - given a probability of 1e-18 (which Wikipedia states it is the uncorrectable bit error rate for HDD’s), - one needs 2.6e10 different keys to reach a collision (with the previous chosen probability), - which if generated at a rate of ~10K per second, - should take around 28 days; **I.e. my conclusion (to be on the safe side) is that one shouldn’t keep cached data more than a week, and definitively it should be entirely flushed once a month.** ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [September 26, 2019, 10:03am UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/8 "2019-09-26T10:03:59Z")
[6ecuk](https://github.com/6ecuk) _commented_ : > AESHash is supported by go runtime, and it does 64 bytes key in 5ns on my laptop. If we can find an SHA implementation which can give us this kind of performance, we can quickly switch. @manishrjain Hi, maybe look on [GitHub - minio/sha256-simd: Accelerate SHA256 computations in pure Go using AVX512, SHA Extensions for x86 and ARM64 for ARM. On AVX512 it provides an up to 8x improvement (over 3 GB/s per core). SHA Extensions give a performance boost of close to 4x over native.](https://github.com/minio/sha256-simd) ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [September 26, 2019, 11:16pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/9 "2019-09-26T23:16:18Z")
[manishrjain](https://github.com/manishrjain) _commented_ : Yeah, minio sha256 looks useful. ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [September 27, 2019, 2:54am UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/10 "2019-09-27T02:54:08Z")
[dgryski](https://github.com/dgryski) _commented_ : For small keys, minio’s implementation has a lot of overhead. From the readme: `Note that, because of the scheduling overhead, for small messages (< 1 MB) you will be better off using the regular SHA256 hashing`. I have found this to be the case in my benchmarks also. ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [September 29, 2019, 5:37pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/11 "2019-09-29T17:37:06Z")
[andersfylling](https://github.com/andersfylling) _commented_ : This also means the metrics from the benchmarks might be affected by collisions giving false positives when it comes to High hit ratio. ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [October 25, 2019, 5:56pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/12 "2019-10-25T17:56:24Z")
[karlmcguire](https://github.com/karlmcguire) _commented_ : Fixed in #88. ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [January 3, 2020, 1:49pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/13 "2020-01-03T13:49:01Z")
[templexxx](https://github.com/templexxx) _commented_ : > Yes. We decided to use uint64 knowing that that leaves us open to collisions to avoid paying for significant memory overhead with large keys. > > The idea is that, if this becomes a problem, we’ll add another hashing technique (or allow a way to do so in general), which we can use to ascertain if the key is correct or not. If there’s a collision, we immediately evict the key from the cache. Also, we’re just going to assume that the chances of a second hash (different algorithm) colliding is too low to be handled. I think what you want is Cuckoo hashing ---
**Author:** ![diggy](https://yyz1.discourse-cdn.com/flex007/user_avatar/discuss.dgraph.io/diggy/32/3666_2.png) [@diggy](https://discuss.dgraph.io/u/diggy)\ **Post date:** [February 21, 2020, 10:30pm UTC](https://discuss.dgraph.io/t/when-using-string-as-keys-there-could-be-hash-collisions-and-thus-get-could-return-the-wrong-data/8705/14 "2020-02-21T22:30:30Z")
[martinmr](https://github.com/martinmr) _commented_ : @karlmcguire Hey. Is this fixed? Your comment says this was fixed by #88 but you closed and reopened this immediately. If it’s not fixed, what else should be done to close this ticket?