Skip to content
TAO: Facebook's Distributed Data Store for the Social Graph 4 min

Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, Venkat Venkataramani · USENIX ATC 2013

TAO: Facebook's Distributed Data Store for the Social Graph

How Facebook serves its social graph: typed objects and edges behind a leader and follower cache. Write in one tier and read a stale value from another.

Read the original paper

Systems & Distributed · Yellow Belt · Pro · 4 min read

TAO: Facebook's Distributed Data Store for the Social Graph

Open Facebook and look at your feed. Behind each post is a web of small facts: who wrote it, who liked it, who commented, who is friends with whom. Showing one page means reading hundreds of these facts, and doing it for over a billion people at once. The data changes all the time, but it is read far more often than it is written.

TAO is the system Facebook built to serve this social graph. Its 2013 paper describes a simple data model, an API for it, and a layered cache that favors availability and efficiency over strong consistency. It is a classic example of a read-heavy system design.

TAO stores a graph of typed objects and typed associations in MySQL, and puts a two layer cache in front of it. Web servers read from follower caches, which fall back to leader caches and then to the database. Writes go through the leader, which sends invalidations to other caches. Reads are fast and always available, at the price of data that can be briefly out of date in another region.

Two kinds of things

TAO's data model has objects and associations. An object is a typed node with a unique id, such as a user, a post or a place. An association is a typed, directed edge between two objects, such as friend or authored, with a time.

TAO's data model has just two things: typed objects and typed, directed associations between them. Many edges come with an inverse, such as a friend in each direction.

Queries start from an object and an association type. Because the same question is asked constantly, such as "the latest 50 comments on this post", TAO organizes edges into association lists: all associations with the same starting object and type, sorted by time with the newest first. That makes "newest first" reads cheap.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

2 more sections, 1 more diagram and 2 interactive elements to play with

  • A cache that is the front door
  • Why trade consistency for availability?

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.