System Design: [Social graph store name]

Reference design for a social graph store and cache: typed objects (people, posts, pages, comments) and typed associations between them (follows, likes, authored, tagged), served at very high read rates through leader and follower cache tiers on top of a sharded relational store. It covers the object and association model, read-heavy graph queries, read-after-write consistency across tiers and regions, hot vertices, inverse edges and sharding. It follows the structure of the System Design Document template, adds a 45-minute interview path, and is pre-filled with a worked design to adapt. Replace every [bracketed] value and every row marked Example; numbers marked Example are assumptions to recompute.

Document control

Approvals

Revision history

Contents

1. Overview
2. Requirements
3. Capacity estimation
4. API design
5. Data model
6. High-level design
7. Detailed design
8. Scalability and performance
9. Reliability, security and operations
10. Trade-offs and alternatives
11. Delivery plan and risks
12. Appendices

1. Overview

1.1 Problem statement

[Example: Product teams read the social graph through a generic look-aside cache in front of sharded relational databases. Each team writes its own cache keys and invalidation code, so the same edge is cached under several keys, stale reads appear after writes (a user unfollows and still sees the account in their list), and a viral post's like list overloads one database shard. Page loads issue 300 to 600 graph reads each, and the cache miss storm after a deploy took the profile page down for 18 minutes last quarter.]

1.2 Proposed solution

[Example: A dedicated graph service exposes two primitives, objects and associations, with a small fixed query API. Data is stored in a sharded relational database, one logical shard per object id range, with each association stored on the shard of its source object. Reads go to a follower cache tier in the caller's region; misses and all writes go to a leader cache tier that owns each shard and is the only component that talks to the database. Leaders keep caches consistent by sending invalidations to followers after each write. Association lists are cached as time-ordered lists with a count, so "latest 50 likes" and "how many likes" are served from memory. Hot objects are replicated across follower servers and cached briefly in clients.]

1.3 Decisions requested from reviewers

1.4 45-minute interview path

Lead with the read-to-write ratio: it justifies the two-tier cache before anyone asks.

2. Requirements

2.1 Core functional requirements

2.2 Non-functional requirements

2.3 Below the line (out of scope)

• [Example: multi-hop graph traversal and graph analytics such as friends of friends at depth 3 (served by an offline graph engine)]
• [Example: ranking of feeds and recommendations (consumers of this store, see News Feed System Design (system-design/design-news-feed))]
• [Example: full-text search over object fields]
• [Example: large binary content such as photos (stored in a blob store; the graph holds references)]
• [Example: cross-object transactions beyond one association and its inverse]
• [Item deferred, with the release that will take it]

3. Capacity estimation

3.1 Assumptions

3.2 Storage

• Objects: 50 billion x 500 B = 25 TB.
• Associations: 1 trillion x 100 B = 100 TB.
• Total about 125 TB of logical data. At 1 TB of disk per database host filled to 50% (0.5 TB of data each), that is 125 / 0.5 = 250 database primaries. Consequence: the store is sharded from day one, and the shard map must allow moving data without changing ids (7.5).

3.3 Read path

• Per region: 20 million / 4 = 5 million reads/s.
• Follower tier at 50% target utilisation: 5 million / (200 000 x 0.5) = 50 servers per region. Memory: 50 x 256 GB = 12.8 TB per region, against a hot set of 125 TB x 5% = 6.25 TB. Consequence: one follower tier per region holds the hot set twice over, so the hit rate is limited by churn, not memory.
• With a 96% follower hit rate, misses are 5 million x 0.04 = 200 000/s per region to the leaders, 800 000/s in total. With a 90% leader hit rate, 80 000 reads/s reach the databases, about 320 per primary. Consequence: the database is sized for writes and cold reads, not for the read load; a cold cache would send 20 million reads/s to 250 hosts and must never happen all at once (9.1, warm-up).

3.4 Write path

• 100 000 writes/s; about 60% are association adds or deletes on types that have an inverse, so rows written are 100 000 x (1 + 0.6) = 160 000/s, about 640 per primary. Consequence: write load is modest per shard; the hard part is ordering and invalidating caches, not throughput.
• Each write produces one invalidation per follower tier holding the key: 4 regions x 1 tier = 4 messages, so 640 000 invalidations/s globally. Consequence: invalidations are batched per destination and carried on the replication stream to follower regions (7.2).

3.5 Hot vertices

• A celebrity post can draw 1 million reads/s on its object and like count. One follower server handles 200 000 ops/s. Consequence: hot keys must be replicated across several follower servers and cached briefly in the client (7.3); sharding alone cannot fix a single hot key.

3.6 Summary

4. API design

4.1 Operations

The graph service is called over an internal RPC protocol; operations are grouped by primitive.

4.2 Request and response examples

An add of a like, then the first page of the post's inverse list. Ids are 64-bit integers with the shard id embedded (7.5).

{"op": "addEdge", "src": 4611686018427387905, "type": "likes", "dst": 5764607523034234881, "time": 1792640000, "data": {"via": "feed"}}

{"op": "rangeEdges", "src": 5764607523034234881, "type": "liked_by", "offset": 0, "limit": 3,
 "result": {"count": 48211, "edges": [{"dst": 4611686018427387905, "time": 1792640000}, {"dst": 4611686018427390117, "time": 1792639990}, {"dst": 4611686018427401002, "time": 1792639975}]}}

4.3 Errors, limits and versioning

5. Data model

5.1 Entities

Two primitives carry all product data; counts and type rules support them.

5.2 Storage choices

5.3 Access patterns

The last column is why inverse edges exist: without them, "who follows B" would be a scatter-gather across every shard.

6. High-level design

7. Detailed design

7.1 Cache entries and the read path

Objects are cached by id. Association lists are cached per (src, atype) as the newest N entries (Example: N = 6 000) plus the count. A range query is answered from cache when the requested window is inside the cached prefix; an older window goes to the database. Because the cache understands the data model, a new like updates the cached list and count in place instead of deleting them, which avoids a miss storm on every write.

7.2 Deep dive 1: read-after-write across tiers and regions

Problem. Follower caches are updated asynchronously, so a user who unfollows an account can read the old list from a different follower or from a follower region before the invalidation arrives.

Choice. B plus C as the default, E for a short list of critical reads (privacy settings, blocks).

Reason. Users notice staleness in their own actions, not in others'. Writing through to the follower that took the write, and keeping a user's session on that follower tier, gives read-your-writes for the cost of routing. Privacy decisions cannot rely on eventual consistency, so they pay the cross-region read. In follower regions, the write is forwarded to the primary region's leader; the local follower applies the result once the primary acknowledges, and the replication stream carries invalidations for everyone else in commit order, so caches are never refilled from a replica that has not yet applied the write.

7.3 Deep dive 2: hot vertices

Problem. A celebrity object or a viral post concentrates reads on one cache key, and a celebrity's follower list can hold tens of millions of edges.

Choice. B and C for hot objects, detected automatically when a key exceeds Example: 50 000 reads/s on one server; D and E for high-degree vertices.

Reason. With K replicas and a client hit rate h, per-server load falls to (1 - h) / K of the original (Example: K = 10, h = 0.5 turns 1 million reads/s into 50 000 per server), while the extra staleness is within the 2 s promise (NFR-04). No viewer needs the exact like count of a post with 40 million likes.

7.4 Deep dive 3: inverse edges

Problem. follows(A, B) lives on A's shard and followed_by(B, A) on B's shard, so one logical write touches two shards.

Choice. B, with a background repair job that scans recent forward edges and fixes missing inverses, and C as the recovery path after outages.

Reason. A dangling edge for a few seconds is acceptable for social relationships; a cross-shard lock on a celebrity's shard is not. The repair job turns rare crashes into short-lived inconsistencies with a measured upper bound.

7.5 Deep dive 4: sharding and ids

Problem. Every request must find the right shard without a lookup service on the hot path, and shards must be movable as data grows.

Choice. C. Example: 16 384 logical shards mapped to 250 hosts through a versioned map pushed to all servers.

Reason. The id carries its shard forever, so caches, logs and clients can route without a lookup. New objects can be placed on the shard of a related object (a comment on its post's shard) to keep associations local. Moving a logical shard is a copy, a short write freeze for that shard, and a map version bump.

How real systems do it (paraphrased from Bronson et al., "TAO: Facebook's Distributed Data Store for the Social Graph", USENIX ATC 2013; inspiration only). The paper describes a graph-aware cache that replaced hand-written look-aside caching. Data is modelled as typed objects and typed associations; association lists are kept newest first with a count, and the read API is a few list, count and point queries. Caching servers are arranged as follower tiers that clients talk to and a leader tier that talks to the database, with leaders sending invalidations or refills to followers. In secondary regions, writes are forwarded to the region that holds the shard's primary database, and the database replication stream carries cache invalidations. Object ids embed the shard id, and inverse associations are written as separate operations, with the paper noting the consistency trade-off this implies. The system favours availability and per-tier read-after-write over global strong consistency. Check the paper for the exact mechanisms and figures.

7.6 Privacy checks on reads

Privacy filtering (blocked users, audience of a post) is applied by the calling application layer on top of graph reads, using the critical-read path from 7.2 for block lists. The store never returns edges of deleted or banned objects: deletes set a tombstone that caches respect immediately.

8. Scalability and performance

Latency budget for a cached read (target p99 5 ms):

9. Reliability, security and operations

9.1 Failure modes

9.2 Security and privacy

9.3 Observability

9.4 Cost estimate

10. Trade-offs and alternatives

10.1 Decisions

10.2 Alternatives considered

• Native graph database. Good for traversals, but this workload is one-hop lists and counts at very high rates; the operational risk was judged higher than its benefit. Revisit if multi-hop queries move online.
• Wide-column store for associations. A strong option for append-heavy edge lists; rejected here because counts and inverse maintenance would need the same leader logic and the team runs the relational stack already. See Distributed Key-Value Store Design (system-design/design-distributed-kv-store).

11. Delivery plan and risks

11.1 Milestones

11.2 Rollout and rollback

[Example: Migrate one association type at a time behind a flag. Dual-read for 14 days and compare; rollback switches the type back to the old path, which stays warm until M4.]

11.3 Risks

12. Appendices

12.1 Open questions

12.2 Glossary

12.3 References

Inspiration only; no text, diagrams or figures are copied.

Standard and licence note

Based on common industry practice for social graph storage and caching and on the public papers listed in 12.3, which are cited as inspiration only. This is a reference design to adapt, with illustrative numbers. Original text written for this collection; check the cited papers for the exact mechanisms they describe. Template licence: MIT.