Collaborative Whiteboard

The problem

"Design a collaborative whiteboard." A team adds sticky notes, arrows and freehand lines to one shared board and sees every change live.

It reuses the pattern of Design Google Docs: a live connection per person, one server that orders each board's changes, and a log of them. New here: shapes instead of letters, two people dragging one note at once, lines that appear while they're drawn, and boards too big to load whole. Park video chat: it's a design of its own.

The numbers

From the interviewer: a busy board has 50 people on it, each changing about one shape a second, and the browser reports about 60 mouse moves a second.

what                  how                     a second
shape changes in      50 people × 1           50
cursor moves in       50 people × 60          3,000
cursor moves out      3,000 × 49 others       about 150,000
at 20 a second        50 × 20 × 49            about 50,000

Cursor traffic is 60 times the edits, so cursors can't be stored like edits, and they shouldn't travel at the full 60 a second.

Shapes, not letters

A board is a set of shapes, each with its own id and properties: s7 is a yellow sticky note at (100, 100). An edit names a shape by its id and sets only what changes:

{"op": "set", "shape": "s7", "pos": [300, 120]}
{"op": "set", "shape": "s3", "color": "red"}
{"op": "add", "shape": "ana-12", "type": "note", "pos": [400, 80]}
{"op": "delete", "shape": "s9"}

In a doc, typing a letter shifts every letter after it, so every pair of crossing edits needs merging. Shapes don't move each other: edits on different shapes, or on different properties of one shape (Ana moves s7 while Ben turns it blue), are simply both applied. New shapes get ids made in the browser, the writer plus a counter such as ana-12, so two adds never collide. A delete can be a flag on the shape, so a drag that crosses it leaves the shape gone either way.

The same shape at once: last write wins

Only the same property of the same shape needs a rule. Ana drags s7 to (300, 120) while Ben drags it to (150, 260); the board's server gets Ana's edit first, as revision 41, then Ben's, as 42.

property   before       Ana, rev 41   Ben, rev 42   after
position   (100, 100)   (300, 120)    (150, 260)    (150, 260)
color      yellow                                   yellow

Last write wins, per property: each property keeps the value with the highest revision, so every screen shows s7 at (150, 260). Treat the position as one property: merging Ana's x with Ben's y would put the note where nobody dropped it.

OT's shift doesn't apply: a position is a value, not a place in a sequence that other edits move. A copy of the note at each spot is Dropbox's conflicted copy, clutter. A lock while someone drags costs a round trip before every drag, for a rare clash that's cheap to fix.

Store each value with its revision (with no server, a clock and the writer's id) and copies agree in any order: a CRDT, as in the Google Docs deep dive, far simpler than one for text. One detail: while Ben's drag waits for its revision, his app ignores Ana's revision 41 for that property, or his note would flicker to her spot and back.

Cursors and lines in motion

Cursors, and a line while it's being drawn, are ephemeral, like Google Docs' cursors: passed on, never logged. Logging them would mean 3,000 writes a second for one board instead of 50, and history would replay cursor trails nobody needs.

Send about 20 updates a second, one every 50 ms, and let each app glide the cursor between them: it looks smooth, and the busy board's 150,000 messages a second drop to about 50,000, a third. Each update carries the cursor's newest spot, or the line's points since the last one. When Ana lifts the pen, the finished line is one shape with all its points: one edit in the log.

Big boards: load the tiles in view

Say a board has 10,000 shapes of about 500 bytes each, 5 MB, and Ana opens it zoomed in on its top-left corner. The server cuts the board into square tiles and keeps a list of the shapes in each, like the grid of cells in Nearby Places:

row   shapes in each tile, left to right
0     60    40    150   300   450   200
1     70    30    250   700   900   500
2     120   180   400   800   950   650
3     90    160   500   850   900   750

Her screen covers the 4 tiles at the top left, which hold 200 shapes, about 100 KB. The app asks for those first, GET /boards/b9/tiles?rows=0-1&cols=0-1, then for the 5 tiles around them (1,100 more shapes), so panning finds them ready. Loading the whole board would send 5 MB, 50 times what's on her screen. Paging oldest first fails too: pages by age are scattered all over the board. Zoomed far out, each tile can come as a small picture, like map tiles.

Same pattern as Google Docs

The skeleton carries over: a WebSocket per browser through gateways, a directory that sends each board's edits to its one server, and that server numbering the edits into the op log, with snapshots for crash recovery. Only the merge changes: shapes and properties, no positions to shift.

Summary

• Scope: shapes, live cursors and lines, big boards; park video chat.
• Data: shapes with an id and properties; an op log and snapshots.
• API: a WebSocket per board; each edit names a shape; tiles over HTTP.
• Numbers: 3,000 cursor moves a second, 60 times its 50 edits.
• Scale: the tiles in view, then the ring around them.
• Conflicts: most edits merge by themselves; on one property, last write wins.
• Cursors and lines: about 20 updates a second, never stored.