Consistent Hashing

Overview

Consistent Hashing is a fundamental technique for distributing data across multiple nodes in a distributed system while minimizing data movement when nodes are added or removed. Unlike traditional hashing, it ensures that only a small fraction of keys need to be redistributed when the cluster topology changes, making it essential for building scalable distributed systems.

Originally developed for distributed caching systems, consistent hashing is now the backbone of many large-scale systems including Amazon DynamoDB, Apache Cassandra, and content delivery networks (CDNs). It solves the critical challenge of maintaining data locality and load balance while allowing dynamic scaling.

The main technical challenges this addresses include:

• Minimal data movement: Reducing redistribution overhead during cluster changes
• Load balancing: Ensuring even distribution of data and requests across nodes
• Fault tolerance: Handling node failures gracefully without major disruption
• Dynamic scaling: Adding or removing nodes without system downtime

Core Principles: The Hash Ring

Traditional Hashing Problems

Simple Modulo Hashing:

// Traditional approach - problematic for distributed systems
function getNode(key, nodeCount) {
  return hash(key) % nodeCount;
}

// Problem: Adding/removing nodes requires massive redistribution
// If nodeCount changes from 3 to 4:
// - hash("user123") % 3 = 1
// - hash("user123") % 4 = 2
// Result: Most keys need to move to different nodes

The Redistribution Problem: When using simple modulo hashing with N nodes, adding or removing a single node requires redistributing approximately (N-1)/N of all keys, which can be 90%+ in large clusters.

Consistent Hashing Solution

The Hash Ring Concept: Consistent hashing maps both keys and nodes to points on a circular hash ring (typically 0 to 2^32-1). Each key is assigned to the first node found when moving clockwise around the ring.

Virtual Nodes (Vnodes)

Problem with Single Hash Points: Using only one hash point per physical node can lead to uneven data distribution, especially with small numbers of nodes.

Solution - Virtual Nodes: Each physical node is mapped to multiple points (virtual nodes) on the hash ring, improving load distribution and fault tolerance.

class ConsistentHashRing {
  constructor(virtualNodeCount = 150) {
    this.virtualNodeCount = virtualNodeCount;
    this.ring = new Map(); // position -> node mapping
    this.nodes = new Set();
    this.sortedPositions = [];
  }
  
  addNode(nodeId) {
    this.nodes.add(nodeId);
    
    // Add virtual nodes for this physical node
    for (let i = 0; i < this.virtualNodeCount; i++) {
      const virtualNodeId = `${nodeId}:${i}`;
      const position = this.hash(virtualNodeId);
      this.ring.set(position, nodeId);
    }
    
    this.updateSortedPositions();
  }
  
  removeNode(nodeId) {
    this.nodes.delete(nodeId);
    
    // Remove all virtual nodes for this physical node
    for (let i = 0; i < this.virtualNodeCount; i++) {
      const virtualNodeId = `${nodeId}:${i}`;
      const position = this.hash(virtualNodeId);
      this.ring.delete(position);
    }
    
    this.updateSortedPositions();
  }
  
  getNode(key) {
    if (this.nodes.size === 0) {
      throw new Error('No nodes available');
    }
    
    const keyHash = this.hash(key);
    
    // Find first node clockwise from key position
    for (const position of this.sortedPositions) {
      if (position >= keyHash) {
        return this.ring.get(position);
      }
    }
    
    // Wrap around to first node
    return this.ring.get(this.sortedPositions[0]);
  }
  
  hash(input) {
    // Simple hash function (use MD5/SHA1 in production)
    let hash = 0;
    for (let i = 0; i < input.length; i++) {
      const char = input.charCodeAt(i);
      hash = ((hash << 5) - hash) + char;
      hash = hash & hash; // Convert to 32bit integer
    }
    return Math.abs(hash);
  }
  
  updateSortedPositions() {
    this.sortedPositions = Array.from(this.ring.keys()).sort((a, b) => a - b);
  }
  
  // Get distribution statistics
  getDistribution() {
    const distribution = new Map();
    
    // Sample keys to test distribution
    for (let i = 0; i < 10000; i++) {
      const key = `test_key_${i}`;
      const node = this.getNode(key);
      distribution.set(node, (distribution.get(node) || 0) + 1);
    }
    
    return distribution;
  }
}

Advanced Implementation Patterns

Weighted Consistent Hashing

class WeightedConsistentHashRing {
  constructor() {
    this.ring = new Map();
    this.nodeWeights = new Map();
    this.sortedPositions = [];
  }
  
  addNode(nodeId, weight = 1, capacity = 100) {
    this.nodeWeights.set(nodeId, { weight, capacity });
    
    // Calculate virtual nodes based on weight
    const virtualNodeCount = Math.ceil(weight * 150);
    
    for (let i = 0; i < virtualNodeCount; i++) {
      const virtualNodeId = `${nodeId}:${i}`;
      const position = this.hash(virtualNodeId);
      this.ring.set(position, {
        nodeId,
        weight,
        capacity,
        virtualNodeIndex: i
      });
    }
    
    this.updateSortedPositions();
  }
  
  getNodeWithCapacity(key) {
    const keyHash = this.hash(key);
    let attempts = 0;
    const maxAttempts = this.sortedPositions.length;
    
    while (attempts < maxAttempts) {
      const position = this.findNextPosition(keyHash, attempts);
      const nodeInfo = this.ring.get(position);
      
      if (this.hasCapacity(nodeInfo.nodeId)) {
        return nodeInfo.nodeId;
      }
      
      attempts++;
    }
    
    throw new Error('No nodes with available capacity');
  }
  
  hasCapacity(nodeId) {
    // Check if node has available capacity
    // This would integrate with actual node monitoring
    return this.getCurrentLoad(nodeId) < this.nodeWeights.get(nodeId).capacity;
  }
  
  getCurrentLoad(nodeId) {
    // Implementation depends on monitoring system
    // Return current CPU, memory, or request load
    return Math.random() * 100; // Placeholder
  }
}

Replication and Consistency

class ReplicatedConsistentHashRing {
  constructor(replicationFactor = 3) {
    this.replicationFactor = replicationFactor;
    this.ring = new ConsistentHashRing();
  }
  
  getReplicaNodes(key) {
    const keyHash = this.ring.hash(key);
    const replicas = [];
    const uniqueNodes = new Set();
    
    let currentPosition = keyHash;
    
    while (replicas.length < this.replicationFactor && 
           uniqueNodes.size < this.ring.nodes.size) {
      
      const node = this.ring.getNodeFromPosition(currentPosition);
      
      if (!uniqueNodes.has(node)) {
        replicas.push(node);
        uniqueNodes.add(node);
      }
      
      // Move to next position on ring
      currentPosition = this.ring.getNextPosition(currentPosition);
    }
    
    return replicas;
  }
  
  async writeData(key, value) {
    const replicas = this.getReplicaNodes(key);
    const writePromises = replicas.map(node => 
      this.writeToNode(node, key, value)
    );
    
    // Wait for quorum (majority) of writes to succeed
    const quorumSize = Math.floor(this.replicationFactor / 2) + 1;
    
    try {
      const results = await Promise.allSettled(writePromises);
      const successful = results.filter(r => r.status === 'fulfilled');
      
      if (successful.length >= quorumSize) {
        return { success: true, replicas: successful.length };
      } else {
        throw new Error(`Write failed: only ${successful.length}/${quorumSize} replicas succeeded`);
      }
    } catch (error) {
      throw new Error(`Write operation failed: ${error.message}`);
    }
  }
  
  async readData(key, consistencyLevel = 'ONE') {
    const replicas = this.getReplicaNodes(key);
    
    switch (consistencyLevel) {
      case 'ONE':
        return await this.readFromFirstAvailable(replicas, key);
      case 'QUORUM':
        return await this.readWithQuorum(replicas, key);
      case 'ALL':
        return await this.readFromAll(replicas, key);
      default:
        throw new Error(`Unknown consistency level: ${consistencyLevel}`);
    }
  }
}

Production Implementation Considerations

Hash Function Selection

// Production-grade hash functions
const crypto = require('crypto');

class ProductionHashRing {
  constructor(hashFunction = 'md5') {
    this.hashFunction = hashFunction;
    this.ring = new Map();
  }
  
  hash(input) {
    switch (this.hashFunction) {
      case 'md5':
        return parseInt(crypto.createHash('md5').update(input).digest('hex').substring(0, 8), 16);
      
      case 'sha1':
        return parseInt(crypto.createHash('sha1').update(input).digest('hex').substring(0, 8), 16);
      
      case 'murmur3':
        return this.murmur3Hash(input);
      
      default:
        throw new Error(`Unsupported hash function: ${this.hashFunction}`);
    }
  }
  
  murmur3Hash(input) {
    // MurmurHash3 implementation - better distribution than MD5/SHA1
    let hash = 0;
    const c1 = 0xcc9e2d51;
    const c2 = 0x1b873593;
    const r1 = 15;
    const r2 = 13;
    const m = 5;
    const n = 0xe6546b64;
    
    for (let i = 0; i < input.length; i += 4) {
      let k = 0;
      k |= (input.charCodeAt(i) & 0xff);
      k |= ((input.charCodeAt(i + 1) & 0xff) << 8);
      k |= ((input.charCodeAt(i + 2) & 0xff) << 16);
      k |= ((input.charCodeAt(i + 3) & 0xff) << 24);
      
      k = Math.imul(k, c1);
      k = (k << r1) | (k >>> (32 - r1));
      k = Math.imul(k, c2);
      
      hash ^= k;
      hash = (hash << r2) | (hash >>> (32 - r2));
      hash = Math.imul(hash, m) + n;
    }
    
    hash ^= input.length;
    hash ^= hash >>> 16;
    hash = Math.imul(hash, 0x85ebca6b);
    hash ^= hash >>> 13;
    hash = Math.imul(hash, 0xc2b2ae35);
    hash ^= hash >>> 16;
    
    return hash >>> 0; // Ensure unsigned 32-bit integer
  }
}

Monitoring and Metrics

class MonitoredConsistentHashRing {
  constructor() {
    this.ring = new ConsistentHashRing();
    this.metrics = {
      keyDistribution: new Map(),
      nodeLoad: new Map(),
      redistributionEvents: [],
      hotspots: new Set()
    };
  }
  
  addNode(nodeId) {
    const beforeDistribution = this.getDistribution();
    this.ring.addNode(nodeId);
    const afterDistribution = this.getDistribution();
    
    this.recordRedistribution('ADD_NODE', nodeId, beforeDistribution, afterDistribution);
  }
  
  removeNode(nodeId) {
    const beforeDistribution = this.getDistribution();
    this.ring.removeNode(nodeId);
    const afterDistribution = this.getDistribution();
    
    this.recordRedistribution('REMOVE_NODE', nodeId, beforeDistribution, afterDistribution);
  }
  
  recordRedistribution(operation, nodeId, before, after) {
    const redistributionPercentage = this.calculateRedistribution(before, after);
    
    this.metrics.redistributionEvents.push({
      timestamp: Date.now(),
      operation,
      nodeId,
      redistributionPercentage,
      affectedKeys: this.getAffectedKeys(before, after)
    });
    
    // Alert if redistribution is higher than expected
    if (redistributionPercentage > 20) { // 20% threshold
      console.warn(`High redistribution detected: ${redistributionPercentage}%`);
    }
  }
  
  detectHotspots() {
    const distribution = this.getDistribution();
    const average = Array.from(distribution.values()).reduce((a, b) => a + b, 0) / distribution.size;
    const threshold = average * 1.5; // 50% above average
    
    for (const [node, load] of distribution) {
      if (load > threshold) {
        this.metrics.hotspots.add(node);
      }
    }
    
    return this.metrics.hotspots;
  }
  
  getHealthReport() {
    return {
      nodeCount: this.ring.nodes.size,
      distribution: this.getDistribution(),
      hotspots: Array.from(this.metrics.hotspots),
      recentRedistributions: this.metrics.redistributionEvents.slice(-5),
      ringBalance: this.calculateRingBalance()
    };
  }
}

Real-World Use Cases

Content Delivery Networks (CDNs)

class CDNConsistentHashing {
  constructor() {
    this.ring = new ConsistentHashRing();
    this.edgeServers = new Map(); // serverId -> server metadata
  }
  
  addEdgeServer(serverId, location, capacity) {
    this.edgeServers.set(serverId, {
      location,
      capacity,
      currentLoad: 0,
      lastHealthCheck: Date.now()
    });
    
    this.ring.addNode(serverId);
  }
  
  routeRequest(contentId, userLocation) {
    // Get primary and backup servers for content
    const primaryServer = this.ring.getNode(contentId);
    const backupServers = this.getBackupServers(contentId, 2);
    
    // Consider geographic proximity
    const candidates = [primaryServer, ...backupServers]
      .filter(serverId => this.isServerHealthy(serverId))
      .sort((a, b) => this.getDistance(userLocation, this.edgeServers.get(a).location) - 
                       this.getDistance(userLocation, this.edgeServers.get(b).location));
    
    if (candidates.length === 0) {
      throw new Error('No healthy servers available');
    }
    
    return candidates[0];
  }
  
  getBackupServers(contentId, count) {
    // Find next servers on ring for replication
    const replicas = [];
    let position = this.ring.hash(contentId);
    
    while (replicas.length < count) {
      position = this.ring.getNextPosition(position);
      const server = this.ring.getNodeFromPosition(position);
      if (!replicas.includes(server)) {
        replicas.push(server);
      }
    }
    
    return replicas;
  }
}

Database Sharding

class DatabaseShardRouter {
  constructor(shardConfig) {
    this.ring = new ConsistentHashRing();
    this.shards = new Map();
    this.replicationFactor = shardConfig.replicationFactor || 3;
    
    // Initialize shards
    shardConfig.shards.forEach(shard => {
      this.addShard(shard.id, shard.connectionString, shard.weight);
    });
  }
  
  addShard(shardId, connectionString, weight = 1) {
    this.shards.set(shardId, {
      connectionString,
      weight,
      connection: this.createConnection(connectionString)
    });
    
    this.ring.addNode(shardId);
  }
  
  async query(key, sql, params) {
    const primaryShard = this.ring.getNode(key);
    const replicaShards = this.getReplicaShards(key);
    
    try {
      // Try primary shard first
      return await this.executeQuery(primaryShard, sql, params);
    } catch (error) {
      console.warn(`Primary shard ${primaryShard} failed, trying replicas`);
      
      // Fallback to replica shards
      for (const replicaShard of replicaShards) {
        try {
          return await this.executeQuery(replicaShard, sql, params);
        } catch (replicaError) {
          console.warn(`Replica shard ${replicaShard} also failed`);
        }
      }
      
      throw new Error('All shards failed for key: ' + key);
    }
  }
  
  async executeQuery(shardId, sql, params) {
    const shard = this.shards.get(shardId);
    if (!shard) {
      throw new Error(`Shard ${shardId} not found`);
    }
    
    return await shard.connection.query(sql, params);
  }
}

Performance Analysis

Complexity Analysis

Load Distribution Analysis

class PerformanceAnalyzer {
  static analyzeDistribution(ring, sampleSize = 100000) {
    const distribution = new Map();
    const nodes = Array.from(ring.nodes);
    
    // Initialize counters
    nodes.forEach(node => distribution.set(node, 0));
    
    // Sample random keys
    for (let i = 0; i < sampleSize; i++) {
      const key = `sample_key_${i}_${Math.random()}`;
      const node = ring.getNode(key);
      distribution.set(node, distribution.get(node) + 1);
    }
    
    // Calculate statistics
    const counts = Array.from(distribution.values());
    const mean = counts.reduce((a, b) => a + b, 0) / counts.length;
    const variance = counts.reduce((sum, count) => sum + Math.pow(count - mean, 2), 0) / counts.length;
    const stdDev = Math.sqrt(variance);
    const coefficientOfVariation = stdDev / mean;
    
    return {
      distribution,
      mean,
      standardDeviation: stdDev,
      coefficientOfVariation,
      maxLoad: Math.max(...counts),
      minLoad: Math.min(...counts),
      loadImbalance: (Math.max(...counts) - Math.min(...counts)) / mean
    };
  }
  
  static benchmarkOperations(ring) {
    const operations = 10000;
    
    // Benchmark lookups
    const lookupStart = performance.now();
    for (let i = 0; i < operations; i++) {
      ring.getNode(`benchmark_key_${i}`);
    }
    const lookupTime = performance.now() - lookupStart;
    
    // Benchmark node additions
    const addStart = performance.now();
    for (let i = 0; i < 10; i++) {
      ring.addNode(`benchmark_node_${i}`);
    }
    const addTime = performance.now() - addStart;
    
    return {
      lookupsPerSecond: operations / (lookupTime / 1000),
      avgLookupTime: lookupTime / operations,
      avgNodeAddTime: addTime / 10
    };
  }
}

Interview-Focused Content

Junior Level (2-4 YOE)

Q: What is consistent hashing and why is it better than simple modulo hashing? A: Consistent hashing is a technique that maps both keys and nodes to a circular hash ring. Unlike modulo hashing which requires redistributing most data when nodes change, consistent hashing only requires redistributing keys from the affected node to its neighbors, typically moving only 1/N of the data when adding/removing one node from N nodes.

Q: Explain the concept of virtual nodes in consistent hashing. A: Virtual nodes (vnodes) are multiple hash positions assigned to each physical node on the ring. Instead of each server having one position, it might have 100-150 virtual positions. This improves load distribution by reducing the impact of uneven hash spacing and provides better fault tolerance since each physical node's load is distributed across many virtual positions.

Q: What happens when a node fails in a consistent hash ring? A: When a node fails, its keys are automatically redistributed to the next node(s) clockwise on the ring. Only the keys that were assigned to the failed node need to be moved, which is approximately 1/N of the total data where N is the number of nodes. The system can continue operating with the remaining nodes.

Senior Level (5-8 YOE)

Q: How would you handle hotspots in a consistent hash ring? A: Strategies for handling hotspots include:

• Weighted nodes: Assign more virtual nodes to higher-capacity servers
• Dynamic load balancing: Monitor actual load and temporarily redirect traffic
• Key splitting: Split hot keys across multiple nodes using prefixes
• Replication: Replicate hot data to multiple nodes for read distribution
• Monitoring: Detect hotspots early and take proactive measures

Q: Design a consistent hashing implementation for a distributed cache with replication. A: Implementation considerations:

• Replication factor: Each key stored on R consecutive nodes on the ring
• Consistency levels: Support different read/write consistency requirements
• Failure handling: Detect node failures and route to healthy replicas
• Anti-entropy: Background processes to ensure replica consistency
• Quorum operations: Require majority of replicas for strong consistency

Q: What are the trade-offs between different hash functions in consistent hashing? A: Hash function considerations:

• MD5/SHA1: Good distribution but slower, cryptographically secure
• MurmurHash: Faster, excellent distribution, not cryptographically secure
• CRC32: Very fast but poorer distribution
• Trade-offs: Speed vs distribution quality vs security requirements
• Production choice: MurmurHash3 often preferred for non-security applications

Staff+ Level (8+ YOE)

Q: Design a consistent hashing strategy for a global, multi-region distributed database. A: Multi-region design considerations:

• Hierarchical rings: Regional rings with global coordination
• Data locality: Keep data close to users while maintaining global accessibility
• Cross-region replication: Asynchronous replication with conflict resolution
• Partition tolerance: Handle inter-region network partitions gracefully
• Consistency models: Different consistency guarantees for local vs global operations
• Failover strategies: Regional failover without global impact

Q: How would you migrate from simple sharding to consistent hashing in a production system? A: Migration strategy:

• Dual-write phase: Write to both old and new systems
• Background migration: Gradually move data to consistent hash ring
• Read routing: Route reads based on data location
• Validation: Verify data consistency during migration
• Rollback plan: Ability to revert if issues arise
• Performance impact: Minimize impact on production traffic

Q: What are the implications of consistent hashing for data analytics and reporting? A: Analytics considerations:

• Range queries: Difficult with hash-based partitioning
• MapReduce operations: Need to coordinate across multiple nodes
• Hot data identification: Tracking which keys/nodes are heavily accessed
• Time-series data: May need different partitioning strategies
• OLAP vs OLTP: Different consistency and availability requirements
• Data warehouse integration: ETL processes need to understand partitioning

Further Reading

• Dynamo: Amazon's Highly Available Key-value Store
• Consistent Hashing and Random Trees
• Cassandra Architecture Documentation
• Building on Quicksand by Pat Helland