The following is an excerpt from 'The Infinite Machine'

Transactional Contention is $O(N²)

Distributed programming environments tend to work with eventual consistency; most services give you a pretty good if slightly stale view of data, trading off consistency for speed / availability / efficiency. Consistency turns out to be expensive in a distributed environment.

But if you work on back-end systems, you’ll eventually find you have to count and/or update things in a strongly consistent manner.

Examples might include updating a leaderboard in a game when results are coming in concurrently and unpredictably. Or you might want to total up some amounts in a database which is also being written to unpredicably. Or there’s always the classic banking scenario: transfer $X from account Y to account Z.

Programmers tend to think in terms of critical sections in these situations. You want something like this:


Usually, the only tool for this in a database or distributed back-end system is a transaction, which looks like this:


This looks like the ticket!

But wait, the semantics are slightly different…

In a critical section, usually modelled with something like a semaphore, mutex, monitor, or the like, the idea is that many threads (or processes or etc) try to enter together. One gets in, others go in a queue. When the thread in the critical section completes, one from the queue is woken up and given the critical section, and so on until the queue is empty.

In a transaction, however, things work differently. Many threads of execution can enter (begin) the transaction and try to do things. These things don’t take affect until the transaction tries to commit. At that time, the system checks to see if any other transaction has committed while this one was underway (changing the data under our transaction). If not, our transaction can be committed; all actions take affect. Otherwise, the transaction rolls back; it fails, and no actions take affect. If a transaction rolls back, it can be retried until it succeeds.

These are superficially similar constructs. The most important way in which they are similar is that the protected data is only operated on by one thread of execution at a time, and that thread both reads and writes consistently. When the critical section’s queue is empty, or all transactions have been retried until success, all processing has been applied serially and successfully.

But the important way in which they are different is that, while a critical section implements a queue to store waiting threads/processes, a transaction lets many threads/processes go ahead, but then causes all but one of them to fail. The failed transactions do expensive work, and need to be retried.

If you’re working in a distributed system, and you’re thinking in terms of critical sections, you might be tempted to ignore this distinction. But you really shouldn’t. Under load (which is when you really care), the performance of critical sections and transactions is remarkably different...


Click Here to Read More

Emlyn O'Regan is a Co-Founder and the CTO of xapiapps, and the author of "The Infinite Machine"

Start Your Free Trial

Get the latest updates by email