FSD Frontend System Design

Part VI — The Blueprint · Lesson 11.12

HLD – Google Sheets

In one lineA virtualized grid over a dependency graph — render what's visible, recalculate only what changed.

Where you've seen itTyping a number into A1 and having exactly the cells that reference it update, instantly, in a sheet with a million rows.

  • Time21 min
  • DiagramVirtualized viewport + formula dependency DAG
  • Chapter11 · High Level Design

Diagram

diagram
1–2 · SCOPE AND SCALE

  in scope   grid · editing · formulas · scroll · selection · collab
  out        charts · pivot tables · apps script · import/export
  scale      up to 10M cells · 1M rows × 26 cols visible-addressable
             only ~1,000 cells on screen at any moment
diagram
3 · VIRTUALIZED GRID — two dimensions, not one

  ┌─── frozen header row ────────────────────────┐
  │   │  C  │  D  │  E  │  F  │                  │
  ├───┼─────┼─────┼─────┼─────┤                  │
  │ 8 │     │     │     │     │   ~40 rows ×     │
  │ 9 │     │  ●  │     │     │   ~25 cols       │
  │10 │     │     │     │     │   = 1,000 cells  │
  │11 │     │     │     │     │     RENDERED     │
  └───┴─────┴─────┴─────┴─────┘                  │
   ▲                                              │
   frozen column                                  │
                                                  │
  scrollTop  → startRow = floor(scrollTop / rowHeight)
  scrollLeft → startCol (prefix-sum if widths vary)
  spacers hold total scrollable size (10.7)

  Never mount 10M cells. Mount ~1,000 and translate the window.
diagram
6a · DEEP DIVE — THE DEPENDENCY DAG

  A1 = 10
  B1 = A1 * 2          B1 depends on A1
  C1 = B1 + A1         C1 depends on B1, A1
  D1 = SUM(A1:C1)      D1 depends on A1, B1, C1

        A1 ──► B1 ──► C1 ──► D1
         └──────┴──────┴──────┘

  edit A1
    → find dependents (reverse edges)
    → topological sort → recalc in order: B1, C1, D1
    → recalc ONLY those cells, never the whole sheet

  cycle detection: A1 = B1 and B1 = A1 → #CIRCULAR!, don't hang
diagram
6b · DEEP DIVE — KEEPING EDITS AT 60fps

  parse formula once → AST, cached per cell
  recalc in a Web Worker when the dirty set is large (5.1)
  batch renders: one paint per frame, not per recalculated cell
  canvas rendering for the grid body if DOM cells prove too slow
  virtualize selection: a 10,000-cell range is a rectangle,
                        not 10,000 selected elements

How it works

  1. Sparse storage: a map keyed by "R3C7", so empty cells cost nothing.
  2. Virtualize both axes, with frozen headers rendered as separate panes.
  3. Build a dependency graph as formulas are parsed; edits walk reverse edges and recalculate topologically.
  4. Detect cycles at parse time and report #CIRCULAR! rather than hanging.
  5. Collaborate per cell — unlike prose (11.11), cells are independent, so per-cell last-write-wins is usually acceptable.

Trade-offs

ChoiceCost
DOM cellsEasy styling and a11y; slower past a few thousand
Canvas gridFast at any size; you rebuild a11y and editing
Full recalcTrivial to write; unusable at scale
DAG recalcFast and correct; graph maintenance complexity

Interview angle

"How do you recalculate a sheet with 10 million cells?"

  • You don't recalculate the sheet — you recalculate the dependents of the edited cell, found via reverse edges in a DAG and ordered topologically.
  • Detect cycles at parse time so a circular reference errors instead of hanging the tab.
  • If the dirty set is large, run recalculation in a Web Worker and batch one repaint per frame so typing stays responsive.

Recap

  • Virtualize both axes; only ~1,000 cells ever exist in the DOM.
  • The dependency DAG is what makes editing fast — recalc the dependents, not the sheet.
  • Cells are independent, so collaboration is far simpler here than in a document.