Re: [PATCH 4/9] commit-graph: document bloom filter format

"Garima Singh via GitGitGadget" <gitgitgadget@gmail.com> writes:

I'm not sure. In theory we might want to switch to another probabilistic set inclusion query structure, like xor filters or cuckoo hashing.

On one hand side we could use separate chunks (e.g. XIDX, XDAT for xor filters), on the other hand we need only one such structure. On the gripping hand this can be left for the future, if needed.

Sidenote: using Bloom filters is somewhat encoded in the name of chunk
(B from Bloom filter).  I don't have a better poposal for 4-char name
(XIDX / XDAT for cXange?  CHDX / CHDT for CHange?  FIDX / FDAT for
changed Files?... I don't know).

I think it would be best to keep description of the commit graph format concise. The details about Bloom filter implementation would be better put in Documentation/technical/commit-graph.txt in my opinion, together with reasoning behind it (perhaps borrowing from Derrick Stolee blog post).

This could be done as a separate patch.

s/bloom/Bloom/ and s/it's/its/

I am not sure about exact wording, but I could at this time think of a better but concise way of stating it.

I think it would be better for consistency and ease of reading to follow the example of OID Fanout (OIDF) chunk description:

 +  Bloom Filter Index (ID: {'B', 'I', 'D', 'X'}) (N * 4 bytes) [Optional]
 +      The ith entry, BIDX[i], stores the number of 8-byte word blocks
 +      in all Bloom filters from commit 0 up to commit i (inclusive)
 +      in lexicographical order.

Maybe even add the following to make implementing it easier:

 +      Data for Bloom filter for i-th commit spans from BIDX[i-1] to
 +      BIDX[i] (plus header length), where we take BIDX[-1] to be 0.

Is it possible for (BIDX[i] - BIDX[i-1]) to be zero (no Bloom filter), for example for commits with more than 512 changes? Or is this case handled by 1 8-byte word Bloom filter of all bits sets to '1', i.e. 0xffffffffffffffff?

How the case of too many changes is distingushed from the case of no changes (`git commit --allow-empty`, or `git merge --ours`)? Is the case of no changes uninteresting, i.e. Bloom filter consisting of zero, that is with all bits set to '0'?

I would say "It starts with the header consisting of three unsigned 32-bit integers:" (but current version is not bad).

I wonder if this metadata should perhaps be put in a separate chunk, BMET... (Bloom filter METadata).

This number not only encodes that the base hash algorithm being used is 32-bit Murmur3 hash, but that 'k' hashes used in the computation are created out of Murmur3 hash using double hashing technique, and specifies two specific seed values for this double hashing technique.

[Maybe we should store those two seed values here too?]

It might be important to say that the currently supported version is '1', and if Git encounters unknown hashing algorithm version it should not use Bloom filter data.

Unless we store encoded _name_ of the hash algorithm, e.g. bytes 'm','u','r','3' for MurmurHash3_32... though it is about more than a base hash.

Do we need whole 4 bytes for hash version, or is it for ease of use and alignment?

All right. Perhaps we should test in the future patches that the value different from the default of 7 would also work.

Also 8-bits / 1 byte for number of hashes (hash functions) should be enough: as I have written in prevous reply there is no need for k > 32.

This is important for construction of Bloom filter, but I think it is not necessary to use it -- so it may not be necessary to store it.

Would also fit in a single byte: we don't need exceedingly low false positive probability.

We could use it to estimate the false positive probability, and...

  +	 * The rest of the chunk is the concatenation of all the computed Bloom 
  +	   filters for the commits in lexicographic order.

It would be, I think, a good idea to make it explicit that BDAT is present iff BIDX is present (iff == if and only if), i.e. that either both or neither of those chunks should be present.

Best,