Project 2: Chord Distributed Hash Table

Introduction

In this assignment, you will implement a basic CHORD distributed hash table (DHT) as described in this paper:

You can download my Linux implementation to play with:

Save the file as chord-sol and make it executable (Linux/OS X):

chmod 755 chord-sol

Then launch it using:

./chord-sol

Requirements

Your DHT must implement the services to maintain a DHT, and it must support a simple command-line user interface. Each instance (running on different machines, or on the same machine on different ports) will run an RPC server and act as an RPC client. In addition, several background tasks will run to keep the DHT data structures up-to-date.

User interface

When running, an instance of your DHT should support a simple command-line interface. It will supply a prompt, and the user can issue one of the following commands. The simplest command is:

The main commands start with those related to joining and leaving DHT rings:

Next, there are those related to finding and inserting keys and values. A <key> is any sequence of one or more non-space characters, as is a value.

Finally, there are operations that are useful mainly for debugging:

Of these, dump is the most helpful and is required. The others may prove helpful in debugging, but they are optional.

DHT interface

When communicating with other DHT nodes, your DHT should use the basic operations described in the paper, including finger tables. You should implement a successor list as described in the paper, and basic migration of key/value pairs as nodes join and leave. Details are given later in this document.

There are a few different basic types of values that you will need to work with. For node addresses, use a string representation of the address in the form address:port, where address is a dotted-decimal IP address (not a host name). When referring to positions on the ring (ring addresses), you will be using a large number, not a string. This works out nicely: keys and node addresses are strings, and both can be hashed into ring addresses, which are not strings. The type checker will make sure you never mix up the two types of addresses.

You will use the sha1 hash algorithm (available in crypto/sha1 in the Go standard library), which gives 160-bit results. This means that your finger table will have up to 160 entries. In order to treat these as large integer operations and perform math operations on them, you will need to use the math/big package. I recommend immediately converting sha1 hash results into big values and using that as your type for ring addresses.

Each node will need to maintain the following data structures as described in the paper:

Note that addresses should contain an IP address and a port number.

The main operations you must support are:

Each of these is described in the pseudo-code in the paper. You must also incorporate the modifications described in the paper to maintain a list of successor links instead of a single successor value.

Suggestions

The following are implementation suggestions, which you are free to follow or ignore.

Goroutines

RPC connections

The number and locations of peers will vary over time. For a production system, you would maintain a pool of outgoing connections and garbage collect connections over time.

To make things simpler, establish a fresh RPC connection for each message you send, wait for the response, then shut down that connection. You may find it helpful to write a function like this:

func call(address string, method string, request interface{}, reply interface{}) error

This function takes care of establishing a connection to the given address, sending a request to the given method with the given parameters, then closes the client connection and returns the result.

It is okay to make all of your requests synchronously, i.e., the goroutine that sends the request can stop and wait until the response is available.

Iterative lookups

Use the iterative style of recursive lookups as described in the paper. All RPC calls will be able to return values immediately without blocking, i.e., every RPC server function queries or modifies local data structures without having to contact other servers.

The most complicated operation you must support is a complete find_successor lookup that may have to contact multiple servers. It should start by checking if the result can be found locally. If not, it should enter a loop. In each iteration, it contacts a single server, asking it for the result. The server returns either the result itself, or a forwarding address of the node that should be contacted next.

Put in a hard-coded limit on the number of requests that a single lookup can generate, just in case. Define this as a global, named constant. 32 ought to be sufficient for hundreds of nodes.

Hash functions

To get a sha1 hash value, include the appropriate libraries and use something like this:

func hashString(elt string) *big.Int {
    hasher := sha1.New()
    hasher.Write([]byte(elt))
    return new(big.Int).SetBytes(hasher.Sum(nil))
}

Now you can use the operations in math/big to work with these 160-bit values. It is a bit cumbersome because you cannot use infix operators. For example, the following is helpful:

const keySize = sha1.Size * 8
var two = big.NewInt(2)
var hashMod = new(big.Int).Exp(big.NewInt(2), big.NewInt(keySize), nil)

func jump(address string, fingerentry int) *big.Int {
    n := hashString(address)
    fingerentryminus1 := big.NewInt(int64(fingerentry) - 1)
    jump := new(big.Int).Exp(two, fingerentryminus1, nil)
    sum := new(big.Int).Add(n, jump)

    return new(big.Int).Mod(sum, hashMod)
}

This computes the address of a position across the ring that should be pointed to by the given finger table entry (using 1-based numbering).

Another useful function is this:

func between(start, elt, end *big.Int, inclusive bool) bool {
    if end.Cmp(start) > 0 {
        return (start.Cmp(elt) < 0 && elt.Cmp(end) < 0) || (inclusive && elt.Cmp(end) == 0)
    } else {
        return start.Cmp(elt) < 0 || elt.Cmp(end) < 0 || (inclusive && elt.Cmp(end) == 0)
    }
}

This one returns true if elt is between start and end on the ring, accounting for the boundary where the ring loops back on itself. If inclusive is true, it tests if elt is in (start,end], otherwise it tests for (start,end).

Getting your network address

It is helpful to have your code find its own address. The following code will help:

func getLocalAddress() string {
    var localaddress string

    ifaces, err := net.Interfaces()
    if err != nil {
        panic("init: failed to find network interfaces")
    }

    // find the first non-loopback interface with an IP address
    for _, elt := range ifaces {
        if elt.Flags&net.FlagLoopback == 0 && elt.Flags&net.FlagUp != 0 {
            addrs, err := elt.Addrs()
            if err != nil {
                panic("init: failed to get addresses for network interface")
            }

           for _, addr := range addrs {
                if ipnet, ok := addr.(*net.IPNet); ok {
                    if ip4 := ipnet.IP.To4(); len(ip4) == net.IPv4len {
                        localaddress = ip4.String()
                        break
                    }
                }
            }
        }
    }
    if localaddress == "" {
        panic("init: failed to find non-loopback interface with valid address on this node")
    }

    return localaddress
}

It finds the first address that is not a loopback device, so it should be one that an outside machine can connect to. If you have multiple devices or multiple IP addresses, it will choose one arbitrarily. It may even pick an IPv6 address.

Implementation order

Week 1

Week 2

At this point, you should have complete functionality as long as there are no failures.

Week 3

To handle failures, you need to keep a successor list. This is a suprisingly easy extension, and makes for a much more satisfying result.

Your ring should now tolerate node failures. All that is left is to manage migrating key/value pairs around the ring as nodes join and leave. This is also relatively easy:

This should give you full functionality.

Last Updated 05/31/2017