Facebook: the social graph, TAO and memcache at planet scale
In June 2026 Meta reported 3.6 billion people using at least one of its apps every day, and its graph store, TAO, was serving over ten billion reads a second back in 2021. This lesson shows how that is built from parts you already know: MySQL, a look-aside cache, sharding and replication, plus a few clever fixes for the problems that only appear when a cache is that big.
By the end you can
- Model a social product as objects and associations, and say why that fits a cache
- Trace a read and a write through TAO's caches and MySQL shards, across regions
- Explain memcache leases: how they stop stale sets and thundering herds
- Explain why invalidations come from the database's commit log, not from the web server
- Build an objects and associations schema in Postgres and a Redis cache with leases
The everyday picture
Picture the noticeboard at a big office. Every staff member has a small card: name, team, phone. String connects the cards: who reports to whom, who is in which WhatsApp group, who liked the canteen post. Almost everyone comes to read the board. Only a few people change it each hour.
The real records live in the HR office's files. Reading those files is slow, so the office keeps a photocopy of the board on every floor. That raises two questions. When someone changes a card in the HR file, how does every floor's copy learn about it? And when the copy on floor 5 is torn down for an update, how do you stop 200 people from all running to the HR office at once to ask for the same card? Facebook's data layer is the answer to those two questions, at the scale of billions of people.
What the product must do
Functional: people, pages, posts, photos, comments and check-ins, with connections between them (friend of, likes, authored, tagged in, commented on). A news feed or profile page is built by reading hundreds of these small pieces and their connections.
Non-functional, the ones that shape the design:
- Reads dominate. The 2013 memcache paper says users consume an order of magnitude more content than they create. In the 2013 TAO paper, 99.8% of requests were reads.
- Each page touches many items. One popular page fetched 521 distinct items from memcache on average (2013).
- Low latency everywhere in the world, so data must be copied to several regions.
- Seeing your own action matters more than global order. After you comment, you must see your comment. A friend in another country seeing it one second later is fine. This is read-after-write consistency for the writer, and eventual consistency for everyone else (CAP and consistency).
Scale in numbers
| Metric | Number | Source, year |
|---|---|---|
| Daily active people across Meta's apps | 3.60 billion (June average) | Meta Q2 results, 2026 |
| TAO reads per second | over 10 billion | RAMP-TAO paper, 2021 |
| TAO writes per second | tens of millions | RAMP-TAO paper, 2021 |
| Share of TAO requests that are reads | 99.8% | TAO paper, 2013 |
| TAO cache hit rate for reads | 96.4% | TAO paper, 2013 |
| MySQL fleet | millions of shards, petabytes of data | Meta engineering blog, 2023 |
| mcrouter peak traffic | close to 5 billion requests per second | Meta engineering blog, 2014 |
| Photos stored (Haystack) | 260 billion images, over 20 PB | Haystack paper, 2010 |
| Data centre campuses | about 30 listed, most in the US | Meta data centres site, 2026 (our count) |
Two numbers explain most of the design. 99.8% reads means a cache in front of the database pays off enormously. A 96.4% hit rate means only about 1 read in 28 reaches MySQL. If a similar hit rate held at 2021's ten billion reads a second (our assumption; the papers are eight years apart), that is still hundreds of millions of database reads a second, which is why MySQL is split into millions of shards.
Objects and associations: the data model
TAO stores the whole social graph with two shapes only.
- An object has a 64-bit id, a type (user, post, comment, location) and a few key-value fields.
- An association is a typed, directed edge: (id1, type, id2), plus a time and a few fields. "Leila likes post 20" is
(Leila, likes, 20). There is at most one association of a type between two objects.
Many edges come in pairs. If Leila likes post 20, post 20 is liked by Leila. TAO can be told that likes has the inverse liked_by, and it writes both. All the edges of one type from one object form an association list, kept newest first. That is exactly what a screen needs: "the 50 newest comments on this post" or "how many people like it".
The API is small on purpose: get an object; get a few specific edges; get a range of an association list ("newest 50"); get edges in a time window; count an association list. In 2013, assoc_range was 40.9% of reads and obj_get 28.9%. There are no joins and no general queries. A small API is easy to cache, because the cache knows exactly what each answer depends on.
Underneath, it is plain MySQL. The paper describes an objects table with the fields serialised into one data column, and an associations table with an index on (id1, type, time) so the range read is one index scan, the composite index rule from Indexes from the inside. Counts are kept in their own table, so "how many likes" reads one row instead of counting thousands.
Quick check
Why does TAO's small API, with no joins and no general queries, make the cache easier to keep correct?
Every read is an object, an edge list or a count, so a write to the edge list (post 20, comments) makes a known set of cached answers wrong, and the cache can fix exactly those. With arbitrary queries, nobody can tell which cached results a write touches. MySQL can join; TAO chose not to.
Sharding: the shard is inside the id
The data is split into many logical shards, "hundreds of thousands" in 2013. Each logical shard is a MySQL database, and one server holds many of them, so a shard can be moved to a new server when one gets too busy (Sharding). The neat part: an object's id contains its shard number, so any server can tell from the id alone where the object lives. An association is stored on the shard of its id1. So "the newest comments on post 20" is answered by one shard, with no fan-out across servers.
Hot spots still happen: a celebrity's post may get millions of reads. The paper describes copying a hot shard's cached data to several cache servers, and clients keeping very hot items briefly in their own memory.
Quick check
The comments on post 20 are stored as edges (post 20, has_comment, comment id). Which database shard answers "the newest 50 comments on post 20"?
The shard number is inside post 20's id, and edges are stored with their id1, so one shard holds the whole list. Asking every shard is Google Search's pattern, which TAO avoids for this read. Storing comments by commenter would scatter one post's list across many shards.
MySQL keeps evolving under TAO. In 2016-2017 Facebook moved its main user database from InnoDB to MyRocks, a storage engine built on RocksDB, which cut storage to about half of compressed InnoDB. In 2023 Meta described moving MySQL replication to Raft, a consensus protocol, so a failed primary is replaced in about 2 seconds instead of the 20 to 40 seconds the older setup took. Both are DBA work at scale: change the engine, keep the API.
The read path
Caches in TAO are arranged in two layers. A region has several follower tiers, which answer reads from web servers. Behind them is one leader tier per region, which talks to MySQL. Within a tier, consistent hashing decides which cache server holds which shard.
The write path, and how other regions find out
Facebook runs in several regions. In the 2013 design, each shard has one master region where its MySQL primary lives; other regions hold read-only MySQL replicas (Replication). Reads are served locally everywhere. Writes take a longer road:
- The web server sends the write to its follower cache, which forwards it to the leader.
- In a replica region, the local leader forwards the write to the leader in the shard's master region, which writes MySQL synchronously.
- The reply carries the new value back down the same path, so the local leader and the user's follower tier update their copies at once. The user sees their own comment immediately: read-after-write within the tier.
- MySQL replication carries the change to every replica region. Riding along in that replication stream are cache invalidation messages. When a region's replica applies the change, the invalidation is applied to that region's caches too. In the 2013 paper, replication lag was under one second in 85% of the measured time windows.
Step 4 is the important design choice. Why not have the web server delete the key in every region right after the write? Because the replica in a far region may not have the new row yet. If the cache there is cleared too early, the next reader misses, reads the old row from the lagging replica, and puts it back in the cache, where it can stay for a long time. The memcache paper calls a web-server invalidation in a replica region "premature" for exactly this reason. Sending invalidations through the database's own change stream guarantees the delete happens after the data is there.
The memcache paper describes the same idea with a daemon called mcsqueal on every database server: it reads committed statements, pulls out the cache deletes, and broadcasts them to every cache cluster in its region. Batching those deletes gave an 18 times improvement in deletes per network packet. This is the outbox pattern and change data capture from Outbox and sagas, used for cache correctness.
Memcache before TAO: leases
In 2013, Facebook wrote that TAO had been in production for several years. Before it, and alongside it for other data, Facebook used plain memcached as a look-aside cache, the cache-aside pattern from Caching: read the cache, on a miss read MySQL and set the cache; on a write, update MySQL and then delete the key. The paper says they delete instead of updating because deletes are idempotent: deleting twice is the same as deleting once.
At that scale, two problems from Caching became daily events.
- Stale sets. Reader A misses and reads the old row. A writer updates the row and deletes the key. Then A, slow for some reason, sets the old row into the cache. The cache now holds an old value with no delete coming to fix it.
- Thundering herds. A hot key is deleted by a write, and thousands of web servers miss at once and all query MySQL.
One mechanism fixes both: a lease. On a miss, memcached gives the client a 64-bit token. The client reads MySQL and sets the value with the token. If a delete arrived in between, memcached has cancelled the token and refuses the set: no stale set. And memcached hands out at most one token per key every 10 seconds. Other clients that miss in that window are told to wait a moment and retry; usually the lease holder fills the key within a few milliseconds. In the paper, leases cut the peak database query rate for one hot set of keys from 17,000 to 1,300 per second.
A refinement: when a key is deleted, memcached keeps the old value briefly in a recently-deleted area. A client that can live with slightly old data, such as a like count, can take that stale value instead of waiting. Instagram later described using the same lease idea on its own memcache, with "first miss" and "hot miss" answers (Instagram).
The paper's other tricks are worth one line each. A small pool of spare cache servers, called Gutter (about 1% of the cache servers in a cluster), takes over for failed servers so a dead cache box does not send its whole load to MySQL. A new, cold cluster warms up by reading from a warm cluster's cache instead of the database, which brings it to full capacity in a few hours. And mcrouter, a routing proxy open-sourced in 2014, sits between web servers and caches and was handling close to 5 billion requests a second at peak.
Quick check
A hot key is deleted by a write, and 3,000 web servers miss it within the same second. With memcache leases, roughly how many of them query the database?
memcached hands out one lease per key at a time, so only one client goes to MySQL while the rest retry a few milliseconds later. The cache never talks to the database itself; the client with the lease does the read and the fill.
Think first: why does a lease stop the stale set, when a plain delete-after-write does not?
Delete-after-write only removes what is in the cache at that moment. The slow reader is not in the cache yet; it is still carrying the old row in its hand. When it arrives and sets the key, nothing remembers that a delete happened. A lease gives the cache a memory: the delete cancels the token, and the set without a valid token is refused. The cache becomes the place that decides who may fill a key, instead of trusting whoever arrives last.
Photos, the edge and shipping code
Photos. In 2009, photos were stored as one file each on network file servers, and reading one photo took several disk operations just to find the file's metadata. Haystack (described in 2009 and in an OSDI 2010 paper) packs many photos into one huge file and keeps a tiny in-memory index from photo id to offset, so a read is one disk operation. The CDN (Files and CDNs) serves popular photos; Haystack exists for the long tail of old photos that the CDN does not hold. The 2010 numbers: 260 billion images, over 20 PB, about a billion new photos a week, and over a million images served per second at peak.
The edge. Your connection ends at a nearby point of presence (PoP), a small Facebook site connected to many local networks. DNS picks the PoP; requests that need data travel over Facebook's backbone to a data centre and back (2017 post on Edge Fabric). Meta's own site lists about thirty data centre campuses, most of them in the US, with others in Europe and Singapore. In 2011 Facebook published its server and data centre designs as the Open Compute Project; it said the Prineville, Oregon building used 38% less energy for the same work and cost 24% less.
Shipping code. In 2017 Facebook described moving facebook.com from three pushes a day to a "quasi-continuous" model: tens to hundreds of changes every few hours, released first to employees, then to 2% of production, then to everyone, with features hidden behind a flag system called Gatekeeper. It is the canary release from Shipping safely at the scale of thousands of engineers.
Famous decisions and what they taught
- Keep MySQL as the source of truth. Facebook scaled with caching and sharding around a boring, well-understood database, then improved the engine underneath (MyRocks, Raft). Lesson: grow around your database before you replace it (Choosing a data store).
- A cache that understands the data (TAO). Plain memcache needed every team to write its own invalidation code, and changing one edge in a list meant reloading the whole list. TAO's small graph API let the cache maintain lists itself. Lesson: when every team repeats the same cache logic, it belongs in one shared service.
- Invalidate from the commit log. Deletes ride with the data they describe, so they can never arrive before it. Lesson: when two systems must agree, drive the second from the first one's log (Outbox and sagas).
When it broke
23 September 2010: a cache that tried to fix itself. Robert Johnson's postmortem explains it. An automated system checked configuration values in the cache and, if one looked invalid, replaced it from the database. Then a bad value was written to the database itself. Every client saw the bad value, decided it was invalid and queried the database to fix it, hundreds of thousands of queries a second. Worse, when a query to the overloaded database failed, the client treated that as an invalid value too and deleted the cache key, which caused more queries. The only way out was to stop all traffic to that database cluster, which meant turning the site off. It was down for about 2.5 hours, the worst outage in over four years. The repair system was switched off until it could be redesigned. The lesson: automatic fixers need a brake. Limit how often they act, and never treat "the database is slow" as "the data is wrong". Leases, which allow one refill per key at a time, are that kind of brake.
4 October 2021: the network that disappeared. During routine maintenance, a command meant to check the capacity of the global backbone took down all the links between Meta's data centres. A bug in the audit tool that should have blocked the command let it through. Meta's DNS servers are designed to withdraw their BGP route announcements when they cannot reach the data centres, so the whole internet lost the way to facebook.com, Instagram and WhatsApp. Cloudflare saw the routes vanish at about 15:40 UTC and come back around 21:00, with service restored by about 21:20, roughly five and a half hours. Engineers had to go on site, and the buildings' security slowed them down. Meta also restored power and traffic in stages, because data centres were drawing tens of megawatts less, and switching all of it back at once could have damaged electrical systems and overloaded cold caches. Practice "storm" drills helped. Lessons: keep a way in that does not depend on the system you are fixing, and bring a cold system back slowly, the same reason the Caching lesson warns about stampedes.
Build it
Build a small TAO in Postgres (objects, associations, counts, inverses), invalidate the cache from committed changes, and put a Redis look-aside cache with leases in front. Tested with PostgreSQL 16, Redis 7, Node 22, and ioredis 5 and 6. The lease rules and the association-list read are also exercises in the Practice section, so you can try them in your browser without Redis.
-
Objects, associations and counts
Two shapes hold the whole graph. The index on
(id1, atype, time DESC)serves the main read, "newest N edges of this type", as one index scan.SQL-- Objects: nodes of the graph. One table for every type, typed by otype. CREATE TABLE obj ( id bigint PRIMARY KEY, -- globally unique (the Instagram lesson shows how to mint one) otype text NOT NULL, -- 'user', 'site', 'post', 'comment' data jsonb NOT NULL DEFAULT '{}', version bigint NOT NULL DEFAULT 1, -- bumped on every update updated_at timestamptz NOT NULL DEFAULT now() ); -- Associations: directed, typed edges. At most one edge of a type between two objects. CREATE TABLE assoc ( id1 bigint NOT NULL REFERENCES obj(id), atype text NOT NULL, -- 'follows', 'likes', 'authored', 'manages' id2 bigint NOT NULL REFERENCES obj(id), time timestamptz NOT NULL DEFAULT now(), -- lists are read newest first data jsonb NOT NULL DEFAULT '{}', PRIMARY KEY (id1, atype, id2) ); CREATE INDEX assoc_list ON assoc (id1, atype, time DESC); -- Counts are read far more than edges are written, so keep them in their own table CREATE TABLE assoc_count ( id1 bigint NOT NULL, atype text NOT NULL, n bigint NOT NULL DEFAULT 0, PRIMARY KEY (id1, atype) ); -- Edge types whose inverse must be written in the same transaction CREATE TABLE assoc_inverse (atype text PRIMARY KEY, inverse text NOT NULL); INSERT INTO assoc_inverse VALUES ('follows', 'followed_by'), ('followed_by', 'follows'), ('likes', 'liked_by'), ('liked_by', 'likes'); -
An
assoc_addthat writes both directions and both countsOne function call is one transaction: the edge, its inverse and both counts, or nothing.
ON CONFLICT DO NOTHINGmakes a double tap harmless (APIs done right).SQLCREATE OR REPLACE FUNCTION assoc_add(p_id1 bigint, p_atype text, p_id2 bigint) RETURNS boolean LANGUAGE plpgsql AS $$ DECLARE inv text; BEGIN INSERT INTO assoc (id1, atype, id2) VALUES (p_id1, p_atype, p_id2) ON CONFLICT DO NOTHING; -- a retry adds nothing IF NOT FOUND THEN RETURN false; END IF; -- the edge already existed INSERT INTO assoc_count AS c (id1, atype, n) VALUES (p_id1, p_atype, 1) ON CONFLICT (id1, atype) DO UPDATE SET n = c.n + 1; SELECT inverse INTO inv FROM assoc_inverse WHERE atype = p_atype; IF inv IS NOT NULL THEN INSERT INTO assoc (id1, atype, id2) VALUES (p_id2, inv, p_id1) ON CONFLICT DO NOTHING; INSERT INTO assoc_count AS c (id1, atype, n) VALUES (p_id2, inv, 1) ON CONFLICT (id1, atype) DO UPDATE SET n = c.n + 1; END IF; RETURN true; END $$;SQLINSERT INTO obj (id, otype, data) VALUES (1, 'user', '{"name": "Ama", "role": "store manager"}'), (2, 'user', '{"name": "Imran"}'), (3, 'user', '{"name": "Leila"}'), (20, 'post', '{"text": "Festival display is ready at store 14"}'); SELECT assoc_add(2, 'follows', 1); -- Imran follows Ama SELECT assoc_add(3, 'follows', 1); -- Leila follows Ama SELECT assoc_add(2, 'likes', 20); SELECT assoc_add(3, 'likes', 20); SELECT assoc_add(3, 'likes', 20); -- double tap: returns false, nothing changes -- assoc_range: Ama's newest followers (one index scan on assoc_list) SELECT id2 FROM assoc WHERE id1 = 1 AND atype = 'followed_by' ORDER BY time DESC LIMIT 10; -- assoc_count: one row, never COUNT(*) SELECT n FROM assoc_count WHERE id1 = 20 AND atype = 'liked_by';Outputid2 ----- 3 2 (2 rows) n --- 2 (1 row) -
Invalidate from the commit, not from app code
A trigger names the cache keys a change affects.
pg_notifymessages are delivered only when the transaction commits, and never if it rolls back, so the invalidation can never arrive before the data, the same promise mcsqueal gives. For a guarantee that also survives the listener being down, write an outbox row instead (Outbox and sagas).SQLCREATE OR REPLACE FUNCTION notify_cache_inval() RETURNS trigger LANGUAGE plpgsql AS $$ DECLARE r record := COALESCE(NEW, OLD); BEGIN IF TG_TABLE_NAME = 'obj' THEN PERFORM pg_notify('cache_inval', 'obj:' || r.id); ELSIF TG_TABLE_NAME = 'assoc' THEN PERFORM pg_notify('cache_inval', 'assoc:' || r.id1 || ':' || r.atype); END IF; RETURN NULL; -- AFTER trigger: return value is ignored END $$; CREATE TRIGGER obj_inval AFTER UPDATE OR DELETE ON obj FOR EACH ROW EXECUTE FUNCTION notify_cache_inval(); CREATE TRIGGER assoc_inval AFTER INSERT OR UPDATE OR DELETE ON assoc FOR EACH ROW EXECUTE FUNCTION notify_cache_inval(); -
Three Lua scripts: lease-get, lease-set, invalidate
Redis runs each script atomically, so no other command can slip in between its steps. Each cache entry uses three keys: the value, its lease, and a short-lived stale copy.
TypeScript// lease-scripts.ts. Keys for one entry k: k (value), lease:k (who may fill it), stale:k (old copy) // Hit: return the value. Miss: the FIRST caller gets a lease; later callers are told to wait // (and get the stale copy, if there is one). ARGV: our token, lease length in ms export const LEASE_GET = ` local v = redis.call('GET', KEYS[1]) if v then return {'hit', v} end if redis.call('SET', KEYS[2], ARGV[1], 'NX', 'PX', ARGV[2]) then return {'lease', ARGV[1]} end return {'wait', redis.call('GET', KEYS[3])}`; // Fill the cache ONLY if our lease is still there. A write since our miss deleted it. // ARGV: our token, value, TTL in seconds export const LEASE_SET = ` if redis.call('GET', KEYS[2]) ~= ARGV[1] then return 0 end redis.call('SET', KEYS[1], ARGV[2], 'EX', ARGV[3]) redis.call('DEL', KEYS[2]) return 1`; // After a database write: delete the value AND any lease. Keep the old value as stale:k // for a few seconds, for readers who said a slightly old answer is fine. ARGV: stale TTL export const INVALIDATE = ` local v = redis.call('GET', KEYS[1]) if v then redis.call('SET', KEYS[3], v, 'EX', ARGV[1]) end redis.call('DEL', KEYS[1], KEYS[2]) return 1`; -
The lease cache
One caller per key loads from the database; the others wait about 20 ms and look again, or take the stale copy if the screen allows it. Keys from different shards are fine, but on Redis Cluster all three keys of an entry must hash to the same slot; wrap the key in braces, such as
{assoc:1:likes}, to make that true.TypeScript// lease-cache.ts: look-aside cache with memcache-style leases, on Redis (ioredis 5 or 6) import Redis from 'ioredis'; import { randomUUID } from 'node:crypto'; import { LEASE_GET, LEASE_SET, INVALIDATE } from './lease-scripts'; const sleep = (ms: number) => new Promise((r) => setTimeout(r, ms)); export class LeaseCache { constructor(private redis: Redis, private leaseMs = 2000, private staleS = 5) {} async get<T>(key: string, ttlS: number, load: () => Promise<T>, allowStale = false): Promise<T> { const keys = [key, `lease:${key}`, `stale:${key}`]; for (let i = 0; i < 100; i++) { // wait at most about 2 s const token = randomUUID(); const [state, v] = (await this.redis.eval(LEASE_GET, 3, ...keys, token, this.leaseMs)) as [string, string | null]; if (state === 'hit') return JSON.parse(v!) as T; if (state === 'lease') { // we are the ONE caller that loads const value = await load(); await this.redis.eval(LEASE_SET, 2, key, keys[1], token, JSON.stringify(value), ttlS); return value; // if the set was refused, only we see it } if (allowStale && v !== null) return JSON.parse(v) as T; // old is OK for this screen await sleep(20); // someone else is loading: wait, retry } return load(); // the loader died: stop waiting } async invalidate(key: string): Promise<void> { // call AFTER the write commits await this.redis.eval(INVALIDATE, 3, key, `lease:${key}`, `stale:${key}`, this.staleS); } } -
The invalidator process
Run one per region (or per Redis). It listens for committed changes and calls
invalidate, which also cancels any lease, so a slow reader cannot put old data back.TypeScript// invalidator.ts import Redis from 'ioredis'; import { Client } from 'pg'; import { LeaseCache } from './lease-cache'; (async () => { const cache = new LeaseCache(new Redis(process.env.REDIS_URL ?? 'redis://127.0.0.1:6379')); const pg = new Client({ connectionString: process.env.DATABASE_URL }); await pg.connect(); pg.on('notification', async (msg) => { if (!msg.payload) return; await cache.invalidate(msg.payload); console.log('invalidated', msg.payload); }); await pg.query('LISTEN cache_inval'); })();SQLSELECT assoc_add(1, 'follows', 2); BEGIN; UPDATE obj SET data = data || '{"name": "Imran (draft)"}' WHERE id = 2; ROLLBACK; UPDATE obj SET data = data || '{"name": "Imran, Store app PM"}', version = version + 1 WHERE id = 2;Outputinvalidated assoc:1:follows invalidated assoc:2:followed_by invalidated obj:2 # the rolled-back UPDATE sent nothing -
Prove both guarantees
Two small scripts in the same project test the lease cache against plain cache-aside. The first sends 200 requests at once for a cold key whose query takes 100 ms (
pg_sleep(0.1)stands in for a heavy join). The second runs the stale-set race: a slow reader reads price 120, a writer commits 135 and invalidates, then the slow reader tries to set 120.Terminalnpm i ioredis pg && npm i -D typescript @types/node @types/pg npx tsc -p . export REDIS_URL=redis://127.0.0.1:6379 DATABASE_URL=postgresql://app@localhost/graph node dist/herd.js node dist/stale-set.jsOutputplain: 200 requests -> 200 DB queries in 497 ms lease: 200 requests -> 1 DB queries in 128 ms plain: cache holds "120.00", database holds "135.00" lease: cache holds null, database holds "135.00"Plain cache-aside sent all 200 misses to Postgres and later kept a wrong price for the whole TTL. With leases, one query filled the key for everyone, and the late set was refused, so the next read loads 135 from the database.
Bring it to your team
Use these whenever a cache sits in front of data that changes.
- When this row changes, which cache keys become wrong, and what deletes them? Is that tied to the commit, or to app code that may be skipped?
- Do we delete keys on write, or update them? If we update, what happens when two writes arrive out of order?
- What happens when the hottest key is deleted at the festival peak: one database query, or hundreds?
- Could a slow reader put an old value back after a write? What stops it?
- Which screens may show a slightly old value while the cache refills, and which must wait?
- Does any automatic job repair or refill data by itself? What limits how fast it can act?
Red flags
- Cache invalidation code copied into many services, each written slightly differently.
- A cache delete that runs before the database commit, or in a replica region before the replica has the data.
COUNT(*)over a large table on every page view for a like or follower count.- Retry loops or self-healing jobs with no rate limit and no backoff.
- An admin or recovery path that depends on the same network or DNS as the product.
Practice
Give a cache memcache-style leases
Finish the in-memory LeaseCache. get returns a hit, or hands the first caller that misses a lease token, or tells later callers to wait (with the old value, if one was kept). set stores a value only if the caller's token is still the lease for that key. invalidate, called after a database write, removes the value and any lease, and keeps the old value as a stale copy. These are the three Lua scripts from step 4 of the Build-it, without Redis.
// A look-aside cache with memcache-style leases, kept in memory.
class LeaseCache {
constructor() {
this.values = new Map(); // key -> cached value
this.leases = new Map(); // key -> token of the ONE caller allowed to fill it
this.stale = new Map(); // key -> the value it had before the last invalidate
this.nextToken = 1;
}
// Hit: { state: 'hit', value }. First miss: { state: 'lease', token }.
// Any other miss while a lease is out: { state: 'wait', stale }.
get(key) {
return { state: 'lease', token: this.nextToken++ };
}
// Store the value only if token is still the lease for this key. Return true if stored.
set(key, token, value) {
this.values.set(key, value);
return true;
}
// Called after a database write: remove the value AND any lease; keep the old value as stale.
invalidate(key) {
this.values.delete(key);
}
}test('the first miss gets a lease, the next miss is told to wait', () => {
const c = new LeaseCache();
expect(c.get('price:1001').state).toBe('lease');
expect(c.get('price:1001').state).toBe('wait');
});
test('the lease holder fills the key, then everyone hits', () => {
const c = new LeaseCache();
const { token } = c.get('price:1001');
expect(c.set('price:1001', token, 120)).toBe(true);
expect(c.get('price:1001')).toEqual({ state: 'hit', value: 120 });
});
test('a write between the miss and the set cancels the lease: no stale set', () => {
const c = new LeaseCache();
const { token } = c.get('price:1001'); // a slow reader read 120 from the database
c.invalidate('price:1001'); // a writer commits 135 and invalidates
expect(c.set('price:1001', token, 120)).toBe(false);
expect(c.get('price:1001').state).toBe('lease');
});
test('a set with a token that is not the lease is refused', () => {
const c = new LeaseCache();
c.get('k');
expect(c.set('k', 999, 'x')).toBe(false);
});
test('while the key is being refilled, waiters can read the old value', () => {
const c = new LeaseCache();
const { token } = c.get('k');
c.set('k', token, 120);
c.invalidate('k');
c.get('k'); // the new lease holder goes to the database
expect(c.get('k')).toEqual({ state: 'wait', stale: 120 });
});
Show a solution
class LeaseCache {
constructor() {
this.values = new Map();
this.leases = new Map();
this.stale = new Map();
this.nextToken = 1;
}
get(key) {
if (this.values.has(key)) return { state: 'hit', value: this.values.get(key) };
if (!this.leases.has(key)) { // first miss: hand out the lease
const token = this.nextToken++;
this.leases.set(key, token);
return { state: 'lease', token };
}
return { state: 'wait', stale: this.stale.get(key) };
}
set(key, token, value) {
if (this.leases.get(key) !== token) return false; // a write cancelled our lease
this.values.set(key, value);
this.leases.delete(key);
return true;
}
invalidate(key) {
if (this.values.has(key)) this.stale.set(key, this.values.get(key));
this.values.delete(key);
this.leases.delete(key); // cancel any lease in flight
}
}Read an association list
The tables obj and assoc from the Build-it hold a few users, post 20, and some edges. Write TAO's assoc_range read for one screen: the names of the 3 newest people who liked post 20, newest first, in a column called name. Names live in obj.data, so use data ->> 'name'. Only edges of type liked_by count.
CREATE TABLE obj (id bigint PRIMARY KEY, otype text NOT NULL, data jsonb NOT NULL DEFAULT '{}');
CREATE TABLE assoc (
id1 bigint NOT NULL, atype text NOT NULL, id2 bigint NOT NULL, time timestamptz NOT NULL,
PRIMARY KEY (id1, atype, id2));
CREATE INDEX assoc_list ON assoc (id1, atype, time DESC);
INSERT INTO obj VALUES (1, 'user', '{"name": "Ama"}'), (2, 'user', '{"name": "Imran"}'),
(3, 'user', '{"name": "Leila"}'), (4, 'user', '{"name": "Ken"}'), (5, 'user', '{"name": "Tomás"}'),
(20, 'post', '{"text": "Festival display is ready at store 14"}');
INSERT INTO assoc VALUES
(20, 'liked_by', 2, '2026-10-01 09:00+00'), (2, 'likes', 20, '2026-10-01 09:00+00'),
(20, 'liked_by', 3, '2026-10-01 09:05+00'), (3, 'likes', 20, '2026-10-01 09:05+00'),
(20, 'liked_by', 4, '2026-10-01 09:20+00'), (4, 'likes', 20, '2026-10-01 09:20+00'),
(20, 'liked_by', 5, '2026-10-01 09:12+00'), (5, 'likes', 20, '2026-10-01 09:12+00'),
(20, 'commented_by', 1, '2026-10-01 09:30+00'),
(1, 'follows', 2, '2026-10-01 08:00+00');
-- The 3 newest people who liked post 20, newest first, as a column called name
SELECT id2
FROM assoc
WHERE id1 = 20;[{"name": "Ken"}, {"name": "Tomás"}, {"name": "Leila"}]
Show a solution
SELECT o.data ->> 'name' AS name
FROM assoc a
JOIN obj o ON o.id = a.id2
WHERE a.id1 = 20 AND a.atype = 'liked_by'
ORDER BY a.time DESC
LIMIT 3;Check yourself
Reader A misses the cache and reads the old price. A writer commits a new price and deletes the key. Then A sets the old price into the cache. What stops this in Facebook's memcache design?
The lease gives the cache a memory of the delete, so the late set fails. A short TTL only limits how long the wrong value lives. Updating instead of deleting creates its own ordering bugs, and deleting before the write opens the same race wider.
Why does Facebook send cache invalidations in a replica region through MySQL replication instead of from the web server right after the write?
The danger is ordering. If the cache is cleared before the lagging replica has the change, the next miss reads the old row and caches it. Riding in the replication stream, the invalidation can never arrive before the data. Speed is not the reason; the replication stream may be slower.
In TAO, how does a server know which MySQL shard holds the comments on post 20?
Embedding the shard in the id means no lookup and no fan-out: the comment list for post 20 sits on post 20's shard. Asking every shard is the Google Search pattern (Google Search), which Facebook avoids for this read. A directory would add a hop and a bottleneck.
Flashcards
Key takeaways
- The social graph is two shapes: objects and typed edges. A small API over them is easy to cache correctly.
- MySQL stays the source of truth, split into many logical shards; the shard is inside the id, so most reads hit one shard.
- Caches answer about 96% of reads. Writes go to the master region, and invalidations ride the replication stream so they never arrive before the data.
- Leases fix both stale sets and thundering herds: one filler per key, and a delete cancels a late set.
- Automatic fixers and recovery paths need brakes and independent access; both big outages taught that.
Sources
- TAO: Facebook's Distributed Data Store for the Social Graph, Bronson et al., USENIX ATC, 2013
- TAO: The power of the graph, Mark Marchukov, Engineering at Meta, 2013
- Scaling Memcache at Facebook, Nishtala et al., USENIX NSDI, 2013
- RAMP-TAO: Layering Atomic Transactions on Facebook's Online TAO Data Store, Cheng et al., PVLDB, 2021
- RAMP-TAO, Engineering at Meta, 2021
- Introducing mcrouter, Engineering at Meta, 2014
- MyRocks: A space- and write-optimized MySQL database, Engineering at Meta, 2016
- Migrating a database from InnoDB to MyRocks, Engineering at Meta, 2017
- Building and deploying MySQL Raft at Meta, Engineering at Meta, 2023
- Finding a needle in Haystack: Facebook's photo storage, Beaver et al., OSDI, 2010
- Needle in a haystack: efficient storage of billions of photos, Engineering at Meta, 2009
- Steering oceans of content to the world (Edge Fabric), Engineering at Meta, 2017
- Rapid release at massive scale, Engineering at Meta, 2017
- Building efficient data centers with the Open Compute Project, Engineering at Meta, 2011
- More details on today's outage, Robert Johnson, Engineering at Meta, 2010
- More details about the October 4 outage, Santosh Janardhan, Engineering at Meta, 2021
- Understanding how Facebook disappeared from the Internet, Cloudflare blog, 2021
- Meta Reports Second Quarter 2026 Results, Meta Investor Relations, 2026
- Meta data center locations, Meta, 2026