# Project Overview

## Longterm Goal/Motivation

Implement a git server with gitoxide that performs well ***at scale***.
Some potential applications:

* attract industry interest from git hosting provides (github, gitlab, aws code commit, ...)
* allows implementation of distributed github alternative
* allows implementation of other distributed services (time tracker, password manager) that leverage git as their core technology for data storage and backup
* **move crates.io from github to a gitoxide based server**
* potentially distributed/federate to allow separate instances in each legislature while still allowing colabaration
> [name=Pascal] TODO: motivate in detail when writing grant application

## Project Goal

Gitoxide is lacking support for git features that are necessary for a high performance git server. The goal of this grant is to develop support for these git features so that an efficient server can be implemented in the future.

Specifically this project will focus on implementing a minimal prototype for a performant implementation of `git-upload-pack`. This command is invoked whenever a fetch (`git pull`/`git fetch` /`git clone`) is performed over ssh or locally.

Apart from the packet transportation itself, the `git-upload-pack` commands main job is determining which objects to send and converting them into packs.
Implementing this process with gitoxide is slow because it requires traversing the entire object graph.
Rechability bitmaps were introduced to `git` to adress that problem and will be a large focus for this project.

## Technical Details

To address the performance requirement layed out above, git was extended with multiple features (mainly by github, see talk by Taylor Blau):

* speedup object counting (for fetch/clone) with reachability bitmaps:
* compressed bitmap stored on disk for some commits that indicates which objects are reachable from a commit
* counting objects for fetch/clone becomes a couple bitmap operations (very fast)
* only works **inside a single pack** (by default) because each object is represented by its pack-order index
* Tasks (related [#296](https://github.com/Byron/gitoxide/issues/296))
- [x] implement basic support (read from disk, iterate set bits) for EWAH bitmaps
- [ ] implement set operations (union/intersection/insert element/remove element) for EWAH bitmaps
- [ ] implement support for reading [bitmap pack files](https://git-scm.com/docs/bitmap-format) (which contain reachability bitmaps)
* Outscoped (handeled by git maintainance)
- [ ] implement support for writing/updating [pack files](https://git-scm.com/docs/bitmap-format)
* repackaging the entire repo into a single pack file during maintenance is prohibitively expensive => reachability bitmaps must be extended to multipack indices (using reverse indecies, see below)
* implementing support for reverse index files:
* Use cases:
* Implementing **reachability bitmaps** for multipack indices requires **a defined pack-order** for the full repo
* many operations (like maintenance/repackaging/pack creation) require a mapping from position within pack to object-id (sha) => recomputed often, faster to cache
* Tasks
* [ ] implement reading single package rev files from disk
* [ ] use reverse index cache during pack creation ([#76](https://github.com/Byron/gitoxide/issues/76)), benchmark if the improvement is worth it
* [ ] implement creation of single-pack reverse index for a pack
* [ ] implement reading multipack rev files from disk
* Outscoped Tasks (required for git maitainance, see Future Work):
* [ ] implement writing single package rev files to disk
* [ ] implement writing multipack rev files to disk
* [ ] implement creation of multipack reverse index for a repo
* [ ] use multipack reverse index to implement full repo reachability index

Implementing `git-upload-pack` requires implementing the server side of the fetch implementation
* goal: be compatible with current gitoxide fetch implementation
* must support protocol v2
* portocol v1 is a stretch goal (optional)
* support for optional capabilities is a stretch goal (needed for shallow clone or advanced pack negotiations)

## Future Work
* implement git maitainance
* each push adds exploded packs to repository => need to be repacked to reduce filesize
* regularly reorganize objects into few packs to keep repo fast
* requirements for performance scaling:
* only few packages should remain after repackaging
* repackaging should only scale with the **number of new packages** since the last repack (not the total number of packages)
* implement geometric pack creation (`git repack --geometric`)
* Strategy to ensure maintenance operations is fast
* When first implemented at GitHub saved 5.67 CPU-days every hour
* Packs are sorted by the number of objects they contain
* The `n`. pack has at least `M` times as many objects as the pack `n-1`, where `M` is an integer parameter (usually 2)
* When the above property does not hold, all previous packages are repackaged into the `n`. pack
>
* Equivalent gix command for `git repackage --geometric` (perform repo maintainance)~~
* implement writing/creation of reachability bitmap

# Somewhat Related Questions
* the ssh protocol is essentially just an ssh tunnel that calls certain git binaries
=> so a server is just multiple gix applications and an ssh server?
* alternative: implement a custom ssh server that can only execute a fixed set of commands (potentially faster because requests do not need to write to disk?)
* fork an existing rust ssh server? (https://github.com/warp-tech/russh)
* http/https/git protocol definitely require a custom server
* pack integration is mostly implemented already [#307](https://github.com/Byron/gitoxide/issues/307) but does not use geometric repackaging

# Grant Application

## Previous Experience

Most of my Rust experience has been obtained by developing an open source [Verilog-A compiler](https://github.com/pascalkuthe/OpenVAF/) for multiple years with more than 60k lines of code. It builds on ideas from rust-analyzer/rustc for the frontend, cranelift and contains a custom middle-end that mixes architecture from llvm and cranelift. All code in Verilog-A is (due to limitations of existing compilers) usually contained in a single function, so performance needed to scale well to large functions.
As a result, I am very proficient in developing high-performance rust code.

Recently, I have been working on the [helix editor](https://github.com/helix-editor/helix) and related projects ([termi](https://github.com/pascalkuthe/termini) and [ropey](https://github.com/cessen/ropey)), as well as a library for performing fast diffs that match/exceed gits performance, [imara-diff](https://github.com/pascalkuthe/termini). It sped up a related `gitoxide` command by a factor of 2.
Trough this work I connected with Sebastian ([byron](https://github.com/Byron/) on github) who suggested collaboration on `gitoxide` and offered to support me during this project.

## Project Proposal

The crates.io index is currently hosted on github.
As a result, the Rust infrastructure is reliant on a single company and unavailable in some legislatures.
For example, to use crates.io in Mainland China, setting up a mirror is required and common practice.
However, hosting a git server on independent infrastructure is challenging because canonical git cannot be used as a library and is difficult to extend or run at scale.
Furthermore, the canonical git implementation often suffers from memory-safety related vulnerabilities (recently in `OpenSSL` for example).
An alternative git server implementation in Rust as part of the `gitoxide` project can solve these problems.

During this project, I will improve the pack creation machinery that runs on the server when a fetch is performed and optionally (stretch goal) develop a minimal viable product for the protocol implementation of the fetches.
Pack generation in `gitoxide` currently doesn't scale well to large repositories (like the crates.io index).
Improving this shortcoming will be my main focus.
I plan to achieve this by utilizing on-disk caches that were added to git by GitHub, but other avenues to further speedups will also be explored.
After the project concludes, the following end-results will be available:

* Performance comparison of pack creation between `git` and `gitoxde`.
* A pack creation implementation in `gitoxide` that will match or exceed the performance of `git` both in the presence and the absence of on-disk caches.
* optionally (stretch goal): A server-side implementation of the git protocol used for fetching that leverages the pack creation to allow fast clones and fetches.

This project benefits Rust beyond hosting crates.io by potentially attracting interest in Rust from git hosting providers (such as AWS or GitHub).
A flexible git implementation also has great potential as the core data storage and backup technology for applications beyond source control.
In the future, `gitoxide` can provide Rust with a unique ecosystem for building distributed services based on git that runs at scale.