More Web Proxy on the site http://driver.im/

research-article

Calvin: fast distributed transactions for partitioned database systems

Authors:

Alexander Thomson,

Thaddeus Diamond,

Daniel J. AbadiAuthors Info & Claims

SIGMOD '12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data

Pages 1 - 12

https://doi.org/10.1145/2213836.2213838

Published: 20 May 2012 Publication History

Abstract

Many distributed storage systems achieve high data access throughput via partitioning and replication, each system with its own advantages and tradeoffs. In order to achieve high scalability, however, today's systems generally reduce transactional support, disallowing single transactions from spanning multiple partitions. Calvin is a practical transaction scheduling and data replication layer that uses a deterministic ordering guarantee to significantly reduce the normally prohibitive contention costs associated with distributed transactions. Unlike previous deterministic database system prototypes, Calvin supports disk-based storage, scales near-linearly on a cluster of commodity machines, and has no single point of failure. By replicating transaction inputs rather than effects, Calvin is also able to support multiple consistency levels---including Paxos-based strong consistency across geographically distant replicas---at no cost to transactional throughput.

References

[1]

Amazon simpledb. http://aws.amazon.com/simpledb/.

[2]

Project voldemort. http://project-voldemort.com/.

[3]

Riak. http://wiki.basho.com/riak.html.

[4]

Transaction processing performance council. http://www.tpc.org/tpcc/.

[5]

D. Abadi. Replication and the latency-consistency tradeoff. http://dbmsmusings.blogspot.com/2011/12/replication-and-latency-consistency.html.

[6]

J. C. Anderson, J. Lehnardt, and N. Slater. CouchDB: The Definitive Guide. 2010.

Digital Library

[7]

J. Baker, C. Bond, J. Corbett, J. J. Furman, A. Khorlin, J. Larson, J.-M. Leon, Y. Li, A. Lloyd, and V. Yushprakh. Megastore: Providing scalable, highly available storage for interactive services. In CIDR, 2011.

[8]

P. A. Bernstein, C. W. Reid, and S. Das. Hyder - a transactional record manager for shared flash. In CIDR, 2011.

[9]

D. Campbell, G. Kakivaya, and N. Ellis. Extreme scale with full sql language support in microsoft sql azure. In SIGMOD, 2010.

Digital Library

[10]

T. Cao, M. Vaz Salles, B. Sowell, Y. Yue, A. Demers, J. Gehrke, and W. White. Fast checkpoint recovery algorithms for frequently consistent applications. In SIGMOD, 2011.

Digital Library

[11]

F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. Bigtable: a distributed storage system for structured data. In OSDI, 2006.

Digital Library

[12]

B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. Pnuts: Yahoo!'s hosted data serving platform. VLDB, 2008.

Digital Library

[13]

G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available key-value store. SIGOPS, 2007.

Digital Library

[14]

S. Gilbert and N. Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 2002.

Digital Library

[15]

P. Hunt, M. Konar, F. P. Junqueira, and B. Reed. Zookeeper: Wait-free coordination for internet-scale systems. In In USENIX Annual Technical Conference.

Digital Library

[16]

E. P. C. Jones, D. J. Abadi, and S. R. Madden. Concurrency control for partitioned databases. In SIGMOD, 2010.

Digital Library

[17]

A. Lakshman and P. Malik. Cassandra: structured storage system on a p2p network. In PODC, 2009.

Digital Library

[18]

L. Lamport. The part-time parliament. ACM Trans. Comput. Syst., 1998.

Digital Library

[19]

L. Lamport. Paxos made simple. ACM SIGACT News, 2001.

[20]

D. Lomet and M. F. Mokbel. Locking key ranges with unbundled transaction services. VLDB, 2009.

Digital Library

[21]

D. B. Lomet, A. Fekete, G. Weikum, and M. J. Zwilling. Unbundling transaction services in the cloud. In CIDR, 2009.

[22]

C. Mohan, B. G. Lindsay, and R. Obermarck. Transaction management in the r* distributed database management system. ACM Trans. Database Syst., 1986.

Digital Library

[23]

E. Pacitti, M. T. Ozsu, and C. Coulon. Preventive multi-master replication in a cluster of autonomous databases. In Euro-Par, 2003.

[24]

E. Plugge, T. Hawkins, and P. Membrey. The Definitive Guide to MongoDB: The NoSQL Database for Cloud and Desktop Computing. 2010.

Digital Library

[25]

J. Rao, E. J. Shekita, and S. Tata. Using paxos to build a scalable, consistent, and highly available datastore. VLDB, 2011.

Digital Library

[26]

M. Seltzer. Oracle nosql database. In Oracle White Paper, 2011.

[27]

M. Stonebraker, S. R. Madden, D. J. Abadi, S. Harizopoulos, N. Hachem, and P. Helland. The end of an architectural era (it's time for a complete rewrite). In VLDB, 2007.

Digital Library

[28]

A. Thomson and D. J. Abadi. The case for determinism in database systems. VLDB, 2010.

Digital Library

[29]

A. Whitney, D. Shasha, and S. Apter. High volume transaction processing without concurrency control, two phase commit, SQL or C. In HPTS, 1997.

Cited By

Liu ZUnal MParkinson MKogias M(2025)DORADD: Deterministic Parallel Execution in the Era of Microsecond-Scale ComputingProceedings of the 30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3710848.3710872(282-296)Online publication date: 28-Feb-2025
https://dl.acm.org/doi/10.1145/3710848.3710872
Ko RXiao COnizuka MLin ZHuang Y(2025)Ultraverse: An Efficient What-if Analysis Framework for Software Applications Interacting with Database SystemsProceedings of the ACM on Management of Data10.1145/37097343:1(1-27)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709734
Liang JYao PChen WHong ZZhang JCai TSun MZheng Z(2025)Sparrow: Expediting Smart Contract Execution for Blockchain Sharding via Inter-Shard CachingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.352201636:3(377-390)Online publication date: Mar-2025
https://doi.org/10.1109/TPDS.2024.3522016
Show More Cited By

Index Terms

Calvin: fast distributed transactions for partitioned database systems

Recommendations

Fast Distributed Transactions and Strongly Consistent Replication for OLTP Database Systems

As more data management software is designed for deployment in public and private clouds, or on a cluster of commodity servers, new distributed storage systems increasingly achieve high data access throughput via partitioning and replication. In order ...
Distributed Optimistic Concurrency Control Methods for High-Performance Transaction Processing

There is an ever-increasing demand for more complex transactions and higher throughputs in transaction processing systems leading to higher degrees of transaction concurrency and, hence, higher data contention. The conventional two-phase locking (2PL) ...
Non-blocking concurrency control in distributed database systems
PAS '95: Proceedings of the First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis

Concurrency control based on conventional techniques requires additional efforts for deadlock detection and elimination. The possibility of a deadlock is also connected to the introduction of delays, and repeated restarts of transactions in deadlock ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data

May 2012

886 pages

ISBN:9781450312479

DOI:10.1145/2213836

General Chairs:
K. Selçuk Candan
Arizona State University
,
Yi Chen
Arizona State University
,
Richard Snodgrass
University of Arizona
,
Program Chair:
Luis Gravano
Columbia University
,
Publications Chair:
Ariel Fuxman
Microsoft Research

Copyright © 2012 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]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 May 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '12

Sponsor:

SIGMOD

SIGMOD/PODS '12: International Conference on Management of Data

May 20 - 24, 2012

Arizona, Scottsdale, USA

Acceptance Rates

SIGMOD '12 Paper Acceptance Rate 48 of 289 submissions, 17%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

417
Total Citations
View Citations
3,688
Total Downloads

Downloads (Last 12 months)282
Downloads (Last 6 weeks)29

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu ZUnal MParkinson MKogias M(2025)DORADD: Deterministic Parallel Execution in the Era of Microsecond-Scale ComputingProceedings of the 30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3710848.3710872(282-296)Online publication date: 28-Feb-2025
https://dl.acm.org/doi/10.1145/3710848.3710872
Ko RXiao COnizuka MLin ZHuang Y(2025)Ultraverse: An Efficient What-if Analysis Framework for Software Applications Interacting with Database SystemsProceedings of the ACM on Management of Data10.1145/37097343:1(1-27)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709734
Liang JYao PChen WHong ZZhang JCai TSun MZheng Z(2025)Sparrow: Expediting Smart Contract Execution for Blockchain Sharding via Inter-Shard CachingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.352201636:3(377-390)Online publication date: Mar-2025
https://doi.org/10.1109/TPDS.2024.3522016
Helt JSharma AAbadi DLloyd WFaleiro J(2025)C5: cloned concurrency control that always keeps upThe VLDB Journal10.1007/s00778-025-00901-334:2Online publication date: 12-Feb-2025
https://doi.org/10.1007/s00778-025-00901-3
Qian SGoel AGavrilovska ATerry D(2024)Massively parallel multi-versioned transaction processingProceedings of the 18th USENIX Conference on Operating Systems Design and Implementation10.5555/3691938.3691979(765-781)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.5555/3691938.3691979
Varshini Choudary Nuvvula (2024)Scaling Cloud-Based Transaction Systems: How Modern Architectures Handle Growing DemandInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology10.32628/CSEIT24106118910:6(1427-1438)Online publication date: 7-Dec-2024
https://doi.org/10.32628/CSEIT241061189
Nikolic LDimitrieski VCelikovic M(2024)An approach for supporting transparent acid transactions over heterogeneous data stores in microservice architecturesComputer Science and Information Systems10.2298/CSIS221210006N21:1(167-202)Online publication date: 2024
https://doi.org/10.2298/CSIS221210006N
Uchida MKawashima H(2024)CLMD: Making Lock Manager Predictable and Concurrent for Deterministic Concurrency ControlInternational Journal of Networking and Computing10.15803/ijnc.14.1_8114:1(81-92)Online publication date: 2024
https://doi.org/10.15803/ijnc.14.1_81
Xu QYang CZhou A(2024)Native Distributed Databases: Problems, Challenges and OpportunitiesProceedings of the VLDB Endowment10.14778/3685800.368583917:12(4217-4220)Online publication date: 8-Nov-2024
https://doi.org/10.14778/3685800.3685839
Eldeeb TBurckhardt SBond RCidon AYang JBernstein P(2024)Cloud Actor-Oriented Database Transactions in OrleansProceedings of the VLDB Endowment10.14778/3685800.368580117:12(3720-3730)Online publication date: 8-Nov-2024
https://dl.acm.org/doi/10.14778/3685800.3685801
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten