1/4/05
| CSEP 545 Transaction Processing for E-Commerce, Winter 2005 University of Washington |
1/4/05
|
|
|
Reading - Chapter 1 of the textbook.
Project - Pick a partner and let us know. If you don’t know Java or C#, start learning one of them now.
This problem is about how the ACID properties are affected by the internal structure and behavior of data management software.
It also raises some design considerations that may affect your project.
B1 is a transactional block-oriented storage system. A user of B1 identifies each block by its physical address on disk.
B1 offers the following five operations. Underlined parameters are output.
· /* Start new transaction */
int start()
Returns: -1, if there is an active transaction
tId < -1 (a new Transaction Identifier) otherwise
· /* If possible, read block at blockAddr on behalf of transaction tId
from disk into main memory and save a pointer to it in block */
int read(int blockAddr, int tId, int *block)
Returns: 0 if successful, -1 otherwise
· /* tell B1 that transaction tId has updated a block at blockAddr */
int write(int blockAddr, int tId)
Returns: 0 if there is no cached entry for blockAddr
1 otherwise
· /* Try to commit transaction tId */
int commit(int tId)
Returns: 0 if successful, -1 otherwise
· /* Abort transaction tId */
int abort(int tId)
Returns: 0
B1 is implemented as follows:
· B1 maintains a cache of blocks in main memory. It organizes this as a collection, called Cache, of cache entries.
Each cache entry e is an object Cache(e) with three attributes:
o int Cache(e).tId, which contains a transaction ID
o int Cache(e).blockAddr, which contains the identity (i.e. disk address) of the block stored in Cache(e)
o int Cache(e).oldBlock, which contains the last committed content of the block
o int Cache(e).newBlock, which contains the last written content of the block
The cache is initially empty. This means that the cache has been allocated, and for all entries e in the cache, Cache(e).tId = 0.
· B1 maintains a variable lastTrans, which is the (sometimes negated) transaction identifier of the last transaction that was started. It is initialized to 1.
· There can be at most one instance of B1 running on a system at a given time. It has exclusive access to the disk drive that it uses.
B1 is used with a Model Uno disk drive, which supports the operations diskRead and diskWrite
·
/* Read the value of block at blockAddr from disk and return it in main
memory at address memAddr */
int diskRead(int blockAddr, int memAddr)
· /* store the content of the main memory beginning at address memAddr
into block blockAddr on disk */
int diskWrite(int blockAddr, int memAddr)
Returns:
For each operation, the disk drive either performs the intended operation and returns 0 or it has no effect and returns -1
B1 implements its five operations as follows. It executes operations one-at-a-time. That is, it executes each invoked operation in its entirety before executing the next invoked operation.
lastTrans = 1;
...
int start()
{
if (lastTrans < 0) return -1
else
{
lastTrans = -(++lastTans);
return lastTrans;
}
}
int read(int blockAddr, int tId, int *block)
{
/* find the cache element e containing the block whose disk address is blockAddr */
if (there is such a cache element e)
{
/* the disk block at blockAddr is in cache */
Cache(e).tId = tId;
block = &Cache(e).newBlock;
/* &Cache(e).newBlock is the address of Cache(e).newBlock */
return 0;
}
else
{
/* pick a cache entry e, where Cache(e).tId = 0.
If there is no such entry, then return -1 */
diskRead(blockAddr, &Cache(e).oldBlock);
Cache(e).newBlock = Cache(e).oldBlock;
block = &Cache(e).newBlock;
Cache(e).tId = tId;
return 0;
}
}
/* A transaction should call write(&Cache(e).newBlock, tId) after it updates Cache(e).newBlock. */
int write(int blockAddr, int tId)
{
/* find the cache entry e for block blockAddr */
if (there is no such entry) return 0
else
{
Cache(e).tId = tId;
return 1;
}
}
int commit(int tId)
{
for (each cache entry e where Cache(e).tId == tId)
{
status = diskWrite(Cache(e).blockAddr, &Cache(e).newBlock)
Cache(e).tId = - tId.
if (status == -1)
{
Abort(tId);
return -1;
}
}
for (all cache entries e, set Cache(e).tId = 0);
lastTrans = -lastTrans;
return 0;
}
int abort(int tId)
{
for (all cache entries e, where Cache(e).tId == -tId)
{
repeat
{
status = diskWrite(Cache(e).blockAddr, &Cache(e).oldBlock)
}until (status == 0)
/* Of course, this will not terminate if diskWrite keeps failing, but ignore that issue */
}
for (all cache entries e)
{
Cache(e).tId = 0
}
lastTrans = -lastTrans;
return 0;
}
Questions
For each of the scenarios below, analyze whether transactions that use B1 satisfy the four ACID properties.
In each case, if a property is violated, show a counterexample where it does not satisfy the property.
In the latter case, you might want to suggest a way to fix the implementation, but don’t lose sleep over it, since some cases are pretty hard.
a. The operating system and B1 never crash. Transactions run serially.
b. The operating system can crash, in which case main memory is lost. Transactions run serially.
c. The operating system and B1 never crash. Transactions run serially. But if DiskWrite(b, addr) returns 0 then it might have corrupted block b on disk.
variation of (c): If DiskWrite(b, addr) returns -1 then it might have corrupted block b on disk.
d.
The operating system and B1 never crash. Two transactions are allowed to
run concurrently.