Clock-SI: Snapshot Isolation for Partitioned Data Stores Using Loosely Synchronized Clocks
- 1 September 2013
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 173-184
- https://doi.org/10.1109/srds.2013.26
Abstract
Clock-SI is a fully distributed protocol that implements snapshot isolation (SI) for partitioned data stores. It derives snapshot and commit timestamps from loosely synchronized clocks, rather than from a centralized timestamp authority as used in current systems. A transaction obtains its snapshot timestamp by reading the clock at its originating partition and Clock-SI provides the corresponding consistent snapshot across all the partitions. In contrast to using a centralized timestamp authority, Clock-SI has availability and performance benefits: It avoids a single point of failure and a potential performance bottleneck, and improves transaction latency and throughput. We develop an analytical model to study the trade-offs introduced by Clock-SI among snapshot age, delay probabilities of transactions, and abort rates of update transactions. We verify the model predictions using a system implementation. Furthermore, we demonstrate the performance benefits of Clock-SI experimentally using a micro-benchmark and an application-level benchmark on a partitioned key-value store. For short read-only transactions, Clock-SI improves latency and throughput by 50% by avoiding communications with a centralized timestamp authority. With a geographically partitioned data store, Clock-SI reduces transaction latency by more than 100 milliseconds. Moreover, the performance benefits of Clock-SI come with higher availability.Keywords
This publication has 19 references indexed in Scilit:
- Transactional storage for geo-replicated systemsPublished by Association for Computing Machinery (ACM) ,2011
- BigtableACM Transactions on Computer Systems, 2008
- Relaxed-currency serializability for middle-tier caching and replicationPublished by Association for Computing Machinery (ACM) ,2006
- TashkentPublished by Association for Computing Machinery (ACM) ,2006
- Relaxed currency and consistencyPublished by Association for Computing Machinery (ACM) ,2004
- Fine-grained network time synchronization using reference broadcastsACM SIGOPS Operating Systems Review, 2002
- The dangers of replication and a solutionACM SIGMOD Record, 1996
- A critique of ANSI SQL isolation levelsACM SIGMOD Record, 1995
- Practical uses of synchronized clocks in distributed systemsDistributed Computing, 1993
- Implementing fault-tolerant services using the state machine approach: a tutorialACM Computing Surveys, 1990