cs4414: Operating Systems

Problem Set 3 - Zhtta Web Server

Monday, 3 March at 11:59pm. Extended to Wednesday, 5 March at 11:59pm.

Purpose

The goals of this assignment are to learn about synchronization, scheduling, memory management, and caching by implementing a much more useful web server than the zhttpo server from PS1.

We also hope that at least one team will produce a server suitable for running rust-class.org for the rest of the semester so we won't have to suffer from any memory-leaking processes on the CS web server.

Collaboration Policy

For this problem set, you are required to work in a team of two or three people (except in cases where you were notified based on your PS2 teamwork that you should work alone for PS3, or where you make your own successful argument before February 19 that it is better for you to work alone).

Your team may not be the same as your team for PS2, so you should either (1) find a new partner to work with for PS3, or (2) if you want to work with your PS2 partner again you must find one other person to join your team. We will have some time at the end of class on Tuesday, 18 February to form teams. If you do not end up on a well-formed team by the end of class on 18 February, you should contact me right away.

Your teams should work together in a way that is efficient and collaborative, and ensures that both of you understand everything in the code you submit. As part of the grading for this assignment, you will do a short demo with one of the course staff, at which all team members will be expected to be able to answer questions about how your code works.

Please note that only one team member should create the private repository for this problem set. The other members should work in the same repository as a collaborator.

In addition to working directly with your teammates, you should feel free to discuss the problems, provide coding help, and ask for help with any students in the class (or anyone else in the world, for that matter), so long as you don't to it in a way that is detrimental to your own or anyone else's learning. You can do this in person, using the course forum (including comments at the end of this page), using the #cs4414 and #rust IRC channels, or any other communication medium you find most effective.

Getting Started

Before continuing with this assignment, one member of your team should:

  1. Set up the private repository named 'cs4414-ps3'.
  2. Add your teammate(s) and 'cs4414uva' as the collaborators.
  3. Clone the empty private repository to your working environment. Instead of mygithubname below, use your github username.
    git clone https://github.com/mygithubname/cs4414-ps3.git
  1. Get the starting code for ps3. 
    git remote add course https://github.com/cs4414/ps3.git
    git pull course master
    git push --tags origin master

After finishing these steps, everyone in the team should have access to your own cs4414-ps3 repository that contains starting code for ps3.

Background

Web servers are among the most important and performace-critical programs in the world today. Amazon estimated that each 100ms increase in latency reduced sales by 1% (this means if you can reduce latency by 100ms for Amazon that is worth $500M/year). Back when she still worked for Google, Marissa Meyer talked about how important speed is for user experience and reported that increasing the reponse latency by 400ms reduced searches by 0.7%. Failing to design a web service to scale well, can also have serious political consequences.

Modern web servers also provide many features beyond just serving static files. Features supported by Apache, the world's most popular web server, include content caching, server-side includes, and mechanisms for enforcing security policies.

For this problem set, your goal is to produce a high-performance web server that also supports some interesting features.

Putting the Z in zhtta: 1042 times better than zhttpto!

In PS1, we implemented a simple Web server named zhttpto (10-21</sup). Your zhttpto server has functionality similar to Sir Tim Berners-Lee's first web server, but is far from adequate for today.

With the help of Rust, zhttpto did support safe concurrency and memory management (unlike most web servers today), but still suffers from many obvious drawbacks and poor performance. Your Zhtta server may not be 1042 times better than zhttpto, but it should be a huge improvement (and better than apache in some ways)! We have provided starting code in zhtta.rs to help you take the first step.

Safe Visitor Counter

For Problem Set 1, you added a visit counter, but needed to use unsafe to do it (you should understand why the visit counter in PS1 was unsafe, but we'll leave that for a midterm question).

For this problem, your goal is to provide a visit counter with the same behavior, but without needing any unsafe code.

Problem 1. Modify your zhtta server to support a safe visitor counter. (Hint: one way to do this is to use an ARC.)

Server-Side Gashing

Many web servers (including Apache) offer the ability to run shell commands embedded in the web page. For example, using Apache Server-side Includes, you can put the following string in an HTML document to display the current date and time:

<!--#exec cmd="date" -->

This is done by passing the commands embedded in the page to a shell to execute, and then replacing the SSI tag with the result.

Problem 2. Modify the zhtta code to integrate gash in zhtta, to run commands embedded in HTML pages that use the .shtml extension. You may use your own gash, or use the PS2 reference solution. You should at least support the Apache #exec cmd="gash command" syntax shown above, where the command is run in the gash shell and its output is incorporated into the generated web page.

Benchmarking Web Servers

The goal of the rest of the problems on this assignment is to improve the performance of your Zhtta server (as well as for you to learn about scheduling and caching, which may not actually be the best ways to improve your server's performance!). When working on performance, it is very important to actually measure things in a smart way. There are lots of stories about effort wasted on performance improvements because of benchmarking problems.

An important measure of performance for a web server is how many concurrent connections it can handle. The C10K problem has been addressed by several modern web servers, including nginx and Microsoft IIS. A more relevant metric is how many users get responses to their requests in a reasonable amount of time.

A big challenge in benchmarking is that you want benchmarks that simulate well the actual traffic you are likely to receive, but that are simple and reproducible.

A simple tool for benchmarking web servers is httperf. To install httperf:

> curl -o httperf-0.9.0.tar.gz https://code.google.com/p/httperf/downloads/detail?name=httperf-0.9.0.tar.gz
> tar xfvz httperf-0.9.0.tar.gz
> cd httperf-0.9.0
> ./configure
> make
> sudo make install

You may get lots of warnings when you make since the httperf code is quite old and uses many deprecated SSL features (but it should still work even with the warnings).

Here are a few examples using httperf:

Send a single request to a server running on port 4414 of the localhost:

> httperf --hog --server=localhost --port=4414

Make 1000 connections to that server, at 10 requests per second:

> httperf --hog --server=localhost --port=4414 --num-conns=1000 --rate=10

For a more interesting test, create some sample files for your server to send by executing these commands:

dd if=/dev/urandom of=5K.bin bs=5K count=1
dd if=/dev/urandom of=5M.bin bs=5M count=1
dd if=/dev/urandom of=10M.bin bs=10M count=1
dd if=/dev/urandom of=20M.bin bs=20M count=1
dd if=/dev/urandom of=40M.bin bs=40M count=1
dd if=/dev/urandom of=80M.bin bs=80M count=1
dd if=/dev/urandom of=512M.bin bs=512M count=1

Then, use the zhtta-test.txt list of URLs for your requests (this file is included in the PS3 repo):

httperf --server localhost --port 4414 --rate 60 --num-conns 60 --wlog=y,./zhtta-test.txt

You will want to try different benchmarks and parameters, but this should be a good starting point to see if you are improving the server's performance. Make sure to consider both the total test duration and the average response time. You should add an automated way to perform benchmark tests to your Makefile to enable you to easily see if changes you make actually improve the performance of your server.

The benchmarking tests we run on your server include this test, but also include some other tests (the details of which we will not disclose until after the submission deadline).

Exploration 1. Try benchmarking your zhptto server from PS1 and the current zhtta server. Which has better performance? Can you explain the differences you see in the benchmark results? (You don't need to turn in anything for this, but should be prepared to talk about how you benchmarked your server and what you learned from it at your demo.)

Smarter Scheduling

The zhttpto server from PS1 used the main task as a listener and spawned a new task to handle each incoming request. This left the order in which requests were handled to be mostly up to the Rust scheduler. (Ambitious students will read the linked code from the Rust runtime implementation to try and understand how this would impact how web requests were scheduled.)

The provided zhtta code provides more control over how requests are scheduled. Before trying to modify this, you should examine the starting code to understand what happens when a request comes in and how the server schedules responses.

Exploration 2. Read the provided starting zhtta.rs code and figure out how the server schedules requests. You should be able to answer:

  • how many tasks are running before the first request arrives?
  • what are all the tasks that are involves in handling a request?
  • if a series of requests, r1, r2, ..., rn arrives in order, what can you say about the order in which the server will respond to them?

(You do not need to turn anything in for this, but should discuss it with your partners, and be well prepared to answer questions about this at your demo.)

For the next three problems, your task is to modify this scheduler to provide more control, performance, and flexibility in how requests are processed.

Prioritizing Tuition-Payers

Some administrators are worried that allowing non-UVa students to access the course materials may be unfair to tuition-paying UVa students whose requests to the course website may be delayed while the server wastes resources responding to requests from non-revenue-producing clients. This could be a problem with a socialist web server like Apache, but Zhtta should be able to do better!

Problem 3. Modify your scheduler to support a WahooFirst scheduling strategy that gives preferential treatment to requests from clients in Charlottesville.

You may assume that clients in Charlottesville can be distinguished by having an IP address that starts with 128.143. or 137.54. (if your own IP address starts differently, you should add that also). More ambitious groups will use an IP geolocation service like http://freegeoip.net to provide better accuracy, but this is not expected (and you shouldn't try this until you have completed the rest of the problems). The most ambitious students may integrate an authentication mechanisms like Persona with your server and give the highest priority to requests from users who have been authenticated with virginia.edu mailing addresses (and if your server is able to authenticate requests from clients paying out-of-state tuition, it should just kill all other processes on the machine whenever such a request comes in to make sure it is handled as quickly as possible).

Multiple Response Tasks

The starting code only has one task that does the work of responding to requests. This is very wasteful, even if we have only one core, since that task is spending most of its time waiting on I/O.

Problem 4. Modify your server to support multiple tasks that respond to requests. You should use benchmarking tests to determine a good number of response tasks to create for your host machine (but implement your solution in a way that this can easily be adjusted if you are running on a machine with more cores).

Reducing Median Latency

Shortest-Remaining-Processing-Time-First (SRPT) is a well-known preemtive scheduling algorithm in Web servers. By giving priority to short requests or those requests with short remaining time, a web server can minimize the average and median response time.

Problem 5. Modify your scheduler to implement Shortest-Processing-Time-First. Your scheduler should select the request with the shortest expected processing time (you can estimate this according to the size of the file for static requests, although will get better results if you do smarter things).

Implementing high-level shortest-processing-time first is satisfactory for this problem, but more ambitious students will also read Bianca Schroeder and Mor Harchol-Balter's paper, Web servers under overload: How scheduling can help (ACM Transactions on Internet Technology, Feb 2006) to learn more about scheduling web requests and attempt to implement some of the strategies describe in the paper also. (Some of the things they do would require making changes at the level of the network library code that is running in the kernel.)

File Streaming

The starting zhtta code sends a static file in respond_with_static_file using,

   stream.write(file_reader.read_to_end());

This means the entire file is read first, and then the contents are written to the output stream. For large files, this is very undesirable since the client requesting the file will not receive the first byte of file contents until the entire file has been read.

Problem 6. Modify the way Zhtta serves static files so that the file is trasmitted back to the client as it is read. (Hint)

Caching

Reading from files is expensive. We can significantly improve web server performance by caching responses for requests, but need to be careful about memory size tradeoffs (bigger caches mean more memory that is outside the processor's L2 and L3 caches and slower responses) as well as correctness (need to be careful about caching responses whose values may change).

Problem 7. Modify your server to improve its performance by caching selected files in memory. You should devise a caching strategy that optimizes the performance of your server on representative benchmarks.

Improving Performance

For the last problem, your goal is to improve the performance of your web server as much as you can (without, of course, breaking any functionality or sacrificing robustness).

Problem 8. Modify your server in some creative and interesting way to either improve its performance, improve its functionality, or both.

There are many ways to substantially improve the performance of the server. One big improvement would come from avoiding the need to queue all requests (for example, by responding to quick requests directly in the listener task), but without losing the flexibility of being able to queue requests.

You are encouraged to think of your own creative and effective ways to improve performance as much as you can. There will be prizes for the teams that produce the best performing web servers.

Submission, Benchmarking Competition, and Demos

There are four parts to submitting PS3:

  1. Submit the PS3 Submission Form (by 11:59pm on Wednesday, 5 March).

  2. Sign-up for a PS3 Demo. Demos will be held on Thursday (6 March) and Friday (7 March). You should sign-up for a demo time by 4:59pm on Wednesday, 5 March.

  3. Submit your server for benchmarking. To prepare for benchmarking, see Setting up your Zhtta Server on EC2 for directions for how to set up your Zhtta server running on EC2.

  4. Within 24 hours of finishing your demo, each team member shoud invidually submit the PS3 Assessment Form. Everyone should have submitted this form by Saturday, 8 March, but you should submit it shortly after your demo while things are fresh in your mind.

comments powered by Disqus

This assignment was originally created by Weilin Xu, Purnam Jantrania, and David Evans for University of Virginia cs4414 Fall 2013, and revised by Weilin Xu for Spring 2014.