CS4321 Project 5: Transaction Processing System
November 21, 2012
This project is due on November 29th, at 23:59pm via CMS. It is worth a total of 100 points. It counts for 25% of your grade. Read the whole assignment carefully, and review the relevant textbook materials, before you start implementing. The relevant material for this assignment can be found in Chapter 16 and
17 of the course textbook.
The Big Picture
Figure 1: A Simple Transaction Processing System
1
Overview
In this assignment, you will implement a transaction processing system. The aim of the project is not to design a completely generic transaction processing engine but rather to give you a taste of the design decisions and challenges involved in doing so. You will be implementing transactions which can read, write and update values in a key-value store. As shown in gure , transactions access the key-value data stored in a "data page" through a linear hash index. The hash index in turn uses the buer manager to fetch the appropriate pages from the disk.
We will provide you with a implementation of a linear hash index in the form of a library. Note that as long as the interface for the index is the same, the linear hash index may as well be replaced by a B+-tree index like the one which you implemented in the previous assignment. However, the B+-tree assignment you implemented does not support concurrent modication and hence cannot be used here directly. The linear hash index which is provided to you supports concurrent modications as is discussed later.
The transaction processing system you will implement will have the following properties :
1. Transactions are never rolled back (undo is never necessary).
2. Transactions have 2 phases: A read phase followed by an atomic write phase.
3. We use shared locks for all reads, and exclusive locks for all writes.
4. We use strict 2 PL as a concurrency control protocol i.e. both shared and exclusive locks once acquired are not released till the transaction ends.
5. Transactions can be aborted due to deadlock.
6. A deadlock detector is executed periodically to analyze wait-for graph and resolve deadlock by aborting necessary transactions.
Implemented Modules
The following modules are already implemented for you. We discuss the interface for each of the modules here. The header les corresponding to them are provided to you.
Linear Hash Index
The hash index which you were taught in CS4320/CS5320 is not thread-safe i.e. there is no way to prevent concurrently running transactions (processes) to make changes to the index. This may result in race condi- tions rendering the index corrupt. In order to prevent this we need to use locking and latching to make all operations over the hash index thread safe. A transaction (process) that needs to make changes to the index structure, i.e. change the directory because of splits or deletes, needs to have exclusive access to the index.
On the other hand a transaction which needs to add/remove data stored in the pages without inducing a split or compression of the index does not need exclusive access to the index as long as it has exclusive access to the bucket it is making changes to. This allows for multiple transactions to access the index and insert/delete data as long as they are not making changes to the index structure.
We have already implemented a thread safe version of a hash index as described above. The interface for the thread safe hash index is as follows :
Thread Safe Hash Index Interface
This interface has been implemented for you.
 ThreadSafeHashIndex(TransactionID tid, HashIndex *HI) Constructor used to set the owner of the current thread safe hash index. The hash index is shared by multiple transactions.
2
 Status InsertKeyValue(KeyType key, DataType value) Provides a wrapper around the InsertKeyValue of the HashIndex to make it threadsafe using the lock manager and latch manager to acquire and release appropriate locks and latches.
 Status DeleteKey(KeyType key) Provides a wrapper around the DeleteKey of the HashIndex to make it threadsafe using the lock manager and latch manager to acquire and release appropriate locks and latches.  Status GetValue(KeyType key, DataType &value) Provides a wrapper around the GetValue of the
HashIndex to make it threadsafe using the lock manager and latch manager to acquire and release appropriate locks and latches.
 Status UpdateValue(KeyType key, DataType newValue) Provides an additional functionality to the higher layers. Implemented in a threadsafe manner using the InsertKeyValue and DeleteKey function- ality of HashIndex.
Latch Manager
While you will not need to deal with the latch manager in this project, it is recommended that you browse through the implementation of a latch manager provided to you as latch.cpp.
Latches are a mechanism of ensuring exclusive access to physical resources by multiple processes. These are held for short duration. Latches are unset immediately after the physical read or write operation is completed. A latch manager keeps track of the latches in the system. We will support a bucket level latching for this project i.e. only 1 processes can access a bucket at any point of time. Since in our case, the objects being locked are keys and they do not correspond to disk pages, it is necessary to have latches to prevent con ict between read/write operations. Unlike locks, latches have no types (i.e no read latches / write latches). Interface
We only discuss 2 of the functions which are part of the latch manager interface. However, it is highly recommended to actually go through the latch.h and latch.cpp to understand how it is implemented in reality.  static void AcquireLatch(int pid, int oid) The caller thread (with identier pid) is either granted a latch on object identied by oid or is put to sleep till it can get the latch. If it is granted the latch, the corresponding information is entered and maintained in a latchTable.
 static void ReleaseLatch(int pid, int oid) The latchTable is updated to re ect the fact that the trans- action pid is releasing the latch and grants the latch to anyone else waiting for a latch on object oid. Lock Manager
The lock manager is modeled as a static class. The lock manager maintains a lock table. Access to this table by multiple transactions is always mutually exclusive.
 static void AcquireSharedLock(int pid, int oid)
This function checks the Lock Table. If the oid is not currently locked by any transaction, then this transaction gets the shared lock. If the oid is currently locked by some set of transactions in shared mode, and there are no exclusiveLockRequests for this object in the object lock queue, then this transaction gets the shared lock. If the oid is currently locked in exclusive mode by some transaction, then this request gets enqueued and the transaction is blocked till the lock is granted.
 static void ReleaseSharedLock(int pid, int oid)
This function removes pid from the list of transactions currently holding locks on oid.
3
 static void AcquireExclusiveLock(int pid, int oid)
If the oid is not currently locked by any transaction, then this transaction gets the shared lock. If the oid is currently locked by some set of transactions in shared mode, then this transactions request gets enqueued and the transaction is blocked. If the oid is currently locked in exclusive mode by some transaction, then this request gets enqueued and the transaction is blocked till the lock is granted.
 static void ReleaseExclusiveLock(int pid, int oid)
This function removes pid from the list of transactions currently holding locks on oid.
The following four functions relating to index locking are self explanatory. They are used by the Thread-
SafeHashIndex implementation and you do not need to use them.
 static void AcquireSharedIndexLock(int pid)
 static void ReleaseSharedIndexLock(int pid)
 static void AcquireExclusiveIndexLock(int pid)
 static void ReleaseExclusiveIndexLock(int pid)
To Be Implemented
Transactions
The following code snippet is what a transaction in our system looks like: public ref class myTrans : TranscationExecution
{
public: void run()
{
int i, j;
T->StartTranscation();
T->Read(2, i);
T->Read(3, j); i = i - 100; j = j + 100;
T->AddWritePair(2,i, UPDATE)
T->AddWritePair(3,j, UPDATE)
T->GroupWrite();
T->CommitTranscation();
T->EndTransaction();
}
};
You may assume that such a transaction transfers an amount of 100$ from account number 2 to ac- count number 3. In the real world such transaction codes are automatically generated from the frontend web interface of many dierent systems including banking, ight reservation etc. Of course they are more complicated, but this simple transaction should give you a feel of how things actually work in the real world.
Each such transaction runs as a separate thread in the system. On each read the transaction uses the thread safe hash index to get the value for the key from the disk. The hash index in turn may use the buer manager to fetch the page which contains the data into memory before allowing the hash index to fetch the value. Each transaction has a read phase during which the transaction performs all the reads, followed by an atomic write phase in which the transaction writes data to disk. Note that once the transaction has performed a groupWrite, it cannot perform any reads. Atomicity of the group write phase is ensured by
4
acquiring write locks on all the data items to be written before actually writing them. After the read and the groupwrite phase, the transaction commits. After commit, the endTransaction function is called which releases all the locks acquired by the transaction.
Interface The following interface needs to be implemented by you.
 Status StartTransaction()
{ Change the transaction status to RUNNING.
 Status Read(int key, int &value)
{ Acquire shared lock before reading data.
{ If AcquireSharedLock() returns false, which means the transaction failed in getting this lock, call
AbortTransaction() and return FAIL.
 Status AddWritePair(int key, int value, OpType fINSERT, DELETE, UPDATEg)
{ Add the key-value pair to write list.
 Status GroupWrite()
{ Acquire exclusive lock(s) before writing data.
{ If AcquireExclusiveLock() returns false, which means the transaction failed in getting this lock, call
AbortTransaction() and return FAIL.
{ Change the transaction status to GROUPWRITE.
 Status CommitTransaction()
{ Change the transaction status to COMMITTED.
 Status EndTransaction()
{ Release all currently held locks (shared and exclusive).
 private: Status AbortTransaction()
{ Change the transaction status to ABORTED.
{ Release all currently held locks (shared and exclusive).
{ The transaction should NOT respond to any later request. If user ignores the fact that the transaction is aborted and continues sending requests, FAIL should be directly returned.
Please do NOT modify the above interface, but feel free to add data structures and private functions to the transaction class if you want to.
Lock Upgrades : It can be done as following:
LockManager::AcquireSharedLock(this->pid, objectID);
...
LockManager::AcquireExclusiveLock(this->pid, objectID);
...
LockManager::ReleaseExclusiveLock(this->pid, objectID);
A AcquireExclusiveLock() request to an object of which the shared lock is already owned by current transaction, will be automatically treated as lock upgrade request by LockManager. The lock manager will try to acquire exclusive lock of the object WITHOUT releasing the shared lock. Therefore, strict 2PL protocol is still enforced.
Note that once a lock gets upgraded, we should use ReleaseExclusiveLock() instead of ReleaseShared-
Lock() when releasing the lock.
5
Deadlock Detector
In the above system, deadlocks may occur. There are two simple deadlock examples in test2() and test3().
A deadlock detector stub is already created and executed periodically.
The deadlock detection and resolving consists of three steps. First, you need to build a wait-for graph by examining the lock tables. Second, you need to analyze the wait-for graph and decide which transactions should be aborted, if there is deadlock(s). Finally, abort the transactions as decided during analysis to eliminate all deadlocks.
Interface
 void run();
{ Add initialization of local data structures here.
 void BuildWaitForGraph();
{ Examine the lock table (will be described in details later).
{ Construct wait-for graph.
 void AnalyzeWaitForGraph();
{ Analyze the wait-for graph and decide the abort transactions(if any).
 void AbortTransactions();
{ Already implemented for you. Please do not modify this function.
For simplicity of implementation, we predene the maximal number of current transactions to be maxT, and a boolean array abortT [1::maxT ] should be generated by AnalyzeWaitForGraph(). AbortTransactions() will abort all transactions with TransactionID tid such that abortT [tid] = true.
Lock Table
You need to examine the lock table in BuildWaitForGraph(). In the lock table, we keep a ReadWriteFI-
FOLock for each object that is accessed by the transaction processing system.
For each ReadWriteFIFOLock, lockingList and waitQ are the two data structures where you can extract wait-for graph from.
The ReadWriteFIFOLock() works in the following way:
1) lockingList keeps all transaction/process IDs that currently hold the lock for this object. Only if it is shared lock, there might be multiple elements in lockingList.
2) waitQ keeps track of transactions that request for the lock but are currently blocked, because some transactions in lockingList have not released their locks yet.
3) When a request arrives at LockManager, if the waitQ is not empty OR the lock cannot be obtained immediately, the request is appended to the tail of waitQ, except
4) If such request is a upgrade request, add it to the head of the waitQ (why this is better than append to the tail of waitQ?).
5) After releasing any lock, if lockingList is empty, requests will be dequeued from waitQ from head to tail, to ll in lockingList.
You need to examine both lockingList and waitQ to build the wait-for graph. Since ReadWriteFI-
FOLock class is written in Managed C++, examples of accessing elements in lockingList and waitQ are provided to you.
Think about the following question:
Does the entire waitQ need to be examined to build wait-for graph? If not, is the rst element (if exists) enough? 6
Compilation and Testing
The source code for the project can be downloaded from the course management system. If you unzip this le, you will see the following directories and les.
Top-level Directory:
 This contains the Visual Studio 2010 project and solution les for this assignment
Related les in directories \src" and \include":
 transaction.cpp(.h)
 lock.cpp(.h)
 deadlockDetector.cpp(.h)
 main.cpp
 test.cpp(.h)
Directory \lib" contains the library les you will need in order to generate an executable.
What You Need to Do
Files to complete:
 transaction.cpp
- You need to implement the interface provided to you.
 deadlock detector.cpp
- You need to implement missing functions for the deadlock detector.
Testcases
You can nd 4 testcases in test.cpp. Note that these 4 testcases can only be run separately. You may edit which test to run in main.cpp
 test1()
{ a no-deadlock example.
 test2()
{ a deadlock example (simultaneous upgrade).
 test3()
{ a deadlock example (circular wait).
 test4()
{ mixture of the two deadlock examples above.
Evaluation
You project will be evaluated using the following criteria: 1) Correctness of locking protocol, 2) Correctness of construction of wait-for graph, 3) Abort rate.
Implementation (90 points)
In order to get full points for implementation, the following requirements should be satised:
7
 The locking protocol is implemented correctly.
 The construction of wait-for graph is correct.
 If there is no deadlock, no transaction will be aborted.
 If there is deadlock(s), try your best to abort as few transactions as possible.
Documentation (10 points)
Write an one-page summary, describing
 How you construct the wait-for graph.
 How you analyze the wait-for graph and decide which transaction(s) should be aborted.
What to Turn In
Submission will be via CMS. Submit a single zip le of your Visual Studio 2010 project. You should submit the same set of les given to you at the beginning of this assignment, plus any additional header and source les you have created for this assignment. The code should compile under the Visual Studio solution le you submit. Good luck!
8