How Facebook's TAO Solves Social Graph Scale: Denormalized Associations Over SQL Joins

The Problem: Social Graph Reads Don't Fit Relational Models

When a billion users each have hundreds of friends, pages, and groups, the social graph becomes a massive, sparse network of edges. A News Feed query needs to fetch the latest posts from a user's friends, pages they follow, and groups they belong to—then rank and paginate them. In a traditional relational schema, this means joining across users, friendships, posts, likes, and comments tables, often with ORDER BY created_time DESC LIMIT 20. At Facebook's scale, those joins don't just run slowly; they cannot be sharded efficiently because the join keys (user IDs) scatter across machines.

TAO (The Associations and Objects) replaces that relational model with a denormalized, sharded graph store. The key engineering decision: accept higher write amplification—writing each association twice, once on each endpoint's shard—to make reads single-shard and cache-friendly. This post walks through how that trade-off works in practice, where it breaks down, and how to evaluate whether your workload fits the same pattern.

Associations as First-Class Citizens

TAO stores two primitives: objects (users, pages, posts, photos) and associations (friend, like, tag, member). An association is a directed edge (id1, assoc_type, id2, time) where id1 is the source object, assoc_type encodes the relationship (e.g., friend, like), id2 is the target object, and time provides ordering. The API is intentionally tiny: assoc_add, assoc_delete, assoc_get, obj_get, plus range queries like assoc_range(id1, type, start_time, end_time, limit).

Sharding is deterministic: every object ID maps to a logical shard via shard_id = id % num_shards. Associations live on the shard of id1. This means fetching "all friends of user 123" is a single-shard range scan on shard 123 % N. Fetching "all users who liked post 456" would require scanning the like association on the liker's shards—but Facebook avoids that by also storing a reverse association (liked_by) on the post's shard at write time. That's the write amplification: one user action becomes two assoc_add calls on different shards.

Cache Invalidation Without Distributed Transactions

TAO sits in front of MySQL shards with a two-tier cache: an in-process LRU (local cache) and a shared memcached layer. Writes go to the master MySQL for the shard, then replicate asynchronously to slaves and remote regions. A lightweight invalidation daemon tails the replication binlog and sends cache invalidation messages to memcached. The local cache has no invalidation path—it relies on short TTLs (seconds) and the fact that reads within the same region hit the same memcached pool after a write.

This design gives read-your-writes consistency within a region: after a successful assoc_add, the client's subsequent assoc_get in that region sees the new edge because the write invalidated the relevant memcached keys before returning. Cross-region reads, however, may see stale data for hundreds of milliseconds until replication catches up. Product code must tolerate this or issue a synchronous read to the master region (a "strong read") for critical paths like permission checks.

Worked Example: A "Like" Action Flow

Consider user U=1001 liking post P=5000. The client sends assoc_add(1001, like, 5000, now) to the TAO frontend.

1. Routing: The frontend hashes 1001 to shard S1 and 5000 to shard S2. It issues two parallel assoc_add RPCs: one to S1 for (1001, like, 5000), another to S2 for (5000, liked_by, 1001).
2. Write path: Each shard's master MySQL inserts the row, commits, and returns success. The invalidation daemon on each shard sees the binlog entry and broadcasts DELETE for the affected association keys in memcached.
3. Read path: When U=1001 refreshes their profile, assoc_range(1001, like, ..., limit=20) hits shard S1. The local cache misses, memcached misses (invalidated), so TAO reads from the local MySQL slave (which has the write via fast replication) and populates both caches.
4. Cross-region: A viewer in another region querying assoc_range(5000, liked_by, ...) on shard S2 might not see the new like until replication delivers the binlog to their region's slave and the invalidation daemon runs there.

If the second assoc_add (the reverse edge) fails, the system has a dangling forward edge. TAO doesn't roll back the first write—there's no distributed transaction. Instead, a background reconciler scans for orphaned associations and repairs them. Application code must also be idempotent: retrying assoc_add with the same (id1, type, id2) is a no-op because the primary key enforces uniqueness.

Trade-offs and Limitations

• No multi-object transactions: You cannot atomically "create a group and add 50 members." Each assoc_add is independent. Product code uses compensating actions (delete on failure) and idempotency keys.
• Write amplification: Every mutual relationship (friend, group member) stores two edges. At Facebook's scale, this doubles write QPS but eliminates fan-out reads.
• Cache staleness under load: If the invalidation daemon lags (e.g., during a binlog backlog), memcached serves stale data longer than the typical <100ms target. Monitoring daemon lag is operational table stakes.
• Schema rigidity: Association types are registered centrally. Adding a new edge type requires a config push, not a schema migration, but you can't ad-hoc query arbitrary predicates like "friends who live in Seattle" without a separate index.

Evaluating the Pattern for Your System

TAO's model fits when: (1) your read patterns are predictable edge traversals from a known source object, (2) you can tolerate eventual consistency across regions, (3) write volume is high but each write touches few edges, and (4) you can invest in idempotent application logic. It fits poorly when: you need ad-hoc multi-hop queries, strong consistency across entities, or low write amplification.

To test the pattern without building a distributed store, run the open-source TAO Bench workload generator against a local MySQL + memcached setup. Configure it with your object/association cardinalities and measure p99 latency for assoc_range under your target QPS. If single-shard reads stay under your SLO while write amplification stays within your budget, the denormalized association model is worth a deeper prototype.

Start by mapping your hottest query to an assoc_range call. If you can express it as "get edges of type X from object Y ordered by time," TAO's sharding and caching will likely serve it well. If you need "get all objects of type Z connected to Y via any path," look elsewhere—graph databases with native traversal or materialized views may suit better.