Transactions, concurrency control and isolation

Two customers on a shared tablet open the same booking page. One seat remains. Both read it and both write a purchase, and the database accepts both without complaint. The fault is not in the application logic but in what the system promised about how the two transactions could interleave.

That promise is isolation, and this lecture argues that naming a level does not deliver it. The SQL standard names its levels after a checklist of anomalies, so a level reads like a guarantee, but the names do not bind an implementation and two engines can advertise one level and permit different outcomes. The level short of full serialisability can clear the whole checklist and still allow a result no serial order of the transactions could produce. Isolation is a design decision priced in named anomalies, in aborts and retries, and in availability. This fourth unit prices two queries running at once.

The transaction groups the failures, and only partly

Gray (1981) restates the transaction concept. A transaction is a transformation of state with atomicity, durability and consistency, the unit that lets a system undo or redo an application's steps as a whole. He lists what the concept leaves unsettled, including transactions lasting for days or months.

Making that boundary real is the recovery method's job. Mohan and colleagues (1992) present ARIES, which supports fine-granularity locking and partial rollbacks through write-ahead logging. They report its implementation in IBM systems including DB2. Undoing part of a transaction requires knowing what it did, so the log makes atomicity real.

Serialisability is the standard, and it is stated on schedules

The criterion behind isolation is serialisability: an interleaved execution must be equivalent to some serial execution of the same transactions. Eswaran, Gray, Lorie and Traiger (1976) define transaction, consistency and schedule. They show that consistency requires that a transaction cannot request new locks after releasing a lock. They also argue that a transaction must lock a logical rather than a physical subset of the database, specified by predicates. The first result is the condition behind two-phase locking. The second is where phantoms come from, because a transaction guarding the rows that match a condition can miss a new row appearing after the read.

Kung and Robinson (1981) supply the sharpest alternative to locking, two families of non-locking control that are optimistic because they rely on transaction backup and on the hope that conflicts will not occur.

The levels name anomalies, and the names do not bind

The standard expresses isolation through phenomena rather than a mechanism, and Gray, Lorie, Putzolu and Traiger (1976) are the ancestor of that habit. Their paper introduces the granularity of lockable objects and the concurrency-overhead trade-off, and defines degrees of consistency numbered zero to three.

Berenson, Bernstein, Gray and colleagues (1995) show what is wrong with it. The ANSI SQL-92 level definitions fail to characterise several popular isolation levels, including the standard locking implementations, and the phenomena themselves are stated ambiguously. Adya, Liskov and O'Neil (2000) add that the revisions proposed to fix them allow only pessimistic, locking implementations. They give portable specifications that also cover optimistic and multiversion control, without which no level could be checked against its own name.

Snapshot isolation shows the checklist is not the standard

Berenson and colleagues (1995) do more than criticise. They define snapshot isolation, a multiversion scheme in which a transaction reads from a consistent snapshot, and note that it avoids the three standard anomalies. A transaction running under it will not read uncommitted data, will not see a value change underneath it, and will not see a phantom. It can still write an outcome no serial order allows.

A constructed interleaving shows the gap. Two transactions each read the same pair of account balances, and each checks that the total is above an overdraft limit. Each then withdraws from a different account. Under snapshot isolation both read the same consistent snapshot, both see a total above the limit, neither writes the row the other read, and both commit. Every anomaly on the checklist is absent, and the final state is one no serial order produces. Whichever transaction ran second would have seen the other's withdrawal and refused. The interleaving is constructed to exhibit the mechanism. It establishes that a level defined by the checklist can permit an outcome the criterion behind isolation forbids.

Fekete, Liarokapis, O'Neil and colleagues (2005) make the gap central. Snapshot isolation is not serialisable in all cases. TPC-C runs under it without anomalies, yet all major database products ship with default non-serialisable levels, and the authors suspect numerous isolation errors occur daily at large sites. Their remedy is a theory characterising when non-serialisable executions can occur, so safety can be demonstrated rather than assumed. Applications may run under them when shown not to produce serious errors. Geng and colleagues (2024) solve SMT constraints over an observed trace of a weakly isolated data store to predict a feasible interleaving that no serial order allows, and report that over 99 per cent of their predictions hold on four benchmarks.

The case is not hypothetical: Fekete and colleagues (2005) record that their snapshot isolation has been implemented by Oracle and by Microsoft SQL Server. That marks the honest boundary of the example above: the anomaly is possible, and whether it is present is a property of the workload.

The price of correctness is paid in detection, not in application code

Once an anomaly is named, the design question is what removing it costs and who pays. Cahill, Rohm and Fekete (2009) describe a change to a database's concurrency control that detects and prevents snapshot isolation anomalies at run time for arbitrary applications, giving serialisable isolation. The earlier remedy was to change each application by adding explicit locking or artificial update conflicts. The cost moves to tracking dependencies and aborting transactions that would break serialisability, not to application logic.

Ports and Grittner (2012) report the production price. They implement PostgreSQL's serialisable level on serialisable snapshot isolation, the first such implementation in a production release, and describe a new lock manager and a technique for bounding memory use. Their evaluation finds performance only slightly below snapshot isolation and significantly better than two-phase locking on read-intensive workloads. The strongest practical level is therefore purchasable at a measured price, but that price belongs to one engine. A level is a specification; what it costs is an implementation.

Isolation is bounded by availability

Bailis, Davidson, Fekete and colleagues (2013) consider highly available transactions, guarantees that do not suffer unavailability during partitions or incur high network latency. They analyse which ACID isolation and distributed consistency guarantees can and cannot be achieved within that constraint, quantifying a benefit of two to three orders of magnitude over wide-area networks. The argument is negative. Some guarantees are unattainable whichever mechanism is chosen, so the design act is to name the one given up.

Harding, Van Aken, Pavlo and colleagues (2017) measure the setting that produces the constraint. They quantify the effects of distributing transactions across servers on concurrency control protocols, and evaluate six classic and modern protocols in an in-memory framework called Deneva. Together the two papers move the question into the architecture: which operations need serialisability, and which can live with less in exchange for availability.

Contested question: who owes the application serialisability?

The literature disagrees about who owns the obligation.

One position holds that the engine owes it, and that asking programmers to reason about anomalies passed a vendor's problem to the application. Adya, Liskov and O'Neil (2000) rewrite the definitions so a level can bind any implementation. Cahill, Rohm and Fekete (2009) detect and prevent the anomalies automatically. Ports and Grittner (2012) show the mechanism shipping close to snapshot isolation in performance, which removes the usual reason to decline it. On this view a system should be set to serialisable wherever that is affordable.

The opposing position holds that serialisability is a property of the workload rather than of the engine's menu, and that the application must own it. Fekete and colleagues (2005) supply both the classical justification and the method, deciding by theory whether a given application has serialisation anomalies under snapshot isolation and applying the test to TPC-C. Bailis and colleagues (2013) supply the harder version. Where a system must remain available, some guarantees cannot be had at all, so the application must tolerate what remains.

The engine's side has shipped implementations and benchmarks. The application's side has a theory and worked applications, and its central empirical claim, that isolation errors are common in practice, is offered as a suspicion rather than measured. What would settle it is one study pricing both routes on the same system, running one representative application at its strongest available level and at a weaker one, counting the failures the weaker level produces against the aborts the stronger one costs, and adding the availability each buys during a partition.

Rate each side by its evidence. Adya, Liskov and O'Neil (2000) rewrite a definition, Cahill, Rohm and Fekete (2009) construct a mechanism, and Ports and Grittner (2012) report a measured cost. Fekete and colleagues (2005) supply a theory applied to one benchmark, and Bailis and colleagues (2013) prove which guarantees an available system cannot hold. The strongest objection is that a serialisable default removes a class of error before anyone reasons about it, so a per-workload argument can be sound and still the slower route to a safe system. While the dispute is open, a designer sets the strongest level the workload can afford and records what that level still permits.

Where the argument is heading

The direction of travel is towards making weak guarantees nameable rather than assuming strong ones. Ports and Grittner (2012) put serialisable snapshot isolation into a production release and publish its cost, turning the top level into an engineering default. Bailis and colleagues (2013) do the matching work at the other end, replacing a vague promise of eventual consistency with a taxonomy of what an available system can and cannot guarantee. Harding and colleagues (2017) point at the remaining hard case, the distributed protocol whose scalability is limited by coordination, and the next unit follows that thread. If a level does not bind an implementation, the field still needs a way to state which anomalies a given system and workload permit, and what excluding each costs.

The sources this unit rests on

• Gray, J. N., Lorie, R. A., Putzolu, G. R. and Traiger, I. L. (1976). The authors introduce lock granularity, the concurrency-overhead trade-off, and degrees of consistency zero to three, the ancestor of the isolation ladder, where a degree packages restrictions rather than naming a mechanism. No abstract is indexed, so this note rests on the paper itself.
• Gray, J. (1981). Gray restates the transaction concept as a transformation of state with atomicity, durability and consistency, and lists what it leaves unsettled, including transactions lasting for days or months. It supplies the unit's definition and its stated limits, not a measured comparison.
• Eswaran, K. P., Gray, J. N., Lorie, R. A. et al. (1976). The authors show that consistency requires that a transaction cannot request new locks after releasing a lock, and argue that it must lock a logical rather than a physical subset, specified by predicates. That is the theory behind two-phase locking and the phantom.
• Kung, H. T. and Robinson, J. T. (1981). The authors present two families of non-locking concurrency control, optimistic because they rely on transaction backup and on the hope that conflicts will not occur.
• Berenson, H., Bernstein, P., Gray, J. et al. (1995). The authors show that the ANSI SQL-92 levels fail to characterise several popular isolation levels, including the standard locking implementations, and define snapshot isolation. It carries the unit's thesis: a system can clear the whole checklist and still permit an outcome no serial order allows.
• Adya, A., Liskov, B. and O'Neil, P. (2000). The authors argue that the ANSI definitions are ambiguous and that proposed revisions allow only pessimistic, locking implementations, and give portable specifications covering optimistic and multiversion schemes too. The definitions had to be made mechanism-independent before a level could bind one; the DOI registrar dates the proceedings to 2002, where the conference was ICDE 2000.
• Fekete, A., Liarokapis, D., O'Neil, E. et al. (2005). The authors theorise when non-serialisable executions can occur under snapshot isolation, note that major products ship with default non-serialisable levels, and apply the theory to TPC-C. A lower level is justified when an application can be shown to survive it, and the showing is the missing part.
• Cahill, M. J., Rohm, U. and Fekete, A. D. (2009). The authors describe a change to a database's concurrency control that detects and prevents snapshot isolation anomalies at run time, where the earlier remedy was to modify each application with explicit locking or artificial update conflicts.
• Ports, D. R. K. and Grittner, K. (2012). The authors implement PostgreSQL's serialisable level on serialisable snapshot isolation, the first such implementation in a production release, and report a new lock manager and bounded memory use, with performance only slightly below snapshot isolation. It shows the cost of a level belongs to one engine's engineering.
• Bailis, P., Davidson, A., Fekete, A. et al. (2013). The authors define highly available transactions as guarantees that do not suffer unavailability during partitions or incur high network latency, and analyse which ACID isolation and distributed consistency guarantees can and cannot be achieved, quantifying a benefit of two to three orders of magnitude over wide-area networks.
• Mohan, C., Haderle, D., Lindsay, B. et al. (1992). The authors present ARIES, a recovery method supporting fine-granularity locking and partial rollbacks through write-ahead logging, and report its implementation in IBM systems including DB2 and Starburst.
• Geng, C., Blanas, S., Bond, M. D. and Wang, Y. (2024). A dynamic predictive analysis that solves SMT constraints over an observed serialisable execution of a weakly isolated data store to find a feasible unserialisable execution of the same application. It supplies the guidance for avoiding weak-isolation errors that earlier work said was missing, though it predicts behaviours rather than observing production errors.
• Harding, R., Van Aken, D., Pavlo, A. et al. (2017). The authors quantify the effects of distributing transactions across servers on concurrency control protocols, evaluating six classic and modern protocols in an in-memory framework called Deneva. Its figures belong to one workload and one hardware setting.