CSE551 -- Programming Assignment #3

In this assignment, you will build a simple Web service that provides a RESTful API to storing and retrieving blocks of data. Your goal is to learn about some modern technological building blocks, including:

• building simple HTTP services
• XML parsers, and the use of XML over HTTP as an RPC equivalent

Overview

First, some terminology:

• we define a "blockdata" object to be 4096 bytes of binary data. No other block size (smaller or larger) is permissible.

• we define a "blockid" object to be the SHA1 hash of the block data. A SHA1 hash, and therefore a blockid object, contains 20 bytes of binary data. Most languages contain support libraries for doing SHA1 hashes. For example, here is a page describing Python's support for SHA1 hashes (and other hash routines).

• we define a "block" object to be the union of a blockid and a blockdata object. The blockid object within a block must have a value which is the SHA1 hash of the blockdata object within the block.

• we will use "url safe base64 encoding" to represent binary data as safe, ASCII strings. For example, here is a url-safe, base64 encoded 20-byte block ID:

    fx8mgRaLcV8U9vxUuAibm9QOxg0=

  Most languages contain support libraries for doing URL-safe base64 encoding and decoding. For example, here is a page describing Python's support for base64 encoding.

  Be careful -- "url safe base64 encoding" is subtly different than standard base64 encoding, so be sure you're using the right one. In particular, I'd like everybody to use an implementation url safe base64 encoding that makes the following substitutions, and no other:

  • - instead of +
  • _ instead of /

  As a cautionary example, somebody pointed me towards a Java implementation that also substitutes . for = (i.e., it changes the padding character). Do not use this implementation (or, if you use it, modify it to fix it), otherwise you'll fail all of the conformance tests...

• we define a blocklist to be an XML document containing a list of block objects. Informally, the schema of the XML document should be:

  <blocklist>
  
    <block>
       <blockid>(some url-safe base64 data)</blockid>
       <blockdata>(some url-safe base64 data)</blockdata>
    </block>
  
    <block>
       <blockid>(some url-safe base64 data)</blockid>
       <blockdata>(some url-safe base64 data)</blockdata>
    <block>
  
    ...etc.
  
  </blocklist>
  

  A blocklist document can contain zero or more block objects.

  As a concrete example, here is a valid blocklist document that contains two block objects. (Note: your web browser won't render it correctly; download the linked document to your computer and look at it with a text editor.)

In case you are having trouble validating that you're properly doing the SHA1 hashing, the url-safe base64 encoding, or the XML document generation, here is a tar.gz archive that contains some example files that should help you out. In particular, it contains the following files:

• blockdata.bin: a file containing 4096 bytes of binary data
• blockid.bin: a file containing the SHA1 hash of blockdata.bin; note that this SHA1 hash is a 20 byte value
• blockdata.bin.urlsafe_base64: the urlsafe base64 encoding of blockdata.bin
• blockid.bin.urlsafe_base64: the urlsafe base64 encoding of blockid.bin
• blocklist.xml: an XML doc containing the blocklist structure associated with this block

Web server interface

  /cse551/fx8mgRaLcV8U9vxUuAibm9QOxg0=

For each of these kinds of URL, your server must handle the following HTTP methods:

• GET: your server should return a blocklist document containing the block associated with the blockID requested. Your server should return status code 200 if the requested block was found, and status code 404 if the requested block was not found. The content-type of the document (i.e., the Content-type HTTP header) that you return should be text/xml.

• DELETE: your server should delete the block specified in the URL. If the block was found and deleted, the server should return status code 200. If the block didn't exist, the server should return status code 404.

    /cse551/post

For each block in the blocklist, the server should verify that the blockid matches the hash of the blockdata. If all hashes match, the server should store the blocks and return a status code of 200. If any hash doesn't match, the server should store no blocks and return a status code of 400. If your server doesn't have the space to store all blocks, no blocks should be stored, and the server should return a status code of 503.

Finally, when the URL "/" is requested, your server should return a simple Web page that contains only the following string:

gribble(at)cs.washington.edu - Steven Gribble

Just to summarize:

• The unit of upload is the blocklist. Your server should always either store all or none of the blocks within the POSTed blocklist. If it returns a 200 status code, this implies all blocks were stored.

• The unit of download (GET) and deletion (DELETE) is the individual block. This means that clients should be able to download or delete an individual block, even if that block was uploaded as part of a set of blocks in a blocklist. Another way to think of this is that your server stores individual blocks, but clients are able to batch upload a set of blocks by POST'ing a blocklist containing that set.

Additional requirements

Registering your server

    /register/hostname/portnum

    http://futureproof.cs.washington.edu:8080/register/foo.com/1004

• parse the URL and verify that the hostname and portnumber are well-formatted and meaningful
• attempt to connect to your web server to retrieve the "/" URL, just to perform an end-to-end check
• return status code 200 if everything works
• return status code 404 otherwise

State kept durably

You can limit the amount of data you choose to store to 100MB if you like; if somebody attempts to POST blocks that would cause your server to exceed that limit, you should return a 503 status code.

Dealing with errors

NATs and port forwarding

You also have access to the attu instructional cluster, if you'd prefer to run your code there. If you choose to do this, please be nice, and don't whammy the machines.

Test code

There is also a test server running provided by the instructor that adheres to this specification for you to test your test suite against; the test server is running at futureproof.cs.washington.edu on port 8080.

Keep your server running

We've added a nice monitoring interface that shows our measurements of your server; to see it, visit:

  http://futureproof.cs.washington.edu:8080/monitor/

  http://futureproof.cs.washington.edu:8080/testharness/hostname/portnum

What to turn in

• a writeup that includes:
  • a brief description of how you implemented your server -- what operating system, language, and development tools did you take advantage of, and why?
  • a brief description of any interesting engineering problems you faced, such as dealing with errors
  • measurements showing the latencies of GET and POST operations, as well as the throughput of a large number of back-to-back POST and GET operations, and a short analysis of your measurements (why do you think they are what they are?)

• source code for your server, and a precise description of what libraries we would need in order to run your server, and any additional instructions needed to launch it

• source code for the test suite that you wrote or appropriated. If you borrowed code from one of your classmates, be sure to credit them.