Skip to content
sysgeeks

Design a Collaborative Editor (Google Docs), stage 3 of 12: decide

Where does a document's live state live?

Five editors of one document may be connected to five different servers. Each op must be ordered relative to every other op for that document, persisted, and delivered to the other four within 200 ms.

System so far· 2 parts
CLIENTEditor clientDATABASEPostgres op log

Select a component to see what it is responsible for and which state it owns.

What you need to know

0 of 1 checks done

  1. Every document needs one authority that decides the order of its operations. Clocks can't do it: client clocks disagree by seconds, so ordering by timestamp gives different orders on different machines. See Ordering.

    Give each document an owner server: it holds the document in memory, assigns each op the next sequence number, persists it and broadcasts it. Ordering becomes a counter in memory.

  2. That turns ordering into routing: every connection for document 42 must reach its current owner. A router can map document IDs to servers with consistent hashing, so that when servers come and go, most documents stay where they are. See Consistent hashing.

  3. Think of the keys as documents and the nodes as collaboration servers. Every key that moves is a document whose owner changes, and whose editors must reconnect.

    2,000 keys spread over cache nodes. Add a node and count the keys that now belong somewhere else: each one is a cache miss, or data to copy.
    Placement
    4 nodes
    4 nodeskeys by hash mod N

    Keys per node. The line is a perfectly even share.

    • Node 1500
    • Node 2508
    • Node 3512
    • Node 4480

    The busiest node holds 1.0× an even share.

  4. Check

    Alternative: any server accepts any client, and each op takes the next sequence number from a row in Postgres. What's the cost?