Timestamp reassignment: taming transaction abort for serializable snapshot isolation
Ningnan ZHOU1,2, Xiao ZHANG1,2(), Shan WANG1,2
1. MOE Key Laboratory of DEKE, Renmin University of China, Beijing 100872, China 2. School of Information, Renmin University of China, Beijing 100872, China
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.
H Esmaeilzadeh, E Belm, R S Amant, K Sanharalingam, D Burger. Power challenges may end the multicore era. Communications of ACM, 2013, 56(2): 93–102 https://doi.org/10.1145/2408776.2408797
2
T Horikawa. 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 https://doi.org/10.1145/2463676.2463720
3
D R K Ports, K Grittner. Serializable snapshot isolation in PostgreSQL. Proceedings of the VLDB Endowment, 2012, 5(12): 1850–1861 https://doi.org/10.14778/2367502.2367523
4
M J Cahill, U Röhm, A D Fekete. Serializable isolation for snapshot databases. ACM Transactions on Database Systems, 2009, 34(4): 20 https://doi.org/10.1145/1620585.1620587
5
S Revilak, P O’Neil, , E O’Neil. Precisely serializable snapshot isolation (PSSI). In: Proceedings of the 27th IEEE International Conference on Data Engineering. 2011, 482–493 https://doi.org/10.1109/ICDE.2011.5767853
6
H Berenson, P Bernstein, J Gray, J Melton, E O’Neil, P O’Neil. A critique of ANSI SQL isolation levels. In: Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. 1995, 1–10 https://doi.org/10.1145/223784.223785
7
A Adya. Weak consistency: a generalized theory and optimistic implementations for distributed transactions. Massachusetts Institute of Technology, 1999
8
A D Fekete, D Liarokapis, E O’Neil, P O’Neil, D Shasha. Making snapshot isolation serializable. ACM Transactions on Database Systems, 2005, 20(2): 492–528 https://doi.org/10.1145/1071610.1071615
9
M J Cahill, U Röhm, A D Fekete. Serializable isolation for snapshot databases. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. 2008, 729–738 https://doi.org/10.1145/1376616.1376690
10
S Finkelstein. Common expression analysis in database applications. In: Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data. 1982, 235–245 https://doi.org/10.1145/582353.582400
S Harizopoulos, V Shkapenyuk, A Ailamaki. QPipe: a simultaneously pipelined relational query engine. In: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. 2005, 383–394 https://doi.org/10.1145/1066157.1066201
13
G Candea, N Polyzotis, R Vingralek. A scalable, predictable join operator for highly concurrent data warehouses. Proceedings of the VLDB Endowment, 2009, 2(1): 277–288 https://doi.org/10.14778/1687627.1687659
14
S Arumugam, A Dobra, C M Jermaine, N Pansare, L Perez. 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 https://doi.org/10.1145/1807167.1807224
15
G Giannikis, G Alonso, D Kossmann. SharedDB: killing one thousand queries with one stone. Proceedings of the VLDB Endowment, 2012, 5(6): 526–537 https://doi.org/10.14778/2168651.2168654
16
M Chavan, R Guravannavar, K Ramachandra, S Sudarshan. DBridge: a program rewrite tool for set-oriented query execution. In: Proceedings of the 27th IEEE International Conference on Data Engineering. 2011, 1284–1287 https://doi.org/10.1109/ICDE.2011.5767949
17
R Guravannavar, S Sudarshan. Rewriting procedures for batched bindings. Proceedings of the VLDB Endowment, 2008, 1(1): 1107–1123 https://doi.org/10.14778/1453856.1453975
18
A Cheung, S Madden, A Solar-Lezama. 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 https://doi.org/10.1145/2588555.2593672
19
A Cheung, S Madden, , O Arden, A C Myers. Automatic partitioning of database applications. Proceedings of the VLDB Endowment, 2012, 5(11): 1471–1482 https://doi.org/10.14778/2350229.2350262
20
D Shasha, F Llirbat, E Simon, P Valduriez. Transaction chopping: algorithms and performance studies. ACM Transactions on Database Systems, 1995, 20(3): 325–363 https://doi.org/10.1145/211414.211427
21
P A Bernstein, D W Shipman, J B Rothnie. Concurrency control in a system for distributed databases (SDD-1). ACM Transactions on Database Systems, 1980, 5(1): 18–51 https://doi.org/10.1145/320128.320131
22
D Agrawal, A A El, R Jeffers, L J Lin. Ordered shared locks for realtime databases. The VLDB Journal, 1995, 4(1): 87–126 https://doi.org/10.1007/BF01232473
23
C Xie, C Z Su, C Littley, L Alivisi, M Kapritsos, Y Wang. Highperformance ACID via modular concurrency control. In: Proceedings of the 25th Symposium on Operating Systems Principles. 2015, 279–294 https://doi.org/10.1145/2815400.2815430
24
C Yan, A Cheung. Leveraging lock contention to improve OLTP application performance. Proceedings of the VLDB Endowment, 2016, 9(5): 444–455 https://doi.org/10.14778/2876473.2876479
25
J M Faleiro, A Thomson, D J Abadi. Lazy evaluation of transactions in database systems. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 2014, 15–26 https://doi.org/10.1145/2588555.2610529
26
S Roy, L Kot, G Bender, B L Ding, H Hojjat, C Koch, N Foster, J Gehrke. 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 https://doi.org/10.1145/2723372.2723720
27
P Bailis, A Fekete, M J Franklin, A Ghodsi, J M Hellerstein, I Stoica. Coordination avoidance in database systems. Proceedings of the VLDB Endowment, 2014, 8(3): 185–196 https://doi.org/10.14778/2735508.2735509
28
Z G Wang, S Mu, Y Cui, H Yi, H B Chen, J Y Li. Scaling multicore databases via constrained parallel execution. In: Proceedings of the 2016 International Conference on Management of Data. 2016, 1643–1658 https://doi.org/10.1145/2882903.2882934
29
M Stonebraker, S Madden, D J Abadi, S Harizopoulos, N Hachem, P Helland. 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
J M Faleiro, D J Abadi, J M Hellerstein. High performance transactions via early write visibility. Proceedings of the VLDB Endowment, 2017, 10(5): 613–624 https://doi.org/10.14778/3055540.3055553
31
M Alomari, M Cahill, A Fekete, U Rohm. The cost of serializability on platforms that use snapshot isolation. In: Proceedings of the 24th IEEE International Conference on Data Engineering. 2008, 576–585 https://doi.org/10.1109/ICDE.2008.4497466
32
U Sirin, P Tözün, D Porobic, A Ailamaki. Micro-architectural analysis of in-memory OLTP. In: Proceedings of the 2016 International Conference on Management of Data. 2016, 387–402 https://doi.org/10.1145/2882903.2882916
