Alexander Thomson
Daniel J. Abadi
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.
- Amazon simpledb. http://aws.amazon.com/simpledb/.Google Scholar
- Project voldemort. http://project-voldemort.com/.Google Scholar
- Riak. http://wiki.basho.com/riak.html.Google Scholar
- Transaction processing performance council. http://www.tpc.org/tpcc/.Google Scholar
- D. Abadi. Replication and the latency-consistency tradeoff. http://dbmsmusings.blogspot.com/2011/12/replication-and-latency-consistency.html.Google Scholar
- J. C. Anderson, J. Lehnardt, and N. Slater. CouchDB: The Definitive Guide. 2010. Google ScholarDigital Library
- 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.Google Scholar
- P. A. Bernstein, C. W. Reid, and S. Das. Hyder - a transactional record manager for shared flash. In CIDR, 2011.Google Scholar
- D. Campbell, G. Kakivaya, and N. Ellis. Extreme scale with full sql language support in microsoft sql azure. In SIGMOD, 2010. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- S. Gilbert and N. Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 2002. Google ScholarDigital Library
- P. Hunt, M. Konar, F. P. Junqueira, and B. Reed. Zookeeper: Wait-free coordination for internet-scale systems. In In USENIX Annual Technical Conference. Google ScholarDigital Library
- E. P. C. Jones, D. J. Abadi, and S. R. Madden. Concurrency control for partitioned databases. In SIGMOD, 2010. Google ScholarDigital Library
- A. Lakshman and P. Malik. Cassandra: structured storage system on a p2p network. In PODC, 2009. Google ScholarDigital Library
- L. Lamport. The part-time parliament. ACM Trans. Comput. Syst., 1998. Google ScholarDigital Library
- L. Lamport. Paxos made simple. ACM SIGACT News, 2001.Google Scholar
- D. Lomet and M. F. Mokbel. Locking key ranges with unbundled transaction services. VLDB, 2009. Google ScholarDigital Library
- D. B. Lomet, A. Fekete, G. Weikum, and M. J. Zwilling. Unbundling transaction services in the cloud. In CIDR, 2009.Google Scholar
- C. Mohan, B. G. Lindsay, and R. Obermarck. Transaction management in the r* distributed database management system. ACM Trans. Database Syst., 1986. Google ScholarDigital Library
- E. Pacitti, M. T. Ozsu, and C. Coulon. Preventive multi-master replication in a cluster of autonomous databases. In Euro-Par, 2003.Google ScholarCross Ref
- E. Plugge, T. Hawkins, and P. Membrey. The Definitive Guide to MongoDB: The NoSQL Database for Cloud and Desktop Computing. 2010. Google ScholarDigital Library
- J. Rao, E. J. Shekita, and S. Tata. Using paxos to build a scalable, consistent, and highly available datastore. VLDB, 2011. Google ScholarDigital Library
- M. Seltzer. Oracle nosql database. In Oracle White Paper, 2011.Google Scholar
- 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. Google ScholarDigital Library
- A. Thomson and D. J. Abadi. The case for determinism in database systems. VLDB, 2010. Google ScholarDigital Library
- A. Whitney, D. Shasha, and S. Apter. High volume transaction processing without concurrency control, two phase commit, SQL or C. In HPTS, 1997.Google Scholar
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 SynthesisConcurrency 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