How does Nginx look-up cached resource?

[Sergey Brester]

On 06.09.2015 02:08, Maxim Dounin wrote:

> Well, not, I don't confuse anything. For sure, brute force attack
> on a 128 bit hash requires approximately 2^64 attempts.

> That is, a single nginx instance with 2^64 cached resources will
> likely show up a collision. But that's not a number of resources
> you'll be able to store on a single node - in particular, because
> 64-bit address space wouldn't be enough to address that many
> cached items.

> To obtain a collision of a 128-bit hash with at least 1%
> probability, you'll need more than 10^18 resources cached on a
> single node, which is not even close to a something possible as
> well.

> Assuming 1 billion of keys (which is way more than a single nginx
> node can handle now, and will require about 125G of memory for a
> cache keys zone), probability of a collision is less than 10^(-20).

> Quoting https://en.wikipedia.org/wiki/Birthday_attack [2]:

> For comparison, 10^(-18) to 10^(-15) is the uncorrectable bit
> error rate of a typical hard disk.

1) I will try to explain you, that is not quite true with a small 
approximation: let our hash value be exact one byte large (8 bit), it 
can obtain 2^8 = 256 different hash values (and let it be perfect 
distributed).
The relative frequency to encounter a collision - same hash for any 
random another inside this interval (Hv0 - Hv255) will be also 256, 
because circa each 256-th char sequence will obtain the same hash value 
(Hv0).
Will be such hash safe? Of course not, never.
But if we will hash any character sequences with max length 16 bytes, we 
will have 256^16 (~= 10^38) different variations of binary string 
(keys). The relation (and the probability (Pc) to have a collision for 
two any random strings) would be only (10^38/256 - 1)/10^38 * (10^38/256 
- 2)/(10^38 - 1) ~= 0.000015.
Small, right? But the relative frequency (Hrc) is still 256! This can be 
explained with really large count of different sequences, and so with 
large count of hash values (Hv1-Hv255) that are not equal with (Hv0).

But let us resolve the approximation: the hash value obtain 2^128 (~= 
10^38), but how many values maximum should be hashed? It's unknown. Let 
our keys contain maximum 100 bytes, the count of variations of all 
possible strings will be 256^100 (~= 10^240). The probability to 
encounter of a collision and the relative frequency to encounter a 
collision will be a several order smaller (1e-78), but the relation 
between Hrc and Pc is comparable to example above (in the sense of 
relation between of both). And in this relation is similar (un)safe. Yes 
less likely (well 8 vs 128 bits) but still "unsafe".

And we can have keys with the length of 500 bytes...

And don't compare the probability of error rate in hard disks with 
probability of a collision for hashes of any *pseudo-random* two strings 
(stress mark to "pseudo-random"). This is in about the same as to 
compare a warm with soft.

I can write here larger two pages formulas to prove it. But... forget 
the probabilities and this approximation... we come to point 2.

2) For the *caching* it's at all not required to have such "safe" hash 
functions:
   - The hash function should create reasonably perfect distributed 
values;
   - The hash function should be fast as possible (we can get MurmurHash 
or something similar, significantly faster than md5);
   - We should always compare the keys, after cache entry with hash value 
was found, to be sure exact the same key was found; But that does not 
make our cache slower, because the generation of hash value can be 
faster through algorithms faster as md5 (for example the MMH3 is up to 
90% faster as MD5);
   - In the very less likely case of collision we will just forget the 
cached entry with previous key or save it as array for serial access 
(not really expected by caching and large hash value, because rare and 
that is a cache - not a database that should always hold an entry).

I want implement that and post a PR, and can make it configurable 
(something like `fastcgi_cache_safe = on`) then you can compare the 
performance of it - would be faster as your md5/crc32 implementation.

Regards,
sebres.