Building a Distributed Hash Table with Web Technologies

By Ethan Witherington

A distributed hash table is a kind of distributed technology – Many nodes work together to achieve a common goal. I find these distributed systems to be fascinating – each part is identical, but together, emergent properties arise. In this blog post, I’ll cover what they are, and how they work (to a good depth). After that, I’ll touch on how to implement a basic DHT using web technologies.

What is a Distributed Hash Table?

A Distributed Hash Table (DHT) is a data store operating across many networked computers. Rather than a single computer, a DHT shares the storage load across potentially millions of nodes. Each node stores only a small portion of the total data – working together, all the nodes of a DHT can store a lot of information.

What are DHTs used for?

The most famous DHT, the Mainline DHT, effectively adds tracker capabilities to each peer in the BitTorrent network. While centralized trackers are fallible, the distributed nature of the Mainline DHT makes it much harder to shut down.

DHTs can also be used for instant messaging, name resolution, and other styles of peer-to-peer file sharing.

Disadvantages

DHTs aren’t perfect. As we will learn in #Key-based Routing, it can take a few requests to find the node responsible for the data you are storing / retrieving. This means that DHTs can be slow. There are some design parameters we can tweak to mitigate this, but they are tradeoffs.

Nodes can join or leave a DHT at any time – we’ll cover this more in depth in churn. While DHT’s are designed to handle nodes leaving, enough neighboring nodes leaving at once can cause data loss.

Advantages

There are a few attributes that make DHTs stand out.

DHTs are highly scalable – the MainLine DHT consists of millions of nodes. Even at such huge numbers, data can still be stored and retrieved efficiently. We’ll learn how in Bootstrapping and Buckets.

Distributed and Self-healing – Nodes can cover the planet, and neighboring nodes are not likely to be geographically close to each other. Power outages, natural disasters, and other events cannot take out a large DHT. In order

How do DHTs work?

In order to behave as one system, every node needs to be able to store and retrieve data. However, not every node has every datapoint. The nodes need a way to identify themselves, each other, and what is stored where.

Keys and IDs

Each node of the DHT chooses a random ID. The node with the closest ID to the hash of a given piece of data is responsible for storing that data.

The hash function used determines the key space of the DHT. If the hash function is sha256, the key space is the set of all 256 bit (32 byte) strings. Each node’s ID must be randomly chosen from within the key space.

Say we have some data that hashes to 42. There are two nodes: 01 and 38. Since 38 is closer to 42, that node would be responsible for storing the data. If we ask node 1 to store it, and node 1 knows about node 38, then node 1 should refuse – or forward our request for us.

Nodes can have low IDs, high IDs, and anywhere in between. This can be thought of as a one-dimensional line.

Nodes laid out in a line

By declaring that IDs can ‘wrap-around’, we can now think of a DHT as a circle.

Nodes laid out in a circle

Randomly-selected IDs will lay the nodes out randomly around the circle.

Key-based routing

Since node IDs and data keys are within the same key space, we can define a distance function to find the distance between a datapoint and a node. XOR works well as a distance function because it is very easy to compute, and it fits the properties required:

  • The distance between anything and itself is zero
  • The distance from A to B to C is greater than or equal to the distance from A to C directly.

Nodes keep a list of known other nodes. When queried for a certain key, they can use the distance function to find which known node is closest to that key. Then, the node can recursively forward the request or direct the consumer to the closer node. This process continues until the desired data is found. This is called Key-based Routing.

This is the primary mechanism that DHT’s depend on. This is what allows any node to answer questions on any data, or ‘store’ data – by forwarding tasks to other nodes.

Like DNS, a DHT can operate recursively or non-recursively.

Non-recursive resolution

In a non-recursive setup, the client is responsible for finding the correct node for a given key – for either storing or retrieving. In english, a retrieve operation might look like this:

  1. Client: ‘Node 6, do you have key 48?’
  2. 6: ‘No, but 12 might’
  3. Client: ‘Node 12, do you have key 48?’
  4. 12: ‘No, but 53 might’
  5. Client: ‘Node 53, do you have key 48?’
  6. 53: ‘Yes, the value is “Hello World”’
A non-recursive query in the XX keyspace

Recursive resolution

In a recursive setup, nodes pass off requests to the closest known node to the desired key. In english, a retrieve operation might look like this:

  1. Client: ‘Node 6, Give me key 48’
  2. 6: ‘Node 12, Give me key 48’
  3. 12: ‘Node 53, Give me key 48’
  4. 53: ‘Node 12, Here’s key 48’
  5. 12: ‘Node 6, Here’s key 48’
  6. 6: ‘Client, here’s key 48’
A recursive query in the XX keyspace

Basic Functionality

In essence, there are four things a node will need to do:

  • store data
    • If the node is not responsible for this data, it can refuse or forward the request.
  • return data, for a given key
    • Once again, if a node does not have the data, it can refuse or forward.
  • store information about other nodes
    • This is required so that nodes can find closer nodes for any key they do not own
  • return information on closer nodes, for a given key
    • such that nodes can find other nodes
  • ping
    • so other nodes can tell that the node is still alive

Bootstrapping and Buckets

If each node had to store information about every other node, then DHTs with millions of nodes would require lots of resources. Instead, each node has ‘buckets’ – collections of other nodes at a certain distance.

A node may store the contact information for 10 others that are:

  • At least half ‘the circle’ away
  • At least a quarter-circle away
  • At least an eighth of the circle away
  • Closer than an eighth of the circle

As a result, nodes can relay to any node in their immediate neighborhood, but only a few that are far away – however, those far nodes will know about their own immediate neighborhood. As a result, a DHT can grow to millions of nodes without each node needing to know about every other.

The process that a node goes through when joining a DHT is called Bootstrapping. When starting, nodes need to know of at least one other node currently in the DHT that they can ask for information about the DHT. By querying for the closest node to their own ID, a bootstrapping node can start to learn about others.

If there is a distance bucket (remember: range of IDs) that the bootstrapping node has no information for, the bootstrapping node can query for a random ID in that range. When the DHT is small, there may be a bucket with no nodes in it.

We can visualize the buckets for node 5 in a DHT with 100 nodes, numbered 0 through 99:

Contact Buckets in a 0-99 DHT, for node 5

The bucket closest to the node in question, spans IDs 99 through 11 (remember, the keyspace wraps). This ensures that nodes know a high density of other nodes in their immediate neighborhood.

Meanwhile, the furthest bucket spans IDs 30 through 80 (that’s 50 IDs!).

Churn

Churn is the term for nodes joining and leaving the network. When nodes join, they take on some data-holding responsibilities. The network needs to be designed such that when a node leaves, their information is not lost.

The MainLine DHT experiences very high churn, as torrent clients join and leave very quickly. When building our DHT, we’ll use some of MainLine’s tricks to increase churn tolerance.

Building a Basic DHT with Web Technologies.

Nodejs and the express package enable us to build an API with only a few lines of code. With the node-fetch package, we can easily send http requests. By using these tools, we can quickly build a basic DHT.

To keep things simple, our DHT will be non-recursive – clients should use its find-node functionality to determine the right node to issue get/store commands to.

Boilerplate:

We’ll start with these files:

  • app.js – this will hold the express and http boilerplate.
  • config.json – this will hold configuration variables
  • endpoints.js – this will hold our API endpoints
  • services/ – this folder will hold files that implement core DHT functionality
    • neighbors.js – this will store info about other nodes
    • data.js – this will store data
  • bootstrapper.js – this will bootstrap our node

Data Storage: services/data.js

In this service file, we need to implement two things: Get and store. We’ll start with importing the crypto module (that we’ll need for calculating keys later), and declaring an internal _dataStore variable.

const crypto = require('crypto');

let _dataStore = {};

Next, let’s implement the store function. This will find the key of the data using sha256, and add it to the datastore.

function store(data){
    const key = crypto
        .createHash('sha256')
        .update(data)
        .digest('hex');

    _dataStore[key] = data;
}

Since we’re given the key on retrieval, the get(key) function is very simple.

function get(key){
    return _dataStore[key];
}

This will return undefined if the key isn’t in our datastore. Our endpoint layer will translate this to a 404 error later.

Finally, let’s export this functionality so the app can use it.

module.exports = {
    store,
    get
};

Neighbors: services/neighbors.js

This is another simple get/store file – in fact, it’s only 8 lines.

const _neighbors = [];

module.exports = {
    get: key => _neighbors.sort((a,b)=>a.id^key - b.id^key)[0],
    store: n => _neighbors.push(n)
};

The add function is simple. The get function takes a key, sorts the list of neighbors by their distance (XOR) to the key, and returns the closest one.

Our bootstrapper will take care of adding ourselves to the neighbors list.

Endpoints: endpoints.js

This is where we convert from HTTP requests to the service layer functionality we’ve already implemented, in addition to ping and self.

// The HTTP layer
const express = require('express');

// Our services
const data = require('./services/data.js');
const neighbors = require('./services/neighbors.js');

// Create the api router
const router = express.Router();

// Uploading Data: POST /data
router.post('/data', (request, response)=>{
    // add the data to the data store
    data.store(request.body);
    // Tell the client: victory!
    response.status(201).end(); // 201: created
});

// Retrieving data: GET /data/<data key here>
router.get('/data/:key', (request, response, next)=>{
    // Get that data!
    const payload = data.get(request.params.key);
    // Did we have the data?
    if(payload===undefined){
        // oh no!
        response.status(404).end();
    }else{
        // oh yeah!
        response.send(payload);
    }
});

// Storing neighbors that other nodes tell us about
router.post('/neighbor', (request, response)=>{
    neighbors.store(request.body);
    response.status(201).end(); // 201: created
});

// Getting the closest neighbor to a key
router.get('/neighbor/:key', (request, response, next)=>{
    const neighbor = neighbors.get(request.params.key);
    // There is guaranteed to be at least one - us!
    response.json(neighbor);
});

// Finally - Ping!
router.get('/ping', (request, response)=>{
    response.status(200).end();
});

// Export it so it can be used
module.exports = router;

Core: app.js

The app.js file stands up an express api HTTP server. There is not much unique about this file. It:

  • Creates a basic express server, defaulting to our router for endpoints
  • Handles and reports errors
  • Calls the bootstrapper when it’s ready
const config = require('./config');
const endpoints = require('./endpoints');
const bootstrapper = require('./bootstrapper');

const http = require('http');
const createError = require('http-errors');
const express = require('express');

async function createServer() {
    const app = express();

    // Add middlewares to parse requests
    app.use(express.json());
    app.use(express.urlencoded({extended: false}));

    // Define endpoints
    app.use('/', endpoints);

    // Default to a 404 error
    app.use((request, response, next) => {
        next(createError(404));
    });

    // Errors: Send them back.
    app.use((err, request, response, next) => {
        let status = err.status || 500;
        status = status < 500 ? status : 500;
        let message = err.message || 'Internal Server Error';
        message = status < 500 ? message : 'Internal Server Error';
        response.status(status).json({ok: false, message});
    });

    // Attach the http server to the express app
    const server = http.createServer(app);

    // Begin listening
    server.listen(()=>{
        // Determine our URI
        let self = server.address();
        let uri = self.family==='IPv4' ? `http://${self.address}:${self.port}` : `http://[${self.address}]:${self.port}`;
        console.log(`Server is listening on ${uri}`);
        bootstrapper.bootstrap(uri);
    });
}

createServer();

Configuration: config.js

This file is where we will store our bootstrap nodes, other configuration data that we may need, and our node ID. This is a js file instead of a json file so that the ID can be randomly generated on startup.

The first node doesn’t need any bootstrapping references, as it will be the only node. Later nodes will need to know about the first one in order to join it.

const crypto = require('crypto');
const nodeID = crypto.randomBytes(32).toString('hex');

module.exports = {
    nodeID,
    bootstraps: [
        // 'http://bootstrapping.server:port/',
    ]
};

Bootstrapper: bootstrapper.js

This is the glue that holds the DHT together. This is where we find other nodes and introduce ourselves to the network.

const fetch = require('node-fetch');

const neighbors = require('./services/neighbors');
const config = require('./config');

module.exports = {
    bootstrap: (uri)=>{
        // Step 1 - Add ourself to our neighbor list.
        neighbors.store({
            id: config.nodeID,
            uri
        });

        // Step 2 - Announce / add all bootstrappers.
        config.bootstraps.forEach(uri=>{
            // Get their ID, and add them
            fetch(uri+'id')
                .then(response=>response.text)
                .then(id=>{
                    neighbors.store({
                        id,
                        uri
                    });
                });
            // Let them know about us
            fetch(
                uri+'neighbors',
                {
                    method: 'POST',
                    body: JSON.stringify(
                        neighbors.get(config.nodeID)
                    )
                }
            );
        });
    }
};

Opportunities for Improvement

Before using this proof-of-concept DHT, there are some safety features that should be added. To prevent against malicious nodes, the schema returned from neighboring nodes should be checked. Finally, this DHT is missing a critical feature: churn tolerance. While new nodes will announce themselves, and will start taking storage requests from clients, there is no redundancy.

  • The neighbors.js file should implement timers to check that neighbors are still up
  • The neighbors.js file should perform queries against neighbors to fill gaps in the address book
  • When a node stores data, it should send a store request to its neighbors for redundancy.

And with that, I hope I’ve inspired some interest in the workings of distributed hash tables, or distributed systems in general. Thank you.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s