5 ms·

This is a seriously great write up. So many links to research and papers. There were some truly new-to-me concepts and they implemented some stuff that are opti

This is a seriously great write up. So many links to research and papers. There were some truly new-to-me concepts and they implemented some stuff that are optimizations that I've not had to deal with yet despite the scale with which I work; it is fun to read about those. Seriously awesome work -- I would love to optimize as much as they have. Two things stand out. One, they could maybe improve thrashing at full capacity by evicting more than one key when at capacity (say, evict n% of total keys). Two, my reading here suggests this is not production ready and dangerous to use. > ... then used this hash as not only the stored key but also to figure out the shard the key should go into. This does introduce a chance of key collision, that’s something we plan to deal with later. If a Get and Set can produce a collision and it is not dealt with, then it is unsafe for production. Imagine calling user foo's data and returning user bar's data instead. This could leak PII and would be an unnoticed bug. Generally, in collisions, you drop down to a list and hurt your runtime to ensure accuracy. I need a correct cache over a fast cache. Unless I misunderstood, this is not production ready. Again, amazing work; it is just not done yet.

demmer 7y ago
> If a Get and Set can produce a collision and it is not dealt with, then it is unsafe for production. That was confusing to me as well in the article. However they also wrote: > If however, a key is already present in the cache, Set would update the key immediately. This is to avoid a cached key holding a stale value. So it sounds like inserts to the cache might not immediately apply, but overwrites are guaranteed to invalidate stale data in cache.
- sethammons 7y ago
  The problem isn't stale data, the problem is getting data for an entirely different key. As an extreme example, if your terrible hashing algo was 'int(key) mod 10', then you have no collisions on keys "3", "45", and "99". However, if you asked for "19", you would get back the data for "99". If that data is their email address, name, address, or medical prognosis, then you just leaked PII when that data is served to a user. Worst of all, you wouldn't even know unless the customer calls up wondering why they got incorrect data.
  - deleted 7y ago
    [deleted]
mrjn 7y ago
We will fix that in the near future. Known problem with our design choice. Wanted to ensure we put it out there first, before solving it. FWIW, note that the probability of a collision with 64 bit hash is pretty low. Still, needs to be solved.
- grumpydba 7y ago
  Could this be solved by some sort of cuckoo hashing?
  - mrjn 7y ago
    The benefit of current hashing algorithm is that Go team is maintaining it ;-). Its written in assembly and runs in single digit nanoseconds. One way to check for collision would be to either store the key as well or use another hashing algorithm (which would further decrease the probability of collision, but not eliminate it). Either would introduce some slowness, because every Get would need to be checked.
    - sethammons 7y ago
      Storing the key with the value is a solid workaround.
      - deleted 7y ago
        [deleted]
- qes 7y ago
  I use 128 bit spooky hash for keys in a system with ~1M keys in cache at any given time, give or take. Rough numbers but maybe 75% of those keys existed last month and will still exist next month and probably next year, too, and 25% will exist for minutes to hours and likely never be seen again. Collisions are uncommon, but a regular enough occurrence (dozen or two a year).
mrjn 7y ago
> by evicting more than one key when at capacity (say, evict n% of total keys) Ristretto does that already. It evicts as many keys as needed to stay within the MaxCost. This is done outside the critical path by background goroutines. However, you also don't want to evict too many keys, because that would affect the hit ratios.
- sethammons 7y ago
  Very cool!

demmer 7y ago

> If a Get and Set can produce a collision and it is not dealt with, then it is unsafe for production. That was confusing to me as well in the article. However they also wrote: > If however, a key is already present in the cache, Set would update the key immediately. This is to avoid a cached key holding a stale value. So it sounds like inserts to the cache might not immediately apply, but overwrites are guaranteed to invalidate stale data in cache.

sethammons 7y ago
The problem isn't stale data, the problem is getting data for an entirely different key. As an extreme example, if your terrible hashing algo was 'int(key) mod 10', then you have no collisions on keys "3", "45", and "99". However, if you asked for "19", you would get back the data for "99". If that data is their email address, name, address, or medical prognosis, then you just leaked PII when that data is served to a user. Worst of all, you wouldn't even know unless the customer calls up wondering why they got incorrect data.
- deleted 7y ago
  [deleted]

mrjn 7y ago

We will fix that in the near future. Known problem with our design choice. Wanted to ensure we put it out there first, before solving it. FWIW, note that the probability of a collision with 64 bit hash is pretty low. Still, needs to be solved.

grumpydba 7y ago
Could this be solved by some sort of cuckoo hashing?
- mrjn 7y ago
  The benefit of current hashing algorithm is that Go team is maintaining it ;-). Its written in assembly and runs in single digit nanoseconds. One way to check for collision would be to either store the key as well or use another hashing algorithm (which would further decrease the probability of collision, but not eliminate it). Either would introduce some slowness, because every Get would need to be checked.
  - sethammons 7y ago
    Storing the key with the value is a solid workaround.
    - deleted 7y ago
      [deleted]
qes 7y ago
I use 128 bit spooky hash for keys in a system with ~1M keys in cache at any given time, give or take. Rough numbers but maybe 75% of those keys existed last month and will still exist next month and probably next year, too, and 25% will exist for minutes to hours and likely never be seen again. Collisions are uncommon, but a regular enough occurrence (dozen or two a year).

mrjn 7y ago

> by evicting more than one key when at capacity (say, evict n% of total keys) Ristretto does that already. It evicts as many keys as needed to stay within the MaxCost. This is done outside the critical path by background goroutines. However, you also don't want to evict too many keys, because that would affect the hit ratios.

sethammons 7y ago
Very cool!