Development Guide

Practices

• test-first development
  • protect against regression and make implementing features easy.
  • user containers to test more elaborate user interactions
  • keep it practical, knowing the Rust compiler already has your back for the mundane things, like unhappy code paths.
  • use git itself as reference implementation, and use their test-cases and fixtures where appropriate. At the very least, try to learn from them.
  • use libgit2 test fixtures and cases where appropriate, or learn from them.
• safety first
  • handle all errors, never unwrap(). If needed, expect("why").
  • provide an error chain and make it easy to understand what went wrong. We use quick-error for non-generic errors and thiserror when generalization is needed.
• Adhere to the stability guide

General

• async

  • library client-side
    • Don't use it client side, as operations there are usually bound by the CPU and ultra-fast access to memory mapped files. It's no problem to saturate either CPU or the IO system.
      • Provide async clients as opt-in using feature toggles to help integrating into an existing async codebase.
  • User Interfaces
    • User interfaces can greatly benefit from using async as it's much easier to maintain a responsive UI thread that way thanks to the wonderful future combinators.
    • blocking can be used to make Read and Iterator async, or move any operation onto a thread which blends it into the async world.
      • Most operations are fast and 'interrupting' them is as easy as ignoring their result by cancelling their task.
      • Long-running operations can be roughly interacted with using git_features::interrupt::trigger() function, and after a moment of waiting the flag can be unset with the …::uninterrupt() function to allow new long-running operations to work. Every long running operation supports this.
  • server-side
    • Building a pack is CPU and at some point, IO bound, and it makes no sense to use async to handle more connections - git needs a lot of resources and threads will do just fine.
      • Support async out of the box without locking it into particular traits using conditional complication. This will make integrating into an async codebase easier, which we assume is given on the server side these days.
  • usage of maybe_async
    • Right not we intentionally only use it in tests to allow one set of test cases to test both blocking and async implementations. This is the only way to prevent drift of otherwise distinct implementations.
    • Why not use it to generate blocking versions of traits automatically?
      • This would require maybe_async and its dependencies to always be present, increasing compile times. For now we chose a little more code to handle over increasing compile times for everyone. This stance may change later once compile times don't matter that much anymore to allow the removal of code.

• Default trait implementations

  • These can change only if the effect is contained within the callers process. This means changing the default of a file version is a breaking change.

• Using the Progress trait

  • When receiving a Progress implementation
    • without calling add_child(…) then use it directly to communicate progress, leaving control of the name to the caller. However, call .init(…) to configure the iteration.
    • and when calling add_child(…) don't use the parent progress instance for anything else.

• interruption of long-running operations

  • Use git-features::interrupt::* for building support for interruptions of long-running operations only.
    • It's up to the author to decide how to best integrate it, generally we use a poll-based mechanism to check whether an interrupt flag is set.
    • this is a must if…
      • …temporary resources like files might otherwise be leaked.
    • this is optional but desirable if…
      • …there is no leakage otherwise to support user interfaces. They background long-running operations and need them to be cancellable.

• prepare for SHA256 support by using git_hash::ObjectId and git_hash::oid

  • eventually there will be the need to support both Sha1 and Sha256. We anticipate it by using the Id type instead of slices or arrays of 20 bytes. This way, eventually we can support multiple hash digest sizes.
  • Right now it's unclear how Sha256 is going to work in git, so we only support Sha1 for now. It might be an avenue to proactively implement it ahead of time once there is a specification to follow.
  • It looks like Git prepares to support it by using compile time, we can support it at runtime though with minimal cost. If needed, we can later remove support using a cargo feature toggle.

• symbolic links do not exist as far as we are concerned

  • in older, probably linux only, git versions symbolic links were used for symbolic references for example. This required special handling in some places. We don't implement that and assume more modern repositories.

• when to use interior mutability

  • in plumbing, do not use it at all but instead provide the mutable part (like caches, buffers) as arguments, pushing their handling entirely to the caller.
  • Set on top an optional abstraction that manages the above for you using interior mutability only if part of the mutable state has to be returned as borrow or if otherwise it wouldn't be possible to borrowcheck. Or in other words: start without interior mutability and try to do it the standard way, but switch when needed.
  • When using primitives to support interior mutability, use the provided ones and utility functions in git_features::threading::* exclusively to allow switching between thread-safe and none-threadsafe versions at compile time.
    • The preferred way of using it is to start out as upgradable reader, and upgrading to write if needed, keeping contention to a minimum.
  • If shared ownership is involved, one always needs interior mutability, but may still decide to use an API that requires &mut self if locally stored caches are involved.
  • Types that are not thread-local must be Sync, but only if the git-features/parallel is enabled due to the usage of git_features::threading::… primitives which won't be thread-safe without the feature.

• when to use shared ownership

  • Use git_features::threading::OwnShared particularly when shared resources supposed to be used by thread-local handles. Going through a wrapper for shared ownership is fast and won't be the bottleneck, as it's only about 16% slower than going through a shared reference on a single core.

Sha256

A bunch of notes collected to keep track of what's needed to eventually support it

• read hash-function-transition.txt
• support gpgsig-sha256 field - we won't break, but also don't do anything with it (e.g. extra_headers)
• support index V3
• Pack file PSRC field

.unwrap() vs .expect(…)

• don't use unwrap, not even in tests. Instead use quick_error!() or Box<dyn std::error::Error>.
• Use expect(…) as assertion on Options, providing context on why the expectations should hold. Or in other words, answer "This should work because…<expect(…)>"

Examples, Experiments, Porcelain CLI and Plumbing CLI - which does what?

Plumbing vs Porcelain

Both terms are coming from the git implementation itself, even though it won't necessarily point out which commands are plumbing and which are porcelain. The term plumbing refers to lower-level, more rarely used commands that complement porcelain by being invoked by it or by hand for certain use cases. The term porcelain refers to those with a decent user experience, they are primarily intended for use by humans.

In any case, both types of programs must self-document their capabilities using through the --help flag.

From there, we can derive a few rules to adhere to unless there are good reasons not to:

Plumbing

• does not show any progress or logging output by default
• if supported and logging is enabled, it will show timestamps in UTC
• it does not need a git repository, but instead takes all required information via the command-line

Porcelain

• Provides output to stderr by default to provide progress information. There is no need to allow disabling it, but it shouldn't show up unless the operation takes some time.
• If timestamps are shown, they are in localtime.
• Non-progress information goes to stdout.

Summary

Here is the hierarchy of programs - each level requires more polish and generally work to be done. Experiments are the quickest ways to obtain some insights. Examples are materialized ideas that others can learn from but that don't quite have the polish (or the potential) to move up to plumbing or porcelain. Plumbing is programs for use in scripts, whereas porcelain is for use by humans.

• Experiments
  • quick, potentially one-off programs to learn about an aspect of gitoxide potentially in comparison to other implementations like libgit2.
  • No need for tests of any kind, but it must compile and be idiomatic Rust and gitoxide.
  • Manual commmand-line parsing is OK
  • no polish
  • make it compile quickly, so no extras
• Examples
  • An implementation of ideas for actual occasional use and the first step towards getting integrated into Porcelain or Plumbing CLIs.
  • Proper command-line parsing with Clap.
  • No tests or progress.
  • High quality Rust code along with idiomatic gitoxide usage so people can learn from it.
• Plumbing CLI
  • Use Clap AND Argh for command-line parsing via feature toggles to allow for tiny builds as plumbing is mostly for scripts.
  • Journey tests
  • Progress can be turned on using the --verbose flag, quiet by default.
  • Examples can be turned into plumbing by adding journey tests and argh command-line parsing, as well as progress.
• Porcelain CLI
  • Use Clap for command-line parsing for the best quality CLI experience - it's for the user.
  • Journey tests.
  • Support for --quiet and --progress.
  • Verbose by default.
  • Examples can be turned into plumbing by adding journey tests and progress.

Maintenance Guide

Utilities to aid in keeping the project fresh and in sync can be found in the Maintenance section of the makefile. Run make to get an overview.

Creating a release

Run make publish-all to publish all crates in leaf-first order using cargo release based on the currently set version. For this to work, you have to run cargo release minor|major each time you break the API of a crate but abort it during package verification. That way, cargo release updates all the dependents for you with the new version, without actually publishing to crates.io.

Which git-version to chase?

Generally, we take the git version installed on ubuntu-latest as the one we stay compatible with (while maintaining backwards compatibility). Certain tests only run on CI, designed to validate certain assumptions still hold against possibly changed git program versions.

This also means that CI may fail despite everything being alright locally, and the fix depends on the problem at hand.

How to update fixtures

Fixtures are created by using a line like this which produces a line we ignore via tail +1 followed by the un-prettified object payload trailed by a newline.

echo c56a8e7aa92c86c41a923bc760d2dc39e8a31cf7  | git cat-file --batch | tail +2 > fixture

Thus one has to post-process the file by reducing its size by one using truncate -s -1 fixture, removing the newline byte.

Discovery: data consistency and resource usage

Summary

Concurrent writes to packs observable by applications pose a challenge to the current implementation and we need to find ways around that. There may be other limitations related to any resource that changes often, most prominently refs.

Motivation

Use this document to shed light on the entire problem space surrounding data consistency and resource usage of packed objects to aid in finding solutions that are best for various use cases without committing to high costs in one case or another.

Git as database

Databases are well understood and there is common semantics they typically adhere to. The following is an exploration of the various kinds of databases that make up a git repository along with some of their interplay.

Object Databases

In repositories there may be millions to 10th of millions of objects like commits, blobs, trees and tags, and accessing them quickly is relevant to many of git's features.

Loose object database

Each object is stored in a single file on disk, partitions by the first byte of its content hash. All implementations handle it similarly.

Packed object database

Packs are single files containing one or more objects. Delta-compression allows them to be very size-efficient, e.g. 90x compression for the linux kernel.

Packs and the object database is inherently append-only, i.e. objects are never *[0] deleted, allowing concurrent readers to observe a consistent state even in presence of writers. Writers create new pack files and may remove them after adding all changes successfully, without the need for locking.

gitoxides implementation as of 2021-11-19 is known to be unsuitable in the presence of concurrent writes to packs due to its inability to automatically respond to changed packs on disk if objects cannot be found on the first attempt. Other implementations like libgit2 and canonical git handle this by using thread-safe interior mutability at the cost of scalability.

gitoxides implementation may be insufficient in that regard, but it shows how read-only data allows to scale across core as well as the CPU architecture allows.

The usage of system resources like file handles is simple but potentially wasteful as all packs are memory-mapped in full immediately. Lazy and partial memory-mapping of packs is used in other implementations. Laziness allows for more efficiency and partial mapping allows to handle big packs on 32 bit systems.

Failure to acquire a memory map due to limits in the amount of open file handles results in an error when initializing the pack database in the gitoxides implementation. To my knowledge, this is handled similarly in other implementations. All implementations assume there is unlimited memory, but the effect of running out of memory is only known to me in case of gitoxide which will panic.

[0] deletion is possible but doesn't happen instantly, instead requiring time to pass and calls to git-maintenance and for them to be unreachable, i.e. not used in the entire repository.

Reference databases

References are pointers to objects or other references and are crucial to git as they form the entry points in all git operations. If objects aren't reachable by starting graph traversal at a reference (or its historical reflog information) it is effectively lost forever, i.e. unreachable.

They may be just a couple to hundreds of thousands of references in a repository which are changed right after new objects are added to the object database.

Loose reference database

References are stored one at a time in files, one reference at a time or multiple ones in a single well known file, packed-refs. packed-refs is updated during maintenance to keep keep direct references only.

Multiple references can change at the same time, but multiple changes aren't atomic as changes are made a file at a time. All implementations may observe intermediate states where some but not all references are updated.

packed-refs may change during maintenance or upon deletion of references. All implementations cache the packed-refs file but check for a stale cache (i.e. see if file on disk changed in the mean time) before each use of the cached data.

The database read, i.e. accessing individual reference values or iterating references, performance is heavily limited by disk-IO when accessing loose files. Handling og packed-refs is speedy even in the presence of hundreds of thousands of references due to optimizations performed in all implementations.

The reference update/add performance is parallel per reference as long as the set of writers don't overlap in references to change, but bound by disk-IO, due to writes happening one file at a time. packed-refs is not changed, but typically read to validate write constraints that help with atomicity, i.e. only change a value if it matches the previously observed one.

Deletions are slow and a worst-case scenario as not only the loose reference(s) will be deleted but potentially the packed-refs file updated if it contained the (possibly only) copy/ies. An update implies rewriting packed-refs file entirely. During that time it is locked, blocking or failing other writers, forming a choking point.

gitoxides implementation keeps one packed-refs cache handle to the underlying repository, which costs a file handle for a memory map if the packed-refs file is larger than 32kB, theoretically configurable but currently hardcoded based on the default in git. Other implementations maintain one per repository instance (libgit2) or one per process (git).

Even the biggest transactions will only additionally open one loose reference file at a time, and close it right after use.

Failures to add/update/delete may occur if the constraint isn't met. It's possible to wait in the presence of a lock file instead of failing immediately, which is beneficial if there is no value constraint. Typically value constraints will be used for safety though, so waiting for a lock to be acquired usually results in failure right after as a change caused by a value mismatch. However, in the presence of deletions, it is always useful to wait for locks as after deletion, the previous value can't be checked anymore causing the operation to succeed.

Races exist do not exist for writers, but do exist for readers as they may observe intermediate states of transactions involving multiple updates.

Semantically, gitoxides implementation of this database is equivalent to the one of git.

Ref-table database

Even though gitoxide doesn't have an implementation yet it's useful to understand its semantics as a possible path forward.

As a major difference to the loose reference database it doesn't operate on user editable files but uses a binary format optimized for read performance and consistency, allowing readers to always have a consistent view. There can be any amount of readers.

All changes like updates, additions or deletions are fully transactional, but there can only be one writer at a time. This has the potential for contention in busy (mono-)repositories as file based locking mechanisms aren't fair and waiting strategies with exponential backoff may cause some writers to wait forever.

Due to the lack of experience with this database details around resource consumption in terms of file handles can't be provided at this time.

Configuration

git employs cascaded configuration files to affect processes running on the repository. Their effect can vary widely, and so can their use in applications handling repositories.

gitoxides implementation currently uses only the repository git configuration file when initializing a repository to correctly determine whether or not it is _bare. It does not expose git configuration at this time and doesn't use git configuration when repository initialization is complete.

We have no reason to believe that other implementations use git configuration beyond first initialization either or do anything to assure it remains up to date in memory after reading it.

Index

The index is a single file for the purpose acting as a staging area for building and manipulating upcoming commits.

It is created and updated when checking out files into the working tree, and is used to keep track of working tree states while no commit object was created yet, i.e. during git add ….

gitoxide neither implements it nor it is used in concurrent environments, which is why we exclude it from this discovery.

Known technical problems and their solutions

Before looking at how changes affect data consistency and resource usage affects reliability, let's list all known technical issues thus far.

Solutions aren't always mutually exclusive despite the form of presentation suggesting it.

Amendum problem 5.

Refreshing packs if an object is missed is the current way of handling writes to the pack database. As outlined in how geometric repacking works it can indeed happen that multiple packs are changed which isn't atomic. However, since this will be done in an additive fashion, first adding the new packs based on existing packs and loose objects, and then removing the packs and loose objects they replace, there is no race happening as all objects stay reachable at all times.

Applying changes to repositories while maintaining consistency

A change to any file in a git repository has the potential to affect the processes operating on it, hence it's important to perform them so these observe only valid repository states. For the sake of simplicity, we assume atomicity for all operations, but these still have to be ordered correctly to assure a consistent state.

Adding objects to the database

1. add objects
   • this is safe as these objects aren't reachable yet.
   • object databases are append, only, so no existing state is ever affected.
2. adjust reference(s)
   • point related references to the entry-points of the newly added objects (typically commits or tags)
   • now the new objects can be discovered

Multiple writers will run into conflicts with each other if the references they are handling overlap. Readers will see the object graph from a snapshot of a set of references.

Reorganize objects or references for higher performance

This happens regularly during maintenance operations, which don't alter the repository content but its structure.

1. find objects or references to include in the reorganization
2. write the reorganized data
3. remove the now obsolete data

Multiple of these operations must synchronize or else unpredictable outcomes may occur. Writers may add packs which remain untouched, the same applies to loose objects. Readers will see the object graph from a snapshot of a set of references.

Read references and find objects reachable through them

1. obtain object entry-points pointed to by references
2. traverse object graph with entry points

Multiple readers are always safe.

It's worth repeating that as long as all of the numbered items are truly atomic, readers will always observe a consistent state in the presence of writers.

What breaks consistency

Packs

If all objects were loose, there would be no issue. However, for the above changes to work one must always be able to see all objects. This isn't the case when packs are involved, as accessing them is too costly to redo the entire pack initialization work each time an object is retrieved (e.g. list packs directory, memory map packs).

Thus packs are cached in order to reuse them each time an object is accessed. Staleness is typically checked if an object isn't present, as it's assumed that all objects accessed are reachable through the object graph, which means they ought to be present, triggering a pack refresh and retrying the retrieval.

This assumption isn't necessarily the case (anymore) due to git features causing partial object repositories:

• depth-pruned clones (i.e. git clone --depth X) where all commits after a certain topological distance to the latest commit are left out. Running into this case during traversal is cheap despite triggering a refresh to detect that the object is truly not present, as it running a single time while stopping an entire traversal.
• partial clones with git clone --filter=blob which can be used to download entire histories but blobs only for a portion of the (usually recent) history. Operations like git diff, without special precautions, may run into a lot of object misses causing costly refreshes each time.

Any writer that eventually creates a pack may break readers that operate on a stale cache, making strategies for mitigation like the one above mandatory. Such a mitigation, however, requires interior mutability as object access is a read-only operation, which in turn is costly in multi-threaded applications or for applications that don't need it, like CLIs.

Loose References

Writing loose references isn't actually atomic, so readers may observe some references in an old and some in a new state. This isn't always a breaking issue like it is the case for packs, the progam can still operate and is likely to produce correct (enough) outcomes.

Mitigations are possible with careful programming on the API user's side or by using the ref-table database instead.

What reduces reliability

System resources are limited and avoiding waste (along with decent configuration of ulimits and maintenance of disk-space) is one of the ways to keep an application from failing.

The biggest consumer of system resources most certainly is the pack database due to its cachce of memory mapped pack and index files, and avoiding to duplicate these within a process is paramount.

Use-Cases

We will look at typical access patterns holistically based on various use-cases, look at the problems they would run into and pick their preferred solution that optimizes for efficiency/performance/reduction of waste.

Multi-threaded CLI tool operating on filtered partial repository clone

The tool displays the reference graph, shows differences and creates 'blame' like views on files. As it's operated by the user, other writers are unlikely to happen while it is running.

Scaling near perfectly with added CPU cores and great performance even in the biggest mono-repos are its hallmark.

As the program is is written with missing objects being the default, it gracefully handles and expects such cases. While running in TUI mode, it offers a manual refresh to the user in case they fetched or pulled in the meantime, to refresh the screen and update its object database to make all newly added objects available.

Problems and Solutions

• The program only deals with 1) initialization and 4) object misses, where the latter are expected and handled gracefully. 1) is handled with solution 1., spending time to make all packs available to get the best and most consistent multi-threaded object access performance.

Drawbacks

The program could benefit of using 1.2 instead of 1.1 which could cause exhaustion of file handles despite the user having no interest in evaluating all available objects, but ideally that is possible without loosing performance during multi-threading.

Professional git-hosting mono-repo server with git-maintenance tasks and just-in-time replication

A single server process handles all reads and writes concurrently and receives and sends using the git protocol using an async TCP/IO framework over a custom transport. All operations calling into gitoxide are unblocked using a thread pool. There is only one repository with a reference namespace for each client repository of which it contains 50.000, each averaging 5000 objects and 5 references for a total of 250.000.000 objects and 250.000 references. As many of these repositories have PNG files and binaries checked in, they average to about 25MB of storage space for a total of 1.25TB.

At night there are about 1 send-pack (fetch) and 0.25 send-pack (clone) operations and 0.5 received-pack per second, ramping up to 6 send-pack (fetch) and 1.5 send-pack (clone) and 3 receive-packs per second. At peak times during the day, these values are 10 times higher due to "push and run go home", causing 30 receive-packs per second for an hour or two. (assumption is 50.000 * 5 pushes and 10 fetches and 2.5 clones). Most client-side push operations are sending just 1 or 2 commits with a couple of changes, averaging pack sizes of about 20 objects for a total of 5.000.000 new objects per day or an average of ~208.000 per hour. Only 1 branch is typically updated for 250.000 per day or ~10400 per hour.

After each receive-pack was run and the client connection was informed of success, a background job is started to push the changes using the git protocol to a a sibling server which also takes part in serving clients and also pushes its changes to this server (the writes caused by it are already part of the above measurements).

git-maintenance runs every 5 minutes using the built-in scheduling mechanism to repack references, place loose objects into packs, create and update reverse index caches and reachability bitmaps and repacks existing packs geometrically. Every 24h it recompresses the newly created packs created during geometric repacking.

Problems and Solutions

• 1.1 pack database - initialization → all at once
  • as the server comes up, there is a moment to map all 27 to 28 packs and their indices, totalling up to 56 required file handles, along with maybe twice that many additional packs in case of many pushes of new repositories happening within the git-maintenance time window.
  • there is traffic at all times with some portions of all objects needed in the course of any 24h period
• 2.1 pack database - file limit hit → fail
  • The worst case scenario for the amount of required file handles can be estimated and overcommitted.
  • Update the ulimit if there is not enough available handles for peak operations.
• 3.2 & 3.3 pack database - file handle reduction/avoid hitting file limit → process wide memory map pooling & mapping entire packs/indices at once
  • Note that multipack indices are related to maximizing object-count performance in conjunction with bitmaps, which is a separate topic, but in short: yes, want that, too :)
• 4.3 & 4.4 pack database - object miss → catch error, refresh packs, retry & writers force update shared memory map pool
  • we read references at well known times and assure their objects exists right away. If not, a forced (but efficient) pack refresh should make the new objects available.
  • For readers this mostly happens if external processes change the pack database, like git-maintenance, as writers keep the view on memory mapped packs fresh (efficiently) by informing about the exact changes to avoid directory scanning.