Gitserver: recursive git tree lister

[camdencheek]

The API to support the file tree would benefit from a bespoke RPC in gitserver.

A few requirements from the perspective of the final consumer (some of this could be implemented in frontend for a simpler gitserver API):

• Pagination. Some directories contain many entries, and we need to be able to request more in a followup. What we use for cursor (offset? tree OID?) is up for debate.
• Recursive listing (e.g. "get me all the things I would need to show in the UI if I expanded the file tree out to this file"). This can be handled in frontend, which might make sense to simplify the gitserver API. However, that comes at the cost of higher latency for deeply nested directories because we will need to make many followup requests. I'm thinking maybe we solve this with bidi streaming?
• (Nice to have) Single-entry directory collapse (e.g. fetch the info to render src/main/com/sourcegraph/gitserver if that's the only thing each of those dirs contains). If we do this in frontend, we need to make a followup request for every directory to see if it contains only a single child, then do that recursively, which is expensive and slow.
• (Nice to have) Language detection. High-fidelity language detection requires that the file contents can be fetched if the language is ambiguous from just the file name. Right now, this means fetching the file contents from gitserver as a followup request, which is slow. It would be considerably cheaper to do this on gitserver itself.

Proposed RPC proto (starting point, feel free to tear apart):

service GitserverService {
  rpc ListFiles(stream ListFilesRequest) returns (stream ListFilesResponse) {
    option idempotency_level = NO_SIDE_EFFECTS;
  }
}

message ListFilesRequest {
  string repo_name = 2;
  string commit_sha = 3;
  string path = 4;

  uint32 limit = 5;
  bool detect_language = 6;
  bool recurse_single_child = 7;
}

message ListFilesResponse {
  string repo_name = 2;
  string commit_sha = 3;
  string path = 4;

  repeated ListFileEntry entries = 5;
  // Whether or not entries is complete
  bool limit_hit = 6;
}

message ListFileEntry {
  // The name of the entry, which can be appended to its parent's path to get
  // the full path to this entry
  string name = 1;
  // Should be blob or tree. Can probably be an enum.
  string type = 2;
  // The oid of the entry.
  string oid = 3;
  // The detected languages of the etry. Will always be empty if a tree entry.
  repeated string languages = 4;
}

This is implemented as a stream so the caller can make asynchronous requests for followup information. This would be used for recursive listing (send a request for each ancestor directory) and for single-child collapsing (sending an asynchronous folllowup for each tree entry). The response would include information on whether or not a limit was hit for that directory. This does not currently have a cursor of any sort, but we could change limit_hit to a next_page_oid cursor or something.

This includes a recurse_single_child option that would proactively send back ListFilesResponse for each tree entry that only contains a single child. This is not strictly necessary because we could send a followup request for each tree entry with limit = 1, but it would likely significantly improve latency.

[bahrmichael]

Adding to @camdencheek's suggestion: For Language Stats Insights we also need the line count in addition to the language.

For the language detection, we currently download each file of a repository, unless it's a vendored file. In some cases we need this to determine the language, but in all cases (1, 2) we need it to count the lines of the file which then go into the language stats of a repository.

I've experimented with a git diff against the dev null sha, like this: git diff --numstat 4b825dc642cb6eb9a060e54bf8d69288fbee4904 -- CHANGELOG.md.

This gives us the line count which we can then return as a number. When I tried hacking this into gitserver I got stuck with error messages about broken work directories that I didn't follow up further on.

[eseliger]

I agree that we would want to expose a better API to efficiently implement recurse single child.

For language detection:

I hacked a little on the inventory case, and (hackily, didn't bother making the caching work again and stuff) was able to get the inventory time for the root of sg/sg with no caches in redis present go from 8.3s to 3.5s by switching to ArchiveReader to stream all tar headers, and then have the file contents readily available when needed. Using archive reader to iterate will incur no additional round trip and process spawning overhead for readfile or for ls-tree. Generating an archive in git is relatively low cost (compared to fetching many trees and blobs individually, at least).
By that you can do language detection and line count for the same cost that gitserver would incur (you have to read the whole file to know the count of \n, there's no metadata in inodes about line count).

I am not super convinced yet that language detection should live in gitserver, plus the caching that would be involved etc., I think it would be better suited either where it is today (in the request path, indexing when needed), or in worker where it would index every repo once every X hours in advance (depending on how often you need that to refresh) and we should instead make sure the gitserver APIs are performant enough to achieve what you need.
The reasoning here is two-fold:

• This is adding additional load to gitserver for running enry, gitserver has difficult scaling today with not being HA and being a statefulset
• The caching and potential background routine that would pre-compute this so we can hit our SLOs for request latencies would add complexity for the case where we would start pursuing HA of the service, because suddenly not every shard should run this for every repo anymore. Going through the routing layer and running the job per repo instead of per cloned copy of the repo will be less complex here

Example diff of the hack

diff --git a/cmd/frontend/backend/inventory.go b/cmd/frontend/backend/inventory.go
index 41330fada61..e718a6d3c9c 100644
--- a/cmd/frontend/backend/inventory.go
+++ b/cmd/frontend/backend/inventory.go
@@ -66,6 +66,7 @@ func InventoryContext(logger log.Logger, repo api.RepoName, gsClient gitserver.C
 	logger = logger.Scoped("InventoryContext").
 		With(log.String("repo", string(repo)), log.String("commitID", string(commitID)))
 	invCtx := inventory.Context{
+		Repo: repo,
 		ReadTree: func(ctx context.Context, path string) ([]fs.FileInfo, error) {
 			trc, ctx := trace.New(ctx, "ReadTree waits for semaphore")
 			err := gitServerSemaphore.Acquire(ctx, 1)
diff --git a/cmd/frontend/backend/repos.go b/cmd/frontend/backend/repos.go
index 30e9bb5f734..8e7ec4f2ea3 100644
--- a/cmd/frontend/backend/repos.go
+++ b/cmd/frontend/backend/repos.go
@@ -3,11 +3,12 @@ package backend
 import (
 	"context"
 	"fmt"
-	"github.com/sourcegraph/sourcegraph/internal/env"
 	"net/http"
 	"strconv"
 	"time"
 
+	"github.com/sourcegraph/sourcegraph/internal/env"
+
 	"github.com/prometheus/client_golang/prometheus"
 	"github.com/prometheus/client_golang/prometheus/promauto"
 	"github.com/sourcegraph/log"
@@ -269,16 +270,11 @@ func (s *repos) GetInventory(ctx context.Context, repo api.RepoName, commitID ap
 		return nil, err
 	}
 
-	root, err := s.gitserverClient.Stat(ctx, repo, commitID, "")
-	if err != nil {
-		return nil, err
-	}
-
 	// In computing the inventory, sub-tree inventories are cached based on the OID of the Git
 	// tree. Compared to per-blob caching, this creates many fewer cache entries, which means fewer
 	// stores, fewer lookups, and less cache storage overhead. Compared to per-commit caching, this
 	// yields a higher cache hit rate because most trees are unchanged across commits.
-	inv, err := invCtx.Entries(ctx, root)
+	inv, err := invCtx.All(ctx)
 	if err != nil {
 		return nil, err
 	}
diff --git a/cmd/frontend/internal/inventory/context.go b/cmd/frontend/internal/inventory/context.go
index c3737b024c5..c93e5857b83 100644
--- a/cmd/frontend/internal/inventory/context.go
+++ b/cmd/frontend/internal/inventory/context.go
@@ -4,10 +4,13 @@ import (
 	"context"
 	"io"
 	"io/fs"
+
+	"github.com/sourcegraph/sourcegraph/internal/api"
 )
 
 // Context defines the environment in which the inventory is computed.
 type Context struct {
+	Repo api.RepoName
 	// ReadTree is called to list the immediate children of a tree at path. The returned fs.FileInfo
 	// values' Name method must return the full path (that can be passed to another ReadTree or
 	// ReadFile call), not just the basename.
diff --git a/cmd/frontend/internal/inventory/entries.go b/cmd/frontend/internal/inventory/entries.go
index 7f53601815a..fd8353ab3f4 100644
--- a/cmd/frontend/internal/inventory/entries.go
+++ b/cmd/frontend/internal/inventory/entries.go
@@ -1,13 +1,55 @@
 package inventory
 
 import (
+	"archive/tar"
 	"context"
-	"github.com/sourcegraph/conc/iter"
-	"github.com/sourcegraph/sourcegraph/lib/errors"
+	"io"
 	"io/fs"
 	"sort"
+
+	"github.com/sourcegraph/conc/iter"
+
+	"github.com/sourcegraph/sourcegraph/internal/gitserver"
+	"github.com/sourcegraph/sourcegraph/lib/errors"
 )
 
+func (c *Context) All(ctx context.Context) (Inventory, error) {
+	gs := gitserver.NewClient("TODO")
+	r, err := gs.ArchiveReader(ctx, c.Repo, gitserver.ArchiveOptions{Treeish: "HEAD", Format: gitserver.ArchiveFormatTar})
+	if err != nil {
+		return Inventory{}, err
+	}
+
+	invs := make([]Inventory, 0)
+	tr := tar.NewReader(r)
+	for {
+		th, err := tr.Next()
+		if err != nil {
+			if errors.Is(err, io.EOF) {
+				return Sum(invs), nil
+			}
+			return Inventory{}, err
+		}
+		entry := th.FileInfo()
+
+		switch {
+		case entry.Mode().IsRegular():
+			inv, err := c.fileTar(ctx, th, tr)
+			if err != nil {
+				return Inventory{}, err
+			}
+			invs = append(invs, inv)
+		case entry.Mode().IsDir():
+			// If we want to we could try to optimize cache invalidation at the tree level
+			// here. For now, we only iterate over all the files in the archive.
+			continue
+		default:
+			// Skip symlinks, submodules, etc.
+			continue
+		}
+	}
+}
+
 // Entries computes the inventory of languages for the given entries. It traverses trees recursively
 // and caches results for each subtree. Results for listed files are cached.
 //
@@ -108,6 +150,33 @@ func (c *Context) file(ctx context.Context, file fs.FileInfo) (inv Inventory, er
 	return Inventory{Languages: []Lang{lang}}, nil
 }
 
+func (c *Context) fileTar(ctx context.Context, file *tar.Header, r io.Reader) (inv Inventory, err error) {
+	// Get and set from the cache.
+	if c.CacheGet != nil {
+		if inv, ok := c.CacheGet(ctx, file.FileInfo()); ok {
+			return inv, nil // cache hit
+		}
+	}
+	if c.CacheSet != nil {
+		defer func() {
+			if err == nil {
+				c.CacheSet(ctx, file.FileInfo(), inv) // store in cache
+			}
+		}()
+	}
+
+	lang, err := getLang(ctx, file.FileInfo(), func(ctx context.Context, path string) (io.ReadCloser, error) {
+		return io.NopCloser(r), nil
+	})
+	if err != nil {
+		return Inventory{}, errors.Wrapf(err, "inventory file %q", file.FileInfo().Name())
+	}
+	if lang == (Lang{}) {
+		return Inventory{}, nil
+	}
+	return Inventory{Languages: []Lang{lang}}, nil
+}
+
 func Sum(invs []Inventory) Inventory {
 	byLang := map[string]*Lang{}
 	for _, inv := range invs {

Thoughts on this?

[bahrmichael]

I agree with your concerns @eseliger. Given performance boost we're seeing here I'll be happy to give that a try, and also test it with the chromium repo. Thanks for explaining your thoughts in such detail and adding a diff that I can continue from!