1. The problem: why does "who follows whom" need its own service?

Almost every Instagram feature asks the graph a question:

• Feed: "who follows the author of this new post?" (to fan it out) and "whom do I follow?" (to pull celebrity posts).
• Profile: follower/following counts, "Followed by alice, bob and 12 others", the Follow/Following/Requested button.
• Privacy: "may this viewer see this private account's posts?", "has either blocked the other?".
• Stories: tray membership and close-friends audiences. Search and Explore: rank accounts you're connected to higher. DMs: requests vs inbox depending on whether you follow each other.

That makes graph reads one of the highest-QPS workloads in the system — every profile view, comment and feed refresh triggers several — while follows/unfollows are comparatively rare. And the data is skewed: a typical user follows a few hundred accounts, but the largest accounts have hundreds of millions of followers.

2. Modelling the graph

A graph is a set of nodes (vertices) connected by edges. Instagram's follow graph is directed (Alice following Bob doesn't mean Bob follows Alice — unlike Facebook friendship, which is undirected/symmetric) and edges carry a little data: creation time, state (active/pending), maybe a close-friends flag.

• Out-degree of a node = how many accounts it follows (Instagram caps this at 7,500 to curb spam). In-degree = follower count — unbounded, and extremely skewed (a power-law distribution).
• Adjacency list: the list of neighbours for each node — the natural storage form for sparse graphs (an adjacency matrix of 2B × 2B would be absurd).

2.1 Rough numbers (assumptions)

Accounts with edges        ~1.5B
Average following          ~200            → 300B directed edges
Stored in both directions  600B rows × ~25 B ≈ 15 TB  (× 3 replicas ≈ 45 TB, plus indexes)
Follow + unfollow writes   500M DAU × 0.2/day ≈ 100M/day ≈ 1,200/s avg
Graph reads                feed fan-out, profile views, permission checks, mutuals
                           → easily several hundred thousand to millions of lookups/s
Read : write               ≈ 1,000 : 1 (or more)

The data fits comfortably on a sharded cluster; the challenge is read throughput, latency and skew, which is why caching dominates graph design.

3. Storage options

3.1 One relational table with two indexes

CREATE TABLE follows (
  follower_id  BIGINT NOT NULL,
  followee_id  BIGINT NOT NULL,
  state        SMALLINT NOT NULL,            -- 1 = active, 2 = pending request
  created_at   TIMESTAMP NOT NULL,
  PRIMARY KEY (follower_id, followee_id)     -- "whom does A follow?", "does A follow B?"
);
CREATE INDEX follows_by_followee ON follows (followee_id, created_at DESC);  -- "who follows B?"

On a single database this is perfect: one row per edge, both directions indexed, follow/unfollow is one transaction, counts are a query (or a trigger-maintained column). It's how most apps start; early Instagram scaling talks describe a follow graph that began as essentially this kind of simple (source_id, target_id, status) table in PostgreSQL.

It breaks when you shard: if the table is sharded by follower_id, "whom does A follow" hits one shard, but "who follows B" must ask every shard (scatter-gather), because B's followers are spread everywhere. One of the two directions always becomes a cross-shard query.

3.2 Two tables, each sharded by its own user (dual writes)

The standard fix is to store the edge twice, each copy sharded by the user it "belongs" to:

• Reads are always local: following(A) lives on A's shard; followers(B) on B's shard.
• Writes touch two shards with no shared transaction (a dual write). If the second write fails, the copies disagree. Strategies:
  • Treat one side as the source of truth (usually following, the side the user controls), and write it together with an outbox event in one local transaction; a consumer applies the inverse edge idempotently, retrying until done.
  • Or write both synchronously and run an anti-entropy/repair job that scans for edges missing their inverse — the approach TAO takes.
• Storage doubles — a cheap price for halving the fan-out of every read.

Wide-column stores like Cassandra fit this naturally: partition key = user_id, clustering key = (created_at DESC, other_id), giving newest-first paged lists per user.

3.3 Graph databases

A graph database (Neo4j, Amazon Neptune, JanusGraph, TigerGraph) stores nodes and relationships natively, using index-free adjacency (each node points directly at its edges), and offers query languages like Cypher or Gremlin for multi-hop traversals:

// Cypher: accounts followed by people I follow, that I don't follow yet, ranked by overlap
MATCH (me:User {id: 1001})-[:FOLLOWS]->(f)-[:FOLLOWS]->(s)
WHERE NOT (me)-[:FOLLOWS]->(s) AND s <> me
RETURN s.id, count(f) AS mutuals ORDER BY mutuals DESC LIMIT 20

Great for deep traversals, fraud rings and knowledge graphs. But Instagram's online queries are almost all one hop (lists, edge checks, counts), at enormous QPS; general-purpose graph databases are hard to shard across hundreds of machines (a traversal crosses partitions constantly), and the multi-hop analyses (suggestions) can run offline in batch systems instead. That's why the largest social networks built sharded key-value/relational stores with graph-shaped APIs rather than using a graph database online.

3.4 Facebook's TAO: objects and associations

TAO ("The Associations and Objects", USENIX ATC 2013) is Meta's publicly described graph store serving Facebook's social graph — billions of reads per second, overwhelmingly reads. Its model:

• Objects: id → (otype, key-value data) — users, posts, comments, places.
• Associations: (id1, atype, id2) → (time, key-value data) — typed, directed edges such as FOLLOWS, LIKES, AUTHORED. An association list is all edges of one type from id1, ordered newest-first.
• Inverse types: FOLLOWS (A→B) can be configured with an inverse FOLLOWED_BY (B→A); TAO writes both. The two writes aren't atomic; a background job repairs "hanging" one-sided edges.
• A small API: assoc_add, assoc_delete, assoc_get(id1, atype, id2set) (edge check), assoc_count(id1, atype), assoc_range(id1, atype, pos, limit), assoc_time_range(id1, atype, high, low, limit).

• Storage: sharded MySQL; an object's ID encodes its shard, and an association is stored on the shard of id1, so association lists are single-shard.
• Caching: two cache layers. Follower tiers absorb reads; on a miss they ask the shard's leader cache, which reads the database. Writes go through the leader (write-through), which updates the DB and invalidates/refreshes followers. Counts (assoc_count) are cached alongside lists.
• Regions: one region holds each shard's primary DB; other regions hold replicas and forward writes to the primary region. Reads are eventually consistent across regions, with read-after-write for your own writes in practice.
• Why it works: the workload is >99% reads, associations are small, and most queries hit recent edges — so caching achieves very high hit rates.

3.5 Comparison

4. The queries the graph must answer

4.1 Mutuals: "Followed by …"

When Alice views Bob's profile, Instagram shows which of the people Alice follows also follow Bob: following(Alice) ∩ followers(Bob). Bob may have 50M followers, Alice ~300 followings — so iterate the small set and probe the big one:

def followed_by(viewer, profile, limit=3):
    mine = graph.following_ids(viewer)                       # ~300 IDs, cached list
    # one batched probe on profile's shard: which of these follow `profile`?
    hits = graph.followers_contains(profile, candidates=mine) # SELECT ... WHERE user=profile AND src IN (...)
    ranked = rank_by_closeness(viewer, hits)                  # show closest friends first
    return ranked[:limit], len(hits)                          # "Followed by a, b, c + N others"

Cost: one multi-get of ~300 keys on a single shard instead of reading 50M rows. "Mutual follow" (A follows B and B follows A) is just two point lookups.

4.2 Suggestions: friends-of-friends and People You May Know

The classic signal is triadic closure: if many people you follow follow X, you probably know or would like X. Computing it online is too expensive — 300 followings × 300 followings each = 90,000 candidate edges per request — so it's done offline (Spark/batch over a graph snapshot in the data warehouse, see Analytics & ML) and served from a precomputed store:

1. Candidate generation: friends-of-friends (2-hop), uploaded contacts (with consent), accounts that follow you but you don't follow back, co-follow similarity ("people who follow X also follow Y"), location/school signals, embeddings + approximate nearest neighbours.
2. Scoring: number of mutual connections, weighted so that mutual friends with few connections count more — e.g. Adamic–Adar score(u, x) = Σz ∈ mutuals 1 / log(degree(z)) — plus an ML model predicting follow-back and long-term engagement.
3. Filtering: remove already-followed, blocked, previously dismissed, private-policy violations, spam accounts.
4. Serving: store the top ~100 per user in a key-value store; refresh daily; add real-time suggestions after a follow ("similar accounts to the one you just followed") from a co-follow index.

5. Celebrity accounts

The largest Instagram accounts have over 600 million followers. Everything that's trivial for a normal user becomes an engineering problem:

• Wide partitions: a followers partition keyed only by user_id would hold 600M rows × ~25 B ≈ 15 GB on one replica set — far beyond what Cassandra-style stores handle well (partitions are best kept well under ~100 MB). Fix: bucket the key, e.g. (user_id, bucket) where bucket is a time range of follow date or hash(follower_id) % N, with N chosen per account size.
• Pagination only: nobody (human or service) may load the whole list. The UI pages 50 at a time with an opaque cursor (bucket, created_at, follower_id), and offers search within followers instead of endless scrolling.
• Fan-out: pushing a celebrity's post into 600M timelines would take 600M writes — the news feed switches to pull for such authors (section 8).
• Hot counters: a celebrity gains thousands of followers per minute; their follower count is a hot counter (section 6).
• Hot edge checks: "does viewer follow Celeb?" is asked by millions of profile views — but it's keyed by (viewer, Celeb) on the viewer's following list, so the load is naturally spread. Good key design matters.

6. Follower count consistency

Counting followers(B) on each profile view would scan millions of rows, so counts are denormalised: follower_count and following_count stored per user and updated on follow/unfollow. Problems and fixes:

• Hot counter: a celebrity gaining 5,000 followers/minute serialises on one row — use the same tricks as like counters: stream aggregation of FollowCreated/FollowRemoved deltas, sharded counters, Redis INCR + flush.
• Drift: retries, partial dual writes and bugs make counters disagree with the edge lists. Derive deltas only from actual state transitions, and run periodic reconciliation (recount edges for accounts whose counters look suspicious, or sample-check).
• Eventual consistency: the public count may lag by seconds; large counts are shown rounded ("612M"). The user's own following count should reflect their action immediately (read-your-writes via optimistic UI).
• Spam cleanup: purging fake accounts removes their edges in bulk, so counts drop in batches — another reason to aggregate deltas rather than lock rows.

7. Private accounts, follow requests, blocking and close friends

7.1 Follow requests

For a private account, following is a two-step handshake. Model the request as its own edge type with a small state machine:

 STATE        EVENT                                  NEXT STATE   EDGES WRITTEN
 ──────────   ────────────────────────────────────   ──────────   ─────────────────────────────────────
 NONE         follow (public account)                FOLLOWING    + FOLLOWS(A→B), FOLLOWED_BY(B←A)
 NONE         follow (private account)               REQUESTED    + FOLLOW_REQUEST(A→B), INCOMING_REQ(B←A)
 REQUESTED    owner accepts                          FOLLOWING    − request edges, + follow edges
 REQUESTED    owner declines / requester cancels     NONE         − request edges
 FOLLOWING    unfollow / owner removes follower      NONE         − follow edges
 any          block (either direction)               NONE         − all follow/request edges, + BLOCKS

• Accepting deletes the request edges and adds the follow edges (plus counts and a FollowCreated event) — a small saga across shards, made idempotent so a double-tap on "Confirm" is harmless.
• Switching private → public auto-approves pending requests (a background job, since there may be thousands).
• Access checks: a private account's posts, stories and follower lists are visible only if does_follow(viewer, owner) is true and active (not pending).

7.2 Blocking

A block (A blocks B) is a strong, symmetric-in-effect relationship stored as its own edge type (BLOCKS with inverse BLOCKED_BY):

• On block: remove follow edges in both directions, remove pending requests, adjust counts, and emit events so feeds/trays drop each other's content.
• On every read path (feed, profile, search, comments, likes lists, stories, DMs) check blocked(A, B) OR blocked(B, A). These checks are extremely frequent, so block lists are small, cached per user, and loaded once per request.
• Blocking must win races: if B's post was already fanned into A's timeline, the read-time filter hides it.

7.3 Close friends, mute and restrict

All are just more typed edges in the same store — which is exactly why a TAO-style "associations with types" model is so convenient: one system, one API, many relationship kinds.

8. How fan-out workers read the graph

When a PostCreated event arrives, the feed fan-out workers must insert the post ID into every follower's timeline. The graph is their main input:

1. Check size: if B's follower count exceeds a threshold (say 1M), skip push entirely — B is a "celebrity" and followers will pull B's recent posts at read time (the feed service calls following(viewer) to find which celebrities to merge).
2. Page through followers: read followers(B) in pages of ~1,000 via cursor; each page becomes an independent job on a queue, so a 500k-follower fan-out is parallelised across many workers and resumable if one crashes.
3. Filter: skip inactive followers (no login in 30 days — they'll get a rebuilt feed on return), muted relationships, blocks, audience restrictions.
4. Batch writes: group follower IDs by timeline cache shard and pipeline ZADDs; trim timelines to the latest N entries. ZADD is idempotent, so retries are safe.

Rough load: 100M posts/day × ~200 followers ≈ 20B timeline inserts/day ≈ 230k/s — which is why follower reads for fan-out are served from cache or bulk-scanned efficiently, and why the celebrity cut-off matters.

9. Follow / unfollow event flow

 App (Alice)        Graph service              Alice's shard        Kafka               Consumers
   | POST /follow Bob   |                            |                  |                      |
   |------------------->| check: blocked? private?   |                  |                      |
   |                    | rate limit (anti-spam)     |                  |                      |
   |                    |-- tx: following(alice,bob) |                  |                      |
   |                    |       + outbox FollowCreated -->|             |                      |
   |<-- 200 following --|                            |-- relay ------->|                      |
   |  (optimistic UI)   |                            |                  |-- inverse writer: followers(bob, alice)
   |                    |                            |                  |-- counters: alice.following+1, bob.followers+1
   |                    |                            |                  |-- notifications: "alice started following you"
   |                    |                            |                  |-- feed backfill: bob's recent posts → alice's timeline
   |                    |                            |                  |-- PYMK / search affinity / analytics

• Feed backfill: after following, the new followee's recent posts should appear in your feed. A consumer inserts B's last few posts into A's timeline (or the feed simply merges them at read time).
• Unfollow mirrors it: delete the edge (+ outbox FollowRemoved); consumers remove the inverse edge, decrement counts, and remove B's posts from A's timeline — or, more cheaply, the feed filters them out at read time against the current following list.
• Idempotency: following someone you already follow creates no new edge and emits no event; consumers dedupe on event ID.
• Abuse: follow/unfollow churn is a classic spam tactic, so the API enforces per-account rate limits and follow caps (see Rate limiting).

10. Sharding and caching the graph

10.1 Sharding

• Shard key = the owning user's ID for each adjacency list: following(A) on shard(A), followers(B) on shard(B). Instagram's 64-bit IDs embed a logical shard number (ID generation), and logical shards map onto physical databases, so data can be rebalanced by moving logical shards.
• Co-location: keeping all of one user's edge types (follows, blocks, close friends, requests) on that user's shard means a request about one user's relationships touches one shard.
• Celebrity buckets: very large follower lists are split into sub-partitions (section 5).
• Consistent hashing or a directory of logical → physical shards makes adding capacity cheap (Consistent hashing).

10.2 Caching

Writes use write-through or invalidate-on-write to the owner's cache entries (TAO's leader cache serialises writes per shard to keep caches coherent). Across regions, caches are eventually consistent; a user's own follow is reflected immediately on their device via optimistic UI and, server-side, by routing their reads to fresh data for a short window after a write. See Caching and Replication.

11. How Instagram uses the social graph

• Scale (assumed): hundreds of billions of edges; graph reads in the millions per second across all features; follows/unfollows in the low thousands per second.
• Limits: Instagram caps how many accounts one user can follow (7,500), bounding out-degree for fan-in reads and mutuals — while in-degree (followers) is unbounded and handled with bucketing and pull-based fan-out.
• Privacy: private accounts, requests, blocks, restrict, mute and close friends are all typed edges checked on every read path.

12. Trade-offs & common pitfalls

Common pitfalls

• Sharding one follows table by follower only → every "who follows B" query is a scatter-gather across all shards.
• COUNT(*) for follower counts on profile views.
• Unbucketed celebrity partitions → 15 GB partitions, slow compactions, timeouts.
• Loading entire follower lists into memory in fan-out or "export" features.
• Checking blocks/privacy only at write time → content leaks after relationships change.
• No negative caching for edge checks → most lookups ("no, A doesn't follow B") hit the database.
• Computing friends-of-friends online per request.

13. Real-world technologies

14. Interview corner

15. Check your understanding

Related lessons

• News Feed — the main consumer of follower lists; push vs pull for celebrities
• Sharding — shard keys, wide partitions and scatter-gather
• Caching — write-through caches, negative caching and hot keys
• Databases — relational vs wide-column vs graph databases
• Likes & Counters — the same counter techniques for follower counts
• Stories — close-friends audiences and tray fan-out
• Microservices — the outbox pattern behind dual writes
• Analytics & ML — offline graph processing for suggestions
• Security & Privacy — blocking, private accounts and abuse prevention