Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2019, Vol. 13 Issue (6) : 1282-1295    https://doi.org/10.1007/s11704-018-7018-z
RESEARCH ARTICLE
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
 Download: PDF(732 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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
 Cite this article:   
Ningnan ZHOU,Xiao ZHANG,Shan WANG. Timestamp reassignment: taming transaction abort for serializable snapshot isolation[J]. Front. Comput. Sci., 2019, 13(6): 1282-1295.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-018-7018-z
https://academic.hep.com.cn/fcs/EN/Y2019/V13/I6/1282
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
[1] Zhenbo XU,Jian ZHANG,Zhongxing XU. Melton: a practical and precise memory leak detection tool for C programs[J]. Front. Comput. Sci., 2015, 9(1): 34-54.
[2] Mingsong LV, Nan GUAN, Qingxu DENG, Ge YU, Wang Yi, . Static worst-case execution time analysis of the μ C/OS-II real-time kernel[J]. Front. Comput. Sci., 2010, 4(1): 17-27.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed