Merge branch 'repack-delta-islands' into 'master'

Use delta islands in RepackFull and GarbageCollect

Closes #1382

See merge request gitlab-org/gitaly!1110

9 files changed, 283 insertions, 20 deletions

diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml
index e1876af5d..0c209e345 100644
--- a/.gitlab-ci.yml
+++ b/.gitlab-ci.yml
@@ -102,6 +102,10 @@ binaries_go1.10:
   <<: *assemble_definition
   image: registry.gitlab.com/gitlab-org/gitlab-build-images:ruby-2.5-golang-1.10-git-2.18
 
+test:go1.12-git-2.21-ruby-2.5:
+  image: registry.gitlab.com/gitlab-org/gitlab-build-images:ruby-2.5-golang-1.12-git-2.21
+  <<: *test_definition
+
 test:go1.12-git-2.18-ruby-2.5:
   image: registry.gitlab.com/gitlab-org/gitlab-build-images:ruby-2.5-golang-1.12-git-2.18
   <<: *test_definition
diff --git a/changelogs/unreleased/repack-delta-islands.yml b/changelogs/unreleased/repack-delta-islands.yml
new file mode 100644
index 000000000..3a6fe19dc
--- /dev/null
+++ b/changelogs/unreleased/repack-delta-islands.yml
@@ -0,0 +1,5 @@
+---
+title: Use delta islands in RepackFull and GarbageCollect
+merge_request: 1110
+author:
+type: performance
diff --git a/internal/git/helper_test.go b/internal/git/helper_test.go
index e928e69d7..e6ad932bd 100644
--- a/internal/git/helper_test.go
+++ b/internal/git/helper_test.go
@@ -29,3 +29,33 @@ func TestValidateRevision(t *testing.T) {
 		})
 	}
 }
+
+func TestSupportsDeltaIslands(t *testing.T) {
+	testCases := []struct {
+		version string
+		fail    bool
+		delta   bool
+	}{
+		{version: "2.20.0", delta: true},
+		{version: "2.21.5", delta: true},
+		{version: "2.19.8", delta: false},
+		{version: "1.20.8", delta: false},
+		{version: "1.18.0", delta: false},
+		{version: "2.20", fail: true},
+		{version: "bla bla", fail: true},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.version, func(t *testing.T) {
+			out, err := SupportsDeltaIslands(tc.version)
+
+			if tc.fail {
+				require.Error(t, err)
+				return
+			}
+
+			require.NoError(t, err)
+			require.Equal(t, tc.delta, out, "delta island support")
+		})
+	}
+}
diff --git a/internal/git/proto.go b/internal/git/proto.go
index 99e4629fe..9f2a43f24 100644
--- a/internal/git/proto.go
+++ b/internal/git/proto.go
@@ -5,6 +5,7 @@ import (
 	"context"
 	"fmt"
 	"path/filepath"
+	"strconv"
 	"strings"
 	"time"
 
@@ -61,6 +62,27 @@ func Version() (string, error) {
 	return ver[2], nil
 }
 
+// SupportsDeltaIslands checks if a version string (e.g. "2.20.0")
+// corresponds to a Git version that supports delta islands.
+func SupportsDeltaIslands(version string) (bool, error) {
+	versionSplit := strings.SplitN(version, ".", 3)
+	if len(versionSplit) < 3 {
+		return false, fmt.Errorf("expected major.minor.patch in %q", version)
+	}
+
+	var major, minor uint32
+	for i, v := range []*uint32{&major, &minor} {
+		n64, err := strconv.ParseUint(versionSplit[i], 10, 32)
+		if err != nil {
+			return false, err
+		}
+
+		*v = uint32(n64)
+	}
+
+	return major >= 2 && minor >= 20, nil
+}
+
 // BuildGitOptions helps to generate options to the git command.
 // If gitOpts is not empty then its values are passed as part of
 // the "-c" option of the git command, the other values are passed along with the subcommand.
diff --git a/internal/service/repository/delta_islands_test.go b/internal/service/repository/delta_islands_test.go
new file mode 100644
index 000000000..5efd49451
--- /dev/null
+++ b/internal/service/repository/delta_islands_test.go
@@ -0,0 +1,99 @@
+package repository
+
+import (
+	"bytes"
+	"crypto/rand"
+	"fmt"
+	"io"
+	"strings"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+	"github.com/stretchr/testify/require"
+	"gitlab.com/gitlab-org/gitaly/internal/git"
+	"gitlab.com/gitlab-org/gitaly/internal/testhelper"
+)
+
+type deltaIslandOutcome int
+
+const (
+	expectDeltaIslands deltaIslandOutcome = iota
+	expectNoDeltaIslands
+)
+
+// testDeltaIslands is based on the tests in
+// https://github.com/git/git/blob/master/t/t5320-delta-islands.sh .
+func testDeltaIslands(t *testing.T, repoPath string, outcome deltaIslandOutcome, repack func() error) {
+	gitVersion, err := git.Version()
+	require.NoError(t, err)
+
+	supported, err := git.SupportsDeltaIslands(gitVersion)
+	require.NoError(t, err, "git delta island support check")
+	if !supported {
+		t.Skipf("delta islands are not supported by this Git version (%s), skipping test", gitVersion)
+	}
+
+	// Create blobs that we expect Git to use delta compression on.
+	blob1 := make([]byte, 100000)
+	_, err = io.ReadFull(rand.Reader, blob1)
+	require.NoError(t, err)
+
+	blob2 := append(blob1, "\nblob 2"...)
+
+	// Assume Git prefers the largest blob as the delta base.
+	badBlob := append(blob2, "\nbad blob"...)
+
+	blob1ID := commitBlob(t, repoPath, "refs/heads/branch1", blob1)
+	blob2ID := commitBlob(t, repoPath, "refs/tags/tag2", blob2)
+
+	// The bad blob will only be reachable via a non-standard ref. Because of
+	// that it should be excluded from delta chains in the main island.
+	badBlobID := commitBlob(t, repoPath, "refs/bad/ref3", badBlob)
+
+	// So far we have create blobs and commits but they will be in loose
+	// object files; we want them to be delta compressed. Run repack to make
+	// that happen.
+	testhelper.MustRunCommand(t, nil, "git", "-C", repoPath, "repack", "-ad")
+
+	assert.Equal(t, badBlobID, deltaBase(t, repoPath, blob1ID), "expect blob 1 delta base to be bad blob after test setup")
+	assert.Equal(t, badBlobID, deltaBase(t, repoPath, blob2ID), "expect blob 2 delta base to be bad blob after test setup")
+
+	require.NoError(t, repack(), "repack after delta island setup")
+
+	switch outcome {
+	case expectDeltaIslands:
+		assert.Equal(t, blob2ID, deltaBase(t, repoPath, blob1ID), "blob 1 delta base should be blob 2 after repack")
+
+		// blob2 is the bigger of the two so it should be the delta base
+		assert.Equal(t, git.NullSHA, deltaBase(t, repoPath, blob2ID), "blob 2 should not be delta compressed after repack")
+	case expectNoDeltaIslands:
+		assert.Equal(t, badBlobID, deltaBase(t, repoPath, blob1ID), "expect blob 1 delta base to still be bad blob after repack")
+		assert.Equal(t, badBlobID, deltaBase(t, repoPath, blob2ID), "expect blob 2 delta base to still be bad blob after repack")
+	}
+}
+
+func commitBlob(t *testing.T, repoPath, ref string, content []byte) string {
+	hashObjectOut := testhelper.MustRunCommand(t, bytes.NewReader(content), "git", "-C", repoPath, "hash-object", "-w", "--stdin")
+	blobID := chompToString(hashObjectOut)
+
+	treeSpec := fmt.Sprintf("100644 blob %s\tfile\n", blobID)
+	mktreeOut := testhelper.MustRunCommand(t, strings.NewReader(treeSpec), "git", "-C", repoPath, "mktree")
+	treeID := chompToString(mktreeOut)
+
+	// No parent, that means this will be an initial commit. Not very
+	// realistic but it doesn't matter for delta compression.
+	commitTreeOut := testhelper.MustRunCommand(t, nil, "git", "-C", repoPath, "commit-tree", "-m", "msg", treeID)
+	commitID := chompToString(commitTreeOut)
+
+	testhelper.MustRunCommand(t, nil, "git", "-C", repoPath, "update-ref", ref, commitID)
+
+	return blobID
+}
+
+func deltaBase(t *testing.T, repoPath string, blobID string) string {
+	catfileOut := testhelper.MustRunCommand(t, strings.NewReader(blobID), "git", "-C", repoPath, "cat-file", "--batch-check=%(deltabase)")
+
+	return chompToString(catfileOut)
+}
+
+func chompToString(s []byte) string { return strings.TrimSuffix(string(s), "\n") }
diff --git a/internal/service/repository/gc.go b/internal/service/repository/gc.go
index 128e343c7..879059475 100644
--- a/internal/service/repository/gc.go
+++ b/internal/service/repository/gc.go
@@ -38,12 +38,8 @@ func (server) GarbageCollect(ctx context.Context, in *gitalypb.GarbageCollectReq
 		return nil, err
 	}
 
-	args := []string{"-c"}
-	if in.GetCreateBitmap() {
-		args = append(args, "repack.writeBitmaps=true")
-	} else {
-		args = append(args, "repack.writeBitmaps=false")
-	}
+	args := repackConfig(ctx, in.CreateBitmap)
+
 	args = append(args, "gc")
 	cmd, err := git.Command(ctx, in.GetRepository(), args...)
 	if err != nil {
diff --git a/internal/service/repository/gc_test.go b/internal/service/repository/gc_test.go
index b8f258ddd..c920e8304 100644
--- a/internal/service/repository/gc_test.go
+++ b/internal/service/repository/gc_test.go
@@ -13,9 +13,11 @@ import (
 	"github.com/stretchr/testify/assert"
 	"github.com/stretchr/testify/require"
 	"gitlab.com/gitlab-org/gitaly-proto/go/gitalypb"
+	"gitlab.com/gitlab-org/gitaly/internal/featureflag"
 	"gitlab.com/gitlab-org/gitaly/internal/helper/text"
 	"gitlab.com/gitlab-org/gitaly/internal/testhelper"
 	"google.golang.org/grpc/codes"
+	"google.golang.org/grpc/metadata"
 )
 
 var (
@@ -257,3 +259,38 @@ func createFileWithTimes(path string, mTime time.Time) {
 	ioutil.WriteFile(path, nil, 0644)
 	os.Chtimes(path, mTime, mTime)
 }
+
+func TestGarbageCollectDeltaIslands(t *testing.T) {
+	server, serverSocketPath := runRepoServer(t)
+	defer server.Stop()
+
+	client, conn := newRepositoryClient(t, serverSocketPath)
+	defer conn.Close()
+
+	testRepo, testRepoPath, cleanupFn := testhelper.NewTestRepo(t)
+	defer cleanupFn()
+
+	ctx, cancel := context.WithCancel(context.Background())
+	defer cancel()
+
+	md := metadata.New(map[string]string{featureflag.HeaderKey(deltaIslandsFeatureFlag): "true"})
+	ctxWithFeatureFlag := metadata.NewOutgoingContext(ctx, md)
+
+	testCases := []struct {
+		desc    string
+		outcome deltaIslandOutcome
+		ctx     context.Context
+	}{
+		{desc: "feature flag not set", outcome: expectNoDeltaIslands, ctx: ctx},
+		{desc: "feature flag set", outcome: expectDeltaIslands, ctx: ctxWithFeatureFlag},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.desc, func(t *testing.T) {
+			testDeltaIslands(t, testRepoPath, tc.outcome, func() error {
+				_, err := client.GarbageCollect(tc.ctx, &gitalypb.GarbageCollectRequest{Repository: testRepo})
+				return err
+			})
+		})
+	}
+}
diff --git a/internal/service/repository/repack.go b/internal/service/repository/repack.go
index e7a08f433..fcc876a44 100644
--- a/internal/service/repository/repack.go
+++ b/internal/service/repository/repack.go
@@ -2,40 +2,50 @@ package repository
 
 import (
 	"context"
+	"fmt"
 
-	grpc_logrus "github.com/grpc-ecosystem/go-grpc-middleware/logging/logrus"
-	log "github.com/sirupsen/logrus"
+	"github.com/prometheus/client_golang/prometheus"
 	"gitlab.com/gitlab-org/gitaly-proto/go/gitalypb"
+	"gitlab.com/gitlab-org/gitaly/internal/featureflag"
 	"gitlab.com/gitlab-org/gitaly/internal/git"
 	"google.golang.org/grpc/codes"
 	"google.golang.org/grpc/status"
 )
 
+const deltaIslandsFeatureFlag = "delta-islands"
+
+var (
+	repackCounter = prometheus.NewCounterVec(
+		prometheus.CounterOpts{
+			Name: "gitaly_repack_total",
+			Help: "Counter of Git repack operations",
+		},
+		[]string{"bitmap", "delta_islands"},
+	)
+)
+
+func init() {
+	prometheus.Register(repackCounter)
+}
+
 func (server) RepackFull(ctx context.Context, in *gitalypb.RepackFullRequest) (*gitalypb.RepackFullResponse, error) {
-	if err := repackCommand(ctx, "RepackFull", in.GetRepository(), in.GetCreateBitmap(), "-A", "--pack-kept-objects", "-l"); err != nil {
+	if err := repackCommand(ctx, in.GetRepository(), in.GetCreateBitmap(), "-A", "--pack-kept-objects", "-l"); err != nil {
 		return nil, err
 	}
 	return &gitalypb.RepackFullResponse{}, nil
 }
 
 func (server) RepackIncremental(ctx context.Context, in *gitalypb.RepackIncrementalRequest) (*gitalypb.RepackIncrementalResponse, error) {
-	if err := repackCommand(ctx, "RepackIncremental", in.GetRepository(), false); err != nil {
+	if err := repackCommand(ctx, in.GetRepository(), false); err != nil {
 		return nil, err
 	}
 	return &gitalypb.RepackIncrementalResponse{}, nil
 }
 
-func repackCommand(ctx context.Context, rpcName string, repo *gitalypb.Repository, bitmap bool, args ...string) error {
-	grpc_logrus.Extract(ctx).WithFields(log.Fields{
-		"WriteBitmaps": bitmap,
-	}).Debug(rpcName)
+func repackCommand(ctx context.Context, repo *gitalypb.Repository, bitmap bool, args ...string) error {
+	cmdArgs := repackConfig(ctx, bitmap)
 
-	var cmdArgs []string
-	if bitmap {
-		cmdArgs = []string{"-c", "repack.writeBitmaps=true", "repack", "-d"}
-	} else {
-		cmdArgs = []string{"-c", "repack.writeBitmaps=false", "repack", "-d"}
-	}
+	cmdArgs = append(cmdArgs, "repack", "-d")
 	cmdArgs = append(cmdArgs, args...)
 
 	cmd, err := git.Command(ctx, repo, cmdArgs...)
@@ -52,3 +62,26 @@ func repackCommand(ctx context.Context, rpcName string, repo *gitalypb.Repositor
 
 	return nil
 }
+
+func repackConfig(ctx context.Context, bitmap bool) []string {
+	var args []string
+
+	if bitmap {
+		args = append(args, "-c", "repack.writeBitmaps=true")
+	} else {
+		args = append(args, "-c", "repack.writeBitmaps=false")
+	}
+
+	deltaIslands := featureflag.IsEnabled(ctx, deltaIslandsFeatureFlag)
+	if deltaIslands {
+		args = append(args,
+			"-c", "pack.island=refs/heads",
+			"-c", "pack.island=refs/tags",
+			"-c", "repack.useDeltaIslands=true",
+		)
+	}
+
+	repackCounter.WithLabelValues(fmt.Sprint(bitmap), fmt.Sprint(deltaIslands)).Inc()
+
+	return args
+}
diff --git a/internal/service/repository/repack_test.go b/internal/service/repository/repack_test.go
index 186095594..324c61532 100644
--- a/internal/service/repository/repack_test.go
+++ b/internal/service/repository/repack_test.go
@@ -11,8 +11,10 @@ import (
 	"github.com/stretchr/testify/assert"
 	"github.com/stretchr/testify/require"
 	"gitlab.com/gitlab-org/gitaly-proto/go/gitalypb"
+	"gitlab.com/gitlab-org/gitaly/internal/featureflag"
 	"gitlab.com/gitlab-org/gitaly/internal/testhelper"
 	"google.golang.org/grpc/codes"
+	"google.golang.org/grpc/metadata"
 )
 
 func TestRepackIncrementalSuccess(t *testing.T) {
@@ -188,3 +190,38 @@ func TestRepackFullFailure(t *testing.T) {
 		})
 	}
 }
+
+func TestRepackFullDeltaIslands(t *testing.T) {
+	server, serverSocketPath := runRepoServer(t)
+	defer server.Stop()
+
+	client, conn := newRepositoryClient(t, serverSocketPath)
+	defer conn.Close()
+
+	testRepo, testRepoPath, cleanupFn := testhelper.NewTestRepo(t)
+	defer cleanupFn()
+
+	ctx, cancel := context.WithCancel(context.Background())
+	defer cancel()
+
+	md := metadata.New(map[string]string{featureflag.HeaderKey(deltaIslandsFeatureFlag): "true"})
+	ctxWithFeatureFlag := metadata.NewOutgoingContext(ctx, md)
+
+	testCases := []struct {
+		desc    string
+		outcome deltaIslandOutcome
+		ctx     context.Context
+	}{
+		{desc: "feature flag not set", outcome: expectNoDeltaIslands, ctx: ctx},
+		{desc: "feature flag set", outcome: expectDeltaIslands, ctx: ctxWithFeatureFlag},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.desc, func(t *testing.T) {
+			testDeltaIslands(t, testRepoPath, tc.outcome, func() error {
+				_, err := client.RepackFull(tc.ctx, &gitalypb.RepackFullRequest{Repository: testRepo})
+				return err
+			})
+		})
+	}
+}