Build a Consistent Hashing Ring

Build a hash ring in JavaScript to route keys across distributed servers.

Introduction

30 Second Summary

Every time you use a streaming service or shop online, your request gets routed to one of many servers. But what happens when a server goes down or a new one joins the cluster?

In this project, you will build a consistent hashing ring in JavaScript to understand how distributed systems like DynamoDB and Memcached route keys to servers with minimal data movement when the cluster topology changes.

What You'll Build

A complete consistent hashing system in JavaScript that simulates how distributed caches route keys to servers.

By the end of this project, you'll have:

  • A working naive modulo hash that demonstrates why simple hashing catastrophically fails at scale.
  • A HashRing class with virtual nodes and O(log n) binary search lookup for key-to-node routing.
  • A test harness that compares key redistribution between naive and consistent hashing with statistical output.
  • Secret Mission: Add bounded-load consistent hashing that caps any single node at 1.5x the average load.

Are there any prerequisites?

This project assumes basic JavaScript knowledge (functions, classes, arrays) and familiarity with running scripts in a terminal.

No external packages are required. Everything uses the built-in Node.js crypto module.

Before We Start

Before We Start...

Set Up Your Environment

Before you can build a consistent hashing ring, you need a working Node.js environment and a project folder to hold your code.

This step gets your machine ready by installing Node.js, creating a project directory, and initializing it with npm.

In this step, get ready to:
  • Install and verify Node.js v22 LTS.
  • Create and initialize a project folder.
  • Open the project in VS Code.
Install Node.js

Node.js is a JavaScript runtime that lets you run JavaScript outside the browser. This project uses Node.js v22 LTS for its built-in crypto module and modern JavaScript support.

  • Open a terminal by pressing Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
  • Type Terminal (macOS) or Command Prompt (Windows) and press Enter to open it.
  • Check your Node.js version by running this command:
node --version

Check which tab matches what you see in your terminal.

✔️ I see version 22 or higher

Your output looks something like v22.x.x. Node.js is ready to go.

  • Confirm npm is also available by running:
npm --version

You should see a version number like 10.x.x. Both tools are ready.

ⓧ I see an older version

You have Node.js installed but it is below version 22. You need to upgrade to v22 LTS.

  • Visit https://nodejs.org and download the v22 LTS installer for your operating system.
  • Run the installer. It will replace your existing Node.js version.
  • Close and reopen your terminal so it picks up the new version.
  • Run node --version again to confirm the output starts with v22.

Why not just use my current version?

This project uses the node:crypto module prefix, which requires Node.js 16 or later. Version 22 LTS gives you long-term stability and support for all the features used in this project.

ⓧ Command not found

Node.js is not installed on your machine yet.

  • Visit https://nodejs.org and download the v22 LTS installer for your operating system.
  • Run the installer and follow the prompts. Accept the default settings.
  • Close and reopen your terminal so it picks up the new installation.
  • Run node --version again to confirm the output starts with v22.

Still not seeing the right version?

On macOS, if you previously installed Node.js via Homebrew, it may be shadowing the new installation. Run which node to check which binary your terminal resolves to.

On Windows, make sure you checked the option to add Node.js to PATH during installation. If you missed it, run the installer again and select Repair.

Help me troubleshoot my Node.js installation.

Create your project folder

Now that Node.js is ready, you need a dedicated folder for the project files.

  • Move to your Desktop by running this command:
cd ~/Desktop
  • Create your project folder and move into it by running these commands:
mkdir consistent-hashing
cd consistent-hashing
  • Initialize a Node.js project by running:
npm init -y

What does this command do?

The npm init -y command creates a package.json file with default values. This file identifies your folder as a Node.js project and tracks any future dependencies.

  • Confirm the file was created by running:
ls

You should see package.json listed in the output.

  • Open the project in VS Code by running:
code .

Getting 'command not found' for code?

On macOS, you need to install the shell command manually. Open VS Code from your Applications folder, press Cmd+Shift+P to open the Command Palette, type shell command, and select Shell Command: Install 'code' command in PATH. Restart your terminal and try again.

On Windows, the VS Code installer adds code to your PATH by default. If it was not added, reinstall VS Code and check the Add to PATH option.

Help me get the code command working in my terminal.

VS Code opens with your consistent-hashing folder in the Explorer sidebar. You should see package.json listed.

✔️ Awesome, I've got everything!

Great. Double check you see package.json in the VS Code Explorer sidebar and you are ready for the next step.

ⓧ I'd like to double check the full code

Your package.json should look like this:

{
  "name": "consistent-hashing",
  "version": "1.0.0",
  "main": "index.js",
  "scripts": {
    "test": "echo \"Error: no test specified\" && exit 1"
  },
  "keywords": [],
  "author": "",
  "license": "ISC",
  "description": ""
}

The exact values for name and description may vary slightly depending on your npm version. The important thing is that the file exists.

Your environment is ready. Next up, you will build naive modulo hashing to see exactly why distributed systems need something better.

Build Naive Modulo Hashing

Your environment is ready. Now let's understand why consistent hashing exists by first building the algorithm it replaces.

Most distributed caches start with a simple idea: hash the key, then use modulo to pick a server. This works perfectly until the number of servers changes. In this step, you'll implement naive modulo hashing and watch it break when you add a single server.

In this step, get ready to:
  • Create a hash() function that converts strings into numeric positions using SHA-256.
  • Build a NaiveHash class that assigns keys to servers using modulo arithmetic.
  • Demonstrate how adding a single server remaps approximately 75% of keys.
Create the naive hash module

We need a way to turn any string key into a numeric value, then assign it to one of N servers. The simplest approach is hash(key) % N to pick a server index.

  • Create a new file called naive-hash.js in your consistent-hashing folder.
  • Add the hash utility function by pasting this code into the file:
const { createHash } = require('node:crypto');

// Turn any string key into a numeric hash value
function hash(key) {
  return parseInt(
    createHash('sha256').update(key).digest('hex').slice(0, 8),
    16
  );
}

What does this code do?

  • require('node:crypto') imports Node.js's built-in cryptography module. No external packages needed.
  • createHash('sha256').update(key).digest('hex') produces a 64-character hex string from any input.
  • .slice(0, 8) takes the first 8 hex characters, giving a 32-bit range (0 to 4,294,967,295).
  • parseInt(..., 16) converts that hex substring into a regular number we can do math on.
  • Save naive-hash.js.
  • Confirm the file exists by running:
ls
  • You should see naive-hash.js and package.json in the output.

Don't see naive-hash.js?

  • Make sure your terminal is inside the consistent-hashing folder. Run pwd to check your current directory.
  • If you created the file from VS Code, confirm it was saved in the project root and not inside a subfolder.

Why isn't my file showing up in the terminal?

Now add the class that uses this hash function to assign keys to servers.

  • Add the NaiveHash class below the hash function in naive-hash.js:
class NaiveHash {
  constructor(nodes) {
    // Store a copy of the server list
    this.nodes = [...nodes];
  }

  getNode(key) {
    // Hash the key and pick a server by index
    const h = hash(key);
    const index = h % this.nodes.length;
    return this.nodes[index];
  }

  addNode(node) {
    this.nodes.push(node);
  }

  removeNode(node) {
    this.nodes = this.nodes.filter(n => n !== node);
  }
}

What does this class do?

  • constructor(nodes) stores a copy of the server list.
  • getNode(key) hashes the key and uses modulo to pick a server index. This is the core of naive hashing.
  • addNode and removeNode change the server list. When the list length changes, the modulo result changes for almost every key.
  • Save naive-hash.js.
  • You won't see any output yet. The next chunk adds a demonstration that runs this class.

Seeing a syntax error later?

If you get an error when you run the file in the next substep, check that the class sits below the hash function (not inside it). The closing brace of hash should appear before class NaiveHash.

Help me fix a syntax error in my naive-hash.js file.

Demonstrate the redistribution catastrophe

Time to prove the problem. You'll assign 100 keys to 3 servers, then add a 4th server and count how many keys get reassigned.

  • Add the demonstration script below the class in naive-hash.js:
// --- Demonstration ---
const servers = ['server-A', 'server-B', 'server-C'];
const naive = new NaiveHash(servers);

// Assign 100 keys with 3 servers
const keysBefore = {};
for (let i = 0; i < 100; i++) {
  const key = `user:${i}`;
  keysBefore[key] = naive.getNode(key);
}

// Add a 4th server
naive.addNode('server-D');

// Recalculate and count moves
let moved = 0;
for (let i = 0; i < 100; i++) {
  const key = `user:${i}`;
  const newNode = naive.getNode(key);
  if (newNode !== keysBefore[key]) {
    moved++;
  }
}

console.log('=== Naive Modulo Hashing ===');
console.log(`Keys total: 100`);
console.log(`Keys moved after adding 1 server: ${moved} (${moved}%)`);
console.log(`Expected: ~75% redistribution\n`);

module.exports = { NaiveHash, hash };

What does this demonstration do?

  • Creates 3 servers and assigns 100 keys using modulo hashing.
  • Records which server each key maps to before any change.
  • Adds a 4th server, which changes the modulo divisor from 3 to 4.
  • Recalculates every key's assignment and counts how many moved to a different server.
  • module.exports makes the NaiveHash class and hash function reusable in later files.
  • Save naive-hash.js.
Run and observe the output
  • Run the script to see the redistribution problem in action:
node naive-hash.js
  • You should see output showing that approximately 75 out of 100 keys moved after adding just one server.

Why is 75% redistribution a disaster?

Imagine each key is a cached user session. Remapping 75% of keys means 75% of your cache is instantly invalid. Every one of those requests hits your database instead of the cache. In production, this causes a cache stampede that can take down your entire system.

The mathematical reason is simple. With N servers, hash(key) % N and hash(key) % (N+1) produce the same result only when both remainders happen to match. For large key sets, about N/(N+1) keys move. Going from 3 to 4 servers means ~75% redistribution.

Seeing an error instead of output?

  • A SyntaxError usually means a missing brace or misplaced comma. Check that each opening { has a matching }.
  • If you see ReferenceError: hash is not defined, make sure the hash function appears above the NaiveHash class in the file.
  • If you see ReferenceError: NaiveHash is not defined, make sure the class appears above the demonstration section.

Help me debug my naive-hash.js file.

✔️ Awesome, I've got everything!

Great. Double check you've saved your file before moving on.

ⓧ I'd like to double check the full code

const { createHash } = require('node:crypto');

function hash(key) {
  return parseInt(
    createHash('sha256').update(key).digest('hex').slice(0, 8),
    16
  );
}

class NaiveHash {
  constructor(nodes) {
    this.nodes = [...nodes];
  }

  getNode(key) {
    const h = hash(key);
    const index = h % this.nodes.length;
    return this.nodes[index];
  }

  addNode(node) {
    this.nodes.push(node);
  }

  removeNode(node) {
    this.nodes = this.nodes.filter(n => n !== node);
  }
}

// --- Demonstration ---
const servers = ['server-A', 'server-B', 'server-C'];
const naive = new NaiveHash(servers);

// Assign 100 keys with 3 servers
const keysBefore = {};
for (let i = 0; i < 100; i++) {
  const key = `user:${i}`;
  keysBefore[key] = naive.getNode(key);
}

// Add a 4th server
naive.addNode('server-D');

// Recalculate and count moves
let moved = 0;
for (let i = 0; i < 100; i++) {
  const key = `user:${i}`;
  const newNode = naive.getNode(key);
  if (newNode !== keysBefore[key]) {
    moved++;
  }
}

console.log('=== Naive Modulo Hashing ===');
console.log(`Keys total: 100`);
console.log(`Keys moved after adding 1 server: ${moved} (${moved}%)`);
console.log(`Expected: ~75% redistribution\n`);

module.exports = { NaiveHash, hash };

You've just proven the core problem. Nearly all keys move when the server count changes by just one. Next up, you'll build a hash ring that solves this by moving only the minimum number of keys.

Implement the Hash Ring

In the last step, you proved that naive modulo hashing falls apart when servers join or leave. About 75% of keys get shuffled around when a single server is added.

Now you'll build the proper solution. A hash ring arranges servers along a circular number line, so adding a new server only displaces keys in its immediate neighborhood.

In this step, get ready to:
  • Create a HashRing class with a constructor and hashing method.
  • Implement addNode and removeNode using virtual nodes.
  • Implement getNode with binary search for O(log n) key lookup.
Create the HashRing class skeleton

The hash ring maps every server to multiple positions on a circular number line (0 to 2^32-1). Each position is called a virtual node. You'll start with the class structure and the hashing function that converts strings into ring positions.

  • Create a new file called hash-ring.js in your consistent-hashing folder.
  • Paste the following code into it:
const { createHash } = require('node:crypto');

class HashRing {
  constructor(nodes = [], replicas = 150) {
    // Number of virtual nodes per physical node
    this.replicas = replicas;
    // Maps ring positions (integers) to node names
    this.ring = new Map();
    // Sorted array of ring positions for binary search
    this.sortedKeys = [];

    // Add any initial nodes passed to the constructor
    nodes.forEach(node => this.addNode(node));
  }

  _hash(key) {
    // SHA-256 the key, take first 8 hex chars, parse as 32-bit integer
    return parseInt(
      createHash('sha256').update(key).digest('hex').slice(0, 8),
      16
    );
  }
}

module.exports = { HashRing };

What does this code do?

The constructor sets up three key data structures: replicas (how many virtual nodes each physical server gets), ring (a Map from positions to server names), and sortedKeys (a sorted array of positions used for fast lookups).

The _hash(key) method produces a 32-bit integer from any string. It uses SHA-256 for uniform distribution, then takes only the first 8 hex characters (32 bits) to keep the position in a manageable range.

  • Save hash-ring.js.
  • Confirm the file exists by running:
ls

You should see hash-ring.js alongside naive-hash.js and package.json in the output.

Don't see hash-ring.js?

Make sure you created the file inside the consistent-hashing folder, not somewhere else. Check that your terminal is in the same directory by running pwd.

Help me find my hash-ring.js file

Why 150 virtual nodes?

If each physical server had just one ring position, the key distribution would be wildly uneven. Spreading 150 virtual nodes per server across the ring gives roughly even coverage. Research shows 150 virtual nodes yield approximately +/- 4% standard deviation in load, with diminishing returns above 256.

Implement addNode and removeNode

These two methods manage the ring's topology. When a server joins, you place its virtual nodes at hashed positions around the ring. When a server leaves, you remove those same positions.

  • In hash-ring.js, find the closing brace of the _hash(key) method. Add the following two methods below it, inside the class:
  addNode(node) {
    // Place virtual nodes at hashed positions around the ring
    for (let i = 0; i < this.replicas; i++) {
      const virtualKey = `${node}:${i}`;
      const position = this._hash(virtualKey);
      this.ring.set(position, node);
    }
    // Rebuild the sorted positions array for binary search
    this.sortedKeys = [...this.ring.keys()].sort((a, b) => a - b);
  }

  removeNode(node) {
    // Delete all virtual nodes belonging to this physical node
    for (let i = 0; i < this.replicas; i++) {
      const virtualKey = `${node}:${i}`;
      const position = this._hash(virtualKey);
      this.ring.delete(position);
    }
    // Rebuild sorted positions without the removed entries
    this.sortedKeys = [...this.ring.keys()].sort((a, b) => a - b);
  }

What does this code do?

  • addNode(node) loops from 0 to 149, hashing strings like server-A:0, server-A:1, etc. Each produces a unique ring position stored in the Map.
  • removeNode(node) recalculates the same positions and removes them. Because the same input always produces the same hash, you don't need to store positions separately.
  • Both methods rebuild sortedKeys after modifying the ring. This sorted array is what makes binary search possible in the next substep.
  • Save hash-ring.js.

You won't see a change yet. The next chunk adds the lookup method that ties everything together.

Implement getNode with binary search

This is the core lookup algorithm. Given a key, it hashes it to a position and then walks clockwise around the ring to find the nearest server. Binary search makes this O(log n) instead of scanning every position.

  • In hash-ring.js, find the closing brace of the removeNode method. Add the following two methods below it, still inside the class:
  getNode(key) {
    if (this.ring.size === 0) {
      return null;
    }

    const h = this._hash(key);

    // Binary search for the first position >= h
    let lo = 0;
    let hi = this.sortedKeys.length;

    while (lo < hi) {
      const mid = Math.floor((lo + hi) / 2);
      if (this.sortedKeys[mid] < h) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }

    // Wrap around to first position if past the end
    const index = lo === this.sortedKeys.length ? 0 : lo;
    return this.ring.get(this.sortedKeys[index]);
  }

  getNodes() {
    return new Set(this.ring.values());
  }

What does this code do?

  • getNode(key) hashes the key, then binary-searches the sorted positions array for the first position that is >= the hash. This simulates walking clockwise on the ring to the nearest server.
  • If the hash lands past the last position, the algorithm wraps to index 0. This is what makes the data structure circular.
  • getNodes() returns the set of distinct physical nodes currently on the ring. It's a helper you'll use in later tests.
  • Save hash-ring.js.
  • Verify the module loads correctly by running this quick test:
node -e "const { HashRing } = require('./hash-ring'); const r = new HashRing(['A','B','C']); console.log(r.getNode('hello'));"

You should see one of the node names (A, B, or C) printed in the terminal. The exact node depends on where the key hashes to on the ring.

Seeing a TypeError or SyntaxError?

  • If you see this.addNode is not a function, your addNode method is defined outside the class braces. Make sure it sits between the constructor and the closing } of the class.
  • If you see a SyntaxError, check that every opening brace { has a matching closing brace }. The class itself, the constructor, and each method all need their own pair.

Help me debug my HashRing class

✔️ Awesome, I've got everything!

Great. Double check you've saved your file before moving on.

ⓧ I'd like to double check the full code

Here's the complete hash-ring.js for comparison:

const { createHash } = require('node:crypto');

class HashRing {
  constructor(nodes = [], replicas = 150) {
    this.replicas = replicas;
    this.ring = new Map();
    this.sortedKeys = [];

    nodes.forEach(node => this.addNode(node));
  }

  _hash(key) {
    return parseInt(
      createHash('sha256').update(key).digest('hex').slice(0, 8),
      16
    );
  }

  addNode(node) {
    for (let i = 0; i < this.replicas; i++) {
      const virtualKey = `${node}:${i}`;
      const position = this._hash(virtualKey);
      this.ring.set(position, node);
    }
    this.sortedKeys = [...this.ring.keys()].sort((a, b) => a - b);
  }

  removeNode(node) {
    for (let i = 0; i < this.replicas; i++) {
      const virtualKey = `${node}:${i}`;
      const position = this._hash(virtualKey);
      this.ring.delete(position);
    }
    this.sortedKeys = [...this.ring.keys()].sort((a, b) => a - b);
  }

  getNode(key) {
    if (this.ring.size === 0) {
      return null;
    }

    const h = this._hash(key);

    // Binary search for the first position >= h
    let lo = 0;
    let hi = this.sortedKeys.length;

    while (lo < hi) {
      const mid = Math.floor((lo + hi) / 2);
      if (this.sortedKeys[mid] < h) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }

    // Wrap around to first position if past the end
    const index = lo === this.sortedKeys.length ? 0 : lo;
    return this.ring.get(this.sortedKeys[index]);
  }

  getNodes() {
    return new Set(this.ring.values());
  }
}

module.exports = { HashRing };

Your hash ring is fully functional. Next up, you'll throw 10,000 keys at it and compare the redistribution numbers against the naive approach from Step 2.

Test Key Distribution and Node Addition

Your HashRing class is complete with virtual nodes, binary search lookup, and add/remove support. Now it's time to prove it actually works better than the naive approach you built earlier.

In this step, you'll create a test script that distributes 10,000 keys across your ring and measures exactly how many keys move when you add a server. Then you'll compare that number against naive modulo hashing to see the difference in black and white.

In this step, get ready to:
  • Verify key distribution is roughly even across 3 nodes.
  • Measure key redistribution when adding a 4th node to the hash ring.
  • Compare consistent hashing redistribution against naive hashing.
Create the test file with helper functions

Before writing any tests, you need a couple of utility functions. One generates a batch of keys, and the other counts how many keys land on each node.

  • Create a new file called test-ring.js in your consistent-hashing folder and add the following code:
const { HashRing } = require('./hash-ring');
const { NaiveHash } = require('./naive-hash');

// Number of keys to distribute across nodes
const KEY_COUNT = 10000;

// Generate an array of test keys
function generateKeys(count) {
  const keys = [];
  for (let i = 0; i < count; i++) {
    keys.push(`key:${i}`);
  }
  return keys;
}

// Count how many keys land on each node
function countDistribution(ring, keys) {
  const counts = {};
  keys.forEach(key => {
    const node = ring.getNode(key);
    counts[node] = (counts[node] || 0) + 1;
  });
  return counts;
}

What does this code do?

The imports pull in both your HashRing class and the NaiveHash class so you can compare them head-to-head.

The generateKeys function creates 10,000 test keys in the format key:0, key:1, etc. The countDistribution function tallies how many keys each node receives, which tells you how balanced the ring is.

  • Save test-ring.js.
Demonstrate distribution with virtual nodes

The first test checks whether 150 virtual nodes per server actually produce an even distribution. With 3 servers and 10,000 keys, each server should hold roughly 33% of the keys.

  • Add the following Test 1 code below your helper functions in test-ring.js:
// --- Test 1: Key Distribution ---
console.log('=== Test 1: Key Distribution (3 nodes, 150 vnodes each) ===\n');

const ring = new HashRing(['server-A', 'server-B', 'server-C'], 150);
const keys = generateKeys(KEY_COUNT);
const dist = countDistribution(ring, keys);

Object.entries(dist).forEach(([node, count]) => {
  const pct = ((count / KEY_COUNT) * 100).toFixed(1);
  console.log(`  ${node}: ${count} keys (${pct}%)`);
});
console.log('');

What does this code do?

This creates a ring with 3 physical nodes and 150 virtual nodes each (450 positions total on the ring). It assigns 10,000 keys, then prints how many keys each server received.

With 150 virtual nodes, you should see each server holding approximately 33% of the keys, give or take about 4%. This proves virtual nodes spread load evenly without needing perfectly spaced physical servers.

  • Save test-ring.js and run it by executing this command in your terminal:
node test-ring.js
  • You should see each server holding roughly 3,000-3,700 keys (around 30-37% each).

Seeing an error about require?

Make sure test-ring.js is in the same folder as hash-ring.js and naive-hash.js. The relative paths ./hash-ring and ./naive-hash assume all three files live in the same directory.

help me fix my require path error in test-ring.js

Test node addition with minimal redistribution

The real power of consistent hashing shows when you change the cluster size. Adding a 4th node to a 3-node ring should only move about 25% of keys (the theoretical minimum of K/(N+1)). Compare that to the 75% catastrophe you saw with naive hashing.

  • Add Test 2 below the Test 1 code in test-ring.js:
// --- Test 2: Node Addition - Consistent Hashing ---
console.log('=== Test 2: Adding a Node (Consistent Hashing) ===\n');

// Record where all keys live before adding a node
const assignmentsBefore = {};
keys.forEach(key => {
  assignmentsBefore[key] = ring.getNode(key);
});

// Add a 4th server to the ring
ring.addNode('server-D');

// Count how many keys changed servers
let movedConsistent = 0;
keys.forEach(key => {
  if (ring.getNode(key) !== assignmentsBefore[key]) {
    movedConsistent++;
  }
});

const pctConsistent = ((movedConsistent / KEY_COUNT) * 100).toFixed(1);
console.log(`  Keys moved: ${movedConsistent} / ${KEY_COUNT} (${pctConsistent}%)`);
console.log(`  Theoretical minimum: ${(100 / 4).toFixed(1)}% (K / N+1)\n`);

What does this code do?

This records where every key lives on the 3-node ring, then adds server-D. After the addition, it checks each key again and counts how many switched servers.

The theoretical minimum redistribution when going from 3 to 4 nodes is K/(N+1) = 25%. Your ring should come close to this number. Only keys that fall in the arc claimed by the new node's virtual positions need to move.

  • Save test-ring.js and run it again:
node test-ring.js
  • In the Test 2 output, you should see approximately 25% of keys moved. This is dramatically better than the 75% you saw with naive hashing in Step 2.

Seeing more than 30% keys moved?

Check that your HashRing constructor passes 150 as the replicas value. Fewer virtual nodes means less even distribution and higher redistribution percentages.

help me debug why my consistent hashing redistribution percentage is too high

Compare against naive hashing

The final test runs the same scenario (adding a 4th server to 3) using the NaiveHash class. This puts both approaches side by side so you can see the difference at the same scale of 10,000 keys.

  • Add Test 3 below the Test 2 code in test-ring.js:
// --- Test 3: Node Addition - Naive Hashing ---
console.log('=== Test 3: Adding a Node (Naive Hashing) ===\n');

// Start fresh with a 3-node naive hash
const naive = new NaiveHash(['server-A', 'server-B', 'server-C']);
const naiveBefore = {};
keys.forEach(key => {
  naiveBefore[key] = naive.getNode(key);
});

// Add the same 4th server
naive.addNode('server-D');

// Count how many keys moved
let movedNaive = 0;
keys.forEach(key => {
  if (naive.getNode(key) !== naiveBefore[key]) {
    movedNaive++;
  }
});

const pctNaive = ((movedNaive / KEY_COUNT) * 100).toFixed(1);
console.log(`  Keys moved: ${movedNaive} / ${KEY_COUNT} (${pctNaive}%)`);
console.log(`  Expected: ~75%\n`);

What does this code do?

This repeats the exact same test scenario (3 servers, add a 4th, count moves) using NaiveHash instead of HashRing. Since naive hashing uses hash % numberOfServers, changing the server count scrambles nearly every key assignment.

The output proves the problem at scale. About 75% of 10,000 keys move with naive hashing, while only about 25% move with consistent hashing. In a real system with millions of cached objects, that difference means the difference between a brief hiccup and a total cache stampede.

  • Save test-ring.js and run the full test suite:
node test-ring.js
  • You should see all three tests print their results. Test 2 shows approximately 25% redistribution, while Test 3 shows approximately 75% redistribution.

Seeing a NaiveHash is not a constructor error?

Make sure your naive-hash.js file ends with module.exports = { NaiveHash, hash };. Without that export line, the require in test-ring.js can't find the class.

help me fix the NaiveHash import error

Why is ~25% the theoretical minimum?

When you add 1 node to N existing nodes, the new node claims 1/(N+1) of the ring's arc space. Only keys that fall within that new arc need to move. For 3 nodes growing to 4, that's 1/4 = 25% of keys. This is the best any algorithm can do, because the new node must own some keys.

Naive hashing gives you no such guarantee. Changing the modulus from 3 to 4 scrambles the assignment of almost every key, regardless of how many actually need to move.

✔️ Awesome, I've got everything!

Great. Double check you've saved test-ring.js and that all three tests produce output when you run the script.

ⓧ I'd like to double check the full code

Here's the complete test-ring.js file so far:

const { HashRing } = require('./hash-ring');
const { NaiveHash } = require('./naive-hash');

const KEY_COUNT = 10000;

function generateKeys(count) {
  const keys = [];
  for (let i = 0; i < count; i++) {
    keys.push(`key:${i}`);
  }
  return keys;
}

function countDistribution(ring, keys) {
  const counts = {};
  keys.forEach(key => {
    const node = ring.getNode(key);
    counts[node] = (counts[node] || 0) + 1;
  });
  return counts;
}

// --- Test 1: Key Distribution ---
console.log('=== Test 1: Key Distribution (3 nodes, 150 vnodes each) ===\n');

const ring = new HashRing(['server-A', 'server-B', 'server-C'], 150);
const keys = generateKeys(KEY_COUNT);
const dist = countDistribution(ring, keys);

Object.entries(dist).forEach(([node, count]) => {
  const pct = ((count / KEY_COUNT) * 100).toFixed(1);
  console.log(`  ${node}: ${count} keys (${pct}%)`);
});
console.log('');

// --- Test 2: Node Addition - Consistent Hashing ---
console.log('=== Test 2: Adding a Node (Consistent Hashing) ===\n');

const assignmentsBefore = {};
keys.forEach(key => {
  assignmentsBefore[key] = ring.getNode(key);
});

ring.addNode('server-D');

let movedConsistent = 0;
keys.forEach(key => {
  if (ring.getNode(key) !== assignmentsBefore[key]) {
    movedConsistent++;
  }
});

const pctConsistent = ((movedConsistent / KEY_COUNT) * 100).toFixed(1);
console.log(`  Keys moved: ${movedConsistent} / ${KEY_COUNT} (${pctConsistent}%)`);
console.log(`  Theoretical minimum: ${(100 / 4).toFixed(1)}% (K / N+1)\n`);

// --- Test 3: Node Addition - Naive Hashing ---
console.log('=== Test 3: Adding a Node (Naive Hashing) ===\n');

const naive = new NaiveHash(['server-A', 'server-B', 'server-C']);
const naiveBefore = {};
keys.forEach(key => {
  naiveBefore[key] = naive.getNode(key);
});

naive.addNode('server-D');

let movedNaive = 0;
keys.forEach(key => {
  if (naive.getNode(key) !== naiveBefore[key]) {
    movedNaive++;
  }
});

const pctNaive = ((movedNaive / KEY_COUNT) * 100).toFixed(1);
console.log(`  Keys moved: ${movedNaive} / ${KEY_COUNT} (${pctNaive}%)`);
console.log(`  Expected: ~75%\n`);

You've proven that your hash ring achieves near-optimal redistribution. Next up, you'll test what happens when a node is removed and verify that the ring maintains its integrity guarantees.

Test Node Removal and Verify Ring Properties

In the previous step, you proved that consistent hashing moves far fewer keys than naive modulo hashing when a server joins the cluster. But servers don't just appear. They crash, get decommissioned, or scale down.

In this step, you'll test the other half of the equation: what happens when a node disappears. You'll also add integrity assertions that prove the ring's two core guarantees hold after topology changes.

In this step, get ready to:
  • Remove a node and measure key redistribution.
  • Assert that all keys still resolve to valid nodes after removal.
  • Verify that unaffected keys remain unchanged.
Test node removal

When a server goes offline in a real distributed cache, only the keys that lived on that server should move. Every other key should stay exactly where it was. This is the property that makes consistent hashing suitable for production systems.

  • In test-ring.js, scroll to the bottom of the file (after Test 3) and add the node removal test by pasting this code:
// --- Test 4: Node Removal ---
console.log('=== Test 4: Removing a Node (Consistent Hashing) ===\n');

const beforeRemoval = {};
keys.forEach(key => {
  beforeRemoval[key] = ring.getNode(key);
});

ring.removeNode('server-B');

let movedAfterRemoval = 0;
keys.forEach(key => {
  if (ring.getNode(key) !== beforeRemoval[key]) {
    movedAfterRemoval++;
  }
});

const pctRemoval = ((movedAfterRemoval / KEY_COUNT) * 100).toFixed(1);
console.log(`  Keys moved: ${movedAfterRemoval} / ${KEY_COUNT} (${pctRemoval}%)`);
console.log(`  Only keys from removed node should move\n`);

What does this code do?

This test snapshots where every key lives before the removal, then calls ring.removeNode('server-B') to simulate a server going offline.

After removal, it recalculates assignments and counts how many keys moved. With 4 nodes reduced to 3, only the keys that belonged to server-B should redistribute. That's roughly 25% of all keys.

Verify ring properties with assertions

A correct hash ring guarantees two things after any topology change: every key resolves to a live node, and keys that weren't on the removed node stay put. These assertions prove both properties hold.

  • Below the Test 4 code you just added, paste the integrity check and summary:
// --- Test 5: Verify all keys still resolve ---
console.log('=== Test 5: Integrity Check ===\n');

let allValid = true;
const remainingNodes = ring.getNodes();
keys.forEach(key => {
  const node = ring.getNode(key);
  if (!remainingNodes.has(node)) {
    allValid = false;
  }
});

console.log(`  All keys resolve to valid node: ${allValid ? 'PASS' : 'FAIL'}`);

// Verify unaffected keys stayed the same
let unaffectedMoved = 0;
keys.forEach(key => {
  if (beforeRemoval[key] !== 'server-B' && ring.getNode(key) !== beforeRemoval[key]) {
    unaffectedMoved++;
  }
});

console.log(`  Unaffected keys unchanged: ${unaffectedMoved === 0 ? 'PASS' : 'FAIL'} (${unaffectedMoved} unexpected moves)`);
console.log('\n=== Summary ===');
console.log(`  Naive hashing redistribution:      ${pctNaive}%`);
console.log(`  Consistent hashing redistribution:  ${pctConsistent}%`);
console.log(`  Improvement: ${(parseFloat(pctNaive) - parseFloat(pctConsistent)).toFixed(1)} percentage points fewer keys moved`);

What does this code do?

  • The first check uses ring.getNodes() to get the set of remaining physical nodes, then asserts every key resolves to one of them. If any key pointed to a dead node, allValid flips to false.
  • The second check filters to keys that were NOT on server-B before removal. If any of those keys moved, it means the ring violated its stability guarantee.
  • The final summary prints a side-by-side comparison of naive vs consistent hashing redistribution percentages.
  • Save test-ring.js.
  • Run the complete test suite by running this command:
node test-ring.js
  • You should see all 5 tests print their results, with Test 4 showing approximately 25% redistribution and Test 5 showing two PASS results.

What should I see?

Test 4 should show around 25% of keys moved. This is the theoretical minimum when removing 1 of 4 nodes (K/N).

Test 5 should show PASS for both assertions. The summary at the bottom compares naive hashing (~75% redistribution) against consistent hashing (~25% redistribution), proving the hash ring moves roughly 50 percentage points fewer keys.

Seeing FAIL in the output?

  • Make sure you pasted Test 4 before Test 5. The beforeRemoval object from Test 4 is used in Test 5's unaffected-keys check.
  • Check that the ring variable is the same one from Test 1. Tests 1 through 5 share a single ring instance that changes state as nodes are added and removed.
  • Verify you haven't accidentally duplicated the const ring declaration. JavaScript will throw an error if const is declared twice.

Why is my test-ring.js throwing an error or showing FAIL?

✔️ Awesome, I've got everything!

Great. Double check you've saved your file.

ⓧ I'd like to double check the full code

const { HashRing } = require('./hash-ring');
const { NaiveHash } = require('./naive-hash');

const KEY_COUNT = 10000;

function generateKeys(count) {
  const keys = [];
  for (let i = 0; i < count; i++) {
    keys.push(`key:${i}`);
  }
  return keys;
}

function countDistribution(ring, keys) {
  const counts = {};
  keys.forEach(key => {
    const node = ring.getNode(key);
    counts[node] = (counts[node] || 0) + 1;
  });
  return counts;
}

// --- Test 1: Key Distribution ---
console.log('=== Test 1: Key Distribution (3 nodes, 150 vnodes each) ===\n');

const ring = new HashRing(['server-A', 'server-B', 'server-C'], 150);
const keys = generateKeys(KEY_COUNT);
const dist = countDistribution(ring, keys);

Object.entries(dist).forEach(([node, count]) => {
  const pct = ((count / KEY_COUNT) * 100).toFixed(1);
  console.log(`  ${node}: ${count} keys (${pct}%)`);
});
console.log('');

// --- Test 2: Node Addition - Consistent Hashing ---
console.log('=== Test 2: Adding a Node (Consistent Hashing) ===\n');

const assignmentsBefore = {};
keys.forEach(key => {
  assignmentsBefore[key] = ring.getNode(key);
});

ring.addNode('server-D');

let movedConsistent = 0;
keys.forEach(key => {
  if (ring.getNode(key) !== assignmentsBefore[key]) {
    movedConsistent++;
  }
});

const pctConsistent = ((movedConsistent / KEY_COUNT) * 100).toFixed(1);
console.log(`  Keys moved: ${movedConsistent} / ${KEY_COUNT} (${pctConsistent}%)`);
console.log(`  Theoretical minimum: ${(100 / 4).toFixed(1)}% (K / N+1)\n`);

// --- Test 3: Node Addition - Naive Hashing ---
console.log('=== Test 3: Adding a Node (Naive Hashing) ===\n');

const naive = new NaiveHash(['server-A', 'server-B', 'server-C']);
const naiveBefore = {};
keys.forEach(key => {
  naiveBefore[key] = naive.getNode(key);
});

naive.addNode('server-D');

let movedNaive = 0;
keys.forEach(key => {
  if (naive.getNode(key) !== naiveBefore[key]) {
    movedNaive++;
  }
});

const pctNaive = ((movedNaive / KEY_COUNT) * 100).toFixed(1);
console.log(`  Keys moved: ${movedNaive} / ${KEY_COUNT} (${pctNaive}%)`);
console.log(`  Expected: ~75%\n`);

// --- Test 4: Node Removal ---
console.log('=== Test 4: Removing a Node (Consistent Hashing) ===\n');

const beforeRemoval = {};
keys.forEach(key => {
  beforeRemoval[key] = ring.getNode(key);
});

ring.removeNode('server-B');

let movedAfterRemoval = 0;
keys.forEach(key => {
  if (ring.getNode(key) !== beforeRemoval[key]) {
    movedAfterRemoval++;
  }
});

const pctRemoval = ((movedAfterRemoval / KEY_COUNT) * 100).toFixed(1);
console.log(`  Keys moved: ${movedAfterRemoval} / ${KEY_COUNT} (${pctRemoval}%)`);
console.log(`  Only keys from removed node should move\n`);

// --- Test 5: Verify all keys still resolve ---
console.log('=== Test 5: Integrity Check ===\n');

let allValid = true;
const remainingNodes = ring.getNodes();
keys.forEach(key => {
  const node = ring.getNode(key);
  if (!remainingNodes.has(node)) {
    allValid = false;
  }
});

console.log(`  All keys resolve to valid node: ${allValid ? 'PASS' : 'FAIL'}`);

// Verify unaffected keys stayed the same
let unaffectedMoved = 0;
keys.forEach(key => {
  if (beforeRemoval[key] !== 'server-B' && ring.getNode(key) !== beforeRemoval[key]) {
    unaffectedMoved++;
  }
});

console.log(`  Unaffected keys unchanged: ${unaffectedMoved === 0 ? 'PASS' : 'FAIL'} (${unaffectedMoved} unexpected moves)`);
console.log('\n=== Summary ===');
console.log(`  Naive hashing redistribution:      ${pctNaive}%`);
console.log(`  Consistent hashing redistribution:  ${pctConsistent}%`);
console.log(`  Improvement: ${(parseFloat(pctNaive) - parseFloat(pctConsistent)).toFixed(1)} percentage points fewer keys moved`);

Secret mission

Add Bounded-Load Consistent Hashing

Your hash ring distributes keys well on average, but individual nodes can still become hot spots. In this mission, you'll add a capacity cap so no single node handles more than 1.5x the average load. When a node is full, the algorithm probes clockwise to the next node with available capacity.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your project files for reference, or delete them to free up disk space.

Resources you used:

  • The consistent-hashing project folder on your Desktop (contains naive-hash.js, hash-ring.js, test-ring.js, hash-ring-bounded.js, and package.json).
  • Node.js v22 LTS (installed as a prerequisite).

Keep everything running

No action needed. Choose this if you plan to extend the project or reference the code later.

  • Your consistent-hashing folder stays on your Desktop.
  • Node.js remains available for future JavaScript projects.

Pause - I'll come back to this later

Since this project has no running processes or cloud resources, there is nothing to pause. Your files sit on disk until you return.

  • Close the VS Code window to free up memory.
  • Your project files remain in the consistent-hashing folder on your Desktop, ready when you are.

Delete - I don't want to use this again

Remove all project files. Only remove Node.js if you have no other JavaScript projects that depend on it.

  • Close VS Code.
  • Delete the project folder by running this command in your terminal:

macOS

rm -rf ~/Desktop/consistent-hashing

Windows

rmdir /s /q %USERPROFILE%\Desktop\consistent-hashing
  • Confirm the folder is gone by checking your Desktop.
  • (Optional) If you no longer need Node.js, uninstall it from your system. On macOS, use the official uninstaller or remove it via your package manager. On Windows, go to Settings > Apps > Installed apps, find Node.js, and click Uninstall.

Nice Work!

Nice Work!

You just built the algorithm that powers billion-dollar distributed systems. From DynamoDB to Cassandra to Memcached, consistent hashing is how the internet routes data without melting down during scaling events.

You've learned how to:

  • Build naive modulo hashing and prove why it fails at scale, with 75%+ key redistribution on topology changes.
  • Implement a full hash ring with virtual nodes and O(log n) binary search lookup for key-to-node routing.
  • Demonstrate that consistent hashing achieves near-optimal key redistribution (~K/N keys move) and verify it statistically across node addition and removal.
  • Added bounded-load consistent hashing to prevent hot-node cascades by capping any single node at 1.5x the average load.

Ready to quiz yourself?