Git for Computer Scientists (2010)
Git for Computer Scientists


Abstract
Quick introduction to git
 internals for people
who are not scared by words like Directed Acyclic
Graph
.
Storage
In simplified form, git object storage is "just" a DAG of objects,
with a handful of different types of objects. They are all stored
compressed and identified by an SHA-1 hash (that, incidentally,
isn't the SHA-1 of the contents of the file they represent, but
of their representation in git).



blob: The simplest object, just a bunch of bytes. This is often
a file, but can be a symlink or pretty much anything else. The
object that points to the blob determines the semantics.



tree: Directories are represented by tree object. They
refer to blobs that have the contents of files (filename,
access mode, etc is all stored in the tree), and to other
trees for subdirectories.
When a node points to another node in the DAG, it depends on the
other node: it cannot exist without it. Nodes that nothing points
to can be garbage collected with git gc, or rescued much like
filesystem inodes with no filenames pointing to them with git fsck --lost-found.



commit: A commit refers to a tree that represents the
state of the files at the time of the commit. It also refers to
0..n other commits that are its parents. More than one
parent means the commit is a merge, no parents means it is an
initial commit, and interestingly there can be more than one
initial commit; this usually means two separate projects
merged. The body of the commit object is the commit message.



refs: References, or heads or branches, are like post-it notes
slapped on a node in the DAG. Where as the DAG only gets added to
and existing nodes cannot be mutated, the post-its can be moved
around freely. They don't get stored in the history, and they
aren't directly transferred between repositories. They act as sort
of bookmarks, "I'm working here".
git commit adds a node to the DAG and moves the post-it note
for current branch to this new node.
The HEAD ref is special in that it actually points to another
ref. It is a pointer to the currently active branch. Normal refs
are actually in a namespace heads/XXX, but you can often skip
the heads/ part.



remote refs: Remote references are post-it notes of a different
color. The difference to normal refs is the different namespace,
and the fact that remote refs are essentially controlled by the
remote server. git fetch updates them.



tag: A tag is both a node in the DAG and a post-it note (of
yet another color). A tag points to a commit, and includes
an optional message and a GPG signature.
The post-it is just a fast way to access the tag, and if lost can
be recovered from just the DAG with git fsck --lost-found.
The nodes in the DAG can be moved from repository to repository, can
be stored in more effective form (packs), and unused nodes can be
garbage collected. But in the end, a git repository is always just
a DAG and post-its.
History
So, armed with that knowledge on how git stores the version
history, how do we visualize things like merges, and how does git
differ from tools that try to manage history as linear changes per
branch.



This is the simplest repository. We have cloned a remote repository
with one commit in it.



Here we have fetched the remote and received one new commit
from the remote, but have not merged it yet.



The situation after git merge remotes/MYSERVER/master. As the
merge was a fast forward (that is, we had no new commits in our
local branch), the only thing that happened was moving our post-it
note and changing the files in our working directory respectively.



One local git commit and a git fetch later. We have both a
new local commit and a new remote commit. Clearly, a merge is
needed.



Results of git merge remotes/MYSERVER/master. Because we had
new local commits, this wasn't a fast forward, but an actual new
commit node was created in the DAG. Note how it has two parent
commits.



Here's what the tree will look after a few commits on both branches
and another merge. See the "stitching" pattern emerge? The git
DAG records exactly what the history of actions taken was.



The "stitching" pattern is somewhat tedious to read. If you have not
yet published your branch, or have clearly communicated that others
should not base their work on it, you have an alternative. You can
rebase your branch, where instead of merging, your commit is
replaced by another commit with a different parent, and your branch
is moved there.
Your old commit(s) will remain in the DAG until garbage collected.
Ignore them for now, but just know there's a way out if you screwed
up totally. If you have extra post-its pointing to your old commit,
they will remain pointing to it, and keep your old commit alive
indefinitely. That can be fairly confusing, though.
Don't rebase branches that others have created new commits on top
of. It is possible to recover from that, it's not hard, but the
extra work needed can be frustrating.



The situation after garbage collecting (or just ignoring the
unreachable commit), and creating a new commit on top of your
rebased branch.



rebase also knows how to rebase multiple commits with one
command.
That's the end of our brief intro to git for people who are not
intimidated by computer science. Hope it helped!
