Re: Questions about the hash function transition

From: Derrick Stolee <stolee@gmail.com>
Date: Aug 29, 2018, 13:27 UTC
Message-ID: <04300dbc-622a-c8cb-172e-985726249a8e@gmail.com>
In-Reply-To: <nycvar.QRO.7.76.6.1808291458480.71@tvgsbejvaqbjf.bet>

On 8/29/2018 9:09 AM, Johannes Schindelin wrote:

Show 27 quoted lines

> Hi Jonathan,
>
> On Tue, 28 Aug 2018, Jonathan Nieder wrote:
>
>> Johannes Schindelin wrote:
>>> On Thu, 23 Aug 2018, Jonathan Nieder wrote:
>>>> Ævar Arnfjörð Bjarmason wrote:
>>>>> Are we going to need a midx version of these mapping files? How does
>>>>> midx fit into this picture? Perhaps it's too obscure to worry
>>>>> about...
>>>> That's a great question!  I think the simplest answer is to have a
>>>> midx only for the primary object format and fall back to using
>>>> ordinary idx files for the others.
>>>>
>>>> The midx format already has a field for hash function (thanks,
>>>> Derrick!).
>>> Related: I wondered whether we could simply leverage the midx code for
>>> the bidirectional SHA-1 <-> SHA-256 mapping, as it strikes me as very
>>> similar in concept and challenges.
>> Interesting: tell me more.
>>
>> My first instinct is to prefer the idx-based design that is already
>> described in the design doc.  If we want to change that, we should
>> have a motivating reason.
>>
>> Midx is designed to be optional and to not necessarily cover all
>> objects, so it doesn't seem like a good fit.

It is optional, but shouldn't this mode where a Git repo that needs to know about two different versions of all files be optional? Or at least temporary?

The multi-pack-index is intended to cover all packed objects, so covers the same number of objects as an IDX-based strategy. If we are rebuilding the repo from scratch by translating the hashes, then "being too big to repack" is probably not a problem, so we would expect a single IDX file anyway.

In my opinion, whatever we do for the IDX-based approach will need to be duplicated in the multi-pack-index. The multi-pack-index does have a natural mechanism (optional chunks) for inserting this data without incrementing the version number.

Show 9 quoted lines

> Right.
>
> What I meant was to leverage the midx code, not the .midx files.
>
> My comment was motivated by my realizing that both the SHA-1 <-> SHA-256
> mapping and the MIDX code have to look up (in a *fast* way) information
> with hash values as keys. *And* this information is immutable. *And* the
> amount of information should grow with new objects being added to the
> database.

I'm unsure what this means, as the multi-pack-index simply uses bsearch_hash() to find hashes in the list. The same method is used for IDX lookups.

> I know that Stolee performed a bit of performance testing regarding
> different data structures to use in MIDX. We could benefit from that
> testing by using not only the results from those tests, but also the code.

I did test ways to use something other than bsearch_hash(), such as using a 65,536-entry fanout table for lookups using the first two bytes of a hash (tl;dr: it speeds things up a bit, but the super-small improvement is probably not worth the space and complexity). I've also toyed with the idea of using interpolation search inside bsearch_hash(), but I haven't had time to do that.

Show 8 quoted lines

> IIRC one of the insights was that packs are a natural structure that
> can be used for the MIDX mapping, too (you could, for example, store the
> SHA-1 <-> SHA-256 mapping *only* for objects inside packs, and re-generate
> them on the fly for loose objects all the time).
>
> Stolee can speak with much more competence and confidence about this,
> though, whereas all of what I said above is me waving my hands quite
> frantically.

I understand the hesitation to pair such an important feature (hash transition) to a feature that hasn't even shipped. We will need to see how things progress on both fronts to see how mature the multi-pack-index is when we need this transition table.

Thanks,

-Stolee