Re: Questions about the hash function transition

From: Derrick Stolee <stolee@gmail.com>
Date: Aug 28, 2018, 12:49 UTC
Message-ID: <c098b0c6-1062-6581-81a9-7ce15f3738de@gmail.com>
In-Reply-To: <nycvar.QRO.7.76.6.1808281402510.73@tvgsbejvaqbjf.bet>

On 8/28/2018 8:04 AM, Johannes Schindelin wrote:

Show 21 quoted lines

> Hi,
>
> On Thu, 23 Aug 2018, Jonathan Nieder wrote:
>
>> Ævar Arnfjörð Bjarmason wrote:
>>
>> [...]
>>>> Since all operations that make new objects (e.g., "git commit") add
>>>> the new objects to the corresponding index, this mapping is possible
>>>> for all objects in the object store.
>>> 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.

If we would like such a mapping, then I would propose the following:

1. The object store has everything in SHA-256, so the HASH_LEN parameter 
of the multi-pack-index is 32.

2. We create an optional chunk to add to the multi-pack-index that 
stores the SHA-1 for each object. This list would be in lex order.

3. We create two optional chunks that store the bijection between 
SHA-256 and SHA-1: the first is a list of integers i_0, i_1, ..., 
i_{N-1} such that i_k is the position in the SHA-1 list corresponding to 
the kth SHA-256. The second is a list of integers j_0, j_1, ..., j_{N-1} 
such that j_k is the position in the SHA-256 list of the kth SHA-1.

I'm not super-familiar with how the transition plan specifically needs this mapping, but it seems like a good place to put it.

Thanks,

-Stolee