Nearby Friends

The problem

"Design Nearby Friends." People who turn the feature on see which of their friends are close by right now, say within 5 km, and how far away each one is, updated live. Both sides must have it on: you see the friends who share, and they see you.

This practice problem reuses the pattern of Design Uber: phones send their position over an open WebSocket held by a gateway, and only the latest position is kept, in memory. Four things are new: everyone both sends and watches, only friends count, a person's location must stay private, and phones share all day on battery. Park chat and suggestions of strangers to meet.

The numbers

From the interviewer: 100 million users, of whom 10 million share their location at busy hours, each phone sending it every 30 seconds. Each user has about 400 friends; like everyone else, about 1 in 10 of them is sharing at a time, so about 40.

what           working                          result
updates in     10 million ÷ 30 s                about 330,000 a second
messages out   330,000 × 40 sharing friends     about 13 million a second
per phone      40 ÷ 30 s                        about 1.3 a second
latest kept    10 million × 100 bytes           about 1 GB

Two common slips: 130 million a second sends every update to all 400 friends, though only the 40 with sharing on are watching, and 330,000 forgets the copies. The writes are Uber-sized; the fan-out makes the messages out 40 times more. Say one gateway server holds about 100,000 WebSockets: 10 million phones need about 100 of them, each sending about 130,000 messages a second.

Friends, not cells: a channel per user

In Uber, a rider's search read the map cells around her and checked every driver in them: cells answer "who is near this spot?". Here the question is "where are my friends?". To be sure of every friend within 5 km, a search would need 11 × 11 = 121 cells of 1 km, full of strangers, for each of 10 million phones every 30 seconds.

Instead, give every user a channel in a pub/sub system. Ben's gateway server saves each of his updates in the location store and publishes it once on Ben's channel. When Ana connects, her gateway server reads her friends list and subscribes to her friends' channels, so their updates are copied to her server, and nobody else's: the channel per user from Online Presence.

Asking for every friend's position every 30 seconds costs 10 million × 400 ÷ 30 ≈ 130 million reads a second, ten times the messages. One read stays: when Ana opens the app, her server reads her friends' latest positions once, so her list fills at once.

Within 5 km: a check on every update

Ana's gateway server holds her latest position, works out the distance to each sharing friend's update, and passes it on only within 5 km. In the lesson:

friend   distance now   shown?
Ben      1.2 km         yes
Dee      3.4 km         yes
Fay      4.9 km         yes
Cy       7.5 km         no
Eli      42.4 km        no
Gus      not sharing    no, he sends nothing

Everyone moves, so the check runs on every update: if Cy drives toward Ana, his first update within 5 km puts him on her list. Checking once when Ana opens the app would miss him. Filtering on the phone would send all 40 friends' updates down to it, and hand Eli's position, 42.4 km away, to a phone that shouldn't have it.

Privacy: opt-in, rounded, no history

• Opt-in: sharing is off until each person turns it on, and turning it off stops the updates at once.
• Rounded: the phone rounds its position to three decimal places, about 100 m or less: enough for "1.2 km away", not for which building.
• No history: only the latest position is kept, with a TTL, as in Online Presence. It must outlast a still phone's 5-minute gap: say 10 minutes, two missed updates. Nothing else keeps positions, not even the logs.

↑ {"type": "position", "lat": 48.857, "lng": 2.352}                  every 30 s, rounded
↓ {"type": "friend", "id": "ben", "lat": 48.866, "lng": 2.362, "km": 1.2}

Who shares with whom lives in the users database next to the friends list; the gateway reads it when someone connects.

Battery: send less when still

Each send wakes the GPS and the radio, and that drains a battery, not the few bytes. So the app sends every 30 seconds while the phone moves and every 5 minutes when its motion sensor says it's still. In Ana's hour, 20 minutes walking and 40 in a café, that's 40 + 8 = 48 updates instead of 120, and the 72 it skips would all have said the same place. Every 5 minutes all the time fails the other way: a friend driving at 50 km/h moves about 4 km between updates.

Same pattern as Uber

The gateway holding a WebSocket per phone and the latest position per person in an in-memory store, overwritten on each update, carry over. What changes is who reads: everyone watches a fixed set of people, so positions travel by subscription, and the store is split by user id rather than by area, since nobody searches by place. Say one in-memory server takes about 100,000 writes a second: 330,000 need at least 4.

Summary

• Scope: friends within 5 km, live; sharing only by choice.
• Data: the latest position per person, rounded, in memory with a TTL; friends and settings in the users database.
• API: a WebSocket per app: your position up, friends' positions down.
• Numbers: about 330,000 updates in and 13 million messages out a second.
• Scale: a channel per user; gateway servers subscribe to friends' channels.
• Within 5 km: checked on the server, on every update.
• Privacy: opt-in, about 100 m, a TTL, nothing in the logs.
• Battery: every 30 s while moving, every 5 minutes when still.