Facebook TAO: the cached social graph

01 · CONTEXT

A graph that is read all the time

Each person sees tailored content, and each item goes through privacy checks that take into account who is viewing. Data dependencies are resolved and privacy is checked on every view of the content and, as far as possible, the graph is pulled rather than pushed.

In the paper's measurements, reads dominate and only 0.2% of requests involve a write; TAO sustains a billion reads per second over a mutable dataset of many petabytes.

02 · BEFORE TAO

The lookaside cache and where it failed

Before TAO, web servers accessed MySQL directly to read and write the social graph, using memcache as a lookaside cache. In this design, data mapping and cache invalidation live in frequently deployed client code.

1. The web server accesses MySQL directly and uses memcache as a lookaside cache.

2. Data mapping and cache invalidation are computed in the frequently deployed client code.

3. For an edge list, the key-value cache forces you to fetch the whole list, and changing one edge requires reloading the entire list.

The paper points out fundamental problems with this architecture when the data is a graph. First, edge lists: queries always fetch the entire list and changing a single edge forces it to be reloaded. Second, distributed control logic: it runs on clients that do not communicate with each other, which increases the number of failure modes. Third, expensive read-after-write consistency: Facebook's MySQL uses asynchronous master/slave replication, which is a problem for caches in datacenters that use a replica.

TAO moves the control logic into the cache. It still uses MySQL for persistence, but it mediates access to the database and uses its own cache that understands the graph.

03 · DATA MODEL

Objects and associations

TAO models the graph with objects and associations. Objects are typed nodes and associations are typed, directed edges between objects. Both can hold data as key-value pairs.

At most one association of a given type can exist between two objects. For association types that have an inverse, creations, updates and deletions are automatically coupled to an operation on the inverse association.

Queries are organized as association lists: all associations with the same id1 and atype, in descending order of the time field. The paper observes that, in the social graph, most of the data is old, but many queries ask for the newest subset. Each query has an upper limit per type, typically 6,000, and for longer lists the client must issue several queries.

04 · ARCHITECTURE

Storage, leaders and followers

TAO is split into two cache tiers and a storage tier. Because the volume of data exceeds what fits on a single MySQL server, the data is divided into shards (logical). An association lives on the shard of its id1, so every association query can be served by a single server.

Large cache tiers are more prone to hot spots and suffer quadratic growth of all-to-all connections. The paper splits the cache into two levels, a leader tier and several follower tiers.

1. The client talks to the closest follower and never contacts leaders directly.

2. On a read miss or on a write, the follower forwards the request to a leader.

3. The leader reads and writes the storage tier and does not issue overlapping concurrent queries to the database.

4. After an update, the leader asynchronously queues invalidation messages for the corresponding followers.

Each shard has one leader and all writes for the shard go through it, so this path is naturally consistent. Leaders serialize concurrent writes arriving from followers and, because they mediate all requests for an id1, are well positioned to protect the database from thundering herds.

Shards are mapped to cache servers within a tier using consistent hashing. To balance load among followers, TAO uses shard cloning, in which reads of a shard are served by several followers. In addition, many objects have more than 6,000 associations of the same atype, and so TAO does not cache the complete list.

05 · GEOGRAPHIC SCALE

Several regions, a single graph

TAO is deployed at Facebook as a single geographically distributed instance. The social graph is tightly interconnected and users cannot be grouped so that cross-partition requests are rare. Having full replicas in every datacenter would be prohibitively expensive; the paper's solution is to choose datacenters clustered into a few regions, where internal latency is small (typically under 1 millisecond), and keep one full copy of the graph per region.

Because follower read misses are 25 times more frequent than writes in the paper's workloads, the choice was a master/slave architecture that requires writes to be sent to the master.

1. In the slave region, the follower forwards read misses to the local leader, which queries the local database, whether master or slave. This means read latency is independent of inter-region latency.

2. A write made in the slave region is forwarded by the local leader to the leader of the master database's region.

3. Because TAO writes to MySQL synchronously, the master database is a consistent source of truth.

4. Cache consistency messages are embedded in the database replication stream.

5. The messages are delivered to the region right after the transaction has been replicated to the slave database, and they reach the slave leader; delivering them earlier would create cache inconsistencies.

The master region is controlled separately for each shard and is switched automatically to recover from a database failure. Writes that fail during the switch are reported to the client as failures and are not retried. At Facebook, TAO and memcache use the same pipeline to deliver invalidations.

06 · CONSISTENCY, FAILURES AND NUMBERS

What TAO trades away for availability

TAO provides eventual consistency by asynchronously sending cache maintenance messages from the leader to the followers. In normal operation, with at most one failure per request, it offers read-after-write consistency within a single tier. Replication lag is usually under one second.

The master database is a consistent source of truth because TAO writes to MySQL synchronously. Reads can be marked as critical, and they are then forwarded to the master region.

When facing a failure, TAO routes around the faulty server, preserving availability and performance at the cost of consistency.

In the paper's measurements, the overall read hit rate was 96.4%. Over a 90-day period, the fraction of TAO queries that failed, measured at the web server, was 4.9 × 10⁻⁶, with the caveat that the failure of one query may prevent the client from issuing another. The average write latency was 12.1 ms in the master region and 74.4 ms in the remote region, since writes from other regions include a round trip between regions.