Why concurrency is a different kind of problem

Why does ten times more throughput create a hundred times more conflict, and how should we think about correctness when many users act at once?

The failure mode changes

Think about the topics that come before concurrency in a database: how bytes sit on a disk, how rows are laid out, how data is encoded, how indexes find rows. All of them answer one question: "what does it cost to represent bytes and reach them?" You can read all of them as if the database had exactly one user. The way they go wrong is that the system is slow or expensive.

Concurrency control is the first topic where the number of actors is the subject, and the first where the failure mode is wrong, silently, and only sometimes. Two things change in a basic way.

Change 1: we judge a schedule, not a state

For storage questions you can point at bytes and ask whether they were laid out well. Here the thing being judged is a schedule: an ordering of operations taken from several transactions. A system is correct if every schedule it allows is equivalent to some serial schedule (one transaction at a time).

You cannot look at a database state and tell whether its concurrency control is correct. The bug lives in a history, not in a state. That is why this topic resists the debugging habits that everything below it taught you: there is often nothing wrong to see in the data afterwards. Two lost updates produce a perfectly normal-looking balance. It is just the wrong normal-looking balance.

Change 2: the cost is combinatorial, not physical

A lock acquisition is one CAS on a hash bucket, about 100 ns. A commit is one log write. Nothing here is expensive in the way a disk seek or a network shuffle is expensive. What is expensive is conflict. Conflict is a property of the workload and of how many transactions you insist on running at the same time. You cannot buy your way out with faster hardware, and that is new.

---

The arithmetic that governs this mechanism

This calculation is worth doing once, because everything later is built on it.

Step 1: how many transactions are in flight? Little's Law says that to sustain an arrival rate λ when each transaction stays in the system for W seconds, you must have

transactions alive at the same moment. This is not a decision. It is an identity. Here it is a correctness constraint, not only a capacity one: the more transactions overlap, the more chances for them to disagree.

Step 2: how many conflicts? Suppose each of the L live transactions touches k items out of an effective key space of N items, and assume every item is equally likely.

• Two given transactions each have k items, so the chance that they share at least one item is about k²/N (k × k pairs of items, each pair equal with probability 1/N, when this number is small).
• There are about L²/2 pairs of live transactions.

So the expected number of conflicts at any moment is about

Useful work rises in a straight line. Conflict rises with the square. The two lines cross, and that crossing is why the throughput curve of every transactional system turns over (it goes up, peaks and then falls) instead of flattening.

This is exactly what Tomas saw. Going from 800 to 8,000 orders per second multiplied the number of transactions in flight by ten and the number of colliding pairs by about a hundred.

The same square appears elsewhere

This quadratic is not new. In scalability theory (the Universal Scalability Law) there is a "coherency" term that grows as N(N−1): the cost of every worker needing to agree with every other worker. You may know it from false sharing (several CPU cores fighting for one cache line) and from incast (many servers answering one server at the same time). For transactions the pairwise term is literal, not an analogy: its coefficient is the probability that two concurrent actors touch the same item.

The assumption nobody can check: uniform access

The formula needs N, and this is the assumption the whole topic makes and cannot verify. The arithmetic above assumes every item is equally likely to be touched. Real access patterns are skewed (statisticians say Zipfian: a few keys get most of the traffic). So the effective N is not the number of rows you store. It is smaller, often by two or three orders of magnitude (100 to 1,000 times).

Independence is assumed everywhere and true almost nowhere. Who pays? The hot key, the popular account, the one partition that every writer touches on the hour. For Kestrel: 50,000 seats exist, but if 90% of buyers want 200 floor seats, the effective N for most buyers is closer to 200 than to 50,000.