CSE Roadmap

Common tier · about 4 hours · 7 parts

Part 2 of 7 · 2 min read

Scope and numbers

A moving target, many watchers.

Think of a group of friends at a festival, each holding a radio. Everyone shouts their position every half minute. Each person only wants to hear the friends who are close.

Questions and the answers assumed here (from the book's sample talk).

  1. What is "nearby"? Within 5 miles in a straight line.
  2. How big is the app? 1 billion users, of which 10 per cent use this feature.
  3. Is history kept? Yes, location history is stored, since it is useful later (for example for machine learning).
  4. When does a friend vanish from the list? After 10 minutes of silence.
  5. Privacy law? Out of scope here, to keep the case small.

Requirements.

  • R1. A user sees nearby friends. Each entry shows a distance and the time of the last update.
  • R2. The list updates a few times a minute.
  • R3. Low delay for updates.
  • R4. Reliable enough. Losing an occasional point is fine.
  • R5. Eventual consistency. A delay of a few seconds is fine.

Numbers (from the book).

  • 100 million daily users of the feature. Concurrent users are 10 per cent: 10 million.
  • Each user sends a location every 30 seconds, since walking speed is slow.
  • Updates: 10,000,000 / 30 = about 334,000 per second.
  • Each user has 400 friends, and about 10 per cent of them are online and nearby. So each update goes to 400 × 10% = 40 friends.
  • Forwarded messages: 334,000 × 40 = about 13 to 14 million per second.

The key finding: the work is not in storing locations, but in pushing 14 million small messages a second.

Fan-out

Fan-out is the number of receivers that one message must reach.

Example: a user with 40 nearby friends has a fan-out of 40 for each location update.

Check yourself: 1. Why is the update interval 30 seconds? 2. How many updates per second reach the servers? 3. How many messages per second are forwarded?