Overview

The second project is to build a message queue client that interacts with a rudimentary pub/sub system using POSIX threads and network sockets via a RESTful API. In a pub/sub system there is usually one server and multiple clients:

As shown above, a typical pub/sub system has a server that maintains a collection of topics, which serve as endpoints for messages, and queues, which store the messages corresponding to individual clients or groups. Clients in the pub/sub system connect to this server and perform the following operations:

(1) SUBSCRIBE: This associates a queue to a particular topic.

In the example above, Client A sends an HTTP PUT command to subscribe the "Spidey" queue to the "Marvel" topic. This means that any messages sent to the "Marvel" topic will be automatically forwarded to the "Spidey" queue.

Note, clients can subscribe to as many topics as they wish. However, they will only receive messages after they have subscribed (any messages sent to the topic before they subscribe) will not be accessible.

(2) PUBLISH: This posts a message to a particular topic.

In the example above, Client B sends a HTTP PUT command to publish a message to the "Marvel" topic with the message body: "With great power, comes great responsibility". Internally, the pub/sub server will see that "Spidey" is subscribed to the the "Marvel" topic, and thus it will forward the message to the "Spidey" queue.

(3) RETRIEVE: This fetches one message in the queue.

In the example above, Client A sends a HTTP GET command to retrieve a message from the "Spidey" queue. Internally, the pub/sub server will fetch one message from the "Spidey" queue and return it as the response to the HTTP request.

Note, when clients retrieve a message but the corresponding queue is empty, then the pub/sub server will delay responding to the request until there is something in the queue. This means that performing a retrieve operation is a blocking action for the client.

Working in groups of one or two people, you are to create a library that utilizes POSIX threads and concurrent data structures to implement a client library for the described pub/sub system. Additionally, you are to utilize this library to a simple chat application. Both the client library and the chat application are due by noon on Saturday, October 9, 2021.

More details about this project and your deliverables are described below.

Publisher / Subscriber

As mentioned in class, pub/sub systems are used on many real-world platforms such as Google Cloud and Amazon Web Services. These systems allow developers to construct distributed and parallel applications that operate concurrently by utilizing both message passing and event-driven programming paradigms.

Protocol

The communication between the client and server utilizes HTTP to perform RESTful operations:

Operation Description Request/Response
Subscribe This associates a $QUEUE to a particular $TOPIC.
Request
PUT /subscription/$QUEUE/$TOPIC
Response

If $QUEUE does not exist, then the server will respond with a 404 HTTP status code and the message:

There is no queue named: $QUEUE

Otherwise, the server will respond with a 200 HTTP status code and the message:

Subscribed queue ($QUEUE) to topic ($TOPIC)
Unsubscribe This disassociates a $QUEUE to a particular $TOPIC.
Request
DELETE /subscription/$QUEUE/$TOPIC
Response

If $QUEUE does not exist, then the server will respond with a 404 HTTP status code and the message:

There is no queue named: $QUEUE

Otherwise, the server will respond with a 200 HTTP status code and the message:

Unsubscribed queue ($QUEUE) from topic ($TOPIC)
Publish This posts a message $BODY to a particular $TOPIC.
Request
PUT /topic/$TOPIC

$BODY

Response

If there are no subscribers to $TOPIC, then the server will respond with a 404 HTTP status code and the message:

There are no subscribers for topic: $TOPIC

Otherwise, the server will respond with a 200 HTTP status code and the message:

Published message ($BYTES bytes) to $SUBSCRIBERS subscribers of $TOPICS
Retrieve This fetches a message $BODY from a particular $QUEUE.
Request
GET /queue/$QUEUE
Response

If there is no $QUEUE, then the server will respond with a 404 HTTP status code and the message:

There is no queue named: $QUEUE

Otherwise, the server will respond with a 200 HTTP status code and the message $BODY:

$BODY

Some notes about this protocol:

Feel free to use curl or nc to play around with the either the client or server.

Server

Due to the limited time frame, a Python server is provided to you in the Project 02 repository:

# Usage
$ ./bin/mq_server.py --help
...

# Start Server on port 9123
$ ./bin/mq_server.py --port=9123

If you take a look at the server source code, you will see that it uses the Tornado framework, which provides event-based concurrency for overlapping compute and I/O. This means that the server will handle as many clients as system resources allow and will continuously process requests until the client disconnects (implicitly or explicitly).

Client

The main goal of this project is to create a client library (ie. lib/libmq_client.a) that communicates to a pub/sub server as described above. This library will be used by a variety of test programs and an chat application of your own design.

Concurrency

As shown above, the client library should utilize multiple POSIX threads to enable concurrent publishing and retrieving messages. This means that at any one time, the library should be able to do the following things concurrently:

  1. Publishing: The library should be able to publish any messages that have been queued up in an outgoing queue. That is, any PUBLISH or SUBSCRIBE requests should go to the outgoing queue rather than directly to the pub/sub server. It will be the job of a pusher thread to send the messages of the outgoing queue to the server.

  2. Retrieving: The library should be able to retrieve any messages that the server has available to the client and place them into an incoming queue. That is, a puller thread should continuously retrieve messages from the pub/sub server and place them in the incoming queue.

Because of this, the library should have at least 2 POSIX threads. To coordinate data access between these threads, you should utilize concurrent data structures. This architecture will allow the client library to operate asynchronously and allow the user to setup their own event loop or to simply overlap compute and I/O in any fashion they want.

Back to the Queue

Hide most of the complexity of multi-threaded programming by using concurrent data structures such as the queue we created in Lecture 10: Condition Variables. Note, you can use any combination of locks, condition variables, and semaphores to synchronize the threads in your client library.

Chat Application

Once you have implemented the client library and are confident in your testing, you must create a chat application that utilizes the pub/sub system. Here are some requirements:

  1. Must support multiple users from different machines.

  2. Must allow for users to enter in messages that are sent to other users via the pub/sub system.

  3. Must support a /exit or /quit command for terminating the application.

  4. Must terminate gracefully (ie. no hanging).

  5. Must properly manage resources (ie. no resource leaks).

Multiplexing I/O

To allow for reading and writing to the terminal at the same time, you normally would want to use the ncurses library for your chat application to handle the text-based graphics. However, this can be tricky and perhaps not worth your time investment. If you wish to do very basic I/O multiplexing in the terminal, then you can use this code skeleton for a shell:

https://yld.me/raw/cJ3H.c

This will allow you to receive input in a buffer and write to the terminal at the same time. When text is printed to the terminal, then the current buffer will be saved and shown below the printed text as you would experience in a normal chat application.

Of course, you will need to modify and adapt this code to fit the needs of your own chat application.

Chat Application

The exact nature of the messages exchanged between the clients is up to you. However, the chat application must utilize your client library and must utilize multiple threads correctly.

Deliverables

As noted above, you are to work individually or in pairs to implement libmq_client.a. You must use C99 (not C++) as the implementation language. Any test scripts or auxillary tools can be written in any reasonable scripting language.

Timeline

Here is a timeline of events related to this project:

Date Event
Monday, September 13 Project description and repository are available.
Saturday, October 2 Brainstorming should be completed.
Saturday, October 9 Client library and chat application must be completed.

Group Project

For the final submission, please open a Pull Request on your repository (for your development branch to the master branch) and assign it to the instructor.

Repository

To start this project, you must create a Project 02 repository on GitHub using the following template:

https://classroom.github.com/g/_asTMxCg

Note: Do your work in a separate git branch that can be later merged into the master branch (ie. make a development branch, DO NOT COMMIT OR MERGE TO MASTER).

Documentation

The Project 02 repository includes a README.md file with the following sections:

  1. Students: This should be the names and email addresses of each group member.

  2. Brainstorming: This contains questions that should help you design and plan your approach to the project. You do not need to fill these out, but they are meant to be helpful.

  3. Demonstration: This should contain a link to a video of your demonstration of your chat application.

  4. Errata: This should contain a description of any known errors or deficiencies in your implementation.

You must complete this document report as part of your project.

Source Code

As you can see, the base Project 02 repository contains a README.md file and the following folder hierarchy:

project02
    \_  Makefile        # This is the project Makefile
    \_  bin             # This contains the executables and test scripts
    \_  include
        \_  mq          # This contains the mq client header files
    \_  lib             # This contains the mq client library
    \_  src             # This contains the mq client source code
    \_  tests           # This contains the test source code

You must maintain this folder structure for your project and place files in their appropriate place.

K.I.S.S.

While the exact organization of the project code is up to you, keep in mind that you will be graded in part on coding style, cleaniness, and organization. This means your code should be consistently formatted, not contain any dead code, have reasonable comments, and appropriate naming among other things:

Please refer to these Coding Style slides for some tips and guidelines on coding style expectations.

Compiling

To help you get started, we have provided you with a Makefile with all the necessary targets:

$ make                  # Builds lib/libmq_client.a
Compiling src/socket.o
Compiling src/request.o
Compiling src/queue.o
Compiling src/mq.o
Linking   lib/libmq_client.a

$ make test             # Builds and runs test programs
Compiling tests/test_queue_functional.o
Linking   bin/test_queue_functional
Compiling tests/test_queue_unit.o
Linking   bin/test_queue_unit
Compiling tests/test_request_unit.o
Linking   bin/test_request_unit
Compiling tests/test_echo_client.o
Linking   bin/test_echo_client

Testing test_request_unit...
 request_create                           ... Success
 request_delete                           ... Success
 request_write                            ... Success

Testing test_queue_unit...
 queue_create                             ... Success
 queue_push                               ... Success
 queue_pop                                ... Success
 queue_delete                             ... Success

Testing test_queue_functional             ... Success

Testing test_echo_client                  ... Success

$ make clean            # Removes all targets and intermediate objects
Removing  objects
Removing  libraries
Removing  test programs

Note, you will need to modify this Makefile to build your chat application.

Running

As noted above, you are provided with a Python implementation of the pub/sub server. To run it, you just specify the port you want to use (by default it is 9620):

$ ./bin/mq_server.py --port=9456        # Start server on port 9456

Since you are only writing the client library, we have provided a simple test client application that uses your library called test_echo_client. Once the server is up and running, you can use the test program by doing the following:

$ ./bin/test_echo_client localhost 9456 # Contact localhost on port 9456

Implementation

All of the C99 header files are in the include/mq folder while the C99 source code for the client librar is in the src/client directory. To help you get started, parts of the project are already implemented:

[~] include/mq/client.h     # MQ client header (mostly implemented)
[x] include/mq/logging.h    # MQ logging header (implemented)
[~] include/mq/queue.h      # MQ queue header (mostly implemented)
[x] include/mq/request.h    # MQ request header (implemented)
[x] include/mq/socket.h     # MQ socket header (implemented)
[x] include/mq/string.h     # MQ string header (implemented)
[x] include/mq/thread.h     # MQ thread header (implemented)
[ ] src/client.c            # MQ client implementation (not implemented)
[ ] src/queue.c             # MQ queue implementation (not implemented)
[ ] src/request.c           # MQ request implementation (not implemented)
[x] src/socket.c            # MQ socket implementation (implemented)

Basically, the socket code along with the basic code skeleton is provided to you. However, you must implement the client, queue, and request structures and functionality. Each of the functions in the incomplete files above have comments that describe what needs to be done.

You will need to examine these source files and complete the implementation of the message queue client library. To do so, you will first need to implement a basic concurrent Queue structure and utilize it in your MessageQueue client structure:

  1. include/mq/client.h, include/mq/queue.h: While most of the headers are complete, these two are considered only mostly implemented because they lack any [mutexes], condition variables, or semaphores. That is, they do not currently utilize any synchronization primitives. You will need to determine which ones you wish to use and how.

    To help simplify your code a bit, we have provided include/mq/thread.h which contains macros and type definitions that can help simplify your POSIX threads code. Feel free to either use these or ignore them.

  2. src/request.c: This file contains the implementation of a Request structure which records the basic components of a HTTP request:

    a. method: This is the HTTP method to perform (ie. GET, PUT, DELETE).

    b. uri: This is the resource to access (ie. /topic/$TOPIC or /queue/$QUEUE)

    c. body: This is the body of the HTTP message.

  3. src/queue.c: This file contains the implementation of a concurrent Queue structure which implements a basic [monitor] for synchronized access to the Queue via push and pop operations. You will need to think carefully on how and when to use your synchronization primitives.

  4. src/client.c: This file contains the implementation of the MessageQueue client structure which is the object the user will interface with. This is where you will define functions that wrap and implement the RESTful API described above. Likewise, this is where you will need to implement the POSIX threads that run in the background (ie. pusher and puller).

Testing

To test the client library, we have provided a variety of tests:

$ make test

Testing test_request_unit...
 request_create                           ... Success
 request_delete                           ... Success
 request_write                            ... Success

Testing test_queue_unit...
 queue_create                             ... Success
 queue_push                               ... Success
 queue_pop                                ... Success
 queue_delete                             ... Success

Testing test_queue_functional             ... Success

Testing test_echo_client                  ... Success

The test_request_unit is a unit test for the Request structure you will be utilizing. Similarly, the test_queue_unit is a unit test for the concurrent queue you will be implementing. It also comes with a functional test (i.e. test_queue_functional) that tests the queue with multiple threads. Finally, we include a basic echo client test (ie. test_echo_client) that will use your message queue library to perform basic operations.

Feel free to create additional tests to verify the correctness of your library.

Reflection

To reflect on the project and the concepts involved, you will need to create a group video demonstration of your software artifact and complete an individual quiz (each member will submit their own answers to their own private assignments repository).

Video Demonstration

As part of your grade, your group will need to create a video that demonstrates and discusses the following:

  1. Your library passing the automated tests.

  2. Your chat application working with multiple clients.

  3. Any errata, quirks, or unresolved issues in your project.

  4. What you learned by doing this project.

The video should include narration to describe what is being presented and should cover the requirements enumerated above. It should be no longer than 5 minutes.

Please upload the video to either YouTube or Google Drive and provide a link to it in your README.md.

Individual Quiz

Once you have completed the project, answer the following Project 02 Quiz questions individually in your own personal assignments repository on GitHub:

The results of the quiz should look like the following:

Checking project02 quiz ...
      Q1 0.50
      Q2 0.50
      Q3 1.50
      Q4 1.50
   Score 4.00 / 4.00
  Status Success

Individual Quiz

Each group member must do the quiz on their own and record their answers in the project02 folder in their assignments GitHub repository.

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 07 TA List.

Grading

Your project will be graded on the following metrics:

Metric Points
Source Code
  1. General
    • Builds and cleans without warnings or errors
    • Uses system calls appropriately
    • Manages resources such as memory and files appropriately
    • Is consistent, readable, and organized
    • Has regular commits and submitted on-time.

  2. Request
    • Implements request_create appropriately
    • Implements request_delete appropriately
    • Implements request_write appropriately

  3. Queue
    • Implements queue_create appropriately
    • Implements queue_delete appropriately
    • Implements queue_push appropriately
    • Implements queue_pop appropriately

  4. Client
    • Performs SUBSCRIBE properly
    • Performs UNSUBSCRIBE properly
    • Performs PUBLISH properly
    • Performs RETRIEVE properly
    • Successfully shutdowns properly
    • Utilizes multiple threads for sending and receiving properly
    • Utilizes concurrent data structures properly
    • Free of concurrency bugs (race conditions, deadlocks, etc.)

  5. Chat Application
    • Supports multiple users from different machines
    • Utilizes multiple threads properly
    • Utilizes client library for communication properly
    • Free of concurrency bugs (race conditions, deadlocks, etc.)
    • Terminates gracefully
22.0
  1. 4.0
    • 0.5
    • 0.5
    • 1.0
    • 1.0
    • 1.0

  2. 1.5
    • 0.5
    • 0.5
    • 0.5

  3. 5.0
    • 0.5
    • 0.5
    • 2.0
    • 2.0

  4. 7.0
    • 0.5
    • 0.5
    • 0.5
    • 0.5
    • 1.5
    • 1.5
    • 1.0
    • 1.0

  5. 4.5
    • 1.0
    • 1.0
    • 1.0
    • 1.0
    • 0.5
Reflection
  1. Group Video Demonstration
    • Exhibits reasonable audio and video quality
    • Demonstrates library passing automated tests
    • Demonstrates chat application working with multiple clients
    • Discusses errata, quirks, or unresolved issues
    • Discusses what the group learned from the project

  2. Individual Quiz
8.0
  1. 4.0
    • 0.50
    • 1.00
    • 1.00
    • 0.75
    • 0.75

  2. 4.0

Commit History

To encourage you to work on the project regularly (rather than leaving it until the last second) and to practice performing incremental development, part of your grade will be based on whether or not you have regular and reasonably sized commits in your git log.

That is, you will lose a point if you commit everything at once near the project deadline.

Error Handling

In addition to meeting the functional requirements of the project (as described above), your program must not exhibit any memory leaks or invalid memory accesses as would be detected by Valgrind.

Additionally, because system calls can fail, your program must implement robust error handling and ensure your code checks the status of system calls when reasonable.

Moreover, you code must compile without any warnings (and -Wall must be one of the CFLAGS).