Created: 2026-11-13 Updated: 2026-11-14 5 min read

TAO: facebook’s distributed data store for the social graph

tao

https://drive.google.com/file/d/1XuSkqQ8oRrUmKRoKtc3J8CVfs_P-LC3p/view?usp=sharing

paper year

2013

thoughts

This is the sequel to the memcache paper I covered last time, so this one will be super short. At the end of that post I said memcache doesn’t know anything about the social graph. It’s a plain key-value store, so friendships, likes, comments and check-ins all get stored as opaque blobs, and the PHP code on the web servers has to manage them. TAO (The Associations and Objects) is how Facebook fixed that. It’s what happens to a system once you understand your workload even better.

Why facebook needed this update if memcached works out of the box? With memcache as a look-aside cache, all the graph logic lived in the application. Say you add a comment to a post. The post’s list of comments is one cached value. You write to MySQL, delete the whole list from memcache, and the next read refetches the entire list from the database. For a hot post with thousands of comments, that’s a lot of wasted work for one tiny change. Lots of different clients doing read-modify-write on the same keys also leads to races, and every product team had to get this right on their own. The data was a graph, but nothing in the stack treated it like one.

facebook nailed their datamodel which helped them to optimize around their datamodel. TAO has just two things: objects (nodes, like a user, a post or a photo) and associations (edges, like “Alice liked this post”). An association is (id1, type, id2, time, data), and the edges going out of an object for a given type are kept as a list sorted by time, newest first. The API is small and built around how Facebook actually reads: give me the latest 50 comments on this post, how many likes does this have, did this person like this. Most of the time you only need the recent items or a count, never the whole list. assoc_count alone saves fetching thousands of edges just to show “1.2K likes”.

Here’s the same post stored both ways, and what happens when one new comment comes in:

json vs graph

Because the cache understands edge lists, a new comment just gets prepended to the cached list and the count goes up by one. The memcache paper deleted instead of updating because deletes are idempotent. TAO can update in place because it owns the data model and every write goes through it. That leads to the main difference between the two designs.

memcache vs tao

Read-through and write-through, not look-aside. In memcache, the web server glued everything together. On a read it checked memcache, and on a miss it went to MySQL itself and set the value back. On a write it updated MySQL and then deleted the key. The cache just sat on the side and had no idea what the data meant. That caused a few problems:

In TAO, the client never sees the database. On a read, you ask TAO, and TAO either answers from its cache or fetches from MySQL and fills the cache itself (read-through). On a write, you send it to TAO, and TAO writes to MySQL and updates its own cache in the same path (write-through). Since every write passes through the cache, the cache knows exactly what changed and can apply that change in place instead of throwing the whole value away. And since only TAO puts values into the cache, the racing clients are gone. The consistency logic lives in one place instead of in every product’s code.

Leaders and followers. The cache is also split into two tiers. The easy way to scale a cache is to add more servers to one big tier. But then every web server has to talk to every cache server, the number of connections explodes (this is what mcrouter was fighting in memcache), and a hot key still sends a flood of misses straight to the database.

So TAO has followers and leaders. Web servers only talk to followers, and there are many follower tiers, each serving its own group of web servers. Followers answer reads from their cache. On a miss or a write, the follower forwards the request to the leader for that shard, and the leader is the only thing that ever talks to MySQL. This solves several problems from memcache:

Sharding by object id. The shard id is embedded inside the object id, and an association lives on the shard of id1. So all likes on this post is a single-shard lookup, no scatter-gather.

Still the same at heart. The cache and persistent storage are still decoupled. MySQL is still the source of truth, regions still have a master and replicas, and writes from a replica region still get forwarded to the master. It’s still eventually consistent, and they’re still fine with that because the workload is about 99.8% reads. They give read-after-write consistency within a tier so users see their own writes, and if a request really needs fresh data, it can be marked critical and go to the master.

they looked at what the newsfeed actually queries and built only that. It’s the same lesson as memcache, taken further: once you understand your workload deeply, you can bake it into the data model itself, and a lot of the hacks from the previous design just disappear.