toolbox/update-all-config.pl: quiet means quiet

[girocco.git] / docs / technical / gc.txt

=============================
Garbage Collection in Girocco
=============================

Girocco suppresses the normal Git on-demand garbage collection that could be
triggered automatically by many Git commands.

It does this by setting the gc.auto config value to 0.  This is a good thing
because it prevents awkward and unwanted pauses during normal repository
operations.  It also prevents the standard garbage collection algorithm from
running which could potentially prune and remove objects still in use by forks.

What this means is that Girocco must schedule and perform its own garbage
collection by using lower-level (sometimes called "plumbing") Git commands to
accomplish the same thing in a non-disruptive fashion that leaves forks intact.

This file describes the approach used by Girocco to perform garbage collection
on its repositories and also discusses the pitfalls (aka race conditions)
inherently present in Git when garbage collection is performed simultaneously
with other repository-changing operations.

-----------
Git Gotchas
-----------

There are three primary gotchas in Git when preforming garbage collection
simultaneously with other repository operations:

  i) An object present in the repository (loose or packed) that is in the
     process of transitioning from being unreachable to becoming reachable
     (due to a ref change) could be removed by a simulataneous garbage
     collection that continues to see the object as unreachable due to various
     race conditions.

 ii) An incoming push that pushes a pack that already exists while garbage
     collection is in progress could result in that pack being removed even
     though it has a `.keep` file.

iii) Two (or more) simultaneous push operations combined with simultaneous
     garbage collection could result in one of the pushes failing to transfer
     all the objects required for its ref change.


Unreachable Objects
~~~~~~~~~~~~~~~~~~~

What happens in case (i) is that an object is initially unreachable, garbage
collection starts and determines that it really is unreachable and then just
before it deletes the object (or the pack containing the object), a push comes
in that uses the object -- and then garbage collection goes ahead and removes
it anyway.

This happens when incoming pushes unpack their objects and any of the objects
already exist in the repository -- in which case the same objects from the
incoming push are ignored; in an unshared repository they (or their
containing pack) should end up with a "freshened" modification time.  But all
that does is shrink the window for the race condition, not eliminate it.

This can be avoided by never unpacking incoming pushes (by setting the config
item transfer.unpackLimit to 1).  This works because the remote client that
sends the push can only see reachable objects that the server has and sends
everything that is not reachable from any of the server's refs in its push
pack.

The push pack may, indeed, contain duplicates of pre-existing unreachable
objects in the repository, but since that push pack will not be unpacked they
will be kept and even if the pre-existing unreachable duplicate objects are
removed no corruption will occur because the push pack contains those objects.

This works because the incoming push pack will be in a `.keep` state
(preventing it from being removed) until _after_ the objects in it have been
made reachable by a ref update.  But see the next section for an exception.

Girocco sets transfer.unpackLimit to 1 for exactly this reason.


Push Pack Redux
~~~~~~~~~~~~~~~

For case (ii) consider a repository with only a `master` branch with its
current tip commit at "C".  This repository has been pushed up to a server but
everything's currently quiescent.

 1. A client pushes a fast-forward to `master` containing commits "D", "E" and
    "F".

    If transfer.unpackLimit is set to 1 or the pack contains enough objects
    the push will result in a new pack on the server.  Call it pack "X".

 2. Now the client immediately decides that was a mistake and pushes a "rewind"
    of `master` back to commit "C".

    But wait, nope, that's not right after all...

 3. Meanwhile the server starts garbage collection and notices pre-existing
    pack "X".  It completes the reachability trace and determines that none of
    the objects in pack "X" are reachable but has not yet removed pack "X".

 4. The client re-pushes a fast-forward to `master` containing exactly the same
    three commits "D", "E" and "F".

    This causes exactly the same push pack that was sent with the original
    fast-forward push in (1) to be sent again.

 5. Garbage collection removes pack "X" corrupting the repository.

If the push pack gets unpacked on push (depending on the setting of
transfer.unpackLimit) then the situation just described doesn't apply and the
scenario becomes the same as explained in the previous section for case (i).

What does Git do when the same pack is pushed again?  Well, it leaves the
pre-existing pack alone (not even "freshening" it).  It will, however, create
the corresponding `.keep` file (since there would not be one for the
pre-existing pack) and then removes that `.keep` after refs have been updated.

The problem with this is `git repack -a -d`.

When a `git repack -a -d` completes it removes all packs that a) existed when
the repack started and b) did not have a `.keep` file and c) do not have the
same name as any pack(s) created by the repack operation.

The solution to this is to never, ever, ever use `git repack -a -d` when there
is a possibility of a simultaneous push operation.

Girocco does not use `git repack -a -d` for garbage collection.

(Girocco had a dubious flirtation with `-a -d` until [a7ea68a8a80e43d5][1].)

Girocco does, however, use a technique that bears some resemblance to the
mechanism that `git repack -a -d` uses in that it records the names of all
preexisting non-keep packs just before starting gc and then removes them
after gc completes (provided they have not been "freshened" in the meantime).

Girocco deals with the "Push Pack Redux" problem by renaming the preexisting
packs while collecting their names.  After the rename is complete it checks to
see if any .keep files have appeared for the original name and creates a
corresponding .keep file for the new name (and excludes it from the list).

If the rename happens in the midst of a "Push Pack Redux", only the renamed
version might be left (hence the transfer of the .keep file).  If there is
no .keep file then either no "Push Pack Redux" has started or it's already
finished its ref updates in which case it will be picked up by the future
reachability trace that hasn't started yet.

The renamed packs get an added suffix so that no incoming push can ever
possibly generate a pack name collision thereby avoiding the problem.


Simultaneous Pushes
~~~~~~~~~~~~~~~~~~~

For case (iii), consider a repository with only a `master` branch.

Client A works on a "topic" branch called `some-topic` and finally pushes it
for public inspection.  At push time it is a new branch on the server.

Client B has decided that the tip of the `master` branch needs to be dropped
(in other words `master` needs to be rewound by one commit).

 1. Client A does a fetch and verifies that the `some-topic` branch is rebased
    onto the latest `master` commit and then does a `git push` of the new
    `some-topic` branch.

    The push starts and receives the ref advertisements from the server and
    the client determines what objects it needs to send and starts building
    its pack for pushing.

 2. While Client A is building its pack for pushing, Client B pushes a rewind
    of branch `master` by one commit.  This operation completes while Client A
    is still continuing to build its pack (hey, it's a big topic branch).

 3. Now, garbage collection just happens to kick off and start its reachability
    trace.  It grabs all the refs and starts walking the DAG.  It has just
    finished determining what's unreachable but not yet removed anything.

 4. That push from Client A finally finishes computing its pack and sends it
    up and the new `some-topic` branch ref is updated.  This will work because
    even though Client B rewound `master` and Client A's push pack did not
    include that rewound and discarded commit, that commit hasn't been removed
    by garbage collection just yet so the `some-topic` ref update still
    succeeds even if it does a full connectivity check.

    No atomic ref pushing or force-with-lease options will prevent this ref
    update from occurring since the `some-topic` branch is new on the server
    and the rewind of the `master` branch has no effect on that.

 5. Now garbage collection removes the unreachable objects (another lovely
    race condition) including the rewound and discarded commit from the
    `master` branch that the new `some-topic` branch needs thereby making the
    `some-topic` branch corrupt.

Yes, a bunch of things have to happen in just the right order and at just the
right time for this to go wrong, but the race condition is there and there's
nothing that can be done to get rid of it (other than disallowing simultaneous
pushes which is not an available configuration option nor is it desirable).

The window for the race can be shrunk to a very small size, but there will
always be a moment after garbage collection does one last check to make sure
no refs have changed and it starts removing objects -- it is in that moment
that a ref can be changed to make the about-to-be-removed object reachable
again.  But then it gets removed anyway.

Girocco deals with this problem by making sure that objects stay around for
at least one day after they initially become unreachable.

It uses two mechanisms in combination to achieve this:

 1. A pre-receive hook records both the old and new hash values for all ref
    changes in a file in the `reflogs` subdirectory.  If it cannot record the
    hash values for some reason it aborts the push.  (The update.sh script does
    the same thing for mirrors to guarantee availability for ref change
    notifications.)

 2. As described later, Girocco's garbage collection consists of four phases.
    During phase II, all valid recent hashes from the `reflogs` directory are
    briefly resurrected to create a pack that contains all recently reachable
    objects that are now unreachable.

The result is that any objects that have become unreachable within the last
day are always kept during gc.  (The interval is configurable to be longer,
but is always forced to be a minimum of one day.)

This gc behavior effectively eliminates the problem provided pushes don't take
more than a day (but that time limit could easily be extended if necessary by
simply bumping up the config item from the default of one day).


Shared Repositories
~~~~~~~~~~~~~~~~~~~

Girocco keeps its Git repositories in shared mode.  In other words, the config
value core.sharedRepository is set to 1.

Unfortunately this creates issues.

Girocco runs various tasks as its "mirror" user.  These include jobd and taskd
which are together responsible for fetching new mirror updates, performing
garbage collection, cloning new repositories to be mirrored and sending out
ref change notifications.

Incoming pushes, however, run as either the web server user (for https pushes)
or one of various different ssh chroot jail users (for ssh pushes).

All three of these ("mirror" user, web server user and ssh chroot jail users)
need to be able to write to the repositories.  Hence core.sharedRepository = 1.

Regardless of the core.sharedRepository setting, Git insists on making loose
objects and pack files have file mode 0444 (readable by all, writable and
executable by none).

But this has an undesirable side effect.  Since mode 0444 files can only be
"touched" by the owner, only the initial creator of the loose object or pack
will be able to change its modification time (aka "freshen" it).

Girocco does not rely on "freshening" happening for normal Girocco operations.

However, Girocco now "tolerates" linked working trees to its repositories and
while it's not possible to eliminate the race described in (i) from occurring
when non-Girocco activities transition loose objects from unreachable to
reachable during a garbage collection, it can be minimized.

The "freshening" of loose objects (or their containing packs) plays a crucial
role in minimizing the race condition window.

For this reason, both the pre-receive hook and the garbage collection script
take great pains to make sure that loose objects and packs remain writable by
both owner and group.  By doing this the "touch"ing that happens when an object
that already exists is re-created will always effect a change in the
modification time of the files being touched thereby "freshening" them.

------------
Fork Follies
------------

Now that the simultaneous push and garbage collection are out of the way, what
about forks?

Forks use the Git alternates mechanism to borrow objects from their parent (aka
the "forkee") so they are not needlessly duplicated potentially wasting huge
amounts of space in the presence of many forks of the same large project.

The parent project has no way of knowing which, if any, of its objects are
reachable from its forks.  It could potentially discover that by doing a
reachability trace on the union of the refs from the entire set of forks of the
project, but that would be somewhat expensive and again subject to a race
condition with regard to incoming pushes during the reachability trace.

One way to prevent corruption of the forks would be to never remove any objects
at all.  Not very conducive to efficient disk space usage.

If a project has forks, during phase III of garbage collection, any objects
that are found to be unreachable and are currently in packs are repacked into
their own pack which is then hard-linked down to all child forks (but removed
from the project itself).

These special "unreachable" packs are given a unique extension and any such
packs received from a parent project are treated as .keep packs and also
hard-linked down into child forks along with any freshly generated phase III
pack.

Since Girocco garbage collection never removes loose objects but only redundant
packs this is enough to eliminate the problem.

(Loose objects are migrated into a "loose objects pack" but that pack then
remains until the following gc cycle thereby guaranteeing all loose objects a
minimum lifetime not withstanding untimely administrator intervention.)

--------------------
Linked Working Trees
--------------------

Along with the new order for garbage collection, Girocco now "tolerates" use
of linked working trees on its repositories.  Since there's little difference
between a linked working tree and a non-bare repository this could allow use
of non-bare repositories with Girocco too, but that's highly discouraged due
to the problems with pushing to a non-bare HEAD branch and shall not be
discussed any further.  ;)

(For those determined to pursue this option a `push-to-checkout` hook will
likely be required as well as setting the `receive.denyCurrentBranch` config
option along with Git version 2.4.0 or later.)

Girocco supports linked working trees by making sure that all objects reachable
from any index, ref log or detached HEAD that do not end up in the phase I pack
(and are not borrowed from an alternate) end up in the phase II pack.

Additionally, in order to minimize the window for race condition loss of
objects due to simultaneous garbage collection while, for example, creating a
new commit in a linked working tree, Girocco attempts to make sure that all
unreachable loose objects persist for at least one min_gc_interval time period.

Furthermore, if one of the redundant packs gets "freshened" during garbage
collection (which could happen during commit creation if one of the loose
objects being created already exists contained in a pack), that pack will not
be removed.  There's a very miniscule window where the check for "freshened"
packs could take place, not find any "freshened" packs, the pack gets freshened
immediately thereafter and then it gets removed anyway.

Can't be helped, Git does not have any <looseobject>.keep mechanism.  Girocco
itself avoids the problem, case (i) above, by preventing incoming pushes from
unpacking their packs.

If the miniscule race condition risk remains unacceptable, either linked
working trees must not be used, the time when Girocco garbage collection runs
must be strictly controlled or all updates must be pushed in from a clone that
does _not_ use the `--reference` mechanism to refer to the Girocco repository.

----------------------------------
Girocco Garbage Collection Process
----------------------------------

Girocco now uses the new order for garbage collection.

None of the "git gc", "git repack" or "git prune" commands are run either
directly or indirectly.  New packs are created via use of the
"git pack-objects" command.  The limited "pruning" that takes places involves
only pruning loose objects that are packed and removing redundant packs after
creating new all-in-one packs.

It is the removal of redundant packs that can permanently remove some
unreachable objects.

Girocco uses a four phase garbage collection strategy (the new order):

  I) Create a new all-in-one pack (this pack may have a bitmap)
 II) Create a pack of "recently reachable" objects and "friends"
III) Create a pack of "unreachable" objects if any child forks exist
 IV) Migrate all remaining loose objects into a pack

Phase I corresponds basically to "git repack -a".  Note that there's no
deletion or removal going on during phase I.  Non-forks will get a bitmap (with
Git v2.1.0 or later) and this pack will serve as the "virtual bundle".

Phase II became possible when Girocco started keeping a record of ref changes
in the reflogs subdirectory (the pre-receive hook and the update.sh script are
responsible for this).  We simply do another full packing after adding
temporary refs for everything in the reflogs directory (that's not too old).
In a nod to linked working trees, anything reachable from ref logs, index files
or detached HEADs is included as "friends".  By manipulating the packing
options it's easy to exclude everything that was already packed in phase I.

Phase III will be skipped unless forks are present.  One more iteration over
the same set of refs Phase II used but passing the "--keep-unreachable" option
and excluding everything packed in either phase I or phase II (or in phase III
packs hard-linked into the fork from its parent) gives us this pack.  It won't
appear in the project itself, but will be hard-linked to all immediate child
forks (along with any phase III packs from the parent) which will in turn
hard-link it (and them) down to their children, if any, when they run gc.

At this point any non-keep packs that existed prior to phase I are removed
(this includes phase III packs that had been hard-linked down from the parent).
Special techniques are used to avoid a "Push Pack Redux" race and to not remove
any packs that have been "freshened" by some kind of simultaneous non-Girocco
loose object activity.

Phase IV is accomplished simply by packing all loose objects that are not
already in a phase I or phase II pack.  Any phase III packs are deliberately
excluded here in an attempt to make sure that any unreachable loose objects
live on for at least one min_gc_interval.

A final "git prune-packed" takes care of removing loose object detritus.

Unless there's some non-Girocco activity going on (such as in a linked working
tree) or objects are being discarded (non-fast-forward ref changes or ref
deletions), phases II, III and IV will never create any packs.

Phase III packs are hard-linked all the way to the bottom of the project's
fork tree as gc progresses through the tree so that the space they occupy does
not balloon up and get multiplied by the total number of forks as it would if
they were allowed to be repacked into a new phase III pack in each fork.

While this strategy may seem complex, it:

 a) avoids ever creating loose objects for much better efficiency and speed
 b) avoids corrupting forks that use the `alternates` mechanism
 c) avoids using large amounts of disk space for packs containing mostly
    redundant objects
 d) maintains "recently become unreachable" objects long enough for meaningful
    ref change notifications
 e) presents a risk of corruption when simultaneous garbage collection occurs
    during new commit creation that's approximately the same as non-Girocco
    Git use would have

Overall this represents a huge improvement over hard-linking all the loose
object splatter created by "git repack -A -d" into child forks.

As part of this "new order," non-Girocco operations on the repository (such as
use of linked working trees) are now reluctantly "tolerated."



[1]: http://repo.or.cz/girocco.git/a7ea68a8a80e43d5
     "gc: retain recently unreferenced objects for 1 day, 2015-10-02"