Engineering Atlas › Low-Level Design

Code a spreadsheet engine with formulas

16 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: text cells, dates, INDIRECT-style dynamic references, cross-sheet references, undo, file formats, multi-user editing and threads. Extensibility covers the first two.

Entities and relationships

Two maps hold the graph: precedents[c] (what c reads) and dependents[p] (who reads p). They are mirror images, kept in sync by set. Edges point to cells that do not exist yet, so a formula can refer to a cell the user fills in later.

Class diagram

classDiagram
    class Sheet {
      -ast: Map~Cell, Node~
      -values: Map~Cell, Value~
      -precedents: Map~Cell, Set~
      -dependents: Map~Cell, Set~
      +set(cell, raw) Cell[]
      +get(cell) Value
      +subscribe(fn)
    }
    class Node {
      <<abstract>>
      +refs(out)
      +eval(values) Value
    }
    class Num
    class Ref
    class Range
    class Neg
    class Bin
    class Call
    class Parser {
      +parse(text) Node
    }
    class Observer {
      <<interface>>
      +onChange(cell, value)
    }
    Sheet "1" o-- "many" Node
    Sheet --> Parser
    Sheet "1" o-- "many" Observer
    Num --|> Node
    Ref --|> Node
    Range --|> Node
    Neg --|> Node
    Bin --|> Node
    Call --|> Node
    Bin "1" *-- "2" Node
    Call "1" *-- "many" Node

Key flows

sequenceDiagram
    participant U as Caller
    participant S as Sheet
    participant P as Parser
    participant N as Node tree
    participant O as Observer
    U->>S: set("B1", "=A1*2")
    S->>P: parse("A1*2")
    P-->>S: Bin(*, Ref A1, Num 2)
    S->>S: rewire precedents and dependents
    S->>S: collect dirty set (B1 and dependents)
    S->>S: Kahn order over the dirty subgraph
    loop each ready cell
        S->>N: eval(values)
        N-->>S: value
    end
    S->>S: unreachable cells get #CYCLE!
    S->>O: onChange(cell, value) for changed cells
    S-->>U: changed cells in evaluation order

The write path has six steps. Parse the raw text. Remove the cell's old edges and add the new ones. Walk dependents breadth first from the edited cell to get the dirty set. Count, for each dirty cell, how many of its precedents are also dirty. Start from the cells with a count of zero and repeatedly evaluate one, then decrement its dependents. Finally compare new values with old and tell the observers about the differences.

The read path is a single map lookup. get never recalculates, because every set leaves the sheet fully consistent. That keeps reads fast and makes the sheet safe to read from a renderer.

Design patterns used and why

Concurrency and edge cases

In the wild

Down the stack

Layer 1The contract

After set returns, every cell's value equals what you would get by evaluating all formulas from scratch in some valid dependency order, as if the sheet were rebuilt. The tests pin this down as four checkable promises. A cell is evaluated only after every cell it reads. A cell outside the dirty set keeps its old value. A value never depends on the order of earlier edits. Cells on or below a cycle read #CYCLE!. set returns the changed cells in evaluation order and notifies observers in that same order.

This is the same contract as an incremental build system. The "Build systems à la carte" paper calls Excel a build system in disguise: formulas are the task descriptions, cell values are the build products, and an edit is a changed input (Mokhov, Mitchell, Peyton Jones).

Layer 2The mechanism

Excel's documented model has three stages: build a dependency tree, build a calculation chain (the formula cells in the order they must be computed), then recalculate the dirty cells in chain order (Microsoft Learn). When a cell changes, all direct and indirect dependents are marked dirty. Volatile functions such as NOW are re-evaluated on every recalculation, together with their dependents.

Our engine builds the order per edit instead of keeping a chain. The steps are Kahn's algorithm on the dirty subgraph (topological sorting): compute in-degrees restricted to dirty cells, queue the zero-degree cells, pop one, evaluate it, decrement its dependents. The queue is a min-heap on (row, column) so output is deterministic. Cost is O(V + E) in the dirty subgraph plus the heap's log factor.

Excel's real chain differs in one respect that matters. Because INDIRECT makes dependencies depend on values, Excel starts from the previous chain, and if a formula depends on a cell that has not been calculated yet, the cell being calculated and its dependents are moved down the chain. A static graph like ours is the simpler special case, and stays valid for any formula whose references can be read off the text.

Range nodes matter for scale. Expanding SUM(A1:A100000) into 100,000 edges is fine for a lesson. Production engines store a range as one node with interval bookkeeping, so a column total costs one edge, not one hundred thousand.

Layer 3The machine

A worksheet is up to 1,048,576 rows by 16,384 columns, about 17 billion addresses (Microsoft support), so storage must be sparse: hash maps keyed by address, not a dense grid. A used cell costs a hash lookup (tens of nanoseconds when warm) plus pointer chasing through the node tree. A tree walk is a chain of dependent loads and virtual or interface calls, so a large sheet of tiny formulas is bound by memory latency rather than arithmetic, and an interpreter language pays a further constant factor on every node visit.

Numbers are 8-byte IEEE 754 doubles with a 53-bit mantissa, which is why integers are exact only up to 2^53 and why 0.1 + 0.2 is not 0.3. The parser's recursion uses the call stack, one frame per nesting level, so a formula of 100,000 open parentheses needs a depth cap. The evaluation order, however, is computed with an explicit queue and not recursion, so a chain of a million cells (A2 = A1 + 1, A3 = A2 + 1, ...) cannot overflow the stack. A recursive "evaluate my precedents first" design would.

Why it's built this way

  1. Typing a formula is rare and cheap; recalculating is constant. So parse once into a tree and keep the tree.
  2. The tree's references are exactly the dependencies, so the graph comes free from parsing and never needs a manual declaration.
  3. Most edits touch a small part of a large sheet, so recalculating everything is wasteful. Dirty marking restricts the work to the affected subgraph.
  4. Evaluating a dependent before its input yields a wrong value, so the order must be topological. Doing that with an explicit queue also detects cycles and avoids deep recursion.
  5. Users type nonsense all day, so failures become values that propagate. The sheet stays alive and shows where the problem is.

Extensibility

Leadership lens

Check yourself

  1. A sheet has A1 = 1, B1 = A1 + 1, C1 = A1 + 2, D1 = B1 + C1. If you change A1 and recalculate recursively through dependents, how many times can D1 be computed, and what is the fix?

    Show answer

    Twice, once per path, and the first time with a stale B1 or C1. Evaluate the dirty cells in topological order so D1 runs once, after both inputs are final.

  2. In Kahn's algorithm over the dirty subgraph, how do you know which cells are in a cycle, and why are some non-cycle cells also reported?

    Show answer

    Cells never reaching in-degree zero are never evaluated. They are the cycle members and every cell that depends on them, because those wait forever for an input that never completes. #CYCLE! on all of them is consistent with error propagation.

  3. Why must set remove a cell's old edges before adding the new ones?

    Show answer

    Otherwise a formula changed from =A1 to =B1 would still be recalculated when A1 changes and could look cyclic through stale edges. The graph must always equal the references of the current formulas.

  4. Why does the engine publish observer events after the whole recalculation instead of inside the loop?

    Show answer

    A listener that reads other cells mid-pass would see some cells new and some old. Publishing after the pass guarantees the sheet is consistent, and the changed list lets listeners redraw only what moved.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

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