CSC 590 Challenge - Bulletin Board Messages and Distributed Agreement
Bulletin Board Messages and Distributed Agreement: A CSC 590 Challenge
Stefan D. Bruda stefan@bruda.ca
Read all this handout carefully before you start working and make sure that you understand all the requirements. Indeed, all these requirements are reflected in the marking scheme.
Contents
1 Phase 1: A Bulletin Board Server 2
1.1 ApplicationProtocol .......................................... 2
1.2 PerformanceandOtherImplementationRequirements ...................... 4
1.3 TheBulletinBoardFile......................................... 4
1.4 ConcurrencyManagement....................................... 5
1.5 StartupandReconfiguration...................................... 5
2 Phase 2: Data Replication 5 2.1 Synchronization............................................. 6 2.2 ApplicationProtocol .......................................... 6
3 Implementation and Testing 8
3.1 Configuration .............................................. 8
3.2 Debugging................................................ 9
3.3 ReferenceandStagingComputingEnvironments.......................... 9
4 Submission 10 4.1 Presentation............................................... 10 4.2 HowtoSubmit ............................................. 11
5 Grading 12
6 Resources 12
Introduction
This challenge consists of two phases. In the first phase you will construct a simple network server. The next phase will consists of convincing multiple such servers to work together. Read the document completely before starting any coding; everything in the document is part of the specification and it is your responsibility to ensure that you have implemented the whole server as specified.
The challenge is set up so that it gives you the opportunity to showcase your skills at system program- ming in a POSIX1 environment. Indeed, you must implement the server as a UNIX service (“daemon”) and you further must use the POSIX API provided by the UNIX standard C library. Therefore your server must be written in C or C++.
Throughout the handout we will refer to the following configuration parameters. How these parameters are obtained will be described in Section 3.1. number), see Section 2;
d is a Boolean flag controlling the startup of the server, see Section 1.5;
D is a Boolean flag controlling debugging facilities, see Sections 1.3 (last paragraph) and 3.2.
Phase 1: A Bulletin Board Server
bp is the port number for client-server communication (positive integer), see Section 1; sp is the port number for inter-server communication (positive integer), see Section 2;
bbfile is the name of the bulletin board file that will be manipulated throughout this project (string), see Section 1;
max is the number of preallocated threads (positive integer), see Section 1.4;
peers the list of peers participating in synchronization (possibly empty list of pairs host name–port
Your first task is to construct a simple bulletin board server. The server accepts one-line messages from multiple clients, stores them in a local file, and serves them back on request. The name of the file is given by the parameter bbfile. Messages are identified upon storage by an unique number established by the server, and by the “sender ” of the message (as provided by the USER command explained below).
The clients connect to our server on port bp. We also assume a production environment so that we implement concurrency control.
1.1 Application Protocol
For reasons of interoperability a network application communicates using a strict protocol (called the ap- plication protocol). The particular application protocol used by your server is outlined in this section. Fixed-width font represents text which is fixed for the given command or response, while parameters that may vary are shown in italics.
Every command and response consists of a single line of text. The server should handle any combination of the characters ’\n’ and ’\r’ as line terminator and should send back responses terminated by a single ’\n’. You should be able to test your server using telnet as a client or indeed any other client capable of sending and receiving plain text.
Greeting
At the beginning of the interaction the server send the following text to the client that just connected:
0.0 greeting
where greeting is some (possibly empty) message intended for human consumption. There is no par- ticular format for the greeting text, but it is strongly suggested for this text to summarize the com- mands available to clients.
1In case you are wondering, POSIX originally came from “Portable Operating System Interface for uniX”. As time went by the standard was adopted by other operating systems, so that the “for uniX” part is no longer pertinent. Thus many people claim that nowadays POSIX stands for “Portable Operating System Interface with an X added at the end for coolness”.
Performance and Other Implementation Requirements
Your server must be robust, in the sense that no message shall be lost when the server is terminated, except possibly a message that is currently being written to disk. The bulletin board file should be considered too large to be kept completely in memory.
Your server must also be efficient, in the sense that it must not rewrite the whole bulletin board file upon the receipt of each and every message. It should use the file system as little as possible (within the robustness requirements above).
Now it is also the time to think about and implement a mechanism for rolling back the most recent transaction (write or replace). This is going to be used in the second part of the assignment.
You must build a concurrent server, which is able to serve many clients simultaneously. You must pro- vide an implementation based on POSIX threads, using concurrency management and thread preallocation (as explained in Section 1.4).
1.3 The Bulletin Board File
The bulletin board file specified in the configuration file or on the command line must be created if nonex- istent and must be re-used as is otherwise (rather than being overwritten). Message numbers are assigned by the server in sequence, according to the order in which the WRITE requests have been received. No two messages can have the same number in any bulletin board file. In particular, if the server is started on an existing file it should inspect the file on startup and make sure that any new message written to the file has an associated number that does not conflict with existing message numbers.
The access control to the bulletin board file follows the readers/writers paradigm, a common scheme in operating systems. Simultaneous reads of the bulletin board file by different threads of execution must be allowed. However, no other operation (read or write) is allowed when a thread writes to the bulletin board file. Of course, if a write request is issued while several read operations are in progress, the write will have to wait until the current reads complete. Note that this mechanism is slightly more complicated than the normal file locking. You may want to use a structure (that records the number of current read and write operations) protected by a critical region and also a condition variable to enforce this restriction. Inefficient implementations of this access control mechanism will be penalized. Do not use file locking for implementing the access control since this method will not work as expected.
1.4 Concurrency Management
The server must use preallocated threads. The number of threads to be preallocated is ? is also a limit on concurrency.
1.5 Startup and Reconfiguration
max, so that ? max
Whenever the configuration file and the command line (see Section 3.1) results in a value of true for d the server performs the following startup sequence:
- Bindstotheportnumbersasspecifiedandperformsanynecessaryinitializationofthedatastructures.
- Sets an appropriate umask.
- Installs appropriate signal handlers for all the signals.
- Leaves the current process group.
- Closes all file descriptors and re-opens them as appropriate. In particular console output is redirected to the file bbserv.log located in the current working directory.
- Detaches from the controlling tty.
- Puts itself into background.
- Check and writes into the PID file bbserv.pid located in the current working directory.
Whenever d is false the following steps above are not performed: 4, 5, 6, and 7.
The server reacts to the SIGQUIT and SIGUP signals as follows: It closes all the master sockets, terminates all the preallocated threads immediately after the current command (if any) is completed, and then closes all the connections to all the clients. If the signal received is SIGQUIT then the server terminates. If on the other hand SIGHUP is being handled, then the server re-reads the configuration file, applies the changes (if any) and restart the normal operation. However, any change of d is disregarded. Also note that as opposed to the normal startup (see Section 3.1) this time the (new) parameters re-read from the configuration file take precedence over the command line, including the list of peers (which is set exclusively according to the new configuration file).
2 Phase 2: Data Replication
We are now ready to implement a replicated database management system. Since we have it already we will use the bulletin board file as our database. This file is now kept replicated (and synchronized) on multiple servers.
Each server receive a list of the other servers that are participating in the synchronization. This is the list peers as specified in the configuration file and/or on the command line (see Setion 3.1). Each element in the list consists of a host name and a port number.
In addition, each server listens on port sp for incoming requests for synchronization. 5
2.1 Synchronization
The fact that this is a replicated database is transparent to the clients. All the peers are equally capable of serving clients as described in the previous section. The only perceptible difference is a possible delay in the response of a request to write or replace a message. Any USER, READ, or QUIT request is served locally as before. The synchronization between servers is initiated by the receipt of a WRITE or REPLACE command, and is accomplished using the two-phase commit protocol. This protocol is widely used in applications where data consistency is critical. Specifically, the protocol ensures as much as possible that data stored at each replica server are identical, even if this causes some data to be lost.
When using the two-phase commit algorithm, the server that received the WRITE or REPLACE command becomes the master (or coordinator), and the others become salves (or participants). In passing, note that the master becomes a client to all of the slaves. As the name of the algorithm implies, it consists of two phases:
2.2 Application Protocol
You are responsible for designing the application protocol for the two-phase commit algorithm. Give some thought to this design, preferably before starting coding so that your protocol is robust and unambiguous. The protocol must be fully described in a file named protocol2pc.txt included in your submission.
In addition, whenever D is true your server must print to the standard output all the messages ex- changed with its peers (sent and also received). Please identify in such a printout what are the messages that have been sent and what are the messages that have been received.
3 Implementation and Testing
Most of the implementation requirements have already been outlined earlier. The only major thing left to specify is how are the configuration parameters obtained. We also include a short discussion on debugging considerations.
3.1 Configuration
Upon startup, our server reads a configuration file. This file contains pairs consisting of a variable name and a value for that variable, separated by an = character (with no blanks). The configuration file includes (in no particular order) the following definitions:
Most of the lines in the configuration file are optional; each missing line causes the respective variable where max, 9000 for bp, 10000 for sp, an empty list for peers, true for d, and false for D. The only mandatory data is bbfile; if the server cannot obtain the file name from either the configuration file or the command line (see below) then it must refuse to start (with a suitable error message printed to the standard output). The server never modifies the configuration file, even if it is missing or incomplete.
The default configuration file is called bbserv.conf and resides in the current directory. The name can be overridden by the command line option -c whose argument specifies (using an absolute or relative path) the configuration file to be used for the respective session.
