3 ms·
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 cha
by 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 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.
- 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 agoWhile 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 agoSo 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 agoHaven'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.
- kbaker 7y agoAh 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.
- deleted 7y ago[deleted]
- deleted 7y ago[deleted]