Skip to content
LumenaryAcademy
Engineering 75 min

Version control with Git

Snapshots, hashes and a graph of history — how Git works inside, and how teams work with it.

Code tested · 5AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

Why version control?

Every professional codebase lives in a version control system, and the reasons are more than "backup".

  • Undo, at any scale. A change from last Tuesday broke the payment page. You can see exactly what changed, and revert just that change, without losing the work done since.
  • History as documentation. Six months from now someone will ask "why does this function round down instead of to the nearest cent?" A good history answers in one command: the commit that introduced the line, who wrote it, when, and — if the message is good — why.
  • Parallel work. Forty engineers change one codebase at once. Each works on a branch, isolated from the others' half-finished changes, and merges when ready.
  • Review and accountability. Changes are proposed, discussed and approved before they reach the main line, and the record of that discussion is kept.
  • Reproducibility. "Which code is running in production?" has a precise answer: a commit hash. So does "which code produced the numbers in this paper?"

Without version control, teams reinvent it badly: folders named final_v3_really_final, emailed zip files, and the special dread of two people editing the same file. Git, created in 2005, is now the overwhelmingly dominant system. This lesson explains how Git works inside, because nearly every confusing Git situation becomes simple once you can picture the objects and the graph, and then how teams use it day to day.

IntuitionH

Commits are snapshots, named by their content

The single most useful fact about Git: a commit is a snapshot of the entire project, not a list of changes. When you ask Git for a diff, it computes one by comparing two snapshots. (On disk, Git does compress similar objects as deltas inside packfiles, but that is a storage optimisation invisible to the model.)

Storing a full snapshot every commit sounds wasteful, and would be, but for the second key idea: content addressing. Every object Git stores is named by a cryptographic hash of its contents. A file that did not change between commits has the same contents, therefore the same hash, therefore it is the same object, stored once. A snapshot is cheap because it mostly consists of pointers to objects that already exist.

Content addressing gives three more properties for free:

  • Integrity. If a single bit of a stored object is corrupted or tampered with, its hash no longer matches its name.
  • Cheap comparison. Two directories with the same hash have identical contents, all the way down; Git never needs to look inside them.
  • Global names. A hash means the same thing in every clone of the repository, on every machine, without any central authority handing out numbers.

You met hash functions in Hash tables; Git's hashes are cryptographic, which means that finding two different inputs with the same hash is meant to be infeasible. Applied cryptography explains what that requires.

DefinitionsH

The object model

Definition— Git objects

Git's database holds four kinds of immutable objects, each named by the SHA-1 hash of a short header (<kind> <size> and a zero byte) followed by its contents:

  • a blob holds the bytes of one file (no name, no permissions — just contents);
  • a tree holds one directory: a sorted list of entries, each a mode, a name, and the hash of a blob or a subtree;
  • a commit holds the hash of the root tree, the hashes of zero or more parent commits, author and committer lines with timestamps, and a message;
  • an annotated tag names another object with a message and, usually, a signature.

Definition— Refs, branches and HEAD

A ref is a human-readable name for a commit hash. A branch is a ref that moves forward automatically when you commit on it; it is nothing more than a file containing 40 hexadecimal characters. HEAD says what you are working on: normally it names a branch ("HEAD is main"), and in detached HEAD state it names a commit directly.

commit 4305a80commit e6e3648parentroot tree d4d3770root tree 3e42dbctree src ef6ad67blob README 4390652tree src b6dcf64blob app.py 11b15b1blob app.py 9f69d32
Two commits sharing structure. The second commit changed only src/app.py, so it adds a new blob, a new src tree, a new root tree and itself; README.md's blob is shared.

Because each commit names its parents by hash, the history forms a directed acyclic graph (DAG): edges point from child to parent, and a cycle would require a commit to contain its own hash. A merge commit has two parents; the first commit has none. "Is commit X included in branch Y?" is the question "is X an ancestor of Y in the graph?" — the reachability you studied in Graphs. The ancestor relation is a partial order, a structure studied in Orders and lattices.

And because a commit contains its parent's hash, which depends on its parent's hash, and so on, a commit hash pins down the entire history behind it. A tree of hashes in which each node's hash covers its children is called a Merkle tree; Git's history is a Merkle DAG.

ComputationC

Building Git's object store in Python

The following model stores objects exactly as Git does — header, zero byte, contents, SHA-1 — so the hashes it prints are the ones real Git computes for the same files, author and timestamps. (Try printf 'hello world\n' | git hash-object --stdin in a terminal.)

python
import hashlib
import zlib

class ObjectStore:
    """Git's object database in miniature: each object is stored under the hash of its bytes."""
    def __init__(self):
        self.objects = {}

    def put(self, kind, body):
        data = f"{kind} {len(body)}".encode() + b"\0" + body
        oid = hashlib.sha1(data).hexdigest()
        self.objects[oid] = zlib.compress(data)      # Git stores loose objects zlib-compressed too
        return oid

    def get(self, oid):
        data = zlib.decompress(self.objects[oid])
        header, _, body = data.partition(b"\0")
        assert hashlib.sha1(data).hexdigest() == oid, "corrupted object!"
        return header.decode().split()[0], body

def blob(store, text):
    return store.put("blob", text.encode())

def tree(store, entries):
    """entries maps a name to (mode, oid); Git sorts by name and stores raw 20-byte hashes."""
    body = b"".join(f"{mode} {name}".encode() + b"\0" + bytes.fromhex(oid)
                    for name, (mode, oid) in sorted(entries.items()))
    return store.put("tree", body)

def commit(store, tree_oid, parents, message, when):
    who = "Ngozi Okafor <ngozi@example.org>"
    lines = [f"tree {tree_oid}"] + [f"parent {p}" for p in parents]
    lines += [f"author {who} {when} +0000", f"committer {who} {when} +0000", "", message]
    return store.put("commit", ("\n".join(lines) + "\n").encode())

FILE, DIR = "100644", "40000"
store = ObjectStore()
print("blob of 'hello world\\n':", blob(store, "hello world\n"))
store = ObjectStore()

# Commit 1: README.md and src/app.py
readme = blob(store, "# Weather station\n")
app_v1 = blob(store, 'print("hello")\n')
src_v1 = tree(store, {"app.py": (FILE, app_v1)})
root_v1 = tree(store, {"README.md": (FILE, readme), "src": (DIR, src_v1)})
c1 = commit(store, root_v1, [], "Add weather station skeleton", when=1767225600)
print(f"commit 1 {c1}   objects in store: {len(store.objects)}")

# Commit 2: change only src/app.py
app_v2 = blob(store, 'print("hello, world")\n')
src_v2 = tree(store, {"app.py": (FILE, app_v2)})
root_v2 = tree(store, {"README.md": (FILE, readme), "src": (DIR, src_v2)})
c2 = commit(store, root_v2, [c1], "Greet the whole world", when=1767229200)
print(f"commit 2 {c2}   objects in store: {len(store.objects)}")
print()

kind, body = store.get(c2)                           # like `git cat-file -p <commit>`
print(f"{kind} {c2[:7]}:\n{body.decode()}")

# Tamper with commit 1's message: a different hash, so commit 2's parent link no longer matches it.
forged = commit(store, root_v1, [], "Add weather station skeleton (edited)", when=1767225600)
print("original commit 1:", c1)
print("edited commit 1:  ", forged)
print(f"commit 2 ({c2[:7]}) still records parent {c1[:7]}: the edited commit is not in its history.")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Count the objects: the first commit creates five (two blobs, two trees, one commit). The second creates four, not five: the README's blob is reused, while the change to app.py forces a new blob, a new src tree (its entry changed), a new root tree (its src entry changed) and the commit. A change deep in a large project creates one new tree per directory on the path to the root, and shares everything else. That is why Git can afford snapshots.

ExplanationH

Branches, merges and conflicts

Because a branch is just a pointer, creating one costs a few bytes, and switching branches rewrites only the files that differ. That is why teams branch for every change.

bash
git switch -c fix/rain-gauge-units      # create a branch at HEAD and move HEAD to it
# ... edit files ...
git add -p                              # choose, hunk by hunk, what goes into the commit
git commit                              # opens an editor for the message
git log --oneline --graph --all         # draw the commit graph

When it is time to combine work, Git looks at the graph. If main has not moved since the branch was created, main's commit is an ancestor of the branch's tip, and a merge is a fast-forward: the main pointer simply moves forward. Otherwise Git performs a three-way merge. It finds the merge base — the best common ancestor of the two tips — and compares each side against it:

  • a file changed on only one side takes that side's version;
  • a file changed identically on both sides takes that version;
  • a file changed differently on both sides is merged line by line, using the same rule on regions of lines; overlapping changes to the same region are a conflict.

The result is recorded as a merge commit with two parents. Here is that logic at the level of whole files, with letters standing for commit hashes:

python
parents = {"A": [], "B": ["A"], "C": ["B"], "D": ["B"], "E": ["D"]}   # main: A-B-C, feature: B-D-E
snapshots = {
    "B": {"README.md": "v1", "units.py": "v1", "plot.py": "v1"},
    "C": {"README.md": "v2 (main)", "units.py": "v1", "plot.py": "v2 (main)"},
    "E": {"README.md": "v1", "units.py": "v2 (feature)", "plot.py": "v2 (feature)", "rain.py": "new"},
}

def ancestors(commit):
    """Every commit reachable from `commit`, including itself."""
    seen, todo = set(), [commit]
    while todo:
        c = todo.pop()
        if c not in seen:
            seen.add(c)
            todo.extend(parents[c])
    return seen

def merge_base(a, b):
    common = ancestors(a) & ancestors(b)
    # the best common ancestors are those not reachable from another common ancestor
    best = [c for c in common if not any(c != d and c in ancestors(d) for d in common)]
    return sorted(best)

def merge3(base, ours, theirs):
    merged, conflicts = {}, []
    for path in sorted(set(base) | set(ours) | set(theirs)):
        b, o, t = base.get(path), ours.get(path), theirs.get(path)
        if o == t:          # same on both sides (or deleted on both)
            result = o
        elif o == b:        # only theirs changed it
            result = t
        elif t == b:        # only ours changed it
            result = o
        else:               # both changed it, differently
            conflicts.append(path)
            result = f"<<<<<<< ours: {o} ||||||| base: {b} ======= theirs: {t} >>>>>>>"
        if result is not None:
            merged[path] = result
    return merged, conflicts

print("merge base of main (C) and feature (E):", merge_base("C", "E"))
print("fast-forward possible?", "C" in ancestors("E"))
merged, conflicts = merge3(snapshots["B"], snapshots["C"], snapshots["E"])
for path, content in merged.items():
    print(f"  {path:10} {content}")
print("conflicts:", conflicts)
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Notice that the merge needs the base. Comparing only the two tips, Git could not tell whether README.md was changed on main or reverted on the feature branch; the base shows that only main touched it. This is also why resolving a conflict well means understanding three versions. Turn on git config --global merge.conflictStyle zdiff3 and Git's conflict markers include the base version between ||||||| and =======, so you can see what each side was trying to do.

A good conflict resolution:

  1. Read the base, ours and theirs, and state in words what each side intended ("main renamed the unit to mm; the feature added a new caller using inches").
  2. Write code that achieves both intentions, which is often neither side verbatim.
  3. Run the tests: a merge with no textual conflict can still be semantically wrong, for instance when one side renames a function and the other adds a call to the old name.
ExplanationH

Rebasing: replaying work on a new base

Rebasing is the alternative to merging. Instead of tying two lines of history together with a merge commit, git rebase main takes the commits on your branch that are not on main, and replays them one at a time on top of main's tip, producing a linear history.

bash
git fetch origin
git rebase origin/main                  # replay my branch's commits onto the latest main
# if a commit conflicts: fix the files, then
git add units.py && git rebase --continue
git push --force-with-lease             # update my branch on the server (see below)

The object model explains everything about rebasing. A replayed commit has the same changes but a different parent, so its contents differ, so its hash differs: rebasing does not move commits, it creates new ones and moves the branch pointer to them. The old commits still exist until garbage collection, which is why git reflog can rescue you from a rebase gone wrong.

It also explains the one rule that matters: do not rebase commits that other people have already built on. If a colleague's branch descends from your old commits and you replace them with new ones, their history and yours now disagree about what happened, and reconciling them is miserable. Rebasing your own unpublished work, or your own feature branch before review, is fine and common. When you must update a branch you have already pushed, use --force-with-lease, which refuses to overwrite the server's branch if someone else has pushed to it since you last fetched.

Teams choose a convention and write it down. Some merge feature branches with merge commits, preserving exactly what happened; some rebase or squash-merge (collapse a branch into one commit on main) for a linear history that is easier to read and to bisect. Each is a reasonable choice; mixing them by accident is not.

ExplanationH

Remotes, pull requests and code review

Git is distributed: every clone has the full history and can commit offline. A remote is another copy you exchange objects with, conventionally called origin. git fetch downloads new objects and updates remote-tracking branches such as origin/main — your read-only record of where the server's branches were when you last fetched. git pull is fetch followed by a merge (or rebase) into your current branch; git push uploads your objects and asks the server to move its branch pointer, which it does only if that is a fast-forward unless you force it.

On top of this, hosting services — GitHub, GitLab, Bitbucket, Gitea and others — add the pull request (GitLab calls it a merge request): a proposal to merge a branch, with a diff, a discussion thread, automated checks from continuous integration, and required approvals before the merge button works. Large companies use the same flow, sometimes on their own tools; the essentials are identical.

Code review that works

Code review catches defects, but its larger value is shared understanding: at least two people know every change, and the codebase's conventions spread. Habits that make it work:

As an author

  • Keep changes small and focused. A 200-line pull request gets a careful review; a 2,000-line one gets a skim. Split refactors from behaviour changes.
  • Explain why, in the description: the problem, the approach, what you considered and rejected, how you tested it. Link the issue.
  • Review your own diff first. You will find the debugging print and the commented-out block before anyone else has to.
  • Respond to every comment, with a change or a reason. Disagreement is fine; silence is not.

As a reviewer

  • Review promptly. A pull request waiting two days blocks a colleague and invites merge conflicts.
  • Prioritise: correctness, design, tests and clarity before style. Let formatters and linters enforce style automatically, so humans never argue about it.
  • Comment on the code, not the person, and ask rather than command: "What happens here if the list is empty?" teaches more than "This is wrong." Label optional suggestions ("nit:") so the author knows what blocks approval.
  • Approve when the change makes the codebase better, even if it is not exactly how you would have written it. Google's public review guide states the standard as improving overall code health rather than demanding perfection.

A good commit message

A commit message is a letter to a future maintainer — possibly you — who has the diff but not your context. The conventions Git's own tools assume:

text
Convert rain gauge readings to millimetres at ingestion

Gauges from two suppliers report in hundredths of an inch, and we
converted them only when drawing charts. Daily totals in the API were
therefore 25.4 times too small for stations in Kisumu and Recife.

Convert once, when a reading is stored, and add a units column so the
original value is never lost. Existing rows are migrated in 0042.

Fixes #318
  • A summary line of about 50 characters, in the imperative mood ("Convert …", as if completing "If applied, this commit will …"), with no full stop.
  • A blank line, then a body wrapped at about 72 characters explaining what and especially why: the diff already shows how.
  • References to issues or tickets at the end.

Compare "fix bug", "wip" and "changes" — the most common messages in many repositories, and useless to every future reader. Some teams also adopt a structured format such as Conventional Commits (fix(ingest): …) so tools can generate changelogs.

Common misconceptionsH

Common misconceptions

Misconception

"A branch is a copy of the code." A branch is a 41-byte file holding a commit hash. Creating one copies nothing, which is why it is instant even in a repository with millions of files.

Misconception

"Deleting a branch, or a bad reset, destroys my commits." Commits become unreachable, not deleted. git reflog records where HEAD and each branch have pointed recently, and unreachable objects survive until garbage collection prunes them (by default, not for weeks). Uncommitted changes are another matter: commit early and often.

Misconception

"No merge conflict means the merge is correct." Git merges text. If one branch renames a function and another adds a new call to the old name, the text merges cleanly and the program does not build. Continuous integration that runs the tests on the merged result is the real safeguard.

Misconception

"SHA-1 is broken, so Git's history can be forged." In 2017 researchers produced the first SHA-1 collision (two PDFs with the same hash; see shattered.io). Git responded by switching to a hardened SHA-1 implementation that detects such collision attacks, and has added support for SHA-256 repositories; see the hash function transition document in the references. For authenticity — proving who made a commit — teams sign commits or tags, because a hash alone proves integrity, not identity.

History & global context

A short history

Early systems such as SCCS (1972) and RCS (1982) tracked the history of individual files on one machine. CVS (1990) and Subversion (2000) put a single central server in charge of the whole project's history, so committing, and often even viewing history, required a connection to it. Distributed systems gave every developer the complete history.

The Linux kernel project used the proprietary distributed system BitKeeper from 2002 until its free licence was withdrawn in April 2005. Linus Torvalds wrote the first version of Git within weeks, designing it around speed, integrity via hashing, and support for thousands of parallel branches; Junio Hamano became its maintainer that July and still is. Mercurial appeared the same month with similar ideas. GitHub launched in 2008 and made the pull request the standard unit of collaboration for open-source projects and, later, for most companies.

Exercises

Exercises

1. Version control with Git

Warm-upComputational

Write git_blob_hash(data), which takes the contents of a file as bytes and returns the 40-character hexadecimal name Git gives it as a blob: the SHA-1 of the header blob <size>, a zero byte, and the contents. Check: git_blob_hash(b"hello world\n") is 3b18e512dba79e4c8300dd08aeb37f8e728b8dad.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

2. Version control with Git

CoreHuman

A repository's latest commit contains README.md, docs/guide.md and src/station/sensors.py, so its root tree has entries README.md, docs and src, and src contains the directory station. You edit only src/station/sensors.py and commit. How many new objects does Git create for this commit?

3. Version control with Git

CoreHuman

After git rebase main, every commit on your feature branch has a new hash, even though the changes in each commit look the same. Why?

Choose one

4. Version control with Git

CoreComputational

A commit graph is given as a dictionary parents mapping each commit id to the list of its parents. Write merge_base(parents, a, b), which returns the best common ancestor of commits a and b: a commit that is an ancestor of both (a commit counts as its own ancestor) and is not an ancestor of any other common ancestor. The tests only use graphs where this commit is unique.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

5. Version control with Git

CoreComputational

Implement a file-level three-way merge. merge3(base, ours, theirs) takes three snapshots, each a dictionary from path to contents (a missing path means the file does not exist in that snapshot). It returns (merged, conflicts): the merged snapshot as a dictionary, and a sorted list of paths that conflict. Rules for each path:

  • the same in ours and theirs (including both deleted): take it;
  • unchanged from base on one side: take the other side (which may be a deletion or an addition);
  • otherwise it is a conflict: keep our version in merged (or leave it out if we deleted it) and list the path in conflicts.
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Version control with Git

Warm-upHuman

You created feature from main and made three commits on it. Nobody has committed to main since. What happens when you run git switch main and then git merge feature?

Choose one

7. Version control with Git

Warm-upHuman

Which commit message best follows the conventions in the lesson?

Choose one

8. Version control with Git

CoreHuman

You are reviewing a pull request that adds retry logic to a function uploading sensor readings. You notice the loop retries forever if the server keeps failing. Which comment is most effective?

Choose one

Further reading and resources