Subject: Calculation of the hash width in cache-digests

From: Martin Thomson <[email-masked]>
Date: Mon, 18 Jul 2016 15:27:54 +0200

The draft describes how to select P to achieve a particular false
positive probability.  The net effect of this is that you get
approximately the probability.

I think that this would be better if there was a description of how to
decide on an upper bound for the false positive probability.

The calculation is a little less clean:

n is the number of resources
p is the lower bound of the probability of false positive

P is the number of fixed bits allocated to each entry
N+P is the width of the hash output

All of these are integers, except p, which is a number between 0 and 1.

The current draft chooses:

P = ??(0 - log2(p)) - it's not clear, but I imagine that this uses floor()
N = round(log2(n))

I propose that we instead do:

P = round(0 - log2(p))
N+P = ceil(log2(n)-log2(p))

This is, I think, a much better calculation.  We would still benefit
from encoding N and P separately.

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 19 Jul 2016 01:20:26 +0900

> from encoding N and P separately.

Thank you for the suggestion.

We need to encode N and P, since the two values are mandatory for
correctly decoding the digest. That means that how the values are
encoded must be defined in a normative form, as well as how the hashed
values are encoded.

On the other hand, how N and P should be selected not necessarily
needs to be defined; it’s completely up to the client. Therefore, it
might make more sense to define the process as an example.

That said, I agree that it might make more sense to describe a process
that uses the upper bound of the false-positive rate. However, if that
is the case, we cannot calculate P directly from the false-positive
rate, since P chosen as the reciprocal of the false-positive-rate
becomes as half as small than it should be in case N is just below
power-of-two (in such case, we would waste approx. 1 bit per entry).

So, I think we should define the encoding process of digest-value as follows:

In normative form, specify to:

1. decide appropriate N, P as well as constructing a list of
sha256(url) values, each of them truncated to log2(N+P) bits and
deduped
2. encode N, P, and the listed values using GCS

and as a suggestion, describe the following algorithm for calculating
the three values of above step 1:

1. if the url list is empty, set N=0, P=0 and return
2. set NP to round_up_to_power_of_two(num_urls / max_false_positive_rate)
3. create a list that contains sha256(url) of all the URLs, each
truncated to log2(NP) bits
4. sort the list and remove the duplicates
5. set P to round_to_nearest_power_of_two(NP / size-of-the-list)
6. set N to NP / P

The added bonus of not calculating P directly from false-positive rate
are that i) it would emit more compact GCS for any false-positive
rates not rounded to power-of-two (e.g. 1/100) and ii) it would emit
more compact GCS in case false-positive rate is very high (in such
case, many keys would be removed by dedupe, and that has an effect on
the ideal value of P).

-- 
Kazuho Oku

---

From: Martin Thomson <[email-masked]>
Date: Mon, 18 Jul 2016 18:29:31 +0200

> 5. set P to round_to_nearest_power_of_two(NP / size-of-the-list)

Yes, I believe that this is exactly what I proposed.

I agree with you that the choice of values for N and P need to be
signaled, but they don't need to be selected in the same way.  The
draft could be clearer about this; even to the point of explicitly
saying that.