Definition: Distributed hashing technique that minimizes data movement when servers are added/removed
Purpose: Efficiently distribute data across multiple servers in distributed systems
Key Feature: Only K/n keys need to be remapped when adding/removing servers (K = keys, n = servers)
Core Problem
Traditional Hashing: server = hash(key) % server_count
Issue: Adding/removing servers requires remapping most data
Example: With 3 servers, adding 1 server remaps ~75% of data
Challenge: Massive data movement during scaling
How Consistent Hashing Works
Hash Ring Concept
Structure: Circular hash space (0 to 2^160 or similar)
Server Placement: Servers hashed and placed on ring
Data Placement: Keys hashed and placed on ring
Assignment Rule: Key assigned to next server clockwise on ring
Basic Algorithm
Hash Servers: Place servers at random positions on ring
Hash Keys: Place data keys at positions on ring
Assignment: Each key goes to next server clockwise
Lookup: Hash key, traverse clockwise to find server
Virtual Nodes (Vnodes)
Problem: Uneven data distribution with few servers
Solution: Each physical server mapped to multiple virtual nodes
Benefit: More even distribution and better load balancing
Implementation: Server appears at multiple ring positions
Advantages
Minimal Data Movement
Efficiency: Only affected keys need remapping
Formula: ~K/n keys remapped when adding/removing server
Contrast: Traditional hashing remaps ~K×(n-1)/n keys
Load Balancing
Virtual Nodes: Distribute load more evenly
Flexibility: Adjust number of vnodes per server capacity
Fairness: Prevents single server from being overloaded
Fault Tolerance
Server Failure: Only affects small portion of data
Quick Recovery: Failed server’s data distributed to neighbors
Availability: System remains operational during failures
Scalability
Dynamic Scaling: Add/remove servers without major disruption
Gradual Migration: Data moves incrementally
Online Operations: No downtime required for scaling
Implementation Details
Hash Function Requirements
Uniform Distribution: Spread servers/keys evenly
Consistency: Same input always produces same output
Common Choices: MD5, SHA-1, SHA-256
Range: Large hash space to minimize collisions
Virtual Node Configuration
Typical Range: 128-512 virtual nodes per physical server
Trade-offs: More vnodes = better distribution, more overhead
Capacity Weighting: More vnodes for powerful servers
Data Replication
Strategy: Store copies at N successive servers
Fault Tolerance: Survive N-1 server failures
Consistency: Manage replicas for data consistency
Real-World Examples
Amazon DynamoDB
Implementation: Uses consistent hashing for data distribution
Partitioning: Each partition assigned range on hash ring
Scaling: Automatic partition splitting/merging
Apache Cassandra
Token Ring: Each node owns token range on ring
Virtual Nodes: num_tokens: 16 vnodes per node by default since Cassandra 4.0 (it was 256 in 3.x; fewer tokens plus the token allocation algorithm still give an even spread)
Replication: Configurable replication factor
Content Delivery Networks (CDNs)
Use Case: Distribute content across edge servers
Benefits: Minimize cache misses during server changes
Example: Akamai, CloudFlare
Distributed Caches
Redis Cluster: Not consistent hashing: 16384 fixed hash slots (slot = CRC16(key) mod 16384) assigned to nodes; resharding moves slots
Memcached: Consistent hashing for client-side sharding
Benefits: Minimize cache invalidation
Challenges & Solutions
Hotspots
Problem: Popular keys create uneven load
Solution: Use virtual nodes and monitor load
Mitigation: Redistribute popular keys manually
Range Queries
Limitation: Consistent hashing doesn’t preserve key order
Impact: Range queries require hitting multiple servers
Alternative: Use range-based partitioning for range queries
Network Partitions
Challenge: Split-brain scenarios during network failures
Solution: Use consensus algorithms (Raft, Paxos)
Strategy: Maintain quorum for operations
Variations & Improvements
Bounded Load Consistent Hashing
Problem: Some servers may still get overloaded
Solution: Limit maximum load per server
Trade-off: Slightly more complex load balancing
Jump Consistent Hashing
Google’s Approach: O(1) space complexity
Use Case: When servers are homogeneous
Limitation: Less flexible than ring-based approach
Rendezvous Hashing
Alternative: Highest Random Weight (HRW) hashing
Benefit: No ring structure needed
Use Case: When adding servers in groups
Best Practices
Virtual Node Configuration
Start Conservative: Begin with 128-256 vnodes per server
Monitor Distribution: Check for load imbalances
Adjust Gradually: Modify vnode count based on performance
Hash Function Selection
Cryptographic Quality: Use well-tested hash functions
Performance: Balance quality vs. computation cost
Consistency: Ensure all nodes use same hash function
Monitoring & Maintenance
Load Tracking: Monitor data distribution across servers
Performance Metrics: Track request latency and throughput
Rebalancing: Periodic adjustment of vnodes if needed
