In this lab, you will implement a simple locking-based transaction system in SimpleDB. You will need to add lock and unlock calls at the appropriate places in your code, as well as code to track the locks held by each transaction and grant locks to transactions as they are needed.
The remainder of this document describes what is involved in adding transaction support and provides a basic outline of how you might add this support to your database.
As with the previous lab, we recommend that you start as early as possible. Locking and transactions can be quite tricky to debug!
You will need to add these new test cases to your release. The easiest way to do this is to untar the new code in the same directory as your top-level simpledb directory, as follows:
$ tar -cvzf CSE444-lab4-submitted.tar.gz CSE444-lab4
$ mv CSE444-lab4 CSE444-lab3
$ wget http://www.cs.washington.edu/education/courses/cse444/12sp/labs/lab3/CSE444-lab3-supplement.tar.gz
tar -xvzf CSE444-lab3-supplement.tar.gzThis will not overwrite any existing files, but will just add new tests to the
test/simpledb/systemtestdirectories, as well as adding the new file
In the remainder of this section, we briefly overview these concepts and discuss how they relate to SimpleDB.
transactionCompletecommand. Note that these three points mean that you do not need to implement log-based recovery in this lab, since you will never need to undo any work (you never evict dirty pages) and you will never need to redo any work (you force updates on commit and will not crash during commit processing).
BufferPool, for example), that allow a caller to request or release a (shared or exclusive) lock on a specific object on behalf of a specific transaction.
We recommend locking at page granularity, though you should be able to implement locking at tuple granularity if you wish (please do not implement table-level locking). The rest of this document and our unit tests assume page-level locking.
You will need to create data structures that keep track of which locks each transaction holds and that check to see if a lock should be granted to a transaction when it is requested.
You will need to implement shared and exclusive locks; recall that these work as follows:
If a transaction requests a lock that it should not be granted, your code should block, waiting for that lock to become available (i.e., be released by another transaction running in a different thread).
You need to be especially careful to avoid race conditions when writing the code that acquires locks -- think about how you will ensure that correct behavior results if two threads request the same lock at the same time (you way wish to read about Synchronization in Java).
You may find it helpful to define a class that is responsible for maintaining state about transactions and locks, but the design decision is up to you.
You may need to implement the next exercise before your code passes the unit tests in LockingTest.
Fortunately, the SimpleDB design is such that it is possible obtain locks on
BufferPool.getPage() before you read or modify them.
So, rather than adding calls to locking routines in each of your operators,
we recommend acquiring locks in
getPage(). Depending on your
implementation, it is possible that you may not have to acquire a lock
anywhere else. It is up to you to verify this!
You will need to acquire a shared lock on any page (or tuple)
before you read it, and you will need to acquire an exclusive
lock on any page (or tuple) before you write it. You will notice that
we are already passing around
Permissions objects in the
BufferPool; these objects indicate the type of lock that the caller
would like to have on the object being accessed (we have given you the
code for the
Note that your implementation of
HeapFile.deleteTuple(), as well as the implementation
of the iterator returned by
access pages using
BufferPool.getPage(). Double check
that that these different uses of
getPage() pass the
correct permissions object (e.g.,
Permissions.READ_ONLY). You may also wish to double
check that your implementation of
any of the pages they access (you should have done this when you
implemented this code in lab 2, but we did not test for this case.)
After you have acquired locks, you will need to think about when to release them as well. It is clear that you should release all locks associated with a transaction after it has committed or aborted to ensure strict 2PL. However, it is possible for there to be other scenarios in which releasing a lock before a transaction ends might be useful. For instance, you may release a shared lock on a page after scanning it to find empty slots (as described below).
BufferPool.getPage(), this should work correctly as long as your
BufferPool.getPage(), this should work correctly as long as
HeapFile. When do you physically write the page to disk? Are there race conditions with other transactions (on other threads) that might need special attention at the HeapFile level, regardless of page-level locking?
Modifications from a transaction are written to disk only after it commits. This means we can abort a transaction by discarding the dirty pages and rereading them from disk. Thus, we must not evict dirty pages. This policy is called NO STEAL.
You will need to modify the evictPage method in BufferPool. In particular, it must never evict a dirty page. If your eviction policy prefers a dirty page for eviction, you will have to find a way to evict an alternative page. In the case where all pages in the buffer pool are dirty, you should throw a DbException.
Note that, in general, evicting a clean page that is locked by a running transaction is OK when using NO STEAL, as long as your lock manager keeps information about evicted pages around, and as long as none of your operator implementations keep references to Page objects which have been evicted.
TransactionIdobject is created at the beginning of each query. This object is passed to each of the operators involved in the query. When the query is complete, the
Calling this method either commits or aborts the
transaction, specified by the parameter flag
commit. At any point
during its execution, an operator may throw a
TransactionAbortedException exception, which indicates an
internal error or deadlock has occurred. The test cases we have provided
you with create the appropriate
TransactionId objects, pass
them to your operators in the appropriate way, and invoke
transactionComplete when a query is finished. We have also
BufferPool. Note that there are two versions of transactionComplete, one which accepts an additional boolean commit argument, and one which does not. The version without the additional argument should always commit and so can simply be implemented by calling
When you commit, you should flush dirty pages associated to the transaction to disk. When you abort, you should revert any changes made by the transaction by restoring the page to its on-disk state.
Whether the transaction commits or aborts, you should also release any state the
BufferPool keeps regarding
the transaction, including releasing any locks that the transaction held.
At this point, your code should pass the
TransactionTest unit test and the
AbortEvictionTest system test. You may find the
TransactionTest system test
illustrative, but it will likely fail until you complete the next exercise.
There are many possible ways to detect deadlock. For example, you may implement a simple timeout policy that aborts a transaction if it has not completed after a given period of time. Alternately, you may implement cycle-detection in a dependency graph data structure. In this scheme, you would check for cycles in a dependency graph whenever you attempt to grant a new lock, and abort something if a cycle exists.
After you have detected that a deadlock exists, you must decide how to improve the situation. Assume you have detected a deadlock while transaction t is waiting for a lock. If you're feeling homicidal, you might abort all transactions that t is waiting for; this may result in a large amount of work being undone, but you can guarantee that t will make progress. Alternately, you may decide to abort t to give other transactions a chance to make progress. This means that the end-user will have to retry transaction t.
src/java/simpledb/BufferPool.java. Most likely, you will want to check for a deadlock whenever a transaction attempts to acquire a lock and finds another transaction is holding the lock (note that this by itself is not a deadlock, but may be symptomatic of one.) You have many design decisions for your deadlock resolution system, but it is not necessary to do something complicated. Please describe your choices in the lab writeup.
You should ensure that your code aborts transactions properly when a
deadlock occurs, by throwing a
This exception will be caught by the code executing the transaction
TransactionTest.java), which should call
transactionComplete() to cleanup after the transaction.
You are not expected to automatically restart a transaction which
fails due to a deadlock -- you can assume that higher level code
will take care of this.
We have provided some (not-so-unit) tests in
test/simpledb/DeadlockTest.java. They are actually a
bit involved, so they may take more than a few seconds to run (depending
on your policy). If they seem to hang indefinitely, then you probably
have an unresolved deadlock. These tests construct simple deadlock
situations that your code should be able to escape.
Note that there are two timing parameters near the top of
DeadLockTest.java; these determine the frequency at which
the test checks if locks have been acquired and the waiting time before
an aborted transaction is restarted. You may observe different
performance characteristics by tweaking these parameters if you use a
timeout-based detection method. The tests will output
TransactionAbortedExceptions corresponding to resolved
deadlocks to the console.
Your code should now should pass the
TransactionTest system test (which may also
run for quite a long time).
At this point, you should have a recoverable database, in the
sense that if the database system crashes (at a point other than
transactionComplete()) or if the user explicitly aborts a
transaction, the effects of any running transaction will not be visible
after the system restarts (or the transaction aborts.) You may wish to
verify this by running some transactions and explicitly killing the
You have now completed this lab. Good work!
All CSE 444 labs are to be completed INDIVIDUALLY! However, you may discuss your high-level approach to solving each lab with other students in the class.
To submit your code, please create a CSE444-lab3.tar.gz tarball (such that, untarred, it creates a CSE444-lab3/src/java/simpledb directory with your code) and submit it 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). If applicable, please indicate your partner in your writeup. Please also submit your individual writeup as a PDF, plain text file (.txt), 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:
test/simpledbdirectory, compile, and run.
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. Before handing in your code, you should make sure it 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 .dat files! You should therefore be careful changing our APIs. This also means you need to test whether your code compiles with our test programs. 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-lab3.tar.gz $ tar xvf CSE444-lab3.tar $ cd ./CSE444-lab3 [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!