Version Control System

Overview

A version control system keeps the history of a project, one saved version at a time. Each saved version is a commit: the full list of files and their contents, a message, an author, a time, and a link to the commit or commits it came from. Branches let several lines of work grow from the same point, and a merge joins two lines back together.

The problem tests whether you can pick the right data structures. Three ideas carry the design, and all three come from Git. File contents are stored by the hash of their bytes, so a file that did not change costs nothing in the next commit. Commits point at their parents, so history is a directed acyclic graph (a DAG: arrows only go backward in time, never in a loop). A branch is only a name for one commit, so creating one costs O(1).

A strong answer draws the commit graph, explains a fast-forward and a three-way merge on it, names the merge base, and writes code whose demo shows a clean merge and a conflict.

Scoping the problem

• Local only, or push and pull to a remote too? — A remote adds networking and sync — Local; remote is a follow-up
• Is there a staging area between editing and committing? — Adds the index — Yes: add, then commit
• Which merges? — Fast-forward, three-way, rebase — Fast-forward and three-way
• Conflicts at file level or line level? — Line level needs a line merge algorithm — File level; line level is a follow-up
• Directories as tree objects, or flat paths? — Trees save space for big repositories — Flat paths in the core
• Does diff show lines? — Needs a diff algorithm — Yes, a unified diff
• Several threads using one repository? — Decides the locking — Operations must be atomic

Three places a file lives

A file moves through three areas. You edit it in the working directory, add copies it into the index (the staging area, which is the next commit's snapshot), and commit freezes the index into a commit and moves the branch pointer.

Storage by content

The id of a blob is the SHA-1 hash of a short header ('blob', the size in bytes, a zero byte) followed by the content. That is exactly how Git names its blobs, and the demo checks one of Git's own published hashes. Two files with equal text get the same id and are stored once, and a commit only lists ids, so an unchanged file costs one tuple entry in the next commit.

• Blob — Hash of the content — Never: new content is a new blob
• Commit — Hash of tree, parents, message, author, time — Never: commits are frozen
• Ref (branch) — Branch name — On every commit or merge on that branch

The refs are the only part that changes. Everything else is immutable, which is why history is safe to share and cheap to cache.

The commit graph and merges

The arrows point forward in time here for reading; in the data, each commit stores its parents. Merging other into the current branch has three cases.

• Up to date — other is an ancestor of HEAD — Nothing
• Fast-forward — HEAD is an ancestor of other — Move the branch pointer to other; no new commit
• Diverged — Neither is an ancestor — Find the merge base, merge each file three ways, commit with two parents

The three-way rule compares each file in the base (B), ours (O) and theirs (T):

• O equals T — O — Both sides agree
• O equals B — T — Only theirs changed it
• T equals B — O — Only ours changed it
• All three differ — Conflict — Both changed it differently

A missing file counts as a value, so a delete on one side and no change on the other deletes the file. On a conflict the code returns the paths and does not move HEAD.

What you will be able to do

• Explain content-addressed storage and why an unchanged file costs nothing in a new commit.
• Draw the commit DAG and say why a branch is O(1) to create.
• Tell up-to-date, fast-forward and three-way merges apart, and find the merge base.
• Apply the three-way rule per file and report conflicts without moving HEAD.
• Keep every operation atomic with one repository lock.

Functional requirements

• write and delete files in a working directory; add(path) stages the change into the index
• commit(message, author, now) freezes the index into a commit and moves the current branch; an empty commit is refused
• branch(name) creates a pointer to the current commit; checkout(name) switches branches and refuses when there are uncommitted changes
• log() lists first-parent history from HEAD back to the first commit
• merge(other) reports up-to-date, fast-forwards, or does a three-way merge with a two-parent commit; conflicts are reported and HEAD does not move
• diff(a, b) returns a unified diff per changed file between two commits

Non-functional requirements

• Blobs and commits are immutable; only branch refs change
• Equal contents are stored once (content addressing)
• Creating a branch is O(1); a commit costs O(files) to list ids, not O(bytes)
• Every public operation is atomic under one repository lock
• Deterministic: time is passed in, so commit ids are stable in tests

Interview questions

• How do you find the merge base, and what if there is more than one?
• How would you merge at the line level instead of the file level?
• Storing a full snapshot per commit sounds wasteful. Is it?
• Two threads commit to the same branch at the same moment. What can go wrong?
• How would you add revert?

More Low-Level Design topics

• Tic Tac Toe
• Traffic Control System
• Trie (Prefix Tree)
• URL Shortener
• Use Case Diagram
• Vending Machine
• Visitor Pattern
• You Aren't Gonna Need It (YAGNI)