Consistency, Availability and CAP

The moment your system holds more than one copy of anything — a read replica, a cache, a search index — you have a consistency problem. Not a potential one. The copies are updated at different times, so there is always a window in which they disagree, and the design question is what happens to a request that arrives during it.

This post covers what CAP actually says (which is narrower than its reputation), the consistency models worth naming, and the dual-write problem — shown against a live system, including exactly where it goes wrong.

CAP, without the folklore

The theorem states that a distributed system cannot simultaneously guarantee all three of:

• Consistency — every read returns the most recent write.
• Availability — every request gets a non-error response.
• Partition tolerance — the system keeps working when the network drops messages between nodes.

The popular version is “pick two”, and that framing is what makes it useless in practice. You do not get to pick partition tolerance. Networks fail: cables are cut, switches reboot, a deploy misconfigures a security group. If your nodes talk over a network, partitions happen, so P is a fact rather than a choice.

Which means CAP is really about what you do during a partition:

                    the network splits

    [ node A ] ── ✗ ── [ node B ]
        ▲                   ▲
   a write arrives here, and B cannot be told about it

   CP: refuse the write.  Data stays correct, this node is DOWN.
   AP: accept the write.  Node stays UP, the two now DISAGREE.

   There is no third option. That is the whole theorem.

A CP system refuses to serve rather than serve something wrong. A traditional relational database with synchronous replication behaves this way: lose the quorum and writes stop. That is correct for money.

An AP system keeps answering and reconciles later. A shopping cart, a social feed, a DNS record. A slightly stale timeline is fine; an error page is not.

PACELC, which is more useful

CAP only describes the failure case, and partitions are rare. PACELC extends it to the other 99.9% of the time:

   if (P)artition:  choose (A)vailability or (C)onsistency
   (E)lse:          choose (L)atency      or (C)onsistency

That second line is the one you live with daily. Even when nothing is broken, making a read consistent means waiting — for a quorum, for a replica to catch up, for a lock. Every milliseconds-versus-correctness decision in a healthy system is the EL/C trade, and it comes up far more often than partitions do.

Postgres with async replicas is PA/EL: it stays available and it is fast, and it is not strongly consistent across replicas. Spanner is PC/EC: consistent always, and it pays for it in latency.

The two-generals reason none of this goes away

It is worth knowing why this is a fundamental limit rather than an engineering gap somebody will close.

Two generals must attack at the same time, and can only communicate by messengers who may be captured. General A sends “attack at dawn”. Did it arrive? A needs an acknowledgement. B sends one — but did that arrive? B now needs an acknowledgement of the acknowledgement, and so on forever. No finite exchange of messages gives both sides certainty.

That is every network call you will ever make. When a request times out, you do not know whether it failed or succeeded and the response was lost:

   POST /charge  ──X──>   did the charge happen?
                          you cannot tell from a timeout.

   retry  -> maybe charging twice
   don't  -> maybe never charging at all

This is why idempotency is not an optimisation but a requirement: it is the only way out of the dilemma. If retrying is guaranteed harmless, the impossible question stops needing an answer — you simply retry. Every reliable distributed system is built on that move, and it is why the topic recurs in the queues and concurrency posts.

The consistency models you should be able to name

The two in the middle are the ones that matter in practice, because they are what users actually notice.

Read-your-writes. A user edits their profile, the write goes to the primary, the next page load hits a replica 200ms behind, and their change has vanished. They will try again, and you will get a bug report you cannot reproduce.

Monotonic reads. Two consecutive reads land on different replicas at different lags, so a comment appears and then disappears. This one is worse than plain staleness, because users interpret it as data loss.

   read 1 -> replica A (100ms behind)  -> comment IS there
   read 2 -> replica B (900ms behind)  -> comment is GONE
   read 3 -> replica A                 -> it is back

   Nothing was lost. It looks exactly like something was.

The usual fix for both is stickiness: route a given user’s reads to the same replica, or to the primary for a few seconds after they write. Note that this is not free — it is the sticky-session problem from the load balancing post, reappearing at the data layer.

Where the models come from

One point that clears up a lot of confusion: these models are not different technologies, they are different amounts of waiting.

   write arrives
      │
      ├─ acknowledge NOW, replicate later      -> eventual (fast, may be stale)
      ├─ acknowledge when a quorum has it      -> strong-ish (slower)
      └─ acknowledge when ALL have it          -> strong (slowest, fragile —
                                                  one slow replica stalls writes)

Every consistency guarantee is bought with latency at write time, read time, or both. That is the PACELC “else” branch made concrete, and it is why “just make it strongly consistent” is not a free move: it means every write waits for the slowest participant, and the slowest participant is sometimes a machine having a bad minute.

Quorums

How distributed datastores make the consistency level a per-request choice rather than a property of the system.

   N = 3 replicas
   W = replicas that must acknowledge a write
   R = replicas read from

   W + R > N   =>  the read set and the write set overlap,
                   so a read always sees the newest write

   W=1 R=1  (2 > 3 false)  fast, may be stale
   W=3 R=1  (4 > 3 true)   strong reads, writes fail if any node is down
   W=2 R=2  (4 > 3 true)   balanced — survives one node down, either way

W=2, R=2 on three replicas is the common default, and the reason is the middle column: it tolerates losing exactly one node without losing either strong reads or the ability to write. That is the shape of most quorum configurations you will meet.

Transactions, and what isolation actually promises

Before distributing anything, it is worth being precise about what a single database gives you, because the guarantees are weaker than most people assume — and every distributed consistency problem is a version of one of these.

ACID is four promises: atomicity (all of it or none), consistency (constraints hold), isolation (concurrent transactions do not interfere), and durability (a committed write survives a crash).

Isolation is the one with a dial on it, and the settings are named after the anomalies they prevent:

The default matters more than the table. Postgres runs read committed, which means that within one transaction, reading the same row twice can return different values — because another transaction committed in between.

   BEGIN
     SELECT count(*) FROM bookings WHERE property_id = 7;   -> 0
                                        (another transaction commits a booking)
     INSERT INTO bookings ...                               -> now there are 2
   COMMIT

That is a phantom, and it is the database-level version of the double-booking race. A transaction did not protect against it, because read committed does not promise to. This is why the concurrency post reaches for a constraint rather than a transaction: wrapping the check and the insert in BEGIN and COMMIT changes nothing at the default isolation level.

SERIALIZABLE does prevent it, by making concurrent transactions behave as if they ran one after another — and it pays for that by aborting some of them, so every caller needs retry logic. That is a real option and it is the reason people reach for constraints instead: a constraint costs nothing and fails at exactly one place.

The dual-write problem

Here is where theory becomes a bug in your code. Two datastores cannot be updated atomically. There is no transaction that spans Postgres and Elasticsearch, or Postgres and an email provider, or a database and a cache.

StayHub has exactly this shape. Postgres is the source of truth; Elasticsearch holds a derived copy so that search does not have to touch Postgres:

   writes ──> [ Postgres ]  source of truth
                   │
                   │  sunk from application code, after the commit
                   v
              [ Elasticsearch ]  derived, disposable, rebuildable

The code is two lines, and every interesting question is about their order:

    def _sync(self, prop: Property) -> None:
        indexed = indexer.index_property(prop)
        cache.invalidate(cache.property_key(prop.public_id))

Why it is after the commit

Indexing before the commit looks more careful and is worse. If the transaction then rolls back, a listing exists in the search results that does not exist in the database, and the guest who clicks it gets a 404 from a page that just offered it to them.

Indexing inside the transaction is worse still. It makes a search cluster having a bad day into a reason that a host’s save fails — coupling the availability of the write path to a system that was supposed to be an optimisation.

So: commit first, then index. Which leaves a gap, and the gap is real.

   COMMIT succeeds   <- the listing is now published, durably
   ...                  process is killed here
   index_property()  <- never runs

   Postgres says PUBLISHED. Search has never heard of it.

The module says so out loud rather than pretending:

**What it does not do:** it is not transactional. The commit succeeds and *then* the index is
updated, so a crash in between leaves the two out of step. That is deliberate — the alternative
(indexing inside the transaction) is worse: a slow or dead Elasticsearch would then fail writes
that have nothing wrong with them.

Three ways to narrow the gap

Retry on failure. If the index write returns an error, queue it and try again. This handles the common case — Elasticsearch restarting — and StayHub does it:

        if not indexed:
            outbox_service.enqueue(
                self.db,
                indexer.TOPIC_PROPERTY_CHANGED,
                {"propertyId": str(prop.public_id), "reason": "index-write-failed"},
            )

It does not handle the process dying between the commit and the enqueue. The code says that too, because a comment claiming a guarantee the code does not provide is worse than no comment.

The transactional outbox. The complete fix: write the intent to index as a row in the same transaction as the change, and let a worker do the actual indexing. Now there is no gap — if the commit succeeded, the instruction is durable. It costs latency, since the index is updated when the worker next polls rather than immediately. The queues post is about this pattern.

Change data capture. Read the database’s replication log and project it outward. Nothing in application code can forget, because it is not in application code at all. It is the most robust answer and it is a substantial piece of infrastructure.

The property that makes it survivable

Whatever you choose, some divergence will happen. What makes it recoverable rather than fatal is that the index is derived data: Postgres is authoritative and the index is a copy that can be thrown away.

So there is a repair path, and it is one call:

    def reindex_all(self) -> int:
        """Rebuild the whole search index from Postgres. The repair button."""
        return indexer.rebuild_index(self.properties.all_for_reindex())

This is the single most important idea in the post. Decide which copy is the truth, and make every other copy rebuildable from it. Then eventual consistency is a temporary annoyance rather than corruption, and “how do you recover?” has an answer that fits in a sentence.

A system where two stores are both authoritative and they disagree has no repair path, because there is no way to know which one is right. That is the situation to design yourself out of.

Handlers must be idempotent

Retrying implies delivering more than once. The index write survives that by construction:

        client.index(
            index=settings.elasticsearch_index,
            id=str(prop.public_id),
            document=to_document(prop),
        )

The document id is the property’s public id, so indexing the same property five times produces exactly the same index as indexing it once. That is what makes at-least-once delivery safe here rather than merely tolerable.

There is a second, subtler decision in the retry handler: it re-reads the property from Postgres rather than replaying a snapshot captured when the event happened. For derived data that is correct — if the listing was edited three more times while Elasticsearch was down, writing the first snapshot would store a stale document and then mark the job done, leaving search confidently wrong. Re-reading collapses all four changes into one correct write.

The opposite is true for an email about a booking: that describes a moment, so it should carry the moment. The question to ask is does the consumer need the event as it happened, or the world as it is now?

Detecting divergence before a user does

“It will converge eventually” is a claim, and a claim nobody checks is a claim that quietly stops being true. If two copies can disagree, something should be looking.

The cheapest useful check is a count comparison on a schedule — how many published listings does Postgres have, and how many documents are in the index?

   every 5 minutes:
       postgres: SELECT count(*) WHERE status='PUBLISHED' AND NOT deleted
       index:    GET /_count

   equal            -> fine
   differ slightly  -> normal; writes are in flight
   differ and STAY  -> alert. something is not converging.

The distinction on the last two lines is the whole design of the check. A momentary difference is the system working as intended; a difference that persists across several samples is the failure mode. Alerting on the first produces noise nobody reads, which is worse than no alert.

Where correctness genuinely matters, the stronger version compares content rather than counts — hash a set of fields per record on both sides and compare the hashes, usually over a sample rather than everything. That is what a reconciliation job is, and financial systems run them nightly for exactly this reason.

A related habit that costs nothing: expose the lag as a metric. Replication delay in seconds, queue depth, the age of the oldest unprocessed message. Staleness you can graph is staleness you can reason about; staleness you cannot measure is one you will discover from a support ticket.

Conflicts, when both sides can write

Everything above has one writer and several derived copies, which is the easy case — there is always an obvious winner. When two replicas both accept writes, that stops being true, and you need a rule for reconciling them.

Last-write-wins deserves particular suspicion, because it is the default in several systems and it depends on clocks. Two servers whose clocks differ by 50ms will disagree about which write came second, and the loser is discarded with no record. The classic illustration is a shopping cart where two devices add different items and one item simply disappears — which is why Dynamo-style systems modelled carts as a set union instead.

The practical advice is to design so this never arises: one writer per piece of data. Multi-master writing is a genuinely hard problem and it is almost never worth adopting to solve a scaling issue that a single primary with replicas would have handled.

Choosing a model, per feature

Consistency is not a property of a system, it is a property of an operation. The same application wants different answers for different things:

Being able to produce a table like that for the system on the whiteboard is a genuinely strong signal, because it shows you know consistency has a price and are choosing where to pay it.

Distributed transactions, and why you probably will not use one

The obvious question after all of this: if two datastores cannot be updated atomically, why not use a protocol that makes them?

Two-phase commit does exist. A coordinator asks every participant to prepare, and if all agree, tells them all to commit:

   PHASE 1   coordinator -> "can you commit?" -> A: yes
                                              -> B: yes
   PHASE 2   coordinator -> "commit"          -> A: done
                                              -> B: done

   The failure that ruins it:
   PHASE 1   both say yes  (both are now HOLDING LOCKS)
             coordinator dies before phase 2
             -> A and B wait. Forever. Holding locks.

That is the blocking problem, and it is why 2PC is rare outside a single database cluster. It converts the coordinator into a component whose failure freezes every participant, which is precisely the availability property you were trying to improve.

The pattern that replaced it is the saga: a sequence of local transactions, each with a compensating action if a later step fails.

   book the room     ok      compensate: cancel the booking
   charge the card   ok      compensate: refund
   send confirmation FAILED
                             -> run the compensations backwards

Sagas are eventually consistent by construction and they leak: for a moment the room is booked and the card is not charged, and someone can see that state. There is no way around it — you are trading atomicity for availability, which is the same trade as everywhere else in this post. The Amazon post works one through in detail, because checkout is the canonical example.

The practical advice is the boring one: arrange your boundaries so that the things which must be atomic live in one database. StayHub creates a booking and its payment record and its outbox message in one transaction, precisely so no saga is needed for the part that matters. Sagas are for what genuinely crosses a boundary — a third-party payment provider — not for boundaries you drew yourself.

What to say when asked

• CAP is about behaviour during a partition. P is not optional; the choice is refuse or diverge.
• PACELC is the version you use daily — even healthy, consistency costs latency.
• Name the model per operation, not per system.
• Read-your-writes and monotonic reads are the two users actually notice.
• Two datastores cannot be updated atomically. Say which one is the truth.
• Make every derived copy rebuildable, and know where the rebuild button is.
• Anything retried must be idempotent, and idempotency is usually achieved by choosing the right key rather than by adding a check.

And the framing to carry into the case studies: consistency questions are almost never “is this system consistent?” They are “which copy is the truth, how far behind can the others get, who notices, and how do I rebuild them?” A design that answers those four has answered the topic.

Next: message queues and asynchronous work, which is the complete answer to the dual-write gap this post left open.