What concurrency schemes forbid
What this article forbids
- Serializability without either waiting or aborting. There is no third currency, except commutativity, which changes the problem instead of solving it.
- Exact, cheap conflict detection. Every practical scheme is conservative and pays in false conflicts.
- A long-running transaction concurrent with a high write rate on overlapping data. That is arithmetic, not tuning.
- Avoiding a collector once you have multiversioned.
- Isolation behaviour that is independent of physical design. Because predicate locking is intractable, which index exists determines which locks are taken, which determines which transactions conflict.
Escapes and their prices
| Escape | Price |
|---|---|
| Weaken the guarantee | The application pays, in anomalies |
| Multiversion | Space, a collector, and the oldest reader's veto over both |
| Partition and serialize | Cross-partition transactions become a cliff, not a slope |
| Determinize | No interactive transactions, advance access sets, a global sequencer |
| Commute | Works only where the operation has an algebra |
| Shrink W | The most underrated of the six, and the only one with no structural cost |