Re: [PATCH 03/10] builtin/pack-objects.c: learn '--assume-kept-packs-closed'

Taylor Blau [off-list ref] writes:

Teach pack-objects an option to imply the revision machinery's new
'--no-kept-objects' option when doing a reachability traversal.

When '--assume-kept-packs-closed' is given as an argument to
pack-objects, it behaves differently (i.e., passes different options to
the ensuing revision walk) depending on whether or not other arguments
are passed:

  - If the caller also specifies a '--keep-pack' argument (to mark a
    pack as kept in-core), then assume that this combination means to
    stop traversal only at in-core packs.

  - If instead the caller passes '--honor-pack-keep', then assume that
    the caller wants to stop traversal only at packs with a
    corresponding .keep file (consistent with the original meaning which
    only refers to packs with a .keep file).

  - If both '--keep-pack' and '--honor-pack-keep' are passed, then
    assume the caller wants to stop traversal at either kind of kept
    pack.

If there is an out-of-band guarantee that .kept packs won't refer to
outside world, then we can obtain identical results to what existing
--honor-pack-keep (which traverses everything and then filteres out
what is in .keep pack) does by just stopping traversal when we see
an object that is found in a .keep pack.  OK, I guess that it
answers the correctness question I asked about [02/10].

It still is curious how we can safely "assume", but presumably we
will see how in a patch that appears later in the series.

How "closed" are these kept packs supposed to be?  When there are
two .keep packs, should objects in each of the packs never refer to
outside their own pack, or is it OK for objects in one kept pack to
refer to another object in the other kept pack?  Readers and those
who want to understand and extend this code in the future would need
to know what definition of "closed" you are using here.

Thanks.

On Thu, Jan 28, 2021 at 07:21:09PM -0800, Junio C Hamano wrote:

Taylor Blau [off-list ref] writes:

quoted

Teach pack-objects an option to imply the revision machinery's new
'--no-kept-objects' option when doing a reachability traversal.

When '--assume-kept-packs-closed' is given as an argument to
pack-objects, it behaves differently (i.e., passes different options to
the ensuing revision walk) depending on whether or not other arguments
are passed:

  - If the caller also specifies a '--keep-pack' argument (to mark a
    pack as kept in-core), then assume that this combination means to
    stop traversal only at in-core packs.

  - If instead the caller passes '--honor-pack-keep', then assume that
    the caller wants to stop traversal only at packs with a
    corresponding .keep file (consistent with the original meaning which
    only refers to packs with a .keep file).

  - If both '--keep-pack' and '--honor-pack-keep' are passed, then
    assume the caller wants to stop traversal at either kind of kept
    pack.

If there is an out-of-band guarantee that .kept packs won't refer to
outside world, then we can obtain identical results to what existing
--honor-pack-keep (which traverses everything and then filteres out
what is in .keep pack) does by just stopping traversal when we see
an object that is found in a .keep pack.  OK, I guess that it
answers the correctness question I asked about [02/10].

It still is curious how we can safely "assume", but presumably we
will see how in a patch that appears later in the series.

I think this would generally happen if the .keep packs are generated
using something like "git repack -a", which packs everything reachable
together. So if you do:

  git repack -ad
  touch .git/objects/pack/pack-whatever.keep
  ... some more packs come in, perhaps via pushes ...
  # imagine repack knew how to pass this along...
  git repack -a --assume-kept-packs-closed

then you'd repack just the objects that aren't in the big pack.

(And other kept packs; this probably would not want to be used with
.keep packs, since those can be racily created by receive-pack. Rather
you'd want to say "consider this specific list of packs to be closed and
kept").

It is dangerous, though. If your assumption is somehow wrong, then you'd
potentially corrupt the repository (because you'd stop traversing, but
perhaps delete a pack that contained a useful object you would have
reached that you don't have elsewhere).

The overall goal here is being able to roll up loose objects and smaller
packs without having to pay the cost of a full reachability traversal
(which can take several minutes on large repositories). Another
very-different direction there is to just enumerate those objects
without respect to reachability, stick them in a pack, and then delete
the originals. That does imply something like "repack -k", though, and
interacts weirdly with letting unreachable objects age out via their
mtimes (we'd constantly suck them back into fresh packs).

That would work better if we our unreachable "aging out" storage was
marked as such (say, in a pack marked with a ".cruft" file, rather than
just a regular loose object that might be new or might be cruft). Then a
roll-up repack would leave cruft packs alone (neither rolling them up,
nor deleting them). A "real" repack would eventually delete them, but
only after having done an actual reachability traversal, which make sure
there are no objects within them that need rescued.

How "closed" are these kept packs supposed to be?  When there are
two .keep packs, should objects in each of the packs never refer to
outside their own pack, or is it OK for objects in one kept pack to
refer to another object in the other kept pack?  Readers and those
who want to understand and extend this code in the future would need
to know what definition of "closed" you are using here.

I think it would want to be "the set of all .keep packs is closed". In a
"roll all into one" scenario like above, there is only one .keep pack.
But in a geometric progression, that single pack which constitutes your
base set could be multiple packs (the last whole "git repack -ad", but
then a sequence of roll-ups that came on top of it).

-Peff

On Fri, Jan 29, 2021 at 02:19:25PM -0500, Jeff King wrote:

The overall goal here is being able to roll up loose objects and smaller
packs without having to pay the cost of a full reachability traversal
(which can take several minutes on large repositories). Another
very-different direction there is to just enumerate those objects
without respect to reachability, stick them in a pack, and then delete
the originals. That does imply something like "repack -k", though, and
interacts weirdly with letting unreachable objects age out via their
mtimes (we'd constantly suck them back into fresh packs).

As I mentioned in an earlier response to Junio, this was the original
approach that I took when implementing this, but ultimately decided
against it because it means that we'll never let unreachable objects age
out (as you note).

I wonder if we need our assumption that the union of kept packs is
closed under reachability to be specified as an option. If the option is
passed, then we stop the traversal as soon as we hit an object in the
frozen packs. If not passed, then we do a full traversal but pass
--honor-pack-keep to drop out objects in the frozen packs after the
fact.

Thoughts?

I think it would want to be "the set of all .keep packs is closed". In a
"roll all into one" scenario like above, there is only one .keep pack.
But in a geometric progression, that single pack which constitutes your
base set could be multiple packs (the last whole "git repack -ad", but
then a sequence of roll-ups that came on top of it).

I don't think having a roll-up strategy of "all-except-one" simplifies
things. Or, if it does, then I don't understand it. Isn't this the exact
same thing as a geometric repack which decides to keep only one pack?

ISTM that you would be susceptible to the same problems in this case,
too.


Thanks,
Taylor

On Fri, Jan 29, 2021 at 03:01:48PM -0500, Taylor Blau wrote:

On Fri, Jan 29, 2021 at 02:19:25PM -0500, Jeff King wrote:

quoted

The overall goal here is being able to roll up loose objects and smaller
packs without having to pay the cost of a full reachability traversal
(which can take several minutes on large repositories). Another
very-different direction there is to just enumerate those objects
without respect to reachability, stick them in a pack, and then delete
the originals. That does imply something like "repack -k", though, and
interacts weirdly with letting unreachable objects age out via their
mtimes (we'd constantly suck them back into fresh packs).

As I mentioned in an earlier response to Junio, this was the original
approach that I took when implementing this, but ultimately decided
against it because it means that we'll never let unreachable objects age
out (as you note).

Right. But that's no different than using "-k" most of the time, and
then occasionally doing a more careful repack with short expiration
times and a full reachability check. As you know, this is basically what
we do at GitHub.

So it may be reasonable to go that direction, which is really defining a
totally separate strategy from git-gc's "repack, and occasionally
objects age out". Especially if we find that the
assume-kept-packs-closed route is too risky (i.e., has too many cases
where it's possible to cause corruption if our assumptions isn't met).

I'm not convinced either way at this point, but just thinking out loud
on the options (and trying to give some context to the list).

I wonder if we need our assumption that the union of kept packs is
closed under reachability to be specified as an option. If the option is
passed, then we stop the traversal as soon as we hit an object in the
frozen packs. If not passed, then we do a full traversal but pass
--honor-pack-keep to drop out objects in the frozen packs after the
fact.

Thoughts?

I'm confused. I thought the whole idea was to pass it as an option (the
user telling Git "I know these packs are supposed to be closed; trust
me")?

quoted

I think it would want to be "the set of all .keep packs is closed". In a
"roll all into one" scenario like above, there is only one .keep pack.
But in a geometric progression, that single pack which constitutes your
base set could be multiple packs (the last whole "git repack -ad", but
then a sequence of roll-ups that came on top of it).

I don't think having a roll-up strategy of "all-except-one" simplifies
things. Or, if it does, then I don't understand it. Isn't this the exact
same thing as a geometric repack which decides to keep only one pack?

ISTM that you would be susceptible to the same problems in this case,
too.

I wasn't trying to argue that all-except-one avoids any problems. I was
saying that the example I gave above was an all-into-one, but if you
want to extend the concept to multiple packs, it has to cover the whole
set. I.e., answering Junio's:

  > is it OK for objects in one kept pack to refer to another object in
  > the other kept pack?

with "yes".

-Peff

On Fri, Jan 29, 2021 at 03:25:37PM -0500, Jeff King wrote:

So it may be reasonable to go that direction, which is really defining a
totally separate strategy from git-gc's "repack, and occasionally
objects age out". Especially if we find that the
assume-kept-packs-closed route is too risky (i.e., has too many cases
where it's possible to cause corruption if our assumptions isn't met).

Yeah, this whole conversation has made me very nervous about using
reachability. Fundamentally, this isn't about reachability at all. The
operation is as simple as telling pack-objects a list of packs that you
do and don't want objects from, making a new pack out of that, and then
optionally dropping the packs that you rolled up.

So, I think that teaching pack-objects a way to understand a caller that
says "include objects from packs X, Y, and Z, but not if they appear in
packs A, B, or C, and also pull in any loose objects" is the best way
forward here.

Of course, you're going to be dragging along unreachable objects until
you decide to do a full repack, but I'm OK with that since we wouldn't
expect anybody to be solely relying on geometric repacks without
occasionally running 'git repack -ad'.

Junio: I don't think that you have picked this up yet, but please avoid
doing so for now, and I'll send a new series that goes in the direction
I outlined above.

Thanks,
Taylor

On Fri, Jan 29, 2021 at 05:10:20PM -0500, Taylor Blau wrote:

On Fri, Jan 29, 2021 at 03:25:37PM -0500, Jeff King wrote:

quoted

So it may be reasonable to go that direction, which is really defining a
totally separate strategy from git-gc's "repack, and occasionally
objects age out". Especially if we find that the
assume-kept-packs-closed route is too risky (i.e., has too many cases
where it's possible to cause corruption if our assumptions isn't met).

Yeah, this whole conversation has made me very nervous about using
reachability. Fundamentally, this isn't about reachability at all. The
operation is as simple as telling pack-objects a list of packs that you
do and don't want objects from, making a new pack out of that, and then
optionally dropping the packs that you rolled up.

So, I think that teaching pack-objects a way to understand a caller that
says "include objects from packs X, Y, and Z, but not if they appear in
packs A, B, or C, and also pull in any loose objects" is the best way
forward here.

Of course, you're going to be dragging along unreachable objects until
you decide to do a full repack, but I'm OK with that since we wouldn't
expect anybody to be solely relying on geometric repacks without
occasionally running 'git repack -ad'.

While writing my other response, I had some thoughts that this "dragging
along" might not be so bad.

Just to lay out the problem as I see it, if you do:

  - frequently roll up all small packs and loose objects into a new
    pack, without regard to reachability

  - occasionally run "git repack -ad" to do a real traversal

then the problem is that unreachable objects never age out:

  - a loose unreachable object starts with a recent-ish mtime

  - the frequent roll-up rolls it into a pack, freshening its mtime

  - the full "repack -ad" doesn't delete it, because its pack mtime is
    too recent. It explodes it loose again.

  - repeat forever

We know that "repack -d" is not 100% accurate because of similar "closed
under reachability" assumptions (see my other email). But it's OK,
because the worst case is an object that doesn't quite get packed yet,
not that it gets deleted.

So you could do something like:

  - roll up loose objects into a pack with "repack -d"; mostly accurate,
    but doesn't suck up unreachable objects

  - roll up small packs into a bigger pack without regard for
    reachability. This includes the pack created in the first step, but
    we know everything in it is actually reachable.

  - eventually run "repack -ad" to do a real traversal

That would extend the lifetime of unreachable objects which were found
in a pack (they get dragged forward during the rollups). But they'd
eventually get exploded loose during a "repack -ad", and then _not_
sucked back into a roll-up pack. And then eventually "repack -ad"
removes them.

The downsides are:

  - doing a separate "repack -d" plus a roll-up repack is wasted work.
    But I think they could be combined into a single step (at the cost
    of some extra complexity in the implementation).

  - using "--unpacked" still means traversing every commit. That's much
    faster than traversing the whole object graph, but still scales with
    the size of the repo, not the size of the new objects. That might be
    acceptable, though.

I do think the original problem goes away entirely if we can keep better
track of the mtimes. I.e., if we had packs marked with ".cruft" instead
of exploding loose, then the logic is:

  - roll up all loose objects and any objects in a pack that isn't
    marked as cruft (or keep); never delete a cruft pack at this stage

  - occasionally "repack -ad"; this does delete old cruft packs (because
    we'd have rescued any reachable objects they might have contained)

I'm not sure I want to block this topic on having cruft packs, though.
Of course there are tons of _other_ reasons to want them (like not
causing operational headaches when a repo's disk and inode usage grows
by 10x due to exploding loose objects). So maybe it's not a bad idea to
work on them together. I dunno.

-Peff