PhysiCS-NMSI: efficient consistent snapshots for scalable snapshot isolation
Article No.: 4, Pages 1 - 4
Abstract
Non-Monotonic Snapshot Isolation (NMSI), a variant of the widely deployed Snapshot Isolation (SI), aims at improving scalability by relaxing snapshots. In contrast to SI, NMSI snapshots are causally consistent, which allows for more parallelism and a reduced abort rate.
This work documents the design of PhysiCS-NMSI, a transactional protocol implementing NMSI in a partitioned data store. It is the first protocol to rely on a single scalar taken from a physical clock for tracking causal dependencies and building causally consistent snapshots. Its commit protocol ensures atomicity and the absence of write-write conflicts.
We argue that PhysiCS-NMSI approach increases concurrency and reduces abort rate and metadata overhead as compared to state-of-art systems.
References
[1]
NTP: The network time protocol. https://www.ntp.org/, retrieved August 2015.
[2]
M. Ahamad, J. E. Burns, P. W. Hutto, and G. Neiger. Causal memory. In Proc. 5th Int. Workshop on Distributed Algorithms, pages 9--30, Delphi, Greece, Oct. 1991.
[3]
D. D. Akkoorath, A. Z. Tomsic, M. Bravo, Z. Li, T. Crain, A. Bieniusa, N. Preguiça, and M. Shapiro. Cure: Strong semantics meets high availability and low latency. In IEEE 36th International Conference on Distributed Computing Systems, ICDCS '16, Nara, Japan, June 2016. IEEE Computer Society.
[4]
M. S. Ardekani, P. Sutra, and M. Shapiro. Non-monotonic snapshot isolation: Scalable and strong consistency for geo-replicated transactional systems. In Proceedings of the 2013 IEEE 32Nd International Symposium on Reliable Distributed Systems, SRDS '13, pages 163--172, 2013.
[5]
M. S. Ardekani, P. Sutra, M. Shapiro, and N. Preguiça. On the scalability of snapshot isolation. In Proceedings of the 19th International Conference on Parallel Processing, Euro-Par'13, pages 369--381, 2013.
[6]
H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O'Neil, and P. O'Neil. A critique of ANSI SQL isolation levels. In Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, SIGMOD '95, pages 1--10, 1995.
[7]
J. Du, S. Elnikety, A. Roy, and W. Zwaenepoel. Orbe: Scalable causal consistency using dependency matrices and physical clocks. In Proceedings of the 4th Annual Symposium on Cloud Computing, SOCC '13, pages 11:1--11:14, New York, NY, USA, 2013. ACM.
[8]
J. Du, S. Elnikety, and W. Zwaenepoel. Clock-SI: Snapshot isolation for partitioned data stores using loosely synchronized clocks. In Proceedings of the 2013 IEEE 32Nd International Symposium on Reliable Distributed Systems, SRDS '13, pages 173--184, Washington, DC, USA, 2013. IEEE Computer Society.
[9]
J. Du, C. Iorgulescu, A. Roy, and W. Zwaenepoel. GentleRain: Cheap and scalable causal consistency with physical clocks. In Proceedings of the ACM Symposium on Cloud Computing, SOCC '14, pages 4:1--4:13, New York, NY, USA, 2014. ACM.
[10]
R. C. Hansdah and L. M. Patnaik. Update serializability in locking. In Proceedings on International Conference on Database Theory, pages 171--185, New York, NY, USA, 1986. Springer-Verlag New York, Inc.
[11]
L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, July 1978.
[12]
W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen. Don't settle for eventual: Scalable causal consistency for wide-area storage with COPS. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP '11, pages 401--416, 2011.
[13]
H. Lu, K. Veeraraghavan, P. Ajoux, J. Hunt, Y. J. Song, W. Tobagus, S. Kumar, and W. Lloyd. Existential consistency: Measuring and understanding consistency at facebook. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP '15, pages 295--310, New York, NY, USA, 2015. ACM.
[14]
S. Peluso, P. Ruivo, P. Romano, F. Quaglia, and L. Rodrigues. When scalability meets consistency: Genuine multiversion update-serializable partial data replication. In Proceedings of the 2012 IEEE 32Nd International Conference on Distributed Computing Systems, ICDCS '12, pages 455--465, Washington, DC, USA, 2012. IEEE Computer Society.
[15]
Y. Sovran, R. Power, M. K. Aguilera, and J. Li. Transactional storage for geo-replicated systems. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP '11, pages 385--400, 2011.
[16]
I. Zhang, N. K. Sharma, A. Szekeres, A. Krishnamurthy, and D. R. K. Ports. Building consistent transactions with inconsistent replication. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP '15, pages 263--278, New York, NY, USA, 2015. ACM.
Recommendations
WFR-TM
Transactional Memory (TM) is a promising concurrent programming paradigm which employs transactions to achieve synchronization in accessing common data known as transactional variables. A transaction may either commit, making its updates to ...
Wait-n-GoTM: improving HTM performance by serializing cyclic dependencies
ASPLOS '13Transactional memory (TM) has been proposed to alleviate some key programmability problems in chip multiprocessors. Most TMs optimistically allow concurrent transactions, detecting read-write or write-write conflicts. Upon conflicts, existing hardware ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 April 2016
Check for updates
Qualifiers
- Short-paper
Conference
EuroSys '16
Acceptance Rates
Overall Acceptance Rate 34 of 47 submissions, 72%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 114Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)1
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in