Department of Information Technology

Consistent updates of a distributed database

Basic rules

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.

A synopsis of the assignment

arch.gif


The picture above shows the architecture of the distributed database system.

Assume that you have a distributed replicated database. This scenario offers many advantages, such as load balancing for queries and fault tolerance. The price of these advantages is additional complexity. Handling of crashed database instances require a detection mechanism. Consistency is also an important aspect. All database instances must contain the same information, and regardless of which instance is queried, the result should be the same.

Normally, one needs to take into account that nodes may be stopped, crash and come online while the system is running. To simplify implementation, we do not require your programs to handle these cases. You may however not use this to rationalize a choice of a strategy that would not work in the face of crashes or dynamic reconfiguration of the system, and you should provide a broad outline of how your system copes with crashes and dynamic reconfigurations.

Besides consistency, we are also interested in transaction atomicity: I.e., if we perform a set of operations, e.g. if we perform the operations A = 10 ; B = A + 10, then A should equal 10 and B should equal 20 afterwards, or the whole transaction should be rolled back.

Another important point is isolation. Concurrent transactions should be executed so that the result at the end can be
achieved by running the transactions sequencially.

Middleware

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.

Choice of algorithms

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.

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.

Reports

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.

Hints

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.

Updated  2006-01-22 20:22:45 by Ahmed Rezine.