Authors: Caleb Carlson, Menuka Warushavithana
Team-based implementation of Chord's Peer-to-Peer Distributed Hashtable (DHT) written in Java, to complete CS555: Distributed Systems' Assignment 2 (click link to view description). Implementation includes Peers, a Discovery Node, and a Client. Requests are managed using a thread-per-request threading model, and a custom Socket-based messaging implementation with messages marshalled/unmarshalled into efficient byte structures.
Decentralized and responsible for the actual storage of data items. Organized into a ring configuration, per Chord's specification. Each Peer maintains information about the data stored, their successor Peer, and their predecessor Peer. Also maintains a Finger Table, as discussed below:
Contains exactly 16 entries. Each entry i in the Finger Table for Peer p is the ID and IP address of the successor(2^(i-1) + p). For example, entry i = 3 in the Finger Table for Peer p = 16,000 would be the successor Peer of the 2^(2) + 16,000 = 16,004th position in the ring. This Finger Table is dynamically updated with new nodes joining and leaving the network.
A request for the true successor of ID k is satisfied by either the current Peer, if it is the successor of k, or if it knows the true successor of k. If it does not know the true successor of k in the ring, it forwards the request to the closest Peer p' to k such that p' < k.
Data items with an ID strictly less than or equal to our Peer ID can be stored locally.
Responsible for keeping track of Peer IP addresses and their identifiers, so that one can be used at random as an entry-point to the DHT. Not a critical component of the system, but acts like trackers do in other distributed networks-- a discovery service.
Every time a peer joins the network, it reaches out to the Discovery Node, and the Discovery Node returns the network information of a random peer that is currently being tracked. The random selection of a node provides a basic load-balancing mechanism. Once a random peer is selected, its hostname/IP address is returned to the Peer requesting to join the network. This allows a Peer to get in contact with an existing Peer in the ring.
Responsible for interacting with the Peers directly to store/retrieve data items.
16 bits, allowing for up to 2^16 = 65,535 unique values. Represented as a 4-digit hex value. Computed as a digest of each data item that is stored in the DHT. This digest determines where in the ring (which Peer) the data item is stored. The first Peer in the ring that has an ID p greater than or equal to the ID of the data item k is the Peer responsible for storing that data item.
Note: The Discovery Server, Peer, and Client (store-data) are all interactive and take STDIN once spun up.
Using the Makefile:
- Clean the previous build:
make clean - Recompile and build the project:
make build - Run the Discovery Server:
make discovery - Run a Peer:
make peer DISCOVERY=<discovery_server_hostname> ID=<peer_id> - Store data:
make store-data DISCOVERY=<discovery_server_hostname>
make discovery(on arkansas.cs.colostate.edu)
make peer DISCOVERY=arkansas ID=83d8make peer DISCOVERY=arkansas ID=f5c5make peer DISCOVERY=arkansas ID=1e4amake peer DISCOVERY=arkansas ID=fffemake peer DISCOVERY=arkansas ID=1539
- FileDir:
./test-data
| FileName | Digest |
|---|---|
| img1.jpg | 1714 |
| img2.jpg | 608c |
| img3.jpg | 6c8e |
| img4.jpg | ec5d |
| img5.jpg | 9783 |
| img6.jpg | 8640 |
| img7.jpg | d687 |
| img8.jpg | 505c |
| img9.jpg | 34dd |
| img10.jpg | d0d1 |
make store-data DISCOVERY=arkansas> add-file test-data/img1.jpg