Nearby Friends

Design a "Nearby Friends" feature: opt-in mobile users see geographically nearby friends. Unlike the Proximity Service (static business locations), friend locations change frequently: dynamic data.

Figure 1: Facebook's nearby friends

Step 1 of 4: Understand the problem and establish design scope #

Goal: lock in requirements and the load numbers.

Functional requirements #

Must have:

1. Users see nearby friends with distance and last-updated timestamp
2. "Nearby" = within 5 miles (configurable). Straight-line distance
3. Friend lists update every few seconds
4. Inactive friends (no update >10 min) disappear from the list
5. Store location history (for ML purposes)
6. Privacy laws (GDPR/CCPA) out of scope for now

Non-functional:

1. Low latency for location updates
2. Reliable overall, but occasional data point loss acceptable
3. Eventual consistency: a few seconds delay between replicas is fine

Back-of-the-envelope estimation:

1. 1B total users; 10% use nearby friends → 100M DAU
2. Concurrent users: 10% of DAU → 10M
3. Users report locations every 30 seconds (walking speed ~3-4 mph, 30s movement negligible)
4. Average user has 400 friends (all using the feature)
5. Display 20 nearby friends per page
6. Location update QPS = 10M / 30 = ~334,000
7. If ~10% of friends are online and nearby: each update forwarded to ~40 friends
8. Total forwarded updates: 334K × 40 = ~13M/sec

Step 2 of 4: Propose high-level design and get buy-in #

Goal: reject P2P, agree on the shared backend + pub/sub routing.

High-level design #

P2P approach (persistent connections to every friend) is impractical for mobile (flaky connections, power constraints). Shared backend approach:

Backend responsibilities:

1. Receive location updates from all active users
2. Find active friends who should receive each update
3. Forward only if distance ≤ threshold

Figure 4: High-level design

Components:

1. Load balancer: fronts REST API + WebSocket servers. Distributes traffic
2. RESTful API servers: stateless HTTP. Handles friends management, user profiles, etc.
3. WebSocket servers: stateful. Each client maintains one persistent connection. Handles real-time location updates and client initialization (seeds the initial nearby friends list)
4. Redis location cache: latest location per active user. TTL on each entry; update refreshes TTL. Expired = user inactive
5. User database: user profiles + friendship data. Relational or NoSQL
6. Location history database: historical locations. Cassandra (write-heavy, horizontally scalable) or sharded relational DB by user_id
7. Redis pub/sub server: lightweight message bus. Each user has a channel; online friends subscribe. Location updates published to the user's channel → broadcast to all subscribers → each subscriber's WebSocket handler recomputes distance → forwards if within radius

Figure 6: Redis Pub/Sub

Periodic location update flow #

Figure 7: Periodic location update

1. Mobile client sends location update via persistent WebSocket connection
2. Load balancer forwards to the WebSocket server for that client
3. WebSocket server saves to the location history database
4. WebSocket server updates the location cache (refreshes TTL) and stores in the connection handler variable
5. WebSocket server publishes to the user's Redis pub/sub channel (steps 3–5 in parallel)
6. Redis pub/sub broadcasts to all subscribers (online friends' WebSocket handlers)
7. Each subscriber's WebSocket handler computes the distance between the updating user and the subscriber
8. If distance ≤ search radius → forward to subscriber's client. Otherwise drop

Figure 8. Example: User 1's friends = {2,3,4}. Update published to User 1's channel → broadcast to handlers for users 2,3,4 → distance check → forward.

API design #

WebSocket APIs:

1. Periodic location update: client sends (lat, lng, timestamp). No response
2. Client receives location updates: friend's (lat, lng, timestamp)
3. WebSocket initialization: client sends (lat, lng, timestamp); receives all nearby friends' locations
4. Subscribe to new friend: server sends friend ID; receives friend's (lat, lng, timestamp)
5. Unsubscribe friend: server sends friend ID. No response

HTTP: friends CRUD, user profiles: standard.

Data model #

Redis location cache:

Why Redis? Only need the current location (one per user); TTL auto-purges inactive users; no durability needed (cache can be rebuilt from new updates). Super-fast reads/writes.

Location history database (Cassandra):

Handles heavy-write workload; horizontally scalable. Alternative: relational DB sharded by user_id.

Step 3 of 4: Design deep dive #

Goal: scale each component: especially the pub/sub routing layer.

Scaling each component #

API servers: stateless → standard auto-scaling by CPU/load/I/O.

WebSocket servers: stateful but auto-scalable. Before removing a node, mark it "draining": no new connections; wait for existing connections to close.

Client initialization (on WebSocket connect):

1. Update the user's location in cache
2. Save location in the connection handler variable
3. Load all friends from the user DB
4. Batch-fetch friends' locations from the location cache (TTL = inactivity timeout, so inactive friends won't be in cache)
5. For each located friend, compute distance; if within radius, return profile + location + timestamp
6. Subscribe to each friend's Redis pub/sub channel (all friends, active or inactive: inactive channels consume tiny memory, zero CPU)
7. Send the user's location to their own pub/sub channel

User database: shard by user_id for horizontal scaling. At scale, likely managed by a dedicated team via internal API.

Location cache (Redis):

1. 10M active users peak × ~100 bytes/location → fits a single Redis server with GBs of memory
2. But 334K writes/sec is likely too high for one server → shard by user_id across multiple Redis instances
3. Each shard replicated to a standby for HA (promote on primary failure)

Redis pub/sub scaling #

Each of 100M users gets a channel. Subscribers ≈ active friends using the feature (avg 100).

Memory: 100M channels × 100 subscribers × 20 bytes ≈ 200 GB → ~2 Redis servers (modern 100GB servers).

CPU: 13M subscriber pushes/sec. Conservative estimate: ~100K pushes/sec/server → ~130 Redis pub/sub servers needed. CPU is the bottleneck, not memory.

Distributed Redis pub/sub cluster #

Shard channels across servers via consistent hashing on the publisher's user_id. Use service discovery (etcd/ZooKeeper) storing a hash ring:

Key: /config/pub_sub_ring
Value: ["p_1", "p_2", "p_3", "p_4"]

Figure 9: Consistent hashing

Publishing flow:

1. WebSocket server consults the hash ring → determines the target Redis pub/sub server
2. Publishes to that server

Subscribing: same mechanism.

Scaling considerations:

1. Messages are stateless (not persisted; dropped if no subscribers). But subscriber lists ARE stateful
2. Moving channels (resizing the cluster) → mass resubscription events → potential missed updates. Resize during low-traffic hours. Over-provision for headroom
3. Replacing a single failed server causes fewer channel moves than resizing

Node replacement:

1. On-call updates the hash ring to replace the dead node with a standby
2. WebSocket servers notified → each handler checks subscribed channels → re-subscribes if the channel moved

Adding/removing friends #

Register callbacks in the mobile app. On friend add → WebSocket subscribes to the new friend's channel + returns the friend's latest location. On friend remove → unsubscribe. Same for opt-in/opt-out changes.

Users with many friends #

Hard cap on friends (e.g. Facebook's 5,000). Subscribers scattered across the WebSocket cluster → no hotspots. "Whale" users spread across pub/sub servers.

Nearby random person (extra credit) #

Add pub/sub channels by geohash. Users in the same geohash subscribe to the same channel. To handle border cases, subscribe to your own geohash + 8 surrounding grids (9 total).

Alternative: Erlang #

Erlang/Elixir on the BEAM VM: lightweight processes (~300 bytes each, millions per server). Model each active user as an Erlang process with native pub/sub. Eliminates the Redis pub/sub cluster entirely. Operational tools are excellent. Downside: niche skill, hard to hire.

Step 4 of 4: Wrap up #

What we designed:

1. WebSocket (real-time comm), Redis (fast location read/write), Redis pub/sub (routing layer)
2. Scaling: consistent hashing for pub/sub, sharding for location cache and user DB
3. Addressed friend add/remove, whale users, and the nearby-random-person extension
4. Erlang as an alternative routing layer