Which of Your Invariants Actually Needs a Lock?

Two things happen to account 7741 on the same Tuesday afternoon.

A £9.99 renewal charge gets appended to its ledger. And somewhere else in the same service, a rule says the balance on that account must never drop below zero.

Same table. Same team, same deploy, same afternoon. One of those can run in London and Virginia at the same instant, forever, with the two regions never once speaking to each other, and it will always be right. The other one cannot be made safe by any database, at any isolation level, at any price you are willing to pay.

The difference has nothing to do with the database.

Why the append is free and the floor isn’t

Take the append first, because it’s the easy one and its easiness isn’t obvious.

London and Virginia both take a charge for 7741 in the same second: £9.99 from the renewal, £2.50 from a metered overage. Each region writes its own row and tells its own customer it worked. Later the two sets of rows meet. Union them in either order and you get the same two rows, and the balance you compute from them is £12.49 either way.

There’s no ordering to get wrong, because there is no ordering. The ledger is a set of facts and the balance is a function of that set. Nothing in the second write depends on having seen the first.

Now the floor, on the same account, an hour later. There’s £10 left. London sees £10 and approves a £9.99 charge. Virginia sees £10 and approves a £9.99 charge. Both decisions were correct where they were made, against a database state that was genuinely valid at the time. Merge them and the balance is minus £9.98.

You cannot fix that with a better merge function, because there is nothing to fix. Both sides were right. The merged state is wrong. The only thing that could ever have prevented it is one region asking the other for permission before answering the customer, which is the round trip, which is the cost.

That gap between “both sides were right” and “the answer is wrong anyway” is the entire subject, and it has a proper name.

The test has a name, and it comes with a table

It’s called invariant confluence, from a 2015 VLDB paper by Bailis, Fekete, Franklin, Ghodsi, Hellerstein and Stoica (the extended version is on arXiv). The definition is almost disappointingly plain: a set of transactions is I-confluent with respect to an invariant if, for any two states you could reach from a common ancestor by running those transactions, merging the two states gives you something still valid.

That’s the ledger and the floor, formalised. Two valid states, one merge, one question: does the merge survive?

The theorem attached to it is the part worth pinning above your desk. A system can keep an invariant globally valid while staying available, converging, and never coordinating if and only if the transactions are I-confluent with respect to that invariant.

Both halves of that matter, and teams usually only hear one. If the test says no, then no database, no vendor, no isolation level and no amount of money buys you the coordination-free version, because one doesn’t exist.¹¹The forward direction is a partitioning argument, the same shape as the CAP proof: construct a partition where a replica cannot tell a safe execution from an unsafe one using only local information, and it has to either block, lie, or diverge. The backward direction is by construction, and it’s the easy half. If the test says yes, then any coordination you’re currently doing is a choice you made, usually by accident, usually years ago.

And the paper does the tedious bit for you. It works through sixteen combinations of invariant and operation drawn from ordinary SQL and ordinary data types, and publishes the verdict for each one with a proof number. Pick the rule you’re defending and the thing you want to do to it:

Ten of the sixteen are free. Not “free if you buy the right database”, not “free at read committed”. Free, in the sense that a correct coordination-free implementation provably exists.

Notice what the rows are keyed on, though. Not the invariant. The invariant and the operation. Look at the three foreign key rows and they don’t agree with each other.

Insert and delete are not the same question

A foreign key under insertion is I-confluent. A foreign key under deletion isn’t. A foreign key under cascading deletion is I-confluent again.

Same constraint, same schema, same afternoon. The reasoning is short enough to repeat at a design review: a dangling row means a parent that vanished, merges in this model only ever add rows, so under insert-only workloads nothing can vanish and nothing can dangle. Start deleting and the parent can vanish. Make the delete cascade and it takes its children with it, so there’s nothing left to dangle.

The same authors went and measured what that means in a codebase people actually ship. They surveyed 67 open source Ruby on Rails applications and found over 9,950 uses of application-level validations, which were used more than 37 times as often as transactions. Then they ran I-confluence over the lot.

Under insertions, 86.9% of built-in validation usage by volume is safe. Under deletions, 36.6%.

Same applications. Same validations. Same code. Change the verb and more than half the safety evaporates, and nobody writing the validation had any reason to notice, because Rails presents validates_uniqueness_of and validates_presence_of as the same kind of thing.

The number I find hardest to shake is from the experiment they ran afterwards. Sixty-four concurrent requests creating the same key, a hundred rounds. With validations switched off entirely: 6,300 duplicate records. With validations on and three worker processes: 249. With a plain unique index in the database instead: zero.²²They also found, while running this, that PostgreSQL’s serializable snapshot isolation admitted duplicates for this exact workload, reported it as bug #11732, and noted the behaviour still stood as of March 2015. I haven’t checked whether it still does, and you shouldn’t assume either way. The point is narrower: “just turn on serializable” is a plan that depends on your database implementing it, which is a thing to verify rather than assume.

So the application-level check didn’t make the invariant safe, it made it about ten times less unsafe, which is the worst possible outcome because it looks like it works in staging. The declarative constraint made it safe, because the database could choose to coordinate on exactly that one thing.

Which brings us to the constraint almost nobody remembers declaring.

Your primary key is a uniqueness constraint you never chose

Row five in the table: AUTO_INCREMENT, on insert, not I-confluent.

Think about what you actually asked the database for when you typed SERIAL. You asked it to hand out one specific value, the next one, and one specific value is the single thing no replica can choose alone. Two regions each pick 8,412,551, both are locally fine, the merge has two rows with the same primary key. That’s the same Stan-and-Mary counterexample from the paper, with your schema on it.

Now look at the row directly above it. Uniqueness where the database gets to choose some value, rather than a value you named, is I-confluent, as long as replicas know who they are and draw from their own slice of the namespace.

Those two rows are the same constraint. The only thing that changed is whether you asked for “id 8,412,551” or “an id nobody else will pick”. One of those costs a round trip on every insert for the rest of the system’s life and the other costs nothing, and the difference lives entirely in your schema file.

The vendors know. PostgreSQL’s documentation says out loud that the value from nextval isn’t reclaimed if the calling transaction aborts, specifically to avoid blocking other transactions drawing from the same sequence, and concludes that its sequences “cannot be used to obtain gapless sequences”. Postgres gave up the sequential half of your sequential id decades ago to dodge exactly this coordination. It just never sent you a note saying so.

TiDB goes further and hands out ids in blocks: 30,000 per node by default, with the documentation stating plainly that values are then only monotonic per server, and that AUTO_INCREMENT “might cause hotspot in production environments”, recommending AUTO_RANDOM instead. If you insist on strict MySQL-style behaviour, their own note says that before v6.4.0 every single id allocation required a distributed transaction against the storage layer, and that the fix was to build a centralised allocating service to do it in memory. A centralised service is, of course, coordination. They just made it cheap.

Cockroach Labs skips the diplomacy: monotonically increasing keys create hotspots for reads and writes in a distributed database, and the first recommendation on the list is gen_random_uuid().

Here’s the arithmetic, because it’s a division and not much else:

Drag it down to a one millisecond round trip and the strict allocator still caps you at a thousand inserts a second on that one counter. Drag it out to a coast-to-coast hop and it’s twelve. Twelve inserts a second, from a design decision that took nobody thirty seconds to make.

You didn’t pick a database with a coordination problem. You wrote down a coordination problem and then went shopping for a database.

Sometimes, though, you write one down on purpose, and then the only question left is what it costs.

What a “yes” actually costs

The same paper measured that ceiling. Not the throughput of a particular product, but the ceiling imposed by having to block for agreement at all, computed from atomic commitment latency:

Seven orders of magnitude between the top bar and the bottom one, and the thing that moves you down the chart is never the code. It’s how many servers have to agree and how far apart they are. Two servers in one datacentre buys you a little over a thousand a second. Eight servers in that same datacentre buys you 173, because you’re now waiting on the slow tail of eight replies instead of two. Virginia to Oregon buys you twelve. All eight availability zones buys you two.³³The same group measured the other side of this in their work on Highly Available Transactions, where dropping the coordination requirement is worth two to three orders of magnitude over a wide-area network. Different framing, same physics: the win isn’t a faster protocol, it’s not having to wait for anybody.

I’ve spent most of a decade on the good side of that chart without thinking about why. A Kafka to ClickHouse pipeline moving a billion rows an hour, which is what we ran at Zeta, works at that rate for one boring reason: no row in it asks any other row’s permission to exist. Appends, roll-ups, immutable facts. The instant you put one genuinely non-I-confluent rule in that path, the whole pipeline inherits the bottom bar of this chart, and no amount of partition tuning gets it back.

Where those servers physically sit, and what that does to your p99, is a whole post of its own. This one is the prior question: whether you should be buying the round trip in the first place. Because sometimes you genuinely have to.

The ones you can’t argue away

Some invariants are just load-bearing, and the honest move is to pay.

TPC-C is the worked example, and the result is more encouraging than you’d expect. The benchmark declares twelve consistency conditions. Run the analysis and ten of the twelve are I-confluent: they’re materialised view roll-ups and foreign key relationships, and both of those only regulate when updates become visible, which is a different problem from agreement. The two that fail are both sequential id assignment, per district.

So they didn’t remove the coordination. They shrank it. The New-Order transaction generates a temporary non-sequential id, does all its real work coordination-free using that, and then swaps in a real sequential id at commit time by incrementing one counter and recording the mapping in a lookup table. All the coordination that remains is confined to a single server, which means it never becomes a distributed commit. The result scales linearly to over 12.7 million New-Order transactions a second on 200 servers, and the paper reports it as a 25-fold improvement on the previous published figure for that cluster size.

That’s the general shape of the fix, and the balance floor takes it too. You can’t make “the global balance never goes negative” I-confluent. What you can do is hand each region a slice of the balance up front, so the rule becomes “this region’s allowance never goes negative”, which has exactly one writer and therefore no merge to lose. You coordinate when a region runs out and wants more, not on every charge. That’s the same manoeuvre as swapping SERIAL for a UUID: you didn’t beat the theorem, you changed the invariant so the theorem stopped applying.

Real billing systems do a version of this constantly, and the reason they get complicated is that the slices need reclaiming, the allowances expire, and the state machine that tracks all of it outlives every process that touches it.

None of which helps if you got the invariants wrong, and that failure mode is quieter than it sounds.

Where this falls over

That’s not a footnote, it’s the main risk. Every team I’ve worked on has had invariants that live in one person’s head and no schema. “We never bill the same subscription twice for the same period.” “A refund can’t exceed what was captured.” “Entitlement follows the last successful payment, not the last event.” None of those are in a CHECK constraint anywhere. Run I-confluence over the constraints you did write and you get a clean bill of health for a system that can still do something appalling on a Tuesday.

There’s a second limit worth knowing. Recency guarantees, the “read your own writes” family, aren’t invariants over database states at all. They’re statements about execution, and they don’t fit through this door. If your requirement is that a user sees their own charge immediately after making it, that’s a real requirement, and this framework will not tell you it’s free.

If you want the same result stated one level up, from states to programs, the CALM theorem is the companion piece: the programs with consistent, coordination-free implementations are exactly the ones expressible in monotonic logic. Monotonic means the answer only ever grows as you learn more, which is a very precise way of saying what our ledger has and our balance floor doesn’t.

What I’d do about it

• Write the invariants down where a machine can see them. A UNIQUE index that the database enforces beats a validator in your application layer by roughly a factor of infinity, because the database can coordinate on exactly one thing and your application can only race.
• Ask the question per operation, not per table. “Is this foreign key safe” has no answer. “Is this foreign key safe under the deletes we actually do” has one, and it’s often no.
• Audit your primary keys first. It’s the highest-volume coordination in most systems and the one with the shortest fix. If nothing in your product shows a user a sequential number, you’re paying for an ordering nobody reads.
• When the answer is genuinely no, shrink the coordination instead of removing it. Confine it to one server, one key, one moment at commit. Ten of TPC-C’s twelve invariants being free is what makes the other two affordable.
• Say out loud which invariants aren’t written down. That list is the real risk register, and it’s usually shorter than people fear and more alarming than they expect.

The reason I keep coming back to this paper isn’t the theorem. It’s that it moves the argument to somewhere an argument can actually be settled. “Should we use serializable here” is a question about taste and fear, and it goes round the room twice and lands wherever the most senior person was leaning.

“What exactly are we protecting, and does it survive a merge” has an answer, and it’s in a table somebody already published.

Sources

Papers

• Bailis, P., Fekete, A., Franklin, M. J., Ghodsi, A., Hellerstein, J. M. and Stoica, I. Coordination Avoidance in Database Systems, PVLDB 8(3), 2015.
• Bailis, P., Fekete, A., Franklin, M. J., Ghodsi, A., Hellerstein, J. M. and Stoica, I. Feral Concurrency Control: An Empirical Investigation of Modern Application Integrity, SIGMOD, 2015.
• Bailis, P., Davidson, A., Fekete, A., Ghodsi, A., Hellerstein, J. M. and Stoica, I. Highly Available Transactions: Virtues and Limitations, VLDB, 2014.
• Hellerstein, J. M. and Alvaro, P. Keeping CALM: When Distributed Consistency is Easy, 2019.

Documentation

• PostgreSQL. Sequence Manipulation Functions.
• PingCAP. AUTO_INCREMENT, TiDB documentation.
• Cockroach Labs. SQL Performance Best Practices.

@article{ghosh2025invariants,
  title = {Which of Your Invariants Actually Needs a Lock?},
  author = {Ghosh, Krish},
  journal = {krishghosh.com},
  year = {2025},
  month = {October},
  url = "https://krishghosh.com/writing/invariants-that-need-a-lock"
}