Jose M. Faleiro
Daniel J. Abadi
Abstract
Multi-versioned database systems have the potential to significantly increase the amount of concurrency in transaction processing because they can avoid read-write conflicts. Unfortunately, the increase in concurrency usually comes at the cost of transaction serializability. If a database user requests full serializability, modern multi-versioned systems significantly constrain read-write concurrency among conflicting transactions and employ expensive synchronization patterns in their design. In main-memory multi-core settings, these additional constraints are so burdensome that multi-versioned systems are often significantly outperformed by single-version systems.
We propose Bohm, a new concurrency control protocol for main-memory multi-versioned database systems. Bohm guarantees serializable execution while ensuring that reads never block writes. In addition, Bohm does not require reads to perform any bookkeeping whatsoever, thereby avoiding the overhead of tracking reads via contended writes to shared memory. This leads to excellent scalability and performance in multi-core settings. Bohm has all the above characteristics without performing validation based concurrency control. Instead, it is pessimistic, and is therefore not prone to excessive aborts in the presence of contention. An experimental evaluation shows that Bohm performs well in both high contention and low contention settings, and is able to dramatically outperform state-of-the-art multi-versioned systems despite maintaining the full set of serializability guarantees.
- A. Adya, B. Liskov, and P. O'Neil. Generalized isolation level definitions. In Proc. of ICDE, pages 67--78. IEEE, 2000. Google Scholar
Digital Library
- D. Agrawal, A. J. Bernstein, P. Gupta, and S. Sengupta. Distributed optimistic concurrency control with reduced rollback. Distributed Computing, 2(1):45--59, 1987.Google ScholarDigital Library
- M. K. Aguilera, A. Merchant, M. Shah, A. Veitch, and C. Karamanolis. Sinfonia: a new paradigm for building scalable distributed systems. In ACM SIGOPS Operating Systems Review, volume 41, pages 159--174. ACM, 2007. Google ScholarDigital Library
- T. E. Anderson. The performance of spin lock alternatives for shared-money multiprocessors. IEEE TPDS, 1(1):6--16, 1990. Google ScholarDigital Library
- H. Attiya, R. Guerraoui, D. Hendler, P. Kuznetsov, M. M. Michael, and M. Vechev. Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated. In ACM SIGPLAN Notices, volume 46, 2011. Google ScholarDigital Library
- H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O'Neil, and P. O'Neil. A critique of ansi sql isolation levels. In Proc. of SIGMOD, pages 1--10, 1995. Google ScholarDigital Library
- M. J. Cahill. Serializable Isolation for Snapshot Databases. PhD thesis, University of Sydney, 2009.Google ScholarDigital Library
- M. J. Cahill, U. Röhm, and A. D. Fekete. Serializable isolation for snapshot databases. In Proc. of SIGMOD, pages 729--738, 2008. Google ScholarDigital Library
- B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with ycsb. SoCC, 2010. Google ScholarDigital Library
- J. M. Faleiro, A. Thomson, and D. J. Abadi. Lazy evaluation of transactions in database systems. Proc. of SIGMOD, pages 15--26, 2014. Google ScholarDigital Library
- A. Fekete. Allocating isolation levels to transactions. In Proc. of PODS, 2005. Google ScholarDigital Library
- A. Fekete, D. Liarokapis, E. O'Neil, P. O'Neil, and D. Shasha. Making snapshot isolation serializable. TODS, 30(2):492--528, 2005. Google ScholarDigital Library
- A. Fekete, E. O'Neil, and P. O'Neil. A read-only transaction anomaly under snapshot isolation. ACM SIGMOD Record, 33(3):12--14, 2004. Google ScholarDigital Library
- J. Gray, P. Sundaresan, S. Englert, K. Baclawski, and P. J. Weinberger. Quickly generating billion-record synthetic databases. Proc. of SIGMOD, 1994. Google ScholarDigital Library
- S. Harizopoulos, D. Abadi, S. Madden, and M. Stonebraker. Oltp through the looking glass, and what we found there. Proc. of SIGMOD, 2008. Google ScholarDigital Library
- K. Jacobs, R. Bamford, G. Doherty, K. Haas, M. Holt, F. Putzolu, and B. Quigley. Concurrency control, transaction isolation, and serializability in SQL 92 and Oracle 7. Oracle Whitepaper, Part No. A33745, 1995.Google Scholar
- R. Johnson, I. Pandis, and A. Ailamaki. Improving oltp scalability using speculative lock inheritance. PVLDB, 2(1):479--489, 2009. Google ScholarDigital Library
- H. Jung, H. Han, A. D. Fekete, G. Heiser, and H. Y. Yeom. A scalable lock manager for multicores. In Proc. of SIGMOD, 2013. Google ScholarDigital Library
- P.-A. Larson, S. Blanas, C. Diaconu, C. Freedman, J. M. Patel, and M. Zwilling. High-performance concurrency control mechanisms for main-memory databases. PVLDB, 5(4):298--309, Dec. 2011. 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
- P. E. Mckenney, J. Appavoo, A. Kleen, O. Krieger, O. Krieger, R. Russell, D. Sarma, and M. Soni. Read-copy update. In In Ottawa Linux Symposium, pages 338--367, 2001.Google Scholar
- J. M. Mellor-Crummey and M. L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems (TOCS), 9(1):21--65, 1991. Google ScholarDigital Library
- I. Moraru, D. G. Andersen, and M. Kaminsky. There is more consensus in egalitarian parliaments. In Proc. of SOSP, 2013. Google ScholarDigital Library
- I. Pandis, R. Johnson, N. Hardavellas, and A. Ailamaki. Data-oriented transaction execution. PVLDB, 3(1-2):928--939, 2010. Google ScholarDigital Library
- K. Ren, A. Thomson, and D. J. Abadi. Lightweight locking for main memory database systems. PVLDB, 6(2):145--156, Dec. 2012. Google ScholarDigital Library
- K. Ren, A. Thomson, and D. J. Abadi. An evaluation of the advantages and disadvantages of deterministic database systems. PVLDB, 7(10):821--832, 2014. 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. Modularity and scalability in calvin. IEEE Data Engineering Bulletin, 36(2): 48--55, 2013.Google Scholar
- 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
- A. Thomson, T. Diamond, S.-C. Weng, K. Ren, P. Shao, and D. J. Abadi. Fast distributed transactions and strongly consistent replication for oltp database systems. ACM Trans. Database Syst., 39(2):11:1--11:39, May 2014. Google ScholarDigital Library
- S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden. Speedy transactions in multicore in-memory databases. SOSP, 2013. Google ScholarDigital Library
- M. Welsh, D. Culler, and E. Brewer. Seda: An architecture for well-conditioned, scalable internet services. In SOSP, 2001. 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
- Rethinking serializable multiversion concurrency control
Recommendations
Multiversion Cautious Schedulers for Database Concurrency Control
Let MC stand for a class of logs (i.e. sequences of read/write steps of transactions) that are serializable when multiple versions of the data items are maintained. The multiversion cautious scheduler, MCS(MC) which is introduced, outputs a sequence ...
Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems
SIGMOD '15: Proceedings of the 2015 ACM SIGMOD International Conference on Management of DataMulti-Version Concurrency Control (MVCC) is a widely employed concurrency control mechanism, as it allows for execution modes where readers never block writers. However, most systems implement only snapshot isolation (SI) instead of full ...
Efficiently making (almost) any concurrency control mechanism serializable
Concurrency control (CC) algorithms must trade off strictness for performance. In particular, serializable CC schemes generally pay higher cost to prevent anomalies, both in runtime overhead such as the maintenance of lock tables and in efforts wasted ...
Comments