Extended Ehemeral Logging: Log Storage Management for Applications with Long Lived Transactions.

@article{DBLP:journals/tods/Keen97,
  author    = {John S. Keen and
               William J. Dally},
  title     = {Extended Ehemeral Logging: Log Storage Management for Applications
               with Long Lived Transactions},
  journal   = {ACM Trans. Database Syst.},
  volume    = {22},
  number    = {1},
  year      = {1997},
  pages     = {1-42},
  ee        = {http://doi.acm.org/10.1145/244810.244811, db/journals/tods/Keen97.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Extended ephemeral logging (XEL) is a new technique for managing a log of database activity subject to the general assumption that the lifetimes of an application's transactions may be statistically distributed over a wide range. The log resides on nonvolatile disk storage and provides fault tolerance to system failures (in which the contents of volatile main memory storage may be lost).

XEL segments a log into a chain of fixed-size FIFO queues and performs generational garbage collection on records in the log. Log records that are no longer necessary for recovery purposes are "thrown away" when they reach the head of a queue; only records that are still needed for recovery are forwarded from the head of one queue to the tail of the next. XEL does not require checkpoints, permits fast recovery after a crash and is well suited for applications that have a wide distribution of transaction lifetimes. Quantitative evaluation of XEL via simulation indicates that it can significantly reduce the disk space required for the log, at the expense of slightly higher bandwidth for log information and more main memory; the reduced size of the log permits much faster recovery after a crash as well as cost savings. XEL can significantly reduce both the disk space and the disk bandwidth required for log information in a system that has been augmented with a nonvolatile region of main memory.

Copyright © 1997 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.

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An4-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition: ACM Digital Library

References

[Agrawal and DeWitt 1985]

Rakesh Agrawal, David J. DeWitt: Recovery Architectures for Multiprocessor Database Machines. SIGMOD Conference 1985: 131-145 BibTeX

[Aho et al. 1983]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: Data Structures and Algorithms. Addison-Wesley 1983, ISBN 0-201-00023-7
BibTeX

[Bernstein et al. 1987]

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX

[Boral 1986]

...

[Cormen et al. 1990]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0
BibTeX

[DeWitt et al. 1984]

David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX

[Eswaran et al. 1976]

Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX

[Gray 1977]

...

[Gray 1991]

...

[Gray et al. 1985]

...

[Gray et al. 1990]

Jim Gray, Bob Horst, Mark Walker: Parity Striping of Disk Arrays: Low-Cost Reliable Storage with Acceptable Throughput. VLDB 1990: 148-161 BibTeX

[Gray et al. 1981]

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

[Gray and Reuter 1993]

Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX

[Härder and Reuter 1983]

Theo Härder, Andreas Reuter: Principles of Transaction-Oriented Database Recovery. ACM Comput. Surv. 15(4): 287-317(1983) BibTeX

[Hagmann 1986]

Robert B. Hagmann: Crash Recovery Scheme for a Memory-Resident Database System. IEEE Trans. Computers 35(9): 839-843(1986) BibTeX

[Hagmann and Garcia-Molina 1991]

...

[Kaunitz and van Eckert 1984]

John Kaunitz, Louis van Ekert: Audit Trail Compaction for Database Recovery. Commun. ACM 27(7): 678-683(1984) BibTeX

[Keen 1994]

...

[Keen and Dally 1993]

John S. Keen, William J. Dally: Performance Evaluation of Ephemeral Logging. SIGMOD Conference 1993: 187-196 BibTeX

[Kohler 1981]

Walter H. Kohler: A Survey of Techniques for Synchronization and Recovery in Decentralized Computer Systems. ACM Comput. Surv. 13(2): 149-183(1981) BibTeX

[Lehman and Carey 1987]

Tobin J. Lehman, Michael J. Carey: A Recovery Algorithm for A High-Performance Memory-Resident Database System. SIGMOD Conference 1987: 104-117 BibTeX

[Lieberman and Hewitt 1983]

Henry Lieberman, Carl Hewitt: A Real-Time Garbage Collector Based on the Lifetimes of Objects. Commun. ACM 26(6): 419-429(1983) BibTeX

[Mohan et al. 1992]

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) BibTeX

[North and Reppy 1987]

...

[Patterson et al. 1989]

...

[Patterson et al. 1988]

David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD Conference 1988: 109-116 BibTeX

[Rosenblum and Ousterhout 1990]

...

[Rosenblum and Ousterhout 1991]

Mendel Rosenblum, John K. Ousterhout: The Design and Implementation of a Log-Structured File System. SOSP 1991: 1-15 BibTeX

[Rosenblum and Ousterhout 1992]

Mendel Rosenblum, John K. Ousterhout: The Design and Implementation of a Log-Structured File System. ACM Trans. Comput. Syst. 10(1): 26-52(1992) BibTeX

[Sharma and Soffa 1991]

Ravi Sharma, Mary Lou Soffa: Parallel Generational Garbage Collection. OOPSLA 1991: 16-32 BibTeX

[Ungar 1984]

David Ungar: Generation Scavenging: A Non-Disruptive High Performance Storage Reclamation Algorithm. Software Development Environments (SDE) 1984: 157-167 BibTeX

[Zorn 1990]

...