Yingjun Wu
ABSTRACT
Main-memory database management systems (DBMS) can achieve excellent performance when processing massive volume of on-line transactions on modern multi-core machines. But existing durability schemes, namely, tuple-level and transaction-level logging-and-recovery mechanisms, either degrade the performance of transaction processing or slow down the process of failure recovery. In this paper, we show that, by exploiting application semantics, it is possible to achieve speedy failure recovery without introducing any costly logging overhead to the execution of concurrent transactions. We propose PACMAN, a parallel database recovery mechanism that is specifically designed for lightweight, coarse-grained transaction-level logging. PACMAN leverages a combination of static and dynamic analyses to parallelize the log recovery: at compile time, PACMAN decomposes stored procedures by carefully analyzing dependencies within and across programs; at recovery time, PACMAN exploits the availability of the runtime parameter values to attain an execution schedule with a high degree of parallelism. As such, recovery performance is remarkably increased. We evaluated PACMAN in a fully-fledged main-memory DBMS running on a 40-core machine. Compared to several state-of-the-art database recovery mechanisms, can significantly reduce recovery time without compromising the efficiency of transaction processing.
- MySQL. http://www.mysql.com.Google Scholar
- OLTPBench. http://oltpbenchmark.com/.Google Scholar
- Oracle. http://www.oracle.com.Google Scholar
- F. E. Allen. Control Flow Analysis. In ACM SIGPLAN Notices, 1970. Google ScholarDigital Library
- T. M. Austin and G. S. Sohi. Dynamic Dependency Analysis of Ordinary Programs. In ISCA, 1992. Google ScholarDigital Library
- T. Cao, M. Vaz Salles, B. Sowell, Y. Yue, A. Demers, J. Gehrke, and W. White. Fast Checkpoint Recovery Algorithms for Frequently Consistent Applications. In SIGMOD, 2011. Google ScholarDigital Library
- A. Cheung, S. Madden, O. Arden, and A. C. Myers. Automatic Partitioning of Database Applications. In VLDB, 2012. Google ScholarDigital Library
- J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford. Spanner: Google's Globally-Distributed Database. In OSDI, 2012. Google ScholarDigital Library
- D. J. DeWitt, R. H. Katz, F. Olken, L. D. Shapiro, M. R. Stonebraker, and D. A. Wood. Implementation Techniques for Main Memory Database Systems. In SIGMOD, 1984. Google ScholarDigital Library
- C. Diaconu, C. Freedman, E. Ismert, P.-A. Larson, P. Mittal, R. Stonecipher, N. Verma, and M. Zwilling. Hekaton: SQL Server's Memory-Optimized OLTP Engine. In SIGMOD, 2013. Google ScholarDigital Library
- D. E. Difallah, A. Pavlo, C. Curino, and P. Cudre-Mauroux. OLTP-Bench: An Extensible Testbed for Benchmarking Relational Databases. In VLDB, 2013. Google ScholarDigital Library
- D. Gawlick and D. Kinkade. Varieties of Concurrency Control in IMS/VS Fast Path. IEEE Data Eng. Bull., 8(2), 1985.Google Scholar
- J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. 1992. Google ScholarDigital Library
- M. Grund, J. Krüger, H. Plattner, A. Zeier, P. Cudre-Mauroux, and S. Madden. HYRISE: A Main-Memory Hybrid Storage Engine. In VLDB, 2010. Google ScholarDigital Library
- R. Johnson, I. Pandis, N. Hardavellas, A. Ailamaki, and B. Falsafi. Shore-MT: A Scalable Storage Manager for the Multicore Era. In EDBT, 2009. Google ScholarDigital Library
- R. Johnson, I. Pandis, R. Stoica, M. Athanassoulis, and A. Ailamaki. Aether: A Scalable Approach to Logging. In VLDB, 2010. Google ScholarDigital Library
- R. Kallman, H. Kimura, J. Natkins, A. Pavlo, A. Rasin, S. Zdonik, E. P. C. Jones, S. Madden, M. Stonebraker, Y. Zhang, J. Hugg, and D. J. Abadi. H-Store: A High-Performance, Distributed Main Memory Transaction Processing System. In VLDB, 2008. Google ScholarDigital Library
- A. Kemper and T. Neumann. HyPer: A Hybrid OLTP & OLAP Main Memory Database System Based on Virtual Memory Snapshots. In ICDE, 2011. Google ScholarDigital Library
- K. Kim, T. Wang, J. Ryan, and I. Pandis. ERMIA: Fast Memory-Optimized Database System for Heterogeneous Workloads. In SIGMOD, 2016. Google ScholarDigital Library
- J. Lee, K. Kim, and S. K. Cha. Differential Logging: A Commutative and Associative Logging Scheme for Highly Parallel Main Memory Database. In ICDE, 2001. Google ScholarDigital Library
- X. Li and M. H. Eich. Post-Crash Log Processing for Fuzzy Checkpointing Main Memory Databases. In ICDE, 1993. Google ScholarDigital Library
- A.-P. Liedes and A. Wolski. Siren: A Memory-Conserving, Snapshot-Consistent Checkpoint Algorithm for In-Memory Databases. In ICDE, 2006. Google ScholarDigital Library
- D. Lomet, K. Tzoumas, and M. Zwilling. Implementing Performance Competitive Logical Recovery. In VLDB, 2011. Google ScholarDigital Library
- N. Malviya, A. Weisberg, S. Madden, and M. Stonebraker. Rethinking Main Memory OLTP Recovery. In ICDE, 2014.Google ScholarCross Ref
- C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, and P. Schwarz. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. TODS, 17(1), 1992. Google ScholarDigital Library
- S. Mu, Y. Cui, Y. Zhang, W. Lloyd, and J. Li. Extracting More Concurrency from Distributed Transactions. In OSDI, 2014. Google ScholarDigital Library
- N. Narula, C. Cutler, E. Kohler, and R. Morris. Phase Reconciliation for Contended In-Memory Transactions. In OSDI, 2014. Google ScholarDigital Library
- F. Nielson, H. R. Nielson, and C. Hankin. Principles of Program Analysis. 1999. Google ScholarDigital Library
- D. Ongaro, S. M. Rumble, R. Stutsman, J. Ousterhout, and M. Rosenblum. Fast Crash Recovery in RAMCloud. In SOSP, 2011. Google ScholarDigital Library
- I. Pandis, R. Johnson, N. Hardavellas, and A. Ailamaki. Data-Oriented Transaction Execution. In VLDB, 2010. Google ScholarDigital Library
- A. Pavlo, G. Angulo, J. Arulraj, H. Lin, J. Lin, L. Ma, P. Menon, T. C. Mowry, M. Perron, I. Quah, S. Santurkar, A. Tomasic, S. Toor, D. Van Aken, Z. Wang, Y. Wu, R. Xian, and T. Zhang. Self-Driving Database Management Systems. In CIDR, 2017.Google Scholar
- K. Ramachandra, R. Guravannavar, and S. Sudarshan. Program Analysis and Transformation for Holistic Optimization of Database Applications. In SOAP, 2012. Google ScholarDigital Library
- K. Ren, T. Diamond, D. J. Abadi, and A. Thomson. Low-Overhead Asynchronous Checkpointing in Main-Memory Database Systems. In SIGMOD, 2016. Google ScholarDigital Library
- K. Salem and H. Garcia-Molina. Checkpointing Memory-Resident Databases. In ICDE, 1989. Google ScholarDigital Library
- D. Schwalb, M. Faust, J. Wust, M. Grund, and H. Plattner. Efficient Transaction Processing for Hyrise in Mixed Workload Environments. In IMDM. 2015.Google ScholarCross Ref
- D. Shasha, F. Llirbat, E. Simon, and P. Valduriez. Transaction Chopping: Algorithms and Performance Studies. TODS, 20(3), 1995. Google ScholarDigital Library
- B. Steensgaard. Points-To Analysis in Almost Linear Time. In POPL, 1996. Google ScholarDigital Library
- M. Stonebraker, S. 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 VLDB, 2007. Google ScholarDigital Library
- A. Thomson, T. Diamond, S.-C. Weng, K. Ren, P. Shao, and D. J. Abadi. Calvin: Fast Distributed Transactions for Partitioned Database Systems. In SIGMOD, 2012. Google ScholarDigital Library
- S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden. Speedy Transactions in Multicore In-Memory Databases. In SOSP, 2013. Google ScholarDigital Library
- T. Wang and R. Johnson. Scalable Logging Through Emerging Non-Volatile Memory. In VLDB, 2014. Google ScholarDigital Library
- Y. Wu, J. Arulraj, J. Lin, R. Xian, and A. Pavlo. An Empirical Evaluation of In-Memory Multi-Version Concurrency Control. In VLDB, 2017. Google ScholarDigital Library
- Y. Wu, C.-Y. Chan, and K.-L. Tan. Transaction Healing: Scaling Optimistic Concurrency Control on Multicores. In SIGMOD, 2016. Google ScholarDigital Library
- Y. Wu and K.-L. Tan. Scalable In-Memory Transaction Processing with H™. In USENIX ATC, 2016. Google ScholarDigital Library
- C. Yan and A. Cheung. Leveraging lock contention to improve oltp application performance. In VLDB, 2016. Google ScholarDigital Library
- C. Yao, D. Agrawal, G. Chen, B. C. Ooi, and S. Wu. Adaptive Logging: Optimizing Logging and Recovery Costs in Distributed In-Memory Databases. In SIGMOD, 2016. Google ScholarDigital Library
- Y. Zhang, R. Power, S. Zhou, Y. Sovran, M. K. Aguilera, and J. Li. Transaction Chains: Achieving Serializability With Low Latency in Geo-Distributed Storage Systems. In SOSP, 2013. Google ScholarDigital Library
- W. Zheng, S. Tu, E. Kohler, and B. Liskov. Fast Databases With Fast Durability and Recovery Through Multicore Parallelism. In OSDI, 2014. Google ScholarDigital Library
Index Terms
- Fast Failure Recovery for Main-Memory DBMSs on Multicores
Recommendations
Main Memory Database Recovery: A Survey
Many of today’s applications need massive real-time data processing. In-memory database systems have become a good alternative for these requirements. These systems maintain the primary copy of the database in the main memory to achieve high throughput ...
A Checkpointing Strategy and Redo Point Strategy for Embedded Real-Time Main Memory Databases Crash Recovery
CSIE '09: Proceedings of the 2009 WRI World Congress on Computer Science and Information Engineering - Volume 02In the embedded environment, the rapid and efficient recovery is needed in the event of the real-time main memory database system failures. Checkpointing strategy is very important for system recovery as one of the most important techniques of real-time ...
Main Memory Database Recovery Strategies
SIGMOD '23: Companion of the 2023 International Conference on Management of DataMost of the current application scenarios, such as trading, real-time bidding, advertising, weather forecasting, social gaming, etc., require massive real-time data processing. Main memory database systems have proved to be an efficient alternative to ...
Comments