Re: [PATCH 4/8] bundle-uri: download in creationToken order

From: Derrick Stolee <derrickstolee@github.com>
To: Victoria Dye <vdye@github.com>,
	Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com>,
	git@vger.kernel.org
Cc: gitster@pobox.com, me@ttaylorr.com, avarab@gmail.com,
	steadmon@google.com, chooglen@google.com
Subject: Re: [PATCH 4/8] bundle-uri: download in creationToken order
Date: Fri, 20 Jan 2023 09:56:50 -0500	[thread overview]
Message-ID: <1e787073-a1f6-58cd-ec5a-f99f2879624f@github.com> (raw)
In-Reply-To: <ede340d1-bce4-0c1d-7afb-4874a67d1803@github.com>

On 1/19/2023 1:32 PM, Victoria Dye wrote:> Derrick Stolee via GitGitGadget wrote:
>> +static int fetch_bundles_by_token(struct repository *r,
>> +				  struct bundle_list *list)
>> +{
>> +	int cur;
>> +	int pop_or_push = 0;
>> +	struct bundle_list_context ctx = {
>> +		.r = r,
>> +		.list = list,
>> +		.mode = list->mode,
>> +	};
>> +	struct sorted_bundle_list sorted = {
>> +		.alloc = hashmap_get_size(&list->bundles),
>> +	};
>> +
>> +	ALLOC_ARRAY(sorted.items, sorted.alloc);
>> +
>> +	for_all_bundles_in_list(list, insert_bundle, &sorted);
>> +
>> +	QSORT(sorted.items, sorted.nr, compare_creation_token);
>
> So, at this point, 'sorted' is ordered by *decreasing* creation token? With
> the loop below being somewhat complex, it would be nice to have a comment
> mention that explicitly so readers have a clear understanding of the
> "initial state" before entering the loop.

That's a good point, but also in my local version I have the following line:

	QSORT(bundles.items, bundles.nr, compare_creation_token_decreasing);

The comparison function was renamed based on Junio's feedback. After making
that change, this line is more self-documenting. Do you still think that it
needs a clarification comment if this rename occurs?

>> +	/*
>> +	 * Use a stack-based approach to download the bundles and attempt
>> +	 * to unbundle them in decreasing order by creation token. If we
>> +	 * fail to unbundle (after a successful download) then move to the
>> +	 * next non-downloaded bundle (push to the stack) and attempt
>> +	 * downloading. Once we succeed in applying a bundle, move to the
>> +	 * previous unapplied bundle (pop the stack) and attempt to unbundle
>> +	 * it again.
>> +	 *
>> +	 * In the case of a fresh clone, we will likely download all of the
>> +	 * bundles before successfully unbundling the oldest one, then the
>> +	 * rest of the bundles unbundle successfully in increasing order
>> +	 * of creationToken.
>> +	 *
>> +	 * If there are existing objects, then this process may terminate
>> +	 * early when all required commits from "new" bundles exist in the
>> +	 * repo's object store.
>> +	 */
>> +	cur = 0;
>> +	while (cur >= 0 && cur < sorted.nr) {
>> +		struct remote_bundle_info *bundle = sorted.items[cur];
>> +		if (!bundle->file) {
>> +			/* Not downloaded yet. Try downloading. */
>> +			if (download_bundle_to_file(bundle, &ctx)) {
>> +				/* Failure. Push to the stack. */
>> +				pop_or_push = 1;
>> +				goto stack_operation;
>
> Personally, I find the use of "stack" terminology more confusing than not.
> 'sorted' isn't really a stack, it's a list with fixed contents being
> traversed stepwise with 'cur'. For example, 'pop_or_push' being renamed to
> 'move_direction' or 'step' something along those lines might more clearly
> indicate what's actually happening with 'cur' & 'sorted'.

s/pop_or_push/move_direction/ makes a lot of sense.

I'll think about describing the strategy differently to avoid the "stack"
language. Mentally, I'm constructing a stack of "downloaded but unable to
unbundle bundles", but they aren't actually arranged that way in any
explicit structure. Instead, they are just the bundles in the list that
have a file but haven't been unbundled.

>> +			}
>> +
>> +			/* We expect bundles when using creationTokens. */
>> +			if (!is_bundle(bundle->file, 1)) {
>> +				warning(_("file downloaded from '%s' is not a bundle"),
>> +					bundle->uri);
>> +				break;
>> +			}
>> +		}
>> +
>> +		if (bundle->file && !bundle->unbundled) {
>> +			/*
>> +			 * This was downloaded, but not successfully
>> +			 * unbundled. Try unbundling again.
>> +			 */
>> +			if (unbundle_from_file(ctx.r, bundle->file)) {
>> +				/* Failed to unbundle. Push to stack. */
>> +				pop_or_push = 1;
>> +			} else {
>> +				/* Succeeded in unbundle. Pop stack. */
>> +				pop_or_push = -1;
>> +			}
>> +		}
>> +
>> +		/*
>> +		 * Else case: downloaded and unbundled successfully.
>> +		 * Skip this by moving in the same direction as the
>> +		 * previous step.
>> +		 */
>> +
>> +stack_operation:
>> +		/* Move in the specified direction and repeat. */
>> +		cur += pop_or_push;
>> +	}
>
> After reading through this loop, I generally understood *what* its doing,
> but didn't really follow *why* the download & unbundling is done like this.

The commit message should be updated to point to refer to the previously-
added test setup in t5558:

# To get interesting tests for bundle lists, we need to construct a
# somewhat-interesting commit history.
#
# ---------------- bundle-4
#
#       4
#      / \
# ----|---|------- bundle-3
#     |   |
#     |   3
#     |   |
# ----|---|------- bundle-2
#     |   |
#     2   |
#     |   |
# ----|---|------- bundle-1
#      \ /
#       1
#       |
# (previous commits)

And then this can be used to motivate the algorithm. Suppose we have
already downloaded commit 1 through a previous fetch. We try to download
bundle-4 first, but it can't apply because it requires commits that are
in bundle-3 _and_ bundle-2, but the client doesn't know which bundles
contain those commits. Downloading bundle-3 successfully unbundles, so a
naive algorithm would think we are "done" and expect to unbundle bundle-4.
However, that unbundling fails, so we go deeper into the list to download
bundle-2. That succeeds, and then retrying bundle-4 succeeds.

> I needed to refer back to the design doc
> ('Documentation/technical/bundle-uri.txt') to understand some basic
> assumptions about bundles:
>
> - A new bundle's creation token should always be strictly greater than the
>   previous newest bundle's creation token. I don't see any special handling
>   for equal creation tokens, so my assumption is that the sorting of the
>   list arbitrarily assigns one to be "greater" and it's dealt with that way.

Yes, the bundle provider should not have equal values unless the bundles are
truly independent. That could be clarified in that doc.

> - The bundle with the lowest creation token should always be unbundleable,
>   since it contains all objects in an initial clone.

Yes, at least it should not have any required commits.

> I do still have some questions, though:
>
> - Why would 'unbundle_from_file()' fail? From context clues, I'm guessing it
>   fails if it has some unreachable objects (as in an incremental bundle), or
>   if it's corrupted somehow.

You are correct. We assume that the data is well-formed and so the problem
must be due to required commits not already present in the local object store.

> - Why would 'download_bundle_to_file()' to fail? Unlike
>   'unbundle_from_file()', it looks like that represents an unexpected error.

Yes, that could fail for network issues such as a server error or other
network failure. In such cases, the client should expect that we will not
be able to download that bundle for the process's lifetime. We may be able
to opportunistically download other bundles, but we will rely on the Git
protocol to get the objects if the bundles fail.

These failure conditions are not tested deeply (there are some tests from
earlier series that test the behavior, but there is room for improvement).

> Also - it seems like one of the assumptions here is that, if a bundle can't
> be downloaded & unbundled, no bundle with a higher creation token can be
> successfully unbundled ('download_bundle_to_file()' sets 'pop_or_push' to
> '1', which will cause the loop to ignore all higher-token bundles and return
> a nonzero value from the function).
>
> I don't think that assumption is necessarily true, though. Suppose you have
> a "base" bundle 100 and incremental bundles 101 and 102. 101 has all objects
> from a new branch A, and 102 has all objects from a newer branch B (not
> based on any objects in A). In this case, 102 could be unbundled even if 101
> is corrupted/can't be downloaded, but we'd run into issues if we store 102
> as the "latest unbundled creation token" (because it implies that 101 was
> unbundled).

You are correct. bundle-3 can be unbundled even if bundle-2 fails in the
test example above.

> Is there any benefit to trying to unbundle those higher bundles *without*
> advancing the "latest creation token"? E.g. in my example, unbundle 102 but
> store '100' as the latest creation token?

I will need to think more about this.

Generally, most repositories that care about this will not have independent
bundles because between every bundle creation step the default branch will
advance. (Of course, exceptions can still occur, such as over weekends.)
Thus, the latest bundle will have a required commit that only exists in the
previous bundle. This algorithm and its error conditions are then looking
for ways to recover when that is not the case.

When a bundle fails to download, my gut feeling is that it is unlikely that
it was completely independent of a bundle with higher creationToken. However,
we have already downloaded that bundle and it is a very low cost to attempt
an unbundling of it.

The tricky part is that we want to avoid downloading _all_ the bundles just
because one is failing to unbundle. If a failed download would cause the top
bundle from unbundling, we don't want to go through the whole list of bundles
even though they unbundle without issue. I'm thinking specifically about the
incremental fetch case, where we don't want to blow up to a full clone worth
of downloads.

This deserves a little more attention, so I'll think more on it and get
back to you.

>>  	git -C clone-from for-each-ref --format="%(objectname)" >oids &&
>> -	git -C clone-list-http-2 cat-file --batch-check <oids
>> +	git -C clone-list-http-2 cat-file --batch-check <oids &&
>> +
>> +	for b in 1 2 3 4
>> +	do
>> +		test_bundle_downloaded bundle-$b.bundle trace-clone.txt ||
>> +			return 1
>> +	done
>
> If I understand correctly, these added conditions would have passed even if
> they were added when the test was initially created in patch 1, but they're
> added here to tie them to the implementation of the creationToken heuristic?
> Seems reasonable.

They probably should have been added in patch 1 to be clear that behavior
is not changing here.

>> +'
>> +
>> +test_expect_success 'clone bundle list (http, creationToken)' '
>
> This new test has the same name as the one above it - how does it differ
> from that one? Whatever the difference is, can that be noted somehow in the
> title or a comment?

The title should change, pointing out that the bundle list is truncated
and the rest of the clone is being fetched over the Git protocol. It will
be expanded with fetches later, I think, but it should be better motivated
in this patch, even if that is so.

>> +# Usage: test_bundle_downloaded <bundle-id> <trace-filename>
>> +test_bundle_downloaded () {
>> +	cat >pattern <<-EOF &&
>> +	"event":"child_start".*"argv":\["git-remote-https","$HTTPD_URL/$1.bundle"\]
>> +	EOF
>> +	grep -f pattern "$2"
>> +}
>
> This function is the same as the one created in 't5558'. Should it be moved
> to 'lib-bundle.sh' or 'test-lib.sh' to avoid duplicate code?

It's slightly different, but that is just because we are using the advertisement
and thus we never download a bundle-list and always download .bundle files. That
is not an important distinction and I expect to replace it with the
test_remote_https_urls() helper discussed in an earlier response.

Thanks,
-Stolee