In this MP you will be implementing a distributed transaction system. You goal is to support transactions that read and write to distributed objects while ensuring full ACI(D) properties. (The D is in parentheses because you are not required to store the values in durable storage or implement crash recovery.)
You are (once again) implementing a system that represents a collection of accounts and their balances. The
accounts are stored in five different branches (named A, B, C, D, E). An account is named with the
identifier of the branch followed by an account name; e.g., A.xyz is account xyz stored at branch A.
Account names will be comprised of lowercase english letters.
You will need to implement a server that represents a branch and keeps track of all accounts in that branch, and a client that executes transactions by communicating with all the necessary branches. You may optionally use a separate coordinator server for coordinating the transactions.
Unlike the previous MPs, you do not have to handle failures and can assume that all the servers remain up for the duration of the demo. Clients may exit but you do not have to deal with clients crashing in the middle of a transaction.
At start up, the client should automatically connect to all the necessary servers and start accepting commands typed in by the user. The user will execute the following commands:
BEGIN: Open a new transaction, and reply with “OK”.DEPOSIT server.account amount: Deposit some amount into an account. Amount will be a positive integer.
(You can assume that the value of any account will never exceed 1,000,000,000.)
The account balance should increase by the given amount. If the account was previously unreferenced, it
should be created with an initial balance of amount. The client should reply with OKDEPOSIT A.foo 10 OK DEPOSIT B.bar 30 OK
BALANCE server.account: The client should display the current balance in
the given account:BALANCE A.foo A.foo = 10
If a query is made to an account that has not previously received a deposit, the client should print NOT FOUND and abort the transaction.
WITHDRAW server.account amount: Withdraw some amount from an account. The account balance should
decrease by the withdrawn amount. The client should reply with OK if the operation is successful. If the
account does not exist (i.e, has never received any deposits), the client should print NOT FOUND and abort
the transaction.BEGIN WITHDRAW C.baz 5 NOT FOUND
COMMIT: Commit the transaction, making its results visible to other transactions. The client should reply either with COMMIT OK or ABORTED, in the case that the transaction had to be aborted during the commit process.ABORT: Abort the transaction. All updates made during the transaction must be rolled back. The client should reply with ABORTED to confirm that the transaction was aborted.Notes:
BEGIN).DEPOSIT A.foo -232 or
WITHDRAW B.$#@% 0.DEPOSIT A.foo 10 and then call BALANCE on
A.foo in the same transaction, I should see the deposited amounts. Whether updates from other transactions are seen depends on whether those transactions are committed and isolation properties, discussed below.ABORT before getting a response and you must abort the transaction immediately.BEGIN. E.g.:BEGIN DEPOSIT A.foo 10 OK DEPOSIT B.bar 30 OK ABORTED
Transactions should execute atomically. In particular, any changes made by a transaction should be rolled back in case of an abort (initiated either by the user or the server) and all account values should be restored to their state before the transaction.
As described above, a transaction should not reference any accounts that have not yet received any deposits
in a WITHDRAW or BALANCE command. An additional consistency constraint is that, at the end of a
transaction no acccount balance should be negative. IF, when a user specifies COMMIT any balances are
negative, the transaction should be aborted.
BEGIN DEPOSIT B.bar 20 OK WITHDRAW B.bar 30 OK COMMIT ABORTED
However, it is OK for accounts to have negative balances during the transaction, assuming those are eventually resolved:
BEGIN DEPOSIT B.bar 20 OK WITHDRAW B.bar 30 OK DEPOSIT B.bar 15 OK COMMIT COMMIT OK
You should support up to 10 simultaneous clients that execute transactions concurrently. You should guarantee the serializability of the executed transactions. This means that the results should be equivalent to a serial execution of all committed transactions. (Aborted transactions should have no impact on other transactions.) You may want to use two-phase locking to achieve this, though this is not a strict requirement. (E.g., you can implement timestamped concurrency instead.)
You must support concurrency between transactions that do not interfere with each other. E.g., if T1 on
client 1 executes DEPOSIT A.x, BALANCE B.y and then T2 on client 2 executes DEPOSIT A.w, BALANCE B.z,
the transactions should both proceed without waiting for each other. In particular, using a single global
lock (or one lock per server) will not satisfy the concurrency requirements of this MP. You should support
read sharing as well, so BALANCE A.x executed by two transactions should not be considered interfering.
On the other hand, if T1 executes DEPOSIT A.x and T2 executes BALANCE A.x, you may delay the execution
of one of the transactions while waiting for the other to complete; e.g., BALANCE A.x in T2 may wait to return a response until T1 is committed or aborted.
For extra credit, you may implement a deadlock resolution strategy. One option is deadlock detection, where
the system detects a deadlock and aborts one of the transactions.
As discussed earlier, aclient can spontaneously display ABORTED to the user at any
point in time to indicate that the transaction has been aborted. Remember that deadlocks may span multiple servers and clients.
You should not use timeouts as your deadlock detection strategy because transactions will be executed interactively and this will therefore result in too many false positives. Likewise, you should not use lock ordering or early locking since the client interface does not allow you to specify the entire set of locks to be acquired.
On the other hand, you can use timestamped concurrency, or other strategies, that avoid deadlocks altogether, and you will receive extra credit for this part, assuming that the strategy is implemented correctly and successfully avoids deadlocks.
Unlike previous MPs, we are not asking you to perform experiments in this MP. You do need a design document that describes the following details about your implementation.
A walk-through of a simple transation that clarifies the roles that the clients, servers, and coordinator (if any) play; i.e., what messages are sent, what state is maintained by which of the nodes, etc.
An detailed explanation of your concurrency control approach. Explain how and where locks are maintained, when they are acquired, and when they are released. If you are using a lock-free strategy, explain the other data structures (timestamps, dependency lists) used in your implementation.
If your algorithm implements a strategy that does not directly follow a concurrency strategy described in the lecture or the literature, you will also need to include an argument for why your strategy ensures serial equivalence of transactions.
A description of how transactions are aborted and their actions are rolled back. Be sure to mention how you ensure that other transactions do not use partial results from aborted transactions.
If you are implementing the extra credit, describe how you detect or prevent deadlocks.
Your document should also include the location of your git repository for the project and the commit hash of the revision you want us to evaluate, as in previous MPs.