Design a source control system

01The design, in the six-step framework

1. Requirements

Interviewers often start by asking whether you would model it on Git or Perforce and then probe the consequences. Pick a content-addressed model with centralised history, say why, and design the service around a monorepo.

Functional

• Commit, branch, merge, diff, blame and log over a single repository with 100 million files.
• Check out any directory subtree without downloading the whole repository.
• Code review with proposed changes that run presubmit checks before merging.
• Permissions per directory; some files are secret even inside the company.
• Out of scope: the build system, the code review UI beyond its data needs.

Non-functional

• Scale: 50,000 engineers, 100,000 commits a day, 2 billion lines of code, repository history 100 TB.
• Latency: a file read or blame under 300 ms; a commit acknowledged under 2 seconds; a merge of a small change under 5 seconds.
• Consistency: linear history on the main branch; a commit, once acknowledged, is never lost or reordered.
• Availability: 99.95 percent for reads and commits worldwide.

2. Core entities

• Blob: hash of file content, the bytes (deduplicated).
• Tree: hash, list of (name, mode, child hash) entries: a directory snapshot.
• Commit: hash, root tree hash, parent commit hashes, author, message, timestamp, sequence number on its branch.
• Ref: branch or tag name → commit hash; the only mutable thing.
• Change (proposed commit): change id, base commit, diff, reviewers, presubmit results, status.

3. API

• GET /objects/{hash} returns a blob, tree or commit; immutable, cacheable for ever.
• GET /refs/{branch} returns the current head; POST /refs/{branch} with expected old hash and new hash performs the atomic update (compare-and-swap).
• POST /changes submits a diff against a base commit; POST /changes/{id}/submit asks the server to rebase, run presubmits and merge.
• GET /blame?path=&at=commit and GET /log?path=&from= for history queries over a path.

4. High-level design

1. The client never clones 100 TB. A virtual filesystem fetches trees and blobs by hash on demand from the regional object cache, which serves immutable objects from object storage.
2. An engineer uploads a change: new blobs and trees are written to the object store (content-addressed, so unchanged files cost nothing), and a change record points at them.
3. Submit goes through a queue: the service rebases the change onto the current head, runs presubmit checks, and if they pass performs a compare-and-swap on the branch ref.
4. The history indexer tails ref updates and updates per-path indexes so blame and log do not walk the whole commit graph.

5. Deep dives

Git or Perforce, and what does the answer change?

Git's model (content-addressed blobs, trees and commits; branches as pointers) gives deduplication, cheap branching and integrity for free, because every object is named by its hash. Git's distribution model (every clone has all history) does not survive a 100 TB monorepo. So take the object model and reject full clones: keep history on the server, give clients a lazy virtual filesystem, and make the server the only place where the main branch moves. That is closer to Perforce in operation and to Git in storage. Say this trade explicitly: offline work is limited to files already fetched, and in return every engineer sees one linear history and checkouts are seconds, not hours.

How does the main branch accept 30 commits a second serially without a queue a mile long?

The ref update is a compare-and-swap on a consensus-replicated record, which handles thousands of CAS per second; the bottleneck is rebasing and presubmit, which take seconds to minutes. Run them in parallel against the current head, then submit in a queue: a change whose base is still the head commits at once; a change whose base moved is rebased again, and if the files it touched do not overlap the intervening commits, the presubmit result is reused and it commits without re-running. Only truly conflicting changes wait for a human. With 30 submits a second and typical changes touching disjoint files, the queue stays short; batch submission (merge several non-overlapping changes as one head move, test once) is the lever if it does not.

How are blame and log fast on a path with a million commits in its ancestry?

Walking commit history and diffing trees is linear in history depth. Instead maintain a per-path history index: for each path, the list of commits that changed it, in branch order, built by the indexer as commits land. Log is a range read of that list. Blame is computed once per (path, commit) and cached as a mapping from line ranges to commits; a new commit's blame is derived from its parent's blame plus the diff, which is incremental and cheap. The index is sharded by path prefix and lives in a wide-column store sorted by path then commit sequence.

How do permissions work on a content-addressed store?

Object hashes are not secrets, so authorisation is enforced by path, not by hash. Every object read is requested through a path and a commit; the object service checks that the caller may read that path at that commit before returning the bytes. Trees for restricted directories are stored with the same mechanism, and the virtual filesystem simply shows a restricted directory as empty. Secrets are not committed; a presubmit check blocks known secret patterns, which is the control that actually matters.

How does the system stay available across regions?

Objects are immutable and replicated to every region's object store asynchronously, so reads are served locally and a missing object is fetched from the home region on first access. Refs are the only mutable state and live in a consensus group with members in three regions; a CAS on the main branch pays one cross-region round trip, about 100 ms, which is invisible inside a submit that already takes seconds. If the leader region is lost, the consensus group elects a new leader and the submit queue resumes within a minute; no acknowledged commit is lost because a ref update is acknowledged only after a majority has it. The history index is derived data and can be rebuilt from the refs and objects, so it is replicated best-effort and repaired by the indexer.

6. What a strong answer sounds like

• Choose the model and defend it: Git's object model, server-side history, lazy checkout, one serial branch.
• Show that reads are immutable-object fetches, so caching solves them, and the serial submit path is the real design problem.
• Explain the submit queue with rebase, presubmit reuse and batching.
• Give the per-path history index that makes blame and log O(changes to the path), not O(all commits).
• Follow-ups to expect: very large binary files (chunk them so small edits do not re-upload gigabytes), cross-region latency for the ref CAS (one leader region, commits pay a round trip), and garbage collection of unreachable objects (reference counting from refs, run as a batch job with a grace period).

02Where this question was reported

• IGotAnOffer · SWE list
• Blind · Candidate picks perforce or git, then interviewer probes why