Consistent updates of a distributed database

This assignment is designed to be solved in groups of two students. If you want to try it on your own, you should contact your assignment advisor (check the course information).

Groups with more than two persons will not be accepted.

The clients and databases used in this assignment are provided for you, and you may not change or replace them. Between the clients and databases we have a layer of software called a middleware.

To the clients, the system looks like a single server, and it has no knowledge of replication or other clients. To the client, the system appears as if the client was the only user.

The database instances, on the other hand, are really just databases with no knowledge of replication or other database instances. They only provide single threaded access to a database, but no record locking or other useful functions.

The middleware is the glue that connects clients with databases and provide replication, consistency and handles competing clients.

The goal of the assignment is to construct the middleware. You will be provided with sources for a stub middleware that only connects a single client with a single database, but with no replication, no awareness of other middlewares or other functionality.

Your choice of strategy for your middleware will force you to change many parts of the provided middleware, but you should take care not to change the semantics, as perceived by the user of the front end.

The first part of the assignment is to choose two workable strategies for implementing a distributed middleware and describe them. We use the word strategy, because it is most likely not a single algorithm, but a combination of algorithms.

Both of your strategies must be described in enough detail that it should be obvious how to implement them. Compare these two strategies, pointing out their strengths and weaknesses.

You will then proceed to chose one of these two and implement it. Normally, the final choice of algorithm will be dependent on how the database will be used, but in this case you do not know this and should instead give a motivation of your choice and explanation of the case where this strategy will work well, and under which circumstances it will be less efficient. In other words, you must give a real-world example of a situation in which your chosen strategy would be a good choice.

In choosing strategy, consistency is paramount, but efficiency is also important. Solutions that cause unnecessary delays will not be accepted. You must carefully document situations in which other transactions are blocked by one transaction, and motivate why this blocking is necessary and reasonable. In order to make the handling efficient you have to differ between locking a resource for reading and locking for writing.

Good places to look for algorithms are:

• Chapter 5 in "Distributed Systems, Principles and Paradigms" by Tannenbaum and van Steen
• Chapter 10 (especially 10.4) and chapter 12 in "Distributed Systems, Concepts and Design" (3rd Ed) by Coulouris, Dollimore and Kindberg (10.3 and 13 in the 2nd Ed)

It is very important that you hand in your first report in time. You need to receive a green light from your advisor before doing your implementation.

Implement your chosen strategy and construct test cases to verify that it works correctly. You need to run multiple middleware, clients and databases. While you are not required to handle dynamic reconfiguration, you system should be reconfigurable at start-up to handle an arbitrary number of databases and middlewares.

You are expected to implement this in C++. The existing skeleton does not make use of extensive C++ features. Knowlegde of C should be sufficient to implement a working solution.

Databases

Database instances are called DATABASE<n> where <n> is a number. The database program is started with an argument <n> that specifies the <n> part of the name of this database instance. Do not run multiple databases with the same number.

Middlewares

Middlewares are called MIDDLEWARE<n> where <n> is a number. As with databases, avoid registering several middlewares with the same name.

Middlewares register themselves and open the client port by calling the function start_middleware_frontend(). Middlewares should de-register themselves at termination by calling stop_middleware_frontend().

A single UNIX process can only handle a single middleware.

Clients

Clients specify what middleware to communicate with, and a filename of a file containing the operations that should be performed. Any results will be printed out.

Provided software

For this assignment, most of the software is provided to you. See the assignment's web page to download the package. Since there might be updates to this package, please make sure that the assignment advisor has your email-address.

System start

Since the startup of a distributed system is a fairly big problem in itself, you are given much freedom in how to implement start-up of your system. The only requirement is that you provide a start-up program or script (sh, csh, perl, python...) that takes arguments as follows:

STARTUP <N - number of middlewares> <machine1> ... <machineN> <M - number of databases> <machine1> ... <machine M>

Hint: You can use the command rsh to start programs on other computers inside the local it network.
E.g, to start a system consisting of two databases running on machines "Beta" and "Gamma" and two middlewares running on machines Alpha and Beta, you would issue the following command:

1. ./STARTUP 2 Alpha Beta 2 Beta Gamma

You can also use the already existing startup program. Use it, modify it, do whatever you want with it. The syntax for this program is a bit different from above. Already existing startup program syntax:

1. ./startup -m host1:host2:...:hostN -d host1:host2:...:hostN

where -m is the middleware hosts and -d the database hosts.

You are expected to hand in two reports. The first one must contain:

• A filled out front page for the assignment (see assignment's web page)
• A description of the two strategies and differences between them. Each strategy should address:
  • Atomicity
  • Isolation
  • Concurrency

For example, possible strategies could consist in Optimistic Concurency Control with Private Workspace, or strict Two Phase Locking with Write-ahead log.

• When concurrency is handled by mutual exclusion, please consider the following points: Can deadlocks happen? What must be done to prevent them? How does a process wait for a resource locked by another process (active waiting, use of notification)?
• If a strategy makes use of timestamps, you have to describe how to implement timestamps in a distributed environment. Why is time harder to handle in a distributed environment?

The second report should consist of the following parts:

• A filled out front page for the assignment.
• Remind what strategy you chose to implement.
• Explanations, descriptions and listings of the tests you have run to verify that your implementation performs correctly. Remember to test every required property:
  • Atomicity
  • Consistency
  • Isolation
  • Durability
  • Absence of deadlocks (if you use mutual exclusion)
  • Good performance, unnecessary long waiting times are not acceptable.
• Well documented sources of your implementation. Do not forget to include a print-out of your sources.
• A pointer to your sources. The advisor will check your implementation by running his own tests.

Finally, when you hand-in a corrected version of your report (either the first one or the second), always join all older versions of your reports.

You will probably need to use the select() system call to be able to accept data from multiple sources. Study the manual pages carefully, select() is a very useful mechanism, but the interface is not trivial.
You should make your middlewares single threaded, i.e. you only have to handle a single client per middleware at a time. Your system must be able to handle multiple clients connecting in parallel to different middlewares.

Helpful information about network programming can be found at Beej's Guide to Network Programming.
Be careful when implementing communication between middlewares. Students often tend to use TCP because of its reliability, even in cases where UDP would be a more natural choice. Imagine a situation where middlewares A and B want to send a message to all other middlewares simultaneously. The following obvious algorithm is incorrect:

SendMessageToEveryone:
for all other middlewares C: sock = connect(C); write(sock); close(sock);

Since A and B are not accept()ing connections during the short period of time they are sending their messages, concurrent calls to connect(B) (from A) and connect(A) (from B) will never complete.
Solutions:

• Establish connections during the system's startup once and for all.
• Use connection-less communications (UDP)

The first solution is far from ideal, because it makes it hard to handle loss of connections, and it prevents dynamic reconfiguration (addition of new middlewares on-the-fly). Although you are not supposed to implement dynamic reconfiguration, you are not allowed to use solutions that would make it impossible to support it in a 100% finished product.
The second solution requires you to implement a message acknowledgement mecanism to cope with lost packets, which is not very hard, but requires some additional coding efforts.

In further updates of the package and the course home pages, additional hints and information may be added as the course progresses.