Design Version Control System
Design an in-memory Version Control System that supports tracking file changes, committing updates, branching, and retrieving historical versions.
A Version Control System (VCS) is a tool that helps individuals and teams manage changes to source code or files over time. It records a history of edits, enables collaborative development, and allows users to revert to previous versions if needed.
Key features of a typical VCS include:
- Commit history: Track incremental changes with context
- Branching and merging: Experiment or isolate features without affecting the main line
- Collaboration support: Prevent developers from overwriting each other’s work
- Version retrieval: View or restore any past state of the system
Popular version control tools include Git, Subversion (SVN), and Mercurial.
In this chapter, we will explore the low-level design of a simplified version control system.
Let's start by clarifying the requirements:
1. Clarifying Requirements
Before starting the design, it's important to ask thoughtful questions to uncover hidden assumptions, clarify ambiguities, and define the system's scope more precisely.
Here is an example of how a conversation between the candidate and the interviewer might unfold:
Candidate: Should the system support nested directories and a hierarchical file structure?
Interviewer: Yes, the system should support managing files in a directory tree structure, similar to a typical file system.
Candidate: Should we store full snapshots of files or just the differences (deltas) between versions?
Interviewer: To keep things simple, store full snapshots for each commit. In real-world systems, we would optimize this using deltas.
Candidate: Do we need to support a staging area where users can select specific files to include in a commit?
Interviewer: No, assume that the entire repository is committed at once.
Candidate: Do we need to support branching and merging features?
Interviewer: Yes, basic branching should be supported. You can skip merging for now.
Candidate: Should the system allow users to roll back to a previous version?
Interviewer: Yes, the system should allow viewing commit history and reverting the repository to any prior commit.
Candidate: Should the system support viewing diffs between any two commits?
Interviewer: It would be nice to have, but let’s leave that out for this design.
Candidate: Should we use a command-line interface or just hardcode a sequence of operations for demonstration?
Interviewer: A hardcoded sequence is fine for demonstration purposes.
After gathering the details, we can summarize the key system requirements.
1.1 Functional Requirements
- Support creation and versioning of multiple files within a hierarchical directory structure.
- Allow users to commit changes across the entire repository (no staging area).
- Support basic branching operations (create and switch branches).
- Maintain a commit history for each branch.
- Allow users to rollback to any previous commit in the history.
- Store full snapshots of the file system at the time of each commit.
- Enable viewing the commit history of the repository.
1.2 Non-Functional Requirements
- Modularity: The system should be designed with clear separation between modules.
- Maintainability: Code should follow object-oriented principles, be easy to test, and allow for future changes with minimal impact
- Reliability: Ensure consistency and correctness of the file system across commits, branches, and rollbacks.
- Usability: Provide a simple interface to demonstrate core operations such as
commit,checkout,branch, andrevert