Timestamp reassignment: taming transaction abort for serializable snapshot isolation

Abstract

Serializable snapshot isolation (SSI) is a promising technique to exploit parallelism for multi-core databases. However, SSI suffers from excessive transaction aborts. Existing remedies have three drawbacks: 1) tracking prohibitively transitive dependencies; 2) aborting on every writewrite conflict; and 3) requiring manual annotation on transaction programs.

In this paper, we propose to suppress transaction aborts by reassigning timestamps. We combine static analysis with augmented query plan. In this way, we save both aborts caused by read-write and write-write conflicts, without tracking transitive dependency and annotating transaction programs. As such, our approach does not exhibit drawbacks of existing methods. Extensive experiments demonstrate the effectiveness and practicality of our approach.

Keywords

serializable snapshot isolation / timestamp reassignment / static analysis / augmented query plan

References

[1] Esmaeilzadeh H, Belm E, Amant R S, Sanharalingam K, Burger D. Power challenges may end the multicore era. Communications of ACM, 2013, 56(2): 93–102

[2] Horikawa T. Latch-free data structures for DBMS: design, implementation, and evaluation. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 2013, 409–420

[3] Ports D R K, Grittner K. Serializable snapshot isolation in PostgreSQL. Proceedings of the VLDB Endowment, 2012, 5(12): 1850–1861

[4] Cahill M J, Röhm U, Fekete A D. Serializable isolation for snapshot databases. ACM Transactions on Database Systems, 2009, 34(4): 20

[5] Revilak S, O’Neil P, O’Neil , E. Precisely serializable snapshot isolation (PSSI). In: Proceedings of the 27th IEEE International Conference on Data Engineering. 2011, 482–493

[6] Berenson H, Bernstein P, Gray J, Melton J, O’Neil E, O’Neil P. A critique of ANSI SQL isolation levels. In: Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. 1995, 1–10

[7] Adya A. Weak consistency: a generalized theory and optimistic implementations for distributed transactions. Massachusetts Institute of Technology, 1999

[8] Fekete A D, Liarokapis D, O’Neil E, O’Neil P, Shasha D. Making snapshot isolation serializable. ACM Transactions on Database Systems, 2005, 20(2): 492–528

[9] Cahill M J, Röhm U, Fekete A D. Serializable isolation for snapshot databases. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. 2008, 729–738

[10] Finkelstein S. Common expression analysis in database applications. In: Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data. 1982, 235–245

[11] Sellis T K. Multiple-query optimization. ACM Transactions on Database Systems, 1988, 13(1): 23–52

[12] Harizopoulos S, Shkapenyuk V, Ailamaki A. QPipe: a simultaneously pipelined relational query engine. In: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. 2005, 383–394

[13] Candea G, Polyzotis N, Vingralek R. A scalable, predictable join operator for highly concurrent data warehouses. Proceedings of the VLDB Endowment, 2009, 2(1): 277–288

[14] Arumugam S, Dobra A, Jermaine C M, Pansare N, Perez L. The DataPath system: a data-centric analytic processing engine for large data warehouses. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. 2010, 519–530

[15] Giannikis G, Alonso G, Kossmann D. SharedDB: killing one thousand queries with one stone. Proceedings of the VLDB Endowment, 2012, 5(6): 526–537

[16] Chavan M, Guravannavar R, Ramachandra K, Sudarshan S. DBridge: a program rewrite tool for set-oriented query execution. In: Proceedings of the 27th IEEE International Conference on Data Engineering. 2011, 1284–1287

[17] Guravannavar R, Sudarshan S. Rewriting procedures for batched bindings. Proceedings of the VLDB Endowment, 2008, 1(1): 1107–1123

[18] Cheung A, Madden S, Solar-Lezama A. Sloth: being lazy is a virtue (when issuing database queries). In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 2014, 931–942

[19] Cheung A, Madden S, Arden , O, Myers A C. Automatic partitioning of database applications. Proceedings of the VLDB Endowment, 2012, 5(11): 1471–1482

[20] Shasha D, Llirbat F, Simon E, Valduriez P. Transaction chopping: algorithms and performance studies. ACM Transactions on Database Systems, 1995, 20(3): 325–363

[21] Bernstein P A, Shipman D W, Rothnie J B. Concurrency control in a system for distributed databases (SDD-1). ACM Transactions on Database Systems, 1980, 5(1): 18–51

[22] Agrawal D, El A A, Jeffers R, Lin L J. Ordered shared locks for realtime databases. The VLDB Journal, 1995, 4(1): 87–126

[23] Xie C, Su C Z, Littley C, Alivisi L, Kapritsos M, Wang Y. Highperformance ACID via modular concurrency control. In: Proceedings of the 25th Symposium on Operating Systems Principles. 2015, 279–294

[24] Yan C, Cheung A. Leveraging lock contention to improve OLTP application performance. Proceedings of the VLDB Endowment, 2016, 9(5): 444–455

[25] Faleiro J M, Thomson A, Abadi D J. Lazy evaluation of transactions in database systems. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 2014, 15–26

[26] Roy S, Kot L, Bender G, Ding B L, Hojjat H, Koch C, Foster N, Gehrke J. The homeostasis protocol: avoiding transaction coordination through program analysis. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015, 1311–1326

[27] Bailis P, Fekete A, Franklin M J, Ghodsi A, Hellerstein J M, Stoica I. Coordination avoidance in database systems. Proceedings of the VLDB Endowment, 2014, 8(3): 185–196

[28] Wang Z G, Mu S, Cui Y, Yi H, Chen H B, Li J Y. Scaling multicore databases via constrained parallel execution. In: Proceedings of the 2016 International Conference on Management of Data. 2016, 1643–1658

[29] Stonebraker M, Madden S, Abadi D J, Harizopoulos S, Hachem N, Helland P. The end of an architectural era: (it’s time for a complete rewrite). In: Proceedings of the 33rd International Conference on Very Large Data Bases. 2007, 1150–1160

[30] Faleiro J M, Abadi D J, Hellerstein J M. High performance transactions via early write visibility. Proceedings of the VLDB Endowment, 2017, 10(5): 613–624

[31] Alomari M, Cahill M, Fekete A, Rohm U. The cost of serializability on platforms that use snapshot isolation. In: Proceedings of the 24th IEEE International Conference on Data Engineering. 2008, 576–585

[32] Sirin U, Tözün P, Porobic D, Ailamaki A. Micro-architectural analysis of in-memory OLTP. In: Proceedings of the 2016 International Conference on Management of Data. 2016, 387–402

RIGHTS & PERMISSIONS

2018 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature