TAO: Facebook’s Distributed Data Store for the Social Graph
📜 Abstract
We introduce a simple data model and API tailored for serving the social graph, and TAO, an implementation of this model. TAO is a geographically distributed data store that provides efficient and timely access to the social graph for Facebook’s demanding workload using a fixed set of queries. It is deployed at Facebook, replacing memcache for many data types that fit its model. The system runs on thousands of machines, is widely distributed, and provides access to many petabytes of data. TAO can process a billion reads and millions of writes each second.
✨ Summary
Paper summary
TAO is a geographically distributed, read-optimized data store designed to serve Facebook’s highly customized social-graph workload. It replaces application-managed look-aside caching for suitable data types while retaining MySQL as the persistent storage layer. The system exposes a deliberately restricted graph model consisting of typed objects and directed associations, together with APIs for object operations and association-list queries such as counts, ranges, time ranges, additions, deletions, and type changes.
The architecture separates persistent storage from graph-aware caching. Data is partitioned into logical shards, with objects assigned permanently to shards and associations stored according to their source object. Within each region, leader caches coordinate access to databases and serialize writes, while follower tiers serve clients and scale read throughput. Multiple geographic regions maintain complete copies of the graph through asynchronous master/slave replication. This design keeps reads local to a region while sending writes to the region that masters each shard.
TAO favors availability, read performance, and machine efficiency over strong consistency. Its normal consistency model is eventual consistency, with read-after-write consistency generally provided within a single follower tier. Cache invalidation and refill messages propagate asynchronously, while version numbers, repair jobs, failover mechanisms, shard cloning, and client-side caching address races, failures, and hot objects. Critical reads can be routed to the master region when stronger freshness is required.
The production workload is overwhelmingly read-oriented: in the reported sample, reads accounted for 99.8% of API requests, the overall read cache hit rate was 96.4%, and replication lag was below one second for 85% of the tracing period. The deployment processed approximately one billion reads and millions of writes per second over many petabytes, demonstrating that a constrained data model combined with hierarchical caching and relaxed consistency could support web-scale social-graph serving.
Influence
The clearest documented follow-on is RAMP-TAO, which explicitly builds on TAO to add atomic-visibility and read-transaction guarantees without redesigning the underlying highly available, read-optimized store. The follow-on work reports that partial transactional updates occurred in approximately 1 in 1,500 batched reads and presents a protocol with 0.42% memory overhead, while allowing more than 99.9% of reads to complete in one local-cache round trip. (engineering.fb.com)
RAMP-TAO demonstrates a direct research and engineering influence: TAO’s original separation of caching, replication, and consistency concerns became the foundation for layering stronger guarantees selectively, rather than imposing transactional overhead on all workloads. Meta described this approach as applicable beyond TAO to other large-scale, read-optimized systems. (engineering.fb.com)
The original paper was published as a USENIX ATC 2013 conference paper in June 2013, with the bibliographic details and author list confirmed by USENIX. (usenix.org)