Facebook TAO Explained: Objects, Associations and Leader-Follower Caching

A plain key-value cache stores one value under one name, the key. It keeps each list of links as one blob, so every new like or comment throws the whole list away. Many web servers then find nothing in the cache at once and all rebuild it from the database. Facebook TAO was built to avoid this.

Picture a common setup. A campus social app keeps posts, comments and likes in MySQL, a popular open-source database, with a key-value cache in front. The setup is made up, but each problem below is described in the TAO paper.

A popular notice about hostel wifi has 3,000 comments (made up). The app caches the comment list under one key. When a new comment arrives, the app deletes that key, and the next reader reloads all 3,000 rows to see one new one.

Facebook hit the same problems before TAO existed. Its web servers read and wrote the graph in MySQL and used memcache, a key-value cache, beside it. The 2013 TAO paper lists three problems with that design.

• Edge lists fit badly. A key-value cache has no idea a value is a list, so changing one edge means reloading the whole list.
• Control logic was spread across clients. Web servers did not talk to each other, so avoiding a thundering herd was hard. A thundering herd is many clients missing the cache and hitting the database together.
• Reading your own write was expensive. MySQL copies changes to other regions after a delay, so a user could post and then not see the post. The fix was to mark recently changed keys and send reads for them to the distant region holding the main copy.

TAO answers all three by making the cache understand graphs and by giving each piece of data a single owner. The rest of this guide shows how, and what that choice cost.

You need eight words. Each is tied to the hostel wifi post.

• Social graph: all the people and things in an app, plus the links between them. The post, its author and its comments are part of it.
• Cache: a fast copy of data kept in memory. A hit means the cache had the answer; a miss means it had to ask the slower database.
• Lookaside cache: a cache that the app checks first and fills by itself after a miss. The cache never talks to the database on its own.
• Shard: one slice of a big database. Each shard lives on one database server, and one server can hold many shards.
• Master and slave: the TAO paper's words for the main copy of a database that takes writes and the copies that follow it. Many teams now say primary and replica.
• Replication lag: the delay before a change on the master shows up on a slave copy.
• Eventual consistency: copies may disagree for a while, but if writes stop, they all end up the same.
• Read-after-write consistency: once you write something, your own next read shows it.

Facebook TAO is a graph-aware cache and data service that sits between the web servers of Facebook, now Meta, and MySQL. It was described at the USENIX Annual Technical Conference in June 2013, in a paper by fifteen authors from Facebook.

The paper's abstract says TAO was deployed at Facebook, replacing memcache for many data types that fit its model. MySQL stayed underneath as the place where data is stored for good. The SevyDevy guide on scaling memcache covers the memcache layer that TAO replaced for those data types.

TAO is read-optimised. A Facebook page, the paper says, commonly queries hundreds of objects and associations while it renders. Writes are rare by comparison, so the whole design spends effort to make reads cheap.

The paper also sets a clear limit. Its goal was not to support a complete set of graph queries. TAO answers a fixed set of simple questions very fast, and apps build anything fancier on top.

An object is a thing with an id, a type and some fields. An association is a one-way, typed link from one object to another, with a time and optional fields. Together they form the whole graph.

In the paper's notation, an object maps (id) to (otype, key-value pairs). An association maps (id1, atype, id2) to (time, key-value pairs). Here otype and atype just mean object type and association type.

• Object ids are 64-bit integers, unique across every object type. A user, a post and a comment never share an id.
• At most one association of a given type can exist between any two objects. A user can like a post once, which fits a LIKES link.
• Each association has a 32-bit time field, an integer the app sets. Many associations use their creation time, and the paper calls the field central to queries.
• Repeatable actions become objects. A comment is an object, because one user can comment many times. A like is only an association.

Many links run both ways. TAO lets you configure an inverse type, so adding AUTHORED from a user to a post also adds AUTHORED_BY from the post back. A symmetric type such as FRIEND is its own inverse.

The paper stresses one detail. Writes to a link and its inverse can touch two shards, and TAO does not make the pair atomic, meaning all-or-nothing. A failure can leave a one-sided link, which a background job repairs later.

Three write calls and four query calls cover associations, plus simple object calls to add, get, update and delete. The paper writes the names with spaces; the underscores here are the common spelling.

Meta's 2013 engineering post says TAO offers no operations for complex traversals (walking many hops across the graph) or pattern matching. It has no server-side set intersection (finding ids common to two lists) either. A client library builds one from simple lookups and list reads instead.

The object API also leaves something out. It has no compare-and-set, an update that succeeds only if the value has not changed. The paper says eventual consistency makes such a check much less useful.

Every association list is kept sorted by its time field in descending order. So position 0 is always the newest link, and assoc_range simply slices from pos for limit items.

This matches how people read feeds. The paper calls it creation-time locality: most data is old, but many queries ask for the newest part. Caching the front of each list therefore serves most reads.

The paper adds that TAO caches only contiguous prefixes of association lists, meaning the front part with no gaps. An app pages further with a larger pos, or with a time bound in assoc_time_range.

• Large lists are paged. TAO enforces a per-type upper bound on limit, typically 6,000, according to the paper.
• Counts are cheap. TAO keeps association counts as their own cache entries, and in MySQL in a separate table, so a count does not scan the list.
• Empty answers are cheap too. The paper notes that a cached count of zero is enough to answer a range query without asking anyone.
• Very busy objects are special. Many objects had more than 6,000 links of one type, so TAO does not cache their complete lists.

In the 2013 trace, assoc_range was the most common read, 40.9% of all reads. Only 31.0% of those calls returned anything, and 45% of assoc_count calls returned zero. Empty lists are normal in a social graph.

Clients read from the nearest follower tier, and every write goes through the single leader that owns the shard. A tier is a set of cache servers that together can answer any TAO query.

Each shard is hosted by one leader, and all writes to that shard go through it. Followers forward read misses and writes to the leader. The paper says clients never contact leaders directly.

In normal operation, the leader is the only part that reads and writes MySQL for its shards. Because every miss for a shard meets in one place, it can put simultaneous writes in a single order and avoid overlapping database queries.

If a leader fails, the paper says followers send read misses straight to the database and reroute writes to another member of the leader's tier.

That single owner fixes the second old problem. The paper says the leader is ideally positioned to protect the database from thundering herds, and it caps the queries pending on each shard.

Why not one giant tier? The paper says very large tiers suffer quadratic growth in all-to-all connections. If every client talks to every server, doubling both roughly quadruples the connections. Many smaller follower tiers avoid that.

An everyday picture helps. Think of a college with notice boards in every hostel and one registrar's office. Students read the board in their own hostel, which is the follower tier.

To change anything, a student goes to the registrar, which is the leader. The registrar updates the official register, which is MySQL, then sends runners to update every hostel board.

The student's own board is updated before they leave the office, so they see their change at once. Students in other hostels see it only when the runner arrives.

Where the picture breaks: a real follower keeps only popular items, evicting the least recently used ones. A runner for an item the board no longer holds has nothing to do.

The write goes through the follower to the leader, the leader writes MySQL, and the reply updates caches on the way back. Meta's 2013 engineering post calls this a write-through cache; the paper describes it without that name.

1. 1

   Client sends the write

   The web server calls assoc_add or obj_update on its nearest follower tier, never on the leader.

2. 2

   Follower forwards it

   The follower passes the write to the leader that owns the shard of the object's id, or of id1 for a link.

3. 3

   Leader writes MySQL

   The leader writes the row to its shard and updates its own cache. A version number stored with the data goes up by one.

4. 4

   Writing tier updates at once

   The leader's reply carries the change, which the paper calls a changeset. The follower that sent the write applies it before answering the client.

5. 5

   Other tiers update later

   The leader asynchronously sends the follower tiers an invalidation for an object or a refill for a list. Asynchronously means the write does not wait for them.

Objects and lists get different messages for a reason. Invalidating an object just drops it, and the next read fetches it again. Dropping a list would throw away many cached edges to change one.

So for a list the leader sends a refill. A follower that holds the list asks the leader for the updated list, and a follower that does not hold it ignores the message.

The paper says a version number in each message lets a follower ignore it when it arrives late. In our toy, a follower ignores a message for a version it already holds or has passed.

In the 2013 design, Facebook TAO is eventually consistent. After a write, the paper says TAO guarantees an invalidation or refill eventually reaches every tier, and replication lag is usually under one second.

On top of that, the 2013 design gives read-after-write consistency within a single tier. Its scope is exact: in normal operation, meaning a request meets at most one failure, the tier that sent a write shows it on the next read.

Other tiers can serve the old value until their message arrives. The paper notes that a user who keeps using the same follower tier will typically see a consistent view.

• Failover, switching to another tier when one fails, can break it. If a read fails over before that tier's message arrives, the paper says read-after-write can be violated.
• Critical reads exist for this. A read marked critical goes to the master region, the one region whose database takes writes for that data. The paper's example is authentication, where replication lag must not expose stale credentials.
• Version numbers stay inside TAO. The paper says they are not exposed to clients, so an app cannot ask for a specific version.

The script below models one leader, two follower tiers and one shard, using only the Python standard library. It is not TAO's code; it follows the paper's design closely enough to watch the messages work.

To keep it short, the toy leader reads its own dictionary as if it were MySQL. A real leader is also a cache in front of MySQL, and real followers cache counts separately instead of counting the list.

# tao_sim.py: a toy model of TAO's leader and follower cache tiers.
# One region, one shard. Not TAO's code; it follows the 2013 paper's design.
from collections import deque


class Leader:
    """Owns the shard: every write goes through here to storage."""

    def __init__(self):
        self.objects = {}        # stands in for MySQL: id: (version, data)
        self.assocs = {}         # (id1, atype): {id2: time}
        self.followers = []
        self.outbox = deque()    # cache messages, sent later (asynchronously)
        self.next_id = 1

    def obj_add(self, data):
        oid, self.next_id = self.next_id, self.next_id + 1
        self.objects[oid] = (1, data)
        return oid

    def obj_get(self, oid):
        return self.objects.get(oid)

    def assoc_list(self, id1, atype):
        edges = self.assocs.get((id1, atype), {})
        return sorted(edges.items(), key=lambda e: -e[1])   # newest first

    def obj_update(self, oid, data):
        version = self.objects[oid][0] + 1
        self.objects[oid] = (version, data)
        for f in self.followers:
            self.outbox.append((f, "invalidate", oid, version))
        return (version, data)   # the changeset for the writing tier

    def assoc_add(self, id1, atype, id2, time):
        self.assocs.setdefault((id1, atype), {})[id2] = time
        for f in self.followers:
            self.outbox.append((f, "refill", (id1, atype), None))
        return self.assoc_list(id1, atype)

    def deliver_all(self):
        while self.outbox:
            f, kind, key, version = self.outbox.popleft()
            f.on_message(kind, key, version)


class Follower:
    """One follower tier: clients read here; misses and writes go to the leader."""

    def __init__(self, name, leader):
        self.name, self.leader = name, leader
        self.objects, self.lists = {}, {}
        leader.followers.append(self)

    def obj_get(self, oid):
        if oid not in self.objects:          # cache miss: ask the leader
            self.objects[oid] = self.leader.obj_get(oid)
        return self.objects[oid]

    def assoc_range(self, id1, atype, pos, limit):
        key = (id1, atype)
        if key not in self.lists:
            self.lists[key] = self.leader.assoc_list(id1, atype)
        return self.lists[key][pos:pos + limit]

    def assoc_count(self, id1, atype):
        self.assoc_range(id1, atype, 0, 0)   # make sure the list is cached
        return len(self.lists[(id1, atype)])  # real TAO caches counts separately

    def obj_update(self, oid, data):
        self.objects[oid] = self.leader.obj_update(oid, data)   # applied now

    def assoc_add(self, id1, atype, id2, time):
        self.lists[(id1, atype)] = self.leader.assoc_add(id1, atype, id2, time)

    def on_message(self, kind, key, version):
        if kind == "invalidate":
            cached = self.objects.get(key)
            if cached and max(cached[0], version) == cached[0]:
                print(f"  {self.name}: ignores invalidate v{version}, holds v{cached[0]}")
            else:
                self.objects.pop(key, None)
                print(f"  {self.name}: drops object {key}")
        elif kind == "refill" and key in self.lists:
            self.lists[key] = self.leader.assoc_list(*key)
            print(f"  {self.name}: refills list {key}")


leader = Leader()
post = leader.obj_add("Hostel wifi down tonight")
for cid, t in [(101, 1000), (102, 1060), (103, 1120)]:   # comment ids, times
    leader.assoc_add(post, "COMMENT", cid, t)
tier_a, tier_b = Follower("tier A", leader), Follower("tier B", leader)

for tier in (tier_a, tier_b):        # both tiers warm their caches
    tier.obj_get(post), tier.assoc_range(post, "COMMENT", 0, 2)

print("1. A user on tier A edits the post and adds a comment")
tier_a.obj_update(post, "Hostel wifi back at 11 pm")
tier_a.assoc_add(post, "COMMENT", 104, 1180)
for tier in (tier_a, tier_b):
    print(f"   {tier.name}: {tier.obj_get(post)}",
          tier.assoc_range(post, "COMMENT", 0, 2),
          "count", tier.assoc_count(post, "COMMENT"))

print(f"2. Leader delivers {len(leader.outbox)} queued messages")
leader.deliver_all()
for tier in (tier_a, tier_b):
    print(f"   {tier.name}: {tier.obj_get(post)}",
          tier.assoc_range(post, "COMMENT", 0, 2),
          "count", tier.assoc_count(post, "COMMENT"))

print("3. Next page, assoc_range(post, COMMENT, pos=2, limit=2):",
      tier_b.assoc_range(post, "COMMENT", 2, 2))

Pause and predict: a user on tier A edits the post and adds comment 104. Before any message is delivered, what does a reader on tier B see? Guess before reading the output.

Run it with python3 tao_sim.py. On Python 3.13.17, which we used, it prints exactly this:

1. A user on tier A edits the post and adds a comment
   tier A: (2, 'Hostel wifi back at 11 pm') [(104, 1180), (103, 1120)] count 4
   tier B: (1, 'Hostel wifi down tonight') [(103, 1120), (102, 1060)] count 3
2. Leader delivers 4 queued messages
  tier A: ignores invalidate v2, holds v2
  tier B: drops object 1
  tier A: refills list (1, 'COMMENT')
  tier B: refills list (1, 'COMMENT')
   tier A: (2, 'Hostel wifi back at 11 pm') [(104, 1180), (103, 1120)] count 4
   tier B: (2, 'Hostel wifi back at 11 pm') [(104, 1180), (103, 1120)] count 4
3. Next page, assoc_range(post, COMMENT, pos=2, limit=2): [(102, 1060), (101, 1000)]

What just happened? Right after the write, tier A shows version 2 and four comments, because it applied the leader's changeset. Tier B still shows version 1 and three comments: a stale read.

Then four queued messages arrive, two per tier. Tier A ignores the invalidation for version 2, because it already holds version 2. Tier B drops the old post, and both tiers refill the comment list from the leader.

Finally, assoc_range with pos 2 and limit 2 returns the two oldest comments, 102 and 101. Paging walks back in time because the list is kept newest first.

Try one change to check your understanding. Remove the version check in on_message and run again: tier A now drops its fresh copy and must refetch it. The answer stays correct, but the cache does extra work.

Each region keeps a full copy of the graph and reads locally, but each shard takes writes in only one region, its master region. Leaders in other regions forward writes there.

The paper explains the trade with one number from its 2013 workload. Read misses by followers were 25 times as frequent as writes, so sending writes far away and keeping reads local was the cheaper choice.

• The paper groups data centres into a few regions, with latency inside a region typically under 1 millisecond.
• Each region, in the production deployment the paper describes, had one complete set of databases, one leader cache tier and at least two follower tiers.
• Leaders read their own region's database, whether it is the master or a slave copy.
• A slave region's leader forwards writes to the master region's leader. If the write succeeds, the local leader updates its cache with the fresh value.
• The master region is chosen per shard and switches automatically if a database fails. Writes that fail during the switch are reported as failed, not retried.

The clever part is timing. TAO embeds its invalidation and refill messages in the MySQL replication stream. In a slave region, they are delivered right after its database applies the change.

The paper says earlier delivery would create cache inconsistencies, because reading from the local database would give stale data. Followers can get two messages for one write: one when it succeeds and one after replication.

Running a two-region toy

The second script adds a master region, a slave region with two follower tiers, a replication log and a critical read. Like the first, it is our model of the paper, not TAO code.

# tao_regions.py: a toy model of TAO across a master and a slave region.
# Not TAO's code; it follows the design in the 2013 USENIX ATC paper.
replication_log = []   # MySQL changes waiting to reach the slave database
async_msgs = []        # master-region cache messages, sent asynchronously


class Database:
    def __init__(self, name):
        self.name, self.rows = name, {}   # id: (version, data)


class RegionLeader:
    def __init__(self, name, db, master=None):
        self.name, self.db, self.master = name, db, master
        self.cache, self.followers = {}, []

    def read(self, oid):
        if oid not in self.cache:          # miss: read the LOCAL database copy
            self.cache[oid] = self.db.rows.get(oid)
        return self.cache[oid]

    def write(self, oid, data):
        if self.master:                    # slave region: forward to master leader
            change = self.master.write(oid, data)
        else:
            version = self.db.rows.get(oid, (0, None))[0] + 1
            change = self.db.rows[oid] = (version, data)
            replication_log.append((oid, change))
            async_msgs.extend((f, oid, version) for f in self.followers)
        self.cache[oid] = change           # a leader keeps the fresh value
        return change

    def invalidate(self, oid, version):
        cached = self.cache.get(oid)
        if not (cached and max(cached[0], version) == cached[0]):
            self.cache.pop(oid, None)


class FollowerTier(RegionLeader):
    def __init__(self, name, leader):
        super().__init__(name, None)
        self.leader = leader
        leader.followers.append(self)

    def read(self, oid):
        if oid not in self.cache:          # miss: ask this region's leader
            self.cache[oid] = self.leader.read(oid)
        return self.cache[oid]

    def write(self, oid, data):
        self.cache[oid] = self.leader.write(oid, data)   # changeset applied now

    def critical_read(self, oid):          # proxied to the master region
        return (self.leader.master or self.leader).read(oid)


def replicate(slave_db, slave_leader):
    """MySQL replication catches up; cache messages ride along with it."""
    while replication_log:
        oid, change = replication_log.pop(0)
        slave_db.rows[oid] = change
        for node in [slave_leader] + slave_leader.followers:
            node.invalidate(oid, change[0])


def show(label, *tiers):
    print(label)
    for t in tiers:
        print(f"   {t.name}: {t.read(1)}")


master_db, slave_db = Database("master"), Database("slave")
master_leader = RegionLeader("master leader", master_db)
slave_leader = RegionLeader("slave leader", slave_db, master=master_leader)
tier_m = FollowerTier("master-region tier", master_leader)
tier_s1 = FollowerTier("slave tier S1", slave_leader)
tier_s2 = FollowerTier("slave tier S2", slave_leader)

tier_m.write(1, "Hostel wifi down tonight")
replicate(slave_db, slave_leader)
async_msgs.clear()                         # setup done
show("0. Everyone has version 1", tier_m, tier_s1, tier_s2)

tier_s1.write(1, "Hostel wifi back at 11 pm")   # a user in the slave region
show("1. Write from slave tier S1, replication not done yet",
     tier_s1, tier_s2, tier_m)

for f, oid, v in async_msgs:
    f.invalidate(oid, v)
async_msgs.clear()
show("2. Master region's async invalidations arrive", tier_m)

tier_s1.cache.clear(), slave_leader.cache.clear()   # memory pressure: evicted
show("3. S1 and its leader evict the post, then S1 reads again", tier_s1)
print(f"   critical read from S1: {tier_s1.critical_read(1)}")

replicate(slave_db, slave_leader)
show("4. Replication catches up; messages ride along", tier_s1, tier_s2)

It prints the following on Python 3.13.17:

0. Everyone has version 1
   master-region tier: (1, 'Hostel wifi down tonight')
   slave tier S1: (1, 'Hostel wifi down tonight')
   slave tier S2: (1, 'Hostel wifi down tonight')
1. Write from slave tier S1, replication not done yet
   slave tier S1: (2, 'Hostel wifi back at 11 pm')
   slave tier S2: (1, 'Hostel wifi down tonight')
   master-region tier: (1, 'Hostel wifi down tonight')
2. Master region's async invalidations arrive
   master-region tier: (2, 'Hostel wifi back at 11 pm')
3. S1 and its leader evict the post, then S1 reads again
   slave tier S1: (1, 'Hostel wifi down tonight')
   critical read from S1: (2, 'Hostel wifi back at 11 pm')
4. Replication catches up; messages ride along
   slave tier S1: (2, 'Hostel wifi back at 11 pm')
   slave tier S2: (2, 'Hostel wifi back at 11 pm')

What just happened? Step 3 is the surprising one. The paper calls it rare, because the slave database must lag longer than it takes the cache to evict a fresh entry. The toy forces both by clearing the caches by hand.

TAO gave up strong consistency, rich queries and several safety features most databases offer. Each loss is written down in the 2013 paper or Meta's 2013 post.

• Strong consistency: other tiers and regions can serve old data for a while, usually under a second of replication lag.
• Compare-and-set: there is no conditional update, so in effect two writers doing read-modify-write on the same object can lose one of the updates.
• Atomic inverse links: a link and its inverse can live on two shards, and a failure between them leaves a one-sided link until a background job fixes it.
• General queries: only a fixed set of calls, so no SQL-style joins, no complex traversals and no server-side intersections. The paper says TAO did not support an advanced graph processing API.
• Full lists for huge objects: for objects with more than 6,000 links of one type, TAO does not cache the whole list, so some queries go to the database.
• Guaranteed write success: writes that fail during a master database switch are returned as failures and not retried by TAO.

Some of these were later revisited. A 2021 paper on RAMP-TAO says TAO had added failure-atomic write transactions across shards. It also measured fractured reads, where a batch sees only part of a transaction, in 1 of every 1,500 read batches.

A 2020 paper on FlightTracker says TAO originally provided read-your-writes through write-through caching, and that scaling challenges led to a new implementation. FlightTracker is a family of APIs and systems that, per that paper, managed consistency for online access to Facebook's graph.

When the trade is worth copying

Copy the shape when reads dwarf writes, data is a graph of small items, and a second of staleness is harmless. Feeds, comment lists, follower counts and notification lists fit this well.

Avoid it when a stale read costs money or safety. Bank balances, seat bookings and stock counts need conditional writes and stronger guarantees. TAO itself keeps critical reads for such moments.

They describe one sampled workload in 2013, not TAO today. Read them as proportions that explain design choices, not as targets for your system.

The 99th percentile means 99 of every 100 requests took that long or less. The paper also reports that the failover path was used on 0.15% of follower cache misses.

Do not compare these numbers with your own cache without the context. The paper measured 2013 follower servers with 144 GB of RAM and two 8-core CPUs, and Facebook's own mix of queries.

Start with the workload, then the data model, then the two tiers, then the consistency trade. Interviewers usually want to hear why each choice follows from reads vastly outnumbering writes.

1. 1

   State the workload

   A social feed reads hundreds of small items per page and writes rarely. In the 2013 paper, only 0.2% of requests were writes.

2. 2

   Name the data model

   Objects with 64-bit ids, and typed, timed associations between them. Lists are kept newest first, so assoc_range is a slice and assoc_count is a stored number.

3. 3

   Draw the tiers

   Clients read from follower tiers; each shard has one leader that writes to MySQL and serialises writes. Explain how a single owner protects the database from thundering herds.

4. 4

   Walk one write

   Follower to leader to MySQL, a changeset back to the writer's tier, and asynchronous invalidations or refills, with version numbers, to the others.

5. 5

   Go multi-region

   Each region has a full copy and reads locally. Writes go to the shard's master region, and cache messages ride the replication stream.

6. 6

   Say what you give up

   Eventual consistency across tiers, no compare-and-set, non-atomic inverse links and a fixed query set. Offer critical reads for login-like paths.