# 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.

<!--
Guidance: How to use this template
- Start with 3.1: the read rate, the write rate and the size of the graph.
  The read-to-write ratio decides almost everything else in this design.
- Fill the access-pattern table (5.3) before you pick storage; a graph
  store is defined by the handful of queries it must answer fast.
- Decide the consistency promise (7.2) in writing with product owners.
  "My own write is visible to me" is cheap; "everyone sees every write at
  once" is not, and nobody needs it for likes.
- Keep the failure-mode table (9.1) and the 10x / 0.1x row (10.1) filled;
  reviewers check them first.
- Use the 45-minute path (1.4) when you present this design in an interview
  or a short review; use the full document for a real design review.
-->

## Document control

<!-- Guidance: A design is a proposal until it is approved; record who decided and when. -->

| Field | Value |
|---|---|
| Document ID | [SDD-GRAPH-001] |
| System / feature | [Social graph store and cache] |
| Version | [0.1] |
| Status | [Draft / In review / Approved / Implemented / Superseded] |
| Owner | [@owner] |
| Author(s) | [@author] |
| Approvers / reviewers | [@reviewer-1], [@reviewer-2] |
| Last updated | YYYY-MM-DD |
| Classification | [Internal / Confidential] |
| Data classes stored | [Profile data, relationships, content references, privacy settings] |
| Regions | [Primary region, follower regions] |
| Related | News Feed System Design (`system-design/design-news-feed`), Distributed Key-Value Store Design (`system-design/design-distributed-kv-store`), [ADR: consistency model] |

### Approvals

| Role | Name | Decision | Date |
|---|---|---|---|
| Tech lead | [@name] | [Approved / Changes requested] | YYYY-MM-DD |
| Staff / principal engineer | [@name] | [Decision] | YYYY-MM-DD |
| Database reliability engineering | [@name] | [Decision] | YYYY-MM-DD |
| Privacy and security | [@name] | [Decision] | YYYY-MM-DD |
| Product (consistency promise) | [@name] | [Decision] | YYYY-MM-DD |

## Revision history

<!-- Guidance: Note what changed in the design, not the wording. -->

| Version | Date | Author | Change summary |
|---|---|---|---|
| 0.1 | YYYY-MM-DD | [@name] | First draft for design review |
| 0.2 | YYYY-MM-DD | [@name] | *Example:* Added follower tier per region after miss-rate analysis |
| 0.3 | YYYY-MM-DD | [@name] | *Example:* Inverse edges written by the leader with background repair |
| 1.0 | YYYY-MM-DD | [@name] | *Example:* Approved |

## Contents

<!-- Guidance: Keep aligned with the headings. -->

1. [Overview](#1-overview)
2. [Requirements](#2-requirements)
3. [Capacity estimation](#3-capacity-estimation)
4. [API design](#4-api-design)
5. [Data model](#5-data-model)
6. [High-level design](#6-high-level-design)
7. [Detailed design](#7-detailed-design)
8. [Scalability and performance](#8-scalability-and-performance)
9. [Reliability, security and operations](#9-reliability-security-and-operations)
10. [Trade-offs and alternatives](#10-trade-offs-and-alternatives)
11. [Delivery plan and risks](#11-delivery-plan-and-risks)
12. [Appendices](#12-appendices)

## 1. Overview

<!-- Guidance: One page that a busy reviewer can read alone: problem, proposed solution in a paragraph, and the decisions that need their attention. -->

### 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

| ID | Question | Recommended option | Section |
|---|---|---|---|
| Q-01 | *Example:* Generic cache or graph-aware cache? | Graph-aware: objects and association lists are first-class cache entries | 7.1, 10 |
| Q-02 | *Example:* Consistency promise? | Read-after-write for the writer within its tier; eventual elsewhere, bounded by replication lag | 7.2 |
| Q-03 | *Example:* How to keep inverse edges in sync? | Two writes from the leader, repaired by a background checker | 7.4 |
| Q-04 | *Example:* How to shard? | Shard id embedded in object id; associations live with their source object | 7.5 |
| [Q-nn] | [Question] | [Option] | [Section] |

### 1.4 45-minute interview path

<!-- Guidance: Use this order when time is short. Name the deep dive you pick and why. -->

| Minutes | Cover | Output on the whiteboard |
|---|---|---|
| 0 to 5 | Core requirements (2.1) and what is below the line (2.3) | Five queries the store must serve; consistency promise |
| 5 to 10 | Estimates (3) with consequences | Read rate, graph size, "cache must absorb over 95% of reads" |
| 10 to 15 | API (4) and data model (5) | Objects, associations, access-pattern table |
| 15 to 25 | High-level design (6) | Clients, follower tier, leader tier, sharded database, invalidation path |
| 25 to 40 | One or two deep dives | Pick 7.2 (read-after-write) by default; pick 7.3 (hot vertices) if the interviewer mentions celebrities |
| 40 to 45 | Failure modes and 10x (9.1, 10.1) | What breaks first and the fix |

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

## 2. Requirements

<!-- Guidance: Split core requirements from below-the-line items so nobody designs for what is out of scope. Non-functional requirements need numbers and a way to measure them. -->

### 2.1 Core functional requirements

| ID | Requirement | Priority |
|---|---|---|
| FR-01 | *Example:* Create, read, update and delete typed objects with a small set of fields | Must |
| FR-02 | *Example:* Add and remove typed associations between two objects, with a timestamp and small payload | Must |
| FR-03 | *Example:* List associations of one type from an object, newest first, with paging | Must |
| FR-04 | *Example:* Count associations of one type from an object (followers, likes) | Must |
| FR-05 | *Example:* Check whether specific associations exist (does user A like post P) | Must |
| FR-06 | *Example:* Maintain inverse associations automatically for configured types (follows / followed by) | Must |
| FR-07 | *Example:* List associations in a time range (likes since yesterday) | Should |
| [FR-nn] | [Requirement] | [Must / Should / Could] |

### 2.2 Non-functional requirements

| ID | Quality | Target | Measured as |
|---|---|---|---|
| NFR-01 | Read latency | *Example:* p99 at or below 5 ms for cache hits, 50 ms for misses | Client-side timing per call |
| NFR-02 | Read throughput | *Example:* 20 million reads/s at peak, all regions | Load test and production metrics |
| NFR-03 | Write latency | *Example:* p99 at or below 100 ms in the primary region, 250 ms from follower regions | Client-side timing |
| NFR-04 | Consistency | *Example:* A writer reads its own write on the next request; others see it within 2 s at p99 | Synthetic write-then-read probes |
| NFR-05 | Availability | *Example:* 99.99% for reads; reads continue from cache during database outages | Error budget |
| NFR-06 | Durability | *Example:* No acknowledged write lost (RPO 0 within region) | Restore tests |
| [NFR-nn] | [Quality] | [Target] | [Measurement] |

### 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

<!-- Guidance: Back-of-the-envelope numbers decide the shape of the design. Show inputs, formulas and results, and end every estimate with the design consequence. See Back-of-Envelope Estimation (`system-design/back-of-envelope-estimation`). -->

### 3.1 Assumptions

| Input | Value | Source |
|---|---|---|
| Peak graph reads per second, all regions | *Example:* 20 million | Page profiling x traffic forecast |
| Peak graph writes per second | *Example:* 100 000 | Write logs |
| Regions | *Example:* 4 (one primary per shard, followers elsewhere) | Deployment plan |
| Objects | *Example:* 50 billion, average 500 bytes | Database statistics |
| Associations, including inverses | *Example:* 1 trillion, average 100 bytes | Database statistics |
| Hot working set | *Example:* 5% of all data | Cache simulation on access logs |
| Cache server capacity | *Example:* 200 000 ops/s and 256 GB memory | Benchmark on target instance |

### 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

| Quantity | Estimate | Design consequence |
|---|---|---|
| Data | ~125 TB logical | 250 database primaries; sharded from day one |
| Reads | 20 million/s | Two cache tiers; database sees under 1% of reads |
| Writes | 100 000/s (160 000 rows/s) | Leader per shard serialises writes and invalidations |
| Hot key | 1 million reads/s | Hot-key replication and client cache |
| Follower servers | 50 per region | Sized for throughput, memory has 2x headroom |

## 4. API design

<!-- Guidance: Define the contract first. A small fixed API is a feature: it lets the cache understand every query. Use RFC 9457 problem details for errors on HTTP interfaces. -->

### 4.1 Operations

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

| Operation | Purpose | Served from |
|---|---|---|
| `getObject(id)` | Read one object | Follower cache |
| `createObject(type, fields) -> id` | Create an object; id allocated on a chosen shard | Leader, then database |
| `updateObject(id, fields, version)` | Update fields with optimistic version check | Leader |
| `deleteObject(id)` | Soft-delete; associations cleaned asynchronously | Leader |
| `addEdge(src, type, dst, time, data)` | Add an association and its inverse if configured | Leader |
| `removeEdge(src, type, dst)` | Remove an association and its inverse | Leader |
| `getEdges(src, type, dstSet)` | Check existence of specific associations | Follower cache |
| `countEdges(src, type)` | Number of associations of a type | Follower cache |
| `rangeEdges(src, type, offset, limit)` | Newest-first page of an association list | Follower cache |
| `timeRangeEdges(src, type, from, to, limit)` | Associations within a time range | Follower cache |

### 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).

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

```json
{"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

| Case | Behaviour |
|---|---|
| Unknown association type | Reject with `INVALID_TYPE`; types are registered in a schema registry |
| Version conflict on update | Reject with `CONFLICT`, return current version |
| Page size above 1 000 | Clamp to 1 000; deep paging beyond 10 000 uses time ranges |
| Leader unreachable on write | Retry once on the backup leader, then fail with `UNAVAILABLE` |
| Schema change | New fields are additive; association types are never reused after deletion |

## 5. Data model

<!-- Guidance: Choose storage by access pattern, not by habit. Show entities, keys, partitioning and the queries each store must answer. -->

### 5.1 Entities

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

```mermaid
erDiagram
  OBJECT {
    bigint id PK
    string otype
    bytes fields
    int version
    datetime updated_at
  }
  ASSOCIATION {
    bigint src PK
    string atype PK
    bigint dst PK
    bigint time
    bytes data
  }
  ASSOC_COUNT {
    bigint src PK
    string atype PK
    bigint count
  }
  ASSOC_TYPE {
    string atype PK
    string inverse_type
    bool unique_per_pair
  }
  OBJECT ||--o{ ASSOCIATION : "is source of"
  OBJECT ||--o{ ASSOC_COUNT : "has counts"
  ASSOC_TYPE ||--o{ ASSOCIATION : "types"
```

### 5.2 Storage choices

| Data | Store | Key | Why |
|---|---|---|---|
| Objects | *Example:* Sharded relational database | `id` (shard id embedded) | Durable, transactional per shard, mature tooling |
| Associations | Same shard as `src` | `(src, atype, dst)` plus index on `(src, atype, time)` | One shard answers every list and count for a source |
| Counts | Same shard as `src` | `(src, atype)` | Counting rows at read time is too slow for popular objects |
| Association types | Schema registry, pushed to all servers | `atype` | Small, changes rarely |
| Cached objects and lists | Follower and leader caches | Object id; `(src, atype)` list | Serve over 99% of reads |

### 5.3 Access patterns

| Query | Served by | Key or index | Partition rationale |
|---|---|---|---|
| Profile card: get object | Follower cache, then leader, then `objects` | `id` | Shard from id, no lookup needed |
| Latest 25 likes of a post | Cached association list | `(src, atype, time desc)` | All edges of a source on one shard |
| Like count of a post | Cached count | `(src, atype)` count row | Same shard as the edges, updated in the same transaction |
| Does user A follow B | Cached list lookup or point query | `(src=A, atype=follows, dst=B)` | Point lookup on A's shard |
| Who follows B (followers list) | Inverse type `followed_by` on B | `(src=B, atype=followed_by, time desc)` | Inverse edge stored on B's shard, avoids scatter-gather |
| Likes since a time | Cached list if covered, else index range | `(src, atype, time)` | Range scan on one shard |

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

<!-- Guidance: One diagram that shows every component on the read and write paths and where state lives. Name components by responsibility. -->

```mermaid
flowchart LR
  web[Web and API servers] --> fol[Follower cache tier, local region]
  fol -->|miss or write| lead[Leader cache tier, owns shard]
  lead --> db[(Sharded database primary)]
  db -->|replication stream| rdb[(Replica in follower region)]
  lead -->|invalidate / refill| fol
  rdb --> rlead[Leader tier in follower region]
  rlead -->|invalidate| rfol[Follower tier, other region]
  rweb[Web servers, other region] --> rfol
  rfol -->|miss| rlead
  rlead -->|writes forwarded| lead
  reg[Schema registry] --> fol
  reg --> lead
```

| Component | Responsibility | Scales by |
|---|---|---|
| Follower cache tier | Serve reads; forward misses and writes to the leader; apply invalidations | Servers per region; several tiers per region if needed |
| Leader cache tier | One leader per shard; serialise writes, read through to the database, send invalidations | Shards per leader server |
| Sharded database | Durable storage; one primary per shard in its primary region | Number of shards |
| Replica database and regional leader | Serve misses locally in follower regions; forward writes to the primary region | Per region |
| Schema registry | Association types, inverse rules, field schemas | Small replicated service |

## 7. Detailed design

<!-- Guidance: Go deep on the parts that are new, risky or contested. Each deep dive lists options, the choice and the reason. -->

### 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.

```mermaid
sequenceDiagram
  participant W as Web server
  participant F as Follower
  participant L as Leader
  participant D as Database
  W->>F: rangeEdges(post, liked_by, 0, 25)
  alt list cached
    F-->>W: 25 edges + count
  else miss
    F->>L: rangeEdges(post, liked_by, 0, 25)
    L->>D: SELECT by (src, atype, time desc) LIMIT N
    D-->>L: rows
    L-->>F: list + count (cache it)
    F-->>W: 25 edges + count
  end
```

### 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.

| Option | How it works | Cost |
|---|---|---|
| A. Invalidate on write, no other guarantee | Leader sends invalidations; readers may see old data briefly | Visible staleness for the writer |
| B. Write-through to the writer's follower | The follower that received the write applies the result to its own cache synchronously | Only that follower is fresh |
| C. Sticky routing per user | Route a user's reads to the same follower tier for a session | Hot users skew load |
| D. Version tokens | Write returns a version; reads carrying a newer token bypass stale entries | Token plumbing in every client |
| E. Read from primary for critical reads | Selected reads go to the leader in the primary region | Cross-region latency |

**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.

| Option | Effect | Drawback |
|---|---|---|
| A. More shards | Spreads keys, not one key | Does not help a single hot key |
| B. Replicate hot keys across follower servers | Reads for a hot key spread over K servers | Invalidation fan-out multiplies by K |
| C. Short client-side cache (*Example:* 1 s) | Absorbs repeated reads on one web server | Up to 1 s extra staleness |
| D. Cap cached list length and page by time | Bounded memory for huge lists | Deep pages hit the database |
| E. Approximate counts for very large lists | Count updated by batched increments | Count lags by seconds |

**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.

| Option | Consistency | Cost |
|---|---|---|
| A. Distributed transaction (two-phase commit) | Atomic | Latency, coordinator failure handling, lock contention on hot vertices |
| B. Two ordered writes from the leader, forward then inverse | Brief window where one side exists | Needs repair for crashes between writes |
| C. Write forward edge, derive inverse from change data capture | Inverse lags by seconds | Extra pipeline |

**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.

| Option | Lookup | Rebalancing |
|---|---|---|
| A. Hash of id modulo host count | None | Re-hashing moves most data |
| B. Directory service mapping id to shard | One lookup per request | Flexible, but another dependency |
| C. Shard id embedded in the object id, logical shards mapped to hosts | None for shard; small cached map for host | Move whole logical shards between hosts |

**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

<!-- Guidance: Show how the design meets the numbers in section 3 and where it will break first. -->

| Concern | Approach | Limit before redesign |
|---|---|---|
| Read throughput | Add follower servers or a second follower tier per region | *Example:* invalidation fan-out above 4 tiers per region |
| Database growth | Move logical shards to new hosts | One logical shard per host at most: 16 384 hosts, or about 8 PB at 0.5 TB of data per host, before the id scheme changes |
| Hot keys | Hot-key replication and client cache | One key above 5 million reads/s |
| Very large lists | Cached prefix plus time-range paging | Lists above 100 million edges need a separate index |
| Cross-region writes | Forwarding to primary region | Write-heavy regions should own their users' shards |

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

| Step | Budget |
|---|---|
| Client library routing and serialisation | 0.3 ms |
| Network to follower (same zone) | 0.5 ms |
| Follower lookup | 0.2 ms |
| Tail allowance (GC, queueing) | 4.0 ms |

## 9. Reliability, security and operations

<!-- Guidance: Name the failure modes, the threats and the signals operators watch. Each mitigation should be testable. -->

### 9.1 Failure modes

| Component | Failure | Detection | Blast radius | Mitigation | RTO |
|---|---|---|---|---|---|
| Follower server | Crash | Health check, client errors | Keys on that server in one tier | Clients re-route to another follower in the tier; cold keys refill from leader | *Example:* 30 s |
| Leader server | Crash | Health check | Writes and misses for its shards | Backup leader promoted; followers route misses to it | *Example:* 60 s |
| Database primary | Failure | Replication monitor | Writes to one shard | Promote replica; leaders queue writes briefly, then fail them | *Example:* 5 min |
| Primary region | Loss | Region health | Writes for shards mastered there | Promote replicas in a follower region per shard; reads continue from cache | *Example:* 30 min |
| Replication lag | Lag above 10 s | Lag metric | Stale reads in one follower region | Route critical reads to primary; alert | Until lag clears |
| Mass cache loss | Deploy or bug flushes caches | Hit-rate drop | Database overload, global | Rolling restarts only; warm new tiers from a peer; admission control at leaders | *Example:* 15 min |
| Invalidation loss | Message dropped | Consistency probe mismatches | Stale entries until TTL | Version check on refill; TTL backstop (*Example:* 1 day) | Probe interval |

### 9.2 Security and privacy

| Threat | Control |
|---|---|
| Enumeration of private edges | Store has no public interface; callers authenticate with service identity and apply privacy checks |
| Bulk scraping through the application | Rate limits per user and per token; see Rate Limiter System Design (`system-design/design-rate-limiter`) |
| Data subject deletion | Object delete tombstones, then asynchronous removal of edges on both shards and from caches, with completion tracking |
| Insider access | Access to raw shards is audited and break-glass only |
| [Threat] | [Control] |

### 9.3 Observability

| Signal | Metric | Alert threshold |
|---|---|---|
| Follower hit rate | Per tier and per query type | Below 95% for 10 min |
| Read latency | p99 per region | Above 5 ms for 10 min |
| Consistency probes | Write-then-read mismatch rate | Any mismatch older than 2 s |
| Hot keys | Top keys per server | Any key above 50 000 reads/s not yet replicated |
| Inverse repair backlog | Missing inverses found per hour | Increase over 7-day baseline |

### 9.4 Cost estimate

| Item | Unit cost | Quantity | Monthly cost |
|---|---|---|---|
| Follower cache servers | [USD per server-month] | *Example:* 200 (4 regions x 50) | [USD] |
| Leader cache servers | [USD per server-month] | *Example:* 80 | [USD] |
| Database hosts (primary and replicas) | [USD per host-month] | *Example:* 250 x 4 | [USD] |
| Cross-region replication traffic | [USD per GB] | [GB] | [USD] |
| **Total** | | | **[USD]** |

## 10. Trade-offs and alternatives

<!-- Guidance: For each major decision list the options, what each costs and why you chose one. Include what changes at 10x and at 0.1x. -->

### 10.1 Decisions

| Decision | Options | Chosen | Why | What we give up |
|---|---|---|---|---|
| Storage engine | Native graph database; wide-column store; sharded relational | Sharded relational | Mature operations, transactions per shard, known tooling | No multi-hop queries in the store |
| Cache model | Look-aside key-value; graph-aware cache | Graph-aware | Updates lists in place; one invalidation scheme | A custom cache service to build and run |
| Consistency | Strong everywhere; eventual with per-writer read-after-write | Eventual with read-after-write | Low latency and high availability | Others may see old data for seconds |
| Inverse edges | Distributed transaction; two writes plus repair | Two writes plus repair | No cross-shard locks | Brief one-sided edges |
| **At 10x** (200 million reads/s, 1.25 PB) | | | More follower tiers per region; split id space; hot-key replication becomes standard | Invalidation fan-out becomes the bottleneck; consider lease-based refill |
| **At 0.1x** (2 million reads/s, 12 TB) | | | One cache tier and a handful of database shards, or a managed key-value store with secondary indexes | The two-tier cache is not worth its operating cost |
| [Decision] | [Options] | [Chosen] | [Why] | [Cost] |

### 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

<!-- Guidance: How the design reaches production safely, and what could stop it. -->

### 11.1 Milestones

| Milestone | Scope | Exit criterion | Target date |
|---|---|---|---|
| M1 | Graph API over existing databases, no new cache | Shadow reads match existing results above 99.99% | YYYY-MM-DD |
| M2 | Leader tier and invalidations in one region | Hit rate above 90%, no consistency probe failures | YYYY-MM-DD |
| M3 | Follower tiers in all regions | Read p99 under 5 ms | YYYY-MM-DD |
| M4 | Old look-aside caches removed | Zero direct database reads from product code | YYYY-MM-DD |

### 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

| ID | Risk | Likelihood | Impact | Mitigation | Owner |
|---|---|---|---|---|---|
| R-01 | *Example:* Consistency bugs surface as user-visible stale data | Medium | High | Consistency probes before each migration step | [@name] |
| R-02 | *Example:* Cache warm-up overloads databases | Medium | High | Warm from peer tier; leader admission control | [@name] |
| R-03 | *Example:* Product teams need queries outside the fixed API | High | Medium | Add operations through design review only | [@name] |
| [R-nn] | [Risk] | [L / M / H] | [L / M / H] | [Mitigation] | [@name] |

## 12. Appendices

<!-- Guidance: Supporting detail, glossary, references and open questions. -->

### 12.1 Open questions

| ID | Question | Owner | Due |
|---|---|---|---|
| OQ-01 | *Example:* Which association types need inverses by default? | [@name] | YYYY-MM-DD |
| OQ-02 | *Example:* Should counts above 10 million be shown rounded? | [@name] | YYYY-MM-DD |
| [OQ-nn] | [Question] | [@name] | YYYY-MM-DD |

### 12.2 Glossary

| Term | Meaning |
|---|---|
| Object | A typed node in the graph with a small set of fields |
| Association | A typed, directed, timestamped edge from a source object to a destination object |
| Inverse association | The edge maintained in the opposite direction on the destination's shard |
| Leader tier | The cache tier that owns a shard and is the only one writing to its database |
| Follower tier | A cache tier that serves reads and forwards misses and writes |
| Hot vertex | An object whose read rate exceeds what one cache server can serve |
| [Term] | [Meaning] |

### 12.3 References

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

| Reference | Use |
|---|---|
| Bronson et al., "TAO: Facebook's Distributed Data Store for the Social Graph", USENIX ATC 2013, pp. 49 to 60 (usenix.org/conference/atc13/technical-sessions/presentation/bronson) | Object and association model, cache tiers (paraphrased in 7.5) |
| Nishtala et al., "Scaling Memcache at Facebook", USENIX NSDI 2013 | Look-aside caching problems that motivate a graph-aware cache |
| RFC 9457 Problem Details for HTTP APIs | Error format for any HTTP-facing interface |
| News Feed System Design (`system-design/design-news-feed`) | Main consumer of the graph |
| Back-of-Envelope Estimation (`system-design/back-of-envelope-estimation`) | Method for section 3 |
| Resilience and Load Shedding Design (`system-design/resilience-load-shedding-design`) | Admission control during cache warm-up |

## 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.