repository: Use heuristic to prune objects in OptimizeRepository

While we now try to do incremental repacks when we determine that a
repository has too many loose objects, it could be that those loose
objects are in fact unreachable objects which won't ever get written
into a packfile. As a consequence, we'd try to repack repositories every
time because the number of loose objects never goes down. This isn't
much of a problem: git-repack(1) would exit rather fast in this case.
But it's a shortcoming of the way OptimizeRepository is implemented.

Introduce a new heuristic which prunes unreachable objects when there
are still too many objects after having packed the repository, using
the exact same logic we also use for incremental repacks. If we have
more than this number of objects then we'll try to prune objects.

Note that git-prune(1) has a two-week grace period before deleting
unreachable objects. This guards us against accidentally corrupting the
repository in case concurrently running Git commands still refer to the
objects that are unreachable, even though no reference point to them
anymore. Furthermore, it allows us to restore objects during that grace
period, if required.

There is one exception to this new heuristic: when OptimizeRepository is
executed on an object pool we don't ever want to prune objects, so we
exit early in case we see that it is one. This is a hard requirement
right now: object pools don't have the full view of all referenced
objects for all pool members, so it could be that objects in the pool
are unreachable via its current set of references, but any other member
still requires them. While this shouldn't ever happen because we create
keep-alive references to retain unreachable objects in pools, it is both
safer and also more performant to skip pruning because it should in
theory never prune any objects anyway.

Changelog: changed

3 files changed, 157 insertions, 1 deletions

diff --git a/internal/git/command_description.go b/internal/git/command_description.go
index d4d5ec82d..a1a33c037 100644
--- a/internal/git/command_description.go
+++ b/internal/git/command_description.go
@@ -176,6 +176,9 @@ var commandDescriptions = map[string]commandDescription{
 	"pack-objects": {
 		flags: scNoRefUpdates | scGeneratesPackfiles,
 	},
+	"prune": {
+		flags: scNoRefUpdates,
+	},
 	"push": {
 		flags: scNoRefUpdates,
 		opts: []GlobalOption{
diff --git a/internal/gitaly/service/repository/optimize.go b/internal/gitaly/service/repository/optimize.go
index cc61d30c2..3d8f10891 100644
--- a/internal/gitaly/service/repository/optimize.go
+++ b/internal/gitaly/service/repository/optimize.go
@@ -10,6 +10,7 @@ import (
 	"strings"
 
 	"github.com/grpc-ecosystem/go-grpc-middleware/logging/logrus/ctxlogrus"
+	"gitlab.com/gitlab-org/gitaly/v14/internal/git"
 	"gitlab.com/gitlab-org/gitaly/v14/internal/git/housekeeping"
 	"gitlab.com/gitlab-org/gitaly/v14/internal/git/localrepo"
 	"gitlab.com/gitlab-org/gitaly/v14/internal/git/stats"
@@ -17,6 +18,12 @@ import (
 	"gitlab.com/gitlab-org/gitaly/v14/proto/go/gitalypb"
 )
 
+const (
+	// looseObjectLimit is the limit of loose objects we accept both when doing incremental
+	// repacks and when pruning objects.
+	looseObjectLimit = 1024
+)
+
 func (s *server) OptimizeRepository(ctx context.Context, in *gitalypb.OptimizeRepositoryRequest) (*gitalypb.OptimizeRepositoryResponse, error) {
 	if err := s.validateOptimizeRepositoryRequest(in); err != nil {
 		return nil, err
@@ -47,6 +54,7 @@ func (s *server) validateOptimizeRepositoryRequest(in *gitalypb.OptimizeReposito
 func (s *server) optimizeRepository(ctx context.Context, repo *localrepo.Repo) error {
 	optimizations := struct {
 		PackedObjects bool `json:"packed_objects"`
+		PrunedObjects bool `json:"pruned_objects"`
 	}{}
 	defer func() {
 		ctxlogrus.Extract(ctx).WithField("optimizations", optimizations).Info("optimized repository")
@@ -62,6 +70,12 @@ func (s *server) optimizeRepository(ctx context.Context, repo *localrepo.Repo) e
 	}
 	optimizations.PackedObjects = didRepack
 
+	didPrune, err := pruneIfNeeded(ctx, repo)
+	if err != nil {
+		return fmt.Errorf("could not prune: %w", err)
+	}
+	optimizations.PrunedObjects = didPrune
+
 	return nil
 }
 
@@ -199,7 +213,7 @@ func needsRepacking(repo *localrepo.Repo) (bool, repackCommandConfig, error) {
 	//
 	// In our case we typically want to ensure that our repositories are much better packed than
 	// it is necessary on the client side. We thus take a much stricter limit of 1024 objects.
-	if looseObjectCount > 1024 {
+	if looseObjectCount > looseObjectLimit {
 		return true, repackCommandConfig{
 			fullRepack:  false,
 			writeBitmap: false,
@@ -283,3 +297,40 @@ func estimateLooseObjectCount(repo *localrepo.Repo) (int64, error) {
 	// Scale up found loose objects by the number of sharding directories.
 	return looseObjects * 256, nil
 }
+
+// pruneIfNeeded removes objects from the repository which are either unreachable or which are
+// already part of a packfile. We use a grace period of two weeks.
+func pruneIfNeeded(ctx context.Context, repo *localrepo.Repo) (bool, error) {
+	// Pool repositories must never prune any objects, or otherwise we may corrupt members of
+	// that pool if they still refer to that object.
+	if strings.HasPrefix(repo.GetRelativePath(), "@pools") {
+		return false, nil
+	}
+
+	looseObjectCount, err := estimateLooseObjectCount(repo)
+	if err != nil {
+		return false, fmt.Errorf("estimating loose object count: %w", err)
+	}
+
+	// We again use the same limit here as we do when doing an incremental repack. This is done
+	// intentionally: if we determine that there's too many loose objects and try to repack, but
+	// all of those loose objects are in fact unreachable, then we'd still have the same number
+	// of unreachable objects after the incremental repack. We'd thus try to repack every single
+	// time.
+	//
+	// Using the same limit here doesn't quite fix this case: the unreachable objects would only
+	// be pruned after a grace period of two weeks. But at least we know that we will eventually
+	// prune up those unreachable objects, at which point we won't try to do another incremental
+	// repack.
+	if looseObjectCount <= looseObjectLimit {
+		return false, nil
+	}
+
+	if err := repo.ExecAndWait(ctx, git.SubCmd{
+		Name: "prune",
+	}); err != nil {
+		return false, fmt.Errorf("pruning objects: %w", err)
+	}
+
+	return true, nil
+}
diff --git a/internal/gitaly/service/repository/optimize_test.go b/internal/gitaly/service/repository/optimize_test.go
index 701f30fd7..e09cf2a18 100644
--- a/internal/gitaly/service/repository/optimize_test.go
+++ b/internal/gitaly/service/repository/optimize_test.go
@@ -503,6 +503,108 @@ func TestNeedsRepacking(t *testing.T) {
 	}
 }
 
+func TestPruneIfNeeded(t *testing.T) {
+	t.Parallel()
+
+	ctx := testhelper.Context(t)
+	cfg, _ := setupRepositoryServiceWithoutRepo(t)
+
+	for _, tc := range []struct {
+		desc          string
+		isPool        bool
+		looseObjects  []string
+		expectedPrune bool
+	}{
+		{
+			desc:          "no objects",
+			looseObjects:  nil,
+			expectedPrune: false,
+		},
+		{
+			desc: "object not in 17 shard",
+			looseObjects: []string{
+				filepath.Join("ab/12345"),
+			},
+			expectedPrune: false,
+		},
+		{
+			desc: "object in 17 shard",
+			looseObjects: []string{
+				filepath.Join("17/12345"),
+			},
+			expectedPrune: false,
+		},
+		{
+			desc: "objects in different shards",
+			looseObjects: []string{
+				filepath.Join("ab/12345"),
+				filepath.Join("cd/12345"),
+				filepath.Join("12/12345"),
+				filepath.Join("17/12345"),
+			},
+			expectedPrune: false,
+		},
+		{
+			desc: "boundary",
+			looseObjects: []string{
+				filepath.Join("17/1"),
+				filepath.Join("17/2"),
+				filepath.Join("17/3"),
+				filepath.Join("17/4"),
+			},
+			expectedPrune: false,
+		},
+		{
+			desc: "exceeding boundary should cause repack",
+			looseObjects: []string{
+				filepath.Join("17/1"),
+				filepath.Join("17/2"),
+				filepath.Join("17/3"),
+				filepath.Join("17/4"),
+				filepath.Join("17/5"),
+			},
+			expectedPrune: true,
+		},
+		{
+			desc:   "exceeding boundary on pool",
+			isPool: true,
+			looseObjects: []string{
+				filepath.Join("17/1"),
+				filepath.Join("17/2"),
+				filepath.Join("17/3"),
+				filepath.Join("17/4"),
+				filepath.Join("17/5"),
+			},
+			expectedPrune: false,
+		},
+	} {
+		t.Run(tc.desc, func(t *testing.T) {
+			relativePath := gittest.NewRepositoryName(t, true)
+			if tc.isPool {
+				relativePath = gittest.NewObjectPoolName(t)
+			}
+
+			repoProto, repoPath := gittest.CreateRepository(ctx, t, cfg, gittest.CreateRepositoryConfig{
+				RelativePath: relativePath,
+			})
+			repo := localrepo.NewTestRepo(t, cfg, repoProto)
+
+			for _, looseObjectPath := range tc.looseObjects {
+				looseObjectPath := filepath.Join(repoPath, "objects", looseObjectPath)
+				require.NoError(t, os.MkdirAll(filepath.Dir(looseObjectPath), 0o755))
+
+				looseObjectFile, err := os.Create(looseObjectPath)
+				require.NoError(t, err)
+				testhelper.MustClose(t, looseObjectFile)
+			}
+
+			didPrune, err := pruneIfNeeded(ctx, repo)
+			require.Equal(t, tc.expectedPrune, didPrune)
+			require.NoError(t, err)
+		})
+	}
+}
+
 func TestEstimateLooseObjectCount(t *testing.T) {
 	t.Parallel()