The commit DAG — what Git is really a graph of

A Git repository is not a list of commits and it is not a tree of directories. It is a Directed Acyclic Graph (DAG) of commits. Every commit is a node; every parent line in a commit object is a directed edge from the child back to the parent; and the graph is forbidden from containing cycles. This single design choice is why Git can merge branches, walk ancestry, compute merge bases, and reason about reachability - and why every log command in this part exists.

What a DAG actually is

A graph is a set of nodes connected by edges. A directed graph draws an arrow on each edge, indicating which direction the relationship flows. An acyclic graph forbids following the arrows in a loop and returning to the starting node.

Git’s commit graph satisfies all three properties:

• Nodes are commit objects, identified by their OID.
• Edges are parent lines in each commit object, pointing from the child to the parent.
• Direction flows from newer commits toward older commits: the child points at the parent, not the other way around.
• Acyclicity is structural: a new commit cannot be a parent of itself, and git will refuse to construct a commit whose parent set includes a descendant of the new commit. A cycle would mean the future is the ancestor of the past.

flowchart LR
    A["commit A\nno parents"] --> B["commit B\nparent: A"]
    B --> C["commit C\nparent: B"]
    B --> D["commit D\nparent: B"]
    C --> E["commit E\nparents: C, D"]
    D --> E

In the diagram, E has two parents (C and D) and three ancestors (A, B, and one of C/D). There is no path from any node back to itself - that is the acyclicity invariant.

Why Git uses a DAG and not a linear list

Early version-control systems (and some modern ones that imitate their user interfaces) treat history as a linear list: each commit has at most one parent, and branches are simulated by copying or cherry-picking. Git does not do this. A merge in Git produces a commit with two parents, encoding the fact that two lines of development converged at a specific point in time.

The DAG model buys four properties that a linear model cannot give:

1. True convergence. A merge commit records that two lines of work joined, with the merge’s tree being the resolved result. The history remembers the convergence; a linear history cannot.
2. True branching. A feature branch is a path through the graph, not a copy of the tree. Reverting, rebasing, and cherry-picking are all defined as graph operations on the DAG.
3. Ancestry queries. “Is commit X an ancestor of commit Y?” reduces to “is Y reachable from X in the DAG?”. The answer is one git merge-base --is-ancestor command away, not a manual search.
4. Merge-base computation. The common ancestor of two commits is the deepest node reachable from both. This is a well-defined graph operation, and the three-way merge machinery depends on it.

Why acyclicity is a hard invariant

If the commit graph could contain a cycle, then git log <oid> would loop forever, git merge-base A B would have no answer (the two commits would be reachable from each other), and the object-store’s reachability invariant - that a reachable object is one an operation can find - would have no fixed point. Every plumbing command that walks the graph assumes termination.

Git enforces acyclicity by construction. When you run git commit -p <parent>, Git does not check whether the new commit would introduce a cycle - it cannot, because the new commit’s parent must already exist, and the parent’s descendants cannot include the new commit (it did not exist a moment ago). A cycle can only appear if a tool constructs commits by hand and gets the parent references wrong. Git will refuse to check out the resulting repository, and git fsck will flag the dangling reference.

# Reject a hand-built commit whose parent set is malformed
git update-ref REF_HEAD "$BAD_OID"
# fatal: update_ref failed for ref 'REF_HEAD':
# cannot update ref with dangling referent

DAG versus tree versus list

The DAG is sometimes confused with a tree (because Git also has tree objects, which are directory structures) or with a list (because git log without flags shows a linear-looking output). The distinctions:

• A list allows one parent per node and one child per parent. Every node has degree two (in and out), and there is exactly one path from the root to any node.
• A tree allows one parent per node but multiple children. The graph branches, but every node still has a single parent, so the graph cannot converge - two branches cannot rejoin.
• A DAG allows multiple parents per node and multiple children per parent. The graph branches and converges. This is exactly what Git history needs.

Reading the graph on the command line

git log --graph --oneline draws the DAG as ASCII. Every commit is one line, edges are pipes, asterisks, slashes, and backslashes, and time flows downward. The characters are not decoration - they are a literal rendering of the parent edges:

git log --graph --oneline --decorate --all
# * 8a3f9d2 (HEAD -> main) bump terraform module to v1.4.0
# *   4d2c8e0 Merge branch 'feature/iam-rotation' into main
# |\
# | * 9f3c1d7 (feature/iam-rotation) rotate iam keys
# | * 7a1b2c3 add rotation cron
# |/
# * 6f4e5a6 initial commit

The branching is the feature branch feature/iam-rotation, the convergence is the merge commit 4d2c8e0, and the trunk is the chain of first parents from 4d2c8e0 down to 6f4e5a6. Every character is meaningful; reading the graph fluently is the single most useful log skill.

Production discipline

1. Think in graphs, not in lines. When you read a log, ask “where is this commit in the DAG?” not “what commit came before?”. The DAG view is the one that survives a merge.
2. Refuse to break acyclicity. If a tool proposes a non-fast-forward operation that would create an unreachable state, stop and check whether the operation is correct. Cycles are bugs in the tool, not features of the workflow.
3. Use --graph --oneline --decorate --all as your default log invocation. It renders the DAG exactly and includes every ref. It is the most informative view Git offers and the baseline for everything in the next five lessons.

Cross-course references

• Ansible for Production Sysadmins - Part XXXVIII (Review) describes how an Ansible role’s git history is reviewed as a graph: the reviewer walks the first-parent chain and inspects every branch tip. The DAG model is what makes the review tractable.
• Terraform for Production Sysadmins - Part XII (State) notes that Terraform state versions are append-only and never rewritten, mirroring Git’s acyclic history model. State versions are linear, but the commits that produced them are not.
• Linux for Production Sysadmins - Part XX (BootProcess) discusses systemd unit dependencies as a DAG, which is the same graph model applied to service ordering.

Quiz