Consistent Hashing

Difficulty: Advanced

Question

What is consistent hashing? Why is it used in distributed systems and how does it solve the rehashing problem?

Answer

Consistent hashing is a technique that minimizes key redistribution when nodes are added or removed from a distributed system.

Problem with simple hashing: hash(key) % N maps keys to N servers. When N changes (server added/removed), almost ALL keys must be remapped.

Consistent hashing solution: Arrange hash space in a ring (0 to 2^32). Both servers and keys are hashed onto this ring. Each key is assigned to the next server clockwise on the ring.

When a server is added: Only keys between the new server and its predecessor are remapped. When a server is removed: Only its keys move to the next server.

Virtual nodes: Each physical server maps to multiple points on the ring for more even distribution.

Used by: DynamoDB, Cassandra, Memcached, CDN routing, load balancers.

Code examples

Consistent Hashing Implementation

const crypto = require('crypto');

class ConsistentHash {
  constructor(virtualNodes = 150) {
    this.virtualNodes = virtualNodes;
    this.ring = new Map();       // hash -> server
    this.sortedHashes = [];      // sorted hash positions
    this.servers = new Set();
  }

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

  addServer(server) {
    this.servers.add(server);
    for (let i = 0; i < this.virtualNodes; i++) {
      const virtualKey = `${server}:vn${i}`;
      const h = this.hash(virtualKey);
      this.ring.set(h, server);
      this.sortedHashes.push(h);
    }
    this.sortedHashes.sort((a, b) => a - b);
  }

  removeServer(server) {
    this.servers.delete(server);
    for (let i = 0; i < this.virtualNodes; i++) {
      const h = this.hash(`${server}:vn${i}`);
      this.ring.delete(h);
      this.sortedHashes = this.sortedHashes.filter(x => x !== h);
    }
  }

  getServer(key) {
    if (this.sortedHashes.length === 0) return null;
    const h = this.hash(key);
    // Find next server clockwise on the ring
    for (const pos of this.sortedHashes) {
      if (pos >= h) return this.ring.get(pos);
    }
    return this.ring.get(this.sortedHashes[0]); // Wrap around
  }
}

Virtual nodes ensure even distribution across servers. Each physical server has 150 positions on the ring, preventing hotspots. Binary search can replace the linear scan for better performance.

Demonstrating the Rehashing Problem

// Simple hash: hash(key) % numServers
// Adding one server remaps most keys!

function simpleHash(key, numServers) {
  let hash = 0;
  for (const char of key) hash = (hash * 31 + char.charCodeAt(0)) >>> 0;
  return hash % numServers;
}

// With 3 servers:
// 'user:1' -> server 2
// 'user:2' -> server 0
// 'user:3' -> server 1

// With 4 servers (added one):
// 'user:1' -> server 3  (MOVED!)
// 'user:2' -> server 2  (MOVED!)
// 'user:3' -> server 0  (MOVED!)
// Almost everything moved!

// Consistent hashing with 3 servers:
// 'user:1' -> server A
// 'user:2' -> server B
// 'user:3' -> server C

// With 4 servers (added server D):
// 'user:1' -> server A  (unchanged)
// 'user:2' -> server D  (moved - was between C and D)
// 'user:3' -> server C  (unchanged)
// Only ~1/N keys moved (N = number of servers)

// Impact: with 100 servers and 1M keys
// Simple hash: ~990,000 keys move (99%)
// Consistent hash: ~10,000 keys move (1%)

Simple modulo hashing causes massive key redistribution when server count changes. Consistent hashing limits movement to approximately 1/N of keys, making scaling smooth.

Real-World Usage: Distributed Cache

// Distributed cache using consistent hashing
class DistributedCache {
  constructor(servers) {
    this.hashRing = new ConsistentHash();
    this.clients = {};

    for (const server of servers) {
      this.hashRing.addServer(server);
      this.clients[server] = new RedisClient(server);
    }
  }

  async get(key) {
    const server = this.hashRing.getServer(key);
    return this.clients[server].get(key);
  }

  async set(key, value, ttl) {
    const server = this.hashRing.getServer(key);
    return this.clients[server].set(key, value, 'EX', ttl);
  }

  // Scale up: add a new cache server
  async addServer(server) {
    this.hashRing.addServer(server);
    this.clients[server] = new RedisClient(server);
    // Only ~1/N keys need to migrate
    // Keys will naturally migrate on cache miss + refill
  }

  // Scale down: remove a cache server
  async removeServer(server) {
    this.hashRing.removeServer(server);
    delete this.clients[server];
    // Removed server's keys cause cache misses
    // They get refilled on next access from the DB
  }
}

// Usage:
const cache = new DistributedCache([
  'redis-1:6379',
  'redis-2:6379',
  'redis-3:6379'
]);

await cache.set('user:123', userData, 3600);
const user = await cache.get('user:123');

Consistent hashing lets distributed caches scale smoothly. Adding or removing nodes only affects a small fraction of cached keys. Cache misses from moved keys are naturally refilled from the database.

Key points

Concepts covered

Consistent Hashing, Hash Ring, Virtual Nodes, Data Partitioning, Distributed Systems