Seeing is Believing
- 25 July 2017
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
Abstract
This paper introduces the first state-based formalization of isolation guarantees. Our approach is premised on a simple observation: applications view storage systems as black-boxes that transition through a series of states, a subset of which are observed by applications. Defining isolation guarantees in terms of these states frees definitions from implementation-specific assumptions. It makes immediately clear what anomalies, if any, applications can expect to observe, thus bridging the gap that exists today between how isolation guarantees are defined and how they are perceived. The clarity that results from definitions based on client-observable states brings forth several benefits. First, it allows us to easily compare the guarantees of distinct, but semantically close, isolation guarantees. We find that several well-known guarantees, previously thought to be distinct, are in fact equivalent, and that many previously incomparable flavors of snapshot isolation can be organized in a clean hierarchy. Second, freeing definitions from implementation-specific artefacts can suggest more efficient implementations of the same isolation guarantee. We show how a client-centric implementation of parallel snapshot isolation can be more resilient to slowdown cascades, a common phenomenon in large-scale datacenters.Keywords
Funding Information
- National Science Foundation (CNS-1718709 & CNS-1409555)
- Google (Faculty Research Award and Doctoral Fellowship)
This publication has 28 references indexed in Scilit:
- Highly available transactionsProceedings of the VLDB Endowment, 2013
- Virtual world consistency: A condition for STM systems (with a versatile protocol with invisible read operations)Theoretical Computer Science, 2012
- Rethink the syncACM Transactions on Computer Systems, 2008
- Making snapshot isolation serializableACM Transactions on Database Systems, 2005
- A critique of ANSI SQL isolation levelsACM SIGMOD Record, 1995
- Principles and realization strategies of multilevel transaction managementACM Transactions on Database Systems, 1991
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- Multiversion concurrency control—theory and algorithmsACM Transactions on Database Systems, 1983
- Concurrency Control in Distributed Database SystemsACM Computing Surveys, 1981
- The serializability of concurrent database updatesJournal of the ACM, 1979