CS297 Proposal
Schemes to make Aries and XML work in harmony
Thien An Nguyen (thien_an9@yahoo.com)
Advisor: Dr. Chris Pollett
Description:
ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) -
family of locking, logging and recovery algorithms for persistent data management.
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 case of repeated failures during restart or of nested rollbacks. [Mohan90]
ARIES is designed around the redo history paradigm, that is, during the redo phase,
database sub-system redo all updates even with loser transactions.
NATIX, a
native XML database management system has been recently developed (from scratch),
introduce the novice of subsidiary logging and annihilator undo. Suppose a record
is updated multiple times by the same transaction i.e. when a sub-tree is added node by
node multiple times. In such case, the log size would be reduced if we log only the composite
update operation as one operation. It is called subsidiary logging. Undo operations that imply
undo of other operations following them in the log is called annihilators. To improve the
performance in XML context, annihilator undo skips undo operations implied by the annihilators.
For example, update operation(s) to a record that has been created by the same transaction doesn't
need to be undone when the transaction is aborted because the record will be deleted anyway.[Kan03]
Natix, on the other hand, supports selective redo and selective undo to accelerate restart recovery.
The goal that I want to accomplish in this CS297 is to study the structure of an open source,
object database that implements ARIES, and experiments with the log records to simulate transaction
rollback/abort and transaction restart recovery. We chose PREDATOR because PREDATOR is an
object-relational database system that was built on top of the SHORE (Scalable Heterogeneous
Object REpository) storage manager under development at the University of Wisconsin
(also publicly available software) - a persistent object storage engine that supports creation
of persistent files and records. Records can range from a few bytes to megabytes or larger.
Records can be retrieved by object identifier or by scanning files. Shore supports log-based
recovery based on ARIES mechanism [Venkatarman96]. My intention in CS298 is to implement
subsidiary logging, annihilator undo, and selective redo/undo on top of Predator.
Schedule:
Week 1 & 2:
Jan. 29 - Feb 12 | 1. Read "The Core Technologies for Native XML Database Management System" [Kan03] 2. Read "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging" [Mohan90] 3. Read Shore Storage Manager architecture |
Week 3:
Feb. 19 | Deliverable 1: Install Shore SM |
Week 4 & 5:
Mar. 4 | 1. Read PREDATOR System Design Document: A detailed
description of internal design decisions and implementation details
2. Read PREDATOR User Manual and Tutorial: A tutorial of the user of the
system, along with interactive examples. 3. Read PREDATOR, Design and
Implementation [Seshadri97].
|
Week 6:
Mar. 11 | Deliverable 2: Install PREDATOR v2.1 for Windows
(on top of Shore SM ) |
Week 7 & 8: Mar. 25 |
Study Predator's recovery code. Class hierachy
Read "ARIES/KVL: A Key-Value Locking Method for
Concurrency Control of Multiaction Transactions
Operating on B-Tree Indexes" [Mohan92] |
Week 9: Apr 1 | Spring Break |
Week 10:
Apr. 15 | Read "Recovery Protocols for Shared
Memory Database Systems" [Molesky95] Deliverable 3: Writing
Testcases/jobs that go through transaction abort/restart recovery |
Week 11: Apr. 22 |
Deliverable 4: Result for transaction rollback/abort |
Week 12 & 13:
May 6 | Deliverable 5: Result for Restart Recovery |
Week 14 & 15:
May 20 | Deliverable 6: Final Report |
Deliverables:
The full project will be done when CS298 is completed. The following will
be done by the end of CS297:
1. Install SHORE storage manager up running on windows 2000
2. Install PREDATOR on top of Shore
3. 2 testcases/jobs that go through rollback/abort, and restart recovery code path (maybe combines with breakpoint in the source code)
4. Results of transaction rollback/abort after added log records.
5. Results of restart recovery after added log records. 6. Final report
References:
[Kan03] Core Technologies for Native XML Database Management System. Carl-Christian Kanne. Mannheim. 2003. [Mohan90] ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, P. Schwarz. ACM Transactions on Database Systems, 1990. [Seshadri97] PREDATOR: An OR-DBMS with Enhanced Data Types. P. Seshadri, M. Paskin. SIGMOD, 1997, p. 568-571. [Venkatarman96] Global Memory Management for Multi-server Database Systems. S. Venkatarman. University of Wisconsin - Madison, 1996. [Mohan92] ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. C. Mohan. In Proc. of the 12th International Conference on Distributed Computing Systems, Yokohama, 1992. [Mohan99] Repeating History Beyond ARIES. C. Mohan. Proc. 25th International Conference on Very Large Data Bases, Edinburgh, 1999. [Molesky95] Recovery Protocols for Shared Memory Database Systems. L. Molesky, K. ramamritham. ACM, 1995. [Lahiri01] Fast-Start: Quick Fault Recovery in Oracle. T. Lahiri, A. Ganesh, R. Weiss, A. Joshi. ACM SIGMOD, 2001. [Mohan93] ARIES/LHS: A Concurrency Control and Recovery Method Using Write-Ahead Logging for Linear Hashing with Separators. C. Mohan. Proceedings of the 9th IEEE International Conference on Data Engineering, 1993. Shore SM source code available at: ftp://ftp.cs.wisc.edu/shore/current/ Predator source code available at http://www.distlab.dk/predator/download.htm |