Facebook Social Graph TAO

TAO models the social graph with two primitives: Objects and Associations. An Object has an id, type, and key-value properties — a user object has (name, profile_pic_url, join_date). An Association is a typed, directed edge between two objects with a timestamp and optional data — (user_123, LIKES, post_456, timestamp=...). Associations are stored in association lists sorted by timestamp, enabling efficient queries like 'get the 20 most recent likes on this post.' This fixed data model is deliberately restrictive — by limiting the API to a small set of operations, TAO can optimize aggressively for those specific access patterns.

TAO uses a two-level caching architecture within each geographic region. Follower caches handle the majority of read traffic and are scaled horizontally — adding more follower cache servers linearly increases read throughput. Follower caches forward cache misses and all writes to the leader cache, which is the single source of truth for that region's cache state. The leader cache communicates with the underlying MySQL database for persistent storage. This hierarchy provides read-after-write consistency within a region: a write updates the leader, which invalidates the relevant follower caches synchronously. Users see their own writes immediately.

TAO's persistent storage layer is a massively sharded MySQL deployment. Objects and associations are assigned to shards by object ID using a consistent mapping. Each shard is a MySQL database containing the objects and outgoing associations for its assigned IDs. Association lists are stored in MySQL tables with efficient indexes for the common 'get most recent K associations of type T for object X' query pattern. The MySQL layer handles durability, point-in-time recovery, and schema migrations — while TAO's cache layer absorbs the read volume that would otherwise overwhelm MySQL.

Facebook operates multiple datacenter regions globally. Each region has its own TAO leader and follower caches, and its own MySQL replica. Writes in a region update the local leader and are asynchronously replicated to other regions via MySQL replication. This means cross-region consistency is eventual — a user in Europe might not immediately see a post written by a user in the US. However, TAO provides read-after-write consistency within a region: a user always sees their own recent writes. For critical operations (like accepting a friend request), the write is sent to the primary region to ensure global ordering.

When a celebrity posts and millions of users simultaneously request the same object, a cache miss on a single follower cache could cascade into millions of requests hitting the leader and MySQL. TAO implements thundering herd protection: when a follower cache misses on a key, it marks that key as 'pending' and holds subsequent requests for the same key in a queue. Only one request is forwarded to the leader. When the response arrives, all queued requests are served from the newly cached value. This collapse of concurrent requests is critical for objects with extreme read fanout — without it, a single viral post could overwhelm the storage layer.