MP3: Distributed transactions

Due: 11:59pm, Monday, Apr 29

Notes

Overview

In this MP you will be implementing a distributed transaction system. Your 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.)

Clients, Servers, Branches, and Accounts

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. For each transaction, a client randomly picks one of the five servers to communicate with. The chosen server acts as the coordinator (and the frontend) for that transaction, and communicates with the client and all other necessary servers. In other words, the client communicates only with the transaction’s coordinator, and the coordinator then accordingly communicates with the other servers. The coordinator can be different for different transactions. More details on transactions and their properties have been provided later in this specification.

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. You need to handle multiple clients, where each client issues a single transaction and exits once the transaction completes. However, you do not have to deal with clients crashing in the middle of a transaction.

Configuration

Each server must take two arguments. The first argument identifies the branch that the server must handle. The second argument is a configuration file. E.g.: ./server A config.txt

The configuration file has 5 lines, each containing the branch, hostname, and the port no. of a server. The configuration file provided to each server is the same. A sample configuration file for a cluster running on group g01 would look like this:

A sp23-cs425-0101.cs.illinois.edu 1234
B sp23-cs425-0102.cs.illinois.edu 1234
C sp23-cs425-0103.cs.illinois.edu 1234
D sp23-cs425-0104.cs.illinois.edu 1234
E sp23-cs425-0105.cs.illinois.edu 1234

A client takes two arguments – the first argument is a client id (unique for each client), and the second argument is the configuration file (same as above), which provides the required details for connecting to a server when processing a transaction. E.g.: ./client abcd config.txt

Client Interface and Transactions

At start up, the client starts accepting commands from stdin (typed in by the user). The user will execute the following commands:

BEGIN
OK
DEPOSIT A.foo 10
OK
DEPOSIT B.bar 30
OK
BALANCE A.foo
A.foo = 10

If a query is made to an account that has not previously received a deposit, the server must abort the transaction and inform the client. The client should then print NOT FOUND, ABORTED.

BEGIN
OK
BALANCE C.baz 5
NOT FOUND, ABORTED
BEGIN
OK
WITHDRAW B.bar 5
OK
WITHDRAW C.baz 5
NOT FOUND, ABORTED

The client will forward each command in a transaction to the coordinating server for that transaction (that is randomly selected, as mentioned earlier). The coordinating server communicates with the appropriate server (corresponding to the branch in which the account is maintained) by sending it the command and receiving the outcome, which it then forwards to the client. The coordinating server handles ABORT and COMMIT commands by appropriately communicating with all other servers. Each server must process each command it receives in a way that satisfies the atomicity, consistency, and isolation properties discussed later in this spec.

Each client tackles a single transaction. Once the transaction ends (i.e. it has either been committed or aborted and the client has accordingly replied back with COMMIT OK or ABORTED), the client should exit.

Atomicity

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 a server) and all account values should be restored to their state before the transaction.

Consistency

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 account balance should be negative. If any balances are negative when a user specifies COMMIT, the transaction should be aborted.

BEGIN
OK 
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
OK 
DEPOSIT B.bar 20
OK
WITHDRAW B.bar 30 
OK
DEPOSIT B.bar 15
OK
COMMIT
COMMIT OK

Isolation

Your system should be able to support concurrent transactions from multiple clients simultaneously (we will run tests with up to 5 simultaneous clients). Note that each individual client handles sequential commands, only one transaction at a time. Your system 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.) A natural choice is to use two-phase locking or timestamped concurrency to achieve this (though these are not strict requirements).

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.

Deadlock Resolution

Your system must implement a deadlock resolution strategy. One option is deadlock detection, where the system detects a deadlock and aborts one of the transactions. You can also use concurrency control strategies that avoid deadlocks altogether (e.g. via timestamped concurrency control).

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. Moreover, your deadlock resolution strategy cannot assume that the objects requiring a lock are known apriori (when the transaction begins), as the user will input commands interactively.

The server system may choose to spontaneously abort a transaction (e.g. to break a deadlock, or while implementing timestamped concurrency control). When this happens, it must inform the client, and the client must display ABORTED to the user to indicate that the transaction has been aborted.

Notes:

BEGIN
OK
DEPOSIT A.foo 10
OK
DEPOSIT B.bar 30
ABORTED
….

Submission Instructions

Your code needs to be in a git repository hosted by the Engineering GitLab. After creating your repository, please add the following NetIDs as members with Reporter access:

You will also need to submit a report through Gradescope. In your report, you must include the URL of your repository and the full revision number (git commit id) that you want us to grade, as shown by git rev-parse HEAD. Make sure that revision is pushed to GitLab before you submit. Only one submission per group – it is set up as a “group submission” on Gradescope, so please make sure you add your partner to your Gradescope submission.

In addition to this, your report should include:

Design document

  1. A 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 (e.g. timestamped ordering), explain the other data structures 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.

  2. A description of how transactions are aborted and their actions are rolled back. Be sure to mention how your strategy ensures that other transactions do not use partial results from aborted transactions.

  3. Describe how you detect or prevent deadlocks.

Assumptions about input and folder structure instructions

Code input and output guidelines

The client should only print the responses to the commands or the ABORTED message (as described above). It should not print any additional messages.

For testing purposes, the client should support commands entered interactively via stdin (as exemplified above), as well as reading transaction commands one line at a time from a file redirected to stdin. For example, an input test file, in.txt, may contain the following lines:


BEGIN
DEPOSIT A.foo 20
DEPOSIT A.foo 30
WITHDRAW A.foo 10
DEPOSIT C.zee 10
BALANCE A.foo
COMMIT

Running ./client a config.txt < in.txt should print the following output:


OK
OK
OK
OK
OK
A.foo = 40
COMMIT OK

Every time a server commits any updates to its objects, it should print the balance of all accounts with non-zero values. Other than the above, the servers should not print any additional messages.

Sample Test

We have provided a sample script here that runs locally to test whether your code runs with the basic functionality. Place your folder with the code and the compiled executables inside the testing directory and rename it to src. You can run the test by executing ./run.sh. You should see no output for the diff command (after printing Difference between your output and expected output:) if your code passes the test. Otherwise, double check the difference between your client’s output and the expected output. The output of your clients will be saved as output1/2.log and the output of your servers will be saved as server_A/B/C/D/E.log. The testing script sets a timeout of 5s for each client (i.e. a client has up to 5s to finish executing its transaction and exit; it will be automatically killed after 5s) – ideally, your code should run much faster than that. The testing script used for grading will be similar to this sample test except that we will be running it in a distributed manner on the VMs and will be testing more complicated aspects of your code (e.g. how well you handle atomicity, consistency, isolation, and deadlocks). Passing this sample test does not automatically imply that you will pass all our test-cases. The sample test is provided only for you to sanity check whether the input/output format and the setup for your nodes complies with the specifications.

Graphs

You do not need to perform any experiment, or plot any graphs for this MP.

High-level Rubric

Acknowledgement

We would like to acknowledge Prof. Nikita Borisov for the initial design of this MP.

The source code of the website has been borrowed from Nikita Borisov