CS/SE Individual Practical (08-09) Part 1: Familiarisation with Chord and DHash

Issue: Wednesday Week 2 (1st October)
Due: Thursday Week 6 (30th October)
Weighting: 25% of overall mark.

Introduction

The Chord protocol provides a mapping from a set of identifiers to a set of nodes. The identifiers are 160 bit words in the original Chord protocol. Typically, they are the produced by secure hash functions from perhaps file names or the contents of files. Each node is typically a computational and storage resource accessible via a port at some Internet address. The protocol is accessible from any node and distributes its computational and storage requirements amongst the nodes. There is no centralised server managing the mapping. This gives the protocol, and applications based on it, significant scalability.

A common layer built on top of the protocol is a distributed hash table (DHash). The Chord protocol mapping provides one stage in the mapping of, for example, a filename to a location on some node where that file is stored.

Java implementations of the Chord protocol and a distributed hash table are provided as the starting point for your work on this part of IP.

The Part 1 tasks involve making minor extensions to the provided Chord protocol and DHash implementations. These extensions will help you develop your understanding of the provided code base.

Before starting work, please read fully these instructions and the auxiliary web pages on the Chord protocol and Java RMI. These auxiliary pages are linked to in the next section.

Please use the newsgroup and weekly meetings to ask for clarifications on any of the instructions here and on the supplied code.

Background Reading

System Architecture

It is essential that you read and understand this summary of the Chord protocol. You might well find it useful to have a look at the paper

Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan, ACM SIGCOMM 2001, San Deigo, CA, August 2001, pp. 149-160.

Focus on Sections 1-4 of this paper which deal with the non-concurrent version of the Chord protocol that is used in this assignment.

The Chord protocol itself is only concerned with mapping Chord identifiers to nodes in the peer to peer system. It is not concerned with data storage at the nodes. The paper

Wide-area cooperative storage with CFS, Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica, ACM SOSP 2001, Banff, October 2001.

discusses the implementation of a distributed hash table and a distributed file system on top of the Chord protocol. The supplied code for the Chord protocol and hash table and the filesystem you are to design follow the basic architecture described in this paper, but do not include most of the more sophisticated features that this paper covers. Both papers are available from the Chord Project home page.

Java RMI

This assignment makes extensive use of the RMI (Remote Method Invocation) capability that comes packaged with the Standard Edition of Java. This RMI resources page should be consulted to learn more.

The provided Chord protocol implementation

The implementation classes and interfaces are:

ID: (Class) Chord ring identifiers.
ChordNodeImp: (Class) Implements the Chord protocol. The methods here are close to those described in the Chord protocol paper cited above.
ChordNode: (Interface) Specifies those methods of ChordNodeImp that need to be callable remotely. Implemented by ChordNodeImp.
ChordNodeRef: (Class) Wraps references to ChordNode objects, caching frequently accessed information such as ID values.
AppNode: (Interface) In a typical Chord protocol application, each Chord node is paired with an application node. This interface specifies a callback method the application node should provide for the situation when a Chord node acquires a new predecessor.

In addition, several classes and interfaces are provided for testing the implementation in both single and multiple JVM contexts. These are:

IDTest: (Class) A JUnit test class for the ID class. This is a good example of a unit test. Fairly thorough tests are provided of most of the public methods of ID.
CNTest: (Class) A JUnit test class for constructing and exercising rings of ChordNodeImp objects. The architecture of the test-bench has been set up so that the code executed is virtually identical, whether the ChordNodeImp objects exist in one or more than one Java runtime.
CNSlaveImp: (Class) Each ChordNodeImp object is paired with a CNSlaveImp object in the same Java runtime. CNSlaveImp methods exercise the user oriented methods of ChordNodeImp objects (e.g. to map an ID to a node) under the direction of test methods in a CNTest master.
CNSlave: (Interface) This interface is implemented by the CNSlaveImp class. It declares certain CNSlaveImp methods to be remotely callable by Java's RMI support. A test method of CNTest running in one Java runtime can control not only local ChordNodeImp objects by exercising local CNSlaveImp objects, but also can control all ChordNodeImp objects in other Java runtimes by making appropriate RMI calls to the corresponding CNSlaveImp objects.
CNFactoryImp: (Class). This is a singleton class: there is exactly one object of this type. The CNFactoryImp method makeCNSlave() constructs a CNSlaveImp object (which in turn constructs its correspondingChordNodeImp object). The CNSlaveImp constructor is wrapped in this way to enable CNSlaveImp objects to be constructed on command from CNTest test methods by using RMI.
AuxProcess: (Class). Provides utility methods for running commands in new processes.

We call this test architecture a master-slave architecture because a CNTest master controls one or more CNSlaveImp slaves.

The file pt1/README.txt describes the locations of the Java files and instructions for compiling and running them.

The provided distributed hash table implementation

A layered architecture is adopted where the distributed Chord protocol implementation is largely hidden from users of the hash table.

The main classes and interfaces are:

DHashNodeImp: (Class) An object in this class holds key value pairs for some associated ChordNodeImp object.
DHashNodeClient: (Interface) This interface specifies control methods for initialising new DHashNodeImp objects and adding them to existing rings of DHashNodeImp objects. It also specifies a set of typical methods one might expect any map class to support. For example, it has a method for inserting a new key value pair, and a method for looking up a value, given a key. This interface completely hides the Chord protocol implementation, and the distributed nature of the hash table is only apparent in the control methods.
DHashNode: (Interface) Declares DHashNodeImp methods that need to be callable via RMI from DHashNodeImp methods executing in another JVM.

A master-slave test architecture is also adopted for testing rings of DHashNodeImp objects. This is similar to that used for testing rings of ChordNodeImp objects, though there are slight differences in how the master and slave processes are started up. The relevant classes and interfaces are:

DHNTest: (Class)
DHNSlaveImp: (Class)
DHNSlave: (Interface)
DHNFactoryImp: (Class)

Additional classes and interfaces include:

CNHandler: (Class) Defines methods for handling and formatting logging messages.
MonitorImp: (Class) Used for monitoring certain logging messages coming in from DHash nodes and Chord nodes in a distributed setting. Also provides a way for slave processes to make initial contact with the master test process.
Monitor: (Interface) Declares remotely accessible methods of MonitorImp objects.
DHAppNode: (Interface) Just as the Appnode interface characterises a generic application node for ChordNodeImp objects, so this DHAppNode interface characterises a generic application node for DHashNodeImp objects. No significant use is made of it in Part 1.
SimpleDHAppImp: (Class) Class to demonstrate use of the DHAppNode interface.
SimpleDHApp: (Interface) Declares remotely accessible methods of SimpleDHAppImp.

Again, the file pt1/README.txt describes the locations of the Java files and instructions for compiling and running them.

Tasks

Task A: Reporting Chord and DHash configurations

Extend the provided DHNTest with a static method

    private static void printRing(DHNSlave d) throws RemoteException {}

that prints out the current status of the Chord and DHash rings, including for each node:

The domain of the node, a name assigned to the JVM containing the node
The node's ID
The predecessor node's ID
The ID of each node in the node's finger table
The data stored in the local hash table for the node, including keys, key IDs, and values.

For example, after the join of node 15 in test1() provided in DHNTest, it should print something like:

[B]   7   ( 1') :  9   9  15' 15'   [ka( 2) va] 
[B]   9   ( 7 ) : 15' 15' 15'  1'   [kb( 9) vb] 
[A]  15   ( 9') :  1   1   7'  7'   [kc(14) vc] 
[A]   1   (15 ) :  7'  7'  7'  9'

Here, there's one line for each node in sequence round the ring from the d argument starting point. The line for a node lists the domain, predecessor and fingers of the Chord node, and the key value pairs stored at the corresponding DHash node. The IDs corresponding to key names are shown after the key names to make it easy to see whether each key-value pair has been stored on the correct node. The forward quote(') characters after the IDs are used to indicate that the predecessor or finger is referring to a node in a remote process.

Assume that printRing() is only used with IDs of up to say 9 bits in size, and that the key value data is brief, so information on each node can fit comfortably onto a single line. Display IDs in decimal.

Add printRing() calls to test1() after each change in ring configuration, and add println() calls so that the operations of the test are intellible from the print output. For example, part of the output might look like:

[B]   7   ( 1') :  9   9   1'  1'   [ka( 2) va] 
[B]   9   ( 7 ) :  1'  1'  1'  1'   [kb( 9) vb] 
[A]   1   ( 9') :  7'  7'  7'  9'   [kc(14) vc] 

Joining new node 15 to ring

[B]   7   ( 1') :  9   9  15' 15'   [ka( 2) va] 
[B]   9   ( 7 ) : 15' 15' 15'  1'   [kb( 9) vb] 
[A]  15   ( 9') :  1   1   7'  7'   [kc(14) vc] 
[A]   1   (15 ) :  7'  7'  7'  9'   

Adding key-value pairs d,e

[B]   7   ( 1') :  9   9  15' 15'   [ke( 3) ve] [ka( 2) va] 
[B]   9   ( 7 ) : 15' 15' 15'  1'   [kb( 9) vb] 
[A]  15   ( 9') :  1   1   7'  7'   [kd(13) vd] [kc(14) vc] 
[A]   1   (15 ) :  7'  7'  7'  9'

You should convince yourself that these configurations are as you might expect.

You might find the format method of the java.util.Formatter class useful for printing to fixed-width fields.

Task B: Tracing behaviour of findSuccessor()

Look in the ChordNodeImp class at the findSuccessor() method implementation. The code for this method and the main methods it calls includes invocations of logging methods to enable tracing of the search for a node responsible for an id.

The logging code makes use of the java.util.logging package. The Java API documentation page for this package decribes the overall organisation of the Java logging classes and links to further documentation on the package.

Logging is configured so that log records created in logging invocations in the ChordNodeImp class make their way to the publish() method of the supplied CNHandler class. This formats records as strings and passes these strings, possibly using remote method invocations, to the publish() method of the MonitorImp class, which does some further formatting and prints the log messages. The point of this organisation is to pull together and suitably interleave logging messages that originate in the possibly multiple Java processes involved in the findSuccessor() execution. In a multiple process test, the findSuccessor() and CNHandler publish() methods all execute in the test slave processes, whereas the MonitorImp publish() method executes in the test master process, printing to the standard output of the master process.

Task B involves understanding the supplied code and completing the code in the provided CNHandler and MonitorImp classes in order to generate logs of form:

[A] ENTERING n1.findSuccessor(5)
[A] Calling n1.findStrictPredecessor(5)
[A]    ENTERING n1.findStrictPredecessor(5)
[A]    RETURNING n1
[A] Receiving n1
[A] RETURNING n7'

[B] ENTERING n9.findSuccessor(8)
[B] Calling n9.findStrictPredecessor(8)
[B]    ENTERING n9.findStrictPredecessor(8)
[B]    Calling n9.closestStrictlyPrecedingFinger(8)
[B]       ENTERING n9.closestStrictlyPrecedingFinger(8)
[B]       stopped at finger 4 
[B]       RETURNING n1'
[B]    Receiving n1'
[B]    Calling n1'.findStrictPredecessor(8)
[A]       ENTERING n1.findStrictPredecessor(8)
[A]       Calling n1.closestStrictlyPrecedingFinger(8)
[A]          ENTERING n1.closestStrictlyPrecedingFinger(8)
[A]          stopped at finger 3 
[A]          RETURNING n7'
[A]       Receiving n7'
[A]       Calling n7'.findStrictPredecessor(8)
[B]          ENTERING n7.findStrictPredecessor(8)
[B]          RETURNING n7
[A]       Receiving n7'
[A]       RETURNING n7'
[B]    Receiving n7
[B]    RETURNING n7
[B] Receiving n7
[B] RETURNING n9

Note there are five kinds of messages appearing here. The code added should be set up to handle each kind of message, and should not itself be customised just for the logging resulting from findSuccessor() execution.

The test1() method in the supplied DHNTest class includes code to generate the log records for the above examples. Comments in the test1() code indicate code to be uncommented to enable log record generation. As a first step, try enabling record generation and figure out how the provided code in the CNHandler and MonitorImp classes is generating the observed output.

The logging invocations in the ChordNodeImp class should not be touched when working on this task.

Task C: Checking that configurations are well formed

Extend the provided DHNTest with a static method

    private static void checkRing(DHNSlave d) throws RemoteException {}

that checks the ring pointed to by d is well formed. In particular it should check:

By following successor links, one eventually arrives back where one started.
The IDs in the ring only progress once through the possible range of values once as one traverses around the ring. For example, the sequence 4, 9, 5, 8, 1, 4 is a bad sequence of values for a ring with IDs in range 0..15, but 4, 5, 8, 9, 1, 4 is a good sequence of values.
The predecessor values are all correctly set.
The fingers are all correctly set.
Each key value pair is stored on the correct node.

Each property check should be done using a call to an appropriate static method of JUnit's Assert class. Use the versions of the methods that allow for brief messages to be inserted explaining what is being checked, and provide appropriate messages. The checks should not need to make use of methods such as findSuccessor() that do search in the ring. Indeed, use of such methods is unwise, given that they rely in the first place on the ring being properly configured.

Include a call to checkRing() everywhere you have a call to printRing() in your test1() method.

How to organise your work

The references to directories below all assume that your current directory is set to pt1, the main directory of the supplied set of files. See the Getting Started section below on how to obtain these files.
You should only need to make modifications to the source files DHNTest.java, MonitorImp.java and CNHandler.java. Please do not modify any other source files. Group your modifications together as much as possible, and use comments to clearly indicate the sections of code modified or added.
The test2() method in the DHNTest.java file is not relevant for Part 1, and should be deleted.
Add a run-pt1.txt file to the main directory describing how to compile and run your test on a DICE machine. This should provide explicit and detailed instructions on how to generate the output you supply in your log files. If you wish, you can try automating the running of your test using ant. If so, include a build.xml file in your pt1 directory. However, the use of ant is not required.
Please appropriately indent your code and keep your line lengths in text files at or below 80 characters. We won't be deducting marks if you don't do this, but it is in your interest, because it makes it easier to read and understand printouts. If possible, avoid using tab characters, because different editors and print routines don't always handle these in the same way.
See the Resources and Tools section of the main page for tips on using the indentation facilities of xemacs and how to eliminate tabs if you are already using them.

Assessment

Part 1 is worth 25% of the overall IP mark. The Part 1 mark will be based on 3 criteria:

Quality of documentation.
This documentation should be included in the Java file. Each method should be clearly documented and there should be some documentation introducing the block of methods for each task.
For Task C, you need to include a clear statement of the property that each check is checking.
Extent of working solution.
It should be clear that you have implemented what has been asked for. Your code should compile and run on a DICE machine following the instructions you supply.
Quality of implementation.
For example, how well have you structured your solutions for the tasks into distinct methods? How efficient are your solutions? In particular, please add a comment about the time complexity of your checks of each finger in Task C.

Marks for these criteria will be weighted 40%/40%/20% respectively.

Getting Started

Download the tar and gzipped file pt1.tgz to your working directory for this course. Ensure that only you can read the contents of this directory.
cd to this working directory and use tar xzvf pt1.tgz to unpack. This will create a subdirectory pt1 containing all the supplied files.
Consult pt1/README.txt for a summary of how files are arranged in directories and how to compile and run files. It is recommended that you check you can run the supplied code before starting on developing your own code.

Submission of Solutions

Each file you submit (whether a report file, Java file or some other kind) should include the following information on the first page.

Title of file / report including Task name
Your Examination Number

Your programs should compile and run on DICE machines with unmodified versions of all supplied source files, except those explicitly indicated above.

Please generate log files from runs of the main JUnit test, test1() in the DHNTest class. Provide log files part1-S.log and part1-A.log in the pt1 directory for tests in single-process (S) and multi-process automatic-startup (A) modes respectively. For example, use the command

java dhash.DHNTest A &> part1-A.log

to generate the A mode log, capturing both standard output and standard error streams.

Only submit the files you have created or modified.

Submission check list

Before submitting anything please check that you have followed all the instructions above. Failure to submit any of the necessary files or to include instructions on how to compile and run your program may result in marks being deducted. In particular, please ensure that:

Your code compiles and runs correctly under DICE from the command line (i.e. not just from within Eclipse or Netbeans etc.)
You have written explicit instructions on how to compile and run your code (under DICE) to produce the output you submit in your part1-S.log and part1-A.log files, saved these in a file called run-pt1.txt, and saved this file in the main pt1 directory.
- If you use ant you must inform us of this in run-pt1.txt, submit your build.xml file along with the rest of your work, and provide clear instructions on how to reproduce the output in your log files.
- If you don't use ant you may find it helpful to write a small shell script to compile and run your code. An example script is shown below. To turn this text into a shell script simply put it in a file, e.g. run-pt1.sh in your pt1 directory and do a chmod u+x run-pt1.sh to make the file executable. To run the script, type ./run-pt1.sh in your pt1 directory. If you use such a script to generate your log file then please submit it along with the rest of your work and tell us how to run it in the run-pt1.txt file.
```
#!/bin/bash
export CLASSPATH=src:test:lib/junit-4.4.jar:bin
javac -d bin test/dhash/DHNTest.java 
java dhash.DHNTest S &> part1-S.log
java dhash.DHNTest A &> part1-A.log
```
Do not edit the log files you provide - we will be checking that the logs exactly match the output we get when we run your program.
You have downloaded and completed an 'own work declaration' and included it in your submission

Submission

Save this Part 1 own work declaration form to file

  pt1/own-work-decl-ip-pt1.txt

and complete it.

If necessary, edit the file pt1/soln-files.lis which lists the files to be included in your submission. The supplied version of this file lists the files:

test/dhash/MonitorImp.java
test/dhash/CNHandler.java
test/dhash/DHNTest.java
run-pt1.txt
part1-S.log
part1-A.log
own-work-decl-ip-pt1.txt

With your current directory set to pt1, tar and gzip your files using a command similar to:

  tar cvzf pt1-soln.tgz -T soln-files.lis

Submit your tar file using the submit command:

   
  submit cs3 ip 1 pt1-soln.tgz

Revisions

27 Oct 08: Updated submission instructions to increase anonymity of submissions

Paul Jackson, Paul.Jackson (@) ed.ac.uk

Last modified: Mon Oct 27 15:47:18 GMT 2008

Home : Teaching : Courses : Ip