Hacker News Reader

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...

[2] https://softwareengineering.stackexchange.com/questions/4955...

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.

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.

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...

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.

[0] https://en.wikipedia.org/wiki/Cache_placement_policies#Direc...

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.

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.

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.

Is 2-left hashing what you're taking about: https://xlinux.nist.gov/dads/HTML/twoLeftHashing.html

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/

Similar to two choice, but they were using it instead of chaining.

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".