Jit Devlog #01 — Objects 101: Blobs

We start off our first devlog with an important mechanism for jit, the way that we store files in our repository. Welcome to my development journey, where I'm building my own distributed version control system. Follow along here.

Tracking Changes

For a version control system to be able to track changes for you, it must have some mechanism of storing these changes. Traditional version control would store deltas (or diffs), which are effectively just the changes that are made to a file, encoded in a way so that the system can piece together the state of a file at any given time by applying a set of deltas to some base version of the file. This is somewhat of an oversimplification, but that's the general idea.

However, git famously doesn't store deltas. At a high level, git stores snapshots of your project, which include compressed versions of each and every one of your files. If you're like me, you'd wonder "Doesn't that take up a ton of space?" For each version of the project, are we storing the entire thing again? But of course not! Instead, we store each file as a compressed content-addressable blob (Binary Large OBject).

In this entry, we'll dive into how git stores file content on your disk and get a sneak peak into how this way of storage is helpful in keeping the file system from being overloaded while continuing to provide robust version control capabilities.

Blobs

So what exactly is a blob? You can read the linked article for more detail in a database-specific context, but in general, a blob is really just a piece of data stored in binary. It's like an array (or collection) of bytes.

When you initialize your repository, git takes each of your files, compresses them using zlib, and stores them in their compressed form somewhere in the .git directory. Every git repository has this directory, and if you're curious, I encourage you to go look at what's being stored there on your own, but be careful not to edit any of the files or you run the risk of corrupting your local repository.

In the context of version control, we will refer to this compressed file as a blob, which is a type of object. There are other objects that will become very relevant later on, but for now we will focus on blobs. Blobs are compressed file contents.

Content-addressability

Each object needs some sort of ID; it needs some mechanism in place so that we can identify it later on. For git (and by extension, also for jit), blobs are content-addressable. This means that blobs can be identified in some way based on strictly the contents stored within it. Regular files on your computer are not designed this way; they are instead identified by their file names, and whatever is stored within the file does not change how they are identified (more or less).

If you've got sharp eyes, you'll realize that this method of storing blobs moves us in the right direction and provides a bit of insight into how git tracks changes. If the same file (content-wise) appears in multiple different versions of the codebase, we do not store multiple different copies of these files, but instead just reference a single blob. Moreover, if you have multiple files (even if they have different names) that have the exact same content in different locations within your repository, these will refer to the exact same blob too! So we get the added benefit of saving on storage here as well.

Blob IDs & Hash Functions

That's cool stuff, but how do we actually derive our object ID from the contents of a file? In short, we hash a string containing the file contents with a small header prepended to the start. This "header" is quite simple and is usually just the text blob <content_size>\0.

A hash function takes a piece of data as input and outputs a piece of nondescript text that is very difficult to reverse-engineer. Without going into specifics, a hash function should have the following properties:

1. It is "easy" to compute, but its inverse is computationally difficult to produce. Given a piece of data x, we can run x through a hash function relatively easily and get an output h, but if we were given some hash h, it is difficult to retrieve the input that would have produced h via the hash function.
2. For any input x, it is difficult to find another different input y where the hash function would give you the same output.

When I say "difficult" I really mean computationally impossible. There are many reasons for why this is the case, and if you're curious, you can read more about hash functions and cryptography online, but the most important takeaway for us here is that two files that store different content will give us different hashes the vast majority of the time. A more secure ("better") hash function will have a lower chance of collisions (the situation in which two unique inputs give the same output).

Example

Here's an example of how we would construct the ID for a blob given its source file. Suppose we have the following file:

Hello World!

We would read the contents, and end up constructing a string of the form:

"blob 12\0Hello World!"

Passing this entire string through a hash function would then give us the object ID we use to identify the contents of file.txt:

980a0d5f19a64b4b30a87d4206aade58726b60e3

Putting it all Together

With all of that information in mind, we can now describe the complete flow that git follows when it needs to store a file in the repository.

1. Read the file contents and create a string of the form blob <content_size>\0.
2. Put this string through a hash function to obtain the file's object ID.
3. Compress the original file using zlib.
4. Store the compressed file somewhere in the .git directory in the root of your repository named by its object ID.

Where in .git?

git stores objects in the .git/objects/ directory, but we don't just store all our objects here in this one folder; if we did, the the file system would run into issues when trying to list the directory as it grows larger. We instead sort objects into buckets keyed by the first 2 hex digits of its object ID.

For instance, file.txt from our earlier example results in object ID 980a0d5f19a64b4b30a87d4206aade58726b60e3, so the compressed file contents would be stored at .git/objects/98/0a0d5f19a64b4b30a87d4206aade58726b60e3. This way, objects with the same first 2 hex digits will be stored in the same folder, and the file system won't be overwhelmed with entries as the repository grows.

The Result

The result of all our hard work so far is the ability to store compressed versions of files in our repository. At the time of writing, I have implemented object ID generation given a file path for jit, and I plan to implement a CLI dispatcher with support for sub-commands before I write jit's first command: jit init, which will create the .jit directory in the repository root and index the files in the folder, storing them as objects.

There's a lot more learning that happened during the implementation, and although I think those lessons are valuable, I figured they may be a little too "in the weeds" to put in this post. Although I do plan on putting up a post with some things I went through implementing this in C, since there were some headaches, and even though the process is simple at a high level, there's lots of work to do during implementation that goes unseen.

Thanks for reading.