Nearby friends

01 · CONTEXT

Locations that never stop changing

The exercise asks for the backend of an app where people share their own location and discover which friends are nearby. Unlike the proximity service case, here locations change all the time, while business addresses barely change.

Instead of querying static points, the system needs to distribute a stream of updates to those who are interested in them.

On the functional side, each friend appears with distance and the time of the location update, and the list is refreshed every few seconds. "Nearby" is a configurable five-mile radius, and location history should be stored, for example for machine learning.

On the non-functional side, low latency matters for receiving updates without much delay. Occasionally losing a data point is acceptable, as long as the system is generally available, and location storage does not need strong consistency.

02 · SCALE

The math that drives the design

The source's assumptions: location is updated every 30 seconds, because people on foot move slowly; one hundred million users use the feature per day, with 10% concurrent, that is, ten million; and each user has on average 400 friends, all using the feature.

Dividing the ten million concurrent users by the 30-second interval gives about 334 thousand location updates per second. With 400 friends and 10% of them online, each received update generates about 40 updates to forward.

03 · ARCHITECTURE

Shared server and one channel per user

The shared server receives the locations of all active users, finds for each update the active users who should receive it, and forwards it, without relaying when the distance between friends exceeds the configured limit.

Os WebSocket servers are stateful and forward the updates to clients. The location cache cache stores the most recent location of each active user, and each entry has an expiration time: when it expires, the user is no longer active and their data leaves the cache. Pub/sub is a lightweight bus with one channel per user. REST servers handle auxiliary tasks such as friendships and profiles.

The location history is not necessarily used by the feature itself, and a database like Cassandra can store it because it is optimized for heavy write loads.

1. The phone sends the location to the load balancer, which forwards it to the client's persistent connection on the WebSocket server.

2. The server writes the location to the history and updates the location cache.

3. The server publishes the location to the user's channel via Pub/sub.

4. Pub/sub broadcasts the update to all subscribers of the channel, that is, to the servers responsible for the friends.

5. Each subscribing server works out who the update should go to and sends it to the friend's phone.

04 · FAN-OUT

Who subscribes to what

On startup, the server fetches the user's friends, subscribes to their channels on Pub/sub, reads their positions from the cache and relays them to the client. In steady state, WebSocket servers subscribe to channels for the users connected to them, and every publish on someone's channel reaches the servers responsible for that person's friends.

1. The sender's server publishes the position to the user's channel.

2. The channel broadcasts the same update to all servers subscribed to it.

3. Each subscribing server works out who the update should go to.

4. Where the friend is within the distance limit, the position is relayed to their phone.

5. Where the distance exceeds the configured limit, the server does not relay the position.

In Pub/sub, the publisher does not know the subscribers: messages are categorized into channels, and subscribers receive them in the order they were published. A channel that is created but unused consumes no memory, which makes it possible to pre-allocate channels for all of the feature's users.

05 · GUARANTEES

What Pub/sub promises and what it does not

The Redis documentation says that Pub/sub delivers at most once, and that if the subscriber cannot handle the message, it is lost forever. On the requirements side, occasionally losing a data point is acceptable.

06 · BUS

Spreading the channels across many servers

By the source's estimate, about 14 million updates per second need to be pushed. Assuming 100 thousand pushes per second per server, at least 140 Redis servers are needed, and therefore a distributed cluster because of the CPU load.

To sustain the cluster, the source uses a service discovery component, such as ZooKeeper or etcd, to know which servers are alive. The WebSocket servers use the data stored there to find where each channel lives, and the hash ring can be kept in memory on each of them.

1. The WebSocket server needs to know where the channel lives; it consults the hash ring coming from service discovery, which it can keep in memory.

2. The user's channel lands on the node indicated by the ring.

3. The server publishes to and subscribes to the channel directly on that node.

4. When a node is added, consistent hashing minimizes the number of channels that move.

5. The WebSocket servers redo the subscriptions for the moved channels, and some updates may be lost during that interval.

The Redis documentation also describes sharded Pub/sub, which helps scale Pub/sub in cluster mode and limits traffic on the cluster bus compared with global Pub/sub, where every message goes to all nodes.

The source also mentions Erlang as an alternative to Redis, which would allow creating millions of small processes that communicate with each other, at the cost of being a niche language in which it can be hard to hire experienced people.

07 · EDGES

Edge cases

For users with many friends, the source suggests capping the number of friends, for example with a ceiling of five thousand. The server of such a user may carry more load, but with enough servers it is fine.

For the variation in which random people nearby appear, a set of Pub/sub channels is defined per geohash, and it is possible to subscribe to several geohashes to cover people who are close but in a neighboring geohash.

When removing a server, mark the server as draining on the load balancer to stop sending connections to it.