Case Studies: Media, Location and Money

Requirements

Functional, agreed with the interviewer:

• Creators upload videos (up to a few GB, from flaky mobile connections, so uploads must be resumable).
• The system processes each upload into streamable renditions and thumbnails; the video becomes watchable within minutes.
• Viewers watch on phones, browsers and TVs, with quality adapting to their network; they can seek.
• Viewers see title, creator and view count. Search, recommendations, comments and live streaming are out of scope (say so; live changes the segment and latency story, see the gotcha below).

Non-functional:

• Playback start under about 2 seconds and rare rebuffering: the metrics viewers feel.
• Watch path highly available (99.99% or better); the upload and processing path can be less available and slower.
• Originals are never lost: a creator's upload is the only copy. Store it durably (object storage is designed for 11 nines of durability; AWS states 99.999999999% for S3) before acknowledging.
• Cost: egress and storage dominate, so every decision is checked against bytes served and bytes stored.
• Scale: 500 hours uploaded per minute and 1 billion hours watched per day, the YouTube figures above.

Estimates

// Assumptions (YouTube-scale, from the figures quoted above; change them and re-run).
const uploadHoursPerMin = 500;          // hours of new video per minute
const watchHoursPerDay = 1e9;           // hours watched per day
const ladderKbps = [145, 365, 730, 1100, 2000, 3000, 4500, 6000, 7800]; // Apple's H.264 example ladder
const avgWatchKbps = 2500;              // average rung actually streamed
const segmentSec = 6;                   // HLS target duration
const peakFactor = 2;                   // evening peak vs daily average
const sourceMbps = 10;                  // what creators upload (1080p, high quality)

const GB = 1e9, PB = 1e15;
const uploadHoursPerDay = uploadHoursPerMin * 60 * 24;
const ladderBytesPerHour = ladderKbps.reduce((a, b) => a + b, 0) * 1000 / 8 * 3600;
const storedPerDay = uploadHoursPerDay * ladderBytesPerHour;
const segmentsPerDay = uploadHoursPerDay * (3600 / segmentSec) * ladderKbps.length;
const egressPerDay = watchHoursPerDay * 3600 * avgWatchKbps * 1000 / 8;
const avgTbps = (egressPerDay * 8) / 86400 / 1e12;

console.log(`uploaded:        ${uploadHoursPerDay.toLocaleString("en")} hours/day`);
console.log(`ingest:          ${((uploadHoursPerDay * 3600 * sourceMbps) / 86400 / 1000).toFixed(0)} Gbps of source video, ${((uploadHoursPerDay * 3600 * sourceMbps * 1e6) / 8 / PB).toFixed(1)} PB/day of originals`);
console.log(`ladder:          ${(ladderBytesPerHour / GB).toFixed(1)} GB per hour of video (all ${ladderKbps.length} rungs)`);
console.log(`new renditions:  ${(storedPerDay / PB).toFixed(1)} PB/day, ${(storedPerDay * 365 / 1e18).toFixed(1)} EB/year`);
console.log(`new segments:    ${(segmentsPerDay / 1e9).toFixed(1)} billion files/day`);
console.log(`egress:          ${(egressPerDay / 1e18).toFixed(2)} EB/day`);
console.log(`bandwidth:       ${avgTbps.toFixed(0)} Tbps average, ${(avgTbps * peakFactor).toFixed(0)} Tbps peak`);
console.log(`read:write:      ${(egressPerDay / storedPerDay).toFixed(0)} bytes served per byte stored`);

uploaded:        720,000 hours/day
ingest:          300 Gbps of source video, 3.2 PB/day of originals
ladder:          11.5 GB per hour of video (all 9 rungs)
new renditions:  8.3 PB/day, 3.0 EB/year
new segments:    3.9 billion files/day
egress:          1.13 EB/day
bandwidth:       104 Tbps average, 208 Tbps peak
read:write:      135 bytes served per byte stored

API

POST /v1/uploads                      { title, sizeBytes, contentType }
  -> 201 { uploadId, partSize: 8388608, partUrls: [ ...presigned PUT URLs... ] }
PUT  <presigned part URL>             raw bytes of part n, straight to object storage; retry a part, not the file
POST /v1/uploads/{uploadId}/complete  { parts: [ { n, etag } ] }
  -> 202 { videoId, status: "processing" }
GET  /v1/videos/{videoId}
  -> 200 { title, status, durationSec, manifestUrl, thumbnails }
GET  https://cdn.example.com/v/{videoId}/master.m3u8     served by the CDN, not by the API
POST /v1/playback-events              batched: { videoId, startupMs, stalls, rendition, watchedSec }

The upload is a multipart, presigned upload: the API only hands out URLs and records progress; the bytes go from the creator's device to object storage, part by part, so a dropped connection costs one part, not the whole file. This is the pattern from object storage for files and media. The 202 on complete says "accepted, not done": processing is asynchronous and the client polls GET /v1/videos/{id} or receives a notification. Playback telemetry (start-up time, stalls) is how you will know whether the ABR and CDN choices work, so it belongs in the API from the start.

Data model

Two decisions worth saying aloud. Segment files are immutable: a re-encode writes new paths and a new manifest, so the CDN never needs purging. And the 3.9 billion new segments a day can be one object each, or each rendition can be a single fragmented MP4 file that the playlist addresses with byte ranges (HLS supports this with EXT-X-BYTERANGE), which cuts the object count by 600 times per hour of video at the cost of range-request support at every cache.

High-level design

Walk the interviewer through it in two passes. Upload: the client creates an upload, sends parts straight to object storage with presigned URLs, and calls complete; the object-created event puts a job on a queue (why queues: the transcoders run at their own pace and a burst of uploads just makes the queue longer). Transcoders split, encode and package, write the renditions, and flip the video to ready. Watch: the player asks the video API for metadata and the manifest URL, then every byte of video comes from the CDN. On a miss the edge asks an origin shield (one mid-tier cache per region, so a new video causes one origin read per region rather than one per edge, see CDNs), and only the shield reads object storage.

A 10-minute upload must become 9 renditions of 100 segments each. Doing it as one job on one machine is slow; the trick is to split first, then encode the pieces in parallel:

1. Split the original into chunks of one segment each. The upload's own keyframes can be anywhere, so the splitter cuts at the source's keyframes nearest each boundary (or decodes across the boundary), and every encoded chunk is made to start with a fresh keyframe (IDR). Apple's HLS authoring specification asks for an IDR every 2 seconds and 6-second segments, so each 6-second output chunk starts on a keyframe and was encoded independently of its neighbours.
2. Encode every chunk at every rung as a separate task: (chunk, rung) pairs are independent, so they fan out across a worker pool.
3. Package the encoded chunks into segments and write the media playlists and the master playlist.
4. Publish: write the renditions rows and set status = ready in one transaction; the CDN needs no warming, because the first viewer's miss fills it.

How much parallelism buys you, with encoding assumed to run at 2× real time per rung per vCPU (a rule of thumb that varies a lot with codec and preset):

// Assumptions: encoding one rung runs at 2× real time on one vCPU (a rule of thumb; it depends heavily on codec
// and preset), and a chunk is one 6-second segment.
const rungs = 9, encodeSpeed = 2, chunkSec = 6;
const uploadHoursPerDay = 720_000;

function wallClock(videoMin, workers) {
  const tasks = Math.ceil((videoMin * 60) / chunkSec) * rungs;  // one task = one chunk at one rung
  const taskSec = chunkSec / encodeSpeed;
  const waves = Math.ceil(tasks / workers);                     // tasks run in parallel waves
  return { tasks, seconds: waves * taskSec };
}

for (const [min, workers] of [[10, 1], [10, 100], [10, 900], [120, 900]]) {
  const r = wallClock(min, workers);
  const t = r.seconds >= 60 ? `${(r.seconds / 60).toFixed(1)} min` : `${r.seconds} s`;
  console.log(`${String(min).padStart(3)}-min video, ${String(workers).padStart(3)} ${workers === 1 ? "worker: " : "workers:"} ${String(r.tasks).padStart(5)} tasks, ${t.padStart(8)} of encoding`);
}
const cpuHoursPerDay = (uploadHoursPerDay * rungs) / encodeSpeed;
console.log(`fleet: ${(cpuHoursPerDay / 1e6).toFixed(2)} M vCPU-hours/day = ${Math.round(cpuHoursPerDay / 24).toLocaleString("en")} vCPUs busy around the clock`);

 10-min video,   1 worker:    900 tasks, 45.0 min of encoding
 10-min video, 100 workers:   900 tasks,     27 s of encoding
 10-min video, 900 workers:   900 tasks,      3 s of encoding
120-min video, 900 workers: 10800 tasks,     36 s of encoding
fleet: 3.24 M vCPU-hours/day = 135,000 vCPUs busy around the clock

Make every task idempotent: its output path is derived from (videoId, rung, chunk), so a retried task overwrites the same object with the same bytes. The job queue delivers at least once, a worker can die halfway, and the pipeline still converges (the idea from idempotency and exactly-once). Track the DAG's progress in a table keyed by video, so a coordinator can see which tasks are missing and re-enqueue only those. Put uploads from big creators on a priority queue if the business wants their videos live first.

The player never sees "a video"; it sees playlists. The master playlist lists the rungs, and each rung's media playlist lists its segments:

#EXTM3U
#EXT-X-STREAM-INF:BANDWIDTH=7200000,AVERAGE-BANDWIDTH=6000000,RESOLUTION=1920x1080,CODECS="avc1.640028,mp4a.40.2"
avc_1080p/playlist.m3u8
#EXT-X-STREAM-INF:BANDWIDTH=3600000,AVERAGE-BANDWIDTH=3000000,RESOLUTION=1280x720,CODECS="avc1.64001f,mp4a.40.2"
avc_720p/playlist.m3u8
#EXT-X-STREAM-INF:BANDWIDTH=180000,AVERAGE-BANDWIDTH=145000,RESOLUTION=416x234,CODECS="avc1.42c00d,mp4a.40.2"
avc_234p/playlist.m3u8

BANDWIDTH is the peak bitrate of the rung and AVERAGE-BANDWIDTH its average; the player compares its throughput estimate with these numbers. The playlist shows three of the nine rungs, and its peak values are illustrative: Apple's spec asks for the measured peak and average to be within 10% of these attributes, and for on-demand video a peak of no more than 200% of the average. The ladder used on this page is Apple's example H.264 ladder from the HLS authoring specification (checked October 2026): 416×234 at 145 kbps, 640×360 at 365, 768×432 at 730 and 1100, 960×540 at 2000, 1280×720 at 3000 and 4500, 1920×1080 at 6000 and 7800. The same document gives an HEVC ladder that reaches 1080p at 4,500–5,800 kbps, roughly a quarter less than H.264 for the same picture, and 4K at 11,600–16,800 kbps. Apple presents it as "one possible set" of variants, not a requirement.

Segment length is a trade-off you should be able to defend. HLS's authoring spec asks for 6-second segments; DASH deployments commonly use 2 to 6 seconds (Bitmovin's 2020 guide gives 2–6 s as the typical range for on-demand video). Shorter segments let the player react sooner and cut live latency, but they mean more requests per minute, more playlist entries and more keyframes (keyframes are expensive, so compression gets worse). Longer segments compress better and cost fewer requests, but the player reacts later, and a bad pick costs more buffer. For video on demand, 6 s is a good default; for live, segments get shorter and are split into smaller chunks (low-latency HLS and CMAF chunked transfer).

The ABR algorithm is a client decision, and there are two families. Throughput-based players, like the model above, estimate bandwidth from recent downloads and pick the highest rung below a safety fraction of it. Buffer-based players (BOLA is the best-known; dash.js ships it) pick from the buffer level alone: low buffer means low rung, full buffer means high rung, which avoids trusting noisy throughput samples. Production players mix both, start on a low or middle rung for fast start-up, and abandon a download that would empty the buffer, as segment 6 showed.

At 208 Tbps the question isn't "should we use a CDN" but "how much of the catalogue must sit at the edge to keep origin egress affordable". Video popularity is heavily skewed: a few videos get most views, and millions get a handful. This model assumes a Zipf distribution with skew 0.9 over 10 million videos and asks what share of views the edge can serve if it holds the top K:

// Popularity of N videos follows a Zipf law: the k-th most popular gets views ∝ 1 / k^s.
const N = 10_000_000;   // videos in the catalogue
const s = 0.9;          // skew: an assumption; measure your own catalogue
const egressTbps = 208; // peak from the estimate above
const gbPerVideo = (11.5 * 8) / 60; // 8-minute average video, all rungs (11.5 GB per hour)

// Prefix sums of the weights, so "share of views in the top K" is one division.
const prefix = new Float64Array(N + 1);
for (let k = 1; k <= N; k++) prefix[k] = prefix[k - 1] + 1 / k ** s;
const share = (K) => prefix[K] / prefix[N];

console.log("edge holds top K   storage   hit ratio   origin egress at peak");
for (const K of [1_000, 10_000, 100_000, 1_000_000, 5_000_000]) {
  const hit = share(K);
  const pb = (K * gbPerVideo) / 1e6;
  console.log(`${K.toLocaleString("en").padStart(16)}   ${(pb < 1 ? (pb * 1000).toFixed(0) + " TB" : pb.toFixed(1) + " PB").padStart(7)}` +
    `   ${(hit * 100).toFixed(1).padStart(8)}%   ${(egressTbps * (1 - hit)).toFixed(0).padStart(5)} Tbps`);
}

edge holds top K   storage   hit ratio   origin egress at peak
           1,000      2 TB       25.9%     154 Tbps
          10,000     15 TB       38.6%     128 Tbps
         100,000    153 TB       54.5%      95 Tbps
       1,000,000    1.5 PB       74.7%      53 Tbps
       5,000,000    7.7 PB       91.8%      17 Tbps

Netflix's Open Connect is the extreme version. Netflix's page on how it works with ISPs says Open Connect delivers 100% of its video traffic, close to 90% of it over direct connections with the residential ISPs its members use, and Netflix gives qualifying ISPs its cache appliances for free to put inside their networks. Those figures are old: the page is undated, but it gives viewing as "over 125 million hours" a day, the figure Digital TV Europe reported for Open Connect in March 2016, and a June 2018 APNIC blog post on Open Connect already put the direct share at close to 95%. Treat them as roughly ten-year-old figures that show the approach, not as current numbers. For an interview, the layered answer is enough: edge caches in many cities, an origin shield per region, object storage as the origin, a cache key that ignores per-user query parameters, and long TTLs because segments are immutable. For paid or private content, the player gets short-lived signed URLs or cookies that the edge validates, so access control doesn't break caching.

Pre-positioning helps the head: when a new episode of a popular show is due, push it to edges overnight ("fill") instead of letting the first viewers' misses pull it at peak. Rarely watched long-tail videos can stay at the origin and in regional shields only.

Trade-offs and what to say

Requirements

Functional:

• Upload, download, rename, move and delete files and folders, of any type, up to tens of GB.
• Sync automatically across a user's devices; a change shows up on the other devices within seconds when they're online.
• Work offline and sync when back online.
• Share folders with other users (they become part of a shared namespace).
• Keep version history (for example 30 days) and restore deleted files.

Non-functional:

• Durability above everything: never lose a file or silently overwrite someone's edit. Conflicts must keep both versions.
• Bandwidth efficiency: small edits to large files must not re-upload the file (mobile data, slow uplinks).
• Sync latency of seconds for small changes; large uploads can take as long as the network needs, and are resumable.
• Consistency: one path has one current revision per namespace, and every device ends up at the same state (eventually, in seconds). Strong consistency for the commit of a revision; eventual for propagation.
• Scale: 500 M accounts, 100 M daily active users.

Estimates

// Assumptions for a Dropbox-like service (state them; the interviewer can change them).
const users = 500e6, dauShare = 0.2;     // 500 M accounts, 20% active on a given day
const storedPerUserGB = 15;              // average used quota
const editsPerDau = 20;                  // files created or changed per active user per day
const avgFileKB = 300;                   // average changed file
const blockMiB = 4;                      // Dropbox's content-hash block size
const devicesPerUser = 2.5;              // each change must reach the user's other devices
const dedupSaving = 0.3;                 // assumed share of bytes already stored (identical blocks)
const peak = 3;

const dau = users * dauShare;
const writesPerSec = (dau * editsPerDau) / 86400;
const uploadGbps = (writesPerSec * avgFileKB * 1e3 * 8) / 1e9;
const logicalEB = (users * storedPerUserGB * 1e9) / 1e18;
const blocks = (users * storedPerUserGB * 1e9) / (blockMiB * 2 ** 20);
const notifyPerSec = writesPerSec * (devicesPerUser - 1);

console.log(`DAU:                  ${(dau / 1e6).toFixed(0)} M`);
console.log(`file commits:         ${Math.round(writesPerSec).toLocaleString("en")}/s average, ${Math.round(writesPerSec * peak).toLocaleString("en")}/s peak`);
console.log(`upload bandwidth:     ${uploadGbps.toFixed(0)} Gbps average (before dedup)`);
console.log(`stored (logical):     ${logicalEB.toFixed(1)} EB, ${(logicalEB * (1 - dedupSaving)).toFixed(2)} EB after ${dedupSaving * 100}% dedup`);
console.log(`block index:          at least ${(blocks / 1e12).toFixed(1)} trillion entries, ${((blocks * 64) / 1e12).toFixed(0)} TB at 64 B each`);
console.log(`change notifications: ${Math.round(notifyPerSec).toLocaleString("en")}/s to other devices`);

DAU:                  100 M
file commits:         23,148/s average, 69,444/s peak
upload bandwidth:     56 Gbps average (before dedup)
stored (logical):     7.5 EB, 5.25 EB after 30% dedup
block index:          at least 1.8 trillion entries, 114 TB at 64 B each
change notifications: 34,722/s to other devices

API

POST /v1/blocks/check            { hashes: ["9f86…", "2c26…"] }      -> { missing: ["2c26…"] }
PUT  /v1/blocks/{sha256}         raw bytes (≤ 4 MiB); server recomputes the hash and rejects a mismatch
GET  /v1/blocks/{sha256}         raw bytes
POST /v1/commit                  { namespace, path, baseRev, blocks: [...], size, mtime }
  -> 200 { rev }                 when baseRev is still the current revision
  -> 409 { currentRev }          someone committed first: the client keeps both versions
GET  /v1/changes?namespace=&cursor=     -> { entries: [...], cursor, hasMore }
GET  /v1/changes/wait?cursor=&timeout=60 -> { changed: true | false }      long poll

The order of calls is the protocol. A client uploads blocks first and commits metadata second, so a committed revision can never point at a block the server doesn't have; a crash between the two leaves only unreferenced blocks, which garbage collection removes later. PUT /v1/blocks/{sha256} is idempotent by construction: the URL is the content's hash, so a retried upload writes the same bytes to the same key. The commit carries baseRev, the revision the client's edit started from, which turns it into a compare-and-set.

Data model

Shard the metadata by namespace: every commit, conflict check and journal read touches one namespace, so it is one shard and one transaction. A huge shared namespace (a company-wide folder) can be hot; that is the resharding problem from partitioning and sharding, solved by giving big namespaces their own shards. Blocks are shared across namespaces only if you dedup globally.

High-level design

The client is a big part of this design and worth naming: a file watcher notices changes, a chunker cuts and hashes, a local database remembers the last synced revision and block list of every path, and an upload queue retries blocks independently. On the server the block service is stateless (it streams bytes to and from object storage), and the metadata service is the one stateful, carefully designed component. Notifications only say "something changed"; the device pulls the details with its cursor, so a missed notification costs latency, never correctness.

Naming blocks by their hash gives three things at once. Integrity: the server recomputes the SHA-256 of every uploaded block and rejects one that doesn't match its URL. Idempotency: uploading the same block twice is harmless. Deduplication: identical blocks are stored once, whether they come from the previous version of the same file, a copy in another folder, or (if you allow it) another user.

Choosing the chunking scheme is choosing where to pay:

A practical design mixes them: content-defined chunking with a large average (around 1 MiB) for big files, so inserts stay cheap and the block count stays manageable, and whole-file blocks for small files, which are most files by count and are usually rewritten entirely anyway. Files that are already compressed or encrypted (videos, zip archives) dedup poorly whatever you do.

Deleting is the hard part of dedup. A block may be referenced by many file revisions in many namespaces, so you can't delete it when one file goes away. Keep a reference count per block, or periodically mark every block still referenced by a live revision and sweep the rest after a grace period (safer: a reference-count bug becomes data loss). Version history (30 days) means old revisions keep their blocks alive until they expire.

Every namespace has one journal with a sequence number that only goes up. A device's state is one number per namespace: the cursor, the last seq it applied. Syncing a device is "give me everything after my cursor", which makes the protocol simple and restartable: a device that was offline for a week sends cursor 41 and gets the entries from 42 onwards, in order, page by page.

Pushing the change itself to every device would be fragile (devices are offline, connections drop), so the push is only a hint. Each device holds a long poll (GET /v1/changes/wait) or a WebSocket to the notification service, which subscribes to the change log for that device's namespaces. When a commit lands, the hint goes out, the device calls GET /v1/changes with its cursor, applies the entries to its local database, fetches missing blocks from the block service, writes the file, and advances its cursor. At 34,722 hints a second, the notification tier is a fan-out problem like the ones in pub/sub and fan-out, but each message is a few bytes.

Applying entries in seq order matters: a rename followed by an edit applied in the other order would edit a path that doesn't exist yet. The journal gives the order for free.

Two devices edit the same file from the same revision while one of them is offline. When both commit, one has to lose the race. The question is what "lose" means. This model plays the scenario with the metadata service's compare-and-set:

// Metadata service: the latest revision of each path, plus an append-only journal of every change.
const files = new Map();   // path -> { rev, blocks, by }
const journal = [];        // { seq, path, rev, blocks }

// A conflicted copy gets a name no other file has: the device and the date, then a counter if even that is taken.
function conflictName(path, device, day) {
  const [, base, ext] = path.match(/^(.*?)(\.\w+)?$/);
  const tag = `${device}'s conflicted copy ${day}`;
  let name = `${base} (${tag})${ext ?? ""}`;
  for (let n = 2; files.has(name); n++) name = `${base} (${tag} ${n})${ext ?? ""}`;
  return name;
}

function commit(device, path, baseRev, blocks, day) {
  const cur = files.get(path);
  if ((cur?.rev ?? 0) !== baseRev) {                       // someone committed since this device last synced
    return commit(device, conflictName(path, device, day), 0, blocks, day); // a new file: never drop a user's edit
  }
  const rev = baseRev + 1;
  files.set(path, { rev, blocks, by: device });
  journal.push({ seq: journal.length + 1, path, rev, blocks });
  return { path, rev };
}

// A device asks "what changed since my cursor?" and applies it.
function pull(device) {
  const changes = journal.filter((e) => e.seq > device.cursor);
  for (const e of changes) device.local.set(e.path, { rev: e.rev, blocks: e.blocks });
  device.cursor = journal.length;
  return changes.map((e) => `${e.path}@${e.rev}`);
}

const laptop = { cursor: 0, local: new Map() }, phone = { cursor: 0, local: new Map() };
const base = (device) => device.local.get("plan.txt").rev;  // the revision this device's edit starts from
const day = "2026-10-24";                                   // a fake clock: the commit date

console.log("laptop creates:", commit("laptop", "plan.txt", 0, ["b1", "b2"], day));
pull(phone); pull(laptop);

// Both go offline and edit the same file from revision 1.
console.log("laptop commits:", commit("laptop", "plan.txt", base(laptop), ["b1", "b3"], day));
console.log("phone commits: ", commit("phone", "plan.txt", base(phone), ["b4", "b2"], day));
pull(phone); pull(laptop);
// Later the same day both edit offline again, now from revision 2, and the phone loses the race again.
console.log("laptop commits:", commit("laptop", "plan.txt", base(laptop), ["b1", "b6"], day));
console.log("phone commits: ", commit("phone", "plan.txt", base(phone), ["b5", "b2"], day));

console.log("phone pulls:   ", pull(phone));
console.log("laptop pulls:  ", pull(laptop));
for (const [p, f] of files) console.log(`server has:     ${p} rev ${f.rev} blocks ${f.blocks} (by ${f.by})`);

laptop creates: { path: 'plan.txt', rev: 1 }
laptop commits: { path: 'plan.txt', rev: 2 }
phone commits:  { path: "plan (phone's conflicted copy 2026-10-24).txt", rev: 1 }
laptop commits: { path: 'plan.txt', rev: 3 }
phone commits:  { path: "plan (phone's conflicted copy 2026-10-24 2).txt", rev: 1 }
phone pulls:    [ 'plan.txt@3', "plan (phone's conflicted copy 2026-10-24 2).txt@1" ]
laptop pulls:   [ 'plan.txt@3', "plan (phone's conflicted copy 2026-10-24 2).txt@1" ]
server has:     plan.txt rev 3 blocks b1,b6 (by laptop)
server has:     plan (phone's conflicted copy 2026-10-24).txt rev 1 blocks b4,b2 (by phone)
server has:     plan (phone's conflicted copy 2026-10-24 2).txt rev 1 blocks b5,b2 (by phone)

The alternatives, so you can argue for the choice: last-write-wins (simple, loses data, unacceptable for user files; see last-write-wins and CRDTs); locking (check-out/check-in, as some enterprise tools do; prevents conflicts, but a lock held by an offline laptop blocks everyone); merging (only possible when the system understands the content, which is what a collaborative editor does with operational transforms or CRDTs, see collaborative document editor). A file sync service keeps both copies and leaves merging to the user or the application.

Trade-offs and what to say

Requirements

Functional:

• Riders see nearby available cars on the map and request a ride from a pickup to a destination.
• The system matches the request to a nearby available driver within seconds; the driver accepts or declines.
• Both sides see each other's live position until pickup, and the rider sees the trip's progress.
• Trip completion produces a fare and a payment (payment itself is the payment system). Pricing, ETAs and surge are mentioned but not designed in depth.

Non-functional:

• Matching latency: a match within a few seconds; the nearby-cars map updates every few seconds.
• No double assignment: a driver is never offered or assigned to two trips at once. This needs strong consistency per driver, even though positions themselves can be eventually consistent and a few seconds stale.
• High write throughput: location updates outnumber everything else by orders of magnitude.
• Availability: degrade gracefully per city; a problem in one region must not stop the others.
• Scale: 1.5 M drivers online at the busiest hour, 30 M rides a day.

Estimates

Uber's developer documentation (the Guest Rides API's driver-location webhook, checked October 2026) says the webhook is sent every 4 seconds by default during a trip, and notes that frequent driver location webhooks are "not available in all regions". That is a public figure for how often positions are shared with partners; the driver app's own reporting interval isn't published, so this estimate assumes 4 seconds as well.

// Assumptions for a global ride-hailing service at peak.
const driversOnline = 1.5e6;     // drivers with the app on at the busiest hour
const updateEverySec = 4;        // driver app reports its location every 4 s
const updateBytes = 100;         // id, lat, lng, heading, speed, timestamp, plus overhead
const ridesPerDay = 30e6;
const peakFactor = 3;
const indexEntryBytes = 64;      // in-memory: id, position, cell, status

const updatesPerSec = driversOnline / updateEverySec;
const ridesPeak = (ridesPerDay / 86400) * peakFactor;
console.log(`location updates:   ${updatesPerSec.toLocaleString("en")}/s, ${((updatesPerSec * updateBytes * 8) / 1e6).toFixed(0)} Mbps in`);
console.log(`location history:   ${((updatesPerSec * updateBytes * 86400) / 1e12).toFixed(1)} TB/day if every point is kept`);
console.log(`ride requests:      ${Math.round(ridesPeak).toLocaleString("en")}/s at peak`);
console.log(`live index:         ${((driversOnline * indexEntryBytes) / 1e6).toFixed(0)} MB, fits in one machine's RAM`);
console.log(`write:read ratio:   ${Math.round(updatesPerSec / ridesPeak)} location writes per ride request`);

// Geohash cell size: each character adds 5 bits, alternating longitude and latitude.
const lat = 43.65, kmPerDegLat = 111.32, kmPerDegLng = 111.32 * Math.cos((lat * Math.PI) / 180);
console.log("geohash length  cell size at Toronto's latitude");
for (const len of [4, 5, 6, 7]) {
  const bits = 5 * len, lngBits = Math.ceil(bits / 2), latBits = Math.floor(bits / 2);
  const w = (360 / 2 ** lngBits) * kmPerDegLng, h = (180 / 2 ** latBits) * kmPerDegLat;
  const fmt = (x) => (x >= 1 ? `${x.toFixed(1)} km` : `${Math.round(x * 1000)} m`);
  console.log(`${String(len).padStart(14)}  ${fmt(w)} wide × ${fmt(h)} tall`);
}

location updates:   375,000/s, 300 Mbps in
location history:   3.2 TB/day if every point is kept
ride requests:      1,042/s at peak
live index:         96 MB, fits in one machine's RAM
write:read ratio:   360 location writes per ride request
geohash length  cell size at Toronto's latitude
             4  28.3 km wide × 19.6 km tall
             5  3.5 km wide × 4.9 km tall
             6  885 m wide × 611 m tall
             7  111 m wide × 153 m tall

API

Driver app (one WebSocket per online driver)
  -> { type: "location", lat, lng, heading, speedKmh, ts }        every 4 s
  <- { type: "offer", offerId, pickup, etaSec, expiresInSec: 15 }
POST /v1/offers/{offerId}/accept       -> 200 { rideId }  | 409 { reason: "offer expired" }
POST /v1/offers/{offerId}/decline

Rider app
POST /v1/rides   Idempotency-Key: …   { pickup, dropoff, product: "standard" }
  -> 202 { rideId, status: "matching" }
GET  /v1/rides/{rideId}                -> { status, driver, driverPosition, etaSec }
WebSocket /v1/rides/{rideId}/live      <- driver position and status changes
GET  /v1/drivers/nearby?lat=&lng=      -> up to 20 approximate positions for the map

Locations come over a long-lived connection because 375,000 short HTTP requests a second would spend most of their cost on connection setup, and the same connection carries offers back to the driver (see scaling WebSockets). POST /v1/rides carries an idempotency key because a rider on a bad connection taps again, and two rides for one tap is a real bug (idempotency keys for APIs). Matching is asynchronous, so the request returns 202 and the rider watches the status.

Data model

Positions and status are kept separate on purpose. Positions are overwritten constantly and can be stale; status changes rarely and must be exact. A stale position means a slightly worse match; a stale status means two riders get one car.

High-level design

Talk through one ride. The driver app streams its position to a gateway that holds its WebSocket; the gateway forwards updates to the location service shard for that city, which updates its cell index, and to a log for everything that wants history. The rider requests a ride; the matching service asks the location service for available drivers near the pickup, ranks them (distance first, or better, estimated time to pickup), claims the best one in the driver state store with a compare-and-set, writes the ride, and sends the offer back through the driver's gateway. If the driver declines or the 15-second offer expires, the claim is released and the next candidate gets it.

Why not a database with an index on latitude and longitude? A B-tree on (lat, lng) answers "latitude between a and b" well, but not "and longitude between c and d" at the same time, and every one of 375,000 updates a second rewrites index pages. Spatial indexes (R-trees, PostGIS) answer the query well but are built for data that changes far less often. A grid of cells in memory makes both operations cheap: an update is a hash-map write (and a set move 6.7% of the time), and a search is 9 set lookups plus a sort of a few hundred candidates.

Options for the grid:

• Geohash cells in your own service, as in the model. Simple, and a cell id is a string, so it shards and caches easily.
• Redis GEO commands. GEOADD stores members in a sorted set whose score is a 52-bit geohash (latitude and longitude bits interleaved), and GEOSEARCH finds members within a radius or box. Redis's source (geo.c) searches the cell and its 8 neighbours at a precision chosen for the radius and then filters by distance, and the docs say that with ANY it returns as soon as enough matches are found, so they may not be the closest. A sorted set update is O(log N), fine at a few hundred thousand writes a second spread over shards.
• H3 hexagons. Uber built H3 for dispatch and pricing and open-sourced it (Uber engineering blog, 2018). Every hexagon's six neighbours are at the same distance from its centre, unlike squares, whose diagonal neighbours are farther than the side ones, which makes "rings" of cells and per-cell statistics like demand and surge cleaner.

Shard by geography. A city is a natural shard: rides almost never cross cities, and a city's traffic fits on a few machines. Big cities split further by cell prefix. A rider near a shard boundary needs a query to both shards, which the location service handles by mapping the 9 cells to their shards. Replicate each shard to a standby, but remember that losing it costs only seconds: the next updates rebuild it.

Updates arrive out of order sometimes (mobile networks retry). Keep the update's device timestamp and drop any update older than the stored one, otherwise a driver can jump backwards on the map.

Many matching servers run at once, and two riders standing on the same corner will both see the same nearest driver. Reading "driver is available" and then writing "driver is offered" is a race: both matchers read available, both write offered, and the driver gets two offers. The fix is the same as for any shared resource: make the claim a compare-and-set on a version.

// Driver state with a version number; an offer only goes out if the version hasn't moved since it was read.
const drivers = new Map([
  ["d1", { status: "available", version: 7, km: 0.4 }],
  ["d2", { status: "available", version: 3, km: 0.9 }],
  ["d3", { status: "on_trip", version: 12, km: 0.2 }],
]);

function compareAndSet(id, expectedVersion, next) {        // in Redis: a Lua script or WATCH/MULTI; in SQL: UPDATE … WHERE version = ?
  const d = drivers.get(id);
  if (d.version !== expectedVersion) return false;
  Object.assign(d, next, { version: d.version + 1 });
  return true;
}

function match(rideId, snapshot) {                         // snapshot = what this matcher read from the geo index
  const candidates = [...snapshot].filter(([, d]) => d.status === "available").sort((a, b) => a[1].km - b[1].km);
  for (const [id, seen] of candidates) {
    if (compareAndSet(id, seen.version, { status: "offered", ride: rideId })) return `${rideId} -> offer sent to ${id}`;
    console.log(`  ${rideId}: ${id} was taken between read and write, trying the next driver`);
  }
  return `${rideId} -> no driver, widen the search`;
}

// Two matchers read the same state at the same moment, then act one after the other.
const snapA = new Map([...drivers].map(([id, d]) => [id, { ...d }]));
const snapB = new Map([...drivers].map(([id, d]) => [id, { ...d }]));
console.log(match("ride-A", snapA));
console.log(match("ride-B", snapB));
console.log(Object.fromEntries([...drivers].map(([id, d]) => [id, `${d.status} v${d.version}${d.ride ? " " + d.ride : ""}`])));

ride-A -> offer sent to d1
  ride-B: d1 was taken between read and write, trying the next driver
ride-B -> offer sent to d2
{ d1: 'offered v8 ride-A', d2: 'offered v4 ride-B', d3: 'on_trip v12' }

The claim store is not the final word. The compare-and-set is atomic on the Redis primary, but Redis replicates asynchronously (its replication documentation says so, and adds that even WAIT doesn't turn it into a strongly consistent system), the same weakness the ticket-booking design below notes for Redis hold keys. If the primary fails right after d1 was claimed for ride-A, the promoted replica may still show d1 as available, and another matcher can offer him to ride-B. Two backstops make that harmless. First, an offer is only an offer: the driver's explicit accept (POST /v1/offers/{offerId}/accept) is what assigns the ride. Second, the accept writes the ride in the rides database under a rule of one active ride per driver, a partial unique index on rides(driver_id) for rides in accepted or in_progress, so a second accept fails with 409 and that rider is matched again. The fast store keeps double offers rare; the durable, transactional database makes a double assignment impossible.

Greedy "nearest free driver per request" is easy to explain and good enough for an interview. Mention the improvement: batch matching. Collect the requests that arrive in a short window (a second or two) and solve the assignment for all of them together, minimising total pickup time, so one rider doesn't take the only driver who was perfect for another. Rank by estimated time to pickup rather than straight-line distance: a driver 300 m away on the other side of a highway can be ten minutes away.

The gateway tier holds 1.5 M WebSockets; at tens of thousands of connections per server (a common rule of thumb; measure your own) that's dozens to hundreds of servers, behind a load balancer that keeps a driver on one gateway for the life of the connection. Each update is fanned out to two places with different needs: the geo index (latest position only, may drop updates under load) and the location log (every point, durable, consumed later). If the index falls behind, shed load by dropping stale updates, not by queueing them: a 20-second-old position is worthless when a fresh one arrives every 4 seconds (the idea from backpressure and load shedding).

During a trip the rider subscribes to their driver's position: the gateway (or a pub/sub channel per ride) pushes each update to the rider's connection. Before a request, the "cars near you" map doesn't need exact data: return a handful of approximate positions from the cells around the rider, cached for a few seconds per cell, which turns millions of map views into a small number of index reads.

The app can also adapt its reporting rate: every 4 seconds while available or on a trip, much less often when stationary or offline. That saves phone battery and cuts the write rate where it buys nothing.

Trade-offs and what to say

Requirements

Functional:

• Search for places near a location (the user's position or a point on the map), within a radius or "nearest N", with filters: category, open now, price level, minimum rating.
• Results are ranked by a mix of distance and quality, and paginated.
• View a place's details, photos and reviews.
• Business owners add and edit places; users write reviews. New places can take minutes to hours to appear in search.

Non-functional:

• Low latency: search p99 under about 200 ms end to end, so the index lookup itself must be a few milliseconds.
• Read-heavy and highly available: searching must keep working even if writes are paused.
• Eventual consistency is fine for place edits and new reviews; nobody is hurt if a new café shows up 10 minutes late.
• Scale: 200 M places, 100 M daily active users.

Estimates

// Assumptions for a Yelp-like "places near me" service.
const places = 200e6;            // businesses and points of interest worldwide
const dau = 100e6;
const searchesPerDau = 5;
const peakFactor = 3;
const placeUpdatesPerDay = 1e6;  // new places, edits, closures
const detailBytes = 2_000;       // name, address, hours, categories, rating summary
const geoEntryBytes = 24;        // id (8) + lat (8) + lng (8)
const replicas = 3;

const qps = (dau * searchesPerDau) / 86400;
console.log(`search QPS:        ${Math.round(qps).toLocaleString("en")} average, ${Math.round(qps * peakFactor).toLocaleString("en")} peak`);
console.log(`write rate:        ${(placeUpdatesPerDay / 86400).toFixed(0)} updates/s, read:write ≈ ${Math.round((qps * peakFactor) / (placeUpdatesPerDay / 86400))}:1 at peak`);
console.log(`geo index:         ${((places * geoEntryBytes) / 1e9).toFixed(1)} GB raw, fits in RAM on every replica`);
console.log(`place details:     ${((places * detailBytes) / 1e9).toFixed(0)} GB, ${((places * detailBytes * replicas) / 1e12).toFixed(1)} TB with ${replicas} copies`);
const perNode = 5_000;           // searches/s one index server handles (rule of thumb, measure it)
console.log(`index servers:     ${Math.ceil((qps * peakFactor) / perNode)} at ${perNode.toLocaleString("en")} QPS each, plus spares`);

search QPS:        5,787 average, 17,361 peak
write rate:        12 updates/s, read:write ≈ 1500:1 at peak
geo index:         4.8 GB raw, fits in RAM on every replica
place details:     400 GB, 1.2 TB with 3 copies
index servers:     4 at 5,000 QPS each, plus spares

API

GET /v1/places/search?lat=43.6532&lng=-79.3832&radius=2000&category=coffee&openNow=true&limit=20&cursor=…
  -> 200 { results: [ { id, name, lat, lng, distanceM, rating, reviewCount, priceLevel, openNow } ], nextCursor }
GET  /v1/places/{id}                    -> 200 { …details, hours, photos }
GET  /v1/places/{id}/reviews?cursor=…
POST /v1/places                         (owner)  { name, lat, lng, category, hours, … } -> 201 { id }
PATCH /v1/places/{id}                   (owner)
POST /v1/places/{id}/reviews            { stars, text }

Pagination uses a cursor rather than an offset (pagination at the API level): the cursor can encode the query point, the filters and the score of the last result returned, so the next page continues from there. Coordinates in the query string are fine (they aren't secret), but round them to about 4 decimal places (11 m) so that nearby users' identical searches share a cache key.

Data model

Keep the filter fields inside the index so a query can filter candidates without a database round trip per place. The index then answers "ids of open coffee shops near here, best first", and one batched read fetches the 20 detail records.

High-level design

The search service is stateless apart from its copy of the index, which it loads from the latest snapshot at start-up and then keeps current by applying deltas from the change stream. A query goes: parse the point and filters → walk the index for candidate ids (with filters applied inside the index) → rank → fetch the top 20's details from the cache (misses go to a read replica) → return. Adding capacity is adding search servers behind the load balancer.

For this interview, a strong answer is: geohash in the database as the source of truth, an in-memory index on each search server for speed. The geohash6 column lets anything (batch jobs, a fallback path) answer "places in these 9 cells" with an ordinary index: WHERE geohash6 IN (?, ?, …). The in-memory index can be a quadtree if density varies as wildly as it does between a city centre and the countryside, which it does; with only 12 writes a second, rebuilding the tree in the background every few minutes and swapping it in is simpler than updating it in place.

Watch the edge cases. Geohash cells are not square everywhere: east–west they shrink as latitude grows, so a fixed length is coarser in Singapore than in Oslo. Neighbouring cells can have completely different prefixes (cells on either side of the equator or the prime meridian share no prefix), so never find neighbours by string prefix; compute them, as the models in this chapter do. A radius search must still filter by real distance, because 9 cells cover a rectangle, not a circle.

Distance alone gives you the chain café next door; raw star rating gives you a place with one 5-star review. Search is two phases: retrieve a few hundred candidates from the index (nearest first, filters applied), then rank them with a score that mixes quality and distance. A small, explainable version:

// Candidates from the geo index (already within 2 km), then ranked. Ratings are 1–5 stars.
const candidates = [
  { name: "Brand-new café", km: 0.15, stars: 5.0, reviews: 2 },
  { name: "Neighbourhood favourite", km: 0.6, stars: 4.6, reviews: 900 },
  { name: "Chain coffee", km: 0.1, stars: 3.4, reviews: 1500 },
  { name: "Hidden gem", km: 1.4, stars: 4.8, reviews: 160 },
];

const PRIOR_STARS = 3.8, PRIOR_WEIGHT = 25;          // pretend every place starts with 25 average reviews
const bayes = (p) => (p.stars * p.reviews + PRIOR_STARS * PRIOR_WEIGHT) / (p.reviews + PRIOR_WEIGHT);
const closeness = (p) => Math.exp(-p.km / 1.5);     // 1.0 at the door, 0.51 at 1 km
const score = (p) => 0.6 * ((bayes(p) - 1) / 4) + 0.4 * closeness(p); // stars mapped to 0–1

const by = (f) => [...candidates].sort((a, b) => f(b) - f(a)).map((p) => p.name).join(" > ");
console.log("by raw stars:  ", by((p) => p.stars));
console.log("by distance:   ", by((p) => -p.km));
console.log("by score:      ", by(score));
for (const p of candidates)
  console.log(`  ${p.name.padEnd(24)} adjusted ${bayes(p).toFixed(2)}  closeness ${closeness(p).toFixed(2)}  score ${score(p).toFixed(3)}`);

by raw stars:   Brand-new café > Hidden gem > Neighbourhood favourite > Chain coffee
by distance:    Chain coffee > Brand-new café > Neighbourhood favourite > Hidden gem
by score:       Neighbourhood favourite > Brand-new café > Chain coffee > Hidden gem
  Brand-new café           adjusted 3.89  closeness 0.90  score 0.795
  Neighbourhood favourite  adjusted 4.58  closeness 0.67  score 0.805
  Chain coffee             adjusted 3.41  closeness 0.94  score 0.735
  Hidden gem               adjusted 4.66  closeness 0.39  score 0.707

Updates are rare, so freshness is easy: the change stream (change data capture from the primary) delivers each edit to the index builder within seconds, and search servers apply it as a delta. A nightly full rebuild from a snapshot catches anything a delta missed. Reviews update rating_avg asynchronously; a few minutes' lag is invisible.

Caching works well because queries cluster: many people search "coffee" around the same downtown blocks. Cache full responses keyed by (geohash6 of the rounded point, filters, page) with a TTL of a minute or two; a user standing anywhere in the cell gets the same cached first page, at the cost of results ranked from the cell's centre rather than their exact spot (re-sort the cached candidates by exact distance on the server if that matters). Place details are cached by id and invalidated on edit, the cache-aside pattern from caching strategies.

If the index outgrew one machine (for example with many more fields per place), shard it by region, and route each query to the shard owning the query point's cells; queries near a boundary go to two shards and the results are merged.

Trade-offs and what to say