Re: [squid-users] What bit per entry means?

On Wed, 18 Apr 2001, 林英超 wrote:

> I have read Squid FAQ. I am trying to use Cache Digest. but I
> don't know what "bit per entry". Isn't it each entry just needs
> four hash function and needs to set four bit ? And why we need to
> add 7 to "number of bits in array"....
>
> -------------------------------
>
> 16.4 How is the size of the Cache Digest in Squid determined?
> Upon initialisation, the capacity is set to the number of objects that can
> be (are) stored in the cache. Note that there are upper and lower limits
> here.
>
> An arbitrary constant, bits_per_entry (currently set to 5), is used to
> calculate the size of the array using the following formula:
>
> number of bits in array = capacity * bits_per_entry + 7
> ??????????????????
> The size of the digest, in bytes, is therefore:
> digest size = int (number of bits in array / 8)

I think that bits_per_entry part of the formula is well documented in
the paragraph you cited. It is an arbitrary constant or parameter. The
physical meaning of that constant is the mean number of bits per cache
entry, approximately.

By increasing that arbitrary parameter, one gets fewer collisions but
larger digests and vice versa. The number of collisions also depends
on the number of hashing functions, of course. If we had a nice
universal formula for that dependency, we could specify the desired
collision ratio (and compute bits_per_entry) instead of specifying
bits_per_entry directly.

You have to add 7 because arrays are built with bytes, not bits. So
one has to round up to the smallest array of bytes that will contain
the required number of bits. That array size is "digest size" above.
Perhaps it would be clearer if these manipulations were moved to the
"digest size" calculation:
        number of bits in array = capacity * bits_per_entry
        digest size = int ((number of bits in array + 7) / 8)

Alex.
Received on Wed Apr 18 2001 - 07:41:34 MDT