Highly available transactions and invariant confluence
Which guarantees survive total availability, and which of your invariants actually need coordination?
The availability frontier: Highly Available Transactions (HAT)
HAT is the first result that spans both hierarchies. Its question: which transactional guarantees are achievable with total availability?
| Achievable without coordination | Not achievable with total availability |
|---|---|
| Read Committed | Snapshot Isolation |
| Monotonic atomic view | Repeatable Read |
| Item-cut isolation | Serializability |
| Read atomicity | Linearizability |
| The four session guarantees | Strict serializability |
| Transactional causal consistency (the ceiling) | Global uniqueness constraints |
| Bounded-value constraints | |
| Referential integrity under deletion |
Read atomicity means a reader sees either all or none of another transaction's writes. Monotonic atomic view means: once a transaction has seen one effect of another transaction, it sees all of that transaction's effects.
Why does Snapshot Isolation land on the unavailable side? Derive it, because it surprises people who think of SI as a weak level. SI must prevent lost update. Preventing lost update requires detecting that two transactions wrote the same item. That requires the partitions holding those two writers to communicate. First-committer-wins is a coordination point by definition. The cheapness of SI in a single-node engine is not portable.
So the frontier is a line, not a gradient: causal+ with read atomicity is the strongest transactional guarantee compatible with total availability. Everything above costs a round trip and becomes unavailable under partition. That sentence explains the design of every globally distributed, always-on database.
Invariant confluence: the theorem a practitioner can run
Bailis and co-authors. Given an invariant I and a set of transactions T, I is I-confluent with respect to T if: whenever two states reachable from a common ancestor by executing T both satisfy I, their merge also satisfies I.
The result is an if and only if, not a heuristic: a coordination-free, globally I-valid execution exists exactly when I is I-confluent. Coordination is required for non-I-confluent invariants and for nothing else.
The worked cases are the payoff, because they are things that exist in real schemas:
| I-confluent: no coordination | Not I-confluent: coordination required |
|---|---|
| Per-row check constraints, types, NOT NULL | Uniqueness (usernames, application-assigned keys) |
| Foreign keys under insert only | Foreign keys under deletion |
| "≥ k" where transactions only increase | "≤ k" where transactions increase: inventory, balance ≥ 0, seat counts |
| Set membership, union, unbounded counters | "At most n of X" in any form |
The structural characterization: I-confluence fails exactly when the invariant is an upper bound on a quantity that transactions push upward, or a uniqueness condition. Two branches, each locally legal; the merge is illegal. Nothing else on the list is mysterious once you see that shape.
The one escape: partition the slack
When I-confluence fails, there is one escape. It appears here in three costumes: escrow transactions, the bounded counter of Sessions, convergence and quorums, and here as the general move. Split the global budget across replicas, so each replica can act locally until its share is spent. (How a system stays out of coordination in general is Coordination avoidance.) It comes with arithmetic, which makes it a design decision and not a trick:
coordination rate ≈ consumption rate / slack per replicaThe cost is the stranded slack: units reserved at a replica where nobody is buying. It is the same trade as Hi/Lo sequence-block allocation (a service takes a block of ids and hands them out locally), per-producer sequence ranges, and distributed rate-limiter token pre-allocation. All one mechanism.