TTL, TAO, and the Reconciliation Loop: What Facebook’s Cache Taught Me About Keeping ScyllaDB in Sync

Babayevqocheli

8 min read

·

Aug 2, 2026

--

Listen

Share

Three systems, three different scales, one shared problem: a fast copy of your data will always drift from the truth. The only question is how you catch it.

The problem underneath every cache

Every system that copies data for speed inherits the same debt: the copy can lie. A cache can serve a stale price. A denormalized read table can serve a product that was deleted five minutes ago. A follower replica can answer a read with data the leader has already overwritten.

This isn’t a bug you eliminate — it’s a tradeoff you manage. I ran into this directly while building a reconciliation pipeline for ScyllaDB on top of a PostgreSQL source of truth: what happens when a row is deleted directly in ScyllaDB, bypassing the write pipeline entirely? ScyllaDB says “gone.” Postgres says “still here.” Nothing in between notices — unless you build something that does.

It turns out the pattern I ended up with — periodically comparing a derived store against its source of truth and healing the difference — is the same pattern that shows up, at wildly different scale, in Facebook’s TAO. And both of them are really just an extension of the oldest caching primitive there is: TTL.

This article walks through all three, from the ground up, with real code.

Part 1: TTL and cache-aside — the 30-second version

TTL (Time To Live) is an expiration timer attached to a cached value. You write something into Redis or a local cache with “this is valid for 300 seconds,” and when that window closes, the cache entry disappears — you don’t have to clean it up yourself.

The reason TTL exists at all: a cache is always a stale copy of the database, the moment you write it. TTL is the simplest possible bound on how stale it’s allowed to get.

The most common pattern built around this is cache-aside:

public class ProductService {
    private final JedisPool jedisPool;
    private final ProductRepository dbRepository;
    private static final int TTL_SECONDS = 300;

    public Product getProduct(String productId) {
        try (Jedis jedis = jedisPool.getResource()) {
            String cacheKey = "product:" + productId;            String cached = jedis.get(cacheKey);
            if (cached != null) {
                return deserialize(cached);          // cache HIT
            }            Product product = dbRepository.findById(productId);
            if (product == null) return null;            jedis.setex(cacheKey, TTL_SECONDS, serialize(product)); // cache MISS -> fill
            return product;
        }
    }
}

Check the cache first. Miss? Read the database, then populate the cache before returning. The next identical request is served from memory.

The three decisions every cache design has to make are:

• Expiration (TTL) — how long is a stale answer acceptable? ScyllaDB itself even exposes this natively at the row level, via USING TTL on an insert — a column can be told to disappear on its own, no delete required.
• Eviction — when the cache is full, what gets thrown out? (Usually LRU — Least Recently Used.)
• Invalidation — when the underlying data changes, how does the cache find out?

That third one is the famous one. Phil Karlton’s line — “there are only two hard things in computer science: cache invalidation and naming things” — exists because TTL alone is a blunt instrument. It bounds staleness, but it doesn’t detect it. If your TTL is 5 minutes, you’ve simply decided that 5 minutes of wrong answers is an acceptable cost of doing business.

For a single key-value cache in front of one database, that’s usually fine. It stops being fine once your reads look less like “get this row” and more like “get this list of things connected to this other thing” — at which point you’ve arrived at Facebook’s problem in 2008.

Part 2: Facebook TAO — when a plain cache breaks

Facebook’s early architecture looked like the pattern above: web servers hit MySQL directly, with memcache sitting in front as a lookaside cache — exactly the cache-aside pattern from Part 1, at Facebook’s scale. It worked, for a while. Then three specific cracks appeared, described in the original TAO paper (Bronson et al., published at USENIX ATC 2013):

1. Inefficient edge lists. A social graph isn’t rows and columns — it’s this user’s list of friends, this post’s list of comments. A key-value cache is a poor fit for “give me this whole list”: any single change to the list means invalidating and reloading the entire thing, not just one key.

2. Distributed control logic. In a lookaside architecture, the decision logic — what to fetch, what to invalidate, how to prevent duplicate work — lives on the client side, and clients don’t coordinate with each other. More failure modes, harder to reason about.

3. Expensive read-after-write consistency. MySQL replication was asynchronous, master to replicas. A user could write something, then immediately read it back from a replica that hadn’t caught up yet — and see their own action disappear.

Facebook’s answer wasn’t a better cache-aside implementation. It was TAO: a data store that understands the graph natively — objects (nodes) and associations (edges) — instead of treating everything as opaque key-value blobs. Reads and writes go through TAO’s own API, and TAO decides internally how to cache, invalidate, and route them.

Two design choices from the paper are worth pulling out, because they map directly onto the reconciliation problem:

A two-tier leader/follower cache. Each region has a tier of caching servers; one tier is designated leader for a given shard of data and owns the authoritative cached copy, while follower tiers serve reads and forward writes and misses up to the leader. Writes are committed to the underlying MySQL leader, and the cache propagates the change down through this hierarchy — rather than every client independently deciding when to invalidate.

Eventual consistency, on purpose. TAO explicitly favors availability and read efficiency over strict consistency. It was designed to sustain on the order of a billion reads per second against a changing graph, and it accepts that a follower cache might briefly serve slightly stale data rather than block or reject a read while it catches up.

That second point is the important one for what comes next. TAO doesn’t pretend a distributed cache can be perfectly, instantly correct. Instead, it builds in a structural expectation: followers will lag leaders, and that’s fine, as long as they converge. Convergence is designed in — not left to a TTL and hope. It’s worth noting ScyllaDB itself inherits a version of this idea from Cassandra’s lineage: replicas can legitimately disagree for a window, and mechanisms like read repair and hinted handoff exist specifically to converge them — the same philosophy TAO applies at the cache layer.

Part 3: The same idea, a much smaller machine — ScyllaDB reconciliation

I don’t run a billion reads a second. I run a product catalog synced from PostgreSQL into ScyllaDB, with domain events flowing through Kafka. But the underlying shape of the problem is identical to TAO’s: a derived, read-optimized copy of data that can drift from its source of truth, and row deletions are exactly the kind of drift that no amount of TTL or “wait for the next event” can fix — because a delete of the row itself, done outside the normal write path, leaves no event behind to replay. There’s nothing to invalidate on, because nothing announced the change.

TAO solves this with an always-on hierarchy that propagates every write. At my scale, a lighter mechanism does the same job on a schedule: a background reconciler that periodically asks “do these two stores agree?” and heals the answer when they don’t.

Step one — cheap check first. Don’t compare full data if you don’t have to; compare counts:

var pgCount = await pgQuery.CountAsync(ct);

var countRow = await session.ExecuteAsync(
    new SimpleStatement("SELECT COUNT(*) FROM products"));
var scyllaCount = countRow.First().GetValue<long>("count");if (pgCount == scyllaCount) return;   // nothing to do, most runs end here

(In practice, COUNT(*) on a large ScyllaDB table is expensive — a full scan — so this is normally replaced with a maintained counter table or a periodic approximate count, not run on every cycle. The principle is the same: cheap check first.)

Step two — if counts disagree, find out which records are missing, without loading the whole table into memory. This is where the two systems’ scale problems actually converge conceptually: TAO can’t hold the whole social graph in one cache tier, and I can’t hold a multi-million-row table in application memory. Both solve it by moving through data in bounded windows rather than all at once. In Postgres, that means keyset pagination over IDs — never OFFSET, which gets slower as the table grows. Checking those IDs against ScyllaDB is where the two databases diverge technically from an OpenSearch-based version of this pipeline: there's no mget. Instead, because id is the partition key, an IN clause is a set of efficient single-partition lookups, not a scan — which is exactly the shape you want for this check:

private async Task<List<Guid>> FindMissingIdsStreamingAsync(AppDbContext db, ISession session, CancellationToken ct)
{
    var missing = new List<Guid>();
    Guid? lastId = null;
    const int pageSize = 5000;

    var checkStmt = session.Prepare("SELECT id FROM products WHERE id IN ?");    while (true)
    {
        var query = db.Products.AsNoTracking().AsQueryable();
        if (lastId.HasValue)
            query = query.Where(p => p.Id.CompareTo(lastId.Value) > 0);        var idBatch = await query
            .OrderBy(p => p.Id)
            .Take(pageSize)
            .Select(p => p.Id)
            .ToListAsync(ct);        if (idBatch.Count == 0) break;        var rows = await session.ExecuteAsync(checkStmt.Bind(idBatch));
        var found = rows.Select(r => r.GetValue<Guid>("id")).ToHashSet();        missing.AddRange(idBatch.Where(id => !found.Contains(id)));        lastId = idBatch.Last();
        if (idBatch.Count < pageSize) break;
    }
    return missing;
}

Step three — heal only what’s actually missing, in one round trip, not one per record. ScyllaDB’s equivalent of a bulk write is an unlogged batch — appropriate here because every statement targets a different partition key and we don’t need the atomicity (and cost) of a logged batch:

private async Task RestoreMissingAsync(AppDbContext db, ISession session, List<Guid> missingIds, CancellationToken ct)
{
    var entities = await db.Products
        .Where(p => missingIds.Contains(p.Id))
        .ToListAsync(ct);

    var insertStmt = session.Prepare(
        "INSERT INTO products (id, name, sku, price, updated_at) VALUES (?, ?, ?, ?, ?)");    var batch = new BatchStatement().SetBatchType(BatchType.Unlogged);
    foreach (var e in entities)
        batch.Add(insertStmt.Bind(e.Id, e.Name, e.Sku, e.Price, e.UpdatedAt));    await session.ExecuteAsync(batch);
}

Run this on a BackgroundService every 15 minutes, across every table pair you care about, and each pair fails independently — one bad reconciliation doesn't block the other eight.

This is, structurally, a slow-motion version of what TAO’s follower tier does continuously — and, not coincidentally, of what ScyllaDB’s own read repair does at the replica level: accept that a derived copy can lag, and build convergence into the system on purpose instead of hoping the event stream never drops a message.

The one idea that ties it together

TTL, TAO, and a reconciliation loop are three different answers to the same question, asked at three different scales:

What it protects against How it converges TTL / cache-aside A single stale key Expires and refetches on a timer Facebook TAO A whole graph cache drifting under massive write load A leader/follower hierarchy that propagates every write, accepting brief staleness ScyllaDB reconciliation Silent drift from out-of-band changes (like a manual delete) that no event stream ever announces A scheduled sweep that compares source and derived store, and heals only the difference

None of these eliminate staleness. They just make a deliberate choice about how much staleness is tolerable, and — critically — build an actual mechanism to bound it, rather than assuming the happy path holds forever. The lesson I took from reading the TAO paper while debugging my own pipeline: don’t just protect against writes going wrong — assume some data will eventually exist somewhere your event pipeline never told you about, and build the sweep that finds it.

If you’re building something similar — a CDC pipeline, a denormalized store kept in sync with a relational database, anything with a “source of truth” and a “fast copy” — the pattern above generalizes past ScyllaDB: any derived store benefits from a scheduled reconciliation pass, not just an event stream and a prayer.