Design a Git Version Control System

Problem Statement

Design an in-memory version control utility modeled after Git (Mini-Git). The system must support staging files (git add), committing snapshots with messages (git commit), managing multiple branches (git checkout -b), switching between commits (git checkout), and displaying the commit history logs (git log).

Asked In Companies

Atlassian Microsoft

---

Design Decisions & Patterns Used

Modeling Git requires representing files as immutable snapshots rather than delta differences. When we commit, we capture a snapshot of the entire staging area merged with previous files. Branching is represented as simple references pointing to specific commit nodes in a Directed Acyclic Graph (DAG).

We will utilize the following Design Patterns:

• Memento Pattern: Storing snapshots of file states (commits) and restoring the working directory state when checking out a commit.
• State Pattern: Tracking active branches and head states dynamically to route staging actions correctly.
• Command Pattern: Wrapping commits as immutable transactions linked to parent nodes.

---

Functional Requirements

• Stage file contents: add(filePath, content).
• Commit staged changes with a message: commit(message), creating a parent-linked commit node.
• Create and checkout branches: checkoutBranch(branchName).
• Rollback/revert state: checkoutCommit(commitId) to restore working files.
• Walk history: log() to print the commit path starting from HEAD.

---

Objects Required

• Commit (Memento object representing file snapshots, timestamps, and parent commits)
• Repository (Context coordinator managing staging areas, branch refs, and head markers)

---

Commit Class (Memento)

The Commit class acts as the memento, capturing the file snapshot, the commit message, and a reference to the parent commit.

import java.util.HashMap;
import java.util.Map;
import java.util.UUID;

public class Commit {
    private final String id;
    private final String message;
    private final Commit parent;
    private final Map<String, String> fileSnapshots;
    private final long timestamp;

    public Commit(String message, Commit parent, Map<String, String> fileSnapshots) {
        this.id = UUID.randomUUID().toString().substring(0, 8); // simplified hash
        this.message = message;
        this.parent = parent;
        this.fileSnapshots = new HashMap<>(fileSnapshots);
        this.timestamp = System.currentTimeMillis();
    }

    public String getId() { return id; }
    public String getMessage() { return message; }
    public Commit getParent() { return parent; }
    public Map<String, String> getFileSnapshots() { return fileSnapshots; }
    public long getTimestamp() { return timestamp; }
}

The constructor assigns a unique ID, copy-creates the file snapshot map to enforce immutability, and logs the parent commit reference.

---

Repository Class

The Repository class manages the staging area, updates branch pointers, and resolves commit checkpoints.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Repository {
    private final Map<String, String> stagingArea;
    private final Map<String, Commit> commitRegistry;
    private final Map<String, Commit> branchPointers;
    private final Map<String, String> workingDirectory;
    private String currentBranch;
    private Commit head;

    public Repository() {
        this.stagingArea = new HashMap<>();
        this.commitRegistry = new HashMap<>();
        this.branchPointers = new HashMap<>();
        this.workingDirectory = new HashMap<>();
        this.currentBranch = "main";
        this.head = null;
        branchPointers.put("main", null);
    }

    public void add(String filePath, String content) {
        workingDirectory.put(filePath, content);
        stagingArea.put(filePath, content);
        System.out.println("Staged changes for file: " + filePath);
    }

    public String commit(String message) {
        if (stagingArea.isEmpty()) {
            throw new IllegalStateException("Nothing to commit. Staging area is empty.");
        }

        // Build file snapshot from the parent commit and the staging area
        Map<String, String> newSnapshot = new HashMap<>();
        if (head != null) {
            newSnapshot.putAll(head.getFileSnapshots());
        }
        newSnapshot.putAll(stagingArea);

        Commit newCommit = new Commit(message, head, newSnapshot);
        commitRegistry.put(newCommit.getId(), newCommit);
        
        // Update HEAD and branch pointers
        head = newCommit;
        branchPointers.put(currentBranch, head);
        stagingArea.clear(); // Clear staging area

        System.out.println("Committed: [" + newCommit.getId() + "] " + message);
        return newCommit.getId();
    }

    public void checkoutBranch(String branchName) {
        if (branchPointers.containsKey(branchName)) {
            currentBranch = branchName;
            head = branchPointers.get(branchName);
            restoreWorkingDirectory(head);
            System.out.println("Switched to branch '" + branchName + "'");
        } else {
            // Git shortcut: checkout -b (create branch pointing to current HEAD)
            branchPointers.put(branchName, head);
            currentBranch = branchName;
            System.out.println("Created and switched to branch '" + branchName + "'");
        }
    }

    public void checkoutCommit(String commitId) {
        Commit target = commitRegistry.get(commitId);
        if (target == null) {
            throw new IllegalArgumentException("Commit not found: " + commitId);
        }
        head = target;
        restoreWorkingDirectory(head);
        System.out.println("Checked out commit [" + commitId + "]. (HEAD is now detached)");
    }

    private void restoreWorkingDirectory(Commit commit) {
        workingDirectory.clear();
        if (commit != null) {
            workingDirectory.putAll(commit.getFileSnapshots());
        }
    }

    public List<String> log() {
        List<String> history = new ArrayList<>();
        Commit temp = head;
        while (temp != null) {
            history.add(String.format("Commit: %s | Message: %s", temp.getId(), temp.getMessage()));
            temp = temp.getParent();
        }
        return history;
    }

    public String getFileContent(String filePath) {
        return workingDirectory.get(filePath);
    }

    public String getCurrentBranch() { return currentBranch; }
}

Here is an explanation of the core operations in the Repository class:

• The constructor configures working directories, staging maps, branch reference tables, and sets the default branch to main.
• add() registers file changes in the staging map, simulating the git add command.
• commit() compiles files by merging the parent commit's snapshot with the staging area, instantiates a new Commit, updates the HEAD pointer, and clears the staging area.
• checkoutBranch() switches the current branch pointer. If the branch is new, it creates it pointing to the current HEAD commit. It then calls restoreWorkingDirectory() to update files.
• checkoutCommit() switches HEAD directly to the specified commit ID, detaching HEAD and restoring the file state to that commit.
• log() walks backward through parent commit pointers starting from HEAD to build the commit history path.

---

Main Driver Class

This class tests our version control system. It stages files, commits changes, branches, checks out historical commits, and prints history logs.

public class Main {
    public static void main(String[] args) {
        Repository git = new Repository();

        System.out.println("--- Scenario 1: Initial Commit on 'main' ---");
        git.add("index.html", "<html>Hello v1</html>");
        git.add("styles.css", "body { color: black; }");
        String c1 = git.commit("Initial commit adding index and styles");

        System.out.println("\n--- Scenario 2: Second Commit on 'main' ---");
        git.add("index.html", "<html>Hello v2 (Updated)</html>");
        String c2 = git.commit("Updated index content");

        System.out.println("\n--- Scenario 3: Creating and Switching to Feature Branch ---");
        git.checkoutBranch("feature-oauth");
        git.add("auth.js", "function login() { return true; }");
        String c3 = git.commit("Added authentication scripts");

        System.out.println("\n--- Printing Repository Commit Log ---");
        for (String logLine : git.log()) {
            System.out.println(logLine);
        }

        System.out.println("\n--- Scenario 4: Switching back to 'main' ---");
        git.checkoutBranch("main");
        System.out.println("File auth.js exists in main? " + (git.getFileContent("auth.js") != null ? "Yes" : "No"));
        System.out.println("index.html content in main: " + git.getFileContent("index.html"));

        System.out.println("\n--- Scenario 5: Checking out commit v1 (Rollback state) ---");
        git.checkoutCommit(c1);
        System.out.println("index.html content at commit v1: " + git.getFileContent("index.html"));
    }
}

The main() driver initializes the repository, stages and commits files, creates branches, verifies file isolation between branches, and checks out historical commits to demonstrate state restoration.

---

Also See

• Most Commonly Asked Low Level Design Interview Questions
• Top 10 Low Level Design Interview Questions