How de-duplicate similar repositories with alternates

A co-worker asked me today how space could be saved when you have multiple checkouts of the same repository (at different revs) on the same machine. I said since these won't block-level de-duplicate well[1] one way to do this is with alternates.

However, once you have an existing clone I didn't know how to get the gains without a full re-clone, but I hadn't looked deeply into it. As it turns out I'm wrong about that, which I found when writing the following test-case which shows that it works:

    (
        cd /tmp &&
        rm -rf /tmp/git-{master,pu,pu-alt}.git &&

        # Normal clones
        git clone --bare --no-tags --single-branch --branch master https://github.com/git/git.git /tmp/git-master.git &&
        git clone --bare --no-tags --single-branch --branch pu https://github.com/git/git.git /tmp/git-pu.git &&

        # An 'alternate' clone using 'master' objects from another repo
        git --bare init /tmp/git-pu-alt.git &&
        for git in git-pu.git git-pu-alt.git
        do
            echo /tmp/git-master.git/objects >/tmp/$git/objects/info/alternates
        done &&
        git -C git-pu-alt.git fetch --no-tags https://github.com/git/git.git pu:pu

        # Respective sizes, 'alternate' clone much smaller
        du -shc /tmp/git-*.git &&

        # GC them all. Compacts the git-pu.git to git-pu-alt.git's size
        for repo in git-*.git
        do
            git -C $repo gc
        done &&
        du -shc /tmp/git-*.git

        # Add another big history (GFW) to git-{pu,master}.git (in that order!)
        for repo in $(ls -d /tmp/git-*.git | sort -r)
        do
            git -C $repo fetch --no-tags https://github.com/git-for-windows/git master:master-gfw
        done &&
        du -shc /tmp/git-*.git &&

        # Another GC. The objects now in git-master.git will be de-duped by all
        for repo in git-*.git
        do
            git -C $repo gc
        done &&
        du -shc /tmp/git-*.git
    )

This shows a scenario where we clone git.git at "master" and "pu" in different places. After clone the relevant sizes are:

    108M    /tmp/git-master.git
    3.2M    /tmp/git-pu-alt.git
    109M    /tmp/git-pu.git
    219M    total

I.e. git-pu-alt.git is much smaller since it points via alternates to git-master.git, and the history of "pu" shares most of the objects with "master". But then how do you get those gains for git-pu.git? Turns out you just "git gc"

    111M    /tmp/git-master.git
    2.1M    /tmp/git-pu-alt.git
    2.1M    /tmp/git-pu.git
    115M    total

This is the thing I was wrong about, in retrospect probably because I'd been putting PATH_TO_REPO in objects/info/alternates, but we actually need PATH_TO_REPO/objects, and "git gc" won't warn about this (or "git fsck"). Probably a good idea to patch that at some point, i.e. whine about paths in alternates that don't have objects, or at the very least those that don't exist. #leftoverbits

Then when we fetch git-for-windows:master to all the repos they all grow by the amount git-for-windows has diverged:

    144M    /tmp/git-master.git
    36M     /tmp/git-pu-alt.git
    36M     /tmp/git-pu.git
    214M    total

Note that the "sort -r" is critical here. If we fetched git-master.git first (at this point the alternate for git-pu*.git) we wouldn't get the duplication in the first place, but instead:

    144M    /tmp/git-master.git
    2.1M    /tmp/git-pu-alt.git
    2.1M    /tmp/git-pu.git
    148M    total

This shows the importance of keeping such an 'alternate' repo up-to-date, i.e. we don't get the duplication in the first place, but regardless (this from a run with sort -r) a "git gc" will coalesce them:

    131M    /tmp/git-master.git
    2.1M    /tmp/git-pu-alt.git
    2.2M    /tmp/git-pu.git
    135M    total

If you find this interesting make sure to read my https://public-inbox.org/git/87k1s3bomt.fsf@evledraar.gmail.com/ and https://public-inbox.org/git/87in7nbi5b.fsf@evledraar.gmail.com/ for the caveats, i.e. if this is something intended for users then no ref in the alternate can ever be rewound, that'll potentially result in repository corruption.

1. https://public-inbox.org/git/87bmhiykvw.fsf@evledraar.gmail.com/

On Thu, Nov 29 2018, Ævar Arnfjörð Bjarmason wrote:

Actually looking at this again the thing that may have stumped me last time is that this has a bad interaction with gc.bigPackThreshold. If you have an alternate that would otherwise house most of your objects *and* you have a pack that's larger than the gc.bigPackThreshold your mostly redundant pack won't be removed.

That's understandable in terms of implementation, but unfortunate. It would be nice if we learned some way to detect this, i.e. "I have this 10GB pack, but with this alternate I can extract this 100MB out of it and throw it away". Now we just keep the 10GB pack even if it's mostly redundant to what's in the alternate.

On Thu, Nov 29, 2018 at 7:00 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

Another way is to use git-worktree, which would solve the gc issues mentioned below?

I view alternates as a historic artefact as the deduping of objects client side can be done using worktrees, and on the serverside - I think - most of the git hosters use namespaces and put a fork network into the same repository and use pack islands.

Can you elaborate on why worktrees would not solve the problem? (I initially was hesitant to use them as I liked going into .git and tempering with files such as the config directly. But now I cannot `cd .git` any more; it turns out the advantages outweigh this corner case that I was attached to)

On Thu, Nov 29 2018, Stefan Beller wrote:

This was discussed recently on-list & I chimed in with details about that here: https://public-inbox.org/git/87po1waqyc.fsf@evledraar.gmail.com/ & https://public-inbox.org/git/87muwzc2kv.fsf@evledraar.gmail.com/

In particular the "multiple devs" use-case described in the latter E-Mail is what I have in mind. Worktrees are inherently unsuitable for that.

On Thu, Nov 29, 2018 at 9:15 PM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

Yeah, the separate ref namespace is something I would like to have on the client side too. I did consider implementing it a couple times but it's really no small task. Naively, I could achieve that pretty quick if all refs are loose, but performance would tank once the number of refs goes over say a hundred.

On Thu, Nov 29, 2018 at 10:55:49AM -0800, Stefan Beller wrote:

Nope, we definitely use alternates. The ref namespace support in Git is not nearly complete enough to run a modern hosting site; it only kicks in for upload-pack and receive-pack. Other commands (e.g., rev-list to traverse for a history-view page) have no support at all. So we share object storage, but not ref storage.

In theory the caller could namespace requests (e.g., the user asks for "foo", the web site feeds "refs/forks/$id/refs/heads/foo" to git). But any bugs are a lot more likely to lead to security problems (oops, you accidentally wrote into somebody else's fork!). And ref storage has traditionally been a sore point for scaling, so giving each fork its own repo and refs helps break that up.

By contrast, object storage is pretty easy to share. It scales reasonably well, and the security model is much simpler due to the immutable nature of object names.

-Peff

On 12/4/2018 2:06 AM, Jeff King wrote:

And for the client side, we use alternates as an important way to scale VFS for Git to multiple enlistments on the same machine. VFS for Git manages a "shared object cache" (the alternate) that is updated in the background (including multi-pack-index and commit-graph).

Using worktrees for the same effect would add complications to the user interactions, not only when creating an enlistment but the fact that two enlistments cannot check out the same ref will confuse users.

Thanks, -Stolee

On Thu, Nov 29, 2018 at 03:59:26PM +0100, Ævar Arnfjörð Bjarmason wrote:

We do complain about missing directories; see alt_odb_usable(). Pointing to a real directory that doesn't happen to contain any objects is harder. If there are no loose objects, there might not be any hashed object directories. For a "real" object database, there should always be a "pack/" directory. But technically the object storage directory does not even need to have that; it can just be a directory full of loose objects that happens not to have any at this moment.

That said, I suspect if we issued a warning for "woah, it looks like this doesn't have any objects in it, nor does it even have a pack directory" that nobody would complain.

-Peff

On Tue, Dec 04 2018, Jeff King wrote:

Yeah, although see my <87sgzjyif2.fsf@evledraar.gmail.com>, I also ran into a different issue.

I think a warning (or even error) like this would be more useful:

    test ! -d $objdir && error... # current behavior
    test -d $objdir/objects && error "Did you mean $objdir/objects, silly?" # new error

I.e. I suspect I'm not the only one who's not read the documentation carefully enough and thought it was a path to the root of the repo and wondered why it silently didn't work.

Add a test for the error() case in alt_odb_usable() where an alternate directory doesn't exist. This behavior has been the same since 26125f6b9b ("detect broken alternates.", 2006-02-22), but if that error() was turned into die() the entire test suite would still pass.

Perhaps we should die() in that case, but let's start by adding a test here to assert the long-standing existing behavior.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 t/t5613-info-alternate.sh | 7 +++++++
 1 file changed, 7 insertions(+)

Add a test for the error() case in alt_odb_usable() where an alternate directory doesn't exist. This behavior has been the same since 26125f6b9b ("detect broken alternates.", 2006-02-22), but if that error() was turned into die() the entire test suite would still pass.

Perhaps we should die() in that case, but let's start by adding a test here to assert the long-standing existing behavior.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---

Unchanged from a 3-part series I submitted in December: https://public-inbox.org/git/20181204132716.19208-1-avarab@gmail.com/

Part of trying to re-submit the uncontentious parts of whatever I've submitted in the past that I have stalled for whatever reason...

 t/t5613-info-alternate.sh | 7 +++++++
 1 file changed, 7 insertions(+)

On Thu, Mar 28, 2019 at 09:04:56PM +0100, Ævar Arnfjörð Bjarmason wrote:

I think if anything we might go the other direction, and downgrade the error() to a warning() or even omit it entirely. It's not an error to have a missing or transient alternate. Unless of course it has objects you need, but then those generate their own errors.

I actually think in an ideal world we wouldn't say anything at all about alternates which aren't present, don't appear to contain objects, etc, on their own. And then when we hit an error because an object is missing, only _then_ diagnose and say "hey, you have this alternate but it doesn't have anything in it. Maybe that's an error?". Doing that diagnosis in the error path helps in two ways:

  - we don't have to worry about it being slow

  - we can be a bit more loose about things that _might_ be an issue.
    E.g., it's not an error to point to an alternate directory that has
    no files in it. It might be a misconfiguration, or it might just not
    have any objects right now. It's hard to justify complaining about
    it in _every_ git command that loads alternates. But after hitting a
    fatal error due to a missing object, it seems like a convenient
    thing to mention to the user.

I suspect that implementing it that way might be a pain, though. Even if we had a convenient diagnose_missing_object() one-liner, there are probably dozens of separate places it would need to be called from.

All that said, I don't really have an objection against this patch, since it's just testing the current behavior. Anybody who wants to change it would find it pretty easy to tweak this test, too.

-Peff

On Fri, Mar 29 2019, Jeff King wrote:

Yeah that sounds fine. FWIW it's just an "error" in the sense of being printed out by error(), but we proceed, so it's really a warning, sort-of.

Yup. Just wanted to get the patch to test what we do *currently* out, might loop back to finishing up the rest of this.

On Fri, Mar 29 2019, Ævar Arnfjörð Bjarmason wrote:

Junio: *ping* about picking up this trivial test coverage improvement
(missed in the latest What's Cooking).

Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:

I was waiting for you to make up your mind about your earlier "might loop back to finishing up". For a topic like this, for which the ball has been in your court for a long time, just resending would be easier to handle than pinging, as I do not remember much about the original attempt anyway ;-)

On Tue, Apr 09 2019, Junio C Hamano wrote:

I don't know when I'll get to finishing the rest of it.

I'll leave it up to you if you want to queue just the test patch or drop it. I figured I'd re-send just that since I figured just fixing the blindspot of the current behavior would be a good thing on its own, not as an endorsement of the current behavior, just a "this is the current known behavior" regression test.

Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:

As I said in a separate message, I think it is good to make sure that fsck does not crash. I do not think it is good to grep in its output.

If the behaviour is undesirable one, we could document the current "breakage" with "test_expect_failure", whether we plan to fix it immediately. It is OK if readers cannot tell between a bug that is expected to stay forever with us, or a bug that somebody is actively working on.

But unfortunately, there is no separate "test_merely_documenting", that is different from "test_expect_success", so even if we claim "this is not an endorsement, but is merely documenting the current behaviour" when we add such a test, there is no way for future readers to tell between the two, short of going back to "git blame" and seeing the log message.

For that reason, I do not think it is a good practice to document the "current behaviour that happens to be" the same way as "the behaviour we desire" in test_expect_success.

On Tue, Apr 09, 2019 at 06:43:41PM +0900, Junio C Hamano wrote:

FWIW, that approach (and your rationale below) makes a lot of sense to me for this case.

-Peff

Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:

I went back to the original thread to see what the patch was about.

I actually am fairly negative on casting the current behaviour in stone for this one. Isn't the current status something like: we notice that we say 'error', we suspect that we would want to demote it to 'warning' or even silence, but this is not too pressing and it is OK as long as we do not make things worse by turning it into a more severe error.

I do not mind if the last "look in stderr" step did not exist, though. It is good to make sure that fsck does not die when it sees a non-existing directory listed in the alternates file.

This adds a warning for the issue discussed upthread. As noted in these patches we've been emitting an "error" while not impacting the exit code, should we die() instead? Maybe, but until there's consensus on that let's change this to warning() while we're at it.

Ævar Arnfjörð Bjarmason (3):
  sha1-file: test the error behavior of alt_odb_usable()
  sha1-file: emit error if an alternate looks like a repository
  sha1-file: change alternate "error:" message to "warning:"

 sha1-file.c               | 16 ++++++++++++----
 t/t5613-info-alternate.sh | 21 +++++++++++++++++++++
 2 files changed, 33 insertions(+), 4 deletions(-)

Since 26125f6b9b ("detect broken alternates.", 2006-02-22) we've emitted an error if the alternates directory doesn't exist, but not for the common misstep of adding a path to another git repository as an alternate, as opposed to its "objects" directory.

Let's check for this, i.e. whether X/objects or X/.git/objects exists if the user supplies X and print an error (which as a commit leading up to this one shows doesn't change the exit code, just "warns").

This check is intentionally not implemented by e.g. requiring that any of X/?? exists or X/info or X/pack exists. It's a legitimate use-case to point to an existing alternate that hasn't been populated yet, but pointing to one where an "X/objects" or "X/.git/objects" directory exists is definitely a mistake we should warn the user about.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 sha1-file.c               | 10 +++++++++-
 t/t5613-info-alternate.sh | 14 ++++++++++++++
 2 files changed, 23 insertions(+), 1 deletion(-)

Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:

I agree that "Let's check for this" is a good idea, but do not necessarily agree with "i.e.". Don't we have a helper that takes the path to an existing directory and answers "Yup, it does look like a Git repository"? Using that is a lot more in line with what you claimed to do in the title for this patch.

I haven't read 3/3 yet, but as I said, I suspect it is reasonable to DWIM and use the object store associated with the directory we found to be a repository.

On Wed, Dec 05, 2018 at 12:35:08PM +0900, Junio C Hamano wrote:

Hmm. Yeah, one case this does not handle is when ".git" is a git-file pointing elsewhere, which should trigger the condition, too.

I think we can afford to be a bit loose with this check if it's just generating a warning for a case that would otherwise not work (and the worst is that we might fail to correctly diagnose a broken setup). But that I think points to another issue: this kicks in even if the path is otherwise usable.

So if had, say, a git repository whose worktree was full of objects and packfiles, it currently works for me to point to that as an alternate. But after this patch, we'd complain "wait, this looks like a git repo!".

So I'd much rather see the logic check first for something usable, and only when we fail to find it, start doing a loose diagnosis. Something like:

  if !is_directory($path)
	complain that it does not exist, as now
  else if !is_directory($path/pack)
	/*
	 * it doesn't look like an object directory; technically it
	 * _could_ just have loose objects, and maybe we ought to check
	 * for directories matching [0-9a-f]{2}, though it seems
	 * somewhat unlikely these days.
	 */
	if is_directory($path/objects) || exists($path/.git)
		complain that it looks like a git dir
	else
		complain that it doesn't look like an object dir
  fi

Hmm. I managed to write a gross mix of C and shell for my pseudocode, but hopefully you can read it. ;)

Yeah, I'm tempted by that, too, though I worry about corner cases. How much effort should we put into discovery? I guess the rules from enter_repo() would make sense, though the logic in that function would need some refactoring to be reused elsewhere.

-Peff

Change the "error" message emitted by alt_odb_usable() to be a "warning" instead. As noted in commits leading up to this one this has never impacted the exit code ever since the check was initially added in 26125f6b9b ("detect broken alternates.", 2006-02-22).

It's confusing to emit an "error" when e.g. "git fsck" will exit with 0, so let's emit a "warning:" instead.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 sha1-file.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:

OK, that sounds sensible. An alternative that may be more sensible is to actually diagnose this as an error, but the purpose of this message is to help users diagnose a possible misconfiguration and keeping the repository "working" with the remaining set of object stores by leaving it as a mere warning, like this patch does, is probably a better approach.

On Wed, Dec 05, 2018 at 12:37:58PM +0900, Junio C Hamano wrote:

Yeah, I think it's better to keep it as a warning. It's actually reasonably likely to be benign (e.g., you did a "git repack -ad && rm /path/to/alternate" to remove the dependency, but forgot to clean up the alternates). And when it _is_ a problem, the object-reading code paths will definitely let you know.

-Peff

Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:

If it is an error common enough, perhaps we could even DWIM it, I guess, that is...

	if test ! -d $objdir
	then
		error
	elif test -d $objdir/objects/pack
	then
		possibly warn
		objdir=$objdir/objects
	fi

On Thu, Nov 29 2018, Ævar Arnfjörð Bjarmason wrote:

Maybe this is useful to someone. Here's a cronjob I wrote since I wrote this thread that runs in daily cron on some of our systems.

It expects repositories in /var/lib/git_tree-for-alternates like /var/lib/git_tree-for-alternates/git/git.git to exist, then scours /home and /etc/puppet/environments (which we had a lot of) for "config" files with the string in git/git (this saves us some work) and then tries to find a git repository relative to that "config" file with "rev-parse --absolute-git-dir".

If there is one, we check if the repository has a SHA-1 that the history of our /var/lib/git_tree-for-alternates/git/git.git started with (if >1 we pick the oldest), if so this is a repository that can benefit from using /var/lib/git_tree-for-alternates/git/git.git/objects as an alternate, and we add the appropriate alternate info, unset gc.bigPackThreshold so GC will actually do its work, and run "git gc" sudo'd as the the user who owns the thing.

One one server the .git directories in /home went from ~2TB to ~100GB using this script. On another from ~250G to ~5G. The leftover space spent is the commit-grah (not de-duped like objects are), and whatever accumulated divergence (topic branches mainly) exist in those repos different than what the alternate store has in the HEAD branch.

#!/bin/bash

set -euo pipefail

ALTERNATES_STORE=/var/lib/git_tree-for-alternates

if ! test -d $ALTERNATES_STORE
then
    echo 'We have no alternates repositories here to point to!' >&2
    exit 0
fi

find_owning_user() {
    path=$1
    case $path in
        /home/*|/etc/puppet/environments/*)
            who=$(echo $path | perl -pe 's[^
                (?:
                    /home
                    |
                    /etc/puppet/environments
                )
                /
                ([^/]+)
                /
                .*
            ][$1]gx')
            if getent passwd $who >/dev/null
            then
                echo $who
            else
                echo "Know how to get user from path '$path', but '$who' is not a valid user!" >&2
            fi
            ;;
        *)
            echo "Don't know how to get user from path '$path' yet!" >&2
            ;;
    esac
}

find $ALTERNATES_STORE -type d -name '*.git' -printf "%P\n" |
while read alternate
do
    alternate_no_git=$(echo $alternate | sed 's/\.git//')
    ALTERNATES_STORE_OBJECTS=$ALTERNATES_STORE/$alternate/objects

    # If these repositories we're finding don't share a root commit
    # with the repo we have this is not going to work and we have the
    # wrong match. Note that we can have more than one root commit
    # and try to find the oldest one. Pretty sure bet that that's
    # the "real" root.
    root_commit=$(git -C $ALTERNATES_STORE/$alternate log --max-parents=0 --date-order --reverse --pretty=format:%H | head -n 1)
    echo "> Finding repositories on the system that share the $root_commit commit with $alternate" >&2

    find \
        /home \
        $(if test -d /etc/puppet/environments; then echo /etc/puppet/environments; fi) \
        -type f -name 'config' -exec grep -Hl $alternate_no_git {} \; 2>/dev/null |
    while read config
    do
        dirname=$(dirname $config)
        echo ">> Checking if $dirname is in a $alternate git repository..." >&2
        if git_dir=$(git -C $dirname rev-parse --absolute-git-dir) &&
                git -C $git_dir cat-file -e $root_commit
        then
            echo ">>> ...Yes it was, at $git_dir" >&2
            echo ">>>> Is it already migrated?..." >&2
            if test -e $git_dir/objects/info/alternates &&
                    grep -x -F -q $ALTERNATES_STORE_OBJECTS $git_dir/objects/info/alternates
            then
                echo ">>>> ...yes, nothing to do here" >&2
                continue
            else
                echo ">>>> ...no, doing migration" >&2

                who=$(find_owning_user $git_dir)
                if test -z "$who"
                then
                    echo ">>>>> unable to find who owns $git_dir" >&2
                    continue
                else
                    echo ">>>>> found that $who owns $git_dir" >&2
                fi

                if test "$DRY_RUN" = "1"
                then
                    echo ">>>>>> Would have ran commands migrating $git_dir"
                else
                    if ! sudo -u $who stat $git_dir >/dev/null 2>&1
                    then
                        echo ">>>>>> The '$who' user can't access his own '$git_dir'. Could be e.g. ex-employee. Using 'root'"
                        who=root
                    fi

                    echo ">>>>>> Migrating $git_dir is now $(sudo -u $who du -sh $git_dir | cut -f1)"
                    sudo -u $who git -C $git_dir config gc.bigPackThreshold 0
                    echo $ALTERNATES_STORE_OBJECTS | sudo tee -a $git_dir/objects/info/alternates >/dev/null
                    sudo -u $who git -C $git_dir gc
                    echo ">>>>>> Migrated $git_dir is now $(sudo -u $who du -sh $git_dir | cut -f1)"
                fi
            fi
        else
            echo ">>> No it isn't. Skipping it" >&2
            continue
        fi
    done
done

On 12/4/2018 8:35 AM, Ævar Arnfjörð Bjarmason wrote:

The commit-graph could be shared, as the commits in each enlistment can be parsed from local with GENERATION_NUMBER_INFINITY, giving us similar speedups.

The issue is: who updates the file? As the commit-graph gets behind, performance will degrade. But it seems like you'd need similar maintenance on the alternate object store, anyway.

Thanks, -Stolee