Re: [PATCH 00/30] [RFC] extensions.refFormat and packed-refs v2 file format

On Mon, Nov 7, 2022 at 11:01 AM Derrick Stolee via GitGitGadget
[off-list ref] wrote:

Introduction
============

I became interested in our packed-ref format based on the asymmetry between
ref updates and ref deletions: if we delete a packed ref, then the
packed-refs file needs to be rewritten. Compared to writing a loose ref,
this is an O(N) cost instead of O(1).

In this way, I set out with some goals:

 * (Primary) Make packed ref deletions be nearly as fast as loose ref
   updates.

Performance is always nice.  :-)

 * (Secondary) Allow using a packed ref format for all refs, dropping loose
   refs and creating a clear way to snapshot all refs at a given point in
   time.

Is this secondary goal the actual goal you have, or just the
implementation by which you get the real underlying goal?

To me, it appears that such a capability would solve both (a) D/F
conflict problems (i.e. the ability to simultaneously have a
refs/heads/feature and refs/heads/feature/shiny ref), and (b) case
sensitivity issues in refnames (i.e. inability of some users to work
with both a refs/heads/feature and a refs/heads/FeAtUrE, due to
constraints of their filesystem and the loose storage mechanism).  Are
either of those the goal you are trying to achieve (I think both would
be really nice, more so than the performance goal you have), or is
there another?

I also had one major non-goal to keep things focused:

 * (Non-goal) Update the reflog format.

After carefully considering several options, it seemed that there are two
solutions that can solve this effectively:

 1. Wait for reftable to be integrated into Git.
 2. Update the packed-refs backend to have a stacked version.

The reftable work seems currently dormant. The format is pretty complicated
and I have a difficult time seeing a way forward for it to be fully
integrated into Git. Personally, I'd prefer a more incremental approach with
formats that are built for a basic filesystem. During the process, we can
create APIs within Git that can benefit other file formats within Git.

Further, there is a simpler model that satisfies my primary goal without the
complication required for the secondary goal. Suppose we create a stacked
packed-refs file but only have two layers: the first (base) layer is created
when git pack-refs collapses the full stack and adds the loose ref updates
to the packed-refs file; the second (top) layer contains only ref deletions
(allowing null OIDs to indicate a deleted ref). Then, ref deletions would
only need to rewrite that top layer, making ref deletions take O(deletions)
time instead of O(all refs) time. With a reasonable schedule to squash the
packed-refs stack, this would be a dramatic improvement. (A prototype
implementation showed that updating a layer of 1,000 deletions takes only
twice the time as writing a single loose ref.)

Makes sense.  If a ref is re-introduced after deletion, then do you
remove it from the deletion layer and then write the single loose ref?

If we want to satisfy the secondary goal of passing all ref updates through
the packed storage, then more complicated layering would be necessary. The
point of bringing this up is that we have incremental goals along the way to
that final state that give us good stopping points to test the benefits of
each step.

I like the incremental plan.  Your primary goal perhaps benefits
hosting providers the most, while the second appears to me to be an
interesting usability improvement (some of my users might argue it's
even a bugfix) that would affect users with far fewer refs as well.
So, lots of benefits and we get some along the way to the final plan.

Stacking the packed-refs format introduces several interesting strategy
points that are complicated to resolve. Before we can do that, we first need
to establish a way to modify the ref format of a Git repository. Hence, we
need a new extension for the ref formats.

To simplify the first update to the ref formats, it seemed better to add a
new file format version to the existing packed-refs file format. This format
has the exact lock/write/rename mechanics of the current packed-refs format,
but uses a file format that structures the information in a more compact
way. It uses the chunk-format API, with some tweaks. This format update is
useful to the final goal of a stacked packed-refs API, since each layer will
have faster reads and writes. The main reason to do this first is that it is
much simpler to understand the value-add (smaller files means faster
performance).


RFC Organization
================

This RFC is quite long, but the length seemed necessary to actually provide
and end-to-end implementation that demonstrates the packed-refs v2 format
along with test coverage (via the new GIT_TEST_PACKED_REFS_VERSION
variable).

For convenience, I've broken each section of the full RFC into parts, which
resembles how I intend to submit the pieces for full review. These parts are
available as pull requests in my fork, but here is a breakdown:

Part I: Optionally hash the index
=================================

[1] https://github.com/derrickstolee/git/pull/23 Packed-refs v2 Part I:
Optionally hash the index (Patches 1-2)

The chunk-format API uses the hashfile API as a buffered write, but also all
existing formats that use the chunk-format API also have a trailing hash as
part of the format. Since the packed-refs file has a critical path involving
its write speed (deleting a packed ref), it seemed important to allow
apples-to-apples comparison between the v1 and v2 format by skipping the
hashing. This is later toggled by a config option.

In this part, the focus is on allowing the hashfile API to ignore updating
the hash during the buffered writes. We've been using this in microsoft/git
to optionally speed up index writes, which patch 2 introduces here. The file
format instead writes a null OID which would look like a corrupt file to an
older 'git fsck'. Before submitting a full version, I would update 'git
fsck' to ignore a null OID in all of our file formats that include a
trailing hash. Since the index is more short-lived than other formats (such
as pack-files) this trailing hash is less useful. The write time is also
critical as the performance tests demonstrate.

This feels like a diversion from your goals.  Should it really be up-front?

Reading through the patches, the first patch does appear to be
necessary but isn't well motivated from the cover letter.  The second
patch seems orthogonal to your series, though it is really nice to see
index writes dropping almost to half the time.

Part II: Create extensions.refFormat
====================================

[2] https://github.com/derrickstolee/git/pull/24 Packed-refs v2 Part II:
create extensions.refFormat (Patches 3-7)

This part is a critical concept that has yet to be defined in the Git
codebase. We have no way to incrementally modify the ref format. Since refs
are so critical, we cannot add an optionally-understood layer on top (like
we did with the multi-pack-index and commit-graph files). The reftable draft
[6] proposes the same extension name (extensions.refFormat) but focuses
instead on only a single value. This means that the reftable must be defined
at git init or git clone time and cannot be upgraded from the files backend.

In this RFC, I propose a different model that allows for more customization
and incremental updates. The extensions.refFormat config key is multi-valued
and defaults to the list of files and packed.

This last sentence doesn't parse that well for me.  Perhaps "...and
defaults to a combination of 'files' and 'packed', meaning supporting
both loose refs and packed refs "?

In the context of this RFC,
the intention is to be able to add packed-v2 so the list of all three values
would allow Git to write and read either file format version (v1 or v2). In
the larger scheme, the extension could allow restricting to only loose refs
(just files) or only packed-refs (just packed) or even later when reftable
is complete, files and reftable could mean that loose refs are the primary
ref storage, but the reftable format serves as a drop-in replacement for the
packed-refs file. Not all combinations need to be understood by Git, but
having them available as an option could be useful for flexibility,
especially when trying to upgrade existing repositories to new formats.

In the future, beyond the scope of this RFC, it would be good to add a
stacked value that allows a stack of files in packed-refs format (whose
version is specified by the packed or packed-v2 values) so we can further
speed up writes to the packed layer. Depending on how well that works, we
could focus on speeding up ref deletions or sending all ref writes straight
to the packed-refs layer. With the option to keep the loose refs storage, we
have flexibility to explore that space incrementally when we have time to
get to it.


Part III: Allow a trailing table-of-contents in the chunk-format API
====================================================================

[3] https://github.com/derrickstolee/git/pull/25 Packed-refs v2 Part III:
trailing table of contents in chunk-format (Patches 8-17)

In order to optimize the write speed of the packed-refs v2 file format, we
want to write immediately to the file as we stream existing refs from the
current refs. The current chunk-format API requires computing the chunk
lengths in advance, which can slow down the write and take more memory than
necessary. Using a trailing table of contents solves this problem, and was
recommended earlier [7]. We just didn't have enough evidence to justify the
work to update the existing chunk formats. Here, we update the API in
advance of using in the packed-refs v2 format.

We could consider updating the commit-graph and multi-pack-index formats to
use trailing table of contents, but it requires a version bump. That might
be worth it in the case of the commit-graph where computing the size of the
changed-path Bloom filters chunk requires a lot of memory at the moment.
After this chunk-format API update is reviewed and merged, we can pursue
those directions more closely. We would want to investigate the formats more
carefully to see if we want to update the chunks themselves as well as some
header information.

I like how you point out additional benefits the series could provide,
but leave them out.  Perhaps do the same with the optional index
hashing in patch 2?

Part IV: Abstract some parts of the v1 file format
==================================================

[4] https://github.com/derrickstolee/git/pull/26 Packed-refs v2 Part IV:
abstract some parts of the v1 file format (Patches 18-21)

These patches move the part of the refs/packed-backend.c file that deal with
the specifics of the packed-refs v1 file format into a new file:
refs/packed-format-v1.c. This also creates an abstraction layer that will
allow inserting the v2 format more easily.

One thing that doesn't exist currently is a documentation file describing
the packed-refs file format. I would add that file in this part before
submitting it for full review. (I also haven't written the file format doc
for the packed-refs v2 format, either.)

Sounds like another win-win opportunity to get someone from the
community to contribute.  :-)   ..Or maybe that's not the best
strategy, since recent empirical evidence suggests that trick doesn't
work.  Oh well, it was worth a shot.

Part V: Implement the v2 file format
====================================

[5] https://github.com/derrickstolee/git/pull/27 Packed-refs v2 Part V: the
v2 file format (Patches 22-35)

This is the real meat of the work. Perhaps there are ways to split it
further, but for now this is what I have ready. The very last patch does a
complete performance comparison for a repo with many refs.

The format is not yet documented, but is broken up into these pieces:

 1. The refs data chunk stores the same data as the packed-refs file, but
    each ref is broken down as follows: the ref name (with trailing zero),
    the OID for the ref in its raw bytes, and (if necessary) the peeled OID
    for the ref in its raw bytes. The refs are sorted lexicographically.

 2. The ref offsets chunk is a single column of 64-bit offsets into the refs
    chunk indicating where each ref starts. The most-significant bit of that
    value indicates whether or not there is a peeled OID.

 3. The prefix data chunk lists a set of ref prefixes (currently writes only
    allow depth-2 prefixes, such as refs/heads/ and refs/tags/). When
    present, these prefixes are written in this chunk and not in the refs
    data chunk. The prefixes are sorted lexicographically.

 4. The prefix offset chunk has two 32-bit integer columns. The first column
    stores the offset within the prefix data chunk to the start of the
    prefix string. The second column points to the row position for the
    first ref that has name greater than this prefix (the 0th prefix is
    assumed to start at row 0, so we can interpret the prefix range from
    row[i-1] and row[i]).

Between using raw OIDs and storing the depth-2 prefixes only once, this
format compresses the file to ~60% of its v1 size. (The format allows not
writing the prefix chunks, and the prefix chunks are implemented after the
basics of the ref chunks are complete.)

The write times are reduced in a similar fraction to the size difference.
Reads are sped up somewhat, and we have the potential to do a ref count by
prefix much faster by doing a binary search for the start and end of the
prefix and then subtracting the row positions instead of scanning the file
between to count refs.


Relationship to Reftable
========================

I mentioned earlier that I had considered using reftable as a way to achieve
the stated goals. With the current state of that work, I'm not confident
that it is the right approach here.

My main worry is that the reftable is more complicated than we need for a
typical Git repository that is based on a typical filesystem. This makes
testing the format very critical, and we seem to not be near reaching that
approach. The v2 format here is very similar to existing Git file formats
since it uses the chunk-format API. This means that the amount of code
custom to just the v2 format is quite small.

As mentioned, the current extension plan [6] only allows reftable or files
and does not allow for a mix of both. This RFC introduces the possibility
that both could co-exist. Using that multi-valued approach means that I'm
able to test the v2 packed-refs file format almost as well as the v1 file
format within this RFC. (More tests need to be added that are specific to
this format, but I'm waiting for confirmation that this is an acceptable
direction.) At the very least, this multi-valued approach could be used as a
way to allow using the reftable format as a drop-in replacement for the
packed-refs file, as well as upgrading an existing repo to use reftable.
That might even help the integration process to allow the reftable format to
be tested at least by some subset of tests instead of waiting for a full
test suite update.

Thanks for providing this background; I also like how it potentially
makes it easier to adopt reftable in the future.

I'm interested to hear from people more involved in the reftable work to see
the status of that project and how it matches or differs from my
perspective.

That wouldn't be me, but I appreciate the comparisons to help me
orient where things are.