|
|
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 |
|
|
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
|
Corresponding Author(s):
Xiao ZHANG
|
Just Accepted Date: 25 September 2017
Online First Date: 15 November 2018
Issue Date: 19 July 2019
|
|
1 |
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
|
11 |
T K Sellis. Multiple-query optimization. ACM Transactions on Database Systems, 1988, 13(1): 23–52
https://doi.org/10.1145/42201.42203
|
12 |
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|