Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Ben Peart <peartben@gmail.com>]

On 11/9/2017 11:46 PM, Junio C Hamano wrote:
> Ben Peart <benpeart@microsoft.com> writes:
> 
>> To make this work for V4 indexes, when writing the index, it periodically
>> "resets" the prefix-compression by encoding the current entry as if the
>> path name for the previous entry is completely different and saves the
>> offset of that entry in the IEOT.  Basically, with V4 indexes, it
>> generates offsets into blocks of prefix-compressed entries.
> 
> You specifically mentioned about this change in your earlier
> correspondence on this series, and it reminds me of Shawn's reftable
> proposal that also is heavily depended on prefix compression with
> occasional reset to allow scanning from an entry in the middle.  I
> find it a totally sensible design choice.
> 

Great! I didn't realize there was already precedent for this in other 
patches.  I guess good minds think alike... :)

>> To enable reading the IEOT extension before reading all the variable
>> length cache entries and other extensions, the IEOT is written last,
>> right before the trailing SHA1.
> 
> OK, we have already closed the door for further enhancements to
> place something other than the index extensions after this block by
> mistakenly made it the rule that the end of the series of extended
> sections must coincide with the beginning of the trailing checksum,
> so it does not sound all that bad to insist on this particular one
> to be the last, I guess.  But see below...
> 
>> The format of that extension has the signature bytes and size at the
>> beginning (like a normal extension) as well as at the end in reverse
>> order to enable parsing the extension by seeking back from the end of
>> the file.
> 
> I think this is a reasonable workaround to allow a single extension
> that needs to be read before the main index is loaded.
> 
> But I'd suggest taking this approach one step further.  Instead,
> what if we introduce a new extension EOIE ("end of index entries")
> whose sole purpose is to sit at the end of the series of extensions
> and point at the beginning of the index extension section of the
> file, to tell you where to seek in order to skip the main index?
> 
> That way, you can
> 
>   - seek to the end of the index file;
> 
>   - go backward skiping the trailing file checksum;
> 
>   - now you might be at the end of the EOIE extension.  seek back
>     necessary number of bytes and verify EOIE header, pick up the
>     recorded file offset of the beginning of the extensions section.
> 
>   - The 4-byte sequence you found may happen to match EOIE but that
>     is not enough to be sure that you indeed have such an extension.
>     So the following must be done carefully, allowing the possibility
>     that there wasn't any EOIE extension at the end.
>     Seek back to that offset, and repeat these three steps to skip
>     over all extensions:
> 
>     - read the (possible) 4-byte header
>     - read the (possible) extsize (validate that this is a sane value)
>     - skip that many bytes
> 
>     until you come back to the location you assumed that you found
>     your EOIE header, to make sure you did not get fooled by bytes
>     that happened to look like one.  Some "extsize" you picked up
>     during that process may lead you beyond the end of the index
>     file, which would be a sure sign that what you found at the end
>     of the index file was *not* the EOIE extension but a part of
>     some other extension who happened to have these four bytes at the
>     right place.
> 

I'm doing this careful examination and verification in the patch 
already.  Please look closely at read_ieot_extension() to make sure 
there isn't a test I should be doing but missed.

> which would be a lot more robust way to allow any extensions to be
> read before the main body of the index.
> 
> And a lot more importantly, we will leave the door open to allow
> more than one index extensions that we would prefer to read before
> reading the main body if we do it this way, because we can easily
> skip things over without spending cycles once we have a robust way
> to find where the end of the main index is.  After all, the reason
> you placed IEOT at the end is not because you wanted to have it at
> the very end.  You only wanted to be able to find where it is
> without having to parse the variable-length records of the main
> index.  And there may be other index extensions that wants to be
> readable without reading the main part just like IEOT, and we do not
> want to close the door for them.
> 

The proposed format for extensions (ie having both a header and a footer 
with name and size) in the current patch already enables having multiple 
extensions that can be parsed forward or backward.  Any extensions that 
would want to be parse-able in reverse would just all need to be written 
one after the other after right before the trailing SHA1 (and of course, 
include the proper footer).  The same logic that parses the IEOT 
extension could be extended to continue looking backwards through the 
file parsing extensions until it encounters an unknown signature, 
invalid size, etc.

That said, the IEOT is essentially a table of contents into the index (I 
hesitate to call it an index of the index as that could get confusing 
:)).  While in the current iteration of this patch it only contains 
offsets into blocks of cache entries that are independently parse-able, 
I had initially considered including an offset into the index where the 
extensions start just as you suggest above.

When I looked at the existing extensions to see if they could be sped up 
by loading them on parallel threads I found that some of them 
assume/require they are processed in a specific order so there was no 
real benefit to loading them in parallel threads.

I ended up removing the offset to the first extension because I've found 
that trying to speculatively design a feature for a potential future 
need often doesn't result in what you actually need once you get there. 
:)  Instead, I made sure there was a version number in the IEOT 
structure so if we actually needed a way to extend the table of contents 
at some point in the future (like to include an offset to the 
extensions), we could easily add it and increment the IEOT version.

I could add the offset back in but currently nothing would use it so 
we're just adding additional complexity to calculate and parse it with 
with no (current) benefit.

How about I rename this the "Index Table of Contents" (ITOC) to make 
it's potential more clear and if/when we need to enhance it with an 
offset to the extensions, we do so at that point in time?

> Hmm?
>