Distributed Cache Design: Part 2

CAP theorem and consistency models

CAP theorem usually gets taught as “pick two of three: Consistency, Availability, Partition tolerance.” That framing causes more confusion than it clears up, because in a real distributed system, network partitions aren’t optional. They happen. Partition tolerance isn’t really a choice on the table. The decision you’re actually making at design time is narrower: when a partition hits, do you favor consistency or availability?

The trade-off, with warehouses

Say a delivery company runs warehouses in three different cities, all syncing inventory to a central system. One day the link to one of the regional warehouses drops. The manager on the ground now has exactly two options.

Stop selling until the link’s back, so nobody ever sees a wrong count — that’s choosing consistency, at the cost of availability. Or keep selling locally and reconcile with headquarters once reconnected, meaning for a while the local count and the central count disagree — that’s choosing availability, at the cost of consistency.

That’s the whole theorem once you strip the jargon out:

• C — every read returns the latest write, or an error. Never a stale value.
• A — every request gets a response, even if the data isn’t the freshest.
• P — the system keeps functioning despite a network partition.

Object read(String key, boolean partitionDetected, ConsistencyMode mode) {
    if (partitionDetected) {
        if (mode == ConsistencyMode.STRONG) {
            throw new UnavailableException("can't confirm latest value during partition");
        }
        return localReplica.get(key); // AVAILABLE: may be stale, but it answers
    }
    return localReplica.get(key);
}

Where a distributed cache lands, and why it’s not one answer

Caches almost always favor availability. That’s kind of the whole point of caching: speed over freshness. If a cache node goes unreachable, you’d rather serve a possibly-stale value than throw an error — that’s not really a compromise, that’s the product doing its job.

What’s easy to miss is that a distributed cache isn’t making one CAP choice. It has two layers, and they should make opposite ones.

The data plane — the actual cached key/value pairs — can lean AP. If a node gets partitioned off, the worst a client sees is a stale value, and two clients might get different answers for the same key during that window. For a cache, that’s usually fine, since the cache is rarely the source of truth to begin with. Things resync once the partition heals, and staying responsive matters more than being perfectly fresh. Compare that to a bank balance, where the same staleness could mean an overdraft or a double-spend — there, correctness has to win over responsiveness.

The control plane — cluster membership, leader election, shard ownership, rebalancing, configuration — should lean CP instead, and this is the part people miss when they only think about the data. If two partitioned nodes each independently believe they’re the leader, you get split-brain: both accepting writes, both making conflicting eviction and rebalancing decisions. That’s not a stale value sitting in someone’s cache, that’s active corruption of the cluster’s own state. For the control plane it’s safer to reject or delay an operation during a partition than to let two halves of the cluster disagree about who’s in charge.

Data plane leans AP. Control plane leans CP. Most engineers only reason about the first half and never think through how the cluster agrees on its own topology — which is exactly why it’s worth having ready.

The piece CAP doesn’t cover: consistency models

CAP only describes what happens during a partition. Your system is making consistency trade-offs all the time, partition or not, and that’s a separate spectrum that shapes day-to-day behavior far more often than an actual partition does.

Take a patient record replicated across three clinic branches. A doctor at one branch adds a new allergy to the chart. Every consistency model is really answering one question: how soon, and in what order, do the other branches see that write?

Strong consistency means the write isn’t done until every replica agrees — any branch, checked at any moment afterward, sees the new allergy. It’s the safest option, but you pay a coordination cost on every write. Eventual consistency means replicas converge with no guaranteed timeline — another branch might still show the old chart for a few seconds, longer under load. Cheap and fast, risky if someone acts on the stale version in that window. Causal consistency preserves cause-and-effect order — if the allergy was added because of a lab result, nobody sees the allergy without having already seen that lab result, though unrelated concurrent writes can still land in different orders at different branches. Read-your-writes is narrower still, a session-level promise: you always see your own write immediately, even while other people’s views lag behind. The doctor who made the edit sees it on refresh; another branch might not yet.

V readYourWrites(String key, long myLastWriteVersion, CacheEntry<V> replicaEntry) {
    if (replicaEntry.writerVersion < myLastWriteVersion) {
        // this replica hasn't caught up to MY write — don't show them stale data
        return readFromPrimary(key);
    }
    return replicaEntry.value;
}

Most caches default to eventual consistency for cross-client reads, because it’s cheap and fast, then layer read-your-writes on top specifically for whoever just wrote. Update a profile picture and your own next page load has to show it, even if CDN edge nodes elsewhere haven’t caught up.

One distinction worth being precise about: a system where the writer sees their own update instantly, but other clients can lag up to 200ms behind, is not strong consistency. Strong consistency means every client’s next read reflects the write, not just the writer’s own. What you actually have there is read-your-writes for the writer, plus a bounded staleness guarantee for everyone else — bounded because the lag has a known ceiling, which is what separates it from plain eventual consistency, where the lag has no ceiling at all.

Putting it together

Two separate questions, two separate answers. During a partition: does the system favor consistency or availability? For a cache’s data plane, almost always availability. For its control plane, almost always consistency, because split-brain is worse than a stale value. All the time, partition or not: what’s the consistency model for reads — strong if every client has to see the same value immediately, eventual if convergence-with-lag is fine, causal if cause-and-effect ordering matters more than global ordering, read-your-writes if the only hard requirement is that people never see their own actions undone.

A design doc that just says “the cache is eventually consistent” has answered half the question. The other half — what happens to the control plane during a partition, and what guarantee the writer actually gets about their own writes — is where the real failure modes tend to live.