Engineering Atlas › Low-Level Design

Code a mini Git-style version control system

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Requirements

Functional:

Non-functional:

Out of scope for the interview: merging (covered in Git, Testing and Code Review Basics, which implements merge base and three-way merge), remotes and network sync, a staging area with partial commits, and line-level diff algorithms. Name each and place it in Extensibility.

Entities and relationships

Relationships: commits reference trees, trees reference blobs and subtrees, commits reference parents. Nothing in the object store references a ref; refs only point inward. That one-way arrow is why branches are cheap (a 41-byte file in Git) and why deleting a branch never deletes history until garbage collection proves it unreachable.

Class diagram

classDiagram
    class Repository {
      -objects: ObjectStore
      -refs: RefStore
      -work: WorkingTree
      -head: Head
      +commit(message) CommitId
      +branch(name) void
      +checkout(name) void
      +log() Commit[]
      +diff(a, b) Change[]
    }
    class GitObject {
      <<interface>>
      +id() ObjectId
      +serialize() bytes
    }
    class Blob {
      +content: bytes
    }
    class Tree {
      +entries: TreeEntry[]
    }
    class Commit {
      +tree: ObjectId
      +parents: ObjectId[]
      +message: string
    }
    class ObjectStore {
      <<interface>>
      +put(obj) ObjectId
      +get(id) GitObject
    }
    class RefStore {
      <<interface>>
      +get(name) ObjectId
      +compareAndSet(name, old, new) bool
    }
    class Head {
      +branch: string
      +detached: ObjectId
    }
    GitObject <|.. Blob
    GitObject <|.. Tree
    GitObject <|.. Commit
    Repository --> ObjectStore
    Repository --> RefStore
    Repository --> Head
    ObjectStore "1" o-- "many" GitObject
    Tree --> Blob
    Tree --> Tree
    Commit --> Tree
    Commit --> Commit : parents

Key flows

Commit writes objects bottom-up (blobs, then trees, then the commit) and only then moves the branch. If the process dies before the last step, the new objects are unreachable garbage and the repository is still consistent.

sequenceDiagram
    participant U as User
    participant R as Repository
    participant W as WorkingTree
    participant O as ObjectStore
    participant F as RefStore
    U->>R: commit("fix login")
    R->>W: snapshot files
    R->>O: put(blob) for each file
    O-->>R: blob ids (existing ones reused)
    R->>O: put(tree)
    O-->>R: tree id
    R->>R: tree id == parent tree? refuse
    R->>O: put(commit tree, parent, msg)
    O-->>R: commit id C2
    R->>F: compareAndSet(main, C1, C2)
    F-->>R: ok
    R-->>U: C2

Design patterns used and why

Concurrency and edge cases

Down the stack

Layer 1The contract

commit either returns a new id whose tree exactly matches the working tree and whose parent is the previous HEAD commit, with the current branch moved to it, or fails and moves nothing. The same tree, parent and message always yield the same id. A ref update succeeds only if the ref still holds the value the writer last read. checkout either replaces the working tree completely and moves HEAD, or refuses and changes nothing. diff(a, b) depends only on the two snapshots, never on the path between them.

Layer 2The mechanism

Git serialises every object as <type> <size>\0<payload> and names it by the hash of that byte string. A tree payload is a sequence of entries <mode> <name>\0<20 raw hash bytes>, sorted by name. A commit payload is text: tree <id>, one parent <id> line per parent, author, committer, a blank line and the message. Loose objects are zlib-compressed and stored at .git/objects/ab/cdef..., the first two hex digits forming 256 subdirectories so no single directory grows huge. Refs are small text files under .git/refs/heads/, many of them consolidated into packed-refs, and HEAD usually contains ref: refs/heads/main. Because trees nest per directory, a commit that changes one file deep in a large repository writes one new blob plus one new tree per directory level on its path, and reuses every other subtree id unchanged. Diffing two commits walks both trees in parallel and skips any subtree whose ids are equal, which is why git diff between nearby commits is fast in a repository with a million files.

Layer 3The machine

Git's collision-detecting SHA-1 runs at several hundred MB/s per core, so hashing a 10 KB source file costs tens of microseconds. zlib compresses source code to roughly a quarter to a third of its size. A loose object costs one inode and at least one 4 KB filesystem block regardless of size, which is why Git periodically packs them: a packfile stores objects back to back, with similar blobs stored as deltas against each other, and a companion .idx file holds sorted ids plus a 256-entry fanout table so a lookup is one table read and a binary search. Durability is a matter of fsync: Git's core.fsync setting controls whether object files and refs are flushed to disk before the ref rename, trading 0.1 to several milliseconds per commit for crash safety.

Why it's built this way

  1. Developers need to trust that history has not been altered, so objects are named by the hash of their content and any change produces a new name.
  2. Hash-named objects are immutable, so they can be shared freely: identical files and unchanged subtrees are stored once and copied between repositories by id.
  3. Immutable objects cannot express "the latest version", so a separate, tiny mutable layer of refs is needed, and all contention concentrates there.
  4. Contention on a single small name is best handled by compare-and-swap, so refs update with a lock file and an atomic rename.
  5. Storing snapshots rather than diffs makes every commit independently readable, and compression plus delta packing recovers the space a diff-based design would have saved.

Extensibility

Leadership lens

Check yourself

  1. Why does a commit store a snapshot (a root tree) instead of a diff against its parent?

    Show answer

    Each commit can then be read without replaying history, diffs can be computed between any two commits with any algorithm, and unchanged files cost nothing because their blob ids are reused.

  2. Why must the branch ref be updated last when creating a commit?

    Show answer

    So that a crash leaves only unreachable objects, which garbage collection can remove. Updating the ref first would leave it pointing at a commit, tree or blob that may not exist.

  3. Two people commit on top of the same main at the same time. Which part of the system detects the conflict, and how?

    Show answer

    The ref store, through compare-and-swap: the second writer's update expects main to be the old commit, finds the first writer's commit instead, and fails, so the second writer must merge or rebase.

  4. How can comparing two commits skip most of a huge repository?

    Show answer

    Trees are hashed per directory, so equal subtree ids mean identical contents. The diff walks both trees together and descends only where ids differ.

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →