Post

System Shapes: Real-Time (Ride Matching, Live Location, Collaborative Editing)

Real-time systems are defined by a latency budget, ordering per key, and long-lived connections that pin state to servers. Here is the shape, the arithmetic, and a deep dive on ride matching, live location, and collaborative editing, each with the one property that makes it different.

System Shapes: Real-Time (Ride Matching, Live Location, Collaborative Editing)

Ride matching, live location, and collaborative editing look like three unrelated products. They share a shape. In each one, the user is staring at a screen waiting for something to change, the server has to push that change rather than wait to be asked, and the change is only useful if it arrives within a budget measured in milliseconds or a few seconds. Late data is wrong data.

That shape moves the difficulty to three places most designs never think about: the latency budget end to end, the order in which updates are applied, and the fact that every client holds a long-lived connection to one specific server. This post walks through the generic architecture for that shape, the problems every real-time system hits, and then each of the three examples in depth, starting with the one property that makes it different from the other two.

Where This Shows Up

  • “Design Uber” or “Design Lyft.” The headline is matching a rider to a driver; the follow-ups are about location and dispatch.
  • “Design a delivery tracker” or “Show the courier moving on the map.”
  • “Design Google Docs” or “Design a collaborative whiteboard.”
  • Follow-ups inside other designs: “How does the rider see the car move?”, “What happens when the WebSocket server holding this user dies?”, “Two people type at the same position at the same time. What happens?”, “How do you deploy without disconnecting everyone?”

What They Are Really Checking

  1. Do you work from a latency budget? “It should be fast” is not a requirement. “A remote keystroke should appear within 200 milliseconds at the 99th percentile (p99)” is, and it tells you where the servers must sit and how many hops you can afford.
  2. Do you know that connections are state? A WebSocket lives on one server. Sending a message to a user means finding that server. Deploys, crashes, and load balancing all behave differently when connections last for hours.
  3. Can you tell ephemeral data from durable data? A driver’s position is replaced every four seconds. Writing each one to a database is the classic mistake. A trip record or a document edit is the opposite: losing it is a bug.
  4. Do you know whose order wins? Real-time systems need ordering per key (per trip, per document, per device), not globally. The interviewer wants to hear who assigns the order and why wall clocks are not it.
  5. Can you find the one decision that must be exact? Most real-time data tolerates loss and staleness. Assigning a driver to a rider does not. Spotting the small contended write inside the stream of ephemeral updates is the senior move.

The Gotchas

Gotcha 1: Writing every location update to the database. One million drivers reporting every four seconds is 250,000 writes per second, each of which is overwritten four seconds later. Durability is pointless for data that replaces itself. Keep the latest position in memory and sample history to cheap storage asynchronously.

Gotcha 2: Polling for real-time. A million clients polling every second is a million requests per second, almost all of which return “nothing changed,” and the average delay is still half the polling interval. Push over a long-lived connection instead, and keep polling only as a fallback.

Gotcha 3: Forgetting that the connection lives on one server. The message for user 42 arrives at some backend instance, but user 42’s WebSocket is held by gateway 17. Without a connection registry or a pub/sub topic that gateway 17 subscribes to, the message has nowhere to go. Name the routing mechanism explicitly.

Gotcha 4: The reconnect storm. A gateway holding 50,000 connections dies, and all 50,000 clients reconnect in the same second, each doing a TLS (Transport Layer Security) handshake and then fetching a full state snapshot. That spike takes down the next gateway. Clients need jittered exponential backoff, and resync should be incremental from a sequence number, not a full reload.

Gotcha 5: Expecting the load balancer to spread long-lived connections. Round-robin balances new connections, not existing ones. After a rolling deploy, the first server back holds most of the clients and the newest server holds almost none. Balance by least connections, cap connections per server, and drain deliberately so clients spread out.

Gotcha 6: Ordering by client wall clocks. Phone clocks drift by seconds. Two edits ordered by device timestamp can be applied in the wrong order and the document diverges. Order comes from a single owner per key that assigns sequence numbers, or from a logical clock that does not depend on wall time.

Gotcha 7: Offering one driver to two riders. Two matchers each see driver D as available and each send an offer. The driver accepts one, and the other rider waits for a car that is not coming. Moving a driver from available to offered is a conditional write on one record, exactly like a seat hold, not a read followed by a write.

Gotcha 8: Last-writer-wins on a shared document. Two people edit the same paragraph, and the server keeps whichever save arrived last. One person’s work silently vanishes. Collaborative editing needs operations that merge, OT (Operational Transformation) or CRDTs (Conflict-free Replicated Data Types), not whole-document overwrites.

Gotcha 9: Persisting presence and cursors. Cursor positions change ten times a second per user and are worthless a second later. Writing them to the document’s operation log bloats it and slows every load. Presence is ephemeral: broadcast it, throttle it, drop it on disconnect.

Gotcha 10: One global index for a local problem. A rider in Chicago will never be matched to a driver in Denver, yet a single world-wide matching service makes every update contend with every other. Shard by geography (city or region), and handle the few cross-boundary cases explicitly.

How to Answer

What defines the shape

Property Real-time shape
Traffic ratio Write-heavy in raw volume (positions, keystrokes, cursors), but each write is tiny and most are overwritten soon after
Access pattern Push from server to client over a long-lived connection, keyed by an entity: a trip, a document, a map cell
Latency A hard budget, end to end, at p99: about 100 to 200 milliseconds for typing, 1 to 5 seconds for a map marker, a few seconds for a dispatch decision
Data size Small working set. One million drivers at 200 bytes each is 200 MB. An active document is kilobytes to a few megabytes
Skew Geographic and per key: Manhattan at 6 p.m., a stadium letting out, one document with 200 editors
Consistency tolerance Stale by seconds is fine for most data. Order within a key matters. A few decisions (assignment, a committed edit) must be exact

The defining sentence: the newest value matters, the old ones mostly do not, and it has to reach a specific connected client quickly. That is why the core state lives in memory in an owner process, not in a database that is written on every update.

The generic architecture

flowchart LR
    C[Clients<br/>phones, browsers] <-->|WebSocket| G[Connection gateways<br/>stateful, ~50k conns each]
    G <--> B[Pub/sub bus<br/>topic per key]
    B <--> O[Owner services<br/>in-memory state per key:<br/>city matcher, trip, document]
    G --> R[(Connection registry<br/>user to gateway, TTL)]
    O --> L[(Durable log<br/>only what must survive)]
    L --> S[(Cold storage<br/>history, analytics)]
  • Gateways hold sockets and nothing else: authenticate, heartbeat, forward. Holding no data makes them easy to replace.
  • Owner services hold a key’s live state in memory and decide its order: one matcher per city, one session per document, placed by consistent hashing or leases (the coordination shape in miniature).
  • Durable storage gets only what must survive: the trip record, the operation log, sampled history.

Transport choice is the first decision on the board:

Transport Direction Cost Use when
Short polling Client asks every N seconds One request per client per interval, mostly empty; average delay N/2 Never for real-time; fine for a status page
Long polling Client asks, server holds the request until there is data One held request per client; reconnect after each message Fallback when WebSockets are blocked
SSE (Server-Sent Events) Server to client only, over HTTP One connection; text only; auto-reconnect built in Push-only feeds: live scores, a map marker the user does not update
WebSocket Both directions, one connection One connection; you own heartbeats, reconnect, and backpressure Chat, editing, driver apps: anything where the client also sends often

Connection arithmetic. A tuned gateway holds 50,000 to 100,000 mostly idle WebSockets at tens of kilobytes each, a few gigabytes of memory. Two million clients at 50,000 per gateway is 40 gateways, 60 with headroom. One message per client every four seconds is 500,000 messages per second, about 8,000 per gateway: comfortable.

Latency budget arithmetic. For a remote keystroke with a 200-millisecond p99 target:

Hop Same region Owner in another region
Sender to gateway (last mile, often mobile) 30 to 80 ms 30 to 80 ms
Gateway to document owner 0.5 ms 100 ms
Apply, sequence, fan out 1 to 2 ms 1 to 2 ms
Owner to receiver’s gateway 0.5 ms 100 ms
Gateway to receiver 30 to 80 ms 30 to 80 ms
Total about 60 to 160 ms about 260 to 360 ms

The hop costs are from the back-of-envelope post. So: the last mile eats most of the budget, the owner must sit near its users, and there is no room for a synchronous database write before the fan-out.

Routing a message to a connection. Either a connection registry (each gateway writes user -> gateway to an in-memory store with a short TTL (time to live), refreshed by heartbeat, and senders look it up) or topic subscription (each gateway subscribes to a pub/sub topic per key for its connections, and senders publish). Most systems use topics for keys with several watchers (a document, a trip) and the registry for direct messages to one user.

The standard problems

Problem What goes wrong Usual fix
Connection routing The message reaches a server that does not hold the recipient’s socket Connection registry with TTL, or topic per key that gateways subscribe to
Reconnect storm A gateway dies or deploys; tens of thousands of clients reconnect in one second Jittered exponential backoff on clients; incremental resync; admission limits on gateways
Uneven connections After a rolling deploy, old servers are full and new ones are empty Least-connections balancing, per-server caps, graceful drain that asks clients to move in batches
Missed messages Messages sent while a client was briefly disconnected are lost Per-key sequence numbers; client reconnects with “last seen 4,812” and the owner replays the gap or sends a snapshot
Slow consumer A client on a bad network cannot keep up; its buffer grows until the gateway runs out of memory Bounded per-connection queue; for latest-wins data, drop older updates; disconnect past the limit
Ordering Updates applied in a different order on different clients One owner per key assigns sequence numbers; clients apply in sequence order
Hot key One cell, one trip, or one document gets far more traffic than its owner can handle Subdivide the key (smaller cells), cap active editors, relay fan-out through a tree
Owner failover In-memory state is lost when the owner process dies Rebuild from snapshot plus log (durable data), or wait for the next round of updates (ephemeral data); a lease with a fencing token so the old owner cannot write after a pause
Deploys Every deploy disconnects everyone Graceful drain: stop accepting, tell clients to reconnect elsewhere over several minutes, then exit

Graceful drain deserves one number: 50,000 connections told to reconnect at once is a storm; spread over five minutes it is about 170 per second, which nobody notices.

Ride matching: a decision over a moving, partitioned supply

Special property: an exactly-once decision (this driver gets this rider) over a supply that moves every few seconds and only matters locally. Live location tolerates loss; editing tolerates none but has no geography. Matching has a fuzzy, fast-changing input and a decision that must not be duplicated.

The geo index. Finding “available drivers near this point” needs a spatial index that can be updated 250,000 times a second. A tree over coordinates (a quadtree or R-tree on disk) is the wrong tool; a hash of cells in memory is the right one. Divide the map into cells, and keep cell -> set of available drivers. When a driver moves, remove them from the old cell and add them to the new one, which is two set operations.

Scheme Cell shape Strength Weakness
Geohash Rectangles, base-32 string prefix Simple, prefix = containment, works in any key-value store Cells distort near the poles; neighbors across a prefix boundary have unrelated strings
Google S2 Quadrilaterals on a cube projected onto the sphere Precise hierarchy, good for region covering Neighbors are not equidistant
Uber H3 Hexagons, 16 resolutions All six neighbors are the same distance from the center, so “within k rings” approximates a circle Hexagons do not nest perfectly; children approximate the parent

The geohash vs. quadtree post explains how each of these works and when a tree is the better choice.

With H3 at resolution 9 (cells about 0.1 square kilometers, edges about 175 meters), a query is “the rider’s cell plus its k-ring”: one ring is 7 cells, two rings is 19. If those cells hold too few drivers, widen the ring. The candidate set is tens of drivers, not thousands.

Rank by ETA, not distance. The nearest driver by straight line may be across a river. Shortlist by cell, then rank candidates by estimated time of arrival (ETA) on the road network from a routing service.

Greedy versus batched dispatch:

Strategy How Gain Cost
Greedy Each request takes the best available driver immediately Lowest latency for the first rider Globally worse: the best driver for rider A was the only good option for rider B
Batched Collect requests for 1 to 2 seconds per area, solve an assignment over all of them Lower total ETA across riders Adds the batch window to every request’s latency

Say the trade-off and pick: batching in dense cities where many requests overlap, greedy where requests are sparse.

The contended write. The driver is a state machine: available -> offered -> assigned -> on_trip. Moving from available to offered is a conditional write on the driver’s record, set status = offered, offer = R1, expires = now + 15s where status = available and version = 7, owned by the city’s matcher. If it fails, someone else got the driver first, and the matcher moves to the next candidate. The offer has an expiry checked in the same conditional write, exactly like a seat hold in the ticket booking design. This is the contended writes shape hiding inside the real-time one, and it is small: one record, held for seconds.

Shard by city. Requests and drivers in a city only interact with each other. One matcher per city (large cities split into zones) keeps index and driver state in one process, so the conditional write is local, not distributed. At boundaries (an airport between cities), a matcher reads its neighbor’s index and claims through the owner of the driver’s zone.

Surge. A supply-to-demand ratio per cell over a sliding window, recomputed every minute: a small write-heavy ingest aggregate. The rider gets a quote token that expires in a few minutes, so they pay what they saw even if surge moves before the match.

Failure. If a city’s matcher dies, its index is empty, but every available driver reports within four seconds, so it rebuilds itself. Driver records with offers in flight live in a store that survives restarts, and the trip record is a real database transaction, because it is money.

Live location: high-frequency writes where only the latest matters

Special property: an enormous stream of tiny writes, each making the previous one worthless. Editing keeps every operation; live location keeps almost nothing, and the design is about how much to throw away.

The arithmetic.

Quantity Value
Active drivers 1,000,000
Update interval while moving 4 seconds
Updates per second 1,000,000 / 4 = 250,000
Bytes per update (id, lat, lng, heading, speed, timestamp, sequence) about 200
Inbound bandwidth 250,000 x 200 B = 50 MB/s
Updates per day 250,000 x 86,400 = 21.6 billion
Raw volume per day if all kept about 4.3 TB
Size of “latest position for everyone” 1,000,000 x 200 B = 200 MB

So: the current state fits in the memory of one machine, the write rate does not fit on one relational primary, and storing every point forever is terabytes a day of data nobody reads. The design follows from those three facts.

Last-known-position store. An in-memory key-value store keyed by driver id. A Redis-class node does about 100,000 operations per second, so 250,000 overwrites per second needs three to five shards, split by city so the matcher reads local data. No replication for durability: a lost shard regenerates within one update interval.

Throttle and coalesce at every layer.

  • Client: every 4 seconds while moving, every 30 while parked, every second near pickup. This alone halves the average rate.
  • Server: if three updates for one driver are queued for a watcher, send only the newest. Dropping is correct for latest-wins data.
  • Gateway: a slow consumer’s queue holds at most one pending position per driver, so a bad network means fewer updates, not a growing backlog.

Ordering per device. Mobile networks retry and reorder. Each device stamps its updates with an increasing sequence number, and the store applies an update only if its sequence is higher than the stored one. This is a comparison per device, so it never depends on clocks agreeing between devices.

Fan-out to watchers is narrow. The rider, perhaps someone they shared the trip with, and the matcher: one to three watchers, unlike the fan-out shape. Publish to a topic per trip; the rider’s gateway subscribes for the trip and the subscription ends with it, which also enforces privacy.

Smooth motion on the client. The client interpolates between points and extrapolates briefly from heading and speed (dead reckoning), snapping to the road. Most real-time smoothness is client animation over a modest update rate.

History, sampled. Every update goes onto a durable log (Kafka-style) for consumers that need it; a downstream job writes trip routes at full resolution (for fares, receipts, and disputes) and off-trip positions sampled to one every 30 to 60 seconds, in batches to object storage. That is the write-heavy ingest shape, kept entirely off the live path. Retention is a policy decision: location history is sensitive personal data, so say how long you keep it.

Collaborative editing: concurrent edits must converge

Special property: many people change the same object at once, every change matters, and all copies must end up identical, even when two edits were made against different versions.

Local echo first. The typist’s keystroke is applied locally at zero latency and sent in the background. The 200-millisecond budget is for other people seeing it.

One document, one owner. All editors of document D reach the single session process that owns it. The owner holds D in memory, assigns each operation a sequence number, and broadcasts it: a total order per document with no consensus on the hot path, the same move as one matcher per city.

OT versus CRDT. The core problem: Alice inserts “x” at position 5 while Bob deletes position 3. Applied naively in different orders, the copies diverge.

  OT (Operational Transformation) CRDT (Conflict-free Replicated Data Type)
Idea Operations are positions. When an operation arrives that was made against an older version, transform it against the operations it missed (Alice’s insert at 5 becomes an insert at 4) Every character gets a unique, ordered identifier. Operations reference identifiers, not positions, and are designed to commute, so any order gives the same result
Needs a central server Practically yes: the server’s order defines the transforms No: peers can merge directly, which suits offline and peer-to-peer
Metadata cost Low: the document is plain text plus a version Higher: identifiers per character and tombstones for deletions, though modern implementations compress this heavily
Offline edits Possible but painful: a long offline session must be transformed against everything that happened since Natural: merge whenever reconnected
Known users Google Docs (descended from the Jupiter system) Yjs and Automerge; Figma uses a server-authoritative design inspired by CRDTs

The interview answer: with a central owner per document already in the design, OT is proven and cheap. If offline-first or peer-to-peer editing is a requirement, choose a CRDT and accept the metadata. Either way, say that last-writer-wins on the whole document is not an option.

Persistence: log plus snapshots. Unlike positions, an edit must not be lost once the user has seen it acknowledged. The owner appends each operation to a durable, replicated log before acknowledging it, then broadcasts. Every 1,000 operations or after a minute idle, it writes a snapshot. Loading a document is “latest snapshot plus the log tail,” which keeps load time bounded. An active typist produces a few operations per second, so even a busy document generates a log that a snapshot every few minutes keeps small.

Reconnect and offline. The client keeps unacknowledged operations in a local queue, each tagged with a client operation id and the last server sequence it had seen. On reconnect it resends them; the owner deduplicates by operation id (the idempotency key pattern) and transforms or merges them against what it missed. The client asks for the gap from its last sequence rather than reloading the document.

Presence is a separate, lossy channel. Cursors, selections, and “Alice is viewing” go through the same owner and connection but are never logged, are throttled to around 10 updates per second per user, and are dropped on disconnect. Mixing them into the operation log is gotcha 9.

Hot documents. A document with 10,000 viewers is a fan-out problem for its owner. Cap simultaneous editors and serve extra viewers a read-only stream through a relay tier, so the owner sends each operation once, not 10,000 times.

Owner failover. The owner holds a lease on the document. If it dies, a new owner takes the lease with a higher fencing token, loads snapshot plus log, and clients reconnect and resend their unacknowledged operations. The fencing token stops a paused old owner from appending to the log after it has been replaced, the same mechanism as in the job scheduler design.

Side by side

  Ride matching Live location Collaborative editing
Special property Exact decision over a moving, local supply Huge rate of writes; only the latest matters Concurrent edits must converge; nothing may be lost
Owner key City or zone Driver (stored), trip (watched) Document
Latency budget A few seconds to a match 1 to 5 seconds to the map About 200 ms for remote edits; 0 ms local echo
Durability Trip record durable; index ephemeral Latest ephemeral; history sampled Every acknowledged operation durable
Ordering Driver state transitions on one record Per-device sequence numbers Per-document sequence from the owner
Dropping updates Fine for positions, never for offers Correct and encouraged Never for operations; fine for cursors
The hard part Geo index, conditional assignment, city sharding Throttling, in-memory overwrite, sampling OT or CRDT, log plus snapshots, reconnect
Recovery after owner loss Rebuilds from the next round of pings Regenerates within one interval Snapshot plus log, clients resend

Where each example stops being real-time

Example The part that is a different shape Shape
Ride matching Assigning the driver: a conditional write on one hot record Contended writes
Ride matching The trip and payment flow after the match Contended writes plus a saga
Ride matching Scheduled rides booked for tomorrow Coordination (a scheduler)
Live location History, analytics, surge inputs Write-heavy ingest
Live location One position watched by thousands (a marathon tracker, a live sports map) Fan-out
Collaborative editing Document list, search, permissions lookup Read-heavy lookup
Collaborative editing Comment notifications and @mentions Fan-out
Collaborative editing Placing document owners and handing them over Coordination

The sentence to say in the interview

This is a real-time system, so I will start from the latency budget and work backward. Clients hold WebSocket connections to a gateway tier, and each key (a city, a trip, a document) has one owner process that holds its live state in memory and decides the order of updates. Data that is replaced every few seconds stays in memory and is sampled to cold storage; the few things that must be exact, like assigning a driver or acknowledging an edit, are a conditional write or a durable log append. The rest of the design is about routing messages to the right connection and surviving reconnects.

The question that impresses: “Which updates can we drop, and which single decision must never happen twice?”

Follow-Up Questions to Expect

  • “What happens when a gateway dies?” Its clients reconnect with jittered backoff to other gateways, re-register or resubscribe, and resume from their last sequence number. The registry entries for the dead gateway expire by TTL. No state is lost because gateways hold sockets, not data.
  • “How do you deploy without dropping everyone?” Graceful drain: the gateway stops accepting new connections, sends clients a reconnect hint in batches over several minutes, waits for them to leave, then exits. Owners hand over keys through the lease mechanism.
  • “How do you know the driver’s position is fresh?” Store the device timestamp and sequence with the position, and treat anything older than about 15 seconds as unknown in the matcher. A driver whose app is in a tunnel should not be offered a ride.
  • “OT or CRDT?” With a server owner per document, OT is simpler and lighter. With offline-first or peer-to-peer requirements, a CRDT. Both converge; they differ in where the merge logic lives and what metadata they carry.
  • “How does this work in multiple regions?” Place each key’s owner in the region nearest its users: a city’s matcher in that city’s region, a document’s owner where most of its editors are. Cross-region edits pay the 100-millisecond round trip, which fits inside a 200-millisecond typing budget only barely, so say it.

Key Takeaways

  • Real-time is defined by a latency budget, ordering per key, and long-lived connections. Start from the budget, and note that the last mile spends most of it.
  • Connections are state. Name how a message finds the gateway holding the socket (registry or topic), and how reconnect storms and deploys are survived (backoff with jitter, incremental resync, graceful drain).
  • One owner per key (city, trip, document) holds live state in memory and assigns order. No consensus on the hot path.
  • Ephemeral data stays in memory and is overwritten; history is sampled off the live path. Durable data (trips, edit operations) is written before it is acknowledged.
  • Ride matching: an in-memory hexagon or cell index per city, rank by ETA, and assign with a conditional write so no driver is offered twice.
  • Live location: 1 million drivers every 4 seconds is 250,000 writes per second into 200 MB of state. Throttle, coalesce, and drop older updates.
  • Collaborative editing: local echo, one owner per document, OT or CRDT to converge, log plus snapshots, presence on a separate lossy channel.

Further Reading

The Six Shapes

Each shape has its own deep dive. Start with the first five minutes to see how naming the shape fits into the opening of an interview.

Shape Examples Where the difficulty is
Read-heavy lookup URL shortener, product catalog, profile service Cache and read path; writes are trivial
Write-heavy ingest Metrics, logging, clickstream Ingest path, storage tiering, downsampling
Fan-out News feed, notifications, chat Delivery to many recipients; hot users
Contended writes Ticketing, inventory, auctions Consistency on a hot row; the peak moment
Coordination Scheduler, workflow engine, locks Leases, exactly-once claims, failure recovery
Real-time (you are here) Ride matching, live location, collaborative editing Latency, ordering, stateful connections
This post is licensed under CC BY 4.0 by the author.