Scalar for Git at Scale

15 posts · Sep 2016 – Nov 2023

What this trail covers

This thread tracks the evolution of Git's commit-graph feature for accelerating operations in large repositories. Initially focusing on the commit-graph itself and generation numbers, it has expanded to incorporate Bloom filters for optimizing file history calls and advanced graph algorithms for topological sorting. The goal is to significantly speed up history queries by intelligently avoiding unnecessary tree walks and ensuring correct ordering of commits. This post details improvements to the Trace2 logging framework for detailed performance analysis of Git commands, enabling engineers to identify and address bottlenecks in large repositories.

All Microsoft trails

Nov 2023Git Partial Clone Now Supported in Azure DevOpsIntroduces support for treeless and blobless Git Partial Clones in Azure DevOps. Explains how to use `git clone --filter=blob:none` and `git clone --filter=tree:0`. Highlights performance benefits, showing an average 88.6% reduction in clone time for large repositories. Differentiates partial clones from shallow clones.
Feb 2020Introducing Scalar: Git at scale for everyoneIntroduces Scalar, a .NET Core application designed to accelerate Git workflows for large repositories. Scalar maximizes Git command performance by setting recommended config values, running background maintenance (commit-graph updates, packfile cleanup, loose object cleanup), and supporting the GVFS protocol for cloning. It also details lessons learned: focusing on relevant files, reducing object transfer, and not waiting for expensive operations. The post outlines quick start guides for existing repositories and GVFS protocol usage, and discusses plans for contributing Scalar's features to the core Git client.
Nov 2019Updates to the Git Commit Graph FeatureThis post details the evolution and enhancements of Git's commit-graph feature. It explains how the commit-graph file format, generation numbers, and an iterative Kahn's algorithm improve the performance of commands like `git log --graph` by up to 650x. It also introduces the concept of incremental commit-graph files, forming a chain of smaller graph files to speed up updates after `git fetch` operations. Configuration settings like `core.commitGraph`, `gc.writeCommitGraph`, and `fetch.writeCommitGraph` are explained, with `core.commitGraph` and `gc.writeCommitGraph` being enabled by default in Git 2.24.0. The post also provides a DIY example for creating a commit-graph chain.
Aug 2019A Deep Dive into Git Performance using Trace2This post introduces and details the Trace2 logging framework in Git, a new feature available in Git 2.22. It explains how to enable and use Trace2's performance format target to generate PERF format tracing data. The post provides a deep dive into analyzing `git status` output using Trace2, breaking down process startup, index reading, VFS hook application, status computations, and printing results. It highlights the significant time spent in the 'print' region due to the ahead/behind calculation problem and introduces the concept of using Trace2 for iterative development loops to understand and improve Git performance, especially for large repositories.
May 2019Exploring new frontiers for Git push performanceIntroduced a new sparse pack algorithm for Git that dramatically improves the git push operation on large repos. This algorithm walks uninteresting and interesting commits and trees simultaneously, using commit date and paths as heuristics to identify the frontier and reduce the scope of the tree walk. This leads to significant performance boosts, such as a 7.7x improvement for the Windows team.
Advertisement
Jul 2018Supercharging the Git Commit Graph IV: Bloom FiltersThis post introduces the application of Bloom filters to accelerate file history calls in Visual Studio Team Services (VSTS) Git. It explains how Bloom filters, as probabilistic sets, can provide a 'definitely not' or 'probably in the set' answer, allowing VSTS to avoid walking Git trees when a path has definitely not changed between commits. The post details the mechanics of Bloom filters, their implementation for file history by creating a filter per commit based on changed paths, and the observed speedups (up to 6x-20x) with minimal storage overhead. It also discusses the potential for extending the Git commit-graph feature to use Bloom filters.
Jul 2018Supercharging the Git Commit Graph III: Generations and Graph AlgorithmsThis post introduces the concept of 'generation numbers' for Git commits, defining it as one more than the maximum generation number of its parents. It explains how generation numbers can be computed using DFS and stored in the commit-graph file. The post details three applications of generation numbers: short-circuiting 'Can X Reach Y?' questions (like in `git push`), improving merge-base calculations for `git merge-base` and `git status`, and enabling more efficient topological sorting for `git log --graph` by using two concurrent walks. It also discusses why commit dates are unreliable for ordering and highlights that these advancements are being incorporated into future Git releases and are already used in Visual Studio Team Services (VSTS) for displaying commit history.
Jul 2018Supercharging the Git Commit Graph II: File FormatThis post details the file format of the Git commit-graph, explaining its structure with four main sections: Commit IDs, Fanout, Commit Data, and Octopus Edges. It also discusses small optimizations made to Git's parsing and object database lookups, such as avoiding `mark_parents_uninteresting()` calls and lazily loading tree objects, which contribute to significant speedups for commands like `git status` and `git log --graph`. The post contrasts these improvements with the performance of Visual Studio Team Services (VSTS) in displaying commit history.
Jun 2018Supercharging the Git Commit GraphThis post announces the submission and release of the serialized commit-graph feature to the core Git project (Git 2.18.0 and Git for Windows 2.18.0). It details how to manually enable and update the commit-graph feature, provides performance benchmarks on large repositories (Linux, Git, Windows), and discusses real-world examples of its impact, such as improving force-push times. The author also shares their personal history with the commit graph, from academic research to implementing it on the VSTS Git server and now bringing it to the Git client community.
Jan 2018Microsoft's Performance Contributions to Git in 2017This post details specific contributions to the core Git client in 2017 aimed at improving performance for large repositories, particularly those used with GVFS. Key contributions include optimizations for index loading (skipping ordering checks, checking last entry before binary search, reducing reloads), improvements to `git status` and `git checkout` (new flags for status, file-system monitor integration), and a new algorithm for calculating abbreviated object hashes using binary searches. Micro-optimizations for index reads/writes, such as using hashmaps and stack allocations, are also highlighted.
May 2017Beyond GVFS: more details on optimizing Git for large repositoriesThis post details specific optimizations made to Git and libgit2 to handle large repositories. For the Git index, it describes skipping binary searches when appending sorted paths during branch switches (reducing checkout time by 15-20%) and skipping SHA-1 checksum calculation on index reads for performance gains. For libgit2, it explains the transition from an O(n^2) exact rename detection algorithm to a linear time approach by using a hash map of file IDs, which resolved pull request timeouts for large refactorings.
May 2017Announcing git graph and advanced filters to visualize commit historyThis post introduces the Git graph visualization within Visual Studio Team Services (VSTS) commit history. It explains how the graph visually represents commit ancestry and topological order, aiding in understanding complex changes across multiple branches. The post also details advanced filtering options ('Simple history', 'First parent', 'Full history', 'Full History with simplified merges') to provide different granularities of commit history, helping users identify the impact of commits that might be hidden in simplified views.
Dec 2016What's new in Git for Windows 2.11?This post details performance improvements in Git for Windows v2.11.0, including acceleration of `git rebase` startup, faster hash generation leveraging OpenSSL's Intel CPU support, faster `git add` in large worktrees, better integration of `fscache` with sparse checkouts, and more efficient internal cache for case-insensitive file names. It also introduces an experimental, faster native `difftool` and highlights the ability to build Git for Windows with Visual Studio, enabling code navigation, refactoring, debugging, and profiling tools.
Nov 2016Git perf and scaleThis post details three specific performance and scale improvements for Git operations within Team Services: 1. Significant speedup of pull request merges (64% reduction in median merge time for a large test repo) by adopting a newer LibGit2 version and altering its caching strategy. 2. Rewriting a ref lookup from O(N) to O(1) behavior, improving performance for displaying branch names on the web. 3. Designing and implementing a fast, compact representation of the Git graph to track file history, replacing a 90GB SQL table with an in-memory representation on application tier machines, leading to significant database space savings and improved performance.
Sep 2016What's new in Git for Windows 2.10?This post introduces significant performance improvements to the `git rebase -i` command by re-implementing core logic in C, resulting in up to 5x speedup on Windows. It also announces MinGit, a stripped-down Git for Windows distribution suitable for embedding in applications, and highlights other improvements in Git for Windows v2.10.0, including faster `git rebase` onto fast-moving branches, configurable help browser, executable file marking on Windows, faster initial `git fetch`, and improved `git grep` and merge handling.