Question 1

How would you design the object store for a version control system like Git?

Accepted Answer

Use a content-addressable store keyed by SHA-256 hash of the object's content. Store four object types: blobs (file contents), trees (directory listings with mode, name, and child hash), commits (tree pointer, parent commit hashes, author metadata, message), and tags. Write objects immutably to a flat-file store partitioned by the first two hex digits of the hash (e.g., .git/objects/ab/cd1234...) to limit directory fan-out. Pack loose objects periodically into packfiles with delta compression to reduce storage. A content-addressable design gives deduplication and integrity verification for free: if two files have identical content, they share one blob object.

Question 2

What branching model data structures allow efficient branch creation and deletion in a VCS?

Accepted Answer

Represent branches as mutable named pointers (refs) to a commit hash stored in a lightweight file or a key-value ref database. Because a branch is just a 40-byte SHA pointer, creation and deletion are O(1) — no data is copied. Maintain a special HEAD ref that either holds a branch name (attached HEAD) or a direct commit hash (detached HEAD). For remote refs, namespace them under refs/remotes//. Use a packed-refs file for repos with thousands of branches to avoid per-file syscall overhead. The DAG of commit objects itself is immutable; only the ref pointers move, making branch operations cheap regardless of history depth.

Question 3

Walk through the three-way merge algorithm used when merging two branches.

Accepted Answer

Find the merge base — the most recent common ancestor commit — using a lowest-common-ancestor traversal of the commit DAG (BFS from both branch tips, intersecting visited sets). For each file, perform a three-way diff: compare base→ours and base→theirs independently. If only one side changed a region, take that change. If both sides changed the same region differently, emit a conflict marker. If both sides made the identical change, accept it without conflict. At the object level, generate a new tree object reflecting the merged file contents, then create a merge commit with two parent pointers. For renames, use similarity scoring (edit distance on content) to detect renames before diffing, preventing spurious conflicts.

Question 4

How do you handle concurrent pushes to the same branch in a distributed VCS server?

Accepted Answer

Use optimistic concurrency with a compare-and-swap on the ref. When a client pushes, it sends the current (expected) tip hash and the new tip hash. The server atomically updates the ref only if the current value matches the expected value — reject with a 'non-fast-forward' error otherwise. Implement this via a per-ref advisory lock (flock on the ref file, or a distributed lock in Redis/ZooKeeper for clustered servers) held only for the duration of the CAS write. For high-throughput hosting services, queue pushes to the same branch and process them serially to avoid lock contention. Store incoming pack objects before acquiring the lock so the critical section is just the ref pointer swap, keeping lock hold time under a millisecond.

Version Control System Low-Level Design: Object Store, Branching Model, and Merge Algorithm

Object Types

Content Addressing

Branch Model

Three-Way Merge Algorithm

Pack Files and Delta Compression

Garbage Collection

Shallow Clone and Grafts

Reflog

Hooks