Designing Facebook TAO: A Read-Optimized Store for the Social Graph

When engineers hear "social graph," they reach for a graph database. Facebook — owner of the largest social graph in existence — famously does not use one. TAO, the system serving that graph, is MySQL shards under two tiers of graph-aware cache, exposing an API so restricted it forbids most things graph databases are proud of. The restraint is the design: TAO is a masterclass in cutting features to fit a workload, and it's become a staple question for exactly that reason.

The workload dictates everything

The read:write ratio is extreme — roughly 1,000:1. Every page render fans into hundreds of tiny graph reads (this user's friends, this post's likes, is A tagged in B), latency budget in single-digit milliseconds, from data centers worldwide. Writes (a like, a comment) trickle by comparison but must be visible to their author immediately. Queries are shallow: point reads and one-hop association lists — nobody renders a page with a six-hop traversal. That last observation is the license for everything TAO refuses to do.

The data model: objects and associations

Two types, total:

object:      (id) -> {otype, key->value data}          # user, post, comment, page
association: (id1, atype, id2) -> {time, data}         # LIKES, FRIEND, AUTHORED
association lists: (id1, atype) -> [assocs, newest-first]

The API is deliberately tiny: get/create/update objects; add/delete associations; assoc_get(id1, atype, id2set), assoc_range(id1, atype, offset, limit) — time-ordered, paginated — and assoc_count(id1, atype). Inverse edges (FRIENDED_BY, LIKED_BY) are maintained as paired writes. No traversal language, no multi-hop queries, no transactions across objects. Friends-of-friends is composed by the application as two rounds of assoc_range — the system's restraint pushes the fan-out where it can be cached, batched, and load-shed per product decision.

The count query deserves its own note: assoc_count exists as a first-class, separately-cached primitive because "4.2M likes" must not cost reading 4.2M rows — precomputed counters maintained on write, the same denormalize-the-aggregate move every feed system makes.

Storage and the two cache tiers

Under the API: MySQL, sharded by object id (shard id embedded in the 64-bit id at creation); an association's row lives on id1's shard, so a node and its outgoing edge lists co-locate. InnoDB provides per-shard durability and ordered scans for assoc_range; the graph semantics live entirely above.

The cache is where the architecture is. Followers and leaders: many follower tiers (per web region/cluster) absorb the billion reads; on miss they consult the leader tier (one per database region), which alone talks to MySQL. Caches are graph-semantic, not byte-blobs — they understand association lists, so assoc_range(user, FRIEND, 0, 50) hits a structured list the cache maintains incrementally on writes rather than invalidating wholesale.

Writes flow up: follower → leader → MySQL, synchronously through the master region for that shard; the leader then feeds updates/invalidations back to its followers (asynchronously). Remote regions hold read replicas + their own leader/follower stacks; a remote write forwards to the master region and — the crucial touch — the originating follower applies the change locally at once. That is how TAO delivers its consistency contract: read-your-writes for the author, eventual (sub-second, typically) for everyone else. Your like appears instantly to you; your friend in Frankfurt may see it 400ms later. For a social graph that asymmetry is not a compromise — it is the requirements, stated precisely (session guarantee for the writer, causal-ish freshness for others).

The hot spot story

Celebrity posts are the adversarial case: millions of reads/sec against one object and one association list. TAO's layers each absorb some: hot objects replicate across many follower tiers (each caching it independently — read amplification becomes the friend it never is at the storage layer); leaders coalesce concurrent misses for the same key into one DB read (request coalescing, again); counters absorb the "how many likes" traffic that would otherwise be a scan. The write side of a viral post — everyone liking it — contends on one counter row, handled by batching increments at the leader. Same hot-key playbook as a distributed cache, executed at graph granularity.

Interview probe	Answer sketch
Why not Neo4j/a graph DB?	Traversal engines optimize the queries this workload never issues, and give up the cache-tiering and shard-locality that the actual workload (1-hop reads at 10⁹/sec) demands
Consistency during region failover?	Master-region writes + async replication = a failover can lose recent writes' visibility ordering; TAO accepts brief anomalies — likes are not ledgers
New edge type with different fanout (follows vs friends)?	Association lists are time-ordered and paginated by design; asymmetric follow graphs work unchanged — celebrity lists are what the hot-spot machinery is for
Would you build TAO today?	Same shape, different parts: the pattern — restricted graph API, semantic caching, per-writer session guarantees over global consistency — outlives the MySQL specifics

The transferable lesson is the method, not the system: start from the query distribution, delete every capability it doesn't need, and spend the freed complexity budget on the two things it does need — cache tiers shaped like the data, and exactly the consistency each reader requires, no more.