ACM SIGMOD Anthology TODS dblp.uni-trier.de

ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging.

C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17(1): 94-162(1992)
@article{DBLP:journals/tods/MohanHLPS92,
  author    = {C. Mohan and
               Donald J. Haderle and
               Bruce G. Lindsay and
               Hamid Pirahesh and
               Peter M. Schwarz},
  title     = {ARIES: A Transaction Recovery Method Supporting Fine-Granularity
               Locking and Partial Rollbacks Using Write-Ahead Logging},
  journal   = {ACM Trans. Database Syst.},
  volume    = {17},
  number    = {1},
  year      = {1992},
  pages     = {94-162},
  ee        = {http://doi.acm.org/10.1145/128765.128770, db/journals/tods/MohanHLPS92.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we present a simple and efficient method, called ARIES (Algorithm for Recovery and Isolation Exploiting Semantics), which supports partial rollbacks of transactions, fine-granularity (e. g., record) locking and recovery using write-ahead logging (WAL). We introduce the paradigm of repeating history to redo all missing updates before performing the rollbacks of the loser transactions during restart after a system failure. ARIES uses a log sequence number in each page to correlate the state of a page with respect to logged updates of that page. All updates of a transaction are logged, including those performed during rollbacks. By appropriate chaining of the log records written during rollbacks to those written during forward progress, a bounded amount of logging is ensured during rollbacks even in the face of repeated failures during restart or of nested rollbacks. We deal with a variety of features that are very important in building and operating an industrial-strength transaction processing system. ARIES supports fuzzy checkpoints, selective and deferred restart, fuzzy image copies, media recovery, and high concurrency lock modes (e. g., increment/decrement) which exploit the semantics of the operations and require the ability to perform operation logging. ARIES is flexible with respect to the kinds of buffer management policies that can be implemented. It supports objects of varying length efficiently. By enabling parallelism during restart, page-oriented redo, and logical undo, it enhances concurrency and performance. We show why some of the System R paradigms for logging and recovery, which were based on the shadow page technique, need to be changed in the context of WAL. We compare ARIES to the WAL-based recovery methods of DB2TM, IMS, and TandemTM systems. ARIES is applicable not only to database management systems but also to persistent object-oriented languages, recoverable file systems and transaction-based operating systems. ARIES has been implemented, to varying degrees, in IBM's OS/2TM Extended Edition Database Manager, DB2, Workstation Data Save Facility/VM, Starburst and QuickSilver, and in the University of Wisconsin's EXODUS and Gamma database machine.

Copyright © 1992 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 5107 KB]

References

[1]
...
[2]
B. R. Badrinath, Krithi Ramamritham: Semantics-Based Concurrency Control: Beyond Commutativity. ICDE 1987: 304-311 BibTeX
[3]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[4]
Andrea J. Borr: Robustness to Crash in a Distributed Database: A Non Shared-memory Multi-Processor Approach. VLDB 1984: 445-453 BibTeX
[5]
Donald D. Chamberlin, A. M. Gilbert, Robert A. Yost: A History of System R and SQL/Data System (Invited Paper). VLDB 1981: 456-464 BibTeX
[6]
Albert Chang, Mark F. Mergen: 801 Storage: Architecture and Programming. ACM Trans. Comput. Syst. 6(1): 28-50(1988) BibTeX
[7]
Philip Y. Chang, William W. Myre: OS/2 EE Database Manager Overview and Technical Highlights. IBM Systems Journal 27(2): 105-118(1988) BibTeX
[8]
George P. Copeland, Setrag Khoshafian, Marc G. Smith, Patrick Valduriez: Buffering Schemes for Permanent Data. ICDE 1986: 214-221 BibTeX
[9]
Brian E. Clark, Michael J. Corrigan: Application System/400 Performance Characteristics. IBM Systems Journal 28(3): 407-423(1989) BibTeX
[10]
Josephine M. Cheng, Christopher R. Looseley, Akira Shibamiya, Patricia S. Worthington: IBM Database 2 Performance: Design, Implementation, and Tuning. IBM Systems Journal 23(2): 189-210(1984) BibTeX
[11]
...
[12]
...
[13]
...
[14]
...
[15]
Richard A. Crus: Data Recovery in IBM Database 2. IBM Systems Journal 23(2): 178-188(1984) BibTeX
[16]
...
[17]
Partha Dasgupta, Richard J. LeBlanc, William F. Appelbe: The Clouds Distributed Operating System. ICDCS 1988: 2-9 BibTeX
[18]
...
[19]
...
[20]
David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen: The Gamma Database Machine Project. IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990) BibTeX
[21]
...
[22]
Graeme N. Dixon, Graham D. Parrington, Santosh K. Shrivastava, Stuart M. Wheater: The Treatment of Persistent Objects in Arjuna. Comput. J. 32(4): 323-332(1989) BibTeX
[23]
...
[24]
Wolfgang Effelsberg, Theo Härder: Principles of Database Buffer Management. ACM Trans. Database Syst. 9(4): 560-595(1984) BibTeX
[25]
Klaus Elhardt, Rudolf Bayer: A Database Cache for High Performance and Fast Restart in Database Systems. ACM Trans. Database Syst. 9(4): 503-525(1984) BibTeX
[26]
Alan Fekete, Nancy A. Lynch, Michael Merritt, William E. Weihl: Commutativity-Based Locking for Nested Transactions. J. Comput. Syst. Sci. 41(1): 65-156(1990) BibTeX
[27]
...
[28]
Dieter Gawlick, David Kinkade: Varieties of Concurrency Control in IMS/VS Fast Path. IEEE Database Eng. Bull. 8(2): 3-10(1985) BibTeX
[29]
Jorge F. Garza, Won Kim: Transaction Management in an Object-Oriented Database System (Invited Paper). SIGMOD Conference 1988: 37-45 BibTeX
[30]
...
[31]
Jim Gray, Paul R. McJones, Mike W. Blasgen, Bruce G. Lindsay, Raymond A. Lorie, Thomas G. Price, Gianfranco R. Putzolu, Irving L. Traiger: The Recovery Manager of the System R Database Manager. ACM Comput. Surv. 13(2): 223-243(1981) BibTeX
[32]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[33]
Vassos Hadzilacos: A theory of reliability in database systems. J. ACM 35(1): 121-145(1988) BibTeX
[34]
Theo Härder: Handling hot spot in DB-sharing systems. Inf. Syst. 13(2): 155-166(1988) BibTeX
[35]
Donald J. Haderle, Robert D. Jackson: IBM Database 2 Overview. IBM Systems Journal 23(2): 112-125(1984) BibTeX
[36]
Theo Härder, Andreas Reuter: Principles of Transaction-Oriented Database Recovery. ACM Comput. Surv. 15(4): 287-317(1983) BibTeX
[37]
...
[38]
Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. PODS 1988: 201-210 BibTeX
[39]
...
[40]
Roger L. Haskin, Yoni Malachi, Wayne Sawdon, Gregory Chan: Recovery Management in QuickSilver. ACM Trans. Comput. Syst. 6(1): 82-108(1988) BibTeX
[41]
...
[42]
...
[43]
...
[44]
...
[45]
Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) BibTeX
[46]
Vincent Y. Lum, Peter Dadam, R. Erbe, Jürgen Günauer, Peter Pistor, Georg Walch, H. Werner, John Woodfill: Design of an Integrated DBMS to Support Advanced Applications. FODO 1985: 31-49 BibTeX
[47]
...
[48]
...
[49]
Bruce G. Lindsay, Laura M. Haas, C. Mohan, Paul F. Wilms, Robert A. Yost: Computation and Communication in R*: A Distributed Database Manager. ACM Trans. Comput. Syst. 2(1): 24-38(1984) BibTeX
[50]
...
[51]
Barbara Liskov, Robert Scheifler: Guardians and Actions: Linguistic Support for Robust, Distributed Programs. ACM Trans. Program. Lang. Syst. 5(3): 381-404(1983) BibTeX
[52]
...
[53]
...
[54]
C. Mohan, Donald J. Haderle, Yun Wang, Josephine M. Cheng: Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. EDBT 1990: 29-43 BibTeX
[55]
C. Mohan, Donald S. Fussell, Abraham Silberschatz: Compatibility and Commutativity of Lock Modes. Information and Control 61(1): 38-64(1984) BibTeX
[56]
J. Eliot B. Moss, Nancy D. Griffeth, Marc H. Graham: Abstraction in Recovery Management. SIGMOD Conference 1986: 72-83 BibTeX
[57]
C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405 BibTeX
[58]
C. Mohan: Commit_LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems. VLDB 1990: 406-418 BibTeX
[59]
...
[60]
...
[61]
J. Eliot B. Moss, Bruce Leban, Panos K. Chrysanthis: Finer Grained Concurrency for the Database Cache. ICDE 1987: 96-103 BibTeX
[62]
...
[63]
C. Mohan, Bruce G. Lindsay: Efficient Commit Protocols for the Tree of Processes Model of Distributed Transactions. PODC 1983: 76-88 BibTeX
[64]
C. Mohan, Bruce G. Lindsay, Ron Obermarck: Transaction Management in the R* Distributed Database Management System. ACM Trans. Database Syst. 11(4): 378-396(1986) BibTeX
[65]
C. Mohan, Inderpal Narang: Recovery and Coherency-Control Protocols for Fast Intersystem Page Transfer and Fine-Granularity Locking in a Shared Disks Transaction Environment. VLDB 1991: 193-207 BibTeX
[66]
C. Mohan, Inderpal Narang: Efficient Locking and Caching of Data in the Multisystem Shard Disks Transaction Environment. EDBT 1992: 453-468 BibTeX
[67]
...
[68]
...
[69]
C. Mohan, Hamid Pirahesh: ARIES-RRH: Restricted Repeating of History in the ARIES Transaction Recovery Method. ICDE 1991: 718-727 BibTeX
[70]
...
[71]
...
[72]
J. Eliot B. Moss: Log-Based Recovery for Nested Transactions. VLDB 1987: 427-432 BibTeX
[73]
...
[74]
Edgar Nett, Jörg Kaiser, Reinhold Kröger: Providing Recoverability in a Transaction Oriented Distributed Operating System. ICDCS 1986: 590-597 BibTeX
[75]
...
[76]
...
[77]
Patrick E. O'Neil: The Escrow Transactional Method. ACM Trans. Database Syst. 11(4): 405-430(1986) BibTeX
[78]
Kee S. Ong: Synapse Approach to Database Recovery. PODS 1984: 79-85 BibTeX
[79]
Peter Peinl, Andreas Reuter, Harald Sammer: High Contention in a Stock Trading Database: A Case Study. SIGMOD Conference 1988: 260-268 BibTeX
[80]
R. J. Peterson, Jimmy P. Strickland: LOG Write-Ahead Protocols and IMS/VS Logging. PODS 1983: 216-243 BibTeX
[81]
...
[82]
Andreas Reuter: A Fast Transaction-Oriented Logging Scheme for UNDO Recovery. IEEE Trans. Software Eng. 6(4): 348-356(1980) BibTeX
[83]
Andreas Reuter: Concurrency on High-trafic Data Elements. PODS 1982: 83-92 BibTeX
[84]
Andreas Reuter: Performance Analysis of Recovery Techniques. ACM Trans. Database Syst. 9(4): 526-559(1984) BibTeX
[85]
Kurt Rothermel, C. Mohan: ARIES/NT: A Recovery Method Based on Write-Ahead Logging for Nested Transactions. VLDB 1989: 337-346 BibTeX
[86]
...
[87]
Peter M. Schwarz, Walter Chang, Johann Christoph Freytag, Guy M. Lohman, John McPherson, C. Mohan, Hamid Pirahesh: Extensibility in the Starburst Database System. OODBS 1986: 85-92 BibTeX
[88]
...
[89]
Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988) BibTeX
[90]
...
[91]
Lindsey L. Spratt: The Transaction Resolution Journal: Extending the Before Journal. Operating Systems Review 19(3): 55-62(1985) BibTeX
[92]
Michael Stonebraker: The Design of the POSTGRES Storage System. VLDB 1987: 289-300 BibTeX
[93]
...
[94]
...
[95]
Tandem Database Group - NonStop SQL: A Distributed, High-Performance, High-Availability Implementation of SQL. HPTS 1987: 60-104 BibTeX
[96]
James Z. Teng, Robert A. Gumaer: Managing IBM Database 2 Buffers to Maximize Performance. IBM Systems Journal 23(2): 211-218(1984) BibTeX
[97]
Irving L. Traiger: Virtual Memory Management for Database Systems. Operating Systems Review 16(4): 26-48(1982) BibTeX
[98]
...
[99]
...
[100]
Gerhard Weikum: Principles and Realization Strategies of Multilevel Transaction Management. ACM Trans. Database Syst. 16(1): 132-180(1991) BibTeX
[101]
Matthew J. Weinstein, Thomas W. Page Jr., Brian Livezey, Gerald J. Popek: Transactions and Synchronization in a Distributed Operating System. SOSP 1985: 115-126 BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Fri May 16 16:52:33 2008