4 ms·

> 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

> 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 ago
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. [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 ago
  Thank 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.
  - malisper 7y ago
    > 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. [0] https://en.wikipedia.org/wiki/Cache_placement_policies#Direct-mapped_cache https://en.wikipedia.org/wiki/Cache_placement_policies#Direc...
  - meritt 7y ago
    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.
    - kbaker 7y ago
      So does it just serve completely incorrect data when a request for the 'old' cache key come in? 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...
      - archgoon 7y ago
        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.
- deleted 7y ago
  [deleted]
- deleted 7y ago
  [deleted]
thrownaway954 7y ago
Am I missing something here? 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.
- ignoramous 7y ago
  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.
  - merlincorey 7y ago
    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".
  - hinkley 7y ago
    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.
EdSchouten 7y ago
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.

meritt 7y ago

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. [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 ago
Thank 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.
- malisper 7y ago
  > 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. [0] https://en.wikipedia.org/wiki/Cache_placement_policies#Direct-mapped_cache https://en.wikipedia.org/wiki/Cache_placement_policies#Direc...
- meritt 7y ago
  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.
  - kbaker 7y ago
    So does it just serve completely incorrect data when a request for the 'old' cache key come in? 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...
    - archgoon 7y ago
      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.
deleted 7y ago
[deleted]
deleted 7y ago
[deleted]

thrownaway954 7y ago

Am I missing something here? 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.

ignoramous 7y ago
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.
- merlincorey 7y ago
  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".
- hinkley 7y ago
  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.

EdSchouten 7y ago

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.