howto
Chord HOWTO
This document describes how to build and run the Chord/DHash server. The source code consists of several main components:
- The Chord library: This provides the basic functionality of Chord. It maintains routing tables
and is able to evaluate
find_successor. Depends on the SFS libraries for RPC services. - The DHash library:
libdhashandlibdhashclientimplement DHash, the algorithms that handle the storage of blocks in a Chord network. Depends on the SFS libraries and the Chord library. There are also support libraries (libutilandlibmerkle). - The DHash server (
lsd): lsd is the daemon which implements the Chord and DHash protocols. Depends on the Chord and DHash libraries as well as the SFS libraries.
For more information, see also:
Chord runs on any system that supports SFS. This includes Linux, FreeBSD, OpenBSD, Solaris. Macintosh OS X and NetBSD may work as well.
Chord is based on SFS and the SFSlite toolkit. For Chord versions
before October 2006, your best bet is to use full SFS (to support
chordcd and CFS. For versions of Chord after October 2006,
you must use SFSlite 0.8.13 or newer. For code written after March 2007,
you must use SFSlite 0.8.16pre1 or newer.
You can link against an installed version (e.g., from FreeBSD ports) or
a build-tree directly.
Obtain SFSlite either as a source tar ball or as a package. To
build from source, you must configure with --with-sfsmisc. Note
that if you wish to use dmalloc to debug
your Chord programs, you must build a local copy of SFSlite
--with-dmalloc enabled.
To build SFSlite you'll need a few tools:
- A recent GCC (4.0ish works well).
- autoconf, automake, GNU make, etc.
You'll probably want to do an "out of place" build, summarized here:
- create a build directory
- run the
configurescript located in the source directory from the build directory - type
gmake(ormake).
This might look something like this:
% cd ~/src/sfslite-0.8.16pre1
% mkdir ~/build/sfslite
% cd ~/build/sfslite
% ~/src/sfslite-0.8.16pre1/configure --with-sfsmisc
creating cache ./config.cache
checking for a BSD compatible install... /usr/bin/install -c
checking whether build environment is sane... yes
checking whether make sets ${MAKE}... yes
checking for working aclocal... found
checking for working autoconf... found
checking for working automake... found
checking for working autoheader... found
...
% gmake
SFSlite should build in about 10 minutes. If your home-directory
is served from a network file system (e.g. NFS, SFS, AFS), you will
probably want to build on a local disk (e.g. /scratch or
/var/tmp) instead of in $HOME.
The Chord source is available in via Git at /~https://github.com/sit/dht or from one of the periodic snapshots. To obtain the latest snapshot from Mercurial, just run
% git clone git://github.com/sit/dht chord-0.1
Once you have cloned the entire history, you can select any version you like; for example, the version closest approximating the version used by OverCite:
% cd chord-0.1
% git checkout 9ab9b473afd75ea254a9671df9dd38ee61a95262
should give you the same source as the 20060902 snapshot.
The Chord build process is based on automake.
- Berkeley DB v4.x from http://www.sleepycat.com/
- Gtk2 (if you want to build vis)
We'll demonstrate an out of place build here as well:
% cd src/chord-0.1
% ./setup # not needed if you are building from a snapshot
+ gm4 svc/Makefile.am.m4 > svc/Makefile.am
+ chmod +x setup
+ aclocal
+ autoheader
+ automake --add-missing
...
% mkdir ~/build/chord
% cd ~/build/chord
% ~/src/chord-0.1/configure --with-dmalloc --with-sfs=../sfslite
creating cache ./config.cache
checking for a BSD compatible install... /usr/bin/install -c
checking whether build environment is sane... yes
checking whether make sets ${MAKE}... yes
checking for working aclocal... found
checking for working autoconf... found
checking for working automake... found
checking for working autoheader... found
checking for working makeinfo... found
checking host system type... i386-unknown-freebsdelf4.3
checking for gcc... gcc
checking whether the C compiler (gcc ) works... yes
checking whether the C compiler (gcc ) is a cross-compiler... no
checking whether we are using GNU C... yes
% gmake
If you have problems, please see the FAQ.
The Chord daemon is named lsd. lsd takes a bevy of confusing
options on the command line. Run it with no options just to make
sure the build went right:
% lsd/lsd
Usage: lsd -j hostname:port -p port
Options:
DHash/Chord configuration:
[-v <number of vnodes>]
[-l <locally bound IP>]
[-m successors|chord|pns|pnsrec|...]
[-s <server select mode>]
Control sockets:
[-d <adbd socket path>]
[-S <dhashgateway sock path>]
[-C <lsdctl sock path>]
Misc configuration:
[-D] # Daemonize
[-H <heartbeatfile>]
[-L <warn/fatal/panic output file name>]
[-t] # Enable trace logging
[-T <trace file name (aka new log)>]
[-O <config file>]
The most important ones are:
| Option | Meaning |
|---|---|
| -j hostname:port | the location of a running node; used to bootstrap |
| -p port | listen on UDP port and TCP port + 1 |
| -v nvnodes | Create nvnodes virtual nodes in a single process |
| -l ipaddress | listen on the specified local address; useful for multihomed hosts |
| -m mode | Use the selcted routing mode (variants of Chord) |
To run Chord/DHash, you should use the lsd/start-dhash script. This
script was introduced in October 2005 to simplify the process of
starting the supporting daemons used by lsd, the main Chord/DHash
process. These include adbd (introduced Summer 2005), syncd
(introduced Spring 2005 and obsoleted Winter 2006), and maintd
(introduced in Winter 2006 to replace syncd). Earlier versions of
lsd performed the functions of all these helpers internally but long
delays due to disk I/O necessitated these separate programs.
You can pass start-dhash the same options as lsd would take.
start-dhash configures all the other options to sandbox all
of the relevant log files and control sockets in a single directory.
When a node joins a Chord network, it must contact a well-known, or bootstrap
node. Any node, once running, can serve as a bootstrap node. However, the first
node run as part of a Chord network must bootstrap itself. All this really
means is that when starting the node one must specify a port (rather than
letting Chord choose one) and set the bootstrap node to itself. The following
example illustrates this process as it might be run on a machine
called sure.lcs.mit.edu.
The important fact to note is that this node has specified a
port number and specified itself (:10000) as the bootstrap
node.
% ~/src/chord-0.1/lsd/start-dhash --root dhash-a -j sure.lcs.mit.edu:10000 -p 10000 &
RUNNING: lsd/adbd adbd -d ./db -S ./adbd-sock
RUNNING: maint/maintd maintd -d ./maintdata -m carbonite -C ./maint-sock
RUNNING: lsd/lsd lsd -d ./adbd-sock -S ./dhash-sock -R ./maint-sock -C ./lsd-sock -j sure.lcs.mit.edu -p 10000
% tail -f dhash-a/log.lsd
lsd: lsd starting up at Wed Apr 18 13:18:43 2007
lsd: running with options:
lsd: IP/port: 127.0.0.1:10000
lsd: vnodes: 1
lsd: lookup_mode: 1
lsd: ss_mode: -1
1176916725:875838 9173f7cbbc4f426392eca75f3a45781d292f69c2: stabilize: stable! stabilize timer 1000
When starting additional (non-bootstrap nodes) the port argument is optional,
and the address of a running node should be specified after the -j parameter.
If no port is specified, lsd will choose an unused port.
% ~/src/chord-0.1/lsd/start-dhash --root dhash-b -j sure.lcs.mit.edu:10000 &
N.B.: DHash uses erasure coding of objects by default. As a result, in its default configuration, 16 nodes (virtual or otherwise) must be present in the system to allow blocks to be inserted successfully.
The easiest way to exercise DHash is with the synthetic client dbm, located
in the tools directory of the source tree. dbm was used to generate the
performance numbers presented in the CFS paper. dbm sports a less than
advanced command parser. It's arguments must be given in order and all are
mandatory. To see the usage just call "tools/dbm". Here's an example of using dbm:
% tools/dbm dhash-a/dhash-sock store chash 128 8192
This will store 128 8K blocks into the Chord system and print the results (just the elapsed time in this case) to standard out. Here is a more exciting example:
% tools/dbm dhash-a/dhash-sock fetch chash 128 8192 nops=10 seed=2
This asks the first virtual node to fetch 128 8K blocks using "2" as the random seed to generate the blocks and to run 10 simultaneous lookups. The results will be printed to standard out. If you actually run this command you will see a series of error messages since the blocks generated by random seed 2 were never inserted.
You may want to view the state of your Chord ring to better understand its
properties. In order to make this easier, we provide a visualization tool:
vis. The vis tool requires GTK. If your GTK is installed in a
non-standard location you may have to specify the prefix using
--with-gtk-prefix configure option.
vis takes the same command line join arguments as lsd. To run vis point it at any node in the system:
./vis -j sure.lcs.mit.edu:10000 [-a sec] [-f color file]
The optional arguments specifiy the auto-update frequency in milliseconds (-a) and the a file mapping latencies to colors (-f).
You should see a display like the one pictured below:
In this example, the fingers of a single node are shown. To show information other than fingers, depress the corresponding button on the right. To toggle whether or not a node is drawn, click on it. The "show all" and "show none" buttons are a shortcut for toggling the drawn state of all nodes on or off. The refresh button will update the display by re-querying the nodes in the network; if a node is not reachable the display may not update until a 10 second timeout interval has occurred.