The purpose of this assignment is to gain some familiarity with the research literature in Computer Science, in the Database
Management area.
There are three ``classic'' papers from the database literature and five recent research papers on reserve in the Taylor library.
You are to pick one of these papers and write a 3 to 5 page review. This review should consist of a summary of the ideas
reported in the paper, and some opinion of your own concerning the paper. These personal comments can include whether or
not you would recommend this to your colleagues to read, or whether or not you think the ideas or results are important. If it is
a classic paper, comment on its importance and readability. If it is a recent paper, comment on whether or not you think the
system or ideas reported on will ever become commercially available or part of a commercially available system, etc.
The 3 to 5 pages should be in 11 or 12 point type, have reasonable margins and not more than double spacing. Roughly 10
percent of the marks will be for spelling and grammar. If you need to read additional material in order to clarify a point or figure
out the basis of some of the comments in the paper, then do so and include proper references to these additional readings, as
well as to the paper you are reviewing, in a References section at the end.
No group work is allowed on this assignment - your review should be the result of individual effort.
Worth 15%
All TA comments written in red and surrounded by brackets.
Due Date: November 29, 2000.
This document passed MS Word 97's grammer check.
Counts
Pages:
4
Words:
1368
Characters:
6919
Paragraphs:
21
Sentences:
63
Averages
Sentences per Paragraph:
3.7
Words per Sentence:
21.6
Characters per word:
4.9
Readability
Passive Sentences:
31%
Flesch Reading Ease:
38.6
Flesch-Kincaid Grade Level:
12.0
92/100
Review of High Speed On-line Backup when using Logical Log Operations
Summary
(Should have a space here.)
In order for a stable database to be crash recoverable, it must be accessible and correct. The last resort for dealing with erroneous applications that have corrupted the database is a system called media recovery. To guard against failures, the media recovery system has a backup copy of the database and a media recovery log that can be used to update the backup by rolling is state forward to the desired state, usually the one that was most recently committed. To recover from failures, the media recovery system restores the database by copying the backup and then applying the media recovery log to "roll" it forward to the state of the last committed transaction.
On-line backups, which are needed by databases with a high availability requirement, are concurrent with normal database activity
, while off-line backups are not.
There are two kinds of page-oriented log operations used by traditional database systems: Physical and physiological. Updated objects (sometimes referred to as "dirty" objects) in the cache can be flushed (copied) to the database in any order as long as the write ahead log protocol is used. Pages are the recoverable objects in databases and records are usually what are being updated. Since both are small, simple cache management can be used to control the form of the log operation.
The primary advantage of logical (should briefly mention "such as Application Recovery, File System ...") log operations is that they reduce the normal execution cost of providing recover by reducing the amount of data that is written to the log. It produces such a saving by storing the identifiers, rather than the actual data values of operands in a way that's analogous to pointers to large data structures. Storing an identifier that's unlikely to be larger than 16 bytes is vastly more efficient than storing an operand value that can be several megabytes. An operation is considered logical if it can read one or more objects (pages) and write multiple objects.
The main disadvantage is that cache management is more complicated since cached objects can have flush order dependencies. That is, there is an operation update(X) that must be flushed to the database before an operation copy(X,Y) occurs otherwise the variable Y may get an old, not updated X and the backup will be inconsistent with the database.
The problem with implementing a High Speed On-line backup is that the objects updated by logical operations have the same ordering constraints when copied to the backup database to ensure correct media recovery. That is, the copy dependencies must be enforced for both the main and backup databases.
Lomet's proposed solution: to copy data at high speed from the main database to the backup using logical operations, while update activity continues. This method ensures that the results of the logical operations are copied to the backup in the correct order and does not require "tight coupling" with the cache manager.
(Should break up w/ more headings in the "summary" section")
In order for Lomet's solution to work, there needs to be a redo recovery framework. The installation graph describes the order in which operations must be placed in the database in order for recovery to be possible. (no extra space) An installed operation is one that doesn't need to be replayed because its effects do not need to be repeated (for example, an operation that permanently deleted an object). An operation that has not been installed must be replayed in order for recovery to succeed. A write graph takes the installation order of the operations and translates them into the proper flush order on updated objects. A redo test is used during the recovery phase to determine which operations must be replayed.
After a crash, the set of installed operations that can explain s must be identified. Such a set is called explainable if every object of the set is either in an exposed or unexposed state. An exposed object is one that has a value needed for recovery and it equals the value that was written by the last operation. An unexposed object is one that will be overwritten during recovery, before the uninstall operation, so recovery does not depend on its value. A database is said to be recoverable after a crash if it is explainable and the log contains all uninstalled operations. Therefore the cache manager has to make sure that there is always a set of installed operations identified that explains the database state. (Should mention the various "graphs" created.)
Because the backup database is loosely synchronized with the cache management, we cannot be certain that the write graph is the same as the flush ordering of objects to the database. The solution is to monitor the backup process by defining an order that dictates when objects in the database are copied to the backup. But this alone is not sufficient. There must also be a way to control the flow of flushing out of the cache, so as not to overwhelm the backup process. Lomet favours injecting cache manager identity writes into the log so that object values are present on the log when they are need if they happen to not end up in the backup. This has a lower cost and has less impact on system operations than atomic flushing operations. Thus, when flushing objects to the backup, only the changed portion of the database will need to be copied.
Incremental backup is an efficient way to perform backup operations. This method has two aspects to it. First, identify the set of objects in the database that have been updated since the last backup. Second, copy only those identified objects to the backup. Since the High Speed On-line Backup when using Logical Log Operations meets these two aspects, it too is an efficient system.
Review
In many ways, this paper expected a moderately strong technical background of the reader in order for it to be understood. For example, Lomet describes his Installation Graph as something that "resembles the conflict graph of serializability theory, but is weaker," presuming the reader to know what serializability theory is.
Lomet also refers to other articles sometimes when describing or justifying (GOOD POINT) his own ideas in the paper without really describing what the article he referenced means. For example, in section 1.2 Lomet writes, "Backup is mentioned in [2, 3, 1, 4, 12, 13]." In section 5.3 he writes, "Hence, much of the efficiency of [13] also holds for backup with logical operations." As one who is unfamiliar with most of these articles, it would have been nice to receive an extra two or three sentences describing the conclusions of those articles.
Lomet provided some calculations describing the cost of logging, using his logical operation method, for both general and tree style databases. Unfortunately he didn't include information on the how typical on-line systems perform so it wasn't possible to compare the performance differences or note any improvement.
In general Lomet does a good job in providing an overview of how modern databases handle recovery in his introduction. I found that part of the article to be the most useful and interesting and I would heartily recommend that section to any of my colleagues who would like to learn more about database recovery techniques, in general. Lomet's suggestion for high-speed on-line backup is quite simple, actually. By using (fast) logical operations combined with incremental backup techniques, he describes a fast and efficient way of updating the database while circumventing the problems of the fuzzy boundaries in the Physiological approach.
The main limitation for implementing this type of system would be in the hardware. It's unlikely that today's server and network interfaces can meet the speed and reliability requirements that are necessary in order for the object information to sent across an network in tact and in time. Another consideration is building a cache that can deal with multiple megabyte records from numerous simultaneous users.
Given that there are many organizations that need systems that operate (GOOD PT) 24 hours a day, seven days a week with 100% recoverability (e.g. e-commerce web sites, airline reservation systems), it is likely that there will be a substantial commercial demand for database systems with this capability. Once the hardware barriers are overcome, I believe that this system, or something very close to it, will likely be implemented in many of commercial systems.
References
Lomet, David. High Speed On-line Backup using Logical Log Operations. Proc. of 2000 ACM Sigmod International Conference on Management of Data. May, 2000, 34-45.