In this lab you will implement log-based rollback for aborts and log-based crash recovery. We supply you with the code that defines the log format and appends records to a log file at appropriate times during transactions. You will implement rollback and recovery using the contents of the log file.
The logging code we provide generates records intended for physical whole-page undo and redo. When a page is first read in, our code remembers the original content of the page as a before-image. When a transaction updates a page, the corresponding log record contains that remembered before-image as well as the content of the page after modification as an after-image. You'll use the before-image to roll back during aborts and to undo loser transactions during recovery, and the after-image to redo winners during recovery.
We are able to get away with doing whole-page physical UNDO (while ARIES must do logical UNDO) because we are doing page level locking and because we have no indices which may have a different structure at UNDO time than when the log was initially written. The reason page-level locking simplifies things is that if a transaction modified a page, it must have had an exclusive lock on it, which means no other transaction was concurrently modifying it, so we can UNDO changes to it by just overwriting the whole page.
Your BufferPool already implements abort by deleting dirty pages, and
pretends to implement atomic commit by forcing dirty pages to disk
only at commit time. Logging allows more flexible buffer management
(STEAL and NO-FORCE), and our test code calls
BufferPool.flushAllPages()
at certain points in order to exercise that flexibility.
You'll need to modify some of your existing source and add a few new files. Here's what to do:
$ tar -cvzf CSE444-lab3-submitted.tar.gz CSE444-lab3
$ mv CSE444-lab3 CSE444-lab5
$ cd CSE444-lab5
$ wget http://www.cs.washington.edu/education/courses/cse444/13sp/labs/lab5/CSE444-lab5-supplement.tar.gz
tar -xvzf CSE444-lab5-supplement.tar.gzThis will not overwrite any existing files, but will just add a new test file to the
test/simpledb/systemtest
directory.
Insert the following lines into BufferPool.flushPage()
before
your call to writePage(p)
, where p
is a reference
to the page being written:
// append an update record to the log, with // a before-image and after-image. TransactionId dirtier = p.isDirty(); if (dirtier != null){ Database.getLogFile().logWrite(dirtier, p.getBeforeImage(), p); Database.getLogFile().force(); }This causes the logging system to write an update to the log. We force the log to ensure the log record is on disk before the page is written to disk.
BufferPool.transactionComplete()
calls flushPage()
for each page that a committed transaction dirtied. For each such
page, add a call to p.setBeforeImage()
after you have flushed
the page:
// use current page contents as the before-image // for the next transaction that modifies this page. p.setBeforeImage();After an update is committed, a page's before-image needs to be updated so that later transactions that abort rollback to this committed version of the page. (Note: We can't just call
setBeforeImage()
in
flushPage()
, since flushPage()
might be called even if a transaction isn't committing. Our test case actually
does that! If you implemented
transactionComplete()
by calling flushPages()
instead, you may need to pass an additional
argument to flushPages()
to tell it whether the flush is being
done for a committing transaction or not. However, we strongly suggest
in this case you simply rewrite
transactionComplete()
to use flushPage()
.)
LogTest
systemtest, and fail the rest:
% ant runsystest -Dtest=LogTest ... [junit] Running simpledb.systemtest.LogTest [junit] Testsuite: simpledb.systemtest.LogTest [junit] Tests run: 10, Failures: 0, Errors: 7, Time elapsed: 0.42 sec [junit] Tests run: 10, Failures: 0, Errors: 7, Time elapsed: 0.42 sec [junit] [junit] Testcase: PatchTest took 0.057 sec [junit] Testcase: TestFlushAll took 0.022 sec [junit] Testcase: TestCommitCrash took 0.018 sec [junit] Testcase: TestAbort took 0.03 sec [junit] Caused an ERROR [junit] LogTest: tuple present but shouldn't be ...
You may also wish to consult the JavaDoc for SimpleDB.
LogFile.java
for a description of
the log file format.
You should see in LogFile.java
a set of functions, such as
logCommit()
, that generate each kind of log record and append
it to the log.
Your first job is to implement the rollback()
function in
LogFile.java
. This function is called when a transaction aborts,
before the transaction releases its locks. Its job is to un-do any
changes the transaction may have made to the database.
Your rollback()
should read the log file,
find all update records
associated with the aborting transaction, extract the before-image
from each, and write the before-image to the table file. Use
raf.seek()
to move around in the log file, and
raf.readInt()
etc. to
examine it. Use readPageData()
to read each of the before- and
after-images. You can use the map tidToFirstLogRecord
(which maps
from a transaction id to an offset in the heap file) to determine
where to start reading the log file for a particular transaction.
You will need to make sure that you discard any page from the buffer
pool whose before-image you write back to the table file.
As you develop your code, you may find the Logfile.print()
method useful for displaying the current contents of the log.
Implement LogFile.rollback().
After completing this exercise, you should be able to pass the TestAbort and TestAbortCommitInterleaved sub-tests of the LogTest system test.
LogFile.recover()
will be
called before any new transactions start. Your implementation should:
LogFile.logCheckpoint()
flushes all dirty buffers to disk.
Implement LogFile.recover().
After completing this exercise, you should be able to pass all of the LogTest system test.
To submit your code, please create a CSE444-lab5.tar.gz tarball (such that, untarred, it creates a CSE444-lab5 directory with your source code at CSE444-lab5/src/java/simpledb). Include your individual writeup in the tarball that you submit:
$ cp lab5_writeup.pdf CSE444-lab5 $ tar -cvzf CSE444-lab5.tar.gz CSE444-lab5
Please do not use the ant handin target to create your submission archive.
Submit your tarball for the Lab 5 assigment to the dropbox.. You may submit your code multiple times; we will use the latest version you submit that arrives before the deadline (before 11:59pm on the due date). Please submit your writeup as a PDF, plain text file, or word document (.doc or .docx).
SimpleDB is a relatively complex piece of code. It is very possible you are going to find bugs, inconsistencies, and bad, outdated, or incorrect documentation, etc.
We ask you, therefore, to do this lab with an adventurous mindset. Don't get mad if something is not clear, or even wrong; rather, try to figure it out yourself or send us a friendly email. Please submit (friendly!) bug reports to the course staff. When you do, please try to include:
src/simpledb/test
directory, compile, and run.
PageEncoder
.
50% of your grade will be based on whether or not your code passes the system test suite we will run over it. These tests will be a superset of the tests we have provided; the tests we provide are to help guide your implementation, but they do not define correctness. Before handing in your code, you should make sure produces no errors (passes all of the tests) from both ant test and ant systemtest.
Important: Before testing, we will replace your build.xml, HeapFileEncoder.java, and the entire contents of the test/ directory with our version of these files. This means you cannot change the format of the .dat files! You should also be careful when changing APIs and make sure that any changes you make are backwards compatible. In other words, we will untar your tarball, replace the files mentioned above, compile it, and then grade it. It will look roughly like this:
$ gunzip CSE444-lab5.tar.gz $ tar xvf CSE444-lab5.tar $ cd CSE444-lab5 [replace build.xml, HeapFileEncoder.java and test] $ ant test $ ant systemtest [additional tests]If any of these commands fail, we'll be unhappy, and, therefore, so will your grade.
An additional 50% of your grade will be based on the quality of your writeup and our subjective evaluation of your code.
We've had a lot of fun designing this assignment, and we hope you enjoy hacking on it!