0
$\begingroup$

Say you are editing a document like a 1000 page book. There are 20 authors all working furiously to edit the book. Every day they are merging their changes 2 or 3 times with the main branch. According to my understanding of git snapshots, this would create a new copy of the document every merge, so by the end of a year there would be $20 \times (2..3) \times 365 = 9125$ copies of that 1000 page file, each with their own snapshot. If that file was 50MB, that could potentially be ~450 GB of storage required (if I am calculating correctly). I am not sure yet how packing would help, it might though, but still this is a lot of extra data, when the change set might be fairly small relatively speaking, only a few lines or paragraphs here and there for each commit.

Same with editing structured data. Say you have one "file" which is 1 million records in a CSV or indexed data structure, and thousands of records are edited every day. This would explode the amount of disk usage required for git to keep versioned snapshots of the file.

What are solutions to this problem? Ideally only focusing on structured tree data like XML files, but if I could ask for one more it would be arbitrarily large text files like a book. But most important for my current task is diffing on trees. I found Precise Version Control of Trees with Line-based Version Control Systems and other XML related tree-versioning systems, but I wonder why they are not mainstream (or why I have missed them if they are).

I would like to build a sort of versioned XML database and wondering what the cutting edge is in terms of getting git-like branching/merging, to commit history and navigating to old folder hierarchies, to the performance/speed of doing a commit or clone (instant for all intents and purposes, compared to subversion). Have these problems been solved in one way or another, or is it still an open research question?

My wishlist would be:

  1. Fast reads and writes to the "package" or central data repository.
  2. Fast commits.
  3. Compact data representation to avoid the disk space explosion problem of git on these types of data.
  4. Fast navigation between commits and branches.
  5. Many people could be branching and merging at the same time as easily as git.
$\endgroup$

1 Answer 1

2
$\begingroup$

With Git, you have to distinguish between three different things:

  • The Abstract Git Object Model which sits at the core of Git.
  • The Storage Format which sits underneath the Object Model.
  • The surface interpretation of that Object Model by the Git command-line tools.

Git Object Model

The Git Object Model is very similar to the design of the Unix filesystem, which is not surprising given that Git was designed by the author of a Unix-like Operating System. The major difference to a traditional filesystem is that Git is content-addressable.

Adress space

All Git Objects live in the same address space. The address of an object is a hash of its content. Hence, two objects with the same content have the same address and are thus indistinguishable … or in other words, they aren't two objects, they are one and the same.

At the moment, that hash is SHA-1, but a design for moving to SHA-256 was created in 2017 and the implementation is now in an alpha-stage.

Content address

Each Git Object has an Object Header. The Object Header is

  1. An ASCII string describing the type of the object, e.g. blob, tree, commit, etc. followed by …
  2. An ASCII space character followed by …
  3. The length of the content in octets, encoded as a series of ASCII digits followed by …
  4. a NUL octet.

This is then followed by the actual content of the object.

The address of the object is the hash of the whole thing, i.e. the header followed by the content.

Blob

The simplest kind of object in the Git Object Model is the blob. A blob is just an un-typed un-structured sequence of octets. It is the equivalent to a file in Unix.

Its structure is extremely simple: it is just the object header (with type blob) followed by the octet sequence.

Tree

A tree associates names with blobs (and trees). A tree is a set of name→object mappings. Trees in Git are the equivalent to directories in Unix and the name→object mappings are the equivalent of a hardlink.

In addition to the name→object mapping, a tree also stores some metadata about the mapping, in particular, permissions. This is different from Unix, where the permissions are a property of the file, not the link!

For the purpose of hashing the content of the tree, the content is encoded into a well-defined format with a well-defined ordering of the mappings.

Commit

A commit records a specific state of a tree at a specific time by a specific person and associates a descriptive message with that state.

A commit consists of the following:

  • Exactly one tree.
  • Zero or more parent commits.
  • A committer name.
  • A commit timestamp.
  • An author name.
  • An authoring timestamp.
  • A commit message.
  • An optional digital signature.

The address is again based on a well-defined encoding of those fields.

(Annotated) Tag

An (annotated) tag gives a human-readable name and description to a commit.

A tag consists of the following:

  • A commit.
  • A tagger name.
  • A tag timestamp.
  • A tag name.
  • A tag message.
  • An optional digital signature.

References

References are actually not part of the object model. They are just names assigned to objects (mostly commits). This applies for example both to branches and (non-annotated) tags.

The Storage Format

Loose

A naïve way of storing Git Objects would be to just store each object as a separate file with the address as the name. And in fact, a slight variation of this naïve format (which uses the first two characters of the hexadecimal encoding of the address to create a directory tree in order to avoid having too many files in a single directory) was the original storage format for Git and it is still in limited use today. Nowadays, it is called the loose object format as opposed to the newer packed object format.

As you rightly pointed out in your question, this format could potentially waste a lot of space. Although it does not actually take up as much space as you would think:

  • Remember that two objects which have the same content are the same object. So, a file that is not changed between two commits is only stored once.
  • In fact, this does not only apply to different versions of a single repository. Two files anywhere in the world in completely unrelated repositories which have the same content will have the same address. If you think about a service like GitHub which stores many different unrelated repositories, there will for example only be one copy of the license text of the GPL in the entirety of GitHub, since the text is always the same in every version of every repository that contains the GPL license, the address will always be the same. (Modulo things like Unix vs. DOS line endings or whether or not the file ends with an empty line.)
  • Only blobs are big, all other objects are tiny since they mostly contain just addresses of other objects. (Unless you write a 100000 word commit message …)
  • All objects are stored deflate-compressed. This means that anything which compresses well, such as text (that means both your book as well as your hypothetical 100000 word commit message) will not use much storage space.

Packed

However, that is not actually how Git stores objects long-term. Whenever you perform an operation which adds new objects to the object storage, Git will check a number of statistics and compare them against a set of configurable thresholds. If it finds that one of the statistics (e.g. number of loose objects) is higher than the threshold, it will pack the loose objects into a packfile.

A packfile is simply all content of the loose objects concatenated together and then xxdelta-compressed. Next to the packfile, there is an index which maps addresses to offsets within the packfile so you can find your objects again.

At some point, you will then find yourself with a small number of loose objects and a growing number of packfiles and indices, but you can again apply some statistics and repack those individual packfiles and loose objects into a single packfile containing your entire repository.

Since there are lot of similarities between the objects (e.g. two consecutive versions of a blob will be almost identical, or many commits will have the same committer), there is a lot of redundancy in the packfile, and it compresses very well. In fact, Git uses some additional heuristics to optimize the placement of the objects inside of the packfile to make it easier on the compression algorithm and keep runs of octets that are likely to be similar closer together.

Note! I am not actually sure whether all of these heuristics are used, but I am going to list some examples of what could be useful:

  • Blobs which are assigned the same name in trees are kept close together, under the assumption that they are all the same file with only small changes between them.
    • This is further optimized by also taking into account how many commits there are in between the two versions, putting consecutive versions closer together.
  • Blobs which are assigned names with the same file extension are kept closer together, under the assumption that e.g. C files will be similar to each other (e.g. by all beginning with the same copyright statement or a documentation comment), HTML files will be similar to each other, etc.
  • Objects of the same type are kept closer together, under the assumption that e.g. commits will only contain the names of a small number of committers over and over again, or trees will point to mostly unchanged blobs with mostly the same names, etc.

Based on these heuristics and the packfile format, Git can often eliminate redundancies between consecutive versions of files (as a difference-based SCM would) but even between similar runs of content in totally unrelated files (such as identical copyright statements at the top of every source file). As a result, Git repositories are often smaller than the equivalent repository in a different, difference-based SCM. For example, when I converted all my old Subversion repositories back in 2005, I got a significant reduction in storage space.

Aside: network protocol

The network protocol is also based on packfiles. The client can request from the server a certain set of objects, e.g. based on a range of references or commits, and the server will send all of the objects needed to reconstruct everything within that range to the client. What it is actually sending is one or more packfiles which contain (at least) those objects. Theoretically, the server could just always keep the repository fully packed and blindly send the full packfile on every request (since it will by definition include all objects the client asked for because it contains every object in the repository), but that would be inefficient. In reality, there is a balancing act of tradeoffs whether or not and how much the server repacks the data so that it only contains what the client needs.

Abstraction

Note that in the standard implementation(s) of Git (the original Git CLI tools and libgit2) as well as in many alternative implementations (e.g. JGit, Git#, etc.), the storage format and the object model are kept well abstracted from each other. This allows companies like GitHub to completely replace the storage format with a custom one that is more suited for their application and scale.

For example, I have seen people replace the storage backend with a database. There are browser-based Git implementations which use HTML5 Local Storage. And of course, GitHub's secret sauce when it comes to performance is their completely custom storage backend.

Interpretation

You might have noticed that I talked about for example blobs and trees in very abstract terms. I never wrote they are files and directories, because as far as large parts of Git are concerned, they don't know anything about files or directories. The storage backend isn't even necessarily concerned about trees or blobs or commits! It only cares about objects.

The only thing in the entire object model that breaks this nice conceptual separation are the permission bits in the trees.

It is only the high-level surface tools like git checkout which then interpret trees as directories and blobs as files. But that is only an interpretation of the object model, and just like the storage backend is neatly abstracted, so are the high-level surface tools. You can replace the tools with your own, and thus supply your own interpretation.

For example, there are Wikis which use Git as their backend. Here, blobs are pages, not files, and trees represent page nesting, not directories. Some Smalltalk systems use Git as a versioned object database.

Within Git itself, there are Git Notes which are a kind of versioned metadata for Git objects.

So, in your world, you could interpret blobs as paragraphs and trees as chapters, for example. I myself have experimented with interpreting blobs as methods and trees as classes.

Summary

So, in short: Git has solved all your problems already, you just need to change your viewpoint of what "Git" is a little bit.

At its core, Git is a content-addressable versioned object database with a space-efficient storage backend (that can be swapped out if needed) and only a thin (and optional!) veneer on top that interprets those objects as files and directories.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.