ABSTRACT
Existing database systems employ an \textit{eager} transaction processing scheme---that is, upon receiving a transaction request, the system executes all the operations entailed in running the transaction (which typically includes reading database records, executing user-specified transaction logic, and logging updates and writes) before reporting to the client that the transaction has completed. We introduce a \textit{lazy} transaction execution engine, in which a transaction may be considered durably completed after only partial execution, while the bulk of its operations (notably all reads from the database and all execution of transaction logic) may be deferred until an arbitrary future time, such as when a user attempts to read some element of the transaction's write-set---all without modifying the semantics of the transaction or sacrificing ACID guarantees. Lazy transactions are processed deterministically, so that the final state of the database is guaranteed to be equivalent to what the state would have been had all transactions been executed eagerly.
Our prototype of a lazy transaction execution engine improves temporal locality when executing related transactions, reduces peak provisioning requirements by deferring more non-urgent work until off-peak load times, and reduces contention footprint of concurrent transactions. However, we find that certain queries suffer increased latency, and therefore lazy database systems may not be appropriate for read-latency sensitive applications.
We introduce a lazy transaction execution engine, in which a transaction may be considered durably completed after only partial execution, while the bulk of its operations (notably all reads from the database and all execution of transaction logic) may be deferred until an arbitrary future time, such as when a user attempts to read some element of the transaction's write-set---all without modifying the semantics of the transaction or sacrificing ACID guarantees. Lazy transactions are processed deterministically, so that the final state of the database is guaranteed to be equivalent to what the state would have been had all transactions been executed eagerly.
Our prototype of a lazy transaction execution engine improves temporal locality when executing related transactions, reduces peak provisioning requirements by deferring more non-urgent work until off-peak load times, and reduces contention footprint of concurrent transactions. However, we find that certain queries suffer increased latency, and therefore lazy database systems may not be appropriate for read-latency sensitive applications.
- A. J. Bernstein, D. S. Gerstl, and P. M. Lewis. Concurrency control for step-decomposed transactions. Information Systems, 24:673--698, 1999. Google ScholarDigital Library
- P. A. Bernstein, C. W. Reid, and S. Das. Hyder - a transactional record manager for shared flash. In CIDR, pages 9--20, 2011.Google Scholar
- Y. Breitbart, R. Komondoor, R. Rastogi, S. Seshadri, and A. Silberschatz. Update propagation protocols for replicated databates. SIGMOD, 1999. Google ScholarDigital Library
- P. Buneman, R. E. Frankel, and R. Nikhil. An implementation technique for database query languages. ACM Trans. Database Syst., 7(2):164--186, June 1982. Google ScholarDigital Library
- A. Cheung, S. Madden, O. Arden, and A. C. Myers. Speeding up database applications with pyxis. In SIGMOD, 2013. Google ScholarDigital Library
- D. Friedman and D. Wise. Cons should not evaluate its arguments. Automata, Languages and Programming. 1976.Google Scholar
- H. Garcia-Molina and K. Salem. Sagas. In Proc. of SIGMOD, pages 249--259, 1987. Google ScholarDigital Library
- G. Giannikis, G. Alonso, and D. Kossmann. Shareddb: Killing one thousand queries with one stone. Proc. VLDB Endow., 5(6):526--537, Feb. 2012. Google ScholarDigital Library
- J. Gray, P. Helland, P. O'Neil, and D. Shasha. The dangers of replication and a solution. In SIGMOD, 1996. Google ScholarDigital Library
- P. Henderson and J. H. Morris, Jr. A lazy evaluator. POPL, 1976. Google ScholarDigital Library
- P. Hudak. Conception, evolution, and application of functional programming languages. ACM Comput. Surv., 21(3):359--411, 1989. Google ScholarDigital Library
- P. Hudak, J. Hughes, S. Peyton Jones, and P. Wadler. A history of haskell: being lazy with class. In SIGPLAN, 2007. Google ScholarDigital Library
- C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguiça, and R. Rodrigues. Making geo-replicated systems fast as possible, consistent when necessary. In Proc. of OSDI, 2012. Google ScholarDigital Library
- N. Malviya, A. Weisberg, S. Madden, and M. Stonebraker. Rethinking main memory oltp recovery. In Proc. of ICDE, 2014.Google ScholarCross Ref
- K. Morton, M. Balazinska, D. Grossman, and C. Olston. The case for being lazy: how to leverage lazy evaluation in mapreduce. ScienceCloud, 2011. Google ScholarDigital Library
- E. Pacitti, P. Minet, and E. Simon. Fast algorithms for maintaining replica consistency in lazy master replicated databases. In Proc. VLDB, pages 126--137, 1999. Google ScholarDigital Library
- A. Pavlo, E. P. Jones, and S. Zdonik. On predictive modeling for optimizing transaction execution in parallel oltp systems. PVLDB, 5(2):85--96, 2012. Google ScholarDigital Library
- K. Ren, A. Thomson, and D. J. Abadi. Lightweight locking for main memory database systems. PVLDB, 2013. Google ScholarDigital Library
- D. Shasha, F. Llirbat, E. Simon, and P. Valduriez. Transaction chopping: Algorithms and performance studies. ACM Trans. Database Syst., 20(3):325--363, Sept. 1995. Google ScholarDigital Library
- 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 Proc. of VLDB, 2007. Google ScholarDigital Library
- A. Thomson and D. J. Abadi. The case for determinism in data base systems. In Proc. of VLDB, 2010. Google ScholarDigital Library
- A. Thomson, T. Diamond, S. chun Weng, K. Ren, P. Shao, and D. J. Abadi. Calvin: Fast distributed transactions for partitioned database systems. In SIGMOD, 2012. Google ScholarDigital Library
- VoltDB. Website. voltdb.com.Google Scholar
- C. Wadsworth. Semantics and Pragmatics of the Lambda-calculus. University of Oxford, 1971.Google Scholar
- Y. Zhang, R. Power, S. Zhou, Y. Sovran, M. K. Aguilera, and J. Li. Transaction chains: Achieving serializability with low latency in geo-distributed storage systems. In Proc. of SOSP, 2013. Google ScholarDigital Library
- J. Zhou and K. A. Ross. Buffering databse operations for enhanced instruction cache performance. SIGMOD, 2004. Google ScholarDigital Library
Index Terms
- Lazy evaluation of transactions in database systems
Recommendations
Lazy Evaluation for Concurrent OLTP and Bulk Transactions
IDEAS '16: Proceedings of the 20th International Database Engineering & Applications SymposiumExisting concurrency control systems cannot execute transactions with overlapping updates concurrently. This is especially problematic for bulk updates, which usually overlap with all concurrent transactions. To solve this, we have developed a ...
Comments