Storing a social graph

The problem: who follows whom

Snip Bio lets people follow creators. The feed (12.03 Feed generation: push, pull, hybrid) needs "who does Ana follow?", notifications need "who follows this creator?", profiles show follower counts, and the app suggests "creators followed by people you follow". Soon there are hundreds of millions of follow edges, and one creator has 9 million followers.

Edges as rows, indexed both ways

A follow is an edge with a direction. The plainest storage is a table of edges, indexed for both questions:

CREATE TABLE follows (
  follower_id bigint      NOT NULL,
  followee_id bigint      NOT NULL,
  created_at  timestamptz NOT NULL DEFAULT now(),
  PRIMARY KEY (follower_id, followee_id)                              -- "who does X follow?", no duplicates
);
CREATE INDEX follows_by_followee ON follows (followee_id, follower_id); -- "who follows X?"

Each question is now an index range scan. Tested on 395,000 random edges in Postgres: listing a user's followers ran as an index-only scan, and "people you may know" (accounts followed by the people you follow, excluding ones you already follow) ran in about a quarter of a millisecond:

SELECT f2.followee_id AS suggestion, count(*) AS via
  FROM follows f1
  JOIN follows f2 ON f2.follower_id = f1.followee_id
 WHERE f1.follower_id = $1
   AND f2.followee_id <> $1
   AND NOT EXISTS (SELECT 1 FROM follows x WHERE x.follower_id = $1 AND x.followee_id = f2.followee_id)
 GROUP BY f2.followee_id
 ORDER BY via DESC
 LIMIT 10;

Two hops is where this stays fast: it touches the edges of the people you follow. Three hops multiplies again, which is why "friends of friends of friends" queries are computed offline, not per request.

Counts are stored, not counted

"9.2M followers" on a profile can't be count(*) over 9 million rows on every view. Keep a counter per account, updated when edges are added or removed, through the same batching as any hot counter (11.01 Counting at scale): a viral creator gains thousands of followers a minute, and one counter row would be a hot spot (05.02 Hot partitions and celebrity keys).

Sharding the graph

At hundreds of millions of edges, the table is sharded (05.01 Sharding: range, hash, directory). By follower ID, "who do I follow?" is on one shard but "who follows X?" is spread over all of them. The usual answer is to store each edge twice: once on the follower's shard (outgoing) and once on the followee's shard (incoming), written together through the outbox (07.06 The outbox pattern and change data capture). Each direction is then a single-shard query.

The celebrity with 9 million followers still puts 9 million incoming edges on one shard. Paging through them is fine; loading them all at once isn't, and the feed avoids needing to (12.03 Feed generation: push, pull, hybrid).

Objects and associations: Facebook's TAO

Facebook stores its social graph in TAO, which models everything as objects (users, posts, comments) and associations (typed, directed edges: follows, likes, authored, commented on). Underneath, TAO is MySQL, sharded, with a large two-tier cache in front of it: read-dominated work is served from cache, and the cache understands association lists, so "the 50 most recent comments on this post" is a cache read. Its API is deliberately small: get an object, get associations of a type from an object (newest first), count them.

That's the general lesson. Most social graphs are mostly one- or two-hop lookups (followers, following, likes on a post), which a relational store with the right indexes and a cache handles well. Graph databases shine for deep, arbitrary traversals (fraud rings, recommendations across many hops), which are usually run offline.

Recap

Interview questions