Skip to content

Transactions: myths, surprises and opportunities

A talk at Strange Loop, St. Louis, Missouri, US, 26 Sep 2015


Back in the 1970s, the earliest databases had transactions. Then NoSQL abolished them. And now, perhaps, they are making a comeback… but reinvented.

The purpose of transactions is to make application code simpler, by reducing the amount of failure handling you need to do yourself. However, they have also gained a reputation for being slow and unscalable. With the traditional implementation of serializability (2-phase locking), that reputation was somewhat deserved.

In the last few years, there has been a resurgence of interest in transaction algorithms that perform well and scale well. This talk answers some of the biggest questions about the bright new landscape of transactions:

  • What does ACID actually mean? What race conditions can you get with weak isolation (such as “read committed” and “repeatable read”), and how does this affect your application?
  • What are the strongest guarantees we can achieve, while maintaining high availability and high performance at scale?
  • How do the new generation of algorithms for distributed, highly-available transactions work?
  • Linearizability, session guarantees, “consistency” and the much-misunderstood CAP theorem – what’s really going on here?
  • When you move beyond a single database, e.g. doing stream processing, what are your options for maintaining transactional guarantees?


  1. Atul Adya: “Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions,” PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, March 1999.
  2. Hagit Attiya, Faith Ellen, and Adam Morrison: “Limitations of Highly-Available Eventually-Consistent Data Stores,” at ACM Symposium on Principles of Distributed Computing (PODC), July 2015.
  3. Peter Bailis, Alan Fekete, Ali Ghodsi, Joseph M Hellerstein, and Ion Stoica: “HAT, not CAP: Towards Highly Available Transactions,” at 14th USENIX Workshop on Hot Topics in Operating Systems (HotOS), May 2013.
  4. Peter Bailis, Ali Ghodsi, Joseph M Hellerstein, and Ion Stoica: “Bolt-on Causal Consistency,” at ACM International Conference on Management of Data (SIGMOD), June 2013.
  5. Peter Bailis, Aaron Davidson, Alan Fekete, et al.: “Highly Available Transactions: Virtues and Limitations,” at 40th International Conference on Very Large Data Bases (VLDB), September 2014.
  6. Hal Berenson, Philip A Bernstein, Jim N Gray, et al.: “A Critique of ANSI SQL Isolation Levels,” at ACM International Conference on Management of Data (SIGMOD), May 1995.
  7. Eric A Brewer: “CAP Twelve Years Later: How the “Rules” Have Changed,” IEEE Computer Magazine, volume 45, number 2, pages 23–29, February 2012.
  8. Michael J Cahill, Uwe Röhm, and Alan Fekete: “Serializable Isolation for Snapshot Databases,” at ACM International Conference on Management of Data (SIGMOD), pages 729–738, June 2008.
  9. Donald D Chamberlin, Morton M Astrahan, Michael W Blasgen, et al.: “A History and Evaluation of System R,” Communications of the ACM, volume 24, number 10, pages 632–646, October 1981.
  10. Tushar Deepak Chandra and Sam Toueg: “Unreliable Failure Detectors for Reliable Distributed Systems,” Journal of the ACM, volume 43, number 2, pages 225–267, March 1996.
  11. Kapali P Eswaran, Jim N Gray, Raymond A Lorie, and Irving L Traiger: “The Notions of Consistency and Predicate Locks in a Database System,” Communications of the ACM, volume 19, number 11, pages 624–633, November 1976.
  12. Hector Garcia-Molina and Kenneth Salem: “Sagas,” at ACM International Conference on Management of Data (SIGMOD), May 1987.
  13. Jim N Gray, Raymond A Lorie, Gianfranco R Putzolu, and Irving L Traiger: “Granularity of Locks and Degrees of Consistency in a Shared Data Base,” in Modelling in Data Base Management Systems: Proceedings of the IFIP Working Conference on Modelling in Data Base Management Systems, G.M. Nijssen, Editor. Elsevier/North Holland Publishing, pages 364–394, 1976.
  14. Rachid Guerraoui: “Revisiting the relationship between non-blocking atomic commitment and consensus,” at 9th International Workshop on Distributed Algorithms (WDAG), pages 87–100, September 1995.
  15. Theo Härder and Andreas Reuter: “Principles of Transaction-Oriented Database Recovery,” ACM Computing Surveys, volume 15, number 4, pages 287–317, December 1983.
  16. Pat Helland and Dave Campbell: “Building on Quicksand,” at 4th Biennial Conference on Innovative Data Systems Research (CIDR), January 2009.
  17. Joseph M Hellerstein: “The Declarative Imperative: Experiences and Conjectures in Distributed Logic,” ACM SIGMOD Record, volume 39, number 1, March 2010.
  18. Martin Kleppmann: “Hermitage: Testing the ‘I’ in ACID,” 25 November 2014.
  19. Martin Kleppmann: “A Critique of the CAP Theorem,” Preprint arXiv:1509.05393 [cs.DC], Sep 2015.
  20. Martin Kleppmann: Designing Data-Intensive Applications. O’Reilly Media, to appear. ISBN 1-4493-7332-1.
  21. Wyatt Lloyd, Michael J Freedman, Michael Kaminsky, and David G Andersen: “Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS,” at 23rd ACM Symposium on Operating Systems Principles (SOSP), pages 401–416, October 2011.
  22. Dan R K Ports and Kevin Grittner: “Serializable Snapshot Isolation in PostgreSQL,” at 38th International Conference on Very Large Data Bases (VLDB), volume 5, number 12, pages 1850–1861, August 2012.
  23. Michael Stonebraker, Samuel Madden, Daniel J Abadi, et al.: “The End of an Architectural Era (It’s Time for a Complete Rewrite),” at 33rd International Conference on Very Large Data Bases (VLDB), pages 1150–1160, September 2007.
  24. Marek Zawirski, Annette Bieniusa, Valter Balegas, et al.: “SwiftCloud: Fault-Tolerant Geo-Replication Integrated all the Way to the Client Machine,” INRIA Research Report 8347, August 2013.