Hands-on design challenge

Challenge 13: Social graph queries

The situation

Users look up their friends of friends, and the friend graph is too large to keep on a few shards. People are placed on shards by a hash of their ID, so a person's friends land on shards at random, and a read that cannot tell which shard holds what it needs asks every shard and waits for the slowest. A person's friends and their friends are read again and again, by that person and by everyone near them in the graph, so most reads repeat one already made.

Traffic

10,000 requests a second.

OperationShareSteps
Read90%Read data
Write10%Write data
  • Read90%Read data
  • Write10%Write data

Data

A cache answers 95% of the reads that reach it.

What you are proving

A read that asks every shard loads every shard, so adding shards does not help it: the cure is to make few reads need them all.

Rules

  • A CDN does not help here.Each answer depends on who is asking, their friends and their friends' friends, so no copy a CDN keeps near users could answer another user.
  • The friend graph stays spread over the shards the targets ask for.It is too large for fewer, so a design cannot escape the slowest shard by merging shards.

Builds on

  • Serve all 10,000 requests a second
  • At least 99.99% available, with no single point of failure
  • At most 4,000 USD a month
  • Data held in at least 16 partitions
  • Any tier loses one instance: nothing dropped, no tier over 80% busy