Consistent Hashing in JavaScript (NodeJS)

Consistent hashing is a technique widely used in distributed systems to achieve load balancing and maintain data distribution across nodes efficiently. In this blog post, we’ll explore a basic implementation of consistent hashing in Node.js.

Background

Consistent hashing addresses the challenge of redistributing data when the number of nodes in a distributed system changes. Traditional hashing techniques can lead to significant data migration when nodes are added or removed. Consistent hashing minimizes this impact, providing a more scalable and efficient solution.

The Implementation

Let’s delve into a simple implementation of consistent hashing using Node.js. The code includes classes for StorageNode and ConsistentHashing, along with functions for adding and removing nodes, as well as assigning items to nodes.

const crypto = require("crypto");

class StorageNode {
  constructor(name, host) {
    this.name = name;
    this.host = host;
  }

  putFile(path) {
    // Implementation for putting a file on the node
    console.log(`File ${path} stored on node ${this.name}`);
  }

  fetchFile(path) {
    // Implementation for fetching a file from the node
    console.log(`File ${path} fetched from node ${this.name}`);
  }
}

class ConsistentHashing {
  constructor(totalSlots) {
    this.totalSlots = totalSlots;
    this.nodes = [];
    this.keys = [];
  }

  hashFn(key) {
    const hash = crypto.createHash("sha256").update(key, "utf-8").digest("hex");
    return parseInt(hash, 16) % this.totalSlots;
  }

  addNode(node) {
    if (this.keys.length === this.totalSlots) {
      throw new Error("Hash space is full");
    }

    const key = this.hashFn(node.host);
    const index = this.keys.findIndex((k) => k > key);

    if (index > 0 && this.keys[index - 1] === key) {
      throw new Error("Collision occurred");
    }

    this.nodes.splice(index, 0, node);
    this.keys.splice(index, 0, key);

    return key;
  }

  removeNode(node) {
    if (this.keys.length === 0) {
      throw new Error("Hash space is empty");
    }

    const key = this.hashFn(node.host);
    const index = this.keys.findIndex((k) => k === key);

    if (index === -1) {
      throw new Error("Node does not exist");
    }

    this.keys.splice(index, 1);
    this.nodes.splice(index, 1);

    return key;
  }

  assign(item) {
    const key = this.hashFn(item);
    const index = this.keys.findIndex((k) => k > key) % this.keys.length;

    return this.nodes[index];
  }
}

// Example usage
const consistentHashing = new ConsistentHashing(5);

const nodes = [
  new StorageNode("A", "10.131.213.12"),
  new StorageNode("B", "10.131.217.11"),
  new StorageNode("C", "10.131.142.46"),
  new StorageNode("D", "10.131.114.17"),
  new StorageNode("E", "10.131.189.18"),
];

nodes.forEach((node) => consistentHashing.addNode(node));

const fileToUpload = "example.txt";
const assignedNode = consistentHashing.assign(fileToUpload);
assignedNode.putFile(fileToUpload);

Usage Example

The implementation is exemplified with a scenario involving storage nodes A, B, C, D, and E. Files are uploaded to nodes based on the consistent hashing algorithm, ensuring a balanced distribution.

// Upload a file to the assigned node
const fileToUpload = "example2.txt";
const assignedNode = consistentHashing.assign(fileToUpload);
assignedNode.putFile(fileToUpload);

Conclusion

Consistent hashing is a crucial concept in distributed systems, offering an elegant solution to the challenges of data distribution and load balancing. The provided Node.js implementation serves as a foundation for understanding and integrating consistent hashing into your own projects.