Concepts
Social graph cache with leader and followers (TAO)
Intuition
Imagine a huge central archive and thousands of people asking for information all the time, almost always just to look something up. You put several counter clerks who answer from memory what they already know; when they don't know, they don't run to the archive, they ask a single person responsible for that drawer. That person is the only one who goes to the archive and the only one who records changes to that drawer, so there are no lines of people fetching the same thing and no two people changing the same paper at the same time.
How it works
In TAO, the graph is modeled as objects (typed nodes with a 64-bit id) and associations (directed, typed edges identified by id1, atype and id2), and persistent storage remains MySQL, split into logical shards. Each association lives on the shard of its id1, so an association list query (ordered by time, newest to oldest) can be served by a single server. The cache layer implements the graph API and is split into a leader tier and several follower tiers, to avoid huge tiers with hot spots and quadratic all-to-all communication. Clients talk only to followers; on a read miss or on any write, the follower forwards the request to the shard's leader, which is the one that accesses the database. Because all writes for a shard go through a single leader, it serializes concurrent writes and protects the database from thundering herds by limiting overlapping and pending queries. After a write, TAO guarantees eventual delivery of invalidations or refills to all tiers, embedded in the database replication stream, and the client that wrote has read-after-write consistency within its tier because the leader returns a changeset that updates the cache synchronously. This differs from the look-aside memcache used earlier at Facebook, where the control logic lived in clients that do not talk to each other and required patches such as leases to contain stampedes and delayed writes; in TAO this coordination lives inside the cache itself. The price is that TAO does not guarantee atomicity when an association and its inverse land on different shards: a failure can leave an association without its inverse, repaired later by an asynchronous job.
In practice
The design suits read-dominated workloads, in which each page is assembled by pulling data from a graph of objects and edges and accepting momentarily stale data is preferable to being down, as the paper describes for Facebook. Choose it when a simple lookaside key-value cache starts to struggle with edge lists, thundering herds, and control logic scattered across clients, and accept in exchange eventual consistency by default and the possibility of temporarily inconsistent inverse edges.
Use it in a design
Practice the cases that rely on this concept in the System Design school.