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.
| Operation | Share | Steps |
|---|---|---|
| Read | 90% | Read data |
| Write | 10% | 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
- 1.2 Response time versus throughput
- 2.2 Availability patterns and failover
- 2.3 Availability in numbers
- 4.3 Horizontal sharding and consistent hashing
- 6.1 Caching tiers and cache placement
- 10.4 Real-time search and scatter-gather
- 13.1 Requirements, estimates and the graph model
- 13.3 Graph partitioning and the TAO cache
Targets
- 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