Push a ref to a remote with many refs

Push a ref to a remote with many refs

[Patrick Marlier (pamarlie)]

Dear git community,

I am hitting a performance issue with "git push <remote> <refspec>".
The local repository has only few refs and the remote repository has a lot of refs (1000+) with objects unknown to the local repository.

"git push" of only one refspec takes minutes to complete. A quick analysis shows that a lot of time is spent in the client side.
A deeper analysis shows that the client receives the entire list of refs on the remote, then the client is checking in its local repository if the objects exist for all remote refs.
Since the local repository has a only few refs, most of the objects are unknown.
This issue is particularly amplified because the local repository is using many alternates. Indeed for each unknown object, git will try to find in all alternates too.

To workaround this issue, I ended up skipping the refs that are not part of the push. See patch at the end of the message.
Is this safe to do? Is there a better way to do this?

Thanks.
Have a nice day,

Author: Patrick Marlier <pamarlie@cisco.com>
Date:   Tue Aug 6 21:40:48 2019 +0200

    send-pack skip if not part of refspec

diff --git a/send-pack.c b/send-pack.c
index 34c77cbb1a..0fe899f753 100644
--- a/send-pack.c
+++ b/send-pack.c
@@ -94,7 +94,7 @@ static int pack_objects(int fd, struct ref *refs, struct oid_array *extra, struc
                feed_object(&extra->oid[i], po_in, 1);
 
        while (refs) {
-               if (!is_null_oid(&refs->old_oid))
+               if (!is_null_oid(&refs->old_oid) && !is_null_oid(&refs->new_oid))
                        feed_object(&refs->old_oid, po_in, 1);
                if (!is_null_oid(&refs->new_oid))
                        feed_object(&refs->new_oid, po_in, 0);

Re: Push a ref to a remote with many refs

[Patrick Marlier (pamarlie)]

> To workaround this issue, I ended up skipping the refs that are not part of the push. See patch at the end of the message.
> Is this safe to do? Is there a better way to do this?

Some help on this?

Thanks!
--
Pat

[PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects

[Jeff King]

On Tue, Nov 19, 2019 at 01:12:51PM +0000, Patrick Marlier (pamarlie) wrote:

> I am hitting a performance issue with "git push <remote> <refspec>".
> The local repository has only few refs and the remote repository has a
> lot of refs (1000+) with objects unknown to the local repository.
> 
> "git push" of only one refspec takes minutes to complete. A quick
> analysis shows that a lot of time is spent in the client side.
> A deeper analysis shows that the client receives the entire list of
> refs on the remote, then the client is checking in its local
> repository if the objects exist for all remote refs.

Right, this is expected. The client send-pack feeds the list of remote
objects (that it has) to pack-objects, which can then limit the size of
the packfile it sends based on what the other side has.

So the patch you showed (to skip refs that aren't part of the push)
would miss many opportunities for a smaller push. E.g., imagine I create
a new branch "topic" from the remote branch "master", and then try to
push it up. If I do not look at which objects are in "master", I'll end
up sending the whole history again, when I really just need to send the
differences between the two.

> Since the local repository has a only few refs, most of the objects
> are unknown.
>
> This issue is particularly amplified because the local repository is
> using many alternates. Indeed for each unknown object, git will try to
> find in all alternates too.

I think the patch below would help you.

-- >8 --
Subject: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects

When pushing, we feed pack-objects a list of both positive and negative
objects. The positive objects are what we want to send, and the negative
objects are what the other side told us they have, which we can use to
limit the size of the push.

Before passing along a negative object, send_pack() will make sure we
actually have it (since we only know about it because the remote
mentioned it, not because it's one of our refs). So it's expected that
some of these objects will be missing on the local side. But looking for
a missing object is more expensive than one that we have: it triggers
reprepare_packed_git() to handle a racy repack, plus it has to explore
every alternate's loose object tree (which can be slow if you have a lot
of them, or have a high-latency filesystem).

This isn't usually a big problem, since repositories you're pushing to
don't generally have a large number of refs that are unrelated to what
the client has. But there's no reason such a setup is wrong, and it
currently performs poorly.

We can fix this by using OBJECT_INFO_QUICK, which tells the lookup
code that we expect objects to be missing. Notably, it will not re-scan
the packs, and it will use the loose cache from 61c7711cfe (sha1-file:
use loose object cache for quick existence check, 2018-11-12).

The downside is that in the rare case that we race with a local repack,
we might fail to feed some objects to pack-objects, making the resulting
push larger. But we'd never produce an invalid or incorrect push, just a
less optimal one. That seems like a reasonable tradeoff, and we already
do similar things on the fetch side (e.g., when marking COMPLETE
commits).

Signed-off-by: Jeff King <peff@peff.net>
---
Interestingly, upload-pack does not use OBJECT_INFO_QUICK when it's
getting oids from the other side. But I think it could possibly benefit
in the same way. Nobody seems to have noticed. Perhaps it simply comes
up less, as servers would tend to have more objects than their clients?

 send-pack.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/send-pack.c b/send-pack.c
index 34c77cbb1a..16d6584439 100644
--- a/send-pack.c
+++ b/send-pack.c
@@ -41,7 +41,9 @@ int option_parse_push_signed(const struct option *opt,
 static void feed_object(const struct object_id *oid, FILE *fh, int negative)
 {
 	if (negative &&
-	    !has_object_file_with_flags(oid, OBJECT_INFO_SKIP_FETCH_OBJECT))
+	    !has_object_file_with_flags(oid,
+					OBJECT_INFO_SKIP_FETCH_OBJECT |
+					OBJECT_INFO_QUICK))
 		return;
 
 	if (negative)
-- 
2.24.0.716.g722aff65ed

Re: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects

[Patrick Marlier (pamarlie)]

> On Tue, Nov 19, 2019 at 01:12:51PM +0000, Patrick Marlier (pamarlie) wrote:
>> I am hitting a performance issue with "git push <remote> <refspec>".
>> The local repository has only few refs and the remote repository has a
>> lot of refs (1000+) with objects unknown to the local repository.
>> 
>> "git push" of only one refspec takes minutes to complete. A quick
>> analysis shows that a lot of time is spent in the client side.
>> A deeper analysis shows that the client receives the entire list of
>> refs on the remote, then the client is checking in its local
>> repository if the objects exist for all remote refs.

>Right, this is expected. The client send-pack feeds the list of remote
>objects (that it has) to pack-objects, which can then limit the size of
>the packfile it sends based on what the other side has.

>So the patch you showed (to skip refs that aren't part of the push)
>would miss many opportunities for a smaller push. E.g., imagine I create
>a new branch "topic" from the remote branch "master", and then try to
>push it up. If I do not look at which objects are in "master", I'll end
>up sending the whole history again, when I really just need to send the
>differences between the two.

Thanks Jeff. Indeed it makes sense.
(My very particular use-case would have a limited impact in this case)


>> Since the local repository has a only few refs, most of the objects
>> are unknown.
>>
>> This issue is particularly amplified because the local repository is
>> using many alternates. Indeed for each unknown object, git will try to
>> find in all alternates too.

> I think the patch below would help you.

I will give a try next week and I keep you posted on how it goes.

Thanks a lot for your input and the patch!

Have a nice day,
--
Pat

Re: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> I think the patch below would help you.
>
> -- >8 --
> Subject: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects
>
> When pushing, we feed pack-objects a list of both positive and negative
> objects. The positive objects are what we want to send, and the negative
> objects are what the other side told us they have, which we can use to
> limit the size of the push.
>
> Before passing along a negative object, send_pack() will make sure we
> actually have it (since we only know about it because the remote
> mentioned it, not because it's one of our refs). So it's expected that
> some of these objects will be missing on the local side. But looking for
> a missing object is more expensive than one that we have: it triggers
> reprepare_packed_git() to handle a racy repack, plus it has to explore
> every alternate's loose object tree (which can be slow if you have a lot
> of them, or have a high-latency filesystem).
>
> This isn't usually a big problem, since repositories you're pushing to
> don't generally have a large number of refs that are unrelated to what
> the client has. But there's no reason such a setup is wrong, and it
> currently performs poorly.
>
> We can fix this by using OBJECT_INFO_QUICK, which tells the lookup
> code that we expect objects to be missing. Notably, it will not re-scan
> the packs, and it will use the loose cache from 61c7711cfe (sha1-file:
> use loose object cache for quick existence check, 2018-11-12).
>
> The downside is that in the rare case that we race with a local repack,
> we might fail to feed some objects to pack-objects, making the resulting
> push larger. But we'd never produce an invalid or incorrect push, just a
> less optimal one. That seems like a reasonable tradeoff, and we already
> do similar things on the fetch side (e.g., when marking COMPLETE
> commits).
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> Interestingly, upload-pack does not use OBJECT_INFO_QUICK when it's
> getting oids from the other side. But I think it could possibly benefit
> in the same way. Nobody seems to have noticed. Perhaps it simply comes
> up less, as servers would tend to have more objects than their clients?

Makes me wonder how many times we wre bitten by the fact that
INFO_SKIP_FETCH_OBJECT does not imply INFO_QUICK.  Perhaps most of
the users of INFO_SKIP_FETCH_OBJECT wants to use INFO_FOR_PREFETCH?

cf. 31f5256c ("sha1-file: split OBJECT_INFO_FOR_PREFETCH", 2019-05-28)

>  send-pack.c | 4 +++-
>  1 file changed, 3 insertions(+), 1 deletion(-)
>
> diff --git a/send-pack.c b/send-pack.c
> index 34c77cbb1a..16d6584439 100644
> --- a/send-pack.c
> +++ b/send-pack.c
> @@ -41,7 +41,9 @@ int option_parse_push_signed(const struct option *opt,
>  static void feed_object(const struct object_id *oid, FILE *fh, int negative)
>  {
>  	if (negative &&
> -	    !has_object_file_with_flags(oid, OBJECT_INFO_SKIP_FETCH_OBJECT))
> +	    !has_object_file_with_flags(oid,
> +					OBJECT_INFO_SKIP_FETCH_OBJECT |
> +					OBJECT_INFO_QUICK))
>  		return;
>  
>  	if (negative)

Re: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects

[Jeff King]

On Sat, Nov 30, 2019 at 09:08:32AM -0800, Junio C Hamano wrote:

> > Interestingly, upload-pack does not use OBJECT_INFO_QUICK when it's
> > getting oids from the other side. But I think it could possibly benefit
> > in the same way. Nobody seems to have noticed. Perhaps it simply comes
> > up less, as servers would tend to have more objects than their clients?
> 
> Makes me wonder how many times we wre bitten by the fact that
> INFO_SKIP_FETCH_OBJECT does not imply INFO_QUICK.  Perhaps most of
> the users of INFO_SKIP_FETCH_OBJECT wants to use INFO_FOR_PREFETCH?

We seem to be discussing this about once a month lately. :)

There's some good digging by Jonathan in:

  https://public-inbox.org/git/20191011220822.154063-1-jonathantanmy@google.com/

That thread is also about this exact same spot, which is why I cc'd him
originally.

I do tend to think that QUICK ought to imply SKIP_FETCH. I'm slightly
negative on sprinkling FOR_PREFETCH everywhere, because the name implies
to me that we are telling object_info() that we are pre-fetching. Which
yes, has the effect we want, but I think is misleading. So we'd want to
change the name of the combined flag, I think, or just let QUICK imply
SKIP_FETCH and use that more thoroughly.

-Peff

Re: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects

[Jonathan Tan]

> On Sat, Nov 30, 2019 at 09:08:32AM -0800, Junio C Hamano wrote:
> 
> > > Interestingly, upload-pack does not use OBJECT_INFO_QUICK when it's
> > > getting oids from the other side. But I think it could possibly benefit
> > > in the same way. Nobody seems to have noticed. Perhaps it simply comes
> > > up less, as servers would tend to have more objects than their clients?
> > 
> > Makes me wonder how many times we wre bitten by the fact that
> > INFO_SKIP_FETCH_OBJECT does not imply INFO_QUICK.  Perhaps most of
> > the users of INFO_SKIP_FETCH_OBJECT wants to use INFO_FOR_PREFETCH?
> 
> We seem to be discussing this about once a month lately. :)
> 
> There's some good digging by Jonathan in:
> 
>   https://public-inbox.org/git/20191011220822.154063-1-jonathantanmy@google.com/
> 
> That thread is also about this exact same spot, which is why I cc'd him
> originally.
> 
> I do tend to think that QUICK ought to imply SKIP_FETCH. I'm slightly
> negative on sprinkling FOR_PREFETCH everywhere, because the name implies
> to me that we are telling object_info() that we are pre-fetching. Which
> yes, has the effect we want, but I think is misleading. So we'd want to
> change the name of the combined flag, I think, or just let QUICK imply
> SKIP_FETCH and use that more thoroughly.

If we want to make QUICK imply SKIP_FETCH but not the other way around, then
note that we'll have to make sure that we do not repeat the error that
31f5256c82 ("sha1-file: split OBJECT_INFO_FOR_PREFETCH", 2019-05-28) fixes.

As for whether we should do it in the first place, I think that having 2
orthogonal flags is clearer than having 1 that controls fetch
(SKIP_FETCH) and 1 that does both (QUICK) without any that recheck
packed, but I'm quite familiar with this part of the code, so perhaps
I'm the wrong person to ask - we should optimize for the typical Git
developer who just wants to access the object store. Judging from the
frequency in which we encounter this issue (as Peff says), maybe we
should go ahead and make QUICK imply SKIP_FETCH but not the other way
around. (It is also possible just to make both imply the other and unify
QUICK and SKIP_FETCH into one flag - I am not opposed to that - although
read my email that Peff linked to see why bidirectional implication is
correct in one sense but incorrect in another.)

Re: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects

[Junio C Hamano]

Jonathan Tan <jonathantanmy@google.com> writes:

> As for whether we should do it in the first place, I think that having 2
> orthogonal flags is clearer than having 1 that controls fetch
> (SKIP_FETCH) and 1 that does both (QUICK) without any that recheck
> packed, but I'm quite familiar with this part of the code, so perhaps
> I'm the wrong person to ask - we should optimize for the typical Git
> developer who just wants to access the object store. Judging from the
> frequency in which we encounter this issue (as Peff says), maybe we
> should go ahead and make QUICK imply SKIP_FETCH but not the other way
> around.

Thanks for thinking this through.  I am OK with that direction.

> (It is also possible just to make both imply the other and unify
> QUICK and SKIP_FETCH into one flag - I am not opposed to that -
> although read my email that Peff linked to see why bidirectional
> implication is correct in one sense but incorrect in another.)

Yup, also from the old message:

> Having said that, perhaps we should consider promisor-remote.c as
> low-level code and expect it to know that objects are fetched into a
> packfile (as opposed to loose objects), so it can safely use QUICK
> (which is documented as checking packed after packed and loose). If no
> one disagrees, I can make such a patch after jt/push-avoid-lazy-fetch is
> merged to master (as is the plan, according to What's Cooking [1]).

I agree that it makes sense to treat promisor-remote.c as the
low-level implementation detail that is allowed to be intimately
familiar with how its behaviour would interact with QUICK and
SKIP_FETCH options.

Thanks.

Re: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects

[Jonathan Nieder]

Hi,

Jeff King wrote:

> Subject: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects
>
> When pushing, we feed pack-objects a list of both positive and negative
> objects. The positive objects are what we want to send, and the negative
> objects are what the other side told us they have, which we can use to
> limit the size of the push.
>
> Before passing along a negative object, send_pack() will make sure we
> actually have it (since we only know about it because the remote
> mentioned it, not because it's one of our refs). So it's expected that
> some of these objects will be missing on the local side. But looking for
> a missing object is more expensive than one that we have: it triggers
> reprepare_packed_git() to handle a racy repack, plus it has to explore
> every alternate's loose object tree (which can be slow if you have a lot
> of them, or have a high-latency filesystem).

Nice analysis.

> This isn't usually a big problem, since repositories you're pushing to
> don't generally have a large number of refs that are unrelated to what
> the client has. But there's no reason such a setup is wrong, and it
> currently performs poorly.
>
> We can fix this by using OBJECT_INFO_QUICK, which tells the lookup
> code that we expect objects to be missing. Notably, it will not re-scan
> the packs, and it will use the loose cache from 61c7711cfe (sha1-file:
> use loose object cache for quick existence check, 2018-11-12).

On first reading, I wondered how this would interact with alternates,
since you had mentioned that checking alternates can be expensive.  Does
this go too far in that direction by treating an object as missing
whenever it's not in the local object store, even if it's available from
an alternate?

But I believe that was a misreading.  With this patch, we still do pay
the cost of checking alternates for the missing object.  The savings
is instead about having to *double* check.

Am I understanding correctly?

[...]
> Signed-off-by: Jeff King <peff@peff.net>

Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>

> ---
> Interestingly, upload-pack does not use OBJECT_INFO_QUICK when it's
> getting oids from the other side. But I think it could possibly benefit
> in the same way. Nobody seems to have noticed. Perhaps it simply comes
> up less, as servers would tend to have more objects than their clients?

I like to imagine that servers are also more likely to keep a tidy set
of packs and to avoid alternates.  But using INFO_QUICK when checking
the fetcher's "have"s does sound like a sensible change to me.

Thanks,
Jonathan

Re: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects

[Jeff King]

On Tue, Dec 03, 2019 at 07:55:22PM -0800, Jonathan Nieder wrote:

> > We can fix this by using OBJECT_INFO_QUICK, which tells the lookup
> > code that we expect objects to be missing. Notably, it will not re-scan
> > the packs, and it will use the loose cache from 61c7711cfe (sha1-file:
> > use loose object cache for quick existence check, 2018-11-12).
> 
> On first reading, I wondered how this would interact with alternates,
> since you had mentioned that checking alternates can be expensive.  Does
> this go too far in that direction by treating an object as missing
> whenever it's not in the local object store, even if it's available from
> an alternate?
> 
> But I believe that was a misreading.  With this patch, we still do pay
> the cost of checking alternates for the missing object.  The savings
> is instead about having to *double* check.
> 
> Am I understanding correctly?

Yes, we'd still look in alternates for each object before giving up. The
reason alternates are relevant is that normally if you have (say) 5
alternates, then you have to do 5 syscalls to find out whether each
alternate has an object. And alternates are more likely to be on
high-latency filesystems like NFS, which exacerbates the cost. But with
OBJECT_INFO_QUICK, we'll build an in-memory cache for each alternate
directory (as well as the main object store, of course), rather than
making one request per object.

> > Interestingly, upload-pack does not use OBJECT_INFO_QUICK when it's
> > getting oids from the other side. But I think it could possibly benefit
> > in the same way. Nobody seems to have noticed. Perhaps it simply comes
> > up less, as servers would tend to have more objects than their clients?
> 
> I like to imagine that servers are also more likely to keep a tidy set
> of packs and to avoid alternates.  But using INFO_QUICK when checking
> the fetcher's "have"s does sound like a sensible change to me.

At GitHub we do use alternates (but only one, and on the same local
disk). And our packing situation does sometimes get unwieldy. I think it
might be worth looking into, but it would be nice to have real numbers
before proceeding (likewise we've known about this spot in send-pack,
but it hadn't been expensive enough for anybody to notice; I'll be
curious to see real-world numbers from Patrick's case).

-Peff

Re: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects

[Patrick Marlier (pamarlie)]

> From: Jeff King <peff@peff.net>
> I'll be curious to see real-world numbers from Patrick's case).

Here the real-world case (40 pushes)

released
average 00:08:35.54
median 00:07:37.88
max 00:15:30.26

patched
average 00:06:45.67
median 00:05:39.57
max 00:16:15.46

Note our production is using 2.19 so I back-ported the patch (need to include 2 other patches).
It helped to improve the push duration. I know one big part is git lfs but I need to check what are the other bottlenecks.

Thanks a lot for the help.
--
Pat

Re: [PATCH] send-pack: use OBJECT_INFO_QUICK to check negative objects

[Jeff King]

On Tue, Dec 10, 2019 at 04:16:40PM +0000, Patrick Marlier (pamarlie) wrote:

> > From: Jeff King <peff@peff.net>
> > I'll be curious to see real-world numbers from Patrick's case).
> 
> Here the real-world case (40 pushes)
> 
> released
> average 00:08:35.54
> median 00:07:37.88
> max 00:15:30.26
> 
> patched
> average 00:06:45.67
> median 00:05:39.57
> max 00:16:15.46
> 
> Note our production is using 2.19 so I back-ported the patch (need to
> include 2 other patches).

You may see much better performance if you move to 2.21 or higher, or
backport the topic from 3b2f8a02fa (Merge branch 'jk/loose-object-cache',
2019-01-04). That would cause most of your negative lookups to not touch
the filesystem at all.

-Peff