Assignment 9 — Transactions
The goal of this assignment is to gain experience using transactions.
The schema contains an account table. You will
operate on this table, from multiple concurrent transactions,
experiment with different isolation levels, and observe and
explain the different behaviors obtained with each.
What's in the archive
Here is the archive.
Header files
There are two header files:
- db.h: An API for operating on the
database: Connecting and disconnecting, beginning and committing
transactions, submitting queries and updates, and extracting query
results.
- txn.h: An API for operating on
the account table: reading and updating an account's
balance, transferring funds between balances, and doing an audit
(finding the sum of all balances).
db.cpp, txn.cpp
Corresponding to each .h file is a .cpp file. You
will need to write code in db.cpp and txn.cpp
main.cpp
This is the test driver. You don't need to modify it.
Makefile
You can build your code using this Makefile by simply
typing make. Doing so will create an executable
named a9.
q_and_a.txt
This file contains questions regarding transactions and isolation
level. Type your answers in this file.
Running the test driver
If you run a9 without any arguments, you get a usage message:
a9 TXN_TEST HOST DBNAME USER PASSWORD
TXN_TEST:
ac: test transactions without explicit transaction boundaries (i.e., auto-commit)
rc: test transactions with READ COMMITTED transactions
ser: test transactions with SERIALIZABLE transactions
So to do a complete run of the tests, I do the following:
./a9 ac localhost jao jao jao
./a9 rc localhost jao jao jao
./a9 ser localhost jao jao jao
The code you need to write
In db.cpp
You already implemented db.cpp in Assignment 8, just use it
as is, (assuming it was working correctly). The only change you will
need to make is to implement begin_transaction and commit_transaction.
In txn.cpp
You need to fill in the empty functions. Note that I have filled in
the transfer function, which relies
on update_balance. You need to fill
in update_balance. Note that update_balance
MODIFIES the balance by adding an amount to it. It does not ASSIGN
the amount to the balance. (I provided transfer because it
involved a subtlety in the ordering of operations, which we haven't
yet discussed yet.)
Output from the driver
Running the driver should produce output that looks like this:
BEGIN auto-commit ------------------------------------------------------------------------------
process 109528 -- bad balance: 23, failed balance: 0, failed transfer: 0, bad audit: 967, failed audit: 0, failed commit: 0
process 109530 -- bad balance: 23, failed balance: 0, failed transfer: 0, bad audit: 982, failed audit: 0, failed commit: 0
process 109532 -- bad balance: 20, failed balance: 0, failed transfer: 0, bad audit: 968, failed audit: 0, failed commit: 0
process 109534 -- bad balance: 29, failed balance: 0, failed transfer: 0, bad audit: 965, failed audit: 0, failed commit: 0
process 109529 -- bad balance: 25, failed balance: 0, failed transfer: 0, bad audit: 979, failed audit: 0, failed commit: 0
process 109533 -- bad balance: 21, failed balance: 0, failed transfer: 0, bad audit: 973, failed audit: 0, failed commit: 0
process 109536 -- bad balance: 20, failed balance: 0, failed transfer: 0, bad audit: 965, failed audit: 0, failed commit: 0
process 109531 -- bad balance: 25, failed balance: 0, failed transfer: 0, bad audit: 958, failed audit: 0, failed commit: 0
process 109527 -- bad balance: 24, failed balance: 0, failed transfer: 0, bad audit: 952, failed audit: 0, failed commit: 0
process 109535 -- bad balance: 20, failed balance: 0, failed transfer: 0, bad audit: 959, failed audit: 0, failed commit: 0
END auto-commit
BEGIN read committed ------------------------------------------------------------------------------
process 109566 -- bad balance: 20, failed balance: 0, failed transfer: 0, bad audit: 0, failed audit: 0, failed commit: 0
process 109557 -- bad balance: 19, failed balance: 0, failed transfer: 0, bad audit: 0, failed audit: 0, failed commit: 0
process 109564 -- bad balance: 19, failed balance: 0, failed transfer: 0, bad audit: 0, failed audit: 0, failed commit: 0
process 109559 -- bad balance: 20, failed balance: 0, failed transfer: 0, bad audit: 0, failed audit: 0, failed commit: 0
process 109565 -- bad balance: 27, failed balance: 0, failed transfer: 0, bad audit: 0, failed audit: 0, failed commit: 0
process 109558 -- bad balance: 17, failed balance: 0, failed transfer: 0, bad audit: 0, failed audit: 0, failed commit: 0
process 109562 -- bad balance: 14, failed balance: 0, failed transfer: 0, bad audit: 0, failed audit: 0, failed commit: 0
process 109560 -- bad balance: 17, failed balance: 0, failed transfer: 0, bad audit: 0, failed audit: 0, failed commit: 0
process 109561 -- bad balance: 22, failed balance: 0, failed transfer: 0, bad audit: 0, failed audit: 0, failed commit: 0
process 109563 -- bad balance: 10, failed balance: 0, failed transfer: 0, bad audit: 0, failed audit: 0, failed commit: 0
END read committed
BEGIN serializable ------------------------------------------------------------------------------
process 109596 -- bad balance: 0, failed balance: 0, failed transfer: 552, bad audit: 0, failed audit: 0, failed commit: 0
process 109595 -- bad balance: 0, failed balance: 0, failed transfer: 567, bad audit: 0, failed audit: 0, failed commit: 0
process 109590 -- bad balance: 0, failed balance: 0, failed transfer: 555, bad audit: 0, failed audit: 0, failed commit: 0
process 109591 -- bad balance: 0, failed balance: 0, failed transfer: 543, bad audit: 0, failed audit: 0, failed commit: 0
process 109589 -- bad balance: 0, failed balance: 0, failed transfer: 597, bad audit: 0, failed audit: 0, failed commit: 0
process 109586 -- bad balance: 0, failed balance: 0, failed transfer: 577, bad audit: 0, failed audit: 0, failed commit: 0
process 109588 -- bad balance: 0, failed balance: 0, failed transfer: 549, bad audit: 0, failed audit: 0, failed commit: 0
process 109598 -- bad balance: 0, failed balance: 0, failed transfer: 599, bad audit: 0, failed audit: 0, failed commit: 0
process 109597 -- bad balance: 0, failed balance: 0, failed transfer: 578, bad audit: 0, failed audit: 0, failed commit: 0
process 109599 -- bad balance: 0, failed balance: 0, failed transfer: 555, bad audit: 0, failed audit: 0, failed commit: 0
END serializable
Test of transaction API
This runs a test of the transaction API, which is
in txn.h. It reports the number of errors found. The test
starts in test_transactions in main.c.
For a given isolation level, the test does the following steps:
- Start 10 worker processes.
- In each worker, do 1000 transfers.
- A transfer is from one randomly selected account to
another, (there are 10 accounts).
- The amount transferred is a random number between 1 and
100.
- To avoid withdrawing more than the account balance, the
balance of the source account is read first, and if the amount
select exceeds the balance, the transfer amount is set to the
balance.
- Reading the balance, and the transfer (which updates two
account balances) is done in one transaction.
- After each transfer, an audit is done in a separate
transaction. The sum of all balances is computed, and a check is
made to see whether the amount is as expected.
- run_transfers counts the occurrences of various
problems:
- Bad audit: Sum of balances does not match the expected value.
- Failed audit: The computation of the audit resulted in an
error due to a concurrency conflict.
- Failed transfer: The transfer of funds resulted in an
error due to a concurrency conflict.
- Bad balance: A negative balance was detected. This should
not occur since the withdrawal amount is limited to the
account balance.
- Failed balance: Reading the balance of an account
resulted in an
error due to a concurrency conflict.
- Failed commit: A transaction commit resulted in an error
due to a concurrency conflict.
- Once each worker has done 1000 transfers and audits, the
number of each kind of problem is reported.
Here is pseudo-code summary of the steps carried out by each worker process:
do 100 times:
begin transaction
source_id = random account id
target_id = random (but different) account id
read balance of account(source_id)
transfer_amount = min(random number between 1 and 100, balance)
transfer transfer_amount from source_id to target_id
commit transaction
begin transaction
compute sum of balances
compare sum of balances to expected sum
commit transaction
report counts of observed failures
What you have to do
- Fill in the code in db.cpp, (mostly copied from Assignment 6).
- Fill in the code in txn.cpp.
- Run
the ac, rc and ser tests.
- Analyze the output from the the ac, rc
and ser tests, answering the questions below.
Questions about the transaction tests
If your output looks like mine (see above), then the different
isolation levels resulted in very different results. Submit written
(well, typed) answers to these questions, in the file q_and_a.txt.
- In auto-commit mode (no transaction boundaries), there are bad
balances and bad audits, but nothing else goes wrong. Explain this by
demonstrating the interleaving of the steps of two processes that can
produce a) a bad balance, and b) a bad audit.
- With READ COMMITTED isolation, there are bad balances, but nothing
else goes wrong. Explain this, again by showing an interleaving of the
steps of two processes.
- With SERIALIZABLE isolation, the only problem is failed
transfers. (You could conceivably see a failed commit too.) Explain a
failed transfer by showing an interleaving of the steps of two
processes that produces this result.
Notes on Valgrind
Valgrind output
You will see valgrind output repeated 10 times. This is because
the spawn_workers function in main.cpp spawns 10
processes, and you are getting valgrind output for each.
libssl problems
As in Assignment 8, set this environment variable to avoid
error messages due to libssl:
export OPENSSL_ia32cap=0x00000000
libcrypto problems
Again, as in Assignment 8, you will still probably see some errors
that originate in libcrypto, e.g.
==16619== Use of uninitialised value of size 8
==16619== at 0x4BA93DC: ??? (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
==16619== by 0x4BA95DA: AES_encrypt (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
==16619== by 0x4C911DC: ??? (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
==16619== by 0x4CA01C2: ??? (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
==16619== by 0x4CD3B46: ??? (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
==16619== by 0x4CD3B8C: ??? (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
==16619== by 0x4CD3C5A: ??? (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
==16619== by 0x4CD4027: ??? (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
==16619== by 0x4CD44FD: ??? (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
==16619== by 0x4CD4AD8: RAND_DRBG_instantiate (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
==16619== by 0x4CD59BA: ??? (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
==16619== by 0x4CD5A56: ??? (in /usr/lib/x86_64-linux-gnu/libcrypto.so.1.1)
I don't see how to get rid of these without also getting rid of checks that you do want.
So just ignore these if you see them.
What to submit
Put these files in a zip file and submit:
- db.cpp
- db.h
- main.cpp
- Makefile
- txn.cpp
- txn.h
- q_and_a.txt